分布式变量选择—MCP正则化.pdf

文档介绍：该【分布式变量选择—MCP正则化 】是由【焦大】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【分布式变量选择—MCP正则化 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.

2021年06月CHINESEJOURNALOFENGINEERINGMATHEMATICSJune2021
doi:.1005-:1005-3085(2021)03-0301-14
分布式变量选择|MCP正则化
王格华,王璞玉,张海
(西北大学数学学院,西安710069)
摘要:随着数字化时代的发展,
数据,如何将其转化为可存储、便分析、能为解决实际问题提供参考的材料成为当前
,
储是将数据集按照某种方式不重复的存储在不同的机器中,以此解决数据存储问题.
那么,如何设计和研究出适合于分布式数据存储方式的机器学****算法便成为另一个亟
,正则化方法的提出和发展为我们处理和
分析海量高维数据提供了有效工具,
变量选择和特征提取的优越性,我们将分布式存储与非凸正则化方法相结合,关注基
于分布式计算的非凸正则化方法,

多个计算机,并提出分布式MCP方法,基于ADMM算法实现相邻计算机之间交互信
息的分布式MCP算法,完成全数据的变量选择,并给出分布式MCP算法的收敛性分
,通过实验
证明本文所提出的方法适合于处理分布式存储数据.
关键词:分布式;稀疏;MCP;ADMM
分类号:AMS(2010)68Q30中图分类号:O213;:A
1引引引言言言
考虑线性回归Y=X+",其中X∈RN×p是输入变量,Y∈RN是输出变
量,∈Rp是该模型的系数向量,",即真实的大部分分量
等于零,,正则化方法具有如下形式
12
min∥Y−X∥2+∥∥k;
2
其中Y=[Y;Y;···;Y]T∈RN;X=[X;X;···;X]T∈RN×p,>0是调控参
12N12N
数,=0时,上述正则化框架对应于AIC或BIC[1;2],此时
,但求解它对应于一个NP难
,众多学者提出了不同的正则化方法来逼近L0正则化,其中包括Lasso方
法(当k=1时)[3-7].为了得到更稀疏的解,许多学者提出了非凸正则化方法,包
收稿日期:2019-02-:王格华(1994年6月生),女,:非凸正则化.
基金项目:国家自然科学基金(11571011).
万方数据:.
302工程数学学报第38卷
括AdaptiveLasso[8]、SmoothlyClippedAbsoluteDeviation(SCAD)[9]、MinimaxCon-
cavePenalty(MCP)[10]、L正则化[11],MCP方法的提出作为一种经典的
1=2
非凸正则化方法,具有许多理想的性质,并且已经被广泛研究[12-15].它具有以下形式
12()
min∥Y−X∥2+PMCP||;(1)
2
∑p
其中PMCP(||)=i=1p;
(|i|),p;
在[0;+∞)的形式为
2
−;若≤
;
2
p;
()=(2)
1
2;若>
;
2
其中≥0;
>1.
上述正则化方法的提出和发展为我们处理和分析海量高维数据提供了有效工具,
但其仅适合于单机数据处理,,大量的生
,设计和研究适合

