레이 솔로모노프(Ray Solomonoff)

레이 솔로모노프는 1926년 미국 클리블랜드에서 러시아에서 온 유대인 이민자의 아들로 태어났습니다. 그가 평생 붙든 물음은 하나였습니다. 지금까지 본 자료에서 다음에 올 것을 어떻게 예측해야 하는가, 그리고 그 방법을 기계가 따를 수 있게 정확히 적을 수 있는가. 흄 이래 철학자들은 귀납이 논리로 정당화되지 않는다고 말해 왔지만, 솔로모노프는 정당화 대신 가장 좋은 귀납의 방법을 계산의 말로 정의하려 했습니다.

나이 세 ·

2차 세계대전 막바지에 해군에서 전자 장비를 가르친 뒤 시카고 대학에서 물리학을 공부했고, 그곳에서 철학자 루돌프 카르나프가 확률⁠(probability)⁠로 귀납을 설명하려는 시도를 배웠습니다. 카르나프는 문장들에 확률을 매기는 논리를 세우려 했지만, 무엇을 기본 문장으로 삼느냐에 따라 확률이 달라지는 문제를 끝내 풀지 못했습니다. 솔로모노프는 기본 단위를 문장 대신 프로그램으로 바꾸었습니다. 모든 계산을 흉내 낼 수 있는 튜링 기계⁠(Turing machine)⁠ 하나를 정하고, 그 기계의 모든 프로그램을 가설로 삼는 것입니다.

그는 대학에 자리를 잡지 않았습니다. 매사추세츠주 케임브리지의 작은 회사 제이터사와, 1970년에 세운 자기 회사 옥스브리지 리서치에서 주로 미 공군의 연구비를 받으며 거의 혼자 일했습니다. 1956년 여름 '인공지능⁠(artificial intelligence)⁠'이라는 이름을 처음 내건 다트머스 모임에 참석한 열 명 남짓 가운데 여름 내내 머문 몇 안 되는 사람이었고, 그해 확률로 배우는 기계에 관한 보고서 「귀납 추론 기계」를 돌렸습니다. 논리와 탐색이 주류이던 초기 인공지능에서, 확률로 배우는 기계를 말한 드문 목소리였습니다.

1960년 보고서와 1964년 두 부로 나뉜 논문 「귀납 추론의 형식 이론」에서 그는 오늘날 알고리즘적 확률이라 부르는 것을 내놓았습니다. 길이가 ℓ비트인 프로그램에 사전확률⁠(prior probability)⁠ 2^−ℓ을 주고, 지금까지의 자료로 시작하는 출력을 내는 프로그램들의 가중치⁠(weight)⁠를 모두 더해 다음 기호를 예측합니다(위의 식). 짧은 프로그램일수록 큰 몫을 가지니 베이즈 정리⁠(Bayes' theorem)⁠에 오컴의 면도날⁠(Occam's razor)⁠을 사전확률로 넣은 셈이고, 모든 계산 가능한 규칙을 가설로 품으니 '보편' 예측입니다. 프로그램을 적는 기계를 바꾸어도 사전확률이 상수배 이상 달라지지 않는다는 불변성도 그가 보였습니다.

이 생각은 거의 같은 무렵 모스크바의 콜모고로프(1965)와 뉴욕의 10대 학생 그레고리 차이틴(1966)이 따로 이른 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠와 한 뿌리입니다. 콜모고로프가 정보의 양을, 차이틴이 무작위성과 증명의 한계를 물었다면, 솔로모노프는 처음부터 예측을 물었다는 점이 다릅니다. 1978년 그는 자료가 어떤 계산 가능한 확률 규칙을 따라 나올 때, 보편 예측이 걸음마다 참 확률에서 벗어난 정도의 제곱을 끝없이 더해도 그 기댓값⁠(expected value)⁠이 규칙을 적는 가장 짧은 프로그램의 길이에 비례하는 값을 넘지 않는다는 정리를 발표했습니다. 규칙이 짧을수록 빨리 배운다는 뜻입니다.

대가는 계산할 수 없다는 것입니다. 어떤 프로그램이 끝내 멈출지 미리 알 수 없는 정지 문제⁠(halting problem)⁠ 때문에 모든 프로그램의 투표를 셀 수 없습니다. 솔로모노프는 이것을 결함이 아니라 이상으로 보았습니다. 실제로 쓸 방법들은 이 이상에 얼마나 가까운지로 평가하면 된다는 것입니다. 이 관점은 모형의 길이와 자료의 길이를 함께 재는 최소 기술 길이⁠(minimum description length)⁠, 마르쿠스 후터의 AIXI와 압축 대회로 이어졌습니다. 그는 2003년 첫 콜모고로프 상을 받았고, 2009년 세상을 떠났습니다.

이어지는 곳. 튀코의 표를 케플러의 세 줄로 줄이는 일을 비트로 세고, 솔로모노프의 혼합을 작은 판으로 직접 돌려 보는 이야기는 「압축하는 것이 이해하는 것이다」에 있습니다. 그 바탕인 콜모고로프 복잡도와 최소 기술 길이, 계산할 수 없는 까닭인 정지 문제는 각각의 페이지에서, 더 줄일 수 없는 것을 무작위로 보는 생각의 넓은 그림은 무작위성에서 볼 수 있습니다.

관계.

• 영향을 줌 안드레이 콜모고로프 — 콜모고로프는 1965년 따로 같은 복잡도에 이르렀고, 솔로모노프의 앞선 연구를 알게 된 뒤 그의 우선권을 인정했습니다. 그 인정이 솔로모노프의 이론이 널리 알려진 계기가 되었습니다.
• 함께 연구 마빈 민스키 — 1952년 무렵부터 알고 지냈고, 1956년 다트머스 모임에서 함께 여름을 보냈습니다. 민스키는 뒤에 솔로모노프의 알고리즘적 확률을 인공지능의 가장 중요한 발견 가운데 하나로 꼽았습니다.
• 함께 연구 존 매카시 — 다트머스 모임을 연 매카시와 귀납 추론 기계를 두고 이야기를 나누었고, 솔로모노프의 1956년 보고서는 그 모임에서 돌려 읽혔습니다.

연표.

• 1926년 오하이오주 클리블랜드에서 러시아계 유대인 이민자 집안에 태어나다
• 1944년 고등학교를 마치고 해군에서 전자 장비 교관으로 복무하다
• 1951년 시카고 대학에서 물리학 석사 학위를 받다. 카르나프의 확률 논리를 접하다
• 1956년 다트머스 여름 연구 모임에 여름 내내 머물고, 보고서 「귀납 추론 기계」를 돌리다
• 1960년 보고서 「귀납 추론의 일반 이론에 관한 예비 보고」에서 알고리즘적 확률을 내놓다
• 1964년 「귀납 추론의 형식 이론」 1·2부를 『인포메이션 앤드 컨트롤』에 싣다
• 1970년 자기 회사 옥스브리지 리서치를 세우다
• 1978년 보편 예측의 오차 합이 유한하다는 수렴 정리⁠(convergence theorem)⁠를 발표하다
• 2003년 런던 대학 로열 할러웨이의 첫 콜모고로프 상을 받다
• 2009년 세상을 떠나다