INTELIGENCIA ARTIFICIAL

Prévia do material em texto

Aula 1 - Introdução e Conceitos de Inteligência Artificial
DEFINIÇÃO DE INTELIGÊNCIA ARTIFICIAL
“O excitante novo esforço para fazer o computador pensar ... máquinas com mentes, no sentido literal e pleno” (Haugeland)
“O estudo de faculdades mentais através do uso de modelos computacionais” (Charniak and McDermott)
“A automação de atividades que associamos ao pensamento humano, atividades tais como tomadas de decisão, resolução de problemas, aprendizado ... ” (Bellman)
“O estudo das computações que tornam possível perceber, raciocinar e agir” (Winston)
“A arte de criar máquinas que executem funções que exijam inteligência quando executadas por pessoas” (Kurzweil)
“O estudo de como fazer computadores realizarem coisas nas quais, no momento, as pessoas são melhores” (Rich and Knight)
EVOLUÇÃO HISTÓRICA DA INTELIGÊNCIA ARTIFICIAL
· [1883] Babbage Proc. Mec.
· [1889]	Hollerith Calc. Mec.
· [1935] Konrad Suze Calc. Eletrôn.
· [1943] McCullock-Pitts Mod. Neurônio.
· [1946] Von Newman Comp. Moderno.
· [1956] J. McCarthy Intel. Artificial
· [1958] Allen Newell Sist. Espec.
· [60-70] Fuzzy, Alg. Genétic.
· [80-90] Redes Neurais, Bio-inspirados
· [2000] Sistemas Híbridos
INTELIGÊNCIA X CONHECIMENTO
O conhecimento: 
· É que possibilita possibilita a inteligência 
· É volumoso
· É difícil de caracterizar
· Está em constante mudança
· É organizado (diferente dos dados)
· É individual (interpretação)
PROBLEMAS AO LIDAR COM O CONHECIMENTO
Como representar o conhecimento? 
· Como determinar se o conhecimento é suficiente?
· Como realizar inferências automaticamente? 
· Como tratar situações onde o conhecimento é incompleto, incorreto, impreciso ou conflitante?
· Como agregar conhecimento ao longo do tempo?
ESTRUTURA ORGANIZACIONAL DOS MODELOS DE IA
Modelos Simbolistas 
· Grafos de Estados
· Sistemas Especialistas 
· Lógica Nebulosa
Modelos Não Simbolistas
· Sistemas Evolucionários
· Redes Neurais
MODELOS SIMBOLISTAS
· Lidam com conhecimento explícito e representado simbolicamente
· Examinam o seu raciocínio
· Podem justificar conclusões
· Atuam mesmo com conhecimento incompleto ou impreciso
· Aplicações: jogos, telemarketing, concessão de crédito, gestão de carteira, tutoria, seleção, orçamento, planejamento estratégico, alocação de recursos, diagnósticos, psico-testes.
MODELOS NÃO SIMBOLISTAS
· Lidam com conhecimento não simbolicamente representado 
· Bio-inspirados (cérebro, comportamento animal, genética)
· Processam a informação de forma paralela e distribuída 
· Aprendem com treinamento
· Generalizam conhecimento aprendido
· Em modelos conexionistasnão justificam decisões
· Aplicações: aplicações gerais de classificação, agrupamento, previsão e otimização.
MODELOS DE INTELIGÊNCIA ARTIFICIAL
· Buscas em grafos de estados;
· Sistemas de regras (Sistemas Especialistas);
· Sistemas Nebulosos (Lógica Fuzzy)
· Modelos evolucionários (Algoritmos Genéticos)
· Modelos Conexionistas (Redes Nerais)
BUSCAS EM GRAFOS DE ESTADOS
· Modelam os sistemas de produção
· Modelam os problemas como sucessões de estados possíveis
· Estabelecem estratégias de busca por soluções 
· Justificam decisões
· Aplicações em problemas gerais de roteamento, sequenciamento de ações, estratégia de negócios, robótica e jogos de uma forma geral
SISTEMAS ESPECIALISTAS
· Expressam o conhecimento em regras de produção
· Modelam o conhecimento de um ou mais especialistas
· Justificam soluções
· Podem agregar conhecimento
· Atuam mesmo com conhecimento incompleto ou conflitante
· Aplicações em sistemas específicos de engenharia, finanças, vendas, tutoria e treinamento, manutenção, telemarketing, sistemas da área médica e planejamento estratégico.
SISTEMAS NEBULOSOS
· Modelam os modos imprecisos do raciocínio aproximado
· Trabalham com proposições imprecisas em linguagem natural
· Realizam inferências com operadores e modelos lógicos
· Aplicações em controle de aeronaves, operações do metrô, transmissão automática de veículos, controle de elevadores, análise fnanceira, ajuste da imagem em câmeras de vídeo, estabilizador de imagens de filmadoras, controle de máquinas de lavar e sistemas de ar condicionado.
ALGORITMOS GENÉTICOS
· São algoritmos de otimização global
· Inspirados nos mecanismos da genética
· Empregam uma estratégia de busca paralela e estruturada
· Criam soluções que têm tendência à melhoria constante
· Algumas aplicações: problemas gerais de otimização incluindo roteamento, controle de sistemas dinâmicos, parametrização e topologia de outros modelos de IA
REDES NEURAIS
· Lidam com conhecimento não simbolicamente representado 
· São inspirados no comportamento do cérebro
· Processam a informação de forma paralela e distribuída 
· Aprendem com treinamento e generalizam conhecimento
· Não justificam decisões
· Aplicações em reconhecimento de som e imagem, classificação de padrões, previsão de índices financeiros e agrupamento de dados.
SISTEMAS DE PRODUÇÃO
· Lidam com problemas que devem possuir:
· Situações que representam os estados do problema
· Operações conhecidas que causam mudanças de estados
· Um estado inicial e estado(s) final(is) desejado(s)
· Ex: jogos de tabuleiro, problemas gerais de roteamento
REPRESENTAÇÃO DOS SISTEMAS DE PRODUÇÃO
representados com grafos onde:
· Estados são vértices (A,B,C)
· Operações são arestas (x,y)
· Estados inicial (A) e final (C) são marcados
EXEMPLO DE PROBLEMA
Dois jarros opacos têm capacidade para 4 litros (jarro A) e 3 litros (jarro B). Queremos colocar exatamente dois litros no jarro A. Para tanto, podemos: 
· encher totalmente um dos jarros;
· esvaziar totalmente um deles; ou,
· passar o líquido de um para outro.
MODELANDO O PROBLEMA DOS JARROS
Representação dos estados:
· Par (x,y) indica conteúdos atuais
Operações possíveis:
· R1 – encher o jarro A
· R2 – encher o jarro B
· R3 – esvaziar o jarro A
· R4 – esvaziar o jarro B
· R5 – passar do jarro A para o jarro B (até completar) 
· R6 – passar do jarro B para o jarro A (até completar)
ARVORE DE BUSCA PARA O PROBLEMA DOS JARROS
ESTRATÉGIA DE BUSCA
Uma estratégia é uma forma sistemática de gerar novos estados, em busca da solução. Devemos:
· Obter uma sequência de operações que levem a um estado final; 
· Evitar a repetição de estados em um ramo da árvore (círculos);
Algoritmo geral de uma estratégia:
· Estado atual ← estado inicial
· Enquanto não for atingido um estado final:
· Selecione um operador R aplicável ao estado atual
· Novo estado ← R (estado atual)
(0,0)R1(4,0)R5 (1,3)R4(1,0)R5(0,1)R1(4,1)R5(2,3)
· Será esta a única solução?
· Havendo outras, será esta a melhor solução?
· Como podem ser obtidas esta ou outras soluções?
· Como podemos avaliar a qualidade de uma solução?
· Forneça outra solução para o problema.
· Pesquise na Internet outros problemas semelhantes.
Aula 2 - Estratégias de buscas em grafos com e sem custos
O QUE É UMA ESTRATÉGIA DE BUSCA
É uma forma sistemática de percorrer um grafo de estados à procura de um estado final. Cada estratégia é caracterizada, portanto, por uma sequência de aplicação de operadores que levam o problema do estado inicial a um estado final. 
PRINCIPAIS ESTRATÉGIAS DE BUSCA
Busca em profundidade
· Busca irevogável
· Busca backtracking
Busca em largura
· Buscas com custos
· Baseadas somente nos custos
· Baseadas em heurísticas (estimativas)
BUSCA EM PROFUNDIDADE
Algoritmo:
1. Escolher um dos operadores possíveis
2. Aplicar o operador e mudar para um novo estado
3. Se o novo estado não é final, retornar ao passo 1
Outras escolhas “erradas” de operadores. também causam fracasso.
busca em profundidade é chamada de irrevogável, pois não garante que a solução será encontrada, visto que, pode acabar parando em um estado que não tem operadores para fazer a transição.
BUSCA EM PROFUNDIDADE (BACKTRACKING)
A busca backtraking garante que encontra a solução, caso haja. 
A busca backtracking permite que ao chegarmos em um estado sem transição, podemos voltar ao estado anterior e escolher outras operações.
BUSCA EM LARGURA
Algoritmo:
1. Enquanto houver estados nãoinvestigados no nível atual
a. Escolher um dos estados não investigados do nível atual
b. Aplicar todos os operadores possíveis ao estado escolhido
c. Se não foi atingido um estado final, retornar ao passo I
2. Alterar nível atual para próximo nível e retornar ao passo 1
Se houver solução, esta será garantidamente encontrada
Se não houver solução, a busca indicará que todos os caminhos foram investigados e não há solução
Se houver mais de uma solução, a busca em largura encontrará primeiramente a solução que demanda menos passos (a mais próxima da raiz)
BUSCAS COM CUSTOS
A maioria do problemas reais possui custos distintos para escolha de cada operador
Podemos sintetizar essa situação em um problema de roteamento que consiste em partir de uma cidade de origem e chegar a uma cidade de destino, em um mapa que possui ligações entre as cidades com distâncias conhecidas (custos)
Queremos encontrar o caminho para ir da origem ao destino ao menor custo possível.
Vamos examinar duas estratégias:
· Busca gulosa (vizinho mais próximo)
· Busca ordenada (algoritmo de Dijkstra) 
Estado inicial: A, Estado final: E
Caminhos possíveis:
· ABCE – custo: 3+5+8 = 16
· ACDE – custo: 4+7+4 = 15
· ACE – custo: 4+8 = 12
· ADE – custo: 6+4 = 10
BUSCA GULOSA (VIZINHO MAIS PRÓXIMO)
Algoritmo:
1. escolha o operador (caminho) que apresente o menor custo e leve a um vizinho ainda não visitado 
2. Se o novo estado não for o estado final, retorne ao passo 1
Seguindo esta estratégia, a rota escolhida seria ABCDE, o que representaria um custo de 3+5+7+4=19 (o pior de todos)
Essa estratégia:
· não garante encontrar um caminho
· Encontrando um caminho, não garante ser o de menor custo
BUSCA ORDENADA (ALGORITMO DE DIJSKSTRA)
1. Escolha o nó aberto (que ainda não teve seus caminhos investigados) de menor custo total e expanda todos os possíveis caminhos desse nó 
2. Marque o nó que teve os seus caminhos expandidos como nó fechado
3. Calcule o custo total dos novos nós como o custo do nó anterior mais o custo da ligação entre os nós 
4. Abandone os nós com custo total maior que os nós equivalentes encontrados em outros ramos da árvore
5. Caso haja algum nó aberto da árvore de busca com custo total menor que o custo do nó final encontrado, retorne ao passo 1 
Vamos estabelecer algumas simbologias antes de resolver o problema ao lado:
· A → nó aberto
· (A) → nó fechado
· A (3) → custo total do nó
· A TRACEJADO → nó abandonado por ter sido encontrado outro nó igual com menor custo total 
BUSCA HEURÍSTICA
· A busca ordenada encontra garantidamente o menor caminho 
· Entretanto, a busca ordenada pode ter que investigar muitos caminhos para encontrar o melhor caminho
· Podemos usar uma estimativa sobre as perspectivas futuras de cada opção para a escolher o melhor caminho
· Essa estimativa é a heurística (uma aproximação da realidade descoberta de alguma forma) que podemos então considerar 
· Se levarmos em conta apenas as estimativas, teremos novamente uma busca gulosa que pode não encontrar o menor caminho
· Se combinarmos as estimativas com os custos reais dos caminhos, teremos então uma busca chamada de A* 
BUSCA A*
Para que a busca A* funcione e também encontre o menor caminho (como a busca ordenada), apenas é necessário que:
1. Haja uma estimativa para cada nó N aberto, que equivalha ao custo estimado para ir de N até o final e que é chamada de h(N) 
2. Cada h(N) não seja maior que o custo real para ir de N até o final, ou seja, as estimativas devem ser otimistas 
O algoritmo A* é igual à busca ordenada, exceto pelo fato que o custo total considerado nas decisões é o custo para chegar até aquele nó (o mesmo da busca ordenada) mais o custo estimado para ir daquele nó até o final.
Ou seja, C(N) = r(N) + h(N), onde:
· C(N) → custo total para o nó N
· r(N) → custo real para chegar até o nó N
· h(N) → custo heurístico estimado para ir de N até final 
A forma de estimar o custo h(N) depende de cada problema
Em problemas de roteamento, podemos usar como estimativa a distância entre os pontos, que será sempre, em uma geometria Euclidiana, necessariamente otimista (“ a menor distância entre dois ponto é uma reta”)
Em outros tipos de problemas devemos encontrar uma forma qualquer de estabelecer estimativas otimistas 
Aula 3 - Regras de Produção e Sistemas Especialistas
LIMITAÇÕES DAS REPRESENTAÇÕES POR GRAFOS DE ESTADOS
Nos problemas com representações de grafos, todo o conhecimento está disponível (operadores e estados possíveis, estado inicial e estados finais).
Ocorre que muitos problemas são incompletos e precisam de mecanismos de inferência para gerar novos conhecimentos a partir dos existentes ou fazer perguntas aos usuários, ler sensores ou consultar bancos de dados.
REGRAS DE PRODUÇÃO E SISTEMAS ESPECIALISTAS
A representação do conhecimento que estudaremos nesta aula são os sistemas de Regras de Produção (com os quais se constroem aplicações chamadas de  Sistemas Especialistas). 
Esta técnica lida com duas entidades: 
· os fatos (ou seja, as verdades ou informações que possuímos sobre um determinado contexto) e
· a representação dos conhecimentos (que nesta técnica é feita por meio de regras de produção).
REGRAS DE PRODUÇÃO
Uma regra é formada por uma premissa simples ou composta (usando operadores lógicos) e uma ou mais conclusões que são acionadas quando as premissas são verdadeiras. As premissas/conclusões são também chamadas de situação/ação ou de antecedente/consequente das regras.
	Se PREMISSA Então CONCLUSÃO
EXEMPLOS:
· Se a temperatura é maior que 38 graus, então o paciente tem febre.
· Se o paciente tem febre há mais de 3 dias, então o paciente tem uma infecção.
· Se há tensão na entrada da fonte e não há tensão na saída da fonte, então o transformador está queimado
LÓGICA E ESTRATÉGIA
Os sistemas baseados em regras usam a forma lógica de argumento (silogismo) Modus Ponens.
Dado que o fato A é verdadeiro e que a implicação A→B é verdadeira, conclui-se que o fato B é verdadeiro.
Além da representação é necessário empregar alguma técnica de busca por fatos de interesse e por regras que possam gerar esses fatos, o que é conhecido como estratégia de busca.
ESTRATÉGIAS DE BUSCA
A ideia é lidar com os fatos e regras que se tem para encontrar e os fatos que se deseja descobrir.
Para escolher quais regras examinar e ativar, podemos empregar duas abordagens básicas:
· Estratégia dirigida a dados (forward chain)
· Estratégia dirigida a objetivos (backward chain).
ESTRATÉGIA DIRIGIDA A DADOS
Aciona-se todas as regras que possam ser acionadas a partir dos fatos (dados) conhecidos, esperando-se que os fatos de interesse possam ser concluídos em algum momento (em algum ciclo de acionamento das regras). 
A cada ciclo novos fatos são gerados e que pode provocar o acionamento de outras regras no ciclo seguinte.
A estratégia funciona se os fatos de interesse são inferidos por alguma regra ou fracassa se um ciclo se completa sem que novos fatos sejam inferidos.
ESTRATÉGIA DIRIGIDA A OBJETIVOS
Investiga-se as regras que possuam na conclusão os objetivos que procuramos. Caso o fato da premissa da regra seja desconhecido, esse será o novo objetivo e passamos a buscar uma regra que o contenha na conclusão.
 O objetivo original é provisoriamente abandonado e será retomado quando a premissa original tiver sido encontrada. 
