基于ADMM的L1/2稀疏迭代分布式算法研究與應用

李 輝，黃祖源，田 園

（云南電網有限責任公司信息中心，云南昆明 650011）

大數據時代已經來臨。機器學習和數據分析是將大數據轉換成有用知識的關鍵技術，并且有研究表明，在很多情況下，處理的數據規模越大，機器學習模型的效果會越好。因此，機器學習是大數據智能化分析處理應用中的重要手段。在大數據背景下，計算數據量級已升至TB 級或PB 級，給傳統機器學習帶來了挑戰和機遇。機器學習算法本身含有大量的選代計算，非常適用干并行化。目前，對大數據機器學習并行化研究已成為應對大數據應用需求的熱點研究方向。

傳統機器學習算法，由于理論設計局限，大部分都是串行算法，只能運行于單機環境，在面對大數據量時表現不佳，隨著并行化技術的發展，在面對海量數據時，如何提升算法的執行效率，就成為學術界和行業研究的熱點。文章提出的基于集成學習及ADMM 的分布式并行挖掘算法，有效地解決了單機算法無法并行化的問題，在不改變原有算法理論的基礎上，使得原有的單機算法更好地適配分布式的計算模式。

稀疏信息處理近來受到研究與應用界的廣泛關注，針對稀疏求解，文章提出一種基于L1/2正則化稀疏問題求解的方法，包括L1/2稀疏迭代分類算法、L1/2稀疏迭代回歸算法和L1/2稀疏迭代時間序列算法?；贚1/2正則化的稀疏迭代算法是求解基于損失函數與L1/2范數（正則項）的極小化非凸優化問題，以期望得到問題的稀疏解，相比于L1正則化算法，L1/2正則化的解更稀疏。

文章介紹了ADMM 算法的實現原理，在ADMM并行化算法的研究基礎上，對L1/2稀疏迭代算法進行了并行化改造。

1 ADMM

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是一種解決可分解凸優化問題的簡單方法。它可以將原問題的目標函數等價地分解成若干個可求解的子問題，然后并行求解每一個子問題，最后協調子問題的解得到原問題的全局解。ADMM 被廣泛地應用在信號處理、圖像處理、機器學習、工程計算等領域，具有收斂速度快，收斂性能好的優勢。

ADMM 通常用于解決存在兩個優化變量的只含等式約束的優化類問題，其一般形式為：

式中，x∈Rn，z∈Rm為優化變量；A∈Rp×n，B∈Rp×m，C∈Rp；f和g為凸函數。

為解決此類凸優化問題，定義增廣拉格朗日函數：

算法流程如下：

每一步只更新一個變量而固定另外兩個變量，如此交替重復更新。即，對于k=1，2，3，…，重復如下步驟：

ADMM 算法提供了一個將多優化變量問題轉化為單優化變量問題的轉化方式（交替方向），并未涉及具體的下降方法，其中關于x和z的更新過程需要結合具體的下降類算法，如梯度下降算法等。

上面這個式子被稱為是ADMM 的縮放形式。

相應地，更新步驟變為：

2 基于ADMM的L1/2稀疏迭代分布式算法

稀疏信息處理近來受到研究與應用界的廣泛關注。L1/2正則化是一種處理稀疏問題的方法?；贚1/2正則化的稀疏迭代算法是求解基于損失函數與L1/2范數的罰函數（正則項）的和的極小化非凸優化問題，以期望得到問題的稀疏解。相比于L1正則化算法，L1/2正則化的解更稀疏。求解L1/2正則化的算法有：重賦權迭代算法、soft 閾值迭代算法（軟門限閾值迭代算法）。

算法可采用分類和回歸兩類損失函數，實現對分類和回歸問題的處理。算法將這一極小化目標的過程通過解決L1/2的軟門限閾值迭代算法實現。

具體實現思路如下：

求解采用重賦權迭代算法：

對于凸的可拆解的算法，可采用ADMM，將全局問題分解為多個較小、較容易求解的局部子問題，并通過協調子問題的解得到全局問題的解。文章中自主創新的L1/2稀疏迭代分類算法、L1/2稀疏迭代回歸算法、L1/2稀疏迭代時間序列算法均采用基于ADMM 的分布式并行思路實現。其基本思路如下。

若優化問題為：

式中，x∈Rd，A∈Rp×d，y∈Rp，λ>0，可將其轉換為ADMM 的Consensus 型優化問題：

其可以直接采用分布式方式進行計算，流程如圖1所示。

圖1 基于ADMM的分布式并行挖掘算法

3 應用實例

基于ADMM 的L1/2 稀疏迭代分布式算法是基于極小化損失函數與關于稀疏解L1/2范數正則項的高效稀疏算法，L1/2 正則化與L2 正則化相比更容易求解，而與L1正則化相比能產生更稀疏的解，說明L1/2 正則化具有廣泛且重要的應用價值?；贏DMM 的L1/2稀疏迭代分布式算法具有高效，精確的優點。

電力數據具有實時性、真實性、覆蓋性等特征，能夠客觀且真實的反映社會經濟變革過程中行業的發展現狀及其趨勢，可助力政府部門實時監測行業動態，準確把握政策實施效果。電力行業中存在著大量的分類場景和回歸場景中，并且數據多且雜。

分類場景：在傳統用戶用電行為分析和異常用戶識別定位過程中，主要是通過相關人員的經驗、業務規則以及各個專項模型等方法實現異常用戶識別。通常業務人員會結合相關業務經驗知識，搭建多維行業用戶行為特性特征指標體系，建立智能化、自動化嫌疑用戶智能識別模型，用于異常用電用戶快速定位，包括反竊電、臺區線損識別以及企業信用評價等應用場景。

回歸場景：業務人員基于電力客戶基本信息、長期的用電記錄、繳費情況、繳費能力等數據，對各類數據進行統計分析，構建售電量預測模型。

在上述電力相關的分類場景和回歸場景中，在建模過程中運用基于ADMM 的L1/2稀疏迭代分布式算法建立相關模型，能取得好的結果以及效果。

4 結束語

在機器學習特定的應用中，算法的空間復雜度和時間復雜度，或者說算法的效率是和算法的準確率同樣重要的問題。傳統的機器學習算法大多是串行的，在數據量、數據維度不斷增長的情況下，單機的存儲容量和運行時長都是無法忍受的。在這種情況下，考慮將算法并行化是一個非常自然的想法。通過基于ADMM 并行化方法的研究，對L1/2稀疏迭代算法進行并行化改造。通過實驗可以發現基于ADMM 的L1/2稀疏迭代分布式算法的執行效率極大提升，特別是在大數據量的情況下?；贏DMM 的L1/2稀疏迭代分布式算法可以應用于不同的場景中，包括分類以及回歸等業務場景中。