講演抄録/キーワード |
講演名 |
2010-11-05 15:30
[ポスター講演]近似解のパス追跡に関する一考察 ○烏山昌幸(名工大/学振)・竹内一郎(名工大) IBISML2010-89 |
抄録 |
(和) |
機械学習におけるパス追跡は解の区分線形性を利用し,最適化問題の厳密解を追跡する.しかし,(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 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2010-89 |