前回、2つの要素が等しいか否かということに関して議論してきました。今日は、等しくない場合の話、2つの要素がどれくらい異なるのかに関して議論していこうと思います。
誰かに近づきたい、何かを達成したいという目標があるとき、その目標と自分との違いを知ることが非常に重要になってきます。前に、人生の生命時間を計算しましたが、目標に対しては、きちーっとした計画を立てて最短時間で達成できるのが一番よいです。
いきなり議論を進めていく前に、僕の学生時代の話をしようと思います。
約1割しかいない男女比は、男子学生のもて悩み種。しかし、女子学生はどうか。女子学生は、いつも学年3番以内の勉強のできるイケメン男子学生の周りにいて、だいたいみんなよくできる。僕を含める一部の男子学生のように、女子学生は落ちこぼれない。口癖はいつも「(テスト勉強が)やばい。やばい。」で、勉強のできる男子学生ホイホイのできあがりですね。
やっぱり、理系大学の生態系のなかで、培った地位、まさに、ニッチ(niche)。
世の中ポジティブシンキングとか言われていますけど、彼女たちには当てはまりませんね。彼女たちは、ちょっとネガティブ、「ちょいネガ」とでもいいましょうか。「やばい」ということが生きる目的関数の最大化です。
上の例では、女子学生が、勉強のできるイケメンというわらじを吐いて、よく勉強ができるようになっています。自分だけで勉強していると「やばい」ということが解っている。目標と現在地の違いがよく解っているんですね。そして、目標と現在地の違いが解っているからこそ、戦略を練ることができる。僕のようにポジティブシンキングでいって華々しく散るか、女子学生のようにちょいネガで行って成功するかです。
では、目標と自分との違い、つまり2つの要素の違いはどのように測っていくのかです。結論から言ってしまうと、基本的に用いるツールは2つ覚えておけばよくて、距離関数を使うか、内積を求めるかです。後者に関しては、長くなってしまうので、また今度。今回は、前者の距離関数で2つの要素の違いを求めていきます。
きちーっと定義を知ってから距離関数を見ていくことにしましょう。
まず、距離関数は、2つの引数 x, y ∈ X(ある集合のなかの任意の2つの要素) を取る関数で、 d(x, y) と書きます。関数を評価すると実数が返ってきます。つまり、距離を実数として評価するのが距離感数です。
次に、細かい定義が4つ続き
1. 非負性: d(x, y) ≧ 0
2. x = y と d(x, y) = 0 は同値
3. 対称性: d(x, y) = d(y, x)
4. 三角不等式: d(x, y) + d(y, z) ≧ d(x, z)
(ただし、x, y, z ∈ X)
が成り立つことが d(x, y) が距離関数であるために必要です。順番に説明すると、まず1です。非負性というもので、距離はマイナスになることはありません。2は、当然同じだったら距離も0というもの。距離が0だったら、当然同じですよね。3は、ひっくり返しても同じだよね。4は、中学と高校でやるはずです。三角形を書いて考えてみてください。
3に関しては、当たり前と思う人多いと思いますが、注意が必要です。例えば、恋愛に関していうと、自分から相手を見て距離は小さいと思っていたとしても、相手から自分は距離無限大という時があります。僕らの考えている恋愛に関する距離は必ずしも距離関数を構成しないのです。
絶対値ってなんでしょうか。考えてみてください。
答えられない生徒は論外として、受からない生徒は「マイナスをプラスにした」と答えます。では、どう応えるべきなのか?
「(与えられた値の)数直線上における原点からの距離」というのが模範解答になります。絶対値は距離を求める関数という感覚が無いとこの世の中はもちろん受験でも生きていけません。距離を求める最も簡単な関数が絶対値です。
そして、マンハッタン距離というのは、絶対値(||)を利用した距離関数です。定義(2次元空間の場合)は簡単です。
,p_2=(x_2,y_2))
を2次元空間の中の点として、マンハッタン距離は
となる。
これは、碁盤目状の道路を歩いて家
から職場 
に行くときの距離というイメージができるかと思います。横に何マス歩いて縦に何マス歩くのかという話です。簡単ですね。こちらは、何次元でも使うことができます。
プログラミングの世界では、演算のコストが低いので、よく用いられる方法です。この点では、次のユークリッド距離よりも優れています。今後とも使ってあげてください。
=%5Csqrt%7B(x_1%20-%20x_2)%5E2%2B(y_1-y_2)%5E2)
見難くてすみませんが、ピタゴラスの定理を使った p1 から p2 の求め方になります。こちらも、何次元でも使うことができます。
ゲームなどで、厳密に距離を図りたいときは、これを使います。ですが、単に距離の比較の場合、二乗根(ルート)の計算は無駄な場合が多いので、二乗和%5E2%2B(y_1-y_2)%5E2)
を用いることも多いです。この場合、三角不等式が成り立たなくなるので、距離関数ではなくなりますが、テクニックとして知っておいてください。
もちろん、計算を楽にするためには、ユークリッド距離ではなくて、マンハッタン距離を採用できるのであれば、その方が良いです。ユークリッド距離はいつでも万能ということはありえません。距離と言われると何でもかんでもユークリッド距離を思いつく人は注意してください。
例えば、
「あいうえお」と「あいうえお」のハミング距離は 0
「あいうえお」と「かいうえお」のハミング距離は 1
「あいうえお」と「えぬじげん」のハミング距離は 5
のようにハミング距離は簡単に求められます。ハミング距離が1の情報は、ハミング距離が2の情報よりも間違いが少ない正確な情報ということになります。間違いが少なければ、ひょっとすると元の情報に戻せるかもしれません。
これを応用したのが符号理論で、通信における多少のハミング距離を情報の誤りの程度として、誤りを検出したり訂正できるようになったのが今の世の中であります。符号理論は、n次元の得意とする分野でもあります。
ノード間のエッジの数を数えたものがグラフ距離となります。距離が小さいと関連性が非常に高く、近いということになります。
SNSでは、人同士をグラフのノード、友達関係をエッジとして管理しています。自分の友だちを検索するときは、距離1のノードを検索し、友達の友達は距離2のノードを検索することになります。自動車のナビも有向グラフというものを使って、最短経路問題の部分最適解を求めるように作られています。
グラフ理論におけるグラフ距離は、現代の世の中に無くてはならないものだということがお解りいただけたのではないでしょうか。
誰かに近づきたい、何かを達成したいという目標があるとき、その目標と自分との違いを知ることが非常に重要になってきます。前に、人生の生命時間を計算しましたが、目標に対しては、きちーっとした計画を立てて最短時間で達成できるのが一番よいです。
いきなり議論を進めていく前に、僕の学生時代の話をしようと思います。
東工大の女子学生の生態系
学生時代を思い返すと、東工大生(東京工業大学の学生)の特に女子学生は、目標を定めたときの努力の最適化が半端ではないほど上手かったです。まず、前提として、東工大の男女比(pdf)がここから見られます。ご参照ください。学生のうち、約1割強が女子学生ということになります。(注: 東工大は男子校ではありません。)約1割しかいない男女比は、男子学生のもて悩み種。しかし、女子学生はどうか。女子学生は、いつも学年3番以内の勉強のできるイケメン男子学生の周りにいて、だいたいみんなよくできる。僕を含める一部の男子学生のように、女子学生は落ちこぼれない。口癖はいつも「(テスト勉強が)やばい。やばい。」で、勉強のできる男子学生ホイホイのできあがりですね。
やっぱり、理系大学の生態系のなかで、培った地位、まさに、ニッチ(niche)。
世の中ポジティブシンキングとか言われていますけど、彼女たちには当てはまりませんね。彼女たちは、ちょっとネガティブ、「ちょいネガ」とでもいいましょうか。「やばい」ということが生きる目的関数の最大化です。
上の例では、女子学生が、勉強のできるイケメンというわらじを吐いて、よく勉強ができるようになっています。自分だけで勉強していると「やばい」ということが解っている。目標と現在地の違いがよく解っているんですね。そして、目標と現在地の違いが解っているからこそ、戦略を練ることができる。僕のようにポジティブシンキングでいって華々しく散るか、女子学生のようにちょいネガで行って成功するかです。
では、目標と自分との違い、つまり2つの要素の違いはどのように測っていくのかです。結論から言ってしまうと、基本的に用いるツールは2つ覚えておけばよくて、距離関数を使うか、内積を求めるかです。後者に関しては、長くなってしまうので、また今度。今回は、前者の距離関数で2つの要素の違いを求めていきます。
距離関数
距離関数といっても様々な関数を作ることができます。適切な関数を構成するか選択できるかでないと、当然、僕らの目標までの距離を求めることはできないわけです。周り見回してみてください。結構、変な距離関数持っちゃっている人いると思います。きちーっと定義を知ってから距離関数を見ていくことにしましょう。
まず、距離関数は、2つの引数 x, y ∈ X(ある集合のなかの任意の2つの要素) を取る関数で、 d(x, y) と書きます。関数を評価すると実数が返ってきます。つまり、距離を実数として評価するのが距離感数です。
次に、細かい定義が4つ続き
1. 非負性: d(x, y) ≧ 0
2. x = y と d(x, y) = 0 は同値
3. 対称性: d(x, y) = d(y, x)
4. 三角不等式: d(x, y) + d(y, z) ≧ d(x, z)
(ただし、x, y, z ∈ X)
が成り立つことが d(x, y) が距離関数であるために必要です。順番に説明すると、まず1です。非負性というもので、距離はマイナスになることはありません。2は、当然同じだったら距離も0というもの。距離が0だったら、当然同じですよね。3は、ひっくり返しても同じだよね。4は、中学と高校でやるはずです。三角形を書いて考えてみてください。
3に関しては、当たり前と思う人多いと思いますが、注意が必要です。例えば、恋愛に関していうと、自分から相手を見て距離は小さいと思っていたとしても、相手から自分は距離無限大という時があります。僕らの考えている恋愛に関する距離は必ずしも距離関数を構成しないのです。
マンハッタン距離
大学受験の塾講師が生徒に対して受かりそうか否かを判定する簡単な質問がいくつかあるのですが、「絶対値とは結局何?」というのがその1つです。絶対値ってなんでしょうか。考えてみてください。
答えられない生徒は論外として、受からない生徒は「マイナスをプラスにした」と答えます。では、どう応えるべきなのか?
「(与えられた値の)数直線上における原点からの距離」というのが模範解答になります。絶対値は距離を求める関数という感覚が無いとこの世の中はもちろん受験でも生きていけません。距離を求める最も簡単な関数が絶対値です。
そして、マンハッタン距離というのは、絶対値(||)を利用した距離関数です。定義(2次元空間の場合)は簡単です。
となる。
これは、碁盤目状の道路を歩いて家
プログラミングの世界では、演算のコストが低いので、よく用いられる方法です。この点では、次のユークリッド距離よりも優れています。今後とも使ってあげてください。
ユークリッド距離
距離と言ったら、これでしょう。ユークリッド距離は皆さんが親しんでいるものです。地図座標における直線距離とか言うのがこれですね。見難くてすみませんが、ピタゴラスの定理を使った p1 から p2 の求め方になります。こちらも、何次元でも使うことができます。
ゲームなどで、厳密に距離を図りたいときは、これを使います。ですが、単に距離の比較の場合、二乗根(ルート)の計算は無駄な場合が多いので、二乗和
もちろん、計算を楽にするためには、ユークリッド距離ではなくて、マンハッタン距離を採用できるのであれば、その方が良いです。ユークリッド距離はいつでも万能ということはありえません。距離と言われると何でもかんでもユークリッド距離を思いつく人は注意してください。
ハミング距離
ハミング(Hamming)距離というのも重要な距離です。書き言葉、話し言葉において差分の大きさを取るための簡単な方法がハミング距離となります。例えば、
「あいうえお」と「あいうえお」のハミング距離は 0
「あいうえお」と「かいうえお」のハミング距離は 1
「あいうえお」と「えぬじげん」のハミング距離は 5
のようにハミング距離は簡単に求められます。ハミング距離が1の情報は、ハミング距離が2の情報よりも間違いが少ない正確な情報ということになります。間違いが少なければ、ひょっとすると元の情報に戻せるかもしれません。
これを応用したのが符号理論で、通信における多少のハミング距離を情報の誤りの程度として、誤りを検出したり訂正できるようになったのが今の世の中であります。符号理論は、n次元の得意とする分野でもあります。
グラフ距離
人同士の距離を測るのに便利なのがグラフ理論におけるグラフ距離ですね。中学高校で勉強したxy座標を図示するためのグラフではなく、ノード(点)と点をエッジ(線)で結んだものをグラフと言います。ノード間のエッジの数を数えたものがグラフ距離となります。距離が小さいと関連性が非常に高く、近いということになります。
SNSでは、人同士をグラフのノード、友達関係をエッジとして管理しています。自分の友だちを検索するときは、距離1のノードを検索し、友達の友達は距離2のノードを検索することになります。自動車のナビも有向グラフというものを使って、最短経路問題の部分最適解を求めるように作られています。
グラフ理論におけるグラフ距離は、現代の世の中に無くてはならないものだということがお解りいただけたのではないでしょうか。
コメント
コメントを書く