Melodische Ähnlichkeit

Klaus FrielerRMA Hamburg WS 05/06

Aufbau des Vortrags

1. Motivation/Hypothesen2. Ähnlichkeitsmaße3. Experimente4. Modellierung5. Anwendungen6. Zusammenfassung

1. Motivation Melodische Ähnlichkeit ist ein Kernkonzept in

Musik und Musikwissenschaft, z.B.: Musiktheorie, Musikanalyse Musikpsychologie, z.B. Musikgedächtnisforschung Datenbanksuche U.v.m.

Quantifzierung von Ähnlichkeit: Ähnlichkeitsmaße Sehr große Anzahl von Ähnlichkeitsmaßen in der

Literatur Frage: Gibt es „objektive“ Ähnlichkeit? Kann man

Ähnlichkeitsurteile algorithmisch modellieren?

1. Motivation (Fort.)

Ziel: Bestimmung adäquater Ähnlichkeitsmaße

Methode: Mathematische Systematisierung, algorithmische Implementierung und musikpsychologische Validierung

Resultat: Software Simile (a.k.a. „Antiplagiator“)

1. Hypothesen Musikexperten bewerten melodische

Ähnlichkeit sehr präzise und konsistent. Bewertungen können als ‚korrekt‘ definiert werden und als Referenz für algorithmische Maße dienen.

Musikexperten benutzen verschiedene musikalische Dimensionen für ihre Bewertungen (z.B. Intervalle, Kontur, Rhythmus).Konstruktion von ‚optimierten‘ Maßen als Kombination verschiedener Einzelmaße.

2. ÄhnlichkeitsmaßeDefinition

Sei M = { (ti, pi), ti<ti+1} der Raum abstrakter Melodien von (Einsatzpunkt, Tonhöhe)-Paaren.

Ein Ähnlichkeitsmaß ist eine Abbildung s: MxM->[0,1]

mit den folgenden Eigenschaften: Symmetrie s(m, n) = s(m, n) Selbstidentität: s(m, m) = 1 Invarianz unter Transposition, Zeit-

verschiebung und -streckung (Tempowechsel)

2. Ähnlichkeitsmaße Überblick

Daten

Basistransformationen

Haupttransformationen

Numerischer Algorithmus

Ähnlichkeitswert

2. Ähnlichkeitsmaße Basistransformationen

Projektionen: Tonhöhen– und Rhythmus-projektionen

Differenzierung: Tonhöhe Intervalle Einsatzpunkte Dauern (IOIs) Dauern Dauernverhältnisse

Quantisierung

2. Ähnlichkeitsmaße Haupttransformationen

Rhythmische Gewichtung Rangbildung Konturisierung: Interpolation von

Tonhöhenwerten zwischen Extrema. (Steinbecks und eigener Algorithmus)

Fouriertransformation Fuzzifizierung/Kategorisierung (Intervalle,

Dauern) Gaussifizierung (Einsatzzeiten) Clusterung, z.B. Zuweisung harmonischer

Vektoren zu einzelnen Abschnitten (Takten)

2. Ähnlichkeitsmaße Haupttransformationen - Beispiele

Original

Kontur (Steinbeck)

Kontur (M&F)

Rhythmisch gewichtet Intervalle: +4 –2 +1 +1 +1 –3 +2 +3 Intervallkategorien: +T –S +S +S +S –T +S +T Intervallrichtung: U D U U U D U U Ränge: 6. 3. 5. 4. 3. 2. 5. 3. 1. Implizite Tonalität: D - Moll

2. ÄhnlichkeitsmaßeNumerische Algorithmen

Vektormaße: Melodien und Rhythmen als Elemente eines geeigneten reellen Vektorraums (z.B. Pearson-Bravais-Korrelation, Skalarprodukt)

Symbolische Maße: Melodien und Rhythmen als Zeichenketten(z.B. Editierdistanz, N-Gramme)

2. Ähnlichkeitsmaße Editierdistanz - Definition

Editierdistanz zwischen zwei Zeichenketten (Strings) sind die minimale Kosten für Operationen, die man braucht, um eine in die andere zu transformiern.

Mögliche Operationen sind: Einfügen, Löschen, Ersetzen

Jede Operation kann verschiedene Kosten haben. Einfachster Fall: Jede Operation kostet 1.

Maximale Editierdistanz: Länge des längeren Strings (für die konstante Kostenfunktion)

2. Ähnlichkeitsmaße Editierdistanz - Beispiel

„Anthropology“ (Charlie Parker)

„Ornithology“ (Charlie Parker)

2. Ähnlichkeitsmaße Editierdistanz - Beispiel

Ausrichtung von „Anthropology“ und „Ornithology“

2 Einfügungen (Löschungen) und 4 Ersetzungen werden gebraucht = insgesamt 6 Operationen.

Länge der längeren Melodie: 11 Noten. Editierdistanz (rawEd): 1-6/11 = 5/11 = 0,4545...

2. Ähnlichkeitsmaße N-gramme - Definition

N-gramme sind (Teil-)Strings der Länge N. Benutzte Zeichenalphabete: Intervalle,

Intervallrichtungen, Dauernklassen etc. Maße werden gebildet durch den Vergleich von N-

gramm-Verteilungen auf drei verschiedene Weisen: Häufigkeitsmaß: Summe der Häufigkeiten gemeinsamer

N-gramme (sum common) Anzahlmaß: Anzahl gemeinsamer N-gramme (count

distinct, coordinate matching) Ukkonenmaß: Differenz der Häufigkeiten aller N-gramme

2. Ähnlichkeitsmaße N-gramme – Beispiel

Keine gemeinsamen Intervall-N-Gramme! Ähnlichkeit = 0 Intervallrichtungen (Parsonskode) von „Anthropology“:

(U D U U U D U U ) Intervallrichtungen von „Ornithology“:

(U U U U U D U U D D) 3-gramme Total: (UDU, 2:1), (DUU, 2:1), (UUD,1:2), (UUU,

1:3), (UDD, 0:1) Gemeinsame 3-gramme: (D U U), (U U D), (U U U) Summe Häufigkeiten: (2+1) + (1+2) +(1+3) = 11 nGrSumCo = 11/(9+11-2*(3-1)) =11/16 = 0.6875

nGrCoord = 3 / 4 = 0.75nGrUkkon = 1 - 6/(9+11-2*(3-1)) = 1 –6/16 = 0.625

2. Ähnlichkeitsmaße Vollständige Liste

VPN_MEANRAWEDRAWEDWRAWPCRAWPCSTRAWPCWRAWPCWSTRAWCCRAWCCWCONSEDCONSPCCONSPCSTCONSCCCONEDCONPCCONPCSTCONCC

Mw. der Vpn.-urteileTonhöhen EditierdistanzTonh. Editierdistanz, gewichtetTonh. Pearson-Korrelation Tonh. P.-Korr., 0-1Tonh. P.-Korr., gew.Tonh. P.-Korr., gew., 0-1Tonh. KorrelationTonh. Korrelation, gew.Kontur (Steinbeck), Editierdist.Kontur (Steinbeck), P.-Korr.Kontur (Stein.), P.-Korr., 0-1 Kontur (Steinbeck), Korr.Kontur (M&F), EditierdistanzKontur (M&F), P.-KorrelationKontur (M&F), P.-Korr., 0-1Kontur (M&F), Korrelation

FOURRFOURRSTFOURRWFOURRWSTFOURRIDIFFEDDIFFDIFFEXPDIFFFUZDIFFFUZC

Fourier (Ränge) Fourier (Ränge), gew., 0-1 Fourier (Ränge), gew.,Fourier (Ränge), gew., 0-1 Fourier (Ränge, Intervalle)Intervalle (Editierdistanz) Intervalle (Mittl. Differenz) Intervalle (Mittl. Diff., exp.)Intervalle (Fuzzy), Ed.-dist. Intervals (Fuzzy, Kontur)

