1何のための手法か

「この2つは似ているか」を、何を特徴と見るかを決めずに問う。

ふつう、2つの対象の類似度を測るには、まず特徴を取り出す。単語の頻度、座標、カテゴリの有無といった数値の列に直し、そのうえでユークリッド距離やコサイン距離を計算する。この手順には、どの特徴を選ぶかという判断が最初に入り込む。選ばなかった情報は、そこで落ちる。

正規化圧縮距離（Normalized Compression Distance, NCD）は、この手順を踏まない。2つのファイルをそのまま圧縮器に渡し、圧縮後のサイズだけを見る。似ている2つを連結して圧縮すると、共通する部分が繰り返しとして検出されて縮む。似ていなければ縮まない。この差を数値にしたものが NCD である。

小野原 (2010) がこの手法を採ったのは、比較したい対象が入れ子構造を持つ XML ドキュメントだったからである。地理情報標準に準拠して設計したモデルに従い、調査地点ごとの方言情報を XML にした。緯度経度、語彙の一般名称、語彙の発音が階層的に入っている。このような複雑な構造を持つデータは、論文の言葉を借りれば「分析方法が限られるため、取り扱われる機会は少なくなる」。NCD は、その構造を平坦な数値表に直すことなく距離行列を得る道を与える。

論文が挙げている利点

「この分析方法の利点の一つは、一般的な分析手法と比較して、事前のデータ抽出や整形などが簡略化できることにある」と論文は述べている。特徴設計をしないことは、情報を捨てない代わりに、何を測っているのかが見えにくくなることでもある。この裏表は第6節で扱う。

2起源 ―― 計算できない量を、圧縮器で置き換える

出発点はコルモゴロフ複雑性。ただしそれは計算できない。

コルモゴロフ (1965) は、個々の対象の情報量を、確率分布を経由せずに定義した。文字列 \(x\) の複雑性 \(K(x)\) とは、\(x\) を出力する最短プログラムの長さである。規則的な文字列は短いプログラムで書けるので \(K\) が小さく、でたらめな文字列は自分自身を書き下すしかないので \(K\) が大きい。

ここから2つの対象の隔たりを定義できる。\(x\) を知ったうえで \(y\) を作るのに必要な追加の記述長を使う考え方で、Li ら (2004) はこれを正規化して正規化情報距離（normalized information distance）とし、一定の意味で最適な距離であることを示した。

問題は、\(K\) が計算不可能なことである。ある文字列に対する最短プログラムを一般に求める手続きは存在しない。そこで Cilibrasi と Vitányi (2005) は、\(K(x)\) を実在の圧縮器による圧縮後サイズ \(C(x)\) で置き換えた。こうして得られるのが NCD であり、理論上の最適性と引き換えに、実際に計算できる量になっている。

この置き換えが、手法のすべてを決めている

圧縮器は最短プログラムを見つける装置ではない。GZIP なら直前の一定範囲に現れた繰り返しを辞書で置き換えるだけで、それ以上のことはしない。したがって NCD が捉える「似ている」は、その圧縮器が捉えられる種類の規則性に限られる。近似の質は圧縮器の性能そのものであり、手法の妥当性はここに集約される。

論文はこの系譜を引用していない

小野原 (2010) の参考文献に Kolmogorov や Cilibrasi & Vitányi は含まれておらず、NCD は定義式とともに「汎用類似度算出技術の一つ」として導入されている。上に述べた系譜は、この手法の位置づけを説明するために本ページで補ったものである。

3観点5「情報理論」のどこに当たるか

同じ「情報量」でも、測っている対象が違う。

7つの観点を式で読むの観点5は、「短く符号化できることを、よい説明とみなす」という立場をまとめている。そこに並ぶエントロピー \(H(p)=-\sum_x p(x)\log p(x)\)、カルバック・ライブラー情報量、AIC はいずれも確率分布に対して定義された量である。符号長の期待値を考えており、背後には「データを生む分布がある」という前提が置かれている。

NCD が属するのは、同じ情報理論でもアルゴリズム的情報理論の側である。\(K(x)\) は分布ではなく個々の対象1つに対して定義される。確率モデルを立てないので、モデルが正しいかという問いが発生しない。代わりに、圧縮器が十分よいかという問いが発生する。

2つの情報量の、測る対象の違い
\[ H(p) \;=\; -\sum_{x} p(x)\log p(x) \qquad \text{対} \qquad K(x) \;=\; \min\{\,|P| \;:\; U(P)=x\,\} \]

\(H(p)\) … 分布 \(p\) の平均的な予測しにくさ。個々の \(x\) には値が付かない
\(K(x)\) … 対象 \(x\) そのものの記述長。\(U\) は万能機械、\(|P|\) はプログラム長
共通するもの … どちらも「短く書けること」を良さとみなす

AICと同じ屋根の下にあるが、立っている場所が違う

観点5の AIC は、当てはまりを対数尤度で測り、パラメータ数で罰を与える。モデルの複雑さを数えている。NCD は対象そのものの記述長を問題にし、モデルを持たない。どちらも「記述が短いほうがよい」という同じ原理を共有しながら、一方は分布とモデルの世界に、他方は個別の対象の世界に立っている。観点5にこの手法を置くのは前者の意味ではなく、符号長で良さを測るという原理を共有するからである。

4定義と、なぜ正規化するのか

連結して圧縮したときに、どれだけ得をするか。

正規化圧縮距離
\[ \mathrm{NCD}(x,y) \;=\; \frac{C_{XY} - \min\{C_X,\, C_Y\}}{\max\{C_X,\, C_Y\}} \]

\(C\) … 圧縮アルゴリズム
\(C_X,\, C_Y\) … \(x\)、\(y\) をそれぞれ単独で圧縮したファイルサイズ
\(C_{XY}\) … \(x\) に \(y\) を連結して圧縮したファイルサイズ

式の形は論文に記載されたとおりである。読み方は次のようになる。

分子は「一方を知った上での、もう一方の追加分」

仮に \(C_X \le C_Y\) とすると、分子は \(C_{XY} - C_X\) である。これは\(x\) をすでに書いたあとで、\(y\) を書き足すのに追加で必要になった量にあたる。\(x\) と \(y\) が似ていれば、\(y\) の多くは \(x\) の繰り返しとして参照でき、追加分は小さくなる。全く似ていなければ、\(y\) をほぼ丸ごと書くことになり、追加分は \(C_Y\) に近づく。

分母は長さの違いを打ち消すため

追加分をそのまま使うと、長いファイルほど距離が大きく出てしまう。長い文書どうしは、似ていても追加分の絶対量が大きい。そこで大きいほうの圧縮サイズで割り、「追加分は、丸ごと書いた場合の何割か」という比に直す。これにより値はおおよそ \([0,1]\) に収まり、長さの異なる対象どうしを同じ物差しで比べられる。

0 に近いほど似ている、1 に近いほど似ていない。完全に同じ対象なら、連結しても圧縮後サイズはほとんど増えないので、分子はほぼ 0 になる。

近似であることは、定義の時点で織り込まれている

この式の \(C\) を \(K\) に置き換えたものが理論上の正規化情報距離である。\(K\) は計算できないので、実在の圧縮器を代入して使う。したがって NCD は常に近似であり、圧縮器を変えれば値が変わる。論文も「NCD は、圧縮アルゴリズムに依存する」と明記したうえで、使用したソフトウェアが GZIP 圧縮のみをサポートしていることを述べている。

5この研究での使い方

方言の分布図を XML に直し、地点どうしの NCD から領域を抽出する。

