第１１回助教の会

　第１１回の数理助教の会では数理第６研究室の冨岡亮太さんに「行列およびテンソルデータに対する機械学習」というタイトルでおはなししていただきました。冨岡さんは機械学習の分野において第一線で活躍されている研究者です。また冨岡さんは、この数理助教の会の「いいだしっぺ」であり、この集まりを通じて多岐にわたる領域をカバーする数理工学分野の若手研究者の横のつながりを活発にするためにご尽力されております。

　行列は行と列の２軸上のデータとして見ることができます。さらに軸を増やしたデータはテンソルとよばれます。行列の低ランク分解についてはリコメンデーションに利用される協調フィルタリングなどの重要な応用がよく知られています。その一方で、テンソルに関しては機械学習においてまだ新しい研究対象であり、また最近冨岡さんが活発に取り組んでいる研究テーマだそうです。今回のトークでは、行列に対する判別モデルにおける低ランク分解の応用研究と、テンソルに対する生成モデルにおける基礎理論の研究を紹介していただきました。

　前半のトピックは、ブレイン・ コンピュータ・インタフェース（BCI）における行列の低ランク分解の応用のおはなしです。まず今回扱っている視覚と脳波を用いた文字入力のBCIであるP300 speller システム（Farwell & Donchin, 1988）について解説します。被験者はタテ・ヨコに６つずつ並んだ、計３６個の文字（アルファベット２６文字、１～９までの数字とアンダーバー）のうちの１つを一定時間じっと見続け、その間、ある１行またはある１列にある６文字が同時に光るというパターンがランダムに切り替わります。行と列はそれぞれ６つあるので、光り方のパターンは１２通りとなります。被験者が見ている文字の位置を複数の電極から得られる脳波データを用いて推定することが本システムの目的です。

　冨岡さんらの提案した判別手法では、ある１つの行または列の６文字が光っている短時間の脳波の行列データXについて、被験者が見ている文字が光っているか光っていないかを評価する判別器 f (X) = <X, W> + b を考えます。ここで、W と b を次の条件を満たすように決定します。

　（１）訓練サンプルに対する当てはまりが良い。

　（２）f を決める行列 W が低ランク分解される。

条件（１）に関連して損失項を、条件（２）に関連して正則化項を適切に設定することで、最小化問題を解くことで判別器が決定されます。

　冨岡さんらの提案手法のポイントは、正則化項でSchatten 1-ノルム（行列の特異値の線形和）を用いていることです。これによって考えるべき最小化問題が凸となり、高速に判別器を設計することができます。さらに、行ごと、列ごとのデータを別々に考慮することで、「もっともらしい」時空間フィルタを得ることに成功したそうです。

　後半のトピックはテンソルの低ランク分解です。テンソルは数学的に非自明な点が多く、サイズの小さいテンソルでも扱いが難しい面もあるそうです。テンソルのランクはCANDECOMP / PARAFAC 分解（CP分解）の意味でのランクとTucker分解によるランクなどがあります。

　冨岡さんの研究ではTucker分解を扱っており、またテンソルに対して低ランク化を促す正則化項として、いくつかの行列のSchatten 1-ノルムで表される、overlapped Schatten 1-ノルムを採用しています。このノルムを用いることで、低ランクテンソルの推定が凸最適化により可能となります。例えば、テンソル補完問題はテンソルの一部の値が見えている状況でランクの最小のテンソルを求める問題ですが、テンソル補完に対しoverlapped Schatten 1-ノルムを用いた緩和問題は凸最適化手法で解けるそうです。冨岡さんはテンソル分解に関する理論的な解析を与え、さらに解析結果と実験結果が「そこそこ」一致していることが確認されたとのことです。

　私自身は最適化理論の研究をしているのですが、冨岡さんの研究において最適化問題の扱いやすさがポイントとなっている点が興味深いです。連続最適化の分野と機械学習の分野の積極的な交流（このような交流は国際的にはある程度は進んではいるのですが）によって日本のグループでも面白い研究ができるであろうと感じました。冨岡さんによれば「テンソル業界はまだまだ人手不足」だそうですので、新しい領域に乗り込む意欲のある方は挑戦してみてはいかがでしょうか？

生産技術研究所 最先端数理モデル連携研究センター 永野清仁

行列およびテンソルデータに対する機械学習（数理助教の会 2011/11/28）

View more presentations from ryotat

第１０回助教の会

