Forum:  Numerik & Optimierung
Thema: SVM: Rekonstruktion der primalen Lösung von der dualen
Themen-Übersicht
mbInfoStudent
Aktiv
Dabei seit: 22.08.2015
Mitteilungen: 54
Aus:
Themenstart: 2020-09-17 18:28

In unserem Skript wird beschrieben, wie man von der dualen Lösung des Optimierungsproblems für SVM auf das primale zurückrechnen kann.
Die primale Darstellung ist:
$$\min_{w,b,z} \frac{1^Tz}{N} + \frac{\lambda}{2} w^T w \\ s.t. \text{ } y_i(w^Tx_i - b) + z_i \geq 1, z_i\geq 0, i \in [N]$$ und somit die Langrangefunktion von der primalen Darstellung:
$$ L(w,b,z,u,v) = \frac{1^Tz}{N} + \frac{\lambda}{2} \|w\|_2^2 - u^Tz + \Sigma_{i=1}^N v_i(1-z_i - y_i(w^Tx_i - b))$$ Die dualle Formulierung ist:
$$ \max_v 1^Tv - \frac{1}{2} v^TKv \\ s.t. \text{ } 0\leq v\leq \frac{1}{N}1^N,\text{ }\text{ }\text{ } y^Tv = 0 \\ \text{wobei } K_{ij} = \frac{1}{\lambda}(y_iy_j)x_i^Tx_j$$
Anhand der KKT-Bedingungen wissen wir, dass gilt $\nabla_{(w,b,z)}L(w,b,z,u,v) =0$ was identisch ist zu:
$$\nabla_w L(w,b,z,u,v) = \lambda w - \Sigma_{i=1}^N v_iy_ix_i = 0 \Rightarrow  w= \frac{1}{\lambda} \Sigma_{i=0}^N v_iy_ix_i $$ $$\nabla_b L(w,b,z,u,v) = \Sigma_{i=1}^N v_iy_i = y^Tv = 0$$ $$ \nabla_z L(w,b,z,u,v) \Rightarrow u+v = \frac{1}{N}1^N$$
Nun sei $v^*$ eine optimale Lösung für das duale Problem. Nun sollen die KKT Bedingungen benutzt werden, um die primale Lösung auszurechnen. Wir haben schon $w^*= \frac{1}{\lambda} \Sigma_{i=0}^N v_i^*y_ix_i$ erhalten.
Nun steht im Skript:
Basierend auf der Komplimentaritätsbedingungen haben wir:
$$u_i^* \geq0,  z_i^* \geq 0, u_i^* >0 \Rightarrow z_i^* = 0$$ $\textbf{Frage 1: Könntet Ihr mir bitte helfen,  wie man hier auf die strikte Ungleichung $u_i^* >0$ kommt. }$
Denn die Komplimentatirätsbedinung besagt ja:
$$u^*\geq 0, v^* \geq 0$$ $$\nabla_{u,v}L(w,b,z,u,v)^T(u,v)^* = 0 \Leftrightarrow \nabla_uLu^* = -z^Tu^* = 0, \nabla_vLv^* = \Sigma_{i=1}^N (1-z_i-y_i(w^Tx_i-b))^Tv^* = 0$$ wenn ich richtig gerechnet habe. Wie folgt daraus $u_i^*>0$?
Zusätzlich entnimmt das Skript aus der Komplimentatirätsbedinungen:
$$v_i^*\geq 0, 1-z_i^* - y_i((w^*)^T x_i - b^*) \leq0, v_i^* >0 \Rightarrow z_i^* = 1-y_i((w^*)^T x_i - b*) \geq 0.$$ Auch hier habe ich ähnliche Frage wie oben
$\textbf{Frage 2: Wieso gilt hier die strikte Ungleichung $v_i^*>0$}$?  Kann es sein, dass hier die Supportvektoren gemeint sind? Denn für diese gilt ja tatsächlich $v_i^* >0$

Meine letzte Frage bezieht sich auf die Berechnung von $z_i^*$. Im Skript stehen folgende Fallunterscheidungen:
$$ i\in \{j\in[N]:v_j^* = 0\} : z_i^* = 0 , 1- y_i((w^*)^Tx_i - b*) \leq0,\\
   i\in \{j\in[N]:v_j^* = \frac{1}{N}\} : z_i^* = 1- y_i((w^*)^Tx_i - b*) \geq 0$$ $\textbf{Frage 3:Meine Frage ist, wie man im ersten Fall auf $z_i^*=0$ kommt?}$ Ich kann das aus keinem der Regeln herleiten. Dabei ist die zweite für mich sinnhaft, dann wenn $v_i^*\neq0$ dann muss $1-z_j^* - y_i((w^*)^Tx_i-b^*)\geq0$ sein.
Ich weiß, dass diese Frage sehr lang geworden ist, aber ich müsste die Vorinformationen da mit reinpacken. Ich wäre für jegliche Hilfe wirklich sehr dankbar


mbInfoStudent
Aktiv
Dabei seit: 22.08.2015
Mitteilungen: 54
Aus:
Beitrag No.1, vom Themenstarter, eingetragen 2020-09-18 17:20

Hat jemand diesbezüglich eine Idee?


StefanVogel
Senior
Dabei seit: 26.11.2005
Mitteilungen: 3708
Aus: Raun
Beitrag No.2, eingetragen 2020-09-19 08:40

Hallo mbInfoStudent,
die Zeile

2020-09-17 18:28 - mbInfoStudent im Themenstart schreibt:
\(u_i^* \geq0,  z_i^* \geq 0, u_i^* >0 \Rightarrow z_i^* = 0\)

lese ich als "es gilt \(u_i^* \geq0\) und \(z_i^* \geq 0\) und wenn \(u_i^* >0\) dann ist \(z_i^* = 0\)". Es wird nicht behauptet, dass \(u_i^* >0\) ist, sondern nur ausgesagt, wenn \(u_i^* >0\) ist, dann ist \(z_i^* = 0\). Ob das inhaltlich zu der Herleitung passt, überblicke ich nicht. Das ist nur so eine Idee, wie das gemeint sein könnte.

Viele Grüße,
  Stefan




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249457=110
Druckdatum: 2020-12-02 03:48