Problem-solving Strategies in a Music Transcription System

PROBLEM-SOLVING STRATEGIES IN A MUSIC TRANSCRIPTION SYSTEM

Bernard Mont-Reynaud

CCRMA, Stanford Universtty

absurd (but physically accurate) transcrtpttons, as may be obtatned by setttng the tempo and the metrtcal grtd reaolutton to ttxed values, and roundtng durattons to the neareat grtd potnt. But one should keep in mtnd that, tor example, an eighth note (1/2 ot a beat) may be played shorter than a trtplet etghth (1/3 ot a beat) wtthout contustng human Usteners, provtded the approprtate mustcal context. How to provtde sutttctent context mechantsms to reach correct dectstons, orten 1n sptte ot the physical evtdence, wtthout carrytng context-drtvtng to excesa, may weil be the mostsensitive questton 1n the destgn ot robust perceptton systems.

ABSTRACT

Mustc transcrtptton 1s a stgntttcant problem 1n machtne perceptton. The system dtscussed in thts paper, MANA, takes as tnput etther the sound ot a recorded pertormance, or data captured ustng a muslcal keyboard.. It produces conventtonal mustcal notatton as output. It has successtully handled pteces rangtng trom 18th-century plano mustc to tmprovtsattons on conga drums, in the Atro­ Cuban style.

The paper descrlbes the key tdeas and techntques round tn the temporal analysts component or MANA, the goal ot whtch 1s to asstgn a rhythmtc value to each note played.

Perceptton seems to result trom the tnterplay ot sensory evtdence and pre-extsttng mental structures, data­ drtven agents pttted agatnst model-driven agents 1n the tormatten ot hypothe.ses that seem tolerable to our prejudices and not too dtstant from the data. To thts ttrst order vtew one must add a second order one, whtch allows the system to nottce patterns among parttally elaborated hypotheses, and to use these patterns to alter conftdence rat tngs, accordtng to "peer pressure" rules.

Concerntng the use ot multiple criteria tor hypothests evaluatton and pruntng, whtch necessary in the context ot perceptton systems, tt ls argued that the use ot partial orders over multi-dimensional spaces ot natural crtterta yteld more robust methods that approaches based on combtntng crtterta down to scalars.

I INTRODUCTION

An ongotng research project at CCRMA (Stantord Untverstty) is concerned with exploring an AI approach to the recognttton ot mustcal structures 1n sound and other torms or data. The errecttve tntegratton ot numertcal processtng and symboltc processtng towards the goal or machine perceptton is a central techntcal theme, while music tranacrtptton is the task goa1.

Automatte transcriptton trom sound ts clearly more difticult than transcriptton trom keyboard. atrokes. It requtres, prior to the musical analysts whtch 1s needed in both cases, an tntttal stage ot acousttc analysts. Further rettnements may be obtatned by teedtng tntormatton gathered trom the mustcal context back to acousttc Ievels ot the analysis system.

It ts perhaps less obvtous that transcrtptton trom keyboard strokes alone presents a stgntttcant challenge. The problem ts trivial 1t one etther torbtds expressive pertormance and rhythmic complextty, requtrtng strtct metronomts accuracy in ttmtng; or 1t one accepts mustcally In thta paper, the dtscusston w1ll be Umtted to the mustcal analysts component ot MANA, and further restrtcted to the temporal aspects ot the analysts. The reader 1s raterred to [FOS82a-b, SCH84] tor a discusston ot acousttc analyats, and to [CHA82, MON84] tor a more comprehenstve account ot the methods used in mustcal analysts. Sectton ß ot the paper provtdes an overvtew ot the aystem, and presenta aome ot the key tdeas and techniques used in temporal analysts. Sectton m discussea aome or the problem­ aolvtng atrategiea whose compounded ettect 1s a caretully meuured dose ot context-drtvtng. Sectton IV draws aome concluatons and outUnes the dtrectton ot ruture reaearch, in whtch learntng tssues w1ll play an tncreastng role.

II MUSICAL ANALYSIS

The pertormance goaltntttally set tor the aystem was to exhtbtt a fair degree ot mustcal wisdom while tranacrtbtng expresstvely played 18th-century music. The tnput was restrtcted to a atngle mustcal votce. A ttrst redeatgn or the temporal analysts permttted opentng up the range ot mustcal stylea wtthout havtng to tratn spectttc atylea tnto the program. Another redestgn, whtch 1s 1s progreaa, 1s atmed at dealtng with polyphonlc aound. However, the aystem as dtscu.ssed here only wtth one votce at a time.

Further progress towarda tncreased grasp ot the mustcal structure, tncluding more robust methods tor tempo tracktng and meter determtnatton, requtre moderately powertul learning techniques, or the "unsupervtsed" type. The tdea 1s to uncover the most stgnittcant mustcal patterns tn a ptece, and to use the temporal patterns ot pattern occurences as hinta to the tempo and meter. Near-mtsses also otrer tmportant possibllittes, notably ror error detectton. near-mtssed to inittate selt-doubt.

