Teoria da inferência indutiva de Solomonoff - Solomonoff's theory of inductive inference

A teoria da inferência indutiva de Solomonoff é uma prova matemática de que, se um universo é gerado por um algoritmo, as observações desse universo, codificadas como um conjunto de dados, são mais bem previstas pelo menor arquivo executável desse conjunto de dados. Essa formalização da navalha de Occam para indução foi introduzida por Ray Solomonoff , com base na teoria da probabilidade e na ciência da computação teórica . Em essência, a indução de Solomonoff deriva a probabilidade posterior de qualquer teoria computável , dada uma sequência de dados observados. Essa probabilidade posterior é derivada da regra de Bayes e de algum prior universal , ou seja, um prior que atribui uma probabilidade positiva a qualquer teoria computável.

Origem

Filosófico

A teoria é baseada em fundamentos filosóficos e foi fundada por Ray Solomonoff por volta de 1960. É uma combinação matematicamente formalizada da navalha de Occam e o Princípio das Explicações Múltiplas . Todas as teorias computáveis que descrevem perfeitamente as observações anteriores são usadas para calcular a probabilidade da próxima observação, com mais peso nas teorias computáveis ​​mais curtas. A inteligência artificial universal de Marcus Hütter se baseia nisso para calcular o valor esperado de uma ação.

Princípio

A indução de Solomonoff foi considerada a formalização computacional do Bayesianismo puro . Para entender, lembre-se que o bayesianismo deriva a probabilidade posterior de uma teoria a partir de dados pela aplicação da regra de Bayes, que produz , onde as teorias são alternativas à teoria . Para que essa equação faça sentido, as quantidades e devem estar bem definidas para todas as teorias e . Em outras palavras, qualquer teoria deve definir uma distribuição de probabilidade sobre os dados observáveis . A indução de Solomonoff essencialmente se resume a exigir, além disso, que todas essas distribuições de probabilidade sejam computáveis . ${\ displaystyle \ mathbb {P} [T | D]}$${\ displaystyle T}$${\ displaystyle D}$${\ displaystyle \ mathbb {P} [T | D] = \ mathbb {P} [D | T] \ mathbb {P} [T] / (\ mathbb {P} [D | T] \ mathbb {P} [ T] + \ sum _ {A \ neq T} \ mathbb {P} [D | A] \ mathbb {P} [A])}$${\ displaystyle A}$${\ displaystyle T}$${\ displaystyle \ mathbb {P} [D | T]}$${\ displaystyle \ mathbb {P} [D | A]}$${\ displaystyle T}$${\ displaystyle A}$${\ displaystyle D}$

Curiosamente, o conjunto de distribuições de probabilidade computáveis ​​é um subconjunto do conjunto de todos os programas, que é contável . Da mesma forma, os conjuntos de dados observáveis ​​considerados por Solomonoff eram finitos. Sem perda de generalidade, podemos, portanto, considerar que qualquer dado observável é uma string de bits finitos . Como resultado, a indução de Solomonoff pode ser definida invocando apenas distribuições de probabilidade discretas.

A indução de Solomonoff então permite fazer previsões probabilísticas de dados futuros , simplesmente obedecendo às leis da probabilidade. Ou seja, nós temos . Essa quantidade pode ser interpretada como a média das previsões de todas as teorias com dados anteriores , ponderada por suas credenciais posteriores . ${\ displaystyle F}$${\ displaystyle \ mathbb {P} [F | D] = \ mathbb {E} _ {T} [\ mathbb {P} [F | T, D]] = \ sum _ {T} \ mathbb {P} [ F | T, D] \ mathbb {P} [T | D]}$${\ displaystyle \ mathbb {P} [F | T, D]}$${\ displaystyle T}$${\ displaystyle D}$${\ displaystyle \ mathbb {P} [T | D]}$

Matemático

A prova da "navalha" é baseada nas propriedades matemáticas conhecidas de uma distribuição de probabilidade sobre um conjunto contável . Essas propriedades são relevantes porque o conjunto infinito de todos os programas é um conjunto enumerável. A soma S das probabilidades de todos os programas deve ser exatamente igual a um (de acordo com a definição de probabilidade ), portanto, as probabilidades devem diminuir aproximadamente à medida que enumeramos o conjunto infinito de todos os programas, caso contrário, S será estritamente maior que um. Para ser mais preciso, para cada > 0, existe algum comprimento l tal que a probabilidade de todos os programas serem maiores do que l é no máximo . Isso, entretanto, não impede que programas muito longos tenham uma probabilidade muito alta. ${\ displaystyle \ epsilon}$${\ displaystyle \ epsilon}$

Os ingredientes fundamentais da teoria são os conceitos de probabilidade algorítmica e complexidade de Kolmogorov . A probabilidade universal anterior de qualquer prefixo p de uma sequência computável x é a soma das probabilidades de todos os programas (para um computador universal ) que computam algo começando com p . Dado algum p e qualquer distribuição de probabilidade computável, mas desconhecida, da qual x é amostrado, o prior universal e o teorema de Bayes podem ser usados ​​para prever as partes ainda não vistas de x de maneira ótima.

Garantias matemáticas

Integridade de Solomonoff

A propriedade notável da indução de Solomonoff é sua integridade. Em essência, o teorema da completude garante que os erros cumulativos esperados feitos pelas previsões baseadas na indução de Solomonoff são limitados pela complexidade de Kolmogorov do processo de geração de dados (estocástico). Os erros podem ser medidos usando a divergência de Kullback-Leibler ou o quadrado da diferença entre a predição da indução e a probabilidade atribuída pelo processo de geração de dados (estocástico).

Incomputabilidade de Solomonoff

Infelizmente, Solomonoff também provou que a indução de Solomonoff é incomputável. Na verdade, ele mostrou que computabilidade e completude são mutuamente exclusivas: qualquer teoria completa deve ser incomputável. A prova disso deriva de um jogo entre a indução e o ambiente. Essencialmente, qualquer indução computável pode ser enganada por um ambiente computável, escolhendo o ambiente computável que nega a previsão da indução computável. Esse fato pode ser considerado um exemplo do teorema do não almoço grátis .

Aplicativos modernos

Inteligência artificial

Embora a inferência indutiva de Solomonoff não seja computável , vários algoritmos derivados de AIXI se aproximam dela para fazê-la funcionar em um computador moderno. Quanto mais poder de computação eles recebem, mais próximas suas previsões estão das previsões de inferência indutiva (seu limite matemático é a inferência indutiva de Solomonoff).

Outra direção de inferência indutiva é baseada no modelo de aprendizagem no limite de E. Mark Gold , de 1967, e tem desenvolvido cada vez mais modelos de aprendizagem desde então. O cenário geral é o seguinte: Dada uma classe S de funções computáveis, existe um aluno (isto é, funcional recursivo) que para qualquer entrada da forma ( f (0), f (1), ..., f ( n )) produz uma hipótese (um índice e em relação a uma numeração aceitável previamente acordada de todas as funções computáveis; a função indexada pode ser exigida consistente com os valores dados de f ). Um aprendiz M aprende uma função f se quase todas as suas hipóteses têm o mesmo índice e , que gera a função f ; M aprende S se M aprende cada f em S . Os resultados básicos são que todas as classes recursivamente enumeráveis ​​de funções podem ser aprendidas, enquanto a classe REC de todas as funções computáveis ​​não pode ser aprendida. Muitos modelos relacionados foram considerados e também o aprendizado de classes de conjuntos recursivamente enumeráveis ​​a partir de dados positivos é um tópico estudado do artigo pioneiro de Gold de 1967 em diante. Uma extensão de longo alcance da abordagem de Gold é desenvolvida pela teoria das complexidades generalizadas de Kolmogorov de Schmidhuber, que são tipos de algoritmos super-recursivos .

Máquinas de Turing

A terceira direção de inferência indutiva com base matemática faz uso da teoria de autômatos e computação. Nesse contexto, o processo de inferência indutiva é realizado por um autômato abstrato denominado máquina de Turing indutiva (Burgin, 2005). As máquinas de Turing indutivas representam o próximo passo no desenvolvimento da ciência da computação, fornecendo melhores modelos para computadores e redes de computadores contemporâneos (Burgin, 2001) e formando uma importante classe de algoritmos super-recursivos, pois eles satisfazem todas as condições na definição de algoritmo . Ou seja, cada máquina de Turing indutiva é um tipo de método eficaz em que uma lista definida de instruções bem definidas para completar uma tarefa, quando dado um estado inicial, irá prosseguir através de uma série bem definida de estados sucessivos, eventualmente terminando em um fim -Estado. A diferença entre uma máquina de Turing indutiva e uma máquina de Turing é que, para produzir o resultado, uma máquina de Turing precisa parar, enquanto em alguns casos uma máquina de Turing indutiva pode fazer isso sem parar. Stephen Kleene chamou procedimentos que poderiam ser executados para sempre sem parar pelo procedimento de cálculo de nome ou algoritmo (Kleene 1952: 137). Kleene também exigiu que tal algoritmo eventualmente exibisse "algum objeto" (Kleene 1952: 137). Essa condição é satisfeita pelas máquinas de Turing indutivas, pois seus resultados são exibidos após um número finito de etapas, mas as máquinas de Turing indutivas nem sempre informam em qual etapa o resultado foi obtido.

Máquinas de Turing indutivas simples são equivalentes a outros modelos de computação. As máquinas de Turing indutivas mais avançadas são muito mais poderosas. Está provado (Burgin, 2005) que funções recursivas parciais limitantes, predicados de tentativa e erro, máquinas de Turing gerais e máquinas de Turing indutivas simples são modelos equivalentes de computação. No entanto, máquinas de Turing indutivas simples e máquinas de Turing gerais fornecem construções diretas de autômatos de computação, que são totalmente aterrados em máquinas físicas. Em contraste, predicados de tentativa e erro, limitando funções recursivas e limitando funções recursivas parciais apresentam sistemas sintáticos de símbolos com regras formais para sua manipulação. As máquinas de Turing indutivas simples e as máquinas de Turing gerais estão relacionadas a funções recursivas parciais limitantes e predicados de tentativa e erro, assim como as máquinas de Turing estão relacionadas a funções recursivas parciais e cálculo lambda.

Observe que apenas máquinas de Turing indutivas simples têm a mesma estrutura (mas semânticas de funcionamento diferentes do modo de saída) que as máquinas de Turing. Outros tipos de máquinas de Turing indutivas têm uma estrutura essencialmente mais avançada devido à memória estruturada e instruções mais poderosas. A sua utilização para inferência e aprendizagem permite alcançar maior eficiência e reflete melhor a aprendizagem das pessoas (Burgin e Klinger, 2004).

Alguns pesquisadores confundem cálculos de máquinas de Turing indutivas com cálculos ininterruptos ou com cálculos de tempo infinito. Primeiro, alguns cálculos de máquinas de Turing indutivas param. Como no caso das máquinas de Turing convencionais, alguns cálculos de parada fornecem o resultado, enquanto outros não. Em segundo lugar, alguns cálculos ininterruptos de máquinas de Turing indutivas fornecem resultados, enquanto outros não. As regras das máquinas de Turing indutivas determinam quando um cálculo (com ou sem parada) dá um resultado. Ou seja, uma máquina de Turing indutiva produz saída de tempos em tempos e, uma vez que essa saída para de mudar, ela é considerada o resultado do cálculo. É necessário saber que as descrições desta regra em alguns artigos estão incorretas. Por exemplo, Davis (2006: 128) formula a regra quando o resultado é obtido sem parar como "uma vez que a saída correta tenha sido produzida, qualquer saída subsequente simplesmente repetirá este resultado correto." Terceiro, em contraste com o equívoco generalizado, as máquinas de Turing indutivas dão resultados (quando isso acontece) sempre após um número finito de etapas (em tempo finito) em contraste com cálculos de tempo infinito e infinito. Existem duas distinções principais entre as máquinas de Turing convencionais e as máquinas de Turing indutivas simples. A primeira distinção é que mesmo as máquinas de Turing indutivas simples podem fazer muito mais do que as máquinas de Turing convencionais. A segunda distinção é que uma máquina de Turing convencional sempre informa (parando ou chegando a um estado final) quando o resultado é obtido, enquanto uma máquina de Turing indutiva simples em alguns casos informa sobre como alcançar o resultado, enquanto em outros casos (onde a máquina de Turing convencional está indefesa), não informa. As pessoas têm a ilusão de que o próprio computador sempre informa (por meio de uma parada ou por outros meios) quando o resultado é obtido. Em contraste com isso, os próprios usuários têm que decidir, em muitos casos, se o resultado calculado é o que eles precisam ou se é necessário continuar os cálculos. Na verdade, os aplicativos de computador de mesa do dia-a-dia, como processadores de texto e planilhas, passam a maior parte do tempo esperando em loops de eventos e não são encerrados até que sejam orientados pelos usuários.

Máquinas de Turing indutivas evolucionárias

