Laplacian行列

今回はLaplacian行列について記事を書きます.Laplacian行列は機械学習でもデータのクラスタリングなどにしばしば用いられるので,情報系の学生にとってはそこそこ馴染みのあるものだと思いますが,Laplacian行列をちゃんと(導出とか物理学的解釈とか)説明している日本語の教科書やweb記事は私の知る限りほぼ存在しないように思います.おかげで私もB4の頃は勉強にとても苦労しました...... 今回は工学(特に,情報工学や数理工学)の学生を対象にしているので万人向けではないですが,理工系の学部生程度の知識があれば十分読めると思います.タブン.

前口上はさておき,早速説明に移りましょう.

Laplacian行列はグラフラプラシアン,キルヒホッフ行列とも呼ばれますが,ここではLaplacian行列で統一します.ここでいう"グラフ"というのは,散布図やヒストグラムなどのグラフではなく,グラフ理論で扱われるグラフ,つまり事物や人の関係性を記述する数学概念です.

グラフはノードとリンクによって構成されます.ノード集合を V=\{1,2,\dots,n\},リンク集合を E \subset V \times Vとすると,グラフはG=G(V,E)と書くことができます.さらに,ノード i-j間のリンク(i,j)の方向を区別する場合は有向グラフ,区別しない場合は無向グラフと呼ばれます.以下では,グラフGは無向グラフとして話を進めます.

グラフを数学的に取り扱うため,グラフ理論ではグラフ構造を行列を用いて表現します.グラフ構造の行列表現として,国内のグラフ理論の教科書では,接続行列や隣接行列が挙げられることが多いですが,一般に接続行列は非正方行列となり扱いづらいので,実用的には隣接行列の方がよく用いられます.グラフGの隣接行列 \boldsymbol{A}=[A_{ij}]の各成分 A_{ij}はリンクの有無を表し,ノード i-j間にリンクがあれば A_{ij}=1,リンクがなければ A_{ij}=0となります.

さて,これで準備が整ったのでいよいよLaplacian行列の導出に移りましょう.このために,次のようなグラフ上の拡散過程を考えます.

ノード i上の何らかの分布量 \psi_{i}がリンクを介してグラフ上を拡散する状況を考えます.なお,ノード jからノード iへの流入は差 \kappa(\psi_{j}-\psi_{i}) (\kappa>0) に比例すると仮定します(差 \kappa(\psi_{j}-\psi_{i})が負になる場合はノード iからノード jへの流出を意味します).このとき,ノード iの分布量 \psi_{i}の時間発展は以下のように記述できます.

 \frac{d\psi_{i}}{dt} = \kappa\sum_{j=1}^{n}A_{ij}(\psi_{j}-\psi_{i}) = \kappa\sum_{j=1}^{n}(A_{ij}-\delta_{ij}d_{i})\psi_{j}

ここで, \delta_{ij}クロネッカーのデルタ, d_{i}:=\sum_{j=1}^{n}A_{ij}はノード iの次数を表します.上式をベクトルで書くと

 \frac{d\boldsymbol{\psi}}{dt} = \kappa(\boldsymbol{A}-\boldsymbol{D})\boldsymbol{\psi}

となります.ただし, \boldsymbol{D}:=\mathrm{diag}(d_{1},d_{2},\dots,d_{n})は次数行列です.ここで \boldsymbol{L}:=\boldsymbol{D} - \boldsymbol{A} とすると,グラフ上の拡散方程式として

 \frac{d\boldsymbol{\psi}}{dt} = -\kappa \, \boldsymbol{L} \, \boldsymbol{\psi}

以下が得られます.上式を連続空間における拡散方程式 \frac{du}{dt}=\kappa \, \Delta \, uと比較すると,行列\boldsymbol{L}ラプラス演算子 \Deltaに対応することがわかります.これが行列 \boldsymbol{L}がLaplacian行列と呼ばれる由縁です.

ところで,グラフ上の拡散方程式の右辺にはマイナスが付いていますが,これは単に定義の問題で本質には影響しません.論文によっては \boldsymbol{L}:=\boldsymbol{A} - \boldsymbol{D} と定義しているものもあります.一般に \boldsymbol{L}:=\boldsymbol{D} - \boldsymbol{A} とされているのは,このように定義すると \boldsymbol{L}が非負正定値行列になって便利というだけの理由だと思います.

