一篇关于时间序列异常检测的论文

November 26, 2018 zr9558 2 Comments

近期阅读了一篇论文《Rapid Deployment of Anomaly Detection Models for Large Number of Emerging KPI Streams》，这篇文章基于之前的 ROCKA 系统做了一些额外的工作。ROCKA 系统是用来做时间序列的实时聚类的，而这篇文章是在 ROCKA 系统的基础上增加了时间序列异常检测的功能。通常来说，时间序列异常检测可以使用有监督的方法来解决，参考 Opperentice 系统。而本篇文章使用了半监督学习的思路来解决异常检测的问题，下面来详细分析一下这篇文章的细节，本文的作者把这个系统称为 ADS（Anomaly Detection through Self-training）。

数据集的情况

在论文中，作者使用了两份数据集，分别是已经历史上的 70 条时间序列，另外还有新来的 81 条时间序列。在 ADS 系统中，历史上的 70 条时间序列被划分成 5 类，并且已经可以找出每个类的质心位置，并且每条历史上的时间序列通常来说会大于三个星期（3 weeks）。本篇论文的评价指标是 F-Score，也属于机器学习领域里面比较常用的衡量模型效果的指标。整体来看，这篇文章的数据集大约是 200 条时间序列，时间序列的时间间隔通常来说是五分钟（不过其余的运维场景会有一分钟的数据采集粒度），而一般来说都拥有大半年甚至一年的时间跨度。那么时间点的个数预估是 200 * (1440 / 5) * 365。假设异常的数据：正常的数据 = 1：10000（也就是说平均每条时间序列每周至少发生一次异常），于是这批时间序列数据的异常数据量大约是 200 * (1440 / 5) * 365 / 10000 = 2102，也就是说异常的样本大约是 2102 个左右，剩下的都是正常的样本。PS：当然如果异常的数据：正常的数据的比例大于 1：10000 的话，异常的样本还会更多一些。整体来看，时间序列异常检测是一个样本极其不均衡的场景。

ADS 的系统架构

按照作者之前论文的经验，时间序列异常检测通常都是先做聚类，然后再根据每一个类的特点来做一个异常检测模型，之前的技术架构就是 ROCKA + Opperentice。因为 ROCKA 可以根据时间序列的走势和趋势来进行时间序列的实时分类/聚类，然后 Opperentice 就是做时间序列异常检测的模型。在本文的场景下，作者把 70 条时间序列分成了5 类，因此只需要维护 5 个时间序列的异常检测模型就可以了。当然把时间序列切分成更多的类也是可以的，只是需要维护的时间序列异常检测就变多了，人工成本会加大。

如果看到上面两幅图，有心的读者一定会发现其实 ADS 就是基于 ROCKA 所做的工作。ADS 先对时间序列进行了分类，然后进行了特征提取的工作，再通过半监督学习模型，最后进行异常检测。也就是说，ADS 会走下面四个步骤：

ADS 先把历史上的时间序列进行聚类；
通过算法获得每一个类的质心，并且标记出质心曲线的异常点和正常点；
对新来的时间序列进行实时聚类，划分到合适的类别；
基于新来的时间序列（没有标记）和历史上的时间序列（有标记）使用无监督算法来重新训练一个新的模型，进行该类别的时间序列异常检测。

ADS 的细节

对于时间序列的聚类框架 ROCKA，之前的一篇 BLOG 里面已经详细介绍过，这里将不会再赘述。而 ADS 的另一个模块就是半监督学习算法 Contrastive Pessimistic Likelihood Estimation（CPLE），详细的论文细节可以参考论文《Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification》。CPLE 有几个好处：

CPLE 是半监督学习算法中比较健壮的，因为它并没有过多的假设条件，并且也符合这篇文章的业务场景，同时拥有质心曲线（有标记）和新来的曲线（无标记），使用半监督学习也是符合常理的。除了 CPLE，其实在实战过程中也可以多尝试其他的半监督模型，具体可以参考周志华的《机器学习》。
CPLE 的复杂度比较低，计算快。
CPLE 支持增量学习，因此，当越来越多新的时间序列进入 ADS，这个模型也会随之而调整并提高准确率。

整体来看，ADS = ROCKA + CPLE，而在论文中，它的对比模型就是 ROCKA + Opperentice。而且在 CPLE 中，也使用了与 Opperentice 系统类似的特征，如下图所示。

其实，从本质上来看，就是半监督学习与有监督学习在这份数据集合上面的比较。从这篇论文里面所展示的数据来看，CPLE 有一定的优势。

ADS效果对比1 — Average best F-scores of ADS, iForest, Donut, Opperentice, ROCKA + Opperentice

整体来看，本篇文章介绍了时间序列异常检测的一种方案，也就是把时间序列先进行聚类的操作，然后根据不同的类来进行异常检测。在异常检测的方法中，不仅可以使用 Random Forest，GBDT，XGBoost 等有监督学习方法，也可以使用 CPLE 等半监督算法。具体在业务中如何使用，其实只能够根据具体的数据来进行合理地选择了。

时间序列, 智能运维

两篇关于时间序列的论文

November 22, 2018 zr9558 1 Comment

这次整理的就是清华大学裴丹教授所著的两篇与时间序列相关的论文。一篇是关于时间序列聚类的，《Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection》；另外一篇文章是关于时间序列异常检测的，重点检测时间序列上下平移的，《Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection》。本文将会整理一下这两篇文章的关键技术点。

Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection

在互联网公司中，通常会拥有海量的的时间序列，而海量的时间序列就有着各种各样的形状和走势。因此，就有学者提出可以先对时间序列进行分类，然后根据不同的类使用不同的检测模型来进行异常检测。如果要做时间序列的分类，就先需要做聚类的操作，无论从 KMeans，DBSCAN，还是层次聚类来说，都会消耗一定的运算时间。所以，如何在较短的时间内进行聚类或者分类的操作则是这个系统的关键之处。于是，这篇文章提出了一个将时间序列快速聚类的方法。

时间序列 -> 时间序列分类

-> 根据每一类时间序列使用不同的异常检测模型

而在做时间序列聚类的时候，也有着不少的挑战。通常挑战来自于以下几点：

形状：通常来说，时间序列随着业务的变化，节假日效应，变更的发布，将会随着时间的迁移而造成形状的变化。
噪声：无论是从数据采集的角度，还是系统处理的角度，甚至服务器的角度，都有可能给时间序列带来一定的噪声数据，而噪声是需要处理掉的。
平移：在定时任务中，有可能由于系统或者人为的原因，时间序列的走势可能会出现一定程度的左右偏移，有可能每天 5:00 起的定时任务由于前序任务的原因而推迟了。
振幅：通常时间序列都存在一条基线，而不同的时间序列有着不同的振幅，振幅决定了这条时间序列的振荡程度，而振幅或者基线其实也是会随着时间的迁移而变化的。

从整篇论文来看，ROCKA 系统是为了做实时的时间序列分类判断的。要想做成实时的分类判断，就需要有离线和在线两个模块。其中离线是为了做模型训练或者聚类的，在线是为了使用离线处理好的模块来做曲线分类的。

从整个系统来看，离线模块需要做以下几件事情：首先需要收集一批时间序列数据，也就是所谓的 Raw Time Series Data（Raw），通过预处理模块，实施基线提取，再进行聚类的操作，获得相应的聚类结果和质心。在线模块同样也要做类似的事情：首先对于每一条新来的时间序列数据，也就是所谓的 New Time Series Data（Raw），通过预处理模块，实施基线提取，然后使用已经聚类好的离线模块来进行实时的分类。

下面，我们来逐一分析每个模块的作用。

预处理模块（Preprocessing）

通常预处理模块包含几个关键点：

缺失值：缺失值指的是在该上报数据的时间戳上并没有相应的数据上报，数据处于缺失的状态。通常的办法就是把数据补齐，而数据补齐的方法有很多种，最简单的就是使用线性插值（Linear Interpolation）的方式来补齐。
标准化：对于一个时间序列而言，有可能它的均值是10万，有可能只有10，但是它们的走势有可能都是一样的。所以在这个时候需要进行归一化的操作。最常见的有两种归一化方法：一种是标准化，另外一种是最大最小值归一化。如果 $[x_{1},x_{2}, \cdots, x_{n}]$ 表示原始的时间序列的话，标准化指的是 $\hat{x}_{i} = (x_{i} -\mu) /\sigma$ ，其中 $\mu$ 和 $\sigma$ 分别表示均值和标准差。最大最小值归一化指的是 $\hat{x}_{i} = (x_{i} - \min) / (\max - \min)$ ，其中 $\max, \min$ 分别表示这段时间内的最大值与最小值。

基线提取模块（Baseline Extraction）

基线提取指的是把时间序列分成基线和剩余项两个部分，假设时间序列是 $[x_{1},x_{2},\cdots,x_{n}]$ ，基线提取就是：

$x_{i} = baseline_{i} + residual_{i},$

其中 $baseline_{i}, residual_{i}$ 分别指的是 $x_{i}$ 的基线和剩余项。

在处理基线的时候，有几件事情需要注意：

异常值的处理：通常需要移除一些明显异常的值，然后使用线性插值等方法来把这些移除的值补上。
使用简单的移动平均算法加上一个窗口值 $w$ 来提取基线。假设时间序列是 $[x_{1},\cdots,x_{n}]$ ， $SMA_{i} = \sum_{j=i-w+1}^{i} x_{j} / w$ ， $R_{i} = x_{i} - SMA_{i}$ 。也就是说 $x_{i} = SMA_{i} + R_{i}$ 。
提取基线的方式其实还有很多，使用带权重的移动平均算法（Weighted Moving Average），指数移动平均算法（Exponentially Weighted Moving Average）都可以提取基线，甚至使用深度学习中的 Autoencoder 或者 VAE 算法都能够提取基线。

基于密度的聚类算法（Clustering）

使用预处理和基线提取技术之后，可以得到原始时间序列的基线值，然后根据这些基线值来进行时间序列的聚类操作。一般来说，时间序列的聚类有两种方法：

通过特征工程的方法，从时间序列中提取出必要的时间序列特征，然后使用 KMeans 等算法来进行聚类。
通过相似度计算工具，对比两条时间序列之间的相似度，相似的聚成一类，不相似的就分成两类。

对于第一种方法而言，最重要的就是特征工程；对于第二种方法而言，最重要的是相似度函数的选择。在这篇文章中，作者选择了第二种方法来进行时间序列的聚类。对于两条时间序列 $X = [x_{1},\cdots,x_{m}]$ 和 $Y = [y_{1},\cdots,y_{m}]$ 而言，为了解决左右平移的问题，需要考虑一个偏移量 $|s|$ ，然后计算它们之间的内积。

$CC_{s}(X,Y) = \begin{cases} \sum_{i=1}^{m-s}x_{s+i}\cdot y_{i}, \text{ where } s\geq 0, \\ \sum_{i=1}^{m+s}x_{i} \cdot y_{i-s} \text{ where } s<0.\end{cases}$

通过这个偏移量 $|s|$ 就可以计算出最大的相似度，然后计算出两条时间序列之间的距离。i.e.

$NCC(X,Y) = \max_{s}\bigg(\frac{CC_{s}(X,Y)}{||X||_{2}\cdot||Y||_{2}}\bigg),$

$SBD(X,Y) = 1 - NCC(X,Y).$

其中 $NCC \in [-1,1]$ 指的是 Normalized version of Cross-Correlation， $SBD \in [0,2]$ 指的是 Shape-based distance。

而聚类的另一个重要指标就是质心的选择，在这里，每个类的质心可以设置为：

$\text{Centroid} = argmin_{X \in \text{cluster}_{i}} \sum_{Y \in \text{cluster}_{i}} SBD(X,Y)^{2}.$

实时分类（Assignment）

对于一条新的时间序列（Raw Data），同样需要经过预处理，基线提取等步骤，然后计算它与之前每一个质心的距离。然后进行距离的从小到大排序，最小的那一类可能就是所需要的。当然，当最小距离大于某个 threshold ，就说明这条新的时间序列曲线很可能不属于之前的任何一类。通过人工查看之后，可以考虑新增一类，并且更新之前所做的聚类模型。

聚类与时间序列异常检测

如果要做海量的时间序列异常检测的话，通常有以下两种做法。

先对时间序列进行聚类或者分类，针对不同的时间序列类型来使用不同的模型；
在时间序列异常检测中加入分类特征。

对于第一种方法而言，需要针对不同形状的时间序列维护不同的模型，而且如果第一层的聚类/分类错误了，那么使用的模型也会出现错误。对于第二种方法而言，关键在于样本的积累和分类特征的构建。

Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection

这篇文章是关于时间序列异常检测的，而清华大学的 Netman 实验室做时间序列异常检测的相关工作比较多。从 2015 年开始的 Opperentice（Random Forest 模型），Funnel（SST 模型，变更相关），到后来的 Donut（VAE 模型），都是时间序列异常检测的相关文章。而这篇问题提到的 StepWise 系统针对的场景是关于指标的迁移的，所谓概念漂移（Concept Drift）指的就是时间序列会随着变更，发布，调度或者其他事件的发生而导致上下漂移或者左右漂移。一个比较典型的例子就是关于网络流量的漂移，通常来说在某个特点的时间点，时间序列会出现猛跌或者猛涨的情况，但是下跌或者上涨之后的走势和历史数据是及其相似的，只是绝对值上有所变化。

正如上图所示，在时间戳 08-02 附近，时间序列出现了一个下跌的情况。但是根据历史数据所计算出来的上界（Upper Bound）和下界（Lower Bound）却会把未来一段时间的序列都判断为异常。但是前后的曲线走势却是一样的，其实只有下跌的那一小段时间应该被判断为异常，其他时间都是正常的。基于以上的业务场景，这篇文章的作者就提出了概念漂移（Concept Drift）的一些方法。

在整个 StepWise 系统背后，有两个比较关键的地方。其中第一个关键之处就是如何判断异常点。在这个业务场景下，需要检测的是上图发生暴跌的点。而暴跌或者暴涨只是业务运维用来描述时间序列的一个词语。在统计学领域，这种点通常称为变点（Change Point）。所以概念漂移的检测可以转化为一个变点检测的问题，正是论文里面写的。

Insight 1：Concept drift detection can be converted into a spike detection problem in the change score stream.

如果是进行变点检测的话，其实可以参考 2016 年的论文 Funnel：Assessing Software Changes in Web-based Services。里面使用了 Singular Spectrum Transform 来进行检测，并且使用 Difference in Difference 来判断时间序列是否真正出现了异常。关于 SST（Singular Spectrum Transform）的具体细节可以参考 Yasser Mohammad, Toyoaki Nishida 所撰写的 Robust Singular Spectrum Transform。SST 算法是基于 SVD 算法的，有一定的时间复杂度。而基于 SST 又有学者提出了 Robust SST，具体可以详见论文。而 StepWise 的其中两步就是 Detection 和 Classification，其中的 Detection 使用了 Improved SST，Classification 使用了Difference in Difference。而 Funnel 系统的其中两步也是 Improved SST 和 Difference in Difference，这与 Funnel 有异曲同工之妙，Funnel 系统详情请见下图。

而突变前后的时间序列可以分别叫做 Old Concept 和 New Concept，由于前后的走势几乎一致，所以本文的第二个关键点就是相似度的判断。

Insight 2：The relationship between new concept and old concept can be almost perfectly fitted by linear regression.

从数学的角度来讲，Insight 2 的陈述是想判断两条时间序列是否相似。假设 $X=[x_{1},\cdots, x_{n}]$ 和 $Y = [y_{1},\cdots, y_{n}]$ ，那么以下陈述是等价的。

存在一个线性关系 $y = kx$ 使得二维点集 $\{(x_{i},y_{i}), 1\leq i\leq n\}$ 能够被很好的拟合好，也就是说此刻的方差较小。
$[x_{1},\cdots,x_{n}]$ 与 $[y_{1},\cdots,y_{n}]$ 的 Pearson 系数很高；
$[x_{1},\cdots,x_{n}]$ 与 $[y_{1},\cdots,y_{n}]$ 标准化（z-score）之后的曲线几乎一致。
分别存在两个值 $\mu_{1},\mu_{2}$ 使得 $[x_{1}/\mu_{1},\cdots,x_{n}/\mu_{1}]$ 与 $[y_{1}/\mu_{2},\cdots,y_{n}/\mu_{2}]$ 几乎一致。

所以，在 StepWise 中，作者通过线性回归的算法来判断 old concept 与 new concept 是否存在线性关系，也就是说这两者是否只是平移的关系。其实也可以尝试上面所说的其余方法。

整体来看，StepWise 大致分成两个关键步骤。首先使用类似 Funnel 系统的思想，先进行异常检测（SST），再使用判断一下是不是因为软件的变更引起的（DID），最后使用一层过滤逻辑（线性拟合）来判断是否出现了概念漂移的情况。在实际使用过程中，无论是异常检测还是过滤逻辑，都需要根据具体的业务来做，很难找到一个固定的模型来解决所有的难题。

Finance

Kelly Criterion

November 15, 2018 zr9558 Leave a comment

典型案例

无论是在数学课上还是日常生活中，相比大家对抛硬币这个游戏并不陌生。通常来说，硬币有正反两面，并且抛一次硬币出现正面和反面的概率是一样的，也就是二分之一。如果用数学符号来表示的话，那就是 $p = q = 1/2,$ 这里的 $p,q$ 分别表示硬币出现正面和反面的概率值。从直觉上说，在这种情况下，如果我们每次投入的资金都是一样的并且资金链条不会断裂，那么随着投币次数的增多，最终我们应该是既不会赢钱也不会输钱，总资产和一开始的时候一样保持不变。

数学描述

用数学语言来描述这个过程的话，假设我们的初始资产是 $X_{0}$ ， $X_{n}$ 表示 $n$ 次下注之后我们当前的资产，每次下注的钱是 $B_{k}$ ，用 $T_{k} =1$ 表示第 $k$ 次下注获胜， $T_{k} = -1$ 表示第 $k$ 次下注失败。那么从数学公式上来说就是：对于所有的 $k\geq 1$ ，都有

$X_{k} = X_{k-1} + T_{k}B_{k},$

进一步可以得到：

$X_{n} = X_{0} + \sum_{k=1}^{n} T_{k}B_{k},$

所以，

$E(X_{n}) = X_{0} + \sum_{k=1}^{n}E(T_{k}B_{k}) = X_{0} + \sum_{k=1}^{n}(p-q)E(B_{k}).$

对于上面特殊的例子，当 $p = q = 1/2$ 时，就可以得到 $E(X_{n}) = X_{0}.$

当 $p>q$ 的时候，表示赌赢的概率大于赌输的概率。这种时候，如果需要让 $E(X_{n})$ 最大，那么就需要最大化每次的 $E(B_{k})$ 。所以，在这种情况下，我们需要在每次下注的时候，把手上所有的资产全部下注，然后总资产随着次数的增加就会出现几何级数的增长。

相反的，如果 $p<q$ ，表示下注获胜的概率小于下注失败的概率。这种时候，如果需要让 $E(X_{n})$ 最大，那么就需要最小化每次的 $E(B_{k})$ ，因为 $p-q<0.$ 所以，在这种情况下，我们在每次下注的时候，其实就不需要投注，每次的 $B_{k}=0$ ，在这种情况下，我们的总资产其实就会保持原样不变。i.e. $E(X_{n}) = X_{0}.$

按比例投注

在每次下注或者投资的时候，我们通常都会想着按照一定的比例来投注自己当前的资产。也就是说，存在一个参数 $0\leq f\leq 1$ ，使得 $B_{i} = f X_{i-1}$ ，也就是说，每次投注的时候，基于上一轮的总资产来投注相应的比例即可。如果当前的资产是 $X$ ，如果下注赢了，那么总资产就变成 $X(1+f)$ ；如果下注输了，那么总资产就变成 $X(1-f)$ 。意思就是说，如果赢了，那就在原来资产的基础上乘以 $(1+f)$ ；如果输了，那就在原来资产的基础上乘以 $(1-f)$ 。在这种情况下，如果我们进行了 $n$ 次下注，那么此刻的资产就变成了

$X_{n} = X_{0} \cdot(1+f)^{S}\cdot(1-f)^{F}$

其中， $S, F$ 分别表示成功和失败的次数，并且 $S+F=n$ 。

当 $f=0$ 时，表示永远不下注，此时对于所有的 $n\geq 0$ ，都有 $X_{n}=X_{0}$ ；当 $f=1$ 时，表示每次下注的时候都是全部下注，那么只要 $F\geq 1$ ，就会出现 $X_{n}=0$ 的情况。意思就是说，如果有一次失败了，那就全盘皆输，没有任何资产可以继续运营。但是如果运气足够好的话，那就是 $S=n, F=0$ ，总资产就是 $X_{n} = X_{0}\cdot 2^{n}.$

当 $0<f<1$ 时，从公式中可以得到：

$\ln X_{n} = \ln X_{0} + S\cdot \ln(1+f) + F\cdot \ln(1-f)$

$\Rightarrow G_{n}(f)=\ln(X_{n}/X_{0})^{1/n}$

$=(\ln X_{n}-\ln X_{0})/n = (S/n) \ln(1+f) + (F/n)\ln(1-f)$

进一步可以得到：

$g(f) = E(\ln(X_{n}/X_{0})^{1/n})$

$= E((S/n) \ln(1+f) + (F/n)\ln(1-f))$

$= p\ln(1+f)+q\ln(1-f).$

因此，可以通过研究 $g(f)$ 来确定 $E(X_{n})$ 的最大值。为了计算 $g(f)$ 的最大值和最小值，则需要通过导数来研究。可以简单的看出来：当 $p,q\in(0,1)$ 时， $g(0) = 0$ ， $\lim_{f\rightarrow 1^{-}} g(f) = -\infty$ 。计算导数可以得到：

$Dg(f) = \frac{p}{1+f} - \frac{q}{1-f} = \frac{p-q-f}{1-f^{2}},$

$D^{2}g(f) = \frac{-(1-f)^{2}-4fq}{(1-f^{2})^{2}}<0.$

所以，导数 $Dg(f)$ 是一个严格递减函数，当 $f<p-q$ 时， $Dg(f)>0$ ；当 $f>p-q$ 时， $Dg(f)<0$ 。因此，函数 $g(f)$ 会在 $f^{*} = p-q$ 的时候达到最大值。所以，每次最佳的投注比例应该是 $f^{*} =p-q$ 。

从这个结果上来看，如果 $p<q$ ，那么意思就是最好不要做投注，因为输的概率比较大。如果 $p>q$ ，那么意思就是投注的比例是 $f^{*}=p-q$ 。在这种情况下，可以得到 $g(f^{*}) = p\ln p + q\ln q + \ln 2.$ 从以上信息分析，也可以得到存在一个点 $f_{c}$ 使得 $g(f_{c}) = 0$ 。

kellycriterion1

一般形式（一）

在一般情况下，在现实生活中都会有赔率的概念。也就是说：赢钱的时候需要考虑赔率，押 $1$ 赔 $b$ ，也就是所谓的赢钱率，资产从 $1$ 增加到 $1+b$ 。举个简单的例子来描述那就是：当硬币有偏差，同时有赔率（赢钱率）的时候该怎么办？

在这种情况下，之前的 $g(f)$ 可以写成如下的形式：

$g(f)=p\ln(1+bf)+q\ln(1-f)$ .

这里的 $p, q$ 分别表示赢钱和输钱的概率，并且 $p+q=1$ 。 $f$ 表示每次应该押上的当前总资产的比例，并且 $0\leq f\leq 1$ 。通过计算可以直接得到：

$Dg(f) = \frac{pb-q-bf}{(1+bf)(1-f)}$ .

并且 $g(0) = 0$ ， $\lim_{f\rightarrow 1^{-}}g(f) = -\infty$ 。从导数上可以看出，当 $f>(pb-q)/b$ 时， $g(f)$ 是增函数；当 $f<(pb-q)/b$ 时， $g(f)$ 是递减函数。因此，当 $f = (pb -q)/b$ 时， $g(f)$ 达到最大值，也就是

