Inteligência Artificial: Conceitos e Definições

Inteligência Artificial e Conhecimento

• Inteligência Artificial necessita de conhecimento, frequentemente volumoso, difícil de caracterizar precisamente e em constante mudança.
• A base de muitas aplicações comerciais é o Sistema Pericial.
• O conhecimento usado na IA deve ser representável para: permitir a representação de regras gerais, ser compreensível para quem o fornece ao sistema e ser facilmente modificável.
• O conhecimento pode ser impreciso ou incompleto, permitindo superar o seu próprio volume.

Métodos de Procura - Custo Uniforme

• Variante do Breadth-First focada em minimizar o custo, em vez da distância, quando os custos dos arcos variam.
• Algoritmo garante a minimização do custo.
• Passos:
  • Nó inicial inserido em ABERTOS com g(s) = 0.
  • Se ABERTOS estiver vazio, falha.
  • Remover da lista de ABERTOS o nó (n) com menor custo (g) e colocá-lo em FECHADOS.
  • Se (n) for o nó objetivo, terminar e apresentar a solução.
  • Expandir o nó (n). Adicionar os sucessores a ABERTOS, usando ponteiros para (n) e calculando o g de cada sucessor.
  • Voltar ao passo 2.

Avaliação de uma Inteligência Artificial - Teste de Turing

• Teste de Turing: dois canais de comunicação independentes (um com pessoa e outro com máquina); se depois de interação razoável for impossível distinguir a pessoa da máquina, a máquina é considerada inteligente.
• A Inteligência Artificial moderna se preocupa mais com a colaboração Humano-Máquina, valorizando as capacidades de ambos, do que a imitação humana.

Métodos de Procura - Depth-First

• A profundidade do nó raiz é zero; define-se um nível de profundidade máxima onde os nós não se expandem.
• Re-calcular profundidade de nós já presentes em Abertos ou Fechados.
• Passos:
  • Nó inicial em ABERTOS.
  • Se ABERTOS estiver vazio, falha.
  • Remover o primeiro nó de ABERTOS (n) e colocá-lo em FECHADOS.
  • Se a profundidade de (n) exceder o limite, voltar ao passo 2.
  • Expandir o nó (n). Adicionar os sucessores ao início de ABERTOS, com ponteiros para (n).
  • Se algum sucessor for o nó objetivo, terminar e apresentar a solução; caso contrário, voltar ao passo 2.

Resolução de Problemas

• A resolução de problemas em IA baseia-se em usar conhecimento para reduzir a explosão combinatória de explorar todos os caminhos possíveis.

Heurísticas

• Para resolver o problema da explosão combinatória, a IA usa heurísticas.
• O conhecimento heurístico é não científico, incerto e baseado em experiência passada.
• O objetivo é sacrificar a solução ótima em prol da garantia de encontrar uma solução satisfatória, mesmo que não seja a melhor.

Grafos em vez de Árvores

• Se o espaço de estados for um grafo, os algoritmos precisam de ser modificados.
• Breadth-First: Verificar se um estado sucessor já está em ABERTOS ou FECHADOS; caso positivo, o nó não é adicionado a ABERTOS.
• Custo Uniforme: Se o sucessor de n está em ABERTOS e g (sucessor de n) > g (sucessor em ABERTOS), o sucessor não é adicionado; caso contrário, o sucessor de n substitui o que está em ABERTOS. Se o sucessor está em FECHADOS, ignorá-lo.
• Depth-First: Se um nó com o mesmo estado já estiver em ABERTOS, o nó gerado é descartado (custo g menor ou igual). Se o nó estiver em FECHADOS e seu custo for maior ou igual, substituir o nó antigo pelo gerado em ABERTOS, incluindo ponteiros para o nó gerado; caso contrário, descartar o nó gerado.

Algoritmos de Procura em Espaço de Estados - Procura com Memória Limitada

• IDA*: garante a descoberta da solução ótima se a heurística for admissível.
• Passos: aplicar repetidamente o método de procura em profundidade com limiares de profundidade variáveis baseados em f.
  • O limiar inicial (L) é calculado como f'(no) = g(no) + h'(no).
  • Expandir nós com f'(n) ≤ L.
  • Se a solução não for encontrada, recalcular L como o mínimo valor de f(n) dos nós visitados mas não expandidos.
• RBFS: variante do IDA* que recalcula f' de um nó e de seus antecessores (backup).
• SMA*: eficiente usando toda a memória disponível, evitando repetição de estados. Algoritmo completo se a memória permitir o caminho mais curto; ótimo se a memória permitir o caminho de menor custo.
  • No caso de falta de memória, desprezar o nó com maior f(n).

Métodos Heurísticos ou "Informados"

• Usam regras empíricas para acelerar a procura, focadas em nós mais promissores.
• Utilizam funções de avaliação (f(n)) para determinar o interesse dos nós. Geralmente, a lista de nós ABERTOS é organizada por ordem crescente de f(n).
• Passos:
  • Nó inicial em ABERTOS com f(s) = 0.
  • Se ABERTOS estiver vazio, falha.
  • Remover o nó de ABERTOS (n) com menor f e colocá-lo em FECHADOS.
  • Expandir (n) e calcular f de seus sucessores.
  • Adicionar os sucessores novos a ABERTOS (em ordem de f), com ponteiros para (n).
  • Se um sucessor for objetivo, terminar.
  • Atualizar f de sucessores existentes ou em FECHADOS, para o menor valor encontrado.
  • Recolocar em ABERTOS sucessores de FECHADOS com f reduzido; redirecionar ponteiros para (n) onde f baixou.
  • Voltar para o passo 2.

