Benjamin Lecouteux
email: benjamin.lecouteux@imag.fr

Georges Linares
email: georges.linares@univ-avignon.fr

Yannick Estève
email: yannick.esteve@univ-lemans.fr

Guillaume Gravier

Dynamic Combination of Automatic Speech Recognition Systems by Driven Decoding

Keywords: Speech processing, automatic speech recognition, system combination

Combining automatic speech recognition (ASR) systems generally relies on the posterior merging of the outputs or on acoustic cross-adaptation. In this paper, we propose an integrated approach where outputs of secondary systems are integrated in the search algorithm of a primary one. In this driven decoding algorithm (DDA), the secondary systems are viewed as observation sources that should be evaluated and combined to others by a primary search algorithm. DDA is evaluated on a subset of the ESTER I corpus consisting of 4 hours of French radio broadcast news. Results demonstrate DDA significantly outperforms vote-based approaches: we obtain an improvement of 14.5% relative word error rate over the best single-systems, as opposed to the the 6.7% with a ROVER combination. An in-depth analysis of the DDA shows its ability to improve robustness (gains are greater in adverse conditions) and a relatively low dependency on the search algorithm. The application of DDA to both A* and beam-search-based decoder yields similar performances.

I. INTRODUCTION

The general ASR system combination principle consists in using complementary ASR systems that exchange information at different levels of the decoding process. Numerous approaches rely on the combination of acoustic information. In [START_REF] Zolnay | Acoustic feature combination for robust speech recognition[END_REF], the authors aggregate multiple feature streams into a single one. Other approaches combine acoustic scores at the frame or at the model level [START_REF] Barrault | Framebased acoustic feature integration for speech understanding[END_REF], [START_REF] Hoffmeister | Frame based system combination and a comparison with weighted ROVER and CNC[END_REF], [START_REF] Nock | Loosely coupled HMMs for ASR[END_REF]. One of the most popular techniques being cross-adaptation which consists in adapting acoustic models on transcriptions produced by other systems [START_REF] Prasad | The 2004 BBN/LIMSI 20xRT English Conversational Telephone Speech Recognition System[END_REF], [START_REF] Stüker | Cross-system adaptation and combination for continuous speech recognition: The influence of phoneme set and acoustic front-end[END_REF]. Considering that the combination efficiency strongly depends on the system (or model) complementarity, several papers propose techniques that aim at augmenting system diversity while preserving accuracy [START_REF] Burget | Complementarity of speech recognition systems and system combination[END_REF], [START_REF] Siohan | Constructing ensembles of ASR systems using randomized decision trees[END_REF], [START_REF] Breslin | Complementary system generation using directed decision trees[END_REF].

Another family of combination techniques relies on the posterior re-estimation of the hypotheses generated by various systems: in this case, re-estimation is done through posterior merging of recognition hypotheses. In this combination scheme, each ASR system computes, independently from the others, the best hypothesis; as a final step, all text outputs are then aligned and merged. In the ROVER algorithm [START_REF] Fiscus | A post-processing system to yield reduced word error rates: Recognizer Output Voting Error Reduction (ROVER)[END_REF], this merging is performed by a simple weighted vote that is applied to the N single-system hypotheses by taking into account ASR This research was supported by the ANR (Agence Nationale de la Recherche) under contract number ANR-09-BLAN-0161 (ASH). system posteriors. ROVER is usually limited to the 1-best hypotheses; [START_REF] Goel | Segmental minimum bayes-risk ASR voting strategies[END_REF] proposes to apply it to the N-best list from each ASR system. In [START_REF] Hillard | iROVER: Improving system combination with classification[END_REF], [START_REF] Zhang | Investigations of issues for using multiple acoustic models to improve continuous speech recognition[END_REF], improvements of ROVER are evaluated based on machine learning algorithms against voting. In [START_REF] Schwenk | Combining multiple speech recognizers using voting and language model information[END_REF], the authors refine ROVER by using a language model concurrently with the voting algorithm. Another approach, proposed in [START_REF] Sankar | Bayesian model combination (baycom) for improved recognition[END_REF], uses Bayesian decision theory for an optimal weighting of ASR system hypotheses which take into account confidence measures. A ROVER generalization was proposed in [START_REF] Evermann | Posterior probability decoding, confidence estimation, and system combination[END_REF], where the voting mechanism relies on the posterior combination of confusion networks (CNC). However, experiments assessed in [START_REF] Hoffmeister | Frame based system combination and a comparison with weighted ROVER and CNC[END_REF] exhibit only a slight gain with CNC compared to ROVER. These two methods, ROVER and CNC, yield significant performance improvement, especially when the sub-systems have a good level of complementarity and relatively close performance. Nevertheless, they have some serious limitations.

The main issue with posterior combination is that merging the system outputs leads to discarding some crucial information related to the decoding process, especially word boundaries, which are omitted in confusion networks or wordutterance synchronization and linguistic stream continuity. Furthermore, during decoding, each system prunes hypotheses according to its current knowledge and its specific decoding strategy, though sharing earlier cross-system information could avoid the pruning of correct hypotheses. Globally, we can expect better precision for the combination by integrating downstream the information from the multiple auxiliary sources [START_REF] Chen | A new framework for system combination based on integrated hypothesis space[END_REF].

In this paper, we propose an integrated approach that relies on the basic idea of combining integrated systems. We present a framework based on the driven decoding algorithm (DDA) that consists in joining an ASR system with outputs provided by auxiliary systems [START_REF] Lecouteux | System combination by driven decoding[END_REF], [START_REF] Lecouteux | Generalized driven decoding for speech recognition system combination[END_REF] or manual transcripts [START_REF] Lecouteux | Integrating imperfect transcripts into speech recognition systems for building high-quality corpora[END_REF]. This method relies on a new decoding strategy where the search algorithm is dynamically driven by transcripts from other systems, thus dynamically modifying the search space.

The paper is structured as follows: DDA is formalized in Section II while Section III details implementation of DDA with two types of decoder, namely A * and beam search. Section IV presents the experimental framework. Section V reports the evaluation of the DDA approach applied on both a A * decoder and a beam-search decoder; results are discussed and compared to a classical combination based on a ROVER tech-nique. Various cross-adaptation strategies applied on DDAbased decoding are evaluated in Section VI. In Section VII, we present a generalization of this algorithm to confusion network driven decoding and to N system combination with N ≥ 2. Finally, we conclude in the last section.

II. THE DRIVEN DECODING ALGORITHM

The general idea of DDA is to give credit to partial search hypotheses of the primary system which are consistent with the hypotheses of the auxiliary systems. The algorithm works by integrating on-the-fly assumptions derived from the auxiliary systems. The principle of the algorithm consists in aligning the auxiliary transcripts with partial hypotheses of the primary system during decoding. The quality of the fit between a partial hypothesis and auxiliary transcripts is then used to reevaluate the language model component of the primary system, where a good fit increases the language model score.

We first describe the synchronization step to locate the best portion of the auxiliary transcript corresponding to the current partial hypothesis. We then propose an alignment measure to modify the language model score.

A. ASR synchronization to the auxiliary transcript

In order to locate an anchor point in the auxiliary hypothesis T of size m (being the number of words), each word from the current hypothesis H is aligned to T using an edit distance. We use the method presented in [START_REF] Lecouteux | Integrating imperfect transcripts into speech recognition systems for building high-quality corpora[END_REF]: the partial hypothesis H of size n is built by collecting the current word and its history from the best path found during the search process. To align sequences we construct an n-by-m matrix where the element (i, j) of the matrix contains the distance between the two words T j and H i . We use a basic distance function, where d(T j , H i ) = 0 when T j = H i and d(T j , H i ) = 3 for deletion, d(T j , H i ) = 4 for insertion and d(T j , H i ) = 6 for substitution. Costs were computed via the estimated probability of each event in the auxiliary systems (i.e., number of insertion, deletions and substitutions). In practice these costs are the same for all auxiliary systems and the impact of distance values in a ± 1 range is limited. The cumulative distance γ(i, j) between H i and T j is computed as follows:

γ(i, j) = d(T j , H i )+min{γ(i-1, j-1), γ(i-1, j), γ(i, j-1)}
(1) This alignment is performed each time a word end is hypothesized. To efficiently compute the alignment, a cache of the previous alignment can be used in order to quickly compute the cumulative distances γ(i, j).

The dynamic synchronization of the search algorithm driven by the alignment on an auxiliary transcript is illustrated Figure 1.

The best hypothesis-to-reference matching provides a synchronization point Γ(i) defined as follows:

Γ(i) = arg min j γ(i, j) (2)
Γ(i) allows to find the best synchronization point s i : Given the synchronization point between the hypothesized and auxiliary transcripts, one has to evaluate a transcript-tohypothesis score reflecting how well the two sequences match.

s i = (T Γ(i) , H i ) (3)

B. Transcript-to-hypothesis matching score

In order to use information of the auxiliary transcript, the linguistic part of the primary ASR cost function is reevaluated according to a transcript-to-hypothesis matching score θ δ (s i ) combined with a confidence score φ(s i ) of the word T Γ(i) in s i . This mechanism drives the search by dynamically rescoring the language model value, according to the alignment and word confidence scores. The better the alignment and confidence score, the higher the impact on the linguistic score.

The matching score denoted θ δ (s i ) is based on the number δ (Γ(i)) of words in the language model short-term history of size δ that are correctly aligned with the auxiliary transcript. θ δ (s i ) is greater when the trigram is aligned and linearly decreases with the misalignments of the history:

θ δ (s i ) = δ (Γ(i)) δ ( 4
)
where δ is the size of the history used to compute the matching score Finally, the matching score α δ (H i ) of the word H i is computed by using the word confidence score φ(s i ) of the word T j as

α δ (H i ) = φ(s i )θ δ (s i ) (5)
C. On-the-fly linguistic rescoring

Once the matching score is fully estimated according to the synchronization process and the confidence measures, the ngram probabilities are reevaluated. We evaluate two types of strategies: the first one consists of a dynamic language model scaling factor and the second one of a dynamic word penalty.

1) Dynamic language model: The first proposed combination dynamically evaluates the language model scaling factor according to the auxiliary transcript T . The linguistic probabilities are modified according to the following rescoring rule:

P (w i |w i-2 , w i-1 ) = P (w i |w i-2 , w i-1 ) 1-α δ (wi) (6)
where P (w i |w i-2 , w i-1 ) is the resulting modified linguistic score. P (w i |w i-2 , w i-1 ) is the initial trigram probability and 1 -α δ (w i ) is the word LM scale factor for w i .

2) Log-linear combination: [START_REF] Tax | Comparison between product and mean classifier combination rules[END_REF] conducted experiments which demonstrated that the product combination rule gives good results when all classifiers are quite accurate. On the other hand, if one (or more) of the classifiers significantly fails, then the arithmetic mean rule yields better results. In this case, the combination consists of a dynamic word penalty with a rescaling of the initial linguistic probability. Following this principle, the linguistic probabilities are modified using the following rescoring rule:

P (w i |w i-2 , w i-1 ) = P (w i |w i-2 , w i-1 ) 1-β α δ (w i ) β (7)
where β is an empirical scaling factor.

III. DDA IMPLEMENTATION

The DDA principle of modifying the linguistic score of an ASR system based on auxiliary transcripts is generic and can be implemented in various ASR systems. We provide details on the implementation with two widely used algorithms, namely A * and beam search.

A. A * implementation

The LIA laboratory has developed a large vocabulary continuous speech recognition system named Speeral [START_REF] Nocéra | The LIA's French broadcast news transcription system[END_REF]. This decoder is derived from the A * search algorithm dedicated to the search of the best path in a graph. It has been used in several speech recognition engines, generally for wordgraph decoding. In Speeral, the A * algorithm operates on a phoneme lattice, which is estimated using cross-word and context-dependent HMM.

The exploration of the lattice is supervised by an estimation function F (h n ), which evaluates the probability of the hypothesis h n crossing the node n:

F (h n ) = g(h n ) + p(h n ) (8)
where p(h n ) is the probe that estimates the probability of the best hypothesis from the current node n to the ending node. In Speeral, the probe p combines the acoustic probability and a language model look-ahead (LMLA) score [START_REF] Massonié | Scalable language model lookahead for LVCSR[END_REF]. The acoustic term is determined via an acoustic decoding process, carried out as a Viterbi algorithm on the phone-lattice. The LMLA used in Speeral enables the comparison of competing hypotheses before reaching a word boundary. The probability of a partial word corresponds to the best probability in the list of words sharing the same prefix:

P (W * |h) = max i P (W i |h) (9)
where W * is the best possible continuation word and h the word history (partially present in g(h n )). g(h n ) is the probability of the current hypothesis that results from the partial exploration of the search graph (from the starting point to the current node n):

g(h n ) = max P (W ) Θ ∆ |W | P (X|W ) (10)
where P (W ) is the linguistic probability of the current word sequence, P (X|W ) is the acoustic probability according to the word sequence W , Θ is the language model scale factor, ∆ is the linguistic penalty and |W | the number of words in W .

The Speeral speech recognition system generates hypotheses as the phone-lattice is being explored: the best hypotheses at time t are extended according to the current hypothesis probability and the probe results: best paths are then explored in a depth-first manner. In practice, a partial hypothesis H of size n is built by collecting the current word (i.e., the best word end according to the LMLA for the node currently considered) and its history from the path found during the search process. The sequence alignment is achieved as presented in II-A at each newly encountered word in the phone-lattice.

With the DDA (in log-linear version), Eq. 10 becomes:

g(h n ) = max k=|W | k=1 P (W k ) (Θ-β+1) α δ (W k ) β ∆ |W | P (X|W ) (11)
where α(W k ) is dynamically evaluated according to the auxiliary transcript alignment with the currently explored hypothesis (i.e., using the δ last words of the sequence W ).

B. Viterbi implementation

The DDA can be transposed in a Viterbi decoding with the requirement to know the best history alignment of the currently explored word in the beam search in order to scale the linguistic score. The framework proposed by [START_REF] Placeway | Cheating with imperfect transcripts[END_REF] aligns subtitles in a similar manner. In their approach the rescoring trigram rule is based on the conditional distribution P (w i |w w1...i-1 c 1 ...c m ) where w i is the following word in a transcript whose subtitle is c 1 ...c m .

C. DDA and decoding time

We observe that the DDA algorithm improves decoding speed slightly on the A * algorithm, in spite of the additional computational cost due to search synchronization. This gain in terms of execution time is due to the earlier exploration of the best paths provided by auxiliary systems.

IV. EXPERIMENTAL FRAMEWORK

We implemented DDA both in an A * algorithm and in a Viterbi-based algorithm. The A * version is assessed by the Speeral decoder. The Viterbi version is tested on the Speeral word-graphs (not obtained with DDA) by using Fastnc, a LIA Viterbi-based graph decoder. The auxiliary hypotheses (and associated confidence measures) are supplied by a Sphinxderived system developed by LIUM [START_REF] Deléglise | The LIUM speech transcription system: A CMU Sphinx III-based system for French broadcast news[END_REF].

A. Development and test corpus

Development (1 hour) and test (3 hours) data constitutes a subset of the development corpus provided for the ESTER evaluation campaign [START_REF] Galliano | The ESTER phase II evaluation campaign for the rich transcription of French broadcast news[END_REF]. The ESTER corpus consists of radio broadcast news from four channels, namely France Inter, France Info, Radio France International (RFI) and Radio Télévision Marocaine (RTM). The corpus, designed to evaluate broadcast news transcription systems, contains mostly high quality speech. Nevertheless, some segments are recorded in more difficult acoustic conditions, including adhoc interviews, speech from non-native speakers, and on-thefly translations.

We used RTM (1h) to tune the scale factor β of DDA. The combination values were determined empirically by using a grid-search method in order to reduce the WER. We have observed a relation between parameter values and the quality of auxiliary ASR systems. The quality of confidence measures has a strong impact.