$g(f) = p\ln p + q\ln q + \ln(1+b) - q\ln b$ .

在这种情况下，直接带入一些简单的数字可以得到：

当 $p = q = 0.5,$ $b = 1$ 时， $f^{*} = (pb-q)/b = 0$ ；
当 $p = 2/3, q= 1/3,$ $b = 1$ 时， $f^{*} = (pb-q)/b = 1/3$ ;
当 $p = q = 0.5,$ $b = 2$ 时， $f^{*} = (pb-q)/b = 1/4$ ;
当 $p = q = 0.5,$ $b = 1/2$ 时， $f^{*} = (pb-q)/b = - 1/2$ ; 此时不该下注。

从公式 $f^{*} = p - \frac{q}{b}$ 可以看出：

当 $p$ 增加的时候， $q$ 会减少， $f^{*}$ 也会增加，意思就是随着赢钱的机会加大，就该增加投注的比例；反之，当 $p$ 减少的时候， $f^{*}$ 也会随之减少，也就是说当赢钱的机会变小的时候，就该减少投注的比例。
当 $b$ 增加的时候， $f^{*}$ 会增加，意思就是说当赢钱率增加的时候，应该加大投注的比例；反之，当赢钱率减少的时候，应该减少投注的比例。
当 $f^{*}\leq 0$ 时，就表示这个游戏不值得投注，因为总资产的期望是负数。

一般形式（二）

除了赢钱率之外，在一般情况下，还有一个损失率的概念。也就是说，当投掷的硬币有偏差，并且同时有赢钱率和损失率的时候该怎么办？

假设

赌赢的概率是 $p$ ；
赌输的概率是 $q$ ；
赢钱率是 $b$ ，下注的资产会按比例增加，从 $1$ 变成 $1+b$ ；
损失率是 $c$ ，下注的资产会按比例减少，从 $1$ 变成 $1-c$ 。

一般情况下， $0\leq c\leq 1$ 。在这种情况下，函数 $g(f)$ 的形式又会发生微小的变化，

$g(f) = p\ln(1+bf) + q\ln(1-cf)$ .

直接计算可以得到： $Dg(f) = \frac{pb-cq-cbf}{(1+bf)(1-cf)}$ 。因此，临界点是 $f^{*} = \frac{p}{c} - \frac{q}{b}$ 。从公式上看，

当 $p$ 增加的时候， $q$ 会减少， $f^{*}$ 也会增加，意思就是随着赢钱的机会加大，就该增加投注的比例；反之，当 $p$ 减少的时候， $f^{*}$ 也会随之减少，也就是说当赢钱的机会变小的时候，就该减少投注的比例。
当 $b$ 增加的时候， $f^{*}$ 会增加，意思就是说当赢钱率增加的时候，应该加大投注的比例；反之，当赢钱率减少的时候，应该减少投注的比例。
当 $c$ 增加时， $f^{*}$ 会减少，意思是说当损失率增加的时候，应该减少投注的比例；反之，当输钱率减少的时候，应该增加投注的比例。
当 $f^{*}\leq 0$ 时，就表示这个游戏不值得投注，因为总资产的期望是负数。

结论

本文从简单的概率论常识出发，介绍了 Kelly 公式的初步概念。对此有兴趣的读者，建议读其它更有深度的文章。

Computer Science, 智能运维

浅谈机器学习的一些小众方向

October 6, 2018 zr9558 Leave a comment

随着 DeepMind 的 AlphaGo 在 2016 年战胜了李世石，“人工智能”这个词开始进入大众的视野。从那时起，不管是大型互联网公司还是初创企业都开始大规模招聘机器学习的相关从业者，无论社招的求职者还是校招的应聘学生都出现了大规模的增长。由于机器学习的人才短缺并且大量应届生涌入，以至于现在某些公司的校园招聘出现了算法工程师简历太多，并且移动端岗位，web 开发岗位的简历略有不足的情况，导致这些互联网公司甚至通过邮件的方式来呼吁应届生尽量修改投递职位。

字节跳动

就这几年的人工智能发展情况和笔者的个人经验而言，人工智能可以大致分成以下几个方向：

计算机视觉方向
自然语言处理方向
语音识别方向
机器学习方向

CV，NLP & Speech Recognition

计算机视觉方向（Computer Vision）无论是在学校还是在公司，都有着大量的从业者，并且 ImageNet 项目可以提供上千万的标注图片供大家使用。既然 ImageNet 是开源的数据集，那么无论是学校的教授还是学生，不管是大型互联网公司还是初创企业，都可以轻易地获取到这些数据集，不仅可以进行 CV 算法的研究工作，还可以进行相关的工程实践。由于计算机视觉方向的历史悠久，不管是计算机系，工程系，甚至数学系，都有着大量的老师和相应的学生从事该方向的研究工作，因此，学校或者研究所能够对工业界输出的计算机视觉人才数量也是可观的。

与计算机视觉方向相比，自然语言处理方向（Natural Language Processing）在学校里面也有不少的教授从事相关研究。不过要想让计算机理解人类的语言可不是一件容易的事情。尤其是中文还拥有多音字，语义双关等情形，而且理解中文很可能还要基于上下文来前后推敲。如果和聊天机器人聊过就会发现，其实聊天机器人和人类的聊天给用户的感觉是完全不一样的。语音方向笔者不是很了解，也只是道听途说而已，在这里就不在赘述了。

ImageNet

机器学习

除了以上三个方向，人工智能的另外一个研究方向自然就是机器学习了。在周志华老师的教材《机器学习》中，无监督学习，有监督学习，半监督学习，强化学习等方向都已经在该教材中进行了详细的解释。貌似几年前强化学习这个方向也是不温不火，但是在 AlphaGo 崛起之后，深度学习和强化学习就已经开始进入了大多数人的视野。随着围棋被攻克之后，德州扑克AI，或者其他的游戏 AI 也被很多学者和大型游戏公司所关注。DeepMind 也在 2017 年开放了星际争霸的研究平台，今年无论是在 Dota2 还是星际争霸上，游戏 AI 相比之前都有了巨大的突破。

starcraft2

除了强化学习之下的游戏 AI 之外，其实机器学习一直在一个领域发挥着巨大的用处，那就是推荐系统。无论是广告推荐，YouTube 视频推荐，甚至今年非常火的抖音 APP，推荐系统在其中的作用都不容忽视。关于推荐系统的书其实有很多，笔者也没有一一读过，不过就近些年的发展状况来看，无论是在学术界还是工业界，从零到一搭建一套推荐系统已经不是壁垒，如何搭建一套结合业务场景的优秀推荐系统才是难题。而推荐系统中常用的各种模型，例如逻辑回归（logistic regression），SVD，ItemCF & UserCF，甚至深度神经网络，在各种开源框架之下（Spark，Tensorflow等），只要拥有足够的计算资源，训练出一个可以使用的模型已经没有太大的难度。难度在于算法工程师如何贴近业务并且理解业务，在此基础上如何使用机器学习算法将内容库里面的优质内容推荐给用户，而不引起用户的反感，点击率如何在合理的范围内进一步提升。搭建一套推荐系统已经不是难题，如何结合多种多样的推荐场景才是关键，怎么结合业务来使用推荐系统则是算法工程师需要思考的问题。

Tensorflow

机器学习+安全业务

就笔者的个人经验来看，推荐系统或者游戏 AI 其实只是机器学习的一个应用领域。既然机器学习能够应用在推荐系统或者游戏 AI 上，那么为何不能够应用在别的领域上呢？

对于一些大型互联网公司而言，推荐系统能够给用户们带来足够优质的体验，游戏 AI 能够帮助玩家提升自己的技艺。但是在给用户带来优质体验的时候，总有一些黑产用户在伺机而动，通过 APP 的各种 bug 来寻找赚钱的机会，给正常用户带来各种各样的骚扰。在游戏中，有一些人使用了外挂等技术，破坏了游戏中的平衡。在金融行业中，一直都有黑产用户正在进行各种各样违法犯罪的事情，例如信用卡欺诈等，给正常用户带来了不少的损失。在社交网络中，有一些用户通过社交网络传播着各种各样的不良信息，无论是谣言，虚假广告还是各种各样的假冒伪劣产品宣传，都给正常用户带来了不好的体验。因此，安全业务一直是互联网公司和金融公司的重点业务，安全业务一直是保护着互联网公司能够正常运行的基石。各种各样的安全实验室在大型互联网公司里面并不罕见，也是必须要配备的力量。对于业务安全上，无论是盗号，刷帖，传播虚假消息等都是需要关注的对象。在黑产力量日益壮大的情况下，打击黑产的人力也越来越多。随着人力的增多，如何使用机器学习算法来进行人类经验的传承，或者说随着黑产技术的升级如何才能够尽快的提升互联网公司的黑产对抗能力，这些都是值得做的工作。除了互联网公司之外，银行等金融机构也需要进行信用卡的风控评级，打击信用卡盗刷，黑色产业的资金链条挖掘等。因此，银行等金融机构对于业务安全上面的要求有的时候可能比互联网公司还要严格。

黑客图片1

能够用在安全领域上的机器学习算法有很多，最容易想到的当然就是异常检测。无论是高维异常检测，还是图（Graph）上的异常检测，都在业务安全领域有着巨大的应用场景。异常检测算法可以从众多的数据中发现数据中的异常点，然后通过人工审核等方式进行数据的标注，并且可以使用有监督学习模型进行训练和上线预测。整体来说，就是使用无监督算法，有监督算法，图挖掘算法等机器学习常见技术来进行恶意黑产的打击工作。对于从事业务安全+机器学习方向的算法工程师来说有一些潜在的优势，那就是业务安全方向是工业界的刚需。但是学术界并不完全有能力培养相关的人才，因为互联网或者金融公司的数据都具有保密性，很难把数据像 ImageNet 一样开放给全世界，共同享受数据带来的巨大优势。如果没有基础的数据，那么学校的教授或者学生就无法接触到这个领域，也就无法在学校提升相关的技术。虽然异常检测等其他机器学习算法会在学术中有所突破，但是安全的业务经验只有在做过相关业务之后，真正地打击过黑产用户之后才能够有更深层次的体会和理解。一个没有接触过安全业务的人，即使他的学术造诣再高，在短时间内也是很难提出一些靠谱想法或者技术方案的。

机器学习+运维业务

在这里做一个不恰当的比喻来方便大家理解。

如果把 APP 比喻成一栋楼房的话，那么后台开发就是搭建钢筋水泥的人，前台开发就是负责刷墙贴砖的人，设计师是负责把这栋楼设计得更加美观的人，安全人员就好比楼房的保卫人员，那么运维人员就是这栋大楼的检修人员。

在一些互联网公司，运维人员也被称为技术运营人员，整体来说就是保障APP或者业务稳定运营的。例如：网络抖动了该怎么办，交换机何时宕机，大量用户无法登陆APP了该怎么办，APP的某个页面无法打开了该怎么办等诸如此类的问题。为了保障业务的稳定运营，就需要有一定数量的技术运营同事来维护整个业务的正常运行。正所谓“天有不测风云，人有旦夕祸福”，公司拥有安全人员和运维人员好比买保险，在没有黑客攻击或者业务正常运行的时候，通常存在感略低。但是一旦业务出了问题，第一个要召集的人肯定就是安全和运维人员。因此，无论是安全工作还是运维工作，都是大型互联网公司和金融机构必不可少的力量。

随着机器学习的发展，智能运维（Artificial Intelligence Operations），也就是所谓的 AIOps，也开始被众多技术公司所关注。提到技术运营工作，根据 2018 年的《企业级AIOps实施建议白皮书V0.6》 的观点，可以大致分成以下三个方向：

质量保障；
效率提升；
成本管理。

其中质量保障就是为了保证业务的正常，高效，稳定地运转。在质量保障的过程中，无法避免的就需要进行异常检测。在运维领域，异常检测的范围非常广，不仅包括大家耳熟能详的时间序列异常检测，还包括多维数据下钻分析，甚至还包括日志模板提取和异常挖掘。除了质量保障之外，效率提升也是一个方面，无论是自动化运维领域还是使用 NLP 的技术来构建智能聊天机器人，甚至使用机器学习等技术来进行智能扩缩容，机器学习技术在运维领域都有着巨大的发挥空间。

AIOps场景

在智能运维领域，最重要的任务之一就是时间序列异常检测，这里的时间序列不仅包括服务器的各种各样的指标（CPU，进程，PKG等），还有网络出入流量等交换机数据，甚至包括各种各样的业务指标（在线用户数，失败数，请求量等）。各种各样的时间序列组合在一起就形成了一个时间序列数据库，而且这些时间序列通常来说都是按照分钟量级来收集数据，因此，时间序列项目完全符合机器学习项目的各种条件。在时间序列异常检测或者趋势预测中，时间序列和机器学习，甚至深度学习结合的各种技术都可以在这里有着一定的用武之地。

timeseries

除了时间序列之外，服务器的异常挖掘，多维度数据分析都是智能运维中非常有挑战的项目。除了质量保障之外，效率提升中的智能聊天机器人将有希望把运维人员从繁重的客服任务中解放出来，智能扩缩容技术将有机会取代原来很多“拍脑袋”所做出来的容量估计。对于一家正常经营的公司而言，质量保障和效率提升只是其中的两个方面，如何有效地进行成本的管理则是非常重要的项目。如果成本预算过少，那么明年的项目发展将会受到限制；如果成本预算过多，那么明年的资源势必造成各种浪费。因此，无论是质量保障，效率提升，还是成本管理，都是技术运营领域的核心问题。

机器学习+其他领域

除了以上笔者接触过或者略微了解过的领域之外，其实机器学习在其他的领域应该都是有着自己的用武之地。在量化分析方向，据说有的团队已经开始用机器学习的方法进行股票交易。在化学或者生物学领域，也有学者使用机器学习的方法来挖掘数据之间的信息。总之，除了人工智能在那几个经典领域的应用之外，机器学习的方法应该有希望应用到各行各业中，改变原来的工作方式，提升原有学科的效率。机器学习本身并不是一个新的东西，只要运用得当，机器学习在各行各业都有着强大的创造力和生命力。

PHD的生涯, 互联网的生涯

25 岁做什么，可在 5 年后受益匪浅？

October 6, 2018 zr9558 Leave a comment

25 岁做什么，可在 5 年后受益匪浅？

很久之前在知乎上看到一个问题：“25 岁做什么，可在 5 年后受益匪浅？”

25 岁的时候

在写这篇文章之前先回忆一下自己在 25 岁的时候在干什么。

笔者在 25 岁的时候应该是 2013 年，正好是在 NUS 读博士的时候。当时笔者的科研进展缓慢，几乎处于无法自我推进的状态。而在笔者迷茫了大半年之后，碰巧在网上看到一本书叫做《战胜拖拉》，于是笔者花了几天功夫读完了整本书之后就将知识用于实战，目标是战胜自己长期拖延不科研的状态。不过花费了一段时间之后，效果比较明显，没花费多少时间就把当时论文里面的第一步 Real Bound Theorem 搞出来了。事后想起这件事情的时候，最感谢的就是《战胜拖拉》那本书的作者，作者在书中确实提供了不少有用的建议。在解决了毕业论文里面的重大难题之后，笔者写了两篇关于拖延症的文章，希望对大家有帮助。

”PHD 身边的时间陷阱“

”战胜拖延-让PHD达成每天必要的工作时间“

在看完拖延症的书籍并做完论文的第一步之后，当然要完成的就是论文的全部。在做科研的过程中整体来说还是比较辛苦，以至于读完博士之后还写了一篇文章来介绍科研整件事情，那就是”科研这条路“。

选择比努力更重要

所有的博士生在拿到博士学位之后自然就是面临就业的问题。笔者 2005 – 2015 年一直在数学系攻读学位，回顾读书这十年给笔者最大的感受就是，学校招聘老师的标准是越来越高。刚开始的时候，如果博士的学校较好，也许没有太多的论文都能够进一个还不错的大学。到了 2010 年之后，即使有了不少的论文也不能够保证一定能够进好大学。同时，博士生的数量也是越来越多，在学校的教师岗位根本无法容纳下那么多博士生的情况下，很多无法找到教职的博士生就要去企业工作或者继续从事博士后的岗位。不过有的专业找工作确实相对容易一些，有的专业找工作相对难一些。假设有一个博士生在 2010 年选择机器学习专业，那么在他毕业的时候，正好就是机器学习刚刚火起来的时候，那么肯定会非常容易就业。不过在 2010 年的时候，机器学习也不算什么热门方向，企业所提供的岗位也相对较少。因此，有的时候要想在未来获得更大的收益，选择当前热门的领域并不是一件很好的事情，选择未来有可能火的领域才是关键。不过要想判断未来哪个领域会火实在是太难了。因此，选择比努力重要的多，无论是整个大的行业，还是研究方向，甚至到每天手上所做的那件事情。

自我的成长

在选择了一个合适自己的方向之后，那就要去努力做这件事情，无论是在上学的时候，还是工作的时候，都要时刻注意自己的产出。在学校的时候，学生需要注意的就是这半年需要做什么，能够达到的目标是什么。然后从后往前反推此刻应该做什么，需要做什么样的事情才能够达到相应的结果。比如，如果在开学的时候就想要在期末考试的时候获得一个不错的成绩，那么在开学的时候不仅要下定决心学好这门课，还要根据课程的实际情况制定出相应的学习计划，最后才能够在期末考试中获得相应的成绩。又比如，如果目标是半年后写一篇论文，那么就需要准备开题报告，论文规划和预期效果，以及相应的时间节点。但是做论文的时候最大的风险点在于不确定性，所以很多时候需要根据论文的实际情况来进行调整。如果是在公司里面的话，通常来说都是季度考核，半年考核，全年考核等几个大的阶段。而且在项目的不同时期，考核的方式也是截然不同的，在项目的初期，可能也只是需要有一些调研方向和小的产出；在项目的中期，可能就需要有阶段性的成绩；在项目的后期，可能就需要把整个项目进行回顾，然后总结成功点和失败点，再让所有项目组成员来学习成功点，总结失败点，避免在未来的项目中走同样的弯路。其实无论是在学校里面还是在公司里面，“项目管理”这类知识还是挺有用的，在学校的时候可以用来管理自己的学业，在公司的时候可以用来管理项目的进展。

工作的意义不仅仅在于获得一份工资，有可能的话最好从工作中获得一定的自我认同感，更重要的是获得个人的持续成长。刚开始进入公司的时候，由于是新人，所以可以学的东西其实非常多。无论是专业技能，业务沟通，还是项目管理，每一个领域都够一个新人学一段时间。因此，在刚进入公司的时候，需要给自己一定的压力，前一年半其实是个人成长最快的时候，在这个时候最好需要充分利用上下班的时间，甚至周末最好也花一定的时间进行自我充电。而到了两年之后，成长的速度就会明显放缓很多，感觉每隔半年才会成长一点。

专业的问题

在学校的时候，通常学生都只会关注本专业的知识，只有遇到了想转行的时候才会去主动学习别的学科。但是在工作的时候，如果只想做本专业的知识，那么在其实就是在限制自己的发展空间，千万不要让自己的专业限制了自己的发展。无论是在学校还是工作中所学到的经验是一种财富，但是这些经验在有的时候也会形成自己的绊脚石。一般来说，在工作中做一些相对成熟的事情是容易出成绩的，做未知的事情是需要承担风险的。在做成熟事情的时候大家都会采用已有的方案继续做下去，在做未知事情的时候就需要有人去做很多的调研工作，看看这件事情是否值得做下去，是否能够达到预期的收益效果。如果调研了之后确实能够达到预期的效果，那就值得做下去；如果有一定的风险，那就要把预期降低，在一个合理的预期之内做适当的事情。

明确不想做的事情

可以在学校期间明确一下自己不想做的事情。通常来说，你问别人，你想做什么，他能够七七八八的说出一堆，但是绝大部分都不会去做。而且随着时间的迁移，每个人的想法都会产生变化，今年想做的事情明年不一定想做。但是就一般情况而言，一个人不想做的事情是不会发生太大变化的。如果一个人不喜欢学习物理，那么十几年过去之后可能还是这样；如果一个人不喜欢写作，那他肯定也很难提起自己的笔去认认真真地写一篇文章。所以，可以在学校或者工作的时候确定自己不喜欢做什么事情，然后在选择专业或者就业的时候避开这些专业或者岗位。因为在学校里面会与这些专业相伴几年，而工作的时候在岗位的时间有可能比在家的时间还要多。

PHD的生涯, 互联网的生涯

不要为已经打翻的牛奶而哭泣

September 27, 2018 zr9558 Leave a comment

当年，曹操与刘备在汉中决战，两军久久僵持不下。曹操见久攻不下，心中烦闷，此时士兵来询问夜间的口令，曹操顺口说一句：“鸡肋。”而主簿杨修听到这句话，便开始收拾行装，并告诉周边的人一起收拾行装。众人不解，反问之，杨修解释道：“鸡肋鸡肋，食之无肉，弃之有味，今丞相进不能胜，恐人耻笑，明日必令退兵。”而杨修因为这句话而引来了杀身之祸。

三国1

熟读三国演义的人都知道，曹操杀了杨修之后，便令众军前进。其实到了最后，曹操也未能战胜刘备，获得汉中攻略战的胜利，只能退回许昌。虽然现在我们很难猜测曹操当时的想法是什么，不过“夫鸡肋，弃之如可惜，食之无所得”这句话却由于这个故事而流传下来。无论是当年的曹孟德，还是现在的很多平凡的普通人，身边总有一些事物与鸡肋一样，食之无味而弃之可惜。

在经济学中可以用沉没成本来描述鸡肋这个概念。沉没成本指的是已经付出了，但是不能收回的成本。例如，有一家电影院不允许顾客退票，有位顾客买了一张电影票，但是他看了半小时的电影之后觉得电影十分难看，这种时候他就有两种选择：

1. 继续看下去；

2. 中途离场，去做自己想做的事情。

其实绝大多数的人都会忍着看完这部难看的电影。而从经济学上的观点来看，如果人是足够理性的，当这个人在做决策的时候，是应该把沉没成本放在一边而不去考虑的，因为沉没成本是无法被改变的。按照上面的例子，无论他选择是否继续看下去，这个电影票的钱都已经无法退回，而此时需要做决定的事情是是否继续看完电影。通常这种情况下，按照经济学的理论来说，经济学家会建议这个人选择中途离场，去做任何自己想做的事情。因为这样的话他只是浪费了一张电影票的钱，但是省下来的时间却可以做其他更有趣的事情。

COSTS

虽然这只是书本上的一个简单例子，但是这样的例子在生活中比比皆是。无论是对学生还是职场人士，无论是对普通人还是位高权重的决策者，都面临着沉没成本是否放弃的难题。对于学生而言，最常见的情况就是这个学生在大学期间学了四年根本不感兴趣的专业，但是在面临存在转专业的机会时，是否要放弃原有的技能而重新学习一个新的专业便成为了一个难题。对于在职人士而言，在面临一个有挑战但是并不熟悉的行业或者领域的时候，是否愿意放弃原有的一些经验，是否存在勇气进入一个新的领域也是一个难以抉择的问题。

沉没成本其实很影响一个人的决策。对于学生而言，如果在某个方向上花费了巨大的精力和时间，是很难下定决心转一个全新的方向的；对于工作后的人士而言，主动放弃已经拥有的一些经验，放弃已经掌握的一些人脉和资源，也是十分困难的。但是，在人生的十字路口，其实又必须要下定决心做一些事情。众所周知，学校里面的不少专业其实就是“鸡肋”，完全符合“食之无味，弃之可惜”的条件，无论是学生的就业率和成材率都处于所有专业的底部。如果这些专业的学生不放弃自己的专业，将会在这些专业里面越陷越深，最终无法自拔。其实，这些专业的学生继续从事该专业的学习都不能称之为“坚持”，而是在“死扛”，用自己的大好前途来耗费在一些没有任何用处的专业技能上。有的技能虽然看上去比较高大上，但实在是“屠龙之技”，离开了已有的圈子，学校之后就再无任何用武之地。这些专业还能继续招生的原因大概就是学校招聘了不少这些专业的教师。因此，对于这些专业的学生而言，不破不立，只有勇敢地走出自己所在的圈子，才能够体会到其他专业的精妙之处。

