descubrimiento de estructuras

Descubrimiento de Estructuras

Gabriel Infante-Lopez

Grupo de PLNFacultad de Matematica, Astronomıa y Fısica

UNC, Cordoba (Argentina)http://www.cs.famaf.unc.edu.ar/~pln

http://www.cs.famaf.unc.edu.ar/~gabriel

August 5, 2010

Gabriel Infante-Lopez Descubrimiento de Estructuras

http://www.cs.famaf.unc.edu.ar/~pln

http://www.cs.famaf.unc.edu.ar/~gabriel

contenido

1. generalidades

2. aprendizaje de lenguajes regularesI cadenas ocultas de markovI n-grammas

3. gramaticas libre de contextoI aprendizaje supervisadoI aprendizaje no supervisado y gramaticas minimas.


generalidades

objetivos

1. dar una idea general de la problematica asociada alaprendizaje de estructuras en lenguaje natural

2. dar una idea general de algunas tecnicas usuales para resolveresta problematica.

3. dar un mapa general de las relaciones entre los distintosmecanismos

desobjetivos

1. manejo de los modelos

2. teorias linguisticas de lenguaje natural


algunas tareas posibles

1. encontrar palabras

2. encontrar numeros

3. encontrar verbos

4. encontrar nombres propios

5. encontrar sustantivos.

6. encontrar adjetivos, verbos, sustantivos, etc

7. encontrar como estos se agrupan para formar NP, VP, PP, etc

8. encontrar patrones en general: ¿que son patrones? ¿quesignificado tienen?


corpus

mostrar corpus


¿por que buscamos esta informacion en particular?

1. porque puede ayudarnos a “entender” el significado de lo quese dice: de quien se habla, que cosas hacen estos, que cosastienen, como opinan, done quieren ir, a que hora van, etc.

2. porque sabemos de antemano que esta informacion estapresente en el texto. sabemos esto por que al menosentendemos un lenguaje natural.


¿como sabemos que lo encontrado es lo buscado?

1. sabemos de antemano las respuestas correctas y probamos elsistema.

1.1 reportamos el numero de elementos correctos encontramos conrespecto a los elementos encontrados

1.2 reportamos el numero de elementos correctos encontrados conrespecto a los elementos correctos.

2. disenamos una metrica sobre lo encontrado que indique lacalidad de lo buscado.

I reportamos metricas de compresion o de verisimilitud. nosiempre aplicable. depende principalmente de la naturaleza dela informacion.


gramaticas para expresar estructura

I gramaticas regulares, tambien conocidas como automatas.

I gramaticas de un solo elemento en el lenguaje.

I gramaticas libre de contexto.


el uso de probabilidades en las estructuras

¿por que usar probabilidades?

I definen un espacio de probabilidad sobre conjunto de strings,

I atrapan la idea de frecuencia en lenguaje natural.: una oraciones mas frecuente que otra,

I introducen un mecanismo claro para disambiguar: vi un perrocon un telescopio vs. vi un perro con un telescopio,

I mejoran la expresividad de los formalismos no-probabilısticos,

I mejoran las propiedades de aprendabilidad de los formalismos,y

I permiten el uso de los estiamdores probabilısticos.


diferentes gustos de gramaticas regulares

algunos posibles modelos

I ngrams

I cadenas de markov ocultas

I automatas probabilısticos determinısticos

I automatas probabilısticos no-determinısticos

I gramaticas libres de contexto probabilısticas

I tree adjoining grammars probabilısticas

¿que tienen en comun? ¿que las diferencia?


lenguaje natural: un fenomeno natural

I queremos modelos computacionales que modelen las oracionesde un lenguaje natural.

I suponemos que este conjunto de oraciones son modelables conuna mecanismo formal

I queremos realiazar apliacaciones con lenguaje natural y nonecesariamente “caracterizarlo”

nuestro objetivo

dar una idea de modelos computacionales que permitan lamanipulacion de lenguaje natural


cadenas de markov ocultas

1 2

[a 0.2 ][b 0.8 ]

[a 0.9 ][b 0.1 ]

0.9

0.4 0.6

0.7

0.30.1

generacion en estas cadenas

1. elegir donde empezar,

2. elegir que sımbolo emitir,

3. elegir el proximo estado,

4. volver al paso 2.

probabilidad de la secuencia generada

la probablidad de cada una de las elecciones realizadas


algoritmos basicos para hmm

1. dada una secuencia de emisiones (ejemplo: abbaba), cual es lasecuencia mas probable de estados?

