원 논문은 여기서 확인하실 수 있습니다.
https://arxiv.org/abs/1805.04276
Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis
Program synthesis is the task of automatically generating a program consistent with a specification. Recent years have seen proposal of a number of neural approaches for program synthesis, many of which adopt a sequence generation paradigm similar to neura
arxiv.org
Abstract
Program Synthesis는 specification에 맞는 프로그램을 자동적으로 생성하는 작업입니다.
보통 이를 위해 LSTM을 이용하여 프로그램 토큰들을 순차적으로 출력하게끔 학습시키는 Seq2Seq 모델을 많이 사용하며, 학습을 위해서는 Maximum Likelihood Estimation(MLE)을 사용합니다.
하지만 이런 방법에는 두 가지 한계점이 있습니다.
1) Program Aliasing - 이루어진 토큰은 다르지만, 같은 내용을 의미하는 프로그램이 큰 로스로 다가올 수 있습니다.
MLE를 사용한 supervised 학습은 이런 의미적인 부분을 무시하게 됩니다.
2) Strict Program Syntax - 프로그램 토큰을 차례로 나열하는 Seq2Seq 모델은 프로그램의 문법적인 부분에 대해 캐치하지 못한 채로 잘못된 문법의 프로그램을 만들어낼 수 있습니다.
문법이 맞지 않는 프로그램은 실행시킬 수도 없고, 의미가 없기 때문에 이 점을 모델에게 어떤 식으로라도 도와줄 수 있다면 좋을 것입니다.
이 논문에서는 이 문제들에 대한 해결을 위해
1) 순수한 Supervised Learning이 아닌 강화 학습을 추가로 적용하여 학습시킵니다.
강화 학습의 리워드는 의미적으로 맞는 프로그램을 생성하였는가가 됩니다.
2) 모델에 Syntax Check를 도와주는 추가적인 작업을 적용시킵니다.
LSTM의 Output으로 나오는 다음으로 나올 토큰들의 확률들에 대하여 Syntax가 맞지 않는 토큰의 확률은 없애서 올바른 문법의 프로그램을 출력할 수 있게 도와줍니다.
Introduction
Program Synthesis는 Input-Output 예시라던지 하는 어떠한 specification에 대하여 그에 맞는 프로그램을 자동적으로 생성해내는 작업입니다.
이와 비슷한 작업인 Neural Program Induction 분야는 최근 굉장한 발전이 있었지만, 이는 명시적으로 해석이 가능한 프로그램을 생성하지 않습니다. (프로그램의 형식으로 작업을 하긴 하는데, 프로그램을 처음부터 끝까지 쫙 만드는 게 아니라 그때그때 환경에 필요한 프로그램을 호출하는 형식입니다. NPI가 이 분야에 속합니다.)
그 외에도 각각의 프로그램을 배우기 위해 많은 예시가 필요한다던지 하는 문제들이 있습니다.
이런 문제들에 대해 해결하기 위해 나온 방식이 Neural Program Synthesis입니다.
이는 5개 정도 되는 몇 개 안되는 예시(few examples)에 대해서도 Domain-Specific Language(DSL)를 통해 프로그램으로 표현을 해내는 것이 가능합니다.
하지만 이 모델도 두 가지의 한계점들이 있었습니다.
1) Program Aliasing
몇 개 안되는 예시로부터 프로그램을 만들기에 만들 수 있는 프로그램의 수는 굉장히 많습니다. 하지만 supervised 학습은 ground-truth 프로그램을 출력하게끔 하기 때문에 다른 가능한 프로그램들에 대해서는 높은 loss를 내게 됩니다.
가능한 어떤 프로그램이라도 만들 수 있게끔 하는 본래의 Program Synthesis 목적에 맞게끔 이 문제를 해결하기 위해 MLE를 대신하여 강화 학습을 접목할 것입니다.
2) Strict Program Syntax
프로그램은 엄격한 문법 구조를 지켜야 합니다. 하지만 단순한 seq2seq 모델로는 이 문법 구조를 알게 하기가 쉽지 않습니다.
이를 위해 본 모델을 도와줄 syntax checker를 추가적으로 사용하고, 이를 통해 pruning이 가능하게 합니다.
위 방법들에 대한 효과를 검증하기 위해 Karel 환경에서 실험을 진행합니다.
Karel은 교육용 프로그래밍 언어로써 if 구절 같은 control flow를 포함하고 있고, 이는 program synthesis 작업을 좀 더 어렵게 합니다.
이 논문이 기여하는 바를 다시 한번 정리하면,
1) 순수한 supervised 학습에 비해 일반화된 프로그램 생성에서 좋은 성능을 보이는 강화 학습 방법을 제시합니다.
2) syntax checker를 통한 탐색 공간의 축소화 방법을 제시합니다.
3) syntax checker가 없을 수 있기 때문에, 이를 위해 프로그램 생성과 더불어 자체적으로 syntax를 학습하는 모델 또한 소개합니다.
Problem Overview
<Program Synthesis Formulation>
데이터셋은 위 수식으로 표현이 가능합니다. IO는 input/output 쌍을 나타냅니다. input과 output은 상태로 표현할 수 있습니다.
예를 들어 Karel에서는 각각의 격자 칸의 상태를 상태로 표현이 가능합니다.
람다는 프로그램을 나타냅니다.
즉, 프로그램 i에 대해서 k개의 Input/output 쌍이 존재한다고 설명이 가능합니다.
위 논문에서 Program Synthesis 모델이 세타입니다.
k개의 IO가 주어질 때 그에 맞는 프로그램을 생성해내는 일을 하게 됩니다.
테스트 셋은 spec과 test로 나누어지는데, spec은 모델의 입력으로 주어지는 IO이며, test는 모델이 출력한 프로그램을 실행하여 맞게 만들어졌는지 테스트하기 위한 IO입니다.
즉 이 모델의 목표는 위 식으로 표현이 가능합니다.
테스트 데이터셋에 대하여 모델이 만들어낸 프로그램에게 input 상태에서 시작할 때 최종적으로 정답 output 상태가 나오게끔 만들면 됩니다.
<Neural Program Synthesis Architecture>
가장 기본적인 LSTM 기반의 seq2seq 모델로,
Input : Embedding(IO) + Embedding(이전의 토큰)
Output : 다음으로 나오게 될 토큰들의 확률 (출력값이 추가적으로 softmax layer를 거칩니다)
표현이 가능합니다. Karel의 상태에 대한 임베딩은 CNN을 활용하였습니다.
모델을 식으로 표현하면 아래와 같습니다.
s는 토큰을 의미하고 L은 토큰의 길이를 의미합니다.
K개의 IO가 주어질 때 올바른 프로그램 세타를 예측하게 될 확률을 높이는 과정은 위 수식의 오른쪽으로 표현이 가능합니다.
테스트시에는 Beam Search를 활용하여 프로그램을 얻습니다.
program synthesis의 장점으로는 실행할 수 있는 프로그램을 만들어낸다는 점입니다.
실행을 통해 문법적으로 오류가 있거나 예시와 일치하지 않는 프로그램을 제거하며, 남아있는 프로그램들 중 가장 높은 확률의 프로그램을 모델에게 전달합니다.
Syntax checker까지 존재하는 모델의 전체적인 구조와 흐름을 설명드리겠습니다.
Input>
IO는 concat, CNN과 FC 레이어를 통해 임베딩 됩니다.
위 임베딩 벡터에 이전에 나온 토큰의 임베딩 값이 concat 되어 LSTM의 입력값으로 들어가게 됩니다.
IO는 변함이 없지만, 토큰 임베딩 값은 상황마다 변하게 됩니다.
각 프로그램마다 K개의 IO쌍이 있습니다.
각각의 IO쌍에 대해 각각의 LSTM을 입력으로 주게 됩니다.
Output>
K개의 LSTM으로부터 나온 값에 MaxPooling을 적용합니다.
이와 별개로 이전의 토큰을 Syntax checker에게 넣어 mask 벡터를 구합니다.
위 두 개의 벡터를 곱하고, 이에 softmax를 적용하여 최종적으로 다음에 나오게 될 토큰을 구하게 됩니다.
Objective Function
<Maximum Likelihood Optimization>
모델의 가중치(파라미터) 세타에 대해 supervised 학습을 적용한 기본적인 방법은 MLE입니다.
MLE를 적용한 목적함수가 위 식이라고 할 수 있습니다.
하지만 위에서도 말했듯이, 위 식만을 이용하면 여러 문제가 생깁니다.
학습 과정에서 모델은 오로지 훈련 데이터에 대해서만 노출되지만, 테스트 과정에서는 자신이 출력한 토큰이 입력으로 들어오게 됩니다.
Natural Language Processing에서 이런 문제는 Exposure Bias라고 합니다.
게다가 이 loss는 program synthesis의 진정한 목적이라고 할 수 없습니다.
MLE 학습 과정에서는 Program Aliasing 문제가 발생할 수 있기 때문입니다.
이 문제를 해결하기 위해 ground-truth 프로그램과 일치하지는 않더라도 맞는 프로그램에 대해서 loss 함수가 페널티를 주는 것을 막을 것입니다.
<Optimizing Expected Correctness>
Program Synthesis의 진정한 목적에 맞게 하기 위한 목적 함수의 첫 번째 수정은 아래와 같습니다.
R은 리워드 함수를 의미합니다.
리워드 함수는 여러 가지로 설정할 수 있습니다.
감마가 시그마 아래에 있는 건 만들어질 수 있는 프로그램이 강화 학습에서는 정말 다양하게 나올 수 있기 때문에 저렇게 표현한 것으로 보입니다.
하지만 위 식의 문제점은 너무 다양한 프로그램이 나올 수 있기 때문에 어떻게 기준을 잡아 계산하기 어렵다는 점입니다.
이 점을 해결하기 위해 몬테 카를로 방식을 사용하여 몇 개에 샘플에 대한 식으로 바꿀 수 있습니다.
여기서 S는 샘플의 개수입니다.
하지만 위 방식 또한 문제점을 찾을 수 있는데, 기울기를 추정하며 샘플을 뽑아낼 때 반복적으로 같은 프로그램을 만들어낼 확률이 높다는 점입니다.
이는 특히나 supervised 학습을 통해 pre-train 된 경우 도드라집니다.
이를 위해 살짝 다른 변경을 통해 학습을 도와줄 수 있습니다.
이 변화는 S 개의 샘플을 만들어낼 때 Beam Search에서 S개의 가장 높은 확률의 샘플을 뽑아내는 것입니다.
위 그림에서 S는 3이며, 각각의 타임 스텝마다 3개의 후보에 대해 Beam Search를 진행합니다.
BS(p세타, S)는 파라미터가 세타일 때 Beam Search를 통해 S개의 샘플을 뽑아낸 최종적인 결과를 의미하며, 초록색은 End Token을 의미합니다.
이렇게 나오게 된 S개의 프로그램은 확률 p를 가지고 있는데, 이 p를 softmax 비슷하게 적용하여 확률 q로 리스케일링 해줍니다.
이를 통해 중복적인 프로그램이 나오는 경우를 방지할 수 있습니다.
위 과정을 Exp.7과 비슷하게 표현이 가능합니다.
전체 수식은 p가 q로 변경된 점뿐입니다.
하지만 Beam Search를 이용한 샘플링을 한다는 점이 추가되었습니다.
참고로 주의할 점은 S가 과도하게 커지게 되어 모든 생성될 만한 프로그램을 커버할 수 있게 되면 7번 수식과 다를 게 없다는 점입니다.
여기서 조금 더 다루기 쉽게 하기 위해 더 복잡한 목적 함수를 정의할 수 있습니다.
Program Synthesis에서 입력으로 들어온 Specification을 통해 몇몇 예측값들을 pruning 할 수 있습니다.
그러므로, 하나의 프로그램을 샘플링할 때 기대되는 reward 값을 최적화하는 것 이상으로 프로그램들의 묶음 C를 샘플링하고 최상의 프로그램을 유지할 때 기대되는 reward 값을 최적화하는 것을 선택할 수 있습니다.
Reward 함수는 프로그램이 올바르냐에 따라 0, 1의 값을 줄 수 있고, 이를 이용해 식을 좀 더 쉽게 표현하면 아래와 같습니다.
* 10번과 11번 수식은 자세히 이해되진 않습니다. 설명해주신다면 감사하겠습니다..
Model
<Conditioning On the Syntax>
Program Synthesis 작업은 문법적으로 맞지 않는 프로그램을 만들어낼 수 있다는 측면이 있는데, 예측하기 전에 선별해 줄 수 있습니다.
stx는 문법적으로 맞는 프로그램이라는 걸 의미합니다.
이를 신경 써서 모델링한다는 점은 위 식처럼 표현할 수 있습니다.
이를 조금만 더 분해해서 생각하여, t번째 토큰을 예측하는 걸 식으로 표현하면 아래와 같습니다.
실제 모델 구현에서는 일종의 Mask를 모델이 softmax를 통해 최종 아웃풋을 출력하기 전에 더해주게끔 하였습니다.
각각의 타임 스텝마다 토큰 벡터에 대해 Mask M= {-INF, 0}으로 표현할 수 있습니다.
-INF는 현재 문맥에서 문법적으로 불가능한 토큰에 부여됩니다.
이를 통해 문법적으로 정확한 프로그램만을 찾게 되므로, Beam Search에서 탐색 범위를 줄여 효율적인 탐색이 가능합니다.
이는 문제를 좀 더 단순하게 만들고 학습을 쉽게 만듭니다.
<Jointly Learned Syntax>
하지만 항상 Syntax Checker가 존재한다고 가정할 수는 없습니다.
또한 모델이 그저 학습만으로도 Syntax를 파악하게 된다면 일반적으로 쓰기 더 좋을 것입니다.
이를 위해 이 논문에서는 Syntax Checker를 뉴럴 네트워크 모듈(syntaxLSTM)로 만들고, 함께 학습을 시킵니다.
몇 가지 특징은 아래와 같습니다.
1) syntaxLSTM은 IO 쌍과 상관없이 오로지 프로그램 토큰들이 중요하기 때문에 IO는 입력으로 받지 않습니다.
이를 통해 문법의 학습에 집중할 수 있게 합니다.
2) syntaxLSTM으로부터 나오게 된 출력 값은 x -> -exp(x) 활성화 함수를 통과하여 decoder LSTM의 출력 값에 더해지게 됩니다.
위에서 설명한 Mask처럼 -exp 함수 또한 문법적으로 맞지 않는 토큰에 대해 페널티를 부과합니다.
syntaxLSTM의 추가는 모델 구조의 간단한 변경이기 때문에 학습의 절차를 바꿀 필요는 없습니다.
하지만, supervised 학습에서는 문법적으로 맞는 프로그램에게 갈 수 있게 해줘야 하기 때문에 MLE에 더해 추가적인 loss를 사용합니다.
이 loss는 문법적으로 유효한 프로그램들을 통해 syntaxLSTM에게 올바른 문법을 학습시킬 수 있게 도와줍니다.
Experiments
<The Domain : KAREL>
KAREL은 그리드 월드에서 에이전트가 움직이거나(move, turn{Left, Right}), 환경을 바꾸면서({pick, put}Marker), 또한 환경으로부터 정보를 얻으며(markerPresent, noMarkerPresent, frontIsClear, leftIsClear, rightIsClear) 진행해나갈 수 있는 실험 환경입니다.
위 토큰들 말고도 control flow로 for, while, if를 지원합니다. 실험을 위해 서브루틴을 정의할 수 있는 기능은 사용하지 않았습니다.
DataSet>
실험을 위해 랜덤 DSL 프로그램 생성을 하였으며, 간단한 몇 가지 휴리스틱 체크를 통해 환경에 변화를 주지 않는 프로그램이나, 의미 없는 행동(turnLeft, turnRight를 이어서 하는 경우처럼)을 하는 프로그램은 사용하지 않았습니다.
각각의 프로그램에 대해 많은 IO쌍을 만들고, 적어도 프로그램에 존재하는 모든 IF를 한 번은 지나가도록 선별하여 6개의 IO 쌍을 가지게끔 하였습니다.
첫 5개의 샘플은 입력으로 주어지며, 6번째 샘플은 테스트를 위해 사용됩니다. 5000개의 프로그램을 나누어 validation set과 test set으로 사용되었습니다.
모델의 입출력>
KAREL의 상태는 각각의 그리드마다 16개로 나타내어질 수 있었습니다.
실험에서 그리드는 18 * 18 크기를 사용했고, 따라서 IO는 16 * 18 * 18의 형태를 띄었습니다.
IO는 각각 CNN에 들어가 feature를 추출한 후 Concatenation 한 뒤, 다시금 두 개의 CNN과 하나의 FC를 거쳐 512 크기의 벡터를 최종적으로 출력하게끔 하였습니다.
모델의 출력 값은 step마다 K개의 Decoder의 출력 값을 Maxpooling을 한 값을 이용하여 최종 출력에 사용하였습니다.
<Results>
Full Dataset : 100만 개의 프로그램 데이터셋입니다.
Small Dataset : 1만 개의 프로그램 데이터셋입니다.
데이터셋을 나눠서 실험하는 이유는 실 세계의 program synthesis domain에서는 수많은 데이터를 모으기 어렵기 때문입니다.
첫 번째 실험은 학습 방법을 통한 결과 비교 실험입니다.
모델>
MLE : 수식 6을 이용하는 방법이며, 평범한 supervised 학습 방식 모델입니다.
아래의 RL은 모두 reward로 프로그램이 모든 샘플과 일치하면 1, 아니면 0을 사용합니다.
RL : 수식 7과 8을 loss로 이용하는 방법입니다. (샘플링 적용한 강화 학습)
RL_beam : 수식 9를 loss로 이용하는 방법입니다. (샘플링에서 같은 샘플 뽑히는 문제 해결한 방법)
RL_beam_div : 수식 10을 loss로 이용합니다. (output이 좀 더 다양하게 나올 수 있도록 개량한 방법)
RL_beam_div_opt : 수식 10을 loss로 이용하지만, time step에 따라 추가적으로 reward에 페널티를 주는 방법을 사용하였습니다.
RL 관련 모델은 supervised 학습을 통해 먼저 pretrain 되었습니다.
보통의 Neural Machine Traslation 방법에서 보편적으로 사용되는 방식이기도 하고, 아무래도 순수 RL만으로 하기에는 성능이 좋지 못했다고 합니다.
이는 DSL을 통한 탐색 공간이 너무 넓어서 그런 것으로 생각됩니다.
평가지표>
Generalization : 만들어진 프로그램이 모든 IO에 대하여 정확하게 매치되는지 확인합니다.
Exact Match : 만들어진 프로그램이 ground-truth 프로그램과 정확하게 매치되는지 확인합니다.
분석>
Full dataset : RL을 이용하였을 때, Exact Match는 줄어들지만, Generalization은 좋아지고 있습니다.
이를 통해 RL을 이용하면 supervised의 한계였던 기존의 ground-truth 프로그램과 정확하게 일치하는 프로그램을 생성하던 비율이 줄어든다는 의미로 볼 수 있습니다.
즉, Program Aliasing 문제를 해결한다고 볼 수 있습니다. 이는 특히 RL_beam에서 두드러집니다.
Small dataset : MLE로만 학습을 진행시켰을 때보다 강화 학습을 추후에 추가로 진행하였을 때 성능이 두 가지 지표에서 모두 올라가는 것을 확인할 수 있습니다.
이를 통해 데이터가 적을 때 강화학습을 이용하여 데이터의 효율성을 높일 수 있다는 점을 확인할 수 있습니다.
두 번째 실험은 Full dataset에서 각각의 모델로부터 생성된 Top-k개의 프로그램에 대한 Generalization 비교 실험입니다.
분석 >
위 실험을 통해 알아낼 수 있는 점은 같은 일을 하더라도 다른 코드로 표현할 수 있는 능력을 본다고 생각합니다.
특히 이런 능력은 Program Synthesis에서 중요한 부분이라고 생각합니다.
Top-1과 Top-5에서 RL_beam_div_opt 모델의 성능이 가장 좋은 점을 확인할 수 있는데, 이는 Beam Search의 다양성을 높이면서, time step에 따른 reward의 조정으로 의미 없는 액션의 반복을 피했기 때문이라고 생각합니다.
개인적으로 의미 없는 액션의 반복을 계속하다, 이상한 길로 빠질 수도 있다고 생각합니다.
Top-50에 대해서는 MLE가 성능이 가장 좋은 점을 확인할 수 있는데, 이 부분에 대해서는 강화 학습은 MLE에 비해 넓은 범위를 탐색하기 때문에 최적의 프로그램은 더 잘 만들 수 있지만, 그런 만큼 넓은 범위에 대해 탐색하기 때문에 50개를 뽑을 때는 전체 성능은 낮을 수밖에 없다고 생각합니다.
세 번째 실험은 Syntax Checker 방식에 따른 성능의 차이 유무입니다.
모델>
MLE_learned : syntaxLSTM을 학습시키는 모델입니다.
MLE_handwritten : syntax 규칙을 알고 있는 syntax checker를 사용하는 모델입니다.
MLE_large : 추가적인 syntaxLSTM을 사용하지는 않지만 그만큼 파라미터 수를 추가해서 학습하는 모델입니다.
분석>
Full dataset : MLE가 MLE-learned보다 성능이 높은 점을 알 수 있습니다.
이는 충분한 데이터가 주어지면 모델이 따로 명시되어 있지 않아도 syntax에 대해 학습을 한다는 것으로 보입니다. 이에 대한 것은 MLE_large가 성능이 가장 좋은 점을 통해서도 알 수 있습니다.
Small dataset : 하지만 데이터셋이 충분하지 않을 때는 문법을 명시적으로 학습시키려 하는 MLE_learned 성능이 가장 좋았습니다.
특히 handwritten보다 성능이 좋은 점은 눈여겨볼 만 한데, 이 이유는 syntaxLSTM이 문법적으로 올바르지 못한 토큰을 거르는 것을 포함하여, 의미적으로 이상한 토큰마저도 거르는 걸 도와줄 수 있기 때문이라고 생각합니다.
다른 모델은 syntax를 자체적으로 학습하기에는 데이터가 충분하지 않은 점이 비교적 낮은 성능의 원인이라고 생각합니다.
네 번째 실험은 MLE_learned 모델이 full dataset에 대해 학습하였을 때 Top-k개에 대하여 문법적으로 맞는 프로그램을 만들어내는가를 확인하는 실험입니다.
모델>
Joint Model : syntaxLSTM을 사용하여 프로그램을 생성하는 모델입니다.
Without Learned Syntax : syntaxLSTM으로부터 나온 mask를 사용하지 않는 모델입니다.
분석>
syntaxLSTM을 사용하지 않은 모델의 정확도가 급격하게 떨어진 점은 학습을 함에 있어서 syntaxLSTM에 의존하게 되었기 때문이라고 보입니다.
Joint Model을 보면 문법적으로는 거의 완벽한 프로그램들만을 생성하는 점을 볼 수 있습니다.
위 그림은 Fig1.a에 대해 handwritten model(Manual)과 learned model의 syntax mask에 대한 비교입니다.
하얀색은 문법적으로 가능한 토큰을 의미합니다.
(c)는 두 mask의 차이를 나타낸 것이며, 하얀색은 같고, 파란색은 learn이 문법적으로 틀린 토큰에 대해 가능하다고 판단한 부분이며, 빨간색은 문법적으로 가능한 토큰에 대해 불가능하다고 판단한 부분입니다.
빨간색이 세 번째 실험과 어느 정도 연관성이 있는, 가능하지만 의미적으로 이상하다고 학습된 부분으로 보입니다.
즉 syntaxLSTM이 문법 자체만 학습하는 것이 아닌 전체적인 토큰의 분포 또한 학습을 하는 것으로 이해할 수 있습니다.
Conclusion
이 논문은 현재의 최신 neural program synthesis에 있어 성능을 향상시킬 수 있는 두 가지의 새로운 기여를 하였습니다.
1) 출력되는 프로그램의 일반화를 위해 강화 학습을 사용하였습니다.
2) 추가적인 메커니즘으로 syntax check를 통해 탐색 공간을 줄였습니다. 이는 부족한 데이터셋에 대해서 눈에 띄는 성능 향상을 가져올 것입니다. (실험 3)
'AI > 논문 리뷰' 카테고리의 다른 글
| [논문 리뷰] Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks (0) | 2019.11.12 |
|---|---|
| [논문 리뷰] One-Shot Visual Lmitation Learning via Meta-Learning (1) | 2019.10.28 |
| [논문 리뷰] Neural Architecture Search with Reinforcement Learning (0) | 2019.10.07 |
| [논문 리뷰] Neural Task Programming: Learning to Generalize Across Hierarchical Tasks (0) | 2019.10.04 |
| [논문 리뷰] Neural Programmer-Interpreter (0) | 2019.10.01 |