論 文
言語表現のベクトル空間モデルにおける最適な計量距離
持橋 大地†,††

菊井玄一郎†

北研二†,†††

Learning an Optimal Distance Metric in the Linguistic Vector Space
Daichi MOCHIHASHI†,†† , Genichiro KIKUI† , and Kenji KITA†,†††

あらまし 自然言語処理の手法にはコサイン距離，すなわち単純なユークリッド距離に依存しているものが多いが，この距離は素性間の相関を考慮しないこと，また素性に恣意的な重みづけを必要とするという問題を持っている．本論文ではこれに代わり，訓練データより導かれる最適な計量距離を提案し，二つの問題を同時に解決する．この計量は訓練データのクラスタ構造の歪みを最小化する二次最適化問題の解として導くことができる．
提案する計量距離の効果を，同義文検索，文書検索，および機械学習用一般ベクトルデータのクラスタリングタ
スクによって確認し，ユークリッド距離に対し常に精度の改善がみられた．特にクラスタ化の強い同義文検索タ
スクにおいて精度の改善が大きく，ベースラインと比較して 11 点平均精度で 33% の向上があった．
キーワード 距離計量，コサイン距離，tf.idf，素性空間，カーネル法

1. ま え が きかのベクトルとみなし，大量のコーパスに対し，高速自然言語処理において，文，文書，パラグラフな比較は再帰的なカーネル関数を用いてカーネル法の枠な検索や比較を行うものである．近年，(a) の構造的などの言語表現の間の意味的な距離を計算することは内で見通しよく扱えるようになっているが [3], [4]，こ基礎的で重要な技術となっている．たとえば，情報

こでは (b) の非構造的な比較に着目する．これは，上検索は検索語あるいは特定文書と意味的な距離が近に述べたような大量のコーパスに対する自然言語処理

い文書を文書集合の中から検索するタスクであるし，では，構造的比較に必要な構文解析や依存構造解析が

TextTiling [1] やその後継であるスペクトル法などのテキスト分割法 [2] においては，いずれもパラグラ

計算量的に非現実的であり，近似的であっても高速な

フ間のコサイン距離がその基礎として使われている．

おいても再帰の葉においては依然，非構造的比較 (イ

質問応答 (QA) や言い換え，用例ベース機械翻訳の場

グザクトマッチやベクトルのマッチ) が行われるため，面でも，文間距離を計算することが基礎的な要素技術

それらの基礎をなすと考えられるからである．

比較が求められるということの他に，構造的な比較にしかしながら，それらの場面で使われる非構造的比となっている．
現在，このような言語表現の比較には大きく分けて較は多く，はじめに述べたコサイン (＝ユークリッド)(a) 構造的な方法 と (b) 非構造的な方法 が存在している．(a) の構造的な方法は何らかの構文解析または依距離に依存しており，素性間の相関および各素性の重存構造解析を用い，精密な比較を行うものであり，一代わり，訓練データから得られる最適な計量距離を導方 (b) の非構造的な比較は言語表現を実数空間の何ら入し，その効果を実験的に検証する．この計量は訓練†データとして与えるクラスタ構造をもとに，二次最適
ATR 音声言語コミュニケーション研究所，京都
ATR Spoken Language Translation Research Laboratories
Hikaridai 2-2-2, Keihanna science city, Kyoto 619-0288††

奈良先端科学技術大学院大学 情報科学研究科
Graduate School of Information Science, NAIST†††

み付けの点で問題を残している．本論文ではこれに化問題の解として導出される．
本論文は以下のように構成される．2 章で，自然言語処理において伝統的に使われてきたユークリッド距

Takayama-cho 8916-5, Ikoma, Nara 630-0192

離とその問題点について述べる．3 章では，この問題

徳島大学高度情報化基盤研究センター

が機械学習における，データに基づく計量の導出問題

Center for Advanced Information Technology, Tokushima
University Minamijosanjima 2-1, Tokushima 770-8506と捉えられることを示し，近年の関連研究について述

電子情報通信学会論文誌 D–II Vol. Jxx–D–II No. xx pp. 1–10

xxxx 年 xx 月

1

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–D–II No. xx

べる．4 章で提案手法を説明し，5 章でその効果を同中にもいくつかのバリエーションがあるが，その選択

義文検索，文書検索および一般データのクラスタリン

に対する一般的な基準は存在していない．

グタスクを用いて検証する．6 章と 7 章で議論，課題
および結論を述べる．

3. 関 連 研 究
上述したような素性の相関および素性の重みづけは，

2. ユークリッド距離とその問題

機械学習においてはデータ空間において適切な計量を自然言語処理において非構造的比較を行う場合，言求める問題と考えることができ，近年特に注目されて語表現はしばしば，素性 i の生起回数 xi (i = 1. . .n)いる問題である．[9] は本論文と同様の問題意識に基づ

nを要素とするベクトル 
x ∈ R として表現される．素いており，「似た」点のペアの集合を訓練データとして，性が単純に単語であるとき，これは単語の袋詰めとい本論文と似た計量行列を学習している．[10] および [11]う意味で “Bag of words” とよばれているが [5]，一般は，適切な計量をそれぞれ，スペクトル法によるクラには素性には他の可能性も考えられるため，以下ではスタリングと SVM における比較データの問題設定の統一して素性と表記する．

中で求めるものである．この意味で，本論文は [9] のこうしたベクトル u, v 間の距離としては，単純な内積またはユークリッド距離（注 1）d(u, v )2 = (u − v )T (u − v )=(ui − vi )2

よび提案手法の優位性については 6. 章で述べる．

(1)
(2)

i

(T は転置を表す) が事前の素性重みづけとともに
これまで多くの自然言語処理の手法で用いられている [5], [6]．しかし，この距離関数は 2 つの大きな問題を持っている．

(i) 素性間の相関が考慮されていない．
(ii) 素性の最適な重みづけが決定できない．
言語データにおいては，コロケーションや構文など
を通じて一般に素性間には強い相関が存在するため，(i) は特に大きな問題である．カーネル法を用いた場合(たとえば [7])，高次の多項式カーネルなど特定のカーネルを用いることで複数の素性の組み合わせを考慮することができるが，現在このカーネル法は自然言語処理においては分類問題として多く使用されており，連続的な順序付けを必要とする情報検索や QA などを置換できる方法は提案されていない．

(ii) も実際的に重要な問題である．各素性はしばしば，単語あるいはその組み合わせであり，意味のある比較のためには内容語には強い重みを，機能語には弱い重みを，といった意味的な重みづけが必要となる．
しかし，現在このために行われている tf.idf [8] などの重みは発見的なものであり，距離に関して何らかの最適化基準に依っているものではない．また，tf.idf の（注 1）：情報検索ではベクトルの長さを |
u| = |
v | = 1 と正規化することが一般に行われるが，このとき (u −v )T (u −v) = |u|2 +|v |2 −2
u ·v∝− cos(u, v ) であり，ユークリッド距離による比較はコサイン距離によるものと一致する．[5]2

自然な拡張とみなすことができる．[9] との類似点，おまた，確率的生成モデルを基にデータ間の内積を与えるカーネルである Fisher kernel [12] も原理的には同じ意味を持ったものであることに注意したい．Fisher
kernel の定式化においては，データの分布から期待値として導かれるフィッシャー情報量行列の逆行列が，確率モデル空間における計量を与える．ただし，この計算は計算量がきわめて大きいために，実際には単位行列で近似されることが多い．
情報検索の分野では，[13], [14] がクエリに対する適合フィードバックの立場から R-SVD (RiemannianSVD) を提案している．しかし，これは大域的な検索
距離空間の改良を目指したものではなく，本論文で用いたようなクラスタ構造は用いられていない．

4. 提 案 手 法
上のような距離関数に関する問題について，われわ
れはデータ中に存在するクラスタ構造に注目する．ここでいうクラスタ構造とは，個々のデータを着目する
観点に従って分類したものであり，実際には同一サイトの文書，同義文のクラスタ，振られたクラスラベルなどが該当する．訓練データは一般に完全に独立ではなく，データは言語の再帰的構造に従って構造化されていることも多いため，このような構造は多くの言語
データに関して見られると考えられる．
各クラスタ内のデータを類似したものと見なせば，理想的なベクトル空間において，各データベクトルは集中して分布しているはずである．この性質に基づき，訓練データのクラスタ構造を用いて，最小二乗の意味
で最適な距離行列を導出することができる．これにつ論文／言語表現のベクトル空間モデルにおける最適な計量距離

いて以下に述べる．

4. 1 データ分布と計量ベクトル u, v 間の二乗 (L2 -) 距離を，式 (1) に代わり，計量行列 M = [mkl ] を用いて
dM (u, v )2 = (u − v )T M (u − v )
=


k

High
covariancexn

Lowvariance

x2

x2

(3)

mkl (uk − vk )(ul − vl ) (4)

l

xn

High
variancex1x1(a) Original space(b) Mapped space

図 1 素性空間におけるクラスタ構造．
Fig. 1 Cluster geometry of feature space.

として求めることを考える．これは一般に画像等の分類問題において用いられるマハラノビス距離であり，

M = I (単位行列) の特別な場合として式 (1) を含む．
式 (4) から，計量行列 M によって任意に各素性の重できれば，その M は素性に対して適切な重みを与え，み，および素性間の相関が表現できることがわかる．

意味で最適な M について考える．

M は対称行列であり，このとき，式 (3) は式 (5) のように書き換えることができるから，dM (u, v )2 = (M 1/2 (u − v ))T (M 1/2 (u − v )) (5)素性間の相関を適切に捉えるはずである．以下，この4. 2 最適な計量行列の導出
各データ (たとえば，文や文書) 
x を Rn 上のベク
トルとし，その全体が N 個のクラスタ X1 . . . XN に分けられていると仮定する．すなわち，ベクトルの次

この距離は，ベクトル 
u − v を M 1/2 によって新しい

元数は n, クラスタ数は N である．各クラスタ Xi

空間へ写像し，その間のユークリッド距離を考えるこに対して，その重心 (セントロイド) を ci とおくと，ととも等価である [9]．なお，このマハラノビス距離は一般的なものであり，パターン認識における用法に限

ci = 1/|Xi |の要素数)．




x∈Xi


x である (|X| はクラスタ X 中られないことに注意したい．パターン認識においては

このとき，前節の議論から，各クラスタ内でデータ

一般に，複数の固定されたクラスタが正規分布をもつ間の距離を最小にする計量を求める．すなわち，各クラと仮定し，各クラスタ毎にその共分散行列の逆行列を

スタ Xi に含まれるデータ x ∈ Xi とセントロイド ci

M とすることで各クラスタへの距離を定義し，分類との距離 dM (x, ci ) の総和を，全クラスタ X1 . . . XNを行うが [15]，ここで求めるものは事前に決まったクにわたり最小にするような M を求めればよい．これ

ラスへの識別問題ではなく，多数のクラスタより導かは以下の二次最小化問題として定式化することがでれ，一般的に用いることのできる大域的な距離計量だ

きる．

からである．[9]〜[11] も同じ問題意識を共有している．
したがって，ここでは訓練データ全体にわたる最適化が必要となる．本章最初の議論より，クラスタ内のデータは理想的な空間内では集中して分布しているべきと考えられるが，実際にはデータおよびその同義ク
ラスタはユークリッド空間において図 1(a) のように楕円体型に分布しており，ある次元には高い分散を，別の次元には低い分散を持っている．また，クラスタの向きは一般にユークリッド距離における基底ベクト
ルには沿っていない．言語データは非常に高次元であるため，この傾向は特に顕著であると考えられる．
このとき，図 1(b) のように，M 1/2 で写像された空最小化問題:

M = argmin
M= argminNdM (xj , ci )2

i=1 xj ∈Xi

N



M

(xj − ci )T M (xj − ci ) (6)i=1 xj ∈Xi

規格化条件 : |M | = 1.

(7)

規格化条件は，M = 0 となる縮退した解をもたないための条件である．(| · | は行列式を表す．) 右辺の1 は任意の定数であり，これを c とすれば c2 M が新
しい解となる．

間において，高い分散を抑え，低い分散を拡大するこ

この最適化問題はデータベースの分野で提案されたとでこうしたクラスタの歪みを最小化し，同義クラス

MindReader [16] の考えを複数クラスタに拡張したもタを真球に近づけるような計量 M を見出だすことがのであり，以下の一意な解を持つ．
3

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–D–II No. xx[定理] 条件式 (7) の下で (6) 式の最小化問題を満たす

め，同義文検索，文書検索，および機械学習用ベクト

行列 M はルデータのクラスタリングタスクを用いて実験を行った．提案手法は汎用性を持つため，後者のような非言

M = |A|1/n A−1(8)である．ここで，A = [akl ] は以下で定義される行列．

akl =語データにも適用することができる．
実験の基本的な手順は以下の通りである．まず，訓練データからクラスタ構造を用いて計量行列 M を計N(xjl − cil )(xjk − cik ).

(9)

i=1 xj ∈Xi

算する．次に検索タスクにおいては，テストデータ中の各ベクトルに対し残りのベクトルとの距離を計算し，昇順にソートする．そのリスト中で元のベクトルと同[証明] 付録 1 を参照．2

クラスタに含まれるものを正解データとし，再現率–(8) 式の |A|1/n は定数であるから，これは上記最適化問題の解は，各クラスタの分散-共分散行列の総和

適合率および R-精度を求める．ここで R を正解デー(平均) の逆行列になっていることを意味し，直観的にも妥当な結果である．式 (9) は全クラスタにわたる総和となっているから，この計量行列 M は大域的に分散の大きい軸を縮小し，分散の小さい軸を拡大することでデータの分散を安定化する働きを持っていることがわかる．
ただし，一般に言語データにおいては素性は高次元かつ非常に疎であり，分散-共分散行列の和 A は正則
ではないことが多い．したがって，[16] と同様に，われわれは A−1 として Moore-Penrose の擬逆行列 A+を用いた．詳細については付録 2 を参照のこと．

4. 3 クラスタ重みを用いた一般化
般には含まれるデータ数に応じてクラスタには強弱があり，階層的クラスタリングにおいては上位クラスタ
ほどその意味は薄まると考えられる．この情報は正規iξi = 1) を用いて，最小化する式 (6) を以下のように一般化することで実現できる．

arg min
M

N

i=1

ξi



て正解データであるとき 1, 正解が全く含まれないときに 0 となり，クラスタの復元精度を表現する．上位

R 個以下の正解分布は再現率–適合率曲線およびその11 点平均精度によって示される．
この計算をテストデータ中のすべてのベクトルについて行い，平均を求めた．このため，テストデータ数

