07/06/2017

1

Aprendizado de Máquina

Um pouco de teoria

Formalização (Classificação Binária)

Entrada • X: Espaço de exemplos • D: Distribuição de probabilidade sobre os

exemplos de X • S X: Conjunto de treino obtido sorteando

elementos de X de acordo com a distribuição D • c*: função (conceito alvo) que mapeia cada

ponto xX em {0,1}. – O Valor de c* só é conhecido para os pontos em S – c* pode ser pensado como o conjunto de pontos

positivos.

Formalização (Classificação Binária)

Objetivo

• Obter uma função h: X {0,1} que minimize o ‘true error’

errD(h)= PrD [ h(x) <> c*(x) ]

Erro de Treinamento

• Fração dos pontos em S que a função h erra errS(h)= | x S : h(x) <> c*(x) | / |S|

• É fácil ter um erro treinamento igual a 0, basta construir uma função h tal que h(x)=c(x) para todo x S.

• O desafio é conseguir garantir que o true error seja pequeno

Conceitos Importantes

07/06/2017

2

Overfitting

• True error bem maio que erro no conjunto de treino

– baixo poder de generalização

Conceitos Importantes

Classe de hipóteses (conceitos ou funções)

• Para lidar com overfitting e tornar o problema de learning computacionalmente tratável restringimos as possibilidades da função h para uma classe de funções H

• Exemplos de classes: funções booleanas, separadores linerares

Conceitos Importantes

Teorema 1. Seja H uma classe de hipóteses. Além disso, seja >0 e >0. Se o conjunto S de tamanho

n >( ln |H| + ln(1/ ) ) /

é obtido a partir da distribuição de probabilidade D, então com probabilidade ≥ 1- , toda hipótese h em H tal que errD(h) ≥ satisfaz errS(h)>0.

De forma, equivalente com probabilidade maior ou igual a 1- , toda hipótese h em H com errS(h)=0 tem true erro <

Sample Complexity

Prova.

• Seja h hipótese tal que errD(h) ≥ . Então a probabilidade dela ter erro no conjunto S de 0 é (1- )n .

• Portanto, a probabilidade de existir uma hipótese h em H com errD(h) ≥ e errS(h)=0 é limitada por |H| (1- )n (union bound)

• Substituindo n por seu limite inferior concluímos que |H| (1- )n <

Sample Complexity

07/06/2017

3

Em palavras…

• Se o conjunto de treino é ‘grande’ o suficiente é muito improvável que uma hipótese com erro 0 no treino tenha um resultado ruim (erro > ) no conjunto todo.

• O resultado apresesentado é conhecido na literatura como um PAC bound

Sample Complexity

Em palavras …

