Florian Metze
email: fmetze@cs.cmu.edu

Nitendra Rajput
email: rnitendra@in.ibm.com

Xavier Anguera

Marelie Davel

Guillaume Gravier

Charl Van Heerden

Gautam V Mantena

Armando Muscariello

Kishore Pradhallad

Igor Szöke

Kishore Prahallad

Javier Tejedor

The Spoken Web Search task at MediaEval 2011

Keywords: low-resource speech recognition, evaluation, spoken web, audio search, spoken term detection

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

INTRODUCTION

The "Spoken Web Search" task of MediaEval 2011 involves searching for audio content, within audio content, using an audio content query. By design, the data consisted of only 700 utterances in Telephony quality from four Indian languages (English, Gujarati, Hindi, Telugu), without language labels. The task therefore required researchers to build a language-independent audio search system so that, given a query, it should be able to find the appropriate audio file(s) and the (approximate) location of query term within the audio file(s). Performing language identification, followed by standard speech-to-text is not appropriate, because recognizers are typically not available in these languages. Evaluation was performed using standard NIST metrics for spoken term detection [START_REF] Fiscus | Results of the 2006 spoken term detection evaluation[END_REF]. For comparison, participants could also search using the lexical form of the query, but dictionary entries for the search terms were not provided, and we are not reporting results here. This work is the first in which results under this condition have been reported, and encompasses languages or dialects with no written form.

This task has been suggested by IBM Research India, and is using data provided by this group, see [START_REF] Kumar | WWTW: The world wide telecom web[END_REF], to be able to go bayond searching through the meta-data related to the audio content only [START_REF] Diao | Faceted search and browsing of audio content on spoken web[END_REF].

Recently, there has been a great interest in algorithms that allow rapid and robust development of speech technology for any language, particularly with respect to search, see for example [START_REF]IARPA-BAA-11-02[END_REF]. Today's technology was mostly developed for transcription of English, with markedly lower performance on non-English languages, and still covering only a small subset of the world's languages.

This evaluation attempts to provide an evaluation corpus and baseline for research on language-independent search and transcription of real-world speech data, with a special focus on low-resource languages, in order to provide a forum for original research ideas.

In this paper, we will give an overview of the different approaches submitted to the evaluation [START_REF] Anguera | Telefonica system for the spoken web search task at MediaEval 2011[END_REF][START_REF] Barnard | Phone recognition for spoken web search[END_REF][START_REF] Mantena | SWS Task: Articulatory phonetic units and sliding DTW[END_REF][START_REF] Szöke | BUT-HCTLab approaches for spoken web search[END_REF][START_REF] Muscariello | IRISA MediaEval 2011 spoken web search system[END_REF], analyze the results, and summarize the findings of the evaluation workshop [START_REF] Rajput | Spoken web search[END_REF].

DESCRIPTION OF TASK AND DATA

Participants were provided with a dataset that has been kindly made available by the Spoken Web team at IBM Research India [START_REF] Kumar | WWTW: The world wide telecom web[END_REF]. The audio content is spontaneous speech that has been recorded using commonly available land-line and mobile phone equipment in a live setting by low-literate users. While most of the audio content is related to farming practices, there are other domains as well. Data was collected from the following domains: (1) Sugarcane information by farmers (North India, Hindi language, 3000 users), (2) Village portal by villagers (South India, Telugu language, 6500 users), (3) Farming knowledge portal (West India, Gujarati language, 175 users), (4) Mixed content, e.g. job portal, event agenda (South and North India, English language, 80 users).

Table 1 provides details of the selected data. The labels identifying the language were intentionally not provided either in the development or the evaluation dataset.

The development set contains 400 utterances (100 per language) or "documents", and 64 queries (16 per language), all provided as digital recordings in 8kHz/ 16bit quality. For each query (and document on the development data), Romanized lexical transcriptions in UTF-8 encoding were also provided. The transcriptions had been generated by native speakers. For each development document, up to n matching queries were provided to participants, but not the exact location of the match within the document. A "match" is defined by the word transcription of the query appearing identically in the document. Sequences of one to three words were included as queries. they were selected to include typical target phrases, names, etc., which occur with a minimum frequency. Evaluation data consists of 200 utterances (50 per language), and 36 queries (9 per language), selected using the same criteria. Participants were allowed to use any additional resources they might have available, as long as their use is documented.

Participants received development audio data (documents and queries) as well as matches between queries and documents, and had five weeks to develop systems, before they also received the evaluation audio data. Results were due another five weeks later. There was no overlap between development and evaluation speakers, samples, and queries. Participants also attempted to detect occurrences of development queries on evaluation data, as well as evaluation queries on development data. The purpose of requiring these two additional, contrastive conditions was to see how critical tuning is for the different approaches: participants knew their performance for "dev queries" on "dev documents", so for evaluation we will evaluate the performance of unseen "eval queries" on previously known "dev documents" (which could have been used for unsupervised adaptation, etc.), known queries (for which good classifiers could have been developed) on unseen data, and unseen queries on unseen utterances (the primary condition). No group however achieved reasonable performance on the dev-eval and eval-dev conditions, and we assume this is due to the difficulty in choosing good parameters for an overall low number of positive events, and acoustic mismatch, so we will not discuss these results in the following.

Data was provided as a "term-list" XML file, in which the "termid" corresponds to the file-name of the audio query. This information was distributed along with a modified version of the NIST 2006 Spoken Term Detection (STD) evaluation scoring software [START_REF] Fiscus | Results of the 2006 spoken term detection evaluation[END_REF]. The primary evaluation metric was ATWV (Average Term Weighted Value), computed with the default values for the 2006 STD evaluation with respect to density of search terms, etc., but with "similarity" and "find" thresholds set to 20 s.

SYSTEM DESCRIPTIONS

In the following, we describe a selection of systems submitted to the evaluation. More systems were submitted, but the following ones provide the greatest insight and variety of approaches.

Broadly speaking, IRISA and TID submitted "zero-knowledge" approaches trained only on the available data, while BUT-HCTLabs and MUST submitted phone-based systems, which leveraged additional information. IIIT submitted an articulatory-feature-based approach, which also leveraged additional audio data.

GMM/HMM Term Modeling -BUT-HCTLabs

This approach is inspired by filler model-based acoustic keyword spotting, with a standard Viterbi-based decoder slightly modified to compute a likelihood ratio [START_REF] Szöke | Phoneme based acoustics keyword spotting in informal continuous speech[END_REF]. However, instead of the typical representation of both query model consisting of the corresponding phone transcription of the query term and filler/background model consisting of a free phone loop, we stuck with an acoustic representation of both the query term and the filler/background model, to maintain the language-independency, as follows: (1) the query model is represented with a Gaussian Mixture Model/Hidden Markov Model (GMM/HMM) whose number of states is 3 times the number of phones according to the phone recognition with 1 GMM component each, (2) the background model is a GMM/HMM with 1-state modeled with 10-GMM components. Queries represented by a single phone have been modeled with 6 states as if the query contained 2 phones to prevent the system from generating many false alarms for those queries. We used the number of phones output by a Slovak recognizer to derive the number of states of each query model due to its best performance in terms of the Upper-bound Term Weighted Value metric (UBTWV) [START_REF] Szöke | Hybrid word-subword spoken term detection[END_REF] among Czech, English, Hungarian, Levantine, Polish, Russian, and Slovak. The score assigned by the acoustic keyword spotter to each detection is the likelihood ratio divided by the length of the detection. To deal with the score calibration and some problematic query length, detections were post-processed by 'Filtering" according to a length difference from an "average length" criterion. The average length of a query is calculated as the average length of speech (phones) across all the phone recognizers, except the Polish one due to its worse performance in the development data. Next, each detection is re-scored: the detection score remains the same if the detection length is longer than 80% and shorter than 140% of the average query length. Otherwise the score is lowered the shorter/longer the detection is according to the original query.

Features used for background and query modeling were obtained as follows: (1) the 3-state log-phone posteriors obtained by concatenating all the 3-state phone posteriors according to each feature extractor (corresponding to the recognizers of Czech, English, Hungarian, Levantine, Polish, Russian and Slovak languages) are applied a Karhunen-Loeve transform (KLT) for each individual language, (2) we keep the features that explain up to 95% of the variance after KLT for each individual language, (3) we build a 152-dimensional feature super-vector, from them. The KLT statistics have been computed from the development data provided by the task organizers and next applied on the evaluation data. The 3-state phone posterior estimator [START_REF] Tejedor | Novel methods for query selection and query combination in query-by-example spoken term detection[END_REF] contains a Neural Network (NN) classifier with a hierarchical structure called bottle-neck universal context network. It consists of a context network, trained as a 5-layer NN, and a merger that employs 5 context net outputs. The nets use ≈ 40 phones, ≈ 1300 nodes in the hidden layer, ≈ 480 nodes of the hidden layer in the merger net, ≈ 120 nodes in the posterior output layer, see [START_REF] Tejedor | Novel methods for query selection and query combination in query-by-example spoken term detection[END_REF].

Articulatory Features and Sliding DTW -IIIT

The primary motivation for this approach is to have speech specific features rather than language specific features like phone models. The advantage is that the articulatory phonetic units (selected well) could represent a broader set of languages. This would enable us to build articulatory units from one language and use it for other languages. We used 15 articulatory categories.

Audio content is decoded into their corresponding articulatory units using HMM models with 64 Gaussian mixture models using HTK. The models were built using 15 hours of telephone Telugu data, consisting of 200 speakers. Using the decoded articulatory phonetic output, tri-grams were used for indexing. The audio query was also decoded and the audio segments were selected, if there was a match in any of the tri-grams. Let t start and t end be the start and the end time-stamps for the tri-gram in the audio content that matches with one of the tri-grams from the audio query. Then the likely segment from the audio content would be between (tstartaudio query length) and (t end + audio query length).

These time stamps would provide the audio segments that are likely to contain the audio query. Sliding Dynamic Time Warping (DTW) search was applied on these audio segments to obtain the appropriate time stamps for the query.We propose an approach where we consider an audio content segment of length twice the length of the audio query, and a DTW is performed. After a segment has been compared the window is moved by one feature shift and DTW search is computed again. MFCC features, with window length 20 msec and 10 msec window shift, have been used to represent the speech signal. Consider an audio content segment S and an audio query Q. Construct a substitution matrix M of size qxsq where q is the size of Q and sq = 2q. We also define M [i, j] as the node measuring the optimal alignment of the segments Q[1 : i] and S[1 : j].

During DTW search, at some instants M [q, j](j <= sq) will be reached. Then the time instants from column j to column sq are the possible end points for the audio segment. Euclidean distance measure has been used to calculate the costs for the matrix M . The scores corresponding to all the possible end points are considered for k-means clustering. For k = 3, mean scores are calculated. The segment with the lowest score among segments overlapping at least 70% is selected.

Template Matching -IRISA

This system purely relies on pattern matching, exploiting different pattern comparison approaches to deal with variability in speech.

The system operates at the acoustic level, with limited prior knowledge eventually embedded in posteriorgrams. As in most (if not all) pattern matching approaches, a segmental variant of DTW is used to efficiently search for the query in each document. Candidate hits are further evaluated with self-similarity matrix comparison. Details can be found in [START_REF] Muscariello | A zero-resource system for audio-only spoken term detection using a combination of pattern matching techniques[END_REF].

Pattern Matching with DGMM Posteriorgrams -TID

This system is based exclusively on a pattern-matching approach, which is able to perform a query-by-example search with no prior knowledge of the acoustics or language being spoken, computed on the non-silence part of the data. For the main submission we construct a Discriminative Gaussian Mixture Model (DGMM) [START_REF] Anguera | Speaker independent discriminant feature extraction for acoustic pattern-matching[END_REF] and store the Gaussian posterior probabilities (normalized to sum to 1) as features. Differently from standard GMM-posteriors, in DGMM modeling after the standard Enhanced Max Margin Learning (EMML) GMM training step we perform a hard assignment of each frame to their most likely Gaussian and retrain the Gaussian's mean and variance to optimally model these frames. This last step tries to solve a problem that EMML training has, which focuses on optimizing the Gaussian parameters to maximize the overall likelihood of the model on the input data, but not on discriminating between the different sounds in it. By performing the last assignment and retraining step we push Gaussians apart from each other to better model individual groups of frames depending on their location and density. This results in Gaussians with much less overlap, thus obtaining more discriminative posterior probability feature vectors. For this evaluation, only the development data from the SWS task was used for training.

In the comparison step, given two sequences, X and Y of posterior probabilities, respectively obtained from the query and any given phone recording, we compare them using a DTW-like algorithm. The standard DTW algorithm returns the optimum alignment between any two sequences by finding the optimum path between their start (0, 0) and end (x end , y end ) points. In our case we constrain the query signal to match between start and end, but we allow the phone recording to start its alignment at any position (0, y) and finish its alignment whenever the dynamic programming algorithm reaches x = x end . Although we do not set any global constraints, the local constraints are set so that at maximum 2-times or 1 2 -times warping is allowed. In addition, at every matching step we normalize the scores by the length of the optimum path up to that point, slightly favoring diagonal matches.

Phone Recognition -MUST

Aiming at both speaker independence and robustness with respect to recognition errors in the spoken queries, we implemented a phonebased system. The main dataset used for acoustic modeling was 60 hours of spontaneous conversations in colloquial Hindi. There are 996 native Hindi speakers and all conversations range between 1 and 4 minutes in duration. All conversations are transcribed and a basic pronunciation dictionary is provided.

A standard HMM-based recognizer was constructed using the Hindi data. The list of mono-phones was reduced from 62 to 21 units in order to work with a small set of broad but reliable classes, appropriate to the later scoring tasks. The speech data and transcriptions provided were cleaned using an aggressive form of garbage modeling, and the resulting data used to Maximum-A-Posteriori-adapt the Hindi acoustic models to the task domain (and languages).

Unconstrained phone recognition of both the query terms and the content audio is employed to represent these recordings as phone strings. A dynamic-programming (DP) approach with a linguistically motivated confusion matrix then finds regions in the content phone strings that correspond closely to one or more query strings. The resulting DP score (normalized by phone length) is used as confidence measure.

RESULTS AND ANALYSIS

Figure 1 shows the results of the five approaches described above on the development data, which participants could use to develop and tune their approaches. Using the provided metric, three approaches achieved maximal ATWVs of 0.1 or greater, detecting about 15% of events, with very low false alarm probabilities, as required by the parameters chosen to compute ATWV.

Figure 2 shows the corresponding results on the unseen evaluation data. The same three approaches could be run successfully on the unseen evaluation data, and the choice of decision thresholds was remarkably stable, given the little amount of available data. The "TID" query-by-example approach generalizes best to unseen data, while the phone-based "MUST" approach achieves an identical performance on the evaluation data as on the development data. The "BUT-HCTLabs" HMM/GMM approach also generalizes well.

It is interesting to note that under the given conditions, the zeroknowledge approaches could perform very similarly to the phonebased approaches, which relied on the availability of matching data from other languages. Follow-up work on larger datasets will be required to investigate the scalability of these systems.

OUTLOOK

These initial results on a very low-resource spoken term detection task show promising results, which will be explored further and improved upon in future work. It is interesting to note that very diverse approaches could achieve very similar results, and future work should include more evaluation criteria, such as amount of external data used, processing time(s), etc., which were deliberately left unrestricted in this evaluation, to encourage participation.

With respect to the amount of data available, this evaluation was even harder than the research goals proposed by for example IARPA's Babel [START_REF]IARPA-BAA-11-02[END_REF] program, yet results have been achieved that appear useful in the context of the "Spoken Web" task, which is targeted primarily at communities that currently do not have access to Internet. Many target users have low literacy skills, and many speak in languages for which fully developed speech recognition systems won't exist even for years to come. Yet, access to highly variable information is critical for their development.

The organizers and participants are currently working to prepare more and varied data for future evaluations in a similar style, for example the Lwazi corpus [START_REF] Barnard | ASR corpus design for resource-scarce languages[END_REF]. We will attempt to make this, and other, future evaluation corpora available to a wider audience, in order to promote insight and progress on making speech technology available independent of the speaker's language.

Fig. 1 .

 1 Fig. 1. Results (ATWV) on development data.

Fig. 2 .

 2 Fig. 2. Results (ATWV) on evaluation data.

ACKNOWLEDGMENTS

