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

在线预测降维研究

• 批准号: 13780185
• 负责人: 瀧本 英二
• 金额: $ 1.41万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780185/
• 关键词: オンライン予測; 重み更新アルゴリズム; カーネル; ランダムプロジェクション; 情報圧縮; 次元圧縮

これまで,オンライン予測の問題に対し,ほぼ最適な予測値系列を出力するさまざまな重み更新アルゴリズムが開発されている.これらのアルゴリズムは,各時刻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次元空間では線形分離したサンプルに写像する能力を有する.これにより,カーネル手法に代わる新しい非線形学習方式を提案した.

迄今为止，已经开发了各种重量更新算法，以输出在线预测问题的几乎最佳预测序列。这些算法在每次t时具有保持权重向量w_t∈R^n的共同属性，当给出新的观察数据x_t∈R^n时，根据内部产品操作（W_T ・ x_t）输出预测值并将权重更新为W_ <t+1>。在这项研究中，通过适当的转换φ：r^n→r^n将某个结构的问题映射到高维空间（N≫N）中。我们关注以下事实：它可以被视为=φ（z_t）的在线预测问题（z_t是实际观察数据），并研究了有效地模仿预测算法的条件，而无需明确使用MAPφφ。特别是，如果还可以在低维空间中使用矢量V_T间接表示，例如w_t =φ（v_t），则内部产品W_T，X_T =φ（Z_T）和φ（Z_T）和φ（v_t）成为Z_T和V_T的函数（kernels），并且可以计算得出计算效率。首先，根据有效图的路径，我们提出了一类具有定义转换φ的自然问题，并为有效计算内核操作和重量更新提供了条件。特别是，在交通情况之间不断变化的网络环境中，我们为动态找到几乎最佳路由路径并找到决策图的最佳修剪的问题提供了有效的算法。我们还证明，该结果通常可以使用基于正则表达式的内核概念来表达。此外，我们还检查了从高维空间n到低维空间k的转换R，并使用由随机矩阵定义的r属性几乎可以保留两个点之间的欧几里得距离，我们为线性分离功能设计了有效的学习算法。在这种情况下，如果随机矩阵的每个组件都限制为四个，则可以由n = logn维随机矢量的变换φ创建。由于φ是一种非线性变换，因此它具有将N维空间中非线性分离的样品映射到N维空间中线性分离的样品的能力。这暗示了一种新的非线性学习方法来替换内核方法。

项目成果

Eiji Takimoto, Akira Maruoka: "Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme"Theoretical Computer Science. 261・1. 179-209 (2001)

Eiji Takimoto、Akira Maruoka：“通过动态规划方案预测决策树的最佳剪枝”理论计算机科学 261・1（2001）。

Eiji Takimoto, Akira Maruoka: "Top Down Decision Tree Boosting and Its Applications"Progress in Discovery Science (Lecture Notes in Artificial Intelligence). 2281. 327-337 (2002)

Eiji Takimoto、Akira Maruoka：“自上而下的决策树提升及其应用”发现科学进展（人工智能讲义）。

Akira Maruoka, Eiji Takimoto: "On-Line Algorithm to Predict Nearly as Well as the Best Pruning of a Decision Tree"Progress in Discovery Science (Lecture Notes in Artificial Intelligence). 2281. 296-306 (2002)

Akira Maruoka、Eiji Takimoto：“几乎可以预测决策树以及最佳修剪的在线算法”发现科学进展（人工智能讲义）。

Eiji Takimoto, Manfred Warmuth: "Path Kernels and Multiplicative Updates"Computational Learning Theory (Lecture Notes in Artificial Intelligence). 2375. 74-89 (2002)

Eiji Takimoto、Manfred Warmuth：“路径核和乘法更新”计算学习理论（人工智能讲义）。

松本 淳, 瀧本 英二, 丸岡 章: "決定ダイアグラムに基づくブースティング"情報技術レターズ. 1. 9-10 (2002)

Jun Matsumoto、Eiji Takimoto、Akira Maruoka：“基于决策图的提升”信息技术快报。1. 9-10 (2002)