CHOICE

而对于职场人士而言，基本上都会想靠一些好项目来升职加薪，但是在整个社会的大环境下，有的方向确实是在走下坡路，行业越来越饱和，竞争越来越激烈，所做的技术难度越来越低。随着技术的发展，原有的一些技术和框架都会逐渐被淘汰，掌握的技能价值也会越来越低，甚至可能出现找一些应届生培训几个月之后就能够达到老员工的水平。在这种情况下，随着行业的整体下滑，如果还抱着原有的技术栈不松手，那只能变得越来越没有竞争力。在这种情况下，就要主动寻求突破，寻找自己所拥有的技能和其他专业的共同点，将自己的技能主动地迁移到更有潜力的方向上。在职场上，一定不要死抱着一个东西不放手，一定不要抱着我就是来做这个方向的想法，而其他的方向都不去了解和尝试。在工作中，应该审时度势，创造或者寻找优质的项目和资源，因为一个有潜力的项目和优质的资源所能够带来的好处有的时候会远远大于自己当年所做的方向，那个自己当年不舍得放弃的方向。

上升通道

整体来说，在一个人面临着决策的时候，沉没成本最会影响一个人的决策。无论是从经济学的原理上来说，还是从日常经验上来讲，其实都应该放下包袱，轻装上阵，寻找一个更有前景和前途的方向去发挥自己的特长。

Nanjing University

梦回金陵：南京大学（一）

September 23, 2018 zr9558 Leave a comment

笔者从事数学研究大约有十年的期间，后面五年是在新加坡国立大学度过的，而前面的五年则是在南京大学度过的。之前写过不少文章介绍新加坡国立大学的点点滴滴，感觉有必要回忆一下笔者在南京大学的一些事迹。虽然已经时隔多年，但是在南京大学的时候其实还是有许多有趣的人和有趣的事情，也许有一些事情已经不太记得清楚，但是在南京大学度过的五年生活也许是人生中最美好的五年。

梦回金陵1

近二十年来，中国的高校都在发展，学生和老师的人数都随着时间的迁移而越来越多，老校区毕竟面积有限。于是在 1993 年的时候，南京大学浦口校区开始接收第一批新生。在 2005 年笔者刚入学的时候，南京大学的浦口校区已经走过了 12 年的历史。而作为老校区的鼓楼校区则依旧保持着几十年前的景色，无论是校长办公室的北大楼，还是数学系的西大楼，都见证了南京大学的发展和变迁。当年，南京大学只有鼓楼校区和浦口校区，仙林校区还没有对外开放。因此，在 2005 年前后，几乎所有专业的大四学生和研究生都在鼓楼校区，而大一大二大三的学生一般都会在浦口校区。梦回金陵2 梦回金陵6

由于南京的地理位置原因，鼓楼校区与浦口校区相隔很远，每次进城购物或者买东西的时候，总是要跨越南京长江大桥。而当年浦口地区还没有通地铁，当年南京唯一的一条地铁就是一号线，如果没有记错的话大概是从火车站到奥体中心。跨越南京长江大桥的办法除了靠双腿走过去之外，还可以选择坐公交 131 路或者 159路。131 路公交当年是开到大桥南路的家乐福店，而 159 路则是开到南京火车站附近。如果浦口大学的学生们只是去大超市买点东西的话，其实大桥南路的家乐福店是一个不错的选择，所以当年很多时候笔者都是乘坐 131 公交去家乐福。不过由于当年的交通工具实在是不方便，每次乘车的时候都是人山人海，要和其他同学一起挤上车，而且每到周末或者节假日的时候，更是人满为患。

梦回金陵3

虽然说当年的浦口校区距离市区非常远，但是学校里面该有的设施基本上还是有的。当年有三个大食堂，分别是六七八号食堂，随着时间迁移，到了大三的时候，九食堂就已经修好并且对外开放。让人印象深刻的是由于当时上泛函分析课程的地点是在西平教室，并且是早上的三四节课，为了避免在 12 点钟的时候在食堂排长队，于是趁着三四节课课间休息的十几分钟就可以冲去九食堂吃饭，然后迅速返回教室。除了食堂之外，当年的浴室是公共浴室，在宿舍只有凉水，于是如果要去洗澡的话，就必须去浦口大学的公共澡堂。而浦口大学的公共澡堂位于当年的八食堂附近，每天下午 14:00 左右开门，晚上 21:00 左右结束。南京素有火炉之称，每逢夏天的晚上，女浴室的门口总是排起了长龙，排队洗澡的人群总是络绎不绝。而男浴室的门口则没有那么多人，一是因为男生洗澡的速度通常比女生快很多，二是有不少的男生会选择在宿舍里面洗冷水澡。

梦回金陵5

在 2005 年左右，当年的手机还是 Nokia 的时代，移动端的娱乐方式并没有现在那么丰富。大家的娱乐方式通常来说就是聚在一起打扑克，或者在一起玩电脑游戏。当时比较风靡的单机游戏是暴雪公司开放的魔兽争霸，网络游戏也是该公司开发的魔兽世界。而大一的时候，绝大多数人还没有拥有自己的个人电脑，于是为了玩这些游戏通常都只能够去浦口大学门口的多瑙河网吧，因此一些人就出现了白天上课，晚上包夜的情况。也许是刚20岁出头的年纪身体比较好，到了30岁左右的时候，想通宵熬夜就是一件很困难的事情了。有趣的是，当时一个宿舍会有四个人，一旦有一个人开始打游戏，通常都会带动整个宿舍的人一起玩。

梦回金陵7

而学生的想象力总是无穷的，总能够挖掘身边无数的资源，变腐朽为神奇。除了浦口大学门口的多瑙河之外，其实学校内部也有机房。当年大一的时候，数学系总会开设 C++ 编程设计这门课，既然是编程课，那么就需要上机实验，因此玉辉楼的数学系机房就是一个还不错的环境。不过既然是机房，那么它的硬件设施就肯定没有外面的网吧好。但是，机房总是免费的，于是就有一些同学会选择在机房玩一些小游戏，当年的几十台机器还是能够择优选择出几台机器可以运行 Diablo II 的。

梦回金陵8

除了数学系的机房之外，其实还有另外一个地方提供了不少的电脑。对于南京大学的绝大多数学生，数学和英语是两门必修课。既然是学英语，那无法避免的就是听说练习，为了提供必要的听说训练，南京大学在教学楼的三区五楼提供了一块场地，叫做大学生英语学习中心。当年刚入学的时候，每个学生都要进行一次入学考试，目的就是把每个学生的英语能力进行分级。总共分了四级。其中，四级的能力最高，只需要上一个学期的英语课；一级的能力最差，要上四个学期的英语课。不过作为贵州出来的学生，英语通常都不会太好，于是就只能够混到二级，上三个学期的英语课。既然是要上课，就无法避免地要做作业和考试。而当年做作业的方式就是在大学生英语学习中心做，学习某门课程之后，然后在机房里面做阅读理解和听力测试。而当时做作业的时候是限时的，必须要在一个合适的时间内完成相应的题目才算及格，而这些作业就算平时的作业成绩了。记得当年考试的时候，考试的题目有一部分就出于书本里面，只要熟记书本里面的内容，虽然不能够保证得高分，但是能够保证自己顺利地通过考试。

梦回金陵10

作为数学系的学生，通常来说学业压力都比较重，一般来说只靠课堂上的时间是无法学好数学的，需要在课下花费很多的时间和精力去学习和巩固已知的课程。而在宿舍几乎就没有办法去学习，毕竟宿舍是提供住宿的地方。而当年浦口大学没有图书馆，图书馆是在2007年左右才建立起来的，在05年左右的图书馆是临时搭建的，属于过渡期。于是，能够提供自习的场所就只剩下了教学楼，西平，南平。西平教室当年是给金陵学院的，南平教室的环境也比较恶劣，就只有教学楼的环境还可以。不过教学楼整体来说也不小，八角楼附近的人比较多，于是为了寻找一个相对安静的环境，通常都会去一区五楼的教室自习。教学楼一区的人数相对偏少，而教室偏多，五楼又是一个比较高的地方，于是自习的人数是最少的。

梦回金陵11

（未完待续）

PHD的生涯, 互联网的生涯

授人以渔—从博士生和新员工的成长谈起

September 22, 2018 zr9558 Leave a comment

众所周知，无论是在学术界还是工业界，所有的人都是从新手开始，一步一步地走向正轨。如果想在高校谋得一个教授的职位，所有的人都是从本科开始，然后到 Master 阶段，最后走向 PHD 的漫长时期。即使拿到了博士学位，也就是一个预备军的阶段，相当于获得了一个学术界的入场券。通常来说，在获得了博士学位之后，通常还需要一段时间的博士后工作经历，才有可能在学术界谋得一席之地。在工业界，除了少数大牛之外，几乎所有的人都是从底层干起，一年一年的升级打怪，最终获得职位上的晋升。作为一个在学术界和工业界都混过几年的人，在这两个地方都踩过不少的坑，这几年也看到周边的同学在学术界上的分别走向不同的道路，身边的同事也在工业界上作出各自的选择。近期正值博士生开学和新人入职的时期，正好有一些个人的感悟跟大家交流一下。

循序渐进

对于一个在读博士生来说，如果最终想留在学术界工作，并且在高校或者研究所谋得一个讲师或者教授的职位，那么博士期间的工作就显得至关重要。对于一个博士生而言，博士期间的课题通常来说都是导师帮忙定下来的，从一开始的课题收集，开题答辩，整理思路，撰写论文，导师在其中将会发生着至关重要的作用。选择的课题好坏直接决定着博士生最终的产出和收益。其实，要想让一个博士生做不出来课题是非常容易的，直接让他去攻克 Riemann Hypothesis 就可以了，但是这样做并没有任何的意义。导师的作用是培养一个又一个合格的博士生，让其所在的研究方向能够逐渐壮大，从而在国际上处于领先地位。如果让博士生去攻克 Riemann Hypothesis，不仅没有任何好处，也会对博士生造成毁灭性的打击。在博士生刚入学的时候，导师要根据自己的多年以来的工作经验，给博士生选择一个能够出成绩，但是又不是特别难的课题，而不是给学生一个本方向的终极难题。只有这样，博士生才能够在最终答辩和找工作的时候占据一定的优势，并且也有机会在学术界存活下来。

即使选择了一些合适的课题，也不能够让博士生从正面直接攻克它。因为最终的问题可能还是相对偏难一些，对刚进入博士阶段的 PHD 来说可能并不合适。在这种时候，需要采取循序渐进的策略。就拿笔者之前所研究的动力系统方向来举例，刚刚开始攻读博士的时候，尤其是在前两年，只需要做一个 Ergodic Theory and Dynamical Systems 这种级别的论文就可以了。因为这种时候需要的是稳定军心，让 PHD 能够有信心继续从事一些更难的课题。在博士生第三年至第五年的时候，尽量去做一个更难一些的题目，然后其博士论文的课题大致能够发表在 Communications in Mathematical Physics 这种级别上。这样的话，博士生寻找一个博士后岗位甚至一个教职都没有太大的问题。在找到了工作之后，通过会有两种选择，一是可以继续做之前的课题，保持一个持续的领先优势，二是可以做更难一些的问题。如果能够有持续的小论文产出，并且最终有一个大论文的话（例如发表在 Annals of Mathematics）上，基本上 Tenure 之路已经接近稳妥。整体来看，在博士生期间最好的策略是选择一个循序渐进的过程，而不是想一口气吃成一个胖子，给了一个超难的课题让博士生自生自灭。

对于刚刚工作的人也是一样的道理，无论是实习生还是刚入职的应届生，在公司层面都会制定一个所谓的“师傅”或者直系领导帮忙带一下。对于实习生而言，其实他们在公司里面的工作时间也就两三个月，并且最终会面临一个实习生考核，来决定是否录用。在这种时候，如果是想当一个负责任的老员工，在这种时候就一定要给实习生一个相对容易出成绩的项目。而这种项目则不能是那种很难的长期项目，但是与长期项目又需要有某种千丝万缕的联系，最好就是长期项目所需要的核心部分。老员工需要做的就是把这一部分内容从整个项目中剥离开，该准备的数据，该搭建的工具环境都需要提前准备好。只有这样，实习生才能够在一个相对紧凑的时间段内迅速的出成绩，然后最终产出的时候获得一个不错的成绩。

融入圈子

无论是在学术界还是在工业界，都强调一个圈子的概念。在学术界选择导师的时候，就好比足球运动员选择各种各样的俱乐部，有的俱乐部可能比较大并且人才济济，有的俱乐部可能比较小但是却很有发展潜力。在进入了这个俱乐部的时候，导师除了需要把必要的论文资源和材料，相应的方向指导清楚之外，其实最重要的就是带领学生们进入这个圈子。可以通过举办一些学术会议的方式，让学生们去参加，并且主动结识同行中优秀的人才。也可以通过开讨论班的方式，让博士生主动认识院系里面的各位大佬。其实，在未来找工作或者教职的时候，不仅是需要老板的推荐信，还需要同行们的一些评价和建议，甚至由同行大佬们提供一个岗位。因此，提前融入相应的圈子对于一个博士生来说非常重要。在这种时候，导师需要做的就是主动把自己的学生介绍给自己的学术界朋友认识，说不定在互相交流的过程中会有一些灵感出现，对学生做论文也是有益无害的。而且导师也是有着自身的局限性，不可能在学术领域里面面面俱到，这种时候，如果有同行的协助，那么对学生的成长方面则是会很有益处的。整体来看，主动帮博士生寻找必要的资源则是一个合格的导师应该做的事情。

如果是对于公司里面的新员工或者实习生来说，很可能面临的事情就是项目无法推动，无法在团队内部找到资源。这种时候，如果没有老员工一些必要的协助，实习生或者新员工将会举步维艰。因为公司里面的代码，架构，技术很可能散落在各个地方，文档的管理建设方面也未必特别合理。这种时候，只有老员工才知道哪里有坑，哪些人能够解决哪些事情，哪些人能够提供相应的资源。这些是新员工无法预先了解到的事情。如果是一个合格的师傅，就需要及时了解新人在做项目过程中所遇到的困难，所需要寻找的资源和技术，然后协助新人去寻找相应的资源，把项目整体推动下去。在一些集体活动方面，也需要帮助新人主动地融入团队的圈子，避免出现新人被孤立的情形。

避免坑人

无论是在学术界还是工业界，都存在着导师坑博士生，老员工坑新员工的情况。在公司里面，老员工和新员工可能还存在某种竞争关系，因此会出现老员工不太愿意教新员工的情况，甚至主动坑新人的事情。有的时候可能是因为老员工的能力不太行，自己无法开疆拓土，只能靠坑新人来拉开自己和新人之间的差距。有的时候是因为老员工不愿意把自己的核心技术告诉新员工，担心新员工有朝一日取代自己。其实，是否主动教人是完全自愿的，这个看每个人的性格和具体情况来定，但是在团队内部，如果主动坑新人就是老员工的不对了。老员工可以不主动传授别人知识，但是万万不能主动坑害新人。所有的人都是从新人阶段逐步走过来的，如果在项目中老员工发现了一些坑，那么有的时候是需要主动告知新人，避免犯同样的错误。而老员工在一些时候，则需要给新人一些独立成长的机会，让新人能够在项目中获得相应的成长，只有这样，才能够最终独当一面，在未来成为一个合格的员工。

无论是导师在学校带博士生，还是老员工在企业里面带新员工，整体来说，如果新人比较靠谱的话，对导师或者老员工来说其实是有相应的收益的。无论是学术界还是工业界，其最终的目的都是使得课题越做越好，发的论文档次越来越高，项目的收益和技术影响力越做越大。

时间序列, 智能运维

基于自编码器的时间序列异常检测算法

September 19, 2018 zr9558 1 Comment

随着深度学习的发展，word2vec 等技术的兴起，无论是 NLP 中的词语，句子还是段落，都有着各种各样的嵌入形式，也就是把词语，句子，段落等内容转换成一个欧氏空间中的向量。然后使用机器学习的方法来进行文本的聚类和相似度的提取，甚至进行情感分类等操作。那么在表示学习（Representation Learning）方向上，除了刚刚提到的自然语言之外，语音，图像，甚至图论中的Graph都可以进行嵌入的操作，于是就有了各种各样的表示算法。既然提到了表示学习，或者特征提取的方法，而且在标注较少的情况下，各种无监督的特征提取算法就有着自己的用武之地。除了 NLP 中的 word2vec 之外，自编码器（Auto Encoder）也是一种无监督的数据压缩算法，或者说特征提取算法。本文将会从自编码器的基础内容出发，在时间序列的业务场景下，逐步展开基于自编码器的时间序列表示方法，并且最终如何应用与时间序列异常检测上。

自编码器

AutoEncoder3

提到自编码器（Auto Encoder），其实它就是一种数据压缩算法或者特征提取算法。自编码器包含两个部分，分别是编码层（encoder）和解码层（decoder），分别可以使用 $\phi$ 和 $\psi$ 来表示，也就是说：

$\phi: X\rightarrow F,$

$\psi: F\rightarrow X,$

$\phi,\psi = argmin_{\phi,\psi}||X-(\psi\circ\phi)X||^{2},$

其目标函数就是为了拟合一个恒等函数。对于最简单的情况，可以令 $X = \mathbb{R}^{n},$ $F=\mathbb{R}^{m}$ ，并且编码器和解码器都是前馈神经网络，也就是说：

$z = f(Ax+c),$

$x'=g(Bx+d),$

