Olivier Lartillot
email: olivier.lartillot@ircam.fr

Perception-Based Musical Pattern Discovery

Keywords: musical pattern discovery, cognitive inferences, music perception, pattern similarity, pattern associations

A new general methodology for Musical Pattern Discovery is proposed, which tries to mimic the flow of cognitive and sub-cognitive inferences that are processed when hearing a piece of music. A brief survey shows the necessity to handle such perceptual heuristics and to specify perceptual constraints on discoverable structures. For instance, successive notes between patterns should verify a specific property of closeness. A musical pattern class is defined as a set of characteristics that are approximately shared by different pattern occurrences within the score. Moreover, pattern occurrence not only relies on internal sequence properties, but also on external context. Onto the score is build pattern occurrence chains which themselves interface with pattern class chains. Pattern classes may be interassociated, in order to formalize relations of inclusion or repetition. The implemented algorithm is able to discover pertinent patterns, even when occurrences are, as in everyday music, translated, slightly distorted, slowed or fastened.

Introduction

Musical Pattern Discovery (MPD) is an emerging discipline, which aims at offering automated analyses of musical scores [START_REF] Lartillot | Perception-Based Advanced Description of Abstract Musical Content[END_REF]. Lots of Musical Information Retrieval applications would highly benefit from the tools offered by MPD. Indeed, as MPD would automatically retrieve the content of score, new types of music browsing, listening, visualizing, etc., would be possible.

Nowadays, however, no computer system is able to complete in a pertinent way the demanding task of MPD. In this paper, we suggest a new approach that may offer an answer to fundamental problems arisen in this discipline, and that could therefore solve a certain number of difficulties.

We introduce a general methodology whose intuition stems from a mimicking of human perception. We will defend such a position through a critical overview of current approaches in MPD. This overview will lead us towards a characterization of musical pattern that takes into account the fundamental notions of repetition, sequence and similarity in the musical context of temporal perception. We then propose a complete computational model that attempts to follow such methodology, and that already offers promising results.

The remaining of the paper is structured as follows. A preliminary survey of MPD concepts and methods will enable a formalization of our approach. We then introduce the data architecture and the algorithmic principles of the proposed system. Finally, we illustrate the use of the system in various musical contexts.

Some Necessary Conditions For Musical Pattern Discovery

Pattern Characterization

The concept of musical pattern may be characterized following three main criteria: Implicit knowledge. Pattern may result from implicit knowledge that cannot be obtained directly from the score, such as: expected phrase length or metric [START_REF] Lerdahl | A Generative Theory of Tonal Music[END_REF]. The trouble is, pattern perception cannot firmly rely on such theoryoriented implicit knowledge. Indeed, musical motives may be structured in an ambiguous way, through a breaking of these rigid rules, playing with the listener's expectations and conveying musical delightedness. A mere fugue may easily show that patterns (here themes, for instance) may appear at very unexpected metric places, and may feature a long temporal extension.

Local boundaries.

Low-level structural properties of the musical surface may be obtained through local boundary detection [START_REF] Cambouropoulos | Towards a General Computational Theory of Musical Structure[END_REF]. For instance, grouping boundaries may be introduced between entities that contrast one with the other according to their pitch, duration, intensity parameters, etc. Such heuristics may enable an understanding of metric phenomenon, for instance. However, such local segmentation does not contribute to the understanding to the idea of musical pattern itself. Indeed, a musical pattern is implicitly built through contrastive aggregation.

Fig. 1. A pattern may feature contrastive steps.

In figure 1, the first leap of interval of fifth, although triggering a contrastive idea, is the important element that characterizes the beginning of the pattern itself. A pattern is therefore not a conservation of sameness, but on the contrary a travel along differences. In fact, similar patterns features similar differences.

In the same time, it has to be recognized that local boundaries may provoke a breaking of sequencing.

We have integrated such characteristic of music in our mechanism of stream perception inside polyphony (see paragraph 4.1).

Repetition. Finally, a musical pattern may be defined as a set of characteristic that is shared by several sets of notes throughout the score. These sets of notes are said to be similar in a certain sense. This may look as a particularly intricate definition of pattern, which could have been formalized more simply as: a set of notes that is approximately "repeated". But two difficulties should be taken into account: firstly, that the concept of pattern refers either to the characteristics, to a prototype of such characteristics, or to occurrences; secondly, that such concept of similarity has to be explicitly defined (see paragraph 2.3 and 2.4).

This "repetition"-oriented criterion of pattern seems to remain the most relevant one, since music motives are classically defined in this way [START_REF] Nattiez | Music and discourse: towards a semiology of music[END_REF]).

Set Paradigm Vs. String Paradigm

In previous definition, a pattern is a "repeated" set of notes. A pattern may in fact be either a general set of notes [START_REF] Wiggins | SIA(M)ESE: An Algorithm for Transposition Invariant, Polyphonic Content-Based Music Retrieval[END_REF] or a sequence, that is: a succession of notes, where successive notes in the sequence are successive notes in the score.

If pattern is not constrained to be a sequence, temporal distance between nearest notes within this set may be arbitrarily large. We previously claimed the necessity to enable such a general view of pattern, in order to catch slow melodies accompanied by fast arpeggios for instance (Lartillot 2002b). However, even if limitations are set on temporal distance between successive notes, such a loose formalization leads to computational ineffectiveness -since lots of absurd patterns may be found -and cognitive incoherencies [START_REF] Hofstadter | [END_REF]). It appears that musical listening capabilities, such as the one previously described, may be explained in a more efficient way through the idea of parallel sequences (see paragraph 4.1).

Musical Similarity

The idea of successiveness should not be considered in a rigid way, in order to enable deletions of notes or insertions of new ones in the pattern. Dynamic programming [START_REF] Rolland | Discovering Patterns in Musical Sequences[END_REF] is the most classical way to handle such operations. But music features other kinds of sequence transformation, such as passing notes or appoggiaturas, which should be also considered. Now patterns may be subject to other kinds of transformation. Simply transposed patterns may be detected by considering each pattern in its own transposition reference. For example, if patterns are described not with absolute pitch, but with relative pitch whose reference is the absolute pitch of the first note of the pattern, then such descriptions of transposed patterns are exactly identical.

