Valiant의 학습 가능성 이론에서 학습 가능한 것은 무엇인가?

Valiant의 1984년 논문은 PAC 학습 (PAC learning) 모델을 도입한 것으로 널리 인정받고 있지만, 사실은 다른 모델을 도입했습니다. PAC 학습과 달리, 학습자는 오직 양성 (positives) 샘플만을 받으며, 멤버십 쿼리 (membership queries)를 발행할 수 있고, 거짓 양성 (false positives)이 없는 가설을 출력해야 합니다. 이전 연구들은 쿼리가 없는 경우를 포함하여 다양한 변형들을 규정해 왔습니다. 우리는 Valiant의 원래 모델을 재검토하며 다음과 같은 질문을 던집니다: 이 모델에서 학습 가능한 클래스는 무엇인가? Valiant의 불리언 하이퍼큐브 (Boolean-hypercube) 설정을 포함하여 모든 유한 도메인 (finite domain)에 대해, 우리는 클래스가 학습 가능하다는 조건이 모든 실현 가능한 양성 샘플이 다항식 크기의 적응형 쿼리 압축 스킴 (poly-size adaptive query-compression scheme)에 의해 인증될 수 있을 필요충분조건임을 보여줍니다. 이는 학습자가 멤버십 오라클 (membership oracle)과의 짧은 상호작용을 통해 샘플을 인증하는 샘플 압축 (sample compression)의 새로운 변형입니다. 우리의 규명에 따르면, Valiant 모델에서의 학습 가능성은 PAC 모델에서의 학습 가능성과 멤버십 쿼리가 없는 Valiant 모델의 변형 사이의 엄격한 샌드위치 (sandwiched) 구조를 가집니다. 이는 멤버십 쿼리의 도입이 단순히 샘플 복잡도나 계산 복잡도만을 바꾸는 것이 아니라, 학습 가능한 클래스의 집합 자체를 변화시키는 드문 사례 중 하나입니다. 다음으로, 우리는 이 모델을 임의의 도메인으로 확장한 자연스러운 확장을 연구합니다. 정확한 규명을 얻지는 못했지만, 우리의 기술은 쉽게 일반화되어 동일한 엄격한 샌드위치 구조가 지속됨을 보여줍니다. 마지막으로, 우리는 쿼리 없이는 학습할 수 없는 $d$-차원 반공간 (halfspaces)이 쿼리가 있으면 학습 가능하다는 것을 보여줍니다. 우리는 $\mathrm{poly}(d) \tilde{O}(1/ε)$ 샘플 및 $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ 쿼리 알고리즘을 제시하며, 최소 $Ω(d)$의 샘플 또는 쿼리가 필요함을 증명합니다. 우리가 알기로는, 이것이 Valiant 모델에서 반공간을 위한 최초의 알고리즘입니다. 종합적으로, 이러한 결과들은 Valiant의 독창적인 학습 가능성 개념 뒤에 숨겨진 놀라울 정도로 풍부한 이론을 밝혀내며, 학습 이론 (learning theory)에서 독립적으로도 흥미로울 수 있는 아이디어들을 소개합니다.