O procedimento é recorrente, isto é, os objetivos vão sendo abandonados e retomados, em uma cadeia de busca para trás (backward chain).
EXEMPLO:
Conhecimentos gerados por um especialista: 
· Regra 1: Se a taxa de juros é baixa Então a bolsa de valores está em alta
· Regra 2: Se a taxa de juros é alta Então a bolsa de valores está em baixa
· Regra 3: Se a cotação do Dolar está baixa Então a taxa de juros é alta
· Regra 4: Se a cotação do Dolar está alta Então a taxa de juros é baixa
Considere também que conhecemos o seguinte fato:
Fato 1: a cotação do Dolar está baixa.
Queremos saber: "Qual a tendência da bolsa de valores?"
ESTRATÉGIA ORIENTADA A FATOS
AGREGANDO CONHECIMENTOE quando o conhecimento (regras + fatos) é insuficiente?
· Agregamos fatos de origem externa (fora do sistema)
· Forma fácil: fazer perguntas
No exemplo a seguir temos:
· Várias regras especialistas sobre FRUTAS
· NENHUM fato conhecido inicialmente
· Um objetivo a descobrir: qual é a FRUTA?
Vamos acompanhar a resolução passo-a-passo
ORIENTADO A OBJETIVOS
LIDANDO COM INCERTEZAS
Muitas respostas ou decisões estão ligadas a incertezas
Os sistemas de produção em geral lidam com incertezas usando um Fator de Confiança (FC) para regras e fatos
Os operadores podem manipular o FC da seguinte forma:
· Negação (Não) – o FC é complementado a 1
· Conjunção (E) – os FC são multiplicados 
· Disjunção (OU) – os FC são somados e do resultado se subtrai o produto dos FC
· Implicação (ENTÃO) – o FC da premissa é multiplicado pelo FC da regra 
· Se o mesmo fato possui diferente FC, aplicamos a conjunção
Ex: conhecemos os fatos A, C e E com FC=0,9 e as regras:
· R1: se A então B (FC=0,7)
· R2: se B e C então D (FC=1)
· R3: se D ou E então F (FC=0,4)
· R4: se F então G (FC=1)
Resolvendo:
· R1: FCA * FCRegra = FCB 0,9*0,7 = 0,63 = FCB
· R2: FCB*FCC = FCpremissa = 0,63*0,9=0,57 0,57*1=0,57=FCD
· R3: FCD+FCE - FCD*FCE = 0,57 + 0,9 – 0,57 x 0,9 = 0,95 0,95 x 0,4 = 0,36 = FCF
· R4: FCpremissa = FCF = 0,38 < 0,5 regra NÃO é acionada 
Situação: O carro da de Madame M foi furtado e os suspeitos são o mordomo e o genro da vítima.
Conhecemos as seguintes regras sobre furtos de carros:
Além das regras, a investigação produziu os seguintes fatos:
1. O carro do mordomo estava quebrado (ele precisava de transporte) CF=1
2. O carro do genro estava funcionando (não precisava de transporte) CF=1
3. As impressões digitais do mordomo estavam no carro de Madame M CF=1
4. As impressões digitais do genro de Madame M. não estavam no carro CF=1
5. As impressões digitais do mordomo não estavam na chave do carro CF=1
6. As impressões digitais do genro estavam na chave do carro CF=1
7. As chaves do carro de Madame M. foram deixadas no carro CF=1
8. O mordomo não gostava de Madame M. CF=0,6
9. O genro gostava de Madame M. CF=0,8
10. O mordomo estava assistindo TV quando o crime ocorreu CF=0.85
11. O genro estava dormindo quando o crime ocorreu CF=0,2
Vamos resolver o problema usando a estratégia orientada a objetivos
Podemos calcular a confiabilidade para qualquer coisa que queiramos descobrir (por ex.: se o mordomo é culpado, se o genro é culpado, se ambos são culpados, etc.)
Vamos, então, calcular a confiabilidade de o mordomo ser culpado.
Para tanto montaremos a tabela com as informações:
FERRAMENTAS PARA DESENVOLVER SISTEMAS ESPECIALISTAS
Existem ferramentas (procure na internet) para desenvolver e executar sistemas especialistas.
Tais ferramentas possuem:
· Motor de inferências – aplica a estratégia de busca;
· Base de conhecimentos - armazenar as regras de produção de uma área específica de aplicação;
· Base de dados - armazena os fatos conhecidos e/ou inferidos
USANDO FERRAMENTAS PARA DESENVOLVER UM SISTEMA ESPECIALISTA
· Nome: SINTA (ferramenta acadêmica)
· Desenvolvedor: LIA-UFC (http://www.lia.ufc.br)
· Vamos ver a execução de um exemplo fornecido com a ferramenta
· Procure artigos e exemplos em SINTA na internet
Aula 4 - Lógica Nebulosa (Fuzzy) e Sistemas Baseados em Regras Fuzzy
LIMITAÇÕES DAS REPRESENTAÇÕES NOS SISTEMAS ESPECIALISTAS
Os Sistemas de Produção tendem a ser muito extensos (muitas regras) para cobrir situações reais.
Também demandam especificação exata dos valores de cada variável, o que pode não ser viável em alguns casos.
Finalmente, apresentam respostas invariantes em situações onde claramente deveria haver uma proporcionalidade. Ex: Se temperatura < 120o então chama = 150o (F.C.=0,9) 
A saída será sempre 150 para qualquer entrada < 120.
LÓGICA NEBULOSA (FUZZY)
Lida com variáveis imprecisas para modelar o raciocínio
Ao invés da ambivalência (verdadeiro/falso) da lógica clássica, lida como o conceito de pertinência a um conjunto
Trabalha com operadores lógicos (E, OU, NÃO) que atuam sobre o grau de pertinência das variáveis 
Permite construir sistemas lógicos com regras fuzzy para modelar o raciocínio sobre um determinado problema
Tendem a possuir menos regras e utilizar mais regras, combinando-as de forma mais completa em cada inferência
Resumindo: A Lógica Fuzzy suporta modos de raciocínio que são aproximados, ao invés de exatos, como estamos acostumados a trabalhar.
Assim, é possível capturar conceitos vagos, descritos em linguagem natural e convertê-los em um formato numérico, de fácil manipulação pelos computadores
Exemplos de conceitos que podemos modelar: BAIXO, ALTO, QUENTE, FRIO, LENTO, RÁPIDO, LONGE, PERTO, GORDO, etc. 
CONJUNTOS FUZZY
A Lógica Fuzzy lida com Variáveis Fuzzy, construídas a partir de Conjuntos Fuzzy, que são funções que modelam uma entrada escalar em uma saída entre 0 e 1 (µ), chamada Grau de Pertinência, permitindo modelar um conceito vago:
Ou seja, um conjunto Fuzzy pemite modelar um conceito vago como “meia idade” em um número entre 0 e 1:
TIPOS DE FUNÇÕES
Pode-se utilizar qualquer função que associe o domínio da variável que se deseja fuzzificar com a imagem do intervalo [0,1]. Algumas funções comumente usada são:
SISTEMAS FUZZY
Usa conjuntos fuzzy para fuzzyficar dos valores escalares do mundo real, para manipula-los como valores linguísticos, como as pessoas altas do conjunto visto anteriormente.
Utilizam regras de inferência expressas com esses valores linguísticos, mas lidam com os valores de pertinência para produzir conjuntos fuzzy resultantes e, por fim, em um processo chamado defuzzyficação, os valores escalares que se apliquem à saída para o mundo real.
REGRAS FUZZY
combinam valores linguísticos (quente, alto, longe, etc.) e quantificadores (muito, pouco, extremamente, etc.) com operadores lógicos (E, OU, NÃO) ou de implicação (ENTÃO):
· SE temperatura é muito quente E fluxo é baixo ENTÃO gire a torneira muito à direita
· SE temperatura é morna E fluxo é médio ENTÃO gire a torneira um pouco à esquerda
COMBINAÇÃO DE REGRAS E DEFUZZIFICAÇÃO
Várias regras podem ser acionadas a cada vez e elas ser,,,,ão combinadas para produzir um conjunto fuzzy final
Finalmente, conjunto fuzzy resultante do acionamento das regras é defuzzyficado para produzir um valor escalar de saída do sistema
CARACTERISTICAS FUZZY
Associa valores contínuos, modelados com funções fuzzy, a valores linguísticos não mutuamente exclusivos 
Lida com imprecisão e não ambiguidade (domínio indefinido) Ex: SE o acarajé está quente ENTÃO . . . (temperatura?)
Permite conceitos conflitantes. Por exemplo:
· Se vendas estão baixas então abaixe o preço (Marketing)
· Se vendas estão baixas então aumente o preço (Finanças)
Permite a cobertura do domínio com menos regras e gera saídas diferentes para entradas diferentes. Ex: mais 
· Sist. Espec. Se temperatura < 120º ENTÃO chama=150º
· Sist. Fuzzy SE temperatura baixa ENTÃO chama alta 
Grau de pertinência é uma avaliação sobre um indivíduo, enquanto Fator de confiança é uma estimativa individual a partir de uma estatística colhida em uma população. Ex: altura do próximo indivíduo que veremos.
NOMENCLATURAS EM FUZZY
· Domínio
· Suporte
· Universo do discurso
OPERADORES FUZZY
Operadores lógicos: E OU NÃO ENTÃO
Aplicáveis à mesma variável ou variáveis distintas:
· Se idade é criança OU idade é jovem ENTÃO ...
· Se temperatura é baixa E pressão é grande ENTÃO ...
· Se vazão NÃO é pequena ENTÃO ...
Para o operador NÃO usa-se o complemento a 1 do grau de pertinência
Para o operador ENTÃO usa-se multiplicação dos graus de pertinência
Para os operadores E e OU usam-se as expressões da tabea a seguir, feitas com os graus de pertinência: 
Aula 5 - Construção de sistemas fuzzy
INFERÊNCIA FUZZY
Inferência é uma relação lógica que obedece à mesma implicação Modus Ponens da lógica tradicional
Na lógica Fuzzy, entretanto, a regra só será acionada se o grau de pertinência da premissa for diferente de zero.Ex.:
As formas mais usadas de calcular a implicação 
As formas mais usadas de calcular a implicação são:
· Usando o mínimo: µ p→q (x, y) = min [µ p(x), µ q(y)] 
· Usando o produto: µ p→q (x, y) = µ p(x) . µ q(y)
Combinar regras acionadas
DEFUZZIFICAÇÃO
É a forma de encontrar um valor escalar representativo do conjunto fuzzy de saída. As mais usadas são:
Defuzzificação pelo centro da área:
Defuzzificação pela média dos máximos:
z = (MC1 . µC1 + MC2 . µC2) / (µC1 + µC2)
 
Exemplo de aplicação (Software demo FuzzyTech)
REGRAS DE CONTROLE FUZZY
Se DISTÂNCIA = far e ÂNGULO = neg_small
Então POTÊNCIA = pos_high
Se DISTÂNCIA = medium e ÂNGULO = neg_small
Então POTÊNCIA = pos_high
Se DISTÂNCIA = medium e ÂNGULO = neg_big
Então POTÊNCIA = pos_medium 
Aula 6 – Sistemas evolutivos e algoritmos genéticos
CONCEITUANDO UM PROBLEMA DE OTIMIZAÇÃO
Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo
Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x)
Máximos e mínimos podem ser equivalentes
· Encontrar o “ótimo” pode ser encontrar o máximo ou o mínimo
· Ex: na função f(x)= -x2+3, podemos querer achar o “x” que maximiza f(x)
· Para uma função de muitos parâmetros, temos f( x1, x2, x3,...xn) 
· Função a otimizar: Função Objetivo
· Intervalo de busca da solução: Espaço de Busca
Espaço de busca pode ter restrições. Ex:
· Função objetivo: f(x) = x2 + y2 + 4
· Restrições: 2x - 3y < 5 e x + y = 7.
Otimização combinatória: busca-se uma sequência ótima de valores
CARACTERISTICAS QUE A FUNÇÃO A OTIMIZAR PODE APRESENTAR
 Ex: função mono parâmetro
 f(x) = x sen (3 x)
· Mínimos locais
· Estabilidade da função
· Funções multi-modais
· Ex: função mono parâmetro
 f(x) = sen (x/2) + cos (2x)/1,5
SOLUÇÕES PARA PROBLEMAS DE OTIMIZAÇÃO
Existem vários modelos matemáticos de otimização:
· Métodos analíticos (ex: Newton-Raphson): usam cálculo diferencial e dependem das funções serem conhecidas, contínuas e diferenciáveis
· Métodos de subida de encosta (ex: gradiente descendente, recozimento simulado, busca tabu): são métodos de buscas locais, em geral rápidos, mas sensíveis a mínimos locais 
· Métodos heurísticos (ex: algoritmos genéticos, colônia de formigas e enxames de abelhas): são métodos que exploram de forma mais uniforme o espaço de busca, são robustos quanto a mínimos locais, mas em geral são mais lentos .
ALGORITMOS GENÉTICOS – CARACTERISTICAS
· Possibilitam exploração simultânea (paralelizável) do espaço de busca;
· Funcionam em espaços de busca contínuos ou discretos;
· Não são sensíveis à existência de mínimos locais;
· Capazes de descobrir várias soluções (útil para funções multi-modais);
· Não impõem condições especiais (continuidade, existência de derivada);
· Funcionam bem em espaços de busca com muitas dimensões;
· Permitirem modelar restrições e otimizar simultaneamente múltiplas funções, mesmo que conflitantes; e,
· São fáceis de implantar computacionalmente, não dependendo de compreensão do problema a ser otimizado e de sua modelagem.
ALGORITMOS GENÉTICOS – INSPIRAÇÃO ORIGINAL
· Modelo computacional proposto por John Holland;
· Inspirado na biologia evolutiva (A Origem das Espécies - Charles Darvin);
· Ideia principal: seres mais adaptados têm mais chances de sobrevivência
· Capacidade de adaptação determina a sobrevivência
· Evolução das espécies se dá com mecanismos como:
· Seleção dos mais aptos (seleção natural)
· Recombinação genética (reprodução sexuada) 
· Mutações aleatórias (mutação genética)
ALGORTIMOS GENÉTICOS – O MODELO COMPUTACIONAL
· Modela as soluções do problema como indivíduos de uma espécie;
· Lida com um conjunto de soluções chamado de população;
· Modela cada solução como uma cadeia de bits que representa o genoma;
· Associa a cada solução uma medida de qualidade que reflete a capacidade do indivíduo em relação aos demais indivíduos da população;
· A evolução se dá pela criação de sucessivas gerações de indivíduos onde novos indivíduos são criados aplicando os mecanismos genéticos de seleção natural, reprodução por combinação e mutação aleatória.
· A evolução da população favorece o aparecimento de indivíduos mais adaptados, ou seja, de soluções otimizadas para o problema original.
MODELO COMPUTACIONAL – COMO COMEÇAR
Inicialmente é necessário criar uma representação para as soluções, chamado de cromossomo do indivíduo:
· É uma cadeia de bits que representam os parâmetros da função
· Pode conter valores discretos ou contínuos
É necessário estabelecer uma função de avaliação da aptidão de cada indivíduo que reflita a qualidade de cada solução/indivíduo
Estabelecer formas de aplicar os operadores genéticos de cruzamento e mutação para criação dos novos indivíduos
Estabelecer parâmetros de intensidade para aplicação dos operadores genéticos e critérios de parada para encerramento da evolução.
MODELO COMPUTACIONAL – CICLO EVOLUTIVO
1. Criar aleatoriamente uma população inicial 
2. Enquanto o critério de parada não for satisfeito:
· Associar grau de aptidão a cada indivíduo da população
· Criar uma nova população baseada no grau de aptidão:
· Inserir cópia de indivíduo muito apto na população do próximo ciclo
· Recombinar dois indivíduos por cruzamento genético, formando dois novos indivíduos para o próximo ciclo.
· Alterar a representação de um indivíduo em uma posição aleatória, gerando uma mutação genética desse indivíduo.
· Indivíduo com maior aptidão é a melhor solução nesta geração
3. Critérios de parada possíveis: 
· Melhor indivíduo atual ser satisfatório
· Número máximo de gerações ter sido atingido
· Tempo limite de processamento ter sido atingido
· Não haver melhora da população após várias gerações
DETALHANDO OS OPERADORES – SELEÇÃO
Ideia central: privilegiar os mais aptos sem zerar chances dos menos aptos
Métodos mais usados: torneio e roleta
Torneio: forma-se grupos de indivíduos e escolhe-se o mais apto do grupo
Roleta (amostragem estocástica): indivíduos são selecionados por amostragem em uma roleta em que cada indivíduo ocupa uma fatia proporcional à sua aptidão relativa na população
CRUZAMENTO (CROSSOVER)
Ideia central: transmitir características genéticas aos descendentes
Métodos mais usados: cruzamento de um ponto, multi pontos e uniforme
Cruzamento de um ponto: um ponto é escolhido e o material genético dos pais é trocado para gerar os filhos
Multi pontos: pontos distintos são escolhidos para troca do material
Uniforme: para cada gene é determinada uma probabilidade de troca
MUTAÇÃO
Ideia central: alterar aleatoriamente os indivíduos para manter a diversidade genética e explorar novas regiões no espaço de buscas
Método mais usado: alteração aleatória de um gene do genoma, geralmente invertendo um bit do cromossomo de um dos indivíduos também aleatoriamente escolhido
AJUSTE DOS PARÂMETROS GENÉTICOS
· Tamanho da população
· Taxa de cruzamento
· Taxa de mutação
· Taxa de elitismo
A ESCOLHA DA REPRESENTAÇÃO
Um solução tem um conjunto de características ou parâmetros, representados por genes, que podem ser unidos para formar um cromossomo, que é o genótipo do indivíduo. Ex: 
· Valores binários para ausência/presença de características 
· Valores numéricos codificados como cadeias de bits
Problemas: 
· genótipos inválidos devem ser corrigidos
· Alfabeto de representação deve ser o menor possível
A FUNÇÃO DE APTIDÃO
É o ponto central para o funcionamento da técnica
Geralmente é determinante no tempo global do algoritmo
Associa um valor escalar a cada indivíduo, refletindo a qualidade relativa do mesmo dentro da população
Se a função a ser otimizada é conhecida, a função de aptidão é a própria função a ser otimizada
Em outros casos é uma métrica que reflita a qualidade. Ex: o tamanho do caminho (caixeiro viajante), a quantidade de regiões adjacentes de mesma cor (colorir mapas), etc.
Aula 7 – Aplicando algoritmos genéticos em problemas reais
PASSOS DE APLICAÇÃO DOS ALGORITMOS GENÉTICOS
Inicialmente é necessário criar uma representação para as soluções, chamado de cromossomo do indivíduo:· É uma cadeia de bits que representam os parâmetros da função
· Pode conter valores discretos ou contínuos
É necessário estabelecer uma função de avaliação da aptidão de cada indivíduo que reflita a qualidade de cada solução/indivíduo
Estabelecer formas de aplicar os operadores genéticos de cruzamento e mutação para criação dos novos indivíduos
Estabelecer parâmetros de intensidade para aplicação dos operadores genéticos e critérios de parada para encerramento da evolução.
EXEMPLO: ENCONTRAR O VALOR MÁXIMO DA FUNÇÃO
Encontrar o valor de x correspondente ao máximo da função :
f(x)= -x2 + 33x , onde x[0, 31] e x é um número inteiro
1. Codificar o parâmetro x como uma cadeia finita de bits:
· Com 5 bits cobre-se a variação de x no espaço de busca
2. Criar aleatoriamente uma população inicial, que estabeleceremos em 4 indivíduos, como os à direita:
3. Associar um grau de aptidão a cada indivíduo da população
· A função de aptidão, nesse caso, é a própria função f(x)
· Calcular a aptidão relativa (%) do indivíduo na população
4. Aplicar um método de seleção natural, como a roleta:
 .
