受 Free Mind 的影响按这种形式写年度总结

年初的时候看到一句话：「 2019 是过去十年中最差的一年，也是未来十年中最好的一年」。和其他人一样，我害怕不确定性，不过生活除了鼓起勇气前进，还有什么其他选择。

工作

完整在滴滴工作一年，自己没有太多变化，可是环境却变了很多。从年初内部会议上 Will 优化员工开始，很多同事陆续离开，从而我都快要成为团队元老……

做为食物链低端的算法工程师，工作中杂七杂八的事情干了很多。洗数据、跑模型、改工程代码、测试、上线、实验各个方面都干过。

说回来，算法还是自己的主要工具。今年用的最多的是 FM 和 GBDT，这些都是几年前的技术，但是架不住效果好，性能要求小。自己也写了一些相关的文章，可以供大家参考。

(FM) Factorization Machines | 算法花园

(FTRL) Follow The Regularized Leader | 算法花园

All About GBDT (1) | 算法花园

Practical Lessons from Predicting Clicks on Ads at Facebook(gbdt + lr) | 算法花园

关于深度学习，在我入职前模型就基本迭代完成，今年主要探索个性化场景的解决以及模型性能优化。很遗憾，这两方面的工作目前还没有什么可以写成博客分享的。最后，自己没有参与到组内强化学习的项目中，不过还是通过李宏毅老师的相关课程了解初步的概念，争取 20 年内做一些相关的事情。

9月份开始，leader突然让我准备一些编程题目，开始去面试实习生。通过牛客网以及北邮人论坛大概收到简历60多份，我面试10多个候选人，最终通过的大概五六人，不过过来实习的也就 2 个。印证自己之前的想法，一家已经不是快速发展的公司，很难招到即懂机器学习又会做编程题的实习生。

另外想写的一点是是匿名交流。内部论坛之前有一个匿名区，后来由于一件比较有名的事情，匿名喷得太厉害，被某位海归高管以提高交流效率减少戾气所关闭（目前这位已经离职，有人开玩笑期待干掉他新公司的匿名论坛）。所幸脉脉还有职言（匿名）以及公司圈。在上面混了一年之后，越来越理解匿名交流的必要，说事。比如今年发生的延迟发年终奖，快手可以直接在内部匿名区引起宿华回复。我们的公司圈一堆人才自嗨。本质是国内环境下很难公开交流一些话题。

之前看过[一篇文章]中介绍 Google 的 TGIF：

TGIF是Larry和Sergey在公司早期就创立的，一个全公司范围的周会。在这个周会上高管们会透露公司新项目的进展，也安排有答疑环节，员工可以询问两位创始人任何问题。TGIF毫无疑问是为了提高公司内部的透明度，但它在增强员工凝聚力的同时也对公司文化提出了挑战，最直接的就是保密问题。比如Chrome项目在公司内部的公开就是在一次TGIF上发生的，那时离Chrome的正式对外宣布早了一年多的时间。

阅读

今年读过 33 本书，阅读量和前几年基本持平。年底发现自己的一个坏习惯：很多书读了一半就放在那里，导致开的坑很多。应对方法也很简单：一段时间内只读一本书。而且为了提高阅读的质量，将自己读完一本书的定义从读到最后一页改成完成对这本书内容的整理。

阅读的主要工具是 kindle 和微信阅读（iPhone）。kindle 是这么多年一直使用的阅读介质，从前几年的找破解图书到现在的完全中亚购买（以目前看书的频率还不至于承受不住），长时间看电子水墨屏能减轻一些疲劳。微信阅读的特点是白领无限卡后就能全场免费读，实在是太香了。理想状态下用这两个工具读不类型的材料，微信阅读读小说以及人物传记，kindle 看需要大量抄记的书。对于需要反复阅读的内容，实体书则是最佳的选择。

分享读完觉得不错的几本书：

1. 经济学通识/薛兆丰经济学讲义：薛兆丰目前看起来风评不是很好，这两本也不是什么严肃的经济学读物。前一本书是作者专栏文章的合集，后一本是得到专栏的文字版，两本书大量的内容是重复的。书中通过现实中的例子来讲解背后的经济学原理，很适合看完之后做为饭后谈资。反正我运用书中的一些原理，给同事分析好久公司的停车场应该怎么分配车位。
2. 银河帝国：这一套书有很多本，只看完前三本。概括起来，这本小说是以太空为背景讲政治故事，以谢顿的预言为主线，讲述基地对抗各种危机的挑战。另外书中提到看起来有多少分像统计学的心理史学，谢顿一直用这种方法预测未来，而且信徒们一直强调，预测结果不会因为个人而改变。第三本书，围绕寻找第二基地展开，把所有读者能猜的地方都写了出来，选择了一种情理之中，意料之外的结局。
3. 人类简史/未来简史：尤瓦尔·赫拉利是前几年很火的一个历史学家。人类简史主要是按他的框架回顾从原始人类到现代人类的文明发展历程。对于我这种没有系统接受过历史学教育的人，完全是一种震撼。未来简史讨论的是人类未来的发展方向，成神。
4. 房思琪的初戀樂園：讲述一个小女孩被文明所不齿的方式杀死的故事，最让人痛心的这女孩就是作者本人……引用最近很流行的一句话：地狱空荡荡，魔鬼在人间。
5. 基督山伯爵：看完《了不起的盖茨比》后，老板强力推荐的爽文小说。快意恩仇，永远不要丧失对生活的期望。
6. 临高启明：工科党神书，死于历史空无主义，最后放上来缅怀一下。

2020 年开始使用 Notion 记录读书过程，点击 看书也就图一乐 查看。

观影

和去年一样，看电影比起看书来更加容易，豆瓣上轻松标记 60 部。想想原因，打开一个视频放在那里，不用怎么理它就能结束。按类别推荐一下自己觉得不错的影视：

1. 小丑/蝙蝠侠三部曲：去年在观影中大力推荐漫威宇宙，今年看完 DC 这 4 部电影，刷新对超级英雄片的认知。蝙蝠侠：黑暗骑士在是在超级英雄的框架下对人性进行探讨。小丑展示出社会如何逼一个人成为恶魔。
2. 黑客帝国三部曲：经典的电影，赛博朋克风格。之前的神话描述神创造了世界，在这部片子里面，这个神就变成了机器人。多少算是人工智能行业的从业者，强人工智能离我们看起来还是很远。
3. 人生七年9：这应该是拍摄时间最慢长的纪录片，也给我们机会在几十个小时时间里面见证这些主人公 60 多年岁月。很大一个感受，除了 Nick 之外，其他人不过是重复父辈的道路，阶级跃迁又是谈何容易。
4. 哪吒之魔童降世：即大鱼海棠之后，第二部在电影院看的动画电影。之前想过一个问题：为什么一些小说要隔一段时间就翻拍一次？简单的认为要赋予时代主题。这部片子中最喜欢的一个设定：龙族也是妖怪，镇守龙宫，其实也是镇住自己。
5. 邪不压正：电影看到一半的时候，我就觉得自己看不懂。说回来，看这部电影有一种酣畅淋漓的感觉，节奏很快，比《一步之遥》和《让子弹飞》更快。半夜在知乎上看了很多回答之后渐渐地懂得其中的情节，蓝先生的爱国情怀，李的复仇梦想。在历史的框架下演绎，始终无法逃离历史的结果，日本人还会按照发展进入北京城。一句“异父异母的亲兄弟”就值得一看。

游戏

今年新增的一个板块，自从购入 Switch 之后，开始重新接触一些游戏。

1. 隐形守护者：抗战背景下面，一个特工面对选择的游戏。所有的场景都是真实拍摄出来的，比绝大部分国内的抗战剧精美。游戏有很多个结局，当然只有符合社会主义核心价值观的才算善终。最印象深刻是第二号突然的一句：什么都是马尔可夫链。
2. 有氧拳击/健身环大冒险：NS 上的铁人三项之二，充分发挥体感的优势，晚上下班之后健身用。不过从目前的使用频率来看，大概率和买健身卡一个性质。
3. 塞尔达传说：旷野之息：决定买 Switch 很大程度上源于少数派中一篇关于这个游戏的介绍，大意是没有传统的等级增长，只有你真正掌握一个技巧，林克才能使用出来。这款游戏的给我带来看似无限大的空间，但也有一点遗憾，有时候遇到下雨不好攀岩时，我想让林克坐下等雨停，然后发现没有坐下的选项……
4. 超级马力欧创作家2：大学的时候，经常看超级小桀玩这个游戏。对于我这种连普通的马里奥都要靠无敌才能通关的来说，大部分自制的地图还是有点难的。说回来，买这个游戏就是买一个青春。只可惜物是人非。
5. 暗黑破坏神3：永恒之战版 ：Switch 上的冷饭，自己瞎玩了很久，看完所有的剧情。最终在咸鱼上买了很多强力的装备后，速通 150 层大秘境后索然无味。所以玩游戏还是不要作弊。

未来

世界变化太快，未来可期。

于浙江临海

2017 迷茫 >> 2018 探索

GBDT(Gradient Boosting Decision Tree) 从名字上理解包含三个部分：提升、梯度和树。它最早由 Freidman 在 greedy function approximation ：a gradient boosting machine 中提出。很多公司线上模型是基于 GBDT+FM 开发的，我们 Leader 甚至认为 GBDT 是传统的机器学习集大成者。断断续续使用 GBDT 一年多后，大胆写一篇有关的文章和大家分享。

朴素的想法

假设有一个游戏：给定数据集 ${(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$，寻找一个模型${\hat y=F(x_i)}$，使得平方损失函数 ${\sum \frac{1}{2}(\hat y_i - y_i)^2}$ 最小。

如果你的朋友提供一个可以使用但是不完美的模型，比如

$$F(x_1)=0.8,y_1=0.9$$

$$F(x_2)=1.4,y_2=1.3$$

在如何不修改这个模型的参数情况下，提高模型效果？

一个简单的思路是：重新训练一个模型实现

$$F(x_1)+h(x_1)=y_1$$

$$F(x_2)+h(x_2)=y_2$$

$$...$$

$$F(x_n)+h(x_n)=y_n$$

换一个角度是用模型学习数据 ${(x_1,y_1-F(x_1)),(x_2,y_2-F(x_2)),...,(x_n,y_n-F(x_n))}$。得到新的模型 ${\hat y=F(x_i)+h(x_i)}$。

其中 ${y_i-F(x_i)}$ 的部分被我们称之为残差，即之前的模型没有学习到的部分。重新训练模型 ${h(x)}$正是学习残差。如果多次执行上面的步骤，可以将流程描述成：

$${F_0(x)}$$

$${F_1(x)=F_0(x)+h_1(x)}$$

$${F_2(x)=F_1(x)+h_2(x)}$$

$${...}$$

$${F_t(x)=F_t-1(x)+h_t(x)}$$

即 ${F(x;w)=\sum^T_{t=1}h_t(x;w)}$，这也就是 GBDT 。

如何理解 Gradient Boosting Decision Tree ?

Gradient Boosting Decision Tree 简称 GBDT，最早由 Friedman 在论文《Greedy function approximation: a gradient boosting machine》中提出。简单从题目中理解包含三个部分内容：Gradient Descent、Boosting、Decision Tree。

Decision Tree 即决策树，利用超平面对特征空间划分来预测和分类，根据处理的任务不同分成两种：分类树和回归树。在 GBDT 算法中，用到的是 CART 即分类回归树。用数学语言来描述为 ${F=\{f(x)=w_{q(x)}\}}$，完成样本 ${x}$ 到决策树叶子节点 ${q(x)}$ 的映射，并将该叶子节点的权重 ${w_{q(x)}}$ 赋给样本。CART 中每次通过计算 gain 值贪心来进行二分裂。

Boosting 是一种常用的集成学习方法（另外一种是 Bagging）。利用弱学习算法，反复学习，得到一系列弱分类器（留一个问题，为什么不用线性回归做为弱分类器）。然后组合这些弱分类器，构成一个强分类器。上面提到的模型 ${F(x;w)=\sum^T_{t=1}h_t(x)}$ 即是一种 boosting 思路，依次训练多个 CART 树 ${h_i}$，并通过累加这些树得到一个强分类器 ${F(x;w)}$。

为什么 GBDT 可行？

在 2 中我提到 GBDT 包括三个部分并且讲述了 Boosting 和 Decison Tree。唯独没有提到 Gradient Descent，GBDT 的理论依据却恰恰和它相关。

回忆一下，Gradient Descent 是一种常用的最小化损失函数 ${L(\theta)}$ 的迭代方法。

• 给定初始值 ${\theta_0}$
• 迭代公式：${\theta ^t = \theta ^{t-1} + \Delta \theta}$
• 将 ${L(\theta ^t)}$ 在 ${\theta ^{t-1}}$ 处进行一阶泰勒展开：${L(\theta ^t)=L(\theta ^{t-1} + \Delta \theta) \approx L(\theta ^{t-1}) + L^\prime(\theta ^{t-1})\Delta \theta}$
• 要使 ${L(\theta ^t) < L(\theta ^{t-1}) }$，取 ${\Delta \theta = -\alpha L^\prime(\theta ^{t-1})}$
• 其中 ${\alpha}$ 是步长，可以通过 line search 确定，但一般直接赋一个很小的数。

在 1 中提到的问题中，损失函数是 MSE ${L(y, F(x))=\frac{1}{2}(y_i - f(x_i))^2}$。

我们的任务是通过调整 ${F(x_1), F(x_2), ..., F(x_n)}$ 最小化 ${J=\sum_i L(y_i, F(x_i))}$。

如果将 ${F(x_i)}$ 当成是参数，并对损失函数求导得到 ${ \frac{\partial J}{\partial F(x_i)} = \frac{\partial \sum_i L(y_i, F(x_i))}{\partial F(x_i)} = \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} = F(x_i)-y_i}$。

可以发现，在 1 中提到的模型 ${h(x)}$ 学习的残差 ${y_i-F(x_i)}$正好等于负梯度，即 ${y_i-F(x_i)=-\frac{\partial J}{\partial F(x_i)}}$。

所以，参数的梯度下降和函数的梯度下降原理上是一致的：

• ${F_{t+1}(x_i)=F_t(x_i)+h(x_i)=F(x_i)+y_i-F(x_i)=F_t(x_i)-1\frac{\partial J}{\partial F(x_i)}}$
• ${\theta ^t = \theta ^{t-1} + \alpha L^\prime(\theta ^{t-1})}$

GBDT 算法流程

模型 F 定义为加法模型：

$${F(x;w)=\sum^{M}_{m=1} \alpha_m h_m(x;w_m) = \sum^{M}_{m=1}f_t(x;w_t)}$$

其中，x 为输入样本，h 为分类回归树，w 是分类回归树的参数，${\alpha}$ 是每棵树的权重。

通过最小化损失函数求解最优模型：${F^* = argmin_F \sum^N_{i=1}L(y_i, F(x_i))}$

输入: ${(x_i,y_i),T,L}$

1. 初始化：${f_0(x)}$
2. 对于 ${t = 1 to T}$ ：
   1. 计算负梯度（伪残差）： ${ \tilde{y_i} = -[\frac{\partial L(y_i, F(x_i))}{\partial F(x)}]_{F(x)=F_{m-1}(x)} ,i=1,2,...,N}$
   2. 根据 ${\tilde{y_i}}$ 学习第 m 棵树： ${w^*=argmin_{w} \sum_{i=1}^N(\tilde{y_i} - h_t(x_i;w))^2}$
   3. line searcher 找步长：${\rho^* = argmin_\rho \sum_{i=1}^{N}L(y_i, F_{t-1}(x_i)+\rho h_t(x_i;w^*))}$
   4. 令 ${f_t=\rho^*h_t(x;w*)}$，更新模型：${F_t=F_{t-1}+f_t}$
3. 输出 ${F_T}$

说明：

1. 初始化 ${f_0}$ 方法
   1. 求解损失函数最小
   2. 随机初始化
   3. 训练样本的充分统计量
2. 每一轮拟合负梯度，而不是拟合残差，是为方便之后扩展到其他损失函数。
3. 最小化问题中，如果有解析解，直接带入。否则，利用泰勒二阶展开，Newton Step 得到近似解。

这一篇就先到这里，之后还会分享 GBDT 常用损失函数推导以及 XGboost 相关内容。如果有任何想法，都可以在留言区和我交流。

Reference

1. 李航, 《统计学习方法》8.4 提升树
2. Freidman，greedy function approximation ：a gradient boosting machine
3. 【19年ML思考笔记】GBDT碎碎念（1）谈回归树的分裂准则 - 知乎
4. 机器学习-一文理解GBDT的原理-20171001 - 知乎
5. GBDT入门详解 - Scorpio.Lu|Blog
6. python - Why Gradient Boosting not working in Linear Regression? - Stack Overflow
7. GBDT基本原理及算法描述 - Y学习使我快乐V的博客 - CSDN博客
8. GBDT的那些事儿 - 知乎

FTRL 是 Google 提出的一种优化算法。常规的优化方法例如梯度下降、牛顿法等属于批处理算法，每次更新需要对 batch 内的训练样本重新训练一遍。在线学习场景下，我们希望模型迭代速度越快越好。例如用户发生一次点击行为后，模型就能快速进行调整。FTRL 在这个场景中能求解出稀疏化的模型。

基础知识

• L1 正则比 L2 正则可以产生更稀疏的解。
• 次梯度：对于 L1 正则在 $x=0$ 处不可导的情况，使用次梯度下降来解决。次梯度对应一个集合 $\{v: v(x-x_t) \le f(x)-f(x_t)\}$，集合中的任意一个元素都能被当成次梯度。以 L1 正则为例，非零处梯度是 1 或 -1，所以 $x=0$ 处的次梯度可以取 $[-1, 1]$ 之内任意一个值。

FTL

FTL(Follow The Leader) 算法：每次找到让之前所有损失函数之和最小的参数。

$$W=argmin_W \sum^t_{i=1}F_i(W)$$

FTRL 中的 R 是 Regularized，可以很容易猜出来在 FTL 的基础上加正则项。

$$W=argmin_W \sum^t_{i=1}F_i(W) + R(W)$$

代理函数

FTRL 的损失函数直接很难求解，一般需要引入一个代理损失函数 $h(w)$。代理损失函数常选择比较容易求解析解以及求出来的解和优化原函数得到的解差距不能太大。

我们通过两个解之间的距离 Regret 来衡量效果：

$$\begin{array}{c}{w_{t}=\operatorname{argmin}_{w} h_{t-1}(w)} \\ {\text {Regret}_{t}=\sum_{t=1}^{T} f_{t}\left(w_{t}\right)-\sum_{t=1}^{T} f_{t}\left(w^{*}\right)}\end{array}$$

其中 $w^{*}$ 是直接优化 FTRL 算法得到的参数。当距离满足 $\lim _{t \rightarrow \infty} \frac{\text {Regret}_{t}}{t}=0$，损失函数认为是有效的。其物理意义是，随着训练样本的增加，两个优化目标优化出来的参数效果越接近。

推导过程

参数 $w_{t+1}$ 的迭代公式：

$${w_{t+1}=argmin_w\{ g_{(1:t)}w + \frac{1}{2} \sum_{s=1}^t \sigma_s \lVert w - w_s \rVert ^2 + \lambda_1 \lVert W \rVert_1 + \frac{1}{2} \lambda_2 \lVert W \rVert^2 \}}$$

其中 $g_{(1:t)}=\sum^{t}_{s=1}g_s$，$g_s$ 为 $f(w_s)$ 的次梯度。参数 $\sum^t_{s=1}\sigma_s=\frac{1}{\eta _t}$，学习率 $\eta _t = \frac{1}{\sqrt{t}}$，随着迭代轮数增加而减少。

展开迭代公式

$${F(w)= g_{(1:t)}w + \frac{1}{2} \sum_{s=1}^t \sigma_s \lVert w - w_s \rVert ^2 + \lambda_1 \lVert W \rVert_1 + \frac{1}{2} \lambda_2 \lVert W \rVert^2 }$$

$${F(w)= g_{(1:t)}w + \frac{1}{2} \sum_{s=1}^t \sigma_s ( w^Tw - 2w^Tw_s + w_s^Tw_s) + \lambda_1 \lVert W \rVert_1 + \frac{1}{2} \lambda_2 \lVert W \rVert^2 }$$

$${F(w)= (g_{(1:t)} - \sum_{s=1}^t \sigma_s w_s)w + \frac{1}{2} (\sum_{s=1}^t \sigma_s + \lambda_2) w^Tw + \lambda_1 \lVert W \rVert_1 + const }$$

$${F(w)= z_t^Tw + \frac{1}{2} (\frac{1}{\eta _t} + \lambda_2) w^Tw + \lambda_1 \lVert W \rVert_1 + const }$$

其中 ${z_{t-1}=g^{(1:t-1)} - \sum_{s=1}^{t-1} \sigma_s w_s}$。

对 $F(w)$ 求偏导得到：

$${z_t + (\frac{1}{\eta _t} + \lambda_2) w + \lambda_1 \partial \lvert W \rvert = 0}$$

$w$ 和 $z$ 异号时，等式成立。

根据基础知识里面提到的对于 L1 正则利用偏导数代替无法求解的情况，得到：

$$\partial|W|=\left\{\begin{array}{ll}{0,} & {\text { if }-1<w<1} \\ {1,} & {\text { if } w>1} \\ {-1,} & {\text { if } w<-1}\end{array}\right.$$

1. 当 ${ z_t > \lambda_1}$ 时，${w_i < 0}$ , ${w_i = \frac{- z_t + \lambda_1 }{\frac{1}{\eta _t} + \lambda_2 }}$
2. 当 ${ z_t < - \lambda_1}$ 时，${w_i > 0}$ , ${w_i = \frac{- z_t - \lambda_1 }{\frac{1}{\eta _t} + \lambda_2 }}$
3. 当 ${ \lvert z_t \rvert < \lambda_1}$ 时，当且仅当 ${w_i=0}$ 成立

因此可得：

$$w_{i}=\left\{\begin{array}{ll}{0,} & {\text { if }\left|z_{i}\right| \leq \lambda_{1}} \\ {\frac{-\left(z_{i}-\text sgn(z_i) \lambda_{1}\right)}{\eta_{t}+\lambda_{2}},} & {\text { if others }}\end{array}\right.$$

FTRL 和 SGD 的关系

将 SGD 的迭代公式写成：${W^{t+1}=W^t - \eta _tg_t}$

FTRL 迭代公式为：${W^{t+1}=argmin_w\{ G^{(1:t)}W + \lambda_1 \lVert W \rVert_1 +\lambda_2 \frac{1}{2} \lVert W \rVert \}}$

代入 ${\sum^t_{s=1}\sigma _s= \frac{1}{\eta _t}}$ 到上面的公式中，得到 ${W^{t+1}=argmin_w\{ \sum_t^{s=1}g_sW + \frac{1}{2} \sum^t_{s=1}\sigma _s\lVert W - W_s \rVert_2^2 \}}$

求偏导得到 ${\frac{\partial f(w)}{\partial w} = \sum^t_{s=1}g_s + \sum^t_{s=1}\sigma _s( W - W_s )}$

令偏导等于 0 ：${\sum^t_{s=1}g_s + \sum^t_{s=1}\sigma _s( W^{t+1} - W_s ) = 0}$

化简得到：${(\sum^t_{s=1}\sigma _s) W^{t+1} = \sum^t_{s=1}\sigma _s W^{s} - \sum^t_{s=1}g_s}$

代入 $\sigma$：${\frac{1}{\eta _t} W^{t+1} = \sum^t_{s=1}\sigma _s W^{s} - \sum^t_{s=1}g_s}$

根据上一个公式得出上一轮的迭代公式：${\frac{1}{\eta _{t-1}} W^{t} = \sum^{t-1}_{s=1}\sigma _s W^{s} - \sum^{t-1}_{s=1}g_s}$

两式相减：${\frac{1}{\eta _t} W^{t+1} - \frac{1}{\eta _{t-1}} W^{t} = (\frac{1}{\eta _t} - \frac{1}{\eta _{t-1}}) W_t - g_t}$

最终化简得到和 SGD 迭代公式相同的公式：${W_{t+1} = W_t - \eta_t g_t}$

FTRL 工程化伪代码

引用自论文 Ad Click Prediction: a View from the Trenches

下面的伪代码中学习率和前面公式推导时使用的一些不一样： $\eta_{t_{i}}=\frac{\alpha}{\beta+\sqrt{\sum_{s=1}^{t} g_{s_{i}}^{2}}}$。Facebook 在 GBDT + LR 的论文中研究过不同的学习率影响，具体可以参看博文 Practical Lessons from Predicting Clicks on Ads at Facebook(gbdt + lr) | 算法花园。

例：FM 使用 FTRL 优化

FM 是工业界常用的机器学习算法，在之前博文 (FM)Factorization Machines 中有简单的介绍。内部的 FTRL+FM 代码没有开源，所以也不好分析。从 FM+FTRL算法原理以及工程化实现 - 知乎 中找了一张 FTRL+FM 的伪代码图片。

Reference

• Online Learning算法理论与实践 - 美团技术团队
• FTRL公式推导 - 知乎
• 每周一文】Ad Click Prediction: a View from the Trenches(2013)_机器学习,CTR,online_fangqingan_java的专栏-CSDN博客

[TOC]

这里记录过去一个月，我看到、想到值得分享的东西，每周六滚动更新。

0x04 你见过哪些让你目瞪口呆、脑洞大开的骗局？ - SME情报员的回答 - 知乎

推荐其中的吉普赛读心术，当成脑筋急转弯来看。

首先任选一个两位数，在心里默默记住，然后用这个两位数再依次减去它的十位和个位，最后用得数查表，找到对应的怪符号。 比如67,相应的计算就是67-6-7=54， 现在，在表中找到你心中数字经过计算后所对应的符号。

最后的答案都会是

0x03 Deep Neural Networks for YouTube Recommendations #paper #ml

Youtube 几年前的论文，最近拿过来看一下。工业界的论文最大的价值是提到的一些 tick，比如这篇论文中分析到用户对新视频的偏好，引入 example age 代表视频的上传到预测时的时间。再比如，给用户推荐视频时，考虑用户看过这个视频相关频道次数以及这个视频在用户实现中出现的次数。所以，做算法实现需要深入理解自己所处的场景。

推荐知乎上一些关于这篇论文的解读：

• Deep Neural Network for YouTube Recommendation论文精读 - 知乎
• 重读Youtube深度学习推荐系统论文，字字珠玑，惊为神文 - 知乎
• YouTube深度学习推荐系统的十大工程问题 - 知乎
• 揭开YouTube深度推荐系统模型Serving之谜 - 知乎

0x02 Fine-Tune Your Days with the Scientific Method

这个小标题出自 Make Time，翻译成中文是利用科学的方法每天微调你的习惯。

0x01 2020 阅读看板

参考部分网友 Notion 的用法，搭建一个自己的阅读看板 看书也就图一乐。目前挑选出来的书远远超过前两年的阅读量，加油一起读书。

Notion 这种一个数据库 + 可选的 View 很接近我心目中任务管理软件的极限。

0x00 大佬们的年度总结

新的一年开始时，最期待翻看大佬们的年度总结，罗列一些我觉得有总结。

• Growing a Result-Driven Mindset - Yiming Chen：英文总结，Yiming 的博客给我带来学习英语并且用之来表达的动力。
• 2019 总结与 2020 计划 | 小土刀 2.0：从不同角度回顾自己的 2019 年。
• 2019 时光小偷：这位博主每年总结的标题都是一首歌，也是几年前看他的总结才开始尝试写自己的总结。
• 致敬时间的价值：一品十年 - 知乎：和这个主题没有太大的关系，看一下其他人十年的总结，也能很好的指导自己的生活。
• 2019年：下个十年路口，Farewell | Crossairplane的博客：读这篇文章的时候突然想到一点，之后再看年终总结时，留言一句「新年快乐」。
• Create vs. Consume - ends 2019 then starts 2020 - Ziting Li：真诚的思考。
• 我的千书阅读计划 - 意欲蔓延 - Hi!PDA Hi!PDA：fatdragoncat 13 年在 Hi!PDA 上立下愿望，这么多年过去，不知道数量上有没有达到，但是读书的收获已经改变他的生活。难得可贵这篇帖子展示他的变化过程。

Info

课件下载：Hung-yi Lee - Deep Reinforcement Learning

课程视频：DRL Lecture 1: Policy Gradient (Review) - YouTube

• Change Log
  • 20191226: 整理 PPO 相关资料
  • 20191227: 整理 Q-Learning 相关资料
  • 20200906: 拖延半年多没有整理笔记，将剩下的内容整理到单独的笔记中。

我的笔记汇总：

• Policy Gradient、PPO: Proximal Policy Optimization、Q-Learning
• Actor Critic
• Sparse Reward
• Imitation Learning

RL 基础

强化学习基本定义：

• Actor：可以感知环境中的状态，通过执行不同的动作得到反馈的奖励，在此基础上进行学习优化。
• Environment：指除 Actor 之外的所有事务，受 Actor 动作影响而改变其状态，并给 Actor 对应的奖励。
• on-policy 和 off-policy 的区别在于 Actor 和 Environment 交互的策略和它自身在学习的策略是否是同一个。

一些符号：

• State s 是对环境的描述，其状态空间是 S。
• Action a 是 Actore 的行为描述，其动作空间是 A。
• Policy $\pi(a|s)=P[A_t=a|S_t=s]$ 代表在给定环境状态 s 下 动作 a 的分布。
• Reward ${r(s,a,s^{\prime})}$ 在状态 s 下执行动作 a 后，Env 给出的打分。

Policy Gradient

Policy Network 最后输出的是概率。

目标：调整 actor 中神经网络 policy $\pi(\theta)$，得到 $a=\pi(s, \theta)$，最大化 reward。

trajectory $\tau$ 由一系列的状态和动作组成，出现这种组合的概率是 $p_{\theta}(\tau)$ 。

$$\begin{array}{l}{p_{\theta}(\tau)} \\ {\quad=p\left(s_{1}\right) p_{\theta}\left(a_{1} | s_{1}\right) p\left(s_{2} | s_{1}, a_{1}\right) p_{\theta}\left(a_{2} | s_{2}\right) p\left(s_{3} | s_{2}, a_{2}\right) \cdots} \\ {\quad=p\left(s_{1}\right) \prod_{l=1}^{T} p_{\theta}\left(a_{t} | s_{t}\right) p\left(s_{t+1} | s_{t}, a_{t}\right)}\end{array}$$

reward ：根据 s 和 a 计算得分 r，求和得到 R。在围棋等部分任务中，无法获得中间的 r（下完完整的一盘棋后能得到输赢的结果）。

需要计算 R 的期望 $\bar{R}_{\theta}$，形式和 GAN 类似。如果一个动作得到 reward 多，那么就增大这个动作出现的概率。最终达到 agent 所做 policy 的 reward 一直都比较高。

$$\bar{R}_{\theta}=\sum_{\tau} R(\tau) p_{\theta}(\tau)$$

强化学习中，没有 label。需要从环境中采样得到 $\tau$ 和 R，根据下面的公式去优化 agent。相当于去求一个 likelihood。

$\nabla f(x) = f(x) \frac{\nabla f(x)}{f(x)}= f(x) \nabla \log f(x)$ ，这一步中用到对 log 函数进行链式求导。

$$\nabla \bar{R}_{\theta}=\sum_{\tau} R(\tau) \nabla p_{\theta}(\tau)$$

$$\begin{array}{l}{=E_{\left.\tau \sim p_{\theta}(\tau)[R(\tau)] \log p_{\theta}(\tau)\right]} \approx \frac{1}{N} \sum_{n=1}^{N} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(\tau^{n}\right)} \\ {=\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(a_{t}^{n} | s_{t}^{n}\right)}\end{array}$$

参数更新方法：

1. 在环境中进行采样，得到一系列的轨迹和回报。
2. 利用状态求梯度，更新模型。如果 R 为正，增大概率 $p_{\theta}(a_t|s_t)$, 否则减少概率。
3. 重复上面的流程。

PG 的例子

训练 actor 的过程看成是分类任务：输入 state ，输出 action。

最下面公式分别是反向传播梯度计算和 PG 的反向梯度计算，PG 中要乘以整个轨迹的 R。

tip 1： add a baseline

强化学习的优化和样本质量有关，避免采样不充分。Reawrd 函数变成 R-b，代表回报小于 b 的都被我们当成负样本，这样模型能去学习得分更高的动作。b 一般可以使用 R 的均值。

tip 2: assign suitable credit

一场游戏中，不论动作好坏，总会乘上相同的权重 R，这种方法是不合理的，希望每个 action 的权重不同。

1. 引入一个 discount rate，对 t 之后的动作 r 进行降权重。
2. 利用 Advantage Function 评价状态 s 下动作 a 的好坏 critic。

PPO: Proximal Policy Optimization

importance sampling

假设需要估计期望 $E_{x~p[f(x)]}$，x 符合 p 分布，将期望写成积分的形式。由于在 P 分布下面很难采样，把问题转化到已知 q 分布上，得到在 p 分布下计算期望公式。

上面方法得到 p 和 q 期望接近，但是方差可能相差很大，且和 $\frac{p(x)}{q(x)}$ 有关。

原分布的方差：

$$\operatorname{Var}_{x-p}[f(x)]=E_{x-p}\left[f(x)^{2}\right]-\left(E_{x-q}[f(x)]\right)^{2}$$

新分布的方差：

$$\begin{array}{l}{\operatorname{Var}_{x \sim p}[f(x)]=E_{x \sim p}\left[f(x)^{2}\right]-\left(E_{x \sim p}[f(x)]\right)^{2}} \\ {\operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]=E_{x \sim q}\left[\left(f(x) \frac{p(x)}{q(x)}\right)^{2}\right]-\left(E_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]\right)^{2}} \\ {=E_{x \sim p}\left[f(x)^{2} \frac{p(x)}{q(x)}\right]-\left(E_{x \sim p}[f(x)]\right)^{2}}\end{array}$$

在 p 和 q 分布不一致时，且采样不充分时，可能会带来比较大的误差。

从 On-policy 到 Off-policy

on-policy 时，PG 每次参数更新完成后，actor 就改变了，不能使用之前的数据，必须和环境重新互动收集数据。引入 $p_{\theta \prime}$ 进行采样，就能将 PG 转为 off-ploicy。

和之前相比，相当于引入重要性采样，所以也有前一节中提到的重要性采样不足问题。

$$J^{\theta^{\prime}}(\theta)=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} | s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right]$$

PPO/TRPO

为了克服采样的分布与原分布差距过大的不足，PPO 引入 KL 散度进行约束。KL 散度用来衡量两个分布的接近程度。

$$J_{P P O}^{\theta^{\prime}}(\theta)=J^{\theta^{\prime}}(\theta)-\beta K L\left(\theta, \theta^{\prime}\right)$$

TRPO(Trust Region Policy Optimization)，要求 $K L\left(\theta, \theta^{\prime}\right)<\delta$。

$$J_{T R P O}^{\theta^{\prime}}(\theta)=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} | s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right]$$

KL 散度可能比较难计算，在实际中常使用 PPO2。

• A>0，代表当前策虑表现好。需要增大 $\pi( \theta )$，通过 clip 增加一个上限，防止 $\pi( \theta )$ 和旧分布变化太大。
• A<0，代表当前策虑表现差，不限制新旧分布的差异程度，只需要大幅度改变 $\pi( \theta )$。

