Komplexität der Anpassung von Modellen an Daten

Angenommen, ist eine stetige Funktion $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$

$x_1 \ldots x_n$ ist eine Menge realer Werte, die wir berechnen möchten

$\text{argmin}_a \sum_i f(a,x_i)$ mit vorgeschriebener Genauigkeit

Gibt es einige Ergebnisse zur Schwierigkeit dieses Problems für verschiedene f?

Angenommen, . Das Minimum unseres Problems ist jetzt der Mittelwert von x, einfach zu berechnen. Nehmen wir andererseits an, , es gibt keine geschlossene Lösung, also scheint es schwieriger zu sein, Argmin zu berechnen ... oder? $f(m,x)=(m-x)^2$ $f(m,x)=\log (1+\exp(-m x))$

Motivation: Dieses Minimierungsproblem tritt auf, wenn Modelle an Daten angepasst werden. Das erste Beispiel für f ist die Anpassung der kleinsten Quadrate und das zweite f ist die logistische Regression.

Bearbeiten : Ich habe gerade eine verwandte Frage gesehen , und es ist im Geiste dessen, was ich gefragt habe, für eine bestimmte Wahl von f

approximation-algorithms machine-learning st.statistics Jaroslaw Bulatow
quelle

Antworten:

Wenn konvex ist, können Sie mithilfe von Suchmethoden (in einer begrenzten Domäne) einen Punkt finden, der dem lokalen Minimum, das auch das globale Minimum ist, so nahe kommt, wie Sie möchten, auch wenn es keine geschlossene Form hat - Dies funktioniert, um das Minimum der Summe zu finden, da die Summe der konvexen Funktionen ebenfalls konvex ist. $f$

Es gibt viele andere bessere numerische Methoden mit unterschiedlichen Garantien (abhängig von den Eigenschaften der Funktion) zur Optimierung konvexer Funktionen - dieses Buch ist eine gute (und kostenlose!) Referenz.

Lev Reyzin
quelle

Ein zusätzlicher Hinweis: Quadratverlust, logistischer Verlust und Bregman-Divergenzen (in ihrem ersten Argument) sind konvex.

Lev Reyzin

Ich dachte, jede konvexe Optimierung sei einfach, bis ich kürzlich auf einige konvexe Ziele stieß, bei denen alle numerischen Optimierer, die ich ausprobierte (einschließlich Newtons Methode mit genauem Hessischen). Das Problem war, dass das Ziel zu flach war. Die Lösung bestand darin, algebraische Methoden zu verwenden ( tinyurl.com/2dz8wky ). Dies legt nahe, dass einige praktische konvexe Optimierungsprobleme schwierig sind

Yaroslav Bulatov

Ich denke, es hängt von der Bedeutung von schwer / leicht ab. Wenn Sie eine Box-Einschränkung für die Domain haben, können Sie immer nur eine binäre Suche durchführen.

Lev Reyzin

OK, das stimmt. Der Grund für diese Frage war, dass es für mich überraschend ist, dass Sie Modelle nehmen können, für die die Anpassung nachweislich schwierig ist, das Maß der Anpassung geringfügig ändern und ein Modell erhalten können, bei dem die Anpassung einfach ist. (dh maximale Wahrscheinlichkeit vs. Pseudolikelihood für dichte grafische Modelle, beide sind konsistente Schätzer, aber nur einer ist nachvollziehbar)

Yaroslav Bulatov

Sie sind sich dessen vielleicht bereits bewusst, aber wenn f eine Bregman-Divergenz ist , hat dieses Argument immer eine einfache Lösung. Die spezifische Form hängt von der Reihenfolge der Parameter ab, aber ob der Ausdruck minimiert wird

\arg min_{a} \sum_{i} f (x_{i}, a)

$\arg\min_a \sum_i f(x_i, a)$

Wenn eine Bregman-Divergenz ist, ist die Antwort immer der Mittelwert von . Wenn die Reihenfolge der Parameter umgekehrt ist, können Sie die Dualität der Bregman-Divergenzen verwenden. Insbesondere wenn durch eine streng konvexe Funktion , ist die Lösung das Mittel das durch . $f$ $x_i$ $f$ $\phi$ $\phi$ $c$

\nabla ϕ (c) = (1 / n) \sum_{i} \nabla ϕ (x_{i})

$\nabla \phi(c) = (1/n)\sum_i \nabla \phi(x_i)$

Ein weiterer interessanter Fall ist, wenn die euklidische Norm ist (nicht im Quadrat). In diesem Fall ist das Argument der bekannte Fermat-Weber-Punkt und wurde in der Operationsforschung eingehend untersucht. Es gibt ein global optimales iteratives Schema, um es zu lösen, aber keinen Ausdruck in geschlossener Form. $f$

Suresh Venkat
quelle

Interessant, wusste das nicht ... haben Sie eine Referenz für die Phi-Mean-Formel? Ich frage mich, ob dies eine schnellere Möglichkeit bietet, logistische Regressionsmodelle anzupassen

Jaroslaw Bulatow

Die Ableitung ist sehr einfach (Grundrechnung, kombiniert mit dem Fenchel-Dual), aber eine Referenz ist das JMLR-Papier von Banerjee et al.: jmlr.csail.mit.edu/papers/v6/banerjee05b.html

Suresh Venkat