[PRML] Chapter 1. Introduction (3) - 차원의 저주, 결정 이론

본 글은 책 ‘패턴 인식과 머신 러닝’의 국내 출판본을 바탕으로 작성되었습니다.

1.4 차원의 저주

앞서 살펴본 다항식 곡선 피팅에서는 입력 변수가 $x$ 하나였지만 실제 사례에서는 많은 종류의 입력 변수로 구성된 고차원의 공간을 다뤄야 합니다.

계산량의 문제

Figure 1.19 오일 흐름 데이터의 산포도 ($x_6, x_7$)

예시로 들 데이터는 오일, 물, 가스가 혼합되어 운반되는 송유관에서 측정된 데이터입니다. 세 가지 원료는 또 각각 세 가지 방식으로 송유관 안에 혼합되어 있을 수 있습니다. 각각의 방식 내의 세 가지 성분의 배합도 다릅니다. 각 데이터는 12차원의 입력 벡터로 표현됩니다. 위 사진은 그 중 $x_6$과 $x_7$을 표현한 산포도입니다. 각 데이터의 색상은 해당 데이터가 어떤 혼합 방식인지를 의미합니다.

Figure 1.20 입력 공간을 단순히 나눠서 예측한 접근법

위 그림과 같이 단순한 접근법을 사용할 수 있습니다. 공간을 나눈 뒤 각 영역에서 가장 많이 차지하고 있는 label로 분류하는 것입니다. 이 접근법은 여러가지 문제가 있을 수 있습니다. 가장 큰 문제는 입력 변수가 더 많은 경우에 발생합니다.

Figure 1.21 차원의 저주

입력 변수가 많을수록 구분에 필요한 칸의 숫자가 기하급수적으로 늘어나게 됩니다. 칸이 많아진다면 각 칸이 비어있지 않도록 더 많은 데이터가 필요하게 됩니다. 따라서 변수의 종류가 많으면 이 방법을 사용하기 힘듭니다. 고차원 공간에서의 문제점을 더 자세히 알아보겠습니다. 앞에서 살펴본 다항식 곡선 피팅 문제에 적용해보겠습니다. $D$개의 입력 변수가 있을 경우 3차 계수까지의 다항식의 형태는 다음과 같습니다.

\[y(\mathbf{x},\mathbf{w}) = w_0 + \sum^D_{i=1}w_ix_i + \sum^D_{i=1}\sum^D_{j=1}w_{ij}x_ix_j + \sum^D_{i=1}\sum^D_{j=1}\sum^D_{k=1}w_{ijk}x_ix_jx_k\]

$D$가 증가함에 따라 독립적인 계수의 숫자는 $D^3$에 비례하여 증가합니다. $M$차 다항식의 경우 $D^M$에 비례하여 증가합니다.

직관의 문제

우리가 지니고 있는 기하학적 직관이 고차원에서는 매우 다르게 적용할 수 있다는 문제점도 있습니다. 예로 $D$차원의 반지름 $r$ = 1인 구체에서 $r=1-\epsilon$에서 $r=1$ 사이에 존재하는 부피의 비율을 계산해보겠습니다. $D$차원에서 반지름 $r$을 가진 구체의 부피는 $r^D$에 비례하여 증가합니다.

\[V_D(r) = K_DrD\]

여기서 상수 $K_D$는 $D$에만 종속되어 있습니다. 따라서 위에서 언급된 비율은 다음과 같습니다.

\[\frac{V_D(1)-V_D(1-\epsilon)}{V_D(1)} = 1 - (1 - \epsilon)^D\]

Figure 1.22 차원값 $D$에 대해 $r = 1 - \epsilon$에서 $r=1$사이에 존재하는 부피의 비율

이처럼 큰 $D$의 경우 작은 $\epsilon$ 값에 대해서도 비율이 1에 가깝습니다. 고차원의 공간에서는 구체 부피의 대부분이 표면 근처의 얇은 껍질에 집중되어 있는 것인데, 직관으로는 이해하기 힘든 결과입니다. 고차원 공간에서의 가우시안 분포에 대해 문제를 확장시켜 생각해볼 수 있습니다. 데카르트 좌표에서 극좌표로 변환한 뒤에 방향성 변수들을 적분시켜 없애면 반지름 $r$에 대한 함수 $p(r)$로 표현되는 밀도 함수를 구할 수 있게 되며, 이 분포의 그래프를 다양한 $D$값에 대해 그려보겠습니다.

Figure 1.23 차원값 $D$에 대해 반지름 $r$의 확률 분포에 대한 가우시안 분포

이처럼 큰 $D$값에 대해서는 가우시안 확률 질량이 얇은 겉껍질에 집중됩니다. 저차원 공간에서 발전시킨 아이디어들이 반드시 고차원에서 적용되지는 않습니다.

현실에서의 적용

차원의 저주는 중요한 문제점을 시사하지만 고차원 입력값에 대해 사용할 수 있는 효과적인 패턴 인식 테크닉이 없는 것은 아닙니다. 그 이유로는 크게 두 가지가 있습니다. 첫째로 실제 세계의 고차원 데이터들의 경우 유의미한 차원의 수는 제한적입니다. 둘째로 실제 세계의 데이터는 보통 입력값에서 작은 변화가 일어나면 표적값에서도 작은 변화가 일어나게 되고, 지역 보간법 등의 테크닉을 적용하여 입력 변수에 대한 타깃 변수를 예측할 수 있습니다.

1.5 결정 이론

불확실성이 존재하는 상황에서 의사결정을 내릴 때에 결정 이론의 도움을 받을 수 있습니다. 결합 확률 분포 $p(\mathbf{x},\mathbf{t})$는 변수들의 전체 불확실성을 요약해서 나타내어 줍니다. $p(\mathbf{x},\mathbf{t})$를 찾아내는 것은 추론 inference의 대표적인 예시입니다. 추론은 매우 어려운 문제로, 대부분의 실제 사례에는 $\mathbf{t}$에 대해서 예측하는 것이 더 중요한 문제입니다. 일반적인 추론 문제는 결합 확률 분포 $p(\mathbf{x},\mathcal{C}_k)$ 또는 $p(\mathbf{x},\mathbf{t})$를 결정하는 과정을 포함하고 있습니다. 여기서 $\mathcal{C}_k$는 k번째 클래스를 의미합니다. 해당 상황에 대해 가장 완전하고 확률적인 설명을 알려줄 수 있는 것이 결합 확률 분포입니다. 하지만 우리가 최종적으로 알고 싶은 것은 어떤 클래스 $\mathcal{C}_k$를 선택해야 할지이며 이것이 바로 결정 단계 입니다. 결정 이론을 통해 적절한 확률들로부터 최적의 결정을 내릴 수 있습니다.

우리의 목표는 데이터 $\mathbf{x}$를 구한 후 어떤 클래스로 분류해야 할지 알아내는 것입니다. $\mathbf{x}$가 주어졌을 때 각각의 클래스의 조건부 확률을 알아내고 싶으며 이는 $p(\mathcal{C}_k\vert\mathbf{x})$ 로 표현됩니다. 베이지안 정리를 활용하면 다음과 같이 표현할 수 있습니다.

\[p(\mathcal{C}_k\vert\mathbf{x}) = \frac{p(\mathbf{x}\vert \mathcal{C}_k)p(\mathcal{C}_k)}{p(\mathbf{x})}\]

위의 베이지안 정리에서 사용된 모든 값들은 결합 확률 분포 $p(\mathbf{x},\mathcal{C}_k)$를 활용하여 구할 수 있습니다. $p(\mathcal{C}_k)$는 클래스 $\mathcal{C}_k$에 포함될 사전 확률, $p(\mathcal{C}_k\vert\mathbf{x})$는 사후 확률에 해당합니다. 만약 우리의 목표가 $\mathbf{x}$를 잘못된 클래스에 포함시킬 가능성을 최소화하는 것이라면 직관적으로 우리는 더 높은 사후 확률을 가진 클래스를 가지게 될 것입니다.

오분류 비율의 최소화

목표를 단순히 잘못된 분류 결과의 숫자를 최대한 줄이는 것이라고 해보겠습니다. 이를 위해서는 각각의 $\mathbf{x}$를 가능한 클래스들 중 하나에 포함시키는 규칙이 필요합니다. 이 규칙은 입력 공간을 결정 구역 decision region 이라고 불리는 구역 $\mathcal{R}_k$들로 나누게 됩니다. 결정 구역들 사이의 경계를 결정 경계 또는 결정 표면 이라고 부릅니다. 클래스가 2개일 때 오분류할 확률은 다음과 같습니다.

\[\begin{aligned} p(오분류) &= p(\mathbf{x} \in \mathcal{R}_1, \mathcal{C}_2) + p(\mathbf{x} \in \mathcal{R}_2, \mathcal{C}_1) \\ &= \int_{\mathcal{R}_1}p(\mathbf{x}, \mathcal{C}_2)dx + \int_{\mathcal{R}_2}p(\mathbf{x}, \mathcal{C}_1)dx \end{aligned}\]

오분류할 확률을 최소화하기 위해서는 각각의 $\mathbf{x}$를 위 식의 피적분 함수들 중 더 작은 값을 가진 클래스에 포함시켜야 합니다. 따라서 오분류 가능성을 최소화하기 위해서는 각각의 $\mathbf{x}$를 사후 확률 $p(\mathcal{C}_k\vert\mathbf{x})$가 최대가 되는 클래스에 포함시키면 됩니다.

\[p(올바름) = \sum^K_{k=1}\int_{\mathcal{R}_k}p(\mathbf{x},\mathcal{C}_k)dx\]

Figure 1.24 두 클래스 각각의 결합 확률 $p(x, \mathcal{C}_K)$를 그린 그림. $\hat{x}$는 결정경계.

기대 손실의 최소화

많은 경우에 목표는 더 복잡할 수 있습니다. 가령 암에 걸린 환자를 걸리지 않았다고 오분류하는 경우는 반대의 경우보다 훨씬 위험합니다. 비용 함수 cost function 라고 불리는 손실 함수를 도입함으로써 이러한 문제들을 공식화할 수 있습니다. 우리의 목표는 전체 손실을 최소화하는 방향으로 바뀌게 됩니다. 효용 함수 utility function을 사용하기도 하는데, 부호만 바꿔주면 같은 개념입니다.

입력값 $\mathbf{x}$ 를 클래스 $k$로 분류했다고 가정해 보겠습니다. 이 과정에서 우리는 손실 $L_{kj}$ 를 발생시킵니다. 우리는 손실 함수를 최소화하는 해를 찾아야 하는데, 알려져 있지 않은 실제 클래스값을 알아야만 계산이 가능합니다. 결합 확률 분포 $p(\mathbf{x}, \mathcal{C}_K)$ 를 활용하여 평균 손실을 최소화하는 것을 목표로 삼겠습니다.

\[\mathbb{E}[L]=\sum_k\sum_j\int_{\mathcal{R}_j}L_{kj}p(\mathbf{x},\mathcal{C}_k)dx\]

우리의 목표는 구역 $\mathcal{R}_j$를 적절히 선택해서 위 식의 기대 손실값을 최소화하는 것입니다. 따라서 기대 손실을 최소화하는 결정 법칙은 각각의 $\mathbf{x}$를 다음의 식을 최소화하는 클래스 $j$에 할당하는 것입니다.

\[\sum_kL_{kj}p(\mathcal{C}_k\vert\mathbf{x})\]

각각의 클래스에 대한 사후 확률 $p(\mathcal{C}_k\vert\mathbf{x})$를 알고 나면 쉽게 실행할 수 있습니다.

거부 옵션

입력 공간 중 결합 확률 $p(\mathbf{x}, \mathcal{C}_K)$들이 비슷한 값을 가지고 있는 구역이 있을 수 있습니다. 이 구역들에 대해서는 해당 구역이 어떤 클래스에 속할지에 대한 확신 정도가 적은 것입니다. 이런 경우 오류 비율을 최소화하기 위해 결정을 피하는 것이 나을 수 있습니다. 이것을 거부 옵션 reject option 이라고 합니다. 이런 경우에는 거부 결정이 내려졌을 때 발생하는 손실값을 고려 사항에 포함해야 할 것입니다.

추론과 결정

지금까지 분류 문제를 추론 단계와 결정 단계로 나누어 보았습니다. 두 가지 문제를 한 번에 풀어낼 수도 있습니다. $\mathbf{x}$가 주어졌을 때 결정값을 돌려주는 함수를 직접 학습시키는 것입니다. 이러한 함수를 판별 함수 discriminant function 라고 합니다. 결정 문제를 푸는 3가지 방법을 알아보겠습니다.

• 생성 모델

  각각의 클래스에 대해서 조건부 확률 밀도 $p(\mathbf{x}\vert\mathcal{C}_k)$를 알아내는 추론 문제를 풀어냅니다. 클래스별 사전 확률 $p(\mathcal{C}_k)$도 구합니다. 그 후 베이지안 정리를 적용해서 각 클래스별 사후 확률 $p(\mathcal{C}_k\vert\mathbf{x})$을 구합니다. 아래와 같이 정리할 수 있습니다.

  \[p(\mathbf{x}) = \sum_kp(\mathbf{x}\vert\mathcal{C}_k)p(\mathcal{C}_k)\]

  이와 동일하게 결합 분포 $p(\mathbf{x}, \mathcal{C}_K)$를 직접적으로 모델링한 후 정규화해서 사후 확률을 구할 수도 있습니다. 그 후 결정 이론을 적용하여 각각의 새 입력변수 $\mathbf{x}$에 대한 클래스를 구합니다. 직간접적으로 입력값과 출력값의 분포를 모델링하여 입력 공간에 합성 데이터를 생성해 넣는 것이 가능하기 때문에 생성 모델 이라고 부릅니다.

• 판별 모델

  사후 확률 $p(\mathcal{C}_k\vert\mathbf{x})$를 계산하는 추론 문제를 풀어낸 후에 결정 이론을 적용하여 각각의 입력 변수 $\mathbf{x}$에 대한 클래스를 구합니다. 사후 확률을 직접 모델링하는 이 방식을 판별 모델 이라고 합니다.

• 단순 분류

  각각의 입력값 $\mathbf{x}$에서 바로 클래스를 뽑아내는 판별 함수 $f(\mathbf{x})$를 찾습니다. 이 방식에서는 확률론이 사용되지 않습니다.

첫번째는 결합분포를 찾아야 하기 때문에 가장 어려운 방식입니다. 각각의 클래스에 대해 일정 수준 이상의 조건부 밀도를 구하기 위해서는 상당히 큰 훈련 집합이 필요합니다. 하지만 이 방식을 사용하면 데이터 $p(\mathbf{x})$의 주변 밀도를 구해 발생 확률이 낮은 새 데이터를 미리 발견해 낼 수 있습니다. 이러한 데이터에 대해서는 예측 모델이 낮은 정확도를 보입니다. 이러한 검출 방식을 이상점 검출 outlier detection 혹은 새것 검출 nobelty detection 이라고 합니다.

하지만 분류만이 목적일 경우 결합 분포 $p(\mathbf{x}, \mathcal{C}_K)$를 전부 계산하는 것은 비효율적입니다. 데이터에 대한 요구량도 큽니다. 이런 경우 사후 확률 $p(\mathcal{C}_k\vert\mathbf{x})$를 직접 계산하는 두번째 방식이 훨씬 더 효율적입니다. 클래스별 조건부 분포에는 사후 확률에 영향을 미치지 않는 정보가 많이 포함되어 있을 수 있습니다.

세번째는 제일 간단합니다. 추론 단계와 결정 단계를 하나로 합친 것입니다. 하지만 사후 확률$p(\mathcal{C}_k\vert\mathbf{x})$를 알지 못하게 된다는 단점이 있습니다. 사후 확률을 구하는 것은 다음과 같은 이유들 때문에 유의미합니다.

• 위험의 최소화

  손실 행렬의 값들이 변할 수 있습니다. 사후 확률을 알고 있다면 식을 약간 수정해서 대응할 수 있지만 판별 함수만 알고 있다면 다시 훈련해야 합니다.

• 거부 옵션

  거부 옵션을 활용하려면 사전 확률을 알아야합니다.

• 클래스 사전 확률에 대한 보상

  클래스가 불균형한 문제의 경우 단순한 해를 최종 해로 결정 내리기 쉽습니다. 이렇게 만들어진 알고리즘은 일반화 성능이 떨어지기 마련입니다. 데이터를 균형 잡힌 데이터로 만들어 학습할 경우 훈련 집합을 변경한 것에 대한 보상을 적용해야 합니다. 사후 확률을 알고 있다면 실제로 모델을 적용할 모수 집합의 클래스의 비율을 곱해 수정된 사후 확률을 구할 수 있습니다.

