Abstraction & Reasoning in AI systems : (4) discrete program search

NeurIPS 에서의 < Abstraction & Reasoning in AI systems : Modern perspectives > 강연을 보고 그 중에서도 Francois Chollet 의 "why abstraction is the key, and what we're still missing" 에 대해 정리해보겠다.

(해당 강연은 https://slideslive.com/38935790/abstraction-reasoning-in-ai-systems-modern-perspectives 이 링크에서 확인할 수 있다.)

 

<4> what are the methods that are currently working to generate the form of abstraction that is out of reach for deep learning

- discrete program search : how to learn to reason

 

 

** Discrete program search : how to learn to reason

 

그렇다면 딥러닝이 할 수 없는 program-centric abstraction 형태인 reasoning, planning 문제들, 예를 들면 ARC 와 같은 문제, 리스트를 정렬하는 문제, 소수를 찾는 문제와 같은 문제들은 어떻게 해결해야 할까?

 

- 답은 "program synthesis" (프로그램 합성) 이다.

 

즉 도메인 특정 언어인 DSL(domain specific language) 에서 가져온 연산자의 그래프에 대한 combinatorial search (결합 검색)이다.

이것은 그래프에 대한 discrete 검색이고, 특히 유전자 프로그래밍과 같은 여러 종류가 있다.

 

아래와 같이 머신러닝과 program synthesis 사이에 유사점을 찾을 수 있다.

 

 

** 머신러닝  VS  프로그램 합성

 

 

 

머신러닝에서는 모델이 미분가능한 매개변수의 함수이다.

그리고 프로그램 합성에서는 도메인 특정 언어에서 온 연산자들의 그래프가 모델이다.

 

머신러닝에서는 학습 엔진이 stochastic gradient descent(확률적 경사 하강)이라면, 프로그램 합성에서는 combinatorial search(조합 검색)이다.

 

- 머신러닝에서 주요 장애물은 문제 매니폴드에 대해 dense 한 sampling 이 필요하다는 점이었다면, 프로그램 합성에서의 주요 장애물은 combinatorial explosion(조합 폭발)이다.

 

- 딥러닝과 달리 프로그램 합성을 사용하여 적은 예시로도 문제를 해결할 수 있다. 그러나 빌드할 수 있는 가능한 프로그램 집합은 프로그램 크기와 함께 증가하기 때문에 매우 expensive 하다고 볼 수 있다.

 

 

 

또 프로그램 합성, 특히 유전자 프로그래밍은 비록 이제 시작이지만 ARC 에서 꽤 성공적이라고 할 수 있다.

 

지금까지 ARC 에 대한 모든 상위 솔루션들은 거의 동일한 템플릿을 사용한다.

바로 DSL(도메인 특정 언어) 을 가지고 있다는 점과 이 DSL 로 만들어진 가능한 프로그램을 검색한다는 점과, 보다 효율적인 검색을 위해 휴리스틱(스스로 발견하게 하는 체험적)을 사용한다는 점이다.

이 시스템들은 여전히 극히 원시적이고, 이들은 combinatorial explosion(조합 폭발)의 주요 문제를 해결하기 위해 거의 노력을 기울이지 않으며, 현재 program-centric abstraction 을 활용하지 않는다.

 

그래서 이 유전자 프로그래밍은 DSL 의 하드 코딩된 구성 요소들을 복잡한 알고리즘이 아닌 exhaustive search(철저한 검색)과 결합하는 것이다. 비록 매우 원시적이긴 하지만 ARC 문제 해결에 있어서는 딥러닝보다 훨씬 더 성공적이다.

 

 

** continuous optimization & program synthesis 효율적으로 만들기

 

한가지 매우 중요한 것은 continuous optimization 이나 program synthesis 나 실제로 사용하려면 이것들을 효율적으로 만들어야 한다는 것이다.

그리고 효율성을 위해서는 주로 modularity(모듈식의, 여러 개 개별단위로 되어있어 선택조립할 수 있는), hierarchy, reuse 가 필요하고, 이 reuse 는 abstraction 과도 같은 말이다.

 

 

* 딥러닝은 continuous optimization 에 modularity 와 hierarchy 를 추가하면 효율적으로 만들 수 있다.

 

즉 매개변수함수를 계층들의 깊은 스택으로 구조화하고(=hierarchy), 하드 코드한 abstract module (=modularity)을 continuous optimization 에서 재사용(=reuse)하면 딥러닝 아키택처 패턴을 얻게 된다.

 

- 예를 들어 컨볼루션은 공간 위치를 추상화하는 하드 코딩된 모듈이고, 위치에 관한 추상적인 개념이다.

- 마찬가지로 RNN 은 시간적 “for” 루프를 가진 모듈이다. RNN 의 데이터의 다른 시간 단계는 동일한 하위 모듈에 의해 처리되어야 하고, 그래서 시간 축에 대해서는 추상적이다.

 

그리고 modularity, hierarchy, reuse 를 이용해 더 효율적으로 만드는 것은 discrete combinatorial optimization 에도 동일하게 적용된다.

따라서 모듈화 및 계층화를 중심으로 하는 경향이 있는 소프트웨어 아키텍처 모범 사례를 따르는 프로그램으로 검색을 제한하여 효율적으로 만들 수 있다. 그리고 program-centric abstraction 와도 같은 “function reuse”을 시작해 효율적으로 만들 수 있다.

 

 

* 프로그램 합성 은 두가지 도구를 통해 효율적으로 만들 수 있다.

: abstract function reuse(추상적 기능 재사용) & limit branching decision (분기 결정 제한)

 

추상적 기능 재사용  + combinatorial explosion 방지를 위해 프로그램 공간을 줄일 때 더 현명한 분기 결정을 내릴 수 있다. 그리고 이 때 딥러닝을 사용할 수도 있다.

 

 

** program synthesis 에 program-centric abstraction 활용하기

 

 

- symbolic module reuse(program centric abstraction) 에 대해 간단히 말해보자면,

 

일반적인 아이디어는 주어진 DSL 로 시작하고 프로그램 검색을 실행하여 ARC 작업과 같은 다양한 문제를 해결한다는 것이다.

따라서 솔루션 프로그램을 생성한 다음 프로그램 내에서 또는 프로그램 간에 하위 그래프 isomorphism 을 식별하기 시작하고

이러한 하위 프로그램들을 발견하면 다시 사용할 수 있는 함수로 추상화하여 그 함수를 다시 DSL 에 추가하는 것이다.

그리고 다시 검색을 계속한다.

 

이제 검색에는 아까의 추상 기능이 포함되었을 것이고 이는 소프트웨어 엔지니어링 모범 사례와 매우 유사하다. (ex.오픈소스 라이브러리 재사용)

 

그리고 위의 방법 (symbolic module reuse) 은 프로그램 합성을 더 효율적으로 만드는 매우 중요한 방법 중 하나이다.

 

 

하지만 프로그램 합성을 향상시키는 보완적이면서도 훨씬 강력한 방법이 있다.

바로 프로그램 합성과 딥러닝을 결합하는 것이다.

 

프로그램 검색 공간을 줄이고 combinatorial explosion 을 방지하는 방법으로 딥러닝을 활용하면 된다.

따라서 딥러닝이 지금까지 ARC 유형 문제에 사용되지 않았다는 사실이 딥러닝이 필요없다는 것을 의미하지는 않는다.

 

 

 

 

다음 글에서 프로그램 합성을 향상시키는 강력한 방법, 즉 딥러닝과 프로그램 합성을 결합하는 방법에 대해 다뤄볼 예정이다.

 

 

 

 

(출처 : 해당 글의 이미지들은 NeurIPS 의 < Abstraction & Reasoning in AI systems : Modern perspectives > 강연 발표자료에서 가져왔다. )