さて,ここまでの議論でグラフ上の拡散現象がLaplacian行列によって記述できることがわかりました.しかし,Laplacian行列が本質的にグラフにおけるラプラス演算子であることを考えれば,拡散の他にも様々な現象を表現できそうです.私の知る限り,グラフ上の拡散方程式の他に,反応拡散方程式,回路方程式,振動方程式などがLaplacian行列によって記述できたと記憶しています.以下では,その一例としてグラフ上の振動方程式を紹介したいと思います.

 n個のノードがバネで結合されており,隣接ノード同士で相互に影響を与え合いながら振動する連成振動系を考えます.時刻 tにおけるノード iの平衡点からの変位を x_{i}=x_{i}(t)とし,復元力はノード間の変位の差に比例すると仮定します.ノードの質量を m,バネ係数を kとし,一般化運動量を p_{i}=p_{i}(t)とすると,この系のハミルトニアン Hは以下のように書けます.

 H = \sum_{i \in V}\frac{(p_{i})^{2}}{2m}+\frac{k}{2}\sum_{(i,j) \in E}(x_{i}-x_{j})^{2}= \sum_{i \in V}\frac{(p_{i})^{2}}{2m}+\frac{k}{2}( {}^{t}\boldsymbol{x} \boldsymbol{L} \boldsymbol{x} )

上式右辺の第1項は運動エネルギー,第2項はポテンシャルエネルギーを表しています.

さて,ハミルトニアンから正準方程式を導出すると

 \frac{dp_{i}}{dt} = -\frac{\partial H}{\partial x_{i}} = - k \sum_{j=1}^{n}L_{ij}x_{j}

 \frac{dx_{i}}{dt} = \frac{\partial H}{\partial p_{i}} = \frac{p_{i}}{m}

となります. 上式をまとめて p_{i}を消去すると,ノード iに関する振動方程式

 m \frac{d^{2}x_{i}}{dt^{2}}=- k \sum_{j=1}^{n}L_{ij}x_{j}

が得られます.これをベクトル形式で表現するとグラフ上の振動方程式

 m \frac{d^{2}\boldsymbol{x}}{dt^{2}}=- k \boldsymbol{L} \, \boldsymbol{x}

 を得ます.ここでは,面倒くさかったため簡単のため質量やバネ係数を全て同一としましたが,ノード毎に質量が異なる場合やリンク毎にバネ係数が異なる場合にも容易に拡張可能です.

グラフ上の振動方程式の応用先として代表的なものにグラフの可視化があります.確かPythonのNetworkXモジュールのグラフレイアウトの一つとして利用されていた気がします.また,分子動力学の分野においてタンパク質間相互作用を近似的に記述するためにちょうど上記のような振動モデルを導入していたと思います.

 

改めて読み返すと説明の拙い部分が随所に見られますが,ちゃんと伝わるでしょうか.この記事を読んだ方々がLaplacian行列について少しでも理解を深めていただけたなら僥倖です.にゃん.

この日記は半分眠りながら書きました

Twitterを眺めていると,ほんの些細なテーマに対して思いつきで長々と意見を述べている人間を多く観測する.私にはとても真似できない.

私は文章を書くのが苦手だ.実を言えば,たった140字のツイートを書くことですら私にとっては一苦労なのだ.このブログの更新があまりされないのも私の文章記述への忌避感(及びそれに伴う億劫さ)に依る部分が大きい.

自身の思考過程を分析してみるに,私は言語ではなくイメージで思考をしているようで,もやもやした雲のような思考イメージをそのまま加工することで思考を進めている(気がする).このため,咄嗟に考えを述べようとすると,言語化処理に長い時間が掛かってもごもごしてしまうことが多い.また,思考をどうにか言語化しようと言葉を探しているうちに,いつの間にか思考そのものが拡散して消えてしまうこともある.

改めて客観視するとばかみたいだけど,この思考形式はひらめきという点で優れている.言語で思考をする場合,思考は言語の論理性に束縛されてしまい,ひらめきは訪れにくい.一方で,イメージで思考をする場合,その曖昧さゆえに連想的に自由に思考を展開でき,ひらめきが訪れやすい.そう思わないとやってられない.

 

まだ書きたいことあったけど,もう死ぬほどねむいのでおわり.

過去

