Probabilidade indutiva

A probabilidade indutiva tenta aferir a probabilidade de eventos futuros baseado em eventos passados. É a base para o raciocínio indutivo, e fornece a base matemática para o aprendizado e percepção de padrões. É uma fonte de conhecimento sobre o mundo.

Há três fontes de conhecimento: inferência, comunicação e dedução. A comunicação retransmite informações encontradas utilizando-se outros métodos. A dedução estabelece novos fatos, baseando-se nos existentes. Somente a inferência estabelece novos dados a partir de informação.

A base da inferência é o teorema de Bayes, mas esse teorema é, algumas vezes, difícil de ser entendido e aplicado. O método mais simples de entender inferência é em termos da quantidade da informação.

A informação que descreve um mundo é escrita em uma linguagem. Por exemplo, uma simples linguagem matemática de proposições pode ser escolhida. Sentenças podem ser escritas nessa linguagem como uma cadeia de caracteres. Mas, no computador, é possível codificar essas sentenças como cadeias de bits (uns e zeros). Assim a linguagem pode ser codificada de forma que as sentenças mais utilizadas são as mais curtas. Essa linguagem interna implicitamente representa a probabilidade de declarações.

A Navalha de Occam diz que "a teoria mais simples, consistente com os dados é a mais provável de estar correta". A "teoria mais simples" é interpretada como a representação da teoria escrita nessa linguagem interna. A teoria com a codificação mais curta nessa linguagem interna é a mais provável de estar correta.

História

Probabilidade e estatística foram focadas em distribuições de probabilidade e testes de significância. Probabilidade foi formal, bem definida, mas de escopo limitado. Em particular, sua aplicação foi limitada a situações que poderiam ser definidas como um experimento ou teste, com uma população bem definida.

teorema de Bayes tem esse nome graças ao Reverendo Thomas Bayes 1701-1761. A inferência bayesiana ampliou a aplicação da probabilidade para diversas situações onde a população não era bem definida. Mas o teorema de Bayes sempre dependeu de probabilidades anteriores para gerar novas probabilidades. Não era claro de onde essas probabilidades anteriores deveriam vir.

Por volta de 1964 Ray Solomonoff desenvolveu a probabilidade algorítmica, que deu uma explicação para o que é a aleatoriedade e como padrões nos dados podem ser representados por programas de computador, que fornecem representações mais curtas dos dados.

Por volta de 1968, Chris Wallace e D. M. Boulton desenvolveram a mensagem de comprimento mínimo. Mais tarde, por volta de 1978, Jorma Rissanen desenvolveu o descrição de comprimento mínimo. Esses métodos permitem que a teoria da informação se relacione à probabilidade de forma que possa ser comparada à aplicação do teorema de Bayes, mas dando uma fonte e uma explicação para o papel de probabilidades anteriores.

Por volta de 1998 Marcus Hutter combinou a teoria da decisão com o trabalho de Ray Solomonoff e Andrey Kolmogorov para formular uma teoria para o comportamento da eficiência à Pareto para um agente inteligente.

Mensagem/descrição de comprimento mínimo

O programa com o menor comprimento que corresponde aos dados é o mais provável de predizer dados futuros. Essa é a tese por trás dos métodos de mensagem de comprimento mínimo e descrição de comprimento mínimo.

A primeira vista, o teorema de Bayes parece ser diferente do princípio do comprimento mínimo de uma mensagem/descrição. Ao observarmos melhor, percebemos que são a mesma coisa. O teorema de Bayes é sobre probabilidades condicionais. Qual a probabilidade de que o evento B aconteça se o evento A acontecer primeiro?

$P(A\land B)=P(B)\cdot P(A\mid B)=P(A)\cdot P(B\mid A)$

Torna-se, em termos da mensagem de tamanho L,

$L(A\land B)=L(B)+L(A\mid B)=L(A)+L(B\mid A)$

Isso significa que, ao descrevermos um evento, se todas as informações que o descrevem forem fornecidas, então o tamanho da informação pode ser utilizado para chegarmos à probabilidade bruta do evento. Então, se a informação descrevendo a ocorrência de A é dada juntamente com a informação descrevendo B dado A, toda a informação descrevendo A e B foi dada.

Sobre-ajuste

Sobre-ajuste é onde o modelo corresponde ao ruído aleatório e não ao padrão nos dados. Por exemplo, tome a situação na qual uma curva é ajustada sobre um conjunto de pontos. Se é ajustada polinomialmente, com vários termos, pode representar os dados com maior fidelidade. Então o ajuste será melhor e a informação necessária para descrever os desvios da curva ajustada serão menores. Menor comprimento de informação significa mais provável.

No entanto, a informação necessária para descrever a curva também deve ser considerada. O total da informação para uma curva com vários termos pode ser maior do que o de uma curva com menos termos, que não tem um bom ajuste, mas precisa de menos informação para descrever o polinômio.

Baseado em inferência sobre a complexidade do programa

A teoria de inferência indutiva de Solomonoff também é inferência indutiva. Uma cadeia de bits x é observada. Então, considere todos os programas que geram cadeias que começam com x. No formato de inferência indutiva, os programas são teorias que sugerem a observação da cadeia x.

O método aqui utilizado para dar probabilidades para inferência indutiva é baseado na teoria de inferência indutiva de Solomonoff.

Detectando padrões nos dados

