Tecnicas cuantitativas para laextraccion de terminos en un corpus

Jordi Porta Zamorano

Escuela PolitecnicaUniversidad Autonoma de Madrid

jordi.porta@uam.es

12 de julio de 2006

Definicion de termino

Norma ISO 1087 (1990):

“La designacion de un concepto definido en un lenguajeespecializado mediante una expresion linguıstica. Nota: Un terminopuede estar compuesto por una sola palabra o por dos o mas.”

Problemas (para la extraccion automatica):

I no proporciona criterios operacionales

I se necesita conocimiento de mundo y de dominio

Solucion:combinar su estructura (morfologica, sintactica, . . . ) con susdistribuciones estadısticas en distintas dimensiones:

I unidad (unithood)

I pertenencia a un dominio (domainhood)

I uso especializado (specialized usage)

Contenidos

I descripcion de los materiales usados

I metodologıa para la evaluacion de un sistema de extraccionI medidas para la extraccion en distintas dimensiones:

I unidad (unithood)I pertenencia a un dominio (domainhood)I uso especializado (specialized usage)

I combinacion de medidas con aprendizaje automatico

I evaluacion final

Descripcion del corpus de trabajoy

otros materiales empleados

Corpus especializado

I Journal of Computational Linguistics (JCL)1980–2003

