Category Archives: Computer Science

Facebook 时间序列预测算法 Prophet 的研究

Prophet 简介

Facebook 去年开源了一个时间序列预测的算法,叫做 fbprophet,它的官方网址与基本介绍来自于以下几个网站:

  1. Github:https://github.com/facebook/prophet
  2. 官方网址:https://facebook.github.io/prophet/
  3. 论文名字与网址:Forecasting at scale,https://peerj.com/preprints/3190/

从官网的介绍来看,Facebook 所提供的 prophet 算法不仅可以处理时间序列存在一些异常值的情况,也可以处理部分缺失值的情形,还能够几乎全自动地预测时间序列未来的走势。从论文上的描述来看,这个 prophet 算法是基于时间序列分解和机器学习的拟合来做的,其中在拟合模型的时候使用了 pyStan 这个开源工具,因此能够在较快的时间内得到需要预测的结果。除此之外,为了方便统计学家,机器学习从业者等人群的使用,prophet 同时提供了 R 语言和 Python 语言的接口。从整体的介绍来看,如果是一般的商业分析或者数据分析的需求,都可以尝试使用这个开源算法来预测未来时间序列的走势。

Prophet 的算法原理

Prophet 数据的输入和输出

prophetexample1

首先让我们来看一个常见的时间序列场景,黑色表示原始的时间序列离散点,深蓝色的线表示使用时间序列来拟合所得到的取值,而浅蓝色的线表示时间序列的一个置信区间,也就是所谓的合理的上界和下界。prophet 所做的事情就是:

  1. 输入已知的时间序列的时间戳和相应的值;
  2. 输入需要预测的时间序列的长度;
  3. 输出未来的时间序列走势。
  4. 输出结果可以提供必要的统计指标,包括拟合曲线,上界和下界等。

就一般情况而言,时间序列的离线存储格式为时间戳和值这种格式,更多的话可以提供时间序列的 ID,标签等内容。因此,离线存储的时间序列通常都是以下的形式。其中 date 指的是具体的时间戳,category 指的是某条特定的时间序列 id,value 指的是在 date 下这个 category 时间序列的取值,label 指的是人工标记的标签(’0′ 表示异常,’1‘ 表示正常,’unknown’ 表示没有标记或者人工判断不清)。

prophetexample2.png

而 fbprophet 所需要的时间序列也是这种格式的,根据官网的描述,只要用 csv 文件存储两列即可,第一列的名字是 ‘ds’, 第二列的名称是 ‘y’。第一列表示时间序列的时间戳,第二列表示时间序列的取值。通过 prophet 的计算,可以计算出 yhat,yhat_lower,yhat_upper,分别表示时间序列的预测值,预测值的下界,预测值的上界。两份表格如下面的两幅图表示。

prophetexample3

prophetexample4

Prophet 的算法实现

在时间序列分析领域,有一种常见的分析方法叫做时间序列的分解(Decomposition of Time Series),它把时间序列 y_{t} 分成几个部分,分别是季节项 S_{t},趋势项 T_{t},剩余项 R_{t}。也就是说对所有的 t\geq 0,都有

y_{t} = S_{t} + T_{t} + R_{t}.

除了加法的形式,还有乘法的形式,也就是:

y_{t} = S_{t} \times T_{t} \times R_{t}.

以上式子等价于 \ln y_{t} = \ln S_{t} + \ln T_{t} + \ln R_{t}。所以,有的时候在预测模型的时候,会先取对数,然后再进行时间序列的分解,就能得到乘法的形式。在 fbprophet 算法中,作者们基于这种方法进行了必要的改进和优化。

一般来说,在实际生活和生产环节中,除了季节项,趋势项,剩余项之外,通常还有节假日的效应。所以,在 prophet 算法里面,作者同时考虑了以上四项,也就是:

y(t) = g(t) + s(t) + h(t) + \epsilon_{t}.

其中 g(t) 表示趋势项,它表示时间序列在非周期上面的变化趋势;s(t) 表示周期项,或者称为季节项,一般来说是以周或者年为单位;h(t) 表示节假日项,表示在当天是否存在节假日;\epsilon_{t} 表示误差项或者称为剩余项。Prophet 算法就是通过拟合这几项,然后最后把它们累加起来就得到了时间序列的预测值。

趋势项模型 g(t)

在 Prophet 算法里面,趋势项有两个重要的函数,一个是基于逻辑回归函数(logistic function)的,另一个是基于分段线性函数(piecewise linear function)的。

首先,我们来介绍一下基于逻辑回归的趋势项是怎么做的。

如果回顾逻辑回归函数的话,一般都会想起这样的形式:\sigma(x) = 1/(1+e^{-x}), 它的导数是 \sigma'(x) = \sigma(x) \cdot(1-\sigma(x)), 并且 \lim_{x\rightarrow +\infty} \sigma(x) = 1, \lim_{x\rightarrow -\infty} \sigma(x) = 0. 如果增加一些参数的话,那么逻辑回归就可以改写成:

f(x) = C / (1 + e^{-k(x-m)}),

这里的 C 称为曲线的最大渐近值,k 表示曲线的增长率,m 表示曲线的中点。当 C=1, k = 1, m =0 时,恰好就是大家常见的 sigmoid 函数的形式。从 sigmoid 的函数表达式来看,它满足以下的微分方程:y'=y(1-y)

那么,如果使用分离变量法来求解微分方程 y'=y(1-y) 就可以得到:

\frac{y'}{y} + \frac{y'}{1-y} = 1 \Rightarrow \ln\frac{y}{1-y} = 1 \Rightarrow y = 1/(1+K e^{-x}).

但是在现实环境中,函数 f(x) = C / (1+e^{-k(x-m)}) 的三个参数 C, k, m 不可能都是常数,而很有可能是随着时间的迁移而变化的,因此,在 Prophet 里面,作者考虑把这三个参数全部换成了随着时间而变化的函数,也就是 C = C(t), k = k(t), m = m(t)

除此之外,在现实的时间序列中,曲线的走势肯定不会一直保持不变,在某些特定的时候或者有着某种潜在的周期曲线会发生变化,这种时候,就有学者会去研究变点检测,也就是所谓 change point detection。例如下面的这幅图的 t_{1}^{*}, t_{2}^{*} 就是时间序列的两个变点。

prophetchangepoint1

在 Prophet 里面,是需要设置变点的位置的,而每一段的趋势和走势也是会根据变点的情况而改变的。在程序里面有两种方法,一种是通过人工指定的方式指定变点的位置;另外一种是通过算法来自动选择。在默认的函数里面,Prophet 会选择 n_changepoints = 25 个变点,然后设置变点的范围是前 80%(changepoint_range),也就是在时间序列的前 80% 的区间内会设置变点。通过 forecaster.py 里面的 set_changepoints 函数可以知道,首先要看一些边界条件是否合理,例如时间序列的点数是否少于 n_changepoints 等内容;其次如果边界条件符合,那变点的位置就是均匀分布的,这一点可以通过 np.linspace 这个函数看出来。

下面假设已经放置了 S 个变点了,并且变点的位置是在时间戳 s_{j}, 1\leq j\leq S 上,那么在这些时间戳上,我们就需要给出增长率的变化,也就是在时间戳 s_{j} 上发生的 change in rate。可以假设有这样一个向量:\boldsymbol{\delta}\in\mathbb{R}^{S}, 其中 \delta_{j} 表示在时间戳 s_{j} 上的增长率的变化量。如果一开始的增长率我们使用 k 来代替的话,那么在时间戳 t 上的增长率就是 k + \sum_{j:t>s_{j}} \delta_{j},通过一个指示函数 \mathbf{a}(t)\in \{0,1\}^{S} 就是

a_{j}(t) = \begin{cases} 1, \text{ if } t\geq s_{j},\\ 0, \text{ otherwise.} \end{cases}

那么在时间戳 t 上面的增长率就是 k + \mathbf{a}^{T}\boldsymbol{\delta}. 一旦变化量 k 确定了,另外一个参数 m 也要随之确定。在这里需要把线段的边界处理好,因此通过数学计算可以得到:

\gamma_{j} = \bigg(s_{j} - m - \sum_{\ell <j} \gamma_{\ell} \bigg) \cdot \bigg( 1- \frac{k + \sum_{\ell < j} \delta_{\ell}}{k + \sum_{\ell\leq j}\delta_{\ell}} \bigg).

所以,分段的逻辑回归增长模型就是:

g(t) = \frac{C(t)}{1+exp(-(k+\boldsymbol{a}(t)^{t}\boldsymbol{\delta}) \cdot (t - (m+\boldsymbol{a}(t)^{T}\boldsymbol{\gamma})},

其中,

\boldsymbol{a}(t) = (a_{1}(t),\cdots,a_{S}(t))^{T},  \boldsymbol{\delta} = (\delta_{1},\cdots,\delta_{S})^{T}, \boldsymbol{\gamma} = (\gamma_{1},\cdots,\gamma_{S})^{T}.

在逻辑回归函数里面,有一个参数是需要提前设置的,那就是 Capacity,也就是所谓的 C(t) ,在使用 Prophet 的 growth = ‘logistic’ 的时候,需要提前设置好 C(t) 的取值才行。

再次,我们来介绍一下基于分段线性函数的趋势项是怎么做的。众所周知,线性函数指的是 y=kx+b, 而分段线性函数指的是在每一个子区间上,函数都是线性函数,但是在整段区间上,函数并不完全是线性的。正如下图所示,分段线性函数就是一个折线的形状。

prophetpiecewiselinear1

因此,基于分段线性函数的模型形如:

g(t)=(k+\boldsymbol{a}(t)\boldsymbol{\delta})\cdot t+(m+\boldsymbol{a}(t)^{T}\boldsymbol{\gamma}),

其中 k 表示增长率(growth rate),\boldsymbol{\delta} 表示增长率的变化量,m 表示 offset parameter。而这两种方法(分段线性函数与逻辑回归函数)最大的区别就是 \boldsymbol{\gamma} 的设置不一样,在分段线性函数中,\boldsymbol{\gamma}=(\gamma_{1},\cdots,\gamma_{S})^{T}, \gamma_{j}=-s_{j}\delta_{j}. 注意:这与之前逻辑回归函数中的设置是不一样的。

在 prophet 的源代码中,forecast.py 这个函数里面包含了最关键的步骤,其中 piecewise_logistic 函数表示了前面所说的基于逻辑回归的增长函数,它的输入包含了 cap 这个指标,因此需要用户事先指定 capacity。而在 piecewise_linear 这个函数中,是不需要 capacity 这个指标的,因此 m = Prophet() 这个函数默认的使用 growth = ‘linear’ 这个增长函数,也可以写作 m = Prophet(growth = ‘linear’);如果想用 growth = ‘logistic’,就要这样写:

m = Prophet(growth='logistic')
df['cap'] = 6
m.fit(df)
future = m.make_future_dataframe(periods=prediction_length, freq='min')
future['cap'] = 6

变点的选择(Changepoint Selection)

在介绍变点之前,先要介绍一下 Laplace 分布,它的概率密度函数为:

f(x|\mu, b) = exp\bigg(-|x-\mu|/b\bigg)/2b,

其中 \mu 表示位置参数,b>0 表示尺度参数。Laplace 分布与正态分布有一定的差异。

在 Prophet 算法中,是需要给出变点的位置,个数,以及增长的变化率的。因此,有三个比较重要的指标,那就是

  1. changepoint_range,
  2. n_changepoint,
  3. changepoint_prior_scale。

changepoint_range 指的是百分比,需要在前 changepoint_range 那么长的时间序列中设置变点,在默认的函数中是 changepoint_range = 0.8。n_changepoint 表示变点的个数,在默认的函数中是 n_changepoint = 25。changepoint_prior_scale 表示变点增长率的分布情况,在论文中, \delta_{j} \sim Laplace(0,\tau),这里的 \tau 就是 change_point_scale。

在整个开源框架里面,在默认的场景下,变点的选择是基于时间序列的前 80% 的历史数据,然后通过等分的方法找到 25 个变点(change points),而变点的增长率是满足 Laplace 分布 \delta_{j} \sim Laplace (0,0.05) 的。因此,当 \tau 趋近于零的时候,\delta_{j} 也是趋向于零的,此时的增长函数将变成全段的逻辑回归函数或者线性函数。这一点从 g(t) 的定义可以轻易地看出。

对未来的预估(Trend Forecast Uncertainty)

从历史上长度为 T 的数据中,我们可以选择出 S 个变点,它们所对应的增长率的变化量是 \delta_{j} \sim Laplace(0,\tau)。此时我们需要预测未来,因此也需要设置相应的变点的位置,从代码中看,在 forecaster.py 的 sample_predictive_trend 函数中,通过 Poisson 分布等概率分布方法找到新增的 changepoint_ts_new 的位置,然后与 changepoint_t 拼接在一起就得到了整段序列的 changepoint_ts。

changepoint_ts_new = 1 + np.random.rand(n_changes) * (T - 1)
changepoint_ts = np.concatenate((self.changepoints_t, changepoint_ts_new))

第一行代码的 1 保证了 changepoint_ts_new 里面的元素都大于 change_ts 里面的元素。除了变点的位置之外,也需要考虑 \delta 的情况。这里令 \lambda = \sum_{j=1}^{S}|\delta_{j}|/S,于是新的增长率的变化量就是按照下面的规则来选择的:当 j>T 时,

\delta_{j}=\begin{cases} 0 \text{, with probability } (T-S)/T \\ \sim Laplace(0,\lambda) \text{, with probability } S/T \end{cases}.

季节性趋势

几乎所有的时间序列预测模型都会考虑这个因素,因为时间序列通常会随着天,周,月,年等季节性的变化而呈现季节性的变化,也称为周期性的变化。对于周期函数而言,大家能够马上联想到的就是正弦余弦函数。而在数学分析中,区间内的周期性函数是可以通过正弦和余弦的函数来表示的:假设 f(x) 是以 2\pi 为周期的函数,那么它的傅立叶级数就是 a_{0} + \sum_{n=1}^{\infty}(a_{n}\cos(nx) + b_{n}\sin(nx))

在论文中,作者使用傅立叶级数来模拟时间序列的周期性。假设 P 表示时间序列的周期,P = 365.25 表示以年为周期,P = 7 表示以周为周期。它的傅立叶级数的形式都是:

s(t) = \sum_{n=1}^{N}\bigg( a_{n}\cos\bigg(\frac{2\pi n t}{P}\bigg) + b_{n}\sin\bigg(\frac{2\pi n t}{P}\bigg)\bigg).

就作者的经验而言,对于以年为周期的序列(P = 365.25)而言,N = 10;对于以周为周期的序列(P = 7 )而言,N = 3。这里的参数可以形成列向量:

\boldsymbol{\beta} = (a_{1},b_{1},\cdots,a_{N},b_{N})^{T}

N = 10 时,

X(t) = \bigg[\cos(\frac{2\pi(1)t}{365.25}),\cdots,\sin(\frac{2\pi(10)t}{365.25})\bigg]

N = 3 时,

X(t) = \bigg[\cos(\frac{2\pi(1)t}{7}),\cdots,\sin(\frac{2\pi(3)t}{7})\bigg]

因此,时间序列的季节项就是:s(t) = X(t) \boldsymbol{\beta},\boldsymbol{\beta} 的初始化是 \boldsymbol{\beta} \sim Normal(0,\sigma^{2})。这里的 \sigma 是通过 seasonality_prior_scale 来控制的,也就是说 \sigma= seasonality_prior_scale。这个值越大,表示季节的效应越明显;这个值越小,表示季节的效应越不明显。同时,在代码里面,seasonality_mode 也对应着两种模式,分别是加法和乘法,默认是加法的形式。在开源代码中,X(t) 函数是通过 fourier_series 来构建的。

节假日效应(holidays and events)

在现实环境中,除了周末,同样有很多节假日,而且不同的国家有着不同的假期。在 Prophet 里面,通过维基百科里面对各个国家的节假日的描述,hdays.py 收集了各个国家的特殊节假日。除了节假日之外,用户还可以根据自身的情况来设置必要的假期,例如 The Super Bowl,双十一等。

prophetholiday1.png

由于每个节假日对时间序列的影响程度不一样,例如春节,国庆节则是七天的假期,对于劳动节等假期来说则假日较短。因此,不同的节假日可以看成相互独立的模型,并且可以为不同的节假日设置不同的前后窗口值,表示该节假日会影响前后一段时间的时间序列。用数学语言来说,对与第 i 个节假日来说, D_{i} 表示该节假日的前后一段时间。为了表示节假日效应,我们需要一个相应的指示函数(indicator function),同时需要一个参数 \kappa_{i} 来表示节假日的影响范围。假设我们有 L 个节假日,那么

h(t)=Z(t) \boldsymbol{\kappa}=\sum_{i=1}^{L} \kappa_{i}\cdot 1_{\{t\in D_{i}\}},

其中 Z(t)=(1_{\{t\in D_{1}\}},\cdots,1_{\{t\in D_{L}\}})\boldsymbol{\kappa}=(\kappa_{1},\cdots,\kappa_{L})^{T}.

其中 \boldsymbol{\kappa}\sim Normal(0,v^{2}) 并且该正态分布是受到 v = holidays_prior_scale 这个指标影响的。默认值是 10,当值越大时,表示节假日对模型的影响越大;当值越小时,表示节假日对模型的效果越小。用户可以根据自己的情况自行调整。

模型拟合(Model Fitting)

按照以上的解释,我们的时间序列已经可以通过增长项,季节项,节假日项来构建了,i.e.

y(t)=g(t)+s(t)+h(t)+\epsilon

下一步我们只需要拟合函数就可以了,在 Prophet 里面,作者使用了 pyStan 这个开源工具中的 L-BFGS 方法来进行函数的拟合。具体可以参考 forecast.py 里面的 stan_init 函数。

Prophet 中可以设置的参数

在 Prophet 中,用户一般可以设置以下四种参数:

  1. Capacity:在增量函数是逻辑回归函数的时候,需要设置的容量值。
  2. Change Points:可以通过 n_changepoints 和 changepoint_range 来进行等距的变点设置,也可以通过人工设置的方式来指定时间序列的变点。
  3. 季节性和节假日:可以根据实际的业务需求来指定相应的节假日。
  4. 光滑参数:\tau= changepoint_prior_scale 可以用来控制趋势的灵活度,\sigma= seasonality_prior_scale 用来控制季节项的灵活度,v= holidays prior scale 用来控制节假日的灵活度。

如果不想设置的话,使用 Prophet 默认的参数即可。

 

Prophet 的实际使用

Prophet 的简单使用

因为 Prophet 所需要的两列名称是 ‘ds’ 和 ‘y’,其中,’ds’ 表示时间戳,’y’ 表示时间序列的值,因此通常来说都需要修改 pd.dataframe 的列名字。如果原来的两列名字是 ‘timestamp’ 和 ‘value’ 的话,只需要这样写:

df = df.rename(columns={'timestamp':'ds', 'value':'y'})

如果 ‘timestamp’ 是使用 unixtime 来记录的,需要修改成 YYYY-MM-DD hh:mm:ss 的形式:

df['ds'] = pd.to_datetime(df['ds'],unit='s')

在一般情况下,时间序列需要进行归一化的操作,而 pd.dataframe 的归一化操作也十分简单:

df['y'] = (df['y'] - df['y'].mean()) / (df['y'].std())

然后就可以初始化模型,然后拟合模型,并且进行时间序列的预测了。

初始化模型:m = Prophet()
拟合模型:m.fit(df)
计算预测值:periods 表示需要预测的点数,freq 表示时间序列的频率。
future = m.make_future_dataframe(periods=30, freq='min')
future.tail()
forecast = m.predict(future)

而 freq 指的是 pd.dataframe 里面的一个指标,’min’ 表示按分钟来收集的时间序列。具体参见文档:http://pandas.pydata.org/pandas-docs/stable/timeseries.html#offset-aliases

prophetdataframefrequency

在进行了预测操作之后,通常都希望把时间序列的预测趋势画出来:

画出预测图:
m.plot(forecast)
画出时间序列的分量:
m.plot_components(forecast)

prophetexample5prophetexample6

如果要画出更详细的指标,例如中间线,上下界,那么可以这样写:

x1 = forecast['ds']
y1 = forecast['yhat']
y2 = forecast['yhat_lower']
y3 = forecast['yhat_upper']
plt.plot(x1,y1)
plt.plot(x1,y2)
plt.plot(x1,y3)
plt.show()

prophetexample7

其实 Prophet 预测的结果都放在了变量 forecast 里面,打印结果的话可以这样写:第一行是打印所有时间戳的预测结果,第二行是打印最后五个时间戳的预测结果。

print(forecast[['ds', 'yhat', 'yhat_lower', 'yhat_upper']])
print(forecast[['ds', 'yhat', 'yhat_lower', 'yhat_upper']].tail())

 

Prophet 的参数设置

Prophet 的默认参数可以在 forecaster.py 中看到:

def __init__(
    self,
    growth='linear',
    changepoints=None,
    n_changepoints=25, 
    changepoint_range=0.8,
    yearly_seasonality='auto',
    weekly_seasonality='auto',
    daily_seasonality='auto',
    holidays=None,
    seasonality_mode='additive',
    seasonality_prior_scale=10.0,
    holidays_prior_scale=10.0,
    changepoint_prior_scale=0.05,
    mcmc_samples=0,
    interval_width=0.80,
    uncertainty_samples=1000,
):

增长函数的设置

在 Prophet 里面,有两个增长函数,分别是分段线性函数(linear)和逻辑回归函数(logistic)。而 m = Prophet() 默认使用的是分段线性函数(linear),并且如果要是用逻辑回归函数的时候,需要设置 capacity 的值,i.e. df[‘cap’] = 100,否则会出错。

m = Prophet()
m = Prophet(growth='linear')
m = Prophet(growth='logistic')

变点的设置

在 Prophet 里面,变点默认的选择方法是前 80% 的点中等距选择 25 个点作为变点,也可以通过以下方法来自行设置变点,甚至可以人为设置某些点。

m = Prophet(n_changepoints=25)
m = Prophet(changepoint_range=0.8)
m = Prophet(changepoint_prior_scale=0.05)
m = Prophet(changepoints=['2014-01-01'])

而变点的作图可以使用:

from fbprophet.plot import add_changepoints_to_plot
fig = m.plot(forecast)
a = add_changepoints_to_plot(fig.gca(), m, forecast)

prophetexample8

周期性的设置

通常来说,可以在 Prophet 里面设置周期性,无论是按月还是周其实都是可以设置的,例如:

m = Prophet(weekly_seasonality=False)
m.add_seasonality(name='monthly', period=30.5, fourier_order=5)
m = Prophet(weekly_seasonality=True)
m.add_seasonality(name='weekly', period=7, fourier_order=3, prior_scale=0.1)

prophetexample9

节假日的设置

有的时候,由于双十一或者一些特殊节假日,我们可以设置某些天数是节假日,并且设置它的前后影响范围,也就是 lower_window 和 upper_window。

playoffs = pd.DataFrame({
  'holiday': 'playoff',
  'ds': pd.to_datetime(['2008-01-13', '2009-01-03', '2010-01-16',
                        '2010-01-24', '2010-02-07', '2011-01-08',
                        '2013-01-12', '2014-01-12', '2014-01-19',
                        '2014-02-02', '2015-01-11', '2016-01-17',
                        '2016-01-24', '2016-02-07']),
  'lower_window': 0,
  'upper_window': 1,
})
superbowls = pd.DataFrame({
  'holiday': 'superbowl',
  'ds': pd.to_datetime(['2010-02-07', '2014-02-02', '2016-02-07']),
  'lower_window': 0,
  'upper_window': 1,
})
holidays = pd.concat((playoffs, superbowls))

m = Prophet(holidays=holidays, holidays_prior_scale=10.0)

 

结束语

对于商业分析等领域的时间序列,Prophet 可以进行很好的拟合和预测,但是对于一些周期性或者趋势性不是很强的时间序列,用 Prophet 可能就不合适了。但是,Prophet 提供了一种时序预测的方法,在用户不是很懂时间序列的前提下都可以使用这个工具得到一个能接受的结果。具体是否用 Prophet 则需要根据具体的时间序列来确定。

参考文献:

  1. https://otexts.org/fpp2/components.html
  2. https://en.wikipedia.org/wiki/Decomposition_of_time_series
  3. A review of change point detection methods, CTruong, L. Oudre, N.Vayatis
  4. https://github.com/facebook/prophet
  5. https://facebook.github.io/prophet/

 

Advertisements

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

近期阅读了一篇论文《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系统架构
ADS 的系统架构
ROCKA系统架构
ROCKA 的系统架构

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

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

ADS 的细节

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

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

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

ADS特征
特征工程

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

ADS效果对比1
Average best F-scores of ADS, iForest, Donut, Opperentice, ROCKA + Opperentice
ADS效果对比2
The New KPI Streams

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

 

两篇关于时间序列的论文

这次整理的就是清华大学裴丹教授所著的两篇与时间序列相关的论文。一篇是关于时间序列聚类的,《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,还是层次聚类来说,都会消耗一定的运算时间。所以,如何在较短的时间内进行聚类或者分类的操作则是这个系统的关键之处。于是,这篇文章提出了一个将时间序列快速聚类的方法。

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

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

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

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

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

ROCKA系统架构
ROCKA系统架构

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

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

预处理模块(Preprocessing)

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

  1. 缺失值:缺失值指的是在该上报数据的时间戳上并没有相应的数据上报,数据处于缺失的状态。通常的办法就是把数据补齐,而数据补齐的方法有很多种,最简单的就是使用线性插值(Linear Interpolation)的方式来补齐。
  2. 标准化:对于一个时间序列而言,有可能它的均值是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} 的基线和剩余项。

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

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

基于密度的聚类算法(Clustering)

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

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

对于第一种方法而言,最重要的就是特征工程;对于第二种方法而言,最重要的是相似度函数的选择。在这篇文章中,作者选择了第二种方法来进行时间序列的聚类。对于两条时间序列 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 ,就说明这条新的时间序列曲线很可能不属于之前的任何一类。通过人工查看之后,可以考虑新增一类,并且更新之前所做的聚类模型。

聚类与时间序列异常检测

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

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

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

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

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

StepWiseExample.png
概念漂移的例子

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

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

StepWise系统架构
StepWise 的系统架构

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 系统详情请见下图。

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}],那么以下陈述是等价的。

  1. 存在一个线性关系 y = kx 使得二维点集 \{(x_{i},y_{i}), 1\leq i\leq n\} 能够被很好的拟合好,也就是说此刻的方差较小。
  2. [x_{1},\cdots,x_{n}][y_{1},\cdots,y_{n}] 的 Pearson 系数很高;
  3. [x_{1},\cdots,x_{n}][y_{1},\cdots,y_{n}] 标准化(z-score)之后的曲线几乎一致。
  4. 分别存在两个值 \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),最后使用一层过滤逻辑(线性拟合)来判断是否出现了概念漂移的情况。在实际使用过程中,无论是异常检测还是过滤逻辑,都需要根据具体的业务来做,很难找到一个固定的模型来解决所有的难题。

 

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

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

字节跳动

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

  1. 计算机视觉方向
  2. 自然语言处理方向
  3. 语音识别方向
  4. 机器学习方向

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》 的观点,可以大致分成以下三个方向:

  1. 质量保障;
  2. 效率提升;
  3. 成本管理。

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

AIOps场景

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

timeseries

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

成本

机器学习+其他领域

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

 

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

随着深度学习的发展,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}. fg 分别是编码层和解码层的激活函数,A,cB,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 等算法之外,本文尝试了一种新的异常检测算法,基于深度学习模型,利用自编码器的重构误差和局部误差,针对时间序列的异常检测的场景,初步达到了一个还不错的效果。这种方法可以用来提供部分异常样本,加大异常检测召回率的作用。但是这种方法也有一定的弊端:

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

参考文献

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

 

黑盒函数的探索

黑盒函数的定义

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

Blackbox3D-withGraphs

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

黑盒函数的研究对象

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

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

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

黑盒函数的根

对于多项式 p(x) = a_{n}x^{n}+\cdots + a_{0} 而言,多项式的根指的是使得 p(x)=0x 的解。特别的,对于二次多项式而言,也就是 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})<0f(x_{2})>0, 那么必定存在 x_{0} \in (x_{1},x_{2}) 使得 f(x_{0})=0。根据这个定理,我们可以提出二分法来计算函数的根。

如果要计算 f(x) = 0 的解,其一般步骤是:

  1. 先找到一个区间 [a,b], 使得 f(a)f(b)<0;
  2. 求这个区间的中点 m=(a+b)/2, 并求出 f(m) 的取值;
  3. 如果 f(m)=0, 那么 m 就是函数的根;如果 f(m)f(a)>0, 就选择 [m,b] 为新的区间,否则选择 [a,m] 为新的区间;
  4. 重复第 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 逼近定理可以知道:

  1. 闭区间上的连续函数可以用多项式级数一致逼近;
  2. 闭区间上的周期为 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)

SA1SA2SA3

模拟退火算法是为了模拟金属退火现象。其核心思想是构造了温度 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 足够小。

总结

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

 

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

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

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


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 也产生了浓厚的兴趣,撰写过两篇文章“强化学习与泛函分析”,“深度学习与强化学习”。


2017 年:再整旗鼓

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

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

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

正式接触到运维项目是 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 时间序列进行异常检测。这一类方法笔者总结过,那就是“时间序列简介(一)”,最终我们做到了“百万条曲线一人挑”,成功去掉了制定阈值的业务效果。


2018年:走向未来

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

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

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

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

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

张戎

2018年2月