View
69
Download
1
Category
Preview:
Citation preview
Aprendizado de Máquina
Cristiane Neri Nobre
Aprendizado de Máquina
Construção de programas de computador que melhoram seu desempenho por meio de experiência
Um programa aprende a partir da experiência E, em relação a uma classe de tarefas T, com me-dida de desempenho P, se seu desempenho em T, medido por P, melhora com E
Mitchell, 1997
AM – Conceitos Básicos
Aprendizado Supervisionado
Indutor recebe conjunto de exemplos na forma (entrada, rótulo_desejado)
Técnicas: Redes Neurais do tipo Multilayer Perceptron Máquinas de Vetores Suporte Algoritmos Genéticos Árvores de Decisão
AM – Conceitos Básicos
Aprendizado Não-supervisionado
Indutor recebe apenas atributos de entrada
Encontrar aglomerados
Técnicas: Redes Neurais do tipo mapas auto-organizáveis Algoritmo k-médias
AM – Conceitos Básicos
Exemplo (padrão, instância) Amostra de tecido de paciente
Característica (atributo, variável) Nível de expressão de um gene do tecido
Vetor de características Vetor com expressões de m genes do
tecido Classe
Presença ou ausência de câncer
AM – Conceitos Básicos
g1 g2 gj gN-1gN
Padrão 1Padrão 2Padrão 3
Padrão i
Padrão m
Característica
Câncer
Normal
Câncer
Classe
AM – Conceitos Básicos
Conjunto de exemplos (conj. de dados) Conjunto de treinamento Conjunto de teste
Acurácia (taxa de erro) Falsos positivos e falsos negativos Overfitting (super ajustamento)
Árvores de Decisão – ADs
Forma mais simples: Lista de perguntas respostas “sim”
ou “não” Hierarquicamente arranjadas Levam a uma decisão
Estrutura da árvore determinada por meio de aprendizado
ADs
Contém códon de parada?
Não
Não-gene
Sim
Códon de parada downstream?
Tamanho da seqüência > limiar?
Não-gene Gene
Não-gene
Não Sim
Não Sim
ADs
Contém códon de parada?
Não
Não-gene
Sim
Códon de parada downstream?
Não-gene
Não Sim
Nós internos correspondem a testes
Ramos são resultados dos testes
Folhas fornecem classificações
ADs
Contém códon de parada?
Não
Não-gene
Sim
Códon de parada downstream?
Tamanho da seqüência > limiar?
Não-gene Gene
Não-gene
Não Sim
Não Sim
Novo padrão: Contém códon de parada dowstream e tamanho da seqüência é menor que limiar
ADs – treinamento
Treinamento AD encontra regras que recursivamente
bifurcam o conjunto de dados Sub-conjuntos homogêneos intra sub-conjuntos e Sub-conjuntos heterogêneos inter sub-conjuntos
Conteúdo dos sub-conjuntos pode ser descrito por um conjunto de regras
ADs – treinamento
Day Outlook Temperature Humidity Wind PlayTennisD1 Sunny Hot High Weak NoD2 Sunny Hot High Strong No
D3 Overcast Hot High Weak YesD4 Rain Mild High Weak YesD5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong NoD7 Overcast Cool Normal Strong YesD8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak YesD10 Rain Mild Normal Weak YesD11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong YesD13 Overcast Hot Normal Weak YesD14 Rain Mild High Strong No
Considere a tarefa de aprendizado representada pelos exemplos de treinamento na tabela abaixo, em que o objetivo é prever o atributo PlayTenis baseando-se nos outros atributos. Construa uma AD.
ADs – treinamento
Teste Exemplo Outlook Temperature Humidity Wind Play? If outlook=sunny D1
D2 D8 D9 D11
Sunny Sunny Sunny Sunny Sunny
Hot Hot Mild Cool Mild
High High High Normal Normal
Weak Strong Weak Weak Strong
No No No Yes Yes
If outlook=overcast
D3 D7 D12 D13
Overcast Overcast Overcast Overcast
Hot Cold Mild Hot
High Normal High Normal
Weak Strong Strong Weak
Yes Yes Yes Yes
If outlook=rain D4 D5 D6 D10 D14
Rain Rain Rain Rain Rain
Mild Cool Cool Mild Mild
High Normal Normal Normal High
Weak Weak Strong Weak Strong
Yes Yes No Yes No
ADs – treinamento
Teste Exemplo Outlook Temperature Humidity Wind Play? If outlook=sunny and humidity=high
D1 D2 D8
Sunny Sunny Sunny
Hot Hot Mild
High High High
Weak Strong Weak
No No No
If outlook=sunny and humidity=nomal
D9 D11
Sunny Sunny
Cool Mild
Normal Normal
Weak Strong
Yes Yes
If outlook=overcast
D3 D7 D12 D13
Overcast Overcast Overcast Overcast
Hot Cold Mild Hot
High Normal High Normal
Weak Strong Strong Weak
Yes Yes Yes Yes
If outlook=rain and wind=strong
D6 D14
Rain Rain
Cool Mild
Normal High
Strong Strong
No No
If outlook=rain and wind=weak
D4 D5 D10
Rain Rain Rain
Mild Cool Mild
High Normal Normal
Weak Weak Weak
Yes Yes Yes
ADs - conclusão
Vantagens: Estrutura de fácil manipulação Produzem modelos que podem ser facilmente
interpretados por humanos
Desvantagens: Pouca robustez a dados de grande dimensão Acurácia afetada por atributos pouco relevantes Dificuldade em lidar com dados contínuos
Algumas Ferramentas para extração de ADs
Weka – http://www.cs.waikato.ac.nz/ml/weka/
Trepan - poderá ser adquirido através de um e-mail enviado à Mark Craven (craven@biostat.wisc.edu), autor do Trepan.
C4.5 - HAMILTON, H.; GURAK, E.; FINDLATER, L.; OLIVE, W.
Machine learning/decision trees - C4.5 tutorial. Disponível em: <http://www.cbi.msstate.edu/faculty/dvance/ml/ C4_5%20Tutorial.htm>. Acesso em: 03 jan. 2002.
ID3, C5.0, dentre outros...
Redes Neurais Artificiais
O que são Redes Neurais Artificiais?
Redes Neurais Artificiais (RNA) são modelos de computação com propriedades particulares:
Capacidade de adaptação (aprendizado)
Generalizar
O que são RNAs?
Uma rede neural é um processador maciçamente paralelamente distribuído constituído de unidades de processamento simples, que têm a propensão natural para armazenar conhecimento experimental e torná-lo disponível para o uso. Ela se assemelha ao cérebro em dois aspectos:
1. O conhecimento é adquirido pela rede a partir de seu ambiente através de um processo de aprendizagem
2. Forças de conexão entre neurônios, conhecidas como pesos sinápticos, são utilizadas para armazenar o conhecimento adquirido.
Simon Haykin
O que são RNAs?
RNA: estruturas distribuídas formadas por grande número de unidades de processamento conectadas entre si.
Multi-disciplinaridade: Ciência da Computação, Matemática, Física, Engenharias, Psicologia, Biologia, Lingüística, Filosofia, etc.
Modelos inspirados no cérebro humano Compostas por várias unidades deprocessamento (“neurônios”)
Interligadas por um grande número deconexões (“sinapses”)
Eficientes onde métodos tradicionais têm se mostrado inadequados
Características das RNAs
Aprendem através de exemplos Adaptabilidade Capacidade de generalização Tolerância a falhas
Potenciais áreas de aplicação das RNAs Classificação de padrões Clustering/categorização Aproximação de funções
Previsão Otimização Controle Mineração de dados etc...
Breve histórico
Década de 40 : O começo
(1943) McCulloch & Pitts Modelo artificial de um neurônio
biológico (1949) Hebb desenvolve algoritmo
para treinar RNA (aprendizado Hebbiano) Se dois neurônios estão
simultaneamente ativos, a conexão entre eles deve ser reforçada
1950-1960: Anos de euforia
(1958) Von Neumann mostra interesse em modelagem do cérebro (RNA)
The Computer and the Brain, Yale University Press
(1958) Rosenblatt implementa primeira RNA, a rede Perceptron
Ajuste iterativo de pesos Prova teorema da convergência
Década de 70: Pouca atividade
(1969) Minsky & Papert analisam Perceptron e mostram suas limitações
Não poderiam aprender a resolver problemas simples como o OU-exclusivo
Causou grande repercussão
Década de 70: Pouca atividade
(1971) Aleksander propõe redes Booleanas
(1972) Kohonen e Anderson trabalham com RNAs associativas
(1975) Grossberg desenvolve a Teoria da Ressonância Adaptiva (redes ART)
Década de 80: A segundaonda
(1982) Hopfield mostra que Redes Neurais podem ser tratadas como sistemas dinâmicos
(1986) Hinton, Rumelhart e Williams, propõem algoritmo de aprendizagem para redes multi-camadas
Tendências atuais
• Controle de generalização
• Sistemas neurais híbridos
Conceitos básicos
Estrutura geral das RNAs:
Unidades de processamento ni (nós) Conexões wij
Saída Topologia
• Modelo Matemático de um Neurônio
Conceitos FundamentaisConceitos Fundamentais
O neurônio de McCulloch-Pitts
Neurônio de McCulloch-Pitts
Exercício
Solucão
Aprendizado
Capacidade de aprender a partir de seuambiente e melhorar sua performance com otempo
Parâmetros livres de uma RNA são adaptados através de estímulos fornecidos pelo ambiente Processo iterativo de ajustes aplicado às
sinapses A RNA deve saber mais sobre seu ambiente
após cada iteração
RNA deve produzir para cada conjunto de entradas apresentado o conjunto de saídas adequado.
Forma geral para o ajuste de pesos é: wik(n+1) = wik(n) + wik(n)
Mecanismos de aprendizado
Modificação de pesos (wij(n)) associados às conexões
Acréscimo e/ou eliminação de conexões e/ou nodos
Aprendizado supervisionado
Professor externo
Possui conhecimento sobre ambiente Representado por conjunto de pares (x, d)
Parâmetros da rede são ajustados por (x,d) Rede procura repetir comportamento do
professor
Aprendizado por reforço
Crítico externo
Processo de tentativa e erro Procura maximizar sinal de reforço
Se ação tomada por sistema é seguida por estado satisfatório, ação é fortalecida, caso contrário, ação é enfraquecida
Aprendizado por reforço
Tipos de reforço
Positivo = recompensa Negativo = punição Nulo
Aprendizado nãosupervisionado
Não está associado a crítico ou professor externo
Extração de características estatisticamente relevantes dos dados
Perceptron
Perceptron Simples
Perceptron - Características
O perceptron é usado para conjuntos de treinamento linearmente separáveis
Inclusão de tendência (“bias”) No algoritmo de aprendizagem do Perceptron busca-se
um vetor W que tenha projeção positiva (produto interno) com todos os exemplos positivos e projeção negativa com todos os exemplos negativos
A aprendizagem do perceptron sempre tem sucesso em tempo finito para um conjunto de treinamento finito e separável de exemplos de treinamento
p
jjj uWWS
10 .
Algoritmo do Perceptron1. Fazer W ser o vetor nulo.
2. Selecionar um exemplo de treinamento Ek (com a correspondente classificação Ck). Isto pode ser feito de maneira cíclica (em ordem) através dos exemplos de treinamento ou pegando um exemplo aleatoriamente.
3. Se W classifica Ek corretamente, isto é, se:
{W.Ek 0 e Ck = +1} ou se {W.Ek < 0 e Ck = -1} Então: não fazer nada. Senão Passo de alteração: Modificar W somando
ou subtraindo Ek de acordo com a saída correta ser +1 ou -1: W’ = W + CkEk.
4. Ir ao passo 1.
Perceptron - Conclusões
Para um conjunto finito de exemplos de treinamento E, com componentes inteiros (ou racionais), o algoritmo de aprendizagem do perceptron, em tempo finito: Produzirá um vetor peso que satisfaz todos os
exemplos de treinamento (se e somente se E é separável); ou
Abandonará e reutilizará um vetor peso (se e somente se E é não-separável).
Perceptron - Conclusões
Se um conjunto de exemplos de treinamento E é não-separável, então por definição não existe um vetor de pesos W que classifique corretamente todos os exemplos de treinamento em E utilizando o algoritmo de aprendizagem do perceptron. A alternativa mais natural é encontrar um vetor de pesos W* que classifique tantos exemplos de treinamento quanto possível de E. Tal conjunto de pesos é chamado de ótimo
Algoritmo Backpropagation - MLP
Resumo do algoritmo de treinamento:
1 - Apresentar vetor de entrada à camada de entrada da rede e propagá-lo até a camada de saída;
2 - Atualizar pesos das camadas de saída e escondida, propagando o erro de volta às entradas;
3 - para os nodos j da camada de saída, atualizar os pesos da seguinte forma:
Wij(n+1)=wji(n) + j(n)yi(n)
Onde j(n) equivale a:
j(n)=j(n)f’j(vj(n))
4 - Para os nodos j da camada escondida:
Wij(n+1)=wji(n) + j(n)yi(n)
Onde j(n) equivale a:
j(n) = f’j(vj(n)) k(n)wkj(n)
e k se refere aos nodos da camada de saída.
A atualização dos pesos é feita de forma individual para cada um dos vetores do conjunto de treinamento;
Para cada vetor de treinamento, o sinal deve ser propagado das entradas para as saídas para que o erro possa então propagar em sentido contrário e permitir o treinamento;
Algoritmo Backpropagation - Considerações
• Cada apresentação completa de todos os elementos do conjunto de treinamento e conseqüente ajuste de pesos é chamada epoch;
• É aconselhável randomizar a seqüência com que os vetores são apresentados à rede de uma epoch para a outra para acrescentar um componente estocástico ao treinamento e evitar ciclos limites indesejáveis na atualização dos pesos;
• Os pesos iniciais devem ser preferencialmente obtidos de uma distribuição uniforme (evita polarização)
• Reconhecimento de Caracter• Aproximador de Funções
ExemplosExemplos
Defina valor de ;
Repita
Para cada par {v, t}
Calcule a saída y apresentando v nas entradas;
Se y<>t então w(n+1) = w(n) + (t-y)v
Senão w(n+1) = w(n);
Fim
Fim para
Até erro < Tolerância
Exemplo - Algoritmo GeralExemplo - Algoritmo Geral
Padrões de EntradaPadrões de Entrada
Exemplo - Reconhecimento de CaracterExemplo - Reconhecimento de Caracter
Exemplo - Reconhecimento de CaracterExemplo - Reconhecimento de Caracter
Variações nos padrões de EntradaVariações nos padrões de Entrada
Exemplo - Reconhecimento de CaracterExemplo - Reconhecimento de Caracter
Variações nos padrões de entradaVariações nos padrões de entrada
Parâmetros: ta=0.1, num_ep=3000, tol=0.0001)Parâmetros: ta=0.1, num_ep=3000, tol=0.0001)
Exemplo - Aproximador de Exemplo - Aproximador de FunçõesFunções
Exemplo - Aproximador de FunçõesExemplo - Aproximador de Funções
Gráfico de erroGráfico de erro
http://www.nada.kth.se/~orre/snns-manual/
Matlab
Etc, etc
Ferramentas
Recommended