PAC 학습 이론 창시자 레슬리 밸리언트 인터뷰: 기계학습 이론 40년의 전개와 교육 가능성이라는 다음 질문

핵심 메시지

• 밸리언트는 계산 복잡도 연구를 하다가 '인간의 능력을 설명하지 못하는 이론은 부족하다'는 문제의식으로 학습 이론에 뛰어들었다.
• PAC(확률적 근사 정확) 모형의 핵심은 학습에 쓰인 분포에서만 잘 작동하면 된다고 요구 조건을 낮춘 것이고, 그 덕에 어떤 분포에서든 학습이 가능해졌다.
• 계산이 어려운 문제와 학습이 어려운 문제는 다르며, 3항 논리곱 정규형처럼 판정이 어려운 대상도 PAC 학습은 가능하다는 결과가 이 분야의 출발점이 됐다.
• 반대로 유한 오토마타 학습은 RSA 같은 암호체계를 깨는 것만큼 어렵다는 것이 증명돼, 특정 문법 학습 시도가 실패해 온 이유를 설명했다.
• 밸리언트는 지금 학습과 추론, 지시를 통한 배움을 하나로 묶은 '교육 가능성'이라는 더 큰 개념을 정의하려 하고 있다.

쉽게 이해하기

스탠퍼드 디지털이코노미랩의 팟캐스트 '머신러닝, 우리는 어떻게 여기까지 왔나'에서 진행자 톰 미첼이 하버드 교수이자 튜링상 수상자인 레슬리 밸리언트를 만났다. 주제는 특정 알고리즘의 성능이 아니라 그 아래에 놓인 질문이다. 학습은 언제 가능한가, 그리고 어느 정도 정확도를 보장하려면 사례가 몇 개나 필요한가 같은, 학습자가 컴퓨터든 사람이든 통하는 이론이다.

밸리언트는 자신의 출발점이 앨런 튜링의 논문이었다고 말한다. 수학과 물리를 공부하던 그에게 계산 가능성보다 흥미로웠던 것은 인간의 사고에 한계가 있다는 함의였다. 그러나 이후 10년간 그가 한 연구는 인간과 무관한 계산 복잡도였고, 1980년대 초 다시 인공지능 쪽을 바라보며 여러 분과 중 가장 근본적인 것이 기계학습이라고 판단했다. 확률과 통계가 답의 일부지만 통계학자들이 놓친 계산의 측면이 있을 것이라는 직관이 PAC 모형으로 이어졌다.

그가 사람들을 설득한 결과는 각 절에 변수가 셋인 논리곱 정규형 수식에 관한 것이었다. 이 수식은 만족 가능성을 판정하는 일이 계산적으로 어렵다고 이미 알려져 있었는데도, 학습은 가능했다. 학습자는 입력이 나오는 분포에서 잘 예측하기만 하면 되므로, 거의 등장하지 않는 희귀한 사례까지 알아낼 필요가 없기 때문이다. 계산의 어려움과 학습의 어려움이 다른 층위에 있다는 것을 보여준 대목이다.

진행자는 당시 이 모형이 준 해방감을 회고한다. 훈련 분포와 시험 분포가 같다고 두면, 실제로 마주치지 않을 사례에서 가설들이 어떻게 갈리는지 걱정할 필요가 없어진다. 밸리언트도 이 제약이 부담스럽지 않으면서 동시에 세상의 형태를 전혀 제한하지 않는 유연함을 준다는 점을 강조한다. 이후 1980년대에는 가설 공간의 복잡도 측정과 학습 가능성 특성화 연구가 쏟아졌고, 밸리언트는 '인공지능 겨울'이라는 말과 무관하게 흥분된 시기였다고 기억한다.

이론이 낳은 성과 중 그가 먼저 꼽은 것은 부스팅이다. 어떤 분포에서든 조금이라도 학습할 수 있다면 그 능력을 증폭해 일반적인 경우까지 학습할 수 있다는 발상이 실용적인 기법이 됐다. 반대 방향으로는 학습 불가능성 연구가 있었다. 그는 이 모형이 표준 데이터셋으로 실험을 반복하는 연구 관행에도 명확한 목표를 제공했다고 본다.

요즘 그의 관심은 더 넓다. PAC 학습이 기계학습이라는 블랙박스를 잘 설명했다면, 인지의 더 큰 덩어리도 정의 가능한 형태로 붙잡을 수 있는지가 40년째 붙들고 있는 질문이다. 그는 최근 책 '교육 가능하다는 것의 중요성'에서 학습과 추론, 상식, 지시를 통해 배우는 능력, 서로 다른 시점에 얻은 지식을 이어 붙이는 능력을 하나로 묶으려 했다. 대학원생에게 주는 조언은 소음을 무시하고 스스로 근본적이라 여기는 것을 좇으라는, 지키기 어려운 원칙이었다.

주요 인사이트

• 문제를 어떻게 정식화하느냐가 결과를 좌우한다는 교훈이 밸리언트의 복잡도 연구 경험에서 나왔다. 아무렇게나 목표를 세우면 거의 모든 것이 계산적으로 어려워지므로, 실현 가능한 무언가를 담아낼 수 있게 조심스럽게 정의해야 한다는 것이다.
• PAC 모형은 요구를 낮춘 대신 적용 범위를 넓힌 사례다. 학습 대상 분포에서만 잘하면 된다는 제약을 받아들이자 인위적 가정 없이 임의의 분포를 다룰 수 있게 됐다.
• 학습 불가능성 증명이 암호학과 연결된 지점이 흥미롭다. 유한 오토마타를 예시로부터 학습하는 일이 RSA를 깨는 것만큼 어렵다는 결과는, 촘스키 위계의 언어를 학습하려던 시도들이 왜 성공하지 못했는지를 설명해 준다.
• 밸리언트는 이론 연구를 두 종류로 나눈다. 아직 아무도 제대로 붙잡지 못한 개념을 정의하려는 미래 지향적 작업과, 이미 이해된 개념을 더 깊이 분석하는 작업이다. 두 가지 모두 필요하다는 것이 그의 입장이다.
• 잡음 모형에 관해서는 여전히 정답이 없다고 인정한다. 여러 형태의 잡음 모형이 제안됐지만 어느 것이 옳은 모형인지는 아무도 모른다는 것이다.

자주 묻는 질문

관련 AI 소식