损失函数就是 $L(x,x')=||x-x'||^{2} = ||x-g(Bf(Ax+c)+d)||^{2},$ 其中 $x\in X=\mathbb{R}^{n},$ $z\in F =\mathbb{R}^{m}.$ $f$ 和 $g$ 分别是编码层和解码层的激活函数， $A,c$ 和 $B,d$ 分别是编码层和解码层的矩阵和相应的向量。具体来说它们的矩阵大小分别是 $A_{m\times n}, c_{m\times 1}, B_{n\times m}, d_{n\times 1}.$

AutoEncoder2

对于自编码器而言，它的输入层的维度等于输出层的维度，隐藏层的维度是需要小于输入层的维度的。只有这样，自编码器才可以学习到数据分布的最显著特征。如果隐藏层的维度大于或者等于输入层的维度，其实是没有任何意义的，具体的解释可以参考下面这个Claim。

Claim. 对于自编码器而言，其中隐藏层的维度 $m$ 一定是要小于输入层的维度 $n$ 的。

Proof. 如果 $n=m$ ，那么令 $A=B=I_{n},$ $c=d=0,$ $f=g=id$ 就可以得到一个自编码器，而这个自编码器对于提取特征没有任何的意义。同理，当 $m>n$ 时， $A$ 是一个 $m\times n$ 矩阵， $B$ 是一个 $n\times m$ 矩阵。从线性代数的角度来看，有无数个矩阵 $A, B$ 满足 $BA=I_{n}$ 。这种情况下对于提取特征也是没有意义的。而当 $m<n$ 时，其实无法找到矩阵 $A,B$ 使得 $BA=I_{n}.$ 如果存在 $BA=I_{n},$ 那么

$n = rank(I_{n})=rank(BA) \leq \min\{rank(A),rank(B)\} \leq \min\{m,m\}=m.$

这就导致了矛盾。因此，只有在 $m<n$ 的情况下提取特征才是有意义的。

对于自编码器而言，其本质上也是一个神经网络，那么它的激活函数其实不仅可以选择 sigmoid, 还可以使用 tanh，ReLU，LeakyReLU 等其余激活函数，其本质上都是为了拟合一个恒等变换，中间层则作为一个特征提取的工具。在训练的时候，同样是使用反向传播算法，可以使用不同的优化函数，例如 SGD，Momentum，AdaGrad，RMSProp，Adam 等。

在图像领域，有学者尝试使用自编码器来进行图像的重构工作，图像的特征提取等内容，整体来看也能达到不错的效果，请看下图：

AutoEncoder1

从上图来看，基于均方误差的自编码器是无法重构出乒乓球的。由于该自编码器的容量有限，目标函数是均方误差，因此自编码器并没有意识到乒乓球是图片中的一个重要物品。

时间序列异常检测：

时间序列异常检测一直是学术界和工业界都关注的问题，无论使用传统的 Holt-Winters，ARIMA，还是有监督算法进行异常检测，都是统计学和传统机器学习的范畴。那么随着深度学习的兴起，是否存在某种深度学习算法来进行异常检测呢？其实是存在的。请看上图，左边一幅图有一个白色的小乒乓球，但是随着自编码器进行重构了之后，白色的小乒乓球已经在重构的图像中消失了。那么根据异常检测的观点来看，小乒乓球其实就可以作为图片中的异常点。只要在图片的局部，重构出来的图片和之前的图片存在着巨大的误差，那么原始图片上的点就有理由认为是异常点。

在这个思想下，针对时间序列异常检测而言，异常对于正常来说其实是少数。如果我们使用自编码器重构出来的时间序列跟之前有所差异的话，其实我们就有理由认为当前的时间序列存在了异常。其实，简单来看，基于自编码器的时间序列异常检测算法就是这样的：

原始时间序列

-> Auto Encoder（Encoder 和 Decoder）

-> 重构后的时间序列

-> 通过重构后的时间序列与原始时间序列的整体误差和局部误差来判断异常点

简单来说，只要输出的时间序列在局部的信息跟原始的时间序列不太一致，就有理由认为原始的时间序列存在着异常。

那么，首先我们需要提取时间序列中的一些子序列，例如我们可以提取今天（today），昨天（yesterday），一周前（week）的数据，基于同样的时间戳把它们重叠在一起，也就是下图这个形式。其中，蓝线表示一周前的数据，黑线表示昨天的数据，红色表示今天的数据。

AutoEncoder4

基于一条很长的时间序列，我们可以提取它的很多子序列，从而构造出很多的片段序列。这些片段序列就可以形成自编码器的输入数据，而自编码器是模拟一个恒等变换，因此它会把有异常的点尽量磨平，而正常的点则保持原样。所以，通过大量子片段来进行训练数据的输入，自编码器就能够得到一个较为合理的权重。得到了一个训练好的自编码器之后，对于任何一个子片段，都可以重构出一个新的片段。例如上面的子片段就可以重构成下图：对于今天的数据（today），那个凸起被直接抹平；对于昨天的数据（yesterday）而言，那个凹下去的部分也被磨平。基于时间序列重构前和重构后的数据差异，可以获得时间序列的异常点。

AutoEncoder5

除此之外，还有很多时间序列的异常点可以被自编码器（AutoEncoder）发现，例如下面四幅图，无论是上涨，还是下跌，其实都可以被自编码器（AutoEncoder）发现异常。

总结

通常来说，在时间序列异常检测场景中，异常的比例相对于正常的比例而言都是非常稀少的。因此，除了有监督算法（分类，回归）之外，基于无监督算法的异常检测算法也是必不可少的。除了 HoltWinters，ARIMA 等算法之外，本文尝试了一种新的异常检测算法，基于深度学习模型，利用自编码器的重构误差和局部误差，针对时间序列的异常检测的场景，初步达到了一个还不错的效果。这种方法可以用来提供部分异常样本，加大异常检测召回率的作用。但是这种方法也有一定的弊端：

从理论上说，它只能对一个时间序列单独训练一个模型，不同类型的时间序列需要使用不同的模型。这样的话，其实维护模型的成本比较高，不太适用于大规模的时间序列异常检测场景；
对周期型的曲线效果比较好，如果是毛刺型的数据，有可能就不太适用；因为长期的毛刺型数据就可以看成正常的数据了。
每次调参需要人为设置一定的阈值，不同的时间序列所需要的阈值是不一样的。

参考文献

Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications, Haowen XU, etc., 2018
Deep Learning, Ian Goodfellow, etc., 2016
https://zr9558.com/2016/06/12/replicator-neural-networks/

PHD的生涯, 互联网的生涯

短板与长板理论

June 10, 2018 zr9558 Leave a comment

之前听说过一个木桶理论：“一个木桶能够装多少水，取决于最短的一块板”。这个理论听上去确实很有道理。在高考的时候，如果一个学生的英语只能考 20 分，那么即使其他课程都是满分，也是上不了最好的学校的。反之，如果一个学生的每门课都很好，即使他没有达到每科顶尖的水平，在填写高考志愿的时候也是会比前者能够选择得更多。因此，在高中的时候，老师们都会奉劝大家不要偏科，因为在高考的大环境下，过度的偏科确实没有太大的好处。

后来念了大学和研究生，发现在一个知识爆炸的时代，在一个人的精力实在是有限的前提下，实在是无法做到面面俱到。即使在数学专业，几乎也无法做到一个人精通数学的所有领域（当然精通本科数学课程那种程度实在是不能算）。一般来说，研究分析和研究代数的就是两拨人，这两拨人的技能点和兴趣点都不太一致。在数学界尚且如此，更不要说跨行业的精通了。就像在企业里面，很难找到一个前端，后台，设计，机器学习统统都精通的人（不是说找不到，而是非常稀缺）。在这种情况下，每个人都面临着选择，是选择做一个全栈工程师，还是一个只精通一个领域的人。

如果选择做一个什么都会做，面面俱到的人，首先就要跨领域的多学习各种东西，例如前端，后台，机器学习等等。在精力上就要像高考的时候一样做到相对均衡的分配，在每个领域都需要有所涉及。这样的好处就是什么样的活都能干，如果团队里面暂时缺少某个领域的人，这类人就可以及时补上，能够把项目顺利完成。这类人在就业的时候选择面也会广一些，因为他们什么任务都能够做。而且很多时候，在团队里面确实需要一些这样的人才。但是这类人才可能也会有一些问题，那就是精力会相对分散。毕竟研究的面广了之后，研究的深度可能就要打折扣。不过，这件事情也是因人而异的，毕竟人和人之间是不一样的。

如果选择做一个精通某个领域的人，那么他的精力就会相对集中。在同等智力条件下，他所研究的深度就会比面面俱到的人所研究得深。说句实在话，在知识爆炸的时代，即使是人工智能领域，其实也很难做到样样精通。例如，自然语言处理所使用的技巧和方法与图片处理所用的方案是有一定的区别的，在推荐系统上所使用的技术到了运维系统上可能就不能生效。在这种时候，如果企业要解决某个业务难题，无论是防止黑客攻击还是做一个智能运维系统，都会聘请一个在这些领域有过相关经验，并且在业界有一定知名度的人才来帮忙解决这个问题。一般来说，在这种时候不太可能选择一些没有相关工作经验的人来重新培养，因为一来成本太高，二来无相关工作经验的人可能也无法胜任这类工作。总之来说就是风险太大。

就普通成年人而言，一般都有着自己的工作习惯和专业技能。如果一个人的学习能力还可以，那么就可以把他已掌握的技能迁移到其他类似的领域去；但是却很难去让一个成年人进入一个他完全不了解的领域。如果进入一个完全陌生的领域，一来重新学习新的技能成本太高，二来放弃自己所掌握的技能是一件很困难的事情。所以，有的时候这个人能否做不同类型的工作就看此人是否具备技能迁移的能力了。

整体来说，做通才或者专才看的是这个人的性格和能力，每个人都需要根据自己的实际情况作出最适合自己的选择。在精力充足的情况下，可以选择多学习一些方向，掌握不同的技能点；在精力有限的情况下，不如根据自己的兴趣爱好，选择一个最擅长的领域做下去，然后在这个领域形成自己独有的竞争力。

PHD的生涯, Singapore

在新加坡的这五年—生活篇（二）

June 10, 2018 zr9558 1 Comment

上一篇文章《在新加坡的这五年—生活篇》已经整体介绍了新加坡的衣食住行，本篇文章将会回顾一下个人在新加坡遇到的有趣的人和有趣的事情。

新加坡国立大学（National University of Singapore）的 PHD Research Programme 的项目是其实是专为博士生量身定做的。虽然是博士生的项目，但是在刚入学的时候其实不能够被当做博士生，基本上和国内的硕士生没啥区别。因为 PHD Research Programme 里面有一项无法避免的内容，那就是修满一定的学分，而在不同的院系有着截然不同的修课标准。就数学系的博士毕业标准而言，那就是在四年时间内修满八门课，并且博士生要把 MA 5198 这门课修完。对于刚入学的博士生来说，除了修课之外，还有一个重要的任务，那就是尽快通过 Qualify Exam，因此几乎所有的 PHD 都会选择分析，代数，计算这三门课中的两门。

在 2010 年，当时的数学系刚刚从 S14 搬到 S17，而 S17 的只有 6-8 层已经装修好，4-5 层几乎还处于没有装修的状态。导致当时要上数学系的课程，教授和学生都必须要去 S14 的教室上课。而当年的代数课程是由 Berrick 教授负责，并且Qualify Exam 的考试又是由 Berrick 负责出题，但是 Berrick 教授给的分数一向不高。说实话，我对代数课程其实没有太多的兴趣，总觉得代数课程过于抽象，而这门课的主要内容居然是范畴论（Category Theory）。对个人来说这门课几乎是一门绝对用不上的课程。而范畴论好比数学界的黑话，这个理论总喜欢把一个容易理解的东西用及其抽象的语言描述出来，让人摸不着头脑。和范畴论相比，什么线性代数，抽象代数都已经是非常具体，浅显易懂的课程了。虽然范畴论的内容我现在已经全部忘记，半点都想不起来，但是在课堂上我印象最深刻的就是每次上课的时候 Berrick 教授都会拿着一种饮料进入教室，而且只喝那一种口味。于是，个人后续逛超市的时候就专门去寻找了那种饮料，终于在 West Coast Plaza 里面的 FairPrice 超市看到了那款饮料，尝试了之后果然味道不错，于是后续去 FairPrice 的时候，经常都会买那款饮料来喝。

提到 NUS 周围的超市，远远不止 FairPrice 这一家。就拿 West Coast Plaza 附近来说，除了 FairPrice 之外，还有 Shengsiong 超市。当年住在 Block 602 的时候，就觉得就 Shengsiong 超市的价格比 FairPrice 貌似要便宜一点。而当 Kent Ridge 地铁站建好了之后，对于 NUS 的学生而言，买东西的首选已经从 West Coast Plaza 变成了 Kent Ridge 地铁站，因为地铁站的二楼和三楼有一个小的 Shopping Mall，并且二楼同样也有 FairPrice 超市。无论是从 PGPR 宿舍区还是从 UTown 出发，都能够乘坐校车 A1 或者 A2 直达 Kent Ridge 地铁站，因此除非是特别想买某个物品，否则一般来说也不太需要专门去 West Coast Plaza 那边了。

其实读博士不仅仅是上课和搞科研，在此期间也会做很多助教的工作。在做助教的时候，给人印象最深刻的就是大峰哥和全知帝等人，这几人在读博期间所得到的助教成绩和学生的认可度都非常高，长期高居数学系助教排行榜的榜首。大峰哥在搞助教的时候，通常都会去 NUS 的 COOP（校园超市）购买一些打印纸，然后给学生们打印相应的课程材料，并且在考试之前都会给学生们进行详细的辅导。说到 NUS 的 COOP，无论是打印纸，笔记本，中性笔等常见的学习用具都能找到，甚至教授上课所用的教材都应有尽有。并且也会有一些 NUS 的周边礼品，包括最经典的小狮子，笔记本电脑，NUS 的文化衫等内容。对于 NUS 的学生而言，如果想要购买基础的学习用具，都可以在 NUS 的COOP 商店里面搞定。

nuscoop1

对于大峰哥而言，除了科研和助教之外，还有其余有趣的事情。在 2014 世界杯期间，作为球迷的大峰哥经常买可乐和零食给大家，请大家在吃东西的同时一起看球。由于新加坡的酒水实在是太贵，估计大峰哥买的不算太多，只能够靠可乐来撑数量。除此之外，貌似是在 2014 年底，百事可乐举办了抽奖活动，而抽奖的内容就是收集百事可乐的瓶盖，瓶盖越多中奖概率越大，所以大峰哥经常去超市搬一些可乐回来请办公室的同学们喝。刚开始的时候大家还是有兴趣喝，但是喝了几周之后其实大家都没有什么兴趣了。有个同学听闻大峰哥在做这件事的时候，就直接打电话给超市，送了几箱百事可乐过来，最终貌似由于百事可乐的版本不对而作罢。话说回来，个人觉得还是可口可乐比百事可乐好喝一些。

刚到了 NUS 的时候，由于数学系刚刚搬迁，除了教室不足之外，连 PHD 的办公位都很紧张。刚开始的时候，新来的 PHD 都要通过抽签的方式来决定是否拥有办公位。由于本人的运气比较背，连续两次都没有抽中办公位，于是在 NUS 的第一个学期只好在学校里面的几个图书馆之间打转。距离 S17 最近的图书馆自然是 Science Library。图书馆里面的书并不是所有的都能够外借。而不能外借的通常来说都是由任课老师所指定的，当时正在使用的教材。除此之外，其余的书籍基本上都能够外借。NUS的图书馆除了 Science Library 之外，Central Library 和 Business Library 都是非常不错的图书馆。当年读书的时候除了在 Science Library 借过书之外，在其他 Library 也借过不少的资料。NUS 的一个特点就是在走廊，图书馆的外面拜访了不少的桌子和椅子，专门给学生们自习或者讨论问题用的。当年准备 Qualify Exam 的时候恰好是圣诞节和元旦的时候，而每次到了 Public Holiday，图书馆都会闭馆。所以在当时没有办公位的情况下，Qualify Exam 的准备工作个人就是在图书馆门口的座位上准备的。

提到博士生的生活，除了日常的搬砖和去超市购买日用品之外，经常做的事情就是组团出去吃海鲜或者火锅。而且新加坡的火锅通常来说都是自助的形式，30 新币左右就可以吃到饱。刚开始去新加坡的时候，经常和富贵等人一起去吃 West Coast Plaza 的川江号子火锅，或者在周末的时候跟陈老师去吃 Shengsiong 附近的添一点火锅。提到添一点火锅，一开始还想着经常吃撑，不过到了后面的时候基本上也就是看情况而定。在 PHD 第一年的某个假期，个人和陈老师经常中午去吃添一点火锅，一开始先吃肉和蔬菜，然后到了最后就只吃虾，于是到了晚上的时候就再也不用吃饭了。后来除了火锅之外，大伙又在 Novena 地铁站附近发现了一个海鲜自助餐，维也纳海鲜，那里整体的环境和氛围都相对偏好。无论是牛肉还是螃蟹，甚至各种饮料都是畅饮。所以，后续我们年级的 PHD 如果有啥集体活动的时候，大伙都会选择去那边吃。之后 RDD 同学来的几次，都会去维也纳海鲜吃自助，其实那里的螃蟹和龙虾整体来说还是非常不错的。

除了各种各样的自助餐之外，其实海鲜一直是新加坡的特色，而个人比较推崇的就是黑胡椒螃蟹。提到黑胡椒螃蟹，就想到司北当年从日本来新加坡旅游，个人请他在克拉码头的珍宝海鲜楼吃了一顿饭，貌似三个人花费大概在 120 SGD 左右。珍宝海鲜楼的黑胡椒螃蟹在新加坡的食物中都算得上是一流的。当年 RDD 来的时候，其实也吃过不少黑胡椒螃蟹。整体来看，黑胡椒螃蟹或者螃蟹米粉是新加坡的一大特色，来新加坡的朋友千万不要错过这几种美食。

生活都包括衣食住行，对于留学生来说不可避免的就是租房问题。当年的 PGPR 和 UTown 还没有对 PHD 们开放的时候，大伙通常来说都会在外面租房子住。一开始的时候，姜师兄帮忙在 Block 602 #11-28 租了一间房，我和陈老师共同分担房租。其实后面 RDD 来玩的时候，也会去短租一些房子。至于找房子的问题，除了通过朋友们介绍或者转租之外，当年租房子的时候个人都会去华新论坛或者狮城论坛上面找。对于学生而言，一般都在华新论坛上面逛。每当看到一个合适的房源，都会去现场看一下，跟房东聊一下，然后就签订一份协议。不过相比国内现在的租房市场来说，当年签订的协议基本上就是君子协议，一般也就按时交房租就可以了。不过一开始在 Block 602 的时候，是 760 SGD 一间房，后续涨到了 800 SGD，貌似到了后面就越来越高了。和陈老师住的时候其实也就是住了一年，个人在 Block 602 的时候换过四个室友，陈老师，XXX（我真不记得了，就住了两个月），温同学，杰爷（我居然跟杰爷住过），上将。之后房东就不让我，杰爷和上将继续住了，我和上将就申请了 PGP 的房子，就剩下杰爷找了一个 260 SGD 的床位继续住。不过杰爷后续去了美帝国之后，从 Princeton 毕业之后大概找了一个几十万 USD / Per Year 的工作，估计再也不会住 260 SGD 的床位了。没过几年，上将也去澳洲继续攻读博士学位，当年在 Block 602 住过的几位室友恐怕很难再聚集到一起了。（未完待续）

PHD的生涯, 互联网的生涯

从高考志愿谈起

June 10, 2018 zr9558 Leave a comment

高考志愿

2018年6月10日，又是一年高考刚结束的日子。每次到了这个时候，都会回想起笔者在 2005 年高考填写志愿的时候。记得当年最火的方向应该是生物工程或者生命科学一类的专业，然后有不少优秀的学生去选择了这类专业。当时貌似还有人说计算机的人才过剩，会出现过了几年人才过剩，毕业生不好找工作的情况。不过当年自己也没想那么多，就完全凭着兴趣选择了最想学的方向，也是大多数人不会选择的方向，那就是数学与应用数学专业。

一般提到数学专业，绝大多数人的反应就是：“读完之后大概只能够当老师了吧？”有的人也会说：“读了数学专业，再去金融或者计算机专业会变得容易许多。”这一类的话笔者当时确实也听了不少。不过，当年还年轻，也没想那么多事情，就一门心思的想把数学学好，做自己喜欢做得事情，也就是所谓的 Follow My Heart。

当年笔者在本科一直研究着数学，后来又在博士生阶段继续从事数学研究。在数学界学习的时候，笔者一直在学习数学相关的知识。通常来说老师只会告诉书本上的内容，包括定理和证明之类的。并没有告诉学生们这些数学知识该怎么用。这个其实也不怪老师们。毕竟大多数老师并没有工业界的工作经验，基本上都是在搞科学研究。事后回想起这些数学知识，就好比了解了一个精巧的工具箱，里面有着各种各样的工具，但是却没有人告诉笔者这些工具该如何使用，该用在什么实际场景中。所以，经常就会有人问老师：“学习那么多数学知识究竟有没有用？”

剑宗与气宗

其实，数学并不是没有用，而是对大多数人没有用。数学有没有用就看每个人对数学的掌握程度和应用程度，如果一个人只能掌握到高中的水平，那基本上也就是加减乘除这种量级了。如果一个人能够掌握微积分这种程度，那就可以从事机器学习的相关工作。通常来说，在工业界搬砖的话，如果是机器学习的面试，一般或多或少都会问到一些微积分和线性代数的知识。如果是博士生去面试投行的 quant ，还需要会概率论，随机过程等统计学知识。

从笔者在工业界工作这几年的情况来看，一般工业界能够用到的数学边界，通常来说就在泛函分析，抽象代数，微分流形，随机过程这几门课的难度，再高级一点的课程恐怕就用不上了。而数学专业的两门基础课数学分析和高等代数，在工业界可以说是无处不在。而学习数学课，通常来说就像打基础的一个过程，更像是一种修行，好比学武的修炼内功。

金庸的《笑傲江湖》里岳不群这样说：三十多年前，咱们气宗是少数，剑宗中的师伯、师叔占了大多数。再者，剑宗功夫易于速成，见效极快。大家都练十年，定是剑宗占上风；各练二十年，那是各擅胜场，难分上下；要到二十年之后，练气宗功夫的才渐渐的越来越强；到得三十年时，练剑宗功夫的便再也不能望气宗之项背了。然而要到二十余年之后，才真正分出高下，这二十余年中双方争斗之烈，可想而知。

而学习计算机的正反馈其实相对快很多，在 GitHub 上下载源码装上了环境就可以运行，就能够看到效果。而学习数学的正反馈其实慢很多，毕竟看了很多数学书也不见得马上能够投入生产环境使用，甚至可能一辈子都无法投入实际使用。但是学习数学有一个好处，那就是思考问题和分析问题的时候会把实际问题抽象出来，把实际的问题转化成以前解决过的问题，用类似的方法和技巧进行解决。

其实选择什么样的专业也跟一个人的性格有关系。有的人就喜欢那种立竿见影的效果，学习一个东西就希望能够立刻投入生产使用，能够看到有产出，希望得到正反馈；而有的人会把得到正反馈的时间延长，期待通过长时间的学习，获得一个更大的正反馈。如果是学习工科的话，通常来说做一个东西所得到的正反馈就会很快；如果是学习理科的话，得到正反馈的时间就会变得很长，甚至没有正反馈。

数学的作用

其实，并不是学数学的人就一定能够做成每一件事，能够干好每一个行业。如果是数学系的学生刚刚进入工业界，最有可能面临的情况就是短期内无法产出，没有相应的成果，毕竟在公司内部都是半年甚至三个月考核一次。数学系的人的产出在短期内估计无法与计算机系的人相比。只有当数学系的人具备了写代码的能力，并且能够独立负责一个模块，能够实现一个功能的时候，这个人的数学能力才能够发挥出来。

虽然现在是一个知识爆炸的时代，但是数学系的课程却没有发生过太大的改变。十年前的课本和现在的课本也差不了多少，估计未来也不会发生巨大的改变，最多是删减一些内容。最关键的是，数学课本上写成公理，定理，推论这类的东西是正确的，是不会被推翻的（当然课本上也有写错的时候）。十年前是正确的，现在是正确的，未来也是正确的。但是其他学科就不太一样了，技能更新太快，现在所学的技能未来很可能就没有用处了。数学从来就没有大热过，很多人根本就不会选择数学专业，也不需要主动去劝退别人，数学系的学生从来都是主动退出。从中小学开始，就有很多人被数学虐得死去活来了，也不会去做“明知山有虎，偏向虎山行”的事情。

不过，凡是热衷于干脑力劳动的人，一般都会觉得当年要是多学一点数学该有多好。在最后，摘选知乎上的一段话：https://www.zhihu.com/question/47952938/answer/375655910

虽然说计算机和金融这俩行业都不能迷信数学，即把数学在其中的地位无限拔高。但这俩行业离开了数学，就是达内培训班和清华叉院的区别，就是银行柜员和文艺复兴的区别。就冲这个区别，数学的王者地位，还是无可动摇的。

PHD的生涯

在新加坡的这五年—生活篇

May 25, 2018 zr9558 2 Comments

之前的一篇文章撰写了笔者在新加坡的助教故事，本篇文章将会介绍笔者在新加坡的一些生活经历。

当年在中学地理课本里面，就写着新加坡是一座花园城市。不过毕竟耳听为虚，眼见为实。当笔者从新加坡的机场走出来的时候，看到一棵有一颗高大的树木（请原谅我不知道它们叫什么树），樟宜机场航站楼里面的绿化情况。就清楚地知道了地理教材上所言非虚，“花园城市”果然名不虚传。从机场到 NUS 坐了一路地铁，但是从 Clementi 下车之后到 West Coast Plaza 的一路却是公交车，明显可以感受到新加坡的绿化工作相比其他城市好不少。除了某些时候由于邻国烧芭导致空气质量低下之外，整个新加坡的空气质量和环境还是十分赞的。

（图）办公室外随手拍一张新加坡的天空

（图）滨海湾花园

（图）新加坡的公路

作为一个 NUS 的学生，除了日常的繁重学习之外，自然还有着丰富的课余活动。据说，NUS 的本科生想住在学校的宿舍的话，除了要保证成绩之外，还要保证一定的社会工作时间。这个社会工作包括社工，学校的活动等等。要想做好一些公益活动或者社会实践，只靠平时挤时间是完全不够的。从 NUS 的每年的日程安排来看，教学的时长大约是 8 个月。这就意味着 NUS 的假期长度明显高于国内。一个假期是在 12 月 – 1 月，大约 5 周的时间，主要是圣诞节和元旦；另一个假期是从 5 月开始，直到 7 月底结束。而每年 8 月开学的时候，绝大多数本科生都要进行一个大型的表演活动，所以，每次到了放暑假（5 月）的时候，学校里面都会看到不少的本科生占据了食堂，办公楼，图书馆的一些空旷地带，然后开始准备上两三个月的表演材料。经常看到的就是一堆本科生围成一圈，席地而坐，然后开始一边聊天一边做手上的工作。最终，学生们会根据做好的花车和编排好的节目在每年 8 月份的时候举行盛大的游行活动。
NUS花车1 NUS花车2

（图）NUS 本科生们的花车表演

对于博士生而言，虽然课余生活没有本科生那么丰富，但是也是要学会“苦中作乐”的，否则天天看书写论文的日子实在是不好过。在 NUS 内部，不仅有着健身房和游泳池，在 MPSH 和 YIH 附近还有着乒乓球桌和羽毛球场地。提到 NUS 的游泳池，一个是在 UTown 的一个屋顶上，是露天游泳池，和 Marina Bay Sands 相比就是高度低了点，其他都没有什么问题。另外一个大的游泳池就是在 MPSH 附近，里面有一个 50 米长的游泳池，并且有八条赛道。通常来说，白天的时候不会有太多的人去游泳，晚上的时候人会多一点。不过博士生的时间相对自由一些，因此自己在平时也会挑选一些 free time 去游泳。因为新加坡身处热带，降雨非常多，一旦遇到雷电天气，为了大家的安全着想，游泳池的管理员就会让大家上岸，等雷电天气过了之后才会让大家重新下水游泳。除了平时会抽空去游泳池之外，当年住在 PGP 的时候，每次到了周六或者周日，都会与卫同学从 PGP 坐早晨的第一班 A2 出发去游泳池，一起在游泳池里面谈笑风生。

（图）MPSH 的游泳池

（图）UTown 的游泳池

（图）Marina Bay Sands 的屋顶游泳池

除了健身之外，和大家日常生活相关的那就是衣食住行。NUS 的食堂其实还真不少，除了距离 NUS 数学系最近的 Science Canteen 之外，还有工程学院，Central Library ，YIH，商学院的食堂，其实最经常去的还是 Prince George Park 的食堂。记得当时每次从 Science 去 PGP 的时候，笔者都会和杰爷在 S17 的楼下朝 YIH 的方向一眼望去。如果能够看到 A2 快来了，那就选择去 PGP，否则就会就近选择 Science Canteen。其实，NUS 的食堂价格相对外面还算便宜，一顿饭大约 5 新币左右，也就是不到 30 人民币。不过就算食堂再好吃，有的时候我们也会选择出去吃顿更好的。刚到新加坡的时候，2010 级的 PHD 们一般都是去 West Coast Plaza 吃添一点火锅或者川江号子火锅。每次想吃火锅的时候，只需要在 S17 坐 C 车过去即可。虽然在 Clementi Woods 上面有一家 Sakura 的自助餐厅，但是吃了一两次之后个人感觉实在是挺一般的，因此后面就不再主动去那一家。后来我们发现 Clementi 附近有“黄土地”卖羊肉泡馍和肉夹馍，还有“福苑家传菜”，有的时候也会选择在 AYE 上面坐公交车过去。到了后来，NUS 附近的 Kent Ridge 地铁站开通了之后，去 Buona Vista 或者 Holland Village 变得十分方便。于是，每到周末的时候，就会和卫同学坐地铁去这两个地方吃拉面或者其他食物。有的时候，如果大家的时间能够凑齐的话，会选择去更远的地方，例如 Vivo City 或者克拉码头附近。不过后来快毕业的时候想再去吃一顿这些地方，发现有的店铺已经关门了，而笔者都不知道它们是什么时候停止营业的。真是“花儿还有重开日,人生没有再少年”。

NUS食堂

（图）NUS 的 UTown 食堂

在新加坡除了各种各样的中国食物之外，其实相对多一点的就是各种各样的自助餐了。刚到新加坡没多久的时候，就有同学发现了 Novena 地铁站的维也纳海鲜自助（Vienna International Seafood & Teppanyaki Restaurant）。除了跟众多 PHD 们去过这一家，还跟 RDD 同学去过几次。里面的食物除了日常的海鲜三文鱼之类的，还有牛排等食物。除此之外，强烈推荐的食物就是黑胡椒螃蟹，这个可以去珍宝海鲜楼（Jumbo Seafood）和无招牌海鲜（No Signboard Seafood），其中后者在 VivoCity 就有一家分店。除了海鲜之外，还和 RDD 同学一起去过 Clementi 的 Seoul Garden，这是一家韩式烤肉店，整体感觉也是不错的。记得当时吃饭的点貌似是工作日的下午一点左右，然后看到 Clementi 小学的学生们已经放学了。。。。。

Jumbo1

（图）珍宝海鲜楼

提到出行方面，在 NUS 的 Kent Ridge 地铁站还没有修好之前，大家都是通过公交车出行，要么在 S17 楼下坐 95 路公交车去 Buona Vista 地铁站，要么在 Central Library 坐 96 路公交车去 Clementi 地铁站，要么在 AYE 上面坐 197，198，963 直接去 Vivo City。不过新加坡的 Bus 质量都挺好的，坐起来也算比较舒服，毕竟是 Benz 的牌子。不过，自从地铁开通了之后，大家貌似都不怎么坐公交了。不过有的时候我还是会选择坐公交出行，毕竟在地面上还能够看看新加坡的风景，在地下就只能够看手机了。记得当年跟 RDD 同学还一起坐在双层 Bus 的二楼第一排一起看风景。
新加坡Bus1

（图）新加坡的 Benz 公交

新加坡的住宅一般分成两种，一种是组屋，一种是公寓。不过自己从来没有住过公寓，基本上都是住在组屋。组屋一般来说比公寓的租金会低一点，不过只要是好一点的组屋，也不会特别便宜。除了在外租房之外，NUS 的宿舍也是非常不错的。一开始的时候，由于 Utown 还未建成，NUS 给博士生提供的宿舍是在 BoonLay 那边，所以有的同学每天都会坐学校提供的 Bus 往返学校和宿舍区。到了后来，UTown 建成了之后，博士生的宿舍一般就是 PGP 和 UTown 这两个宿舍群。一般来说，这两个宿舍群给大家提供的都是单人间的宿舍，只是略有不同而已。在 Prince George Park，每个房间就住一个人，只不过一层楼有十几个房间，大家公用一个大的浴室和卫生间。而在 UTown，则是一个四人间的屋子，每个人住一间屋子，然后公用卫生间和浴室。由于 PGP 有空调的屋子貌似都有独立的卫生间和浴室，所以会比 UTown 贵不少。不过，在都没有空调的前提下，UTown 的宿舍会比 PGP 的宿舍便宜一些。

（图）PGP 的单人间宿舍

在购物方面，最近的商场那应该就是 West Coast Plaza。由于新加坡一年到头都是夏天，所以我们只需要购买夏天的衣服就可以了。因此，West Coast Plaza 里面的 Nike Factory 店就成为了我的首选。一是 Nike 的衣服确实也还不错，二是那边的衣服确实相对便宜一点。除了 West Coast Plaza，Vivo City 是一个较大的购物广场，可以在里面买到更多的东西。无论是买日常的衣服，还是其他东西，或者来这里吃饭，都是不错的选择。不过整体来说，自己来 Vivo City 的次数还是相对少，毕竟笔者的活动范围有限，不愿意跑太远的路程。（未完待续）

PHD的生涯

在新加坡的这五年－－－助教篇

May 3, 2018 zr9558 Leave a comment

很多 PHD 在国外攻读博士学位的时候，除了做科研和发表论文，还要负责一定量的教学工作，毕竟这些 PHD 以后是非常有可能去大学或者科研机构去任教的。回想当年（2009 年，i.e. 将近十年前），收到新加坡国立大学 Offer 的时候，除了一些 Congratulations 的话语和愿意提供给我 Offer 的信件之外，最重要的就是被数学系告知每周都需要做一定量的教学工作。在攻读博士学位期间，笔者不仅给本科生修改过作业，还给本科生上过习题课；而每次到了期中期末的时候，还要负责监考。在新加坡读书那五年，当助教的过程中，身边发生了不少有趣的事情，时隔多年也不知道能否一一想起，于是提笔写下此文，希望多年之后还能够想起那么多有趣的人和有趣的事。

KentRidgeRoad

NUS 的 Kent Ridge Road，Block S17 过街天桥。一条走了 3000 次的路。

助教开始

刚进入 NUS 的时候，也就是 2010 年秋季。低年级的 PHD 们自然还处于一个适应期和修课的阶段，于是系里面也没有给低年级的 PHD 们很重的工作量，也没有让低年级的 PHD 们去教本科生的习题课。于是我们拿到的任务就是修改作业，同时授课老师会给我们提供一份作业答案，我们只需要照着那份答案修改即可。其实修改作业还算好，没有给笔者造成很大的压力。当时压力比较大的就是给本科生上 Maple（一种数学软件）。说到压力大并不是说这门课有多难，而是要英语给本科生讲这门课。作为一个英语一直不太好的人，当时的听说读写还是存在很大的困难，何况在刚到新加坡没多久的情况下就要给本科生讲习题课。但是，这些都是数学系给的任务，不做的话就没有办法顺利拿到学位，一切都只能够硬着头皮上。当时教 Maple 的时候不仅需要给学生讲一些基础概念，还要负责学生们的上机操作。通常来说，学生在运行程序出 Bug 的时候除了自己 Debug 之外，更多的则是直接问我们各种各样的问题。所以，在教课的过程中需要不停地给学生们查看 Maple 程序里面的 bug，解答各种奇怪的数学问题。有一次在教课的过程中，有个学生对某个习题提出了自己的意见，不过当时自己没有回答出来，当时也不知道是自己的英语问题还是其他的问题。不过事后还是重新梳理了思路，给了学生一个合理的解释。在教 Maple 的过程中，除了学到了一些新的知识之外，最大的收获应该就是自己的英语口语能力的到了提升，并且能够独立地讲习题课。

当年刚到 NUS 的时候还有一些小插曲，由于当时数学系刚从 Block S14 搬到 Block S17，办公室的座位十分紧张，并不能够保证所有 PHD 都有办公座位。因此就需要通过抽签的方式来决定哪些人有座位，哪些人没有座位。而笔者非常悲剧的通过两次抽签，成为了当年系里面唯一一个没有自己座位的 PHD。所以笔者在第一个学期每次从老师那里拿到作业的时候，都只能够拿到 Science Library 去修改，然后带回 Block 602（当时在外租的房子）。只有到了需要归还给教课老师的时候，再从 Block 602 拿到系里面。所以，当时修改作业给我的最大印象就是把学生们的作业搬来搬去是非常累的一件事情。话说，在当年没有办公室座位的时候，笔者只能去 Science Library 去看书。但是，自从有了办公室之后，除了日常的借书之外，就几乎没有去过 Science Library 了。

ScienceLibrary2

Science Library 的门口

ScienceLibrary1

Science Library 中的 GTM 系列

在修改了一年的作业之后，通过一年多的课程的学习，除了数学知识的增加之外，自己的英语能力也得到了相应的提高，至少用英语讲几节习题课是没有太大的问题了。在 2011 年的时候，应该是在 2011 年的第一个学期，学校组织了一次教学的培训，那就是 CDTL（Centre for Development of Teaching & Learning）那边组织的提供了两天的培训，系里面不少的同学都去参加了那个培训。在培训的第一天都是在听那些教课的老师传授经验，至今能够记住的只有一句话：“每个人能够专注的时间非常短”。第二天则是所有来参加培训的 PHD 们都有一次十分钟的练习机会，然后老师和其余的 PHD 们都会来提供意见与建议。当年 CDTL 培训完之后，给每个学员提供了一个杯子，记得当时我还问培训老师这个我能否带走，老师给出了肯定的答案。于是，这个杯子就被我从 CDTL 拿到了 S17，然后从新加坡带回国，最后放在了我目前的办公桌上。

CDTL 的杯子

除了学校提供的助教培训课程之外，数学系主管教学的老师们也会给学生们提供培训课程。于是，到了第二年，系里面主管教学的 VT 老师就给第二年的 PHD 们群发邮件，告诉大家系里面将会组织一次培训，每个 PHD 都收到了一份习题和相应的答案。然后大家将会在一个下午现场操练一下，分别讲一讲那份习题，VT 老师会给大家相应的建议。在这次培训之后，大家就算正式接受过学校和院系的助教培训了，就要给学生们带习题课了。

助教生涯

说到第二年助教，那是自己唯一一次教线性代数的课程，Linear Algebra，MA1102。当时所用的教材是 NUS 的几位老师所写的，作者有 VT，NG 等。虽然这门课的难度并没有国内的难度大，但是教这门课确实也花费了不少的功夫。因为选择这门课的学生不仅有数学系和工程系的学生，甚至还有文科的学生。对于理工科的学生来说，这门课可能难度还行；但是对于文科，例如 Arts 之类的学生来说，这门课的难度估计已经远远超过了他们的想象。记得当时也有一些来自文科院系的学生反映了学这门课比较困难，所以每次这些学生遇到困难的时候，我总是会在下课之后多给他们讲一些内容。一来学生选了这门课就要拿到相应的学分，二来有的学生确实学习态度十分端正。说来说去，线性代数也算是自己第一次带一门课，可能对于老师来说，第一次独自带一门课，对学生总是会好很多。现在回想起来，通过这门课也认识了一些很不错的朋友，虽然毕业之后大家都再也没有见过面，不过当年能够在一起共同学习一门课也是一种缘分。

linear_algebra_i_ma_siu_lin_victor_tan_and_ng_kah_loon_1516770173_954ef566 (1)

Linear Algebra 的教材封面

数学系的老师除了教授本专业的课程之外，最重的课程应该就是 MA1505 和 MA1506。这两门课的名字叫做 Mathematics (I) 和 Mathematics (II)，按照国内的教学内容来看就是大学数学。为什么说课程量重呢？因为这两门课是面向全校所有院系的，不仅有数学系的人会听课，还有计算机系（School of Computing）的人，甚至还有整个工程院系（Faculty of Engineering）的本科生。所以每个学期的学生人数都是一千多人，教课的时候老师们都只能够选择那种很大的课堂，然后分成几个很大的班级，分别教授同样的课程。记得每次教这两门课的时候都要用数学系的四个老师去教，而助教的人数就更多了，每次都要花费数十个 PHD 才能够提供足够多的习题课供学生们选择。而数十个 PHD 则几乎是一个年级的全部 PHD，所以，随着后来 PHD 们数量的减少，教学的任务就变得越来越重。在 2011 年的时候，每个 PHD 只需要教课 4 小时可以了，但是到了 2014 年的时候，每个 PHD 都必须有 5 小时以上的工作量才能够把整个习题课解决掉。

贴一张当年 MA1505 课程安排的工作量

因为要教 4－5 小时的习题课，于是大家都倾向于把习题课安排在同一天，因为这样的话只需要去一天就好了。这样虽然能够减少去的次数，不过教四节课那天实在是非常累，讲完之后基本上都不愿意继续说话。在 UTown 没有修好之前，MA1505 通常都会安排在 Faculty of Engineering；而在 UTown 修好之后，MA1505 就改到了 UTown 的教室。除了习题课之外，MA1505 通常都会给学生们提供答疑的时间，一般来说每个人每周去一个小时就可以了。有一次，我和富贵，何老师同时教一门课，于是三个人一合计就把时间选择在了某一天的早上，从 9:00-12:00，每次一个人连去三小时，一个学期算下来虽然工作的时间量没变化，但是去的次数少了很多。由于 UTown 或者 Engineering 距离 NUS 的游泳池非常近，于是自己在教课之前或者教课之后会选择去游泳池健身。不过整体来说，NUS 的助教的工作量还是属于能够接受的范围内，一般来说不会占用一个 PHD 很多的时间。

上面这幅图是在 2013 年当助教的时候，在 Faculty of Engineering 买的午饭，也是当年发的第一个微信朋友圈。

当年 MPSH 的 Swimming Pool

通过当年的助教，确实把之前所学的很多内容重新学习了一遍，虽然之前在本科的时候学过数学分析和高等代数，但是多年过去难免忘记很多细节。借助助教的机会重温了当年的许多课程，也算是把自己多年的所学进一步巩固了一下。时至今日，一旦有一些空闲时间，笔者就会翻开之前所学的数学书，看一看当年的内容是否已经生疏，是否需要重新学习一遍。

助教故事

提到当 NUS 数学系的助教，就不能够不提到大峰哥。当年在 VT 给大家培训的时候，我们就发现只有大峰哥把习题全部自己做了一遍，然后逐字逐句给大家解释得很清楚，同时 VT 老师也对大风歌给出了非常高的评价。于是，在未来几年里面，大峰哥都主要在给 VT 老师当助教。大峰哥在数学系做助教的时候，尽职尽责，不仅能够做到认真备课，还把课堂上的所有 PPT 和资料自行整理了一遍。这里的整理并不只是把资料整理好给学生，而是把所有的课堂要点和考试关键点用 LaTex 整理出来，并整理成 PDF 发给学生当学习资料。而且每次大峰哥在考试之前都开设专门的答疑时间，给全体学生们的考试答疑解惑。最终的结果就是大峰哥连续 N 次拿到 Best Tutor 的职位，每次的学生评分都在 4.5 以上，据说有一次的评分达到了 4.8（满分是5）。记得之前笔者讲得最好的时候貌似也就是 3.7 左右的得分，从来没有上过 4 分，与大峰哥的得分形成了鲜明的对比。

BestTutor1

NUS 数学系的 Best Tutor 们

虽然说笔者从来没有拿到过 Best Tutor，但是自认为教课也算认真负责。那几年只有一次讲线性代数，一次讲数学物理方法。剩下的时间全部是讲 MA1505 和 MA1506，每一学期几乎都是面对相同的教学内容，只是学生换了一波又一波。因此，笔者在 2013 年秋整理了 MA1505 的讲义和资料，不仅使用 WordPress 整理在个人主页上（zr9558.com），还在习题课的时候打开自己的主页，使用所做的资料给学生们授课。除此之外，在每次考试之前，无论是期中考试还是期末考试，都会给学生们划出考试重点，甚至在考试之前还会写出考题预测（虽然也没有命中某个题目，但是足以命中某类题目）。即使笔者那么做，也并没有提高学生的评分。不过，在教 MA1505 和 MA1506 的时候，还是认识了不少优秀的学生。当时来新加坡就读的大部分都是 SM2，SM3 这些政府项目，也就是说这些大陆来的学生在毕业之后是需要留在新加坡工作几年的，需要履行当年所签下的合同。

TutorialsMA1505

以上图片是当年在 zr9558.com 上面给学生所整理的资料

除此之外，还有许多有趣的人和有趣的事情尚未写下来，后续笔者会持续更新当年求学路上的点点滴滴。

智能运维

黑盒函数的探索

April 28, 2018 zr9558 Leave a comment

黑盒函数的定义

在工程上和实际场景中，黑盒函数（black box function）指的是只知道输入和输出对应关系，而不知道它的内部结构，同时也不能写出具体表达式的一类函数。正如下图所示，每次给定一组输入，通过黑盒函数的计算，都能够得到一组输出的值，但是却无法写出 Black box 函数的精确表达式。

Blackbox3D-withGraphs

与之相反的是函数或者系统称之为白盒函数（open system），它不仅能够根据具体的输入获得相应的输出，还能够知道该函数的具体表达式和细节描述。例如 $f(x) = \sin(x)$ 和 $f(x) = \ln(x)$ 等都是白盒函数。

黑盒函数的研究对象

无论是白盒函数还是黑盒函数，都有很多的学术界人士和工业界人士去研究。通常来说，对于一个函数 $f(x)$ 而言，我们都可以研究该函数的以下性质：

最大值与最小值，i.e. $\max f(x)$ 和 $\min f(x).$
根，i.e. $\{x:f(x) = 0\}.$
函数的单调性与凹凸性等。

对于具有明显表达式的函数，例如 $f(x) = \sin(x)$ 等，我们能够使用的方法和技巧都很多，其方法包括但不限于导数，积分，Taylor 级数等等。但是对于黑盒函数，我们能够使用的方法和技巧就会一定的限制。本文将从如何研究一个函数的根，最大值和最小值等方向入手，逐步向大家展示黑盒函数研究中所遇到的数学与机器学习方法。

黑盒函数的根

对于多项式 $p(x) = a_{n}x^{n}+\cdots + a_{0}$ 而言，多项式的根指的是使得 $p(x)=0$ 的 $x$ 的解。特别的，对于二次多项式而言，也就是 $ax^{2} +bx+c=0,$ 它的根可以表示为：

$x = \frac{-b\pm\sqrt{b^{2}-4ac}}{2a}.$

对于一般函数 $f(x)$ 而言，它的根指的是 $\{x:f(x)=0\}$ 这个集合。下面我们来介绍一下如何计算一个函数的根。

二分法

在数学分析中，介值定理（Intermediate value theorem）描述了连续函数在两点之间的连续性，具体描述是：

[介值定理] 如果连续函数 $f(x)$ 的定义域包含 $[a,b],$ 而且通过 $(a,f(a))$ 与 $(b,f(b))$ 两点，它也必定通过区间 $[a,b]$ 内的任意一点 $(c,f(c)),$ 其中 $a<c<b.$

从介值定理可以得到，如果我们知道 $f(x_{1})<0$ 和 $f(x_{2})>0,$ 那么必定存在 $x_{0} \in (x_{1},x_{2})$ 使得 $f(x_{0})=0$ 。根据这个定理，我们可以提出二分法来计算函数的根。

如果要计算 $f(x) = 0$ 的解，其一般步骤是：

先找到一个区间 $[a,b],$ 使得 $f(a)f(b)<0;$
求这个区间的中点 $m=(a+b)/2,$ 并求出 $f(m)$ 的取值；
如果 $f(m)=0,$ 那么 $m$ 就是函数的根；如果 $f(m)f(a)>0,$ 就选择 $[m,b]$ 为新的区间，否则选择 $[a,m]$ 为新的区间；
重复第 2 步和第 3 步直到达到最大迭代次数或者最理想的精度为止。

Bisection_method

牛顿法（Newton’s Method）

牛顿法的大致思想是：选择一个接近 $f(x)$ 零点的初始点 $x_{0},$ 计算这个点相应的函数取值 $f(x_{0})$ 与导数值 $f'(x_{0}),$ 然后写出通过点 $(x_{0},f(x_{0}))$ 的切线方程，并且计算出该切线与横轴的交点 $x_{1}.$ i.e.

$x_{1} = x_{0} - f(x_{0})/f'(x_{0}).$

我们可以不停地重复以上过程，就得到一个递推公式：

$x_{n+1}= x_{n}-f(x_{n})/f'(x_{n}).$

在一定的条件下，牛顿法必定收敛。也就是说 $x_{n}$ 随着 $n$ 趋近于无穷，将会趋近于 $f(x)=0$ 的解。

Ganzhi001

割线法

根据导数的定义：

$f'(x_{0}) = \lim_{x\rightarrow x_{0}}\frac{f(x)-f(x_{0})}{x-x_{0}}$

可以得到，当 $x$ 靠近 $x_{0}$ 的时候，可以用右侧的式子来估计导数值，i.e.

$f'(x_{0}) \approx \frac{f(x)-f(x_{0})}{x-x_{0}}.$

当我们不能够计算 $f(x)$ 的导数的时候，就可以用上式来代替。

于是，割线法与牛顿法的迭代公式非常相似，写出来就是：

$x_{n+1} = x_{n} - \frac{x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}f(x_{n}).$

在这里，割线法需要两个初始值 $x_{0}$ 与 $x_{1},$ 并且它们距离函数 $f(x)=0$ 的根越近越好。

割线法1

备注

对于黑盒函数而言，我们是不知道它们的表达式的，因此以上的方法和技巧在黑盒函数的使用上就有限制。例如牛顿法是需要计算函数的导数值的，因此不适用在这个场景下。但是对于二分法与割线法，只需要计算函数在某个点的取值即可，因此可以用来寻找黑盒函数的根。

黑盒函数的最大值与最小值

对于能够写出表达式的函数而言，如果要寻找 $f(x)$ 的最大值与最小值，可以计算 $f(x)$ 的导数 $f'(x),$ 然后令 $f'(x) =0,$ 就可以得到函数的临界点（critical point），再根据周围的点导数的性质即可判断这个点是否是局部最大值或者局部最小值。

Weierstrass 逼近定理

对于黑盒函数而言，通常来说我们只知道一组输入和相应的输出值。如果只考虑一维的情况而言，那就是 $\{(x_{i},y_{i})\in \mathbb{R}^{2},0\leq i\leq n\}$ 这 $n+1$ 个样本。根据 Weierstrass 逼近定理可以知道：

闭区间上的连续函数可以用多项式级数一致逼近；
闭区间上的周期为 $2\pi$ 的连续函数可以用三角函数级数一致逼近。

用数学符号来描述就是：

[Weierstrass 逼近定理] 假设 $f(x)$ 是闭区间 $[a,b]$ 连续的实函数。对于任意的 $\epsilon>0$ ，存在一个多项式 $p(x)$ 使得对于任意的 $x\in[a,b],$ 有 $|f(x)-p(x)|<\epsilon.$

因此，如果要计算黑盒函数的最大值和最小值，可以使用一个多项式去拟合这 $n+1$ 个点，于是计算这个多项式的最大值与最小值即可。

Lagrange 插值公式

按照之前的符号，如果我们拥有 $n+1$ 个样本 $\{(x_{i},y_{i}), 0\leq i\leq n\},$ 那么我们可以找到一个多项式 $p(x)$ 使得 $p(x_{i}) = y_{i}$ 对每一个 $0\leq i\leq n$ 都成立。根据计算，可以得到该多项式是：

$p(x) = \sum_{i=0}^{n}\bigg(\prod_{0\leq j\leq n, j\neq i}\frac{x-x_{j}}{x_{i}-x_{j}}\bigg)y_{i}.$

于是，要计算黑盒函数的最大值与最小值，就可以转化成计算 $p(x)$ 的最大值与最小值。

除了数学方法之外，机器学习中有一种算法叫做启发式优化算法，也是用来计算黑盒函数的最大值和最小值的，例如粒子群算法与模拟退火算法等。

粒子群算法（Particle Swarm Optimization）

PSO 最初是为了模拟鸟群等动物的群体运动而形成的一种优化算法。PSO 算法是假设有一个粒子群，根据群体粒子和单个粒子的最优效果，来调整每一个粒子的下一步行动方向。假设粒子的个数是 $N_{p}$ ，每一个粒子 $\bold{x}_{i}\in \mathbb{R}^{n}$ 都是 $n$ 维欧几里德空间里面的点，同时需要假设粒子的速度 $\bold{v}_{i}\in\mathbb{R}^{n}$ 。在每一轮迭代中，需要更新两个最值，分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值，分别记为 $\bold{x}_{i}^{*}$ （ $1\leq i \leq N_{p}$ ）和 $\bold{x}^{g}$ 。在第 $t+1$ 次迭代的时候，

$\bold{v}_{i}(t+1) = \bold{v}_{i}(t) + c r_{1}[\bold{x}_{i}^{*}(t) - \bold{x}_{i}(t)] + c r_{2}[\bold{x}^{g}(t) - \bold{x}_{i}(t)],$

$\bold{x}_{i}(t+1) = \bold{x}_{i}(t)+\bold{v}_{i}(t+1), \text{ } 1\leq i\leq N_{p}.$

在这里， $c>0$ ，并且 $r_{1}, r_{2}$ 是 $[0,1]$ 中间的随机数。

模拟退火（Simulated Annealing）

SA1 SA2 SA3

模拟退火算法是为了模拟金属退火现象。其核心思想是构造了温度 $T$ 这个维度，当温度 $T$ 高的时候，分子运动速度快，能够探索更多的区域；温度 $T$ 低的时候，分子运动速度慢，能够探索的区域有限。随着时间的迁移，温度 $T$ 会从一个较大的值逐渐降低到 0。

模拟退火的大体思路是这样的：先设置一个较大的温度值 $T$ ，随机初始化 $\bold{x}(0)$ 。假设目标函数是 $E(\bold{x}),$ 需要寻找 $argmin_{\bold{x}}E(\bold{x})$ ，然后执行以下的程序：

Repeat：

a. Repeat:

i. 进行一个随机扰动 $\bold{x} = \bold{x} + \Delta \bold{x}$ ；

ii. 计算 $\Delta E(\bold{x}) = E(\bold{x}+\Delta\bold{x}) - E(\bold{x})$ ，

如果 $\Delta E(\bold{x}) <0$ ，也就是 $E(\bold{x} + \Delta\bold{x})<E(\bold{x})$ ，选择 $\bold{x}+\Delta\bold{x}$ ；

否则，按照 $P = e^{-\Delta E/T}$ 的概率来接受 $\bold{x} +\Delta\bold{x}$ 。

b. 令 $T = T-\Delta T$ 。

直到 $T$ 足够小。

总结

本文从数学和机器学习的角度，简要介绍了部分计算黑盒函数的最大值，最小值和根的方法，后续将会介绍更多的类似方法。

Complex Analysis

Riemann Zeta 函数（二）

April 27, 2018 zr9558 Leave a comment

在上一篇文章里面，我们已经给出了 Riemann Zeta 函数的定义，

$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}.$

