Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

당신이 이야기의 다음 단어나 노래의 다음 음표를 추측하려고 노력하고 있다고 상상해 보세요. 컴퓨터 과학의 세계에서 이것은 "시퀀스 예측(sequence prediction)"이라고 불립니다. 수십 년 동안 이를 완벽하게 수행하는 황금 표준은 **솔로모노프 귀납법(Solomonoff Induction)**이라는 이론적 아이디어였습니다. 이것을 아주 똑똑한 탐정이라고 생각해보세요. 이 탐정은 컴퓨터 프로그램이 이야기를 써 내려간 모든 가능한 방식을 조사합니다. 이 탐정은 모든 프로그램을 검토하며, 짧고 단순한 프로그램에는 큰 가중치를 부여하고, 길고 복잡한 프로그램에는 아주 미미한 가중치를 부여합니다. 만약 이 탐정이 우주의 모든 프로그램을 한꺼번에 확인할 수 있다면, 그 예측 오차는 이야기를 생성하는 프로그램의 복잡도에 의해 엄격하게 제한됩니다.

하지만 함정이 있습니다. 이 완벽한 탐정은 단 하나의 이야기에서 다음 단계를 추측하는 데는 뛰어나지만, 여러 가지 서로 다른 이야기들로 이루어진 전체 라이브러리로부터 "학습하는" 방법은 모릅니다. 만약 당신이 이 탐정에게 천 권의 서로 다른 책이 담긴 데이터셋을 보여준다면, 그는 "아, 패턴이 보이네. 다음 책은 아마도 이들과 비슷하겠군"이라고 말할 수 없습니다. 그는 각 새로운 이야기를 완전히 새로운 미스터리로 취급하며, 훈련 데이터로부터 이해도를 업데이트하지 못합니다. 이것은 현대의 인공지능(우리가 사용하는 챗봇과 같은)이 거대한 데이터셋을 통해 일반적인 규칙을 학습하는 방식이기 때문에 발생하는 문제입니다. 우리는 탐정의 완벽한 논리는 유지하면서도, 단 하나의 이야지가 아닌 전체 라이브러리의 예시로부터 학습할 수 있는 방법을 필요로 합니다.

여기서 네이선 영(Nathan Young)의 논문 "계층적 솔로모노프 귀납법: 무제한 머신 러닝 모델(Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model)"이 등장합니다. 저자는 업그레이드된 탐정인 **계층적 솔로모노프 귀납법(HSI)**을 제안합니다. HSI는 단순히 프로그램을 보는 것이 아니라, 그 프로그램을 생성하는 규칙을 봅니다. "메타 탐정"을 상상해 보세요. 이 탐정은 단순히 다음 단어를 추측하는 것이 아니라, 어떤 유형의 이야기 생성기가 사용되고 있는지를 추측합니다. HSI는 "하이퍼프라이어(hyperprior)", 즉 이야기를 쓰는 모든 가능한 방식에 대한 거대하고 가중치가 부여된 목록을 유지합니다. HSI는 훈련 예시가 담긴 데이터셋을 보면, 데이터에 부합하는 생성기의 가중치는 높이고, 부합하지 않는 생성기의 가중치는 낮추며 이 목록을 업데이트합니다.

이 논문은 두 가지 주요한 사실을 증명합니다. 첫째, 이 새로운 HSI는 단일 시퀀스를 볼 때 원래의 완벽한 탐정(솔로모노프 귀납법)과 수학적으로 동일함을 보여주며, 이는 원래의 예측 능력을 그대로 유지함을 의미합니다. 둘째, 더 중요한 점은 HSI가 머신 러닝 모델처럼 데이터셋으로부터 학습할 수 있음을 증명한다는 것입니다. 논문은 HSI에 점점 더 많은 데이터를 입력함에 따라, 평균 초과 오차(average excess error)가 줄어들어 결국 0으로 수렴하며, 데이터의 기저에 깔린 패턴을 완벽하게 예측할 수 있음을 보여줍니다. 저자는 HSI가 "이상적인" 머신 러닝 모델이라고 주장합니다. 즉, 무한한 컴퓨팅 파워를 가지고 있고 어떤 데이터셋으로부터도 학습할 수 있다면 시스템이 얼마나 잘 수행할 수 있는지를 보여주는 이론적 모델이라는 것입니다.

탐정의 새로운 초능력

