adquisición de conocimiento usando técnicas de procesamiento de texto y red ... · 2012-03-10 ·...

Adquisicion de conocimiento usando tecnicas deprocesamiento de texto y red semantica

Sesion 2: Parsing

Dra. Olivia Sanchez Graillet

7 de marzo de 2012

Dra. Olivia Sanchez Graillet (IIMAS) Seminario de Divulgacion 7 de marzo de 2012 1 / 62

Temas

Parsing con CFG (Gramaticas libres de contexto)

Parsers con CFG probabilıstica

Parsing con programacion dinamica

Parsing con DG (Gramaticas de dependencias)

Shallow parsers


Objetivos del analisis sintactico

Para un entendimiento profundo

Identificacion de TERMINOS (e.g., en IR)

En adquisicion lexica, para identificar RELACIONESGRAMATICALES

Para revision de gramatica

Para generacion de texto


Parsing con CFG


CFG

La DERIVACION de una cadena es una secuencia de aplicaciones dereglas

Ejemplo: la cadena “a flight” se puede derivar de la gramaticaanterior y el sımbolo NP por la derivacion:NP ⇒ Det Nominal ⇒ a Nominal ⇒ a Noun⇒ a flight

Las derivaciones se pueden visualizar como arboles de parseo (PARSETREES)

Los lenguajes definidos por CFGs son conjuntos de cadenas derivadasdel sımbolo de inicio S (Sentence: oracion)


CFG

Una CFG es una cuadrupla < N,Σ,P, S > que consiste en:

un conjunto de sımbolos no-terminales N

un conjunto de sımbolos terminales Σ

un conjunto de producciones PI A −→ αI A es un non-terminalI α es una cadena de sımbolos del conjunto infinito de cadenas (Σ ∪N)∗I S es el sımbolo inicial


Significado de “Libre de contexto”

El sımbolo no-terminal del lado izquierdo de la regla no depende denada mas

A −→ BCSe puede escribir A como BC sin importar el contexto en el que seencuentra A


Parsing con CFG

Parsing es el proceso de reconocer y asignar una ESTRUCTURA

Analizar una cadena con una CFG

Encontrar la derivacion de la cadena consistente con la gramatica

La derivacion da un arbol de parseo (PARSE TREE)


Ejemplo


Parsing visto como busqueda

Como en el caso de expresiones regulares no-determinısticas, elproblema principal con parsing es la existencia de PUNTOS deELECCION

Se necesita una extrategia de busqueda que determine el orden en elque se consideran las alternativas


Estrategias de busqueda Top-down y Bottom-up

TOP-DOWN: trata de construir arboles de parseo desde el sımbolo deinicio S hacia abajo (a las hojas) de acuerdo a la gramatica. Tipo deparseo EXPECTATION-DRIVEN

BOTTOM-UP: genera arboles de parseo a partir de las palabras de laoracion de entrada hacia arriba, aplicando las reglas de la gramatica.Tipo de parseo DATA-DRIVEN


Ejemplo de busqueda Top-Down (en paralelo)


Ejemplo de busqueda Bottom-up


Top-down vs Bottom-up

TOP-DOWN:

No pierde tiempo buscando en arboles que no empiezan en S

Pierde tiempo en arboles que no son consistentes con la entrada

Sufre de recursion a la izquierda (left-recursion)

BOTTOM-UP:

Desperdicia tiempo y recursos en arboles que no llegan a S

Forma arboles consistentes con la entrada


Busqueda no-en-paralelo

Cuando no es posible examinar todas las alternativas en paralelo (e.g.cantidad de memoria insuficiente), se consideran otras alternativas:

1 Que nodo en el espacio de busqueda se expande primero

2 Que regla gramatical aplicable se expande primero

3 Que nodo hoja en un arbol de parseo se expande a continuacion


Parsing Top-down, Depth-first, Left-to-right

1 Depth-first: cuando el arbol explorado es inconsistente con lagramatica, se regresa al ultimo arbol generado no explorado

2 Las regla gramaticales aplicables se expanden de acuerdo a su ordentextual en la gramatica definida

3 Left-most: el nodo hoja mas a la izquierda no expandido del arbolexplorado, se expande primero


