Procesamiento de Lenguaje Natural TEMA 2 Palabras Enrique Alfonseca Pilar Rodr´ıguez

´ Indice

2

• An´ alisis morfol´ ogico

• Morfolog´ıa • Morfolog´ıa computacional

• PoS tagging

• • • •

Introducci´ on Listas de transformaci´ on Modelos de Markov Otros

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (I) – Definiciones

Morphology Introducci´ on Computacional

PoS tagging

´ındice

3

Morfolog´ıa Es el estudio de la estructura dentro de las palabras: • Mecanismos para crear nuevas palabras. • Mecanismos para utilizar las palabras. Morfema Es la unidad m´ as peque˜ na a la que se le puede asignar significado. Ra´ız, Lema Es el morfema que expresa un concepto sem´ antico (puerta). Alomorfos Son los morfemas que aportan el mismo significado a la palabra (-i, -is en servi, patris).

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (II) – Definiciones

Morphology Introducci´ on Computac.

PoS tagging

´ındice

4

Morfema libre Es el que puede constituir una palabra per se (casa). Morfema ligado Es el que s´ olo ocurre en combinaci´ on con otros(-s para el plural). • En algunos idiomas (ingl´ es, espa˜ nol, etc.) han de ocurrir asociados por delante o por detr´ as a la ra´ız. • En otros (´ arabe, hebreo, etc.) se emplean operaciones no concatenativas (por ejemplo, variar vocales).

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (III) Clasificaci´ on de lenguajes

Morphology Introducci´ on Computac.

PoS tagging

´ındice

5

Inflectional languages (Lenguajes flexionales): distintos contenidos de significaci´ on se juntan en un solo morfema ligado, que se afija al lema (Lenguas indoeuropeas). Isolating languages (Lenguajes aislantes): no hay morfemas ligados (Chino mandar´ın). Agglutinative languages (Lenguajes aglutinantes): todos los morfemas ligados son afijos que se van engarzando unos con otros para formar la palabra (Fin´ es, Turco). Polysynthetic languages (Lenguajes polisint´ eticos): expresan m´ as informaci´ on estructural de manera morfol´ ogica (lenguas Inuit). Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (IV) Morfolog´ıa flexional

Morphology Introducci´ on Computac.

PoS tagging

´ındice

6

Determinados contextos sint´ acticos exigen que la palabra lleve una cierta inflexi´ on determinando su funci´ on gramatical. Todas las formas de una palabra se llaman el paradigma: Nominativo Vocativo Acusativo Genitivo Dativo Ablativo

Singular servus serve servum servi servo servo

Plural servi servi servos servorum servis servis

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (V) Morfolog´ıa flexional

Morphology Introducci´ on Computac.

PoS tagging

´ındice

7

• Funcional: un afijo act´ ua como una funci´ on (p. ej., el sufijo -s que forma el plural). • Preserva la categor´ıa sint´ actica de la palabra. • Completa: Con raras excepciones, todas las palabras tienen todas las formas de su paradigma (llover). • Productiva: nuevas palabras autom´ aticamente utilizan las reglas de inflexi´ on. Seg´ un la inflexi´ on, las palabras se clasifican como: • Part´ıculas o palabras sin inflexi´ on (preposiciones, conjunciones, adverbios...) • Verbos, que siguen una conjugaci´ on. • Nominales, o palabras que siguen declinaciones (nombres, adjetivos y pronombres). Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (VI) Morfolog´ıa derivacional Morphology Introducci´ on Computac.

PoS tagging

´ındice

8

Derivaci´ on es un proceso mediante el cual se crean palabras nuevas. Se realiza base: comer eat essen

uniendo un morfema ligado a una forma comest-ible eat-able ess-bar

concebir conceive absehen

conceb-ible conceiv-able abseh-bar

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (VII) Morfolog´ıa derivacional

Morphology Introducci´ on Computac.

PoS tagging

´ındice

9

