Inteligência Artificial - Resumão teórico para P1

Resumo para P1 de Inteligência Artificial.

Aula I

O que é inteligência artificial? Explique de maneira sucinta.

É a área da pesquisa dedicada a buscar métodos ou dispositivos computacionais que possuam ou simulem a capacidade racional de resolver problemas, pensar ou, de forma ampla, ser inteligente. Consegue obter sucesso graças a seu ajuste ao ambiente, percepção de relações entre fatos e regras, buscando atingir um objetivo.

Aula II

O que são agentes? Dê exemplos.

São entidades que agem por outro ou no lugar de outro, e também, qualquer coisa q pode perceber seu ambiente por sensores e agir sobre este ambiente com atuadores.

Exemplos:
humano; 5 sentidos, braços, boca.
robô; câmera, detectores, sonares…

Quais são as principais partes de um agente?

Sensores: coletam informações do ambiente.
Atuadores: permite o agente interagir com o ambiente.
Pecerpções: entradas perceptivas para entender o reusltado da ação ou ambiente.
Ações: tarefas executadas pelos atuadores para modificar o ambiente.
Ambiente: tudo o que se relaciona com o agente (estático ou dinâmico, discreto ou contínuo).

Defina o modelo geral de agente.

Junção de abilities, goals/preferences (objetivos/preferências), prior knowledge(conhecimento prévio), observations, past experiences para gerar as actions.

O que é função agente? Explique percept trace, command trace e belief state.

É a ação executada pelo agente em um determinado tempo e é resultado da análise dos dados utilizados na percepção.

A função executada pode ser:

• percept trace: sequência de todas as percepções passadas, presentes e futuras recebidas pelo controlador. Monitoramento de informação temporal, exemplo: gráficos de ações, estatisticas etc…

• command trace: sequência de todos os comandos passados, presentes e futuros emitidos pelo controlador. Ações a serem tomadas em relação ao Percept trace.

O histórico da funções percept trace e command trace representam o belief state do agente em questão.
O controlador deve manter o belief state do agente e determinar qual comando a ser executado a cada instante.

O estado inclui:

• contadores de programas
• fatos específicos que serão úteis
• estado parcial do ambiente e suas partes dinâmicas
• codifica os objetivos e intenções para alcança-los

Explique agente reativo.

Conjunto de regras que podem ser avaliadas em uma determinada situação, devolvendo assim, uma resposta baseada nela, ou seja, para cada tipo de regra é retornada uma ação.

Função agente reativo: AGENTE-REATIVO([posição,estado]) retorna ação.

Ex: aspirador de pó.

Explique sucintamente as funções: melhorada, objetivo e utilidade.

melhorada: através dos sensores, estado, conhecimento do mundo, o que as ações podem fazer, definem regras/condições para tomar alguma ação e influenciar o ambiente.

objetivo: idem ao ‘melhorada’, porém o agente procura descobrir a consquência da ação (como vai ficar) e troca as ‘regras/condições’ e por ‘objetivos’.

utilidade: idem ao ‘objetivo’, porém após descobrir a consquência da ação (como vai ficar), verifica se ele vai ficar feliz naquele estado, com base na utilidade determinada, removendo-se o ‘objetivo’.

Defina agentes racionais.

Um agente racional deve selecionar uma ação que se espera vir a maximizar sua medida de desempenho para cada sequencia de percepções possíveis.
O conceito de sucesso do agente depende de uma medida de desempenho objetiva.

Ex: quantidade de sujeira aspirada, gasto de energia, gasto de tempo, quantidade de barulho gerado, etc.

Para cada sequência de percepções possíveis:

• Escolha da ação que maximize a medida de desempenho.
• Execução da ação.

Explique sucintamente a função da hierarquia.

Sua função é dividir o corpo do agente em diversos sensores, toda a informação é então enviada a um reasoner (raciocinador) e tal reasoner representa o controlador (cérebro), que envia ações (atuadores) novamente o corpo.