2. cual es la probabilidad de una oracion. es decir la suma detodos los caminos que las emiten

3. aprendizaje:

3.1 dada una cadena de markov con su topografia definida, y unconjunto de secuencias de emisiones encontrar lasprobabilidades de los arcos y de las emisiones.

3.2 dado un conjunto de emisiones, encontrar las topografia de lacadena de markov con sus emisiones


modelado de LN con hmm

suposiciones

I el lenguaje es regular,

I y tiene una distribucion de probabilidad particular

I las cadena tiene estados que no conocemos

desventajas

I el lenguaje es regular,

I y tiene una distribucion de probabilidad particular

I las cadena tiene estados que no conocemos

aplicaciones

I Part of speech tagging.


simplificaciones estructurales

1 2

[a 0.2 ][b 0.1 ]

0.9

0.4 0.6

0.7

0.30.1 1 2

[a 1.0 ][b 1.0 ]

0.9

0.4 0.6

0.7

0.30.1

I cada estado solo puede emitir un sımbolo

I la distribucion de probabilidad para las emisiones se vuelvetrivial

I podemos suponer que hay un mapeo injectivo entre estados ysımbolos emitidos.

resultado de estas suposiciones

unigramas


algoritmos basicos para hmm

1. dada una secuencia de emisiones (ejemplo: abbaba), cual es lasecuencia mas probable de estados?

2. cual es la probabilidad de una oracion. es decir la suma detodos los caminos que las emiten

3. aprendizaje:

3.1 dada una cadena de markov con su topografia definida, y unconjunto de secuencias de emisiones encontrar lasprobabilidades de los arcos y de las emisiones.

3.2 dado un conjunto de emisiones, encontrar las topografia de lacadena de markov con sus emisiones


aprendizaje de unigramas

I topologia definida por la naturaleza de los unigramas

I tiene un solo estado, y la probabilidad de cada emision, esproporcional a la frecuencia de cada sımbolo.

I la probabilidad de una oracion: producto de las veces queaparece cada palabra.


volver al lenguaje natural

que suponemos sobre lenguaje natural cuando lo modelamoscon unigramas

I las palabras son independientes del contexto en el queaparecen.

I la vida es una moneda y la moneda es una vida tienen lamisma probabilidad

I de de de de tiene mas probabilidad que mi mama me mima

1

[a 0.2 ][b 0.8 ]

1

1

pero...

I son muy faciles de aprender!

I usadas para back-off, smoothing, y generacion de reglas.


n-gramms

mejorando el modelo

I supondremos que una emision depende solamente de las nanteriores.

I cada estado sigue emitiendo un solo sımbolo

I hay tantos estados por una emision como contextos existanpara una palabra.


graficamente

a b

[a 1.0 ] [b 1.0 ]

a b

[a 1.0 ] [b 1.0 ]

símbolo a generar

símbolo anterior


generador de textos

demo de un generador de texto


gramaticas libre de contexto probabilisticas

una pcfg consiste de

I Un conjunto de terminales , wk, k = 1, . . . ,V

I Un conjunto de no-terminales, N i, i = 1, ..., n

I Un sımbolo inicial destacado, N1.

I Un conjunto de reglas, N i → ζ j, (donde ζj es una secuenciade terminales y no-terminales)

I Probabilidades asignadas a las reglas de manera que :

∀i∑

j

P(N i → ζ i ) = 1


notacion

I Oracion: secuencia de palabras w1 . . .wm

I wab: la secuencia wa . . .wb.

I N iab el no-terminal N i domina wa . . .wb.

N j

wa . . .wb


ejemplo

S → NP VP 1.0 NP → NPPP 0.4PP → P NP 1.0 NP → astronomos 0.1VP → V NP 0.7 NP → orejas 0.18VP → VP PP 0.3 NP → vieron 0.04P → con 1.0 NP → estrellas 0.18V → vieron 1.0 NP → telescopios 0.1


arboles sintacticos - I

’S1.0

NP0.1

astronomos

VP0.7

V1.0

vieron

NP0.4

NP0.18

estrellas

PP1.0

P1.0

con

NP0.18

orejas


arboles sintacticos - I

’S1.0

NP0.1

astronomos

VP0.3

VP0.7

V1.0

vieron

NP0.18

estrellas

PP1.0

P1.0

con

NP0.18

orejas


La probabilidad de los arboles y de las oraciones

P(t1) = 1.0× 0.1× 0.7× 1.0× 0.4× 0.18× 1.0× 1.0× 0.18= 0.0009072

P(t2) = 1.0× 0.1× 0.3× 0.7× 1.0× 0.18× 1.0× 1.0× 0.18= 0.0006804

