PLN - Anotación automática de textos

Anotación automática

de textos: resolución

de ambigüedad

Diego Burgos

[email protected]

Programa de Idiomas

Facultad de Ciencias

Instituto Tecnológico Metropolitano – ITM

mailto:[email protected]

Anotación automática de textos:

resolución de ambigüedad 227/11/2008

Contenido

Introducción

Marco teórico y metodológico

Tipos de anotación

Métodos de anotación

Anotación morfosintáctica

Anotación semántica (WSD, clases léxicas)

Conclusiones



Introducción

Anotación = desambiguación

Ambigüedad:

“múltiples estructuras lingüísticas alternativas para

una entrada determinada” (Jurafsky & Martin,

2000)

11.5% types en el Brown corpus son ambiguos

40% tokens son ambiguos, muchos de ellos fáciles

de desambiguar. P. ej.: P(Prep|a) > P(N|a)



Introducción (2)

I made her duck.

Duck can be a verb or a noun (part of speech tagging)

her can be a dative pronoun or a possessive pronoun

(probabilistic parsing)

make it can mean create or cook (word sense

disambiguation)

make can be transitive, single direct object or ditransitive

make can take a direct object and a verb

I could have been eye or made could have been maid

(speech act interpretation)



Marco teórico y metodológico



Tipos de anotación

Morfosintáctica (pos)

Sintáctica (chunking, parsing)

Semántica (NER, WSD, roles)

Discursiva (dialogue act tagging)

Ad hoc



Tipos de anotación (2)

Morfosintáctica (pos):

The cross sections show: a) the D-4S engine

with direct and port injectors, and b) the 3GR-

FSE direct-injection D-4 version.




Morfosintáctica (pos):

The_DT cross_NN sections_VBZ show_NN:_:

a_DT )_) the_DT D-4S_NNP engine_NN

with_IN direct_JJ and_CC port_JJ

injectors_NNS, and_CC b_NN )_) the_DT

3GR-FSE_JJ direct-injection_JJ D-4_NNP

version_NN._.




Sintáctica (chunking, parsing)

([ The_DT cross_NN ]) (( sections_VBZ )) ([

show_NN ]):_: a_DT )_) ([ the_DT D-

4S_NNP engine_NN ]) with_IN ([ direct_JJ

and_CC port_JJ injectors_NNS ]) ,_,

and_CC ([ b_NN ]))_) ([ the_DT 3GR-

FSE_JJ direct-injection_JJ D-4_NNP

version_NN ])._.

!




Semántica (NER, WSD, roles temáticos,…)

Identificación de nombres y relaciones de entidades en el texto: Dexi Argüelles debutó en el reciente Salón del

Automóvil de Frankfurt.

Desambiguación léxica de sentidos: Dexi Argüelles debutó en el reciente Salón del

Automóvil de Frankfurt= recinto

= evento

= persona = evento

= lugar



Métodos de anotación

Lingüísticos: Basados en reglas o en información lingüística

Probabilísticos: Probabilidades y modelos matemáticos

Regla de Bayes

Modelos ocultos de Markov (HMM)

Híbridos o mixtos: Combinación de lingüísticos y probabilísticos

Transformation-Based Tagging

Máxima verosimilitud: asignar la etiqueta más frecuente



Anotación morfosintáctica (pos t)

Es el proceso de asignar una marca (etiqueta oanotación) de categoría gramatical o sintáctica a cadapalabra en un corpus.

en/P el/AFS modalidad/N5-FS a/N4666 =/Z el/AFS caja/N5-6Shacer/VDR3S- el/AMP cambio/N5-MP automáticamente/D6 en/Pfunción/N5-FS de/P el/AMS programa/N5-MS drivelogic/N4666=/Z de/P el/AMS estilo/N5-MS de/P manejo/N5-MS =/Z de/Pel/AFS velocidad/N5-FS y/C de/P el/AFS posición/N5-FS de/Pel/AMS pedal/N5-MS de/P el/AMS acelerador/N5-MS =/Z



Algunas aplicaciones pos t

Aporte importante de información sobre

una palabra (o categoría gram.) y sus

vecinos.

Síntesis y reconocimiento del habla:

Ejemplo para el inglés:

Objetc (noun) = /'äb-jikt/

Object (verb) = /&b-'jekt/



Algunas aplicaciones pos t (2)

Recuperación de información: Stemming

la pos puede indicar los sufijos que puede tomar una raíz.

Clasificación de documentos Detección de sustantivos como palabras clave

Lingüística de corpus: Frecuencia y representatividad de patrones

sintácticos



Juegos de etiquetas (tag sets)

C7: 146 http://www.natcorp.ox.ac.uk/docs/bnc2guide.htm

Brown corpus: 87 http://icame.uib.no/brown/bcm.html

