Teoria da Inferência Indutiva de Solomonoff

A Teoria de Inferência Indutiva Universal de Solomonoff é uma teoria de predição baseada em observações lógicas, assim como predizendo o próximo símbolo baseada numa dada série de símbolos. A única suposição é de que o ambiente segue alguma distribuição probabilística desconhecida mas computável. Isso é uma lâmina de Occam matematicamente formalizada.

Origem

Filosófica

A teoria é baseada em fundamentos filosóficos e foi fundada por Ray Solomonoff por volta de 1960. É uma Lâmina de Occam formalizada matematicamente. Teorias computáveis menores têm mais peso quando calculando a probabilidade da próxima observação. A Inteligência Artificial Universal de Marcus Hutter baseia-se nisso para calcular o valor esperado de uma ação.

Matemática

A prova da "lâmina" é baseada nas propriedades matemáticas conhecidas de uma distribuição probabilística sobre um conjunto contável. Essas propriedades são relevantes porque o conjunto infinito de todos os problemas é contável. A soma S das probabilidades de todos os programas deve ser exatamente igual a um (pela definição de probabilidade), daí as probabilidades devem decrescer grosseiramente à medida que enumeramos o conjunto infinito de todos os programas, ou então S será estritamente maior que um. Para ser mais preciso, para todo ε > 0, há algum tamanho L tal que a probabilidade de todos os programas maiores que L são, no máximo, ε . Isso não impede, entretanto, programas muito longos de ter probabilidades muito altas. Ingredientes fundamentais da teoria são os conceitos de probabilidade algorítmica e a complexidade de Kolmogorov. A probabilidade prévia universal de qualquer prefixo P de uma sentença 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 probabilística desconhecida, mas computável, da qual X é amostrada, a prévia universal e o teorema de Bayes podem ser usados para predizer as partes ainda não vistas de X de uma forma ideal.

Aplicações Modernas

Inteligência Artificial

Embora a inferência indutiva de Solomonoff não seja computável, vários algoritmos derivados de AIXI se aproximam dele para fazê-lo funcionar em um computador moderno. Quanto mais eles recebem poder de computação, mais as suas previsões estão perto das previsões de inferência indutiva (seu limite matemático é inferência indutiva de Solomonoff). Outra direção de inferência indutiva é baseado no modelo de E. Mark Gold da aprendizagem no limite de 1967 e tem vindo a desenvolver, desde então, mais e mais modelos de aprendizagem. O cenário geral é o seguinte: Dada uma classe S de funções computáveis, existe um aluno (ou seja, uma função recursiva) que para qualquer entrada da forma (f(0),f(1),...,f(n)) produz uma hipótese (um índice 'e' em relação a um acordo previamente com uma numeração aceitável de todas as funções computáveis; a função indexada deve ser consistente com os valores de f). Um aluno M aprende uma função 'f' se quase todas as suas hipóteses são o mesmo índice e, o que gera a função f;M aprende S se M aprender todo f em S. Resultados básicos são que todas as classes de funções recursivamente enumeradas são possíveis de se aprender enquanto que a classe REC de todas as funções computáveis não é possível de ser aprendida. Muitos modelos relacionados foram considerados e também o aprendizado de classes de conjuntos recursivamente enumeráveis de dados positivos é um tópico estudado do artigo pioneiro de Gold em 1967 em diante. Uma extensão abrangente da extensão da abordagem de Gold é desenvolvida pela teoria de Schmidhuber das complexidades generalizadas de Kolmogorov, que são tipos de algoritmos super-recursivos.

Máquinas de Turing

A terceira direção baseada matematicamente de inferência indutiva faz uso das teorias dos autômatos e da computação. Nesse contexto, o processo de inferência indutiva é feita por um autômato abstrato chamado de Máquina de Turing indutiva. Máquinas de Turing Indutivas representam o próximo passo no desenvolvimento da ciência d computação suprindo melhores modelos para computadores contemporâneos e para redes de computadores e formando uma importante classe de algoritmos super-recursivos à medida que elas satisfazem todas as condições na definição de algoritmos. Nomeadamente, cada máquina de Turing indutiva é um tipo de de método efetivo no qual a lista definitiva de instruções bem definidas para se completar uma tarefa, quando fornecido um estado inicial, procederá através de séries bem definidas de estados sucessivos, eventualmente terminando num estado final. a diferença entre uma máquina de Turing indutiva e uma comum é que, para se produzir um resultado, a comum tem de parar, enquanto que, em alguns casos, a indutiva pode fazer isso sem parar. Kleene chamou procedimentos que poderiam rodar para sempre sem parar de procedimento ou algoritmo de calculo. Kleene também demandou que tal algoritmo deve eventualmente exibir algum objeto. Essa condição é satisfeita por Máquinas de Turing Indutivas nem sempre dizem em qual passo o resultado foi obtido.

Máquinas de Turing indutivas simples são equivalentes a outros modelos de computação. Máquinas indutivas mais avançadas são muito mais poderosas. Foi provado 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 de computação equivalentes. Entretanto, máquinas de Turing indutivas simples e comuns permitem construção diretas de autômatos computáveis, que são máquinas físicas. Em contraste, os outros dois exemplos disponibilizam sistemas sintáticos de símbolos com regras formais para sua manipulação. Máquinas de Turing indutivas simples e Máquinas de Turing comuns estão relacionadas a funções recursivas parciais limitantes e a predicados de tentativa e erro assim como Máquinas de Turins estão relacionadas com funções recursivas parciais e cálculo lambda.