其定义域是 $[1,\infty)\subseteq\mathbb{R}.$ 根据级数与定积分的等价关系可以得到：

当 $s = 1$ 时， $\zeta(1) = \infty;$
当 $s>1$ 时， $\zeta(s)<\infty.$

本文将会重点讲两个内容：

如何把 Riemann Zeta 函数从 $[1,\infty)\subseteq \mathbb{R}$ 上延拓到 $\{s\in \mathbb{C}: \Re(s)>0\}$ 上；
Riemann Zeta 函数在 $\{s\in\mathbb{C}: \Re(s)\geq 1\}$ 上没有零点。

Riemann Zeta 函数定义域的延拓

如果想把 Riemann Zeta 函数的定义域从 $[1,\infty)\subseteq \mathbb{R}$ 延拓到更大的区域 $\{s\in\mathbb{C}:\Re(s)>0\}$ 上，就需要给出 Riemann Zeta 函数在 $\{s\in \mathbb{C}: \Re(s)>0\}$ 上的定义。而且在原始的定义域 $[1,\infty)\subseteq\mathbb{R}$ 上面，新的函数的取值必须与原函数的取值保持一致。

首先，我们将会在 $[1,\infty)\subseteq \mathbb{R}$ 上面证明如下恒等式：

$\zeta(s) = \frac{s}{s-1} - s\int_{1}^{\infty}\frac{\{x\}}{x^{s+1}}dx$ .

