Francesco Foscarin
email: francesco.foscarin@cnam.fr

Florent Jacquemard
email: florent.jacquemard@inria.fr

Philippe Rigaux
email: philippe.rigaux@cnam.fr

Modeling and Learning Rhythm Structure

We present a model to express preferences on rhythmic structure, based on probabilistic context-free grammars, and a procedure that learns the grammars probabilities from a dataset of scores or quantized MIDI files. The model formally defines rules related to rhythmic subdivisions and durations that are in general given in an informal language. Rules preference is then specified with probability values. One targeted application is the aggregation of rules probabilities to qualify an entire rhythm, for tasks like automatic music generation and music transcription. The paper also reports an application of this approach on two datasets.

INTRODUCTION

In the context of music notation, rhythm is commonly modeled as a recursive subdivision of a temporal space organized in measures, beats and sub-beats. This naturally gives rise to a representation based on hierarchical structures (aka Rhythm Trees [START_REF] Agón | Representation and rendering of rhythm structures[END_REF]). Moreover, this subdivision involves, at each level, choices based on the context (in particular the current metre) and on a long-established tradition of best practices. They can be expressed as rules such as the notation convention "beam the notes in order to highlight the beat position" [START_REF] Gould | Behind bars[END_REF]. Those rules (there are countless) express preferences on rhythm with different purposes (e.g. reduce complexity, improve readability, etc.), but remains at an informal level and their application is crafted in both the core of engraving software, and the expertise of their human users.

In the present paper we propose a formal framework to express these rules in a computational context that enables an automatic determination of rhythm structures. Our model is based on Probabilistic Context Free Grammars (PCFG), where production rules and attached weight values specify rhythmic subdivisions in a way that is both formal and close to the musical intuition. Parse trees, representing the grammars' computations, also represent Rhythm Trees (hence score structure). A PCFG acts as a model replacing informal notation rules. One could manually define such a model, but one can also learn this model, as soon as we dispose of a large enough, high quality training set (of parse trees). An immediate thought is to base the learning step on the many corpora of existing (quantized) MIDI files or even digital scores. This gives rise however to an important issue: these datasets provide sequences of quantized events, but there is no direct mean to obtain the hierarchical structures (rhythm trees) that are necessary for learning a grammar. In the case of MIDI input, the rhythmic representation is simply missing (MIDI input). XML-based format such as MusicXML or MEI seem more suitable. However their hierarchical structure is not directly used for encoding rhythmic trees which makes their extraction unreliable. Moreover, there exists many ways to encode with these formats a same input, and this gives rise to ambiguities when it comes to identify a normalized rhythm representation.

In order to overcome this limitation, we propose to produce automatically training sets from collection of quantized input. Since there exists many possible rhythm trees that can be built from a single dataset entry, we need a decision guidelines to determine a unique candidate tree. Our decision method is based on the assumption that the the best rhythmic representation is the one that maximize the notation readability. This assumption is supported by the analysis of music notation conventions, and corresponds to the intuition that the purpose of a notation language is to obtain a concise, accurate and readable representation of the noted content. The main goal of the present paper is to develop an algorithm for training set production based on this assumption, and to validate it on a set of representative datasets.

The production algorithm relies on the definition of a tree minimization criteria, and explores the space of solutions trees that correctly represent a sequence input in order to find the minimal one with respect to this criteria. Given a dataset of sequences, we then apply the algorithm to produce the corresponding training set of minimal rhythm trees, and then carry out maximum likelihood estimation in order to obtain the PCFG (Figure 1).

Finally, we validate our method by running our training algorithm on a set of representative corpus, checking that the obtained PCFG is consistent with best music notation practices. Our results confirm that the best tree decision method based on tree minimization is a reliable computational method to produce PCFG that would, otherwise, have to be manually defined. We believe that our methodology is important for several reasons. First, PCFGs are quite useful for music transcription. In a companion paper [3] we describe an algorithm that takes as input a non-quantized sequence of musical events (e.g., a human performance of some music work, with micro-rhythmic deviations) and relies on a PCFGs to produce a music score. Note, that a PCFG is, in this regard, more powerful than the tree-minimization method mentioned above that only operates on quantized inputs. Another common application for PCFGs is music generation [START_REF] Conklin | Music generation from statistical models[END_REF]. More generally, disposing of a language model is useful to measure in which extent this model is a reliable representation of the actual language used in a corpus. In concrete terms, it can be used for instance to evaluate the quality of an existing notation, or to detect outliers in a corpus (e.g., scores of MIDI files that present an unusual rhythm). In general, we consider that this constitutes a quite useful analytic tool to make sense of sequential inputs that can be structured, quantified, explored and compared.

Lastly, the necessity of having a good grammar is fundamental to all the applications cited above. The technique presented in this paper allows to automatically build a grammar from a large dataset of scores or MIDI files, avoiding the manual building, a process that is very time consuming and is error prone.

To summarize, the paper: (1) uses PCFGs as a formalization of rhythm notation rules (Section 3), (2) learns PCFGs from datasets of music events sequences, producing training sets thanks to a complexity minimization criteria, (Section 4) and (3) validates that the resulting PCFGs trained on a dataset indeed accurately capture the best practices established in music notation (Section 5). We begin by Section 2 that briefly reviews some of the current works that use trees and grammar to work with rhythm and conclude with Section 6.

STATE OF THE ART

Many works in the literature rely on linear models (e.g., ngrams) that apply to the sequential flow of music events [START_REF] Takeda | Hidden markov model for automatic transcription of midi signals[END_REF].

