꾸준히 걷는중

 * 구글 딥마인드가 ICLR 2016에서 발표한 논문입니다. 

Abstract

 논문은 Neural Programmer-interpreter(NPI) 모델을 제안합니다. 이 모델은 프로그램을 표현하고 실행하는 법을 배우는 recurrent하고 compositional한 뉴럴 네트워크입니다.

 NPI는 세 가지 요소를 가지고 있습니다. 

 1) Task와 상관없는 코어 RNN

 2) key-value 프로그램 메모리 

 3) Task 도메인마다의 특정 인코더 - 이를 통해 다양하고 다른 여러가지 환경에서 NPI가 작동할 수 있게 해줍니다.

 하위 레벨의 프로그램들을 조합하여 상위 레벨의 프로그램을 표현하는 법을 배우기 위해, NPI는 기존 Seq2Seq LSTM 모델과 비교하였을 때 학습과정에서의 샘플 필요 수를 줄이고, 일반화 능력을 높였습니다.

 프로그램 메모리는 이미 존재하는 프로그램들과 함께 추가적인 task에 대한 효율적인 학습을 할 수 있게 합니다.

 NPI는 또한 RNN의 hidden state에 대한 장기적인 기억에 대한 부담을 감소시킬 수 있게끔 환경을 이용할 수 있습니다. 예를 들어 환경에 패드(메모장)가 존재한다면, 그 패드에 계산의 중간값을 저장할 수 있습니다.

 NPI는 완전지도학습으로 학습됩니다. 각각의 프로그램은 Input에 따라 중간중간 서브프로그램을 실행하는 예시 순서들을 가지고 있습니다. 많은 수의, 하지만 상대적으로 빈약한 training 데이터보다, 풍부하지만 적은 수의 training 데이터를 이용해 학습한다고 합니다.

 이 논문은 NPI가 여러 타입의 프로그램들(덧셈, 정렬, 3D 모델 회전시키기)을 학습할 수 있다는 것을 증명하려 합니다.

 더 나아가서, 단 하나의 NPI가 이 프로그램들과 21가지의 연관된 서브프로그램을 실행할 수 있게 학습시킬 수 있습니다.

Introduction & Model

 Recurrent와 Compositional, 이 두 말의 의미는 논문에서 대략 이렇게 사용됩니다. 

 1) Recurrent는 말 그대로 반복적인 모델이라는 뜻인데, 보통 RNN이라고 표현합니다.

 2) Compositional은 여러 개의 모델이 합쳐져 사용된다는 뜻으로 보입니다.

 이 두가지를 그림으로 표현하면 아래와 같습니다.

 h 가 써져있는 네모난 블록이 하나하나의 신경망이라고 보시면 됩니다. 그림을 보시면 h 블록으로부터 다른 h 블록으로 화살표가 이어져있는 것을 볼 수 있는데, 이전에 나왔던 출력값이 다시 입력값으로 들어가는 Recurrent한 모습을 보여줍니다. 하지만 모든 블록들이 이렇게 이어져있지 않고 여러 그룹이 존재합니다. 이렇게 여러 그룹들이 존재하는 모습이 Compositional 하다라고 볼 수 있습니다. 

 이 논문의 모델을 잘 표현한 그림이라 조금만 더 설명드리겠습니다. h 는 신경망이라고 했는데, 아래에 위치한 블록들이 입력값, 위에 위치한 블록들이 출력값입니다. 모델의 입력으로는 현재 실행하는 프로그램과 현재의 State 값이 들어가게 됩니다.

<Input>

1) 현재 실행되는 프로그램을 나타내는 임베딩 값

2) 현재의 State는 두 개의 값으로 구성됩니다. 프로그램을 실행할 때 같이 들어온 매개변수와 환경의 상태입니다.

- 환경의 상태는 task를 수행할 환경마다 다르기 때문에 환경마다 특정한 Encoder를 사용합니다. 위의 그림에서는 이미지로 받아들이기 때문에 CNN 기반의 Encoder가 사용될 것입니다.

