Bahjat Safadi
email: bahjat.safadi@imag.fr

Georges Quénot
email: georges.quenot@imag.fr

A Factorized Model for Multiple SVM and Multi-Label Classification for Large Scale Multimedia Indexing

Keywords: Multimedia indexing and retrieval, support vector machine, multi-learner approach, class imbalance

This paper presents a set of improvements for SVMbased large scale multimedia indexing. The proposed method is particularly suited for the detection of many target concepts at once and for highly imbalanced classes (very infrequent concepts). The method is based on the use of multiple SVMs (MSVM) for dealing with the class imbalance and on some adaptations of this approach in order to allow for an efficient implementation using optimized linear algebra routines. The implementation also involves hashed structures allowing the factorization of computations between the multiple SVMs and the multiple target concepts, and is denoted as Factorized-MSVM. Experiments were conducted on a large-scale dataset, namely TRECVid 2012 semantic indexing task. Results show that the Factorized-MSVM performs as well as the original MSVM, but it is significantly much faster. Speed-ups by factors of several hundreds were obtained for the simultaneous classification of 346 concepts, when compared to the original MSVM implementation using the popular libSVM implementation.

I. INTRODUCTION

The aim of multimedia indexing is to automatically detect visual concepts in massive, continuously growing image/ video collections. In general, the indexing is achieved by supervised learning approaches for each target concept (binary classification). In which, a classifier is trained on positive and negative samples of the target concept to generate a classification model. This model is then used to predict the likeliness of new samples to contain the learnt concept. Support Vector Machine (SVM) classifiers with RBF kernels [START_REF] Cortes | Support-vector networks[END_REF], [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF] are very popular and efficient for supervised classification, specially, in the case where the learned classes are not linearly separable. But they are not very well suited for highly imbalanced datasets. They process multiple concepts independently for training and for predicting. Ensemble learning extensions like multi-SVM approach (MSVM) [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF] efficiently handles the class-imbalance problem that usually appears when indexing large-scale multimedia datasets. The main idea of MSVM is to split the training set into m balanced subsets and train a SVM classifier on each subset, thus generates m different models. For each sample in the test set, these models are used to predict its likelihood to contain the target concept separately, and a fusion function is applied on the m predicted scores to generate its final score. However, a drawback limitations of MSVM are crucial as they need huge processing times, especially at the prediction phase. In this paper, we propose some improvements to the MSVM approach, which makes it faster mainly at the prediction phase and usable almost in a real time.

The availability of specific and highly optimized mathematical packages like the Netlib BLAS (Basic Linear Algebra Subprograms [START_REF] Lawson | Basic linear algebra subprograms for fortran usage[END_REF]) or the Intel VML (Vector Math Library) and/or of specialized parallel architectures like GPU (Graphical Processing Units) boards can bring huge improvements in computing speed and partly solve the related scalability issues. Such speed-up is generally obtained at the price of a more complex implementation and often requires a significant redesign effort. Considering their specificities (e.g. some are more sequential or iterative), not all methods can easily take advantage of these possibilities.

The proposed work is in the context of methods based on small to intermediate size descriptors combined with classifiers using non-linear kernels. It is also more interesting in the case in which several concepts are annotated for each training sample; the annotation does not have to be dense however. This work also addresses the imbalanced data problem and is designed for taking advantage of optimized mathematical libraries (BLAS and VML). Though not tested yet, it should work well too with GPU implementations of such libraries.

We propose the following improvements to the original MSVM approach in the context of multiple concept classification:

• speed-up of the SVM prediction function using matrix multiplication; • fusing of SVM models corresponding to a single target concept and to different splits into a single model, with a probability normalization (Platt [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF]) extension; • multi-label indexing, based on fusing of SVM models corresponding to different target concepts into a single and global model. All these improvements permit an efficient use of BLAS1/2/3 and VML at many levels yielding a very significant speed-up.

The remainder of this paper is organized as follows: section II discusses related work; section III presents the proposed methods for improving the MSVM implementation; section IV presents experimental evaluation of the proposed contributions; and section V draws some conclusions and discusses perspectives.

II. RELATED WORK

A. Optimizing the prediction of SVM

In the last decade, the optimization methods for SVM training has been intensively studied, including kernel approximation approaches [START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF], [START_REF] Le | Fastfood?approximating kernel expansions in loglinear time[END_REF], greedy basis selection [START_REF] Keerthi | Building support vector machines with reduced classifier complexity[END_REF], and online SVM solvers [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF]. Recently, Jose et al. [START_REF] Jose | Local deep kernel learning for efficient non-linear svm prediction[END_REF] proposed an approximate solver to reduce the prediction time of SVM, by reformulating the problem or by using derivatives of the SVM. However, in this paper we focus on reducing the prediction time of the SVM approaches based on RBF-kernel. We propose an algorithm for speeding up the SVM prediction function and apply it with the MSVM approach, as it is mostly used as a solution for indexing imbalanced datasets [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF].

B. Class-imbalance problem

The most widely used approaches for handling the classimbalance problem are the re-sampling methods, which are used for balancing the datasets before SVM training. Resampling methods have been successfully applied for training SVMs with class-imbalanced datasets in different domains [START_REF] Yuan | Learning concepts from large scale imbalanced data sets using support cluster machines[END_REF], [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF], [START_REF] Liu | Exploratory undersampling for classimbalance learning[END_REF], [START_REF] Tahir | A multiple expert approach to the class imbalance problem using inverse random under sampling[END_REF], [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF].

The alternative approach presented in [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF], which mainly works by selecting randomly a subset from the negative (i.e. majority) samples with a size comparable to that of all positive (i.e. minority) ones, then train a classifier on this subset. Support cluster machines (SCMs) method [START_REF] Yuan | Learning concepts from large scale imbalanced data sets using support cluster machines[END_REF] can be viewed as another focused re-sampling method for SVMs. This method first partitions the negative examples into disjoint clusters by using the kernel-k-means clustering method. Then it trains an initial SVM model using the positive examples and the representatives of the negative clusters (i.e. the data examples representing the cluster centers). These approaches may lead to loss of information, especially when the dataset is of large-scale and the learnt concepts are sparse, since many informative majority class samples may be ignored. Thus, it is possible to balance this loss by making several selections on the majority class set, and merging the outputs of different classifiers built from these subsets.

Ensemble learning has also been applied as a solution for training classifiers with imbalanced datasets [START_REF] Liu | Exploratory undersampling for classimbalance learning[END_REF], [START_REF] Tahir | A multiple expert approach to the class imbalance problem using inverse random under sampling[END_REF], [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF]. Among the state-of-the-art methods in this scenario, we are interested in the multi-learner approach based on SVM (denoted as MSVM) presented in [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF]. The authors have showed the ability of MSVM to increase the classification performance of the video indexing system. They gave a full evaluation and comparison of their approach versus several single-and multi-learner approaches (e.g. logistic regression and SVM) for the concept indexing task in video documents. They have compared their method with different approaches, such as [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF], [START_REF] Tahir | A multiple expert approach to the class imbalance problem using inverse random under sampling[END_REF], and concluded that multi-learner approach based on SVM is designed to address best the problem of sparse concepts in large-scale multimedia datasets.

Most of the reviewed multi-learner approaches are based on fusing the classification scores; this needs a prediction step of all test samples with each learnt model. In large-scale data sets, this is crucial since the prediction time of the all samples may be larger than the time for learning the models themselves.

In this paper, we propose an efficient multi-learner approach based on a factorization of SVM models.

III. THE PROPOSED METHOD

A. Accelerating the SVM prediction function

When using SVM for multimedia indexing with largescale data sets, the prediction step is computationally the most expensive step. In this section, an implementation of SVM prediction for n test samples (Z = (z j ) (1≤j≤n) ) against a SVM model with m SVs (X = (x i ) (1≤i≤m) ) is proposed. Let the test set length to be n × d, and the SVM-model length for a learnt concept to be m × d, where d is the size of the used descriptor. The prediction function requires the computation of the full (m × n) distance matrix between all descriptors and SVs. Then, a merging function is applied on the m distances of each sample to assign a prediction score or a probability for the sample to contain the learnt concept. The computation of the distance matrix is the most expensive computational step in the SVM prediction function.

Basically, the square Euclidean distance, between two vectors used in the RBF kernel, is computed as follows:

xi -zj 2 = k=d k=1 (x ik -z jk ) 2 .
This can be rewritten as:

xi -zj 2 = k=d k=1 x 2 ik + k=d k=1 z 2 jk -2 k=d k=1 x ik z jk (1)
The advantage of this form of the Euclidean distance is that it decomposes the computation of a distance matrix between sets of vectors into smaller steps which are faster to compute. The first two sums have to be computed respectively m and n times only for the m × n distances and this can be done efficiently by calling the BLAS1 scalar product routine. The second sum has to be computed m×n but all the values can be computed at once and very efficiently using the BLAS3 matrixmatrix multiplication routine. These are simply the elements of the X.Z T matrix. Once the set of distances are computed and multiplied by the γ value (i.e. the free parameter of the Gaussian radial basis function), the kernel K(x i , z j ) values can be obtained as a K ij matrix by applying a vectorized exponentiation operator (such as the one available in the Intel VML library) on its m × n elements.

The computation of the set of scalar products x i .z j , using matrix multiplication, can also be used when computing linear and polynomial kernels. The computation of the first two sums is not necessary in this case, and vectorized operators can still be used for the final kernel computations in the polynomial case. Unfortunately, the RBF kernel with χ 2 or L 1 distances still cannot benefit from the matrix multiplication trick. However, the work presented in [START_REF] Safadi | Descriptor Optimization for Multimedia Indexing and Retrieval[END_REF] concluded that applying a power transformation on low-level descriptors makes the Euclidean distance as effective as or even better than χ 2 and L 1 .

Once the matrix of K(x i , z j ) values are computed, the decision function values for the set of vectors can be obtained, by multiplying the transposed K ij matrix by the vector a (y i α i ) of the m values (y i , α i are the target and the contribution of the i th training example to the model, respectively), which can be efficiently done using the BLAS2 vector-matrix multiplication, and adding the bias term ρ:

(f (z j )) (1≤j≤n) = f = ρ.1 n + K T .a (2)
with 1 n being a vector of n elements all equal to 1.

Finally, if probability normalization is required, the application of the sigmoid function (on the set of z j vectors) can also be accelerated using vector operators. Though all the mentioned linear algebra and vector operation optimizations lead to some performance improvement, the most important and significant one is, by far, the use of matrix multiplication (BLAS3) to accelerate kernel computations. It is particularly efficient when the dimensions of the considered matrices are large (number of components in the descriptor, number of support vectors and number of test samples). For maximum efficiency, a minimum number of test vectors must be processed at one. If the number of test vectors is very large, these can be processed by blocks of this minimum size. In practice, blocks of 1K test vectors are large enough to optimally benefit of BLAS3 speed-up. Beyond this, the computation is not significantly faster but it requires significantly more memory. In the case in which test vectors have to be processed one by one (this may happen during the training phase or if prediction is needed for a single test sample), BLAS2 matrix-vector operations can be used instead of BLAS3 matrix-matrix ones, leading to a less substantial but still significant speed-up.

Though the structure of the SVM training algorithm does not permit a simple use of the matrix multiplication trick directly within it as for the SVM prediction, optimizing the prediction function can lead to some acceleration of the training phase as well since, during it, the SVM algorithms apply the prediction function for learning the weights of the SVs (i.e. the α vector), as well as for tuning the Platt's parameters by cross-validation.

B. The factorized MSVM Model (FMSVM)

Multiple-SVM [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF] approach handles the class imbalance by building a number of balanced elementary classifiers, and by fusing their predictions. The elementary classifiers do not actually need to be perfectly balanced. SVM classifiers do tolerate a moderate amount of imbalance, and a compromise can be found between the number of elementary classifiers and the amount of imbalance left to them.

