Ch9.1~9.2 Algorithm-independent machine learning - Introduction

 2020-2학기 서강대 김경환 교수님 강의 내용 및 패턴인식 교재를 바탕으로 본 글을 작성하였습니다.

 

9.1 Introduction

---

▶ Questions concerning the foundations and philosophical underpinnings of statistical pattern classification.

• any reasons to favor one algorithm over another?
• are there any fundamental results that hold regardless of the cleverness of the designer, the number and distribution of the patterns, and the nature of the classification task?
• are there fundamental results that do not depend upon the particular choice of classifier or learning method?

 앞 장에서는 패턴 인식을 위한 여러 학습 알고리즘과 기법들을 보았다. 당연 "이러한 많은 알고리즘들을 중에서 어떤 게 최선(Best)일까?"라는 질문을 할 수 있을 것이다. 

 예를 들어, train set에 대해 똑같이 잘 동작하는 두 개의 classifier(A, B 분류기)가 있다고 하자. test set에서는 더 간단한 분류기(A)가 더 잘 동작할 것으로 기대될 수 있다는 주장이 빈번하다. 그러나 이 "version of Occam’s razor(Occam의 면도날 : 더 간단한 분류기가 잘 동작할 것이라는 믿음)"이 정말 명백한가? 마찬가지로, classifier의 판전 함수들에 대해 "smoother"을 선호하거나 부과한다. 더 간단하거나 "더 부드러운" 분류기들이 일반화 성능이 좋은가, 만일 그렇다면, 그 이유는를 찾고 싶을 것이다. 이번 Ch9.에서는 위의 의견과 통계적 패턴 분류의 기초 및 철학적 토대에 관한 관련된 의문들을 살펴보려고 한다. 

 

▶ “Algorithm-independent” in the title refers to ("알고리즘-독립적")

• those mathematical foundations that do not depend on the particular classifier or learning algorithm used. 
• techniques that can be used in conjunction with different learning algorithms, or provide guidance in their use.

 Ch9.에 사용된 "Algorithm-independent"의 의미를 집고 넘어가자.

 첫째, 사용된 특정 분류기나 학습 알고리즘에 종속되지 않는 수학적 근거들을 말함. 예를 들면, "bias-variance"와 관련된 논의할 내용은 어떤 알고리즘을 사용하여도 똑같이 유효하다.

 둘째, 다른 학습 알고리즘들과 함께 사용될 수 있거나 사용할 때 가이드를 제공할 수 있는 기법들을 의미. 예를 들면, cross-validation과 resample 기법들은 수 많은 훈련 방법 중 어느 것과도 함께 사용될 수 있음

 

▶ In this chapter:

1. No pattern classification method is inherently superior to any other, or even to random guessing.
2. Several ways to quantify and adjust the match between a learning algorithm and the problem it addresses.
3. Methods for integrating component or expert classifiers, which themselves might implement quite different algorithms.

이번 장에서는

1.  먼저 어더한 패턴 분류 방법도 다른 것, 심지어 랜덤한 추측보다 본질적으로 우월하지 않음을 보게 될 것 (어떤 형태의 분류기가 최선의 성능을 제공할 것인지를 결정하는 것은 문제의 유형, 사전 확률 분포 및 다른 정보들임) 
2.  어떤 학습 알고리즘과 그것이 처리하는 문제 간의 "match(일치)"를 정량화하고 조정하는 몇 가지 방법을 다룰 예정 (어떤 특정 문제에 대해서든 물론 분류기 간의 차이가 있으며, 따라서 어떤 가정들을 사용하여 정확도를 추정해서 서로 다른 분류기들을 비교할 수 있음을 보여줌)
3.  "전문가" 분류기들을 통합하기 위한 방법 (이 방법은 자체가 또 다른 알고리즘을 구현할 수도 있음) 즉, 여러 알고리즘을 병합하면 좋은 성능을 낼 수 있음

 수업에서는 1, 2 내용을 다룰 예정이다.

 

9.2 Lack of inherent superiority of any classifier 

---

 어떠한 알고리즘도 성능이 절대적으로 우수한 것은 없다. (= Lack of inherent superiority of any classifier)

 이제 9.1에서 거론된 주요 질문을 시작 : 일반화 성능에 관심이 있다면, 한 분류기 또는 학습 알고리즘을 다른 것보다 좋아할 어떤 이유가 있는가? 분류 작업의 성격에 관해 아무런 사전 가정을 세우지 않는다면, 임의의 분류 방법이 전체적으로 볼 때 우월하거나 열등할 것으로 기대할 수 있는가? 랜덤한 추측보다 전반적으로 우월(또는 열등)한 알고리즘을 발견할 수 있는 것인가?

9.2.1 No Free Lunch Theorem (공짜 점심 부론 정리)

 정리 9.1 (No Free Lunch Theorem) : 임의의 두 학습 알고리즘 $P_1{h|D}$와 $P_2{h|D}$에 대해, 다음은 샘플링 분포 $P(\mathbf{x})$와 훈련 갯수 $n$과 무관하게 True(참)이다.

