Stéphane Ayache

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

EVALUATION OF ACTIVE LEARNING STRATEGIES FOR VIDEO INDEXING

In this paper, we compare active learning strategies for indexing concepts in video shots. Active learning is simulated using subsets of a fully annotated dataset instead of actually calling for user intervention. Training is done using the collaborative annotation of 39 concepts of the TRECVID 2005 campaign. Performance is measured on the 20 concepts selected for the TRECVID 2006 concept detection task. The simulation allows exploring the effect of several parameters: the strategy, the annotated fraction of the dataset, the number of iterations and the relative difficulty of concepts. Three strategies are compared. The first two respectively select the most probable and the most uncertain samples. The third one is a random choice. The "most probable" strategy is almost always the best one and it permits to get very close to the maximum performance while requesting the annotation of only one eighth of the whole dataset. The "most uncertain" strategy is better for moderately difficult concepts and when a significant part of the dataset is annotated.

INTRODUCTION

Image and video databases become more and more common and large. They are found in a variety of places including home, companies and institutions and for a variety of applications. In order to keep them manageable, powerful tools are needed for searching and browsing. These tools need other tools for contents indexing. This indexing can be done at the signal level (color, texture, motion ...) or at the semantic level (concepts). From both indexing types, the latter is by far the most useful for the users but it is also by far the most difficult one to extract from the contents. Due to the so called semantic gap between the raw image or video contents and the elements that makes sense to human beings, indexing concepts in image or video documents is a very hard task. This task is most often carried out using classifiers or networks of classifiers [START_REF] Milind | On the detection of semantic concepts at trecvid[END_REF][START_REF] Ayache | Context-based conceptual image indexing[END_REF]. Supervised learning consists in training a system from sets of positive and negative examples. The learning system Georges Quénot is with CNRS may be composed of various types of feature extractors, classifiers and fusion modules. The systems' performance depends a lot on the implementation choices and details but it also strongly depends upon the size and quality of the training examples. While it is quite easy and cheap to get large amounts of raw data, it is usually very costly to have them annotated because it involves human intervention for the judging of the "ground truth". In the context of LSCOM (Large Scale Concept Ontology for Multimedia) [START_REF] Naphade | Large-scale concept ontology for multimedia[END_REF], 449 concepts have been annotated on about 69 thousands of samples. If we consider the performance obtained by the state of the art systems using this annotated data during the TRECVID 2006 evaluation campaign (a Mean Average Precision of only 0.1 to 0.2), even this seems far from being sufficient. While the volume of data that can be manually annotated is limited due to the cost of manual intervention, there remains the possibility to select the data sample that will be annotated so that their annotation is as useful as possible. Deciding which samples will be the more useful is not trivial. Active learning is an approach in which an existing system is used to predict the usefulness of new samples. This approach is a particular case of incremental learning in which a system is trained several times with a growing set of samples. Several strategies or heuristics can be considered to predict the samples' usefulness. Most of them operate by selective sampling which consists in progressively adding to the training set the samples expected to be the most informative ones. The most popular ones include:

• When several systems are available, choose the samples which maximize the disagreement amongst them ("query by committee" [START_REF] Seung | Query by committee[END_REF]). This strategy cannot be used if a single system is available or inefficient if the used systems are too close to each other.

• Choose the most uncertain samples (uncertainty sampling [START_REF] Lewis | A sequential algorithm for training text classifiers[END_REF]). This strategy tries to increase the sample density in the neighborhood of the frontier between positives and negatives and therefore improve the system's precision.

• Choose the most probable positive samples. This strategy tries to maximize the size of the set of positive samples (the positive samples are most often sparse within the whole set and finding negative samples is easy and these generally come as numerous enough whatever the selection strategy).

• Choose the farthest samples from already evaluated ones. This strategy tries to maximize the variety of the evaluated samples and therefore to improve the system's recall. It is based on a distance between sample that has to be appropriately defined and it does not require the availability of a system (the considered distance, however, may be related to some system outputs).

More complex strategies can be used including combinations of these. For instance, the system may choose the samples for annotation amongst the most probable ones and amongst the farthest from the already evaluated ones. Another possibility is to select samples by groups in which maximize the expected global knowledge gain [START_REF] Souvannavong | Partition sampling for active video database annotation[END_REF]. Quite often, indexing systems classify samples for several concepts. Many strategies are based on the assumption that when a sample is selected for annotation, all the concepts are evaluated by the annotator. This is what was done in the context of the collaborative annotation effort of TRECVID 2003 [START_REF] Lin | Video collaborative annotation forum: Establishing ground-truth labels on large multimedia datasets[END_REF] where 133 concepts were annotated at once by an operator for each proposed shot. The resulting annotation was of poor quality because of the cognitive load applied to the annotator. For instance, many false negative were observed because the operator was not able to keep in mind all the concepts to be annotated. Therefore, for the TRECVID 2005 [START_REF] Volkmer | A web-based system for collaborative annotation of large image and video collections[END_REF] collaborative annotation effort and for the LSCOM annotations as well [START_REF] Naphade | Large-scale concept ontology for multimedia[END_REF], the choice was made to give to the operators a single concept to annotate on a series of proposed shots. From the active learning point of view, the type of annotation has some implications. The second one excludes methods that require that each selected sample is annotated against all concepts. On the other hand, it permits a finer grain application of the various strategies because sample selection can be done independently for each concept.

A particular case is the use of active learning within relevance feedback. In this case, there is only one concept considered and it corresponds to the user's need. The system learns it from the growing set of user's judgments across feedback cycles. This approach has been successfully used in content-based image retrieval [START_REF] Tong | Support vector machine active learning for image retrieval[END_REF][START_REF] Gosselin | A comparison of active classification methods for content-based image retrieval[END_REF].

In this work we investigate how efficient active learning strategies are for the indexing of concepts in video shots. We consider the annotation type used in TRECVID 2005 and LSCOM collaborative annotation efforts: samples are presented to the annotator for a single concept at once. We use a single classification system which is one of the variant that we used for our participation to the "high level feature extraction" task of TRECVID 2006 [START_REF] Ayache | CLIPS-LSR Experiments at TRECVID 2006[END_REF]. One originality in the evaluation approach is that we use the full TRECVID 2005 collaborative annotation to simulate the incremental annotations required by the various active learning strategies. Our assumption is that the annotations made by an annotator do not depend upon the order in which the annotations are proposed to him or that, if this is the case, this does not significantly affect our conclusions.

SIMULATED ACTIVE LEARNING

Actual experiments for comparing strategies in active learning are difficult and costly to organize because of the involvement of humans in the process. Active learning methods are especially developed for contexts in which it is possible to annotate only a small fraction of a large data set. It sometimes happens however that large datasets are fully annotated even if the corresponding cost if very high. Active learning is not relevant in these cases since nothing remains to be annotated but, on the opposite, such large scale full annotations constitute opportunities to simulate, evaluate and compare strategies in active learning without the need to involve again a user. In simulated active learning, methods are executed as if no annotation is available in the beginning. Then, each time a human annotation is needed, the corresponding subset of the full annotation is made available.

The performance of the system during the various stages of the simulated active learning process will normally not exceed the performance it achieves using the whole annotated dataset. What simulated active learning brings is the possibility to compare the performance that the system would have reached with the various strategies if only a given fraction of the whole dataset could have been annotated.

From this, it is possible to make predictions on what would be the better strategy if an even larger dataset becomes available but only a small fraction of it can be annotated. It is also possible to make predictions on what would be the better strategy for annotating a large number of new concepts on a small fraction of the existing dataset. A large number of strategies can be compared under equivalent and repeatable conditions.

Large fully annotated datasets have been produced in the context of TRECVID 2005 [START_REF] Volkmer | A web-based system for collaborative annotation of large image and video collections[END_REF] and LSCOM [START_REF] Naphade | Large-scale concept ontology for multimedia[END_REF]. In both cases, data samples are video shots of the development part of the TRECVID 2005 video collection. In the TRECVID 2005 collaborative annotation effort, 39 concept labels were assigned to 36014 shots and in the LSCOM project, 449 concept labels were assigned 61901 shots. This was done in conditions similar to those of active learning.

In order to evaluate the efficiency of the different strategies, it is necessary to measure the system performance on a test dataset which is different from the training dataset. The TRECVID 2005 and 2006 test datasets with their annotations and performance metrics can be used for this purpose in conjunction with the above mentioned training data.

SYSTEM DESCRIPTION

For the evaluation of active learning strategy, the exact type of system used has probably a strong influence. It can be expected that a better the system will globally increase the efficiency of most strategies. Also, the optimal strategy may vary with systems' characteristics. We did not evaluate here the influence of the classifying system implementation. We selected one of the variants of the classification system we used for the TRECVID 2006 concept detection task [START_REF] Ayache | CLIPS-LSR Experiments at TRECVID 2006[END_REF]. This variant has the advantages of having a relatively short training time and of working independently on the different concepts. It also has a global performance (when trained on the whole development set) which is close to the median performance of the participating systems.

Concept detection is performed using networks of SVM classifiers arranged in order to take into account a variety of low level descriptors combining text, local and global visual information as well as conceptual context. The 20 assessed concepts of the TRECVID 2006 campaign are derived from "intermediate" concepts, themselves derived from low level descriptors and not necessarily related to the target final concepts. This approach is linked to the idea that it may be better to bridge the semantic gap in several steps within which the complexity remains low and the correlation between the inputs and the outputs is kept high.