A Rational Approximation Generation

Note valuea, metrtcal intervala and metrical postttons are rattonal numbers, expreased in terms ot a reterence untt. Gtven (aay) a note duratton X and the duratton R ot the metrtcal reterence unit, both in seconds, one wishes to generate rational approximationa of X/R as candidate note valuea for the given note, in terms of the given unit. The choioe of rational approximationa must take into account at leaat two criteria: clo.seness to the data (or fit), and simplicity of the fraction. The latter must be understood in terms of how simple or natural the resulting musical notation would be. The techniques of multi-criteria tütering (section ßi-B) come into play at this point, to limit the number of answers retained.

The program relies on the same generator for a variety of different tasks, but it varies parameterssuch as the set of acceptable numerators and denominators, and the error thresholds. The most obvious use is in the generation ot hypotheses for individual note values. There are others, and they use different tunings.

Finally, the complexity measure for metric fractions i.s allowed to change over time. For example, fractions such as 1/3 and 2/3 may become simpler than 1/4 or 1/2 atter sufficient statistical evidence of ternary meter has been gathered. This is an applicationa of peer pres:rure (ct. lil­ A).

B Approach to the rhythmlo value problem

The goa1 is to express note values as rational fractiona of a whole note. It turna out that this goal must be approached in a round-about manner, which goes in 4 steps as followa: (a) choo.se a reference unit R; (b) express note valuea u fractions of a reference unit R; (c) analyze the pat terna of note values in order to determine values for metrical divisions like beat, bar and (at least) the whole note; and (d) convert from R-values to whole-note values.

Problem (b) is the rhythmic value problem. Problem (c) is the meter problem, which is not discussed here. From a formal point of view, it appears that the value of Rn step (a) is arbitrary. This is not so: the behavior of the rational approximator depends very much on the referenoe unit uaed. A first set of rules is uaed to determine R Statistical eluatering of note values plays a role there.

The next key idea is to localize the problem, to regiona where the tempo is supposedly held conatant. This factora out the global tempo ßuctuation, which can be repreaented by a piecewise linear correspondence between muaical time and physical time. The slope of each linear segment i.s a tempo value, and the list of successive segments is regarded as the tempo line ot the piece. A second set of rulea, based on simple rhythmic and molodie patterna is used to determine the structural anchor.s. These notes are singled out as likely candidatos to occupy strong positiona in the (as yet undetermined) metric grid. For inatance, these notes might oocur at downbeats, or at least at beat boundaries. The endpoints of the tempo Une segments, on the physical time axi.s, ·are placed at these structural anchor points.

A third set or rules determines the metrical duration ot each tempo Une segment, in terms of R. This completes the conatruction of the tempo line. Once the tempo is known within each segment, it is possible to use the rational approximation generator to associate with each no~., a set of candidate rational values, in terms of R Among tht~ combination of approximationa which add up to the dealred metric length it is possible to select one that represents the best compromise between musical simplicity and oloaeneas to the data, for this segment.

In terms of search paradigma, choosing the tempo line before aasigning individual note values is a special case of solving a problem in a much smaller ab.stract .space. Once an abltract aolution S is obtained, one ratums to solving the original problem under the conatraints imposed by S.

III PROBLEM-SOLVING STRATEGlEB

MANA oper atos primarily in a bottom- up fashion, but it does use top-down constraints. The important point is that very few a priori top-down constraints are used. In other words, the program tries to refrain from having too strong a notion of what music "must" be like. On the other hand, a posteriorl constraints are heavily relied upon. Such context- driving operatos in a top-down manner, but the cont'lxt is acquired during previous bottom-up hypothesis generation. The idea is to promote homogeneity, or self­ consistency. In other words, the program operatos under the assumption that a piece defines its own "style" and then w ants to see more of the same "style". This feodback mechanism, termed peer pressure, is further examined in section m-A.

Inatead of backtracking, the system relies on a multiple-value technique, whereby a set of alternatives is operated on parallel. Techniques of multl-criteria filtering (cf III-B) are used to to prune the sets of alternatives whenever evaluation criteria are added or moditied.

A. Peer pressure

The system uses several Ievels of abstraction in its description of the data. It combines data-driven and context-driven methods of hypothesis generation and evaluation. Data-driven methods use features obtained at one Ievel to generate hypotheses at the next Ievel. Context­ driven methods use information gathered at higher Ievels to re-evaluate and possibly re-generate lower-level hypotheses. A key problem is to arrange that feodback loops between the bottom-up and top-down modes either converge rapidly, either to a stable consensus, or to no effect at all. This problem is adressed by the peer pre.ssure strategy, a method that allows a collection of hypotheses (obtained using statistics, clustering or pattern discovery methods) to promote hypotheses with similar contextual featurea.

