http://deeplearning.stanford.edu/tutorial/

Supervised Learning and Optimization - Softmax Regression

Introduction

Softmax regression 혹은 multinomial logistic regression은 logistric regression의 일반화된 알고리즘입니다. 이는 여러 클래스를 다루기 위해 고안된 것입니다. Logistic regression에서는 레이블 $y^{(i)} \in \{ 0, 1 \} $으로 가정하였고, 이것을 0과 1 두 종류의 손글씨를 구분하는데 이를 사용하였습니다. 반면 Softmax regression은 $K$개 중 하나의 클래스를 가지는 레이블 $y^{(i)} \in \{ 1, \dots, K \} $를 구분할 수 있게 해 줍니다.

Logistic regression으로 돌아가서, $m$개의 이미 레이블이 지정된 훈련 셋 $ \{ (x^{(1)}, y^{(1)}), \ldots, (x^{(m)}, y^{(m)}) \} $ 가지고 있다고 가정합시다. 입력 특징은 $x^{(i)} \in \Re^{n} $ 입니다. Logistic regression을 사용하면, 바이너리 분류만이 가능하기 때문에 레이블은 $y^{(i)} \in \{ 0, 1 \} $이 되어야 할 것입니다. 우리의 hypothesis는 다음과 같습니다.

$$h_\theta(x) = \frac{1}{1+\exp(-\theta^\top x)}$$

그리고 모델 파라미터 $\theta$는 다음 cost function을 최소화하여 훈련됩니다.

$$J(\theta) = -\left[ \sum_{i=1}^m y^{(i)} \log h_\theta(x^{(i)}) + (1-y^{(i)}) \log (1-h_\theta(x^{(i)})) \right]$$

Softmax regression에서는 바이너리보다 여러 클래스의 분류에 관심이 있기 때문에 레이블 $y$를 2개가 아니라 $K$개의 다른 값을 갖도록 합니다. 따라서 우리 훈련 셋 $ \{ (x^{(1)}, y^{(1)}), \ldots, (x^{(m)}, y^{(m)}) \} $은, $y^{(i)} \in \{ 1, 2, \dots, K \} $의 값을 가집니다. 클래스 번호가 0이 아니라 1부터 시작한다는 점을 주의하길 바랍니다. MNIST 손글씨 숫자 분류 문제에서는, 각 클래스마다 $K=10$이 될 것입니다.

이제 우리는, 테스트 입력 $x$가 주어졌을 때 각 $k=1, \dots, K$에 대한 확률 $P(y=k|x)$을 추정하는 hypothesis가 필요합니다. 다시 말하면, $K$개의 각 클래스에 속할 확률을 추정하고 싶습니다. 따라서 hypothesis의 결과물은 각 클래스에 속할 확률 값으로 구성된 $K$차원의 벡터로 나타낼 수 있습니다. 따라서 모든 요소들의 합은 1이 됩니다. 자세히 살펴보묜, hypothesis $h_\theta(x)$는 아래와 같이 계산됩니다.

$$h_\theta(x) = \begin{bmatrix} P(y = 1 | x; \theta) \\ P(y = 2 | x; \theta) \\ \vdots \\ P(y = K | x; \theta) \end{bmatrix} = \frac{1}{ \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) }} \begin{bmatrix} \exp(\theta^{(1)\top} x ) \\ \exp(\theta^{(2)\top} x ) \\ \vdots \\ \exp(\theta^{(K)\top} x ) \\ \end{bmatrix}$$

여기서 $ \theta^{(1)}, \theta^{(2)}, \ldots, \theta^{(K)} \in \Re^{n} $ 는 우리 모델의 파라미터라고 할 수 있습니다. 또한 $\frac{1}{ \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) } }$은 normalization을 위한 항으로 각 요소의 합이 1이 되도록 하여 줍니다.

편의를 위해 이제부터는 각 클래스에 대한 파라미터 벡터들을 $\theta$로 표현하도록 하겠습니다. Softmax regression을 실제로 구현하게 될 때에도 아래와 같이 각 파라미터 벡터들을 컬럼으로 하는 n * K 행렬로 만들어 처리하는 것이 더 편리합니다.

$$\theta = \left[\begin{array}{cccc}| & | & | & | \\ \theta^{(1)} & \theta^{(2)} & \cdots & \theta^{(K)} \\ | & | & | & | \end{array}\right]$$

Cost Function

이제 softmax regression에서 사용할 cost function에 대해서 알아봅시다.

$$J(\theta) = - \left[ \sum_{i=1}^{m} \sum_{k=1}^{K} 1\left\{y^{(i)} = k\right\} \log \frac{\exp(\theta^{(k)\top} x^{(i)})}{\sum_{j=1}^K \exp(\theta^{(j)\top} x^{(i)})}\right]$$

