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

Consensus4.1 全局变量一致性优化（Global variable consensusoptimization）（切割数据，参数（变量）维数相同）所谓全局变量一致性优化问题，即目标函数根据数据分解成N子目标函数（子系统），每个子系统和子数据都可以获得一个参数解xi，但是全局解只有一个z，于是就可以写成如下优化命题：

mins.t.∑i=1Nfi(xi),xi∈Rnxi−z=0

注意，此时fi:Rn→R⋃+∞仍是凸函数，而xi并不是对参数空间进行划分，这里是对数据而言，所以xi维度一样xi,z∈Rn，与之前的问题并不太一样。这种问题其实就是所谓的并行化处理，或分布式处理，希望从多个分块的数据集中获取相同的全局参数解。

在ADMM算法框架下（先返回最初从扩增lagrangian导出的ADMM），这种问题解法相当明确：

Lρ(x1,…,xN,z,y)=∑i=1N(fi(xi)+yTi(xi−z)+(ρ/2)∥xi−z∥22)s.t.C={(x1,…,xN)|x1=…=xN}

⟹xk+1izk+1yk+1i=argminx(fi(xi)+(yki)T(xi−zk)+(ρ/2)∥xi−z∥22))=1N∑i=1N(xk+1i+(1ρyki))=yki+ρ(xk+1i−zk+1)

对y-update和z-update的yk+1i和zk+1i分别求个平均，易得y¯k+1=0，于是可以知道z-update步其实可以简化为zk+1=x¯k+1，于是上述ADMM其实可以进一步化简为如下形式：

xk+1iyk+1i=argminx(fi(xi)+(yki)T(xi−x¯k)+(ρ/2)∥xi−x¯k∥22))=yki+ρ(xk+1i−x¯k+1)

这种迭代算法写出来了，并行化那么就是轻而易举了，各个子数据分别并行求最小化，然后将各个子数据的解汇集起来求均值，整体更新对偶变量yk，然后再继续回带求最小值至收敛。当然也可以分布式部署（hadoop化），但是说起来容易，真正工程实施起来又是另外一回事，各个子节点机器间的通信更新是一个需要细细揣摩的问题。

另外，对于全局一致性优化，也需要给出相应的终止迭代准则，与一般的ADMM类似，看primal和dual的residuals即可

∥rk∥22=∑i=1N∥xki−x¯k∥22,∥sk∥22=Nρ∥x¯ki−x¯k−1∥22

4.2 带正则项的全局一致性问题下面就是要将之前所谈到的经典的机器学习算法并行化起来。想法很简单，就是对全局变量加上正则项即可，因此ADMM算法只需要改变下z-update步即可

mins.t.∑i=1Nfi(xi)+g(z),xi∈Rnxi−z=0⟹xk+1izk+1yk+1i=argminx+i(fi(xi)+(yki)T(xi−zk)(ρ/2)∥xi−z∥22))=argminz(g(z)+∑i=1N(−(yki)Tz+(ρ/2)∥xk+1i−z∥22))=yki+ρ(xk+1i−zk+1)

同样的，我们仍对z做一个平均处理，于是就有

zk+1=argminz(g(z)+(Nρ/2)∥z−x¯k+1−(1/ρ)y¯k∥22)

上述形式都取得是最原始的ADMM形式，简化处理，写成scaled形式即有

xk+1izk+1uk+1i=argminx(fi(xi)+(ρ/2)∥xi−zk+uki∥22))=argminz(g(z)+(Nρ/2)∥z−xk+1i−u¯k∥22)=uki+xk+1i−zk+1

这样对于后续处理问题就清晰明了多了。可以看到如果g(z)=λ|z|1，即lasso问题，那么z-update步就用软阈值operator即可。因此，对于数据，要想用lasso等算法，只需要对数据做切块（切块也最好切均匀点），纳入到全局变量一致性的ADMM框架中，即可并行化处理。下面给出一些实例。

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