PAC 학습 (probably approximately correct learning)
한 줄 정의: 높은 확률로 거의 정확한 가설을 배울 수 있는지를 따지는 학습 이론의 틀입니다.
쉽게 풀면
학습이 성공했다는 말을 수학적으로 정의하려는 시도입니다. 완벽하게 맞히는 것은 불가능하니, “오차가 ε보다 작은 가설을 1−δ 이상의 확률로 찾아낸다”는 두 겹의 느슨함을 허용합니다. 그리고 이 조건을 만족하려면 표본이 몇 개나 필요한지를 계산합니다.
왜 중요한가
머신러닝을 경험적 기술이 아니라 증명 가능한 학문으로 다루게 해 준 출발점입니다. 모델의 복잡도와 필요한 데이터 양 사이의 관계를 정량화하기 때문에, 표본 크기가 부족할 때 일반화가 무너지는 현상을 이론적으로 설명할 수 있습니다. 계산학습이론 논문에서는 거의 모든 결과가 이 틀 위에서 진술됩니다.
논문에서는 이렇게 쓰입니다
"해당 가설 공간은 PAC 학습 가능하며, 요구되는 표본 복잡도는 VC 차원에 선형으로 비례하는 것으로 나타났다."
이 모델군은 이론적으로 학습이 보장되며 필요한 데이터 양이 모델 복잡도에 비례해 늘어난다는 의미입니다.
조금 더 깊게 보면
1984년 레슬리 밸리언트가 제안했으며, 어떤 개념 부류가 PAC 학습 가능하다는 것은 ε과 δ, 그리고 문제 크기의 다항식 시간·표본 안에서 학습 알고리즘이 존재한다는 뜻입니다. 학습 가능성의 조건은 가설 공간의 VC 차원이 유한한지와 밀접하게 연결되어 있습니다. 데이터에 잡음이 섞인 상황을 다루는 불가지론적(agnostic) PAC 학습으로 확장되어, 최적 가설과의 상대적 격차를 보장하는 형태로도 널리 쓰입니다.
주의할 점
PAC 학습이 가능하다는 결과는 충분한 표본이 있을 때의 존재 증명이지, 실제 알고리즘이 효율적으로 그 가설을 찾아낸다는 보장과는 다릅니다. 교차검증이 특정 데이터에서 성능을 경험적으로 추정하는 절차라면, PAC는 데이터 분포 전체에 대한 최악의 경우 보장을 다룹니다.