Aprendizagem de máquina:
visão geral
Francisco Carvalho, Paulo Adeodato,
Geber Ramalho, Jacques Robin, Marcilio
Campos, Teresa Ludermir
CIn-UFPE
Técnicas de aprendizagem
Paradigma simbólico:
 Aprendizagem de conceitos por
busca no espaço de soluções
(version-space)
 Indução de árvores de decisão
e regras proposicionais
 Programação em lógica indutiva
 Raciocínio baseado em casos
 Agrupamento de conceitos
proposicionais
Paradigma Fuzzy:
 Fuzzy clustering
Paradigma probabilista:
 K Vizinhos mais próximo
 Regressão estatística
 Aprendiz bayesiano ingênuo
Paradigma conexionista:
 Perceptron multicamada
 Redes de Kohonen
 Memórias associativas
Paradima evolucionista:
 Algoritmos genéticos
Abordagens híbridos:
 Rede bayesianas
 Sistemas neuro-fuzzy
Classificação Bayesiana



Aprendizado probabilista: Cálcula probabilidades
explícitas para hipóteses, entre as abordagens mais
práticas para certos tipos de porblemas de aprendizagem
Incremental: Cada exemplo pode, incrementalmente,
aumentar/diminuir a probabilidade de que uma hipótese
seja correta. Pode-se combinar conhecimento prévio com
dados observados
Previsão probabilistica: Previsão de multiplas hipóteses,
ponderadas pelas suas probabilidades
Teorema de Bayes

Dado um conjunto de dados de treinamento D, a probabilidade
a posteriori de uma hipótese , P(h|D) segue o teorema de Bayes
P(h | D)  P(D | h)P(h)
P(D)

MAP hipótese de maior probabilidade a posteriori
h
 arg max P(h | D)  arg max P(D | h)P(h).
MAP
hH
hH

Dificuldade prática: requer conhecimento inicial de muitas
probabilidades, custo computacional significativo
Classificação Bayesiana

O problema de classificação pode ser formulado
usando-se probabilidades a posteriori:



P(C|X) = prob. de que a observação
X=<x1,…,xk> seja da classe C.
Ideia: atribuir a observação X a classe de rótulo C tal
que P(C|X) é máximo
Estimação de probabilidades a posteriori

Teorema de Bayes:
P(C|X) = P(X|C)·P(C) / P(X)

P(X) é constante para todas as classes

P(C) = frequencia relativa dos exemplos da classe C

C tal que P(C|X) é maximo =
C tal que P(X|C)·P(C) é máximo

Problema: Calculo de P(X|C) é irrealizável
Classificador Bayesiano Igenuo
Suposição ingenua: independencia entre os atributos
P(x1,…,xk|C) = P(x1|C)·…·P(xk|C)
 Se o I-ésimo atributo é categorico:
P(xi|C) é estimado como a frequência relativa das
observações tendo valor xi para o I-ésimo attribute
na classe C
 Se o i-ésimo atributo é continuo:
P(xi|C) é estimatedo via uma função de densidade
Gaussiana
 Computacionalmente facil em ambos os casos

Classificador bayesiano ingênuo: exemplo
Dia Tempo Temp. Humid.
D1 Sol
Quente Alta
D2 Sol
Quente Alta
D3 Coberto Quente Alta
D4 Chuva Normal Alta
D5 Chuva Frio
Normal
D6 Chuva Frio
Normal
D7 Coberto Frio
Normal
D8 Sol
Normal Alta
D9 Sol
Frio
Normal
D10 Chuva Normal Normal
Vento
Fraco
Forte
Fraco
Fraco
Fraco
Forte
Forte
Fraco
Fraco
Fraco
D11 Sol
Forte
Frio
Alta
Jogar
Não
Não
Sim
Sim
Não
Não
Sim
Não
Sim
Sim
?
P(Sim) = 5/10 = 0.5
P(Não) = 5/10 = 0.5
P(Sol/Sim) = 1/5 = 0.2
P(Sol/Não) = 3/5 = 0.6
P(Frio/Sim) = 2/5 = 0.4
P(Frio/Não) = 2/5 = 0.4
P(Alta/Sim) = 2/5 = 0.4
P(Alta/Não) = 3/5 = 0.6
P(Forte/Sim) = 1/5 = 0.2
P(Forte/Não) = 2/5 = 0.4
P(Sim)P(Sol/Sim) P(Frio/Sim)
P(Alta/Sim) P(Forte/Sim) = 0.0032
P(Não)P(Sol/Não)P(Frio/Não)
P(Alta/Não) P(Forte/Não) = 0.0288
 Jogar_Tenis(D11) = Não
A hipótese de independencia…

… torna os cálculos possíveis

… torna o classificador ótimo quando satisfeita


… mas é raramente satisfeita na pratica, pois os
atributos (variaveis) frequentemente são
correlacionadas
Tentativa para superar essa limitação:
• Redes Bayesianas, combina o raciocinio Bayesiano com
relações causais entre atributos
Redes Bayesianas
Hostoria
Familiar
Fumante
(HF, F) (HF, ~F)(~HF, F) (~HF, ~F)
CancerPulmão
RaioXPositive
Emfisema
Dispneia
Rede Bayesiana
CP
0.8
0.5
0.7
0.1
~CP
0.2
0.5
0.3
0.9
A tabela de probabilidades
condicional para a variável
CancerPulmão
Resdes Bayesianas

Redes Bayesianas adimitem um subconjunto de variáveis
condicionalmente independentes

Modelagem gráfica d relações causais

Vários casos de aprendizado de Redes Bayesianas
• Estrutura conhecida, completamente observável

as tabelas de probabilidade condicionada podem ser estimadas
usando o conjunto de exemplos
• Estrutura desconhecida, completamente observável

o problema é construir a topologia da rede.
• Estrutura conhecida, variáveis escondidas

caso parecido com aprendizado em redes neurais
• Estrutura desconhecida, variáveis escondidas

não se conhece algoritmos para este tipo de problema
Paradigma Conexionista: Redes Neurais

Definição
• Técnica inspirada no funcionamento do cérebro, onde neurônios
artificiais, conectados em rede, são capazes de aprender e de
generalizar.
• Técnica de aproximação de funções por regressão não linear.

Modelo de neurônio
e(i)  w ji  sj
s1
w1i
sj
wji
s(i)  f (e(i))
sn
e(i)

semi-linear
t
e
s(i)
wni
s
degrau


s
s
sigmoide
e
e
Multilayer Perceptron (MLP) e
Backpropagation
camada de
entrada
conexões
camadas
intermediárias
camada
de
saída
MLP: complexidade funcional em função do
número de camadas
Cascade-Correlation: complexidade funcional
em função do número de neurônio
1 neurônio
3 neurônios
5 neurônios
Problema
das
2 espirais
7 neurônios
9 neurônios
12 neurônios
Redes Neurais: Perceptron Multi-Camada
com Retropropagação
Multi-Layer Perceptron (MLP)
 Exemplos: codificados na camada (nós) de entrada
 Classe, previsão ou ação: codificada na camada (nós) de
saída
 Algoritmo: parte de pesos aleatórios e iterativamente

• repetitivamente apresenta todos os exemplos
• a cada iteração (época) ajuste pesos tal que:
w ji (t  1)  w ji (t)   s j i
 - taxa de aprendizagem
  (si - di), erro
sj - saída do neurônio anterior j
• até algum critério de convergência chega a ser satisfeito
Redes Neurais

Vantagens
• ~qualidade de previsão geralmente é alta
• Robustes, funciona mesmo uando os exemplos de
treinamento contem erros
• A saída pode ser discreta, continua, ou um vetor de vários
atributos discretos ou contínuos

Criticas
• Tempo de trinamento longo
• Dificuldade para se entender a função aproximada (pesos)
• Incorporação de conhecimento do domínio não trivial
Memórias associativas (Redes de Kohonen)

Agrupamento de padrões com características comuns
• a rede identifica características comuns ao longo do domínio dos
padrões de entrada

Mapa topográfico de características
• Quantização vetorial (compressão de dados)
• Relações de vizinhança preservadas
• Representação de espaços N-Dimensionais em 2-D
Memórias associativas
Estado
/Saída
Processamento em 3 passos:
1. excitação vertical global
2. seleção do neurônio mais
excitado
3. excitação horizontal local ao
redor desse neurônio com
função de chapéu mexicano
Entrada


Camada de saída = camada de estados = grade 2-D
Camadas de entrada e saída totalmente conectadas
Memórias associativas:
algoritmo de aprendizagem

Inicializa a rede:
• define pesos iniciais (podem ser aleatórios), raio da vizinhança,
taxa de aprendizagem e taxa de redução da vizinhança
Apresenta todos os exemplos N vezes
 A cada iteração:

• para cada exemplo




apresenta o exemplo na camada de entrada
calcula a distância euclidiana do vetor dj de entrada a cada neurônio j
de saída
seleciona o neurônio nj* de menor distância dj*
atualiza os pesos do neurônio nj* e da sua vizinhança Nj*, segundo a
regra: wij (t+1) = wij (t) + (t)[xi (t)-wij (t)]
• reduz a vizinhança e a taxa de aprendizagem (convergência)
Memória associativas: exemplo
T=0
T=25
T=10.000
T=500
T = iteração
Algoritmos Genéticos
São técnicas de busca e otimização.
 É a metáfora da teoria da evolução das espécies
iniciada pelo Fisiologista e Naturalista inglês Charles
Darwin.
 Desenvolvido por John Holland (1975) e seus alunos.
 Popularizado por David Goldberg (1989).

Teoria da Evolução

1859 - Charles Darwin publica o livro “A
Origem das Espécies”:
.
Charles
Darwin
“As espécies evoluem pelo
principio da seleção
natural e sobrevivência do
mais apto.”
Teoria da Evolução

• Pai da genética.
.
Gregor
Mendel
1865- Gregor Mendel apresenta
experimentos do cruzamento genético de
ervilhas.

A Teoria da Evolução começou a partir
da conceituação integrada da seleção
natural com a Genética.
Otimização

É a busca da melhor solução para um dado problema.

As técnicas de otimização, geralmente, apresentam:
• Consiste em tentar vários soluções e usar a informação
obtida para conseguir soluções cada vez melhores.
 Espaço de busca: onde estão todas as possíveis soluções
do problema;
• Função objetivo: utilizada para avaliar as soluções
produzidas, associando a cada uma delas uma nota.
Características dos
Algoritmos Genéticos
É um algoritmo estocástico (não é determinístico).
 Trabalha com uma população de soluções
simultaneamente.
 Utiliza apenas informações de custo e recompensa.
Não requer nenhuma outra informação auxiliar
 São fáceis de serem implementados em
computadores.
 Adaptam-se bem a computadores paralelos.
 São facilmente hibridizados com outras técnicas.
 Funcionam com parâmetros contínuos ou discretos.

Algoritmos Genéticos
(Conceitos Básicos)
AG manipula uma população de indivíduos.
 Individuos são possíveis soluções do problema.



Os indivíduos são combinados (crossover) uns com os
outros, produzindo filhos que podem sofrer ou não
mutação.
As populações evoluem através de sucessivas gerações
até encontrar a solução ótima.
Aplicações
Em problemas díficeis de otimização, quando não
existe nenhuma outra técnica especifica para
resolver o problema.
 Otimização de funções numéricas em geral
 Otimização combinatória

•
•
•

Problema do caixeiro viajante
Problema de empacotamento
Alocação de recursos (job shop schedulling)
Aprendizado de Máquina
Algoritmo Genético Tradicional
1. Gerar a população inicial.
2. Avaliar cada indivíduo da população.
3. Enquanto critério de parada não for satisfeito faça
3.1 Selecionar os indivíduos mais aptos.
3.2 Criar novos indivíduos aplicando os
operadores crossover e mutação.
3.3 Armazenar os novos indivíduos em uma
nova população.
3.4 Avaliar cada cromossomo da nova
população.
Support Vector Machines



Support vector machines usa modelos lineares para
implementar fronteiras de classes não lineares
Como? Transformando o espaço de instancias em um novo
espaço via uma aplicação não linear
Um modelo linear construido no novo espaço pode
representar uma fronteira de decisão não linear no
espaço original
Support Vector Machines
Support vector machines são algoritmos para a
aprendizagem de classificadores lineares
 Eles são resistentes ao hiper-ajustamento (overfitting)
porque eles aprendem uma superficie de decisão linear
específica: o hiper-plano marginal máximo

• O hiperplano marginal maximo é aquele que fornece a maior
separação entre as classes

Eles são rápidos no caso não linear
• Eles empregam uma astucia matemática para evitar a criação de
“pseudo-atributos”
• O espaço não linear é criado implicitamente
Hiper-plano marginal maximo
Vetor Suporte
Vetor Suporte
As instâncias mais próximas do hiper-plano marginal
máximo (aquelas de menor distancia em relação a ele) são
chamadas support vector
 Os vetores suport definem o hiper-plano marginal
máximo

• Todas as outras instâncias podem ser eliminadas sem mudar a
posição e a orientação do hiper-plano

Isso significa que o hiper-plano
pode ser escrito como
z b
z  w0  w1 x1  w2 x2
 y a(i)  a
i i
i é vetor suporte
SVMs não lineares
“pseudo atributos” representam combinações de
atributos
 Overfitting não constitui um problema porque o hiperplano marginal máximo é estável



Usualmente existem poucos vetores suporte em relação ao
tamanho do conjunto de treinamento
Complexidade no tempo pode ser um problema
 Cada vez que o dot product é calculado é necessário