- 매개변수 또한 환경마다 다를 수 있기 때문에 특정 Encoder에 같이 들어가게 됩니다.

2)에서 사용되는 Encoder를 통해 NPI 모델이 받아들일 수 있는 Input의 사이즈에 맞게 항상 환경의 특징들이 추출된다고 볼 수 있습니다. 

<Output>

1) KEY 는 다음에 실행할 프로그램을 찾을 수 있는 키값입니다. 이를 이용해 프로그램 메모리에서 적절한 프로그램을 찾습니다.

2) END 는 현재 실행되고 있는 프로그램을 종료할 확률입니다. 특정 쓰레쉬홀드값을 넘어가게끔 하면 이 프로그램은 끝을 맺습니다.

3) ARG 는 다음에 실행할 프로그램의 매개변수입니다.

전체적인 동작의 과정은 알고리즘을 보시면 좀 더 이해하시기 편할 것 같습니다.

 * 반복문 while의 조건은 END 확률이 쓰레쉬홀드값을 넘어가기 전까지 계속해서 반복됩니다.

 1) 매개변수와 환경을 Encoder에 넣어서 나온 출력값 s 와 현재의 프로그램 p, 그리고 RNN이기 때문에 이전 출력값 h도 함께 모델에 입력값으로 넣습니다.

 2) 모델로부터 나온 출력값 h 를 이용하여 KEY, END, ARG를 구해냅니다.

 3) KEY를 이용하여 어떤 프로그램을 실행할지 알아내는 과정은 프로그램 메모리에 저장되어 있는 키값들 중에서 가장 유사한 값을 찾는 방식입니다.

 4) 만약 이번에 실행할 프로그램이 ACT(가장 원자단위의 행동 프로그램이라는 뜻입니다) 라면 환경에 대해서 실행하고, 아니라면 재귀적으로 RUN 함수를 호출하면서 또 다른 모델구조를 만듭니다.(Compositional)

 위 알고리즘과 그림을 함께 보시면, 대략적인 구조가 이해되실 것 같습니다. 

Training

 이 모델의 학습은 아래의 식을 이용합니다.

 즉, 이전의 Input history가 주어질 때 output으로 나와야하는 Ground-truth output의 확률을 높이는 방식으로 되어있습니다. 이는 아래와 같이 표현할 수 있습니다. 

Experiments

 이 논문에서의 실험 환경은 3가지입니다.

 1) Addition

 input1, input2, carry, output 4개의 row로 이루어져 있으며, 각각의 row마다 포인터가 존재합니다. 두 개의 인풋이 들어오면 덧셈 연산을 합니다.

 환경마다의 특정한 Encoder가 필요하다고 했었는데, Addition 환경에서의 Encoder는 위와 같습니다. Q는 각각의 포인터가 가리키는 숫자가 원핫 인코딩으로 표현되어있습니다. 즉, 이 환경에서는 4개의 포인터가 가리키는 4개의 숫자와 함께 매개변수 3개를 합쳐서 MLP에 입력하여 나온 출력값을 S 값으로 사용합니다.

2) Sorting

 Bubble-sort를 이용하여, 정렬을 하는 환경입니다. 하나의 row에 두 개의 포인터로 이루어져 있습니다.

 Encoder는 위 Addition과 비슷하게 이루어져 있습니다.

