学習者言語の分析（応用）2（第4回）

  • 8 依存木の違い
    • 8.1 依存木の「同型」
    • 8.2 依存木の「距離」
      • 8.2.1 編集距離（レーベンシュタイン距離）
      • 8.2.2 依存木の編集距離
    • 演習問題16

8 依存木の違い¶

8.1 依存木の「同型」¶

  • 以下の2つの文は単語は異なりますが、依存関係から見ると同じです。
  1. Meteorologists can use these algorithms.
  2. Students can use all rooms.
In [1]:
import sys
sys.path.append("../")
from common import utils
In [2]:
# 1. Meteorologists can use these algorithms.
text = "Meteorologists can use these algorithms"
V1,E1 = utils.text_to_set_dep(text)
g = utils.set_to_graph(V1,E1)
g
Out[2]:
No description has been provided for this image
In [3]:
# 2. Students can use all rooms.
text = "Students can use all rooms"
V2,E2 = utils.text_to_set_dep(text)
g = utils.set_to_graph(V2,E2)
g
Out[3]:
No description has been provided for this image
  • これらの文の「同型」判定は以下のように行うことができます。
In [4]:
E1 == E2
Out[4]:
True
  • 以下の文は2の疑問文なので2と「同型」にはなりません。
  1. Can students use all rooms
In [5]:
# 2. All the students can use all rooms.
text = "can students use computer rooms"
V3,E3 = utils.text_to_set_dep(text)
g = utils.set_to_graph(V3,E3)
g
Out[5]:
No description has been provided for this image
In [6]:
E2 == E3
Out[6]:
False
  • 以下の文は2に単語が加えられた文なので、2と「同型」にはなりません。
  1. All the students use computer rooms
In [7]:
# 2. All the students can use all rooms.
text = "All the students use all rooms"
V4,E4 = utils.text_to_set_dep(text)
g = utils.set_to_graph(V4,E4)
g
Out[7]:
No description has been provided for this image
In [8]:
E2 == E4
Out[8]:
False

以下の文は1および2とグラフの形状は同じですが、ノードの名称が異なるので1および2と「同型」にはなりません。

  1. She always likes cheese burgers
In [9]:
# 5. She always likes cheese burgers
text = "She always likes cheese burgers"
V5,E5 = utils.text_to_set_dep(text)
g = utils.set_to_graph(V5,E5)
g
Out[9]:
No description has been provided for this image
In [10]:
E2 == E5
Out[10]:
False

8.2 依存木の「距離」¶

  • 上述のような違いが「どの程度違っているか」を示すために編集距離を用いて数値で表現してみます。
  • 以下の1から4の文の依存木において、1と2の違いおよび1と3の違いに比べると1と4の違いは大きいと言えます。
  1. I bought a car.
  2. I bought a new car.
  3. John bought a car yesterday.
  4. Yesterday John gave Mary a car.

8.2.1 編集距離（レーベンシュタイン距離）¶

  • 文字列Aと文字列Bとの類似度を示す指標で、文字列Aの文字を、置換、削除、挿入して文字列Bにする場合の最小の処理数を示しています。
    • 「とまと」を「とまれ」にするには「と」を「れ」に置換するので編集距離は1。
    • 「まくら」を「まっくら」にするには「っ」を挿入するので編集距離は1。
    • 「とばっちり」を「ばっちり」にするには「と」を削除するので編集距離は1。
  • このようにして2つの文字列の「距離」を測ることができます。
  • 編集距離が小さければ2つの文字列は似ていて、大きいと似ていないということになります。
  • しかしながら、文字列が長くなると距離も長くなるので、算出した距離を長い方の文字列で割って標準化した値を用いる場合があります。
  • 以下のように算出します。
In [11]:
a = "とばっちり"
b = "ばっちり"

utils.edit_dist(a,b)/max(len(a),len(b))
Out[11]:
0.2

8.2.2 依存木の編集距離¶

  • これまで、依存木の辺集合は以下のように表していました。

[['ROOT_1', 'nsubj_0'], ['ROOT_1', 'dobj_2']]

  • これは、"nsubj -> det"などの関係が2つ以上出現する可能性があるため出現順序を付与して重複を避けるためでした。
  • しかしながら、これをこのまま利用すると、上の1と2の依存木の違いはかなり大きいものになってしまいます。
In [12]:
text = "I bought a car"
V1,E1 = utils.text_to_set_dep(text)
In [13]:
text = "I bought a new car"
V2,E2 = utils.text_to_set_dep(text)
In [14]:
utils.edit_dist(E1,E2)
Out[14]:
3
  • 単語をひとつ加えただけなのに編集距離は3になります。
  • これの問題を解消するために、この辺集合を集合ではなくリストにします（つまり、重複要素を許す）。
In [15]:
text = "I bought a car"
V3,E3 = utils.text_to_set_dep_un(text)
E3
Out[15]:
[['ROOT', 'nsubj'], ['ROOT', 'dobj'], ['dobj', 'det']]
In [16]:
text = "I bought a new car"
V4,E4 = utils.text_to_set_dep_un(text)
E4
Out[16]:
[['ROOT', 'nsubj'], ['ROOT', 'dobj'], ['dobj', 'det'], ['dobj', 'amod']]
In [17]:
utils.edit_dist(E3,E4)
Out[17]:
1
  • このようにすると、編集距離は1になります。

演習問題16¶

任意の英語の文の依存木と「同型」の文、編集距離が1の文、編集距離が2の文を../DATA01/sentences.txtから見つけ てみましょう。