Se todos os bits são 1, então pode-se inferir que há uma propensão da moeda e que é mais provável que o próximo bit também será 1. Isso é descrito como aprendendo ou detectando um padrão nos dados.

Tal padrão pode ser representado por um programa de computador. Um pequeno programa de computador pode ser escrito de forma que produza uma série de bits que são todos 1. Se o comprimento do programa K é $L(K)$ bits, então a sua probabilidade anterior é,

$P(K)=2^{-L(K)}$

O comprimento do programa mais curto que representa a cadeia de bits é chamado de complexidade de Kolmogorov.

Complexidade de Kolmogorov não é computável. Isto está relacionado com o problema da parada. Ao procurar pelo programa mais curto, alguns programas podem entrar em um loop infinito.

Considerando todas as teorias

É atribuída ao filósofo grego Epicuro a frase: "Se mais de uma teoria é consistente com as observações, mantenha todas as teorias".

Como num romance policial todas as teorias devem ser consideradas para a determinação do provável assassino, então com probabilidade indutiva todos os programas devem ser considerados na determinação dos prováveis bits futuros decorrentes do fluxo de bits.

Os programas que já são maiores que n não têm poder preditivo. A probabilidade bruta (ou anterior) de que o padrão de bits é aleatório (não tem padrão) é $2^{-n}$.

Cada programa que produz a sequência de bits, mas é mais curto do que n é uma teoria/um padrão sobre os bits com uma probabilidade de $2^{-k}$ onde k é o comprimento do programa.

A probabilidade de receber uma sequência de bits y depois de receber uma série de bits x é, então, a probabilidade condicional de receber y dado x, que é a probabilidade de x com y anexado, dividida pela probabilidade de x.

Prévias universais

A linguagem de programação afeta as previsões do próximo bit na cadeia. A linguagem atua como uma probabilidade anterior. Isto é particularmente um problema onde as linguagens de programação codificam por números e outros tipos de dados. Intuitivamente nós pensamos que 0 e 1 são números simples, e que os números primos são de algum modo mais complexos podendo ser fatorados.

Usando a complexidade de Kolmogorov temos uma estimativa imparcial (uma prévia universal) da probabilidade prévia de um número. Como um experimento mental um agente inteligente pode ser equipado com um dispositivo de entrada de dados dando uma série de números, depois de aplicar alguma função de transformação aos números brutos. Outro agente pode ter o mesmo dispositivo de entrada com uma função de transformação diferente. Os agentes não veem ou sabem sobre essas funções de transformação. Então não há uma base racional para se preferir uma função em detrimento a outra. Uma prévia universal garante que, apesar de dois agentes poderem ter diferentes distribuições de probabilidade iniciais para a entrada de dados, a diferença será limitada por uma constante.

Então prévias universais não eliminam uma tendência inicial, mas a reduzem e limitam. Sempre que descrevemos um evento em uma linguagem, seja usando linguagem natural ou outra, a linguagem tem codificada em si nossas expectativas prévias. Sendo assim, alguma confiança em probabilidades anteriores é inevitável.

Um problema surge onde expectativas prévias de um agente inteligente interagem com o ambiente para formar um loop de feedback de autorreforço. Esse é o problema da parcialidade ou preconceito. Prévias universais reduzem, mas não eliminam esse problema.

Inteligência artificial universal

inteligência artificial universal aplica desde teoria de decisão à probabilidades indutivas. A teoria mostra como as melhores ações para otimizar uma função de recompensa podem ser escolhidos. O resultado é um modelo teórico de inteligência.

É uma teoria fundamental da inteligência, o que otimiza o comportamento dos agentes em:

• Explorar o ambiente; realizando ações para obter as respostas que ampliem o conhecimento do agente.
• Competir ou cooperando com outro agente; jogos.
• Equilibrar recompensas de curto e longo prazo.

Em geral, nenhum agente irá sempre oferecer as melhores ações em todas as situações. A escolha em particular feita por um agente pode estar errada, e o ambiente pode não fornecer uma maneira para que o agente se recupere de uma má escolha inicial. No entanto, o agente é eficiente à Pareto no sentido de que nenhum outro agente vai fazer melhor do que este agente neste ambiente, sem fazer pior em outro ambiente. Nenhum outro agente pode, neste sentido, ser considerado melhor.

Atualmente, a teoria é limitada pela incomputabilidade (o problema da parada). Aproximações podem ser utilizadas para evitar isso. Velocidade de processamento e explosão combinatória permanecem os fatores limitantes primários para a inteligência artificial.

Probabilidade

Probabilidade é a representação do conhecimento incerto ou parcial sobre a verdade das afirmações. As probabilidades são estimativas subjetivas e pessoais de resultados prováveis ​​com base na experiência do passado e inferências feitas a partir dos dados.

Esta descrição de probabilidade pode parecer estranha à primeira vista. Em linguagem natural nos referimos à "probabilidade" de que o sol nascerá amanhã. Não nos referimos à "sua probabilidade" de que o sol nascerá. Mas, para que a inferência seja corretamente modelada, a probabilidade deve ser pessoal, e o ato de inferência gera novas probabilidades posteriores à partir probabilidades anteriores.

As probabilidades são pessoais, porque eles ficam dependentes do conhecimento do indivíduo. Probabilidades são subjetivas, porque elas sempre dependem, em certa medida, de probabilidades anteriores atribuídas pelo indivíduo. Subjetiva não deve ser tomado aqui como vaga ou indefinida.

O termo agente inteligente é usado para se referir ao titular das probabilidades. O agente inteligente pode ser um humano ou uma máquina. Se o agente inteligente não interage com o ambiente, então a probabilidade convergirá ao longo do tempo para a frequência do evento.

Se, no entanto, o agente usa a probabilidade para interagir com o ambiente, pode haver uma reação, de modo que dois agentes em ambientes idênticos começando com antecedentes ligeiramente diferentes, acabam com probabilidades completamente diferentes. Neste caso, a teoria da decisão ótima como na Inteligência Artificial Universal de Marcus Hutter dará uma performance com eficiência à Pareto ao agente. Isto significa que nenhum outro agente inteligente poderia fazer melhor em um ambiente sem fazer pior em outro ambiente.

Comparação com probabilidade dedutiva

Em teorias de probabilidade dedutivas, probabilidades são absolutas, independentemente do indivíduo fazendo a avaliação. Mas probabilidades dedutivas são baseadas em,

• Conhecimento compartilhado; e
• Fatos assumidos, que devem ser inferidos a partir dos dados.

Por exemplo, em um ensaio os participantes estão cientes do resultado de toda a história prévia de ensaios. Eles também assumem que cada resultado é igualmente provável. Em conjunto, isto permite que um único valor incondicional de probabilidade seja definido.

Mas, na realidade, cada indivíduo não tem a mesma informação. E, em geral, a probabilidade de cada resultado não é igual. Os dados podem ser carregados, e esta carga deve ser inferida a partir das informações.

Probabilidade como estimação

O princípio da indiferença tem desempenhado um papel-chave na teoria da probabilidade. Ele diz que se N declarações são simétricas, de forma que uma condição não pode ser preferida em detrimento de outra, então todas as declarações são igualmente prováveis.

Levado a sério, na avaliação de probabilidade, este princípio leva a contradições. Suponha que há 3 sacos de ouro distantes e você é solicitado a escolher um. Então, devido à distância, você não pode ver o tamanho dos sacos. Você estima usando o princípio da indiferença que cada saco tem quantidades iguais de ouro, e cada saco tem um terço do ouro.

Agora, enquanto você não está olhando, eu pego um dos sacos e o divido em 3 sacos. Agora existem 5 sacos de ouro. O princípio da indiferença agora diz que cada saco tem um quinto do ouro. Um saco que foi estimado como tendo um terço do ouro é agora estimado como tendo um quinto do ouro.

Tomado como um valor associado à bolsa, os valores são diferentes, por conseguinte, contraditórios. Mas, tomado como uma estimativa dada no âmbito de um determinado cenário, ambos os valores são estimativas separadas dadas em circunstâncias diferentes e não há nenhuma razão para acreditar que eles são iguais.

Estimativas de probabilidades anteriores são particularmente suspeitas. As estimativas serão construídos de forma que não sigam qualquer distribuição de frequência consistente. Por esta razão probabilidades anteriores são consideradas como as estimativas de probabilidades em vez de probabilidades.

Um tratamento teórico completo iria associar com cada probabilidade,

• A declaração;
• Conhecimento prévio;
• Probabilidades anteriores; e
• O procedimento de estimativa usada para dar a probabilidade.

Combinando abordagens de probabilidade

Probabilidade indutiva combina duas abordagens diferentes para a probabilidade.

• Probabilidade e informações
• Probabilidade e frequência

Cada abordagem dá um ponto de vista ligeiramente diferente. A teoria da informação é usada em relacionar probabilidades a quantidades de informação. Essa abordagem é muitas vezes usada para dar estimativas de probabilidades anteriores.

A probabilidade de frequência define probabilidades como declarações objetivas sobre a frequência com que ocorre um evento. Essa abordagem pode ser estendida definindo-se os ensaios para ser sobre mundos possíveis. Declarações sobre mundos possíveis define eventos.

Probabilidade e informação

Considerando que a lógica representa apenas dois valores; verdadeiro e falso como os valores da declaração, a probabilidade associa um número entre 0,0 e 1,0 com cada afirmação. Se a probabilidade de uma declaração é 0 a afirmação é falsa. Se a probabilidade de uma declaração é de 1 a afirmação é verdadeira.

Ao considerar alguns dados como uma sequência de bits as probabilidades prévias para uma sequência de 1 e 0s, a probabilidade de 1 e 0 é igual. Por isso, cada bit extra divide a probabilidade de uma sequência de bits. Isto leva à conclusão de que,

$P(x)=2^{-L(x)}$

Onde

• $P(x)$ é a probabilidade de uma cadeia de bits x;
• $L(x)$ é o comprimento da cadeia de bits x;
• $2^{-L(x)}$ significa 1 dividido por 2 elevado ao comprimento da cadeia de bit x.

A probabilidade anterior de qualquer declaração é calculado a partir do número de bits necessários para indicá-lo. Veja também a teoria da informação.

Combinando informação

Duas declarações A e B podem ser representados por duas codificações separadas. Então, o comprimento da codificação é,

$L(A\land B)=L(A)+L(B)$

ou em termos de probabilidade,

$P(A\land B)=P(A)P(B)$

Mas esta lei nem sempre é verdade, pois pode haver um método mais curto de codificar B se assumirmos A. Então a lei de probabilidade acima aplica-se apenas se A e B são "independentes".