In the same way, slower and faster patterns may be considered as identical one with the other if a relative temporal representation is considered. For this purpose, instead of considering the temporal interval between successive notes, the quotient between current temporal interval and first temporal interval is considered.

But real music features much more complex transformations. In particular, pitch and temporal distortions may appear locally inside patterns. To handle such plasticity, more relative viewpoints of the pattern may be considered, such as the contour representation in particular. However, such a crude representation is so loose that non-pertinent repetitions may also be detected.

In fact, when considering such local distortions, there exist no viewpoint (Conklin and Anagnostopoulou 2001) sufficiently loose for finding an exact repetition but in the same time sufficiently detailed for avoiding non-pertinent inferences. Therefore approximate repetition has to be tentatively inferred, to be induced (Lartillot 2002a) from rough phenomenon, even if risks have to be taken.

Incremental Inference of Similarity

Global analyses of the score, such as naïve statistics, not taking into consideration the incremental expression of music, fail to catch the essential temporal aspect. Classical pattern analyses, by explicitly considering prefixes and suffixes may offer better results. Dynamic programming successfully highlights the necessity to consider a progressive and chronological scanning of patterns.

Lots of musical phenomenon deeply relies on the fact that music is progressively perceived, and that the listener itself progressively infers new knowledge about what he is currently hearing. Therefore, music listening should be considered as a kind of progressive reasoning. That is why some configurations are not detected and therefore not pertinent, simply because they cannot be caught during progressive listening.

Hence, pattern cannot be defined solely along internal description, but also along external criteria, or context. It is senseless, therefore, to measure the similarity between sequences out of their context. Patterns of figure 2 may be considered as two occurrences of a same abstraction, because of the intrinsic similarity, only if this example was the actual score itself. When these patterns are included inside a real score, their similarity should be inferred only if they share a similar context. The incremental and logical thinking that builds human perception of music is ruled by fundamental principles, which are necessary for insuring a coherent process. For example, every time a sequence is considered as an occurrence of a pattern, every suffix could themselves be considered as occurrences of other pattern class, for simple mathematical reasons. But cognitively speaking, such inferences are not pertinent, since they do not correspond to inference human makes when listening to music. This is due to the fact that the first longest pattern was sufficient to explain the phenomenon, and that further inferences of suffixes would only infringe a clear analysis of the score. That is why suffix of pattern should not be explicitly represented [START_REF] Dannenberg | Listening to "Naima": An Automated Structural Analysis of Music from Recorded Audio[END_REF].

Selection

As many patterns may be found, pertinent patterns are considered as those that feature a highest defined score [START_REF] Cambouropoulos | Towards a General Computational Theory of Musical Structure[END_REF]. Such selecting mechanism is a classical and efficient way to extract important knowledge. It should be remarked, however, that this global selection, although enabling a quick characterization of a piece, infringes a thorough understanding of the complete score. We would like to retrieve also little detail at particular places, that may be of high relevance, and that may be taken into account by an active listening. The only necessary condition for a pattern to be considered as pertinent is that its score (here a degree of activation) has to exceed a certain minimal threshold. Therefore, to pattern selection we would prefer the concept of pattern detection.

As the result of such analysis is very complex, an interface should enable a browsing inside the analysis space or across the score. As such interface is not available now, our current implementation has to feature selecting operations.

Finally, since the process of pattern discovery proceeds itself through explicit characterization, there is no need to characterize a posteriori the patterns that have been discovered.

Data Representation

Pattern Class And Occurrence

The fact that several sequences are considered as similar in a certain sense means that they all belong to a same abstraction, which may be considered as a pattern class. These sequences are therefore occurrences of the pattern class. In this way, any new sequence sharing the same similarity will simply be considered as a new occurrence of this pattern class. The pattern class is not represented by a single prototype, but by all its occurrences that are effectively linked to it.

Pattern Class Chain

According to the incremental characteristic of music perception, patterns are progressively discovered, interval by interval, from initial interval to whole pattern. Pattern classes have to be represented following this cognitive constraint. In particular, all possible prefixes of a pattern may be considered as a pattern, uncompleted indeed, but still a pattern. Therefore, prefix of pattern classes are pattern classes. The set of all prefixes of a pattern class, ordered by growing order of pattern length, is a chain, called pattern class chain (PCC).

Progressively, for each new note of the pattern that is being discovered, a new pattern class is added as a continuation of the previous pattern class. In this way, if a prefix of a discovered pattern class appears later, it will simply be considered as a new occurrence of the intermediary pattern class associated to this pattern.

Pattern Occurrence Chain

For each pattern occurrence, an additional interface should associate the sequence of notes inside the score that constitutes the occurrence with the pattern class. Such interface may also be described as a chain -called pattern occurrence chain -where each successive state within the POC represents at the same time a note in the sequence and a state in the PCC.

Pattern Associations

The idea of segmentation may implicitly and dangerously suggest that score features only one level of pattern representation. On the contrary, patterns of different lengths may coexist and there may be inclusion or intersection relationships between them. In figure 5, the main 8-note pattern is itself structured into an exact repetition of 3-note patterns. Each occurrence of the 8-note pattern, though constantly varied, carefully verifies the inner repetition of two sub-patterns. And each 8-note pattern is itself repeated twice.

Thus pattern cannot simply be characterized through an enumeration of similar intervals. The inner description as explained below should be made explicit too, and should be inferred by the machine.

We propose to represent such relationship between pattern and sub-pattern as follows. If occurrences of a pattern class feature a particular subpattern, a new POC, representing this sub-pattern, is linked to the PCC of the pattern itself. With such linking inside PCCs, a new association network is build between pattern classes. This high-level organization may help the recognition of basic pattern occurrences. In this way, expectations are generated by the system during the analysis: when a new occurrence of the pattern is discovered, sub-patterns are also expected [START_REF] Meyer | Emotion and Meaning in Music[END_REF]). Fig. 6. On the first bar of Bach's Prelude may be build a POC (below the score) that is associated to the 8-note PCC (white circles), and two POC for the 3-note PCC (over the score). These 3-note patterns, since they are repeated on different 8-note patterns, are represented directly on the 8-note PCC with two additional POCs (at the bottom).

