2011年10月24日月曜日
第8回助教の会
第8回助教の会では生産技術研究所の田中剛平さんに「ネットワークの動的ロバスト性」というタイトルで話して頂きました。田中さんは今年7月に「複雑系動力学とその応用」というテーマを掲げて助教から特任准教授に昇進されたばかりです。
複雑系動力学を研究をする目的は、対象となる動的システムの定性的な挙動の変化(分岐現象や相転移)を調べたり、それらの性質を工学的に応用したりすることです。
その中でも、田中さんがとくに注目しているのはネットワークのロバスト性です。ネットワークは神経回路や細胞内シグナル伝達のネットワークなど自然界に普遍的に存在するだけでなく、電力ネットワーク、情報ネットワークなどがあり、私達の生活にも深く関わっています。これらのシステムはネットワークを通してつながっているため、システムの一部に障害が発生したとき、例えば今年3月にあったみずほ銀行のATM障害のように、その影響が広範囲に拡大してしまう可能性があります。そのため、一部に障害が発生した際の影響に対してネットワーク全体がどの程度ロバスト(頑健)であるか解析することは重要なのですが、これはネットワークが複雑であればあるほど容易ではありません。
田中さんによると、ネットワークのロバスト性には構造的なロバスト性と動的なロバスト性があると考えることができます。構造的なロバスト性は2000年ごろから Barabasiら[1]によって研究されてきました。例えばネットワークの一部の構成要素を取り除いたときに、ネットワーク全体の繋がりがどの程度保たれるか、さらに、それがネットワークの種類によってどのように変化するか、といったことが調べられています。一方で、動的ロバスト性はネットワークの繋がり具合ではなく、機能がどの程度保たれるかを問題にする比較的新しい考え方です。ネットワークが繋がりを保っていても、果たすべき機能を果たさなければ困るからです。
・・・とだんだん本題に迫ってきたのですが、ここから先は未発表の内容なので残念ながらブログに書くことはできません。情報が出せる段階になりましたら、更新させていただきます。
2012/2/3 追記:
上記のネットワークの動的なロバスト性に関する論文が Scientific Reports に採録されたそうです:
Gouhei Tanaka, Kai Morino & Kazuyuki Aihara (2012) Dynamical robustness in complex networks: the crucial role of low-degree nodes. Scientific Reports, vol. 2.
おめでとうございます!
[1] Réka Albert, Hawoong Jeong & Albert-László Barabási (2000) "Error and attack tolerance of complex networks." Nature 406, 378-382.
数理第6研究室 冨岡亮太
2011年7月26日火曜日
第7回助教の会
第7回目となる今回の数理助教の会は,情報基盤センターの佐藤一誠さんに「Quantum Annealing in Statistical Machine Learning - 統計的機械学習における量子アニーリング -」というタイトルで発表していただきました.佐藤さんはこの3月に博士号を取得され,4月から情報基盤センターで助教として勤務している若手研究者です.統計的機械学習の研究をされており,特に自然言語処理に興味をお持ちとのことです.
タイトルにもある「統計的機械学習」とは,多くののデータが与えられたときに,これらのデータがどのような過程で生成されたのかを統計的に記述することを目的としています.例えば,数値データが与えられたときに,似たデータ同士をグループ分けする(クラスタリングする)といったことが代表的な問題になります.対象とするデータは数値データに限らず,例えば多くの文書をクラスタリングする手法も研究されており,Latent Dirichlet Allocation と呼ばれる手法では単語の出現頻度に注目することで文書をトピックごとにクラスタリングしています.文書のクラスタリングは,文書要約や翻訳の性能向上,評判分析などに用いられており,実用上重要な問題となっています.

「統計的機械学習」という用語自体は非常に広い意味を持っていますが,今回は,確率的潜在変数モデルを用いた統計的機械学習について講演して頂きました.これは,与えられたデータが「未知の変数(潜在変数)によって定まる確率過程から生成される」というモデルであり,研究の目的はいかにこの潜在変数を推定するかということになります.上のクラスタリングの例であれば,「どのグループに入っているのかを表す変数」と「各グループ内の分布を表す変数」が潜在変数となります.潜在変数の推定には,事前分布に基づいた MLもしくは MAP といった各点ごとに値を推定する方法もありますが,より良い推定をする際には,多くの場合事後分布を用いる必要があります.事後分布の計算には積分が必要なため,事後分布(の近似)をいかに効率的に計算するかが重要な問題となってきます.
事後分布の近似には様々な手法が研究されており,それらはサンプリング(MCMC)を用いる手法と変分ベイズ法(Variational Bayes) を用いる手法に大別されます.サンプリングは,多くのサンプル点を選ぶことで積分計算を近似する手法であり,容易なアルゴリズムを構成できる汎用的な手法なのですが,時間のかかるランダムなアルゴリズムとなっています.一方,変分ベイズ法は,計算しやすい関数クラスの中で真の関数に近いものを求める手法であり,最適化問題として定式化できます.この手法は高速で決定的なアルゴリズムですが,求めている関数自体が近似関数となっています.佐藤さんは,さらにこれらの手法を No interaction と Interaction という視点から分類し,今まで手法が提案されていなかった,Interaction タイプの最適化型の手法(ML/MAP, 変分ベイズ法)を提案しています.Interaction タイプとは複数の初期値から過程を計算していく際に,単純に複数回計算を繰り返して行うのとは異なり,それぞれの過程が相互に影響することを用いた手法を指しています.

本講演では,分割数が未知の場合のクラスタリングの問題(無限混合モデル)に対する Interaction タイプの最適化型の手法(ML/MAP)を説明して頂きました.無限混合モデルにおいては分割数が未知のため,Chinese Restaurant Process (CRP) と呼ばれる過程を用いて探索を行います.この過程はランダムな過程なのですが,Simulated Annealing 法を用いて,徐々に決定的な探索に近づけていく手法が既に知られていました.佐藤さんが提案した手法では,Simulated Annealing の代わりに,物理において量子系の解析で発展してきた Quantum Annealing (量子アニーリング)という手法を用いています.この手法では,複数の過程を同時に計算していく際に,個々の過程を別々に扱うのではなく,それぞれの過程における離散状態の重ね合わせを一つの状態と見て操作を加えていきます.離散状態を重ね合わせたものを一つの状態を見るというのが,物理の意味での量子揺らぎと対応しています.量子系における手法を機械学習に適用した,という発想自体が佐藤さんの大きな貢献ですが,実際のアルゴリズムの構成のためには更なる工夫が必要となります.単純に量子アニーリング法を適用するだけでは,非常に大きな行列の固有値分解を扱うことになってしまうのですが,佐藤さんのアルゴリズムは大きな行列の出現を避けた,高速なアルゴリズムとなっています.
今回の講演の中では,線形代数,確率,微積分,最適化,から物理に至るまで,数学の様々な分野が登場しました.機械学習という応用のはっきりした研究の中で,これだけ様々な分野の道具が使われているということに驚かされました.幅広い分野の知識が必要とされるので大変だとは思いますが,様々な分野と関連してくる活発で魅力的な研究だと感じました.
数理第二研究室 小林 佑輔
Jokyokai20110725
View more presentations from issei_sato.
2011年7月11日月曜日
第6回助教の会

