Sunday, December 30, 2012

マルコフ行列の中の著者達 Part 2 (7): どの著者がもっとも人々に影響を与えたのか? 実験編


前回までに結果の上位 40 位の表を掲載した.この表を眺めているといろいろと興味深いので,まずは名前をざっとご覧になられると良いと思う.ここからはこれまでに掲載した表などに関しての議論を述べる.

議論

Matrix rank

表 3 では,sink rank や外向きのみのリンクを持つノードを除いたにもかかわらず,matrix は full rank ではないことを示している.これはlink 関係に相互リンクのあるいくつかのグループが存在していることを意味する.このようなグループに関する調査は将来の課題とする.

Japanese Wikipedia template bias


最初,日本の Wikipedia での pagerank 計算結果を見たところ,夏目漱石も芥川龍之介も三島由紀夫も森鴎外も全て 100 位以下であった.また,日本の著者に関する結果はドイツ語と英語の Wikipedia の結果とあまりにもかけ離れていた.調べた所,芥川賞受賞者が圧倒的に上位に入っていることが判明した.これは図 5 に示すように,芥川賞受賞者間では相互リンクが張られるからである.受賞者は全ての他の受賞者からリンクを受ける.これによってpagerank が高くなる.そこで今回の計算では受賞者の相互リンクは排除した.その結果が表 12 である.
Figure 5: Award winner cross link bias problem.
この芥川賞のリンクがどのような bias を生んでいるのか興味ある読者のために,まったく Postprocessing 処理をせずに PageRank を計算した結果を表 13 に示す.表 13 の全員が芥川受賞者である(注 1).実際には芥川賞受賞者全員が上位に来る結果となった.この方式では 101 位に初めて芥川賞受賞者でない三島由紀夫が登場する.Bias を除くと,芥川賞受賞者のうち次の 8 人のみが Top 40 に入っている:大江健三郎,松本清張,吉行淳之介,開高健,丸谷才一,古井由吉,石原慎太郎,安岡章太郎.

図 6 にはこの postprocessing をした場合としない場合の Adjacency matrix を示しておく.Matrix の比較をすると,bias と考えられる内部の相互リンクがパターンとして認識できる.より詳しく見るために,図 6 の下図は,この差をとってみた.差は賞の相互リンクを示している.完全に規則的でないのは,芥川賞以外にもいくつかの相互リンクを行う賞(例えば毎日芸術賞)があるからである.
Figure 6: Adjacency matrices. Japanese authors in ja.wikipedia.org. Top: Removed Navbox bias, Middle: No postprocessing, Bottom: difference (middle - top)
Table 13: Japanese author rank result with Navbox. We think this Navbox causes a bias.
次回は Wikipedia におけるカテゴリ問題に関して議論する.

(注 1): 表 13 において,赤瀬川原平は尾辻克彦のペンネームで芥川賞を受賞している.

Saturday, December 29, 2012

マルコフ行列の中の著者達 Part 2 (6): Japanese author result


日本の著者の結果

Table 10: Japanese author rank result in de wikipedia.
Table 11: Japanese author rank result in en wikipedia.
Table 12: Japanese author rank result in ja wikipedia.

次回はこの結果に関する議論を行う.

マルコフ行列の中の著者達 Part 2 (5): English author result


イギリスの著者の結果

Table 7: English author rank result in de wikipedia.

Table 8:English author rank result in en wikipedia.

Table 9: English author rank result in ja wikipedia. (Our page rank implementation can only find 29 valid authors.)

マルコフ行列の中の著者達 Part 2 (4): German Author result


今回から3回は遂にPageRank(Eigen analysis)結果を示す.

ドイツの著者の結果

Table 4: German author rank result in de wikipedia. ``en'' is en wikipedia's rank result.
Table 5: German author rank result in en wikipedia.
Table 6: German author rank result in ja wikipedia. (Our page rank implementation can only find 31 valid authors.)

Friday, December 28, 2012

マルコフ行列の中の著者達 Part 2 (3): どの著者がもっとも人々に影響を与えたのか? 実験編


今回はどんな matrix が生成されたかについて述べる.

実装

今回以下の 4 つのプログラムを実装した.

  • Link_Vector_Extractor: 作家のリストベクトルを作成する
  • Graph_Extractor: 隣接行列を作成する
  • Page_Rank: PageRank の計算を行う
  • Remapper: PageRank 結果を作家のリストベクトルに map する

実験に利用した計算機環境は CPU: Intel(R) Core(TM) DUO CPU P8400, 2 Cores, OS: 64bit Linux 3.2.0.32, Kubuntu 12.04. である.プログラミング環境としては Python 2.7.3, Beautiful Soup 4.0.2, matlab R2006a, octave 3.2.4を用いた.

Adjacency matrix

Adjacency matrix がどんな形になっているのかを図 2, 3, 4 に示す.この図では隣接関係がある著者間に点がうたれている.
Figure 2: Adjacency matrices. Top to bottom: German authors in de.wikipedia.org, en.wikipedia.org, ja.wikipedia.org.

Figure 3: Adjacency matrices. Top to bottom: English authors in de.wikipedia.org, en.wikipedia.org, ja.wikipedia.org.
Figure 4: Adjacency matrices. Top to bottom: Japanese authors in de.wikipedia.org, en.wikipedia.org, ja.wikipedia.org.
German author の en.wikipedia.org に規則的なパターンが見られるが,これに関しては後に述べる template bias の可能性が高い(注1).また,en.wikipedia.org はもう一つ変わった点として著者への平均リンク数が他に比較してずいぶん高いことがある.ここでのリンク数は Wikipedia 内での著者に分類されている Page にリンクがあるかないかであって,Page 中にある全てのリンク数ではない.例えば,同内容他言語Page へのリンクや,self link,著者ベクトルにないリンクは除外してある.したがって,著者でない人へのリンクが多くあってもそのリンクは数に入っていない.表 2 には matrix にサイズに関するデータを示した.

Table 2: Matrix size, non zero elements, and the average number of  links between authors. Wiki ``en'' means en.wikipedia.org.
これらの matrix は PageRank algorithm [1] に従って rank sink node を除いた.これに共なう link も除いたので,いわゆる dangling link (文献 [1] 2.7節)も除かれている.また,外への link しかない node も除いた.外向きのlink しかない node は PageRank では意味がないが,原論文 [1] では除かれていない.これは原論文では Webを対象にしていたため,外向きの link しかない node であるかどうかを判断することが困難であるからだと思われる.一方で我々の実験では全ての page の規模自体が小さいので これを判断することが可能である.このリンクを除くかどうかの違いはnormalization 部分に出るのだが,normalization はPageRank 値よりも行列の性質を改善するものであり,また PageRank の絶対値は相対値に比較してそんなに重要ではない.我々にとっては,誰の影響力が他の誰かよりも高いかが重要であって,PageRank 絶対値にはあまり興味がない.したがって,normalization の値の違いは我々の目的としてはあまり影響がないと考えられる.これは PageRank の原論文でもそのように考えられている.

この結果縮小された matrix の大きさとその rank を表 3 に示す.

Figure 3: Adjacency matrices: original size, reduced size, and its rank.

次回はようやく Wikipedia 的に誰が重要な著者かの結果である.

注1: この記事を連載していた当時(2012-12-29) 友人の Joerg M. より指摘がありこの箇所を更新した.

マルコフ行列の中の著者達 Part 2 (2): どの著者がもっとも人々に影響を与えたのか? 実験編


実験

実験に用いたデータを表 1 に示す.幸い,どの Wikipedia にも各言語の作家のリストが存在したので,そのリストを Root page として直接リンクされている作家の page を download した.Download に際しては 15 秒に 1 pageのスピードで download し,サーバへの負担にならないように注意した.ここで利用したWikipedia のページのうち,日本語の「石原慎太郎」は例外的にファイルが圧縮されていたため,実験においては展開して利用した.Root page に関しては,他にも候補はあったが,表 1 にあるものを利用した.例えば,ドイツ語 Wikipedia におけ英語の著者として,Liste_englischsprachiger_Schriftsteller ではなく,Liste_britischer_Schriftsteller を利用している.これは私が任意に選んだだけであって,こちらでなくてはいけないという理由はない.なお,実験に使用したファイルは全て 2012-5-30 に download したものである.

Table 1: Experimental data set.

Wednesday, December 26, 2012

マルコフ行列の中の著者達 Part 2 (1): どの著者がもっとも人々に影響を与えたのか? 実験編


今回から Part 2 の実験編である.これまではどうやって最初の疑問,「どの著者がもっとも人々に影響を与えたのか?」について考えてきた.Part 2 ではついにこの答えについて述べる.

著者間の関係の解析

著者グラフの作成方法

著者間の関係を eigenanalysis を用いて実際に解析してみる.まずは著者間の隣接関係を作成する必要がある.もちろん私が手で作成しても良いのであるが,日本の著名な著者だけでもおそらく千人は下らない人数がいるであろう.その著者間の関係を調べ挙げるだけで,私の生涯の趣味の時間では不足するだろう.このグラフのデータを簡単に入手することはできないだろうかと考えた.Web 上のデータで使えるものはないかと考えた時,Wikipedia の Link 関係が良いのではないかと思い,これを利用してみた.

本実験の前提

Wikipedia の著者の Page にある Link 関係は著者間の関係を示していると仮定する.
この前提に異論があることは確実であろう.まず,著者間の関係とは何か,というような問題に戻ることになる.したがって,ここでは著者間の関係はWikipedia の Link 関係として与えられるものと定義する.直感的には,「Wikipedia の筆者らが link を張った著者間には,Wikipedia の筆者らが,著者間に関係があると考えたからである.」と考えても良いと我々は思ったからである.この仮定が認められない場合には以下の議論は全て成立しない.今後,より良い手法が出てきた際にはこの前提を再考する必要があるであろう.

この前提に基き,Wikipedia のリンクの関係を著者間の隣接関係として,固有値問題を解くことにする.

この方法には次のような利点と欠点がある.

利点:


  1. 大量のデータが既に利用可能
  2. ある程度の review がなされている
  3. 人間によって書かれているので,リンク構造には意味があることが予想できる

欠点:


  1. リンク構造の誤りがある可能性がある
  2. 特定の Wikipedia の著者による bias がある可能性がある
  3. Wikipedia の編集方針による bias がある可能性がある

ここで私は大量のデータが既に利用可能であるという利点を最大限に活用することにした.欠点 1 は避けられない問題であり,欠点 2 に関しては現時点で私には学術的に立証された関係グラフを入手不可能なためこれも避けられない.欠点3 には編集上の bias とは何かという定義を考える必要がある.我々が何らかのbias があると考えても,それはいったい何に基づくものなのだろうか.もしbias が主観でしか論じられないものである場合,それは観測者(実験者)の biasになってしまう可能性がある.つまり我々が勝手に Wikipedia の情報を操作することになる危険性を含んでいることに我々は注意する必要がある.とはいえ,この研究は我々の趣味なので,我々がここでどのような操作をしたか明記する限り,問題はないであろう.この問題に関しては,「こういう bias があるようなので,こうやって回避してみた.」という形で述べることになろう.

しかしどの欠点にしても,リンク構造の誤りという考えに帰着できる.これは利用できるデータが一種類しかなければ検出することが難しい.しかし,Wikipedia のデータは一種類しかないのだろうか.いや,あるではないか.日本の著者に関するデータは英語の Wikipedia にもドイツ語の Wikipedia にもある.したがってこれらを比較することでリンク構造の誤りを検出可能かもしれない.もちろん,日本の作家に関しては日本語の Wikipedia の方が情報は豊富である.また,英語の Wikipedia は日本語のWikipedia の翻訳である可能性もある.つまり,これらは独立したデータではない可能性はある.英語の Wikipedia が日本語の Wikipedia の忠実な翻訳である場合,両者には同じ誤りが含まれるために誤りを検出することができない.しかし,完全に独立したデータではないにせよ,完全に同じデータでもないことは確実である.そこで,データセット間に依存関係がある可能性は注意しておく.

Tuesday, December 25, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (24)

Google PageRank

ここで PageRank という手法 [2] を紹介する.Web page 間の影響力というものをどう考えるかについて,Sergey Brin と Lawrence Page という二人は,Web page のリンクを隣接関係として考え,その固有値問題を解くことでWeb の重要度を計算し,それを Web page のサーチの基礎として利用することを提案した.後にこの二人はこのアルゴリズムを使ったサーチエンジンの会社Google を設立する.この論文には,Jon Kleinberg が既に Web 環境を用いて引用関係をリンクによって表現する場合,これを固有値問題として考えることを提案していると記されている.固有値問題そのものは線形代数で基本的なものとして長年研究されてきた.では PageRank そのものは新しくなく,この二人は運が良かっただけではないかというと私はそうは思わない.シンプルでソリッドなアイデアを実際に世界規模で使えるように実装したというところがすごいことだと思う.また,Web のサイズを考えれば,単に固有値を求めるということも単純ではない.

ここでの私の説明は,文献 [9] の書法に従っているが,PageRank の論文[2] ではちょっと違う書法を用いているので注意しておく.
PageRank の論文中, page 4, 2nd paragraph では固有値が,\(R=cAR\)となる c となっている.ここでは\(Mx = \lambda x\) の \(\lambda\)と記述した.したがって,\(\lambda = \frac{1}{c}\) である.
PageRank の論文では,Web のグラフは不完全であるため,そのまま固有値計算をすることはできないことを説明している.たとえば,リンク切れを除くことや,リンクがループしている場合などを挙げ,その対策を述べている.基本的にはユーザがリンクをランダムにクリックしていくが,時々リンクとはまったく関係ないランダムなページにも移動するという考えを用いている.すなわち,PageRank は,Web をスキャンして隣接行列を作成し,リンク切れやループなどの処理を行なった後,ランダムに移動する項を加え,Markov matrix を作成して,固有値問題を解くということになる.もちろん,大規模なWeb であるから,固有値を求める手法にも工夫がなされている.

私はこの論文を読んだ時に,線形代数をかくもエレガントに使うアルゴリズムに心酔した.しかもそれが実用として使い易いというところにも感動した.論文そのもの自体興味深いので一読することをおすすめする.その感動は論文を読んでから何年も心のどこかにあったのだろう.友人からの質問を聞いた瞬間に私はこの論文を思い出した.そこでこのような blog を書いているわけである.現在のGoogle のアルゴリズムはスパム対策など様々な改良がなされていると聞いているが,基本的な考えは同じであると思う.

今回で理論編は終了する.次回からは実験編としてここまでに述べた方法を著者のグラフに適用した結果を述べよう.

References

[2] Sergey Brin, Lawrence Page, ``The PageRank Citation Ranking: Bringing Order to the Web,'' Stanford University, Technical Report, 1998

[9] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition'', Wellesley-Cambridge Press,  2009

Monday, December 24, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (23)


Again, at which station am I?

2つの街の人口の移動の関係を用いて Eigenanalysis に関して説明してみた.これは Berlin の S-Bahn の例に用いることもできる.その方法を示そう.

街の人口の推移と同様,駅間での人の移動ということを考えることができる.隣の駅に行く可能性はどの場合も同じとしてみよう.この場合,隣かそうでないか,つまりトポロジが人の移動形態を決定する.この移動可能性を示す行列は隣接行列のカラムを正規化することで作ることができる.もしある駅が2つの駅に接続されていたならば,各駅に移動する可能性は 1/2 づつになる.同様に3つの駅に接続されている場合には各接続されている駅に移動する可能性は 1/3 である.これは最初に隣の駅に行く可能性をどの駅でも同じと仮定したからである.違うモデルを用いることもできる.駅の隣接行列をこの可能性の行列に各カラムを確率として\(L_1\)で正規化すると,以下のようになる.(細かいことになるが,ここでは確率を考えているので,\(L_1\)ノルムを使用した.)
\begin{eqnarray*}
 \left[
  \begin{array}{cccc}
   1 & 1 & 0 & 0 \\
   1 & 1 & 1 & 1 \\
   0 & 1 & 1 & 0 \\
   0 & 1 & 0 & 1 \\
  \end{array}
 \right]
 \rightarrow
 \left[
  \begin{array}{cccc}
   0.5 & 0.25 & 0   & 0 \\
   0.5 & 0.25 & 0.5 & 0.5 \\
   0   & 0.25 & 0.5 & 0 \\
   0   & 0.25 & 0   & 0.5 \\
  \end{array}
 \right]
\end{eqnarray*}
これが隣接行列から生成された S-Bahn の Markov Matrix である.

octave で各駅に滞在する可能性がどのようになるか計算してみよう.
octave:10> Mb =
[0.5 0.25 0 0; 0.5 0.25 0.5 0.5;
 0 0.25 0.5 0; 0 0.25 0 0.5];
octave:11> [L D] = eig(Mb)
L =
2.88e-01  8.16e-01 -3.77e-1  1.25e-01
-8.66e-1 -4.83e-16 -7.55e-1 -3.25e-16
2.88e-01 -4.08e-01 -3.77e-1 -7.61e-01
2.88e-01 -4.08e-01 -3.77e-1  6.35e-01
D =
Diagonal Matrix
  -0.2500       0       0       0
        0  0.5000       0       0
        0       0  1.0000       0
        0       0       0  0.5000
octave:12> x1 = L(:,3)/ sum(L(:,3))
x1 =
   0.20000
   0.40000
   0.20000
   0.20000
 3 番目のカラムベクトルを使ったのは,3番目の固有値が1だからである.1000回行列 M を適用した場合も計算してみる.
octave:16> Mb^1000 * w
   0.20000
   0.40000
   0.20000
   0.20000
1000 step 移動した際の各駅にいる可能性はそれぞれ 0.2, 0.4, 0.2, 0.2 である.どの駅から出発しても十分長いステップ移動するとこの値に近づくが,それは既に固有値解析によってわかっている.駅のトポロジを思い出してみると(図 7),二番目の駅,Alexanderplatz, に滞在する可能性が高い.この例では Alexanderplatz がハブの役目を果たしているからであるが,ハブとなる駅には他の駅に比較してどれだけ人が集まるのかが計算できた.
Graph example 2. Each node is a train station.

これで基本的な理論は説明した.では著者の重要性とどの駅にいるかはどういう関係なのだろうか.既にこれらは同じグラフというもので示されることを見てきた.グラフという観点を持てば,駅のネットワークを移動してどの駅が重要であるかを計算することと,著者の関係ネットワークを移動してどの著者が重要であるかを計算することは,同じである.人間の解釈は異なるが数学ではこれらは同一である.数学では形が同じものは同じなのである.それは \(2+3=5\) の各数字が牛乳を示していても,ユーロであっても,時間であってもこの計算が正しいことに似ている.2リットルの牛乳と3リットルの牛乳を合わせれば 5 リットルであり,2時間と3時間を合わせれば5時間であり,2 ユーロと3ユーロを合わせれば 5ユーロであるように,数学では同じ形には様々な解釈はあるが,これらは量の加算としては同じものである.グラフを駅のネットワークと見るか,著者間の関係と見るかはただの解釈であった.

このように抽象化することは意味を失うとして人間的でないと嫌う向きもある.この感情は私にはよく理解できる.全てをお金に換算して価値をお金の数字としてしか見ないことは数学的抽象化に似ており,それが全てであるとは思えない.しかし,お金がさまざまな価値と返還できることは,数学的な抽象化が,様々な問題に適応できることにも似ている.つまり未知の問題にも過去の知識が適用できる可能性がある.これは数学を重要な道具にしてきた.個人的には,問題に対してどこまで抽象化を行うかというバランスが大事であると思う.あまりに無理な仮定から抽象化を行うとそれが実際の問題とあまり合致しないにもかかわらず,つまり意味がまったくないにもかかわらず,その答えに意味があるように錯覚してしまうからである.これはお金が全ての価値であると考えると,様々な弊害が起きてくることに似ている.この部分は,(応用)数学者の人間が問われる部分でもある.私は,人間性と数学の関係はあまりないというのは誤解であると思う.問題を解くことは数学者の感情からであることは既に述べたが,数学者の質というものは人間性に関わってくることは私には興味深い.

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (22)

How to compute the eigenvectrors?

これまで,固有ベクトルがどのようなものかは説明してきたが,計算方法については述べてこなかった.実際に固有値ベクトルをどう計算するかのアルゴリズムはここでは述べず,既にあるフリーソフうウェアを使うことにする.octave では eig という関数が教えてくれるのでこれを使おう.

計算してみよう.

octave:34> [L V] = eig(M)
L =
   0.83205  -0.70711
   0.55470   0.70711
V =
Diagonal Matrix
   1.00000         0
         0   0.50000
以前私は固有値が matrix と同じに見えると言った.確かにそうであるが,一つの数字で matrix を完全に表すことはできない.もしできるのならば,matrixは不要になってしまう.実は通常の matrix は複数の固有値と複数の固有ベクトルを持つ.それでも matrix の要素の数 \(n^2\) に比較して \(n\) しか固有値は存在しないのでかなり簡単になる.

この Matrix の固有値は 1 と 0.5, 対応する固有ベクトルは (0.83205,0.55470) と (-0.70711, 0.70711) である.ここでは 0.5 の固有値は無視する.なぜなら,この固有値は Markov matrix がどのように収束するかついては教えてくれないからである.詳しく知りたい読者は Matrix diagonalization について調べてみて欲しい.固有値が 1 の固有ベクトルが,Markov matrix がどのような値に収束するのかを教えてくれる.それを計算して,総人口1000 人の分布を見ると以下のようになる.
octave:38> x1 = L(:,1)/ sum(L(:,1))
   0.60000
   0.40000
octave:39> x1 * 1000
   600
   400
これは前節の結果と一致する.何が違うかというと,固有値を求める方法では,M を 100回掛ける必要がないということである.この位小さな行列では計算機で計算すると計算時間にあまり違いはでてこないが,大規模な行列を扱う場合にはそうではない.その場合には固有値と固有ベクトルを求める効率的な手法が知られているので,それを利用することになるだろう.


次回は隣接行列から Markov 行列を生成する方法について述べよう.駅のネットワークの例では,これによってどの駅にいる可能性が高いのかを計算することができる.そしてそれは実は著者のネットワークの評価と同じである.理論編も大詰めになってきたようだ.


Sunday, December 23, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (21)

前々回には,Berlin の人数と Potsdam の人数がいかなるものであっても,その無限回の操作の結果は一定に落ちつくことを見た.

この Berlin 600 人,Potsdam 400 人というベクトルはこの Matrix にとって特殊なベクトルであって固有ベクトルという名前がついている.このベクトルを図12 の上に書いてみると,図 13 になる.見事に固有ベクトル上に人口の分布が並んでいるではないか.
Figure 12: Population history with various initial conditions.
Figure 13: Population history of Berlin and Potsdam with $y =\frac{400}{600}x$ line.
固有ベクトル \(\vec{x}\)は matrix \(M\) に対して,
\begin{eqnarray*} M\vec{x} &=& \lambda \vec{x} \end{eqnarray*}
となる特殊なベクトルである.ここで \(\lambda\) はスカラ値である.このスカラ値にも固有値という名前がついている.

ここでは次式のように \(\lambda = 1\) である.
\begin{eqnarray*} M \left[ \begin{array}{c} 600 \\ 400 \\ \end{array} \right] &=& \left[ \begin{array}{c} 600 \\ 400 \\ \end{array} \right] \end{eqnarray*}
ここでのベクトルは定数倍しても変化しないので,
\begin{eqnarray*} M \left[ \begin{array}{c} 6 \\ 4 \\ \end{array} \right] &=& \left[ \begin{array}{c} 6 \\ 4 \\ \end{array} \right] \end{eqnarray*}
でもかまわない.この固有値も驚きの数である.左辺と右辺を見ると,一つのスカラ値が Matrix に対応しているように見える.この例での Matrix は 2x2 であったが,Matrix が何千次元であっても,やはり固有値という考えは利用できる.つまりこの固有値は matrix の何らかの特徴を代表している.私は何千次元という大きな matrix を直接理解することはとてもできないが,一つの数なら多少の感じはつかめる.

Matrix の方になにかあるということであるから,M を何度も掛けた時に,どうなっているかを見てみよう.

octave:2> M
   0.80000   0.30000
   0.20000   0.70000
octave:3> M^2
   0.70000   0.45000
   0.30000   0.55000
octave:4> M^3
   0.65000   0.52500
   0.35000   0.47500
octave:5> M^5
   0.61250   0.58125
   0.38750   0.41875
octave:6> M^10
   0.60039   0.59941
   0.39961   0.40059
octave:7> M^100
   0.60000   0.60000
   0.40000   0.40000

M を 100 回掛けた時に出てくるこの数は既にもう見たであろう.

この固有値と固有ベクトルを求める方法についてはこれ以上詳しく述べないが,興味ある読者は文献 [9] を参照して欲しい.ここで何度も掛けて一定の値になるのは,最大の固有値が 1 であったからであり,どんな行列でもそうなるわけではない.しかし,Markov matrix は最大の固有値 1 を持つことが知られている.

また,ここで述べた人口の変移と固有ベクトルの話は様々な文献に登場するものであるが,私の参考にした文献は [6]である.固有値に関しては[8] が面白かった.また,[9] は私の一番好きな線形代数の本である.


