Aprendizagem de Máquina
(Machine Learning)
Filipo Studzinski Perotto
Luís Otávio Álvares
Porto Alegre,
Junho de 2008.
Sumário
•
•
•
•
Introdução
Aprendizagem Supervisionada
Aprendizagem Não-Supervisionada
Aprendizagem por Reforço
2
Introdução
Comportamento Inteligente
X
Aprendizagem
3
Como pré-programar toda a
solução para problemas
complexos e dinâmicos?
4
Aplicações Bem-Sucedidas
• Aprender a reconhecer palavras faladas
• Aprender a conduzir um veículo
• Aprender a classificar estruturas astronômicas
• Aprender a jogar
• Aprender a classificar e-mails
• Descoberta de relações em bases de dados
5
Definindo
Aprendizagem de Máquina
• Um sistema apresenta aprendizagem se ele é
capaz de transformar-se adaptativamente a
partir das próprias experiências
• Portanto, num problema de aprendizagem bem
formulado identificamos 3 fatores:
– a classe das tarefas T
– a medida de desempenho a ser melhorada P
– e a fonte de experiência (treinamento) E.
6
Aprendizagem Supervisionada
• Existe um “professor”
• Fonte externa indica
certo e errado
7
Classificação
Definição do Problema
• Dados:
– Um conjunto de exemplos de treinamento
• na forma (entrada-saída)
• Encontrar:
– uma função geral capaz de prever adequadamente as saídas
para novos exemplos, por representar, em princípio, a função
geradora dos exemplos de treinamento
8
Abordagem Conexionista
• Rede Neural / Máquinas de Núcleo
– O conhecimento da rede fica armazenado nos pesos das ligações
entre os nós
• O conhecimento é distribuído:
– uma unidade pode participar
de diversos padrões
– um padrão pode estar ligado
à diversas unidades
9
Abordagem Estatística
• Modelo Incremental:
– inicia com uma hipótese a priori da distribuição
– atualiza a distribuição conforme recebe os exemplos
10
Rede Bayesiana:
Hábito 1
Hábito 2
Hábito 3
Sintoma 1
Sintoma 2
Sintoma 3
Filtro Bayesiano:
11
Aprendizagem de Conceitos
• Dados:
– Um Espaço de Características
– Um conjunto de exemplos de treinamento
• Características (f1, f2, f3, ..., fn)
• Rótulo z
• Encontrar:
– Um Modelo de Classificação
Entradas
Modelo
Saídas
12
Melhor Hipótese Corrente
H ← Qualquer Hipótese consistente com o 1º Exemplo
Para cada Novo Exemplo faça:
Se é falso positivo para H então:
H ← Especialização de H (+ condições)
Se é falso negativo para H então:
H ← Generalização de H (- condições)
13
Mundo dos Blocos
Um Arco é:
- 2 blocos azuis em pé paralelos
+
- um bloco azul sobre os outros dois
Um Arco é:
- 2 blocos de qualquer cor em pé paralelos
+
- um bloco sobre os outros dois
Um Arco é:
- 2 blocos em pé separados e paralelos
- um bloco sobre os outros dois
-
14
Espaço de Versões
• Preserva todas as Hipóteses Válidas
• Representação:
– G (Conjunto de Hipóteses mais Gerais)
– S (Conjunto das Hipóteses mais Específicas)
– Conjunto Parcialmente Ordenado
• Atualização do Espaço de Versões:
– Especializa G com um falso positivo
– Generaliza S com um falso negativo
15
-
G
-
-
G1
-
+ ++
+ +
+
+
+
+
+
+
S
2
-
-
-
-
-
-
+ +
+
-
16
Hipóteses mais
G1 G2 G 3 G4 G5
...
Gn
Gerais
...
S1
S2
S3
S4
S5
...
Sm
Hipóteses mais
Específicas
17
Árvores de Decisão
• Nós Superiores:
F1
Testes de Discriminação
F2
F3
Fn
...
y1
ym
• Folhas:
Rótulo da Classe
18
Prejuízo
Situação
Explicação
Atitude
Alto
Médio
Médio
Alto
Baixo
Baixo
...
Anonimato
Anonimato
Evidência
Evidência
Evidência
Anonimato
...
Boa
Ruim
Ruim
Ruim
Boa
Ruim
...
Ficar
Correr
Ficar
Correr
Ficar
Ficar
...
19
Prejuízo
médio
Ficar
alto
Ficar
Anonimato
não
baixo
Explicação
sim
Correr
boa
Ficar
ruim
Correr
20
Indução de Árvores de Decisão
S inicial = o conjunto de todos os exemplos de treinamento;
SE todos os elementos em S satisfazem o critério de parada,
ENTÃO:
Cria um Nó Folha, caracterizando uma classe;
SENÃO
Seleciona um Atributo A
Cria um Nó de Discriminação baseado em A;
Particiona S em subconjuntos, conforme A;
Aplica o algoritmo recursivamente em cada subconjunto;
21
Indução: passo 1
O+O+
+O+O
OO++
22
Indução: passo 2
O+O
+O+
OO+
++
+
23
Indução: passo 3 ... n
++
+
OO
O
OO+
O+
24
• Construção da Árvore
– Critério de Escolha dos Atributos Discriminantes
– Critério de Parada do Particionamento
– Objetivo: minimizar a árvore
• Complexidade
– Encontrar a árvore mínima é NP-Completo
– Saída: Utilização de Heurísticas
25
• Critério para Seleção de Atributos
– Baseado no Ganho de Informação
– Um bom candidato separa bem os exemplos entre as classes
– Critério de Ganho: Redução Esperada da Entropia
• Entropia
– Quantidade de Informação necessária para fazer a descrição dos
elementos do conjunto
– Muitas classes misturadas e homogeneamente distribuídas dentro de
um grupo representam alta entropia
• Entropia( 50% / 50%) = 1
• Entropia( 100% / 0%) = 0
26
• Superadaptação
– Ramos
excessivos
que
não
significativamente para a classificação
contribuem
• Poda
– Pode considerar
• Taxa de Erro
• Limite Mínimo de Ganho
– Pode ser feita
• Durante a construção (limite como critério de parada)
• Depois da construção (revisão)
– Substitui uma subárvore por uma folha
27
Superadaptado?
Generalização Adequada?
28
Aprendizagem Computacional
• Provavelmente Correta
• Aproximadamente Correta
• Conjunto suficientemente grande de exemplos
de treinamento
É quase certo que qualquer hipótese que esteja seriamente errada será
‘desmascarada’ com alta probabilidade após um pequeno número de
exemplos.
Qualquer hipótese que seja consistente com um conjunto suficientemente grande
de exemplos de treinamento terá pouca probabilidade de estar seriamente
errada.
29
Aprendizagem Não-Supervisionada
• Aprendizagem Não-Supervisionada
– Não há exemplos nem classes pré-definidas
– Domínios naturalmente divididos em classes
– Análise de padrões nos dados de entrada através da
distribuição no espaço
– Análise de correlações e coincidências
– Descoberta de Conhecimento
Entradas
Modelo
30
Clusterização
Definição do Problema
• Dados:
– Um Espaço de Características
– Um Conjunto de Instâncias situadas nesse espaço
• Encontrar:
– Grupos de entidades similares (Clusters)
– Regiões com alta densidade relativa de pontos no espaço
31
• Exemplo:
32
Método Hierárquico Divisivo
• Todos os objetos são inicialmente alocados a um único
grupo, e esse vai sendo dividido (ou partido) em grupos
menores.
Geral
Sub1
teste de discriminação
Sub2
Sub n
...
33
34
Método de Centróides
Pontos representativos de possíveis conceitos são
espalhados inicialmente no espaço de entradas. Cada um
desses pontos conceituais vai se aproximando da nuvem
de pontos de entrada mais próxima.
35
10
9
8
10
7
9
6
8
5
7
4
6
Atualiza
Médias
3
2
5
4
1
3
0
2
0
1
2
3
4
5
6
7
8
9
10
1
0
0
K= Número de
Agrupamentos
1
2
3
4
5
6
7
8
9
10
Reassocia
10
9
8
Inicialização
Aleatória
7
10
6
Atualiza
Médias
5
4
9
8
7
3
6
2
5
1
4
3
0
0
1
2
3
4
5
6
7
8
9
10
2
1
0
0
1
2
3
4
5
6
7
8
369
10
• Problema:
Desequilíbrio na distribuição dos centros...
37
Aprendizagem por Reforço
Metáfora do Agente:
Idéia de interação contínua
Agente
Percepções
Ação
Reforço (+/-)
Ambiente
38
Política de Ações
Definição do Problema
• Dados:
– Um Agente em um Ambiente
– A cada instante de tempo:
•
•
•
•
o agente está em um estado s
executa uma ação a
vai para um estado s’
recebe uma recompensa r
• Encontrar:
– uma política de ações que maximize o total de recompensas
recebidas pelo agente
39
Questão da Autonomia
• Como um agente aprende a escolher ações
apenas interagindo com o ambiente?
– Muitas vezes, é impraticável o uso de
aprendizagem supervisionada
• Como obter exemplos do comportamento correto e
representativo para qualquer situação?
• E se o agente for atuar em um ambiente
desconhecido?
40
A Função de Recompensa
• Feedback do ambiente sobre o
comportamento do agente
• Indicada por r:(S  A) R
– r(s,a) indica a recompensa recebida quando se
está no estado s e se executa a ação a
– Pode ser determinística ou estocástica
41
Política de Ações
• Aprendizagem por Reforço
– não há exemplos
– existe um feedback do ambiente (recompensa) que avalia o
comportamento do agente
• Aprendizagem Incremental
– Desempenho + Exploração
42
Estimativa da Recompensa
Recompensas
Utilidade
0
0
0
0
10
3
4
6
8
10
0
0
0
0
0
2
3
4
6
8
0
0
0
0
0
1
2
3
4
6
0
0
0
0
0
0
1
2
3
4
43
Métodos de Função de Utilidade
U(s) : (S  R)
• Cálculo da Função de Utilidade do Estado:
– Faz uma tabela com a utilidade de cada estado
– Utilidade é a estimativa de recompensas futuras
– Constrói um Modelo de Transição de Estados
• Algotitmos: TD, PDA
44
Métodos de Valor das Ações
Q(s,a) : (S  A)  R
• Cálculo do Valor das Ações:
– Faz uma tabela com o valor de cada par (estadoação)
– Avalia cada par (estado-ação) pelas recompensas
– Método Livre de Modelo
• Algoritmos: Q-Learning
45
Estimativa da Recompensa
• A idéia:
– R := Rt + *Rt+1 + 2*Rt+2 + ...
– Rt é a Recompensa da ação atual
–  é um fator de desconsideração para as
recompensas previstas nos passos futuros
46
Estimativa da Recompensa
• Atualização da Tabela Utilidade do Estado:
– V = R + (V[s’])
– U[s]  U[s] + (V - U[s])
• Atualização da Tabela Valor da Ação:
– V = R +  maxa’ (Q[s’, a’])
– Q[a,s]  Q[a,s] + (V - Q[a,s])
47
Exemplo: Labirinto (=0.9)
Função recompensa
Função Q*
Função V*
Uma política de ações ótima
48
Abordagem Evolutiva
• Sistemas Classificadores
– Constrói um conjunto de regras (estado, ação)
– Aplica Algoritmos Genéticos neste conjunto
– Recompensas avaliam a força das regras
Criar Regras
Avaliar Regras
Descoberta
(Algoritmos Genéticos)
Escolher Regras
Atribuição de Crédito
(Bucket Brigade)
Entrada
Desempenho
(Sistema Classificador)
Saída
Recompensa
49
Algoritmo Q-Learning
• Para todo estado s e ação a, inicialize a tabela
Q[s][a] = 0;
• Para sempre, faça:
–
–
–
–
Observe o estado atual s;
Escolha uma ação a e execute;
Observe o próximo estado s’ e recompensa r
Atualize a tabela Q:
• V = R +  maxa’ (Q[s’, a’])
• Q[a,s]  Q[a,s] + (V - Q[a,s])
50
Q-Learning
• Atualiza-se Q(st) após observar o estado st+1 e
recompensa recebida
•
Q(s1,aright) = r + maxa’Q(s2,a’)
= 0 + 0.9 max{63,81,100}
= 90
51
Dilema aproveitamentoexploração
• Na aprendizagem por reforço ativa o agente
enfrenta dilema aproveitamento-exploração:
– Quando gulosamente aproveitar da estimação atual da
função valor e escolher ação que a maximiza?
– Quando curiosamente explorar outra ação que pode
levar a melhorar estimação atual da função valor?
– Taxa de exploração = proporção de escolhas curiosas
– Geralmente se começa com uma taxa de exploração alta
que vai decrescendo com tempo
52
Exemplos
• Arm Robot Problem:
– http://www.applied-mathematics.net/
53
Maldição da Dimensionalidade
• o número de estados possíveis cresce
exponencialmente com a quantidade de
características representadas
• Conseqüentemente o tempo de treinamento e
número de exemplos necessários também
• Q-Learning só pode ser aplicado a problemas
relativamente pequenos
54
Questão:
• É melhor aprender um modelo e uma
função de utilidade ou apenas uma função
de ação-valor sem modelo?
• Qual o limite dessa idéia de aprendizagem?
55
56
Aprendizagem de Máquina
Filipo Studzinski Perotto
Luís Otávio Álvares
Porto Alegre,
Junho de 2008.
cv , 2
cv , 2
cv , 2
cv ,1
cv , 2
cv ,1
cv , 2
ck
cv ,1
xi
cv ,1
cv , 2
cv , 2
cv , 2
cv , 2
cv , 2
cv , 2
cv ,1
cv , 2
cv ,1
cv , 2
ck
cv ,1
xi
cv ,1
cv , 2
cv , 2
cv , 2
58
Problema da Estrutura
• Aprendizagem de Variáveis Ocultas
– criar e destruir variáveis
– problema: complexidade exponencial
Hábito 1
Hábito 2
Hábito 3
Doença
Sintoma 1
Sintoma 2
Sintoma 3
59
Indução de Árvores de Decisão
60
Máquinas de Núcleo
• Aumentar a Dimensionalidade do Espaço.
• Tornar o Problema
Linearmente Separável
• Uso de Vetores de Suporte
• Uso de Funções de Núcleo
61
• Percorrer a Árvore
– Tomada de Decisão
– Expressão através de Regras: Disjunção de Conjunções
Estrago
médio
Ficar
alto
Ficar
Anonimato
não
baixo
sim
Fugir
Explicação
boa
Ficar
ruim
Fugir
Se (Estrago = Alto) e (Explicação = Ruim) Então Fugir
62
Algoritmos de Indução de AD
• ID3
–
–
–
–
Representa apenas atributos categóricos
Subdivide o grupo pela cardinalidade do atributo de teste
Não faz tratamento de ruídos
Utiliza critério de ganho de informação no particionamento
• CART
– Permite atributos numéricos
– Gera sempre divisões binárias (agrupando valores)
– Pode fazer regressão (função numérica)
• C4.5
– Permite atributos numéricos e valores desconhecidos
– Utiliza Poda
63
Abordagens:
–
–
–
–
–
Simbólica
Conexionista
Analítica
Evolutiva
Estatística
Condições:
–
–
–
–
Representação
Ruído
Determinismo
...
64
Maldição da Dimensionalidade
“Maldição da Dimensionalidade”: o número de classificadores
que devem ser considerados aumenta exponencialmente com o
número de atributos do conjunto de dados, ficando mais difícil
para o algoritmo de aprendizagem encontrar um modelo
preciso (Bellman, 1961).
“O número de exemplos necessários para se aprender um certo
conceito cresce exponencialmente de acordo com o número de
atributos” (Valiant, “A Theory of The Learnable”, 1984).
65
Exemplo Não-Determinístico
Ações: ,,,
Chance da execução correta: 90%
-1
-1
-1
-1
+100
-1
-1
-1
-1
-100
-1
-1
-1
-1
-1
-50
-50
-50
-50
+100
A
-1
-1
-1
-1
-50
-50
-50
-50
-100
-50
-50
-50
-50
-50
A
-50
-50
-50
-50
66