Teoria do Aprendizado Computacional

Prévia do material em texto

Inteligência Artificial
Prof. Renato Sassi
Machine Learning – Tom Mitchell
Capítulo 7 – Teoria do Aprendizado 
Computacional
Nelson Koshoji
1
– “Em que condições um aprendizado bem 
sucedido pode ser possível ou impossível?”
– “Em que condições um algoritmo de 
aprendizado específico garante o sucesso 
do aprendizado?”
2
• “Quantos exemplos de treinamento são 
necessários para o sistema convergir (com 
uma probabilidade alta) a uma hipótese bem 
sucedida?”
• “Quanto esforço computacional será 
necessário para isso?”
• “Quantos erros serão cometidos antes de uma 
hipótese bem sucedida?”
3
Dado uma função alvo desconhecida, um 
treinamento (D) e um espaço de hipóteses (H). 
Dentro deste cenário, é possível definir limites 
quantitativos sobre essas medidas, tais como:
• tamanho ou complexidade do espaço hipótese;
• precisão com a qual o conceito deve ser 
aproximado;
• a probabilidade de uma hipótese bem sucedida; 
• a maneira como os exemplos de treinamento são 
obtidos.
4
Para Análise de Algoritmo de Aprendizado
Computacional são considerados dois “frameworks” :
• PAC (Provavelmente Aproximadamente Correto) 
– Identifica classes de hipóteses que podem ou 
não ser aprendidas a partir de um número 
polinomial de exemplos de treinamento.
• Erro limite – examina o número de erros de 
treinamento que será feito por aprendizado antes 
de determinar a hipótese correta 
5
Modelo PAC (Provavelmente Aproximadamente 
Correto)
• Seja X um conjunto de todas as instancias 
possíveis
• C – conjunto de conceitos alvos para o 
aprendizado, gerados através da função booleana 
c:X→{0,1} 
• D – Exemplos de treinamento gerados por uma 
distribuição de probabilidade
• Aprendiz L - emite algumas hipóteses h dentro de 
um conjunto de hipóteses possíveis dentro de H.
6
Erro de uma Hipótese (true error)
• O verdadeiro erro da hipótese [h], em relação ao 
conceito alvo [c] e a distribuição {D}, é a 
probabilidade de que h irá classificar 
erroneamente uma instância de modo aleatório.
7
PAC - Aprendível
• Objetivo: caracterizar as classes de conceitos 
alvo que podem ser aprendidas de forma 
confiável a partir de um número razoável de 
exemplos de treinamento sorteados e uma 
quantidade razoável de computação.
• Esperar um perfeito aprendizado onde 
errorD(h) = 0
• Neste espaço amostral, não podemos esperar 
errorD(h) = 0 , então ...
8
• Exigir apenas que o erro seja limitado por uma 
constante pequena, ε.
• Não exigir que o aprendizado seja bem 
sucedido para cada seqüência de exemplos de 
treinamento sorteados, mas exigir apenas que 
a sua probabilidade de falha seja limitada por 
alguma constante , δ.
• Parâmetro de erro (ɛ) e parâmetro de 
confiança (δ)
9
• O conceito C é PAC-aprendível por L usando H 
se para todo c є C, e as distribuições D sobre X, 
onde 0<ε<1/2 e 0<δ<1/2; o aprendiz L com 
amostras aleatórias de D, com probabilidade 
pelo menos (1−δ) terá como saída uma 
hipótese h є H tal que errorD(h)<=ε
• Após o algoritmo ter observados (m) exemplos, 
o aprendiz L irá gerar hipóteses consistentes 
com alta probabilidade de estarem 
aproximadamente corretas, logo, aprendiz 
provavelmente aprende uma hipótese 
aproximadamente correto (PAC).
10
Complexidade das amostras para 
espaços finitos
• O aumento no número de exemplos de 
treinamentos necessários com o tamanho do 
problema chamamos de complexidade da 
amostra.
• Para espaços finitos teremos um aprendiz L 
consistente, pois um aprendiz é consistente se 
produz hipóteses que se encaixam 
perfeitamente os dados de treinamento, 
sempre que possível.
11
• Recordando ... (espaço de versão)
• O espaço de versão no que diz respeito ao 
espaço hipótese H e exemplos de treinamento 
D, é o subconjunto de hipóteses de H 
consistente com os exemplos de formação em D
• Serão gerados hipóteses que só pertencem ao 
espaço de versão.
• Precisamos limitar o número de exemplos (m) 
necessários para assegurar que o espaço versão 
não contenha hipóteses inaceitáveis.
12
• Considere um espaço hipótese H, conceito 
alvo c, exemplo de distribuição D, e um 
conjunto de exemplos de treinamento D de c. 
O espaço de versão VSH,D é dito ε-exhausted, 
se cada hipótese h em VSH,D tem um erro 
inferior a ε em função a C e D.
13
14
• Tem formação de erro r = 0
• Se o espaço hipótese H é finito, e D é uma 
sequência de exemplos m > = 1 tirados ao 
acaso de um conceito de destino C, para 
qualquer 0 <= ε < = 1, a probabilidade de que 
a versão de espaço VSH,D não seja ε-exhausted 
é menor ou igual a
15
• O limite para a probabilidade de que (m) 
exemplos de treinamento vai deixar de 
eliminar todas as hipóteses "maus" (ou seja, 
as hipóteses com true error maior do que ε ). 
Utilizamos este resultado para determinar o 
número de exemplos de treino necessárias 
para reduzir a probabilidade de falha menor 
do que δ: 
16
17
• Isolando o m, temos:
• A equação acima fornece o número de exemplos 
de treinamentos suficientes para qualquer aprendiz 
consistente para aprender com sucesso qualquer 
conceito alvo em H, para quaisquer valores 
desejados de δ e ε . Este número é suficiente para 
garantir que qualquer hipótese consistente será 
provavelmente (com probabilidade (1 - δ)) 
aproximadamente (dentro do erro ε) correta. (m) 
cresce linearmente em 1/ε e logarítmica em 1/δ. 
• Exemplo: EnjoySport() 
– Hipóteses: considerando (4 * 3 * 3 * 3 * 3 * 3) + 1 
= 973
– Com um probabilidade de 95%, o VSD,H contém 
hipóteses somente com ErrorD(h)<=0.1, então...
– Temos, exemplos de treinamento.
18
))1ln(||(ln1

 Hm
))
05,0
1ln(973(ln
1,0
1 m
8,98m
Complexidade de Amostras do
Aprendizado de Conjunções Booleanas 
em espaços finitos
Considere conjunções com n características booleanas. 
Exemplo: Velho, sua negação Velho
Exemplo de Conjunção: Velho ^ Alto
Cada característica pode aparecer forma positiva, de 
forma negativa ou não aparecer. Logo, serão 3n
conjunções, então |H|= 3n . Substituindo ...
19


• Exemplo: Se um aprendiz precisa aprender 
um conceito alvo descrito por conjunções de 
até 10 características booleanos, e desejamos 
uma probabilidade de 95 % que vai aprender 
uma hipótese com erro menor do que 0,1. 
Qual o valor de (m)?
20
))1ln(3ln(1

 nm
140))
05,0
1ln(3ln10(
1,0
1 m
Complexidade das amostras para 
espaços infinitos
• Alguns espaços de hipóteses infinitos são mais 
expressivos do que outros. 
• Usamos, então, o chamado dimensão Vapnik -
Chervonenkis de H (dimensão VC , ou VC(H))
21
• Considere um conjunto de instâncias S em X
{xS | h(x) = 1}
{xS | h(x) = 0}
• Temos 2|S| possíveis
dicotomias.
• Exemlo: 23 = 8
• Um conjunto de três instancias que foi quebrada por 
oito hipóteses 
22
Dimensão VC
• Exemplo: Duas instâncias
– S = {3.1,5.7}, VC(H)?, S pode ser quebrado por H 
(por um único intervalo)?
– VC(H) = 2
23
24
• Três instâncias
• VC(H)=2
• Não é possível quebrar por um único intervalo
Outro Exemplo
25
No primeiro caso , o conjunto de 3 pontos pode ser quebrado. 
A dimensão VC(H) de superfícies de decisão linear no plano 
é de 3. 
No segundo caso, o conjunto de 3 pontos não pode ser 
quebrado
Complexidade de amostras usando 
dimensão VC
• Para amostras complexas usando dimensão 
VC podemos determinar que o números de 
exemplos é suficiente para o modelo PAC, pela 
seguinte equação: 
• (Blumer et al., 1989)
• 1/ε não cresce mais linearmente e sim 
logaritmicamente, assim como 1/δ 
26
Modelo Erro Limite
• Este modelo está vinculado ao erro de aprendizagem, 
no qual o aprendizé avaliado pelo número total de 
erros que se faz antes de convergir para a hipótese 
correta.
• Quantos erros o aprendiz vai fazer em suas previsões 
antes de aprender o conceito alvo?
• Importante em cenários práticos enquanto o sistema 
está em uso real. Ex. Fraude em cartão de crédito.
• Aprender o conceito alvo significa convergir 
exatamente para uma hipótese de tal modo que 
( x)h(x)=c(x ) .
27
Erro Limite: Find-S algorithm
• Seja H = conjunto de literais booleanos:
• Find-S
– Inicie h com a hipótese mais específica:
• l1 ^ ¬l1 ^ l2 ^ ¬l2 … ln ^ ¬ln
– Para cada positivo, treine a instancia x
• Retire do h qualquer literal que não é satisfeita por x.
– Saída da hipótese h
• Para calcular o número de erros, precisamos apenas 
contar o número de erros que classificará 
erroneamente tanto para exemplos positivos como 
negativos. 
• Número total de erros: n+1
28
Erro Limite: HALVING algorithm 
• Este conceito usa o VS Candidate-Elimination 
algorithm
• Para encontrar o erro, observa-se que a única vez 
que o Halving algorithm pode cometer um erro é 
quando a maioria das hipóteses em seu VS classifica 
incorretamente um novo exemplo. Neste caso, 
espaço versão será reduzido para a metade do seu 
tamanho atual 
• Dado que cada erro reduz o tamanho do espaço de 
versão, pela metade, e dado que o VS inicial contém 
apenas membros de |H|, o número máximo de 
possíveis erros pode ser dado por log2|H|.
• Considere-se, por exemplo, o caso em que |H| = 7. O 
primeiro erro deve reduzir |H| a, no máximo 3, e o 
segundo erro, então reduzi-la a 1 .
29
Erro Limite Ótimo
• Seja MA(C) o número máximo de erros cometidos 
pelo algoritmo A para aprender conceitos em C
• Seja C uma classe de conceito. O erro limite ótimo 
Opt (C) é o mínimo sobre todos os algoritmos de 
aprendizagem possíveis A do MA (C).
30
)(max)( cMCM A
Cc
A 

• Littlestone (1987) mostra que para qualquer 
classe conceito C, há uma relação interessante 
entre o erro ótimo, o Halving algorithm e a 
dimensão VC de C, ou seja:
31
Erro Limite Ótimo
OBRIGADO !
32