储的新特点,Mateos等[16]提出了将分布式计算与正则化方法相结合的分布式Lasso方
法,Wang等[17]提出了分布式L1=
的优越性,我们关注基于分布式计算的非凸MCP正则化方法.
,依数据所属计算机的不同,提出分布式MCP模
型;其次,基于ADMM算法,,通过模
拟实验和真实数据实验,证明所提方法在处理海量分布式存储的数据的有效性.
2分分分布布布式式式MCP模模模型型型
假设数据集S={Xn;Yn}N分布式存储在多台计算机中,Xj∈RNj×p;Yj∈
n=1
,所有计算机构成一个网络.
我们用无向图G=(J;E)来表示该网络,其中,集合J:={1;2;···;J}表示J台计
算机,E∈RJ×J为计算机i和计算机j的连接情况,定义N为计算机j的邻居的集
ijj
合,|Nj|表示集合Nj的大小,如果j∈Nj,则Eij=1,否则Eij=,我们假
设G=(J;E)是连通的,即在网络中任何一对计算机都存在一条路径使之可以通信.
根据局部数据所属计算机的不同,我们重新定义S={X;Y}J;X=[XT;XT;···;
jjj=112
XT]T∈RN×p;Y=[YT;YT;···;YT]T∈RN,并将模型(1)转化为
J12J
1∑J()
min∥Y−X∥2+P||;(3)
jj2MCP
2j=1
模型(3)将所有数据拆为J个部分,其与原模型(1)等价.
为了使每台计算机能够不依赖其他计算机独立的进行计算,我们考虑用局部变
量{}J替换全局变量,其中(3)可改写为下
jj=1j
万方数据:.
第3期王格华,等:分布式变量选择—MCP正则化303
述分布式MCP模型
1∑J{2P(||)}
2MCPj
minJ∥Yj−Xjj∥2+
{j}j=12j=1J
(4)
s:t:=′;j∈J;j′∈N:
jjj
定理1如果无向图G=(J;E)是连通的,则(3)和(4)等价.
证明若G=(J;E)是连通的,则每台计算机可以和网络中任意一台计算机交互信
息,即对于任意的j;j′∈J,存在j;j;···;j,满足b=b=···=b=b′,则存
12njj1jnj
在b,满足b=b1=···=b代替所有的{bj}J,我们可以消除分布式
j=1
优化问题的约束,反之亦然,那么(4)与(3)等价.
3分分分布布布式式式MCP算算算法法法
本节基于ADMM算法求解分布式MCP,并给出算法的收敛性分析.

ADMM算法于20世纪70年代早期被提出[18;19],随后被众多学者推广[20-24].近年
来,ADMM算法在计算机视觉,
法求解分布式模型(4).首先,考虑添加辅助局部变量{Z}J,则模型(4)可以改写为
jj=1
∑J∑J()
121
min∥Yj−Xjj∥2+PMCP|Zj|
{j}JjJj=1;{Zi}JiJi=12J
j=1j=1(5)
s:t:Zi−j=0;∀i;j=1;2;···;J:
模型(5)要求网络中所有局部变量彼此相等,注意到我们假设图G=(J;E)是连通的,那
么(3)和(5)是等价的.
为了方便表述,我们将模型(5)写成向量的形式
minf()+h(Z)
Z;
(6)
s:t:AZ+B=0;
其中
∑J∑J
121
f()=∥Yj−Xjj∥2;h(Z)=PMCP(|Zj|);
2j=1Jj=1
=[T;T;···;T]T∈R(J×p)×1;Z=[ZT;ZT;···;ZT]T∈R(J×p)×1;
12J12J
[]T(J×J×p)×(J×p)
B=−I(J×p)×(J×p);···;I(J×p)×(J×p)∈R;
A=[AT;AT;···;AT]T∈R(J×J×p)×(J×p);
12J
其中A∗=[I;···;I]T∈R(J×p)×(p);0∈R(J×p)×p是零矩阵,A=[A∗;0;···;0];
p×pp×p1
A=[0;A∗;···;0];···;A=[0;···;0;A∗].
2J
万方数据:.
304工程数学学报第38卷
模型(6)的二次增广拉格朗日函数为
c2
L(Z;;V)=f()+h(Z)+⟨V;AZ+B⟩+∥AZ+B∥2;(7)
2
其中V∈R(J×J×p)×1为拉格朗日乘子,c>0为预选参数.
ADMM算法分为以下三个步骤:
步骤1更新Z
Zk+1=argminL(Z;k;Zk);(8)
Z
步骤2更新
k+1=argminL(Zk+1;;Vk);(9)