"Visual" intermediate concepts

In • 9 color components (RGB means, variances and covariances)

• 24 texture components (8 orientations × 3 scales Gabor transforms)

• 7 motion components (the central velocity components plus the mean, variance and co-variance of the velocity components within the patch; a velocity vector is computed for every image pixel using an optical flow tool [START_REF] Quénot | Computation of optical flow using dynamic programming[END_REF] on the whole image).

The 15 × 260 outputs of those intermediate concepts are inputs for the higher level classifiers (the 20 classifiers corresponding to the TRECVID 2006 assessed concepts). In practice, not all of the 15 intermediate concepts are used for all of the 20 concepts but only a subset of them. This subset is manually chosen for each of the concepts and typically contains 5 or 6 intermediate concepts. Therefore, we consider those intermediate concepts as "local" descriptor which typically contains about 1500 components. The vector components corresponding to the intermediate concepts are real values between 0 and 1 corresponding to the estimated probability of the patch of containing the concept as they are computed by the libsvm package [START_REF] Chang | LIB-SVM: A Library for Support Vector Machines[END_REF].

Visual global features

The intermediate concepts are completed by low-level visual features at the global level. The two descriptors are simply concatenated, as an "early fusion" scheme. The global low-level image descriptors include:

• 64 color components (4 × 4 × 4 color histogram),

• 24 texture components (8 orientations × 5 scales Gabor transform),

• 5 motion components (the mean, variance and covariance of the velocity components within the image).

Adding global descriptors aim to add context into the concept detection process. Exploiting local and global descriptors can help to overcome the ambiguity often faced in concept detection.

Textual intermediate concepts

We also computed "Textual" intermediate concepts on each audio segment of the ASR-MT transcription. A list of 2500 terms optimized for each of the 20 concepts is built considering the most frequent terms and excluding stop words, which co-occur with a considered concept. The text descriptor is a Boolean vector whose components are 0 or 1 if the term is absent or present in the audio segment. Again the vectors built at the level of the audio segments are projected on the key frames and in the same way.

Normalized Early Fusion

The number of extracted features depends upon the modalities and the type of the features. Hence, an early fusion scheme based on simple vector concatenation is much affected by the vector which has the highest number of inputs. Such fusion should ha an impact on the classification, especially with a RBF kernel which is based on Euclidian distance between each training sample.

In traditional SVM implementation, a normalization process is integrated and aims to transform each input in the same range (e.g. [0..1], [-1..1]) in order to unbiased the Euclidian distance. But, for the scope of merging features, this normalization does not take into account the number of input from individual features. Hence, we used a normalized early fusion scheme to avoid the problem of imbalanced features input by reprocessing each feature vectors before concatenation. We normalized each individual vector so that its average norm is about the same. The normalization formula becomes:

x i ′ = x i -min i (max i -min i ) × Card(x i )
where x i is an input of the feature vector x, min i and max i are respectively the minimum and maximum value of the i th input among the training samples and Card(x i ) is the number of dimensions of the source vector of x i .

EXPERIMENTATIONS

Evaluations were done using the TRECVID 2005 collaborative annotation for training and the TRECVID 2006 concept detection task for testing. In this task, systems are required to provide, for 20 concepts, a ranked list of the 2000 shots most likely to contain it (amongst 146328 candidate shots). System performance is measured using the Mean Average Precision of the system computed on the returned list (in practice, a variant called Inferred Average Precision is used). This metric is the one that we use for all our evaluations and for comparing the efficiency of the different strategies.

Strategies

Three strategies have been evaluated each with three different step sizes. The first strategy is to always select the most probable positive samples. The second strategy is to always select the most uncertain samples. The third strategy in rather an absence of strategy and corresponds to a random choice, it is used as a baseline for the other two. The system always outputs a score for each test sample. This score is used for ordering the results list and it correspond to the probability of presence of the target concept in the sample computed as such by the last SVM stage of the system. In the "most probable" strategy, samples with the probability closest to 1.0 are selected. In the "most uncertain" strategy, samples with the probability closest to 0.5 are selected. The three strategies are implemented using a step size (fraction of the whole set that is proposed for annotation to a human) of 1/6th, 1/20th and 1/40th respectively. We did not investigate yet the effect of the initial conditions. We started all experiments with an initial set of ten positives and twenty negative samples per concept randomly selected in the set of all positive and negative samples. That is: for the "cold start", we assume that in actual experiments, users have at least ten examples of what they are looking for. We also consider that "negatives come for free" because it is much easier to find negative samples than positive ones. For system training, we use twice as many negative samples as positive samples because this appears to be an optimum value for the kind of classifier we use. In all our experiments, whatever the strategy, the target concept, the step size and the step number, we always got at least this ratio in the annotations we asked for. Since there are always much more negative samples than necessary, the selected ones are randomly chosen.

Global trends

Figure 1 displays the evolution of system MAP (actually Inferred Average Precision as measured in TRECVID 2006) with the number of annotated samples for the three strategies, for all concepts and with the smallest step size (2.5% of the sample set). We first notice a significant level of "noise": the performance has some fluctuations even considering an average on 20 concepts and large numbers so annotated samples. The performance is not always increasing with the number of annotations. The fluctuations are probably due to the fact that added concepts, though positives, are not always very representative. We also noticed that they depend upon the random choice of negative samples and upon the initial choice of the positive samples for the cold start (not shown). This is the case even at the last iteration when all positive samples are taken into account because the negative samples have been selected in a different way. General trends can be observed anyway by making abstraction of the fluctuations:

• The "most probable" strategy is the best one and it gets very close to the best performance with the annotation of only about 12.5% of the whole sample set.

• The "most uncertain" strategy does still much better than the "random" one but worse than the "most probable" one. This is a bit surprising because this strategy is the preferred one in many approaches. This strategy gets close to the best performance with the annotation of about 25% of the whole sample set. The performance increases then very slowly.

• The "random" strategy shows a continuous increase in performance with the size of the sample set with

Most probable Most uncertain Random

Fig. 1. Evolution of system MAP with the number of annotated samples for the three strategies, all concepts a higher rate near the beginning. The maximum performance is not reached even with the annotation of 50% of the sample set.

Relation with concept difficulty

Figures 2, 3 and 4 display the same information for easy, moderately difficult and difficult concepts respectively. Easy concepts are: WEATHER (0.4539), SPORT (0.3006), MAPS (0.2171), MILITARY (0.0985) and CAR (0.0771). Moderate concepts are: WATERSCAPE-WATERFRONT (0.0755), CHARTS (0.0708), MEETING (0.0671), FLAG-US (0.0634), TRUCK (0.0355), MOUNTAIN (0.0329) and PEOPLE-MARCHING (0.0284). Difficult concepts are: DESERT (0.0557), EXPLOSION-FIRE (0.0548), COMPU-TER-TV-SCREEN (0.0411), POLICE-SECURITY (0.0257), AIRPLANE (0.0206), ANIMAL (0.0058), OFFICE (0.0027) and CORPORATE-LEADER (0.0000). The number between parentheses is the MAP for this concept when the system is trained on the whole dataset.

The general trend is conserved for each group of concepts even if the MAP absolute values are on different scales.

There are more fluctuations in the results for difficult concepts. These are also less frequent and each new positive sample added has a significant impact which may be negative if the sample, though positive, is not very representative.

For moderately difficult concepts, it seems that the "most uncertain" strategy is better than "most probable" one when the number of annotated samples exceeds 20% of the sample set. This suggests that a hybrid strategy like "most probable first then most uncertain" could do even better. For difficult concepts, it seems that the "most uncertain" strategy is better than "most probable" one when the number of annotated samples is below 20% of the sample set though this might be due to fluctuations.

It seems also that the random strategy does better than the other two for difficult concepts near the end of the sample set and that might not be due to fluctuations. Again, this is probably due to the difference in the selection of negative concepts: for difficult concepts, it may be better to choose samples that are within the less probable ones. That may be due to their sparseness and high variability.

Finding of positive and negative samples

Figure 5 displays the evolution of the number of positive samples found with the number of annotated samples for the three strategies, for all concepts and with the smallest step size. As expected, the "random" strategy finds positive samples in a quasi-linear way; the "most uncertain" strategy finds them faster and the "most probable" strategy even faster. The finding rates relatively to random near the beginning are of about 2.5:1 and 4:1 for "most uncertain" and "most probable" strategies respectively. These ratios probably depend significantly of the system performance but the relative performance of the strategies is clear either from the number of positive samples found or from the Mean Average Precision and we expect it to be representative.

We notice a strange behavior for the "most uncertain" curve near the end of the experiment: the number of positive is lower than expected and then it strongly increases. This is probably due to a small implementation mistake: instead of selecting samples with scores as close as possible to 0.5, the program selected samples with decreasing scores starting from 0.5 and then, if no more were available with increasing scores starting from 0.5. This makes little difference in the first few iterations (at least up to the middle of the sample set) since there are always lots of samples with scores just before and just after 0. Most probable Most uncertain Random Fig. 5. Evolution of the number of positive samples with the number of annotated samples for the three strategies the selection of negative samples until they are exhausted, the last positive samples being then included. We are currently running again the "most uncertain" strategy with the right selection criterion (scores as close as possible to 0.5) and the corresponding results will be included in the final version of the paper. We already observed that this has very little influence on the first half of the curves where most of the interesting observations are to be made (active learning strategies are of interest when only a fraction of the training set can be annotated).

