ALBANO PietroCASTIGLIONE ArcangeloZACCAGNINO Gianluca

Inferenza statisticaattraverso tecniche di

compressione datiApplicazioni ed Esempi

Corso di Compressione Dati in Sistemi MultimedialiProf. Bruno CARPENTIERI

Outline

• Concetti preliminari

• Similarità

• CompLearn Toollkit

• Campi di applicazione

• Semantic Web con NGD

Concetti preliminariNCD e Clustering gerarchico

• NCD (Normalized Compression Distance): misura di quanto due oggettisono simili• in pratica numero reale 0≤r≤1

• valori prossimi allo zero corrispondono ad oggetti molto simili

• utilizzato per la costruzione di una Matrice delle Distanze contenente ledistanze tra ciascuna coppia di oggetti

• Clustering gerarchico: raggruppa un insieme di oggetti sotto forma dialbero• tiene conto delle informazioni contenute all’interno della Matrice delle

Distanze

Clustering gerarchicoValutazione dei risultati

• qualità del clustering dipendente dalla qualità della rappresentazionedelle informazioni contenute nella Matrice delle Distanze• misurata dal costo S(T) (normalized tree benefit score) associato ad ogni

albero di clustering

• per alcuni tipi di dati la rappresentazione sotto forma di albero potrebbeessere distorta• all’aumentare degli oggetti l’albero tende ad aumentare la distorsione

• fenomeno osservabile dal valore S(T) (valori più piccoli in corrispondenza didistorsioni)

• analisi di dati di un certo tipo:• file musicali

• record di transazioni

• informazioni relative al genoma

• nei dati di interesse sono presenti relazioni nascoste utili da determinareper fini pratici

• obiettivo: determinare le similarità tra tali dati in modo tale da classificarlie raggrupparli

• la combinazione di NCD e Clustering Gerarchico ha portato a risultatiinteressanti nel campo della classificazione e del clustering

SimilaritàProblematica

• metodi convenzionali: richiedono conoscenza specifica e dettagliatadella tipologia dei dati in analisi e delle caratteristiche da ricercare:• file musicali: pitch, ritmo, armonia ottenute mediante trasformata di Fourier o

trasformazione dell’onda…

• dati del genoma: frequenza di lettere o blocchi

• …

• NCD: rappresenta una metrica di similarità che gode dei seguentivantaggi:• non richiede alcuna conoscenza specifica relativa ai dati in esame (non-

feature similarities)

• semplice da realizzare e basata su tecniche di compressione ben note(compression-based similarity)

SimilaritàMetodi convenzionali vs NCD

• insieme di strumenti software Open-Source e multi-purpose

• utilizzato per la validazione degli esperimenti effettuati e la visualizzazione deirisultati ottenuti

• applicazione di tecniche di compressione al processo di classificazione eclustering in differenti domini:• approccio utilizzato completamente compression-based

• nessuna conoscenza preliminare richiesta

• nessun parametro relativo al dominio da impostare

• classificazione automatica degli oggetti in esame utilizzando la matrice delledistanze prodotta mediante NCD

CompLearn Toolkit

Outline

• Concetti preliminari

• Similarità

• CompLearn Toollkit

• Campi di applicazione

• Semantic Web con NGD

Campi di applicazione

• potenziali applicazioni in qualsiasi campo del sapere umano• musica, letteratura, arte, scienze, ecc…

• risulta necessaria tuttavia• rappresentazione digitale degli oggetti in esame

• preprocessing delle informazioni prima di ciascun esperimento

• approccio utilizzato convenzionalmente:• estrazione di specifiche caratteristiche quali pitch, ritmo, armonia, … (ad

esempio utilizzando la trasformata di Fourier)

• classificazione e clustering delle caratteristiche estratte utilizzando softwaredi classificazione esistenti (basati su classificatori di Bayes, modelli diMarkov, …)

• richiesta conoscenza specifica e dettagliata del dominio e dellecaratteristiche da ricercare

Music Categorization Approccio Human Expert

• approccio molto più generale rispetto a quello convenzionale• non si cercano similarità rispetto a caratteristiche specifiche rilevanti

per la classificazione musicale

• utilizzo della compressione per la classificazione basata sullametrica NCD

• utilizzo per gli esperimenti di file MIDI (Musical Instrument DigitalInterface):• calcolo delle distanze tra coppie di brani musicali

• costruzione dell’albero contenente tali brani organizzati in modoconsistente rispetto alle distanze calcolate

Music Categorization Approccio basato su NCD

• utilizzo di file MIDI distinti appartenenti a generi musicali eterogenei (dalla musicaclassica a quella popolare)

• preprocessing di ciascun file MIDI:• estrazione degli eventi MIDI Note-On e Note-Off

• calcolo del volume medio (ottenuto dall’evento MIDI Note-Velocity) e della nota modale(pitch della nota che compare più spesso nella traccia musicale)

• utilizzo dei file ottenuti dalla fase di processing come input per il calcolo dellamatrice delle distanze (utilizzo di gzip o bzip2) e per la costruzione dell’alberogerarchico

