상대적으로 똑똑한 학습: 인증 가능한 오차로 최악의 경우 분석을 넘어서는 학습 이론

핵심 메시지

• PAC 모델의 최악의 경우 분석은 현실적인 분포에서 지나치게 비관적이며, 분포마다 다른 학습기를 써야 더 잘하는 경우도 있다.
• 분포를 아는 학습기와 상수 배 이내로 겨루는 '스마트 학습'은 일반적으로 불가능하다는 것이 이미 알려져 있다.
• 불가능의 원인은 비지도 학습의 실패를 넘어선다. 분포를 알려 줘도 그것이 거짓인지 레이블 없는 데이터만으로는 잡아낼 수 없다.
• 새 틀은 '인증 가능한' 성능만 인정하도록 기준을 낮춰, 구별 불가능성을 벤치마크에 미리 반영한다.
• 분포 자유 설정에서는 표본 수를 제곱으로 늘리면 모든 가설 집합에 대해 이 기준을 달성할 수 있고, 이 제곱은 더 줄일 수 없다.

쉽게 이해하기

서던캘리포니아대의 샤딘 두그미가 워털루대 박사과정생과 함께 쓴 논문을 TTIC 콜로퀴엄에서 발표했다. 출발점은 학습 이론의 오래된 불만이다. PAC 모델은 학습기를 분포에 대한 최악의 성능으로 평가하는데, 현실에서 마주치는 상당수 분포는 사실 쉽다. 이때 경험적 위험 최소화 같은 표준 학습기의 분석이 과하게 비관적일 수도 있고, 더 나아가 그 분포에 맞춘 다른 학습기를 썼다면 훨씬 잘했을 수도 있다.

그래서 발표자가 던지는 질문은 '분포마다, 인스턴스마다 통계적으로 최적인 학습기를 얻을 수 있는가'이다. 여기서 최적성은 계산량이 아니라 표본 복잡도 기준이며, 분포는 레이블 없는 데이터의 주변 분포를 뜻한다. 목표를 다르게 말하면, 분포를 미리 알지 못하는데도 마치 완벽히 그 분포에 맞춰 설계된 학습기만큼 해내는 것이다.

이 목표를 형식화한 기존 개념이 2011년에 제안된 스마트 학습이다. 주변 분포를 아는 최적의 학습기, 즉 레이블 없는 데이터를 무한히 가진 준지도 학습기와 보편 상수 배 이내로 겨루면 스마트하다고 부른다. 발표자가 든 예시는 대다수가 0이고 소수의 점만 1인 '한쪽으로 쏠린' 가설 집합인데, 여기서 경험적 위험 최소화는 표본이 적을 때 다수 레이블을 통째로 틀릴 수 있는 반면 훈련에서 더 자주 본 레이블을 그대로 예측하는 단순한 학습기는 훨씬 잘한다.

문제는 후속 연구가 스마트 학습이 일반적으로 불가능함을 보였다는 점이다. 그것도 표본을 제곱이나 지수만큼 더 줘도 뚫리지 않는 견고한 불가능성이다. 발표자는 그 이유를 한 걸음 더 파고든다. 이것은 단순히 비지도 학습이 주변 분포를 충분히 배우지 못하는 문제가 아니다. 누군가 주변 분포를 알려 주면서 거짓말을 해도, 레이블 없는 데이터만 들여다봐서는 그 거짓을 잡아낼 방법이 없다는 것이 더 근본적인 장벽이다.

그래서 제안된 것이 '상대적으로 똑똑한 학습'이다. 분포에 맞춰진 최선의 오차 전부와 겨루는 대신, 레이블 없는 데이터만으로 인증할 수 있는 오차와만 겨룬다. 학습기에 짝지어진 인증기는 레이블 없는 데이터를 받아 그 학습기의 오차에 대한 타당한 상한을 내놓아야 하며, 구별할 수 없는 다른 분포에서 학습기가 못한다면 인증기는 추정치를 올릴 수밖에 없다. 이렇게 구별 불가능성을 벤치마크에 미리 반영하는 것이 이 틀의 핵심이다.

주요 인사이트

• 분포 자유 설정의 주요 결과는 긍정적이다. PAC 학습이 가능하든 아니든 모든 가설 집합은 표본 수를 제곱으로 늘려 주면 상대적으로 똑똑한 학습기를 갖는다. 이를 달성하는 것은 아무 학습기나가 아니라 일-포함 그래프 학습기다.
• 증명의 직관은 생일 역설이다. 표본 m개만으로는 참 분포와, 그 분포에서 뽑은 m제곱 개의 점 위 균등분포를 구별할 수 없다. 그래서 인증 가능한 오차는 후자에서의 최선을 밑돌 수 없고, 학습기에 m제곱 개를 주면 문제는 사실상 하나 빼고 다 아는 상태에서의 예측이 되는데 그 최적해가 바로 일-포함 그래프다.
• 제곱이라는 대가는 줄일 수 없다. 발표자는 어떤 가설 집합에서는 제곱보다 나은 표본 증가율로는 상대적 스마트함을 얻을 수 없다는 하한을 함께 제시했다.
• 분포 집합을 좁히면 오히려 어려워질 수 있다는 역설적 결과도 나온다. 분포를 더 허용하면 학습기의 일도 어려워지지만 인증기의 일도 어려워져 벤치마크가 함께 느슨해지기 때문에, 난이도가 분포 집합에 대해 단조롭지 않다.
• 발표자가 남긴 가장 흥미로운 미해결 문제는 경험적 위험 최소화가 상대적으로 똑똑한지 여부다. 그는 아니라고 추측하지만 증명이 까다롭다고 밝혔고, 일-포함 그래프 학습기가 일반적으로 다루기 쉬운 편이 아닌 만큼 더 단순하거나 다항 시간에 돌아가는 대안이 있는지가 다음 과제로 남는다.

자주 묻는 질문

관련 AI 소식