Inteligência Artificial - Resumos PDF

Inteligência Artificial Inteligência Artificial e Conhecimento 1 - Introdução A Inteligência Artificial requer a utilização de conhecime...

Inteligência Artificial Inteligência Artificial e Conhecimento 1 - Introdução A Inteligência Artificial requer a utilização de conhecimento. Este conhecimento que lhe é dado pode ser volumoso, difícil de caracterizar com precisão e está em constante mutação. Este também é a base para o principal tipo de O que é a Inteligência Artificial aplicação comercial: O Sistema Pericial. O conhecimento a induzir na Inteligência Artificial deve ser representado de Existem muitas definições de Inteligência. São aspetos a considerar como definição de inteligência a capacidade de forma a: resolver problemas, a capacidade de usar o conhecimento, ou seja, raciocinar e capacidade de aprender. Permitir representar regras gerais A Inteligência Artificial não tem uma definição globalmente aceite, no entanto pode ser vista como o estudo de como Ser compreendido pelas pessoas que o fornecem ao sistema fazer os computadores realizarem tarefas em que de momento as pessoas são melhores. Ser facilmente modificável Os problemas iniciais para a Inteligência Artificial foram: Este conhecimento pode ser impreciso ou incompleto e pode ser usado para superar o seu próprio volume. Jogos como Xadrez ou Damas Demonstração de Teoremas Avaliação de uma Inteligência Artificial – Teste de Turing Linguagem Natural No teste de Turing existem 2 canais de comunicação idênticos e independentes (1 pessoa e uma máquina). Se ao fim de Atualmente é possível a resolução de problemas logísticos, exploração de dados e diagnóstico médico através da 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 Inteligência Artificial. Até mesmo em jogos como o Xadrez a Inteligência Artificial ganhou ao campeão mundial. inteligente. Atualmente a Inteligência Artificial está mais interessada em fazer máquinas que ajudem as pessoas a resolver Redes Neuronais problemas, de forma colaborativa, tirando o melhor partido das capacidades de memoria e rapidez de calculo das máquinas e das capacidades das pessoas (criatividade e tratamento de exceções). É 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. 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 colaboração Humano-Máquina utilizando as capacidades dos dois ao máximo do que fazer com que as máquinas imitem Redes neuronais são aplicadas em: seres humanos. Reconhecimento de padrões Robótica e Controlo Processamento de dados e extração de informação Resolução de Problemas Processamento da linguagem natural A resolução de problemas em Inteligência Artificial é baseada na utilização de conhecimento como forma de reduzir a explosão combinatória que resulta da exploração de todos os caminhos possíveis para a solução. Âmbito da Inteligência Artificial A inteligência artificial permite então dar resposta a problemas com características que os tornam muito difíceis de ser Heurísticas resolvidos métodos convencionais como formulas matemáticas ou algoritmos. Para resolver o problema da explosão combinatória, a Inteligência Artificial recorre à utilização de heurísticas. O No entanto existem dois problemas principais com os quais a inteligência artificial tem de lidar: conhecimento heurístico é: A incapacidade de usar modelos da realidade à Usar modelos mentais da forma como os especialistas resolvem De natureza não científica os problemas. Incerto Explosão combinatória à Usar conhecimento para reduzir o espaço de procura (Heurísticas) Baseado na experiência passada 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 melhor. 1 2 2 – Procura em Espaço de Estados Métodos de Procura – Custo Uniforme Espaço de Estados Variante do Breadth-First que se interessa em minimizar o custo em vez da distância caso os custos associados aos arcos forem diferentes de arco para arco. Este algoritmo garante a minimização do custo. 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 1. Nó inicial à ABERTOS. Faz g(s) = 0 ser equacionado em termos de: Estados e Operadores. 2. Se ABERTOS vazio, falha 3. Remove o nó de ABERTOS (n) com menor custo (g) e coloca-o em FECHADOS Terá ainda de ser definido o estado final. 4. Se (n) for um nó objetivo termina e dá a solução 5. Expande o nó n. Coloca os sucessores em ABERTOS, colocando ponteiros para (n) e calculando o g de cada um dos sucessores Representação 6. Vai para 2. Grafo – O Espaço de Estados pode ser representado por um grafo dirigido acíclico Nó – Cada nó do grafo representa um estado do problema, com alguma informação adicional: Ponteiro para o nó que o Métodos de Procura – Depth-First gerou / Heurística / Pontuação / Outros tipos de informação relevante Neste método convenciona-se que a profundidade do nó raiz é zero e é definido um nível de profundidade máximo, a Arco – Cada arco do grafo representa uma transição de estado ao longo do processo de resolução do problema. partir do qual os eles não se expandem. Quando são gerados nós sucessores que já estão em ABERTOS ou FECHADOS pode ser necessário recalcular a profundidade dos nós correspondentes. Estratégias de Exploração de Arvores 1. Nó inicial à ABERTOS 2. Se ABERTOS vazia, falha Conceitos 3. Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS Nó inicial 4. Se a profundidade de (n) é maior que o nível de profundidade máximo volta para 2 5. Expande o nó n. Coloca os sucessores no início de ABERTOS, com ponteiros para n Sucessores de um nó: Nós gerados pela aplicação dos operadores lógicos 6. Se algum dos sucessores é um nó objetivo sai e dá a solução. Caso contrário volta para 2. Expansão de um nó: Geração de todos os sucessores Ponteiro para o nó pai: Permite obter a solução a partir do estado final Lista de nós abertos: Lista com os nós que ainda não foram explorados Grafos em vez de Arvores Lista de nós fechados: Lista com os nós que já foram expandidos Se o espaço de estados for um grafo, é preciso modificar os algoritmos estudados. Breadth-First Métodos de Procura – Breadth-First o Reconhecer se um estado sucessor já está em ABERTOS ou em FECHADOS, e nesse caso não colocar o nó Neste método assume-se que o nó inicial não é um nó objetivo. Este método encontra sempre a solução que correspondente em ABERTOS corresponde ao caminho mais curto e caso não haja solução termina com falha caso o grafo seja finito ou não termina Custo Uniforme caso o grafo seja infinito o Se o sucessor de n está em ABERTOS § Este sucessor não é adicionado se g (sucessor de n) > g (sucessor em ABERTOS) 1. Nó inicial à Abertos § Caso contrário o sucessor de n substitui o que se encontra em ABERTOS 2. Se Abertos estão vazios, falha o Se o sucessor está em fechados ignora-se o sucessor de n 3. Remove o primeiro nó de ABERTOS (nó n) e coloca-o em FECHADOS Depth-First 4. Expande o nó n. Coloca os sucessores no fim de ABERTOS e os ponteiros para n o Se está em ABERTOS um nó com o mesmo estado, quer dizer que esse nó tem um custo g menor ou 5. Se algum sucessor for um nó objetivo sai e dá a solução. Caso contrário vai para 2 igual ao do nó gerado agora. Abandona o nó gerado o Se está em FECHADOS e tem um custo maior ou igual, elimina o nó antigo e coloca o nó gerado em ABERTOS, e coloca ponteiros nos sucessores do nó antigo para o nó gerado o Caso contrário, abandona o nó gerado. 3 4 Métodos Heurísticos ou “Informados” Admissibilidade Para combater o facto de que todos os métodos estudados até este ponto não resolvem o problema da explosão Um algoritmo diz-se admissível se, para qualquer grafo, descobre sempre o caminho ótimo para o objetivo desde que combinatória fazendo uma procura exaustiva, sendo assim considerados métodos cegos ou não informados é necessário esse caminho exista. utilizar alternativas mais “inteligentes”. Se h’ é um limite inferior de h então o algoritmo é admissível. A admissibilidade implica que: A alternativa é a utilização de Métodos Heurísticos. Estes métodos aproveitam-se do facto de por vezes ser possível Quando o A* expande um nó (n) já encontrou um caminho ótimo para (n) utilizar regras empíricas para acelerar a procura. A ideia central é evitar considerar todas as alternativas, focando apenas Quando o A* expande um nó (n) a função de avaliação f’ não é maior que o custo real f. nas que têm mais interesse. O interesse de um nó é calculado através de funções de avaliação. As regras utilizadas em cada problema são especificas para esse mesmo problema e podem nem resultar. Informação Heurística Uso de Funções de Avaliação Usar h’(n) = 0 reflete a ausência total de conhecimento acerca do domínio de aplicação pelo que embora o algoritmo Como foi dito anteriormente é utilizada uma função de avaliação para determinar o interesse dos nós f(n). Por seja admissível é pouco prático. Um algoritmo A é mais informado do que um algoritmo B se e só se h(A) > h(B) para convenção a lista de nós ABERTOS é ordenada por ordem crescente de f(n), em que f(n) é o valor da função de avaliação todos os estados exceto os estados objetivo. aplicada ao nó. Um algoritmo que use esta convenção para realizar procura em espaço de estados cuja estrutura seja do tipo “Grafo Consistência Acíclico”, consiste na seguinte sequencia de passos: Pode demonstrar-se que se a heurística for consistente o A* nunca expande mais nós do que um algoritmo A com 1. Nó inicial à ABERTOS. Faz f(s) = 0 informação heurística menor ou igual. 2. Se ABERTOS vazia, falha 3. Remove o nó de ABERTOS (n) com menor custo (f) e coloca-o em FECHADOS Uma heurística é consistente se h’(m) – h’(n) = h’(n0) ) 4. Só se expandem nós com f’(n)