請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48991
標題: | 針對一次正則化及分組一次正則化問題的隨機活動集近端擬牛頓法 Stochastic Active-Set Proximal Quasi-Newton Method for L1 and Group-L1 Regularized Learning |
作者: | Yu-Chen Lu 盧昱辰 |
指導教授: | 林守德(Shou-De Lin) |
關鍵字: | 特徵選擇,大規模學習, feature selection,large-scale learning, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 一次正則化(L1 regularization)已經是標準的特徵選取(feature selection)方法之一。當我們對於資料特徵有額外的結構資訊,我們可以將特徵選取延伸至挑選一些預先定義的特徵集合,而這可以由分組一次正規化(group-L1 regularization)來達成。面對高維度的機器學習問題,shrinking 以及貪婪方法常被用來維護一個工作集以縮小問題。然而shrinking 採取太過保守的策略,而貪婪方法需要過多的花費。在這篇論文中,我們提出了隨機活動集方法(Stochastic Active-Set method),透過無偏的近似貪婪方法維護一個活動集,並有夠高的機率達到收斂。藉由一個雙重採樣的策略,我們平衡了搜尋特徵空間的花費以及活動集的效果。除此之外,為了應對那些計算密集的損失函數,我們建構了一個擬牛頓法的新變體來配合我們的活動集方法,因此不需要計算所有的損失函數梯度。在我們的實驗中,對於計算密集的損失函數的一次正規化以及分組一次正規化問題,我們所提出的方法相較於目前最先進的方法,展現出了顯著的加速。 L1 regularization has become one of the standard techniques for feature selection. Furthermore, when structural prior knowledge is available, we can extend the feature selection problem to selecting (predefined) groups of variables, which can be achieved via solving a Lp;1 regularization. To deal with high dimensional learning tasks, shrinking heuristics and greedy method are often exploited to maintain a relatively small working set. However, in practice, shrinking could be too conservative while greedy method could be too expensive in the search of greedy variable. In this work, we propose a Stochastic Active-Set method that maintains an active-set by an approximate and unbiased greedy search method that finds active variables with certain probability suffices to achieve fast convergence. A balance between exploiting active set and exploring high-dimensional space is achieved via a double sampling strategy. In addition, to handle loss function of expensive evaluation cost, we construct a new variant of Quasi-Newton approximation for our Active-Set method, which does not require computation of the whole gradient vector. In our experiments, the proposed algorithm leads to significant speed up over state-of-the-art solvers for L1, L2;1 and Linf;1 regularized problems of computationally expensive loss function. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48991 |
DOI: | 10.6342/NTU201603353 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 1.84 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。