Another category, more suited to represent the hierarchical structure of rhythm notation, are models based on trees and grammars. Starting from the Generative Theory of Tonal Music by Lerdahl & Jackendoff [START_REF] Lerdahl | A generative theory of tonal music[END_REF], those models have been successfully explored for rhythmic notation processing and evaluation [START_REF] Agón | Representation and rendering of rhythm structures[END_REF][START_REF] Nauert | A theory of complexity to constrain the approximation of arbitrary sequences of timepoints[END_REF][START_REF] Jacquemard | A structural theory of rhythm notation based on tree representations and term rewriting[END_REF], meter detection [START_REF] Mcleod | Meter detection and alignment of midi performance[END_REF], melodic search [START_REF] Bernabeu | Melodic identification using probabilistic tree automata[END_REF] and music analysis [START_REF] Granroth-Wilding | Statistical parsing for harmonic analysis of jazz chord sequences[END_REF][START_REF] Rohrmeier | Towards a generative syntax of tonal harmony[END_REF][START_REF] Nakamura | Tree-structured probabilistic model of monophonic written music based on the generative theory of tonal music[END_REF][START_REF] Marsden | No longer'somewhat arbitrary': calculating salience in gttm-style reduction[END_REF].

In [START_REF] Bernabeu | Melodic identification using probabilistic tree automata[END_REF], probabilistic tree automata (PTA) learning techniques are used for symbolic melody recognition. More precisely, given one melody M represented as a melodic tree (a structure similar to our parse trees), a PTA A M is computed, so that, when given another melody M , A M will return the probability that M is a cover (or a variation, or a plagia) of M . Therefore, although the objectives of [START_REF] Bernabeu | Melodic identification using probabilistic tree automata[END_REF] differ from ours, a dataset of melodic trees was needed in this work. However, this dataset is small, and can be constructed manually since, by definition, only 1 melody is needed in order to train 1 automaton.

In [START_REF] Jacquemard | Generating equivalent rhythmic notations based on rhythm tree languages[END_REF][START_REF] Ycart | A supervised approach for rhythm transcription based on tree series enumeration[END_REF], a notation of rhythm languages defined by formal context-free grammars is proposed in order to fix the kinds of rhythmic notation to consider using declarative rules. In [3], we propose techniques based on weighted context-free grammars for automatic rhythm transcription, but the grammar is assumed given and no details are given about the procedure to construct it. In this paper we start from the same settings but we focus on the grammar creation, using results for context-free-grammars presented in [START_REF] Chi | Estimation of probabilistic context-free grammars[END_REF] to obtain a model that can be trained on a dataset.

MODEL SPECIFICATION

Probabilistic Context-Free Grammars (PCFGs) extend CF grammars with rule probabilities. Computations of PCFGs are conveniently represented as hierarchical structures called parse trees. As observed in several papers, such tree structure are natural representations of common Western notation for rhythms, as they reflect structural nested decomposition of measures into beats.

Context Free Grammars for Rhythm

A PCFG is a tuple G = Q, q init , R where (i) Q is a finite set of non-terminal symbols (nt), denoted q 0 , q 1 . . . , (ii) q init ∈ Q is a starting non-terminal, and (iii) R is a finite set of weighted production rules of one of the two following types, where w is a weight value in [0, 1]:

(k-div) q 0 --→ w q 1 . . . q k with q 0 , . . . , q k ∈ Q and k > 1, (leaf) q 0 --→ w n with q 0 ∈ Q and n ∈ N,
such that for all q 0 ∈ Q, q0-→ w α∈R w = 1 (where α stands for q 1 , . . . , q k ∈ Q or n ∈ N). The nt q 0 is called the head of both above rules. A production rule (k-div) describes the division of a time interval into parts of same length, e.g. the division of a quarter note into 2 eight notes (for k = 2) or into a triplet (for k = 3). The recursive application of (k-div) rules represents nested divisions. A (leaf) rule expresses that the time interval I reached in nt q 0 contains n events, all aligned at the left bound of I. When n > 1, it means that we have n -1 grace notes, of theoretical duration 0, followed by one note spanning over I. When n = 0, I is called a continuation, and its function is similar to that of a tie or a dot in music notation. Continuations are a fundamental concept in our model, since they practically allow us to split a note in multiple parts that span multiple terminal symbols. The weight of nested divisions and event alignments is the product of the weights of all the rules involved.

