Download Procesamiento del lenguaje natural

Procesamiento del lenguaje natural
F. J. Martı́n Mateos
J. L. Ruiz Reina
Dpto. Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Contenidos
Introducción
Gramáticas independientes del contexto
Gramáticas de cláusulas definidas
Gramáticas probabilı́sticas
Modelos probabilı́sticos: n-gramas
Recuperación de la información
Clasificación de documentos
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 1
Sección 1
Introducción
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Introducción
El Procesamiento del Lenguaje Natural es una disciplina de la
Inteligencia Artificial que se ocupa de la formulación e
investigación de mecanismos computacionales para la
comunicación entre personas y máquinas mediante el uso de
Lenguajes Naturales
Los Lenguajes Naturales son los utilizados en la comunicación
humana, ya sean escritos, hablados o signados
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Introducción
Aplicaciones del Procesamiento del Lenguaje Natural:
Comprensión del lenguaje
Recuperación de la información
Extracción de la información
Búsqueda de respuestas
Generación de discurso
Traducción automática
Reconstrucción de discurso
Reconocimiento del habla
Sı́ntesis de voz
...
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Fases de la comunicación (R&N)
Intención: A quiere transmitir la proposición P a B
Generación: A transforma P en la frase W
Sı́ntesis: A envı́a W ′ a B (donde W ′ es la realización fı́sica de
W)
Percepción: B percibe W ′′ como la realización fı́sica W ′ y lo
decodifica como la frase W2
Análisis: B infiere que W2 puede tener como posibles
significados P1 , . . . , Pn
Resolución de ambigüedades: B decide que Pi es el significado
más probable de entre los posibles
Incorporación: B decide si cree o no la proposición Pi
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Análisis del lenguaje
Se analiza la estructura del lenguaje a cuatro niveles
Análisis morfológico: El análisis de las palabras para extraer
raı́ces, rasgos flexivos, unidades léxicas compuestas y otros
fenómenos
Análisis sintáctico. El análisis de la estructura sintáctica de la
frase mediante una gramática de la lengua en cuestión
Análisis semántico. La extracción del significado (o posibles
significados) de la frase
Análisis pragmático. El análisis de los significados más allá de
los lı́mites de la frase, por ejemplo, para determinar los
antecedentes referenciales de los pronombres
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Técnicas de análisis del lenguaje
Las distintas fases y problemáticas del análisis del lenguaje se
afrontan principalmente con las siguientes técnicas
Técnicas lingüı́sticas formales: Se basan en el desarrollo de
reglas estructurales que se aplican en las fases de análisis del
lenguaje
Técnicas probabilı́sticas: Se basan en el estudio en base a un
conjunto de textos de referencia (corpus) de caracterı́sticas de
tipo probabilı́stico asociadas a las distintas fases de análisis del
lenguaje
Modelos para el procesamiento del lenguaje natural
Lógicos (gramáticas)
Probabilı́sticos (basados en corpus)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 2
Sección 2
Gramáticas independientes del contexto
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas independientes de contexto
Una gramática independiente de contexto está formada por:
Un conjunto de sı́mbolos terminales T (las palabras)
Un conjunto de sı́mbolos no terminales N (los constituyentes o
categorı́as sintácticas)
Un sı́mbolo no terminal inicial S
Un conjunto de reglas de producción, que indican las maneras
en que se puede derivar una oración valida a partir del sı́mbolo
inicial
Estas reglas son de la forma N =⇒ W , donde N ∈ N y
W ∈ (N ∪ T )∗
Usualmente, para describir una gramática, sólo se
proporcionan las reglas
Los sı́mbolos no terminales se escriben en mayúsculas y son los
únicos que pueden aparecer en el lado izquierdo de las reglas
Los sı́mbolos terminales se escriben en minúsculas
El sı́mbolo inicial es siempre el mismo: S
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas independientes de contexto
Ejemplo
S
NP
VP
PP
DT
N
V
P
=⇒ NP VP
=⇒ DT N
|N
|NP PP
=⇒ V NP
|V
|VP PP
=⇒ P NP
|P
=⇒ el | los
=⇒ hombre | amigos | café | leche
=⇒ toma | toman
=⇒ con | solo
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas independientes de contexto
Utilizando las reglas de la gramática, podemos derivar
oraciones
Una regla se aplica sustituyendo el sı́mbolo que aparece en la
parte izquierda por los que aparecen en su parte derecha
Una derivación es la aplicación sucesiva de reglas hasta
obtener una expresión que sólo contiene sı́mbolos terminales
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas independientes de contexto
Ejemplo
S =⇒
=⇒
=⇒
=⇒
=⇒
=⇒
=⇒
=⇒
NP
DT
el
el
el
el
el
el
VP
N VP
N VP
hombre
hombre
hombre
hombre
hombre
VP
V NP
toma NP
toma N
toma café
Podemos abreviar la derivación de la siguiente forma:
S =⇒∗ el hombre toma café
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas independientes de contexto
La forma en que se ha realizado la derivación se puede
capturar con un árbol de derivación sintáctica
Ejemplo:
S
VP
NP
DT
N
V
NP
el
hombre
toma
N
café
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas independientes de contexto
El lenguaje generado por una gramática G es el conjunto de
frases s para las que existe una derivación:
L(G) = {s ∈ T ∗ |S =⇒∗ s}
Formas de utilizar una gramática:
Para generar texto
Para analizar texto (parsing), obteniendo el árbol sintáctico
Existen numerosos algoritmos de parsing eficientes
(compiladores)
Las gramáticas independientes del contexto son muy útiles
para procesar lenguajes formales (con pocos sı́mbolos
terminales y pocas reglas)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Limitaciones de la gramáticas independientes de contexto
Los lenguajes naturales son mucho más expresivos que los
lenguajes descritos por gramáticas independientes de contexto
Concordancia morfológica: género, número, tiempos verbales,
pronombres. Por ejemplo, S =⇒∗ el amigos toma café
Por ejemplo, deberı́amos tener un conjunto de reglas para
frases en plural y otro para frases en singular.
El número de reglas aumenta exponencialmente si se quieren
tener en cuenta todas las concordancias
Otro problema: ambigüedades sintáctica y semántica
La misma frase tiene distintos árboles de derivación sintáctica,
aunque sólo uno de ellos es correcto a nivel semántico: Él toma
café con leche
La misma frase tiene distintos árboles de derivación sintáctica,
y ambas son correctas a nivel semántico: Él toma café solo
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 3
Sección 3
Gramáticas de clausulas definidas
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Aumentando la capacidad expresiva: GCDs
Una gramática de cláusulas definidas (GCD) es similar a una
gramática independiente de contexto, pero considera que los
sı́mbolos no terminales son sı́mbolos de predicados
Y por tanto pueden llevar argumentos.
Estos argumentos se pueden utilizar para implementar
concordancia morfológica o extracción de significado, entre
otras aplicaciones.
GCD con concordancia de género y número
oracion
--> sintagma_nominal(N),
verbo(N),
complemento.
complemento
--> [].
complemento
--> sintagma_nominal(N).
sintagma_nominal(N) --> nombre(G,N).
sintagma_nominal(N) --> determinante(G,N),nombre(G,N).
verbo(N)
--> [P],{es_verbo(P,N)}.
nombre(G,N)
--> [P],{es_nombre(P,G,N)}.
determinante(G,N)
--> [P],{es_determinante(P,G,N)}.
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Notación en las gramáticas de cláusulas definidas
Frases: listas de palabras.
Ejemplo: [la,profesora,lee,un,libro]
Sı́mbolos no terminales: sı́mbolos de predicado
Variables en los argumentos: mayúsculas o mudas
Sı́mbolos terminales: listas unitarias.
Ejemplo: [el]
Colocamos entre llaves cualquier llamada a predicados
externos a la gramática.
Ejemplo: {es_verbo(P,N)}
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Definiendo el léxico de la gramática del ejemplo
Las llamadas externas pueden servir, entre otras cosas, para
separar el léxico de las reglas sintácticas. Basta con incluir los
siguientes hechos:
Léxico
es_nombre(profesor,masculino,singular).
es_nombre(profesores,masculino,plural).
es_nombre(profesora,femenino,singular).
es_nombre(profesoras,femenino,plural).
es_nombre(libro,masculino,singular).
es_nombre(libros,masculino,plural).
es_determinante(el,masculino,singular).
es_determinante(los,masculino,plural).
es_determinante(la,femenino,singular).
es_determinante(las,femenino,plural).
es_determinante(un,masculino,singular).
es_determinante(una,femenino,singular).
es_determinante(unos,masculino,plural).
es_determinante(unas,femenino,plural).
es_verbo(lee,singular).
es_verbo(leen,plural).
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Reglas GCD como reglas en lógica de primer orden
Cada regla de la gramática se puede convertir a una regla
lógica (clausula definida) en la que cada sı́mbolo no terminal
se corresponde con un predicado con los mismos argumentos
más un argumento adicional que representa la sublista de
palabras que se analiza según la categorı́a gramatical que
representa el sı́mbolo.
Ejemplo: la regla
sintagma_nominal(N) --> determinante(G,N),nombre(G,N).
se traduce a la regla lógica:
determinante(G,N,S1) ∧ nombre(G,N,S2)
→ sintagma_nominal(N,S1@S2)
(aquı́ @ representa concatenación)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Reglas GCD como reglas en lógica de primer orden
Para las reglas correspondientes a sı́mbolos terminales, la
traducción es algo distinta.
Ejemplo: la regla
nombre(G,N) --> [P],{es_nombre(P,G,N)}.
se traduce a la regla lógica:
es_nombre(P,G,N) → nombre(G,N,[P])
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas de cláusulas definidas y SLD-resolución
Con esa visión de una GCD como un conjunto de reglas, el
analizar sintácticamente según una GCD puede reducirse a
deducir usando SLD-resolución
Las GCDs surgen como una extensión al lenguaje Prolog
De hecho, se pueden escribir tal cual en cualquier intérprete
de Prolog, y de esa manera se tiene directamente un
analizador sintáctico, usando el predicado phrase (y
considerando que las frases como listas de palabras):
?- phrase(oración,[la,profesora,lee,un,libro]).
Yes
?- phrase(oración,[las,profesores,lee,los,libro]).
No
Incluso tenemos un generador de frases del lenguaje:
?- phrase(oración,L).
L=[la,profesora,lee,un,libro];
....
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Lenguajes expresables por GCDs
Incluso en lenguajes formales, GCDs son más expresivas que
GIC.
GCD que define el lenguaje L = {a2n b2n c2n : n ∈ N}, no
expresable con una GIC:
GCD para el lenguaje L = {a2n b2n c2n : n ∈ N}
palabra
a(0)
a(s(N))
b(0)
b(s(N))
c(0)
c(s(N))
-->
-->
-->
-->
-->
-->
-->
a(N), b(N), c(N), {par(N)}.
[].
[a],a(N).
[].
[b],b(N).
[].
[c],c(N).
par(0).
par(s(s(N))) :- par(N).
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Análisis semántico
¿Cómo representar el significado de una frase?
En general, se trata de expresarlo mediante algún lenguaje
formal
Esto permite que una máquina pueda realizar las acciones
adecuadas al mensaje emitido (almacenar información,
responder preguntas razonadamente,. . . )
En nuestro caso, usaremos la lógica de primer orden como
lenguaje de representación
Podrı́amos usar cualquier otro formalismo de representación
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Análisis semántico
Ejemplos de significados asignados a frases:
Juan es alto:
alto(juan)
Pedro bebe agua:
bebe(pedro, agua)
Todo hombre tiene alma:
∀x[hombre(x) → tiene(x, alma)]
Algún hombre tiene dinero:
∃x[hombre(x) ∧ tiene(x, dinero)]
Todo hombre que no come pan no tiene dinero:
∀x[(hombre(x) ∧ ¬come(x, pan)) → ¬tiene(x, dinero)]
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Un caso simple de construcción de significado
¿Cuál es el significado de la frase “Juan es alto”?
Significado de “Juan”: el término (constante) juan
Significado de “es”: es sólo un nexo de unión del sujeto con el
adjetivo que lo califica (no aporta significado)
Significado de “alto”: predicado unario alto que expresa una
propiedad sobre alguien; puede verse como una función tal que
dado un sujeto, devuelve la afirmación de que dicho sujeto es
alto; dicha función se representa usualmente por λx.alto(x)
El significado de la frase completa se obtiene aplicando el
significado del sintagma verbal al significado del sintagma
nominal: (λx.alto(x))(juan) = alto(juan)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Semántica composicional
Hipótesis composicional: el significado de una categorı́a
sintáctica se obtiene a partir del significado de las
subcategorı́as que lo componen
Esta hipótesis no siempre es cierta, pero simplifica el análisis
semántico
Pasando parte del trabajo a la fase de eliminación de
ambigüedades
oracion
alto(juan)
sn
sv
juan
lambda(x,alto(x))
n
verbo
juan
juan
atributo
lambda(x,alto(x))
es
adjetivo
lambda(x,alto(x))
alto
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Extracción de significado
En lugar de tener una lambda como significado, en la GCD
tenemos como argumentos separados sus componentes: en
este caso, uno para la variable y otro para el cuerpo
GCD para extracción de significado
oración(SSV)
--> sintagma_nominal(SSN),
sintagma_verbal(SSN,SSV).
sintagma_nominal(SNP) --> nombre_propio(SNP).
sintagma_verbal(X,SA) --> verbo_cop,atributo(X,SA).
atributo(X,SA)
--> adjetivo(X,SA).
verbo_cop
--> [es].
nombre_propio(juan)
--> [juan].
nombre_propio(pedro) --> [pedro].
adjetivo(X,alto(X))
--> [alto].
adjetivo(X,bajo(X))
--> [bajo].
El mecanismo de unificación sirve para “componer” el
resultado
?- phrase(oración(S),[juan,es,alto]).
S = alto(juan)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Frases con verbos transitivos
Significado de un verbo transitivo: predicado que relaciona el
sujeto con el objeto directo. Por ejemplo, el significado del
verbo “come” es la función λx.λy .come(x, y )
GCD para frases con verbos transitivos
oración(SSV)
--> sujeto(SS),
sintagma_verbal(SS,SSV).
sujeto(SNP)
--> nombre_propio(SNP).
sintagma_nominal(SN)
--> nombre(SN).
sintagma_verbal(X,SV)
--> verbo_trans(X,SN,SV),
sintagma_nominal(SN).
verbo_trans(X,Y,come(X,Y)) --> [come].
verbo_trans(X,Y,bebe(X,Y)) --> [bebe].
nombre_propio(juan)
--> [juan].
nombre_propio(pedro)
--> [pedro].
nombre(pan)
--> [pan].
nombre(agua)
--> [agua].
Ejemplo de sesión
?- phrase(oración(S),[pedro,come,pan]).
S = come(pedro, pan)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Frases con determinantes todo y algún
En la lógica de primer orden, estos determinantes se
corresponden con los cuantificadores universal y existencial
Ejemplos:
“Todo andaluz come pescado”:
∀x[andaluz(x) → come(x, pescado)]
“Algún informático tiene dinero”:
∃x[informatico(x) ∧ tiene(x, dinero)]
En la GCD que veremos a continuación se define su
significado ası́:
determinante(X,Prop,SSV,existe(X, Prop y SSV))
--> [algún].
determinante(X,Prop,SSV,para_todo(X, Prop => SSV)) --> [todo].
El significado de estos determinantes es un “esqueleto” de
fórmula lógica, que se irá concretando a medida que se analice
la frase.
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Frases con determinantes todo y algún
GCD para frases con determinantes todo y algún
:-op(600,xfy,’=>’).
:-op(900,xfy,y).
oración(S) --> sujeto_det(X,SSV,S), sintagma_verbal(X,SSV).
sujeto_det(X,SSV,S) --> determinante(X,Prop,SSV,S),
nombre_propiedad(X,Prop).
determinante(X,Prop,SSV,existe(X, Prop y SSV))
--> [algún].
determinante(X,Prop,SSV,para_todo(X, Prop => SSV)) --> [todo].
objeto_directo(SN) --> nombre(SN).
sintagma_verbal(X,SV) --> verbo_trans(X,SN,SV),
objeto_directo(SN).
sintagma_verbal(X,SV) --> verbo_cop,nombre_propiedad(X,SV).
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Frases con determinantes todo y algún
GCD para frases con determinantes todo y algún
verbo_trans(X,Y,tiene(X,Y)) --> [tiene].
verbo_trans(X,Y,come(X,Y)) --> [come].
verbo_cop --> [es].
nombre(pan)
nombre(pescado)
nombre(carne)
nombre(dinero)
nombre(coche)
-->
-->
-->
-->
-->
[pan].
[pescado].
[carne].
[dinero].
[coche].
nombre_propiedad(X,hombre(X))
nombre_propiedad(X,carpintero(X))
nombre_propiedad(X,informático(X))
nombre_propiedad(X,andaluz(X))
nombre_propiedad(X,francés(X))
nombre_propiedad(X,europeo(X))
Inteligencia Artificial II 2012–2013
-->
-->
-->
-->
-->
-->
[hombre].
[carpintero].
[informático].
[andaluz].
[frances].
[europeo].
Procesamiento del lenguaje natural
Frases con determinantes todo y algún
Sesión
?- phrase(oración(S),[todo,andaluz,come,pescado]).
S = para_todo(X, andaluz(X) => come(X, pescado))
?- phrase(oración(S),[algún,informático,tiene,dinero]).
S = existe(X, informático(X) y tiene(X, dinero))
?- phrase(oración(S),[algún,informático,es,andaluz]).
S = existe(X, informático(X) y andaluz(X))
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Aplicación: razonamiento y lenguaje natural
Mantenimiento y consultas de una base de conocimiento
usando lenguaje natural
El conocimiento se aserta en lenguaje natural (y es incluido en
lenguaje formal)
La respuesta a una consulta se da en lenguaje natural y puede
implicar deducir información a partir de lo afirmado
anteriormente
Cada frase en la comunicación hombre-máquina es analizada
semánticamente:
Del humano hacia la máquina: lenguaje natural a lenguaje
formal
De la máquina hacia el humano: lenguaje formal a lenguaje
natural
El razonamiento lo realiza la máquina usando las expresiones
formales (con SLD-resolución, por ejemplo)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Aplicación: razonamiento y lenguaje natural
Sesión con adición de información y con consultas:
?- consulta([]).
? [juan,es,andaluz].
? [¿, quién, es, andaluz, ?].
! [juan, es, andaluz]
? [¿, es, juan, europeo, ?].
! No
? [todo, andaluz, es, europeo].
? [¿, es, juan, europeo, ?].
! [juan, es, europeo]
? [¿, quién, es, europeo, ?].
! [juan, es, europeo]
? muestra_reglas.
! [todo, andaluz, es, europeo]
! [juan, es, andaluz]
? fin.
Yes
Esta sesión corresponde a un programa Prolog que usa una
GCD para el análisis semántico y SLD-resolución para la
deducción.
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 4
Sección 4
Gramáticas probabilı́sticas
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Modelos probabilı́sticos del lenguaje
Un modelo probabilı́stico del lenguaje define una distribución
de probabilidad sobre el conjunto de las cadenas de caracteres
o de palabras, a partir del análisis de un corpus
Un corpus es una colección grande de textos, escritos por y
para humanos
Es decir, cada frase tiene asociada una probabilidad y estas
probabilidades se aprenden a partir de un corpus o se calculan
a partir de las aprendidas
Los distintos modelos probabilı́sticos del lenguaje se
caracterizarán por las propiedades de independencia asumidas,
y la forma en la que se calcula la probabilidad de una frase
Ventajas:
Reflejan mejor la realidad del lenguaje y son más robustos
Se aprenden a partir de textos
Resuelven ambigüedades
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Un modelo probabilı́stico basado en gramáticas
Una gramática independiente de contexto probabilı́stica es
igual a una gramática independiente de contexto en la que
cada regla tiene asociada una probabilidad
La regla N =⇒ W 1 , . . . , W n tiene asociada la probabilidad
P(N =⇒ W 1 , . . . , W n |N)
La suma de las probabilidades asociadas a las reglas con un
mismo
sı́mbolo no terminal en su parte izquierda es 1:
P
n
P(N
=⇒ Wj1 , . . . , Wj j |N) = 1
j
Estas gramáticas permiten calcular la probabilidad de una
derivación sintáctica a partir de las probabilidades de todas las
reglas que se han aplicado
La probabilidad de cada regla se aprende analizando
colecciones de textos (corpus)
De esta forma se intenta resolver la ambigüedad sintáctica:
tómese el árbol de derivación más probable
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas probabilı́sticas
Ejemplo
S
NP
VP
PP
DT
N
V
P
=⇒ NP VP
1,0
=⇒ DT N
0,4
|N
0,2
|NP PP
0,4
=⇒ V NP
0,5
|V
0,2
|VP PP
0,3
=⇒ P NP
0,8
|P
0,2
=⇒ el | los
0,50 c.u.
=⇒ hombre | amigos | café | leche 0,25 c.u.
=⇒ toma | toman
0,50 c.u.
=⇒ con | solo
0,50 c.u.
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas probabilı́sticas
Ejemplo
S1,0
NP0,4
DT0,5
el
N0,25
S1,0
NP0,4
VP0,5
V0,5
hombre toma
NP0,4
NP0,2
PP0,2
N0,25
P0,5
café
solo
DT0,5
el
VP0,3
VP0,5
N0,25
PP0,2
hombre V0,5
NP0,2
P0,5
toma
N0,25
solo
café
Probabilidad del primer análisis: 0,000025
Probabilidad del segundo análisis: 0,0000187
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Gramáticas probabilı́sticas
Ventajas
Dan una idea probabilı́stica de lo buena que es una derivación
sintáctica de una frase, permitiendo decidir ante una
ambigüedad
Las reglas probabilı́sticas se pueden aprender a partir de un
conjunto de ejemplos correctamente formado
Inconvenientes
La probabilidad de una frase depende únicamente de la
derivación sintáctica y no tiene en cuenta el contexto léxico:
La frase el amigos toma hombre tiene la misma
probabilidad que el hombre toma café
Las frases cortas tienen mayor probabilidad que las largas
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 5
Sección 5
Modelos n-gram
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Modelos probabilı́sticos basados en n-grams
De manera general, dada una secuencia de palabras w1 ... wn ,
su probabilidad se podrı́a calcula de la siguiente forma:
P(w1 ... wn ) = P(w1 )P(w2 |w1 ) · · · P(wn |w1 , . . . , wn−1 )
Intuitivamente, cada P(wi |w1 , . . . , wi−1 ) es la probabilidad de
que (en el lenguaje modelado) aparezca la palabra wi a
continuación de la secuencia w1 , . . . , wi−1
Estas probabilidades se aprenden a partir de un corpus
Pero en la práctica es imposible saber la probabilidad de cada
palabra condicionada a cada posible secuencia de palabras
anteriores.
Por esto, se toman determinadas suposiciones de
independencia que simplifican el modelo (a costa de perder
precisión)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Modelos n-gram
Modelo unigram: Se asume independencia entre palabras
consecutivas
Y
N(wi )
P(w1 ... wn ) =
P(wi ) con P(wi ) =
N
i
Donde N(wi ) es el número de ocurrencias de la palabra wi en
el corpus y N es el número total de palabras (incluyendo
repeticiones)
Modelo bigram: Se asume dependencia entre una palabra y la
anterior, pero independencia con las demás
Y
N(wi wj )
P(w1 ... wn ) = P(w1 )
P(wi+1 |wi ) con P(wj |wi ) =
N(wi )
i
Donde N(wi wj ) es el número de ocurrencias de la secuencia
(bigram) wi wj en el corpus
Un bigram está formado por dos palabras consecutivas en el
corpus
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Modelos n-gram
Modelo trigram: Se asume dependencia entre una palabra y
las dos anteriores, pero independencia incondicional con las
demás
Y
P(w1 ... wn ) = P(w1 )P(w2 |w1 )
P(wi+2 |wi+1 , wi )
i
Un trigram está formado por tres palabras consecutivas en el
corpus
Modelo n-gram: Generalización de los modelos anteriores
Un n-gram está formado por n palabras consecutivas en el
corpus
En estos modelos probabilı́sticos, salvo el unigram, se tienen
en cuenta relaciones contextuales léxicas, que no suelen
aparecer en los modelos gramaticales
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Generación de frases con modelos n-gram
Para ilustrar las capacidades de los modelos n-gram, podemos
generar frases aleatorias siguiendo un muestreo a partir de
dichos modelos
Experimento: a partir el libro de texto de Russel& Norvig,
“Artificial Intelligence: A Modern Approach”, constuimos
modelos unigram, bigram y trigram.
Resultados generando secuencias de palabras en cada uno de
esos modelos:
Unigram: logical are as confusion a may right tries agent goal
the was ...
Bigram: systems are very similar computational approach
would be represented ...
Trigram: planning and scheduling are integrated the success of
naive bayes model ...
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Suavizado en modelos n-gram
En un modelo n-gram, la probabilidad de gran cantidad de las
n-secuencias de palabras será nula
El número total de n-secuencias de palabras es muy superior al
número de n-secuencias que aparecen en el corpus
Esto hace que una secuencia de texto perfectamente válida
pueda tener probabilidad nula si alguna de sus n-secuencias
componentes nunca aparece en el corpus
Para evitar esto se utilizan técnicas de suavizado
La técnica de suavizado más simple consiste en sumar 1 a los
numeradores de las probabilidades individuales y compensar la
suma total aumentando adecuadamente los denominadores
(Ley de Laplace)
Otra técnica de suavizado consiste en realizar una combinación
lineal de varios modelos probabilı́sticos
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Suavizado en modelos n-gram: ley de Laplace
Modelo unigram suavizado:
N(w ) + 1
N + V1
Donde V1 es el número total de palabras distintas en el corpus
P(w ) =
Modelo bigram suavizado:
N(wi wj ) + 1
N(wi ) + V2
Donde V2 es el número total de bigrams distintos en el corpus
P(wj |wi ) =
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Suavizado en modelos n-gram: interpolación lineal
Es probable que un trigram w1 w2 w3 aparezca muy poco en
el corpus, pero que w2 w3 o w3 sean muy frecuentes
En esta situación el modelo trigram proporciona una
probabilidad muy baja a la secuencia w1 w2 w3 , pero los
modelos bigram y unigram no
Una forma de suavizar el modelo trigram consiste en
combinarlo con los modelos bigram y unigram, de forma que:
P(w3 |w1 , w2 ) = λ3 P3 (w3 |w1 , w2 ) + λ2 P2 (w3 |w2 ) + λ1 P1 (w3 )
Donde P1 es la probabilidad según el modelo unigram, P2 es
la probabilidad según el modelo bigram, P3 es la probabilidad
según el modelo trigram y λ1 + λ2 + λ3 = 1
De forma general se puede suavizar un modelo n-gram
combinándolo como modelos (n−1)-gram, ..., bigram y
unigram
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Evaluación de modelos n-gram
¿Cómo de bueno es el modelo probabilı́stico obtenido a partir
de un corpus?
Usualmente, separamos el corpus en dos partes: una para
entrenamiento y otra para tests
Una vez obtenido el modelo probabilı́stico a partir del corpus
de entrenamiento, evaluamos éste calculando las
probabilidades que éste asigna a las cadenas de texto del
corpus de prueba
Para evitar probabilidades demasiado pequeñas, se usa lo que
se conoce como perplejidad:
Perplejidad(frase) = 2−log2 (P(frase))/N
donde N es el número de palabras de la frase
Cuanto menor la perplejidad, mejor es el modelo
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Una aplicación del modelo unigram: segmentación
Problema: Determinar las palabras de un texto en el que no
hay espacios en blanco
Esta tarea es necesaria en la interpretación de lenguajes que se
escriben sin espacios en blanco, como el Japonés o el Chino
Ejemplo:
Supongamos el siguiente texto sin espacios en blanco
Esfácilleerfrasessinespaciosenblanco
El objetivo es obtener la frase original con un cierto grado de
confianza en que ası́ lo es
Es fácil leer frases sin espacios en blanco
Este proceso se puede llevar a cabo fácilmente con un modelo
unigram del lenguaje
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Una aplicación del modelo unigram: segmentación
Consideremos un modelo unigram de un corpus P
La probabilidad de cada palabra se calcula como la frecuencia
relativa de aparición de dicha palabra en el corpus (estimador
de máxima verosimilitud)
Dado un texto sin espacios en blanco w de longitud n
Una segmentación de w es una secuencia de palabras
l = w1 ... wk cuya concatenación es igual a w
Notaremos por wil la i-ésima palabra en la segmentación l de w
El objetivo consiste en encontrar la segmentación l con mayor
probabilidad
Y
argmax P(l) = argmax
P(wil )
l
Inteligencia Artificial II 2012–2013
l
i
Procesamiento del lenguaje natural
Algoritmo de segmentación
Entrada: Una distribución de probabilidad de palabras
obtenida a partir de un modelo unigram de un corpus P y una
cadena de texto
Salida: Una cadena de texto idéntica a la de entrada salvo por
la inclusión de espacios en blanco para separar palabras
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Algoritmo de segmentación
1. Sean N = LONGITUD(TEXTO),
PALABRAS un vector vacı́o de longitud N+1,
MEJOR un vector de longitud N+1 inicializado a 0 y
MEJOR[0] = 1
2. Para cada I desde 0 a N
2.1. Para cada J desde 0 a I-1
2.1.1. Sea PALABRA = TEXTO[J+1,I]
2.1.2. Si P[PALABRA] * MEJOR[J] >= MEJOR[I] entonces
2.1.2.1. Sea MEJOR[I] = P[PALABRA] * MEJOR[J]
2.1.2.2. Sea PALABRAS[I] = PALABRA
3. Sea SALIDA una cadena vacı́a e I = N
4. Mientras I > 0 hacer
4.1. SALIDA = ’ ’ + PALABRAS[I] + SALIDA
4.2. I = I - LONGITUD(PALABRAS[I])
5. Devolver SALIDA
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Algoritmo de segmentación
Interpretación de los vectores auxiliares
El vector PALABRAS almacena en cada posición I la mejor
palabra que se ha encontrado terminando en la posición I del
texto de entrada
El vector MEJOR almacena en cada posición I la probabilidad
de la mejor segmentación del texto de entrada hasta la
posición I
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Algoritmo de segmentación
Interpretación de la doble iteración (punto 2 del algoritmo)
El algoritmo considera cualquier subcadena del texto de
entrada para ver con que grado de probabilidad dicha
subcadena es una palabra completa
A continuación se calcula la probabilidad de la mejor
segmentación del texto de entrada hasta la posición I en la
que la última palabra es la subcadena considerada
De todas las posibilidades se queda con la mejor, que es
almacenada en la posición I-ésima de los vectores PALABRAS
y MEJOR
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Algoritmo de segmentación
Obtención de la secuencia de salida
En la posición N-ésima del vector PALABRAS se encuentra la
última palabra de la mejor segmentación del texto de entrada
Para determinar cual es la palabra anterior hay que acceder a
la posición del vector PALABRAS que se obtiene restando de la
posición actual el valor de la longitud de la última palabra
considerada
Todas las palabras de la mejor segmentación obtenida se
concatenan para formar la salida
Obsérvese que en MEJOR[N] está almacenada la probabilidad
de la segmentación obtenida
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo del algoritmo de segmentación
TEXTO = "lacadenaestarota"
MEJOR[0] = 1
I = 1, J = 0: PALABRA = "l"
P["l"] = 53.2e-6
MEJOR[1] = 53.2e-6
PALABRAS[1] = "l"
I = 2, J = 0: PALABRA = "la"
P["la"] = 32072.3e-6
MEJOR[2] = 32072.3e-6
PALABRAS[2] = "la"
I = 2, J = 1: PALABRA = "a"
P["a"] = 17230.6e-6
17230.6e-6 * 53.2e-6 = 0.917e-6
I = 3, J = 0: PALABRA = "lac"
P["lac"] = 0.2e-6
MEJOR[3] = 0.2e-6
PALABRAS[3] = "lac"
I = 3, J = 1: PALABRA = "ac"
P["ac"] = 2.1e-6
2.1e-6 * 53.2e-6 = 0.0001117e-6
I = 3, J = 2: PALABRA = "c"
P["c"] = 138.1e-6
138.1e-6 * 32072.3e-6 = 4.429e-6
MEJOR[3] = 4.429e-6
PALABRAS[3] = "c"
I = 4, J = 0: PALABRA = "laca"
P["laca"] = 3.0e-6
MEJOR[4] = 3.0e-6
PALABRAS[4] = "laca"
I = 4, J = 1: PALABRA = "aca"
P["aca"] = 0.6e-6
0.6e-6 * 53.2e-6 = 0.00003192e-6
I = 4, J = 2: PALABRA = "ca"
P["ca"] = 8.1e-6
8.1e-6 * 32072.3e-6 = 0.2598e-6
I = 4, J = 3: PALABRA = "a"
P["a"] = 17230.6e-6
17230.6e-6 * 4.429e-6 = 0.07631e-6
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo del algoritmo de segmentación
I = 5, J = 0: PALABRA = "lacad"
P["lacad"] = 0
MEJOR[5] = 0
PALABRAS[5] = "lacad"
I = 5, J = 1: PALABRA = "acad"
P["acad"] = 1.1e-6
1.1e-6 * 53.2e-6 = 0.00005852e-6
I = 5, J = 2: PALABRA = "cad"
P["cad"] = 0.6e-6
0.6e-6 * 32072.3e-6 = 0.01924e-6
MEJOR[5] = 0.01924e-6
PALABRAS[5] = "cad"
I = 5, J = 3: PALABRA = "ad"
P["ad"] = 7.9e-6
7.9e-6 * 4.429e-6 = 0.00003499e-6
I = 5, J = 4: PALABRA = "d"
P["d"] = 139.2e-6
139.2e-6 * 3.0e-6 = 0.0004176e-6
La mejor segmentación hasta la quinta letra del texto de
entrada es: la cad
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo del algoritmo de segmentación
I = 6, J = 0: PALABRA = "lacade"
P["lacade"] = 0
MEJOR[6] = 0
PALABRAS[6] = "lacade"
I = 6, J = 1: PALABRA = "acade"
P["acade"] = 0
I = 6, J = 2: PALABRA = "cade"
P["cade"] = 0.5e-6
0.5e-6 * 32072.3e-6 = 0.0001604e-6
MEJOR[6] = 0.0001604e-6
PALABRAS[6] = "cade"
I = 6, J = 3: PALABRA = "ade"
P["ade"] = 0.7e-6
0.7e-6 * 4.429e-6 = 0.0000031003e-6
I = 6, J = 4: PALABRA = "de"
P["de"] = 50999.7e-6
50999.7e-6 * 3.0e-6 = 0.153e-6
MEJOR[6] = 0.153e-6
PALABRAS[6] = "de"
I = 6, J = 5: PALABRA = "e"
P["e"] = 644.2e-6
644.2e-6 * 0.01924e-6 = 0.00001239e-6
La mejor segmentación hasta la sexta letra del texto de
entrada es: laca de
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo del algoritmo de segmentación
I = 7, J = 0: PALABRA = "lacaden" P["lacaden"] = 0
MEJOR[7] = 0
PALABRAS[7] = "lacaden"
I = 7, J = 1: PALABRA = "acaden"
P["acaden"] = 0
I = 7, J = 2: PALABRA = "caden"
P["caden"] = 0
I = 7, J = 3: PALABRA = "aden"
P["aden"] = 0
I = 7, J = 4: PALABRA = "den"
P["den"] = 15.3e-6
15.3e-6 * 3.0e-6 = 0.0000459e-6
MEJOR[7] = 0.0000459e-6
PALABRAS[7] = "den"
I = 7, J = 5: PALABRA = "en"
P["en"] = 22695.0e-6
22695.0e-6 * 0.6e-6 = 0.013617e-6
MEJOR[7] = 0.013617e-6
PALABRAS[7] = "en"
I = 7, J = 6: PALABRA = "n"
P["n"] = 59.9e-6
59.9e-6 * 0.153e-6 = 0.0000091647e-6
La mejor segmentación hasta la séptima letra del texto de
entrada es: la cad en
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo del algoritmo de segmentación
I = 8, J = 0: PALABRA = "lacadena" P["lacadena"] = 0
MEJOR[8] = 0
PALABRAS[8] = "lacadena"
I = 8, J = 1: PALABRA = "acadena" P["acadena"] = 0
I = 8, J = 2: PALABRA = "cadena"
P["cadena"] = 40.3e-6
40.3e-6 * 32072.3e-6 = 1.29251369e-6
MEJOR[8] = 1.29251369e-6
PALABRAS[8] = "cadena"
I = 8, J = 3: PALABRA = "adena"
P["adena"] = 0
I = 8, J = 4: PALABRA = "dena"
P["dena"] = 0.1e-6
0.1e-6 * 3.0e-6 = 0.0000003e-6
I = 8, J = 5: PALABRA = "ena"
P["ena"] = 0.3e-6
0.3e-6 * 0.01924e-6 = 0.000000005772e-6
I = 8, J = 6: PALABRA = "na"
P["na"] = 7.1e-6
7.1e-6 * 0.153e-6 = 0.0000010863e-6
I = 8, J = 7: PALABRA = "a"
P["a"] = 17230.6e-6
17230.6e-6 * 0.013617e-6 = 0.0002346290802e-6
La mejor segmentación hasta la octava letra del texto de
entrada es: la cadena
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Algoritmo de segmentación
Observaciones
La segmentación más probable de elundecimo es
el un decimo
El algoritmo da preferencia a palabras pequeñas (más
frecuentes) frente a palabras grandes (menos frecuentes)
El modelo unigram no tiene en cuenta relaciones contextuales
léxicas por lo que el algoritmo considerará como más probables
algunas segmentaciones sin sentido
Un proceso similar se aplica a la identificación de palabras en
reconocimiento del habla
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Una aplicación del modelo bigram: etiquetado sintáctico
Problema: Etiquetar cada palabra de un texto con la categorı́a
sintáctica que le corresponde
Este es un paso intermedio que permite eliminar ambigüedades
léxicas antes del análisis sintáctico
Ejemplo:
Supongamos el siguiente texto sin etiquetar
el hombre toma café con leche
El objetivo es asignar a cada palabra una categorı́a sintáctica
coherente con la estructura de la frase
el/LD hombre/NN toma/VIP café/NN con/E
leche/NN
Este problema se puede resolver con un modelo bigram del
lenguaje
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Etiquetado sintáctico
Consideremos un modelo bigram de un corpus P previamente
etiquetado
Dado un texto de n palabras w1,n = w1 w2 ... wn
Un etiquetado de este texto es una secuencia de etiquetas
t1,n = t1 t2 ...tn en la que cada ti es la etiqueta asociada a la
palabra wi
El objetivo consiste en encontrar el etiquetado t1,n con mayor
probabilidad
argmax P(t1,n |w1,n ) = argmax
t1,n
t1,n
P(w1,n |t1,n )P(t1,n )
P(w1,n )
= argmax P(w1,n |t1,n )P(t1,n )
t1,n
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Etiquetado sintáctico
En un modelo bigram, una palabra/etiqueta sólo depende de
la anterior
n
Y
P(ti |ti−1 )
P(t1,n ) =
i=1
Si asumimos independencia entre palabras consecutivas
condicionada a la secuencia de etiquetas y que una palabra
sólo depende de la etiqueta que tiene asociada en el corpus,
entonces
P(w1,n |t1,n ) =
n
Y
i=1
Inteligencia Artificial II 2012–2013
P(wi |t1,n ) =
n
Y
P(wi |ti )
i=1
Procesamiento del lenguaje natural
Etiquetado sintáctico
Finalmente, el objetivo consiste en encontrar el etiquetado t1,n
que maximiza la expresión
n
Y
argmax
P(ti |ti−1 )P(wi |ti )
t1,n
i=1
Cada probabilidad condicionada P(t i |t j ) se estima con la
frecuencia de ocurrencia de las dos etiquetas consecutivas en el
corpus
N(t j t i )
P(t i |t j ) =
N(t j )
Cada probabilidad condicionada P(w |t) se estima como la
frecuencia con que una palabra tiene una determinada etiqueta
en el corpus
N(w /t)
P(w |t) =
N(t)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 6
Sección 6
Recuperación de la información
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Recuperación de la información
Problema: Dada una colección de documentos, encontrar
aquellos más relevantes con respecto a una necesidad de
información expresada por un usuario.
Se caracteriza por:
Una colección de documentos (hay que definir qué se entiende
por “documento” en cada caso)
Una pregunta del usuario realizada usando un lenguaje
especı́fico de consultas
Un conjunto de resultados obtenidos (un subconjunto de la
colección de documentos)
Una presentación de los resultados obtenidos
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
El modelo de claves booleanas
Cada palabra en la colección de documentos es una variable
booleana que es cierta en aquellos documentos en los que la
palabra aparece y falsa en los que no aparece
El lenguaje de consulta es el lenguaje de las expresiones
booleanas construidas sobre las caracterı́sticas asociadas a las
palabras. Por ejemplo: pollo AND (tomate OR frito)
Un documento es relevante sólo si la consulta se evalúa a
verdadero
Este modelo tiene la ventaja de que es muy simple y fácil de
implementar. Sin embargo tiene bastantes desventajas
La relevancia de un documento es 1 o 0, no hay una gradación
de la misma
Las expresiones booleanas no suelen ser familiares a los
usuarios que no son programadores o lógicos
Es difı́cil realizar una consulta adecuada
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
El modelo de espacio vectorial
Supondremos a partir de ahora que las consultas las realiza el
usuario mediante texto libre
Conjunto de palabras (términos) que considera relevantes para
lo que busca
El modelo de espacio vectorial trata de medir la relevancia de
un documento respecto de una consulta a partir de las
frecuencia con la que ocurre un término de la consulta en un
documento
Pero considerando menos relevantes aquellos términos que
ocurren con mucha frecuencia en la mayor parte de los
documentos
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Representación vectorial de un documento
Definiciones:
La frecuencia de un término t en un documento d (notada
tft,d ) es el número de veces que aparece en el mismo
La frecuencia documental de un término t (notada dft ) es el
número de documentos en los que aparece el término
La frecuencia documental inversa de un término t es
idft = log (N/dft ), donde N es el número total de documentos
El peso de un término t en un documento d es
tfidft,d = tft,d · idft
Un vocabulario es un conjunto de términos que consideramos
importantes en la colección de documentos
Podrı́amos tomar como vocabulario el conjunto de todos los
términos de todos los documentos, o un subconjunto
significativo de ellos
En el modelo de espacio vectorial un documento se representa
como el vector de pesos de cada término del vocabulario
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo en el modelo de espacio de vectores (Grossman)
Documentos:
D1 : “Cargamento de oro dañado por el fuego”
D2 : “La entrega de la plata llegó en el camión color plata”
D3 : “El cargamento de oro llegó en un camión”
Consulta: “oro plata camión”
Vocabulario: llegó, dañado, entrega, fuego, oro, plata,
cargamento, camión, color.
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Ejemplo en el modelo de espacio de vectores (Grossman)
Las representaciones vectoriales de D1 , D2 y D3 son,
~ 1, W
~2 y W
~ 3 (las tres últimas columnas de
respectivamente, W
la tabla)
Término t
tft,1
tft,2
tft,3
dft
N/dft
idft
~1
W
~2
W
~3
W
llegó
dañado
entrega
fuego
oro
plata
cargamento
camión
color
0
1
0
1
1
0
1
0
0
1
0
1
0
0
2
0
1
1
1
0
0
0
1
0
1
1
0
2
1
1
1
2
1
2
2
1
1.5
3
3
3
1.5
3
1.5
1.5
3
0.1761
0.4771
0.4771
0.4771
0.1761
0.4771
0.1761
0.1761
0.4771
0
0.4771
0
0.4771
0.1761
0
0.1761
0
0
0.1761
0
0.4771
0
0
0.9542
0
0.1761
0.4771
0.1761
0
0
0
0.1761
0
0.1761
0.1761
0
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Proximidad entre documentos y consultas
La proximidad entre dos documentos se calcula en función de
la proximidad entre sus vectores de pesos asociados; para ello
calculamos el coseno del ángulo que forman:
P
Vi Wi
i=1p
~ ,W
~ ) = pP
sim(V
P
2
2
i=1 (Vi )
i=1 (Wi )
Consultas:
Una consulta puede ser vista como un documento Q, y por
~ (la mayorı́a de sus componentes serán
tanto como un vector Q
cero)
~ W
~ ) dará una medida de lo relevante que es el
sim(Q,
documento respecto de la consulta (cuanto más cercano a
uno, más relevante)
Recuperación de información en el modelo vectorial:
transformar tanto la consulta como los documentos en
vectores de pesos, calcular los cosenos y presentar (ordenados)
los K mejores
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Una consulta en el ejemplo anterior
La consulta “oro plata camión” en representación vectorial es
~ = (0, 0, 0, 0, 0,1761, 0,4771, 0, 0,1761, 0)
Q
Las distintas medidas de similitud son:
~ W
~ 1 ) = 0,00801
sim(Q,
~
~ 2 ) = 0,7561
sim(Q, W
~
~ 3 ) = 0,3272
sim(Q, W
Resultados en orden de relevancia: D2 , D3 , D1
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Recuperación de la información en la práctica
Las palabras muy comunes se suelen ignorar (stop words)
Los términos en los documentos se suelen normalizar:
atendiendo a su raı́z (stemming), mayúsculas/minúsculas,
acentos, corrección de deletreo, . . .
Se consideran también otros factores que influyen en la
relevancia de un documento respecto de una consulta:
proximidad entre términos
Evaluación de sistemas de recuperación de la información:
Precisión: porcentaje de documentos devueltos como
relevantes que realmente lo son
Memoria (recall): porcentaje de documentos presentados como
relevantes de entre todos los realmente relevantes
Los sistema reales de recuperación de la información son
sistemas que acceden a una cantidad masiva de datos
Es muy importante la eficiencia: ı́ndices
Muchas veces, depende del hardware de almacenamiento
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Enlaces entre documentos
Hasta ahora, no hemos considerando los sistemas de
recuperación de la información en la web
En ese caso, además de la similitud vectorial, es importante
también la estructura de enlaces, que influye en la relevancia
del documento.
Ejemplos:
PageRank de Google
HITS (Hyperlink-Induced Topic Search)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
PageRank
La relevancia de una página web no puede estar basada
únicamente en sus tf , debe tenerse en cuenta también el
número de enlaces que apuntan a la página:
Pero no todos los enlaces deben “pesar” igual, sino que deben
contar más aquellos enlaces desde páginas de mayor relevancia
Definición (recursiva):
PR(p) =
X PR(ini )
1−d
+d
N
C (ini )
i
PR(p) es el PageRank de una página p
N es el número total de páginas en el corpus
ini son las páginas que tienen enlaces a p
C (ini ) es el número de total enlaces que salen desde ini
d es un factor de amortiguación (entre 0 y 1)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
PageRank
Modelo de navegación aleatoria: PR(p) es la probabilidad de
que una persona que navega por la red llegue en algún
momento a visitar p, supuesto que en cada página que visita:
Con probabilidad d, hace clic aleatoriamente en uno de sus
enlaces
Con probabilidad 1 − d, reinicia en una página aleatoria
El cálculo del PageRank de cada página se actualiza cada
varios meses
Desde el punto de vista algebraico es el cálculo de un
autovector
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
HITS
Cálculo de relevancia basado en dos valoraciones: autoridad
(authority) y centro (hub).
Una página es autoridad en una materia si es una fuente
importante de información (y por tanto está enlazada desde
muchas otras)
Una página es un centro en la materia si tiene una buena
colección de enlaces a autoridades en la materia.
Definición de los ı́ndices de autoridad (a) y centro (h):
h(v ) =
X
a(y )
v 7→y
a(v ) =
X
h(y )
y 7→v
Definición mutuamente recursiva, cuya solución se tienen
mediante el cálculo de autovectores
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Sección 7
Sección 7
Clasificación de documentos
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Clasificación de documentos
El problema de clasificar documentos:
Dado un documento d y un conjunto C de categorı́as
documentales (o temas), encontrar la clase c a la que
pertenece d.
Tiene numerosas aplicaciones:
Filtros anti-spam
Control de contenidos infantiles
Clasificación automática de correos
Detección de sentimientos y opiniones
Presentación de resultados en recuperación de la
información,. . .
Es un problema de aprendizaje: supondremos que tenemos un
conjunto entrenamiento (textos ya clasificados)
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Clasificación de documentos en el modelo vectorial con
kNN
Para clasificar un documento dado, buscar los k documentos
del conjunto de entrenamiento más cercanos y devolver la
clase más frecuente en esos k documentos
La cercanı́a la calculamos usando la medida de similitud
definida en el modelo vectorial
Previamente, hay que elegir:
El vocabulario: conjunto de términos cuyos “tfidf” servirán
para obtener la representación vectorial
El valor de k
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Clasificación de documentos en el modelo vectorial con
kNN
Vocabulario:
Debe ser un conjunto de términos cuya presencia o ausencia
sea relevante para caracterizar la pertenencia a una clase.
Existen técnicas estadı́sticas para elegir esos términos
Elección de k:
Usualmente, basándonos en algún conocimiento especı́fico
sobre el problema de clasificación
También como resultado de pruebas en conjuntos más
pequeños
Preferiblemente impar, para intentar evitar empates (k=5, por
ejemplo)
Variante en kNN: para cada clase c, sumar la similitud (con el
que se quiere clasificar) de cada documento de esa clase que
esté entre los k más cercanos. Devolver la clase que obtenga
mayor puntuación.
Ası́ un documento cuenta más cuanto más cercano esté
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Clasificación de documentos usando Naive Bayes
Partimos de un vocabulario de términos escogido a priori
(existen técnicas para decidir el conjunto de términos)
Procedimiento: dado el documento d a clasificar y
{t1 , . . . , tnd } el conjunto de términos del vocabulario que
aparecen en d, devolver cnb como clasificación de d, donde
cnb se define:
Y
P(tk |c)
cnb = argmax P(c|d) = argmax P(c)
c∈C
c∈C
1≤k≤nd
Para evitar desbordamientos por números muy bajos, se suele
usar la siguiente versión equivalente X
con logaritmos:
logP(tk |c)]
cnb = argmax [logP(c) +
c∈C
1≤k≤nd
Como ya sabemos, las probabilidades de estas fórmulas se
obtienen como estimaciones ML a partir del conjunto de
entrenamiento
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Estimación ML de las probabilidades
P(c) se estima como NNc , donde Nc es el número de
documentos de la categorı́a c y N el número total de
documentos en el conjunto de entrenamiento.
P(t|c) se estima como la proporción de ocurrencias de t en
todo el conjunto de entrenamiento (respecto de todas las
T
ocurrencias de todos los términos del vocabulario): P c,tTc,s
s∈V
Nota: además de las suposiciones de independencia sobre las
que está basado Naive Bayes, también asumimos
independencia respecto de la posición de los términos dentro
del documento
Para evitar que muchas de estas probabilidades sean 0, se
aplica un suavizado de Laplace:
P(t|c) = P
Tc,t + 1
Tc,t + 1
=P
s∈V (Tc,s + 1)
s∈V Tc,s + |V |
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Algoritmo Naive Bayes para clasificación de texto
EntrenaNB(C,D)
1. Sea V igual al vocabulario que se extrae del conjunto de
entrenamiento D, y N el número de documentos de D
2. Para cada categorı́a c en C, hacer:
2.1 Sea Nc el número de documentos en la clase c y
prior[c]=Nc/N
2.2 Sea Texto c la concatenación de todos los documentos
de la clase c
2.3 Para cada t en V sea T –tc˝ el número de ocurrencias
de t en Texto c
2.4 Para cada t en V sea condprob[t,c] el resultado de
dividir T –tc˝+1 entre la suma de todos los (T –sc˝+1),
con s en V
3. Devolver V, y las matrices prior y condprob
ClasificaNB(C,V,prior, condprob, d)
1. Sea W el conjunto de términos de V que aparecen en d
2. Para cada clase c en C, hacer:
2.1 Inicializar score[c] con log(prior[c])
2.2 Para cada término t en W, acumular en score[c]
la cantidad log(condprob[t,c])
3. Devolver la clase c para la que score[c] sea máximo
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Detección de SPAM con Naive Bayes
Problema: Decidir si un correo electrónico es SPAM o no,
basándonos en un conjunto previo de correos clasificados
como SPAM o como HAM
En este caso el corpus está formado por los correos
electrónicos previamente clasificados
Dado un correo nuevo, consideramos la variable aleatoria Y
representando el hecho de que dicho correo sea SPAM o no
Consideramos también un conjunto de variables aleatorias Xi
asociadas a ciertas caracterı́sticas del correo electrónico (p.ej.
aparición de ciertas palabras, remitente, mayúsculas..)
Se asume que las variables Xi son independientes entre sı́,
condicionadas a la variable Y
Es muy importante una buena selección de caracterı́sticas
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Detección de SPAM con Naive Bayes
Según Naive Bayes, se clasifica el nuevo correo como SPAM
en función del valor de
ynb =
argmax
[log (P(Y = y ))+
y ∈{spam.ham}
X
log (P(X = xi |Y = y ))]
1≤i≤n
El corpus se utiliza para estimar las probabilidades:
P(Y = spam) =
H
S
, P(Y = ham) =
S +H
S +H
P(X = x|Y = spam) =
Hx
Sx
, P(x|Y = ham) =
S
H
donde Sx es el número de correos SPAM del conjunto de
entrenamiento que tiene la caracterı́stica X = x y Hx es el
número de correos HAM del conjunto de entrenamiento con la
caracterı́stica X = x
Estas estimaciones suelen suavizarse
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural
Bibliografı́a
Russell, S. y Norvig, P. Artificial Intelligence (A Modern
Approach) 3rd edition (Prentice–Hall Hispanoamericana,
2010)
Secciones 22.1, 22.2, 22.3, 23.1, 23.2 y 23.3
Manning, C.D. y Schütze, H. Foundations of statistical
natural language processing (MIT Press, 1999)
Manning, C.D., Raghavan, P. y Schütze, H. Introduction to
Information Retrieval (Cambridge University Press, 2008)
Secciones 6.2, 6.3, 13.1, 13.2, 14.3, 21.2 y 21.3
Inteligencia Artificial II 2012–2013
Procesamiento del lenguaje natural