A Theory of the Learnable(1984)

Artificial Intelligence and Language Processing

 

무언가를 깊게 이해하기 위해서는 그에 대한 역사와 변혁과정을 아는 것이 중요하다.

머신러닝의 초기 아이디어와 어떻게 발전해왔는지에 대해 알고싶었다.

레딧에서 추천한 리스트를 기반으로 논문들을 정리해보고자 한다.

 

A Theory of the Learnable - L. G. VALIANT(1984)는 기계가 학습한다는 것에 대한 개념이 없었을 때, 어떻게 하면 기계가 사람이 무언가를 학습하는 과정을 모방할 수 있을까에 대한 아이디어에 대해 다룬 논문이다. 논문 전반적으로 propositional calculus에 대한 내용이 자주 등장한다. propositional calculus (명제논리)는 명제에 논리합과 같은 논리연산을 통해 구성한 명제들을 다루는 논리체계라고 한다. 듣기만 해도 어려운 이 논리수학 자체보다는 이 논리수학을 어떻게 기계에 implement하려고 했는지에 중점을 두고 읽어봐야겠다.

 

ABSTRACT: Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learned using it in a reasonable (polynomial) number of steps. Although inherent algorithmic complexity appears to set serious limits to the range of concepts that can be learned, we show that there are some important nontrivial classes of propositional concepts that can be learned in a realistic sense.

 

ABSTRACT : 인간은 새로운 컨셉을 배울 때, 기존에 있던 감각들을 바탕으로 컴퓨터처럼 프로그램하지 않아도 된다. 이 논문에서 우리는 '학습'을 'explicit programming 없이 지식을 얻는 현상'으로 정의한다. computational viewpoint에서 어떻게 학습에 대해 연구할지에 대한 방법론에 대해 얘기하고자한다. 알맞는 정보 수집 메커니즘, 학습 프로토콜, 그리고 적당한 (polynomial) 수의 연산을 통해 학습될 수 있는 컨셉들의 종류를 포함한다. 알고리즘적인 복잡도가 '학습'될 수 있는 컨셉들의 범위를 제한하긴 하지만, 우리는 현실적으로 학습될 수 있는 명제적 컨셉들을 선보이고자 한다.

 

INTRODUCTION

Computability theory는 기계적 연산으로 설명될 수 있는 보편적인 현상이 정확한 모델로 설명될 수 있을 때 가능해진다. 이 이론은 인간 경험에 대해 설명하고 인공적 컴퓨팅 기기들의 필요성에 대해 설명한다. 

학습에 대한 현상도 computability theory와 비슷하다. 논점은 인간 경험과 그에 대한 학습이 가능한 디바이스를 만드는 것과 밀접한 관련이 있는 적합한 모델들을 발견하는 것이다. 이 모델들은 computatbility가 어떤 것이 compute 가능하고 불가능한지에 대해 설명하는 것처럼, 무엇이 학습 가능하고 무엇이 불가능한지에 대한 이해를 높여줄 것이다.

이 논문에서 우리는 목적한 업무를 explicit programming이 아닌 다른 방법을 통해 성취한 것을 '학습'했다라고 정의한다. 명확히 선천적으로 미리 프로그램된 요소들도 있지만, 다른 몇몇은 지시 과정 (sequence of instructions)을 통해서 실행되는 것들도 있다. 일일이 명시하여 프로그래밍해서 설명할 수 없는 스킬 습득 영역이 아직 많이 남아있다. 이 부분이 우리가 학습으로 묘사하고자 하는 부분이다. 익숙한 물체 인식하는 기술 등이 그 예이다. 이러한 기술들은 추가적인 특성이 있는데, 우리가 배우고 나서도, 특별히 어떻게 배웠는지에 대한 알고리즘적 부분에 대해 설명하기 어렵다는 것이다. 이럴 때 기계가 학습할 수 있도록 한다면 정말 놀라운 결과라고 할 수 있을 것이다. 

이 논문은 '학습' 현상에 대한 정확한 computational 모델들에 대해 고민한다. 우리는 다시 이 '학습'을  '입력값이 우리가 정의한 특정한 컨셉이 맞는지 아닌지에 대해 인지하는지'로 제한할 수 있을 것이다. 만약 외부 프로그램으로부터가 아닌 다른 방법을 통해 답을 추론한다면 이는 컨셉을 '학습'했다고 할 수 있을 것이다.