The test is performed on 3 shows from 3 radio broadcasts: one hour from France Inter, one hour from France Info and one hour from RFI.

B. Segmentation issue

Each ASR system uses its own segmentation algorithm. Segmentation is used in order to extract speech segments from audio data. Each segmentation system gives different results in terms of timestamps and speech detection. Segmentation errors lead to the miss of speech segments or to non-speech decoding, increasing significantly the WER. We take advantage of the multiple ASR segmentations. When the main system misses some speech segments which have been recognized by the auxiliary one with a confidence score greater than a fixed threshold, the corresponding transcript is integrated to the final hypothesis.

C. The LIA broadcast news system

Experiments were carried out with the LIA system used in the ESTER evaluation campaign, this system was based on the Speeral decoder and the Alize-based segmenter [START_REF] Bonastre | ALIZE, a free toolkit for speaker recognition[END_REF]. Segments are automatically segmented by speaker (in order to adapt the acoustic models using Maximum Likelihood Linear Regression), and their size is limited to 30 seconds.

Context-dependent acoustic models are used. We train the acoustic models on ESTER materials (about 80 hours of annotated speech). The language models are classical trigrams estimated from about 200M of words from the French newspaper Le Monde and the broadcast news manual transcripts provided during the ESTER campaign. The system runs two passes. The first one provides intermediate transcripts which are used for MLLR adaptation. The first pass takes about 3xRT and the second takes about 5xRT (exploration cut-offs are decreased) on a standard desktop computer.

We use the Fastnc decoder in order to test DDA with a Viterbi search. Initially the Speeral graphs do not contain linguistic informations. As a first step the Fastnc decoder performs a static graph expansion by using the 3-gram language model. For each new expanded node, DDA is applied to bias the language model probabilities. When the graph is expanded a classic Viterbi algorithm is applied to find the best path in the graph.

The LIA confidence measures (used for ROVER experiments) are computed in two stages. The first one extracts lowlevel features related to the acoustic and search graph topology, and high-level features related to linguistic information. Each word from the hypothesis is represented by a feature vector composed of 23 features that are grouped into 3 classes. Then, a first bad word detection hypothesis is produced by a classifier based on the boosting algorithm. More details can be found in [START_REF] Lecouteux | Combined low-level and highlevel features for out-of-vocabulary word detection[END_REF].

D. The LIUM broadcast news transcription system

The LIUM speech transcription system is based on the CMU Sphinx 3.3 (fast) decoder [START_REF] Placeway | The 1996 Hub-4 Sphinx-3 system[END_REF]. The Sphinx 3.3 decoder is a branch of the CMU Sphinx III project which has been developed to include some speed improvements. This decoder uses fully continuous acoustic models with 3 or 5-state leftto-right HMM topologies.

The LIUM Speech Project has added a Speaker Adaptive Training module, a 4-gram word-lattice rescoring process, and a segmentation toolkit. The decoding process can be decomposed into two passes (plus the segmentation process): a first pass using band-and gender-specialized acoustic models and a trigram language model; a second pass using adapted acoustic models and a word-lattice rescoring process with a 4-gram language model.

The LIUM system has earned second position in the transcription task (TRS) in the ESTER evaluation campaign. More details about this system are presented in [START_REF] Deléglise | The LIUM speech transcription system: A CMU Sphinx III-based system for French broadcast news[END_REF].

For the experiments presented in this paper, the acoustic and linguistic models were trained on the ESTER training corpus.

Each word H i in hypothesis H is assigned to a local confidence measure φ(H i ). In the next experiments, the LIUM speech recognition system [START_REF] Deléglise | The LIUM speech transcription system: A CMU Sphinx III-based system for French broadcast news[END_REF] provides the one-best hypothesis. The confidence measure used by this system is described in [START_REF] Mauclair | Automatic detection of well recognized words in automatic speech transcription[END_REF], and is called WP/LMBB. This measure is a combination of classical word posteriors (WP) with a measure based on the language model backoff behavior (LMBB). Using the normalized cross entropy (NCE) as an evaluation metric of confidence measures (this is the one used during the NIST campaigns), the WP/LMBB measure obtains 0.266 on the data used for the experiment presented below. This is an interesting score which shows that the WP/LMBB provides reliable information on the correctness of the recognized words.

V. EVALUATION OF COMBINATION BY DRIVEN DECODING

The auxiliary system (the LIUM one) runs a full decoding process as described in Section IV-D, thus providing a transcript with confidence measures. These results are integrated into the primary system using the driven decoding algorithm (DDA) in the Speeral search process as detailed in section II.

The baseline results are the recognition outputs from the LIA, LIUM and a ROVER based combination: LIA-P2 is the result of the entire decoding process of Speeral (performing two passes), LIUM is the result of the entire decoding process of the LIUM system (two passes) and ROVER is a ROVER using LIUM and LIA confidence scores.

A. DDA experiments

The DDA is used here during the second pass of the LIA system: unsupervised acoustic adaptation is applied using the first pass transcript of the LIA system; the second pass using the adapted acoustic models. The first pass is the same as the one used in the LIA baseline system. Results of this DDA process are called LIA-P1 DDA-P2 in the case of Speeral and DDAf in the case of Fastnc (Fastnc experiments use graph computed by the second pass of the LIA baseline system, without DDA).

Table I shows that the DDA process obtains a significant reduction of the word error rate (WER) in comparison with the best baseline system for a given show (up to 2.4% absolute WER reduction). The best global reduction is 2% absolute in comparison with the best baseline system (21.2% WER for the LIUM system, 19.2% WER for the DDA system).

Moreover, these experiments show that DDA is able to outperform significantly the ROVER baseline. Especially on the F.Info show where ROVER does not allow for improvement compared to the ASR LIUM system. Finally DDA presents a global WER reduction of 1.4% absolute in comparison with the ROVER baseline system (about 7% relative).

Better results are obtained by using the log-linear combination which is more efficient on all shows.

The Viterbi decoder (DDAf) shows a slight improvement: the word-graphs generated by the LIA system are not fully explored by the A * algorithm because of cut-off, while the Viterbi decoder performs an exhaustive search. However, these experiments highlights that DDA works similarly in a Viterbi framework and in an A * framework.

In order to evaluate the optimal combination of the one-best hypotheses of the two baseline systems, the best combination of the two hypotheses knowing the correct transcription of the utterance is computed. This allows to determine the oracle WER using a ROVER method [START_REF] Fiscus | A post-processing system to yield reduced word error rates: Recognizer Output Voting Error Reduction (ROVER)[END_REF] to merge the results of these two systems. Moreover, the oracle WER using a ROVER among the 3 systems (LIA-P2 baseline, LIUM baseline and DDA system) is also computed.

Results reported in Table II show that the optimal best potential gain obtained using the DDA system is very significant. Mainly, these results underline an interesting feature of the DDA in comparison with combining the two systems through a single-weighted ROVER: by using an oracle between LIA, LIUM and DDA, we observe a gain compared to the LIA-LIUM oracle. This highlights that the DDA approach allows to propose new word hypotheses which were not present in the initial one-best results of the baseline systems. This aspect shows that with the same information used by ROVER, DDA is able to combine information and to explore new paths in the graph (Figure 4). These new paths allows to introduce new hypotheses correlated with auxiliary transcripts, thus confirming the potential gains of an integrated approach.

The next experiments generalize the DDA approach by driving the search process using confusion networks instead of single one-best hypotheses.

B. Confusion network driven decoding

The information used by the driven decoding based on the output transcription of an auxiliary system remains relatively poor. We investigate in this section the benefit of a richer information about the previous run of the auxiliary system. We apply the idea by integrating not only the one-best hypothesis but also the word confusion network (WCN) generated by the auxiliary system.

As with the single best output, the combination method operates at the search level, by dynamically mapping the current word utterance to the confusion network. This is achieved by minimizing the edit-distance between the hypothesis and the WCN (Figure 2). At the decoder level the changes are minor: we only modify the distance function of the dynamic alignment. The distance function becomes : where W CN i is the i th node of the WCN and W CN n i is the n th word of the i th node. The alignment step allows to extract the best projection of the hypothesis in the network; at this point, the rescoring problem is similar to the one-best driven decoding case: linguistic probabilities are reevaluated according to WCN-to-hypothesis matching-score and word posteriors.