Note que apenas Máquinas de Turing indutivas simples têm a mesma estrutura (mas diferenres semânticas de funcionamento do modo de saída) que Máquinas de Turing comuns. Outros tipos de Máquinas de Turing indutivas têm essencialmente uma estrutura mais avançada devido à memória estruturada e à instruções mais poderosas. Sua utilização para inferências e aprendizado permite-se chegar a maiores eficiências e melhores reflexos de aprendizagem das pessoas (Burgin e Klinger, 2004).

Alguns pesquisadores confundem computações de Máquinas de Turing indutivas com computações sem-paradas ou com computações de tempo infinito. Primeiramente algumas ds computações de Máquinas de Turing indutivas param. Como no cao de Máquinas de Turing convencionais, algumas computações que param dão resultados, enquanto que outras, não. Segundo, algumas computações que não param de Máquinas de Turing indutivas dão resultados, já outras, não. Regras de Máquinas de Turing indutivas determinam quando uma computação (que para ou não) dá um resultado. Nominalmente, uma Máquinas de Turing indutivas produz saídas de tempos em tempos e, uma vez que essa saída para ed mudar, é considerada o resultado da computação. É necessário saber que descrições dessa regra, em alguns artigos, está incorreta. Por exemplo, Davis (2006: 128) formula a regra quando o resultado é obtido sem parar como "...uma vez que a saída correta foi obtida, qualquer saída subsequente simplesmente repetirá tal resultado". Terceiro, em contraste com o equívoco bem disseminado, Máquinas de Turing indutivas sempre dá resultados depois de um número finito de passos (em tempo finito) em contraste com as computações infinitas. Existem duas distinções principais entre Máquinas de Turing convencionai e Máquinas de Turing indutivas simples. A primeira distinção é que até Máquinas de Turing indutivas simples podem fazer mais que Máquinas de Turing convencionais. A segunda distinção é que Máquinas de Turing convencionais (por parar ou chegar num estado final) quando um resultado é obtido, enquanto que uma Máquinas de Turing indutivas simples informa que chegou ao resultado, isso acontece em apenas alguns casos, pois nos outros (nos quais a convencional é inútil), ela não informa. Pessoas têm a ilusão de que um computador sempre consegue informar (por parar ou por outros meios) quando o resultado é obtido. Em contraste a isso, usuários por si mesmos têm de decidir em muitos casos se o resultado computado é o que eles precisam ou se é necessário que se continue computando. Realmente, aplicações cotidianas de desktops, como processadores de texto e planilhas passam a maior parte do tempo esperando em loops de eventos, e não terminam até que o usuário o faça.

Máquinas de Turing Indutivas Evolucionárias

Uma abordagem evolucionária para inferência indutiva é obtida por outra classe de autômatos, chamados de Máquinas de Turing indutivas evolucionárias (Burgin e Eberbach, 2009; 2012). Uma Máquina de Turing indutiva evolucionária é uma (possivelmente infinita) sequencia FORMULAKE de Máquinas de Turing indutivas A[t] cada uma trabalhando com gerações X[t] que são codificadas como palavras no alfabeto das máquinas A[t]. O objetivo é construir uma população Z satisfazendo a condição de inferência. A automação A[t] chamado como um componente, ou um autômato , de E e é processado pelo autômato A[t] recebe a geração X[t-1] como sua entrada de A[t-1] e então aplica a variação do operador V e do operador de seleção S, produzindo a geração X[i+1] e mandando-a para A[i+1] para continuar a evolução.

Veja também

• Maquina de Turing

Referências

• Angluin, D., and Smith, C. H. (1983) Inductive Inference: Theory and Methods, Comput. Surveys, v. 15, no. 3, pp. 237–269
• Mark Burgin (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. and Klinger, A. Experience, Generations, and Limits in Machine Learning, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 71–91
• Gasarch, W. and Smith, C. H. (1997) A survey of inductive inference with an emphasis on queries. Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., 187, Dekker, New York, pp. 225–260.
• Sanjay Jain, Daniel Osherson, James Royer and Arun Sharma, Systems that Learn: An Introduction to Learning Theory (second edition), The MIT Press, Cambridge, Massachusetts, 1999.
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997.
• Daniel Osherson, Michael Stob and Scott Weinstein, Systems That Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists, Bradford – The MIT Press, Cambridge, Massachusetts, 1986.
• Ray Solomonoff "Two Kinds of Probabilistic Induction," The Computer Journal, Vol. 42, No. 4, 1999
• Ray Solomonoff "A Formal Theory of Inductive Inference, Part I" Information and Control, Part I: Vol 7, No. 1, pp. 1–22, March 1964
• Ray Solomonoff "A Formal Theory of Inductive Inference, Part II" Information and Control, Part II: Vol. 7, No. 2, pp. 224–254, June 1964
• Hay, Nick. "Universal Semimeasures: An Introduction," CDMTCS Research Report Series, University of Auckland, Feb. 2007.
• Burgin, M. and E. Eberbach, Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms, Fundamenta Informaticae, v. 91, No. 1, 2009, 53–77
• Burgin, M. and E. Eberbach, On Foundations of Evolutionary Computation: An Evolutionary Automata Approach, in Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies (Hongwei Mo, Ed.), IGI Global, Hershey, Pennsylvania, 2009, 342–360
• Burgin, M. and Eberbach, E. Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation, Computer Journal, v. 55, No. 9, 2012, pp. 1023–1029
• Martin Davis (2006) The Church–Turing Thesis: Consensus and opposition]". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
• Kleene, Stephen C. (First Edition 1952), Introduction to Metamathematics, Amsterdam: North-Holland.