cada camada vê a a camada abaixo como um corpo virtual.
objetivo é manter cada camada o mais simples possível.

Apresente 3 exemplos de modelo PEAS.

Professor, médico e táxi:

Ambiente (local onde ocorre) Professor: sala de aula, aluno Médico: hospital, paciente, equipamentos médicos Táxi: ruas, pistas, rodovia, pedestre, passageiro

Performance (o que quero atingir) Professor: melhores notas dos alunos, melhor desempenho dos alunos Médico: quantidade de pacientes curados Táxi: menor tempo de corrida, maior lucro

Atuadores (o que posso fazer para influenciar) Professor: provas, exercícios, aulas Médico: perguntas de saúde do paciente Táxi: buzina, volante, seta

Sensores (como vou verificar os pontos) Professor: teclado Médico: sintomas Táxi: GPS

Aula III

O que é conhecimento?

É a informação sobre um determinado domínio utilizada para solução de problemas neste mesmo domínio.

Representado por:

• Seleção de uma tarefa ou domínio a ser representada.
• Representação atômica de alguns aspectos do domínio.
• Informa fatos que são verdades (aximomatization).
• Teste com perguntas.

Exemplo de conhecimento utilizando lógica matemática

Drago é um cachorro,
cachorro(Drago),
∀x: cachorro(x) → tem-rabo(x),
tem-rabo(Drago),
Drago tem rabo  

Itens a serem considerados:

• Adequação representacional: representar todo o conhecimento do domínio.
• Adequação inferencial: manipular as estruturas de modo a derivar novas estruturas.
• Eficácia inferencial: incorporar novas informações.
• Eficácia aquisitiva: adquirir novas informações diretamente.

Computação online vs offline

Online: o belief state é a memória de curto prazo, a qual mantém o modelo de ambiente necessário.

Offline: tornar a computação online mais eficiente e efetiva e possui grande quantidade de informações.

Ex: Sistema de diagnóstico médico

• Offline: conjunto de todas as doenças e seus sintomas. Busca por relações entre diversas doenças
• Online: Conhecendo os sintomas de um determinado paciente, busca uma possível doença e suas alternativas de cura

Explique lógica proposicional usando o jogo Hunt the Wumpus.

Também conhecida como lógica Booleana, é a lógica simples que representa a estrutura de sentenças usando conectivos como: “e”, “ou” e “não“. No jogo Hunt the Wumpus, é necessário criar uma tabela verdade grande para representar os fatos com as regras, depois interceptar e verificar se são verdadeiros ou falsos.

É muito simples para representar o conhecimento de ambientes complexos de uma forma concisa.

Possui limitação para descrever um ambiente com muitos objetos.

Dê exemplos de lógica proposicional. Explique a diferença entre a implicação e a equivalência lógica.

⋀ = E lógico
⋁ = OU lógico

P ⋀ Q
P ⋀ Q ⇒ R
(P ⋀ Q) ⋁ S ⇒ R
¬(P ⋀ Q) ⇒ R
¬(P ⋀ Q) ⇒ R ⋁ S

• Implicação lógica P ⇒ Q (=>)
  Se está chovendo então as ruas estão molhadas.
  Se P é verdade então Q é verdade.
  Se P é falso então Q pode ser verdade ou falso.
• Equivalência lógica P ⟺ Q (<=>)
  Se dois lados de um triângulo são iguais então os dois ângulos da base são iguais.

Explique linguagem natural e lógica de primeira ordem? Explique a diferença comparada a lógica proposicional.

Linguagem natural: Objetos: pessoas, casas, números, cores, jogos, séculos, …
Relações:

• unárias: propriedades de um objeto (vermelho, redondo, falso, etc).
• n-árias: relacionam grupos de objetos (irmão de, maior que, interior a, parte de, etc).
• funções: um objeto está relacionado a exatamente um objeto (pai de, melhor amigo de, terceiro turno de, uma unidade maior que, etc).

Lógica de primeira ordem: elaborada em torno de objetos e relações.

