Mateusz Budnik

Laurent Besacier

Ali Khodabakhsh

Cenk Demiroglu

OCR-AIDED PERSON ANNOTATION AND LABEL PROPAGATION FOR SPEAKER MODELING IN TV SHOWS

Keywords: active learning, annotation propagation, clustering, speaker identification, OCR

In this paper, we present an approach for minimizing human effort in manual speaker annotation. Label propagation is used at each iteration of an active learning cycle. More precisely, a selection strategy for choosing the most suitable speech track to be labeled is proposed. Four different selection strategies are evaluated and all the tracks in a corresponding cluster are gathered using agglomerative clustering in order to propagate human annotations. To further reduce the manual labor required, an optical character recognition system is used to bootstrap annotations. At each step of the cycle, annotations are used to build speaker models. The quality of the generated speaker models is evaluated at each step using an i-vector based speaker identification system. The presented approach shows promising results on the REPERE corpus with a minimum amount of human effort for annotation.

INTRODUCTION

Thanks to the widespread availability of TV and the Internet, an immense quantity of videos are now available and can be used as a source for extracting a variety of useful information. However, due to complex nature of such data, annotation and indexing of these data can be costly and requires intensive human labor, which makes it impossible to be done at very large scale. To speed-up the process, several active learning methods are being developed to determine the most suitable instances/tracks for annotation, and by doing so, reducing the need for manual annotation [START_REF] Ayache | Evaluation of active learning strategies for video indexing[END_REF].

Effective methods for finding the most informative samples for labeling have been an active field of research. An unsupervised algorithm for active learning is presented in [START_REF] Hu | Unsupervised active learning based on hierarchical graph-theoretic clustering[END_REF] addressing some of the drawbacks of supervised active learning. An example of those is inability of selecting samples from new categories, which can be problematic in person identification tasks on broadcast data due to high number of distinctive classes with small number of instances [START_REF] Choudhury | Mulitmodal person recognition using unconstrained audio and video[END_REF]. A semantic approach of annotation propagation is proposed in [START_REF] Zonta Pastorello | Multimedia semantic annotation propagation[END_REF], and a person name propagation algorithm is proposed in [START_REF] Pham | Naming people in news videos with label propagation[END_REF] for video data. It is observed that the final score for person identification can be higher than with a SVM trained on the same initial labeled data. The information of the cluster structure is used alongside the selection of the most representative samples in [START_REF] Hieu | Active learning using pre-clustering[END_REF] to avoid sampling the same cluster.

In this paper, as an extension of the previous work done by the authors in [START_REF] Budnik | Active selection with label propagation for minimizing human effort in speaker annotation of tv shows[END_REF], the effectiveness of our active learning and annotation propagation methods is evaluated for a true speaker identification task. The method provides a cheap solution for creating reference speaker models from raw video input. For this, we make use of a classifier's output on clustered speech data to determine the most informative samples for annotation [START_REF] Safadi | Active learning with multiple classifier for multimedia indexing[END_REF]. This annotation is then propagated throughout its corresponding clusters. Reclustering is done afterwards and then a new sample is selected for annotation. To bootstrap the labeling process, Optical Character Recognition (OCR) can be used on overlaid text of broadcast data (e.g. when a person is shown on screen and his/her name is shown at the bottom of the screen).

Our goal here is to investigate how much annotation is needed to produce an accurate speaker model. Additionally, the comparison is made between models that were trained in an unsupervised manner (with the only source of labels being the overlaid names present in the video) and those that gradually use more human annotation, i.e. they become more and more supervised. The quality of the generated speaker models is evaluated through speaker identification tests on a separate set of unseen data.

A previously developed unsupervised system for label propagation [START_REF] Poignant | Towards, a better integration of written names for unsupervised speakers identification in videos[END_REF] was used and it is shortly described here. In our work the active learning module is added on top of that unsupervised system. The results indicate the advantages of using both overlaid names for the cold start and propagation of annotation within clusters. Also, to obtain a model with good enough performance, it is shown that one does not necessarily have to label all the data.

The rest of the paper is organized as follows: Section 2 describes the overall design and proposes in-detail description of the used systems. The experimental setup and results are presented in Section 3. Section 4 concludes the paper.

SYSTEM DESCRIPTION

An overview of the system used in this study is shown in Figure 1. After the extraction of speaker tracks (which are equivalent to segments and in this work both names are used interchangeably), the distances between tracks are calculated and agglomerative clustering is done. In the case of usage of OCR labels for cold start, OCR is applied on the videos and overlaid names are extracted. Then, the clusters are labeled with initial labels obtained accordingly. Next, the active learning (AL) cycle (pictured in Figure 1) is introduced by choosing a sample for labeling using different selection strategies (random, chronological, longest, and biggest cluster probability).

Once the new label is obtained, we recalculate the clusters and propagate the annotation to the instances in the same cluster. During this step, some clusters may be combined and new clusters may be created. The new and modified cluster structure is then used as a starting point for the next cycle of active learning. Details about each component of this process are given in the next sub-sections.

Speaker Diarization and Speech Track Distance Calculation

After splitting the signal into acoustically homogeneous segments with the use of the conventional BIC-criterion [START_REF] Chen | Speaker, environment and channel change detection and clustering via the bayesian information criterion[END_REF], a similarity score matrix is calculated between each pair of speech tracks. Single full-covariance Gaussians are used and distances are normalized to have a maximum of 1. This is an automated process, which may lead to some of the speaker tracks containing a degree of background noise, music or silence.

Overlaid name extraction

In order to be able to automatically extract the overwritten names from video, an OCR system following the design proposed in [START_REF] Poignant | From text detection in videos to person identification[END_REF] is used. Usually guests and speakers are introduced on a television show in their first appearance with an overlaid text containing their name. Using OCR, the texts visible on the screen are extracted, however, it is important to note that not all of the visible texts contain the name of the speaker. This module is composed of a text detection step and a text recognition step. For text detection, the approach in [START_REF] Anthimopoulos | A two-stage scheme for text detection in video images[END_REF] is adopted where coarse detection is obtained using Sobel filter and dilatation/erosion. To filter out the false positive text boxes, several temporally shifted images are extracted for the same text. This allows the system to overcome the shortcoming of binarization.

When text boxes are extracted, the publicly available Tesseract1 OCR system developed by Google is applied for text recognition.

Selection Strategies and Re-clustering

During a single AL cycle, one track is selected for each show of the train collection. Four different selection strategies are applied in this study.

Random

This strategy chooses a random track to be annotated for every show; this method is used as a baseline.

Chronological

This strategy chooses the track to be annotated chronologically for a given show.

Longest

For this strategy, the longest track is chosen for manual annotation. The tracks that are already annotated (or that benefit from label propagation) are left out.

Biggest Cluster Probability

In this strategy, a track from a cluster with a low annotation ratio is chosen for annotation. For this, the score S c is calculated for each cluster as S c = at nt , where a t is the number of annotated tracks in the cluster and n t is the total number of tracks in the cluster. This score is used to bias a random variable for which tracks in clusters with low annotation ratio have higher probability to be selected.

Speaker Identification Systems

An automatic speaker identification system based on frontend factor analysis [START_REF] Dehak | Front-end factor analysis for speaker verification[END_REF], also known as Total Variability Space (TVS), is chosen for this study.

Gaussian Mixture Models (GMM) are typically used as a generative model for representing the acoustic feature space in speaker recognition systems. A Universal Background Model (UBM) is first trained on speech data from multiple speakers, and then speaker-specific models are obtained using Maximum a Posteriori (MAP) adaptation.

Speaker models can be represented as high-dimensional supervectors of means of Gaussian distributions. Using probabilistic factor analysis on these supervectors, speaker models can be represented as a low-dimensional identity vector (ivector). In this approach, the mean supervector of a speaker s is modelled with M s = M 0 +T w s , where M 0 is the mean supervector of the UBM, w s is the i-vector of speaker s, and T is the low-rank rectangular matrix representing the variability space of the i-vectors. In case of having multiple tracks for speaker modeling, i-vectors extracted from each speech track are averaged and the average i-vector is used as the speaker model. The averaging can be done in a weighted manner according to the logarithm of the duration of the tracks. Duration of the tracks in seconds is incremented by one prior to taking logarithm to avoid negative weights. Length normalization is done prior to generation of speaker models [START_REF] Garcia | Analysis of i-vector length normalization in speaker recognition systems[END_REF].

Identification is done by extraction of the i-vector of a target track and calculation of the cosine similarity score of the extracted i-vector with all the speaker models (each represented with an i-vector). The speaker corresponding to the model with the highest score is chosen as the identified speaker.

For feature extraction, Energy and Mel-Frequency Cepstral Coefficients (MFCCs) of 13 dimensions are extracted every 10 ms with a window length of 20 ms. These features along with their delta and delta-delta coefficients are concatenated. Feature warping [START_REF] Pelecanos | Feature warping for robust speaker verification[END_REF] is done on these features and static energy feature is discarded resulting in a 41 dimensional feature vector per frame. Sound activity detection is done using bi-gaussian distribution on frame log-energies. The segmentation is done in a similar manner as described for speaker diarization. Segments with less than 150 ms of voice activity are ignored.

A UBM consisting of 1024 gaussians is trained on the training data for the GMM-UBM system. A UBM of the same size is used for training the T matrix. Total variability space is then learned using Expectation-Maximization (EM) algorithm on the segmented training data. The dimension of the output i-vectors is set to 400 and weighted averaging is done for generation of speaker model i-vectors. A modified version of MSR Identity Toolbox [START_REF] Seyed | Msr identity toolbox v1. 0: A matlab toolbox for speaker recognition research[END_REF] is used for the experiments.

EXPERIMENTS

Database and Protocols

The REPERE corpus [START_REF] Giraudel | The repere corpus: a multimodal corpus for person recognition[END_REF] was used for evaluation of the annotation propagation methods. This corpus consists of seven types of shows from the French TV channels BFM-TV and LCP, and is aimed for development of person identification methods on broadcast data. The train set consists of 58 videos and has a total duration of ˜28 hours. The development set and test set, with a total annotated duration of ˜8 hours and ˜13 hours, containing 57 and 90 videos respectively, are both used for evaluation. Only parts of the videos corresponding to specific shows are annotated. Length of these series differ, ranging from 3 minutes to half an hour, and therefore, the number of annotations per video vary widely from twenty to several hundreds.

Experimental Setup

In this study, simulated active learning is done on the training set, where all the manual annotations are available initially, but considered as unknown to the system. The labels are revealed to the system as the selection algorithm selects them for annotation. The simulation is done for the duration of 20 AL cycles and on each cycle only one annotation per show is selected. For each selection strategy, there are 10 replicas and randomly 20% of the data is completely left-out for each replica. Four different selection strategies are evaluated.

For every repetition of each AL cycle using each selection strategy, speaker models are created based on the output annotations of the active learning system (on the training data). The speaker identification performance is evaluated on the development and test sets separately using the standard F-measure. However, due to the fact that all the data is not annotated, the performance is only evaluated on the annotated tracks. Number of annotated tracks used in this study are 3490 and 4779 for development and test respectively.

Tests are done in an open-set manner, and results with correct labels corresponding to the maximum possible F-measure as well as results with a fully supervised system are reported for comparison. Tests with and without OCR cold start are also reported.

Results and discussion

Figure 2 and 3 give the F-measure results with the standard deviation starting with no available annotation. With a good enough selection strategy one can get close to the fully supervised performance in just a few steps. Overall, the best approach is to select the longest track first, which is not surprising given that a long uninterrupted speech segment from a single speaker would lead, in most cases, to a good speaker model.

The results with the overlaid names as a cold start can be seen in Figure 4 and 5 for the development and test set, respectively. This approach gives an initial boost in performance, which can be further increased with just a few additional annotations. Regardless of the use of the OCR, both approaches are able to arrive at the same level of performance (especially in the case of the longest strategy), even though the use of OCR makes it faster for every selection approach. This would indicate that the approach presented here could be successfully employed on different datasets where the OCR may not always be available. The weak performance of the Fig. 2. Performance of the speaker identification system on the development data in terms of F-measure. The results with supervised speaker modeling as well as maximum possible F-measure in the open-set setup are also reported for comparison. Fig. 3. Performance of the speaker identification system on the test data in terms of F-measure. The results with supervised speaker modeling as well as maximum possible Fmeasure in the open-set setup are also reported for comparison.

biggest cluster strategy can partially be attributed to the noisiness of the initial clusterings.

After around 6 steps (when using OCR) the performance increases only slightly. Without OCR it takes around 9 steps for the best strategy to get to a comparable level. It seems, therefore, that the use of such an active learning system can greatly reduce the number of annotation needed to produce competitive speaker models. Manual annotation is often expensive and time consuming. This approach can help to reduce this burden, especially when the final goal is to have reliable speaker models.

CONCLUSION

In this paper the evaluation of an active learning system is presented. The main goal was to train speaker models using i-vectors and trying to determine if a similar performance can be achieved without fully annotating the dataset. The presented experiments indicate that when using a good selection strategy a comparable performance can be obtained with just a fraction of the labels.

Additionally, the use of automatic labels, extracted using an OCR system, is evaluated. As seen in the experiments, OCR names can further reduce the need for manual annotation.

Fig. 1 .

 1 Fig.1. Overview of the system structure with optional use of extracted overlaid names.

Fig. 4 .

 4 Fig. 4. Performance of the speaker identification system on the development data with use of overlaid names for initialization in terms of F-measure. The results with supervised speaker modeling as well as maximum possible F-measure in the open-set setup are also reported for comparison.

Fig. 5 .

 5 Fig. 5. Performance of the speaker identification system on the test data with use of overlaid names for initialization in terms of F-measure. The results with supervised speaker modeling as well as maximum possible F-measure in the open-set setup are also reported for comparison.

http://code.google.com/p/tesseract-ocr/

http://camomile.limsi.fr

This work was conducted as a part of the CHIST-ERA CAMOMILE

Acknowledgements: This work is a part of a project aiming to create a collaborative annotation framework for 3M (multimodal, multimedia, and multilingual) data, called CAMOMILE 2 project. 3


Mateusz Budnik

Bahjat Safadi

Laurent Besacier

Georges Quénot

Ali Khodabakhsh
email: ali.khodabakhsh@ozu.edu.tr

Cenk Demiroglu
email: cenk.demiroglu@ozyegin.edu.tr

LIG at MediaEval 2015 Multimodal Person Discovery in Broadcast TV Task

In this working notes paper the contribution of the LIG team (partnership between Univ. Grenoble Alpes and Ozyegin University) to the Multimodal Person Discovery in Broadcast TV task in MediaEval 2015 is presented. The task focused on unsupervised learning techniques. Two different approaches were submitted by the team. In the first one, new features for face and speech modalities were tested. The second method presents an alternative way to calculate the distance between face tracks and speech segments. It also had a competitive MAP score and was able to beat the baseline.

INTRODUCTION

These working notes present the submissions proposed by LIG team (partnership between Univ. Grenoble Alpes and Ozyegin University) to the MediaEval 2015 Multimodal Person Discovery in Broadcast TV task. Along with the algorithms and initial results, a more general discussion about the task is provided as well. A detailed description of the task, the dataset, the evaluation metric and the baseline system can be found in the paper provided by the organizers [START_REF] Poignant | Multimodal person discovery in broadcast tv at mediaeval 2015[END_REF]. All the approaches presented here are unsupervised (following the organizers guidelines) and were submitted to the main task.

The main goal of the task is to identify people appearing in various TV shows, mostly news or political debates. The task is limited to persons that speak and are visible at the same time (potential people of interest). Additionally, the task is confined to the multimodal data (including face, speech, overlaid text) found in the test set videos and is strictly unsupervised (no manual annotation available). The main source of names is given by the optical character recognition system used in the baseline [START_REF] Poignant | From text detection in videos to person identification[END_REF].

Thanks to the provided baseline system [START_REF] Poignant | Unsupervised speaker identification using overlaid texts in tv broadcast[END_REF], it was possible to concentrate on some aspects of the task, like a particular modality or the clustering method. Initially, our focus was on creating better face and speech descriptors. In the second approach however, only the distances between face tracks and speech segments were modified. The output of the baseline OCR system was used as is, while the output from the speech transcription system was not used at all.

Copyright is held by the author/owner(s).

MediaEval 2015 Workshop Sept. 14-15, 2015, Wurzen, Germany

APPROACH

Our initial approach focused on creating new features for both face and speech. The second approach is based more on the baseline system, i.e. no new descriptors were generated and the key element was the distance between speech segments and face tracks.

What did not work: new features

The first approach explored the use of alternative features for different modalities. For speech, a Total Variability Space (TVS) system [START_REF] Dehak | Front-end factor analysis for speaker verification. Audio, Speech, and Language Processing[END_REF] was designed using the following settings with the segmentation provided by the baseline system. Models were learned on the test data without any manual annotation available.

• 19 MFCC and energy + ∆s (no static energy) + feature warping

• 20ms length window with a 10ms shift

• Energy based silence filtering

• 1024 GMMs + 400 dimensional TVS

• Cosine similarities between segments within each video are calculated

For faces, features extracted from a deep convolutional neural network [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] were used. This was done in the following way using the test set only:

• Face extraction with the approach provided by the organizers. All scaled to resolution of 100x100 pixels.

