[AGI] Program Synthesis - 3

2장의 간단한 recap과 함께 시작한다.

The problem

풀을 안쪽에, 버섯을 바깥쪽에 놓는 사각형을 그리는 것이 문제이다. 이 문제는 입력-출력, spec의 specification으로 표현된다.

---

The ground-truth distribution

spec이 주어졌을 때 meaning matrix에서의 행 M[spec, :]를 보자. 모든 사각형(프로그램)에서 이 행은 우리의 spec이 옳은지 틀린지를 나타낸다.

 

주어진 spec에 대해 program synthesis의 정답 분포(ground-truth distribution)은 아래와 같이 정의한다:

올바른 프로그램의 개수(N)을 센 다음, 각 올바른 프로그램에 1/N의 가중치를 부여하는 것이다.

$$ P_{ground-truth}(prog\mid spec) \propto 1(M[prog, spec])$$

프로그램 합성은 이런 ground-truth distribution에서 샘플을 뽑아내는 것을 요구한다. 그러나 ground-truth distribution에서 샘플을 뽑는 것은 매우 어렵다. spec이 주어졌을 때 프로그램이 올바른 지 체크하는 것은 쉽지만 올바른 프로그램을 만드는 것은 힘들다.

---

Program synthesis as rejection sampling

실제에서는 synthesis를 이용하여 ground-truth distribution에서 rejection sampling을 진행한다.

$$P_{synthesis}(prog\mid spec) \propto P_{writer}(prog\mid spec)1(M[prog, spec])$$

즉, specification이 주어지면 프로그램 작성자는 많은 양의 프로그램을 만들고 checker는 주어진 spec을 기준으로 프로그램들이 올바른지 필터링을 진행한다.

---

Getting a program-writer close to ground-truth

작성자의 분포가 ground-truth 분포에 가까울수록 synthesis 알고리즘이 샘플링해야 할 프로그램의 수는 줄어들며 여기서 이 가까움은 기댓값 KL-divergence로 수학적으로 정의된다.

$$\mathbb{E}_{spec \sim P(spec)}(D_{KL}(P_{ground-truth}(prog\mid spec)\parallel P_{writer}(prog\mid spec)))$$

즉, specification의 사전 분포 $P(spec)$에 대해 우리는 $P_{writer}(prog\mid spec)$이 $P_{ground-truth}(prog\mid spec)$에 가까워지는 것을 원한다.

 

이런 프로그램 작성자를 얻기 위해 우리는 언어 모델(language models)을 활용한다.

---

Language models

언어는 문자들의 시퀀스로 이뤄진 문자열의 집합이다. 언어 모델은 해당 언어 내의 문자열들에 확률을 부여하는 모델이다.

Unconditional generation

우리는 unconditional language models로 시작한다. 이 모델은 specification을 무시한다. 물론 한계는 존재하지만 이 방식은 좋은 시작점을 만들어준다.

$$P_{writer}(prog\mid spec)\approx P_{writer}(prog)$$

예제로, **"[1, 3, 1, 4]"**라는 프로그램을 나타내는 문자열을 고정된 타깃으로 삼고, 다양한 unconditional language model이 이 문자열을 얼마나 잘 생성하는지를 분석해볼 것이다.

 

all strings

우리는 단순히 무작위의 문자를 숫자만큼 뽑아서 만들 수 있다. 이 방법은 문자열의 모든 가능성을 포함하고 있다.

def writer1():
    return ''.join(random.choice(string.printable) for i in range(9))
print(writer1()) # you should see something like "=1Vi![Au37"

 

"[1, 3, 1, 4]"는 9개의 문자를 가지고 있다. 각각의 확률은 1 / len(string.printable)이고 계산해보면 이 문자열이 정확히 생성될 확률은 (1/100)^9의 확률이다. 매우 좋지 않다.

 

DSL

우리는 프로그램처럼 보이는 문자열만 생성하도록 제약을 걸 수 있다. 이것을 domain specific language(DSL)이라고 부른다. DSL은 프로그램의 모든 문자열중 합리적인 하위집합을 정의한다. DSL은 generator로부터 구체화된다.

def writer2():
    # W is globally defined to be 6
    U = random.randint(0,W)
    D = random.randint(0,W)
    L = random.randint(0,W)
    R = random.randint(0,W)
    return '['+str(U)+','+str(D)+','+str(L)+','+str(R)+']'