A linguagem interna da informa

A principal utilização da abordagem de informação para a probabilidade é fornecer estimativas da complexidade das declarações. Lembre-se que a navalha de Occam afirma que "Todas as coisas sendo iguais, a teoria mais simples é o mais provável estar correta". Para aplicar esta regra, primeiro é necessário que haja uma definição do que "simples" significa. A teoria da informação define mais simples como tendo a codificação mais curta.

Conhecimento é representado como declarações. Cada afirmação é uma expressão booleana. Expressões são codificadas por uma função que leva uma descrição (como contra o valor) da expressão e a codifica como uma cadeia de bits.

O comprimento da codificação de uma instrução dá uma estimativa da probabilidade de uma instrução. Esta estimativa de probabilidade será frequentemente utilizada como a probabilidade anterior de uma declaração.

Tecnicamente esta estimativa não é uma probabilidade, porque não é construída a partir de uma distribuição de frequência. As estimativas de probabilidade dada por ele nem sempre obedece à lei do total da probabilidade. Aplicando a lei da probabilidade total para vários cenários normalmente irá resultar em uma estimativa de probabilidade mais precisa da probabilidade prévia do que a estimativa do comprimento da declaração.

Codificando expressões

Uma expressão é construída a partir de subexpressões,

• Constantes (incluindo identificador de função);
• Aplicação de funções;
• quantificadores.

Um código Huffman deve distinguir os 3 casos. O comprimento de cada código é baseado na frequência de cada tipo de subexpressões.

Inicialmente todas as constantes recebem o mesmo comprimento/probabilidade. Mais tarde, constantes podem receber uma probabilidade usando o código de Huffman com base no número de utilizações do id da função em todas as expressões gravadas até agora. Na utilização de um código de Huffman o objetivo é o de estimar probabilidades, não comprimir os dados.

O comprimento da aplicação de uma função é o comprimento da constante identificadora da função mais a soma dos tamanhos das expressões para cada parâmetro.

O comprimento de um quantificador é o comprimento da expressão sendo quantificada.

Distribuição de números

Nenhuma representação explícita dos números naturais é dada. No entanto números naturais podem ser construídos pela aplicação da função sucessor em 0 e, em seguida, aplicando-se outras funções aritméticas. Uma distribuição de números naturais é implicada por isso, com base na complexidade de construção de cada número.

Números racionais são construídos pela divisão de números naturais. A representação mais simples não tem fatores comuns entre o numerador e o denominador. Isso permite que a distribuição de probabilidade dos números naturais pode ser prorrogado para números racionais.

Probabilidade e frequência

A probabilidade de um evento pode ser interpretada como as frequências de resultados onde a declaração é verdadeira, dividido pelo número total de resultados. Se os resultados formar um continuum a frequência pode ter de ser substituída por uma medida.

Os eventos são conjuntos de resultados. Declarações podem estar relacionadas com eventos. Uma declaração booleana B sobre resultados define um conjunto de resultados b,

$b=\{x:B(x)\}$

Probabilidade condicional

Cada probabilidade é sempre associado com o estado de conhecimento em um determinado ponto no argumento. Probabilidades antes de uma inferência são conhecidos como probabilidades anteriores, e as probabilidades depois são conhecidos como probabilidades posteriores.

Probabilidade depende dos fatos conhecidos. A verdade de um fato limita o domínio de resultados para os resultados consistentes com o fato. Probabilidades anteriores são as probabilidades de antes de um fato ser conhecido. Probabilidades posteriores são de após um fato ser conhecido. As probabilidades posteriores são ditas ser condicionada pelo fato. Probabilidades condicionais são escritas,

$P(B\mid A)$

Isto significa a probabilidade de que B é verdadeiro dado que A é verdadeiro.

Todas as probabilidades são, em certo sentido condicionais. A probabilidade anterior de B é,

$P(B)=P(B\mid {\text{true}})$

A abordagem frequencista aplicada a mundos possíveis

Na abordagem frequencista, probabilidades são definidas como a razão entre o número de resultados dentro de um evento para o número total de resultados. No modelo do mundo possível, cada mundo possível é um resultado, e declarações sobre possíveis mundos definem eventos. A probabilidade de uma declaração ser verdadeira é o número de mundos possíveis, dividido pelo número total de mundos.

O número total de mundos pode ser infinito. Neste caso, em vez de contar os elementos do conjunto, uma medida deve ser usada. Em geral, a cardinalidade |S|, onde S é um conjunto, é uma medida.

A probabilidade de uma declaração A ser verdadeira sobre possíveis mundos é então,

$P(A)={\frac {|\{x:A(x)\}|}{|x:true|}}$

Para uma probabilidade condicional.

$P(B\mid A)={\frac {|\{x:A(x)\land B(X)\}|}{|x:A(x)|}}$

então

$P(A\land B)$

$={\frac {|\{x:A(x)\land B(x)\}|}{|x:true|}}$

$={\frac {|\{x:A(x)\land B(x)\}|}{|\{x:A(x)\}|}}{\frac {|\{x:A(x)\}|}{|x:true|}}$

$=P(A)P(B\mid A)$

Usando simetria esta equação pode ser escrita como lei de Bayes.

$P(A\land B)=P(A)P(B\mid A)=P(B)P(A\mid B)$

