Back | Home | Next

HMM Generator

ANNA  K5

@

Home
Glossary
Objectives
Formalism
Morphology
Physiology
Connectors
Serialization
Traits
Methods
Claims
Relations
Dictionary
Core UML
Ring1 Apps
Tiger Server
Features
History
ToDo
Authors
API
Images
ToDo
DNA Declarations
Physiology RO
Real Time RO
ANNA as an Eco System RO
HMM Generator
ERP

 

Revision History

Date/Reviser

Comment

Sat, 15 Jan 2011

Alexandru Mihail

Started

Wed, 19 Jan 2011

Alexandru Mihail

Finished

Sat, 22 Jan 2011

Esantioane vectoriale. Covarianta. Baum Welch

 

 

 

 

Contents

1       Obiectiv. PAGEREF _Toc283460627 \h 1

2       Constructia unui Graf Fiziologic. PAGEREF _Toc283460628 \h 2

3       Grafuri fiziologice ca Model Hidden Markov. PAGEREF _Toc283460629 \h 3

3.1        Definitia consacrata a unui HMM cu alfabet discret PAGEREF _Toc283460630 \h 3

3.2        Extensie si reprezentare. PAGEREF _Toc283460631 \h 3

3.3        Matricea grafului PAGEREF _Toc283460632 \h 3

3.4        Constructia unui HMM.. PAGEREF _Toc283460633 \h 4

3.5        Graful fiziologic. PAGEREF _Toc283460634 \h 4

4       HMM generator de semnal PAGEREF _Toc283460635 \h 5

4.1        Pasii de evaluare 1, 2. PAGEREF _Toc283460636 \h 5

4.2        Pasul 3 si 18. PAGEREF _Toc283460637 \h 6

5       Experimentul Baum-Welch. PAGEREF _Toc283460638 \h 7

5.1        Antrenarea neofitului PAGEREF _Toc283460639 \h 8

 

 

1           Obiectiv

 

Sistemul nostru de operare ANNA Kernel 5 modeleaza lumea inconjuratoare in trei dimensiuni: Topologie, Morfologie si Fiziologie. Topologia unei lumi este totalitatea obiectelor ei concrete ca suma de noduri si conexiuni imbricate. Morfologia este totalitatea tipurilor si relatiilor intre tipuri care genereaza si clasifica Topologia. Fiziologia este suma proceselor care traverseaza Topologia impreuna cu starea, istoria si rolul obiectelor.

 

Monitorul fiziologic al sistemului de operare realizeaza o proiectie a modelului din spatiul TxMxF intrun sub-spatiu TxMxF al masuratorilor unde se creaza si se actualizeaza Graful Fiziologic al proceselor urmarite. Graful Fiziologic consta in tipuri speciale proprii monitorului care genereaza noduri si arce corespunzand firelor de executie si starilor prin care trec procesele urmarite in model.

 

Proiectia se realizeaza printr-o Proba care intercepteaza activitatea proceselor din model si care creaza in monitor stari, clienti ai starilor, arce de tranzitie intre stari si directii intre clienti si stari. Monitorul calculeaza statistici de utilizare a starilor de catre procese. Daca procesele monitorizate nu sunt reentrante, atunci graful fiziologic este un proces Markovian.

 

In aceasta lucrare vom prezenta structura si constructia unui Graf Fiziologic si il vom demonstra in implementarea Modelelor Markov Ascunse pentru generarea si decodarea de semnal discret.


 

2           Constructia unui Graf Fiziologic

$

p

'

0

C

p'

B

A

 O matrice patrata de (1+M+N) linii si (1+M+N) coloane defineste structura unui GF cu M noduri client si N resurse. Matricea are o zona A care determina conectica strilor fiziologiei, o zona C a directiilor de acces de la fiecare client la resurse, o zona B a iesirii clientilor din sistem la diverse resurse. Nodul $ este un supra-nod care este simultan si client si resursa si se conecteaza cu celelalte noduri continute prin directiile determinate de zonele , p, , p'.

 

Un exemplu tipic de graf fiziologic in lucru este:

 

cu urmatoarea forma matriciala:

 

 

Procesul monitorizat este cel de formare a unui dictionar prin admisia si compilarea unor fisiere de intrare in format HTML, extragerea textului si bobinarea fiecarui text in arhiva dictionarului.

 

3           Grafuri fiziologice ca Model Hidden Markov

Folosind blocurile A, B, , si p ale matricii grafului fiziologic se poate defini un HMM.

 

3.1         Definitia consacrata a unui HMM cu alfabet discret

O={o1, o2, ...,oM}alfabetul de iesire.