対象は岐阜県全域の方言語彙である。『岐阜県方言の研究』（奥村, 1976）に掲載された10枚の分布図から、125箇所の調査地点について、唐がらし・唐もろこし・薬指・旋毛・竹馬・お手玉・粳米・馬鈴薯・真綿・里芋の10語彙をどう発音するかを読み取った。

  1. 属性の抽出　各分布図から、調査地点ごとに「緯度経度情報」「語彙の一般的名称情報」「語彙の発音情報（方言）」の3つを取り出す。たとえば調査地点1では、唐がらしが「ナンバン」、唐もろこしが「トウナ」、薬指が「ベニサシユビ」、真綿と里芋はデータ無しである。
  2. メタモデルの設計　文化現象を時空間上で人間が行う一連の行動として定義した「メタ・メタモデル」を上位概念に置き、その下に方言のメタモデルを設計する。地理情報標準の応用スキーマ（ISO19109）に準拠させ、「方言（Dialects）」クラスが「話し手（Speaker）」と「語彙（Vocabulary）」に関係を持つ「メッセージ（Message）」クラスから成る構造とした。
  3. XML へのインスタンス化　地理情報標準の符号化規則（ISO19118）に従い、調査地点ごとに1つの XML ドキュメントを作る。125地点ぶんの XML が比較対象になる。
  4. NCD の算出　藤本が開発した NCD 算出ソフトウェア「百花壱式 Ver1.0」を用い、125個のドキュメントのすべての組み合わせについて NCD を計算して距離行列を得る。同ソフトウェアのバージョンは GZIP 圧縮のみをサポートする。
  5. 欠損の多い地点の除外　XML 内で「NULL」と表した欠損が類似性として結果に影響を及ぼすため、欠損値の多い15地点（35, 62, 93, 96, 104, 114, 115, 116, 119, 120, 121, 122, 123, 124, 125）をあらかじめ分析対象から外し、110地点とする。
  6. クラスタリング　得られた距離行列に、非階層的な PAM、階層的な Ward・Average、系統学的な Neighbor Joining・Neighbor-Net、グラフクラスタリングの DPClus を当て、結果を比較する。
  7. 検証　同じ調査から別のデータセットを作り、先行研究と照合する。

分類の結果

PAM では5クラスタとし、外れ値の1クラスタを除いた4分類が適切だと判断された。一方、NCD 行列からの分類法としては、Neighbor Joining のアルゴリズムに基づく Neighbor-Net が、先行研究の成果を最も忠実に再現した。具体的には、徳山村戸入地区（調査地点28）の孤立と、大垣市（調査地点63）と垂井町（調査地点51）のあいだの東西アクセントの対立が図に現れている。いずれも方言学で古くから知られてきた事実である。

検証は、別のデータと別の距離で行われた

NCD が発音の類似性を適切に反映しているかを確かめるため、同じ調査から2種類の行列を別に作った。ひとつは列を調査語彙、行を調査地点とし、各地点での発音を一文字の記号に置き換えたもの。もうひとつは列を調査語彙のすべての発音、行を調査地点とし、その語彙が存在すれば1、しなければ0とした2値データである。距離には Gower と（2値データには）Jaccard を用い、クラスタリングは NCD の場合と同じ手法を試した。

データ距離先行研究を最もよく再現した分類法
XML ドキュメントNCD（GZIP）Neighbor-Net
発音を記号化した行列Gower―（下の行が最良）
語彙の有無の2値データJaccardDPClus（距離<0.85, density=0.95, 最小構成地点数=4）

いずれも110地点での分析。論文は、両者の結果を比較して「各グループの中核的な構成地点に差は無く、NCD による分析の有効性は示された」と述べている。用いたのは語彙分布の類似性データであるが、アクセント分布による先行研究結果との間にも齟齬が無いことにも注目すべきである、としている。

結論として得られた領域