3) Canonicalizing 3D Models

 3D 환경에서 주어진 차의 모습을 target 각도로 돌리는 것이 목표인 환경입니다. 

 Encoder가 위 두 개의 환경이랑 조금 다르게 되어있습니다. 이 환경에서 target은 각도와 고도가 각각의 숫자로 나타내어져 있고, 그것을 Q를 통해 읽게 됩니다. 또한 3D 환경이므로 현재의 상태를 CNN을 통해 파악하게 됩니다.

 첫번째 실험과 두번째 실험은 bubble-sort task에 대하여 평범한 Seq2Seq LSTM과의 비교실험입니다. Bubble-sort는 시간복잡도가 O(N^2)이기에, 정렬해야할 숫자가 길어질수록 급격하게 상태정보가 커지게 되고, 이는 LSTM의 hidden state에 전부 담기에 불가능해집니다. 하지만 NPI는 Compositional 하기 때문에 평범한 LSTM에 비해 더 많은 상태저장이 가능합니다.

 훈련 데이터는 2개에서부터 20개까지의 숫자 리스트들에 대한 64개의 예시와 1216개의 trace 과정들을 통해 이루어집니다.

 길이가 20인 배열의 정렬을 가능하게끔 하기 위해 필요한 훈련 데이터의 갯수를 그래프로 나타낸 것입니다. 한 눈에 보기에도 NPI가 2개부터 학습을 시작하여, 8개에서 이미 학습을 완료한 점이 눈에 띕니다. 그에 반해 Seq2Seq 모델은 64개부터 시작하여, 250개에 이르러서야 어느정도 학습이 되는 모습입니다.

 이번에는 길이가 20을 넘어서는 배열에 대해서도 정렬이 가능한지에 대한 실험입니다. 이것이 가능하다는 것은 배우는 것에 대해 일반화를 했다고 볼 수 있는데, NPI가 Seq2Seq 모델에 비해 훨씬 강력한 일반화 능력을 보여주고 있습니다.

 NPI는 추가적인 프로그램을 학습시키는 것이 가능합니다. 이것에 대해 먼저 걱정되는 점은 새로운 학습이 기존의 task에 대한 성능을 떨어뜨릴 수 있지 않을까 하는 점입니다. 이를 극복하기 위해 NPI core 모델의 가중치는 고정을 시키고, 오로지 프로그램 메모리를 업데이트하는 식으로 프로그램을 추가합니다. 하지만 이렇게 되면 실수로 기존의 프로그램이 새로운 프로그램을 불러버리는 일도 있을 수 있습니다. 이점을 극복하기 위해서는 이 논문에서는 새로운 프로그램의 trace들 뿐만 아니라, 기존에 존재하던 trace들 또한 학습에 사용했습니다.

 위 실험은 하나의 task에 대해서 학습시킨 Single 모델과, 한번에 여러가지의 task를 학습시킨 Multi모델, 그리고 Multi에 추가로 Max 프로그램을 학습시킨 모델 세 가지의 Acc를 비교합니다. 이를 통해

1) 새로운 프로그램을 학습시키는 것은 기존의 다른 task들의 성능에 영향을 주지 않는다는 것

2) 하나의 NPI 코어만으로 여러 task에 접목하는 것이 가능하다는 것

두 가지를 증명했습니다. 

Conclusion

 오로지 하나의 NPI만으로 비슷하지 않은 여러 환경들의 프로그램들에 대해 배우는 것이 가능한 모델입니다.

 그리고 NPI는 LSTM과 비교하여 강력한 일반화 능력을 가지고 있습니다.

 또한 NPI는 여러 새로운 프로그램들을 기존 프로그램을 잊지 않으면서 학습하게끔 할 수 있습니다.

https://www.acmicpc.net/problem/1014

 처음 봤을 땐 어디부터 DP를 적용해나가야 할지 난감했던 문제입니다.

 문제를 보면, 한 자리에 누군가를 앉히면 저 화살표로 나타내어진 부분은 다른 사람을 앉힐 수가 없습니다.

 위 그림에선 B를 제외하곤 다른 사람을 앉힐 수 없습니다.

