경험적 위험 최소화

Mathematical foundations 통계적 학습이론에서 **경험적 위험 최소화** 또는 **경험적 리스크 최소화**(Empirical risk minimization) 원리는 알려져 있고 고정된 데이터셋에 대한 성능 평가를 기반으로 하는 학습 알고리즘의 한 종류를 정의한다. 핵심 아이디어는 큰 수의 법칙을 적용한 것이다. 더 구체적으로 말해, 우리는 데이터의 진정한 분포를 알지 못하기 때문에 예측 알고리즘이 실제로 얼마나 잘 작동할지(즉, "진정한 위험") 정확히 알 수 없지만, 대신 알려진 훈련 데이터셋에서 알고리즘의 성능을 추정하고 최적화할 수 있다. 알려진 훈련 데이터셋에 대한 성능은 "경험적 위험"이라고 불린다.
# 배경
다음 상황은 많은 지도 학습 문제의 일반적인 설정이다. 두 객체 공간 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의 결정론적 함수가 아니라 고정된 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)를 계산할 수 없다. 그러나 iid 훈련 데이터 포인트 샘플이 주어지면 훈련 세트에 대한 손실 함수의 평균을 계산하여 경험적 위험이라고 불리는 추정치를 계산할 수 있다. 더 공식적으로는 경험적 측도에 대한 기댓값을 계산하는 것이다. : \\! R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i). 경험적 위험 최소화 원리V. Vapnik (1992). Principles of Risk Minimization for Learning Theory.는 학습 알고리즘이 가설 클래스 \mathcal H에서 경험적 위험을 최소화하는 가설 \hat{h}를 선택해야 한다고 명시한다. : \hat{h} = \underset{h \in \mathcal{H{\operatorname{arg\, min\, R_{\text{emp(h). 따라서 경험적 위험 최소화 원리로 정의되는 학습 알고리즘은 위의 최적화 문제를 해결하는 것으로 구성된다.
# 속성
경험적 위험 최소화 성능에 대한 보증은 선택된 함수 클래스뿐만 아니라 가정된 분포에 따라 크게 달라진다.language=en 일반적으로 분포-자유 방법은 너무 거칠고 실제적인 경계를 제공하지 않는다. 그러나 일관성과 같은 학습 알고리즘의 점근적 속성을 도출하는 데 여전히 유용하다. 특히, 고정된 함수 클래스가 주어졌을 때 경험적 위험 최소화 성능에 대한 분포-자유 경계는 함수 클래스의 VC 복잡도에 대한 경계를 사용하여 도출할 수 있다. 단순화를 위해 이진 분류 작업을 고려할 때, 선택된 분류기 \phi_n이 최상의 분류기 \phi^*보다 훨씬 나쁠 확률을 제한하는 것이 가능하다. 크기 n의 데이터셋이 주어졌을 때, 성장 함수 \mathcal S(\mathcal C, n)를 가진 가설 클래스 \mathcal C에 대해 정의된 위험 L을 고려한다. 그러면 모든 \epsilon > 0에 대해:Devroye, L., Gyorfi, L. & Lugosi, G. A Probabilistic Theory of Pattern Recognition. Discrete Appl Math 73, 192–194 (1997) \mathbb P \left (L(\phi_n) - L(\phi^*) > \epsilon \right ) \leq \mathcal 8S(\mathcal C, n) \exp\\{-n\epsilon^2 / 32\\} 회귀 작업에서도 유사한 결과가 나타난다. 이러한 결과는 종종 균일 큰 수의 법칙에 기반하는데, 이는 가설 클래스 전체에 걸쳐 경험적 위험과 실제 위험 간의 편차를 통제한다.
## 불가능 결과
분포 가정이 없을 경우 알고리즘 성능의 하한을 보여주는 것도 가능하다.url-access=subscription 이는 때때로 공짜 점심 정리라고 불린다. 특정 학습 알고리즘이 어떤 분포에 대해서도 점근적으로 최적의 성능을 제공할 수 있지만, 유한 샘플 성능은 적어도 하나의 데이터 분포에 대해서는 항상 좋지 않다. 이는 주어진 샘플 크기에 대해 모든 분포에 대해 오류를 개선할 수 있는 분류기가 없다는 것을 의미한다. 구체적으로, \epsilon > 0라고 하고, 샘플 크기 n과 분류 규칙 \phi_n을 고려할 때, 위험 L^* =0(즉, 완벽한 예측이 가능함)인 (X, Y)의 분포가 존재하여 다음과 같다. \mathbb E L_n \geq 1/2 - \epsilon. 또한 학습 알고리즘의 수렴 속도가 일부 분포에 대해 좋지 않다는 것을 보여줄 수도 있다. 구체적으로, 0으로 수렴하는 감소하는 양수 시퀀스 a_i가 주어지면 다음과 같은 분포를 찾을 수 있다.
## 계산 복잡도
0-1 손실 함수를 사용하는 분류 문제의 경험적 위험 최소화는 선형 분류와 같이 비교적 간단한 함수 클래스에서도 NP-난해 문제로 알려져 있다.V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (See the paper and references therein) 그럼에도 불구하고, 최소 경험적 위험이 0일 때, 즉 데이터가 선형 분리 가능할 때 효율적으로 해결될 수 있다. 실제로, 기계 학습 알고리즘은 0-1 손실 함수에 대한 볼록 근사(예: SVM의 힌지 손실)를 사용하여 이 문제를 해결한다. 이 근사는 최적화하기 더 쉽거나, 분포 P(x, y)에 가정을 부과하여(따라서 위 결과가 적용되는 비분포 학습 알고리즘이 되는 것을 멈춤) 해결한다. 볼록화의 경우, 장의 보조정리는 볼록화된 문제의 초과 위험을 사용하여 원래 문제의 초과 위험을 주요화한다.language=en 후자를 볼록 최적화를 사용하여 최소화하면 전자를 제어할 수도 있다.
# 기울어진 경험적 위험 최소화
기울어진 경험적 위험 최소화는 기울기 매개변수를 도입하여 제곱 오차와 같은 표준 손실 함수를 수정하는 데 사용되는 기계 학습 기술이다. 이 매개변수는 훈련 중에 데이터 포인트의 가중치를 동적으로 조정하여 알고리즘이 데이터 분포의 특정 영역이나 특성에 집중할 수 있도록 한다. 기울어진 경험적 위험 최소화는 불균형 데이터가 있거나 예측 공간의 특정 부분에서 오류를 강조할 필요가 있는 시나리오에서 특히 유용하다.
# 더 읽어보기
* isbn=978-0-387-98780-4 위키데이터 속성 추적 분류:기계 학습