第6回目となる今回の数理助教の会は,数理第2研究室の小林佑輔さんで,「点素パス問題に対するアルゴリズム」について発表していただきました.小林さんは組合わせ的問題に対するアルゴリズムの研究を行っていて,より具体的には,グラフ上の問題に対し,それを解くアルゴリズムの計算量の評価および高速化を考えています.こういった問題は,ちょっとした設定の違いでP(多項式時間で解ける)からNP困難に切り替わることがあり,このような問題の解きやすさの変化は大変魅力的であり,自身も興味をもって研究に取り組んでいるとのことです.
今回の発表では,表題のとおりグラフ上の点素パス問題について説明していただきました.点素パス問題とは,上図のように与えられた頂点対に対し,パスが頂点を共有しないようなパス(点素なパス)を見つける問題で,点素パス問題の研究の応用としては,VLSIの設計などが挙げられるそうです.一言で点素パス問題と言っても,グラフが無向グラフか有向グラフか,平面グラフかどうか、頂点対数kが定数か変数かなどの違いで,問題にはいくつかバリエーションが考えられ,それぞれの問題に対してそれを解くための理論的計算量(NP困難か多項式時間で解けるか線形時間で解けるか)が精力的に研究されています.単純なケースとして,頂点対の行き先tが一点である場合は,学部でも習うような最大流アルゴリズムにより多項式時間で解けますが,一般の入力に対しては,計算量の評価は難しいものになるとのことでした.
こういった研究の中で,今回はこの業界の大きな成果である,無向点素パス問題を多項式時間で解くRS(Robertson-Seymour)アルゴリズムについて簡単に紹介していただきました.このアルゴリズムは,まず扱っているグラフに対し木幅というグラフの複雑さの指標を計算し,木幅がある定数より小さければ動的計画法で解き,大きければ頂点を取り除いて木幅をどんどん小さくしていき,点素パスが見つかる(あるいはないことが分かる)までこの操作を繰り返すというもので,これは1980年代から現在に至る23本の論文にわたるグラフマイナー理論のもと完成したアルゴリズムだそうです(下図参照,赤枠のGraph Minors 13 にあるとのこと).ただし,このRSアルゴリズムの計算量はグラフの頂点数nに対しては多項式時間であるものの,頂点対数kに依存する非常に大きな定数がかかるという問題点がありました.
これに対して小林さんは,オイラー的もしくは4辺連結なグラフを考え,この場合の辺素パス問題に対する単純なアルゴリズムを提唱し,これによりオーダー評価における頂点対数kに依存する係数がRSアルゴリズムに比べ非常に小さくなることを示しました.他にも,辺に長さが定義されているようなグラフに対する点素パス問題や,パス同士が隣り合う頂点対を持たないようなパスを見つける問題(誘導点素パス問題)といったものを扱い,それぞれに対して計算複雑度の評価を行っています.
実は僕はこの話を以前もっと短い時間で聞いていて,今回は2回目なのですが,知らない専門用語がたくさん登場するにもかかわらず最後まで楽しんで聞くことができました.そして2回目ですがBreak timeの点素パスは見つけられませんでした.どうも自分にこの手の研究は向いてないようですね.かなりセンスの必要な研究分野だろうなと改めて感じました.
数理第3研究室 助教 相島健助
Jokyo20110711
View more presentations from y-kobayashi.
2011年7月4日月曜日
第5回助教の会

