양성 표본만의 적정 학습 완전 규명, 표준 PAC와 갈라서는 학습이론 지형

기계학습 이론에서 가장 익숙한 그림은 학습기가 양성과 음성 사례를 라벨과 함께 골고루 받아보는 상황이다. 그러나 현실의 데이터는 종종 한쪽으로 치우쳐 있다. 사용자가 클릭한 문서, 실제로 적발된 사기 거래, 어떤 동물 종이 관찰된 장소처럼, 많은 기록은 '있었다'만 남기고 '없었다'를 명시하지 않는다. 음성 사례가 체계적으로 누락된 채 양성 사례만 손에 들어오는 이 설정에서 과연 신뢰할 만한 분류기를 배울 수 있는가. 이것이 1987년 Natarajan이 STOC에서 제기한 양성 표본 학습(positive-only learning) 문제이며, Ben-David와 동료들의 이번 연구는 그 한 갈래에 남아 있던 오랜 공백을 메운다.

양성만 보고 전체를 평가받는다는 역설

이 모델의 묘미는 학습과 평가의 비대칭에 있다. 학습기는 미지의 목표 개념이 양성으로 판정하는 영역에서만 독립 표본을 뽑아 본다. 음성 영역이 어떻게 생겼는지에 대한 직접적인 신호는 전혀 주어지지 않는다. 그런데도 학습 결과는 양성과 음성 모두에 질량을 두는 원래 분포 위에서 채점된다. 음성 쪽을 한 번도 보지 못한 채로, 양성과 음성을 가르는 경계를 잘 그려내야 하는 것이다. 직관적으로는 거의 불가능해 보이지만, 사실 비적정(improper) 버전의 답은 오래전에 알려졌고 교과서에도 실릴 만큼 정리되어 있다. 임의의 가설을 출력해도 된다면 유한 VC 차원이라는 익숙한 조건이 본질적으로 핵심을 잡아낸다.

남아 있던 문제는 적정(proper) 학습이었다. 적정 학습이란 출력하는 가설이 반드시 학습 대상이 되는 개념 클래스 안에 속해야 한다는 제약이다. 해석 가능성이나 표현의 일관성 때문에 실무에서 자주 요구되는 조건인데, 양성 표본만 주어지는 상황에서 이 제약이 언제 충족 가능한지는 30여 년간 열린 채로 남아 있었다. 이번 논문은 그 질문에 종지부를 찍는다.

유한 VC 차원만으로는 부족하다

핵심 정리는 간결하다. 어떤 개념 클래스가 양성 표본만으로 적정하게 학습 가능하려면, 유한한 VC 차원을 가져야 하고 동시에 저자들이 균일 외부 분리성(uniform exterior separability)이라 이름 붙인 새로운 조합론적 조건을 만족해야 하며, 그 역도 성립한다. 여기서 놀라운 대목은 유한 VC 차원이라는, 표준 PAC 학습에서는 사실상 만능 열쇠였던 조건이 이 세계에서는 충분조건이 되지 못한다는 점이다. 추가 조건은 양성 영역 바깥, 즉 보이지 않는 음성 영역을 클래스 내부의 개념들로 균일하게 분리해낼 수 있느냐를 묻는다. 보지 못한 곳을 다룰 능력을 클래스 구조 자체가 미리 갖추고 있어야 한다는 직관이다.

이 규명과 함께 제시되는 여러 분리 결과가 이 분야의 지형을 표준 PAC 학습과 선명하게 갈라놓는다. 표준 PAC에서는 한 덩어리로 묶여 있던 개념들이 여기서는 따로 논다. 적정 학습과 비적정 학습이 실제로 분리되고, 무작위 적정 학습과 결정적 적정 학습 사이에도 진짜 간극이 생긴다. 무작위성을 허용하면 결정적으로는 배울 수 없는 클래스를 배울 수 있다는 뜻이다. 더 충격적인 것은 어떤 클래스에서는 그 어떤 경험적 위험 최소화(ERM) 규칙도 학습기가 되지 못한다는 사실이다. ERM이 곧 학습이라는 통념이 이 설정에서는 무너진다. 게다가 유한 VC 차원은 비균일(non-uniform) 학습조차 보장하지 못한다.

이론적 도구로서의 가치

이 연구가 당장 어떤 제품의 성능을 끌어올리는 종류의 결과는 아니다. 그러나 양성 사례만 관측되는 약지도(weakly-supervised) 상황은 추천, 이상 탐지, 생태 모델링, 의료 기록 분석 등에서 끊임없이 재등장하는 구조이며, 이때 어떤 가설 클래스가 안전하게 학습 가능한지를 가르는 정확한 경계가 무엇인지 아는 것은 실용적 함의를 갖는다. 저자들이 논의 과정에서 도입한 새로운 조합론적 차원들 역시 양성 표본 학습을 넘어 학습이론 전반에서 재사용될 여지가 있다. 표준 PAC 학습이 오랫동안 제공해온 깔끔한 직관 — 유한 VC 차원이면 충분하고 ERM이면 된다 — 이 한 꺼풀 벗겨진 자리에서, 데이터의 비대칭이 학습 가능성의 본질을 어떻게 바꾸는지를 이 논문은 정밀하게 보여준다.