2. Ähnlichkeitsmaße Vollständige Liste

NGRSUMCONGRUKKONNGRCOORDNGRSUMCRNGRUKKORNGRCOORRNGRSUMCFNGRUKKOFNGRCOORFNGRSUMFRNGRUKKFRNGRCOOFR

N-gramme Häufigkeit (HM)N-gramme Ukkonnen (UM)N-gramme Anzahl (AM)N-gramme Intervallricht., HM N-gramme Intervallricht., UMN-gramme Intervallricht., AMN-gramme Intervallkat., HMN-gramme Intervallkat., UM N-gramme Intervallkat., AMN-gramme Dauerkat., HM N-gramme Dauerkat., UMN-gramme Dauerkat., AM

RHYTGAUSRHYTFUZZESFMAXESFMODESFMODKESFSIGNHARMCORRHARMCORKHARMCOREHARMCORCJOINT52

Rhythmus (Gaussif. Korr)Dauernkat., EditierdistanzSelfridge-Field (Max.) Selfridge-Field (Modus I) Selfridge-Field (Modus II) Selfridge-F. (Vorzeichen) Harmonische Korrelation IHarmonische Korrelation IIHarm. Korr. (Editierdist.) Harm. Korr. (Kreis) Akzente, (Editierdist. 2)

3. ExperimenteParadigma

3 Experimente: Variation im experimentellen Material (Melodien), Vpn., Bewertungsskalen, Dauer

Vorgehensweise: Einschätzung der Ähnlichkeiten von Paaren kurzer Melodien auf Bewertungsskala

Kontext I: Variantenkontext Kontext II: Gemischter Kontext Test–Retest Design mit Kontrollitems Material: Popmusikmelodien und Varianten mit

Manipulationen auf verschiedenen musikalischen Dimensionen zu verschiedenen Graden (eingebaute Fehler)

3. ExperimenteResultate

Insgesamt 108 MuWi-Studenten; 40 mit stabilen und reliablen Urteilen blieben in der AuswertungResultat: Hypothesen bestätigt Sehr hohe Intersubjektkorrelation (Cronbach‘s alpha = 0.962; 0.978)

„Wahre“ melodische Ähnlichkeit Starker Einfluss von Zahl und Typ der Fehler

4. ModellierungVorgehen

1. „Indicator of fit“: Euklidische Distanzen zum Mw. der menschlichen Urteile

2. Auswahl der besten Maße von 5 Dimensionen (Tonhöhe/Intervalle, Kontur, Rhythmus, harmonischer gehalt, kurze Motive)

3. Lineare Regression mit den besten Maßen ‚Optimierte‘ Maße als gewichtete Kombination von Einzelmaßen

4. ModellierungEuklidische Distanz zu den Vpn.-Urteilen

Experiment 1VPN_MEAN 0 DIFFEXP 7,94 NGRCOORR 9,92CONED 5,29 CONPC 8 CONSPC 9,99RAWEDW 5,63 CONCC 8,8 FOURRI 10,01RAWED 5,8 DIFFFUZ 8,89 FOURRST 10,11NGRCOORD 5,94 RAWPCST 9,18 NGRUKKOR 10,13NGRUKKON 6,09 ESFMAX 9,26 DIFF 10,17NGRSUMCO 6,17 ESFMOD 9,26 CONSCC 10,18HARMCORE 6,18 ESFSIGN 9,26 NGRSUMCR 10,38DIFFED 6,3 RAWPC 9,27 RHYTFUZZ 10,43JOINT52 6,55 RAWCCW 9,35 ESFMODK 10,64NGRUKKOF 6,68 RAWPCWST 9,48 RHYTGAUS 10,7NGRCOORF 6,72 RAWPCW 9,62 HARMCORC 11,05NGRSUMCF 7,21 FOURRW 9,68 NGRUKKFR 11,05CONSED 7,3 FOURRWST 9,72 NGRCOOFR 11,12HARMCORK 7,59 FOURR 9,78 NGRSUMFR 11,18DIFFFUZC 7,74 CONSPCST 9,84 HARMCORR 12,8CONPCST 7,81 RAWCC 9,85