Esta lei descreve a relação entre probabilidades anteriores e posteriores quando novos fatos são aprendidos.

Escrito como quantidades de informações o teorema de Bayes torna-se,

$L(A\land B)=L(A)+L(B\mid A)=L(B)+L(A\mid B)$

Duas declarações A e B são ditas independentes se conhecer a verdade de A não muda a probabilidade de B. Matematicamente isto é,

$P(B)=P(B\mid A)$

assim, o teorema de Bayes reduz-se a,

$P(A\land B)=P(A)P(B)$

A lei do total da probabilidade

Para um conjunto de possibilidades mutuamente exclusivas $A_{i}$, a soma das probabilidades posteriores deve ser 1

$\sum _{i}{P(A_{i}\mid B)}=1$

Substituindo usando o teorema de Bayes dá a lei da probabilidade total

$\sum _{i}{P(B\mid A_{i})P(A_{i})}=\sum _{i}{P(A_{i}\mid B)P(B)}$

$P(B)=\sum _{i}{P(B\mid A_{i})P(A_{i})}$

Este resultado é usado para dar a forma estendida do teorema de Bayes,

$P(A_{i}\mid B)={\frac {P(B\mid A_{i})P(A_{i})}{\sum _{j}{P(B\mid A_{j})P(A_{j})}}}$

Esta é a forma usual do teorema de Bayes utilizado na prática, porque garante a soma de todas as probabilidades posteriores para $A_{i}$ é 1.

Possibilidades alternativas

Para possibilidades mutuamente exclusivas, as probabilidades adicionam.

$P(A\lor B)=P(A)+P(B)$ if $P(A\land B)=0$

Usando

$A\lor B=(A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B)$

Então as alternativas

$A\land \neg (A\land B)$

$B\land \neg (A\land B)$

$A\land B$

são todas mutuamente exclusivas

Também,

$(A\land \neg (A\land B))\lor (A\land B)=A$

$P(A\land \neg (A\land B))+P(A\land B)=P(A)$

$P(A\land \neg (A\land B))=P(A)-P(A\land B)$

então, colocando tudo junto,

$P(A\lor B)$

$=P((A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B))$