参考 【点滴】策略梯度之PPO - 知乎

PPO algorithm

系数 $\beta$ 在迭代的过程中需要进行动态调整。引入 $KL_{max} KL_{min}$，KL > KLmax，说明 penalty 没有发挥作用，增大 $\beta$。

Q-Learning

value-base 方法，利用 critic 网络评价 actor 。通过状态价值函数 $V^{\pi}(s)$ 来衡量预期的期望。V 和 pi、s 相关。

1. Monte-Carlo MC: 训练网络使预测的 $V^{\pi}(s_a)$ 和实际完整游戏 reward $G_a$ 接近。
2. Temporal-difference TD: 训练网络尽量满足 $V^{\pi}(s_t)=V^{\pi}(s_{t+1}) + r_t$ 等式，两个状态之间的收益差。

MC: 根据策虑 $\pi$ 进行游戏得到最后的 $G(a)$，最终存在方差大的问题。$\operatorname{Var}[k X]=k^{2} \operatorname{Var}[X]$

TD: r 的方差比较小，$V^{\pi}(s_{t+1})$ 在采样不充分的情况下，可能不准确。

Another Critic

State-action value function $Q^{\pi}(s, a)$：预测在 pi 策略下，pair(s, a) 的值。相当于假设 state 情况下强制采取 action a。

对于非分类的方法：

Q-Learning

1. 初始 actor $\pi$ 与环境互动
2. 学习该 actor 对应的 Q function
3. 找一个比 $\pi$ 好的策虑：$\pi \prime$，满足 $V^{\pi \prime}(s,a) \ge V^{\pi}(s,a)$, $\pi^{\prime}(s)=\arg \max _{a} Q^{\pi}(s, a)$

在给定 state 下，分别代入 action，取函数值最大的 a，作为后面对该 state 时采取的 action。

证明新的策虑存在：

Target NetWork

左右两边的网络相同，如果同时训练比较困难。简单的想法是固定右边的网络进行训练，一定次数后再拷贝左边的网络。

Exploration

Q function 导致 actor 每次都会选择具有更大值的 action，无法准确估计某一些动作，对于收集数据而言是一个弊端。

• Epsilon Greedy
  • 小概率进行损失采样
• Boltzmann Exploration
  • 利用 softmax 计算选取动作的概率，然后进行采样

Replay buffer

采样之后的 $(s_t, a_t, r_t, s_{t+1})$ 保存在一个 buffer 里面（可能是不同策虑下采样得到的)，每次训练从 buffer 中 sample 一个 batch。

结果：训练方法变成 off-policy。减少 RL 重复采样，充分利用数据。

Typical Q-Learning Algorithm

Q-Learning 流程：

Double DQN DDQN

• Q value 容易高估：目标值 $r_t + maxQ(s_{t+1}, a)$ 倾向于选择被高估的 action，导致 target 很大。
• 选动作的 Q’ 和计算 value 的 Q(target network) 不同。Q 中高估 a，Q’ 可能会准确估计 V 值。Q’ 中高估 a ，可能不会被 Q 选中。

Dueling DQN

改 network 架构。V(s) 代表 s 所具有的价值，不同的 action 共享。 A(s,a) advantage function 代表在 s 下执行 a 的价值。最后 $Q(s, a) = A(s, a) + V(s)$。

为了让网络倾向于使用 V（能训练这个网络），得到 A 后，要对 A 做 normalize。

Prioritized Reply

在训练过程中，对于经验 buffer 里面的样本，TD error 比较大的样本有更大的概率被采样，即难训练的数据增大被采样的概率。

Multi-step

综合 MC 和 TD 的优点，训练样本按一定步长 N 进行采样。MC 准确方差大，TD 方差小，估计不准。

Noisy Net

• Noise on Action：在相同状态下，可能会采取不同的动作。
• Noise on Parameters：开始时加入噪声。同一个 episode 内，参数不会改变。相同状态下，动作相同。
  更好探索环境。

Distributional Q-function

Q 是累积收益的期望，实际上在 s 采取 a 时，最终所有得到的 reward 为一个分布 reward distribution。部分时候分布不同，可能期望相同，所以用期望来代替 reward 会损失一些信息。