Ejemplo Top-down, Depth-first, Left-to-right (1)

Does this flight include a meal?


Top-down, Depth-first, Left-to-right (2)


Problemas en parseo

Ambiguedad

Analizar mas de una vez (reparsing)


Ambiguedades estructurales comunes

Ambiguedad en COORDINACIONI old (men and women)I (old men) and women

Ambiguedad en COLOCACION (ATTACHMENT)I Ambiguedad en la colocacion del gerundio VP

I saw the Eiffel Tower flying to Paris

I Ambiguedad en la colocacion de PPI shot an elephant in my pajamas


Ambiguedad en colocacion (PP)


Reparsing

Ejemplo: Analizar con un parser top-down la NP:A flight from Indianapolis to Houston on TWA

Con la gramatica:I NP ⇒ Det NominalI NP ⇒ NP PPI NP ⇒ ProperNoun


Reparsing (2)


Soluciones al problema de ambiguedad

Parsers estadısticos

Uso de semantica

Programacion dinamica


Gramatica libre de contexto probabilıstica (PCFG)

PCFG se define como < N,Σ,P, S ,D >

D es una funcion que agrega una probabilidad condicional a cadaregla en P: A→ β[p]

D expresa la probabilidad p de que un sımbolo no-terminal A seaexpandido a la secuencia β: P(A→ β|A)

Esto es la probabilidad condicional de una expansion dado elno-terminal A

Todas las posibles expansiones de un no-terminal deben sumar 1


Ejemplo PCFG


PCFG

La probabilidad de un parseo T es el producto de las probabilidadesde todas las reglas r usadas para expandir cada nodo n en el arbol deparseo:

P(T ,S) =∏n∈T

p(r(n))

Se escoge el parseo con la probabilidad mas alta: el mejor arbol parala oracion S del conjunto de arboles de parseo para S


Ejemplo arboles PCFG

“astronomers saw stars with ears”

http://www.mpi-inf.mpg.de/departments/d5/teaching/ss11/ie/slides/dat_ba_nguyen.pdf


http://www.mpi-inf.mpg.de/departments/d5/teaching/ss11/ie/slides/dat_ba_nguyen.pdf

PCFG: creacion de probabilidades

Se puede extraer una gramatica de un treebank comprimiendo losarboles de estructuras de frases con elementos etiquetados, junto coninformacion estadıstica asociada para eliminar la ambiguedad delanalisis

Para obtener una PCFG:I se crea una regla para cada arbol en el treebankI se estima la probabilidad de cada regla directamente del treebank:

F se acumula el conteo de la frecuencia para cada reglaF al final, se normalizan los conteos de forma que cada conjunto de reglas

con la misma categorıa a la izquierda sumen 1


Desventajas de PCFG

PCFG ignora la influencia del contexto sintactico y la seleccion depalabras

En Ingles, prevalecen mas las estructuras sintacticas en las ramasderechas que en las ramas izquierdas, pero PCFG no puede capturaresto mediante probabilidades


Desventajas de PCFG (2)

Por ejemplo, no puede modelar el hecho de que en

“There was some change in the order”

La PP “in the order” modifica a “some change”, mientras que en

“There was some change in the afternoon”

Una PP parecida (solo con una palabra diferente) modifica al verboprincipal

La probabilidad asociada a cada regla se estima independientementede las demas, dando como resultando que pequenas variantes de unamisma regla tengan probabilidades muy diferentes debido a la pocacantidad de datos


Parsing con programacion dinamica


Programacion dinamica (PD)

PD divide un problema en sub-problemas que almacena en una tabla

En parseo, se almacenan sub-arboles por cada componente encontrado

Parser con PD: Cocke-Younger-Kasami (CYK),Graham-Harrison-Ruzzo (GHR) y Earley

Un parser T-D estandar reanalizarıa 4 veces “A FLIGHT”, siempre dela misma manera

Un algoritmo de PD usa una tabla (CHART) para evitar repetir eltrabajo


Algoritmo de Earley

No sufre del problema de recursion a la izquierda (left-recursion)

Resuelve un problema exponencial en O(n3)

Resuelve reparsing


Chart

El algoritmo de Earley usa una tabla (chart) de tamano N+1, dondeN es la longitud de la entrada (secuencia de palabras)

