머신러닝의 이론적 기초를 한번 소개해 볼까함


소위 Probably Approximately Correct (PAC) learning이라고 부르는 이론인데,


현재 존재하는 머신러닝 방법론들 기반을 이루는 이론이라고 보면 됨


일단 아래처럼 용어들을 정리하고




용어가 생소할 수도 있지만 X,Y는 각각 실제 데이터의 집합, 레이블 집합이라고 보면 되고


C는 우리가 찾고 싶은 완벽한 함수들 c:X->Y의 집합, H는 우리가 세운 가설을 통해서 (예를들어 선형회귀, 로지스틱회귀, 딥러닝 etc) 만들 수 있는 함수들 h:X->Y 의 집합이라고 보면 됨.


그럼 학습 (learning)이라는 개념을 논리적으로 어떻게 정의할 수 있을까?


단순한 방법은 실제 데이터 X에 대해 올바른 레이블을 찾을 수 있는 완벽한 함수 집합 C를 찾으면 됨. 소위 consistency learning이라고 부름.


그럼 더 포말하게 consistency learning을 정의해보자.




위의 정의를 이용해서 완벽한 함수들의 집합 C가 consistency model learnable 인 경우, 우리는 트레이닝 데이터 S에 대해 consistent한 결과를 가지는 모델을 찾을 수 있음.


다만 위의 consistency model가 유용하기 위해서는 우리는 모든 경우의 수에 대한 데이터를 다 가지고 있다고 가정해야함


그렇지 않다면 작은 트레이닝 데이터에 대한 consistency만을 가정한 모델 (그래서 consistency model임)이기 때문에, 트레이닝 데이터를 제외한 unseen/test 데이터에 대해선 아무것도 알 수 없음.


하지만 현실에서 이러한 가정은 사실상 말이 안됨.


현실에서는 모든 데이터를 가지고 트레이닝 하는 경우는 거의 없고, 우리는 주어진 한정된 트레이닝 데이터로 가설 집합 (특정한 모델들, 선형회귀, 로지스틱, 등등)에서 함수 h를 찾아내야함.


다시말해서 주어진 트레이닝 데이터 집합 S가 주어졌을 때


모델 1 - 트레이닝 에러 0

모델 2 - 트레이닝 에러 0

모델 3 - 트레이닝 에러 0

모델 4 - 트레이닝 에러 0.05


이런 모델들이 있다고 치자


우리는 consistency model기준으로는 모델4는 모델 1,2,3 보다 좋지 않다는 것을 알 수 있음. 하지만 consistency model은 unseen/test data 에 대해서 어떠한 정보도 제공하지 않음.


그렇다면 위의 모델1, 모델2, 모델3 은 unseen/test 데이터에 대해서도 완벽하게 예측할 수 있을까? 그렇지 않다면 우리는 unseen data에 대해서 모델1,2,3의 일반화 오류를 계산할 수 있을까?


Probably Approximately Correct learning은 위의 질문에 대한 해답을 위해서 만들어진 이론임.





위의 정의를 보면 일반화 에러 (unseen data에 대한 에러)가 일정 기준 (epsilon) 이상일 확률이 delta 보다 낮은 경우 우리는 PAC-learnable이라고 정의할 수 있음.


즉 완벽한 함수 c:X->Y가 PAC-learnable이면 우리가 얻은 함수 h가 Probably (확률적으로) Approximately (근사적으로) Correct (올바른) 함수라는 것을 알 수 있음.


또한 위의 정의에서 바로 PAC-learning의 주요 정리 하나를 얻을 수 있는데








위의 정리를 이용하면 트레이닝 데이터의 수, generalisation error 파라메터들 (m, epsilon, delta) 사이의 관계를 알 수 있음.


즉, 트레이닝 데이터가 많아지면 많아질수록 exponential하게 모델의 에러 bound가 좁아진다는 것을 알 수 있음.



다만, 예시에서 나온 것 처럼 위의 PAC learning 은 트레이닝 데이터에 대해서 완벽한 (트레이닝 에러 0) 모델을 가정하고 있음. 그렇다면 현실에서 이러한 케이스를 찾을 수 없는 경우는 어떨끼? 조금더 일반화 하면 위의 이론은 완벽한 함수의 집합 C가 가설집합 H의 부분집합임을 가정하고 있음, 만약 그렇지 않은 경우는 어떨까?


또한 위의 정리1.3을 보면 |H|, 즉 가설집합이 유한해야한다는 것을 알 수 있음. 만약 가설집합이 무한한 경우에도 PAC learning을 이용해서 의미있는 generalisation bound를 얻을 수 있을까?


첫번째 질문은 agnostic PAC learning 이론으로, 두번째 질문은 Vapnik-Chervonenkis dimension 으로 이어짐


이둘은 나중에 다시 소개해볼께.