分布式计算python_经典分布式计算模型_并行分布式计算(11)

A=[A1,…,AN],Ai∈Rm×ni,x=(x1,…,xN),x∈Rni,→Ax=∑i=1NAixi

于是正则项也可以切分为r(x)=∑Ni=1ri(xi)。那么最初的minl(Ax−b)+r(x)形式就变成了

minl(∑i=1NAixi−b)+∑i=1Nri(xi)

这个与sharing问题非常接近了，做点变化那就是sharing问题了

mins.t.l(∑i=1Nzi−b)+∑i=1Nri(xi)Aixi−zi=0,i=1,…,N⟹xk+1izk+1uk+1=argminxi(ri(xi)+(ρ/2)∥Aixi−Aixki+Ax¯¯¯¯¯k−z¯k+uk∥22))=argminz(l(Nz¯−b)+Nρ/2∥z¯−Ax¯¯¯¯¯k+1−uk∥22)=uki+Ax¯¯¯¯¯k+1−z¯k+1

与之前的globalconsensus问题相比，ADMM框架x-update与z-update似乎是反过来了。于是将此形式直接套到Lasso等高维问题即有很具体的形式解了。

（1）Lasso

xk+1iz¯k+1uk+1=argminxi(λ∥xi∥1+(ρ/2)∥Aixi−Aixki+Ax¯¯¯¯¯k−z¯k+uk∥22))=1N+ρ(b+ρAx¯¯¯¯¯k+1+ρuk)=uk+Ax¯¯¯¯¯k+1−z¯k+1

当|ATi(Aixki+z¯k−Ax¯¯¯¯¯k−uk)|2≤λ/ρ时xk+1i=0（第i块特征不需要用），这样加快了x-update速度,不过这个对串行更有效，对并行起来也没有多大用..

（2）Group Lasso与lasso基本一样，只是在x-update上有一个正则项的不同，有ℓ1-norm变成了ℓ2-norm

xk+1i=argminxi(λ∥xi∥2+(ρ/2)∥Aixi−Aixki+Ax¯¯¯¯¯k−z¯k+uk∥22)

该问题其实就是按组最小化(ρ/2)|Aixi−v|22+λ|xi|2，解为

if∥ATiv∥2≤λ/ρ,otherwisethenxi=0xi=(ATiAi+vI)−1ATiv

涉及矩阵长短计算时，再看矩阵小技巧。

（3）Sparse Logstic Regression也与lasso区别不大，只是z-update的损失函数不同，其余相同于是

z¯k+1=argminz¯(l(Nz¯)+(ρ/2)∥z¯−Ax¯¯¯¯¯k+1−uk∥22)

（4）SVM

SVM与之前的global consensus时候优化顺序反了过来，与logisticrgression只是在z-update步不同（损失函数不同）：

xk+1iz¯k+1uk+1=argminxi(λ∥xi∥22+(ρ/2)∥Aixi−Aixki+Ax¯¯¯¯¯k−z¯k+uk∥22))=argminz¯(1T(Nz¯+1)++(ρ/2)∥z¯−Ax¯¯¯¯¯k+1−uk+1∥)=uk+Ax¯¯¯¯¯k+1−z¯k+1

z-update解析解可以写成软阈值算子

(z¯k+1)i=⎧⎩⎨⎪⎪vi−N/ρ,−1/N,vi,vi>−1/N+N/ρvi∈[−1/N,−1/N+N/ρ]vi<−1/Nvi=(Ax¯¯¯¯¯k+1+u¯k)i

（5）Generalized Additive Models

广义可加模型是一个很适合sharing框架的问题。它本身就是对各个各个特征做了变化后（非参方法），重新表示观测的方式

b≈∑j=1nfj(xj)

当fi是线性变化时，则退化成普通线性回归。此时我们目标优化的问题是

min∑i=1mli(∑j=1nfj(xij)−bi)+∑j=1nrj(fj)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-34812-11.html