• Relacional: el mismo sufijo puede tener resultados diferentes (criticise vs. localise). • No necesariamente preserva la categor´ıa sint´ actica. • Incompleta: no todas las palabras pueden acomodar el mismo conjunto de afijos. Por ejemplo, -ible no es aplicable a todos los verbos). En ingl´ es, -ity s´ olo se aplica a palabras de origen latino (rarity, gravity, *reddity, *weirdity). • Recursiva: hospital → hospitalizar → hospitalizaci´ on → pseudohospitalizaci´ on Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (VIII) Afijaci´ on Un afijo es un morfema ligado que consta de un conjunto de fonemas. Morphology Introducci´ on Computac.

Prefijaci´ on: Se da cuando se a˜ nade un afijo (prefijo) delante del lema. gramatical → a-gramatical

PoS tagging

Sufijaci´ on: Se da cuando se a˜ nade un afijo (sufijo) detr´ as del lema: gram´ atica → gramatic-al ´ındice

10

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (IX) Afijaci´ on

Morphology Introducci´ on Computac.

PoS tagging

´ındice

11

Circunfijaci´ on: Es la combinaci´ on de la prefijaci´ on y la sufijaci´ on que conjuntamente expresan una caracter´ıstica: sagen (decir ) → ge-sag-t (dicho) (Alem´ an) Infijaci´ on: Se da cuando la posici´ on del afijo depende de alguna condici´ on fonol´ ogica, por lo que puede aparecer dentro del lema. fikas (fuerte) → fumikas (ser fuerte) (Bontoc, Filipinas)

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (X) Afijaci´ on

Morphology Introducci´ on Computac.

PoS tagging

Reduplicaci´ on: Se da cuando se copia parte o todo el lema, posiblemente con variaciones fon´ eticas. • En Javan´ es, expresa el repetitivo habitual (soler): bali regresar bolabali regresar a menudo dolan recrear dolandoln recrear a menudo adus ba˜ narse odasadus ba˜ narse a menudo • En Yidin (Australia), expresa plural: mulari persona iniciada mulamulari gindalba lagarto gindalgindalba • En Amharic (Etiop´ıa) expresa el frecuentativo.

´ındice

12

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (XI) Fen´ omenos no aglutinantes Morphology Introducci´ on Computac.

PoS tagging

´ındice

13

Ablaut: Fen´ omeno heredado del protoindoeuropeo, conlleva la modificaci´ on de alguna vocal del lema como proceso morfol´ ogico. mann (hombre), Anglosaj´ on: Nominativo Acusativo Genitivo Dativo

Singular mann mann mannes menn

Plural menn menn manna mannum

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (XII) Fen´ omenos no aglutinantes Morphology Introducci´ on Computac.

PoS tagging

´ındice

14

Umlaut: Consiste en que alguna vocal del lema se convierte en la vocal frontal equivalente: Alem´ an: Singular Mutter Garten

Plural M¨ utter G¨ arten

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (XIII) Fen´ omenos no aglutinantes

Morphology Introducci´ on Computac.

Morfolog´ıa lema-“plantilla”: Se da en lenguajes sem´ıticos. La ra´ız consiste en de dos a cuatro consonantes, y las vocales indican las carater´ısticas morfol´ ogicas: ´ rabe ptr (escribir): A

PoS tagging

´ındice

15

Activa katab kattab ka:tab taka:tab nka:tab staktab

Pasiva kutib kuttib ku:tib tuku:tib nku:tib stuktib

Verbo escribir causar que escriba mantener correspondencia escribirse m´ utuamente suscribir dictar

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa (XIV) Idiomas aglutinativos

Morphology Introducci´ on Computac.

PoS tagging

´ındice

16

