[Incarnate the Algorithm] Linear Classification

Classification problem을 해결하는 방법에는 크게 두 가지가 있다.

그 중의 하나인 regression perspective를 다루고자 햔다.

이는 분류 문제를 회귀의 관점에서 바라보는 것이다. 

 

multi-class를 분류하는 방법도 있지만 여기서는 2 class classification problem을 다룬다.

2개의 class를 나타내는 output으로 0과 1을 가진다고 하자.

그렇다면 이를 step function으로 나타낼 수 있다. step function은 다음과 같이 0과 1의 output만을 가진다.

graph of step function

하지만 이 function을 이용할 경우 1의 값을 갖는 data를 0으로 잘못 분류하는 경우가 발생할 수 있다,

또한 discrete function이므로 data를 step function에 넣어 least squares를 적용하면 수많은 discrete flat region이 생겨 w를 최적화하는 것이 매우 어렵다.

lots of discrete flat regions

 

이러한 문제를 해결하기 위해 step function을 smooth function으로 만든 것이 logistic sigmoid function이다.

step function처럼 0과 1의 값만을 가지는 것은 아니지만 연속적인 함수이며 x가 0에 가까울수록 0에 한없이 가까워지고, x가 무한대에 가까울수록 1에 가까워진다는 점에서 step function과 유사하다.

logistic sigmoid function

그래프의 양 끝에서 0과 1에 가까워지는 것을 알 수 있다

 

이 함수는 step function과는 다르게 연속함수이므로 discrete flat region이 생기지 않는다.

logistic regression

이를 logistic regression이라고 한다.

이는 일반적으로 항상 convex는 아니지만, local optimization을 이용하면 적절하게 최적화할 수 있다.

 

 

y_p의 label이 {0, 1} 두 가지일 때, log error를 통하여 더 나은 하나의 식으로 표현하면 이를 Cross Entropy cost function(for logistic regression)이라고 한다.

시그마는 sigmoid function

 

이와 유사하지만 ,y_p의 label이 {-1, 1} 두 가지일 때, log error를 통하여 더 나은 하나의 식으로 표현하면 이를 softmax cost function(for logistic regression)이라고 한다.

이때 sigmoid는 {0,1}의 label에 대해 유효하므로, 2*sigmoid - 1로 표현되는 hyperbolic tangent function으로 대체한다.

 

두 함수는 항상 convex function으로 least square에 비해 훨씬 강력하며, label의 값만 다르지 완전히 동일한 함수이다.

 

 

---

이제 이 함수들을 이용하여 data들을 fitting해보자.

 

다음과 같은 data가 주어져있다.

{0, 1}의 label

 

data가 {0, 1}의 label을 가지므로, cross entropy 함수를 이용해야 한다.

따라서 cross entropy 함수를 코드로 정의하면 다음과 같다.

# 1) cross-entropy cost 함수를 정의

def model(x, w): # linear regression을 통해 구한 hyperplane
    a = w[0] + np.dot(x.T, w[1:]) 
    return a.T

def sigmoid(t):
    return 1/(1 + np.exp(-t))

def cross_entropy(w, x, y):
    a = sigmoid(model(x,w)) # 구한 model함수를 sigmoid함수에 넣어 근사화한 값을 구한다
    
    ind = np.argwhere(y==0)[:,1] # [0,1,2,3,4]; 답(y)을 알고 있으므로 이를 이용한다
    cost = -np.sum(np.log(1 - a[:,ind])) # np.log(ind에 해당하는 model의 output)의 값이 배열로 저장 => np.sum으로 더한다
    
    ind = np.argwhere(y==1)[:,1] # [5,6,7,8,9,10]
    cost -= np.sum(np.log(a[:,ind]))
    
    return cost/y.size

 

함수의 정의가 끝났다면, 앞서 했듯이 gradient descent를 통해 cost를 줄여나갈 수 있다.

이에 대한 내용은 Gradient Descent 포스팅을 참고하자.

https://yeppyteen2.tistory.com/19

[Incarnate the Algorithm] Gradient Descent

 

이를 적용한 코드는 다음과 같다.

# 2) gradient descent 알고리즘으로 솔루션 찾기