步骤3更新拉格朗日乘子
Vk+1=Vk+c(AZk+1+Bk+1):(10)
在分析ADMM算法的收敛性之前,***@f表示函数f的次梯
度,M表示矩阵ATA的最小正特征值,M′
函数可微且梯度是李普希兹连续的,,模型(6)中
的f()是李普希兹可微的,;Z2,都有下式成立,存
在!≥1,
!2⟨⟩
PMCP(Z1)+∥Z1−Z2∥2≥PMCP(Z2)+***@PMCP(Z2);Z1−Z2:(11)
2
对于[Z2]的每个维度[Z2]i,若[Z2]i=0,则[Z2]i的广义次梯度在[−1;1]之间,如果!足
够大,那么对于任何Z1,我们都有
()!()2
p;
[Z1]i+[Z1]i≥***@p;
(0)·[Z1]i:
2
若[Z2]i̸=0,则[Z2]的二阶梯度为0或−1=
,那么
()()()()1()2
p;
[Z1]i−p;
[Z2]i−***@p;
[Z2]i·[Z1]i−[Z2]i≥−[Z1]i−[Z2]i:
2
故(11)成立.
下面,我们给出几个引理和主要的收敛定理.
引理1对于所有的k,下面的结论成立:
(A1)∇f(k+1)=−BTVk+1;
(A2)∥Zk−Zk+1∥2≤(1=M)∥AZk−AZk+1∥2;
22
(A3)∥k−k+1∥2≤(1=M′)∥Bk−Bk+1∥2;
22
(A4)∥Vk−Vk+1∥2≤(L2=M′)∥k−k+1∥2.
2f2
证明对于(A1),由k+1的最优性条件可知
0=▽f(k+1)+BTVk+cBT(AZk+1+Bk+1);
万方数据:.
第3期王格华,等:分布式变量选择—MCP正则化305
且
Vk+1=Vk+c(AZk+1+Bk+1):
由于M和M′分别为ATA和BTB的最小正特征值,则(A2)和(A3)显然成立.
(A4)可由下式得到
kk+121
Tkk+1
2
∥V−V∥≤
B(V−V)
2M′2
(a)1
2(b)L2
kk+1
fkk+12
=′∇f()−∇f()2≤′∥−∥2;
MM
其中,利用引理1(A1),(a)成立;注意到f是李普希兹可微的,(b)成立.
引理2若c>max{L=2M′;LM′;!=JM},则当k→∞时,L(Zk+1;k+1;Vk+1)
ff
收敛.
证明首先,我们证明在选取合理的预选参数c的情况下,L(Z;;V)在每次ADMM
迭代期间递减.
我们将增广拉格朗日函数之差拆分为
L(Zk;k;Vk)−L(Zk+1;k+1;Vk+1)
(kkkk+1kk)(k+1kkk+1k+1k+1)
=L(Z;;V)−L(Z;;V)+L(Z;;V)−L(Z;;V):
考虑第一项
L(Zk;k;Vk)−L(Zk+1;k;Vk)
=h(Zk)−h(Zk+1)+⟨Vk;AZk−AZk+1⟩
ckk2ck+1k2
+∥AZ+B∥2−∥AZ+B∥2
22
(c)kk+1Tkkk+1
=h(Z)−h(Z)+⟨AV;Z−Z⟩
⟨Tkkkk+1⟩ckk+12
+cA(AZ+B);Z−Z+∥AZ−AZ∥2
2
(d)kk+1⟨k+1kk+1⟩ckk+12
=h(Z)−h(Z)−***@h(Z);Z−Z+∥AZ−AZ∥2
2
(e)!kk+12cMkk+12JcM−!kk+12
≥−∥Z−Z∥2+∥Z−Z∥2=∥Z−Z∥2;
2J22J
其中,利用公式∥b+c∥2−∥a+c∥2=∥b−a∥2+2⟨a+c;b−a⟩,(c)成立,这里a=
222
AZk+1;b=AZk;c=Bk;注意到***@h(Zk+1)=−(ATVk+cAT(AZk+1+Bk)),(d)成
立;利用h(Z)的形式,引理1(A2)和不等式(11),(e)成立.
考虑第二项
L(Zk+1;k;Vk)−L(Zk+1;k+1;Vk+1)
=f(k)−f(k+1)+⟨Vk;AZk+1+Bk⟩−⟨Vk+1;AZk+1+Bk+1⟩
万方数据:.
306工程数学学报第38卷
ck+1k2ck+1k+12
+∥AZ+B∥2−∥AZ+B∥2
22
kk+1Tk+1kk+1⟨k+1k+1k+1k⟩
=f()−f()+⟨BV;−⟩−c(AZ+B);AZ+B
ck+1kk+1kck+1k+12
+⟨AZ+B;AZ+B⟩−∥AZ+B∥2
22
(f)Lfkk+12ckk+121kk+12
≥−∥−∥2+∥B−B∥2−∥V−V∥2
22c
(g)(cM′−LL2)
≥f−f∥k−k+1∥2;
2cM′2
其中,利用引理1(A1)和f为李普希兹可微的,(f)成立;利用引理1(A3)和引理1(A4),
(g),ADMM算法中的迭代满足下式
L(Zk;k;Vk)−L(Zk+1;k+1;Vk+1)
(cM!)(cM′−LL2)
≥−∥Zk−Zk+1∥2+f−f∥k−k+1∥2:
22J22cM′2
如果c>max{Lf=2M′;!=JM},则在ADMM迭代期间L(Z;;V)单调递减.
下面,我们证明增广拉格朗日函数对任意k都有界.
对于任意一个Zk+1,存在′,使得AZk+1+B′=0,那么
L(Zk+1;k+1;Vk+1)
k+1k+1k+1k+1k+1ck+1k+12
=h(Z)+f()+⟨V;AZ+B⟩+∥AZ+B∥2
2
k+1k+1k+1k+1′k+1′ck+1k+12
=h(Z)+f()+⟨V;AZ+B+B−B⟩+∥AZ+B∥2
2
k+1k+1⟨k+1k+1′⟩ck+1k+12
=h(Z)+f()+∇f();−+∥AZ+B∥2
2
k+1′Lf′k+12ck+1k+12
≥h(Z)+f()−∥−∥2+∥AZ+B∥2
22
LfM′c
≥h(Zk+1)+f(′)−∥B′−Bk+1−AZk+1−B′∥2+∥AZk+1+Bk+1∥2
2222
(h)c−LM′
≥h(Zk+1)+f(′)+f∥AZk+1+Bk+1∥2≥h(Zk+1)+f(′)≥0;
22
其中,在(h)中我们假设c>LfM′,则L(Zk+1;k+1;Vk+1)有下界,进而当k→∞时,
L(Zk+1;k+1;Vk+1)收敛.
引理3存在dk+1∈***@L(Zk+1;k+1;Vk+1),使得当k→∞时,∥dk+1∥2→0.
2
证明首先,有
***@L(Zk+1;k+1;Vk+1)=(***@L;∇L;∇L):
ZV
万方数据:.
第3期王格华,等:分布式变量选择—MCP正则化307
因为∇VL=AZk+1+Bk+1=(1=c)(Vk+1−Vk),且由引理1(A4),不等式
L2
∥∇L∥2≤f∥k−k+1∥2
V22′2
cM
,我们有
∇L=∇f(k+1)+BTVk+1+cBT(AZk+1+Bk+1)=BT(Vk+1−Vk);

因此∥∇L∥2=∥BT(Vk+1−Vk)∥2.
22
又因为
***@L=***@h(Zk+1)+ATVk+1+cAT(AZk+1+Bk+1)
ZZ
(i)Tk+1kTk+1k
=A(V−V)+cA(B−B);
其中,利用Zk+1的最优性条件,(i)成立,则有
2
Tk+1k
2
Tk+1k
2
∥***@ZL∥2≤
A(V−V)
+
cA(B−B)
:
22
因为当k→∞时,L(Zk;k;Vk)−L(Zk+1;k+1;Vk+1)→0,结合引理2,我们
有∥Zk−Zk+1∥2→0;∥k−k+1∥2→0,且由引理1(A4),我们有∥Vk−Vk+1∥2→0.
222
进而当k→∞时,∥dk+1∥2→.
2
基于上述三个引理,我们给出ADMM算法收敛性定理.
定理2若c>max{2L=M′;LM′;!=M},则由ADMM算法(8)–(10)产生的序列
ff
收敛到L(Z;;V)的驻点.

为了求解ADMM算法的三个步骤,我们改写增广拉格朗日函数
()∑J∑J()
121
L{Zj};{j};{Vij}=∥Yj−Xjj∥2+PMCP|Zj|
2j=1Jj=1
∑J∑J(
2
2)
c
Vij
Vij
+Eij
Zi−j+
−
:(12)
2j=1i=1c2c2
首先,考虑{Zj}的更新,令
∑J[∑J(
2
2)]
c
Vij
Vij
PMCP(|Zj|)
O(Z)=Eij
Zi−j+
−
+:
j=12i=1c2c2J
根据数据所属计算机的不同,我们将(8)分解为J个子问题
∑J
k+1c2PMCP(|Zj|)
Zj=argminEij∥Qij(k)−Ip×p·Zj∥2+;(13)
Zj2i=1J
万方数据:.
308工程数学学报第38卷
kVijk[25]
其中Ip×p是单位矩阵,Qij(k)=j−(13),对于m=
1;2;···;p,向量Zj的第m个坐标[Zj]m转化为优化下式
∑J
k+1c
(−m)
2p;
(|Z|)
[Zj]m=argminEijQij(k)−Im·Z2+;(14)
Z2i=1J
(−m)∑k
其中Im为Ip×p的第m列,Qij(k)=Qij(k)−l̸=mIl·[Zi]l.(14)的显式解为
b
S(a;Ja)b
k+11−1=Ja
;若|a|≤
;
[Zj]m=(15)
bb
a;若|a|>
;
∑J∑J(−m)
其中a=ci=1Eij;b=ci=1Eij·[Qij(k)]m,S是软阈值算子,当≥0时,