• Labels generated by the OCR. They were then assigned to co-occurring faces. This was based on a temporal overlap between the face and the label. This generated list served as a training set. The number of classes equaled the number of unique names.

• The general structure of the net is based on the smallest architecture presented in [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], but with just 5 convolutional layers and the number of filters at each layer reduced by half. The fully connected layers had 1024 outputs. It was trained for around 15 epochs.

• After the training, the last layer containing the classes was discarded and the last fully connected hidden layer (1024 outputs) was then used for feature extraction.

Two individual sets of clusters were generated for each modality. Afterwards, late fusion was performed to generate the final output. Additional submissions involving this approach were made, which included adding descriptors provided by the baseline (e.g. HOG for face and BIC for speech). However, they did not manage to give better performance than the baseline.

What did work : modified distance between modalities

In the baseline provided, the written names are first propagated to speaker cluster and then the named speakers are assigned to co-occurring faces. Due to the nature of the test set, an alternative was used where the written names are first propagated to face cluster. These face-name pairs are subsequently assigned to co-occurring speech segments. This approach yielded a more precise but smaller set of named people compared to the baseline. In order to expand it, a fusion with the output of the original system was made, where every conflict (e.g. different names for the same shot) would be resolved in favor of our proposed approach.

Additionally, another way to calculate the distance between speech and face track was developed. Originally, the distance between a face track and a speech segment is calculated using lip movement detection, size and the position of the face and so on. Our complementary approach is based on temporal correlation of tracks from different modalities.

First, overlapping face tracks and speech segments are extracted for each video. Similarity vectors for both modalities are extracted with respect to all the other segments within the same video. Correlation of the similarity vectors are calculated in order to determine which face and voice go together. In other words, a face-speech pair which appears frequently throughout the video is more likely to belong to the same person. Finally, the output of this approach is combined with the output of the system described in the first paragraph of this subsection (face-name pairs assigned to co-occuring speech segments).

INITIAL RESULTS AND DISCUSSION

The first system performed rather poorly with 30.48 % EwMAP (MAP = 30.63 %). While our second approach with EwMAP = 85.67 % (and MAP = 86.03 %) was far more successful and was able to beat the baseline system (EwMAP = 78.35 % and MAP = 78.64 %). The scores presented here were provided by the organizers and can change slightly before the workshop, due to more annotation being available.

During the preparation for this evaluation there were a number of issues and observations connected to both our approach and to the data. First of all, trying to build biometric models for individual people does not work well for this particular task (at least based on what was tested in the context of this evaluation, e.g. SVMs). In order to comply with the task requirements, the labels can only be generated from the OCR and then be assigned to one of the modalities. However, both steps are unsupervised, generating noisy annotation in the process. Additionally, the video test set consists of one type of program (TV news) where, apart from the news anchor, most people appear only once and this may not be enough to create an accurate biometric model. This stands in contrast to the development set, which contains debates and parliament sessions where some persons re-appeared much more frequently.

A more general issue is also the class imbalance. While some people, especially the anchors, appear frequently across different videos, most of the others are shown once or twice and are confined to a single video. This makes the use of unsupervised techniques, like clustering, challenging, due to widely varying cluster sizes -small clusters can get attached to bigger ones, which is heavily penalized under the MAP metric. This can, at least partially, explain the poor performance of the first approach. Even though the features used in this method are state-of-the-art, they would require more high quality data (including annotation) and parameter adjustment to create good enough distinctions between thousands of individual persons appearing in the videos.

For the above reasons, the strong baseline performance is not that surprising. The evaluation metrics also seems to work in favor of such solutions, where wide coverage across different people is preferable to an exhaustive annotation of a selected few.

CONCLUSIONS

During this evaluation different algorithms were tested in order to (unsupervisingly) identify people, which speak and are visible in TV broadcasts. One approach concentrated on trying to provide state-of-the-art features for different modalities, while the other provided an alternative estimation of the distance between already provided modalities of face and speech.

The first approach, even with its limited performance on this particular shared task, seems to have greater potential and our future work may try to address some of its shortcomings. This includes a focus on a more robust deep learning approach that could deal with noisy or automatically generated training sets.

ACKNOWLEDGMENTS

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).


Emre Demir
email: emredemir@itu.edu.

Tr

Zehra Cataltepe
email: cataltepe@itu.edu.

Umit Ekmekci
email: uekmekci@itu.edu.

Mateusz Budnik
email: mateusz.budnik@imag.

Laurent Besacier
email: laurent.besacier@imag.

Unsupervised Active Learning For Video Annotation

 video dataset, which is created for the problem of person identification in videos. Our study aims to identify who is speaking and who is on screen by using multi-modal data.

Introduction

Annotating immense quantity of videos manually is a labor-intensive and time-consuming process. On the other hand, automatic annotation techniques such as Active Learning offer various solutions to overcome the excessive cost of manual annotation. Different active learning methods have been proposed for the video annotation problem. One of the studies [START_REF] Ayache | Evaluation of active learning strategies for video indexing[END_REF] applies active learning for video annotation by comparing uncertainty sampling, the most probable sampling and random sampling for video indexing. [START_REF] Ayache | Video corpus annotation using active learning[END_REF] pro-Proceedings of the 32 nd International Conference on Machine Learning, Lille, France, 2015. JMLR: W&CP volume 37. Copyright 2015 by the author(s).

poses video retrieval and annotation system called LIGVID which uses two active learning methods: 'relevance sampling' and 'uncertainty sampling'. Another study integrates SVM based active learning for feature selection to solve the text classification problem [START_REF] Joshi | Ualr at trec: Blog track[END_REF]. However, active learning for feature selection fails in that study, because of the use of a wrong feature reduction technique called GainRatio Feature Selection [START_REF] Joshi | Ualr at trec: Blog track[END_REF].

In the study [START_REF] Bilgic | Active learning for networked data[END_REF], active learning is applied on a networked data, nodes of which are 'papers' and links are 'references to the other papers'. It uses a method based on query by disagreement and reduces paper annotation costs for classifying research papers. The study [START_REF] Raghavan | Active learning with feedback on features and instances[END_REF] extends the traditional active learning framework by including feedback on features alongside labeling the instances. It focuses on the effects of feature selection and human feedbacks for features in the setting of text categorization and applies uncertainty sampling based methods.

In this study1 , we propose a cluster based unsupervised active learning approach as a selection strategy on REPERE [START_REF] Giraudel | The repere corpus: a multimodal corpus for person recognition[END_REF] video dataset, which is created for the problem of person identification in videos. Our study aims to identify who is speaking and who is on screen.

The Properties of The Dataset

We use the video dataset from the REPERE challenge, which aims to find answers to questions "Who is speaking?", "Who is present in the video?", etc., by the use of various information on speech and image extracted from the dataset. The REPERE Corpus consists of 28 videos, which includes 7 different types of shows such as news, talk show, etc. and various numbers of participants from 3 to dozens in a video. Furthermore, the length of the videos has a range of 3 to 30 minutes, which naturally causes various numbers of annotations for each video approximately 20 to 100 frames. [START_REF] Budnik | Automatic propagation of manual annotations for multimodal person identification[END_REF] applies speech and face segmentation processes on videos to gather the similarity matrices faceto-face and speech-to-speech which are normalized into the interval [0,1]. The third similarity matrix, face-to-speech, occurs from correlation scores between the faces and the speakers to build a multimodal clustering. We use these three similarity matrices for training and manually annotated videos from REPERE dataset for testing. The study [START_REF] Poignant | From text detection in videos to person identification[END_REF] extracts overlaid texts in videos by an Optical Character Recognition (OCR) system to gather an initial set of annotated data. We use the information from embedded texts in videos that can point the name of a represented speaker.

Notation

In this study we use the following notation. The finite data set is X = x 1 , x 2 , . . . , x n where the cardinality is |X| = n. The cluster set C = {C 1 , C 2 , . . . , C k } represents the cluster sets of the set X with the assumption |C i | > 0 for all i = 1, 2, . . . , k. C is the second clustering for X where