　第１０回助教の会は、生産技術研究所　最先端数理モデル連携研究センター　特任助教の永野清仁さんにお話してもらいました。永野さんは、数理第２研究室のご出身で、２００８年３月に博士号を取得され、離散アルゴリズムの研究に従事しておられます。最近は、機械学習と関連した離散最適化問題などを扱っているそうです。

　今回は、永野さんの研究テーマである、「劣モジュラ制約下の凸最適化」について、理論および応用の両側面での研究についてそれぞれ話していただきました。

　劣モジュラ関数とは、集合を引数に取る関数fで、「大きな集合に要素を加えるよりも、小さな集合に要素を加えたほうが影響が大きい」という性質を（数式では、∀S, T⊆V, f(S)+f(T)≧f(S∪T)+f(S∩T)と表される）持つもので、この劣モジュラ関数の理論は、グラフ、ネットワーク、ゲーム理論、オークション理論、機械学習など、様々な場面で使われているそうです。

　劣モジュラ関数fの例として、集合に対する２つのコスト関数の例を説明していただきました。一つは、「ホットドックの代金」、例えば「Aさんが2個、Bさんが4個、Cさんが8個のホットドックを食べるときに、必要なお金」であり、これは、それぞれの代金の和となります。（f(AさんとBさん)=f(Aさん)+f(Bさん）、など。）もう一つは、「コピーフリーのCDの代金」、例えば、「Aさんが2枚、Bさんが4枚、Cさんが8枚のCDを手に入れる時に、必要なお金」であり、これは、どの場合でも、CD1枚分の値段のままになります。（f(AさんとBさん)=f(Aさん)=f(Bさん)=定数。）いずれのfも劣モジュラ関数ですが、さらに、この両極端の場合の中間にも、様々なコスト関数を定義することができます。

　このようなfが決まると、それに対して「基多面体」B(f)と呼ばれるものが定義でき、この基多面体の上で、「もっとも良い点」（良さは、B(f)上の各点に対する関数g(x)で決まる）を見つけるのがすなわち「劣モジュラ制約下の凸最適化」ということです。

　g(x)には様々なものがあり、例えばLexicographically optimal bases (Fujishige,80)という有名な問題（これは、「なるべく中心に近い点を見つける」という問題で、様々なタスクが、この形式で表現できるそうです。）があるのですが、永野さんらは、α-カーブというアイデアに基づいて、このLexicographically optimal basesの問題が、Submodluar Utility Allocation (SUA)という、一見別の問題設定と、最適解が一致するということを発見したそうです。

　発表の後半では、この理論を、実際にネットワークの分析に応用した例を紹介していただきました。応用するのは、「最密部分グラフ問題」すなわち、「与えられたノード数の部分グラフの中で、最もエッジ重みの合計が大きいもの」を見つける問題です。この「与えられたノード数」というのが厄介で、これがなければ簡単に（多項式時間で）解けるのに、この制約があるととたんに難しく（NP-hardに）なるそうです。永野さんらは、制約なしの場合に使われる「Fujishige-Wolfe法」を拡張することで、「さまざまなノード数について、もしも最適解が見つかれば、それを出力する」というアルゴリズムを設計しました。Fujishige-Wolfe法では活用しきれていなかった情報をより「しゃぶりつくす」ことで、Fujishige-Wolfe法では出せていなかった答を出力させることができるそうです。必ず最適解が見つかるわけではありませんが、もし見つかれば高速に答えを見つけることができます。

　このFujishige-Wolfe法は、まさに前半のお話にあった、「基多面体上での最適化」に基づくアルゴリズムであり、通常の多項式時間アルゴリズムでは現実的には解けないような大きな問題まで解くことができるそうです。「最適解がもしも見つかれば、それを出力する」というアルゴリズムはなかなか変わっていて、面白いと思いました。

　劣モジュラの理論は、頭の普段使わない部分を使う感じで難しかったのですが、永野さんの力強い発表のおかげで、なんとなくやりたいことの気持ちがわかってきたような気がします。構造の複雑そうなグラフの問題が、きれいな理論で表現できる様子が魅力的でした。

情報基盤センター　助教　吉田稔

Nagano jokyoukai

View more presentations from kiyohito_nagano.

第9回助教の会

こんにちわ、先月の頭に風邪をひいたのに、今月の頭も風邪を引いたので、来月の頭が心配な東大情報基盤センターの佐藤です。

第9回助教の会では、東京大学　情報基盤センターの吉田稔さんに「接尾辞配列とディリクレ過程混合モデルを用いたテキスト中の数値表現マイニング」というタイトルで話していただきました。吉田さんは、東京大学の元辻井研で博士号を取得しており、主にテキストマイニングの研究をしています。

今回の発表では、「テキストマイニング」についての説明から始まり、東京大学中川研で公開しているテキストマイニングツールの説明とご自身が取り組んでいる数値情報と言語情報を解析する研究について、説明をしていただきました。

吉田さんの説明によると

「テキストマイニングとは、テキストデータを統計的に処理し、自明でない知見を発見する技術」のことを言います。

発表中には、「自然言語処理」と「テキストマイニング」の関係についての議論が為されました。吉田さんの認識では、自然言語処理を基礎技術として応用したのがテキストマイニングである一方で、テキストマイニングで得られた知見を自然言語処理へと活かすという相補的な関係にあるようです。

吉田さんの現在の研究テーマは、「テキスト中に含まれる数値表現をデータベースとして扱う研究」です。

テキスト中に含まれる数値表現を陽にデータベース化することなく、テキストのままデータベースとして扱うことで、言語と数値の関係を抽出する研究を行っています。

言語と数値の関係では、

例えば、年齢ごとに「人」に関する呼び名が変わる現象が挙げられます。

[12〜19]歳という数値表現で表された「男性/女性」は「少年/少女」という単語に関係しており、

[65〜歳]という数値表現で表された人間は、「高齢者」という単語に関係しています。

このような関係をテキストデータから自動で抽出することができるシステムの開発をしているそうです。

また、「75歳男性が脳梗塞で死亡」などのテキストデータが大量にある場合に

「男性」,「脳梗塞」という単語から、[60-75]歳という統計処理された数値表現データを抽出することも可能になります。

実際にシステムで使われている技術は、suffix arrayを数値データを扱いやすいように改良したデータ構造や、数値表現から抽出した数値データを統計処理するためにディリクレ過程混合モデルを検索時にリアルタイムに用いるなど、データ構造と機械学習技術の実践的な融合がなされていると感じました。

第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研究室　冨岡亮太

第７回助教の会

第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.

第６回助教の会

第6回目となる今回の数理助教の会は，数理第2研究室の小林佑輔さんで，「点素パス問題に対するアルゴリズム」について発表していただきました．小林さんは組合わせ的問題に対するアルゴリズムの研究を行っていて，より具体的には，グラフ上の問題に対し，それを解くアルゴリズムの計算量の評価および高速化を考えています．こういった問題は，ちょっとした設定の違いでP（多項式時間で解ける）からNP困難に切り替わることがあり，このような問題の解きやすさの変化は大変魅力的であり，自身も興味をもって研究に取り組んでいるとのことです．



今回の発表では，表題のとおりグラフ上の点素パス問題について説明していただきました．点素パス問題とは，上図のように与えられた頂点対に対し，パスが頂点を共有しないようなパス（点素なパス）を見つける問題で，点素パス問題の研究の応用としては，VLSIの設計などが挙げられるそうです．一言で点素パス問題と言っても，グラフが無向グラフか有向グラフか，平面グラフかどうか、頂点対数kが定数か変数かなどの違いで，問題にはいくつかバリエーションが考えられ，それぞれの問題に対してそれを解くための理論的計算量（NP困難か多項式時間で解けるか線形時間で解けるか）が精力的に研究されています．単純なケースとして，頂点対の行き先tが一点である場合は，学部でも習うような最大流アルゴリズムにより多項式時間で解けますが，一般の入力に対しては，計算量の評価は難しいものになるとのことでした．

こういった研究の中で，今回はこの業界の大きな成果である，無向点素パス問題を多項式時間で解くRS(Robertson-Seymour)アルゴリズムについて簡単に紹介していただきました．このアルゴリズムは，まず扱っているグラフに対し木幅というグラフの複雑さの指標を計算し，木幅がある定数より小さければ動的計画法で解き，大きければ頂点を取り除いて木幅をどんどん小さくしていき，点素パスが見つかる（あるいはないことが分かる）までこの操作を繰り返すというもので，これは1980年代から現在に至る23本の論文にわたるグラフマイナー理論のもと完成したアルゴリズムだそうです（下図参照，赤枠のGraph Minors 13 にあるとのこと）．ただし，このRSアルゴリズムの計算量はグラフの頂点数nに対しては多項式時間であるものの，頂点対数kに依存する非常に大きな定数がかかるという問題点がありました．



これに対して小林さんは，オイラー的もしくは４辺連結なグラフを考え，この場合の辺素パス問題に対する単純なアルゴリズムを提唱し，これによりオーダー評価における頂点対数kに依存する係数がRSアルゴリズムに比べ非常に小さくなることを示しました．他にも，辺に長さが定義されているようなグラフに対する点素パス問題や，パス同士が隣り合う頂点対を持たないようなパスを見つける問題（誘導点素パス問題）といったものを扱い，それぞれに対して計算複雑度の評価を行っています．

実は僕はこの話を以前もっと短い時間で聞いていて，今回は２回目なのですが，知らない専門用語がたくさん登場するにもかかわらず最後まで楽しんで聞くことができました．そして２回目ですがBreak timeの点素パスは見つけられませんでした．どうも自分にこの手の研究は向いてないようですね．かなりセンスの必要な研究分野だろうなと改めて感じました．

数理第３研究室 助教 相島健助

Jokyo20110711

View more presentations from y-kobayashi.

第５回助教の会

第５回目となる今回の数理助教の会は, 数理第３研究室の相島健助さんに「行列の特異値計算」について発表していただきました. 相島さんは大規模行列の数値計算について, 精度評価や収束の理論的な解析, 新しい手法の提案を行っています. 今回の発表では特異値計算におけるdqds法について詳しく説明してもらいました.

特異値分解は行列の対角化と同様に線型代数で習う話ですが, 応用の場面ではかなりサイズの大きい行列について数値的に求めることになります. 例えば, デジカメ写真のような二次元画像は行列データで表現できますが, 特異値分解を行ってみると, 特異値の多くが十分小さくなるため0に近似できます. このような操作を施して画像に戻すと, 見た目はほとんど変わらずにデータ量が圧縮された画像ができるそうです. これ以外にもサイズの大きいデータを統計的に解析する場合に行列の特異値分解・固有値分解を高速に求める方法が非常に重要だそうです.

特異値分解の数値計算のアルゴリズム自体はすでに幾つかありますが, 相島さんの着目したのは次のような２ステップで特異値を求める方法です.



ステップ１では, 与えられた行列を有理演算と平方根の操作のみで上二重対角行列に変形します. こちらの操作は有限回で終了します. ステップ２では, ステップ１で作った上二重対角行列を特異値が対角成分に並んだ対角行列に変形します. この操作で特異値のすべてが求められます. しかし, ステップ２の操作は一般に有限回の反復では終了せず, 反復回数を増やすことで正しい値に近づけていきます.

ステップ２については, Fernando and Parlett (1994)がdqds法と呼ばれるアルゴリズムを提案しており, 現在，LAPACKなどの数値計算ライブラリで使われています. 反復回数を増やした時に正しい値に収束することは，Rutishauserにより別の反復アルゴリズム（LR法）の流れで間接的に証明されていましたが, 収束速度についての精緻な解析はなされていませんでした.



dqds法の収束速度は各ステップで設定されるシフトと呼ばれるパラメータに依存しており，いかに軽い計算量で（一反復の）収束を加速するシフト量を設定するかを考えるのが重要になります. そこで, 相島さんは, 既に知られているシフト量の設定の仕方（シフト戦略）での収束の速さの詳細な解析，新たなシフト戦略の提案などを行いました. さらに, 最近はdqds法を改良したアグレッシブデフレーション付dqds法を海外の研究者と共同で設計し, 既存のルーチンをさらに高速化しています.

大規模な行列計算を数値的に行う際には収束するだけでなく速さも重要だと改めて感じました. 個別の問題への応用だと, 行列や特異値に構造が入ってくるため, もっと高速化・簡略化できそうですね. そして, 今回は聞けなかったのですがやはり行列の固有値計算とそのアルゴリズムの速さに関する最近の研究も気になります.

Jokyonokai

View more presentations from nwpmq516

数理第４研究室 助教 ＆さきがけ数学領域研究者（兼任）田中冬彦

第４回助教の会

第４回目となる今回の数理助教の会は，数理第４研究室の田中冬彦さんで，「ベイズ予測とその応用」について発表していただきました．田中さんはJSTさきがけ「数学と諸分野の協働によるブレークスルーの探索」の研究員を兼任されており，統計の理論を理論物理学の研究と結びつけていくことも行なっています．

田中さんの主な研究テーマは「予測する」ということです．「予測」とは，n個のデータが観測されたときに，n+1個目のデータの値の分布を推定することです．推定された分布を「予測分布」と呼びます. 予測分布を用いると, 例えば, コンビニが新規オープンして１週間経過したあと, ７日間の売上データから翌日の売上がどのくらいになるか推測できます. 「明日の売上の期待値は１００万円」だけでなく「売上が３０万円以下になる確率は１０％」といった情報も予測分布から得られます.

予測分布を求めるには，実際にはn個のデータがパラメータθによって定まる, ある確率分布から発生しているという確率モデルを立てて行います. さらに未知パラメータθも事前分布に従っていると仮定することで, ベイズの定理を用いて最適な予測分布（ベイズ予測分布）が構成できます. 先のコンビニの例であれば, 同じ地区の別のコンビニでの売上実績でパラメータの事前分布を求めておき, 実際の売上データと合わせることで, 明日の売上をうまく推測できるそうです. ただし, 新しい地区に初めてコンビニをオープンする場合には事前分布を構成できません.

このような場合に, どのような方法で事前分布を決めるかが理論的にも重要で難しい問題だそうです.一般にはJeffreys事前分布を使うのが汎用的なのですが，優調和事前分布が存在すれば，それを用いることで，Jeffreys事前分布よりもよい予測が可能であることが知られています．ここで問題となってくるのは，そのような優調和事前分布が存在するか，そして，存在するならば具体的に構成できるか，です．

田中さんの発表では，
・時系列分析など相関を持つデータに対するベイズ予測手法
・量子情報で扱うミクロの系への応用
という２つの話題に関して，ベイズ予測と事前分布を軸に話をしてもらいました．

一つ目の話は時系列データの解析です．株価・財務情報や気温などの時系列データは, 実際には互いに独立な確率分布から発生しているわけではありません. 上で述べたこれまでの結果では, データに独立性を仮定して予測を行なっていましたが, 田中さんの研究ではそれを相関をもつ場合に拡張しています.

要点は元の時系列データをスペクトルの世界に変換することです. 田中さんは，スペクトル解析の手法を用いて，時系列解析でよく用いられるAR過程において，必ず優調和事前分布が存在し，かつそれを陽に構成できることを証明しています．他の多くの研究では実問題に合わせて事前分布を発見的に決めているのに対し，田中さんの手法では事前分布の情報がない場合でも，理論的に精度が保証されて
いる事前分布を作ることができます．

二つ目の話は量子情報についてです．量子力学で記述されるようなミクロの系では，電子線の干渉やトンネル現象など，マクロではありえないような不思議な現象が起こります．たとえば，粒子の位置と運動量を観測したときに，それらの測定誤差はマクロの系のように同時確率分布に従いません．今回の発表では，粒子を密度行列や波動関数に対応させてそれらを予測する手法を簡単に紹介してもらいました．これらの予測は，通常のマクロの系のようにこれまでのデータの確率を混ぜ合わせるだけでは不十分で，二乗誤差を最小にして陽に計算する必要があります．時間の都合上簡単な紹介のみで終わってしまいましたが，物理の知識を全て忘れてしまった自分にとってはかなり難しそうでした．．．

このように田中さんの研究では，統計の理論的な枠組みを時系列解析や量子系に応用するために，概念からきちんと整備する所まで含めて取り組んでいます．最近ではQ-statsというグループを作るなど，統計理論と理論物理の研究者の交流が盛んになってきているそうで，これからの盛り上がりがかなり期待される研究分野でした．

Seminar 110705 v2

View more presentations from tanafuyu.

第３回助教の会

第３回目は数理第二研究室の垣村尚徳さんに「数理計画法における符号可解性（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研究室 助教 江本健斗

発表スライド：

第３回数理助教の会

View more presentations from Naonori Kakimura

第２回助教の会

第二回目は数理第三研究室の江本健斗さんに「準同型に基づくスケルトン並列プログラミング」という題で話していただきました．今回からブログのタイトルが“数理助教「の」会”になりました．

プログラミングの研究とはそもそも，「正しくかつ効率的なプログラムを作る」ことをいろいろな意味で容易にさせることを目的としますが，江本さんはその中でも並列計算プログラミングを支援する枠組みを，データ構造の代数的な側面，特に「準同型」に注目して研究を進めています．逐次的な処理はプログラムが容易でも，時にそれを効率的に並列化させることは自明ではありません．そこで，並列化プログラミングを支援する構造の一つとして「スケルトン」という考え方があります．スケルトンとは並列計算の基本パタンのようなもので，スケルトンを組み合わせることで効率的な並列計算アルゴリズムの設計が容易になります．例えばGoogleのMapReduceが有名です．しかし，ある問題が与えられたときにそれにどうスケルトンを適用すれば良いかという統一的なルールや枠組みがあるわけではありません．江本さんの研究のアイディアは，データ構造を代数系とみなし，オペレータに備わっている準同型性を利用することで，構成的に並列化を実現するというところにあります．準同型性を利用することにより，バッチ処理を並列分散化させる過程があくまで代数的・機械的になされます．これより，対象となるデータ構造とそれに対する処理を書くだけで自動的に並列化させることが可能になります．江本さんはリストのような１次元のデータ構造だけでなく，二次元の代数系に対していかに準同型性を利用した並列化ができるかという研究もされているそうです．一連の研究は，C++のExpression Templateを利用し，SkeToというライブラリとして実装・公開されています．

Homomorphism-based Skeletal Parallel Programming

View more presentations from emoken34.

「助教会」のブログをはじめるにあたって

皆さんはじめまして。

「助教会」というと耳慣れない言葉だなと思われたかもしれません。この会は東京大学の本郷キャンパスにある数理情報学専攻の助教が定期的に集まってお互いの研究の情報交換をしようと今月 (2011年4月) 立ち上がったものです。

今までそういう会がなかったのか？同じ専攻なのにお互いの研究内容を知らないの？と不思議に思われるかもしれませんが、実際その通りでした。

せっかく集まって研究の話をするので、その成果を外部の方にも分かりやすい形で公開しようという趣旨でこのブログを立ち上げました。

また、研究室選び、学科選び（東大には進学振り分けという仕組みがあります）の参考にして頂けるかなということや、そもそも助教という人種が何を考え、何に熱中しているのか（面白いかどうかはともかく）知っていただけたらという動機もあります。

実際「数理情報学」って何ですか？と聞かれたときに一言で答えるのは難しいです。「現実問題を数学的にモデル化して・・・」はいもう十分ですよね（興味のある方はこの本を見てみて下さい）。このブログではひとりひとりの研究にフォーカスしてその味わいどころ、と「数理」がどう現実社会に繋がっているか、を少しでもお伝えできたらなと思います。

数理第6研究室 助教 冨岡亮太

第1回助教会

記念すべき数理助教会のトップバッターは第5研究室の鈴木大慈さんです。今日の発表のタイトルは "Theory for Information Integration in Statistical Learning" で日本語で言うと「統計的学習における情報統合の理論」というところでしょうか。

発表の内容は盛りだくさんの3本立てで、

1. ベイズ推定の事前分布をどう決めるかという話
2. 相互情報量を用いた特徴選択法の話
3. 複数のカーネルを用いたカーネル法の性能解析の話

とどれも1回分くらいの広がりのありそうな話です。情報統合というのは色々な意味で使われる言葉だと思いますが、今日の発表の中では (a) 複数の学習機械をベイズ推定の枠組みの中で組み合わせること、(b) 複数の情報源があるときにうまく有用な情報を組み合わせ、不要な情報を捨てることという2種類の意味で使われていたように思います。1は(a)の話で2と3は(b)の話です。

1. の話の背景にはベイズ推定というものがあります。ベイズ推定では事前分布をどう選ぶかが問題となるのですが、事前分布というのは答えがどこにありそうか、あらかじめあたりを付けておくようなものなので答えが分からないときは一様にしておくのが良さそうです。この一様な分布をここではJefferys事前分布と言いますが、この話の味わいどころは対象とするモデル（というのは何らかのパラメータをもつ確率分布の集合）の幾何学的な形状によってはJefferys事前分布を性能で常に上回る事前分布が作れるというところです。このような事前分布が作れるかどうかはモデルの上のラプラシアンで決まるランダムウォークが再帰性を持たないことが必要十分条件です。鈴木さんはすでに得られていた結果[1]を一般のα-ダイバージェンスを評価基準とした場合のβ-事後分布に拡張しました[2]。この時α≠βの場合にランダムウォークにラプラシアンによる拡散項だけでなく、一種のドリフト項が現れるのだそうです。


スライド前半:

Jokyokai

View more presentations from trinmu

スライド後半:
jokyokai2



参考文献
[1] "Shrinkage Priors for Bayesian Prediction." F. Komaki. The Annals of Statistics, 34(2), 808-819, 2006.
[2] "On prior selection and covariate shift of β-Bayesian prediction under α-divergence risk." T Suzuki and F. Komaki. Communications in Statistics --- Theory and Methods, 2010.