4. ModellierungOptimierte Maße

Verschiedene optimierte Maße für verschiedene Beurteilungskontexte

Optimiertes Maß (opti1) für Variantenkontext (Kontext I):s = -0.151 + 0.559*rawEdw + 0.457*nGrCoord euklidische Distanz zum Vpn.-Urteilen: 3.789 (28.5% besser als bestes Einzelmaß)

4. ModellierungOptimierte Maße

0

2

4

6

8

10

12

SUBJ _MEAN OPTI1 CONED RAWEDW NGRCOORD HARMCORE RHYTFUZZ

5. AnwendungenVolkslieduntersuchung

Analyse von 585 Volkslieder aus Luxemburg und 435 aus Lothringen (ESAC Datenbank) mit dem opti3-Maß.

Verteilung von 254.910 Ähnlichkeitswerten: ‚Gutartig‘, aber Test auf Normalverteilung nicht signifikant.

OPTI3

OPTI3

Hä

ufig

ke

it

40000

30000

20000

10000

0

Std.abw. = ,07

Mittel = ,154

N = 254910,00

5. AnwendungenDubletten und Parodien

Untersuchung von 19 Lieder (Luxemburg), die als Varianten gekennzeichnet waren 4 Lieder hatten denselben Text, aber alternative

Melodien (Ähnlichkeiten<0.3) Ein Lied hatte kein Original (Fehler des Sammlers?) Von den 14 übrigen Lieder hatten 8 eine Ähnlichkeit

>0.8, 2 zwischen 0.7 und 0.8 und 3 zwischen 0.6 und 0.7 zu ihrem Original.

Untersuchung von 49 Paaren mit Ähnlichkeitswerten >0.6 Dubletten: 37 Paare Parodien: 10 Paare ‚Psalme‘: 2 Paare

5. Anwendungen Ein Beispiel

T0262 –‘Ist denn Liebe ein Verbechen?‘

T0385 -‘Ehestandslehren‘

5. Anwendungen Ein Beispiel

Struktur Zwei 4-taktige Phrasen Nur 2 verschiedene rhythmische Muster Die 1. Phrasen unterscheiden sich stark in der Kontur,

die 2. Phrasen sind eher ähnlich. Ähnlichkeitswerte:

opti3 0.462

nGrUkkon 0.21

rhytFuzz 0.84

harmCorE 0.62

diffEd 0.3

6. Zusammenfassung1. Sehr hohe Korrelation zwischen den

Ähnlichkeitsurteilen der Experten.2. Optimierung als lineare Kombination von

Einzelmaßen ist möglich signifikant bessere Resultate.

3. Maße und ihre Gewichte hängen vom Aufgabenkontext ab.

4. Anwendungen für opt. Ähnlichkeitsmaße:• Automatische Strukturierung von großen

Melodiesammlungen (z.B. Volkslieddatenbanken)• Melodiesuche in Datenbanken (z.B. Qbh)• Plagiatserkennung• Etc.

Melodische Ähnlichkeit

Klaus FrielerRMA Hamburg WS 05/06

Similarity measures Edit distance - Example

ED (ANTHROPOLOGY, ORNITHOLOGY)1. Suffix OLOGY is same, no costs. Consider

ANTHROP and ORNITH2. Add ROP at end of ORNITH: ORNITHROP, costs 33. Delete R and I: ONTHROP, costs 24. Substitute O with A: Ready, costs 15. Total costs: 66. Normalization: Divide by length of longer

strings: len(ANTHROPOLOGY) =127. Result: ED = 0.5