$=P(A\land \neg (A\land B)+P(B\land \neg (A\land B))+P(A\land B)$

$=P(A)-P(A\land B)+P(B)-P(A\land B)+P(A\land B)$

$=P(A)+P(B)-P(A\land B)$

Negação

Como,

$A\lor \neg A=true$

então

$P(A)+P(\neg A)=1$

Implicação e probabilidade condicional

Implicação é relacionada com a probabilidade condicional pela seguinte equação,

$A\to B\iff P(B\mid A)=1$

Derivação,

$A\to B$

$\iff P(A\to B)=1$

$\iff P(A\land B\lor \neg A)=1$

$\iff P(A\land B)+P(\neg A)=1$

$\iff P(A\land B)=P(A)$

$\iff P(A)\cdot P(B\mid A)=P(A)$

$\iff P(B\mid A)=1$

Testes da hipótese bayesiana

O teorema de Bayes pode ser utilizado para estimar a probabilidade de uma hipótese ou teoria H, dado alguns factos F. A probabilidade posterior de H é então

$P(H\mid F)={\frac {P(H)P(F\mid H)}{P(F)}}$

ou em termos de informação,

$P(H\mid F)=2^{-(L(H)+L(F\mid H)-L(F))}$

Ao assumir a hipótese como verdadeira, uma representação mais simples da declaração F pode ser dada. O comprimento da codificação desta representação mais simples é L (F\mid H).

$L(H)+L(F\mid H)$ representa a quantidade de informação necessária para representar os fatos F, se H é verdadeiro. L(F) é a quantidade de informação necessária para representar F, sem a hipótese H. A diferença é o quanto a representação dos fatos foi comprimida assumindo que H é verdadeiro. Esta é a evidência de que a hipótese H é verdadeira.

Se L (F) é estimada a partir de comprimento de codificação, a probabilidade obtida não estará compreendida entre 0 e 1. O valor obtido é proporcional à probabilidade, sem ser uma boa estimativa de probabilidade. O número obtido é por vezes referido como uma probabilidade relativa, sendo o quão mais provável a teoria é do que não manter a teoria.

Se um conjunto completo de hipóteses mutuamente exclusivas que fornecem prova é conhecida, uma estimativa adequada pode ser dada para a probabilidade prévia $P(F)$.

Conjunto de hipóteses

As probabilidades podem ser calculadas a partir da forma estendida do teorema de Bayes. Dada toda hipótese mutuamente exclusiva $H_{i}$ que dão provas, de tal forma que,

$L(H_{i})+L(F\mid H_{i})<L(F)$

e também a hipótese R, de que nenhuma das hipóteses é verdadeira, então,

$P(H_{i}\mid F)={\frac {P(H_{i})P(F\mid H_{i})}{P(F|R)+\sum _{j}{P(H_{j})P(F\mid H_{j})}}}$

$P(R\mid F)={\frac {P(F\mid R)}{P(F\mid R)+\sum _{j}{P(H_{j})P(F\mid H_{j})}}}$

Em termos de informação,

$P(H_{i}\mid F)={\frac {2^{-(L(H_{i})+L(F\mid H_{i}))}}{2^{-L(F\mid R)}+\sum _{j}{2^{-(L(H_{j})+L(F|\mid H_{j}))}}}}$

$P(R\mid F)={\frac {2^{-L(F\mid R)}}{2^{-L(F\mid R)}+\sum _{j}{2^{-(L(H_{j})+L(F\mid H_{j}))}}}}$

Na maioria das situações, é uma boa aproximação para supor que F é independente de R,

$P(F\mid R)=P(F)$

dando,

$P(H_{i}\mid F)\approx {\frac {2^{-(L(H_{i})+L(F\mid H_{i}))}}{2^{-L(F)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}$

$P(R\mid F)\approx {\frac {2^{-L(F)}}{2^{-L(F)}+\sum _{j}{2^{-(L(H_{j})+L(F\mid H_{j}))}}}}$

Inferência indutiva booleana

Inferência abdutiva   começa com um conjunto de fatos F que é uma declaração (expressão booleana). Raciocínio abdutivo é da forma,

Uma teoria T implica a instrução F. À medida que a teoria T é mais simples do que F, abdução diz que existe uma probabilidade de que a teoria T é implicada por F.

A teoria T, também chamado de uma explicação sobre a condição F, é uma resposta à factual "porquê" questão onipresente. Por exemplo, para a condição F é "Por que as maçãs caem?". A resposta é um T teoria que implica que as maçãs caem;

$F=G{\frac {m_{1}m_{2}}{r^{2}}}\$

Inferência indutiva é da forma,

Todos os objetos observados em uma classe C têm uma propriedade P. Portanto, existe uma probabilidade de que todos os objetos em uma classe C tem uma propriedade P.

Em termos de inferência abdutiva, todos os objetos em uma classe C ou conjunto tem uma propriedade P é uma teoria que implica a condição observada, Todos os objetos observados em uma classe C tem uma propriedade P.

Então inferência indutiva é um caso especial de inferência abdutiva. No uso comum, o termo inferência indutiva é usado frequentemente para se referir tanto a inferência abdutiva quanto a inferência indutiva.

Generalização e especialização

Inferência indutiva está relacionada à generalização. Generalizações podem ser formadas a partir de declarações substituindo-se um valor específico com adesão de uma categoria, ou por substituição adesão a uma categoria pela adesão de uma categoria mais ampla. Na lógica dedutiva, a generalização é um poderoso método de geração de novas teorias que podem ser verdadeiras. Na inferência indutiva, a generalização gera teorias que têm uma probabilidade de ser verdadeira.  

O oposto de generalização é a especialização. Especialização é usado em aplicação de uma regra geral a um caso específico. Especializações são criados a partir de generalizações através da substituição de membros de uma categoria por um valor específico, ou substituindo uma categoria com uma sub-categoria.

A classificação Linnaen dos seres vivos e objetos constitui a base para a generalização e especificação. A capacidade de identificar, reconhecer e classificar é a base para a generalização. Perceber o mundo como uma coleção de objetos parece ser um aspecto fundamental da inteligência humana. É o modelo orientado a objeto, num sentido fora da ciência da computação.

O modelo orientado a objeto é construído a partir de nossa percepção. Em particular, visão baseia-se na capacidade de comparar duas imagens e calcular a quantidade de informação é necessária para transformar ou mapear uma imagem em outra. A visão computacional utiliza este mapeamento para construir imagens 3D a partir de pares de imagens estéreo.

Programação lógica por indução é um meio de construção de teoria que implica uma condição. A abordagem da "generalização relativa menos geral (do inglês, rlgg)" de Plotkin  constrói a generalização mais simples de acordo com a condição.

O uso da indução por Newton

Isaac Newton usou argumentos indutivos na construção de sua lei da gravitação universal.  Começando com a declaração,

• O centro de uma maçã desce em direção ao centro da Terra.

Generalizando substituindo-se maçã por objeto, e Terra por objeto dá, em um sistema de dois corpos,

• O centro de um objeto cai em direção ao centro de outro objeto.

A teoria explica todos os objetos que caem, para que haja uma forte evidência para isso. A segunda observação,

• Os planetas parecem seguir uma trajetória elíptica.

Depois de alguns cálculo matemáticos complicados, pode ser visto que, se a aceleração segue a lei do quadrado inverso, então objetos seguirão uma elipse. Então, indução dá evidência para a lei do quadrado inverso.

Usando a observação de Galileu de que todos os objetos caem com a mesma velocidade,

$F_{1}=m_{1}a_{1}={\frac {m_{1}k_{1}}{r^{2}}}i_{1}$

$F_{2}=m_{2}a_{2}={\frac {m_{2}k_{2}}{r^{2}}}i_{2}$

onde $i_{1}$ e $i_{2}$ vetorizam para o centro do outro objeto. Assim, usando a terceira lei de Newton $F_{1}=-F_{2}$

$F=G{\frac {m_{1}m_{2}}{r^{2}}}$

Probabilidades para inferência indutiva

Implicação determina probabilidade de condição como,

$T\to F\iff P(F\mid T)=1$

Então,

$P(F\mid T)=1$

$L(F\mid T)=0$

Esse resultado pode ser usado nas probabilidades indicadas para o teste de hipótese Bayesiana. Para uma única teoria, H = T e,

$P(T\mid F)={\frac {P(T)}{P(F)}}$

ou em termos de informação, a probabilidade relativa é,

$P(T\mid F)=2^{-(L(T)-L(F))}$

Note que esta estimativa para P(T|F) não é uma probabilidade verdadeira. Se $L(T_{i})<L(F)$, a teoria tem evidência para apoiá-la. Então, para um conjunto de teorias $T_{i}=H_{i}$, tal que $L(T_{i})<L(F)$,

$P(T_{i}\mid F)={\frac {P(T_{i})}{P(F\mid R)+\sum _{j}{P(T_{j})}}}$

$P(R\mid F)={\frac {P(F\mid R)}{P(F\mid R)+\sum _{j}{P(T_{j})}}}$

resultando,

$P(T_{i}\mid F)\approx {\frac {2^{-L(T_{i})}}{2^{-L(F)}+\sum _{j}{2^{-L(T_{j})}}}}$

$P(R\mid F)\approx {\frac {2^{-L(F)}}{2^{-L(F)}+\sum _{j}{2^{-L(T_{j})}}}}$

Derivações

Derivação de probabilidade indutiva

Faça uma lista de todos os programas mais curtos $K_{i}$ onde cada um produz uma sequência infinita distinta de bits, e satisfaz a relação,

$T_{n}(R(K_{i}))=x$

onde,

$R(K_{i})$ é o resultado da execução do programa $K_{i}$.

$T_{n}$ trunca a seqüência depois de n bits.

O problema consiste em calcular a probabilidade de que a fonte é produzido pelo programa $K_{i}$, dado que a fonte truncada depois de n bits é x. Isto é representado pela probabilidade condicional,

$P(s=R(K_{i})\mid T_{n}(s)=x)$

Usando a forma estendida do teorema de Bayes

$P(A_{i}\mid B)={\frac {P(B\mid A_{i})\,P(A_{i})}{\sum \limits _{j}P(B\mid A_{j})\,P(A_{j})}}\cdot$

onde,

$B=(T_{n}(s)=x)$

$A_{i}=(s=R(K_{i}))$

A forma estendida baseia-se nalei da probabilidade total. Isso significa que o $A_{i}$ deve ser possibilidades distintas, que é dado pela condição de que cada $K_{i}$ produz uma sequência infinita diferente. Também uma das condições $A_{i}$ deve ser verdadeira. Isso deve ser verdade, tal como no limite em que n tende ao infinito, há sempre pelo menos um programa que produz $T_{n}(s)$.

Então, usando a forma estendida e substituindo $B$ e $A_{i}$ temos,

$P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {P(T_{n}(s)=x\mid s=R(K_{i}))\,P(s=R(K_{i}))}{\sum \limits _{j}P(T_{n}(s)=x\mid s=R(K_{j}))\,P(s=R(K_{j}))}}\cdot$

Como $K_{i}$ são escolhidos tal que $T_{n}(R(K_{i}))=x$, então,

$P(T_{n}(s)=x\mid s=R(K_{i}))=1$

A probabilidade a priori da cadeia sendo produzida a partir do programa, dada nenhuma informação sobre a cadeia, é baseada no tamanho do programa,

$P(s=R(K_{i}))=2^{-I(K_{i})}$

resultando,

$P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{\sum \limits _{j}2^{-I(K_{j})}}}\cdot$

Programas que são o mesmo ou maior que o comprimento de x não fornecem poder preditivo. Separando-os resultando,

$P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}+\sum \limits _{j:I(K_{j})>=n}2^{-I(K_{j})}}}\cdot$

Em seguida, identifique as duas probabilidades como, A probabilidade de que x tem um padrão $=\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}$ O oposto disso, A probabilidade de que x é um conjunto aleatório de bits $=\sum \limits _{j:I(K_{j})>=n}2^{-I(K_{j})}$ Mas a probabilidade a priori de que x é um conjunto aleatório de bits é $2^{-n}$. Então,

$P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{2^{-n}+\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}}}\cdot$

A probabilidade de que a fonte é aleatória, ou imprevisível é,

$P(\operatorname {random} (s)\mid T_{n}(s)=x)={\frac {2^{-n}}{2^{-n}+\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}}}\cdot$

Um modelo para inferência indutiva

Um modelo de como os mundos são construídos é usado para determinar as probabilidades de teorias,

• Uma cadeia de bits aleatória é selecionada.
• A condição é construída a partir da cadeia de bits.
• Um mundo consistente com a condição é construído.

Se w é a cadeia de bits, o mundo é criado de tal forma que $R(w)$ é verdade. Um agente inteligente tem alguns fatos sobre a palavra, representada pela cadeia de bits c, o que dá a condição,

$C=R(c)$

O conjunto de seqüências de bits idênticas a qualquer condição x é $E(x)$.

$\forall x,E(x)=\{w:R(w)\equiv x\}$

Uma teoria é uma condição mais simples que explica (ou implica) C. O conjunto de todas essas teorias é chamado de T,

$T(C)=\{t:t\to C\}$

Aplicando o teorema de Bayes

A forma estendida do teorema de Bayes pode ser aplicada

$P(A_{i}\mid B)={\frac {P(B\mid A_{i})\,P(A_{i})}{\sum \limits _{j}P(B\mid A_{j})\,P(A_{j})}}\cdot$

onde,

$B=E(C)$

$A_{i}=E(t)$

Para aplicar o teorema de Bayes o seguinte deve ser mantido,

• $A_{i}$ é uma partição do espaço de evento.