Penn Treebank: 45 http://www.cis.upenn.edu/~treebank/

Elección:

especificidad del marcaje

capacidad de caracterización

Eficiencia < 100%

http://www.natcorp.ox.ac.uk/docs/bnc2guide.htm

http://icame.uib.no/brown/bcm.html

http://www.cis.upenn.edu/~treebank/



Preproceso del corpus

Marcas SGML <doc_codi g20950>: <s>Afirmó que la fuerza de frenado de un

vehículo depende de <num>10</num> factores</s>

Tokenización la

fuerza

…

* Lematización: afirmar que el fuerza de frenado de un vehículo depender de diverso factor

Desambiguar

puntuación



Entrada y salida pos t

Entrada (input):

texto

juego de etiquetas

Salida:

cada palabra con la mejor etiqueta según

cada sistema.



Métodos: basados en reglas

Diccionarios (lexicones): Para asignar a cada palabra una lista de posibles

categorías.

Reglas manuales: Para desambiguar y definir una etiqueta de la lista

generada por el diccionario.

Ej.: Constraint Grammar 56.000 entradas en el lexicon

3.744 reglas



Métodos: basados en reglas (2)




Asignación de etiquetas John had shown that salivation . . .

John JOHN N NOM SG PROPER

had HAVE V PAST VFIN SVO

HAVE PCP2 SVO

shown SHOW PCP2 SVOO SVO SV

that ADV

PRON DEM SG

DET CENTRAL DEM SG

CS

salivation N NOM SG

. . .




ADVERBIAL-THAT RULE “it isn‟t that odd”

Dada la entrada: “that”

if

(+1 A/ADV/QUANT); /* si la próx. palabra es adj, adv. o cuant. */

(+2 SENT-LIM); /* y después hay fin de oración */

(NOT -1 SVOC/A); /* y la palabra anterior no es un verbo como */

/* „consider‟ que permite adjs como comp. de objeto */

/* “I consider that odd” */

then elimina non-ADV tags

else elimina ADV tag

Karlsson, F., Voutilainen, A., Heikkil¨a, J., and Anttila, A. (Eds.). (1995b). Constraint Grammar: A Language- Independent System for Parsing Unrestricted Text. Mouton de Gruyter, Berlin.



Métodos: probabilísticos (HMM)

HMM simplificado para la anotación

mofosintáctica

Uso de probabilidades

Inferencia bayesiana (T. Bayes, desde 1763)

Dado un conjunto de observaciones O y un

conjunto de clases C, asignar una clase a cada

observación.



Métodos: (HMM) (2)

Dada la oración:

“Secretariat is expected to race tomorrow”

¿Cuál es la mejor secuencia de etiquetas que le

corresponde de todas las posibles?

Secuencia de n palabras =

Secuencia de n etiquetas =

Seleccionar la secuencia que maximice :



Métodos: (HMM) (3)

Para computar utilizamos la regla

bayesiana que fragmenta una probabilidad

condicional en otras tres probabilidades:

Podemos obviar el denominador:



Métodos: (HMM) (4)

Prob.Cond. Prob. a priori.

HMM asume: a) P de una palabra depende

de su categoría pero no de otras palabras

o categorías:



Métodos: (HMM) (5)

HMM asume: b) P de una categoría

depende sólo de la categoría anterior

(bigramas):



Métodos: (HMM) (6)

P. ej.: en español, los determinantes suelen

preceder a los nombres pero no tanto a los

adjetivos, por eso P(N|Det) > P(Adj|Det)

Prob. de

transición

Prob. de una

palabra



Métodos: (HMM) (7)

La estimación de la probabilidad de transición

se estima con base en un corpus anotado (e.g.,

Brown):



Métodos: (HMM) (8)

Estimación de probabilidad de una palabra dada

una etiqueta. P. ej. P(is|VBZ):



Métodos: HMM. Ejemplo

Desambiguar “race”

Secretariat/NNP is/BEZ expected/VBN to/TO

race/VB tomorrow/NR

People/NNS continue/VB to/TO inquire/VB

the/AT reason/NN for/IN the/AT race/NN

for/IN outer/JJ space/NN



Métodos: HMM. Ejemplo (2)

P(NN|TO) = .00047

P(VB|TO) = .83



Métodos: formalización de HMM

HMM: autómata de estados finitos (=

conjunto de estados y conjunto de

transiciones entre los estados ambos

basados en observaciones)

Ponderado (weighted): cada arco se asocia

con una probabilidad.

Cadena de Markov: para secuencias no ambiguas

HMM: para secuencias ambiguas (e.g., anotación)



Métodos: formalización HMM (2)

Un HMM está especificado por:

Q = q1q2 . . .qN conjunto de estados

A = a01a02 . . .an1 . . .ann matriz de probabilidad de transición A, cada aij representa la probabilidad de moverse del estado i al estado j,

O = o1o2 . . .oN conjunto de observaciones, cada una tomada de un vocabulario V = v1,v2, ...,vV .

B = bi(ot ) Conjunto de probabilidades de emisión; cada una expresa la probabilidad de que una observación ot se genere desde el estado i.

q0,qend estado especial de inicio y fin que no se asocia con las observaciones

En resumen, dos probabilidades: transición (a priori) y observación (condicionada)



Métodos: HMM. Adicionales

Algoritmo de Viterbi

Trigramas

…



Métodos: transformation-based

Combinación de métodos basados en

reglas y estocásticos

Las reglas se inducen automáticamente de

los datos

Supervisado (i.e., necesita corpus anotado)

Paradigma TBL según Terry Harvey



Métodos: TBL (2)

¿Cómo se asignan las etiquetas?

Anotación mediante máxima verosimilitud

P(NN|race) = .98

P(VB|race) = .02

Se aplican reglas de transformación Cambiar NN a VB cuando la etiqueta anterior es TO

Se reasignan etiquetas

Iterar pasos 2 y 3



Métodos: TBL (3)

El número de transformaciones se limita

mediante plantillas. Cambia “a” a “b” cuando:

La etiqueta + 1 (-1) es z.

La etiqueta +2 (-2) es z.

La etiqueta +2 ó +1 (-2 ó -1) es z.

Una de las etiquetas anteriores o posteriores es z.

La etiqueta +1 es w y la etiqueta -1 es z.

La etiqueta -1 (+1) es z y la etiqueta -2 (+2) es w.



Otros

Evaluación y análisis del error

Tópicos avanzados

Tokenización

Palabras y etiquetas desconocidas

Particularidad de otros idiomas

Combinación de anotadores



Herramientas