The authors would like to acknowledge the MediaEval Multimedia Benchmark (http://www.multimediaeval.org/mediaeval2011/index.html), and IBM Research India for collecting and providing the audio data and references used in this research. The organizers would also like to thank Martha Larson from TU Delft for organizing this event, and the participants for their hard work on this challenging evaluation.


Cédric Penet

Claire-Hélène Demarty

Guillaume Gravier

Patrick Gros

MULTIMODAL INFORMATION FUSION AND TEMPORAL INTEGRATION FOR VIOLENCE DETECTION IN MOVIES

Keywords: Bayesian networks, structure learning, violence detection, multimodal fusion, temporal integration

This paper presents a violent shots detection system that studies several methods for introducing temporal and multimodal information in the framework. It also investigates different kinds of Bayesian network structure learning algorithms for modelling these problems. The system is trained and tested using the MediaEval 2011 Affect Task corpus, which comprises of 15 Hollywood movies. It is experimentally shown that both multimodality and temporality add interesting information into the system. Moreover, the analysis of the links between the variables of the resulting graphs yields important observations about the quality of the structure learning algorithms. Overall, our best system achieved 50% false alarms and 3% missed detection, which is among the best submissions in the MediaEval campaign.

INTRODUCTION

Violence detection in movies is a use case at Technicolor, which involves helping users choose movies that are suitable for children in their families by showing them the most violent segments.

This use case raises the issue of defining violence. Violence is a very subjective notion and may have several forms, such as physical violence or verbal violence. People perceive it differently from one person to another. Furthemore, in the context of movies, it may be spread over several modalities, and each event duration is variable. These characteristics highlight the complexity of the task.

This also appears in the small amount of literature on this subject over the past years. Until recently, it focused mainly on monomodal and static systems such as in [START_REF] Liang-Hua | Action Scene Detection With Support Vector Machines[END_REF], where the authors developed a system based on support vector machines and visual features to detect action scenes in movies. The work in [START_REF] Pikrakis | Gunshot detection in audio streams from movies by means of dynamic programming and Bayesian networks[END_REF] is an audio-based concept detection system. To our knowledge, it is also the only paper to introduce temporal information in the system through dynamic programming. More recently, the same authors combined audio and visual information in [START_REF] Giannakopoulos | Audio-Visual Fusion for Detecting Violent Scenes in Videos[END_REF]. They added a visual activity detector and integrated it into their previous system through a nearest neighbour classifier to infer the presence of violence. In that paper, they no longer use any dynamic programming. To summarise, state-of-the-art systems use either multimodal information or temporal information but not both, and to the best of our knowledge, these characteristics have not been extensively studied.

In our opinion, the structure of the events requires the systems to integrate both multimodal and temporal information. For temporal integration, we propose to use contextual features as in [START_REF] Baghdadi | Apprentissage de structure dans les réseaux bayésiens pour la détection d'évènement vidéo[END_REF] and to study their effect. We also propose to compare different types of multimodal fusion methods and we will conclude on the interest of both these subjects for detecting violent shots in movies. A direct comparison of our system with prior works is difficult as they are not built using the same dataset and the same definition of violence. Hence, it was tested in the context of the MediaEval 2011 Affect Task [START_REF] Demarty | The MediaEval 2011 Affect Task: Violent Scenes Detection in Hollywood Movies[END_REF], which aims at comparing methods for detecting violent shots in movies using a common definition of violent events and a common dataset. A common definition, the task considers sequences in which an action or accident resulted in human pain or injury. It attempts to narrow the scope of the task, therefore reducing its subjectivity. The corpus is composed of 15 movies, hence increasing the size of the dataset compared to the literature. Through this common framework, the MediaEval 2011 Affect Task provided comparison of our technique with 5 different state-of-the-art systems.

The system developed is presented in section 2. In section 3.1, we present the dataset and evaluation metric. Finally, the results and their analysis are presented in section 3.2 and section 3.3.

SYSTEM DESCRIPTION

The system we developed aims at detecting violent video shots in movies. It contains four different parts: the features extraction, the classification step, the temporal integration and the fusion of modalities.

Features extraction

Movies have several components that convey different information, namely audio, video, subtitles. . . We chose to extract features from the audio and video modalities. The audio features are the energy, the centroid, the asymmetry, the zero crossing rate (ZCR) and the flatness, which are classical stateof-the-art low level features. They were extracted from 40 msec frames with 20 msec overlap and then averaged over a shot. The video features for each shot are the shot duration, the average number of blood-like color pixels in the HSV space, the average activity and the number of flashes (high luminance variation over three frames 1 ). The features histograms were then rank-normalised over 22 values for each movie.

Classification

We chose to use Bayesian networks (BN) [START_REF] Heckerman | A Tutorial on Learning with Bayesian Networks[END_REF] as a probability distribution modelisation process. BN exhibit interesting features: in particular, they link the variables in a graph whose structure may be learned. On the downside, they consider each feature independently. During the inference stage, in the case of classification, the algorithm outputs the marginal probability for the sample of being violent. The decision is then taken by thresholding this probability. The huge number of possible graphs is another drawback of BN, which is why structure learning algorithms were developed. They have been successfully used in the literature for soccer action detection [START_REF] Baghdadi | Apprentissage de structure dans les réseaux bayésiens pour la détection d'évènement vidéo[END_REF], however their use in multimodal event detection appears to be quite recent. There exists two families of structure learning algorithms. The first one tries to find relations between variables using an independence test. The main drawback of these methods is that they are computationally intensive, especially when the number of variables increases. The second family groups score-based algorithms. They scan the different possible graphs and optimise a score function that is a trade-off between the likelihood of the data and the complexity of the graph. They mostly differ in the heuristics used to scan the possible graphs. Both these families are supervised.

For this paper, we focused on two score-based structure learning algorithms2 , which we compare to the naive case:

• The naive Bayesian network is the simplest network. It links the features to the classification node3 assuming that they are all independent with respect to this node. • The forest augmented naive Bayesian network (FAN) is introduced in [START_REF] Lucas | Restricted Bayesian Network Structure Learning[END_REF]. It relaxes the features independence assumption by learning a forest between the features before connecting them to the classification node. • The K2 [START_REF] Cooper | A Bayesian method for the induction of probabilistic networks from data[END_REF] algorithm is a state-of-the-art score-based greedy search algorithm. It requires a node ordering to decide for a given node which nodes may be its children, hence reducing the number of graphs to test.

Temporal integration

In order to account for the temporal structure of movies, we first used contextual features. However, contrary to what is done in [START_REF] Baghdadi | Apprentissage de structure dans les réseaux bayésiens pour la détection d'évènement vidéo[END_REF], we did not restrict the contextual features to the five next video shots and also used the features from the five previous video shots. Hence, considering

X t = [x 1 , • • • , x K ]
the feature vector for sample at time t, the contextual features vector becomes

X c t = [X t-n , • • • , X t , • • • , X t+n ] with n = 5.
We also considered two types of temporal filtering over 5 samples, that are used for smoothing decisions:

• Taking the maximum vote decision over a few samples, after probability thresholding.

• Averaging the samples probabilities of being violent, before probability thresholding.

Modalities fusion

As for multimodal fusion, two cases were considered: late (LF) and early fusion (EF). For early fusion, we simply concatenated the features from both modalities before learning, while for late fusion, we fused the probability of both modalities for the i th shot s i using: ) is the probability of being violent for the audio (respectively video) modality for the i th shot. This rule gives high scores when both audio and video find a violent segment, a low score if they both do not and an intermediate score if only one answers yes.

P si f

EXPERIMENTAL RESULTS

Protocol

The MediaEval 2011 Affect Task [START_REF] Demarty | The MediaEval 2011 Affect Task: Violent Scenes Detection in Hollywood Movies[END_REF] corpus used for experimenting the system is composed of 12 Hollywood movies for training and 3 movies for testing. These movies were calibrated to cover a wide range of violence types in both sets. The total amount of available data is about 30 hours of video, which corresponds to 21,608 shots for the development data and 4,500 shots for the test data. A detailed description may be found in [START_REF] Demarty | The MediaEval 2011 Affect Task: Violent Scenes Detection in Hollywood Movies[END_REF].

For evaluation, the metric used for the MediaEval 2011 Affect Task is a cost function (MC) of the shot false alarms (FA) and missed detections (M) rates: This cost function reflects the fact that missing a violent shot has much bigger consequences than having a false alarm. However, it implies that best score is mostly obtained when each shot is classified as violent, meaning a FA rate of 1 and a M rate of 0. The problem boils down to a FA reduction problem. For the sake of analysis, we also studied the FA and M curves which are proposed in Figure 1.

M C = 10 * % M + 1 * % F A (2)

Results

Table 1 presents the results for 12 selected experiments chosen according to the MC metric and the false alarms vs. missed detections curves among all the possible combinations of the system. For the audio and the video experiments, the two best experiments according to each metric were chosen, while for the multimodal ones (namely early and late fusion), only the best ones are reported. The first thing to notice is that most of the obtained scores have values lower than 1 which is better than the simple case where each sample is classified as violent, i.e. FA=100% and M=0%.

As most of the selected runs use temporal information, it seems clear that the introduction of temporality in the systems provides better results, especially for contextual data, which confirms the importance of the temporal structure of movies. The depth used for contextual data has been chosen arbitrarily, however considering other depths could be interesting. On the downside, it seems that these results depend on the algorithm used for learning the BN structures: FAN seems to work better with non contextual data contrary to the K2 algorithm. This is confirmed by the analysis of the additional experiments not presented in the paper.

The effect of multimodal fusion may be seen on Figure 1 and Table 1. It seems that EF provides worse results than LF and all the other experiments, selected or not selected, even though we thought it would improve the results. The analysis of the produced graphs (see Figure 2) yields that for non con-Fig. 1: False alarms vs. missed detection for each selected experiment. The legend is organised as in table 1. textual data the algorithm only links the video features (red nodes) to the violence node (blue node), while the contextual data graphs are messy. Both these results indicate that the features from the two modalities are not correlated. In our opinion, it is mainly due to the semantic level of the features used, as the audio ones are low level features and the video ones mid level features, and they cannot be compared as such.

Graph analysis

Graph analysis produces very interesting results, particularly the analysis of the K2 graphs, as the approach is more generic than the others. A good example of the quality of the structure learning algorithm is proposed in Figure 3. Firstly, the links between features may be easily interpreted: the activity is linked to the shot length as the shot detector used tends to oversegment when the activity is high and blood has been found uncorrelated to violence which is legitimate considering the definition of violence adopted and the fact that the presence of blood highly differs from one movie to another. Furthermore, it seems that the algorithms produce a strict tem- poral structure, i.e. the features from time t = n are linked together and not to features from different times unless they are in temporal chains. There are two temporal chains in these graphs: activity and blood. It is easy to see that these features have a temporal coherency. On the other hand, the flash feature is only connected to the violence node and forms no chain, which is again logical as the flash feature only detects high luminance variations, and has therefore no well defined temporal structure. Comparable conclusions may be drawn from an example of an audio graph (see Figure 4).

On the downside, these results depend on the movie the system is used on: the best results were obtained for the Bourne identity, then Kill Bill and finally the Wizard of Oz. We think that it is mainly due to the low number of variables considered (4 for the video modality and 5 for the audio modality), which is probably not sufficient for the system to model each type of violence and generalise well. Again, further investigation is needed.

CONCLUSION

This paper presented a Bayesian network framework for temporal integration and multimodal information fusion. First, it was shown experimentally that the introduction of temporality in the framework through context and/or temporal smoothing helped improving the results. It was also shown that early fusion with features that have different natures lead to poor results, while late fusion seemed to be more promising. Finally, the structure learning algorithm output logical graphs with respect to the provided data: they were able to capture the links between features, detect the most significant variables and provide a coherent temporal structure.

This work provides a promising baseline for future work on the subject. We have several improvement ideas. Firstly, we will investigate further the contextual data and test other structure learning algorithms. Secondly, we want to add features from the text modality, as we think it also contains important information on the violent nature of the video shots.