P(w15) = P(t1) + P(t2)= 0.0015876


la probabilidad de los arboles y de las oraciones

P(w1n) =∑

t

P(w1n, t)donde tes un arbol para w1n


modelos de lenguaje

las pcfgs definen una distribucion de probabilidad en el espacio destrings, sobre los arboles. es un solo modelo para todas lasoraciones que cuando se marginaliza muestra un modelo para cadaoracion.


Suposiciones subyacentes en las PCFGs

1. Invariante de lugar (similar al de HMM):

∀kP(Nk(k+c) →∗ ζ)

es siempre la misma.

2. libre de contexto

P(N jkl → ζ|palabras fuera dewk . . .wl) = P(N j

kl → ζ)

3. Libre de Ancestros.

P(N jkl → ζ|nodos por arriba de N j

kl) = P(N jkl → ζ)


Caracterısticas Importantes de las PCFGs

I son una solucion parcial al problema de la ambiguedad.

I son buenas desde un punto de vista formal sobre elaprendizaje automatico.

I son robustas, pueden dar un analisis a casi cualquier oracion.

I definen un modelo de lenguaje, aunque en la practica secomporta peor que trigramas.

I las PCFGs tienen un bias: arboles pequenos tienen mejorprobabilidad que arboles grandes.


preguntas a resolver para PCFGs

I P(w1m|G )

I arg maxtP(t|w1m,G )I Aprendizaje:

I Supervisado: Encontrar G tal que P(t1 . . . tk |G ) sea maximo.I No-Supervisado: Encontrar G tal que P(w1m|G ) sea maximo.


aprendizaje supervisado

input

conjunto de oraciones con sus respectivas derivaciones

output

una gramatica libre de contexto probabilıstica

aproximaciones

I estimaciones de maxima verisimilitud

I gramaticas en dos niveles


aprendizaje no supervisado

input

conjunto de oraciones

output

una gramatica libre de contexto probabilıstica

aproximaciones

I EM: un algoritmo de hill climbing que busca un modelo quemaximize la verosimilitud de los datos.

I gramaticas mınimas: buscan gramaticas de tamano minimo.


problema de la gramatica mınima

definicion del problema

Dada una secuencia s, encontrar una gramatica libre de contextoG (s) de tamano minimo que genere exactamente esta y solamenteesta secuencia.

ejemplo

s =“how much wood would a woodchuck chuck if awoodchuck could chuck wood?”, una posible G (s) (nonecesariamente minimal) es

S → how much N2 wN3 N4 N1 if N4 cN3 N1 N2 ?N1 → chuckN2 → woodN3 → ouldN4 → a N2N1


Aproximaciones Existentes

1. algoritmos practicos: Sequitur (y otras aproximacionesoffline). 1996“Compression and Explanation Using Hierarchical Grammars”. Nevill-Manning & Witten. The Computer

Journal. 1997

2. entorno de compresion teorica: Grammar Based Code. 2000“Grammar-based codes: a new class of universal lossless source codes”. Kieffer & Yang. IEEE T on

Information Theory. 2000

3. ratio de aproximacion al tamano de la gramatica mas pequenaen el peor caso. 2002“The Smallest Grammar Problem”, Charikar et.al. IEEE T on Information Theory. 2005


algoritmos offline

I Maximal Length (ML): elegir la repeticion mas larga,reemplazar todas las ocurrencias con un nuevo sımbolo, iterar.Bentley & McIlroy “Data compression using long common strings”. DCC. 1999.

Nakamura, et.al. “Linear-Time Text Compression by Longest-First Substitution”. MDPI Algorithms. 1999

I Most Frequent (MF): take most frequent repeat, replace alloccurrences with new symbol, iterateLarsson & Moffat. “Offline Dictionary-Based Compression”. DCC. 1999

I Most Compressive (MC): take repeat that compresses thebest, replace with new symbol, iterateApostolico & Lonardi. “Off-line compression by greedy textual substitution” Proceedings of IEEE. 2000

S → how much wood would a woodchuck chuckif a woodchuck could chuck wood?

⇓S → how much wood wouldN1huck ifN1ould chuck wood?N1 → a woodchuck c

⇓S → how much wood wouldN1huck if N1ould N2wood?N1 → a woodN2cN2 → chuck


un esquema general: IRR

IRRCOO (Iterative Repeat Replacement with Choice of OccurrenceOptimization) frameworkentrada: una secuencia s, y una funcion de puntuacion f

1. inicializar la gramatica como S → s

