Jinliang Zang

Le Wang

Ziyi Liu

Qilin Zhang

Nanning Zheng

Attention-based Temporal Weighted Convolutional Neural Network for Action Recognition

Keywords: Action recognition, Attention model, Convolutional neural netwoks, Video-level prediction, Temporal weighting

Research in human action recognition has accelerated significantly since the introduction of powerful machine learning tools such as Convolutional Neural Networks (CNNs). However, effective and efficient methods for incorporation of temporal information into CNNs are still being actively explored in the recent literature. Motivated by the popular recurrent attention models in the research area of natural language processing, we propose the Attention-based Temporal Weighted CNN (ATW), which embeds a visual attention model into a temporal weighted multi-stream CNN. This attention model is simply implemented as temporal weighting yet it effectively boosts the recognition performance of video representations. Besides, each stream in the proposed ATW framework is capable of end-to-end training, with both network parameters and temporal weights optimized by stochastic gradient descent (SGD) with backpropagation. Our experiments show that the proposed attention mechanism contributes substantially to the performance gains with the more discriminative snippets by focusing on more relevant video segments.

Introduction

Action recognition and activity understanding in videos are imperative elements of computer vision research. Over the last few years, deep learning techniques dramatically revolutionized research areas such as image classification, object segmentation [START_REF] Jianru | Automatic Salient Object Extraction with Contextual Cue In: ICCV[END_REF][START_REF] Wang | Video object discovery and co-segmentation with extremely weak supervision[END_REF][START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF] and object detection [START_REF] Ji | 3d convolutional neural networks for human action recognition[END_REF][START_REF] Karpathy | Largescale video classification with convolutional neural networks[END_REF][START_REF] Zhang | Fast implementation of sparse iterative covariance-based estimation for source localization[END_REF][START_REF] Ran | Convolutional neural network-based robot navigation using uncalibrated spherical images[END_REF][START_REF] Abeida | Iterative sparse asymptotic minimum variance based approaches for array processing[END_REF][START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF]. Likewise, Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs) have been popular in the action recognition task [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Ng | Beyond short snippets: Deep networks for video classification[END_REF][START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF][START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF][START_REF] Chéron | P-cnn: Pose-based cnn features for action recognition[END_REF][START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF][START_REF] Huang | Video-based sign language recognition without temporal segmentation[END_REF]. However, various network architectures have been proposed with different strategies on the incorporation of video temporal information. However, despite all these variations, their performance improvements over the finetuned image classification network are still relatively small. Unlike image classification, the most distinctive property of video data is the variable-length. While Images can be readily resized to the same spatial resolution, it is difficult to subsample videos temporally. Therefore, it is difficult for the early 3D ConvNet [START_REF] Ji | 3d convolutional neural networks for human action recognition[END_REF] to achieve action recognition performance on par with the sophisticated hand-crafted iDT [START_REF] Wang | Action recognition with improved trajectories[END_REF] representations.

In addition, some of the legacy action recognition datasets (e.g., KTH [START_REF] Schuldt | Recognizing human actions: a local svm approach[END_REF]) only contain repetitive and transient actions, which are rarely seen in everyday life and therefore have limited practical applications. With more realistic actions included (with complex actions, background clutter and long temporal duration), the more recent action recognition dataset, e.g., YouTube's sports, daily lives videos (UCF-101 [START_REF] Soomro | Ucf101: A dataset of 101 human actions classes from videos in the wild[END_REF]) and isolated activities in movies (HMDB-51 [START_REF] Kuehne | Hmdb51: A large video database for human motion recognition[END_REF]), offer much more realistic challenges to evaluate modern action recognition algorithms. Therefore, all experimental results in this paper are based on the UCF-101 and HMDB-51 datasets.

Previous multi-stream architecture, such as the two-stream CNN [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF], suffers from a common drawback, their spatial CNN stream is solely based on a single image randomly selected from the entire video. For complicated activities and relatively long action videos (such as the ones in the UCF-101 and HMDB-51 datasets), viewpoint variations and background clutter could significantly complicate the representation of the video from a single randomly sampled video frame. A recent remedy was proposed in the Temporal Segment Network (TSN) [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF] with a fusion step which incorporates multiple snippets 1 .

Inspired by the success of the attention model widely used in natural language processing [START_REF] Luong | Effective approaches to attention-based neural machine translation[END_REF] and image caption generation [START_REF] Xu | Show, attend and tell: Neural image caption generation with visual attention[END_REF][START_REF] Mnih | Recurrent models of visual attention[END_REF], the Attention-based Temporal Weighted CNN (ATW) is proposed in this paper, to further boost the performance of action recognition by the introduction of a benign competition mechanism between video snippets. The attention mechanism is implemented via temporal weighting: instead of processing all sampled frames equally, the temporal weighting mechanism automatically focuses more heavily on the semantically critical segments, which could lead to reduced noise. In addition, unlike prior P-CNN [START_REF] Chéron | P-cnn: Pose-based cnn features for action recognition[END_REF] which requires additional manual labeling of human pose, a soft attention model is incorporated into the proposed ATW, where such additional labeling is eliminated. Each stream of the proposed ATW CNN can be readily trained end-to-end with stochastic gradient descent (SGD) with backpropagation using only existing dataset labels.

The major contributions of this paper can be summarized as follows. (1) An effective long-range attention mechanism simply implemented by temporal weighting; (2) each stream of the proposed ATW network can be optimized end-to-end, without requiring additional labeling; (3) state-of-the-art recognition performance is achieved on two public datasets.

Related Works

Human action recognition has been studied for decades, which were traditionally based on hand-crafted features, such as dense trajectories [START_REF] Wang | Action recognition with improved trajectories[END_REF][START_REF] Wang | Action recognition by dense trajectories[END_REF] and sparse space-time interest points [START_REF] Laptev | On space-time interest points[END_REF]. In the past few years, CNN based techniques have revolutionized the image/video understanding [1, 2, 4, 6, 10-13, 16, 27]. Per the data types used for action recognition, deep neural networks based methods can be categorized into two groups: (1) RGBD camera based action recognition, usually with skeleton data and depth/3D point clouds information [START_REF] Chéron | P-cnn: Pose-based cnn features for action recognition[END_REF][START_REF] Wang | Mining actionlet ensemble for action recognition with depth cameras[END_REF][START_REF] Du | Hierarchical recurrent neural network for skeleton based action recognition[END_REF];

(2) conventional video camera based action recognition. RGBD camera based action recognition offers 3D information, which is a valuable addition to the conventional RGB channels. Such datasets are usually captured by the Microsoft Xbox One Kinect Cameras, such as The Kinetics dataset [START_REF] Chéron | P-cnn: Pose-based cnn features for action recognition[END_REF]. Despite its obvious advantage, there are some limiting factors which restrict such model from wide applications. RGBD video datasets are relatively new and labelled ones are not always readily available. A huge backlog of videos captured by conventional RGB camcorders cannot be parsed by such methods due to modality mismatch [START_REF] Zhang | Multi-view visual recognition of imperfect testing data[END_REF]. In addition, pure pose/skeleton based pipelines rarely achieve recognition accuracy on par with RGB video frame based pipelines [START_REF] Zhang | Can visual recognition benefit from auxiliary information in training?[END_REF][START_REF] Zhang | Auxiliary training information assisted visual recognition[END_REF], making them more suitable for an auxiliary system to existing ones.

Inspired by the success of computer vision with still RGB images, many researchers have proposed numerous methods for the conventional RGB video camera based action recognition. Ji et al. [START_REF] Ji | 3d convolutional neural networks for human action recognition[END_REF] extend regular 2D CNN to 3D, with promising performances achieved on small video datasets. Simonyan et al. [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF] propose the two-stream CNN, with each steam being a regular 2D CNN. The innovation is primarily in the second CNN steam, which parses a stack of optical flow images that contain temporal information. Since then, optical flow is routinely used as the secondary modality in action recognition. Meanwhile, 3D CNN has evolved, too. Tran et al. [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF] modified traditional 2D convolution kernels and proposed the C3D network for spatiotemporal feature learning. Feichtenhofer et al. [START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF] discovered one of the limiting factors in the two-stream CNN architecture, only a single video frame is randomly selected from a video as the input of the RGB image stream. They proposed five variants of fusing spatial CNN stream and two variants for the temporal steam. Additionally, Donahue et al. [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF] developed a recurrent architecture (LRCN) to boost the temporal discretion. Consecutive video frames are loaded with redundant information and noises, therefore, they argue that temporal discretion via LRCN is critical to action recognition. Some recent literature also proposed new architectures with special considerations for temporal discretion [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Huang | Video-based sign language recognition without temporal segmentation[END_REF][START_REF] Yao | Describing videos by exploiting temporal structure[END_REF][START_REF] Gaidon | Temporal localization of actions with actoms[END_REF].

Formulation

Firstly, the temporally structured video representation is introduced, followed by the temporal attention model and the proposed ATW framework.

Temporally Structured Representation of Action

How do various CNN based architectures incorporate the capacity to extract semantic information in the time domain? According to the previous two-stream CNN [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF] literature, there are generally 3 sampling strategies: (1) dense sampling in time domain, the network inputs are consecutive video frames covering the entire video; (2) spare sampling one frame out of τ (τ ≥ 2) frames, i.e., frames at time instants 0, t, t + τ, t + 2τ, • • • , t + N τ are sampled; (3) with a target number of N segments2 , non-overlapping segments are obtained by evenly partition the video into N such chunks, as illustrated in Fig. 1.

As noted by [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF][START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF], the dense temporal sampling scheme is suboptimal, with consecutive video frames containing redundant and maybe irrelevant information, recognition performance is likely to be compromised. For the sparse sampling strategy with τ intervals, the choice of τ is a non-trivial problem. With τ too small, it degrades to the dense sampling; with τ too large, some critical discriminative information might get lost. Therefore, the third sampling scheme with fixed target segments is arguably the advisable choice, given the segment number N is reasonably chosen.

Suppose a video V is equally partitioned into N segments, i.e., V = {S k } N k=1 , where S k is the k-th segment. Inspired by [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Zhang | Fast implementation of sparse iterative covariance-based estimation for array processing[END_REF], multi-modality processing is beneficial. Therefore, three modalities (RGB video frame, optical flow image and warped optical flow image3 ) are included in our proposed ATW network.

One RGB video frame, five optical flow image and five warped optical flow images are randomly sampled from each segment S k , as illustrated in Fig. 1, and respectively used as the inputs to the spatial RGB ResNet stream, temporal flow ResNet stream, and temporal warped flow ResNet stream, as shown in Fig. 2. RGB, optical flow and warped optical flow images sampled from the same video segment are grouped in a snippet. Each snippet is processed by the proposed 3-stream ATW network and a per-snippet action probability is obtained. After processing all snippets, a series of temporal weights are learned via the attention model, which are used to fuse per-snippet probabilities into video-level predictions.

Temporal Attention Model

The proposed ATW network architecture is presented in Fig. 2. Our base CNN is the ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] or BN-Inception [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF], which are both pretrained on the Im-ageNet dataset [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]. During the training phase, every labeled input video V is uniformly partitioned into N segments, i.e.,

V = {M RGB i , M F i , M W F i , y} N i=1 , where M RGB i , M F i , M W F i
represent the RGB, optical flow and warped optical flow images from the ith snippet, with y being the corresponding action label. The 3 CNN stream (C RGB , C F and C W F ) map each input to corresponding feature vector as

C RGB (M RGB i ) = a RGB i , C F (M F i ) = a F i , C W F (M W F i ) = a W F i , i = 1, • • • , N, (1)
where we call these a RGB att , a F att , a W F att action feature vectors, and use a i to represent any given one from the 3 modalities. Note that w i is the expected importance value of the ith snippet relative to the entire video. Evidently, if w i ≡ 1

N , the attention model degrades to naive averaging. The weight w i is computed by the attention model f att by a multi-layer perceptron conditioned on the previous fully-connected hidden state (i.e., w att ). The value of weight w i decides which part of the segments should to pay attention to. Formally, the attention model f att is defined as

e i = f att (w att , a i ) = w T att a i . (2)
The weight w i of each action vector is computed by where each w i are normalized by passing through a softmax function, which guarantees they are positive with i w i = 1. Finally, the attention mechanism ϕ is implemented with a linear layer followed by a rectifier (ReLu), which serve as a temporal weighting function that aggregates all the per-snippet prediction probabilities into a per-video prediction. After training, the attention model obtains a set of non-negative weights {w i } N i=1 , so the weighted attention feature is obtained by

w i = exp e i j exp e j , (3)
A RGB att = ϕ(a RGB 1 , • • • , a RGB N ) = i w i a RGB i , A F att = ϕ(a F 1 , • • • , a F N ) = i w i a F i , A W F att = ϕ(a W F 1 , • • • , a W F N ) = i w i a W F i . (4)
For better readability, we give this new action feature vector A att a name as attention vector. To emphasize, the attention model directly computes a soft alignment, so that the gradient of the loss function is trained by backpropagation.

Implementation Details

During the training phase, images from all three modalities (RGB, optical flow and warped optical flow) are cropped to 224×224. We employ cross modality pretraining [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF]. Firstly, the spatial stream (ResNet or BN-Inception) is pre-trained on the ImageNet image classification dataset. Subsequently, these pre-trained weights are used to initialize all 3 streams in the ATW. Each stream of the proposed ATW is trained independently. We use a single frame (1) and a stack of ( 5) consecutive (warped) optical flow frame as inputs. Based on the standard cross-entropy loss function, the SGD algorithm is used with a mini-batch size of 128 videos. We use an initial learning rate of 0.001 for the spatial stream and 0.005 for both temporal streams. For spatial stream, the learning rate is multiplied by a factor of 0.1 every 2000 iterations. For both temporal streams, the learning rate decay is divided into stages. Learning rates are multiplied by 0.1 at iterations 12000 and 18000. All momentums are fixed at 0.9.

During the testing phase, with each testing video, a fixed number of snippets (80 in our experiments) are uniformly sampled. We use weighted average fusion (1, 1, 0.5 for the spatial stream, optical flow stream, and warped optical flow stream, respectively) to generate a per-video prediction.

Pytorch [START_REF] Paszke | [END_REF] is used in our experiments with optical flow and warped optical flow extracted via OpenCV with CUDA 8.0. To speed up training, 2 NVIDIA Titan Xp GPUs are used.

Experiments

Trimmed Action Datasets. We evaluate our approach on two popular action recognition benchmarks, namely UCF-101 [START_REF] Soomro | Ucf101: A dataset of 101 human actions classes from videos in the wild[END_REF] and HMDB-51 [START_REF] Kuehne | Hmdb51: A large video database for human motion recognition[END_REF]. The UCF-101 dataset is one of the biggest action datasets containing 13320 videos clips distributed in 101 classes. HMDB-51 dataset is a very challenging dataset with 6766 videos (3570 training and 1530 testing videos) in 51 classes. Evaluation on these two trimmed datasets is performed using average accuracy over three training/testing splits. Baselines. Throughout the following section, we compare our proposed ATW network with the standard base architecture, mostly two-stream with the single segment of a video (N = 1). For network architecture, we choose the traditional BN-Inception [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] for comparison in experiments. Comparison with Different Consensus Functions. Firstly, we focus on comparing the attention model from two optional consensus functions: (1) max segmental consensus; (2) average segmental consensus. The max and weighted average consensus function is injected at last fully-connected layer, whereas, average consensus can be used after softmax layer. On the other hand, our attention model is set before softmax layer. The experimental performance is summarized in Table 1. We implement these four segmental consensuses with the BN-Inception ConvNet [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] on the first split of UCF-101. The number of segmentation N is set to 4. We use the weighted average fusion of three-stream outputs to generate the video-level prediction. Average segmental consensus performs slightly better than max function. The best result is obtained by the proposed attention model. Thus it can be seen the usage of attention model significantly improves temporal structure for action recognition. Multi-Segment. Specially, in Table 3, we use RGB modality for training on multi-segment temporal structure with BN-Inception ConvNet [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF]. Note that if N < 3, the model is oversimplified, and the performance on UCF-101 (split1) has seriously degraded. The attention model boosts the mAP with 85.80% on the UCF-101 dataset and 53.88% on HMDB-51 dataset (N =4), resulting from the successfully reduced training error. This comparison verifies the effectiveness of the soft attention mechanism on long-range temporal structure. Parameters Initialization and Activation Function. As we train the proposed ATW CNN, an appropriate initialization of the attention layer's parameters is crucial. We compare different initialization strategies: (1) the weight w i is set to 1, bias is 0; (2) the weight w i is set to 1 N , bias is 0; (3) random Gaussian distribution initialization. In addition, on behalf of finding the most fitting activation functions, we tested several traditional activation functions in the attention layer. As shown in Table 2, on the UCF-101 dataset, 1 for weight and 0 for bias initialization achieves 85.80% on the top of the three.

Comparison with State-of-the-arts. We present a comparison of the performance of Attention-based Temporal Weighted CNN and previous state-of-the-art methods in Table 4, on UCF-101 and HMDB-51 datasets. For that we used a spatial ConvNet pre-trained on ImageNet, the temporal ConvNet was trained by cross-modality pretraining. We choose ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] for network architecture. As can be seen from Table 4, both our spatial and temporal nets alone outperform the hand-crafted architectures of [START_REF] Wang | Action recognition with improved trajectories[END_REF][START_REF] Cai | Multi-view super vector for action recognition[END_REF][START_REF] Peng | Bag of visual words and fusion methods for action recognition: Comprehensive study and good practice[END_REF][START_REF] Wang | Mofap: A multi-level representation for action recognition[END_REF] by a large margin. The combination of attention improves the results and is comparable to the very recent state-of-the-art deep models [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF][START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF][START_REF] Sun | Human action recognition using factorized spatio-temporal convolutional networks[END_REF][START_REF] Wang | Action recognition with trajectory-pooled deepconvolutional descriptors[END_REF][START_REF] Varol | Long-term temporal convolutions for action recognition[END_REF][START_REF] Zhu | A key volume mining deep framework for action recognition[END_REF][START_REF] Fernando | Modeling video evolution for action recognition[END_REF][START_REF] Ni | Motion part regularization: Improving action recognition via trajectory selection[END_REF]. Visualization. To analyze the ability of the proposed attention model and to select key snippets from long-range temporal multi-segment, we visualize what the proposed model has learned on frame-level, which can help to understand the operation of attention interpreting the feature activity. We test our model on several videos to acquire the expected value of the action feature, which can map this attention back to the input temporal dimension. Fig. 3 presents what input 55.9% DT [START_REF] Cai | Multi-view super vector for action recognition[END_REF] 83.5% iDT [START_REF] Wang | Action recognition with improved trajectories[END_REF] 57.2% iDT [START_REF] Wang | Action recognition with improved trajectories[END_REF] 85.9% BoVW [START_REF] Peng | Bag of visual words and fusion methods for action recognition: Comprehensive study and good practice[END_REF] 61.1% BoVW [START_REF] Peng | Bag of visual words and fusion methods for action recognition: Comprehensive study and good practice[END_REF] 87.9% MoFAP [START_REF] Wang | Mofap: A multi-level representation for action recognition[END_REF] 61.7% MoFAP [START_REF] Wang | Mofap: A multi-level representation for action recognition[END_REF] 88.3% Two Stream [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF] 59.4% Two Stream [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF] 88.0% VideoDarwin [START_REF] Fernando | Modeling video evolution for action recognition[END_REF] 63.7% C3D [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF] 85.2% MPR [START_REF] Ni | Motion part regularization: Improving action recognition via trajectory selection[END_REF] 65.5% Two stream +LSTM [START_REF] Ng | Beyond short snippets: Deep networks for video classification[END_REF] 88.6% FSTCN (SCI fusion) [START_REF] Sun | Human action recognition using factorized spatio-temporal convolutional networks[END_REF] 59.1% FSTCN (SCI fusion) [START_REF] Sun | Human action recognition using factorized spatio-temporal convolutional networks[END_REF] 88.1% TDD+FV [START_REF] Wang | Action recognition with trajectory-pooled deepconvolutional descriptors[END_REF] 63.2% TDD+FV [START_REF] Wang | Action recognition with trajectory-pooled deepconvolutional descriptors[END_REF] 90.3% LTC [START_REF] Varol | Long-term temporal convolutions for action recognition[END_REF] 64.8% LTC [START_REF] Varol | Long-term temporal convolutions for action recognition[END_REF] 91.7% KVMF [START_REF] Zhu | A key volume mining deep framework for action recognition[END_REF] 63.3% KVMF [START_REF] Zhu | A key volume mining deep framework for action recognition[END_REF] 93.1% TSN (3 modalities) [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF] 69.4% TSN (3 modalities) [START_REF] Wang | Temporal segment networks: Towards good practices for deep action recognition[END_REF] 93.4%

Proposed ATW 70.5% Proposed ATW 94.6%

images originally caused an attention value. The first row shows the top ranked four frames with their corresponding attention weights, and the second row shows the lowest ranked four frames. The attention model pays more attention to the relevant frames than irrelevant frames, and this means that the attention model always focuses on the foreground over time.

Conclusion

We presented the Attention-based Temporal Weighted Convolutional Neural Network (ATW), which is a deep multi-stream neural network that incorporates temporal attention model for action recognition. It fuses all inputs with a series of data-adaptive temporal weights, effectively reducing the side effect of redundant information/noises. Experimental results verified the advantage of the proposed method. Additionally, our ATW can be used for action classification from untrimmed videos, and we will test our proposed method on other action datasets in our future work.

Fig. 1 .

 1 Fig. 1. Snippet generation with a fixed target number (N ) of chunks. A video is evenly portioned into N non-overlapping segments. Each segment contains approximately the same number of video frames. As shown above, 2 additional modalities derived from RGB video frames are also included, i.e., optical flows and warped optical flows. RGB, optical flow and warped optical flow images sampled from the same segment are grouped in a snippet.

Fig. 2 .

 2 Fig.2. Proposed ATW network architecture. Three CNN streams are used to process spatial RGB images, temporal optical flow images, and temporal warped optical flow images, respectively. An attention model is employed to assign temporal weights between snippets for each stream/modality. Weighted sum is used to fuse predictions from the three streams/modalities.

Fig. 3 .

 3 Fig. 3. Visualization of the focus of attention on four videos from UCF-101 dataset over temporal dimension. The model learns to focus on the relevant parts. The attention weight is given on top of each image. The higher the attention weight (wi) of the frame, the more critical to classify the action.

RGB Input Flow Input Basketball Dunk Flow Feature Attention Vector Spatial ResNet:RGB

		conv	conv	conv	conv	conv	conv
							RGB Feature	Attention Vector	Action Label
		conv	Temporal ResNet:Flow conv conv conv conv conv	linear linear Attention ReLu Model	w1 w3 w2 Attention Vector	Playing Guitar Playing Guitar Apply Eye Makeup Juggling Balls Juggling Balls
		conv	conv	conv	conv	conv	conv
	Warped Flow Input	Temporal ResNet:Warped Flow	Warped Flow Feature	Attention-based Temporal Weighted Network

Table 1 .

 1 Exploration of different segmental consensus functions on the UCF-101 dataset (split1).

	Consensus Function Spatial ConvNets Temporal ConvNets Two-Stream
	Max	85.0%	86.0%	91.6%
	Average	85.0%	87.9%	93.4%
	Attention Model	86.7%	88.3%	94.6%

Table 2 .

 2 Experiments of different initialization strategies for initializing the attention layer's parameters and several traditional activation functions on the UCF-101 dataset (split1). Specifically, weight = 1/N (N = 4) equivalent to average consensus.

	Initialization	Spatial-Stream Activation Function Spatial-Stream
	weight = 1/N	84.44%	tanh	84.91%
	weight = 1	85.17%	sigmoid	85.29%
	random gaussian	85.80%	relu	85.80%

Table 3 .

 3 Exploration of ATW CNN with more number of segments on the UCF-101 dataset and HMDB-51 dataset (split1).

	Dataset	N=1	N=2	Spatial-Stream Accuracy N=3 N=4 N=5 N=6	N=7	N=8
	UCF-101	83.33% 83.89% 84.80% 85.80% 85.29% 85.21% 85.04% 85.55%
	HMDB-51 50.07% 53.33% 53.01% 53.88% 53.33% 55.36% 53.20% 53.14%

Table 4 .

 4 Comparison of our method with other state-of-the-art methods on the UCF-101 dataset and HMDB-51 dataset.

	HMDB-51	UCF-101
	Model	Accuracy Model	Accuracy
	DT [40]

Snippets are multi-modal data randomly sampled from non-overlapping video segments, see Fig.1. Typically a video is divided into 1 to 8 segments. Segments are typically much longer than "clips" used by 3D CNN literature, e.g., the 16-frame clip in C3D[START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF].

Typical N values are from 1 to 8.

As in[START_REF] Wang | Action recognition with improved trajectories[END_REF], warped optical flow is obtained by compensating camera motion by an estimated homography matrix.

Acknowledgment

This work was supported partly by NSFC Grants 61629301, 61773312, 91748208 and 61503296, China Postdoctoral Science Foundation Grant 2017T100752, and key project of Shaanxi province S2018-YF-ZDLGY-0031.


Irsha Tehseen
email: irshatehseen@gmail.com

Rasool Ghulam

Khadija Tahir

Mubbashir Shakeel

Ali

Ghulam Rasool Tahir

Khadija Shakeel

Corpus Based Machine Translation for Scientific Text

Keywords: Machine Translation, Corpus Based Machine Translation, Scientific Text Translation, Term tagger

Introduction

Language is the main medium for humans to communicate. Whenever humans need to communicate, having different languages, they have to face issues. This arises the demand to translate. This demand is as old as the human [START_REF] Homiedan | Machine translation[END_REF]. Human experts in multiple languages are offering their services of translation from many decades. The demand of translation is increasing with the growth of cross-regional communication. Different sources of data are accessed worldwide. They cannot be written or translated in every language manually. They need to be written in one language and automatically translated in user preferred. This demands to cover the barrier of the language. [START_REF] Callison-Burch | Findings of the 2011 workshop on statistical machine translation[END_REF]. Due to increase of translation demand humans are not able to fulfill the needs of the society, in response the automate process of translation is generated [START_REF] Hutchins | An introduction to machine translation[END_REF]. This idea fascinated the researchers. This research area is known as Machine Translation.

Machine Translation

Machine Translation (MT) is the process of translation from one language to another by the use of computing devices [START_REF] Homiedan | Machine translation[END_REF]. MT is an automatic process in which all the translation jobs are done with the help of programming languages and software [START_REF] Homiedan | Machine translation[END_REF][START_REF] Khan | Translation rules and ann based model for english to urdu machine translation[END_REF]. All materials needs to be translated, this includes commercial, business and scientific documents, instruction manuals, text books, World Wide Webs. [START_REF] Hutchins | An introduction to machine translation[END_REF][START_REF] Khan | Beyond translation memory: Computers and the professional translator[END_REF]. Machine Translators are serving for multiple languages. Quality of MT also varies with language pairs. Two languages for instance English to French may have high quality of translation, some other pair may have translation of low quality. Currently none of the language pairs are translated accurately. The main difficulty in automated translation of one language to another is varied written scripts and multiple lexical choices for a single idea. A single world may have various meanings, in different situations it is used for different purposes. At the current level of research, a single level of representation of every language is almost impossible. Every language needs to be considered separately with its scripting choices for automatic translation [6].

English to Urdu Machine Translation

English and Urdu both are Indo-European languages but differ in written scripts and morphology. Urdu is a right to left scripted language and Eng. is left to right. Eng. follows the same order while Urdu is a free order language. English always follows the subject-verb-object order, Urdu mostly follows subject-object-verb pattern but not always [START_REF] Jawaid | English to urdu statistical machine translation: Establishing a baseline[END_REF]. Although a lot of work is done for MT but still English to Urdu MT is in its early stage. This pair of language is considered a low resource language because enough standard translated text is not available for the training of the system [START_REF] Salam | Example-based machine translation for lowresource language using chunk-string templates[END_REF].

Machine Translation Service for Scientific Text

The number of scientific texts other than English keeps increasing quickly as compared to past, as the scientific communities in non-English countries grow [START_REF] Altbach | The imperial tongue: English as the dominating academic language[END_REF]. However, majority of high impact journals are published in English [START_REF] Altbach | The imperial tongue: English as the dominating academic language[END_REF]. For translating scientific text, considering only the semantic representation is not enough. Different terminologies have various meanings in multiple domains. A single word may give a total different concept in various fields. Terms are different in every subject, while translating from one language to another these terms should be considered according to the scenario. For the true sense of data all of the terms should be translated with true meaning of the domain. None of the translator is working on the translation of scientific text in true meaning. While translating scientific text accuracy is a major issue [START_REF] Olohan | Science in Translation[END_REF]. We can get more advantage by using MT for translating these scientific text in local language or from local language to English language.

Problems in Automated Translation of Scientific Text

Translation of scientific text is not as simple as it seems. There are approx. 10 main branches of science and each branch is followed by many sub branches so approx. there are more than 100 fields of sciences [START_REF] Sandstrom | How many 'sciences' are there?[END_REF]. Each field has different terms and meaning of terms, so a single generic system for all these sciences is not easy. Translation of scientific text requires domain and translator expert. These texts are written by using Languages for Special Purposes (LSP). Translation of scientific text not only requires the knowhow of the language but it also requires the deep understanding of the field. For the translation of scientific text both of the skills: translation skill and domain skill are compulsory [START_REF] Wright | Editors' preface: Technical translation and the american translator[END_REF][START_REF] Byrne | Scientific and Technical Translation Explained[END_REF].

Although there are many translators doing the job but translation of scientific text is still ambiguous. Translators are not trained for domain skills. Translators are working only with the translation. There is need to develop a MT system which can be a benchmark for translating scientific text while considering domain of the text.

Shortfalls in Existing MT Techniques for Scientific Text

Various terminologies are overlapped in multiple fields but their meaning is different in ever field. Such as the word "monitor" is a device in the field of Computer Science (CS) , but in classroom environment it is used for a student. The word "Python", in CS is the name of a programming language, outside of the CS it is considered a snake. Both examples shows generic words may have different meanings in various field.

Existing translators are translating data in generic meanings. They are not able to translate scientific text in real sense. These systems do not distinguish between domains. Above mentioned are the few samples of basics sentences of CS. Translating a whole book or a research paper is more pathetic, humorous.

So far no such benchmark is available for translating scientific text. People have to make extra effort in understanding scientific text because have to understand the language also. So there is need of a study, to identify different techniques which should be used for better translation of scientific text. It is to decrease the effort in learning language skills or translating manually. Existing work do not bridge this gap to translate the scientific text with correct sense. There is a need to develop a customized translator which can effectively bridge this gap. Domain specific translators are tend to give better results as compared to the translation of generic systems [START_REF] Micher | Improving domain-specific machine translation by constraining the language model[END_REF][START_REF] Xu | Domain dependent statistical machine translation[END_REF][START_REF] Hatim | Discourse and the Translator[END_REF].

Methodology

Terms of any field plays an important role in the translation of the text. It enables to understand the meaning or idea correctly. For quality translation a term tagger can play an important role in translation. It is complex to create single term tagger for all the fields together. This section focuses on the development of a scientific text translator and a term tagger for the field of CS. This translator and term tagger can be trained for any domain of science. The main contribution of the proposed work is term corpus of CS, translation of that corpora and, a term tagger of scientific text and translation of text according to the meaning of the domain.

Overview of Proposed Scientific Text Translator

The development of a quality translator is a challenging and tricky task in MT research community. This is mainly due to the diversity of the languages. We have proposed a customized domain specific translator for scientific text. A complete overview of the system is given in the Fig. It is composed of 4 modules. In module 1, inputted text is converted into plain text. The module 2 tag the terms and divide the sentences into phrases. CBR (Case Based Reasoning) Trainer is used for the searching and retrieving case from case base in 3rd module. At the end, module 4 is used to reorder the phrases to make the translation quality a bit better and readable.

Module 2: Sentence Fragmentation

There are two ways to keep the sentences into the corpus. One is to keep whole sentence. It will decrease the scope of the sentence as one sentence is equal to only one example. The second choice is to fragment it into multiple phrases. Each sentence is divided into two or more phrases. Scope of the sentences is increased with this. A broader range of sentences is covered by using genetic algorithm [START_REF] Echizen-Ya | Machine translation method using inductive learning with genetic algorithms[END_REF]. This module is divided into the following submodules: Term Taggers, Phrase Generator. Term Tagger: Terms are used to express a concept, mainly in a particular domain of the study. A list of terms is developed to handle the terms of the computer science. Term Tagger tag and checks whether the terms are present in the sentence or not. If it found one or more terms in the sentence, it tags the terms are T1, T2.....Tn Phrase Generator: Generating phrases is a required and vital module [START_REF] Mallinson | Paraphrasing Revisited with Neural Machine Translation[END_REF]. More phrases leads to more accurate results. Our phrase generator is based on tagged terms and linking words. Linking words are available at [START_REF]Linking words and phrases[END_REF] For each case ena If case is a term case Find the case ena in the term base and make a set Ura Find the translation solutions of ena and add it to Ura and add 1 to a Else Find the case ena in the case base and make a set Ura Find the translation solutions of ena and add it to Ura and add 1 to a If ends Loop ends Find the union of all Ura's Note: a is a counter variable for counting number of phrases en is a set of English Computer Science (CS) phrases ur is the set of Urdu CS Translation phrases for each ea there is an equivalent part Ura. It is considered as follows: En = Set of English CS phrases = { en1, en2, en3.....enn } Ur = Union of all the Urdu CS Translation phrases = Ur1 + Ur2 + Ur3.................Urn Here number of phrases of a particular sentence is not specific and cannot be known before the actual program executes. These phrases are constructed at the run time. Solution of the cases are also only available at the run time.

Updating Corpus: New solved cases are saved for future use. Case base is updated but these cases are kept separate until they are post-edited and verified by expert.

Module 4: Reordering:

Union of Ur is presented as output. Reordering of the sentence is a separate issue. Here we only consider it to some extent, just to make the translation a bit readable.

Reordering Rules: If en1.....enn are the CS phrases in English whose equivalent phrases are Ur1 + Ur2....Urn, then the translation of [en1, en2, en3.....enn] is [Ur1 + Urn + Urn-1...... + Ur3 + Ur2]

4

Experimental studies

Here we present self-generated corpora, its translation and results. The accuracy results of our system are presented and compared with existing translators.

Experimental Corpus:

We used self-generated corpus. Generating corpus is a weighty research extraction. There are two corpus: Term Corpus; Base Corpus Term Corpus: It is our first corpus, for this corpus the terms are picked from multiple sources [START_REF] Hutchins | An introduction to machine translation[END_REF][START_REF] Knight | Machine translation glossary[END_REF][START_REF] Henderson | Encyclopedia of computer science and technology[END_REF][START_REF] Koehn | Statistical Machine Translation. Statistical Machine Translation[END_REF][START_REF] Press | Microsoft Computer Dictionary. CPG Series[END_REF]. Many resources have same terms, overlapped terms are cleaned and discarded automatically, later they are checked manually.

Base Corpus: It is our second corpora. It consists on CS phrases. These phrases are constructed from multiple sentences. Sentences are selected from CS books, research papers and Wikipedia page of CS. These sentences have various length and terms in it. Sentences are fragmented into phrases by using proposed fragmentation algorithm. All the duplicate phrases and special symbols are removed.

Translation of Corpora: It is another major issue. As there are very few standard translated text of CS is available in Urdu language. Text is translated as accurate as it can. Translation of term requires a careful and persistent effort [START_REF] Olohan | Scientific and technical translation[END_REF]. How we translated these terminology is also a separate issue. Translation of Term corpora is done according to the meanings of CS and it is also revised twice. The second step is translating Base corpora into equivalent Urdu translation. These translations still can be improved by expert. A concise overview of the above explained corpora is given in the Table 1.

Experiments:

In this section, we presented the experiments to evaluate the performance of our system. These experiments are performed by using datasets discussed in Table 1. The accuracy results of our proposed system are shown in Table 2.

Experiment 1: Evolution of Proposed Scientific Text Translator:

The purpose of this experiment is to evaluate the translation accuracy of proposed system. The experiment has been conducted on above mentioned datasets. After giving the text, first step performed is preprocessed the text according to the algorithm proposed. Second step performed is to tag the terms in the given sentence and generate phrases fragmentation algorithm. Third step is to search and retrieve solution cases. At the end of the translation process reordering is done.

Experiment 2: Comparison of Proposed Translator with competitor:

Purpose of Experiment:

The aim to conduct this experiment is to compare the proposed system's accuracy with existing systems. The experiment is performed on our internally generated datasets. This experiment is performed in three different steps. In first step, 500 sentences of CS are selected from the corpora and CS books, 50% sentences are selected from corpus, 25% from different text books and rest 25% is from Wikipedia page of CS. Second step is to check translation of selected sentences one by one and verify those translations on famous existing systems and analyzed how much of them are translated correctly.

Comparison of Existing and Proposed Scientific text translation:

Experimental results of competitors for scientific text translation are given in Table 2. We can observe that the existing systems are giving very less translation accuracy and very less terms are translated correctly. These sentences are tested on different famous translation systems. Results are given below in the table. It can be clearly seen that proposed system gives more accuracy as compared to the existing system.

Conclusion

We have introduced an effective scientific text translator. The proposed translation method is based on tagging terms of sciences and corpus based MT approach by using CBR. To meet the challenges of terminologies translation of scientific text, a term tagger for scientific text is proposed. It tags the terms of sciences and then translate with the help of self-generated Term Corpora. The performance of proposed technique has been evaluated by performing experiment on self-generated English to Urdu parallel bilingual dataset of CS. Both corpus are developed and translated. Experiment has also been conducted to provide a comparison between proposed technique and existing translation services. From the comparative results we concluded that, the proposed translator accuracy results are significantly better as compared to existing translator approaches. It gives considerable accuracy rate. Our proposed technique is also capable of handling other fields of sciences, all we need is to train the system for that domain.

The current training of the system is done on the domain of CS. If we change its training, it can effectively work for every domain of life.

Fig. 1 .

 1 Fig. 1. Overview of Proposed Scientific Text Translator

  1. The process of generating scientific text translation is comprised of following steps: Repeat step 8 for all the non-term phrase cases 12. Generate list of phrases 13. Reorder the retrieved cases as 14. Repeat step 4 to 11 for all the sentences and present solutions of the reordered case

	Proposed Algorithm Overview:
	1. Check number of sentences entered
	2. If sentence is more than one, separate each sentence
	3. Create a list of sentences
	4. Select a sentence
		phrase
	6. List of phrases generated
	7. Pick a phrase, if phrase is tagged as a term; search phrase in term base
	a. Retrieve term case	b. Repeat step 7 for all the terms
	8. If phrase is not a term, check in case base
	a. Compute similarity of the phrase in case base
	b. If similarity is 1, retrieve the case	c. If similarity is less than 1
	9. search for most similar case
	10. Retrieve most similar case
	11.

a. Remove special characters, symbols, white-spaces and tabs 5. Check for term in the sentences a. If term found, tag the term and also generate phrases based on tagged term (1) Repeat step 5a for all the terms in the sentence b. If linked word found, generate phrases based on linked words (1) Repeat step 5b for all the linked words in the

TABLE 1 .

 1 A concise overview of our experimental datasets

	Sr#	Corpora	Dataset Description	Total	Unique
	1	Term Base A Bilingual Corpus (English to Urdu) of unique CS terms	14002 Terms	10156 Terms
	2	Case Base A Bilingual Corpus (English to Urdu) of unique CS text phrases 1500 sentences /	14232
				18982 Phrases	Phrases

Table 2 .

 2 A concise overview of our experimental datasets

	#	Translator	Type	Sentences test Terms in sentences Successfully translated terms Accuracy %
	1	Proposed System Domain Specific 500	379	301	79%
	2	Google	Generic	500	379	102	26%
	3	Being	Generic	500	379	153	40%
	4	Babylon	Generic	500	379	77	20%
	5 Dictionary Translator Generic	500	379	46	12%


Alexandra Degeest
email: adegeest@he2b.be

Michel Verleysen
email: michel.verleysen@uclouvain.be

Benoît Frenay
email: benoit.frenay@unamur.be

Benoît Frénay

Smoothness Bias in Relevance Estimators for Feature Selection in Regression

Keywords: feature selection, smoothness, filter methods, mutual information, noise variance

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

High-dimensional datasets are now ubiquitous. Selecting a subset of the most relevant features is useful to ease the learning process, to alleviate the curse of dimensionality, to increase the interpretability of features, to visualise data, among others. Many works focus on methods to reduce the number of features in datasets [START_REF] Guyon | An introduction to variable and feature selection[END_REF][START_REF] François | Resampling methods for parameterfree and robust feature selection with mutual information[END_REF][START_REF] Verleysen | Advances in feature selection with mutual information[END_REF][START_REF] Frénay | Feature selection for nonlinear models with extreme learning machines[END_REF][START_REF] Gomez-Verdejo | Information-theoretic feature selection for functional data classification[END_REF][START_REF] Kohavi | Wrappers for feature subset selection[END_REF][START_REF] Paul | Kernel methods for heterogeneous feature selection[END_REF]. These methods can be roughly categorised into filter methods, wrappers and embedded methods that all have their respective advantages and drawbacks [START_REF] Guyon | An introduction to variable and feature selection[END_REF]. This paper focuses on filter methods, which have the advantage to be fast because they do not require to train any model during the feature selection process, contrarily to wrappers [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] and embedded methods [START_REF] Efron | Least angle regression[END_REF]. Filters use a relevance criterion during the feature selection process. Three popular relevance criteria used to select features in regression tasks are the correlation, the mutual information and the noise variance. This paper focuses on mutual information and noise variance because of their property to be able to detect features that have nonlinear relationships with the variable to predict. It shows that the statistical estimators of mutual information and of noise variance both suffer from a bias, mostly when small samples are considered, and that this bias may affect the selection of the features. The paper also shows that this bias disappears in large datasets, but faster when using noise variance than when using mutual information.

The remaining of the paper is organised as follows. Feature selection in regression with filters is detailed in Section 2. Section 3 analyses the behaviour of mutual information and Delta Test, and discusses the potential bias for small sample datasets. In order to confirm the bias and its consequences, simple experiments are described in Section 4 and their results are shown in Section 5. Finally, conclusions are given in Section 6.

2

Feature Selection with Filters

In the context of filter methods for feature selection, a relevance criterion is necessary to select the most relevant features among all the available ones. The relevance criterion aims at measuring the existing relationship between a feature or a set of features and the variable to predict. There exist several relevance criteria. Correlation is the simplest one, but it is only able to detect linear relationships between random variables, and it is restricted to the univariate case (sets of features can only be evaluated individually, which prevents to take into account the possible relations between the features themselves). In this paper, we focus on nonlinear and multivariate relationships between a set of random input variables and one random output variable. For this type of relationships, mutual information (MI) and noise variance are both popular measures used as relevance criteria for filter methods. Both need to be estimated in practice on a finite set of data: traditional estimators are the Kraskov estimator for the former and the Delta Test for the latter. These criteria have been repeatedly used for feature selection in regression problems [START_REF] Frénay | Is mutual information adequate for feature selection in regression?[END_REF][START_REF] Doquire | Risk estimation and feature selection[END_REF]. This section reviews the mutual information (MI) and noise variance criteria, and their Kraskov and Delta Test estimators. Both estimators are based on k-nearest neighbours. The next sections show that these estimators implicitly take into account a measure of smoothness (Section 3), which could lead to a bias in the choice of features during the feature selection process (Sections 4 and 5).

Feature Selection with Mutual Information

Mutual information (MI) is a popular criterion for filter methods [START_REF] Gomez-Verdejo | Information-theoretic feature selection for functional data classification[END_REF][START_REF] Degeest | Feature ranking in changing environments where new features are introduced[END_REF][START_REF] Brown | Conditional likelihood maximisation: A unifying framework for mutual information feature selection[END_REF][START_REF] Battiti | Using mutual information for selecting features in supervised neuralnet learning[END_REF][START_REF] Vergara | A review of feature selection methods based on mutual information[END_REF]. Based on entropy, it is a symmetric measure of the dependence between random variables, introduced by Shannon in 1948 [START_REF] Shannon | A mathematical theory of communication[END_REF]. MI measures the information contained in a feature, or in a group of features, with respect to another one. It has been shown to be a reliable criterion to select relevant features in classification [START_REF] Frénay | Theoretical and empirical study on the potential inadequacy of mutual information for feature selection in classification[END_REF] and regression [START_REF] Frénay | Is mutual information adequate for feature selection in regression?[END_REF][START_REF] Doquire | Risk estimation and feature selection[END_REF][START_REF] Guillén | New methodologies based on delta test for variable selection in regression problems[END_REF][START_REF] Yu | Variable selection for financial modeling[END_REF]. This paper focuses on regression problems.

Let X and Y be two random variables, where X represents the features and Y the target. MI measures the reduction in the uncertainty on Y when X is known Where [START_REF] Guyon | An introduction to variable and feature selection[END_REF] is the entropy of Y and

(2)

(3)
is the conditional entropy of Y given X. The mutual information between X and Y is equal to zero if and only if they are independent. If Y can be perfectly predicted as a function of X, then I(X;Y) = H(Y).

In addition to the criterion, feature selection needs a search procedure to find the best feature subset among all possible ones. Given the exponential number of possible subsets, search procedures such as greedy search or genetic algorithms are used to find the best subset of features without having to compute the selection criterion between all subsets of variables and the output. Among these subsets, the one maximising the MI with the output is selected.

In practice, MI cannot be directly computed because it is defined in terms of probability density functions. These probability density functions are unknown when only a finite sample of data is available. Therefore, MI has to be estimated from the dataset. The estimator introduced by Kraskov et al. [START_REF] Kraskov | Estimating mutual information[END_REF] is based on a k-nearest neighbour method and results from the Kozachenko-Leonenko entropy estimator [START_REF] Kozachenko | Sample estimate of the entropy of a random vector[END_REF] (4

)
where k is the number of neighbours, N is the number of instances in the dataset, d is the dimensionality, c d = (2π d/2 )/Γ(d/2) is the volume of the unitary ball of dimension d, ϵ k (i) is twice the distance from the i th instance to its k th nearest neighbour and ψ is the digamma function.

Kraskov estimator (4) of the mutual information is then [START_REF] Gomez-Verdejo | Information-theoretic feature selection for functional data classification[END_REF] where τ x (i) is the number of points located no further than the distance ϵ X (i,k)/2 from the i th observation in the X space, τ y (i) is the number of points located no further than the distance ϵ Y (i,k)/2 from the i th observation in the Y space and where ϵ X (i,k)/2 and ϵ Y (i,k)/2 are the projections into the X and Y subspaces of the distance between the i th observation and its k th neighbour.

Feature Selection with Noise Variance

Noise variance is another filter criterion used for feature selection. Its definition is even more intuitive than mutual information. With this filter criterion, the noise represents the error in estimating the output variable by a function of the input variables, under the hypothesis that this function could be built (by a machine learning regression model). It is a filter criterion because it does not require building a regression model, but it is close to the idea of a wrapper method because the goal is to evaluate how good a model could be.

Let us consider a dataset with N instances, d features X j , a target Y and N inputoutput pairs (x i ,y i ). The relationship between these input-output pairs is [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] where f is the unknown function between x i and y i , and ϵ i is the noise or prediction error when estimating f. The principle is to select the subsets of features which lead to the lowest prediction error, or lowest noise variance [START_REF] Guillén | New methodologies based on delta test for variable selection in regression problems[END_REF].

In practice the noise variance has to be estimated, e.g. with the Delta Test [START_REF] Yu | Variable selection for financial modeling[END_REF]. The Delta Test δ is defined as [START_REF] Paul | Kernel methods for heterogeneous feature selection[END_REF] where N is the size of the dataset, y NN(i) is the output associated to x NN(i) , x NN(i) being the nearest neighbour of the point x i .

Similarly to the use of mutual information for feature selection, when using the Delta Test the relationships between several subsets of features and Y are computed, again with a search procedure such as a greedy search. Among these subsets of features, the one minimising the value of δ with Y will be selected. The Delta Test has also been widely used for feature selection [START_REF] Eirola | Using the delta test for variable selection[END_REF][START_REF] Eirola | The delta test: The 1-nnestimator as a feature selection criterion[END_REF].

3

Behaviour of kNN-based Estimators of Relevance Criteria in Small Sample Scenarios

This section analyses the behaviour of the mutual information and noise variance estimators in small datasets.

Mutual Information Analysis

The Kraskov estimator (5) can be used to estimate MI in regression. However, as a kNN-based estimator of I(X;Y) = H(Y)-H(Y|X), it is affected by the degree of smoothness of the relationship between the target and the considered features. Indeed, the Kraskov estimator assumes that the conditional distribution p(Y|X) is stationary in the k-neighbourhood of x. However, if the neighbourhood of x is large, which is the case when the sample is small, this hypothesis does not hold anymore and the interval of observed values for Y will widen. The Kraskov estimator will consequently overestimate the conditional entropy H(Y|X) and underestimate I(X;Y). This underestimation will be more severe for non-smooth functions, as the interval of Y in the neighbourhood of x is larger in this case. Consequently, when two features will be compared, the one that has the smoother relation to Y will tend to be favoured in the feature selection.

Delta Test Analysis

To estimate the variance of the noise in regression problems, the Delta Test uses a 1nearest neighbour method by looking for the nearest neighbour of each point of the dataset and by computing a variation in target values between the point and its nearest neighbour.

The Delta Test, already defined in [START_REF] Paul | Kernel methods for heterogeneous feature selection[END_REF], can be rewritten with ( 6) as [START_REF] Efron | Least angle regression[END_REF] where noise ϵ i is i.i.d. The average behaviour of the Delta test can be characterised using a first order approximation f(x) ≈ f(x i )+∇f(x i ) T (xx i ), based on the assumption that the nearest neighbour is close enough to make this approximation sufficiently accurate. The expected value of the Delta Test is then approximated as [START_REF] Frénay | Is mutual information adequate for feature selection in regression?[END_REF] The first term of ( 9) is the noise variance, but the second term is related to the smoothness of f and is independent from the noise variance: it measures how much f changes on average from an instance x to its closest neighbour x NN . This second term is affected by two factors. First, if the gradient is small (i.e. the function is smooth), the second term remains small. Second, if instances and their closest neighbours are close (i.e. the dataset is quite large), the second term also remains small. Hence, for small datasets, the second term penalises non-smooth functions.

Discussion

In small datasets, smooth relations between features and output will have, on average, a smaller Delta Test or a higher MI result. On the opposite, a nonsmooth relation will have, on average, a larger Delta Test or smaller MI result, even with the same level of target noise. As discussed above, estimators based on k-nearest neighbours methods seem to be biased by the smoothness of functions. The two estimators make the assumption that the function does not vary too much in the proximity of the neighbours. However, in small sample and with non-smooth functions, this assumption is violated, which introduces a bias in the estimators. It is thus anticipated that smooth features will tend to be selected first when comparing two features that have the same level of information content to predict output Y. However, this short analysis does not answer the question whether this estimation bias has a real influence during the feature selection process, nor if the problem is more severe with MI or with noise variance. The next section evaluates these questions by experiments.

4

Experimental Settings

In order to study how much the smoothness can be a bias for selection criteria such as the mutual information or Delta Test in regression, experiments performed in this paper consider several functions with various smoothnesses and several sizes of datasets. These experiments are conducted to give some insights to the questions raised in the previous section, i.e. does the estimation bias has an influence while comparing features, and is the problem more severe with MI or with noise variance. Six different periodic functions have been generated with different frequencies and different levels of noise:

y 1 = f 1 (x) = sin(x) + ϵ
where ϵ ~ N(0,0.05) y 2 = f 2 (x) = sin(3x) + ϵ where ϵ ~ N(0,0.05) y 3 = f 3 (x) = sin(9x) + ϵ where ϵ ~ N(0,0.05)

y 4 = f 4 (x) = sin(x) + ϵ
where ϵ ~ N(0,0.3) y 5 = f 5 (x) = sin(3x) + ϵ where ϵ ~ N(0,0.3) y 6 = f 6 (x) = sin(9x) + ϵ where ϵ ~ N(0,0.3) [START_REF] Doquire | Risk estimation and feature selection[END_REF] Figures 1(a), 1(b), 1(c), 1(d), 1(e) and 1(f) represent the six functions f 1 , f 2 , f 3 , f 4 , f 5 and f 6 , respectively. In theory, features associated to f 1 , f 2 and f 3 (resp. f 4 , f 5 , f 6 ) should be selected equally in a feature selection process, as prediction errors (or levels of noise) are identical.

The experiments have been performed with various sizes of samples, from extremely small to large ones. For each size of the sample, an estimator of the two decision criteria, the mutual information and the noise variance, has been used to drive the selection process, in order to show the influence of the bias introduced by the smoothness of the function on both criteria. For the noise variance, the estimator used is the Delta Test, based on a k-NN method with 1-nearest neighbour, and described in Section 2.2. For the mutual information, the estimator used is the one introduced by Kraskov et al. and described in Section 2.1, also based on a k-NN method (with k=6 as suggested in [START_REF] Kraskov | Estimating mutual information[END_REF]). All experiments have been repeated 10 times; averages are reported.

Experimental Results

Figure 2 represents the average value (on 10 repetitions) of the mutual information estimator (2(a) and 2(c)) and the Delta Test estimator (2(b) and 2(d)), for increasing sizes of the dataset. All figures show a clear effect in overestimating the noise variance and underestimating the mutual information in small datasets. The over-and underestimations are much more severe for non-smooth functions (f 3 and f 6 ). It is also clear that when the size of the dataset increases, the biases tend to disappear. What is more interesting to see is that the asymptotic values of the Delta Test are reached in this experiment when the dataset includes a few hundreds of instances, while for the MI a few thousands of instances are necessary, in the same experiment (the horizontal logarithmic scales with the number of instances are different in the left and right figures). This is an argument in favour of using the noise variance rather than the mutual estimation.

When comparing the upper and lower parts of Figure 2 (both left -MI-and rightnoise variance-), it is also interesting to see that for small samples, the order of selection between features can be inverted. For example, let us consider the Delta Test values in Figures 2(b) and 2(d) for three cases. First, for 40 instances, the 6 functions will be ranked in the following order: f 1 , f 2 , f 4 , f 5 , f 3 and f 6 , given that the features with the lower Delta values are selected first. Without the bias effect shown in this paper, it would have been expected that f 1 , f 2 and f 3 would be selected first, as their capacity to predict Y is higher (or their noise is lower) than for f 4 , f 5 and f 6 . Second, for 70 instances, the 6 functions will be ranked in the following order f 1 , f 2 , f 3 , f 4 , f 5 and f 6 . In this case, the order of selection between features is not inverted anymore but the bias still remains. Finally, for approximately 300 instances, the bias disappears, the 3 functions f 1 , f 2 , f 3 obtain the same Delta value and the 3 functions f 4 , f 5 , f 6 obtain another unique Delta value, higher than the one for f 1 , f 2 , f 3 . These cases show that, for small samples, the bias has an influence on the order of selection between features and that it disappears with a larger dataset. A similar behaviour can be observed for MI in figures 2(a) and 2(c).

Conclusion

To the best of our knowledge, no work in the literature focuses on the bias explicitly associated to the smoothness in a feature selection context. Wookey and Konidaris [START_REF] Wookey | Regularized feature selection in reinforcement learning[END_REF] use smoothness as a prior knowledge during feature selection, but only for data regularization.

This paper shows that an overestimation of the noise variance and an underestimation of the mutual information can occur in small datasets when the function to estimate is not smooth. Experiments have been conducted with both criteria on functions with various smoothnesses and levels of noise, for different sizes of datasets. They confirm the theoretical discussion and show that the biases in the estimations are much more severe when using mutual information than when using the noise variance; this is an argument in favour of using the latter rather than the former.

The experiments also confirm that in a feature selection process, where a decision to select a feature is taken by comparing values of the criteria between different possible features or groups of features, the order of selection may be affected (a smooth feature with a low dependency to the output could be selected before a nonsmooth with a high dependency). This is a serious shortcoming that should be taken into account when designing a feature selection algorithm. For example the noise variance could be explicitly estimated and used to remove the bias, or the selection process could be improved to favour non-smooth features.

Fig. 1 .Fig. 2 .

 12 Fig.1. Experimental data generated with various frequencies and different levels of noise variance.


Sarah Elsharkawy
email: sarah.elsharkawy@itworx.com

Ghada Hassan
email: ghada.hassan@bue.edu.eg

Tarek Nabhan
email: tarek.nabhan@itworx.com

Mohamed Roushdy
email: mroushdy@cis.asu.edu.eg

Studying the Dissemination of the K-core Influence in Twitter Cascades

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The super-spreaders are the users capable of initiating a viral spread of a piece of information, a meme or an idea. Identifying a set of users as super-spreaders is an indication that they can influence a significantly large number of other users in the cascade. However, it does not indicate whether their influence spread is in the depth or breadth of the social network. For instance, a celebrity account or a news agency account that has thousands of followers could be a super-spreader because they influence many their direct followers, hence, the spread is in the cascade breadth. A depth effect, on the other hand, would signify their ability to influence the followers of their followers. In this case, they can diffuse viral content to users outside the list of their direct followers.

Previous research [START_REF] Al-Garadi | Identification of influential spreaders in online social networks using interaction weighted k-core decomposition method[END_REF][START_REF] Zhang | Finding critical users for social network engagement: The collapsed k-core problem[END_REF] has identified the users with largest spreading influence to be the users located in the k-core of the network. The k-core is a maximal subgraph, where all nodes are connected to some number (k) of other nodes in the same subgraph. The k-core decomposition analysis is used to find the k-core of a given graph by iteratively deleting nodes with degree less than k. The degree of a node is the number of edges connected to the node. A k-shell is the subgraph of nodes in the k-core but not in the (k+1)-core. The work done in [START_REF] Kitsak | Identification of influential spreaders in complex networks[END_REF] proved that the most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis. The authors proved their observation by counting the total number of cascaded successors of each node and showing that the number of successors is correlated with the k-value of the k-shell where each user is located. However, their study did not differentiate between the users whose successors span a few k-shells from those whose successors span many k-shells.

In this paper, we propose a measure to estimate how far the influence of the super-spreaders located at the inner-most k-core of the cascade reaches other users located in further k-shells in the cascade. We differentiate between the datasets where the k-core users' influence is confined to the few neighboring k-shells, as opposed to where their influence is disseminating to the shallower k-shells of the cascade. In addition, we investigate whether the presence of spam accounts in the information cascade lessen the overall influence of the k-core users.

The paper is organized as follows: Section 2 gives an overview of research like this work. Section 3 studies the relationship between the k-core size and the graph size on synthetic graphs and discusses the meaning of such relationship in real-life datasets. Section 4 presents the conducted experiments and their results. Finally, Section 5 discusses and concludes this work.

Related Work

The virality of memes, as indicated by a large and/or quick growth in size, has been examined from various perspectives. A meme may become viral because it appeals to many [START_REF] Berger | What makes online content viral[END_REF], but virality of a meme also depends on other factors such as network structure, randomness, adoption patterns of influential users, timing, and many others [START_REF] Pinto | Using early view patterns to predict the popularity of youtube videos[END_REF]. Authors of [START_REF] Elsharkawy | On the reliability of cascade size as a virality measure[END_REF] proposed an approach to judge the reliability of the cascade size in social networks by observing the k-core size. They argued that the size of the cascade, on its own, is a misleading indicator of the growth of popularity.

Other lines of research focused on identifying influential spreaders using different measures. Examples of such measures are the number of retweets, the number of followers, the number of mentions, betweenness centrality, and k-core [START_REF] Dorogovtsev | k-core organization of complex networks[END_REF][START_REF] Kitsak | Identification of influential spreaders in complex networks[END_REF]. Authors in [START_REF] Pei | Searching for superspreaders of information in real-world social media[END_REF] found that the best spreaders are consistently located in the k-core across dissimilar social platforms such as Twitter and Facebook.

In [START_REF] Giatsidis | Evaluating cooperation in communities with the k-core structure[END_REF], the authors evaluated communities based on the k-core concept, as means of evaluating their collaborative nature. In [START_REF] Guille | Information diffusion in online social networks: a survey[END_REF], the authors show that k-cores have an important role in counter-contagions in online social networks. They stated that to start a counter-contagion to an existing contagion, one needs to search for the most influential nodes to start with. k-cores was one of the methods they proposed to identify those influential nodes. Authors of [START_REF] Kitsak | Identification of influential spreaders in complex networks[END_REF] show that the most efficient spreaders are not necessarily the most connected people in the network, but rather are those located within the core of the network as identified by the k-core decomposition analysis.

Relationship Between K-core Size and Graph Size

In this section, we discuss the relationship between the inner k-core size and the graph size and its significance in meme cascades. Consider the following two scenarios for two different dynamic meme cascades: in the first cascade, as the k-core size increases, the graph size enlarges as well. And, as the k-core size gets smaller, the graph size decreases too. This synchronization between the k-core size and the graph size signifies that the core users are consistently spreading their influence to the whole community, and this relationship strengthens the criticality of the kcore users. In the second cascade, the k-core size increases and decreases regardless of the growth or shrinkage of the graph size. In this scenario, there is no noticeable relationship between the k-core size and the graph size, which indicates that the core users are not spreading their influence effectively. Therefore, we conclude that the correlation between the k-core size and the graph size is a projection for the real-life influence of the k-core on the rest of the cascade.

Conditions for the Presence of Correlation

Let G be a simple connected graph and k d be the k value of the inner-most kcore of G; that is, no core exists at k = k d + 1. Let S(G, k) be the k-core size measured as the number of nodes in the k-core of G. The size of the whole graph can be represented by S(G).

According to [START_REF] Shin | Corescope: Graph mining using k-core analysis -patterns, anomalies and algorithms[END_REF], the degrees of the nodes in the inner k-core represent an upper bound for the value k d . Given the degree distribution (DD) of any simple connected graph, there is a percentage (P) of the graph nodes that have a degree larger than or equal to k d , and a percentage (100-P ) of nodes that have a degree less than k d . Based on the k-core decomposition analysis, all the nodes in the k d -core must have a degree larger than or equal to k d , and hence they constitute a portion (P core ) of the (P) nodes. The k d -core size is then calculated as:

S(G, k d ) = P core × P × S(G) (1)
Let the ratio of the k d -core size to the graph size be denoted by r. Based on equation 1, a set of graphs {G 1 , G 2 , ..., Gn} having equal percentages {P 1 = P 2 = ... = P n } and equal {P core1 = P core2 = ... = P coren } would consequently have equal ratios {r 1 = r 2 = ... = r n }. Hence, a direct correlation between the k d -core size and the graph size exists within the given set of graphs.

Correlation on Synthetic Scale-Free Power-Law Degree Graphs

In this section, we focus on exploring the correlation on scale-free power-law synthetic graphs as it is the type of graphs found in social networks [START_REF] Barabasi | Emergence of scaling in random networks[END_REF]. We generated thousands of scale-free synthetic graphs and used power-law curve fitting approaches to estimate the exponent of the power-law DD.

We used the Networkx Python package for graph generation and manipulation. Each synthetic graph is generated as follows:

1. A power-law sequence of degrees is generated (using the power law sequence method.) 2. The graph is constructed based on the generated degrees (using the method configuration model). 3. Any self-loops and parallel-edges that may exist on the graph are removed and the largest connected component is extracted. 4. The DD of the graph is fitted to a power-law model, and the exponent of the fitted model is measured using the approach of [START_REF] Clauset | Power-law distributions in empirical data[END_REF]. Although we have created the graphs based on the power-law sequence of degrees (steps 1 and 2), there is a possibility that the DD of some graphs is not a powerlaw distribution due to applying step 3. A standard approach to check whether a given distribution follows a certain model is to use the goodness-of-fit test, such as the Kolmogorov-Smirnov (KS) [START_REF] Massey | The Kolmogorov-Smirnov test for goodness of fit[END_REF], which generates a p-value that quantifies the plausibility of the hypothesis which, in our case, states that the observed data is drawn from a power-law distribution. The KS-test is applied to the graph relative to its fitted power-law model and the graph is disposed if its p-value is larger than 0.05. We ran the experiments using a variety of exponents and other parameters to ensure the variability of graph structures. We clustered the graphs into groups based on the power-law exponent of their fitted model.

We observed that the graphs having the same power-law exponent, also have the same P and P core . For illustration, Figure 1 plots two synthetic graphs that follow a power-law DD, where their k d values lie on the 78 th percentile of the degree range and the number of the k d -core nodes is approximately 12% of the number of the total graph size.

Table 1 shows the exponents and the k d -core size to graph size ratio of each group. We notice that, within each group, the k d -core size to the graph size ratio varies minimally. This indicates a high positive correlation between the k d -core size and the graph size when the graphs have similar power-law DD.

DD Similarity in Real-life Dynamic Cascades

In the previous section, we discussed the correlation on synthetic graphs. Synthetic graphs are constructed using specific rules and hence, they do not model the infinite patterns that occur in real-life datasets. In a real-life meme cascade, users are affected by one or more sources of influence that guide their adoption behavior towards a meme. To model a dynamic meme cascade, we take snap-shots of the cascade as it evolves over time. We found that the set of graphs representing the snapshots of a single meme cascade share similar structural properties, and their DD varies minimally. The mean and standard deviation of the power-law exponents of the snapshots in our datasets are shown in Table 2.

To measure the K d -core influence dissemination, in terms of k-shells, in a given meme cascade, we propose the following:

1. Taking consecutive snapshots of the meme cascade over periodic time steps. 2. Measuring the correlation between the inner k d -core sizes and the graph sizes of the snapshots. 3. If the correlation is high: we conclude that the users located in the k dcore of the given meme cascade are the most influential spreaders. They constitute the dominating source of influence that guides the propagation of the meme cascade. 4. If the correlation is low: (a) We propose to measure the correlation between the K d -core size and each of the neighboring k-shells as an attempt to define the portion of the cascade that is being influenced by the K d -core. The k-shells exhibiting a high correlation are the ones being influenced by the K d -core.

(b) One of the possible reasons behind the low correlation is the effect of other influential sources on the cascade propagation such as word-of-mouth, media channels, and/or spam. We recommend using a spam detection approach to detect the spam nodes, specifically within the nodes of the kshells that are less correlated with the K d -core due to the existence of a good indication that the nodes in these shells are not behaving like the rest of the graph nodes.

Experiments and Results

In this section, we present the conducted experiments and their results. In section 4.1, we describe our datasets. Sections 4.2 and 4.3 present our findings.

Datasets Description

We collected four real-life Twitter datasets using the free Twitter API. The first is Tsunami dataset of tweets discussing the tsunami disaster of 2011 in Japan. The second is the Royal baby dataset which is the set of tweets discussing the birth of the son of Prince William of the UK. Two more datasets P1, P2 were collected that are tweets regarding two concurrent but competing political campaigns that ran during a constrained period. Table 2 shows the time span, the total number of tweets collected and the count of users in each dataset.

For each dataset, the set of information cascades representing the dynamics of the dataset were constructed. Each cascade represents a snapshot of the dataset information cascade with a 24-hour time span between the cascades. For each cascade (snapshot in time), the node degree was fitted, the exponent determined, and the KS-test used to test the goodness-of-fit between the node degree curve and the power-law curve following the procedure described earlier in Section 3.2. Table 2 shows the mean and the standard deviation of the values of the fitted power-law curve exponents for each dataset.

Correlation on Twitter Datasets

In the first experiment, we measured the correlation between the k d -core size and graph size of each dataset of snapshots. Table 2 shows the Spearman's correlation coefficients (ρ) between k d -core size and graph size of each dataset. All the reported coefficients are statistically significant with a P-value < 0.05. We notice that the correlation is high in Tsunami (0.76) and Royal Baby (0.8) datasets, and it drops in the two political datasets, P1 (0.54) and P2 (0.47).

We conducted another experiment in which we correlate the k d -core size with the size of each k-shell at k < k d, to monitor at which k value the correlation would break. Table 3 shows how the correlation coefficient is high at inner shells and gradually decreases as we move to the outer shells. In Tsunami and Royal Baby datasets the correlation remains relatively high at all shells. However, in P1 and P2 political datasets, the correlation breaks at outermost shells.

The Spam Effect on the Correlation

The decrease of correlation is a direct indication of the disengagement of the growth or shrink of the k d -core size and the graph size. One of the possible reasons of this disengagement is the effect of other influencing sources acting on the cascade. Due to the lack of ground-truth information about the other sources that affected our datasets, we are only able to use heuristic approaches that are found in literature to get an estimation of such an external effect on our cascades. After we have constructed all the cascades of our four datasets, we used Truthy's BotOr-Not API [START_REF] Ratkiewicz | Truthy: mapping the spread of astroturf in microblog streams[END_REF] to check all user accounts in our graphs to determine how likely they are to be spam. We then spotted the location of each of them on the graph and measured the k-shell value at which each of them is located. Results are shown in Figure 2.

The percentage of spam accounts relative to the cascade size is 0.02% in Tsunami, 0.05% in Royal Baby, 0.11% in P1 and 0.1% in P2. Figure 2 shows the amount of spam detected at each k-shell of the four datasets. We observe that no spam is found at inner k-shells while it increases at outer shells. The results match the values found in Table 3 which show how the correlation is significantly high at inner k-shells and decreases at outer shells. From this experiment, we uncovered three main findings: first, the number of spam accounts found in each dataset is inversely proportional to the correlation between the K d -core and the graph sizes of the snapshots of a given dataset. Where Tsunami has ρ = 0.76 and spam ratio of 0.02%, Royal baby has ρ = 0.8 and spam ratio of 0.05%, P1's ρ = 0.54 and spam ratio of 0.11 and finally P2 has ρ = 0.47 and spam ratio of 0.1. Second, the number of spam accounts in each k-shell is inversely proportional to the correlation between the k d -core and k-shell sizes of the dataset as seen in Table 3 and Figure 2. The third is that the number of spam accounts increases at outer k-shells and almost vanishes at the inner K d -core.

Discussion and Conclusion

In this paper, we studied the relationship between the inner k-core size and the graph size and we tackled the question of how far the influence of the most influential spreaders located at the inner k-core reach users located in the outer k-shells.

We presented a novel approach to estimate the influence reach of the users located at the k-core inferred from the observed correlation between the k-core size and the graph size. We demonstrated that a correlation between the inner k-core size and the cascade size exist in sets of synthetic graphs under some constraints, and we identify such constraints.

F i g . 2 .

Box plot representing the probability distribution of the percentage ratio be-tween the spam count in each k-shell to the shell size. The x-axis represents the (k) value of the k-shell, and the y-axis represents the percentage ratio of the number of spam accounts in a given k-shell to the number of nodes in the same k-shell.

We presented results of a case study on four real-life Twitter datasets. The datasets represented snapshots of the meme propagation graph every 24 hours. We found that the correlation between the k-core and the neighboring k-shells decreases gradually towards the outer shells. We also found that in political datasets the correlation drops significantly at outer shells due to external influencing factors such as spam, while in the other two datasets the correlation remained consistent. Using Truthy BotOrNot API, we identified the spam ac-counts in our datasets. We found that the number of spam increases at outer shells and that the number of spam accounts in a shell is inversely proportional to the correlation of the size of that shell to the k-core size.

We conclude that the influence propagation of the super-spreaders located at the k-core of a meme cascade varies significantly from one dataset to an-other. In the datasets which exhibit other sources of influence such as spam accounts, the superspreaders are notably unable to disseminate their influence to the shallower k-shells of the cascade. These datasets are signified by the low correlation between the inner k-core size and the graph size of snapshots captured over periodic time steps of the lifetime of the cascade. For those datasets, having low correlation, marketers need to pay more attention to other types of super-spreaders such as those having high betweenness centrality. Identifying the ideal super-spreaders that should be targeted in this case is still an area of investigation.

Another important conclusion is that the datasets that have a low correlation between its inner k-core size and graph size usually unveil a large number of spam accounts. Hence, the proposed correlation measure could be used for an early warning for spam. Moreover, we observed that the outer k-shells have a higher tendency for the presence of spam. This phenomenon could be used to speed up the spam detection algorithms by searching in the outer k-shells first.

Fig. 1 .

 1 Fig. 1. Histograms representing the degree distributions of two synthetic graphs that follow a power-law DD. The vertical thin grey line is the kd value. The black bars represent the number of graph nodes and the grey bars represent the number of kd -core nodes.

Table 1 .

 1 Synthetic graphs grouped based on power-law exponent of node DD.

	Exponent	k d -core size to graph size percent
	2.16 ± 0.023	(1.79 ± 0.66) %
	2.35 ± 0.037	(1.45 ± 0.64) %
	2.65 ± 0.073	(1.5 ± 1.12) %
	2.82 ± 0.051	(2.37 ± 3.26) %
	3.01 ± 0.051	(11.53 ± 13.58) %
	3.2 ± 0.058	(20.88 ± 7.23) %
	3.4 ± 0.058	(17.04 ± 3.95) %

Table 2 .

 2 Datasets Description

	Dataset Name	Tsunami Royal Baby	P1	P2
	Time span	10/3/2011 -10/4/2011	22/6/2013 -22/7/2013	1/6/2013 -1/7/2013	1/6/2013 -1/7/2013
	Tweets Count	770,083	137,036	110,782	13,446
	Users Count	415,642	130,788	42,760	7,821
	Power-law	Mean	3.06	4.63	3.03	3.69
	exponent	St. dev.	0.89	0.78	0.68	1.01
	Spearman's rho for kd -core to cascade size	0.767076	0.80355	0.54163	0.47127

Table 3 .

 3 Spearman's correlation coefficients between kd -core size and each outer k-shell size measured on all snapshots of each dataset.

	(k) of	Tsunami	Royal Baby	P1	P2
	Shell	Shell to 13-core	Shell to 29-core	Shell to 29-core	Shell to 28-core
	1-shell	0.654	0.783	0.538	0.550
	2-shell	0.750	0.789	0.545	0.532
	3-shell	0.751	0.702	0.555	0.537
	4-shell	0.721	0.782	0.571	0.656
	5-shell	0.762	0.784	0.592	0.701
	6-shell	0.815	0.784	0.655	0.849
	7-shell	0.822	0.785	0.671	0.859