Fig. 2 :

 2 Fig. 2: Example of an early fusion graph using non contextual variables and learned with the K2 algorithm (V: violence, A: asymmetry, F: flatness, E: energy, C: centroid, ZCR: zero crossing rate, B: blood, AC: activity, SL: shot lenght, FL: flashes). The red color nodes are the video modality nodes connected to the violent node (in blue).

Fig. 3 :

 3 Fig. 3: Video graph using contextual variables and K2 algorithm. Each color corresponds to one group of contextual features.

Fig. 4 :

 4 Fig. 4: Audio graph using contextual variables and K2 algorithm. Each color corresponds to one group of contextual features.

  THIS WORK WAS PARTLY ACHIEVED AS PART OF THE QUAERO PROGRAM, FUNDED BY OSEO, FRENCH STATE AGENCY FOR IN-NOVATION. WE WOULD LIKE TO ACKNOWLEDGE THE MEDIAEVAL MUL-TIMEDIA BENCHMARK HTTP://WWW.MULTIMEDIAEVAL.ORG/ AND IN PARTICULAR THE AFFECT TASK 2011 FOR PROVIDING THE DATA USED IN THIS RESEARCH.

Table 1 :

 1 Selected experiments results ordered by modali-

	Modality		Temporal integration	Structure learning	MediaEval cost
	Late	C	A: Me V: Ma A: N V: K2	0.761
	Video	C -	Ma Me Ma Ma	K2 K2 N FAN	0.784 0.840 0.950 1.009
			Me	K2	0.805
	Audio	C	Me Ma	N K2	0.843 0.943
		-	-	K2	0.967
	Early Fusion	C	Ma -	K2 K2	0.892 0.998

Fusion A: Me V: Me A: N V: K2 0.774 ties used (MC: MediaEval cost, C: contextual, N: naive BN, Ma: max decision vote, Me: mean probability).

Similar to http://users.iit.demokritos.gr/ ˜amakris/ Violence.html

We used the Bayes Net Toolbox: http://code.google.com/p/bnt/.

The classification node is the variable node corresponding to what we want to model.


Frédéric Bimbot
email: frederic.bimbot@irisa.fr

Emmanuel Deruty
email: emmanuel.deruty@gmail.com

Gabriel Sargent
email: gabriel.sargent@irisa.fr

Emmanuel Vincent
email: emmanuel.vincent@inria.fr

METHODOLOGY AND RESOURCES FOR THE STRUCTURAL SEGMENTATION OF MUSIC PIECES INTO AUTONOMOUS AND COMPARABLE BLOCKS

. The present article develops further a number of fundamental notions and practical issues, so as to facilitate the usability and the reproducibility of the approach.

We formalize the general methodology as an iterative process which aims at estimating both a structural metric pattern and its realization, by searching empirically for an optimal compromise describing the organization of the content of the music piece in the most economical way, around a typical timescale.

Based on experimental observations, we detail some practical considerations and we illustrate the method by an extensive case study. We introduce a set of 500 songs for which we are releasing freely the structural annotations to the research community, for examination, discussion and utilization. 1

INTRODUCTION

Given its numerous applications, the automatic inference of musical structure is a key subject in MIR [START_REF] Paulus | Audio-based music structure analysis[END_REF], which has been focusing significant research effort in the past years [START_REF] Peeters | Deriving Musical Structures from Signal Analysis for Music Audio Summary Generation: Sequence and State Approach[END_REF][START_REF] Abdallah | Theory and evaluation of a Bayesian music structure extractor[END_REF][START_REF] Goto | A Chorus Section Detection Method for Musical Audio Signals and Its Application to a Music Listening Station[END_REF][START_REF] Paulus | Music structure analysis by finding repeated parts[END_REF][START_REF] Peeters | Sequence Representation of Music Structure Using Higher-Order Similarity Matrix and Maximum-Likelihood Approach[END_REF][START_REF] Levy | Structural Segmentation of musical audio by constrained clustering[END_REF][START_REF] Kelly | Locating Tune Changes and Providing a Semantic Labelling of Sets of Irish Traditional Tunes[END_REF][START_REF] Weiss | Identifying Repeated Patterns in Music Using Sparse Convolutive Non-Negative Matrix Factorization[END_REF][START_REF] Kaiser | Music structure discovery in popular music using non-negative matrix factorization[END_REF]. It has also triggered several studies [START_REF] Peeters | Is Music Structure Annotation Multi-Dimensional ? LSAS[END_REF][START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks[END_REF] and projects [13,[START_REF]SALAMI Project[END_REF] supporting this research with the investigation of methodological issues and the collection of annotated data.

In this context, the structural description approach called decomposition into autonomous and comparable blocks was recently introduced [START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks[END_REF] in terms of general concepts, inspired from structuralism and generativism. It has been designed to be applicable to a wide range of "conventional" music, including pop music.

The present follow-up paper develops further this approach, with the purpose of facilitating the usability and the reproducibility of the method. With hindsight resulting from our own annotation experience and from reactions of fellow scientists to our first paper, this new contribution provides more practical elements and a number of novel points in terms of problem statement (section 2), introduction of a structural metric Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. © 2011 International Society for Music Information Retrieval pattern as a central concept (section 3.4), reformulation of the former concept of musical consistency preservation (section 4.1), clarification of the notion of affixes (section 4.3) and practical illustrations of the annotation process (sections 5.2 and 6). This paper also announces the release of 500 annotated and partially commented music pieces in accordance with the proposed conventions.

PROBLEM STATEMENT

Levels of musical organization

It is commonly agreed that the composition and the perception of music pieces rely on simultaneous processes which vary at different timescales. Similarly to [START_REF] Snyder | [END_REF], we consider the three following levels corresponding to three different ranges of timescales :

• the low-level elements which correspond to fine-grain events such as notes, beats, silences, etc… We call this level the acoustic level and its time scale is typically below or around 1 second.

• the mid-level organization of the musical content, based on compositional units such as bars or hyper-bars or on perceptual units such as musical cells and phrases, ranging typically between 1 and 16 seconds. We will refer to this level as the morpho-syntagmatic level.

• the high-level structure of the musical piece, which describes the long term regularities and relationships between its successive parts, and which we will call the level of the semiotic structure, typically at a time scale around or above 16 seconds.

The figure of section 6 provides an illustration of these three levels. Note that we use the term semiotic in a quite restricted scope, (compared for instance to that of Nattiez [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF]) as denoting the high-level symbolic and metaphoric representation of musical content 1 .

Semiotic structure

What we consider as the semiotic structure of a music piece is something that may look like :

A B C D E F B C D E G D E D E H

1 We thus avoid the term semantic, referring to some musical meaning of objects (for instance, chorus, verse, etc…) : such a notion falls completely outside the scope of this paper.

thus reflecting :

1) some sort of high-level decomposition/segmentation of the whole piece into a limited number of blocks (here 16 blocks) of comparable size, and

2) some form of similarity or equivalence relationship between blocks bearing identical labels (here, 8 distinct symbols)

Providing a semiotic description for a music piece requires primarily the identification of the most adequate granularity (block size and number of blocks) which then conditions the inventory of labels.

From the example below, choosing a finer granularity could lead to a sequence of labels such as:

AA'BB'CC'DD'EE'FF'BB'CC'DD'EE'GG'DD'EE'DD'EE'HH'

where any symbol X is systematically followed by symbol X' , therefore yielding a rather redundant semiotic description.

Conversely, a coarser granularity would require either the uneven grouping of the units into irregular segments (i.e. of more diverse sizes) :

A BC DE F BC DE G DE DE H

or a very misleading representation such as :

AB CD EF BC DE GD ED EH

which completely hides the similarities existing between portions of the piece which had identical labels at a lower scale.

This example thus illustrates a simple case where there exist clearly a preferable granularity at which the semiotic level of the music piece can be described with some form of optimal compromise between :

-The minimality of the set of labels -The informativeness of the sequence of labels -The regularity of the block size

The goal of this work is to present a set of methodological principles for :

1) identifying the most appropriate granularity for describing the semiotic structure, and

2) locating as univocally as possible the corresponding block boundaries.

In this article, the granularity referred to in item 1 is defined as the structural metric of the music piece and the actual borders of the segmental units (item 2) as the realization of the structural meter.

The proposed process relies on the listening of a music pieces, but can be extended to music in written form (scores). However, note that scores may not be available and sometimes are even meaningless w.r.t. the type of musical content under consideration.

BASIC CONCEPTS

Definitions

As exposed in the previous section, the hypothesis of this work is that the semiotic structure of "conventional" music pieces is built on structural blocks, characterized by the content of their musical layers. One of the aim of semiotic structure annotation is therefore to locate the block boundaries (with the convention that they are synchronized with the first beat of a bar). We call size the dimension of the blocks relative to a snap scale proportional to that of the beat (see 3.3).

We call structural metric pattern, the underlying high-level organization of the musical content which is the most adequate for representing economically the semiotic level, and we assume that block boundaries rest on the (potentially irregular) realization of that structural metric pattern. The annotation task thus consists in jointly inferring the structural metric pattern and its realization.

Musical information layers

Even though this is a simplified view of reality, we consider that a piece of music is characterized by 4 main reference properties, potentially evolving over time 1 :

• intensity (amplitude / sound level)

• tonality/modality (reference key and scale)

• tempo (speed / pace of the piece)

• timbre (instrumentation / audio texture)

We also consider that a piece of music shows 4 main levels of temporal organization :

• rhythm (relative duration and accentuation of notes)

• melody (pitch intervals between successive notes)

• harmony (chord progression)

• lyrics (linguistic content and, in particular, rhymes)

These levels of description form 8 musical layers 2 .

