티스토리 뷰

Study/AI

[Machine Learning] Generalization bound

생각많은 소심남 2014. 4. 16. 21:36


수업시간에 다룬 Vapnik - Chervonenkis generalization(VC generalization) 을 표현해봤다. 우리가 Machine Learning을 하는 이유 자체는 개념에도 담겨있다시피 기계를 학습시키기 위함이고, 당연히 미래에 들어올 데이터에 대한 예측을 요구하는 것이다. 이를 위해서는 기존에 받아둔 Sample Data를 가지고, 그 Sample에 대한 hypothesis를 구해서, 최종 결과와 비교해야 한다. 당연히 sample에 대한 hypothesis가 최종 결과와 거의 비슷하게 나오면, 이 hypothesis를 가지고 미래에 들어올 Data를 구별하게 될 것이다. 보통 이런 개념을 In-sample Error와 Out-of-Sample Error간의 차이로 표현하기도 한다. 

 그런데 그 Sample Data의 갯수를 무작정 늘리면 좋을까? 물론 많은 sample이 있기 때문에 조금더 미래에 나올 Data에 대해서 예측을 하기 쉬울 것이다. 그런데 그걸 저장할 공간과 계산하는데 드는 cost를 고려해보면 sample이 무조건 많다고 좋은 건 아니라는 결론을 내리게 된다. 그래서 이에 필요한 Sample 갯수와 예측값에 대한 관계를 언급한 것이 Generalization이라는 것이고, 이걸 하나의 관계식으로 표현할 수 있다. 위의 그래프가 그걸 표현한 것이다. 원래 수식은 이렇다.



처음에 이런 관계를 정립한 것이 맨위에 있는 vapnik & chervonenkis 이고, 그 이하 Rademacher나 Parrondo, Devroye는 그 error bound를 조금더 낮추기 위해서 최적화를 한 결과다. 잘보면 알겠지만 Parrondo bound나 Devroye bound는 우변에 epsilon값이 들어 있는 것을 알 수 있다. 결국 이걸 epsilon에 관한 식으로 풀기 위한 방정식을 세워야 하고, 위 그래프에 나온 결과가 그렇게 나온거다.


댓글