[Geschlossen] Optimierungsaufgabe

grauenvolle formatierung...

kann nix versprechen, aber wenn du es nochmal sauber tex'st und hier verlinkst schau ich nochmal drüber (dipl-math. here mit guten optimierungskenntnissen).

ist doch getex't, nur nicht kompiliert

achja? dann kompilier das mal und versuch es zu lesen, ohne vorher nochmal komplett zu überarbeiten.

ok, bin nur grad nicht daheim. ich formatier dir es mal sauber und schick es dir als pdf wenn du magst. mit mehr hintergrund informationen.

danke schon mal

Ok hasu, habs recht sauber getecht, hoffe ich hab es verständlich formuliert. ansonsten meld dich. Vielen Dank
---------------------------------------------
\begin{document}
Seien $n$ Test-Datenpaare $(x_i,y_i)$ verfügbar, wobei die $y_i$ die jeweiligen Label der Punkte $x_i$ markieren. Wir suchen eine Entscheidungsfunktion $f$, die neue Punkte $x$ bestmöglich mit einem der $K$ Labels klassifiziert. Das Problem stammt ursprünglich aus diesem dem Paper http://ttic.uchicago.edu/~tewari/research/tewari07consistency.pdf, wobei auf Seite 1009 die Minimierung des Risikos beschrieben wird, nämlich als
\begin{align}
\textbf{f}_{D} = \underset{\textbf{f} \in \mathcal{F}_n}{\operatorname{argmin}} R_{\Psi,D}(\textbf{f}) = \underset{\textbf{f} \in \mathcal{F}_n}{\operatorname{argmin}} \frac{1}{n} \sum_{i=1}^n \Psi_{y_i} (\textbf{f}(x_i)).
\end{align}
(Im Paper heißt Sie $\hat{f}_n$). In meinem Fall möchte ich für $\Psi$ die Methode von Lee et al. anwenden, welche auf Seite 1019 beschrieben wird. Allerdings wähle ich aus Implementierungsgründen für $\phi$ nicht die Hinge, sondern die Least Square $\phi(t) = (1-t)^2$. Aus der Theorie der SLT (Representer Theorem), wissen wir, dass wir durch geschickte Wahl des Funktionenraums $\mathcal{F}$ (wir nehmen $\mathcal{H}$, dürfte aber keine Rolle zur Berechnung spielen) das gesuchte $f$ darstellen können als
\begin{align}
f = \begin{cases}
\sum_{i=1}^n \alpha_{y_1,i}k(x_i,\cdot)\\
\vdots\\
\sum_{i=1}^n \alpha_{y_K,i}k(x_i,\cdot)
\end{cases}
\end{align}
und die Minimierungsaufgabe umschreiben können zu
\begin{align}
R(f) = \lambda ||f|| + \frac{1}{n} \sum_{i=1}^n \sum_{y'\neq y} (1 + \sum_{j=1}^n \alpha_{y',j} k(x_j,x_i))^2,
\label{eq:3}
\end{align}
wobei $\lambda > 0, \left\|f\right\| := ||f||_{H}^2$, und $k$ steht für einen frei wählbaren Kern. Wir könnten einen linearen Kern $k(x,y) = <x,y>$ annehmen, aber in der Lösung sollte sowieso ein allgemein gehaltenes $k$ stehen. Der vordere Teil des Terms ist als Regulierung zu verstehen. WICHTIG: Es gilt aufgrund der Methode von Lee die Nebenbedingung, dass die Summe der Koordinaten von $f(x) = 0$ ergibt für alle $x$, also
\begin{align}
\sum_{l=1}^K \sum_{i=1}^n \alpha_{y_l,i}k(x_i,x) = 0 \quad \forall x \in X.
\end{align}
Nun müsste man eigentlich in der Lage sein, die Koeffizienten $\alpha$ in \eqref{eq:3} zu berechnen, die diesen Term minimieren. Viel Erfolg.
\end{document}

Verstehe einiges vom Formalismus her nicht. (das Anwendungsgebiet ist mir leider völlig fremd).

- Warum gibt es n Datenpaare, aber K Labels?
- Gl. (2) .. soll f abschnittsweise definiert sein, oder was sind das für \cases ?
Achso, oder soll das Vektorschreibweise sein?

Insofern leider kleines Verständnisproblem, aber dennoch ein paar Hinweise:

Deine Zielfunktion ist quadratisch und konvex, ist offensichtlich nach unten beschränkt. Damit hast du auf jeden Fall eine Lösung, sofern du mind. 1 zulässigen Vektor findest.
Bin mir nicht sicher wie man mit den (unendl.) Nebenbedingungen umgeht, aber da die linear sind hast du eigentlich ein herkömmliches quadr. Optimierungsproblem. [ http://en.wikipedia.org/wiki/Quadratic_programming ]
Die Lösung bestimmst du allgemein über Lagrange-Multiplikatoren da du keine Ungleichungsrestriktionen hast.

Um dir noch genauer weiterzuhelfen verstehe ich wie gesagt die Problemstellung leider nicht gut genug, aber bis auf diese "Orthogonalitäts"-NB ist das denke ich ein Standardproblem.

sidenotes/brag: die besten (S)QP algorithmen kommen übrigens vom Schittkowski aus Bayreuth, bei dem hab ich Informatik gehört
Kann man mit der richtigen Toolbox sicher numerisch lösen.

Viel Erfolg.

- es gibt n testdatenpunkte, d.h. punkte an denen das jeweilige label bekannt ist. z.b. wenn es 2 label gibt, sind die punkte entweder blau oder rot. ein neuer punkt soll nun, je nach lage und von den n bekannten testpunkten abhängig, das label erhalten, welches das programm als wahrscheinlichstes errechnet. mithilfe dieser testpunkte soll die gesuchte entscheidungsfunktion f unbekannten punkten eines der K labels zuweisen.

- ja richtig, vektorenschreibweise. sry, eine große klammer häts wohl besser getan.

standartproblem ... nicht schlecht. kenn mich bei so optimierungsgeschichten halt null aus, außer numerik 1 nix gehört dazu. dann les ich mich mal in die geschichte ein. wenn du mehr weißt, immer her damit!

thnx

was ist eigentlich die Motivation der Aufgabe? Weißt du, dass sie lösbar ist, in dem Sinne dass man mit herkömmlichen Methoden eine Lösung ausrechnen kann?
Nur zu wissen dass es eine gibt (recht einfach bei beschränkten konvexen Problemen, s.o.) hilft einem da ja u.U. nicht viel.

Ansonsten evtl. nochmal genauer erklären, was bei dir ein "Kern" ist, der Begriff ist für mich hier nicht eindeutig.

zur motivation: die zielfunktion, die es zu minimieren gilt, heißt empirisches risiko. da die verteilung P(x,y), mit der die labels verteilt sind, unbekannt ist, können wir das tatsächliche risiko nicht ausrechnen. stattdessen wählen wir das empirische risiko, bei dem unsere testpunkte mit den bekannten labels miteinfließen. ich habe in einem theorieteil gezeigt, dass die methode von lee mit der least square verlustfunktion konsistent ist, d.h. dass für n (anzahl der testpunkte) -> \infty das empirische risiko gegen das eigentliche risiko konvergiert.

in einem weiteren theorieteil konnte für binäre klassifikationsverfahren (nur 2 labels) gezeigt werden, dass die gesuchte entschiedungsfunktion f, dargestellt werden kann als \sum_i \alpha_i k(x_i,.), wobei k ein kern ist. d.h. die k(x_i,.) bilden eine basis des Funktionenraums H, aus dem das gesuchte f stammt. k kann völlig verschieden aussehen, meist wählt man jedoch den gauß-kern k(x,x') = exp(-\sigma^2 ||x-x'||). diese herangehensweise garantiert für den binären fall die lösbarkeit, und ich bin der mir fast sicher, dass sich dies auf den K-dimensionalen fall so übertragen lässt.

also habe ich diese darstellung von f ins K-dimensionale übernommen, und das führt letztendlich zu meiner oben genannten formulierung des problems. lösbar ist das problem sicher, das hast du ja auch direkt erkannt, mehr weiß ich leider auch nicht. es gibt zu dieser problematik auch meines wissens bisher keine literatur.
ich wurde jedoch vom prof extra darauf hingewiesen, die squared loss als verlustfunktion zu wählen, weil dann die lösung auf das invertieren einer matrix hinauslaufen würde.

Hm, irgendwas passt da nicht.

Funktionenräume sind doch i.A. unendlichdim., haben also keine endliche Basis. Wie können dann die k(x_i,.) mit i=1,...,n eine Basis bilden?
Ist dein Fkt.raum hier immer endlichdim.?

Die Lösungsmethodik ist an sich relativ einfach:
http://en.wikipedia.org/wiki/Lagrange_multipliers

Du hängst die Nebenbedingung mit Lagrange-Multiplikator \mu ans Zielfunktional an (Lagrange-Funktion), und bildest den Gradienten nach \alpha und \mu. Der muss verschwinden.

Part. Ableitung nach \mu liefert dir wieder die NB in ihrer Ursprungsform. D.h. was bleibt ist R(\alpha) + \mu*g(\alpha) nach \alpha (komponentenweise) abzuleiten und = 0 setzen.

Damit bekommst du lineare Gln. in \alpha die dir zusammen mit der NB die notwendigen Bedingungen liefern. (Da Zielfkt. quadratisch auch hinreichend)

Wenn ich mich nicht mit der NB (\forall x...) etwas schwertun würde könnt mans quasi einfach runterschreiben.

dieser fktraum ist endlichdimensional. das hängt damit zusammen, dass man nicht alle funktionen zulassen will, da es funktionen gibt, welche die n testpunkte richtig klassifizieren, aber ansonsten schlechte vorhersagen treffen (overfitting). mit anwachsendem n sind dann auch komplexere f möglich.

die nebenbedingung stimmt, nachzulesen in >jmlr.csail.mit.edu/papers/volume8/tewari07a/tewari07a.pdf< auf seite 1019, das \mathcal{C} wird in (5) auf seite 1010 definiert und ist eindeutig \forall x.

in meinen ansätzen hab ich immer \sum i=1 ^{K-1} f_i = -f_K verwendet, aber war nicht zielführend.