Los afijos se van engarzando unos a otros alrededor del lema. ´ ste comi´ Kivunjo (lengua Bant´ u) N¨ a¨ık`ımly` ´ ı¨ı` a (E o eso para beneficio de aquel): N Marcador indicando que la palabra es el tema de la conversaci´ on. ¨ a Marcador de concordancia con el sujeto (humano singular), de entre los 16 g´ eneros. ¨ı Tiempo presente (otros tiempos son hoy, hoy antes de ahora, ayer, no antes de ayer, en el pasado remoto, habitualmente, etc.) k`ı Marcador de concordancia con el complemento directo (g´ enero clase 7) m ´ Marcador de concordancia con el beneficiado por la acci´ on. ly`ı El verbo, comer. ¨ı Marcador “aplicativo”, indica que hay un actor m´ as en la acci´ on (en este caso, el beneficiado). ` a Modo indicativo. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa Computacional (I) Motivaci´ on

Morphology Introducci´ on Computac.

PoS tagging

´ındice

17

• An´ alisis: obtenci´ on de la estructura interna de las palabras (lema y afijos) – Para comprobar concordancia en an´ alisis sint´ acticos. – Para correctores ortogr´ aficos. – Para poner guiones al final de las l´ıneas. – Para indexar documentos por lemas de las palabras. – Para separar palabras en lenguajes sin blancos (chino, japon´ es...) • Generaci´ on: obtenci´ on de palabras con inflexi´ on para generaci´ on de textos. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa Computacional (II) Lexic´ on completo

Morphology Introducci´ on Computac.

PoS tagging

´ındice

18

Consiste en tener un lexic´ on completo con todas las palabras del idioma en todas sus formas posibles. • Simple. • Aplicable a todos los fen´ onemos posibles (afijaci´ on, ablaut, etc.) • Redundancia. • Inabilidad de tratar formas que no est´ en en el lexic´ on. • Algunos lenguajes (Kivunjo) pueden tener alrededor de medio mill´ on de formas para cada palabra. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa Computacional (III) Lexic´ on de lemas y reglas Consiste en tener un lexic´ on con todos los lemas de un lenguaje, y un conjunto de reglas de inflexi´ on. Morphology Introducci´ on Computac.

PoS tagging

´ındice

19

Problemas: • Palabras muy comunes no suelen seguir los paradigmas (el verbo ser, verbos irregulares). • Excepciones (y arca´ısmos), como los verbos fuertes en ingl´ es: give-gave-given • Reglas fonol´ ogicas que alteran los sufijos y los lemas: in+batible → imbatible • Los algoritmos de an´ alisis y de generaci´ on son totalmente diferentes. • Los algoritmos son muy espec´ıficos de cada idioma. Procesamiento de Lenguaje Natural 2004 - LAT X slides E

Morfolog´ıa Computacional (IV) Morfolog´ıa de estado finito Morphology Introducci´ on Computac.

PoS tagging

´ındice

20

Muchas reglas morfol´ ogicas se pueden expresar con expresiones regulares. Por tanto, se pueden codificar como transductores finitos deterministas. Formalismos: • Morfolog´ıa a dos niveles. • Morfolog´ıa paradigm´ atica. • Sistema DATR.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morfolog´ıa Computacional (V) Morfolog´ıa a dos niveles

Morphology Introducci´ on Computac.

PoS tagging

• Existen dos niveles: el de la palabra tal como se escribe o pronuncia, y el nivel l´ exico, con diacr´ıticos. • Los diacr´ıticos # y + son los separadores de palabras y morfemas, respectivamente. • Un conjunto de reglas indican c´ omo se alterna entre los dos niveles (sirven tanto para an´ alisis como para generaci´ on). #bliss+s# 0blisses0 +:e ⇐ {s x z [{s c} h]}: s; (Koskenniemi, 1984)

´ındice

21

Procesamiento de Lenguaje Natural 2004 - LATEX slides

´ Indice

22

• An´ alisis morfol´ ogico

• Morfolog´ıa • Morfolog´ıa computacional

• PoS tagging

• • • •

Introducci´ on Listas de transformaci´ on Modelos de Markov Otros

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on

Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

23

