[기계학습 2주차A] 귀납적 편향과 PAC 학습
가설만으로 문제를 풀 수 있을까?
제시된 불리언 함수를 살펴보자. 입력 (x1, x2)는 총 4쌍으로 2bit 신호라는 instance space J가 된다. 가설 공간 H는 4bit 신호 16쌍으로 구성되어 있다.
4쌍의 입력 중 첫 번째인 (0, 0)이 입력되었다고 생각해보자. 만약 (0, 0)에 대한 label이 0이라면 h1~h16의 가설 중 h1~h8의 여덟 개의 가설이 consistent하다고 할 수 있다.
만약 다음 입력 데이터가 (0, 1)인데 이에 해당하는 label은 1이라면, 앞선 여덟 개의 가설 중 h5~h8의 4개 만이 consistent한 가설로 줄여진다.
이런 식으로 4개의 학습 데이터를 모두 입력했을 때, 가설 16개 중 하나는 consistent하게 된다. 즉 존재하는 모든 다이코토미에 consistent한 가설 h가 모두 존재하므로 이 함수의 VC 차원은 4이다. 바꿔말하면 앞선 4개의 학습 데이터 외에 다섯 번째 입력이 들어온다면, 이 불리언 함수는 그것의 label을 제대로 판별해내지 못한다.
이런 식으로 생각을 해보자. 4쌍의 입력 중 앞의 2가지 입력인 (0, 0)과 (0, 1)이 들어와서 h5~h8의 4개의 가설만이 consistent하다고 가정하자. 이때 테스트 입력으로 (1, 0)이 들어오면 이 불리언 함수는 label을 0과 1 중에 뭘로 판단할까?
h5와 h6에선 0으로, h7과 h8에선 1로 판단되므로 2:2 동률이 된다. 따라서 이 불리언 함수에서는 단 2가지의 input만으론 3번째 input을 판단할 수 없다. 바꿔말하면 “학습 데이터가 아닌 입력에 대한 추론을 하지 못하고 있다”. 이건 기계학습으로서 실패한 것이 아닌가?
이런 경우를 Ill-posed problem이라고 한다. 해결방법을 잘못 구성한 문제를 말한다. 머신러닝으로서 학습이 제대로 이뤄지지 않고 있는 것이다. 그렇다면 이러한 문제를 해결할 방법은 없을까?
귀납적 편향(Inductive Bias)
이때 필요한 것이 편향(bias)이다. 통계학에서의 편향과는 조금 다르다. 번역이 이래서 그렇지, 나라면 ‘편견’으로 옮겼을 것 같다. 선입견은 우리가 판단을 빠르게 하는 데에 도움을 준다. 이런 선입견을 생각해보자는 거다.
앞서 family car문제에서 0과 1을 구분할 때 우리는 축에 평행한 직사각형을 활용했다. 이런게 inductive bias다. 비슷한 예로 kNN 문제에서 “가까이 있는 input끼리는 같은 class일 것이다”라는 편향이 잘 먹힌다.
\[B\;s.t.\;\forall x\in J[(B\wedge D\wedge x)\vdash L(x|D)]\]이 수식은 편향 B와 데이터 D 및 입력 x를 토대로 할 때, label L이 결정되는 객체 공간 J에 모든 입력 x값이 존재한다는 것이다. 쉽게 말하면 편향 B를 활용해 모든 레이블을 추측할 수 있다는 것이다. 이게 귀납적 편향의 힘이다.
이런 편향을 바탕으로 알고리즘이나 가설 공간 H, 객체 공간 J 등의 모델을 결정할 수 있는데, 이를 model selection이라 한다. 이때 model이 너무 복잡해지거나 단순해지면 model의 정확도가 떨어질 수 있다.
대표적인 귀납적 편향으로 오켐의 면도날(Ockham’s razor)이라는 것이 있다. “Simplest is the Best! 쳐낼 수록 좋다”라는 뜻이다.
컴퓨터 과학을 포함한 모든 이론에서 간단한 모델은 큰 효과를 발휘하는데, 특히 잘못된 입력(input error)이나 아직 알아내지 못한 특성(hidden attributes)을 놓치는 경우를 방지한다.
하지만 너무 모델이 단순할 경우 과소적합(Underfitting)이 일어나는데, 분산은 줄어들지만 데이터의 에러(통계적 의미의 bias)가 늘게 된다. 반대로 모델이 너무 복잡하면 과적합(Overfitting)이 일어나 에러는 줄어들지만 분산이 너무 커지게 된다. 따라서 적절한 Complexity의 모델을 찾는 것이 중요하다.
교차 검증(Cross Validation)
그렇다면 그 적절한 Complexity를 어떻게 찾는가? 교차 검증(cross validation)을 통해 찾을 수 있다. 실무적 의미의 교차 검증은 train dataset의 일부를 validation 과정에 사용하는 것이지만, 여기서의 교차 검증은 검증 데이터를 통하여 hyperparameter를 최적화하는 과정을 의미한다.
학습 데이터는 기본 parameters를 조정한다면, 검증 데이터는 hyperparameters를 조정하는 데에 쓰인다. 이때 하이퍼파라미터를 조정하며 error가 가장 적은 지점에서의 복잡도(complexity)가 최적의 복잡도인 것이다. 이후 테스트 데이터셋을 통해 최종 결과를 기록한다.
여기서 trade-off가 있는데, 가설공간이 복잡해질수록 처음엔 (bias가 줄면서) error의 개수도 줄어들지만, 가면 갈수록 점점 (variance가 늘면서) error가 커지게 된다. 즉 과적합도 과소적합도 좋지 않다. 다만 데이터가 커지면 에러는 줄어든다. 객체(학습) 공간이 클수록 일반화 에러가 감소하기 때문이다. 이를 Triple Trade-off라 한다.
PAC Learning
그렇다면 triple trade-off의 두 번째 특성인 “N이 커질수록 E가 줄어든다”에서 N은 어느 정도일까? N에 따른 E가 기준치보다 내려갈 확률이 특정 수치 이상일 때, 우리는 이 모델이 PAC-learnable하다고 표현한다.
\[P\{E(h)\le \epsilon\}\ge 1-\delta\]위 수식에서 엡실론은 에러(error)를, 델타는 실패확률을 의미한다. 즉 가설 h에 대하여 에러가 엡실론보다 작아질 확률이 1-delta라는 성공확률보다 높을 때, 학습이 잘 된다는 것이다. 보통 1-delta는 90% 이상으로 잡는다. 그렇다면 정확히 어느 정도의 N이 있을 때 PAC Learnable할까?
먼저 Target Concept c에서의 오류율이 엡실론보다 작다면, 그 안의 가설 h에서의 오류율(오류의 개수로 생각하면 더 편하다)은 더 작을 것이다. c에서 실증적 에러가 10개가 있었다면 h에서는 그보다는 더 적은 6, 7개의 에러가 있지 않겠는가? 따라서 이 경우 PAC learnable하다.
반면 c에서의 오류을이 엡실론보다 컸다면, 최소한 가설 h에서의 오류율은 엡실론보다 더 작게 설정해야한다. 여기서 앞서 다룬 귀납적 편향이 등장한다. ‘직사각형 모양의 4개의 strip이 있다’는 inductive bias를 토대로 각각의 strip에서 1/4 엡실론만큼의 확률로 instance를 뽑을 수 있다고 가정해보자.
그렇다면 instance 하나를 뽑았을 때 이것이 특정 strip(여기선 보라색으로 표시돼있다) 바깥에서 뽑힐 확률은
\[1-\frac{\epsilon}{4}\]이다. N개의 instances를 뽑는다면
\[(1-\frac{\epsilon}{4})^N\]이 된다. 따라서 4개의 strip에서 N개의 instances가 하나도 뽑히지 않을 확률은 최대 \(4(1-\frac{\epsilon}{4})^N\)이다. (strip의 영역이 겹친다든가하여 이보다 더 작을 수 있기 때문)
그렇다면 반대로 N개의 샘플을 뽑았을 때 모든 strip에서 적어도 하나씩 뽑힐 확률은
\[1-4(1-\frac{\epsilon}{4})^N\]인데, 앞서 가정한 바에 따라 4개의 strip에서의 에러는 엡실론보다 작으며, 그 에러율은 1-delta라는 성공률보다 커야한다. 따라서
\[1-4(1-\frac{\epsilon}{4})^N\ge 1-\delta\]가 된다.
자 이제 우리가 찾고 싶어하는 N의 최소 개수를 보이겠다. 뜬금없지만 항등식 \(1-x\le exp(-x)\)을 들고오겠다.
항등식의 x에 epsilon/4를 대입하면
\[1-\epsilon/4\le exp(-\epsilon/4)\]이다. 양변을 N제곱을 하면
\[(1-\epsilon/4)^N\le exp(-\epsilon/4)^N\]이고 이후 양변에 -4를 곱하고 1을 더해주면
\[1-4(1-\epsilon/4)^N\ge 1-4exp(-\epsilon/4)^N\]가 된다. 이때 좌변은 앞서 말한대로 1-delta보다 커야하므로, 우변인 \(1-4exp(-\epsilon/4)^N \ge 1-\delta\)이 더 크다고 놓는다고 놓아도 좌변이 더 크다는 사실은 변하지 않는다.(사실 여기부터 수학적으로 엄밀하다고 보긴 어려울 듯)
식을 정리하면
\[exp(-\epsilon/4)^N \le \delta/4\]이므로 양변에 자연로그를 취하면
\[-N\epsilon/4 \le ln(\delta/4)\]에서
\(N \ge \frac{4}{\epsilon}ln(\frac{4}{\delta})\)
가 된다!!
해석하자면 에러율 epsilon과 실패율 delta를 줄이기 위해서(더 적은 에러가 발생) 샘플의 수 N을 늘려야 한다는 결론이다.
출처: 기계학습(COSE362) ㅇㄷㅅ 교수님