In the original MSVM approach, the authors fuse the scores after their normalization as probabilities using a sigmoid function (Platt's method). They consider five possible fusion functions of the score of the elementary classifiers: the minimum, the harmonic mean, the geometric mean, the arithmetic mean and the maximum. We found out that all of them were roughly equivalent, except the maximum one that performed significantly less well (see the experiments section).

The MSVM considers score fusion after probability normalization for practical reasons (these were directly given by the libsvm tool [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] for each elementary classifier, but they could have considered as well as the fusion of scores directly produced by the initial decision functions and then perform a probability normalization. This would have been more complicated, however, since the computation of the global B and A coefficients (i.e. the symmetry point and the slope at this point in a sigmoid function respectively) by crossvalidation would have require to manage cross-validation subproblems' splits jointly with the multiple classifiers' splits. We propose here a simple method for computing global A and B sigmoid coefficients directly from the A k and B k sigmoid coefficients computed separately for the elementary classifiers by cross-validation.

There is no a priori reason for the score fusion within the MSVM approach is better before and after sigmoid normalization and experiments show that the overall performance is also equivalent. This is probably due to the fact that the SVM approach gives similar distributions to all elementary classifiers. Less choice is given for the fusion function since harmonic and geometric means are not suited for values that can be negative. The minimum and maximum values could also be used but would be less natural. Finally, only the arithmetic mean seems meaningful in this case. It is also the only one that can lead to a simplification of the computation of the global decision function.

Sigmoid normalization applied after score fusion has no effect on the ranking of the test samples since the sigmoid function is always increasing. It does have effect however in the case of further processing, for instance if the obtained global scores have to be fused again, considering results coming from different descriptors or from other learning methods also normalized as probabilities. We again found out that the method that we propose for the fusion of sigmoid parameters performed as well as the original one in the case of further descriptor and classifier fusion.

The fusion method that we propose is defined as follows. The elementary classifier decision functions are defined as:

f k (z) = ρ k + xi∈S k y i α ki K(x i , z) (3)
and the associated probability functions are defined as:

p k (z) = 1 1 + e A k .f k (z)+B k (4)
where k ∈ [1, l] is the elementary classifier index and S k the set of support vectors associated to the k th elementary classifier. Without loss of generality, we can consider the global set of support vectors (S = l k=1 S k ) and rewrite equations 3 as:

f k (z) = ρ k + xi∈S y i α ki K(x i , z) (5)
taking all α ki for x i in S \ S k equal to zero (this requires a global re-numbering of the support vectors). The arithmetic mean of the elementary decision functions can then be rewritten as:

f (z) = ρ + xi∈S y i α i K(x i , z) (6)
with ρ and the α i being respectively the arithmetic mean of the ρ k and of the α ki for k ∈ [1, l]. This leads to a decision function, which is exactly of the same type as the one computed using a single and larger SVM. Though of the same type, the MSVM fused function is different and though it does not benefit from a global convex optimization, it performs better in the case of highly imbalanced classes.

Considering the probability normalization, if needed, the elementary sigmoid functions can also be fused into a global one. The elementary sigmoid functions are defined by two parameters that can be taken as the abscissa of their symmetry point which is equal to B k /A k and the slope at this point which is equal to A k . We simply propose to take the average of the abscissa of the symmetry points and of the slope at these points for the global sigmoid function. As the data are normalized before (by the SVM implementation) and after (by Platt's method), the elementary sigmoid are already quite "close" in general and fusing them is not only correct but is also likely to reduce the noise in their estimation. Finally, the global probability function is defined as:

p(z) = 1 1 + e A.f (z)+B (7)
with A and B defined so that A and B/A are respectively the arithmetic mean of the A k and of the

B k /A k for k ∈ [1, l].
Once again, this leads to a formulation which is exactly of the same type as the one computed using a single and larger SVM.

Many computations are factorized in this approach. This is why we call this method factorized MSVM (FMSVM). The overall form is well suited for an efficient computation using BLAS routines. In particular, K(x i , z) is computed only once for all the x i elements of the global set of support vectors while these may appear several times in the sets of support vectors of the different elementary classifiers. The factorization of the elementary classifiers is implemented via an accumulation in a hashed structure of the S k , ρ k , α ki , A k and B k /A k elements.

C. Factorized Model for Multi-Label Classification

The algorithm presented in the previous section can be extended for computing prediction values for a set of q predefined and learnt concepts. With slight modifications, the method used for factorizing computations for multiple elementary learners can also be applied for factorizing computations for multiple target concepts.

The multi-label classification method that we propose is defined as follows. The per concept classifier decision functions are learnt separately for each concept c, and defined as:

f c (z) = ρ c + xi∈Sc y ci α ci K(x i , z) (8)
where c ∈ [1, q] is the concept index and S c the set of support vectors associated to the classifier trained for the c th concept.

For each concept, the f c (z) values can come, either directly from a classical SVM or from a FMSVM as presented in the previous section. The main difference with equation 3 is that a c index has to be added to the y labels but this has no practical implication in the computations. The associated probability functions are defined as:

p c (z) = 1 1 + e Ac.fc(z)+Bc (9)
Again, without loss of generality, we can consider the global set of support vectors: (S = q c=1 S c ) and rewrite equations 3 as:

f c (z) = ρ c + xi∈S y ci α ci K(x i , z) (10)
taking all α ci for x i in S \ S c equal to zero. So far, the method is the same as for the MSVM fusion but we do not perform any fusion operation here. Instead we keep all the per concept results in parallel and we rewrite equation 2 in a vectorized form considering the set of concepts as:

(f c (z j )) (1≤j≤n)(1≤c≤q) = f = ρ T .1 n + K T .a ( 11
)
where ρ is the bias vector ρ c of the q terms and a is the q × m matrix of the y ci α ci values. The BLAS3 matrix multiplication routine can be used once again for an efficient computation of the set of f c (z j ) values.

Considering the probability normalization, if needed, no fusion has to be performed and the sigmoid computation has to be done for each f c (z j ) value. These can be efficiently computed however using VML functions.

As in the MSVM fusion, many computations are factorized in this approach and the overall form is well suited for an efficient computation using BLAS routines. Once again, the implementation involves a hashed structure. The main difference is that the accumulation of values is replaced by a vectorization of them. We also refer to this method as factorized MSVM (FMSVM). The F in FMSVM may refer either to the factorization of multiple elementary classifiers for a single concept or to the factorization of multiple classifiers corresponding to multiple concepts or to the combination of both.

The proposed optimization requires that the γ parameter is the same for all concepts while it could in principle be tuned by cross-validation separately for each one. This is not a problem since the classification performance is not very sensitive to the exact value of this parameter and the optimal value is more related to the descriptor type and collection contents than to the target concepts. Furthermore, the estimation of this parameter can be noisy in the case of highly imbalanced classes and taking a single value for all concepts is a good way to reduce such noise. In the case one would want to use a separate γ c parameter for each concept, the proposed method could still bring significant improvement: the factorization of the Euclidean distance computations could still be used while the second factorization corresponding to equation 11 could not. The first one is however the most important for speeding up the prediction, especially when applied with high dimensionality descriptors.

Practical implementation may face a problem of memory space, especially when indexing a large number of concepts (e.g. when indexing thousands of concepts). However, this problem can be solved by processing the data by blocks over the test examples and the concepts to index.

IV. EXPERIMENTS

Experiments were conducted in the context of the TREC-Vid 2012 semantic indexing task [START_REF] Over | Trecvid 2012 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF]. The data collection [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF], which compares between different classifiers and shows the effectiveness of the MSVM approach to handle the class-imbalance problem in large-scale multimedia datasets.

A. Video description

We have used several descriptors of different types and sizes, which have been produced and shared by various partners of the IRIM project of GDR-ISIS [START_REF] Ballas | IRIM at TRECVID 2013: Semantic Indexing and Instance Search[END_REF]. Most of the selected descriptors are based on the color histograms or on the bag of words approaches. In practice, we have used eight descriptors whose size and performance are given in table I. The performance is evaluated using the inferred Mean Average Precision on the 346 evaluated concepts.

All the used descriptors were optimized by applying a power law normalization and a dimensionality reduction using the principle component analysis (PCA) followed by a second power law normalization. The use of this optimization is motivated, as it makes the Euclidean distance outperform the χ 2 distance with RBF kernels [START_REF] Safadi | Descriptor Optimization for Multimedia Indexing and Retrieval[END_REF]. The optimization of the hyper-parameter, the α exponents for the power laws and the k values for PCA, were tuned by cross-validation separately for each descriptor.

B. Effectiveness of the Factorized MSVM

In this section, we compare the performance of the indexing system using the original MSVM and the new proposed method (Factorized-MSVM). Both methods were applied with the Euclidean distance and the RBF-kernel. The performances of the systems were measured as the MAP value over the 346 concepts of TRECVid 2012, calculated on the validation set. Table I shows the system performance with the MSVM and Factorized-MSVM with the eight descriptors considered in this work. As the table shows, for each descriptor, the MAP values are not significantly different between both methods. We believe that the small difference comes from the floating point rounding (single precision was used) when fusing the scores in the original approach. Final scores for the test samples using the MSVM were produced by applying the arithmetic mean 1 http://www.quaero.org/ as a fusion function on the m predicted scores while in the Factorized-MSVM, the scores were computed only once. This is a very interesting result. It validates that the proposed Factorized-MSVM method performs as well as or very close to the original MSVM. Thus, factorizing the models leads to similar results than fusing predicted scores.

C. The efficiency of Factorized-MSVM

All the experiments were done on a machine which has two quad-core processors running at 2.66 GHz and 32 Gbytes of Ram. The execution time depends upon the descriptor size. In table II, we report and compare the training and prediction times of the original MSVM approach (based on libsvm prediction) and of the proposed Factorized-MSVM approach. The table shows the processing times in hours for the semantic indexing task of 346 concepts on the validation set using the considered descriptors. Furthermore, it presents the processing times of the multi-class prediction function of the 346 concepts with each of the considered descriptors. A very significant improvement in efficiency of the proposed prediction method has been observed. With the original MSVM, the training times for all the concepts are smaller than the prediction times, with each descriptor. The training times range from 13 hours to 101 hours, while the predicting times it go from 42 hours up to 390 hours. This depends upon the descriptor size and upon the number of SVs found for each concept. However, the learning process using the Factorized-MSVM (which applies the new prediction algorithm), are between 5.3 to 27.3 hours, which are almost 3 times faster than the original MSVM. The improvement of the training process are due to the prediction that the libsvm does while training, since the training algorithm applies a cross-validation method (prediction included) while training. Furthermore, the prediction times are less than learning times and much faster than the prediction times with the original MSVM, between 1.5 and 3.2 hours. Finally, using the multi-class prediction (applied once for the 346 concepts), the prediction time decreases to only a few minutes, which is almost negligible when compared to the original prediction times and also to the descriptors' computation time.

The prediction times are also reduced to a single SVM. For instance, in the case of indexing the data set for a concept Person, the data is almost balanced. Thus, the system required only one learner according to the MSVM approach. It has been observed that FMSVM significantly reduced the processing times with all descriptors. The learning time was reduced about 3 to 5 times, depending on the descriptor type. The prediction times was reduced about 32 to 245 times, and became less than two minutes for each descriptor.

D. Performance on the TRECVid 2012 test set

The same experiments were conducted on the full collection of TRECVid 2012, in which we used the full development set for training set and made predictions on all the samples of the test set. These data sets are more challenging; they are larger, and thus they need more processing time. The improvement in efficiency of the proposed method is shown in table III. The reported results validate the efficiency of the proposed method when indexing large-scale collections, such as TRECVid 2012. We have proposed and evaluated a new algorithm for content-based multimedia indexing on large-scale dataset. The algorithm is an extension to the multi-learner based on SVM approach and is denoted as Factorized-MSVM. The approach is designed for taking advantage of optimized mathematical libraries (BLAS and VML). Moreover, the approach involves hashed structures allowing the factorization of computations between the multiple SVMs and the multiple target concepts. The method has been validated and evaluated using several descriptors in the context of the TRECVid 2012 semantic indexing task. Experimental results show that the Factorized-MSVM performs as well as the original MSVM, but it is much faster. It is about 39 -145 times faster than the prediction made using the original libsvm separately for each concept. By applying the multi-class prediction method, the prediction times over all the concepts reduces to a few minutes instead of several hours with the original MSVM. The learning time was accelerated as well. Furthermore, the method was validated in the single-learner case.

A released software package of our proposed Factorized-MSVM implementation can be found on 'http://mrim.imag.fr/FMSVM'. In future work, we plan to compare the Factorized-MSVM with the methods based on fisher-vector with linear classifier [START_REF] Perronnin | Towards Good Practice in Large-Scale Learning for Image Classification[END_REF] and the Deep Convolutional Neural Networks approaches [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], [START_REF] Farabet | Learning hierarchical features for scene labeling[END_REF].

TABLE I .

 I THE MAP VALUES ON THE TRECVID 2012 VALIDATION SET, USING THE DIFFERENT MSVM METHODS. large sets: the development and the test sets. The development set contains 400, 289 annotated video shots, while the test set contains 145, 634 shots. The evaluations were conducted on 346 concepts, which were provided by NIST and Quaero 1 . We have divided the development set into two parts: the training set (train, 197, 185 video shots) and the validation set (val, 203, 104 video shots). In this paper, we evaluate and compare the proposed factorized model and the original MSVM approach. For comparison with other classifiers, we refer to the work presented

	Descriptor	Size	PCA	Original	Factorized
				MSVM	MSVM
	hg	104	104	0.1155	0.1153
	bov2 dsiftSC	8192	512	0.1701	0.1699
	labm1x3x1024	3072	384	0.1328	0.1327
	vlat hog6s8 dict64	4096	512	0.1637	0.1603
	dense sift k1024	1024	256	0.1290	0.1289
	vlad	32768	640	0.1720	0.1717
	mlhmslbp spyr	26624	768	0.1461	0.1466
	superpixel color sift	1064	256	0.1413	0.1409
	consists of two

TABLE II .

 II PROCESSING TIMES (IN HOURS FOR THE 346 CONCEPTS), ON THE val SET OF TRECVID 2012. G INDICATES THE SPEEDUP RATES OF FMSVM OVER MSVM.

		MSVM	FMSVM	multi-class
	Descriptor	train	predict	train (Gt)	predict (Gp)	predict (Gm)
	hg	13.3	42.1	05.3 (2.5)	1.6 (26)	0.10 (421)
	bov2 dsift*	53.7	255.1	17.0 (3)	2.9 (88)	0.17 (1500)
	labm*	76.1	274.1	26.0 (3.0)	1.9 (141)	0.16 (1713)
	vlat hog*	55.9	232.3	18.3 (3)	3.1 (75)	0.16 (1451)
	dense sift*	20.1	96.5	07.9 (2.5)	1.7 (54)	0.18 (536)
	vlad	39.8	222.5	22.0 (1.8)	2.3 (99)	0.12 (1854)
	mlhmslbp*	101.0	390.7	27.3 (3.7)	3.2 (124)	0.15 (2604)
	superpixel*	31.4	95.5	11.4 (3)	1.5 (64)	0.11 (868)

TABLE III .

 III PROCESSING TIMES (IN HOURS FOR THE 346 CONCEPTS) ON THE TEST SET OF TRECVID 2012. G INDICATES THE SPEEDUP RATES OF FMSVM OVER MSVM.

		MSVM	FMSVM	multi-class
	Descriptor	train	predict	train (Gt)	predict (Gp)	predict (Gm)
	hg	48.4	58.1	21.2 (2.3)	1.5 (39)	0.13 (445)
	bov2*	195.4	289.8	67.6 (2.9)	2.5 (116)	0.17(1705)
	labm*	274.0	395.5	90.5 (3.0)	3.3 (122)	0.25 (1643)
	vlat*	311.7	364.1	73.0 (4.7)	3.3 (109)	0.24 (1518)
	dense sift*	87.5	145.6	30.3 (2.9)	1.5 (94)	0.14 (1051)
	vlad	173.7	231.0	77.5 (2.2)	3.6 (64)	0.28 (805)
	mlhmslbp*	388.2	569.7	122.0 (3.2)	3.9 (145)	0.18 (3074)
	superpixel*	119.3	134.3	42.3 (2.8)	2.0 (67)	0.15 (861)
		V. CONCLUSION AND FUTURE WORK

ACKNOWLEDGEMENTS

This work was partly realized as part of the Quaero Program funded by OSEO, French State agency for innovation.


Abdelkader Hamadi

Philippe Mulhem

Georges Qu Énot
email: georges.quenot@imag.fr

Philippe Hamadi

Mulhem

Temporal re-scoring vs. temporal descriptors for semantic indexing of videos

may come

Temporal re-scoring vs. temporal descriptors for semantic indexing of videos

Abdelkader Hamadi, Philippe Mulhem, Georges Quénot

I. INTRODUCTION

The context helps to understand the meaning of a word and helps to disambiguate polysemous terms. Much research has exploited the advantage of this notion especially in information retrieval domain. Overall, it is recognized that the use of context enables the design of images analysis and understanding algorithms that are less complex and more robust [START_REF] Brézillon | Context in problem solving: A survey[END_REF]. For images and videos indexing and retrieval by visual concepts detection, this idea seems a priori valid. On the other hand, it is not always easy to have effective learners whatever the classes or concepts to deal with. Classic methods of semantic indexing of images and videos are not very effective because they manipulate multimedia samples and concepts separately and ignore contexts in which they appear. Some researchers tried to deal with this problematic. Indeed, several categories of context were considered: semantic [START_REF] Naphade | Factor graph framework for semantic video indexing[END_REF], [START_REF] Rabinovich | Objects in context[END_REF], [START_REF] Qiu | Improving news video annotation with semantic context[END_REF], spatial [START_REF] Yuan | Exploiting spatial context constraints for automatic image region annotation[END_REF], scale [START_REF] Torralba | Contextual priming for object detection[END_REF], temporal [START_REF] Weng | Multi-cue fusion for semantic video indexing[END_REF], [START_REF] Safadi | Re-ranking for Multimedia Indexing and Retrieval[END_REF], [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF], [START_REF] Hamadi | Two-layers re-ranking approach based on contextual information for visual concepts detection in videos[END_REF], [START_REF] Qi | Correlative multilabel video annotation with temporal kernels[END_REF], [START_REF] Siersdorfer | Automatic video tagging using content redundancy[END_REF], [START_REF] Li | Sequence multi-labeling: A unified video annotation scheme with spatial and temporal context[END_REF]. Videos have a characteristic that differentiates them from still images: the temporal aspect. Ignoring this feature leads to a loss of relevant information. In fact, the order of shots in a video gives a precise meaning to its content. So, the temporal structure of videos may be useful to bridge the semantic gap. On the other hand, to understand the content of a video, even a human needs to analyze information contained in some successive shots. This is due to the fact that the successive shots of a video are temporally, visually or semantically linked. Based on this idea, we assume that the presence of a concept in a given shot will increase the likelihood of its presence in certain shots that surround the concerned shot, especially the concepts that appear for a long period, as it is the case of events that usually last long. For example, if the concept "ski" appears in a video shot, its apparition is extended into several successive shots. In this same context, we will see the white color representing the "snow" throughout these successive shots. This proves that there is a dependency between the visual and/or the semantic contents of successive fragments of videos. Several researchers have attempted to use the temporal dimension for semantic video indexing and/or retrieval. However, the temporal information can be derived from different sources and exploited in different possible levels of an indexing system. We can cite: 1) before learning step, 2) in the learning process, and 3) in a post-processing step of the learning stage. In this paper, we compare two methods that concern the cases 1 and 3 for semantic indexing of videos.