print(writer2()) # you should see something like "[5,2,1,0]"

 

언어에 이러한 구조를 보게 되면 우리는 확률이 (1/6)^4까지 올라간 것을 확인할 수 있다. 그러나 아직도 "[5, 2, 1, 0]"과 같은 해석하기 힘든 프로그램을 포함하고 있다.

 

better DSL

우리는 더 나아가서 DSL을 더 타이트하게 만들 수 있다. 해석할 수 없는 프로그램을 제외하는 방식으로

def writer3():
    U = random.randint(0,W-2)
    L = random.randint(0,W-2)
    height = random.randint(1,W-U)
    width = random.randint(1,W-L)
    D, R = U+height, L+width
    return '['+str(U)+','+str(D)+','+str(L)+','+str(R)+']'
print (writer3()) # you should see something like "[0,2,4,5]"

 

여기서 "[1, 3, 1, 4]"를 만들 확률이 어떻게 되는가? 그거는 너의 계산에 맡긴다. 그리고 추가로 writer3가 만드는 프로그램들이 모두 해석이 가능한 프로그램인가?

---

Synthesis with prior distribution

unconditional language models은 사전 분포(prior distribution)을 제공한다. 이는 specification이 주어지지 않은 상태에서 프로그램들이 자연스럽게 분포하는 방식을 의미한다. 우리는 이 prior $P(prog)$를 writer로 활용할 수 있다.

$$P_{synthesis}(prog\mid spec) \propto P(prog)1(M[prog,spec])$$

이런 접근은 프로그램 공간이 작은 경우에 충분히 괜찮은 결과를 제공하며, program synthesis 실무자들이 가장 먼저 시도해보는 방법 중 하나이다.

---

Training a conditional generator

조건부 생성(conditional generation)에서는 프로그램 작성자는 spec을 그럴듯한 프로그램의 샘플링으로 처리한다.

$$P_{writer}(prog\mid spec) = P_\theta(prog\mid spec)$$

여기서 작성자는 neural networks with weights와 같은 파라미터를 가진 함수를 사용한다. 목표는 KL-divergence를 최소화하는 theta값을 찾아내는 것이다.

$$\min_\theta \underset{spec\sim P(spec)}{\mathbb{E}}(D_{KL}(P_{ground-truth}(prog\mid spec)\parallel P_\theta(prog\mid spec)))$$

여기서 수수께끼가 하나 있는데 이것을 최적화하기 위해서는 ground-truth distribution이 필요하다! 우리는 이것을 다음 식으로 해결했다.

$$P(spec){P(prog \mid spec)}= P(\text{prog}, \text{spec})= {P(\text{prog}) P(\text{spec} \mid \text{prog})}$$

여기서 $P(prog\mid spec)$은 program synthesis가 어렵기 때문에 $P(spec\mid prog)$로 바꿔서 spec generation은 쉽도록 만들었다.

---

The approximation lemma of program synthesis

lemma : D를 joint-distribution P(prog, spec)에서 나온 (prog, spec)의 쌍으로 이루어진 데이터라고 하자. 우리는 D에 대한 조건부 밀도 추정을 이용하여 ground-truth synthesis distribution을 근사화할 수 있다.

$$
\begin{aligned}
&\quad\min_\theta \underset{spec\sim P(spec)}{\mathbb{E}}(D_{KL}(P_{\text{ground-truth}}(prog\mid spec)\parallel P_\theta(prog\mid spec))) \\
&= \max_\theta \underset{(prog,spec)\sim P(prog,spec)}{\mathbb{E}}\log P_\theta(prog\mid spec) \\
&\approx \max_\theta \underset{(prog,spec)\sim D}{\mathbb{E}}\log P_\theta(prog\mid spec)
\end{aligned}
$$

큰 데이터셋 D와 표현력이 충분히 높은 모델이 있다면 P_theta(prog|spec)을 훈련시키면 ground-truth 분포에 도달할 수 있을 것이다. 추가로 D를 생성하는 것은 자동적이므로 사람이 필요가 없다! 이것은 나중에 더 자세히 나올 예정이다.

---

Making the dataset D of joint-distribution samples

D의 각 데이터는 아래의 분포에서 나온 (prog, spec)의 튜플이다:

$$P(prog,spec) = P(prog)P(spec\mid prog)$$

우리는 prior로부터 프로그램을 먼저 만들고, 그 후에 spec을 생성할 것이다.

---

generating programs from a prior

우리는 무엇을 해야할지 이미 알고 있다. 이것은 단순히 unconditional language을 생성하는 것이다(앞에서 봤던 writer3처럼). 그러나 우리가 더 자연스러운 데이터셋을 더 모을 수 있다면 더 나은 prior가 될 것이다. GitHub의 Codex가 그러한 예시가 될 수 있다.

---

generating specifications from programs

프로그램이 주어졌을 때 우리는 specification을 다음과 같은 방법으로 생성할 수 있다:

1. 무작위의 입력을 샘플링한다
2. 그 입력에 대한 출력값을 위해 프로그램을 실행한다

우리의 사각형 문제에서는 먼저 무작위의 좌표를 만들고 사각형이 올바른지를 확인하면 된다.

def sample_input():
    return random.randint(0,W-1), random.randint(0,W-1)

def sample_spec(prog):
    # pick a number of inputs, up to 10 patches of mushroom / grass total
    n_inputs = random.randint(1,10)
    inputs = [sample_input() for i in range(n_inputs)]
    prog = eval(prog) # needed since for this post progs are modelled as strings
    outputs = [is_inside(prog, input) for input in inputs]
    return list(zip(inputs, outputs))

r_spec = sample_spec("[1,3,1,4]")
print (r_spec) # [((5, 2), False), ((4, 4), False), ((0, 1), False), ((3, 3), True)]

---

putting it together

synthesis problem이 주어졌을 때 데이터셋 D를 만들 수 있는 방법은 아래와 같다:

def sample_D(n_samples):
    D = []
    for i in range(n_samples):
        prog = writer3()
        spec = sample_spec(prog)
        D.append((prog, spec))
    return D

D = sample_D(10000)
print (D[4542]) # should see something like ('[3,5,4,6]', [((1, 0), False), ((5, 0), False)])

---

D is a sample of M

우리는 데이터셋 D를 meaning matrix M의 샘플링된 요약본으로 볼 수 있다. meaning matrix M의 모든 항목을 전부 나타내는 것은 불가능하지만, 우리는 여전히 그 일부를 샘플링할 수 있다. 더 많은 샘플을 수집할수록 우리는 M의 구조와 분포를 더 잘 파악할 수 있게 된다.

---

Conditional generation with fitted unigrams

이제 우리의 사각형 예제에 이 이론들을 대입해볼 시간이다. 가장 단순한 방법 중 하나는 unigram distribution을 사용하는 것이다. unigram distribution은 프로그램들의 속성을 독립적으로 샘플링하는 것이다. 여기서 기억해야할 것은 사각형의 4개 좌표 값은 실제로는 서로 독립적이지 않기 때문에 위의 가정은 엄밀히 말하면 틀렸다. 하지만 계산을 단순하기 위해 이 불완전한 가정을 받아들여보자.

$$P_\theta(t,d,l,r\mid spec) = P_{\theta_t}(t\mid spec)P_{\theta_d}(d\mid spec)P_{\theta_l}(l\mid spec)P_{\theta_r}(r\mid spec)$$

우리는 프로그램의 한 요소인 $t$를 multi-way classification 문제로 취급할 수 있다. 즉, specification을 입력으로 받아 사각형의 top 경계를 [0, 1, ..., W-2] 중 하나로 매핑하는 문제로 볼 수 있다는 것이다.

---

encoding the spec as a vector of binary feature

우리는 spec을 이진기법으로 인코딩 후, 직선(WxWx2)의 특징 벡터로 나타냈다.

def spec_to_bitvec(spec):
    bitvec = np.zeros((W,W,2))
    for coord,bool in spec:
        # turn bool into a number 0 or 1
        bool_num = 1 if bool else 0
        bitvec[coord[0],coord[1],bool_num] = 1
    # flatten the bitvec into a 1D array
    return bitvec.flatten()

---

fitting the factors independently

우리의 spec 특징 벡터를 기반으로 사각형의 각 속성마다 하나씩, 총 4개의 조건부 unigram 분포를 logistic regression으로 학습시켰다. boosted tree, nearest neighbors, conv-net같은 다른 classifier를 사용해보는 것도 좋다.

import sklearn.linear_model
# train the unigram distribution
def train_unigram(Data):
    spec_bitvec, Ts, Ds, Ls, Rs = [], [], [], [], []
    for prog, spec in Data:
        T, D, L, R = eval(prog)
        spec_bitvec.append(spec_to_bitvec(spec))
        Ts.append(T)
        Ds.append(D)
        Ls.append(L)
        Rs.append(R)
    # convert to numpy arrays
    spec_bitvec = np.array(spec_bitvec)
    Ts = np.array(Ts)
    Ds = np.array(Ds)
    Ls = np.array(Ls)
    Rs = np.array(Rs)
    model_T = sklearn.linear_model.LogisticRegression()
    model_T.fit(spec_bitvec, Ts)
    model_D = sklearn.linear_model.LogisticRegression()
    model_D.fit(spec_bitvec, Ds)
    model_L = sklearn.linear_model.LogisticRegression()
    model_L.fit(spec_bitvec, Ls)
    model_R = sklearn.linear_model.LogisticRegression()
    model_R.fit(spec_bitvec, Rs)
    return model_T, model_D, model_L, model_R

---

making a program-writer using the fitted unigrams

unigram distribution의 학습이 완료되면 프로그램을 작성하는데 사용할 수 있다. 사각형의 각 속성은 독립적으로 샘플링되고 이것들이 합쳐져서 사각형이 될 것이다.

def get_writer4(model_T, model_D, model_L, model_R):
    def writer4(spec):
        spec_bitvec = spec_to_bitvec(spec)
        model_T_prob = model_T.predict_proba([spec_bitvec])[0]
        model_T_sample = np.random.choice(range(len(model_T_prob)), p=model_T_prob)
        model_D_prob = model_D.predict_proba([spec_bitvec])[0]
        model_D_sample = np.random.choice(range(len(model_D_prob)), p=model_D_prob)
        model_L_prob = model_L.predict_proba([spec_bitvec])[0]
        model_L_sample = np.random.choice(range(len(model_L_prob)), p=model_L_prob)
        model_R_prob = model_R.predict_proba([spec_bitvec])[0]
        model_R_sample = np.random.choice(range(len(model_R_prob)), p=model_R_prob)
        return '[{},{},{},{}]'.format(model_T_sample, model_D_sample, model_L_sample, model_R_sample)
    return writer4

---

compare different language models as program writers

우리는 전 포스트에서 사용해던 알고리즘들을 포함해서 서로 다른 조건부/비조건부 작성자들을 이용하여 서로 다른 program synthesizer를 만들 수 있다.

# ignoring the spec for unconditional writers
synthesizer1 = get_synthesizer(lambda spec : writer1(), is_correct, 100)
synthesizer2 = get_synthesizer(lambda spec : writer2(), is_correct, 100)
synthesizer3 = get_synthesizer(lambda spec : writer3(), is_correct, 100)
# our fitted unigram writer
synthesizer4 = get_synthesizer(get_writer4(*train_unigram(D_train)), is_correct, 100)
# the manual writer from last post
synthesizer5 = get_synthesizer(manual_writer, is_correct, 100)

 

여러 가지 synthesis 알고리즘을 비교할 때 자주 사용되는 그래프는 다음과 같은 구조를 가진다:

• x축 : search budget(시도 횟수)
• y축 : 문제를 해결한 비율

그래프를 생성하기 위해 테스트 셋 $D_{test}$를 만들고 모든 synthesizer들을 이 테스트셋에서 실행시킨다.

to_plot = [[], [], [], [], []]
    for _, spec in D_test:
        for synth_id, synth in enumerate([synthesizer1, synthesizer2, synthesizer3, synthesizer4, synthesizer5]):
            samples_needed, prog = synth(spec)
            to_plot[synth_id].append(samples_needed)
    print (to_plot)

 

0부터 100 사이의 다양한 budget 값에 대해, 각 budget 이하로 문제를 해결한 synthesis 사례의 개수(또는 비율)를 카운트하여 그래프로 나타낸다.

https://evanthebouncy.github.io/program-synthesis-minimal/generating-programs/

writing programs with language models