C = {C' 1 , C' 2 , . . . , C' } ∈ S(X). M = m ij
is the confusion matrix of each clustering pair C, C . The intersection between C i and C' j is a kx matrix where the ij th element gives the number of the elements in the intersection of C i and C' j .

m ij = |C i ∩ C' j |, 1 ≤ i ≤ k, 1 ≤ j ≤ (1)

Unsupervised Active Learning

Supervised query by disagreement method (QBD) [START_REF] Settles | Active learning. Synthesis Lectures on Artificial Intelligence and Machine Learning[END_REF] is one of the active learning methods in the literature. QBD uses two different classifiers and asks the label of a disagreed point to an expert. We introduce unsupervised query by disagreement method to accelerate the learning phase of the automatic video annotation by using unsupervised learners. When it is used with supervised learners, Query by Disagreement (QBD) lets the learners label each instance and compares the learners' outputs for the same instance to detect disagreement instances. However, since unsupervised methods do not generate labels for each data instance as output of a learner, using QDB on unsupervised learners is a new and a challenging problem. We propose a novel approach for QBD on unsupervised learners and apply the solution on multimodal video data.

In our study, we use the following steps during an Active Learning phase: clustering, cluster matching, disagreement measurement between clusters, selection of the most disagreed clusters, selection of an instance to be queried from the selected cluster.

Clustering and Cluster Matching

Active learning cycle begins with the clustering of the data. We use two clustering algorithms: Agglomerative Clustering and K-Medoid Clustering. For a given threshold, Agglomerative Clustering estimates the number of clusters, which we use as the value of the K-Medoid Clustering's number of clusters parameter k.

In order to find the clustering disaggreement, we first solve the complementary problem of finding the disagreements between clusterings. We apply a cluster matching algorithm to measure the similarities between the clusterings produced by the Agglomerative and K-Medoid algorithms.

We use the intersection of clusters by calculating the cluster similarity metric as in equation 2.

H(C, C ) = 1 k j=match(i) m ij (2)
We need to find j = match(i) which denotes the cluster that the cluster C j to which the C i should be matched. Then, in order to assign a clusters between Agglomerative and K-Medoid clusterings, we adopt and apply the Gale-Shapley algorithm [START_REF] Iwama | A survey of the stable marriage problem and its variants[END_REF][START_REF] Krumpelman | Matching and visualization of multiple overlapping clusterings of microarray data[END_REF] which is used for solving the 'Stable Marriage Problem'. Gale-Shapley algorithm guarantees that the solution obtained is perfect (i.e. everyone gets married) and stable.

Let the clustering produced by the Agglomerative clustering be C = C 1 , C 2 , . . . , C k and the clustering produced by the k-medoid clustering be C = C 1 , C 2 , . . . , C k . Gale-Shapley algorithm requires that each cluster C i ranks the clusters C j and vice versa. We use the cluster confusion matrix entries (Equation 1) in order to produce these rankings and then apply the Gale-Shapley algorithm to produce a cluster matching. The output of the Gale-Shapley is a matching M = [m 1 , m 2 , . . . , m k ] where, m i ∈ 1, . . . , k, m i = j if C i is matched with C j in the stable matching.

Query Instance Selection

In order be able to select which instance to query, we first select the most informative cluster of cluster pair, and then we select the most informative instance in the selected clus-ter.

CLUSTER SELECTION

We score clusters using different methods and select and instance from the cluster with the highest score. Big Cluster Selection (BCS): The study [START_REF] Budnik | Automatic propagation of manual annotations for multimodal person identification[END_REF] proposes 'Big Cluster First' selection strategy which calculates a score using size of a set and the number of annotated instances in that set. The method selects an instance from a minimum scored set by asking human expert.

The BCS strategy score for a cluster C i is calculated as

BCS(C i ) = N umberOf Annotations(C i )/Size(C i ).
The Most Disagreement Selection (MDS):In theory, the most disagreed cluster pair gives us the most uncertain points because two stable matched clusters have lots of disagreed instances. For measuring the disagreement between a pair of matched clusters C i , C j where j = m i , we divide the number of common instances by the total number of instances:

M DS(C i ) = C i ∩ C j C i ∪ C j (3)
MDS method choosed the cluster C i which has the highest DS score.

Hybrid Cluster Selection BCS method performs better during the initial stages of active learning where the number of labeled instances are very few and labeling instances on big clusters help a label a lot of instances. On the other hand, MDS performs better when clusters contain more known instances. Because cluster disagreement has a correlation with the label assignment. Therefore, we introduce two hybrid cluster selection methods: Soft Hybrid Selection (SH) and Hard Hybrid Selection (HH).

In order to combine or compare the different BCS and MDS clustering scores, we apply the z-score normalization on them.

The Soft Hybrid Selection (SH) score for a cluster C i is computed as the weighted average of the normalized BCS and MDS scores:

SH(C i ) = ((1 -α) × BCS(C i )) + α × M DS(C i ) (4)
where 0 < α < 1. Since we want to give more weight to the BCS method during the initial iterations and more weight to MDS during the later iterations, we vary the value of the weight alpha by passing through the sigmoid function in each iteration number t.

The Hard Hybrid Selection method uses the BCS scores at the beginning of active learning iterations and then uses the BCS scores after a certain iteration number five.

INSTANCE SELECTING STRATEGY

Instance selection strategy tries to determine the most informative instances in the selected cluster. The instances from the center of a cluster are more 'certain' than the instances close to the cluster boundary in terms of class knowledge. However, since the entropies of uncertain instances are relatively higher than the entropies of certain instances (Settles, 2012), the most informative instances are actually on the region around the boundary of a cluster. Therefore, for each instance in a cluster, we sum the distances to other instances in the same cluster and choose the instance with the highest sum, which gives us the most 'uncertain' instance, the instance which is farthest away from all the other instances. Instance selection strategy can select the most 'uncertain' or the most 'certain' (i.e. medoid) instance from a cluster or a cluster pair.

Results and Discussion

We evaluate the performance of selection strategies over active learning cycles using multimodality on 28 videos from 7 different TV programs. Each video has three different similarity matrices namely face-to-face, speech-tospeech and face-to-speech. We run four experiments with regard to matrices in this order; 'face score for face track annotation" (FF), 'face score for speaker track annotation' (FS), ' speaker score for speaker track annotation' (SA) and 'speaker score for speaker annotation' (SS). An active learning cycle which is depicted as 'step', asks one annotation for each video. As the performance measure, we use the F-measure, instead of accuracy, since the number of instances of each class (person) in the datasets is very different from each other. F-measure is the harmonic mean of precision p and recall r values. Precision shows how much relevant instances are retrieved among all retrieved instances and recall shows how much retrieved instances are relevant among all relevant instances. In the experiment FS, BCS selects good annotations at the earlier steps and achieves high F-measure value more rapidly than MDS-Certainty since there is no sufficient data to be disagreed upon for the MDS-Certainty method. However, at the later steps, F-measure value decreases, but MDS-Certainty keeps increasing. In order to take advantage of the strongest sides of both methods, Hard Hybrid Certainty (HHC) use BCS at the first five steps. After the fifth step, it uses MDS and keeps increasing in terms of F-measure. As a result, HHC achieves better scores than random.

In the experiment SF, BCS achieves high F-measure scores rapidly and higher than random as in FS. Nevertheless, it's decreasing at the later steps and finally performs worse than random. On the other hand, MDS-Certainty F-measure increases stably as in FS but performs similar to random. However, the most interesting result comes from HHC that combines BCS and MDS-Certainty. HHC gives higher Fmeasures rapidly like BCS at the earlier steps and continues to increase at the later stages like MDS-Certainty. Furthermore, it performs better than random significantly until the 10th step. Fortunately, in terms of active learning, reaching to the highest F-measure score rapidly is more meaningful.

We proposed the MDS active learning method and its hybrid variations and we applied them on multimodal video annotation data. According to our experiments, for different types of annotation tasks, different active learning strategies could be more suitable. Hybrid strategies could be more successful than using a single strategy alone. Decision of the cluster selection and instance selection method adaptively during each active learning step, using a synthetic dataset to investigate the merits of these strategies, examination of each method for each video, rather than the whole REPERE corpus are the future research directions we aim to follow.

Figure 1

 1 Figure1(a) shows the F-measure values on the FF in each step. The results indicate that active learning methods BCS -uses uncertainty-and Hard Hybrid perform better than the random method in the earlier steps. However, random selection achieves the best values among all other methods at the later steps. On the other hand, MDS-Uncertainty, MDS-Certainty and Soft Hybrid achieve a little better performance than random for SS as shown in Figure1 (d). Soft Hybrid selection performs worse in FF, FS and SF and barely good at SS.The multimodal classifying problems FS and SF (SeeFigure 1 (b),(c)) have more deviations than the others because the correlation between face tracks to speaker tracks is weaker than head to head tracks or speaker to speaker tracks. For this reason, MDS certainty performs better than all others in FS and more robust than BCS in SF.

Figure 1 .

 1 Figure 1. F-measure scores, from left to right: (a)face score for face modality (FF), (b)face score for speaker modality (FS), (c)speaker score for face modality (SF) and (d)speaker score for speaker modality (SS).

The study is a part of the project CAMOMILE (cam), which targets to produce an annotation framework for multimodal, multimedia and multilingual data

Acknowledgments

Work in this paper is partially supported by the Scientific and Technological Research Council of Turkey (TUBITAK) project 112E176.


New efficient clustering quality indexes

Jean-Charles Lamirel, Nicolas Dugué, Pascal Cuxac Abstract-This paper deals with a major challenge in clustering that is optimal model selection. It presents new efficient clustering quality indexes relying on feature maximization, which is an alternative measure to usual distributional measures relying on entropy, Chi-square metric or vector-based measures such as Euclidean distance or correlation distance. First Experiments compare the behavior of these new indexes with usual cluster quality indexes based on Euclidean distance on different kinds of test datasets for which ground truth is available. This comparison clearly highlights altogether the superior accuracy and stability of the new method on these datasets, its efficiency from low to high dimensional range and its tolerance to noise. Further experiments are then conducted on "real life" textual data extracted from a multisource bibliographic database for which ground truth is unknown. These experiments show that the accuracy and stability of these new indexes allow to deal efficiently with diachronic analysis, when other indexes do not fit the requirements for this task.

I. INTRODUCTION

Unsupervised classification or clustering is a data analysis technique which is increasingly widely-used in different areas of application. If the datasets to be analyzed have growing size, it is clearly unfeasible to get ground truth that permit to work on them in a supervised fashion. The main problem which then arises in clustering is to qualify the obtained results in terms of quality. A quality index is a criterion which makes possible to decide which clustering method to use, to fix an optimal number of clusters and also to evaluate or develop a new method. Many approaches have been developed for that purpose as it has been pointed out in [START_REF] Milligan | An Examination of Procedures for Determining the Number of Clusters in a dataset[END_REF] [START_REF] Yanchi | Understanding of internal clustering validation measures[END_REF] [27] [START_REF] Latha | Cluster validity measures dynamic clustering algorithms[END_REF]. However, even if recent alternative approaches do exist [START_REF] Bock | Probability model and hypothese testing in partitionning cluster analysis[END_REF] [START_REF] Gordon | External validation in cluster analysis[END_REF] [START_REF] Halkidi | On clustering validation techniques[END_REF], the usual quality indexes are mostly based on the concepts of dispersion of a cluster and dissimilarity between clusters. Computation of the latter criteria themselves relies on Euclidean distance. Most popular such indexes are the Dunn index [START_REF] Dunn | Well separated clusters and optimal fuzzy partitions[END_REF], the Davis-Bouldin index [START_REF] Davies | A cluster separation measure[END_REF], the Silhouette index [START_REF] Rousseeuw | Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[END_REF], the Calinski-Harabasz index [START_REF] Calinsky | A dendrite method for cluster analysis[END_REF] and the Xie-Beni index [START_REF] Xie | A validity measure for fuzzy clustering[END_REF]. They implement the afore mentioned concepts in slightly different ways.

Consider a dataset D made of n data points, and C, a partition in k clusters of the dataset :

C = (C i , • • • , C k ).
The Dunn index (Equation 1), that has to be maximized, identifies clusters which are well separated and compacts. It combines dissimilarity between clusters and their diameters to estimate the most reliable number of clusters:

DU = min 1≤i<j≤k Diss DU (C i , C j ) max m=1,••• ,k Diam(C m ) (1)
The dissimilarity distance usually used as the numerator is often an exhaustive dissimilarity measure between all Jean-Charles Lamirel is with the Synalp Team, LORIA, Nancy, France (email: lamirel@loria.fr).

points of distinct clusters. In general, different diameters and distances definitions can be used.

The Davies-Bouldin index (Equation 2) is similar to the Dunn index and identifies clusters which are far from each other and compacts. It should be minimized:

DB = 1 k k i=1 max j=1,••• ,k;i =j { Diam(c i ) + Diam(c j ) Diss DB (C i , C j ) } (2)
The dissimilarity distance used in Davies-Bouldin is a distance between centroids. It is thus far faster to compute than the Dunn Index in its usual form.

To define the Silhouette index, we first define the Silhouette width of each point (Equation 3):

S(i) = b(i) • a(i) max(b(i), a(i)) (3)
with a(i) being the mean distance of point i to the other points of its cluster, and b(i), the lowest average distance between i and each other cluster point set. A negative silhouette value for a given point means that the point is most suited to belong to a different cluster from the one it is allocated. Then, the Silhouette Index is computed as follows and has to be maximized:

SI = 1 n i∈n S(i) (4)
The Calinski-Harabasz index (Equation 5) is defined as follows:

CH = (n -k) (k -1) BGSS W GSS (5)
with BGSS the Between Group Sum of Squared that measures the dissimilarity between different clusters, and W GSS the Within Group Sum of Squared that measures dissimilarity within clusters. Well separated and compact clusters should maximize this ratio. The Xie-Beni index (Equation 6) is a compromise between the approaches provided by the Dunn index and by the Calinski-Harabasz index, and it should be minimized:

XB = 1 n W GSS min 1≤i<j≤k Diss DU (C i , C j ) (6)
As stated in [31] [12] usual indexes have the defect to be sensitive to noisy data and outliers. In [START_REF] Lamirel | Variations to incremental growing neural gas algorithm based on label maximization[END_REF], we also observed that the proposed indexes are not suitable to analyze clustering results in highly multidimensional space as well as they are unable to detect degenerated clustering results. Also, these indexes are not independent of the clustering method with which they are used. As an example, a clustering method which tends to optimize WGSS, like k-means [START_REF] Macqueen | Some Methods for classification and Analysis of Multivariate Observations[END_REF], will also tend to naturally produce low value for that criteria which optimizes indexes output, but does not necessarily guarantee coherent results, as it was also demonstrated in [START_REF] Lamirel | Variations to incremental growing neural gas algorithm based on label maximization[END_REF]. Last but not least, as Hamerly et al. pointed out in [START_REF] Hamerly | Learning the K in K-Means[END_REF], the experiments on these indexes in the literature are often performed on unrealistic test corpora made up of low dimensional data with a small number of "well-shaped" (mostly hyperspheric) embedded virtual clusters. As an example, in their reference paper, Milligan and Cooper [START_REF] Milligan | An Examination of Procedures for Determining the Number of Clusters in a dataset[END_REF] compared 30 different methods for estimating the number of clusters. They classified CH and DB in the top 10, with CH the best but their experiments only used simulated data described in a low dimensional Euclidean space. The same remark can be made about the comparison performed in [START_REF] Yanchi | Understanding of internal clustering validation measures[END_REF] or in [START_REF] Dimitriadou | An examination of indexes for determining the number of clusters in binary data sets[END_REF]. However, Kassab et al. [START_REF] Kassab | Feature Based Cluster Validation for High Dimensional Data[END_REF] used the Reuters test collection to show that the aforementioned indexes are often unable to identify an optimal clustering model whenever the dataset is constituted by complex data which need to be represented in both highdimensional and sparse description space, obviously with embedded non-Gaussian clusters, as is often the case with textual data. The silhouette index is considered one of the more reliable indexes among those mentioned above, especially in the case of multidimensional data, mainly because it is not a diameter-based index optimized for Gaussian context. However, like the Dunn and Xie-Beni indexes, its main defect is that it is computationally expensive, which could represent a major drawback for use with large datasets constituted by high-dimensional data.

There are also other alternatives to the usual indexes. For example, in 2009, Lago-Fernãndez et al. [START_REF] Lago-Fernãndez | Using the Negentropy Increment to Determine the Number of Clusters[END_REF] proposed a method using negentropy which evaluates the gap between the cluster entropy and entropy of the normal distribution with the same covariance matrix, but again their experiments were only conducted on two-dimensional data. Other recent indexes attempts were also limited by the researchers' choice of complex parameters [START_REF] Yanchi | Understanding of internal clustering validation measures[END_REF].

Our goals were manifold: to get rid of the method-index dependency problem and of the sensitivity to noise issue, and to deal with high-dimensional context while avoiding computation complexity and parameter settings. To achieve such goals, we exploited features of the data points attached to clusters instead of information carried by cluster centroids and replaced Euclidean distance with a more reliable quality estimator based on the feature maximization measure. This measure has been already successfully used by Lamirel et al. to solve complex high-dimensional classification problems with highly unbalanced and noisy data gathered in similar classes thanks to its very efficient feature selection and data resampling capabilities [START_REF] Lamirel | Optimizing text classification through efficient feature selection based on quality metric[END_REF]. As a complement to this information, we shall show in the upcoming experimental section that cluster quality indexes relying on this measure do not possess any of the defects of usual approaches including computational complexity.

Section II presents a feature maximization measure and our proposed new indexes. Section III presents our first experimental context based on reference datasets. Section IV details our first results already presented in a more synthetical way in [START_REF] Lamirel | Reliable Clustering Quality Estimation from Low to High Dimensionnal Data[END_REF]. Section V presents a further step of comparative exploitation of the index on a real application of diachronic analysis of scientific litterature. Section VI draws our conclusion and ideas for future work.

II. FEATURE MAXIMIZATION FOR FEATURE SELECTION

Feature maximization is an unbiased measure which can be used to estimate the quality of a classification whether it be supervised or unsupervised. In unsupervised classification (i.e. clustering), this measure exploits the properties (i.e. the features) of cluster associated data. Its principal advantage is thus to be totally independent of the clustering method and of its operating mode.

Consider a partition C which results from a clustering method applied to a dataset D represented by a group of features F . The feature maximization measure favours clusters with a maximal feature F-measure. The feature Fmeasure F F c (f ) of a feature f associated with a cluster c is defined as the harmonic mean of the feature recall F R c (f ) and of the feature predominance F P c (f ), which are themselves defined as follows:

F R c (f ) = Σ d∈c W f d Σ c∈C Σ d∈c W f d F P c (f ) = Σ d∈c W f d Σ f ∈Fc,d∈c W f d (7) with F F c (f ) = 2 F R c (f ) × F P c (f ) F R c (f ) + F P c (f ) (8)
where W f d represents the weight of the feature f for the data d and F c represents all the features present in the dataset associated with the cluster c. Feature Predominance measures the ability of f to describe cluster c. In a complementary way, Feature Recall allows to characterize f according to its ability to discriminate c from other clusters.

There are some important similarities between Recall and Predominance used in the proposed approach and Recall and Precision used in information retrieval. We have already exploited this analogy more thoroughly in some of our former works, like in [START_REF] Lamirel | New classification quality estimators for analysis of documentary information: application to patent analysis and web mapping[END_REF], but the measures proposed here must be considered as generalizations of such information retrieval measures which are no more based on agreement but on influence of a feature materialized by a weight. Weight represents the importance of a feature for a data and furthermore for a cluster. The choice of the weighting scheme is not really constrained by the approach, but it is necessary to deal with positive values. Such scheme is supposed to figure out the significance (i.e. semantic and importance) of the feature for the data.

Feature recall is a scale independent measure but feature predominance is not. We have however shown experimentally in [START_REF] Lamirel | Optimizing text classification through efficient feature selection based on quality metric[END_REF] that the F-measure which is a combination of these two measures is only weakly influenced by feature scaling. Nevertheless, to guaranty full scale independent behavior for this measure, data must be standardized.

In supervised context, feature maximization measure can be exploited to generate a powerful feature selection process [START_REF] Lamirel | Optimizing text classification through efficient feature selection based on quality metric[END_REF]. In our unsupervised (clustering) context, the selection process can be used to describe or label clusters according to the most typical and representative features. This process is a non-parametrized process that uses both the capacity of F-measure to discriminate between clusters (F R c (f ) index) and its ability to faithfully represent the cluster data (F P c (f ) index). The set S c of features that are characteristic of a given cluster c is belonging to a partition C is translated by:

Sc = f ∈ Fc | F Fc(f ) > F F (f ) and F Fc(f ) > F F D ( 9
)
where

F F (f ) = Σ c ∈C F F c (f ) |C /f | and F F D = Σ f ∈F F F (f ) |F | ( 10
)
where C /f represents the subset of C in which the feature f occurs.

Finally, the set of all selected features S C is the subset of F defined by:

S C = ∪ c∈C S c . (11)
In other words, the features judged relevant for a given cluster are those whose representations are better than average in this cluster, and better than the average representation of all the features in the partition, in terms of feature F-measure. Features which never respect the second condition in any cluster are discarded.

A specific concept of contrast G c (f ) can be defined to calculate the performance of a retained feature f for a given cluster c. It is an indicator value which is proportional to the ratio between the F-measure F F c (f ) of a feature in the cluster c and the average F-measure F F of this feature for the whole partition 1 . It can be expressed as:

G c (f ) = F F c (f )/F F (f ) (12)
The active features of a cluster are those for which the contrast is greater than 1. Moreover, the higher the contrast of a feature for one cluster, the better its performance in describing the cluster content. Below we give an example of the operating mode of the method, on the basis of a toy-dataset encompassing two classes (Men (M), Women (F)) described with 3 features: Nose Size, Hair Length, Shoes Size. Figure 1 shows the source data and how the F-measure calculation of the Shoes Size feature operates in the Men class.

As shown in Figure 2, the second step consists in calculating the average F-measure of each feature over the clusters, 9) and notation F (x, .) stands for average of class x, which is itself computed as:

F (x, .) = Σ f ∈Sx F F x (f ) |S x | (13)
Features with F-measures that are systematically lower than the overall average are eliminated. The Nose Size feature is thus removed. Remaining features (i,e. selected features) are considered active in the classes in which their F-measure is above the marginal average: 1) Shoes Size is active in the Men's class, 2) Hair Length is active in the Women's class.

Contrast ratio highlights the degree of activity and passivity of selected features as regards their F-measure marginal average in different classes. Figure 3 illustrates how the contrast is calculated for the example presented. In the context of this example, the contrast may be considered as a function that will virtually have the following effects:

1) Increase the length of women's hair, 2) Increase the size of the men's shoes, 3) Decrease the length of the men's hair, 4) Reduce the size of women's shoes.

As already mentioned before, the active features in a Fig. 3. Principle of computation of contrast for selected features.

cluster are selected features for which the contrast is greater than 1 in that cluster. Conversely, the passive features in a cluster are selected features present in the cluster's data for which contrast is less than unity2 . A simple way to exploit the features obtained is to use active selected features and their associated contrast for cluster labelling as we proposed in [START_REF] Lamirel | Optimizing text classification through efficient feature selection based on quality metric[END_REF]. A more sophisticated method (as we shall propose hereafter) is to exploit information related to the activity and passivity of selected features in clusters to define clustering quality indexes identifying an optimal partition. This kind of partition is expected to maximize the contrast described by eq. 12. Indeed, the more contrasted are the features, the more compact and separated the clusters. Hence, this approach leads to the definition of two different indexes.

The PC index, whose principle corresponds by analogy to that of intra-cluster inertia in the usual models, is a macro-measure based on the maximization of the average weighted contrast of active features for optimal partition. For a partition comprising k clusters, it can be expressed as:

P C k = 1 k k i=1 1 n i f ∈Si G i (f ) (14)
The EC index, whose principle corresponds by analogy to that of the combination between intra-cluster inertia and inter-cluster inertia in the usual models, is based on the maximization of the average weighted compromise between the contrast of active features and the inverted contrast of passive features for optimal partition:

EC k = 1 k k i=1   |si| ni f ∈Si G i (f ) + |si| ni h∈Si 1 Gi(h) |s i | + |s i |   (15)
where n i is the number of data associated with the cluster i, |s i | represents the number of active features in i, and |s i |, the number of passive features in the same cluster.

III. EXPERIMENTAL DATA AND PROCESS

To objectively evaluate the accuracy of our new indexes, we used several different datasets of varying dimensionality and size for which the optimal number of clusters (i.e. ground truth) is known in advance.

Part of the datasets came from the UCI machine learning repository [START_REF] Bache | UCI Machine learning repository[END_REF] and is more usually exploited for classification tasks. The 4 selected UCI datasets represent mostly low to middle dimensional datasets and small datasets (except for PEN dataset which is large). The ZOO and SOY datasets which includes variables with modalities are transformed into binary files. IRIS is exploited both in standard and in binarized version to obtain clearer insight into the behavior of quality index on binary data.

VERBF is a dataset of French verbs which are described both by semantic features and by subcategorization frames. The ground truth of this dataset has been established both by linguists who studied different clustering results and by a gold standard based on the VerbNet classification, as in [START_REF] Sun | Investigating the cross-linguistic potential of VerbNet-style classification[END_REF]. This binary dataset contains verbs described in a space of 231 Boolean features. It can be considered a typical middle size and middle dimensional dataset.

The R8 and R52 corpora were obtained by Cardoso Cachopo from the R10 and R90 datasets, which are derived from the Reuters 21578 collection 3 . The aim of these adjustments was to only retain data with a single label. Considering only monothematic documents and classes that still had at least one example of training and one of test, R8 is a reduction of the R10 corpus (the 10 most frequent classes) to 8 classes and R52 is a reduction of the R90 corpus (90 classes) to 52 classes. The R8 and R52 datasets, with respective size of 7674 and 9100 documents, and associated bag of words description spaces of 1187 and 2618 words, can be considered as large and high dimensional datasets.

The summary of overall datasets characteristics is provided in Table I.

