경험적 위험 최소화

통계적 학습 이론에서 경험적 위험 최소화 원리는 알려진 고정된 데이터셋에 대한 성능 평가를 기반으로 하는 학습 알고리즘의 계열을 정의한다. 핵심 아이디어는 대수의 법칙의 응용에 기초한다. 보다 구체적으로, 데이터의 실제 분포를 알 수 없기 때문에 예측 알고리즘이 실제로 얼마나 잘 작동할지(즉, "실제 위험")를 정확히 알 수는 없지만, 대신 알려진 훈련 데이터 집합에서 알고리즘의 성능을 추정하고 최적화할 수 있다. 알려진 훈련 데이터 집합에 대한 성능을 "경험적 위험"이라고 한다.

배경

다음 상황은 많은 지도 학습 문제의 일반적인 설정이다. 두 개의 객체 공간 X와 Y가 있으며, x \in X가 주어졌을 때 객체 y \in Y를 출력하는 함수 \ h: X \to Y(흔히 가설이라 불림)를 학습하고자 한다. 이를 위해 n개의 예제로 구성된 훈련 집합 \ (x_1, y_1), \ldots, (x_n, y_n)이 있으며, 여기서 x_i \in X는 입력이고 y_i \in Y는 h(x_i)로부터 기대되는 대응 출력이다.

보다 형식적으로 설명하면, X와 Y에 대한 결합 확률 분포 P(x, y)가 존재한다고 가정하고, 훈련 집합이 P(x, y)로부터 독립 동일 분포(i.i.d.)로 추출된 n개의 인스턴스 \ (x_1, y_1), \ldots, (x_n, y_n)으로 구성된다고 가정한다. 결합 확률 분포의 가정은 예측의 불확실성(예: 데이터의 잡음으로 인한)을 모델링할 수 있게 해주는데, 이는 y가 결정론적 함수가 아니라 고정된 x에 대해 조건부 분포 P(y | x)를 갖는 확률 변수이기 때문이다.

또한 가설의 예측 \hat{y}가 실제 결과 y와 얼마나 다른지를 측정하는 음이 아닌 실수값 손실 함수 L(\hat{y}, y)가 존재한다고 가정한다. 분류 과제에서 이러한 손실 함수는 채점 규칙이 될 수 있다. 가설 h(x)와 관련된 위험은 손실 함수의 기댓값으로 정의된다: R(h) = \mathbf{E}[L(h(x), y)] = \int L(h(x), y),dP(x, y).

이론에서 흔히 사용되는 손실 함수는 0-1 손실 함수이다: L(\hat{y}, y) = \begin{cases} 1 & \mbox{ if }\quad \hat{y} \ne y \ 0 & \mbox{ if }\quad \hat{y} = y \end{cases}.

학습 알고리즘의 궁극적 목표는 고정된 함수 클래스 \mathcal{H}에서 위험 R(h)가 최소가 되는 가설 h^를 찾는 것이다: h^ = \underset{h \in \mathcal{H}}{\operatorname{arg, min}}, {R(h)}.

분류 문제에서 베이즈 분류기는 0-1 손실 함수로 정의된 위험을 최소화하는 분류기로 정의된다.

형식적 정의

일반적으로 분포 P(x, y)가 학습 알고리즘에 알려져 있지 않기 때문에 위험 R(h)를 계산할 수 없다. 그러나 독립 동일 분포의 훈련 데이터 포인트 표본이 주어지면, 훈련 집합에 대해 손실 함수의 평균을 계산하여 경험적 위험이라 불리는 추정값을 계산할 수 있다. 보다 형식적으로는 경험적 측도에 대한 기댓값을 계산하는 것이다: ! R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i).

경험적 위험 최소화 원리[^4]는 학습 알고리즘이 가설 클래스 \mathcal H에서 경험적 위험을 최소화하는 가설 \hat{h}를 선택해야 한다고 명시한다: \hat{h} = \underset{h \in \mathcal{H}}{\operatorname{arg, min}}, R_{\text{emp}}(h). 따라서, 경험적 위험 최소화 원리에 의해 정의된 학습 알고리즘은 위의 최적화 문제를 푸는 것으로 구성된다.

성질

경험적 위험 최소화의 성능 보장은 선택된 함수 클래스와 분포 가정에 크게 의존한다.[^1] 일반적으로 분포 무관(distribution-free) 방법은 너무 거칠어 실용적인 한계를 도출하지 못한다. 그러나 일관성(consistency)과 같은 학습 알고리즘의 점근적 성질을 유도하는 데에는 여전히 유용하다. 특히, 고정된 함수 클래스가 주어졌을 때 경험적 위험 최소화의 성능에 대한 분포 무관 한계는 함수 클래스의 VC 복잡도에 대한 한계를 이용하여 유도할 수 있다.

간단히 하기 위해 이진 분류 문제의 경우를 고려하면, 선택된 분류기 \phi_n이 최적의 분류기 \phi^*보다 훨씬 나쁠 확률에 대한 한계를 구할 수 있다. 크기 n의 데이터셋이 주어졌을 때, 성장 함수 \mathcal S(\mathcal C, n)을 갖는 가설 클래스 \mathcal C 위에서 정의된 위험 L을 고려하자. 그러면 모든 \epsilon > 0에 대해 다음이 성립한다:[^2]

\mathbb P \left (L(\phi_n) - L(\phi^*) > \epsilon \right ) \leq \mathcal 8S(\mathcal C, n) \exp{-n\epsilon^2 / 32}

회귀 문제에 대해서도 유사한 결과가 성립한다.[^3] 이것은 때때로 *공짜 점심 없음 정리(No free lunch theorem)*라고 불린다. 특정 학습 알고리즘이 임의의 분포에 대해 점근적으로 최적의 성능을 제공할 수 있더라도, 유한 표본에서의 성능은 적어도 하나의 데이터 분포에 대해서는 항상 좋지 않다. 이는 어떤 분류기도 모든 분포에 대해 주어진 표본 크기에서의 오류를 개선할 수 없음을 의미한다.[^2]

구체적으로, \epsilon > 0이고 표본 크기 n과 분류 규칙 \phi_n을 고려하면, 위험 L^* =0인 (즉, 완벽한 예측이 가능한) (X, Y)의 분포가 존재하여 다음을 만족한다:[^2] \mathbb E L_n \geq 1/2 - \epsilon.

더 나아가 학습 알고리즘의 수렴 속도가 일부 분포에 대해 좋지 않음을 보일 수 있다. 구체적으로, 0으로 수렴하는 감소하는 양수 수열 a_i가 주어지면, 다음을 만족하는 분포를 찾을 수 있다:

<math display='block> \mathbb E L_n \geq a_i

이는 모든 n에 대해 성립한다. 이 결과는 보편적으로 좋은 분류 규칙은 존재하지 않음을, 즉 해당 규칙이 적어도 하나의 분포에 대해서는 품질이 낮아야 함을 보여준다.[^2]

계산 복잡도

0-1 손실 함수를 사용하는 분류 문제에 대한 경험적 위험 최소화는 선형 분류기와 같은 비교적 단순한 함수 클래스에 대해서도 NP-난해 문제로 알려져 있다.[^5] 그럼에도 불구하고, 최소 경험적 위험이 0인 경우, 즉 데이터가 선형 분리 가능한 경우에는 효율적으로 풀 수 있다.

실제로 기계 학습 알고리즘은 최적화가 더 용이한 0-1 손실 함수의 볼록 근사(예: SVM의 힌지 손실)를 사용하거나, 분포 P(x, y)에 대한 가정을 부과함으로써(따라서 위 결과가 적용되는 비구지적(agnostic) 학습 알고리즘이 아니게 됨) 이 문제에 대처한다.

볼록화의 경우, Zhang의 보조정리는 볼록화된 문제의 초과 위험을 이용하여 원래 문제의 초과 위험을 구한다.[^6] 볼록 최적화를 이용하여 후자를 최소화하면 전자도 제어할 수 있다.

기울어진 경험적 위험 최소화

기울어진 경험적 위험 최소화(Tilted empirical risk minimization)는 기울기 매개변수를 도입하여 제곱 오차와 같은 표준 손실 함수를 수정하는 데 사용되는 기계 학습 기법이다. 이 매개변수는 훈련 중 데이터 포인트의 가중치를 동적으로 조정하여, 알고리즘이 데이터 분포의 특정 영역이나 특성에 집중할 수 있도록 한다. 기울어진 경험적 위험 최소화는 불균형 데이터가 있는 시나리오나 예측 공간의 특정 부분에서의 오류를 강조할 필요가 있을 때 특히 유용하다.

같이 보기

*M-추정량 *최대우도추정

더 읽을거리

---

참고 문헌

[^1]: Györfi, László. A Distribution-Free Theory of Nonparametric Regression. Springer. (2010-12-01)

[^2]: Devroye, L., Gyorfi, L. & Lugosi, G. A Probabilistic Theory of Pattern Recognition. Discrete Appl Math 73, 192–194 (1997)

[^3]: Devroye, Luc. A Probabilistic Theory of Pattern Recognition. (1996)

[^4]: V. Vapnik (1992). [https://papers.nips.cc/paper_files/paper/1991/file/ff4d5fbbafdf976cfdc032e3bde78de5-Paper.pdf ''학습 이론을 위한 위험 최소화의 원리.'']

[^5]: V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). [https://arxiv.org/abs/1012.0729 ''반공간에 의한 단항식의 불가지론적 학습은 어렵다.''] (해당 논문 및 그 안의 참고 문헌을 참조)

[^6]: 기계 학습의 수학 강의 9 노트 {{!