Inteligência Artificial - Resumos PDF

**[Inteligência Artificial ]** **[1 - Introdução]** **O que é a Inteligência Artificial** Existem muitas definições de Inteligência. São aspetos a considerar como definição de inteligência a capacidade de resolver problemas, a capacidade de usar o conhecimento, ou seja, raciocinar e capacidade de...

**[Inteligência Artificial ]** **[1 - Introdução]** **O que é a Inteligência Artificial** Existem muitas definições de Inteligência. São aspetos a considerar como definição de inteligência a capacidade de resolver problemas, a capacidade de usar o conhecimento, ou seja, raciocinar e capacidade de aprender. 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: - Jogos como Xadrez ou Damas - Demonstração de Teoremas - Linguagem Natural Atualmente é possível a resolução de problemas logísticos, exploração de dados e diagnóstico médico através da Inteligência Artificial. Até mesmo em jogos como o Xadrez a Inteligência Artificial ganhou ao campeão mundial. **Redes Neuronais** É 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. Redes neuronais são aplicadas em: - Reconhecimento de padrões - Robótica e Controlo - Processamento de dados e extração de informação - Processamento da linguagem natural **Â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 resolvidos métodos convencionais como formulas matemáticas ou algoritmos. No entanto existem dois problemas principais com os quais a inteligência artificial tem de lidar: - A incapacidade de usar modelos da realidade Usar modelos mentais da forma como os especialistas resolvem os problemas. - Explosão combinatória Usar conhecimento para reduzir o espaço de procura (Heurísticas) **Inteligência Artificial e Conhecimento** 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 aplicação comercial: O Sistema Pericial. O conhecimento a induzir na Inteligência Artificial deve ser representado de forma a: - Permitir representar regras gerais - Ser compreendido pelas pessoas que o fornecem ao sistema - Ser facilmente modificável Este conhecimento pode ser impreciso ou incompleto e pode ser usado para superar o seu próprio volume. **Avaliação de uma Inteligência Artificial -- Teste de Turing** No teste de Turing existem 2 canais de comunicação idênticos e independentes (1 pessoa e uma máquina). Se ao fim de 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 inteligente. Atualmente a Inteligência Artificial está mais interessada em fazer máquinas que ajudem as pessoas a resolver 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). 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 seres humanos. **Resolução de Problemas** 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. **Heurísticas** Para resolver o problema da explosão combinatória, a Inteligência Artificial recorre à utilização de heurísticas. O conhecimento heurístico é: - De natureza não científica - Incerto - 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. **[2 -- Procura em Espaço de Estados]** **Espaço de Estados** 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 ser equacionado em termos de: Estados e Operadores. Terá ainda de ser definido o estado final. **Representação** **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 gerou / Heurística / Pontuação / Outros tipos de informação relevante **Arco --** Cada arco do grafo representa uma transição de estado ao longo do processo de resolução do problema. **Estratégias de Exploração de Arvores** **Conceitos** - Nó inicial - Sucessores de um nó: Nós gerados pela aplicação dos operadores lógicos - 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 - Lista de nós fechados: Lista com os nós que já foram expandidos **Métodos de Procura -- Breadth-First** Neste método assume-se que o nó inicial não é um nó objetivo. Este método encontra sempre a solução que corresponde ao caminho mais curto e caso não haja solução termina com falha caso o grafo seja finito ou não termina caso o grafo seja infinito 1. Nó inicial Abertos 2. Se Abertos estão vazios, falha 3. Remove o primeiro nó de ABERTOS (nó n) e coloca-o em FECHADOS 4. Expande o nó n. Coloca os sucessores no fim de ABERTOS e os ponteiros para n 5. Se algum sucessor for um nó objetivo sai e dá a solução. Caso contrário vai para 2 **Métodos de Procura -- Custo Uniforme** 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. 1. Nó inicial ABERTOS. Faz g(s) = 0 2. Se ABERTOS vazio, falha 3. Remove o nó de ABERTOS (n) com menor custo (g) e coloca-o em FECHADOS 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 6. Vai para 2. **Métodos de Procura -- Depth-First** Neste método convenciona-se que a profundidade do nó raiz é zero e é definido um nível de profundidade máximo, a 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. 1. Nó inicial ABERTOS 2. Se ABERTOS vazia, falha 3. Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS 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 6. Se algum dos sucessores é um nó objetivo sai e dá a solução. Caso contrário volta para 2. **Grafos em vez de Arvores** Se o espaço de estados for um grafo, é preciso modificar os algoritmos estudados. - Breadth-First - Reconhecer se um estado sucessor já está em ABERTOS ou em FECHADOS, e nesse caso não colocar o nó correspondente em ABERTOS - Custo Uniforme - Se o sucessor de n está em ABERTOS - 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 - Se o sucessor está em fechados ignora-se o sucessor de n - Depth-First - 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 - 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 - Caso contrário, abandona o nó gerado. **Métodos Heurísticos ou "Informados"** Para combater o facto de que todos os métodos estudados até este ponto não resolvem o problema da explosão combinatória fazendo uma procura exaustiva, sendo assim considerados métodos cegos ou não informados é necessário utilizar alternativas mais "inteligentes". A alternativa é a utilização de Métodos Heurísticos. Estes métodos aproveitam-se do facto de por vezes ser possível utilizar regras empíricas para acelerar a procura. A ideia central é evitar considerar todas as alternativas, focando apenas 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. **Uso de Funções de Avaliação** Como foi dito anteriormente é utilizada uma função de avaliação para determinar o interesse dos nós f(n). Por 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 aplicada ao nó. Um algoritmo que use esta convenção para realizar procura em espaço de estados cuja estrutura seja do tipo "Grafo Acíclico", consiste na seguinte sequencia de passos: 1. Nó inicial ABERTOS. Faz f(s) = 0 2. Se ABERTOS vazia, falha 3. Remove o nó de ABERTOS (n) com menor custo (f) e coloca-o em FECHADOS 4. Expande o nó (n) e calcula o (f) de cada um dos seus sucessores 5. Colocar os sucessores que ainda não existem em ABERTOS nem FECHADOS em ABERTOS, por ordem de f colocando também os ponteiros para n 6. Se algum sucessor for um nó objetivo termina e dá a solução. 7. Associa aos sucessores já em ABERTOS ou FECHADOS o menor dos valores de f (existente ou agora calculado). Coloca em ABERTOS os sucessores que estavam em FECHADOS cujos valores de f baixaram. Redireciona para (n) os ponteiros de todos os nós cujos valor de f baixaram. 8. Vai para 2. **Algoritmo A\*** O algoritmo anterior não especifica o tipo de função de avaliação. Se esta consistir em f(n) = g(n) + h(n), em que g(n) é o custo do nó e h(n) é o seu valor heurístico designa-se essa família de algoritmos por A. Se se modificar o algoritmo de procura ordenada por forma a que o teste de estado objetivo seja feito sobre o nó (n) que é selecionado depois de colocar todos os sucessores em ABERTOS, tem-se o algoritmo A\* **Admissibilidade** Um algoritmo diz-se admissível se, para qualquer grafo, descobre sempre o caminho ótimo para o objetivo desde que esse caminho exista. Se h' é um limite inferior de h então o algoritmo é admissível. A admissibilidade implica que: - Quando o A\* expande um nó (n) já encontrou um caminho ótimo para (n) - Quando o A\* expande um nó (n) a função de avaliação f' não é maior que o custo real f. **Informação Heurística** Usar h'(n) = 0 reflete a ausência total de conhecimento acerca do domínio de aplicação pelo que embora o algoritmo 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 todos os estados exceto os estados objetivo. **Consistência** Pode demonstrar-se que se a heurística for consistente o A\* nunca expande mais nós do que um algoritmo A com informação heurística menor ou igual. Uma heurística é consistente se h'(m) -- h'(n) \