An Overview of Statistical Learning
Empirical Risk 사용의 근거?Permalink
이번 게시글은 Statistical Learning, 즉 통계적 학습이론의 근간이 되는 추정 이론 중 Empirical risk 사용의 근거와 관련 이론에 대해 살펴보도록 하자. 내용은 대표적인 머신러닝 알고리즘인 Support Vector Machine의 공동 창시자 Vladimir N. Vapnik의 ’An Overview of Statistical Learning’(1999) 논문을 바탕으로 하였다.
Learning ProblemPermalink
통계적 학습이론(혹은 머신러닝)의 근간은 함수추정(function estimation) 과정이다. 즉, i.i.d인 N개의 관측값(training data)
이 주어질 때 함수들의 집합
값을 최소화하는 것으로 나타난다. 여기서
Empirical RiskPermalink
하지만, 일반적인 학습문제에서는 데이터셋의 확률측도
을 사용해야 한다. 이는 기댓값 형태가 아니므로 확률측도에 대한 사전정보가 불필요하고, 대신 training data에 기반한다. 이로 인해 함수추정의 문제는
이러한 ERM principle은 사실 머신러닝에서만의 특별한 방법이 아니다. Loss function으로 squared loss를 사용하고, 함수모임
Risk functional(식 1)을 최소화하는 함수
Theory of ConsistencyPermalink
Key Theorem of the Learning TheoryPermalink
Vapnik이 제시한 학습이론에서의 핵심 정리는 다음과 같다.
Key Theorem : 함수모임
이 확률측도 에 대해 bounded loss를 가진다고 하자. 즉, 그러면 ERM principle이 일치성을 갖기 위할 필요충분조건은
에서 가 로 균등수렴(uniformly convergence)하는 것이다. 즉, 임의의 에 대해 을 만족해야 한다.
위와 같은 형태의 수렴을 uniform one-sided convergence라고도 한다(절대값 없이 한 방향으로의 수렴이기 때문). 위 정리가 Key theorem인 이유는, ERM principle에서의 어떠한 형태의 수렴여부를 판정하기 위해서는 worst case를 판별해야 한다는 조건을 제시해주기 때문이다. 위 정리에서는 함수집합들 중에서 상한을 취했기 때문에 risk value와 empirical risk value가 가장 크게 차이나는 worst case가 기준이 되는 것이다.
Uniform ConvergencePermalink
위 key Theorem으로부터 ERM principle의 일치성 확인을 위해 균등수렴이 보장되어야 된다는 것을 확인했다. 그렇다면 균등수렴이 성립할 필요충분조건은 어떤 것이 있을지 살펴보도록 하자. 여기서 중요한 개념으로 엔트로피(entropy) 가 정의되는데, 두 단계로 나누어 살펴보도록 하자.
Entropy of the set of IndicatorsPermalink
우선 함수모임
값을 random entropy라고 정의하며, 이는 주어진 데이터셋에서 정의될 수 있는 분류기(함수) 집합의 diversity를 설명하는 역할을 한다. 또한, 여기서 더 나아가면 random sample
이를 Indicator functions
Theorem. ERM principle의 uniform two-sided convergence, 즉 임의의
에 대해 다음 조건
= 0 이 성립할 필요충분조건은 다음 식이 성립하는 것이다.
Entropy of the Set of Real FunctionsPermalink
앞에서 살펴본 Indicator function들의 집합에 대한 entropy를 이번에는 실함수 집합으로 확장시켜보도록 하자. 유계인 손실함수들의 집합
을 정의할 수 있다. 이때 C metric에 대한 위 벡터모임의 minimal
또한, 위 식에서 metric
을 유계함수모임
을 함수모임에 대한 VC-entropy라고 정의한다. 이를 이용하여 유계인 (실함수)손실함수들에 대한 일치성의 필요충분조건을 다음과 같이 정리할 수 있다.
Theorem. 유계실함수인 손실함수에 대한 ERM principle의 uniform two-sided convergence, 즉 임의의
에 대해 다음 조건
= 0 이 성립할 필요충분조건은 임의의
에 대해 다음 식이 성립하는 것이다.
VC DimensionPermalink
앞선 내용에서 ERM principle이 일치성을 갖기 위한 필요충분조건에 대해 살펴보았다. 그러나 앞선 식들은 수렴의 속도(rate of convergence)에 대한 정보를 제공하고 있지 않다. 이를 해결하기 위해서는 VC-dimension이라는 새로운 capacity 개념과 Growth function
VC-dimension using Growth functionPermalink
앞서 Indicator function들의 집합
로 정의했었다. 이때 기댓값과 로그함수의 순서를 바꾼
를 annealed VC-entropy라고 정의하며, 이는 Jensen’s Ineqaulity로부터 entropy 이상의 값을 갖는다. 또한 기댓값 대신 상한을 취한
을 growth function이라고 정의하며, 이는 상한에 의해 annealed VC-entropy 이상의 값을 갖는다. 이때 growth function에 대해 다음 정리가 성립한다.
Theorem. 임의의 growth function은 다음 등식
를 만족하거나 다음과 같이 위로 유계이다.
이때 는 다음을 만족하는 정수이다. 위 정리는 growth function이 선형함수이거나, 로그함수에 의해 유계라는 사실을 의미한다. 만일
에 대한 growth function이 선형함수라면 함수집합의 VC-dimension이 무한(infinite)하다고 정의한다. 만일 선형함수가 아니라면(로그함수에 의해 유계) VC-dimension이 유한(finite)하다고 정의하며 이때 위 정리를 만족하는 의 값을 VC-dimension으로 정의한다.
Another DefinitionPermalink
반면, 다른 방법에 의해 VC-dimension을 동일하게 정의하고 이를 실함수로 확장할 수 있다. 우선 Indicator function의 집합
벡터
가 집합 에 의해 모든 분류의 경우의 수( 가지)로 분류될 때(shattered) 이를 만족하는 중 최댓값 으로 정의된다. 예를 들어, 만일 어떤 지시함수 집합의 VC-dimension이 3이라는 것은 해당 집합의 지시함수들로 최대 3개의 벡터를 shatter(8가지로 나눔)할 수 있음을 의미한다. 만일 개의 벡터가 shatter될 수 있다면, 해당 집합의 VC-dimension은 무한차원이다.
이러한 정의를 유계실함수들의 모임
를 정의하고(
ExamplePermalink
N-dimensional coordinate space
의 VC-dimension은 다음과 같은 지시함수모임
의 VC-dimension과 동일한데, 이때 위 지시함수모임은 최대
Structural Risk MinimizationPermalink
ERM의 문제점Permalink
ERM principle은 risk functional 최적화 문제의 해에 대한 일치성을 갖는다. 그러나 이러한 일치성은 sample size에만 의존한다는 문제점이 있다. 실제로 유계실함수집합
에 대해 다음이 성립하는데,
여기서
으로 정의된다. 만일 식에서
Def of SRMPermalink
함수모임
를 만족하는 부분집합열
- 집합
가 S에서 조밀하다. 의 VC-dimension 는 모두 유한하다. 의 모든 함수는 totally bounded( )이다.
이로부터 정의되는 SRM principle은 random sample
이때 다음 정리가 성립한다.
Theorem. 임의의 확률분포에 대해 SRM method는 best possible solution(minimizes the expected risk)으로의 수렴을 보장한다.
즉, 이는 SRM priciple이 전역적으로(universally) 일치성을 갖는다는 의미이다. 또한, SRM의 수렴 속도와 관련하여 다음 정리가 성립한다.
Theorem. Admissible structure에 대해 SRM을 적용하여 N개의 sample에 대해
번째 structure가 대응된다고 하자. 이때 expected best risk 으로 수렴하는 risk의 열 을 구성하고, 이때 각 단계에서의 근사함수를 이라고 두면 근사적 수렴속도(asymptotic rate of convergence)는 으로 주어진다. 이때
은 에 속한 함수들의 bound를 의미하며 을 만족한다. 또한
은 근사의 속도(rate of approximation) 를 의미한다.
Leave a comment