적절한 양성 전용 학습(Proper Positive-Only Learning)에서의 놀라운 발견들

양성 전용 샘플(positive-only samples)로부터의 이진 분류(Binary classification)는 학습자가 미지의 타겟 개념(target concept)의 양성 영역(positive region)으로부터 i.i.d. 샘플을 받지만, 원래의 분포(양성 및 음성 영역 모두에 질량을 두는 분포) 하에서 평가되는 PAC 학습의 변형입니다. 이 모델은 Natarajan [1987, STOC]까지 거슬러 올라가며, 부적절한 학습(improper learning)의 특성화는 잘 알려져 있어 교과서에도 등장합니다. 그러나 적절한 양성 전용 학습(proper positive-only learning)의 특성화는 오랫동안 미해결 과제로 남아 있었습니다. 본 연구에서 우리는 이 문제를 재검토하고 해결합니다: 개념 클래스(concept class)가 양성 전용 샘플로부터 적절하게 학습 가능(properly learnable)하기 위한 필요충분조건은 해당 클래스가 유한한 VC 차원(VC dimension)을 가지며, 우리가 균등 외부 분리 가능성(uniform exterior separability)이라고 부르는 새로운 조합론적 조건을 만족하는 것입니다. 여러 분리 결과(separation results)와 함께, 이 특성화는 표준 PAC 학습과는 극명하게 다른 놀라울 정도로 풍부한 지형을 드러냅니다: 적절한 학습(proper learning)과 부적절한 학습(improper learning)이 분리되어 있으며, 무작위적(randomized) 적절한 학습과 결정론적(deterministic) 적절한 학습이 분리되어 있고, ERM(Empirical Risk Minimization)이 학습자가 될 수 없는 클래스들이 존재하며, 유한한 VC 차원이 비균등 학습(non-uniform learning)에 대해서조차 충분하지 않다는 점을 보여줍니다. 이 과정에서 우리는 학습 이론(learning theory)에서 더 넓은 관심을 끌 수 있다고 믿는 새로운 조합론적 차원(combinatorial dimensions)들을 소개합니다.