II. RELATED WORKS

The easiest way to use the temporal context is to consider it in a re-scoring step by post-processing the classification results. Safadi et al. [START_REF] Safadi | Re-ranking for Multimedia Indexing and Retrieval[END_REF], [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF] used the notion of the temporal context for semantic indexing of videos by exploiting concepts detection scores in the neighboring shots. They achieved a very significant improvement of the baseline system. This good result can be explained by content dependency between successive shots that are locally homogeneous. We will detail this approach in section II-A. Temporal context can also be considered using temporal kernels. Qi et al. [START_REF] Qi | Correlative multilabel video annotation with temporal kernels[END_REF] propose a temporal kernel function. The problem with such methods is that they are not easy to implement and they usually require a long computation time and big data collections. Siersdorfer et al. [START_REF] Siersdorfer | Automatic video tagging using content redundancy[END_REF] propose a video annotation approach based on context redundancy. Their idea assumes that most a video v i labeled t i includes a sequence of a video v j labeled t j , the likelihood that v i will be labeled t j increases. For videos annotation, Yuanning et al. [START_REF] Li | Sequence multi-labeling: A unified video annotation scheme with spatial and temporal context[END_REF] propose to consider the spatial and temporal contexts using a kernel function that takes into account the temporal correlation and the spatial correlation between concepts. For example, we may find a rule of the type: when a concept c i is present in three successive shots, the concepts c j and c k co-occur in the last two successive shots. Experiments on TRECVid'05 and TRECVid'07 collections showed interesting results. Weng et al. [START_REF] Weng | Multi-cue fusion for semantic video indexing[END_REF] propose to integrate the semantic context (inter-concepts correlation) and the temporal context (the dependency between shots of a same video) for visual concept detection in videos. To create the contextual relationships between concepts, an algorithm similar to decision trees has been introduced. It is based on inter-concepts correlation calculated using the "chi-square" test on datasets updated progressively by subdividing the original collection. The temporal relationships are detected in the same manner as inter-concept relationships. So, a chronological route, in both directions (forward and backward) is performed. The operation continues until no shot with a significant correlation is found. In [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF], the authors exploit the idea presented in [START_REF] Safadi | Re-ranking for Multimedia Indexing and Retrieval[END_REF], [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF] and propose another approach that consists of generating a descriptor by performing an early fusion of high-level descriptors of shots belonging to a temporal window centered on the current shot. They achieved very interesting results and enhanced a good baseline system.