4. Na seleção natural pela roleta suponha que para selecionar 4 indivíduos entre a população, tenhamos gerados de forma aleatória os números: 35; 52; 91 e 66 (entre 0 e 99). Então: 
· 35 está entre 17 e 43 (cadeia 11000);
· 52 corresponde à cadeia 01000;
· 91 corresponde à cadeia 10011; e,
· 66 corresponde à cadeia 01000
5. Após a seleção natural, temos os seguintes indivíduos:
 a) 11000 b) 01000 c) 10011 d) 01000 (repetido)
6. Vamos aplicar o cruzamento de um ponto
· Taxa de cruzamento: 50% (população é muito pequena)
· Substituição total: filhos substituem pais (sem elitismo)
· Pais selecionados: novo sorteio, para o qual suponha que foram escolhidos os pares a-c 
· Ponto de cruzamento: após o terceiro bit 
6. Cruzamento gera os seguintes filhos:
Pais: 11000 e 10011 com ponto de corte = 3, então os filhos 11011 e 10000 substituirão os pais
7. A seguir aplica-se a mutação aleatoriamente. 
Taxa de cruzamento: 5% 
Com essa taxa, é esperada troca de apenas 1 bit no geral
Suponha que foi sorteado o terceiro bit do indivíduo b:
 01000 vai se transformar em 01100
8. Resumindo, após a aplicação de tosos os operadores genéticos e da avaliação da nova população, teremos:
9. Avaliação geral subiu de 822 para 864
10. Melhor valor subiu de f(19)=266 para f(16)=272
EXEMPLO: JOGO DAS 8 RAINHAS
Objetivo: posicionar oito rainhas no tabuleiro de xadrez sem que nenhuma rainha seja atacável pelas demais.
Por exemplo: se a primeira rainha fosse posicionada como na casa marcada no tabuleiro ao lado, todas as casas em cinza podem ser atacadas e não se pode posicionar outras rainhas nas mesmas.
1. A representação pode ser feita em um cromossomo com oito genes representando, cada um, a posição de uma rainha em cada uma das oito colunas do tabuleiro, já que só pode haver uma rainha por coluna. 
2. A aptidão pode ser avaliada contando quantas rainhas podem ser atacadas em uma configuração do tabuleiro. Para o caso ao lado, a aptidão dessa solução seria 7 (ruim), pois só a rainha em preto está livre de ser atacada (ideal=0).
2. Para que a aptidão seja grande quando a quantidade de rainhas atacadas for pequena, podemos fazer como no ex:
· Contagem de S1 = 2; Contagem de S2 = 4; Contagem de S3 = 6
· A contagem total seria 2+4+6=12
· A aptidão complementar seria: S1→12-2=10, S2→12-4=8 e S3→12-6=6. A aptidão total complementar seria 10+8+6=24
· As aptidões relativas seriam então:
S1→ 10/24 = 41,66%, S2→ 8/24 = 33,33% e S3→ 6/24 = 25%.
3. O cruzamento pode ser feito da seguinte forma:
· Escolhe-se um ponto de corte (por exemplo, o meio)
· Pega-se a primeira metade do primeiro pai
· Pega-se a segunda metade do segundo pai
· Verifica-se se há necessidade de reparar a representação da segunda metade para que não haja repetição de genes, pois isso representaria rainhas colocadas na mesma linha.
· Um exemplo de cruzamento seria o seguinte:
Pai 1: 1 3 5 2 | 6 4 7 8	 Pai 2: 3 5 7 2 | 4 8 1 6
Filho 1: 1 3 5 2 4 8 7 6 Filho 2: 3 5 7 2 6 4 1 8
4. A mutação poderia ser feita trocando dois genes dentro do cromossomo de uma solução:
· Sorteia-se um dos indivíduos (usando a taxa de mutação)
· Sorteia-se dois genes no cromossomo desse indivíduo. Ex: 3 5 7 2 6 4 1 8	
5. A mutação poderia ser feita trocando dois genes dentro do cromossomo de uma solução:
· Sorteia-se um dos indivíduos (usando a taxa de mutação)
· Sorteia-se dois genes no cromossomo desse indivíduo. Ex:
	3 5 7 2 6 4 1 8	→	3 4 7 2 6 5 1 8
Devemos percorrer N cidades passando apenas uma vez por cada uma das cidades:
· Problema NP-difícil: existem (N-1)! Caminhos
· N=5 → (N-1)! = 24 caminhos
· N=7 → (N-1)! = 720 caminhos
· N=11 → 3.628.800 caminhos
· N=50 → número IMENSO de caminhos
· N=100 → número incomputável de caminhos
EXEMPLO: PROBLEMA DO CAIXEIRO VIAJANTE
A representação de uma solução do problema pode ser feita com um cromossomo de tamanho N, onde cada posição é uma cidade e o caminho é dado pela sequência em que cada cidade aparece dentro do cromossomo. Ex:
 
A adaptação de uma solução pode ser dada pelo comprimento do total do percurso, somando os custos individuais dos caminhos entre cada duas cidades adjacentes:
Aptidão = custo total = G-D + D-A + A-F + F-K + ...
O cruzamento será:
· baseado na manutenção da ordem dos genes
· OBX do acrônimo em inglês Order Based Crossover
· Escolhe-se aleatoriamente genes a serem trocados
· Genes não escolhidos são copiados de Pai1 para Filho1
· Filho1 é complementado com genes do pai2 na ordem em que aparecem em Pai2]
Exemplo de como é feito o cruzamento:
Pai1: 		B E A D G H F C
Pai2: 		G C F H E D A B
Posições: 	 * * * 
Filho1: 	B E G D H A F C
Filho2: 	G C E H D F A B
A mutação pode ser feita como no caso anterior (trocando pares de genes) ou trocando sublistas definidas por um ponto de corte, como no exemplo abaixo:
Antes: 		A B C D E | F G H
Ponto de corte: 		 | 
Depois: 		F G H A B | C D E
OUTROS EXEMPLOS DE APLICAÇÕES
· Elaboração de escalas de trabalho em ambientes de saúde
· Alocação de horários e professores em grades de ensino
· Definição de componentes de circuitos eletrônicos
· Recuperação de informação em documentos de texto
· Projeto de transformadores elétricos
· Planejamento de eventos (paraolimpíadas de Barcelona)
· Apoio às decisões táticas de batalhas
Aula 8 – Modelos conexionistas e redes neurais
DIFERENÇAS – MODELO SIMBOLISTA E MODELO CONEXIONISTA
Modelos Simbolistas:
· Representam o conhecimento com algoritmos, regras, etc.
Modelos Conexionistas:
· Não há representação do conhecimento
· Aprendem por meio de exemplos (treinamento)
· Armazenam o conhecimento nas conexões da rede
· Após treinadas o conhecimento armazenado não é interpretável
· Não justificam o raciocínio, pois decisões não são interpretáveis
· Possuem capacidade de generalizar o conhecimento aprendido
CONHECIMENTOS BÁSICOS SOBRE OS MODELOS CONEXIONISTAS
· Originalmente inspirados no funcionamento do cérebro
· Utilizam uma unidade básica chamada de neurônio artificial
· Juntam neurônios artificiais em conjuntos chamados de Redes Neurais (ou Neuronais)
· Neurônios artificiais ou nós da rede são conectados por ligações que possuem pesos ajustáveis
· O treinamento da rede consiste em um algoritmo de ajuste dos pesos, portanto, é nos pesos que, ao final do treinamento, se encontram as informações aprendidas.
INSPIRAÇÃO BIOLÓGICA
O neurônio artificial é inspirado no neurônio biológico
O neurônio artificial é um modelo computacional
· x1, x2, ..., xp são os sinais de entrada;
· w1, w2, ..., wp são pesos aplicados aos sinais de entrada;
· Σ é a função somadora que gera “a” (entrada líquida);
· f(a) é a função de função de ativação do neurônio
· y é a saída do neurônio
FUNÇÃO DE ATIVAÇÃO
· Determinam a forma e a intensidade da saída do neurônio· Primeira FA proposta (McCullock-Pitts): função de limiar
· Funções de limiar: Unidades binárias (0 e 1 ou -1 e 1)
· Usada na primeira RN (Rosenblatt) com saídas -1 e 1
CONECTANDO NEURÔNIOS EM REDES NEURAIS
Neurônios são conectados uns aos outros com alguma topologia onde as conexões ponderadas influenciam na transmissão dos estímulos de um neurônio para o outro.
Redes mais usadas: redes diretas multicamadas(entrada saída)
TOPOLOGIAS DE REDE
REDES DIRETAS
Não possuem ciclos, propagando o sinal sempre para a frente.
REDES COM CICLOS
A característica principal é que realimentam o sinal: 
· Com neurônios dinâmicos são redes recorrentes
· Com neurônios que competem pelo direito de produzir a saída são chamadas de redes competitivas 
REDES NEURAIS – TREINAMENTO
É o modo como a rede aprende a partir dos dados que são apresentados durante o processo de treinamento
Aprendizado implica na alteração dos pesos das conexões. Após o treinamento são os pesos que armazenam o conhecimento que permite à rede tomar decisões corretas 
Cada tipo de treinamento é adequado a um tipo específico de topologia
TREINAMENTOS SUPERVISIONADOS E NÃO SUPERVISIONADOS
Algoritmos de aprendizado podem ser:
Supervisionados: são apresentados as entradas e as saídas correspondentes que se deseja que a rede produza. Esse conjunto constitui os padrões de treinamento. O ajuste dos pesos é feito a cada padrão entrada/saída para produzir a saída desejada. Usado em redes diretas.
Não supervisionados: são apresentadas apenas entradas. As saídas correspondem às características de interesse dos padrões de entrada. Usado em redes competitivas.
PROJETO DA REDE NEURAL
Parâmetros importantes a serem considerados:
· Topologia da rede
· Quantidade de camadas (redes diretas em camadas)
· Quantidade de neurônios
· Função de transferência
· Representação dos dados
· Dinâmica do aprendizado
· Condições de parada
Não existe modelo ou procedimento sistemático
REDES COM FUNÇÃO DE LIMIAR
Com e sem polarização:
Considerando a polarização como um peso, ou seja b = w0:
AO INVÉS DE 
E voltamos a ter
RESOLVENDO UM PROBLEMA
Com um neurônio desse tipo é possível resolver um problema de lógica booleana (porta lógica OU) :
É um problema de classificação resolvível com a rede:
Separação obedece à: E1 . w1 + E2 . w2 + w0 = 0 
COMO DESCOBRIR OS PESOS
O treinamento consiste em encontrar uma regra de atualização automática dos pesos
A regra de Hebb tem essa característica e funciona para:
· Neurônios com função de limiar bipolar (-1 e 1)
· Pesos iniciam todos com 0
· Wi novo = Wi antigo+ DELTAWi
· DELTAWi = Ei . d; 	onde d é a saída desejada,
· W0 = b e E0 = 1
Aplicando a regra de Hebb teremos:
Ao final, a rede ficou assim: 
REGRA DE TREINAMENTO PERCEPTRON
Função de ativação pode ter limiar teta diferente de 0.
Fator de aprendizado n regula as mudanças dos pesos
Aplicando a regra de Perceptron teremos:
· Neurônios com função de limiar bipolar (-1 e 1)
· Pesos iniciam com valores aleatórios
· Wi novo = Wi antigo+ Wi
· DELTAWi = n . Ei . D y diferente d; onde d é a saída desejada,
· W0 = b e E0 = 1
REDES ADALINE (ADAPTATIVE LINEAR ELEMENT)
Rede ADALINE: EXEMPLO DO OR BIPOLAR
Aula 9 – Redes neurais supervisionadas
LIMITAÇÕES DAS REDES DE UMA CAMADA
Lidam apenas com problemas linearmente separáveis:
Ex: não é possível emular um uma porta XOR
Ex: não é possível emular um uma porta XOR
Para emular um uma porta XOR precisamos de uma rede como esta:
· A rede criou uma superfície separadora 
· Plano separador é tridimensional pois o nó tem três entradas
· Foi necessário criar uma rede com mais de uma camada
· entradas N dimensionais geram superfícies separadoras no plano N-1 dimensional para as classes do problema 
· encontrar os valores dos pesos e polarizações necessários depende de um algoritmo que considere que não são conhecidas as saídas dos nós das camadas ocultas
CONHECIMENTOS BÁSICOS SOBRE OS MODELOS CONEXIONISTAS
· Originalmente inspirados no funcionamento do cérebro
· Utilizam uma unidade básica chamada de neurônio artificial
· Juntam neurônios artificiais em conjuntos chamados de Redes Neurais (ou Neuronais)
· Neurônios artificiais ou nós da rede são conectados por ligações que possuem pesos ajustáveis
· O treinamento da rede consiste em um algoritmo de ajuste dos pesos, portanto, é nos pesos que, ao final do treinamento, se encontram as informações aprendidas.
REDES PERCEPTRON DE MÚLTIPLAS CAMADAS
Algoritmo de retropropagação dos erros (backpropagation):
1. Apresentar um padrão (entrada + saída desejada) à rede;
2. Calcular o erro na saída (saída obtida – saída desejada);
3. Retropropagar o erro na rede calculando de que forma as mudanças nos pesos afetam o erro;
4. Modificar os pesos para minimizar o erro médio dos padrões;
5. Retornar ao passo 1 enquanto haja padrões;
6. Se um erro máximo desejado não tiver sido atingido, retornar ao passo 1 para a próxima iteração.
1. Apresentar um padrão de entrada;
2. Propagar o sinal para a frente, calculando as saídas; 
3. Calcular os ’s para os neurônios da camada de saída;
4. Retropropagar o erro da saída calculando os ’s das camadas ocultas;
5. Atualizar os pesos e retornar ao passo 1.
Alguns aspectos relevantes sobre a função de ativação a ser empregada, dadas as características do algoritmo:
1. A função de ativação precisa ser diferenciável em todo o domínio;
2. A função de ativação precisa ser não decrescente para que a sua derivada não troque de sinal comprometendo a convergência do algoritmo;
Exemplos de funções utilizadas:
· Sigmóide: 
· Tangente hiperbólica (semelhante com limite inferior de -1)
· Linear
CARACTERISTICAS PRATICAS DO TREINAMENTO BACKPROPAGATION:
· Dados de treinamento x dados de validação
· Atualização dos pesos (a cada padrão ou batelada)
· Parada do treinamento
· Escolha dos pesos iniciais
· Termo de momento: 
· Mínimos locais
· Atualização das taxas de aprendizado e de momento
DETERMINAÇÃO DO TAMANHO DA REDE
Excesso de treinamento x precisão
Tamanho da rede x precisão
Métodos de eliminação de pesos (poda de pesos):
Exemplo de aplicação:
reconhecimento e codificação de caracteres 
Aula 10 – Redes neurais auto organizadas de treinamento não supervisionado
TREINAMENTO SUPERVISIONADO X TREINAMENTO NÃO SUPERVISIONADO
No treinamento supervisionado:
· Padrões de treinamento possuem entradas E saídas desejadas
· Queremos que a rede aprenda a partir de padrões CONHECIDOS
· Treinamento é direcionado para diminuir o ERRO na saída (classificar corretamente as entradas)
No treinamento não supervisionado:
· Padrões de treinamento possuem apenas entradas 
· Padrões apresentados não possuem classificação conhecida
· Treinamento é direcionado para auto organizar os padrões de entrada semelhantes em grupos (clusters)
APLICAÇÕES DE REDES NÃO SUPERVISIONADAS
Problemas gerais de agrupamento, exemplos:
· Identificar grupos de clientes (marketing/vendas)
· Identificar problemas comuns de usuários (suporte)
· Estabelecer protótipo de comportamento de fraude (segurança corporativa)
· Análise de capacidade de pagamento (empréstimos)
· Identificação de potencial falimentar (finanças)
CARACTERISTICAS DAS REDES AUTO ORGANIZADAS
· Deve existir redundância nas entradas
· Redundância fornece conhecimento
· Buscam identificar padrões semelhantes
· Aprendizado não supervisionado
· Hebbiano
· Competitivo
REDES AUTO ORGANIZADAS COM APRENDIZADO HEBBIANO
· O treinamento utiliza a regra de Hebb
· Tais redes são associadoras
· Aplicações:
· Extração de características
· Análise de dados
· Memória auto-associativa
· Redes desse tipo: Hopfield, PCA
REDES AUTO ORGANIZADAS COM APRENDIZADO COMPETITIVO
· Neurônios competem entre si pelo direito de atualizar seus pesos
· Utilizadas para agrupamento de dados similares
· Aplicações:
· Extração de características
· Formação de clusters (agrupamentos)
· Redes desse tipo: ART, SOM
ESTRUTURA DAS REDES COMPETITIVAS
Possuem uma só camada (camadade saída) 
As entradas (camada i) são ligadas diretamente nas saídas (camada j) por meio dos pesos wij
TREINAMENTO DAS REDES COMPETITIVAS
Nós competem entre si pela atualização dos pesos 
Para cada padrão de entrada, apenas um nó é declarado vencedor e terá os pesos atualizados
O nó vencedor é o mais representativo do cluster ao qual pertence aquele padrão de entrada.
A representatividade é medida pela distância entre o vetor de pesos e o vetor de entrada. 
1. Para cada padrão de entrada (vetor) é calculada a distância para cada nó (vetor de pesos do nó)
2. O nó escolhido tem seus pesos ajustados para ficar ainda mais parecido com o padrão de entrada
3. Padrões de entrada parecidos entre si terão o mesmo nó como vencedor e provocarão ajustes nos mesmos pesos
4. Considere entradas com 3 valores (vetor tridimensional) e uma rede com 3 nós (vetor de pesos também com valores). A figura a seguir ilustra a situação inicial caso haja 19 padrões de entrada.
ESTRUTURA DAS REDES COMPETITIVAS
Durante o treinamento, a rede identifica o nó que melhor representa o padrão e ajusta-o um pouco
Após a rede ser treinada, cada padrão de entrada pertence a um nó de saída que é representativo do grupo (cluster) a que ele pertence. 
Os pesos de um nó, após a rede treinada, são o protótipo dos elementos daquele agrupamento.
REDES AUTO ORGANIZAVEIS
A distância entre o vetor de entrada e o vetor de pesos de cada nó pode ser medida usando:
Produto escalar dos dois vetores (para vetores normalizados). Quanto maior o produto escalar, mais próximos estão os valores.
Distância Euclidiana entre o vetor de pesos e o vetor de entrada  (wk-x)2
MAPAS AUTO ORGANIZAVEIS (SOM – SELF ORGANIZED MAPS): KOHONEN
Uma camada de saída com nós em disposição bidimensional.
A camada de saída cria uma mapeamento do espaço n-dimensional (n entradas) para o espaço bidimensional.
Padrões parecidos no espaço n-dimensional estarão próximos no espaço bi-dimensional.
O neurônio vencedor e os seus vizinhos (definidos por algum raio) sofrem alterações nos pesos.
Ajuste dos pesos é feito da seguinte forma: wij(t +1) = η (xi(t) - wij(t)) 
 (yj é um nó da vizinhança do nó vencedor)