Las palabras pueden agruparse en clases en funci´ on de su comportamiento sint´ actico, llamadas categor´ıas gramaticales o partes del lenguaje. Por ejemplo, • los nombres generalmente designan personas, lugares, cosas, y otros conceptos f´ısicos y abstractos, • los verbos suelen utilizarse para designar acciones y procesos; • y los adjetivos describen propiedades y estados de los nombres.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (II)

Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

24

Las palabras de las mismas categor´ıas gramaticales realizan, en general, las mismas funciones sint´ acticas en el lenguaje. Por ejemplo, los nombres pueden actuar de ra´ız o modificador en los sintagmas nominales, y de sujeto en las oraciones.

  pr´ıncipe     guerrero      sastrecillo El valiente enano    elfo      fontanero    Shrek

salv´ o a la princesa.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (III)

Morphology

PoS tagging

Introducci´ on

Clases abiertas y cerradas Se dice que una parte del lenguaje es una clase abierta cuando continuamente se est´ an a˜ nadiendo nuevos miembros a esa clase: • Nombres • Verbos • Adjetivos • Adverbios

TL Markov Otros

´ındice

25

’Twas brillig, and the slithy toves Did gyre and gimble in the wabe. All mimsy were the borogroves And the mome raths outgrabe.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Long ago, in a finite state far away, there lived a JOVIAL character named Jack. Jack and his relations were poor. Often their hash table was bare. One day Jack’s parent said to him, ”Our matrices are sparse. You must go to the market to exchange our RAM for some BASICs.” She compiled a linked list of items to retrieve and passed it to him. Morphology

PoS tagging

Introducci´ on TL Markov Otros

So Jack set out. But as he was walking along a path, he met the traveling salesman. ”Whither dost thy flow chart take thou?” prompted the salesman in high-level language. ”I’m going to the market to exchange this RAM for some chips and Apples,” commented Jack. ”I have a much better algorithm. You needn’t join a queue there; I will swap your RAM for these magic kernels now.” Jack made the trade, then backtracked to his house. But when he told his busy-waiting parent of the deal, she became so angry she started thrashing. ”Don’t you even have any artificial intelligence? All these kernels together hardly make up one byte,” and she popped them out the window... – Mark Isaak, ”Jack and the Beanstack”.

´ındice

26

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (V)

Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

27

Clases abiertas y cerradas Clases cerradas son aquellas que permanecen invariables en largos periodos de tiempo: • Preposiciones • Determinantes • Pronombres • Conjunciones Pueden variar en largos per´ıodos de tiempo: cabe, mag¨ uer, ... Dialectales: a m´ as a m´ as, todo y que

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morphology

PoS tagging

Introducci´ on (VI) Partes del lenguaje Es posible subdividirlas tanto como haga falta, en funci´ on de las necesidades. Las etiquetas de PoS del Brown Corpus, las del Penn Treebank y las del BNC son las m´ as utilizadas. part-of-speech noun

Introducci´ on TL

adjective

Markov Otros

´ındice

28

verb

morphological variation singular plural proper, singular proper, plural normal comparative superlative base non-3rd, present tense 3rd person, present past tense past participle gerund

tag NN NNS NNP NNPS JJ JJR JJS VB VBP VBZ VBD VBN VBG

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (VII) Partes del lenguaje Morphology

part-of-speech personal pronoun

PoS tagging adverb Introducci´ on TL Markov Otros

´ındice

29

predeterminer determiner preposition conjunction ...

morphological variation nominative genitive interrogative interr., gen. normal comparative superlative interrogative

copulative ...

tag PRP PRP$ WP WP$ RB RBR RBS WRB PDT DT IN CC ...

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (VIII)

Morphology

PoS tagging

Introducci´ on TL Markov

Etiquetado de las partes del lenguaje • Consiste en etiquetar cada palabra con la parte del lenguaje a la que pertenece. • Se considera un paso previo al an´ alisis sint´ actico. Ambig¨ uedad: TimeN N fliesV BZ likeIN anDT arrowN N TimeN N fliesN N S likeV BP anDT arrowN N TimeV B fliesN N S likeIN anDT arrowN N TimeN N fliesN N S likeIN anDT arrowN N