A. Temporal re-scoring (TRS)

We propose to use the idea of Safadi et al. [START_REF] Safadi | Re-ranking for Multimedia Indexing and Retrieval[END_REF], [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF] by extending the target concept detection to the neighboring shots belonging to a window of size 2 × w + 1 shots instead of a single shot (w shots before the current shot and w shots after it). The new detection score of a concept c i in the j th shot e j of a video v is given by the following formula:

F trs (e j , c i ) = 1 N × (F init (e j , c i ) + w k=-w,k =0 F init (e k , c i )) (1)
where: e k is the k th shot of the video v. N is a normalization factor. F init (e j , c i ) is the initial detection score of the concept c i in the j th shot of the video v. F trs (e j , c i ) is the final detection score of the concept c i in the j th shot of the video v, obtained by a temporal re-scoring. This fusion function is not unique. Indeed, many functions can be used, such as the one presented in [START_REF] Safadi | Re-ranking for Multimedia Indexing and Retrieval[END_REF], [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF], where the new detection score of a concept c i in a shot e is calculated as follows :

F trs (e j , c i ) = [F init (e j , c i )] 1-γ × [F temp (e j , c i )] γ (2)
where γ is a parameter that controls the robustness of the re-scoring method, and F temp (e j , c i ) is a global score that is calculated by merging the scores of the neighboring shots through a simple function such as arithmetic mean, geometric mean, min, max, etc. γ is tuned by cross validation on development set.

B. Temporal descriptors

TRS uses semantic information which is a set of detection scores of a visual concept in neighboring shots. Its performance is good when concept detectors have a reasonably good performance. However, if we take bad concept detectors we may be surprised by a degradation of performance. In fact, if such a detector provides erroneously the occurrence of a concept in shots s i-1 and s i+1 , it may improve the likelihood that the shot s i contains the target concept while the latter does not belong to si. This error of temporal propagation of semantic information is due to errors made by concept detectors at the classification stage. We propose therefore, a method that uses the temporal context in a step that permits to avoid the problem of classification error propagation. It is possible to incorporate the temporal context in the descriptors extraction step in order to have features that consider themselves the temporal aspect. Descriptors of motion are a typical example for this case. One way to do this is to consider a temporal window when extracting descriptors instead of taking into account only the concerned shot. For example, to calculate a color histogram, we can count the occurrences of the gray levels values not only in one shot, but we extend the treatment to the neighboring shots. Similarly, for SIFT computing method, one can expand points of interest extraction into the neighboring segments, and we can also consider the neighborhood of a shot when counting the occurrences of visual words in bags of words computing. Although with such an idea we exploit temporal information, the temporal order is omitted. Indeed, after the histogram computing over a temporal window, it is not possible to distinguish the information corresponding to the current shot from those of the neighboring ones. Therefore, it becomes impossible to weight information of different sources.

To remedy this problem we propose an approach that escapes these disadvantages and is much simpler to implement.

We propose to extract descriptors in a classic manner, from each segment and then make an early fusion by concatenating for each shot, the descriptors extracted from adjacent shots belonging to a temporal window of size equal to (2 × w + 1) successive shots and centered on the current one (w shots preceding and w shots following the current shot).

Although it is simple, this approach faces a major problem, which is the size of the resulting descriptor. Indeed, the final descriptor is (2 × w + 1) times larger than the feature vector extracted from a single shot in a classic situation. This may become critical especially for some types of big descriptors (e.g. Bags of opponent-SIFT). This affects the learning step which would be slow for large descriptors. It is therefore advisable to plan a dimensionality reduction step (e.g. PCA) to keep a reasonable size of descriptors. On the other hand, it is not recommended to consider a large temporal window for the same reasons of calculation performance. We propose in a second time, to weigh the temporal information so as to give more importance to the information extracted from the current shot. Weight values decrease as one moves away from the current shot. So, the more the shot is far from the center of the temporal window, the more its weight is low. Components values of each temporal fragment of the temporal descriptor are weighted by the weight value associated with it.

III. EXPERIMENTS AND RESULTS

We tried at first to study the variation of relative gain provided by the temporal re-scoring regarding the baseline system performance. We used several baseline systems that follow the classic pipeline : "extraction/classification/fusion". You can refer to the work [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF] for more details. These systems perform a late fusion of a set of concepts detectors trained on different types of low-level descriptors. The only difference in the experimental aspect of these systems is the choice and the number of fused descriptors and data collection used. Our evaluation was conducted on TRECVID 2010 and/or TRECVID 2012 collections. We used Mean Average Precision (MAP) calculated on the whole set of concepts considered as evaluation measure. Figure 1 describes the variation of the percentage of the relative gain on MAP achieved by applying the temporal rescoring on baseline systems. We note that the temporal rescoring usually improves baseline system results. The percentage of relative gain on MAP varies between +2% and +16%. However, the performance of the studied approach may depend on the initial systems we want to improve. Indeed, we note that the relative gain is inversely proportional to the performance of the initial system. The more the system performance to improve is good, the more the gain obtained by the temporal re-scoring is low. This can be explained by the fact that it is easier to improve a system that is bad rather than a system with a good performance. On the other hand, we found that the gain obtained by the temporal re-scoring varies from one concept to another, but this approach improves in most cases concept detection in videos.

We compared in a second time the two approaches described above. To do this, we applied them on the same baseline system. We tested and evaluated our proposed approaches in the context of the semantic indexing task of TRECVid 2012 [START_REF] Over | TRECVID 2012 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF]. Annotations of 346 concepts were provided for the development set via the collaborative work [START_REF] Ayache | Video Corpus Annotation using Active Learning[END_REF]; and ground truth were provided for only 46 of them on the test corpus. We used for the evaluation measure the inferred average precision (infAP) on the 46 evaluated concepts.

We used a list of 10 variants of four types of descriptors: dense SIFT, lab, qw and vlat. You can refer to [START_REF] Ballas | IRIM at TRECVID 2012: Semantic Indexing and Instance Search[END_REF] for more details about these descriptors. We chose to use MSVM classifier/detector in the classification stage because of its good results [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF] for video indexing. Before that, a preprocessing of descriptors was performed using a normalization (Powerlaw) and dimensionality reduction methods (ACP) [START_REF] Safadi | Descriptor optimization for multimedia indexing and retrieval[END_REF]. After extracting the single descriptors of each video shot, we trained MSVM to generate a baseline model. Results of all single descriptors for each couple (concept, shot) are then fused by averaging the detection scores. We will call in the following this results: "Classic descriptors without TRS". We considered it as a baseline system.

We then generated the temporal descriptors as described in section II-B. Because it was difficult to make experiments with a large temporal window, we considered in addition to the current shot the two shots surrounding it. We set weight values after a tunning stage on development data using descriptors of low sizes to facilitate the experimental process. We considered three cases (w i is the weight value of the i th shot): 1)

w i-1 = 1, w i = 1 et w i+1 =1, 2) w i-1 = 0.05, w i = 1 et w i+1 =0.05, and 3) w i-1 = 0.01, w i = 1 et w i+1 =0.01.
We generated for each of the ten single descriptors a temporal descriptor. So for each of these three cases, we obtained ten temporal descriptors. We then trained new MSVM detectors on the temporal descriptors. For each of the three cases and each pair (concept, shot), we combined the results of the ten temporal descriptors, by averaging the detection scores obtained from the classification step. We will call in the following this results: "Temporal descriptors without TRS". We compare "Temporal descriptors" with TRS to study their complementarity. So we applied TRS on "Classic descriptors without TRS" and "Temporal descriptors without TRS", respectively; to generate new results which we will call "Classic descriptors + TRS" and "Temporal descriptors + TRS", respectively. Table I describes results obtained in terms of MAP obtained by the two approaches. The first column of MAP values presents the results obtained by a late fusion of the classic/temporal descriptors without applying TRS. The second one describes the results of applying the temporal re-scoring on the results of the classic/temporal descriptors late fusion. The last line concerns the late fusion of the classic descriptors. The first observation we can make is that the weighting step significantly affects the results. Indeed, we can see in table I that when the same weight value(= 1) is attributed to the different temporal segments we obtained a result worse than the one achieved by using classic descriptors. This leads to a system performance deterioration by decreasing the MAP from 0.2312 to 0.2052, which is equivalent to a relative difference of about -11.24%. Reducing weights of the neighboring shots leads to a performance improvement. The relative gain in this context is about +0.77%. We recall that for "Temporal descriptors", we considered a temporal window of size equal to three successive shots. We expect better performance by adjusting and tuning the temporal window size and weights values. Moreover, we did not perform a more developed optimization of these parameters because of the experimental process heaviness, especially for large values of the temporal window and/or descriptors sizes. On the other hand, TRS improves the results in all cases, as we shown previously in figure 1. The relative gain varies here between +1% and +2.72%. Two other important remarks can be made. The first one is that the temporal rescoring further improves the result of the classic descriptors fusion than the temporal ones, reaching a relative gain of about +2.72% ((0.2375-0.2312)/0.2312) and +0.77% ((0.2330-0.2312) /0.2312), respectively. The second remark is that TRS provides additional gain when it is applied to the fusion of temporal descriptors, reaching an additional relative gain of about +1.5 % ((0.2365-0.2330) /0.2330). This demonstrates the complementarity of the two methods that exploit the temporal context in different ways. In [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF], TRS has deteriorated the results when it was combined with another method taking into account the temporal aspect. We explain this by the fact that both methods that were combined exploit temporal information of semantic type: detection scores. Indeed, this leads to a noise accumulation. But in our work, TRS uses temporal information of semantic type while "Temporal descriptors" exploits lowlevel information: descriptors. This explains somewhat why our two approaches are complementary and their combination improves the results.