第5回目となる今回の数理助教の会は, 数理第3研究室の相島健助さんに「行列の特異値計算」について発表していただきました. 相島さんは大規模行列の数値計算について, 精度評価や収束の理論的な解析, 新しい手法の提案を行っています. 今回の発表では特異値計算におけるdqds法について詳しく説明してもらいました.
特異値分解は行列の対角化と同様に線型代数で習う話ですが, 応用の場面ではかなりサイズの大きい行列について数値的に求めることになります. 例えば, デジカメ写真のような二次元画像は行列データで表現できますが, 特異値分解を行ってみると, 特異値の多くが十分小さくなるため0に近似できます. このような操作を施して画像に戻すと, 見た目はほとんど変わらずにデータ量が圧縮された画像ができるそうです. これ以外にもサイズの大きいデータを統計的に解析する場合に行列の特異値分解・固有値分解を高速に求める方法が非常に重要だそうです.
特異値分解の数値計算のアルゴリズム自体はすでに幾つかありますが, 相島さんの着目したのは次のような2ステップで特異値を求める方法です.
ステップ1では, 与えられた行列を有理演算と平方根の操作のみで上二重対角行列に変形します. こちらの操作は有限回で終了します. ステップ2では, ステップ1で作った上二重対角行列を特異値が対角成分に並んだ対角行列に変形します. この操作で特異値のすべてが求められます. しかし, ステップ2の操作は一般に有限回の反復では終了せず, 反復回数を増やすことで正しい値に近づけていきます.
ステップ2については, Fernando and Parlett (1994)がdqds法と呼ばれるアルゴリズムを提案しており, 現在,LAPACKなどの数値計算ライブラリで使われています. 反復回数を増やした時に正しい値に収束することは,Rutishauserにより別の反復アルゴリズム(LR法)の流れで間接的に証明されていましたが, 収束速度についての精緻な解析はなされていませんでした.
dqds法の収束速度は各ステップで設定されるシフトと呼ばれるパラメータに依存しており,いかに軽い計算量で(一反復の)収束を加速するシフト量を設定するかを考えるのが重要になります. そこで, 相島さんは, 既に知られているシフト量の設定の仕方(シフト戦略)での収束の速さの詳細な解析,新たなシフト戦略の提案などを行いました. さらに, 最近はdqds法を改良したアグレッシブデフレーション付dqds法を海外の研究者と共同で設計し, 既存のルーチンをさらに高速化しています.
大規模な行列計算を数値的に行う際には収束するだけでなく速さも重要だと改めて感じました. 個別の問題への応用だと, 行列や特異値に構造が入ってくるため, もっと高速化・簡略化できそうですね. そして, 今回は聞けなかったのですがやはり行列の固有値計算とそのアルゴリズムの速さに関する最近の研究も気になります.
数理第4研究室 助教 &さきがけ数学領域研究者(兼任)田中冬彦
2011年6月8日水曜日
第4回助教の会
第4回目となる今回の数理助教の会は,数理第4研究室の田中冬彦さんで,「ベイズ予測とその応用」について発表していただきました.田中さんはJSTさきがけ「数学と諸分野の協働によるブレークスルーの探索」の研究員を兼任されており,統計の理論を理論物理学の研究と結びつけていくことも行なっています.
田中さんの主な研究テーマは「予測する」ということです.「予測」とは,n個のデータが観測されたときに,n+1個目のデータの値の分布を推定することです.推定された分布を「予測分布」と呼びます. 予測分布を用いると, 例えば, コンビニが新規オープンして1週間経過したあと, 7日間の売上データから翌日の売上がどのくらいになるか推測できます. 「明日の売上の期待値は100万円」だけでなく「売上が30万円以下になる確率は10%」といった情報も予測分布から得られます.
予測分布を求めるには,実際にはn個のデータがパラメータθによって定まる, ある確率分布から発生しているという確率モデルを立てて行います. さらに未知パラメータθも事前分布に従っていると仮定することで, ベイズの定理を用いて最適な予測分布(ベイズ予測分布)が構成できます. 先のコンビニの例であれば, 同じ地区の別のコンビニでの売上実績でパラメータの事前分布を求めておき, 実際の売上データと合わせることで, 明日の売上をうまく推測できるそうです. ただし, 新しい地区に初めてコンビニをオープンする場合には事前分布を構成できません.
このような場合に, どのような方法で事前分布を決めるかが理論的にも重要で難しい問題だそうです.一般にはJeffreys事前分布を使うのが汎用的なのですが,優調和事前分布が存在すれば,それを用いることで,Jeffreys事前分布よりもよい予測が可能であることが知られています.ここで問題となってくるのは,そのような優調和事前分布が存在するか,そして,存在するならば具体的に構成できるか,です.
田中さんの発表では,
・時系列分析など相関を持つデータに対するベイズ予測手法
・量子情報で扱うミクロの系への応用
という2つの話題に関して,ベイズ予測と事前分布を軸に話をしてもらいました.
一つ目の話は時系列データの解析です.株価・財務情報や気温などの時系列データは, 実際には互いに独立な確率分布から発生しているわけではありません. 上で述べたこれまでの結果では, データに独立性を仮定して予測を行なっていましたが, 田中さんの研究ではそれを相関をもつ場合に拡張しています.
要点は元の時系列データをスペクトルの世界に変換することです. 田中さんは,スペクトル解析の手法を用いて,時系列解析でよく用いられるAR過程において,必ず優調和事前分布が存在し,かつそれを陽に構成できることを証明しています.他の多くの研究では実問題に合わせて事前分布を発見的に決めているのに対し,田中さんの手法では事前分布の情報がない場合でも,理論的に精度が保証されて
いる事前分布を作ることができます.
二つ目の話は量子情報についてです.量子力学で記述されるようなミクロの系では,電子線の干渉やトンネル現象など,マクロではありえないような不思議な現象が起こります.たとえば,粒子の位置と運動量を観測したときに,それらの測定誤差はマクロの系のように同時確率分布に従いません.今回の発表では,粒子を密度行列や波動関数に対応させてそれらを予測する手法を簡単に紹介してもらいました.これらの予測は,通常のマクロの系のようにこれまでのデータの確率を混ぜ合わせるだけでは不十分で,二乗誤差を最小にして陽に計算する必要があります.時間の都合上簡単な紹介のみで終わってしまいましたが,物理の知識を全て忘れてしまった自分にとってはかなり難しそうでした...
このように田中さんの研究では,統計の理論的な枠組みを時系列解析や量子系に応用するために,概念からきちんと整備する所まで含めて取り組んでいます.最近ではQ-statsというグループを作るなど,統計理論と理論物理の研究者の交流が盛んになってきているそうで,これからの盛り上がりがかなり期待される研究分野でした.
Seminar 110705 v2
View more presentations from tanafuyu.
2011年5月24日火曜日
第3回助教の会

