使用mini-batch的并行SGD算法伪代码如下：
参数服务器强调模型训练时参数的并行异步更新，最早是由Google的Jeffrey Dean团队提出，为了解决深度学习的参数学习问题，其基本思想是：将数据集划分为若干子数据集，每个子数据集所在的节点都运行着一个模型的副本，通过独立部署的参数服务器组织模型的所有权重，其基本操作有：Fatching：每隔n次迭代，从参数服务器获取参数权重，Pushing：每隔m次迭代，向参数服务器推送本地梯度更新值，之后参数服务器会更新相关参数权重，其基本架构如下：
From Jeffrey Dean: Large Scale Distributed Deep Networks
每个模型的副本都是，为减少通信开销，每个模型副本在迭代次后向参数服务器请求参数跟新，反过来本地模型每迭代次后向参数服务器推送一次梯度更新值，当然，为了折中速度和效果，梯度的更新可以选择异步也可以是同。参数服务器是一个非常好的机器学习框架，尤其在深度学习的应用场景中，有篇不错的文章： 参数服务器——分布式机器学习的新杀器。开源的实现中比较好的是bosen项目和李沐的ps-lite（现已集成到DMLC项目中）。下面是一个Go语言实现的多线程版本的参数服务器（用于Ftrl算法的优化），源码位置：Goline：
// data structure of ftrl solver.
type FtrlSolver struct {
Alpha float64 `json:"Alpha"`
Beta float64 `json:"Beta"`
L1 float64 `json:"L1"`
L2 float64 `json:"L2"`
Featnum int `json:"Featnum"`
Dropout float64 `json:"Dropout"`
N []float64 `json:"N"`
Z []float64 `json:"Z"`
Weights util.Pvector `json:"Weights"`
Init bool `json:"Init"`
}
// data structure of parameter server.
type FtrlParamServer struct {
FtrlSolver
ParamGroupNum int
LockSlots []sync.Mutex
log log4go.Logger
}
// fetch parameter group for update n and z value.
func (fps *FtrlParamServer) FetchParamGroup(n []float64, z []float64, group int) error {
if !fps.FtrlSolver.Init {
fps.log.Error("[FtrlParamServer-FetchParamGroup] Initialize fast ftrl solver error.")
return errors.New("[FtrlParamServer-FetchParamGroup] Initialize fast ftrl solver error.")
}
var start int = group * ParamGroupSize
var end int = util.MinInt((group+1)*ParamGroupSize, fps.FtrlSolver.Featnum)
fps.LockSlots[group].Lock()
for i := start; i < end; i++ {
n[i] = fps.FtrlSolver.N[i]
z[i] = fps.FtrlSolver.Z[i]
}
fps.LockSlots[group].Unlock()
return nil
}
// fetch parameter from server.
func (fps *FtrlParamServer) FetchParam(n []float64, z []float64) error {
if !fps.FtrlSolver.Init {
fps.log.Error("[FtrlParamServer-FetchParam] Initialize fast ftrl solver error.")
return errors.New("[FtrlParamServer-FetchParam] Initialize fast ftrl solver error.")
}
for i := 0; i < fps.ParamGroupNum; i++ {
err := fps.FetchParamGroup(n, z, i)
if err != nil {
fps.log.Error(fmt.Sprintf("[FtrlParamServer-FetchParam] Initialize fast ftrl solver error.", err.Error()))
return errors.New(fmt.Sprintf("[FtrlParamServer-FetchParam] Initialize fast ftrl solver error.", err.Error()))
}
}
return nil
}
// push parameter group for upload n and z value.
func (fps *FtrlParamServer) PushParamGroup(n []float64, z []float64, group int) error {
if !fps.FtrlSolver.Init {
fps.log.Error("[FtrlParamServer-PushParamGroup] Initialize fast ftrl solver error.")
return errors.New("[FtrlParamServer-PushParamGroup] Initialize fast ftrl solver error.")
}
var start int = group * ParamGroupSize
var end int = util.MinInt((group+1)*ParamGroupSize, fps.FtrlSolver.Featnum)
fps.LockSlots[group].Lock()
for i := start; i < end; i++ {
fps.FtrlSolver.N[i] += n[i]
fps.FtrlSolver.Z[i] += z[i]
n[i] = 0
z[i] = 0
}
fps.LockSlots[group].Unlock()
return nil
}
// push weight update to parameter server.
func (fw *FtrlWorker) PushParam(param_server *FtrlParamServer) error {
if !fw.FtrlSolver.Init {
fw.log.Error("[FtrlWorker-PushParam] Initialize fast ftrl solver error.")
return errors.New("[FtrlWorker-PushParam] Initialize fast ftrl solver error.")
}
for i := 0; i < fw.ParamGroupNum; i++ {
err := param_server.PushParamGroup(fw.NUpdate, fw.ZUpdate, i)
if err != nil {
fw.log.Error(fmt.Sprintf("[FtrlWorker-PushParam] Initialize fast ftrl solver error.", err.Error()))
return errors.New(fmt.Sprintf("[FtrlWorker-PushParam] Initialize fast ftrl solver error.", err.Error()))
}
}
return nil
}
// to do update for all weights.
func (fw *FtrlWorker) Update(
x util.Pvector,
y float64,
param_server *FtrlParamServer) float64 {
if !fw.FtrlSolver.Init {
return 0.
}
var weights util.Pvector = make(util.Pvector, fw.FtrlSolver.Featnum)
var gradients []float64 = make([]float64, fw.FtrlSolver.Featnum)
var wTx float64 = 0.
for i := 0; i < len(x); i++ {
item := x[i]
if util.UtilGreater(fw.FtrlSolver.Dropout, 0.0) {
rand_prob := util.UniformDistribution()
if rand_prob < fw.FtrlSolver.Dropout {
continue
}
}
var idx int = item.Index
if idx >= fw.FtrlSolver.Featnum {
continue
}
var val float64 = fw.FtrlSolver.GetWeight(idx)
weights = append(weights, util.Pair{idx, val})
gradients = append(gradients, item.Value)
wTx += val * item.Value
}
var pred float64 = util.Sigmoid(wTx)
var grad float64 = pred - y
util.VectorMultiplies(gradients, grad)
for k := 0; k < len(weights); k++ {
var i int = weights[k].Index
var g int = i / ParamGroupSize
if fw.ParamGroupStep[g]%fw.FetchStep == 0 {
param_server.FetchParamGroup(
fw.FtrlSolver.N,
fw.FtrlSolver.Z,
g)
}
var w_i float64 = weights[k].Value
var grad_i float64 = gradients[k]
var sigma float64 = (math.Sqrt(fw.FtrlSolver.N[i]+grad_i*grad_i) - math.Sqrt(fw.FtrlSolver.N[i])) / fw.FtrlSolver.Alpha
fw.FtrlSolver.Z[i] += grad_i - sigma*w_i
fw.FtrlSolver.N[i] += grad_i * grad_i
fw.ZUpdate[i] += grad_i - sigma*w_i
fw.NUpdate[i] += grad_i * grad_i
if fw.ParamGroupStep[g]%fw.PushStep == 0 {
param_server.PushParamGroup(fw.NUpdate, fw.ZUpdate, g)
}
fw.ParamGroupStep[g] += 1
}
return pred
}
概览
大部分的优化算法都是基于梯度的迭代方法，其迭代式来源为泰勒展开式，迭代的一般式为：
其中步长，向量 被称作搜索方向，它一般要求是一个能使目标函数值（最小化问题）下降的方向，即满足：
进一步说， 的通项式有以下形式：
是一个对称非奇异矩阵（大家请问为什么？）。
这类优化方法大体分两种，要么是先确定优化方向后确定步长（line search），要么是先确定步长后确定优化方向（trust region）。
以常用的line search为例，如何找到较好的步长X呢？好的步长它需要满足以下条件：
牛顿法(Newton Method)
从泰勒展开式得到牛顿法的基本迭代式：
对牛顿法的改进之一是使用自适应步长X：
但总的来说牛顿法由于需要求解Hessian 矩阵，所以计算代价过大，对问题规模较大的优化问题力不从心。
拟牛顿法(Quasi-Newton Method)
为解决Hessian 矩阵计算代价的问题，想到通过一阶信息去估计它的办法，于是涌现出一类方法，其中最有代表性的是DFP和BFGS(L-BFGS)，其原理如下：
一些有用的资料：
· 最优化相关书籍首推：《NumericalOptimization 2nd ed (Jorge Nocedal, Stephen J.Wright)》
· vw源码：vowpal_wabbit
· John Langford的博客
思考一个问题：为什么通常二阶优化方法收敛速度快于一阶方法？
