Automatas probabilisticos

AUTÓMATAS PROBABILÍSTICOS O ESTOCÁSTICOS

Autómatas Probabilísticos
En su funcionamiento interviene el concepto de probabilidad, asociada a que se produzca una determinada transición. Son autómatas finitos en los que las transiciones entre estados a partir de símbolos de entrada pueden no producirse de forma segura (probabilidad = 1) sino que existe una determinada probabilidad asociada a quese produzca la transición. No se habla del estado en el que se encuentra el autómata en un determinado instante, sino de la probabilidad de que se encuentre en cada uno de los estados del autómata. Aplicaciones reales basadas en comportamientos probabilísticos de transición, pej. Movimiento de robots, reconocimiento de voz, lenguaje natural, etc.

Definición
AFP = (Σ, Q, M, P(0), F), es unaquíntupla
Σ: alfabeto de entrada Q: conjunto de estados, finito y no vacío M: conjunto de matrices de probabilidad de transición entre estados.
M = {Ma  a ∈ Σ}, Ma contiene las probabilidades de transición de un estado a otro cuando se recibe el símbolo a. Para cada símbolo del alfabeto, existe una matriz de probabilidades

P(0): vector de estado inicial: contiene la probabilidad de encontrarseen el estado inicial. Cada estado de Q tiene asociada una probabilidad de ser el estado inicial F⊆Q: Conjunto de estados finales o de aceptación (no vacío).

Matrices de Probabilidad de Transición
Por cada símbolo a de Σ se define una matriz de probabilidad de transición, M(a), que define la probabilidad de dado que el autómata se encuentre en un determinado estado y reciba el símbolo deentrada a, transite a cada uno de los demás estados.
p11 p12 ... p1n

∀a ∈ Σ, ∃ M(a) =

p21 p22 ... P2n ... ...... .... pn1 pn2 ....pnn

donde: n: número de estados: Q pij: probabilidad de que estando en el estado i y recibiendo una a como entrada, transite al estado j. 0 ≤Pij ≤ 1 para cada estado i, se cumple: ∑ pij = 1
n j =1

Vectores de estados
P(t) es el vector de estados en uninstante t. Indica la probabilidad de cada estado en el instante t
Tiene una componente para cada estado del AFP. P(t) = (P1(t), ..., Pn(t)), para un AFP con n estados Cada Pi(t) es la probabilidad de que el AFP se encuentre en el estado i. n Se cumple: ∑i =1 pi = 1, ∀t La probabilidad de que el AFP se encuentre en el instante t+1 en el estado i, si el símbolo que se lee es “a”, deberá considerar lasuma de las probabilidades de llegar a i desde cada uno de los j posibles:

Pi (t + 1) = ∑ j =1 pj (t ) x Mji ( a )
n

Para el vector completo: P (t + 1) = P (t ) x M ( a )

AF Probabilísticos. Ejemplo
Según los valores de M(a) y M(b) (I):
M (a) = M (b) =
1 0 0 1

Ppp=1

p

q

Pqq=1

t = 0, P(0) = {Pp(0) Pq(0)} t = 1, a la llegada de una “a” o una “b”: P(1) = {Pp(0) x 1 + Pq(0) x0 Pp(0)x 0+ Pq(0) x 1} = {Pp(1) Pq(1)}

AF Probabilísticos. Ejemplo
Según los valores de M(a) y M(b) (II):
M (a) = M (b) =
0 1 1 0

Ppq=1 p Pqp=1
t = 0, P(0) = {Pp(0) Pq(0)} t = 1, a la llegada de una “a” o una “b”:
P(1) = {Pp(0) x 0 + Pq(0) x 1 Pp(0)x 1+ Pq(0) x 0} = {Pq(1) Pp(1)}

q

AF Probabilísticos. Ejemplo
Según los valores de M(a) y M(b) (III):
M (a) = M (b) =
0.5 0.5 0.50.5

Ppq=0.5 Ppp=0.5 p Pqp=0.5
t = 0, P(0) = {Pp(0) Pq(0)} t = 1, a la llegada de una “a” o una “b”:
P(1) = {Pp(0) x 0.5 + Pq(0) x 0.5 Pp(0)x 0.5+ Pq(0) x 0.5} = {Pp(1) Pq(1)}

q

Pqq=0.5

AF Probabilísticos. Ejemplo
Sea el AFP, AFP1= ({0,1}, {q1, q2, q3}, M, (1/3 1/3 1/3), {q3}), donde
M = {M(0), M(1)}
1/3 1/3 1/3 1/2 1/2 0

M (0) =

1/2 0 1/2 0 1 0

y M(1) =

1/3 2/3 0 0 01

Si P(0) = (1/3 1/3 1/3) y se recibe un 0, escribir P(1).
P(1) = {P1(1) P2(1) P3(1)} P1(1) = P2(1) = P3(1) =

∑ P ( 0) x M ∑ P ( 0) x M ∑ P ( 0) x M
3 j =1 3 j =1 3 j j j =1 j

j1 j2 j2

(0) = 1 / 3 x1 / 3 + 1 / 3 x1 / 2 + 1 / 3 x 0 = 5 / 18 (0) = 1 / 3x1 / 3 + 1 / 3 x 0 + 1 / 3x1 = 4 / 9 (0) = 1 / 3x1 / 3 + 1 / 3 x1 / 2 + 1 / 3 x 0 = 5 / 18

P(1) = (5/18 4/9 5/18), por lo que en...