문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 지도 학습]] == 개요 == Binary decision rule이란, d 차원의 공간을 두가지의 공간으로 나누는 것을 말한다. 이때 사용되는 면을 Hyperplane이라고 한다. 예를 들어서 2차원에서 1차원 직선은 2차운 공간을 두 공간으로 나누며 그 직선을 Hyperplane이라고 한다. Binary percpetron Algorithm이란, 이러한 Hyperplane의 계수를 알아내는 작업을 말한다. Perceptron 은 mistake 기반의 online classifier이고, neural network의 기본적인 building block이 된다. == Binary Perceptron Algorithm == * w = 0에서 시작하여 * 모든 데이터(epoch)에 대해서 t = 1...T까지 반복하며 ** 각각 데이터에 있는 샘플 (x,y) i = 1...N까지 반복하며 *** prediction = sign(w dot x_i)를 계산하여 (sign은 0일 경우 -1을 리턴한다.) **** 만약 예측이 올바르면(prediction == y_i) 계수 w를 바꾸지 않고 **** 만약 틀리다면 w = w + y_ix_i로 계수를 바꾼다. == Multiclass Decision Rule == *모든 class마다 각자의 weight vector을 두고 *activate을 다음과 같이 계산하여 : <math>activation_w(x,y) = w_y x</math> *제일큰 activation을 같는 class가 분류하도록 하면된다. : <math> argmax_y(activation_w(x,y))</math> === Multiclass Perceptron Algorithm === * w = 0에서 시작하여 * 모든 데이터(epoch)에 대해서 t = 1...T까지 반복하며 ** 각각 데이터에 있는 샘플 (x,y) i = 1...N까지 반복하며 *** prediction = argmax_k(w_k,x_i)를 계산하여 (sign은 0일 경우 -1을 리턴한다.) **** 만약 예측이 올바르면(prediction == y_i) 계수 w를 바꾸지 않고 **** 만약 틀리다면 잘못 예측된 클래스는 w = w - x_i로 계수를 바꾼고, **** 원래 올바르게 분류되어야 했을 클래스는 w = w + x_i로 계수를 바꾼다. == Logistic Regression과의 차이 == [[Logistic Regression]]또한 비슷한 업데이트 방식을 가지고 있다. : <math>w_i^{(t+1)} \leftarrow w_i^t + n\sum_j x_i^j[y^j-P(y^j=1|x^j,w)]</math> 그리고 Perceptron은 다음과 같은 업데이트 방식을 가진다. : <math>w_i^{(t+1)} \leftarrow w^t + y^ix^i</math> 사실 윗 식은 다음과 같이 적을 수 있다. : <math>w_i^{(t+1)} \leftarrow w^t + [y^i - sign^0(wx^i)]x^i</math> # Logistic Regression은 확률을 포함하며 계산한다. 즉 Logistic Regression은 Probalilistic모델이며 Perceptron은 Error driven learning이다. # Perceptron은 모든 각각의 샘플에 대해서 계수의 변화를 수반한다. # Logistic Regression은 계수의 업데이트에 모든 traing Data를 계산해야 하지만 Perceptron은 일부만으로도 계산을 진행 할 수 있다. # Perceptron은 online algorithm이라고 하며, Logsitic Regression은 offline이라고 한다. == Linearly Separable == : <math>\exists w \ s.t. \ ||w||_2 = 1 \ and \ \forall t \ y^t(w,x^t) \ge r \gt 0 </math> 인 r이 존재하면 Perceptron은 모든 x를 y에 분류할 수 있다. 여기서 r을 margin이라고 하며 hyperplane에서 데이터들이 최소한 r정도 떨어져 있음을 나타낸다. 사실 r은 [[SVM]]에서 Support Vectors라고 불리는 중요한 변수이다. === Mistake Bound === Mistake Bound란 Perceptron이 어느정도 잘못 분류를 하는 정도를 나타낸다. : <math>\exists w \ s.t. \ ||w||_2 = 1 \ and \ \forall t \ y^t(w,x^t) \ge r \gt 0 </math> 인 r에 대해서, : <math> \forall t \ ||x^t||_2 \ge R </math> 이면 : <math> mistakes \le \frac{R^2}{r^2}</math> == 문제점 == # Noise: 데이터가 Seperable하지 않으면 weight이 진동할 수 있다. 분류 가능하지 않기 때문에 수렴하지 않고 계속해서 결정면이 두 상태를 진동하는 것이다. 이러한 경우 평균을 내는 방식으로 해결할 수있다. Generalization으로 사용될 수 있다. # Overtraining: tranning / held-out 정확도가 오를 수록, overfitting되어서 test에서의 정확도가 떨어지는 문제가 생긴다. # Mediocre generalization: hyperplane이 두 집단의 가운데에 위치하는 것이 아니라 한 집단과 가깝게 형성되는 문제가 생길 수 있다. Binary decision rule 문서로 돌아갑니다.