Distribuições de Probabilidades e Complexidade Computacional

9

Esta questão é sobre a interseção da teoria da probabilidade e da complexidade computacional. Uma observação importante é que algumas distribuições são mais fáceis de gerar do que outras. Por exemplo, o problema

Dado um número n , retorne um número uniformemente distribuído i com .0i<n

é fácil de resolver. Por outro lado, o seguinte problema é ou parece ser muito mais difícil.

Dado um número , retorne um número tal que seja (o número Gödel de) uma prova válida de comprimento n na aritmética do Peano. Além disso, se o número de tais provas for , a probabilidade de obter qualquer prova específica de comprimento deve ser .i i p r ( n ) n 1niipr(n)n1pr(n)

Isso me sugere que as distribuições de probabilidade vêm com uma noção de complexidade computacional. Além disso, essa complexidade provavelmente está intimamente relacionada aos problemas de decisão subjacentes (sub-recursivos, por exemplo , , , recursivos, recursivamente enumeráveis ​​ou piores).E X PPEXP

Minha pergunta é: como se define a complexidade computacional das distribuições de probabilidade, especialmente quando o problema de decisão subjacente não é decidível. Tenho certeza de que isso já foi investigado, mas não sei para onde procurar.

Martin Berger
fonte
11
Outro exemplo interessante (mas que é decidível) é a transformação quântica de Fourier. Dado que retorna um número tal que a probabilidade de seja proporcional a, . l [ 0 , N ] l | F ( l ) | F ( l ) = N k = 0 f ( k ) e - 2 π i k l / Nf(k)=akmodbl[0,N]l|F(l)|F(l)=k=0Nf(k)e2πikl/N
Wandering Logic
11
Ambos os seus exemplos são distribuições uniformes discretas. Eu imagino que as complexidades diferentes estariam em como é difícil contarOnde é o suporte. χ|χ|χ
Nicholas Mancuso
11
@NicholasMancuso Concordo que a contagem + a opção não formada sempre pode ser usada. Então, em certo sentido, isso dá um limite superior. Isso é tudo o que pode ser dito? Onde na literatura isso foi investigado?
Martin Berger
11
@NicholasMancuso Os exemplos que dou são distribuições uniformes. Mas pode-se fazer a mesma pergunta sobre distribuições não uniformes. Também se pode perguntar sobre distribuições em . No que diz respeito às distribuições discretas: prima facie, a contagem não parece ser suficiente em geral, você também precisa gerar o ésimo elemento, depois de escolher uniformemente . Dito isto, pode ser que a contagem seja o cerne do problema. Rii
Martin Berger
11
@NikosM. Obrigado, mas esse link também não diz nada sobre a complexidade da distribuição subjacente. A referência fala sobre uma transformação na distribuição uniforme. Mas essa transformação pode ser difícil / ou fácil computacionalmente. ϕ
Martin Berger

Respostas:

2

A complexidade das distribuições de probabilidade surge particularmente no estudo de problemas de distribuição como DistNP na teoria de Levin da teoria da complexidade de casos médios .

Uma distribuição é computável em P se sua função de densidade cumulativa puder ser avaliada em tempo polinomial.

Uma distribuição é P-samplable se pudermos amostrá- las em tempo polinomial.

Se uma distribuição é P-computável, então é P-sampable. O inverso não é verdadeiro se existirem certas funções de mão única.

Você pode estender as definições para outras classes de complexidade.

Oded Goldreich tem boas notas introdutórias sobre o tópico que você pode querer verificar.

Kaveh
fonte
Obrigado, acho que uma teoria das distribuições de amostra é algo como o que eu estava procurando. Mas não há razão para restringir a atenção para P , você pode definir C distribuições -samplable para qualquer classe de complexidade C . Com o recente aumento de linguagens de programação probabilísticas que está se tornando vital. PPCC
Martin Berger
@ Martin, sim. Houve um tutorial sobre Programação Probabilística ( slides , o vídeo também será postado) no NIPS 2015. Ouvi pessoas que compareceram acharam muito interessante. É bom ver pessoas trabalhando no cruzamento da ML / Stats e PL. :)
Kaveh
Sim, e o principal problema é que essas linguagens (= sampler genéricos e programáveis) são lentas. Como podemos acelerá-los?
Martin Berger