Results:

An important question that we can ask is why the improvement achieved is not very high ? To answer this question we have verified the results per concept. We noticed that the gain achieved for some concepts (e.g. Motorcycle, Press conference, etc) is very high and varies between +3,84% and 43%. However, the described approaches fail and deteriorate the detection performance of some other concepts (e.g. Scene Text, Walking Running, etc). We explain this by the fact that some concepts appear for long periods (several consecutive shots) compared to some others, as is the case for: Airplane Flying, Press conference, Singing, etc. Considering the temporal context for such concepts proves a good idea. On the other hand, concepts for which our approaches fail mainly concern fixed objects or concepts that appear in scenes that contain many other different objects (e.g. Bicycling Appears with: road, trees, cars, houses, etc.). In addition, results also vary between descriptors. Therefore, with a simple fusion of their results, descriptors for which our approaches do not perform well affect negatively the overall performance.

Therefore, the gain achieved by our approaches is not low but they do not work well for some concepts and descriptors, and this affects the calculation of the overall performance measure (MAP). We believe that optimizing the fusion approach and choosing the concepts for which our approaches are appropriate could further improve the results.

IV. CONCLUSION AND FUTURE WORK

We presented two methods exploiting the temporal context for semantic indexing of videos. The first one is a rescoring approach that merges concepts detection scores in the neighboring shots. This method demonstrated its effectiveness by improving several baseline systems reaching gains that are inversely proportional to the initial systems performance. The second approach incorporates the temporal context in descriptors extraction stage. To detect a concept c in a shot s i , this approach combines the descriptors extracted from the neighboring shots by applying an early fusion of the descriptors belonging to a temporal window centered on s i . Each of the temporal segments is weighted by a value, so as to give more importance to the shots that are closer to the current shot. Despite a few optimal use, this method has improved a baseline system, but it has been less effective than the temporal rescoring. However, we expect better performance by optimizing and tunning well the size of the temporal window and the weights values. Both approaches have shown the importance and usefulness of the temporal context for semantic video indexing and proved their complementary.

For the future work we will introduce other approaches in comparison and we will develop more deeply the study. To parallelize "Temporal descriptors" approach or studing its run on GPU architecture to better optimize it, take also part of our prospects.

Fig. 1 .

 1 Fig.1. % of relative gain on MAP achieved by TRS.

  ) OF TEMPORAL DESCRIPTORS AND TEMPORAL RE-SCORING ON TRECVID 2012 COLLECTION.

ACKNOWLEDGEMENTS

This work was partly realized as part of the Quaero Program funded by OSEO, French State agency for innovation. This work was supported in part by the French project VideoSense ANR-09-CORD-026 of the ANR. Experiments presented in this paper were carried out using the Grid'5000 experimental test bed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr). The authors wish to thank the participants of the IRIM (Indexation et Recherche d'Information Multimédia) group of the GDR-ISIS research network from CNRS for providing the descriptors used in these experiments.


Mateusz Budnik

Efrain-Leonardo Gutierrez-Gomez

Bahjat Safadi

Georges Quénot

Learned features versus engineered features for semantic video indexing

In this paper, we compare "traditional" engineered (hand-crafted) features (or descriptors) and learned features for content-based semantic indexing of video documents. Learned (or semantic) features are obtained by training classifiers for other target concepts on other data. These classifiers are then applied to the current collection. The vector of classification scores is the new feature used for training a classifier for the current target concepts on the current collection. If the classifiers used on the other collection are of the Deep Convolutional Neural Network (DCNN) type, it is possible to use as a new feature not only the score values provided by the last layer but also the intermediate values corresponding to the output of all the hidden layers. We made an extensive comparison of the performance of such features with traditional engineered ones as well as with combinations of them. The comparison was made in the context of the TRECVid semantic indexing task. Our results confirm those obtained for still images: features learned from other training data generally outperform engineered features for concept recognition. Additionally, we found that directly training SVM classifiers using these features does significantly better than partially retraining the DCNN for adapting it to the new data. We also found that, even though the learned features performed better that the engineered ones, the fusion of both of them perform significantly better, indicating that engineered features are still useful, at least in this case.

I. INTRODUCTION

Deep Convolutional Neural Networks (DCNN) have recently made a significant breakthrough in image classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. This has been made possible by a conjunction of factors including: findings about how to have deep networks effectively and efficiently converge [START_REF] Orr | Neural Networks : Tricks of the Trade[END_REF], the use of convolutional layers [START_REF] Fukushima | Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[END_REF] [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], the availability of very powerful parallel architectures (GPUs), findings about how exactly a network should be organized for the task [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], and the availability of huge quantity of cleanly annotated data [START_REF] Deng | ImageNet: A Large-Scale Hierarchical Image Database[END_REF].

Not to minimize the importance of the hardware progress and of algorithmic breakthroughs, the availability of a large number of image examples for a very large number of concepts was really crucial as DCNNs really needs such amount of training data for actually being efficient. Data augmentation (e.g. multiple crops of training samples) can further help but also only when a huge amount of data is already available. Such amount of training data is currently available only with ImageNet which corresponds to a single type of application and only for still images. For video documents for instance, many annotated collection exist but with much smaller number of concepts and/or much smaller number of examples. Trying to train DCNNs on such data generally leads to results that are less good than those obtained using "classical" engineered fea-tures (or descriptors) combined with also "classical" machine learning methods (typically SVMs).

Two strategies have been considered for making other domains benefit from the success of the DCNN/ImageNet combination. The first one consists in pre-training a DCNN on ImageNet data and then partly retrain or fine-tune it on another collection [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF] [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF]. Generally, only the last layers are retrained, the exact number of which as well as the learning parameters being experimentally determined by cross-validation. Though this strategy can produce much better results than when the DCNN is trained only on the target data, it does not necessarily compete with classical approaches and/or lead to gains that are much less important than in the ImageNet case.

The second strategy consists in using a DCNN pre-trained on ImageNet, applying it to a different target collection and use the final ImageNet concept detection scores and/or the output of the hidden layers as features for training classifiers and making prediction on the different target collection. Razavian et al. [START_REF] Razavian | CNN Features Off-the-Shelf: An Astounding Baseline for Recognition[END_REF] have very successfully applied this strategy to a number of test collections for both image indexing and image retrieval.

In this work, we explore how these strategies perform in the context of video indexing. We also investigate how they can be combined with classical methods based on engineered features and how they can be combined with other videospecific improvement methods like temporal re-scoring [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF]. Experiments have been carried out in the context of the semantic indexing task at TRECVid [START_REF] Over | Trecvid 2014 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF]. In this paper we make the following contributions:

1) We confirm the results obtained for still images in the case of video shot indexing: features learned from other training data generally outperform engineered features for concept recognition. 2) We show that directly training SVM classifiers using these features does better than partially retraining the DCNN for adapting it to the new data. 3) We show that, even though learned features outperform engineered ones, fusing them perform significantly better, indicating that engineered features are still useful, at least in this case. 4) We show that temporal an conceptual re-scoring methods also improve classification results obtained with DCNN features.

II. RELATED WORK

Semantic features are not restricted to DCNN and had already been used for multimedia classification and retrieval.