Because of their cyclic properties in conventional music, the levels of temporal organization are central to the determination of block boundaries, in our approach. Indeed, as explained in section 4.1, we assume that block boundaries coincide with the convergence of cyclic behaviors taking place simultaneously in the 4 levels of temporal organization.

On the opposite, blocks may globally differ in terms of intensity, tonality, tempo or timbre but these properties may happen to change within a block without corresponding to a structural boundary.

Block size

A primary property of blocks is their size, which we describe in a custom unit that we call snap, and which is defined as the number of times a listener would snap his fingers to accompany the music, at a rate which is as close as possible to 1 bps (beat per second). As opposed to the beat (which is a compositional notion), the snap is a perceptual unit.

Although we may come to consider the blocks from a variety of perspectives during their identification, their ultimate description within the scope of this paper is their size in snaps.

The definition of the snap requires further consolidation, since a tempo-invariant unit would be desirable. However, an evolution of the definition of the snap would not affect the structural segmentation per se, as the snap is only a measure of the block size. 1 In previous work, we identified 3 reference properties only, but we consider now that intensity should also be part of the list. 2 These layers may not all be active simultaneously and some additional layers may be observed in some music pieces.

Structural metric pattern

A fundamental assumption of the proposed method is based on the hypothesis that the semiotic structure can be described in reference to a structural metric pattern, i.e. a prototypical partition of the beat or the snap scale. As an example, a very common structural metric pattern is the repetition of blocks of 16 snaps (structural pulsation period Ψ = 16)

The high-level structure of the music piece is governed by the structural meter but actual semiotic blocks result from the realization of the structural meter and this realization may lead to blocks of irregular size. For example, even if the structural period of a piece is equal to 16, the size of some blocks may deviate from the prototypical value (for instance, 18). We develop further the fact that, in a large number of cases, irregular blocks can be reduced to regular stems that conform to the structural metric pattern.

The structural metric pattern is analogous to the bar, but operates at a higher level : whereas the bar is the organizational entity of low-level elements such as beats and notes, the structural metric pattern governs the organization of midlevel elements (bars, cells, phases, etc…).

ANNOTATION CRITERIA AND NOTATION

Detection of cycles (syntagmatic analysis)

In conventional music, the various temporal organization layers tend to show (quasi-)cyclic behaviors, which we define as the recurrent return of the considered layer to some specific state or set of states 1 . For instance, rhythmic patterns generally show a short-term recurrence which participates to the mid-level organization of the music piece, melodies tend to return to tonic or to exhibit particular intervals (depending on the piece), specific chords sequences conclude harmonic progressions (cadences), etc…

We consider that, in conventional music pieces, there exist time instants for which the 4 levels of temporal organization exhibit some phase convergence towards their respective ends of cycles, which creates identifiable cues of the piece structure. In other words, block boundaries should correspond to some form of recurrent convergence of all levels of temporal organization.

These instants of convergence take very versatile forms, as they can be signaled in the music content by very diverse combination of structuring cues, such as a particular rhythmic pattern combined with the return to a specific note or chord, the completion of a system of rhymes in the lyrics the conclusion of a carrure and a recurrent sound effect… Even though these cues and their combinations are partly conventional (at least within a particular music genre), they generally vary from one piece to another and their identification is part of the empirical analysis conducted by the annotator.

In our approach, cyclicity plays a central role for identifying structural blocks through the 2 ensuing properties :

1) iterability : structural blocks can be looped to yield a consistent (larger) musical stream 2) suppressibility : structural blocks can be skipped in the music piece without creating the perception of a discontinuity in the remaining musical stream Indeed, if one thinks of a periodic signal, each period can be repeated indefinitely and can be removed from the signal without disrupting seriously the organization of the remaining signal. This generalizes conceptually to quasi-cyclic processes, as defined above.

The property of cyclicity gives a founded ground for the syntagmatic definition of structural blocks. It establishes more clearly the criterion formerly based on the preservation of "musical consistency" [START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks[END_REF] and also brings additional substance to the concept of Constitutive Solid Loop [START_REF] Peeters | Is Music Structure Annotation Multi-Dimensional ? LSAS[END_REF].

The listener's ability to identify iterable and suppressible segments in the music piece is a key point in the proposed analysis and it does not require the annotator to be able to express in musicological terms the actual properties of the structuring cues.

When necessary, the analysis can be complemented by an explicit designation of the structuring cues, but attention must be paid that these cues should not be expected to be univocally associated to blocks boundaries : all structuring cues are not systematically observed at all segment borders and some cues can also be observed within block boundaries.

Detection of similarities (paradigmatic analysis)

The identification of actual block boundaries is further (or, in practice, simultaneously) carried out by performing paradigmatic analysis on the musical content, for reinforcing and disambiguating the set of candidate borders hinted by the detection of cyclic segments.

It consists in searching for "repeating" patterns across the musical content, which are identical, similar or, more generally speaking, easy to explain economically relative to one another (for instance, transposition, change in the level of instrumental support, superimposition of a melodic motif, insertion of a musical segment, …).

As for the syntagmatic analysis of section 4.1, the locations of such paradigms do not coincide univocally with block boundaries : they only constitute additional cues of such boundaries.

Note that the paradigmatic analysis performed at this stage calls for similar processes to those that are needed for labeling the segments. However, whereas the labeling stage requires the determination of a global system of contrasts between segments, the extraction of paradigmatic structural cues simply requires pairwise comparisons of musical segments for the only purpose of identifying and locating candidate blocks.

Regularity and reduction

For many conventional music pieces, it can be assumed that a majority of blocks within the piece have a comparable size in snaps, hence corresponding to some structural pulsation period (Ψ). Blocks whose size is equal to the structural pulsation period are called regular blocks.

Some blocks have a smaller size than Ψ, which can generally be interpreted as corresponding to a shortened realization of a regular block. This is especially true for half-size target segments, which can often be matched with the first or second half of a regular block observed somewhere else in the piece. Alternatively such blocks may be considered as a half realization of the structural metric (this is often the case for prechorus and bridges).

In a significant number of cases, blocks are longer than the structural period. However, in these cases, they can often be reduced into a stem of size Ψ and an affix. An affix is a subset of snaps which can be viewed as having been inserted into a (regular) stem and affixes are therefore suppressible from the original block (but not necessarily iterable), i.e., the stem forms, on its own, an admissible block. If the insertion of the affix takes place at the beginning (resp. at the end) of the block, it is called a prefix (resp. suffix).

Affixes are particularly easy to identify and locate within a block when there exist, somewhere else in the song, another block which corresponds to the realization of the stem alone. But sometimes, the stem has to be hypothesized based on more subtle considerations, because it is not attested alone in the piece (but, for instance, with a different affix).

Frequent examples of suffixes are observed when for instance a block is extended by lengthening the last snap over 2 more snaps (resulting in some form of break), by doubling the duration values of the notes on the last 2 snaps of the block or by repeating the last 4 snaps twice (thus rendering an insistence effect). Affixes within blocks can be more tricky to detect, and may take versatile forms, for instance the repetition of a p-snap segment, a tonal excursion of a few snap or a segment with totally different properties from the rest of the block.

By convention, prefixes and suffixes should be of maximum size equal to half of that of the block (preferably strictly less) and they should not alter the harmonic valence of the block, i.e. the harmonic properties at the block boundaries

Structural metric pattern notation

To describe the structural metric pattern, we use the following notation : n a constant stem size of n snaps throughout the piece {n 1 ,n 2 } 2 stem sizes in the piece, n 1 and n 2, occurring in any order but in decreasing frequency (can be generalized to more than 2 values)

(n 1 ,n 2 ) a systematic alternance of stem sizes n 1 and n 2, starting with n 1 (can be generalized to more than 2 values)

These notations are superscripted with a star (n * , {n 1 ,n 2 } * , etc…), if the piece contains only within-blocks irregularities, or very few short blocks considered by the annotator as nonrepresentative of the dominant structure of the piece (in particular, in intros, outros, re-intros, etc…). If relevant, the annotator can combine further the notations, for instance {16, [START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks[END_REF][START_REF] Kelly | Locating Tune Changes and Providing a Semantic Labelling of Sets of Irish Traditional Tunes[END_REF]}, but these needs are quite exceptional…

In conventional pop music, the most common segmental structure is m x 16 * (m being the number of blocks, which is itself usually close to 16), but pieces from the genre blues have usually block sizes based on 24 snaps. More complex patterns such as {16,12}, [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF] Kelly | Locating Tune Changes and Providing a Semantic Labelling of Sets of Irish Traditional Tunes[END_REF] or [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF] Kelly | Locating Tune Changes and Providing a Semantic Labelling of Sets of Irish Traditional Tunes[END_REF] happen to be observed.

Block size notation

Following are the corresponding notation conventions which we use to designate the size of (realized) blocks, in reference to a structural pulsation period of n snaps:

[n+p] Insertion of a p-snap suffix after stem [p+n] Insertion of a p-snap prefix before stem [n&p] Insertion of a p-snap infix (somewhere) inside stem Undeterminable size (usually owing to a lack of snap) Sometimes, two structural blocks may overlap over p snaps, which we call block tiling. This is the case when the realization of a new block starts while the previous blocks is still p snaps before its final boundary and continues in the meantime (for instance, in canons). It is also the case when some snaps function simultaneously as the end of a given block and the beginning of the next one. The notation convention for tiling situations is :

[n-p [p] -p+n].
Note that the internal structure of blocks could be further specified by decomposing the block size into sub-blocks according to paradigmatic properties within the block (for instance 4x4 as the internal structure of a size 16 block), but this goes beyond the scope of the current paper.

GENERAL METHODOLOGY

Annotation process

Based on the notions introduced in the previous section, the annotation of a music piece X can be understood as an (empirical) joint estimation task, namely the determination of :

• The most likely structural metric pattern (M) for the piece • The most likely decomposition of the piece into a set of blocks (S), i.e. the realization of M.

In practice, the annotator proceeds iteratively as follows :

1. hypothetize a structural period Ψ, or (more generally) a structural metric pattern M from the listening of X 2. (attempt to) decompose X into blocks following M, by introducing, if and only if necessary, irregularities (affixes, irregular blocks) so as to satisfy cyclicity of blocks and to maximize similarities across blocks (resp. sections 4.1 and 4.2). 3. consider possible alternatives to Ψ or M 4. if such alternative(s) seem to be worth considering, return to step 2 and test the new hypothesis

The understanding of step 2 is crucial to the proposed methodology : at that stage, the annotator is actually trying to estimate the realization of M via the minimization of the necessary distortion that M should undergo to make it match the properties of the actual musical content of X.

Ultimately, among various hypotheses for M and the corresponding decompositions, the annotator retains that which seems globally more economical for describing the semiotic level, i.e. the solution which results in a satisfactory compromise between :

• the simplicity and typicality of the structural metric • the regularity of the decomposition • the non-redundancy of successive blocks • the closeness of the structural period(s) to a reference value (currently set to 15 seconds) Figure 1 : illustration of the case study of section 6.

Hypothesizing the structural metric pattern

A priori properties and typical values

Previous work [START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks[END_REF] has put forward arguments based on the "Predictive Information Context" (PIC) suggesting that an a priori economical description of the structure of a music piece is based on segments of typical length equal to the square root √ of the length of the piece. In the annex section, we propose complementary considerations based on information theory concepts, which strengthen this point.

We assume that structural blocks of approximate size √ happen to be a reasonable initial assumption when estimating the structural pulsation period. However, the actual analysis of the musical content may lead to a final (a posteriori) result which deviates significantly from this initial guess.

On the basis of an average song length of 240 seconds, √ falls in the range of 15.5 s. With a snap around 1 s, the size of a block will therefore typically be of 16 snaps. Here again, this property should only be considered an a priori hypothesis (the one to start with).

From these consideration, a canonical model which summarizes all the a prioris can be laid down : it consists in 16 blocks of 16 snaps of 1s each. For a given piece, the structural metric pattern and its realization are thus searched as the minimal deviation from this canonical model, which enables a structural description compatible with the musical content.

Estimating plausible snap and structural period(s)

By definition, the snap is the multiple of the beat corresponding to a duration as close as possible (in logarithmic scale) to 1 s (in fact, it usually corresponds to the downbeat, but not always). Identifying the snap is, in general, rather straightforward from the listening of parts of the piece, preferably away from the beginning or the end, which may exhibit particular beat and tempo properties. Depending on the type of bar, admissible intervals for the snap are : [0.71, 1.41] for binary bars and [0.58, 1.73] for ternary ones (for more complex, odd bars, the snap can be unevenly alternating between different numbers of beats).

Once the snap is determined, plausible values of the structural pulsation period(s) are hypothesized by listening to the piece and considering in priority its most salient and steady parts : typically the chorus (if any), the developments of recurring motifs or phrases, the parts of the piece perceived as homogeneous, etc… From these segments, the annotator can generally infer rapidly one or two plausible values of pulsation period(s), from which he/she will start a more comprehensive analysis of the piece, looking for particular patterns and locating irregularities.

Given the central role played by the canonical model, the value of 16 is usually investigated in priority, unless obvious evidence in the musical content direct the annotator towards another hypothesis (for instance, 24 in many pieces of blues). Segments IV, VII, XII and XIII present a clear paradigmatic relationship (chorus of this piece). Three of them last 18 snaps but XII lasts only 16 snaps and can be considered as the stem on which the three other blocks are built by lengthening the harmonic content over the last 2 snaps.

A CASE STUDY

Segments II, V, X form a second paradigm, with the return to tonic as a clear (conventional) structuring cue. Being of size 16, they are in line with the Ψ=16 hypothesis. An alternative hypothesis would be to consider them as the repetition of 2 almost identical (half-)blocks of 8 snaps, but i) this would need the introduction of a second structural period, ii) no occurrence of such a half-block alone is observed in the song and iii) it would split the rhyme pattern of block V.