Distributional Q-function 直接输出分布，均值相同时，采取方差小的方案。这种方法不会产生高估 q 值的情况。

Rainbow

rainbow 是各种策略的混合体。

DDQN 影响不大。

Continuous Actions

action 是一个连续的向量，Q-learning 不是一个很好的方法。

$$a=\arg \max _{a} Q(s, a)$$

1. 从 a 中采样出一批动作，看哪个行动 Q 值最大。
2. 使用 gradient ascent 解决最优化问题。
3. 设计一个网络来化简过程。
   1. $\sum$ 和 $\mu$ 是高斯分布的方差和均值，保证矩阵一定是正定。
   2. 最小化下面的函数，需要最小化 $a - \mu$。

Reference

• 强化学习基础知识 - 知乎

[TOC]

这里记录过去一个月，我看到、想到值得分享的东西，每周六滚动更新。

0x02. Org-mode Workflow

国外一名 CS 学生的 org mode workflow 教程，包括 GTD 和 Zettelkasten 两个主要的部分，分别对应时间管理和知识管理，是一份很好的参考资料。

0x01. HHKB 更新

改めてとなりますが今回新しく登場したHHKBは3機種になります。それぞれの特徴をまとめたものがこちらになります。#HHKBミートアップ pic.twitter.com/GVVxNI6H72

— HHKB OFFICIAL (@PFU_HHKB) December 10, 2019

HHKB 好久之后终于更新了！不过价格也变得更贵……还是很喜欢自己 18 年买的 HHKB BT 版。不过在使用 Emacs 之后，出现没有方向键的烦恼。之前通过映射 Ctrl + HJKL 替代方向键，然后和 Emacs 的一些快捷键冲突……等买一个新的机械键盘。

0x00. My GTD Workflow (2019 ver.) - Yiming Chen #gtd

很少看到国人用英文写的 GTD 相关文章，年初自己也想按 Workflow 这种形式写一篇，不过一直拖到现在都没有完成。

• 对任务设置优先级：A B C
• 如何设置任务优先级，对目标进行分解
  • 每年一月份设定年度目标
  • 每月一号根据年度目标设定月度目标
  • 每周日根据月度目标设定每周目标
  • 每天早上设定当天目标
• 任务安排优先级和截止日期后，可以使用四象限法则。
• 回顾技巧
  • 追求 100% 完成，可以接受 70%。
  • 一个任务多次延迟之后，考虑是否还是重要。
  • 如果任务还是重要，对任务进行拆分。

呼吸不止，折腾不停。记录在过去的一年，自己选择的软件和硬件。去年写指南并不能指南，所以今年直接写成指北。

硬件更新

iPhone XR 和 Apple Watch Series 4

iPhone XR 刚出来的时候，一直被吐槽是大边框。不过随着在电商网站上不断降价，越来越被当成是无边框手机……在忍受不了使用多年 iPhone 6 的卡顿，以及很难脱离 iOS 生态的现实。终于在苏宁上下单 $(Product)^{read}$ 版的 XR。经过半年多的使用，这部手机实用但是不出彩。

购买 Apple Watch Series 4(AW) 理由很简单：在去公司健身房锻炼的时候，希望有一个可以记录运动数据的设备。事实 AW 自带的运动软件很不错，可以满足我的运动记录需求。但是例如 Keep 之类的第三方 App 适配不好。另外，AW 很好扩展 iPhone 和 Mac 的使用，比如可以解锁 Mac、查看 iPhone 上的信息等等。到头来，AW 还只是一块需要一天一充的电子表。

Nintendo Switch

Nintendo Switch(NS) 是任天堂在 2017 年推出的，集掌机和主机于一体的游戏机。买 NS 的理由也很简单，Mac 上游戏太少，我需要一个设备玩游戏。更深层次的来说，感觉自己的反应太慢，想通过玩游戏来锻炼快速决策能力。

简单统计一下，我在 NS 上花费的时间大概有 200 多小时，购入游戏也花费上千元……反应能力不知道有没有上去，但是享受到游戏的快乐。

Nintendo Switch 目前可以选的有 Nintendo Switch、Nintendo Switch 续航版、Nintendo Switch Lite。

Kindle Oasis 2

大概是 5 月末，通过公司内部闲置群出了使用 5 年多的 Kindle PaperWhite 2 后，从淘宝上购入美版 Kindle Oasis 2 。可惜的是，1 个月不到的时间，亚马逊推出 Kindle Oasis 3 ……

和 KPW2 相比，KO2 主要带来一下几个方面的提升：

1. 7寸屏幕，更高的分辨率。看的更多，看的更清晰，更加逼近纸书的感觉。
2. 不对称设计，电池集中在一边，握持比较舒服。
3. 金属机身。前几代 kindle 都是亚马逊祖传的类肤质塑料机身，很容易沾上油脂，这一代采用金属机身，看起来更加富有科技感。毕竟当年小米用上金属边框的时候，都敢去吹一块钢板的艺术之旅。
4. 两个翻页实体按键，按起来比较有安全感。

上面说这么多，kindle 主要功能还是看书。这几年，很多 kindle 电子书分享站都由于版权问题陆续关闭，优质的资源比较难下载。不过，去年自己办信用卡时，领了一年的 Kinle U 会员（今年又领到一年的会员），在中亚上借阅很多本小说。从体验上来说，KU 会员不能实现全场自由借，而且大部分书籍都只是滥竽充数。一对比微信读书会员就是十分实惠，多期待微信读书可以出电子书阅读器吧。

软件实践

18 年开始，着手准备构建自己的数字化系统。19 年在前面的基础上，进行了很多迁移。

信息管理

11 月份看到一句话：input 做的越多，知识管理越差。这个很好形容我之前的状态，在印象笔记中囤积待看的剪藏、OF 里面有很多想写的主题、MWeb 遗留大量没有写完的文章。

年中的时候，想把自己写的一些笔记更好的管理起来。最初想到的是搭建 wiki ，实现知识的网状化连接。不过市面上常用的一些个人 wiki 方案都不是很满意。最终选择 hexo 搭配一个 wiki 主题 Wikitten。另外，后来了解到有一种基于纯文本的知识管理方案：zettelkasten。感兴趣的可以去看一下。

写日记是这么多年以来坚持的一件小事情。之前一直是在笔记本上写，后来慢慢的尝试通过印象笔记来写。2月份，订阅 Day One ，开始尝试迁移到它上面去。作为一个专业的软件，体验真的比之前的方式不知道好多少。Day One 上也有很多数据统计，多少可以拿来得瑟用。另外，自己干的一件事情就是把印象笔记中的日记慢慢转移到 Day one 。写在笔记本上的日记，也被我拍成一张又一张的照片，只不过这个迁移起来比较麻烦。

任务管理

这个问题一直是一个大坑，花费很多时间在多个软件中试来试去。在现在这个时间点，自己开始选择混合使用 OmniFocus 和 Org mode。具体怎么搭配使用，等再坚持几个月再出来分享。不过说回来，任务管理的关键不在于软件，而在于执行。

其他实践

下面这一些今年自己做的选择，都有一个共同的特点：从商业软件到开源项目。很多人选着使用的开源项目的出发点在于害怕商业公司无休止的使用个人隐私数据，而吸引我的主要是自由软件自由开放的精神。

从 MoneyWiz 到 Beancount

MoneyWiz 是在少数派上了解到记账软件，Setapp 中可以免费使用。和国内那些整天搞社区和卖理财的记账软件相比，只是纯粹的一个记账软件。Beancount 是无意中从BYvoid文章中了解的一款纯文本记账软件。最大的优点是扩展性强。在使用过程中，搭配一些简单的脚本，可以实现每月底花一个小时就能把这个月的开销记录明白。

从 1Password 到 KeePass

之前看过一个结论：密码破解的难度主要在于长度而不是复杂度。所以借助密码软件辅助记忆密码是不二之选。1Password 是在去年感恩节活动中获得的长达一年的免费体验。快要到期前，没有选择转向订阅（今年感恩节活动依然是新用户
长度一年的免费使用），反而是选择开源的 KeePass。KeePass 在不同的平台上有多个客户端可以选择，目前我主要用的是 MacPass 和奇密。KeePass 中所有的密码数据都保存在一个文件中，跨平台使用只需要简单同步这个文件。

从搜狗输入法到鼠须管

网上关于搜狗输入法的声讨一直不绝于耳，我也长时间忍受搜狗动不动给你跳出来的斗图功能提示。在花费一番力气，配置鼠须管后，彻底删除搜狗，详见 「Rime 鼠须管」小鹤双拼配置指南 | 算法花园。另外 Mac 上自带的输入法的体验也没有那么差。

博客上和这个主题相关的文章：

• Best of iPhone 2019 软件清单 | 算法花园
• 2018 年消费指南 | 算法花园
• iPhone软件清单 | 算法花园
• Mac软件清单 | 算法花园

去年学习这门做的部分笔记，现在分享出来。
笔记格式有些问题，持续整理中。

• 大量内容参考 mbadry1/CS231n-2017-Summary

Table of contents

• Table of contents
• Course Info
• 01. Introduction to CNN for visual recognition
• 02. Image classification
• 03. Loss function and optimization
• 04. Introduction to Neural network
• 05. Convolutional neural networks (CNNs)
• 06. Training neural networks I
• 07. Training neural networks II
• 09. CNN architectures
• Reference

Course Info

• 主页: http://cs231n.stanford.edu/
• 视频：斯坦福深度学习课程CS231N 2017中文字幕版+全部作业参考_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
• 大纲：Syllabus | CS 231N
• 课件：Index of /slides/2017
• 笔记：贺完结！CS231n官方笔记授权翻译总集篇发布
• 作业仓库：MachineLearning/CS231n at master · xiang578/MachineLearning
• 总课时: 16

01. Introduction to CNN for visual recognition

