統計数理研究所の「ビッググラフと最適化」を聞いてきました。(午後セッション編)
先日参加した数学協働プログラム チュートリアル「ビッググラフと最適化」(http://coop-math.jpn.org/ )の午後セッションの話を書きます。
===============【プログラム】===============
10:10～11:00
上田修功（NTTコミュニケーション科学基礎研究所 機械学習・データ科学センタ代表）
11:00～11:50
下流から攻めるビッグデータ
樋口知之（統計数理研究所長）
13:00～13:50
巨大グラフ：数学的解析と高速アルゴリズム
河原林健一（国立情報学研究所 情報学プリンシプル研究系 教授）
13:50～14:40
次世代スーパーコンピュータ技術を用いた超大規模グラフ解析と実社会への応用
14:50～15:40
大規模な組合せ最適化問題に対する発見的解法
梅谷俊治（大阪大学 大学院 情報科学研究科 情報数理学専攻 准教授）
15:40～16:30
SCIP Optimization Suite によるシュタイナー木問題の解法
品野勇治（Zuse-Institut Berlin 研究員・統計数理研究所 客員准教授）
==============================
午前セッションはこちらから。
統計数理研究所の「ビッググラフと最適化」を聞いてきました。(午前セッション編) - 背伸びのままで。
それでは、以下から午後セッション編。
巨大グラフ：数学的解析と高速アルゴリズム
ERATO河原林巨大グラフプロジェクトの河原林教授がプロジェクトの概要を面白い事例も入れながら解説するセッションでした。
グラフ理論を応用して、今まで1ヶ月もかかっていたプロ野球のスケジュール組みを数十秒だか数十分だかで完成させるソフトを作るなど、現実に数学や情報の理論を応用するところまで手がけている方でした。
※元記事が消えていたので、記事を取り上げているブログを貼っておきます。
記事名：●プロ野球日程を瞬時に計算 数学者がソフトを開発
http://ameblo.jp/harulu745/day-20130316.html
歴代プロジェクトには以下の様な数え上げの限界を分かりやすく解説する動画を作った人もいたようです。コミカルに描かれていますが、シャレにならない問題なのです。
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ - YouTube
身の回りの物事でも、普通に数え上げていこうとすると何万年もかかってしまうことがあります。巡回セールスマン問題とか。
そのような実は数学や情報の知識を使って解決できるようなことへのソリューションを提供していくことを考えているとのことでした。
AcademicとEngineeringとCompanyの3者をAcademicの方向から結びつけていくべく、優秀かつ変なプライドを持たない次世代の研究者を多数擁してプロジェクトを進めており、チームのメンバーのほとんどが30歳未満で構成されています。
野球のスケジューリングにグラフ理論を使うという発想は、一見突拍子もないように思えますが、アルゴリズムと理論屋特有の以下のアプローチでは自然な発想であるとのことでした。
アルゴリズム＆理論屋特有のアプローチ
残念ながらスケジュール作成のソフトはプロ野球で採用されなかったようですが、満遍なく各チームとの対戦頻度やアウェイ/ホームのバランスを保ちながら、総移動距離や移動回数を数十パーセント改善するというソリューションにグラフ理論を使うというのは、彼らの発想からすると突拍子もないようなことではないとのことです。
専門性を実社会に活かすということはこういうことか、ということが垣間見られたセッションでした。
次世代スーパーコンピュータ技術を用いた超大規模グラフ解析と実社会への応用
もうこの辺からは分からなすぎてメモさえ残せていません…。
前のセッションではできるだけ計算量を効率化して、短時間で解くことができるアルゴリズムに落としこむ(例えばn log m程度)ということを志向しているプロジェクトでしたが、このセッションではそれほど計算量を効率化できないが(m^3+n^3など)重要な問題でもスーパーコンピュータの処理能力を生かして解くというようなプロジェクトも行っているということでした。
メディアではなかなか発表されることではないので知らなかったですが、スピーカーの藤澤克樹教授は、ある基準においてダントツで世界の1位の性能を持つスパコン計算の成果を残すなど、ベンチマークテストも含めてスパコンの活用に取り組んでいるそうです。
理工学部教授 藤澤 克樹が代表を務めるCRESTチームがGreenGraph500世界第一位に認定、上位を独占 | 中央大学
http://www.chuo-u.ac.jp/research/industry_ag/rdi/news/2013/06/2085/
プロジェクトのサイト
たとえば、避難経路の探索など、多数の要因が複雑に絡み合って計算量が爆発してしまう問題などに応用されているようです。
大規模な組合せ最適化問題に対する発見的解法
次のセッションは大阪大学の梅谷准教授のものでした。
http://www-sys.ist.osaka-u.ac.jp/~umetani/
この分野は一部、自分が学部時代にやっていたことと共通していて、パッキング問題や翻訳の精度向上など、現状のデータや制約条件の中で目的関数を最大化あるいは最小化するという最適化問題の説明です。
パッキング問題というのは、容器の中に出来るだけモノをたくさん詰める(=隙間を少なくする)ために、どういうアルゴリズムでものを詰めていけばという問題で、大学にいたころにこの問題に関して発表をしたことを思い出しました。
たとえば、四角形の容器に座標を設定して「モノ同士が他のモノの上か下か右か左にいる」という事実から詰め込み方を決める方法や、大きいモノから詰めていくという方法、モノの価値がそれぞれ異なる場合は高いものから詰めていく方法、など様々な方法のうち制約条件内で最適な解き方を探っていきます。
最適化問題では、日常の解きにくい問題の制約条件の捉え方(=数式化)から考える必要があります。つまり問題の読み解き方が非常に重要です。
その他に色々な事例が紹介していたのですが、面白いと思ったのが、翻訳に使われているということでした。
上記の図のように、複数言語間で同時に使われやすい単語の相関を求め、一つの文章が入力された時に最も使われやすそうな単語が選択されるという仕組みで翻訳することができるとのことでした。大量の文章データがあれば、このような非常に原始的な方法で翻訳することができるようです。
その他の変数も含んだ大量データがあれば、「影響力を与える(=面白い、広まる、など)簡単な言い回し」も作ることもできそうです。ただ、面白い"文章"を狙って作るレベルまでは、今の技術の延長でコンピュータが人間を越えることは(少なくとも生きている間は)無い気がしています。
サルが長い時間キーボードを叩き続けるとシェイクスピアの作品を打ち出すという「無限の猿定理」 - GIGAZINE
http://gigazine.net/news/20081003_infinite_monkey_theorem/
SCIP Optimization Suite によるシュタイナー木問題の解法
最適化問題を解ける無償ソルバーのなかで最も性能が高いと評価されているSCIPというソルバーの話をしていたけど、全然わからんかったです。
SCIP(http://scip.zib.de/)ホームページより引用
この日話していた問題の多くに対応していて、最適もしくは妥当な計算方法をいち早く見つけて問題を解決することができるとのことでした。
それ以上は本当に全然わからず、最後に専門性の壁を突き付けられた形で終わったセミナーとなりました。
一日通して分からないところばっかりだったけれど、考えたいことも増えて非常に楽しい休日となりました。
早く当日の資料来ないかなぁ。