Segments III, VI and XI constitute a third paradigm. Their raw form amounts for 14 snaps, but they can be described as a 4x4 snap carrure of the abab type, whose last quarter has been truncated of the last 2 snaps, hence the notation 16-2, This comforts (or at least does not contradict) the hypothesis Ψ=16.

Segments I and IX are very similar, I being an instrumental intro of 16 snaps and IX the second half of I, used as an instrumental bridge (hence the notation -8+16). Finally, VIII is a solo, which conveniently lasts exactly 16 snaps.

The segmental structure of the piece is therefore considered to be 13 x 16 * , i.e. a basic 16-snap pattern realized 13 times with a few within-block irregularities. Alternative options could have been 25 x 8 * , but this would introduce much redundancy in the underlying semiotic description, since almost all segments would be observed in systematical pairs, without bringing significantly down the number of irregular segments (only IX would thus become regular). A pattern such as [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF]SALAMI Project[END_REF][START_REF][END_REF] * could be envisaged given the recurrence of this particular size sequence in II-III-IV and V-VI-VII but the existence of XII as a 16-snap realization of the chorus just in between XI and XIII makes this complicated alternative a non-sustainable option.

CORPUS DESCRIPTION

RWC Pop set

A first set of annotations is composed of the 100 songs from the RWC Popular Music database [17], written and produced for research purposes. Their structural annotations have been released and used last year for the MIREX 2010 evaluation [START_REF][END_REF] Eurovision songs are limited, to a 3'00" maximum duration by the rules of the contest, and tend to show other properties (including their structure) influenced by the contest's format and to its target public. These titles however cover a variety of languages and a diversity of sub-genres within Euro-pop.

Ongoing effort

At the time of finalizing this paper, we are completing the annotation of the RWC Music Genre database (100 titles) and we intend to annotate shortly an additional set of titles, so as to reach a total of 500 annotated titles before the end of 2011.

Release

All the aforementioned annotations are available at :

http://musicdata.gforge.inria.fr and on an experimental web site where some of the data are accompanied with comments and which offers the possibility of consulting and debating the proposed annotations :

http://metissannotation.irisa.fr

CONCLUSIONS

The work presented in this paper constitutes a contribution towards the general strategic goal of defining, building and disseminating consistent re-usable resources for research and development in MIR. It proposes operational concepts, consistent procedures and freely available data for the description of music structure.

Our current work direction is to consolidate connections between music structure description and information theory, so as to encompass a wider range of concepts and, in particular, to integrate several timescales in the structural description.

  [p-n] Omission of p snaps at the end of stem [-p+n] Omission of p snaps at the beginning of stem [n\p] Omission of p snaps (somewhere) inside stem [n/2] Half-size block (undetermined place of missing half) [x]

Figure 1

 1 Figure 1 illustrates the analysis of song Genre 08 from the RWC database [17] (labeled as Rock). Structural blocks are depicted both as their span on the x-axis (time in snap) and their height on the yaxis (in log scale). Each block is identified by a distinct roman number. The duration of the song is 3'26" (including initial and final silences) and the size of the song in snaps is 200 (snap is almost equal to 1 s).

  The average length of songs is approximately 4 minutes. A subset of 97 titles contains several pieces from the same artists (see below). The remaining 62 titles correspond to 62 other distinct artists. This corpus covers a large range of music genres but the vast majority of artists are American or English.The Beatles : 21 -Jedi Mind Tricks : 14 -Eric Clapton : 11 Pink Floyd : 9 -Queen : 8 -The Cure : 8 -D Angelo : 4 ACDC, Black Sabbath, Buenavista Social Club and Shack : 3 Eminem, F. Zappa, Madonna, M. Jackson and Plastikman : 27.3 Eurovision setThe Eurovision set is currently composed of 124 titles, corresponding to the songs which participated to the semi-finals and/or the final in years 2008, 2009 and 2010, in their studio version (as recorded on the "official" albums) :

			in
	structural segmentation and since then, they have been marginal-
	ly revised.
	RWC Pop		100 titles
	7.2 Quaero set
	The Quaero set is composed of 159 titles selected by IRCAM
	which are being used in the Quaero project [13] for the eval-
	uation of music structure detection algorithms :
	Quaero 2009	Development set	20 titles
	Quaero 2009	Evaluation set	49 titles
	Quaero 2010	Evaluation set	45 titles
	Quaero 2011	Evaluation set	45 titles
	Total		159 titles
	2008 (Belgrade) ref # 5 099921 699726	43 titles
	2009 (Moscow) ref # 5 099969 968020	42 titles
	2010 (Oslo)	ref # 5 099964 171722	39 titles
	Total		124 titles

Note that cyclic does not necessarily mean periodic, the latter being a stronger property. For example, the zero-crossing of a sequence of values form a set of cycles which may not be periodic.

ANNEX

Let's consider a song represented as a sequence of discrete elements at a given time-scale and let's now consider a bidimensional organization of X into blocks of size n, i.e. a (lines) × (columns) matrix representation of X :

with / and # ($ -1) × + ( Given this structure, the quantity of information needed to index all elements in the matrix requires :

Thus, the index of each line in matrix X can be coded with log 2 m bits, and the total number of bits required to index all lines in X is m log 2 m (the same applies for the columns, hence n log 2 n).