证明：当 $s=1$ 时，上述等式显然成立，两侧都是 $\infty.$

$\frac{s}{s-1}-s\int_{1}^{\infty}\frac{\{x\}}{x^{s+1}}dx$

$= \frac{s}{s-1} - s\sum_{n=1}^{\infty}\int_{n}^{n+1}\frac{\{x\}}{x^{s+1}}dx$

$= \frac{s}{s-1} - s\sum_{n=1}^{\infty}\int_{n}^{n+1}\frac{x-n}{x^{s+1}}dx$

$= \frac{s}{s-1} - s\sum_{n=1}^{\infty}\bigg(\int_{n}^{n+1}\frac{1}{x^{s}}dx - \int_{n}^{n+1}\frac{n}{x^{s+1}}dx\bigg)$

$= \frac{s}{s-1} - s\int_{1}^{\infty}\frac{1}{x^{s}}dx + \sum_{n=1}^{\infty}n\cdot\int_{n}^{n+1}\frac{s}{x^{s+1}}dx$

$= \sum_{n=1}^{\infty}n\cdot\bigg(\frac{1}{n^{s}}-\frac{1}{(n+1)^{s}}\bigg)$

$= \sum_{n=1}^{\infty}\bigg(\frac{1}{n^{s-1}}-\frac{1}{(n+1)^{s-1}} + \frac{1}{(n+1)^{s}}\bigg)$

$= \sum_{n=1}^{\infty}\frac{1}{n^{s}}.$

从右式的表达式

$\frac{s}{s-1} - s \int_{1}^{\infty}\frac{\{x\}}{x^{s+1}}dx$

可以看出 $\zeta(s)$ 可以延拓到 $\{s \in\mathbb{C}:\Re(s)>0\}$ 上。而且右侧的函数在 $\{s\in\mathbb{C}:\Re(s)>0,s\neq 1\}$ 是解析的，并且 $s=1$ 是该函数的一个极点。进一步的分析可以得到，我们得到一个关于 $(s-1)\zeta(s)$ 的解析函数，而且 $\lim_{s\rightarrow 1}(s-1)\zeta(s)=1.$ 综上所述：

Riemann Zeta 函数可以延拓到 $\{s\in\mathbb{C}:\Re(s)>0\}$ 上；
Riemann Zeta 函数在 $\{s\in\mathbb{C}:\Re(s)>0, s\neq 1\}$ 上是解析的； $s=1$ 是 Riemann Zeta 函数的极点。

Riemann Zeta 函数的非零区域

著名的 Riemann 猜想说的是 $\zeta(s)$ 函数的所有非平凡零点都在直线 $\{s\in\mathbb{C}:\Re(s)=1/2\}$ 上。因此，数学家首先要找出的就是 Riemann Zeta 函数的非零区域。而本篇文章将会证明 Riemann Zeta 函数在 $\{s\in\mathbb{C}:\Re(s)\geq 1\}$ 上面没有零点。

$\Re(s)>1$ 区域

首先，我们要证明当 $\Re(s)>1$ 时， $\zeta(s)\neq 0.$

在这里，就需要使用一个重要的恒等式：当 $\Re(s)>1$ 时，

$\zeta(s) =\sum_{n=1}^{\infty}\frac{1}{n^{s}}$

$= \prod_{p}\bigg(1+\frac{1}{p^{s}}+\frac{1}{p^{2s}}+\cdots\bigg)$

$= \prod_{n=1}^{\infty}\bigg(1-\frac{1}{p_{n}^{s}}\bigg)^{-1},$

其中这里的 $p$ 表示所有的素数相乘，而 $p_{n}$ 表示第 $n$ 个素数。

下面我们证明：

$\bigg|1-\frac{1}{p_{n}^{s}}\bigg|^{-1}\geq 1-\frac{1}{p_{n}^{\sigma}-1} .$

事实上，令 $s = \sigma + i t,$ ，当 $\sigma=\Re(s)>1$ 时，我们有

$\bigg|1-\frac{1}{p_{n}^{s}}\bigg|^{-1} = \bigg(1+\frac{1}{p_{n}^{s}}+\frac{1}{p_{n}^{2s}}+\cdots\bigg)$

$\geq 1-\frac{1}{|p_{n}^{s}|}- \frac{1}{|p_{n}^{2s}|} -\cdots$

$= 1- \frac{1}{p_{n}^{\sigma}} - \frac{1}{p_{n}^{2\sigma}} -\cdots$

$= 1- \frac{1}{p_{n}^{\sigma}-1}.$

因此，

$|\zeta(s)| \geq \prod_{n=1}^{\infty}\bigg|1-\frac{1}{p_{n}^{s}}\bigg|^{-1} \geq\prod_{n=1}^{\infty}\bigg(1-\frac{1}{p_{n}^{\sigma}-1}\bigg).$

同时，

$\lim_{n\rightarrow \infty} \bigg(1- \frac{1}{p_{n}^{\sigma}-1}\bigg) = 1 ,$

$1-\frac{1}{p_{n+1}^{\sigma}-1} \geq 1- \frac{1}{p_{n}^{\sigma}-1} ,$

$\sum_{n=1}^{\infty}\frac{1}{p_{n}^{\sigma}}\leq \sum_{n=1}^{\infty}\frac{1}{n^{\sigma}}<\infty$ when $\sigma>1.$

所以，当 $\Re(s)>1$ 时， $\zeta(s) \neq 0.$

$\Re(s) =1$ 直线

Claim 1. 下面我们将会证明恒等式：对于 $\sigma >1, \text{ } t\in\mathbb{R},$

$\Re(\ln\zeta(\sigma + it)) = \sum_{n=2}^{\infty}\frac{\Lambda(n)}{n^{\sigma}\ln(n)}\cos(t\ln(n)) ,$

其中当 $n$ 形如 $p^{\alpha},$ $p$ 是素数， $\alpha \geq 1.$ $\Lambda(n) = \ln(p).$ 而对于其余的 $n,$ $\Lambda(n)=0.$

事实上，根据 Euler 公式，

$\zeta(s) = \prod_{p}\bigg(1-\frac{1}{p^{s}}\bigg)^{-1}.$

令 $s = \sigma + it,$ 可以得到

$\ln\zeta(s) = -\sum_{p}\ln\bigg(1-\frac{1}{p^{s}}\bigg)$

$= \sum_{p}\sum_{\alpha=1}^{\infty}\frac{1}{\alpha p^{\alpha s}}$

$= \sum_{p}\sum_{\alpha=1}^{\infty}\frac{1}{\alpha p^{\alpha\sigma}}\cdot p^{-i\alpha t}$

$= \sum_{p}\sum_{\alpha = 1}^{\infty}\frac{1}{\alpha p^{\alpha\sigma}}\cdot e^{-i\alpha t \ln p}$

进一步，

$\Re(\ln\zeta(s)) = \sum_{p}\sum_{\alpha =1}^{\infty}\frac{1}{\alpha p^{\alpha\sigma}}\cos(\alpha t \ln p)$

并且右侧等于

$RHS = \sum_{n=2}^{\infty}\frac{\Lambda(n)}{n^{\sigma}\ln(n)}\cos(t\ln(n))$

$= \sum_{p}\sum_{\alpha = 1}^{\infty} \frac{\ln(p)}{p^{\alpha\sigma}\ln(p^{\alpha})}\cos(t\ln(p^{\alpha}))$

$= \sum_{p}\sum_{\alpha = 1}^{\infty}\frac{1}{\alpha p^{\alpha\sigma}}\cos(\alpha t\ln p).$

所以，恒等式成立，Claim 1 证明完毕。

Claim 2.

$\Re(3\ln\zeta(\sigma) + 4\ln\zeta(\sigma+it) + \ln\zeta(\sigma+2it))\geq 0,$

其中 $\sigma>1,$ $t\in\mathbb{R}.$ 换句话说

$|\zeta(\sigma)^{3}\zeta(\sigma+it)^{4}\zeta(\sigma+2it)|\geq 1.$

事实上，

从三角函数的性质可以得到：

$3+4\cos(\theta)+\cos(2\theta) = 3 + 4\cos(\theta)+2\cos^{2}(\theta)-1$

$= 2(\cos(\theta)-1)^{2}\geq 0,$

所以，从 Claim 1 可以得到

$\Re(3\ln\zeta(\sigma) + 4\ln\zeta(\sigma+it) + \ln\zeta(\sigma+2it))$

$= \sum_{n=2}^{\infty} \frac{\Lambda(n)}{n^{\sigma}\ln(n)} \cdot ( 3 + 4\cos(t\ln(n)) + \cos(2t\ln(n))) \geq 0.$

进一步地，使用 $\Re(\ln(z)) = \ln(|z|)$ 可以得到

$0\leq 3\ln|\zeta(\sigma)| + 4\ln|\zeta(\sigma+it)| + \ln|\zeta(\sigma+2it)|$

$= \ln|\zeta(\sigma)^{3}\zeta(\sigma+it)^{4}\zeta(\sigma+2it)|,$

可以推导出 $|\zeta(\sigma)^{3}\zeta(\sigma+it)^{4}\zeta(\sigma+2it)|\geq 1.$ 因此 Claim 2 证明完毕。

Claim 3. $\zeta(1+it)\neq 0$ 对于所有的 $\{t\in\mathbb{R}: t\neq 0\}$ 成立。

反证法：假设 $\zeta(s)$ 在 $s=\sigma + it (t\neq 0)$ 存在阶数为 $m$ 的零点。也就是说：

$\lim_{\sigma\rightarrow 1^{+}} \frac{\zeta(\sigma+it)}{(\sigma+it-1)^{m}}=c\neq 0,$ 其中 $m\geq 1.$

从 Riemann Zeta 函数的延拓可以知道， $\lim_{\sigma\rightarrow 1^{+}}(\sigma -1)\zeta(\sigma) = 1.$ 并且 $\zeta(s)$ 在 $\{s\in\mathbb{C}:\Re(s)>0, s\neq 1\}$ 上是解析函数。

从 Claim 2 可以得到：

$|(\sigma-1)^{3}\zeta(\sigma)^{3}(\sigma+it-1)^{-4m}\zeta(\sigma+it)^{4}\zeta(\sigma+2it)|$

$\geq |\sigma-1|^{3}|\sigma-1+it|^{-4m}$

$\geq |\sigma-1|^{3}\cdot |\sigma-1|^{-4m}$

$= \frac{1}{|\sigma-1|^{4m-3}}.$

令 $\sigma\rightarrow 1^{+},$ 可以得到左侧趋近于一个有限的值，但是右侧趋近于无穷，所以得到矛盾。也就是说当 $t\neq 0$ 时， $\zeta(1+it)\neq 0$ 成立。

根据之前的知识， $s= 1$ 是 $\zeta(s)$ 的极点，所以我们得到了本篇文章的主要结论： $\zeta(s)$ 在 $\{s\in\mathbb{C}:\Re(s)\geq 1\}$ 上面没有零点。

总结

本篇文章从 Riemann Zeta 函数的延拓开始，证明了 Riemann Zeta 函数在 $\{s\in\mathbb{C}:\Re(s)\geq 1\}$ 上没有零点。在下一篇文章中，笔者将会证明在 $\Re(s)=1$ 附近一个“狭长”的区域上，Riemann Zeta 函数没有零点。

Mathematical Analysis

从调和级数到 RIEMANN ZETA 函数（一）

April 21, 2018 zr9558 Leave a comment

Riemann Zeta 函数

Riemann Zeta 函数（Riemann zeta function）， $\zeta(s)$ ，是一个关于复数 $s$ 的方程。在复平面上，当复数 $s$ 的实数部分 $\sigma=\Re s >1$ 时， $\zeta(s)$ 就是如下的级数形式：

$\zeta(s) = \sum_{n=1}^{\infty}\frac{1}{n^{s}}.$

调和级数的概念与性质

既然提到了级数，首先让我们来回顾一下级数的定义是什么？

级数的定义：在数学中，一个有穷或者无穷的序列 $(x_{0},x_{1},x_{2},...)$ 的形式和 $S = x_{0}+x_{1}+x_{2}+...$ 称为级数，里面的每一项都称为级数的通项。

级数收敛的定义：令 $S_{n}=x_{0}+...+x_{n}$ ，如果存在有限的 S 使得 $\lim_{n\rightarrow \infty}S_{n}=S$ ，那么就称该级数收敛。否则，该级数就称为发散级数。

然后下面我们来研究一下调和级数的基本性质。调和级数的表达式写出来十分简单，那就是 Riemann Zeta 函数在 $s=1$ 的取值，i.e.

$\zeta(1) = \sum_{n=1}^{+\infty}\frac{1}{n}.$

提到级数的收敛或发散，就必须要提到关于级数收敛的等价定理（Cauchy 判别法），那就是：级数 $S_{n}$ 收敛当且仅当对任意的 $\epsilon>0$ ，存在 $N$ 使得对于任意的 $m, n>N$ 都有 $|S_{m}-S_{n}|<\epsilon$ .

既然是等价定理，那么就可以使用 Cauchy 判别法来判断调和级数是否收敛。

Method 1. 令

$S_{n}=\sum_{k=1}^{n}\frac{1}{k},$

直接通过计算得到

$|S_{2n}-S_{n}|=\frac{1}{n+1}+...+\frac{1}{2n}>\frac{1}{2n}+...+\frac{1}{2n}=\frac{1}{2},$

说明该级数是不收敛的，也就是调和级数是发散的。

除了基于 Cauchy 收敛准则的证明之外，能否写出判断调和级数发散的其他方法呢？答案是肯定的。以下有一种使用初等数学方法就能够解释调和级数发散的方法。

Method 2.

$\sum_{n=1}^{+\infty}\frac{1}{n}$

$=1+\frac{1}{2}+(\frac{1}{3}+\frac{1}{4})+(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8})+...$

$>1+\frac{1}{2}+(\frac{1}{4}+\frac{1}{4})+(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8})+...$

$=1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+...=+\infty.$

既然都提到了高等数学，那么当然不能仅仅局限于使用初等数学的技巧来解决问题。而且如果只是用初等数学的方法，在拓展性方面就会受到极大的限制。

Method 3. 调和级数的发散可以通过定积分的技巧来进行解决。

HarmonicSeries

$1+\frac{1}{2}+...+\frac{1}{n}$

$>\int_{1}^{2}\frac{1}{x}dx + \int_{2}^{3}\frac{1}{x}dx+...+\int_{n}^{n+1}\frac{1}{x}dx$

$=\int_{1}^{n+1}\frac{1}{x}dx=\ln(n+1)$

因此， $\sum_{n=1}^{\infty}\frac{1}{n}=+\infty$ .

从上面的定积分的方法可以预计出调和级数的量级大约是对数的量级，那么能否精确的估计出来呢？例如下面这个问题：

问题： $\lim_{n\rightarrow +\infty}\frac{\sum_{k=1}^{n}\frac{1}{k}}{\ln(n)}=?$

通过 L’Hospital 法则可知： $\lim_{x\rightarrow 0}x/\ln(1+x)=1.$

通过 Stolz 定理可知：

$\lim_{n\rightarrow +\infty}\frac{\sum_{k=1}^{n}\frac{1}{k}}{\ln(n)}$

$= \lim_{n\rightarrow +\infty}\frac{\frac{1}{n}}{\ln(n/(n-1))}$

$= \lim_{x\rightarrow 0}\frac{x}{\ln(1+x)}=1$

除此之外，我们同样可以证明

$\lim_{n\rightarrow+\infty}(1+\frac{1}{2}+...+\frac{1}{n}-\ln(n))$

这个极限是存在并且有限的。

调和级数的推广

那么，如果在考虑 $\zeta(2)$ 也就是级数

$\zeta(2) = \sum_{n=1}^{\infty}\frac{1}{n^{2}}$

是否收敛的时候，能否用到以上类似的技巧呢？首先，确实也存在各种各样的初等数学技巧，例如：

Method 1.

$\sum_{n=1}^{+\infty}\frac{1}{n^{2}}<1+\sum_{n=2}^{+\infty}\frac{1}{n(n-1)}=1+\sum_{n=2}^{+\infty}(\frac{1}{n-1}-\frac{1}{n})=2$ .

Method 2. 使用数学归纳法。也就是要证明：

$\sum_{k=1}^{n}1/k^{2}\leq 2-\frac{1}{n}.$

当 $n=1$ 的时候，公式是正确的。假设 $n$ 的时候是正确的，那么我们有 $\sum_{k=1}^{n}1/k^{2}\leq 2-\frac{1}{n}$ 。计算可得：

$\sum_{k=1}^{n+1}\frac{1}{k^{2}}$

$<2-\frac{1}{n}+\frac{1}{(n+1)^{2}}$

$= 2- \frac{1}{n+1}-\frac{1}{n(n+1)^{2}}$

$\leq 2-\frac{1}{n+1}$ .

因此，不等式正确，所以 $\sum_{n=1}^{+\infty}1/n^{2}$ 收敛。

其次，在判断调和级数发散的时候，使用的定积分的方法同样可以应用在这个场景下。

Method 3.

$1+\frac{1}{2^{2}}+...+\frac{1}{n^{2}}$

$<1+\int_{1}^{2}\frac{1}{x^{2}}dx+...+\int_{n-1}^{n}\frac{1}{x^{2}}dx$

$=1+\int_{1}^{n}\frac{1}{x^{2}}dx=1+1-\frac{1}{n}<2.$

那么这个是针对次数等于2的情况，对于一般的情形，

$\zeta(s)=\sum_{n=1}^{+\infty}\frac{1}{n^{s}},$ 当 $\sigma = \Re(s)>1.$

使用定积分的技术，同样可以证明对于任意的 $\sigma = \Re(s)>1$ ，都有 $\zeta(s)$ 是收敛的。但是 $\zeta(1)$ 是发散的。

Riemann Zeta 函数中某些点的取值

除此之外，既然 $\zeta(s)$ 在 $\sigma = \Re(s)>1$ 的时候收敛，能否计算出某些函数的特殊值呢？答案是肯定的，例如，我们可以使用 Fourier 级数来计算出 $\zeta(2), \zeta(4), \zeta(6),...$ 的取值。首先，我们回顾一下 Fourier 级数的一些性质：

假设 $f(x)$ 是一个关于 $2\pi$ 的周期函数， i.e. $f(x)=f(x+2\pi)$ 对于所有的 $x \in \mathbb{R}$ 都成立。那么函数 $f(x)$ 的 Fourier 级数就定义为

$a_{0}+\sum_{n=1}^{\infty} (a_{n} \cos(nx) +b_{n} \sin(nx)),$

其中， $a_{0}= \frac{1}{2\pi} \int_{-\pi}^{\pi} f(x) dx,$

$a_{n}= \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos(nx) dx$ 当 $n\geq 1,$

$b_{n}= \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin(nx) dx$ 当 $n\geq 1,$

定理 1. 如果 $f(x)$ 在区间 $(-\pi, \pi)$ 上满足 Lipschitz 条件，那么

$f(x) =a_{0}+\sum_{n=1}^{\infty} (a_{n} \cos(nx) +b_{n} \sin(nx)).$

定理 2. Parseval’s 恒等式.

$\frac{1}{\pi} \int_{-\pi}^{\pi} |f(x)|^{2} dx= 2a_{0}^{2}+ \sum_{n=1}^{\infty} (a_{n}^{2}+b_{n}^{2}).$

下面我们就来证明下列恒等式：

$\sum_{n=1}^{\infty} \frac{1}{(2n-1)^{2}}=\frac{\pi^{2}}{8}$

$\sum_{n=1}^{\infty} \frac{1}{n^{2}}=\frac{\pi^{2}}{6}$

$\sum_{n=1}^{\infty} \frac{1}{(2n-1)^{4}}=\frac{\pi^{4}}{96}$

$\sum_{n=1}^{\infty} \frac{1}{n^{4}}=\frac{\pi^{4}}{90}$

证明：

选择在区间 $(-\pi, \pi)$ 上的函数 $f(x)=|x|$ ，并且该函数是关于 $2\pi$ 的周期函数。

使用 $a_{n}$ 和 $b_{n}$ 的公式，我们可以得到函数 $f(x)=|x|$ 的 Fourier 级数是

$\frac{\pi}{2} + \sum_{n=1}^{\infty} \frac{2((-1)^{n}-1)}{\pi} \cdot \frac{cos(nx)}{n^{2}}$

从定理1, 令 $x=0$ , 可以得到

$0= \frac{\pi}{2} + \sum_{n=1}^{\infty} \frac{2((-1)^{n}-1)}{n^{2} \pi} = \frac{\pi}{2} + \sum_{m=1}^{\infty} \frac{-4}{(2m-1)^{2}\pi} = \frac{\pi}{2} - \frac{4}{\pi} \sum_{m=1}^{\infty} \frac{1}{(2m-1)^{2}}$

