ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE Fakulta elektrotechnická Katedra teorie obvodů
IMPLEMENTACE ROZPOZNÁVAČŮ ŘEČI DO MULTIMEDIÁLNÍCH STRUKTUR Pavel Štemberk
Školitel: Ing. Václav Hanžl, CSc. únor 2005
V současné době se hojně používá tzv. token passing algoritmus [9] (HTK - HMM toolkit). Má ovšem své nevýhody, které mohou být kompenzovány jinými metodami hledání největší pravděpodobnosti posloupnosti slov. Obsahem dizertační práce by tak byl rozpoznávač s vylepšenými vlastnostmi, které dávají konečné automaty.Toto je hlavní bod mé současné doktorandské aktivity.
2
Obsah 1 Úvod
4
2 Základní princip rozpoznávače 2.1 HMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Distribuční funkce . . . . . . . . . . . . . . . . . . . . . . . 2.2 Výpočet P (O | M ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Přímý výpočet . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Dopředný algoritmus . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Viterbiho algoritmus . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Viterbiho algoritmus s použitím logaritmů pravděpodobností 2.2.5 Algoritmus Token Passing (HTK) . . . . . . . . . . . . . . . 2.2.6 Lattice N-best a word N-best . . . . . . . . . . . . . . . . . 3 Automaty s konečným počtem stavů - FSM 3.1 Úvod do FSM . . . . . . . . . . . . . . . . . 3.2 Váhové akceptory (WFSA) . . . . . . . . . . 3.3 Váhové měniče (WFST) . . . . . . . . . . . 3.4 Operace mezi WFST . . . . . . . . . . . . . 3.4.1 Skládání (composition) . . . . . . . . 3.4.2 Determinizace . . . . . . . . . . . . . 3.4.3 Minimalizace . . . . . . . . . . . . . 3.5 Rozpoznávací síť . . . . . . . . . . . . . . . 3.5.1 WFST gramatiky . . . . . . . . . . . 3.5.2 WFST pro lexikon . . . . . . . . . . 3.5.3 WFST kontextové závislosti . . . . . 3.5.4 WFST reprezentující HMM . . . . . 3.6 Rozpoznávání řeči s použitím WFST . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . .
5 5 7 8 8 9 9 10 11 12
. . . . . . . . . . . . .
13 13 14 15 16 16 17 18 19 19 19 20 20 21
4 Programové vybavení
24
5 Shrnutí
25
6 Další činnost
25
7 Přílohy 27 7.1 Příloha A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 7.2 Příloha B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 7.3 Příloha C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3
1
Úvod
Historie rozpoznávačů řeči sahá až k počátku sedmdesátých let 19. století. Tehdy Alexandr Bell přišel s myšlenkou stroje, který by pomáhal sluchově postiženým lidem. Belovi laboratoře však zaznamenaly první větší úspěch na poli řeči v roce 1936, kdy pracovníci laboratoře vyvinuli řečový syntezátor. Tak se zrodil ”robotický” hlas, který měl úspěch v nepříliš kvalitních nízkorozpočtových filmech. První pokusy s rozpoznáváním se prováděly v 50. letech, kdy se různí vědci pokoušeli popsat základní myšlenky akustické fonetiky. V roce 1952 v Bellových laboratořích byl postaven systém pro rozpoznávání izolovaných číslovek na jednoho mluvčího. Systém pracoval na bázi měření doby spektrálních rezonancí samohlásek každé číslovky. V roce 1959 na univerzitě College ve Velké Británii byly pokusy postavit fonémový rozpoznávač pro rozpoznávání 4 samohlásek a 9 souhlásek. Srovnávali přitom spektrální čáry s danými modely. Mnohem rychlejší vývoj rozpoznávačů nastal díky platnosti Mooreova zákona o vývoji výkonu počítačů až v 70. letech 20. století. Výzkum rozpoznávání řeči v 80. letech byl charakterizován posunem na technologii založené na statistickém modelování - skrytých Markovových modelech (HMM). Přestože metoda rozpoznávání pomocí HMM byla v několika laboratořích používána (výrazně IBM a Dragon Systems), do poloviny 80. let nebyla žádná publikace o rozpoznávání pomocí HMM rozšířena [7]. V roce 1989 vznikla na univerzitě v Cambridge první verze HTK (Hidden Markov Model Toolkit) [9]. Jedná se o kolekci knihoven a modulů v jazyce C, které jsou nezbytné pro stavbu rozpoznávače na bázi skrytých Markovových modelů. Do dnešních dnů se HTK toolkit značně rozmohl o další nástroje, popřípadě došlo k zefektivnění funkcí a formy ukládání dat [6].
4
2
Základní princip rozpoznávače
Rozpoznávání řeči s použitím HMM je vlastně hledání HMM modelů pro danou promluvu - případ rozpoznávání izolovaných slov, či hledání nejlepší možné variace více ”slepených” HMM modelů představujících základní fonémy daného jazyka - případ rozpoznávání spojité řeči. Pravděpodobnost celého HMM je dána množinou vstupních pozorovacích posloupnosti v diskrétním čase [7]. V případě rozpoznávání řeči jsou pozorovací posloupnosti zparametrizované úseky řečového signálu [9]. Na obr. 1 je schematicky znázorněno jak se pozorovací vektory z řeči získávají.
set of phonemes
speech parametrisation speech vectors o1, o 2 , ... , o T recognition
Obrázek 1: Základní princip dekódování informace z lidského hlasu HMM řeší relativně velký problém v rozpoznávání mluvené řeči. Je jím rozdílná řeč různých mluvčích1 , která má za následek obrovské množství realizovatelných variací řečového signálu. Základní princip trénování HMM a vlastního rozpoznávání celých slov ukazuje obr. 2.
2.1
HMM
Zjednodušeně řečeno: HMM je stochastickým procesem vykazujícím pravděpodobnost, že množina vstupních pozorovacích posloupností dává vlastnosti právě tohoto modelu. HMM Samotný se skládá ze dvou částí - stavovým automatem s konečným počtem 1
Zde může klidně jít i o jednoho mluvčího, který má rozdílnou náladu, je udýchaný apod. Dobrým příkladem je většina mobilních telefonů s hlasovým ovládáním menu v současnosti, kde se ke zjištění podobnosti s nějakým vzorem hojně používá autokorelace
5
set of isolated words examples "one"
"two"
"three"
unknown vector
O
O
O model parameters estimation
O
choose max of probability a) training
b) recognition
Obrázek 2: a) - princip trénování HMM b) rozpoznávání řeči pomocí HMM stavů a konečným počtem výstupních distribučních funkcí s normálním rozdělením ze všech emitujících vnitřních stavů. Velmi často se tak používá pro modelování opakujících se situací s různými podmínkami, např. házení třemi různě vyváženými mincemi [7]. Příklad HMM často používaného pro rozpoznávání izolovaných slov je zobrazen na obr. 3. HMM je definován následujícími parametry: 0.85
1
0.93
2
0.83 0.06
0.07
3 0.09
b2( ot )
b1( ot )
0.92 0.12
0.08
4
5
0.05
b3( ot )
Obrázek 3: Příklad levo-pravého HMM; matice přechodů viz (1) • π - inicializační vektor; πi je tak pravděpodobností, že HMM je ve stavu i v čase t = 0, pro řeč používáme (1, 0, . . . , 0) • A - matice přechodů; ai,j je pravděpodobnost přechodu ze stavu i do stavu j viz (1) • B - matice výstupních rozdělení; bj (o) je pravděpodobnost výskytu pozorovaného vektoru o ve stavu j 0 0.93 0.07 0 0 a1,1 a1,2 a1,3 a1,4 a1,5 0 0.85 0.06 0.09 0 a2,1 a2,2 a2,3 a2,4 a2,5 A = 0 0 0.83 0.12 0.05 = a3,1 a3,2 a3,3 a3,4 a3,5 (1) 0 0 0 0.92 0.08 a4,1 a4,2 a4,3 a4,4 a4,5 0 0
0
0
0
a5,1
a5,2
a5,3
a5,4
a5,5 6
Pokud je dolní trojúhelníková část matice přechodů nulová, HMM model nazýváme levo-pravý - viz (1), obr. 3. Zatímco matice A jednotlivých modelů jsou známy již po natrénování rozpoznávače, matice B se sestavují těsně před rozpoznávacím procesem z parametrů distribučních funkcí aplikovaných pozorovací vektory. 2.1.1
Distribuční funkce
Výpočet matice B je tedy součást rozpoznávacího procesu a je počítán přes n rozměrné normální rozdělení (2) !#γs "M ns S Y X (osk − µsmk )2 1X 1 , (2) · exp − bj (o) = csm · p Q s 2 k=1 rsmk (2π)ns nk=1 rsmk s=1 m=1 kde • o = [o1 o2 ... on ]T je vstupní vektor pozorování, resp. zparametrizovaná část řečového signálu délky n • µ = [µ1 µ2 ... µn ]T je vektor středních hodnot • r = [r1 r2 ... rn ]T je vektorem rozptylů • S, resp. M je počet ”streams”, resp. ”mixtures” [9] - pro jednoduchost je zde používat nebudeme, jako S i M tak uvažujeme 1 • csm , resp. γs jsou váhy pro m-tý mixtures, resp. pro s-tý stream - opět uvažujeme 1 V praxi se však spíše pracuje s logaritmickými pravděpodobnostmi a to kvůli možné ztrátě přesnosti při násobení čísel menších jedné. Pro základní matematické operace dostáváme log(P1 P2 )
= log(P1 ) + log(P 2)
log(P1 + P2 ) = log(P1 ) + log 1 +
P2 P1
.
(3)
V praxi pro součet pravděpodobností je vhodné volit P1 ≥ P2 , potom je možné log(1 + P2 /P1 ) aproximovat jako log(P1 /P2 ). Pro logaritmické pravděpodobnosti a,b se původní operace součtu mění na ladd(a, b) = ln(ea + eb ) = max(a, b) + f (|a − b|)
,
(4)
kde f (x) = ln(1 + e−x )
(5)
Zaveďme operátor součtu N logaritmických pravděpodobností N G i=1
ai = ln
N X
eai .
(6)
i=1
7
Aplikací (3) na (2) dostaneme efektivní způsob výpočtu funkce výstupních rozdělení. ! S M ns X G X 1 1 . (7) ln bj (o) = γs ln csm + ln p − (osk − µsmk )2 Qns ns 2 rsmk (2π) r k=1 smk s=1 m=1 k=1
2.2
Výpočet P (O | M )
Chceme spočítat P (O | M ) vektoru pozorování O = (o1 , o2 , . . . , oT ) pro daný model M . obr. 2. 2.2.1
Přímý výpočet
Asi nejsrozumitelnější způsob výpočtu P (O | M ) vede přes součet všech možných posloupností stavů délky T (počtu vektorů pozorování), kterých je N T . Uvažujme pevnou posloupnost stavů s = (s1 , s2 , . . . , sT ) , (8) kde q1 je počáteční stav. Pravděpodobnost pozorované posloupnosti O při známé posloupností stavů (8) v modelu M P (O | s, M ) =
T Y
P (ot | st , M ) =
T Y
bs (ot ) ,
(9)
t=1
t=1
kde vektory pozorování považujeme za statisticky nezávislé. Pravděpodobnost nějaké posloupnosti stavů s v modelu M je dána P (s | M ) = πs1 as1 s2 as2 s3 . . . asT −1 sT ,
(10)
Pravděpodobnost současného výskytu posloupností O a s je pak součinem (9) a (10) P (O, s | M ) = P (O | s, M )P (s | M ) .
(11)
Pravděpodobnost P (O | M ) je tak dána sečtením pravděpodobnosti (11) přes všechny možné posloupnosti stavů
P (O | M ) =
P
P (O | s, M )P (s | M ) =
s
P s
π s1
T Q t=2
ast−1 st
T Q
bs (ot )
.
(12)
t=1
Přímý výpočet P (O | M ) pomocí (12) je nejnáročnější možný, neboť je nutné provést (2T − 1)N T ≈ 2T N T součinů a N T − 1 ≈ N T součtů. Pro výpočet jednoho třístavového HMM (N=3) a délku pozorovací posloupnosti T=100 bychom pak museli realizovat 2 × 100 × 3100 ≈ 1050 součinů! Pro představu by výpočet i na dnešních nejrychlejších strojích trval asi 1033 tisíciletí2 ! 2
Uvažuje se 1 mld. operací násobení za sekundu
8
2.2.2
Dopředný algoritmus
Definujme dopřednou proměnnou αt (i) = P (o1 , o2 , . . . , ot , st = i | M ) ,
(13)
která označuje pravděpodobnosti výskytu částečné posloupnosti vektorů o1 , o2 , . . . , ot a současně že HMM je ve stavu i v čase t. αt (i) pak můžeme řešit indukcí, jak je uvedeno v následujícím algoritmu [7]: 1. Inicializace α1 (i) = πi bi (o1 ), 1 ≤ i ≤ N (14) 2. Rekurze αt+1 (j) = bj (ot+1 )
N P
αt (i)aij ,
1≤t≤T −1
i=1
(15)
1≤j≤N 3. Ukončení P (O | M ) =
N X
αT (i)
(16)
i=1
Je vidět, že algoritmus je časově synchronní (nemožnost použití paralelních výpočetních jednotek), počítáme ”zleva doprava” tzn. že pro výpočet pravděpodobnosti výskytu vektorů o1 , o2 , . . . , ot musíme znát pravděpodobnosti výskytu vektorů o1 , o2 , . . . , ot−1 pro všechny konečné stavy HMM. Algoritmus tak zahrnuje N (N + 1)(T − 1) + N ≈ N 2 T součinů a (N − 1)N (T − 1) ≈ N 2 T součtů. 2.2.3
Viterbiho algoritmus
Pro vlastní rozpoznávání (jak je např. uvedeno na obr. 2) nemusíme nutně znát P (O | M ), postačující je maximální pravděpodobnost ze všech možných posloupností stavů. K nalezení nejlepší posloupnosti stavů s = (s1 , s2 , . . . , sT ) pro danou posloupnost pozorovacích vektorů O = (o1 , o2 , . . . , oT ) definujme proměnnou δt (i) =
max
s1 ,s2 ,...,st−1
P (s1 , s2 , . . . , st−1 , st = i, o1 , o2 , . . . , ot | M ) ,
(17)
která označuje nejvyšší pravděpodobnost výskytu posloupnosti o1 , o2 , . . . , ot v nalezené posloupnosti stavů s1 , s2 , . . . , st−1 a koncový stav i. Indukcí dostaneme δt+1 (j) = bj (ot+1 ) max [δt (i)aij ] . 1≤i≤N
(18)
Viterbiho algoritmus: 1. Inicializace: δ1 (i) = πi bi (o1 ), ψ1 (i) = 0
1≤i≤N
(19)
9
2. Rekurze: δt (j) = bj (ot ) max [δt−1 (i)aij ], 1≤i≤N
2≤t≤N
(20)
1≤j≤N ψt (j) = arg max [δt−1 (i)aij ], 1≤i≤N
2≤t≤N
(21)
1≤j≤N 3. Ukončení3 : P ∗ = max [δT (i)]
(22)
s∗T = arg max [δT (i)]
(23)
1≤i≤N
1≤i≤N
4. Hledání posloupnosti stavů (od konce) s∗t = ψt+1 (s∗t+1 ),
t = T − 1, T − 2, . . . , 1.
(24)
Hlavní rozdíl mezi dopředným a Viterbiho algoritmem je v hledání maxima (18) oproti (15). Náročnost algoritmu je v násobení shodná s dopředným algoritmem, tzn. cca N 2 T součinů. Jednou z výhod je však odpadnutí součtů pravděpodobností. Tak můžeme snadno počítat v logaritmických pravděpodobnostech bez použití součinů. 2.2.4
Viterbiho algoritmus s použitím logaritmů pravděpodobností
Definujme logaritmické proměnné π ˜i = log(πi ), 1≤i≤N ˜bi (ot ) = log[bi (ot )], 1 ≤ i ≤ N, 1 ≤ t ≤ T ; a ˜ij = log(aij ), 1 ≤ i, j ≤ N Další postup pak: 1. Inicializace:
δ˜1 (i) = π ˜i + bi (o1 ), ψ1 (i) = 0
1≤i≤N
(25)
(26)
2. Rekurze: h i ˜ ˜ ˜ δt (j) = bj (ot ) + max δt−1 (i) + a ˜ij 1≤i≤N h i ψt (j) = arg max δ˜t−1 (i) + a ˜ij , 2 ≤ t ≤ T, 1 ≤ j ≤ N
(27)
P˜ ∗ = max [δ˜T (i)]
(28)
s∗T = arg max [δ˜T (i)]
(29)
1≤i≤N
3. Ukončení: 1≤i≤N
1≤i≤N
3
V rozpoznávání řeči se často používá předpokladu ukončení ve stavu N, tudíž P ∗ = δT (N ) a s∗T = N
10
4. Hledání posloupnosti stavů (od konce) s∗t = ψt+1 (s∗t+1 ),
t = T − 1, T − 2, . . . , 1.
(30)
Náročnost algoritmu je v tomto případě cca N 2 T součtů. Jedná se tak o nejvýhodnější možnou implementaci algoritmu hledání nejlepší posloupnosti stavů. Výše uvedený algoritmus demonstruje na příkladě třístavového HMM s pozorovací posloupností šesti vektorů obrázek 4. 4
o1
o2
0.08
o4
o5
~ ~ d3 (3) =b3( o3)+log(0.12)+ d 2(2) y3 (3)=2
~ (3) =b ( o )+log(0.12)+ ~ (2) d4 d3 3 4 y4 (3)=2
~ (3) =b ( o )+log(0.12)+ ~ (2) d5 d4 3 5 y5 (3) =2
~ (2) =b ( o )+log(0.06)+ ~ (1) d2 d1 2 2 y2 (2)=1
~ (2) =b ( o )+log(0.06)+ ~ (1) d3 d2 2 3 y3 (2)=1
~ (2) =b ( o )+log(0.06)+ ~ (1) d4 d3 2 4 y4 (2)=1
~ (2) =b ( o )+log(0.83)+ ~ (2) d5 d4 2 5 y5 (2)=2
~ ~ d2 (1) =b1(o2)+log(0.85)+ d 1(1) y2 (1)=1
~ ~ d3 (1) =b1( o3)+log(0.85)+ d 2(1) y3 (1)=1
~ (1) =b ( o )+log(0.85)+ ~ (1) d4 d3 1 4 y4 (1)=1
3
0.92
o3
o6 ~ (3) =b ( o )+log(0.92)+ ~ (3) d6 d5 3 6 y6 (3) =3
0.12
2
0.83 0.06
1
0.85
~ d1 (1) =b1 ( o1) y1 (1)=0
0.93
0
Obrázek 4: Demonstrace Viterbiho algoritmu - příklad pro 3-stavový HMM a 6 pozorovacích vektorů. Šipky ukazují na stav i předchozího vektoru o s největší částečnou pravděpodobností (27)
2.2.5
Algoritmus Token Passing (HTK)
V HTK je pro rozpoznávání spojité řeči využita další alternativa Viterbiho algoritmu nazývaná token passing [9]. Opět jde o nalezení posloupnosti stavů s = (s1 , s2 , . . . , sT ) s největší pravděpodobností P (O | s, M ). Každý stav j v čase t obsahuje přemístitelný token obsahující mimo jiného i částečnou pravděpodobnost δ˜t (j) (pro pozorovanou posloupnost vektorů o1 , o2 , . . . , ot ). Algoritmus token passing tak nahrazuje (27). Pro každou pozorovací posloupnost v čase t jsou vykonány následující kroky: 1. každý token ve stavu i je zkopírován do všech navazujících stavů j, přičemž je jeho částečná pravděpodobnost δ˜t (j) zvětšena o ˜bj (ot ) + a ˜ij 2. tokeny se v každém stavu seřadí dle jejich částečné pravděpodobnosti δ˜t (j) a v případě hledání pouze jedné vítězné cesty s nejvyšší P (O | s, M ) se všechny tokeny, kromě toho s nejvyšší pravděpodobností zruší. Předpokládejme, že možné sekvence Markovových modelů jsou definovány sítí s konečným počtem stavů. Příklad ukazuje obrázek 5, kde je znázorněna jednoduchá sít. Každé slovo je v síti definováno jako posloupnost Markovových modelů (reprezentovaných ovály) představujících fonémy. Všechny slova jsou umístěny do smyčky, kde speciální stavy konců slov 11
(tzv. word-end ) jsou označeny obdelníky. Celá síť tak představuje v podstatě jeden velký HMM, na který je aplikován výše uvedený algoritmus. Jediný rozdíl je v požadavku více informací, než je logaritmická pravděpodobnost nejlepšího tokenu. Jestliže nejlepší token dorazí na konec promluvy, musí být z cesty skrz síť patrná rozpoznaná sekvence modelů. Každý token proto obsahuje ukazatel, nazývaný word end link. Pokud je token šířen z posledního stavu některého slova (zjištěno projitím skrz stav word-end) do vstupního stavu slova jiného, pak takovýto přechod reprezentuje potenciální hranici slov. V tomto momentě je generován tzv. WLR - Word Link Record, kde je uchován zápis slova, které token právě opustil. Ukazatel word end link nového tokenu od tohoto okamžiku ukazuje na právě vytvořený WLR. WLR má v sobě také ukazatel, který je později přepsán ukazatelem na nový WLR - vše ilustruje obr. 5. Podrobná ilustrace principu rozpoznávání pomocí token passing algoritmu je v příloze A. Jedná se o fonémový rozpoznávač slov ”jo” a ”ne” pro případ 26 pozorovacích vektorů o. Jak je z obrázku vidět, v algoritmu token passing se používají tzv. neemitující stavy. Jedná se o stavy na koncích slov a stavy, které mají zajistit větvení možných promluv - na obrázku vyznačeno kružnicemi. 2.2.6
Lattice N-best a word N-best
Algoritmus lattice N-best je rozšířením výše popisovaného algoritmu token passing. Neukládá se tak do WLR pouze nejlepší token, ale i další s většími pravděpodobnostmi. Takto je možné mít celou řadu možností promluvy seřazenou dle jejich pravděpodobnosti. Algoritmus je však omezen jedním tokenem na stav; není tak možné procházet celou historií jednotlivých cest. Toto omezení je možné odstranit, pokud bude všem stavům přiřazeno více tokenů oproti jednomu, za významné tokeny jsou pak označeny ty, které přišly z jiného předchozího slova. Algoritmus se pak nazývá word N-best [9].
12
Before
After
logP
logP
d o t
v s r ^
Recording Decisions
a m i
dva osm tri ^
Best Token came from "osm"
logP
logP
logP
logP
t−3 dva
t−2 dva
t−1 osm
t Word Ends osm
Record
Obrázek 5: Token passing algoritmus a záznamy možných hranic slov
3
Automaty s konečným počtem stavů - FSM
Aplikace konečných automatů na rozpoznávání řeči [2, 1, 4, 5, 10] je v současné době jednou z náplní výzkumu společnosti AT&T. Měnič (transducer) je automat s konečným počtem stavů, který mapuje vstupní posloupnost např. znaků na výstupní. Váhový převaděč přiřazuje jednotlivým přechodům váhy, které mohou reprezentovat např. pravděpodobnost, dobu trvání, penalizace, či cokoliv, co je možné lineárně akumulovat přes celou cestu stavového automatu. Vzhledem k charakteru současných komponent používaných pro rozpoznávání řeči (Viterbiho algoritmus, gramatika, . . .) se jeví použití konečných automatů jako váhových měničů zcela přirozeně.
3.1
Úvod do FSM
Váhové automaty s konečným počtem stavů (dále jen FSM4 ) závisí mimo jiné na algebraické struktuře použitého semiringu [4]. Semiring (K, ⊕, ⊗, ¯0, ¯1) je tak množina K obsahující dvě matematické operace ⊕ a ⊗, pro které platí ¯0 ⊕ a = a ⊕ ¯0 = a ¯1 ⊗ a = a ⊗ ¯1 = a
a∈K .
(31)
Například semiringem je (N, +, ., 0, 1). Váhy používané pro rozpoznávání řeči často reprezentují pravděpodobnosti. Patřičný semiring pro uvedené použití se tak nazývá 4
Finite-state machines
13
pravděpodobnostní semiring (R, +, ., 0, 1). Jak již bylo uvedeno v předchozí kapitole, je výhodné počítat s logaritmy pravděpodobností. Logaritmický semiring má pro tento případ tvar (R+ ∪ {∞}, ladd, +, ∞, 0). Pokud je používán Viterbiho algoritmus, kde se operace součtu nevyskytuje, použijeme tzv. tropical semiring (R+ ∪ {∞}, max, +, ∞, 0).
3.2
Váhové akceptory (WFSA)
Modely, jako je např. HMM pro rozpoznávání řeči jsou speciálním případem váhového akceptoru konečných stavů(WFSA).WFSA A = (Σ, Q, E, i, F, λ, ρ)
(32)
přes semiring K je dán vstupní množinou Σ, konečnou množinou stavů Q, konečným počtem přechodů E ⊆ Q × (Σ ∪ {}) × K × Q, počátečním stavem i ∈ Q, množinou konečných stavů F ⊆ Q, počáteční váhou λ a konečnou váhovou funkcí ρ. Přechod t = (t− , l(t), w(t), t+ ) ∈ E může být reprezentován spojnicí ze zdrojového stavu t− do cílového stavu t+ s návěštím l(t) a váhou w(t), která v rozpoznávačích řeči velmi často reprezentuje logaritmus pravděpodobnosti. Cesta v A je posloupnost pospojovatelných přechodů, pro které platí − t+ i = ti+1 ,
i = 1, . . . , n − 1 .
(33)
Návěští značí přechod nepředpokládající vstup. Úspěšná cesta π = t1 . . . tn je cestou z počátečního stavu i do koncového stavu f ∈ F . π má přiřazeno své návěští, pospojované z návěští jednotlivých přechodů l(π) = l(t1 ) . . . l(tn ) a svou váhu, což je ⊗ operace mezi inicializační vahou, vahami jednotlivých přechodů a konečnou vahou ρ(t+ n) w(π) = λ ⊗ w(t1 ) ⊗ w(t2 ) ⊗ . . . ⊗ w(tn ) ⊗ ρ(t+ n) .
(34)
Posloupnost symbolů x je akceptována automatem A, pokud existuje cesta π s návěštím x tak, že l(π) = x . (35) Celková váha přiřazená automatem A posloupnosti x je dána ⊕ operací mezi vahami všech úspěšných cest π s posloupností jednotlivých návěští x. WFSA tak mapuje vstupní posloupnost symbolů na váhy. Na obr. 6 nahoře vidíme malou část modelu gramatiky pro hlasové ovládání hry šachy, kde slova coby návěští skrz každou úspěšnou cestu reprezentují možnou variantu posloupnosti slov. w(π) pak dává věrohodnost dané posloupnosti. Dole je pak vyznačeno použití WFSA pro mapování pravděpodobností alternativních výslovností daného slova. 14
dáma/0.5 <sil>/1
0
1
2
na/0.5 na/0.5
jezdec/0.5
pět/0.5 5
e/1
3
6
čtyři/0.5
č/0.5 š/0.5
1
t/1
8
<sil>/0.5
4
0
<sil>/0.5
7
2
i/1
3
ř/0.5 r/0.5
4
i/1
5
Obrázek 6: Příklady WFSA. Je dohodnuto, že stavy se značí kružnicemi a jsou očíslovány dle jejich pořadí. Počáteční stav je reprezentován silnou kružnicí, koncové pak zdvojenou. Váhy a návěští značíme jako l(t)/w(t). Konečná váha ρ(f ) koncového stavu f ∈ F je v koncovém stavu označena f /rho(f ), či vynechána pokud ρ(f ) = ¯1(uvedený příklad) podobně jako inicializační váha λ.
3.3
Váhové měniče (WFST)
Váhové měniče s konečnými stavy (dále jen WFST5 ) se od WFSA liší doplněním jednoduchého návěští přechodů párem (i, o) vstupního návěští i a výstupního o. WFST T = (Σ, Ω, Q, E, i, F, λ, ρ) (36) přes semiring K je dán vstupní množinou návěští Σ, výstupní množinou návěští Ω, konečnou množinou stavů Q, konečným počtem přechodů E ⊆ Q×(Σ∪{})×(Ω∪{})×K×Q, počátečním stavem i ∈ Q, množinou konečných stavů F ⊆ Q, počáteční váhou λ a konečnou váhovou funkcí ρ. Přechod t = (t− , li (t), lo (t), w(t), t+ ) ∈ E může být reprezentován spojnicí ze zdrojového stavu t− do cílového stavu t+ se vstupním návěštím li (t), výstupním návěštím lo (t) a vahou w(t). Definice cesty, její posloupnosti návěští a vah je shodná s WFSA. Přibyla zde posloupnost výstupních návěští úspěšné cesty a ta je dána složením jednotlivých výstupních návěští podél této cesty. Gramatika reprezentovaná na obr. 6 nahoře pomocí WFSA je zobrazena na obr. 7 pomocí WFST. Není zde žádná nová informace, reprezentace pomocí WFST se však používá mnohem častěji. Na obr. 7 dole je pak znázorněn příklad slovníku mapujícího jednotlivé fonémy do slov, kde váhy coby pravděpodobnosti reprezentují věrohodnost alternativní výslovnosti. 5
Weighted finite-state transducers - používané české označení též překladový automat
15
dáma:dáma/0.5 0
<sil>:<sil>/1
1
2
na:na/0.5 na:na/0.5
jezdec:jezdec/0.5
pět:pět/0.5 5
e/1
3
čtyři:čtyři/0.5
4
č:čtyři/0.5 0
1
t:<eps>/1
6
<sil>:<sil>/0.5 <sil>:<sil>/0.5
8
7
2
i:<eps>/1
3
š:čtyři/0.5
ř:<eps>/0.5 r:<eps>/0.5
4
i:<eps>/1
5
d:dva/1 6
v:<eps>/1
7
a:<eps>/1
8
Obrázek 7: Příklady WFST
3.4
Operace mezi WFST
WFSA, resp. WFST je možné zpracovávat pomocí operací [2] [4]. Ty jsou zobrazeny v následující tabulce, kde silně vytištěné operace se často používají v rozpoznávání řeči a budou zde popsány. Všechny operace jsou popsány v [3] nebo v manuálu k libovolnému FSM toolkitu (viz dále). constructing operation closure union concatenation complementation intersection composition
A∗ A∪B AB A¯ A∩B A◦B
optimisation - identical epsilon removal determinization minimization FSA FSA FSA FST
others reverse inversion projection (FSM→FSA) equivalence weight pushing best path
Jak dále uvidíme, jsou pro sestavení automatu coby rozpoznávacího zařízení potřeba právě tyto operace. Na obr. 7 je ukázka jednoduché gramatiky a lexikonu (shora). Pokud budou do lexikonu vstupem jednotlivé fonémy, výstupem z něj jsou slova, které pak použijeme jako vstup do automatu gramatiky pro zmapování dané věrohodnosti posloupnosti slov. Právě vytvoření automatu, který dělá výše uvedenou činnost (mapování posloupnosti fonémů na věrohodnost posloupnosti slov) je dobrým příkladem operace skládání (composition). 3.4.1
Skládání (composition)
Skládání dvou měničů R a S T =R◦S
(37)
16
má za následek vytvoření cesty mapující posloupnost návěští u na posloupnost w právě když měnič R mapuje posloupnost u na posl. v a současně měnič S mapuje posl. v na posl. w. Váhy jsou pak výsledkem operátoru ⊗ mezi odpovídajícími přechody měničů R a S [4, 8]. Skládání se tak používá pro spojování jednotlivých úrovní reprezentovaných tzv. rozpoznávací kaskádou (dvě komponenty z rozpoznávací kaskády jsou např. uvedeny na obr. 7) viz dále. Stavy výsledného měniče po operaci skládání (37) jsou dány párem stavů měničů c:a/0.300 a:b/0.100 0
1
a:b/0.600 a:a/0.400 b:b/0.5
b:a/0.200
3/0.600
0
b:c/0.300
1
a:b/0.400
2/0.699
2
c:b/0.900 c:b/0.700 (0,0)
a:c/0.400
(1,1)
(1,2)
a:b/1
a:b/0.800
(3,2)/1.299
Obrázek 8: Příklad skládání dvou WFST Ra • • •
S pokud Počáteční stav je párem počátečních stavů R a S Koncové stavy jsou párem koncových stavů R a S Pro každý pár přechodů tR z r do r0 a tS z s do s0 existuje přechod t z (r, s) do (r0 , s0 ) tak, že výstupní návěští tR je rovno vstupnímu návěští tS Přechod t tak přebírá vstupní návěští z tR , výstupní z tS váhu jako ⊗ operaci vah tR a tS . Problematika prázdných návěští je diskutována např. v [3] Na obr. 8 je příklad operace skládání [4]. Je zde použit tropical semiring, operace ⊗ tak znamená součet (váhy sečteny). 3.4.2
Determinizace
WFST je deterministický, pokud každý z jeho stavů má nejvýše jeden přechod pro dané vstupní návěští [4]. Obr. 9 ilustruje příklad determinizace slovníku číslovek. Jak je z obrázku vidět, determinizace zajišťuje jedinečné vstupní návěští pro přechod z každého stavu. To se po determinizaci projeví jakýmsi ”rozvětvením” automatu. Pro váhový měnič, resp. akceptor zde platí zachování nejnižší váhy úspěšné cesty [4]. Determinizace je identickou operací. Znamená to, že vznikající automat je ekvivalentní původnímu. Dva WFSA jsou ekvivalentní, pokud přiřazují stejné váhy pro každou možnou vstupní posloupnost. Váhy mohou být rozmístěny odlišně, váha všech možných 17
d:deset
1
d:dva
6
d:dvacet
0
9
d:dvanáct
15
o:osm
22
e:<eps>
2
v:<eps>
7
v:<eps>
10
v:<eps>
16
s:<eps>
23
s:<eps>
a:<eps>
d:<eps> 0
1
v:<eps>
e:<eps>
11
a:<eps>
17
m:<eps>
c:<eps>
n:<eps>
e:<eps>
6
c:dvacet a:<eps>
2
s:<eps>
m:<eps>
5
12
18
9
10
n:dvanáct
7
<eps>:dva
o:osm
t:<eps>
5
e:<eps>
á:<eps>
13
19
t:<eps>
c:<eps>
14
20
t:<eps>
21
24
3
4
4
8
a:<eps>
s:<eps> e:deset
3
8
11
t:<eps>
e:<eps>
á:<eps>
13
14
15
t:<eps>
c:<eps>
16
17
t:<eps>
18
12
Obrázek 9: Příklad determinizace lexikonu (část rozpoznávací kaskády) úspěšných cest musí být zachována. Dva WFST jsou ekvivalentní, pokud mapují stejnou výstupní posloupnost a stejné váhy úspěšných cest. Rozmístění vah podél úspěšné cesty být identické nemusí. Časová náročnost je úměrná n2 , kde n je počet stavů. Je možné dokázat, že ne všechny váhové automaty jdou detrminizovat. Nicméně platí, že determinizovat lze každý acyklický WFSA nebo WFST [4]. Podrobný popis algoritmu je možné najít např v [2]. 3.4.3
Minimalizace
Každý deterministický automat může být minimalizován. Výsledný automat B má po minimalizaci nejmenší možný počet stavů a přechodů ze všech možných deterministických automatů ekvivalentních původnímu automatu A. Minimalizace FSA je celkem <eps>
a 4
7
n c
9
v
d 0
1
e
o 2
á
10 e
c 8
t
11
6
s 3 s
m 5
Obrázek 10: Příklad minimalizace determinizovaného lexikonu z obr. 9 výkonný proces; časová náročnost je zde úměrná m + n, resp. m log n pro acyklický případ, resp. obecný případ, kde m je počet přechodů a n počet stavů. Příklad minimalizace 18
determinizovaného lexikonu z obr. 9 ilustruje obr. 10. Algoritmus minimalizace váhového akceptoru vyžaduje před minimalizací samotnou tzv. řazení vah [4, 2].
3.5
Rozpoznávací síť Rozpoznávací sítí rozumíme složení [1] H ◦C ◦L◦G ,
kde • • • •
(38)
H- měnič mapující stavy jednotlivých HMM na kontextově závislé fonémy C - měnič mapující kontextově závislé fonémy (trifóny) na kontextově nezávislé L - slovník, resp. lexikon mapující fonémy do slov G - stavový automat reprezentující gramatiku (pravděpodobnost posloupnosti slov)
3.5.1
WFST gramatiky
Zjednodušený příklad gramatiky pro hru šachy je zobrazen na obr. 7 nahoře. Gramatika muže být vytvořena buď ručně (případ nějakého jednoduššího hlasového ovládání - např. zde uváděná hra šachy), nebo pomocí nějakých dlouhých textů bez pravopisných chyb. Ve druhém případě automat gramatiky nazýváme n-gram, kde n je historie předchozích slov. Například pro n = 2 a dvě slova w1 a w2 bude automat gramatiky vypadat dle obr. 11. P (w) zde označuje věrohodnost výskytu slova w a P (w1 | w2) věrohodnost w1:w1/P(w1|w1) w2:w2/P(w2|w1) w1:w1/P(w1) 0
1
w2:w2/P(w2|w2)
w1:w1/P(w1|w2)
2
w2:w2/P(w2)
Obrázek 11: Bigram pro slova w1 a w2 výskytu slova w1 po slově w2. 3.5.2
WFST pro lexikon
Měnič pro lexikon mapuje vstupní posloupnost fonémů na slova, přičemž může brát v úvahu alternativní výslovnost (např. obr. 6 dole). Příklad lexikonu ukazuje obr. 9 nahoře. Pokud však má být rozpoznávací kaskáda (38) platná, je potřeba operace uzavření [1]. Uzavřený lexikon je na obr. 12. 19
d:dvanáct
v:<eps>
15
16
a:<eps>
17
n:<eps>
18
á:<eps> 19
<eps>:<eps>
d:deset
d:dva
e:<eps>
1
6
s:<eps>
2
v:<eps>
<eps>:<eps>
3
e:<eps>
5
4
a:<eps>
7
20
8
<eps>:<eps> 25
c:<eps> t:<eps>
t:<eps> 0
<eps>:<eps> <eps>:<eps>
t:<eps> e:<eps>
o:osm d:dvacet
22
s:<eps>
m:<eps>
24
a:<eps>
11
23
c:<eps>
14
13
12 21
9
v:<eps>
10
<eps>:<eps>
Obrázek 12: Uzavřená verze lexikonu z obr. 9 3.5.3
WFST kontextové závislosti
Tento měnič mapuje kontextově závislé fonémy (trifóny) na kontextově nezávislé6 . Měnič samotný je poměrně rozlehlý, neboť obsahuje n2 +n+1 stavů a n3 +2n2 +n přechodů, kde n je počet fonémů. Na obr. 13 je z důvodů přehlednosti zobrazen měnič pouze pro dva fonémy, kde kontextově závislý foném je označen jako foném/levý kontext pravý kontext. x/<eps>_x:x/<eps>_<eps> x/<eps>_x:x/x_x x/<eps>_x:x/<eps>_x
x/<eps>_x:x/x_<eps>
x,<eps> x/<eps>_x:x/y_<eps>
x,x
x/<eps>_y:y/<eps>_x x/<eps>_x:x/y_x x/<eps>_x:x/x_y
<eps>,*
y,x
x/<eps>_y:y/x_x
x/<eps>_x:x/<eps>_y x/<eps>_x:x/y_y x,y x/<eps>_y:y/x_y
x/<eps>_y:y/<eps>_y
x/<eps>_y:y/y_x x/<eps>_y:y/y_y
y,y x/<eps>_y:y/<eps>_<eps>
x/<eps>_y:y/y_<eps>
x/<eps>_y:y/x_<eps>
y,<eps>
Obrázek 13: Příklad měniče kontextové závislosti; pro jednoduchost pouze pro dva fonémy ”x” a ”y”. Např. vstupní posloupnost ”x y x x” bude mapována na ”x/ y y/x x x/y x x/x ” a naopak, prohodíme-li vstupní a výstupní návěští automatu (tzv. inverze)
3.5.4
WFST reprezentující HMM
HMM byly podrobněji popsány v předchozí kapitole. Měnič musí obsahovat všechny použité modely s kontextovou závislostí. V případě rozsáhlejších systémů může v praxi jít i o cca 10000 modelů. Váhy jsou reprezentovány pomocí matice přechodů A, distribučními funkcemi bj o(t) jednotlivých vektorů pozorování o(t). Váhy je tak možné doplnit až po 6
Prohozením vstupních a výstupních návěští - inverzí dosáhneme opaku
20
x#2:<eps>
x#1:<eps> <eps>:x
1
x#1:<eps>
3
x#3:<eps> x#2:<eps>
5
x#3:<eps> 7
<eps> 9
<eps>
0 <eps> <eps>:y y#1:<eps> 2
y#3:<eps>
y#2:<eps> y#1:<eps>
4
y#2:<eps>
y#3:<eps>
8
6
Obrázek 14: Příklad dvou uzavřených 3-stavových HMM fonémů ”x” a ”y” bez kontextové závislosti. rozvinutí rozpoznávací kaskády do dopředné nedeterministické sítě a po ukončení promluvy. Ukázka dvou uzavřených HMM je na obr. 14
3.6
Rozpoznávání řeči s použitím WFST
Shrňme postup, který vede k vytvoření rozpoznávače založeného na FSM. 1. z gramatiky (vytvořené ručně, nebo z nějakého obsáhlého textu) vytvoříme měniče G, L, C a H a z nich optimalizovanou rozpoznávací kaskádu (38) [4]. Dostaneme min(det(H ◦ det(C ◦ det(L ◦ G))))) .
2. 3.
4.
5.
(39)
Příklad rozpoznávací kaskády reprezentující fonémový rozpoznávač jednoho slova osm je na obr. 15 vlevo. nahrajeme promluvu a získáme tak pole pozorovacích posloupností O = {o1 , o2 , . . . , oT } s počtem vektorů T . pomocí předem natrénovaných HMM pro jednotlivé fonémy (získaných např. použitím HTK [9]), známého pole vektorů O vytvoříme pravděpodobnostní matici P s prvky jsou výsledné pravděpodobnosti funkce bM #j (ot ), kde M #j představuje řádek matice (HMM model M ve stavu j) a t sloupec. rozpoznávací kaskádu s pomocí matice P rozvineme v dopřednou nedeterministickou sít jak ukazuje na příkladě obr. 15 vpravo. Velikost vah je pak dána parametry patřičných HMM modelů a pozorovacími posloupnostmi ot , viz obr.16. nástrojem fsmbestpath z FSM toolkitu nalezneme tzv. n-bestpath [2]. Výstupní posloupnosti návěští tak představují n nejpravděpodobnějších variant sekvencí rozpoznaných HMM kontextově závislých fonémů.
21
o1
o2
o3
o4
o5
o6
o7
o_a11
bo#1 ( o1 )
bo#1 ( o2 )
bo#1 ( o3 )
bo#1 ( o4 )
bo#1 ( o5 )
bo#1 ( o6 )
bo#1 ( o7 )
bo#1 ( o8 )
bo#1 ( oN )
o_a22
bo#2 ( o1 )
bo#2 ( o2 )
bo#2 ( o3 )
bo#2 ( o4 )
bo#2 ( o5 )
bo#2 ( o6 )
bo#2 ( o7 )
bo#2 ( o8 )
bo#2 ( oN )
o_a33
bo#3 ( o1 )
bo#3 ( o2 )
bo#3 ( o3 )
bo#3 ( o4 )
bo#3 ( o5 )
bo#3 ( o6 )
bo#3 ( o7 )
bo#3 ( o8 )
bo#3 ( oN )
bs#1 ( o1 )
bs#1 ( o2 )
bs#1 ( o3 )
bs#1 ( o4 )
bs#1 ( o5 )
bs#1 ( o6 )
bs#1 ( o7 )
bs#1 ( o8 )
bs#1 ( oN )
s_a22
bs#2 ( o1 )
bs#2 ( o2 )
bs#2 ( o3 )
bs#2 ( o4 )
bs#2 ( o5 )
bs#2 ( o6 )
bs#2 ( o7 )
bs#2 ( o8 )
bs#2 ( oN )
s_a33
bs#3 ( o1 )
bs#3 ( o2 )
bs#3 ( o3 )
bs#3 ( o4 )
bs#3 ( o5 )
bs#3 ( o6 )
bs#3 ( o7 )
bs#3 ( o8 )
bs#3 ( oN )
m_a11
bm#1( o1 )
bm#1( o2 )
bm#1( o3 )
bm#1( o4 )
bm#1( o5 )
bm#1( o6 )
bm#1( o7 )
bm#1( o8 )
bm#1( oN )
m_a22
bm#2( o1 )
bm#2( o2 )
bm#2( o3 )
bm#2( o4 )
bm#2( o5 )
bm#2( o6 )
bm#2( o7 )
bm#2( o8 )
bm#2( oN )
bm#3( o1 )
bm#3( o2 )
bm#3( o3 )
bm#3( o4 )
bm#3( o5 )
bm#3( o6 )
bm#3( o7 )
bm#3( o8 )
bm#3( oN )
o#0
o8
oN
o_a01
o#1
o
o_a12
o#2 o_a23
o#3 o_a34
s#1
s
s_a11
s_a12
s#2 s_a23
s#3 s_a34
m#1
m
m_a12
m#2 m_a23
m#3
m_a33
m_a34
m#4
Obrázek 15: Ukázka sestavení pravděpodobnostní matice a následného dopředného nedeterministického automatu (vpravo) z rozpoznávací kaskády (vlevo). Tento příklad rozpoznávače samozřejmě může rozpoznt pouze jedno slovo, ale pro vysvětlení principu plně vyhovuje
o2
o1
o#0
o3
o_a01
o#1
o
o_a11
o_a12
o#2
o_a22
o_a23
o#3
o_a33
o_a34
s#1
e:e / o_a11
.
bo#1 ( o2 )
e:e / o_a12
.
bo#2 ( o2 )
bo#1 ( o1 )
bo#1 ( o2 ) bo#2 ( o2 )
e:e / o_a11
.
bo#1( o3 )
e:e / o_a12
.
bo#2( o3 )
e:e / o_a22
.
bo#2( o3 )
e:e / o_a23
.
bo#3( o3 )
e:e / o_a11
.
bo#1( o4 )
e:e / o_a12
.
bo#2( o4 )
bo#1 ( o3 ) bo#2 ( o3 ) bo#3 ( o3 )
e:e / o_a22
.
bo#2( o4 )
e:e / o_a23
.
bo#3( o4 )
e:e / o_a33
.
bo#3 o4
e:o / o_a34
.
bs#1( o4 )
s_a11
s_a12
Obrázek 16: Detail vytváření vah v rozvinutém nedeterministickéma automatu z obr. 15
22
6. Získané posloupnosti fonémů přivedeme na vstup neucelené rozpoznávací kaskády det(C ◦ det(L ◦ G)) .
(40)
Nejpravděpodobnější promluvu pak určíme jako výstup měniče (40) s nejnižší vahou7 . Příklad rozpoznávače slov ”ano” a ”ne” je uveden v příloze B. Zde je vidět složitost výsledného stavového automatu, jehož sestavení z rozpoznávací kaskády následuje po ukončení rospoznávané promluvy (nutně potřebujeme znát počet pozorovacích vektorů).
7
Váhy zde představují záporné logaritmy pravděpodobností (použit tropical semiring)
23
4
Programové vybavení
Pro realizaci uvedených operací automatů s konečnými stavy používám FSM knihovny v4.0 od AT&T (Mohri a kol. 2000). Z volně dostupných knihoven je tato jedna z nejvýkonnějších, avšak je dostupná pouze v binární formě. Pro natrénování HMM reprezentujících české trifóny je použit HTK toolkit v3.2.1 [9, 6]. Data pro trénování pocházejí z řečové databáze SPEECON (cca 1000 mluvčích), která je pro studentské účely k dispozici na katedře teorie obvodů FEL ČVUT. Pro zpracování dat při trénování pomocí HTK a transformace HTK lattice formátu na AT&T FSM formát8 byl napsán program hdp - HTK data preparation toolkit. Pro vytvoření jednotlivých měničů H, C, L, G z volného textu a vytvoření dopředného nedeterministického automatu z rozpoznávací kaskády je vyvíjen program rct - recognition cascade toolkit. Ten v současné době umožňuje vytvořit kompletní rozpoznávací kaskádu ve formátu AT&T, rekurzivní vytvoření dopředné sítě je zatím ve vývoji (příloha C ukazuje prozatímní výsledek rozpoznávače slov ”ANO” a ”NE”).
8
V této práci jsem se o tomto směru použití FSM toolkitu nezmiňoval, více v [10]
24
5
Shrnutí
Srovnejme několik základních vlastností rozpoznávačů vytvořených pomocí HTK a FSM toolkitu. Vytvoření rozpoznávací sítě je pro HTK zapouzdřený proces, jde o vytvoření lattice 9 pomocí nástrojů HParse (případ ručně psané gramatiky) nebo HBuild (případ sestavení gramatiky z textu) [9]. Vlastní dopředná rozpoznávací síť, jak je na příkladu zobrazena v příloze A se vytvoří až po dosažení vstupních pozorovacích posloupností o1 , o2 , . . . , oT . Pro metodu konečných automatů je dopředná rozpoznávací síť vytvořena obdobným způsobem těsně po zparametrizování vstupní promluvy, avšak z již hotové minimalizované a determinizované rozpoznávací kaskády, tedy nikoliv jen z gramatiky. Znamená to významné snížení velikosti celkové rozpoznávací sítě a ušetření času potřebného pro rozpoznávání dané promluvy. Síťová reprezentace kontextově závislých fonémů je pro HTK značně náročná. znamená to poměrně obtížný proces při vytvoření dopředné rozpoznávací sítě. Metoda konečných automatů díky měniči kontextové závislosti a následné kompozici tohoto měniče C s L◦G tuto problematiku řeší již před vlastním rozpoznávacím procesem, takže je zde opět časová úspora. Rozdělení vah v HTK lattice může mít za následek neefektivní vyhledávání nejlepší cesty. Pro konečné automaty existuje operace weight pushing, která umožňuje v části rozpoznávací kaskády L ◦ G váhy seřadit dle jejich velikosti při zachování ekvivalentního automatu [2, 1, 4, 8].
6
Další činnost
Na katedře teorie obvodů plánuji pokračovat ve vývoji rozpoznávače využívajícího již zmíněný FSM toolkit od AT&T. Prozatímním výsledkem je program rct napsaný v jazyce C. Ten je schopen spolu s FSM toolkitem vytvořit rozpoznávací kaskádu a z ní (zatím pouze omezeno na rozpoznávání jednotlivých slov) jednoduchou dopřednou síť. Zatím bez vah; načítání HMM modelů v HTK formátu a zparametrizované promluvy pomocí HTK nástroje HCopy bude vyřešeno v nejbližších týdnech.
9
Síť pro gramatiku [9]
25
Reference [1] Fernando, C., Pereira, N., Riley, M. Speech recognition by composition of weighted finite automata. MIT Press , Cambridge, Massachusetts, 1997. [2] Mohri, M. Finite-state transducers in language and speech processing. Association for Computational Linguistic, 23:2, 1997. [3] Mohri, M., Fernando, C., Pereira, N. The design principles of weighted finite-state transducer library. Theoretical Computer Sience, 231:17–32, 2000. [4] Mohri, M., Fernando, C., Pereira, N. Weighted finite state transducers in speech recognition. Computer Speech and Language, 1:69–88, 2002. [5] Mohri, M., Riley, M. Network optimizations for large vocabulary speech recognition. MIT Press , Cambridge, Massachusetts, 25:3, 1997. [6] neuveden. Htk history. URL: http://htk.eng.cam.ac.uk/docs/history.shtml. [7] Rabiner, L., Juang, B., H. Fundamentals Of Speech Recognition. Englewood Cliffs, N.J., PTR Prentice Hall, c1993. 507 p. TK7895.S65R33, 1993. [8] Roche, E., SchabesRabiner, Y. Finite-State Language Processing. 464p, ISBN 0-26218182-7, 1997. [9] Young, S. The HTK Book (for HTK Version 3.2.1). Microsoft Corporation, Cambridge University Engineering Department, 3.2 edition, 2002. [10] Štemberk, P. Speech recognition based on fsm and htk toolkits. Příspěvek ve sborníku, Digital Technologies 2004, EDIS-Žilina University publishers, Žilina, ISBN 80-8070-334-5., 1:55–60, 2004.
26
o
j_a12
j#1
o#3
e
n
o_a22
o_a11
j_a33
j_a22
j_a11
o_a33
o_a23
o#2
o_a12
o#1
j_a34
j#3
j_a23
j#2
e#3
e_a22
e_a11
n_a33
n_a22
n_a11
e_a33
e_a23
e#2
e_a12
e#1
n_a34
n#3
n_a23
n#2
n_a12
n#1
o2
o3
o4
o
o5
o6
ne
LogP NULL t=8 jo
LogP NULL t=8 ne
LogP NULL t=7
jo
LogP NULL t=7
ne
jo
o8
ne
jo
o7
ne
jo
o9
ne
jo
o 10
...
...
ne
jo
o 11
ne
jo
o12
ne
t=14
t=13 ne
LogP
LogP
jo
t=14
jo
LogP
t=13
ne
jo
o 14
LogP
ne
jo
o 13
ne
jo
o15
ne
jo
o16
ne
jo
o 17
ne
jo
...
...
o 18
ne
jo
o19
ne
jo
o20
ne
jo
o 21
ne
jo
o 22
ne
jo
o 23
ne
jo
o 24
LogP t=26 jo
LogP t=26 ne
t=25 jo
LogP t=25 ne
ne
jo
o 26
LogP
ne
jo
o 25
7.1
j
o1
7 Přílohy
Příloha A
27
o
n
a
o#3
o_a22
o_a11
n_a33
n_a22
n_a11
a_a33
a_a22
a_a11
o_a33
o_a23
o#2
o_a12
o#1
n_a34
n#3
n_a23
n#2
n_a12
n#1
o_a34
a#3
a_a23
a#2
a_a12
a#1
()#3
()_a23
()#2
()_a12
()#1
()#3
()_a33
()_a22
e
n
()_a33
()_a22
()_a11
()_a11
()_a23
()#2
()_a12
()#1
()_a01
e#3
e_a22
e_a11
n_a33
n_a22
n_a11
e_a33
e_a23
e#2
e_a12
e#1
n_a34
n#3
n_a23
n#2
n_a12
n#1
o1 o2 o3 o4 o5 o6
oN
7.2 Příloha B
28
0
0:1
0:1
1
7
0:1
0:1
0:1
0:1
2
8
14
0:1
0:1
0:1
0:1
0:1
0:1
0:1
3
9
21
15
84
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
4
10
22
16
28
0:1
5
11
0:1
6
12
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
18
24
30
36
87
42
93
99
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
17
23
29
35
86
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
85
0:1
0:1
0:1
92
0:1
0:1
91
0:1
0:1
98
0:1
0:1
0:1
0:1
13
19
25
31
37
88
43
94
49
100
106
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
105
0:1
0:1
112
0:1
0:1
20
26
32
38
89
44
95
50
101
56
107
113
119
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
27
33
39
90
45
96
51
102
57
108
63
114
120
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
34
40
46
97
52
103
58
109
64
115
70
121
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
41
47
53
104
59
110
65
116
71
122
77
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
48
54
60
111
66
117
72
123
78
0:1
126
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
55
61
67
118
73
124
79
0:1
127
133
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
62
68
74
125
80
0:1
128
134
140
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
69
75
81
0:1
129
135
141
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
76
82
0:1
130
136
142
0:1
0:1
0:1
0:1
0:1
0:1
0:1
0:1
83
131
137
143
0:1
0:1
0:1
0:1
0:1
0:1
132
138
144
0:1
0:1
0:1
0:1
139
145
0:1
0:1 146
7.3 Příloha C
29
