線形変換されたℓoスパース制約下での学習

• Item type: SIG Technical Reports(1)
• 公開日: 2017-06-16
• タイトル: 線形変換されたℓoスパース制約下での学習
• タイトル / 言語: en
• タイトル: Learning with linearly transformed ℓo sparsity
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電信電話株式会社(NTT)
• 著者所属: 日本電信電話株式会社(NTT)
• 著者所属(英): en
• 著者所属(英): Nippon Telegraph and Telephone
• 著者所属(英): en
• 著者所属(英): Nippon Telegraph and Telephone
• 著者名: 丸茂, 直貴; 岩田, 具治
• 著者名(英): Naoki, Marumo; Tomoharu, Iwata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 線形変換されたスパース制約下での非 凸 最適化問題を考える． これは，機械学習ので生じる多くの問題を含む問題クラスである．この問題は NP 困難であり，直接解くのが難しいため， ℓ₁ 緩和に基づく手法が研究されてきたが，それらの手法は推定バイアスがのってしまう．本稿ではこれを回避するため，緩和なしに元の問題を直接解く，理論保証付きの解法を提案する．本解析では，提案手法が大域的最適解の近くに一次収束することを示している．また数値実験によって，提案手法が既存手法より高速かつ高精度であることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider a class of non-convex optimization problems with linearly transformed sparsity constraints, which includes a wide range of problems in machine learning. Since this problem is difficult to solve directly, ℓ₁ relaxation methods have been extensively used. However, ℓ₁ methods often suffer from large estimation bias. To avoid this problem, we propose a provable algorithm for solving the ℓ₀ problem without relaxation. Our analysis shows that the proposed method converges linearly to an approximately global optimum under mild assumptions. With our experiments, we confirm that the proposed method is faster and more accurate than existing ℓ₁ and ℓ₀ methods and that the proposed method can capture the true sparsity level more correctly. Furthermore, the results show that the proposed method works well under severe conditions such as small sample size and high dimension.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2017-MPS-113, 号 47, p. 1-7, 発行日 2017-06-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8833
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会