We exploited 2 different usual clustering methods, namely k-means [START_REF] Macqueen | Some Methods for classification and Analysis of Multivariate Observations[END_REF], a winner-take-all method, and GNG [START_REF] Fritzke | A growing neural gas network learns topologies[END_REF], a winner-take-most method with Hebbian learning. For text and/or binary datasets we also used the IGNGF neural clustering method [START_REF] Lamirel | Variations to incremental growing neural gas algorithm based on label maximization[END_REF] which has already been proven to outperform other clustering methods, including spectral methods [START_REF] Sun | Investigating the cross-linguistic potential of VerbNet-style classification[END_REF], on this kind of data. We have reported on the method that produced the best results in the following experiments.

As class labels were provided in all datasets and considering that the clustering method could only produce approximate results as compared to reference categorization, we also used purity measures to estimate the quality of the partition generated by the method as regards to category ground truth. Following [START_REF] Sun | Investigating the cross-linguistic potential of VerbNet-style classification[END_REF], we use modified purity (mPUR) to evaluate the clusterings produced, which is computed as follows: For the same reason, we also varied the number of clusters in a range up to 3 times that determined by the ground truth 4 . An index which gave no indication of optimum in the expected range was considered to be out-of-range or diverging index (-out-). We finally designed a process which consists in generating disturbance in the clustering results by randomly exchanging data between clusters to different fixed extents (10%, 20%, 30%) whilst maintaining the original size of the clusters. This process simulated increasingly noisy clustering results and the aim was to estimate the robustness of the proposed estimators.

mP U R = |P | |D| (16)

IV. RESULTS

The results are presented in Tables II-IV. Some complementary information is required regarding the validation process. In the Tables, MaxP represents the number of clusters of the partition with highest mPUR value (Equation 16), or in some cases, the interval of partition sizes with highest stable mPUR value. When a quality index identified an optimal model with MaxP clusters and MaxP differed from the number of categories established by ground truth, its estimation was still considered valid. This approach took into account the fact that clustering would quite systematically produce sub-optimal results as compared to ground truth. The partitions with the highest purity values were thus studied to deal with this kind of situation. For similar reason, all estimations in the interval range between the optimal k (ground truth) and MaxP values were also considered valid. When indexes were still increasing and decreasing (depending on whether they were maximizers or minimizers) when the number of clusters was more than 3 times the number of expected classes, there were considered out-ofrange (-out-symbol in Tables II-IV). The Figure 4 When considering the results presented in Tables II-III, it should first be noted that one of our tested indexes, the Xie-Beni (XB) index never provides any correct answers. These were either out of range (i.e. diverging) or answers (i.e. minimum value when this index was a minimizer) in the range of the variation of k, but too far from ground truth or even too far from optimal purity among the set of generated clustering models. Some indexes were in the low mid-range of correctness and provide unstable answers. This was the cases with the Davis-Bouldin (DB), Calinski-Harabasz (CH), Dunn (DU) and Silhouette (SI) indexes. With higher dimensions, these indexes were generally unable to provide any correct estimation. This phenomenon has already been observed in previous experiments with Davis-Bouldin (DB) and Calinski-Harabasz (CH) indexes [START_REF] Kassab | Feature Based Cluster Validation for High Dimensional Data[END_REF]. Davis-Bouldin (DB) performed slightly better than average on low dimensional data. Our PC index was found to perform significantly better than average on low dimensional data but remains a better low dimensional problem estimator than a high dimensional one. Help from passive features somehow seems mandatory to estimate an optimal model in the case of high dimensional problems. Hence, the EC index which exploited both active and passive features was found to have from far the best performance, with low (Table II) or high dimensional data (Table III). According to our evaluation criteria, this index only returns wrong results in the case of the PEN dataset. However, even in this case its estimation (model of size 9) is still in the close neighbour of the optimal one (model of size 10). Additionally, the EC and PC indexes, were both found to be capable of dealing with binarized data in a transparent manner, which is not the case of some of the usal indexes namely the Xie-Beni (XI) index, and to a lesser extent, Calinski-Harabasz (CH) and Silhouette (SI) indexes. One potential explanation is that binarization process introduces some sparsity that is better dealt by our indexes than by those which use Euclidean distance. Interestingly, on the UCI ZOO dataset, the results of noise sensitivity analysis presented in Table IV underline the fact that noise has a relatively limited effect on the operation of PC and EC indexes. The EC index was again found to have the most stable behavior in that context. The Figure 5 presents a parallel view of the different trends of EC value on non noisy and noisy clustering environment, respectively. It shows that noise tends to lower the index value in an overall way and to soften the trends relatively to changes in k value. However, the index is still able to estimate, either the optimal model in the best case, or a neighbour model in the worst case. The usual indexes do not work as well at all in the same context. For example, the Silhouette index firstly delivered the wrong optimal k values on this dataset before getting out of range when the noise reached 20% on clustering results.

The Davis-Bouldin (DB) and Dunn (DU) indexes were found to shift from a correct to a wrong estimation as soon as noise began to appear. In all our experiments, we observed that the quality estimation depends little on the clustering method. Morever, we noted that the computation time of the index was one of the lowest among the indexes studied. As an example, for the R52 dataset, the EC index computation time was 125s as compared to 43000s for the Silhouette index using a standard laptop with 2,2 GHz quadricore processor and 8 GB of memory.

V. COMPARATIVE EXPLOITATION OF THE INDEXES FOR DIACHRONIC ANALYSIS

In this section, we propose a "real life" estimation of the accuracy of the cluster quality indexes, whenever they are integrated in an operationnal data mining environnement. We thus made the choice to compare their behaviour in the framework of a diachronic analysis environnement working in the context of scientific litterature. The role of such environment is to highlight different kinds of research topics changes or similarities that could occur between time periods (appearing topics, disappearing topics, splitting topics, merging topics, stable topics).

A first version of this environnement working on indexer keywords has been proposed by Lamirel [START_REF] Lamirel | A new approach for automatizing the analysis of research topics dynamics: application to optoelectronics research[END_REF] for demonstrating the feasabilty of a fully unsupervised approach exploiting clutering and unsupervised Bayesian reasoning between views (MVDA) for diachronic mining. A new version of this environmement working on full-text of the papers is up to now under developpement in the context of the ISTEX5 project. A demonstrator of this new environment is already available online 6 and described in Dugué et al [START_REF] Dugué | Diachronic'Explorer : keep track of your clusters ! Research Challenge in Information Science[END_REF].

Figure 6 identifies the different steps of the proposed diachronic analysis process 7 . In this particular experiment, we first constitute a dataset of bibliographic data from the ISTEX project. The ISTEX database is queried to extract papers related to research in medical care between years 1996 and 2010. This results in a dataset of 9779 papers. A basic indexing is exploited on the full text of the documents in order to produce content metadata (single and multi-words indexing terms). The resulting index size is 8347 terms with freq. > 4. A random walk algorithm (here Walktrap [START_REF] Pons | Computing Communities in Large Networks Using Random Walks[END_REF]) exploiting the relationship between the different extracted terms and the publication years is used to extract meta-periods ( [START_REF] Tebbakh | Feature selection and complex networks methods for an analysis of collaboration evolution in science: an application to the ISTEX digital library[END_REF]). At the issue of this process, three meta-periods are extracted (P1=1996-2000, P2=2000-2005, P3=2006-2010). This is between these periods that the diachronic analysis would be lead. This process should allow to monitor topic evolution in medical research across these periods. In each period, we use clustering to group documents of same topics. GNG clustering is therefore launched several times with standard Fritzke parameters settings [START_REF] Fritzke | A growing neural gas network learns topologies[END_REF] on the data of each metaperiod (P1= 4054 data and 3023 terms, P2= 2012 data and 2036 terms, P3= 3713 data and 3288 terms) making varying the number of clusters in a range from 2 to 50 clusters. The different quality indexes are exploited to highlight an optimal model in each period. On this optimal model, the feature selection and contrast ( [START_REF] Lamirel | Optimizing text classification through efficient feature selection based on quality metric[END_REF]) method described in Section II is used to extract characteristics and salient terms for each cluster, i.e. describe cluster topics. These cluster topics descriptions are then used to compute the diachronic analysis and thus monitor the topic evolution across periods. The diachronic analysis is made using unsupervised Bayesian reasoning [START_REF] Lamirel | A new approach for automatizing the analysis of research topics dynamics: application to optoelectronics research[END_REF]. Basically, signals are propagated between clusters of the different periods through the means of the salient features (Figure 7). Matching rules between clusters (topics) are based on the probability of activating a cluster of a period knowing that a cluster of an alternative period has been activated with the signal. Starting from a cluster s of a source period and issuing on a cluster t of a target period, this probability is computed as :

P (t|s) = f ∈Ss∩St G t (f ) f ∈St G t (f ) (17)
where G t (f ) is the contrast of the feature f for the cluster t (Eq. 12).