調査地点は7から8のクラスタに分類でき、そのうち3から4のクラスタは地理的なまとまりを持たない。そこから地理空間的な視点で見ると、岐阜県下は大きく4つのグループに分けられるという結論が導かれた。論文は、これら4グループの境界の一つが岐阜市周辺に位置し、同じ傾向が藤本 (2010) による縄文土器を用いた分析でも指摘されていることに触れている。

6限界

値を左右するのは、対象そのものだけではない。

圧縮器を変えれば、距離が変わる

NCD は \(K\) の近似なので、どの圧縮器を使うかが結果に直接効く。この研究では GZIP のみが使われた。GZIP は直前の一定幅（ウィンドウ）に現れた繰り返しを辞書で置き換える方式で、ウィンドウを超えて離れた位置にある繰り返しは捉えられない。連結したファイルが長くなると、前半と後半の対応が見えなくなる領域が生じる。

Cebrián ら (2005) は、圧縮器が冪等でないこと、すなわち同じ内容を2つ並べても圧縮後サイズが単独の場合の2倍近くになってしまう場合があることを示し、対象のサイズとウィンドウサイズによって NCD が歪むこと、その結果として \(\mathrm{NCD}(x,x)=0\) という同一性が崩れることを報告している。論文自身も圧縮アルゴリズムへの依存には言及しているが、ウィンドウサイズの影響までは検討していない。

同じスキーマから作った XML どうしは、はじめから似ている

比較対象の125個の XML は、いずれも同じメタモデルから生成されている。したがってタグ構造がすべて共通である。<dataset>、<communication>、<message>、<pronunciation> といった文字列が、中身の発音が全く違う地点どうしでも同じように並ぶ。連結して圧縮すれば、この共通部分がまとめて縮む。

その結果、距離行列の値は全体として似ている側に寄り、地点間の差が圧縮される方向に偏りうる。タグの冗長性が大きいほど、発音情報という本来見たい部分の寄与は相対的に小さくなる。論文はこの点に触れていない。本ページで指摘しておくのは、XML を入力とする NCD 分析に共通して当てはまる性質だからである。

距離の公理を厳密には満たさないまま、系統推定に渡されている

前述のとおり、実在の圧縮器を使う NCD では同一性が厳密には成り立たず、三角不等式も保証されない。ところがこの研究では、得られた行列を PAM、Ward、Average、Neighbor Joining、Neighbor-Net、DPClus に渡している。とくに Neighbor Joining と Neighbor-Net は、距離が加法的であること、すなわち枝長の和として表せることを前提に枝を組み立てる手法である。

NCD の値はこの前提を満たすように作られていない。それでも先行研究を再現できたという事実は、手法の頑健さを示す実証的な証拠ではあるが、理論的な正当化ではない。得られたネットワークの枝長を、系統の分岐年代のように読むことはできない。

除外の基準が示されていない

15地点が「欠損値が多い」として除外されたが、何件以上を多いとしたかは論文に書かれていない。除外の理由そのもの（XML 内の「NULL」という文字列が共通するために、中身と無関係に似てしまう）は妥当であり、これは上で述べたタグの冗長性と同じ問題の別の現れでもある。

ただし除外は分析対象そのものを減らす操作であり、地図上ではそれらの地点が空白になる。論文は図の中で除外した地点を小円・茶色で示し、クラスタに分類されなかった地点を灰色で示したうえで「灰色の調査地点内で一つのクラスタを形成することを示すものではない」と注記している。図の読み方についての注意が明示されている点は、手法の使い方として適切である。

クラスタ数は、先行研究をどれだけ再現したいかで変わっている

多次元尺度構成法で概要を把握したところ、全調査地点を4つにグループ分けするのが適当だと分かった。その一方で、先行研究を通して明らかとなった地域差を見ようとするならば、どのクラスタ分析においても7から8のクラスタに分ける必要があることも明らかとなった、と論文は述べている。