위의 식에서 $ 1 \{ \cdot \} $는 indicator function이라고 불리는 것으로, 괄호 안의 조건이 참이면 1, 그렇지 않으면 0의 값을 갖는 함수입니다. 예를들면, $ 1 \{ 2 + 2 = 4 \}$는 1로, $ 1 \{ 1 + 1 = 5 \}$는 0으로 대체됩니다.

Logistic regression의 일반화 식도 위와 같은 형식으로 나타낼 수 있습니다.

$$J(\theta) = - \left[ \sum_{i=1}^m (1-y^{(i)}) \log (1-h_\theta(x^{(i)})) + y^{(i)} \log h_\theta(x^{(i)}) \right] \\ = - \left[ \sum_{i=1}^{m} \sum_{k=0}^{1} 1\left\{y^{(i)} = k\right\} \log P(y^{(i)} = k | x^{(i)} ; \theta) \right]$$

Softmax의 cost function은 $K$개의 클래스 레이블에 대해서 값을 더해주는 부분을 제외하고는 위의 일반화된 logistic regression 식과 동일합니다. 따라서 softmax regression에서 각 클래스 레이블에 대한 확률은 다음과 같이 됩니다.

$$P(y^{(i)} = k | x^{(i)} ; \theta) = \frac{\exp(\theta^{(k)\top} x^{(i)})}{\sum_{j=1}^K \exp(\theta^{(j)\top} x^{(i)}) }$$

하지만 이 cost function $J(\theta)$의 최저점을 해석적(analytically)으로 찾는 것은 불가능하기 때문에 반복적인(iterative) 방법을 사용하여 푸는 수밖에 없습니다.

“$\nabla_{\theta^{(k)}}$“의 의미를 다시 상기시켜 보면, $\nabla_{\theta^{(k)}} J(\theta)$는 벡터로, 이 벡터의 $j$번째 요소는 $\frac{\partial J(\theta)}{\partial \theta_{jk} }$입니다. 즉 각 요소는 $J(\theta)$를 $\theta^{(k)}$의 $j$번째 요소에 대해서 편미분 한 값입니다.

이를 이용하여 $J(\theta)$의 최소지점을 구하기 위해서 일반적인 최적화 알고리즘들에 이 문제를 적용할 수 있습니다.

Properties of softmax regression parameterization

Softmax regression은 일반적이지 않은 특성을 하나 가지고 있습니다. 바로 파라미터의 redundant 셋을 가진다는 것입니다. 이것이 무엇인지 이야기 하기 위해 다음을 가정해봅시다. 일단 각 파라미터 벡터 $\theta^{(j)}$에서 어떤 특정한 벡터 $\psi$를 뺀 벡터를 생각해봅시다. 이제 $\theta^{(j)}$는 $\theta^{(j)} - \psi $로 대체되었을 것입니다. 그렇다면 우리의 hypothesis는 이제 각 클래스에 대해 다음과 같이 변하게 됩니다.

$$P(y^{(i)} = k | x^{(i)} ; \theta) = \frac{\exp((\theta^{(k)}-\psi)^\top x^{(i)})}{\sum_{j=1}^K \exp( (\theta^{(j)}-\psi)^\top x^{(i)})} \\ = \frac{\exp(\theta^{(k)\top} x^{(i)}) \exp(-\psi^\top x^{(i)})}{\sum_{j=1}^K \exp(\theta^{(j)\top} x^{(i)}) \exp(-\psi^\top x^{(i)})} \\ = \frac{\exp(\theta^{(k)\top} x^{(i)})}{\sum_{j=1}^K \exp(\theta^{(j)\top} x^{(i)})}$$

다시 말하면, 모든 $\theta^{(j)}$에 대해서 벡터 $\psi$를 빼는 것은 hypothesis의 예측 능력을 전혀 변화시키지 않습니다. 이것은 softmax regression의 파라미터가 redundant하다는 것을 보여줍니다. 좀더 정확히 말하자면, 이 softmax 모델은 overparameterized되었다고 말할 수 있습니다. 이것은 곧 데이터에 맞춘 어떠한 hypothesis이든 간에, 여러 파라미터 세팅이 있을 수 있다는 것입니다. 하지만 이들 파라미터 세팅들은 입력 $x$에 대해서 같은 예측을 내놓은 정확히 같은 hypothesis 함수를 갖습니다.