• 视觉地出现促进了物种竞争。
• ImageNet 是由李飞飞维护的一个大型图像数据集。
• 自从 2012 年 CNN 出现之后，图像分类的错误率大幅度下降。 神经网络的深度也从 7 层增加到 2015 年的 152 层。截止到目前，机器分类准确率已经超过人类，所以 ImageNet 也不再举办相关比赛。
• CNN 在 1998 年就被提出，但是这几年才流行开来。主要原因有：1) 硬件发展，并行计算速度提到 2）大规模带标签的数据集。
• Gola: Understand how to write from scratch, debug and train convolutional neural networks.

02. Image classification

• 图像由一大堆没有规律的数字组成，无法直观的进行分类，所以存在语义鸿沟。分类的挑战有：视角变化、大小变化、形变、遮挡、光照条件、背景干扰、类内差异。
  • 
• Data-Driven Approach
  • Collect a dataset of images and labels
  • Use Machine Learning to train a classifier
  • Evaluate the classifier on new images
• 图像分类流程：输入、学习、评估
• 图像分类数据集：CIFAR-10，这个数据集包含了60000张32X32的小图像。每张图像都有10种分类标签中的一种。这60000张图像被分为包含50000张图像的训练集和包含10000张图像的测试集。
• 一种直观的图像分类算法：K-nearest neighbor(knn)
  • 为每一张需要预测的图片找到距离最近的 k 张训练集中的图片，然后选着在这 k 张图片中出现次数最多的标签做为预测图片的标签（多数表决）。
  • 训练过程：记录所有的数据和标签 ${O(1)}$
  • 预测过程：预测给定图片的标签 ${O(n)}$
  • Hyperparameters：k and the distance Metric
  • Distance Metric
    • L1 distance(Manhattan Distance)
    • L2 distance(Euclidean Distance)
  • knn 缺点
    • Very slow at test time
    • Distance metrics on pixels are not informative
  • 反例：下面四张图片的 L2 距离相同
    • 
• Hyperparameters: choices about the algorithm that we set ranther than learn
• 留一法 Setting Hyperparameters by Cross-validation:
  • 将数据划分为 f 个集合以及一个 test 集合，数据划分中药保证数据集的分布一致。
  • 给定超参数，利用 f-1 个集合对算法进行训练，在剩下的一个集合中测试训练效果，重复这一个过程，直到所有的集合都当过测试集。
  • 选择在训练集中平均表现最好的超参数。
• Linear classification: Y = wX + b
  • b 为 bias，调节模型对结果的偏好
  • 通过最小化损失函数来，来确定 w 和 b 的值。
• Linear SVM: classifier is an option for solving the image classification problem, but the curse of dimensions makes it stop improving at some point. @todo
• Logistics Regression: 无法解决非线性的图像数据

03. Loss function and optimization

• 通过 Loss function 评估参数质量
  • 比如 $$L=\frac{1}{N}\sum_iL_i\left(f\left(x_i,W\right),y_i\right)$$
• Multiclass SVM loss 多分类支持向量机损失函数

  • $$L_i=\sum_{j \neq y_j}\max\left(0,s_j-s_{y_i}+1\right)$$

  • 这种损失函数被称为合页损失 Hinge loss
  • SVM 的损失函数要求正确类别的分类分数要比其他类别的高出一个边界值。
  • L2-SVM 中使用平方折叶损失函数$$\max(0,-)^2$$能更强烈地惩罚过界的边界值。但是选择使用哪一个损失函数需要通过实验结果来判断。
  • 举例
    • 
    • 根据上面的公式计算：$$L = \max(0,437.9-(-96.8)) + \max(0,61.95-(-96.8))=695.45$$
    • 猫的分类得分在三个类别中不是最高得，所以我们需要继续优化。
• Suppose that we found a W such that L = 0. Is this W unique?
  • No! 2W is also has L = 0!
• Regularization: 正则化，向某一些特定的权值 W 添加惩罚，防止权值过大，减轻模型的复杂度，提高泛化能力，也避免在数据集中过拟合现象。

  • $$L=\frac{1}{N}\sum_iL_i\left(f\left(x_i,W\right),y_i\right) + \lambda R(W)$$

  • R 正则项 $$\lambda$$ 正则化参数
• 常用正则化方法
  • L2$$\begin{matrix} R(W)=\sum_{k}\sum_l W^2_{k,l} \end{matrix}$$
  • L1$$\begin{matrix} R(W)=\sum_{k}\sum_l \left\vert W_{k,l} \right\vert \end{matrix}$$
  • Elastic net(L1 + L2): $$\begin{matrix} R(W)=\sum_{k}\sum_l \beta W^2_{k,l} + \left\vert W_{k,l} \right\vert \end{matrix}$$
  • Dropout
  • Batch normalization
  • etc
• L2 惩罚倾向于更小更分散的权重向量，L1 倾向于稀疏项。
• Softmax function：

  • $$f_j(z)=\frac{e^{s_i}}{\sum e^{s_j}}$$

  • 该分类器将输出向量 f 中的评分值解释为没有归一化的对数概率，通过归一化之后，所有概率之和为1。
  • Loss 也称交叉熵损失 cross-entropy loss $$L_i = - \log\left(\frac{e^{s_i}}{\sum e^{s_j}}\right)$$

1
2
3
4
5

f = np.array([123, 456, 789]) # 例子中有3个分类，每个评分的数值都很大
p = np.exp(f) / np.sum(np.exp(f)) # 不妙：数值问题，可能导致数值爆炸
# 那么将f中的值平移到最大值为0：
f -= np.max(f) # f becomes [-666, -333, 0]
p = np.exp(f) / np.sum(np.exp(f)) # 现在OK了，将给出正确结果

• SVM 和 Softmax 比较
  1. 评分，SVM 的损失函数鼓励正确的分类的分值比其他分类的分值高出一个边界值。
  2. 对数概率，Softmax 鼓励正确的分类归一化后的对数概率提高。
  3. Softmax 永远不会满意，SVM 超过边界值就满意了。
• Optimization：最优化过程
  • Follow the slope
    • 
• 梯度是函数的斜率的一般化表达，它不是一个值，而是一个向量，它是各个维度的斜率组成的向量。
  • Numerical gradient: Approximate, slow, easy to write. (But its useful in debugging.)
  • Analytic gradient: Exact, Fast, Error-prone. (Always used in practice)
  • 实际应用中使用分析梯度法，但可以用数值梯度法去检查分析梯度法的正确性。
• 利用梯度优化参数的过程：W = W - learning_rate * W_grad
• learning_rate 被称为是学习率，是一个比较重要的超参数
• Stochastic Gradient Descent SGD 随机梯度下降法
  • 每次使用一小部分的数据进行梯度计算，这样可以加快计算的速度。
  • 每个批量中只有1个数据样本，则被称为随机梯度下降（在线梯度下降）
• 图像分类任务中三大关键部分：
  1. 评分函数
  2. 损失函数：量化某个具体参数 ${W}$ 的质量
  3. 最优化：寻找能使得损失函数值最小化的参数 ${W}$ 的过程

04. Introduction to Neural network

• 反向传播：在已知损失函数 ${L}$ 的基础上，如何计算导数${\nabla _WL}$？
• 计算图
  • 由于计算神经网络中某些函数的梯度很困难，所以引入计算图的概念简化运算。
  • 在计算图中，对应函数所有的变量转换成为计算图的输入，运算符号变成图中的一个节点（门单元）。
• 反向传播：从尾部开始，根据链式法则递归地向前计算梯度，一直到网络的输入端。
  • 
  • 绿色是正向传播，红色是反向传播。
• 对于计算图中的每一个节点，我们需要计算这个节点上的局部梯度，之后根据链式法则反向传递梯度。
• Sigmoid 函数：${f(w,x)=\frac{1}{1+e^{-(w_0x_0+w_1x_1+w_2)}}}$
  • 
  • 对于门单元 ${\frac{1}{x}}$，求导的结果是 ${-\frac{1}{x^2}}$，输入为 1.37，梯度返回值为 1.00，所以这一步中的梯度是 ${(\frac{-1}{1.37^2})*1.00=-0.53}$。
  • 模块化思想：对 ${\sigma(x)=\frac{1}{1+e^{-x}}}$ 求导的结果是 ${(1-\sigma(x))\sigma(x)}$。如果 sigmoid 表达式输入值为 1.0 时，则前向传播中的结果是 0.73。根据求导结果计算可得局部梯度是 ${(1-0.73)*0.73=0.2}$。
• Modularized implementation: forward/backwar API

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class MultuplyGate(object):
  """
  x,y are scalars
  """
  def forward(x,y):
    z = x*y
    self.x = x  # Cache
    self.y = y	# Cache
    # We cache x and y because we know that the derivatives contains them.
    return z
  def backward(dz):
    dx = self.y * dz         #self.y is dx
    dy = self.x * dz
    return [dx, dy]

• 深度学习框架中会实现的门单元：Multiplication、Max、Plus、Minus、Sigmoid、Convolution
• 常用计算单元
  • **加法门单元：**把输出的梯度相等地分发给它所有的输入，这一行为与输入值在前向传播时的值无关。
  • **取最大值门单元：**将梯度转给前向传播中值最大的那个输入，其余输入的值为0。
  • **乘法门单元：**等值缩放。局部梯度就是输入值，但是需要相互交换，然后根据链式法则乘以输出值得梯度。
• Neural NetWorks
  • (Before) Linear score function $$f = Wx$$
  • (Now) 2-layer Neural NetWork $$f=W_2\max(0,W_1x)$$
  • ReLU $$\max(0,x)$$ 是激活函数，如果不使用激活函数，神经网络只是线性模型的组合，无法拟合非线性情况。
  • 神经网络是更复杂的模型的基础组件

05. Convolutional neural networks (CNNs)

• 这一轮浪潮的开端：AlxNet
• 卷积神经网络
  • Fully Connected Layer 全连接层：这一层中所有的神经元链接在一起。
  • Convolution Layer：
    • 通过参数共享来控制参数的数量。Parameter sharing
    • Sparsity of connections
  • 卷积神经网络能学习到不同层次的输入信息
  • 常见的神经网络结构：INPUT -> [[CONV -> RELU]*N -> POOL?]*M -> [FC -> RELU]*K -> FC
  • 使用小的卷积核大小的优点：多个卷积层与非线性的激活层交替的结构，比单一卷积层的结构更能提取出深层的更好地特征。而且使用的参数也会更少
