논문 Learning Compositional Rules via Neural Program Synthesis - Maxwell, I. et al. (2020) 리뷰를 해보겠다.
앞의 논문에서 다뤘던 SCAN 문제에 대해 neuro-symbolic approach 로 해결한 방법론에 대해 설명해보겠다.
< Learning Compositional Rules via Neural Program Synthesis >
인간은 적은 예로부터 체계적인 규칙을 배우고, 이 규칙들을 결합하여 compositional rule-based systems (구성적인 규칙 기반 시스템)을 형성한다.
반면, 현재의 neural architecture 은 training 과 체계적으로 다른 방식으로 평가될 때, 구성적인 방식으로 일반화하지 못하는 경우가 많다. (SCAN 문제처럼) 또한 현대의 neural architectures 가 입력 시퀀스와 출력 시퀀스 사이의 rule-like mapping 을 직접 학습할 때 여전히 체계적인 방식으로 일반화하기 어려웠다. 따라서 진정한 compositional, human-like generalization 을 위해서는 hybrid neural-symbolic architectures 가 필요하다. 본 연구에서는 작은 예제 집합에서 전체 규칙 시스템을 학습하는 “neuro-symbolic model” 을 제시한다.
- 입력으로부터 출력을 바로 예측하는 대신, neural program synthesis 기술들을 바탕으로 이전에 본 예시들을 지배하는 규칙의 명시적 시스템을 유도할 수 있도록 모델을 훈련시킨다.
- specific 한 것들에서 abstract 을 통해 general 한 것을 잘 찾아내는 program synthesis 방법을 통해 모델 훈련.
* 핵심 idea
- program synthesis community 의 기술을 활용하고 빠른 neural proposals 과 엄청난 symbolic checking 을 통해 문제를 명시적인 rule-learning 으로 프레임화 하는 것.
A 처럼, 새로운 입력에 대해 output 을 예측하려고 모델을 훈련시키는 것이 아니라, B처럼 support examples 로부터 이 예들의 동작을 제어하는 명확한 규칙 시스템을 유도할 수 있도록 모델을 훈련시킨다. B 의 과정으로 규칙 시스템을 유도하면, 이 시스템을 사용해 input 에 대한 output 을 예측할 수 있는 것이다. 우리는 support examples 에 대해 확인할 수 있는 명시적 프로그램을 “search” 한다. 이를 통해 후보 프로그램들을 제안하고 확인할 수 있으며, neural model 에서 프로그램들을 샘플링하고, 제안된 솔루션이 이전 데이터와 일치하는 경우에만 검색을 종료할 수 있다.
A) 이전의 연구에서는, support examples 들을 external neural memory 로 인코딩하고, 쿼리 출력은 쿼리 입력 시퀀스를 조절하고 attention 을 통해 외부 메모리와 상호작용하여 예측된다.
B) 이 논문의 모델에서는 support examples 로부터 candidate grammars 에 대한 분포를 생성하고, 이 분포에서 표본을 추출하고, 이 support examples 를 만족하는 문법이 발견될 때까지 각 샘플링된 grammars 의 일관성을 ‘상징적으로 점검’ 한다.
- 중간의 빠른 neural proposal + 이후 쿼리셋에 대한 symbolic checking = rule-learning
- 검색 프로세스 : support examples 들을 가지고 neural model 에서 샘플링하여 후보 프로그램을 제안
--> 후보 프로그램이 support inputs 에서 이를 실행함으로써 support examples 를 잘 충족하는지, 즉 G(xi) = yi 의 여부를 상징적으로 점검한다. 각 트레이닝 에피소드마다 support set X 가 주어지고, 기본 프로그램 G 를 추론하도록 훈련된다.
- 우리의 신경 합성 접근 방식은 많은 수의 support examples 에 대해 동시에 유연하게 접근하여 다양한 support examples 로부터 다양한 종류의 정보를 통합할 수 있는 능력이 있다.
- 우리의 training 계획은 meta-learning 에서 영감을 받았고, 메타그래머의 분포를 가정하여 문법 학습 문제를 sampling 하고, 이 샘플링된 문제에 대한 훈련을 통해 모델을 훈련시킨다. 여기서 핵심은 데이터를 설명하는 잠재 프로그램의 가능성을 최대화하는 것이다.
* 우리의 rule-synthesis approach 가 다른 neural meta-learning 기술보다 더 낫다.
- 우리 모델은 빠르고 유연한 추론을 위해 compositional generalization 및 neural program synthesis 를 위한 “symbolic program representation” 을 사용한다. 이를 통해 프로그램 공간에서 검색을 활용하여 추측하고 확인할 수 있다.
우리의 synthesis-based rule learner 의 문법 적용 사례를 보면,
Support examples 는 BiLSTMs 을 통해 인코딩되고, 디코더 LSTM 은 결과 벡터 위에 방문하고 문법을 디코딩하며, 이는 보류된 쿼리 인풋에 상징적으로 적용될 수 있다.
- 참가자들은 색칠된 원의 순서를 만들어냄으로써 임시 단어들의 새로운 언어로 명령을 실행하는 법을 배웠다. Support set 에서 conditioned 되면, 우리 모델은
이 방법으로 문법을 합성하여 보류된 쿼리 명령에서 올바른 출력 시퀀스를 예측할 수 있다.
** 우리의 접근법
- 주어진 support examples 로부터 symbolic program (symbolic grammar) G 를 합성하는 모델 pθ(·|X ) 을 구축하는데, 이 프로그램 G 는 쿼리 입력에서 실행하여 원하는 쿼리 출력 ri = G(qi) 을 예측할 수 있다.
- 우리의 symbolic program G 는 ‘해석 문법’ 으로 구성되는데, 이것은 각각 토큰 순서의 변환을 나타내는 ‘다시쓰기 규칙’ 이다.
** 우리의 모델
우리의 신경 모델 [ pθ(G|X) ] 는 support set X 를 고려할 때 symbolic 프로그램 G 에 대한 분포이다. 모델은 두가지 구성요소로 구성되어있다.
1) 각 support example (xi, yi) 를 벡터 hi 로 인코딩하는 인코더 Enc
2) support examples 에 방문하는 동안 프로그램을 디코딩하는 디코더 Dec
pθ(·|X ) = Dec({hi}), , {hi} = Enc(X)
= 각 예시들을 인코더에 넣어 벡터 hi 로 인코딩한 결과를 다시 디코더에 넣으면 뉴럴 프로그램 합성 모델에 각 예시를 넣은 결과와 같다.
인코더
: 각 support 예제 (xi, yi) 에 대해 입력 시퀀스 xi 와 출력 시퀀스 yi 는 각각 입력 BiLSTM 인코더 fI(xi) 와 출력 BiLSTM 인코더 fO(yi) 의 최종 숨겨진 상태를 가져옴으로써 각각 벡터(hi)로 인코딩된다 (그림 2의 왼쪽). 그런 다음 이러한 숨겨진 상태는 가중치 W 와 단일 feed forward layer 를 통해 결합되어 support example 당 하나의 벡터 hi 를 생성한다.
hi = ReLU(W[fI (xi); fO(yi)])
( 벡터 hi 는 (xi, yi) 를 각각 입력 인코더, 출력인코더에 통과시킨 후 가중치 W 와 단일 feed forward layer = ReLU 를 통해 결합되어 나온 벡터이다. Support example 에 여러 개의 인풋들이 있겠지만 이 것들이 다 이 ReLU 를 거쳐서 하나의 벡터 hi 를 생성한다. )
디코더
: 우리는 디코더로 LSTM 을 사용한다. 디코더는 attention 을 통해 support vectors hi 에 방문하는 동안 토큰별 프로그램을 생성한다. 디코더는 아웃풋으로 토큰화된 프로그램을 출력하고 이는 곧 해석 문법으로 분해된다.
해석문법
: 본 연구의 프로그램들은 용어 재작성 시스템의 한 형태인 ‘해석 문법’ 의 예이다. 이 작품에 사용된 해석문법은 순서화된 규칙 리스트로 구성되어있다. 각 규칙은 left hand side (좌측) (LHS) 과 right hand side (우측) (RHS) 로 구성된다. LHS 는 입력 단어, 문자열 변수 x, 원시 변수 u 로 구성된다.
입력 시퀀스 zup blicket wif kiki dax fep 에 대해 첫번째 kiki 규칙에서 해당 RHS 가 적용되어 [dax fep] [zup blicket wif] 가 생성되고, 그 이후 각각 fep 및 blicket 규칙을 사용하여 재귀적으료 평가된다.
검색
: test 할 때, 우리는 뉴럴 프로그램 합성 모델에서 후보 프로그램들을 샘플링한다. 새 후보 프로그램 G 가 support set 를 만족하면 (if G(xi) = yi ) 검색이 종료되고 후보 프로그램 G 가 솔루션으로 반환된다. 그런 다음 프로그램 G 가 보류된 쿼리 세트에 적용되어 최종 쿼리 예측 ri = G(qi) 를 생성한다. 검색 중에, 우리는 가장 많은 support 예시들을 만족시키는 프로그램으로 정의된 지금까지 최고의 프로그램을 유지한다. 검색 시간이 초과되고 모든 support 예제를 해결하는 프로그램이 발견되지 않은 경우 지금까지 중에서의 최상의 프로그램이 솔루션으로 반환된다.
순수 뉴럴 유도 모델의 경우에는, 쿼리 입력 및 해당 output 예측이 주어지면 support set 와의 일관성을 확인할 방법이 없다. 하지만 우리는 ‘검색’을 통해 이를 확인할 수 있다. 우리 모델은 각 후보 프로그램들이 올바르게 인풋 아웃풋 매핑하는지 확인하기 위해 각 후보 프로그램들을 support set 에 대해 명시적으로 검색한다. 모든 예시를 충족하는 프로그램이 발견될 때까지 검색하고, 검색 예산을 늘리면서 SCAN 에 대한 완벽한 정확도를 달성할 수 있다.
- 또 RobustFill 과 우리 모델의 차이는 ‘시스템에 제공되는 입출력 예제의 수와 다양성’ 이다. RobustFill 과 같은 이전 neural program synthesis 방법은 많은 다양한 예시들 처리할 수 없다. 예시들을 선택하기 위한 기법은 있지만 비용이 많이 들어서 추가 외부 루프가 필요하거나 새로운 반례가 발견될 때마다 검색을 다시 해야 했다. 하지만 우리 모델은 검색 예산을 늘리면서 모든 예시에 다 방문하기 때문에 다양하고 많은 예제들을 다 확인할 수 있다.
트레이닝
: 우리는 Compositional generalization through meta sequence-to-sequence learning 와 유사한 방식으로 모델을 훈련시킨다. 각 훈련 에피소드 동안, 메타그래머에 대한 분포에서 무작위로 해석 문법 G를 샘플링하고, 샘플링된 해석 문법과 일치하는 입력 시퀀스를 샘플링한 후 각 입력 시퀀스에 해석 문법을 적용하여 출력 시퀀스를 생성한다. 이렇게 해서 입력-출력 예제 를 만들고, 입출력 예제의 support set 에서 조건화되었을 때 문법 G 를 출력하기 위해 ‘지도학습’ 을 통해 네트워크 모델 네트워크 pθ 의 매개변수 θ 를 훈련하여 gradient descent 로
를 최대화한다.
SCAN Challenge 에서의 neuro-symbolic approach
SCAN 의 목표는 테스트 데이터가 훈련 데이터와 체계적으로 다를 때 신경망의 구성 능력을 테스트하는 것이다. 우리는 rule-learning approach (규칙 학습 접근 방식) 이 이러한 compositional challenges (구성 문제) 를 해결할 수 있는지 여부를 결정하기 위해 SCAN 데이터 셋에서 모델을 테스트한다.
Training Setup
: 이전의 테크닉에서는 메타러닝을 통해서 모델을 트레이닝시켰고, 메타트레이닝 분포가 메타트레인과 메타테스트 간에 동일한 SCAN 작업 구조를 유지하면서 명령에 동작을 할당하는 순열로 구성되었다. 반면에 우리는 일반적이고 광범위한 SCAN 유사 규칙 시스템에 대한 meta-training 을 통해 소수의 예에서 전체 SCAN 문법을 학습하는데 접근했다.
- SCAN 을 해결하는 grammar 을 만들게 해주는 두가지
1) 원어들은 빈 토큰에 다시 쓸수 있다. Ex. turn à EMPTY_STRING
2) 각 문법의 마지막 규칙은 MiniSCAN 에서 ‘연속규칙’ 이라고 했는데, SCAN 에서는.
아까 MiniSCAN 처럼 standard concatenation rule (u1 x1 -> [u1] [x1] ) 을 따르던가 아니면 50%의 확률로 다른 concatenation(연속) rule 인 ( u1 u2 -> [u2] [u1] ) 를 따른다. 이건 두개의 인접한 single 원어들에서만 작동한다. à 일반 문자열에서는 작동하지 않은 이것을 굳이 사용하는 이유는, MiniSCAN 문법과 호환성을 유지하면서 SCAN 문법이 트레이닝되고있는 메타그래머의 support examples 내에 있는지 확인하는 것이다.
Testing Setup
- SCAN training sets 는 수천 개의 예시들을 가지고 있기 때문에 테스트할 때 전체 트레이닝셋을 참석하는 것은 불가능하다. 따라서 우리는 테스트할 때 우리 네트워크의 support set 으로 사용하기 위해 SCAN 트레이닝 셋에서 100개의 예시들을 랜덤하게 샘플링했다. 그리고 우리는 이 SCAN 트레이닝 셋으로부터 뽑은 100개의 예시들을 가지고 조건화된 프로그램 추론을 돌렸다. SCAN 데이터셋은 SCAN 문법에서 가능한 모든 예제를 고정된 깊이까지 열거함으로써 형성된다. : 우리의 모델은 target 문법에서 예제들을 샘플링해서 훈련되었다.
(기존 SCAN 은 SCAN 문법에서 모든 예제들을 다 열거해 데이터를 만든다면, 우리는 딱 필요한 target 문법에서 예제들을 샘플링.) 이로 인해 분포 불일치가 발생하여, 모든 규칙이 입증되도록 하면서도, 테스트 할 때 더 짧은 예제를 업샘플링(샘플링 비율 높이는것)하기 위해 휴리스틱을 사용하여 수정한다.
+ 각 SCAN 트레이닝 셋에서 support examples 을 잘 뽑을 수 있는 2가지 방법이 있다.
1) 테스트할 때의 support sets 와 트레이닝할 때의 support sets 분포가 매치하는걸 확신하기 위해, 우리는 training 시간에 나타나는 입력 시퀀스 길이의 경험적 분포와 일치하도록 test-time support examples 을 선택했다. 우리는 일관된 시퀀스 길이를 보장하기 위해 트레이닝과 테스트 할 때 rejection sampling 을 사용했다.
2) test-time support set 에서 조금 더 긴 시퀀스들과 연관된 단어들이 예시에서 많이 보이면 결과가 좋은 것을 발견했다. 따라서 support set 에서 ‘opposite’ 과 ‘around’ 단어가 표시될 확률을 가중시켰다. (opposite, around 가 나오면 left turn, right turn 등 많이 하게 되니 문장 길어짐)
- 트레이닝 예시들의 수가 많기 때문에 우리는 또한 성능을 높이기 위해 우리의 test-time 검색 알고리즘을 살짝 수정할 수 있었다. 우리는 우리의 네트워크를 위한 초기 support set 으로서 100개의 예시들을 선택하고, 이 예시들을 완벽하게 충족하는 문법을 찾는다. 만약 20초안에 그 세트안에 만족하는 문법이 없으면, 다른 100개의 예시들을 다시 뽑고 다시 문법을 찾는다. 만족스러운 문법을 찾을 때까지 이 과정을 반복한다. 이는 한번에 수천개의 예시들을 방문하지 않고도 많은 예시들을 활용할 수 있게 해주었다.
- Eunumeration, DeepCoder 프로그램 합성 기준선의 실패는, 정확한 인지모델들은 이런 넓은 공간 안에서 효율적으로 검색해야한다는 것을 제안한다. (우리의 모델의 경우는 with search 를 통해)
결과
검색을 사용해서 우리의 합성 모델은 각각의 SCAN 분할에 대해 완벽한 성능을 보일 수 있었다. 검색이 없었더라면, 합성 접근법은 SCAN 문제를 풀지 못했을 것이다. 비슷하게, program representation 이나 search 를 모두 사용하지 않은 meta seq2seq는 매우 일반적인 meta-grammar 안에서 트레이닝 했을 때, 테스트 셋의 1%도 해결하지 못하면서 SCAN 문제를 풀지 못했다.
우리 접근법의 이점은 각각 분할에 대해 모델을 재훈련하지 않아도 된다는 점이다.
Meta-training 이 일어나면 우리 모델은 각각 분할에 대해 test 될 수 있고, 모든 4개의 분할에 대해 만족스러운 문법을 유도할 수 있다. 이전의 연구에서는, separate meta-training 셋이 각각의 SCAN 분할에 사용되었었다. (99.95% ‘jump’, 98.71% ‘right’) 반대로 우리는 meta-train 을 한번만 하고, 4개의 분할 전부에 테스트했다. 이전의 meta-learning 은 이 세팅에서 실패(0.51%, 0.03%) 했었다. 이전 접근법들은 전체 SCAN 트레이닝 셋을 사용했고, 우리 모델은 SCAN 을 해결하기 위해 트레이닝 데이터의 2퍼센트 보다 적은 양을 요구한다.
Conclusion
우리는 다양한 예시들의 작은 세트로부터도 rule-based (규칙기반) 시스템을 학습할 수 있는 “뉴로심볼릭 프로그램 합성” 모델을 제시한다. 우리의 접근법은 neural attention 을 이용하여 많은 예시들을 유동적으로 한번에 condition 하고, 다양한 support examples 로부터 정보를 통합한다. program representation 과 explicit search 의 사용은 강력한 out-of-sample 일반화를 제공해주었다.
(출처 : 해당 글의 몇 몇 이미지들은 논문 안의 표, 그림에서 가져왔다. arxiv.org/abs/2003.05562 )
댓글