Skip to main content

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (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 の線形結合を求めることは,すなわちベクトルを掛けることであった.したがって,それぞれの駅に何ステップで行けるかわかっている場合には,どこからスタートしたのかも計算できる.線形システムを解けばよい.しかし,どこの駅からスタートしたかはあまり興味のない問題だと思う.今どこにいて限られた時間でどこまで行けるかという方が通常は知りたいことだからである.

参考文献

Comments

Popular posts from this blog

共有メモリによるプロセス間通信

Unix の共有メモリを使ったプロセス間通信について調べて実験をしてみた.対象は1つのホスト上での複数のプロセスである.ネット上でいくつか例題はないかと探したが,どうも良い例となるコードが見当たらなかった.結局はある解説記事と,Stack Overflow の議論と,man page を見て作ってみたものになったので,例をここに置くのも有用かと考え,この記事を書く.(もしかしたら探し方が悪くて良いコード例をみつけられなかっただけかもしれない.) mmap を使うかどうかという話がいくつもでていたが,POSIX の方向としては,shmem_open と mmap を使うという方向があるということだったので,それを信じてその形での実装を試してみた. 基本的なコードの流れは次のようになる. 共有メモリ領域を1つのプロセスが shm_open() を使って作成する.その際に,プロセス間で共通の文字列を識別子(``identifier'')とする.(Linux ではこれが /dev/shm/identifier のように見える.) 共有メモリ領域を mmap() でメモリにマップする.共有メモリポインター (shared_ptr)が得られる. shared_ptr を使って複数のプロセスで通信をする. 利用終了後は munmap() をつかってマップを消す. 共有メモリオブジェクトを shm_unlink() によって消す. 以下に示すプログラムは,server と client の2つのプロセスが共有メモリを使って通信をするものである.ここで,server プロセス数と client プロセス数は共に 1 を仮定する.server と client は自分の領域にしか値を書き込まないことで,ロックを避けている.互いに相手の値を読み,それよりも1大きい数を一定の期間ごとに自分の領域に書くという例題である.シンプルではあるが,共有メモリで通信をする基本としては十分なものだと思う.ソースコード(shmem_test.cpp)を以下に付加する.ソースコードのコメントにコンパイル方法とどのように利用するかを書いておく. /*   Shared memory inter process communication minimal exa

複数の線を持つ線グラフを Jenkins の plot plugin で描く方法

私は毎夜のソフトウェアテストを自動化するために Jenkins というツールを使っています.今回は, valgrind  を使ってメモリーリークのテストを自動化することにし ました.その際,エラーの数の結果をグラフとして表そうと思って, Plot plugin  を使うことにしました. Plot plugin の例図からは,複数のデータラインを描くことができるのは明らかなのですが,どうやったらいいのかは参照のページや,例としてあった Perl script,plugin 中の help からは私にはよくわからなかったのです. ここで重要な考えは,それぞれのデータラインにはそれぞれの出力ファイルが必要ということでした.私はこれを誤解していました. 例として,ビルドの時に次の property データファイルを出力します.それぞれのファイルが1つのデータラインを表します. valgrind_trunk_result.definitely.property valgrind_trunk_result.indirectly.property valgrind_trunk_result.possibly.property それぞれのデータの中身は1行のデータ点です.たとえば, valgrind_trunk_result.definitely.property ファイルの中身は次のような1行 です. YVALUE=0 このファイルを ${WORKSPACE} ディレクトリ以下に出力します.ここで," WORKSPACE " は jenkins が提供する環境変数です. 図1が私の plot plugin の設定を示しています.これは jenkins の config 画面です.3つの data series があって,それぞれにデータファイルがあります. Figure 1: Plot plugin configuration in Jenkins 図2が結果です.複数の線が描かれているのがわかります.(実際には 3 本の線がありますが,最初の線と2番目の線が同じデータなので,重ねって見えません.) Fugure 2: Plot data with multiple data lines

ソニーのカメラ (α 5000) の 30 分のビデオ録画時間の制限を外す方法

私は Sony の Alpha 5000 を気にいって使っています。しかし一つだけ問題がありました。それはビデオの録画時間の制限が 30 分というものです。 今日,ちょっと気になって探したらこの制限を解除できることがわかりました。以下のビデオがその紹介です。 https://youtu.be/7cstA_PuRIg このビデオの作者によれば,ほとんどのソニーのカメラのビデオの制限はなくせるそうです。ただし私が試したのは,Alpha 5000 のみです。 手順 カメラ側 スイッチ On Menu -- Setup --- USB connection を MTP にする スイッチ Off and On USB ケーブルでカメラをコンピュータに接続する (以下接続したままにする) コンピュータ側でソフトのダウンロードとインストール (私は Windows 10 で試しました) 次の URL に行く https://sony-pmca.appspot.com/apps ただし,Internet Explorer か Safari のみサポートということでした。Chrome では上手くいきませんでした。私が試したのは Windows 10,Internet Explore 11 です。 注意事項: このサイトは Sony のサイトですが,ここにあるソフトウェアは Sony のものとは限らないので保証はありません。御自分でリスクを判断してご利用下さい。当方も何も責任を負えません。 上記の URL から,OpenMemories のページに移動する。 このページにある PMCADownloader plugin (PMCADownloader.msi) をダウンロードする PMCADownloader をインストールする 私はいちどここでページを閉じてもう一度 https://sony-pmca.appspot.com/apps を開き,OpenMemories のページに移動しました ここで log に Loading plugin Plugin loaded と表示されます。PMCADownloader の Install がされていない時には,``Plugin loaded'&#