A diferença entre Lógica de Primeira Ordem e a Lógica Proposicional é o compromisso ontológico.

LP: pressupõe fatos válidos ou não-válidos.
LPO: pressupõe que o mundo consiste em objetos com certas relações (válidas ou não).

Apresente 2 exemplos de LPOs.

∀x = para todo x
∃x = para algum x

∀x ¬Gosta(x,Cenouras) ≣ ¬∃x Gosta(x,Cenouras) =  
“todo mundo detesta cenouras” =  
“não existe alguém que goste de cenouras”.  

∀x¬P ≣ ¬∃xP  

Ou então,

∀x Gosta(x,Sorvete) ≣ ¬∃x ¬Gosta(x,Sorvete) =  
“todo mundo gosta de sorvete” =  
“não existe alguém que não goste de sorvete”  

∀xP ≣ ¬∃x¬P  

Aula IV

Explique o que são fatos e o que são regras.

Fatos: proposição onde uma nova informação é dada e estabelecem um relacionamento existente.
Regras: expressão de dependência entre um fato e outro fato.

Explique as relações em prolog.

As relações usam a implicação e alguns operadores para procurar a respostas tendo como base os fatos em KB (knowledge base).

Explique os operadores em Prolog.

X = Y igual a
X = Y não igual a
X < Y menor que
Y > X maior que
Y =< X menor ou igual a
Y >= X maior ou igual a

Explique os sinais em prolog. Como fazer perguntas em Prolog?

:- é implicação

ex: avo(X,Y) :- pai(X, Z), pai(Z, Y).

. todo final de comando
; representa OU lógico
, representa E lógico
?- é pergunta

ex: ?- avo(X, paulo).

Apresente algumas relações em prolog.

avo(X,Y) :- pai(X, Z), pai(Z, Y).

filho(Y,X) :- progenitor(X,Y).
mae(X,Y) :- progenitor(X,Y), mulher(X).
avo(X,Z) :- progenitor(X,Y), progenitor(Y,Z).
irmao(X,Y) :- progenitor(Z,X), progenitor(Z,Y).
ancestral(X,Z) :- progenitor(X,Z).
ancestral(X,Z) :- progenitor(X,Y), ancestral(Y,Z).

Aula V

O que é problema de busca?

Problema de busca é o processo que tenta encontrar uma sequência de ações que leva de um estado até um objetivo. Uma vez encontrada a solução, o agente pode executar a sequência para chegar no objetivo.
Para solucionar o problema:
definir um espaço de estados com configurações possíveis.
especificar um ou mais estados como início da solução (estados iniciais).
estados aceitáveis como soluções (estados finais).
descrição das ações através de regras.

Defina estado inicial e custo.

Estado inicial são um ou mais estado definidos como início da solução.
Custo é a distância real do ponto A até B.

Explique a busca cega e seus tipos.

A busca cega não sabe qual é o melhor nó da fronteira a ser seguido. Existem os algoritmos de Busca em Largura (BFS) e Busca em Profundidade (DFS).

• BFS: Apó o nível 0 gerar o nível 1, analisa-se as todas as “bolinhas” geradas da esquerda para a direita, e então, segue para o próximo nível.
  Usa uma fila (de vértices) em um estilo iterativo.

• FS: Expande-se o estado mais à esquerda e no nível mais profundo.
  Repete-se até encontrar a solução ou um beco.
  No caso do beco, o algoritmo retorna e reinicia a busca do próximo estado (direita) ainda não expandido -> backtracking.
  Usa uma pilha em um estilo recursivo.

Explique a busca heurística e suas tipos.

A busca heurísticas estima o melhor nó a ser seguido através de conhecimento específicos do problema.

São usadas quando: não pode ter solução exata por de ambiguidades em sua formação. ex: diagnóstico médico. pode ter uma solução exata, mas o custo computacional é muito alto. ex: xadrez.