因此， $\sum_{n=1}^{\infty} \frac{1}{(2n-1)^{2}}=\frac{\pi^{2}}{8}$ .

假设 $S=\sum_{n=1}^{\infty} \frac{1}{n^{2}}$ , 可以得到

$S=\sum_{odd} \frac{1}{n^{2}} + \sum_{even} \frac{1}{n^{2}} = \frac{\pi^{2}}{8} + \frac{1}{4} S$ .

因此 $S=\frac{\pi^{2}}{6}$ .

从 Parserval’s 恒等式，我们知道

$\frac{2\pi^{2}}{3}= \frac{1}{\pi} \int_{-\pi}^{\pi} x^{2}dx = 2\cdot (\frac{\pi}{2})^{2} + \sum_{n=1}^{\infty} \frac{4((-1)^{n}-1)^{2}}{\pi^{2}\cdot n^{4}} = \frac{\pi^{2}}{2} + \sum_{m=1}^{\infty} \frac{16}{\pi^{2} (2m-1)^{4}}$

因此 $\sum_{n=1}^{\infty} \frac{1}{(2n-1)^{4}} = \frac{\pi^{4}}{96}$ .

假设 $S=\sum_{n=1}^{\infty} \frac{1}{n^{4}}$ , 得到

$S=\sum_{odd} \frac{1}{n^{4}} + \sum_{even} \frac{1}{n^{4}} = \frac{\pi^{4}}{96} + \frac{1}{16} S$

因此, $S=\frac{\pi^{4}}{90}$ .

总结

本篇文章从调和级数的发散性开始，介绍了判断调和级数是否收敛的几种方法。进一步考虑了其他级数的收敛性，并通过 Fourier 级数的方法计算出了部分 Riemann Zeta 函数的取值。

Computer Science

如何从零到一地开始机器学习？

April 19, 2018 zr9558 Leave a comment

导语：作为一个数学系出身，半路出家开始搞机器学习的人，在学习机器学习的过程中自然踩了无数的坑，也走过很多本不该走的弯路。于是很想总结一份如何入门机器学习的资料，也算是为后来人做一点点微小的贡献。

在 2016 年 3 月，随着 AlphaGo 打败了李世乭，人工智能开始大规模的进入人们的视野。不仅是互联网的工程师们很关注人工智能的发展，就连外面的吃瓜群众也开始关注人工智能对日常生活的影响。随着人脸识别能力的日益增强，个性化新闻推荐 app 的横行天下，TensorFlow 等开源工具被更多的人所知晓，于是就有越来越多的人开始逐步的转行到人工智能的领域，无论是计算机出身的后台开发人员，电子通信等工程师，还是数学物理等传统理科人士，都有人逐步开始转行到机器学习的领域。

作为一个数学系出身，半路出家开始搞机器学习的人，在学习机器学习的过程中自然踩了无数的坑，也走过很多本不该走的弯路。于是很想总结一份如何入门机器学习的资料，也算是为后来人做一点点微小的贡献。

作为一个转行的人，自然要介绍一下自己的专业背景。笔者在本科的时候的专业是数学与应用数学，外行人可以理解为基础数学。在博士期间的研究方向是动力系统和分形几何，所做的还是基础数学，和计算机的关系不大。如果有人想了解笔者究竟在做什么科研的话，可以参考知乎文章“复动力系统（1）— Fatou集与Julia集”。至于机器学习的话，在读书期间基本上也没接触过，甚至没听说过还有这种东西。不过在读书期间由于专业需要，C++ 之类的代码还是能够写一些的，在 UVA OJ 上面也留下过自己的足迹。

2015 年：尝试转型

行路难，行路难，多歧路，今安在？

在 2015 年毕业之后机缘巧合，恰好进入腾讯公司从事机器学习的相关工作。不过刚进来的时候压力也不小，现在回想起来的话，当时走了一些不该走的弯路。用李白的《行路难》中的诗词来描述当时的心情就是“行路难，行路难，多歧路，今安在？”在 2015 年 10 月份，第一次接触到一个不大不小的项目，那就是 XX 推荐项目。而这个项目是当时组内所接到的第二个推荐项目，当年的推荐系统还是搭建在大数据集群上的，完全没有任何说明文档和前端页面，当时的整个系统和全部流程复杂而繁琐。不过在接触这个系统的过程中，逐步开始学习了 Linux 操作系统的一些简单命令，SQL 的使用方法。了解 SQL 的话其实不只是通过了这个系统，通过当时的 ADS 值班，帮助业务方提取数据，也把 SQL 的基础知识进一步的加深了。SQL 的学习的话，在2015年读过两本非常不错的入门教材《SQL基础教程》与《HIVE编程指南》。Linux 的相关内容阅读了《Linux 命令行与 Shell 脚本编程大全》之后也就大概有所了解了。于是工作了一段时间之后，为了总结一些常见的 SQL 算法，写过一篇文章 “HIVE基础介绍“。

在做推荐项目的过程中，除了要使用 SQL 来处理数据，要想做机器学习，还需要了解常见的机器学习算法。当年接触到的第一个机器学习算法就是逻辑回归（Logistic Regression），既然提到了机器学习的逻辑回归，无法避免的就是交叉验证的概念，这个是机器学习中的一个基本概念。通过物品的类别属性和用户的基本特征来构造出新的特征，例如特征的内积（inner product）。后来在学习的过程中逐步添加了特征的外积和笛卡尔积，除了特征的交叉之外，还有很多的方法来构造特征，例如把特征标准化，归一化，离散化，二值化等操作。除了构造特征之外，如何判断特征的重要性则是一个非常关键的问题。最常见的方法就是查看训练好的模型的权重，另外还可以使用 Pearson 相关系数和 KL 散度等数学工具来粗糙的判断特征是否有效。在此期间也写过一些文章“交叉验证”，“特征工程简介”，“KL散度”。关于特征工程，除了阅读一些必要的书籍之外，最重要的还是要实践，只有实践才能够让自己的经验更加丰富。

在做推荐系统的时候，之前都是通过逻辑回归算法（Logistic Regression）离线地把模型的权重算好，然后导入线上系统，再进行实时的计算和打分。除了离线的算法之外，在 2015 年的 12 月份了解到了能够在线学习的 FTRL 算法。调研了之后在 2016 年初在组内进行了分享，同时在 zr9558.com 上面分享了自己的总结，最近把该文章转移到自己的微信公众号上“Follow the Regularized Leader”。

在做 XX 推荐项目的过程中，了解到了数据才是整个机器学习项目的基石，如果数据的质量不佳，那就需要进行数据的预处理，甚至推动开发人员去解决数据上报的问题。通常来说，要想做好一个推荐项目，除了特征工程和算法之外，最重要的就是数据的核对。当时的经验是需要核对多方的数据，那就是算法离线计算出来的结果，线上计算出来的结果，真实产品中所展示的结果这三方的数据必须要完全一致，一旦不一致，就需要复盘核查，而不是继续推进项目。在此期间，踩过无数的数据的坑，因此得到的经验就是一定要反复的核查数据。

v2-58d234f9633710b627fd7199d233b7d1_hd

2016：从零到一

站在巨人的肩膀上，才能看得更远。-—学习推荐系统

“站在巨人的肩膀上，才能看得更远。”到了 2016 年的 2 月份，除了 XX 推荐项目的首页个性化调优算法之外，还开启了另外一个小项目，尝试开启首页的 tab，那就是针对不同的用户推荐不同的物品。这个小项目简单一点的做法就是使用 ItemCF 或者热传导传播的算法，在用户收听过某个节目之后，就给用户推荐相似的节目。这种场景其实在工业界早就有了成功的案例，也不算是一个新的场景。就好比与用户在某电商网站上看中了某本书，然后就被推荐了其他的相关书籍。之前也写过一篇推荐系统的简单算法“物质扩散算法”，推荐给大家参考一下。至于 ItemCF 和热传导算法的相关内容，会在后续的 Blog 中持续完善。

“读书千遍，其义自见。”在使用整个推荐系统的过程中，笔者只是大概知道了整个系统是如何搭建而成的。而要整体的了解机器学习的相关算法，光做项目则是远远不够的。在做推荐业务的这段时间，周志华老师的教材《机器学习》在2016年初上市，于是花了一些时间来阅读这本书籍。但是个人感觉这本书难度不大，只是需要另外一本书结合着看才能够体会其中的精妙之处，那就是《机器学习实战》。在《机器学习实战》中，不仅有机器学习相关算法的原理描述，还有详细的源代码，这足以让每一个初学者从新手到入门了。

路漫漫其修远兮，吾将上下而求索

说到从零到一，其实指的是在这一年体验了如何从零到一地做一个新业务。到了 2016 年的时候，为了把机器学习引入业务安全领域，在部门内部成立了 XX 项目组，这个项目在部门内部其实并没有做过大规模的尝试，也并没有成功的经验，甚至也没有一个合适的系统让人使用，而且安全业务和推荐业务基本上不是一回事。因为对于推荐系统而言，给用户的推荐是否准确决定了 CTR 是否达标，但是对于安全系统而言，要想上线打击黑产的话，准确率则需要 99% 以上才行。之前的推荐系统用得最多的算法就是逻辑回归，而且会存储物品和用户的两类特征，其余的算法主要还是 ItemCF 和热传导算法。这就导致了当时做 XX 项目的时候，之前的技术方案并不可用，需要基于业务安全的实际场景来重新搭建一套框架体系。

但是当时做安全项目的时候并没有实际的业务经验，而且暂定的计划是基于 XX1 和 XX2 两个业务来进行试点机器学习。为了做好这个项目，一开始笔者调研了几家号称做机器学习+安全的初创公司，其中调研的最多的就是 XX 这家公司，因为他们家发表了一篇文章，里面介绍了机器学习如何应用在业务安全上，那就是搭建一套无监督+有监督+人工打标签的对抗体系。笔者还是总结了当时两三个月所学的异常点检测算法，文章的链接如下：“异常点监测算法（一）”，“异常点检测算法（二）”，“异常点检测算法（三）”，“异常点检测算法综述”。

在 2016 年底的时候，说起来也是机缘巧合，有的同事看到了我在 2016 年 11 月份发表的 KM 文章“循环神经网络”，就来找笔者探讨了一下如何构建游戏 AI。当时笔者对游戏AI的应用场景几乎不了解，只知道 DeepMind 做出了 AlphaGo，在 2013 年使用了深度神经网络玩 Atari 游戏。在12月份花费了一定的时间研究了强化学习和深度学习，也搭建过简单的 DQN 网络进行强化学习的训练。通过几次的接触和交流之后总算 2017 年 1 月份做出一个简单的游戏 AI，通过机器学习也能够进行游戏 AI 的自主学习。虽然不在游戏部门，但是通过这件事情，笔者对游戏 AI 也产生了浓厚的兴趣，撰写过两篇文章“强化学习与泛函分析”，“深度学习与强化学习”。

v2-480b992cb49efc66a880eb4514edaae0_hd

2017 年：再整旗鼓

在做日常项目的同时，在 2017 年也接触量子计算。在后续几个月的工作中，持续调研了量子计算的基础知识，一些量子机器学习的技术方案，写了两篇文章“量子计算（一）”，“量子计算（二）”介绍了量子计算的基础概念和技巧。

三十功名尘与土，八千里路云和月

提到再整旗鼓，其实指的是在 2017 年再次从零到一的做全新的项目。到了 2017 年 7 月份，随着业务安全的机器学习框架已经逐渐完善，XX 项目也快走到了尾声，于是就又有了新的项目到了自己的手里，那就是智能运维项目。运营中心这边还在探索和起步阶段，业界的智能运维（AIOPS）的提出也是在2017年才逐步开始，那就是从手工运维，自动化运维，逐步走向人工智能运维的阶段，也就是所谓的 AIOPS。只有这样，运营中心才有可能实现真正的咖啡运维阶段。

v2-4fcc9c421892c91f9ce9cdd3589a508e_hd

正式接触到运维项目是 2017 年 8 月份，从跟业务运维同学的沟通情况来看，当时有几个业务的痛点和难点。例如：Monitor 时间序列的异常检测，哈勃的根因分析，ROOT 系统的根源分析，故障排查，成本优化等项目。在 AIOPS 人员短缺，并且学术界并不怎么研究这类技术方案的前提下，如何在运维中开展机器学习那就是一个巨大的难题。就像当年有神盾系统，无论怎么做都可以轻松的接入其余推荐业务，并且也有相对成熟的内部经验，学术界和工业界都有无数成功的案例。但是智能运维这一块，在 2017 年才被推广出来，之前都是手工运维和 DevOps 的一些内容。于是，如何尽快搭建一套能够在部门内使用的智能运维体系就成了一个巨大的挑战。面临的难题基本上有以下几点：

1. 历史包袱沉重

2. AIOPS 人员短缺

3. 没有成熟的系统框架

在这种情况下，外部引进技术是不可能了，只能够靠自研，合作的同事主要是业务运维和运营开发。当时第一个接触的智能运维项目就是哈勃的多维下钻分析，其业务场景就是一旦发现了成功率等指标下跌之后，需要从多维的指标中精准的发现异常，例如从运营商，省份，手机等指标中发现导致成功率下跌的原因，这就是经典的根因分析。这一块在调研之后发现，主要几篇文章可以参考，综合考虑了之后撰写了一份资料，那就是“根因分析的探索”。PS：除了哈勃多维下钻之外，个人感觉在 BI 智能商业分析中，其实也可以是这类方法来智能的发现“为什么DAU下跌？”“为什么收入没有达到预期”等问题。

除了哈勃多维下钻之外，Monitor 的时间序列异常检测算法则是更为棘手的项目。之前的 Monitor 异常检测算法，就是靠开发人员根据曲线的特点设定三个阈值（最大值，最小值，波动率）来进行异常检测。这样的结果就是准确率不准，覆盖率不够，人力成本巨大。在上百万条曲线都需要进行异常检测的时候，每一条曲线都需要人工配置阈值是完全不合理的。于是，导致的结果就是每周都需要有人值班，有了问题还不一定能够及时发现。而对于时间序列算法，大家通常能够想到的就是 ARIMA 算法，深度学习的 RNN 与 LSTM 算法，Facebook 近期开源的 Prophet 工具。这些方法笔者都调研过，并且未来会撰写相关的文章介绍 ARIMA，RNN，Prophet 的使用，欢迎大家交流。

其实以上的几种时间序列预测和异常检测算法，主要还是基于单条时间序列来做的，而且基本上是针对那些比较平稳，具有历史规律的时间序列来进行操作的。如果针对每一条曲线都单独搭建一个时间序列模型的话，那和阈值检测没有任何的区别，人力成本依旧巨大。而且在 Monitor 的实际场景下，这些时间序列异常检测模型都有着自身的缺陷，无法做到“百万条KPI曲线一人挑”的效果。于是在经历了很多调研之后，我们创新性的提出了一个技术方案，成功的做到了“百万条曲线”的异常检测就用几个模型搞定。那就是无监督学习的方案加上有监督学习的方案，第一层我们使用无监督算法过滤掉大部分的异常，第二层我们使用了有监督的算法来提升准确率和召回率。在时间序列异常检测的各类算法中，通常的论文里面都是针对某一类时间序列，使用某一类模型，效果可以达到最优。但是在我们的应用场景下，见过的曲线千奇百怪，笔者都说不清楚有多少曲线的形状，因此只用某一类时间序列的模型是绝对不可取的。但是，在学习机器学习的过程中，有一种集成学习的办法，那就是把多个模型的结果作为特征，使用这些特征来训练一个较为通用的模型，从而对所有的 Monitor 时间序列进行异常检测。这一类方法笔者总结过，那就是“时间序列简介（一）”，最终我们做到了“百万条曲线一人挑”，成功去掉了制定阈值的业务效果。

v2-fadf803defdd739088284af0c7ec9039_hd

2018年：走向未来

亦余心之所善兮，虽九死其犹未悔。

在转行的过程中，笔者也走过弯路，体会过排查数据问题所带来的痛苦，经历过业务指标达成所带来的喜悦，感受过如何从零到一搭建一套系统。在此撰写一篇文章来记录笔者这两年多的成长经历，希望能够尽微薄之力帮助到那些有志向转行来做机器学习的人。从这两年做项目的经历来看，要想从零到一地做好项目，在一开始就必须要有一个好的规划，然后一步一步的根据项目的进展调整前进的方向。但是如果没有一个足够的知识积累，就很难找到合适的前进方向。

“亦余心之所善兮，虽九死其犹未悔。”在某些时候会有人为了短期的利益而放弃了一个长远的目标，但是如果要让自己走得更远，最佳的方案是让自己和团队一起成长，最好的是大家都拥有一个长远的目标，不能因为一些微小的波动而放任自己。同时，如果团队或个人急于求成，往往会导致失败，而坚持不懈的学习则是做科研和开展工作的不二法门。

诗人陆游曾经教育过他的后辈：“汝果欲学诗，功夫在诗外”。意思是说，如果你想真正地写出好的诗词，就要在生活上下功夫，去体验生活的酸甜苦辣，而不是抱着一本诗词歌赋来反复阅读。如果看过天龙八部的人就知道，鸠摩智当时上少林寺去挑战，在少林高僧面前展示出自己所学的少林七十二绝技，诸多少林高僧无不大惊失色。而当时的虚竹在旁边观战，就对少林高僧们说：“鸠摩智所耍的招数虽然是少林绝技，但是本质上却是使用小无相功催动出来的。虽然招数相同，但是却用的道家的内力。”为什么少林的高僧们没有看出来鸠摩智武功的关键之处呢，那是因为少林高僧们在练功的时候，一直抱着武学秘籍在修炼，一辈子练到头了也就13门绝技。其实从鸠摩智的个人修炼来看，修练武学的关键并不在武学秘籍里。没有找到关键的佛经，没有找到运功的法门，无论抱着武学秘籍修炼多少年，终究与别人有着本质上的差距。

笔者在 SNG 社交网络运营部的这两年多，用过推荐项目，做过安全项目，正在做运维项目，也算是部门内唯一一个（不知道是否准确）做过三种项目的人，使用过推荐系统，从零到一搭建过两个系统。目前笔者的个人兴趣集中在 AIOPS 这个场景下，因为笔者相信在业务运维这个传统领域，机器学习一定有着自己的用武之地。相信在不久的将来，AIOPS 将会在运维上面的各个场景落地，真正的走向咖啡运维。

v2-b70865721c58f2cb1a53c2ccc2a2f824_hd

张戎

2018年2月

数据挖掘与机器学习

启发式优化算法

April 9, 2018 zr9558 Leave a comment

启发式优化算法的一些调研

启发式优化算法的背景

1. 首先，我们需要有一个目标函数 $f(\bold{x}),$ 其中的 $\bold{x} \in \mathbb{R}^{n}$ ， $n$ 是一个正整数。然后，目标函数 $f(\bold{x})$ 不一定需要是显式的（所谓显式指的是能够精确写出 $f(\bold{x})$ 的表达式，例如逻辑回归的目标函数，神经网络的目标函数，XGBoost 的目标函数等），隐式的目标函数使用启发式优化算法也是可以研究的（即无法写出 $f(\bold{x})$ 表达式）。

2. 其次，需要计算目标函数 $f(\bold{x})$ 的最大值 $\max f(\bold{x})$ 或者最小值 $\min f(\bold{x})$ 。

3. 再次，如果存在多个函数 $f_{i}(\bold{x}), 1\leq i\leq m,$ 并且每一个 $f_{i}(\bold{x})$ 的值域都在 $[0,1]$ 内。如果目标函数是

$\min_{x}(\max_{i}f_{i}(x)-\min_{i}f_{i}(x)),$

希望求该目标函数的最小值，那么意思就是使得每一个 $1\leq i\leq m,$ $f_{i}(\bold{x})$ 在 $\bold{x}$ 的定义域内都相差得不多，也就是这 $m$ 条曲线几乎重合。

4. 拥有目标函数的目的是寻找最优的 $\bold{x}$ 使得它满足 $argmin_{\bold{x}}f(x)$ 或者 $argmax_{\bold{x}}f(x)$ 。

5. 在这里的 $\bold{x}\in \mathbb{R}^{n}$ 一般都是连续的特征，而不是那种类别特征。如果是类别的特征，并不是所有的启发式优化算法都适用，但是遗传算法之类的算法在这种情况下有着一定的用武之地。

启发式优化算法的实验方法

1. 论文中的方法：找到一些形状怪异的函数作为目标函数，需要寻找这些函数的全局最大值或者全局最小值。除了全局的最大最小值点之外，这些函数也有很多局部极值点。例如 Rastrigin 函数（Chapter 6，Example 6.1，Search and Optimization by Metaheuristics）

$\min_{\bold{x}}f(\bold{x}) = 10\cdot n +\sum_{i=1}^{n}(x_{i}^{2}-10\cos(2\pi x_{i})),$

其中， $\bold{x}\in[-5.12,5.12]^{n}.$ 或者 Easom 函数（Chapter 2，Example 2.1，Search and Optimization by Metaheuristics）

$\min_{\bold{x}}f(\bold{x}) = - \cos(x_{1})\cos(x_{2})\exp(-(x_{1}-\pi)^{2}-(x_{2}-\pi)^{2}),$

其中， $\bold{x} \in [-100,100]^{2}.$

2. 最朴素的算法：随机搜索法（Random Search）。也就是把 $\bold{x}$ 的定义域切分成 $m^{n}$ 份，其中 $\bold{x}\in\mathbb{R}^{n}.$ 计算每一个交点的函数取值，然后统计出其最大值或者最小值就可以了。实际中不适用，因为当 $n\geq 100$ 的时候，这个是指数级别的计算复杂度。

3. 启发式优化算法：针对某一个目标函数，使用某种启发式优化算法，然后与随机搜索法做对比，或者与其余的启发式优化算法做对比。

4. 在线调优：启发式优化算法大部分都可以做成实时调优的算法，调优的速度除了算法本身的收敛速度之外，还有给定一个 $\bold{x}$ 之后，获取到 $f(\vec{x})$ 的时间。

注：可以尝试使用启发式优化算法在线调优推荐系统中的 AUC 或者 CTR。不过 CTR 一般具有波动性，需要几个小时甚至一天的数据才能够统计出一个相对靠谱的取值。同时，如果用户量不够多的话，如果切流量的话，可能会造成一些流量的 CTR 偏高，另外一些流量的 CTR 偏低。并且流量的条数会有上限，一般来说不会超过 100 左右，甚至只有 10 个不同的流量。因此，在其余场景下使用这类方法的时候，一定要注意获取目标函数 value 的时间长度。时间长度越短，能够进行的尝试（探索次数）就会越多，收敛的希望就会越大；反之，时间长度越长，能够进行的尝试（探索次数）就会受到限制，收敛的时间长度就会变长。

启发式优化算法的一些常见算法

以下的内容暂时只涉及最基本的算法，有很多算法的变种暂时不做过多的描述。

粒子群算法（Particle Swarm Optimization）

PSO 算法是有一个粒子群，根据群体粒子和单个粒子的最优效果，来调整每一个粒子的下一步行动方向。假设粒子的个数是 $N_{p}$ ，每一个粒子 $\bold{x}_{i}\in \mathbb{R}^{n}$ 都是 $n$ 维欧几里德空间里面的点，同时需要假设粒子的速度 $\bold{v}_{i}\in\mathbb{R}^{n}$ 。在每一轮迭代中，需要更新两个最值，分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值，分别记为 $\bold{x}_{i}^{*}$ （ $1\leq i \leq N_{p}$ ）和 $\bold{x}^{g}$ 。在第 $t+1$ 次迭代的时候，

$\bold{v}_{i}(t+1) = \bold{v}_{i}(t) + c r_{1}[\bold{x}_{i}^{*}(t) - \bold{x}_{i}(t)] + c r_{2}[\bold{x}^{g}(t) - \bold{x}_{i}(t)],$