The negative samples selected by the "most probable" strategy are more useful than those selected by the "most uncertain" strategy because they look more like positive samples. Negative samples that are far from the positive ones are usually not considered by the SVM classifiers and do not help. Therefore, the "most probable" strategy does not only select more positive samples, it also selects more helpful negative samples.

Effect of the step size

We tried the three strategies with three step sizes corresponding to 1/6th, 1/20th and 1/40th of the dataset size. We presented the previous results with the smallest step size since it is the most realistic. Figure 6 shows the evolution of system MAP with the number of annotated samples on the first half of the dataset for the "most probable" strategy for the three step size and for all concepts. As expected, smaller step sizes leads to a faster and stronger active learning effect. Similar results are obtained with the "most uncertain" and random strategies (not shown).

The effect of the step size seems to be larger within the first few iterations. Also, the training associated to the last iterations becomes longer and longer due to the increasing number of positive and negative samples. This suggests that an increasing step size strategy would optimize the gain relatively to both the number of annotation available and the cumulated training time.

CONCLUSION

We have compared active learning strategies for indexing concepts in video shots. Active learning was simulated using subsets of a fully annotated dataset instead of actually calling for user intervention. Training was done using the collaborative annotation of 39 concepts of the TRECVID 2005 campaign. Performance was measured on the 20 concepts selected for the TRECVID 2006 concept detection task. The simulation allowed exploring the effect of several parameters: the strategy, the annotated fraction of the dataset, the number of iterations and the relative difficulty of concepts.

Three strategies were compared. The first two respectively select the most probable and the most uncertain samples. The third one is a random choice. The "most probable" strategy is almost always the best one and it permits to get very close to the maximum performance while requesting the annotation of only one eighth of the whole dataset. The strategy depends upon the difficulty of the target concepts and the fraction of the dataset which is annotated. For instance, the "most uncertain" strategy is better for moderately difficult concepts and when a significant part of the dataset is annotated.

Current annotated corpora, TRECVID 2003 and 2005, and LSCOM, constitute very good resources but they are still insufficient for efficient system training. Their exhaustive annotation has been very useful for the current study and for the design and evaluation of many concept indexing systems. These annotated corpora will have to be further enriched and active learning techniques should be considered Fig. 6. Evolution of system MAP with the number of annotated samples for the "most probable" strategy for the three step size, all concepts in order to get as much useful information as possible from every paid annotation. These corpora can themselves be used for the cold start and the set of already developed systems could be used in a collaborative way for the implementation of the most efficient active learning strategies. Future work will be conducted to better characterize the optimal strategy. Other strategies can be investigated like "query by committee" if several system are accessible. A selection of negative samples based on a maximum variability could be considered instead of a random selection. Combination of several strategies should also be investigated.

Fig. 4 .

 4 Fig. 4. Evolution of system MAP with the number of annotated samples for the three strategies, difficult concepts


Keywords: Relation, extraction d'information, base de connaissances, expansion de requête

Les relations entre termes jouent toujours un rôle très important dans la représentation de contenu du texte. Ces relations qu'elles soient de nature statistique, syntaxique ou sémantique, leur information abordée reflète le contexte au niveau local ou global des termes et contribuent donc à la compréhension du texte. Dans le cadre de ce travail, nous proposons une méthode hybride d'extraction, de structuration et de filtration des relations multi types dans le texte. La base de connaissances extraite pourra éventuellement être appliquée à l'expansion de requête en vue d'améliorer la performance de recherche d'information. Nous avons également évalué lors d'une expérimentation les différentes relations extraites. Mot

I. INTRODUCTION

N ous partons du contexte général des Systèmes de Recherche d'Information (SRI): problème de recherche avec termes -mot clés. Les limitations des mots clés sont claires ; ils ne sont pas assez précis au niveau de description du contenu du texte ; Les documents pertinents ne partage pas toujours les mêmes mots clés avec ceux de la requête. De ce fait, les connaissances d'un plus haut niveau de compréhension du texte comme connaissances syntaxiques et sémantiques sont exploitées et intégrées dans le SRI, notamment par l'utilisation à l'indexation de syntagmes ou de terme structuré [START_REF] Arampatzis | Linguistically Motivated Information Retrieval, Encylopedia of Library and Information Science[END_REF], [START_REF] Chevallet | Proposition d'un modèle relationnel d'indexation syntagmatique:mise en oeuvre dans le système IOTA[END_REF] et pour expansion de requête [START_REF] Voorhees | Query expansion using lexical-semantic relations[END_REF].

Un système d'extraction d'information ou de connaissances est un système qui produit une représentation de l'information textuelle pertinente dans un domaine particulier et pour une application particulière. Les connaissances extraites doivent représenter le contenu des textes sous une forme compréhensive par l'ordinateur et riche en information. Cette base de connaissances extraite peut être utilisé dans les deux phrases principales d'un SRI. Premièrement, pour effectuer une indexation à vocabulaire contrôlé, les termes d'indexations sont alors plus complets et plus précis, ils permettent d'atteindre une meilleure performance. Deuxièmement, en consultant ce base de connaissances, les termes similaires avec ceux de la requête sont retrouvés et utilisés dans reformulation de la requête.

Notre méthode d'extraction de connaissances s'appuie concrètement sur l'extraction des termes significatifs et représentatifs du contenu informationnel du corpus et les relations entre les couples de termes.

II. TRAVAUX SIMILAIRES

Les travaux dans la littérature du domaine d'extraction de connaissances textuelles foisonnent d'idées et de techniques. On peut les grouper en trois approches principales :

A. Approche statistique Cette approche observe la régularité des termes dans un contexte déterminé d'une grande masse de collection de texte. Elle est basée sur hypothèse dans [START_REF] Van | Information Retrieval[END_REF] : « L'emploi de deux termes en cooccurrence est l'expression d'une relation sémantique entre eux ». Afin d'exploiter la relation entre les termes, de nombreuses mesures de similarité ont été utilisées dans la littérature statistique. L'avantage de cette approche est qu'elle est facile à mettre en oeuvre et indépendante du corpus. Parmi des travaux de cette approche, [START_REF] Grefenstette | Use of syntatic context to produce terms association list for text retrieval[END_REF] contribue au domaine de l'extraction de connaissances par une technologie d'extraction des contextes des mots à partir des corpus textuels pour produire la liste des mots reliés à n'importe quel mot apparu dans le corpus. Ces mots reliés utilisés dans l'expansion de requêtes donnent de meilleurs résultats que ceux obtenus par un seul caractère de cooccurrence. Cette technologie utilise une analyse syntaxique de surface sans aucune autre connaissance linguistique.

B. Approche linguistique

A l'inverse de l'approche statistique, l'approche linguistique n'observe pas la régularité des termes dans le corpus. Ce qui est important est les informations linguistiques exploitées à partir du texte. Autrement dit, cette approche vise à extraire les dépendances ou les relations entre les termes grâce aux phénomènes langagiers. Des travaux récents utilisent ces technologies:

• Exploitation des marqueurs linguistiques dont [START_REF] Nazarenko | Compréhension du langage naturel: le problème de la causalité[END_REF] est un travail profond en compréhension du langage naturelle. Elle exploite les marqueurs de causalité (par exemple : « à cause de », « parce que » …) afin d'extraire la relation causale pour l'intégrer dans le système de question-réponse KALIPSO. [START_REF] Soo-Guan | Automatic identification of causale relations in text and their use for improving precision in information retrieval[END_REF] est un travail similaire sur ce type de relation en s'appuyant en plus sur le rôle que joue cette relation dans les SRI. • Exploitation des patrons syntaxiques: travaux de [START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF] et [START_REF] Morin | Extraction de liens sémantiques entre termes à partir de corpus de textes techniques[END_REF]

C. Approche hybride

Les travaux récents se centrent sur la combinaison de l'approche statistique et linguistique, afin de profiter de l'avantage des deux approches. Cette approche hybride utilise souvent des données statistiques pour filtrer les données linguistiques. SEXTANT [START_REF] Grefenstette | Automatic thesaurus generation from raw text using knowledge-poor technique[END_REF] et IOTA [START_REF] Bruandet | Construction automatique d'une base de connaissances du domaine dans un système de recherche d'information[END_REF] sont les systèmes qui effectuent cette approche et montrent des résultats très encourageants. Plus récent, [START_REF] Hatem | Extraction et l'impact des connaissances sur les performances des systèmes de recherche d'information[END_REF]

H2: La relation sémantique (synonymie, hyponymie et causale) entre deux termes ne co-occurrent pas très souvent est aussi importante et doit être extraire. L'importance des termes dépend non seulement de leurs fréquences, de leurs quantités d'information mais aussi de leurs liens sémantiques avec les autres.

Nous proposons donc une approche hybride en fusionnant des associations entre les couples de termes extraits de manière statistique avec les relations sémantiques extraites par approche linguistique. Ex :

A. Chaîne de traitements d'extraction d'informations:

On a : Q sem (supression d'emploi) = Q sem (Dépendancesyntaxique) + Q sem (Causale) = δ + γ Q sem (emploi) = Q sem (Dépendance syntaxique) = δ Q sem (emploi) = Q sem (Causale) = γ

C. Filtrage des SN

Le nombre de termes extraits à partir d'un corpus volumineux est très important. De ce fait, il ne faut pas tous les conserver. On garde seulement ceux qui sont importants pour leur capacité à représenter le contenu du corpus. Cette capacité dépend non seulement de la fréquence et de la quantité d'information mais aussi de la qualité sémantique (Qsem) via leurs associations avec les autres. Qsem reflète la force sémantique d'un terme par apport à sa corrélation sémantique avec les autres termes. Le filtrage est donc définit par une fonction qui doit refléter cette dépendance multiple de la fréquence, la quantité d'information et de la qualité sémantique. Nous proposons la fonction de filtrage des SN : F(SN) = Freq(SN) x Qinf(SN) x Qsem(SN) Via un seul prédéfini expérimentalement, terme SN n'est gardé si F(SN) supérieur au seuil.

IV. EXPERIMENTATION

Dans un premier temps, nous avons effectué une expérimentation d'extraction des relations sémantiques et de filtrage du résultat obtenu. En utilisant simplement des patrons lexico-syntaxique prédéfinis, nous pouvons extraire du corpus des relations de synonymie, hyperonymie et causalité. Le corpus utilisé est le corpus « le Monde » de taille 150Mo de la campagne d'évaluation CLEF. -A cause de la structure complexe de la phrase : «Son arrière-grand-père a officié dans l'armée_française comme son grand-père, son père et ses trois beaux-frères » On extrait des relations bizarres: Du côté expérimental, nous avons effectué un travail d'extraction de relations sémantiques à l'aide de patrons lexico-syntaxique. Parmi les relations extraites, nous avons trouvé des informations intéressantes mais aussi des bruits dus à : l'ambiguïté du langage naturel, la structure complexe des phrases et les étiquettes incorrectes. Afin d'éliminer ces bruits, nous avons filtré les termes par leur fréquence et leur quantité d'information.

Relation

∑ ∈ = SN a a Cat Q SN Q )) ( inf( ) inf( Emploi Causale syntaxique Suppression d'emploi Chômage sem sem i 1 Q ( ) Q (Rel ) n i SN = = ∑
Le travail présenté peut être complété et étendu pour différentes applications. La plus importante est l'utilisation de cette base de connaissances dans l'expansion automatique de requête :

Filtrage 1

Filtrage 2 Freq >= 2 1<Qinf<7 1<Qinf<7

• Elargir le champ de la recherche : En ajoutant les termes qui relient sémantiquement ceux de la requête, en particulier les termes synonymes. Dans le cas d'une requête donnée par utilisateur si les termes ajoute ont un faible pouvoir de discrimination, les termes ajoutés plus discriminants permettrons une meilleure recherche.

• Focaliser le besoin d'information de l'utilisateur: La relation hyperonyme est très efficace dans la focalisation de l'information demandée. Dans ce cas si l'utilisateur ne précise pas assez son besoin d'information. Cela entraîne des bruits dans la recherche. Les termes proposés à l'utilisateur à l'aide de cette base de connaissances focaliseront donc la recherche. D'ailleurs, la base de connaissance peut également servir à d'autres tâches comme: présenter le contenu du corpus à l'utilisateur pour lui permettre de mieux percevoir le contenu effectif de l'ensemble des documents, de mieux exprimer son besoin d'information dans construction de la requête ; filtrer et classifier les documents du Web, etc.

Fig. 1 .

 1 Fig. 1. Chaîne de traitements d'extraction de connaissances

  Quant à elles, les informations statistiques ont un caractère global et indépendant du corpus de textes. Aussi, elles sont faciles à mettre en oeuvre, elles sont donc souvent utilisées pour filtrer les relations sémantiques et pour donner un poids sur l'importance d'une relation. A partir des apports conjoints entre informations sémantiques et statistiques, nous proposons une idée sur la coopération de ces deux types d'information dans l'extraction de relation de type syntaxique, statistique et sémantique, ainsi que dans la représentation du contenu du texte avec les termes et leurs relations extraites. Les relations statistiques sont filtrées par la combinaison de la statistique ou de la sémantique.

				vise à construire une base de
	connaissances grâce à une technologie de fouille de donnée,
	appelée règles d'association et grâce à une extraction des
	syntagmes nominaux.
	III. PROPOSITION
	L'approche hybride d'extraction de connaissances montre
	son efficacité dans l'augmentation de la performance de RI.
	D'ailleurs, les travaux en profondeur d'extraction d'un seul
	type de relation sémantique sont pertinents mais ces approches
	sont coûteuses et adaptées seulement à un certain type de
	requêtes. L'approche statistique n'est plus utilisée toute seule
	car elle est trop limitée [13]. En effet, les SN sont de bonnes
	représentations du texte. Les éventuelles relations entre SN
	extraites sont intéressantes à exploiter. Inspirés des
	constatations sur ces travaux récents, nous sommes intéressés
	aux apports bilatéraux entre les informations sémantiques et
	statistiques :
	• Apports	d'informations	sémantiques	aux
	informations statistiques : information linguistique
	représentée sous forme de relations sémantiques
	précise le sens d'association entre deux termes qui
	co-occurrent. Ces relations sémantiques sont plus
	compréhensibles et représentatives du contenu
	textuel que les statistiques.
	• Apports d'informations statistiques aux informations
	sémantiques : L'idée	est	basée	sur	les	deux
	hypothèses suivantes:

H1: Si deux termes co-occurrent souvent, et s'ils sont reliés au moins une fois par un type de relation sémantique donné, alors toutes ses relations de cooccurrences sont de ce type.

Structuration de connaissances

  Fig. 2. Exemple de fusion des graphes de termes6) Le filtrage des termesPour éliminer les termes qui ne sont pas importants, on utilise un seuil de filtrage. Les termes d'une valeur de filtrage inférieure au seuil prédéfini sont éliminés. Le seuil est définit expérimentalement afin d'obtenir le meilleur taux de précision/rappel. Le résultat du travail d'extraction de connaissances est représenté sous la forme d'une liste de termes avec leurs relations, qui doivent être présentées aux utilisateurs tel qu'ils puissent les consulter selon différents critères et fournir les suggestions lors de la phrase d'interrogation pour faciliter ou augmenter la qualité de la recherche. C'est la raison pour laquelle nous avons besoin de la structuration des connaissances extraites. Avec une approche fusion de l'information statistique, syntaxique et sémantique, la structuration doit refléter ces trois informations pour pouvoir les consulter de façon flexible. Nous adoptons la structuration en réseau de dépendance syntaxique (tête et expansion) en ajoutant les associations statistiques et sémantiques. Notre hypothèse de structuration est :Les SN qui partagent la même tête, co-occurrent souvent ou sont reliés ensemble par une des relations sémantiques (Synonyme, hyperonyme, causale) représentent le même thème.Cette structuration permet à la fois de situer sur les relations à l'intérieur d'un SN (relations entre expansions), ainsi que relations à l'extérieur des SN. L'objectif est de récupérer en même temps dépendance syntaxique, statistique et sémantique pour fournir une vue cohérence sur le contenue de corpus.La structuration des SN en tête et expansion permet de mettre en évidence non seulement la dépendance syntaxique entreSN mais aussi la relation hyponymie entre un SN et ses variations (Ex : système, système d'information, système d'information multimédia) et co-hyponymie entre SN qui partage la même tête (Ex: « Système automatique », « système informatique ») Cette structuration en tête et expansion se base sur des patrons syntaxiques. Par exemple: est la qualité sémantique que le SN apporte. Nous proposons cette mesure en supposant que les relations sémantiques sont les connaissances les plus fines et les plus fortes au sens sémantique. Dans la phase d'extraction du contenu textuel, on exploite au fur à mesure toutes les informations possibles afin de trouver les relations. Lorsque l'on a trouvé une relation, nous pensons qu'il faut la prendre en compte dans l'évaluation de l'importance des termes qui sont reliées par cette relation. Nous basons sur l'hypothèse que : la qualité sémantique des relations sémantiques est beaucoup plus forte que celle de relation syntaxique et statistique. Cela reflète l'importance des termes qui sont reliés par une relation sémantique. Plus un terme possède des relations sémantiques, plus il obtient une forte qualité sémantique. De ce fait, nous définissons Q sem d'un terme SN par rapport aux relations auxquelles il est relié. Rel i est le type de relation qui relie terme T avec un autre terme. Q sem (Rel i ) est une valeur prédéfinie pour évaluer la force sémantique de la relation Rel i On définit une valeur γ > 1 pour chaque relation d'un terme avec une autre par relation synonyme, hyperonyme ou causale, et γ >δ >1 pour exprimer la qualité sémantique des termes reliés avec les autres par dépendance syntaxique ou statistique.

	On utilise un module d'extraction de SN de IOTA pour ils n'apparaissent pas aussi souvent dans corpus que les
	réaliser cette tâche. termes simples. Pour équilibrer l'importance des SN par
	3) Calcul de fréquence et de Cooccurrence entre termes : rapport aux termes simples, la quantité d'information a pour
	A cette étape, nous proposons de calcul la cooccurrence but évaluer l'importance de l'information qu'apporte un SN :
	(terme, terme) par une variation de la formule Cosinus [13]
	d'origine dans [14].
	4) Extraction de relations sémantiques: Relation Ou Cat(a) : Catégorie grammaticale de chaque mot qui
	synonyme, hyponyme et causale sont extraites grâce aux forme le SN (Substantif, adjectif,…)
	patrons lexico_syntaxique : Qinf(Cat(a)) : Valeur prédéfinie pour chaque catégorie
	Ex : Patron lexico_syntaxique : SN1 comme LISTE (SN2, grammaticale. Plus la catégorie est porteuse d'information
	SN3,…) plus cette valeur est grande. Dans ce cas, les substantifs ont la
	Notre objectif n'est pas d'extraire des relations avec tous valeur plus élevé tandis que les prépositions, conjonctions et
	les patrons lexico-syntaxique possibles, mais avec seulement articles ont une quantité d'information nulle.
	quelques patrons principaux pour ensuite, fusionner avec les On prédéfinit heuristiquement la valeur α pour exprimer la
	données statistiques et enfin filtrer, évaluer la base de quantité d'information de la catégorie subjonctifs et β pour les
	connaissances finales. catégories adjectif, verbe à l'infinitif, participe passé et		Corpus
	5) Fusion des deux graphes des termes adverbe avec α >> β. Nous proposons d'ajouter des nouveaux termes et relations, Ex : SN = nouveau système d'information	Parseur
	ou renommer les relations au nom des relations sémantiques a Qinf(SN)= inf(Cat(nouveau)) + Qinf(Cat(système)) priori si elles coïncident. + Qinf(Cat(information))		Collection étiquetée
	Exemple de fusion entre le graphe des termes et leurs = Qinf(Cat(Adjectif)) + Qinf(Cat(Substantif)) associations statistiques/syntaxique avec celui des termes et + Qinf(Cat(Substantif))	Extraire SN
	leurs relations sémantiques : = β + 2α Société Q	Chômage	Collection étiquetée et marquée des SN
			Causale	Calculer		Extraire relations
	Emploi	Chômage		co-occurrence		sémantiques
		Suppression d'emploi
	Syntaxique		Synonymie	Termes et		Termes et leurs
				leurs associations		relations
	Suppression d'emploi	Licenciement	statistiques	Fusion	sémantiques
				Filtrer
		Société		Patrons	Tête	Expansion
				syntaxiques	Base de connaissances
				SUBC1 SUBC2	finale SUBC1	SUBC2
		Emploi	Chômage	SUBC ADJQ ADJQ SUBC	SUBC SUBC	ADJQ ADJQ
	Syntaxique	Causale	1) Etiquetage SUBC1 PREP SUBC2	SUBC1	SUBC2
				A cette étape, une technique de traitement automatique de Tab.1. Exemple des patrons syntaxiques de SN
		Suppression d'emploi	langage naturel est appliquée pour donner une étiquette de
				catégorie grammaticale pour chaque unité linguistique dans le Nous adoptons la structuration des SN dans [12] et en
			Synonymie	texte. Nous utilisons un parseur pour cette tâche. Ex : « SystèmeSUBC dePREP informationSUBC estVBCJ ajoutons une mesure de qualité sémantique. Un SN est donc définit comme :
			Licenciement	unARTD nouveauADJQ domaineSUBC .PNTF » SN : [T, Freq, Qinf, Q sem ]
				2) Extraction de SN à l'aide de patrons syntaxiques T : la tête de SN
				Un patron syntaxique est une règle sur l'ordre
				d'enchaînement des catégories grammaticales formées un SN.
				Ex : ADJQ SUBC Qinf : La quantité d'information
				« Premier ministre, grande école », etc. Cette mesure a pour but de résoudre le problème de basse
				SUBC PREP SUBC fréquence des termes complexes. Même si les termes
				« job d'été », « guerre en Irak », etc. complexes sont de bonnes représentations du contenu textuel,