Para que $T(C)$ seja uma partição, nenhum sequência de bits n pode pertencer a duas teorias. Para provar isso, assuma que elas podem e derivam uma contradição,

$N\in T\land N\in M\land N\neq M\land n\in E(N)\land n\in E(M)$

$\implies N\neq M\land R(n)\equiv N\land R(n)\equiv M$

$\implies \operatorname {false}$

Em segundo lugar, provar que T inclui todos os resultados consistentes com a condição. Como todas as teorias consistentes com C estão incluídas, $R(w)$ deve estar nesse conjunto.

Assim, o teorema de Bayes pode ser aplicado como especificado resultando,

$\forall t\in T(C),P(E(t)\mid E(C))={\frac {P(E(t))\cdot P(E(C)\mid E(t))}{\sum _{j\in T(C)}P(E(j))\cdot P(E(C)\mid E(j))}}$

Usando a lei da implicação e probabilidade condicional, a definição de $T(C)$ implica,

$\forall t\in T(C),P(E(C)\mid E(t))=1$

A probabilidade de cada teoria em T é dada por,

$\forall t\in T(C),P(E(t))=\sum _{n:R(n)\equiv t}2^{-L(n)}$

então,

$\forall t\in T(C),P(E(t)\mid E(C))={\frac {\sum _{n:R(n)\equiv t}2^{-L(n)}}{\sum _{j\in T(C)}\sum _{m:R(m)\equiv j}2^{-L(m)})}}$

Finalmente as probabilidades dos eventos podem ser identificadas com as probabilidades da condição cujo resultado do evento satisfaz,

$\forall t\in T(C),P(E(t)\mid E(C))=P(t\mid C)$

resultando,

$\forall t\in T(C),P(t\mid C)={\frac {\sum _{n:R(n)\equiv t}2^{-L(n)}}{\sum _{j\in T(C)}\sum _{m:R(m)\equiv j}2^{-L(m)}}}$

Essa é a probabilidade da teoria t após a observação de que a condição C é mantida.

Removendo teorias sem poder preditivo

Teorias que são menos prováveis do que a condição C não têm poder preditivo. Separá-los resulta em,

$\forall t\in T(C),P(t\mid C)={\frac {P(E(t))}{(\sum _{j:j\in T(C)\land P(E(j))>P(E(C))}P(E(j)))+(\sum _{j:j\in T(C)\land P(E(j))\leq P(E(C))}P(j))}}$

A probabilidade das teorias sem poder preditivo em C é a mesma que a probabilidade de C. Assim,

$P(E(C))=\sum _{j:j\in T(C)\land P(E(j))\leq P(E(C))}P(j)$

Então a probabilidade

$\forall t\in T(C),P(t\mid C)={\frac {P(E(t))}{P(E(C))+\sum _{j:j\in T(C)\land P(E(j))>P(E(C))}P(E(j))}}$

e a probabilidade de nenhuma previsão para C, escrito como $\operatorname {random} (C)$,

$P(\operatorname {random} (C)\mid C)={\frac {P(E(C))}{P(E(C))+\sum _{j:j\in T(C)\land P(E(j))>P(E(C))}P(E(j))}}$

A probabilidade de uma condição foi dada como,

$\forall t,P(E(t))=\sum _{n:R(n)\equiv t}2^{-L(n)}$

Cadeias de bits para as teorias que são mais complexas do que a cadeia de bits dada ao agente como entrada não têm poder preditivo. Lá probabilidades são melhor incluídas no caso aleatório. Para implementar isso, uma nova definição é dada como F em,

$\forall t,P(F(t,c))=\sum _{n:R(n)\equiv t\land L(n)<L(c)}2^{-L(n)}$

Usando F, uma versão melhorada das probabilidades abdutivas é,

$\forall t\in T(C),P(t\mid C)={\frac {P(F(t,c))}{P(F(C,c))+\sum _{j:j\in T(C)\land P(F(j,c))>P(F(C,c))}P(E(j,c))}}$

$P(\operatorname {random} (C)\mid C)={\frac {P(F(C,c))}{P(F(C,c))+\sum _{j:j\in T(C)\land P(F(j,c))>P(F(C,c))}P(F(j,c))}}$

Pessoas chave

• William of Ockham
• Thomas Bayes
• Ray_Solomonoff
• Andrey Kolmogorov
• Chris_Wallace
• D. M. Boulton
• Jorma_Rissanen
• Marcus Hutter

Ver também

• Raciocínio abdutivo
• Probabilidade algorítmica
• Teoria algorítmica de informação
• Inferência bayesiana
• Teoria da informação
• Inferência indutiva
• Programação lógico-indutiva
• Raciocínio indutivo
• Aprendizagem
• Mensagem de comprimento mínimo
• Descrição de comprimento mínimo
• Navalha de Occam
• Teoria da inferência indutiva de Solomonoff
• Inteligência artificial universal

Ligações externas

• Rathmanner, S and Hutter, M., "A Philosophical Treatise of Universal Induction" in Entropy 2011, 13, 1076–1136: A very clear philosophical and mathematical analysis of Solomonoff's Theory of Inductive Inference.
• C.S. Wallace, Statistical and Inductive Inference by Minimum Message Length, Springer-Verlag (Information Science and Statistics), ISBN 0-387-23795-X, May 2005 – chapter headings, table of contents and sample pages.