경험적 위험 최소화

통계적 학습이론에서 경험적 위험 최소화 또는 경험적 리스크 최소화(Empirical risk minimization) 원리는 알려져 있고 고정된 데이터셋에 대한 성능 평가를 기반으로 하는 학습 알고리즘의 한 종류를 정의한다. 핵심 아이디어는 큰 수의 법칙을 적용한 것이다. 더 구체적으로 말해, 우리는 데이터의 진정한 분포를 알지 못하기 때문에 예측 알고리즘이 실제로 얼마나 잘 작동할지(즉, "진정한 위험") 정확히 알 수 없지만, 대신 알려진 훈련 데이터셋에서 알고리즘의 성능을 추정하고 최적화할 수 있다. 알려진 훈련 데이터셋에 대한 성능은 "경험적 위험"이라고 불린다.

배경

다음 상황은 많은 지도 학습 문제의 일반적인 설정이다. 두 객체 공간 ${\displaystyle X}$와 ${\displaystyle Y}$가 있으며, ${\displaystyle x\in X}$가 주어졌을 때 ${\displaystyle y\in Y}$를 출력하는 함수 ${\displaystyle \ h:X\to Y}$(종종 가설이라고 불림)를 학습하고자 한다. 이를 위해 ${\displaystyle n}$개의 예시로 구성된 훈련 세트 ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$가 있으며, 여기서 ${\displaystyle x_{i}\in X}$는 입력이고 ${\displaystyle y_{i}\in Y}$는 ${\displaystyle h(x_{i})}$에서 원하는 해당 응답이다.

더 공식적으로 설명하자면, ${\displaystyle X}$와 ${\displaystyle Y}$에 대한 결합분포 ${\displaystyle P(x,y)}$가 존재하고, 훈련 세트는 ${\displaystyle P(x,y)}$에서 i.i.d.로 추출된 ${\displaystyle n}$개의 인스턴스 ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$로 구성된다고 가정한다. 결합 확률 분포의 가정은 예측의 불확실성을 모델링할 수 있게 한다(예: 데이터의 노이즈로 인해). 왜냐하면 ${\displaystyle y}$는 ${\displaystyle x}$의 결정론적 함수가 아니라 고정된 ${\displaystyle x}$에 대한 조건부 분포 ${\displaystyle P(y|x)}$를 가진 확률 변수이기 때문이다.

또한 가설의 예측 ${\displaystyle {\hat {y}}}$가 진정한 결과 ${\displaystyle y}$와 얼마나 다른지를 측정하는 음수가 아닌 실수 값을 가지는 손실 함수 ${\displaystyle L({\hat {y}},y)}$가 존재한다고 가정한다. 분류 작업의 경우, 이러한 손실 함수는 스코어링 룰이 될 수 있다. 가설 ${\displaystyle h(x)}$와 관련된 위험은 손실 함수의 기댓값으로 정의된다.

${\displaystyle R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).}$

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

학습 알고리즘의 궁극적인 목표는 고정된 함수 클래스 ${\displaystyle {\mathcal {H}}}$ 중에서 위험 ${\displaystyle R(h)}$가 최소화되는 가설 ${\displaystyle h^{*}}$를 찾는 것이다.

${\displaystyle h^{*}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,{R(h)}.}$

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

공식 정의

일반적으로 분포 ${\displaystyle P(x,y)}$가 학습 알고리즘에 알려져 있지 않기 때문에 위험 ${\displaystyle R(h)}$를 계산할 수 없다. 그러나 iid 훈련 데이터 포인트 샘플이 주어지면 훈련 세트에 대한 손실 함수의 평균을 계산하여 경험적 위험이라고 불리는 추정치를 계산할 수 있다. 더 공식적으로는 경험적 측도에 대한 기댓값을 계산하는 것이다.

