for textmining

유한문법 기반의 문장 생성

|

이번 글에서는 유한문법(finite grammar)을 바탕으로 문장을 생성하는 모델에 대해 살펴보도록 하겠습니다. 이 글은 ‘밑바닥부터 시작하는 데이터 과학(조엘 그루스 지음, 인사이트 펴냄)’을 정리하였음을 먼저 밝힙니다. 지금은 저 스스로 정리할 목적으로 올리는 포스트인데요, 한국어를 기반으로 한 실험 결과를 조만간 업데이트하겠습니다.

아이디어

문법에 기반해 말이 되는 문장을 생성해보자는 게 핵심 아이디어입니다.

예컨대 영어에서 문장(S)은 명사구(NP)와 동사구(VP)로 분석할 수 있습니다. 동사구(VP)에는 동사 하나(V)로만 구성될 수 있지만 동사(V)와 명사구(NP)가 결합해 있는 구로도 구성될 수 있습니다. 그런데 이 명사구(NP)에는 다시 명사(N) 하나로만 구성될 수도 있고, 형용사(A)+명사구(NP)+전치사(P)+형용사(A)+명사(N)로 이뤄진 구일 수도 있습니다.

다시 말해 유한한 수의 문법규칙만으로도 무한한 개수의 문장을 만들어낼 수 있다는 이야기입니다.

grammar = {
    "_S" : ["_NP _VP"],
    "_NP" : ["_N",
             "_A _NP _P _A _N"],
    "_VP" : ["_V",
             "_V _NP"],
    "_N" : ["data science", "Python", "regression"],
    "_A" : ["big", "linear", "logistic"],
    "_P" : ["about", "near"],
    "_V" : ["learns", "trains", "tests", "is"]
}

코드

그렇다면 유한문법 규칙을 활용해 어떻게 문장을 생성할 수 있을까요? 문장(S)로 시작한다고 했을 때 모든 항목이 종결어(teminal)가 될 때까지 유한문법규칙에 맞는 구나 단어를 재귀적으로 선택함으로써 만들어낼 수 있습니다. 그 코드는 다음과 같습니다.

import random

def is_terminal(token):
    return token[0] != "_"

def expand(grammar, tokens):
    for i, token in enumerate(tokens):

        # ignore terminals
        if is_terminal(token): continue

        # choose a replacement at random
        replacement = random.choice(grammar[token])

        if is_terminal(replacement):
            tokens[i] = replacement
        else:
            tokens = tokens[:i] + replacement.split() + tokens[(i+1):]
        return expand(grammar, tokens)

    # if we get here we had all terminals and are done
    return tokens

def generate_sentence(grammar):
    return expand(grammar, ["_S"])

Comments