引子

• 受众: 技术杂志的读者，受过计算机教育但是领域比较泛。要求有简单的数学基础和机器学习的背景知识。
• 主题：不讲机器学习算法是什么,讲学习算法如何和应用场景结合的问题
• 逻辑: 发现问题-分析问题-解决问题

合约投放系统

直接媒体购买

合约广告英文是Agreement-based Advertising，它是一种基于合约(Agreement)的商业模式，大家会看到它与Network和Exchange有相当大的不同，我们当前最主要的是把合约广告要解决的问题理解清楚，具体的技术可以再理解。

传统的广告媒体购买方式是称之为直接媒体购买方式(Direct Media Buy)。 它是一种简单的购买方式，比如一个杂志可能有几个广告位，比如封二页，封底页，广告主可以直接购买这些广告位，这种方式没有任何的技术元素。在这种方式的运作中，Supply有一个广告排期系统，广告排期系统比较简单，用于对购买了的广告位，以及相应的时间的广告排期。不提供受众定向，它在展示时将广告素材直接插入页面，这样广告作为静态资源加载，它的response time就会比较短，这样用户看到广告也越早，效果也就也越好。这种方式的代表公司是4A。需求方，即广告代理商要做的是两件事情：

1. 帮助广告商策划和执行排期，
2. 用经验和人工满足广告商的质和量的需求。

比如宝马公司今年要reach多少用户，通过什么要的媒体reach，4A公司就会帮宝马公司把创意做好，并分析在哪些媒体，哪些位置上投放广告，能达到效果。因为没有技术元素，所以都是要依赖经验和人工的方式来完成的。但令人惊讶的是，中国很多品牌广告仍然是以为种方式进行的。

30天学30种技术

RedHat负责OpenShift技术推广的Shekhar Gulati从2013年10月29日开始，立下心愿要在30天内学习30种技术

现在，他完成了。他自己的头衔也编程了“30天学30种技术”博客作者，比Evangelist感觉的确强不少。这个系列当然也为OpenShift网站带来了不少流量和关注度。国内做技术营销的同学，学着点吧。

算法描述

应用场景

优缺点

问题

场景

相关反馈

方法

为什么要实时

1. 每天新发布
2. 每天修改的商品
3. 各种换季、打折、促销、新款、活动
4. 突发事件
5. 新增加用户
6. 用户兴趣漂移

长尾商品更多的曝光机会 流量动态利用

TIP: 提供一些数据支持，iPV/IPV

本文参考了博文Online Learning in Clojure和论文Pegasos: Primal Estimated sub-GrAdient SOlver for SVM(PDF)

online learning

Online learning的算法结构是非常简单的，下面的描述是监督的online learning算法框架，其中有经验损失函数$L$，样本流$S$，样本的格式为$(x,y)$:

Initialise a starting model w
While there are more examples in S
    Get the next feature vector x
    Predict the label y' for x using the model w
    Get the true label y for x and incur a penaly L(y,y')
    Update the model w if y ≠ y'

一般来是，训练出来的模型都是一个与样本相同维度的向量。对应二分的分类器，往往涉及到的是计算内积$\langle w,x \rangle$，模型的更新是沿着损失函数的梯度下降方向的。

Pegasos

论文Pegasos: Primal Estimated sub-GrAdient SOlver for SVM是一种svm的online learning算法。

预备知识

共轭函数，凸优化，对偶函数，对偶问题

1. 对偶问题

首先，以等价约束的凸优化问题为例：

$$\text{minimize} \; f(x) \\\\ \text{subject to} \; Ax = b$$

f(x)是凸函数, x是N维变量

该问题的拉格朗日问题是：

$$L(x,y) = f(x) + y^t(Ax-b)$$

对偶函数： $$ g(y) = \inf_{x}{L(x,y)} = -f^\star(-A^Ty)-b^Ty $$

y是对偶变量，$f^\star$是f的凸共轭函数

对偶问题

$$\text{maximize}\; g(y)$$

ADMM的方法：先确定y，然后根据y得到x;交换顺序，确定x，计算y

$$x^{k+1} = argminL(x,y^k) \\ y^{k+1} = y^k + \alpha^k (Ax^{k+1} - b)$$

相关资料

ADMM是一种通用的并行优化策略, 它可以非常方便的在分布式环境的迭代优化计算，ADMM的算法文档可参考:ADMM文档

• ADMM
• MPI example for alternating direction method of multipliers
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

算法

1. paralled Dual-ADMM
2. FISTA
3. GRock

代码

• admm-hadoop
• admm-lasso-without-mpi
• admm-mpi
• Parallel and Distributed Sparse Optimization

可预测性理论

Predictability and Information Theory. Part I: Measures of Predictability

如何度量