グラフ理論と可視化｜直感と数学 #3
『数学って難しそう』ってよく聞きますが、確かに数式だけ追ってると難しく感じる時もあるかもしれません。ですが、ちょっと視点を変えてみるだけで新しい洞察が得られる時があります。
この直感的な感覚をわかっていただければということで、一見難しそうな話を直感的に理解することができるような形で諸々取り扱っていければと考えています。勉強しているというより遊んでいる感覚で見てもらえれば嬉しいです。
#1ではポワソン分布、#2では勾配降下法(Gradient Descent)について取り扱いました。
#3ではグラフ理論について取り扱います。#1と#2については話を面白くするために独自の考察をメインに話を進めたのですが、グラフ理論についてはなんとそのまま取り扱っても直感的で面白いので#3ではグラフ理論のベーシックなところをご紹介できればと思います。
以下目次になります。
1. グラフ理論の概要と歴史
2. 隣接行列と有向グラフ、無向グラフ
3. 有名なアルゴリズム
3.1 ダイクストラ法
4. 機械学習とグラフ理論
4.1 グラフィカルモデリングとベイジアンネットワーク
4.2 TensorFlowと計算グラフ
5. まとめ
1. グラフ理論の概要と歴史
概要を抑えるにあたっては一旦はWikipediaなどで十分だと思います。
グラフ理論(graph theory)は、ノード(頂点; Node)の集合とエッジ(辺; Edge)の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。
上記はWikipediaの冒頭を少々編集したものです。ここでのキーワードとしてはノードとエッジです。
上図もWikipediaの写真を拝借したのですが、この図は6つのノード(点)と7つのエッジ(辺)で成り立っています。
コンピュータでの取り扱いについては2節の隣接行列のところで説明しますが、行列表記との対応を覚えておくと便利です。また、ノードとエッジの組み合わせで表した上図をグラフと呼んでいます。この辺までは定義なので、そういうものだと覚えていただければと思います。
また、グラフ理論の歴史ですが、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示したのが起源のひとつとされるそうです。
https://ja.wikipedia.org/wiki/一筆書き#ケーニヒスベルクの問題
詳しくは上記を見ていただければと思いますが、18世紀の初め頃にプロイセン王国の東部、東プロイセンの首都であるケーニヒスベルクという大きな町の橋を題材に一筆書きで橋が渡れるかという問題が題材となっています。始まりそのものが非常に具体的な話題なので、色々と直感が働かせやすい分野なのではと思います。
以上が簡単な概要になります。以降は2節でグラフの行列的取り扱いの隣接行列、3節では有名なアルゴリズムの具体例としてダイクストラ法、4節では機械学習への応用ということでグラフィカルモデリングやTensorFlowについて触れられればと思います。
2. 隣接行列と有向グラフ、無向グラフ
隣接行列(adjacency matrix)はグラフの行列表現になります。
こちらもWikipediaがわかりやすいので上記をベースに進めていきます。
言葉で説明するのが難しいので、結論から表現すると上記が1節で例に出したグラフの隣接行列です。こちらもWikipediaに載っていたものをお借りしました。
さて、上記の意味ですが、行列のa行b列が1の場合はaとbがエッジで連結しているということを意味しています。例えば1行2列が1なので1と2は連結している一方で、1行3列が0なので1と3は連結していません。このように要素の数を行数と列数に持つ行列を用意することで、グラフを行列で表記することができます。これが隣接行列の基本的な考え方です。
また、グラフには向きがあるグラフと向きがないグラフがあります。それぞれ有向グラフ、無向グラフと言います。冒頭の例は向きがないので無向グラフです。例としてあげるなら駅の路線図などがわかりやすいかもしれません。有向グラフは人物相関図など一方通行もありえる場合に用います。
それぞれの隣接行列については、無向グラフはa行b列とb行a列の値が同じなのに対し、有向グラフはそれは成り立ちません。このことによりグラフ上の向きという概念を行列で表現することができます。
3. 有名なアルゴリズム
グラフ理論の有名なアルゴリズムにはベルマン–フォード法、ボルゥースカ法、ダイクストラ法、ワーシャル–フロイド法など様々なアルゴリズムがあります。全体の分量のバランス上そこまで詳細に取り扱いたくないので、一番ベーシックな例として良くあるダイクストラ法について3.1節で取り扱えればと思います。
3.1 ダイクストラ法
上記記事がわかりやすいです。ざっくり言うと、原点から近い順に最短経路のノードを決定していき、ゴールの最短経路を求めると言うアルゴリズムです。Wikipediaの記事のgifのアニメーションがわかりやすいのではと思います。詳細はWikipediaの記事をご確認ください。
より応用的な例をということで4節では機械学習との関連についてまとめられればと思います。4.1ではPRMLの8章を参考にグラフィカルモデリング、4.2ではTensorFlowの計算グラフとTensorBoardについて取り扱います。
グラフィカルモデルに関する解説についてはPRMLの8章が情報量が豊富で非常に良いです。
PRML カテゴリーの記事一覧 - lib-arts’s diary
詳細に関しては上記のように1章単位でまとめているので、こちらでまとめていければと思います。今回はグラフィカルモデリングのメリットと言うことで、8章の冒頭部から引用できればと思います。
グラフィカルモデルは以下のような便利な特徴を持っている。
1. 確率モデルの構造を視覚化する簡単な方法を提供し、新しいモデルの設計方針を決めるのに役立つ
2. グラフの構造を調べることにより、条件付き独立性などのモデルの性質に関する知見が得られる
3. 精巧なモデルにおいて推論や学習を実行するためには複雑な計算が必要となるが、これを数学的な表現を暗に伴うグラフ上の操作として表現することができる
上記がグラフィカルモデルの利点として言及されていました。グラフ理論は3節のようにアルゴリズム的に云々もそうですが、複雑な概念を視覚化する手段として用いることで大きな武器となります。精巧で複雑なモデリングを行えば行うほど状況の整理が大変になるので、グラフィカルに表現すると良いです。
PRML8章では有効グラフィカルモデル(directed graphical modeling)の例としてベイジアンネットワーク(Bayesian network)、無向グラフとしてマルコフ確率場(Markov random field)について言及されています。
4.2 TensorFlowと計算グラフ
4.1でグラフィカルモデルの利点をまとめたのですが、最近勢いのあるライブラリでこちらをうまく利用しているのがTensorFlowだと思います。
上記はTensorFlowの公式ページですが、概要の説明のところで深層学習と言うよりもデータフローグラフという言葉が強調されています。
一連の計算における数学的な演算ノード、データの配列をエッジとして表現するグラフとして表すことで、複雑なモデリングも直感的に取り扱うことができます。
上記のようにグラフとして扱った演算における計算の流れをTensorBoardを用いて可視化を行うことも可能です。複雑な演算を行う際のコーディングは非常に不安になるものですが、このように可視化を行うことでミスを減らすことができます。
5. まとめ
今回まとめたグラフ理論は複雑な内容を可視化して、直感を働かせやすくしてミスを減らしたり思考のアシストをしてくれたりする非常に強力な考え方です。
抑えておくことで様々な活用シーンで役に立つのではと思います。複雑な内容を直感的に取り扱えるというのはやはり強力な武器になりうるので、可視化というのは常に意識すると良い内容なのかもしれません。
