Pac Learning vs. Lernen auf einheitliche Verteilung

Question

Die Klasse der Funktion $ \ Mathcal {f} $ ist pac-lernbar, wenn ein Algorithmus vorhanden ist $ A $ so, dass für beliebige -Treiber $ d $ , jede unbekannte Funktion $ F $ und jeder $ \ Epsilon, \ DELTA $ Es gilt, dass es gibt $ M $ das auf einer Eingabe von $ m $ iID-Proben $ (x, f (x)) $ wo < Span-Klasse="Math-Container"> $ x \ SIM D $ , $ A $ Retouren, mit Wahrscheinlichkeit größer als $ 1- \ DELTA $ , eine Funktion, die $ \ Epsilon $ -close auf $ F ist $ (in Bezug auf $ D $ ). Die Klasse $ \ Mathcal {f} $ ist effizient lernbar, wenn er lernbar ist, und $ A $ Läuft in der Zeit $ \ Text {Poly} (1 / \ Epsilon, 1 / \ Delta, n) $ (wobei $ | x |= n $ ) und die Beschreibung von $ F $ .

Gibt es einen Fall, in dem eine Klasse $ \ Mathcal {f} $ nicht effizient lernbar ist, aber es ist auf der einheitlichen Verteilung effizient erlerstbar?

Answer 1

Gibt es einen Fall, in dem eine Klasse $ \ Mathcal {f} $ nicht effizient lernbar ist, aber es ist auf der einheitlichen Verteilung effizient erlerstbar?

Dieses wurde gefragt weiter Tcs.se . Es sieht so aus, als wäre die kurze Antwort Ja - Aaron Roth gibt das Beispiel der Breite - $ K $ Konjunktionen für $ k \ gg \ log n $ . In den Kommentaren wird Avrim Blum als Angabe der Antwort von $ 2 $ -term dnf angegeben.

Ich verstehe die Beispiele nicht völlig - es muss etwas mehr Arbeit dauern, um das Ergebnis wirklich abzuleiten (ich werde diese Antwort aktualisieren, wenn ich einen in sich geschlossenen Nachweis finde). Das allgemeine Problem hier mit der einheitlichen Verteilung besteht jedoch darin, dass, wenn die Zielfunktion $ F $ "sparsam" ist, und bedeutet, dass sie auf den meisten Einen $ \ Delta $ Fraktion der Eingabestands mit $ 1 $ , dann ist es leicht zu erlernen, indem Sie einfach nur erraten $ 0 $ .

---

jenseits eines nur effizienten (polynomialen) PAC-Lernens gibt es andere Beispiele, in denen die einheitliche Verteilung zu helfen scheint. Zum Beispiel ist ein klassisches hartes Problem für das PAC-Learning DNF, ein Problem, das vermutet ist, dass er nicht lernbar ist, und ziemlich hart. Andererseits ist DNF über die einheitliche Verteilung fast lernbar: Wir haben einen qausi Polynomzeitalgorithmus dafür. Siehe diese Notizen und diese Notizen .

In Zusammenfassung scheint der Lernen unter der einheitlichen Verteilung viel Arbeit zu lernen (Suchen "PAC lernen unter einheitlicher Verteilung" für zusätzliche Referenzen). Und es scheint, dass dieses Problem einfacher ist als das Studium von PAC-Lernen, wo wir nicht viel beweisen können. Zitat Ryan O'Donnells Notizen oben:

Allgemeines PAC-Learning besteht darauf, dass ein Algorithmus für alle Distributionen gleichzeitig arbeitet. Tatsächlich findet die Machine-Lerngemeinschaft, die an realen Anwendungen interessiert ist, die einheitliche Einstellung fragwürdig: "Sie schlagen Sie in der Nase, wenn Sie versuchen, ihnen von Algorithmen in diesem zu erzählen Rahmen. "- Ratean. Aber in einem allgemeineren Rahmen kann niemand wirklich beweisen.