CCGパーサーを利用して知識グラフのためのトリプルを生成する

はじめに

自然言語処理において英文から意味を理解し、構造化された知識を得たいときに便利なのが知識グラフだ。知識グラフはさまざまな用途で使われるが、主に各ノード(人物や物など)の関係性をエッジを用いて表現したグラフ構造のデータであると考えることができる。今回この記事で簡単に紹介するのは、CCG（Combinatory Categorial Grammar）という文法を利用したパーサーを利用して、英文から知識グラフを構築するためのトリプルを自動的に取り出す方法だ。

CCG（Combinatory Categorial Grammar）とは？

CCGは自然言語の文を構造的に解析する文法理論のひとつで、1970年代にMark Steedmanによって提案・発展された。「単語や句にカテゴリ（型）を割り当て、それらを関数のように適用しながら文全体の意味を作り出す」という特徴を持つ。

カテゴリ（型）とは？

• 基本型: 名詞は NP（名詞句）、名詞単体は N、文は S といった具合に、単語やフレーズにカテゴリを割り当てる。
• 関数型: 例えば動詞 love は、「主語（NP）を左から受け取って、目的語（NP）を右から受け取ると文（S）になる」という関数として扱う。
  つまり love のカテゴリは (S\NP)/NP。
  • / は「右側に引数を取る」
  • \ は「左側に引数を取る」

例文：「Alice loves Bob」をCCGで解析してみる

単語	カテゴリ	意味（簡易表記）
Alice	NP	alice
loves	(S\NP)/NP	love
Bob	NP	bob

解析の流れ：

1. loves と Bob を右側から適用
   (S\NP)/NP に NP を適用して、S\NP ができる。
   意味的には (love bob)。

2. Alice と (loves Bob) を左側から適用
   NP に S\NP を適用して S（文）になる。
   意味的には ((love bob) alice)。

これがCCGの「関数適用」による文の構築である。関数型カテゴリのおかげで、単語をまるでプログラムの関数のように組み合わせて文の意味を段階的に作り上げられるのが特徴である。

知識グラフがトリプルで構成される理由

知識グラフは「(主語, 関係, 目的語)」のトリプルで知識を表現する。これは自然言語での「○○は□□の～である」という関係をシンプルにモデル化しているからだ。

例えば、

Light_Yagami is son of Soichiro_Yagami

という文は、

(Light_Yagami, is_son_of, Soichiro_Yagami)

というトリプルで表現できる。

トリプルの形ならグラフ構造としてデータベース化しやすく、検索や推論が効率的にできるため、知識を扱う上で非常に便利なのだ。自然言語の意味の骨格を取り出して単純化し、機械で扱いやすい形に落とし込むために「トリプル」という構造が使われることもよくある。

CCGを利用して英文からトリプルを生成する方法

CCG（Combinatory Categorial Grammar）は、英文の構造を解析するだけでなく、その文の意味を表す「意味式」を同時に生成できる文法理論だ。解析の最初の段階で、各単語に対応するカテゴリ（型）と意味をLexicon（辞書）から割り当てる。例えば、名詞は「NP」、動詞は「(S\NP)/NP」といった形でカテゴリ付けされ、意味的な役割も定義される。CCGパーサーの面倒なところとして、このLexiconを我々が事前知識として用意しなければならないことが挙げられるが、世の中にはすでに優れたCCGパーサーが多く存在しているため（例えば、Mark Steedmanや彼の研究グループが公開しているものや、広く使われる「C&C parser」など）、中にはLexiconをすでに内包しているものもある。

CCGの関数適用ルールを使い、隣接する単語や句を組み合わせていくことで、文全体の意味式を段階的に構築する。たとえば「A loves B」という文では、"loves"が関数で、"A"や"B"がその引数となり、最終的に「(loves B) A」という意味式が得られる。この意味式は論理式に似ていて、文中の主語や目的語、述語の関係を表現している。

この意味式をプログラムで解析し、主語・述語・目的語の関係を抜き出すことで、知識グラフの基本単位であるトリプル（主語、述語、目的語）に変換できる。たとえば、「Light_Yagami is the son of Soichiro_Yagami」という文からは、(Light_Yagami, is_son_of, Soichiro_Yagami)というトリプルが生成される。こうして、CCGを使うことで、ただの英文を構造化された意味情報に変換し、知識グラフ構築の基盤を作ることができる。

実装例

では実際に簡単な実装例を見ていこう。この実装では「Light_Yagami is the son of Soichiro_Yagami」という文から(Light_Yagami, is_son_of, Soichiro_Yagami)というトリプルを作成するコードの例を見せる。この実装では読者の理解を深めるため、外部のCCGパーサーを一切使わずスクラッチからパーサーを実装している。そのため、私の実力不足で、少々不恰好な実装となっている。また、特定の文のみに対象を絞っているので、少々汎用性にも欠けるかもしれないがそこには目を瞑ってほしい。

1. CCGノードの定義

CCGの各ワードを表すクラス。各ワードは型であるカテゴリと意味式である意味表現を持つ。また、パースが木構造で行われるため、最小単位である単語以外の句にはその句を構成する単語等が子ノードとしてぶら下がる。

class CCGNode:
    def __init__(self, category, semantics, children=None):
        self.category = category      # CCGカテゴリ（例：NP, S\NP）
        self.semantics = semantics   # 意味表現
        self.children = children or []  # 子ノード

    def __str__(self):
        if self.children:
            return f"Category: {self.category}\nSemantic: {self.semantics}\n\tChildren: {' '.join(str(child) for child in self.children)}"
        else:
            return f"{self.category}:{self.semantics}"

２. 辞書（Lexicon）の定義

上述の通り、Lexiconは自前で用意する必要がある。今回用意したものは今回のタスク専用のLexiconであるため、汎用性は高くない。一般的には一つの単語が複数のカテゴリを持つ可能性もある。また、今回は、面倒な概念を省くため、意味式をただの一階述語論理における項や述語のように表現しているが、本来は「λx.λy.(love(y,x))」のようなラムダ式的な表現である。

lexicon = {
    # 固有名詞（NP）
    'Light_Yagami': [('NP', 'light_yagami')],
    'Soichiro_Yagami': [('NP', 'soichiro_yagami')],

    # be動詞（(S\NP)/NP）
    'is': [('(S\\NP)/NP', 'is')],

    # 限定詞（NP/N）
    'the': [('NP/N', 'the')],

    # 名詞（N）
    'son': [('N', 'son')],

    # 前置詞（(NP\NP)/NP）
    'of': [('(NP\\NP)/NP', 'of')],
}

３. CCG組み合わせルールの実装

CCG（Combinatory Categorial Grammar）では、単語や句に割り当てられたカテゴリ（型）同士を結合して文を構成していく際に、「組み合わせルール（combinatory rules）」が重要な役割を果たす。特に代表的なのが 前向き適用（forward application） と 後ろ向き適用（backward application） だ。

前向き適用（Forward Application）

これは、左側の要素が「関数」の役割を持ち、右側の要素がその「引数」として適用されるケース。記号で書くと：

X/Y + Y → X

ここで、X/Y は「Y型の引数を右側から取ってX型になる関数」を意味し、右側の Y と結合して結果的に X になる。
例：(S\NP)/NP （他動詞）が NP （目的語）を受け取ると、S\NP（動詞句）になる。

後ろ向き適用（Backward Application）

これは、右側の要素が「関数」の役割を持ち、左側の要素がその引数となるケース。記号で書くと：

Y + X\Y → X

ここで、X\Y は「Y型の引数を左側から取ってX型になる関数」を意味し、左側の Y と結合して結果的に X になる。
例：NP（主語）が S\NP（動詞句）と結合して、S（文）になる。

CCGの解析で自然な意味構造を得るには、このような組み合わせルールを正しく実装し、単語のカテゴリが適切に割り当てられている必要がある。組み合わせルールはパーサーの核となる部分だが、自前で用意しなければならないことが多い。ただし、既存のCCGパーサーやライブラリでは、これらのルールや大規模なカテゴリ辞書（Lexicon）が既に用意されている場合も多い。そのため、自分で一から実装する場合はルールの設計とLexicon整備が大変だが、既存ツールを活用することで効率的に解析できる。今回の場合は、わかりやすさを重視するため、自分でルールを設計した。

def combine(left, right):
    # 前向き適用: (S\NP)/NP + NP → S\NP
    if left.category == "(S\\NP)/NP" and right.category == "NP":
        new_cat = "S\\NP"
        new_sem = f"({left.semantics} {right.semantics})"
        return CCGNode(new_cat, new_sem, [left, right])

    # 前向き適用: NP/N + N → NP
    if left.category == "NP/N" and right.category == "N":
        new_cat = "NP"
        new_sem = f"({left.semantics} {right.semantics})"
        return CCGNode(new_cat, new_sem, [left, right])

    # 前向き適用: (NP\NP)/NP + NP → NP\NP
    if left.category == "(NP\\NP)/NP" and right.category == "NP":
        new_cat = "NP\\NP"
        new_sem = f"({left.semantics} {right.semantics})"
        return CCGNode(new_cat, new_sem, [left, right])

    # 後向き適用: NP + NP\NP → NP (修飾語句の適用)
    if left.category == "NP" and right.category == "NP\\NP":
        new_cat = "NP"
        new_sem = f"({left.semantics} {right.semantics})"
        return CCGNode(new_cat, new_sem, [left, right])

    # 後向き適用: NP + S\NP → S
    if left.category == "NP" and right.category == "S\\NP":
        new_cat = "S"
        new_sem = f"({right.semantics} {left.semantics})"
        return CCGNode(new_cat, new_sem, [left, right])

    return None

4. パーサーの実装

上記の組み合わせルールを用いて実際に英文をパースする関数。このパーサーでは貪欲探索（グリーディー戦略）による隣接ペア結合というアプローチをとっている。

このパーサーのアルゴリズムは、隣接するノードのペアをすべて試して、定義した組み合わせルールに合致するペアを探すというシンプルなものだ。複数の候補がある場合はスコアリングで最適と思われる組み合わせを選び、そのペアを結合してノード数を減らすことで文全体の構造を徐々に組み上げていく。これを最終的にノードが一つになるまで繰り返す手法である。

このスコアリング戦略は比較的柔軟にしてある。限定詞と名詞の結合を最優先にし、修飾語句や動詞句の結合も加味することで、言語の基本構造を反映した自然な解析を促した。一方で、全ての組み合わせを網羅的に試すわけではなく貪欲に進めるため計算コストは抑えられているが、複雑な文では誤解析のリスクもある。本来ならより高度な実装として、スコアリングルールの追加やより高度な探索アルゴリズム（例えば動的計画法やビームサーチ）等も考慮すべきだったが、CCGパーサー開発の入り口としてはまあいいかと考えてこの実装にした。

def parse_sentence(sentence, lexicon):
    tokens = sentence.split()

    nodes = []
    for word in tokens:
        if word in lexicon:
            cat, sem = lexicon[word][0]
            nodes.append(CCGNode(cat, sem))
        else:
            nodes.append(CCGNode('NP', word.lower()))

    while len(nodes) > 1:
        combinations = []
        for i in range(len(nodes) - 1):
            new_node = combine(nodes[i], nodes[i+1])
            if new_node:
                combinations.append((i, new_node))

        if not combinations:
            break

        best_combination = None
        best_score = -1

        for i, new_node in combinations:
            score = 0
            if nodes[i].category == 'NP/N' and nodes[i+1].category == 'N':
                score += 40
            elif nodes[i].category == '(NP\\NP)/NP' and nodes[i+1].category == 'NP':
                score += 35
            elif nodes[i].category == 'NP' and nodes[i+1].category == 'NP\\NP':
                score += 30
            elif nodes[i].category == '(S\\NP)/NP' and nodes[i+1].category == 'NP':
                score += 25
            if new_node.category != 'S':
                score += 10
            score += (len(nodes) - i)

            if score > best_score:
                best_score = score
                best_combination = (i, new_node)

        if best_combination:
            i, new_node = best_combination
            nodes = nodes[:i] + [new_node] + nodes[i+2:]

    return nodes[0] if nodes else None

だいたいこんな感じでパースがされていく。

Step 1:
      Combining: NP + (S\NP)/NP
      No combination possible
      Combining: (S\NP)/NP + NP/N
      No combination possible
      Combining: NP/N + N
      Determiner + Noun: NP/N + N → NP
      Combining: N + (NP\NP)/NP
      No combination possible
      Combining: (NP\NP)/NP + NP
      Preposition + NP: (NP\NP)/NP + NP → NP\NP
  Best combination: 2 and 3
    Result: NP = (the son)
  Current nodes:
    0: NP = light_yagami
    1: (S\NP)/NP = is
    2: NP = (the son)
    3: (NP\NP)/NP = of
    4: NP = soichiro_yagami

Step 2:
      Combining: NP + (S\NP)/NP
      No combination possible
      Combining: (S\NP)/NP + NP
      Forward application: (S\NP)/NP + NP → S\NP
      Combining: NP + (NP\NP)/NP
      No combination possible
      Combining: (NP\NP)/NP + NP
      Preposition + NP: (NP\NP)/NP + NP → NP\NP
  Best combination: 3 and 4
    Result: NP\NP = (of soichiro_yagami)
  Current nodes:
    0: NP = light_yagami
    1: (S\NP)/NP = is
    2: NP = (the son)
    3: NP\NP = (of soichiro_yagami)

Step 3:
      Combining: NP + (S\NP)/NP
      No combination possible
      Combining: (S\NP)/NP + NP
      Forward application: (S\NP)/NP + NP → S\NP
      Combining: NP + NP\NP
      Modifier application: NP + NP\NP → NP
  Best combination: 2 and 3
    Result: NP = ((the son) (of soichiro_yagami))
  Current nodes:
    0: NP = light_yagami
    1: (S\NP)/NP = is
    2: NP = ((the son) (of soichiro_yagami))

Step 4:
      Combining: NP + (S\NP)/NP
      No combination possible
      Combining: (S\NP)/NP + NP
      Forward application: (S\NP)/NP + NP → S\NP
  Best combination: 1 and 2
    Result: S\NP = (is ((the son) (of soichiro_yagami)))
  Current nodes:
    0: NP = light_yagami
    1: S\NP = (is ((the son) (of soichiro_yagami)))

Step 5:
      Combining: NP + S\NP
      Backward application: NP + S\NP → S
  Best combination: 0 and 1
    Result: S = ((is ((the son) (of soichiro_yagami))) light_yagami)

5. 意味表現からトリプルを抽出する実装

このアルゴリズムは、CCGパーサーが生成した意味表現（セマンティック式）を解析し、知識グラフのトリプルに変換する処理を行っている。まず、parse_semantic_expr関数は意味表現の文字列を受け取り、括弧の構造をもとにネストしたリスト形式のツリー構造に変換する。これにより複雑な意味式を扱いやすいデータ構造に整形している。

次に、transform_relations関数では、このツリー構造を再帰的に探索し、特定のパターンに一致する意味の関係を抽出する。具体的には、「is」という述語が含まれ、その目的語部分が「the son of ～」という構造を持つ場合に、「is_son_of」という関係のトリプル (主語, is_son_of, 対象) に変換している。これにより自然言語の意味を、知識グラフで扱いやすい形式に構造化する。

最後に、extract_kg_triples関数はこれらの処理をまとめて実行し、入力された意味表現から知識グラフのトリプルを抽出して返す。全体として、このアルゴリズムは単純なパターンマッチングを使いながらも、意味構造を木構造で正しく解析し、自然言語の意味を機械的に知識グラフに落とし込む基盤を提供している。

ぶっちゃけ、意味式からトリプルへの変換規則は色々あるし、自前でいくらでも定義し用意することができる。今回はあえてこのような実装にしたが、意味式に対応した正しいトリプルが得られるならルールや実装は各々に任される。

import re

def parse_semantic_expr(expr):
    """カッコ付きの意味表現をネストしたリストに変換"""
    tokens = re.findall(r'\(|\)|[^\s()]+', expr)
    stack = [[]]
    for tok in tokens:
        if tok == '(':
            stack.append([])
        elif tok == ')':
            last = stack.pop()
            stack[-1].append(last)
        else:
            stack[-1].append(tok)
    return stack[0]

def transform_relations(tree):
    """構造木から述語形式に変換"""
    if isinstance(tree, list):
        if len(tree) == 1 and isinstance(tree[0], list):
            return transform_relations(tree[0])

        if len(tree) == 2 and isinstance(tree[0], list):
            inner_list = tree[0]
            subject = tree[1]

            if (isinstance(inner_list, list) and len(inner_list) == 2 and 
                inner_list[0] == 'is'):

                pred_obj = inner_list[1]

                if (isinstance(pred_obj, list) and len(pred_obj) == 2 and
                    isinstance(pred_obj[0], list) and pred_obj[0][0] == 'the' and pred_obj[0][1] == 'son' and
                    isinstance(pred_obj[1], list) and pred_obj[1][0] == 'of'):

                    obj = pred_obj[1][1]
                    return ('is_son_of', subject, obj)

    return tree

def extract_kg_triples(semantic_expression):
    tree = parse_semantic_expr(semantic_expression)
    result = transform_relations(tree)

    triples = []
    if isinstance(result, tuple) and result[0] == 'is_son_of':
        subject, object_entity = result[1], result[2]
        triples.append((subject, 'is_son_of', object_entity))

    return triples

実行例

コード：

sentence = "Light_Yagami is the son of Soichiro_Yagami"
result = parse_sentence(sentence, lexicon, debug=True)

print(f"\nFinal parse result:\n{result.category} = {result.semantics}")

triples = extract_kg_triples(result.semantics, debug=True)
print("\nExtracted triples:")
for t in triples:
    print(t)

実行結果：

Final parse result:
S = ((is ((the son) (of soichiro_yagami))) light_yagami)

Extracted triples:
('light_yagami', 'is_son_of', 'soichiro_yagami')

まとめ

前回のGNNのシリーズ記事で、もう疲れたからしばらく休むなどと言っていたが、三連休中にCCGと知識グラフに関する昔の記憶がよみがえり、どうしても気になってしまい。結局この記事を書くこととなった。私は元の専門が「自然言語処理」ということもありCCGは義務教育扱いで、大学在学中に叩き込まれたが、しばらく使っていなかった。そのため、もしこの記事にCCGに関する不備や誤った知識があれば、私がさまざまなことを忘却してしまっているのだなと優しい眼差しでスルーしてほしい。

この記事ではあくまで知識グラフ構築の基礎であるトリプルをいかに非構造データである自然言語の文章から自動的に得ることができるか論じるために、知識グラフやCCGに関する詳細な説明は省いてしまった。本来ならCCGはもっと奥の深い内容であり、それについて解説を深く行わない私は、CCGを教えてくれた私の大学の教授からすると、破門されてもおかしくない程の罪を犯している可能性がある。一方で、CCGはほとんどの人間からすると「何それ？美味しいの？」といった程度のものであり、その詳細な定義や意義について語るよりも、この記事のように具体的で面白そうな応用方法を伝えた方が今後のCCG界隈のためになるのではないかと私は考えてこの記事を書いた。この記事がCCG界への何らかの一助担っていれば幸いである。

さてお約束ではあるが、次の記事を私がいつ書くかは神のみぞ知る。また時間のある時に、モチベーションの上がる内容を見つけたら自然と記事を書いていそうではあるが、とりあえず今は、明日から始まるお盆休みを満喫する準備が重要である。