Baum – Welchův algoritmus - Baum–Welch algorithm - Wikipedia

v elektrotechnika, počítačová věda, statistické výpočty a bioinformatika, Baum – Welchův algoritmus je zvláštní případ EM algoritmus slouží k nalezení neznámých parametrů a skrytý Markovův model (HMM). Využívá algoritmus dopředu-dozadu k výpočtu statistik pro krok očekávání.

Dějiny

Algoritmus Baum – Welch byl pojmenován podle svých vynálezců Leonard E. Baum a Lloyd R. Welch. Algoritmus a modely Skrytého Markova byly poprvé popsány v sérii článků Bauma a jeho vrstevníků z Institut pro obranné analýzy na konci 60. a začátku 70. let.^[1] Jednou z prvních hlavních aplikací HMM byla v oblasti zpracování řeči.^[2] V 80. letech se HMM ukázaly jako užitečný nástroj při analýze biologických systémů a informací, zejména genetická informace.^[3] Od té doby se staly důležitým nástrojem pravděpodobnostního modelování genomových sekvencí.^[4]

Popis

A skrytý Markovův model popisuje společnou pravděpodobnost kolekce „skrytý "a pozorované diskrétní náhodné proměnné. Spoléhá se na předpoklad, že i-tá skrytá proměnná vzhledem k (i - 1) -tá skrytá proměnná je nezávislá na předchozích skrytých proměnných a aktuální proměnné pozorování závisí pouze na aktuálním skrytém stavu.

Algoritmus Baum – Welch používá k vyhledání dobře známého algoritmu EM maximální pravděpodobnost odhad parametrů skrytého Markovova modelu vzhledem k sadě pozorovaných vektorů rysů.

Nechat ${ displaystyle X_ {t}}$ být diskrétní skrytá náhodná proměnná s ${ displaystyle N}$ možné hodnoty (tj. předpokládáme, že existují ${ displaystyle N}$ státy celkem). Předpokládáme ${ displaystyle P (X_ {t} střední X_ {t-1})}$ je nezávislá na čase ${ displaystyle t}$ , což vede k definici časově nezávislé stochastické přechodové matice

{ displaystyle A = {a_ {ij} } = P (X_ {t} = j mid X_ {t-1} = i).}

Počáteční rozdělení stavu (tj. Kdy ${ displaystyle t = 1}$ ) je dána

{ displaystyle pi _ {i} = P (X_ {1} = i).}

Pozorovací proměnné ${ displaystyle Y_ {t}}$ může vzít jednu z ${ displaystyle K}$ možné hodnoty. Rovněž předpokládáme, že pozorování dané „skrytým“ stavem je nezávislé na čase. Pravděpodobnost určitého pozorování ${ displaystyle y_ {i}}$ v čase ${ displaystyle t}$ pro stát ${ displaystyle X_ {t} = j}$ je dána

{ displaystyle b_ {j} (y_ {i}) = P (Y_ {t} = y_ {i} střední X_ {t} = j).}

S přihlédnutím ke všem možným hodnotám ${ displaystyle Y_ {t}}$ a ${ displaystyle X_ {t}}$ , získáme ${ displaystyle N krát K}$ matice ${ displaystyle B = {b_ {j} (y_ {i}) }}$ kde ${ displaystyle b_ {j}}$ patří do všech možných stavů a ${ displaystyle y_ {i}}$ patří ke všem pozorováním.

Sekvence pozorování je dána vztahem ${ displaystyle Y = (Y_ {1} = y_ {1}, Y_ {2} = y_ {2}, ldots, Y_ {T} = y_ {T})}$ .

Takto můžeme popsat skrytý Markovův řetězec ${ displaystyle theta = (A, B, pi)}$ . Algoritmus Baum – Welch najde lokální maximum pro ${ displaystyle theta ^ {*} = operatorname {arg , max} _ { theta} P (Y mid theta)}$ (tj. parametry HMM ${ displaystyle theta}$ které maximalizují pravděpodobnost pozorování).^[5]

Algoritmus

Soubor ${ displaystyle theta = (A, B, pi)}$ s náhodnými počátečními podmínkami. Mohou být také nastaveny pomocí předběžných informací o parametrech, pokud jsou k dispozici; to může zrychlit algoritmus a také jej nasměrovat k požadovanému místnímu maximu.

Předávací řízení

Nechat ${ displaystyle alpha _ {i} (t) = P (Y_ {1} = y_ {1}, ldots, Y_ {t} = y_ {t}, X_ {t} = i mid theta)}$ , pravděpodobnost pozorování pozorování ${ displaystyle y_ {1}, y_ {2}, ldots, y_ {t}}$ a být ve stavu ${ displaystyle i}$ v čase ${ displaystyle t}$ . Toto se nachází rekurzivně:

${ displaystyle alpha _ {i} (1) = pi _ {i} b_ {i} (y_ {1}),}$
${ displaystyle alpha _ {i} (t + 1) = b_ {i} (y_ {t + 1}) součet _ {j = 1} ^ {N} alpha _ {j} (t) a_ { ji}.}$

Protože tato řada konverguje exponenciálně na nulu, algoritmus bude numericky podtečen pro delší sekvence.^[6] Tomu se však lze v mírně upraveném algoritmu vyhnout změnou měřítka ${ displaystyle alpha}$ dopředu a ${ displaystyle beta}$ v zpětném postupu níže.

Zpětný postup

Nechat ${ displaystyle beta _ {i} (t) = P (Y_ {t + 1} = y_ {t + 1}, ldots, Y_ {T} = y_ {T} střední X_ {t} = i, theta)}$ to je pravděpodobnost ukončení dílčí sekvence ${ displaystyle y_ {t + 1}, ldots, y_ {T}}$ daný počáteční stav ${ displaystyle i}$ v čase ${ displaystyle t}$ . Počítáme ${ displaystyle beta _ {i} (t)}$ tak jako,

${ displaystyle beta _ {i} (T) = 1,}$
${ displaystyle beta _ {i} (t) = součet _ {j = 1} ^ {N} beta _ {j} (t + 1) a_ {ij} b_ {j} (y_ {t + 1 }).}$

Aktualizace

Nyní můžeme vypočítat dočasné proměnné podle Bayesovy věty:

{ displaystyle gamma _ {i} (t) = P (X_ {t} = i mid Y, theta) = { frac {P (X_ {t} = i, Y mid theta)} { P (Y mid theta)}} = { frac { alpha _ {i} (t) beta _ {i} (t)} { sum _ {j = 1} ^ {N} alpha _ {j} (t) beta _ {j} (t)}},}

což je pravděpodobnost, že budete ve stavu ${ displaystyle i}$ v čase ${ displaystyle t}$ vzhledem k pozorované sekvenci ${ displaystyle Y}$ a parametry ${ displaystyle theta}$

{ displaystyle xi _ {ij} (t) = P (X_ {t} = i, X_ {t + 1} = j mid Y, theta) = { frac {P (X_ {t} = i , X_ {t + 1} = j, Y mid theta)} {P (Y mid theta)}} = { frac { alpha _ {i} (t) a_ {ij} beta _ { j} (t + 1) b_ {j} (y_ {t + 1})} { sum _ {k = 1} ^ {N} sum _ {w = 1} ^ {N} alpha _ {k } (t) a_ {kw} beta _ {w} (t + 1) b_ {w} (y_ {t + 1})}}}}

což je pravděpodobnost, že budete ve stavu ${ displaystyle i}$ a ${ displaystyle j}$ občas ${ displaystyle t}$ a ${ displaystyle t + 1}$ vzhledem k pozorované sekvenci ${ displaystyle Y}$ a parametry ${ displaystyle theta}$ .

Jmenovatelé ${ displaystyle gamma _ {i} (t)}$ a ${ displaystyle xi _ {ij} (t)}$ jsou stejní ; představují pravděpodobnost provedení pozorování ${ displaystyle Y}$ vzhledem k parametrům ${ displaystyle theta}$ .

Parametry skrytého Markovova modelu ${ displaystyle theta}$ nyní lze aktualizovat:

${ displaystyle pi _ {i} ^ {*} = gamma _ {i} (1),}$

což je očekávaná frekvence strávená ve stavu ${ displaystyle i}$ v čase ${ displaystyle 1}$ .

${ displaystyle a_ {ij} ^ {*} = { frac { sum _ {t = 1} ^ {T-1} xi _ {ij} (t)} { sum _ {t = 1} ^ {T-1} gamma _ {i} (t)}},}$

což je očekávaný počet přechodů ze stavu i do stavu j ve srovnání s očekávaným celkovým počtem přechodů od státu i. Abychom objasnili, počet přechodů od státu i neznamená přechody do jiného stavu j, ale do kteréhokoli státu včetně sebe samého. To odpovídá počtu stavů i je sledován v pořadí od t = 1 až t = T − 1.

${ displaystyle b_ {i} ^ {*} (v_ {k}) = { frac { sum _ {t = 1} ^ {T} 1_ {y_ {t} = v_ {k}} gamma _ { i} (t)} { sum _ {t = 1} ^ {T} gamma _ {i} (t)}},}$

kde

{ displaystyle 1_ {y_ {t} = v_ {k}} = { begin {cases} 1 & { text {if}} y_ {t} = v_ {k}, 0 & { text {jinak}} end {případy}}}

je indikátorová funkce a ${ displaystyle b_ {i} ^ {*} (v_ {k})}$ je očekávaný počet opakování výstupních pozorování ${ displaystyle v_ {k}}$ ve stavu ${ displaystyle i}$ přes očekávaný celkový počet případů ve stavu ${ displaystyle i}$ .

Tyto kroky se nyní opakují iterativně až do požadované úrovně konvergence.

Poznámka: Je možné over-fit konkrétní datovou sadu. To znamená, ${ displaystyle P (Y mid theta _ { text {final}})> P (Y mid theta _ { text {true}})}$ . Algoritmus také dělá ne zaručit globální maximum.

Více sekvencí

Algoritmus popsaný doposud předpokládá jedinou pozorovanou sekvenci ${ displaystyle Y = y_ {1}, ldots, y_ {N}}$ . V mnoha situacích je však pozorováno několik sekvencí: ${ displaystyle Y_ {1}, ldots, Y_ {R}}$ . V tomto případě musí být při aktualizaci parametrů použity informace ze všech sledovaných sekvencí ${ displaystyle A}$ , ${ displaystyle pi}$ , a ${ displaystyle b}$ . Za předpokladu, že jste vypočítali ${ displaystyle gamma _ {ir} (t)}$ a ${ displaystyle xi _ {ijr} (t)}$ pro každou sekvenci ${ displaystyle y_ {1, r}, ldots, y_ {N_ {r}, r}}$ , parametry lze nyní aktualizovat:

${ displaystyle pi _ {i} ^ {*} = { frac { sum _ {r = 1} ^ {R} gamma _ {ir} (1)} {R}}}$
${ displaystyle a_ {ij} ^ {*} = { frac { sum _ {r = 1} ^ {R} sum _ {t = 1} ^ {T-1} xi _ {ijr} (t )} { sum _ {r = 1} ^ {R} sum _ {t = 1} ^ {T-1} gamma _ {ir} (t)}},}$
${ displaystyle b_ {i} ^ {*} (v_ {k}) = { frac { sum _ {r = 1} ^ {R} sum _ {t = 1} ^ {T} 1_ {y_ { tr} = v_ {k}} gamma _ {ir} (t)} { sum _ {r = 1} ^ {R} sum _ {t = 1} ^ {T} gamma _ {ir} ( t)}},}$

kde

{ displaystyle 1_ {y_ {tr} = v_ {k}} = { begin {cases} 1 & { text {if}} y_ {t, r} = v_ {k}, 0 & { text {jinak }} end {cases}}}

je indikátorová funkce

Příklad

Předpokládejme, že máme kuře, ze kterého každý den v poledne sbíráme vejce. To, zda kuře snášelo vejce ke sběru nebo ne, závisí na některých neznámých faktorech, které jsou skryté. Můžeme však (pro zjednodušení) předpokládat, že existují pouze dva státy, které určují, zda kuře klade vejce. Nyní neznáme stav v počátečním počátečním bodě, neznáme pravděpodobnosti přechodu mezi těmito dvěma stavy a neznáme pravděpodobnost, že kuře položí vejce dané daným stavem.^[7]^[8] Pro začátek nejprve uhodneme přechodovou a emisní matici.

Přechod
	Stát 1	Stát 2
Stát 1	0.5	0.5
Stát 2	0.3	0.7

Emise
	Žádná vejce	Vejce
Stát 1	0.3	0.7
Stát 2	0.8	0.2

Počáteční
Stát 1	0.2
Stát 2	0.8

Poté provedeme sadu pozorování (E = vejce, N = žádná vejce): N, N, N, N, N, E, E, N, N, N

To nám dává sadu pozorovaných přechodů mezi dny: NN, NN, NN, NN, NE, EE, EN, NN, NN

Dalším krokem je odhad nové matice přechodu. Například pravděpodobnost posloupnosti NN a stavu ${ displaystyle S_ {1}}$ pak ${ displaystyle S_ {2}}$ je dán následujícím, ${ displaystyle P (S_ {1}) * P (N | S_ {1}) * P (S_ {1} rightarrow S_ {2}) * P (N | S_ {2}).}$

Pozorovaná sekvence	Pravděpodobnost posloupnosti a stavu je ${ displaystyle S_ {1}}$ pak ${ displaystyle S_ {2}}$	Nejvyšší pravděpodobnost pozorování této sekvence
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
NE	0.006 = 0.2 * 0.3 * 0.5 * 0.2	0.1344	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {1}}$
EE	0.014 = 0.2 * 0.7 * 0.5 * 0.2	0.0490	${ displaystyle S_ {1}}$ , ${ displaystyle S_ {1}}$
EN	0.056 = 0.2 * 0.7 * 0.5 * 0.8	0.0896	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
Celkový	0.22	2.4234

Nový odhad pro ${ displaystyle S_ {1}}$ na ${ displaystyle S_ {2}}$ přechod je nyní ${ displaystyle { frac {0.22} {2.4234}} = 0,0908}$ (v následujících tabulkách označováno jako „Pseudo pravděpodobnosti“). Poté vypočítáme ${ displaystyle S_ {2}}$ na ${ displaystyle S_ {1}}$ , ${ displaystyle S_ {2}}$ na ${ displaystyle S_ {2}}$ a ${ displaystyle S_ {1}}$ na ${ displaystyle S_ {1}}$ pravděpodobnosti přechodu a normalizace, takže se přidají k 1. To nám dává aktualizovanou matici přechodu:

Stará přechodová matice
	Stát 1	Stát 2
Stát 1	0.5	0.5
Stát 2	0.3	0.7

Nová přechodová matice (pseudopravděpodobnosti)
	Stát 1	Stát 2
Stát 1	0.0598	0.0908
Stát 2	0.2179	0.9705

Nová přechodová matice (po normalizaci)
	Stát 1	Stát 2
Stát 1	0.3973	0.6027
Stát 2	0.1833	0.8167

Dále chceme odhadnout novou emisní matici,

Pozorovaná sekvence	Nejvyšší pravděpodobnost pozorování této sekvence pokud se předpokládá, že E pochází ${ displaystyle S_ {1}}$		Nejvyšší pravděpodobnost pozorování této sekvence
NE	0.1344	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {1}}$	0.1344	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {1}}$
EE	0.0490	${ displaystyle S_ {1}}$ , ${ displaystyle S_ {1}}$	0.0490	${ displaystyle S_ {1}}$ , ${ displaystyle S_ {1}}$
EN	0.0560	${ displaystyle S_ {1}}$ , ${ displaystyle S_ {2}}$	0.0896	${ displaystyle S_ {2}}$ , ${ displaystyle S_ {2}}$
Celkový	0.2394		0.2730

Nový odhad pro E pocházející z ${ displaystyle S_ {1}}$ emise je nyní ${ displaystyle { frac {0.2394} {0.2730}} = 0,8769}$ .

To nám umožňuje vypočítat emisní matici, jak je popsáno výše v algoritmu, sečtením pravděpodobností pro příslušné pozorované sekvence. Potom opakujeme, pokud N pochází ${ displaystyle S_ {1}}$ a kdyby N a E pocházely ${ displaystyle S_ {2}}$ a normalizovat.

Stará emisní matice
	Žádná vejce	Vejce
Stát 1	0.3	0.7
Stát 2	0.8	0.2

Nová emisní matice (odhady)
	Žádná vejce	Vejce
Stát 1	0.0404	0.8769
Stát 2	1.0000	0.7385

Nová emisní matice (po normalizaci)
	Žádná vejce	Vejce
Stát 1	0.0441	0.9559
Stát 2	0.5752	0.4248

Pro odhad počátečních pravděpodobností předpokládáme, že všechny sekvence začínají skrytým stavem ${ displaystyle S_ {1}}$ a vypočítat nejvyšší pravděpodobnost a poté opakovat pro ${ displaystyle S_ {2}}$ . Znovu se pak normalizujeme, abychom dostali aktualizovaný počáteční vektor.

Nakonec tyto kroky opakujeme, dokud se výsledné pravděpodobnosti uspokojivě neshodují.

Aplikace

Rozpoznávání řeči

Skryté Markovovy modely byly poprvé použity pro rozpoznávání řeči od James K. Baker v roce 1975.^[9] Kontinuální rozpoznávání řeči probíhá podle následujících kroků, modelovaných HMM. Analýza prvků se nejprve provede na časových a / nebo spektrálních vlastnostech řečového signálu. Tím vznikne pozorovací vektor. Funkce je poté porovnána se všemi sekvencemi jednotek rozpoznávání řeči. Tyto jednotky by mohly být fonémy, slabiky nebo jednotky celého slova. K omezení vyšetřovaných cest je použit systém dekódování lexikonu, takže jsou zkoumána pouze slova v lexikonu (slovníku slov) systému. Podobně jako při dekódování lexikonu je systémová cesta dále omezována pravidly gramatiky a syntaxe. Nakonec je použita sémantická analýza a systém vydá rozpoznanou promluvu. Omezením mnoha aplikací HMM na rozpoznávání řeči je, že aktuální stav závisí pouze na stavu v předchozím časovém kroku, což je pro řeč nerealistické, protože závislosti často trvají několik časových kroků.^[10] Algoritmus Baum – Welch má také rozsáhlé aplikace při řešení HMM používaných v oblasti syntézy řeči.^[11]

Kryptoanalýza

Algoritmus Baum – Welch se často používá k odhadu parametrů HMM v dešifrování skrytých nebo hlučných informací a následně se často používá v dešifrování. V oblasti zabezpečení dat by pozorovatel chtěl extrahovat informace z datového proudu, aniž by znal všechny parametry přenosu. To může zahrnovat reverzní inženýrství a kodér kanálu.^[12] HMM a v důsledku toho algoritmus Baum – Welch byly také použity k identifikaci mluvených frází v šifrovaných hovorech VoIP.^[13] Kromě toho je kryptoanalýza HMM důležitým nástrojem pro automatizované vyšetřování dat časování mezipaměti. Umožňuje automatické zjištění stavu kritického algoritmu, například klíčových hodnot.^[14]

Aplikace v bioinformatice

Hledání genů

Prokaryotický

The ZÁBLESK Software (Gene Locator a Interpolated Markov ModelER) byl brzy hledání genů program používaný k identifikaci kódovacích oblastí v systému Windows prokaryotický DNA.^[15]^[16] GLIMMER používá k identifikaci interpolovaných Markovových modelů (IMM) kódující oblasti a odlišit je od nekódující DNA. Ukázalo se, že nejnovější verze (GLIMMER3) se zvýšila specifičnost a přesnost ve srovnání s jeho předchůdci, pokud jde o predikci iniciačních míst translace, což ukazuje průměrnou 99% přesnost lokalizace 3 'míst ve srovnání s potvrzenými geny u prokaryot.^[17]

Eukaryotický

The GENSCAN webserver je lokalizátor genů schopný analyzovat eukaryotický sekvence až jeden milion párů bází (1 Mbp) dlouhý.^[18] GENSCAN využívá obecný nehomogenní, tři periodický, pátý řád Markovův model oblastí kódujících DNA. Kromě toho tento model vysvětluje rozdíly v hustotě a struktuře genů (jako jsou délky intronů), které se vyskytují u různých isochores. Zatímco většina integrovaného softwaru pro vyhledávání genů (v době vydání GENSCANů) předpokládala, že vstupní sekvence obsahují přesně jeden gen, GENSCAN řeší obecný případ, kdy jsou přítomny částečné, úplné nebo více genů (nebo dokonce žádný gen).^[19] Ukázalo se, že GENSCAN přesně předpovídá umístění exonu s 90% přesností a 80% specificitou ve srovnání s anotovanou databází.^[20]

Detekce změny počtu kopií