Taxa de treinamento n é ajustável 
Cria mapeamento em regiões do espaço bi-dimensional que aglutina indivíduos parecidos no espaço n-dimensional.
MAPAS AUTO ORGANIZAVEIS (CICLO DE TREINAMENTO)
1. Iniciar os pesos com valores aleatórios
2. Definir o raio de vizinhança e a taxa de treinamento
3. Repetir enquanto o critério deparada não for atingido:
Para cada padrão de treinamento:
· Para cada neurônio:
· Calcular a saída dK de todos os neurônios
· Selecionar o neurônio nk com o menor dK
· Atualizar os pesos do neurônio nk e de seus vizinhos 
EXEMPLO DE REDE SOM
A entrada da rede de Kohonen é um conjunto de vetores de padrões. Por exemplo, poderíamos ter 10 mil padrões de clientes bancários, cada um formado por um vetor de tamanho 5, contendo, para cada cliente, informações de: idade; imóvel próprio ou não; CEP; profissão; e, renda.
Para uma rede 4X4, cada nó está ligado ao vetor de entradas por um vetor de pesos de tamanho 5. 
Após o treinamento, poderemos atribuir 1 dos 16 neurônios da malha a cada um dos 10 mil padrões.
OUTRO EXEMPLO DE REDE SOM
Rede com dois nós para classificar veículos.
Como a rede é mínima, vamos considerar a vizinhança como sendo o próprio neurônio, duas iterações e fazer n = 0.8 (fixo).
As características serão o número de rodas e a existência ou não de motor (1 indica a existência de motor enquanto 0 indica a ausência).
Vejamos os padrões de entrada para os dois veículos que usaremos no treinamento:
		Rodas	 Motor	
Bicicleta	2		0	
Carro		4		1	
A rede terá 2 entradas (características dos padrões) e 4 nós. 
Aleatoriamente os pesos são inicializados para: 
neurônio 1 = { w11, w21} = {1, 2} 
neurônio 2 = { w12, w22} = {2, 2} 
neurônio 3 = { w13, w23} = {1, 3} 
neurônio 4 = { w14, w24} = {3, 2} 
PRIMEIRA ITERAÇÃO 
Apresentado as característica da bicicleta {2,0} e calculando as distâncias: 
d1 = (2-1)2 + (0-2)2 = 5 
d2 = (2-2)2 + (0-2)2 = 4 neurônio vencedor
d3 = (2-1)2 + (0-3)2 = 10 
d4 = (2-3)2 + (0-2)2 = 5 
O neurônio vencedor é o segundo (d2). Ajustando seu peso: 
w12 = w12 + 0.8(x1(t) - w12(t)) = 2 + 0.8.(2-2) = 2 
w22 = w22 + 0.8(x2(t) - w22(t)) = 2 + 0.8.(0-2) = 0.4 
Apresentado as características do automóvel {4,1} e calculando as distâncias: 
d1 = (4-1)2 + (1-2)2 = 10 
d2 = (4-2)2 + (1-0.4)2 = 4.36 
d3 = (4-1)2 + (1-3)2 = 13 
d4 = (4-3)2 + (1-2)2 = 2 neurônio vencedor
O neurônio vencedor é o quarto (d4). Ajustando seu peso: 
w14 = w14 + 0.8(x1(t) - w14(t)) = 3 + 0.8.(4-3) = 3.8 
w24 = w24 + 0.8(x2(t) - w24(t)) = 2 + 0.8.(1-2) = 1.2 
Aplicando novamente os padrões em uma SEGUNDA ITERAÇÃO, ajustaremos os pesos para:
neurônio 1 = { w11, w21} = {1, 2} 
neurônio 2 = { w12, w22} = {2, 0.08} 
neurônio 3 = { w13, w23} = {1, 3} 
neurônio 4 = { w14, w24} = {3.96, 1.04} 
Considerando que nesse ponto a rede já esteja treinada e aplicando as características de uma motocicleta, teremos: 
 x = {2,1} 
d1 = (2-1)2 + (1-2)2 = 2 
d2 = (2-2)2 + (1-0.08)2 = 0.8464 mesma classe da bic.
d3 = (2-1)2 + (1-3)2 = 5 
d4 = (2-3.8)2 + (1-1.2)2 = 3.8432 
Conj. Treinamento.	80	40	20	16	14	13	12	11.5	11	10.5	10	9.6	9.1999999999999993	Conj. Validação	90	50	30	24	21	18	20	22	24	27	29	31	33	Tempo de treinamento
Erro