Computer Science › Inteligência + Teoria
Um agente como qualquer coisa que percebe seu ambiente por meio de sensores e age sobre ele por meio de atuadores, e a racionalidade como escolher, a cada passo, a ação que se espera que melhor alcance os objetivos do agente dado o que ele percebeu até ali, e não a ação que se prova ótima em retrospecto.
O framework PEAS (Performance, Environment, Actuators, Sensors) para especificar uma tarefa com precisão, as propriedades que tornam um ambiente mais difícil que outro (parcialmente observável, estocástico, sequencial, dinâmico, contínuo, com vários agentes) e a hierarquia de quatro níveis de projetos de agente (reflexo, baseado em modelo, baseado em objetivo, baseado em utilidade), em que cada nível acrescenta um mecanismo que faltava ao anterior.
Buscar em uma árvore de jogo do mesmo jeito que a DFS explora um grafo, só que com dois jogadores alternando turnos com objetivos opostos. MAX tenta maximizar a utilidade final, MIN tenta minimizá-la, e o minimax calcula o valor que cada jogador racional consegue garantir contra um oponente de pior caso.
O minimax calcula exatamente o mesmo valor explorando só uma fração da árvore, acompanhando a melhor garantia que cada jogador já tem e cortando qualquer ramo que não tem como mudar o resultado. É uma ideia de poda, não uma aproximação, e nunca muda a decisão final.
O minimax presume um adversário perfeitamente racional, mas dados, cartas e oponentes imperfeitos pedem um nó de acaso que tira a média dos resultados ponderada pela probabilidade, em vez de pegar o pior caso. É o mesmo esqueleto de busca em árvore com um tipo de nó trocado, e com a poda em grande parte perdida como consequência.
Um CSP fatora um problema de busca em variáveis, cada uma com um domínio de valores possíveis, e restrições que limitam quais combinações são permitidas. Coloração de mapas, Sudoku e escalonamento viram todos o mesmo formato de problema quando escritos assim, expondo uma estrutura que uma busca genérica no espaço de estados nunca enxergaria.
O backtracking atribui variáveis uma de cada vez e desfaz uma escolha no instante em que ela viola uma restrição; o forward checking vai além, apagando de antemão os valores que se tornaram impossíveis no domínio de cada vizinho não atribuído, para que um beco sem saída seja detectado muito antes de o backtracking chegar até ele.
O AC-3 propaga restrições mais longe que o forward checking ao garantir que todo valor restante de uma variável tenha pelo menos um valor compatível em cada vizinho, enquanto as heurísticas de mínimo de valores restantes e de valor menos restritivo decidem qual variável e qual valor tentar em seguida. É a diferença entre um solver de CSP que se debate e um que quase nem precisa buscar.
Os mesmos conectivos proposicionais já vistos como lógica formal, agora usados como uma base de conhecimento que um agente pode consultar. TELL acrescenta uma sentença, ASK checa se uma sentença é consequência lógica de tudo o que foi informado até ali, e a verificação de modelos responde a essa pergunta enumerando a tabela-verdade por força bruta.
A verificação de modelos escala muito mal, então raciocinadores reais convertem cada sentença para a forma normal conjuntiva e aplicam repetidamente uma única regra de inferência, a resolução. É prova por contradição repetida até aparecer a cláusula vazia, a mesma ideia de refutação que provou o Problema da Parada, agora automatizada como um procedimento de busca.
A lógica proposicional só consegue dizer que fatos individuais são verdadeiros ou falsos; a lógica de primeira ordem acrescenta os objetos, relações, funções e quantificadores já vistos como matemática pura, permitindo que uma base de conhecimento enuncie uma única sentença, "todo aluno que estuda passa", que vale por infinitos fatos proposicionais de uma vez.
A unificação encontra as ligações de variáveis que fazem duas sentenças de primeira ordem coincidirem, exatamente o mesmo mecanismo de ligação e backtracking já rastreado passo a passo no Prolog, e o encadeamento para frente e para trás o reaproveitam para conduzir tanto a resolução quanto motores reais de consulta de programação lógica.
O STRIPS representa um problema de planejamento como um conjunto de estados e ações em lógica de primeira ordem, com pré-condições e efeitos explícitos, transformando "encontrar uma sequência de ações do início ao objetivo" em um problema de busca sobre o espaço de estados do mundo que as próprias ações do agente conseguem alcançar.
Agentes reais raramente têm a certeza que a lógica pressupõe, então este conceito volta aos axiomas de probabilidade e ao teorema de Bayes já vistos e acrescenta a única ideia que a lógica sozinha não consegue expressar, a independência condicional, a premissa que torna o raciocínio probabilístico sobre muitas variáveis tratável em vez de exponencial.
Uma rede bayesiana é um grafo direcionado acíclico em que a tabela de probabilidade condicional de cada nó depende apenas dos seus pais. É um jeito fatorado de escrever uma distribuição conjunta completa que de outra forma precisaria de uma quantidade exponencial de números, explorando exatamente a estrutura de independência condicional que a maioria dos domínios reais de fato tem.
Responder a uma consulta em uma rede bayesiana, seja enumerando diretamente a distribuição conjunta, seja com o algoritmo de eliminação de variáveis, muito mais barato, que soma as variáveis irrelevantes uma de cada vez e guarda os fatores intermediários em cache em vez de recalcular a conjunta inteira.
Um modelo oculto de Markov encadeia redes bayesianas ao longo de passos de tempo sob a mesma hipótese de Markov já usada na matriz de transição do PageRank, só que agora o estado real nunca é observado diretamente, apenas uma leitura ruidosa de sensor. A filtragem faz exatamente a pergunta que um robô com um sensor pouco confiável realmente precisa responder: em que estado eu provavelmente estou agora?
Dadas crenças como probabilidades e preferências como uma função de utilidade, o princípio da utilidade esperada máxima diz que um agente racional deve escolher a ação cujo retorno médio ponderado pela probabilidade é o maior. É uma única regra de decisão que engloba escolhas com e sem incerteza como casos especiais.
Um MDP estende uma cadeia de Markov com ações e recompensas, e a equação de Bellman expressa o valor de um estado recursivamente em termos dos valores dos estados alcançáveis a partir dele. É a mesma ideia de subestrutura ótima já vista em programação dinâmica, aplicada a decisões sequenciais em vez de a um array de entrada fixo.
Dois algoritmos que resolvem a equação de Bellman de um MDP iterando, em vez de resolvê-la em forma fechada. A iteração de valor atualiza repetidamente o valor de cada estado até convergir; a iteração de política alterna entre avaliar exatamente uma política fixa e melhorá-la. Os dois comprovadamente convergem para a mesma política ótima.
Um capstone que compara cada técnica coberta por esta disciplina (busca adversarial, CSPs, lógica, redes bayesianas, MDPs) pelo formato de problema a que cada uma de fato se encaixa, e um mapa honesto de onde esta disciplina para. Aprendizado por reforço e as técnicas de machine learning que estimam esses modelos a partir de dados pertencem às disciplinas seguintes, não a esta.
Part of the Computer Science curriculum.
Um agente como qualquer coisa que percebe seu ambiente por meio de sensores e age sobre ele por meio de atuadores, e a racionalidade como escolher, a cada passo, a ação que se espera que melhor alcance os objetivos do agente dado o que ele percebeu até ali, e não a ação que se prova ótima em retrospecto.
O framework PEAS (Performance, Environment, Actuators, Sensors) para especificar uma tarefa com precisão, as propriedades que tornam um ambiente mais difícil que outro (parcialmente observável, estocástico, sequencial, dinâmico, contínuo, com vários agentes) e a hierarquia de quatro níveis de projetos de agente (reflexo, baseado em modelo, baseado em objetivo, baseado em utilidade), em que cada nível acrescenta um mecanismo que faltava ao anterior.
Buscar em uma árvore de jogo do mesmo jeito que a DFS explora um grafo, só que com dois jogadores alternando turnos com objetivos opostos. MAX tenta maximizar a utilidade final, MIN tenta minimizá-la, e o minimax calcula o valor que cada jogador racional consegue garantir contra um oponente de pior caso.
O minimax calcula exatamente o mesmo valor explorando só uma fração da árvore, acompanhando a melhor garantia que cada jogador já tem e cortando qualquer ramo que não tem como mudar o resultado. É uma ideia de poda, não uma aproximação, e nunca muda a decisão final.
O minimax presume um adversário perfeitamente racional, mas dados, cartas e oponentes imperfeitos pedem um nó de acaso que tira a média dos resultados ponderada pela probabilidade, em vez de pegar o pior caso. É o mesmo esqueleto de busca em árvore com um tipo de nó trocado, e com a poda em grande parte perdida como consequência.
Um CSP fatora um problema de busca em variáveis, cada uma com um domínio de valores possíveis, e restrições que limitam quais combinações são permitidas. Coloração de mapas, Sudoku e escalonamento viram todos o mesmo formato de problema quando escritos assim, expondo uma estrutura que uma busca genérica no espaço de estados nunca enxergaria.
O backtracking atribui variáveis uma de cada vez e desfaz uma escolha no instante em que ela viola uma restrição; o forward checking vai além, apagando de antemão os valores que se tornaram impossíveis no domínio de cada vizinho não atribuído, para que um beco sem saída seja detectado muito antes de o backtracking chegar até ele.
O AC-3 propaga restrições mais longe que o forward checking ao garantir que todo valor restante de uma variável tenha pelo menos um valor compatível em cada vizinho, enquanto as heurísticas de mínimo de valores restantes e de valor menos restritivo decidem qual variável e qual valor tentar em seguida. É a diferença entre um solver de CSP que se debate e um que quase nem precisa buscar.
Os mesmos conectivos proposicionais já vistos como lógica formal, agora usados como uma base de conhecimento que um agente pode consultar. TELL acrescenta uma sentença, ASK checa se uma sentença é consequência lógica de tudo o que foi informado até ali, e a verificação de modelos responde a essa pergunta enumerando a tabela-verdade por força bruta.
A verificação de modelos escala muito mal, então raciocinadores reais convertem cada sentença para a forma normal conjuntiva e aplicam repetidamente uma única regra de inferência, a resolução. É prova por contradição repetida até aparecer a cláusula vazia, a mesma ideia de refutação que provou o Problema da Parada, agora automatizada como um procedimento de busca.
A lógica proposicional só consegue dizer que fatos individuais são verdadeiros ou falsos; a lógica de primeira ordem acrescenta os objetos, relações, funções e quantificadores já vistos como matemática pura, permitindo que uma base de conhecimento enuncie uma única sentença, "todo aluno que estuda passa", que vale por infinitos fatos proposicionais de uma vez.
A unificação encontra as ligações de variáveis que fazem duas sentenças de primeira ordem coincidirem, exatamente o mesmo mecanismo de ligação e backtracking já rastreado passo a passo no Prolog, e o encadeamento para frente e para trás o reaproveitam para conduzir tanto a resolução quanto motores reais de consulta de programação lógica.
O STRIPS representa um problema de planejamento como um conjunto de estados e ações em lógica de primeira ordem, com pré-condições e efeitos explícitos, transformando "encontrar uma sequência de ações do início ao objetivo" em um problema de busca sobre o espaço de estados do mundo que as próprias ações do agente conseguem alcançar.
Agentes reais raramente têm a certeza que a lógica pressupõe, então este conceito volta aos axiomas de probabilidade e ao teorema de Bayes já vistos e acrescenta a única ideia que a lógica sozinha não consegue expressar, a independência condicional, a premissa que torna o raciocínio probabilístico sobre muitas variáveis tratável em vez de exponencial.
Uma rede bayesiana é um grafo direcionado acíclico em que a tabela de probabilidade condicional de cada nó depende apenas dos seus pais. É um jeito fatorado de escrever uma distribuição conjunta completa que de outra forma precisaria de uma quantidade exponencial de números, explorando exatamente a estrutura de independência condicional que a maioria dos domínios reais de fato tem.
Responder a uma consulta em uma rede bayesiana, seja enumerando diretamente a distribuição conjunta, seja com o algoritmo de eliminação de variáveis, muito mais barato, que soma as variáveis irrelevantes uma de cada vez e guarda os fatores intermediários em cache em vez de recalcular a conjunta inteira.
Um modelo oculto de Markov encadeia redes bayesianas ao longo de passos de tempo sob a mesma hipótese de Markov já usada na matriz de transição do PageRank, só que agora o estado real nunca é observado diretamente, apenas uma leitura ruidosa de sensor. A filtragem faz exatamente a pergunta que um robô com um sensor pouco confiável realmente precisa responder: em que estado eu provavelmente estou agora?
Dadas crenças como probabilidades e preferências como uma função de utilidade, o princípio da utilidade esperada máxima diz que um agente racional deve escolher a ação cujo retorno médio ponderado pela probabilidade é o maior. É uma única regra de decisão que engloba escolhas com e sem incerteza como casos especiais.
Um MDP estende uma cadeia de Markov com ações e recompensas, e a equação de Bellman expressa o valor de um estado recursivamente em termos dos valores dos estados alcançáveis a partir dele. É a mesma ideia de subestrutura ótima já vista em programação dinâmica, aplicada a decisões sequenciais em vez de a um array de entrada fixo.
Dois algoritmos que resolvem a equação de Bellman de um MDP iterando, em vez de resolvê-la em forma fechada. A iteração de valor atualiza repetidamente o valor de cada estado até convergir; a iteração de política alterna entre avaliar exatamente uma política fixa e melhorá-la. Os dois comprovadamente convergem para a mesma política ótima.
Um capstone que compara cada técnica coberta por esta disciplina (busca adversarial, CSPs, lógica, redes bayesianas, MDPs) pelo formato de problema a que cada uma de fato se encaixa, e um mapa honesto de onde esta disciplina para. Aprendizado por reforço e as técnicas de machine learning que estimam esses modelos a partir de dados pertencem às disciplinas seguintes, não a esta.