Pattern Repetition

If a pattern is repeated successively several times, occurrences are themselves elementary objects that forms a meta-pattern. In particular, local intervals may be considered between such successive occurrences. Such a successive repetition of occurrences of a same pattern class may simply be represented by extending each pattern with the first note of the following pattern, and by associating to this added note the POC of this same pattern class. Fig. 6. When a pattern is repeated more than twice, the last note of the pattern is linked to the first note through an additional POC on the PCC. Such a mechanism is not as arbitrary as it may appear. When perceiving such successive repetitions of occurrences of a same 8-note pattern, we actually perceive 9-note pattern, where last note is in the same time the first note of a new pattern. Thanks to this mechanism, every time we perceive a whole occurrence of the 9-note pattern, we then expect a new occurrence again.

Algorithms

Decomposing Polyphony Into Streams

In paragraph 2.2, we explained that a pattern should be considered as a sequence. This means that for each note of the pattern, its preceding note inside the pattern should be one of its previous notes, where previous is defined as following.

Let n be current note. Let m1, m2, … be the set of simultaneous notes that precedes n but in the same time are temporally closest to n. Let mi be the note that has the closest pitch compared to n. Then mi is a previous note of n.

Now if there exist past notes p1, p2, … whose pitch is particularly closer (defined below) to the pitch of n than any other note already known to be close to n, then the pi that is the temporally closest note is also a previous note. This last operation is repeated as long as necessary. Fig. 7. Current note (in black) and past note (in white). Some past notes are defined as previous note (with an array). Now the pitch of pi is particularly closer to the pitch of n than any other close notes when the quotient between the pitch distance between pi and n and the pitch distance between any close note and n is below a certain threshold.

In this way, a current note may accept several possible previous notes. Such interval between any previous note and current note, which is the building element of pattern construction, will be called local interval. Thanks to this decomposing of polyphony into streams, overlapping patterns may be discovered. See figure 10 for an example of this method.

Pattern Class Discovery

In this section, we will show how our system is able to detect new pattern classes, that is, new abstractions. As told previously, a pattern is defined as an approximately (or exactly) repeated sequence. So pattern will be discovered only if a similarity relationship is inferred between a current sequence and a past one. Past sequence has to be recalled because of its similarity with current sequence. The trouble is: current sequence does not already exist as a sequence if repetition itself is not already detected.

In our previous work (Lartillot 2002b), we alleviated the task by imposing a constraint, which can be expressed as follows: for a new pattern repetition to be detected, the repetition of each single interval of the patterns has to be explicitly and progressively discovered. In particular, the similarity between the first interval of each patterns has to be inferred before inferring the similarity of the remaining of the pattern. The trouble is, such a constraint can hardly be satisfied. Nevertheless, we will show first how we implemented our previous approach. A generalization of this algorithm will then be proposed, that can overcome previous limitation.

First Approach. First, every local interval has to be memorized in an associative memory that is able to retrieve any interval similar to a query. For this purpose, a hash-table associates for each interval parameter the set of its occurrences within the score. Now if the hash-table shows a similarity between current local interval i1 and an old local interval i1', a new pattern class is inferred (unless already discovered) associated to this single interval. Then if there exists any similarity between an interval i2 that follows previous local interval i1, and an interval i2' that follows previous old local interval i1', then a new pattern class extends previous pattern class. And so on. Fig. 8. In first approach, similarity of single intervals (solid lines) has to be inferred. This similarity can be extended to following intervals (dotted lines).

If i1 and i1' have to be identical for being considered as similar, then pattern featuring a slight distortion on its first interval will not be detected.

Therefore, a looser comparison between i1 and i1' should be tolerated. But in this case, lots of nonpertinent little patterns will be inferred too. Moreover, with such approach it is not possible to detect patterns with different speed, since i1 and i1' should have similar interonset value.

Second Approach. We propose to improve our first approach as follows. If current interval i1 is particularly similar to an old local interval i1', then a pattern class is inferred as previously. If, on the contrary, this similarity is not very high, previous local intervals i0 that precede i1 are considered, and compared to previous local intervals i0' that precede i1'. If the sequence i0-i1 is considered as similar to the sequence i0'-i1', then a pattern class is inferred, that consist of this succession of two intervals. In this way, a pattern may be detected even if its first interval was not a sufficient clue. Fig. 9. In second approach, similarity may be inferred between sequences of intervals. Now such approach may be immediately generalized to n intervals instead of 2.

Pattern Class Extension.

Once a new pattern class has been discovered, its extension is an easier task. Indeed, the new local interval that extends the discovered new pattern just have to be compared to possible continuations of the discovered old pattern, instead of comparing it to all possible intervals through the hash-table. Indeed, thanks to the previous pattern class initiation, two or more similar contexts have been discovered in the score. Pattern extension just consists of a deeper analysis of found contexts.

Pattern Occurrence Discovery

The discovery of a new occurrence of an already discovered pattern class follows the two steps of Pattern Class Discovery -namely: pattern initiation and pattern extension. But this time, no pattern class have to be inferred.

Results

This model has been implemented as a library of Open Music, a musical representation software developed at Ircam. This new library called OMkanthus is able to proceed to analysis of MIDI files. In version 0.1, these results are displayed as a list of texts that is not easy to understand. That is why this library is provided with some basic tools for selecting and displaying longest patterns, most frequent patterns, or most pertinent patterns, where pertinence is a product of length and frequency. Here are some results.