Similarity measures N-grams - Example

Sum-Common-measure (4-grams)

SC(s=ANTHROPOLOGY, t=ORNITHOLOGY) Only two common 4-grams : OLOG und LOGY, once

each. Sum-Common(4-grams) = 1 +1 +1 +1 = 4 Normalization: len(s)+len(t)-2*(4-1)=12+11-6 =17 SC = 4/17~0.235

Similarity measures Accent similarity measures

Idea: Accented notes are more important for similarity judgements

Determine accent structures of 2 melodies and compare them

‚True‘ accents combine accents from different dimensions (pitch, rhythm, harmony etc.)

Construction of joint accent measures:1. Segment melodies in phrases2. Give accents to melodies according to 25 rules from the

literature (Thomassen, 1982; Povel & Essens, 1985; Boltz & Jones, 1986)

3. Compare output of rules to human similarity data and combine best rules to joint accent measures

4. Choose best comparision technique for accent structures

Accent similarity List of accent rules

JUMPAFT3JUMAFT4JUMPAFT5JUMPBEA3JUMPBEA4JUMPBEA5JUMLOCSHORTPRPEXTREMPEXTRSTPEXTRMFPEXTRALONGPRLONG2PRENDLOIOIBEATS13BEAT1

After jump of 3 semitonesAfter jump of 4 semitonesAfter jump of 5 semitonesBefore and after jump of 3 semitones Before and after jump of 4 semitonesBefore and after jump of 5 semitonesAft. local jump (2 s.t. larger than pr. int)On 2nd note of 2-note-phraseContour turning pointCon. turning expt. change notes (Steinb.) Con. turning expt. change notes (M&F)After contour turning pointLonger previous note2x longer previous noteNote ending long IOI (≥2x mod. of dur.)On beats 1 and 3 of 4/4 meter On beat 1 of 4/4 meter

TRIADTRIADPHENPHRASBEGPHRASEND

1,3,5 of impl. tonality (Krumhansl)1,3,5 of impl. ton. on phrase endsNote beginning phraseNote ending phrase

Accent similarity List of combined accent measures

Joint accent measure Combined rules

JOINT41 JUMPAFT4 LONG2PR BEAT13 TRIAD

JOINT42 PEXTRMF LONG2PR BEAT13 TRIAD

JOINT43 JUMPAFT4 ENDLOIOI BEAT13 TRIAD

JOINT44 PEXTRMF ENDLOIOI BEAT13 TRIAD

JOINT45 JUMPBEA3 LONG2PR BEAT13 TRIAD

JOINT46 JUMPBEA3 ENDLOIOI BEAT13 TRIAD

JOINT51 JUMPAFT4 PEXTRMF LONG2PR BEAT13 TRIAD

JOINT52 JUMPAFT4 PEXTRMF LONG2PR PHRASEND TRIAD

JOINT53 JUMPAFT4 PEXTRMF ENDLOIOI BEAT13 TRIAD

JOINT54 JUMPAFT4 PEXTRMF ENDLOIOI PHRASEND TRIAD

JOINT55 JUMPBEA3 PEXTRMF LONG2PR BEAT13 TRIAD

JOINT56 JUMPBEA3 PEXTRMF LONG2PR PHRASEND TRIAD

JOINT57 JUMPBEA3 PEXTRMF ENDLOIOI BEAT13 TRIAD

JOINT58 JUMPBEA3 PEXTRMF ENDLOIOI PHRASEND TRIAD

JOINT61 JUMPAFT4 PEXTRMF LONG2PR BEAT13 PHRASEND TRIAD

JOINT62 JUMPAFT4 PEXTRMF ENDLOIOI BEAT13 PHRASEND TRIAD

JOINT63 JUMPBEA3 PEXTRMF LONG2PR BEAT13 PHRASEND TRIAD

JOINT64 JUMPBEA3 PEXTRMF ENDLOIOI BEAT13 PHRASEND TRIAD