• 计算卷积层输出
  • stride 是卷积核在移动时的步长
  • 通用公式 (N-F)/stride + 1
    • stride 1 => (7-3)/1 + 1 = 5
    • stride 2 => (7-3)/2 + 1 = 3
    • stride 3 => (7-3)/3 + 1 = 2.33
  • Zero pad the border: 用零填充所有的边界，保证输入输出图像大小相同，保留图像边缘信息，提高算法性能
    • 步长为 1 时，需要填充的边界计算公式：(F-1)/2
      • F = 3 => zero pad with 1
      • F = 5 => zero pad with 2
      • F = 7 => zero pad with 3
  • 计算例子
    • 输入大小 32*32*3 卷积大小 10 5*5 stride 1 pad 2
    • output 32*32*10
    • 每个 filter 的参数数量：5*5*3+1 =76 bias
    • 全部参数数量 76*10=760
• 卷积常用超参数设置
  • 卷积使用小尺寸滤波器
  • 卷积核数量 K 一般为 2 的次方倍
  • 卷积核的空间尺寸 F
  • 步长 S
  • 零填充数量 P
• Pooling layer
  • 降维，减少参数数量。在卷积层中不对数据做降采样
  • 卷积特征往往对应某个局部的特征，通过池化聚合这些局部特征为全局特征
• Max pooling
  • 2*2 stride 2
  • 避免区域重叠
• Average pooling

06. Training neural networks I

• Activation functions 激活函数

  • 不使用激活函数，最后的输出会是输入的线性组合。利用激活函数对数据进行修正。
  • 
  • Sigmoid
    • 限制输出在 [0,1]区间内
    • firing rate
    • 二分类输出层激活函数
    • Problem
      • 梯度消失：x很大或者很小时，梯度很小，接近于0（考虑图像中的斜率。无法得到梯度反馈。
      • 输出不是 0 均值的数据，梯度更新效率低
      • exp is a bit compute expensive
  • tanh
    • 输出范围 [-1, 1]
    • 0 均值
    • x 很大时，依然没有梯度
    • ${f(x)=\frac{e^{z}-e^{-z}}{e^{z}+e^{-z}}}$
    • ${1-(tanh(x))^2}$
  • RELU rectified linear unit 线性修正单元
    • 一半空间梯度不会饱和，计算速度快，对结果又有精确的计算
    • 不是 0 均值
  • Leaky RELU
    • leaky_RELU(x) = max(0.01x, x)
    • 梯度不会消失
    • 需要学习参数
  • ELU
    • 比 ReLU 好用
    • 反激活机制
  • Maxout
    • maxout(x) = max(w1.Tx + b1, w2.Tx + b2)
    • 梯度不会消失
    • 增大参数数量
  • 激活函数选取经验
    • 使用 ReLU ，但要仔细选取学习率
    • 尝试使用 Leaky ReLU Maxout ELU
    • 使用 tanh 时，不要抱有太大的期望
    • 不要使用 sigmoid

• 数据预处理 Data Preprocessing

  • 均值减法：对数据中每个独立特征减去平均值，从几何上来看是将数据云的中心都迁移到原点。
  • 归一化：将数据中的所有维度都归一化，使数值范围近似相等。但是在图像处理中，像素的数值范围几乎一致，所以不需要额外处理。

  1 2	X -= np.mean(X, axis = 1) X /= np.std(X, axis =1)

  • 图像归一化
    • Subtract the mean image AlexNet
      • mean image 32,32,3
    • Subtract per-channel mean VGGNet
      • mean along each channel = 3 numbers
    • 如果需要进行均值减法时，均值应该是从训练集中的图片平均值，然后训练集、验证集、测试集中的图像再减去这个平均值。
  • Weight Initialization
    • 全零初始化
      • 网络中的每个神经元都计算出相同的输出，然后它们就会在反向传播中计算出相同的梯度。神经元之间会从源头上对称。
    • Small random numbers
      • 初始化权值要非常接近 0 又不能等于 0。将权重初始化为很小的数值，以此来打破对称性
      • randn 函数是基于零均值和标准差的高斯分布的随机函数
      • W = 0.01 * np.random.rand(D,H)
      • 问题：一个神经网络的层中的权重值很小，那么在反向传播的时候就会计算出非常小的梯度。会减小反向传播中的“梯度信号”，在深度网络中就会出现问题。
    • Xavier initialization
      • W = np.random.rand(in, out) / np.sqrt(in)
      • 校准方差，解决输入数据量增长，随机初始化的神经元输出数据的分布中的方差也增大问题。
    • He initialization
      • W = np.random.rand(in, out) / np.sqrt(in/2)
  • Batch normalization
    • 保证输入到神经网络中的数据服从标准的高斯分布
    • 通过批量归一化可以加快训练的速度
    • 步骤
      • 首先计算每个特征的平均值和平方差
      • 通过减去平局值和除以方差对数据进行归一化
      • Result = gamma * normalizedX + beta
        • 对数据进行线性变换，相当于对数据分布进行一次移动，可以恢复数据之前的分布特征
    • BN 的好处
      • 加快训练速度
      • 可以使用更快的而学习率
      • 减少数据对初始化权值的敏感程度
      • 相当于进行一次正则化
    • BN 适用于卷积神经网络和常规的 DNN，在 RNN 和增强学习中表现不是很好
  • Babysitting the Learning Provess
  • Hyperparameter Optimization
    • Cross-validation 策略训练
    • 小范围内随机搜索

07. Training neural networks II

• Optimization Algorithms:

  • SGD 的问题

    • x += - learning_rate * dx
    • 梯度在某一个方向下降速度快，在其他方向下降缓慢
    • 遇到局部最小值点，鞍点

  • mini-batches GD

    • Shuffling and Partitioning are the two steps required to build mini-batches
    • Powers of two are often chosen to be the mini-batch size, e.g., 16, 32, 64, 128.

  • SGD + Momentun

    • 动量更新：从物理学角度启发最优化问题
    • V[t+1] = rho * v[t] + dx; x[t+1] = x[t] - learningRate * V[t+1]
    • rho 被看做是动量，其物理意义与摩擦系数想类似，常取 0.9 或0.99
    • 和 momentun 项更新方向相同的可以快速更新。
    • 在 dx 中改变梯度方向后， rho 可以减少更新。momentun 能在相关方向加速 SGD，抑制震荡，加快收敛。

  • Nestrov momentum

    • 
    • v_prev = v; v = mu * v - learning_rate * dx; x += -mu * v_prev + (1 + mu) * v

  • AdaGrad

    • $n_t=n_{t-1}+g^2_t$
    • $\Delta \theta _t = -\frac{\eta}{\sqrt{n_t+\epsilon}}$
    • 下面根号中会递推形成一个约束项。前期这一项比较大，能够放大梯度。后期这一项比较小，能约束梯度。
    • gt 的平方累积会使梯度趋向于 0

  • RMSProp

    • RMS 均方根
    • 自适应学习率方法
    • 求梯度的平方和平均数：cache = decay_rate * cache + (1 - decay_rate) * dx**2
    • x += - learning_rate * dx / (sqrt(cache) + eps)
    • 依赖全局学习率

  • Adam

    • RMSProp + Momentum
    • It calculates an exponentially weighted average of past gradients, and stores it in variables $v$ (before bias correction) and $v^{corrected}$ (with bias correction).
    • It calculates an exponentially weighted average of the squares of the past gradients, and stores it in variables $s$ (before bias correction) and $s^{corrected}$ (with bias correction).
    • 一阶到导数累积，二阶导数累积
    • It updates parameters in a direction based on combining information from “1” and “2”.
    • The update rule is, for $l = 1, ..., L$:

    $$\begin{cases} v_{dW^{[l]}} = \beta_1 v_{dW^{[l]}} + (1 - \beta_1) \frac{\partial \mathcal{J} }{ \partial W^{[l]} } \\ v^{corrected}_{dW^{[l]}} = \frac{v_{dW^{[l]}}}{1 - (\beta_1)^t} \\ s_{dW^{[l]}} = \beta_2 s_{dW^{[l]}} + (1 - \beta_2) (\frac{\partial \mathcal{J} }{\partial W^{[l]} })^2 \\ s^{corrected}_{dW^{[l]}} = \frac{s_{dW^{[l]}}}{1 - (\beta_1)^t} \\ W^{[l]} = W^{[l]} - \alpha \frac{v^{corrected}_{dW^{[l]}}}{\sqrt{s^{corrected}_{dW^{[l]}}} + \varepsilon} \end{cases}$$

    where:

    • t counts the number of steps taken of Adam
    • L is the number of layers
    • $\beta_1$ and $\beta_2$ are hyperparameters that control the two exponentially weighted averages.
    • $\alpha$ is the learning rate
    • $\varepsilon$ is a very small number to avoid dividing by zero

    特点：

    • 适用于大数据集和高维空间。
    • 对不同的参数计算不同的自适应学习率。

  • Learning decay

    • 学习率随着训练变化，比如每一轮在前一轮的基础上减少一半。
    • 防止学习停止

  • Second order optimization

• Regularization
  • Dropout
    • 每一轮中随机使部分神经元失活，减少模型对神经元的依赖，增强模型的鲁棒性。
• Transfer learning
  • CNN 中的人脸识别，可以在大型的模型基础上利用少量的相关图像进行继续训练。

09. CNN architectures

• 研究模型的方法：搞清楚每一层的输入和输出的大小关系。
• LeNet - 5 [1998]
  • 60k 参数
  • 深度加深，图片大小减少，通道数量增加
  • ac: Sigmod/tanh
• AlexNet [2012]
  • (227,227,3) （原文错误）
  • 60M 参数
  • LRN：局部响应归一化，之后很少使用
• VGG - 16 [2015]
  • 138 M
  • 结构不复杂，相对一致，图像缩小比例和通道增加数量有规律
