語の並びを考慮した意味類似度手法の提案

DEIM Forum 2015 A2-6
語の並びを考慮した意味類似度手法の提案
小中 史人†
三浦 孝夫†
† 法政大学 理工学部創生科学科 184–8584 東京都小金井市梶野町 3-7-2
E-mail: †[email protected], ††[email protected]
あらまし
本研究では語義・語順を捉えるためにいくつかの距離概念を導入し，コロケーションの考慮が可能な，文
の意味類似性（STS）に基づく類似度手法を提案する．そのために，距離概念に意味類似度を適用する．これにより，
意味距離を定義する．語義・語順・コロケーション（連語）の考慮を確認するために，30 個の名詞のペアを用いて実
験を行う．
キーワード
テキストマイニング，情報検索，STS
1. 前 書 き
インターネット上に点在する文書には，様々な種類が存在し
それぞれが特徴的な構造・構成を取ることが多い．その例の
であっても，計算機による処理としてはこれまで有効な解法が
知られておらず，学習コーパスなどを前提とした機械学習的な
処理や，文法構造や辞書などの既存知識の活用が提案されてい
る程度である [3]．
１つとして Blog や Twitter といった Social Network Service
文字列とは平坦な文字の並びであり，これを何らかの構造 (語
（SNS）がある．SNS の特徴として，短文が多いこと，出現単語
句や形態素，あるいはその構造）に変換することで背後の意味
の重複が少ないこと，文法の無視，
「www」や「BBA」，
「(笑)」
を決定する．しかし，これをどの粒度で実施するかは自明では
といった特殊な語用が挙げられる．
なく計算量も大きい．不可欠な背景知識も，学習コーパス，辞
大量の文書データに対して情報検索を行うための手法は広く
研究されている．特に，現在の文書検索における主流なモデル
書，意味ネットワークなど多様にわたり，経験的な方法に頼ら
ざるを得ない．
として Bag-Of-Words 法に代表されるベクトル空間モデルがあ
文の意味類似性 (Semantic Texutual Similarity, STS) によっ
る．このモデルは単語の意味情報をベクトルによって表現して
て，文書検索に新たな機能を導入することができる．実際，文
いる．これは「似た文脈に出現する語は意味が近い」という仮
の意味を直接扱うことから，語やその分布により文脈を間接的
説である Distributional Semantic Model(DSM) に基づく [1]．
に推定するのではなく，構成する語句の意味や関連性，あるい
しかし，SNS 文書は一般に短文であり，語の並びが重要な働
は文法を考慮することで，文全体の意味を明らかにすることが
きをする．また出現する語が低頻度であることから，このアプ
期待される．
ローチは SNS に必ずしも適切に作用しない．DSM では語同
STS を考える際には コロケーション (Collocation) も考慮
士の関係を正確に解釈することもできないといった特徴を持
する必要がある．コロケーションは熟語または連語を示す慣用
つ．例えば，”I hope to marry her.”と”I hope to divorce her.”
句である（注 1）. 例えば "His lecture came across well." と
という文章では DSM に従うと，反意語の関係にある”marry”
"His lecture resonated well." は語数が異なるが，come
と”divorce”を類似語として捉えるため，ベクトル間の類似度は
across と resonate は類似した表現であるため，同じ意味を示
常に高くなる．
している．このため，文の意味類似性を判別する上でコロケー
本稿では，文の意味類似性を論じるため，いくつかの距離
概念を導入し，これに基づく類似性を定義する．具体的には，
ションの考慮が必要である．文の意味は長さや語数に依存し
ない．
ユークリッド距離とレーベンシュタイン距離に語の意味類似度
文法は自然言語を特徴づける要素であり，文の意味は文法
を適用することで，コロケーション（連語），語順，語義の考
による解釈によって決定される．実際，"His lecture came
慮が可能な文の類似度を定義する．2 章では意味的類似性につ
across well." と"His across well came lecture." では，
いて，3 章で具体的な提案手法を述べる．4 章で実験・考察を
後者が文法規則を無視しており少なくとも同じ意味を有してい
行い，5 章で結論とする．
るとは言えない．
2. 意味的類似性
2. 1 文の意味類似性
2. 2 WordNet
WordNet は英語の意味辞書である．本来，機械可読な辞書と
して開発され，1985 年より，プリンストン大学の認知科学研究所
自然言語で使用される語は多様な意図で使用されており，ど
の意味を表すかを特定することは自明ではない．語義曖昧性解
消 (Word Sense Disambiguation, WSD) は文章中で文脈に整
合する語の意味を特定する機能をいう [2]. 人間にとっては自明
（注 1）：熟語とは，複数の語からなる慣用的な表現であり，
「目玉を食う」等のよ
うに（「目玉」や「食う」とは別の）独立した固有の意味を有する．連語は，複
数の単語からなる生起しやすいまとまった形の表現であり，”somethink like
that” のように，習慣として生じやすい表記をいう．
によって心理学者である同大学教授の George A. Miller の主導
のもとで運営されている (http://wordnet.princeton.edu/).
3. 意味類似文の距離
2005 年現在，WordNet のデータベースには約 115,000 の syn-
本章では，文章の意味類似性を論じるため，いくつかの類似
set に分類された約 15 万語を収録している．全体では 203,000
性概念を導入する．各類似度は 0∼1 の値を持ち，1 に近いほど
の単語と意味の組み合わせがある．WordNet では名詞，動詞，
類似，0 に近いほど相違する．
形容詞，副詞を文法上の扱いが異なることから，区別して収蔵
している．
synset は同義の単語あるいはコロケーションをグループにま
とめたものである．ほとんどの synset は他の synset の上位語，
下位語，反意語といった意味的な関係が番号によって示されて
いる (Wikipedia)．
WordNet において名詞と動詞は is-a の関係で定義される階
層構造にまとめられている．図 1 はその一部を示している．
提案手法を述べるために，以下の 2 つの例文を用いる．
（S1 ）”In former times, serfs were a class of people
who had to work on a particular person’s land and
could not leave without that person’s permission.”
（S2 ）”A slave is someone who is the property of
another person and has to work for that person.”
3. 1 拡張ユークリッド類似度
ベクトルで表された文書の距離を定義する．語数 (見出し語
数) n の文書を，n 次元ベクトル空間上で表す．２つの文書ベク
トル p = (p1 , p2 , · · · , pn )，q = (q1 , q2 , · · · , qn ) は，通常 TF
や TF*IDF などの値を要素とする．p，q に対するユークリッ
ド距離（距離関数 d）は，以下の式で定義される．
v
u n
u∑
d(p, q) = t (qi − pi )2
i=1
一方，本稿では文章間の類似度を定義する．任意の語 wi ,
w̄i に対して，語類似度 Sim(wi , w̄i ) が定義されているとする．
図 1 WordNet の階層構造
S1 ,S2 が共に k 個の語から構成され，第 i 番目の語をそれぞれ
wi , w̄i とすると，S1 , S2 の拡張ユークリッド類似度を次のよう
WordNet は語同士の類似性判定にも用いられる．類似性の
に定義する．
√∑
k
判定のため Path が提案されている [4]．語 W1 から語 W2 の類
似度を P ath(W1 , W2 ) と定義する．P ath(W1 , W2 ) は
P ath(W1 , W2 ) =
1
path length(W1 , W2 )
と表される．path length(W1 , W2 ) は語 W1 から語 W2 に最
SimEU (Ŝ1 , Ŝ2 ) =
i=1
Sim(wi , w̄i )2
k
なお，この類似度は [0.0..1.0] の実数値を取り，距離とは異な
り 1 に近いほど類似する．
短経路で至るまでの経路長である．図 1 における synset 間を
3. 2 語の対応付け
結ぶ結ぶ経路において，例えば図 1 で teacher と boy の類似度は，
拡張ユークリッド類似性を用いて任意の文の類似度を算出す
teacher−educator−professional−adult−person−male−boy よ
るには，語数が等しい必要がある．このため，n-gram(n=1,..,4)
り経路長は 6 であるため，その Path 値は 1/6 となる．
を用いて文の形式的な語数を統一する．語数 s の文 S を n-gram
2. 3 関 連 研 究
に分割すると，s ないし s/4 個の n-gram を生成することがで
椿ら [1] は文の構成最適化と分解による単語表現学習モデル
きる．文 S1 , S2 が表現可能な n-gram 数のうち同数となる値
と，カーネル和を用いた文の意味的類似度計算手法を提案する．
を算出する (アルゴリズム 1)．各文を n-gram を用いて表現可
この研究は単語ベクトル空間と文の構成性に基づいた意味的ア
能な語数を算出する．即ち S1 , S2 を同じ数 k 個 の n-gram に
プローチの基礎的なモデルである．
分割し，拡張ユークリッド類似度を算出する．k を求めるアル
Li ら [5] は語順に着目し，これと語の意味類似度を組み合わ
ゴリズムでは，分割可能な値の範囲を求め，共通値それぞれで
せる手法を提案する．これにより，出現位置に関係なく文同士
（複数の）から最良の分割を選択する．共通する表現可能な語
で出現する共通語（類似語含む）を特徴として抽出する．
数が存在しない場合は，2 文間の類似度は 0 とする．
Islam ら [6] は単語間の文字列に着目し，その類似度と単語の
意味類似度を組み合わせる手法を提案する．これにより，辞書
アルゴリズム 1 Calculate k = I1 ∩ I2
に依存した手法では不可能なスペルミスの考慮が可能となる．
(1) S1 > 0 ∧ S2 > 0
Feng ら [7] は文をエンハンスした上で意味類似度を算出し，
(2) k > 0 ∨ k = ∅
これと語順類似度を組み合わせる手法を提案する．これにより，
(3) I1 = ⌈ S41 ⌉ ∼ ⌈ S11 ⌉
短文の短さに起因する特徴不足を解消する．これらの手法では
(4) I2 = ⌈ S42 ⌉ ∼ ⌈ S12 ⌉
コロケーションを考慮していない．
| ∅) k = (I1 ∩ I2 )
(5) if(I1 ∩ I2 =
3. 3 拡張レーベンシュタイン類似度
(6) else error
本稿では語の出現順，類似語の重複といった出現語の特徴を
n-gram が辞書に登録されているコロケーションと合致し
考慮するために，レーベンシュタイン距離を語に対して拡張す
た場合は，その n-gram を 1 語として解釈する．S1 では in
る．長さ m，n の 2 つの文字列 x，y に対して，レーベンシュ
time,work on が WordNet に合致する．そのため，S1 は以下
タイン距離は以下の式で定義される．
のように書き換えられる．
（S1 ）”In times former, serfs were a class of people
who had to work on a particular person’s land and
could not leave without that person’s permission.”
Mi,0 = i(0 <
=i<
= m), M0,j = j(0 <
=j<
= n)



 Mi−1,j−1 + δ(xi , yj )
Mi,j = min
Mi,j−1 + 1


 M
+1
i−1,j
2 つの n-gram w,w̄ の意味類似度は，Path を用いて次のよ
うに定義する．
ここで δ(xi , yj ) は以下の式で定義される．
{
δ(xi , yj ) =
Sim(w, w̄) = max P ath(ai , bj )
i,j
n-gram w,w̄ それぞれに生じる語 ai ,bi の類似度 P ath(ai , bi )
0
(xi = yj )
1
(xi =
| yj )
拡張レーベンシュタイン類似度を次のように定義する．
を求め、類似性が最大になるものを採用する．この類似度は
[0.0..1.0] の実数値を取る．距離とは異なり 1 に近いほど類似
する．
2 つの文は語数が異なるため，n-gram を用いて表現可能な
Mi,0 = i(0 <
=i<
= m), M0,j = j(0 <
=j<
= n)



 Mi−1,j−1 + (1 − P ath(wi , w̄j ))
Mi,j = min
語数をそれぞれ算出する．各文の語数はそれぞれ S1 = 24，
S2 = 18 であるので，
24
24
I1 =
∼
= 6 ∼ 24
4
1
18
18
I2 =
∼
= 6 ∼ 18
4
1
k = {6 ∼ 24} ∩ {6 ∼ 18} = 6 ∼ 18
ここで k = 6 の場合を考える．この場合，2 つの文を n-gram
を用いて 6 語に統一する．n-gram を用いて k 語で文を表現可
能であることが保証されている．k = 6 より n = ⌈ 24
⌉=4で
6
Mi,j−1 + (1 − P ath(wi , w̄j ))


 M
i−1,j + (1 − P ath(wi , w̄j ))
SimLS (S1 , S2 ) = 1 −
拡張レーベンシュタイン類似度は再帰的に計算することで出現
語を網羅する．なお，この類似度は [0.0..1.0] の実数値を取り，
距離とは異なり 1 に近いほど類似する．
例題で，名詞について拡張レーベンシュタイン類似度を適用
する．表 1 において，5 行 5 列目の people と person の交わる
マスの値は，



 2.5 + (1 − P ath(people, person))
あるため，最長 4-gram を用いた S1 を表現する組み合わせを
全て得る．S2 にも同様の処理を行う．全ての組み合わせの中か
Mpeople,person = min
ら，類似性が最大になるものを採用する．この処理を全ての k
の値に適用し，最大の類似性を示す値を拡張ユークリッド類似
度の値とする．S1′ が S1 の，S2′ が S2 の統一結果である．w[i]
は文中における第 i 語であることを表す．n-gram 内の語は順序
情報を持つ．
（S1′ ）”w[1]：In times former serfs were, w[2]：a class
Mm,n
max(m, n)
2.73 + (1 − P ath(people, person))


 3.33 + (1 − P ath(people, person))
より，3.4 となる．次に 6 行 5 列目の person と person の交差
するマスを考える．その値は



 3.33 + (1 − P ath(person, person))
Mperson,person = min
of people, w[3]：who had to work on, w[4]：a parti-
3.4 + (1 − P ath(person, person))


 3.4 + (1 − P ath(person, person))
cular person’s land, w[5]：and could not leave, w[6]：
より，3.33 となる．これを Mpermission,person に達するまで繰
without that person’s permission”
り返す．その結果，SimLSn = 1 −
（S2′ ）”w[1]：A
slave is, w[2]：someone who is, w[3]：
the property of, w[4]：another person and, w[5]：has
to work, w[6]：for that person”
4. 実
5.17
8
= 0.35 となる．
験
実験環境と評価方法を述べ，実験により得られた結果を示す．
4. 1 実 験 環 境
各文の第 1 語 w1 , w̄1 では P ath(serf, slave) の類似度 0.25
が最大となるため，Sim(w1 , w̄1 ) = 0.25 となる．同様にして，
他の語の類似度を算出する．その後，拡張ユークリッド類似度
を算出すると 0.25 となる．
本実験では，テストコーパスとして, Rubenstein [8] による，
65 個の名詞のペアのうち，30 個を用いる．これらのペアは
Li [5] によって人手によるスコアづけが行われ，スコアが均一
になるように選択された．この 30 個の名詞のペアは数多くの
論文で用いられている [5] [6] [7] [9] [10] [11]．
4. 3 考
slave property person person
察
表 2,3 に基づき，結果の考察を行う．表 3 より，ペア co-
0
1
2
3
4
time
1
0.89
1.78
2.7
3.62
ast&shore は人手によるスコアでは 6 位，ペア coast&forest は
serf
2
1.64
1.82
2.58
3.38
22 位となっているが，提案手法ではそれぞれ 19 位，7 位となっ
class
3
2.5
2.5
2.73
3.49
ている．coast および shore, coast および forest の定義文を表
people
4
3.35
3.33
3.4
3.63
person
5
3.85
4.24
3.33
3.33
land
6
4.65
4.52
4.25
4.25
person
7
5.15
5.43
4.25
4.25
permission 8
6.08
6.03
5.17
5.17
表1
4 に示す．
coast および shore の定義文は，
（文中の）語数が大きく異な
る．語数統一後の定義文を表 5 に示す．shore より，コロケー
ションの考慮が確認できる．実際に Path を用いて類似度を算出
すると，P ath(coast, shore) = 0.5, P ath(area, land) = 0.08,
拡張レーベンシュタイン類似度
P ath(sea, ship) = 0.08 となる．第 1,3,5,6,7 語は類似度 0 で
本実験では各名詞を the Collins Cobuild dictionary （注 2） の
第一用法に置き換え，それを対象に，TreeTagger
（注 3）
により，
ある．
coast および forest の定義文はほぼ同じ語数を有している．語
数統一後の定義文を表 5 に示す．実際に Path を用いて類似度を
予め形態素処理したものを用いる．
本実験では拡張ユークリッド類似度への重みを 0.5，名詞に
対する拡張レーベンシュタイン類似度への重みを 0.3，動詞に
対する拡張レーベンシュタイン類似度への重みを 0.2 とする．
算出すると，P ath(area, area) = 1, P ath(land, tree) = 0.17
となる．第 1,4 語の類似度は 0 である．
area と land, sea と ship よりも，land と tree は類似して
いると Path は判断した．このため，coast&shore は下位に，
重みは予め予備実験より得るものを用いる．
Sim(S1 , S2 ) = 0.5 × SimEU (Ŝ1 , Ŝ2 )
+0.3 × SimLSn (S1 , S2 )
+0.2 × SimLSv (S1 , S2 )
coast&forest は上位にランクづけされた．
5. 結
論
本稿では，語義・語順を捉えるためにユークリッド距離とレー
ベンシュタイン距離をそれぞれ拡張し，コロケーションの考慮
評価は Li [5] の人手によるスコアをランキング化し，それに
対する適合率で行う．比較手法には Islam [6],Feng [7] の結果を
用いる．
が可能な，STS に基づく類似度手法を提案した．これにより，
文の意味類似度を定義した．実験では名詞のペアの第一用法定
義文に対して意味類似度を算出し，ランク付けを行った．文の
4. 2 実 験 結 果
意味は語数に依存しないと予想し，語数に依存する手法よりも
表 2 に実験によって得られた適合率を，表 3 に実際の実験結
果を示す．Islam [6] の手法には上位 1-10 件で優位性を示し，か
つ平均においても 0.08 の優位性を示しているが，Feng [7] の手
法には平均において僅かに 0.01 劣っていることがわかる．
件数
提案手法 Islam et al.
Feng et al.
1
1
0
1
5
0.8
0.6
0.8
10
0.6
0.8
0.6
15
0.6
0.8
0.67
20
0.7
0.85
0.75
25
0.88
0.96
0.88
30
1
1
1
平均
0.8
0.72
0.81
表2
適 合
率
表 3 を見ると，比較手法では正解で 21 位以下のペアが上位
10 件に含まれていない．提案手法では正解で 21 位以下のペア
coast&forest が上位 10 件に含まれている．
（注 2）：http://www.collinsdictionary.com/dictionary/
english-cobuild-learners
（注 3）：http://www.cis.uni-muenchen.de/˜schmid/tools/TreeTagger/
概ね良い結果を得ることができた．だが，正解では下位のペア
が提案手法では上位に，上位のペアが下位にランクづけされる
ケースがあった．結果として，提案手法は平均適合率 0.8 を得
た．また，上位 1-10 件において提案手法は Islam [6] より優位
性を示し，平均適合率では 0.08 の優位性を得た．
文
献
[1] 椿真史, Kevin Duh, 新保仁, 松本裕治. 文の意味構成に伴う高
次元空間の最適化と単語表現学習. 言語処理学会第 20 回年次大
会 発表論文集, pp.1015-1018, Mar 2014.
[2] Navigli, R. (2009). Word sense disambiguation: A survey.
ACM Computing Surveys (CSUR), 41(2), 10.
[3] 奥村学：自然言語処理の基礎, コロナ社, 2010
[4] Pedersen, T., Patwardhan, S., and Michelizzi, J. (2004,
May). WordNet:: Similarity: measuring the relatedness of
concepts. In Demonstration Papers at HLT-NAACL 2004
(pp. 38-41). Association for Computational Linguistics.
[5] Li, Y., McLean, D., Bandar, Z. A., O’shea, J. D., and
Crockett, K. (2006). Sentence similarity based on semantic
nets and corpus statistics. Knowledge and Data Engineering, IEEE Transactions on, 18(8), 1138-1150.
[6] Islam, A., and Inkpen, D. (2008). Semantic text similarity using corpus-based word similarity and string similarity. ACM Transactions on Knowledge Discovery from Data
(TKDD), 2(2), 10.
[7] Feng, J., Zhou, Y. M., and Martin, T. (2008). Sentence similarity based on relevance. In Proceedings of IPMU (Vol.
8, p. 833).
順位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
正解
midday&noon
cock&rooster
cemetery&graveyard
gem&jewel
forest&woodland
coast&shore
implement&tool
boy&lad
automobile&car
cushion&pillow
grin&smile
serf&slave
cord&string
autograph&signature
journey&voyage
magician&wizard
furnace&stove
hill&mound
oracle&sage
hill&woodland
glass&tumbler
coast&forest
magician&oracle
boy&rooster
forest&graveyard
boy&sage
cord&smile
asylum&fruit
bird&woodland
autograph&shore
提案手法
midday&noon
cock&rooster
serf&slave
forest&woodland
gem&jewel
cemetery&graveyard
coast&forest
boy&rooster
journey&voyage
automobile&car
hill&woodland
boy&lad
magician&oracle
grin&smile
magician&wizard
boy&sage
autograph&signature
forest&graveyard
coast&shore
cord&string
implement&tool
autograph&shore
glass&tumbler
asylum&fruit
furnace&stove
cushion&pillow
oracle&sage
bird&woodland
hill&mound
cord&smile
Islam et al.
cock&rooster
midday&noon
gem&jewel
boy&lad
automobile&car
implement&tool
cemetery&graveyard
cord&string
coast&shore
serf&slave
journey&voyage
magician&wizard
forest&graveyard
grin&smile
furnace&stove
cushion&pillow
hill&woodland
glass&tumbler
coast&forest
forest&woodland
magician&oracle
autograph&signature
boy&rooster
boy&sage
hill&mound
bird&woodland
autograph&shore
oracle&sage
asylum&fruit
cord&smile
Feng et al.
midday&noon
cock&rooster
cemetery&graveyard
gem&jewel
boy&lad
cord&string
serf&slave
automobile&car
grin&smile
boy&rooster
boy&sage
magician&wizard
journey&voyage
asylum&fruit
magician&oracle
coast&shore
autograph&signature
cushion&pillow
furnace&stove
autograph&shore
glass&tumbler
forest&woodland
implement&tool
forest&graveyard
hill&woodland
oracle&sage
hill&mound
bird&woodland
cord&smile
coast&forest
表3 実験結果
coast
shore
coast
forest
coast および shore
The coast is an area of land that is next to the sea.
The shores or the shore of a sea, lake, or wide river is the land along the edge of it.
Someone who is on shore is on the land rather than on a ship.
coast および forest
The coast is an area of land that is next to the sea.
A forest is a large area where trees grow close together.
表4 定
語
coast
shore
coast
forest
1
the
1
the,shore,or,the
2
coast
2
shore,of,a,sea
1
the
1
a,forest,is
3
is
3
lake,or,wide,river
義
文
定義文
coast および shore
4
5
an,area
of,land
4
5
is,the,land,along the,edge,of,it
coast および forest
2
coast,is,an,area
2
a,large,area
表 5 統一後の定義文
[8] Rubenstein, H., and Goodenough, J. B. (1965). Contextual correlates of synonymy. Communications of the ACM,
8(10), 627-633.
[9] Ho, C., Murad, M. A. A., Kadir, R. A., and Doraisamy, S. C.
(2010, August). Word sense disambiguation-based sentence
similarity. In Proceedings of the 23rd International Conference on Computational Linguistics: Posters (pp. 418-426).
Association for Computational Linguistics.
[10] O’Shea, J., Bandar, Z., Crockett, K., and McLean, D.
(2008). A comparative study of two short text semantic
similarity measures. In Agent and Multi-Agent Systems:
Technologies and Applications (pp. 172-181). Springer Berlin Heidelberg.
[11] O’Shea, J., Bandar, Z., Crockett, K., and McLean, D.
(2008). Pilot short text semantic similarity benchmark data
set: Full listing and description. Computing.
6
that,is
6
someone,who,is on,shore
3
of,land,that,is
3
where,trees
7
next,to
7
is on,the,land,rather
8
the,sea
8
than,on,a,ship
4
next,to,the,sea
4
grow,close,together