Funktionen, die nicht effizient berechenbar, aber lernbar sind

28

Wir wissen, dass (siehe z. B. Theoreme 1 und 3 von [1]) unter geeigneten Bedingungen Funktionen, die von Turing-Maschinen in polynomieller Zeit effizient berechnet werden können ("effizient berechenbar"), durch polynomielle neuronale Netze ausgedrückt werden können mit vernünftigen Größen und kann somit mit polynomieller Abtastkomplexität ("lernbar") unter beliebigen Eingangsverteilungen gelernt werden.

Hier betrifft "lernbar" nur die Komplexität der Stichprobe, unabhängig von der Komplexität der Berechnung.

Ich wundere mich über ein sehr eng verwandtes Problem: Gibt es eine Funktion, die von Turing-Maschinen in Polynomzeit nicht effizient berechnet werden kann ("nicht effizient berechenbar"), die jedoch in der Zwischenzeit mit der Komplexität von Polynomproben gelernt werden kann ("lernbar")? unter irgendwelchen Eingabeverteilungen?

Minkov
quelle
4
Ich beschäftige mich mit "und kann so gelernt werden". Es gibt sehr effizient berechenbare Funktionen (z. B. DFAs), die sehr schwer zu erlernen sind, auch ungefähr.
Aryeh
3
Hier fehlt wahrscheinlich der Punkt, aber was ist mit der Klasse von (sagen wir) 2 - √?n- voreingenommene Boolesche Funktionen? (Dh mehr oder weniger eine Zufallsfunktion, wobei jeder Wert unabhängig1mit einer Wahrscheinlichkeit von2- √ ist2n1n ). Für jedesε>2-2nn , PAC-Lernen unter der gleichmäßigen Verteilung ist trivial (0 Stichprobe erforderlich, die konstante Funktion0ist eine gute Hypothese), aber es scheint, als müsste jeder Bewertungsalgorithmus superpolynomielle Zeit aufwenden (da es keine Struktur für die Funktion gibt). Ich verstehe die Frage jedoch höchstwahrscheinlich falsch. ε>2n0
Clement C.
3
Ihre Terminologie ist etwas verwirrend. Wenn wir „effizient lernbar“ sagen, beziehen wir uns normalerweise auf Recheneffizienz. Nur „lernfähig“ zu sagen, ist ausreichend, um die Effizienz der Stichprobe zu implizieren.
Lev Reyzin
1
@Minkov Um PAC zu lernen, solltest du in Bezug auf jede Distribution lernen. Ansonsten ist die Frage nicht interessant (wie Clement betont).
Lev Reyzin
2
Warum stimmen die Leute ab, um zu schließen? Ich denke, das ist eine tiefe und subtile Frage!
Aryeh

Antworten:

11

Ich werde eine Variante dieser Frage formalisieren, bei der "Effizienz" durch "Berechenbarkeit" ersetzt wird.

Lassen C nCn sein der Begriff Klasse aller Sprachen L & Sgr; *LΣ erkennbar Turing - Maschinen auf nn Zuständen oder weniger. Im allgemeinen wird für x & Sigma; *xΣ und f C nfCn , das Problem der Auswertung f ( x )f(x) ist unentscheidbare.

Nehmen wir jedoch an, wir haben Zugang zu einem (richtigen, realisierbaren) PAC-Lernorakel AA für C nCn . Das heißt, für jedes ϵ , δ > 0ϵ,δ>0 fordert das Orakel eine markierte Stichprobe der Größe m 0 ( n , ϵ , δ ) an,m0(n,ϵ,δ) so dass das Orakel A eine Hypothese ausgibt , wenn eine solche Stichprobe aus einer unbekannten Verteilung D gezogenD wurde fC N , die mit einer Wahrscheinlichkeit von mindestens 1 - δ hat DAf^Cn1δD-Allgemeinerungsfehler nicht mehr als ϵϵ . Wir werden zeigen, dass dieses Orakel nicht nach Turing berechenbar ist.

Tatsächlich werden wir zeigen, dass ein einfacheres Problem nicht zu entscheiden ist: Bei einer markierten Stichprobe S wird bestimmtS , ob es ein mit S konsistentes f C n gibtfCn . Nehmen wir an (um einen Widerspruch zu bekommen), dass K eine Turing-Maschine ist, die das Konsistenzproblem entscheidet.SK

Wir machen die folgenden Darstellungskonventionen. Identifizieren Σ *Σ mit N = { 0 , 1 , 2 , ... } über die übliche lexikographische Ordnung. Für x { 0 , 1 } * , sagen wir , dass ein TM M "S-prints" x wenn es alle Saiten in nimmt Σ * zu den Indices i st x i = 1 und übernimmt keine (möglicherweise durch nicht Anhalten) einer der Zeichenfolgen, die den Indizes x entsprecheni = 0 . Da (unter der Annahme) K entscheidbar ist, folgt daraus, dass die Funktion ˜ K : x k , die als das kleinste k definiert ist,so dass ein Teil von TM in C k S x druckt, Turing-berechenbar ist. Daraus folgt weiterdaß die Funktion g : k x , das ordnet ein k N an das mindestens (lexikographisch) string x { 0 , 1 } * derartdass ~ K ( x) > k ist ebenfalls berechenbar.

Nun den TM definieren M wie folgt: M S-prints g ( |M | ) , wobei M ist die Kodierung von M , | x | bezeichnet die Länge einer Zeichenkette, und der Rekursionssatz wird aufgerufen, um die Existenz eines solchen M zu behaupten . Dann hat M eine Kodierungslänge, = | M | und es druckt eine Zeichenkette, x M{ 0 , 1 } . Konstruktionsbedingt ist ˜ K ( x M ) > , und daher kann x M von keinem TM mit der Beschreibungslänge oder kürzer S-gedruckt werden . Dabei ist es definiert als die S-Print-Ausgabe eines TM mit der Beschreibungslänge --- ein Widerspruch.

Aryeh
quelle
2
Herausforderung: Konvertiere mein "unendliches" Argument über die Berechenbarkeit in ein endliches Argument über die Effizienz. Ich denke, die Antwort auf @ minkovs Frage ist negativ: Sie können eine Funktionsklasse nicht effizient lernen, die Sie nicht effizient auswerten können. Ich denke, dass dies auch dann der Fall sein wird, wenn Sie den richtigen oder realisierbaren PAC überschreiten.
Aryeh