Distributions de probabilités et complexité informatique

Cette question concerne l'intersection de la théorie des probabilités et de la complexité de calcul. Une observation clé est que certaines distributions sont plus faciles à générer que d'autres. Par exemple, le problème

Étant donné un nombre $n$ , renvoyer un nombre uniformément distribué $i$ avec $0 \leq i < n$ .

est facile à résoudre. D'un autre côté, le problème suivant est ou semble être beaucoup plus difficile.

Étant donné un nombre $n$ , renvoyer un nombre $i$ tel que $i$ soit (le nombre de Gödel) une preuve valide de longueur n en arithmétique Peano. De plus, si le nombre de ces preuves est $pr(n)$ , alors la probabilité d'obtenir une preuve spécifique de longueur $n$ doit être $\frac{1}{pr(n)}$ .

Cela me suggère que les distributions de probabilité viennent avec une notion de complexité de calcul. De plus, cette complexité est probablement étroitement liée aux problèmes de décision sous-jacents (qu'ils soient sous-récursifs, par exemple $P$ , $EXP$ , récursifs, récursivement énumérables ou pire).

Ma question est la suivante: comment définir la complexité de calcul des distributions de probabilité, en particulier lorsque le problème de décision sous-jacent n'est pas décidable. Je suis sûr que cela a déjà fait l'objet d'une enquête, mais je ne sais pas où chercher.

complexity-theory reference-request probability-theory probabilistic-algorithms Martin Berger
la source

Un autre exemple intéressant (mais qui est décidable) est la transformée de Fourier quantique. Étant donné renvoyer un nombre tel que la probabilité de est proportionnelle à, .

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

Vos deux exemples sont des distributions uniformes discrètes. J'imagine que les complexités différentes résideraient dans la difficulté de compteroù est le support.

| χ |

$|\chi|$

χ

$\chi$

Nicholas Mancuso

@NicholasMancuso Je suis d'accord que le décompte + le choix de déformation peuvent toujours être utilisés. Donc, dans un certain sens, cela donne une limite supérieure. Est-ce tout ce que l'on peut dire? Où dans la littérature cela a-t-il été étudié?

Martin Berger

@NicholasMancuso Les exemples que je donne sont des distributions uniformes. Mais on peut se poser la même question sur les distributions non uniformes. On peut aussi s'interroger sur les distributions sur . En ce qui concerne les distributions discrètes: à première vue, le comptage ne semble pas être suffisant en général, vous devez également pouvoir générer le ème élément, après avoir uniformément choisi . Cela dit, il se peut que le comptage soit au cœur du problème.

R

$\mathbb{R}$

i

$i$

i

$i$

Martin Berger

@NikosM. Merci, mais ce lien ne dit rien non plus sur la complexité de la distribution sous-jacente. La référence parle d'une transformation sur la distribution uniforme. Mais cette transformation pourrait être difficile / ou facile à calculer.

ϕ

$\phi$

Martin Berger

La complexité des distributions de probabilités apparaît particulièrement dans l'étude de problèmes de distribution comme DistNP dans la théorie de Levin de la théorie de la complexité des cas moyens .

Une distribution est P-calculable si sa fonction de densité cumulée peut être évaluée en temps polynomial.

Une distribution est échantillonnable P si nous pouvons en échantillonner en temps polynomial.

Si une distribution est P-calculable, elle est P-sampable. L'inverse n'est pas vrai si certaines fonctions unidirectionnelles existent.

Vous pouvez étendre les définitions à d'autres classes de complexité.

Oded Goldreich a de belles notes d'introduction sur le sujet que vous voudrez peut-être vérifier.

Kaveh
la source

Merci, je pense qu'une théorie des distributions échantillonnées est quelque chose comme ce que je cherchais. Mais il n'y a aucune raison de limiter l' attention à , vous pouvez définir distributions -samplable pour toutes les classes de complexité . Avec l'essor récent des langages de programmation probabilistes qui devient vital.

P

$P$

P

$P$

C

$C$

C

$C$

Martin Berger

@Martin, oui. Il y avait un tutoriel sur la programmation probabiliste ( diapositives , la vidéo sera également publiée) au NIPS 2015. J'ai entendu que les personnes présentes ont trouvé cela très intéressant. Ravi de voir des gens travailler à l'intersection de ML / Stats et PL. :)

Kaveh

Oui, et le principal problème est que ces langages (= échantillonneurs génériques et programmables) sont lents. Comment pouvons-nous les accélérer?

Martin Berger

Distributions de probabilités et complexité informatique

Réponses: