2012年6月13日水曜日

第15回助教の会


第15回助教の会では公立はこだて未来大学の田中健一郎さんに発表していただきました.田中さんは2007年3月に東京大学大学院情報理工学系研究科数理情報学専攻にて博士号を取得後,東京海上日動火災保険株式会社に就職.2011年4月より公立はこだて未来大学システム情報科学部複雑系知能学科の助教として研究活動をされています.大学院時代の同期である数理4研助教の田中冬彦さんの仲介により今回の発表が実現しました.発表タイトルは「微分作用素に対するHillの方法の収束次数および明示的な誤差上界」ということで,微分方程式に対する数値解法であるスペクトル法,特にHillの方法に関する研究成果のお話でした.

物理的な現象や社会的な現象の中には微分方程式により記述されるものが多くあります.本発表で出てくる波の挙動はその代表的な例といえます.微分方程式の数値解法としてはスペクトル法の他に差分法や有限要素法がよく知られています.スペクトル法の特徴は,他の手法と比べて非常に精度よく解を近似できることです.田中さんの研究は,Hillの方法による近似誤差の収束次数と上界に関する理論的な結果を与えています.特に,誤差上界の評価については,スペクトルの真値を利用しないことで計算可能な上界が得られています.数値手法を実際に利用する上で理論的な評価は重要な指針となります.本発表の主結果(の一部)は次の通りです.

図1:主結果

具体的な問題設定は以下の通りです(図2).まず,対象は非線形波動方程式です.この非線形波動方程式を定常解の周りで線形近似することにより,摂動$\eta$を使って解$\zeta$の安定性を調べることが目的です.ここではさらに$\eta(x,t)=\Psi(x)\exp(\lambda t)$を仮定して,時刻に依存しない関数$\Psi$の微分方程式へと変形します.今,解の安定性は微分作用素$S_p$のスペクトル,特にその実数部分の正負で判定されます.つまり,スペクトルの実部が負であれば安定,正であれば安定ではないということです.以上より,問題は微分方程式$S_p\Psi = \lambda \Psi$を数値的に解くことに帰着し,あとはこの微分方程式を数値的に解けばよいことになります.そして田中さんは,Hillの方法による近似を考え,その収束次数と誤差上界を理論的に導出しています.

図2:非線形方程式の変形


Hillの方法はもともと1886年にHillにより提唱されましたが,有効な数値計算手法として認識されたのはごく最近になってからの話だそうです.Hillの方法による近似は
1. Floquet-Bloch分解
2. Fourier級数による近似
の2段階で行われます.まず,Floquet-Bloch分解の概要を図3に示します.Floquet-Bloch分解をなぜ行うかというと,それは作用素$S_p$が連続スペクトルをもち直接的な解析が難しいためです.Floquet-Bloch分解では,非周期性を指定するパラメータ$\mu$の値に応じて周期解と微分作用素$S_p^{\mu}$を考えます.パラメータ$\mu$の値を変化させることで作用素$S_p$のスペクトルがすべて現れ,$\mu$の値ごとに作用素$S_p^{\mu}$が点スペクトルだけをもつので解析がしやすくなります(図4).

図3:Floquet-Bloch分解(その1)
図4:Floquet-Bloch分解(その2)

Fourier級数による近似では,周期関数を使って周期解を無限級数展開し,$2N+1$項の有限打ち切りによる近似を行います(図5).Hillの方法により,微分方程式$S_p\Psi = \lambda \Psi$という問題がパラメータ$\mu$ごとに$2N+1$次正方行列の固有値問題に帰着されます.

図5:Fourier級数による近似


固有値問題の解ともとの問題$S_p\Psi = \lambda \Psi$のスペクトルとの誤差を評価するために,田中さんは誤差を「固有値問題の固有関数ともとの問題の固有関数との誤差」と「Fourier近似による誤差」の2つに分解しました(図6).後者についてはFourier解析の一般論から誤差の評価が得られます.前者の評価にはGershgorinの定理とDunford積分という2つの道具が使われています.Gershgorinの定理は固有値の存在する範囲を教える定理であり,Dunford積分は複素解析における留数の定理を作用素に対して考えたようなものとのことです.上界の評価においては,収束次数の評価で用いた手法に工夫を加え,スペクトルの真値を直接利用しないことで明示的な上界を与えています.以上より精度誤差の収束次数と上界に関する主結果を得ます.

図6:精度誤差評価のためのアイデア

例題について,近似誤差と田中さんの与えた上界との比較結果も紹介されました(図7).

図7:精度誤差と上界との比較

今回の田中さんの発表では「実際に計算できるもので評価する」という点が強調されていたように思います.誤差の理論的な評価は数値手法に関する重要な指標です.特に,実際に計算して使える指標の存在はやはり心強いものだと思います.大変興味深く面白いお話でした.


数理5研助教 廣瀬善大



2012年6月8日金曜日

第14回助教の会

今年度より助教の会に入会した林です.5月28日に行われた第14回助教の会では廣瀬善大さんに "Dimension Reduction Based on the Geometry of Dually Flat Spaces" (双対平坦空間の幾何学に基づいた次元削減)というタイトルで発表していただきました.

廣瀬さんは昨年度3月に東京大学の数理5研で博士号を取得され,今年度より同研究室で助教に着任されました.

今回のお話は廣瀬さんの博士課程での研究成果をまとめたもので,一言でいうと Least Angle Regression (LARS, 最小角回帰法) の幾何学的な拡張と具体的な確率モデルへの応用について発表されました.発表の前半ではLARSの解説とその拡張について,後半ではグラフィカルガウシアンモデルへの応用が紹介されています.

そもそものモチベーションとして,統計モデルを学習させるときに疎(スパース)な解を得たいというものがあります.例えば,線形回帰の問題では入力Xと出力yの組に対して線形な関係を仮定し,二乗誤差が最小となるような重みパラメータを求めます(最尤推定).この求められた重みの強さによってどの特徴量がyの予測に役立っているかを知ることができますが,重みが疎,すなわち多くの値が0で埋まっていればyと関係する特徴量を簡単に絞り込むことができます.一般的に線形回帰で求められた解は疎にならないため,L1ノルムによる正則化項を付け加える(LASSO)などなんらかの工夫が必要となります.

LARSは線形回帰の解を疎に求めるアルゴリズムとして2004年に提案されました.
  • Efron, Hastie, Johnstone and Tibshirani: Least Angle Regression (with discussion). Annals of Statistics, vol. 32 (2004), pp. 407-499.
LARSによるパラメータ推定の手順は一種の繰り返しアルゴリズムになっています.通常の最尤推定値を$\bar{y}$としたとき,LARSは予測に使う特徴量を一つづつモデルに加えていき,原点から$\bar{y}$にいたるまでのパスを計算します.具体的なアルゴリズムは以下になります.またアルゴリズムの具体例を図1に示します.
  1. すべての特徴量を使わない状況,すなわちすべての重みを0としてスタート.
  2. まだ使っていない特徴量のうち,相関が一番大きい特徴量を基底に加える.
  3. 基底に入っている特徴量と$\bar{y}-\hat{\mu}$との相関を考える.$\hat{\mu}$がその上を動くような直線として,これらの相関が互いに等しいままであるような直線をとる(角の二等分線に相当する直線).使っていない特徴量のうち,これらの相関と同じだけ大きい相関をもつ特徴量が現れたら,2.に移る.
  4. 推定値$\hat{\mu}$が$\bar{y}$に到達するまで2.と3.を繰り返す.
このアルゴリズムをk回目で止めるとk個の非ゼロな重みをもつパラメータを得ることができるため,ユーザは任意の疎な解を得ることができます.
図1:LARSによって得られるパス(赤線)

廣瀬さんはLARSのアイデアを情報幾何の世界で解釈しなおし,他の統計モデルにとって自然な拡張を行いました.LARSはパスを求める際,角の二等分線というユークリッド幾何的な性質を用いており,この性質は線形回帰と相性がいいものですが,一般の統計モデルにとってはそうとは限らないからです.LARSは角度という幾何的性質を用いたアルゴリズムですが,廣瀬さんはこの代わりに距離を用いてLARSの拡張を行いました.具体的にはKL擬距離という確率分布にとって自然な距離を導入し,一般化線形モデルやグラフィカルガウシアンモデル(GGM)に応用されました.(この記事では深くは立ち入りませんが,情報幾何とはユークリッド幾何を一般化したもので,ある確率分布がある一点として表現されるような空間を扱う学術体系です.)

発表の後半ではGGMへの応用が紹介されました.GGMは複数の変数が与えられたとき,ある2変数の間に(他の変数が与えられた下での)条件付き独立性があるかないかを調べるときに用いられるモデルです.具体的にはすべての変数は1つの多次元ガウス分布から生成されたと仮定し,推定された精度行列(共分散行列の逆行列)が0であれば対応する変数間には条件付き独立性がないと考えます.変数の数が増えるにしたがってその組み合わせの数も増加するため,ここでもやはり疎な解が歓迎されます.
図2:提案手法の実験結果
実データを用いた実験もいくつか紹介されました.その1つは学生88人の数学5科目の成績から科目間の条件付き独立性を調べたもので,図2は実際に提案手法によって得られた結果を示しています.2科目間の条件付き独立性の有無がグラフ上の辺によって表現されており,たとえば代数と解析の従属性が強いとされるなど興味深い結果となっています.シミュレーションでは提案手法が既存手法よりも優れた予測精度を達成したことが示されています.

今回の廣瀬さんのお話は,線形回帰モデルにのみ用いられてきたLARSアルゴリズムを一般の統計モデルに対しても使えるよう拡張されたという点で,非常に意義深いと感じました.自分も含め,最近は確率モデルや統計モデルを用いた研究はとても一般的になってきたため,ユーザの立場からもこのような一般化はありがたいのではないでしょうか.ただ,提案手法の計算量はそこそこかかってしまう(GGMの場合,変数の数の二乗のオーダ)と伺ったので,今後は計算の効率化にぜひ期待させていただきたいと思いました.

数理第6研究室 林浩平