相関係数･COS類似度

（１）COS類似度


文章の類似度を測る尺度としてCOS類似度がある。クラスタリングの素性だとかに使われるようで、簡単な式で算出できるのでとっても便利である。
\HUGE{\frac{\bf{x}\cdot\bf{y}}{|\bf{x}||\bf{y}|}}=\cos{\theta}

具体例で考えてみる。
文書x:「私は本格的に頭の悪い生徒です。」
文書y:「私は本当に頭の良い生徒です。」


この二つの文書は類似しているだろうか？
ぱっと見似たような文章だがまあ、言いたいことは違うし逆だ。（この文書の類似度を求めることに意味はあるだろうか？）


このとき、文書を単語1語の生起回数を要素としたベクトルにしてみよう。（ベクトルと書いたがこれを単純に、要素を並べたもの、と思ってもこの範囲では問題ない。と書けば予防線が張れるのか。）
まず全文書の単語をならべたベクトルを用意する。


{私,は,本格的,に,本当,頭,の,悪い,良い,生徒,です}


読点は今要らない情報ではないので無視する。
さて、このベクトルに生起回数を入れてみよう。
文書x:{1,1,1,1,0,1,1,1,0,1,1}
文書y:{1,1,0,1,1,1,1,0,1,1,1}
となる。ここでcos類似度を計算すると、0.77777だ。まあ、似ているようだ。一応、式は
\HUGE{\frac{\bf{1+1+0+1+0+1+1+0+0+1+1}}{\bf{\sqrt{9}}\bf{\sqrt{9}}}}こんなもんです。


分母はノルムというやつで、全ての単語生起回数を2乗して足し、平方根をとるという計算になる。
その結果、分母の値は9となった。また、分子はそれぞれの要素をかけて足す演算で、どっちかが0であれば足されずに終わる。
だから、分子は分母に比べて必ず小さくなる。


そういうわけで、COS類似度は1以下の値になる。今回は生起回数を対象にしたのでCOS類似度の値が負になることはない。


しかし、「出現していたら1,出現していなければ-1」という使い方ならば-1になることもあるので、COS類似度の範囲は-1〜1ということを一般にしておくと問題が起きない。
まあ-1〜1だろうと0〜1だろうと、生起回数を対象にしたような扱いなら意味に大した違いはでないだろう。（普通にやれば0〜1の範囲になるとは思うんだけどなあ。）


当たり前のことを書いておくと、別に二つの文が意味的に似ている（伝えたい情報が似ている）ことがCOS類似度によって求められるわけではなく、あくまで見た目似ていることがわかるだけだ。
レポートのパクリチェックとかは割と特異で大きい文書を扱うので、似ているとパクリ確率は非常に高いだろう。しかし、今のような小さい文書などでは、意味のある結果が出るとは限らない。
対象の文書にこの指標が効を奏するか、よくよく考えなければならない。（という自分への戒め）


（２）相関係数


相関係数は二つの「確率変数」の間の関係度合いを測る指標だ。そして、その二つの確率変数には正規分布を仮定する。
正規分布ということは、平均と分散があるということで、この二つを使って相関係数は求められる。
意味としては、値が1か-1に近いほど関係があり、0であれば二つの間に関係がない、ということになる。（場合によるが、大雑把にはこうなる。）
ー1ならば反対の関係があるということだ。（xが増加するとyが減少する、など）
なお、回帰分析からも相関係数の式を垣間見ることができるが、それは今度メモにする。で、式は下記。

\HUGE{\frac{\sum_{k=1}^{n}(x_{k}-\overline{x})(y_{k}-\overline{y})}{(\sqrt{\sum_{k=1}^{n}(x_{k}-\overline{x})^{2}}\sqrt{\sum_{k=1}^{n}(y_{k}-\overline{y})^{2}}}


でっかいためか厳しい式に見えるが、COS類似度との違いは平均を使うかどうかだけだ。
COS類似度では単純に文書の生起回数を使っていたが、今回はそれぞれのデータからそのデータの平均を引くものを使う。


せっかくだから上の文書ベクトルに対して相関係数を求めてみよう。あまりの意味の無さに愕然とするだろう。
まず平均だが、文書xは回数の平均が9/11、文書yも9/11だ。それぞれのデータから平均を引けば、
文書x':{ 2/11, 2/11, 2/11, 2/11, -9/11, 2/11, 2/11, 2/11, -9/11, 2/11, 2/11 }
文書y':{ 2/11, 2/11, -9/11, 2/11, 2/11, 2/11, 2/11, -9/11, 2/11, 2/11, 2/11 }
というベクトルが出来上がる。なお、データの平均からの差は偏差と呼ばれるので、これを偏差ベクトルと呼ぶことにする。


これを使えばあの厳しい式はすっきりする。
\HUGE{\frac{\bf{x'}\cdot\bf{y'}}{|\bf{x'}||\bf{y'}|}}


どうだろう。偏差ベクトルを使えばCOS類似度と式は全く同じだ。
計算してみると、値は-46/190 = -0.2421となる。
ー0.2421というと殆ど無さそうな負の関係があるということだが、この文書の間には何の意味もない値である。
無理やり意味付けするならば、1ならば全く同じ文書、-1のときは二つの文書での出現単語が全て違う文書となる。0はどっちかで全ての単語生起回数が1のときとか？
それ以外の値は色々と考えてみたがどうも場合によるとしか言えない。偏差を使うことは文書ベクトルに対してほとんど意味が無さそうだ。


考えるまでもなく、相関係数を求めることは全く意味の無い結果に終わった。
相関係数を求めるということは、文書ベクトルxが正規分布n1に従い、yが正規分布n2に従う、ということを仮定する。つまり、基本的興味は「文書間の出現単語頻度の分布の関係」になる。
COS類似度でも同じだが、「は」が2回、「本格的」が1回、などの単語が何であるか、といった情報については見ない。身長や体重計測で「佐藤君の身長が165cm」、といった見方をしないのとある意味同じことだ。
すると、今やっていたことは「ある文書中に出てくる出現単語の頻度は、もう一つの文書中に出てくる出現単語の頻度と関係があるか？」という問いとなる。
「ある文書」と「もう一つの文書」の選び方が定まれば関係が出てくるかもしれないが、今は選び方を考えていない以上、二つの文書は「全文書という母集団から（ランダムに）抽出した二つの標本文書」という見方になり、データ群xとデータ群yは同じ母集団に従うため、求めているのは「文書における出現単語頻度の偏差積（ノルムで割ったもの）」ということになってしまう。（つまり、意味が無い。）


（３）まとめ


計算法上では、COS類似度と相関係数の違いはベクトルに偏差を使うか使わないかにある。
そのせいか、自分にはCOS類似度は相関係数とやっていることが同じにしか見えなかった。
そこで、相関係数を文書ベクトルに対して求めてみるというアホなことをしてみたが、偏差を使うことの無意味さを味わってしまったのだ。
恥ずかしいがせっかくなのでメモとして残しておく。
次は相関係数と回帰分析についてメモしてみよう。

Stirlingの公式[5]

（６）まとめ

取りあえず纏めておこう。
まず、n!は評価が難しいので対数に直して評価してみるのだった。
しかし、正確に積分を行うと1/2の範囲でやるため、式がややこしくなった。これが最後に+1/2が指数に出てくる理由となる。
積分で出てくる誤差も一応は評価してみたが、難しいのでμ(n)という関数で収束部分を吐き出して別に考えよう、ということになった。
最後はウォリスの公式に当てはめて、The End。

さて、巷ではStirlingの公式は色々と形があるようで、誤差をあまり考慮しないものもある。
たとえば、
n^{n}e^{-n}
これは非常に覚えやすいのだが、誤差をまるで無視しているので精度はあまりよくなさそうだ。
\sqrt{2\pi}の2.5や、n^{1/2}をまるで考えないのだから、今導いた公式よりは値が小さくなってしまう。
まあ、どうせ桁数が尋常じゃなくなるのだからnが大きければ実用上問題無い程度なのかもしれない。
ただ、n^{1/2}は収束しないからきついぞ、という気はする。

Stirlingの公式[4]

（４）誤差を含めて

前に書いたとおり、δの評価は（自分にとって）難しい。時間があるときにやることにした。（俺流なやり方でやってみたが合ってる気がしない・・）

さて、δnはnが無限のときある値に収束する。（後で計算してみる。）つまり、
\delta_{n}+\mu(n)=\delta
であり、ミューについては\lim_{n\to\infty}\mu(n)=0
となる。0に収束する部分とそうでない部分を分けておくのだ。
さて、長くなってきたが先ずlogで計算したものをeに戻そう。
n^{n-\frac{1}{2}}e^{-n}e^{1-\delta_{n}}
とした。
次に、\delta=\delta_{n}+\mu(n)
を指数のδnに代入しよう。
すると、
e^{1-\delta}n^{n-\frac{1}{2}}e^{-n}e^{\mu(n)}
となり、ここでe^{1-\delta}=aとする。
このaが漸近的にどうなるのか？ということがこの公式の精度に大きく貢献する。


（５）Wallisの公式

ウォリスの公式は非常に面倒くさい形をしており、数学好きにはたまらないのだろうが、一般人には避けたい存在だ。
その意味するところは正直いまだわからないが、Stirlingの公式にたどり着くためには必要な式だ。
\sqrt{\pi}=\lim_{n\to{\infty}}\frac{(n!)^{2}2^{2n}}{(2n)!\sqrt{n}}


Wallisの公式に先ほどの式をあてがってみよう。
n!のところに単純に代入したらいい。

\sqrt{\pi}=\lim_{n\to{\infty}}\frac{(an^{n-\frac{1}{2}}e^{-n}e^{\mu(n)})^{2}2^{2n}}{2na(2n)^{2n-\frac{1}{2}}e^{-2n}\sqrt{n}e^{\mu(n)}}

e^μ(n)は無限にしたとき1になるので消してしまおう。それ以外を丁寧に約分していけば次の形になる。（幾度か失敗した経緯から「丁寧」という言葉が出てきた。）
\frac{a}{\sqrt{2}}

何ということでしょう。といってしまうほどにシンプルだ。これがルートπになるんだから、
a=\sqrt{2\pi}
となる。後はもともと(n-1)!を計算していたことを思い出して右辺にnをかけるだけだ。
こうしてaも遂に求まり、かくしてn!とStirlingの公式はだんだんと近づく。（漸近）

最初の
n! \sim \sqrt{2\pi}n^{n+1/2}e^{-n}
が無事求められた。
だが、誤差の評価という問題が残っている。デルタとして有耶無耶にされたあれらを時間があるときに考えてみよう。

Stirlingの公式[2]

続き。

(3)log(n)
目的はlogn!を計算することだった。
普通に考えて
\int_{1}^{n}\log{x}dx・・・（１）
を計算したらいい。のだが、まず真面目に1個の項での積分を考えて、
\int_{n+\frac{1}{2}}^{n-\frac{1}{2}}\log{x}dx=\log{n}
とする。計算したい箇所の周囲1/2の範囲を計算する、という寸法。直感的。

例えばx=6のとき(log6)を計算するなら

古風にペイント流。

さて、これを1〜nまで足せばいいのだが、図にあるように誤差も評価する必要がある。
また、当然ながらlog1=0なので1はいらない。
よって、log2+log3+・・・log(n-1)+1/2logn+δ
を計算することになる。誤差をδであらわし、最後のnは左側の1/2を計算するだけでいいことに注意。
この計算は（１）と等しく、また（１）は部分積分法によって、
n\log{n}-n+1
となるから、
n\log{n}-n+1=\log{2}+log{3}+...log{(n-1)}+\frac{1}{2}\log{n}+\delta
といえる。今、log(n-1)!を計算したかったのだから、右辺側のn-1のところまでを使う。1/2lognとδを移項して、
\frac{1}{2}n\log{n}-n+1+\delta=\log{(n-1)!}
ができあがる。後は前に書いたように底をeに戻せば前回の式ができる。


上で誤差をδとしてきたが、誤差δはlognの各nで違うので当然\delta_{n}とすべき。続きは明日。

Stirlingの公式[1]

Stirlingの公式
n! \sim \sqrt{2\pi}n^{n+1/2}e^{-n}

解析概論から普段気になるn!について。にしてもこの本難しい・・。


例:n=6のとき
sqrt{2\pi}=2.5
6^{6+1/2}=114283
e^{-6}=0.00247
(=は≒で読み替える。windows電卓で適当な桁まで読んで後ろの桁はすっ飛ばした。正確に計算することは目的じゃない。という言い訳。）
全部かけると705くらいで、正解の720に近いことがわかる。



目的：n!の近似計算
この計算は当然面倒で、近似式が知りたい。のだが込み入って難しそうなので証明から考えてみる。
コンピュータ分野ではアルゴリズムの計算量評価によく使われ、最悪な計算量の象徴。巡回セールスマン問題が一番有名？
ところで、このような最悪の例にセールスマンが選ばれてしまったのは現実社会の境遇に照らし合わせても偶然ではないんだろう。


(1)\simとは
「漸近する」という意味
漸近する、とは　　lim_{n \to \infty}\frac{a_{n}}{b_{n}}=1
というように、数が限りなく大きいとき二つの数列が等しくなるということ。
例えば、と言いたいけどうまい例が見当たらない。



(2):対数を考える。
n!を対数で考えるとどうなるだろうか。積を和で考えれるので多少は楽になるだろう。
ここで、ガンマ関数と同じようになるために(n-1)!を考える。
すると、\log{(n-1)!}は=(n-\frac{1}{2})\log{n}-n+1-\deltaとなる。
そして対数を元に戻せば、
n^{n-\frac{1}{2}}e^{-n}e^{(1-\delta)}
いきなり1/2が出てきたりデルタがあったりするが、順を追ってみよう。


次は明日あたりに。