Algoritmo de Dijkstra

• Algoritmo para encontrar o caminho mais curto em grafos com pesos nos arcos.
• Passos: iniciar com estimativa de custo 0 para a raiz e infinito para outros nós; em cada etapa, encontrar o nó não processado com menor distância à raiz; atualizar distâncias dos vizinhos se necessário.

Medidas de Desempenho

• Possíveis medidas para comparar técnicas de busca: Penetrância (comprimento do caminho / número total de nós gerados) e Fator de Ramificação Média.

Algoritmo A*

• Família de algoritmos de procura em espaço de estados onde f(n) = g(n) + h(n), onde g(n) é o custo do nó e h(n) é o valor heurístico.

Representação de Jogos

• Jogos podem ser representados de forma extensiva (grafo) ou normal (matriz de pagamentos, não útil para jogos sequenciais).
• Heurísticas e funções de avaliação são usadas para auxiliar na escolha da melhor jogada.
• O Princípio da Utilidade Esperada permite valorar a distribuição de probabilidades dos resultados de uma decisão.

Algoritmo MINIMAX

• Algoritmo para determinar a estratégia ótima para o jogador máximo.
• Gera toda a árvore de procura.
• Aplica a função de utilidade a cada nó terminal e usa para calcular a utilidade dos nós dos níveis superiores da árvore.
• Se for um lance do jogador mínimo, o valor calculado é o mínimo em cada nível; se for do jogador máximo, o valor é o máximo.
• Continua o processo de backup até o nó inicial.

Algoritmo MINIMAX com cortes Alfa-Beta

• A procura alfabeta é uma versão do MINIMAX que usa cortes.
• Alfa representa o valor da melhor escolha encontrada até então para o jogador máximo; beta representa o valor da melhor escolha para o jogador mínimo.

Tabelas de Transposição (Hash Tables)

• Usadas em alguns jogos de informação perfeita para acelerar a procura, usando cache dos estados e suas avaliações.

Programação Dinâmica e Memoização

• Abordagem de dividir um problema complexo em subproblemas menores, resolvendo-os apenas uma vez e armazenando as soluções.

Limitação da Árvore de Procura

• Métodos para limitar a árvore de procura: limite de profundidade fixo, Iterative Deepening.

Teoria de Jogos

• Tipos de Jogos: 2 adversários/pessoas, sequenciais (incluindo informação perfeita), simultâneos, simétricos, soma zero, não cooperativos.
• Equilíbrio de Nash: solução para jogos não cooperativos onde cada jogador toma a melhor decisão possível dada a escolha do outro e nenhum pode melhorar unilateralmente.

Algoritmo NEGAMAX

• Versão do MINIMAX que troca o sinal em cada nível após o backup.

Raciocínio Lógico em Sistemas Periciais

• Tipos de Raciocínio: dedutivo, indutivo, abdutivo.

Sistemas Periciais

• Aplicações que resolvem problemas complexos como peritos humanos, usando heurísticas e conhecimento especializado.

Modelos

• Modelos são representações simplificadas da realidade.

Tipos de Lógicas

• Proposicional, Predicativa, Modal.

Fontes de Incerteza

• Incerteza em sistemas periciais pode ser subjetiva (lógica fuzzy) ou objetiva (probabilidades - Lei de Bayes).

Aquisição de Conhecimento

• Duas abordagens principais para a aquisição de conhecimento: direta (especialista) e através de registos históricos (indução de regras).

Conversão de Árvores de Decisão em Regras

• Passos para converter uma árvore de decisão em um conjunto de regras.

Árvores Mínimas

• Árvores de decisão otimizadas por algoritmos como o ID3, baseados em minimização de entropia informacional.

Eficiência dos Sistemas de Produção

• Eficiência pode ser aumentada pela manutenção dos resultados de testes anteriores e pelas características de similaridade estrutural e redundância temporal.

Outros algoritmos

• Algoritmos relacionados a MINIMAX: SSS*, DUAL*, SCOUT, PVS/NEGASCOUT, MTD(F), BNS.

Estrutura de Dados de Suporte

• Dados de suporte representados em Grafo Dirigido Acíclico. Tipos de nós em RETE (raiz, padrão e junção).

MYCIN

• Método de cálculo do fator de confiança da conclusão de uma regra.

Desenvolvimento de Sistemas Periciais

• Abordagem espiral para o desenvolvimento de sistemas periciais.
• Considerações para escolha do domínio de aplicação.
• Tipos de tarefas, participantes, e requisitos.

Teste seus conhecimentos sobre Inteligência Artificial com questões que abrangem desde a definição até os aspectos técnicos da resolução de problemas. Este quiz explora a busca em espaço de estados e o papel dos operadores, características de redes neurais, e os desafios comuns na área. Desfrute de um desafio acadêmico e refine seu entendimento sobre IA!