Using rather broad terms here, Iet us call "data" some collection of hypotheses at a given Ievel of description, and "partial model" some description of the the set of data. The partial modal might be a set ot patterns found in the data, or a atati.stioal aummary of some aspect or the data.

Peer pressure, which may be viewed as a noise reduotion technique, operatos in two steps. The first step extraota a partial modal from the data. The model must be "aafe" before proceoding: under poor conditions, peer prUiure may amplify noisel The second step modifies the data to oreate a better agreement with the partial model. Eaoh data point is re-examined in terms of this agreement. If the agreement is weak, the data point becomes a candidate for modifioation, that is, deletion, replacement by one or more other data points, or simple adjustment. Strang patterna always get stronger by the use of this technique, whioh decreuea the perceived disorder in the interpretation ot the data.

B U:ultl-orlterla filterlng

In an attempt to achieve robustnass over a wide range of examples and styles, MANA relies on a variety of independent methods for hypothesis generation, and also on a multiplicity of evaluation criteria. Rather than using backtracking, MANA usually carries a small number of hypotheses in parallel. Exces.sive pruning of a aet of hypotheses, most likely to occur during early stagea of analysis, may cause a system to overlook a good solution whose value 1s not yet obvious at that stage of the game. Too little pruning, on the other hand, not only slowa thinga down, but leavea noisy pointa which may atfect the operation of peer preaaure. Thus, it 1s important to maintain a balanced degree of indecision.

In a multiple-criteria situation, a popular approach 1s to uae a weighting scheme to produce a scalar from all the criteria. MANA conaiders this method to be one of last resort, as it all too often Ieads to erroneous decisiona. Trying to improve the approach by making the weighting scheme dependent on context leavea the problem unchanged for initial decisions, which must be made before sutficient context 1s eatablished. It also forces one to develop ways of changing the weighta as a function of context, a rather hazardous enterpriae.

It seems better to deal with the original multiplicity of criteria directly, especially during pruning stages. The intuition behind the scheme we use 1s quite simple: if hypothesis A is no worse than hypothesis 8 in any of the criteria, and better in at least one criterion, then (and only then) 8 should be pruned. This idea immediately generalizes to an arbitrary partial erderings in the space of criteria. We say that an hypothesis is dominated if it 1s Iarger than some other hypothesis, with reapect to the chosen partial ordering. Undominated hypotheses are those that correspond to minimal elementa in the space of criteria. They are the only onea retained past a pruning sta~e.

Since the retained hypotheses are minimal in the partial ordering, they trade one criterion for another: one hypothesis might be close to the observed data while the other 11 simpler but farther away, and a third is intermediate in both respects. The scheme is uniform, but leaves much ßexibility in the choice of the partial ordering. In our application, thill technique has been found extremely etrective.

IV CONCLUSIONS

Elements of a methodology for achieving robustneaa in perception task.s have been gathered, along with some ideas more specitic of the transcription domain. In terms of performance, the automatte transcription system described has also produced some rather intereating resulta. Naturally, there 1s much more work to be done, both to

improve robustneaa in single-voice examples, and to deal with polyphonte data.

Experiments underway suggest that the response to theae challengea will be based on (a) extending the use of adaptive feedback strategies into the acoustic Ievels of the ayatem, so that signal proceaaing and reasoning work hand­ in-hand, and (b) developing the techniques for pattern discovery and selection to the point where second-order patterns become a reliable source of Information.

In fact, in the proceaa of this reaearch, it has become more and more apparent that the musical domain provldes an ideal aetting for ln-depth studiea in machine perception and machine learning. Statistical pattern recognition and unsupervised inductive learning [MIC83] both have important rolea to play in a ßexible musical understanding system.

HEFERENCES

[CHA82] Chate, C., 8. Mont-Reynaud and L. Rush. Toward an Intelligent Editor of Digital Audio: Musical Construct Recognition, Computer Music Journal 6:1 (1982), 30-41.

[FOS82a] Foster, S., J . Rockmore and W. Schloss. Toward an Intelligent Editor of Digital Audio: Signal Prooessing Methoda, Computer Music Journal6:1 (1982), 4261.

[FOS82b] Fester, S. and A. Joseph Rockmore. Signal Proceaaing for the Analysis of Musical Sound, ICASSP Prooeedings, Paris. May 3-6, 1982.

[MIC83] Michalsky, R. , J . Carbonell, and T. Mitchell, eds. Macbine Learning. Tioga Publishing Co., Palo Alto, 1983.

[MON84] 8ernard Mont-Reynaud, et. al. Intelligent Systems tor tbe Analysis of Digitized Acoustic Signals, Final Report. Technical Report STAN-M-16, Department of Music. Stanford University, Stanford, California (1984)

[SCH84] Schloss, W. On the Automatie Transcription of Percussive Music, PhD theais, Department of Speech and Hearing, Stanford University, Stanford, Calitornia (in preparation)

· This work was supported by the National Science Foundation under Contraeta NSF MCS-8012476 and DCR8214360-