Seeking for the minimum of ) ! (by zeroing the derivative of ) ! w.r.t. n) yields √ .

Hence, in the absence of any particular knowledge concerning the redundancies in X, the most economical way to index it bidimensionally is to shape it as a "square" matrix structure.


Clément Chatelain

Sébastien Adam

Yves Lecourtier

Laurent Heutte

Thierry Paquet

Non-cost sensitive SVM training using multiple model selection

Keywords: ROC front, multi-model selection, multi-objective optimization, ROC curve, SVM

  L'archive ouverte pluridisciplinaire

Introduction

Optimizing the hyperparameters of SVM classifiers is a complex challenge since it is well known that the choice of their values can dramatically affect the performance of the classification system. In the literature, many contributions in this field have focused on the computation of the model selection criterion, i.e. the value which is optimized with respect to the hyperparameters. These contributions have led to efficient scalar criteria and strategies used to estimate the expected generalization error. One can cite Xi-Alpha bound of [START_REF] Joachims | Making large-scale support vector machine learning practical[END_REF], the Generalized Approximate Cross-Validation of [START_REF] Wahba | The bias-variance tradeoff and the randomized gacv[END_REF], the empirical error estimate of [START_REF] Ayat | Automatic model selection for the optimization of svm kernels[END_REF], the radius-margin bound of [START_REF] Chapelle | Choosing multiple parameters for support vector machines[END_REF] or the maximal-discrepancy of [START_REF] Anguita | Hyperparameter design criteria for support vector classifiers[END_REF]. Based on these criteria, hyperparameters are usually chosen using a grid search, generally coupled with a cross-validation procedure. In order to decrease the computational cost of grid search, some authors suggest to use gradient-based techniques (e.g. [START_REF] Bengio | Gradient-based optimization of hyperparameters[END_REF], [START_REF] Keerthi | An efficient method for gradient-based adaptation of hyperparameters in svm models[END_REF]). In these works, the performance validation function is adapted in order to be differentiable with respect to the parameters to be optimized.

All the approaches mentioned above, though efficient, use a single criterion as the objective during the optimization process. Now, it is well known that a single criterion is not always a good performance indicator since it assumes that both target class priors and optimal cost/benefit tradeoffs are known precisely and are not subject to change. Yet this is rarely the case in the real world and classifiers are often used to find a relatively small number of unusual samples in a large population. Moreover, the costs of errors are rarely equivalent, since classification results often lead to actions which can have serious consequences. Screening medical tests for rare diseases in order to inform the patient of the diagnosis or looking for defrauded accounts among a large population of customers in order to deny the corresponding credit charge are classical examples of such a configuration [START_REF] Provost | Robust classification for imprecise environments[END_REF]. Furthermore, the priors relative to the detection of a serious diseases may change, modifying the operating point of the detection system.

One solution to tackle this problem is to use as performance indicator the Receiver Operating Characteristics (ROC) curve which offers a synthetic representation of the trade-off between the True Positive rate (TP) and the False Positive rate (FP), also known as sensitivity vs. specificity trade-off. One way to take into account both FP and TP in the model selection process is to resume the ROC curve into a single criterion, such as the F-Measure (FM), the Break-Even Point (BEP) or the Area Under ROC Curve (AUC). However, we will show in the following that we can get more advantages in formulating the model selection problem as a true 2-D objective optimization task.

In this paper, our key idea is to turn the problem of the search for a global optimal SVM, (i.e. the best set of hyperparameters) using a single criterion or a resume of the ROC curve into the search for a pool of locally optimal SVMs (i.e. the pool of the best sets of hyperparameters) w.r.t. FP/TP rates. The best classifier among the pool can then be selected according to the needs of some practitioner. From a real-world application point of wiew, such a result is very interesting since system designers do not have to choose classifier hyperparameter values before precise knowledge of key evaluation parameters is available. Moreover, the proposed approach enables to change the classifier in use if target conditions change. An application of the proposed framework has been applied on a handwritten character recognition problem where the misclassification costs can not be accurately estimated [START_REF] Chatelain | Multi-objective optimization for svm model selection[END_REF].

The proposed framework can be viewed as a multiple model selection approach (rather than a model selection problem) and can naturally be expressed in a Multi-Objective Optimization (MOO) framework. Under particular conditions, we assume that such an approach could lead to better results than a more traditional single model selection approach based on a scalar optimization. Figure 1 depicts our overall multi-model selection process. The resulting output is a pool of classifiers, each one optimizing some FP/TP rate tradeoff. The set of trade-off values constitutes an optimal front we call "ROC front" by analogy with MOO field.

The remainder of the paper is organized as follows. In section 2, we detail the rationale behind the ROC front concept and illustrate how our multi-model selection approach can outperform traditional approaches in a MOO framework. In section 3, the SVM multi-model selection problem is adressed. Then, section 4 shows that our method compares favourably with traditional model selection techniques on standard benchmarks (UCI datasets). Finally, a conclusion and future works are drawn in section 5.

The "ROC front" concept

As stated in the introduction, a model selection problem may be seen from a multiobjective point of view, turning thus into a multi-model selection approach. In the literature, some multi-model selection approaches have been proposed. However, these approaches aim at designing a single classifier and thus cannot be considered as real multi model selection approaches. Caruana for example proposes in [START_REF] Caruana | Ensemble selection from libraries of models[END_REF] an approach for constructing ensembles of classifiers, but this method aims at combining those classifiers in order to optimize a scalar criterion (accuracy, cross entropy, mean precision, AUC). Bagging, boosting or Errorcorrecting-output-codes (ECOC) ( [START_REF] Dietterich | Solving multiclass learning problems via error-correcting output codes[END_REF]) also aim at combining different classifiers of an ensemble in order to produce a single classifier efficient with respect to a scalar performance metric. In [START_REF] Lebrun | An ea multi-model selection for svm multiclass schemes[END_REF], an EA-based approach is applied to find the best hyperparameters of the set of binary SVM classifiers combined to produce a multiclass classifier.

The approach which is proposed in this paper is different since our aim is not to build a single classifier but a pool of classifiers using a real multi-objective framework. In such a context, let us recall that the problem when ROC curves are used to quantify classifier performance is their comparison in a 2-D objective space : a classifier may be better for one of the objectives (e.g. FP) and worse for the other one (e.g TP). Consequently, the strict order relation that can be used to compare classifiers when a single objective is considered becomes unusable and classical mono-objective optimization strategies can not be applied.

Usually, this problem is tackled using a reduction of the FP and TP rates into a single criterion such as the Area Under ROC Curve (AUC) ( [START_REF] Rakotomamonjy | Optimizing auc with support vector machine[END_REF]). However, such performance indicators are a resume of the ROC curve taken as a whole and do not consider the curve from a local point of view. The didactic example proposed in figure 2 illustrates this statement. One can see on this figure two synthetic ROC curves. The curve plotted as continuous line has a better AUC value, but the corresponding classifier is not the best for any specific desired value of FP rate (resp. TP). Consequently, optimizing such a scalar criterion to find the best hyperparameters could lead to solutions that do not fit the practitioner needs in a specific context. It seems a better idea to simultaneously optimize FP and TP rates using a MOO framework and a dominance relation to compare classifier performance. Let us recall that the dominance concept has been proposed by Vilfredo Pareto in the 19th century. A decision vector -→ u is said to dominate another decision vector -→ v if -→ u is not worse than -→ v for any objective functions and if -→ u is better than -→ v for at least one objective function. This is denoted -→ u ≺ -→ v .

More formally, in the case of the minimization of all the objectives, a vector

- → u = (u 1 , u 2 , . . . , u k ) dominates a vector -→ v = (v 1 , v 2 , . . . , v k ) if and only if: ∀i ∈ {1, . . . , k}, u i ≤ v i ∧ ∃j ∈ {1, . . . , k} : u j < v j
Using such a dominance concept, the objective of a Multi-Objective Optimization algorithm is to search for the Pareto Optimal Set (POS ), defined as the set of all non dominated solutions of the problem. Such a set is formally defined as the set :

P OS = -→ x ∈ ϑ/¬∃ -→ y ∈ ϑ, --→ f (x) ≺ --→ f (y)
where ϑ denotes the feasible region (i.e. the parameter space regions where the constraints are satisfied) and -→ f denotes the objective function vector. The corresponding values in the objective space constitute the so-called Pareto Front.

From our model selection point of view, the POS corresponds to the pool of non-dominated classifiers (the pool of the best sets of hyperparameters). In this pool, each classifier optimizes a particular FP/TP trade-off. The resulting set of FP/TP points constitutes an optimal front we call "ROC front". This concept is illustrated with a didactic example as shown in figure 3: let us assume that three ROC curves have been obtained from three distinct hyperparameter sets. This could lead to the three synthetic curves plotted as dashed lines. One can see on this example that none of the classifiers dominates the others on the whole range of FP/TP rates. The same statement may be drawn concerning the continuous black curve which may be the ROC curve of a classifier learnt through a minimization of an AUC criterion [START_REF] Rakotomamonjy | Optimizing auc with support vector machine[END_REF]. This curve do not dominates the three synthetic ROC curves. An interesting solution for a practitioner is the "ROC front" (the black curve with dots), which is made of non-dominated parts of a set of classifier ROC curves. The method proposed in this paper aims at finding this "ROC front" (and the corresponding POS ), using an Evolutionary Multi-Objective Optimization Algorithm called NSGA-II. This class of optimization algorithm has been chosen since Evolutionary Algorithms (EAs) are known to be well-suited to search for multiple Pareto optimal solutions concurrently in a single run, through their implicit parallelism.

SVM multi-model selection

