電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2010-11-05 15:30
[ポスター講演]近似解のパス追跡に関する一考察
烏山昌幸名工大/学振)・竹内一郎名工大
技報オンラインサービス実施中
抄録 (和) 機械学習におけるパス追跡は解の区分線形性を利用し,最適化問題の厳密解を追跡する.しかし,(a)大きなデータセットでは解の変化点(ブレイクポイント)が多くなり計算コストが増加する,(b)常に厳密解を保つ必要があるため他のアルゴリズムと併用しにくい,といった問題点がある.そこで,本稿ではある与えられた近似精度を保つパス追跡アルゴリズムを提案する.具体的には,最適性条件に対して許容する誤差を明示的に与え,近似解を追跡するアルゴリズムを考える.通常,パス追跡ではブレイクポイントにおいてある1組の不等式条件の活性と非活性を切り替えるが,提案法では複数組の不等式条件の活性と非活性を一度に切り替えることによってブレイクポイントの削減を試みる.複数条件が同時に活性・非活性の境界にいることは最適化において退化と呼ばれる状況であるが,解の微小変化を考慮することで巡回の可能性を完全に回避する方法に関しても考察する.最後に,数値実験により提案法の有効性を検証する. 
(英) The solution path algorithms in machine learning trace the exact optimal solutions by exploiting the piecewise linearity. However, (a) in large data set, the increase of the change points of solutions (breakpoints) leads large computational cost, (b) due to the requirement of exact optimality, it is difficult to enter the path from the approximated solutions. To overcome these difficulties, we propose an algorithm that can trace the suboptimal solutions under the given tolerance of optimality violations. Conventional solution path algorithm changes activation of one of the constraints at each breakpoint. To decrease breakpoints, proposed approach changes activation of multiple constraints at each breakpoint. Although this brings on a so-called degeneracy problem in parametric programming, we also show how to avoid the cycling using auxiliary quadratic problems. We illustrate our approach by numerical simulations.
キーワード (和) パス追跡 / サポートベクトルマシン / パラメトリック計画法 / 凸2次計画問題 / KKT条件 / 退化 / /  
(英) path following / support vector machine / parametric programming / convex quadratic programming / KKT conditions / degeneracy / /  
文献情報 信学技報, vol. 110, no. 265, IBISML2010-89, pp. 221-230, 2010年11月.
資料番号 IBISML2010-89 
発行日 2010-10-28 (IBISML) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 IBISML  
開催期間 2010-11-04 - 2010-11-06 
開催地(和) 東大生産研 
開催地(英) IIS, Univ. of Tokyo 
テーマ(和) IBIS 2010 (情報論的学習理論ワークショップ) 
テーマ(英) IBIS 2010 (Workshop on Information-based Induction Sciences) 
講演論文情報の詳細
申込み研究会 IBISML 
会議コード 2010-11-IBISML 
本文の言語 日本語 
タイトル(和) 近似解のパス追跡に関する一考察 
サブタイトル(和)  
タイトル(英) A Study on the Suboptimal Solution Path Algorithm 
サブタイトル(英)  
キーワード(1)(和/英) パス追跡 / path following  
キーワード(2)(和/英) サポートベクトルマシン / support vector machine  
キーワード(3)(和/英) パラメトリック計画法 / parametric programming  
キーワード(4)(和/英) 凸2次計画問題 / convex quadratic programming  
キーワード(5)(和/英) KKT条件 / KKT conditions  
キーワード(6)(和/英) 退化 / degeneracy  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 烏山 昌幸 / Masayuki Karasuyama / カラスヤマ マサユキ
第1著者 所属(和/英) 名古屋工業大学 (略称: 名工大/学振)
Nagoya Institute Technology (略称: NIT)
第2著者 氏名(和/英/ヨミ) 竹内 一郎 / Ichiro Takeuchi /
第2著者 所属(和/英) 名古屋工業大学 (略称: 名工大)
Nagoya Institute Technology (略称: NIT)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2010-11-05 15:30:00 
発表時間 180 
申込先研究会 IBISML 
資料番号 IEICE-IBISML2010-89 
巻番号(vol) IEICE-110 
号番号(no) no.265 
ページ範囲 pp.221-230 
ページ数 IEICE-10 
発行日 IEICE-IBISML-2010-10-28 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会