Distribuições de Probabilidades e Complexidade Computacional

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 . $0 \leq i < 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 . $n$ $i$ $i$ $pr(n)$ $n$ $\frac{1}{pr(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). $P$ $EXP$

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.

complexity-theory reference-request probability-theory probabilistic-algorithms Martin Berger
fonte

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, .

f (k) = a^{k} \mod b

$f(k)=a^k \mod b$

l \in [0, N]

$l \in [0,N]$

l

$l$

| F (l) |

$\left|F(l)\right|$

F (l) = \sum_{k = 0}^{N} f (k) e^{- 2 π i k l / N}

$F(l) = \sum_{k=0}^N f(k) e^{-2\pi ikl/N}$

Wandering Logic

Ambos os seus exemplos são distribuições uniformes discretas. Eu imagino que as complexidades diferentes estariam em como é difícil contarOnde é o suporte.

| χ |

$|\chi|$

χ

$\chi$

Nicholas Mancuso

@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

@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.

R

$\mathbb{R}$

i

$i$

i

$i$

Martin Berger

@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.

ϕ

$\phi$

Martin Berger

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

, você pode definir

distribuições -samplable para qualquer classe de complexidade

. Com o recente aumento de linguagens de programação probabilísticas que está se tornando vital.

P

$P$

P

$P$

C

$C$

C

$C$

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

Distribuições de Probabilidades e Complexidade Computacional

Respostas: