probabilidade algorítmica - Algorithmic probability

Em teoria da informação algorítmica , probabilidade algorítmica , também conhecido como Solomonoff probabilidade , é um método matemático de atribuir uma prévia probabilidade para uma dada observação. Foi inventado por Ray Solomonoff na década de 1960. Ele é usado na teoria inferência indutiva e análise de algoritmos. Na sua teoria geral de inferência indutiva , Solomonoff utiliza o anterior obtido por esta fórmula, em regra de Bayes para predição.

No formalismo matemático usado, as observações têm a forma de cadeias binárias finitos, ea prévia universal é uma distribuição de probabilidades sobre o conjunto de cadeias binárias finitos. A prévia é universal no sentido de Turing-computability, ou seja, sem corda tem probabilidade zero. Não é computável, mas pode ser aproximada.


visão global

Probabilidade ofertas algorítmicos com as seguintes perguntas: Dado um corpo de dados sobre algum fenômeno que queremos entender, como podemos selecionar o mais provável hipótese de como ele foi causado, entre todas as hipóteses possíveis e como podemos avaliar as diferentes hipóteses? Como podemos prever dados futuros e como podemos medir a probabilidade de que a previsão de ser o caminho certo?

Quatro principais inspirações para probabilidade algorítmica de Solomonoff foram: a navalha de Occam , princípio de múltiplas explicações Epicuro , teoria da computação moderna (por exemplo, o uso de uma máquina de Turing universal ) e de Bayes regra para predição.

Navalha de Occam e princípio de Epicuro são essencialmente duas aproximações não-matemáticos diferentes do anterior universal .

  • Navalha de Occam: entre as teorias que são consistentes com os fenômenos observados, deve-se selecionar a teoria mais simples .
  • Princípio de múltiplas explicações Epicuro: se mais do que uma teoria é consistente com as observações, manter todas essas teorias .

No coração da prévia universal é um modelo abstrato de um computador, como uma máquina de Turing universal . Qualquer computador abstrato vai fazer, contanto que é Turing completo, ou seja, cada cadeia binária finito tem pelo menos um programa que irá calcular-lo no computador abstrato.

O computador abstrato é usado para dar significado preciso para a frase "explicação simples". No formalismo usado, explicações ou teorias de fenômenos, são programas de computador que geram cadeias de observação quando executado no computador abstrato. Uma explicação simples é um programa de computador curto. Uma explicação complexo é um programa de computador por muito tempo. Explicações simples é mais provável, então uma seqüência de observação de alta probabilidade é aquele gerado por um programa de computador curto, ou talvez por qualquer de um grande número de programas de computador um pouco mais longos. Uma seqüência de observação de baixa probabilidade é aquela que só pode ser gerado por um programa de computador por muito tempo.

Estas ideias podem ser feitas específico e as probabilidades utilizado para construir uma distribuição de probabilidade a priori para a observação determinado. principal razão de Solomonoff para inventar isto antes é para que ele possa ser utilizado na regra de Bayes quando a prévia real é desconhecida, permitindo previsão sob incerteza. Ela prevê a continuação mais provável do que a observação, e fornece uma medida de quão provável que esta continuação será.

Embora a probabilidade universal de uma observação (e sua extensão) é incomputável, existe um algoritmo de computador, Levin Search, que, quando executado por períodos mais longos e mais longos de tempo, irá gerar uma sequência de aproximações que convergem para a distribuição de probabilidade universal .

Solomonoff provou esta distribuição para ser máquina invariante dentro de um factor constante (chamado o teorema invariância ).

Solomonoff inventou o conceito de probabilidade algorítmica com seu teorema da invariância associado por volta de 1960, a publicação de um relatório sobre o assunto: "Um Relatório Preliminar sobre uma Teoria Geral da indutivo Inference". Ele esclareceu essas idéias mais plenamente em 1964, com "uma teoria formal de indutivo Inference", Parte I e Parte II.

Uma discussão mais aprofundada

Solomonoff descrito um computador universal com um programa de entrada gerado aleatoriamente. O programa calcula alguma saída possivelmente infinito. A distribuição de probabilidade universal é a distribuição de probabilidade em todas as cadeias de saída possíveis com entrada aleatória.

A probabilidade algorítmica de um determinado finito prefixo de saída q é a soma das probabilidades dos programas que calculam algo começando com q . Certos objetos longos com programas curtos têm alta probabilidade.

Probabilidade algorítmica é o principal ingrediente da teoria de inferência indutiva de Solomonoff , a teoria da predição baseada em observações; ele foi inventado com o objetivo de usá-lo para a aprendizagem de máquina; dada uma sequência de símbolos, o que virá a seguir? A teoria de Solomonoff fornece uma resposta que é o ideal, em certo sentido, embora seja incomputável. Ao contrário, por exemplo, Karl Popper teoria inferência indutiva informal 's, Solomonoff de é matematicamente rigorosa.

Probabilidade algorítmica está intimamente relacionado com o conceito de complexidade de Kolmogorov . Introdução de complexidade de Kolmogorov foi motivada pela teoria da informação e problemas na aleatoriedade, enquanto Solomonoff introduziu complexidade algorítmica por um motivo diferente: o raciocínio indutivo. Um único probabilidade anterior universal que pode ser substituído para cada probabilidade anterior real em regra de Bayes foi inventado por Solomonoff com complexidade de Kolmogorov como um produto secundário.

Medida enumeráveis de Solomonoff é universal em certo sentido poderoso, mas o tempo de computação pode ser infinito. Uma forma de lidar com esta questão é uma variante do algoritmo de pesquisa de Leonid Levin, que limita o tempo gasto computando o sucesso de programas possíveis, com programas mais curtos dado mais tempo. Outros métodos de limitar o espaço de busca incluem sequências de treinamento.

Pessoas chave

Veja também

Referências

Fontes

  • Li, M. e Vitanyi, P., An Introduction to Kolmogorov complexidade e suas aplicações , 3rd Edition, Springer Science and Business Media, NY, 2008

Outras leituras

links externos