Inteligência Artificial e Conhecimento PDF

Inteligência Artificial e Conhecimento Métodos de Procura – Custo Uniforme A Inteligência Artificial requer a utilização de conhecimento. Este conhecimento que lhe é dado pode ser volumoso, Variante...

Inteligência Artificial e Conhecimento Métodos de Procura – Custo Uniforme A Inteligência Artificial requer a utilização de conhecimento. Este conhecimento que lhe é dado pode ser volumoso, Variante do Breadth-First que se interessa em minimizar o custo em vez da distância caso os custos associados aos arcos difícil de caracterizar com precisão e está em constante mutação. Este também é a base para o principal tipo de forem diferentes de arco para arco. Este algoritmo garante a minimização do custo. aplicação comercial: O Sistema Pericial. O conhecimento a induzir na Inteligência Artificial deve ser representado de 1. Nó inicial à ABERTOS. Faz g(s) = 0 forma a: 2. Se ABERTOS vazio, falha Permitir representar regras gerais 3. Remove o nó de ABERTOS (n) com menor custo (g) e coloca-o em FECHADOS Ser compreendido pelas pessoas que o fornecem ao sistema 4. Se (n) for um nó objetivo termina e dá a solução Ser facilmente modificável 5. Expande o nó n. Coloca os sucessores em ABERTOS, colocando ponteiros para (n) e calculando o g de cada um dos sucessores Este conhecimento pode ser impreciso ou incompleto e pode ser usado para superar o seu próprio volume. 6. Vai para 2. Avaliação de uma Inteligência Artificial – Teste de Turing Métodos de Procura – Depth-First No teste de Turing existem 2 canais de comunicação idênticos e independentes (1 pessoa e uma máquina). Se ao fim de Neste método convenciona-se que a profundidade do nó raiz é zero e é definido um nível de profundidade máximo, a um período de interação razoável não for possível distinguir a pessoa da máquina, então a máquina é considerada partir do qual os eles não se expandem. Quando são gerados nós sucessores que já estão em ABERTOS ou FECHADOS inteligente. pode ser necessário recalcular a profundidade dos nós correspondentes. Atualmente a Inteligência Artificial está mais interessada em fazer máquinas que ajudem as pessoas a resolver 1. Nó inicial à ABERTOS problemas, de forma colaborativa, tirando o melhor partido das capacidades de memoria e rapidez de calculo das 2. Se ABERTOS vazia, falha máquinas e das capacidades das pessoas (criatividade e tratamento de exceções). 3. Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS Assim, a Inteligência Artificial de hoje em dia não seria avaliável através do teste de Turing, pois está mais interessada na 4. Se a profundidade de (n) é maior que o nível de profundidade máximo volta para 2 colaboração Humano-Máquina utilizando as capacidades dos dois ao máximo do que fazer com que as máquinas imitem 5. Expande o nó n. Coloca os sucessores no início de ABERTOS, com ponteiros para n seres humanos. 6. Se algum dos sucessores é um nó objetivo sai e dá a solução. Caso contrário volta para 2. Resolução de Problemas Grafos em vez de Arvores A resolução de problemas em Inteligência Artificial é baseada na utilização de conhecimento como forma de reduzir a Se o espaço de estados for um grafo, é preciso modificar os algoritmos estudados. explosão combinatória que resulta da exploração de todos os caminhos possíveis para a solução. Breadth-First o Reconhecer se um estado sucessor já está em ABERTOS ou em FECHADOS, e nesse caso não colocar o nó correspondente em ABERTOS Heurísticas Custo Uniforme Para resolver o problema da explosão combinatória, a Inteligência Artificial recorre à utilização de heurísticas. O o Se o sucessor de n está em ABERTOS conhecimento heurístico é: § Este sucessor não é adicionado se g (sucessor de n) > g (sucessor em ABERTOS) § Caso contrário o sucessor de n substitui o que se encontra em ABERTOS De natureza não científica o Se o sucessor está em fechados ignora-se o sucessor de n Incerto Depth-First Baseado na experiência passada o Se está em ABERTOS um nó com o mesmo estado, quer dizer que esse nó tem um custo g menor ou igual ao do nó gerado agora. Abandona o nó gerado Este visa sacrificar a solução ótima em benefício da garantia de encontrar uma solução satisfatória ainda que não seja a o Se está em FECHADOS e tem um custo maior ou igual, elimina o nó antigo e coloca o nó gerado em melhor. ABERTOS, e coloca ponteiros nos sucessores do nó antigo para o nó gerado o Caso contrário, abandona o nó gerado. 2 4 Inteligência Artificial 2 – Procura em Espaço de Estados 1 - Introdução Espaço de Estados O que é a Inteligência Artificial Uma forma simples de resolver problemas que não se podem resolver com formulas ou algoritmos, consiste em explorar o espaço de possibilidades tentando vários caminhos possíveis até encontrar a solução. Neste caso um problema terá de Existem muitas definições de Inteligência. São aspetos a considerar como definição de inteligência a capacidade de ser equacionado em termos de: Estados e Operadores. resolver problemas, a capacidade de usar o conhecimento, ou seja, raciocinar e capacidade de aprender. Terá ainda de ser definido o estado final. A Inteligência Artificial não tem uma definição globalmente aceite, no entanto pode ser vista como o estudo de como fazer os computadores realizarem tarefas em que de momento as pessoas são melhores. Os problemas iniciais para a Inteligência Artificial foram: Representação Jogos como Xadrez ou Damas Grafo – O Espaço de Estados pode ser representado por um grafo dirigido acíclico Demonstração de Teoremas Nó – Cada nó do grafo representa um estado do problema, com alguma informação adicional: Ponteiro para o nó que o Linguagem Natural gerou / Heurística / Pontuação / Outros tipos de informação relevante Atualmente é possível a resolução de problemas logísticos, exploração de dados e diagnóstico médico através da Arco – Cada arco do grafo representa uma transição de estado ao longo do processo de resolução do problema. Inteligência Artificial. Até mesmo em jogos como o Xadrez a Inteligência Artificial ganhou ao campeão mundial. Estratégias de Exploração de Arvores Redes Neuronais Conceitos É um sistema de decisão inspirado em sistemas biológicos, programados por exemplos e com aprendizagem automática supervisionada e incremental baseada em reforço. Nó inicial Sucessores de um nó: Nós gerados pela aplicação dos operadores lógicos Redes neuronais são aplicadas em: Expansão de um nó: Geração de todos os sucessores Reconhecimento de padrões Ponteiro para o nó pai: Permite obter a solução a partir do estado final Robótica e Controlo Lista de nós abertos: Lista com os nós que ainda não foram explorados Processamento de dados e extração de informação Lista de nós fechados: Lista com os nós que já foram expandidos Processamento da linguagem natural Métodos de Procura – Breadth-First Âmbito da Inteligência Artificial Neste método assume-se que o nó inicial não é um nó objetivo. Este método encontra sempre a solução que A inteligência artificial permite então dar resposta a problemas com características que os tornam muito difíceis de ser corresponde ao caminho mais curto e caso não haja solução termina com falha caso o grafo seja finito ou não termina resolvidos métodos convencionais como formulas matemáticas ou algoritmos. caso o grafo seja infinito No entanto existem dois problemas principais com os quais a inteligência artificial tem de lidar: 1. Nó inicial à Abertos 2. Se Abertos estão vazios, falha A incapacidade de usar modelos da realidade à Usar modelos mentais da forma como os especialistas resolvem 3. Remove o primeiro nó de ABERTOS (nó n) e coloca-o em FECHADOS os problemas. 4. Expande o nó n. Coloca os sucessores no fim de ABERTOS e os ponteiros para n Explosão combinatória à Usar conhecimento para reduzir o espaço de procura (Heurísticas) 5. Se algum sucessor for um nó objetivo sai e dá a solução. Caso contrário vai para 2 1 3 Admissibilidade Algoritmos de Procura em Espaço de Estados – Procura com Memória Limitada Um algoritmo diz-se admissível se, para qualquer grafo, descobre sempre o caminho ótimo para o objetivo desde que IDA* – Iterative Deepening A* esse caminho exista. Este algoritmo garante a descoberta da solução ótima desde que se use uma heurística admissível. Se h’ é um limite inferior de h então o algoritmo é admissível. A admissibilidade implica que: 1. Aplica-se uma seria de vezes o método de procura em profundidade, com limiares de profundidade variáveis, Quando o A* expande um nó (n) já encontrou um caminho ótimo para (n) mas em que o limite (“Cost cut-off”) é dado em termos do f. Quando o A* expande um nó (n) a função de avaliação f’ não é maior que o custo real f. 2. Na primeira pesquisa o limiar L é dado por f’(n0) = g(n0) + h’(n0) = h’(n0), em que n0 é o nó inicial. 3. O custo do caminho ótimo pode ser igual ao limiar, mas não maior dado que a heurística tem de ser admissível ( (h(n0) >= h’(n0) ) Informação Heurística 4. Só se expandem nós com f’(n) h(B) para todos os estados exceto os estados objetivo. Dado que o IDA* é do tipo de procura-em-profundidade apenas necessita de guardar em memoria um número de nós igual ao maior ramo explorado. Num problema em que os valores de f’ são diferentes para todos os nós de um espaço de estados, o número de Consistência iterações pode ser igual ao número de nós com f’ menor que o custo do caminho ótimo. Pode demonstrar-se que se a heurística for consistente o A* nunca expande mais nós do que um algoritmo A com Neste caso, sendo a solução dada por uma sequência de N nós, o A* explora O(N) enquanto o IDA* explora O(N^2). informação heurística menor ou igual. Uma heurística é consistente se h’(m) – h’(n)