オンライン予測における次元圧縮に関する研究

点击翻译按钮获取中文摘要

これまで,オンライン予測の問題に対し,ほぼ最適な予測値系列を出力するさまざまな重み更新アルゴリズムが開発されている.これらのアルゴリズムは,各時刻tにおいて重みベクトルw_t∈R^Nを保持し,新しい観測データx_t∈R^Nが与えられると,内積演算(w_t・x_t)に基づいて予測値を出力し,重みをw_<t+1>に更新するという共通の性質を持つ.本研究では,ある構造を持つ問題が,適当な変換φ:R^n→R^Nによって高次元空間(N≫n)に写像されたベクトルx_t=φ(z_t)(z_tは実際の観測データ)に対するオンライン予測の問題とみなせることに着目し,写像φを陽に用いずに予測アルゴリズムを効率よく模倣できるための条件について調べた.特に,重みベクトルもw_t=φ(v_t)のように低次元空間におけるベクトルv_tを用いて間接的に表すことができれば,内積w_t・x_t=φ(z_t)・φ(v_t)はz_tとv_tの関数(カーネル)となり,φの計算を行なわずに効率よく計算できる可能性がある.まず,有効グラフの道に基づいて定まる変換φを持つ自然な問題のクラスを提案し,カーネル演算と重み更新が効率よく計算できるための条件を与えた.特に,トラフィックの状況が刻々と変化するネットワーク環境において,ほぼ最適なルーティング経路を動的に見つける問題や,決定グラフの最適な枝刈りを求める問題に対する効率の良いアルゴリズムを与えた.また,この結果を,正規表現に基づくカーネルという概念を用いて一般に表すことができることを示した.さらに,高次元空間Nから低次元空間kへの変換Rについても考察し,ランダム行列によって定義されるRが2点間のユークリッド距離をほぼ保存するという性質を用いて,線形分離関数の効率の良い学習アルゴリズムを設計した.このとき,ランダム行列の各成分は4限定独立であればよく,n=logN次元ランダムベクトルからある変換φによって作ることができる.このφは非線形変換であるため,n次元空間では非線形分離であるサンプルをN次元空間では線形分離したサンプルに写像する能力を有する.これにより,カーネル手法に代わる新しい非線形学習方式を提案した.