Smith et al. [START_REF] Smith | Multimedia semantic indexing using model vectors[END_REF] introduced them as "model vectors". These provide a semantic signature for multimedia documents by capturing the detection of concepts across a lexicon using a set of independent binary classifiers. Ayache et al. [START_REF] Ayache | Image and video indexing using networks of operators[END_REF] proposed to use local visual categories detection scores on regular grids or to use topic detection on ASR transcriptions for video shot classification. Su et al. [START_REF] Su | Improving image classification using semantic attributes[END_REF] also proposed to use semantic attributes obtained with supervised learning either as local or global features for image classification.

In all these works and many other similar ones, the semantic features are learned on completely different collections and generally for concepts or categories different from those searched for on the target collection. Hamadi et al. [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF] used the approach using the same collection and the same concepts both for the semantic feature training and for their use in a further classification step. In this variant, called "conceptual feedback", a given target concept is learned both from the "low-level" features and from the detection scores of the other target concepts also learned from the same low-level features (the training of the semantic features has to be done by crossvalidation within the training set so that it can be used for the second training step both on the training and test sets).

Concerning the first DCNN transfer strategy (DCNN retraining), Yosinski et al. [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF] et al showed that the features corresponding to the output of the hidden layers are well transferable from one collection to another and that re-training only the last layers is very efficient both for comparable or for dissimilar concept types. Their experiments were conducted only within the ImageNet collection however. Similar results were obtained by Chatfield et al. [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF] on different data.

Concerning the second DCNN transfer strategy (classical training with features produced by DCNNs), Razavian et al. [START_REF] Razavian | CNN Features Off-the-Shelf: An Astounding Baseline for Recognition[END_REF] showed that it works very well too, for several test collection, some of which are close to ImageNet and some of which are quite different both in terms of visual contents and in terms of target concepts. They also showed that this type of semantic features can be successfully used both for categorization tasks and for retrieval tasks. Finally, they showed that in addition to the score values produced by the last layer, the values corresponding to the output of all the hidden layers can be used as feature vectors. The semantic level of the layers output values increases with the layer number from low-level, close to classical engineered features for the first layers, to fully semantic for the last layers. Their experiments showed that using the last but one and last but two layer outputs generally gives the best results. This is likely because the last layers contain more semantic information while the last one has lost some useful information as it is tuned to different target concepts. There is generally no equivalent to the output of the hidden layers in classical learning methods (e.g. SVMs) and these can only produce the final detection scores as semantic features.

Many variants of the "classical" approach exist. Most of them consist in a feature extraction step followed by a classification step. In many cases, several different features can be extracted and in some cases a few different classification methods are also used in parallel; a fusion step has then to be considered. Fusion is called "early" when it is performed on extracted features, "late" when it is performed on classification scores or "kernel" when it is performed on computed kernel within the classification step (for kernel-based methods); many combinations can also be considered.

A very large variety of engineered features has been designed and used for multimedia classification. Some of them are directly computed on the whole image (e.g. color histograms), some of them are computed on image parts (e.g. SIFTs) [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. In the latter case, the locally extracted features need to be aggregated in order to produce a single fixed-size global feature. Many methods can be used for that, including the "bag of visual words" one (BoW) [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][17] or the Fisher vector (FV) one [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF] and similar ones like super vectors (SV), and vector of locally aggregated descriptors (VLAD) [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] or tensors (VLAT) [START_REF] Picard | Efficient image signatures and similarities using tensor products of local descriptors[END_REF]. Some of them may reach their maximum efficiency only when they are highly dimensional, typically the FV, VLAD and VLAT ones. Two different strategies can be considered for dealing with them: either use linear classifiers combined with compression techniques [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF] or using dimensionality reduction techniques combined with non-linear classifiers [START_REF] Safadi | Descriptor optimization for multimedia indexing and retrieval[END_REF]. In the case of video indexing, engineered features have been proposed also for the representation of audio and motion content.

The comparison of methods presented here has been conducted in the context of the Semantic INdexing (SIN) task TRECVid [START_REF] Over | Trecvid 2014 -an overview of the goals, tasks, data, evaluation mechanisms and metrics[END_REF]. It differs from the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) in many respects. Indeed, the indexed units are video shots instead of still images. The quality and resolution of the videos are quite low (512 and 64 kbit/s for the image and audio streams respectively). The target concepts are different: 346 non-exclusive concepts with generic-specific relations. Many of them are very infrequent in both the training and test data. The way the collection has been built is also very different. In ImageNet, a given number of sample images have been selected and checked for each target concept resulting in a high quality and comparable example set size for all concepts. In TRECVid SIN, videos have been randomly selected from the Internet Archive completely independently of the target concepts; the target concepts have been annotated a posteriori resulting in very variable number of positive and negative examples for the different concepts. Most of the concepts are very infrequent and also not very well visible. Compared to ImageNet, the positive samples are much less typical, much less centered, of smaller size and with a much lower image quality. The task is therefore much more difficult than the ILSVRC one but it may also be more representative of indexing and retrieval tasks "in the wild". An active learning method was used for driving the annotation process for trying to reduce the imbalance class effect in the training data and also ensure a minimum number of positive samples for each target concept [START_REF] Ayache | Video Corpus Annotation using Active Learning[END_REF]. The resulting annotation is sparse (about 15% in average) and consists in 28,864,844 concept × shots judgements. All of these differences probably explain why training DCNNs directly on TRECVid SIN data gives much poorer results than on ImageNet data and why the two considered adaptation strategies are needed (or perform much better) in this case.

III. COMPARISON BETWEEN ENGINEERED FEATURES AND SEMANTIC FEATURES

In this section, we compare the performance of engineered features and semantic features. For the engineered features, we use a series of features shared by the participants of the IRIM group of the French GDR ISIS [START_REF] Ballas | IRIM at TRECVID 2014: Semantic Indexing and Instance Search[END_REF].

Two different classifiers have been used, one based on the k nearest neighbors and one based on Multiple SVMs because it handles well large class imbalances [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF]. The predictions of these two classifiers were fused producing a globally better result [START_REF] Safadi | LIG at TRECVid 2014: Semantic Indexing[END_REF]. We also use the approach based on dimensionality reduction combined with non-linear classification for dealing with high-dimensional features.

We considered the following engineered features types:

• CEALIST/bov dsiftSC 8192: bag of visual terms [START_REF] Shabou | Locality-constrained and spatially regularized coding for scene categorization[END_REF]. Dense SIFT are extracted every 6 pixels. The codebook of size 1024 is built with Kmeans. Bags are generated with soft coding and max pooling. The final signature results from a three-level spatial pyramid: 1024 × (1 + 2 × 2 + 3 × 1) = 8192 dimensions.

• CEALIST/bov dsiftSC 21504: bag of visual terms [START_REF] Shabou | Locality-constrained and spatially regularized coding for scene categorization[END_REF]. Same as CEALIST/bov dsiftSC 8192 with a different spatial pyramid: 1024 × (1 + 2 × 2 + 4 × 4) = 21504 dimensions.

• ETIS/global <feature>[<type>]x<size>: (concatenated) histogram features [START_REF] Gosselin | Combining visual dictionary, kernel-based similarity and learning strategy for image category retrieval[END_REF], where:

• <feature> is chosen among lab (CIE L*a*b* colors) and qw (quaternionic wavelets, 3 scales, 3 orientations) • <type> can be m1x1 (histogram computed on the whole image), m1x3 (histogram for 3 vertical parts) or m2x2 (histogram on 4 image parts) • <size> is the dictionary size, sometimes different from the final feature vector dimension. For instance, with <type>=m1x3 and <size>=32, the final feature vector has 3 × 32 = 96 dimensions.

• ETIS/vlat <desc type> dict<dict size> <size>:

compact Vectors of Locally Aggregated Tensors (VLAT [START_REF] Picard | Efficient image signatures and similarities using tensor products of local descriptors[END_REF]). <desc type> = low-level descriptors, for instance hog6s8 = dense histograms of gradient every 6 pixels, 8×8 pixels cells. <dict size> = size of the low-level descriptors dictionary. <size> = size of feature for one frame. Note: these features can be truncated. These features must be normalized to be efficient (e.g. L 2 unit length).

• LIG/opp sift <method>[ unc] 1000: bag of word, opponent sift, generated using Koen Van de Sande's software [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]: 1000 dimensions (384 dimensions per detected point before clustering; clustering on 535117 points coming from 1000 randomly chosen images). <method> method is related to the way by which SIFT points are selected: har corresponds to a filtering via a Harris-Laplace detector and dense corresponds to a dense sampling; the versions with unc correspond to the same with fuzziness introduced in the histogram computation.