部屋の片付けをしていたら3年前(大学3年生の頃)に書いていた読書日記が出てきました.折角なのでちょっぴり公開してみたいと思います.

 

 

2014/2/8

読書日記なるものを書きてみむとす.野矢茂樹『入門!論理学』を読んだ.記号を使わないで命題論理学や述語論理学を説明していた.少し冗長に感じた.すぐに読み終わってしまったので,同『無限論の教室』を読んだ.頭が疲れた.でも,面白かった.無限の解釈としての2つの立場:実無限/可能無限.私はどちらなのだろう.カントールの無限論,ラッセルのパラドクス,ゲーデル不完全性定理......これらの証明において用いられた対角線論法.一見すると関連のなさそうなこともどこかで内的な関連を持っている?

 

2014/2/12

早速日記が飛んでしまった.今日は駅まで買い物に行った.掃除機の値段の高さに驚いた.8000円くらいのシンプルな感じのものを買ったのだけど,少し音がうるさい.夜遅くや朝早くには掛けられないな.ところで,今日は脳科学の本を主に読んだ.竹内・茂木『脳のからくり』はどこかで聞いたことのあるような話ばかりであまり新規な知識は得られなかったけれど,知識の整理にはなった.茂木『脳と仮想』は「仮想」という脳内現象を切り口に他者の心や死などを考察していて,まあまあ面白かった.少し新鮮味に欠けるというか刺激的でないところはぼーっと読んでしまったけれども.明日も頑張ろう.

 

2014/2/17

また日記が飛んでしまった.習慣化って難しい.今日は1日中読書をしていた.カント『啓蒙とは何か』はカントの論の運び方を知ることができた気がする.三批判に挑戦してみようかしら.養老『唯脳論』は新鮮で面白かった(古いのに).独我論をもう一歩踏み出した感じなのかな.ダーウィンの進化論の妥当性に対する信頼が少し揺らいだ.ああ,文章下手で嫌になるなあ.

 

2014/3/1

久しぶりの日記.まあバイトの研修やら帰省やらで色々忙しかったから仕方ない.それにしてももう3月とは.光陰矢の如し.元々この日記は読書記録を主たる目的として始めたものだけど,やめよう.下手に制限するよりも考えている(あるいは考えていた)ことを自由に記す方が良い気がする.脳の整理にもなるし.そういえば,小学生の頃は「思ったことを自由に書きなさい」という課題がしばしば出されたものだったけれど,アレは苦手だった.現在も苦手だ.そも,人間がある対象について必ず何らかの感想を抱くことを前提としていることがおかしいと思う.周囲の人々はなぜかすらすら書けていたような気がするけれども.多分子供の頃は何も考えずにぼーっと生きてきたのだろう.いまもそれは変わっていない.僕は童心を忘れないのだ.いえーい.

しかし,今日のバイト(研修)はとても緊張した.講師が多すぎると思う.求人の「急募」とはなんだったのか.お前ら働けよ.研修では講師としての心構えやら書類作成法やらを説明された.右から左に聞き流すことに定評のある私だけど,今日の話は割と頭に入ってきた.話し手のお姉さんが説明上手なためであろう.左から話されたことがよかったのかもしれない.

 

 2014/3/4

まだ日が高いが少し日記を書く.一昨日は体調が芳しくなかったため仕方ないけど,昨日は完全に無駄にした.アニメは1日1時間と決めたはずではなかったか,私よ.しかし,なぜ長時間アニメを見てしまうのだろう.やはり頭を使わないで楽に見られるからだろうか.アニメを見るときに使うのは視覚と聴覚,本を読むときに使うのは視覚のみ.こう考えるとアニメの方が脳の領域を広く使っているように思える.まあ両者では思考の働かせ方の度合いが違うだろうから単純に使用領域の多寡で論じることはできないけれども.「アニメを見る = 馬鹿になる」という安易な結びつけは良くないと分かっているけれども,アニメを見た直後はどうも頭の回転が遅くなるように感じるし,何よりアニメを見て1日過ごすのと本を読んで1日過ごすのとでは寝る前の充実感に大きな差が生じるから,今後アニメを見るのはやめよう.嘘だけど.

