Blog

De Nate Soares. 12 de setembro de 2016.

O MIRI está lançando um artigo apresentando um novo modelo de raciocínio dedutivamente limitado: “ Indução lógica ”, de autoria de Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, minha e Jessica Taylor. Os leitores talvez queiram começar com a versão resumida.

Considere um cenário onde um raciocinador está observando um processo dedutivo (como uma comunidade de matemáticos e programadores de computador) e esperando por provas de várias afirmações lógicas (como a conjectura abc, ou “este programa de computador tem um bug”), enquanto faz suposições sobre quais afirmações serão verdadeiras. Grosso modo, nosso artigo apresenta um algoritmo computável (embora ineficiente) que supera a dedução, atribuindo altas probabilidades subjetivas a conjecturas prováveis ​​e baixas probabilidades a conjecturas refutáveis ​​muito antes que as provas possam ser produzidas.

Este algoritmo possui um grande número de propriedades teóricas interessantes. Ainda grosso modo, o algoritmo aprende a atribuir probabilidades a frases de maneira que respeite qualquer padrão lógico ou estatístico que possa ser descrito em tempo polinomial. Além disso, aprende a raciocinar bem sobre suas próprias crenças e a confiar em suas crenças futuras, evitando paradoxos. Citando o resumo:

Todas essas propriedades e muitas outras decorrem de um único critério de indução lógica, que é motivado por uma série de analogias de negociação de ações. Grosso modo, cada frase lógica φ está associada a uma ação que vale $ 1 por ação se φ for verdadeiro e nada caso contrário, e interpretamos o estado de crença de um raciocinador logicamente incerto como um conjunto de preços de mercado, sendo que ℙ_n (φ) = 50% significa que no dia n, ações de φ podem ser compradas ou vendidas do raciocinador por 50 centavos. O critério da indução lógica diz (de forma muito aproximada) que não deve haver nenhuma estratégia de negociação computável em tempo polinomial com tolerância ao risco finita que obtenha lucros ilimitados nesse mercado ao longo do tempo.

Esse critério é análogo ao critério do “nenhum livro holandês” usado para apoiar outras teorias do raciocínio ideal, como a teoria da probabilidade bayesiana e a teoria da utilidade esperada. Acreditamos que o critério da indução lógica pode desempenhar um papel semelhante para raciocinadores com limitações dedutivas, captando algo do que entendemos por “bom raciocínio” nesses casos.

O algoritmo de indução lógica que fornecemos é mais teórico do que prático. Pode ser considerado uma contrapartida à teoria da inferência indutiva de Ray Solomonoff, que forneceu um método incomputável para a gestão ideal da incerteza empírica, mas nenhum método correspondente para raciocinar sob incerteza sobre frases lógicas ou matemáticas.¹ A indução lógica preenche essa lacuna.

Qualquer algoritmo que satisfaça o critério da indução lógica exibirá as seguintes propriedades, entre outras:

1. Convergência-limite e coerência-limite: as crenças de um indutor lógico são perfeitamente consistentes no limite. (Cada frase comprovadamente verdadeira acaba obtendo probabilidade 1; toda frase comprovadamente falsa acaba obtendo probabilidade 0; se φ implica comprovadamente ψ, então a probabilidade de φ converge para algum valor não superior à probabilidade de ψ; e assim por diante.)
2. Indução de demonstrabilidade: os indutores lógicos aprendem a reconhecer qualquer padrão em teoremas (ou contradições) que possa ser identificado em tempo polinomial.
   • Consideremos uma sequência de conjecturas geradas por um matemático brilhante, como Ramanujan, que são difíceis de provar, mas que continuam a revelar-se verdadeiras. Um indutor lógico reconhecerá esse padrão e começará a atribuir altas probabilidades às conjecturas de Ramanujan bem antes de ter recursos suficientes para verificá-las.
   • Como outro exemplo, considere a sequência de afirmações “na entrada n, este cálculo de longa duração produz um número natural entre 0 e 9”. Se todas essas afirmações forem verdadeiras, então (grosso modo) um indutor lógico aprende a atribuir a elas altas probabilidades tão rápido quanto podem ser geradas. Se forem todas falsas, um indutor lógico aprende a atribuir a elas probabilidades baixas tão rápido quanto podem ser geradas. Nesse sentido, aprende indutivamente a prever como os programas de computador se comportarão.
   • Da mesma forma, dado qualquer método de tempo polinomial para escrever programas de computador que param, os indutores lógicos aprendem a acreditar que eles irão parar aproximadamente tão rápido quanto os códigos-fonte podem ser gerados. Além disso, dado qualquer método de tempo polinomial para escrever programas de computador que provavelmente não conseguem parar, os indutores lógicos aprendem a acreditar que eles não conseguirão parar tão rápido quanto os códigos-fonte podem ser gerados. Quando se trata de programas de computador que não param, mas para os quais não há prova desse fato, os indutores lógicos aprenderão a não antecipar que o programa irá parar tão cedo, mesmo que não possam dizer se o programa irá parar a longo prazo. Dessa forma, os indutores lógicos dão algum apoio formal à intuição de muitos cientistas da computação de que, embora o problema da parada seja indecidível em geral, isso raramente interfere no raciocínio sobre programas de computador na prática.²
