Linear Classification (구현)

경사 하강법(Gradient Descent)를 이용하여 선형 분류 문제를 해결

 

레이블이 $1$, $0$인 두 개의 클래스에 대한 분류문제에서 샘플이 특정 클래스에 속할 확률을 추정하는 지도학습의 한 가지 (Binary case)

선형회귀 모델과 같이 입력 특성의 가중치의 합(편향 포함) ${\beta}^{\rm T} x = \beta_0+\beta_1 x_1+\cdots +\beta_nx_n$을 계산한 다음 시그모이드 함수(sigmoid) $\sigma(t)=\dfrac{1}{1+\exp(-t)}$를 취한 값 $\sigma({\beta}^{\rm T} x)$를 ${\rm P}(Y=1|X=x)$에 대한 추정값 $\hat p(x)$로 추정하는 모델.

즉, 모델 파라미터 ${\beta}=(\beta_0,\cdots,\beta_n)^{\rm T}$에 대한 로지스틱 회귀 모델을 $h_{{\beta}}$라 할 때,

$\quad \quad 
\hat p(x) = h_{{\beta}}(x)= \sigma({\beta}^{\rm T}x)
=\dfrac{1}{1+\exp(-{\beta}^{\rm T}x)}=\dfrac{1}{1+\exp\bigl(-(\beta_0+\beta_1x_1+\cdots+\beta_n x_n)\bigr)} 
$

 

로지스틱 회귀 모델을 통한 레이블의 예측 

샘플 $x$가 양성 클래스(y=1)에 속할 확률 $\hat p(x)=h_{{\beta}}(x)$를 추정한 후 다음과 같이 예측 $\hat y$를 구함 

$$
\hat y = \begin{cases} 0 & \text{ if }\hat p(x)<0.5\\ 1 &\text{ if }\hat p(x)\ge0.5
\end{cases}
$$

 

1. 회귀 계수 결정법 (Numerical Search)
비용함수 $L(\beta)$는 $\beta$에 대해 아래로 볼록한(Convex) 함수이므로 최솟값이 존재함을 보장할 수 있지만, Direct Search 처럼 해를 구하는 공식은 없음  

경사하강법 또는 다른 최적화 알고리즘(BFGS, Newton ...)을 이용하여 해의 근삿값을 구함

배치 경사하강법을 적용할 때 비용함수에 대한 그래디언트 벡터 $\nabla_{\beta}L(\beta)$ : 각 $i$ ($1\le i\le n)$에 대해 $\nabla_{\beta}L(\beta)$의 $j$번째 성분
$$
\begin{aligned}
&\\
\dfrac{\partial L(\beta)}{\partial \beta_j} & = -\frac{1}{n} \sum^{n}_{i=1} [y_{i}\cdot \left( \frac{1}{\sigma \left( \beta^{\rm T} x_{i}\right)  } \right)  \cdot \sigma \left( \beta^{\rm T} x_{i}\right)  \left( 1-\sigma \left( \beta^{\rm T} x_{i}\right)  \right)  \cdot x^{(n)}_{i}]-[\left( 1-y_{i}\right)  \cdot \left( \frac{1}{1-\sigma \left( \beta^{\rm T} x_{i}\right)  } \right)  \cdot \sigma \left( \beta^{\rm T} x_{i}\right)  \cdot \left( 1-\sigma \left( \beta^{\rm T} x_{i}\right)  \right)  \cdot x^{(n)}_{i}]\\
& = -\frac{1}{n} \sum^{n}_{i=1} [y_{i}\cdot \left( 1-\sigma \left( \beta^{\rm T} x_{i}\right)  \right)  \cdot x^{(n)}_{i}]+[\left( 1-y_{i}\right)  \cdot \left( -1\right)  \cdot \sigma \left( \beta^{\rm T} x_{i}\right)  \cdot x^{(n)}_{i}] \\
& = -\frac{1}{n} \sum^{n}_{i=1} \left[ y_{i}-y_{i}\cdot \sigma \left( \beta^{\rm T} x_{i}\right)  -\sigma \left( \beta^{\rm T} x_{i}\right)  +y_{i}\cdot \sigma \left( \beta^{T} x_{i}\right)  \right]  \cdot x^{(n)}_{i} \\
& = -\frac{1}{n} \sum^{n}_{i=1} \left[ y_{i}-\sigma \left( \beta^{\rm T} x_{i}\right)  \right]  \cdot x^{(n)}_{i} \\
& = \frac{1}{n} \sum^{n}_{i=1} \left[ \sigma \left( \beta^{\rm T} x_{i}\right)  -y_{i}\right]  \cdot x^{(n)}_{i} \\
\end{aligned}$$

 

(1) 배치 경사 하강법(Batch Gradient Descent)

파라미터를 업데이트 할 때마다 모든 학습 데이터를 사용하여 cost function의 gradient를 계산

Vanilla Gradient Descent라 불림

모든 학습 데이터를 사용하기 때문에 gradient의 방향성은 정확하지만 연산이 오래걸려 학습 효율이 좋지 못함
$$\nabla_{\beta} L(\beta) = \dfrac 1 n  X^{\rm T}( \sigma (X\beta)- y) \; : \; \text{gradient}$$
$$\beta^{(t+1)}⇐\beta^{(t)}-\eta \nabla_{\beta}L(\beta) \; : \; \text{update rule}$$

beta_bgd_path = list()
eta = 0.1 # 학습률 
n_epochs = 500 # epoch 수 
n = 100 # 샘플수 

np.random.seed(42)
beta_bgd = np.random.randn(2,1) 

####### Empty Module.5 #########
# Batch Gradient Descent를 통해서 최적의 Beta를 찾아보세요
for iteration in range(n_epochs):
    logits = Xb.dot(beta_bgd)
    probabilities = sigmoid(logits)
    gradients = 1 / n * Xb.T.dot(probabilities - y) # 배치 경사 하강법에 해당하는 gradient를 계산하세요 
    beta_bgd = beta_bgd - eta * gradients           # update rule에 따라서 beta_bgd를 update 하세요
    beta_bgd_path.append(beta_bgd)
###############################

 

(2) 확률적 경사 하강법(Stochastic Gradient Descent)

파라미터를 업데이트 할 때, 무작위로 샘플링된 학습 데이터를 하나씩만 이용하여 cost function의 gradient를 계산

모델을 자주 업데이트 하며, 성능 개선 정도를 빠르게 확인 가능

Local minima에 빠질 가능성을 줄일 수 있음
$$\nabla_{\beta} L(\beta) = x(\sigma(x^{\rm T}\beta)- y) \; : \; \text{gradient}$$
$$\beta^{(t+1)}⇐\beta^{(t)}-\eta \nabla_{\beta}L(\beta) \; : \; \text{update rule}$$

beta_sgd_path = []
n_epochs = 500
t0, t1 = 5, 10  # 학습 스케줄 하이퍼파라미터 
n = 100         # 샘플 수 

def learning_schedule(t):
    return t0/(t+t1)
    
np.random.seed(42)
beta_sgd = np.random.randn(2,1)  # beta 무작위 초기화 

####### Empty Module.6 #########
# Stochastic Gradient Descent를 통해서 최적의 Beta를 찾아보세요
for epoch in range(n_epochs):
    for i in range(n):
        eta = learning_schedule(epoch * n + i)

        random_idx = np.random.randint(n)   # 0 ~ n-1 까지 랜덤하게 인덱스 선택
        tx = Xb[random_idx:random_idx+1]    # random_idx를 활용해 샘플 하나 선택
        ty = y[random_idx:random_idx+1]     # random_idx를 활용해 샘플 하나 선택
        
        logits = tx.dot(beta_sgd)
        probabilities = sigmoid(logits)
        gradients = tx.T.dot(probabilities - ty)    # 확률적 경사 하강법에 해당하는 gradient를 계산하세요 
        beta_sgd = beta_sgd - eta * gradients       # update rule에 따라서 beta_sgd를 update 하세요
        
        beta_sgd_path.append(beta_sgd)
##############################

 

(3) 미니 배치 경사 하강법(Mini Batch Gradient Descent) 

파라미터를 업데이트 할 때마다 일정량의 일부 데이터를 무작위로 뽑아 cost function의 gradient를 계산

 

Batch Gradient Descent와 Stochastic Gradient Descent 개념의 혼합

SGD의 노이즈를 줄이면서, GD의 전체 배치보다 효율적
$$\nabla_{\beta}L(\beta)=\frac{1}{m}\sum_{i=1}^{m} x_{i}(\sigma (x_{i}^{\rm T}\beta)-y) \; : \; \text{gradient}$$
$$\beta^{(t+1)}⇐\beta^{(t)}-\eta \nabla_{\beta}L(\beta) \; : \; \text{update rule}$$

beta_mgd_path = []

n_epochs = 50
minibatch_size = 20

np.random.seed(42)
beta_mgd = np.random.randn(2,1)  # 랜덤 초기화

t0, t1 = 200, 1000
def learning_schedule(t):
    return t0 / (t + t1)

t = 0

####### Empty Module.8#########
for epoch in range(n_epochs):
    shuffled_indices = np.random.permutation(n)
    X_shuffled = X[shuffled_indices]
    y_shuffled = y[shuffled_indices]
    for i in range(0, n, minibatch_size):
        t += 1
        eta = learning_schedule(t)

        tx = X_shuffled[i:i + minibatch_size]  # minibatch_size를 활용해 batch 단위로 샘플링
        ty = y_shuffled[i:i + minibatch_size]  # minibatch_size를 활용해 batch 단위로 샘플링
        
        logits = tx.dot(beta_mgd)
        probabilities = sigmoid(logits)
        gradients = 1 / minibatch_size * tx.T.dot(probabilities - ty)   # 미니 배치 경사 하강법에 해당하는 gradient를 계산하세요 
        beta_mgd = beta_mgd - eta * gradients                           # update rule에 따라서 beta_mgd를 update 하세요
        
        beta_mgd_path.append(beta_mgd)
###############################