计算广告|3.相关方法

最优化Optimization

什么是最优化问题

无约束最优化问题：

$minf(x)$

带约束最优化问题：

$\begin{aligned} min f(x) \\ s.t. \textbf{g}(x)\leqslant 0,\textbf{h}(x)=0 \end{aligned}$

无约束优化问题一般思路

目标函数不可/不易求导

• 下降单纯形法（Ameoba变形虫法）

目标函数易求导

• 梯度下降法
• 批处理模式：训练集上的梯度分解为各个样本梯度的和，可以并行实现。
• 串行模式：随机梯度下降法（Stochastic Gradient Descent，SGD）【好用】

批处理梯度法的问题与拟牛顿法

梯度法zigzag更新过程

• 等高线和梯度垂直，因为等高线的形状是压扁的形状，所以会来回的跳，性能不好。

牛顿法

• 不仅考虑一阶导，还考虑二阶导。但是Hession阵可能不正定。

拟牛顿法

• 用近似但正定的Hession阵确保稳定求解

BFGS和L-BFGS方法

BFGS（Broyden，Fletcher，Oldfarb，and Shanno）

• 拟牛顿法是一种，用函数值和特征的变化量来近似Hession矩阵，以保证正定性，并减少计算量。
• Hession集合公式（空间复杂度为N方）

L（Limited memory）- BFGS

• 将Hession逆用{n*k}*{k*k}*{k*n}的方式近似【矩阵分解】
• 空间复杂度为n*k

Trust-Region方法

方法思想

• 不近似Hession阵，但每次迭代将自变量限制在临域内
• 先步长，后方向

上述子问题虽非凸优化，但是满足KKT条件

对于LR模型收敛速度经常好于L-BFGS

带约束优化：拉格朗日法

原问题（Primary Problem）==> 拉格朗日对偶函数(Lagrangian dual function) ==> 对偶问题(Dual problem)

信息检索Information Retrieval

文档的表示与相似度量

词袋（Bag of Words，BoW）表示

• 用关键词TFIDF组成的矢量来表示文档。

TF-IDF

• TF（term frequency）： 某文档中词出现的次数
• IDF（inverse document frequency）：总文档数/某个词出现的文档数，然后取log

向量空间模型

• 用余弦距离来衡量两个文档的相似度

倒排索引

文档集

• D1=“谷歌地图之父跳槽Facebook”
• D2=“谷歌地图创始人拉斯离开谷歌加盟Facebook”
• D3=“谷歌地图创始人跳槽Facebook与Wave项目取消有关”
• D4=“谷歌地图创始人拉斯加盟社交网络Facebook”

关键词（Term）

• {谷歌，地图，之父，跳槽，Facebook，……}

倒排链

• 谷歌->{D1，D2，D3，D4}，地图->{D1,D2,D3,D4},之父->{D1,D3,D4},跳槽->{D1,D3},Facebook->{D1,D2,D3,D4},……

统计机器学习Statistical Machine Learning

贝叶斯学习

$P(\Theta | X ) = \frac{P(X | \Theta)P(\Theta)}{P(X)}$

贝叶斯公式

• 统计机器学习最核心的概念和公式。
• 频率学派 VS 贝叶斯学派
• X是观测的变量，Theta是要估计的参数。
• $P(\Theta | X ) $ 是后验概率Posterior，所有的分类都是追求后验概率最大的原则。
• $P(X | \Theta)$是likelihood(已知是黑人，黑人拥有黑色皮肤的概率)，$P(\Theta)$是prior（黑人在中国出现的概率）.
• $P(X)$ 是evidence
• 贝叶斯的核心是认为所有参数都是不确定的。

若干模型估计方法

指数族分布

归一化形式：$P(x|\Theta)=h(x)g(\Theta)exp\left \{ \Theta^Tu(x) \right \}$

若干重要指数族分布

指数族贝叶斯学习

共轭先验：使先验分布与后验分布形式一致的先验分布

指数族分布共轭先验，一般形式：

$p(\Theta|\eta)=exp\left \{ \chi ^{T} \Theta-vg(\Theta)-b(\chi ,v))) \right \}$

其中$\eta=\left \{ \chi, v \right \}$为超参数（hyperperameter）

指数族后验部分的超参数：

$\tilde{\chi} = \chi + \sum_{N}^{i=1}u(x_i)$

$\tilde{v} = v + N$

指数族分布（二）