3. Coerência afim: os indutores lógicos aprendem a respeitar as relações lógicas entre os valores de verdade de diferentes frases, muitas vezes muito antes de as frases poderem ser provadas. (P. ex., eles aprenderão, para programas arbitrários, que “este programa produz 3” e “este programa produz 4” são mutuamente excludentes, muitas vezes muito antes de serem capazes de avaliar o programa em questão.)
4. Aprendendizado de frequências pseudoaleatórias: quando confrontados com uma sequência suficientemente pseudoaleatória, os indutores lógicos aprendem a usar resumos estatísticos apropriados. Por exemplo, se o (n, n)-ésimo dígito de Ackermann na expansão decimal de π for difícil de prever para n grande, um indutor lógico aprenderá a atribuir ~10% de probabilidade subjetiva à afirmação “o (n, n)-ésimo dígito de Ackermann na expansão decimal de π é 7.”
5. Calibração e imparcialidade: em sequências às quais um indutor lógico atribui ~30% de probabilidade, se a frequência média da verdade convergir, então ela converge para ~30%. Na verdade, em qualquer subsequência na qual a frequência média da verdade converge, não existe um método eficiente para encontrar um viés nas crenças do indutor lógico.
6. Indução científica: indutores lógicos podem ser usados ​​para fazer previsão de sequência e, ao fazê-lo, dominam a semimedida universal.
7. Fechamento sob condicionamento: as probabilidades condicionais nesta estrutura são bem-definidas e os indutores lógicos condicionais também são indutores lógicos.³
8. Introspecção: os indutores lógicos têm crenças precisas sobre suas próprias crenças, de uma maneira que evita os paradoxos-padrão da autorreferência.
   • Por exemplo, as probabilidades em uma sequência que diz “Tenho probabilidade inferior a 50% no n -ésimo dia” chegam extremamente perto de 50% e oscilam pseudoaleatoriamente, de modo que não existe um método de tempo polinomial para dizer se o n-ésimo está ligeiramente acima ou ligeiramente abaixo de 50%.
9. Autoconfiança: os indutores lógicos aprendem a confiar mais em suas crenças futuras do que em suas crenças atuais. Isso dá algum apoio formal à intuição de que os agentes probabilísticos do mundo real podem muitas vezes estar razoavelmente confiantes no seu raciocínio futuro na prática, embora os teoremas da incompletude de Gödel coloquem fortes limites ao raciocínio reflexivo em plena generalidade.⁴

As afirmações acima são bastante vagas; para declarações precisas, consulte o artigo .

A indução lógica foi desenvolvida por Scott Garrabrant em um esforço para resolver um problema aberto de que falamos há cerca de seis meses. Grosso modo, havíamos formalizado dois desideratos diferentes para um bom raciocínio sob incerteza lógica: a capacidade de reconhecer padrões naquilo que é demonstrável (como relações de exclusividade mútua entre afirmações sobre programas de computador) e a capacidade de reconhecer padrões estatísticos em sequências de afirmações lógicas (como reconhecer que os dígitos decimais de π parecem bastante pseudoaleatórios). Nenhum dos dois era muito difícil de alcançar isoladamente, mas ficamos surpresos ao saber que os nossos algoritmos simples para alcançar um deles pareciam bastante incompatíveis com os nossos algoritmos simples para alcançar o outro. Os indutores lógicos nasceram das tentativas de Scott de alcançar ambos simultaneamente.⁵

