복잡도 이론 (Complexity Theory)을 통해 ML을 통한 인간 수준의 성능 구현이 불가능함이 증명된 것은 아니다 [D]

Van Rooij, Guest, Adolfi, Kolokolova, 그리고 Rich는 2024년 Computational Brain & Behavior에서 ML을 통한 AGI 구현이 불가능함을 증명했다고 주장했습니다. 기본적인 아이디어는 알려진 NP-hard 문제를 데이터로부터 인간 수준의 분류기 (classifier)를 학습하는 문제로 환원(reduce)하려는 시도였습니다. 저자들이 "Ingenia Theorem"이라 명명한 이 주장된 결과는 이곳을 포함하여 인터넷상에서 소란을 일으켰습니다.

해당 증명이 회복 불가능할 정도로 잘못되었음을 보여주는 저의 논문이 이제 CBB에도 게재되었습니다 (제한 없는 프리프린트(preprint)는 여기에서 확인 가능합니다).

근본적인 문제는 "인간 수준의 분류기 (human-level classifier)"가 수학적으로 정의되지 않았다는 점이며, 저자들은 이를 ... 정의하지 않음으로써 해결하려 했다는 것입니다. 그들은 문제를 도입할 때 "인간의 상황-행동 튜플 (human situation-behaviour tuples)의 분포"에 대응하는 구조를 사용하지만, 정식 증명을 수행할 단계에 이르면 이 구조를 "모든 다항 시간 샘플링 가능한 분포 (for all polytime-sampleable distributions)"로 교체해 버립니다. 이는 만약 인간의 상황-행동 튜플을 ImageNet의 입력/레이블로 찾아 바꾸기(find-and-replace) 한다면, 해당 논문이 ImageNet을 분류하는 법을 배우는 것이 난해하다(intractable)는 것도 증명하게 된다는 의미입니다.

Penrose부터 Chomsky에 이르기까지 유사한 시도들에 대한 블로그 포스트 논의는 여기에서 볼 수 있습니다.