$\bold{x}_{i}(t+1) = \bold{x}_{i}(t)+\bold{v}_{i}(t+1), \text{ } 1\leq i\leq N_{p}.$

在这里， $c>0$ ，并且 $r_{1}, r_{2}$ 是 $[0,1]$ 中间的随机数。

注：需要解决的问题是如何设置这 $N_{p}$ 个粒子，也就是构造粒子群的问题。在每次只能够设置调整一次 $\bold{x}$ 的时候，可以把时间窗口按照连续的 $N_{p}$ 段来进行切分，在一个时间段内的这 $N_{p}$ 个时间点可以当成 $N_{p}$ 个粒子，然后进行下一轮的迭代即可。

模拟退火（Simulated Annealing）

其核心思想是构造了温度 $T$ 这个维度，当温度 $T$ 高的时候，分子运动速度快，能够探索更多的区域；温度 $T$ 低的时候，分子运动速度慢，能够探索的区域有限。随着时间的迁移，温度 $T$ 会从一个较大的值逐渐降低到 0。

模拟退火的大体思路是这样的：先设置一个较大的温度值 $T$ ，随机初始化 $\bold{x}(0)$ 。假设目标函数是 $E(\bold{x})$ ，需要寻找 $argmin_{\bold{x}}E(\bold{x})$ ，然后执行以下的程序：

Repeat：

a. Repeat:

i. 进行一个随机扰动 $\bold{x} = \bold{x} + \Delta \bold{x}$ ；

ii. 计算 $\Delta E(\bold{x}) = E(\bold{x}+\Delta\bold{x}) - E(\bold{x})$ ，

如果 $\Delta E(\bold{x}) <0$ ，也就是 $E(\bold{x} + \Delta\bold{x})<E(\bold{x})$ ，选择 $\bold{x}+\Delta\bold{x}$ ；

否则，按照 $P = e^{-\Delta E/T}$ 的概率来接受 $\bold{x} +\Delta\bold{x}$ 。

b. 令 $T = T-\Delta T$ 。

直到 $T$ 足够小。

遗传算法的个人理解：

如何选择合适的 $\Delta \bold{x}$ ，可以选择 Gaussian 正态分布，并且可以同时修改 $\bold{x}$ 的 $n$ 个维度，也可以每次只修改一个维度或者部分维度的值；
一开始在温度 $T$ 很大的时候，即使 $E(\bold{x}+\Delta\bold{x})\geq E(\bold{x})$ 的时候，都会以极大概率接受 $E(\bold{x}+\Delta\bold{x})$ ，因为此时 $\lim_{T\rightarrow\infty}e^{-\Delta E/T}=1$ 。然后一开始都在四处游荡；
当温度 $T$ 逐渐降低的时候，当时 $\bold{x}$ 不一定在一个合适的位置，因此，需要记录历史上探索过的满足 $E(\bold{x})$ 最小的值，从历史上的值中选择出一个合适的值继续迭代。因此，在温度下降的时候，如何选择一个合适的值继续迭代可能是一个关键问题。
从遗传算法和 PSO 的对比效果来看，因为 PSO 算法会随时记录当前粒子和所有粒子的最优状态，然后在整个种群中，总会有少数粒子处于当前的最优状态，所以 PSO 的效果从实验效果上来看貌似比不记录状态的遗传算法会好一些。

进化策略（Evolutionary Strategies）

ES 和 GA 有一些方法论上面的不同，这个在书上有论述，等撰写了 GA 在一起看这一块的内容。

进化策略（Evolutionary Strategies）的大体流程与遗传算法（Genetic Algorithm）相似，不同的是 ES 的步骤是交叉/变异（Crossover/Mutation）在前，选择（Selection）在后。

对于经典的进化策略而言，交叉算子（Crossover Operator）可以按照如下定义：两个父代（parents） $\bold{x}_{1}$ 和 $\bold{x}_{2}$ ，那么子代（children）的交叉可以定义为：

$\bold{x}'=(\bold{x}_{1}+\bold{x}_{2})/2,$

这里的相加就是向量之间的相加。

对于经典的进化策略而言，变异算子（Mutation Operator）可以按照如下定义：对于一个向量 $\bold{x} = (x_{1},\cdots,x_{n})$ ，使用 Gaussian 正态分布可以构造出一个后代如下：

$x_{i}'=x_{i}+N(0,\sigma_{i}),\text{ } i=1,\cdots,n,$

这里的 $\sigma_{i}, \text{ } i=1,\cdots,n$ 是基于具体问题的，很难给出一个通用的值。

就经验而谈，ES 算法一般来说比 GA 更加 Robust。在交叉（Crossover）或者变异（Mutation）之后，ES 算法就需要进行选择，通常来说，ES 算法有两种方式，分别是 $(\lambda+\mu)$ 和 $(\lambda,\mu)$ 两种策略。这里的 $\mu$ 表示人口数量（population size）， $\lambda$ 表示从人口中产生的后代的数量。

（1）在 $(\lambda+\mu)$ 策略中，从 $\mu$ 人口中通过变异或者交叉得到 $\lambda$ 个人，然后从这 $(\lambda+\mu)$ 个人中选择出 $\mu$ 个最优的人。 $(\lambda+\mu)$ 是精英策略，每一次迭代都比上一次要好。

（2）在 $(\lambda, \mu)$ 策略中， $\mu$ 个最优的人是从 $\lambda(\lambda\geq\mu)$ 中选择出来的。

传统的梯度搜索法，例如 Newton-Raphson 方法，需要能够计算目标函数 $f(x)$ 的导数，也就是说目标函数必须可导。但是在 Evolutionary Gradient Search 中，不需要 $f(x)$ 是可导的，而是使用导数的近似值来计算。

如果是 $(1,\lambda)-ES$ 的方案，它整体来说其实只有一个人口。从当前的点 $\bold{x}$ 开始，通过 Gaussian Mutation 的方法可以生成 $\lambda$ 个后代，记为 $\bold{t}_{1},\cdots,\bold{t}_{\lambda}$ 。计算它们的函数取值 $f(\bold{t}_{1}),\cdots,f(\bold{t}_{\lambda})$ 。那么估算的梯度就可以计算出来：

$\bold{g}=\sum_{i=1}^{\lambda}(f(\bold{t}_{i})-f(\bold{x}))(\bold{t}_{i}-\bold{x}),$

归一化之后得到 $\bold{e}=\bold{g}/||\bold{g}||.$

Evolutionary gradient search 生成了两个点，分别是：

$\bold{x}_{1}=\bold{x}+(\sigma \psi)\bold{e}, \bold{x}_{2}=\bold{x}+(\sigma/\psi)\bold{e},$

这里的 $\psi>1.$ 新的个体定义为: $\bold{x}'=\bold{x}+\sigma'\bold{e}.$ 如果 $f(\bold{x}_{1})>f(\bold{x}_{2}),$ 那么 $\sigma' = \sigma\psi;$ 如果 $f(\bold{x}_{1})\leq f(\bold{x}_{2}),$ 那么 $\sigma'=\sigma/\psi.$

进化策略（ES）包括 gradient search 和 gradient evolution，并且 covariance matrix adaptation（CMA）ES 在一定的限制条件下加速了搜索的效率。

参考资料：

Search and Optimization by Metaheuristics，Kelin DU, M.N.S. SWAMY，2016年

时间序列, 智能运维

时间序列的自回归模型—从线性代数的角度来看

March 23, 2018 zr9558 Leave a comment

Fibonacci 序列

在开始讲解时间序列的自回归模型（AutoRegression Model）之前，我们需要先介绍一下线性代数的基础知识。为了介绍线性代数的基础知识，我们可以先看一个简单的例子。考虑整数序列 Fibonacci 序列，它的通项公式是一个递归函数，每项的取值是由前两项所生成的，其具体的公式就是

$F_{n}=F_{n-1}+F_{n-2}$ ，

其初始值是 $F_{0}=0, F_{1} = 1$ 。按照其递归公式来计算，我们可以详细写出前面的几项，那就是：

0，1，1，2，3，5，8，13，21，34，55，89，144，…

但是，计算 Fibonacci 的通项公式则比计算等差数列和等比数列的通项公式复杂的多，因为这里需要使用线性代数的技巧才能解决这个问题。

求解 Fibonacci 序列的通项公式－－－矩阵对角化

根据 Fibonacci 数列的递归公式，基于矩阵乘法的定义，Fibonacci 序列可以写成如下形式：

$\left( \begin{array}{c} F_{n+2} \\ F_{n+1} \\ \end{array}\right)= \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array}\right) \left( \begin{array}{c} F_{n+1} \\ F_{n} \\ \end{array}\right) = A \left( \begin{array}{c} F_{n+1} \\ F_{n} \\ \end{array}\right),$

$\left( \begin{array}{c} F_{n} \\ F_{n-1} \\ \end{array}\right)= A \left( \begin{array}{c} F_{n-1} \\ F_{n-2} \\ \end{array}\right) = \cdots = A^{n-1} \left( \begin{array}{c} F_{1} \\ F_{0} \\ \end{array}\right).$

这就意味着我们需要计算出矩阵 A 的幂。在线性代数里面，为了计算矩阵的 n 次方，除了通过矩阵乘法的公式直接计算之外，还有一个经典的技巧，那就是将矩阵对角化。详细来说，如果 $m\times m$ 的矩阵 A 能够对角化，那就是存在可逆矩阵 P 使得

$P^{-1}AP = diag(\lambda_{1},\cdots,\lambda_{m})$

$\implies AP = P diag(\lambda_{1},\cdots,\lambda_{m})$

$\implies A = P diag(\lambda_{1},\cdots,\lambda_{m})P^{-1}.$

其中 $D = diag(\lambda_{1},\cdots,\lambda_{m})$ 表示一个 $m\times m$ 的对角矩阵，其对角的元素从左上角到右下角依次是 $\lambda_{1},\cdots,\lambda_{m}$ 。如果把矩阵 P 写成列向量的形式，i.e. $P =(\vec{\alpha}_{1},\cdots,\vec{\alpha}_{m})$ ，那么以上的矩阵方程就可以转换为 $A\vec{\alpha}_{i} = \lambda_{i}\vec{\alpha}_{i}$ , $1\leq i\leq m$ 。进一步来说，如果要计算矩阵 A 的幂，就可以得到：

$A^{k} = (PDP^{-1})\cdots(PDP^{-1}) = P D^{k} P^{-1}= P diag(\lambda_{1}^{k},\cdots,\lambda_{m}^{k})P^{-1}.$

另外，如果想知道一个矩阵 A 的特征值和特征向量，则需要计算以下多项式的根，i.e. 计算关于 $\lambda$ 的多项式的解，

$det(\lambda I - A) = 0,$

其中 I 是一个单位矩阵（identity matrix）。

按照以上的思路，如果令

$A = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array}\right)$ ,

可以计算出 A 的两个特征值分别是 $\phi=(1+\sqrt{5})/2$ 和 $- \phi^{-1} = (1-\sqrt{5})/2$ ，它们所对应的特征向量分别是：

$\vec{\alpha}_{1} = (\phi,1)^{T}, \vec{\alpha}_{2} = (-\phi^{-1},1)$ .

因此直接计算可以得到

$F_{k} = \frac{1}{\sqrt{5}}\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k} - \frac{1}{\sqrt{5}}\bigg(\frac{1-\sqrt{5}}{2}\bigg)^{k}=\frac{\phi^{k}-(-\phi)^{-k}}{\sqrt{5}}$ .

通过上面的计算方法，为了计算 Fibonacci 数列的通项公式，我们可以先把它转换成一个矩阵求幂的问题，于是我们就能矩阵对角化的方法把 Fibonacci 数列的通项公式求出来。

时间序列的弱平稳性

要讲解自回归模型，就必须提到时间序列的弱平稳性。一个时间序列 $\{x_{t}\}_{t\geq 0}$ 具有弱平稳性（Weak Stationary）指的是：

$E(x_{t})$ 对于所有的 $t\geq 0$ 都是恒定的；
$Var(x_{t})$ 对于所有的 $t\geq 0$ 都是恒定的；
$x_{t}$ 与 $x_{t-h}$ 的协方差对于所有的 $t\geq 0$ 都是恒定的。

另外，时间序列的自相关方程（AutoCorrelation Function）指的是对于 $h = 1,2,3,\cdots$ ，可以定义 ACF 为

$ACF(x_{t},x_{t-h}) = \frac{Covariance(x_{t},x_{t-h})}{\sqrt{Var(x_{t})\cdot Var(x_{t-h})}}$ .

如果时间序列 $\{x_{t}\}_{t\geq 0}$ 在弱平稳性的假定下，ACF 将会简化为

$ACF(x_{t},x_{t-h}) = \frac{Covariance(x_{t},x_{t-h})}{Var(x_{t})}$ .

时间序列的自回归模型（AutoRegression Model）

AR(1) 模型

AR(1) 模型指的是时间序列 $\{x_{t}\}_{t\geq 0}$ 在时间戳 $t$ 时刻的取值 $x_{t}$ 与时间戳 $t - 1$ 时刻的取值 $x_{t-1}$ 相关，其公式就是：

$x_{t}=\delta+\phi_{1}x_{t-1}+w_{t}$ ，

这个时间序列 $\{x_{t}\}_{t\geq 0}$ 满足如下条件：

$w_{t}\sim N(0,\sigma_{w}^{2})$ ，并且 $w_{t}$ 满足 iid 条件。其中 $N(0,\sigma_{w}^{2})$ 表示 Gauss 正态分布，它的均值是0，方差是 $\sigma_{w}^{2}$ 。
$w_{t}$ 与 $x_{t}$ 是相互独立的（independent）。
$x_{0},x_{1},\cdots$ 是弱平稳的，i.e. 必须满足 $|\phi_{1}|<1$ 。

如果选择初始条件 $x_{0}=1$ ，则可以得到一些 AR(1) 模型的例子如下图所示：

AR Models

从 AR(1) 以上的定义出发，我们可以得到：

$E(x_{t}) = \delta/(1-\phi_{1})$ .
$Var(x_{t}) = \sigma_{w}^{2}/(1-\phi_{1}^{2})$ .
$Covariance(x_{t},x_{t-h}) = \phi_{1}^{h}$ .

Proof of 1. 从 AR(1) 的模型出发，可以得到

$E(x_{t}) = E(\delta + \phi_{1}x_{t-1}+w_{t}) = \delta + \phi_{1}E(x_{t-1}) = \delta + \phi_{1}E(x_{t})$ ,

从而， $E(x_{t}) = \delta/(1-\phi_{1})$ .

Proof of 2. 从 AR(1) 的模型出发，可以得到

$Var(x_{t}) = Var(\delta + \phi_{1}x_{t-1}+w_{t})$

$= \phi_{1}^{2}Var(x_{t-1}) +Var(w_{t}) = \phi_{1}^{2}Var(x_{t}) + \sigma_{w}^{2}$ ,

从而， $Var(x_{t}) =\sigma_{w}^{2}/(1-\phi_{1}^{2})$ .

Proof of 3. 令 $\mu = E(x_{t}), \forall t\geq 0$ . 从 $x_{t}$ 的定义出发，可以得到：

$x_{t}-\mu = \phi_{1}(x_{t-1}-\mu)+w_{t}$

$= \phi_{1}^{h}(x_{t-h}-\mu) + \phi_{1}^{h-1}w_{t-h+1}+\cdots+\phi_{1}w_{t-1}+w_{t},$

从而，

$\rho_{h} = Covariance(x_{t},x_{t-h}) = \frac{E((x_{t}-\mu)\cdot(x_{t-h}-\mu))}{Var(x_{t})}=\phi_{1}^{h}$ .

AR(1) 模型与一维动力系统

特别的，如果假设 $w_{t}$ 恒等于零，就可以得到 $x_{t} =\delta + \phi_{1}x_{t-1}$ 对于所有的 $t\geq 1$ 都成立。也就是可以写成一个一维函数的迭代公式：

$f(x) = \phi_{1}x + \delta,$

下面我们要计算 $f^{n}(x)$ 的收敛性，这里的 $f^{n}(x) = f\circ\cdots\circ f(x)$ 表示函数 $f$ 的 $n$ 次迭代。

Method 1.

通过 $f(x)$ 的定义直接计算可以得到：

$f^{n}(x) = \phi_{1}^{n}x+ \frac{1-\phi_{1}^{n}}{1-\phi_{1}}\delta$ ,

令 $n\rightarrow \infty$ ，可以得到 $f^{n}(x)\rightarrow \delta/(1-\phi_{1})$ 。这与 $E(x_{t}) = \delta/(1-\phi_{1})$ 其实是保持一致的。

另外，如果 $|\phi_{1}|>1$ ，可以从公式上得到 $f^{n}(x) \rightarrow \infty$ 当 $n\rightarrow \infty$ 。

Method 2.

将原函数转换成 Lipschitz 函数的形式，i.e. 如果 $|\phi_{1}|<1$ ，那么

$f(x)-\frac{\delta}{1-\phi_{1}} = \phi_{1}(x-\frac{\delta}{1-\phi_{1}})$

$\implies |f(x)-\frac{\delta}{1-\phi_{1}}| <\frac{1+|\phi_{1}|}{2}\cdot|x-\frac{\delta}{1-\phi_{1}}|$

$\implies |f^{n}(x)-\frac{\delta}{1-\phi_{1}}|<\bigg(\frac{1+|\phi_{1}|}{2}\bigg)^{n}\cdot|x-\frac{\delta}{1-\phi_{1}}|$ .

因为 $(1+|\phi_{1}|)/2<1$ ，我们可以得到 $\lim_{n\rightarrow\infty}f^{n}(x)=\delta/(1-\phi_{1})$ . i.e. $f^{n}(x)$ 趋近于 $\delta/(1-\phi_{1})$ .

反之，如果 $|\phi_{1}|>1$ ，很容易得到

$f(x)-\frac{\delta}{1-\phi_{1}} = \phi_{1}(x-\frac{\delta}{1-\phi_{1}})$

$\implies |f(x)-\frac{\delta}{1-\phi_{1}}| >\frac{1+|\phi_{1}|}{2}\cdot|x-\frac{\delta}{1-\phi_{1}}|$

$\implies |f^{n}(x)-\frac{\delta}{1-\phi_{1}}|>\bigg(\frac{1+|\phi_{1}|}{2}\bigg)^{n}\cdot|x-\frac{\delta}{1-\phi_{1}}|$ .

因此，在 $|\phi_{1}|>1$ 这种条件下， $f^{n}(x)\rightarrow \infty$ as $n\rightarrow \infty$ . 特别地，对于一阶差分方程 $x_{t} =\delta + \phi_{1}x_{t-1}$ 而言，如果 $|\phi_{1}|>1$ ，那么 $x_{t}$ 的取值会越来越大，这与现实的状况不相符，所以在时间序列的研究中，一般都会假设 $|\phi_{1}|<1$ 。

AR(p) 模型

按照之前类似的定义，可以把 AR(1) 模型扩充到 AR(p) 模型，也就是说：

1. AR(1) 模型形如：

$x_{t}=\delta+\phi_{1}x_{t-1}+w_{t}.$

2. AR(2) 模型形如：

$x_{t} = \delta + \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+w_{t}.$

3. AR(p) 模型形如：

$x_{t} = \delta + \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+\cdots+\phi_{p}x_{t-p}+w_{t}.$

AR(p) 模型的稳定性－－－基于线性代数

对于 AR(2) 模型，可以假定 $\delta = 0$ 并且忽略误差项，因此可以得到简化版的模型形如：

$x_{t}= \phi_{1}x_{t-1} + \phi_{2}x_{t-2}$ .

写成矩阵的形式形如：

$\left( \begin{array}{c} x_{t+2} \\ x_{t+1} \\ \end{array}\right)= \left( \begin{array}{cc} \phi_{1} & \phi_{2} \\ 1 & 0 \\ \end{array}\right) \left( \begin{array}{c} x_{t+1} \\ x_{t} \\ \end{array}\right) = A \left( \begin{array}{c} x_{t+1} \\ x_{t} \\ \end{array}\right).$

求解其特征多项式则是基于 $det(\lambda I - A) = 0$ ，求解可以得到 $\lambda^{2}-\phi_{1}\lambda - \phi_{2} =0$ ，i.e. $A^{k} = P diag(\lambda_{1}^{k}, \lambda_{2}^{k})P^{-1}$ 。当 $\lambda_{1}, \lambda_{2}$ 都在单位圆内部的时候，也就是该模型 $x_{t+2} = \phi_{1}x_{t+1}+\phi_{2}x_{t}$ 满足稳定性的条件。

对于更加一般的 AR(p) 模型，也就是考虑 p 阶差分方程

$x_{t} = \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+\cdots+\phi_{p}x_{t-p}.$

可以用同样的方法将其转换成矩阵的形式，那就是：

$\left(\begin{array}{c} x_{t+p} \\ x_{t+p-1} \\ \vdots \\ x_{t+1}\\ \end{array}\right) = \left(\begin{array}{ccccc} \phi_{1} & \phi_{2} &\cdots & \phi_{p-1} & \phi_{p} \\ 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{array}\right) \left(\begin{array}{c} x_{t+p-1} \\ x_{t+p-2} \\ \vdots \\ x_{t} \\ \end{array}\right) = A \left(\begin{array}{c} x_{t+p-1} \\ x_{t+p-2} \\ \vdots \\ x_{t} \\ \end{array}\right)$

计算 $det(\lambda I - A) = 0$ ，可以得到其特征多项式为：

$\lambda^{p}-\phi_{1}\lambda^{p-1}-\phi_{2}\lambda^{p-2}-\cdots-\phi_{p}=0.$

当每个特征值都在单位圆盘内部的时候，i.e. $|\lambda_{i}|<1, \forall 1\leq i\leq p$ ，该 p 阶差分方程

$x_{t} = \phi_{1}x_{t-1}+\phi_{2}x_{t-2}+\cdots+\phi_{p}x_{t-p}$

存在稳定性的解。

数据集的情况

ADS 的系统架构

ADS 的细节

Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection

预处理模块（Preprocessing）

基线提取模块（Baseline Extraction）

基于密度的聚类算法（Clustering）

实时分类（Assignment）

聚类与时间序列异常检测

Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection

典型案例

数学描述

按比例投注

一般形式（一）

一般形式（二）

结论

CV，NLP & Speech Recognition

机器学习

机器学习+安全业务

机器学习+运维业务

机器学习+其他领域

25 岁的时候

选择比努力更重要

自我的成长

专业的问题

明确不想做的事情

循序渐进

融入圈子

避免坑人

自编码器

时间序列异常检测：

总结

参考文献

高考志愿

剑宗与气宗

数学的作用

助教开始

助教生涯

助教故事

黑盒函数的定义

黑盒函数的研究对象

黑盒函数的根

二分法

牛顿法（Newton’s Method）

割线法

备注

黑盒函数的最大值与最小值

Weierstrass 逼近定理

Lagrange 插值公式

粒子群算法（Particle Swarm Optimization）

模拟退火（Simulated Annealing）

总结

Riemann Zeta 函数定义域的延拓

Riemann Zeta 函数的非零区域

区域

直线

总结

Riemann Zeta 函数

调和级数的概念与性质

调和级数的推广

Riemann Zeta 函数中某些点的取值

总结

启发式优化算法的一些调研

启发式优化算法的背景

启发式优化算法的实验方法

启发式优化算法的一些常见算法

粒子群算法（Particle Swarm Optimization）

模拟退火（Simulated Annealing）

进化策略（Evolutionary Strategies）

参考资料：

Fibonacci 序列

求解 Fibonacci 序列的通项公式 －－－ 矩阵对角化

时间序列的弱平稳性

时间序列的自回归模型（AutoRegression Model）

AR(1) 模型

AR(1) 模型与一维动力系统

AR(p) 模型

AR(p) 模型的稳定性 －－－ 基于线性代数

zr9558's Blog

$\Re(s)>1$ 区域

$\Re(s) =1$ 直线

求解 Fibonacci 序列的通项公式－－－矩阵对角化

AR(p) 模型的稳定性－－－基于线性代数