Acredito que há uma boa chance de que esta estrutura abra novos caminhos de estudo em questões de metamatemática, teoria da decisão, teoria dos jogos e reflexão computacional que há muito parecem intratáveis. Também estou cautelosamente otimista de que melhorará nossa compreensão da teoria da decisão e do raciocínio contrafactual, além de outros problemas relacionados ao alinhamento de valores da IA.⁶

Publicamos uma palestra on-line que ajuda a fornecer mais informações para nosso trabalho sobre indução lógica:⁷

Editar: Para uma palestra mais recente sobre indução lógica que aborda mais detalhes técnicos, veja aqui .

“Indução lógica” é um trabalho grande e, sem dúvida, ainda existem vários bugs. Agradecemos muito pelo feedback: envie erros de digitação, erros em geral e outros comentários para errata@intelligence.org.⁸

Notas

1. Embora impraticável, a indução de Solomonoff deu origem a uma série de técnicas (métodos de conjunto (ensemble)) que funcionam bem na prática. As diferenças entre nosso algoritmo e a indução de Solomonoff apontam na direção de novos métodos de conjunto que poderiam ser úteis para gerenciar a incerteza lógica, da mesma forma que os métodos de conjunto modernos são úteis para gerenciar a incerteza empírica.

2. Veja também Calude e Stay (2006) “A maioria dos programas param rapidamente ou nunca param.” 

3. Assim, por exemplo, pode-se fazer um indutor lógico sobre a aritmética de Peano pegando um indutor lógico sobre uma teoria vazia e condicionando-o aos axiomas de Peano.

4. Como exemplo, imagine que alguém pergunte a um indutor lógico: “Qual é a sua probabilidade de φ, dado que no futuro você pensará que φ é provável?” Grosso modo, o indutor responderá: “Nesse caso, φ seria provável”, mesmo que atualmente pense que φ é bastante improvável. Além disso, os indutores lógicos fazem isso de uma forma que evita paradoxos. Se φ for “No futuro, pensarei que φ é menos de 50% provável” e no presente você pergunta: “Qual é a sua probabilidade de φ, dado que no futuro você acreditará que é ≥50% provável ?”, então sua resposta será “Muito baixa”. No entanto, se você perguntar “Qual é a sua probabilidade de φ, dado que no futuro a sua probabilidade será extremamente próxima de 50%?”, então ele responderá: “Extremamente próxima de 50%”.

5. Os primeiros trabalhos para chegar a esse resultado podem ser encontrados no Fórum de Fundamentos do Agente Inteligente.

6. Considere a tarefa de projetar um sistema de IA para aprender as preferências de um ser humano (p. ex., aprendizado cooperativo por reforço inverso). A abordagem comum seria modelar o ser humano como um raciocinador bayesiano tentando maximizar alguma função de recompensa, mas isso limita severamente a nossa capacidade de modelar a irracionalidade e os erros de cálculo humanos, mesmo em ambientes simplificados. A indução lógica pode nos ajudar a resolver esse problema, fornecendo um modelo formal idealizado de raciocinadores limitados que não sabem (mas podem acabar aprendendo) as implicações lógicas de todas as suas crenças.

Suponha, por exemplo, que um agente humano faça um movimento de xadrez perdedor (não forçado). Um sistema de IA programado para aprender as preferências do ser humano a partir do comportamento observado provavelmente não deveria concluir que o ser humano queria perder. Em vez disso, o nosso modelo de brinquedo desse dilema deveria permitir que o ser humano tenha recursos limitados e não seja capaz de deduzir todas as implicações dos seus movimentos; e nosso modelo deve permitir que o sistema de IA também esteja ciente disso ou aprenda sobre isso.

7. Slides de porções relativamente não técnicas; slides da porção técnica. Para os espectadores que desejam passar para o conteúdo técnico, enviamos o segmento intermediário da palestra como um vídeo independente mais curto: link .

8. A versão do intelligence.org geralmente está mais atualizada que a versão do arXiv.

---

Tradução: Luan Marques

Link para o original