머신러닝의 학습 가능성과 괴델의 불완전성 정리
Source
Evernote/Inbox/미국 사는 수달의 마이피 ).md
Summary
네이처 머신 인텔리전스에 게재된 연구에 따르면, 머신러닝 알고리즘이 제한된 데이터에서 패턴을 추출하는 ‘학습 가능성(Learnability)’ 문제는 수학적으로 해결 불가능한 문제로 드러났다. 연구진은 학습 가능성과 데이터 압축의 관계를 집합론의 ‘연속체 가설(Continuum Hypothesis)‘과 연결 지었다. 괴델의 불완전성 정리와 코헨의 연구에 따라 연속체 가설은 표준 수학 공리 체계 내에서 참이나 거짓을 증명할 수 없다. 따라서 머신러닝의 학습 가능성 여부도 특정 공리 체계(연속체 가설의 진위)를 선택하지 않는 한 결정할 수 없는 ‘학습 가능성의 공백(Learnability limbo)’ 상태에 있음을 시사한다.
Key Points
- 머신러닝의 ‘학습 가능성’ 문제는 수학적으로 결정 불가능한(undecidable) 문제로 판명됨
- 학습 가능성은 집합론의 ‘연속체 가설’과 동치(equivalent)임이 증명됨
- 연속체 가설은 괴델과 코헨에 의해 표준 공리 체계 내에서 증명/반증 불가능함이 확인됨
- 따라서 머신러닝 모델이 유한한 샘플로 일반화할 수 있는지도 선택한 공리 체계에 따라 달라짐
- 이 연구는 머신러닝의 이론적 한계와 수학의 기초 이론(집합론, 불완전성 정리) 간의 깊은 연관성을 보여줌