Algorithmen für statistische Abfragemodelle?

13

Ich habe diese Frage in übergreifenden Fragen und Antworten gestellt, aber es scheint, dass sie viel mehr mit CS zu tun hat als mit Statistik.

Können Sie mir Beispiele für Algorithmen des maschinellen Lernens nennen, die aus den statistischen Eigenschaften des Datensatzes und nicht aus den einzelnen Beobachtungen selbst lernen, dh das statistische Abfragemodell verwenden ?

Deyaa
quelle
1
Was ist das statistische Abfragemodell?
Suresh Venkat
aus Kearns paper portal.acm.org/citation.cfm?doid=293347.293351 : "In diesem Modell ist es einem Lernalgorithmus untersagt, einzelne Beispiele der unbekannten Zielfunktion zu untersuchen, es wird jedoch auf ein Orakel zugegriffen, das Schätzungen der Wahrscheinlichkeiten für die Stichprobe liefert Raum der zufälligen Beispiele. " Entschuldigung, wenn es nicht offensichtlich ist, ich habe meine Frage mit dem Link zur Zeitung aktualisiert
Deyaa

Antworten:

14

Fast jeder Algorithmus, der im PAC-Modell funktioniert (mit Ausnahme der Paritätslernalgorithmen), kann im SQ-Modell verwendet werden. Siehe z. B. diese Veröffentlichung von Blum et al. in dem mehrere gängige Algorithmen in ihre SQ-Entsprechungen übersetzt werden ( Practical Privacy: das SuLQ-Framework ). Das Papier befasst sich im Prinzip mit "Privatsphäre", aber Sie können das ignorieren - es implementiert wirklich nur Algorithmen mit SQ-Abfragen.

Agnostisches Lernen ist im SQ-Modell hingegen viel schwieriger: Abgesehen von den (wichtigen) Rechenproblemen entspricht die für agnostisches Lernen erforderliche Beispielkomplexität in etwa der für genaues Lernen erforderlichen, wenn Sie tatsächlich Zugriff auf haben die Datenpunkte. Auf der anderen Seite wird das agnostische Lernen im SQ-Modell sehr viel schwieriger - Sie müssen in der Regel überpolynomiell viele Abfragen durchführen, selbst für Klassen, die so einfach wie monotone Disjunktionen sind. Siehe dieses Paper von Feldman ( Eine vollständige Charakterisierung des Lernens statistischer Abfragen mit Anwendungen zur Evolvabilität ) oder dieses kürzlich erschienene Paper von Gupta et al. ( Konjunktionen privat freigeben und die statistische Abfragesperre )

Aaron Roth
quelle
wirklich nette Antwort Aaron :) vielen Dank :)
Deyaa
7

Das SQ-Modell wurde erstellt, um das lärmtolerante Lernen zu analysieren. Ein Algorithmus, der statistische Abfragen durchführt, funktioniert unter der Klassifizierung Lärm. Wie Aaron sagte, haben die meisten PAC-Algorithmen, die wir haben, Entsprechungen im SQ-Modell. Die einzige Ausnahme ist die Gaußsche Eliminierung, die zum Lernen von Paritäten verwendet wird (man kann sie sogar clever anwenden)log (n) loglog (n) Größenparitäten im Klassifikationsrauschmodell lernen). Wir wissen auch, dass Paritäten nicht mit statistischen Abfragen gelernt werden können, und es stellt sich heraus, dass die interessantesten Klassen wie Entscheidungsbäume Paritätsfunktionen simulieren können. Um PAC-Lernalgorithmen für viele interessante Klassen (wie Entscheidungsbäume, DNF usw.) zu erhalten, benötigen wir grundlegend neue Lernalgorithmen, die im statistischen Abfragemodell nicht funktionieren.

Lev Reyzin
quelle
Interessant. Haben Sie eine Referenz, dass Paritäten im SQ-Modell nicht gelernt werden können?
M. Alaggan
1
Dies wurde von Kearns in seinem Originalartikel über das Definieren des Modells nachgewiesen: portal.acm.org/citation.cfm?doid=293347.293351 und dann von Blum et al. erneut gezeigt, wo sie die SQ-Dimension einer Klasse portal.acm.org/citation definierten .cfm? id = 195058.195147 . Grundsätzlich lautet das Argument: Paritäten sind "paarweise unabhängig" in Bezug auf die Gleichverteilung, so dass Sie die richtige Parität erraten müssen, um etwas zu lernen, und es gibt viele mögliche Paritäten ...
Lev Reyzin
5

Ich möchte Aarons Antwort etwas klarstellen. Nahezu jeder Agnostik-Algorithmus (außer alles, was die Gaußsche Eliminierung verwendet) kann im SQ-Modell verwendet werden. Agnostisches Lernen ist natürlich schwieriger als nicht-agnostisches Lernen, aber dies ist eine eigenständige Frage.

user5591
quelle
/ϵ2