d(W CN j , T i ) = 0 when T j = W CN n i else d(W CN j , T i ) = 4 for insertion else d(W CN j , T i ) = 3 for deletion else d(W CN j , T i ) =
We tested confusion network driven decoding using confusion networks from the LIUM system. Results are reported in Table III. We observed a significant improvement compared to the single systems (1.6% absolute WER). Nevertheless, the gain with respect to the one-best driven decoder remains marginal (about -0.1% WER) for the first pass, and no gain is observed after speaker adaptation.

Three reasons might explain this disappointing gain provided by WCN:

• driven decoding based on the one best hypothesis uses both the confidence measures and the final decision taken by the auxiliary search; the latter guides the main search algorithm toward good hypotheses; scoring, especially due to a better support of linguistic information. Since the confidence score is crucial for linguistic rescoring, the difference of confidence measure relevance could impact significantly the final results;

• WCN introduces too much noise: all hypotheses are credited. In the next experiments, we use DDA in order to adapt acoustic models for the second pass.

VI. CROSS ADAPTATION AND DRIVEN DECODING

Cross adaptation has shown to be an efficient and relatively simple method for system combination [START_REF] Prasad | The 2004 BBN/LIMSI 20xRT English Conversational Telephone Speech Recognition System[END_REF]. It consists in adapting acoustic models of a system by mapping them to transcripts provided by another system. This method leads to significant improvements by taking advantage of the acoustic modeling complementarity among systems. We investigate various cross-adaptation schemes by using intermediate transcripts provided by the auxiliary system or by the DDA system.

We test three baseline configurations: a LIA decoding without any unsupervised adaptation (LIA-P1), a DDA decoding without adaptation, and a cross adaptation to transcripts followed by a LIA decoding (LIUM-P1 LIA-P2). Finally, we evaluate 3 acoustic adaptation strategies for the DDA system: acoustic model mapping to the transcript (LIUM-P1 DDA-P2), adaptation using the first pass of LIA decoding (LIA-P1 DDA-P2), adaptation using the DDA first pass decoding (DDA-P1-DDA-P2, Figure 3). Results are reported in table IV Performance by the DDA without speaker adaptation (DDA-P1) is greater than the one obtained by the initial LIA decoding (-2.7% WER) and relatively close to those obtained with the best configuration (-0.6% WER). Moreover, the cross adaptation of LIA models using the LIUM transcripts (LIUM-P1 LIA-P2) outperforms dramatically the classical scheme where the system is adapted using its own transcripts (LIA-P2, reported in the Table IV). Results show that DDA outperforms the baseline ROVER. Nevertheless, it seems clear that the gains are not cumulative: we obtain a maximum of absolute additional gain of 0.3% compared to the driven decoding with models adapted to transcripts from LIA first pass (LIA-P1 DDA-P2).Finally, by combining DDA and cross adaptation, we reach an absolute WER gain of 3.8% compared to the initial Speeral decoding and about 2.2% compared to the LIUM system.

In the next section we investigate DDA method to n-system combination (with n > 2). According to the previous results the best configuration will be used: the one-best with DDA log-linear combination.

VII. MULTI-SYSTEM COMBINATION

Following the general DDA combination paradigm, combining several auxiliary systems can be done in one of two different ways.

The first approach consists in merging the set of auxiliary one-best hypotheses using a vote-based method such as ROVER. The resulting hypothesis drives the decoding performed at the second level using DDA. The second approach consists in considering all information sources as independent word-streams, which can be integrated at the search level. In this full DDA-combination scheme, the current hypothesis is synchronized with each of the auxiliary transcripts, and independent matching scores are computed. Final linguistic rescoring integrates posteriors in order to estimate new linguistic scores according to each information sources and to the primary language model. In this section, the two approaches are compared, using the IRISA ASR system as the second auxiliary source. Finally, we test a last scheme where all single systems and the DDA system outputs are merged by ROVER.

A. IRISA transcription system

Irene is the recognition system developed at IRISA. It is based on word-synchronous beam-search algorithm with HMM acoustic modeling and n-gram linguistic models with a vocabulary of 64k words. The system operates in three steps plus a linguistic post-processing step. The first step uses context-independent acoustic models with a trigram LM to generate a large word-graph which is then reevaluated with a 4gram LM and context-dependent models. A final word-graph is generated in a third pass after MLLR speaker adaptation. Finally, consensus decoding is applied to the 1000best sentence hypotheses list based on a combined acoustic, linguistic and morpho-syntactic score [START_REF] Huet | Morpho-syntactic post-processing of n-best lists for improved French automatic speech recognition[END_REF]. IRISA confidence measures are assessed by the posteriors. B. Generalized DDA 1) Integrated DDA-based combination: In this approach, the outputs of all auxiliary systems are submitted to the primary search. A matching score is computed for each transcript according to its synchronization to the hypothesis. Finally, all linguistic scores are merged by the log-linear combination extended to n systems:

P (wi|wi-2, wi-1) = P (wi|wi-2, wi-1) 1-β N k=1 α δ k (wi) β k (13)
where β k is the weight of the system k:

N k=1 β k = 1, α δ k (w i
) are the posteriors of the words w i provided by the system k and N the number of auxiliary systems.

2) Two-Level ROVER-DDA combination: The principle of the 2-level scheme relies on a first merging step where all auxiliary transcripts are merged. In our experiment, we use ROVER for merging auxiliary system outputs (using the avgconf method). The resulting transcript is then used following the classical scheme of a 2-system DDA combination with LIA as primary system.

C. Results

Baseline results are reported in Table V for each auxiliary system combined with LIA system before (P1) and after (P2) speaker adaptation. The 2-pass strategy is assessed after speaker adaptation based on the transcription from the first driven decoding combination. We also report word error rates for each individual system.

Results show a significant improvement with system combination compared to single systems. Performance achieved by DDA with the LIUM system remains better than the ones obtained with the IRISA system (about 1% absolute WER), the latter exhibiting a higher error rate. Nevertheless, the combination with the IRISA system still improves significantly the initial LIA system performance.

Table VI compares results obtained by the different fusion strategies. First, we observe that the addition of the third system improves systematically the system accuracy. Nevertheless, the ROVER of the 3 single-systems (ROVER-3) obtains results that are close to the best 2-system combination (DDA-LIUM P2). The 2-level method (2-Level DDA-ROVER) provides a more significant WER decrease (0.9% better than DDA-LIUM P1 and 0.3% better than DDA-LIUM P2), but this configuration remains significantly worse than the full DDA approach (DDA-3) in a 3-system configuration (additional gain of -0.5%WER). The last combination method consists in merging all available system outputs including DDA-3 (DDA-3+ROVER). This hybrid method further improves the system accuracy by about 0.3% absolute WER. Globally, the optimal DDA-based combination outperforms both the best single system LIUM (of about 3.3% absolute) and the classical ROVER combination of the 3 single-systems (-1.6% absolute WER).

The results obtained confirm the interest of fusing all information sources into the primary search algorithm. This enables the evaluation of competing hypotheses while taking into account all the constraints and knowledge available. Moreover, accuracy benefits substantially from the addition of the Irene system. Indeed, compared to LIA+LIUM DDA configuration, the relative WER gain is about 7%. The final WER gain is about 4.6 points compared to the single primary system, and to 3.0 points compared to performance of the LIUM system, which is the best single system. The best gain is obtained on RFI show, which is the more difficult session (5.0 points less than to the LIUM-RT, and 4.0 points less than the LIA WER).

D. Driven decoding analysis

1) Oracle DDA: The analysis of multiple system driven decoding is completed, by conducting experiments similar to those proposed in Section V, in order to study the behavior of DDA in this configuration. By comparing the oracle performance on the 3 single-systems (ORACLE-3) with the performance obtained when combining the single-system outputs with the DDA-3 system outputs (ORACLE DDA+ROVER) we show in Table VII that linguistic rescoring allows to guide the search toward alternative paths: the oracle WER improvement means that DDA outputs introduce new correct words; this point confirms that DDA may not be considered as an on-line voting method. However, it is really an integrated approach where additional information is integrated to the global cost function, allowing a new exploration of the search graph.

2) DDA+ROVER: Moreover, we note that ROVER combination of DDA-3 and all single-systems outperforms the pure DDA approach. This result demonstrates that while DDA finds new correct hypotheses, it also deletes some correct ones compared to single-systems. This demonstrates that DDA may benefit from more efficient tuning in order to systematically select more good hypotheses from the auxiliary transcripts.

3) WER at segment level: In this section, we analyze the driven decoding algorithm behavior at the segment level. Systems are presented in the following order: baseline system (i.e. the best single ASR system: LIUM), the LIA system, the IRISA system, the ROVER 3-systems, DDA LIA+LIUM+IRISA, the ROVER 3-systems+DDA, the oracle 3-systems, the oracle 3-systems-DDA.

.

According to the reference segments, we sort each segment according to its WER. We present two analyses which compare the systems at different levels. The first analysis introduces the WER distribution into the same ranges. The second one shows the relative WER for each range based on the WER of the baseline system.

In order to compute WER ranges we use the reference segmentation. Then the WER is computed for each segment. Results are presented in the WER ranges 0-5, 5-10, 10-20, 20-30, 30-40, 40-50 and 50-100. In the distribution based analysis, each segment is assigned into a range according to its score. In the analysis based on the relative WER, the segment classification is according to the baseline (i.e., the best single system LIUM): this allows one to compare the WER evolution inside the segments.

Figure 5 presents the segment distribution according to the WER range: We observe that DDA have a significant impact on the 4 last ranges and the first range. Its behavior is similar to that of the ROVER. The increase on the first range show that DDA is able to improve significantly the ASR output quality, by decreasing WER in very degraded areas.

Figure 6 presents the WER improvement compared to the baseline. This graph allows one to observe the systems complementarity. According to the best system, similar segments in other systems show better WER. Only the range 0-5 presents some degradations, but in this range segments are often very small: an error have a very big WER impact at the segment level. In all other ranges DDA produces better results than the best single ASR system. The 4 last ranges exhibit about 20% WER improvement, while the ranges 5-10 and 10-20 present respectively 7% and 13% relative WER improvement. We observe also that the combination ROVER-DDA yields baseline system (i.e. the best single ASR system: LIUM), the LIA system, the IRISA system, the ROVER 3-systems, DDA LIA+LIUM+IRISA, the ROVER 3-systems+DDA, the oracle 3-systems, the oracle 3-systems-DDA.

. higher improvements in the 3 first ranges. While the DDA allows one to correct degraded segments, rover allows one to improve well decoded segments. These results explain why DDA has a big impact on the most difficult show RFI and why a slight degradation was observed on the same show when DDA was combined with ROVER.

VIII. CONCLUSION We have proposed an algorithm for driven-by-transcript decoding (DDA). This method allows an efficient combination of ASR systems, by rescoring linguistic probabilities according to auxiliary transcripts and word posteriors from auxiliary systems. Once the auxiliary transcripts synchronized to the ASR search algorithm, the current decoding hypothesis is reassessed by exploiting the confidence scores of the auxiliary transcripts. Different configurations were evaluated on the ESTER evaluation corpus. Different strategies have been considered: a simple combination using one pass, an a priori combination by ROVER, a combination using two passes with DDA and two DDA-pass followed by ROVER between all systems. We also experimented several cross-adaptation strategies between systems. The results show that the DDA allows a significant reduction in word error rate. The best configuration is based on two DDA passes followed by ROVER. Moreover, our experiments show that the combination with DDA using the one-best auxiliary hypothesis performs better than the DDA WNC-based system. Finally, the integration of several auxiliary systems (instead of one) brings an additional substancial reduction and significantly exceeds the combination of 3 ROVER system. Finally, using the DDA with a final pass in ROVER we get an overall reduction of 3 points of WER (14.5%) compared to the best selected baseline system. The reduction observed over a ROVER therefore shows that DDA is not always an optimal combination. Nevertheless, this gain is higher than those cited in the literature using either ROVER or CNC.

Fig. 1 .

 1 Fig. 1. Synchronization of the search beams with the auxiliary transcript by the DTW algorithm during an asynchronous decoding. Linguistic probabilities are biased according to the similarity of aligned transcripts.

  by A* decoding (Speeral) (Baseline transcript : Face à elle si le journal) (Reference : Allez salut à tous voici le journal) WCN : Allez salut à tous voici le journal

Fig. 2 .

 2 Fig. 2. DDA using WCN.

Fig. 3 .

 3 Fig. 3. Cross adaptation (DDA-P1 DDA-P2)

Fig. 4 .

 4 Fig. 4. Cross adaptation and DDA examples at the graph level.

Fig. 5 .

 5 Fig.5. Segment distribution for each WER range. Results are presented in 7 WER ranges: 0-5, 5-10, 10-20, 20-30, 30-40, 40-50 and 50-100. Systems are presented in the following order: baseline system (i.e. the best single ASR system: LIUM), the LIA system, the IRISA system, the ROVER 3-systems, DDA LIA+LIUM+IRISA, the ROVER 3-systems+DDA, the oracle 3-systems, the oracle 3-systems-DDA.

Fig. 6 .

 6 Fig.6. WER compared to the baseline: segment classification is based on baseline. Results are presented in 7 WER ranges: 0-5, 5-10, 10-20, 20-30, 30-40, 40-50 and 50-100. Systems are presented in the following order: baseline system (i.e. the best single ASR system: LIUM), the LIA system, the IRISA system, the ROVER 3-systems, DDA LIA+LIUM+IRISA, the ROVER 3-systems+DDA, the oracle 3-systems, the oracle 3-systems-DDA.

TABLE II WORD

 II ERROR RATES FOR oracle ROVER COMBINATION OF SYSTEM OUTPUTS: COMBINATION OF THE BASELINE SYSTEMS ONLY vs. COMBINATION OF THE BASELINE SYSTEMS WITH DDA (AND THEN DDAf ).

TABLE III WORD

 III ERROR RATES FOR CONFUSION NETWORK DRIVEN DECODING

  .

		F. Inter F. Info	RFI	Average
	LIUM	18.5	18.9	25.6	21
	LIA-P1	22.5	23.3	26.3	24
	LIA-P2	21.1	22.2	24.6	22.6
	LIUM-P1 LIA-P2	20.4	21.8	24.1	22.1
	DDA-lin-P1	18.1	18.7	23.6	20.1 (-2.0)
	DDA-log-P1	17.8	18.1	22.4	19.4 (-2.7)
	LIA-P1 DDA-lin-P2	18.1	18.4	23.1	19.9 (-2.2)
	LIUM-P1 DDA-lin-P2	17.9	18.1	22.7	19.6 (-2.5)
	DDA-P1 DDA-lin-P2	17.9	18.1	22.7	19.6 (-2.5)
	LIA-P1 DDA-log-P2	17.8	18.0	22.5	19.4 (-2.7)
	LIUM-P1 DDA-log-P2	17.5	17.9	22.0	19.1 (-3.0)
	DDA-log-P1 DDA-log-P2	17.2	17.8	21.5	18.8 (-3.3)

TABLE IV VARIOUS

 IV SCHEMES OF CROSS ADAPTATION COMBINED TO DRIVEN DECODING : ADAPTATION TARGETS ARE PROVIDED BY LIUM DECODING (LIUM-P1 DDA-P2), LIA FIRST PASS DECODING (LIA-P1 DDA-P2), DDA FIRST PASS DECODING (DDA-1 DDA-2). RESULTING WER ARE COMPARED TO SINGLE LIA DECODING (LIA-P1), DDA FIRST PASS DECODING (DDA-P1), AND LIA DECODING BY ADAPTING TO TRANSCRIPTS (LIUM-P1 LIA P2).

