Classificação Probabilística com TBL Cícero Nogueira dos Santos Pontifícia Universidade Católica do Rio de Janeiro – PUC-Rio Departamento de Informática

Classificação Probabilística com TBL

Cícero Nogueira dos Santos

Pontifícia Universidade Católica do Rio de Janeiro – PUC-RioDepartamento de Informática / Pos-Graduação

Classificação Probabilística com TBL 2

Sumário Introdução O algoritmo TBL Estimando probabilidades

Método proposto Método de Florian et. al (2000) Particionando classes de equivalência Suavização

Experimentos e resultados English Text Chunking English Base-Noun Phrase Identification

Conclusões


IntroduçãoTransformation Based Learning (TBL)

Desenvolvido por Eric Brill (1995) para etiquetagem morfossintática

Aprendizado supervisionadoGera uma lista ordenada de regrasUsado para várias tarefas de PLN, geralmente tratadas como problemas de classificação

Algoritmo guloso


IntroduçãoDesvantagem: não gera probabilidades na classificação

Por que estimar probabilidades?Medida de confiançaAprendizado ativoAprendizado semi-supervisionado


O algoritmo TBLCorpus de Treino não etiquetado

Classificador Inicial

Corpus de Treino atual

Derivação e avaliação das regras

candidatas

Seleção da regra a ser aplicada

Aplicação da regra ao corpus de treino.

Corpus de Treino etiquetado corretamente

Templates de Regras

Seqüência de regras aprendidas.


Aplicação das regras aprendidas

Textonão etiquetado

Classificador Inicial

Texto com classif. inicial

Aplicação (em sequência) das

regras aprendidas

Sequência de regras aprendidas.

Texto etiquetado


Estimando probabilidades com TBL

ObjetivoDe

t <- Etiqueta y

Parat <- (Etiqueta y, P(Y|t))


Método propostoY={ A, B, C} (conj. etiquetas de classe)

Corpus de Treino: (20 exemplos)8 exemplos da classe A6 exemplos da classe B6 exemplos da classe C

Classes de Equivalência

E

Estimando as probabilidades1. P(A|R1) = 0 P(B|R1) = 1 P(C|R1) = 02. P(A|R1,R2) = 0 P(B|R1,R2) = .5 P(C|R1,R2) = .53. P(A|R1,R3) = 0 P(B|R1,R3) = 0 P(C|R1,R3) = 14. P(A|R2) = 0 P(B|R2) = .33 P(C|R2) = .675. P(A|A) = .78 P(B|A) = .11 P(C|A) = .11Estimar a distribuição de máxima verossimilhança em cada classe de

equivalência e E

ModeloClassif. Inicial: tag <= AR1: EC1 tag <= BR2: EC2 tag <= CR3: EC3 tag <= C

