Lasso演算法

在統計學和機器學習中，Lasso演算法。雖然最早是為應用最小二乘法而定義的演算法，lasso正則化可以簡單直接地拓展應用於許多統計學模型上，包括廣義線性模型，廣義估計方程，成比例災難模型和M-估計。Lasso選擇子集的能力依賴於限制條件的形式並且有多種表現形式，包括幾何學，貝葉斯統計，和凸分析。Lasso演算法與基追蹤降噪聯絡緊密。歷史蒂布希拉尼最初使用Lasso來提高預測的準確性與迴歸模型的可解釋性，他修改了模型擬合的過程，在協變數中只選擇一個子集應用到最終模型中，而非用上全部協變數。這是基於有著相似目的，但方法有所不同的Breiman的非負引數推斷。在Lasso之前，選擇模型中協變數最常用的方法是移步選擇，這種方法在某些情況下是準確的，例如一些協變數與模型輸出值有強相關性情況。然而在另一些情況下，這種方法會讓預測結果更差。在當時，嶺迴歸是提高模型預測準確性最常用的方法。嶺迴歸可以透過縮小大的迴歸係數來減少過擬合從而改善模型預測偏差。但是它並不選擇協變數，所以對模型的準確構建和解釋沒有幫助。Lasso結合了上述的兩種方法，它透過強制讓迴歸係數絕對值之和小於某固定值，即強制一些迴歸係數變為0，有效地選擇了不包括這些迴歸係數對應的協變數的更簡單的模型。這種方法和嶺迴歸類似，在嶺迴歸中，迴歸係數平方和被強制小於某定值，不同點在於嶺迴歸只改變係數的值，而不把任何值設為0。基本形式.Lasso最初為了最小二乘法而被設計出來，Lasso的最小二乘法應用能夠簡單明瞭地展示Lasso的許多特性。最小二乘.假設一個樣本包括N種事件，每個事件包括"p"個協變數和一個輸出值。讓formula_1為輸出值，並且formula_2為第i種情況的協變數向量，那麼Lasso要計算的目標方程就是：對所有 formula_3，計算 formula_4這裡 formula_5 是一個決定規則化程度的預定的自由引數。 設formula_6為協變數矩陣，那麼 formula_7，其中 formula_8 是 formula_9的第 "i" 行，那麼上式可以寫成更緊湊的形式：對所有 formula_10，計算 formula_11這裡 formula_12 是標準 formula_13 範數，formula_14是formula_15維的1的向量。因為 formula_16，所以有formula_17對變數進行中心化是常用的資料處理方法。並且協方差一般規範化為 formula_18 ，這樣得到的解就不會依賴測量的規模。它的目標方程還可以寫為：formula_19其拉格朗日形式為：formula_20其中 formula_21 和 formula_22 的關係取決於資料特徵。正交協變數.現在考慮一些Lasso迴歸估計的基本性質。首先假定所有的協變數都是正交的，即 formula_23，其中formula_24 為 克羅內克δ函式。等價的矩陣寫法為 formula_25，使用次梯度法可有如下的表達形式formula_26formula_27 用於表示軟閾值運算元，當這個值非常小的時候為0。一個與之相近的記號formula_28用來表示硬閾值運算元，將較小的數值記為0的同時保留原有的較大數值。與嶺迴歸相比較，其中嶺迴歸的目標在於最小化formula_29即有formula_30因此嶺迴歸是對OLS迴歸中所有的係數以一致的係數formula_31縮放，並不會進行變數選擇。同樣也可以對best subset selection演算法進行比較，其目標在於最小化formula_32其中 formula_33 表示 "formula_34 norm"，即0範數，被定義為該向量中非零元的個數。在這個例子中，可以得到formula_35其中 formula_28 被稱為軟閾值運算元，formula_37 為示性函式。總的來說，Lasso估計量展現出了嶺迴歸和最佳子劃分演算法的係數收縮的優點，使得部分系數為0。此外，在嶺迴歸全部使用一個常數係數縮放的時候，Lasso迴歸會將一個接近0的係數變為0。相關協變數.對於一般的情況中，不同的協變數之間可能並不是獨立的，其中一種特例即為變數存在重複，例如變數j和變數k，有formula_38，formula_39。在這種情況下引數 formula_40 和 formula_41的Lasso迴歸的估計量不是唯一確定的。事實上，如果有一些 formula_42 中存在 formula_43，尋找一個formula_44進行變換，將formula_45變換為formula_46 的同時有 formula_47 變換為 formula_48，並保留其他引數不變，此時Lasso迴歸具有有效的連續性質。一些基於Lasso迴歸的改進，例如彈性網路正則化，旨在解決這個缺點。一般形式.Lasso正則化可以擴充套件為其他目標函式，例如廣義線性模型，廣義估計方程，比例風險模型和M估計。 有目標函式formula_49其中Lasso正則化迴歸給出了下面模型的估計量formula_50在這裡只有formula_51是一個懲罰項，formula_52是一個自由變數，與最基本的模型中的 formula_53 變數一樣。演算法解釋.幾何解釋.Lasso迴歸可以使得某些項係數為0，從幾何上來看，不同約束邊界形狀的嶺迴歸則不能。他們都可以解釋為最小化相同的目標函式formula_11但是有不同的約束條件：在Lasso迴歸中為 formula_55 而在嶺迴歸中為 formula_56。1-範數The figure shows that the constraint region defined by the formula_57 norm is a square rotated so that its corners lie on the axes (in general a cross-polytope), while the region defined by the formula_58 norm is a circle (in general an "n"-sphere), which is rotationally invariant and, therefore, has no corners. As seen in the figure, a convex object that lies tangent to the boundary, such as the line shown, is likely to encounter a corner (or a higher-dimensional equivalent) of a hypercube, for which some components of formula_51 are identically zero, while in the case of an "n"-sphere, the points on the boundary for which some of the components of formula_51 are zero are not distinguished from the others and the convex object is no more likely to contact a point at which some components of formula_51 are zero than one for which none of them are.Making λ easier to interpret with an accuracy-simplicity tradeoff.The lasso can be rescaled so that it becomes easy to anticipate and influence the degree of shrinkage associated with a given value of formula_22. It is assumed that formula_9 is standardized with z-scores and that formula_64 is centered (zero mean). Let formula_65 represent the hypothesized regression coefficients and let formula_66 refer to the data-optimized ordinary least squares solutions. We can then define the Lagrangian as a tradeoff between the in-sample accuracy of the data-optimized solutions and the simplicity of sticking to the hypothesized values. This results informula_67where formula_68 is specified below. The first fraction represents relative accuracy, the second fraction relative simplicity, and formula_69 balances between the two.Given a single regressor, relative simplicity can be defined by specifying formula_70 as formula_71, which is the maximum amount of deviation from formula_65 when formula_73. Assuming that formula_74, the solution path can be defined in terms of formula_75:formula_76If formula_77, the ordinary least squares solution (OLS) is used. The hypothesized value of formula_78 is selected if formula_69 is bigger than formula_75. Furthermore, if formula_81, then formula_69 represents the proportional influence of formula_78. In other words, formula_84 measures in percentage terms the minimal amount of influence of the hypothesized value relative to the data-optimized OLS solution.If an formula_85-norm is used to penalize deviations from zero given a single regressor, the solution path is given byformula_86. Like formula_87, formula_88 moves in the direction of the point formula_89 when formula_69 is close to zero; but unlike formula_87, the influence of formula_75 diminishes in formula_88 if formula_69 increases (see figure). Given multiple regressors, the moment that a parameter is activated (i.e. allowed to deviate from formula_65) is also determined by a regressor's contribution to formula_75 accuracy. First,formula_97An formula_75 of 75% means that in-sample accuracy improves by 75% if the unrestricted OLS solutions are used instead of the hypothesized formula_65 values. The individual contribution of deviating from each hypothesis can be computed with the formula_100 x formula_100 matrixformula_102where formula_103. If formula_104 when formula_75 is computed, then the diagonal elements of formula_106 sum to formula_75. The diagonal formula_106 values may be smaller than 0 or, less often, larger than 1. If regressors are uncorrelated, then the formula_109 diagonal element of formula_106 simply corresponds to the formula_111 value between formula_112 and formula_64.A rescaled version of the adaptive lasso of can be obtained by setting formula_114. If regressors are uncorrelated, the moment that the formula_109 parameter is activated is given by the formula_109 diagonal element of formula_106. Assuming for convenience that formula_65 is a vector of zeros,formula_119That is, if regressors are uncorrelated, formula_69 again specifies the minimal influence of formula_65. Even when regressors are correlated, the first time that a regression parameter is activated occurs when formula_69 is equal to the highest diagonal element of formula_106.These results can be compared to a rescaled version of the lasso by defining formula_124, which is the average absolute deviation of formula_66 from formula_65. Assuming that regressors are uncorrelated, then the moment of activation of the formula_109 regressor is given byformula_128For formula_129, the moment of activation is again given by formula_130. If formula_65 is a vector of zeros and a subset of formula_132 relevant parameters are equally responsible for a perfect fit of formula_81, then this subset is activated at a formula_69 value of formula_135. The moment of activation of a relevant regressor then equals formula_136. In other words, the inclusion of irrelevant regressors delays the moment that relevant regressors are activated by this rescaled lasso. The adaptive lasso and the lasso are special cases of a '1ASTc' estimator. The latter only groups parameters together if the absolute correlation among regressors is larger than a user-specified value.Bayesian interpretation.Just as ridge regression can be interpreted as linear regression for which the coefficients have been assigned normal prior distributions, lasso can be interpreted as linear regression for which the coefficients have Laplace prior distributions. The Laplace distribution is sharply peaked at zero (its first derivative is discontinuous at zero) and it concentrates its probability mass closer to zero than does the normal distribution. This provides an alternative explanation of why lasso tends to set some coefficients to zero, while ridge regression does not.Convex relaxation interpretation.Lasso can also be viewed as a convex relaxation of the best subset selection regression problem, which is to find the subset of formula_137 covariates that results in the smallest value of the objective function for some fixed formula_138, where n is the total number of covariates. The "formula_34 norm", formula_140, (the number of nonzero entries of a vector), is the limiting case of "formula_141 norms", of the form formula_142 (where the quotation marks signify that these are not really norms for formula_143 since formula_144 is not convex for formula_143, so the triangle inequality does not hold). Therefore, since p = 1 is the smallest value for which the "formula_13 norm" is convex (and therefore actually a norm), lasso is, in some sense, the best convex approximation to the best subset selection problem, since the region defined by formula_147 is the convex hull of the region defined by formula_148 for formula_143.應用.LASSO已被應用於經濟和金融領域，可以改善預測結果並選擇有時被忽視的變數。例如：公司破產預測和高增長公司預測。