끄적끄적

Bayes' theorem

 Conditional probability를 활용하여 $P(A\cap B)$ 를 쓰면 다음과 같다.

$P(A\cap B) = P(A \vert B)P(B) = P(B \vert A)P(A)$

위 수식의 의미는, 사건 A와 사건 B가 함께 일어날 확률은 사건 A가 일어나고 사건 B가 일어나거나, 사건 B가 일어나고 사건 A가 일어날 확률로 쓸 수 있다는 것이다.

 위의 수식을 이용하면 $P(A \vert B)$를 다음과 같이 쓸 수 있다.

$P(A \vert B) = \frac{P(B \vert A)P(A)}{P(B)}$

이 수식을 베이즈 정리라 한다.

용어 정리

위 수식을 활용하기 위해 A를 가설, B를 데이터라 하면,

$P(hypothesis \vert data) = \frac{P(data \vert hypothesis)P(hypothesis)}{P(data)}$

라 쓸 수 있다.

$P(hypothesis \vert data)$ : posterior probability(사후확률)라 하며, 주어진 데이터 하에 가설이 참일 확률을 의미한다.

$P(data \vert hypothesis)$ : 가설 하의 데이터의 likelihood이다.

$P(data)$ : marginal probability

$P(hypothesis)$ : Prior probability(사전확률)로 가설에 대한 초기 믿음을 나타낸다.

Naive Bayes' Classifier

 입력 feature $\vec{x}$를 통해 class $y$를 유추하는 모델을 생각해보면 베이즈 정리에 의해 다음과 같이 쓸 수 있다.

$P(y_j \vert \vec{x}) = \frac{P(\vec{x} \vert y_j)P(y_j)}{P(y_j}$

우항의 분모를 다시 쓰면,

$P(\vec{x} \vert y_j)P(y_j) = P(x_1 \vert x_1, \dots, x_n, y_j)$

이며, $x_i$가 서로 독립이라는 가정을 하면(강력한 가정이며 이 때문에 Naive Bayes' classifier이다),

$P(\vec{x} \vert y_j)P(y_j) = P(x_1 \vert y_j)P(x_2 \vert y_j) \dots P(x_n \vert y_j)P(y_j) = \prod_k P(x_k \vert y_j)P(y_j)$

라 쓸 수 있다.

 이 때, 주어진 feature $\vec{x}$에 대한 예측 클래스 $\hat{y}$ 는 다음과 같다.

$\hat{y} = \underset{y_j}{argmax} \prod_k P(x_k \vert y_j)P(y_j)$

Laplace Smoothing

 위 모형의 문제는 샘플의 개수가 적을 때 $P(x_i \vert y_j) = 0$ 이 생기는 문제가 발생할 수 있다. 즉, 데이터 기반으로 likelihood를 계산하다보니 등장하지 않은 데이터에 대해서는 class $y_j$일 확률이 아예 없다고 하는 강력한 모형이 만들어지는 것이다. 이러한 강력한 모형은 바람직 하지 않으므로

$P(x_i \vert y_j) = \frac{\mbox{# number of }x_i + cP(x_i}{\mbox{# of } y_j + c}$

와 같이, 아주 작은 값을 분모와 분자에 더해줘 확률이 0이 되는 것을 피한다.

Application with Iris dataset

 붓꽃 분류 데이터를 활용하여 실습해 보겠습니다. 해당 데이터에서 feature는 4개로 ['sepal length', 'sepal width', 'petal length', 'petal width'] 이고, class는 [0,1,2] 세개로 주어집니다.

 주어진 데이터에 맞게 각 확률을 구해주면 됩니다. 또한, 계산의 편의성을 위해 모든 인풋값을 반올림하여 사용하였습니다. 연속값을 사용하는 경우에는 특정 구간의 데이터 개수를 세면 됩니다.

 Prior probability : 모든 클래스의 데이터가 각 50개씩 주어지므로 1/3으로 했습니다.

 Marginal probability : $[x_1, x_2, x_3, x_4]$ 의 개수를 센 후, 전체 개수로 나누어주면 각 인풋 데이터에 맞는 Marginal probability가 됩니다.

 Likelihood : $P(x_i \vert y)$ 의 개수를 세어 확률을 측정합니다.

 코드는 깃허브를 참조해주세요.

 Github link

 학습과 테스트 데이터는 8:2로 나누었으며, 30개의 테스트셋에 대해 약 93%의 정확도를 보이는 것을 확인할 수 있습니다.

요약

 LMS 알고리즘은 가장 유명한 학습법 중 하나이며, LMS 알고리즘은 성능이 좋으면서도, 빠르고 효율적이며 코드 짜기도 쉽다. 본 포스트에서는 선형회귀만을 다룹니다.

Adpative Filter

 LMS 알고리즘은 adaptive filter라고 할 수 있으며 filtering process와 adaptive process가 합쳐져 있다. $w$와 i번째 샘플 $x(i)$로부터 예상된 결과가 $y(i)$라 할때, $y(i)$와 실제 정답 $d(i)$를 비교함으로써 error $e(i)$를 얻는 과정이 filtering process이고, $e(i)$로부터 $w$를 적절하게 수정해 나가는 과정이 adaptive process이다.

 어떤 이상적인 분류기의 모델로서 optimal solution $w*$가 있다고 할때, 실제 $w*$는 알 수가 없으므로, 우리의 목표는 가지고 있는 sample들로부터 error를 가장 작게 만드는 $w$를 찾는 것이다. $w$에 관한 error를 $\mathcal{E}$라 하면, $\mathcal{E}(w*) <= \mathcal{E}(w)$ 일 것이며, $w*$가 optimal solution일 조건은 $\triangledown\mathcal{E}(w*) = 0$ 이다.

 $w$가 $w*$에 가까워지도록 하는 adaptive filter는 iterative descent의 방식으로 진행된다. 즉 i번째 iteration에서의 error를 $\mathcal{E}(w(n))$라 하면 $\mathcal{E}(w(n+1)) < \mathcal{E}(w(n))$가 된다.

Steepest Decsent Algorithm

 말그대로 가장 가파른 곳으로 내려가는 알고리즘으로, $w$에 대한 에러 $\mathcal{E}(w)$의 경사가 가장 가파른 곳으로 내려가는 알고리즘으로, 

 $w(n+1) = w(n) - \eta$\triangledown\mathcal{E}(w)$

 $\triangle w(n) = w(n+1) = w(n) = - \eta$\triangledown\mathcal{E}(w) = -\eta g(n)$

가 된다. 이러한 방식을 통해 $w$가 $w*$에 가까워지는 이유는 다음과 같이 error를 테일러 전개 함으로써 알 수 있다.

 $\mathcal{E}(w(n+1)) = \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \mathcal{O}((\triangle w(n))^2) \simeq \mathcal{E}(w(n)) - \eta g^T(n)g(n) = \mathcal{E}(w(n)) - \eta \parallel g(n) \parallel^2$

 $\therefore \mathcal{E}(w(n+1)) < \mathcal{E}(w(n))$

Newton's Method

 이번에는 에러 함수를 이차항까지 테일러전개를 하면 아래와 같다.

 $\triangle(\mathcal{E}(w(n))) = \mathcal{E}(w(n+1)) - \mathcal{E}(w(n))$

        $= \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \frac{1}{2} \triangledown^2 \mathcal{E}(w(n))^T (\triangle w(n))^2 + \mathcal{O}((\triangle w(n))^3) - \mathcal{E}(w(n))$

        $= g^T(n) \triangle w(n) + \frac{1}{2} \triangle w^T(n) H(n) \triangle w(n)$, H(n)은 헤세 행렬 ( H(n) = \triangledown^2 \mathcal{E}(w(n))

 즉, $g(n) + H(n) \triangle w(n) =0$ 일때 에러의 차가 최소가 된다.

$\therefore w(n+1) = w(n) - H^{-1}(n)g(n)$

Gauss-Newton Method

 Todo

The Least Mean Square Algorithm

 에러 함수를 다음과 같이 정의하면

 $\mathcal{E}(w) = \frac{1}{2} e^2(n)$,

 gradient vector는 다음과 같다.

 $g(n) = \frac{\partial \mathcal{E}(w)}{\partial w} = e(n) \frac{\partial e(n)}{\partial w} = - e(n)x(n)$

 여기서 Steepest Descent를 활용하여 $w$를 업데이트 시키면 다음과 같다.

 $w(n+1) = w(n) + \eta x(n)e(n)$

LMS 알고리즘은 environment에 대한 정보가 하나도 없어도 적용이 가능하다.

코드로 구현한 내용은 전에 작성한 포스트에 있습니다.

요약

 Bayes' theorem을 이용한 Maximum a posteriori estmation(MAP)을 이용한 모델과 MAP과 least mean-square estimation 사이의 관계에 대하여 다룹니다.

Bayes' theorem

 Regressor $x$가 environment $w$와 상호작용하여 response $d$가 관측되었다고 할 때, 확률론을 이용하면 environment $w$에 대한 조건부 확률 $p_{W,D \vert X}(w,d,x)$는 아래와 같이 쓸 수 있다. 

 $p_{W,D \vert X}(w,d,x) = p_{W \vert D,X}(w \vert d,x)p_D(d) =p_{D \vert W,X}(d \vert w,x)p_W(w)$

 또한, 위의 식을 이용하면 조건부 확률 $p_{W \vert D,X}(w \vert d,x)$을 아래와 같이 쓸 수 있는데, 이것이 Bayes' theorem이다.

 $p_{W \vert D,X}(w \vert d,x) = \frac{p_{D \vert W,X}(d \vert w,x)p_W(w)}{p_D(d)}$

 즉, Bayes' theorem이란, $w$에 대한 조건부 확률을 $w$에 대한 사전확률(믿음)과 관측값 $d$에 대한 조건부 확률을 이용하여 나타내는 것이다.

용어정리

 Observation density : $p_{D \vert W,X}(d \vert w,x)$로, 주어진 환경 $w$하에서 stimuli $x$에 대하여 response $d$가 관측될 확률을 나타낸다.

 Prior : $p_W(w)$로, 관측전의 $w$에 대한 information을 나타내며 앞으로는 $\pi(w)$라고 쓰겠습니다.

 Posterior density : $p_{W \vert D,X}(w \vert d,x)$로, 관측 후의 $w$에 대한 조건부 확률로, 앞으로는 $\pi(w \vert d,x)$로 쓰겠습니다.

 Evidence : $p_D(d)$로, $d$에 대한 통계 분석에 의한 information을 나타낸다.

Maximum likelihood estimation(ML)과 Maximum a posteriori estimation(MAP)

 Likelihood function $l(w \vert d,x)는

 $l(w \vert d,x) = p_{D \vert W,X}(d \vert w,x)$,

 즉, observation density라고 할 수 있고, 위의 Bayes' theorem을 통해 posteriori $\pi(w \vert d,x)$는 다음과 같이 쓸 수 있다.

 $\pi(w \vert d,x) \propto l(w \vert d,x)\pi(w)$

 따라서 ML estimation of $w$ $w_{ML}$과 MAP estimation of $w$ $w_{MAP}$은 아래와 같이 쓸 수 있다.

 $w_{ML} = \underset{w}{\operatorname{argmax}}l(w \vert d,x)$

 $w_{MAP} = \underset{w}{\operatorname{argmax}}\pi(w \vert d,x)$

 둘의 차이점을 살펴보면, $w_{ML}$의 경우에는 $w$에 대한 prior를 고려하지 않는다. 또한 많은 경우에 $\pi(w \vert d,x)$ 값 자체보다는 $log(\pi(w \vert d,x))$ 값이 편리한 경우가 많으므로, 계산상의 편의를 위하여 앞으로는 $w_{MAP} = \underset{w}{\operatorname{argmax}}log(\pi(w \vert d,x))$를 사용한다. 

Parameter estimation in a Gaussian Environment

 Gaussian environment에서의 MAP 추정은 우리에게 친숙한 least-square estimation과 연관되는데, 이를 보이겠다.

 이를 보이기 위해서는 세가지 가정이 필요한데, 먼저 N개의 sample data $({\mathbf{x}_i,d_i})_{i=1}^N$은 i.i.d이다. 또한, $d_i = w^T \mathbf{x}_i + \epsilon_i$ 일 때, error $\epsilon_i$ 역시 Gaussian 분포를 따른다. 

 $p_E(\epsilon_i) = \frac{1}{\sqrt{2 \pi} \sigma}exp(-\frac{\epsilon_i^2}{2 \sigma^2})$

 또한 $\mathbf{w}$가 길이 M인 벡터라 할 때, M개의 각각의 요소들은 stationary하다. 여기서는 각각의 요소들이 독립적이며 평균이 0이고, 분산이 $\sigma_w^2$라 가정한다.

 $\pi(w_k) = \frac{1}{\sqrt{2 \pi} \sigma_w}exp(-\frac{w_k^2}{2 \sigma_w^2})$

 위의 가정들을 종합해보면, $\mathbb{E}[D_i] = \mathbf{w}^T \mathbf{x}_i, var[D_i] = \sigma^2$ 가 된다. 이를 가지고 liklihood function을 쓰면 아래와 같다. 

 $ㅣ(\mathbf{w} \vert d_i, x_i) = \Pi_{i=1}^N l(\mathbf{w} \vert d_i, \mathbf{x}_i) = \frac{1}{^\sqrt{2 \pi} \sigma)^N} exp(-\frac{1}{2 \sigma^2}\sum_i (d_i - w^T \mathbf{x}_i))$

 Prior $\pi(\mathbf{w})$의 경우, 앞에서 $w$의 각각의 요소들이 i.i.d임을 가정했으므로 다음과 같이 쓸 수 있다.

$\pi(w) = \Pi_{k=1}^M \pi(w_k) = \frac{1}{(\sqrt{2 \pi} \sigma_w)^M}exp(\frac{1}{2\sigma_w^2}\sum_k w_k^2) = \frac{1}{(\sqrt{2 \pi} \sigma_w)^M}exp(\frac{1}{2\sigma_w^2}\lVert \mathbf{w} \rVert^2)$

 Priori와 likelihood 함수를 모두 구했으므로, Posteiori는 다음과 같이 쓸 수 있다.

 $\pi(w \vert d,x) \propto exp[-\frac{1}{\sqrt{2 \pi} \sigma}\sum_i(d_i - \mathbf{w}^T \mathbf{w}_i)^2 - \frac{1}{\sqrt{2 \pi} \sigma_w}\lVert \mathbf{w} \rVert^2 ]$

 $w_{MAP} = \underset{w}{\operatorname{argmax}}[-\frac{1}{\sqrt{2 \pi}}\sum_i(d_i - \mathbf{w}^T \mathbf{w}_i)^2 - \frac{\lambda}{\sqrt{2 \pi}}\lVert \mathbf{w} \rVert^2], \lambda = \frac{\sigma^2}{\sigma_w^2}$

 여기서 argmax 함수 안의 첫 항은 least-square estimation 에서 쓰는 quadratic error function이며, 뒤의 항은 regularization이라 할 수 있다. 즉, 가우시안 환경에서의 MAP 추정은 regularized least-square 추정이 된다. 또한 $\lambda \rightarrow 0 (\sigma_w \rightarrow \infty)$인 경우, 즉, $w$의 분포가 uniform 분포인 경우에는 MAP 추정이 ML 추정과 같아진다.

* Neural Networks and Learning Machines -Simon Haykin 의 책을 스터디한 내용을 정리한 것입니다.