이 논문의 주된 공헌은 다음의 세 가지 특성을 갖춘 '학습하는 기계'를 디자인할 수 있을 것이라고 증명한 것이다.

 

1. 기계는 아마 컨셉의 모든 클래스에 대해서 배울 수 있다. 또한, 이 클래스들은 분류될 수 있다.

2. 컨셉의 클래스들은 보편적인 지식에 대해 적당하고 유의미하다.

3. 기계가 결과를 추론하는 데에 필요한 연산적 프로세스는 feasible (여기서 합리적, polynomial)하다. 

 

'학습 기계'는 '추론 과정'과 함께 'learning protocol'을 포함한다. 'learning protocol'은 외부로부터 어떻게 데이터를 수집할 것인지에 대해 세부적으로 설명하고, '추론과정'은 타겟으로 정한 컨셉이 올바르게 인지될 수 있게 하는 '인지 알고리즘'이 어떻게 추론되는지에 대한 메커니즘을 의미한다. 가장 추상적인 레벨에서 '학습'을 연구한다는 것은 다음의 '방법론'들을 의미한다: 합당한 'learning protocol'을 정의하고, 그 'learning protocol'을 사용하여 인지 프로그램들이 'polynomial' 시간 안에 추론해낼 클래스에 대해 조사한다. 

여기서 포로토콜들은 두가지의 정보 공급을 허락한다. 첫번째는 'learning machine'이 컨셉을 올바르게 예제화하는 데이터들에 대한 액세스가 있어야한다는 것. 이 긍정적 예제들은 자연적으로 생성된 '확률분포'를 가질 것이라고 예측된다. A call of a routine EXAMPLES produces one such positive example. 각자 다른 예들을 생성하는 상대적 확률은 이 분포에 의해 정해질 것이다. (대충 데이터들의 확률 분포를 뽑아볼 수 있다면, 이 분포가 데이터를 만들 때 어떤 클래스에 속할지에 대한 확률에 영향을 미칠 거라는 뜻) 두번째로 필요한 정보는 routine ORACLE이다. (여기서 말하는 EXAMPLES와 같은 맥락인 것 같은데...) ORACLE의 가장 기본적이 버젼은 주어진 데이터가 컨셉을 예제화(대표)하는지 안 하는지에 대한 것이다.

가장 중요한 모델 디자인 요소는 어떻게 지식을 대표할지에 대한 부분('knowledge representation')이다. 보편적인 지식을 대표하는 것이 우리의 목표이기 때문에, formal grammars나 기하학적 구조(geometrical constructs)보다는 '논리' 같은 것을 사용해야하는 건 당연해보인다. 이 논문에서 우리는 명제논리의 집합의 불리안 함수와 같은 컨셉을 사용할 것이다. 그러므로 우리가 추론하려는 인식 알고리즘은 불리안 써킷이나 표현들이다. 

실용적 학습 시스템들에서 지식을 대표하기 위해 사용되는 명제논리의 적합성은 명백히 중요하면서도 논란이 있는 질문이다. 오직 몇몇만이 이 정도의 힘 (명제논리를 사용할 정도의)이 필요하지 않을 거라고 할 것이다. 진짜 질문은 이게 충분한지에 대한 것이다. (명제논리보다 더 expressive한 도구가 필요하지 않을까.) 명제논리는 적어도 좋은 시작점이다.  첫번째로 preprogrammed knowledge를 내포한 시스템의 유명한 예제들을 평가한다고 할 때, DENDRALRHK MYCIN 와 같은, 명제논리 그 이상의 논리적 기호들은 근본적으로 필요하지 않다. programmed systems로 관리될만한 concept보다 더 강력한 preprogrammed knowledge를 내포한 학습 시스템을 과한 욕심이긴 하다. Second, the results in this paper can be negatively interpreted to suggest that the class of learnable concepts even within the propositional calculus is severely circumscribed. 이건 명제 논리가 학습할 수 있는 것보다 더 큰 컨셉의 클래스들을 위한 확장 (명제논리보다 더 복잡한 도구를 찾는 것) 힘들다는 것을 의미한다.

 

 

-----이어서

의역해야할 부분과 애매모호한 단어들이 너무 많다....