Yeyeey y )count(),count()|P(

Aplicando o modeloCls. Eq. Exemplos

modif.1. R1 4 –

{4B}2. R1, R2 2 – {1B,

1C}3. R1, R3 2 – {2C}4. R2 3 –

{1A, 2C}5. A 9 – {7A, 1B,

1C}

onde: count(e, y) = # de exemplos em e com etiqueta y count(e) = # de exemplos em e


Aplicando o modeloCls. Eq. Exemplos modificados1. R1 4 – {4B}2. R1, R2 2 – {1B, 1C}3. R1, R3 2 – {2C}4. R2 3 – {1A, 2C}5. A 9 – {7A, 1B, 1C}

Y={ A, B, C} (conj. etiquetas de classes)


ModeloClassif. Inicial: tag <= AR1: EC1 tag <= BR2: EC2 tag <= CR3: EC3 tag <= C

R1 AR2

R2 R3

*

Método proposto

38

22

9

94

2 2

3

20


Algoritmo Entrada

Conjunto de regras TBLCorpus de treino

ProcessamentoAplicar conjunto de regras – guardar, para cada

exemplo, a seqüência de regras que o modificouCriar classes de equivalênciaComputar a distribuição de probabilidades para

cada classe de equivalência Saída:

Modelo de probabilidades associado ao conjunto de regras TBL


Usando o modelo de probabilidades

ProcedimentoAplicar conjunto de regras TBL – guardar, para

cada amostra, a seqüência de regras que a modificou;

Para cada amostra, atribuir a distribuição de probabilidades associada a:seqüência de regras que a modificou; ouetiqueta de classe atribuída pelo classificador inicial


20

812

6

O método de Florian et. al (2000)

Y={ A, B, C} (conj. etiquetas de classe)


Modelo:Classif. Inicial: tag <= AR1: EC1 tag <= BR2: EC2 tag <= CR3: EC3 tag <= C

Aplicando o modelo:Regras Exemplos modificadosR1 4 – {4B}R1, R2 2 – {1B, 1C}R1, R3 2 – {2C}R2 3 – {1A, 2C}A 9 – {7A, 1B, 1C}

R1

R2 R2

A

Classes de equivalência

Estimando as probabilidades (máxima verossim.):P(A|R1) = 0 P(B|R1) = 1 P(C|R1) = 0P(A|R1,R2) = 0 P(B|R1,R2) = .5 P(C|R1,R2) = .5P(A|R1,R3) = 0 P(B|R1,R3) = 0 P(C|R1,R3) = 1P(A|R2) = 0 P(B|R2) = .33 P(C|R2) = .67P(A|A) = .78 P(B|A) = .11 P(C|A) = .11

9 3 R3 2

4 2


Particionando classes de equivalência

Classes de equivalência muito densas Formadas por exemplos não modificados por regras Prejudicam as estatísticas Ex.: base noun phrase identification

(I) -> 108.763 exemplos Solução:

Usar feature auxiliar para particionar Ex.: base noun phrase identification

(I, pos) = 20 classes de equivalência ('I', 'PRP'): [0.992, 'I'], [0.008, 'B'], [0.0, 'O']] ('I', 'FW'): [0.867, 'I'], [0.0, 'B'], [0.133, 'O']]


Calcular distribuição de prob. usando:

Suavização - Lidstone

YcYecyeey

y

)count(),count()|P(

onde: e = classe de equivalênciay = etiqueta de classecount(e, y) = # de exemplos em e com etiqueta ycount(e) = # de exemplos em eY = conjunto de etiquetas de classec = constante - número entre 1 e 0.


Suavização - LidstoneEstimando as probabilidades – sem suavização1. P(A|R1) = 0 P(B|R1) = 1 P(C|R1) = 02. P(A|R1,R2) = 0 P(B|R1,R2) = .5 P(C|R1,R2) = .53. P(A|R1,R3) = 0 P(B|R1,R3) = 0 P(C|R1,R3) = 14. P(A|R2) = 0 P(B|R2) = .33 P(C|R2) = .675. P(A|A) = .78 P(B|A) = .11 P(C|A) = .11

Cls. Eq. Exemplos modif.1. R1 4 – {4B}2. R1, R2 2 – {1B, 1C}3. R1, R3 2 – {2C}4. R2 3 – {1A, 2C}5. A 9 – {7A, 1B, 1C}

Estimando as probabilidades – Lidstone (c=1)1. P(A|R1) = .14 P(B|R1) = .72 P(C|R1) = .142. P(A|R1,R2) = .2 P(B|R1,R2) = .4 P(C|R1,R2) = .43. P(A|R1,R3) = .2 P(B|R1,R3) = .2 P(C|R1,R3) = .64. P(A|R2) = .17 P(B|R2) = .33 P(C|R2) = .55. P(A|A) = .67 P(B|A) = .165 P(C|A) = .165


R1 AR2

R2 R3

*3

22

9

94

2 2

3

8

Suavização - BackoffSuavizar uma estimativa mais específica

P(y|e1) com uma menos específica P(y|e2)Computar a mistura das duas

usando um coeficiente de mistura

)|()1()|()|(ˆ211 eyPeyPeyP

8

20

)'1|()1()2,1|()2,1|( RyPRRyPRRyP