• Busca Gulosa: semelhante à busca cega, mas uma função heurística define qual nó deve ser expandido.
  não é completa (pode entrar em ciclos e não encontrar a solução ou pode se perder em um caminho infinito e nunca retroceder ) e não é ótima.

• A*: É a técnica mais utilizada e permite a expansão de uma quantidade menor de nós.
  Sua função de avaliação é f(n) = g(n) + h(n).

  g(n): distância real (custo acumulado).
  h(n): distância em linha reta (heurística).

  É totalmente eficiente, pois analisa o custo de forma global (custo de todos da fronteira).

Por que o algoritmo A* se destaca?

Este algoritmo é totalmente eficiente pois analisa o custo de forma global (custo de todos da fronteira) com a distância em linha reta, garantindo expandir menos nós e alcançar baixo custo.

Sua função de avaliação é f(n) = g(n) + h(n).

g(n): distância real (custo acumulado).
h(n): distância em linha reta (heurística).

Aula VI

Explique buscal local.

Busca local opera em um único estado corrente ao invés de vários, o caminho percorrida não é guardado e resolvem problemas de otimização, sendo usado em problemas puros de otimização.
As vantagens são: ocupam pouca memória e encontram soluções razoáveis em espaços infinitos.

Pontos importantes
maximizar função -> maior pico.
minimizar função -> vale mais fundo.
completo se o algoritmo atingir o estado objetivo.
ótimo se consegue encontrar o máximo e mínimo.

Qual a diferença de Hill Climbind e Simulated Annealing? Seja sucinto.

A diferença é que Hill Climbing sempre escolhe o primeiro melhor vizinho como próximo melhor estado. Já, o Simulate Annealing escolhe seus movimentos de forma aleatória em vez do melhor movimento, evitando ficar “preso” em máximos locais, planícies ou platôs.

Hill Climbing:

“é como subir o Evereste com nevoeiro cerrado e amnésia”.

Simulatd Annealing

“O algoritmo começa com uma solução inicial gerada aleatoriamente e melhora-a incrementalmente aceitando soluções menos desejáveis com uma certa probabilidade. A probabilidade de aceitar uma solução pior diminui à medida que o algoritmo progride, o que lhe permite escapar da ótima local e encontrar o ótimo global.”

Explique os casos de máximos local, planícieis e platôs. Como isso pode afetar o máximo global?

O máximo global é o objetvo que a função precisa alcançar, porém, em algoritmos como o Hill Climbing, onde o melhor vizinho já é diretamente escolhido, o ponto X da função pode ficar preso em máximos locais (um ponto máximo naquela região com vizinhos menores, porém não atinge o máximo global), planícies (não existe vizinho melhor que o atual, mas apenas igual) ou platôs (planícies em um pico). Ou seja, isso afeta negativamente a execução do algoritmo dito.

Explique os passos de Hill Climbing.

• Iniciar com ponto x em uma região aleatória permitida do problema.
• A cada iteração, um novo ponto x’ é escolhido através de uma perturbação do ponto inicial, ou seja, x’ é vizinho de x.
• Se o novo ponto apresentar melhor valor, o novo ponto se torna o ponto atual.

Termina quando:

Nenhuma melhora é alcançada.
Número fixo de iterações foi efetuado.
Objetivo atingido.

Explique os passos de Simulated Annealing.

• Iniciar com ponto x em uma região aleatória permitida do problema.
• A cada iteração, um novo ponto x’ é escolhido através de uma perturbação do ponto inicial, ou seja, x’ é vizinho de x. x’ pertence a N (x).
• Determinar a energia de x e x’ (E(x) e E(x’)) e verificar a variação de energia do sistema ∆E = E(x’) − E(x).
• Se ∆E ≤ 0, então x’ se torna o ponto atual (x ← x’).
• Caso contrário a probabilidade de x’ se tornar ponto atual é dada por um caso da distribuição de Boltzmann, P(∆E) = exp(−∆E/T).

Termina quando:

Nenhuma melhora é alcançada.
Número fixo de iterações foi efetuado.
Temperatura T atingiu valor mínimo.