Machinese (http://www.connexor.com/)

POS y sintáctico

NER (Inglés, genera pdf)

6 idiomas, incluido el español

Versión en línea

Versión gratuita para investigación

http://www.connexor.com/



Herramientas (2)

TreeTagger (http://www.cele.nottingham.ac.uk/~ccztk/treetagg

er.php)

POS

7 idiomas, incluido el español

Versión en línea

Versión gratuita para investigación

http://www.cele.nottingham.ac.uk/~ccztk/treetagger.php

http://www.cele.nottingham.ac.uk/~ccztk/treetagger.php



Herramientas (3)

QTag (http://www.english.bham.ac.uk/staff/omason/softw

are/qtag.html)

POS

Probabilístico

Independiente de lengua, aunque ahora sólo

tiene recursos para el inglés

Gratuito

http://www.english.bham.ac.uk/staff/omason/software/qtag.html





Herramientas (4)

Stanford Log-linear Part-Of-Speech Tagger download

(http://nlp.stanford.edu/software/postagger-2006-05-21.tar.gz)

POS

Probabilístico

Independiente de lengua, aunque ahora sólo tiene recursos para el inglés

Java

Gratuito

http://nlp.stanford.edu/software/postagger-2006-05-21.tar.gz









Herramientas (5)

Tatoo

POS

Probabilístico

Independiente de lengua, aunque ahora sólo

tiene recursos para el inglés

Gratuito



Herramientas (6)

FreeLing

POS, sintáctico, NER, sentidos de EWN

Multilingüe, incluye el español

Gratuito



Anotación semántica

Desambiguación de sentidos: examinar

palabras en contexto para determinar con qué

sentido se usa cada una.

Similitud léxica, hiperonimia, hiponimia, y

meronimia: relaciones léxicas (WordNet).

Papeles semánticos: anotación de agente,

tema, instrumento respecto de predicados

determinados.



WSD

Homonimia

Polisemia

Algunas aplicaciones Traducción automática (bass = (lubina|bajo)

Respuestas a preguntas

Recuperación de información

Clasificación de textos (MeSH - UMLS)

Síntesis del habla



WSD (2)

Supervisado Corpus de entrenamiento etiquetado con los

sentidos correctos Muestra:

Line, hard, serve, interest

http://www.cs.toronto.edu/~smm/WebPages/software.html

Textos completos: SemCor (700K palabras, 200K con WordNet 1.6)

http://multisemcor.itc.it/semcor.php

SENSEVAL

http://www.senseval.org/

http://www.cs.toronto.edu/~smm/WebPages/software.html

http://multisemcor.itc.it/semcor.php

http://www.senseval.org/



WSD supervisado (3)

Extracción de rasgos Indicios del sentido de una palabra

¿cuál será el tamaño indicado de la ventana para desambiguar el sentido de una palabra?

Es necesario el preproceso: pos tagging

lematización

análisis sintáctico

Vector de rasgos



WSD supervisado (4)

Rasgos:

Colocacional: situación exacta de los vecinos

“En la noche, la guitarra y el bajo sonaron con

contundencia en el escenario”

[wi−2,POSi−2,wi−1,POSi−1,wi+1,POSi+1,wi+2,POSi+2]

[y, CJC, el, DET, sonar, V, con, P]



WSD supervisado (5)

Rasgos: “Bolsa de palabras” (bag-of-words): conjunto

desordenado de palabras (clases abiertas) en cuyocontexto (ventana n) se evalúa la presencia de lapalabra a desambiguar. P. ej

12 palabras más frecuentes de un conjunto de oraciones quecontienen la palabra bajo (WSJ):

[pesca, grande, sonido, sonar, volar, biela, libra, doble, correr,jugar, contundencia, banda]

[0,0,0,1,0,0,0,0,0,0,1,0]



WSD supervisado (6)

Clasificador Naive Bayes:

Dado un vector, cuál es el sentido más probable para

ese vector:

Datos que

asocian vectores

específicos con

cada sentido son

escasos



WSD supervisado (7)

En el corpus de entrenamiento abundan los

pares atributo-valor en el contexto de sentidos

específicos, lo que permite suponer la

independencia de los atributos:La probabilidad de un

vector dado un sentido =

producto de las

probabilidades de cada

uno de sus atributos



WSD supervisado (8)

El entrenamiento del Naive Bayes consiste en

estimar cada una de estas probabilidades:

P a priori de cada sentido:

P a priori de cada atributo:



WSD supervisado (9)

Así, si un rasgo colocacional como

[wi−2 = guitarra]

ocurre 3 veces para el sentido bajo1 y el sentido bajo1

ocurre 60 veces, P( f j |s) = 0.05.

Más específicamente, tomamos la palabra en contexto,extraemos los rasgos, computamos:

para cada sentido, y generamos el sentido asociado con elpuntaje más alto.



WSD supervisado (10)

¿Y si en el corpus de prueba la palabra coocurre con

otra que no estaba en el corpus de entrenamiento?

P( f j |s) = 0 smoothing (suavizado)

LaplaceP( f j |s) = (3 + 1) / (60 + w)



WSD Lesk

Diccionarios y tesauros

Algoritmo de Lesk: selecciona el sentidocuya definición comparta el mayor número depalabras con el contexto de la palabra adesambiguar. P. ej., desambiguar bank en:

“The bank can guarantee deposits will eventuallycover future tuition costs because it invests inadjustable-rate mortgage securities.”



WSD Lesk (2)

Dados los siguientes dos sentidos de WordNet:

El sentido 1 tiene dos palabras (cat. abiertas) que coincidencon el contexto, i.e., deposits y mortgage. En el sentido 2 nohay coincidencias. Se asigna el sentido 1.

Este algoritmo depende de la longitud de las definiciones en eldiccionario (véanse extensiones del algoritmo)



WSD Similitud entre sentidos

Dos palabras (sentidos) son más similares

sin comparten más rasgos semánticos y

hay más distancia entre ellas, mientras

menos rasgos compartan.

Basado en diccionarios (tesauros o redes

semánticas WordNet)

Distribucional



WSD Similitud entre sentidos (2)

Basado en diccionarios

Hiponimia (is-a) e hiperonimia

{vehicle}

{conveyance; transport}

{car; auto; automobile; machine; motorcar}

{cruiser; squad car; patrol car; police car; prowl car} {cab; taxi; hack; taxicab; }

{motor vehicle; automotive vehicle}

{bumper}

{car door}

{car window}

{car mirror}

{hinge; flexible joint}

{doorlock}

{armrest}

hyperonym

hyperonym

hyperonym

hyperonymhyperonym

meronym

meronym

meronym

meronym




Medida por longitud de rutas

ruta




EuroWordNet

skin

hair

body-

covering

Top

1stOrderEntity 2ndOrderEntity

SituationType SituationComponent

Living

Location ExperiencePhysicalStatic DynamicNaturalCovering Part Group

Composition OriginFunction Form

Etc….Etc.

body

part

cell

muscle

organ

Object

Human

Mental

Direction

distance

spatial property

spatial relation

course

path

change of position

divide

locomotion

motion

feeldesire

disturbance

emotion

feeling

humor

pleasance

church

company

institute

organization

party

union

human

adult

adult female

adult male

child

native

offspring




Distribucional:

El significado de una palabra estárelacionado con la distribución de laspalabras que la rodean. P. Ej

A bottle of tezgüino is on the table.

Everybody likes tezgüino.

Tezgüino makes you drunk.

We make tezgüino out of corn.




Adicionales:

Extensiones de estos algoritmos

Evaluación



Papeles semánticos



Otros

Métodos no supervisados

Técnicas de aprendizaje automático



¡Gracias!

PLN - Anotación automática de textos

Technology

Transcript of PLN - Anotación automática de textos