求解LASSO 問題的廣義對(duì)稱交替方向乘子算法

蔣 峰， 黨亞崢， 何澤秀

（上海理工大學(xué) 管理學(xué)院， 上海200093）

0 引 言

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)收集技術(shù)有了巨大的發(fā)展，如何有效地從大規(guī)模數(shù)據(jù)中挖掘出潛在的有用信息成為了新的研究熱點(diǎn)。 線性模型是當(dāng)前比較常用的數(shù)據(jù)挖掘手段，其理論豐富，應(yīng)用廣泛，在農(nóng)業(yè)、工程技術(shù)、經(jīng)濟(jì)、管理、工業(yè)、生物等領(lǐng)域取得了長(zhǎng)足的發(fā)展［1］。 線性模型應(yīng)用的范圍越廣，模型的準(zhǔn)確性就顯得越重要。 就線性模型而言，其準(zhǔn)確性主要取決于變量的選擇和回歸系數(shù)的取值。 受Ridge Regression 和Nonnegative Garrote 算法的啟發(fā)，Tibshirani 提出了一種新的變量選擇方法，即最小絕對(duì)收縮和選擇算子（Least absolute shrinkage and selection operator， LASSO）［2］。 LASSO 問題包含平方誤差的求和和正則化項(xiàng)。 L1 正則化項(xiàng)能夠避免模型過擬合問題，使得模型更加穩(wěn)定［3］。

解決LASSO 問題的方法很多，Efron 提出了最小角回歸算法求解Lasso 問題。 該算法通過消除回歸系數(shù)的異號(hào)情況得到LASSO 問題的解［2］。 陳善雄等人考慮各個(gè)變量在模型中所占比重不同，提出了多維權(quán)重求解算法［3］。 該算法在最小回歸算法的基礎(chǔ)上加入主成分分析、獨(dú)立權(quán)數(shù)法、基于Intercriteria 相關(guān)性指標(biāo)的重要性評(píng)價(jià)法這3 種權(quán)重評(píng)價(jià)方法，優(yōu)化變量的選擇。 數(shù)值實(shí)驗(yàn)表明該方法進(jìn)一步提升了求解LASSO 問題的準(zhǔn)確性。 在解決大規(guī)模數(shù)據(jù)問題中，交替方向乘子法（ADMM）得到廣泛應(yīng)用。 ADMM 算法將原始的凸優(yōu)化問題分解為多個(gè)子問題進(jìn)行分別求解，最后再計(jì)算拉格朗日乘子［4］。 這種方法在很大程度上減少了計(jì)算成本，提升了求解LASSO 問題的效率。

雖然ADMM 算法求解大數(shù)據(jù)背景下的LASSO問題速度較快，但是在很多實(shí)際應(yīng)用中， 精確地求解子問題難以實(shí)現(xiàn)， 或者需要很大代價(jià)。 因此本文提出了一種廣義對(duì)稱ADMM 算法。 該算法的主要?jiǎng)?chuàng)新之處是在對(duì)稱交替方向乘子法的x 極小化子問題中加入半近鄰項(xiàng)近似求解此問題。 此外，為進(jìn)一步提高算法的收斂速度，引入了松弛算子。 通過具體的數(shù)值實(shí)驗(yàn)表明，廣義對(duì)稱交替方向乘子法收斂速度比對(duì)稱交替方向乘子法更快。

1 LASSO 問題及廣義對(duì)稱ADMM 算法

1.1 LASSO 問題描述

機(jī)器學(xué)習(xí)中的凸優(yōu)化問題一般可以表示為

其中，x ∈Rn，P ∈Rm×n，u 是正則化參數(shù)。

1.2 廣義對(duì)稱ADMM 算法

ADMM 算法由Glowinski 等人提出［5］，主要用于求解形如式（3）的凸優(yōu)化問題

其中，A ∈Rm×n，X ?Rn、Z ?Rm是給定閉凸集；f：Rn→R ∪ {＋∞} 和g：Rm→R ∪ {＋∞} 為凸函數(shù)。

本文A 為單位矩陣，其迭代格式如下：

其中，y 為拉格朗日乘子，γ 是懲罰參數(shù)。 由式（3）可以看出，ADMM 算法先求解x 最小化問題，再求解z 最小化問題，最后再更新拉格朗日乘子y。

在文獻(xiàn)［6］中，對(duì)稱ADMM 算法被用于求解LASSO 問題。 然而，在大數(shù)據(jù)背景下，精確地求解（3）中的x 子問題難以實(shí)現(xiàn)，或者需要很大代價(jià)。 因此本文提出了一種廣義對(duì)稱ADMM 算法。

其中， α ∈（0，2］ 是松弛算子。 當(dāng)α ＝1 時(shí)，（1.5）變?yōu)閷?duì)稱ADMM 算法。

2 數(shù)值實(shí)驗(yàn)

本節(jié)將廣義對(duì)稱ADMM 算法應(yīng)用于LASSO 問題。 在進(jìn)行數(shù)值實(shí)驗(yàn)時(shí)，選取矩陣P 并且規(guī)范化P中所有列。 取a 和σ 為隨機(jī)向量，b ＝Pa ＋σ，正則化參數(shù)取m ＝2 500，α ＝0.8，懲罰參數(shù)γ ＝1，矩陣此外，向量x， y， z 的初始值皆為零向量。

其中，δ ＝10－4。

表1 為應(yīng)用對(duì)稱ADMM 算法和廣義對(duì)稱ADMM 算法解決該問題的結(jié)果，其中Iter 表示迭代次數(shù)，CPU（s） 表示CPU 時(shí)間（以秒為單位）， n 表示矩陣P 的維數(shù)。 從表1 可以看出，本文提出的算法快于對(duì)稱ADMM 算法。

表1 LASSO 問題數(shù)值結(jié)果Tab.1 Numerical results for LASSO

為了進(jìn)一步觀察2 種算法的收斂性，比較初始?xì)埐詈蛯?duì)偶?xì)埐铍S迭代次數(shù)的變化情況（縱軸分別是初始?xì)埐詈蛯?duì)偶?xì)埐?，橫軸是迭代次數(shù)）。 從圖1、圖2 中可以直觀地發(fā)現(xiàn)，盡管在算法迭代的某些階段，對(duì)稱ADMM 算法的初始?xì)埐?、?duì)偶?xì)埐顪p小更快，但是本文提出的算法先于對(duì)稱ADMM 算法收斂，因此廣義對(duì)稱ADMM 算法更高效。

圖1 對(duì)偶?xì)埐畹淖兓闆rFig.1 Evolution of primal residual

圖2 初始?xì)埐畹淖兓闆rFig.2 Evolution of dual residual

3 結(jié)束語(yǔ)

本文提出了一種求解LASSO 問題的廣義對(duì)稱ADMM 算法。 該方法的基本思想是在x 子問題中加入一個(gè)二次項(xiàng)，并且引入了松弛算子，從而提升算法效率。 數(shù)值實(shí)驗(yàn)表明，本文提出的算法在求解高維的LASSO 問題時(shí)，相對(duì)于對(duì)稱ADMM 算法具有明顯的優(yōu)勢(shì)。 但是，如何選擇最優(yōu)的α 還需要進(jìn)一步研究。