n に対し，その計算量は O(n2 ) である．クラスタリ
ングタスクでの精度測定については，5. 3 節で述べる．
以上での距離計算において，計量を用いない場合(ベースライン) および用いた場合を比較した．
5. 1 同義文検索
ある文に意味的に類似した文をコーパスあるいは用

前節でわれわれは各クラスタを同等に扱ったが，一化された各クラスタの重み ξ1 . . . ξN (

タ数ととれば，R-精度は計算結果の上位 R 個がすべ

(xj − ci )T M (xj − ci )(10)xj ∈Xi

例文集合から検索する問題は，用例ベース機械翻訳やQA における質問文からの解答候補の検索など，自然言語処理において基礎的な技術となっている．

5. 1. 1 同義文コーパス
このような同義文検索実験のために，われわれはATR で開発された旅行会話ドメインのパラフレーズ
コーパス [17] を用いた．このコーパスは 33,723,164
個の和文からなり，それぞれは 10,610 個の英文の一つと翻訳関係で対応している．この対応により，ある英文の翻訳である和文集合を同義文クラスタとみなすことができる．この中から，われわれは 200 個の訓練ク

これにより，式 (9) を同様に重みづけた解が得られる．

ラスタと 50 個のテストクラスタからなるデータセット

ただし，以下の実験では各クラスタに含まれるデータをランダムに非復元抽出して別々に作成した．1 つの数がほぼ等しいため，この一般化は用いていない．

クラスタに属する文は最大 100 文とし，これを超える

なお，提案手法は N = 1 の特別な場合として，通時はクラスタ内より 100 文をランダムに選んだ．この常のパターン認識におけるマハラノビス距離を含んでデータセットをさらに 10 個作成し，結果を平均した．

いることに注意されたい．

5. 実

験

提案手法の自然言語処理における効果を検証するた4

5. 1. 2 素性と次元圧縮
文の素性としては，ユニグラムおよび機能語のバイグラムを用いた．機能語バイグラムを含めたのは，会話文ドメインであるために，機能語の連接が言い換え

論文／言語表現のベクトル空間モデルにおける最適な計量距離において大きな役割を果たすと考えられるからである．

1

（注 2）

はいるが，素性の総数はデータ量に応じて数千から数0.6

万を超えるため，直接計量行列 M を求めることは現

Recall

旅行会話コーパスのため語彙数は比較的制限されて0.8

実的でなく，また素性が疎であるために，求めた計量

1%
5%
10%
20%
50%

0.4
0.2

も不安定になりやすい．このため，あらかじめ素性を0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

特異値分解によって次元圧縮し，1, 5, 10, 20, 50% の各圧縮率まで削減した．これは本質的に LSI [18] と同じ

Precision

方法であり，各ベクトル間の内積を最小二乗の意味で(a) 提案手法

最適に保存する．

5. 1. 3 結

1

果

1%
5%
10%
20%
50%

0.8

に示す．計量行列を用いた検索では通常のユークリッ
ド距離に比べてノイズが少なく，高精度な検索を実現

Recall提案手法を用いた同義文検索結果の例を付録図 A· 1

できることがわかる．図 A· 2 は次元圧縮をしすぎた場

0.6
0.4
0.2

合 (圧縮率=0.5%)，次元間に混入が生じている例であ0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Precision

るが，この場合でもほとんど無意味な結果を与える従来手法に比べ，本手法では上位に適切な結果が含まれ(b) ユークリッド距離ており，安定した検索性能を見せることがわかる．
図 2 に各圧縮率における再現率および適合率を示す．
これらの結果および図 3 の 11 点平均精度（注 3） は，提図 2 再現率─適合率曲線 (同義文検索)
Fig. 2 Precision-Recall Curve on sentence retrieval

案手法が通常用いられる単純な内積，および idf で重0.7

み付けた内積に比べ，常に高い検索性能を持っている

0.6

ことを示している．

0.4
0.3
0.1

ユークリッド (コサイン) 距離は，ここで左下–右上の00

対角成分のみ 1 の単位行列に対応する．図より明らかに，非対角成分に多くの正負の重みが割り当てられてていることがわかる．対角成分の絶対値の総和は，全行列での総和に対し 3.5% にすぎなかった．また，対Euclidean+idf

0.2

れた上でここでは 200 次元に圧縮されており，通常のおり，(圧縮された) 素性間の正/負の相関が表現されMetric+idf

0.5

5. 1. 4 計 量 行 列
図 4 に，同義文クラスタセットから得られた計量行列の一つを示す．素性はあらかじめ idf で重みづけら

Fig. 35 10 15 20 25 30 35 40 45 50
Dimension Reduction (%)

図 3 11 点平均精度 (同義文検索)
11 Point Average Precision on sentence retrieval

5. 2 文 書 検 索

角成分についてもその値は一様ではなく，idf による文書をクラスタに分類するタスクとして文書分類

重みがさらにクラスタ間相関によって適切に変えられ(Text Classiﬁcation) があり，Naı̈ve Bayes 法や SVMていることがわかる．図 5 に，素性自身の重みであるなど様々な識別器を用いた研究が盛んに行われている

対角成分のプロットを示す．

が [19]，これらはみな文書を事前に決められた少数のカテゴリに分類するものであり，新しいカテゴリ (ク（注 2）：ここでは振られた品詞タグに基づき，名詞・固有名詞・数詞・本
動詞を内容語，それ以外の語を機能語とした．トライグラム以上の素性は素性数が指数的に増大し，複数のバイグラムによって近似的に表現可能と考えられるために採用しなかった．
（注 3）：R-精度はここでは 11 点平均精度とほとんど同様であったため，
図は省略した．

ラスタ) に対しては識別器を構成することができない．
例えば，Web サイトをクラスタとみなすと，文書に対して可能なクラスタは非常に多数存在し，常に増え続ける性質があり，これらに対して 1 つ 1 つ識別器を構5

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–D–II No. xx
Dim.
Red.
0.5%
1%
2%
3%
4%
5%
10%
20%

Table 1R-precision
Metric Euclid
0.421 0.399
0.388 0.368
0.359 0.343
0.344 0.330
0.335 0.323
0.329 0.318
0.316 0.307
0.343 0.297

11-pt Avr. Prec.
Metric Euclid
0.476 0.455
0.450 0.430
0.425 0.409
0.411 0.399
0.402 0.392
0.397 0.388
0.379 0.376
0.397 0.365

表 1 文書検索精度．
Newsgroup text retrieval precisions.

書は中央値 (130 語) になるまでサブサンプリング／
図 4 同義文クラスタからえられた計量行列
Fig. 4 A metric matrix obtained from synonymousclusters.

オーバーサンプリングを行った．また，ベースライン
として tf.idf による単語重み付けを適用した．

5. 2. 2 結

0.035

果

0.03

表 1 に R-精度および 11 点平均精度を示す．テスト

0.025

セットは 4 クラスタからなるため，精度のベースライ
ンは 0.25 である．tf.idf およびユークリッド距離に比

0.02

べ，両方の基準で常によい精度を見せることがわかる
0.015(p 値の平均 = 0.0243)．
0.01

ただし，精度の改善は同義文検索に比べて少ない．

0.005

0

この理由の一つは素性圧縮にあると考えられる．われ0Fig. 5

20

40

60

80

100

120

140

160

180

200

図 5 計量行列の対角成分
Diagonal elements of the metric matrix.

われはデータ行列 X を最初に X = U SV −1 と特異値分解した後，k 個の最大固有値に対応する V の部分行
列 Vk を用いて Xk = Vk X とし， k 次元へ素性を圧成するのは現実的でない．このような環境における検縮したが，式 (5) からこれは，M 1/2 Xk = M 1/2 Vk X

索あるいはクラスタリングには大域的な距離尺度が必の各列間におけるユークリッド距離とみなすことがで要であり，提案手法が有効だと考えられる．

きる．ゆえに，クラスタ化が弱い場合，前処理におい

5. 2. 1 20-Newsgroup データセットて Vk が M の役割を吸収してしまう可能性がある．

このためのデータセットとして，われわれは 20–
Newsgroup dataset [20] を用いた．これは標準的なテ

したがって最適な性能のためには，高次元データに対キスト分類のデータセットの中では，比較的多い 20

ることがわかる．また，次元の呪いの存在しないカーのクラスタ (ニュースグループ) を持つ．20 のクラス

ネル法を用い，そのヒルベルト空間において同じ基準

タの中から 16 クラスタを訓練データ，4 クラスタをを考察することも考えられる．

しては計量の導出と次元圧縮を同時に考える必要のあ

テストデータとし，5 分割交差検定を行った．1 クラ

5. 3 一般ベクトルデータおよびクラスタリング

スタ当たりの文書数は最大 100 文書とし，これを越え計量を用いた距離は情報検索だけでなく，非言語

る場合は非復元抽出によってクラスタからランダムにデータやクラスタリングにおいても適用することがで100 文書を抽出した．素性はユニグラムとし，同様に0.5% ∼ 20% までの次元圧縮を行った．

きる．図 6 に，UCI 機械学習データセット [22] における K 平均クラスタリングに適用した結果を示す．右の提案手法はデータ空間におけるベクトルの分布から棒が計量距離，左の棒がユークリッド距離である．K

最適な計量を求めるために，言語データの場合，文書はデータ中のクラスタ数にとり，ランダムに初期化しの長さが非常に異なると各ベクトルのノルムが異なるて 100 回行い平均をとっている．クラスタリング精度

ため，適切な計量が得られない（注 4） ．このため，各文（注 4）：情報検索で一般に行われるように，ノルムを 1 に正規化する方法では，高次元の超球面上にすべてのデータが写像されるため，本手法

6

は意味のある計量を与えないことがわかった．Spherical K-means [21]のような超球面上での手法に適した計量を求めることは今後の課題である．

論文／言語表現のベクトル空間モデルにおける最適な計量距離
0.9

0.9

Precision

Precision

1

0.8
0.7
0.6

算のみを用いたもので高速であり，最適な計量をデー
タすべてを用いて一度で求めることができる．

0.8

今後の課題としてはまず，4. 3 節で述べたクラスタ
0.7

重みの最適な導出が考えられる．クラスタ化は一般には等質ではないため，これによりさらに適切な計量が

0.6
1

2

5

10

13

1

Dimension5

10 15 20

Dimension(a) “wine” データセット(b) “protein”データセット

Precision

1

Precision

2

0.9

0.8

0.7
2

3

Dimension(c) “iris” データセット

4

響について述べたが，クラスタ構造を考慮したこうした次元削減のほかに，[11] のようにカーネル法の枠組

1の中で，提案手法の基準である訓練データのクラスタ

0.9

歪み最小化を行うこともあげられる．この方法は次元0.8削減を必要としないが，適用範囲がカーネル化できる問題に限られるという欠点があり，一般のベクトル空0.7間における提案手法の意味はあると考えられる．

0.61

得られると期待できる．5. 2. 2 節で次元削減のもつ影

1

2

5

10 20 35

Dimension(d) “soybean”データセット

7. む す び
本論文ではベクトル空間において，ユークリッド距

図 6 UCI 機械学習データセットのクラスタリング精度．
横軸は圧縮した次元数を表す (右端は圧縮なし)．
Fig. 6 K-means clustering of UCI Machine Learning
dataset results. Horizontal axis shows compressed dimensions (rightmost is original).

離の代替として使用できる最適な計量距離を提案した．

は，ランダムに選んだ 2 つのデータが正しいクラスタ

機械学習データのクラスタリングタスクを用いて提案

リング (同クラスタ/別クラスタ) を持つ確率として [9]手法の効果を確認した．

と同様に計算した．
文書データである 20–Newsgroup データセットについても 5. 2. 1 節と同様の設定でクラスタリング実験

この距離は訓練データのクラスタ構造に基づき，クラスタ歪みを最小化する二次最適化問題の解として解析的に導出される．同義文検索，文書検索，および一般

謝辞

本研究は独立行政法人 情報通信研究機構の研究委託「大規模コーパスベース音声対話翻訳技術の研究開発」により実施したものである。

を行い，表 1 と同程度の精度の上昇を得ている．

6. 考

察

文
[1]

献

M. Hearst: “Multi-paragraph segmentation of expository text”, 32nd. Annual Meeting of the Association

本論文では，訓練データのクラスタ構造に基づいた
最適な計量距離を提案した．自然言語処理においてベ

for Computational Linguistics, pp. 9–16 (1994).
[2]クトル間の距離は長く用いられてきたが，データの分布に基づき，その空間の最適な計量を見出だすことは

00 (2000).
[3]

M. Collins and N. Duﬀy: “Convolution Kernels for[4]

J. Suzuki, T. Hirao, Y. Sasaki and E. Maeda: “Hi-

これまで比較的看過されており，最近になって機械学習において注目されている問題である．最近提案されNatural Language”, NIPS 2001 (2001).
erarchical Directed Acyclic Graph Kernel: Methods

たスペクトル法や SVM の下での計量と比べ，提案手

for Structured Natural Language Data”, 41th Annual

法はそうした特定の手法を前提とせず，ベクトル空間

Meeting of Association for Computational Linguistics, pp. 32–39 (2003).

において一般にユークリッド距離に代わり利用することができる．こうした意味で提案手法は [9] の後継手[5]要であり，データの持つ情報をすべて用いることは難C. D. Manning and H. Schütze: “Foundations of
Statistical Natural Language Processing”, MIT Press法であるといえる．ただし，[9] では「似た」点のペア(xi , xj ) の集合 S を訓練データとしているため，計量の導出にはデータ数 n に対して O(n2 ) のペア数が必F. Y. Y. Choi: “Advances in domain independent
linear text segmentation”, Proceedings of NAACL-(1999).
[6]

R. A. Baeza-Yates and B. A. Ribeiro-Neto: “Modern Information Retrieval”, ACM Press / AddisonWesley (1999).

[7]

K. R. Müller, S. Mika, G. Ratsch and K. Tsuda: “An

しく，ニュートン法を用いて繰り返し最適化を行うた

introduction to kernel-based learning algorithms”,

めに計算量も大きい．これに対し，提案手法は線形演IEEE Neural Networks, 12, 2, pp. 181–201 (2001).

7電子情報通信学会論文誌 xxxx/xx Vol. Jxx–D–II No. xx[8]

G. Salton and C. S. Yang: “On the speciﬁcation of付

term values in automatic indexing”, Journal of Documentation, 29, pp. 351–372 (1973).
[9]E. P. Xing, A. Y. Ng, M. I. Jordan and S. Russell:“Distance metric learning, with application to clus-

1. 計量行列の導出
4. 2 節の定理を証明する．すなわち，最小化問題

tering with side-information”, NIPS 2002 (2002).
[10]
[11]

F. R. Bach and M. I. Jordan: “Learning SpectralminClustering”, NIPS 2003 (2003).

M

M. Schultz and T. Joachims:

n



(
xj − ci )T M (xj − ci )

(A·1)

i=1 
xj ∈Xi“Learning a Dis-tance Metric from Relative Comparisons”, NIPS 2003

録を条件

(2003).
[12]

T. S. Jaakkola and D. Haussler: “Exploiting generative models in discriminative classiﬁers”, Proc. of the1998 Conference on Advances in Neural Information
Processing Systems, pp. 487–493 (1999).

[13]

E. P. Jiang and M. W. Berry: “Information Filtering Using the Riemannian SVD (R-SVD)”, Proc. of
IRREGULAR ’98, pp. 386–395 (1998).

[14]|M | = 1(A·2)の下で満たす計量行列 M を求める．

(A·1) を展開すると

 n n
 


B. De Moor: “Structured total least squares and L2
approximation problems”, Systems & Control, Spe-

i

xj



(xjk − cik )mkl (xjl − cil )k=1 l=1(A·3)

cial Issue of Linear Algebra and its Applications on
Numerical Linear Algebra, 188–189, pp. 163–207

である．ここで条件 (A·2) より，すべての k について

(1993).
[15]

R. O. Duda, P. E. Hart and D. G. Stork: “Pattern
Classiﬁcation *Second Edition”, John Wiley & Sonsn


(2000).
[16]

Y. Ishikawa, R. Subramanya and C. Faloutsos:“MindReader: Querying Databases Through Multiple Examples”, Proc. 24th Int. Conf. Very Large Data

sition method by cell-formed registration”, Proc.

(−1)k+l mkl |Mkl | = n

LREC-2002, Vol. I, pp. 326–328 (2002).

となる．ここで |Mkl | は M の第 (k, l)-小行列式である．したがって，(A·3) を (A·4) の条件の下で最小化

dexing by Latent Semantic Analysis”, Journal of the

すればよい．

391–407 (1990).

ラグランジュ乗数 λ を導入することにより，

T. Joachims: “Text categorization with support vector machines: learning with many relevant features”,
Proceedings of ECML-98, No. 1398, pp. 137–142

L=


N

 
i=1 
xj

k



(1998).
[20]

K. Lang: “Newsweeder: Learning to ﬁlter netnews”,−λProceedings of the Twelfth International Conferencek

I. S. Dhillon and D. S. Modha: “Concept Decompositions for Large Sparse Text Data Using Clustering”,
Machine Learning, 42, 1/2, pp. 143–175 (2001).

[22]

C. L. Blake and C. J. Merz:
itory

of

machinelearning“UCI Repos-

databases”

E.

W.

verse”

Weisstein:(2004).

“Moore-Penrose Matrix

Moore-PenroseMatrixInverse.html.

(−1)

mkl |Mkl | − n

l


∂L
=
(xjk − cik )(xjl − cil )∂mkli(1998).

xj− λ(−1)k+l |Mkl | = 0

 

In-

http://mathworld.wolfram.com/

k+lと定義すると，mkl で微分して 0 とおくことにより，

http://www.ics.uci.edu/˜mlearn/MLRepository.html.
[23]

(xjk − cik )mkl (xjl − cil )lon Machine Learning, pp. 331–339 (1995).
[21]

(A·4)

k=1 l=1

S. Deerwester, S. T. Dumais and G. W. Furnas: “InAmerican Society of Information Science, 41, 6, pp.

[19]

すなわち，

F. Sugaya, T. Takezawa, G. Kikui and S. Yamamoto: “Proposal for a very-large-corpus acqui-

[18]

l=1

n
n



Bases, pp. 218–227 (1998).
[17](−1)k+l mkl |Mkl | = 1⇔ |Mkl | =

i


xj

(xjk − cik )(xjl − cil )λ(−1)k+l

.
(A·5)

8

論文／言語表現のベクトル空間モデルにおける最適な計量距離

ここで M −1 = [m−1kl ] とおくと，

m−1
kl =

k+l

(−1) |Mkl |= (−1)k+l |Mkl | (... A·2)
|M |

 

(xjk − cik )(xjl − cil )

x

i

=

j

(... A·5)

λ

.

(A·6)

Query: “合計でいくらですか”(‘How much is the total?’)Metric distance:
distancesynonymous sentence

0.2712

合計でいくらでしょうか *内金はいくらですか
入場料はいくらですか
手付金はいくらですか
合計でいくらいたしますか *合計でいくらいたしますでしょうか *全部でいくらですか *合計でいくらになりますか *合計でいくらになりますでしょうか *合計でいくらになるでしょうか *0.34440.34440.369
0.43770.4479

したがって，

0.45050.4558A = [akl ](A·7)

0.4602
0.4682

akl =

N



(xjl − cil )(xjk − cik )

(A·8)

i=1 
xj ∈Xi

Euclidean distance:
distancesynonymous sentence

0.1732

全部でいくらですか *合計でおいくらですか *紫外線防止ですか
内金はいくらですか
入場料はいくらですか
手付金はいくらですか
全部でおいくらですか *どんな兆候ですか
どんな症状ですか
お一人ですか

1.781と定義すると，(A·6) により

1.902
1.966

−1

A = λM.
. . |A| = λn |M −1 | = λn... λ = |A|1/n .

1.966
1.974
1.983

(A·9)

2.283
2.505
2.65

ゆえに

(* denotes the right answers.)

M = λA−1 = |A|1/n A−1 .

(A·10)
Fig. A· 1

ここで A は (A·7), (A·8) で定義される行列．

図 A· 1 同義文検索の例．
Example of Sentence Retrieval.

2

2. Moore-Penrose の擬逆行列

Query: “デザートに果物をくれないでしょうか”(‘I’d like some fruit for dessert.’)

行列 A の Moore-Penrose の擬逆行列 A+ は A がMetric distance:

非正則な場合でも，x = A+ y が y = Ax の最小二乗かつ最短の解となるという意味で通常の逆行列の性質

distancesynonymous sentence

0.3531

請求書をすぐにくれないでしょうか
デザートとして果物をくれますか *請求書をすぐにくれませんか
伝票をすぐにくれますか
伝票をすぐにくれますでしょうか
お勘定書をすぐにくれますか
伝票をすぐにくれませんでしょうか
お勘定書をすぐにくれませんか
伝票をすぐにくれないですか
デザートには果物をくれないですか *0.3709を持つ一意な行列である [23]．

0.596

A+ は MATLAB 関数 pinv 等を用いて簡単に求めることができる．または [16]，正規直交行列 U および Σ = diag(σ1 , . . . , σr , 0, . . . , 0) (r = rank(A)) を用いて，A を A = U ΣU T と対角化すれば，A+ は
A+ = U Σ+ U T と求められる．

0.6104+ここで Σ= diag(1/σ1 , . . . , 1/σr , 0, . . . , 0) である．

したがって，

M = (σ1 σ2 · · · σr )1/r A+

0.621
0.62550.62950.63430.66850.7966

Euclidean distance:
distancesynonymous sentence

1.036

請求書をすぐにくれないでしょうか
朝ごはんを部屋に運んでもらえないでしょうか
ウィスキーを二人分くれないでしょうか
ウィスキーを二つくれないでしょうか
薬をくれないでしょうか
朝食を部屋に運んでもらえないでしょうか
朝食を部屋に運んでもらえないでしょうか

1.421(A·11)

1.491
1.499

を得る．

2
（平成 xx 年 xx 月 xx 日受付）

1.535
1.622
1.622
:

:

2.787

デザートとして何か果物をくれないでしょうか *この円をポンドに換算くださらないでしょうか

2.854

Fig. A· 2

図 A· 2 次元削減率の高い場合．
High rate of dimensionarity reduction.

9電子情報通信学会論文誌 xxxx/xx Vol. Jxx–D–II No. xx

持橋 大地
1998 年 東京大学教養学部 基礎科学科第二卒業. 2000 年 奈良先端科学技術大学院
大学 情報科学研究科 自然言語処理学講座
博士前期課程修了．現在同講座 博士後期課
程在学中．自然言語処理，特にベイズ統計的アプローチによる意味的処理と時系列モデルに関心を持つ．2003 年より ATR 音声言語コミュニケー
ション研究所 研修研究員．

菊井玄一郎
1986 年京都大学工学部電気工学第二専
攻修士課程修了. 同年 NTT に入社，2001

年 4 月より（株）国際電気通信基礎技術研
究所 (ATR) に出向，現在に至る．在学中
より、自然言語処理，音声言語処理，特に音声翻訳，WEB 情報検索、多言語情報検索等の研究開発に従事．ACL，人工知能学会，言語処理学会
各会員．

北

研二

（正員）

1981 年 早稲田大学 理工学部 数学科卒

業．1983 年から 1992 年まで沖電気工業(株) 勤務．この間，1987 年から 1992 年まで ATR 自動翻訳電話研究所に出向．1992
年 9 月より徳島大学工学部勤務．現在，同教授．工学博士．自然言語処理，情報検索等の研究に従事．電子情報通信学会，言語処理学会 各会員．

10

Abstract Many natural language processing still depend on the Euclidean distance function between
the two feature vectors, but it has severe defects as to feature weightings and feature correlations. In thispaper we propose an optimal metric distance function that can be used as an alternative to the Euclidean
distance, accommodating the two problems at the same time. This metric is optimal in the sense of global
quadratic minimization, and can be obtained from the clusters in the training data in a supervised fashion. We conﬁrmed the eﬀect of the proposed metric by the sentence retrieval, document retrieval, and theK-means clustering of general vectorial data.
Key words Metric learning, cosine distance, tf.idf, feature space, kernel methods