| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | 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) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-11-05 15:30:00 |
| 発表時間 | 180分 |
| 申込先研究会 | IBISML |
| 資料番号 | IBISML2010-89 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.265 |
| ページ範囲 | pp.221-230 |
| ページ数 | 10 |
| 発行日 | 2010-10-28 (IBISML) |
[研究会発表申込システムのトップページに戻る]