​

 점화식을 생각해보기 위해, 문제를 좀 더 생각해보겠습니다.

 세로줄 하나만 있을 때를 생각해보면, (M = 1) 이 때는 모든 칸을 사람으로 채워도 됩니다. 같은 세로줄 내부에선 어디 자리에 누굴 앉힌다고 해서, 영향을 받지 않기 때문입니다.

 그 옆에 세로줄을 하나 더 추가한다고 생각해본다면, 새로 생긴 세로줄 또한 같은 세로줄 내부에서 누가 앉았다고 영향을 받진 않지만, 전 줄에서 어떻게 앉았느냐에 따라 영향을 받게 됩니다.

 만약 전 줄에서 3번째에 사람이 앉았다면, 이번 줄에서는 2, 3, 4번째에서 사람이 앉을 수 없게 됩니다. (앉으면 커닝을 할 수 있는 조건에 만족하게 됩니다.)

 따라서 전 줄에서 어떻게 앉았느냐에 따라 이번 줄에서는 앉을 수 있는 경우의 수가 달라지게 됩니다.

이를 이용하여 DP식을 세워보자면

DP(n, m) = (m - 1) 번째 줄에서 n 상태로 사람이 앉았을 때 m 번째 줄에서 나올 수 있는 가장 많은 학생의 수

 상태를 표현하기 위해서는 몇 번째 자리에 사람이 앉았는지를 표현할 수 있어야 합니다. 마침 n <= 10 이기 때문에 비트 마스크를 사용하기에도 적절합니다.

​

 이 개념을 가지고 소스코드를 짜 보면 아래처럼 됩니다.

import java.io.*;
import java.util.*;

public class Main {
    static int DP[][];
    static boolean obstacles[][];
    static int N, M;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; ++t) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            DP = new int[1 << N][M];
            for(int n = 0 ; n < (1 << N) ; ++n){
                Arrays.fill(DP[n], -1);
            }
            obstacles = new boolean[N][M];
            for (int n = 0; n < N; ++n) {
                String input = br.readLine();
                for (int m = 0; m < M; ++m) {
                    if (input.substring(m, m + 1).equals("x")) obstacles[n][m] = true; // 장애물 체크
                }
            }
            bw.write(Integer.toString(getDP(0, 0)) + "\n");
        }
        bw.flush();
        bw.close();
    }

    static int getDP(int n, int m) { // n = 저번 줄에서 사용한 것, m = 현재 줄
        if (m == M) return 0; // 모든 줄을 체크한 경우
        if (DP[n][m] != -1) return DP[n][m];
        int lastN = n; // 현재 턴에서 사용 불가능한 자리 표시 위한 변수
        for (int i = 0; i < N; ++i) {
            if ((n & (1 << i)) > 0) {
                lastN |= (1 << (i + 1)); // 이 자리 또한 사용 불가능
                lastN |= (1 << (i - 1)); // 이 자리 또한 사용 불가능
            }
        }
        int result = getDP(0, m + 1); // 아무 학생도 앉히지 않고 다음 줄로 넘어가는 경우 (Default)
        for (int i = 1; i < (1 << N); ++i) { // 학생을 앉히는 경우
            if ((i & lastN) > 0) continue; // 나올 수 없는 경우의 수 제외하기
            int count = 0; // 학생 수를 세기 위함 (비트 연산)
            boolean isAvail = true;
            for (int j = 0; j < N && isAvail; ++j) {
                if ((i & (1 << j)) > 0) { // 이 자리에 학생이 앉아있는 경우
                    count++;
                    if (obstacles[j][m]) isAvail = false; // 이 자리가 장애물이 있으면 이 또한 나올 수 없는 경우의 수
                }
            }
            if(!isAvail) continue; // 장애물 체크
            result = Math.max(result, getDP(i, m + 1) + count);// 가능한 경우 재귀적으로 전달
        }
        return DP[n][m] = result;
    }
}

결정트리 - Decision Tree

 스무고개 많이들 해보셨을 텐데요. 결정 트리는 이와 비슷하게 의사를 결정하는 알고리즘 구조입니다.

 지도학습(Supervisior Learning)* 분류에 속하는 이 알고리즘은 매우 직관적으로 데이터들을 어떤 식으로 분류하는 확인할 수 있습니다. 간단한 예시를 들어보겠습니다.