第3回目は数理第二研究室の垣村尚徳さんに「数理計画法における符号可解性(Sign-Solvability in Mathematical Programming)」という題で話していただきました.
発表では,まず,行列の定性的解析のを紹介をしていただきました.それから,それを発展させた組合せ的手法を用いた数理計画問題の定性的解析を紹介いただきました.
行列の定性的解析とは,要素に誤差を含み得る行列の,その誤差に依存しないで決まる性質を解析することです.このような定性的な解析では,行列要素の数値情報は使用できないため,符号情報(行列要素の正負)等の構造的な情報を元に組合せ的手法(グラフ理論等)を用いて解析結果を得ます.このような定性的な解析は1947年に経済学の分野から始まったそうです.
例えば,一般に経済学で価格pは需要D(p)と供給S(p)が釣り合う点D(p)=S(p)で決定される(下図左)と考えられますが,需要がもう一つの変数,嗜好tの増加関数である場合,嗜好tが増減した時に価格pがどのように変化するか,という問題を考えます(下図中央).この時,嗜好tの変化に対する価格pの変化率は下図右のような連立方程式の解として得られますが,その符号は、D(p)やS(p)の具体的な関数形によらずD(p;t)がpに関して減少関数,tに関して増加関数であること,S(p)が増加関数であることから必ず正である(嗜好tが増えれば価格は上昇する)ということがわかります.この一次連立方程式の解の符号をその係数行列の符号のみから判定するという解析は,符号正則性という性質で特徴付けられ,有効グラフの偶閉路の解析や二部グラフの Pfaffian orientations の解析といった組合せ的な手法で解析することが出来るそうです.

上記の行列の定性的解析の考えを,行列を用いて定式化される数理計画問題に応用したものが,組合せ的手法を用いた数理計画問題の定性的解析です.数理計画問題とは,特定の条件を満たす解のうち最適なものを探し出す問題のことであり,多くの現実的な問題が数理計画問題に帰着されています.そのため,その定性的な解析が重要になってきます.例えば,機械を最適に動かすための制御にも数理計画問題が応用されています.そこでは,機械に関して測定された様々な数値データを元に数理計画問題を作り,その数理計画問題の解を元に制御器を作成します.しかしながら,現実の世界の測定結果には誤差が必ず含まれており,得られた制御器の性質はその誤差に影響されているかも知れません.そこで,そのような誤差に影響されない定性的な性質を知る手法が必要になります.垣村さんは,数理計画問題の一種である線形計画問題に対し,その最適解の符号パタンの集合が一意であるか否かという,符号可解性を高速に解析する手法を提案されました.さらに,提案された手法での解析結果を元に,最適解の符号だけでなく最適解そのものも高速に計算する手法を提案されています.組合せ的手法による解析は求解の高速化にも有効であり,応用上重要な今後の研究が非常に楽しみな研究だなと感じました.
数理第3研究室 助教 江本健斗
発表スライド:
2011年5月10日火曜日
第2回助教の会
第二回目は数理第三研究室の江本健斗さんに「準同型に基づくスケルトン並列プログラミング」という題で話していただきました.今回からブログのタイトルが“数理助教「の」会”になりました.
プログラミングの研究とはそもそも,「正しくかつ効率的なプログラムを作る」ことをいろいろな意味で容易にさせることを目的としますが,江本さんはその中でも並列計算プログラミングを支援する枠組みを,データ構造の代数的な側面,特に「準同型」に注目して研究を進めています.逐次的な処理はプログラムが容易でも,時にそれを効率的に並列化させることは自明ではありません.そこで,並列化プログラミングを支援する構造の一つとして「スケルトン」という考え方があります.スケルトンとは並列計算の基本パタンのようなもので,スケルトンを組み合わせることで効率的な並列計算アルゴリズムの設計が容易になります.例えばGoogleのMapReduceが有名です.しかし,ある問題が与えられたときにそれにどうスケルトンを適用すれば良いかという統一的なルールや枠組みがあるわけではありません.江本さんの研究のアイディアは,データ構造を代数系とみなし,オペレータに備わっている準同型性を利用することで,構成的に並列化を実現するというところにあります.準同型性を利用することにより,バッチ処理を並列分散化させる過程があくまで代数的・機械的になされます.これより,対象となるデータ構造とそれに対する処理を書くだけで自動的に並列化させることが可能になります.江本さんはリストのような1次元のデータ構造だけでなく,二次元の代数系に対していかに準同型性を利用した並列化ができるかという研究もされているそうです.一連の研究は,C++のExpression Templateを利用し,SkeToというライブラリとして実装・公開されています.
登録:
投稿 (Atom)
