Funktionen, die nicht effizient berechenbar, aber lernbar sind

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?

• [1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, " Über die rechnerische Effizienz des Trainings neuronaler Netze ", 2014

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

Lassen $C_n$ sein der Begriff Klasse aller Sprachen $L\subseteq\Sigma^*$ erkennbar Turing - Maschinen auf $n$ Zuständen oder weniger. Im allgemeinen wird für $x\in\Sigma^*$ und $f\in C_n$ , das Problem der Auswertung $f(x)$ ist unentscheidbare.

Nehmen wir jedoch an, wir haben Zugang zu einem (richtigen, realisierbaren) PAC-Lernorakel $A$ für $C_n$ . Das heißt, für jedes $\epsilon,\delta>0$ fordert das Orakel eine markierte Stichprobe der Größe $m_0(n,\epsilon,\delta)$ so dass das Orakel A eine Hypothese ausgibt , wenn eine solche Stichprobe aus einer unbekannten Verteilung $D$ wurde f ∈ C N , die mit einer Wahrscheinlichkeit von mindestens 1 - δ hat D$A$$\hat f\in C_n$$1-\delta$$D$-Allgemeinerungsfehler nicht mehr als $\epsilon$ . 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$ , ob es ein mit S konsistentes $f\in C_n$ . Nehmen wir an (um einen Widerspruch zu bekommen), dass K eine Turing-Maschine ist, die das Konsistenzproblem entscheidet.$S$$K$

Wir machen die folgenden Darstellungskonventionen. Identifizieren $\Sigma^*$ mit $\mathbb{N}=\{0,1,2,\ldots\}$ über die übliche lexikographische Ordnung. Für $x\in\{0,1\}^*$ , sagen wir , dass ein TM $M$ "S-prints" $x$ wenn es alle Saiten in nimmt $\Sigma^*$ zu den Indices $i$ st $x_i=1$ und übernimmt keine (möglicherweise durch nicht Anhalten) einer der Zeichenfolgen, die den Indizes $x_i=0$ . Da (unter der Annahme)$K$ entscheidbar ist, folgt daraus, dass die Funktion$\tilde K:x\mapsto 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\mapsto x$ , das ordnet ein$k\in\mathbb{N}$ an das mindestens (lexikographisch) string$x\in\{0,1\}^*$ derartdass$\tilde K(x)>k$ ist ebenfalls berechenbar.

Nun den TM definieren $M$ wie folgt: $M$ S-prints $g(|\langle M\rangle|)$ , wobei $\langle M\rangle$ 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, $\ell=|\langle M\rangle|$und es druckt eine Zeichenkette, $x_M\in\{0,1\}^*$. Konstruktionsbedingt ist $\tilde K(x_M)>\ell$ , und daher kann $x_M$ von keinem TM mit der Beschreibungslänge $\ell$ oder kürzer S-gedruckt werden . Dabei ist es definiert als die S-Print-Ausgabe eines TM mit der Beschreibungslänge $\ell$ --- ein Widerspruch.