Q) 젊은 친구 John은 이런 날 나가서 놀까요?

 위의 질문에 나올 수 있는 답은 O, X 둘 중 하나라고 해보겠습니다. 

 그리고 이 답을 유추하기 위한 속성 값(Attribute)들이 주어집니다. 예를 들어, 

1) 비가 온다 / 오지 않는다 (Boolean Attribute)

2) 온도가 X 이다. (실수 Attribute)

3) 같이 놀 친구가 X명 있다. (정수 Attribute)

 위와 같은 속성값들은 예시이며, 그 외에도 다양하게 존재할 수 있습니다. 

 결정트리결정 트리 모델은 위 그림처럼 특징들을 이용해 분류를 하는 모델입니다. 분기를 어떤 기준으로 설정할 것이고, 어떤 기준을 가장 위에 놓을 것이냐가 결정 트리에서는 중요한 문제가 됩니다. 이를 선택하기 위한 기준으로 엔트로피라는 개념을 사용하는데, 쉽게 설명드리자면 상황마다 가장 깔끔하게 나눌 수 있는 기준을 찾아서 설정한다고 보시면 됩니다.

 결정트리에 대한 간략한 설명은 여기서 마치겠습니다.

* 지도학습(Supervisior Learning) - 머신러닝의 한 분야로써, 훈련데이터를 이용해 머신러닝 모델이 Input X가 주어질 때 Output Y를 출력하게끔 합니다. 분류(Classification), 회귀(Regression) 등의 세부 분야로 나뉩니다.

UCI Repository 살펴보기

https://archive.ics.uci.edu/ml/index.php

 UCI repository는 머신러닝과 지능시스템을 위한 여러 데이터들을 저장하고 있는 저장소입니다. 

 여러 데이터셋을 무료로 사용이 가능하며, 그중 monk's problem dataset을 살펴보겠습니다.

 데이터셋에 대한 설명은 Attribute Information 부분에 되어있습니다. 분류(Classification) 문제에 사용하기 위한 클래스와 속성(Attributes)에 대해 간략하게 나타나 있습니다.

 monks-1에 해당하는 test와 train을 다운로드합니다. 여기서 test는 결정 트리 모델이 잘 만들어졌는지 시험하기 위한 데이터셋이고, train은 결정트리 모델을 만들기 위해 필요한 데이터셋을 의미합니다. 데이터셋에 따라 위와 다르게 하나의 파일만 있는 경우도 있습니다. 

 파일은 이전의 Attribute Information에서 설명한 내용들이 순서대로 띄어쓰기로 구분되어 작성되어 있습니다. 이를 파이썬에서 읽어 들여서 결정 트리를 만들어보겠습니다. 파일에 따라 쉼표나 다른 무언가로 구분되어 있는 경우도 있습니다.