• O ‘grande’ está relacionado com o número de hipóteses possíveis (ln H) já que se existe um número grande de hipóteses, por um efeito do acaso uma pode acabar indo mal no conjunto todo `(erro > ) e muito bem no treino (erro= 0)

• O ‘grande’ está relacionado com o erro (1/ ). Se o erro é pequeno, é razoável ter uma hipótese que erre mas que no conjunto todo mas não erre no treino devido a variância.

Sample Complexity

Teorema 2. Seja H uma classe de hipóteses. Além disso, seja >0 e >0. Se o conjunto S tem tamanho

n >[ ln |H| + ln(1/) ] / 22

é obtido a partir da distribuição D, então com probabilidade ≥ 1- , toda hipótese h em H satisfaz | errD(h) - errS(h) | ≤ .

Sample Complexity

Em palavras…

• Generalização do primeiro teorema que leva em conta a diferença entre o erro da hipótese no treino e no conjunto todo

Sample Complexity

07/06/2017

4

Classificador de email • Escolhermos um conjunto U com d palavras

chaves (cialis, viagra, loan,…,) • Classifcamos um email como spam se pelo menos

uma das palavras do subconjunto W de U está presente. – Atributo x(i)=1 se palavra i está presente e x(i)=0, caso

contrário. – O conjunto W deve ser aprendido

• H: classe das hipóteses {W | W U} – H tem 2d hipóteses

Sample Complexity

Classificador de email Segue do Teorema 1 que se encontrarmos uma hipótese com erro 0 em um conjunto de treino de tamanho maior ou igual a (d ln(2) + ln(1/ )) / garantimos uma acurácia de 1- , com prob (1- ) • d=50, =0.05 =0.01 precisamos de conjunto de

treino de tamanho 800 • d=1000, =0.05 =0.01, precisamos de conjunto de

treino de tamanho 14000

Sample Complexity

Learning Disjunctions

H: classe de funções expressas como disjunção de variáveis positivas

Exemplos:

h1: x(1) OR x(3) OR x(4)

h2: x(1) OR x(2)

Classificador que classifica de forma positiva se uma das variáveis está presente no conjunto

Sample Complexity

‘Devemos priorizar explicações (modelos) mais simples’

Occam Razor

07/06/2017

5

Conexão com o PAC bound

• Se temos duas hipóteses com o mesmo erro no conjunto de treino devemos escolher a mais simples (pertence a uma classe com menos de hipóteses) pois teremos uma garantia teórica melhor

– Termo ln (H) nos Teoremas 1 e 2

Occam Razor

Conexão com o PAC bound

• O método M1 constroi a melhor árvore de decisão dentre aquelas de altura altura 3

• O método M2 constroi a melhor árvore de decisão dentre aquelas de altura 5

Assuma que os dois métodos obtiveram árvores de decisão com erro de treino 0.

Qual árvore devemos escolher?

Occam Razor

• Para árvore de M1 conseguimos garantir um bound melhor já que M1 é uma classe com menos hipóteses (árvores) que enquanto M2

• Isso não quer dizer que M1 é necessariamente melhor que M2

Occam Razor

Regularização

• Forma de penalizar hipóteses mais complexas

• Minimizamos o erro de treinamento mais uma penalidade

07/06/2017

6

Regularização

Corolário. Seja L uma linguagem utilizada para representar hipóteses. Seja S um conjunto de treino obtido a partir da distribuição D. Então com probabilidade ≥ 1- , toda hipótese h satisfaz

onde size(h) é o número de bits necessários para representar a hipótese na linguagem L

Regularização

• A regularização abaixo é natural

Online Learning

• Uma sequência de exemplos x1,…,xt chega ao longo do tempo

• Devemos classificar cada exemplo no momento que ele chega.

• Pagamos um custo ci pela classificação de xi e descobrimos então a classe real do exemplo

Online Learning

Aplicação

• Classificação de email como importante ou não importante

• Usuário informa se o algoritmo está correto ou não

• Não é razoável assumir independência neste caso já que muitos emails são resposta de outros ou contruídos a partir de outros

07/06/2017

7

Online Learning

Halving Algorithm

1. O algoritmo começa com todas as hipóteses da classe H

2. Ao chegar um novo exemplo x, o algoritmo classifica x a partir de uma votação com base nas hipóteses consistentes.

3. Se um erro ocorre, o algoritmo descarta as hipóteses que erraram

Online Learning

Halving Algorithm

• Se ocorre um erro o novo conjunto de hipóteses consistentes tem no máximo metade do tamanho do conjunto anterior

• Portanto, se existe uma hipótese com erro 0, o método erra no máximo log |H| vezes

• Algoritmo é muito caro computacionalmente

– Interessante do ponto de vista teórico.

Online Learning

Online Perceptron

• Algoritmo simples e eficiente para encontrar um separador linear em Rd

• A premissa é a existência de um separador linear w* tal que:

(i) para todo exemplo positivo x, w*x>=1

(ii) para todo negativo , w*x ≤ -1

Online Learning

Online Perceptron

• Todo ponto xi está a distância de pelo menos 1/|w*| do hiperplano w*x=0.

• A distância de xi ao hiperplano é a projeção de xi na direção w* que é dada por

| w*xi /|w*| | >=1

• Essa distância 1/|w*| é a margem do separador

07/06/2017

8

Online Learning

Online Perceptron

w=0

Para t=1,2,3,…

1. Dado um exemplo xt prediz sgn(xtTw)

2. Se a predição não está correta

(a) Se xt é positivo, w w + xt

(b) Se xt é negativo, w w - xt

Online Learning

Teorema (Perceptron). Para qualquer sequência de exemplos x1 x2 ,…,xt se existe um vetor w* tal que:

(i) w*x ≥1 para os exemplos positivos

(ii) w*x ≤ -1 para os exemplos negativos,

então o Perceptron comete no máximo

|w*|2 R2 erros

onde R=maxt | xt |

Online Learning

Prova

• Investigamos a evolução de wTw* e |w|2

• Ao cometer um erro, wTw* aumenta de pelo menos uma unidade:

– Se xt é positivo:

(w+xt ) T w* = wT w* +xt

T w* ≥ wT w*+1

– Se xt é negativo (similar)

Online Learning

Prova

• Ao cometer um erro, |w|2 aumenta de no máximo R2

– xt é positivo:

|(w+xt ) |2 -|w|2 = 2 xt w + | xt |

2 ≤ R 2

onde a desigualdade segue do fato que xtw ≤ 0 se erramos um exemplo positivo

– xt é negativo (similar)

07/06/2017

9

Online Learning

Prova

1. Se comentemos M erros:

– |w2| aumenta de no máximo MR2 unidades

– wTw* aumenta pelo menos M unidades

2. Temos também wTw* / |w*|2 ≤ |w|

– projeção de w na direção w* é menor que w,

3. Juntando (1) e (2) estabelecemos o resultado

Online Learning

Consequência

• Se a margem é grande, w* é pequeno e, portanto, cometemos poucos erros

Observação

• O resultado é invariante a escala porque se muitiplicarmos os exemplo por K podemos multiplicar w* por 1/K

Online Learning

Perceptron (dados não linearmente separáveis)

• Assumimos que existe um separador linear w*

• O que acontece quando não existe w*?

Online Learning

Hinge Loss

• O hinge-loss de w* em um exemplo positivo xt é max{0,1- w* xt}

• O hinge-loss de w* em um exemplo negativo xt é max{0,1+ w* xt}

• Defina LHinge (w*,S) como a soma dos hinge-loss dos exemplos de um conjunto S

07/06/2017

10

Online Learning

Teorema. Para qualquer sequência de exemplos x1 x2 ,…,xt o Perceptron comete no máximo

(|w*|2R2 + 2LHinge) erros

onde R=maxt | xt |

Classes não linearmente separáveis

E se o hinge loss for muito alto?

O que acontece com a fronteira abaixo?

• Criamos novas features x1x2, x12

, x22 associadas

ao ponto x=(x1,x2)

• Representamos x por x’= (x1, x2, x12

, x1x2,x22 )

• Logo, brancos e pretos são separados pelo hiperplano w*x≤4, onde w*=(0,0,1,0,1).

Classes não linearmente separáveis

• Classes que não são separáveis em dimensão mais baixa podem separadas linearmente quando introduzimos novas features

• Quais features devem ser incluidas?

• Como evitar um custo computacional muito alto? – Para mapear um ponto (x1,…, xd) em todos os

produtos com grau no máximo k precisamos de um espaço de dimensão dk

Classes não linearmente separáveis

07/06/2017

11

Kernel Trick

• Suponha a existência de uma função

K(x,y): Rd x Rd ->R

e uma função

:Rd-> RN

com K(x,y) = (x) (y)

• Produto interno (x) (y) pode ser calculado usando a função K. Bem mais eficiente se N>>d

• K com essas propriedas é chamada de Kernel

• K(x,y) = (1+xy)2 corresponde a (x) = (1, 2 x1 , 2 x2, x1

2 , 2 x1 x2 , x22)

(y) = (1, 2 y1 , 2 y2, y12 , 2 y1 y2 , y2

2)

• Em geral, K(x,y) = (1+xy)k corresponde a (x)(y), onde :Rd-> RN , com N dk

• Complexidade de calcular o produto interno é

reduzida de O(dk) para O(d+log k)

Kernel Trick

• Seja w*=(-4,0,0,1,0,1). O hiperplano w*(x)=0 no espaço aumentado, corresponde ao círculo x1

2 + x22=4 no espaço original

• Brancos e pretos são linearmente separáveis no espaço aumentado

Kernel Trick

Perceptron -Kernelization

Online Perceptron (espaço aumentado)

w=0

For t=1,2,3,…

1. Given an example xt predict sgn( (xtT)w )

2. If the prediction is not correct

(a) If xt is positive, w w + (xt)

(b) If xt is negative, w w - (xt)

07/06/2017

12

1. Devemos computar w=w+ (xi) e sgn(w (x))

2. Em vez de calcular explicitamente w+ (xi) guardamos apenas os exemplos que somamos e os que subtraímos

3. Para calcular sgn(w(x)) utilizamos o kernel K

Perceptron -Kernelization

Exemplo

• Se cometemos os seguintes erros na classificação:

x1=positivo x3=negativo e x6=positivo,

então

w=(x1)- (x3)+(x6)

• Para classificar x7 temos que computar

((x1)-(x3)+(x6))(x7) =K(x1,x7)-K(x3,x7)+K(x6,x7)

Percerpton’s Kernelization

Obtendo Kernels …

Teorema. Se K1 e K2 são kernels então

1. c K1 é um kernel

2. K1 + K2 é um kernel

3. K1 x K2 é um kernel

Kernels

Aplicação. (1+xy)k é um kernel já que:

• (1+xy) é um kernel correspondente a (x)= (1,x) e

• (1+xy)k-1 é um kernel por hipótese de indução

Kernel gaussiano

K(x,x’)=e-c (|x-x’||x-x’| )

Kernels

07/06/2017

13

SVM

• Which of the linear separators is optimal?

dk

SVM

• Examples closest to the hyperplane are support vectors.

• Margin ρ of the separator is the distance between support vectors.

r

ρ

SVM

• Dados os exemplos (x1,…,xn), O SVM encontra o separador w que minimize soma ponderada do inverso da margem com erros de classificação

• c é usado para priorizar a importância da margem

SVM

• Admite kernelization

• Boas propriedades teóricas

• Existem implementações eficientes para encontrar separador (SVMLIB)

07/06/2017

14

Boosting

Definição. Um -weak learner é um algoritmo A com a seguinte propriedade:

dado um conjunto de n exemplos, seus rótulos e um peso w(i) associado a cada exemplo x(i), A soma dos pesos dos exemplos classificados corretamente por A é maior ou igual a

+(w(1)+…+w(n))/2

• É uma classificador ligeiramente melhor que o aleatório

Boosting

Boosting

Funcionamento

• Em cada iteração exemplos com classificação errada tem seus pesos aumentados

Boosting

Teorema. Seja A um -weak learner para o conjunto S. Se t0 Omega(1/ 2 log n), então MAJ(h1,…,ht0) tem erro de treino 0.

Prova

• M: número de exemplos classificados de forma incorreta no final

• weight(t): soma dos pesos no final da iteração t

07/06/2017

15

Boosting

Teorema. Seja A um -weak learner para o conjunto S. Se t0 Omega(1/ 2 log n), então MAJ(h1,…,ht0) tem erro de treino 0.

Prova

• Como cada um dos M exemplos é classificado errado por pelo menos t0/2 classificadores então

weight(t(0)) ≥ Mt(0)/2 (*)

Boosting

Teorema. Seja A um -weak learner para o conjunto S. Se t0 Omega(1/ 2 log n), então MAJ(h1,…,ht0) tem erro de treino 0.

Prova

• Como no máximo (1/2- ) dos exemplos são classificados errados

weight(t+1) ≤ (1+2 )weight(t)

• Como o peso inicial é n então

weight(t0) ≤ n (1+2 ) t(0) (**)

Boosting

Teorema. Seja A um -weak learner para o conjunto S. Se t0 Omega(1/ 2 log n), então MAJ(h1,…,ht0) tem erro de treino 0.

Prova

• Combinando os bounds (*) e (**) concluímos que M<1

CQD

Boosting

• É possível relaxar a definição de weak learner

07/06/2017

16

Bibliografia

• Cap 5. Foundations of Data Science, Avrim Blum, John Hopcroft and Ravindran Kannan http://www.cs.cornell.edu/jeh/book.pdf

Combining Expert Advice