Inferência Transdutiva para Classificação
de Textos usando Support Vector Machines
Thorsten Joachins
Apresentação: Allyson A. Brito
[email protected]
Agenda
Abstract
 Introdução
 Classificação de Texto
 SVM Transdutivas (TSVMs)
 TSVM – Classificação de Textos
 O Algoritmo
 Experimentos
 Considerações Finais

Abstract




Este paper introduz TSVM para classificação
de textos
Apresenta analises mostrando que TSVM são
apropriadas para classificação de textos
As descobertas teóricas são complementadas
com experimentos práticos
Um algoritmo para treinamento de TSVM é
proposto
Classificação de Textos

Objetivo principal: Classificar conjuntos de documentos
em um número fixo de categorias semânticas

Documentos podem pertencer a uma ou mais categorias
ou a nenhuma

Problema de Aprendizado Supervisionado

É necessário transformar o texto para uma
representação apropriada (pré-processamento) para o
algoritmo de aprendizado.
Classificação de Textos
Pré-processamento utilizando técnicas de Recuperação de
Informação como: stemming, IDF, etc..


Inverse Document Frequence
 n 

IDF ( wi )  log 
 DF ( wi ) 


wi é uma palavra distinta
n é o número total de
documentos
DF é a freqüência da
palavra no documento
IDF assinala pesos maiores a “radicais” que são infreqüentes em
toda a coleção e pesos menores aos termos freqüentes

Classificação de Textos
Representando texto como um vetor de atributos
Classificação de Textos
Características da classificação de Textos




Espaço de entrada com alta dimensão
(10.000 atributos)
Vetores de atributos são esparsos
Cada atributo é importante, já que a maioria
das palavras são
Cada documento tem um vetor de atributos,
indexado pelos “radicais” das palavras
SVM Transdutivos

SVM Indutivos

Vetores são separados em duas regiões: H1 e H2

A margem é maximizada para que se tenha um erro
mínimo de separação

Pontos de Dados que estão sobre as margens são
chamados de vetores de suporte
SVM Transdutivos

Inferência Indutiva
Generalizar para qualquer conjunto
de teste futuro
 Grande esforço computacional para
descoberta da função


Inferência Transdutiva

Predizer as classes para um conjunto
de testes específico
SVM Transdutivos - TSVM

TSVM
SVMS são utilizadas para aprender
uma decisão de contorno entre duas
classes para predizer rótulos (labels)
para futuros conjuntos de testes
 TSVMs tentam minimizar o número de
predições erradas para o conjunto de
teste especificamente

SVM Transdutivos - TSVM

Conjunto de treinamento (+/-)

Conjunto de teste ( )
.
TSVM para Classificação de
Textos



TSVMs herdam características de SVM que
funcionam bem
TSVMs exploram a co-ocorrencia de
padrões no texto
Exemplo (alta vista) – 2001




Pepper, salt: 181.827
Pepper, physics: 19.425
Salt: 1.9 milhões
Physics: 4.2 milhões
TSVM para Classificação de
Textos
Exemplo:
•D1 e D6 são vetores de atributos de treinamento
•D2 a D5 são vetores de teste
•D1, D2, D3 são classificados como A
•D4,D5,D6 como B
•Isto é possível pelo fato de que os vetores D2 e D3 compartilham
uma palavra comum (atom) como D4 e D5
O Algoritmo

Entradas:





exemplos de treinamento rotulados (x1,
y1),...,(xn,yn)
Exemplos de testes sem rótulo x1, x2,...,xn
C,C* de OP(2) no texto
Num+: número prévio de exemplos de teste
positivos
Saída:

Rótulos preditos dos exemplos de teste y1,
y2,..., yn
O Algoritmo

Parâmetros de usuário
C e C* indicam o tamanho da margem
 Num+: permite a troca de recall
versus precisão

• Recall: proporção de itens atualmente
colocados na categoria
• Precisão: proporção de itens colocados
na categoria e que realmente pertencem
a ela
O Algoritmo
O Algoritmo



Inicialmente rotula os dados de testes
baseado num indutivo SVM
Configura os valores de C* e C*+
Loop Externo – Loop1


Incrementa os fatores de custo pelo valor
definido pelo usuário em C*
Loop Interno – Loop2


Localiza 2 exemplos de teste para os quais
mudando seus rótulos conduz a uma
diminuição na função objetivo atual OP(2)
Se estes dois exemplos existirem, troque-os
O Algoritmo

Loop Interno – Loop2
Objetiva minimizar a função objetivo
OP(2)
 O Algoritmo irá trocar 2 exemplos que
adiante minimizarão OP(S), caso eles
existam
 Os mesmos exemplos podem ser
trocados repetidamente

Conjunto de Dados

Reuters-21578




WebKB




Notícias coletadas pela Reuters em ’87
75% para treino (aprox 9K) e 25% (aprox 3K) para teste
O documento pode estar em uma ou mais das 10 classes
Conjunto de páginas WEB
4K exemplos para treino e outras para teste
Pode estar em 1 das 4 classes (course, faculty, project,
student)
Ohsumed corpus



Documentos médicos agrupados em ’91
10K para treino e 10K para teste
Pode estar em 1 das 5 classes (pathology, neoplasms, etc)
Métricas de Desempenho

Recall e Precisão



Recal: tp(tp+fn)
Precisão: tp/(tp+fp)
Precisão / Recal (P/R) – Ponto de empate



Medida padrão para classificação de textos
Definida como o valor para o qual a precisão
e o recall são iguais
Numero de falso positivos igual ao numero
de falso negativos
Experimentos - Reuters
•17 p/ treinamento e 3,299 exemplos de teste
•TSVM obteve melhor performance em todas as classes
•TSVMs são melhores para pequenos conjuntos de
treinamento, mas também se saem bem para conjuntos
grandes
Experimentos - Reuters
Experimentos - Reuters
Experimentos - WebKB
• 9 exemplos de treino e aprox. 4.000 de testes
•As paginas da classe course não possuem informação de tópico
•Project é a menor classe (1/9), e as páginas possuem informação
de tópico.
Experimentos - WebKB
Classe Course
Experimentos - WebKB
Classe Project
Experimentos - WebKB Ohsumed
• 120 exemplos de treino e 10.000 de testes
•TSVM obteve melhor desempenho em todas as classes
Considerações Finais

TSVM combina ferramentas
poderosas
Usa o conhecimento a prior do
conjunto de testes
 Explora as propriedades de coocorrencia, típicas de textos
 Usa SVM para serpação marginal


TSVM funcionam bem para
classificação de textos
Considerações Finais

Questões Abertas
Melhor forma de representar
documentos textuais
 Pesquisa sobre melhores algoritmos
de treinamento
 Estender classificadores transdutivos
para serem indutivos

Dúvidas !?!?
Obrigado!!
[email protected]