Schnelle Methode zum Finden der besten Metaparameter von SVM (das ist schneller als die Rastersuche)

17

Ich verwende SVM-Modelle zur kurzfristigen Vorhersage von Luftschadstoffen. Um ein neues Modell zu trainieren, muss ich geeignete Metaparameter für ein SVM-Modell finden (ich meine C, Gamma usw.).

In der Libsvm-Dokumentation (und in vielen anderen Büchern, die ich gelesen habe) wird vorgeschlagen, diese Parameter mithilfe der Rastersuche zu finden. Daher trainiere ich grundsätzlich das Modell für jede Kombination dieser Parameter aus einem bestimmten Satz und wähle das beste Modell aus.

Gibt es eine bessere Möglichkeit, optimale (oder nahezu optimale) Metaparameter zu finden? Für mich ist es hauptsächlich eine Frage der Rechenzeit - eine Rastersuche für dieses Problem dauert ungefähr zwei Stunden (nachdem ich einige Optimierungen vorgenommen habe).

Vorteile der Rastersuche:

  • Es kann leicht parallelisiert werden - wenn Sie 20 CPUs haben, läuft es 20-mal schneller, andere Methoden zu parallelisieren ist schwieriger
  • Sie überprüfen große Teile des Metaparameterraums. Wenn es also eine gute Lösung gibt, werden Sie sie finden.
jb.
quelle

Antworten:

10

Der Nachteil der Rastersuche besteht darin, dass die Laufzeit so schnell wächst wie das Produkt aus der Anzahl der Optionen für jeden Parameter.

Hier ist ein Eintrag in Alex Smolas Blog zu Ihrer Frage

Hier ist ein Zitat:

Wählen Sie beispielsweise 1000 Paare (x, x ') zufällig aus Ihrem Datensatz aus, berechnen Sie den Abstand aller dieser Paare und nehmen Sie den Median, das 0,1- und das 0,9-Quantil. Wählen Sie nun λ, um die Umkehrung einer dieser drei Zahlen zu sein. Mit ein wenig Kreuzvalidierung werden Sie herausfinden, welches der drei am besten ist. In den meisten Fällen müssen Sie nicht weiter suchen.

Ich habe es selbst nicht ausprobiert, aber es scheint vielversprechend.

carlosdc
quelle
Wie hängt das mit der Frage zusammen? Es geht darum, die besten Parameter für ein SVM-Modell zu finden (auf schnelle Weise).
Roronoa Zoro
2
@Roronoa Zoro: und so ist die Antwort. Es wird erklärt, wie die Parameter für auf Radialbasisfunktionen basierende SVMs (C und \ lambda in Smolas Blogpost) in 3 | Cs | gefunden werden Zeit im Gegensatz zu | \ gammas || Cs | wie es bei der Rastersuche gemacht wird.
Carlosdc
Zur Verdeutlichung, um sicherzustellen, dass ich die Heuristik verstehe, ziehen Sie im Grunde genommen nur zufällig 1000 Datenpunkte aus dem Datensatz, um die SVM zu trainieren, und nehmen dann die Inverse der .1, .9-Quantile und des Medians und diese sind wahrscheinlich gut Kandidaten für ein geeignetes Gamma?
Thomas
6

Wenn Sie davon ausgehen, dass dem Parameterraster eine relativ glatte Funktion zugrunde liegt, können Sie bestimmte Dinge tun. Eine einfache Heuristik besteht beispielsweise darin, mit einem sehr groben Gitter von Parametern zu beginnen und dann ein feineres Gitter um die besten Parametereinstellungen aus dem Grobgitter zu verwenden.

Dies funktioniert in der Praxis recht gut, natürlich mit Vorbehalten. Erstens ist der Raum nicht unbedingt glatt, und es könnte lokale Optima geben . Das Grobraster kann diese komplett verfehlen und es kann zu einer suboptimalen Lösung kommen. Beachten Sie auch, dass Sie bei relativ wenigen Samples in Ihrem Hold-Out-Set möglicherweise viele Parametereinstellungen haben, die den gleichen Score liefern (Fehler oder welche Metrik Sie auch verwenden). Dies kann besonders problematisch sein, wenn Sie in mehreren Klassen lernen (z. B. mit dem One-versus-All) Methode) und Sie nur wenige Beispiele aus jeder Klasse in Ihrem Hold-Out-Set haben. Ohne auf unangenehme nichtlineare Optimierungstechniken zurückzugreifen, ist dies jedoch wahrscheinlich ein guter Ausgangspunkt.