from autograd import grad 
import autograd.numpy as np 

# gradient descent function 
def gradient_descent(g,alpha,max_its,w,x,y):
    # g : 사용하고자 하는 cost function
    # alpha : steplength
    # max_its : iteration 횟수
    # w : 구하고자 하는 weight vector
    # x : input data, y : output data(정답)
    
    # compute gradient module using autograd
    gradient = grad(g) # get the differentiated function of g

    # run the gradient descent loop
    weight_history = [w] # weight history container
    cost_history = [g(w,x,y)] # cost function history container
    for k in range(max_its):
        # evaluate the gradient
        grad_eval = gradient(w, x, y)

        # take gradient descent step
        w = w - alpha*grad_eval
        
        # record weight and cost
        weight_history.append(w)
        cost_history.append(g(w, x, y))
    return weight_history,cost_history


g = cross_entropy 
w0 = 0.1*np.random.randn(2,1) # 임의의 initial w 생성
max_its = 20000 
alpha_choice = 10**(1.2)
w_history, cost_history = gradient_descent(g,alpha_choice,max_its,w0,x,y)

 

alpha나 max_its의 값이 꽤 큰 것을 알 수 있는데, 이 문제의 경우에 적합한 fitting이 이루어지려면 이 정도를 적용해야만 했다. (너무 많은 반복횟수는 시간이 오래걸리고, 너무 큰 alpha는 오류를 일으키므로 분류가 잘 보이는 적절한 값을 선택해주었다.)

이제 잘 분류가 되는지 확인하기 위해 먼저 cost function history plot과 w1 w2 values history plot을 확인해보면 다음과 같이 적절하게 cost가 줄어들고 있음을 알 수 있다.

 

이를 통해 그린 regression function은 다음과 같다.

# 3-2) regression function 그리기

W = []
W.append(w1[-1])
W.append(w2[-1])
W = np.array(W).reshape((2,1)) # 행렬 곱 연산을 위해 array의 형태를 바꿔준다
A = sigmoid(model(x, W))
print(A)

x2 = x.reshape((11,)) # 그림을 그리기 위해 다시 일반적인 array의 형태로 바꿔준다
A = A.reshape((11,)) # 그림을 그리기 위해 다시 일반적인 array의 형태로 바꿔준다
# idx = np.argsort(x2)  # get the indices that would sort x
# x_sorted = x2[idx]  # sort x in ascending order
# A_sorted = A[idx]

plt.figure()

plt.scatter(x, y, alpha=0.3) # x, y data는 각각 11개
plt.plot(x2, A, c='r')

[[7.25825196e-41 1.42921547e-30 5.78534182e-30 6.24712132e-15
  1.18276042e-02 9.88821819e-01 1.00000000e+00 1.00000000e+00
  1.00000000e+00 1.00000000e+00 1.00000000e+00]]

어느정도 잘 fitting이 된 모습이다

 

 

이번에는 softmax함수를 이용하여 classification을 진행해보자.

앞의 data에서 0이었던 값을 -1로 바꿔주기만 하면 된다.

label이 {-1, 1}이다

 

마찬가지로 softmax함수를 정의한다.

# 1) Softmax cost 함수를 정의

def model(x, w):
    a = w[0] + np.dot(x.T, w[1:])
    return a.T

def hyperbolic_tangent(t):
    return 2*sigmoid(t) - 1

def softmax(w, x, y):
    cost = np.sum(np.log(1 + np.exp(-y*model(x,w))))
    return cost/float(np.size(y))

 

이를 이용하여 똑같은 방식으로 classification을 진행하면 다음의 결과를 얻을 수 있다.

앞과 완전히 동일한 과정이므로 설명이나 코드는 생략하겠다.

 

A = hyperbolic_tangent(model(x, W)) # 최종적으로 구한 w를 이용하여 hyperbolic함수로 근사화된 최종값들을 피팅하여 그릴 수 있다

[[-1.         -1.         -1.         -1.         -0.976316    0.97761643
   1.          1.          1.          1.          1.        ]]

softmax함수도 마찬가지로 잘 fitting이 되어 분류가 잘 이뤄진 것을 확인할 수 있다.