1. 모든 타겟 함수 $F$에 대해 균등하게 평균되면, $\varepsilon_1 (E|F,n) - \varepsilon_2 (E|F,n) = 0$
2. 임의의 고정된 훈련 집합 $D$에 대해, $F$에 대해 균등하게 평균되면, $\varepsilon_1 (E|F,n) - \varepsilon_2 (E|F,n) = 0$
3. 모든 사전 확률 $P(F)$에 대해 균등하게 평균되면, $\varepsilon_1 (E|F,n) - \varepsilon_2 (E|F,n) = 0$
4. 임의의 고정된 훈련 집합 $D$에 대해, $P(D)$에 대해 균등하게 평균되면, $\varepsilon_1 (E|F,n) - \varepsilon_2 (E|F,n) = 0$

  만일, 한 알고리즘이 어떤 특정 상황에서 다른 알고리즘보다 성능이 좋은 것으로 보인다면, 특정 인식 문제에 대해 적합했기 때문이지 알고리즘이 전반적으로 우월하기 때문은 아니다. 새로운 패턴 인식 문제를 대할 때, 이 정리에 대한 인식은 가장 문제가 되는 측면(사전 정보, 데이터 분포, 훈련 데이터 갯수, 비용/보상 함수 등)들에 초점을 맞출 것을 기억하자! 위의 "정리 9.1"은 또한 특정 학습 또는 인식 알고리즘의 전반적 우월성을 보여주고자하는 탐구들에 관한 회의론적인 생각을 가지게하는 정리이다.

  우선 분류기의 일반화 성능을 판단하는 방법을 더 깊게 생각해보자. 지금까지는 train data와 test data를 독립적으로 분리하여 성능을 추정했었다. 하지만, 특별한 경우에는 데이터를 독립적으로 분리한 경우 예기치 못한 단점들이 있다. 

1.  train data와 test data의 갯 수가 매우 크면 불가피하게 서로의 데이터가 중복되어있는 경우가 있을 것이다. 이를테면 train data에서 학습된 모델이 test data에도 너무 잘 맞아 일반화 성능을 판단하기 어려울 것이다.
2. 낮은 noise 또는 낮은 bayes error 경우들에 대해서, 만일 train data를 배우기에 충분할 정도로 효과적인 알고리즘을 사용한다면, i.i.d error의 상한은 train data 크기가 증가함에 따라 감소함.

 따라서 학습 알고리즘들을 비교하기 위해서는 off-training set error(비 훈련 집합 에러 : 훈련 집합에 없는 점들에 대한 에러)를 사용해야 한다. 만일 train data가 너무 크다면, off-training set data의 최대 규모는 물론 작아질 것이다.

9.2.2 Ugly Duckling Theorem (생략)

9.2.3 Minimum description length (생략) 

• specifically “simpler” classifiers over “complex” ones.

 "복잡한" 분류기들보다는 "더 간단한" 분류기들을 선호!

• the approach purports to find some irreducible, smallest representation of all members of a category (much like a “signal”); all variation among the individual patterns is then “noise.”

  "어떤 부류의 모든 멤버의 어떤 축소 불가능한, 가장 작은 표현을 찾는 것을 취지로 함

 우선 알고리즘 복잡도의 개념을 이해해보자.

9.2.4 Minimum description length principle (생략)

9.2.5 Overfitting avoidance and Occam’s razor

 패턴 분류기들에 관한 논의에 거쳐, regularization, pruning, inclusion of penalty terms, minimizing a description length 등 overfitting을 피하기 위한 기법들의 필요성을 언급해왔다. 앞에서 다룬 "No Free Lunch Theorem"에 의하면 위 기법이 왜 필요한지 아래와 같은 의문을 만들 것이다.

1. 한 알고리즘을 다른 것보다 선호할 아무런 문제가 없다면, 왜 overfitting을 피하기 위한 방법이 필요하여 사용되고 있는가?
2. 주어진 훈련 error에 대해, 왜 더 적은 feature와 parameter를 갖는 간단한 분류기들을 일반적으로 사용하고 있는가?

• In fact, techniques for avoiding overfitting or minimizing description length are not inherently beneficial; instead, such techniques amount to a preference over the forms or parameters of classifiers.
• It is the match of the learning algorithm to the problem – not the imposition of overfitting avoidance – that determines the empirical success.

 사실상, overfitting을 막기 위하거나 MDL을 사용하는 기법들은 본질적으로 좋은 방법은 아니다. 대신에, 그러한 기법들은 분류기의 형태 또는 parameter들에 대한 선호 또는 "bias"에 상응한다. (즉, 적합한 문제들을 처리하게 될 때만 유익함)

 문제에 대한 학습 알고리즘의 일치가 실험적 성공을 결정하는 것이지 overfitting을 피하게 강요한다고 되는 게 아님. (극단적으로 overfitting을 해결하는 기법은 실제로 성능을 더 나쁘게 만드는 문제들이 있음)

 책 내용에서 언급하는 전반적인 내용은 overfitting을 피하기 위한 방법에 대한 회의론적인 의견이지만, 그럼에도 불구하고 사용할 수 없는 이유를 풀어서 표현하고 있음

 다음 Ch9.3에서는 보다 구체적으로 분류기를 정량적으로 표현할 수 있는 bias와 variance에 대해 알아보며, 추가적으로 둘 사이의 관계를 알아볼 수 있을 것이다.

 

Reference

---

• pattern classification by richard o. duda