Probabilidade indutiva - Inductive probability

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

Existem três fontes de conhecimento: inferência , comunicação e dedução. Informações de relés de comunicação encontradas usando outros métodos. A dedução estabelece novos fatos com base em fatos existentes. A inferência estabelece novos fatos a partir dos dados. Sua base é o teorema de Bayes .

As informações que descrevem o mundo são escritas em uma linguagem. Por exemplo, uma linguagem matemática simples de proposições pode ser escolhida. As frases podem ser escritas neste idioma como cadeias de caracteres. Mas no computador é possível codificar essas frases como cadeias de bits (1s e 0s). Em seguida, a linguagem pode ser codificada de forma que as frases mais comumente usadas sejam as mais curtas. Essa linguagem interna representa implicitamente as probabilidades de afirmações.

A navalha de Occam diz que a "teoria mais simples, consistente com os dados tem mais probabilidade de ser correta". A "teoria mais simples" é interpretada como a representação da teoria escrita nesta linguagem interna. A teoria com a codificação mais curta nesta linguagem interna tem mais probabilidade de estar correta.

História

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

O teorema de Bayes é nomeado após o Rev. Thomas Bayes 1701-1761. A inferência bayesiana ampliou a aplicação da probabilidade a muitas situações em que uma população não estava bem definida. Mas o teorema de Bayes sempre dependeu de probabilidades anteriores, para gerar novas probabilidades. Não estava claro de onde essas probabilidades anteriores deveriam vir.

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

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

Marcus Hutter combinou a teoria da decisão com o trabalho de Ray Solomonoff e Andrey Kolmogorov para fornecer uma teoria para o comportamento ótimo de Pareto para um agente inteligente , por volta de 1998.

Descrição / comprimento mínimo da mensagem

O programa com a duração mais curta que corresponde aos dados é o que tem maior probabilidade de prever dados futuros. Esta é a tese por trás dos métodos de comprimento mínimo de mensagem e comprimento mínimo de descrição .

À primeira vista, o teorema de Bayes parece diferente do princípio do comprimento mínimo da mensagem / descrição. Olhando mais de perto, acaba sendo o mesmo. O teorema de Bayes é sobre probabilidades condicionais, e afirma a probabilidade de que o evento B aconteça se primeiro o evento A acontecer:

${\ displaystyle P (A \ land B) = P (B) \ cdot P (A | B) = P (A) \ cdot P (B | A)}$

torna-se em termos de comprimento de mensagem L ,

${\ displaystyle L (A \ land B) = L (B) + L (A | B) = L (A) + L (B | A).}$

Isso significa que, se todas as informações são fornecidas descrevendo um evento, o comprimento da informação pode ser usado para fornecer a probabilidade bruta do evento. Portanto, se a informação que descreve a ocorrência de A é fornecida, junto com a informação que descreve B dado A , então todas as informações que descrevem A e B foram fornecidas.

Sobreajuste

O sobreajuste ocorre quando o modelo corresponde ao ruído aleatório e não ao padrão dos dados. Por exemplo, considere a situação em que uma curva é ajustada a um conjunto de pontos. Se um polinômio com muitos termos for ajustado, ele poderá representar os dados de forma mais próxima. Então, o ajuste será melhor e as informações necessárias para descrever os desvios da curva ajustada serão menores. Menor comprimento de informação significa maior probabilidade.

No entanto, as informações necessárias para descrever a curva também devem ser consideradas. A informação total para uma curva com muitos termos pode ser maior do que para uma curva com menos termos, que não tem um ajuste tão bom, mas precisa de menos informações para descrever o polinômio.

Inferência baseada na complexidade do programa

A teoria da inferência indutiva de Solomonoff também é uma inferência indutiva. Uma sequência de bits x é observada. Em seguida, considere todos os programas que geram strings começando com x . Fundidos na forma de inferência indutiva, os programas são teorias que implicam na observação da sequência de bits x .

O método usado aqui para fornecer probabilidades para inferência indutiva é baseado na teoria da inferência indutiva de Solomonoff .

Detectando padrões nos dados

Se todos os bits forem 1, então as pessoas inferem que há um viés na moeda e que é mais provável que o próximo bit também seja 1. Isso é descrito como aprender ou detectar um padrão nos dados.

Esse padrão pode ser representado por um programa de computador . Um programa de computador curto pode ser escrito que produz uma série de bits que são todos 1. Se o comprimento do programa K é de bits, então sua probabilidade anterior é, ${\ displaystyle L (K)}$

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

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

A complexidade de Kolmogorov não é computável. Isso está relacionado ao problema da parada . Ao pesquisar o programa mais curto, alguns programas podem entrar em um loop infinito.

Considerando todas as teorias

O filósofo grego Epicuro é citado como tendo dito "Se mais de uma teoria é consistente com as observações, mantenha todas as teorias".

Como em um romance policial, todas as teorias devem ser consideradas na determinação do provável assassino, portanto, com a probabilidade indutiva, todos os programas devem ser considerados na determinação dos prováveis ​​bits futuros que surgem do fluxo de bits.

Programas que já são mais longos do que n não têm poder preditivo. A probabilidade bruta (ou anterior) de que o padrão de bits seja aleatório (não tem padrão) é . ${\ displaystyle 2 ^ {- n}}$

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

A probabilidade de receber uma sequência de bits y após 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 .

Antigos universais

A linguagem de programação afeta as previsões do próximo bit na string. A linguagem atua como uma probabilidade prévia . Este é um problema particular onde os códigos de linguagem de programação para números e outros tipos de dados. Intuitivamente, pensamos que 0 e 1 são números simples e que os números primos são de alguma forma mais complexos do que os números que podem ser compostos.

O uso da complexidade de Kolmogorov fornece uma estimativa imparcial (a priori universal) da probabilidade anterior de um número. Como um experimento de pensamento, um agente inteligente pode ser equipado com um dispositivo de entrada de dados fornecendo uma série de números, após 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 nem sabem sobre essas funções de transformação. Então, parece não haver base racional para preferir uma função a outra. Um prior universal garante que, embora dois agentes possam ter diferentes distribuições de probabilidade inicial para a entrada de dados, a diferença será limitada por uma constante.

Portanto, os antecedentes universais não eliminam um viés inicial, mas o reduzem e o limitam. Sempre que descrevemos um evento em uma linguagem, seja usando uma linguagem natural ou outra, a linguagem codificou nele nossas expectativas anteriores. Portanto, alguma confiança em probabilidades anteriores é inevitável.

Surge um problema quando as expectativas anteriores de um agente inteligente interagem com o ambiente para formar um loop de feedback de auto-reforço. Este é o problema do preconceito ou preconceito. Prioridades universais reduzem, mas não eliminam esse problema.

Inteligência artificial universal

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

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

• Explorando o meio ambiente; realizando ações para obter respostas que ampliem o conhecimento dos agentes.
• Competir ou cooperar com outro agente; jogos.
• Equilibrar recompensas de curto e longo prazo.

Em geral, nenhum agente sempre fornecerá as melhores ações em todas as situações. Uma escolha particular feita por um agente pode estar errada, e o ambiente pode não fornecer nenhuma maneira para o agente se recuperar de uma escolha ruim inicial. No entanto, o agente é Pareto ótimo no sentido de que nenhum outro agente se sairá melhor do que esse agente neste ambiente, sem se sair 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 usadas para evitar isso. A velocidade de processamento e a explosão combinatória continuam sendo os principais fatores limitantes da inteligência artificial .

Probabilidade

Probabilidade é a representação de conhecimento incerto ou parcial sobre a verdade das afirmações. As probabilidades são estimativas subjetivas e pessoais de resultados prováveis ​​com base em experiências anteriores 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 o sol nascer amanhã. Não nos referimos à "sua probabilidade" de que o sol nasça. Mas, para que a inferência seja modelada corretamente, a probabilidade deve ser pessoal, e o ato da inferência gera novas probabilidades posteriores a partir de probabilidades anteriores.

As probabilidades são pessoais porque dependem do conhecimento do indivíduo. As probabilidades são subjetivas porque sempre dependem, até certo ponto, de probabilidades anteriores atribuídas pelo indivíduo. Subjetivo não deve ser entendido aqui como vago ou indefinido.

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

No entanto, se o agente usar a probabilidade de interagir com o ambiente, pode haver um feedback, de modo que dois agentes em um ambiente idêntico começando com antecedentes apenas ligeiramente diferentes acabem com probabilidades completamente diferentes. Nesse caso, a teoria da decisão ideal , como na Inteligência Artificial Universal de Marcus Hütter, dará a Pareto um desempenho ideal para o agente. Isso significa que nenhum outro agente inteligente poderia ter um desempenho melhor em um ambiente sem ter um desempenho pior em outro.

Comparação com probabilidade dedutiva

Nas teorias de probabilidade dedutiva, as probabilidades são absolutas, independentemente do indivíduo que faz a avaliação. Mas as probabilidades dedutivas são baseadas em,

• Conhecimento compartilhado.
• Fatos presumidos, que devem ser inferidos dos dados.

Por exemplo, em um ensaio, os participantes estão cientes do resultado de todo o histórico anterior de ensaios. Eles também presumem que cada resultado é igualmente provável. Juntos, isso permite que um único valor incondicional de probabilidade seja definido.

Mas, na realidade, cada indivíduo não possui as mesmas informações. E, em geral, a probabilidade de cada resultado não é igual. Os dados podem ser carregados e esse carregamento precisa ser inferido a partir dos dados.

Probabilidade como estimativa

O princípio da indiferença desempenhou um papel fundamental na teoria da probabilidade. Diz que, se N declarações são simétricas, de modo que uma condição não pode ser preferida a outra, todas as declarações são igualmente prováveis.

Levado a sério, ao avaliar a probabilidade, esse princípio leva a contradições. Suponha que haja 3 sacos de ouro à distância e um seja solicitado a selecionar um. Então, por causa da distância, não é possível ver os tamanhos das bolsas. Você estima, usando o princípio da indiferença, que cada bolsa tem quantidades iguais de ouro e cada bolsa tem um terço do ouro.

Agora, enquanto um de nós não está olhando, o outro pega uma das sacolas e divide em 3 sacolas. Agora são 5 sacos de ouro. O princípio da indiferença agora diz que cada saco tem um quinto do ouro. Estima-se que uma bolsa que tinha um terço do ouro agora tem um quinto do ouro.

Tomados como um valor associado à bolsa, os valores são diferentes, portanto, contraditórios. Mas tomados como uma estimativa dada em um cenário particular, ambos os valores são estimativas separadas dadas em circunstâncias diferentes e não há razão para acreditar que eles sejam iguais.

As estimativas de probabilidades anteriores são particularmente suspeitas. As estimativas serão construídas que não seguem nenhuma distribuição de frequência consistente. Por esta razão, as probabilidades anteriores são consideradas como estimativas de probabilidades, em vez de probabilidades.

Um tratamento teórico completo seria associado a cada probabilidade,

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

Combinando abordagens de probabilidade

A probabilidade indutiva combina duas abordagens diferentes de probabilidade.

• Probabilidade e informação
• Probabilidade e frequência

Cada abordagem oferece um ponto de vista ligeiramente diferente. A teoria da informação é usada para relacionar probabilidades a quantidades de informação. Esta abordagem é freqüentemente usada para fornecer estimativas de probabilidades anteriores.

A probabilidade frequentista define as probabilidades como declarações objetivas sobre a frequência com que um evento ocorre. Essa abordagem pode ser ampliada definindo-se que as provações sejam sobre mundos possíveis . Declarações sobre mundos possíveis definem eventos .

Probabilidade e informação

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

Ao considerar alguns dados como uma sequência de bits, as probabilidades anteriores para uma sequência de 1s e 0s, a probabilidade de 1 e 0 é igual. Portanto, cada bit extra reduz pela metade a probabilidade de uma sequência de bits. Isso leva à conclusão de que,

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

Onde está a probabilidade da sequência de bits e seu comprimento. ${\ displaystyle P (x)}$${\ displaystyle x}$${\ displaystyle L (x)}$

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

Combinando informações

Duas declarações e podem ser representadas por duas codificações separadas. Então, o comprimento da codificação é, ${\ displaystyle A}$${\ displaystyle B}$

${\ displaystyle L (A \ land B) = L (A) + L (B)}$

ou em termos de probabilidade,

${\ displaystyle P (A \ land B) = P (A) P (B)}$

Mas essa lei nem sempre é verdadeira porque pode haver um método mais curto de codificação se assumirmos . Portanto, a lei de probabilidade acima se aplica apenas se e for "independente". ${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle B}$

A linguagem interna da informação

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

O conhecimento é representado como declarações . Cada declaração é uma expressão booleana . As expressões são codificadas por uma função que recebe uma descrição (em relação ao valor) da expressão e a codifica como uma string de bits.

O comprimento da codificação de uma declaração fornece uma estimativa da probabilidade de uma declaração. Esta estimativa de probabilidade será freqüentemente usada como a probabilidade anterior de uma afirmação.

Tecnicamente, essa estimativa não é uma probabilidade porque não é construída a partir de uma distribuição de frequência. As estimativas de probabilidade fornecidas por ele nem sempre obedecem à lei do total de probabilidade . A aplicação da lei da probabilidade total a vários cenários geralmente fornecerá uma estimativa de probabilidade mais precisa da probabilidade anterior do que a estimativa do comprimento da declaração.

Expressões de codificação

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 de Huffman deve distinguir os 3 casos. O comprimento de cada código é baseado na frequência de cada tipo de subexpressão.

Inicialmente, todas as constantes são atribuídas ao mesmo comprimento / probabilidade. As constantes posteriores podem receber uma probabilidade usando o código de Huffman com base no número de usos da função id em todas as expressões registradas até agora. Ao usar um código de Huffman, o objetivo é estimar probabilidades, não compactar os dados.

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

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

Distribuição de números

Nenhuma representação explícita de números naturais é fornecida. No entanto, os números naturais podem ser construídos aplicando-se a função sucessora a 0 e, em seguida, aplicando-se outras funções aritméticas. Uma distribuição de números naturais está implícita nisso, com base na complexidade de construir cada número.

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

Probabilidade e frequência

A probabilidade de um evento pode ser interpretada como as frequências de resultados em que a afirmação é verdadeira dividida pelo número total de resultados. Se os resultados formarem um continuum, a frequência pode precisar ser substituída por uma medida .

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

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

Probabilidade Condicional

Cada probabilidade está sempre associada ao estado de conhecimento em um determinado ponto do argumento. As probabilidades antes de uma inferência são conhecidas como probabilidades anteriores e as probabilidades posteriores são conhecidas como probabilidades posteriores.

A probabilidade depende dos fatos conhecidos. A verdade de um fato limita o domínio dos resultados aos resultados consistentes com o fato. Probabilidades anteriores são as probabilidades antes de um fato ser conhecido. As probabilidades posteriores são depois que um fato é conhecido. As probabilidades posteriores seriam condicionadas ao fato. a probabilidade de ser verdadeira, dado que é verdadeira, é escrita como:${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle P (B | A).}$

Todas as probabilidades são, em certo sentido, condicionais. A probabilidade anterior de é, ${\ displaystyle B}$

${\ displaystyle P (B) = P (B | \ top)}$

A abordagem frequentista aplicada a mundos possíveis

Na abordagem frequentista , as probabilidades são definidas como a razão entre o número de resultados em um evento e o número total de resultados. No modelo de mundo possível , cada mundo possível é um resultado, e declarações sobre mundos possíveis definem os eventos. A probabilidade de uma afirmação ser verdadeira é o número de mundos possíveis onde a afirmação é verdadeira dividido pelo número total de mundos possíveis. A probabilidade de uma afirmação ser verdadeira sobre mundos possíveis é, então, ${\ displaystyle A}$

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

Para uma probabilidade condicional.

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

então

${\ displaystyle {\ begin {alinhados} P (A \ land B) & = {\ frac {| \ {x: A (x) \ land B (x) \} |} {| x: \ top |}} \\ [8pt] & = {\ frac {| \ {x: A (x) \ land B (x) \} |} {| \ {x: A (x) \} |}} {\ frac {| \ {x: A (x) \} |} {| x: \ top |}} \\ [8pt] & = P (A) P (B | A) \ end {alinhado}}}$

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

${\ displaystyle P (A \ land B) = P (A) P (B | A) = P (B) P (A | B)}$

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

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

${\ displaystyle L (A \ land B) = L (A) + L (B | A) = L (B) + L (A | B)}$

Duas afirmações A e B são consideradas independentes se saber a verdade de A não muda a probabilidade de B. Matematicamente, isto é,

${\ displaystyle P (B) = P (B | A)}$

então o Teorema de Bayes se reduz a,

${\ displaystyle P (A \ land B) = P (A) P (B)}$

A lei do total de probabilidade

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

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

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

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

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

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

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

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

Possibilidades alternativas

Para possibilidades mutuamente exclusivas, as probabilidades somam.

${\ displaystyle P (A \ lor B) = P (A) + P (B), \ qquad {\ text {if}} P (A \ land B) = 0}$

Usando

${\ displaystyle A \ lor B = (A \ land \ neg (A \ land B)) \ lor (B \ land \ neg (A \ land B)) \ lor (A \ land B)}$

Então as alternativas

${\ displaystyle A \ land \ neg (A \ land B), \ quad B \ land \ neg (A \ land B), \ quad A \ land B}$

são todos mutuamente exclusivos. Também,

${\ displaystyle (A \ land \ neg (A \ land B)) \ lor (A \ land B) = A}$

${\ displaystyle P (A \ land \ neg (A \ land B)) + P (A \ land B) = P (A)}$

${\ displaystyle P (A \ land \ neg (A \ land B)) = P (A) -P (A \ land B)}$

então, juntando tudo,

${\ displaystyle {\ begin {alinhados} 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 \ terreno B) + P (B) -P (A \ terreno B) + P (A \ terreno B) \\ & = P (A) + P (B) -P ( A \ land B) \ end {alinhado}}}$

Negação

Como,

${\ displaystyle A \ lor \ neg A = \ top}$

então

${\ displaystyle P (A) + P (\ neg A) = 1}$

Implicação e probabilidade de condição

A implicação está relacionada à probabilidade condicional pela seguinte equação,

${\ displaystyle A \ to B \ iff P (B | A) = 1}$

Derivação,

${\ displaystyle {\ begin {alinhados} A \ para 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 | A) = P (A) \\ & \ iff P (B | A) = 1 \ end {alinhado}}}$

Teste de hipótese bayesiana

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

${\ displaystyle P (H | F) = {\ frac {P (H) P (F | H)} {P (F)}}}$

ou em termos de informação,

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

Ao assumir que a hipótese é verdadeira, uma representação mais simples da afirmação F pode ser fornecida. O comprimento da codificação desta representação mais simples é${\ displaystyle L (F | H).}$

${\ displaystyle L (H) + L (F | H)}$representa a quantidade de informação necessária para representar os fatos F, se H for verdadeiro. é 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 ao assumir que H é verdadeiro. Esta é a evidência de que a hipótese H é verdadeira. ${\ displaystyle L (F)}$

Se for estimado a partir do comprimento de codificação , a probabilidade obtida não ficará entre 0 e 1. O valor obtido é proporcional à probabilidade, sem ser uma boa estimativa de probabilidade. O número obtido é às vezes referido como uma probabilidade relativa, sendo o quanto mais provável a teoria é do que não sustentá-la. ${\ displaystyle L (F)}$

Se um conjunto completo de hipóteses mutuamente exclusivas que fornecem evidências for conhecido, uma estimativa adequada pode ser fornecida para a probabilidade anterior . ${\ displaystyle P (F)}$

Conjunto de hipóteses

As probabilidades podem ser calculadas a partir da forma estendida do teorema de Bayes. Dadas todas as hipóteses mutuamente exclusivas que fornecem evidências, de tal forma que, ${\ displaystyle H_ {i}}$

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

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

${\ displaystyle {\ begin {alinhados} P (H_ {i} | F) & = {\ frac {P (H_ {i}) P (F | H_ {i})} {P (F | R) + \ soma _ {j} {P (H_ {j}) P (F | H_ {j})}}} \\ [8pt] P (R | F) & = {\ frac {P (F | R)} { P (F | R) + \ sum _ {j} {P (H_ {j}) P (F | H_ {j})}}} \ end {alinhado}}}$

Em termos de informação,

${\ displaystyle {\ begin {alinhados} P (H_ {i} | F) & = {\ frac {2 ^ {- (L (H_ {i}) + L (F | H_ {i}))}} { 2 ^ {- L (F | R)} + \ sum _ {j} 2 ^ {- (L (H_ {j}) + L (F | H_ {j}))}}} \\ [8pt] P (R | F) & = {\ frac {2 ^ {- L (F | R)}} {2 ^ {- L (F | R)} + \ sum _ {j} {2 ^ {- (L ( H_ {j}) + L (F | H_ {j}))}}}} \ end {alinhado}}}$

Na maioria das situações, é uma boa aproximação assumir que é independente de , o que significa dar, ${\ displaystyle F}$${\ displaystyle R}$${\ displaystyle P (F | R) = P (F)}$

${\ displaystyle {\ begin {alinhados} P (H_ {i} | F) & \ approx {\ frac {2 ^ {- (L (H_ {i}) + L (F | H_ {i}))}} {2 ^ {- L (F)} + \ sum _ {j} {2 ^ {- (L (H_ {j}) + L (F | H_ {j}))}}}} \\ [8pt] P (R | F) & \ aprox {\ frac {2 ^ {- L (F)}} {2 ^ {- L (F)} + \ sum _ {j} {2 ^ {- (L (H_ { j}) + L (F | H_ {j}))}}}} \ end {alinhado}}}$

Inferência indutiva booleana

A inferência abdutiva começa com um conjunto de fatos F que é uma afirmação (expressão booleana). O raciocínio abdutivo é da forma,

Uma teoria T implica a declaração F. Como a teoria T é mais simples do que F, rapto diz que há uma probabilidade de que a teoria T está implícito F .

A teoria T , também chamada de explicação da condição F , é uma resposta à onipresente pergunta factual "por que". Por exemplo, para a condição F é "Por que as maçãs caem?". A resposta é uma teoria T que implica que as maçãs caem;

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

A inferência indutiva é da forma,

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

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

Portanto, a inferência indutiva é um caso especial de inferência abdutiva. No uso comum, o termo inferência indutiva é freqüentemente usado para se referir a inferência abdutiva e indutiva.

Generalização e especialização

A inferência indutiva está relacionada à generalização . As generalizações podem ser formadas a partir de declarações substituindo um valor específico pela associação de uma categoria ou substituindo a associação de uma categoria pela associação de uma categoria mais ampla. Na lógica dedutiva, a generalização é um método poderoso de gerar novas teorias que podem ser verdadeiras. Na inferência indutiva, a generalização gera teorias que têm probabilidade de serem verdadeiras.

O oposto de generalização é a especialização. A especialização é usada para aplicar uma regra geral a um caso específico. As especializações são criadas a partir de generalizações, substituindo a associação de uma categoria por um valor específico ou substituindo uma categoria por uma subcategoria.

A classificação de Linnaen de coisas e objetos vivos constitui a base para 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-chave da inteligência humana. É o modelo orientado a objetos, no sentido não da ciência da computação .

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

A programação lógica indutiva é um meio de construir teoria que implica uma condição. A abordagem de " generalização relativa mínima geral (rlgg) " de Plotkin constrói a generalização mais simples consistente com a condição.

O uso de 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çã cai em direção ao centro da terra.

Generalizar substituindo 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 caindo, portanto, há fortes evidências disso. A segunda observação,

• Os planetas parecem seguir um caminho elíptico.

Depois de alguns cálculos matemáticos complicados , pode-se ver que se a aceleração seguir a lei do inverso do quadrado, os objetos seguirão uma elipse. Portanto, a indução fornece evidências para a lei do inverso do quadrado.

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

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

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

onde e vetores em direção ao centro do outro objeto. Então, usando a terceira lei de Newton${\ displaystyle i_ {1}}$${\ displaystyle i_ {2}}$ ${\ displaystyle F_ {1} = - F_ {2}}$

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

Probabilidades para inferência indutiva

A implicação determina a probabilidade da condição como,

${\ displaystyle T \ a F \ iff P (F | T) = 1}$

Então,

${\ displaystyle P (F | T) = 1}$

${\ displaystyle L (F | T) = 0}$

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

${\ displaystyle P (T | F) = {\ frac {P (T)} {P (F)}}}$

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

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

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

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

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

dando,

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

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

Derivações

Derivação da probabilidade indutiva

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

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

onde é o resultado da execução do programa e trunca a string após n bits. ${\ displaystyle R (K_ {i})}$${\ displaystyle K_ {i}}$${\ displaystyle T_ {n}}$

O problema é calcular a probabilidade de que a fonte seja produzida pelo programa, dado que a fonte truncada após n bits é x . Isso é representado pela probabilidade condicional, ${\ displaystyle K_ {i},}$

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

Usando a forma estendida do teorema de Bayes

${\ displaystyle P (s = R (K_ {i}) | T_ {n} (s) = x) = {\ frac {P (T_ {n} (s) = x | s = R (K_ {i} )) P (s = R (K_ {i}))} {\ sum _ {j} P (T_ {n} (s) = x | s = R (K_ {j})) P (s = R ( K_ {j}))}}.}$

A forma estendida depende da lei da probabilidade total . Isso significa que devem ser possibilidades distintas, o que é dado pela condição de que cada uma produza uma string infinita diferente. Além disso, uma das condições deve ser verdadeira. Isso deve ser verdade, pois no limite sempre há pelo menos um programa que produz . ${\ displaystyle s = R (K_ {i})}$${\ displaystyle K_ {i}}$${\ displaystyle s = R (K_ {i})}$${\ displaystyle n \ to \ infty,}$${\ displaystyle T_ {n} (s)}$

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

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

A probabilidade a priori de a string ser produzida a partir do programa, sem informações sobre a string, é baseada no tamanho do programa,

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

dando,

${\ displaystyle P (s = R (K_ {i}) | T_ {n} (s) = x) = {\ frac {2 ^ {- I (K_ {i})}} {\ sum _ {j} 2 ^ {- I (K_ {j})}}}.}$

Programas que são iguais ou maiores que o comprimento de x não fornecem poder preditivo. Separe-os de dar,

${\ displaystyle P (s = R (K_ {i}) | T_ {n} (s) = x) = {\ frac {2 ^ {- I (K_ {i})}} {\ sum _ {j: I (K_ {j}) <n} 2 ^ {- I (K_ {j})} + \ sum _ {j: I (K_ {j}) \ geqslant n} 2 ^ {- I (K_ {j} )}}}.}$

Em seguida, identifique as duas probabilidades como,

${\ displaystyle P (x {\ text {has pattern}}) = \ sum _ {j: I (K_ {j}) <n} 2 ^ {- I (K_ {j})}}$

${\ displaystyle P (x {\ text {is random}}) = \ sum _ {j: I (K_ {j}) \ geqslant n} 2 ^ {- I (K_ {j})}}$

Mas a probabilidade anterior de que x seja um conjunto aleatório de bits é . Então, ${\ displaystyle 2 ^ {- n}}$

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

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

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

Um modelo para inferência indutiva

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

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

Se w for a string de bits, o mundo é criado de forma que seja verdadeiro. Um agente inteligente tem alguns fatos sobre a palavra, representados pela string de bits c , que fornece a condição, ${\ displaystyle R (w)}$

${\ displaystyle C = R (c)}$

O conjunto de strings de bits idêntico a qualquer condição x é . ${\ displaystyle E (x)}$

${\ displaystyle \ 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 ,

${\ displaystyle T (C) = \ {t: t \ para C \}}$

Aplicando o teorema de Bayes

forma estendida do teorema de Bayes pode ser aplicada

${\ displaystyle P (A_ {i} | B) = {\ frac {P (B | A_ {i}) \, P (A_ {i})} {\ sum _ {j} P (B | A_ {j }) \, P (A_ {j})}},}$

Onde,

${\ displaystyle B = E (C)}$

${\ displaystyle A_ {i} = E (t)}$

Para aplicar o teorema de Bayes, o seguinte deve valer: é uma partição do espaço de eventos. ${\ displaystyle A_ {i}}$

Por ser uma partição, nenhuma string de bits n pode pertencer a duas teorias. Para provar isso, presuma que eles podem e derivam uma contradição, ${\ displaystyle T (C)}$

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

${\ displaystyle \ implica (N \ neq M) \ land R (n) \ equiv N \ land R (n) \ equiv M}$

${\ displaystyle \ implica \ bot}$

Em segundo lugar, prove que T inclui todos os resultados consistentes com a condição. Como todas as teorias consistentes com C estão incluídas, então devem estar neste conjunto. ${\ displaystyle R (w)}$

Portanto, o teorema de Bayes pode ser aplicado conforme especificado,

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

Usando a lei de probabilidade de implicação e condição , a definição de implica, ${\ displaystyle T (C)}$

${\ displaystyle \ forall t \ in T (C), P (E (C) | E (t)) = 1}$

A probabilidade de cada teoria em T é dada por,

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

tão,

${\ displaystyle \ forall t \ in T (C), P (E (t) | 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 que os resultados no evento satisfazem,

${\ displaystyle \ forall t \ in T (C), P (E (t) | E (C)) = P (t | C)}$

dando

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

Esta é a probabilidade da teoria t depois de observar que a condição C é válida.

Removendo teorias sem poder preditivo

As teorias menos prováveis ​​do que a condição C não têm poder preditivo. Separe-os de dar,

${\ displaystyle \ forall t \ in T (C), P (t | C) = {\ frac {P (E (t))} {(\ sum _ {j: j \ in T (C) \ land P (E (j))> P (E (C))} P (E (j))) + (\ sum _ {j: j \ em 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 . Então,

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

Então, a probabilidade

${\ displaystyle \ forall t \ in T (C), P (t | 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, escrita como , ${\ displaystyle \ operatorname {random} (C)}$

${\ displaystyle P ({\ text {random}} (C) | 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,

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

As sequências de bits para teorias que são mais complexas do que as sequências de bits fornecidas ao agente como entrada não têm poder preditivo. Essas probabilidades são melhor incluídas no caso aleatório . Para implementar isso, uma nova definição é dada como F in,

${\ displaystyle \ 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 é,

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

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

Pessoas chave

• Guilherme de Ockham
• Thomas Bayes
• Ray Solomonoff
• Andrey Kolmogorov
• Chris Wallace
• DM Boulton
• Jorma Rissanen
• Marcus Hutter

Veja também

• Raciocínio abdutivo
• Probabilidade algorítmica
• Teoria da Informação Algorítmica
• Inferência bayesiana
• Teoria da informação
• Inferência indutiva
• Programação lógica indutiva
• Raciocínio indutivo
• Aprendendo
• Comprimento mínimo da mensagem
• Comprimento mínimo da descrição
• Navalha de Occam
• Teoria da inferência indutiva de Solomonoff
• Inteligência artificial universal

Referências

links externos

• Rathmanner, S e Hutter, M., "A Philosophical Treatise of Universal Induction" in Entropy 2011, 13, 1076-1136: Uma análise filosófica e matemática muito clara da Teoria da Inferência Indutiva de Solomonoff.
• CS Wallace , Statistical and Inductive Inference by Minimum Message Length , Springer-Verlag (Ciência da Informação e Estatística), ISBN  0-387-23795-X , maio de 2005 - títulos dos capítulos , índice e páginas de amostra .