• 모델들의 결합

  하나의 큰 문제를 여러 작은 문제로 나눠 각각을 해결하는 것이 나은 경우도 있습니다. 각 모델이 각 클래스에 대한 사후 확률을 제공한다면 확률의 법칙을 활용하여 서로 다른 출력값을 합할 수 있습니다. 가령 이를 위해 각 클래스에 대해서 데이터의 분포가 독립적이라고 가정할 수 있습니다.

  \[p(\mathbf{x}_\text{I}, \mathbf{x}_\text{B}\vert\mathcal{C}_k) = p(\mathbf{x}_\text{I}\vert\mathcal{C}_k)p(\mathbf{x}_\text{B}\vert\mathcal{C}_k)\]

  이는 조건부 독립 성질의 예시입니다. 분포들이 클래스에 포함된다는 조건하에 독립적입니다. 이를 바탕으로 두 변수가 주어졌을 때의 사후 확률을 구할 수 있습니다. 이것은 나이브 베이즈 모델의 예시입니다.

회귀에서의 손실 함수

회귀 문제의 경우 결정 이론을 어떻게 적용하는지 알아보겠습니다. 각각의 $\mathbf{x}$에 대해서 $t$의 추정값 $y(\mathbf{x})$를 선택해야 합니다. 이때 손실 $L(t, y(\mathbf{x}))$가 발생한다고 가정 하겠습니다. 회귀 문제에서 일반적으로 손실 함수로 사용되는 제곱 손실을 사용하겠습니다. 이때 평균 손실은 다음과 같이 주어집니다.

\[\mathbb{E}[L] = \int\int \{y(\mathbf{x})-t\}^2p(\mathbf{x},t)d\mathbf{x}dt\]

우리의 목표는 $\mathbb{E}[L]$를 최소화하는 $y(\mathbf{x})$를 선택하는 것입니다. 변분법을 적용해서 다음과 같이 적을 수 있습니다.

\[\frac{\delta\mathbb{E}[l]}{\delta y(\mathbf{x})} = 2\int\{y(\mathbf{x})-t\}p(\mathbf{x},t)dt = 0\]

이 식을 $y(\mathbf{x})$에 대해서 해를 구하고 확률의 합과 곱의 법칙을 적용하면 다음과 같이 됩니다.

\[y(\mathbf{x}) = \frac{\int tp(\mathbf{x},t)dt}{p(\mathbf{x})} = \int tp(t\vert\mathbf{x})dt = \mathbb{E}_t[t\vert\mathbf{x}]\]

위 식은 $\mathbf{x}$가 주어졌을 때의 t의 조건부 평균으로 회귀 함수 라고 합니다. 이 식은 최적의 해가 조건부 기댓값이라는 지식을 바탕으로 제곱항을 전개함으로써 얻을 수도 있습니다.

\[\{y(\mathbf{x})-t\}^2 = \{y(\mathbf{x}) - \mathbb{E}[t\vert\mathbf{x}] + \mathbb{E}[t\vert\mathbf{x}] - t\}^2\\= \{y(\mathbf{x}) - \mathbb{E}[t\vert\mathbf{x}]\}^2 + 2\{y(\mathbf{x}) - \mathbb{E}[t\vert\mathbf{x}]\}\{\mathbb{E}[t\vert\mathbf{x}]-t\} + \{\mathbb{E}[t\vert\mathbf{x}]-t\}^2\]

이 전개 결과를 손실 함수에 대입하고 $t$에 대해 적분하면 교차항들이 사라지게 됩니다. 그 결과로 다음 형태의 손실 함수를 얻을 수 있습니다.

\[\mathbb{E}[L] = \int\{y(\mathbf{x})-\mathbb{E}[t\vert\mathbf{x}]\}^2p(\mathbf{x})d\mathbf{x} +\int\text{var}[t\vert\mathbf{x}]p(\mathbf{x})d\mathbf{x}\]

우리가 찾고자 하는 함수 $y(\mathbf{x})$는 첫번째 항에만 있는데, $y(\mathbf{x})$가 $\mathbb{E}[t\vert\mathbf{x}]$일 때 이 항은 최소화 되어 항 자체가 사라집니다. 즉 최적의 최소 제곱 예측은 조건부 평균으로 주어진다는 것을 보여줍니다. 두번째 항은 $t$에 대한 분포의 분산을 계산하고 이를 $\mathbf{x}$에 대해 평균을 낸 것입니다. 이 항은 $y(\mathbf{x})$에 대해 독립적인 노이즈이며 줄일 수 없습니다.

분류 문제와 마찬가지로 3가지 방법이 존재하며 장단점도 같습니다.