passar pelos “pseudo atributos”
SVMs não lineares
Pode-se evitar o cálculo dos “pseudo atributos”
 Pode-se calcular o dot product antes de aplicar a
transformação não linear, no conjunto de atributos
originais
z  b   i yi a(i )  a
i é vetor suporte
 Exemplo. Em vez de calcular

z b
 y a(i)  a 
n
i i
i é vetor suporte
pode-se calcular
n é o numero de fatores na transformação
 Isso corresponde a mapear em um espaço de instâncias
gerado pelo produto de n atributos
 Comece com n=1 (modelo linear) e incremente ate que o
erro estimado cesse de diminuir
Aplicações
Visão computacional: identificação facial
 Superior as outras abordagens
 Reconhecimento de caracteres
 Comparável as melhores alternativas
 Bioinformática: previsão de estrutura secundária de
proteínas
 Classificação textual
 Pode ser modificado para lidar com problemas de
previsão de descritores numéricos

Tipos de Aprendizagem I
(pelo grau de feedback)

Supervisionada: um ”professor“ diz quanto a resposta
dada pelo sistema se aproxima da resposta desejada.
(e. g. nota de um aluno numa prova)

Por Reforço: um ”professor“ diz apenas se a resposta
dada pelo sistema está certa ou errada.
(e. g. punição/recompensa no treinamento de animais)

Não-Supervisionada: o sistema tenta se auto-organizar
baseado nas similaridades entre os exemplos a ele apresentados.
(e. g. agrupamento de clientes)
Tipos de Aprendizagem II
(pelo grau de feedback)

Supervisionada:
• Conjunto de treinamento s = {(x1, f(x1)), (x2, f(x2)),..., (xn, f(xn))}
• Convergência rápida

Por Reforço:
• Conjunto de treinamento s = {(x1, sgn[f(x1)] ), (x2, sgn[f(x2)] ),...,
(xn, sgn[f(xn)] )}
• Convergência média

Não-Supervisionada:
• Conjunto de treinamento s = {(x1, ), (x2, ),..., (xn, )}
• Convergência lenta
Controle da aprendizagem
Aprende depois age ou aprende agindo (treinos x jogos)
 Agir sempre otimamente x aprender novas habilidades
 Busca de hipótese:

• incremental (exemplos apresentado ao poucos)
ou não (todos de uma vez)
• iterativa (exemplos re-apresentados em várias épocas) ou não
(uma apresentação de cada exemplo basta)
• top-down (refina hipótese geral para cobrir exemplos) ou
bottom-up (generaliza exemplos para abstrair hipótese) ou
bi-direcional
• gulosa (generaliza exemplos assim que encontrados) ou
preguiçosa (não generaliza exemplos com antecedência, apenas os
indexa para os adaptar ao receber novas consultas parecidas)
• global (aproxima função completa) ou
local (aproxima-la por partes)
Representação do conhecimento

Função matemática:
• domínio e escopo: {0,1}, Z, R
• monotonia, continuidade
• polinomial, exponencial, logarítmica

Lógica:
• proposicional (ordem 0), de atributos (ordem 0+)
• de Horn ou dos predicados (ordem 1)
• exóticas (ordem superior, temporal, modal, etc)
Distribuição de probabilidades
 Outros, ex.:

• Pesos em redes conexionistas,
• Representações orientada a objetos,
• Árvores de decisão, etc...
Conhecimento prévio

Aprendizagem sem conhecimento prévio:
• dados (exemplos)  conhecimento

Aprendizagem com conhecimento prévio:
• dados x conhecimento prévio  conhecimento

Métodos de aprendizagem que permitem usar
conhecimento prévio em entrada:
• re-aproveitam de conhecimento:


adquirido com especialistas humanos
aprendido durante passos anteriores de KDD
• para aprendem a partir de muito menos dados
• Exemplos, conhecimento prévio e conhecimento aprendido pode
ser representados no mesmo formalismo?
Viés

Conhecimento prévio:
• conhecimento do domínio da aplicação inteligente
• ex, futebol de robôs, bolsa de valor, meteorologia, etc.
• no mesmo formalismo do que o conhecimento a aprender

Viés:
• meta-conhecimento prévio
• sobre a forma do conhecimento a aprender a partir dos dados,
ex.,






classe de função a aproximar (linear, polinomial, ...)
classe de função medindo o erro da aproximação (médio quadrado, …)
dimensionalidade do espaço de hipótese
distribuição probabilista dos pontos nesse espaço (normal, poisson, ..)
restrições lexicais e sintática da linguagem de representação do
conhecimento a aprender (ex, número de premissa ou conclusões de
regras, numero de grupos classificando exemplos, …)
Aprendizagem sem viés não tem poder de generalização !