Binary decision rule

개요

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]

1. Logistic Regression은 확률을 포함하며 계산한다. 즉 Logistic Regression은 Probalilistic모델이며 Perceptron은 Error driven learning이다.
2. Perceptron은 모든 각각의 샘플에 대해서 계수의 변화를 수반한다.
3. Logistic Regression은 계수의 업데이트에 모든 traing Data를 계산해야 하지만 Perceptron은 일부만으로도 계산을 진행 할 수 있다.
4. 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]

문제점

1. Noise: 데이터가 Seperable하지 않으면 weight이 진동할 수 있다. 분류 가능하지 않기 때문에 수렴하지 않고 계속해서 결정면이 두 상태를 진동하는 것이다. 이러한 경우 평균을 내는 방식으로 해결할 수있다. Generalization으로 사용될 수 있다.
2. Overtraining: tranning / held-out 정확도가 오를 수록, overfitting되어서 test에서의 정확도가 떨어지는 문제가 생긴다.
3. Mediocre generalization: hyperplane이 두 집단의 가운데에 위치하는 것이 아니라 한 집단과 가깝게 형성되는 문제가 생길 수 있다.