Varianty počtu kopií (CNV) jsou hojnou formou variace struktury genomu u lidí. K přiřazení chromozomálních oblastí k sedmi odlišným stavům: neovlivněné oblasti, delece, duplikace a čtyři přechodové stavy byla použita diskrétní dvojrozměrná HMM (dbHMM). Řešení tohoto modelu pomocí Baum-Welch prokázalo schopnost předpovědět umístění bodu zlomu CNV na přibližně 300 bp od mikropole experimenty.^[21] Tato velikost rozlišení umožňuje přesnější korelace mezi různými CNV a napříč populacemi než bylo dříve možné, což umožňuje studovat frekvence populace CNV. Rovněž prokázala vzor přímé dědičnosti pro konkrétní CNV.

Implementace

Accord.NET v C#
ghmm C knihovna s Krajta vazby, které podporují diskrétní i kontinuální emise.
HMMBase balíček pro Julie.
Funkce HMMFit v RHmm balíček pro R.
hmmtrain v MATLAB

Viz také

Reference

^ Rabiner, Lawrence. „First Hand: The Hidden Markov Model“. Síť IEEE Global History. Citováno 2. října 2013.
^ Jelinek, Frederick; Bahl, Lalit R .; Mercer, Robert L. (květen 1975). "Návrh lingvistického statistického dekodéru pro rozpoznávání spojité řeči". Transakce IEEE na teorii informací. 21 (3): 250–6. doi:10.1109 / tit.1975.1055384.
^ Bishop, Martin J .; Thompson, Elizabeth A. (20. července 1986). Msgstr "Zarovnání sekvence DNA s maximální pravděpodobností". Journal of Molecular Biology. 190 (2): 159–65. doi:10.1016/0022-2836(86)90289-5. PMID 3641921.
^ Durbin, Richard (23. dubna 1998). Analýza biologické sekvence: Pravděpodobnostní modely proteinů a nukleových kyselin. Cambridge University Press. ISBN 978-0-521-62041-3.
^ Bilmes, Jeff A. (1998). Gentle Tutorial of the EM Algorithm and its application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Berkeley, CA: International Computer Science Institute. s. 7–13.
^ Rabiner, Lawrence (únor 1989). „Výukový program ke skrytým Markovovým modelům a vybraným aplikacím v rozpoznávání řeči“ (PDF). Sborník IEEE. Citováno 29. listopadu 2019.
^ „Aplikace Baum-Welch a HMM“ (PDF). Johns Hopkins Bloomberg School of Public Health. Citováno 11. října 2019.
^ Frazzoli, Emilio. „Úvod do skrytých Markovových modelů: Baum-Welchův algoritmus“ (PDF). Aeronautics and Astronautics, Massachusetts Institute of Technology. Citováno 2. října 2013.
^ Baker, James K. (1975). „Systém DRAGON - přehled“. Transakce IEEE týkající se akustiky, řeči a zpracování signálu. 23: 24–29. doi:10.1109 / TASSP.1975.1162650.
^ Rabiner, Lawrence (únor 1989). "Výukový program pro skryté Markovovy modely a vybrané aplikace v rozpoznávání řeči". Sborník IEEE. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. doi:10.1109/5.18626.
^ Tokuda, Keiichi; Yoshimura, Takayoshi; Masuko, Takashi; Kobayashi, Takao; Kitamura, Tadashi (2000). "Algoritmy generování parametrů řeči pro syntézu řeči založenou na HMM". Mezinárodní konference IEEE o akustice, řeči a zpracování signálu. 3.
^ Dingel, Janis; Hagenauer, Joachim (24. června 2007). "Odhad parametrů konvolučního kodéru z hlučných pozorování". IEEE International Symposium on Information Theory.
^ Wright, Charles; Ballard, Lucas; Coull, Scott; Monrose, Fabian; Masson, Gerald (2008). "Najděte si mě, pokud můžete: Odhalování mluvených frází v šifrovaných konverzacích VoIP". IEEE International Symposium on Security and Privacy.
^ Brumley, Bob; Hakala, Risto (2009). Útoky na šablonu časování mezipaměti. Pokroky v kryptografii. Přednášky z informatiky. 5912. 667–684. doi:10.1007/978-3-642-10366-7_39. ISBN 978-3-642-10365-0.
^ Salzberg, Steven; Delcher, Arthur L .; Kasif, Simon; White, Owen (1998). „Mikrobiální identifikace genů pomocí interpolovaných Markovových modelů“. Výzkum nukleových kyselin. 26 (2): 544–548. doi:10.1093 / nar / 26.2.544. PMC 147303. PMID 9421513.
^ „Glimmer: Microbial Gene-Finding System“. Univerzita Johna Hopkinse - Centrum pro výpočetní biologii.
^ Delcher, Arthur; Bratke, Kirsten A .; Powers, Edwin C .; Salzberg, Steven L. (2007). „Identifikace bakteriálních genů a DNA endosymbiontu pomocí Glimmeru“. Bioinformatika. 23 (6): 673–679. doi:10.1093 / bioinformatika / btm009. PMC 2387122. PMID 17237039.
^ Burge, Christopher. „Webový server GENSCAN na MIT“. Archivovány od originál dne 6. září 2013. Citováno 2. října 2013.
^ Burge, Chris; Karlin, Samuel (1997). "Predikce úplných genových struktur v lidské genomové DNA". Journal of Molecular Biology. 268 (1): 78–94. CiteSeerX 10.1.1.115.3107. doi:10.1006 / jmbi.1997.0951. PMID 9149143.
^ Burge, Christopher; Karlin, Samuel (1998). "Nalezení genů v genomové DNA". Aktuální názor na strukturní biologii. 8 (3): 346–354. doi:10.1016 / s0959-440x (98) 80069-9. PMID 9666331.
^ Korbel, Jan; Urban, Alexander; Grubert, Fabien; Du, Jiang; Royce, Thomas; Starr, Peter; Zhong, Guoneng; Emanuel, Beverly; Weissman, Sherman; Snyder, Michael; Gerstein, Marg (12. června 2007). "Systematická predikce a validace hraničních hodnot spojených s variacemi počtu kopií v lidském genomu". Sborník Národní akademie věd Spojených států amerických. 104 (24): 10110–5. Bibcode:2007PNAS..10410110K. doi:10.1073 / pnas.0703834104. PMC 1891248. PMID 17551006.