Otros TheDT horseN N racedV BD pastIN theDT barnN N fell− . TheDT horseN N [racedV BP pastIN theDT barnN N ] fellV BD . ´ındice

30

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (IX) Fuentes de informaci´ on • Informaci´ on l´ exica: – Palabras que acaban en ando suelen ser verbos en gerundio. Morphology – Palabras que acaban en s son a menudo nombres en plural. PoS tagging

• Contexto: – Palabras precedidas por una preposici´ on suelen ser determinantes o nombres.

Introducci´ on

– Palabras precedidas por un art´ıculo, nombres.

TL Markov Otros

• Etiquetas posibles para cada palabra: – Cada palabra puede tomar s´ olo ciertas etiquetas en cada lenguaje (p.ej., bebida como nombre o participio). – La asignaci´ on a cada palabra de su etiqueta m´ as frecuente: 90% precisi´ on (entrenado en el mismo corpus).

´ındice

31

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morphology

PoS tagging

Introducci´ on TL

Introducci´ on (X) Procedimientos: • Listas de transformaci´ on. • Modelos de Markov • Otros (Entrop´ıa M´ axima, ´ arboles de decisi´ on, etc.)

Markov Otros

´ındice

32

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con listas de transformaci´ on (I) (Brill, 1995) Morphology

Una lista de transformaci´ on (transformation list) es una lista de reglas con la siguiente sintaxis: PoS tagging

If precondition then change tag to XXX Introducci´ on TL Markov Otros

´ındice

33

El funcionamiento es el siguiente: 1. Asignar una etiqueta inicial a cada palabra. 2. Para cada regla de la lista (por orden), • Aplicarla a cada palabra del texto.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con listas de transformaci´ on (II) Ejemplo:

Morphology

PoS tagging

Initial tagging: All-NN the-NN boys-NN and-NN the-NN girls-NN came-NN If the word is currently tagged as NN

Introducci´ on TL Markov Otros

and it ends with an s, then retag it as NNS.

Next tagging: All-NN the-NN boys-NNS and-NN the-NN girlsNNS came-NN

´ındice

34

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con listas de transformaci´ on (III)

Morphology

PoS tagging

Introducci´ on TL Markov Otros

Algoritmo de aprendizaje Entrenamiento(textoNoAnotado textoAnotado) Inicializar: Leer el texto no anotado Inicializar las etiquetas (p.ej., todas como nombre singular, NN) Repetir: Comparar el texto con el anotado Encontrar la regla que maximice las correcciones realizadas sobre el texto. A˜ nadir esta regla al final de la lista. Aplicarla al texto de entrenamiento. hasta que la mejora < umbral. Devolver la lista completa.

´ındice

35

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con listas de transformaci´ on (IV) Morphology

PoS tagging

Introducci´ on TL Markov

Algoritmo de etiquetado Etiquetado(textoNoAnotado) Inicializar: Leer el texto no anotado Inicializar las etiquetas (p.ej., todas como nombre singular, NN) Para cada regla r: Aplicarla al texto.

Otros

Devolver el texto anotado.

´ındice

36

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con listas de transformaci´ on (V) Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

37

Ejemplo de reglas The/NN good-looking/NN dogs/NN barked/NN Rule NN s fhassuf 1 NNS x NN . fchar CD x NN - fchar JJ x NN ed fhassuf 2 VBN x ... NN the fhassuf 3 DT x ... VBN NNS prevword VBD

Text The/NN good-looking/NN dogs/NN barked/NN The/NN good-looking/NN dogs/NNS barked/NN The/NN good-looking/JJ dogs/NNS barked/NN The/NN good-looking/JJ dogs/NNS barked/VBN ... The/DT good-looking/JJ dogs/NNS barked/VBD ... The/DT good-looking/JJ dogs/NNS barked/VBD

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con listas de transformaci´ on (VI)

Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