Suavizar uma estimativa mais específica P1(y|e1) com uma seqüência de estimativas menos específicas P2(y|e2) , P3(y|e3), ..., Pk(y)

Computar uma combinação linear das estimativas, recursivamente:

Suavizar P(y|R1, R2)

)(*)|(*)|(

*)|(ˆ)1()'1|()'1|(

)'1|()1()2,1|()2,1|(

3

3222

2111

yPyPyP

yPRyPRyP

RyPRRyPRRyP

Suavização - Backoff

)|()1()|()|(ˆ)()|(

11

iiiiiii

kkk

eyPeyPeyP

yPeyP

R1 AR2

R2 R3

*3

22

9

94

2 2

3

8

8

20


Suavização - Backoff Como calcular i ? Collins (1999)

contrário caso0

0)(count se)div()count(

)count(

iii

i

ie

ecee

onde: c = parâmetro de ajuste (constante)div(ei) = |{ y| ei contém (x, y)}| (diversidade de etiquetas em ei)


Experimentos

English Text Chunking

English Base-Noun Phrase Identification


Curva de rejeição Entropia H da distribuição de probabilidades

associada ao token x

Aprendizado Ativo Média da entropia H dos tokens de uma

sentença S

Experimentos – Testes e

Métricas

)|(log)|())(( 21

xypxypxYH i

k

ii

S

i

iSYHS

Sf1

),|(1)(


Calibração das constantes de suavização Entropia cruzada condicional

Perplexidade

Experimentos – Testes e

Métricas

)|(log)|()()|( 2 xypxyqxqXYHXx Yy

c

)|(2 XYHcP

),(2 )|(log1

yx

xypX


English Text Chunking Problema

[NP He ] [VP reckons ] [NP the current account deficit ] [VP will narrow ] [PP to ] [NP only # 1.8 billion ] [PP in ] [NP September ]

onde:

NP = Noun Phrase Chunk; VP = Verb Phrase Chunk; PP = Prepositional Phrase Chunk

Corpora (CONLL 2000) Treino: 211.727 tokens; 8.936 sentenças Teste: 47.377 tokens; 2012 sentenças


English Text Chunking Calibração das constantes de suavização

20% do corpus de treino


English Text Chunking Curva de rejeição


Florian et. al (2000) Método Proposto

English Text Chunking Aprendizado Ativo


English Text Chunking

Perplexidade Entropia Cruzada Condicional

TBLconf 1.2952 0.3732

TBLconf + Lidstone 1.2724 0.3476

TBLconf + Backoff 1.2699 0.3447

fnTBL 1.2976 0.3759


English Base-Noun Phrase

Identification Problema

[He] reckons [the current account deficit] will narrow to [only # 1.8 billion] in [September]

Corpora (fnTBL, 2001) Treino: 211.727 tokens; 8.936 sentenças Teste: 47.377 tokens; 2012 sentenças



Identification Calibração das constantes de suavização

20% do corpus de treino



Identification Curva de rejeição



Identification Aprendizado Ativo



IdentificationPerplexidade Entropia Cruzada

CondicionalTBLconf 1.1298 0.1761

TBLconf + Lidstone 1.1229 0.1672

TBLconf + Backoff 1.1237 0.1683

fnTBL 1.1757 0.2335


Conclusões Método proposto mostrou-se robusto Utilização de suavização é fundamental Probabilidades geradas podem servir como

uma medida de confiança Em todos os testes realizados o método

proposto – com suavização – mostrou-se mais eficaz do que o método de Florian et. al (2000)

Documents

Classificação Probabilística com TBL Cícero Nogueira dos Santos Pontifícia Universidade Católica do Rio de Janeiro – PUC-Rio Departamento de Informática