Aprendizagem Estatística de Dados
Francisco Carvalho
Avaliação
dos Classificadores
• Existem poucos estudos analíticos sobre o
comportamento de algoritmos de
aprendizagem.
• A análise de classificadores é
fundamentalmente experimental.
• Dimensões de análise:
Taxa de erro
 Complexidade dos modelos
 Tempo de aprendizagem
…

Avaliação
de Algoritmos de Classificação
• Dois Problemas distintos:
Dados um algoritmo e um conjunto de dados:
¤ Como estimar a taxa de erro do algoritmo nesse
problema?
 Dados dois algoritmos e um conjunto de dados:
¤ A capacidade de generalização dos algoritmos é
igual?

Avaliação
• Qual o desempenho do modelo aprendido?
• Erro no conjunto de treinamento não é um bom
indicador em relação ao que vai ser observado no
futuro
• Solução simples quando os dados são abundantes

dividir os dados em treinamento e teste
• Porém: dados (com rótulo) usualmente são raros
• Ex.: dados sobre falhas em sistemas elétricos nos últimos 15 anos
Avaliação
• Confiabilidade estatística nas diferenças de
performance estimadas
• Escolha de medidas de desempenho
Número de classificações corretas
 Erro em previsões numéricas
 etc

• Custo atribuído a deferentes tipos de erro

Muitas aplicações práticas envolvem custos
Treinamento
e teste
• Medida natural de desempenho para problemas
de classificação: taxa de erro
Sucesso: a classe da instancia é prevista corretamente
 Erro: classe da instancia é prevista incorretamente
 Taxa de erro: proporção dos erros em relação ao
conjunto de exemplos

• Erro de re-substituição: erro calculado a partir do
conjunto de treinamento
• Erro de re-substituição é otimista!
Treinamento
e teste
• Conjunto de Teste: conjunto de exemplos
independentes que não tiveram nenhum papel na
construção do classificador

Suposição: os conjuntos de treinamento e teste são
amostras representativas do problema em questão
• Dados de teste e de treinamento podem ser de
natureza diferente

Exemplo: classificadores construídos usando-se
dados de clientes de duas cidades diferentes A e B
¤ Para estimar o desempenho do classificador da cidade A
em uma nova cidade, teste-o com os dados de B
Ajuste
de parâmetro
• É importante que os dados de teste não sejam
usados de nenhuma maneira para construir o
classificador
• Alguns algoritmos de aprendizagem operam em
dois estágios
Estágio 1: construção da estrutura básica
 Estágio 2: otimização do ajuste dos parâmetros

• Procedimento correto: usar 3 conjuntos:
treinamento, validação e teste

Validação: usado para otimizar os parâmetros
Usar
ao máximo os dados
• Uma vez completada a avaliação, todos os dados
podem ser usados para construir o classificador
final
• Geralmente, quanto maior o conjunto de
treinamento melhor o classificador
• Quando maior o conjunto de teste mais exata a
estimativa do erro
• Holdout: divisão dos dados originais em
treinamento e teste

Dilema: idealmente deseja-se que ambos, o
treinamento e o teste, sejam o maior possível
Previsão
de desempenho
• Suponha que a taxa de erro estimada é 25%. Quão
próxima isso está da verdadeira taxa de erro?

Depende da quantidade de dados de teste
• Classificar pode ser assimilado ao lançamento de uma
moeda viciada

Cara, sucesso; coroa, erro
• Em estatística, uma sucessão de eventos independentes
como esse é chamado de processo de Bernoulli

A teoria estatística permite a construção de intervalos de
confiança com uma certa probabilidade de conter a verdadeira
taxa de erro
Intervalos
de confiança
• Pode-se dizer: com um certo nível de confiança,
um certo intervalo especificado pode conter p
• Exemplo: S=750 sucessos em N=1000 tentativas
Taxa de sucesso estimada: 75%
 Quão próximo é isso da verdadeira taxa de sucesso?

¤ Resposta: com 95% de confiança [73.3;76.8] contém p
• Outro exemplo: S=75 e N=100
Taxa de sucesso estimada: 75%
 com 95% de confiança [70;81] contém p

Média
e Variância
• S: número de sucessos. V.a. de tipo Binomial
• Média e variância para um v.a de tipo Binomial:
p, Np(1-p)
• Taxa de sucesso f = S / N. V.a de tipo binomial
• Média e variância para f: p, p(1-p)/N
• Para N grande uma v.a. de tipo binomial pode ser
aproximada por uma normal
Resultados
da Estatística
• V. a. de tipo t-Student
X 
tvn1 
s n
• Intervalo de confiança par  ao nivel de
confiança de (1-)
P(t / 2,  t  t / 2, )  1  
[ X  t / 2, ( s / n ); X  t / 2, ]
Resultados
da Estatística
• Grandes amostras
X 
X 
t vn 1 
 Z  N(0,1) 
s n
s
n
• Intervalo de confiança par  ao nível de
confiança de (1-)
P ( z / 2  Z  z / 2 )  1  
[ X  z  / 2 (s / n ); X  z  / 2 (s / n )]
• A v.a f tem que ser reduzida para ter média 0 e
variância 1
Transformação
para f
• Intervalo de confiança par p ao nível de
confiança de (1-)
f (1  f ) 