When asking the pattern classes achieving the highest degree of pertinence in the beginning of a piano reduction of the Allegro of Beethoven's Fifth Symphony, we obtain all occurrences of the 4-note pattern (line #4 of figure 11). The prefixes of this pattern are also represented in this figure in lines #1 to #3. This additional information, stemming from intermediate inference during the progressive pattern perception and therefore not pertinent as analytical results, should not therefore be made explicit. This bad behavior is not due to our analytical system, however, but to the roughness of the simple tools we have designed for result selection for display.

When asking the longest pattern, we obtain this time 12-note pattern that consists of repetition of three occurrences of the 4-note pattern. Pattern found line #1 of figure 12 is very pertinent, whereas pattern found line #2 should not have been inferred. Here is one bad behavior of current version 0.1 of our algorithm.

When asking the pattern classes achieving the highest degree of pertinence in the beginning of the melody of the Rondo of Mozart's Sonata in A major K331 "Alla Turca", we obtain the 5-note pattern, line #2 of figure 13, and the long theme itself, line #1. More precisely, the long theme stops just when chords appears, simply because version 0.1 of OMkanthus cannot discover chords. Here also, very short patterns (like simple interval or chord) are displayed, showing the imperfections of our selection method.

When asking the pattern classes achieving the highest degree of pertinence in the beginning of Bach's Prelude in C, BWV 846, we obtain the 8-note pattern (line #4 of figure 14), the 16-note pattern (which consists in fact of the repetition of two 8-note patterns, line #6), and 2-note patterns that are repeated inside the 8-note pattern itself. When considering the different occurrences of these 2-note patterns, we notice that lots of non-pertinent occurrences are found in the end of the example. This comes from a heuristic stating that the more a pattern is repeated, the more approximate patterns may be tolerated. Such heuristic shows here its limitation.

Conclusion and Future Works

In this paper, we have proposed a new approach that attempt to answer to some fundamental problems arisen by current researches in MPD, through the elaboration of a new general computational model founded on explicit principles and aiming at mimicking human capacities for music perception and understanding.

The proposed model and implementation are still in an early phase, showing numerous limitations. With such approach, many questions arise but few are answered yet. Nevertheless, one interest of this general methodology is to propose a framework in order to make explicit some assumptions shared by MPD community.

It would be impossible to list all the difficulties that have to be solved now. Maybe the hardest part is to make these difficulties explicit. Some further improvements include chord pattern discovery, comparison of sub-patterns associated to a pattern (inferring the similarity between sub-pattern themselves, comparing the relative pitch and temporal distance between sub-patterns).

Then an interface has to be designed, enabling a browsing inside the score and the discovered structures. In a long term, such approach may try to go beyond pattern and catch higher-level concepts. Would a system be able to retrieve music theory?

Fig. 2 .

 2 Fig. 2. The similarity of patterns cannot be measured outside of their actual context.

Fig. 3 .

 3 Fig. 3. A PCC, an occurrence of the whole PCC (first bar), and an occurrence of one prefix (second bar).

  Fig. 4. The POC (black circles) interfaces notes in the score with the corresponding PCC (white circles).

Fig. 5 .

 5 Fig. 5. Beginning of Bach's Prelude in C.In figure5, the main 8-note pattern is itself structured into an exact repetition of 3-note patterns. Each occurrence of the 8-note pattern, though constantly varied, carefully verifies the inner repetition of two sub-patterns. And each 8-note pattern is itself repeated twice.Thus pattern cannot simply be characterized through an enumeration of similar intervals. The inner description as explained below should be made explicit too, and should be inferred by the machine.We propose to represent such relationship between pattern and sub-pattern as follows. If occurrences of a pattern class feature a particular subpattern, a new POC, representing this sub-pattern, is linked to the PCC of the pattern itself. With such linking inside PCCs, a new association network is build between pattern classes. This high-level organization may help the recognition of basic pattern occurrences. In this way, expectations are generated by the system during the analysis: when a new occurrence of the pattern is discovered, sub-patterns are also expected[START_REF] Meyer | Emotion and Meaning in Music[END_REF]).

Fig. 10 .

 10 Fig. 10. Local relationships between notes in the beginning of the Fugue in C Major, BWV 846.

Fig. 11 .

 11 Fig. 11. Most pertinent patterns of the beginning of piano reduction of the Allegro of Beethoven's Fifth Symphony.

Fig. 12 .

 12 Fig. 12. Longest patterns of the beginning of piano reduction of the Allegro of Beethoven's Fifth Symphony.

Fig. 13 .

 13 Fig. 13. Most pertinent patterns of the beginning of the melody of the Rondo of Mozart's Sonata in A major K331 "Alla Turca".

Fig. 14 .

 14 Fig. 14. Most pertinent patterns of the beginning of Prelude in C Major, BWV 846.

Acknowledgments

My doctorate project is supervised by Emmanuel Saint-James (LIP6, Paris 6) and Gérard Assayag (Musical Representation Team, Ircam). Some ideas arise from stimulating discussion with my colleague Benoit Meudic.


Benoit Meudic
email: meudic@ircam.fr

Automatic pattern extraction from polyphonic MIDI files. (Extraction automatique de patterns à partir de séquences polyphoniques MIDI.)

Keywords:

In the context of musical analysis, we propose an algorithm that automatically induces patterns from polyphonies. We define patterns as "perceptible repetitions in a musical piece". We claim that a link can be established between the patterns that we extract and the musical structure of the piece. Our aim is that the patterns we extract are perceptively relevant although several perceptive criteria are not taken into account in our model: what we propose is an attempt to explore the limits of a system that do not considers, in a first step, the musical notions of expectation or temporal context (considering temporal context means that we take into account past events for the analysis of current events), but that integrates several other perceptive notions such as polyphonic context. This brings us to discuss several specific issues related to the extraction of patterns in a polyphonic context.

Our model proceeds as follows:

. The algorithm computes the similarity between all the pairs of sequences with same number of beats. It relies on features such as rhythm, contour and pitch intervals. Last, a bottom-up approach is proposed for extracting patterns from the similarity matrix. It builds new patterns by concatenation of the consecutive cells that are on the same diagonal in the similarity matrix. The algorithm was tested on several pieces of music, and interesting results were found. At the same time, new questions were raised on the notion of musical structure.

1

INTRODUCTION Automatic music analysis is an increasingly active research area. Among the main tackled subjects, the search for musical patterns is at a central place. Indeed, most of the musical pieces are structured in various components ("phrases", "motives", "themes", "generative cells"…) that can naturally be associated with the notion of pattern. Considering the only notion of "pattern" simplifies (or postpones) the issue of making the distinction between the different natures of the components (theme, motive etc…) of a musical piece. However, answering to the question "what is a pattern?" is still rather difficult. Often, the notion of pattern can be linked with the notion of repetition: patterns emerge from repetition. But a pattern could also be defined by its salient boundaries, and then patterns would emerge from discontinuities in the music. Last, patterns can also be characterized as independent and coherent entities. Providing a definition is all the more difficult as we place ourselves in a musical context. Most of the time, patterns are linked with perceptive notions, which raises one question: can we consider as "patterns" the structural (one would say mathematical) regularities of a musical sequence, even if theses regularities are not perceived? Inversely, do perceived repetitions only correspond to exact repetitions? We think that the notion of similarity between two sequences plays an important role in the perception of patterns and it should be part of a pattern extraction system.

In this article, we have chosen to focus on perceptible musical structures. Moreover, we assume that musical structures can be induced from the extraction of repeated sequences (which we call patterns) and thus we address the issue of extracting "perceptible repetitions" from a musical piece.

BACKGROUND

The literature is quite poor in algorithms that automatically extract patterns (perceptible repetitions) from polyphonic music. An interesting method, starting from the audio, is proposed in [START_REF] Peteers | Toward Automatic Music Audio Summary Generation from Signal Analysis[END_REF]. It considers the signal as a succession of "states" (at various scales) corresponding to the structure (at various scales) of a piece of music. A similarity matrix is computed from feature vectors. The similarity matrix reveals large and fast variations in the signal that are analysed as boundaries of potential patterns. The patterns are then grouped according to their similarity. The method is relevant for pieces that contain salient transitions (timbre changes, important energy variations etc…), but could reveal less relevant for the detection of phrases in piano music. Another method [START_REF] Lartillot | Perception-Based Advanced Description of Abstract Musical Content[END_REF] starts from MIDI files and induces patterns by analysing the musical sequence in a chronological order. All the possible combinations of successive events contained in a temporal window of limited size are potential candidates for being a pattern.

The notions of temporal context and expectation are modelized. However, if very promising, this method cannot analyse long sequences with too many events because it would require a too high computation cost. Moreover, polyphonic context (see 4.1 for definition) is not considered. Last, [START_REF] Cambouropoulos | Towards a General Computational Theory of Musical Structure[END_REF] proposes to segment a MIDI file and then to categorize the segments in clusters. The segmentation algorithm uses a boundary detection function that computes the similarity between all the possible patterns of the sequence. Then, the segments are clustered according to a threshold that depends on the different distances between the segments. Once the clusters are computed, the distances between segments are re-computed in order to optimize the current clustering, and the clustering function is called again until the clusters are found optimal. This method is interesting because it analyses whole sequences of polyphonic MIDI music, and the notion of context is originally used in one of the two steps of the analysing (the clustering). However, the segmentation step appears hazardous, and would require a high computational cost.

AIMS

The algorithm we present in this article is a new model for extracting patterns from polyphonic MIDI sequences. Our aim is that the patterns are some components of the musical structure. In order to make the system the more general (and primitive) as possible, we do not consider any knowledge based on tonality neither we consider particular styles. Several perceptive notions are taken into account in the algorithm. However, in a first step, we have chosen to challenge the limits of a system that does not modelize temporal context or expectation. Indeed, the integration in the system of all the cognitive mechanisms that play a role in our perception of music is far too complex. Thus, we have to draw the limits of the model. The consideration of temporal context and expectation should be possible in a second step, but we first prefer to explore the limited system, and we will rely on the results to show that our method offers promising applications. Besides, we will not try to extract all but a set of significant patterns from polyphonic music. If our aim is that the extracted patterns are the most relevant of all the sequence, we consider as more important the relevance of the pattern itself.

INTRODUCTION TO THE PATTERN EXTRACTION MODEL

General considerations on patterns

We have defined patterns as "perceptible repetitions in a musical sequence". This notion has to be refined before we describe in details the model.

An issue arises when refining the term 'repetition' of the definition. How to define the similarity between two sequences? An attempt to answer to this question is proposed in 5.2. Another issue stems from the polyphonic context: is a pattern a single melodic line inside a polyphony, or is it itself a polyphonic component of a polyphony? For instance, let's consider the following extract of the 9nth Beethoven's sonata (Figure 1). The sequence formed by the first four events can be called a pattern as it is repeated several times. This sequence is polyphonic (one note followed by three chords). Should we consider that the sequence of chords is formed by three different monophonic patterns that are superposed, or is it one polyphonic pattern? Would it be relevant to dissociate the chords in as many components as there are notes inside, or should we consider them as entities? This also asks the question of the independence of a melodic line from its polyphonic context. Can we always isolate one or several monophonic lines, or do the superposition of several notes form a unique entity that cannot be decomposed? In several musical examples, there would be no reason to extract a single monodic line (see also Figure2). We also claim that considering a single melodic voice without its polyphonic context is often nonsense, as the polyphonic context often plays an important role in the perception of the structure of the piece. For instance, if we consider the beginning of the Sonata AM d664 op121, 1rst Part from Schubert (Figure3), one can extract the melody from the voice at the top. However, the segmentation of the melody in different patterns (that correspond in musical analysis to the usual "antecedent-following" repeated one time with variation) is not trivial without information on the polyphonic context. Similarly, if we consider the beginning of the Intermezzo op117 no1 from Brahms (Figure 4), we could extract the melody by hand with difficulties (it is not at the top of the voices, and it is repeated but with big variations), but it would not characterize the excerpt. Indeed, one could imagine the same simple melody in very different polyphonic contexts, divided in several different voices. However, and this raises one of the main issues, the only melodic line should also be taken into account, for instance when it follows the model 'melody + accompaniment'. Indeed, in this case the melodic line could be separated from the accompaniment and considered as a monophonic pattern that would be repeated in the following music sequence, but with different accompaniment, or with melodic variations. This is mainly a perceptive issue that is difficult to solve with only one rule. Sometimes, the solution is trivial. For instance, melodic lines are often difficult to follow in Bach's Fugues, but fortunately, they appear at the beginning of the fugue one after the other, which let us time to memorize them. In this case, the pattern first appears in a monophonic context (the Fugue's subject) and then is repeated and varied in a polyphonic context. The issue is not to extract a pattern (monophonic or polyphonic) from polyphony but to recognize a known (or memorized) monophonic pattern inside polyphony. However, in some pieces such as canons, only the beginning of the pattern appears in a monophonic context. The repetition covers a part of the pattern. Thus, in a polyphonic context, music cannot always be segmented in individual successive segments (that is often proposed in several musical theories) and possible coverings between the structural components must be taken into account.