I proviene del archivo digital ACL Anthology(http://acl.ldc.upenn.edu)

I 1.179 documentos: artıculos, resenas, editorialesy anuncios

I 7.949.153 palabras

Anotacion del JCL (1/2)

I PDF → OCR → texto → preprocesamiento → anotacion

I anotador TnT con etiquetario Penn Treebank(http://www.cis.upenn.edu/∼treebank/)

I Thorsten Brants. TnT – A Statistical Part-of-Speech Tagger.Proceedings of the Sixth Applied Natural LanguageProcessing, 2000

I preprocesamiento:I segmentacion de palabrasI reconstruccion heurıstica de palabras partidas a final de lınea

(segun frecuencia con y sin “-”)I conversion heurıstica a minusculas de palabras a principio de

oracion (segun frecuencia con distintas cajas tipograficas)

Anotacion del JCL (2/2)

back-of-indices or for document-collection navigation, and also for compilingcontrolled vocabulary terminologies such as are used in, for example, medical cod-ing applications. Several papers address this topic. Most generically, a review paperby M. Teresa Cabre CastellvI, Rosa Estopa Bagot, and Jordi Vivaldi Palatresi reviewstwelve current term extraction systems, including well-known systems such as LEX-

for IN

compiling VBG

controlled VBN

vocabulary JJ

terminologies NNS

such JJ

as IN

are VBP

used VBN

in IN

, ,

for IN

example NN

, ,

medical JJ

coding JJ

applications NNS

. .

several JJ

papers NNS

address VB

this DT

topic NN

. .

most RBS

generically RB

, ,

a DT

review NN

paper NN

by IN

M NNP

. .

Teresa NNP

Cabre NNP

CastellvI NNP

, ,

Rosa NNP

Estopa NNP

Bagot NNP

, ,

and CC

Jordi NNP

Vivaldi NNP

Palatresi NNP

reviews VBZ

twelve CD

current JJ

term NN

extraction NN

systems NNS

Corpus de referencia

I British National Corpus (BNC)I 100 millones de palabras de ingles britanicoI sincronicoI diseno equilibradoI 90 % de material escrito y 10 % oralI anotadoI http://www.natcorp.ox.ac.uk

I reanotado con TnT

Estructura de los terminos

I designaciones =⇒ SSNN

I . . . | JJ NN | JJ NN IN NN | JJ NN IN NNP | JJ NN IN NNS| JJ NN JJ NN | JJ NN JJ NNP | JJ NN JJ NNS | JJ NNJJR NN | JJ NN NN | JJ NN NN NN | JJ NN NN NNP | JJNN NN NNS | JJ NN NNP | JJ NN NNP NN | JJ NN NNPNNP | JJ NN NNP NNS | JJ NN NNS | JJ NN NNS NN | JJNN NNS NNP | JJ NN NNS NNS | JJ NNP | JJ NNP INNNP | . . .

Distribucion de palabras en un corpus: La Ley de Zipf

I si ordenamos las palabras de un texto de la mas comun a lamas rara, la frecuencia decrece exponencialmente

I la frecuencia de una palabra (f ) y su posicion en el ranking de(r) estan relacionadas:

f =k

r

k ≈ 1 (depende del corpus) 1

10

100

1000

10000

100000

1e+06

1 10 100 1000 10000lo

g(fre

c)

log(rank)I es una caracterıstica del lenguaje humanoI George K. Zipf. Human Behavior and the Principle of Least

Effort. Addison-Wesley, 1949I Ramon Ferrer i Cancho. Language: universals, principles and

origins. PhD thesis, Universitat Politecnica de Catalunya,Barcelona, 2003

Origenes de la Recuperacion de la Informacion

I los terminos ındice o las palabras clave son elementos concontenido que permiten recuperar documentos relevantes

I Luhn: las palabras interesantes para la indexacion son aquellasque f · r ≈ k

I Luhn establece dos umbrales dentro de los cuales las palabrasahı contenidas contribuirıan al contenido del documento

Hans Peter Luhn. A Statistical Approach to Mechanized Encodingand Searching of Literary Information. IBM Journal of Researchand Development, 2(2), 1958

Evaluacion de un sistema de extraccion de terminos

Evaluacion de un sistema de extraccion de terminos

Evaluar la actuacion de un sistema nos interesa para:

I valorarlo

I mejorarlo

I compararlo

I cambiarlo

Para una correcta evaluacion se necesitaran a priori ejemplos de:

I terminos

I no terminos

Ejemplos de terminos y no terminos

I fuentes:

I glosario de Robert Dale, H. L. Somers, andHermann Moisl, editors. Handbook of NaturalLanguage Processing: Techniques andApplications for the Processing of Languageas Text. 2000

I ındice de Christopher D. Manning andHinrich Schutze. Foundations of StatisticalNatural Language Processing. 1999

I muestreo aleatorio del JCL: palabras ybigramas clasificados manualmente

Simples Complejos Total

Terminos 296 447 743No terminos 124 581 705

Total 420 1028 1448

Predicciones de un sistema: matriz de confusionLa comparacion de las predicciones del sistema con las clases realesda lugar a distintos grupos:

I verdaderos positivos (VP):terminos correctamente reconocidos por el sistema

I falsos negativos (FN):terminos que el sistema dice que no lo son

I falsos positivos (FP):no terminos que el sistema dice que son terminos

I verdaderos negativos (VN):no terminos correctamente reconocidos como tales

se disponen en una matriz de confusion:

Clase predicha

Clase real Termino No termino

Termino verdaderos positivos falsos negativos

No termino falsos positivos verdaderos negativos

Tasas de acierto y error

Tasa de acierto:porcentaje de ejemplos bien clasificados

tasa de acierto =VP + VN

N

Tasa de error:porcentaje de ejemplos mal clasificados

tasa de error =FP + FN

N

(N = VP + FN + FP + VN)

Incorporacion de costes y beneficios

I los fallos pueden tener costes

I los aciertos pueden tener beneficios

I se expresan en una matriz de costes y beneficios

Clase predicha

Clase real Termino No termino

Termino BVP CFN

No termino CFP BVN

I su combinacion con la matriz de confusion darıa las siguientesevaluaciones:

beneficio = VP · BVP + VN · BVN

coste = FP · CFP + FN · CFN

Cobertura y precision (RI) (1/2)

Cobertura (recall):

¿estan todos los que son?

cobertura =terminos correctamente reconocidos

total de terminos reales=

VP

VP + FN

Precision:¿son todos los que estan?

precision =terminos correctamente reconocidos

total de terminos predichos=

VP

VP + FP

F -measure:

F =2 · cobertura · precision

cobertura + precision

Cobertura y precision (RI) (2/2)

La cobertura y la precision mantienen, por lo general, una relacioninversa:

I aumenta la cobertura =⇒ disminuye la precisionI se reconocen mas terminosI y cosas que no lo son

I aumenta la precision =⇒ disminuye la coberturaI disminuyen los falsos terminosI dejandose de reconocer algunos verdaderos

I cobertura total =⇒ precision nulaI todos son terminosI incluso los que no lo son

Sensibilidad y especificidad

I originadas en la Teorıa de la Deteccion de la Senal

I usados en diagnostico medico (70s) y Aprendizaje Automatico(90s)

Sensibilidad (tasa de verdaderos positivos) (= cobertura):

cuantos terminos son reconocidos como tales

sensibilidad =terminos correctamente reconocidos

total de terminos reales=

VP

VP + FN

Especificidad (1− tasa de falsas alarmas):

cuantos no terminos se han clasificado como tales

especificidad =no term. correct. recon.

total de no term. reales=

VN

VN + FP= 1− FP

FP + VN

Silencio y ruido

Ruido (= 1− precision):

ruido =falsos terminos

terminos predichos=

FP

VP + FP

Silencio (= 1− cobertura):

silencio =terminos no reconocidos

terminos reales=

FN

VP + FN

I usados en extraccion de terminologıaI estan relacionados de manera inversa

I disminuir el silencio provoca ruidoI disminuir el ruido aumenta el silencio

Curvas ROC (Receiver Operating Characteristic)

I desarrolladas dentro de la Teorıa de la Deteccion de la SenalI permite evaluar y comparar clasif. con independencia de:

I la distribucion de las clases (proporcion terms./no terms.)I el coste de los errores

I y: tasa VP = VP/(VP +FN)I x: tasa FP = FP/(FP +VN)

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

M1

M3

M4

M6

M2

M5

Analisis de curvas ROC

I los clasificadores mas proximos a la esquina superior izquierdase consideran buenos clasificadores:

I tasa VP elevadaI tasa FP baja

I los clasificadores situados en la envolvente convexa (M1, M3,M4 y M6) son optimos para alguna relacion coste-beneficio,no los que quedan por debajo de esta curva (M2 y M5)

I el clasificador que mejor opera es aquel que estando situadosobre la envolvente convexa tiene como tangente una rectacon pendiente:

numero de no terminos

numero de terminos· CFP

CFN

I 45◦ =⇒ M3I 75◦ =⇒ M1I 25◦ =⇒ M4

Rankers

I algunos clasificadores asignan un valor numerico

I es necesario un parametro (umbral) para determinar la clase

I ejemplo: ranker basado en la frecuencia:

Frec. VP FP VP-rate FP-rate

19157 1 0 0,003 010333 2 0 0,007 08609 3 0 0,010 0

. . .814 69 11 0,251 0,096812 69 12 0,251 0,105809 70 12 0,255 0,105790 70 13 0,255 0,114766 71 13 0,259 0,114

. . .11 269 110 0,981 0,96410 272 114 0,992 13 273 114 0,996 12 274 114 1 1

Analisis de curva ROC para rankers: la AUC

I punto de operacion optimo: con la tangenteI el area bajo la curva ROC (AUCs) permite:

I valorar rankers

regular 0,50–0,75bueno 0,75–0,92muy bueno 0,92–0,97excelente 0,97–1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

AUC = 0,677I comparar rankers

I tambien puede usarse otro tipo de curvas:I curvas de cobertura-precisionI curvas liftI curvas de coste

Uso especializado

Uso especializado

Hipotesis de trabajo:

las palabras y expresiones relativamente mas frecuentes en textosde especialidad seran probablemente parte del vocabularioespecıfico de ese corpus

Comparacion entre frecuencias relativas

I ratio entre frecuencias relativas

RFR(w) =fG (w)

fS(w)

Fred J. Damerau. Generating and EvaluatingDomain-Oriented Multi-Word Terms from Text. InformationProcessing & Management, 29(4), 1993

I diferencia entre frecuencias relativas

DFR(w) = fS(w)− fG (w)

I ındice de Yule

Y (w) =fS(w)− fG (w)

fG (w) + fS(w)

George U. Yule. Statistical Study of Literary Vocabulary.Cambridge University Press, 1944

Interpretacion de RFR (1/2): zonas de un grafico RFR

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

Frec

. en

A

Frec. en B

A

B

Interpretacion de RFR (2/2): terminos y no terminossimples

0

2e-05

4e-05

6e-05

8e-05

0.0001

0 2e-05 4e-05 6e-05 8e-05 0.0001

Frec

. en

el J

CL

Frec. en el BNC

tØrminosno tØrminos

Contrastes de hipotesis

I se formula una hipotesis nula (H0) que mantiene que ladiferencia entre O y E es debida al azar. Implıcitamente existeuna hipotesis alternativa (H1).

I se elige un estadıstico con el que calcular una cantidad Cα

denominada el valor crıtico. Con ese valor se decide si serechaza o no H0. La eleccion del estadıstico del test dependede la distribucion estadıstica del fenomeno y del tipo dehipotesis formulada.

I se calcula el nivel de significacion del test, la probabilidad derechazar erroneamente H0, consultando las tablas de ladistribucion de referencia del test con el valor Cα.

I si el nivel de significacion no es lo suficientemente alto (lohabitual es un 10, 5 o 1 % dependiendo de la exigencia delresultado) se rechaza H0 a favor de H1.

Contrastes: el test t de Student

I version para contrastar las medias de dos muestras paradeterminar si se trata de la misma poblacion

I las variables que se miden deben seguir distribucionesnormales (no es el caso)

t(w) ≈ fS(w)− fG (w)√fS(w)/NS + fG (w)/NG

Contrastes: el test de χ2

I es un test de independencia estadıstica

I no asume normalidad

I apropiado cuando las frecuencias son altas

X 2 =∑i ,j

(Oij − Eij)2

Eij, Eij =

∑j Oij∑i Ni

aplicacion: Adam Kilgarriff and Tony Rose Measures for corpussimilarity and homogeneity Proceedings of the 3rd Conference onEmpirical Methods in Natural Language Processing. 1999

Contrastes: la ratio de verosimilitud (G 2)

I χ2 no es fiable cuando para frecuencias pequenas

I sobreestima palabras de alta frecuencia cuando se comparancorpus de tamanos distintos

G 2 = 2∑ij

Oij · lnOij

Eij, Eij =

Nj ·∑

k Oik∑k Nk

Ted Dunning. Accurate Methods for the Statistics of Surpriseand Coincidence. Computational Linguistics, 19(1), 1993

I en Robert C Moore. On Log-likelihood-Ratios and theSignificance of Rare Events. Proceedings of the Conference onEmpirical Methods in Natural Language Processing, 2004 secuestiona la superioridad absoluta del test

Evaluacion de medidas para la extraccion de terminossimples basadas en la comparacion de frecuencias

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

YULERFR

G2X2

TTF

Metodo AUC

RFR 0,874Y 0,874t 0,825

G 2 0,785X 2 0,737f 0,600

(a) Curvas ROC (b) AUCs

RFR con el BNC y en varios de sus subcorpus para laextraccion de terminos simples del JCL: curvas ROC

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

BNCdomain=W_leisure

domain=W_artsdomain=W_belief_thought

domain=W_soc_sciencedomain=W_imaginative

domain=W_app_sciencedomain=W_world_affairsdomain=W_nat_science

domain=W_commerce

RFR con el BNC y en varios de sus subcorpus para laextraccion de terminos simples del JCL: AUCs

Dominio AUC Palabras

BNC 0,874 100.615.847W arts 0,870 7.254.473

W world affairs 0,868 17.647.749W commerce 0,867 7.478.464W imaginative 0,861 21.829.929W soc science 0,859 15.240.118

W leisure 0,855 11.050.014W app science 0,845 7.745.784

W belief thought 0,844 3.357.964W nat science 0,838 4.050.941

Pertenencia a un dominio

Pertenencia a un dominio

Hipotesis de trabajo:

I algo que aparecen en todos los documentos no parece tenermucha probabilidad de ser termino

I si el corpus contiene varios dominios es esperable que losterminos aparezcan en varios documentos

I las medidas presentadas estan tomadas del campo de la RI

La frecuencia inversa de documento (IDF)

I Karen Sparck Jones A statistical interpretation of termspecificity and its application in retrieval Journal ofDocumentation, 28, 1972

IDF(w) = − log2DF(w)

D

I TF*IDF: Gerald Salton Automatic Text Processing: TheTransformation, Analysis and Retrieval of Information byComputer Addison-Wesley, 1989

La frecuencia inversa de documento residual (RIDF)

I la ley de Zipf describe la frecs. de palabras en un corpus

I la distribucion de Poisson ajusta bien la distribucion de laspalabras sin contenido (predice su numero de ocurrencias enfuncion la longitud del documento)

IDF(w) = log2 1− eTF(w)

D

RIDF(w) = IDF(w)− IDF(w)

Kenneth W. Church and William Gale Inverse DocumentFrequency (IDF): A Measure of Deviation from PoissonProceedings of the Third Workshop on Very Large Corpora. 1995

Evaluacion de medidas para la extraccion de palabras ybigramas

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

fIDF

RIDFTF*IDF

Medida AUC

RIDF 0,856TF*IDF 0,731

f 0,695IDF 0,463

(a) Curvas ROC (b) AUCs

Unidad

Unidad

Hipotesis de trabajo:

I muchos terminos son complejos

I dichos terminos son colocaciones en un corpus de especialidad

I se pueden usar todas las tecnicas de extraccion de asoc. lexicas

I problemas: pueden mostrar variacion formal o discontinuidad

I solo nos ocuparemos de bigramas

Evert, Stefan, The Statistics of Word Cooccurrences: Word Pairsand Collocations, PhD thesis, University of Stuttgart. 2004http://www.collocations.de

Contrastes de hipotesis

I hasta que punto la probabilidad de coocurrencia de dospalabras es superior a la esperada cuando esas dos palabrasson independientes y forman una combinacion libre

I H0: w1w2 son combinacion libre

I bajo H0 la probabilidad de coocurrencia es:

Pr(w1w2) = Pr(w1) · Pr(w2)

I el modelo es tachado de simple y empıricamente inadecuado

Contrastes

I el test t de Studentversion para un test de independencia

t =Pr(w1w2)− Pr(w1) · Pr(w2)√

Pr(w1w2)N

Church, Kenneth W. and Gale, William and Hanks, Patrickand Hindle, Donald Using statistics in lexical analysis. LexicalAcquisition: Using On-line Resources to Build a Lexicon, 1991

I el test de χ2

la misma formulacion de (X 2) se usa como medida deasociacion lexica en las mismas condiciones

I la ratio de verosimilitud (G 2)

G2 = O11 ln O11 + O12 ln O12 + O21 ln O21 + O22 ln O22 + N ln N− (O11 + O21) ln(O11 + O21)− (O11 + O12) ln(O11 + O12)− (O21 + O22) ln(O21 + O22)− (O22 + O12) ln(O22 + O12)

Informacion mutua (MI)

I fundamentada en la Teorıa de la Informacion

I usada para calcular el grado de asociacion lexica

I Kenneth W. Church and Patrick Hanks. Word AssociationNorms, Mutual Information and Lexicography. ComputationalLinguistics 16(1). 1990.

MI(w1w2) = − log2Pr(w1w2)

Pr(w1) · Pr(w2)

I interpretacion:I MI > 0: asociacion interesanteI MI = 0: asociacion poco interesanteI MI < 0: combinacion libre

I problemas: sobreestimacion de bigramas con baja frecuencia

I soluciones: corrigir este sesgo heurısticamente

Heurısticas basadas en la MI

I informacion mutua al cuadrado

MI2(w1w2) = − log2Pr(w1w2)

2

Pr(w1) · Pr(w2)

I informacion mutua

MI3(w1w2) = − log2Pr(w1w2)

3

Pr(w1) · Pr(w2)

Beatrice Daille, Eric Gaussier, and Jean Marc Lange. AnEvaluation of Statistical Scores for Word Association.J. Ginzburg, Z. Khasidashvili, C. Vogel, J. J. Levy, andE. Vallduvı, editors, The Tbilisi Symposium on Logic,Language and Computation: Selected Papers, 1998.

Extensiones de la MI a n-gramas

I problemas: la MI es que solo es aplicable a bigramasI soluciones:

I informacion mutua generalizada

GMI(t) =Pr(aφb) · Pr(φ)

Pr(aφ) · Pr(φb)

Mikio Yamamoto and Kenneth W. Church. Using Suffix Arraysto Compute Term Frequency and Document Frequency for AllSubstrings in a Corpus. Computational Linguistics, 27(1), 2001

I entropıa contextualI C-value y NC-value: Katerina Frantzi, Sophia Ananiadou and

Hideki Mima. Automatic recognition of multi-word terms: theC-value/NC-value method. Journal on Digital Libraries, 3(2),2000

Medidas asociativas para la extraccion de bigramasterminologicos

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

fMI

MI2T

G2X2

Medida AUC

MI2 0,767−G 2 0,753MI 0,741t 0,700f 0,672

X 2 0,618

(a) Curvas ROC (b) AUCs

Combinacion de medidas

Combinacion de medidas

I las dimensiones vistas no parecen estar correlacionadas

I existen medidas capaces de extraer terminos aun con errores

I casi todas funcionan mejor que la frecuencia

I se pueden combinar con tecnicas de reconocimiento depatrones o con algoritmos de aprendizaje automatico

I el modelo obtenido servira para extraer nuevos terminos

Ejemplos y atributos usados para la construccion declasificadores

todos los algoritmos usados son supervisados y necesitan deejemplos previamente clasificados

n-grama POS n f MI2 RIDF RFR clasedifferent areas JJ NNS 2 1,509 −14,55 −0,007 0,517 −

motion NN 1 11,071 - 0,678 0,263 −structural descriptions JJ NNS 2 5,913 −9,825 0,825 1514,770 +

measures NNS 1 56,113 - 1,279 0,955 +other node JJ NN 2 1,635 −17,357 0,885 118,341 −

special type JJ NN 2 1,383 −15,666 −0,006 3,244 −exhaustive search JJ NN 2 1,761 −9,856 0,476 72,027 +

structural complexity JJ NN 2 1,635 −12,947 0,692 28,957 +syntax NN 1 236,533 - 0,772 48,146 +

epenthesis NN 1 2,516 - 1,725 84,019 +overgeneration NN 1 5,032 - 1,210 171,180 +

classification problem NN NN 2 1,887 −14,728 0,575 9478815,497 +nominalization NN 1 8,681 - 1,607 103,294 +

different features JJ NNS 2 2,516 −15,467 −0,012 15,993 −appropriate type JJ NN 2 2,138 −14,515 0,170 24,415 +

explanation NN 1 110,843 - 1,334 2,440 +belief NN 1 132,987 - 2,257 2,713 +

complexity NN 1 163,686 - 1,082 9,695 +

Clasificadores 1/6

IBk (k Instance-Based Classifier):

I usa una funcion de similitud entre ejemplos

I asigna la clase predominante de los k vecinos mas similares

David W. Aha, Dennis Kibler, y Marc K. Albert. Instance-basedlearning algorithms. Machine Learning, 6, 1991

Clasificadores 2/6

J48 (C4.5):

I genera arboles de decision

I ejemplo:

ridf <= 0.456951| rfr <= 21.748107: n (458.0/23.0)| rfr > 21.748107| | ridf > 0.099599| | | mi2 <= -15.2969| | | | rfr > 91.929478| | | | | rfr <= 493.150004: y (5.0/1.0)| | | | | rfr > 493.150004: n (8.0/1.0)| | | | rfr <= 91.929478: n (13.0)...

J. Ross Quinlan. C4.5: Programs for Machine Learning. MorganKaufmann, 1993.

Clasificadores 3/6

PART:

I genera listas de decision a partir de C4.5

I ejemplo:

ridf <= 0.456951 AND rfr <= 21.748107 AND n > 1: n (421.0/18.0)rfr > 2.018956 AND ridf > 0.644812 AND f > 1.88723AND ridf > 0.898164 AND rfr > 5.451567: y (353.0/16.0)

Eibe Frank y Ian H. Witten. Generating Accurate Rule SetsWithout Global Optimization. Proceedings of the FifteenthInternational Conference on Machine Learning, 1998

Clasificadores 4/6

Bagging:

I metametodo de aprendizaje

I cada clasificador vota

I asigna la clase mas votada

Leo Breiman. Bagging predictors. Machine Learning, 23(2), 1996

Clasificadores 5/6

AdaBoost:

I metametodo de aprendizaje

I voto de cada clasificador ponderado segun el acierto estimadodurante el aprendizaje

Robert E. Schapire. Theoretical views of boosting and applications.Tenth International Conference on Algorithmic Learning Theory,1999

Clasificadores 6/6

Naıve Bayes:

I usa el teorema de Bayes:

Pr(H|E ) =Pr(E |H) · Pr(H)

Pr(E )

I asigna la clase mas verosımil en funcion de los valores de susatributos

I base para la comparacion de otros metodos de aprendizaje

I supone independencia entre atributos

Richard O. Duda, Peter E. Hart, y David G. Stork. PatternClassification. Wiley Interscience, 2 Ed, 2000

Evaluacion: error de resustitucion

I error medido sobre el conjunto de entrenamiento

I acostumbra a ser demasiado optimista

I se pueden detectar errores en los conjuntos de entrenamiento

Matriz de confusion % %Metodo VP VN FP FN Acierto Error

IB5 628 583 121 86 85,40 14,59J48 658 604 100 56 88,99 11,00

AdaBoost 641 537 167 73 83,07 16,92Bagging 662 613 91 52 89,91 10,08

Naıve Bayes 338 646 376 58 69,39 30,60PART 637 612 92 77 88,08 11,91

Evaluacion: validacion cruzada

I hold-out:I reservar una parte para test y el resto para entrenarI factible cuando se tienen muchos datos

I validacion cruzada:I los datos se dividen m veces para hacer hold-out:

I una particion se usa para entrenarI la otra se usa para test

I ejemplo m = 3:

I es estratificada cuando las particiones conservan lasdistribuciones de las clases

I validacion estandar: 10 stratified 10-fold cross-validation

Error con validaciones cruzadas y espacio ROC con losclasificadores

Matriz de confusion % Acierto Cobertura Ruido TP-rateMetodo VP VN FP FN / Error / Precision / Silencio FP-rate

IB5 61,50 52,81 17,59 9,90 80,61/19,39 0,86/0,78 0,22/0,14 0,86/0,25J48 63,04 57,25 13,15 8,36 84,83/15,17 0,88/0,83 0,17/0,12 0,88/0,19

AdaBoost 59,81 56,49 13,91 11,59 82,02/17,98 0,84/0,81 0,19/0,16 0,84/0,20Bagging 63,07 58,86 11,54 8,33 85,99/14,01 0,88/0,85 0,15/0,12 0,88/0,16

Naıve Bayes 33,69 64,16 6,21 37,71 69,03/30,97 0,47/0,85 0,15/0,53 0,47/0,09PART 63,14 56,52 13,88 8,26 84,39/15,61 0,88/0,82 0,18/0,12 0,88/0,20

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

TP ra

te

FP rate

IB5J48

BoostBagg

Bayes

PART

Clasificador final

la validacion nos sirve para elegir el modelo del clasificador:

I se estiman sus parametros con todos los ejemplos disponibles

I se usara para clasificar el resto de ejemplos del corpusI se puede hacer bootstrapping:

I especialistas validan/corrigen los nuevos ejemplos clasificadosI se incorporan al conjunto de entrenamientoI se vuelve al primer punto