이것이 왜 중요한지 이해하기 위해, 원래의 탐정인 **솔로모노프 귀납법(SolInd)**이 어떻게 작동하는지 살펴봅시다. 당신에게 어떤 컴퓨터 프로그램이든 실행할 수 있는 마법 상자가 있다고 가정해 봅시다. 당신은 텍스트 문자열의 다음 글자를 맞추고 싶습니다. SolInd은 "지금까지 본 텍스트를 작성했을 법한 모든 프로그램을 시도해 보자"라고 말합니다. 그것은 각 프로그램의 길이에 따라 점수를 매깁니다. 짧고 단순한 프로그램은 높은 점수를 받고, 길고 복잡한 프로그램은 매우 낮은 점수를 받습니다. 그리고 이 모든 점수를 결합하여 다음 글자를 추측합니다. 이것은 매우 영리한데, 만약 텍스트가 어떤 컴퓨터 프로그램에 의해 생성되었다면, SolInd은 그 프로그램의 복잡도에 의해 제한되는 오차 범위 내에서 결국 그것을 찾아낼 것이기 때문입니다.

하지만 여기 결함이 있습니다. SolInd은 약간 '한 가지 기술만 가진 동물'입니다. 그것은 단일 시퀀스의 다음 단계를 예측하도록 설계되었습니다. 만약 당신이 100개의 서로 다른 이야기를 "훈련"시키기 위해 데이터셋을 준다면, 그는 무엇을 해야 할지 모릅니다. 당신은 100개의 이야기를 하나의 거대한 문자열로 합쳐서 SolInd에게 입력할 수도 있겠지만, 그것은 프랑스어, 스페인어, 만다린어를 배우기 위해 그 언어들이 무작위로 붙여진 책을 읽는 것과 같습니다. 탐정은 그 "접착제"와 이야기들의 순서 때문에 혼란에 빠져, 실제 언어를 배우기보다는 그 순서를 설명하기 위한 복잡한 규칙들을 만들어낼 것입니다. 그는 현대의 AI처럼 "훈련"할 수 없습니다. 그는 한 번에 하나의 시퀀스에 대해서만 "테스트"할 수 있을 뿐입니다.

네이선 영의 논문은 이를 해결하기 위해 **계층적 솔로모노프 귀납법(HSI)**을 도입합니다. HSI를 상사가 있는 탐정이라고 생각해 보세요. 상사(하이프라이어)는 단순히 프로그램을 보는 것이 아니라, 프로그램이 작성되는 방식인 *분포(distributions)*를 봅니다.

모든 책이 서로 다른 작가에 의해 쓰인 도서관을 상상해 보세요.

• SolInd은 책 한 권을 읽고 다음 문장을 추측한 뒤 책을 덮는 독자입니다. 새로운 책이 도착하면, 그는 처음부터 다시 시작하며 이전 책에 대해 기억했던 것을 모두 잊어버립니다.
• HSI는 가능한 모든 작가의 목록을 가진 독자입니다. 그들은 새 책의 몇 페이지를 읽으면 자신의 목록을 확인합니다. "오, 이 스타일은 작가 A와 매우 비슷하군"이라고 생각하며, "작가 A가 필자일 확률을 높여야겠다"라고 판단합니다. 여러 권의 책을 읽을수록, 그들은 어떤 작가가 어떤 책을 쓰고 있는지 파 enough 잘 식별하게 됩니다. 그들은 단순히 다음 단어를 추측하는 것이 아니라, 전체 도서 컬렉션을 바탕으로 작가의 스타일을 추측하는 것입니다.

수학적 마법

