Adaptability
Summary
• Information Extraction Systems
• Evaluation
• Multilinguality
• Adaptability
• Introduction
• Learning of rules
• Learning of statistical models
• Multistrategy learning
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas
• Tendencia a la no supervisión: disminución considerable
del coste de anotación
• Aprendizaje de antecedentes (patrones)+post-anotación
• Normalmente, patrón=expresión de constituyentes
generalizados
– Heuristic driven specializations:
AutoSlog-TS[Riloff96], [Harabagiu&Maiorano00]
– Observation-based learning:
Essence[Català03]
– Bootstrapping:
DIPRE[Brin98], ExDISCO[Yangarber00], [Yangarber03]
[Surdeanu et al.06]
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
AutoSlog-TS (Riloff[96])
Heuristic-driven specialization
• Anotación de documentos (rel, norel)
• Adquisición de reglas single-slot (extrapolable)
• Uso de AutoSlog
Meta-patrones
Docs
preproc.
anotados
Jordi Turmo, 2010
AutoSlog
Patrones
ranking
Patrones
relevantes
N
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
AutoSlog-TS (Riloff[96])
•Cálculo del ranking de un patron pi:
{
ratio(pi) * log2(freq_pi)
0
si ratio(pi) > 0.5
en otro caso
ratio(pi) = Pr(relevant_text|text_contain_pi) = rel_freq_pi /
total_freq_pi
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
AutoSlog-TS (Riloff[96])
• Pros:
• Menos supervisión
• Resultados comparables a AutoSlog
•Cons:
(todos los métodos no supervisados de este área)
•Cons:
(específicos)
•Clasificar manualmente a posteriori cada patrón
con respecto al conjunto de slots del escenario
•Validar manualmente los patrones resultados
•La formula de relevancia tiende a subir
patrones frecuentes y bajar muchos patrones
relevantes menos frecuentes
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
Harabagiu & Maiorano [00]
Heuristic-driven specialization
• Conjunto de palabras relevantes
• Adquisición de reglas multi-slot (eventos)
• Método similar a AutoSlog
• Meta-patrones sustituidos por espacio semantico
inducido a partir de la palabras relevantes sobre
WordNet
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
Harabagiu & Maiorano [00]
keywords
WordNet
semantic
space
…( □ )……( □ )…( □ )…
S
V
O
• Generalización de los conceptos enlazados
• Selección de los patrones más generales
(Máxima cobertura)
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
Harabagiu & Maiorano [00]
• Pros:
• Menor supervisión que AutoSlog y AutoSlog-TS
•Cons:
•Método automático para la selección?
•Ningún resultado sobre la cobertura de los patrones
aprendidos.
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
Essence [Català03]
Observation-based Learning
• Conjunto de palabras relevantes
• Adquisición de reglas multi-slot
• Método similar a CRYSTAL
• Observación = contexto de ocurrencia de palabra
relevante o alguna extension WordNet
= patron específico de constituyentes
• Algoritmo de cobertura bottom-up: generalización
sintáctico-semántica (WordNet) de los patrones
específicos
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
Bootstrapping
• Requiere un conjunto inicial pequeño de ejemplos y un
corpus grande no anotado
• Se aprenden patrones a partir del conjunto de ejemplos
iniciales
• Se reconocen nuevos ejemplos con los que se aprenden
nuevos patrones
• …
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
ExDISCO [Yangarber02]
Bootstrapping
• Conjunto inicial de patrones SVO
• Clasificación de los textos (rel/norel)
• Adquisición de nuevos patrones a partir de los textos
relevantes de forma similar a AutoSlog-TS
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
Bootstrapping
• Pros:
• Poca supervisión
• Cons:
• Dependiente del conjunto inicial de ejemplos
• Poco robusto a la aceptación de patrones erroneos
• Condición de parada?
[Yangarber03]
Jordi Turmo, 2010
[Agichtein&Gravano00]
[Yangarber03]
[Surdeanu et al. 06]
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
[Yangarber03]
Bootstrapping via Counter-training
• Condición de parada para bootstrapping
• Aprendizaje de patrones para diferentes escenarios en
paralelo
• Cada proceso computa la precisión de cada patrón
aprendido en cada iteración
• Evidencia positiva (relevancia inter-escenario)
• Evidencia negativa (relevancia intra-escenario)
• Repetir hasta que solo queda un proceso activo
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
[Yangarber03]
Bootstrapping via Counter-training
• Contra:
• Requiere la clasificación a priori de los documentos
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
[Surdeanu et al.06]
Bootstrapping via Co-training
• A cada iteración
• Aprendizaje de patrones de diferentes escenarios
• Aprendizaje de clasificador de documentos
(palabras)
• Repetir hasta que no se aprendan patrones nuevos o
i=n
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de reglas (no supervisado)
[Surdeanu et al.06]
Bootstrapping via Co-training
Labeled seed docs
Unlabeled docs
Init
NB-EM
Init
Pattern
acquisition
NB-EM
Converged?
no
NB-EM
iteration
Pattern
Acquisition
iteration
si
no
Jordi Turmo, 2010
Pattern
Acquisition
Terminated?
si
patterns
Adaptive Information Extraction
Adaptability
Summary
• Information Extraction Systems
• Evaluation
• Multilinguality
• Adaptability
• Introduction
• Learning of rules
• Learning of statistical models
• Multistrategy learning
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
• Aprendizaje supervisado
• slot-filler extraction models, relation extraction
models
–
–
–
–
–
Hidden Markov Models (HMMs)
Maximum Entropy Models (MEMs)
Dynamic Bayesian Networks (DBNs)
Conditional Random Fields (CRFs)
Hyperplane Separators
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
• Hidden Markov Model (HMM): autómata finito
que tiene probabilidades asociadas a las
transiciones entre estados y a la emisión de
símbolos desde cada estado.
–Pros: robustez, facilidad de desarrollo y evaluación
–Cons: conocimiento a priori de la topología del modelo;
requieren enormes conjuntos de entrenamiento; un
atributo por token (representación pobre)
–Ejemplos:
•Texto semi-estructurado: Freitag and McCallum[99,00], Seymore et
al.[99]
•Texto no restingido: Freitag and McCallum[99,00], Ray and
Craven[01]
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
HMM = conjunto de estados
q0, q1, ..., qn
conjunto de transiciones
( q → q’ )
vocabulario símbolos de
emisión
Σ = {σ 0, σ 1, ..., σ m }
estado inicial q0
estado final qn
probabilidades de transición
entre estados
P( q → q’ )
probabilidades de emisión de
símbolos desde un estado
P( q ↑ σ )
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Ejemplo: extracción de info en cabeceras de
artículos (etiquetar cada palabra de la cabecera como title,
author, date, keyword).
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
EI usando HMMs:
• Dado un modelo M y sus parámetros, la EI se lleva a
cabo determinando la secuencia de estados más
probable que haya generado el documento
(observación).
• Esta secuencia puede ser calculada usando
programación dinámica: algoritmo de Viterbi.
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Freitag and McCallum[99]
Crea un HMM para cada slot. Se fija la topología y se aprenden las
probabilidades de transición y emisión. Dos tipos de estados,
background y target, con conexiones limitadas para capturar el
contexto.
Texto semi-estructurado y texto no restringido.
start
target
bg
end
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Freitag and McCallum[99]
Variaciones en la topología: tamaño de la “ventana” de contexto y
substitución de un target por un conjunto de caminos paralelos de
distinta longitud.
Probs. Transición y emisión se aprenden tratando la sparseness
start
bg
prefix
Jordi Turmo, 2010
prefix
target
end
sufix
sufix
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Freitag and McCallum[00]
Freitag and McCallum[00], la topología se aprende vía stochastic
optimization (hill climbing en el espacio de topologías posibles).
- modelo inicial simple M0
- conjunto de operadores (state-split, state-add, trans-add,…)
- h’(Mi) = F1
Mejoran los resultados
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Topologías aprendidas para
location y speaker.
Freitag and McCallum[00]
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Seymore et al.[99]
A partir de los datos de entrenamiento:
• aprender la topología del HMM (usando técnica de Bayesian
model merging) y
• estimar sus parámetros:
– datos etiquetados (maximum likelihood),
– no etiquetados (algoritmo de Baum-Welch) y
– distantly-labeled (para estimar probabilidades de emisión)
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(HMM)
Ray and Craven[01]
Las sentencias no sólo son secuencias de tokens; se añade su
estructura gramatical.
Los estados del HMM representan información gramatical de una
sentencia (type) y su anotación (label); los parámetros
maximizan la correcta asignación de etiquetas a ciertos
segmentos no a toda la sentencia.
Texto no restringido.
This enzyme, UBC6, localizes
to the endoplasmic
reticulum, with the
catalytic domain facing the
cytosol.
Jordi Turmo, 2010
NP_SEGMENT
this enzyme
NP_SEGMENT:PROTEIN
ubc6
NP_SEGMENT
localizes
PP_SEGMENT
to
NP_SEGMENT:LOCATION
the endoplasmic reticulum
PP_SEGMENT
with
NP_SEGMENT
the catalyctic domain
VP_SEGMENT
Adaptivefacing
Information Extraction
NP_SEGMENT
the cytosol
Adaptability
Aprendizaje de modelos estadísticos
• Maximum Entropy Model (MEM): estima la
probabilidad de que cierta “clase” ocurra en
cierto “contexto”, sujeta a restricciones
impuestas por las observaciones
(p.e. POS adecuado a un token en un contexto, traducción de un
palabra en un contexto).
– Pros: facilidad para extender la cantidad y el tipo de
atributos; atributos dependientes; método de
estimación general (reutilizable)
– Cons: coste computacional
– Ejemplos:
• Texto semi-estructurado: Chieu and Ng[02]
• Texto no restringido: Chieu and Ng[02], Kambhatla[04]
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(MEM)
Chieu and Ng[02]
Paso I (single-slot): clasificar cada palabra en una de las clases
posibles (slots o partes de un slot). Después, usa Viterbi para
seleccionar la secuencia de clases más probable.
Paso II (multi-slot): determinar si dos slot fillers forman parte de
la misma templeta, usando un clasificador de relaciones.
Texto semi-estructurado y texto no restringido.
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
Ejemplo de Chieu
(MEM)
and Ng[02]:
Bronczek, vice president of Federal Express Canada Ltd., was
named senior vice president, Europe, Africa and Mediterranean,
at this air-express concern.
Bronczek, Person In
Federal Express Canada Ltd.,
Organization
Bronczek, Person Out
VP, Post
SVP, Post
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
(MEM)
Kambhatla[04]
Construye MEMs para predecir el tipo de relación que existe
entre pares de menciones (ACE RDC task) en una frase.
Combina atributos léxicos, semánticos y sintácticos.
Los atributos sintácticos se derivan del árbol sintáctico y del
árbol de dependencias, obtenidos usando un parser estadístico
basado en ME.
Texto no restringido.
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
• Dynamic Bayesian Networks: generalización de
HMM para permitir la codificación de
dependencias entre características.
– Pros: permite reducir el coste del aprendizaje usando
conocimiento del dominio; permite múltiples
atributos por token pero no su contexto
– Cons: estructura de la red predefinida manualmente
– Ejemplos:
• texto semi-estructurado: Peshkin and Pfeffer[03]
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadísticos
• Conditional Random Fields: modelo de estados
finito de probabilidad condicional.
– Pros: relaja requerimiento de independencia entre
variables de los HMM
– Cons: probabilidad condicional sobre una única
variable
– Ejemplos:
• texto semi-estructurado: Coxe[05]
Presentación
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de modelos estadisticos
• Hyperplane separators: aprenden un
hiperplano en el espacio de las características
que separa los ejemplos de un concepto entre
+ i - (p.e. SVM, Voted Perceptron)
– Pros: pueden trabajar con muchas propiedades
– Cons:
– Ejemplos: Roth and Yih[01], Sun et al.[03], Chieu et
al.[03], Zelenko et al.[03], Finn and Kushmerick[04],
Zhao and Grishman[05]
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Aprendizaje de hiperplanos separadores
Ejemplos:
• texto semi-estructurado: Roth and Yih[01]
• texto no restringido: Sun et al.[03], Chieu
et al.[03], Zelenko et al.[03], Finn and
Kushmerick[04], Zhao and Grishman[05]
Presentación
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Summary
• Information Extraction Systems
• Evaluation
• Multilinguality
• Adaptability
• Introduction
• Learning of rules
• Learning of statistical models
• Multistrategy learning
Jordi Turmo, 2010
Adaptive Information Extraction
Adaptability
Métodos multiestrategia
Combinan distintos métodos de aprendizaje
automático.
– Freitag[98]: rote memorization, term-space
text classification y inducción de reglas
relacionales (SRV)
– Turmo and Rodríguez[02], Turmo[02]:
closed-loop learning, deductive restructuring y
constructive induction
Jordi Turmo, 2010
Adaptive Information Extraction
Descargar

Aprendizaje de reglas/patrones