Classification 방법 중 Discriminant analysis에 대해 공부한 내용이다.
Classify를 하는 방법에는 다음과 같이 2가지 방법이 있다.
\(x\)라는 data가 있을 때, 어떤 \(y\) class에 속하는지 확률 분포 \(p(y|x)\)를 예측하는 것이다.
- Generative Classifier: likelihood인 \(p(x|y)\)와 prior distribution인 \(p(y)\)를 추정하여 posterior distribution인 \(p(y|x)\)를 예측하는 것이다. 여기서 알고자 하는 posterior distribution은 신만이 알고 있는 분포라고도 한다.
- 예시로 Bayes classifier가 있으며, Discriminant Analysis가 그 방법이다.
- Discriminative Classifier: \(p(y|x)\)를 직접 예측하는 방식이다.
- 저번 주에 공부한 Logistic regression이 예시이다.
Bayes Rule
posterior distribution을 구하기 위해 likelihood와 Prior을 구하는 것이다.
예를 들어 어떤 환자가 병원에 왔을 때 질병이 있는지 판단하고 있다고 해보자.
병이 있다/없다는 \(Y\)에 해당하고 어떤 환자 자체는 \(X\)에 해당한다.
어떤 환자 \(X\)가 있을 때, 병이 있는지 없는지 \(Y\)를 예측하기 위해서 먼저 병이 있고 없을 때의 환자가 어떤 특징을 가지는 likelihood를 구한다.
그리고 병이 걸릴 확률, 안 걸릴 확률인 prior를 곱해준다.
여기서 prior은 기본적으로 알려진, 그냥 이 병에 대해 원래 어느 정도 걸리는지에 대한 확률인 것이다.
\(P(X=x)\)에 대해서도 알 수 있으면 좋겠지만, 알 수없으며 실제로 확률 계산할 때는 소거돼서 자세히는 몰라도 될 것 같다.
나도 잘 모른다.
Discriminant Analysis
generative classifier인 Discriminant Analysis에 대해 자세히 알아보겠다.
앞선 것들과 똑같이 입력 \(x\)에 대해 출력 \(y\)를 예측하는 함수를 추정하는 것이다.
즉 bayes classifier는 risk function을 최소화하는 모델이다.
여기서 risk function은 일단 생략하고 정리한 것에서부터 유도를 해보고자 한다.
그 식을 정리하면
$$ f^*(x) = \operatorname{sign} \left( \log \frac{ p(\mathbf{x} = x \mid \mathbf{y} = 1) p(\mathbf{y} = 1) } { p(\mathbf{x} = x \mid \mathbf{y} = -1) p(\mathbf{y} = -1) } \right) $$
$$ = \operatorname{sign} \left( \log \frac{ \mathcal{N}(\mu_1, \sigma_1) \cdot \alpha } { \mathcal{N}(\mu_{-1}, \sigma_{-1}) \cdot (1 - \alpha) } \right) $$
이다.
sign 함수는 값이 0보다 크면 1을 반환하고 0보다 작으면 -1을 반환한다.
따라서, 분자의 확률이 더 높으면 1을 반환하고 분모의 확률이 더 높으면 음수이기 때문에 -1을 반환한다.
likelihood를 \( \mathcal{N}(\mu_{-1}, \sigma_{-1}) \), \( \mathcal{N}(\mu_{1}, \sigma_{1}) \)인 정규분포로 가정할 수 있다.
많은 분포가 정규분포를 따르기 때문에 이와 같이 가정하는 듯하다.
실제 분포가 이와 같을 때
이런 식으로 추정할 수 있다.
\( \mathcal{N}(\mu_{-1}, \sigma_{-1}) \), \( \mathcal{N}(\mu_{1}, \sigma_{1}) \)에서 \(\mu_{-1}\)과 \(\mu_{1}\)을 추정해야 하는데 이는 MLE를 이용하여 추정하였다.
$$ = \log \prod_{i: y_i=1} p(\mathbf{x}_i \mid y_i) \prod_{j: y_j=-1} p(\mathbf{x}_j \mid y_j) $$
$$ = \sum_{i: y_i=1} \log p(\mathbf{x}_i \mid y_i) + \sum_{j: y_j=-1} \log p(\mathbf{x}_j \mid y_j) $$
$$ = \sum_{i: y_i=1} \log \frac{1}{\sigma_1 \sqrt{2\pi}} - \sum_{i: y_i=1} \frac{(x_i - \mu_1)^2}{2\sigma_1^2} $$
$$ + \sum_{i: y_i=-1} \log \frac{1}{\sigma_{-1} \sqrt{2\pi}} - \sum_{i: y_i=-1} \frac{(x_i - \mu_{-1})^2}{2\sigma_{-1}^2} $$
이 식을 각각 \(\mu_1, \mu_{-1}, \sigma_1, \sigma_{-1}\)에 대해 미분하여 0이 되게 하는 값을 찾는다.
$$ \sum_{i: y_i=1} (x_i - \mu_1)^2 = 0 \quad\Rightarrow\quad \frac{n_1}{\sigma_1} = \frac{1}{\sigma_1^3} \sum_{i: y_i=1} (x_i - \mu_1)^2 $$
즉, 관측 데이터의 평균과 분산이 MLE 값이 된다.
모델링해야 하는 \(f^*(x)\)에 MLE 값을 대입하면 모델이 만들어지는 것이다.
최종적으로 다음과 같은 모델을 만들 수 있다.
$$ f^*(x) = \operatorname{sign} \left( -\frac{1}{2} \log \frac{\sigma_1^2}{\sigma_{-1}^2} - \frac{(x - \mu_1)^2}{2\sigma_1^2} + \frac{(x - \mu_{-1})^2}{2\sigma_{-1}^2} + \log \frac{\alpha}{1 - \alpha} \right) $$
Linear Discriminant Analysis
최종적으로 모델링한 form에서 distribution에 대한 구체적인 가정을 통해 약간 씩 바뀔 수 있다.
\(\hat{\sigma}_1^2 = \hat{\sigma}_{-1}^2 = \hat{\sigma}^2 \) 일 때 각각 소거하게 되어
$$ \frac{1}{\sigma^2} (\mu_1 - \mu_{-1}) \cdot x - \frac{1}{2\sigma^2} (\mu_1^2 - \mu_{-1}^2) + \log \frac{\alpha}{1 - \alpha} $$
\(x\)에 대해 1차 식이 된다.
Quadratic Discriminant Analysis
\(\hat{\sigma}_1^2 = \hat{\sigma}_{-1}^2\)로 가정하였을 때, 최종적으로 모델링한 함수가 \(x\)에 대해 2차식이다.
Discriminant Analysis를 쓰는 이유?
- Data well-separated일 때: Logistic regression으로 학습할 경우 unstable 하다. Discriminant Analysis는 각각의 분포를 중심으로 학습하기 때문에 well-sepatate 돼있으면 좋다. 반면 Logistic regression은 왔다 갔다 하므로 unstable 하며, 애매한 부분(중간)을 볼 수 없으므로 학습이 잘 안 될 수 있다.
- 적은 수의 dataset에서도 잘 작동한다. logistic regression과 비교했을 때, 비교적 파라미터 수가 단순하기 때문이다.
- LDA의 경우 multi class 문제에서 단순한 선형 모델을 이용하여 효과적으로 구분할 수 있다. 또한 결과를 저 차원에서 시각화를 잘해준다.
Discriminant Score
좀 더 일반화하기 위해 Discriminant score에 대해 알아보자.
이 식도 bayes rule을 이용한 것으로 분모에 있는 식은 모든 class에 동일하게 적용되므로 무시하겠다.
계산의 편의를 위해 분자에 log를 씌우고 다음과 같이 정리했다.
$$ -\frac{(x - \mu_k)^2}{2\sigma^2} = -\frac{1}{2\sigma^2} \left( x^2 - 2x\mu_k + \mu_k^2 \right) = -\frac{x^2}{2\sigma^2} + \frac{x\mu_k}{\sigma^2} - \frac{\mu_k^2}{2\sigma^2}. $$
- \( -\frac{x^2}{2\sigma^2} \) 는 \( k \) 와 무관하므로 \( \arg\max \)에서 무시.
- 따라서 남는 항은 \( \frac{x\mu_k}{\sigma^2} - \frac{\mu_k^2}{2\sigma^2} \) 입니다.
$$ \therefore \log [\pi_k f_k(x)] = \log \pi_k + \underbrace{(\text{공통 항})}_{\text{무시}} + \left(\frac{x\mu_k}{\sigma^2} - \frac{\mu_k^2}{2\sigma^2} \right). $$
결과적으로 \( k \)에 대해 달라지는 항만 모아 쓰면,
$$ \delta_k (x) = \frac{x\mu_k}{\sigma^2} - \frac{\mu_k^2}{2\sigma^2} + \log(\pi_k) $$ 이 된다.
여기서 \(x\)에 대한 일차식이 되는데 그 이유는 \(\sigma_k=\sigma\)로 되기 때문이다.
언제 \(K=1\),\(K=2\)이 되는지 판단해야 하는 것이 목표이다.
그렇기 때문에 \(x\)의 경계를 정해야 한다.
\(K=1\),\(K=2\) 일 때의 스코어가 서로 같다고 놓고 구하면 된다.
즉, 결정 경계 \( x \)는 다음 방정식을 만족해야 한다.
$$ \delta_1 (x) = \delta_2 (x) $$
이를 풀어보자.
$$ x \cdot \frac {\mu_1}{\sigma^2} - \frac{\mu_1^2}{2\sigma^2} + \log (0.5) = x \cdot \frac{\mu_2}{\sigma^2} - \frac{\mu_2^2}{2\sigma^2} + \log (0.5) $$
양변에서 \( \log(0.5) \)를 소거하고 정리하면:
$$ x \cdot \frac{\mu_1}{\sigma^2} - x \cdot \frac{\mu_2}{\sigma^2} = \frac{\mu_1^2}{2\sigma^2} - \frac{\mu_2^2}{2\sigma^2} $$
$$ x (\mu_1 - \mu_2) = \frac{\mu_1^2 - \mu_2^2}{2} $$
$$ x = \frac{\mu_1 + \mu_2}{2}. $$
\(x\)가 경계가 되어 판단을 할 수 있다.
이렇게 discriminant score을 알면 multi-class(multinomial) 문제에 대해서도 서로 같다고 놓고 결정 경계를 찾으면 된다.
Multivariate(feature dim이 2이상)일 경우도 dicriminant score를 이용하여 구할 수 있다.
아까와 똑같다. 차원만 달라질 뿐.
다음과 같이 multivariate gausian distribution을 이용하여 Bayes decision boundaries를 구할 수 있다.
Multinomial(K=3), Multivariate(p=2)인 경우다.
$$ f(x) = \frac{1}{(2\pi)^{p/2} |\mathbf{\Sigma}|^{1/2}} \exp \left( -\frac{1}{2} (x - \mu)^{\top} \mathbf{\Sigma}^{-1} (x - \mu) \right) $$
그래프를 보면 likelilhood의 분포가 타원처럼 생긴다.
이것은 contour이라 하는데 확률 밀도가 동일한 점들인 것이고 이를 통해 Bayes decision boundary를 찾는다.
여기서도 위와 마찬가지로 모든 \(\sigma_k\)가 \(\sigma\)로 같을 때, LDA가 돼 점선인 것처럼 decision boundary를 만든다.
반면 \(\sigma_k\)가 다 다를 때, QDA가 돼 위와 같이 곡선형태의 decision boundary가 생긴다.
단 여기서 covariant matrix의 형태에 따라 원이 될지, 타원이 될지 정해진다.
Type of errors
Misclassification rate은 2.75%((23+252)/10000)이다.
어찌 보면 높은 정확도로 예측해 보인다.
단, 여기서 주의해야 할 점은 data의 size가 매우 skew 돼 있다.
이럴 경우 전부 No라 해도 error가 3.33%(333/10000)밖에 안된다.
더 자세하게 errors를 계산하면, No 중에서는 23/9667=0.2% errors를 가진다.
Yes 중에서는 252/333=75.7% errors를 가진다.
정답이 yes일 경우에는 더 큰 오류를 내는 것을 알 수 있다.
이러한 오류를 각각 False positive rate, False negative rate이라 한다.
예시와 함께 설명해 보면 False positive rate은 실제로 병에 안 걸렸는데 병에 걸렸다고 진단하는 경우이다.
False negative rate는 실제로 병에 걸렸는데 안 걸렸다고 진단하는 것이다.
상황에 따라 더 신경 써서 줄여야 하는 오류가 달라지는 것이다.
위의 예시 같은 경우는 False negative rate를 줄여야 한다.
어떤 식으로 줄일 수 있을까?
확률을 계산할 때, threshold를 변경하는 것이다.
지금까지는 0.5를 기준으로 했다.
- Threshold를 높일 경우: Yes라고 predict 하는 것이 엄격해져, 그 수가 적어진다. 따라서 FPR값이 낮아진다.
- Threshold를 낮출 경우: No라고 predict 하기 어려워지는 것이다. 그럼 대부분 yes라고 할 텐데 그래서 FNR값이 낮아진다.
병원을 예시로 들면 실제로 병에 걸렸을 때, threshold를 낮춰 쉽게 yes라 하면 병에 걸렸다고 예측할 경우가 많아지는 것이다.
결과적으로 좋은 방향으로 갈 수 있는 것이다.
Trade-off 관계를 표현 그래프를 살펴보겠다.
threshold가 줄어들수록 FNR은 감소하는 동시에 overall error와 FPR이 증가하는 것을 알 수 있다.
따라서, 어떤 task인지 어떤 error를 줄이는 것이 더 중요한지를 고려하며 threshold를 지정해야 한다.
ROC Curve
ROC Curve는 이진분류 모델의 성능을 평가할 때 사용하는 그래프이다.
x축을 FPR로 y축을 TPR로 정하여 curve를 그린다.
곡선이 왼쪽 위(0,1) 방향으로 높이 올라갈수록
좋은 모델이다.(낮은 FPR, 높은 TPR)
ROC curve 아래 면적을 AUC라 하는데 1에 가까울수록 성능이 좋은 것이다.
Naive Bayes
확률 기반의 분류 알고리즘으로, feature들이 서로 independent 하다는 가정을 기반으로 한다.
그렇기 때문에 p의 값이(multivariate) 커져도 feature들과 상관관계를 고려하지 않기 때문에 빠르고 계산이 간단하다.
generative model로 bayes theorem을 이용하여 확률을 예측한다.
likelihood에 대해 가우시안 분포를 따른다고 가정하고 log를 씌워 덧셈의 형태로 전환한다.
이 방법은 현실적이지 않은 가정이 있어 성능이 낮을 것이라 생각되지만 생각보다 괜찮은 분류성능을 달성한다.