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

在线预测降维研究

• 批准号: 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次元空間では線形分離したサンプルに写像する能力を有する.これにより,カーネル手法に代わる新しい非線形学習方式を提案した.

In response to this problem, the optimal prediction value series is updated and developed. The inner product calculation (w_t·x_t) is based on the prediction of the output value, and the update of the common property is maintained. In this paper, we study the structure of the structure of the problem, appropriate change φ:R^n→R^N, high dimensional space (N), write image x_t=φ(z_t)(z_t), write image φ, use the middle prediction rate, imitate the condition of the middle modulation. In particular, the inner product w_t·x_t=φ(z_t)·φ(v_t)= z_t·v_t is the relation between the inner product w_t·x_t=φ(z_t)·φ(v_t) and v_t. In this case, there is a change in the number of natural problems, and a change in the number of natural problems. In particular, the status of the class is changed from time to time, and the environment is changed from time to time. The problem of determining the optimal condition of the class is the problem of determining the optimal condition of the class. This is the result of a formal presentation of the concept of a general presentation. In addition, the high dimensional space N is changed from the low dimensional space k to R, and the rank is defined. The distance between R and 2 points is preserved. The properties are used. The linear separation is related to the rate of learning. Each component of the array is limited to 4 independent elements,n=logN dimensional elements,n=logN dimensional elements. The ability to write images in non-linear transformations in n-dimensional space without linear separation in N-dimensional space. The new non-linear learning method is proposed in this paper.

项目成果

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, 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, 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)