As explained in the previous sections, the proposed framework aims at finding a pool of SVM classifiers, optimizing simultaneously FP and TP rates.

As stated in [START_REF] Osuna | Support vector machines: Training and applications[END_REF], classification problems with asymmetric and unknown misclassification costs can be tackled using SVM through the introduction of two distinct penalty parameters C -and C + . In such a case, given a set of m training examples x i in n belonging to the class y i :

(x 1 , y 1 ) . . . (x m , y m ), x i ∈ n , y i ∈ {-1, +1}
the maximisation of the dual lagrangian with respect to the α i becomes :

M ax α m i=1 α i - 1 2 m i,j=1 α i α j y i y j K(x i , x j )
subject to the constraints:

   0 ≤ α i ≤ C + f or y i = -1 0 ≤ α i ≤ C -f or y i = +1
m i=1 α i y i = 0 where α i denote the Lagrange multipliers and K(.) denotes the kernel. In the case of a Gaussian (RBF) kernel, K(.) is defined as :

K(x i , x j ) = exp -γ × x i -x j 2
Hence, in the case of asymmetric misclassification costs, three parameters have to be determined to perform an optimal learning of the SVM classifier:

-The kernel parameter of the SVM-rbf : γ.

-The penalty parameters introduced above : C -and C + .

In the following, the proposed framework (see figure 1) is used in order to tune these three hyper-parameters values. For that, two particular points have to be specified for the application of NSGA-II to SVM multi-model selection :

-the solution coding : as said before, three hyperparameters are involved in the learning of SVM for classification problems with asymmetric misclassification costs : C + , C -and γ. These three hyperparameters constitute the parameter space of our optimization problem. Consequently, each individual in NSGA-II has to encode these three real values. We have chosen to use a real coding of these parameters in order to be as precise as possible. -the evaluation procedure : each individual in the population corresponds to some given values of hyperparameters. In order to compute the performance associated to this individual, a classical SVM learning is performed using the encoded parameter values on a learning dataset. Then, this classifier is evaluated on a test dataset with the classical FP and TP rates as performance criteria.

Let us now present some experimental results on several UCI databases.

In this section, the proposed multi-model selection approach based on the ROC front concept is evaluated and compared with other approaches on publicly available benchmark datasets. First, the experimental protocol of our tests is described. Then, the results are shown and compared with some reference works, and finally several comments on these results are proposed.

Our approach has been applied on several 2-class benchmark datasets publicly available in the UCI Machine Learning repository [START_REF] Asuncion | UCI machine learning repository[END_REF] As we propose a real multi objective approach, the result of our experiment is a pool of classifiers describing the ROC Front. Thus, the evaluation of our approach is not easy since as mentioned in the introduction, comparing some results in a multi-dimensional space is a difficult task. Nevertheless, there exist some dedicated measures such as the Set Coverage Metric proposed in [START_REF] Zitzler | Comparison of multiobjective evolutionary algorithms : Empirical results[END_REF]. However, to the best of our knowledge, the other methods in the literature always consider a single classifier as a solution for a classification problem, which makes it difficult to compare our results with those in the literature.

Thus, the only way to evaluate our approach is to reduce the ROC front to a scalar criterion. For that, an Area Under the ROC Front (AUF) is calculated and compared with the Area Under the ROC Curve (AUC) of several approaches in the literature. We know that this comparison is not theoretically correct since the best results of a pool of classifiers is compared with a curve obtained by varying the threshold of a unique classifier. However, the aim of this comparison is only to highlight the fact that more interesting trade-offs may be locally reached with the ROC front approach. This comparison may also be justified by the fact that finally, in both cases only one classifier with a unique threshold will be retained for a given problem. Note also that the results of our approach are compared with several works based on the optimization of a scalar criterion for various classifiers. We emphasize that our comparison is based on the selection for each database of the best results found in the literature up to now: [START_REF] Bostrm | Maximizing the area under the roc curve using incremental reduced error pruning[END_REF] (Decision lists and rules sets), [START_REF] Cortes | Auc optimization vs. error rate minimization[END_REF] (Rankboost), [START_REF] Ferri | Learning decision trees using the area under the roc curve[END_REF] (Decision trees), [START_REF] Rakotomamonjy | Optimizing auc with support vector machine[END_REF] (SVMs) and [START_REF] Wu | A scored auc metric for classifier evaluation and selection[END_REF] (five models : naive Bayes, logistic, decision tree, kstar, and voting feature interval). We refer to these papers for more explanation of the criterion and the model used.

Concerning the application of our multiobjective strategy, a cross validation procedure has been performed with 5 folds for each dataset. The results are presented in table 2, where the first column is the best AUC among the precited works based on the optimization of a scalar criterion, and the second one is the AUF of our approach. As expected, one can see that for every dataset the ROC front yielded by the pool of classifiers leads to a higher area than the area under the ROC curve of the other single classifiers. As said before, it is important to emphasise that the AUF cannot theoretically be compared with AUC since the different operating points of the ROC front cannot be reached by a single classifier. However, this comparison with methods which explicitly optimize AUC clearly shows that our approach enables to reach very interesting local operating points which cannot be reached by the AUC-based classifiers. Hence, we claim that if the good model can be selected among the pool of classifiers, our approach can lead to better results than AUC-based methods.

Let us also remark that compared with other EMOO approaches, the intrinsic parameters of the SVM classifiers (i.e. the position and weight of support vectors) are fixed using a mono-objective optimization algorithm well suited for such a task. Therefore, the EMOO concentrates on the choice of the hyperparameter values. This approach differs from other works using EMOO to perform both intrinsic and hyperparameter settings. In the context of ROC curve optimization we can mention [START_REF] Kupinski | Multiobjective genetic optimization of diagnostic classifiers with implications for generating receiver operating characterisitic curves[END_REF][START_REF] Anastasio | Optimization and froc analysis of rule-based detection schemes using a multiobjective approach[END_REF][START_REF] Fieldsend | Roc optimisation of safety related systems[END_REF][START_REF] Everson | Multi-class roc analysis from a multi-objective optimisation perspective[END_REF]. All these works are limited to noncomplex classifiers (with a few number of intrinsic parameters) because EMOO algorithms rapidly become intractable when the size of the parameter space increases. Within a monoobjective context, such a limitation has been counteracted by developing specific methods for specific problems like the Lagrangian maximisation for the SVM. Therefore, using the Lagrangian method for the tuning of SVM intrinsic parameters enables the EMOO algorithm to concentrate on a small number of hyperparameters.

Finally, let us consider the computational issues of the proposed approach. Assume that o is the learning complexity of the classifier, the learning complexity of the proposed approach O is defined as:

O = M.N × o
where we recall that M stands for the number of generations of the evolutionary algorithm, and N is the population size. Although high, this complexity can be compared with that of a full search approach, which is O = K i D i ×o for a K-hyperparameter problem, where D i is the number of discrete values of each parameter. It is still higher than a gradient based approach, but as shown before leads to better results. Let us notice that the decision complexity of our approach is the same as the standard decision complexity of the involved classifier.

Conclusions

In this paper, we have presented a framework to tackle the problem of SVM model selection with unknown misclassification costs. The approach is based on a multi-model selection strategy in which a pool of SVM classifiers is trained in order to depict an optimal ROC front. Using such a front, it is possible to choose the FP/TP trade-off that best fits the application constraints. An application of this strategy with Evolutionary Multi-Objective Optimization has been proposed, with a validation on UCI datasets. Obtained results have shown that our approach compares favourably with a state-of-the-art approach based on the Area Under ROC Cure criterion since better operating points can be locally reached. As a conclusion, one can say that an AUC-based approach suits pattern recognition problems where the operating point may vary, whereas our approach better suits problems where the operating point is supposed to be static.

The proposed approach is simple and generic. It can be applied to other parametric classifiers (KNN, Neural network, etc.) with other optimization methods ( [START_REF] De Souza | Multiclass svm model selection using particle swarm optimization[END_REF]). Moreover, it can be easily extended through the introduction of other parameters (kernel type) or objectives (number of support vectors, decision time). Note that a feature selection process could also be included in the optimization process in order to provide a complete model selection approach. In our future works, we also plan to extend the approach to the multiclass problem.

Fig. 1 .

 1 Fig. 1. SVM Multi-model selection framework

Fig. 2 .

 2 Fig.2. Comparing ROC curves: the continuous ROC curve provides a better AUC than the dashed ROC curve, but is not locally optimal for a given range of specificity values (False Positive Rate).

Fig. 3 .

 3 Fig. 3. Illustration of the ROC front concept : the ROC front depicts the FP/TP performance corresponding to the pool of non dominated operating points.

Table 1 .

 1 on which state-ofthe-art results have been published. The number of samples and the number of attributes for each problem are reported in table 1. Number of samples and number of attributes of the considered 2-class UCI problems.

	problem # samples # attributes
	australian	690	14
	wdbc	569	30
	breast cancer	699	10
	ionosphere	351	34
	heart	270	13
	pima	768	8

Table 2 .

 2 Comparison of the Area Under the ROC Curve (AUC) in the literature with the Area Under the ROC Front (AUF).

	problem ref. AUC literature	AUF
	australian [24] 90.15 ± 0.53 96.91 ± 1.8
	wdbc	[14] 94.7 ± 4.6	99.82 ± 0.1
	breast cancer [6] 99.13	99.86 ± 0.1
	ionosphere [22] 98.7 ± 3.3	99.14 ± 1.2
	heart	[24] 92.60 ± 0.7	95.67 ± 1.5
	pima	[10] 84.80 ± 6.5	88.36 ± 3.1