제 2 장
2.감지기2.1 감지기 모형2.2 감지기 학습 전략2.3 감지기 학습 알고리즘 감지기 학습 알고리즘의 원시 형식 감지기 학습 알고리즘의 대구형2.4 감지기 학습 알고리즘 수렴 증명2.5 나의 실현은 반드시 간편하지 않다모든 데이터 발굴을 위한 준비
2. 감지기
2.1 감지기 모형
감지기: 두 가지 분류의 선형 모델. 수학적 표현: 입력 공간 X R n X\subseteq R^n X Rn, 출력 공간은 y = {+ 1, 1} y={+1, -1\} y={+1, 1}, 입력 실례x, 입력 실례x, 출력 실례y, 입력 공간을 출력 공간으로 출력하는 함수: f(x) = s i g n(w x + b) f (x) = = sign (wx + b) = sign (wx + b) f (x) f(x) f (x) f(x) f(x) f) f(x) x x x x) f(x) = sign) = sign (x) x x x b) = sign (x)) x x b) = sign (x)) R b\in R b∈R을 편향이라고 합니다.sign 함수는 기호 함수 s i g n(x) = {+ 1, x ⨤0 - 1, x < 0 sign(x) =\begin {cases} +1, & x\geqslant 0\\-1, & x <0\end {cases} sign (x) = {+1, -1, x ⪈0x <0 초평면 S:w x + b = 0 wx + b=0 wx + b=0은 하나의 초평면 S에 대응하고 w는 초평면의 법방향량이며 b는 초평면의 거리로 견본점을 정, 음 두 종류로 나눌 수 있다. 데이터 세트 T의 경우 모든 y i = + 1 yi = +1 yi = +1의 인스턴스, w x i + b > 0 wxi+b>0 wxi+b>0; y i = − 1 y_i = -1 yi = -3 1의 인스턴스, w x i + b < 0 wxi+b<0 wxi+b<0이면 데이터 세트 T는 선형 데이터 세트입니다. 2.2 감지기 학습 전략
입력 공간 R n R^n Rn 중 하나 x 0 x0 x 0 - 초평면 S까지의 거리: 1\w\w x 0 + b\\\\\{| | w | | | | | | | | | | | | | | | | wx0+b | wx0 +b2 L2 범수 데이터가 yi (w x i + b) > 0 y 로 올바르게 분류되면i(wx i+b)>0 yi(wxi+b)>0, yi(w x i + b)로 잘못 분류된 경우 < 0 yi(wx i+b) <0yi(wxi+b) <0, 잘못된 분류점에서 초평면 S까지의 거리i(wx_i+b) −∣∣w∣∣1yi(wxi+b) 손실 함수: L(w x + b) = -3. ∑ x i ∈M y i(w x i + b) L(w x + b) = -\sum{x_i\in M}y_i(wx i+b) L(wx+b) = --∑xi∈Myi(wxi+b), M은 오분류 지점이다.이 손실 함수는 바로 감지기의 경험 위험 함수다. 2.3 감지기 학습 알고리즘
감지기 학습 알고리즘의 원시 형식
손실 함수 극소화: m i n L(w x + b) = -3∑ x i ∈M y i(w x i + b)minL(wx + b)=-\sum{x_i\in M}y_i(wx_i+b) minL(wx+b)=−∑xi∈Myi(wxi+b) 경도 하락:\w L(w, b) = --∑ x i∈M y i x i ablawL(w,b)=-\sum_{x_i\in M}y_ix_i ∇wL(w,b)=−xi∈M∑yixi ∇ b L ( w , b ) = − ∑ x i ∈ M y i abla_bL(w,b)=-\sum_{x_i\in M}y_i ∇bL(w,b)=−xi∈M∑yi w ← w + η y i x i w\leftarrow w +\eta y_ix_i w←w+ηyixi b ← b + η y i b\leftarrow b +\eta y_i b←b+ηyi 알고리즘 과정 초기값 w 0, b 0 w 선택0,b_0 w0,b0 훈련집중에서 데이터 선택(xi, y i)(x i, y i)(xi, yi) 만약 y i (w x i + b)⩽ 0 yi(wx_i+b)\leqslant 0 yi(wxi+b)⩽0, w ← w + η y i x i , b ← b + η y i w\leftarrow w +\eta y_ix_i,b\leftarrow b +\eta y_i w←w+ηyixi,b←b+η이 점이 올바르게 분류될 때까지 훈련 집중에 오류 분류점이 없을 때까지 두 번째 단계로 이동 감지기 학습 알고리즘의 대구 형식
마지막으로 배운 w, b를 w=∑i=1 N으로 표시α i y i x i , b = ∑ i = 1 N α i y i w=\sum_{i=1}^{N}\alpha_iy_ix_i,b=\sum_{i=1}^N\alpha_iy_i w=∑i=1Nαiyixi,b=∑i=1Nαiyi, α i > 0\alpha_i>0 αi>0, N은 샘플 크기
알고리즘 프로세스: 감지기 모델 f(x) = s i g n(∑j = i Nα j y j x j x + b ) f(x)=sign(\sum_{j=i}^N\alpha_j y_jx_jx+b) f(x)=sign(∑j=iNαj yj xj x+b), 여기서α = ( α 1 , α 2 , ⋯ , α N ) T\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T α=(α1,α2,⋯,αN)T α ← 0 , b ← 0\alpha\leftarrow 0,b\leftarrow 0 α←0,b←0 훈련 집중 선택 데이터(xi, yi)(x i, y i)(xi, yi) Y i ∑j = i Nα j y j x j x i + b ⩽ 0 y_i\sum_{j=i}^N\alpha_j y_jx_jx_i+b\leqslant 0 yi∑j=iNαjyjxjxi+b⩽0, α i ← α i + η , b ← b + η y i\alpha_i\leftarrow\alpha_i +\eta ,b\leftarrow b +\eta y_i αi←αi+η,b←b+ηyi 2.4 감지기 학습 알고리즘 수렴 증명
마지막 선형 데이터 집합 학습 결과는 w ^ o p t ⋅ x ^ = w o p t ⋅ x + b o p t = 0\hat {w}{opt}\cdot\hat{x} = w_{opt}\cdot x+b_{opt}=0 w^opt⋅x^=wopt⋅x+bopt=0, ∣ ∣ w ^ o p t ∣ ∣ = 1 ||\hat{w}_{opt}||=1 ∣∣w^opt∣∣=1.
있음γ\gamma γ,모든 데이터를 중앙 집중식으로 y i (w ^ o p t ⋅ x ^ i) = w o p t ⋅ x i + b o p t γ y_i(\hat{w}_{opt}\cdot\hat{x}_i )= w_{opt}\cdot x_i+b_{opt}\geqslant\gamma yi(w^opt⋅x^i)=wopt⋅xi+bopt⩾γ,즉γ\gamma γ초평면에서 가장 가까운 점의 거리입니다. 제k차 학습 후의 학습 결과가 데이터 집합을 완전히 정확하게 분리할 수 있다고 가정한다.w ^ k − 1 = ( w k − 1 T , b k − 1 ) T\hat{w}_{k-1}=(w_{k-1}^T,b_{k-1})^T w^k−1=(wk−1T,bk−1)T w k ← w k − 1 + η y i x i , w_k\leftarrow w_{k-1} +\eta y_ix_i, wk←wk−1+ηyixi, b k ← b k − 1 + η y i , b_{k}\leftarrow b_{k-1} +\eta y_i, bk←bk−1+ηyi, w ^ k = w ^ k − 1 + η y i x ^ i\hat{w}_k=\hat{w}_{k-1} +\eta y_i\hat{x}_i w^k=w^k−1+ηyix^i w ^ k ⋅ w ^ o p t = w ^ k − 1 ⋅ w ^ o p t + η y i w ^ o p t x ^ i ⩾ w ^ k − 1 ⋅ w ^ o p t + η γ ⩾ w ^ o ⋅ w ^ o p t + k η γ\hat{w}_k\cdot\hat{w}_{opt} =\hat{w}_{k-1}\cdot\hat{w}_{opt} +\eta y_i\hat{w}_{opt}\hat{x}_i\geqslant\hat{w}_{k-1}\cdot\hat{w}_{opt}+\eta\gamma\geqslant\hat{w}_{o}\cdot\hat{w}_{opt}+k\eta\gamma w^k⋅w^opt=w^k−1⋅w^opt+ηyiw^optx^i⩾w^k−1⋅w^opt+ηγ⩾w^o⋅w^opt+kηγ ∣ ∣ w ^ k ∣ ∣ 2 = ∣ ∣ w ^ k − 1 + η y i x ^ i ∣ ∣ 2 = ∣ ∣ w ^ k − 1 ∣ ∣ 2 + 2 η y i w ^ k − 1 x ^ i + η 2 ∣ ∣ x ^ i ∣ ∣ 2 ⩽ ∣ ∣ w ^ k − 1 ∣ ∣ 2 + η 2 R 2 ⩽ ∣ ∣ w ^ 0 ∣ ∣ 2 + k η 2 R 2 ||\hat{w}_k||^2=||\hat{w}_{k-1} +\eta y_i\hat{x}_i||^2=||\hat{w}_{k-1}||^2 + 2\eta y_i\hat{w}_{k-1}\hat{x}_i +\eta^2||\hat{x}_i||^2\leqslant||\hat{w}_{k-1}||^2+\eta^2R^2\leqslant||\hat{w}_{0}||^2+k\eta^2R^2 ∣∣w^k∣∣2=∣∣w^k−1+ηyix^i∣∣2=∣∣w^k−1∣∣2+2ηyiw^k−1x^i+η2∣∣x^i∣∣2⩽∣∣w^k−1∣∣2+η2R2⩽∣∣w^0∣∣2+kη2R2 k η γ ⩽ w ^ k ⋅ w ^ o p t ⩽ ∣ ∣ w ^ k ∣ ∣ ∣ ∣ w ^ o p t ∣ ∣ ⩽ ∣ ∣ w ^ k ∣ ∣ 2 ⩽ k η R k\eta\gamma\leqslant\hat{w}_k\cdot\hat{w}_{opt}\leqslant ||\hat{w}_k||||\hat{w}_{opt}||\leqslant ||\hat{w}_k||^2\leqslant\sqrt{k}\eta R kηγ⩽w^k⋅w^opt⩽∣∣w^k∣∣∣∣w^opt∣∣⩽∣∣w^k∣∣2⩽k ηR k ⩽ ( R γ ) 2 k\leqslant(\frac{R}{\gamma})^2 k⩽(γR)2 2.5 나의 실현이 반드시 간편한 것은 아니다
import numpy as np
class Perception:
def __init__(self,x,y):
self.tdx = np.array(x)
self.tdy = np.array(y)
self.w = np.zeros(self.tdx[0].shape)
self.b = 0
def train(self):
n = 0
# ,
while np.sum((np.dot(self.tdx,self.w)+self.b)*self.tdy<=0)>0:
for xi,yi in zip(self.tdx,self.tdy):
# ,
while yi*(np.dot(xi,self.w)+self.b)<= 0:
self.w += yi*xi
self.b += yi
n += 1
print('w:',self.w,' b:',self.b,' %d '%n)
#
if np.sum((np.dot(self.tdx,self.w)+self.b)*self.tdy<0)== 0:
break
return self.w,self.b
x=[[3,3],[4,3],[1,1]]
y=[1,1,-1]
p = Perception(x,y)
wo,bo=p.train()
print(wo,bo)