References

[6] Yoshio Kimura, ``Fun of linear algebra for freshman (Daigaku ichinensei no tameno omosiro senkeidaisuu,'' Gendai Suugakusha, 1993

[8] Kouji Shiga, ``30 Lectures of eigen problem (Koyuuchi mondai 30 kou,'' Asakura shoten, 1991

[9] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition,'' Wellesley-Cambridge Press,
2009

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (20)


前回,「数学が数について考えなくなる」ことを述べた.これに関しての話をしよう.

ある種のすぐれた文学や音楽の中に時に数学に関する深い洞察をみつけることがある.バッハの音楽にみられる数学的形式,俳句に見られる厳密なパターン,夏目漱石の数学的洞察,そしてそれを感情のゆさぶる粋にまで高める芸術性.数学を学んだおかげで驚くべき一面を見ることができたのは楽しい.

中島敦の「名人伝」という作品をご存知だろうか.私は「弟子」も「李陵」も好きだが,この「名人伝」がとても好きだ.矢の名人が更にその段階を越えていき,名人の中の名人から次の言葉を聞く.「それは所詮射の射というもの,そなたはいまだ不射の射を知らぬと見える.」弓を持って矢を射るのでは所詮弓矢の世界を越えられぬ.その世界を越えるには,弓を持たずして矢を射る世界に入るのである.

この中国の古典を元にした日本の作品を人々に説明すると冗談と思われてしまうことが多々あり,私は説明に苦労する.日本語では数学は数の学問であるが,この時点に来た時,我々は数を忘れる.「数を使って数学をするのでは所詮数の数に過ぎぬ.そなたいまだに不数の数を知らずとみえる.」数学が数の操作ではなく数を忘れ,操作そのもの(演算子)の可能性について論じ始めた時,数学は転換期を迎えた.引き算が生まれた時,人々はできない引き算があることに気がついた.たとえば,3 - 5 は計算できない.これはマイナスの数が発明されるまで問題であった.できない計算があると気がつくと,これまでの演算にも疑いが生じる.足し算はいつもできるのか? 大きな数になると足せないことがあるのかもしれない.知っている特定の数だけではなく,全ての数に関して足し算はできるのだろうか? 割り算にもやはり演算ができない場合があった.3/5 は分数がなければ計算できない.マイナスの数を発明しても 3/5 は計算できない.いったいこれはどこまで続くのか? 一つの演算子だけではない,全ての演算子について考えることはできるのだろうか.一つの数だけでなく,全ての数について考えたように.操作の結果の集合が何であるかについて考えることを提案したガロアの仕事が革命的であったのは,彼が数の数学から,操作の数学へと飛翔したからであると私は思う.計算機科学でも同じである.プログラムで数を与えて数を返す基本的な関数から,関数を与えて関数を返すようなメタプログラミングへと視点を変えることでプログラミングは一歩進化する.先日の Google の doodle はチューリングマシンだったことを覚えている方もおられるだろう[1].Alan Turing はもし万能な計算機,つまり全ての計算機をシミュレートできる計算機が存在したら,何ができて何ができないのかということを考えた.驚くべきことに,彼はそれを今日の電子計算機が発明される前に証明してしまった.このような抽象化の考えがいかに強力であるかの話は尽きない.そろそろMatrix の話に戻るべきだろう.

実際の人数がどうなるかの変化を見る数,ベクトルの部分は実は主ではなく,操作そのものである matrix が実は鍵を握っていた.これが数学が数について考えなくなる部分である.Matrix がどういう結果を生むのかではなく,Matrix そのものにある性質を考えること,それによって全てのデータがどのように振る舞うのかが,一目瞭然となる.Berlin の人口と Potsdam の人口の組合せはかなりのものになる.たとえば,合計 100 万人であれば,100 万通りの可能性がある.この 100 万通りの可能性をわずかの数で示すことができる解析手法(ここでは 1 つのベクトル,つまり2つの数であった),それがここで見た固有値解析である.

次回はまた Berlin と Potsdam の人口の遷移の話に戻ることにしよう.

References

[1] Alan Turing 100th birthday doodle, http://www.google.com/doodles/alan-turings-100th-birthday

Tuesday, December 18, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (18)


前回は隣接行列を拡張した人口の移動の行列を紹介した.今回は前回までの仮定から,人口は未来にどうなるかを予想してみる.

まず,計算する前にいくつかの仮説を立て,それについて考えてみよう.私が数学で楽しいのはいろいろ予想してそれを後で確かめることである.思った通りになると楽しい.

一つ確実なことは総人口は 1000 人のままということである.これは誰も生まれず,誰も死なず,全ての人々はどちらかの街にいる.という仮定から導かれる.
  • 仮説1 Berlin に留まる人の割合(0.8)の方が Potsdam に留まる人の割合(0.7)よりも大きいので,いつかは全ての人が Berlin に移動する.
この仮説は残念ながら正しくないようだ.というのも,Berlin の人口が増加すると,その2割が Berlin から流出するので,900人の時には 180 人が Berlin から流出するが,Potsdam の人口は最初 100 人なので,その 3 割が Berlin に移ったとしても,30 人しか流出しない.実際,一年後と二年後の結果では Potsdam の人口が増加している.
  • 仮説2 この二年の変化を見ていると,Potsdam の人口は\(100 \rightarrow 250 \rightarrow 325\) と推移してきた.しかし,ある時点で,Potsdam の人口が十分多くり,流出の割合も大きいことが効いてきて,Potsdam の人口が減少に転ずるであろう.そうすると,今度は Berlin の人口が多くなるのではないだろうか.これを繰り返すという人口の振動が発生するのではないだろうか.
この仮説が正しいかどうかちょっと計算してみよう.

octave:5> M^3 * p
   637.50
   362.50
octave:6> M^4 * p
   618.75
   381.25
octave:7> M^10 * p
   600.29
   399.71
octave:8> M^100 * p
   600.00
   400.00

どうやらある一定の値に近付いているようだ.100 年たつと Berlin に 600 人,Potsdam に 400 人で落ち着いてしまっている.これを図 11 に示す.
Figure 11: Population history of Berlin and Potsdam.
最初 Berlin 1000 人, Potsdam 0 人だった人口は年数が経つにつれてBerlin 600 人, Potsdam 400 人に近づいていき変化しなくなる.

ここで途中の結果に小数点がでてきてしまった.人数が整数でないというのは,ありえないことだが,年間の移動割合がぴったり 2 割というようなことを仮定したので実際にはありえないことが起こってしまったのだ.しかしこれは無意味なことではない.たとえば,ある都市における人の移動率や出生率などは一年ではそんなに変化するものではないから,今年の移動率や出生率を来年のものとほぼ同じと仮定して未来の計画をたてるのはそんなに無意味なことではない.微分積分という分野ではより良い仮定を考えることができるが,ここではそこまで踏み込まないことにしよう.ここでの去年と同じという仮定には一次の近似という名前がついている.小数は,何ヶ月かBerlin にいて残りを Potsdam で過ごした人がいたというように考えることにしよう.

ところでこれは最初の人口の分布によって変化するのだろうか.つまりこれは matrix の性質なのか,matrix と初期状態の両方を合わせた性質なのだろうか.それを次回は見てみたい.

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (19)

前回,時間の経過に共なって,人口の分布が一定の値に近づくことを見た.最後に考えた問題は,この結果が最初の人口の分布によって変化するかどうかであった.つまりこれはmatrix の性質なのか,matrix と初期状態の両方を合わせた性質なのだろうか.

  • 仮説3 初期条件によって将来は変化して一概には決まらない.例えば,ここまでの例では Berlin に最初 900 人,Potsdam に 100 人いたが,Berlin に最初 0 人,Potsdam に 1000 人いた場合には違った結果になるだろう.

これも計算してみよう.Berlin には最初誰もおらず,1000人全員が Potsdam にいるとしよう.

octave:10> p = [0 1000]';
octave:11> M * p
   300
   700
octave:12> M^2 * p
   450.00
   550.00
octave:13> M^3 * p
   525.00
   475.00
octave:14> M^10 * p
   599.41
   400.59
octave:15> M^100 * p
   600.00
   400.00

なんと,初期条件を変えても結果は同じになってしまった.様々な人数の初期状態でどのように人口が推移するかを示したのが図 12 である.何かのパターンが見える.そしてパターンを考えるのが数学である.
Figure 12: Population history with various initial conditions.
ところで,この Berlin 600 人,Potsdam 400 人というのは特別な数であることに気がついただろうか.移動の人数を計算してみると,
\begin{eqnarray*} \mbox{Berlin} \rightarrow \mbox{Potsdam} &=& 600 * 0.2 \\ &=& 120 \\ \mbox{Potsdam} \rightarrow \mbox{Berlin} &=& 400 * 0.3\\ &=& 120 \end{eqnarray*}
なんとこの人数になった時点で移動量が同じになり,結果として人口は変化しない.こうしてみてみると,最初に与えられた人口ベクトルに依存しない何かがあるということが見えてくるのではないだろうか.つまり,Matrix の中に何かあるということが感じられるのではないだろうか.数学ではまず,対象となる数について考えてきた.そしてその数をどう操作するかということが主な関心であった.ところが,ある時点で数ではなく,その操作を考えるようになる.数学が数について考えなくなるのである.

次回はこの「数学が数について考えなくなる」ことについてちょっと話をしてみたい.

Friday, December 14, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (17)


前回は隣接行列の拡張として Markov matrix を導入した.ここで具体的な Markov matrix \(M\) の例を以下のように考える.
\begin{eqnarray*} M &=& \left[ \begin{array}{cc} 0.8 & 0.3 \\ 0.2 & 0.7 \\ \end{array} \right] \end{eqnarray*} \(M\)の要素の意味を具体的に書くと,以下のようになる.
\begin{eqnarray*}  M &=&  \left[   \begin{array}{cc}    \mbox{Stay Berlin}       & \mbox{P $\rightarrow$ B} \\    \mbox{B $\rightarrow$ P} & \mbox{Stay Potsdam}      \\   \end{array}  \right] \end{eqnarray*}
ここで,\(\mbox{B $\rightarrow$ P}\) は Berlin から Potsdam に引っ越す人の割合,\(\mbox{P $\rightarrow$ B}\) は Potsdam から Berlin に引っ越す人の割合を示す.つまり,一年たって,Berlin に 8 割の人がそのまま Berlin に住み,2 割の人は Berlin から Potsdam に移動する.全ての人に関して考えているので,カラムは合計 1となるように(0.8 + 0.2 = 1.0) なっている.Potsdamの場合も同じである.7割の人は一年後も Potsdam に住み,3割の人がBerlin に引っ越す.この場合にも,カラムは合計 1 となっている.

「何割の人が移動する」ということを示す Matrix なので,要素は全て 0 以上であり,1 以下である.たとえば,マイナスの割合の人が移動するということはない.また,カラムの合計が 1 になることは既に見たが,それは住民全員を考えているからである.これが 1 を越えることがないのは,引っ越す人間の合計が住んでいる人の合計よりも多くなることはないからである.この行列では,今年の状態から来年の状態が完全に決定する.このような性質を持つ Matrix を Markov matrix と呼ぶ.

ここでちょっといろいろと予想してみたい.たとえば,最初に Berlin に 900人の人が住んでいて,Potsdam には 100 人の人が住んでいるとする.合計1000人の人がこの2つの街には常にいるとしよう.一年たったら,人口がどのように推移するか octave で計算してみる.

octave:29> M = [0.8 0.3; 0.2 0.7];
octave:30> p = [900 100]';
octave:31> M * p
   750
   250

二年後には次のようになる.

octave:32> M^2 * p
   675
   325

一年,二年,というのを考えてみたが,では,長い年経た後はどうなるであろうか,ちょっと考えてみたい.とはいえ,何故長い年月を考えるのか疑問に思う読者もいるだろう.長い年月の後というのはつまり未来はどうなるかということである.私はこれに興味がある.

多くの科学がそうであるのだが,知識を集める目的は「未来を知りたい」からである.数学が有用であるのは,数学が未来を知る助けになるからである.人間が未来を知りたいのは,それによって生き延びる可能性を広げてきたからではないかと私は思う.未来などどうでもよいという人々もいるだろうが,そういう人々で構成されている社会は滅ぶ可能性が高い.例えば,冬の食料を心配せずに消費してしまう人々はその年の冬に滅んでしまう.未来に備えて子供達を教育しない社会は発展する可能性が低いと思う.我々が長いこと生き延びてきたのは,未来に興味を持ち,それに対して備えることを学んだからであろう.そうでない人々は生きのびてこなかったので,結果として未来に興味を持つ人々が多いのは自然のように思う.

次回はこれまでの仮定から未来を予想してみよう.

Thursday, December 13, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (16)


Markov matrix

駅の接続関係の例では,自分がいた場所から,何度か電車を乗り継ぐことによってどの駅に到達できるかということが示された.隣接行列は駅間を電車で移動するという操作をしていると考えることができる.ここではもう少し単純化して,移動ということに着目してみよう.

Berlin の中心から S-Bahn で 40 分ほど離れた場所に Potsdam という街がある.街が近いので人の移動も多い.Berlin から Potsdam に引っ越す人もいればその逆もある.これらの街が接続されていると考えれば,隣接行列で示すと以下のようになる.
\begin{eqnarray*}  \left[   \begin{array}{cc}    1 & 1 \\    1 & 1 \\   \end{array}  \right] \end{eqnarray*}
一応この隣接グラフが何を接続しているかを示しておく.
\begin{eqnarray*} \begin{array}{ccc} & \mbox{Berlin} & \mbox{Potsdam} \\ \begin{array}{c} \\ \mbox{Berlin} \\ \mbox{Potsdam} \\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right. & \left. \begin{array}{c} 1\\ 1\\ \end{array} \right] \end{array} \end{eqnarray*}
この行列では到達できるかどうかということだけだったので,どちらの街にも行けるし,どちらの街にも留まることができるという意味ではあまり面白い例ではない.しかし,これに人の移動の割合というものを入れてみよう.

人口を示すベクトルとして,以下を考える.
\begin{eqnarray*} \left[ \begin{array}{c} p_{b} \\ p_{p} \\ \end{array} \right] &=& \left[ \begin{array}{l} \mbox{Population of Berlin} \\ \mbox{Population of Potsdam} \\ \end{array} \right] \end{eqnarray*}
ここでは人口の変化を考えたいと思う.どの年を基準にしても良いのだが,例として2000年を基準にしよう.2000年を時間の起点とする.それを次のように書くことにする.ここで t は経過した年を示し,最初は 0 とする.
\begin{eqnarray*} \left[ \begin{array}{c} p_{b} \\ p_{p} \\ \end{array} \right]_{t=0} \end{eqnarray*}
ここで人口の変化を一年ごとに考える.すると時間 t は k 年後と k+1年後となる.この一年の人口の移動の関係を行列\(M\)で示す.
\begin{eqnarray*} \left[ \begin{array}{c} p_{b} \\ p_{p} \\ \end{array} \right]_{t=k+1} &=& M \left[ \begin{array}{c} p_{b} \\ p_{p} \\ \end{array} \right]_{t=k} \end{eqnarray*}
例を簡単にするために,移動の割合だけで人口は決まるとする.つまり,子供は生まれないし,人は死なないとする.そして人の移動はこの2つの街の間に限られるとする.また,移動の割合は毎年同じとする.

この仮定は大きな制限である.人口の移動の割合は毎年変化するだろうし,子供はもちろん生まれるだろう.また,Berlin から引っ越す人は全てPotsdam に行き,Potsdam から引っ越す人は全てBerlin に行くというのはまったく現実離れしている.しかし,街の数は Matrix の大きさを変化させることで世界中に対応できるし,人の移動以外の変動ももっと複雑なモデルにすることである程度対応はできる.ただ,ここで私が説明したいのは,正確な人口の予測ではなく,このMatrixの性質をどうやって調べるか,つまり解析する方法は何かであるので,できるだけ単純化した例で最初は考えたい.数学の応用を説明する際に,できるだけ良い例を選びたいのだが,複雑な例は説明するのが難しく,簡単な例は現実世界を反映するのが難しい.このように仮定があまりに現実離れしているということで,数学は現実には応用できないのではないかと考えてしまう人もいるのではないかと思う.ここでは,最初は簡単な例から出発し,原理がわかったところで,複雑なものに適用していきたい.

ちょっと前置きが長くなってしまった.人の移動と Matrix の話は次回へと続く.

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (15)


Eigenanalysis

At which station am I?

隣接行列はグラフのトポロジ(接続関係)を示すものだった.しかし行列は接続関係を示すだけではなく,あるベクトルに作用して,他のベクトルを生成することもできた.たとえば,隣接行列を駅ベクトルに作用させることで次にどの駅に到達できるかを計算することができた.もう少しこの計算を続けてみよう.つまり,Weinmeisterstr に最初いるとして,各駅で乗り換えるかあるいは留まるということを繰り返す.その時,各駅に行く方法が幾通りあるかということが計算できる.ステップ数を増やしてみよう.まずは最初に Weinmeisterstr 駅にいる.


\begin{eqnarray*} \begin{array}{|c|c|} \hline \mbox{Station} & \mbox{1 step} \\ \hline \mbox{Weinmeisterstr} & 1 \\ \mbox{Alexanderplatz} & 0 \\ \mbox{Hackescher Markt} & 0 \\ \mbox{Jannowitzbruecke} & 0 \\ \hline \end{array} \end{eqnarray*}


2 ステップでそれぞれの駅に行く方法の回数は,以下になる.

\begin{eqnarray*} \begin{array}{|c|c|} \hline \mbox{Station} & \mbox{2 steps} \\ \hline \mbox{Weinmeisterstr} & 2 \\ \mbox{Alexanderplatz} & 2 \\ \mbox{Hackescher Markt} & 1 \\ \mbox{Jannowitzbruecke} & 1 \\ \hline \end{array} \end{eqnarray*}

3 steps, 5 steps, 10 steps を計算してみる.
\begin{eqnarray*} \begin{array}{|c|c|c|c|} \hline \mbox{Station} & \mbox{3 steps} & \mbox{4 steps} & \mbox{10 steps} \\ \hline \mbox{Wein.} & 4 & 26 & 3862 \\ \mbox{Alex.} & 6 & 44 & 6688 \\ \mbox{Hack.} & 3 & 25 & 3861 \\ \mbox{Jann.} & 3 & 25 & 3861 \\ \hline \end{array} \end{eqnarray*}
どうやら Alexanderplatz に行く方法は他の駅に行く方法よりも二倍ほど多いようだ.これは単なる予想であるが,私はこのように予想することは数学では重要なことだと思う.私にとっては数学はパターンをみつける面白さでもあるからだ.

ここで,Alexanderplatz に入る可能性が step を大きくしていくと他の二倍近くなる,というのは,実は偶然ではない.そういうパターンのようなものがあるということ自体興味あることである.続く section ではこれについてもっと見ていきたいと思う.これまでで,グラフ理論や隣接行列を使っていろいろな性質を見ていくことができることはなんとなく感じてもらえるのではないだろうか.

ここで最初の質問に戻ろう.それは「人間関係を解析するにはどうしたらよいか」ということだった.ここで述べた数学では関係が重要であって,何の関係かは考えていない.つまり駅の間の関係であるか人間の間の関係であるかは区別しない.そのためこれを人間関係に応用することはたやすい.A 駅から B 駅に行くまでには,いくつの駅を通過するのか,と A さんから Bさんまでたどりつくには間に何人の人が介在しているのか,は同じ問題である.この隣接行列の性質を調べることによって,関係に関してさらに調べる方法が存在している.

次回はそれに関して述べよう.

Tuesday, December 11, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (14)


前回に続いて行列の計算についてみていこう.毎回同じ隣接行列を書くのはめんどうなので,駅の接続関係の隣接行列を\(M_{bahn}\)としよう.(Bahn はドイツ語で鉄道の意味)

\begin{eqnarray*} M_{bahn} &= & \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \end{eqnarray*}
\(M_{bahn}\) を一度駅ベクトルに掛けると隣接する駅が計算できる.二度掛けると2ステップで到達できる駅が計算できる.計算結果に出てくる数字は,各駅に到達できる道筋の数を示す.Weinmeisterstr にいるという駅ベクトルに二回\(M_{bahn}\) を掛けた結果は以下にようになる.

\begin{eqnarray*} (M_{bahn})^2 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \end{eqnarray*}
それぞれの要素が意味することは,それぞれの駅に 2 step で行く方法が何通りあるかということである.
\begin{eqnarray*} \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \begin{array}{cccc} \mbox{Wein.} & \rightarrow & \mbox{Wein.} & \mbox{2 通り} \\ \mbox{Wein.} & \rightarrow & \mbox{Alex.} & \mbox{2 通り} \\ \mbox{Wein.} & \rightarrow & \mbox{Hack.} & \mbox{1 通り} \\ \mbox{Wein.} & \rightarrow & \mbox{Jann.} & \mbox{1 通り} \\ \end{array} \end{eqnarray*} 例えば,Wein. から Wein. に 2 step で行く方法は Wein. \(\rightarrow\)Wein. \(\rightarrow\) Wein. (二度同じ駅に留まる) と Wein.\(\rightarrow\) Alex. \(\rightarrow\) Wein (Alex に行って戻る)である.

これを計算するプログラムとして私は octave [6] か matlab をおすすめする.私は個人的には matlab が好きなのであるが,個人の趣味として買うにはあまりに高すぎて手がでない.5 年古いバージョンでいいから,ツールキット込みで 100 Euro 位で売ってもらえれば買うのだが.Mathematica のHome Edition のようなものは出ないだろうか.octave の場合は以下のようになる.(以下,全ての octave の例では出力結果を Page のカラムに収まるように,あるいは空行を削るなどの多少の編集している.)

octave:6> Mb = [1 1 0 0; 1 1 1 1;
                0 1 1 0; 0 1 0 1];
octave:7> w = [1 0 0 0]';
octave:8> Mb * w
ans =
   1
   1
   0
   0
octave:9> Mb * Mb * w
ans =
   2
   2
   1
   1

3回動いた場合はどうだろうか.

octave:10> Mb^3 * w
ans =
   4
   6
   3
   3

3 回動いて,Weinmeisterstr に到達する方法は 4 通りある.以下にそれを示す.ここで WはWeinmeisterstr, A は Alexanderplatz を示す.矢印が3つあるので3回動いた(あるいは留まった)ことを示す.
\begin{eqnarray*}  \begin{array}{ccccccc}   \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} \\   \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} \\   \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} \\   \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} \\  \end{array} \end{eqnarray*}
隣接行列を用いることで,何ステップ後にはどの駅にいることができるかということがわかった.

さて,なぜこうなるのかである.(以下は column space と解空間の関係を理解していることを仮定している.あまり詳しくない人はこの説明を飛ばしてしまってもかまわない.) まず第一に有向グラフの場合には行列をtranspose する必要がある.そうすると各カラムが隣接関係を示している.この場合,グラフはカラム数次元の空間を示すことになる.そうすると column space が示す空間こそが到達可能な場所になる.column space の線形結合を求めることは,すなわちベクトルを掛けることであった.したがって,それぞれの駅に何ステップで行けるかわかっている場合には,どこからスタートしたのかも計算できる.線形システムを解けばよい.しかし,どこの駅からスタートしたかはあまり興味のない問題だと思う.今どこにいて限られた時間でどこまで行けるかという方が通常は知りたいことだからである.

参考文献

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (13)

前回ちょっと言い忘れてしまったことがある.それは隣接行列の対角成分をどうするかである.今回は駅には駅自身が接続されていると考えてもかまわないと思う.Alexanderplatz から Alexanderplatz へ行く場合,必ずどこか他の駅に行かなくてはならない場合には,上記の隣接行列は有用である.しかし.Alexanderplatz から Alexanderplatz へ行く場合,その駅に留まっても良い場合,には以下の隣接行列が使えるだろう.

\begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 1\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 1\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 1\\ \end{array} \right] \end{array} \end{eqnarray*} 隣接行列は接続を示すだけではない.行列の演算によってどの駅からどの駅に行けるかがわかるところがまたすばらしい.たとえば,Weinmeisterstr にいるとして,次にどこに行けるか計算してみよう.Weinmeisterstr にいるということを以下のベクトルで示すことができる.これはいまいる場所を 1 として他を0としたベクトルである.
\begin{eqnarray*} \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} このベクトルを駅を訪れる可能な方法の回数ということを示すベクトルという意味で駅ベクトルと呼ぶことにしよう.この駅ベクトルに隣接行列を掛けてみると,
\begin{eqnarray*} \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} になる.ベクトルの最初の要素は Weinmeisterstr であり,二番目の要素はAlexanderplatz であった.これら2つが 1 になったということは,これらの駅を訪れることができたということである.つまり Weinmeisterstr から1回動いて行ける駅は,Weinmeisterstr と Alexanderplatz である.Weinmeisterstr からWeinmeisterstr に行くには駅に留まっていればよい.これが行列の演算の効果である.知らなかったことを計算によって知ることができた.ここでは接続関係から,どの駅を訪れることができるかが計算できた.

次回は隣接行列のこの力をもっと見ていくことにしよう.

Sunday, December 9, 2012

A pattern girl

D 嬢はちょっと騒がしい.時々自分でお話を作ってそれを大声で話している.さて問題はそれをどこでもすることである.とはいっても私はお話を作ることのできる人を尊敬しているので,あんまり静かにしなさいと言いたくない.でも他の子供が集中できないのは困る.それでなんとか問題に集中して欲しい.

先日の D 嬢は Zahlenhaus で足し算の練習をしていた.初級では足し算と引き算の関係を教えようというので,Zahlenhaus は以下のような計算がある.図 1には Zahlenhaus の例を示している.
Zahlenhaus: 7 = 4 + 3
これを見て以下の計算をする.

\begin{eqnarray*}
 4 + 3 &=&  \\
 3 + 4 &=&  \\
 7 - 3 &=&  \\
 7 - 4 &=&  \\
\end{eqnarray*}

もう一つの例は,

\begin{eqnarray*}
 1 + 6 &=&  \\
 6 + 1 &=&  \\
 7 - 1 &=&  \\
 7 - 6 &=&  \\
\end{eqnarray*}

である.つまりこれによって加算は Commutative であること,簡単に言えば足し算をひっくり返しても同じ \(1 + 6 = 6 + 1\) であることを教え,引き算ではHaus を見ることで,片方を取ってしまうともう片方が残ることを教える.後半では以下のような問題になっている.