Python with skLearn

 먼저 데이터 파일을 읽는 작업이 첫 번째로 이루어져야 할 작업입니다. 학습을 위한 train 데이터와 테스트를 위한 test 데이터로 구분하여 파일을 읽었습니다. 파일을 읽는 작업은 pandas의 read_csv 함수를 이용하였습니다.

 * 모듈들의 다운로드는 Anaconda 환경이라고 하면, conda instasll numpy 이런 식으로 가능합니다.

  머신러닝 모델은 함수에 비교되곤 하는데 함수처럼 속성 등 모델에 Input으로 들어가게 되는 값을 x, Input을 이용하여  모델이 출력해야 할 클래스 값을 y로 구분하였습니다. 위 과정을 통해 클래스와 속성이 섞여있는 데이터가 깔끔하게 분리되는 것을 확인할 수 있습니다.

 결정 트리는 이미 사이킷런 라이브러리에 존재하고 있어서 쉽게 만들 수 있습니다. 미리 준비해둔 train 데이터를 통해 fit 함수를 통하여 결정 트리를 학습시킬 수 있습니다. 학습이 끝난 뒤 score 함수를 통해 x가 주어질 때 y를 얼마나 잘 출력해 내는지 확인할 수 있습니다.

 위 값만 보고서는 결정 트리가 잘 만들어진 것인지에 대해 의문을 품을 수 있습니다. 이를 위해 시각적으로 결정 트리를 확인할 수 있는데, 이를 도와줄 프로그램이 추가적으로 설치가 필요합니다. 바로 GraphViz입니다.

 msi 파일을 클릭하여 다운로드를 하시면 됩니다. 이 프로그램은 그래프 시각화에 필요한 소프트웨어입니다.

 설치한 GraphViz 프로그램을 환경변수 PATH에 넣어줍니다. 보통 설치하실 때 추가적으로 설정하신 부분이 없다면 저 위치에 존재하고 있습니다. 위 코드를 실행하고 나면 dt.png 파일이 경로에 생성되게 됩니다. 

 * 만약 위처럼 코드를 실행하였을 때, dot 파일을 찾을 수 없다고 뜨는 경우에는 graphviz 모듈을 다운로드해보시길 바랍니다. Anaconda 환경 기준으로 conda install graphviz 로 다운로드 할 수 있습니다.  

 이상으로 간략하게 데이터셋을 이용한 머신러닝, 그중에서도 결정 트리를 생성했습니다. 이와 비슷하게 다른 데이터셋에 대해서도 적용하실 수 있을 것입니다. 다만 UCI에는 정말 다양한 데이터가 존재하기에 이처럼 결정 트리를 생성하기에는 조금 부적절한 데이터도 있을 수 있습니다.

 * 공부하며 작성하는 글이기에, 틀린 점이나 지적할 점이 있으시다면 댓글로 알려주시면 감사하겠습니다.

[Abstract]

 데모 비디오들로부터 행동 결정 로직을 해석하는 일은 사람을 사람을 흉내 내고 협력하는 데 있어서 키 포인트라고 말하며, 이 로직을 시각적으로 복잡한 여러 데모 비디오들로부터 DSL*을 이용하여 프로그램 포맷으로 생성해내는 Neural Program Synthesizer 모델을 이 논문은 제안합니다. 

 이 모델의 핵심 요소 두 가지는 아래와 같습니다.

 1) Summarizer module - 여러 개의 데모 비디오를 Compact 하게 통합하여 주는 모듈

 2) Multi-task objective - end-to-end 학습에서 모델의 학습 능력을 높이기 위한 부가적인 목적함수들

이 논문의 데모 코드는 https://github.com/shaohua0116/demo2program 에서 확인할 수 있습니다.

* DSL(Domain Specific Language) - 특정 도메인에 특화된 언어로써 이 논문의 모듈이 프로그램을 생성할 때 이를 이용해 생성합니다. 프로그램은 연속된 각각의 토큰들로 생각할 수 있습니다. 이 논문에서는 크게 3가지(Action, Perception, Control flow)로 토큰들을 분류합니다.

[Approach]

 위의 그림은 전체적인 모델의 구조를 보여줍니다.

 모델은 크게 3가지 모듈로 나눌 수 있습니다. 

 1) Demonstration Encoder - 데모 비디오 입력을 통해, 에이전트의 Action과 Perception을 Embedding 합니다.

 2) Summarizer Module - 각각의 데모 비디오들로부터 나온 Embedding을 통합하는 역할을 합니다.

 3) Program Decoder - Summarizer로부터 나온 Vector를 코드의 Sequence로 decode 합니다.

 각 모듈에 대한 추가 설명은 아래에 이어서 하겠습니다.

<Demonstration Encoder>

 어떠한 프로그램으로부터 생성된 데모 비디오가 k개까지 있다고 할 때, 각각의 데모 비디오들은 일정한 time step을 구분으로 하는 state의 연속된 sequence라고 표현할 수 있습니다. state를 encoder(CNN)에 입력으로 얻은 feature 값을 S로 위 그림에서 표현합니다.

 Demo Encoder는 LSTM을 사용하며, S를 차례대로 입력으로 넣고 최종적으로 나오게 되는 cell state c, hidden state h가 데모의 전체적인 내용을 함축한다고 생각할 수 있게 됩니다. Average Pooling 과정에서는 각각의 c와 h를 더해 평균을 낸 Z 를 만들게 됩니다.

