怎样更省更准地做点击预测？用凸优化！——读一篇Google的论文

线性逻辑回归模型参数迭代方程求解：
\[从\min :\left(g_{1:t}\cdot \omega+\frac{1}{2}\sum_{s=1}^{t}\sigma_s{\|\omega-\omega_s\|}_{2}^{2}+\lambda_1{\|\omega\|}_1 \right)中求解\omega_{t+1}=\omega,优化函数R^d \to R\]
1.Logloss函数的梯度：
\[\begin{alignat}{1}
\\a.&假设线性CTR预测模型:p_t=\sigma(\omega_t \cdot x_t＋\epsilon)  \quad\omega_t\in R^d: 第t轮系数 \quad x_t\in R^d :第t轮特征
\\ \quad
\\& sigmoid函数\sigma(a)=\frac{1}{1+e^{-a}},目标观测:y_t=\{0,1\}
\\ \quad
\\b.&特征作为条件的综合事件点击概率P(y_t|x_t)= {p_t}^{y_t} \cdot (1-p_t)^{1-y_t}
\\ \quad
\\c.&定义Logloss为负的条件点击率Log似然函数:l_t(\omega_t)=- \log P(y_t|x_t)＝－y_t \log p_t－(1-y) \log (1-p_t)
\\ \quad
\\d.&记Logloss梯度g_t=\nabla l_t(\omega_t)=\frac{\partial l_t(\omega_t) }{\partial \omega_{t,1}} \cdot j_{t,2}+\frac{\partial l_t(\omega_t) }{\partial \omega_{t,2}} \cdot j_{t,2}+\cdots +\frac{\partial l_t(\omega_t) }{\partial \omega_{t,d}} \cdot j_{t,d}
\\&记g_{t,i}=\frac{\partial l_t(\omega_t) }{\partial \omega_{t,i}} \cdot j_{t,i} \quad g_{1:t}=\sum_{s=1}^{t}g_s
\\&包含sigmoid函数的梯度表示： \end{alignat}
\]
2.机器学习效率：
\begin{alignat}{1}a.常用定义：&第t轮学习效率\eta_t=\frac{1}{\sqrt{t}}，\sigma_t=\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}=\sqrt{t}-\sqrt{t-1}\\b.Ftrl \,Proximal定义：&第i维第t轮学习效率\eta_{t,i}=\frac{1}{\frac{\beta+\sqrt{n_i}}{\alpha}+\lambda_2}\\c.参考定义：&第i维第t轮学习效率\eta_{t,i}=\frac{\alpha}{\beta+\sqrt{\sum_{s=1}^{t}g_{s,i}^{2}}} ,\quad b \Leftrightarrow c意味:\alpha \lambda_2=\beta \quad n_i=\sum_{s=1}^{t}g_{s,i}^{2} \end{alignat}
3.迭代方程形式变换：
\begin{alignat}{1}g_{1:t}\cdot \omega+\frac{1}{2}\sum_{s=1}^{t}\sigma_s{\|\omega-\omega_s\|}_{2}^{2}+\lambda_1{\|\omega\|}_1=&g_{1:t}\cdot \omega+\frac{1}{2}\sum_{s=1}^{t}\sigma_s (\omega-\omega_s)\cdot(\omega-\omega_s)+\lambda_1{\|\omega\|}_1\\=&g_{1:t}\cdot \omega-\sum_{s=1}^{t}\sigma_s \omega_s \cdot \omega+\frac{1}{2}\sum_{s=1}^{t}\sigma_s \omega^2+\frac{1}{2}\sum_{s=1}^{t}\sigma_s {\omega_s}^2+\lambda_1{\|\omega\|}_1
\\=&\left(g_{1:t}-\sum_{s=1}^{t}\sigma_s \omega_s \right) \cdot \omega \end{alignat}
4.解出令目标函数达到最小值的参数迭代方式：

！！！！！！！！！！！！！！！

怎么理解？