Example 1. Let us consider the PCFG in Table 1. Applying the rule ρ 1 to [0, 1[ results in two sub-intervals [0, 1 2 [ and [ 1 2 , 1[, and both of them can be processed with any rule with head q 1 2 . Assume that we apply ρ 11 to the first subinterval and ρ 3 to the second one, which is then divided Following our focus on rhythmic notation, the rules of type (leaf) only care about numbers of musical events, and contain no information about the events themselves, like pitch values, or the nature of events (note or chord). For a representation of melodies, one could replace the natural numbers in (leaf) rules by terminal symbols in some alphabet appropriate to the representation of musical events.

Parse Trees

We formalize the computations of a PCFG G = Q, q init , R with the notion of parse tree, which is a tree t labeled with rules of R, such that: every inner node of t is labeled by a (k-div) rule, every leaf of t is labeled by (leaf) rules, and if an inner node η is labeled by ρ = q 0 --→ w q 1 . . . q k , then it has exactly k subtrees t 1 ,. . . , t k whose respective roots have heads q 1 , . . . q k . The subtree of t with root η is then denoted by ρ(t 1 , . . . , t k ). The weight weight(t) of a parse tree t is the product of the weights of all the transitions labeling its nodes. It is defined recursively by

weight ρ(t 1 , . . . , t k ) = w × k i=1 weight(t i ) when ρ is q 0 --→ w q 1 . . . q k and weight(ρ 0 ) = w for ρ 0 = q 0 --→ w n.
Example 2. The parse tree corresponding to the computation described in Example 1 is depicted in Figure 2.a.

Timelines and Parse Tree Serialization

We consider in the following time-points expressed in fraction of 1 measure (a rational value). A timeline = I, σ is the representation of a sequence of events made of a leftopen time interval I = [p, p [ called carrier of and a sequence σ of time-points inside I. We assume that σ is increasing but not strictly increasing (i.e. it may contain repetitions). Also, the first event in σ may be distinct from the left bound p of I. In this case (and also when σ is empty), it means that starts with a continuation. The concatenation of two timelines

1 = [p 1 , p 1 [, σ 1 and 2 = [p 2 , p 2 [, σ 2 such that p 2 = p 1 is a timeline = [p 1 , p 2 [, σ where σ is the concatenation of σ 1 with σ 2 .
We associate to every parse tree t of a PCFG G and time interval I a timeline denoted t I and defined by: ρ 0 [p,p [ = [p, p [, (p, . . . , p n ) for ρ 0 = q 0 w -→ n, and ρ(t 1 , . . . , t k ) I is the concatenation of the timelines t 1 I1 , . . . , t k I k , for ρ = q 0 --→ w q 1 . . . q k , and where I 1 , . . . , I k is a partition of I into k sub-intervals of equal duration.

Example 3. The parse tree t = ρ 1 ρ 11 , ρ 3 (ρ 16 , ρ 17 ) of Figure 2.a is associated, for the time interval [0, 1[, the timeline represented in Figure 2.b, computed as follows Note that due to the cont, the timeline has 2 events, even if the parse tree has 3 leaves.

(the operator + denotes timeline concatenation):

t [0,1[ = ρ 11 [0, 1 2 [ + ρ 3 (ρ 16 , ρ 17 ) [ 1 2 ,1[ = ρ 11 [0, 1 2 [ + ρ 16 [ 1 2 , 3 4 [ + ρ 17 [ 3 4 ,1[ = [0, 1 2 [, (0) + [ 1 2 , 3 4 [, ( ) + [ 3 4 , 1[, ( 3 4 ) = [0, 1[, (0, 3 4 ) .
We say that a parse tree t yields a timeline = I, σ iff t I = . Therefore every parse tree t of a PCFG G yields an organization t k I of events in time and also a grouping structure for these events. In other terms, t is a consistent representation of music events with respect to the notation defined by G, and given a time signature, a music score can be constructed from it (Figure 2). We call this process score production. Differently from the serialization process, the continuations remain in the final result of the score production. A parse tree can be used to represent an entire score or part of it. In this paper we represent each measure of a score with a different parse tree, i.e. the timeline produced by the serialization of a parse tree will represent a single measure. To summarize, we use parse trees as a model for both rhythmic structure and rhythmic notation.

MODEL TRAINING

We consider the problem of computing weight values in the rules of a PCFG from a dataset made of timelines. Approaches based on maximum likelihood estimator [START_REF] Chi | Estimation of probabilistic context-free grammars[END_REF] permit to obtain such weights from a training set made of parse trees. Therefore, in order to apply such approaches (in Section 4.2), we need to convert datasets of timelines into training sets containing parse trees (Section 4.1).

Training Set Construction from a Score Corpus

As mentioned in the introduction we produce a training set of parse trees from a dataset of monophonic sequences extracted from a corpus of scores. This applies to a wide range of input scores, from (quantized) MIDI files to XML scores. In the latter case, one could potentially benefit from the grouping elements (beaming and tuplets) in the music notation, but this information calls for high-quality corpora where the notation complies to the best practices. Our approach holds independently from such assumptions. From each score (or MIDI file) in the corpus, each part in the score, each voice in the part, and each measure in the voice, we extract a timeline (of carrier [0, 1[) from the list of event durations. We use this dataset D of extracted timelines as input to build parse trees. The resulting set of parse trees is the training set T used for learning a grammar.

Let us assume given an acyclic grammar G = Q, q init , R whose weight are initially unknown (we call such G unweighted). We produce for each timeline ∈ D one parse tree t of G such that t [0,1[ = , called the representative of in the training set. Since there exists several possible parse trees, we need a criteria to choose a unique representative. We choose the tree t with a minimum number of leaves. This choice makes sense both from a computational and from a musical point of view. In fact, we prefer that the scores produced by G not to be crowded with useless notes and ties. Later in Section 5.3 we will show that the results obtained with the above criteria are coherent with some common recommendations for rhythm notation. It means that the trained PCFG will be suited to represent both rhythm and rhythm notation wrt such recommendations.

The following function rep returns for a nt q ∈ Q and a timeline = I, σ , a parse tree t of G, with root headed by q, yielding , and with a minimal number of leaves. In the definition of rep, the min of a set T of trees is the tree with a minimum number of leaves. This min is undefined when T is empty or contains at least two trees with a minimum number of leaves.

If σ is empty or all points of σ coincide with the left bound of I, then rep(q 0 , ) = ρ 0

(1)

where ρ 0 = q 0 → |σ|, if ρ 0 ∈ R, or else rep(q 0 , ) is undefined. For the other cases of σ,

rep(q, ) = min ρ=q→(q1,••• ,q k ) ρ rep(q 1 , 1 ), . . . , rep(q k , k ) (2)
where 1 , . . . , k is the partition of into k timelines of equal duration.

Example 4. Let us present some steps of the computation of rep for the grammar in Table 1 (forgetting the weight values), and the timeline = [0, 1[, (0, 3 4 ) of Figure 2.

rep(q 1 , ) = min      ρ 1 rep(q 1 2 , 2,1 ), rep(q 1 2 , 2,2 ) , ρ 2 rep(q 1 3 , 3,1 ), rep(q 1 3 , 3,2 ), rep(q 1 3 , 3,3 )
where

2,1 = [0, 1 2 [, (0) , 2,2 = [ 1 2 , 1[, ( 3 4 ) , 3,1 = [0, 1 3 [, (0) , 3,2 = [ 1 3 , 2 3 [, ( ) , 3,3 = [ 2 3 , 1[, ( 3 4 )
.

Following (1), rep(q 1 2 , 2,1 ) = ρ 11 , rep(q 1 3 , 3,1 ) = ρ 14 , and rep(q 1 3 , 3,2 ) = ρ 13 . For rep(q 1 2 , 2,2 ) and rep(q 1 3 , 3,3 ), more computation steps are needed.

The function rep can be implemented efficiently with Dynamic Programming through a tabulation procedure similar to the CYK parsing algorithm [START_REF] Kasami | An efficient recognition and syntaxanalysis algorithm for context-free languages[END_REF].

The representative of a 1-measure timeline in the dataset D is rep(q init , ). It may be undefined, either because there is no parse tree t of G yielding , or, on the contrary, because there are more than one such parse trees of G with a minimum number of leaves. In the first case, G is too small to represent D and should be completed. The second case is discussed in Section 4.2. This simple definition of rep is correct because the function which associate to a tree its number of leaves is monotonic, i.e. if t i has more leaves than t i , then ρ(t 1 , . . . , t i , . . . , t k ) has more leaves than ρ(t 1 , . . . , t i , . . . , t k ). It follows that we can build a best representative t for a timeline (wrt this criteria) from best representative for sub-timelines of (which are sub-trees of t).

Computation of Grammar's Weights

Let T be our training set of parse trees. We then compute the weight values for the rules G with a Maximum Likelihood Estimator [START_REF] Chi | Estimation of probabilistic context-free grammars[END_REF]. For a rule ρ = q 0 → α, where α is either q 1 , . . . , q k or n ∈ N, let C T (ρ) be the number of occurrences of ρ in the trees of T . The weight value for the rule ρ is then defined as

C T (ρ) q0→β∈R C T (q 0 → β) .
One can check that the grammar G defined from G with these weight values is a PCFG, according to the definition in Section 3.1 (see [START_REF] Chi | Estimation of probabilistic context-free grammars[END_REF]).

Given a timeline ∈ D, it may happen that its representative is undefined because there is more than one parse tree yielding with minimum number of leaves, see the example in Figure 4. In this case, it is not possible to choose a unique representative, and we will initially discard such . However, those timelines may contains useful information, and we propose the following two step procedure:

1. compute the training set T like in in Section 4.1, using only the timelines of D with a defined (unique) representative, and define weight values for G from T as above, resulting in a PCFG G .

2. for every timeline ∈ D discarded at step 1, compute a representative t which is a parse tree of G build with a modification of the function of Section 4.1 where the min wrt the number of leaves of t is replaced by the max of weight(t). Compute new weight values with these representatives, resulting in a new PCFG G .

IMPLEMENTATION

In this section we first propose two different families of unweighted acyclic grammars acting as input to the construction of Section 4, then we present the result of the grammar learning algorithm from some score corpora along with some consideration from a musical perspective.

ρ 1 : q 1 0.6 --→ q 1 2 , q 1 2 , ρ 2 : q 1 0.2 --→ q 1 3 , q 1 3 , q 1 3 ρ 3 : q 1 2 0.1 --→ q 1 4 , q 1 4 , ρ 4 : q 1 2 0.7
--→ q 1 6 , q 1 6 , q 1 6 ρ 5 : q 1 3 0.6

--→ q 1 6 , q 1 6 , ρ 6 : q 1 3 0.3 --→ q 1 9 , q 1 9 , q 1 9 ρ 7 : q 1 0.05

--→ 0, ρ 8 : q 1 0.1 --→ 1, ρ 9 : q 1 0.05 --→ 2 ρ 10 : q 1 2 0 -→ 0, ρ 11 : q 1 2 0.1 --→ 1, ρ 12 : q 1 2 0.1 --→ 2 ρ 13 : q 1 3 0.05 --→ 0, ρ 14 : q 1 3 0.05 --→ 1, ρ 15 : q 1 3 0.0 --→ 2 ρ 16 : q 1 4 0.1 --→ 0, ρ 17 : q 1 4 0.8 --→ 1, ρ 18 : q 1 4 0.1 --→ 2 ρ 19 : q 1 6 0.3 --→ 0, ρ 20 : q 1 6 0.7 --→ 1, ρ 21 : q 1 6 0 -→ 2 ρ 22 : q 1 9 0.5 --→ 0, ρ 23 : q 1 9 0.3 --→ 1, ρ 24 : q 1 9 0.2
--→ 2 Table 1. An example of grammar with K max = 3, D max = 2 and gn max = 2. Rules 1 to 9 are k-div rules and from 10 to 24 they are leaf rules.

Use-Cases of Unweighted Grammar

In theory, the learned grammar (the one given to the learning step, composed of rules without weights) must be as complete as possible. However, for practical reasons and in particular the size of a grammar that would represent all possible rules, we need to adopt some restrictions. In our implementation, we chose to:

1. allow k-div rules only with k prime number, up to a prime number K max . Other k -split can be obtained by sequential splits by the prime-number factors of k, e.g. to represent a 6-tuplet, we split by 2 and 3.

2. allow sequential rule application up to a maximum depth D max , e.g. with D max = 2 we can split an interval in k sub-interval, recursively split each one of them and then stop the recursion.

3. allow only gn max events in a interval, i.e. gn max -1 grace-notes and one general-note.

The following are examples of practical PCFGs that respect these choices.

Example 5. A first possibility (see Table 1) is to define on rules that do not distinguish intervals of equal size in a measure, whatever their position . Thus, [0, 1 2 [ and [ 1 2 , 1[ are represented by the same non terminal q 1 2 . Each non terminal symbol represents a time interval of a specific duration, and the terminals productions specify how many events are contained in that interval (aligned to the left boundary). Given the grammar of Table 1 an informal notational rule for a 6 8 metric like: "prefer to divide in 2 parts at measure level and subsequently in 3 parts" will translate in our framework in weight(ρ 1 ) ≥ weight(ρ 2 ) and weight(ρ 4 ) ≥ weight(ρ 3 ).

The grammar above is reduced in size, but does not allow for fine-grained distinction of rules based on the position of an interval in a measure, e.g., starting on a strong beat or not. Another possibility is given below. Example 6. Another possibility is to use a larger set of non-terminal symbols that can distinguish intervals both on the level of recursion and on the horizontal position. For instance, the first half of a measure can be treated differently from the second half, or grace notes (in (leaf) rules) can be allowed for the first note of a tuplet and forbidden for the others. It allows to formally represent rules such as: "Prefer to have longer notes on stronger beats" (given that the time intervals that correspond to "stronger beats" are known), by assigning a higher probability to a leaf rule in those intervals and a higher probability of a k-div rule to the other intervals at the same level.

Score Corpora and Datasets

We trained the two grammars presented in the above section with the 1-measure timelines extracted from two corpora of scores: Music21 corpus 1 and Enhanced Wikifonia Leadsheet Dataset (EWLD) dataset [START_REF] Simonetta | Enhanced wikifonia leadsheet dataset[END_REF]. We could compute grammars for the whole dataset but there exist subsets of scores sharing some common properties that are likely to yield more consistent grammars if they are processed independently. One such property is for instance the time signature. Other possible groups could be inferred by style, tempo marking and author, depending of the level of precision that is required. We chose to divide our datasets in four subsets defined by the following time signatures: 4 4 , 3 4 , 6 8 , 12 8 . The number of scores for each group is reported in Table 2.

Within each score, we performed a simple operation of data cleaning, deleting the measure whose events durations did not sum to the correct duration given by the signature (i.e. pickup measures), final measures or incorrectly notated measures.

Trained PCFG from a Notational Point of View

In this section we analyze the result of the training step from a musical point of view in order to show that the criteria that we used to build unique parse trees from durations (Section 4.1) is coherent with music notation conventions.

From music general conventions [START_REF] Gould | Behind bars[END_REF] we know that different time signatures have different grouping preferences in order to expose the beat (e.g. points were stronger accent are placed). It is interesting to notice that there is an high correlation between the probabilities learned for our grammar (the grammar of the Example 5 is sufficient for this analysis) and the divisions suggested by music notation (Table 3).

For example, music conventions state that a 3 4 measure should be divided first in 3 parts (3 quarter notes); We can translate this rules in a grammar-form assigning a higher probability to the 3-div of a measure (with respect to other k-div at measure level). Looking at the trees that we produced from the 3 4 measures (with the algorithm in Section 4.1), we notice that this notation convention is respected, since our trees have a 3-div at measure level in 82% of the cases.

1 http://web.mit.edu/music21/doc/about/ referenceCorpus.html Our criteria to find the smallest tree (minimization of yield), allows us to build trees that are coherent with notation convention; therefore our model make sense to express rules about both rhythmic structure and rhythmic notation. From another point of view we can say that our criteria of minimizing the leaves generates results similar to that of an expert engraver who aims at making the notation as readable as possible.

CONCLUSIONS AND FUTURE WORKS

In this paper we presented a model of rhythm structure based on context-free-grammars and a way to learn it from a dataset of scores, addressing the problem of the generation of a training set of trees.We show that our model makes sense both from rhythm structure point of view than from a rhythmic notation point of view, comparing the frequency of the divisions in our model, with suggested divisions in music notation.

The complete implementation2 of the grammar generation and learning is made in python and C++. The system is also partially implemented in the online digital score library NEUMA, in order to learn grammars from the corpus of scores online.

With big grammars (particularly with the complete grammar), we still have the problems of sparsity, i.e. we have lots of zeros in the final results. The best solution would be to have a bigger dataset, but alternatively the typical approach is to use a smoothing technique. However we would need to think carefully how to apply the smoothing in order to add probabilities to rare rules in a way that makes sense from a musical perspective.

The next objective is to test those grammar in a music transcription algorithm from a MIDI performance, in order to retrieve at the same time the quantized performance and the relative score. Table 2. The number of scores and measures for each corpus and each time signature considered. The discarded measures are the measures whose sum does not correspond to the correct time signature; the failed measures are the one for which it was not possible to build a tree representative.

Figure 1 .

 1 Figure 1. PCFG training from sequences of musical events.

4 [

 4 and [ 3 4 , 1[. Then, we apply respectively ρ 16 and ρ 17 to the latter two sub-sub-intervals of length 1 4 . The above rule applications result in the division of the initial interval [0, 1[ into a partition made of [0, 1 2 [, [ 1 2 , 3 4 [ and [ 3 4 , 1[. The first part contains a single event, at time 0, the second is a continuation (of the first event), and the last part contains a single event, at time 3 4 . Hence the above computation describes the rhythm represented in Figure 2.b.

Figure 2 .

 2 Figure 2. A parse tree (a), the respective music notation given a metric of 1 4 (b) and timeline given an interval [0, 1[(c). The leaf representing a cont is highlighted in yellow. Note that due to the cont, the timeline has 2 events, even if the parse tree has 3 leaves.

Figure 3 .

 3 Figure 3. Three different trees for the same timeline. The terminal rules corresponding to a a continuation are highlighted in yellow.

Figure 4 .

 4 Figure 4. Two trees yielding the same timeline and corresp. notation in time signature 3 4 or 6 8 . Both have a minimal number of leaves 6 and we cannot choose a representative between them.

Table 3 .

 3 Frequency of divisions suggested in music notation in the sets of trees builded from our datasets of scores. Note that in this table the frequency have been normalized on the possible divisions, not considering terminal productions.

				EWLD
		1st div. by 2	99%	99%
	4/4	2nd div. by 2	98%	99%
		3rd div. by 2	93%	96%
	3/4	1st div. by 3 2nd div. by 2	82% 99%	91% 96%
	6/8	1st div. by 2 2nd div. by 3	70% 90%	60% 91%
		1st div. by 2	74%	98%
	12/8	2nd div. by 2	60%	62%
		3rd div. by 3	71%	93%

Available at https://github.com/fosfrancesco/ Modeling-Rhythm-Structure.git.

Acknowledgments

This work was partially funded by the ANR project Mu-NIR. The authors want to thank Masahiko Sakai for his comments and suggestions.

 --------------------------------------------


T Saad Saoud

S Moindjie

D Munteanu

J L Autran

Natural Radiation Events in CCD Imager at Ground Level

In Charged Coupled Devices (CCDs), radiation-induced events generate electron-holes pairs in silicon that cause artefacts and contribute to degrade image quality. In this work, the impact of natural radiation at ground level has been characterized at sea level, in altitude and underground for a commercial full-frame CCD device. Results have been carefully analysed in terms of event shape, size and hourly rates. The respective contributions of atmospheric radiation and telluric contamination from ultra-traces of alpha-particle emitters have been successfully separated and quantified. Experimental results have been compared with simulation results obtained from a dedicated radiation transport and interaction code.

Introduction

Charged Coupled Devices (CCDs) are known to be very sensitive to natural or artificial sources of radiation. In particular, the interactions of single ionizing particles with the CCD materials generate electron-hole pairs that can be partially or totally collected at silicon (i.e. pixel) level, resulting in image artifacts [1][2]. These artifacts, named "cosmic rays" by astronomers (because mainly induced by secondary cosmic rays at terrestrial level), directly affect the reliability of high performance CCD imagers used in astronomy for example [3]. Radiation-induced artifacts can be isolated and fully characterized (in terms of pixel size, hourly rate and related charge event) considering image captures in total darkness [4].

In the present work, we used a commercial CCDbased astronomical camera to precisely characterize such artifacts induced by natural radiation at ground level. In order to also capture events linked to the internal radioactivity of CCD materials, we performed experiments deeply underground to suppress atmospheric radiation. Three different locations have thus been considered: at sea level (in Marseille), underground (at LSM laboratory [START_REF]Laboratoire souterrain de Modane[END_REF]) and in altitude on the ASTEP platform [START_REF] Astep | Altitude Single event effects Test European Plateform[END_REF]. Measurements reported in this work correspond to long-term experiments, with typical durations of several months. Our experimental results have been systematically compared with results deduced from numerical simulation performed with a dedicated radiation transport and interaction code developed in the framework of this study.

Experiments

Our different experiments are based on the use of a USB2.0 CCD monochrome camera (model Atik 383L) taking one full image per minute (i.e. 1 frame/min) in the complete darkness (Fig. 1). The KAF-8300 image sensor is a high performance monochrome full frame CCD with a square pixel (5.4×5.4 µm 2 ) array and 8.6×10 6 effective pixels. Each pixel contains blooming protection. The camera is a cooled system that maintains the CCD approximately 40°C below the room temperature, reducing by several orders of magnitude the dark noise due to thermal generation. The main characteristics of the image sensor are summarized in the table of Fig. 1.

Dedicated acquisition software has been developed under Matlab® to detect radiation-induced artifacts and to save and process related event images. All details about the capture procedure and image processing will be detailed in the final paper. Fig. 2 shows a panel of typical events detected during a oneyear experiment performed at sea level. The detected events have been classified into single pixel event (SPE) that corresponds to isolated pixels and multiple pixel event (MPE) that corresponds to a group of adjacent or neighboring pixels (i.e. having pixel connectivity).

Experimental campaigns of measurements were performed in three different locations with the same camera and the same setup: at sea level in Marseille, underground at LSM laboratory (under 1700 m of rock, equivalent to 4800 m under water) to completely screen atmospheric radiation and in altitude (2552 m) on the ASTEP platform to increase (by a factor of ≈6 for neutrons) the atmospheric radiation. Fig. 3 shows the global (MPE+SPE) event hourly rate detected during these tests. By comparing event rates obtained at LSM and in Marseille, we can deduce that more than the half (58 %) of detected events at sea level are due to the CCD chip radioactivity, i.e. the contamination by alpha particle emitters present under the form of traces in CCD and/or packaging materials. This contribution of chip radioactivity decreases to 27% for altitude measurements, mainly dominated by atmospheric radiation in this case.

Modeling and numerical simulation

The complete modeling and numerical simulation of the different experiments has been performed. We constructed a simplified but realistic 3D model of the complete pixel array considering dimensions, materials and layers deduced from chip analysis using techniques and instruments used in IC failure analysis. The 3D geometry has been modeled using a C++ computational geometry library developed at IM2NP. The EXPACS atmospheric radiation model [7] has been also implemented in the code to compute the energy distributions of neutrons, protons and muons fluxes. In addition, for alpha-particle emitters, both 238 U and 232 Th decay chains have been simulated for contaminants uniformly distributed (for simplicity) in the bulk of all chip material layers. The interactions of neutrons and high-energy protons with circuit materials have been implemented on the basis of pre-calculated Geant4 databases. For all other ionizing particles (secondary products, low energy muons and protons, alpha particles), a direct ionization process has been considered. When a particle interacts with the CCD materials, the code evaluates the amount of charge (energy) directly deposited into the pixels and the additional amount of charge collected by the pixels from the substrate, considering a diffusion-collection model in the silicon region. For each interaction event impacting the pixel array, the code calculates the resulting numerical image and save it for postprocessing and comparison with experimental signatures. Fig. 4 shows a few simulated images computed with this code for Marseille location. Fig. 3 shows that the sum of the pixel event rates for both atmospheric (neutrons + protons + muons) and telluric contributions (alpha) match very well the experimental values at ground level. These results also highlight the importance of atmospheric charged particles in the CCD response, especially at sea level and in altitude. All these results will be in-depth analyzed in the final paper in complement to the accurate description of the modeling/simulation approach.

Figure 1 :

 1 Figure 1: Used camera, experimental setup and CCD imager characteristics.

Figure 2 :

 2 Figure 2: Some examples of radiation-induced events detected during the long-term experiments.

Figure 3 :

 3 Figure 3: Comparison between experimental and simulated event rates at the different experiment locations. The contributions of the different atmospheric particles and alpha particle emitters are also reported.

Figure 4 :

 4 Figure 4: Panel of images obtained with the developed simulation code.


D Munteanu

J L Autran

3D Simulation of Heavy Ions-Induced Single-Event-Transient Effects in Symmetrical Dual-Material DG MOSFET

Dual-Material Gate Double-Gate (DMDG) structure is promising for future ultra-scaled devices thanks to its capability to reduce SCEs and HCEs. This is due to a step in the surface-potential profile which screens the source side of the channel from drain-potential variations and reduces the drain electric field. In this work, we investigate the DMDG sensitivity to single-event transients. The impact of dual gate materials on the bipolar gain is particularly addressed. We show that DMDG is naturally less radiation immune than usual single-material DG (SMSG) devices.

Introduction

Double-Gate (DG) MOSFETs have received particular interest in the last decades due to its promising capabilities for nanometer scaling. Many theoretical and experimental studies have reported on the very good control of parasitic short channel effects (SCE) and ideal subthreshold slope of DG transistors [1]. These performances are namely due to the additional gate electrode which sensibly improves the electrostatic control of the channel and allows using intrinsic channel providing no parasitic doping fluctuation effects and increased carrier mobility.

However, as the gate length shrinks, hot-carrier induced effects (HCE) and drain induced barrier lowering (DIBL) phenomena become important issues that need to be addressed [2,[START_REF] Wong | presented at the IEDM Short Course: Sub-100 nm CMOS[END_REF]. In order to prevent undesired HCEs and to enhance the immunity against SCEs, a new concept of DG MOSFETs with dual gatematerial (DMDG) has been proposed and validated [START_REF] Long | [END_REF]5,6,7]. Compared with the conventional single gatematerial double-gate (SMDG) device (Fig. 1a), this new structure has two materials in the gates (Fig. 1b), M1 and M2 with different workfunctions, Φ M1 and Φ M2 , respectively. This configuration induces a step in the surface-potential profile (see Fig. 2) which, for Φ M1 >Φ M2 , simultaneously provides transconductance increase and DIBL reduction. The step function profile of the surface potential ensures screening of the channel region on the source side (under the material M1) from drain-potential variations. In addition, the peak electric field at the drain is considerably reduced, which suppresses HCEs [8].

The transient response of SMDG MOSFETs submitted to heavy-ion irradiation has been investigated by simulation in [9,10]. These previous studies demonstrate that SMDG show better radiation hardness than fully-depleted Single-Gate SOI devices,

V G Single-Material Double-Gate (SMDG) MOSFET Dual-Material Double-Gate (DMDG) MOSFET t Si W x y z Silicon film Gate oxide L G 1 L 2 Φ M1 Φ M2 V G Φ M1
Fig. 1. Schematic description of the simulated symmetrical SMDG and DMDG devices. For a better view, spacers and isolation oxides are not shown.

particularly due to the enhanced control of the body potential and to the reduction of floating body effects. Concerning DMDG MOSFETs, extensive analytical modeling works have been reported in the literature [START_REF] Long | [END_REF]5,6,7], but, at the best of our knowledge, radiationsensitivity studies of these devices have not been performed. In this paper we investigate by 3-D numerical simulation the response to single-event of DMDG compared with that of SMDG. The impact of the material M2 workfunction on single-event transients and bipolar amplification is also addressed.

Simulated devices and models

Simulated SMDG and DMDG devices are designed with the same geometrical dimensions: channel length L G =20 nm, 100 nm gate width, 6 nmthick intrinsic silicon film and 1 nm-thick gate oxide, similar to real devices reported in [11]. In SMDG, a single-material M1 is used for the gates. In DMDG the gates consists of dual materials, M1 (Φ M1 ) and M2 (Φ M2 ), of lengths L 1 and L 2 , respectively (L 1 +L 2 =L G ). In a first time we considered L 1 =L 2 =L G /2.

3-D numerical simulations have been performed with the DESSIS device simulator from Synopsis Inc. [START_REF]Synopsys Sentaurus TCAD tools[END_REF]. The main models used in simulation are the Shockley-Read-Hall and Auger recombination models, the Fermi-Dirac carrier statistics and the hydrodynamic model was used for the carrier transport equations. The impact ionization model depends on carriers energy. The mobility model includes the dependence on the carrier energy, lattice temperature and doping level.

The ion strike was simulated using the DESSIS HeavyIon module [START_REF]Synopsys Sentaurus TCAD tools[END_REF]. The electron-hole pair column created in the device by the ion strike is modeled using a carrier-generation function which has a Gaussian radial distribution with a characteristic radius of 20 nm, a Gaussian time distribution, centered on 10 ps and having a characteristic width of 2 ps. The ion strikes in the channel center (Fig. 1). Devices are biased in the off-state (V G =0V). The drain terminal is constantly biased at the power supply voltage of 1 V.

Static characteristics of DMDG MOSFETs

Heavy-Ion-Induced Transient: DMDG versus

SMDG MOSFETs

Drain current transient

Figure 3 shows the drain current transient resulting from an ion hit in the channel center of DMDG and SMDG for an ion with a linear energy transfer (LET) of 0.1 MeV.cm 2 /mg. The drain current transient peak is higher and wider for DMDG than for SMDG device. The reason is probably a higher bipolar amplification in DMDG case (see next section) due to the stepfunction profile of the channel potential.

Collected charge and bipolar amplification

The variation of the collected charge, Q COLL , as function of LET is plotted in Fig. 4a. Q COLL is obtained by integrating the simulated drain current over the transient duration. The deposited charge, Q DEP , is calculated considering the Gaussian distribution of the ion track and the 3-D geometry of the silicon body. The bipolar gain is then given by the ratio between the Q COLL and Q DEP . The bipolar amplification variations in DMDG and SMDG are shown in Fig. 4b. The LET range considered here corresponds to the LET range of a neutron-induced ion in silicon in the terrestrial environment [START_REF] Fang | [END_REF]. Figure 4 indicates that the bipolar amplification is higher in DMDG than in SMDG, particularly at low LET. The body potential modification in DMDG induced by the presence of a gate material with lower workfunction on the drain side of the gate sensibly enhances the collected charge and the bipolar gain of the device compared to the SMDG counterpart. The difference between the two devices is important at low LET, but it gradually weakens when the LET value increases. The explanation is that at high LET the electric field is collapsed in both devices and then potential variations in the channel have less impact on the parasitic bipolar amplification. The bipolar gain then becomes nearly the same for DMDG and SMDG.

Ion hit location sensitivity

Previous simulations results have been obtained for an ion hit in the channel center (corresponding to x=30 nm). Since particles can strike the channel at different locations, we consider in the following several ion hit locations along the x-axis between the source contact (x=0) and the drain contact (x=60 nm). Drain current transients obtained for three locations in DMDG are shown in Fig. 5. The drain current peak and transient width increase as the ion strike location moves from source to drain. The collected charge as a function of the strike location in DMDG and SMDG is plotted in Fig. 6 for two different LET values. The deposited charge is also reported for comparison. Q DEP is highest in the middle of the channel and decreases toward the source and drain sides of the silicon film, because a reduced part of the ion track is contained in the active region [14]. Q COLL has a bell-shaped profile with a maximum around the middle of the channel (where Q DEP is the highest) and two minima at the source and drain contacts (where Q DEP is the lowest). For all x locations Q COLL is lower in SMDG than in DMDG. At very low LET=0.1 MeV.cm 2 /mg, Q COLL is always higher than Q DEP , which clearly indicates a strong bipolar amplification (Fig. 7a). For ion strikes in the source and LET=10 MeV.cm 2 /mg Q COLL is lower than Q DEP . This indicates that the bipolar amplification (Fig. 7b) is very low and that there is a strong recombination of the deposited charge in the device [14]. The bipolar gain (Fig. 7) is always higher in DMDG than in SMDG, but has similar dependences on ion hit location for both devices. For low LET, the bipolar gain maximum is located at the channel center and for high LET the highest gain is obtained at the channel-drain junction.

Discussion: gate workfunction impact on singleevent transient effects in DMDG MOSFETs

We also investigated the impact of several technological parameters on the transient response of DMDG. Simulations have been performed considering DMDG devices including a metal gate M2 with various workfunctions. At low LET, the simulation results indicate that the current transient peak and width, the collected charge and the bipolar gain monotonically decrease when Φ M2 is increased. This decrease is strongly attenuated when Φ M2 becomes higher than 4.5 eV, as shown in Fig. 8 for the collected charge and bipolar gain. At high LET, the transient response become sensibly the same for all devices (DMDG with different Φ M2 and SMDG), because, as explained before, the high deposited charge collapse the electric field. Then the body-potential differences between the structures have a lesser influence on their transient response. For LET above about 5 MeV.cm 2 /mg the collected charge and the bipolar gain become sensibly the same for all devices. Additional simulation results for different L 1 and L 2 values and detailed discussion will be included in the full paper.

Figure 2 Fig. 3 .

 23 Figure 2 plots the surface potential profile in SMDG and DMDG for different Φ M2 values. This figure shows, as expected, that the surface potential has

Fig. 4 .

 4 Fig. 4. Collected charge and bipolar amplification as function of LET in DMDG and SMDG MOSFETs for an ion hit in the channel center.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Drain current transients in DMDG MOSFETs for several ion hit locations (LET=10 MeV.cm 2 /mg).

Fig. 7 .

 7 Fig. 7. Bipolar gain in DMDG and SMDG MOSFETs as a function of the ion hit location.

Fig. 8 .

 8 Fig. 8. Collected charge and bipolar gain in DMDG and SMDG MOSFETs for an ion hit at x=40 nm.