はじめに
本記事は、ulgeek Advent Calendarの18日目です。
これまでプログラミング技術のHowが多かったかと思いますが、少し毛色を変えて、プログラミング技術の裏にある数学的な背景に興味が出そうな話題を提供いたします。
なお、数式でよくわからない部分は飛ばしながら斜め読みしていただいてOKです！
突然ですがクイズです。
次の図において、地点Aから地点Bの距離を求めてください。道の幅は無視することとします。
次のように線分ABを引き、その長さを距離とすると、$\sqrt{2}$ kmですね。
しかし、タクシーで地点Aから地点Bに行くとすると、下図のルートを通ります。
このとき、走行距離は 2km ですよね。
このように、ひとくちに「距離」と言っても、日常では様々なはかり方を包含して、「距離」という言葉を使用しています。
では、この「距離」とはいったい何者なのでしょうか？
で、今日の話題は？
この記事では、クイズの2つの回答を通じて数学的に「距離」がどのように定義されるか、「距離」の本質とはなにかということを確認します。その後、単語間の類似度の指標として用いられる編集距離をみてみましょう。
編集距離は、2つの文字列がどれくらい似ているか、という類似度の指標のひとつです。例えば（いまはわかりませんが）Google検索の「もしかして」に応用できます（参考：スペル修正プログラムはどう書くか）。
そんな編集距離ですが、この記事でなぜ距離と呼ばれているのかが本記事でわかるようになります。クイズのような「距離」と単語間の「距離」は本質的には同じなのです。
なお、本記事では編集距離の実装方法には触れませんので、ご了承ください。
回答1：ユークリッド距離
そもそも、距離を測るときに、何と何のどんな距離を測りたいのでしょうか？
そりゃあ、地点Aと地点Bだよ、と思うかもしれませんが、まずはどのような土俵で数学的な議論ができるのか、もう少し考えてみましょう。
まずは、一次元で考えよう
地点Cを以下の図の場所としてみます。
この図において、地点Aと地点Cは、ひとつの数直線上にあると定義できます。このとき、地点Aと地点Cの距離は1kmです。
いまから数学的な議論をするにあたり、クイズの地図のように人間が実用に使用する図から、数直線という味気ない図に変えて議論しますので、"km"という単位や"地点"という言葉は意味をもちません。したがって、以下の議論では"km"という単位を省略し、"地点"という言葉を"点"と呼びます（気になる方は頭の中で"km"や"地点"を補完してもらっても構いません）。
さて、数直線上の点Aと点Cの距離は1ですが、これは点Aが数直線のどこにあっても、点Cは右に1ずれた点と見ることができますので、点Aの数直線上の値を$a$とすると、点Cの数直線上の値を$a+1$と表すことができます。
このとき点Aと点Cの距離$d$は、$d=(a+1)-a=1$と求めることができます。
見方を変えると、距離$d$は点Aと点Cを入力としてその間の実数値を求めるものなので、点Cを$c$とすると、関数として以下のように書くことができます（$|\cdot |$は絶対値で、例えば$|1|=|-1|=1$です）。
$$ d(A, C) = |a-c| = \sqrt{(a-c)^2}. $$
$d$は、数直線（つまり実数）の2つの点を0以上の実数へ変換する関数です。
もう少しややこしく言うと、点Aと点Cの距離というのは、 実数という集合上の2点間に定められる非負（0以上）の実数値 を指しています。
同じことを、二次元で考えてみる
同様に点A、Bを2次元平面上の点とみなしましょう。点Aを $(a_1, a_2)$ 、点Bを $(b_1, b_2)$ とすると、線分ABの長さ$d$は、直角三角形ABCの斜辺を求めるピタゴラスの定理より
$$ d(A, B) = \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2} $$
と書けます。
このとき求められる$d$は、回答1の距離そのものです。（実際に $b_1=a_1+1$、 $b_2=a_2+1$ とすると、$d(A,B) = \sqrt{(a_1 - (a_1 + 1))^2 + (a_2 - (a_2+1))^2} = \sqrt{2}$ とわかります。）
つまり回答1のように定める点Aと点Bの距離$d$というのは、 実数のペアの集合上の2点間に定められる非負の実数値 です。
もう少し数学的な表現に言い換えましょう。実数を $\mathbb{R}$、実数のペアの集合を $\mathbb{R}^2$ とすると、 距離 $d$ は $\mathbb{R}^2$ の2点 $A, B$ 間に定まる非負の実数値 です。
このように距離を $ d(A, B) = \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2} $ と定義するとき、$d$ を（ $\mathbb{R}^2$ 上の）ユークリッド距離と呼びます。ちなみに、ユークリッドは「幾何学の父」とされる古代ギリシアの偉大な数学者の名前です。
先ほど「何と何の距離を測りたいのでしょうか？」と問いましたが、回答1のように、クイズに $\sqrt{2}$ kmと答えた方は、 $\mathbb{R}^2$ の点Aと点Bのユークリッド距離を求めていたんですね。
余談：N次元なら？
余談ですが、一般化すると、次のことが言えます。
$n$個の実数の組の集合を$\mathbb{R}^n$とすると、$\mathbb{R}^n$上の2点A$(a_1,...,a_n)$
B$(b_1,...,b_n)$のユークリッド距離は次のように定義されます。
$$ d(A, B) = \sqrt{\sum_{i=1}^{n}(a_i-b_i)^2} .$$
ユークリッド距離を定義した$\mathbb{R}^n$は、特に**$n$次元ユークリッド空間**と呼ばれます。
回答2：マンハッタン距離
では、回答2のような距離は、何と何のどんな距離なのでしょうか？
このような距離 $d$ は、同じ集合 $\mathbb{R}^2$ の点Aと点Bの間に定まる関数として、次のように定義できます。
$$ d(A,B) = |a_1 - b_1| + | a_2 - b_2 | $$
この距離をマンハッタン距離と呼びます。言葉の定義は、マンハッタンが碁盤の目状の都市であり、自動車で運転する際の距離に相当することに由来します。
回答2のようにクイズに2kmと答えた方は $\mathbb{R}^2$ の点Aと点Bのマンハッタン距離を求めていたということができます。
距離の本質とは
ユークリッド距離もマンハッタン距離のどちらも、集合の2つの点の間に量を定義し、それを「距離」と呼んでいることを見てきました。
そして距離というのは、集合の2つの点から非負の実数値を与える関数を定義していることと同じということがわかりました。
これらの関数の値（つまり距離）は、次のような特徴をもっています。
- 0以上（0は同じ点同士のときの値で、点Aと点Bが異なる場合は0より大きい）
- 点Aと点Bの間ではかる値と、点Bと点Aの間ではかる値は同じ
- 点Cに寄り道すると、点Aから点Bにまっすぐはかる値より大きくなる
数学的な記述をすると、集合 $X$ の2点 $x$、$y$に対し、距離 $d(x,y)$ は、次のような特徴があります。
距離の基本3性質
- $d(x,y) \geq 0$（ただし$x=y$のときのみ$d(x,y)=0$が成り立つ）
- $d(x,y) = d(y,x)$
- 集合 $X$ の点$z$に対して、$d(x,y) \leq d(x,z) + d(y,z)$
興味のある方は、ユークリッド距離やマンハッタン距離に対してこれらが成り立つことを確認してみてください。
ここまでは直感的な距離（ユークリッド距離とマンハッタン距離）がもつ共通の性質を紹介しましたが、逆にこの特徴をもつ関数を距離関数と定義しましょう。つまり、集合$X$上の2点に対して非負の実数を定める関数 $d$ のうち、上記のような性質を持つ関数を距離関数と定義します。
ユークリッド距離やマンハッタン距離の他にも、上記の性質をもつ関数はすべて距離関数です。
また、このように距離関数を定めた集合$X$を、距離空間と呼びます。ユークリッド空間は距離空間のひとつです。
たとえば、ユークリッド距離やマンハッタン距離の他に$\mathbb{R}^2$上に定義できる上記の性質をもつ関数として、$x=(x_1,x_2)$、$y=(y_1,y_2)$ とすると
$$d(x,y) = \max (|x_1-y_1|, |x_2-y_2|)$$
があります。この距離はチェビシェフ距離と呼ばれます。将棋で言えば、王将はチェビシェフ距離1の範囲で動ける駒ですね。
余談：空間と集合の違い
集合に「構造」を与えたものが空間です。単にものの寄せ集め（集合）から「距離」という構造を入れた集合が距離空間です。集合に距離という概念を定義することで、ものの寄せ集めに奥行が感じられるようになりますよね。さらにその奥行の作り方には、ユークリッド距離やマンハッタン距離やチェビシェフ距離のようにいろいろあるんです。
つまり、集合と距離関数をセットで見なければ、距離空間と呼ぶ意味がありません。
クイズのような地図、2つの実数のペアからなる集合の2点間に、ユークリッド距離を導入した距離空間と、マンハッタン距離を導入した距離空間は、異なる距離空間なのです。
そして日常の感覚から直感的に求めた回答1、回答2のどちらの距離も、同じ特徴をもっているんですね。
単語と単語の距離
さて、距離空間とはなにかを定義したところで、実際に距離空間を作ってみましょう。
そこで本題の「単語と単語の距離」を定義してみたいと思います。
ユークリッド距離やマンハッタン距離は地図のように空間的な広がりをイメージしやすいですが、単語と単語ってどんな空間になるのでしょうか。
集合として「単語全体からなる集合」を考えましょう。今回は説明の簡単のために「ローマ字の単語全体からなる集合」としますが、本質的なことは日本語でもヘブライ語でも変わりません。
この集合の要素には、"ulgeek"や筆者の名前の"taguchi"のような固有名詞もあれば、"dog"や"doing"のような英単語も、なんでもありです。
そこで、ある単語に対して、1文字の挿入・削除・置換を繰り返すことにより別の単語にするときの繰り返し回数を考えましょう。
例えば、"dog"を"doing"にするには、
- "i"を挿入する
- "n"を挿入する
の2回の操作により変換できます。また、"taguchi"を"tanuki"にするには、 - "g"を"n"に変換する
- "c"を"k"に変換する
- "h"を削除する
の3回の操作により変換できます。
この回数は一般に編集距離と呼ばれます。
編集距離は、距離の本質をみたしている
この集合をwordの頭文字をとって$W$と名付けます。
編集距離を求める関数を $d$ とすると、上記の例では$W$の要素"dog"、"doing"をとって$d("dog", "doing") = 2$と書けます。
この$d$は集合$W$上の2つの要素を非負実数値にする関数です。そこでこの関数$d$が距離関数の定義をみたすことを確認してみましょう。
編集距離が距離関数であることの確認
$W$上の2つの要素を$x$、$y$とします。$x$、$y$はそれぞれ"dog"や"doing"のような単語です。
まず1つ目の$d(x,y)\geq 0$を確認します。$d(x,y)=0$は、文字列$x$と$y$が同じときのみに成り立ち、$x$と$y$が異なる文字列のとき$d(x,y)>0$となります。したがって、$d(x,y)\geq 0$が成り立ちます。
次に2つ目の$d(x,y)=d(y,x)$を確認します。挿入の代わりに削除、削除の代わりに挿入の操作をすれば、$x$から$y$への変形と$y$から$x$への変形は同じ操作回数で変形可能です。したがって、$d(x,y) = d(y,x)$が成り立ちます。
最後に3つ目の$d(x,y) \leq d(x,z) + d(z,y) $ を確認します。$z$は$W$の要素とします。$x$から$y$に変形する操作回数と、$x$から一度$z$に変形し、それから$z$を$y$に変形する回数を比較すると、後者の回数が大きくなります（$z$が$x$から$y$に変形する途中の文字列なら同じ回数）。したがって、$d(x,y) \leq d(x,z) + d(z,y)$が成り立ちます。
以上より、編集距離 $d$ は距離関数の定義をみたしているため、集合$W$上の距離関数であることがわかります。
上記のように編集距離は距離の本質的な特徴を備えており、この距離関数をもって単語全体の集合は距離空間となります。
単語の集合という一見すると奥行が全く感じられない集合に、距離を導入することによって、空間的な広がりを感じられるようになったのではないでしょうか。
距離空間の先に待っているのは
この記事では、ただの単語の集まりに編集距離という距離関数を定義することで距離空間を構成しました。
ユークリッド距離やマンハッタン距離のような直感的な「距離」がもつ共通の性質をもつ関数を、逆に距離関数の定義とすることで無味乾燥な集合に奥行を感じる指標を取り入れることができました。
さらに議論を突き詰めれば、特殊な空間を構成して数値計算などに応用できることがあります。
例えば、機械学習の分野では、word2vecなどで扱うユークリッド空間を双曲空間と呼ばれる空間にマッピングし、双曲空間に定義される距離関数を用いて計算することで、計算量が大幅に削減できる事例などがあります（参考：異空間への埋め込み！Poincare Embeddingsが拓く表現学習の新展開）。
距離空間を知ることは、より深くて面白い分野の第一歩を踏み出すことにつながるのです。
さいごに
少し毛色の変わった話題をお届けしました。
編集距離の求め方は、「動的計画法」と呼ばれるアルゴリズムを使って求めます。したがって、「距離空間とはなにか」を知らなくても編集距離を求めることができます。
ともするとプログラミングをする上で不要なのだから、その知識は必要ないことだ、と言われれば、そうなのかもしれません。
ですが、編集 距離 という言葉を使われているときに、「普通の距離（つまりユークリッド距離やマンハッタン距離）と何か似ているのかな」とか考えてみると、好奇心の幅が広がり、知識に深みのあるプログラマーに近づくことができると思います。
読者の方の新しい興味を刺激することができていれば幸いです。ありがとうございました。