W={1, 2, ..., N} multimea starilor.

st= starea modelului la momentul t.

A={aij} o matrice de probabilităţi de tranziţie intre stări.

B={bi(k)} matricea probabilitatilor de iesire.

bi(k) este probabilitatea generarii simbolului ok de catre starea i.

p={pi} este distributia starii initiale.

 

cu constrangerile:

 

=1; =1; =1;

 

Notam structura HMM cu F = (A,B,p).

 

3.2         Extensie si reprezentare

Construim setul reunit $ al alfabetului si starilor impreuna cu setul $ insusi.

$={$, o1, o2, ...,oM, 1, 2, ..., N};

Construim o singura matrice G care cuprinde A, B si p.

$ este starea de inceput si sfarsit care genereaza simbolul $.

 

3.3         Matricea grafului

Un HMM cu 2 stari si 3 litere in alfabet. La stari se adauga starea de inceput si de sfarsit $, iar la alfabet se adauga simbolul $ cu rol de separator intre cuvinte.

 

In urmatoarea matrice G:

 

3

0.228644

0.565265

0.206091

0.424381

0.575619

0.030197

0

0

0

0.398818

0.025599

0.011346

0

0

0

0.116721

0.502955

0.958457

0

0

0

0.484461

0.471446

0.085517

0.412456

0.47819

0.109354

0.382141

0.617859

0.914483

0.192345

0.429306

0.378349

0.135009

0.864991

 

se disting urmatoarele zone ale caror celule au suma 1 si reprezinta distributii de probabilitate:

A este matricea probabilitatilor de tranzitie intre starile grafului.

B este matricea probabilitatilor de iesire din stari catre starea finala $.

p este distributia starii initiale.

 

Zonele B', p', , ' au sens echivalent in Monitorul Fiziologic.

 


 

3.4         Constructia unui HMM

Matricea G a fost generata aleator din modulul algebric al sistemului de operare cu functia Random Fill care creaza o matrice cu geometrie RxC, populata cu elemente intre 0 si 1, cu densitate 1 - toate elementele nenule, respectand un hmm cu 3 litere.

 

 

Functia Random Fill face ca blocurile matricii sa fie distributii de probabilitate.

 

Graful aferent a fost generat cu functia algebrica Build Graph.

 

3.5         Graful fiziologic

Matricea G genereaza graful urmator:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Nodurile de forma hexagonala sunt literele alfabetului, nodurile dreptunghiulare (sau circulare) sunt starile automatului, cercul care le cuprinde este starea initiala sau simbolul de separare iar arcele grafului respecta conditiile HMM-ului avand suma probabilitatilor 1.


 

4           HMM generator de semnal

Graful poatea fi evaluat in interfata grafica pentru a genera secventa de observatii X=X1X2...XT in urmatorii pasi

Pasul 1: se generează indicele i conform cu distribuţia π ;

Pasul 2: for t =1, T

                        se generează Xt ~bi(x);

                        se generează indicele j~(aij); i = j;

            end

Pasul 3: afişează X1X2...XT ; STOP.

4.1         Pasii de evaluare 1, 2

La pasul 1 se alege arbitrar starea initiala 4. Aceasta genereaza simbolul C dupa probabilitatea de distributie {0.41, 0.48, 0.11}.

La pasul 2 se alege arbitrar arcul 4,5 conform distributiei probabilitatilor de trecere {0.38, 0.62}. Starea 5 genereaza simbolul D conform distributiei {0.19, 0.43, 0.38}.

4.2         Pasul 3 si 18

 

La pasul 18 sistemul a generat sirul marcat in plotul inferior din dreapta jos.

Generarea continua pana ce probabilitatea "de a se fi generat" sirul scade sub o toleranta, cand, agoritmul este resetat si un separator este emis pe banda de iesire.

5           Experimentul Baum-Welch

O sursa de semnal, un ascultator identic cu sursa si 3 ascultatori diferiti ca structura. Semnalul este acumulat intr-o matrice vector zisa buffer.

Iesirile automatelor reprezinta secventele lor de stari si sunt adunate intr-o matrice numita comparator.

Matricea de covarianta a comparatorului indica gradul de asemanare intre automate.


 

5.1         Antrenarea neofitului

 

Dupa aplicarea algoritmulu BW

Home

Home | Feedback | Contents | Search

Send mail to webmaster@ProximaCentauri.ro with questions or comments about this web site.
All principles and artwork exposed on this site or by our software products is our intellectual property. 
Copyright 2006 Proxima Centauri Romania SRL. Last modified: 05/27/09