| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-11-09 13:00 一般化$ell_1$正則化問題に対するオンライン最適化手法 ○中里佳央・福地一斗（筑波大）・佐久間 淳（筑波大/理研/JST）  IBISML2017-47 |
|
| 抄録 | （和） | 構造正則化は事前知識をモデルに導入することで精度を向上させたり、解釈しやすいモデルを作成するために有用である． また、実質的な次元数を減らすことができるため、学習性能の向上を図る上でも有用である． そうした構造正則化の代表的な例として、一般化グラフ結合正則化(Generalized Fused Lasso、GFL)がある． 本研究ではGFLや近年提案されたトレンドフィルタリングを含むより一般化された一般化$ell_1$正則化問題に対して新たなオンライン凸最適化アルゴリズムを提案する． 提案手法は近接平均法cite{yu2013better}を双対空間で行うことで、微分不可能で分割できない一般化$ell_1$正則化問題を解く． これにより、複雑な正則化に対しても収束の早さの特徴量への依存性を指数的に軽減させることができる． また、効率的なGFLやトレンドフィルタリング等の近接写像のスケーラブルな実装法を提案する． これにより、GFLをグラフの要素数を$d$、グラフの最大次数を$k$としたとき、近接写像の計算量を$O(dk)$とすることができる． 実験では、人工データ、実データで距離関数をブレグマン擬距離に拡張することでユークリッドノルムを用いるより早く収束することがあることを実験的に示し、 効率的な実装により次元数が100,000、エッジ数が約340,000のデータセットに対しても、1反復あたり20ms程度で実行できることを報告する． |
| （英） | Structured sparse regularization is vital to enhance the precision and the interpretability of the model by introducing the prior knowledge. Also, it decreases the substantial number of features and improves the learnability of the model. In this paper, we shed light on the structured $ell_1$ regularized problems including generalized fused Lasso (GFL) and trend filtering. We propose a novel online convex optimization algorithm that solves the structured $ell_1$ regularized problems. Taking advantage of proximal averagecite{yu2013better} in dual space, our method success decreasing its convergence rate regarding the dimensional dependency exponentially. Besides, we propose an efficient implementation of proximal mapping and show the computational complexity of GFL is $O(dk)$, whereas state-of-the-art is $O(d|E|)$, where $d$ is the number of features, and $k$ is the max degree of the graph, and $|E|$ is the number of the edges. In experiments, we demonstrate our proposal can solve the GFL faster than normal proximal average in both synthetic and real dataset. Also, we show our method spends only up to 20 ms in each iteration with the enormous dataset with 100,000 features and about 340,000 edges. |
|
| キーワード | （和） | オンライン凸最適化 / 一般化結合ラッソ正則化 / トレンドフィルタリング / オンライン鏡像降下法 / / / / |
| （英） | Online convex optimization / Generalized fused Lasso / Trend filtering / Online mirror descent / / / / | |
| 文献情報 | 信学技報, vol. 117, no. 293, IBISML2017-47, pp. 93-100, 2017年11月. | |
| 資料番号 | IBISML2017-47 | |
| 発行日 | 2017-11-02 (IBISML) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IBISML2017-47 |
|
| 研究会情報 | |
| 研究会 | IBISML |
| 開催期間 | 2017-11-08 - 2017-11-10 |
| 開催地（和） | 東京大学 |
| 開催地（英） | Univ. of Tokyo |
| テーマ（和） | 情報論的学習理論ワークショップ (IBIS2017) |
| テーマ（英） | Information-Based Induction Science Workshop (IBIS2017) |
| 講演論文情報の詳細 | |
| 申込み研究会 | IBISML |
| 会議コード | 2017-11-IBISML |
| 本文の言語 | 日本語 |
| タイトル（和） | 一般化$ell_1$正則化問題に対するオンライン最適化手法 |
| サブタイトル（和） | |
| タイトル（英） | Online Optimization Method for Generalized $ell_1$ Regularized Problems |
| サブタイトル（英） | |
| キーワード(1)（和/英） | オンライン凸最適化 / Online convex optimization |
| キーワード(2)（和/英） | 一般化結合ラッソ正則化 / Generalized fused Lasso |
| キーワード(3)（和/英） | トレンドフィルタリング / Trend filtering |
| キーワード(4)（和/英） | オンライン鏡像降下法 / Online mirror descent |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中里 佳央 / Yoshihiro Nakazato / |
| 第1著者 所属（和/英） | 筑波大学 (略称： 筑波大) University of Tsukuba (略称： Tsukuba Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 福地 一斗 / Kazuto Fukuchi / |
| 第2著者 所属（和/英） | 筑波大学 (略称： 筑波大) University of Tsukuba (略称： Tsukuba Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 佐久間 淳 / Jun Sakuma / |
| 第3著者 所属（和/英） | 筑波大学/理研/JST (略称： 筑波大/理研/JST) University of Tsukuba/Riken/JST (略称： Tsukuba Univ./Riken/JST) |
| 第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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2017-11-09 13:00:00 |
| 発表時間 | 150分 |
| 申込先研究会 | IBISML |
| 資料番号 | IBISML2017-47 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | no.293 |
| ページ範囲 | pp.93-100 |
| ページ数 | 8 |
| 発行日 | 2017-11-02 (IBISML) |
[研究会発表申込システムのトップページに戻る]