modelos estocasticos

´
Reconocimiento Sintactico de Formas

´
Modelos Estocasticos

2. Modelos Estoc´sticos:
a
2.1.
2.2.
2.3.
2.4.

Introducci´n: formalismo y propiedades
o
An´lisis Sint´ctico Estoc´stico:gram´ticas incontextuales
a
a
a
a
An´lisis Sint´ctico Estoc´stico Corrector de Errores
a
a
a
Aprendizaje de los modelos:

µ Estimaci´n de las distribuciones de probabilidad:
o
­ M´todoscl´sicos: Inside-outside y conteo de Viterbi
e
a

PrM (x)

­ Lenguaje estoc´stico
a

lenguaje car´cter´
a
ıstico.

­ φ : T ∗ −→ [0, 1]

funci´n estoc´stica computable:
o
a

i) x ∈ L=⇒ φ(x) = 0

­ M´todos heur´
e
ısticos: aprendizaje bayesiano
­ Aprendizaje mediante algoritmos de estimaci´n
o

∀x ∈ T ∗

ii) x ∈ L =⇒ 0 < φ(x) ≤ 1

µ Aprendizaje de la estructura:
­M´todos caracterizables: Algoritmo de Sakakibara
e

∀x ∈ T ∗

iii)

Reconocimiento Sint´ctico de Formas
a

(L, φ) sobre el alfabeto T :

­ L ⊆ T∗

­ M´todos basados en un subconjunto dederivaciones
e
­ Estimaci´n basada en aprendizaje discriminativo
o

Jos´ Miguel Bened´ (2005-2006)
e
ı

Dada la observaci´n x ∈ T ∗ y un modelo estoc´stico M ; la probabilidad
o
a
de que elmodelo M describa la observaci´n x, es:
o

/

Modelos Estoc´sticos 1
a

x∈L φ(x)

=1

Jos´ Miguel Bened´ (2005-2006)
e
ı

Reconocimiento Sint´ctico de Formas
a

´
ModelosEstocasticos

­ Gram´ticas estoc´sticas:
a
a

Modelos Estoc´sticos 2
a

/

Modelos Estoc´sticos 4
a

´
´
Gramaticas estocasticas

­ Ejemplo

/

Dado el alfabeto T = {a, b}, se define L ={anbn | n ≥ 0}, con φ(x) = 0,
∀x ∈ L y φ(anbn) =

1
en! .

­ G = (N, T, P, S)
­ Pr : P →]0, 1]

φ(x) =
x∈L

0≤n≤∞

1
1
=
en! e

0≤n≤∞

1
1
= e=1
n! e

∀Ai ∈ N

Ge = (G, Pr)gram´tica caracter´
a
ıstica

probabilidades de las reglas:
Pr(rij ) = Pr(Ai → αj ) = Pr(Ai → αj | Ai)

Sea ni el n´mero de reglas con Ai como parte izquierda, entonces:
u

­ Teorema...