たぶん私は責任感が強い方なのだけれど,この責任感を生み出す根源的な感情は「人に嫌われたくない」というものなのだろう.というか,私の基本的な行動原理は全て「人に嫌われたくない」であるように思える.良くないなあ本当に.人に嫌われることを恐れるようになったのはいつからだろうか.自分を向く他者の負の感情が見えるようになった後だろうから,やはり中学生か.幼少期に強烈な体験をするとそう簡単に忘却することはできない.これは薄々分かっていた.しかしここまでとは.げに恐ろし.虚偽と虚勢で塗り固めた外殻を打ち捨てられる日は来るのだろうか.

 

2014/3/5

今日は朝から雨だった.雨の日は少し陰鬱な気分になる.こんな日は家に引き篭もっているのが一番である.昔の人は言いました.晴耕雨読.ということで,プラトンの著作を2冊ほど読んだ.途中何度かうつらうつらすることもあったけれど,あまり引っかかることなく読み終えた.『饗宴』も『パイドン』も名著の呼び声は高いけど,私にはあまり響かなかった.2冊読んで疲れたので,読書をやめて夕飯を作った.楽だし栄養あるし美味しいし,作ってよかった,温野菜.明日も食べよう.今日の日記はなんか今までで一番日記っぽい気がする.

 

2014/3/7

今日は5回目の研修.内容は主として講師の1日の流れ.まだ緊張は解けないが,初日に比べればだいぶ周りが見えるようになってきた気がする.早く職場の雰囲気に馴染めればいいのだけれど.今日の失敗をしいて挙げるとすれば,折角話題を提供してくれたのに上手く広げられなかった点かな.あまり友好的な雰囲気を纏っていない私に話しかけるのはそれなりに覚悟を必要としただろうに(それともこれは妄想だろうか).申し訳ない.夕飯に焼いたししゃもは美味しかった.ししゃも美味しいよししゃも.さて,風呂入って本読んで寝ましょう.

 

2014/3/8

今日は1日空いていたけど思ったより本が読めなかった.まあ明日もあるし別にいいのだけれど.三島由紀夫のエッセイを読んでいて,やはり文章の上手い人間の本にはつい引き込まれてしまうなあと思った.私も文才が欲しい.知性も欲しい.ついでにお金も欲しい!

人間はざっくり言えば意思決定の手段として理性と感情の2つを持っており,理性が感情によりも相対的に強く働く人間は大人と言われる(気がする).この意味で大人になりたい私は理性を鍛えるために数ある書物の中でも哲学書と理工書を選択的に読もう(あるいは読まなければならない)と考えている.確かに,直感的には小説よりも学術書を多く読んだ方が速やかに理性を獲得できるように思えるし,実際にその通りなのかもしれない.しかし,理性を重んじるばかりに感情を蔑ろにしては,この社会(対人コミュニケーションを避けては通れない,孤独を愛し,孤独に生きる私にとってかくも生きづらいこの社会!)を生き抜けないのではないか.であれば,人間の感情の機微を知るための努力をしなければならない.とりあえず小説を読もう(会話は?).

 

2014/3/9

今日はとても疲れた.朝4時に起きたことと動物的欲求に打ち負けて愚を犯してしまったことが敗因だろう.もっと洗練されねばならない.自己を制し御すのだ.

ところで,科学は最新の科学が最も優れているとされるのに対し,文学や音楽,絵画などの芸術は古典 (classic) が優れたものとされる.これはなぜだろう.ここに理性(あるいは知性)と感性の本質的な差異が現れているような気がする.少し考えてみよう.でも今日は眠いので明日.

 

2014/3/10

太陽に照らされた木々の葉がアスファルトに描く光と陰の万華鏡に春を感じ,朝独特のしんと澄み切った冷気に冬を感じた.もうすぐ春ですね.

9時に成績開示があり,不安と期待を胸に確認してみると,学期GPAが3.24,年度GPAが3.35,累積GPAが3.14とまずまずの結果だった.応用数理の試験で失敗したため,ともすれば累積GPAが3.0を下回るのではないかと戦々恐々していたけど,とりあえず安心.ところで,成績を確認している自身の心の動きを観察していると,期待以下(この表現は正しいのか?)の結果に目が行き,また,その結果の悪さの原因を他者(この場合,教師)に求める自分がいる.逆に,期待以上の結果に対しては特に何も思うことはない.「失敗は他人のせい,成功は自分のおかげ」という諷刺的な言葉があるが,今回のこの心の動きはまさにこれではないか.これはおそらく人間の本質であって,自分の弱さを直視して傷つきたくないという防衛戦略なのであろう.こういう弱い部分は意識していないとすぐに現れ,ともすると他人を傷つけかねない.注意せねば.しかし,以前は成績開示なるイベントは結果に一喜一憂し,「不当な評価である」と愚痴をこぼし,他人と優劣を競って自尊心を傷つけ合うものでしかなかったが,今では自身を客観的に分析する道具として利用することができている.これは私が精神的に成長できていることの証左ではなかろうか.そう思うと嬉しいのでそういうことにしておく.

 

 

