Welche Klassifikatoren für maschinelles Lernen sind am parallelsten?

10

Welche Klassifikatoren für maschinelles Lernen sind am parallelsten? Wenn Sie ein schwieriges Klassifizierungsproblem hätten, eine begrenzte Zeit, aber ein anständiges LAN an Computern, mit denen Sie arbeiten könnten, welche Klassifizierer würden Sie versuchen?

Auf den ersten Blick sieht es für mich wie einige Standardklassifikatoren aus, von denen ich weiß, dass sie sich wie folgt stapeln, aber ich könnte völlig falsch liegen:

Zufällige Wälder - Sehr parallelisierbar, solange jede Maschine alle Daten enthalten kann (dh die Trainingsdaten nicht per se aufteilen können, aber ansonsten parallelisierbar).

Erhöhen - ?

Support Vector Machine - Nicht sehr parallelisierbar.

Entscheidungsbäume - Kann teilweise aufgeteilt werden, aber nicht sehr effizient.

John Robertson
quelle
Dieser Beitrag benötigt ein Update. Derzeit sind DNNs die Algorithmen, die am meisten von der parallelen Berechnung profitieren. und Boosten sind kaum parallelisierbar.
TNM

Antworten:

11

Es wurden Anstrengungen unternommen, um die meisten bekannten Klassifikatoren zu parallelisieren, einschließlich Boosten [ eines Papiers ], SVM [ eines Papiers ] und sogar Entscheidungsbäume [ eines Papiers ]. Wenn Sie Parallelität zugeben, verlieren Sie natürlich manchmal andere Aspekte, sei es die Implementierbarkeit des Algorithmus, die Komplexität der Stichproben oder andere übliche Verdächtige.

Aus theoretischer Sicht ist die Frage schwieriger, denn wenn Sie über das Lernen sprechen, müssen Sie über die Zielfunktion nachdenken. Zum Beispiel wissen wir nicht einmal, dass Entscheidungsbäume PAC-lernbar sind. Wenn also das Ziel (sowie die Methode) ein Entscheidungsbaum ist, können wir ihn (noch) nicht einmal lernen, ohne zusätzliche Facetten in die einzuführen Problem. Boosting umgeht dies, indem es von einer schwachen Lernbedingung, einer SVM-Marge usw. ausgeht. Ich denke, diese Annahmen werden auf den Parallelfall übertragen, um Ihnen PAC-Lernen zu ermöglichen.

Aber wie immer gibt es eine große Lücke zwischen den Grenzen (und damit den Anliegen) von Theorie und Praxis. In der Praxis ist es beispielsweise wichtig, ob die Parallelität über Kernen oder Clustern liegt. Ein Algorithmus, der speziell für den praktischen Einsatz in Umgebungen mit großen Datenmengen entwickelt wurde, ist VW und beginnt, Parallelität zu unterstützen . Vielleicht interessieren Sie sich für die Beiträge im NIPS 2010- Workshop zum praktischen parallelen Lernen.

Lev Reyzin
quelle