TABLE V WORD

 V ERROR RATES FOR DDA COMBINATION OF LIA SYSTEM WITH AN LIUM SYSTEM (DDA-LIUM) AND IRISA SYSTEM (DDA-IRISA) WITH (P1 AND WITHOUT (P2) UNSUPERVISED SPEAKER ADAPTATION. EXPERIMENTS PERFORMED ON 3 HOURS OF FRENCH BROADCAST NEWS FROM THE ESTER CORPUS.

TABLE VII COMPARISON

 VII OF THE oracle PERFORMANCE ON THE 3 SINGLE SYSTEMS (ORACLE-3) WITH THE PERFORMANCE OBTAINED WHEN COMBINING THE SINGLE SYSTEM OUTPUTS WITH THE DDA-3 SYSTEM OUTPUT (ORACLE DDA-3+ROVER). THE oracle WER IMPROVEMENT MEANS THAT DDA OUTPUTS INTRODUCE NEW CORRECT WORDS.

		F. Inter F. Info	RFI	Average
	ORACLE-3	10.3	10.5	14.5	11.8
	ORACLE DDA-3+ROVER	9.8	10.0	13.6	11.1


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

SEMIOTIC STRUCTURE LABELING OF MUSIC PIECES : CONCEPTS, METHODS AND ANNOTATION CONVENTIONS

Music structure description, i.e. the task of representing the high-level organization of music pieces in a concise, generic and reproducible way, is currently a scientific challenge both algorithmically and conceptually. In this paper, we focus on semiotic structure, i.e. the description of similarities and internal relationships within a music piece, as a low-rate stream of arbitrary symbols from a limited alphabet and we address methodological questions related to annotation.

We formulate the labeling task as a blind demodulation problem, whose goal is to identify a minimal set of semiotic codewords, whose realizations within the music piece are subject to a number of connotative variations viewed as modulations. The determination of labels is achieved by combining morphological, paradigmatic and syntagmatic considerations relying respectively on (i) a morphological model of semiotic blocks in order to define their individual properties, (ii) the support of prototypical structural patterns to guide the comparison between blocks and (iii) a methodology for the determination of distinctive features across semiotic classes. Specific notations are introduced to account for unresolvable semiotic ambiguities, which are occasional but must be considered as inherent to the music matter itself. A set of 500 music pieces labeled in accordance with the proposed concepts and annotation conventions is being released with this article.

INTRODUCTION

Music can be defined as "the art, process and result of deliberately arranging sound items with the purpose of reflecting and affecting senses, emotions and intellect" [START_REF]Mixture of several definitions from various sources[END_REF]. From a more operative viewpoint, music can be approached as a set of sounds organized by human composers for human listeners. From these definitions, the role of structure in the musical process appears as rather essential, as it is both a constituent and a support of the musical discourse.

In the domain of MIR, music structure is frequently considered as a central element to music description and modeling, but also as a scientific challenge, both algorithmically and conceptually [START_REF] Paulus | Audio-based music structure analysis[END_REF]. This situation has triggered significant effort in the MIR community, towards the production of annotated resources [START_REF]SALAMI Project[END_REF][4] and the organization of evaluation campaigns [START_REF][END_REF].

At the scale of an entire piece, music structure is a concept which can be approached in several ways : a. The acoustic structure which consists in describing the course and turns of active sources and/or timbral textures within the piece : singer(s), lead entries, instrumentation, etc… b. The functional structure which is based on usual designations of the different parts in terms of their role in the music piece, for instance : intro -versechorus -bridge -etc… (cf. [START_REF]Ten Minute Master n°18[END_REF], for instance), c. The semiotic structure which aims at representing, by a limited set of arbitrary symbols (called labels), the similarities (and interrelations) of structural segments within the piece.

These various views of music structure have influenced the design of methods and algorithms for the automatic analysis of audio data, for instance [START_REF] Foote | Automatic audio segmentation using a measure of audio novelty[END_REF][8] [START_REF] Müller | Towards structural analysis of audio recordings in the presence of musical variations[END_REF].

However, in spite of a need and an interest for methodological and operational concepts [START_REF] Peeters | Deruty : Is Music Structure Annotation Multi Dimensional ? LSAS[END_REF] [START_REF] Smith | Design and Creation of a Large-Scale Database of Structural Annotations[END_REF], there is no well-established principles for the structural annotation of music pieces, either in terms of problem statement, procedure, or annotation conventions, even in "simple" cases like pop songs.

In this context, some of our former work [START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks : A Structural Description of Music Pieces[END_REF][13] has been focused on the definition of structural block boundaries. In this article, we address the labeling task, i.e. the determination of equivalence classes between structural segments so as to obtain a symbolic transcription of the piece's structure. Our methodology is primarily designed for audio data but can also be applied to written music.

By approaching a music piece as a "communication system", we formulate (section 2) the labeling task as the resolution of an ill-posed problem, for which the solution is seeked by assuming that recurring properties and systematic differences across structural blocks are more prone to be semiotically relevant than irregular and occasional variations.

Within this scope, semiotic analysis aims at ensuring a trade-off between :

coverage : i.e. to encompass the largest possible number of musical properties in the semiotic description regularity : i.e. to obtain a transcription as regular as possible and relating to a simple prototypical pattern. accuracy : i.e. to account as faithfully as possible for the distinctive properties across semiotic elements. compactness : i.e. to limit the semiotic alphabet to a reasonable number (and distribution) of elements.

This trade-off is obtained by combining methodological criteria based on morphologic, syntagmatic and paradigmatic considerations (section 3).

In section 4, we introduce annotation conventions which cover the most typical situations but which also handle occasional semiotic ambiguities, i.e. segments undecidedly belonging to two classes at the same time.

We release, with this article, a set of approximately 500 music pieces, annotated with the proposed conventions, and accompanied with additional documentation.

CONCEPTUAL APPROACH

The semiotic annotation of a music piece consists in summarizing its high-level structure as a short sequence of arbitrary symbols drawn from a limited alphabet, for instance :

A B C D A B C D E C D C D D

In the scope of this work, we suppose that the elements thus indexed are structural segments (or blocks) of comparable size and at a typical timescale between 10 and 25 seconds.

A music piece viewed as a communication system 2.1

Assuming the existence of a semiotic description of music structure is intimately linked to the hypothesis of an underlying communication scheme which governs, at the structural scale, the global narrative organization of the piece.

It is rather commonplace to consider music in general as a means of communication, based on a set of rules and conventions (which clearly depend on the type of music under consideration). Here, we consider that each music piece can itself be viewed as the output of a particular communication system, with its own constituents : a sender (the composer), one (or several) receiver(s) (i.e. listeners), a transmission channel (which can take various forms), a message (the musical narration) and a code, namely the alphabet of semiotic elements (or codewords) with which is built and developed the narration.

From this viewpoint, the codewords are fundamentally piece-specific and they are discovered (and inferred) gradually by the listener while the piece unfolds, i.e. while the musical narration develops. Describing the semiotic structure of a music piece can thus be viewed as a deciphering task based on the observation of the output of a communication system (possibly with the help of more or less conscious knowledge of composition conventions).

Semiotic structure : an ill-posed inverse problem 2.2

Semiotic structure description falls in the category of illposed inverse problems, and therefore cannot be solved unequivocally unless additional constraints are incorporated to condition the solution.

One option could be to try to formulate the conditioning constraints in terms of particular properties of the music substance, more or less specific to the genre of the piece. However, this approach would require sharp expertise, general concordance and a stable status of the compositional rules for all genres, which is difficult to imagine and which would certainly raise major problems of comparability and compatibility of the result across pieces (and annotators).

Our objective is to formulate the properties of semiotic elements (i.e. the conditioning constraints) as generically as possible. This is why, we propose that the structural description of the piece should be approached as some sort of blind information demodulation problem, i.e. the separation of a carrier (the sequence of codewords) and a modulation (the variations in the realization of the codewords), solely based on the behavior and relationships of musical properties, but not on their actual substance.

Inferring a semiotic code : an intuitive example 2.3

Let's consider the following sequence :

A careful study of this sequence reveals that :

-Almost all items are directional.

-Only 4 distinct orientations are observed (say N, E, SE and NW). -Gray level varies but does not show any regular pattern, nor does the tail of the objects, nor their size. -Orientation is driven by a strong syntax (for instance, SE is always followed by NW, NW never by E, etc…) -The shape of item #9 is singular (could be interpreted as pointing SE or NW, though)

Let's now consider this second sequence :

Here, we observe that :

-Almost all items are (also) directional but -Direction is taking all sort of random, unquantizable values -Gray level takes only 4 different values (say 20, 40, 60 or 80 %) -The tail of the objects (still) does not show any regular pattern, nor their size. -Gray level is driven by a strong syntax (for instance 20 % is always followed by 80 %) -The gray-level of item #9 is singular / undecided

The successive values or states taken by the various properties constitute information layers and, in both cases, a particular layer exhibits some systematic and organized behavior : "orientation" in the first sequence, "gray-level" in the second one. The knowledge of their behavior conveys, at a low explicative cost, significant information on the overall sequence. At the same time, the other properties appear mostly as creating different variants (or connotations) in the realization of these properties.

In both cases, the symbolic representation of the most organized information layer is :

A B C D A B C D E C D C D D

and in fact, considering any other property (or combination of properties) would create rather uninformative, much less regular or almost trivial descriptions, such as ABCDE…KLMN, AABCBCDAEBADAA, or AAA…ABAAAAA.

The carrier-modulation model 2.4

In the proposed approach, we assume that the sequence of structural elements can be decomposed into :

-A carrier component which is built on information layers whose behavior, is periodic, cyclic, regular, recurrent, repeated, correlated, quantized, organized… -A modulation component which corresponds to information layers which appear as aperiodic, acyclic, irregular, occasional, erratic, sporadic, uncorrelated, isolated, continuous-valued, scattered, etc…

The sequence of semiotic labels describes the succession of property values taken by the carrier component. The modulation component represents circumstantial or incidental variations of the semiotic elements

Application to music 2.5

At the level of a short musical passage, successions of notes belonging to a given musical scale form an acoustic melody whose properties (amplitude, duration, attack, …) are modulated over time to convey expressivity.

Similarly, at the level of the whole piece, the succession of structural blocks forms some sort of semiotic tune, build on the "scale" of semiotic elements and whose modulation constitute connotative variants across different stages of the musical narration. However, as opposed to conventional music units, those "macro-notes" are piece-dependent and they are primarily inferred by detecting and comparing structural elements over the whole piece.

At this point, it is very important to note that the particular status of a property as being either semiotic (carrier) or connotative (modulation) cannot be a priori decided on the single basis of its nature. Indeed, in a number of pieces, structural blocks are built on a few distinct harmonic progressions which recur throughout the piece together with a strong variability of the melodic line, whereas other pieces may be built on a unique harmonic cycle from the beginning to the end, the melodic line being the only distinctive feature between blocks. Some techno or electro pieces rather use the timbre or the texture to create structural patterns over a constant melodic-harmonic loop. In percussive pieces, the structural organization usually stems from rhythmic properties, etc… Therefore, the analysis of semiotic structure primarily requires to identify, for each music piece, which are the musical information layers (melody, harmony, rhythm, etc…) taking part to the semiotic component.

Semiotic features 2.6

Let us now consider a third toy example, which we suppose to be an other realization of ABCDABCDECDCDD :

Here we have a slightly more complex situation than in section 2.3, in the sense that the structure of the sequence is based on a switch of the semiotic property on which the carrier component is built, as summarized in the table below : It is also worth noting that, in this example, the syntagmatic organization of the sequence plays an essential role in guiding the determination of the relevant semiotic features. Indeed, East is always followed by 20 %, itself always followed by 80 %, and more globally, the pattern N-E-20-80 is observed twice.

Symbol Orientation Gray-level Tail-shape Size

The three ingredients of semiotic structure 2.7

To sum up the underlying process at work behind semiotic analysis, we can distinguish 3 levels of reasoning which jointly participate to the determination of the semiotic description :

-Morphological analysis : intrinsic features of the structural elements composing the sequence (i.e, the properties and the values of these properties). -Syntagmatic analysis : local relations that elements exhibit with their neighbors within the piece -Paradigmatic analysis : similarities and differences which they exhibit with other elements.

The following sections investigate in details these three facets of semiotic structure analysis and how they interact with one another.

METHODOLOGICAL AXES

Morphological analysis 3.1

The morphological analysis of structural blocks is based on the System & Contrast (S&C) model [START_REF] Bimbot | Complementary report to the article[END_REF].

Under this approach, each structural block is assumed to be built around 4 morphological elements (of typically 2 bars each) forming a square carrier system. These elements relate through a (usually 2x2) matrix of simple relationships. Structural blocks can be more complex, but they usually can be reduced to a square stem.

In general, on some musical information layers, the 4 th element departs from the logical sequence formed by the first three (thus creating some sort of punctuation).

The morphology of a square S&C can be written as :

( ) ( ) ( ( ( )))
where a is the "seed" morphological element, f and g are the internal relations between the elements forming the carrier system and a contrast function that represents the (relative) disparity of the 4 th element. S&Cs exist on several musical layers in different forms and at different timescales simultaneously. Their synchronization contributes to the musical consistency of the segment and to its autonomy [START_REF] Bimbot | Decomposition into Autonomous and Comparable Blocks : A Structural Description of Music Pieces[END_REF]. Identifying S&Cs is thus very useful to locate, at the chosen timescale, the boundaries of the structural blocks.

A S&C can be summarized as a quadruplet : , which can be viewed as the "genetic code" of the structural block. Moreover, in many situations, either f or g (or both) are "identity" (id), resulting in well-identifiable morphological patterns such as aaaa, abab, aabb (for ) or aaab, abac, aabc (for ). These patterns can straightforwardly be extended to "close-to-id" or "begins-like" functions : aaa'b, aba'c, aa'bc, …

The morphology of structural blocks can therefore be primarily characterized by the various systems followed by its (say p) active musical layers, i.e. as a multidimensional quadruplet ( ) . In many cases, this quadruplet can be represented more simply as the morphological pattern governing each layer : for instance, for the melodic line, for the harmony, for the drum loop, etc…

Syntagmatic analysis 3.2

Moving back now to the timescale of the entire piece, we discuss how the position and context of structural blocks within the piece can be taken into account in order to guide semiotic labeling. Indeed two structural blocks will be considered to be a priori more likely to belong to the same equivalence class if they appear in similar contexts in the piece, i.e. if they are located beside similar left and/or right segments within the piece. For instance, in the sequence ABxDABy-DECDCDD, x and y are more likely to belong to the same semiotic class than in ABxDyBCDECDCDD. This criterion partly relates to commutability, often used in semiotic analysis.

A second syntagmatic factor to take into account is that differences between two blocks should not be appreciated in the same way if the two blocks are immediately next to each other or if they appear at some distance in the piece : a slight difference observed between two successive simi-lar blocks may be distinctive (especially if this opposition is recurrent in the piece) whereas a stronger difference at a long distance may just be a connotative variation, especially if the two blocks occur in similar contexts.

The guidance of a prototypical structural pattern (see Table I) is also an essential element of syntagmatic analysis, for weighing similarities and differences between and across blocks and interpreting them with respect to the global organization of the piece. However, while the semiotic structure of music tends to be based on recurrent patterns, the actual realization of a structural pattern in a music piece generally shows irregularities (which are bound to increase when getting towards the end of the piece). For instance the structural description ABCDABCDECDCDD can be viewed as a realization of 4 cycles of an (ABCD) structural pattern with growing irregularities towards the end of the piece.

In practice, structural patterns can prove to be very efficient to guide the annotation for some musical genres, but they can also turn out to be totally useless for others.

Paradigmatic analysis 3.3

The goal of paradigmatic analysis is to determine the set of semiotic features within the population of structural blocks, i.e. what are the semiotic properties (and the values taken by these properties) which characterize the equivalence classes (cf. subsection 2.6).

A key concept of this process is that, rather than comparing the surface properties of the structural segments, the semiotic comparison of blocks is based primarily on the comparison of their carrier system, i.e. the triplet (as defined in subsection 3.1) resulting from their morphological analysis. Note that the contrast function is treated separately, as a special form of modulation (see 4.1).

For a given music information layer, the carrier systems of two structural blocks x and y are considered as homologous, if there exist a property of that layer for which the triplets (

) and ( ) are similar. For instance, if the musical layer is the melody, the property can be the melody itself, the support notes of the melody, the shape of the melodic line, etc… This comparison is carried out for all musical layers which show some morphological organization and the subset of common properties that emerges from the comparison provides the characteristics of a potential class encompassing x and y. In particular, if the similarity of the systems holds for all music information layers active in x and y, it is considered that these segments should be grouped into a single semiotic class.

Semiotic features can thus be hypothesized as conjunctions of properties (together with their particular values) occurring in similar S&Cs and these features can be ordered (at least partly) according to their coverage of the various musical information layers.

A global solution is then searched (empirically) as a partition of the population of structural segments grouping those with equivalent carrier systems in the subspace of their semiotic features. In case of several possible solutions, the one yielding the most regular sequence of labels is chosen.

Finally, the set of distinctive features is established as the minimal subset of properties (and their particular values) which is necessary and sufficient to distinguish each semiotic element from all the others.

Of course, the trade-off between accuracy of the description and compactness of the semiotic set is an essential stopping condition. It is conjectured that a "good" a posteriori distribution of labels should follow some sort of Zipf law, or at least should not depart too much from it.

ANNOTATION CONVENTIONS Primary notation of semiotic labels 4.1

Quite naturally, two blocks with non-equivalent carrier systems are denoted by 2 distinct alphabetic capital letters : A vs B.

When two blocks show equivalent carrier systems but different contrasts ( ), this difference is noted as a subscript : A 1 vs A 2 . Blocks showing no (or extremely weak) contrasts are denoted A 0 and conversely, blocks showing exceptional contrasts are denoted A * (they usually tend to occur at the end of the piece).

When two blocks have equivalent carrier systems, but they significantly differ in their (surface) realizations (connotative variants), they are denoted with distinct superscripts, for instance : A' vs A''. Optionally, the superscript may be chosen specifically to indicate the nature of the variant. For instance, the notations A + and A -are used to indicate more or less rich occurrences, and A~ can be used to denote exceptional variants of A.

When a property evolves gradually within a block, this is denoted as a fade-in or a fade-out. This is denoted as <A, A> and it may apply to surface properties such as the intensity, the instrumentation support, or to strengthening or vanishing properties of the carrier system.

If a block is realized only in a half-form, specific notations are used : A/2 for a half-size block, |A and A| for left (resp. right) truncated half block, more general cases of incomplete blocks being denoted as …A or A….

Table II summarizes these annotation conventions.

Composite labels for handling ambiguities 4.2

Inevitably, semiotic labeling leads to some situations which exhibit ambiguities, resulting from the combination or the mutation of semiotic items to create new hybrid ones, namely some sort of chord, at the level of the semiotic structure. This is indeed a natural process in music at many time-scales Therefore, a set of additional notations were designed to render these ambiguities through composite labels (whose configurations are schematized on figure 1). AB (vertical hybrid) : block showing undecided prevalence of properties of A and B, for instance, superposition.

A&B (intrication) : block showing intertwined portions of

A and B. The size of block A&B is the total of that of A and B. B|A (horizontal hybrid) : a specific system (B) is present in the first half of the block but the second half recalls the system of A (sometimes with a different contrast). B<A (kinship) : block B is acceptable as autonomous at the current timescale but it exhibits strong cohesion with the previous block A via some common property or supersystem. The sequence [A][B<A] could be described as a single morphological system at the immediately upper timescale.

B/A (mutation) : morphological system partly similar to A (rooted in A) but with a subset of properties whose system strongly departs from that of the other elements of class A. This is typically the case in some types of solos, where the harmony is common to some former block but the melody of the lead becomes freestyle. This situation also includes cases when the subset of properties is simply void, for example a passage (in particular, an intro) where the instrumental background is played alone, without any main lead.

A?B (indetermination) : ambiguous segment which cannot be annotated unequivocally. A typical situation like this is B?A~, when it is impossible for the annotator to conclude whether the segment is a specific semiotic element B or a very particular connotative variant of item A.

We also introduce notations for short segments that occasionally intervene in between regular ones : A_B (overlap) : i.e. tiling segment corresponding to a partial superposition between A and B. _AB_ (connexion) : short segment located between A and B which cannot decidedly be related primarily to A or B. Even though semiotic structure description is distinct from functional structure description, we consider that it can be informative to choose the semiotic labels in such a way that they somehow reflect the proto-functional status of the block within the piece. We therefore propose to use, as much as possible, the alphabetic letters with the correspondence given in Table III.

Transcription example 4.4

Semiotic symbols can be put into brackets to facilitate visual parsing, especially when they are composite. Due to a lack of space, we leave it to the reader to "decode" the semiotic transcription represented below :

[I/A] [A 1 ] [A 2 ] [B] [C] [J/2] [A' 1 ] [|A' 2 ] [B'] [C] [X/C] [Y/2] [C * ]

Concluding remark 4.5

We want to underline that a primary objective of these notations is to provide a consistent communication language for describing the most obvious aspects of the semiotic structure of music, while also being able to reflect some of its subtle ambiguities.

ANNOTATION EFFORT AND FUTURE WORK

The set of approximately 500 music pieces, for which annotations in terms of structural boundaries have been released in 2011 [START_REF] Bimbot | Methodology and Resources for The Structural Segmentation of Music Pieces into Autonomous and Comparable Blocks[END_REF], has been updated and complemented with semiotic labels obtained with the present methodology and is accessible at [15]. These annotations have been produced manually. They come with additional documentation and with the analysis of some difficulties met during the annotation process. Future work will be turned towards the formalization of the concepts and methodology presented in this article in terms of information theory criteria, and their investigation for the design of models and algorithm for the automatic inference of music structure.

Prototype Illustration Codification Trivial

AAAAAAAA… (A) Binary

ABABABABAB… (AB) Ternary

Figure 1 :

 1 Figure 1 : composite labels (schematic configurations)

  ABBCDDDABBCDDD… (A,2B,C,3D) AcyclicABBCDDDEEF… A,2B,C,3D,2E,… ErgodicABCDBADAAACBCC… {ABCD}TableI: Most common prototypical structural patterns

  Such a situation is very common in music : for instance in a song, verses 1 and 2 may consist of two distinct melodies based on a same harmonic progression while choruses 1 and 2 may be based on two distinct chord loops (while the melodic line would be identical or almost). Indeed, in the case of music, semiotic structure relies on musical properties whose nature varies across pieces but which may also vary within a given piece.Semiotic annotation therefore requires the determination of what we call semiotic features, i.e. not only the semiotic properties but also the particular values taken by these properties to form the carrier component describing the sequence of structural blocks. In the case above, the se-

		North	any	any	any
	B	East	any	any	any
	C	any	20 %	any	any
	D	any	80 %	any	any
	E	Indistinct	Multiple	any	any

miotic properties are orientation and gray-level, while the semiotic features are North orientation, East orientation, 20 % gray-level and 80 % gray-level (the other values of orientation and gray-level being irrelevant to the carrier component).

Table II :

 II Main set of semiotic labels

		Intro	Pre-central	Central	Post-central	Relay	Other (recurrent)	Other (sporadic)	Outro
	Primary set	I, J	A,B	C,D	E,F	J,K	M,N	X,Y,Z	K, L
	Secondary set	G,H	P,Q	R,S	T,U	G,H	V,W		G,H

Table III :

 III Proto-functional semiotic symbols

Acknowledgements

Part of this work was achieved in the context of the QUAERO project, funded by OSEO.