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

（1）Least Absolute Deviations

先从一个简单的问题开始。在稳健估计中，LAD是一个应用很广的模型，相对于直接优化平方和损失|Ax−b|22，优化绝对损失|Ax−b|1，它的抗噪性能更好。在ADMM框架下，往之前的受约束的凸优化问题靠拢，这个问题有简单的迭代算法

mins.t.∥z∥1Ax−b=z⟹letf(x)=0,g(z)=∥z∥1⟹xk+1zk+1uk+1=(ATA)−1AT(b+zk−uk)=S1/ρ(Axk+1−b+uk)=uk+Axk+1−zk+1−b

（2）Huber fitting

Huber问题与上面的其实差不多，只是损失函数形式不同，换成了Huber惩罚函数

mins.t.ghub(z)Ax−b=z,ghub(z)=⎧⎩⎨z2/2,|z|−12|z|≤1|z|>1

因此与LAD除了z-update不在是proximity operator（或称作软阈值）之外，其余均是相同的

zk+1=ρ1+ρ(Axk+1−b+uk)+11+ρS1+1/ρ(Axk+1−b+uk)

看着像是proximity operator与一个残差的加权。

LAD和Huberfitting这种问题只是一些传统损失不加正则项的ADMM化，注意一定要构造个z出来即可，x可以基本不用管，总是需要解的，下面的带有正则项的优化问题，ADMM形式就会更明显。

（3）Basis Pursuit

基追踪法师系数信号处理的一种重要方法。目的是想找到一组稀疏基可以完美恢复信号，换套话说就是为一个线性方程系统找到一个稀疏解。原始形式如下，与lasso有些像：

mins.t.∥x∥1Ax=b

修改成ADMM形式，注意往之前受约束的凸优化问题的那种形式回套，将ℓ1看做约束，然后构造带定义域的f(x)，于是就有解

mins.t.f(x)+∥z∥1x−z=0f(x)=I({x∈Rn|Ax=b})indicatorfunction⟹xk+1zk+1uk+1=Π(zk−uk)=S1/ρ(Axk+1+uk)=uk+xk+1−zk+1

其中Π(zk−uk)是向一个线性约束的欧式空间中投影x∈Rn∣Ax=b，这也是有直接的显示解的

xk+1=(I−AT(ATA)−1A)(z−uk)+AT(AAT)−1b

对于矩阵求逆、分解等用之前矩阵那些小技巧即可加快计算，节省计算资源。

最近还有一类算法来解决ℓ1问题，被称作Bregman iteration methods，对于基追踪相关问题，加正则项的Bregmaniteration就是method of multiplier，而所谓的split Bregman iteration就等同于ADMM。我没有继续深究，应该就是类似于并行化的ADMM算法来解决基追踪问题。

（4）一般化的损失函数 + ℓ1正则项问题

这类问题在高维统计开始时便是一个非常重要的问题，而即使到了现在也是一个非常重要的问题，比如grouplasso，generalizedlasso，高斯图模型，Tensor型图模型，与图相关的ℓ1问题等算法的开发，都可以在此框架上直接应用和实施，这正是ADMM一个优势所在，便于快速实施，也便于可能的分布式部署。

minl(x)+λ∥x∥1,⟹mins.t.l(x)+g(z)=l(x)+λ∥z∥1x−z=0⟹xk+1zk+1uk+1=argminx(l(x)+(ρ/2)∥x−zk+uk∥22)=S1/ρ(Axk+1+uk)=uk+xk+1−zk+1

可以看到与Basis Pursuit解法只是在x-update上有区别：BasisPursuit是构造出来一个投影函数f(x)，而一般化的损失函数f(x)+ℓ1正则项问题，用ADMM就更为自然。所以很适合作为框架来解决这一类问题：广义线性模型（普通线性、logistic回归、possion回归、softmax回归）+正则项；广义可加模型+正则项；似然函数（高斯图方向）+正则项。

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