Es gibt eine schöne Referenzen eingestellt hier . In der Vergangenheit bin ich davon ausgegangen, dass Sie einen vernünftigen Bereich von Kernel-Hyperparametern durch Inspektion des Kernels abschätzen können (z. B. im Fall des RBF-Kernels, um sicherzustellen, dass das Histogramm der Kernel-Werte eine gute Streuung der Werte ergibt, anstatt auf 0 oder 1 zu verzerren - und Sie können dies auch automatisch ohne zu viel Arbeit tun), was bedeutet, dass Sie den Bereich eingrenzen können, bevor Sie beginnen. Sie können Ihre Suche dann auf andere Parameter wie den Regularisierungs- / Kapazitätsparameter konzentrieren. Dies funktioniert natürlich nur mit vorberechneten Kerneln, obwohl Sie dies anhand einer zufälligen Teilmenge von Punkten abschätzen können, wenn Sie keine vorberechneten Kernel verwenden möchten, und ich denke, dass dieser Ansatz auch in Ordnung wäre.

tdc
quelle
5

Ich benutze simuliertes Tempern für die Suche nach Parametern.

Das Verhalten wird von einigen Parametern bestimmt:

  • k ist Boltzmanns Konstante.
  • T_max ist deine Starttemperatur.
  • T_min ist Ihre Endschwelle.
  • mu_T( μ) ist, wie viel Sie die Temperatur senken ( T->T/μ)
  • i ist die Anzahl der Iterationen bei jeder Temperatur
  • zist eine Schrittgröße - Sie bestimmen, was genau das bedeutet. Ich bewege mich willkürlich hinein old*(1±z).
  1. Nehmen Sie einen Startpunkt (Satz von Parameterwerten).
  2. Holen Sie sich eine Energie dafür (wie gut es zu Ihren Daten passt; ich verwende Chi-Quadrat-Werte).
  3. Schau in eine zufällige Richtung ("mach einen Schritt").
    • Wenn die Energie niedriger ist als Ihr aktueller Punkt, bewegen Sie sich dorthin.
    • Wenn es höher ist, bewegen Sie sich mit einer Wahrscheinlichkeit dorthin p = e^{-(E_{i+1} - E_i)/(kT)}.
  4. Wiederholen Sie diesen Vorgang T->T/μund iverringern Sie dabei gelegentlich alle Iterationen, bis Sie einen Treffer erzielen T_min.

Spielen Sie ein bisschen mit den Parametern herum und Sie sollten in der Lage sein, ein Set zu finden, das gut und schnell funktioniert.

Und die GNU Scientific Library enthält simuliertes Tempern.

Kevin
quelle
4

Wenn jemand hier interessiert ist, sind einige meiner Gedanken zu diesem Thema:

  • Wie von @tdc vorgeschlagen, mache ich eine Grob- / Feinrastersuche. Dies führt zu zwei Problemen:
    • In den meisten Fällen bekomme ich eine Reihe guter Metaparametersätze mit sehr unterschiedlichen Parametern - ich interpretiere es so, dass diese Parameter optimale Lösungen sind, aber um sicherzugehen, sollte ich alle feinen Gitter in der Nähe all dieser guten Parameter überprüfen ( das würde eine Menge Zeit in Anspruch nehmen), daher überprüfe ich im Moment nur die Nachbarschaft der gesetzten Metaparameter für Wetten.
    • In den meisten Fällen erhöht die Feinsuche die SVM-Leistung nicht (dies kann daran liegen, dass ich nur die Nachbarschaft des besten Punkts aus dem Grobraster überprüfe.
  • Ich habe beobachtet, dass die meiste Rechenzeit für Metaparametersätze aufgewendet wird, die keine guten Ergebnisse liefern. Beispiel: Die meisten Metaparametersätze werden in weniger als 15 Sekunden berechnet (und die besten von ihnen haben eine Fehlerrate von 15%). Einige benötigen 15 Minuten ( und die meisten von ihnen weisen Fehlerraten von mehr als 100% auf. Wenn ich also eine Rastersuche durchführe, töte ich Punkte, deren Berechnung länger als 30 Sekunden dauert, und gehe davon aus, dass sie einen unendlichen Fehler haben.
  • Ich benutze Multiprocessing (was einfach genug ist)
jb.
quelle
1

Wenn der Kernel radial ist, können Sie diese Heuristik verwenden , um einen richtigen Kernel zu erhaltenσ - C-Optimierung ist dann viel einfacher.


quelle
Der Link ist tot. Was war die Heuristik, auf die Sie sich bezogen?
Aalawlx