${\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$

경험적 위험 최소화 원리^[1]는 학습 알고리즘이 가설 클래스 ${\displaystyle {\mathcal {H}}}$에서 경험적 위험을 최소화하는 가설 ${\displaystyle {\hat {h}}}$를 선택해야 한다고 명시한다.

${\displaystyle {\hat {h}}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,R_{\text{emp}}(h).}$

따라서 경험적 위험 최소화 원리로 정의되는 학습 알고리즘은 위의 최적화 문제를 해결하는 것으로 구성된다.

속성

경험적 위험 최소화 성능에 대한 보증은 선택된 함수 클래스뿐만 아니라 가정된 분포에 따라 크게 달라진다.^[2] 일반적으로 분포-자유 방법은 너무 거칠고 실제적인 경계를 제공하지 않는다. 그러나 일관성과 같은 학습 알고리즘의 점근적 속성을 도출하는 데 여전히 유용하다. 특히, 고정된 함수 클래스가 주어졌을 때 경험적 위험 최소화 성능에 대한 분포-자유 경계는 함수 클래스의 VC 복잡도에 대한 경계를 사용하여 도출할 수 있다.

단순화를 위해 이진 분류 작업을 고려할 때, 선택된 분류기 ${\displaystyle \phi _{n}}$이 최상의 분류기 ${\displaystyle \phi ^{*}}$보다 훨씬 나쁠 확률을 제한하는 것이 가능하다. 크기 ${\displaystyle n}$의 데이터셋이 주어졌을 때, 성장 함수 ${\displaystyle {\mathcal {S}}({\mathcal {C}},n)}$를 가진 가설 클래스 ${\displaystyle {\mathcal {C}}}$에 대해 정의된 위험 ${\displaystyle L}$을 고려한다. 그러면 모든 ${\displaystyle \epsilon >0}$에 대해:^[3]

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

회귀 작업에서도 유사한 결과가 나타난다.^[2] 이러한 결과는 종종 균일 큰 수의 법칙에 기반하는데, 이는 가설 클래스 전체에 걸쳐 경험적 위험과 실제 위험 간의 편차를 통제한다.^[3]

불가능 결과

분포 가정이 없을 경우 알고리즘 성능의 하한을 보여주는 것도 가능하다.^[4] 이는 때때로 공짜 점심 정리라고 불린다. 특정 학습 알고리즘이 어떤 분포에 대해서도 점근적으로 최적의 성능을 제공할 수 있지만, 유한 샘플 성능은 적어도 하나의 데이터 분포에 대해서는 항상 좋지 않다. 이는 주어진 샘플 크기에 대해 모든 분포에 대해 오류를 개선할 수 있는 분류기가 없다는 것을 의미한다.^[3]

구체적으로, ${\displaystyle \epsilon >0}$라고 하고, 샘플 크기 ${\displaystyle n}$과 분류 규칙 ${\displaystyle \phi _{n}}$을 고려할 때, 위험 ${\displaystyle L^{*}=0}$(즉, 완벽한 예측이 가능함)인 ${\displaystyle (X,Y)}$의 분포가 존재하여 다음과 같다.^[3] $${\displaystyle \mathbb {E} L_{n}\geq 1/2-\epsilon .}$$

또한 학습 알고리즘의 수렴 속도가 일부 분포에 대해 좋지 않다는 것을 보여줄 수도 있다. 구체적으로, 0으로 수렴하는 감소하는 양수 시퀀스 ${\displaystyle a_{i}}$가 주어지면 다음과 같은 분포를 찾을 수 있다.

$${\displaystyle \mathbb {E} L_{n}\geq a_{i}}$$

모든 ${\displaystyle n}$에 대해. 이 결과는 보편적으로 좋은 분류 규칙은 존재하지 않으며, 적어도 하나의 분포에 대해 규칙이 낮은 품질이어야 함을 보여준다.^[3]

계산 복잡도

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

실제로, 기계 학습 알고리즘은 0-1 손실 함수에 대한 볼록 근사(예: SVM의 힌지 손실)를 사용하여 이 문제를 해결한다. 이 근사는 최적화하기 더 쉽거나, 분포 ${\displaystyle P(x,y)}$에 가정을 부과하여(따라서 위 결과가 적용되는 비분포 학습 알고리즘이 되는 것을 멈춤) 해결한다.

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

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

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

같이 보기

• M-추정기
• 최대가능도 방법