2. tomar una repeticion ω que maximize f sobre G

3. if reemplazar ω produce una gramatica mas grande que Gentonces3.1 devolver G

else3.1 reemplazar todas las ocurencias (no-overlapping) de ω en G

por un nuevo sımbolo N3.2 agregar la regla N → ω a G3.3 G ← mgp(cons(G ) ∪ cons(ω))3.4 goto 2

Complejidad: O(n3)


resultados en el corpus Canterbury

sequence Sequitur IRR-ML IRR-MF IRR-MC

alice29.txt 19.9% 37.1% 8.9% 41000asyoulik.txt 17.7% 37.8% 8.0% 37474cp.html 22.2% 21.6% 10.4% 8048fields.c 20.3% 18.6% 16.1% 3416grammar.lsp 20.2% 20.7% 15.1% 1473kennedy.xls 4.6% 7.7% 0.3% 166924lcet10.txt 24.5% 45.0% 8.0% 90099plrabn12.txt 14.9% 45.2% 5.8% 124198ptt5 23.4% 26.1% 6.4% 45135sum 25.6% 15.6% 11.9% 12207xargs.1 16.1% 16.2% 11.8% 2006

average 19.0% 26.5% 9.3%









Complejidad: O(n3)


dividiendo el problema

eleccion de constituyentes

problema de la gramaticamınima

eleccion de ocurrencias









Complejidad: O(n3)



problema del parseo de gramatica minima (MGP)

dada secuencias Ω = s = w0,w1, . . . ,wm, encontrar unagramatica libre de contexto de tamano minimo que tieneno-terminales S = N0,N1, . . . Nm tal que cons(Ni ) = wi .


eleccion de ocurrencia: un ejemplo

dada una secuencia Ω = ababbababbabaabbabaa, abbaba, bab

N0

N1

N2

A minimal grammar for Ω isN0 → aN2N2N1N1aN1 → abN2aN2 → bab

mgp puede ser computado en O(n3)Gabriel Infante-Lopez Descubrimiento de Estructuras








Complejidad: O(n3)


dividiendo el problema

eleccion de constituyentes

problema de la gramaticamınima



redefinicion del espacio de busqueda

dado s, construir el reticulado 〈R(s),⊆〉 y asociar a cada nodo unapuntuacion η: el tamano de la gramatica mgp(η ∪ s). Lagramatica mınima tendra asociado un nodo con la puntuacionmınima.


redefinicion del espacio de busqueda

el reticulado es un espacio de busqueda bien definido

para una secuencia s, hay un nodo η en 〈R(s),⊆〉 tal quemgp(η ∪ s) es la gramatica mınima.


el algoritmo ZZ

fase bottom-up: dado un nodo η, computar la puntuacion de losnodos η ∪ wi y tomar el nodo con la puntuacion mınima.

fase top-down: dado un nodo η, computar las puntuaciones denodos η \ wi y tomar el nodo con la puntuacion minima.

ZZ: es la sucesion de ambas fases. Complejidad: O(n7)


resultados en el Canterbury Corpus

sequence IRRCOO-MC ZZ IRR-MC

alice29.txt -4.3% -8.0% 41000asyoulik.txt -2.9% -6.6% 37474cp.html -1.3% -3.5% 8048fields.c -1.3% -3.1% 3416grammar.lsp -0.1% -0.5% 1473kennedy.xls -0.1% -0.1% 166924lcet10.txt -1.7% – 90099plrabn12.txt -5.5% – 124198ptt5 -2.6% – 45135sum -0.8% -1.5% 12207xargs.1 -0.8% -1.7% 2006

average -2.0% -3.1%


induccion de automatas probabilisticos

material de entrenamiento

a, b, baaaba, baab, bba

0

1

23

4

5

6

109

8

7a

a

a

aa

a

b

b

b

b

0

1

23

4

5

6

109

8

7a

a

a

aa

a

b

b

b

b

0

23

4

5

6

109

8

7

a

a

a

aa

a

b

b

b

b

0

1

23

4

5

6

109

8

7a

a

a

aa

a

b

b

b

b

0

1

23

4

5

6

109

8

7a

a

a

aa

a

b

b

b

b

0 2 4 6a

a

a

b b


esquema general de induccion de automatas

I construir un arbol de prefijos

I cada arco tiene un peso asociado a la frecuencia de veces quese usa.

I estados donde terminan elementos de entrenamientos semarcan como finales.

I se “unen” estados dependiendo de la aproximacion encuestion.


¿por que unir estados?

I creacion de ciclos. vulve infinito al lenguaje modelado por elautomata.

