-
Introducción Modelos probabilísticos Contenido semántico
Procesamiento del lenguaje natural
Francisco J. Martín MateosJosé L. Ruiz Reina
Dpto. Ciencias de la Computación e Inteligencia ArtificialUniversidad de Sevilla
-
Introducción Modelos probabilísticos Contenido semántico
Índice
Introducción
Modelos probabilísticos
Contenido semántico
-
Introducción Modelos probabilísticos Contenido semántico
Introducción
• El Procesamiento del Lenguaje Natural es una disciplinade la Inteligencia Artificial que se ocupa de la formulacióne investigación de mecanismos computacionales para lacomunicación entre personas y máquinas mediante el usode Lenguajes Naturales
• Los Lenguajes Naturales son los utilizados en lacomunicación humana, ya sean escritos, hablados osignados
-
Introducción Modelos probabilísticos Contenido semántico
Aplicaciones del Procesamiento del Lenguaje Natural• Comprensión del lenguaje (contenido, significado,
relaciones,. . . )• Recuperación de la información (buscadores en internet,
catálogos, . . . )• Extracción de la información (estructurada o
semi-estructurada)• Búsqueda de respuestas (preguntas planteadas en
lenguaje natural,. . . )• Generación de discurso• Traducción automática• Reconstrucción de discurso (espacios en blanco,
traducción, texto predictivo,. . . )• Reconocimiento del habla• Síntesis de voz• . . .
-
Introducción Modelos probabilísticos Contenido semántico
Fases de la comunicación (R&N )
• Intención: A quiere transmitir la idea P a B• Generación: A transforma P en la frase W1• Síntesis: A envía W ′1 a B (donde W
′1 es la realización física
de W1)• Percepción: B percibe W ′′1 como la realización física W
′1 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 idea Pi
-
Introducción Modelos probabilísticos Contenido semántico
Análisis del lenguaje
La estructura del lenguaje se analiza a cuatro niveles• Análisis morfológico: El análisis de las palabras para
extraer raíces, rasgos flexivos, unidades léxicascompuestas y otros fenómenos
• Análisis sintáctico. El análisis de la estructura sintáctica dela frase mediante una gramática de la lengua en cuestión
• Análisis semántico. La extracción del significado (oposibles 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 losantecedentes referenciales de los pronombres
-
Introducción Modelos probabilísticos Contenido semántico
Análisis morfológico
• Estudia la estructura de las palabras individuales (sinreferencia al contexto) con objeto de identificarcomponentes y modificadores
• En idiomas como el español se distinguen:• Raíz de la palabra: proporciona el significado de la palabra• Modificadores: indican género, número, tiempo verbal,
oposición, repetición, ...• Componentes de derivación: generan una palabra a partir
de otra (pueden cambiar la categoría sintáctica)• En otros idiomas la estructura de una palabra puede ser
más compleja:• Modificadores que incluyen información sintáctica:
declinaciones• Composición de varias raíces en una misma palabra con o
sin información estructural
-
Introducción Modelos probabilísticos Contenido semántico
Análisis sintáctico
• Estudia la estructura de la frase agrupando palabrassegún su funcionalidad
• Distintas formas de agrupación o constituyentes• Sintagmas nominales: un nombre con o sin determinante• Sintagmas preposicionales: una preposición junto con un
sintagma nominal• Sintagmas verbales: un verbo que indica una acción, junto
con otros sintagmas nominales o preposicionales queproporcionan información adicional que complementa dichaacción
• Formalismos para analizar la estructura de una frase:• CFG: gramáticas independientes de contexto• DCG: gramáticas de cláusulas definidas• PCFG: gramáticas probabilísticas
-
Introducción Modelos probabilísticos Contenido semántico
Análisis semántico
• Estudia el significado de la frase completa a partir de elsignificado de las palabras y la estructura sintáctica
• El problema fundamental con el que se enfrenta es laambigüedad en el significado de las palabras
• Una vez resuelto el problema de la ambigüedad, utilizalenguajes formales para representar el significado de lafrase• El lenguaje OWL en el contexto de la Web semántica
-
Introducción Modelos probabilísticos Contenido semántico
Análisis pragmático
• Estudia el significado de un texto teniendo en cuenta lasituación de cada frase dentro del mismo
• El problema fundamental con el que se enfrenta es lapresencia de formas adverbiales o pronominales cuyosignificado no está explícito en una frase, sino quedepende del contexto• Adverbios: ahora, ayer, entonces, allí, aquí• Pronombres: éste, aquel, mío, tuyo, suyo
• Se extrae el significado de estos elementos a partir de• Descripciones de la situación actual (quién habla, cuándo
habla, dónde está)• Frases analizadas previamente
-
Introducción Modelos probabilísticos Contenido semántico
Técnicas de análisis del lenguaje
• Las distintas fases y problemáticas del análisis dellenguaje se afrontan principalmente con las siguientestécnicas• Técnicas lingüísticas formales: Se basan en el desarrollo
de reglas estructurales que se aplican en las fases deanálisis del lenguaje
• Técnicas probabilísticas: Se basan en el estudio en basea un conjunto de textos de referencia (corpus), decaracterísticas de tipo probabilístico asociadas a lasdistintas fases de análisis del lenguaje
• Modelos para el procesamiento del lenguaje natural• Lógicos (gramáticas)• Probabilísticos (basados en corpus)
-
Introducción Modelos probabilísticos Contenido semántico
Modelos probabilísticos del lenguaje
• Un modelo probabilístico del lenguaje define unadistribución de probabilidad sobre un conjunto depalabras, 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 (término, característica, . . . ) tiene
asociada una probabilidad y estas probabilidades seaprenden a partir de un corpus o se calculan a partir de lasaprendidas
• Los distintos modelos probabilísticos del lenguaje secaracterizarán por las propiedades de independenciaasumidas, y la forma en la que se calcula la probabilidadde una frase• Reflejan mejor la realidad del lenguaje y son más robustos• Se aprenden a partir de textos• Resuelven ambigüedades
-
Introducción Modelos probabilísticos Contenido semántico
Modelos n-gram: Introducción
• De manera general, dada una secuencia de palabrasw1 ... wn, su probabilidad calcula de la siguiente forma:
P(W1 = w1, . . . ,Wn = wn) =
P(W = w1)P(Wt+1 = w2|Wt = w1) · · ·P(Wt+n−1 = wn|Wt = w1, . . . ,Wt+n−2 = wn−1)
• Intuitivamente, el i-ésimo factor es la probabilidad de que(en el lenguaje modelado) aparezca la palabra wi acontinuación de la secuencia w1, . . . ,wi−1
• Estas probabilidades se aprenden a partir de un corpus• En la práctica es imposible saber la probabilidad de cada
palabra condicionada a cada posible secuencia depalabras anteriores
• Se toman determinadas suposiciones de independenciaque simplifican el modelo (a costa de perder precisión)
-
Introducción Modelos probabilísticos Contenido semántico
Modelos unigram
• Se asume independencia entre palabras consecutivas
P(W1 = w1, . . . ,Wn = wn) =∏
1≤i≤nP(W = wi)
• Se utiliza aprendizaje ML para estimar las probabilidades
P(W = w) =N(w)
N
Donde N(w) es el número de ocurrencias de la palabra wen el corpus y N es el número total de palabras(incluyendo repeticiones)
-
Introducción Modelos probabilísticos Contenido semántico
Modelos bigram
• Se asume dependencia entre una palabra y la anterior,pero independencia con las demás
P(W1 = w1, . . . ,Wn = wn) = P(W = w1)∏
1≤i
-
Introducción Modelos probabilísticos Contenido semántico
Modelos trigram
• Se asume dependencia entre una palabra y las dosanteriores, pero independencia con las demás
P(W1 = w1, . . . ,Wn = wn) =
P(W = w1)P(Wt+1 = w2|Wt = w1)∏
1≤i
-
Introducción Modelos probabilísticos Contenido semántico
Modelos n-gram
• 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, setienen en cuenta relaciones contextuales léxicas, que nosuelen aparecer en los modelos gramaticales
-
Introducción Modelos probabilísticos Contenido semántico
Generación de frases con modelos n-gram
• Para ilustrar las capacidades de los modelos n-gram,podemos generar frases aleatorias siguiendo un muestreoa partir de dichos modelos
• Experimento: a partir el libro de texto de Russel & Norvig,“Artificial Intelligence: A Modern Approach”, construimosmodelos unigram, bigram y trigram.
• Resultados generando secuencias de palabras en cadauno 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 ...
-
Introducción Modelos probabilísticos Contenido semántico
Suavizado en modelos n-gram
• En un modelo n-gram, la probabilidad de gran cantidad delas 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 elcorpus
• Esto hace que una secuencia de texto perfectamenteválida pueda tener probabilidad nula si alguna de susn-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 ycompensar la suma total aumentando adecuadamente losdenominadores (Ley de Laplace)
• Otra técnica de suavizado consiste en realizar unacombinación lineal de varios modelos probabilísticos
-
Introducción Modelos probabilísticos Contenido semántico
Suavizado en modelos n-gram: ley de Laplace
• Modelo unigram suavizado:
P(W = w) =N(w) + 1N + V1
Donde V1 es el número total de palabras distintas en elcorpus
• Modelo bigram suavizado:
P(Wt+1 = wj |Wt = wi) =N(wi wj) + 1N(wi) + V2
Donde V2 es el número total de bigrams distintos en elcorpus
-
Introducción Modelos probabilísticos Contenido semántico
Suavizado en modelos n-gram: interpolación lineal
• Es probable que un trigram w1 w2 w3 aparezca muy pocoen 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 losmodelos bigram y unigram no
• Una forma de suavizar el modelo trigram consiste encombinarlo con los modelos bigram y unigram:
P(Wt+2 = w3|Wt = w1,Wt+1 = w2) =
λ3P3(Wt+2 = w3|Wt = w1,Wt+1 = w2)+λ2P2(Wt+1 = w3|Wt = w2)+λ1P1(W = w3)
Donde P1 es la probabilidad según el modelo unigram, P2es la probabilidad según el modelo bigram, P3 es laprobabilidad 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 yunigram
-
Introducción Modelos probabilísticos Contenido semántico
Evaluación de modelos n-gram
• ¿Cómo de bueno es el modelo probabilístico obtenido apartir de un corpus?
• Usualmente, separamos el corpus en dos partes: una paraentrenamiento y otra para pruebas
• Una vez obtenido el modelo probabilístico a partir delcorpus de entrenamiento, lo evaluamos calculando lasprobabilidades que asigna a las cadenas de texto delcorpus de prueba
• Para evitar probabilidades demasiado pequeñas, se usa loque 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
-
Introducción Modelos probabilísticos Contenido semántico
Una aplicación del modelo unigram: segmentación (I)
• Problema: Determinar las palabras de un texto en el queno 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 oel Chino
• Ejemplo:• Supongamos el siguiente texto sin espacios en blancoEsdifícilleerfrasessinespaciosenblanco
• El objetivo es obtener la frase original con un cierto gradode confianza en que así lo esEs difícil leer frases sin espacios enblanco
• Este proceso se puede llevar a cabo fácilmente con unmodelo unigram del lenguaje
-
Introducción Modelos probabilísticos Contenido semántico
Una aplicación del modelo unigram: segmentación (II)
• Consideremos un modelo unigram de un corpus• Dado un texto sin espacios en blanco w
• Una segmentación de w es una secuencia de palabrasl = w l1 · · ·w lkl cuya concatenación es igual a w
• Notaremos por Lw al conjunto de todas las posiblessegmentaciones de w
• El objetivo consiste en encontrar la segmentación l ∈ Lwcon mayor probabilidad
argmaxl∈Lw
P(l) = argmaxl∈Lw
∏1≤i≤kl
P(W = w li )
-
Introducción Modelos probabilísticos Contenido semántico
Algoritmo de segmentación
• Observaciones• 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 palabrasen reconocimiento del habla
-
Introducción Modelos probabilísticos Contenido semántico
Una aplicación del modelo bigram: etiquetadosintáctico
• Problema: Etiquetar cada palabra de un texto con lacategorí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 etiquetarel hombre toma café con leche
• El objetivo es asignar a cada palabra una categoríasintáctica coherente con la estructura de la fraseel/LD hombre/NN toma/VIP café/NN con/Eleche/NN
-
Introducción Modelos probabilísticos Contenido semántico
Etiquetado sintáctico
• Es una aplicación de los Modelos Ocultos de Markov• Hay que determinar la secuencia de etiquetas más
probable dada la secuencia de palabras• La variable de estado es la que identifica la categoría
sintáctica (etiqueta) de cada palabra, la distribución deprobabilidad de esta variable nos la proporciona un modelobigram del corpus
• La variable observable nos indica el valor de la palabra• El proceso de encontrar el etiquetado de mayor
probabilidad se resuelve con el Algoritmo de Viterbi
-
Introducción Modelos probabilísticos Contenido semántico
Etiquetado sintáctico
• Consideremos un modelo bigram de un corpuspreviamente etiquetado
• Dado un texto de n palabras w = w1 w2 ... wn• Un etiquetado de este texto es una secuencia de etiquetas
t = t1t2...tn en la que cada ti es la etiqueta asociada a lapalabra wi
• Notaremos por Tn al conjunto de todas las sucesiones de netiquetas
• El objetivo consiste en encontrar el etiquetado t ∈ Tn conmayor probabilidad
argmaxt∈Tn
P(t |w) = argmaxt∈Tn
P(t ,w)
-
Introducción Modelos probabilísticos Contenido semántico
Etiquetado sintáctico
• Cada probabilidad condicionada P(tj |ti) se estima con lafrecuencia de ocurrencia de las dos etiquetasconsecutivas en el corpus
P(tj |ti) =N(ti tj)N(ti)
• Cada probabilidad condicionada P(wi |ti) se estima comola frecuencia con que una palabra tiene una determinadaetiqueta en el corpus
P(wi |ti) =N(wi , ti)
N(ti)
-
Introducción Modelos probabilísticos Contenido semántico
Tratamiento semántico del corpus
• En los ejemplos anteriores el corpus se trata como unaunidad de la que se obtiene información léxica o sintáctica
• Un tratamiento semántico del corpus necesita que ésteesté formado por gran cantidad de documentos
• Ejemplos• Recuperación de información• Clasificación de documentos• Extracción de información
-
Introducción Modelos probabilísticos Contenido semántico
Recuperación de la información
• Problema: Dada una colección de documentos, encontraraquellos más relevantes con respecto a una necesidad deinformació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
-
Introducción Modelos probabilísticos Contenido semántico
El modelo de claves booleanas
• Cada palabra en la colección de documentos es unavariable booleana que es cierta en aquellos documentosen los que aparece y falsa en los que no aparece
• El lenguaje de consulta es el lenguaje de las expresionesbooleanas construidas sobre las características asociadasa las palabras. Por ejemplo: pollo AND (tomate ORfrito)
• Un documento es relevante sólo si la consulta se evalúa averdadero
• Este modelo tiene la ventaja de que es muy simple y fácilde 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
-
Introducción Modelos probabilísticos Contenido semántico
El modelo de espacio vectorial
• Supondremos a partir de ahora que las consultas lasrealiza 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 lasfrecuencia con la que ocurre un término de la consulta enun documento• Pero considerando menos relevantes aquellos términos
que ocurren con mucha frecuencia en la mayor parte de losdocumentos
-
Introducción Modelos probabilísticos Contenido semántico
Representación vectorial de un documento (I)
• Definiciones:• La frecuencia de un término (term frequency ) t en un
documento D, notada como tft,D, es el número de vecesque aparece el término en el documento
• La frecuencia documental (documental frequency ) de untérmino t , notada dft , es el número de documentos en losque aparece el término
• La frecuencia documental inversa (inverse documentalfrequency ) de un término t es idft = log(N/dft), donde Nes el número total de documentos
• El peso de un término t en un documento D estfidft,D = tft,D · idft
-
Introducción Modelos probabilísticos Contenido semántico
Representación vectorial de un documento (II)
• Un vocabulario es un conjunto de términos queconsideramos importantes en la colección de documentos,V = {t1, . . . , tm}
• En el modelo de espacio vectorial un documento D serepresenta como el vector de pesos de cada término delvocabulario
~D = (d1, . . . ,dm) donde di = tfidfti ,D
• La proximidad entre dos documentos se calcula en funciónde la proximidad entre sus vectores de pesos asociados;para ello calculamos el coseno del ángulo que forman:
sim(~D, ~D′) =∑m
i=1 DiD′i√∑m
i=1(di)2√∑m
i=1(d′i )
2
-
Introducción Modelos probabilísticos Contenido semántico
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.
-
Introducción Modelos probabilísticos Contenido semántico
Ejemplo en el modelo de espacio de vectores(Grossman)
• Las representaciones vectoriales de D1, D2 y D3 son,respectivamente, ~D1, ~D2 y ~D3 (las tres últimas columnasde la tabla). El número de documentos N es 3.
Término t tft,D1 tft,D2 tft,D3 dft N/dft idft~D1 ~D2 ~D3
llegó 0 1 1 2 1.5 0.1761 0 0.1761 0.1761dañado 1 0 0 1 3 0.4771 0.4771 0 0entrega 0 1 0 1 3 0.4771 0 0.4771 0fuego 1 0 0 1 3 0.4771 0.4771 0 0oro 1 0 1 2 1.5 0.1761 0.1761 0 0.1761plata 0 2 0 1 3 0.4771 0 0.9542 0cargamento 1 0 1 2 1.5 0.1761 0.1761 0 0.1761camión 0 1 1 2 1.5 0.1761 0 0.1761 0.1761color 0 1 0 1 3 0.4771 0 0.4771 0
-
Introducción Modelos probabilísticos Contenido semántico
Proximidad entre documentos y consultas
• Consultas:• Una consulta puede ser vista como un documento y tendrá,
por tanto, un vector ~Q asociado (la mayoría de suscomponentes serán cero)
• sim(~D, ~Q) dará una medida de lo relevante que es undocumento respecto de la consulta (cuanto más cercano auno, más relevante)
• Recuperación de información en el modelo vectorial:transformar tanto la consulta como los documentos envectores de pesos, calcular los cosenos y presentar(ordenados de mayor a menor) los K mejores (los más’parecidos’)
-
Introducción Modelos probabilísticos Contenido semántico
Una consulta en el ejemplo anterior
• La consulta “oro plata camión” en representación vectoriales ~Q = (0,0,0,0,0,1761,0,4771,0,0,1761,0)
• Las distintas medidas de similitud son:• sim( ~D1, ~Q) = 0,00801• sim( ~D2, ~Q) = 0,7561• sim( ~D3, ~Q) = 0,3272
• Resultados en orden de relevancia: D2, D3, D1
-
Introducción Modelos probabilísticos Contenido semántico
Recuperación de la información en la práctica (I)
• 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 larelevancia de un documento respecto de una consulta:proximidad entre términos
-
Introducción Modelos probabilísticos Contenido semántico
Recuperación de la información en la práctica (II)
• Evaluación de sistemas de recuperación de la información:• Precisión: porcentaje de documentos devueltos como
relevantes que realmente lo son• Exhaustividad (recall): porcentaje de documentos
presentados como relevantes de entre todos los realmenterelevantes
• Los sistema reales de recuperación de la información sonsistemas que acceden a una cantidad masiva de datos• Es muy importante la eficiencia: índices• Muchas veces, depende del hardware de almacenamiento
-
Introducción Modelos probabilísticos Contenido semántico
Enlaces entre documentos
• Hasta ahora, no hemos considerando los sistemas derecuperació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 enla relevancia del documento.
• Ejemplos:• PageRank de Google• HITS (Hyperlink-Induced Topic Search)
-
Introducción Modelos probabilísticos Contenido semántico
PageRank
• La relevancia de una página web no puede estar basadaúnicamente en sus tf , debe tenerse en cuenta también elnú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 demayor relevancia
• Definición (recursiva):
PR(p) =1− d
N+ d
∑i
PR(ini)C(ini)
• 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)
-
Introducción Modelos probabilísticos Contenido semántico
PageRank
• Modelo de navegación aleatoria: PR(p) es la probabilidadde que una persona que navega por la red llegue en algúnmomento a visitar p, supuesto que en cada página quevisita:• 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 cadavarios meses• Desde el punto de vista algebraico es el cálculo de un
autovector
• En la actualidad, el PageRank no es de los factores másinfluyentes en Google a la hora de ordenar páginasrelevantes para una consulta, aunque sí que es uno deellos.
-
Introducción Modelos probabilísticos Contenido semántico
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 desdemuchas otras)
• Una página es un centro en la materia si tiene una buenacolección de enlaces a autoridades en la materia.
• Definición de los índices de autoridad (a) y centro (h):
a(v) =∑y 7→v
h(y) h(v) =∑v 7→y
a(y)
• Definición mutuamente recursiva, cuya solución se tienemediante el cálculo de autovectores
-
Introducción Modelos probabilísticos Contenido semántico
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 ∈ C a la quepertenece 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 quetenemos un conjunto entrenamiento (textos yaclasificados)
-
Introducción Modelos probabilísticos Contenido semántico
Clasificación de documentos en el modelo vectorialcon kNN
• Para clasificar un documento dado, buscar los kdocumentos del conjunto de entrenamiento más cercanosy devolver la clase más frecuente en esos k documentos
• La cercanía la calculamos usando la medida de similituddefinida 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
-
Introducción Modelos probabilísticos Contenido semántico
Clasificación de documentos en el modelo vectorialcon kNN
• Vocabulario:• Debe ser un conjunto de términos cuya presencia o
ausencia sea relevante para caracterizar la pertenencia auna clase.
• Existen técnicas estadísticas para elegir esos términos• Elección de k :
• Usando algún conocimiento específico sobre el problemade clasificación
• Realizando pruebas en conjuntos más pequeños• Preferiblemente impar, para intentar evitar empates
• Variante en kNN: para cada clase c, sumar la similitud(con el que se quiere clasificar) de cada documento deesa clase que esté entre los k más cercanos. Devolver laclase que obtenga mayor puntuación.• Así un documento cuenta más cuanto más cercano esté
-
Introducción Modelos probabilísticos Contenido semántico
Clasificación con Naive Bayes Multinomial
• Dado el documento D a clasificar devolver cnb comoclasificación de D, donde cnb se define:
cnb = argmaxc∈C
P(c|D) = argmaxc∈C
P(c)∏
1≤k≤mP(tk |c)ntk
• siendo nt el número de veces que el término t en eldocumento
• Para evitar desbordamientos por números muy bajos, sesuele usar la siguiente versión, equivalente, conlogaritmos:
cnb = argmaxc∈C
logP(c) + ∑1≤k≤m
ntk logP(tk |c)
• Como ya sabemos, las probabilidades se obtienen como
estimaciones ML a partir del conjunto de entrenamiento
-
Introducción Modelos probabilísticos Contenido semántico
Estimación ML de las probabilidades
• P(c) se estima como NcN , donde Nc es el número dedocumentos de la categoría c y N el número total dedocumentos en el conjunto de entrenamiento.
• P(t |c) se estima como Tc,t∑s∈V Tc,s
, la proporción deocurrencias de t en todos los documentos de la categoríac (respecto de todas las ocurrencias de todos los términosdel vocabulario)
• Para evitar que muchas de estas probabilidades sean 0,se aplica un suavizado de Laplace:
P(t |c) =Tc,t + 1∑
s∈V (Tc,s + 1)=
Tc,t + 1∑s∈V Tc,s + |V |
-
Introducción Modelos probabilísticos Contenido semántico
Naive Bayes Multinomial para clasificación de texto
C las clases, D el conjunto de entrenamiento yd el documento a clasificar
EntrenaNB(C,D)1. V ← vocabulario que se extrae de D,2. N ← número de documentos de D3. Para cada clase c en C, hacer:
3.1 Nc ← el número de documentos en la clase c,3.2 prior[c] ← Nc/N,3.3 Textoc ← concatenación de los documentos de la clase c3.4 Para cada término t en V, hacer:
3.4.1 T (c, t) ← número de ocurrencias de t en Textoc3.5 Tc ← la suma de todos los T (c, t),3.6 Para cada término t en V, hacer:
3.6.1 condprob[c,t] ← (T (c, t) + 1)/(Tc + |V |)4. Devolver V, prior y condprob
ClasificaNB(C,V, prior, condprob, d)1. Para cada clase c en C, hacer:
1.1 score[c] ← log(prior[c])1.2 Para cada término t en V, hacer:
1.2.1 nt ← número de veces que aparace t en d1.2.2 incrementar score[c] con nt · log(condprob[c,t])
2. Devolver la clase c para la que score[c] sea máximo
-
Introducción Modelos probabilísticos Contenido semántico
Un ejemplo con Naive Bayes Multinomial
(Manning, Raghavan & Schütze, ejemplo 13.1) Supongamosun problema de clasificación de documentos en el que elvocabulario considerado es {Chino, Pekín, Shanghai, Macao,Tokyo, Japón}. Existen dos categorías posibles: la de losdocumentos que hablan de China (ch), y la de los que hablande Japón (j). Como conjunto de entrenamiento contamos conlos siguientes documentos:
• D1: “Chino Pekín Chino”, categoría ch.• D2: “Chino Chino Shanghai”, categoría ch.• D3: “Chino Macao”, categoría ch.• D4: “Tokyo Japón Chino”, categoría j .
¿Cómo clasificaría el método Naive Bayes Multinomial (conestimación suavizada) el nuevo documento D5 “Chino ChinoChino Tokyo Japón”?
-
Introducción Modelos probabilísticos Contenido semántico
Un ejemplo con Naive Bayes Multinomial
• Estimación de las probabilidades (a priori) de cada clase:
P(ch) =34
P(j) =14
• Estimación de las probabilidades de cada palabra (sólomostramos las que necesitamos para clasificar eldocumento):
P(Chino|c) = 5 + 18 + 6
=37
P(Chino|j) = 1 + 13 + 6
=29
P(Tokyo|c) = 0 + 18 + 6
=114
P(Tokyo|j) = 1 + 13 + 6
=29
P(Japon|c) = 0 + 18 + 6
=114
P(Japon|j) = 1 + 13 + 6
=29
-
Introducción Modelos probabilísticos Contenido semántico
Un ejemplo con Naive Bayes Multinomial
Clasificamos el documento D5 (en este caso no usamoslogaritmos):
• Categoría ch para D5: 34 · (37)
3 · 114 ·114 = 0,0003
• Categoría j para D5: 14 · (29)
3 · 29 ·29 = 0,0001
Luego el método Naive Bayes multinomial clasifica eldocumento D5 como de la categoría de los que hablan deChina
-
Introducción Modelos probabilísticos Contenido semántico
Detección de SPAM con Naive Bayes clásico• Problema: Decidir si un correo electrónico es SPAM o no,
basándonos en un conjunto previo de correos clasificadoscomo 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 aleatoriaY representando el hecho de que dicho correo sea SPAM
• Consideramos también un conjunto de n variablesaleatorias, Xi , asociadas a ciertas características delcorreo 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• En este caso aplicaremos Naive Bayes “clásico”, visto en el
primer cuatrimestre (es decir, no basado en contarocurrencias, como es el caso del multinomial)
• Es muy importante una buena selección de características
-
Introducción Modelos probabilísticos Contenido semántico
Detección de SPAM con Naive Bayes
• Según Naive Bayes, se clasifica el nuevo correo comoSPAM en función del valor de
ynb = argmaxy∈{spam,ham}
[log(P(Y = y)) +∑
1≤i≤n
log(P(X = xi |Y = y))]
• El corpus se utiliza para estimar las probabilidades:
P(Y = spam) =S
S + HP(Y = ham) =
HS + H
P(X = x |Y = spam) = SxS
P(x |Y = ham) = HxH
donde Sx es el número de correos SPAM del conjunto deentrenamiento que tiene la característica X = x y Hx es elnúmero de correos HAM del conjunto de entrenamientocon la característica X = x
• Estas estimaciones suelen suavizarse
-
Introducción Modelos probabilísticos Contenido semántico
Bibliografía
• Russell, S. y Norvig, P. Artificial Intelligence (A ModernApproach) 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 statisticalnatural language processing (MIT Press, 1999)
• Manning, C.D., Raghavan, P. y Schütze, H. Introduction toInformation Retrieval (Cambridge University Press, 2008)• Secciones 6.2, 6.3, 13.1, 13.2, 14.3, 21.2 y 21.3
IntroducciónModelos probabilísticosContenido semántico