목표 vector w⋆, 현재 vector w 라고 하자.
Data set {((x1,y1), ... , (xd,yd)} 가 주어졌다고 하자.
WLOG, ||w⋆||=1, ||x||≤1 이라고 하자.
( 모든 data에 xi←xi/max(x) 해도 같은 hyperplane 얻는다 )
WLOG, w=0 으로 시작한다고 하자.
w⋆의 정의에 따라 모든 (x,y)에 대해 yxTw⋆>0이 성립한다.
Lemma : yxTw⋆≥γ
γ=minx|xTw⋆| 라고 하자.
즉, γ는 목표 hyperplane으로부터의 minimal margin이다.
이 때, yxTw⋆=|xTw⋆|≥γ 가 성립한다. ◻
어떤 (x,y)에 대해 yxTw≤0이 성립하여 update가 이루어졌다고 하자.
1. wTneww⋆=(w+yx)Tw⋆=wTw⋆+yxTw⋆≥wTw⋆+γ
2. wTnewwnew=(w+yx)T(w+yx)=wTw+2yxTw+y2xTx≤wTw+1
이제 M번의 update가 이루어졌다고 해보자.
Mγ≤wTw⋆≤||wT||=√wTw≤√M
∴M≤1γ2
Update는 많아야 ⌊1γ2⌋ 번 이루어진다.