I generalizacion del lenguaje. generaliza el lenguaje,disminuyendo la memorizacion de los elementos en el materialde entrenamiento.


estrategias usuales para unir estados

I mantener la distribucion de probabilidad lo mas cercana a ladistribucion original: MDI.

I minimizar la perplejidad del automata.

I si disponemos informacion negativa: minimizar el automatamanteniendo la informacion consistente.

I si disponemos de un oraculo: designar un mecanismo paracomprobar que dos estados son indistinguibles.


gramaticas de dos niveles

componentes

I pseudo-reglas

I meta-reglas,

I terminales,

I no-terminales,

I variables.


pseudo-reglas y variables

X

Xr x Xl

componentes de una pseudo-regla

I lado izquierdo: no-terminal

I lado derecho: secuencia de variables, terminales y/ono-terminales


meta-reglas y no-terminales

Xr

A X C

Xl

D X F

componentes de las reglas

I lado izquierdo: variables,

I lado derecho, secuencia de variables, no-terminales yterminales.


derivaciones

1. meta-reglas y pseudo-reglas se usan para construir “reglas”.

2. estas “reglas” se usan en el mismo sentido en las que se usanlas reglas de cfgs.

3. las gramaticas de dos niveles se pueden pensar como una cfgcon una cantidad infinita de reglas.

4. asi definidas, las gramaticas de dos niveles son equivalentes agramaticas libre de contexto a nivel de lenguaje.

5. asi definidas, las gramaticas de dos niveles no son equivalentesa gramaticas libre de contexto a nivel de arboles.


ejemplo de derivacion

meta-rules pseudo-rules

ADJm−→ ADJAdj S

s−→ ADJNoun

ADJm−→ Adj Adj

s−→ big

Nouns−→ ball

...

S

Adj

big

Adj

green

Noun

ball


derivaciones en general

4.1. Grammatical Framework 61

language. We show that there is a surjective mapping Γ from T (G) to T (W ) whichcan be used for effectively parsingW -grammars, as we will soon discuss.

We define our tree transformation function Γ using a tree rewriting schema. Therewriting schema is applicable only to trees containing at least one meta-rule. Ourintention is to rewrite those trees in T (G) into trees in T (W ). After each application ofthe rewriting schema, the number of rules marked as meta-rules is reduced by one. Thefunction Γ is defined as the recursive application of the schema until applications are nolonger possible, i.e., until all meta-rules have been eliminated. The intermediate treesin the rewriting procedure do not necessarily belong to either of the two tree languagesT (G) or T (W ). The rewriting schema is pictured in Figure 4.2. Left-hand symbols ofmeta-rules and pseudo-rules have been marked with superscriptsm and s respectively.The rewriting schema eliminates the rule V

m−→ X1X2 . . .Xk by transforming the treein part (a) into the tree in part (b).

(a) (b)

t1 t2 tk

tbta

Xs

tb

V m

ta

X1 X2 Xk

X2X1 Xk

t2 tkt1

. . .

. . .

Xs

Figure 4.2: A tree rewriting schema.

The function Γ for transforming trees in T (W ) into trees in T (G) is defined as follows:

Γ(t) =

t, if t does not contain any meta-variableΓ(t′), for t′ such that t → t′,

where→ is the reflexive and transitive closure of the rewriting schema defined above.A simple inductive proof on the number of meta-rules shows that Γ is well defined forall elements in T (G), i.e., Γ takes exactly one value for each t in T (G).

In Figure 4.3 we picture the rewriting procedure for the tree in Figure 4.1. Thevariable ADJ that is eliminated in each step is marked with ∗ symbols. Since the treein part (c) does not have any more variables, it corresponds to the result of applyingfunction Γ to the tree in part (a).

The function Γ is very important for parsing. With it, we can implement a parser forW-grammars by using a parser for CFGs plus a procedure implementing the function


aprendizaje

1. meta-reglas se definen como lenguajes regulares

2. pseudo-reglas se definen a mano y son fijas.

3. meta-reglas se definen como bigramas.

4. existen metodos supervizados y no-supervisados para aprendergramaticas de dos niveles.


evaluacion

1. programacion: implementacion de modelos simples para lageneracion de texo, definicion de funciones de puntuacionpara la busqueda de gramaticas mınimas, o sus propias ideas.

2. pequenas monografias. relevar el estado del arte en induccionde automatas, en la generacion no supervisada de gramaticaslibre de contexto.

3. examen final, una serie de preguntas a responder.


descubrimiento de estructuras

Documents