• ZFNet [2013]
  • 在 AlexNet 的基础上修改
    • CONV1: change from (11 x 11 stride 4) to (7 x 7 stride 2)
    • CONV3,4,5: instead of 384, 384, 256 filters use 512, 1024, 512
• VGG [2014]
  • 模型中只使用 3*3 conv：与 77 卷积有相同的感受野，而且可以将网络做得更深。比如每一层可以获取到原始图像的范围：第一层 33，第二层 55，第三层 77。
  • 前面的卷积层参数量很少，模型中大部分参数属于底部的全连接层。

• GoogLeNet
  • 引入 Inception module
    • design a good local network topology (network within a network) and then stack these modules on top of each other
    • 该模块可以并行计算
    • conv 和 pool 层进行 padding，最后将结果 concat 在一起

• ResNet
  • 目标：深层模型表现不应该差于浅层模型，解决随着网络加深，准确率下降的问题。
  • Y = (W2* RELU(W1x+b1) + b2) + X
  • 如果网络已经达到最优，继续加深网络，residual mapping会被设置为 0，一直保存网络最优的情况。

Reference

• 深度学习最全优化方法总结比较（SGD，Adagrad，Adadelta，Adam，Adamax，Nadam） - 知乎

李如一在 写作风格手册 中提到写作风格的作用是 「保持机构和组织内部的文体统一，提高沟通效率。」

本清单会持续更新，如果有相关的建议，可以在留言中告诉我。

算法花园定位为个人博客，也是我和这个世界沟通的窗口。为提高读者阅读体验，参考相关文章后，推出该清单统一网站文章的基础风格。

写作

1. 减少形容词使用，尽可能删除 「的」和「了」。
2. 给出引用图片及引文来源。
3. 文章如果发布后大幅度修改，在末尾给出版本信息。
4. 写完文章后，整体阅读一遍。

排版

1. 中文、英文、数字中间加空格，数字与单位之间无需增加空格，全角标点与其他字符之间不加空格。链接前后增加空格用以区分。
2. 不重复使用标点符号。
3. 中文使用直角引号 「」以及『 』。
4. 使用全角中文标点，数字使用半角字符。中文中出现英文部分，仍然使用中文标点。
5. 遇到完整的英文整句、特殊名词，其內容使用半角标点。
6. 专有名词使用正确的大小写，使用公认的缩写。
7. todo 如何处理图片排版和命名。
8. 使用英文命名文档，使用 - 来连接。为保证搜索引擎效果，尽量不要修改文档名称。
9. 每篇文章开头添加简单介绍 <!--more-->。
10. 发布后，在网页中确认格式是否符合预期、链接能否点击以及图片能否展示。

ChangeLog

20191103: 第一版

参考

• 写作风格手册_设计词典_好奇心日报
• 中文文案排版指北（简体中文版） — 码志
• 简体中文文本排版指南 - 知乎
• 少数派写作排版指南 - 少数派
• 城堡制作检查清单 0.1 版 - 简书

严重申明：本篇文章所有信息从论文、网络等公开渠道中获得，不会透露滴滴地图 ETA 任何实现方法。

这篇论文是滴滴时空数据组 2018 年在 KDD 上发表的关于在 ETA 领域应用深度学习的文章，里面提到模型和技巧大家都应该耳熟能详，最大亮点是工业界的创新。

简单介绍一下背景：ETA 是 Estimate Travel Time 的缩写，中文大概能翻译成到达时间估计。这个问题描述是：在某一个时刻，估计从 A 点到 B 点需要的时间。对于滴滴，关注的是司机开车把乘客从起点送到终点需要的时间。抽象出来 ETA 就是一个时间空间信息相关的回归问题。CTR 中常用的方法都可以在这里面尝试。

对于这个问题：文章首先提到一个最通用的方法 Route ETA：即在获得 A 点到 B 点路线的情况下，计算路线中每一段路的行驶时间，并且预估路口的等待时间。最终 ETA 由全部时间相加得到。这种方法实现起来很简单，也能拿到一些收益。但是仔细思考一下，没有考虑未来道路的通行状态变化情况以及路线的拓扑关系。针对这些问题，文章中提到滴滴内部也有利用 GBDT 或 FM 的方法解决 ETA 问题，不过没有仔细写实现的方法，我也不好继续分析下去。

评价指标

对于 ETA 问题来说，工业界和学术界常用的指标是 MAPE(mean absolute percentage error)，${y_i}$ 是司机实际从 A 点到 B 点花费的时间，${f(x_i)}$ 是 ETA 模型估计出来的时间。得到计算公式如下：

$${min_f \sum_{i=1}^{N}\frac{|y_i - f(x_i)|}{y_i}}$$

多说一句，如果使用 GBDT 模型实现 ETA 时，这个损失函数的推导有点困难，全网也没有看见几个人推导过。

这个公式主要考虑预估时间偏差大小对用户感知体验的影响，目前我们更加关心极端 badcase 对用户的影响。

特征

• 特征：
  • 空间特征：路线序列、道路等级、POI等
  • 时间特征：月份、星期、时间片等
  • 路况特征：道路的通行速度、拥堵程度
  • 个性化信息：司机特征、乘客特征（有「杀熟」风险）、车辆特征
  • 附近特征：天气、交通管制

模型

模型包含 3 个部分：

• Wide Learning Models：Wide & Deep 这一部分使用的是 LR + 特征工程，希望模型能记忆一部分的模型。这篇论文中直接利用交叉积学习，减少手动特征工程。
• Deep Neural Networks：对 sparse feature 做一次 Embedding，使用 3 层 MLP 和 ReLU 的网络。
• Long-Short Term Memory：前两部分模块没用使用路线序列特征，所以这部分采用 LSTM 抽取路线特征。由于路线序列是不定长的，论文中的模型是使用最后一个隐藏状态，我们也可以把全部的隐藏状态 reduce_sum 输入到最后的模块。
• Regressor： 将 3 个模型的输出综合起来，作为最后的 ETA 预估。MAPE 作为损失函数，利用 BP 训练模型。

上面模型中使用的特征分类：

• Dense feature：行程级别的实数特征，比如起终点球面距离、起终点 GPS 坐标等。
• Sparse feature：行程级别的离散特征，比如时间片编号、星期几、天气类型等。
• Sequential feature：link 级别的特征，实数特征直接输入模型，而离散特征先做 embedding 再输入模型。注意，这里不再是每个行程一个特征向量，而是行程中每条 link 都有一个特征向量。比如，link 的长度、车道数、功能等级、实时通行速度等。

评估

包括两部分：离线评估和在线评估。

离线评估中取滴滴 2017 年北京前6个月的订单数据，分成两类 pickup （平台给司机分单后，司机开车去接乘客的过程）和 trip （司机接到乘客并前往目的地的过程）。具体数据集划分如下。

离线使用 MAPE 来评价模型。在线评估时，为了更好的与用户体验挂钩，采用多个指标来衡量 ETA 的效果。包括：

• APE20: absolute percentage error 小于 20% 的订单占比。（越大越好）
• Badcase率：APE 大于 50% 或者 AE 大于 180s 的订单占比，定义为对用户造成巨大影响的情况。（越小越好）
• 低估率：低估订单的比例。（越小越好）

离线结果如下图所示，说来汗颜 PTTE 和 TEMP 是什么算法我都不知道…… WD-MLP 指的是将 WDR 中的 R 部分换成 MLP 。最终 WDR 较 route-ETA 有巨大提升，而且 LSTM 引入的序列信息也在 pikcup 上提升了 0.75%。文章的最后还提出来，LSTM 也可以换成是 Attention，这样替换有什么优点和缺点留给大家思考。

在线实验结果如下图所示，滴滴 ETA MAPE 明显小于 com1、com2、com3 ，这三家地图公司具体是哪三家，大家也能猜到吧。

ETA 服务工程架构

从上面的图中可以看出 ETA 服务工程架构主要包括三个部分：

• Data Aggregation：包括利用 Map Matching 将司机上传到平台的 GPS 对应到滴滴的 Map Info 中得到司机真实行驶过的路线信息，Order Context 指的是订单相关的信息，augmented Data 额外数据比如上文说的交通情况相关信息。
• Offline Training：利用上一步得到的历史数据训练模型。这里可以值得一提的是，ETA 模型是和时间强相关的（节假日和工作日的数据分布明显不同），所以在文章中作者指出将拿出最新的一部分数据用来 fine-tune 训练出来的 WDR 模型。
• Online Service：这里需要一个完整的模型服务系统，其他公司也有很多分享，所以原文没有多提。

FMA-ETA: Estimating Travel Time Entirely Based on FFN With Attention

• WDR 模型中 RNN 耗时长，探索基于 Attention 机制的模型
• 对特征分组（multi-factor）去做 Attention 效果比多头要好
• 实验结果分析这部分没有看懂

  The deep modules with attention achieve better results than WDR on MAE and RMSE metrics, which means attention mechanism can help to extract features and sole the long-range dependencies in long sequence.

• 遗憾之处
  • 新模型预测时延减少，但是没有线上实验结果。
  • 暂时没有公开代码和数据集。

总结

从上面简单的介绍来看，ETA 可以使用 CTR 和 NLP 领域的很多技术，大有可为。最后，滴滴 ETA 团队持续招人中（社招、校招、日常实习等），感兴趣者快快和我联系。

说点题外话 你为什么从滴滴出行离职？ - 知乎 中提到一点：

8.同年大跃进，在滴滴中高层的眼里，没有BAT。滴滴单量超淘宝指日可待，GAFA才是滴滴要赶超的对象。百度系，LinkedIn系，学院派，uber帮，联想系，MBB就算了，据说连藤校都混成了一个小圈子。。一个项目A team ，B team。一个ETA，投入了多少人力自相残杀？MAPE做到0%又如何？用户体验就爆表了吗？长期留存就高枕无忧了吗？风流总被雨打风吹去，滴滴是二龙山，三虫聚首？是不是正确的事情不知道，反正跟着公司大势所趋，升D10保平安。

参考

• KDD 2018：滴滴提出WDR模型显著提升ETA预测精度 | 雷锋网
• LBS工业界ETA应用及滴滴WDR技术 – Semocean