\begin{eqnarray*}
 \begin{array}[t]{cccc}
  1 & + & 6 & = \\
  6 & + & 1 & = \\
  &   - &   & = \\
  &   - &   & = \\
 \end{array}
\end{eqnarray*}

D 嬢はこれらの計算をまったく間違えない.

私は答えがあっていることはあんまり興味がない.どう彼女が理解しているのかが面白いことである.そこで,私は尋ねる.「どうやって計算したの? (Wiehast du gerechnet?)」これが一番面白い.まずは子供達はなかなか説明できない.D 嬢は私にどうやったのか教えてくれた.問題は以下のようになっている.

\begin{eqnarray*}
 \begin{array}[t]{cccc}
  1 & + & 6 & = \\
  6 & + & 1 & = \\
  7 & - &   & = \\
  7 & - &   & = \\
 \end{array}
\end{eqnarray*}

まず,最初の答えは三段目にある(赤で示した部分).
したがって,これをコピーする.

次の答えは四段目にある(青で示した部分).それをコピーする.
同様に,以下の色の部分をコピーする.

私は言った「Ausgezeichnet! (すばらしい!)」

数学での重要なことはパターンをみつけることである.物は数えられるというパターンをみつけた時,数学が生まれた.世界の中のパターンをみつけ,それを規則化することが数学である.しかし,そのパターンは吟味され,いつ成立するのかを調べなければいけない.数学の証明でとても起こりそうない特別なケースをとりあげるのは,このパターンがいつ破綻するのかを知りたいからである.限界を知ればいつ使えるのかがわかる.

この練習問題では以下数ページはこのパターンが続く.この後は 8, 9, 10 のZahlenhaus である.彼女はまったく間違えずに,しかしまったく理解せずに全ての問題に答えられるのである.これは研究では時々見られる.何故上手くいくのかわからないが,結果として上手くいっているようだというようなものである.そういうものはあまり研究とは言えないと思うのだが,上手くいく方法があるという経験則の知識の提供という意味はあるかもしれない.

私は彼女に,全て正しい.パターンをみつけることはとてもいいことだ.と言いながら,しばらく考えた.この彼女の方法はすばらしいが,残念ながらいつか破綻する.どうやったら破綻することを納得してもらえるだろうか.

「数学は言葉の一種である.だからそれぞれの行には意味がある.君は数学を使って何かを表現できる.さて,ここにはプラスとマイナスがあるけれども,プラスはどういう意味かな?」

「プラスはたくさんになるという意味です.」

「その通り,でも 1 + 6 はどうして 7 なんだろう?」

「???」

「1 + 6 は 10 ではない.でも 10 は 1 よりも 6 よりもたくさんだ.どうして10 ではないのだろう?どうして 1 + 6 は 7 なんだろう.たくさんだったら 8でも9でも10でもいいのではないだろうか?」

「???」

私はここで Haus に戻って,1 と 6 の丸の数を数えてもらった.彼女は数は数えられるので,これが 7 になることに気がついたようであった.私はプラスは一緒になることであると説明した.一緒になると普通はたくさんになる.だからたくさんというのは正しい.でもたくさんというよりも一緒になるということの方がプラスにはあっている.

次は彼女の方法が破綻する場合を説明したい.私は 1 + 6 に意味があることを説明し,それだけでも答えがあることを説明した.したがって,4つ一組のこの練習問題ではない場合でも 1 + 6 には答えがあることに気づいてもらおうとした.その場合には場所によるコピーできないことがわかってもらえるのではないかと思ったのだ.20分はかかったと思うが,彼女はこれに気がついたのではないかと思う.

しかし,私は 8 歳の子供が,以下のことに一部であるが気がついていたことに驚いた.

\begin{eqnarray*}
 \begin{array}[t]{cccc}
  x & + & y & = z \\
  y & + & x & = z \\
  z & - & x & = y \\
  z & - & y & = x \\
 \end{array}
\end{eqnarray*}

コンピュータでは変数はメモリに格納される.メモリはアドレスという場所を持つ.言語がメモリというものを隠さないようなもの,たとえば C 言語や C++ 言語では,場所と変数の関係を抽象的に理解できるというのは必要なことである.彼女には既にその能力をかいま見ることができる.私は彼女に計算機言語を教えたいと思ったが,まずは足し算ができるようになってからだろう.

Friday, December 7, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (12)

隣接行列とグラフのトポロジ

前回,隣接行列に関して説明したので,今回は隣接行列とグラフの関係を詳しく見ていきたい. 隣接行列はそれを見ればどのように点が接続されているかがわかる.接続されているかどうかだけを気にする場合,数学ではトポロジという言葉を使う.たとえば,Berlin の S-Bahn, U-Bahn の Web site にあるLiniennetz は実際に距離が近いかどうかではなく,電車が駅に行けるかどうかという図である.隣の駅までの距離はあまり関係なく,実際のBerlin の地図の上の線路とはずいぶん異なっている.しかし,トポロジ(=つながりの関係)は正しい. 

図 7 に戻ってみよう.ここには Alexanderplatz に接続されている駅が書かれている.
Figure 7: Graph example 2. Each node is a train station.
この図の隣接行列は以下のようになる.以下の行列には駅名の最初の4文字のみ示した.

\begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 0\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 0\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 0\\ \end{array} \right] \end{array} \end{eqnarray*}

 隣接行列の列の 1 の数はいくつの辺がその点から出ているかに対応する.たとえば,Weinmeisterstr の列だけを取り出すとそれは以下のようになる.

\begin{eqnarray*} \begin{array}{ccccc} \begin{array}{c} \mbox{Wein.} \end{array} & \left[ \begin{array}{c} 0 \\ \end{array} \right. & \begin{array}{c} 1\\ \end{array} & \begin{array}{c} 0\\ \end{array} & \left. \begin{array}{c} 0\\ \end{array} \right] \end{array} \end{eqnarray*}

1 の数は 1 である.つまり Weinmeisterstr から出ている辺の数は 1 である.この数を点の degree と言う.Alexanderplatz の場合,以下に示すように1 が 3 つ あるので degree は 3 である.

\begin{eqnarray*} \begin{array}{ccccc} \begin{array}{c} \mbox{Alex.} \end{array} & \left[ \begin{array}{c} 1 \\ \end{array} \right. & \begin{array}{c} 0\\ \end{array} & \begin{array}{c} 1\\ \end{array} & \left. \begin{array}{c} 1\\ \end{array} \right] \end{array} \end{eqnarray*}

図 7 で点の degree,つまり辺の数がどのようになっているか確認できるだろう. 

次回は隣接行列の演算がどのような意味を持っているかについても紹介しよう.

Thursday, December 6, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (11)

