Naive Bayes에서 Generative Model까지 — 가정이 틀려도 잘 작동하는 이유

Naive Bayes의 핵심 가정은 현실 데이터에서 거의 항상 거짓이다. 키와 체중은 강하게 상관되고, 텍스트에서 “머신”과 “러닝”은 함께 등장한다. 그런데 이 모델은 여전히 spam filter와 text classification의 강력한 baseline으로 살아남는다. 왜인가? 그리고 이 “왜”를 파고들면, 분류 문제 전체를 관통하는 하나의 통찰에 다다른다 — 분류는 확률 추정이 아니라 순위 비교다.

조건부 독립 가정의 실제 의미

Naive Bayes의 핵심은 클래스 $y$가 주어졌을 때 feature들이 독립이라는 가정이다.

$P(x \mid y) = \prod_{j=1}^p P(x_j \mid y)$

이 가정 덕분에 $p$차원 joint distribution을 추정하는 문제가 $p$개의 1차원 문제로 분해된다. MAP 분류기는 다음과 같이 쓸 수 있다.

$\hat{y}(x) = \arg\max_{k} \, P(y=k) \prod_{j=1}^p P(x_j \mid y=k)$

계산 비용은 학습 $O(np)$, 예측 $O(Kp)$다. SVM의 $O(n^2)$이나 Logistic Regression의 반복 Newton step과 비교하면 압도적으로 빠르다.

가정이 명백히 거짓이어도 모델이 작동하는 이유는 Domingos & Pazzani (1997)의 분석이 명확히 설명한다. 분류기가 옳은 결정을 내리려면 진짜 $P(y|x)$를 정확히 추정할 필요가 없다. 클래스별 posterior의 순위만 보존되면 충분하다. Naive Bayes가 $\hat{P}(y=1|x) = 0.95$로 과신해도, 진짜 값이 $0.6$이어도, $0.5$를 넘는 한 결정은 같다. 확률 추정은 틀렸지만 분류는 맞는다.

가정의 강도 스펙트럼 — GNB, LDA, QDA

Naive Bayes를 출발점으로 놓으면, 공분산 구조에 대한 가정을 조금씩 풀어가며 모델의 스펙트럼이 드러난다.

모든 모델은 클래스 likelihood를 다변수 Gaussian으로 가정한다.

$P(x \mid y=k) = \mathcal{N}(x;\, \mu_k,\, \Sigma_k)$

차이는 $\Sigma_k$의 구조다.

• Gaussian NB: $\Sigma_k$가 대각, 클래스마다 다름. Feature 간 공분산을 0으로 강제한다.
• LDA: 모든 클래스가 공분산 $\Sigma$를 공유한다. 결정경계 유도 시 이차 항이 약분되어 선형 경계가 된다.
• QDA: 클래스마다 full covariance. 이차 항이 남아 이차 경계(타원·쌍곡선)가 된다.

파라미터 수 관점에서 보면 bias-variance tradeoff가 바로 보인다. GNB는 $O(Kp)$, LDA는 $O(Kp + p^2)$, QDA는 $O(Kp^2)$다. QDA가 가장 표현력이 크지만 데이터를 가장 많이 필요로 한다. 실험에서 $n \ll p^2$이면 GNB나 LDA가 안정적이고, QDA는 공분산 추정이 ill-conditioned해진다.

Fisher Discriminant — 분류를 차원축소로 보기

LDA를 분류기가 아닌 차원축소 도구로 재해석하면 Fisher의 공식이 나온다. 좋은 projection $w^\top x$는 같은 클래스 점들을 뭉치게 하고 다른 클래스 점들을 분리해야 한다. Fisher discriminant ratio는 이 직관을 수식으로 쓴 것이다.

$J(w) = \frac{w^\top S_B w}{w^\top S_W w}$

$S_B$는 between-class scatter(클래스 평균들 사이의 분산), $S_W$는 within-class scatter(클래스 내 분산의 합)다. $J(w)$의 최대화는 일반화 고유값 문제 $S_B w = \lambda S_W w$와 동치다.

$K$개 클래스에서 $S_B$의 rank는 최대 $K-1$이다. $\sum_k n_k(\mu_k - \bar{\mu}) = 0$이므로 클래스 평균 편차들이 선형종속이기 때문이다. 이것이 LDA의 projection 차원이 정확히 $K-1$인 이유다. Iris 3클래스 데이터를 2D로 완벽히 시각화할 수 있는 수학적 이유가 여기 있다.

PCA와의 대조가 이 관점에서 명확해진다. PCA는 레이블을 무시하고 전체 분산이 최대인 방향을 찾는다. LDA는 레이블을 활용해 클래스 분리가 최대인 방향을 찾는다. 같은 데이터에서 클래스 분리 정보가 분산이 작은 방향에 숨어 있으면 PCA는 그 정보를 버린다. 실험에서 1D projection 분류 정확도가 PCA 방향에서 58%, LDA 방향에서 100%가 나오는 케이스가 바로 이 상황이다.

Generative vs Discriminative — 데이터 크기별 교차점

여기서 더 깊은 질문이 나온다. NB(generative)와 Logistic Regression(discriminative)은 같은 선형 결정경계를 만든다. 그런데 왜 성능이 다른가?

NB는 $P(x, y)$를 학습한다. LR은 $P(y|x)$를 직접 학습한다. NB가 더 어려운 문제를 푸는 것이다.

Ng & Jordan (2001)은 이 차이가 만드는 수렴 속도 차이를 정리했다.

• NB의 generalization error: $\epsilon_\infty^{\text{NB}} + O(\sqrt{\log p / n})$
• LR의 generalization error: $\epsilon_\infty^{\text{LR}} + O(\sqrt{p / n})$

NB는 각 feature를 독립적으로 추정하므로 union bound로 $O(\log p / n)$에 수렴한다. LR은 $p$차원 joint 추정이므로 $O(\sqrt{p/n})$으로 느리다. 작은 $n$에서는 수렴 속도가 결정적이므로 NB가 우세하다.

반대로 $n$이 충분히 크면 점근 오차가 결정적이다. NB의 모델 가정(조건부 독립)이 현실에서 깨질 때 $\epsilon_\infty^{\text{NB}} > \epsilon_\infty^{\text{LR}}$이므로 LR이 우세해진다. 실험적으로 이 교차점은 $n^* \approx 30 \cdot p$ 부근에서 나타난다.

트레이드오프

각 모델이 가진 가정과 그 대가를 정리하면 다음과 같다.

Generative model이 discriminative에 비해 갖는 추가 능력은 $P(x, y)$를 학습한다는 사실에서 온다. Sampling($x \sim P(x|y)$), missing feature marginalization, unlabeled data 활용(semi-supervised), anomaly detection($P(x)$가 낮으면 outlier)이 모두 여기서 나온다. Discriminative는 $P(y|x)$만 알므로 이런 능력이 원천적으로 없다.

정리

• NB의 조건부 독립 가정은 현실에서 항상 깨지지만, 분류에는 확률 정확성이 아닌 클래스별 순위만 필요하다. 가정이 틀려도 분류가 작동하는 이유다.
• GNB → LDA → QDA는 공분산 가정을 점차 완화하는 스펙트럼이다. 가정이 강할수록 파라미터가 적고 수렴이 빠르지만 표현력이 제한된다.
• Fisher LDA는 같은 모델을 차원축소 관점으로 보면 도출된다. $K-1$ 차원이 이론적 상한이다.
• Ng & Jordan의 분석: Generative(NB)는 $O(\sqrt{\log p / n})$, Discriminative(LR)는 $O(\sqrt{p/n})$으로 수렴한다. 교차점 $n^* \approx 30p$ 기준으로 모델을 선택하는 것이 원칙적 접근이다.

1936년 Fisher의 discriminant ratio와 1997년 Domingos-P