Implementazione parallela di algoritmi genetici per la ... · Fasi del lavoro 1.Sviluppo di una...

Universita degli Studi di Trieste

Implementazione parallela di algoritmi genetici per la stimadi HMM

Relatore

Enzo Mumolo

Candidato

Nicola Timeus

14 marzo 2014

Motivazioni

∎ Pattern recognition mediante Modelli Nascosti di Markov (HMM)

∎ Stima dei modelli ottenuta tramite minimizzazione del gradiente(algoritmo di Baum Welch)

∎ Risultato dipende dal punto di partenza (sistema nonlineare) →algoritmo non ottimo

∎ Per raggiungere l’ottimo i modelli sono stati stimati medianteottimizzazione genetica

2 di 21

Nicola Timeus - Implementazione parallela di algoritmi genetici per la stima di HMM

Fasi del lavoro

1. Sviluppo di una libreria C general-purpose per l’ottimizzazionegenetica

2. Utilizzo della libreria per sviluppare un algoritmo diaddestramento alternativo a Baum-Welch

3. Parallelizzazione dell’algorimo ottenuto mediante GPGPU

3 di 21


Strumenti utilizzati

∎ CPU: Intel(R) Core(TM) i7 CPU 950 @ 3.07GHz

∎ Ram: 24 GB

∎ Scheda video: NVidia GeForce GTX 580, architettura CUDA

∎ GPU Clock Speed: 1.57 GHz

4 di 21


Modello di Markov Nascosto

∎ Modella processi stocastici con cambiamenti sequenziali dellecaratteristiche casuali

∎ La sequenza degli stati non e direttamente osservabile ma enascosta

∎ Presenta distribuzioni di probabilita associate ai simboli in uscita

5 di 21


Modello di Markov Nascosto

Rappresentazione grafica

6 di 21


Applicazione degli HMM al riconoscimento di pattern

∎ Riconoscimento di pattern: classificazione di una sequenza di datidi input grezzi o osservazioni

∎ Data una o piu sequenze di osservazioni O e possibile addestrareun modello HMM λ che le rappresenta

∎ Fatta questa operazione per tutte le classi definite e possibileclassificare una sequenza di osservazioni incognita Oi

∎ Classe riconosciuta = argmaxλ Prob(Oi ∣λ)

7 di 21


Problemi principali relativi agli HMM

Problema: Dato un modello λ e una sequenza di osservazioni Ocalcolare Prob(O∣λ)

Algoritmo forward-backward

Problema: Dato un set di sequenze di osservazione calcolare ilmodello HMM λ che meglio le descrive

Algoritmo di Baum-Welch

8 di 21


Algoritmi genetici

∎ Algoritmi di ottimizzazione euristica ispirati alla selezione naturalee alla genetica

Il valore del fitness dell'individuo migliore

è soddisfacente?

L'individuo migliore vienerestituito

SI

NO

Inizializzazione della popolazione

Calcolo della funzione di fitness

Ordinamento della popolazione

Applicazione dell operatore di crossover

Applicazione dell operatore di mutazione9 di 21


Operatori genetici

Crossover

0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0

1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0

Mutazione

0 1 1 0 1 0 1 1

1 1 1 0 0 0 0 1

10 di 21


Applicazione all’addestramento di HMM

Alfabeto per la codifica Insieme delle distribuzioni discrete k-arie

Crossover e mutazione Appropriati per gestire tale alfabeto

Funzione di fitness ∑O Prob(O∣λ)

Probabilita iniziali Matrice di transizione Matrice di emissione

π1 π2 . . . πk T11 T12 . . . Tkk E11 E12 . . . Eknsyms

11 di 21


GPGPU computing

∎ Consente la scrittura di codice arbitrario che viene eseguito inparallelo su GPU

∎ Permette notevoli incrementi di prestazioni se la strutturadell’algoritmo lo consente

Caso ottimale: operazioni semplici con scarsa interdipendenza(assenza di carattere iterativo/ricorsivo)

12 di 21


Architettura tipica di una GPU

13 di 21


Organizzazione del lavoro su GPU

Work dim

2Work dim 1

Work dim

3

Work groups

14 di 21


Algoritmo forward-backward

∎ Consente di calcolare Prob(O∣λ) in modo trattabile

∎ Presenta una natura iterativa

∎ Complessita O(n ⋅ k2)

15 di 21


Parallelizzazione dell’algoritmo forward-backward

Osserva

zioni

Variabili forward

Modelli

Work groups16 di 21


Dati di test

∎ Il riconoscimento e stato testato su un vocabolario costituito dalle26 lettere pronunciate in inglese da 8 uomini e 8 donne

∎ Il vocabolario e intrisecamente difficile da riconoscere

17 di 21


Accuratezza

f1 f2 f3 f4 f5 f6 f7 f8 m1 m2 m3 m4 m5 m6 m7 m860

62

64

66

68

70

72

74

76

78

80

GA su GPU

BaumWelch

Parlatori

Perc

entu

ale

di ri

cono

scim

enti

corre

tti

Baum-Welch 70.2%GA 71.0%

18 di 21


Prestazioni

Speedup in funzione del numero di generazioni

100 200 300 400 5001

2

3

4

5

6

7

8

9

10

11

OpenCL

Multithreading + SSE3

Multithreading

Numero di generazioni

Spee

dup

rispe

tto a

lla v

ersi

one

sequ

enzi

ale

19 di 21


Prestazioni

Speedup in funzione del numero di stati

4 8 12 161

6

11

16

21

26

31

36

41

46

OpenCL

Multithreading + SSE3

Multithreading

Numero di stati

Spee

dup

rispe

tto a

lla v

ersi

one

sequ

enzi

ale

20 di 21


Conclusioni

∎ Il tasso di riconoscimento ottenuto addestrando i modelli conl’algoritmo genetico risulta superiore rispetto al caso conBaum-Welch

∎ Utilizzando la GPU e stato possibile ottenere un miglioramentoconsiderevole in termini di prestazioni

∎ Il tempo di calcolo ottenuto mediante GPU ha lo stesso ordine digrandezza di quello relativo all’algoritmo di Baum-Welch

∎ Tempo di addestramento medio su 26 lettere

Baum-Welch 4.7 sGA su GPU 7.2 s

21 di 21


Implementazione parallela di algoritmi genetici per la ... · Fasi del lavoro 1.Sviluppo di una...

Documents

Transcript of Implementazione parallela di algoritmi genetici per la ... · Fasi del lavoro 1.Sviluppo di una...