z−;若z>;


S(z;)=0;若|z|≤;


z+;若z<−:
下面,我们给出坐标下降法的收敛性分析.
引理4对于m=1;2;···;p,令Oj;m为目标函数O关于变量Zj的坐标m的函
数,>1=(
∗J),则对于所有坐标m,Oj;m是关
于[Zj]m的一个凸函数.
证明定义d−O(d+O)和d2O(d2O)为O的左(右)导数和二阶左(右)导数.
−+
对于每个组j,所有的坐标m;[Zj]m∈(−∞;+∞),
{}∑J
221
mind−Oj;m(Z);d+Oj;m(Z)≥cEij−:
j=1
∗J
∑J
因为我们假设无向图G是连通的,则对每一个j;j=1Eij≥,如果我们
令c>1=(
∗J),min{d2O(Z);d2O(Z)}>0,则目标函数O在(−∞;+∞)上
−j;m+j;mj;m
为严格凸函数.
(k)
定理3对于任意j=1;2;···;J,令{Zj}表示由坐标下降法(15)生成的序列,如
果参数c>1=(
∗J),则序列既收敛到局部最小值点又收敛到O的全局坐标最小值点.
证明假设预选参数c>1=(
∗J),则对于每个计算机j,和所有维度m;O是关
于[Zj][26]
件,,因此每个坐标
最小值也是局部最小值.
从引理4中我们可以看出,当预选参数c>1=(
∗J)时,对于任何一个j∈J,尽
管目标函数O包含非凸的MCP罚项,它仍是一个关于[Zj]
足某些条件时,目标函数L(Z;;V),(15)收敛于目标函
数(13)的全局最小值.
万方数据:.
第3期王格华,等:分布式变量选择—MCP正则化309
下面,我们考虑的更新,它也可以分解为J个子问题
∑J
Vk
2
(k+1)12c
(k+1)ij
j=argmin∥Yj−Xjj∥2+Eij
Zi−j+
:(16)
j22i=1c2
同样,通过使用坐标下降法,给出局部j的第m个坐标的显式解
(∑J)−1(∑J([Vk]))
k+1TT(−m)k+1ijm
[j]m=XjmXjm+cEijXjmYj+cEij[Zi]m+;(17)
i=1i=1c
其中[k+1]为k+1的第m个坐标,X为设计矩阵X的第m列,
jmjjmj
(−m)∑k
Yj=Yj−Xjl[j]l:
l̸=m
注1如果计算机i与计算机j不连接,则Eij=j时,
只需要计算机j的邻居的信息.
结合(15),(17)和(9),我们提出如下分布式MCP算法.
算法1分布式MCP算法
对∀j∈J,令=(1;···;1)T,Z=(1;···;1)T,V=(1;···;1)T,
ij
局部运行
fork=1;2;···
第j台计算机在Nj与邻居传递信息
对于m=1;2;···;p
利用(15)更新[Zk+1].
j
end
forl=1;2;···;p
利用(17)更新[k+1].
j
end
通过(10)更新拉格朗日乘子V.
end
注2算法1在第k+1次迭代时,计算机j接收来自其邻居的局部估计{Zk′}′;
jj∈Nj
{k}′,然后通过(15)估计Zk+1,通过(17)估计k+1,随后通过(10)估计拉格朗日
j′j∈Njjj
乘数Vk+1.
j

