Modelos de Markov Não
Observáveis e Gramáticas
Estocásticas Regulares
Ana L. N. Fred
Instituto Superior Técnico
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMM
vs
SFSG:
(Hidden Markov Models) (Stochastic Finite State Grammars)
Modelos de Markov Não Gramáticas Estocásticas de Estados
Finitos
Observáveis
•São instâncias de uma classe mais geral de modelos:
redes estocásticas de estados finitos (Stochastic
Finite-State Networks)
•conj. finito de estados
•distribuições de probabilidade que definem
transições entre estados e a produção de
sequências finitas de observações
•baseados na teoria dos processos estocásticos,
as suas origens são diferentes:
•teoria da informação - modelos de Markov
•extensões da teoria das linguagens formais
•gramáticas estocásticas regulares
•autómatos estocásticos de estados
finitos
•Ambos geram uma sequência interna (nãoobservável) de símbolos (estados) e uma sequência
externa (observável) de símbolos usando regras
probabilísticas.
•Assumem fomalismos diferentes e
distintos de inferência.
mecanismos
•A probabilidade de uma sequência é calculada de
uma forma semelhante
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Relações formais entre modelos no
contexto das linguagens geradas
Σ - alfabeto
Σ = {a, b, c}
Σ* - concatenação de símbolos em Σ
aabbacbabbacc
aa
bba
L ⊆ Σ* - linguagem
SL = ( L, p)
linguagem estocástica
L ⊆ Σ*
p : Σ* → [0,1]
se x ∉ L
p( x ) = 0
∑
x∈L
p( x ) = 1
WL - weighted language
SRL = ( L, p) tal que L é regular
(= aceite por um autómato de estados finitos)
- linguagem estocástica regular
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Modelos de Markov
HMM
H = (Q, Σ, A, B, π )
Q = {qi } ≡ conjunto finito de estados
Σ ≡ conjunto de símbolos de observação
A : Q × Q → [0,1] ≡ matriz de probabilidade de transição
∑q′∈Q A(q,q′) = 1 , ∀q∈Q
B : Q × Σ → [0,1] ≡ distribuição de probabilidade de observação de símbolo
∑a∈Σ B(q,a) = 1 , ∀q∈Q
π : Q → [0,1] ≡ distribuição de probabilidade do estado inicial
∑q∈Q π(q) = 1
Probabilidade de observação da sequência
x , x ∈Σ
( x) = ∑ π ( q ) B ( q , x ) A( q , q ) B ( q , x )
A(q , q )B(q , x )
x = x1 , x2
p( x | H ) = pH
∑
x1
i
1
q1
Proposição:
n
1
qn
1
1
n −1
n
2
2
n
2
n
Dado um HMM definido em Σ, pH define uma
distribuição de probabilidade em Σ n para cada
n ∈ N.
x ∈Σ pH ( x1
n
n
x ) =
n
π (q ) B(q , x ) A(q , q ) B(q , x )
∑
∑
A(q , q )B(q , x )
= ∑ π (q )(∑ B(q , x )A(q , q )(∑ (∑ B(q , x )) ))
= ∑ π (q )∑ A(q , q )( (∑ A(q , q )) ))
=
1
x1
xn q1
q1
qn
1
qn
1
n −1
1
1
1
1
n
q1
1
=1
Ana L. N. Fred
2
n
n −1
2
2
n
x2
1
q2
2
n
x1
1
2
n
xn
n
qn
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMM usando restrições temporais
LRHMM (left-to-right HMM)
q
q
0
q
1
q
2
n
LRHMM - modelo esquerda-direita
H LR = (Q, Σ, A, B, qi , q f )
Q = {qi } ≡ conjunto finito de estados ordenados tal que
se q < q′ então A(q′, q) = 0
qi ≡ estado inicial
q f ≡ estado final
*
HLR define uma função p HLR : Σ → [0,1]
Probabilidade de observação da sequência
x , x ∈Σ
B (q , x ) A( q , q ) B (q , x )
A(q , q ) B(q , x )
x = x1 , x2
p HLR ( x ) =
q2
∑
qn −1
n
i
1
i
i
2
n −1
f
2
2
f
n
A introdução do conceito de estado final modifica as
propriedades de geração estatística de strings
Proposição:
Ana L. N. Fred
ΓHMM
ΓHLR ≠ ∅
ΓHMM ⊄ ΓHLR
ΓHLR ⊄ ΓHMM
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMMT -HMM with observation probability
distribution in the transitions
HMMT - definição alternativa (equivalente) de um HMM
em que a distribuição de probabilidade de observação de
símbolo é atribuída às transições em vez de aos estados.
HT = (Q, Σ, A, B, π )
Q, A, π como definidos anteriomente
B : Q × Σ × Q → [0,1]
∑ B(q, a, q′) = 1 ∀q,q′∈Q , se A(q, q′) ≠ 0
a∈Σ
Probabilidade de observação da sequência
x , x ∈Σ
( x ) = ∑ π ( q ) A( q , q ) B ( q , x , q )
A(q , q )B(q , x , q )
x = x1 , x2
p HT
0
q0
qn
n
0
i
1
n −1
0
n
1
n −1
1
n
n
Proposição:
Para cada HMM H = (Q, Σ, A, B, π ) existe um HMMT
HT = (Q′, Σ, A′, B′, π ′) tal que ∀ x∈Σ* , pH ( x) = pHT ( x)
Proposição:
Para cada HMMT HT = (Q, Σ, A, B, π ) existe um HMM
H = (Q′, Σ, A′, B′, π ′) tal que ∀ x∈Σ* , p H ( x) = pHT ( x)
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Proposição:
Para cada HMM H = (Q, Σ, A, B, π ) existe um HMMT
HT = (Q′, Σ, A′, B′, π ′) tal que ∀ x∈Σ* , pH ( x) = pHT ( x)
Demonstração:
Seja Q′ = Q {q0 } com q0 ∉ Q
A′( q, q′) = A(q, q′)
∀q, q′ ∈ Q
A′( q0 , q) = π (q )
∀q ∈ Q
B′( q, a, q′) = B( a, q′)
B′( q0 , a, q) = B( a, q )
π ′(q0 ) = 1
∀a ∈ Σ, ∀q, q′ ∈ Q
∀a ∈ Σ, ∀q ∈ Q
e π ′(q ) = 0 ∀q ∈ Q
a) As novas distribuições verificam a definição de HMMT:
∑
∑
∑
∑
q ′∈Q
q∈Q
A′(q, q′) = ∑q′∈Q A( q, q′) = 1
∀q ∈ Q
A′( q0 , q ) = ∑q∈Q π (q) = 1
B′(q, a, q′) = ∑a∈Σ B( a, q′) = 1 ∀q′ ∈ Q
B′(q0 , a, q) = ∑a∈Σ B( a, q ) = 1 ∀q ∈ Q
a∈Σ
a∈Σ
b)A equivalência é mostrada por: para todo o x com |x|=n
pHT ( x) =
π ′(q ) A′(q , q ) B′(q , x , q )
∑
′
′
q0
=
qn
0
1
n −1
0
1
1
, qn ) B (qn −1 , xn , qn )
π (q ) B( x , q ) A(q , q )
∑
A(q
1
q1
qn
= pH ( x)
Ana L. N. Fred
A (q
0
1
1
n −1
1
2
, q n ) B ( xn , q n )
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMM
π(q 1 )
B(a,q 1 )
A(q 1 ,q 3 )
HMMT
q3
q1
B(a,q 3 )
π(q 3 )
A(q 1 ,q 3 )
q3
q1
B(a,q 3 )
B(a,q 3 )
B(a,q 2 )
A(q 1 ,q 2 )
B(a,q 2 )
A(q 2 ,q 3 )
A(q 2 ,q 3 )
A(q 1 ,q 2 )
q2
π(q 2 )
q2
B(a,q 1 )
π(q 1 )
B(q 0 ,a,q 2 )=
B(a,q 2 )
π(q 2 )
π(q 3 )
B(a,q 3 )
q0
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Proposição:
Para cada HMMT HT = (Q, Σ, A, B, π ) existe um HMM
H = (Q′, Σ, A′, B′, π ′) tal que ∀ x∈Σ* , p H ( x) = pHT ( x)
Demonstração:
Seja
Q′ = {(q, q′) | q, q′ ∈ Q e A(q, q′) ≠ 0}
A′((q, q′)), (q′′, q′′′)) = A(q′′, q′′′) se q′ = q′′
=0
caso contrário
B′(a, (q, q′)) = B(q, a, q′)
π ′((q, q′)) = π (q) A(q, q′)
a) As novas distribuições verificam a definição de HMM:
∑
∑
∑
( q ′′, q ′′′ )
A′((q, q′), ( q′′, q′′′)) = ∑q′′′ A(q′, q′′′) = 1 ∀q, q′ ∈ Q
B′(a, (q, q′)) = ∑a∈Σ B (q, a, q′) = 1
π ′(( q, q′)) = ∑q ,q′ π (q) A(q, q′) = 1
( q , q′ )
∀q, q′ ∈ Q
a∈Σ
b)A equivalência é mostrada por: para todo o x com |x|=n
pH ( x) =
π ′(q , q ) B′( x , (q , q )) A′((q , q ), (q , q ))
∑
0
q0
=
qn
1
1
0
1
0
1
1
2
B′( x2 , (q1 , q2 )) A′((qn − 2 , qn −1 ), (qn −1 , qn ))
B′( xn , (qn −1 , qn ))
π (q ) A(q , q ) B(q , x , q )
∑
q0
qn
= pHT ( x)
Ana L. N. Fred
0
0
1
0
1
1
A(q1 , q2 ) B(q1 , x2 , q2 )
A(qn −1 , qn ) B(qn −1 , xn , qn )
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMMT
HMM
π1
π0
q0
B(q 1 ,a,q 2 )
q1
A(q 1 ,q 2 )
B(q 0 ,a,q 2 )
A(q 2 ,q 1 )
A(q 0 ,q 2 )
q2
π2
B(q 2 ,a,q 1 )
B(q 1 ,a,q 2 )
π1 A(q 1 q 2 )
π0 A(q 0 q 2 )
B(q 0 ,a,q 2 ) q 0 q 2
A(q 2 ,q 1 )
q 1q 2
A(q 1 ,q 2 )
A(q 2 ,q 1 )
q 2q 1
π2 A(q 2 q 1 )
B(q 2 ,a,q 1 )
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMMTF - HMM with observation
probability distribution in the transitions and
final state
HMMTF -HMMTF com a restrição de um estado final
“absorvente”
HTF = (Q, Σ, A, B, qi , q f )
∑q′ A(q, q′) = 1 ∀q∈Q−{q f }
B : Q × Σ × Q → [0,1]
∑ B(q, a, q′) = 1 ∀q,q′∈Q , se A(q, q′) ≠ 0
a∈Σ
qi ≡ estado inicial
q f ≡ estado final, no qual todas as transições são proibidas
Todas as sequências terminam no estado final
Probabilidade de observação da sequência
p HTF ( x) =
x = x1 , x2
x
∑
q1
Ana L. N. Fred
n
, xi ∈ Σ
A(qi , q1 ) B ( qi , x1 , q1 )
A( qn −1 , q f ) B ( qn −1 , xn , q f )
q n−1
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMMTF <=> SFSG
Proposição:
Dado um HMMTF HTF = (Q, Σ, A, B, qi , q f ) existe uma SFSG
G e = (G, µ ), com G = ( N , Σ, R, S ), tal que ∀ x∈Σ* , pGe ( x) = p HTF ( x)
N = Q − {q f } ; S = qi
R = {(q → aq′) | B (q, a, q′) ≠ 0 e q′ ≠ q f }
{(q → a) | B(q, a, q f ) ≠ 0 }
µ ( q → aq′) = A(q, q′) B(q, a, q′)
µ ( q → a) = A(q, q f ) B (q, a, q f )
Proposição:
Dado uma SFSG, G e = (G, µ ), existe um HMMTF,
HTF = (Q, Σ, A, B, qi , q f ) , tal que ∀ x∈Σ* , pGe ( x) = pHTF ( x)
Q = N {q f }
A( q, q′) = ∑ µ (q → aq′)
q f ∉N , qi = S
∀q ,q′∈N
a
B( q, a, q′) = µ (q → aq′) / A(q, q′) ∀q ,q′∈N , ∀ a∈N
A( q, q f ) = ∑ µ (q → a )
∀q∈N
a
B( q, a, q f ) = µ (q → a ) / A(q, q f )
A( q, q′) = 0
A( q, q f ) = 0
Ana L. N. Fred
∀q∈N , ∀a∈N
se (q → aq′) ∉ R
se (q → a) ∉ R
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMMT
B(q i,b,q 1 )
µ(q i->a q 1 )=
A(q i,q 1 )B(q i,a,q 1 )
B(q 1 ,a,q f )
B(q i,a,q 1 )
A(q 1 ,q f)
A(q i ,q 1 )
qi
SFSG
q1
a
qf
qi
µ(q 1 ->a )=
A(q 1 ,q f )B(q
a 1 ,a,q f )
q1
T
b
µ(q i->b q 1 )=
A(q i,q 1 )B(q i,b,q 1 )
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
SFSG
µ(q 1 ->a )
µ(q i->a q 1 )
a
a
qi
HMMT
B(q i,a,q 1 )=
µ(q i->a q 1 )/A(q i,q 1 )
B(q 1 ,a,q f )=1
q1
b
µ(q i->b q 1 )
Ana L. N. Fred
T
qi
A(qi ,q1 )=
µ(q i->a q1 )+
µ(q i->b q1 )
A(q1 ,qf )=
µ(q 1 ->a)
q1
qf
B(q i,b,q 1 )=
µ(q i->b q 1 )/A(q i,q 1 )
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
HMM
SFSG:
Prob. de observação de uma
sequência:
n
p( x ) =
∑
∏ A( q
q 1 qn t =1
D
t −1
, qt ) B(qt , xt )
n
p( x ) = ∑ ∏ Pr( At −1 → xt At )
i =1 t =1
Estrutura
• definida a priori
• inferida a partir do
conjunto de treino
0
2
0,1,2,3,7
1
σ
0
0
1
0
T
1
1
0
0,1
1
2
Estimação de Parâmetros
•Viterbi
•Baum-Welch (EM)
Ana L. N. Fred
•Método da apresentação
estocástica (equivalente a
ML para gramáticas não
ambíguas)
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Gramáticas de Estados Finitos
•
•
0010010010014
0010010014
•
•
G=(N,Σ,R,S)
N={n1,n2,n3,n4}
Σ={0,1,4}
S=n1
R: n1 -> 0 n2
n2 -> 0 n3
n3 -> 1 n4 | 1 n1
n4 -> 4
•
•
Derivação de uma sequência:
n1
0 n2
00 n3
001 n1
0010 n2
00100 n3
001001 n4
0010014
Ana L. N. Fred
n1
0
1
n2
0
n3
1
n4
4
n1
0
T
n2
0
n3
1
n1
0
n2
0 n3
1 n4
4
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
SFSG - Gramáticas estocásticas de
estados finitos
SFSG
Ge = (G, µ )
G = ( N , Σ, R, S ) - gramática regular
µ : R → [0,1]
∑a∈Σ,B∈N {ε } µ ( A → aB) = 1
Derivação de x a partir de S de acordo com G é uma
sequência de regras D(x)=(r1,r2,…,rn(x) que permite
obter x a partir de S por sucessiva aplicação de regras em
D(x).
Probabilidade associada à derivação D(x):
p ( D ( x)) = µ (r1 ) µ (r2 )
µ (r
n( x)
)
Probabilidade de geração da sequência
x = x1 , x2
x
n
, xi ∈ Σ
se não existe uma derivação para x
0
pGe ( x) =  p( D( x )) para todas as derivações D ( x)
∑
 D ( x )
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
∑p
Proposição: Dada uma SFSG
Ge
( x) ≤ 1
x∈Σ*
Pn = 1 − ∑a a a
1 2
n
∑
C1C 2
C ∈N ( µ ( S → a1C1 )
Quando n → ∞, Pn →
n
µ (Cn −1 → an Cn ))
∑p
Ge
x∈Σ
( x)
*
∴ ∑ pGe ( x) ≤ 1
x∈Σ*
Dada uma SFSG, se
diz - se consistente
Ana L. N. Fred
∑p
Ge
( x) = 1 a gramática
x∈Σ *
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Reconhecimento de Objectos
Metodologia
Extração de
Contornos
Descrição em
string
Treino
HMM/SFSG
Classificação
MAP
Baseado num
método de
comparação
com limiar
8 directional
differential
chain code
Extração de contornos
•O contorno do objecto é amostrado em 50 pontos
equi-espaçados
•o ângulo entre segmentos consecutivos é
quantifcado em 8 níveis.
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Base de Dados de Imagem
•15 tipos de ferramentas
•50 imagens por ferramenta, divididas em conjunto de
treino e de teste
•incluem-se diferentes poses
00000000500000000010000060000016100000076000000003
00000000500000000010000660000100000000166000000003
00000000660000001610000067000010000000066000000003
00000000500000000000040120500001700000166000000003
00000000570000000100076030760001000000005000000003
00000000500000000000050030500001700000075000000003
Exemplos de Ferramentas
t1
Ana L. N. Fred
t2
t3
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
t4
t5
t6
t7
t8
t9
t11
t12
t14
Ana L. N. Fred
t13
t15
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Aparato Experimental
Aprendizagem do Modelo
•Cada objecto é modelado por um HMM ou uma SFSG,
treinado de acordo com:
HMM: Topologias:
•Totalmente ligada (10 & 20 estados)
•Esquerda-direita (20 & 50 estados)
Estimação de Parâmetros:
•Baum-Welch
•Viterbi
SFSG: Topologia:
•inferida a partir dos dados de treino usando o
método das k-tails (k=1, … 10)
•o número de estados depende da estrutura dos
dados
Estimação de Parâmetros:
•Método da apresentação estocástica
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Resultados
HMM:Os melhores resultados foram obtidos com o
algoritmo de BW
Ponto inicial fixo
Totalmente
ligada
Esquerda-direita
Ponto inicial arbitrário
99.7
99.5
100
98.9
SFSG:
Pe: % erro; Pm: % não reconhecimento; Pec: % erro com prob-NN
Rec: % global de reconhecimento
* Classificação nearest-neighbor probabilística
Ana L. N. Fred
IST, Julho de 98
Modelos de Markov Não Observáveis e Gramáticas Regulares
Conclusões
•A abordagem sintáctica permite uma automatização total
dos processos de modelação e reconhecimento => as
estruturas obtidas por SFSGs e HMMs são diferentes, as
primeiras dependendo da complexidade estrutural dos dados.
• No respeitante à estimação de parâmetros o método de
apresentação estocástica é semelhante ao algoritmo de
Viterbi usado no treino dos HMMs.
Os resultados experimentais revelam:
•elevados níveis de reconhecimento por ambos os métodos
•HMMs são mais robustos no sentido em que possuem uma
maior capacidade de generalização do que as SFSGs. Esta
dificuldade é ultrapassada usando parsers correctores de
erros (regra de decisão o vizinho mais próximo
probabilistico) à custa de um maior custo computacional.
•As SFSGs conduzem geralmente a modelos de menor
dimensão.
Ana L. N. Fred
IST, Julho de 98