38

• Son m´ as expresivas que las listas de decisi´ on y los ´ arboles de decisi´ on. • Una regla puede deshacer lo que ha hecho otra regla anterior en un caso particular. • El aprendizaje es muy lento, pues hay que evaluar a cada paso muchas posibilidades. • El etiquetado de textos nuevos, en cambio, se puede realizar en tiempo lineal (n´ umero de reglas × n´ umero de palabras). • No da varias posibles etiquetaciones en casos dudosos. • Precisi´ on: alrededor del 95-96%.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con modelos de Markov (I) Morphology

PoS tagging

Notaci´ on: wl La la palabra del lenguaje. tj La j a etiqueta. wi La palabra en la posici´ on i del corpus. ti La etiqueta asignada a wi.

Introducci´ on TL Markov Otros

´ındice

39

Procedimiento: Dado un texto con I palabras, se trata de obtener la secuencia de etiquetas {t1, ..., ti, ..., tI }: argmax(t1,...,tn) P (t1, ..., tn|w1, ..., wn)

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con modelos de Markov (II)

Morphology

PoS tagging

Introducci´ on TL Markov

argmax(t1,...,tn) P (t1, ..., tn|w1, ..., wn) P (w1...n|t1...n)P (t1...n) = argmax(t1...n) P (w1...n) = argmax(t1...n)P (w1...n|t1...n)P (t1...n) Podemos hacer dos hip´ otesis para simplificar el problema: • Las palabras son independientes unas de otras. • La identidad de una palabra s´ olo depende de su etiqueta.

Otros

= argmax(t1...n)

n Y

P (wi|ti)P (t1...n)

i=1

´ındice

40

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morphology

Etiquetado con modelos de Markov (III)

PoS tagging

Utilizando cadenas de Markov de segundo orden, se trata de maximizar:

Introducci´ on TL Markov

[ QIi=1 P (ti|ti−1, ti−2)P (wi|ti) ] P (tT +1|tT ) donde t−1 y tT +1 son marcadores de inicio y fin de frase.

Otros

´ındice

41

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (I)

Morphology

Primeramente, se puede obtiener la frecuencia de unigramas, bigramas y trigramas utilizando los estimadores de maximum likelihood: Pˆ(t3) =

PoS tagging

Pˆ(t3|t2) = Introducci´ on TL Markov Otros

42

f (t2, t3) f (t2)

f (t1, t2, t3) f (t1, t2) Igualmente, la probabilidad por cada palabra: Pˆ(t3|t2, t1) =

Pˆ(w3|t3) = ´ındice

f (t3) N

f (w3, t3) f (t3)

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (II)

Morphology

PoS tagging

Introducci´ on TL Markov

Las probabilidades obtenidas no se pueden aplicar directamente debido al problema de datos escasos (sparse data problem). Aunque las probabilidades estimadas Pˆ tienden a la probabilidad real conforme aumenta el tama˜ no del corpus de entrenamiento, por grande que sea el corpus, siempre habr´ a fen´ omenos ling¨ u´ısticos que no aparezcan en ´ el.

Otros

Los estimadores Pˆ siempre asignan probabilidad 0 a fen´ omenos no observados. ´ındice

43

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Morphology

PoS tagging

Introducci´ on TL Markov

Estimaci´ on de los par´ ametros (III) El problema se mitiga con t´ ecnicas de smoothing: • Ley de Laplace • Leyes de Lidstone y Jeffreys-Perks • Estimador Held-out • Deleted interpolation • Otros...

Otros

´ındice

44

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (IV) Ley de Laplace Morphology

PoS tagging

f (t1, ..., tn) + 1 N +B donde N es el n´ umero de trigramas en el corpus, y B es el n´ umero de trigramas diferentes. PLap(t1, ..., tn) =

Problema: Da demasiado peso a los n-gramas no vistos. Introducci´ on TL Markov Otros

