[AGI] Program Synthesis - 2

이번에는 간단한 예시를 들어볼 것이다. program synthesis를 진행하기 위해서는 당연히 풀어야할 문제를 정의해야 한다.

 

Grass turtle and mushrooms

너가 거북이를 감싸는 사각형을 6x6 그리드 위에 그리고 싶다고 생각을 해보자. 너는 풀은 사각형 안쪽에, 그리고 버섯은 사각형 바깥쪽에 놓고 싶다.

필드가 주어졌을 때, 너는 어떤 방식으로 빠르게 사각형을 그릴 것인가?

---

Modeling programming

program synthesis는 프로그래밍과 함께 시작한다. 그리고 프로그래밍은 interpreter와 함께 시작한다.

Program

프로그램은 하나의 데이터 구조로 볼 수 있다. 여기서 프로그램은 top, down, left, right로 구성된 사각형의 구조이다.

# the rectangle in our figure, [T,D,L,R]
rectangle = [1,3,1,4]

 

Input

입력 또한 데이터 구조로 볼 수 있다. 여기서 입력은 (row, col)로 정의되는 좌표이다.

# the mushrooms and grass coordinates in out figure
shroom1 = (0, 4)
shroom2 = (4, 1)
grass1 = (1, 1)
grass2 = (3, 3)

 

Output

결과 또한 데이터 구조로 볼 수 있다. 우리의 경우 안쪽(inside) 혹은 바깥쪽(outside)로 간단히 되어 있다.

inside = True
outside = False

 

Interpreter

interpreter는 입력을 출력으로 바꿔주는 역할을 한다. 우리의 경우 프로그램과 입력을 넣으면 인터프리터는 좌표가 직사각형 안쪽인지 바깥쪽인지 반환하여 입력에 대한 프로그램을 해석하고 실행한다.

def interpret(program, inputt):
    T, D, L, R = program
    i, j = inputt
    return i >= T and i <= D and j >= L and j <= R

 

Putting it together

우리의 사각형이 풀을 포함하고 버섯을 포함하지 않고 있는가?

assert interpret(rectangle, grass1) == inside
assert interpret(rectangle, grass2) == inside
assert interpret(rectangle, shroom1) == outside
assert interpret(rectangle, shroom2) == outside
print ("working as intended !")

---

Programming

프로그래머는 어떻게 프로그램을 작성할까?

작업을 구체화하는 데에는 많은 방식이 있다. 개발자에게 앱 제작을 요청할 수 있는 다양한 방법을 상상해 봐라. 비슷하게 프로그램이 올바른지 확인하는 방법도 여러가지가 있다. 똑같이 앱을 테스트한다고 가정하고 다양한 방법을 상상해 봐라. 그러나 사람의 실제 작업을 컴퓨터가 이해하는 경우는 거의 존재하지 않는다.

 

task as specifications

specification 혹은 spec은 사람과 컴퓨터가 모두 작업에 동의하도록 작업을 명시하는 방법이다. program synthesis에서 보통 spec은 input-output 쌍으로 주어진다. input-output은 굉장히 희귀하게도 사람과 컴퓨터가 둘 다 이해할 수 있는 방식이다.

 

아래는 여러 가지의 spec들이다.

spec = [(grass1, inside), (grass2, inside), (shroom1, outside), (shroom2, outside)]
shroom3 = (2,2)
grass3 = (4,3)
shroom4 = (5,4)
spec2 = [(shroom3, outside), (grass3, inside), (shroom4, outside)]

 

Correctness

spec이 주어지면, 컴퓨터는 프로그램이 “올바른 작업”을 수행했는지를 자동으로 판단할 수 있다. 이는 프로그램에 입력을 넣었을 때, 지정된 출력이 제대로 생성되는지를 확인함으로써 가능하다.

def is_correct(program, spec):
    for inputt, output in spec:
        if interpret(program, inputt) != output:
            return False
    return True

 

Programming problem

프로그래밍 문제는 사람이 작성한 specification과 프로그램으로 이루어지며, 컴퓨터는 프로그램이 specification을 만족하는지 자동으로 확인하는 역할을 한다.

프로그래밍 문제들을 program synthesis 전에 손으로 직접 풀어보는 것은 매우 중요하다. 이것은 기계가 동일한 작업을 수행할 수 있도록 하는 synthesizer를 설계하는 데 중요한 통찰을 제공한다.

# let's try to make a rectangle that satisfy spec2
rect2 = [1,3,1,4]
print (is_correct(rectangle, spec2)) # didn't work
rect3 = [3,4,1,3]
print (is_correct(rect3, spec2)) # worked okay

 

the asymmetry

때로는 specification을 손으로 작성하는 것이 프로그램에 작성하는 것보다쉽다. 이 비대칭성만으로도 program synthesis를 시도할 충분한 동기가 된다.

---

A typical synthesis problem

프로그래머는 더 쉬운 방식인 specification을 작성하고 더 어려운 프로그래밍을 synthesizer에게 넘긴다.

synthesis 문제는 이러한 spec을 프로그램으로 전환하는 것을 의미한다. 이는 meaning matrix를 활용하여 공식화 된다.

---

Characterize the synthesis problem with meaning matrix M

무한한 계산 자원이 있다고 가정하고, meaning matrix M을 구성해보자. 이때 M은 M = spec × prog 형태의 행렬이다.
이 행렬에서 각 행은 하나의 specification,각 열은 하나의 program을 나타내며, 각 원소 M[spec, prog]는 해당 프로그램이 명세를 만족하는지 여부, 즉 is_correct(prog, spec) 값을 나타낸다. 이 관계는 인터프리터를 통해 정의된다.

 

그러면 M은 synthesis 문제를 완전히 표현할 수 있다. 만약 M이 만들어질 수 있다고 가정하면 synthesis 문제는 간단한 문제로 변한다: M[spec, prog] = True를 만족하는지를 찾으면 된다.

 

using M to quantify difficulty

synthesis 문제가 얼마나 어려울까? 간단하게 계산해보자: 사각형의 개수는 6^4, 입력은 6^2, 출력은 2, 그러면 (6^2) * 2의 입력-출력 쌍이 존재한다. 10개의 풀과 버섯이 있다고 가정하면 ((6^2) * 2)^10의 specs가 존재한다.

결론적으로 ((6^2)*2)^10 x 6^4 = 4.852e+21의 행렬이 필요하다.

 

synthesis는 행렬 M을 작성하는 것으로 시작한다. M은 여기서 무서운 조합 괴물이라고 생각하자. M의 구조를 이해하고 근사하는 것이 이 괴물과 싸우는 방법이다.

---

A typical synthesis algorithm

일반적인 program synthesis 알고리즘은 행렬 M을 전체를 계산하지 않고 특정한 행, M[spec, :]에서 일부 원소만 샘플링한다. 이런 알고리즘은 두 가지 구성 요소로 이루어져 있다:

• program writer : 주어진 작업을 기반으로 다양한 프로그램 제안
• program checker : interpreter와 specification을 활용해 프로그램이 올바른지 확인

program writer

writer는 spec을 바탕으로 프로그램 생성을 목표로 한다. 원시 프로그램들은 대부분 간단한 랜덤 프로그램을 사용했다.

def random_writer(spec):
    # ignores the spec, W=6 globally
    T, D, L, R = random.randint(0,W), random.randint(0,W), random.randint(0,W), random.randint(0,W)
    return [T, D, L, R]

 

program checker

우리가 사용한 is_correct 함수가 checker이다. 주로 interpreter를 사용한다.

def program_cheker(prog, spec):
    return is_correct(prog, spec)

 

putting it together

writer가 포기하기 전에 제안할 수 있는 프로그램의 개수를 budget이라 부르기로 하자.

# a synthesizer that returns both a working program (if it finds any)
# and the number of samples it took to find it
def get_synthesizer(writer, checker, budget):
    def synthesizer(spec):
        prog = writer(spec)
        for i in range(budget):
            prog = writer(spec)
            if checker(prog, spec):
                return (i, prog)
        return None
    return synthesizer

 

한 번 시도해보자!

synthesizer = get_synthesizer(random_writer, program_cheker, 1000)
spec1 = [( (0,4), outside), ( (4,1), outside), ( (1,1), inside), ( (3,3), inside)]
n_tries, prog = synthesizer(spec1)
print (n_tries, prog) 
# results vary, but I got 146 [1, 3, 0, 3], 31 [1, 3, 0, 5], 56 [1, 3, 1, 6], etc

 

아마 심각하게 비효율적일 것이다.

 

making the writer better

spec을 무시하는 것 대신에 직사각형의 매개변수로 잔디(안쪽)의 좌표만 사용하는 것이 좋을 수도 있다.

def better_writer(spec):
    # get the coordinates of spec that are inside
    inside_coords = [coord for coord,bool in spec if bool]
    if inside_coords == []:
        # if there are no inside coordinates, default to a random
        return random_writer(spec)
    # otherwise, use the inside coords to suggest parameters of the rectangle
    row_coords = [coord[0] for coord in inside_coords]
    col_coords = [coord[1] for coord in inside_coords]
    T, D = random.choice(row_coords), random.choice(row_coords)
    L, R = random.choice(col_coords), random.choice(col_coords)
    return [T, D, L, R]

 

이것도 역시 해보자!

synthesizer2 = get_synthesizer(better_writer, program_cheker, 1000)
n_tries, prog = synthesizer2(spec1)
print (n_tries, prog)
# results vary, but I got 1 [1, 3, 1, 3], 23 [1, 3, 1, 3], 5 [1, 3, 1, 3], etc

 

아마 처음 버전보다는 훨신 나을 것이다.

 

https://evanthebouncy.github.io/program-synthesis-minimal/typical-synthesis-problem/

a typical synthesis problem