f  N  p,

N


[ f  z / 2
P( z / 2 
f (1  f )
; f  z / 2
N
f p
 z / 2 )  1  
f (1  f ) / N
f (1  f )
]
N
Estimação
Holdout
• O que fazer se os dados são limitados
• O método holdout reserva uma certa quantidade
para teste e o restante para a aprendizagem

usalmente, 1/3 para teste e 2/3 para treinamento
• Problema: a amostra pode não ser representativa

exemplo: uma classe pode estar ausente no conjunto
de teste
• Amostragem estratificada: as classes são
representadas com aproximadamente a mesma
proporção tanto no teste como no treinamento
Holdout
repetido
• Estimação holdout pode ser realizada com mais
confiança repetindo-se o processo com diferentes
sub-amostras
Em cada iteração, uma certa proporção é selecionada
aleatoriamente para treino, com ou sem estratificação
 uma taxa de erro global é calculada pela média das
taxas de erro nas iterações

• Esse processo é chamado holdout repetido
• Problema: os diferentes conjuntos de teste não
são mutuamente excludentes
Validação
cruzada
• Validação cruzada evita conjuntos de teste com
interseção não vazia
os dados são divididos em k conjuntos de mesmo
cardinal
 cada subconjunto é usado como teste e o restante
como treino

• Isso é chamado de validação cruzada k-fold
• Os subconjuntos podem ser estratificados antes
de realizar a validação cruzada
• A taxa de erro global é a média das taxas de erro
calculadas em cada etapa
Validação
cruzada
• Método usual: validação cruzada estratificada
10-fold
• Porque? Evidencias experimentais
• A estratificação reduz a variância da estimativa
• Melhor ainda: validação cruzada estratificada
repetida

validação cruzada 10-fold repetida 10 vezes
Validação
cruzada leave-one-out
• É uma forma particular de validação cruzada
O número de folds é o número de exemplos
 o classificador é construído n vezes

•
•
•
•
usa os dados completamente no treino
não envolve sub-amostras aleatórias
computacionalmente custoso
a estratificação não é possível
Bootstrap
• Validação cruzada usa amostragem sem repetição
• Bootstrap é um método de estimação que usa
amostragem com reposição para formar o conjunto de
treinamento



Retira-se uma amostra aleatória de tamanho n de um conjunto
de n exemplos com reposição
Essa amostra é usada para o treinamento
os exemplos dos dados originais que não estão no conjunto de
treino são usados como teste
• É a melhor maneira quando o conjunto de dados é
pequeno
Comparação
de Classificadores
• Situação freqüente: deseja-se saber entre dois
classificadores, qual o de melhor desempenho
• Atenção: isso depende do domínio
• Maneira óbvia: comparar as estimativas obtidas
através de VC 10-fold (repetida ou não)
• Problema: variância das estimativas
Testes
de hipóteses
• Um teste de hipótese é um guia em relação a
confiança com que assumimos que realmente
existe uma diferença de desempenho
• Hipótese nula: não há diferença
• Hipótese alternativa: há diferença
• Um teste mede a evidencia que existe em favor
da rejeição da hipótese nula
Qual
o melhor algoritmo para um problema ?
• Dados dois algoritmos e um conjunto de dados, que
algoritmo utilizar?

Que algoritmo tem menor erro na população ?
• Estimar o erro dos dois algoritmos


Usando uma estratégia de amostragem
Para cada algoritmo é estimado um erro
• São os dois erros estatisticamente diferentes ?
• Exemplo

Usando 10-validação cruzada:
Teste
de Hipóteses
• Hipótese nula:

Ambos os algoritmos têm a mesma performance
• Como verificar a hipótese nula ?

“paired tests” são mais apropriados.
¤ Eliminar a variabilidade devida a fatores externos
¤ Ambos os algoritmos devem:
 Aprender nos mesmos
conjuntos de treinamento
 Os modelos devem ser avaliados
nos mesmos conjuntos de teste

Teste para 2 caudas
¤ X >> Y ou Y >> X
Student
paired t-test
• Para decidir se duas médias são estatisticamente
diferentes:



Calcular di = xi – yi
Calcular
t
Escolher um nível de confiança
¤ Usual 5% ou 1%
¤ Usar a tabela da distribuição de t para calculo de z


d
d2 / k
k-1 graus de liberdade
Se t > z ou t < -z então as médias são significativamente
diferentes
¤ Para o nível de confiança escolhido.
Exemplo
Amostras
independentes
• Em um esquema foi usado uma VC k-fold e no outro
uma VC j-fold
• Deve-se usar um teste-t para amostras não pareadas com
min(k,j)-1 graus de liberdade
• a estatística agora é
t
mx  m y
2
s
s
 y
k
j
2
x
Critica
• A utilização de t-testes não é pacífica.

Elevada probabilidade de sugerir diferenças onde elas não
existem (erro de Tipo I)
• Problemas:


Na validação cruzada:
¤ Os conjuntos de treinamento não são independentes.
Assume a distribuição normal
• Alguns autores sugerem:

Wilcoxon matched-pairs signed-ranks test
Contabilizando os Custos
 Na
prática, diferentes tipos de erros de
classificação geralmente incorrem em diferentes
custos
 Exemplos:
•
•
•
•
Decisões de empréstimo
Detecção de vazamento de óleo
Diagnóstico de falha
Cartas promocionais

enviar carta p/ família q ñ responderá x ñ enviar carta p/
família q responderá
Levar em conta Custos

A matriz “confusão”:
Classe
Atual
Yes
No

Predicted class
Yes
No
True
False
positive
negative
False
True
positive
negative
Há muitos outros tipos de custos
• Custos de coleta de dados para treinamento
Sensibilidade (abrangência):
Especificidade:
TP
TP  FN
TN
TN  FP
Valor de Predição Positivo (precisão):
Valor de Predição Negativo:
Acerto:
TP  TN
TP  TN  FP  FN
Erro:
FP  FN
TP  TN  FP  FN
TP
TP  FP
TN
TN  FN
F-Measure
2TP
F

1
1
2TP  FP  FN

S VPP
F-Measure (bis)
2
F
2
1
1

E VPN
2TN

2TN  FP  FN
O VPP é diretamente influenciado pela especificidade e
pouco influenciado pela sensibilidade
O VPN é diretamente influenciado pela sensibilidade e
pouco influenciado pela especificidade
Aprendizado Sensível ao Custo
A
maioria dos esquemas de aprendizado não
realizam aprendizado sensível ao custo
• Eles geram o mesmo classificador não importando qual
o custo associado a diferentes classes
• Exemplo: aprendizado de árvore de decisão padrão
 Métodos
custo:
simples para aprendizado sensível ao
• Replicação de instâncias de acordo com os custos
• Utilização de pesos para instâncias de acordo com os
custos
Avaliando Previsões Numéricas
Algumas estratégias: conjunto de teste independente,
cross-validation, testes de significância, etc.
 Diferença: medidas de erro
 Valores atuais: a1, a2, ..., an
 Valores previstos: p1, p2, ..., pn
 Medida mais popular: erro quadrático médio(meansquared error)
 p1  a1 2     pn  an 2
n

• manipulação matemática fácil
Outras Medidas

Raiz do erro quadrático médio:
 p1  a1 2     pn  an 2
n


O erro absoluto médio é menos sensível a outliers que o
erro médio quadrático:
p1  a1    pn  an
n
Às vezes valores de erros relativos são mais apropriados
que valores absolutos
• 10% corresponde a um erro de 50 quando prevendo 500
• 10% corresponde a um erro de 0,2 quando prevendo 2
Aprimoramento da Média


As vezes queremos saber o quanto o esquema é
aprimorado simplesmente prevendo a média
Erro quadrático relativo é (ā é a média):
 p1  a1 2     pn  an 2
a  a1 2    a  an 2

Erro absoluto relativo é:
p1  a1    pn  an
a  a1    a  an
O Coeficiente de Correlação

Mede a correlação estatística entre os valores previstos
e os valores atuais
S PA
SP S A
S PA 
 ( p  p)(a  a )
i
i
i
n 1
SP 
(p
i
 p)2
i
n 1
SA 

Escala independente, entre –1 e +1

Boa performance leva a grandes valores
 (a  a )
i
i
n 1
2
Qual a melhor medida?
Melhor verificar todas elas
 Geralmente não importa
 Exemplo:

Raiz do erro quadrático médio
Erro absoluto médio
Raiz do erro quadrático relativo
Erro absoluto relativo
Coeficiente de correlação
A
67,8
41,3
42,2%
43,1%
0,88
B
91,7
38,5
57,2%
40,1%
0,88
C
63,3
33,4
39,4%
34,8%
0,89
D
57,4
29,2
35,8%
30,4%
0,91
Decomposição
do Erro
• O erro esperado de um classificador pode ser
decomposto em
2
2
2
E    x  viés x  var iancia x 
x



Ruído no conjunto de dados
Viés (Bias)
¤ Mede os erros sistemáticos
¤ Estimativa da capacidade de adaptação da linguagem de
representação utilizada pelo algoritmo ao problema
Variância
¤ Mede a variabilidade das predições
¤ Estimativa da dependência do modelo gerado ao conjunto
de treino
O
Compromisso Bias-Variance
• Aumentando o número de graus de liberdade de um
modelo:


Diminuição da componente do “Bias”
Aumento da variância.
• Minimizar o erro esperado requer um compromisso
entre as duas componentes
Decomposição
em “Bias-Variance”
• Funções Discriminantes


Variância reduzida
Viés elevado
• Arvores de decisão


Variância elevada
Bias reduzido
Sumario
• Avaliação de classificadores
Como estimar o erro do classificador num conjunto
de dados?
 Qual o melhor algoritmo para um problema?

• Amostragem
Validação cruzada
 Amostragem com reposição

• Teste de Hipóteses
• Decomposição do erro em viés e variância