Gibt es eine Arbeit, die maschinelles Lernen und die exotischeren Formen der Komplexitätstheorie kombiniert?

13

Mir scheint, dass Experten für maschinelles Lernen / Data Mining mit P und NP vertraut sind, aber selten über einige der subtileren Komplexitätsklassen (z. B. NC, BPP oder IP) und deren Auswirkungen auf eine effektive Datenanalyse sprechen. Gibt es eine Arbeitserhebung dazu?

cc.complexity-theory reference-request machine-learning Mike Izbicki
quelle
2
Keine Umfrage, die ich kenne, aber sehen Sie sich diesen Hinweis auf "Quantenlernen" (# 5) in diesem Beitrag an: blog.computationalcomplexity.org/2012/10/quantum-workshop.html
Suresh Venkat
Das maschinelle Lernen greift regelmäßig sehr schwierige Probleme an, die außerhalb von NP für eine "globale" Optimierung wahrscheinlich sind, innerhalb von NP jedoch weniger schwierig als bei einer "lokalen" Optimierung. So wird das gesamte Konzept der Komplexitätsklasse unscharf, wenn man für "gut genug" -Ergebnisse optimiert, die mehr durch anwendungsabhängige Qualitätsmessungen gemessen werden und in gewissem Sinne nicht wirklich bekannt sind, als wenn die Algorithmen ausgeführt werden ...
vzn
@vzn Diese Subtilität scheint mir ein Grund mehr zu sein, auf Komplexität zu achten! Es könnte einige sehr interessante Einblicke geben.
Mike Izbicki
es gibt sicherlich Zusammenhänge zwischen Lerntheorie, Schaltungskomplexität, Kryptographie. Dies ist jedoch die Ecke der Lerntheorie, die ein wenig von der maschinellen Lernpraxis entfernt ist. Wenn Sie interessiert sind, kann ich mit ein paar Tipps kommen
Sasho Nikolov
Ja, ein anderes Beispiel: BDDs (binäre Entscheidungsdiagramme) wurden in Datenbankalgorithmen / Data Mining verwendet und haben starke Verbindungen zur Schaltungskomplexität. Mir scheint jedoch, dass die ganze Frage eine knifflige Voraussetzung sein kann, da viel maschinelles Lernen pragmatisch ist und die Komplexität der angewandten ML oft indirekt / empirisch untersucht wird, indem reale Implementierungen von Algorithmen analysiert werden, anstatt zu versuchen, sie theoretisch vorherzusehen oder streng zu klassifizieren.
vzn

Antworten:

3

Zwischen den beiden Bereichen des angewandten maschinellen Lernens und der TCS / Komplexitätstheorie besteht ein gewisser inhärenter Unterschied oder eine gewisse Unähnlichkeit der Ansätze.

Hier ist ein aktueller Workshop zum Thema im Center for Computational Intractability, Princeton, mit vielen Videos.

Beschreibung: Viele aktuelle Ansätze des maschinellen Lernens sind heuristisch: Wir können weder ihre Leistung noch ihre Laufzeit nachweisen. Dieser kleine Workshop konzentriert sich auf das Projekt des Entwurfs von Algorithmen und Ansätzen, deren Leistung genau analysiert werden kann. Ziel ist es, über Einstellungen hinaus zu schauen, in denen bereits nachweisbare Grenzen bestehen.

In der TCS wird ein Hauptstudienbereich des "Lernens", manchmal verwirrenderweise auch "maschinelles Lernen" genannt, PAC-Theorie genannt, die für "wahrscheinlich ungefähr richtig" steht. Seine Anfänge in den frühen 1980er Jahren gehen auf eine viel modernere Erforschung des "maschinellen Lernens" zurück. wikipedia nennt es einen Teil der Theorie des rechnergestützten Lernens . PAC betrifft häufig Ergebnisse des Lernens von Booleschen Formeln bei statistischen Stichproben der Verteilungen usw. und die erreichbare Genauigkeit des Lernens bei verschiedenen Algorithmen oder begrenzten Stichproben. Dies wird in einer rigorosen theoretischen Weise unter Einbeziehung von Komplexitätsklassen untersucht. Aber es ist nicht so sehr eine Seite für angewandte Studien und Wikipedien zum maschinellen Lernen, die es nicht einmal auflistet.

vzn
quelle
5
"wikipedia calls" ... wissen sie eigentlich etwas über das thema? 1) Das Wiki für maschinelles Lernen hat einen Abschnitt Theorie, der auf die Theorie des rechnergestützten Lernens verweist.
Sasho Nikolov