B.

Ex : Système d'information => Tête : Système Fréq : La fréquence dans le corpus entier. sem

  Pour évaluer nos résultat d'extraction de relations, à cause de la voluminosité du résultat et la nature sémantique des relations, dans ce premiers temps, nous avons mesuré le taux précision en comptant manuellement le nombre de relation correcte parmi une centaine des relations extraites sélectionner au hasard. Même si le taux de précision du résultat n'est pas encore élevé (moyenne de 60%), des informations intéressantes on été trouvés par une analyse simple du texte. Afin d'améliorer la précision, nous avons filtré les termes par apport à leur fréquence et leur quantité d'information. Le résultat obtenu après dans le tableau montre une petite augmentation de précision. Pourtant, sur un petit corpus Le Monde (150M), le filtrage des SN base sur leurs fréquences n'est pas efficace car presque tous les termes ont la fréquence égale 1. Dans le cadre de ce travail, nous avons proposé une méthode d'extraction de connaissances et un filtrage qui fusionne à la fois l'approche linguistique et statistique. Pour l'approche statistique, un calcul de la fréquence de termes et leurs occurrences est effectué. L'approche linguistique est effectuée à partir d'une analyse de surface du texte afin d'obtenir des syntagmes nominaux et d'autre part grâce à l'exploitation de patrons lexico-syntaxique afin de repérer les relations sémantiques entre les termes (mot simple ou syntagmes nominaux). Ces deux types d'informations sur les termes sont fusionnés et filtrés à l'aide d'informations de nature statistique, syntaxique ainsi sémantique. La mesure de la qualité sémantique permet d'évaluer l'importance d'un terme et sa contribution à la représentation du contenu du corpus. Un filtrage des termes basé sur ces trois types d'informations a été proposé pour l'adapter à ce contexte.

	armée_français -COMME-grand-père
	armée_français -COMME-père armée_français -COMME-beau-frère • A cause d'ambiguïté du sens : «Rapide, silencieux, stable, la navette se présente en fait comme un train tiré de sorte de caisson container dans lequel peut prendre place environ 90 voitures. » On extrait : fait -COMME-train	Nombre des relations extraites 2331 67 1890 Tab.4. Statistique du taux de précision des relations extraites avant et après Précision Non filter 0.6 Filtre 1 0.58 Filtre 2 0.62 les filtrages
	Il faut d'ailleurs reconnaître l'expression avec « en fait »
	pour éliminer ce bruit.			Grâce au filtre 2, le taux de précision des relations extraites
	• A cause d'étiquetage incorrect		a été augmenté de +2%. Pourtant, cette évaluation de
	«Un autre roman d'amour nous est rapporté dans les trente	précision n'est correcte que pour les premières centaines des
	derniers pages de livre et produitSUBC comme un	relations. Un jugement sur le total des relations extraites est
	coup_de_théâtre »			donc prévu.	Les éventuelles améliorations raisonnables du
	On	extrait :	produitSUBC	-COMME-	parseur de langue française sur un plus large corpus et de la
	coupSUBC_dePREP_théâtreSUBC		fonction de filtrage pourraient donner un meilleur résultat.
	La méthode d'extraction des relations sémantiques donne
	des résultats intéressants mais aussi des limites comme nous		V. CONCLUSION
	venons de montrer. Tab.3.Les filtres des termes		Nous avons proposé une méthode d'extraction de relations en fusionnant les relations statistiques, syntaxiques et sémantiques. Une structuration des connaissances extraites avec les trois sources d'informations différentes donne une vue générale d'un terme et de son contexte. L'aspect statistique avec la fréquence, l'aspect syntaxique avec la structure tête -expansion, la mesure de la quantité d'information et l'aspect sémantique avec les relations sémantiques.
		Evaluation de relations d'hyperonymie extraites
		0.63
		0.62
	Précision	0.58 0.59 0.6 0.61		Non filtré Filtre 1 Filtre 2
		0.57
		0.56
			1
			Filtre

Fig.

[START_REF] Van | Information Retrieval[END_REF]

. Statistique du taux de la précision avant et après le filtrage


Stéphane Ayache

Georges Quénot

Jérôme Gensel

Shin ' Ichi Satoh

Using Topic Concepts For Semantic Video Shots Classification

Automatic semantic classification of video databases is very useful for users searching and browsing but it is a very challenging research problem as well. Combination of visual and text modalities is one of the key issues to bridge the semantic gap between signal and semantic. In this paper, we propose to enhance the classification of highlevel concepts using intermediate topic concepts and study various fusion strategies to combine topic concepts with visual features in order to outperform unimodal classifiers. We have conducted several experiments on the TRECVID'05 collection and show here that several intermediate topic classifiers can bridge parts of the semantic gap and help to detect high-level concepts.

Introduction

In order to retrieve and browse videos into huge databases, needs for indexing understandable concepts are rapidly growing. The extraction of such concepts is one of the main objectives of the semantic video indexing community. Although using and combining visual and text modalities are expected to improve the performance of high-level concepts classification, new issues arise. Usual approaches, merge directly visual and text features into a single flat classifier. However, even with a clever choice of relevant features, the correlation between such low-level features and high-level concepts is still weak. Such approaches assume that there exists a correlation between uttered speech and high-level concepts to classify high-level features [START_REF] Ayache | Video shot classification using lexical context[END_REF][START_REF] Nock | Issues in speech-based retrieval of video[END_REF][START_REF] Snoek | Early versus Late Fusion in Semantic Video Analysis[END_REF]. But, recent TRECVID evaluations 1 have shown the limitations of such approaches: a single classifier cannot bridge this large semantic gap. Furthermore, concerning visual modality, promising results have been obtained by integrating context information based on the merging of intermediate visual concepts [START_REF] Snoek | The MediaMill TRECVID 2004 Semantic Video Search Engine[END_REF][START_REF] Iyengar | Discriminative model fusion for semantic concept detection and annotation in video[END_REF][START_REF] Naphade | On supervision and statistical learning for semantic multimedia analysis[END_REF][START_REF] Ayache | Context-based conceptual image indexing[END_REF]. Such a stacked classifier [START_REF] Wolpert | Stacked Generalization[END_REF] learns implicit relations between intermediate concepts to derive high-level concepts.

