머신 러닝과 연속체 가설

최근 Nature에서 머신 러닝 저널 Nature Machine Intelligence를 런칭했다. 이에 대해서 기존 머신 러닝 연구과 업계 종사자들은 기존 오픈 억세스 기반의 학계 분위기와는 맞지 않는 폐쇄적 저널 시스템을 지적하며 이 저널에 투고, 검토 등을 하지 않겠다는 청원서에도 많은 사람들이 몰렸다는 등 부정적인 시선이 많은 듯하다. 이러니 저러니 했지만 일단 1월호가 나왔는데 그 중 한 논문이[1] 굉장히 흥미로웠다.

샘플링을 토대로 적절한 가설을 찾아 가능한 한 오차를 줄이면서 예측하는 것이 기본적인 (statistical) learning 문제라 할 수 있고, 이 때 필요한 샘플의 개수를 잡을 수 있을지에 대한 개념이 learnability로 정의된다. PAC(probably approximately correct) learnability가 많이 언급되는데, 거의 확실하고 (나쁜 샘플에 의한 실패 확률이 있을 수도 있음) 거의 정확하게 (이상적인 값에서 약간의 오차를 허용) 맞추는 모델을 뜻한다. 이 PAC learnability는 치역이 인 경우 좀 더 간단한 파라메터인 VC dimension이란 이산적인 값이 유한한가의 여부로 결정된다는 것이 증명되어 있고, 이를 통계적 학습의 기본 정리(fundamental theorem of statistical learning)라고 부른다.

위와 같은 경우 learnability를 완벽히 따질 수 있는데, [1]에서는 특정 학습 모델의 경우 learnability가 ZFC와 독립적이라고 한다. 그 증명을 위해 이 논문에서는 연속체 가설을 이용한다. 연속체 가설은 cardinality가 정수의 집합과 실수의 집합 사이에 있는 무한집합이 있는지 유무를 묻는 힐베르트 문제 중 하나로 유명한데, 괴델이 연속체 가설은 ZFC로 반증 불가임을 보이고 코언이 ZFC로 증명 불가임을 보여 괴델의 불완전성 정리의 한 예시가 된 것으로 유명하다.

구체적으로, 어떤 정의역 와 그 위에서의 확률 분포 가 주어져 있되 우리에게 알려져있지 않은 상태에서, 의 부분집합들로 이루어진 family 가 주어져 있을 때 에 속하는 집합 중 measure가 최대에 가까운 것을 잡기 위해 에서 유한개의 샘플을 i.i.d.하게 뽑는 샘플링을 시행하는 것을 생각한다. 이를 EMX(estimating the maximum) 문제라고 하고, 논문에서는 소비자들의 집합 가 있고 광고 에 대해 이에 관심 있는 사람들의 집합 들을 생각해서 좀 더 많은 사람에게 해당하는 광고를 찾는 문제의 예시를 들고 있다.

그러면 가 실수 구간 의 모든 유한 부분집합이고 고려할 확률분포 클래스 는 의 finite support를 갖는 모든 확률분포들로 이루어졌다고 할 때, 의 EMX learnability는 ZFC 공리와 독립적이라는 것이다. 구체적으로,이 EMX-learnable함은 정수의 집합과 실수의 집합 사이에 유한히 많은 cardinality가 있음과 동치가 된다는 것.

complexity, computability, undecidability 같은 개념처럼 학습 모델의 learnability란 개념도 연구되며 기계학습의 이론적 바탕을 완성하고 있다는 것도 흥미로웠고 연속체 가설과 연결되는 결과 자체도 흥미로웠다.

트윗 타래를 정리. (2019/01/09)

Update (2019/01/20): 트친분이 알려주셨는데 이 연구는 실제 머신러닝 연구와 거리가 많이 동떨어져 있으며 non-Borel measurability에 기초하는 등 다소 과대한 관심을 받고 있다는 지적이 있었다. 네이쳐의 언플이 과하다는 이야기. 그와는 별개로 저자 중 한 명인 Shai Ben-David는 앞서 언급한 이 저널에 대한 보이콧 청원에 동참했었다고. 그는 자기 이름을 논문에 올린 적이 없다고 하며, 누군가가 그의 이름을 올렸을 가능성도 있음.

https://t.co/I9bwuygmAT ML 연구하던 수학자들이 알고리즘이 주어진 데이터에서 패턴을 추출할 수 있는지를 연구하는 learnability 관련 문제가 칸토어의 연속체 가설과 관련이 있다는 것을 밝혔다고

— 유닼 (@udaqueness) January 9, 2019

References

[1] S. Ben-David, P. Hrubeš, S. Moran, A. Shpilka and A. Yehudayoff, “Learnability can be undecidable” Nature Machine Intelligence, 1, 44-48. DOI: 10.1038/s42256-018-0002-3