下面,我们给出分布式k折交叉验证算法,以此来选择惩罚参数.
假设∈∧={1;2;···;l},且1>2>···>,我们将整个数据随机
分成K个部分,即S={Xe;Ye}(1≤k≤K)部分数据,可以将计算机j的
iii=1
数据分成两个子集
{(k)(k)}{}∩{}{(−k)(−k)}{}{}
X;Y=Xj;YjXek;Yek;X;Y=Xj;Yj\Xek;Yek;
jjjj
万方数据:.
310工程数学学报第38卷
∩
其中和\为交集和差集算子,则两个子集分别为属于计算机j且属于第k部分的数据以
,我们在{X(k);Y(k)}上计算预测误差,
jj
并在{X(−k);Y(−k)}上拟合非凸模型.
jj
对于不同的;i∈{1;2;···;l},在{X(−k);Y(−k)}上运行分布式MCP正则化,计算
ijj
(−k)l
机协作运行分布式k折交叉验证算法,然后得到{j(i)}i=
k
(k)(k)(−k)
2
ej(i)=
Yj−Xji
:
2
重复上述步骤,我们可以计算每个i的均方误差MSE,使得
∑J∑K
e()=ek():
iji
j=1k=1
最终,我们选择预测误差最小的=argmin{e()}l作为调控参数.
dcviii=1
4实实实验验验
本小节,,实验1通过模拟数据说明算
、实验3通过设计大数据量数据说明算
.
(模拟实验)
在这个实验里,对于我们考虑的线性模型
Y=X+":
我们设置变量数量p=8,具体地=(3;1:5;0;0;0:5;0;0;0);X=(X1;X2;···;X8).
X∼N(0;Σ);Σ=();=0:5|i−j|;1≤i;j≤,我
jijij
们将所有数据划分为J=5组,并选择邻接矩阵

11001


11100


E=01110:


00111

10011
我们模拟了100个数据集,
,
式MCP方法时,用分布式5折交叉验证来选取调节参数,预选参数c=0:
录100组数据集上的正确识别零系数的平均数(),以及错误识别的零系数的平均
数(),结果如表1所示.
从表1中可以看出,非分布式MCP与分布式MCP有相同的变量选择结果,
,,这表明,分布式MCP的变量选择结果比Lasso稀
万方数据:.
第3期王格华,等:分布式变量选择—MCP正则化311
,结果模型和真实模型中值均为0的系数个数的平均
值;,结果模型中值为零但在真实模型中值为非零的系数个
数的平均值.
表1Lasso和分布式MCP在实验1中的结果


分布式MCP(MCP)

在这个实验中,我们模拟数据集n=100000;p=100,其中(1;2;···;20)=
(50;49;···;30);(21;22;···;p)=(0;0;···;0),预选参数c=0:1;X=(X1;X2;···;
X).X∼N(0;Σ);Σ=();=0:5|i−j|;1≤i;j≤
pjijij
时,我们将所有数据划分为J=5组,
结果呈现为图1.
图1当n=100000;p=100时,分