Github갤에도 올렸는데 머신러닝의 이론적 기초를 소개하는 글임.
소위 Probably Approximately Correct (PAC) learning이라고 부르는 이론인데,
현재 존재하는 머신러닝 방법론들 기반을 이루는 이론이라고 보면 됨. Theoretical computer science에서는 나름 중요한 주제 중 하나임.
일단 아래처럼 용어들을 정리하고
용어가 생소할 수도 있지만 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의 집합 C가 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 으로 이어짐
이둘은 나중에 자세히 소개해볼께.
이론컴퓨터과학에 대한 서적에서 발췌한 건가요? 자세히 읽어보지는 않았는데 한 번 읽고 싶네요. 아니면 논문인가?...
이제 latex링크가 안걸려서 직접 latex으로 쓰고 스크린샷으로 캡쳐한거임. 위의 내용은 이론컴퓨터과학, 특히 computational learning theory 관련 책들에서 자세히 공부할 수 있음. 다만 머신러닝 교과서들은 위의 내용은 전부 생략하는 경우가 많음.
머신러닝 교과서에서도 PAC나 Vapnik dimension 정도는 간략하게나마 다루더라구요
물론 쓰는 교재에 따라서 다르긴 한데, 머신러닝 이론서라고 유명한 책들 중에서 PAC이론 다루는 책보단 안다루는 책들이 더 많은 것 같다는 ㅎ 그냥 개인적인 생각임 ㅎㅎ
아 이거 분명 러신머닝 수업때 다룬 내용인데 기억이 안나네;;
이상하게 썼는데 읽히누ㅋㅋㅋ
러닝머신 인줄 ㅋㅋ
마지막 증명에 첫 부등식은 어떻게 유도된거야?
h 함수 하나가 모든 트레이닝 데이터 m에 대해서 올바른 확률 (1- epsilon)^m, 다만 이건 하나의 함수 h에 대한거잖아? bound를 씌우기 위해선 가설 집합 모든 함수의 크기를 넣어줘야함 lHl (1-epsilon)^m 이걸 definition 1.2에 넣으면 됨
이런거 다루는 원서 추천좀여.. 비숍이랑 esl은 다 봤는데 이거 신기하네요
ㅇㅇ 유명 책들인데 PAC는 한마디도 없는 책들, 아마 책 요소가 조금 더 실무위주라서 그럴지도, PAC를 다룬 머신러닝 교과서 중 개인적으로 좋아하는 책은 Shai Shalev-Shwartz, Shai Ben-David의 Understanding Machine Learning: From Theory to Algorithms
신경망이 Random label에서도 error 0나오는거 논문 이후로는 어떻게 얘기가 진행됨?