In this study, we extend the context based framework we proposed in [START_REF] Ayache | Context-based conceptual image indexing[END_REF] by exploiting intermediate concepts extracted from textual modality. In order to learn relations between uttered speech and visual content, we propose to classify video shots with several intermediate topic categories, then to combine them for high-level concepts detection. We show that such topic categories provide useful semantic context when combined with visual information. The main idea is that several intermediate classifiers can bridge small parts of the semantic gap in order to improve the detection of high-level concepts. Similarly to the early and late fusion schemes [START_REF] Snoek | Early versus Late Fusion in Semantic Video Analysis[END_REF], we investigate the combination of intermediate concepts by means of one and two-level fusions. We show the improvement brought by the use of topic concepts for video shots classification through several experiments performed on TRECVID'05 corpora. This paper is structured as follows: in section 2, we argue for the use of intermediate concepts; in section 3, we describe our framework based on intermediate concepts classification; in section 4, we describe and comment some conducted experiments; we finally draw some conclusions in section 5.

The need for intermediate and understandable concepts

Video documents contain visual, textual and audio cues (where text is mainly extracted from speech transcription). Thus, high-level concepts can be extracted from various modalities and can, on the one hand, exploit contexts from other cues while, on the other hand, provide context to them. We have shown that combining intermediate visual concepts offers rich sources of contexts and increase the derivation of high-level concepts [START_REF] Ayache | Context-based conceptual image indexing[END_REF][START_REF] Ayache | CLIPS-LSR-NII experiments at TRECVID 2005[END_REF].

Furthermore, the extraction of understandable concepts is extremely useful for video browsing, since users can use them for expressing non-trivial information needs. Many approaches extract mid-level features by using dimensionality reduction algorithms such as PCA or LSA [START_REF] Murphy | Object detection and localization using local and global features. Sicily Workshop on Object Recognition[END_REF][START_REF] Garg | Fusion of Global and Local Information for Object Detection[END_REF][START_REF] Lisin | Combining Local and Global Image Features for Object Class Recognition[END_REF], yielding discriminant features which fit especially well the learned data. However, such eigen-features are hard to interpret and, hence, unusable for other multimedia tasks. Thus, in order to enrich our basis of concepts, we focus on the use of supervised classifiers in order to extract usable intermediate concepts.

High-level concepts

High-level concepts are input devices which allow users to express their information need for video browsing or search tasks. They can be described in terms of other concepts and are independent of the modality in which they are naturally expressed [START_REF] Iyengar | Semantic indexing of multimediq using audio, text and visual cues[END_REF]. In this paper, we focus on the 10 high-level concepts defined in TRECVID'05.

Visual concepts

We extract visual local concepts from image patches in each keyframe. Intermediate visual concepts provide spatial and semantic knowledge to higher level classifiers. We use a set of 15 visual concepts ('vegetation', 'sky', 'skin/face' ...) selected from the LSCOM ontology [START_REF]LSCOM Lexicon Definitions and Annotations Version 1.0. DTO Challenge Workshop on Large Scale Concept Ontology for Multimedia[END_REF] which can be extracted from patches and are discriminative enough to help the classification of higher level concept.

Topic concepts

We propose to extract a set of topic concepts from speech transcription [START_REF] Gauvain | The LIMSI Broadcast News Transcription System[END_REF], then to classify shots according to these intermediate concepts. We use 25 categories of the TREC Reuters collection [START_REF] Lewis | RCV1: A New Benchmark Collection for Text Categorization Research[END_REF] to classify each speech segment. The advantages of extracting such concepts from the Reuters collection are that they cover a large panel of news topics like the TRECVID collection, they are obviously human understandable, and thus they can be used for video search tasks. Examples of such topics are 'Economics', 'Disasters', 'Sports' and 'Weather'. Reuters collection contains about 800000 text news items in the years 1996 and 1997. They are classified among 103 topics, hierarchically structured. We used the 25 top level categories as topic concepts.

Video indexing framework for high-level concepts classification

In our previous work, we have proposed a context-based approach for automatic image annotation based on intermediate local concepts [START_REF] Ayache | Context-based conceptual image indexing[END_REF]. Using stacking technique, a multi-layer SVM classifier learns topological and semantic contexts from image content. In the present work, topic concepts and visual global features are expected to enhance the discriminating power of semantic context. We also investigate the use of fusion classifiers in order to merge such intermediate concepts while exploiting the 2 following kinds of context:

-Topologic context learns the spatial distribution of a visual local concept and assign a score to the whole image. The idea behind the use of topologic context is that the confidence (or score) of an image performs better by taking into account the confidences obtained for each patch in the image for the same concept. -Semantic context exploits the semantic relations between concepts based on co-occurrences learned by the classifier. The idea is that the confidence of a single concept is computed more accurately by taking into account the confidences obtained for other concepts co-occuring in the same image.

Additionally, we have shown on the TRECVID'05 evaluation that combining both contexts increases the accuracy of high-level concepts classification. By merging all the visual concept scores, a classifier learns Topologic-Semantic context associated with the local concepts and the high-level concepts. The classifier can activate or inhibit high-level concepts based on intermediate scores and learned relations [START_REF] Ayache | CLIPS-LSR-NII experiments at TRECVID 2005[END_REF].

Figure 1 shows a general view of our extended framework. At the intermediate layer, the Local classifier assigns visual local concept scores to each patch of keyframes, while the Topic classifier assigns topic concept scores to each speech segment. Then, the fusion function derives high-level concept scores at shot level, based on both the output of intermediate classifiers and the use of predefined contexts.

Visual Concepts classification

We classify each keyframe using intermediate local concepts and global low-level features. One local concept corresponds to the score of one patch according to a visual concept. In order to derive high-level concepts, we merge local concepts using Topologic-Semantic context. Additionally, the use of global low-level features is expected to enhance local only classification.

Visual low-level extraction

As we want to handle the topologic context, we need to compute low-level features for parts of the image, as well as for the whole image. In order to compute local features, many approaches have been proposed. Since the automatic and a priori segmented regions are usually too far from the semantic meaning of image, we have decided to split images into patches. By doing so, we should be far from semantic, but with such granularity one patch is more likely to contain one single concept.

-Local features: We first split the image into overlapping patches. In our experiments, we use P = 20×13 patches of 32×32 pixels. For each patch, we compute 9 color momentums (3 means + 6 co-variances), 24 Gabor wavelets for texture (3 scales x 8 orientations), and the 2 coordinates of the patches. -Global features: More information can be extracted from a whole image than from a single patch. We extract 4 × 4 × 4 three-dimensional histograms for color features based on RGB channels, Gabor wavelets for texture (5 scales × 8 orientations), and the first two momentums of motion vectors obtained from optical flow.

Topic Concepts classification

Based on speech transcription data, Topic classification relies on text retrieval techniques. The most common and widely used approach is the Vector Space Model [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF], which has been successfully used in the traditional IR field. The model considers a vector space in which both documents and queries are represented by vectors of weighted terms calculated by the TF.IDF formula. For the classification task, a Rocchio classifier consists in first creating a prototype vector for each class, then assigning a test document to the nearest prototype using the Cosine similarity.

In TRECVID transcriptions, one speech segment corresponds to one speaking turn. We build the prototype vectors of each topic category on Reuters corpora and apply the Rocchio classification on each speech segment. Such granularity is expected to provide robustness in terms of covered concepts, as each speaking turn should be related to a single topic. Our assumption is that the statistical distributions of Reuters corpora and TRECVID transcriptions are similar enough to obtain relevant results. Finally, we derive high-level concepts by merging outputs of Topic concept classifiers.

Text analysis

We construct a vector representation for each speech segment by applying stoplist and stemming. Also, in order to avoid noisy classification, we reduce the number of input terms. While the whole collection contains more than 250000 terms, we have experimentally found that considering the top 2500 frequently occurring terms gives the better classification results on Reuters collection.

Combining intermediate features

Combining intermediate concepts aims at deriving high-level concepts from several unimodal intermediate concepts. Such strategy leads to a multimodal shot classifier. In order to unify outputs of intermediate classifiers, we report the topic concept scores of speech segments to each keyframe. A given keyframe, corresponding to the time point T, is associated with the speech-segment delimited by the time bounds TB and TE so that TB ≤ T ≤ TE.

We identify two possibilities to merge intermediate features, depending on the abstraction level considered. Similarly to the early and late fusion schemes defined in [START_REF] Snoek | Early versus Late Fusion in Semantic Video Analysis[END_REF], we use either a one level or a two level fusion schemes, described as follows:

One-level fusion: In a one-level fusion process, intermediate features or concepts are concatenated into a single flat classifier, as in an early fusion scheme [START_REF] Snoek | Early versus Late Fusion in Semantic Video Analysis[END_REF]. Such a scheme takes advantage of the use of the semantic-topologic context from visual local concepts, and semantic context from topic concepts and visual global features. However, it is constrained by the curse of dimensionality problem. Also, the small numbers of topic concepts and global features compared to the huge amount of local concepts can be problematic: the final score might strongly depend upon the local concepts.

