Allgemeine Lösung für unbeaufsichtigte Lernprobleme: ein auf Metaalgorithmen basierendes Framework

Forscher von Microsoft Research und der Princeton University haben am 13. November einen allgemeinen Rahmen für den Entwurf effizienter Algorithmen für unüberwachte Lernprobleme vorgeschlagen, beispielsweise eine Mischung aus Gaußscher Verteilung und Subraum-Clustering.

Metaalgorithmus zur Lösung des Rauschproblems, der die Berechnungsmethode der Lernberechnungsformel für die untere Grenze verwendet. Dieses Framework basiert auf der jüngsten Arbeit von Garg, Kayal und Saha (FOCS'20), die dieses Framework zum Lernen arithmetischer Formeln ohne Rauschen vorgeschlagen haben. Ein Schlüsselelement des Metaalgorithmus ist ein effizienter Algorithmus zur Lösung eines neuen Problems namens „robuste Vektorraumzerlegung“.

Untersuchungen haben gezeigt, dass der Metaalgorithmus gut funktioniert, wenn eine Matrix ein ausreichend großes Minimum ungleich Null hat Wert gut. „Wir vermuten, dass diese Bedingung für geglättete Instanzen unseres Problems gilt, und daher wird unser Framework effiziente Algorithmen für diese Probleme in glatten Umgebungen liefern.“ in the Presence of Noise: A General Framework and Applications to Unsupervised Learning, veröffentlicht am 13. November auf der arXiv-Preprint-Plattform .

Hier betrachten Forscher Daten, die eine gute mathematische Struktur haben oder aus einer mathematisch wohldefinierten Verteilung generiert werden. Ein Beispiel für Ersteres ist, dass Datenpunkte auf der Grundlage bestimmter Ähnlichkeitsmuster in sinnvolle Cluster gruppiert werden können und das Ziel darin besteht, die zugrunde liegenden Cluster zu finden. Ein Beispiel für Letzteres ist die Mischungsmodellierung, bei der davon ausgegangen wird, dass Daten durch eine Mischung prägnant beschriebener Wahrscheinlichkeitsverteilungen (z. B. Gauß-Verteilungen) generiert werden und das Ziel darin besteht, die Parameter dieser Verteilungen aus Stichproben zu lernen.

Ein gängiger Rahmen zur Lösung vieler Probleme des unbeaufsichtigten Lernens ist die Momentenmethode, die die statistischen Momente der Daten nutzt, um auf die zugrunde liegende Struktur oder die zugrunde liegenden Parameter des Modells zu schließen. Bei vielen Problemszenarien des unbeaufsichtigten Lernens, bei denen die zugrunde liegenden Daten eine schöne mathematische Struktur haben, sind die Momente der Daten genau definierte Funktionen der Parameter. Heuristische Argumente zeigen, dass im Allgemeinen das Gegenteil gelten sollte, d. h. die Parameter einer Struktur/Verteilung werden normalerweise eindeutig durch einige Momente niedriger Ordnung der Daten bestimmt. In dieser allgemeinen Richtung besteht die größte Herausforderung darin, Algorithmen zu entwerfen, um die zugrunde liegenden Parameter (annähernd) aus (empirischen) Momenten wiederherzustellen.

Wir möchten außerdem, dass der Algorithmus effizient, rauschtolerant (d. h. er funktioniert auch dann gut, wenn die Momente nur ungefähr und nicht genau bekannt sind) und sogar anomalietolerant (d. h. selbst dann, wenn einige Datenpunkte dies nicht wissen). passt auch gut zur zugrunde liegenden Struktur/Verteilung. Aber selbst die einfachsten Probleme auf diesem Gebiet neigen dazu, NP-schwer zu sein, und bleiben es auch dann, wenn kein Rauschen und Ausreißer vorhanden sind.

Man kann also eigentlich keinen Algorithmus mit nachweisbaren Worst-Case-Garantien erwarten. Man kann jedoch hoffen, dass der Algorithmus im Allgemeinen garantiert gut funktioniert, d. h. für zufällige Probleminstanzen oder idealer für reibungslos ausgewählte Instanzen. Daher wurden für jedes dieser Probleme beim unbeaufsichtigten Lernen viele verschiedene Algorithmen mit unterschiedlichem Wirkungsgrad, Rauschtoleranz, Ausreißertoleranz und nachweisbaren Garantien entwickelt.

In dieser Arbeit präsentieren die Forscher einen Meta-Algorithmus, der auf viele solcher unbeaufsichtigten Lernprobleme anwendbar ist. Der Ausgangspunkt dieser Studie ist die Beobachtung, dass viele dieser Probleme auf die Aufgabe hinauslaufen, geeignete Unterklassen arithmetischer Formeln zu lernen.

Das obige ist der detaillierte Inhalt vonAllgemeine Lösung für unbeaufsichtigte Lernprobleme: ein auf Metaalgorithmen basierendes Framework. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!