Aprendizagem Automática
Uma Introdução
Cristina Mota
Instituto Superior Técnico
L2F Inesc-ID
New York University
O que é Aprendizagem Automática?
“The field of Machine Learning is concerned with the
question of how to construct computer programs that
automatically improve with experience” (Mitchell, 1997)
“Machine learning studies automatic techniques for learning to make
accurate predictions based on past observations” (Schapire, 2001)
Exemplo
Problema: Filtrar as mensagens electrónicas de modo a reconhecer SPAM
Abordagem de Aprendizagem Automática:
1 – Reunir tantos exemplos quanto possível de SPAM e não-SPAM
2 – Fornecer esses exemplos, previamente classificados (S/NS), ao
algoritmo favorito de Aprendizagem que automaticamente irá produzir
uma classificação ou regra de predição
3 – Dado um novo exemplo, não classificado, a regra tenta atribuir uma
classificação
O objectivo é produzir uma regra que faça predições tão precisas quanto
possível relativamente a novos exemplos.
Definição do problema
Classe de tarefas
Medida de desempenho a ser melhorada
Fonte de aprendizagem
Problema de aprendizagem de Reconhecimento de EMs
Tarefa T: Identificar e classificar EMs em textos
Medida de desempenho D: Medida-F
Fonte de aprendizagem E: Texto previamente classificado
Desenho do sistema
Escolher:
- a experiência de treino Como?
- uma função alvo O quê?
- uma representação para a função alvo
- algoritmo de aproximação da função
- estimar valores de treino
- ajustar os valores
- desenho final
Questões
Que algoritmos existem para aprender funções alvo genéricas a partir de
exemplos de treino?
Em que condições converge o algoritmo, havendo dados de treino suficientes?
Que algoritmos se comportam melhor face a que tipo de problemas e
representações?
Que quantidade de dados de treino é necessária?
Que limites genéricos podem ser encontrados que relacionem a confiança nas
hipóteses aprendidas e a quantidade de experiência de treino e natureza do
espaço de hipóteses do “aprendiz”?
Quando e como é que conhecimento anterior mantido pelo “aprendiz” pode
guiar o processo de generalização a partir de exemplos?
Pode o conhecimento anterior
aproximadamente correcto?
ser
útil
mesmo
quando
só
está
Desenho do sistema
Qual é a melhor estratégia para escolher a experiência seguinte mais útil?
Como é que a escolha dessa estratégia altera a complexidade do problema de
aprendizagem?
Qual é a melhor forma para reduzir a tarefa de aprendizagem a um ou mais
problemas de aproximação de funções?
Ou seja, que funções específicas deve o sistema tentar aprender?
Pode este mesmo processo ser automatizado?
Como é que o “aprendiz” pode automaticamente alterar a sua representação para
melhorar a sua capacidade de representar e aprender a função alvo?
Paradigmas de Aprendizagem
COMPUTACIONAL Existe uma representação simbólica manipulada por um
sistema de inferência
Dedutivo Conhecimento inferido a partir do
que já existe, mas que estava implícito. O novo
conhecimento é sempre verdadeiro. Com base
em apenas um exemplo, cria novas regras.
Mecanismo de Inferência
Indutivo Obtenção de conhecimento
instrinsecamente novo. O novo conhecimento
pode não ser verdadeiro. Usa técnicas de
generalização. Usa vários exemplos para criar
novas regras.
Analógico Dado um outro problema e a sua
solução, relaciona os dois problemas para
chegar a uma nova solução. É necessário
descobrir problemas análogos ao que se tem
em mãos.
Paradigmas de Aprendizagem
COMPUTACIONAL Existe uma representação simbólica manipulada por um
sistema de inferência
Aprendizagem de conceitos (Concept Learning) aquisição da definição de uma
categoria genérica a partir de exemplos positivos e negativos dessa categoria.
Decision Tree Learning Método para aproximar funções de valores discretos que
é robusto a dados com ruído, capaz de aprender expressões disjuntivas.
Ex: ID3, ASSISTANT, C4.5
Adequados para problemas com as seguintes características
- Instâncias representadas por pares atributo-valor
- A função alvo tem saídas discretas
- Pode ser necessário descrições disjuntivas
- Os dados de treino podem conter erros
- Os dados de treino podem conter valores desconhecidos
Paradigmas de Aprendizagem
NEURONAL Inspirado no funcionamento do cérebro
Perceptrão de Rosenblatt
1
x1
a0
a1
x2
a2
xn-1
∑
S
an-1
an
xn
Regra de Aprendizagem ≡ ai(n+1) = ai(n)-ηxi(o-d)
0/1
Paradigmas de Aprendizagem
NEURONAL Inspirado no funcionamento do cérebro
ADALINE – ADAptive LINear Element
1
x1
a0
a1
x2
a2
xn-1
∑
O
an-1
an
xn
Regra de Aprendizagem (delta rule) ≡ ai(n+1) = ai(n)-η∑xik(ok-dk)
Batch
(LMS – Least Mean Squares)
Online
≡ ai(n+1) = ai(n)-ηxik(ok-dk)
Paradigmas de Aprendizagem
NEURONAL Inspirado no funcionamento do cérebro
Perceptrão multicamada para a frente
1
b0
1
x1
a0
a1
S1
∑
xn
y1
an
d1
c0
c1
∑
xn
d2
S2
y3
bn
1
d0
1
x1
S3
∑
∑
S4
y2
cn
Aprendizagem: Retropropagação
y4
Paradigmas de Aprendizagem
NEURONAL Inspirado no funcionamento do cérebro
Adequados para problemas com as seguintes características
- Instâncias representadas por muitos pares atributo-valor
- Funções com valores reais, discretos e vectoriais
- Os dados de treino podem conter ruído
- É aceitável ter tempos de processamento grandes
- Possa ser necessário uma rápida avaliação da função alvo
- A (in)capacidade de humanos compreenderem a função alvo não é
importante
Paradigmas de Aprendizagem
GENÉTICO Inspirado na teoria de evolução das espécies
População Inicial
Selecção Natural
Função de adaptação
1/3
1/3
X=∑
2/9
1/9
Paradigmas de Aprendizagem
GENÉTICO Inspirado na teoria de evolução das espécies
População Inicial
Selecção Natural
Função de adaptação
Recombinação
Pontos de corte
X=∑
Paradigmas de Aprendizagem
GENÉTICO Inspirado na teoria de evolução das espécies
População Inicial
Selecção Natural
Função de adaptação
Recombinação
Pontos de corte
X=∑
Paradigmas de Aprendizagem
GENÉTICO Inspirado na teoria de evolução das espécies
População Inicial
Selecção Natural
Função de adaptação
Recombinação
Pontos de corte
Mutação
Frequência
X=∑
Paradigmas de Aprendizagem
GENÉTICO Inspirado na teoria de evolução das espécies
Nova População
Selecção Natural
Função de adaptação
Recombinação
Pontos de corte
Mutação
Frequência
FIM: Solução óptima ou suficientemente boa
X=∑
Paradigmas de Aprendizagem
EMERGENTE Inspirado na organização das sociedades
Depende de um autómato celular (rede de células), em que cada
célula tem um estado que das células vizinhas e é fixado por um
conjunto de regras
As transições de estado de um autómato celular dão-se em
paralelo
Problema da Generalização
Universo
Treino
Teste
Validação
Validação Cruzada
Erro
x
Aprendizagem em PLN
Brill
Yarowsky
Mikheev
Borthwick