Zum in

Ich versuche die Komplexität von Funktionen zu verstehen, die über Schwellenwert-Gatter und dies führte mich zu . Insbesondere interessiert mich, was derzeit über das Lernen in , da ich kein Experte auf diesem Gebiet bin. $\mathsf{TC}^0$ $\mathsf{TC}^0$

Was ich bisher entdeckt habe, ist:

Alle können in quasipolynomialer Zeit unter der gleichmäßigen Verteilung über Linial-Mansour-Nisan gelernt werden . $\mathsf{AC}^0$
In ihrem Artikel wird auch darauf hingewiesen, dass die Existenz eines Pseudozufalls-Funktionsgenerators das Lernen verhindert, und dies, zusammen mit einem späteren Ergebnis von Naor-Reingold , das PRFGs zulässt, legt nahe, dass die Grenzen darstellt der Lernfähigkeit (zumindest im PAC-Sinne) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Es gibt eine Arbeit von Jackson / Klivans / Servedio aus dem Jahr 2002 , die ein Fragment von lernen kann (mit höchstens polylogarithmischen Mehrheitstoren). $\mathsf{TC}^0$

Ich habe die übliche Google-Schulung durchgeführt, hoffe aber, dass die kollektive Weisheit von cstheory eine schnellere Antwort hat:

Ist das, was ich beschrieben habe, der Stand der Technik für unser Verständnis der Komplexität des Lernens (in Bezug auf welche Klassen werden effiziente Lernende eingeschlossen)? Und gibt es eine gute Übersicht / Referenz, die den aktuellen Zustand der Landschaft abbildet?

cc.complexity-theory reference-request cr.crypto-security lg.learning boolean-functions Suresh Venkat
quelle

+1 Schöne Frage. Hatte Lance nicht schon vor einiger Zeit einen ähnlichen Blogeintrag?

Kaveh

Meinen

Suresh Venkat

Vielleicht dieses: blog.computationalcomplexity.org/2013/08/…

Suresh Venkat

Es ist plausibel, dass es in NC0 Pseudozufallsgeneratoren gibt . (Insbesondere finde ich es sehr unwahrscheinlich, dass ein Pseudozufallsgenerator bekanntermaßen das Lernen verhindert.)Andererseits verhindert die Existenz der Maps für eine Pseudozufallsfunktionsfamilie das Lernen.

$\:$

$\;\;\;$

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$

F

$F$

Linial-Mansour-Nisan zeigen, dass unter der gleichmäßigen Verteilung in quasipolynomialer Zeit gelernt werden kann . Kharitinov zeigte, dass bei einer Verbesserung des Quasipolynoms zu einem Polynom ein subexponentieller Zeitalgorithmus zur Faktorisierung von Blum-Ganzzahlen erhalten würde.

{AC}^{0}

$\text{AC}^0$

Robin Kothari

Antworten:

Die Hauptsache, die auf Ihrer Liste fehlt, ist die schöne Ausgabe von 2006 von Klivans und Sherstov . Sie zeigen dort, dass das PAC-Lernen von Schaltkreisen mit Schwellenwerten der Tiefe 2 so schwierig ist, wie das annähernd kürzeste Vektorproblem zu lösen.

Scott Aaronson
quelle

Was ist die schnellste bekannte Laufzeit für das Erlernen solcher LTF-Schaltungen? (oder irgendetwas in )

T C^{0}

$TC^0$

gradstudent

Die Tiefe 2 TC0 kann wahrscheinlich nicht in subexponentieller Zeit über die gleichmäßige Verteilung mit einem zufälligen Orakelzugriff gelernt werden. Ich kenne keine Referenz dafür, aber hier ist meine Argumentation: Wir wissen, dass Parität nur schwer lernbar ist, in dem Sinne, dass die Klasse der Paritätsfunktionen an sich lernbar ist, aber wenn Sie irgendetwas dagegen tun (z es hört auf, lernbar zu sein. Die Tiefe 2 TC0 ist jedoch stark genug, um alle Paritätsfunktionen darzustellen, und stark genug, um gestörte Versionen von Paritäten darzustellen. Ich bin daher der Meinung, dass die Tiefe 2 TC0 nicht per PAC erlernt werden kann.

Paritäten und verrauschte Paritäten können jedoch in polynomialer Zeit gelernt werden, wenn wir ein Mitgliedschaftsorakel erhalten. Es könnte also interessant sein, zu prüfen, ob die Tiefe 2 TC0 mit einem Mitgliedschaftsorakel erlernt werden kann. Ich wäre nicht total überrascht, wenn die Antwort ja wäre. Andererseits bezweifle ich, dass -Tiefe TC0 mit Mitgliedschaftsabfragen gelernt werden kann. Es könnte gut sein, mit AC0 [6] (oder sogar mit AC0 [2]) zu beginnen und von dort fortzufahren. $O(1)$

Mobius Knödel
quelle