더군다나 cost function $J(\theta)$가 어떤 파라미터 세팅 $(\theta^{(1)}, \theta^{(2)},\ldots, \theta^{(k)})$에서 최소화 되었다고 하였을 때, 어떠한 $\psi$에 대해서도 파라미터 $(\theta^{(1)} - \psi, \theta^{(2)} - \psi,\ldots, \theta^{(k)} - \psi)$ 역시 최소 값을 가지게 됩니다. 따라서 $J(\theta)$를 최소화하는 방법은 유일하지 않습니다. 그럼에도 불구하고 $J(\theta)$는 여전히 convex한 함수이며, 때문에 그래디언트 디센트 또한 지역 최적점 문제(local optima problem)에 빠지지 않습니다. 하지만 Hessian은 singular/non-invertible하기 때문에, Newton’s method를 그대로 사용한다면 numerical problem에 빠지게 됩니다.

만약 $\psi = \theta^{(K)}$로 사용한다면, $\theta^{(K)}$는 $\theta^{(K)} - \psi = \vec{0}$로 변경되어 hypothesis에 영향을 주지 않으면서도 모든 파라미터가 0이 되어버립니다. 때문에 hypothesis의 표현력을 잃지 않으면서도 특정한 요소나 벡터를 “제거”할 수 있게 됩니다. 이러한 경우 당연히 $\theta^{(K)} = \vec{0}$으로 사용하게 되면 $(\theta^{(1)}, \theta^{(2)},\ldots, \theta^{(K)}), \theta^{(k)} \in \Re^{n}$인 $K\cdot n$개의 파라미터 대신 남은 $(K-1) \cdot n$에 대해서만 최적화가 이루어지게 됩니다.

Relationship to Logistic Regression

$K = 2$인 특별한 경우 softmax regression은 logistic gression문제로 축소시킬 수 있습니다. 이것은 softmax regression의 logistic regression의 일반화된 버전이라는 것을 보여주는 예입니다. $K=2$인 경우, softmax regression의 hypothesis의 출력은 아래와 같습니다.

$$h_\theta(x) = \frac{1}{ \exp(\theta^{(1)\top}x) + \exp( \theta^{(2)\top} x^{(i)} ) } \begin{bmatrix} \exp( \theta^{(1)\top} x ) \\ \exp( \theta^{(2)\top} x ) \end{bmatrix}$$

여기서 hypothesis가 overparameterized한다는 사실을 이용하여 $\psi = \theta^{(2)}$로 설정하여 각 파라미터에서 빼면,

$$h(x) = \frac{1}{ \exp( (\theta^{(1)}-\theta^{(2)})^\top x^{(i)} ) + \exp(\vec{0}^\top x) } \begin{bmatrix} \exp( (\theta^{(1)}-\theta^{(2)})^\top x ) \exp( \vec{0}^\top x ) \\ \end{bmatrix} \\ = \begin{bmatrix} \frac{1}{ 1 + \exp( (\theta^{(1)}-\theta^{(2)})^\top x^{(i)} ) } \\ \frac{\exp( (\theta^{(1)}-\theta^{(2)})^\top x )}{ 1 + \exp( (\theta^{(1)}-\theta^{(2)})^\top x^{(i)} ) } \end{bmatrix} \\ = \begin{bmatrix} \frac{1}{ 1 + \exp( (\theta^{(1)}-\theta^{(2)})^\top x^{(i)} ) } \\ 1 - \frac{1}{ 1 + \exp( (\theta^{(1)}-\theta^{(2)})^\top x^{(i)} ) } \\ \end{bmatrix}$$

따라서 $\theta^{(2)}-\theta^{(1)}$을 하나의 파라미터 벡터 $\theta`$로 치환하면, softmax regression은 한 클래스에 대해서 $\frac{1}{ 1 + \exp(- (\theta')^\top x^{(i)} ) }$로 확률을 계산하게 되고, 나머지 한 클래스는 $1-\frac{1}{ 1 + \exp(- (\theta')^\top x^{(i)} ) }$가 됩니다. 이는 결국 logistic regression과 같은 결과입니다.

Exercise 1C

ex1c_softmax.m 파일에서 시작하면 됩니다. 연습문제 1B에서와 같이 MNIST의 손글씨를 분류하는 문제를 풀어볼텐데 이번에는 10자리의 숫자를 모두 분류할 것입니다.

앞에서 배운대로 cost function과 그 그래디언트를 softmax_regression_vec.m에 작성하면 됩니다. for-loop를 이용해서 작성해도 괜찮지만 속도가 많이 느리다는 것을 깨닫게 될 것입니다. 따라서 벡터화된 코드로 작성하기를 권장합니다.

그래디언트를 계산한 후에는 마지막에 $g=g(:)$로 전체를 하나의 벡터로 만들어주는 것을 잊지마세요.