Por cada posicion de la palabra en la oracion, hay una lista deESTADOS representando los arboles de parseo parciales generados


Estados

Un estado incluye dos clases de informacion: cuanto de cierta regla seha encontrado en la entrada y que posiciones estan cubiertasA −→ α, [X ,Y ]

Un estado contiene:I Un sub-arbol correspondiente a la regla gramaticalI informacion sobre el progresoI posicion del sub-arbol en la entrada

en la regla gramatical del estado se usa un punto que indica elprogreso del reconocimiento de la regla


Representacion grafica del chart

reglas de puntoVP −→ V NP•NP −→ DET • NominalS −→ •VP


Algoritmo

El algoritmo sigue ciclos a traves de la entrada sin backtracking, encada paso realiza tres operaciones:

I PREDICTOR: crea estados en el chart que representan prediccionesT-D

I COMPLETER: Mueve el punto a la derecha cuando se encuentra elcomponenete buscado

I SCANNER: lee la siguiente palabra (con POS tag) de la entrada

El parser termina satisfactoriamente si la entrada N+1 del chartcontiene el estado S −→ α•, [0,N]


Ejemplo de chart


Ejemplo de chart (1)


Parsing con DG


Gramatica de Dependencias (DG)

Se basa en la informacion sobre dependencias lexicas

Los componentes y las reglas de estructura de frases no sonfundamentales

La estructura sintactica de la oracion se describe unicamente enterminos de palabras y de relaciones binarias semanticas o sintacticasentre estas palabras


Parser con DG

Un parser DG tiene la forma de un conjunto de ligas con direccionentre palabras

Cada liga generalmente esta etiquetada con la funcion gramatical(por ejemplo, sujeto u objecto) que relaciona al dependiente con sugobernante

Un parseo de dependencias no agrupa las palabras en frases ni lasfrases jerarquicamente en arboles, sino que contiene relaciones entrepares de palabras


Parser con DG (2)

Las DGs pueden ser mas apropiadas para PLN que las gramaticas deestructuras de frases en ciertos casos:

En idiomas independientes del orden de las palabras en el cual laforma de expresar los argumentos de un predicado puede variar (e.g.Checo)

El analisis puede contener aspectos importantes de la estructurapredicado-argumento sin necesidad de conocer la estructura jerarquicade las frases


Parser con DG (3)

Para algunos fenomenos gramaticales se requieren dependenciasno-descriptivas (con ligas cruzadas), que no se pueden representar conarboles de estructuras de frases


Parser con DG (4)Hay una correspondencia directa entre el analisis de dependencias“descriptivo” y el analisis de estructuras de componentes, cuando seconoce informacion sobre:

I el “filtrado de los encabezados” (head percolation)I las equivalencias entre estructuras de frases y funciones gramaticales


Parser con DG (5)

Algunos parsers utilizan la correspondenica entre la dependenciasdescriptivas y los arboles de estructuras de frases, obteniendointernamente arboles de estructuras de frases y convirtiendolos aparsers de dependencias

Ejemplos de este tipo de parsers son: Alpino, C&C, RASP, Stanford, yXLE


Gramatica de ligas (Link Grammar LG)

En LG, cada palabra tiene asociada un conjunto de posibles tipos deligas, marcadas con la direccion en la que el gobernante/dependientedebe encontrarse

I was: SUBJ- & OBJ+I some: MOD+I change: MOD- & OBJ-

Cuando se realiza el parsing, todas las posibles ligaduras se exploran:

Los gobernantes no se distinguen de los dependientes (las ligas notienen dieccion)


Gramatica de dependencias funcionales (FDG)

Se etiqueta cada palabra con todos los posibles tipos de funciones

Se aplican reglas que introducen ligas entre tipos especıficos dentrode un contexto dado, y/o quitando otros tipos de funciones. E.g.

(@w =s0 (@SUBJ) (*–1 +FMAINV *R) (NOT *R CLB)(La palabra no es sujeto si el verbo principal esta a la izquierda y nohay lımites de la clausula)

was @+FMAINVsome @ADJ>change ——–@SUB @OBJ

opcionalmente se aplican reglas heurısticas para quitar las ligas menosprobables


Parsers parciales


Parsers parciales (shallow parsers o chunkers)

Identifican los componentes (e.g. NP, VB, VP), pero noespecıficamente su estructura interna ni su papel en la oracionprincipal

Algunas tareas de PLN no requieren de parsers completos (e.g. losalgoritmos IR solo extraen la suficiente informacion del texto parallenar un tipo de plantilla)

Los parsers parciales utilizan cascadas de FSA en lugar de gramaticascomplejas (deep grammars)

Usar FSAs hace que los PP sean muy eficientes

Los sistemas de estado finito no pueden modelar ciertos tipos dereglas recursivas, lo que provoca que los PPs no cubran ciertos casos


Chunkers

Los chunkers se usan para detectar entidades en textos

Segmentan y etiquetan secuencias de tokens

Los pedazos (chunks) producidos no se traslapan

Metodos usados: n-grams, expresiones regulares, machine-learning


Ejemplo de NLTK chunker

http://nltk.googlecode.com/svn/trunk/doc/book/ch07.html


http://nltk.googlecode.com/svn/trunk/doc/book/ch07.html

¿Parsers completos o parciales?

Parsers completos (deep grammar) son mas apropiados cuando:I es importante obtener una interpretacion precisaI se requiere un procesamiento semantico completoI la variedad de expresiones linguısticas es mayor que la cantidad de

datos de entrenamiento disponibleI la calidad de los resultados es facilmente comparada con un estandar

humano

Parsers parciales:I no se necesita conocer la estructura sintactica: e.g.: IE, reconocimiento

de entidades


Parsers (sw libre)

Charniak-Johnson parser:http://bllip.cs.brown.edu/resources.shtml

Link Grammar parser: http://www.link.cs.cmu.edu/link/

MaltParser (multilingual): http://maltparser.org/

MINIPAR:http://webdocs.cs.ualberta.ca/~lindek/minipar.htm

MSTParser:http://www.ryanmcd.com/MSTParser/MSTParser.html

RASP: http://www.informatics.sussex.ac.uk/research/groups/nlp/rasp/

Stanford Parser:http://nlp.stanford.edu/software/lex-parser.shtml

Conexor parser (no gratuito): http://www.connexor.com/nlplib/


http://bllip.cs.brown.edu/resources.shtml

http://www.link.cs.cmu.edu/link/

http://maltparser.org/

http://webdocs.cs.ualberta.ca/~lindek/minipar.htm

http://www.ryanmcd.com/MSTParser/MSTParser.html

http://www.informatics.sussex.ac.uk/research/groups/nlp/rasp/

http://www.informatics.sussex.ac.uk/research/groups/nlp/rasp/

http://nlp.stanford.edu/software/lex-parser.shtml

http://www.connexor.com/nlplib/

Chunkers

TreeTagger chunker: http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/

OpenNLP tools: http://sourceforge.net/apps/mediawiki/opennlp/index.php?title=Chunker

NLTK chunker: http://nltk.googlecode.com/svn/trunk/doc/api/nltk.chunk-module.html

GATE tools: http://gate.ac.uk/


http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/

http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/

http://sourceforge.net/apps/mediawiki/opennlp/index.php?title=Chunker

http://sourceforge.net/apps/mediawiki/opennlp/index.php?title=Chunker

http://nltk.googlecode.com/svn/trunk/doc/api/nltk.chunk-module.html

http://nltk.googlecode.com/svn/trunk/doc/api/nltk.chunk-module.html

http://gate.ac.uk/

Agradecimientos

Esta presentacion se inspiro y contiene algunos materiales de los cursos de:

Massimo Poesio: http://dces.essex.ac.uk/staff/poesio/

John Caroll: http://mitlab.hit.edu.cn/2011summerschool/related/parsing-John%20Carroll.pdf


http://dces.essex.ac.uk/staff/poesio/

http://mitlab.hit.edu.cn/2011summerschool/related/parsing-John%20Carroll.pdf

http://mitlab.hit.edu.cn/2011summerschool/related/parsing-John%20Carroll.pdf

adquisición de conocimiento usando técnicas de procesamiento de texto y red ... · 2012-03-10 ·...

Documents