Was bedeutet eine "nachvollziehbare" Verteilung?

13

Zum Beispiel hören wir in einem generativen kontradiktorischen Netzwerk oft, dass Inferenz einfach ist, weil die bedingte Verteilung von x bei gegebener latenter Variable z 'traktierbar' ist. Außerdem habe ich irgendwo gelesen, dass eine Boltzmann-Maschine und ein Variations-Autoencoder verwendet werden, bei denen die posteriore Verteilung nicht nachvollziehbar ist, so dass eine Art Annäherung angewendet werden muss. Kann mir jemand sagen, was "nachvollziehbar" in einer strengen Definition bedeutet? Oder könnte jemand in einem der Beispiele, die ich oben gegeben habe, erklären, was Tractable genau in diesem Zusammenhang bedeutet?

sirius27
quelle
Dies ist relevant.
Greenparker
1
Es bedeutet einfach, dass Sie in der Lage sind, die relevanten Berechnungen mit der Verteilung durchzuführen. Was also "traktabel" ist, erweitert sich mit der Zeit!
kjetil b halvorsen

Antworten:

10

Zu meiner besten Erinnerung habe ich in einem statistischen Text noch nie eine formale Definition dafür gefunden, aber ich denke, Sie können eine aus einigen kontextbezogenen Lesungen zusammenfügen. Beginnen Sie mit der Bayes'schen Datenanalyse . 261:

Die Bayes'sche Berechnung dreht sich um zwei Schritte: Berechnung der posterioren Verteilung und Berechnung der posterioren Vorhersageverteilung . Bisher haben wir Beispiele betrachtet, bei denen diese in geschlossener Form analytisch berechnet werden könnten [.]p(θ|y)p(y^|y)

Das Hindernis ist im Allgemeinen die marginale Wahrscheinlichkeit, der Nenner auf der rechten Seite der Bayes-Regel, die ein Integral beinhalten könnte, das nicht analytisch ausgedrückt werden kann. Für mehr denke ich, dass Sie den Wiki-Artikel über geschlossene Ausdrücke finden, der für den Kontext hilfreich ist (Hervorhebung von mir):

In der Mathematik ist ein Ausdruck in geschlossener Form ein mathematischer Ausdruck, der in einer endlichen Anzahl von Operationen ausgewertet werden kann. Es kann Konstanten, Variablen, bestimmte "bekannte" Operationen (z. B. + - × ÷) und Funktionen (z. B. n-te Wurzel, Exponent, Logarithmus, trigonometrische Funktionen und inverse hyperbolische Funktionen) enthalten, normalerweise jedoch keine Begrenzung. Die Menge der Operationen und Funktionen, die in einem Ausdruck in geschlossener Form zugelassen sind, kann je nach Autor und Kontext variieren .

Probleme gelten als nachvollziehbar, wenn sie in Form eines Ausdrucks in geschlossener Form gelöst werden können .

Wenn Sie weiterlesen, sehen Sie eine Tabelle mit Ausdrucksklassen, und "Analytische Ausdrücke" enthalten mehrere, die an den Normalisierungskonstanten exponentieller Familienverteilungen beteiligt sind. ZB die Gammafunktion in der Gammaverteilung und die Bessel-Funktion im von-Mises-Fischer.

Das heißt, wir sind bereit, zumindest diese in unsere Definition von "Traktierbarkeit" aufzunehmen. (Es kann andere Verteilungen geben, die die als "analytische Ausdrücke" klassifizierten Operationsklassen betreffen. Ich gebe zu, dass ich nicht vertraut bin.)

Sean Easter
quelle
1
Dies ist eine großartige Antwort, +1. In der zweiten Hälfte von Whittaker & Watson, einem Kurs der modernen Analyse, finden Sie Hinweise darauf, was "Tractable" vor über einem Jahrhundert bedeuten könnte . Gamma- und Bessel-Funktionen sind lediglich die Spitze des Eisbergs.
whuber
1
@whuber Über Whittaker und Watson: GN Watson hat einen kleinen Platz in der Geschichte der Statistik, da er im Auftrag von Karl Pearson eine Grenze für die Kurtosis ableitet. ET Whittaker hat einen größeren als Elternteil der Glättung von Splines avant la lettre .
Nick Cox
@whuber Vielen Dank! Dieser Beitrag erhielt zum Zeitpunkt Ihres Kommentars mehrere Stimmen, was ich als anekdotischen Beweis für einen "Huber Bump" nehme.
Sean Easter
3

Zusätzlich zu Sean Osters Antwort werde ich versuchen, etwas Licht aus der Perspektive der Rechenkosten zu werfen.

Definieren wir zunächst, welche Probleme zu lösen und zu lösen sind (Referenz: http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf ).

Tractable Problem: Ein Problem, das durch einen Polynom-Zeit-Algorithmus lösbar ist. Die Obergrenze ist polynomisch.

Intractable Problem: Ein Problem, das mit einem Polynom-Time-Algorithmus nicht gelöst werden kann. Die Untergrenze ist exponentiell.

Aus dieser Perspektive ist eine Definition für die verfolgbare Verteilung, dass es Polynomzeit braucht, um die Wahrscheinlichkeit dieser Verteilung an einem bestimmten Punkt zu berechnen.

Wenn eine Verteilung in geschlossener Form vorliegt, kann die Wahrscheinlichkeit dieser Verteilung definitiv in Polynomzeit berechnet werden, was in der akademischen Welt bedeutet, dass die Verteilung nachvollziehbar ist. Intraktierbare Verteilungen dauern gleich oder länger als die Exponentialzeit, was normalerweise bedeutet, dass wir mit vorhandenen Rechenressourcen niemals die Wahrscheinlichkeit an einem bestimmten Punkt mit relativ "kurzer" Zeit berechnen können (zu jeder Zeit, die länger als die Polynomzeit ist ... ).

aysljc
quelle
0

Eine Verteilung wird als nachvollziehbar bezeichnet, wenn eine dadurch induzierte Grenzwahrscheinlichkeit in linearer Zeit berechnet werden kann

Malocho
quelle
1
Zitieren Sie eine Referenz oder Autorität? Dies ist eine faszinierende, aber überraschende Charakterisierung, daher wäre ein Hinweis darauf, woher sie kommt und in welchem ​​Umfang sie anwendbar ist, von Interesse.
whuber
2
Ich fand die Quelle, aus der ich sie habe, aus "Über die Verwendung von Summenproduktnetzwerken für die Klassifizierung mehrerer Etiketten" von Julissa Villanueva Llerena und Denis Deratani Mauá
Malocho,