이 논문은 HSI가 단순히 화려한 아이디어가 아니라 엄격한 업그레이드임을 증명하기 위해 수학을 매우 영리하게 사용합니다. 저자는 통계학의 개념인 **드 피네티의 정리(De Finetti's Theorem)**를 사용합니다. 간단히 말해, 이 정리는 만약 당신이 어떤 패턴을 따르는 것처럼 보이는 일련의 것들을 가지고 있다면(예: 순서가 상관없는 카드 덱), 그것들을 생성하는 어떤 숨겨진 규칙("잠재 변수")이 반드시 존재해야 한다는 것을 말합니다.

논문은 이를 컴퓨터 프로그램에 적용합니다. 저자는 우리가 시퀀스 데이터셋을 가지고 있다면, 그것들을 생성한 "진정한 생성기"(특정한 컴퓨터 프로그램 또는 규칙)가 존재한다고 주장합니다. HSI는 이 생성기를 숨겨진 변수로 취급합니다. HSI는 모든 가능한 생성자에 대한 확률 분포를 유지합니다. HSI가 데이터셋을 보면, 어떤 생성기가 진정한 것인지에 대한 믿음을 업데이트합니다.

논문은 놀라운 결과를 증명합니다: HSI는 수학적으로 SolInd와 동일합니다. 이는 만-약 당신이 HSI를 가져와 단일 시퀀스를 예측하게 한다면, 그것이 원래의 완벽한 탐정과 정확히 똑같이 수행하며, 오차는 생성자의 복잡도에 의해 제한된다는 것을 의미합니다. 하지만 HSI는 추가적인 초능력이 있습니다. 전체 데이터셋을 바탕으로 자신의 "상사"(하이프라이어)에 조건화(condition)될 수 있다는 것입니다.

저자는 HSI가 데이터셋을 예측할 때 발생하는 오차가 하이프라이어 내의 진정한 생성기의 "복잡도"에 의해 제한된다고 보여줍니다. 쉬운 말로: 만약 당신의 데이터를 만든 규칙이 단순하다면, H사 HSI는 빠르게 이를 학습하고 거의 실수를 하지 않을 것입니다. 만약 규칙이 복잡하다면 시간이 더 걸리겠지만, 논문은 데이터셋이 커짐에 따라 HSI의 평균 초과 오차가 0으로 떨어질 것임을 증명합니다. 즉, 극한의 상태에서 완벽한 예측으로 수렴합니다.

이것이 AI에 의미하는 바

이 논문은 HSI가 머신 러닝을 위한 "이상적인 무제한 모델"임을 시사합니다. 현재의 AI 모델들, 예를 들어 거대 언어 모델(LLM)은 본질적으로 HSI가 하는 일을 하려고 노력하고 있지만, 제한된 컴퓨팅 파워와 특정 아키텍처(예: 신경망)를 가지고 있습니다.

저자는 LLM이 종종 SolInd와 비교되지만, 그 비교는 불완전하다고 지적합니다. 왜냐하면 LLM은 실제로 데이터셋으로부터 학습하는 반면, SolInd는 그렇지 않기 때문입니다. HSI는 그 간극을 메워줍니다. HSI는 머신 러닝이 도달할 수 있는 이론적 천장을 제공합니다. 이는 만약 우리에게 무한한 컴퓨팅 파워와 학습을 위한 올바른 구조가 있다면, 어떤 데이터셋으로부터도 학습하고 미래를 최적의 정확도로 예측할 수 있는 시스템을 구축할 수 있음을 알려줍니다.

또한 논문은 실질적인 응용 분야, 즉 우리가 AI를 어떻게 훈련시키는가에 대해서도 다룹니다. 현재 우리는 종 때때로 하나의 긴 텍스트 문자열(문서들을 이어 붙인 것)을 AI에게 입력하여 훈련시킵니다. 논문은 HSI와 일치하는 더 나은 방법, 즉 각 문서를 모델의 "하이프라이어"를 업데이트하는 별개의 데이터 조각으로 취급하는 방식이 더 낫다고 제안합니다. 이는 문서를 단순히 이어 붙이는 것보다 개별 문서로 훈련하는 것이 더 효과적이라는 최근의 연구 결과와도 일치합니다.

함정

물론, 함정이 있습니다. 원래의 SolInd와 마찬가지로, HSI는 **계산 불가능(uncomputable)**합니다. 이는 무한한 수의 프로그램을 확인해야 하고 무한한 양의 메모리가 필요함을 의미합니다. 우리는 오늘날 실제 HSI를 구축할 수 없습니다. 이것은 하나의 "사고 실험"으로서, 우리가 도달할 수 있는 지능의 이론적 한계를 보여줍니다.

그러나 저자는 이것이 쓸모없다는 뜻은 아니라고 주장합니다. 완벽한 엔진을 만들 수 없다고 해서, 완벽한 엔진이 어떻게 작동하는지 이해함으로써 더 좋은 자동차를 만들 수 없는 것은 아닙니다. HSI는 우리에게 지도를 제공합니다. 현대의 AI가 학습하는 방식(데이터를 기반으로 믿음을 업데이트하는 방식)이 올바른 방향임을 보여주며, 우리가 이상에 얼마나 가까이 있는지 측정할 수 있는 수학적 방법을 제공합니다.

요약하자면, 이 논문은 과거의 "완벽한 탐정"을 데려와 "학습하는 상사"를 붙여주었습니다. 이 새로운 시스템인 HSI가 기존 탐정의 최적의 예측 능력을 유지하면서도, 전체 라이브러리의 예시로부터 학습할 수 있는 능력을 얻었음을 증명합니다. 이것은 가능한 최고의 머신 러닝 알고리즘이 존재하며, 그것은 시간이 지남에 따라 스스로 업데이트되는 확률의 계층 구조와 닮아 있다는 이론적 증명입니다. 비록 우리가 아직 그것을 직접 만들 수는 없지만, HSI는 우리가 정확히 무엇을 목표로 삼아야 하는지를 알려줍니다.