まだあるのだけど,だいぶ長くなってしまったのでこのへんまで.論理や文章に少々稚拙な部分があり恥ずかしいですが,久しぶりに日記を読み返すと様々な発見があって面白いですね.現在とは考え方や興味の方向性がかなり異なっている気がします.

それにしても,初記事投稿から2回目の記事投稿まで4ヶ月も間を空けてしまうようなどうしようもない怠け者が,3年前はほぼ毎日ちゃんと日記を書いていたとは.

Partition Problem

研究で11月からずっと解決できない問題がある.

この問題というのはある条件を満たす唯一の◯◯◯を求めるという問題で,上手く式を変形していくと,Partition Problem (or Number Partitioning) と呼ばれる最適化問題と等価になることが示せている(厳密に言うと完全に等価ではない).しかし,定式化した最適化問題に近似解法を適用しても,どうしても真の解が得られないのである.

そこで,備忘録を兼ねて(そして,あわよくば誰かからヒントを貰えることに期待を込めて)Partition Problemについてまとめてみようと思う.

 

まず,Partition Problemとは,N個の正整数の集合 S=\{n_{1},n_{2},\dots,n_{N}\}を2つの集合R,\,S-Rに分割するとき,R,\,S-Rの要素和が等しくなるように分割するNP完全問題である.

例として,集合S=\{3,1,1,2,2,1\}を要素和が等しくなるよう2つの集合に分割する問題を考えてみる.これは簡単に解けてR=\{1,1,1,2\},\,S-R=\{2,3\}またはR=\{2,3\},\,S-R=\{1,1,1,2\}が得られる.

上記例のように,元の集合の要素数Nが少なければヒューリスティックに解を得られるが,Nが大きくなるにつれて解を求めるのは困難になる.実際,Partition Problemにおける可能な解の組み合わせは2^{N}存在するため,全数探索で求めるのは非現実的である.

 

では解けないのかというと勿論そんなことはなく,イジングモデルを利用する方法により近似的に解くことが可能であるとされている(他にも様々な方法があるようだが,私はよく知らない).イジングモデルとは,統計力学において強磁性体を解析するために提案されたモデルであり,格子点上に並んだ自由度2(上向き or 下向き)のスピン(棒磁石みたいなもの)で構成される.

イジングモデルについての詳細な説明は他記事の解説や教科書に譲るとして,とりあえず系のハミルトニアン(全エネルギー)を考えてみる.Partition Problemにおいて,ハミルトニアンHは,スピンs_{i}\in\{-1,1\}~(i=1,2,\dots,N)n_{i}を用いて以下のように書ける.

H=A\left( \sum_{i=1}^{N}n_{i}s_{i} \right)^{2}

このHを最小化するスピン配位\textbf{s}=(s_{1},s_{2},\dots,s_{N})を求めることは,集合Sを要素和が等しくなるように2分割することに等しいということが直ちにわかる.ゆえに,最適なスピン配位を焼きなまし法 (Simulated Annealing; SA) などを利用して探索すれば現実的な時間内でPartition Problemを解くことが可能となる.

 

以上でPartition Problemの解説は終わりである.ここからは私の研究の話.

序文?で,私が定式化した問題はPartition Problemに等価ではあるが,厳密には完全に等価ではないなどと不明瞭なことを述べていた.少し具体的に説明すると,ハミルトニアンの形式は同じだが,元の集合の要素が非整数なのである.すなわち,

H=A\left( \sum_{i=1}^{N}r_{i}s_{i} \right)^{2}, ~~~ r_{i} \in \textbf{R}

ということである.上式はn_{i}r_{i}になっただけであり,またH=0となるスピン配位の組み合わせが唯一つ存在することは事前知識としてわかっている.しかしなぜか解けないのである.こまった.