Perzeptron Lernalgorithmus < math. Statistik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Suppose we have N points [mm] x_{i} \in \IR^p [/mm] in general position, with class labels [mm] y_{i} \in [/mm] {-1,1}. Prove that the perceptron learning algorithm converges to a separating hyperplane in a finite number of steps:
a) Denote a hyperplane by f(x)= [mm] \beta_{1}^T [/mm] x + [mm] \beta_{0}, [/mm] or in more compact notation [mm] \beta^T [/mm] x* =0, where x* = (x,1) and [mm] \beta [/mm] = [mm] (\beta_{1},\beta_{0}). [/mm] Let [mm] z_{i}= x_{i}* [/mm] / [mm] \parallel x_{i}*\parallel [/mm] . Show that separability implies the existence of a [mm] \beta_{opt} [/mm] such that [mm] y_{i}\beta_{opt}^T z_{i} \ge [/mm] 1 [mm] \forall [/mm] i
b) Given a current [mm] \beta_{old} [/mm] , the perceptron algorithm identifies a point [mm] z_{i} [/mm] that is missclassified, and produces the update [mm] \beta_{new} [/mm] <- [mm] \beta_{old} [/mm] + [mm] y_{i} z_{i}. [/mm]
Show that [mm] \parallel \beta_{new} [/mm] - [mm] \beta_{opt}\parallel^{2} \le \parallel \beta_{old} [/mm] - [mm] \beta_{opt} \parallel^{2} [/mm] -1 , and hence that the algorithm converges to a separating hyperplane in no more than [mm] \parallel \beta_{start} [/mm] - [mm] \beta_{opt} \parallel^{2} [/mm] steps (Ripley, 1996). |
Im Prinzip ist das die Anleitung für den Beweis, aber ich komm trotzdem nicht nach.
Meine Fragen:
Wie kommt man auf [mm] \ge [/mm] 1 in Teil a?
Man kann bei Trennbarkeit ja sagen, dass die Punkte auf der einen oder anderen Seite der Hyperebene liegen, also
[mm] \beta^T [/mm] x* > 0 für [mm] y_{i} [/mm] =1 und
[mm] \beta^T [/mm] x* < 0 für [mm] y_{i} [/mm] = -1
Wenn man das zusammen schreibt:
[mm] y_{i}\beta^T [/mm] x* > 0 für [mm] y_{i} \in [/mm] {-1,1}
Und zu Teil b:
Es ist ja [mm] \parallel \beta_{neu}-\beta_{opt}\parallel \le \parallel \beta_{old}-\beta_{opt}\parallel
[/mm]
Das gilt dann auch fürs Quadrat. Aber wieso das -1?
Vielen Dank für eure Hilfe!!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:26 Di 03.07.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