Two-level fusion:

In a two-level fusion scheme, we classify high-level concepts from each modalities separately at a first level of fusion. Then, we merge the obtained outputs into a second layer classifier. We investigate the following possible combinations. Classifying each high-level concept with intermediate classifiers, then merging outputs into a second level classifier is equivalent to the late fusion defined in [START_REF] Snoek | Early versus Late Fusion in Semantic Video Analysis[END_REF]. Using more than two kinds of intermediate classifiers, we can also combine pairwise intermediate classifiers separately, then combine given scores in a higher classifier. For instance, we can first merge and classify global features with topic concepts, then combine the given score with outputs of local concept classifiers in a higher classifier. An other possibility is to merge separately local concepts with global features and local concepts with topic concepts, then to combine the given scores in a higher level classifier. Advantages of such schemes are numerous: the second layer fusion classifier avoids the problem of unbalanced inputs, and keep both topologic and semantic contexts at several abstraction levels.

We compute high-level concept scores for each keyframe using the predefined fusion classifiers. Then, in order to set a score to video shots, we keep the keyframe which has the maximum score, according to the idea that a concept occurs in a shot if one of the sub-shots contains this concept.

Experiments

We evaluate the use of visual and topic concepts and their combination for highlevel concepts detection in the conditions of the TRECVID'05 evaluation. We show the 10 high-level concepts classification results evaluated with the trec eval tool using the provided ground truth, and compare our results with the median over all participants. We have used a subset of the training set in order to exploit the speech transcription of the samples. As the quality of TRECVID'05 transcription is quite noisy due to both transcription and translation from Chinese and Arabic videos, some video shots do not have any corresponding speech transcription. In order to compare visual only runs with topic concept based runs, we have trained all classifiers using only keyframes whose transcript is not empty. In average, we have used about 300 positives samples and twice as many negative samples. It has been shown in [START_REF] Lewis | RCV1: A New Benchmark Collection for Text Categorization Research[END_REF] that SVM outperforms a Rocchio classifier on text classification. In this experiment, we first show the improvement brought by the topic concepts based classification by comparing with a SVM text classifier based on the uttered speech occurring in a shot after same text analysis as topic classifiers. Then, we give some evidence of the relevance of using topic concepts, by showing the improvement of unimodal runs when combined with the topic concepts. In a second step, we compare one-level fusion with two-level fusion for combining intermediate concepts. We have implemented several twolevel fusion schemes to merge the output of intermediate classifiers. Particularly, we show that pairwise combinations schemes can increase high-level concepts classification. We used a SVM classifier with RBF kernels as it has proved good performance in many fields, especially in multimedia classification. LibSVM [START_REF] Chang | a library for support vector machines[END_REF] implementation is easy to use and provides probabilistic classification scores as well as efficient cross validation tool. We have selected the best combination of parameters C and Gamma out of 110, using the provided grid search tool.

Figure 2 shows the Mean Average Precision (MAP) results of the conducted experiments. We compare our results with the TRECVID'05 median result. 'Text', 'Topic' 'Global' and 'Local' experiments refers to the use of unimodal classifiers.

On fusion experiments, the sign '-' refers to a one-level fusion and the sign '+' refers to the second-level fusion. For instance, in the run 'lo-to' we have concatenated inputs of the 'Local' and 'Topic' runs, and for the 'lo-to + gl-to' run, we have merged in a second level fusion scheme the classification results of 'lo-to' and 'gl-to' runs.

Topic concepts based classification performs much better than text based classifier, the gain obtained by topic concepts based classification is obvious. It means that despite the poor quality of speech transcription, intermediate topic concepts are useful to reduce the semantic gap between uttered speech and high-level concepts. Each intermediate topic classifier provides significant semantic information despite the differences between Reuters and TRECVID transcripts corpora. It is interesting to notice that the 'Sports' concept is also a Reuters category and has the best MAP value for the Topic concepts based classification.

For 'Global' run, we have directly classified high-level concepts using their corresponding global low level features. When combined with topic concepts, the average MAP increases by 30%, and up to 100% on Sports high-level concept. Also, some high-level concepts which have poor topic based classification MAP cannot benefit from the combination with topic concepts.

The use of the topologic-semantic context in local concepts based classification improves clearly the performance over the global based classifier. However, we observe a non significant gain when combined with topic concepts. This can be explained by the huge numbers of 'Local' inputs compared with the few numbers of 'Topic' inputs. Since we have used RBF kernel, the topic concepts inputs have a very small impact on the euclidian distance between two examples. A solution to avoid such unbalanced inputs could be to reduce the numbers of local concepts inputs using a feature selection algorithm before merging with the topic concepts. Despite this observation, we notice that we obtain better results by combining Local with Topic concepts than combining Local concepts with Global features.

We have conducted several experiments to combine 'Topic' concepts with 'Local' and 'Global' features. Where 'Local' only classification performs very well for some "visual" high-level concepts (Mountain, Waterscape), we can observe an improvement using fusion based runs for most of high-level concepts. The runs 'lo-go-to' and 'lo + go + to', which correspond respectively to the early and late fusion schemes, provide roughly similar results and do not outperform visual local classifier. This is probably due to the relative good performance of 'Local' run compared to other runs.

We have obtained the most significant results using two-level fusion when combining separately topic concepts with local and global features in the first fusion layer. In this case, the duplication of topic concepts at the first level fusion performs better by 10% than other fusion schemes. With such a scheme, topic concepts integrate useful context to visual features and achieve significant improvement, compared to unimodal classifiers, for most of high-level concepts.

Conclusion

In this paper, we investigate the use of topic concepts on a generic framework for high-level concepts video shots classification. We show that topic concepts based classification performs much better than a single text classifier to classify high-level concepts. In addition, we show that combined with visual cues, topic concepts can improve shots classification despite the poor quality of speech transcriptions. However, in some case, the 'Local' unimodal classifier does better than other fusion strategies. This could be due to the huge numbers of 'Local' inputs compared to the few numbers of 'Topic' inputs. The RBF kernel used in the presented experiments was not able to handle such unbalanced inputs.

Furthermore, regarding to the 'Sports' classification performance, the choice of topic categories seems to have a direct impact on the high-level concepts classification. Therefore, in future work, we intend to improve the topic based classification by carefully selecting the topic categories and also by appropriately normalizing the texts of Reuters and TRECVID collections. It should be also interesting to evaluate our approach on the TRECVID 2003 and 2004 collections which have better quality transcriptions.

Fig. 1 .

 1 Fig. 1. Extended framework. LF and GF are numbers of Local and Global Low-level Features, P is the number of Patches, LC denotes the number of Visual Local concepts, HC denotes the number of high-level concepts, N is the number of inputs terms and TC the number of Topic Concepts.

Fig. 2 .

 2 Fig. 2. Mean Average Precision of the 10 high-level concepts of TRECVID'05

TREC Video Retrieval Evaluation: http://www-nlpir.nist.gov/projects/trecvid/


Stéphane Ayache

Georges Quénot

Shin ' Ichi Satoh

CONTEXT-BASED CONCEPTUAL IMAGE INDEXING

Automatic semantic classification of image databases is very useful for users searching and browsing, but it is at the same time a very challenging research problem as well. Local features based image classification is one of the key issues to bridge the semantic gap in order to detect concepts. This paper proposes a framework for incorporating contextual information into the concept detection process. The proposed method combines local and global classifiers with stacking, using SVM. We studied the impact of topologic and semantic contexts in concept detection performance and proposed solutions to handle the large amount of dimensions involved in classified data. We conducted experiments on TRECVID'04 subset with 48104 images and 5 concepts. We found that the use of context yields a significant improvement both for the topologic and semantic contexts.

INTRODUCTION

In order to retrieve images from huge digital databases, users cannot specify their needs with low-level features, but with concepts which are much more understandable. New issues in Content-Based Image Indexing (CBII) field are arising for the reduction of this semantic gap. In order to improve concept detection, many approaches take into account the context. To do so, some approaches fuse local and global descriptors [? ? ] combined using boosted classifiers [? ].

Other define context as spatial relationships between objects within an image [? ? ? ] using probabilistic frameworks. However, in order to deal with a large amount of local descriptors and simplify computation, such approaches first detect points of interest and then assume them independent.

In their work, [? ? ? ] handle semantic relationships [? ] between concepts using Stacked Classifiers [? ? ]. They first classify intermediate concepts, and learn their relationships in the context of a higher level concept by a second-level classifier. In TRECVID'04 experiments, [? ] used a basis of 22 intermediate concepts. By adding the 10 TRECVID's concepts, they learned semantic context of 32 concepts with Stacking. * Georges Quénot is researcher at CNRS In this study, we propose and evaluate a new framework for incorporating contextual information into image indexing process. We assume that both semantic and local contexts can increase the accuracy of a classifier. We incorporate both local and inter-concept information in the decision process, in order to increase accuracy of classification. However, it is difficult to merge many information while managing the curse of dimensionality problem. Thus, we study an "hybrid" approach which tries to merge contextual information with few data. We evaluate and validate our approach on five high-level features of TRECVID 2003 and 2004 Corpus.

