online learning algorithm taoshuai

2020-03-01 232浏览

  • 1.A Survey on Algorithms of the Regularized Conv ex Optimization Problem Shuai Tao 2014.6.20
  • 2.Outline • 传统方法 • Truncated Gradient and FOBOS • RDA (Regularized Dual Averaging) • FTRL (Follow-the-regularized-Leader)
  • 3.问题描述 • 最小化的目标函数（无约束优化）， soft r egularization formulation ： • 另一种等价约束优化描述， convex const raint formulation ：
  • 4.批量（ Batch ）算法 • 无约束优化表示 – 全局梯度下降： – 牛顿顿 法、 顿 LBFGS 等方法 • 不等式约束凸优化问题 • 投影梯度下降（约束优化表示下）， gt 是 subgra dient
  • 5.批量算法 – 传统不等式约束的凸优化方法：内点法（转化为规则化的 无约束优化）等 • 批量算法的优缺点 – 优点 • 精度高 – 局限性 • 受限于被训练数据的规模 • 无法有效处理数据流，做在线训练
  • 6.在顿 算法 顿顿 • 在线梯度下降（ OGD ） • 随机梯度下降（ SGD ），在凸集上做投影 混合正则化项：
  • 7.在线算法 • 梯度下降方法 – 精度比较好 – 局限性 • 很难产生真正稀疏的解，即便加入 L1 正则化项 • 对于不可微点的迭代会存在一些问题（ the iterates of the subgradi ent method are very rarely at the points of non-differentiabilit y）
  • 8.Outline • 传统方法 • Truncated Gradient and FOBOS • RDA (Regularized Dual Averaging) • FTRL (Follow-the-regularized-Leader)
  • 9.稀疏性的考量 1. 简单加入 L1 范数 – a+b 两个 float 数很难绝对等于零，无法产生 真正稀疏的特征权重 2. 那就设定一个阈值，做截断来保证稀疏， 可以结合 L1 范数 – 简单截断方法，每 online 训练 K 个数据截断 一次
  • 10.稀疏性的考量 – Truncated gradient （ 09 年的工作） 3. Black-box wrapper approaches ： – 黑盒的方法去除一些特征，然后重新顿顿顿 的看被消 顿顿 顿 去的特征是否有效。 – 需要在数据集上顿顿 算法跑多次，不太 顿 顿 顿 顿 顿 顿 顿 顿顿 用
  • 11.FOBOS Forward-Backward Splitting method (g oogle 和伯克利 09 年的工作） – 可以看作 truncated gradient 的一种特殊形 式 – 基本思想：跟 projected subgradient 方法 类似，不过将每一个数据的迭代过程，分解成 一个经验损失梯度下降迭代和一个优化问题
  • 12.Outline • 传统方法 • Truncated Gradient and FOBOS • RDA (Regularized Dual Averaging) • FTRL (Follow-the-regularized-Leader)
  • 13.RDA • Regularized dual averaging （微软 10 年的工作） – 非梯度下降的范畴，属于更加通用的一个 prim al-dual algorithmic schema 的一个应用 – 克服了 SGD 类方法所欠缺的 exploiting prob lem structure ， especially for problems with explicit regularization 。 – 能够更好地在精度和稀疏性之间做 trade-off
  • 14.Outline • 传统方法 • Truncated Gradient and FOBOS • RDA (Regularized Dual Averaging) • FTRL (Follow-the-regularized-Leader)
  • 15.FTRL (Follow-the-regularized-Leade r) • FTRL （改进与实际应用 H. Brendan McMahan, google ） – 10 年理论性 paper ，但未显式地支持正则化项迭代； 11 年证明 regret bound 以及引入通用的正则化项； 1 1 年另一篇的 paper 揭示 OGD 、 FOBOS 、 RDA 等算 法与 FTRL 关系； 13 年的 paper 给出了工程性实现的 paper ，并且附带了详细的伪代码，开始被大规模应用 。 – 可以看作 RDA 和 FOBOS 的混合，但在 L1 范数或者其 他非光滑的正则项下， FTRL 比前两者更加有效
  • 16.FTRL (Follow-the-regularized-Leade r) – 基本思想 OGD 不够稀疏 FOBOS 能产生更 加好的稀疏特征 RDA 可以在精度与稀疏性 之顿 做更好的平衡 顿顿顿顿顿顿 梯度下降顿 方法，精度比 顿顿顿顿顿顿顿顿 好 最关键的不同点是累 积 L1 惩罚项的处理方 式 FTRL 综合 OGD 的精度和 RDA 的稀疏性 稀疏性更加出色
  • 17.FTRL (Follow-the-regularized-Leade r) • 迭代公式 – 再看一下 OGD • OGD 迭代公式的等价优化问题的含义： – 每次新的结果不要太远离之前的结果 – 每一步还是要向正确的方向前进（梯度 or 子梯度方向）
  • 18.FTRL (Follow-the-regularized-Leade r) – Mirror decent • 利用了上面的直观特性，但是用 arbitrary Bregm an divergence 代替二范数项，并更进一步，对历 史点的 bregman 项叠加起来： – Composite-objective mirror descent （ C OMID ） • 每一轮将正则化项加入到目标函数中（例如 1 范 数）
  • 19.FTRL (Follow-the-regularized-Leade r) • 迭代方程 – 第一项：梯度或累积梯度； – 第二项： L1 正则化项； – 第三项：限定 x 不要离已迭代过的解太远（ proximal ） ，或者离 0 太远（ central ），也是 low regret 的需求
  • 20.伪代码 实现上做了不少 trick ，具体可以查看 13 年工程实现的那篇 paper
  • 21.Memory saving • Predict 时的 memory saving – L1 范数加策略，训练结果 w 很稀疏，在用 w 做 predict 的时候节省了内存 • Training 时的 memory saving – 在线丢弃训练数据中很少出现的特征 (probabi listic feature inclusion) • Poisson Inclusion • Bloom Filter Inclusion
  • 22.Memory saving – 浮点数重新编码 • 特征权重用不到 32bit 或 64bit 的浮点数，存储浪费空间 • 16bit encoding ，但是要注意处理 rounding 技术对 re gret 带来的影响 – 训练若干相似 model • 对同一份训练数据序列，同时训练多个相似的 model • 这些 model 有各自独享的一些 feature ，也有一些共享 的 feature • 出顿 顿 点：有的特征 顿顿 顿顿 顿 顿顿 度可以是各个模型独享的，而有的各 顿 顿顿 顿顿 顿顿 顿 顿顿 顿 顿顿 顿顿 个模型共享的特征，可以用同样的数据训练。
  • 23.Memory saving – Single Value Structure • 多个 model 公用一个 feature 存储（例如放到 cbase 等）， 各个 model 都更新顿顿 个共有的 顿 顿 顿 feature 结构 • 顿于 某一个model ，对于他所训练的特征向量的某一维，直 接计算一个迭代顿顿 果并与旧 顿 顿 顿 顿顿 做一个平均 顿顿 顿顿 – 使用正负样本的数目来计算梯度的和（所有的 model 具有同样的 N 和 P ）
  • 24.Memory saving – Subsampling Training Data • 在实际中， CTR 远小于 50% ，所以正样本更加有 价值。通过对训练数据集进行 subsampling ，可 以大大减小训练数据集的大小 • 正样本全部采（至少有一个广告被点击的 query 数 据），负样本使用一个比例 r 采样（完全没有广告 被点击的 query 数据）。但是直接在这种采样上进 行训练，会导致比较大的 biased prediction
  • 25.Memory saving • 解决办法：训练的时候，对样本再乘一个权重。权 重直接乘到 loss 上面，从而梯度也会乘以这个权重 。
  • 26.References [1] J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient.JMLR, 10, 2009 . [2] H. B. McMahan. Follow-the-regularized-leader and mirrordescent:Equivalence theorems and L1 regularization. In AISTATS, 2011 [3] L. Xiao. Dual averaging method for regularized stochastic learning and online optimization. In NIPS, 2009 [4] J. Duchi and Y. Singer. Efficient learning using forward-backward splitting. In Advances in Ne ural Information Processing Systems 22, pages 495{503. 2009. [5] H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, Jeremy Kubica, Ad ClickPrediction:a View from the Trenc hes, Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery an d Data Mining (KDD) (2013) [6] H. Brendan McMahan. A unied analysis of regular-ized dual averaging and composite mirror d escent with implicit updates. Submitted, 2011 [7] H. Brendan McMahan and Matthew Streeter. Adap-tive bound optimization for online convex optimiza-tion. InCOLT, 2010
  • 27.Thanks Q&A