今回は 3人の関係を考えよう.3人の関係では,行列は \(3^2\) の 9 の関係が生じる.以下図 10 の例を用いて説明しよう.
Figure 10: A graph examples represents a relationship among three nodes.
3つの点の関係は以下の 3x3 行列によって示される.
\begin{eqnarray*} \left[ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{array} \right] \end{eqnarray*}
図 10 (a) は点1から点2への矢印がある.この時,行列の\(a_{12}\) 要素が 1 になる.したがって,この場合の隣接行列は以下のようになる.
\begin{eqnarray*} M_{(a)} = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \end{eqnarray*}
以下,図 10 (b), (c) の例を示す.
\begin{eqnarray*} M_{(b)} = \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \end{eqnarray*}
 \begin{eqnarray*} M_{(c)} = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right] \end{eqnarray*}
図 10 (d), (e), (f) は無向グラフである.矢印がないのは双方向の関係を示している.これらは以下のような隣接行列となる.
\begin{eqnarray*} M_{(d)} = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \end{eqnarray*}
\begin{eqnarray*} M_{(e)} = \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \end{eqnarray*}
\begin{eqnarray*} M_{(f)} = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array} \right] \end{eqnarray*}
無向グラフでは関係が対称となるため,行列も対称になっていることに注意して欲しい.左上から右下の対角線に対して同じ形になっている.このような行列を対称行列と言う. ここで行列の形の説明をしておこう.対角成分というのは左上から右下の対角線上にある要素である.3x3 の行列では以下の d 部分である.
\begin{eqnarray*} \left[ \begin{array}{ccc} d & & \\ & d & \\ & & d \\ \end{array} \right] \end{eqnarray*}
対称行列というのはこの対角成分を挟んで同じ値のあるものである.次の行列には a,b,c がそれぞれ2つづつある.対称行列では同記号の部分には同じ数字が入っている.

\begin{eqnarray*} \left[ \begin{array}{ccc} & \mbox{a} & \mbox{b} \\ \mbox{a} & & \mbox{c} \\ \mbox{b} & \mbox{c} & \\ \end{array} \right] \end{eqnarray*}
 \(M_{(f)}\) の対角成分を除いた行列は,以下のように対称になっている.
\begin{eqnarray*} M_{(f)} = \left[ \begin{array}{ccc} & 1 & 0 \\ 1 & & 1 \\ 0 & 1 & \\ \end{array} \right] \end{eqnarray*}

Tuesday, December 4, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (10)

前回の Alice 一人の場合は自分が好きなら1,嫌いなら0,ととても簡単だった.これではあまりに簡単すぎるので,Cheshire catにも登場してもらおう.
Figure 9: Graphs representing relationships between Alice and Cheshire cat.
図 9(a) にはAlice は自分は好きだが,Cheshire を好きではなく,Cheshire は自分も Alice も好きではない場合を示す.その行列は以下のようになる.ここで注意することは登場人物の数の二乗の関係が生じていることである.2人の場合は,\(2^2\),つまり 4 つの関係がある. \begin{eqnarray*} \begin{array}{ccc} & \mbox{Alice} & \mbox{Cheshire}\\ \begin{array}{c} \\ \mbox{Alice}\\ \mbox{Cheshire}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 0 \\ \end{array} \right. & \left. \begin{array}{c} 0\\ 0\\ \end{array} \right] \end{array} \end{eqnarray*}
図 9 (b) のグラフではCheshireは自分は嫌いかもしれないが,物語の中では Alice にはちょっとだけ優しかった気がする.だからCheshire は Alice を好きかもしれない.とりあえず Alice は Cheshireをそんなに好きではないとしよう.その場合の隣接行列は次のようになる.
\begin{eqnarray*} \begin{array}{ccc} & \mbox{Alice} & \mbox{Cheshire}\\ \begin{array}{c} \\ \mbox{Alice}\\ \mbox{Cheshire}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right. & \left. \begin{array}{c} 0\\ 0\\ \end{array} \right] \end{array} \end{eqnarray*}
それぞれの関係を書いてみると以下のようになる.ここで A は Alice を C はCheshire cat を示している.A \(\rightarrow\) A は Alice が Alice を好きである.A \(\rightarrow\) C は Alice が Cheshire を好きであると読む.
\begin{eqnarray*} \begin{array}{ccc} & \mbox{Alice} & \mbox{Cheshire}\\ \begin{array}{c} \\ \mbox{Alice}\\ \mbox{Cheshire}\\ \end{array} & \left[ \begin{array}{c} \mbox{A $\rightarrow$ A} \\ \mbox{C $\rightarrow$ A} \\ \end{array} \right. & \left. \begin{array}{c} \mbox{A $\rightarrow$ C}\\ \mbox{C $\rightarrow$ C}\\ \end{array} \right] \end{array} \end{eqnarray*}

図 9 (c) のグラフは,Alice は自分を好きで,しかもCheshireも好きであり,Cheshire は自分は嫌いだけれども Alice は好きだということを示す.その隣接行列は以下になる.
\begin{eqnarray*} \begin{array}{ccc} & \mbox{Alice} & \mbox{Cheshire}\\ \begin{array}{c} \\ \mbox{Alice}\\ \mbox{Cheshire}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right. & \left. \begin{array}{c} 1\\ 0\\ \end{array} \right] \end{array} \end{eqnarray*}
ここで注意して欲しいのは,互いに好きな関係では有向グラフは無向グラフになり (図 9 (d)),隣接行列は特別な形となる.このような形の行列を対称行列と呼ぶ.Alice と Cheshire の関係をひっくり返しても行列は同じ形になっている.行列でみると左上から右下への対角線に対して対称になる.
さて,二人の関係は一人よりは面白かったがまだ簡単である.次回は三人の時を考えてみよう.そこまで行けば何人の関係でも大丈夫ということが示せるだろう.

Monday, December 3, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (9)

今回は Alice に登場してもらおう.(Alice に登場してもらおうというのは,前回説明したように,私が勝手に決めたことの例) 
図 8 (a) はAlice の点を示し,また辺がないので Alice はAlice 自身を好きではない.図 8 (b) では Alice は Aliceへの辺があるので,Alice はAlice を好きである.
Figure 8: Graphs representing relationships between Alice and herself.
Alice 一人の場合,Alice が自分を好きではない場合(図 8 (a))の隣接行列は次のようになる.
\begin{eqnarray*} \begin{array}{cc} & \mbox{Alice}\\ \mbox{Alice} & \left[ \begin{array}{c} 0\\ \end{array} \right] \\ \end{array} \end{eqnarray*} Alice が自分を好きな場合(図 8 (b)) の隣接行列は次のようになる.
\begin{eqnarray*} \begin{array}{cc} & \mbox{Alice}\\ \mbox{Alice} & \left[ \begin{array}{cc} 1 \\ \end{array} \right] \\ \end{array} \end{eqnarray*}
今回は Alice 一人しか登場しないので,関係と言っても簡単だった.次回はもう少し現実味のある関係の話をしよう.

Sunday, December 2, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (8)


隣接行列

行列は数を二次元のます目上に並べたものである.これは数の表のように見える.ある規則で数を並べると,それがグラフを示すことと同じことになる.それを説明しよう.行列はグラフを表現するだけではなく,さらにいろいろなことができるのだが,ここでは特にグラフの表現をすることに集中して説明する.行列に関してもっと詳しく知りたい人には,文献 [1] をお勧めする.

行列について述べる動機はグラフを記述することにある.ここでいうグラフを表現する方法の一つとして隣接行列がある.ここでその定義を述べておこう.
Definition of adjacency matrix: n 個の点を持つグラフは \(n \times n\) の大きさの隣接行列で表現することができる.ここで,点\(i\) と点 \(j\) 間に有向辺がある場合,行列の成分 \(a_{i,j}\) を \(1\) とし,辺がない場合には \(0\) とする.
これだけである.つまり隣接する点(= 辺で接続されている点)の要素を 1,そうでない要素を 0 とするような行列を隣接行列と呼ぶ.

例として人間関係のグラフを考え,好きか嫌いかの関係を隣接行列で示そう.好きという関係がある場合には点の間に辺を置くとここでは決める.嫌いな場合に辺を置くとしても良いが,私は嫌いな関係よりも好きな関係を知りたいので,今回は好きな関係とする.注意して欲しいのはこういう部分は私が勝手に決めることができるということである.これは事実とかではなくて,問題を解こうとしている人が矛盾が起きない限り,勝手に決めることができる.もし私が,「定義する」とか「仮定する」とか「と,考えてみよう」と言ったら,それは私が決めたことであって,読者には賛成してもらいたいと思っている.もし読者が賛成しない場合,その後の議論は意味をなさない.

次回は具体的なグラフと隣接行列の例としてアリスに登場してもらい,その人間関係を示そう.

参考文献


[1] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition'', Wellesley-Cambridge Press,  2009