externí odkazy

Komplexní přehled metod a softwaru HMM v bioinformatice - Profily skrytých modelů Markov
Časné publikace HMM od Bauma:
Shannonova přednáška Welcha, která hovoří o tom, jak lze algoritmus efektivně implementovat:
- Skryté Markovovy modely a Baum-Welchův algoritmus Newsletter IEEE Information Theory Society, prosinec 2003.
Alternativou k algoritmu Baum – Welch, algoritmu Viterbi Path Counting:
- Davis, Richard I.A .; Lovell, Brian C .; „Porovnání a vyhodnocení tréninkových algoritmů souboru HMM pomocí kritérií vlaku a testu a počtu podmínek“, Pattern Analysis and Applications, roč. 6, č. 4, s. 327–336, 2003.
Interaktivní tabulka pro výuku algoritmu dopředu-dozadu (tabulka a článek s podrobným návodem)
Formální derivace algoritmu Baum – Welch
Implementace algoritmu Baum – Welch

[1] Rabiner, Lawrence. „First Hand: The Hidden Markov Model“. Síť IEEE Global History. Citováno 2. října 2013.

[2] Jelinek, Frederick; Bahl, Lalit R .; Mercer, Robert L. (květen 1975). "Návrh lingvistického statistického dekodéru pro rozpoznávání spojité řeči". Transakce IEEE na teorii informací. 21 (3): 250–6. doi:10.1109 / tit.1975.1055384.

[3] Bishop, Martin J .; Thompson, Elizabeth A. (20. července 1986). Msgstr "Zarovnání sekvence DNA s maximální pravděpodobností". Journal of Molecular Biology. 190 (2): 159–65. doi:10.1016/0022-2836(86)90289-5. PMID 3641921.

[Durbin1998-4] Durbin, Richard (23. dubna 1998). Analýza biologické sekvence: Pravděpodobnostní modely proteinů a nukleových kyselin. Cambridge University Press. ISBN 978-0-521-62041-3.

[5] Bilmes, Jeff A. (1998). Gentle Tutorial of the EM Algorithm and its application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Berkeley, CA: International Computer Science Institute. s. 7–13.