<Summarizer Module>

 위에서 만들어진 Z 를 활용하여 데모들을 Review하는 과정을 거치게 됩니다. 이때의 LSTM은 Z 로 Initialized되며, 각 step마다의 입력은 Demo Encoder 과정에서 step마다의 hidden state h 를 이용하게 됩니다. 이는 데모들의 전체적인 관점에서 다시 한번 각각의 데모들을 리뷰하는 과정이라고 보실 수 있겠습니다. 이를 이용해 최종적으로 데모마다 벡터를 뽑게 되고, 이를 Relation Network를 이용하여 최종적으로 모든 데모들이 요약된 벡터 Vsummary 를 만들게 됩니다. Relation Network 관련 부분은 단순하게 생각하면 각각의 데모마다의 관계를 계산하는 모듈이라고 생각할 수 있을 것 같습니다. 

<Program Decoder>

  프로그램을 생성하는 모듈입니다. Vsummary 로 initialized된 LSTM을 사용하며 각각의 step마다 이전 step에서의 토큰Embedding을 입력으로 받고, 출력으로 다음으로 나오게 될 토큰들의 확률을 계산합니다.

<Learning>

 M : training example의 총 개수

 N : 토큰의 총 개수

 W : 이전 토큰들의 sequence

 D : 데모

 데모 D와 이전 토큰들의 시퀀스가 주어질 때 다음 토큰으로 ground-truth 토큰이 되게끔 합니다.

<Multi-task Objective>

 위 모델은 End-to-End로 학습을 진행합니다. 하지만 데모들로부터 각각의 time step에서 Action들과 Perception을 잘 인식하여 뽑아냈는지 확인하기가 어렵습니다. 만약 환경이 시각적으로 좀 더 복잡하다면 이는 모델에게 있어 더 어려운 일이 될 것입니다. 이를 해결하기 위해 두 가지의 Loss 함수를 추가적으로 이용합니다. 

 첫 번째로 Action Loss 입니다. Summarizer Module에서 Relation Network에 들어가기 전 review 과정에서 나왔던

V 와 이전까지의 액션들의 시퀀스 A가 주어질 때 다음 action이 ground-truth action이 되게끔 합니다. 즉, 각각의 데모 비디오로부터 올바른 action sequence를 뽑아내게끔 도와주는 역할을 하는 것으로 보입니다. 

 두 번째로 Perception Loss 입니다. perception은 각각의 perception에 대해서 {0, 1} 바이너리로 표현된 L차원 벡터로 이루어져 있습니다. 이번에도 review 과정에서 나왔던 V 와 이전까지의 perception sequence가 주어질 때 L개의 perception에 대해서 올바른 ground-trueth perception이 나오도록 합니다. 이 또한 위의 Action Loss와 비슷하게 올바른 perception을 뽑아낼 수 있도록 도와주는 역할을 하는 것으로 보입니다.

 지금까지 나온 세 가지 Loss를 각각에 가중치를 곱해 더한 값을 Loss 함수로 위 모델은 사용하게 됩니다.

