상대적 스마트 학습 이론: 준지도 및 표본 최적화 연구
Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
arXiv연구진은 미지의 분포에 대한 오류를 레이블링된 데이터의 복잡도 증가 없이 통제하는 '상대적으로 스마트한 학습' 이론을 제시했습니다.
- 지도학습 환경에서 ERM이 상대적 스마트함을 보였으며, 특히 준지도 학습은 오직 미표본 데이터만으로 오류를 통제하는 높은 효율성을 입증했습니다.
- 이는 레이블링된 데이터가 부족한 실제 환경에서도 대규모 미표본 데이터를 활용하여 모델의 일반화 성능과 신뢰도를 높일 수 있는 이론적 기반을 제공합니다.
- 다만, 높은 레이블 효율성을 달성하는 과정에서는 계산의 복잡성이 증가할 수 있으며, 특정 조건에서 기하급수적인 오라클 호출이 필요하다는 한계가 존재합니다.
연구진은 이분 분류의 분포 비의존적 환경에서 ERM(Empirical Risk Minimization)이 상대적으로 스마트함을 입증했습니다. 구체적으로, $m$개의 표본으로 작은 인증 가능한 오류가 존재한다면, 이는 크기가 $O(m^2)$인 무작위 샘플에 대한 균일 분포에서도 유사하게 작은 오류를 의미합니다. 이 결과는 $O(m^2)$의 표본을 가진 적절한 일관 학습기의 오류를 제어할 수 있음을 보여줍니다.
나아가, 준지도 상대적 스마트 학습은 정보 이론적으로 가능하며, 미표본 데이터 복잡도에 대해서만 이차적인 증가가 발생하고 레이블링된 표본 복잡도에서는 증폭이 없다는 것을 보였습니다. 이 학습 방식은 유한 풀의 일부 레이블을 공개하는 트랜스덕티브 문제에 OIG(One-Inclusion Graph)의 자연스러운 일반화를 활용합니다.
다만, 이러한 높은 레이블 효율성은 단순성과 계산 가능성 측면에서 비용이 발생합니다. 가설 클래스가 비지식적 ERM 오라클을 통해서만 접근 가능하다면, 실질적으로 준-이차적인 레이블 표본 증가를 가진 상대적 스마트 학습기는 슈퍼 다항식(super-polynomially) 많은 오라클 호출을 필요로 합니다. 이 한계는 주변 분포가 명시적으로 주어지는 경우에도 성립합니다.