Music Categorization Dettagli esperimento

• obiettivo: mostrare che il tool è in grado di distinguere tra 3 dei generi musicali più ampi• Classica• Jazz• Rock

• selezione di 12 pezzi ben rappresentativi per ciascun genere

Yardbird suiteCharlie Parker

Round midnightThelonious Monk

Night in TunisiaDizzy Gillespie

SummertimeGeorge Gershwin

So what

Solar

Seven steps to heaven

MilestonesMiles Davis

Impressions

Lazy bird

Giant steps

Blue traineJohn Coltrane

Musica Jazz

YyzRush

Message in a bottle

Every breath you takeThe Police

Voodoo Chile

Hey JoeJimi Hendrix

OneMetallica

Stairway to heavenLed Zeppelin

Money for nothingDire Straits

Layla

CocaineEric Clapton

Michelle

Eleanor RigbyThe Beatles

Musica Rock

Suite Bergamasque 4

Suite Bergamasque 3

Suite Bergamasque 2

Suite Bergamasque 1Debussy

WTPK2 Fuga 2

WTPK2 Fuga 1

WTPK2 Preludio 2

WTPK2 Preludio 1Bach

Preludio Op. 28: 24

Preludio Op. 28: 22

Preludio Op. 28: 15

Preludio Op. 28: 1Chopin

Musica Classica

Music Categorization Generi musicali

ChopPrel1

ChopPrel22

ChopPrel24

MilesSowhat

BachWTK2P1

GershSumm

ChopPrel15

ColtrLazybird

HendrixVoodoo

RushYyz

BachWTK2F2

PoliceMess

MetalOne

BeatlMich

LedZStairw

HendrixJoe

PoliceBreathClaptonLayla

ClaptonCoca

BeatlEleanor

DebusBerg2DebusBerg3

DebusBerg1

DebusBerg4

DireStMoney

ColtrGiantStp

BachWTK2F1

BachWTK2P2

MilesSolar

ColtrImpres

MilesMilesto

ColtrBlueT

Miles7steps

GilleTunisia

MonkRoundMParkYardbird

Musica Classica

Musica Jazz

Musica Rock

Music Categorization Musica Classica (Small Set)

DebusBerg2

DebusBerg3DebusBerg1

DebusBerg4

ChopPrel22

ChopPrel24

ChopPrel1

ChopPrel5

BachWTK2F2

BachWTK2F1

BachWTK2P2

BachWTK2P1

Debussy

Bach

Chopin

Music Categorization Musica Classica (Medium Set)

HaydnSon38

HaydnAndaVari

ChopinEtu1

ChopinEtu2

ChopinEtu3ChopinPrel15 ChopSon2m3 ChopNoct2

ChopNoct1

BachWTK2F2BachGoldAria

BachKdF1

BachInven1

BachGoldV1

BachKdF2 BachWTK2P1

BachGoldV2HaydnSon28

HaydnSon27

HaydnSon40m1

HaydnSon40m2

HaydnSon37DebusBerg1

DebusBerg4DebusBerg3DebusBerg2

ChopPrel24

DebusChCor1

BackWTK2P2

BackWTK2F1

ChopPrel22

ChopPrel1

Chopin

Bach

Debussy

Haydn

MozSon4

MozSon3

HaydnSon28

HaydnSon27BeetSon26

BuxtFug174

ChopNoct2

ChopSon2m3

BachKdF1

BachInven1

BackGoldAria

BachWTK2F2

MozSon1

BachWTK2F1

BeetRomance1 BachWTK2P2

BuxtPF144

BuxtPF143

ChopNoct1

BeetSon14m1

MozSon2

BuxtPF139

BachGoldV1

BachGoldV2

BeetSon8m1

BachKDF2

BuxtTF165

MozSon16R

BuxtPF163

BuxtCanz168

HaydnSon38

HaydnAndaVari

MozFant475

MozFantK397

BeetSon21m2

ChopEtu1

ChopEtu3

ChopEtu2

ChopPrel15

MozVarsDirais

BeetSon14m3

HaydnSon37

HaydnSon40m1

HaydnSon40m2

MozSon6

MozSon19

BachWTK2P1

BeetSon29

BuxtPassa161

BeetSon23

DebusChCor1

BeetFurElise

ChopPrel22

BeetSon14m2

ChopPrel24

DebusBerg1

DebusBerg3

DebusBerg2

DebusBerg4

ChopPrel1

Chopin

Bach

Debussy

Mozart

Haydn

Buxtehude

Beethoven

Music Categorization Problematiche e sviluppi futuri

• risultati di esecuzione differenti anche sullo stesso insieme di dati (dovutoall’utilizzo della casualità nella scelta delle mutazioni nel quartet method)• determinare la soglia di stabilità minima da raggiungere attraverso differenti esecuzioni

• peggioramento dei risultati all’aumentare del numero di pezzi musicali• problemi di scaling sconosciuti legati al quartet method