[Experiments]

 위 논문은 Karel과 VizDoom 두 가지 환경을 사용하여 실험을 진행합니다. 

 평가 척도로는 3가지를 제시하였습니다.

 1) Sequence Accuracy - 코드가 정확하게 일치하는지를 평가하는 척도

 2) Program Accuracy - 같은 의미의 코드라도 다르게 쓰일 수가 있는데 이 점을 감안하여 코드 일치를 평가하는 척도

 3) Execution Accuracy - ground-truth 프로그램과 실행 결과를 비교해서 평가하는 척도

 <Karel Environment>

 Karel 환경은 8x8 Grid 2D 환경으로, 5가지의 Action 및 5가지의 Perception 토큰이 존재하는 간단한 환경입니다. 랜덤으로 35000개의 프로그램을 생성하여, 25000개의 train, 5000개의 valid, 5000개의 test 집합으로 나누었다고 합니다. 각각의 프로그램마다 10개의 seen demo와 5개의 unseen demo를 생성했습니다. (unseen demo는 execution accuracy를 평가할 때 사용됩니다.)

 첫 번째 실험은 아까의 세 가지 척도를 활용하여 모델들을 비교하는 실험입니다. Induction 모델은 프로그램을 생성하지 않고, 단순히 Action들의 Sequence를 만들어내는 모델입니다. 비교할 때 공평성을 위해 Perception 정보를 매 step마다 입력으로 넣어주었다고 하며, 그 결과가 괄호 안의 값이라고 보시면 됩니다. 위 논문에서 제안한 두 가지 요소들이 더해짐으로써 성능이 좋아지는 것을 확인할 수 있습니다. 

 두 번째 실험은 summarizer module의 힘을 보여주는 실험입니다. seen demo의 개수를 k라고 할 때, k가 늘어날수록 Summarizer module을 통한 Execution Accuracy가 증가하는 것을 확인할 수 있습니다.

<VizDoom Environment>

  Doom은 플레이어가 연속된 상태 공간에서 몬스터, 아이템 및 무기로 상호작용을 하는 3인칭 슈팅 게임입니다. VizDoom은 Doom을 베이스로 한 AI platform입니다. 120x160x3 pixel로 표현되는 7개의 Action, 6개의 Perception 토큰이 존재하는 좀 더 복잡한 환경입니다. 이번에는 80000개의 train, 8000개의 test 집합을 생성하였고, 각각의 프로그램마다 25개의 seen demo와 10개의 unseen demo를 생성했습니다.

 첫 번째 실험은 모델 비교 실험입니다. 환경이 좀 더 복잡해지자 Induction 모델의 성능이 확연히 떨어지는 것을 확인할 수 있습니다. 이는 명시적으로 프로그램을 생성해내는 Synthesis 모델의 장점이 드러난다고 볼 수 있습니다. 그리고 한 가지 더 눈여겨볼 점으로 생성된 프로그램들의 구문이 99.9% 정확했습니다. 이는 DSL의 구문 또한 모델이 학습한다고 볼 수 있습니다.

 두 번째 실험은 condition에 따른 행동 변화의 추론에 대한 중요성을 입증하기 위한 실험입니다. 이를 위해 if-else 구문으로 이루어진 간단한 프로그램들로 모델을 비교하며 실험했습니다. Induction model은 condition에 따른 행동 변화를 추론하는 데 있어서 어려움을 가지고 있는 것이 성능으로 드러납니다. 그에 반해 모든 모듈이 포함된 Synthesis 모델은 높은 성능이 보입니다.

 위 그림은 k개의 seen demo가 있을 때 나타나는 execution accuracy 성능을 보여줍니다. Induction model은 demo가 많이 주어지더라도 그에 맞는 성능을 이끌어내지 못하는 점을 확인할 수 있습니다. 그리고 summaraizer module은 demo의 개수가 늘어날수록 급격하게 유무의 차이가 나타나는 점을 확인할 수 있습니다. 이를 통해 summarizer module이 중요한 역할을 한다는 점을 다시 확인할 수 있습니다.

[Conclusion]

이 논문은 여러 데모 비디오로부터 프로그램을 생성해내는 모델을 제안했으며, 이에 추가로 성능을 높이기 위한 summarizer module과 multi-task objective를 제안했습니다. 평가를 위해 fully-observable의 Karel 환경과 partially-observable의 VizDoom 환경에서 실험을 진행했으며, 실험을 통해 제안된 모델이 좋은 성능을 낸다는 것을 증명했습니다.

* 공부하면서 리뷰를 하고 있기 때문에, 틀린 점이 있다면 지적해주시면 감사하겠습니다.