A match between a cluster of a source period and a cluster of a target period is detected if both source and target cluster generate mutual activity which is superior to the average activity they generate with the clusters of the alternative period (see [START_REF] Lamirel | A new approach for automatizing the analysis of research topics dynamics: application to optoelectronics research[END_REF] for more details). If such match exists, the set S st = S s ∩ S t of salient features that are shared between the two aforementioned clusters is called the matching kernel.

The quality indexes have a major role in the process of diachronic analysis because the more accurate will be the choice of the optimal cluster model for each time period, the better and the more accurate will be the temporal alignment between periods and consequently the temporal matching process between those latter. Our hypothesis (that could be experimentally verified) is thus that an accurate model selection will produce the larger number of matches, with matching kernels of the largest sizes and with the highest matching probability. We consequently exploit two complementary criteria for the evaluation of the behaviour of the indexes:

• The total number of matches that can be found between the periods using the optimal clustering models provided by the index. • A matching quality criteria (QMA) combining the number of matches, the size of the matching kernels and the matching probability. This criteria is expressed as :

QM A = (i,j)∈M |S ij | * P (i|j) + P (j|i) 2 (18)
where M represents the set of couples of clusters of different periods for which a match has been detected.

In Table V, we give the results of our evaluation on the corpus we constitued from the ISTEX database which is related to medical care research. It highlights that, similarly to our former experiments (see Section IV), some indexes are unable to find any optimal model (being out-of-range) whatever time period is considered. Some indexes, like Dunn (DU) and our PC index, work partially, finding optimal model only in some periods. Alternatively, Calinsky-Harabasz (CH) and our EC index are able to identify optimal models in all periods.

When the evaluation criteria figuring out the quality of the diachronic analysis (i.e. temporal matches) is exploited, it turns out that the best temporal matching results are produced with the help of EC index that reached the best values both for the number of detected matches and the richness and the accuracy of the matches (QMA criteria). Additionally, despite the number of considered periods, Calinsky-Harabasz (CH), which identified optimal models for 3 periods, provided worth results than our PC index, which identified optimal models only for two periods, relatively to the number of matches. However, the exploitation of Calinsky-Harabasz (CH) index produced better quality matches than PC index as it is figured out by its higher values of QMA criteria.

VI. CONCLUSION

We have proposed a new set of indexes for clustering quality evaluation relying on feature maximization approach. This method exploits the information derived from features which could be associated to clusters by means of their associated data. The experiments we achieved showed that most of the usual quality estimators do not produce satisfactory results in a realistic data context and that they are additionally sensitive to noise and perform poorly with high dimensional data. Unlike the usual quality estimators, one of the main advantages of our proposed indexes is that they produce stable results in cases ranging from a low dimensional to high dimensional context and also require low computation time while easily dealing with binarized data. Their stable operating mode with clustering methods which could produce both different and imperfect results also constitutes an essential advantage.

We have performed experiments in two different contexts including a "real life" context related to diachronic analyis environment. Both experiments confirm the clear advantages of our new indexes, especially the ones of our EC quality index.

However, further experiments are required using both an extended set of clustering methods and a larger panel of high dimensional datasets to confirm this promising behavior. Especially the influence of the sparsity and the one of cluster overlapping ratio on the performance of our indexes must be more precisely evaluated. Taking a larger panel of indexes, including score functions and entropy based indexes would be also a complementary and important issue.

Additionally, we plan to test the ability of our indexes to discriminate between correct and degenerated clustering results in the context of large and heterogeneous datasets.

Fig. 1 .

 1 Fig. 1. Principle of feature F-measure computation for sample data.

Fig. 2 .

 2 Fig. 2. Principle of computation of overall feature F-measure average and elimination of irrelevant features.

  P = {d ∈ D | prec(c(d)) = g(d) ∧ |c(d)| > 1} with D being the set of exploited data points, c(d) a function that provides the cluster associated to data d and g(d) a function that provides the gold class associated to data d. Clusters for which the prevalent class has only one element are considered as marginal and are thus ignored.

  draws the trends of evolution of EC and PC indexes in the case of the R52 dataset. It highlights what is a suitable index behaviour (EC index) and in a parallel way what represents the out-ofrange index behaviour we mentioned before (PC index).

Fig. 4 .

 4 Fig. 4. Trends of PC and EC indexes on Reuters R52 dataset.

Fig. 5 .

 5 Fig. 5. Trends of EC indexes on UCI ZOO dataset with and without noise.

Fig. 6 .

 6 Fig. 6. General architecture of the diachronic analysis environment.

Fig. 7 .

 7 Fig. 7. Overall view of the principle of identification of topic matching between periods (the term label is used here for feature).

TABLE I DATASETS

 I OVERALL CHARACTERISTICS (BINARIZATION OF IRIS DATASET RESULTS IN 12 BINARY FEATURES OUT OF 4 REAL-VALUED FEATURES).

		IRIS IRIS-b WINE	PEN	SOY ZOO VRBF	R8	R52
	Nbr. class	3	3	3	10	16	7	12-16	8	52
	Nbr data	150	150	178	10992	292	101	2183	7674 9100
	Nbr feat.

TABLE II OVERVIEW

 II OF THE INDEXES ESTIMATION RESULTS ON LOW DIMENSIONAL DATA (BOLD NUMBERS REPRESENT VALID ESTIMATIONS).

							Number
		IRIS	IRIS-b	WINE PEN	SOY	of correct
							matches
	DB	2	5	5	7	19	2/5
	CH	2	3	6	8	5	1/5
	DU	1	1	8	17	8	0/5
	SI	4	2	7	14	14	1/5
	XB	2	7	-out-	19	24	0/5
	PC	3	3	4	9	16	4/5
	EC	3	3	4	9	16	4/5
	MaxP	3	3	5	11	19
	Method K-means K-means	GNG	GNG GNG

TABLE III OVERVIEW

 III OF THE INDEXES ESTIMATION RESULTS ON AVERAGE TO HIGH DIMENSIONAL DATA (BOLD NUMBERS REPRESENT VALID ESTIMATIONS).

						Number
		ZOO	VRBF	R8	R52	of correct
						matches
	DB	8	-out-	5	58	1/4
	CH	4	7	6	-out-	1/4
	DU	8	2	-out-	-out-	1/4
	SI	4	-out-	-out-	54	1/4
	XB	-out-	23	-out-	-out-	0/4
	PC	7	18	-out-	-out-	1/4
	EC	7	15	6	52	4/4
	MaxP	10	12-16	6	50-55
	Method IGNGF IGNGF IGNGF IGNGF

TABLE IV INDEXES

 IV ESTIMATION RESULTS IN THE PRESENCE OF NOISE (UCI ZOO DATASET).

		ZOO	ZOO Noise 10%	ZOO Noise 20%	ZOO Noise 30%	Number of correct matches
	DB	8	4	3	3	1/4
	CH	4	5	3	3	0/4
	DU	8	2	2	2	1/4
	SI	14	-out-	-out-	-out-	0/4
	XB	-out-	-out-	-out-	-out-	0/4
	PC	6	4	11	9	1/4
	EC	7	5	6	9	2/4
	MaxP	10	7	10	10
	Method IGNGF	IGNGF	IGNGF	IGNGF

TABLE V OVERVIEW

 V OF THE INDEXES ESTIMATION RESULTS AND RESULTING QUALITY FOR DIACHRONIC ANALYSIS (THE HIGHER NUMBER OF MATCHES AND QMA, THE BETTER)

		Opt. Period P1	Opt. Period P2	Opt. Period P3	Number of temporal matches	QMA evaluation criteria
	DB	-out-	-out-	-out-	0	0
	CH	3	4	4	5	15.26
	DU	14	20	-out-	6	8.60
	SI	-out-	-out-	-out-	0	0
	XB	-out-	-out-	-out-	0	0
	PC	23	23	-out-	9	10.61
	EC	10	6	8	13	27.20

Using p-value highlighting the significance of a feature for a cluster by comparing its contrast to unity contrast would be a potential alternative to the proposed approach. However, this method would introduce unexpected Gaussian smoothing in the process.

As regards the principle of the method, this type of selected features inevitably have a contrast greater than 1 in some other cluster(s) (see eq. 9 for details).

http://www.research.att.com/∼lewis/reuters21578.html

We choose too discard models of size 1 (one single cluster) in our experiments. First, the experimented indexes are not planed to produce results (or only incoherent ones) for such specific case. Second, such models are irrelevant because they correspond to trivial clustering operation.

The ISTEX project (Excellence Initiative for Scientific and Technical Information) is part of the "Investments for the Future" program initiated by the French Ministry for Higher Education and Research (MESR).

See https://github.com/nicolasdugue/istex-demonstrateur

Diachronic analysis and feature selection code can be found at https://github.com/nicolasdugue/istex