• ottenere un riscontro teorico ben fondato per scelte altrimenti arbitrarie quali:• scelta dell’algoritmo di compressione da utilizzare

• modalità di trasformazione dei file MIDI

• definizione della funzione di costo relativa al quartet method

Music Categorization Problematiche e sviluppi futuri (2)

• risultati poco soddisfacenti con file di piccole dimensioni (~100 bytes)• compressione significativa solo per file di dimensioni più grandi

• strumento valido per:• scoperta di plagi o influenze “oneste” tra pezzi musicali e compositori

• separazione di ere e stili musicali

• attribuzione della paternità di una composizione per la quale l’autore è sconosciuto • basandosi su un insieme di pezzi musicali noti per gli autori candidati

Outline

• Concetti preliminari

• Similarità

• CompLearn Toollkit

• Campi di applicazione

• Semantic Web con NGD

• compressione di sequenze di testo relative ad opere della letteratura Russa(costruzione matrice NCD mediante bzip2)

• utilizzo di tre o quattro opere per autore in lingua originale (Cirillico)

• effettuare il clustering delle opere per autore e valutare i risultati ottenuti.

Literature Categorization Clustering di autori russi

A house of Gentlefolk

On the Eve

Rudin

Father and Sons

I. S. Turgenev

Poor Folk

The Idiot

The Gambler

Crime and punishment

F. Dostoyevsky

How the Two Ivans Quarrelled

The Mysterious Portrait

Taras Bulba

Dead Souls

N. V. Gogol

War and Piece

Youth

The Cossacks

Anna Karenina

L. N. Tolstoy

The Heart of a Dog

The Fatefull Eggs

The Master and Margarita

M. Bulgakov

Clustering di autori russi Risultati

DostoyevskyCrime

DostoyevskyPoorfok

DostoyevskyGambi

DostoyevskyIdiot

TurgenevRudin

TurgenevGentlefolk

TurgenevEve

TurgenevOtcydeti

TolstoyAnnak

TolstoyWar1

TolstoyYouth

GogolPortrDvaiv

GogolDsols

GogolPortrDvaiv

GogolTaras

BulgakovMm

BulgakovEgg

BulgakovDghrt

Literature Categorization Considerazioni

• considerando la traduzione inglese degli stessi testi, risultano evidentierrori nel clustering

• clustering influenzato dal traduttore utilizzato

• traduttore sovrappone le proprie caratteristiche sui testi eliminandoparzialmente le caratteristiche dei testi in lingua originale

Clustering di autori russi Risultati testi tradotti

BulgakovMm

BulgakovEgg

BulgakovDghrt

TolstoyCosacs

DostoyevskyCrime

TurgenevOtcydeti

TurgenevGentlefolk

TurgenevEve

TurgenevRudin

TolstoyAnnak

TolstoyWar1

DostoyevskyIdiot

GogolDsols

TolstoyYouth

DostoyevskyGambi

DostoyevskyPoorfok

GogolPortrDvaiv

GogolTaras

Applicare la teoria dell’NGDal motore di indicizzazione di

Google

Semantic Web con NGD

Google SearchEngine Index

Google Simple Object Access Protocol

Query(str1…strn)

Index set

Semantic Web con NGD Architettura

CompLearn

• semantica assegnata mediante comparazione di stringhe (indici)• comparazione effettuata attraverso NGD (Normalized Google Distance)

• NGD: numero 0≤r≤1 che rappresenta di quanto differiscono semanticamentedue termini

• con r che tende a 0 la similarità (semantica) aumenta

Semantic Web con NGD Concetti

• Googling horse and rider• horse: 46.700.000 risultati• rider: 12.200.000 risultati• horse rider: 2.630.000 risultati

• totale pagine indicizzate da Google• 8.058.044.651

• NGD( horse, rider ) ≈ 0.443

Semantic Web con NGD Per capire meglio

chartreuse

purpleorangeyellow

greenblue

red

two

one

transparent

zero

five

fourfortytwo

eight seven

six

small three

white

black

Numeri

Colori

Altro

Semantic Web con NGD Colori e numeri

SteenPrince’s Day

SteenThe Merry Family

SteenWoman at her Toilet

RembrandtThe Stone Bridge

SteenTwo Men Playing Backgammon

RembrandtPortrait

of Maria Trip

RembrandtPortrait of

Johannes Wtenbogaert

RembrandtHendrickje clapend

BolVenus and Adonis

BolConsul Titus

Manlius Torquatus

BolMaria Rey

BolSwartenhont

RembrandtThe Prophetess Anna

SteenLeiden Baker

Arend Oostwaert SteenKeyzerswaert

Rembrandt

Steen

Bol

Semantic Web con NGD Pittori Olandesi del XVII secolo

ALBANO PietroCASTIGLIONE ArcangeloZACCAGNINO Gianluca

Inferenza statisticaattraverso tecniche di

compressione datiFINE

Corso di Compressione Dati in Sistemi MultimedialiProf. Bruno CARPENTIERI