Differenzierbarkeit < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:33 Mi 20.06.2012 | | Autor: | wieschoo |
Kurzfassung:
Warum ist [mm] $f_1(w,b):=\frac{1}{2} \lVert [/mm] w [mm] \rVert^2 [/mm] + [mm] \sum_{i=1}^k \max\{0,1-y_i(w^Tx_i+b)\}^2 \qquad (\star)$ [/mm] diffbar in [mm] $w,b\;$?
[/mm]
Ich beschäftige mich mit diesen SupportVektorMaschinen. Eigentlich handelt es sich dabei nur um das Bestimmen des Minimums von
[mm] $$\min_{w,b} f_i(w,b):=\frac{1}{2} \lVert [/mm] w [mm] \rVert^2 [/mm] + [mm] \sum_{i=1}^k L_i(w,b,x_i,y_i)$$
[/mm]
um eine Gerade [mm]\{x\in\IR^2 : w^Tx+b=0\}[/mm] zu ermitteln.
Hierbei ist [mm]k\in\IN[/mm] und die [mm]x_i\in \IR^2,y_i\in \{-1,1\}[/mm] für i=1,...,n und [mm]w\in\IR^2,b\in \IR[/mm]. Die [mm]x_i[/mm] sind also Punkte im [mm]\IR^2[/mm] und der Punkt [mm]x_i[/mm] gehört zu Klasse [mm]y_i[/mm] (also zu +1 oder -1). Ziel ist das Bestimmen einer dicken Geraden (fat separator), die die Punkte trennt, sofern es geht.
In dem Paper (auf Seite 1):
http://www.csie.ntu.edu.tw/~cjlin/papers/cdl2.pdf
ist für L die Funktion [mm]L_1(w,b,x_i,y_i):= \max\{0,1-y_i(w^Tx_i+b)\}^2[/mm] (dort Gleichung 3) angegeben. Für die Gleichung (4) dort sehe ich es noch ein, dass sie 2mal diffbar ist. Doch für
[mm] $$f_1(w,b):=\frac{1}{2} \lVert [/mm] w [mm] \rVert^2 [/mm] + [mm] \sum_{i=1}^k \max\{0,1-y_i(w^Tx_i+b)\}^2 \qquad (\star)$$
[/mm]
steht, da dass sie einmal diff'bar ist.
"In contrast, L2-SVM (3) is a piecewise quadratic and strongly
convex function, which is diff erentiable but not twice di erentiable"
Als Quelle für die Aussage wird
http://ftp2.cs.wisc.edu/pub/dmi/tech-reports/01-11.pdf
angegeben.
Ist [mm](\star)[/mm] wirklich diff'bar? Das sehe ich überhaupt nicht ein, bzw. ist mir nicht klar. Falls es diese Ableitungen doch gibt: Wie sieht sie aus?
[mm] $$\frac{\partial}{\partial w_i} f_i(w,b)=\frac{\partial}{\partial w_i}\frac{1}{2} \lVert [/mm] w [mm] \rVert^2 [/mm] + [mm] \sum_{i=1}^k \frac{\partial}{\partial w_i}L_1(w,b,x_i,y_i)$$
[/mm]
bzw.
[mm] $$\frac{\partial}{\partial b} f_i(w,b)=\frac{\partial}{\partial b}\frac{1}{2} \lVert [/mm] w [mm] \rVert^2 [/mm] + [mm] \sum_{i=1}^k \frac{\partial}{\partial b}L_1(w,b,x_i,y_i)$$
[/mm]
zählt nicht 
Natürlich könnte man einen Gradientenangeben, indem man die [mm]k^2[/mm] Fälle einzeln betrachtet. Nur glaube ich kaum, dass dies dort gemeint ist.
Mit diff'bar meine ich hier partiell diff'bar. Ich benötige nur den Gradienten für das Gradientenverfahren.
Kann mir da jemand weiterhelfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:17 Do 21.06.2012 | | Autor: | rainerS |
Hallo!
> Kurzfassung:
> Warum ist [mm]f_1(w,b):=\frac{1}{2} \lVert w \rVert^2 + \sum_{i=1}^k \max\{0,1-y_i(w^Tx_i+b)\}^2 \qquad (\star)[/mm]
> diffbar in [mm]w,b\;[/mm]?
>
>
>
> Ich beschäftige mich mit diesen SupportVektorMaschinen.
> Eigentlich handelt es sich dabei nur um das Bestimmen des
> Minimums von
>
> [mm]\min_{w,b} f_i(w,b):=\frac{1}{2} \lVert w \rVert^2 + \sum_{i=1}^k L_i(w,b,x_i,y_i)[/mm]
>
> um eine Gerade [mm]\{x\in\IR^2 : w^Tx+b=0\}[/mm] zu ermitteln.
>
> Hierbei ist [mm]k\in\IN[/mm] und die [mm]x_i\in \IR^2,y_i\in \{-1,1\}[/mm]
> für i=1,...,n und [mm]w\in\IR^2,b\in \IR[/mm]. Die [mm]x_i[/mm] sind also
> Punkte im [mm]\IR^2[/mm] und der Punkt [mm]x_i[/mm] gehört zu Klasse [mm]y_i[/mm]
> (also zu +1 oder -1). Ziel ist das Bestimmen einer dicken
> Geraden (fat separator), die die Punkte trennt, sofern es
> geht.
>
> In dem Paper (auf Seite 1):
> ![[]](/images/popup.gif) http://www.csie.ntu.edu.tw/~cjlin/papers/cdl2.pdf
>
> ist für L die Funktion [mm]L_1(w,b,x_i,y_i):= \max\{0,1-y_i(w^Tx_i+b)\}^2[/mm]
> (dort Gleichung 3) angegeben. Für die Gleichung (4) dort
> sehe ich es noch ein, dass sie 2mal diffbar ist. Doch für
>
> [mm]f_1(w,b):=\frac{1}{2} \lVert w \rVert^2 + \sum_{i=1}^k \max\{0,1-y_i(w^Tx_i+b)\}^2 \qquad (\star)[/mm]
>
> steht, da dass sie einmal diff'bar ist.
> "In contrast, L2-SVM (3) is a piecewise quadratic and
> strongly
> convex function, which is diff erentiable but not twice
> di erentiable"
> Als Quelle für die Aussage wird
> http://ftp2.cs.wisc.edu/pub/dmi/tech-reports/01-11.pdf
> angegeben.
>
> Ist [mm](\star)[/mm] wirklich diff'bar? Das sehe ich überhaupt
> nicht ein, bzw. ist mir nicht klar. Falls es diese
> Ableitungen doch gibt: Wie sieht sie aus?
Dass die Funktion stückweise quadratisch ist, siehst du ein?
Die Frage nach der Differenzierbarkeit stellt sich ja nur an den Stellen, an denen diese Stücke zusammengesetzt sind, also an den Punkten, wo für mindestens ein i
[mm] 1-y_i(w^Tx_i+b) = 0 [/mm]
gilt. Denn auf der einen Seite einer solchen Stelle ist [mm] $\max\{0,1-y_i(w^Tx_i+b)\}$ [/mm] identisch 0, auf der anderen Seite eine lineare Funktion, die - und das ist wichtig - an dieser Stelle den Wert 0 hat.
Das heisst aber, dass das Quadrat
[mm] \max\{0,1-y_i(w^Tx_i+b)\}^2[/mm]
wie eine halbe Parabel aussieht, die an ihrem Scheitelpunkt abgeschnitten wurde. Eine Parabel hat an ihrem Scheitelpunkt die Steigung 0, sodass der links- und der rechtseitige Grenzwert des Differenzenquotienten existieren und übereinstimmen. Das ist genau die Definition der partiellen Diff'barkeit, und die Stetigkeit der partiellen Ableitung ist damit auch klar.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:46 Mo 25.06.2012 | | Autor: | wieschoo |
Danke dir!
Deine Begründung leuchtet mir nun ein. Ich sehe zwar noch nicht direkt, wie der Gradient nun aussieht. Aber das es ihn nun doch gibt, lohnt es sich danach zu suchen.
gruß
wieschoo
|
|
|
|