Ejemplo: Tenemos tres etiquetas: NN, JJ y DT (27 posibles trigramas): Trigrama DT JJ NN DT NN NN JJ NN NN otro

Frecuencia 10 9 1 0

Pˆ 0.5 0.45 0.05 0

PLap 0.23 0.21 0.043 0.03

Incluso a trigramas gramaticalmente incorrectos!: NN NN DT ´ındice

45

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (V) Ley de Lidstone Morphology

PoS tagging

Introducci´ on TL

f (t1, ..., tn) + λ N + Bλ donde N es el n´ umero de trigramas en el corpus, y B es el n´ umero de trigramas diferentes. Se puede demostrar que equivale a una interpolaci´ on lineal entre el estimador de maximum likelihood y una funci´ on de probabilidad uniforme. PLap(t1, ..., tn) =

Markov Otros

Ley de Jeffreys-Perks: Tomar λ = 0.5

PLap(t1, ..., tn) = ´ındice

46

f (t1, ..., tn) + 0.5 N + 0.5 × B

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (VI)

Morphology

PoS tagging

Problemas: • Escoger el valor de λ apropiado. • Sigue dando probabilidad positiva a fen´ omenos que nunca pueden ocurrir. Ejemplo: Tenemos tres etiquetas: NN, JJ y DT (27 posibles trigramas). Con λ = 2,

Introducci´ on TL Markov Otros

´ındice

47

Trigrama DT JJ NN DT NN NN JJ NN NN otro

Frecuencia 10 9 1 0

Pˆ 0.5 0.45 0.05 0

PLap 0.33 0.28 0.045 0.015

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (VII) Estimador Held-out El corpus de entrenamiento se divide en dos partes: Morphology

PoS tagging

Introducci´ on TL Markov Otros

• Una primera parte, para calcular las frecuencias de los n-gramas: f1 (t1 , ..., tn) • Una segunda parte (held out), para ver, al encontrarnos texto nuevo, c´ omo var´ıan los estimadores: f2 (t1 , ..., tn).

Nr = n´ umero de n-gramas con frecuencia f1 = r. Tr = n´ umero de veces que aparecen en la segunda parte todos los trigramas que aparec´ıan r veces en la primera. X Tr = f2(t1...n) {t1...n :f1 (t1...n )=r}

´ındice

48

Tr Pho(t1...n) = Nr N

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (VIII) Morphology

Ejemplo: Tenemos tres etiquetas: NN, JJ y DT (27 posibles trigramas). PoS tagging

Introducci´ on TL Markov Otros

´ındice

49

Trigrama DT JJ NN DT NN NN JJ NN NN otro

f 10 9 1 0

f1 5 5 0 0

f2 5 4 1 0

Pˆ 0.5 0.45 0.05 0

PLap 0.45 0.45 0.004 0.004

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (IX)

Morphology

PoS tagging

Introducci´ on

Interpolaci´ on por eliminaci´ on (deleted interpolation Similar al Held-out, pero cada parte en que se divide el corpus hace de held-out para la otra parte. Supongamos que dividimos el corpus en dos, a y b: Nra = n´ umero de n-gramas con frecuencia fa = r. Trab = n´ umero de veces que aparecen los ngramas de la parte a con frecuencia r en la parte b.

TL Markov Otros

Trab Trba Pho(t1...n) = a o bien b Nr N Nr N Trab + Trba Pdel (t1...n) = N (Nra + Nrb)

´ındice

50

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (X) Morphology

Ejemplo: Tenemos tres etiquetas: NN, JJ y DT (27 posibles trigramas). PoS tagging

Introducci´ on TL Markov Otros

´ındice

51

Trigrama DT JJ NN DT NN NN JJ NN NN otro

f 10 9 1 0

f1 5 5 0 0

f2 5 4 1 0

Pˆ 0.5 0.45 0.05 0

PLap 0.474 0.474 0.002 0.002

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Estimaci´ on de los par´ ametros (XI)

Morphology

PoS tagging

Interpolaci´ on lineal Es probable que un trigrama t1t2t3 no ocurra nunca en el corpus pero que, o bien t2t3, o bien t3 sean muy frecuentes. Eso indica que quiz´ a no han coincidido nunca con t1, pero que hay cierta probabilidad de que ocurra.

Introducci´ on TL Markov Otros

´ındice

52

Pli(t3|t2, t1) = λ1Pˆ(t3|t2, t1) + λ2Pˆ(t3|t2) + λ3Pˆ(t3) Variaciones: • Hacer depender λi de la historia previa. • Si el estimador de trigramas se considera fiable, no interpolar. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con modelos de Markov (IV)

Morphology

Una vez hemos estimado los par´ ametros, se trataba de encontrar la secuencia de etiquetas que maximice

PoS tagging

[

QI

i=1 P (ti|ti−1 , ti−2 )P (wi|ti)

] P (tT +1|tT )

Introducci´ on TL Markov Otros

´ındice

53

• Probar todas las posibles combinaciones: exponencial. • En tiempo polin´ omico con el algoritmo de Viterbi.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Etiquetado con modelos de Markov (V)

Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

54

(Brants, 2001) • Cadenas de Markov de tercer orden. • Estimaci´ on de probabilidades con interpolaci´ on lineal. • Los par´ ametros λ se obtienen con deleted interpolation. • Incorpora modelos de probabilidad P (w|ti) para palabras que no estuvieran en el corpus de entrenamiento. • Incorpora al modelo de Markov el hecho de que las palabas est´ en capitalizadas o no. Precisi´ on: 96.7%. En frases poco dudosas, llega al 99% de precisi´ on. En casos muy dudosos (si las probabilidades son similares), puede dar varias etiquetas con probabilidades. Procesamiento de Lenguaje Natural 2004 - LAT X slides E

Otros modelos (I) Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

55

Entrop´ıa M´ axima Las palabras se van etiquetando una a una. Para cada palabra, podemos considerar: • Caracter´ısticas l´ exicas: prefijos, sufijos, etc. • La historia reciente: palabras que la han precedido, y las etiquetas asignadas a esas A partir de esa informac´ıon, ha de ser posible asignarle una etiqueta, para pasar a la palabra siguiente.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Otros modelos (II)

Morphology

PoS tagging

Introducci´ on TL

Entrop´ıa M´ axima Se consideran caracter´ısticas binarias sobre las palabras y su historia hi:

( 1 fj (hi, ti) = 0

if suf f ix(wi) = ing and ti = VBG otherwise

Con ellas, se entrena un modelo sobre la probabilidad de asignar la etiqueta t a la palabra actual, dada la historia h:

Markov Otros

p(h, t) = πµ

k Y

f (h,t)

αj j

,

j=1

donde π es el factor de normalizaci´ on, y µ, α son los par´ ametros del modelo. ´ındice

56

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Otros modelos (III) Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

57

Entrop´ıa M´ axima • Ratnaparkhi (1996) consigui´ o un 96.6% de precisi´ on. • M´ as lento de entrenar y utilizar que las cadenas de Markov. • Al no existir algoritmos como Viterbi para estos modelos, utiliz´ o una b´ usqueda en haz (beam search), qued´ andose a cada paso con las N etiquetas m´ as probables.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Otros modelos (IV)

Morphology

PoS tagging

Introducci´ on TL Markov Otros

´ındice

58

´ rboles de decisi´ • A on, listas de decisi´ on. ⇒ Menos expresivas que listas de transformaci´ on • Hidden Markov Models para aprendizaje no supervisado. • Aprendizaje basado en memoria (k nearest neighbor). • Redes neuronales. • Bootstrapping. • Combinaci´ on de varios m´ etodos. • EngCG: Reglas definidas a mano por expertos.

Procesamiento de Lenguaje Natural 2004 - LATEX slides