hmm_em(1).pdf

(5833 KB) Pobierz
Statystyczna analiza
danych
ukryte modele Markowa,
algorytm EM
Anna Gambin
Instytut Informatyki
Uniwersytet Warszawski
Wednesday, March 19, 14
modele Markowa
Markowa
Ukryte modele
a´ cucha Markowa. B
edziemy sie
e wylacznie za
n
la´cucha Markowa. B
edziemy si
wylacznie zaj-
7 Ukryte modele Markow
cji n
a opisuje pewien uklad , kt´ry w ka˙ dym momencie mo˙ e
o
z
z
l∈Q
l∈Q
l∈Q
w jednym ze stan´
La´ cuch Markowa
ten obserwujemy w
,
ow
n
∈
Q.
Uklad
opisuje pewien uklad
k
suje pewien
= 0,
opisuje
ry w ka˙ dym
e
momencie mo
uklad
.
,
.
kt´
pewien
z
z
,
na
ory w ka˙ d
o
h
n
czasowych
t
sie znajdowa´ tylko w jednym ze stan´w
z
pocz
o
´ cuch Markowa
1,
..
Przyjmujemy, ˙
kt´
atku
k
uklad
c
dnym
poczatkowym
k
Q.
s
o
Uklad ten
momencie
t,
w stanie
ze stan´w
k
∈
. Je´li w danym
obserwujemy
Wednesday, March 19, 14
iemy od
Markowa
la´ cucha Markowa. Bedziemy
definicji
dzialajacymi w dyskretnym cz
n
łańcuch
Markowa
uchami
Markowa dzialajacymi w dyskretnym cza-
la´ cuchami
n
Zaczniemy od
Markowa
cucha Markowa
n
´
b
sko´ czonymi la´ cuchami
definicji
stan´
dzialajacymi
c
edzie sko´czonym zbiorem (zbi´
r
la´
ow).
Pewien
n
n
o
zie sko´ czonym
c sko´czonymi
or
cuchami Markowa
n
n
mowa´ n
zbiorem (zbi´
n
stan´w).
Pewi
o
la´
zbiór
atkowy.
czonym zbiorem
jest
or
stanów
La´ cuch Markowa
(zbi´
Niech
Q
jako
stan
b
pocz
sko´
n
n
r´zniony
=
∅,
poczatkowy. La´ cuch Markowa
je
o ˙
jako
stan
edzie
iony
n
sie.
oz
Niech
Q
=
∅,
bedzie sko´ czonym z
n
k
z przej´´
M
wyr´
k,l
)
k,l∈Q
,
jako
stan
k, l
∈
Q
podaje
n
jest
= (p
˙ niony
kt´ra dla
poczatkowy. La´
o
0
∈
Q
sc
zej´´
M
scia ze
k,l
k
k,l∈Q
do
jest
ra
l.
zniony
l
jako
Q
poda
sc
=
stan
)
0
∈
k
Q
kt´
wyr´ ˙
M
k,
∈
spelnia´
(p
stanu
,
stochastyczna
o dla
musi
stan
c
o
poc
y
p
k,l
przej´
zadany przez
M
= (p
k,l
)
k,l∈Q
, kt´ra
)
przez macierz przej´´
macierz przej´´
M
=
o d
sc
stanu
sc
musi spelni
(p
k,l k
przej´cia ze
M
musi
k
c stochastyczna): dla ka˙ dego
s
stanu
by´
stanu
l. M
do
(tzn. macierz
z
stanu
opodobie´ stwo
p
k,l
przej´cia ze
p
k,l
przej´cia ze stanu
n
prawdopodobie´stwo
stanu
k
s
do
s
n
n. macierz
M
musi by´ stochastyczna):
c
dla ka˙ de
c
z
pujacy warunek (tzn.
acy warunek (tzn. macierz
M
musi
nastepuj
macierz
M
musi by´ stochasty
p
k,l
Q
1.
=
mamy
k
∈
mamy
l∈Q
p
k,l
= 1.
p
k,l
= 1
p
k,l
= 1.
m
k
0
. Je´li w danym momencie
0
t,
s
je sie w stanie poczatkowym
w
0
. Je´li w
t
+ 1
momencie
on
s
najduje
+
e w stanie
k,
to
on
k
momencie
danym
przechodzi
t,
do stanu
l
si
1 przechodzi
ncie
t
do stanu
l
e sie w stanie
k,
to w
k,l
. Podstawowa cecha la´ cucha Markowa jest to,
on
opodobie´ stwem
p
momencie
t
+
jest to,
n
ncucha Markowa
1 przechodzi
n
do stanu
l
a cecha la´
. Podstawowa cecha la´cucha Markowa jest to,
obie´
stan
p
k,l
z
n
n
epny
stwem
zale˙ y tylko od obecnego stanu i nie zale˙ y od warto´ci
t,
z
s
o
zale˙ y tylko od obecnego
warto´
t,
z
nie zale˙ y od
stanu.
nie
z
tan
stanu i
scia do obecnego
stanu i
sci
zale˙ y od warto´ci
t,
z
s
historii doj´
yte modele Markowa
(HMM, od “hidden Markov models”) stanowia
odele Markowa
(HMM, od “hidden Markov models”) stanowia
hidden Markov models”)
Markowa. Niech
Σ
bedzie
a
rozszerzenie definicji la´ cucha
stanowi
Σ
bedzie alfabetem.
alfabetem.
n
rzenie definicji la´ cucha Markowa. Niech
n
rkowa.
n
z
Niech
cuchy
edzie alfabetem.
e komunikowa´ z otoczeniem
my
za´ la´cuchy Markowa mogace sie komunikowa´ z
probabilistyczne
rozwa˙ a´ la´
Σ
b
Markowa mogace si
c otoczeniem
c n
c
wa˙ c
emitowanie
liter
o liter z alfabetu
Σ.
gace
ciag´w
ciag´w
alfabetu
Σ.
przechodzi
Tak
stanu
automaty
c
owanie
sie komunikowa´ z otoczeniem
majac
wiec
l
majac dany HMM
o
z
e
(x) oraz
Tak wiec
do
dany HMM
z prawdopodobie´ stw
n
k
w
k
∈
Q,
wiec maj
Markowa znane s
∈
Σ
z prawdopodobie´ stwem
o
n
nie
Σ.
Tak
∈
Q,
on
ele
ac dany
Σ
HMM
a w literaturze informatycznej r´w
symbol
∈
z
x
n
tu
stanie
k
emituje
emituje on
x
symbol
prawdopodobie´stwem
ukryte modele Markowa
i doj´cia do obecnego stanu.
s
abilistycznych automat´
s
s
ol
x
∈
Σ
z prawdopodobie´ stwem
ow z wyj´ciem.
Je´li chcemy a
n
z wyjściem
k
∈
Q
emitowany byl jaki´ symbol, to musimy przy
s
s
˙
75
o s
stan
Ukryte mod-
og´lno´ci, je´li dopuszczamy sytuacje, ze w pewnyc
ukryty
W
obserwacja
nstwem
p
k,l
.
´
75
prawdopodobie´ stwem, nic nie jest emitowane, to przyj
n
r´wnie˙ pod nazwa
prob-
o
z
˙
my aby w ka˙ dym stanie
x∈Σ
e
k
(x)
≤
1. Przyjmujemy, ze to co daje sie obserw
z
przyja´
c
e
k
(x) =
towane przez uklad, a nie stany wewnetrzne ukladu (s
1.
x∈Σ
wnych stanach (z pewnym
w każdym
zalo˙ enie
Przyklad 7.0.1
Przykladem ukrytego la´ cucha Mar
n
rzyjmujemy slabsze
stanie emitowany jest jakiś symbol
z
kasyno gry, kt´re ma dwa rodzaje ko´ci: uczciwa ko
o
s
serwowa´ to symbole emi-
c
u (stad nazwa “ukryte”).
dopodobie´ stwem 1/6 wyrzuca sie ka˙ da z sze´ciu mo˙
n
z
s
z
Wednesday, March 19, 14
z wikipedii :)
x
— states
y
— possible
observations
a
— state transition
probabilities
b
— output
probabilities
Wednesday, March 19, 14
abilistycznych automat´w z wyj´ciem.
Je´li chcemy aby w ka˙ dym stanie
o
s
s
z
k
∈
Q
emitowany byl jaki´ symbol, to musimy przyja´
s
c
x∈Σ
e
k
(x) = 1.
W og´lno´ci, je´li dopuszczamy sytuacje, ze w pewnych stanach (z pewnym
o s
s
˙
prawdopodobie´ stwem, nic nie jest emitowane, to przyjmujemy slabsze zalo˙ enie
n
z
˙
c
x∈Σ
e
k
(x)
≤
1. Przyjmujemy, ze to co daje sie obserwowa´ to symbole emi-
towane przez uklad, a nie stany wewnetrzne ukladu (stad nazwa “ukryte”).
przykład: nieuczciwe kasyno
Przyklad 7.0.1
Przykladem ukrytego la´ cucha Markowa jest nieuczciwe
n
F -
gry, kt´re ma dwa rodzaje ko´ci: uczciwa kostke do gry (z praw-
uczciwa kostka
s
kasyno
o
dopodobie´ stwem 1/6 wyrzuca sie ka˙ da z sze´ciu mo˙ liwych warto´ci) oraz
n
z
s
z
s
L - fałszywa kostka - szóstka wypada z
nieuczciwa kostke (dla kt´rej prawdopodobie´ stwo wyrzucenia sz´stki wynosi
o
n
o
prawdopodobieństwem
wi
0.5,
1/2, a dla pozostalych liczb 1/10). Tak
=
ec mamy dwa stany: F (uczciwa
kostka) i L (nieuczciwa). Uklad mo˙ e zmienia´ sw´j stan z pewnym praw-
z
c o
pozostałe
ale my stanu
0.1
mo˙ emy zaobserwowa´. Jedynie widzimy
z pr =
nie z
dopodobie´ stwem,
n
c
ciag liczb bedacych wynikiem rzut´w kostka.
o
Mo˙ emy, na przyklad, mie´ do czynienia z nastepujacym modelem:
p
F,F
=
z
c
0.95,
p
L,L
= 0.9,
p
F,L
= 0.05,
p
L,F
= 0.1; ponadto prawdopodobie´ stwo
n
emisji jest zdefiniowane nastepujaco:
e
F
(x) = 1/6 dla
x
∈
{1,
2, 3, 4, 5, 6}
oraz
e
L
(6) = 0.5 i
e
L
(x) = 0.1 dla
x
∈
{1,
2, 3, 4, 5}
2
Przyklad 7.0.2 (Wyspy CpG)
Wiadomo, ze w ludzkim genomie, je´li po-
˙
s
jawi sie para nukleotyd´w CG (tzn G pojawia sie tu˙ za C w jednej nici, w
o
z
kierunku
Wednesday, March 19, 14
5’ do 3’), to nukleotyd C zwykle ulega zmianie (pod wplywem mety-

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin