データナード

機械学習と自然言語処理についての備忘録 (旧ナード戦隊データマン)

グラフ編集距離でmonolingual sentence alignmentをする

monolingual sentence alignmentとは、同一または類似の意味を持つ文ペアを単一言語コーパスから生成するものです。

概要

モノリンガルコーパスに文がn個ある場合、このn個の文からすべての文ペアの組み合わせをチェックする場合、計算量が O(n^2) になります。膨大な文がある場合、この計算量を削減する何らかの方法が必要です。

今回試すのは、spacyとnetworkxでグラフを作り、そのグラフが似ている文ペアを抽出します。以下のグラフを検討します:

  • lemmaによるグラフ。
  • posによるグラフ。
  • dependency typeによるグラフ。

各々のグラフペアの近似編集距離を使い、グラフサイズの和でノーマライズします。この値が一定以下であるような文ペアを取得します。 実際には、これも O(n^2) であるため、係り受けパスの共通性によって候補を絞り込みます。そして、複数の方法でフィルタリングを適用した上で、最終的にこのグラフ類似度を使います。

コード

いくつかのフィルタリングを施したあと、以下を実行します。

import networkx as nx
import spacy
nlp = spacy.load("ja_ginza")

data_dep = {}

with open("example_pairs_len_bow_w2v_ed_rmdot.txt") as f:
    for line in f:
        line = line.strip().split("\t")
        if len(line) > 2:
            s1 = line[0]
            s2 = line[1]
            if s1 not in data_dep:
                data_dep[s1] = nlp(s1)
            if s2 not in data_dep:
                data_dep[s2] = nlp(s2)

これは、各々の文をspacyのginzaモデルでパースしたものです。次に、3つの種類のグラフをそれぞれ文ごとに求めます。

graph_lemma = {}
graph_pos = {}
graph_dep = {}

for sent, toks in data_dep.items():
    edges_lemma = []
    edges_pos = []
    edges_dep = []
    for tok in toks:
        edges_lemma.append((tok.lemma_, toks[tok.head.i].lemma_))
        edges_pos.append((tok.pos_, toks[tok.head.i].pos_))
        edges_dep.append((tok.dep_, toks[tok.head.i].dep_))
    graph_lemma[sent] = nx.DiGraph()
    graph_lemma[sent].add_edges_from(edges_lemma)
    graph_pos[sent] = nx.DiGraph()
    graph_pos[sent].add_edges_from(edges_pos)
    graph_dep[sent] = nx.DiGraph()
    graph_dep[sent].add_edges_from(edges_dep)

このグラフに対し、文ペアごとのグラフ編集距離をもとめてスコアをだし、スコアが一定以下(グラフ編集距離なので、少ないほうが良い)の文ペアのみを残します。

threshold = 0.3
with open("example_pairs_len_bow_w2v_ed_rmdot.txt") as f, open("example_pairs_len_bow_w2v_ed_rmdot_gsim.txt", "w") as fw:
    for line in f:
        line_ = line.strip()[:]
        line = line.strip().split("\t")
        if len(line) > 2:
            s1 = line[0]
            s2 = line[1]
            if s1 in graph_lemma and s2 in graph_lemma \
            and s1 in graph_pos and s2 in graph_pos \
            and s1 in graph_dep and s2 in graph_dep:
                sim1 = nx.optimize_graph_edit_distance(graph_lemma[s1], graph_lemma[s2])
                sim2 = nx.optimize_graph_edit_distance(graph_pos[s1], graph_pos[s2])
                sim3 = nx.optimize_graph_edit_distance(graph_dep[s1], graph_dep[s2])
                sim1 = next(sim1)/(graph_lemma[s1].size()+graph_lemma[s2].size())
                sim2 = next(sim2)/(graph_pos[s1].size()+graph_pos[s2].size())
                sim3 = next(sim3)/(graph_dep[s1].size()+graph_dep[s2].size())
                if sim1 < threshold and sim2 < threshold and sim3 < threshold:
                    fw.write("{}\t{}\t{}\t{}\n".format(line_, sim1, sim2, sim3))

考察

候補抽出の段階で削減されるデータの量は、precisionとrecallのトレードオフの問題を含んでいると考えられます。削減量が多ければより一致している文を見つけるのでprecisionが上がりますが、カバーできる範囲が減るのでrecallが減ります。削減後のデータ量は別の問題も含んでおり、それは各々のフィルタリング手法の計算量の問題です。

計算量を削減するために、(obj, ROOT)パスが一致しているグループ内だけで各々のフィルタリング手法を使いたいのですが、obj, ROOTが一致しているものだけだとrecallが減ります。それを許容するかどうかを判断する必要があります。

一方で、今回はグラフの類似性を、グラフ編集距離を正規化した値が少ないほど類似性が高い、として考えしましたが、この方法によって生成されたペアは構造的な意味で似ていると考えられます。今回の目的は、アラインメントしたデータで何かを訓練することではなく、アラインメントしたデータからサンプリングした文ペアに対してアノテーションすることによって、「2つの文の共通性を検出する」というモデルに対するテストデータを作成することなので、recallよりはprecisionのほうが優先されるかもしれません。

まだmonolingual sentence alignmentの手法を調べていないので、ここで試したことはおそらく未熟なものなので、タスクに対する調査も行っていきたいところです。

ただし、今回のアラインメントの結果の良し悪しは、データにも依存する問題であるため、コーパス中に似た文が少ない場合は、手法に関わらず、見かけ上悪く見える可能性があります。複数の手法を比較する場合、同一データに対する性能を同一の方法で評価する必要があります。

参考

  1. Similarity Measures — NetworkX 2.4 documentation
  2. http://ssli.ee.washington.edu/tial/projects/simplification/alignment.pdf
  3. https://www.jstage.jst.go.jp/article/jnlp/25/2/25_223/_pdf/-char/ja

追記: 2020-02-13 14:23

グラフ編集距離の正規化でテキトーな方法を使ってしまったが、以下のほうがいいかもしれない。

正規化された編集距離 = グラフ1と2の編集距離 / max(グラフ1のノード数とエッジの和, グラフ2のノード数とエッジの和)