Whatever the situation would be, we believe that the polyphonic context plays an important role. Even if a single melodic line could be extracted from the polyphony, the polyphony should be associated to the melody in most of the cases. One could say that when remembering a polyphonic excerpt, we often sing a single melodic line, but this is due to our physical impossibility to sing a polyphonic sequence, and often when singing the melodic line, we hear (but don't sing) the polyphonic context (at least the harmony) that was associated with it. It means that we have memorized it, and that we take it into account in our comparisons with other sequences. In this article, we propose to define a pattern as a polyphonic component of a polyphonic sequence.

4.2

General architecture of the model Our model analyses a MIDI file that contains the onset (in milliseconds), the pitch (in midicents) and the duration features. The dynamic and the channel features are not considered. The model is composed of two main algorithms:

• The first algorithm computes several similarity matrices from a quantized MIDI file (Section5). • The second algorithm extracts patterns from the similarity matrices (Section 6).

In the first algorithm, we first quantize and segment the MIDI sequence with an algorithm proposed in [START_REF] Meudic | A causal algorithm for beat tracking[END_REF]. The boundaries of the segments correspond to the downbeats of the music. The initial sequence of MIDI events is thus considered as a sequence of beatsegments. Each beat-segment (b.s) is itself a sequence of MIDI events (see Figure 5). Then, given a length L (in number of beats), each sequence of b.s of length L is compared with all the other sequences of same length. For each comparison, three similarity values are computed (corresponding to three different features: pitch intervals, pitch contour and rhythm) and associated with the events of the two sequences that have been found similar (we call them "templates"). All the similarity measures are then stored in similarity matrices. The measures of similarity we use are described in [START_REF] Meudic | Musical similarity in a polyphonic context : a model outside time[END_REF]. They will be presented in 5.2.

In the second algorithm (section 6), patterns are extracted from the similarity matrices. First, the matrix cells (a matrix cell is a couple of two sequences of b.s of same length) are filtered and clustered according to their similarity value. Then, patterns are extracted in a bottom-up approach that starts from the different clusters of cells and then groups them in new (and often smaller) clusters with longer cells.

5

The similarity matrices

5.1

The computation of a matrix A similarity matrix (Figure 6) stores the similarity values between the pairs of b.s (beat.segment) sequences of same length L (in number of beats). The units of the vertical and horizontal axis are expressed in number of beat-segments. We consider the matrix as symmetric (see discussion in 4. The choice of the length L can appear somewhat arbitrary. The issue is to find the "right level" between the maximum length of patterns that cannot be divided in several parts and the minimum length of patterns that can be divided. Indeed, we think that some patterns must be considered as whole entities (see subsection 5.2.1) and not as the concatenation of smaller patterns. Two such patterns (sequences of beatsegments) can be similar while their components (the beat-segments), if considered individually, are different. We think that the maximal length of such patterns could be linked to the limits of our short-term memory: when listening to a musical sequence, we compare what we are hearing with what we have already listened. If what we are hearing is a variation of something already listened, we will match the two sequences. We match the sequences because they share common aspects. The question is: what is the minimal number of common aspects, and the maximal distance between the aspects, that is required to initiate a match between the sequences. In other words, what is the maximal size of a pattern (for us, the size is in number of beat-segments) that must be considered for matching it with another pattern? In our tests, we have decided to define a "blurred" length of pattern L: we compute the similarity between pairs of sequences of length L, L-1, L-2 and L-3, and we choose the best (the higher) similarity value (a decreasing coefficient is applied to the similarity value when the length of the sequence decreases, in order to support longer sequences).

5.2

The similarity measures In this part, we define several similarity measures between two b.s sequences of given length. We compute three different similarity values by considering three different sets of features: pitches (chords, pitch intervals etc…), pitch contours (contour at the top and at the bottom of the polyphony) and rhythm. The similarity values are computed in respect with some cognitive aspects (see sub-section 5.2.1). More details can be found in [START_REF] Meudic | Musical similarity in a polyphonic context : a model outside time[END_REF]. Each time a similarity value is computed between two sequences seq1 and seq2, it is associated with two "templates", that is to say the events of seq1 similar to seq2 (template1) and the events of seq2 similar to seq1 (template2). These templates will be used to refine the kind of similarity relation that exists between the two sequences (see sub-section 6.1).

Cognitive aspects of the similarity

measures First, a musical sequence of b.s is considered as a whole entity (it may contain an abstract cognitive structure), and not solely as the concatenation of smaller entities. Indeed, we think that several relations between non-adjacent events emerge from the whole entity. Theses relations play a role in the cognitive processes for recognizing the similarity between two sequences. To integrate this aspect, the similarity value between two sequences will not be computed from the addition of the similarity values between the smaller components: S(x, x') + S(y, y') ≠ S(xy, x'y')

S(x, x') designs the similarity value between sequences x and x', and xy designs the concatenation of sequence x and y. Another cognitive aspect is that our similarity measure is not symmetric in a polyphonic context:

S(x, x') ≠ S(x', x) (2)
If x is approximately included in x', x will be very similar to x'. But x' will not automatically be very similar to x because some events in x' may not be included in x. Last, according to [START_REF] Tversky | Features of similarity[END_REF], the similarity measure is not transitive, that is to say the triangular inequality is not true: S(x, y) + S(y, z) ≤ or ≥ S(x,z)

For instance, z can be a variation of y that is a variation of x. But z can be very far from x and thus not judged as a variation of x.

Similarity measure for pitches

We consider here the chords and the pitch intervals features. A similarity value is computed from two b.s sequences seq1 and seq2 of same length. The only events falling on the downbeats are considered. This may be arguable, but two reasons have conducted this choice:

• Considering all the polyphonic events would require too much running time. • The downbeats are often perceived as salient temporal position. Two sequences whose pitches coincide on the downbeat but differ elsewhere are often recognised as very similar (this has been confirmed in our experiments). Usually, a downbeat event (dwb.event) is a chord, but it can also be a note or a rest. All the intervals (horizontal and vertical) between all the pairs of dwb.event of one sequence are compared with all the intervals between the corresponding pairs of dwb.event of the other sequence (see Figure 7). The similarity values between pitches or intervals are:

• 1 for equal pitches or equal intervals • 0.5 for transposed vertical intervals • 0 otherwise

Similarity measure for contours

Our model compares the upper and lower contours of two b.s sequences seq1 and seq2 of same length.

As above, the only events falling on a downbeat (dwb.events) are considered. An up (down) contour is the sequence of the intervals between the upper (lower) pitches of the consecutive dwb.events. Each contour of each sequence is compared with the two contours of the other sequence. Contours are very similar (see Figure 8) if the intervals from one sequence are similar to the corresponding intervals from the other sequence (two intervals are similar if their difference is less than 5 half tones).

Overall similarity measure

Each of the three above measures (pitches, contour and rhythm) computes a similarity value between each pair of sequences of length L. The results can be represented in three different similarity-matrices that can be analysed separately. Sometimes, it appears that rhythm, pitches and contour play a different role in the similarity measure, and sometimes the similarity matrices for the different measures are very similar (see Figure 10 and Figure 12). The three measures can also be linearly combined into a global similarity measure (see Figure 9 and 11 for similarity between sequences and Figure 10 and 12 for similarity matrices). In this case, different weights can be applied to the different measures. An algorithm could be used to determine the best weightings by comparing the output of the similarity measures to a set of expected similarity-matrix.

In our experiments, we have chosen to give a higher weight to the rhythmic and the pitch based measures as they are more "selective" than the contour measure: the contour is expected to be common to more sequences than the pitch or the rhythmic successions of events. Due to the non-symmetrical relation (see equation 2), the similarity value between two non-ordered sequences seq1 and seq2 is composed of two different values: S(seq1, seq2) and S(seq2, seq1). In our model, we have chosen not to consider the two different values and thus we only consider the greater value. Doing that, our similarity matrix becomes symmetric and we represent only half of it.

6

Pattern extraction from the similarity matrix Several different types of information can be extracted from the matrices: general evolution for rhythm, pitch intervals or pitch contours, local repetitions of cells, areas of structural changes, etc… All of theses informations could be linked with the notion of pattern. However, in this part, we will only focus on the extraction of "the most important" patterns. Defining such patterns is quite difficult, as there are no objective criteria to characterize them. One would agree to say that the "most important" patterns are the ones that are perceived as the "most salient" in the musical sequence: thus the attribute "most important" is related to perceptive criteria. We think that the musical temporal context would play an important role in the definition of those criteria but once again, we will try not to consider it. Two other criteria are often found in the literature: the length of the pattern, and the number of its repetitions. However, it is quite difficult to combine the two criteria: the "most important" patterns often appear as a compromise between the two. For instance, the same accompaniment can be found all along a musical piece. This pattern is very often repeated and thus very important in regards with the second criterion. However, it rarely appears to us as the "most important" pattern. Inversely, musical pieces that are exactly repeated two times can be seen as two very long patterns but they are not the most relevant for us because the repetition is trivial. We will now propose a method for extracting patterns that could be "the most important ones". First, we propose to filter and cluster the cells of the matrix. Then, we propose to concatenate the cells in long patterns.

6.1

The filtering/clustering of the cells of the similarity matrices As we are looking for repetitions, we focus on the patterns that are very similar. For that, we choose a threshold that selects the only cells with the higher similarity values (see Figure 13). Then, we cluster the cells: each horizontal line of the similarity matrix represents all the similarity values between a reference sequence s(ref) and all the sequences of the line s(i). The high similarity values reveal high similarity with the reference sequence, but they do not reveal the kind of similarity, which has to be evaluated. For that, we compare the templates of the sequences. The template of seq1 (respectively seq2) contains the events of seq1 (resp seq2) similar to seq2 (resp seq1) (see Figure 11). Sequences that have very similar templates are considered as sequences that have same kind of similarity.

6.2

The extraction of patterns We define a bottom-up approach for pattern extraction that starts from the clustered cells and builds new patterns by concatenation of the consecutive cells of a same diagonal line. The algorithm proceeds along the matrix from the lowest horizontal line to the upper one. For instance, in Figure 14, the lowest horizontal line contains 8 cells. Only 6 of theses cells are clustered together. If we consider the second horizontal line, 6 cells can be concatenated to the 6 clustered cells of the first line. Thus, we have extracted 6 patterns of length "2 cells". As there are no cells in the third line, we stop the process. In a second step, we associate to each pattern the corresponding horizontal lines of the matrix (see 6.1). Theses lines contain clustered cells that could be concatenated and that could form new patterns (see Figure 14). Theses patterns could then be added to the six other ones, depending on their kind of similarity with them. In Figure 14, we highlight the 6 extracted patterns and a pattern that has been added in a second step (the last on the right of the figure). We have tested several different musical pieces, and patterns that are part of the musical structure were often extracted. All of the musical examples that have been presented along the paper have been analysed, and the extracted patterns could always be associated with the musical structure of the piece. For other pieces, some patterns could be found that do not begin or end at the right temporal position in the sequence.

Together with this issue, the consideration of all the notes of the polyphonic context was sometimes a constraint for recognizing the repetition of the only melodic line (for instance in canons pieces). The relations between the two (polyphony and the melodic line) is one of the main issue of pattern extraction.

CONCLUSION

We have presented a general system for pattern extraction from polyphonic musical sequences. The notion of perceptible pattern has been discussed in the context of polyphonic music. A global similarity measure that takes into account rhythm, pitches and contour in a polyphonic context has been proposed. A method for extracting patterns from similarity matrices has been described and we have provided several musical examples for illustration. The method we propose could be used in several different musical applications (extraction of some components of musical structure, motive discovery, characterization of different musical pieces from their rhythmical or pitch components). The similarity measure could also be adapted for applications such as "query by constraints": instead of humming a pattern, one could specify it with constraints on pitches or rhythm. The algorithm could then extract several patterns from different musical pieces with same rhythmical or pitch profile. In future work, we plan to integrate temporal context in the model, in such a way that both polyphonic and temporal context are taken into account in the computation of the similarity matrices. We think that our model considers interesting polyphonic aspects of music that are rarely taken into account, but several other polyphonic issues remain to be solved, particularly the relation between polyphony and the melodic line. However, we believe that solutions should emerge from such experimentations that come and go between perceptive considerations and modelization.

Figure 1 .

 1 Figure 1. Beginning of the Sonata for piano No9 EM from Beethoven. The first note and the three chords form a pattern. Transforming the three chords into three independent voices would not be perceptively relevant.

Figure 2 .

 2 Figure 2. A pattern extracted from the Sacral dance of the Rite of the spring from Stravinsky. A monodic voice could hardly be isolated from the polyphonic pattern.

Figure 3 .

 3 Figure 3. Beginning of the Sonata AM d664 op121, 1rst Part from Schubert. The four patterns correspond to the structure antecedent1-following1-antecedent2-following2. This structure could not be extracted from the consideration of the only melodic line.

Figure 4 .

 4 Figure 4. Beginning of the Intermezzo op117 no1 EM from Brahms. The sequence can be divided in four similar patterns (1-6, 7-12, 13-18 and 19-24) Polyphonic context is part of the structure of the sequence. The only melody line with another polyphonic context would not be stated as similar to this one.

Figure 5 .

 5 Figure 5. A sequence of beat-segments (b.s) extracted from the "Variations Goldberg" from Bach. The vertical lines delimit the beat segments. Horizontal lines are the durations of each event.

  4.5). Each cell refers to a pair of b.s sequences. The vertical and horizontal positions of each cell are the two beginning positions (in number of beats) of the two corresponding b.s sequences.Each similarity measure provides a real value between 0 and 1 that states how similar are the compared sequences (1 is for identical). In our model of similarity, sequences of b.s are of same length (length is expressed in number of b.s), so that each position of b.s in a given sequence can be matched with the same position of b.s in the other sequence.

Figure 6 .

 6 Figure 6. Four different similarity matrices from first 30 seconds of (from left to right and top to bottom): Sonata AM d664 op121 2 nd Part from Schubert, 1rst Gymnopedie from Satie, 1rst and 3 rd part of the Sacral dance of the Rite of the Spring from Stravinsky. White areas correspond to dissimilar cells. The unit for both vertical and horizontal axis is expressed in number of beatsegments (one cell per beat-segment).

Figure 7 .

 7 Figure 7. Excerpt from Sonat8Am-mvt2 from Mozart. A reference pattern (the above one) is compared to another pattern. Durations are not represented. All vertical and horizontal intervals between dwb.events C1 and C2 of Pair1-seq1 and dwb.events C3 and C4 of Pair1-seq2 are compared.

Figure 8 .

 8 Figure 8. Two similar patterns in Pierrot Lunaire from Schoenberg. The events that determined the similarity between the patterns (for pitches, contours and rhythm) are represented in black. Lines (1) and (2) show similar contours.

Figure 9 .

 9 Figure 9. Three patterns similar to the above pattern in Sonata AM d664 op121, 1rst Part from Schubert. The similar patterns are sorted according to their decreasing global similarity value S. The square symbols only determined the similarity for rhythm. The oval symbols determined similarity for both pitches and contour.

Figure 10 .

 10 Figure 10. Four similarity matrices from Sonata for piano No9 EM from Beethoven (from left to right and top to bottom): overall similarity measure, similarity for rhythm, similarity for contour and similarity for pitches. The contribution of the different measures to the overall similarity measure is very different (see figure 12 for comparison).

Figure 11 .

 11 Figure 11. Detail of one cell of the similarity matrix (Figure 10). Above, the two compared sequences of the cell. Below, the similar events of each sequence (the templates). Numbers 1, 2 and 10 correspond to similar pitches, contour and rhythmical events. As rhythmical similarity do not considers pitches, it is represented by the events at the bottom of the sequence with static pitch C.

Figure 12 .

 12 Figure 12. Four similarity matrices from Sonata DM d664 op121 2 nd Part from Schubert (from left to right and top to bottom): overall similarity measure, similarity for rhythm, similarity for contour and similarity for pitches. The contributions of the different measures to the overall similarity measure are very similar (see Figure 10 for comparison).

Figure 13 .

 13 Figure 13. A filtered similarity matrix from Sonata DM d664 op121 2 nd Part from Schubert (the initial matrix is in Figure 12). The most similar patterns appear (diagonal lines).

Figure 14 .

 14 Figure 14. (from top to bottom) The filtered similarity matrix from Sonata DM d664 op121 2 nd Part from Schubert, the extracted patterns (each horizontal segment is an instance of the same pattern) and the corresponding musical sequence (the graduation of the matrix and the musical sequence is in "number of beatsegments").

ACKNOWLEDGEMENTS

Part of this work was conducted in the context of the European project CUIDADO. I want to thank Olivier Lartillot for the interesting discussions that we have had on this subject.