A abordagem evolucionária para inferência indutiva é realizada por outra classe de autômatos denominados máquinas de Turing indutivas evolutivas (Burgin e Eberbach, 2009; 2012). Uma máquina de Turing indutiva evolutiva é uma sequência (possivelmente infinita) E = { A [ t ]; t = 1, 2, 3, ...} das máquinas de Turing indutivas A [ t ], cada uma trabalhando nas gerações X [t], que são codificadas como palavras no alfabeto das máquinas A [ t ]. O objetivo é construir uma “população” Z que satisfaça a condição de inferência. O autômato A [ t ] denominado componente, ou autômato de nível, de E representa (codifica) um algoritmo evolutivo de um nível que trabalha com gerações de entrada X [ i ] da população aplicando os operadores de variação ve operadores de seleção s. A primeira geração X [0] é dada como entrada para E e é processada pelo autômato A [1], que gera / produz como saída de transferência a primeira geração X [1], que vai para o autômato A [2]. Para todo t = 1, 2, 3, ..., o autômato A [ t ] recebe a geração X [ t  - 1] como sua entrada de A [ t  - 1] e então aplica o operador de variação v e os operadores de seleção s , produzindo a geração X [ i  + 1] e enviando-a para A [ t  + 1] para continuar a evolução.

Veja também

• Teoria da Informação Algorítmica
• Inferência bayesiana
• Identificação de idioma no limite
• Inferência indutiva
• Probabilidade indutiva
• Métodos de Mill
• Comprimento mínimo da descrição
• Comprimento mínimo da mensagem
• Para um ponto de vista filosófico, consulte: Problema da indução e Novo enigma da indução

Referências

Fontes

• Angluin, Dana; Smith, Carl H. (setembro de 1983). "Inferência Indutiva: Teoria e Métodos" . Pesquisas de computação . 15 (3): 237–269. doi : 10.1145 / 356914.356918 . S2CID  3209224 .
• Burgin, M. (2005), Super-recursive Algorithms , Monographs in computer science, Springer. ISBN  0-387-95569-0
• Burgin, M., "How We Know What Technology Can Do", Communications of the ACM , v. 44, No. 11, 2001, pp. 82-88.
• Burgin, M .; Eberbach, E., "Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms", Fundamenta Informaticae , v. 91, No. 1, 2009, 53-77.
• Burgin, M .; Eberbach, E., "On Foundations of Evolutionary Computation: An Evolutionary Automata Approach", em Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies (Hongwei Mo, Ed.), IGI Global, Hershey, Pensilvânia, 2009 , 342–360.
• Burgin, M .; Eberbach, E., "Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation", Computer Journal , v. 55, No. 9, 2012, pp. 1023-1029.
• Burgin, M .; Klinger, A. Experience, Generations, and Limits in Machine Learning, Theoretical Computer Science , v. 317, No. 1/3, 2004, pp. 71-91
• Davis, Martin (2006) "A Tese de Church – Turing: Consenso e oposição]". Proceedings, Computability in Europe 2006. Lecture Notes in Computer Science, 3988 pp. 125-132.
• Gasarch, W .; Smith, CH (1997) "Uma pesquisa de inferência indutiva com ênfase em consultas". Complexidade, lógica e teoria da recursão , Notas de aula em Pure e Appl. Math., 187, Dekker, New York, pp. 225-260.
• Feno, Nick. " Universal Semimeasures: An Introduction ," CDMTCS Research Report Series, University of Auckland, fevereiro de 2007.
• Jain, Sanjay; Osherson, Daniel; Royer, James; Sharma, Arun, Systems that Learn: An Introduction to Learning Theory (segunda edição), MIT Press , 1999.
• Kleene, Stephen C. (1952), Introdução à Metamatemática (primeira edição), Amsterdam: North-Holland.
• Li Ming; Vitanyi, Paul, Uma Introdução à Complexidade de Kolmogorov e Suas Aplicações , 2ª Edição, Springer Verlag, 1997.
• Osherson, Daniel; Stob, Michael; Weinstein, Scott, Systems That Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists , MIT Press , 1986.
• Solomonoff, Ray J. (1999). "Dois tipos de indução probabilística" (PDF) . The Computer Journal . 42 (4): 256. CiteSeerX  10.1.1.68.8941 . doi : 10.1093 / comjnl / 42.4.256 .
• Solomonoff, Ray (março de 1964). "A Formal Theory of Inductive Inference Part I" (PDF) . Informação e controle . 7 (1): 1–22. doi : 10.1016 / S0019-9958 (64) 90223-2 .
• Solomonoff, Ray (junho de 1964). "A Formal Theory of Inductive Inference Part II" (PDF) . Informação e controle . 7 (2): 224–254. doi : 10.1016 / S0019-9958 (64) 90131-7 .

links externos

• Probabilidade algorítmica - Scholarpedia