平成17（2005）年度　一般研究２実施報告書

 

課題番号

17−共研−2019

専門分類

2

研究課題名

２次錐計画とパターン認識

フリガナ

代表者氏名

ムラマツ　マサカズ

村松　正和

ローマ字

Muramatsu Masakazu

所属機関

電気通信大学

所属部局

電気通信学部

職　　名

助教授

所在地

TEL

FAX

E-mail

URL

配分経費

研究費

0千円

旅　費

0千円

研究参加者数

3　人

 

 

 

研究目的と成果（経過）の概要

本研究は、２次錐計画問題のパターン認識への応用を目的として出発した。２次錐計画問題は、近年注目されている凸最適化問題のクラスであり、種々の応用を持つ。２次錐計画問題を用い、従来のSVMの欠点を補うような新しい Kernel 機械を構成することを目指し，また、問題の特性を最大限に生かした高速な解法を開発することが目的であった。

[7] は従来の SVM をより効率よく２次錐計画を用いて解こうとするもので，パターン認識に２次錐計画を使うことができることを実用的に示している。特に SVM で用いられる最適化問題の構造を利用して，求解を高速化することを試みた。解法アルゴリズムとしては主双対内点法を用いているが，この効率が今一つであったことが新しいアルゴリズムへの研究の動機の一つとなった。

すなわち，[5], [6] における２次錐計画に対するピボット・アルゴリズムに対する研究である。その結果，SVMを２次錐計画を用いて定式化した場合，その最適化問題はピボットを用いて解くことができるようになった。ピボット・アルゴリズムは内点法とは異なる様々な性質を持っているので，それらを活用してKernel機械に現れる最適化問題の効率的な解法の開発につながる可能性がある。実用的に他のアルゴリズムに対抗できるくらい効率が良いかどうかは，これからの検討課題である。

一方土谷は２次錐計画の応用[1]から始まり，層別最小二乗法[2], 制御への応用[3], 重み付き行列式最大化問題[4] など，多岐にわたって研究を行なった。これらはいずれも，２次錐計画およびそれを発展させた凸計画問題に関連するテーマである。

残念ながら，目標としていた「新しい Kernel 機械を構成」するところまでは至らなかったが，上で述べたように，他の部分も含めて十分な成果が得られたと考えられる。

 

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

[1] 土谷 隆, 笹川 卓: 2次錐計画問題による磁気シールドのロバスト最適化. 統計数理, 53巻 (2005), pp.297-315.
[2] 土谷 隆: 層別最小二乗法 ?? 重み付き最小二乗法の極限 ??.統計数理, 53巻 (2005), pp.391--404.
[3] L.Faybusovich, T.Mouktonglang and T.Tsuchiya: Implementation of Infinite-dimensional Interior-point Method for Solving Multi-criteria Linear-quadratic Control Problem.Optimization Methods and Software, Vol.21 (2006), pp.315-341.
[4] Takashi Tsuchiya and Yu Xia: An Extension of the Standard Polynomial-time Primal-dual Path-following Algorithm to the weighted determinant Maximization Problem with Semidefinite Constraints. Research Memorandum No.980, The Institute of Statistical Mathematics, February 2006.
[5] Masakazu Muramatsu: A Pivoting Procedure for a Class of Second-Order Cone Programming, Optimization Methods and Software, 21(2006), pp.295-314.
[6] 栗田圭介，村松正和：２次錐計画のサブクラスに対する単体法的アルゴリズムにおけるピボット選択規則について，統計数理，５３巻(2005)，pp.349-360.
[7] Rameswar Debnath, Masakazu Muramatsu, and Haruhisa Takahashi: An Efficient Support Vector Machine Learning Method with Second-Order Cone Programming for Large-Scale Problems, Applied Intelligence Vol. 23 (2005), pp.219-239.

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

 

研究参加者一覧

氏名

所属機関

夏　雨

日本学術振興会

土谷　隆

統計数理研究所