5.\beta和梯度一个级别，\alpha和常数１一个级别
6.以某种模型和数据集作为基准去和其他的进行比较
11.\lambda_1是控制梯度和的
14.\eta_i表示per-coordinate的学习效率
16.使得将实数Ｒ映射到[0,1]
25.D. W. Hosmer and S. Lemeshow. Applied logistic regression是独立同分布的
46.论文T. Fawcett. An introduction to roc analysis.
53.Regularized Dual Average,精确性比FOBOS好的方法。
58.逻辑回归的loss梯度
62.逻辑回归的loss函数
63.sigmoid函数是从指数族分布特点导出
64.t是迭代次数
65.w_t是模型参数
66.z梯度之和
67.i第i个coordinate
68.对per-coordinate的logloss函数的梯度进行迭代
77.logloss指的是信息损失来自信息学定义
82.n梯度的平方
84.学习效率以梯度和开放之差放进模型，还带一个参数\alpha.
90.体现在per-coordinate系数的定义上面了
93.把实数映射到0,1之间
107.参数\alpha,\beta,\lambda_1,\lambda_2都是需要调节，调参
109.是的
110.t在循环逻辑回归，w_{t,i}就是sigmoid函数中的参数，ｔ的迭代使每个coordinate的逻辑回归系数以某种方式改变，
111.1/1+e^{w_{t,i}x}
104.把最大似然函数的相反数作为梯度下降的对象，没到零就是loss
127.每一个coordinate参数的改变依赖与梯度的和，当梯度的和太小就忽略掉，如果梯度的和足够大就赋于coordinate线性参数。
128.根据学习效率赋值的。
129.超过\lambda_１的部分乘以负的学习效率
133.带坐标指标导数之和：
\[\nabla l_t(w)=\frac{\partial l_t(w) }{\partial  x_1} \cdot i_1+\frac{\partial l_t(w) }{\partial  x_2} \cdot i_2+\frac{\partial l_t(w) }{\partial  x_3} \cdot i_3+\frac{\partial l_t(w) }{\partial  x_d} \cdot i_d\]
它成为一个向量。
137.使得之前累积参数，梯度，预测值等的一个函数取到最小值时候的参数ｗ取为下一阶段的逻辑回归梯度下降参数，但是实际上它并不是梯度下降的参数。
159.广告数据和搜索数据

5.评估模型表现

用历史日志数据评估模型质量是最节省的方式（用live流量数据做评估很重要却也很贵[30]）
因为不同度量以不同方式反应模型变化，我们发现用多数可能的表现度量能很好地评估模型变化。我们计算AucLoss(也就是说，1-AUC，AUC是ROC曲线度量下的标准area),LogLoss,方差。为了一致性，我们定义的度量满足越小越好的要求。

5.1Progressive 验证

我们通常使用Progressive验证有时候也被叫做线上loss而不是对held out数据集做交叉验证。因为给学习效率计算梯度需要九三一个预测，我们可以便宜地把那些预测穿起来做接下去的分析，每小时聚合一次。我们也通过计算在数据集上的小块比如按国家，查询，主题，构架分的故障。
online loss能很好地代表我们提供查询服务的准确性，因为它只度量在我们训练之前最近的数据——准确地分析了当模型用到服务查询中的情形。Online Loss也有相当不错统计比held-out的数据集，因为我们使用我们所有的数据做训练和测试。这点非常重要因为很小的进展能对大型的需要大量可信观测数据带来有价值的影响。
绝对的度量值通常带有误导性。尽管预测是很完美的，LogLoss和其他度量依据问题的难度变化。(也就是贝叶斯风险)。如果点击率接近0.5，最好的能达到的LogLoss在点击率接近0.2的时候要高得多。这点很重要因为点击了随着国家，搜索变化，因此平均化了这个课题在一天中的变化。
我们因此总是关注相对的变化，通常被表示成基于一个baseline的模型。据我们的经验，相对的改变随着时间相对更稳定。我们也关注从同样数据计算出来的不同度量，比如，一个模型上一段时间内loss度量和另一个模型在另外一段时间内的loss度量是不可比的。

5.2通过可视化更深入的理解

在大规模学习中可能遇到的一个陷阱是聚合的表现度量会隐藏子块数据的特定效果。这使得不光光使用聚合的数据是必要的，需要针对一个块的数据做统计。
因为有太多细分有意义数据的方式，我们需要可视化的总结数据很有必要。我们开发出了一个高维的交互可视化工具叫做GridViz来允许复杂的数据理解。
图２中展示了一组按照查询主题的两个模型同一个base模型比较的结果。度量值用有色块表示，行相关模型名职，列相关数据块。Column的宽度表示分块的重要性，也可以被设置成去反应展示的数量或者点击的数量。
因为可能会有数百的分块，我们设计的交互的模块让用户自定义他们的分块。

6.可信度估计

需要平衡已经知道很好的和数据很少不知道好不好的，因为那也有可能好。
他们不用置信区间，因为和他们的应用不适用。
而且置信计算需要耗费比估计少和便宜。
他们用了一个启发性算法算不确定性得分。
比较大的n_i的特征有更小的学习效率，因为我们相信我们得到的洗漱值是比价准确的。logloss是logistic的loss。如果我们假设特征向量是正则化的那么|x_{t,i}|<=1,我们可以bound这个改变在log-odds预测，原因在我们可以观测一个单个的训练样本(x,y)。
为简单期间考虑\lambda_1=\lambda_2=0,所以FTRL_Proximal和OGD等价。
\[令n_{t,i}=\beta+\sum_{s=1}^{t}{g_{t,i}}^2,再利用FTRL_Proximal的ｗ迭代公式得到：\]
\[\begin{alignat}{1}|x\cdot w_t -x \cdot w_{t+1}|&=\sum_{i:|x_i|>0}{}\eta_{t,i}|g_{t,i}|\\&\leq \sum_{i:|x_i|>0}{}\frac{x_{t,i}}{\sqrt{n_{t,i}}}=\alpha \eta \cdot x \equiv u(x)\end{alignat}\]
这里\eta是学习效率矩阵。我们定义不确定性得分是上界u(x),像计算内积那样做。
实验结果：他们首先训练了一个ground truth模型；没用真实的点击标签，把ground truth模型的CTR当做真的CTR.
他们的不确定性得分和另外的一些expensive的估计方式可相匹敌的。(和一个用了32个模型的引导程序估计相比较的)

7.预测校准
准确和良好校准的预测不光在竞价中是必要的，同时允许了一个宽松的在机器学习机制之外的对整体系统进行一些优化设计。
在不同数据集上观测到，预测得出不同的CTR被叫做系统偏见来自很多地方，比如不准确的模型假设，学习算法的不足，或者隐藏特征在训练或者服务时间不允许。
为强调这点我们用一个校准层去匹配预测的CTR和观测到的CTR.
我们在一个数据块上做校准，如果我们预测到了p,实际观测到的CTR在p附近。我们通过利用纠正函数\tau_d(p)来提升校准,d表示数据块中的一个元素。如果校准的预测能在很大范围内的数据块上起作用，我们就达到目的了。
对\tao进行简单的建模方法比如：
\[\tau(p)=\gamma p^k\]
我们可以利用Possion回归在聚合数据上得到\gamma 和\tau.
更一般的方法是用piecewise分段的线性或者常数纠正方程来处理复杂形状的偏见曲线。仅有的限制是映射方程\tau是需要isotonic单调增加。我们能通过isotonic回归发现这样的映射，通过计算加权的最小二乘法，来拟合输入数据符合那些限制。[27,23]这种分段线性方法相比合理的基准方法显著的减少了预测阶段的不管是范围高端还是范围低端的偏见。
没有很强的假设支撑，校准没什么价值，天然的系统回馈循环不会带来校准有理论保证的影响力的。

8.自动的特征管理

大型机器学习很重要的一个方面是管理很大量的装入，包含所有的配置，开发这，代码，计算资源，来组成一个机器学习系统。一个装入要在诸多团队，建模特定领域的问题都需要日常开支。一个典型的有趣的例子就是机器学习特征空间的管理。
我们可以把特征空间刻画成一个contextual和semantic的信号的能被转换成实值特征来学习的集合。(上下文的语义学的)
在一个大型的装载中，许多开发者在信号开发过程中asynchronously是异步工作的.一个信号可能有很多随着配置变更，提升，和本地实施而产生的版本。一个工程团队或许是在消耗信号如果他们没有直接开发的话。信号或许在多个分开的学习平台上被消耗应用于不同的问题。(比如，预测搜索广告vs预测展示广告)为处理用例的组合增长，我们使用了一个元数据索引来管理数千的信号输入和数百的模型调用交互带来的消耗。
有索引的信号接受手动和自动多层面考虑，比如depreaction,特定平台的可使用性，特定领域的可使用性等等。新模型，活动模型通过一个自动的消息系统进行审核。不同的学习平台使用共同的信号消耗报告接口到中心索引。当一个信号被弃用(比如新版本可用了)我们就迅速的为所有用户一致化信号和进行替代。当一个信号的版本提升了，用户会被通知到去使用新版本。
新信号可以通过自动测试和写白名单的方式来审核。白名单可以被用来保证生产系统的纠正也可以用于学习系统的自动特征选择。不在需要的旧信号会被自动的标记用来做代码删除，以及其他相关的数据。
有效的信号消耗管理保证了更多的学习在一开始就是正确的。这样就减少了减少了浪费和重复的工程努力，节省了很多工程时间。在运行学习算法之前为了正确性验证配置消除了不可用模型，可能的资源浪费这样的情况。

9.失败的实验

最后一部分，我们简单的报告一些不会带来显著回报的探索方向。

9.1Aggressive Feature Hashing

近几年有很多围绕特征hashing化来减少大型学习系统的RAM。值得一提，[31]报告了一个用哈希技巧组织一个特征空间使得学习ｄｆｗｅｇ／／／／／／／
他们用了这种方法但是发现他们不能。这种方法没有令他们得到节省，他们更喜欢用interpretable的可判断的，可分析的特征向量来代替。

9.2 Dropout

他们尝试了随机丢弃的技术[17]。主要思想是从输入样本向量中以概率p随机丢弃特征,通过概率因子(1-p)缩放结果的权重来对这个做补偿。这被看做一种在可能的特征子集上仿真打包的正则化。
我们试过从0.1到0.5的丢弃率，每个伴随学习率设定，包括改变通过数据的数量。在所有情况下，我们发现丢弃训练不会对预测的准确性或者一般化能力，提供好处，通常只会提供损害。【This is obviious,jinmei said】
我们＋＋＋／／／

9.3特征打包

另一个我们有投入的和dropout一起的训练变量是特征打包，在k个训练模型在ｋ个overlapping的子集上的特征空间上训练。
最后的结果取每个模型预测结果做平均，这中方法在数据挖掘社区被广泛的使用，最值得一提的是决策树[9],提供了一种权衡偏差的方法。我们对这个感兴趣还因为它提供了可能的将来平行化训练的有用方法。然而，我们发现特征打包实际上轻轻地降低了预测的质量，根据打包scheme,AcuLoss在0.1%~0.6%之间。

9.4特征向量正规化

我们的模型中每事件的非零特征变的特别厉害，导致含有不同量级的特征抽样。我们担心这样的变化可能回减缓收敛速度并且影响预测的准确性。我们探索了几个例子通过训练x/|x|,目标就是减少数量及交叉的样本向量中方差。尽管一些早期的结果显示一些小的精确性的增加但是我们不能把这些搬运到整体的positive 度量中。实际上我们的实验看起来有些detrimental是有害的,可能是因为和per-coordinate 学习效率和正则化的交叉的缘故。
【完】

1.为什么LogLoss的表达式是那样的？
2.FTRL_Proxical  算法的特征迭代方式是什么意思？
3.Learning Rate是做什么的？为什么它是那样定义的？
4.正则化是什么意思？L_1正则化是复变函数中的内容吗？
5.Per-coordinate中的\alpha和\beta是什么意思？
6.这里面的baseline是什么意思？
7.没有明白Bloom Filter为什么其实是概率的？
8.学习效率定义中的t指的是学习的时间，还是学习到一些东西的时间？
9.特征的迭代自然而然的适应了线上学习的特点，迭代的时间间隔是怎么确定的？
10.z迭代的方式是怎么确定的？
11.特征迭代中的\lambda是什么意思？
12.ODG是怎么做的？
13.hash是什么意思？
14.\eta_{t,i}的Learning Rate是怎么算出来的？
15.如何理解第二页的算法１？
16.\sigma函数起到什么作用？
17.AucLoss和LogLoss的图说明了什么？
18.做二次抽样起到什么作用？
19.用了什么方式评估模型？
20.The online Loss 到底是什么意思？
21.用相对度量而不是绝对度量做到了什么？绝对度量的误导性体现在哪里？
22.图3不确定性得分描述了什么？
23.可信度估计针对的是什么？
24.为什么他们不用置信区间？
25.IID数据是什么？
26.不确定性得分是怎么做的？它在统计角度的合理性是怎样的？
27.他们是如何确定他们的不确定性得分工作的很好的？
28.造成那几个常用模型之间差异的本质是什么？
29.Sampled new labels是什么意思？
30.不确定性得分的upper bound不等式是怎么得到的？
31.log-odds是什么意思？
32.可信度估计的实验是怎么做的？
33.通过反函数的方法求解出误差ｅ在可信度估计里面是起了什么作用呢？
34.为什么需要做预测校准？
35.Systematic bias是什么？
36.为什么要纠正函数是单调增加的或者isotonic的？
37.分段校准怎么样同时减少both the high and low ends 的偏见？
38.会有哪些很强的假设帮助我们做校准？
39.Google的特征管理系统还帮助特定的机器学习算法选择特征吗？
40.特征的哈希化是怎么帮助节省RAM的？
41.Overlapping是什么意思？
42.这类机器学习算法的数据量适应性能上面怎么样？
43.那些是通过算法的方式解决了省和准的问题的？
44.为什么随机引入稀疏特征的方式会是有效果的而随机丢弃的方式确是带来麻烦的？
45.一般的机器学习方法都有类似Google分Serving和Trainning的阶段吗？
46.ROC是什么？
47.随机取整数的方法都损失了什么？
48.FTRL_Proximal算法怎么做到又省有精准的？
49.我们是如何描述精准的？
50.学习效率和精准和节省之间的关系是什么？
51.在算法的那几个地方做到了省？
52.这篇论文什么地方不可以借鉴？
53.RDA是什么？
54.FOBOS是什么？
55.随机无偏取整是如何构造的？
56.为什么要存储梯度的和？
57.单值结构起到了什么作用？
58.g_t是什么？
59.为什么g_t会和学习效率有关系？
60.正则化L_1和\lambda_1是相互对应的吗？
61.算法中的\lambda_2起什么作用？
62.梯度下降的时候下降的是什么的梯度？
63.sigmoid函数的作用是什么来着？
64.g_t,y_t中的ｔ表示怎样的时间？是不是迭代次数？
65.w_t到底表示特征向量还是权重？是什么的权重或者什么的特征向量？
66.z_i表示什么？
67.i表示什么？
68.算法的迭代结构是怎样的？
69.其他的几个对比算法的算法结构你能够写出来吗？
70.per-coordinate的迭代是怎么算出来的？
71.L_1和L_2分别指的是算法的哪一部分？
72.逻辑回归和FTRL_Proximal是什么关系？
73.Sparsification指的是什么？
74.如果Sparsification是按照字面意思理解的化，那就解释不通了，本来就是稀疏的矩阵不好处理，为什么还要稀疏化？
75.g_i的平方表示什么意思？
76.z_i是负数表示什么意思？
77.logistic loss为什么是那么定义的？
78.logistic loss的梯度是怎么算出来的？
79.文章在比较什么算法？
80.比较的算法中都用到梯度下降了吗？它们之间的不同就在于使用计算资源的不同吗？
81.他们的基础知识有哪些？
82.n_i表示什么？
83.怎样做per-coordinate?
84.学习效率以怎样的方式放进模型的？
85.X_t 表示什么？
86.哪里体现出线性模型了？
87.为什么要计算特征系数的loss?
88.预测为什么会导致loss?
89.到底是per-coordinate的好，还是非per-coordinate的好？
90.正规化怎么体现在算法中的？
91.逻辑回归和FTRL_Proximal之间的关系是什么？
92.为什么系数是根据loss函数的梯度算出来的？
93.逻辑回归是什么？
94.范数符号的上下角标都是什么意思？
95.算法的执行阶段在整个系统流程的哪一个还是几个部分？
96.算法最后达到什么条件就算收敛了？
97.逻辑回归和per-coordinate有什么关系？
98.为什么要做per-coordinate?做per-coordinate有什么好处？
99.OGD和FTRL_Proximal在算法上的差别是什么？
100.OGD和FTRL_Proximal在实现存储上的差别是什么？
101.Z的符号函数有什么含义？
102.文章的结构是怎样的？
103.应该阐述的重点在哪里？
104.为什么把log似然函数叫做logloss？
105.为什么logloss函数里面不写w而是w_t？
106.到底哪个才是要估计的参数？
107.控制梯度和的\lambda是怎么取的？
108.算法中g_i和g_t一样吗？
109.g_{t,i}是一个值吗？
110.t到底在循环什么？现在能确定i是从1到d的向量中的点。
111.w_{t,i}在sigmoid函数中的什么位置？
112.g_t,w_t,x_t都是同一规格的吗？
113.对于批量逻辑回归下的梯度下降参数迭代方式和恩达讲的一般的梯度下降迭代有什么不同？
114.为什么不直接对最大似然函数做梯度上升呢？
115.要不要展示这个算法过程？
116.用什么方式展示FTRL_Proximal这个算法过程？
117.如何写大家都看得懂的伪代码？
118.有哪几个观看这篇论文的不同视角？
119.训练一批逻辑回归模型的原因是什么？
120.\sigma作为函数是怎么更新的？
121.FTRL_Proximal名字的含义怎么理解？
122.ODG存储了ｗ而FTRL_Proximal存储了ｚ这有什么不同？
123.ｗ的迭代来自对一个方程最小值的求取，这个方程代表什么含义？
124.所有变量的迭代初始值都是怎么确定的？
125.sparsification阶段做了什么事情？
126.参数\lambda_1有符号规定吗？
127.ｔ的循环怎么样改变了每一个coordinate的参数？
128.超过\lambda之后每一个coordinate的参数是怎么赋值的？
129.如何利用学习效率给每一个coordinate的参数赋值的？
130.为什么要依据学习效率乘以负１来给每个coordinate的参数赋值？
131.为什么学习效率表示成梯度和开方的倒数？而学习效率基本的定义确是时间开方的倒数。
132.所有coordinate的梯度和满足什么条件？
133.梯度是什么？
134.梯度怎么和sigmoid函数联系起来了？
135.y_t是向量还是值？
136.为什么预测值用sigmoid函数表示的？
137.OGD直接用梯度下降迭代参数，但是FTRL不是这样的，FTRL是怎样的？
138.\sigma累计达到学习效率的倒数是为什么？
139.FTRL迭代的重写是怎么做到的？
140.OGD中是如何看待一批量的问题的？
141.累计梯度和系数的内积是什么意思？
142.FTRL的迭代中用到最小二乘法了吗？
143.范数是如何计算的？
144.轮数和梯度和之间有什么可比拟之处？
145.为什么文章中的梯度定义是预测值和实际值之间的差额和特征的内积？
146.它和纯粹的梯度下降是不同的，但是是什么保证了这样子做是正确的？
147.学习效率只要满足随着迭代的轮数递减就可以了吗？
148.为什么要用梯度和来定义学习效率?
149.如何将一个综合的计算流程转化为对于编程语言而言清晰可见数据结构？
150.在解w的迭代时候如何解出per-coordinate的迭代方式？或者说参数向量的迭代方式怎么觉得参数单位元的迭代的？
151.那个目标函数是用几次才解出来的，还是一次就是形式的表达出来了？
152.那个迭代函数怎样实现文章的目标的？
153.迭代算法最后输出了什么？怎么看不出来最后迭代完了得到了什么？
154.为什么梯度下降的方式里面没有以一个参数为基准进行逐步减少？
155.如果没有进行梯度的下降那他怎么达到让可能性质最大这样的一个目的？
156.难道为了某种目的可以让那个可能性不达到最大吗？
157.或者是这种流程的目的是什么竟然不知道了，那么这个核心流程它的目的是什么？
158.有哪些很值得注意的挑战呢？
159.特征来自哪里的数据？
160.SGD是什么？
161.在服务阶段的稀疏化和在训练阶段的稀疏化有什么不同？
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.172.173.174.175.176.177.178.179.180