• LIRIS/OCLPB DS 4096: Dense sampling OCLBP [START_REF] Zhu | Color orthogonal local binary patterns combination for image region description[END_REF] 4096-dimensional bag-of-words descriptors are finally generated using a pre-trained dictionary.

• LISTIC/SIFT *: Bio-inspired retinal preprocessing strategies is applied before extracting Bag of Words of Opponent SIFT features (details in [START_REF] Strat | Retina enhanced sift descriptors for video indexing[END_REF]) using the retinal model from [START_REF] Benoit | Using human visual system modeling for bio-inspired low level image processing[END_REF]. Features extracted on dense grids on 8 scales (initial sampling=6 pixels, initial patch=16x16pixels), using a linear scale factor 1.2. Kmeans clustering is used for producing dictionaries of 1024 or 2048 visual words. The proposed descriptors are similar to those from [START_REF] Strat | Retina enhanced sift descriptors for video indexing[END_REF] except that multiscale dense grids are used. Despite showing equivalent mean average performance, the various pre-filtering strategies present different complementary behaviors that boost performances at the fusion stage [START_REF] Strat | Retina enhanced bag of words descriptors for video classification[END_REF]. Figure 1 shows the performance of several types of engineered features. In several cases, the result is shown for already a combination of variants of the same feature type, for instance corresponding to a pyramidal image decomposition. The performance is given as the Mean (inferred) Average Precision on the 2013 and 2014 editions of the TRECVid SIN task. That task was a bit harder in 2014 because the set of evaluated concepts was different, including more difficult ones. The last entry in the figure correspond to a late fusion of all the IRIM features (including others less good than those shown). We can see that the fusion of these features does significantly better than the best of them.

We considered the following learned or semantic feature types:

• Semantic features computed using a Fisher vector approach [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF]. Two variants were produced by Florent Perronnin fro Xerox: a 1000-dimensional one trained using the 1000 concepts of ILSVRC 1000, and a 10174-dimensional one trained using 10174 ImageNet concepts.

• Semantic features computed using a DCNN following the Krizhevsky architecture [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], using the caffe implementation [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF], and pre-trained on the 1000 ISLVRC 2012 concepts. Two variants were produced by LIG and Eurecom, corresponding respectively to the simple and to the data augmented versions.

• Quasi-semantic features corresponding to last three hidden layers of the same network (simple version) whose dimensionalities are respectively 43,264, 4,096 and 4,096 for layers 5, 6 and 7.

• Concepts features corresponding to the conceptual feedback approach [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF] applied two times. These are were originally designed for being used with engineered descriptors but they acn also include other semantic descriptors; here they have been computed including the Xerox semantic descriptors.

Several late fusions of features of the same type were also considered.

Figure 2 shows the performance of several types of learned features. The first entry is the combination of all engineered features showed as a baseline. We can immediately see that almost all semantic features perform similarly to or better than the baseline and therefore significantly better than any individual engineered feature. We can also observe than combinations of semantic features perform even better. Considering the caffe output and internal layers, the best choice is fc6 which is very close to fc7. The final output layer is less good and fc5 is even less good. It is interesting to notice that the performance of the Xerox Fisher vector based semantic features is very close to the performance of the final output of the pre-trained caffe network while both use very similar training data (ILSVRC10 and ILSVRC12 respectively). The features corresponding to the conceptual feedback perform better but the Xerox semantic features were included in their production.

IV. COMPARISON BETWEEN PARTIAL DCNN RETRAINING AND USE OF DCNN LAYER OUTPUT AS FEATURES

We made several trials for retraining the last layers of the pre-trained caffe implementation. We tried to retrain the last one, last two or last three layers, each time doing our best to select the optimal training parameters in each case. The best performance was obtained when retraining the last two layers and it was of 0.2171 and 0.1839 respectively on SIN 2013 and 2014 which is less that using the fc6 layer for which the KNN/MSVM classifier combination gives 0.2347 and 0.2016 respectively. While the retraining of the last two layers starts from the same fc6 feature, it seems that these two layers are not able to do a learning as good as the KNN/MSVM combination. This may be because they actually implement only a twolayer perceptron and because they have difficulties with highly imbalanced training data.

V. TEMPORAL RE-SCORING WITH SEMANTIC FEATURES

We applied the temporal re-scoring method proposed by Safadi et al. [START_REF] Safadi | Re-ranking by Local Re-scoring for Video Indexing and Retrieval[END_REF] as it is a simple way to obtain a significant performance boost at very low computing cost. It simply exploits the fact that if a concept appears in a video shot, it is more likely to appear in the preceding and following shots.

Figure 3 shows the performance gain brought by the temporal re-scoring for the different considered semantic features on SIN 2014. We can observe that the gain is more important for some features that for others. It is greater for learned features than for engineered ones. It is greater for DCNN output features than for Fisher vector based features. It is also greater for semantic features than for quasi-semantic ones (corresponding to internal layers). It also appears smaller for conceptual feedback features but this is due to the fact that the feedback features were computed from scores that were already re-scored as it works better like this [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF].

VI. FUSION AND OTHER IMPROVEMENT METHODS

Figure 4 shows the performance gain brought by the successive fusion of descriptors of increasing performance. This strategy has been selected as it has been observed that fusion gives better results when done on sources of comparable performance [START_REF] Strat | Hierarchical late fusion for concept detection in videos[END_REF]. This strategy also ensures a dilution and therefore a smaller contribution of those having lower performances; it has also been observed that this is better than simply dropping them [START_REF] Strat | Hierarchical late fusion for concept detection in videos[END_REF]. These fusions are followed by post-processing techniques bringing additional performance gains. The (D LIG.14 X) labels correspond to our official submissions at the TRECVid 2014 SIN task.

Fusion of engineered and learned features does better than any of them separately, indicating that though they are individually and collectively less good, engineered features are still useful for global system performance. Though hidden layers are individually the best ones, they do not bring further improvement when the engineered descriptors have already been fused with Fisher vector based features and DCNN output features. Conceptual feedback and temporal re-scoring still improve further. Finally, two other improvement techniques were tried: conceptual re-scoring and use of an uploader model. Conceptual re-scoring is different from conceptual feedback, it is similar to temporal re-scoring but it exploits the semantic similarity between concepts instead of the temporal closeness between video shots [START_REF] Hamadi | Extended conceptual feedback for semantic multimedia indexing[END_REF]. It did not prove useful probably because, even if based on a different method, it captures the same type of information as the conceptual feedback done previously. The uploader model uses the information of who uploaded the video on the Internet archive and tries to exploit the fact that videos uploaded by a same user tend to have the same type of content [START_REF] Niaz | Improving video concept detection using uploader model[END_REF]. It did not bring further improvement after all the other improvements were performed.

VII. CONCLUSION

In this paper, we have compared "traditional" engineered features and learned features for content-based semantic indexing of video documents. We made an extensive comparison of the performance of learned features with traditional engineered ones as well as with combinations of them. The comparison was made in the context of the TRECVid semantic indexing task. Our results confirm those obtained for still images: features learned from other training data generally outperform engineered features for concept recognition. Additionally, we found that directly training SVM classifiers using these features does better than partially retraining the DCNN for adapting it to the new data. We also found that, even though the learned features performed better that the engineered ones, the fusion of both of them still perform significantly better, indicating that engineered features are still useful, at least in this case.

Fig. 1 .

 1 Fig. 1. Performance of engineered features

Fig. 2 .

 2 Fig. 2. Performance of semantic features

  Instead of encoding local patterns on 8 neighbors, encoding is performed on two sets of 4 orthogonal neighbors, resulting in two independent codes. Concatenating and accumulating two codes leads to a final 32 dimensional LBP histogram, compared with original 256 dimensions.

bag-of-words descriptor with 4096 k-means clusters. We extract orthogonal combination of local binary pattern (OCLBP) to reduce original LBP histogram size and at the same time preserve information on all neighboring pixels.

ACKNOWLEDGMENT

This work was conducted as a part of the CHIST-ERA CAMOMILE project, which was funded by the ANR (Agence Nationale de la Recherche, France). Part of the computations presented in this paper were performed using the Froggy platform of the CIMENT infrastructure (https://ciment.ujfgrenoble.fr), which is supported by the Rhône-Alpes region (GRANT CPER07 13 CIRA) and the Equip@Meso project (reference ANR-10-EQPX-29-01) of the programme Investissements d'Avenir supervised by the Agence Nationale pour la Recherche. Results from the IRIM network were also used in these experiments [23]. The authors also wish to thank Florent Perronnin from XRCE for providing features based on classification scores from classifiers trained on ILSVRC/ImageNet data [18].