MULTI-LEVEL FRAMEWORK

Our framework uses several local and global classifiers and arrange them into networks, using stacking, in order to catch contextual information. The idea is that the correlation between the input (low-level features) and the output (concepts) is too weak to be efficiently recovered by a single "flat" classifier even if the low-level features have been carefully chosen. Combining classifiers in a multi-level framework allows extraction of intermediate-level data from low-level features and other classifiers. Detection of concepts from these intermediate-level data is expected to improve the overall performance (both correctness and computation time) of the system. Figure ?? shows an overall architecture of our framework, and how classifiers are combined.

Classifiers from each level bridge a small part of the semantic gap and are expected to do it well because the correlation between their inputs and their outputs is expected to be better than the correlation between the inputs and the outputs of a single classifier that would bridge alone the whole semantic gap. Also, not only the levels are cascaded but many intermediate data are computed in parallel and the outputs of all of them are combined as inputs to the next level. This framework is able to derive high-level concepts from other intermediate concepts, but also reinforce intermediate concepts detection. Experiments of the present work will focus of the second point.

The objective of the present work is to validate our assumptions and to quantify the benefits that can be obtained from Figure ?? shows the multi-layer framework, the first layer (Patch Classifier, on the left) computes scores of concepts detection at patch-level. Then higher level layers assign scores for the whole images. The first layer is basically the only one that handles low-level features. The higher layers handle output of lower level layers i.e. intermediate data.

LOW-LEVEL FEATURES EXTRACTION

As we want to handle topologic context, we need to compute low-level features for parts of the image. In order to compute local features, many approaches have been proposed. While automatic and a priori segmented regions are too far from semantic meaning of image, we decided to split images into patches. By doing so, we should be very far from semantic, but with such granularity one patch is more likely to contain a single concept.

The low-level features extractor's process first splits image into overlapped patches. Basically, we used 260 overlapped patches of 32 × 32 pixels (in 352 × 240 images). And then, extracts 9 moments color (3 means + 6 co-variances), Gabor wavelets for texture (3 scales × 8 orientations), and coordinates of patches.

Those choices have been made for a baseline system. The main goal here is to explore the use of context for concept indexing. We want to study and evaluate various ways of doing it by combining classifiers into networks. In further work, we plan to enrich and optimize the set and characteristics of low level features, especially for video content indexing. Currently, we expect to obtain representative results from the current set of low-level features.

USE OF THE TOPOLOGIC CONTEXT

The idea behind the use of topologic context is that the confidence (or score) for a single patch (and for the whole image) could be computed more accurately by taking into account the confidences obtained for other patches in the image for the same concept.

We studied three network organizations to evaluate the effect of using the topologic context in concept detection at the image level. The first one is a baseline in which no context (either topologic or semantic) is used. The second one uses the topologic context in a flat (single layer) way while the third uses the topologic context in a serial (two layers) way.

In this part, we consider concepts independently one from another. Concept classifiers are trained independently from each other whatever their levels. In the following, N will be the number of concepts considered, P will be the number of patches used (260 in our experiments) and F will be the number of low-level feature vectors components (35 in our experiments).

Baseline, no context, one level (1)

In order to evaluate the patch level alone, we define an image score based on the patch confidence values. To do so, we simply compute the average of all of the patch confidence scores. This baseline is very basic it does not take into account any spatial or semantic context. We have here N classifiers, each with F inputs and 1 output. Each of them is callled P times on a given image and the P output values are averaged.

Topologic context, flat, one level (2)

The "flat" network directly computes scores at the image level from feature vectors. We have here N classifiers, each with F × P inputs and 1 output. Each of them is callled only once on a given image and the single output value is taken as the image score. This network organization is not very scalable and requires a lot of training data and training times because of the large number of inputs of the classifiers.

Topologic context, serial, two levels (3)

The "serial" network is similar to the baseline one. The difference is that the scores at the image level are computed by a second level of classifiers instead of averaging. We have here N level 1 classifiers, each with F inputs and 1 output and N level 2 classifiers, each with P inputs and 1 output. Each level 1 classifier is called P times on a given image and its P output values are passed to the corresponding level 2 classifier which is callled only once. Topologic context is taken into account by concatenating patches confidence value in a vector.

USE OF TOPOLOGIC AND SEMANTIC CONTEXTS

The idea behind the use of semantic context is that the confidence (or score) for a single concept could be computed more accurately by taking into account the confidences obtained for other concepts in the same image.

We studied three other network organizations to evaluate the effect of using additionnally the semantic context in concept detection at the image level. We still include outputs from the patch level, but we do so using the outputs related to all other concepts for the detection of any given concept. We are now considering concepts as related one to each other (and no longer independently one from another).

Topologic and Semantic contexts, sequential, three levels (4)

The fourth network simply take the output of the third one (topologic context, serial, two levels) and adds a third level that uses the scores computed for all concepts to re-evaluate the score of a given concept. We have additionnally here N level 3 classifiers, each with N inputs and 1 output. Each level 3 classifier is callled only once on a given image.

Topologic and Semantic contexts, parallel, two levels (5)

The fifth network is similar to the previous version except that the last two levels have been flattened and merged into a single classifier. The difference is similar to the difference between the serial and flat versions of the networks that use only the topologic context. We have here N level 1 classifiers, each with F inputs and 1 output and N level 2 classifiers, each with N × P inputs and 1 output. All level 1 classifiers are callled P times on a given image and their N × P output values are passed to the corresponding level 2 classifier which is called only once.

Topologic and Semantic contexts, parallel, three levels (6)

The previous network suffers from the same limitation as the other flattened version it is not very scalable and requires a lot of training data and training times because of the large number of inputs of the classifiers. The flattening, however, permits to use the topologic and semantic information in parallel and in a correlated way. The sequential organization, on the contrary, though making use of both information does it in a non-correlated way.

The sixth network organization try to keep both contexts correlated (though less coupled) while avoiding the curse of dimensionality problem. The N × P number of inputs is replaced by N +P . The architecture is a kind of hybrid between the two previous ones. It is the same as in the sequential case but P inputs are added to the classifiers f the last level. These P input comes directly from the output of the first level but for the corresponding concept only (instead as the output from all P patches times all N like in the flattened case).

EXPERIMENTS

We conducted several experiments in TRECVID'04 Collaborative Annotation Corpus, in order to study our framework's behavior. We used the trec eval tool and TRECVID protocol, i.e. return a ranked list of 2000 top images. TRECVID-'04 Collaborative Annotation Corpus contains 48104 key frames. We split it into 50% training set and 50% test set.

We focus on 5 intermediate concepts which can be extracted as patch-level: building, sky, greenery, skin face and studio setting background. We choose them because of their semantics relationships. building, sky, greenery are closer than others. Additionally, skin face and studio setting background occur often together.

We used SVM classifier with RBF Kernel, because it has shown good classification results in many fields, especially in CBIR [GC04]. We use cross validation for parameter selection, using grid search tool to select the best combination of parameters C and gamma (out of 110).

In order to obtain the training set, we extracted patches from annotated regions, it is easy to get many patches by performing overlapped patches. Annotating whole images is harder as annotators must observe each one. We collected many positive samples for patches annotation, and defined experimentally a threshold for maximum numbers of positive samples. We found that 2048 positive samples is a good compromise to obtain good accuracy with smaller training time. Also, we found that twice negative samples is a good compromise. Finally, we randomly choose negative samples. The Table ?? shows the number of positive image examples, for each concept.

Table ?? shows the relative performance and training time for the detection of five concepts and for the six considered network organizations. As expected, the flattened version requires much higher training time. For the presented times, we added the training times of each intermediate levels, it include the cross-validation time. Also, the cross-validation process can be performed in parallel [? ], we used 11 3Ghz Pentium4 "Hyperthreaded" processors, 1Go RAM each. The reported results are the corresponding for one single processor.

The use of topologic context improves the performance over the baseline and combined with the semantic context improves it even further. The performance of the three-level sequential classifier is poorer than the two-level serial one. This may be due to the lack of information of his final level classifier, which have N (currently 5) inputs only. This may change when a much higher number of concepts are used.

For the networks which use both topologic and semantic contexts, the hybrid version has an intermediate performance between the sequential and parallel flattened versions. The twolevel version has the better performance as it merge more information. However, it does not scale well with the number of concepts while the hybrid version suffers much less from this limitation and should performs better with more concepts. Also, by comparing second and fifth networks results, we can conclude that dimensionality reduction induced by our approach is really significant, in term of both accuracy and computational time.

CONCLUSION

We presented a framework for incorporate semantic and topologic contexts in CBII. We compared several networks and showed that both contextual information improves concepts detection. We proposed an hybrid network which is promising for further scalable experiments. Then, we found that dimensionality reduction induced by our framework, provides better accuracy in shorter computation time than a flattened classifier. This result is also very useful for further scalable experiments. Finally, we plan to evaluate how our framework can derive higher-level semantic concepts.

Fig. 1 .

 1 Fig. 1. Overall architecture and experimented networks

Table 1 .

 1 Comparative performance of network organizations: mean average precision (MAP) for five concepts, mean of MAPS, and corresponding training times (in minutes)

	build.	sky	stud.	green.	skin.	all	time

ACKNOWLEDGMENTS

This work has been spported by the ISERE CNRS ASIA-STIC project and the Video Indexing INPG BQR project.