[6] Rabiner, Lawrence (únor 1989). „Výukový program ke skrytým Markovovým modelům a vybraným aplikacím v rozpoznávání řeči“ (PDF). Sborník IEEE. Citováno 29. listopadu 2019.

[7] „Aplikace Baum-Welch a HMM“ (PDF). Johns Hopkins Bloomberg School of Public Health. Citováno 11. října 2019.

[8] Frazzoli, Emilio. „Úvod do skrytých Markovových modelů: Baum-Welchův algoritmus“ (PDF). Aeronautics and Astronautics, Massachusetts Institute of Technology. Citováno 2. října 2013.

[9] Baker, James K. (1975). „Systém DRAGON - přehled“. Transakce IEEE týkající se akustiky, řeči a zpracování signálu. 23: 24–29. doi:10.1109 / TASSP.1975.1162650.

[10] Rabiner, Lawrence (únor 1989). "Výukový program pro skryté Markovovy modely a vybrané aplikace v rozpoznávání řeči". Sborník IEEE. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. doi:10.1109/5.18626.

[11] Tokuda, Keiichi; Yoshimura, Takayoshi; Masuko, Takashi; Kobayashi, Takao; Kitamura, Tadashi (2000). "Algoritmy generování parametrů řeči pro syntézu řeči založenou na HMM". Mezinárodní konference IEEE o akustice, řeči a zpracování signálu. 3.

[12] Dingel, Janis; Hagenauer, Joachim (24. června 2007). "Odhad parametrů konvolučního kodéru z hlučných pozorování". IEEE International Symposium on Information Theory.

[13] Wright, Charles; Ballard, Lucas; Coull, Scott; Monrose, Fabian; Masson, Gerald (2008). "Najděte si mě, pokud můžete: Odhalování mluvených frází v šifrovaných konverzacích VoIP". IEEE International Symposium on Security and Privacy.

[14] Brumley, Bob; Hakala, Risto (2009). Útoky na šablonu časování mezipaměti. Pokroky v kryptografii. Přednášky z informatiky. 5912. 667–684. doi:10.1007/978-3-642-10366-7_39. ISBN 978-3-642-10365-0.

[GLIMMER_paper-15] Salzberg, Steven; Delcher, Arthur L .; Kasif, Simon; White, Owen (1998). „Mikrobiální identifikace genů pomocí interpolovaných Markovových modelů“. Výzkum nukleových kyselin. 26 (2): 544–548. doi:10.1093 / nar / 26.2.544. PMC 147303. PMID 9421513.

[GLIMMER_web-16] „Glimmer: Microbial Gene-Finding System“. Univerzita Johna Hopkinse - Centrum pro výpočetní biologii.

[17] Delcher, Arthur; Bratke, Kirsten A .; Powers, Edwin C .; Salzberg, Steven L. (2007). „Identifikace bakteriálních genů a DNA endosymbiontu pomocí Glimmeru“. Bioinformatika. 23 (6): 673–679. doi:10.1093 / bioinformatika / btm009. PMC 2387122. PMID 17237039.

[18] Burge, Christopher. „Webový server GENSCAN na MIT“. Archivovány od originál dne 6. září 2013. Citováno 2. října 2013.

[19] Burge, Chris; Karlin, Samuel (1997). "Predikce úplných genových struktur v lidské genomové DNA". Journal of Molecular Biology. 268 (1): 78–94. CiteSeerX 10.1.1.115.3107. doi:10.1006 / jmbi.1997.0951. PMID 9149143.

[20] Burge, Christopher; Karlin, Samuel (1998). "Nalezení genů v genomové DNA". Aktuální názor na strukturní biologii. 8 (3): 346–354. doi:10.1016 / s0959-440x (98) 80069-9. PMID 9666331.

[21] Korbel, Jan; Urban, Alexander; Grubert, Fabien; Du, Jiang; Royce, Thomas; Starr, Peter; Zhong, Guoneng; Emanuel, Beverly; Weissman, Sherman; Snyder, Michael; Gerstein, Marg (12. června 2007). "Systematická predikce a validace hraničních hodnot spojených s variacemi počtu kopií v lidském genomu". Sborník Národní akademie věd Spojených států amerických. 104 (24): 10110–5. Bibcode:2007PNAS..10410110K. doi:10.1073 / pnas.0703834104. PMC 1891248. PMID 17551006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]