最大似然估计：$-\triangledown ln \textbf{g}(\theta_{ML} )=\frac{1}{N}\sum_{i=1}^{N}u(x_i)$

混合模型：$P(x|\omega , \Theta)=\sum_{k=1}^{K}w_kh(x)g(\Theta_k)exp\left \{ \Theta_{k}^{T}u(x) \right \}$

• EM算法

深度学习Deep Learning

深度学习是什么？

基于规则的系统

• img of 8 --> 人工设计程序 --> num of 8

传统机器学习

• img of 8 --> 人工设计特征 --> 将特征映射到结果 --> num of 8

深度学习(表示学习)

• img of 8 --> 自动提取特征 --> 将特征映射到结果 --> num of 8
• img of 8 --> 原始特征 --> 额外的层和抽象特征 --> 将特征映射到结果 --> num of 8

全连接多层感知机（Multi-layer Perceptron, MLP）

深度学习的工程本质

浅层模型与深度模型

• 深度模型比浅层模型表示能力更强

优化方法是关键

• 找到了GPU这条优化方法

数据的作用

• 深度学习和大数据关系非常紧密

几种重要的神经网络结构

CNN（Convolutional Neural Networks, 卷积神经网络）

• 采样层->卷积层->采样层->全连接层MLP
• 参数共享
• 图像领域

RNN（Recurrent Neural Networks，递归神经网络）

• 用递归的方式设计网络结构
• sequence到sequence的学习
• 语言领域
• LSTM（Long-Short Term Memory，长短期记忆）是一种时间递归神经网络(RNN)

GAN（Generative Adversarial Network，生成对抗网络）

深度学习优化基础设施

GPU方案

• 并行渲染屏幕上每个像素点，与并行计算各神经元很相似
• 与CPU方案相比，可以加速数倍乃至十数倍

并行计算方法

• SGD过程可以分解到多台机器上进行，分别更新参数
• 可以采用parameter server的计算框架，水平扩展性强

开源框架

• Tensorflow，Caffe，Mxnet，可以一定程度上忽略硬件

数据运营三板斧 – 用户增长

用户增长的基础：用户转化漏斗

用户转化漏斗示例

• 移动用户获取：下载->激活->留存->时长
• 电商用户转化：到达商品页->加入购物车->完成订单->交易确认

漏斗的设计原则与作用

• 原则：整个漏斗过程用于优化一个唯一的目标
• 作用：将该目标分解为若干比率的乘积，便于发现问题并优化
• 示例：总用户时长 = 下载量 X 激活率 X 留存率 X 平均用户时长

转化漏斗相关常见度量

• 转化率 - 激活数与点击数的比
• 「次日/七日/月」留存率 - 某日激活的用户中，「次日/七日/月」后活跃的用户占比
• 「日/月」活跃用户（DAU，MAU）- 每「日/月」活跃的独立用户数
• 用户时长 - 每个活跃用户平均消耗的时间

找到增长的障碍：多维度报表分析

通过漏斗发现问题

• 某页游用户转化漏斗：
• 到达（5130）–19.1%–>注册（980）–14.0%–> 参与（431）–83.0%–> 充值
• 注册率偏低，应该进一步分析？

在多维度报表中找到症结

• 注册率19.1% – IE(25.1%),Chrome(3.5%),FireFox(22.7%)

数据魔方（Data Cube）

• 什么是数据魔方？ 1）用户可以较灵活选择维度组合，得到定制化报表。2）为人工决策提供便利
• 技术方案：OLAP数据库
• 开源方案：Saiku+MySQL

驱动新产品特征：利用A/B测试

为什么需要A/B测试？

• 多维情况下，魔方里大部分区域数据非常稀疏。极端情形：对于新Feature，需要主动分配测试流量
• 某维度上的两个选项（例如两个不同的模型），数据并不是完全可比
• 因此，我们需要一个主动的A/B测试框架，以便：1）主动分配流量给新的产品特征；2）保证对比实验的各组在数据上完全可比；3）尽可能在同样的流量规模上容纳更多的实验。

A/B测试并不是万能的

• 用户产品过于依赖数据会丧失对关键创新的把握。- 汽车无法从“跑得更快的马”进化而来
• 多数情况下，需要测试的可行组合太多，必须先经过人的筛选，或更复杂的E&E策略。- 每天数十万的新闻，那些有可能最受用户欢迎？
• 博弈性场景无法通过A/B测试获得可靠性结论
• A/B测试最适合的场景：理性产品、被动反应场景