つまりクラスタ数は、データだけから決まったのではなく、何を見たいかによって選ばれている。最終的な「岐阜県下は大きく4つ」という結論は、7から8のクラスタのうち3から4が地理的まとまりを持たないという観察を経て導かれたものであり、この経路は論文に明記されている。先行研究との一致は妥当性の傍証になるが、同時に、先行研究が示す構造を見るようにクラスタ数を選んだという循環も含んでいる。

論文自身が述べている留保

結論部で、語彙変化の方向の推定と「典型（Archetype）」データを用いた岐阜県外との関係の分析について、「厳密な部分の解釈を行うためには、より慎重なデータ作成や先行研究データの精査が必要となることが分かった」と述べられている。NCD による領域抽出そのものは有効と判断したうえで、そこから先の解釈には慎重さを求める書き方になっている。

7出典とデータ

本ページは、2010年11月付の発表資料に基づく。執筆時点の所属は同志社大学大学院 文化情報学研究科 博士前期課程であり、本研究は CITMAS プロジェクト（代表者：藤本悠）における研究成果の一部である。

手法の文献

下の4件は、NCD の理論的な位置づけを説明するために本ページで補ったもので、論文の参考文献には含まれていない。Huson & Bryant のみ論文が引用している。

  • Kolmogorov, A. N. (1965) Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1).
  • Li, M., Chen, X., Li, X., Ma, B. & Vitányi, P. M. B. (2004) The similarity metric. IEEE Transactions on Information Theory, 50(12), 3250–3264.
  • Cilibrasi, R. & Vitányi, P. M. B. (2005) Clustering by compression. IEEE Transactions on Information Theory, 51(4), 1523–1545. doi:10.1109/TIT.2005.844059
  • Cebrián, M., Alfonseca, M. & Ortega, A. (2005) Common pitfalls using the normalized compression distance: What to watch out for in a compressor. Communications in Information and Systems, 5(4), 367–384.
  • Huson, D. H. & Bryant, D. (2006) Application of phylogenetic networks in evolutionary studies. Molecular Biology and Evolution, 23(2), 254–267.

照合した先行研究（論文の引用による）

  • 服部四郎 (1930)「近畿アクセントと東方アクセントとの境界線」『音聲の研究』第三輯, 文學社, pp.131–144.
  • 柴田武 (1950)「揖斐川上流のアクセント」『文字と言葉』刀江書院.
  • 山田達也 (1978)「揖斐川上流域における基礎語彙について」『名古屋市立大学教養部紀要 人文社会研究』22, pp.33–66.
  • 徳山村の歴史を語る会 (1984)『徳山村のあけぼのを求めて ―岐阜県揖斐郡徳山村遺跡分布調査中間報告―』
  • 藤本悠 (2010)『文化情報学および理念型モデル化分析法に関する基礎的研究 ―文化情報学における諸概念と方法について―』同志社大学大学院文化情報学研究科 博士論文.

この手法がどの観点に属するか

NCD は、対象の良さや近さを符号長で測るという原理に立っている。短く書けるなら、そこには規則性があるとみなす。7つの観点を式で読むの観点5（情報理論）が扱うエントロピーや AIC と同じ原理を共有しているが、それらが確率分布に対して定義されるのに対し、NCD は個々の対象そのものに対して定義される点が異なる。確率モデルを立てないため、モデルの当てはまりを問う代わりに、圧縮器の性能を問うことになる。
この研究では、得られた距離行列を Neighbor-Net（観点1）に渡して系譜構造を描いている。観点をまたいで手法が接続する例である。

このページは、小野原が実際の研究で使っている手法を、同じ分野の読み手に向けて整理したものです。数値と結果はすべて発表資料に記載されたものを引用し、推定値や概算は記載していません。文献の書誌情報は、論文の参考文献欄とは別に実在を確認したうえで記載しています。
手法の位置づけの全体像は 7つの観点を式で読む、どの授業回がどの観点に当たるかは 手法と数学の地図 にあります。