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

在上一篇文章在新加坡的这五年—生活篇(二)中,笔者回顾了那些年在新加坡读书的时候,所遇到的一些有趣的人和事。本篇文章会回顾之前在新加坡的过年轶事。

最近几天正值新春佳节,虽然 2020 年的开局实在是不够顺利,无论是肆意传播的疫情,还是科比的突然离世,都给新的一年带来了不少沉重的色彩。但是新年总要有新的气象,每年都要立一些新的 Flag(虽然 2010 年的 Flag 可能至今都没有完成)。

li_flag

如果是在国内过春节,除了一些特殊的原因之外,那自然是需要回家乡与亲人团聚,坐在一起吃年夜饭,共同看春节联欢晚会。但是对于留学生而言,回国与家人共度春节就显得没有那么方便了。虽然新加坡的工作人士有很多的年假,但是他们的公共假日却少得可怜。很多外国人也很难想象中国人可以有春节黄金周,十一黄金周这种一整周的假期。在新加坡的官网上可以看到,新加坡的公共假日基本上都是一两天,除了中国农历新年放假两天之外,元旦新年,劳动节,新加坡国庆日,圣诞节等诸多假日都只有一天的假期。在这些公共假日里,从宿舍区去办公室是没有校车的,只能靠自己的 11 路走来走去。

SingaporePublicHoliday2020
2020 新加坡的公共假日

新加坡是一个多民族融合而成的国家,虽然农历新年对于中国人来说意义非凡,但是私底下有的老师对于留学生春节期间离开新加坡返回中国过节这件事情是有一定的意见的。毕竟这段时间学校已处于开学阶段,一旦有学生要离开助教(Teaching Assistant)或者助研(Research Assistant)岗位,该学生或者院系就需要找到另外的学生来临时代替他的工作,确实会对教学和科研造成一定的影响。不过这个只是说不建议留学生回国,其实留在新加坡的话留学生们也不需要来办公室,安心在家休假过节即可。对于很多留学生而言,即使不能够回国与家人欢度除夕新年,在新加坡体验异国他乡的春节其实也还算一个不错的选择。新加坡是以华人为主的社会,农历新年在新加坡绝对算得上是一个非常隆重的节日。每到农历新年之际,无论是 Chinatown,圣淘沙,还是每家每户,都是张灯结彩,充满了喜庆的氛围。

SingaporeSentosaCNY_1
2011 年圣淘沙农历新年
SingaporeSentosaCNY_2
2011 年圣淘沙农历新年

从 NUS 每年的学校日历来看,对于身处新加坡的留学生而言,农历新年的时候正好是刚刚开启新的学期的时候。即使回国也只能迅速返回学校,毕竟只有两天的假期。除了少数回国的学生之外,大部分留学生们都会在新加坡自行组织过农历新年的活动。对于学校而言,虽然是正月初一和正月初二放假,其实到了大年三十下午的时候,就已经不再组织教学活动了,因为就算上课也会有不少学生缺席。无论是学校的教职工,还是学生,都会在除夕当天下午准备过年的食物和喜庆的礼品。在正月初一和正月初二这两个特殊的日子里,很多商店,超市,饭店都是不开门的,即使是每天营业时间最长的昇菘超市(shengsiong),也会选择在大年三十的下午 3:00 提前下班,让员工们提前回去过除夕。因此,提前去超市准备过春节的食物和年夜饭就是所有留学生的必做的事情。

NUS_2019_2020_calendar
NUS 的 2019-2020 年度日历

要想从 NUS 的 UTown 或者 PGPR 两个宿舍区去昇菘超市可没有那么容易,除了等待 West Coast Plaza 的穿梭巴士和 NUS Bus,只能够选择步行的方式,从数学系 Block S17 出发,步行穿过工学院(Faculty of Engineering),再翻山穿过 Clementi Woods,最后走到昇菘超市。去时容易,返回困难。去程的时候双手空空荡荡,返程的时候可是大包小包全部装满了食物,饮料和酒水。通常来说,这往返一趟办公室和昇菘超市,需要两个小时左右的时间。不过,作为年夜饭的准备,还是非常值得的。

NUS_clementiwoods_map
Clementi Woods

从 2011 年算起到 2014 年,笔者前前后后在新加坡度过了四个春节,那几年的除夕夜分别是在 West Coast Plaza 的川江号子,UTown,UTown,ChinaTown 的国府珍锅吃的年夜饭。印象最深刻的就是在 2014 年大年三十的时候,吃完年夜饭,回到 PGP 之后打开电脑,写下了这一段话,立下了 2014 年的 Flag:

今年是农历的除夕,也就是大年三十,依旧和PHD们出去吃了顿火锅。不知道是不是最后一次在新加坡过年了。前前后后也过去四年了。第一次是West Coast Plaza的川江号子,第二次是utown宿舍,第三次也是在utown宿舍,第四次是在Chinatown的国府珍锅。不知道明年还有没有机会在新加坡过年了。最希望的就是尼玛交了论文就直接可以考虑毕业了,就不用在新加坡这个地方过年了。

Jan 31, 2014 00:18

于是,为了兑现 2014 年初的 Flag,笔者在 2014 年整整奋发图强了半年,终于在 2014 年 7 月份的时候把论文的主要步骤自行推导出来,在 2014 年下半年开学之后花了两三个月时间把所有步骤整理并且装订成册,在 2015 年 1 月份的时候就在系统上提交了自己的博士论文。

 

 

 

li_flag_2
Flag

每次提到毕业的事情都会觉得心情沮丧,所幸的是最终还是顺利地拿到博士学位。回想起博士生活的点点滴滴,除了科研的过程比较苦逼之外,其他的各种生活还是丰富多彩的。(未完待续)

 

拉格朗日四平方和定理

拉格朗日四平方和定理

每个正整数均可表示为四个整数的平方和。

Every positive integer is the sum of four squares.

例如:

  • 1=1^{2}+0^{2}+0^{2}+0^{2}
  • 2 = 1^{2}+1^{2}+0^{2}+0^{2}
  • 7 = 2^{2}+1^{2}+1^{2}+1^{2}

证明:可以直接验证如下恒等式

(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\cdot(y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2}) = z_{1}^{2}+z_{2}^{2}+z_{3}^{2}+z_{4}^{2},其中

\begin{cases} z_{1}=x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}+x_{4}y_{4} \\ z_{2}=x_{1}y_{2}-x_{2}y_{1}-x_{3}y_{4}+x_{4}y_{3} \\ z_{3}=x_{1}y_{3}-x_{3}y_{1}+x_{2}y_{4}-x_{4}y_{2} \\ z_{4}=x_{1}y_{4}-x_{4}y_{1}-x_{2}y_{3}+x_{3}y_{2}\end{cases}

由于 1 与 2 都明显满足这个定理,那么只需要考虑大于 2 的正整数。而这些正整数都可以分解成素数的乘积,因此,只需要证明该定理对所有的素数成立,则使用以上恒等式就可以得到最终的结论。假设 p 是一个奇素数。

由于 \{a^{2}:a\in\{0,1,\cdots,(p-1)/2\}\} 里面有 (p+1)/2 个不同的同余类,\{-b^{2}-1: b\in \{0,1,\cdots,(p-1)/2\}\} 里面也有 (p+1)/2 个不同的同余类,但是素数 p 的同余类只有 p 个,因此存在正整数 a,b\in \{0,1,\cdots, (p-1)/2\} 满足 a^{2}\equiv -b^{2}-1 (\mod p)。也就是说 a^{2}+b^{2}+1^{2}+0^{2}\equiv 0(\mod p)。令 n\in\mathbb{Z} 满足 np=a^{2}+b^{2}+1,则有 p\leq np\leq 2(p-1)^{2}/4+1<p^{2}。于是,1\leq n<p

因此存在一个 1\leq n<p 使得 np = a^{2}+b^{2}+1^{2}+0^{2} 是四个整数的平方和。于是必定存在一个最小的正整数 m 使得 1\leq m\leq n<p 使得 mp 为四个整数的平方和,不妨设为 mp=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}

Claim. m=1

proof of the claim. 反证法,假设 1<m\leq n<p 成立。令 y_{i}=x_{i}(\mod m) 对于 i\in\{1,2,3,4\} 成立,并且 -m/2<y_{i}\leq m/2。因此,y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2}\equiv(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\equiv mp \equiv 0(\mod m)。令 mr = y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2}。因此,mr\leq 4(m/2)^{2}=m^{2}

如果 r =m,通过以上不等式得知 r=m 等价于 y_{i}=m/2 对于 i\in\{1,2,3,4\} 都成立。此时,mp = x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}\equiv 4(m/2)^{2} \equiv 0 (\mod m^{2})。因此,pm 的倍数,这与 p 是素数,m>1 矛盾。所以,r<m 成立。i.e. 1\leq r<m\leq n<p 成立。

进一步地,(mp)\cdot(mr) = (x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\cdot(y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2}) = z_{1}^{2}+z_{2}^{2}+z_{3}^{2}+z_{4}^{2},这里的 z_{i} 正如恒定式里面所定义的。由于 y_{i}\equiv x_{i}(\mod m),并且 \sum_{i=1}^{4}x_{i}^{2}\equiv 0(\mod m)。因此,z_{i}\equiv 0(\mod m) 对于 i\in\{1,2,3,4\} 都成立。所以,z_{i}=w_{i}mw_{i}\in\mathbb{Z} 对于 i\in\{1,2,3,4\} 都成立。通过 (mp)\cdot(mr) = \sum_{i=1}^{4}z_{i}^{2} 可以得到 pr=\sum_{i=1}^{4}w_{i}^{2} 成立。但是,1\leq r<m 这与 m 的最小性假设矛盾了。

因此,m=1,Claim 证明完毕。

于是,对于所有的奇素数,都可以表示为四个整数的平方之和。根据之前的分析,可以得到对于所有的正整数,都可以表示为四个整数的平方之和。Lagrange 定理证明完毕。

参考文献

  1. GTM 164, Additive Number Theory, Melvyn B.Nathanson, 1996.

传染病的数学模型

近期,国内的疫情闹得沸沸扬扬,很多省市自治区都出现了流感的患者。回想起之前在学校的时候曾经研究过微分方程和动力系统,于是整理一下相关的数学模型,分享给各位读者。笔者并不是研究这个领域的专家,并且这篇文章只是从微分方程角度出发,分析方程的性质,不一定适用于真实环境,而且真实环境比这个也复杂得多。

关于传染病的数学模型,在许多年前数学界早已做过研究,根据传染病的传播速度不同,空间范围各异,传播途径多样,动力学机理等各种因素,对传染病模型按照传染病的类型划分为 SI,SIR,SIRS,SEIR 模型。如果是按照连续时间来划分,那么这些模型基本上可以划分为常微分方程(Ordinary Differential Equation),偏微分方程(Partial Differential Equation)等多种方程模型;如果是基于离散的时间来划分,那么就是所谓的差分方程(Difference Equation)。

在本文中,将会主要介绍常微分方程中的一些传染病数学模型。在介绍方程之前,首先要介绍一些常用的符号:在时间戳 t 上,可以定义以下几种人群:

  • 易感者(susceptible):用符号 S(t) 来表示;
  • 感染者(infective):用符号 I(t) 来表示;
  • 康复者(Recoverd):用符号 R(t) 来表示;

其次,在时间戳 t 上,总人口是 N(t)=S(t)+I(t)+R(t)。如果暂时不考虑人口增加和死亡的情况,那么 N(t)\equiv N 是一个恒定的常数值。

除此之外,

  • r 表示在单位时间内感染者接触到的易感者人数;
  • 传染率:\beta 表示感染者接触到易感者之后,易感者得病的概率;
  • 康复率:\gamma 表示感染者康复的概率,有可能变成易感者(可再感染),也有可能变成康复者(不再感染)。

在进行下面的分析之前,先讲一个常微分方程的解。

Claim. 假设 x=x(t) 是关于 t 的一个方程,且满足 \frac{dx}{dt} + a_{1}x + a_{2}x^{2}=0x(0)=x_{0},那么它的解是:x(t) = \frac{e^{-a_{1}t}}{\frac{1}{x_{0}}-\frac{a_{2}}{a_{1}}(e^{-a_{1}t}-1)}.

Proof. 证明如下:

通过 \frac{dx}{dt}+a_{1}x+a_{2}x^{2}=0 可以得到 -\frac{d}{dt}\bigg(\frac{1}{x}\bigg) + a_{1}\bigg(\frac{1}{x}\bigg)+a_{2}=0;令 y = 1/x,得到 \frac{dy}{dt}-a_{1}y=a_{2}。所以,\frac{d}{dt}(e^{-a_{1}t}y) = a_{2}e^{-a_{1}t},两边积分可以得到 e^{-a_{1}t}y-y_{0}=\bigg(-\frac{a_{2}}{a_{1}}\bigg)(e^{-a_{1}t}-1),其中 y_{0}=1/x_{0}。求解之后得到:x(t) = e^{-a_{1}t}/\bigg(\frac{1}{x_{0}}-\frac{a_{2}}{a_{1}}(e^{-a_{1}t}-1)\bigg)

SI 模型(Susceptible-Infective Model)

在 SI 模型里面,只考虑了易感者和感染者,并且感染者不能够恢复,此类病症有 HIV 等;

SI_model_1
SI Model

其微分方程就是:

\begin{cases}\frac{dS}{dt} = -\frac{r\beta I}{N} S \\ \frac{dI}{dt}=\frac{r\beta I}{N}S \end{cases}

初始条件就是 S(0)=S_{0}I(0) = I_{0},并且 S(t)+I(t)=N 对于所有的 t\geq 0 都成立。

于是,把 S = N - I 代入第二个微分方程可以得到:\frac{dI}{dt} - r\beta I + \frac{r\beta}{N}I^{2}=0。因此根据前面所提到的常微分方程的解可以得到:

I(t) = \frac{NI_{0}}{I_{0}+(N-I_{0})e^{-r\beta t}}.

这个就是所谓的逻辑回归函数,而在机器学习领域,最简单的逻辑回归函数就是 \sigma(x) = 1/(1+e^{-x}) 这个定义。而 I(t) 只是做了一些坐标轴的平移和压缩而已。由于 \lim_{t\rightarrow +\infty}e^{-t}=0,所以,\lim_{t\rightarrow +\infty}I(t) = N,从而 \lim_{t\rightarrow +\infty}S(t) = 0

通过数值模拟可以进一步知道:

SI_model_graph_1
SI model 的数值模拟(一)

简单来看,在 SI 模型的假设下,全部人群到最后都会被感染。

SIS 模型(Susceptible-Infectious-Susceptible Model)

除了 HIV 这种比较严重的病之外,还有很多小病是可以恢复并且反复感染的,例如日常的感冒,发烧等。在这种情况下,感染者就有一定的几率重新转化成易感者。如下图所示:

SIS_model_1
SIS model

其微分方程就是:

\begin{cases} \frac{dS}{dt} = -r \beta S\frac{I}{N} + \gamma I \\ \frac{dI}{dt}=r\beta S \frac{I}{N} - \gamma I \end{cases},其初始条件就是 S(0)=S_{0}I(0)=I_{0}.

使用同样的方法,把 S=N-I 代入第二个微分方程可以得到:\frac{dI}{dt} - (r\beta - \gamma)I + \frac{r\beta}{N}I^{2}=0. 通过之前的 Claim 可以得到解为:

I(t) = \frac{N(r\beta-\gamma)}{r\beta}/\bigg(\bigg(\frac{N(r\beta-\gamma)}{I_{0}r\beta}-1\bigg)e^{-(r\beta-\gamma)t}+1\bigg).

从而可以得到 \lim_{t\rightarrow +\infty} I(t) = N(r\beta - \gamma)/(r\beta)\lim_{t\rightarrow +\infty} S(t) = (N\gamma)/(r\beta). 这个方程同样也是逻辑回归方程,只是它的渐近线与之前的 SI 模型有所不同。

SIS_model_graph_1
SIS model 的数值模拟(二)

SIR 模型(Susceptible-Infectious-Recovered Model)

有的时候,感染者在康复了之后,就有了抗体,于是后续就不再会获得此类病症,这种时候,考虑 SIS 模型就不合适了,需要考虑 SIR 模型。此类病症有麻疹,腮腺炎,风疹等。

SIR_model_1
SIR model

其微分方程是:\begin{cases} \frac{dS}{dt}=-r\beta S \frac{I}{N} \\ \frac{dI}{dt}=r\beta S\frac{I}{N} - \gamma I \\ \frac{dR}{dt}=\gamma I\end{cases}。其初始条件是 S(0)=S_{0}, I(0)=I_{0}, R(0)=R_{0},并且 S(t), I(t), R(t)\geq 0S(t) +I(t)+R(t)=N 对于所有的 t\geq 0 都成立。

对于这类方程,就不能够得到其解析解了,只能够从它的动力系统开始进行分析,得到解的信息。根据第一个微分方程可以得到:\frac{dS}{dt} = -r\beta S\frac{I}{N}<0,于是 S(t) 是一个严格递减函数。同时,0\leq S(t)\leq N 对于所有的 t\geq 0 都成立,于是存在 S_{\infty}\in[0,\infty] 使得 \lim_{t\rightarrow \infty}S(t)=S_{\infty}.

通过第一个微分方程和第二个微分方程可以得到:\frac{d(S+I)}{dt} = -\gamma I,因此对它两边积分得到 \int_{0}^{T} \frac{d(S+I)}{dt} = -\gamma \int_{0}^{T}I(t)dt. 左侧等于 S(T) + I(T) - S(0) - I(0),上界是 4N,因此令 T\rightarrow \infty 可以得到 \int_{0}^{\infty}I(t) dt\leq 4N/\gamma. 而 I(t)\geq 0 且是连续可微函数,因此 \lim_{t\rightarrow \infty}I(t) = 0。这意味着所有的感染人群都将康复。

由于 S(t) 是严格单调递减函数,因此从第二个微分方程可以得到:当 S(t) = N\gamma/(r\beta) 时,感染人数 I(t) 达到最大值。

SIR_model_graph_1
SIR model 的数值模拟(一)
SIR_model_graph_2
SIR model 的数值模拟(二)

其余模型

在以上的 SI,SIS,SIR 模型中,还可以把死亡因素考虑进去。除此之外,还有 SIRS 模型,SEIR 模型等,在这里就不再做赘述。有兴趣的读者可以参阅相关的参考书籍。

参考文献

  1. Introduction to SEIR Models, Nakul Chitnis, Workshop on Mathematical Models of Climate Variability, Environmental Change and Infectious Diseases, Trieste, Italy, 2017

 

符号计算中的深度学习方法

符号计算

符号计算一直是计算数学的重要领域之一。在开源领域,Python 的 SymPy 就可以支持符号计算。在商业化领域,Maple,Matlab,Mathematica 都能够进行符号计算。它们不仅能够做简单的实数和复数加减乘除,还能够支持数学分析,线性代数,甚至各种各样的大学数学课程。

随着人工智能的进一步发展,深度学习不仅在图像识别,自然语言处理方向上发挥着自身的价值,还在各种各样的领域展示着自己的实用性。在 2019 年底,facebook 两位研究员在 arxiv 上挂出了一篇文章《Deep Learning for Symbolic Mathematics》,在符号计算方向上引入了深度学习的工具。

要想了解符号运算,就要先知道在计算机中,是怎么对数学公式进行表示的。较为常见的表达式形如:

  • 2 + 3 * (5 + 2)
  • 3x^{2}+\cos(2x)+1
  • \frac{\partial^{2}\psi}{\partial x^{2}} - \frac{1}{v^{2}}\frac{\partial^{2}\psi}{\partial t^{2}}

在这里,数学表达式通常都会被表示成树的结构,其中树的内部节点是由算子(operator),函数(function)组成的,叶子节点由数字,变量,函数等组成。例如:

dlsm_figure1.png
图 1

图 1 的三幅图分别对应着上面的三个数学表达式。

在 Python 的 SymPy 工具中,同样可以对数学公式进行展示。其表示方法就是用 sympy.srepr

>>> import sympy
>>> x, y = sympy.symbols("x y")
>>> expr = sympy.sin(x+y) + x**2 + 1/y - 10
>>> sympy.srepr(expr)
"Add(Pow(Symbol('x'), Integer(2)), sin(Add(Symbol('x'), Symbol('y'))), Integer(-10), Pow(Symbol('y'), Integer(-1)))"
>>> expr = sympy.sin(x*y)/2 - x**2 + 1/y
>>> sympy.srepr(expr)
"Add(Mul(Integer(-1), Pow(Symbol('x'), Integer(2))), Mul(Rational(1, 2), sin(Mul(Symbol('x'), Symbol('y')))), Pow(Symbol('y'), Integer(-1)))"
dlsm_figure2.png
图 2

SymPy 的 srepr 函数的输出用树状结构来表示就是形如图 2 这种格式。叶子节点要么是 x,y 这种变量,要么是 -1 和 2 这种整数。对于一元函数而言,例如 sin 函数,就是对应唯一的一个叶子。对于二元函数而言,例如 pow,mul,add,则是对应两个叶子节点。

论文方案

在 Deep Learning for Symbolic Mathematics 这篇论文中,作者们的大致思路是分成以下几步的:

  1. 生成数据;
  2. 训练模型;
  3. 预测结果;

第一步生成数据是为了让深度学习模型是大量的已知样本来做训练;第二步训练模型是用第一步的数据把端到端的深度学习模型进行训练;第三步预测结果是给一个函数或者一个微分方程,使用已经训练好的模型来预测结果,对预测出来的多个结果进行排序,选择最有可能的那个结果作为符号计算的值。

众所周知,深度学习的训练是依赖大量的样本数据的,那么要想用深度学习来解决符号计算的问题,就要解决样本少的问题。在这篇论文中,作者们把精力投入了三个领域,分别是:

  1. 函数的积分;
  2. 一阶常微分方程;
  3. 二阶常微分方程。

在生成数据之前,作者们对数据的范围进行了必要的限制:

  1. 数学表达式最多拥有 15 个内部节点;
  2. L = 11 表示叶子节点的值只有 11 个,分别是变量 x\{-5,-4,-3,-2,-1,1,2,3,4,5\}
  3. p_{1} = 15 表示一元计算只有 15 个,分别是 \exp, \log, \sqrt, \sin, \cos, \tan, \arcsin, \arccos, \arctan, sinh, cosh, tanh, arcsinh, arccosh, arctanh
  4. p_{2} = 4 表示二元计算只有四个,分别是 +, -, *, /;

意思就是在这个有限的范围内去生成深度学习所需要的数据集。

积分数据的生成

在微积分里面,积分指的是求导的逆运算,那么形如 (f',f) 的表达式就可以作为深度学习的积分训练数据。生成积分的话其实有多种方法:

第一种方法:前向生成(Forward Generation,简写为 FWD)。主要思路就是在以上的数据范围内随机生成各种各样的方程 f,然后使用 SymPy 或者 Mathematica 等工具来计算函数 f 的积分 F,那么 (f,F) 就可以作为一个训练集。当然,有的时候函数 f 的积分是无法计算出来的,那么这种计算表达式就需要进行放弃,就不能放入训练集。

第二种方法:反向生成(Backward Generation,简写为 BWD)。由于积分是求导的逆运算,可以在以上的数据范围内随机生成各种各样的方程 f,然后计算它们的导数 f',于是 (f',f) 就可以放入积分数据的训练集。

第三种方法:分部积分(Backward generation with integration by parts,简写为 IBP)。根据分部积分的公式,如果 F'=f, G'=g,那么 \int F(x)g(x)dx=F(x)G(x) - \int f(x)G(x)dx。对于两个随机生成的函数 F, G,可以计算出它们的导数 f, g。如果 fG 在训练集合里面,那么就把 Fg 的积分计算出来放入训练集合;反之,如果 Fg 在训练集合里面,那么就把 fG 的积分计算出来放入训练集合。如果 fGFg 都没有在训练集合,并且都无法积分出来,那么就放弃该条数据。

三种方法的比较可以参见表 1,从表 1 可以看出通过分部积分(Integration by parts)所获得的样本表达式相对于前向生成和反向生成都比较长。

dlsm_table1.png
表 1

一阶常微分方程的生成

一阶常微分方程只有该函数的一阶导数,因此在构造函数的时候,作者们用了一个技巧。在随机生成表达式的时候,叶子节点的元素只从 \{x, -5,-4,-3,-2,-1,1,2,3,4,5\} 选择一个,于是随机把其中的一个整数换成变量 c。例如:在 x\log(2/x) 中就把 2 换成 c,于是得到了一个二元函数 f(x,c) = x\log(c/x)。那么就执行以下步骤:

  1. 生成二元函数 f(x,c) = x\log(c/x)
  2. 求解 c,得到 c = xe^{f(x)/x}
  3. x 进行求导得到 0 = e^{f(x)/x}(1+f'(x)-f(x)/x) = 0
  4. 简化后得到 x+xf'(x) - f(x) =0,也就是 x+xy'-y=0

此时,一阶常微分方程的训练数据就是 (x+xy'-y=0, x\log(c/x))

二阶常微分方程不仅可能由该函数的一阶导数,还必须有二阶导数,那么此时就要求导两次:

  1. 生成三元函数 f(x,c_{1},c_{2}) = c_{1}e^{x}+c_{2}e^{-x}
  2. 求解 c_{2} 得到 c_{2} = f(x,c_{1},c_{2}) e^{x}- c_{1}e^{2x}
  3. x 进行求导得到 0 = e^{x}(\partial f(x,c_{1},c_{2})/\partial x + f(x,c_{1},c_{2})) - 2c_{1}e^{2x} = 0
  4. 求解 c_{1} 得到 c_{1} = e^{-x}(\partial f(x,c_{1},c_{2})/\partial x+f(x))/2
  5. x 进行求导得到 0 = e^{-x}(\partial^{2} f(x,c_{1},c_{2})/\partial x^{2} - f(x,c_{1},c_{2}))=0
  6. 简化后得到 \partial^{2} f(x,c_{1},c_{2})/\partial x^{2} - f(x,c_{1},c_{2})=0,也就是 y''-y=0

那么此时的二阶微分方程的训练数据就是 (y''-y=0, c_{1}e^{x}+c_{2}e^{-x})

需要注意的事情就是,在生成数据的时候,一旦无法求出 c_{1}, c_{2} 的表达式,该数据就需要放弃,重新生成新的数据。

数据处理

  1. 数学表达式的简化(expression simplification):例如 x+1+1 可以简化成 x+2\sin^{2}(x)+\cos^{2}(x) 可以简化成 1。
  2. 参数的简化(coefficient simplification):例如 \log(x^{2}) + c\log(x) 可以简化成 c\log(x)
  3. 无效表达式的过滤(invalid expression filter):例如 \sqrt{2}, \log(0) 等。

树状结构的表达式,是使用前缀表达式来写成一个句子的。例如 2+3 就写成 + 2 3,2 + x 就写成 + 2 x。

模型训练

在这里,作者们用了 Transformer 模型,8 attention heads,6 layers,512 个维度,并且发现用更复杂的模型并没有提升其效果。在预测的时候,使用不同的 Beam Size,其准确率是不一样的,在 Beam Size = 50 的时候,效果比较好。参见表 2。

dlsm_table2.png
表 2

在与其他数学软件的比较中, 作者限制了 Mathematica 的运行时间为 30s。

dlsm_table3.png

并且举出了几个现有模型能够计算出来,Mathematica 无法计算的例子。

dlsm_table4.png

在求解的等价性方面,可以根据 Score 逆序排列,然后这个例子的 Top10 都是等价的。

dlsm_table5.png

在使用 SymPy 的过程中,可以获得各种各样的积分表达式如下:

dlsm_table7.png

结论

符号计算在 1960 年代末就已经在研究了,有诸多的符号计算软件,例如 Matlab,Mathematica,Maple,PARI,SAGE 等。在这篇论文中,作者们使用标准的 seq2seq 模型来对生成的数据进行训练,然后获得积分,一阶常微分方程,二阶常微分方程的解。在传统符号计算的基础上,开拓了一种新的思路。

用 Python 来研究数学 — SymPy 符号工具包介绍

SymPy 的简单介绍

SymPy 是一个符号计算的 Python 库,完全由 Python 写成,为许多数值分析,符号计算提供了重要的工具。SymPy 的第一个版本于 2007 年开源,并且经历了十几个版本的迭代,在 2019 年已经基于修正的 BSD 许可证开源了 1.4 版本。SymPy 的开源地址和官方网站分别是:

  1. GitHub 链接:https://github.com/sympy/sympy
  2. SymPy 官方网站:https://www.sympy.org/en/index.html
sympy_logo
SymPy 的 logo

SymPy 的 1.4 版本文档中,可以看出,SymPy 可以支持很多初等数学,高等数学,甚至研究生数学的符号计算。在初等数学和高等数学中,SymPy 可以支持的内容包括但不限于:

  1. 基础计算(Basic Operations);
  2. 公式简化(Simplification);
  3. 微积分(Calculus);
  4. 解方程(Solver);
  5. 矩阵(Matrices);
  6. 几何(geometry);
  7. 级数(Series);

在更多的数学领域中,SymPy 可以支持的内容包括但不限于:

  1. 范畴论(Category Theory);
  2. 微分几何(Differential Geometry);
  3. 常微分方程(ODE);
  4. 偏微分方程(PDE);
  5. 傅立叶变换(Fourier Transform);
  6. 集合论(Set Theory);
  7. 逻辑计算(Logic Theory)。
sympy_tutorial
SymPy 的教学目录

SymPy 的工具库介绍

SymPy 的基础计算

在数学中,基础的计算包括实数和复数的加减乘除,那么就需要在程序中描述出实数与复数。著名的欧拉公式

e^{i\pi}+1 = 0

正好用到了数学中最常见的五个实数。在 SymPy 里面,e, i, \pi, \infty 是用以下符号来表示的:其中 sympy.exp() 表示以 e 为底的函数。

sympy.exp(1), sympy.I, sympy.pi, sympy.oo

而想要计算欧拉公式的话,只需要输入下面的公式即可:

>>> sympy.exp(sympy.I * sympy.pi) + 1
0

如果需要看 e, \pi 的小数值,可以使用 evalf() 函数,其中 evalf() 函数里面的值表示有效数字的位数。例如下面就是精确到 10 位有效数字。当然,也可以不输入。

>>> sympy.E.evalf(10)
2.718281828
>>> sympy.E.evalf()
2.71828182845905
>>> sympy.pi.evalf(10)
3.141592654
>>> sympy.pi.evalf()
3.14159265358979

除此之外,如果需要查看某个实数的有效数字,也是类似操作的:

>>> expr = sympy.sqrt(8)
>>> expr.evalf()
2.82842712474619

而对于实数的加减乘除,则可以如下操作:

>>> x, y= sympy.symbols("x y")
>>> x + y
x + y
>>> x - y
x - y
>>> x * y
x*y
>>> x / y
x/y

而对于复数的加减乘除,则是类似的操作,令两个复数分别是 z_{1} = x_{1} + i y_{1}z_{2} = x_{2} + i y_{2}

>>> x1, y1, x2, y2 = sympy.symbols("x1 y1 x2 y2")
>>> z1 = x1 + y1 * sympy.I
x1 + I*y1
>>>  z2 = x2 + y2 * sympy.I
x2 + I*y2
>>> z1 + z2
x1 + x2 + I*y1 + I*y2
>>> z1 - z2
x1 - x2 + I*y1 - I*y2
>>> z1 * z2
(x1 + I*y1)*(x2 + I*y2)
>>> z1 / z2
(x1 + I*y1)/(x2 + I*y2)

对于多项式而言,有的时候我们希望将其展开,有的时候则需要将其合并,最终将其简化成最简单的形式。

>>> sympy.expand((x+1)**2)
x**2 + 2*x + 1
>>> sympy.expand((x+1)**5)
x**5 + 5*x**4 + 10*x**3 + 10*x**2 + 5*x + 1
>>> sympy.factor(x**3+1)
(x + 1)*(x**2 - x + 1)
>>> sympy.factor(x**2+3*x+2)
(x + 1)*(x + 2)
>>> sympy.simplify(x**2 + x + 1 - x)
x**2 + 1
>>> sympy.simplify(sympy.sin(x)**2 + sympy.cos(x)**2)
1

在多变量的场景下,SymPy 也可以对其中的某个变量合并同类项,同时还可以计算某个变量的某个次数所对应的系数是多少,例如:

>>> expr = x*y + x - 3 + 2*x**2 - x**2 + x**3 + y**2 + x**2*y**2
>>> sympy.collect(expr,x)
x**3 + x**2*(y**2 + 1) + x*(y + 1) + y**2 - 3
>>> sympy.collect(expr,y)
x**3 + x**2 + x*y + x + y**2*(x**2 + 1) - 3
>>> expr.coeff(x, 2)
y**2 + 1
>>> expr.coeff(y, 1)
x

有理函数形如 f(x) = p(x)/q(x),其中 p(x)q(x) 都是多项式。一般情况下,我们希望对有理函数进行简化,合并或者分解的数学计算。

在需要合并的情形下,如果想把有理函数处理成标准格式 p(x)/q(x) 并且去除公因子,那么可以使用 cancel 函数。另一个类似的就是 together 函数,但是不同之处在于 cancel 会消除公因子,together 不会消除公因子。例如:

expr = \frac{x^{2}+3x+2}{x^{2}+x}

>>> expr = (x**2 + 3*x + 2)/(x**2 + x)
>>> sympy.cancel(expr)
(x + 2)/x
>>> sympy.together(expr)
(x**2 + 3*x + 2)/(x*(x + 1))

除了合并和消除公因子之外,有的时候还希望对分子和分母进行因式分解,例如:

expr = (x**2 + 3*x + 2)/(x**2 + x)
>>> sympy.factor(expr)
(x + 2)/x
>>> expr = (x**3 + 3*x**2 + 2*x)/(x**5+x)
>>> sympy.factor(expr)
(x + 1)*(x + 2)/(x**4 + 1)
>>> expr = x**2 + (2*x+1)/(x**3+1)
>>> sympy.factor(expr)
(x**5 + x**2 + 2*x + 1)/((x + 1)*(x**2 - x + 1))

合并的反面就是部分分式展开(Partial Fraction Decomposition),它是把有理函数分解成多个次数较低的有理函数和的形式。这里需要用 apart 函数:

>>> expr = (x**4 + 3*x**2 + 2*x)/(x**2+x)
>>> sympy.apart(expr)
x**2 - x + 4 - 2/(x + 1)
>>> expr = (x**5 + 1)/(x**3+1)
>>> sympy.apart(expr)
x**2 - (x - 1)/(x**2 - x + 1)

在 SymPy 里面,同样支持各种各样的三角函数,例如:三角函数的简化函数 trigsimp,三角函数的展开 expand_trig,

>>> expr = sympy.sin(x)**2 + sympy.cos(x)**2
>>> sympy.trigsimp(expr)
1
>>> sympy.expand_trig(sympy.sin(x+y))
sin(x)*cos(y) + sin(y)*cos(x)
>>> sympy.expand_trig(sympy.cos(x+y))
-sin(x)*sin(y) + cos(x)*cos(y)
>>> sympy.trigsimp(sympy.sin(x)*sympy.cos(y) + sympy.sin(y)*sympy.cos(x))
sin(x + y)
>>> sympy.trigsimp(-sympy.sin(x)*sympy.sin(y) + sympy.cos(x)*sympy.cos(y))
cos(x + y)

同样的,在乘幂上面,同样有简化函数 powsimp,效果与之前提到的 simplify 一样。除此之外,还可以根据底数来做合并,即分别使用 expand_power_exp 函数与 expand_power_base 函数。

>>> sympy.powsimp(x**z*y**z*x**z)
x**(2*z)*y**z
>>> sympy.simplify(x**z*y**z*x**z)
x**(2*z)*y**z
>>> sympy.expand_power_exp(x**(y + z))
x**y*x**z
>>> sympy.expand_power_base(x**(y + z))
x**(y + z)

作为指数的反函数对数,sympy 也是有着类似的展开合并函数,expand_log,logcombine 承担了这样的角色。

\ln(xy) = \ln(x) + \ln(y)

\ln(x/y) = \ln(x) - \ln(y)

>>> sympy.expand_log(sympy.log(x*y), force=True)
log(x) + log(y)
>>> sympy.expand_log(sympy.log(x/y), force=True)
log(x) - log(y)

 

SymPy 的微积分工具

下面,我们会从一个最基本的函数 f(x) = 1/x 出发,来介绍 SymPy 的各种函数使用方法。如果想进行变量替换,例如把 x 变成 y,那么可以使用 substitution 方法。除此之外,有的时候也希望能够得到函数 f 在某个点的取值,例如 f(1) = 1/1 = 1,那么可以把参数换成 1 即可得到函数的取值。例如,

>>> import sympy
>>> x = sympy.Symbol("x")
>>> f = 1 / x
1/x
>>> y = sympy.Symbol("y")
>>> f = f.subs(x,y)
1/y
>>> f = f.subs(y,1)
1

在微积分里面,最常见的概念就是极限,SymPy 里面的极限函数就是 limit。使用方法如下:

>>> f = 1/x
>>> sympy.limit(f,x,0)
oo
>>> sympy.limit(f,x,2)
1/2
>>> sympy.limit(f,x,sympy.oo)
0
>>> g = x * sympy.log(x)
>>> sympy.limit(g,x,0)
0

对于函数 f(x) = 1/x 而言,它的导数计算函数是 diff,n 阶导数也可以用这个函数算。

>>> f = 1/x
>>> sympy.diff(f,x)
-1/x**2
>>> sympy.diff(f,x,2)
2/x**3
>>> sympy.diff(f,x,3)
-6/x**4
>>> sympy.diff(f,x,4)
24/x**5

提到 n 阶导数,就必须要提一下 Taylor Series 了。对于常见函数的 Taylor Series,SymPy 也是有非常简便的方法,那就是 series 函数。其参数包括 expr, x, x0, n, dir,分别对应着表达式,函数的自变量,Taylor Series 的中心点,n 表示阶数,dir 表示方向,包括”+-“,”-“,”+”,分别表示 x\rightarrow x0, x\rightarrow x0^{-}, x\rightarrow x0^{+}

sympy.series.series.series(exprx=Nonex0=0n=6dir='+') >>> g = sympy.cos(x) >>> sympy.series(g, x) 1 - x**2/2 + x**4/24 + O(x**6) >>> sympy.series(g, x, x0=1, n=10) cos(1) - (x - 1)*sin(1) - (x - 1)**2*cos(1)/2 + (x - 1)**3*sin(1)/6 + (x - 1)**4*cos(1)/24 - (x - 1)**5*sin(1)/120 - (x - 1)**6*cos(1)/720 + (x - 1)**7*sin(1)/5040 + (x - 1)**8*cos(1)/40320 - (x - 1)**9*sin(1)/362880 + O((x - 1)**10, (x, 1))

积分的计算函数是 integrate,包括定积分与不定积分:

\int\frac{1}{x}dx = \ln(x)+C

\int_{1}^{2}\frac{1}{x}dx = \ln(2)

>>> f = 1/x
>>> sympy.integrate(f,x)
log(x)
>>> sympy.integrate(f, (x,1,2))
log(2)

对于广义积分而言,就需要用到 \infty 这个概念了,但是在 SymPy 里面的写法还是一样的。

\int_{-\infty}^{0}e^{-x^{2}}dx=\frac{\sqrt{\pi}}{2}

\int_{0}^{+\infty}e^{-x}dx = 1

\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}e^{-x^{2}-y^{2}}dxdy = \pi

>>> g = sympy.exp(-x**2)
>>> sympy.integrate(g, (x,-sympy.oo,0))
sqrt(pi)/2
>>> g = sympy.exp(-x)
>>> sympy.integrate(g, (x, 0, sympy.oo))
1
>>> h = sympy.exp(-x**2 - y**2)
>>> sympy.integrate(h, (x,-sympy.oo, sympy.oo), (y, -sympy.oo, sympy.oo))
pi

 

SymPy 的方程工具

在初等数学中,通常都存在一元一次方程,一元二次方程等,并且在不同的域上有着不同的解。SymPy 里面的相应函数就是 solveset,根据定义域的不同,可以获得完全不同的解。

\{x\in\mathbb{R}: x^{3}-1=0\}

\{x\in\mathbb{C}:x^{3}-1=0\}

\{x\in\mathbb{R}:e^{x}-x=0\}

\{x\in\mathbb{R}:e^{x}-1=0\}

\{x\in\mathbb{C}:e^{x}-1=0\}

>>> sympy.solveset(sympy.Eq(x**3,1), x, domain=sympy.S.Reals)
{1}
>>> sympy.solveset(sympy.Eq(x**3,1), x, domain=sympy.S.Complexes)
{1, -1/2 - sqrt(3)*I/2, -1/2 + sqrt(3)*I/2}
>>> sympy.solveset(sympy.Eq(x**3 - 1,0), x, domain=sympy.S.Reals)
{1}
>>> sympy.solveset(sympy.Eq(x**3 - 1,0), x, domain=sympy.S.Complexes)
{1, -1/2 - sqrt(3)*I/2, -1/2 + sqrt(3)*I/2}
>>> sympy.solveset(sympy.exp(x),x)
EmptySet()
>>> sympy.solveset(sympy.exp(x)-1,x,domain=sympy.S.Reals)
{0}
>>> sympy.solveset(sympy.exp(x)-1,x,domain=sympy.S.Complexes)
ImageSet(Lambda(_n, 2*_n*I*pi), Integers)

在这里,Lambda 表示的是数学公式,第一个是自变量,第二个是函数,最后是自变量的定义域。

在线性代数中,最常见的还是多元一次方程组,那么解法是一样的:

\begin{cases}x+y-10=0 \\ x-y-2=0\end{cases}

>>> sympy.solve([x+y-10, x-y-2], [x,y])
{x: 6, y: 4}

对于三角函数,也是类似的写法:

\begin{cases} \sin(x-y)=0 \\ \cos(x+y)=0 \end{cases}

>>> sympy.solve([sympy.sin(x-y), sympy.cos(x+y)], [x,y])
[(-pi/4, 3*pi/4), (pi/4, pi/4), (3*pi/4, 3*pi/4), (5*pi/4, pi/4)]

 

SymPy 的矩阵工具

在矩阵论中,最常见的就是单位矩阵了,而单位矩阵只与一个参数有关,那就是矩阵的大小。下面就是 3*3,3*2,2*3 大小的矩阵。

>>> sympy.eye(3)
Matrix([
[1, 0, 0],
[0, 1, 0],
[0, 0, 1]])
>>> sympy.eye(3,2)
Matrix([
[1, 0],
[0, 1],
[0, 0]])
>>> sympy.eye(2,3)
Matrix([
[1, 0, 0],
[0, 1, 0]])

另外还有全零和全一矩阵,意思就是矩阵中的所有值全部是零和一。

>>> sympy.ones(2,3)
Matrix([
[1, 1, 1],
[1, 1, 1]])
>>> sympy.zeros(3,2)
Matrix([
[0, 0],
[0, 0],
[0, 0]])

而对角矩阵也可以使用 diag 轻松获得:

>>> sympy.diag(1,1,2)
Matrix([
[1, 0, 0],
[0, 1, 0],
[0, 0, 2]])

而矩阵的加法,减法,乘法,逆运算,转置,行列式,SymPy 都是可以支持的:

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

B = \left(\begin{array}{cc} 1 & 0 \\ 1 & 1 \end{array}\right)

>>> A = sympy.Matrix([[1,1],[0,2]])
>>> B = sympy.Matrix([[1,0],[1,1]])
>>> A
Matrix([
[1, 1],
[0, 2]])
>>> B
Matrix([
[1, 0],
[1, 1]])
>>> A + B
Matrix([
[2, 1],
[1, 3]])
>>> A - B
Matrix([
[ 0, 1],
[-1, 1]])
>>> A * B
Matrix([
[2, 1],
[2, 2]])
>>> A * B**-1
Matrix([
[ 0, 1],
[-2, 2]])
>>> B**-1
Matrix([
[ 1, 0],
[-1, 1]])
>>> A.T
Matrix([
[1, 0],
[1, 2]])
>>> A.det()
2

在某些情况下,需要对矩阵进行加上一行或者加上一列的操作,在这里就可以使用 row_insert 或者 col_insert 函数:第一个参数表示插入的位置,第二个参数就是相应的行向量或者列向量。而在删除上就很简单了,直接使用 row_del 或者 col_del 即可。

>>> A
Matrix([
[1, 1],
[0, 2]])
>>> A.row_insert(1, sympy.Matrix([[10,10]]))
Matrix([
[ 1, 1],
[10, 10],
[ 0, 2]])
>>> A.col_insert(0, sympy.Matrix([3,3]))
Matrix([
[3, 1, 1],
[3, 0, 2]])
>>> A.row_del(0)
>>> A
Matrix([[0, 2]])
>>> A.col_del(1)
>>> A
Matrix([[0]])

在对角化方面,同样可以使用 eigenvals(),eigenvecs(), diagonalize() 函数:

>>> A
Matrix([
[1, 1],
[0, 2]])
>>> A.eigenvals()
{2: 1, 1: 1}
>>> A.eigenvects()
[(1, 1, [Matrix([
[1],
[0]])]), (2, 1, [Matrix([
[1],
[1]])])]
>>> A.diagonalize()
(Matrix([
[1, 1],
[0, 1]]), Matrix([
[1, 0],
[0, 2]]))

在 eigenvals() 返回的结果中,第一个表示特征值,第二个表示该特征值的重数。在特征向量 eigenvecs() 中,第一个表示特征值,第二个表示特征值的重数,第三个表示特征向量。在对角化 diagonalize() 中,第一个矩阵表示 P,第二个矩阵表示 DA = P*D*P^{-1}

在矩阵中,最常见的还是多元一次方程的解。如果要求 Ax =b 的解,可以有以下方案:

>>> A = sympy.Matrix([[1,1],[0,2]])
>>> A
Matrix([
[1, 1],
[0, 2]])
>>> b = sympy.Matrix([3,5])
>>> b
Matrix([
[3],
[5]])
>>> A**-1*b
Matrix([
[1/2],
[5/2]])
>>> sympy.linsolve((A,b))
{(1/2, 5/2)}
>>> sympy.linsolve((A,b),[x,y])
{(1/2, 5/2)}

 

SymPy 的集合论工具

集合论可以说是数学的基础,在任何数学的方向上都能够看到集合论的身影。在 SymPy 里面,有一个类叫做 sympy.sets.sets.set。在集合论里面,常见的就是边界,补集,包含,并集,交集等常见的操作。但是感觉 SymPy 中的集合论操作主要集中在实数域或者复数域上。

对于闭区间 I=[0,1] 和开区间 J = (0,1) 而言,在 SymPy 中使用以下方法来表示:

I = sympy.Interval(0,1)
J = sympy.Interval.open(0,1)
K = sympy.Interval(0.5,2)

其开始和结束的点可以分别使用 start 和 end 来表示:

>>> I.start
0
>>> I.end
1

其长度用 measure 来表示:

>>> I.measure
1

其闭包用 closure 来表示:

>>> I.closure
Interval(0, 1)

其内点用 interior 来表示:

>>> I.interior
Interval.open(0, 1)

判断其边界条件可以使用 left_open 或者 right_open 来做:

>>> I.left_open
False
>>> I.right_open
False

对于两个集合之间的操作,可以参考以下方法:

I = sympy.Interval(0,1)
K = sympy.Interval(0.5,2)
>>> I.intersect(K)
Interval(0.500000000000000, 1)
>>> I.union(K)
Interval(0, 2)
>>> I-K
Interval.Ropen(0, 0.500000000000000)
>>> K-I
Interval.Lopen(1, 2)
>>> I.symmetric_difference(K)
Union(Interval.Ropen(0, 0.500000000000000), Interval.Lopen(1, 2))

实数集 \mathbb{R} 在 SymPy 中用 sympy.S.Reals 来表示,自然数使用 sympy.S.Naturals,非负整数用 sympy.S.Naturals0,整数用 sympy.S.Integers 来表示。补集的计算可以用减号,也可以使用 complement 函数。

>>> sympy.S.Reals
Reals
>>> sympy.S.Reals-I
Union(Interval.open(-oo, 0), Interval.open(1, oo))
>>> I.complement(sympy.S.Reals)
Union(Interval.open(-oo, 0), Interval.open(1, oo))
>>> sympy.S.Reals.complement(I)
EmptySet()
>>> I.complement(K)
Interval.Lopen(1, 2)
>>> I.complement(sympy.S.Reals)
Union(Interval.open(-oo, 0), Interval.open(1, oo))

 

SymPy 的逻辑工具

在逻辑运算中,我们可以使用 A, B, C 来代表元素。&, |, ~, >> 分别表示 AND,OR,NOT,imply。而逻辑运算同样可以使用 sympy.simplify_logic 简化。

A, B, C = sympy.symbols("A B C")
>>> sympy.simplify_logic(A | (A & B))
A
>>> sympy.simplify_logic((A>>B) & (B>>A))
(A & B) | (~A & ~B)
>>> A>>B
Implies(A, B)

 

SymPy 的级数工具

SymPy 的级数工具有一部分放在具体数学(Concrete Mathematics)章节了。有的时候,我们希望计算某个级数是发散的,还是收敛的,就可以使用 is_convergence 函数。考虑最常见的级数:

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

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

>>> n = sympy.Symbol("n", integer=True)
>>> sympy.Sum(1/n, (n,1,sympy.oo)).is_convergent()
False
>>> sympy.Sum(1/n**2, (n,1,sympy.oo)).is_convergent()
True

如果想计算出收敛级数的值,加上 doit() 函数即可;如果想计算有效数字,加上 evalf() 函数即可。

>>> sympy.Sum(1/n**2, (n,1,sympy.oo)).evalf()
1.64493406684823
>>> sympy.Sum(1/n**2, (n,1,sympy.oo)).doit()
pi**2/6
>>> sympy.Sum(1/n**3, (n,1,sympy.oo)).evalf()
1.20205690315959
>>> sympy.Sum(1/n**3, (n,1,sympy.oo)).doit()
zeta(3)

除了加法之外,SymPy 也支持连乘,其符号是 sympy.Product,考虑

\prod_{n=1}^{+\infty}\frac{n}{n+1}

\prod_{n=1}^{+\infty}\cos\left(\frac{\pi}{n}\right)

>>> sympy.Product(n/(n+1), (n,1,sympy.oo)).is_convergent()
False
>>> sympy.Product(sympy.cos(sympy.pi/n), (n, 1, sympy.oo)).is_convergent()
True

 

SymPy 的 ODE 工具

在常微分方程(Ordinary Differential Equation)中,最常见的就是解方程,而解方程主要是靠 dsolve 函数。例如想求解以下的常微分方程:

df/dx + f(x) = 0,

d^{2}f/dx^{2} + f(x) = 0

d^{3}f/dx^{3} + f(x) = 0

可以使用 dsolve 函数:

>>> f = sympy.Function('f')
>>> sympy.dsolve(sympy.Derivative(f(x),x) + f(x), f(x))
Eq(f(x), C1*exp(-x))
>>> sympy.dsolve(sympy.Derivative(f(x),x,2) + f(x), f(x))
Eq(f(x), C1*sin(x) + C2*cos(x))
>>> sympy.dsolve(sympy.Derivative(f(x),x,3) + f(x), f(x))
Eq(f(x), C3*exp(-x) + (C1*sin(sqrt(3)*x/2) + C2*cos(sqrt(3)*x/2))*sqrt(exp(x)))

而常微分方程对于不同的方程类型也有着不同的解法,可以使用 classify_ode 来判断常微分方程的类型:

>>> sympy.classify_ode(sympy.Derivative(f(x),x) + f(x), f(x))
('separable', '1st_exact', '1st_linear', 'almost_linear', '1st_power_series', 'lie_group', 'nth_linear_constant_coeff_homogeneous', 'separable_Integral', '1st_exact_Integral', '1st_linear_Integral', 'almost_linear_Integral')
>>> sympy.classify_ode(sympy.Derivative(f(x),x,2) + f(x), f(x))
('nth_linear_constant_coeff_homogeneous', '2nd_power_series_ordinary')
>>> sympy.classify_ode(sympy.Derivative(f(x),x,3) + f(x), f(x))
('nth_linear_constant_coeff_homogeneous',)

 

SymPy 的 PDE 工具

在偏微分方程(Partitial Differential Equation)中,同样可以直接求解和判断偏微分方程的类型,分别使用函数 pdsolve() 和 classify_pde()。假设 f = f(x,y) 是一个二元函数,分别满足以下偏微分方程:

\partial f/\partial x + \partial f/\partial y =0

\partial f/\partial x + \partial f/\partial y + f = 0

\partial f/\partial x + \partial f/\partial y + f + 10 = 0

>>> f = sympy.Function("f")(x,y)
>>> sympy.pdsolve(sympy.Derivative(f,x)+sympy.Derivative(f,y),f)
Eq(f(x, y), F(x - y))
>>> sympy.pdsolve(f.diff(x)+f.diff(y)+f,f)
Eq(f(x, y), F(x - y)*exp(-x/2 - y/2))
>>> sympy.pdsolve(f.diff(x)+f.diff(y)+f+10,f)
Eq(f(x, y), F(x - y)*exp(-x/2 - y/2) - 10)

查看类型就用 classify_pde() 函数:

>>> sympy.classify_pde(f.diff(x)+f.diff(y)+f)
('1st_linear_constant_coeff_homogeneous',)
>>> sympy.classify_pde(f.diff(x)+f.diff(y)+f+10,f)
('1st_linear_constant_coeff', '1st_linear_constant_coeff_Integral')
>>> sympy.classify_pde(f.diff(x)+f.diff(y)+f+10,f)
('1st_linear_constant_coeff', '1st_linear_constant_coeff_Integral')

不过目前的 PDE 解法貌似只支持一阶偏导数,二阶或者以上的偏导数就不支持了。

 

SymPy 的数论工具

在数论中,素数就是一个最基本的概念之一。而素数的批量计算,比较快的方法就是筛法(sieve method)。在 sympy 中,同样有 sympy.sieve 这个工具,用于计算素数。如果想输出前100个素数,那么

>>> sympy.sieve._reset()
>>> sympy.sieve.extend_to_no(100)
>>> sympy.sieve._list
array('l', [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631])

如果想输出一个区间内的所有素数,可以使用 primerange(a,b) 函数:

>>> [i for i in sympy.sieve.primerange(10,100)]
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

search() 函数是为了计算某个数附近是第几个素数:

>>> sympy.sieve.search(10)
(4, 5)
>>> sympy.sieve.search(11)
(5, 5)

如果只想获得第 n 个素数,则使用函数 sympy.ntheory.generate.prime(n) 即可。如果是希望计算 x 后面的下一个素数,使用 sympy.ntheory.generate.nextprime(x) 即可。判断 x 是否是素数,可以使用 sympy.ntheory.generate.isprime(x)。

>>> sympy.ntheory.generate.prime(10)
29
>>> sympy.ntheory.generate.nextprime(10)
11
>>> sympy.ntheory.generate.nextprime(11)
13
>>> sympy.ntheory.generate.isprime(11)
True
>>> sympy.ntheory.generate.isprime(12)
False

除此之外,SymPy 的数论方法还有很多,需要读者根据 SymPy 的官方文档自行探索。

 

SymPy 的范畴论工具

SymPy 还支持范畴论(Category Theory)的一些计算方法,在这里简要地列举一下。

>>> A = sympy.categories.Object("A")
>>> B = sympy.categories.Object("B")
>>> f = sympy.categories.NamedMorphism(A,B,"f")
>>> f.domain
Object("A")
>>> f.codomain
Object("B")

由于范畴论是数学的“黑话”,因此其余方法留给范畴论的科研人员自行翻阅。

总结:

整体来看,SymPy 是一个非常卓越的 Python 开源符号计算库。在符号计算领域,不仅支持常见的微积分,线性代数,几何运算,还支持集合论,微分方程,数论等诸多数学方向。后续笔者将会持续跟进并研究这一卓越的开源工具库。

 

参考文献:

  1. Meurer A, Smith C P, Paprocki M, et al. SymPy: symbolic computing in Python[J]. PeerJ Computer Science, 2017, 3: e103.
  2. GitHub:https://github.com/sympy/sympy
  3. SymPy:https://www.sympy.org/en/index.html
  4. Sympy 维基百科:https://en.wikipedia.org/wiki/SymPy
  5. GreatX’s Blog:数值 Python:符号计算:https://vlight.me/2018/04/01/Numerical-Python-Symbolic-Computing/
  6. SymPy 符号计算-让Python帮我们推公式:https://zhuanlan.zhihu.com/p/83822118
  7. Python 科学计算利器—SymPy库:https://www.jianshu.com/p/339c91ae9f41

 

新加坡国立大学的数据科学与机器学习项目介绍

新加坡国立大学(National University of Singapore)是一所综合性的大学,根据泰晤士报和世界大学排名来看,NUS 在整个亚洲的排名是非常靠前的。同时,数学系(Department of Mathematics)则是在理学院(Science)下的一个院系。

NUS数学系的介绍

新加坡国立大学数学系的前身可以追溯到 1929 年的 Raffles College。当时理学院开设了数学,化学,物理三门课程,不过总共也就只有十个学生和三位教师,其中有一位是数学教师。第一届数学系的领导(从 1931 年到 1959 年)是Alexander Oppenheim教授,他是在美国芝加哥大学获得的博士学位。从 1929 年开始,在新加坡的教育系统中,数学教育事业得到了巨大的发展,对现在的新加坡国立大学和南洋理工大学的建立起到了至关重要的作用。

随着 NUS 的建立,数学系就进入了一个新的时代。新的校区在 Kent Ridge,1986 年理学院和数学系就在这里成立。这个时候,数学系就有了巨大的发展,不仅在本科生的招生规模方面有了巨大提高,在研究生项目规模上也有了一定的深度的提升。

NUS数学系首页

新加坡国立大学的数学系与国内的数学系有所不同。一般情况下,国内的数学系能够提供的专业包括数学与应用数学(Mathematics and Applied Mathematics),信息与计算科学(Information and Computing Science)与统计学(Statistics),有的时候会加上金融数学(Financial Mathematics)这一方向。而新加坡国立大学的数学系(Department of Mathematics)与统计系(Statistics)是分开的两个院系,虽然学生可以互相之间选择对方的课程,但是两者却是分属不同的院系。

NUS数学系本科专业

从数学系的首页来看,对于本科生而言,通常都有机会进行双学位的选择,例如:

  1. 计算机科学与数学;
  2. 经济学与数学;

因此,有不少的本科生都会有两个专业的学位证书。目标是为了让学生能够在未来从事数学研究和工业界的工作都打下坚实的基础。

NUS数学系硕士专业

NUS 的项目分成两块,coursework 项目和 Research 项目。第一个主要是以授课型的研究生为主,后者主要是为博士生或者准备攻读博士的人而准备的。对于硕士生而言,一般一两年就可以硕士毕业,只要修课的学分满了即可。

对于众多硕士生而言,进入 NUS 之前就要根据自身情况来选择一个合适的方向进行申请。对于硕士生的项目,数学系可以提供数学,金融数学等方向的课程,并且近期也提供了数据科学与机器学习专业(Data Science and Machine Learning)的课程。

项目介绍

申请条件

数据科学与机器学习项目是数学系,统计系,计算机系联合举办的为期一至两年的硕士生项目。期望学生的本科背景是数学方向,应用数学方向,统计与物理方向等。同时对学生的英语能力有一定的要求,希望对于母语不是英语的学生能够达到托福 85 分以上或者雅思 6.0 分以上的成绩。

项目课程要求

在课程安排方面,这个项目会有 20 个学分的课程,5 门核心课程,包括:

  1. Introduction to Big Data for Industry;
  2. Optimisation for Large-Scale Data-Driven Inference;
  3. Foundations of Machine Learning/Theory and Algorithms for Machine Learning;
  4. Cloud Computing;
  5. DSML Industry Consulting and Applications Project.

而选修课方面包括机器学习,数据挖掘,大数据,计算机视觉,金融数学等方向的专业课程。同样也会要求选择 20 个学分的选修课程即可。

学费

在学费方面,该项目是没有奖学金的,而一年的学费是 45000 新币,大约为 23 万人民币。

NUS申请流程

如果对这个项目感兴趣的同学,需要在 2020 年的 3 月 15 日之前提交申请,才有机会在 2020 年 8 月入学。

NUS数学系联系方式

如果有任何问题的话,可以考虑发邮件给 askmathpg@nus.edu.sg 或者拨打上面的电话号码。

 

读博的意义

读博的意义

在本科数学系,身边的学生大致分为几种情况:第一种学生是高中数学学的比较好,也没有什么特别爱好的专业,于是通过高考或者保送进入了数学系;第二种学生是为了转行计算机或者金融,就来数学系过渡一下,未来从事其他行业的工作;第三种学生是想读其他的专业,但是由于高考分数不足,被分配到了数学系;第四种学生就是为了攀登科学的高峰,立志要在数学界从事科研工作,在填报志愿的时候就果断进入数学系。一般情况下,学生在拿到本科学位之后,如果还想继续从事数学科研的话,就会选择继续攻读数学方向的博士学位,无论在国内还是国外继续学业。640-6

在数学系本科或者硕士的时候,学生们通常都是按部就班的上课,做作业,上讨论班,或者每周集体分享一些论文或者学术资料。到了最后一个学期需要写论文的时候其实也不需要有太多的创新工作(更直接一点的话就是做不出来什么创新的工作),学生们大概就是整理一篇前沿的学术论文或者学术书籍就算完成了论文。在这两个阶段,导师基本上都会告诉学生,什么课题可以做得出来,什么课题比较难被做出来。或者就是导师其实已经知道某个问题的解决步骤和方法了,只需要学生执行完成就可以了。虽然在数学系的本科或者硕士都是按部就班的学习,但是这种学习是非常有必要的,毕竟不积跬步无以至千里,不积小流无以成江海。

QQ20191027-154338@2x

但是到了博士阶段就不一样了,导师给博士生的题目基本上就是学术界未知的问题。如果这个问题被解决了,那就不能够作为一个博士论文的题目。在某些极端情况下,导师连这个题目最终能不能够被学生做出来都不知道,只能够大致判断出这个问题的难易程度。数学系的纯数学方向和其他专业还不一样,某些专业跑跑数据改改模型就能够发表所谓的优秀论文了。而想要做纯数学的研究不仅需要通过天马行空的想象能力来寻找灵感,还需要有强大的逻辑推理能力把之前的想象整理成严谨的学术论文。而这种能力,仅仅靠本科或者硕士的训练是远远不够的,按部就班的读书考试也许能够应付小学,中学,大学,甚至研究生阶段,但是却无法完成博士阶段的任务目标。

QQ20191027-154259@2x

当年笔者在博士期间的研究方向是“复平面上多项式的 Julia 集合正测度”(PS:估计不是相关方向的人都不太读得懂这个题目的意思)。首先要知道复平面,其次要知道 Julia 集合,再次要知道正测度是什么意思。即使这些名词和概念都知道了,也不足以撬动这个题目。要想解决这个题目,除了导师的必要指导之外,还要自行去查阅各种论文资料来详细阅读。记得当年读过好几篇三五十页的 Annals of Mathematics(数学年刊)的论文,还读过一篇上百页的预印稿(关键是这篇论文有一个核心步骤还是错误的)。在此情况下,导师也只能够给博士生圈定一个论文的范围,告诉学生可以去参考其中的思路和方法,至于学生能不能够读懂这些文献,是导师无法保证的。而纯数学论文与其他专业最明显的不同就是满篇都是数学公式的推导,有很多地方充斥着“显然”,“易得”,“显而易见”诸多词汇。有一种情况是写论文的作者没有想明白,然后糊弄了一把;另外一种情况是这个地方真的是显而易见的,只是读者没有明白。纯数学论文的其中一页读上一两天并不是一件罕见的事情,一篇论文读一个学期能读明白也算完成了一件还不错的任务。PS:数学系有的教材就可以让学生一页读上好几天,例如 GTM 52。某些专业做不出来实验还可以把原因归结为材料不足,经费不足,设备不够,但是纯数学专业看不懂论文只能够把绝大部分原因归结为自己,因为草稿纸,笔,打印机,网络都是买得起的,客观上并不存在任何阻碍。

Julia_0.4_0.6Julia-set_z2+c_-0.742_0.1_5000

在整个科研的过程中,一般都会经历:高峰->低谷->逐步爬坡回升->重新达到高峰的这样一个流程状态。正如:邓宁-克鲁格心理效应。从博士生的五年生涯来看,通常都会经历这几个不同的阶段:

1. 愚昧山峰:刚入学第一年的时候;

2. 低谷:第二年,第三年的时候;

3. 回升:第四年,第五年的时候。

而这种状态的经历是在读本科,硕士阶段都无法获得的,只有在经历了博士的求学之路才能够逐渐体会。当然,也有的导师也会帮学生写论文,整理论文,甚至送论文给学生,这样的学生可以在学生圈谋求一份教职,但是也永远体会不到这些心路历程了。这份心路历程在人生中是一场宝贵的财富,教会了如何在绝望之谷的时候迅速反弹回升,如何在逆境中持续成长,如何在被打击之后迅速恢复。

640-7

后来由于种种原因笔者没有继续从事博士期间的科研项目,到了企业从事普通的研发工作。在工作中,通常领导们也不会直接告诉下属项目的细节和执行方案,只会大致说出项目方向,该达成的目标是什么,下属们需要自行思考这个项目的背景是什么,为什么要启动这个项目,该怎么实现这个项目,怎么样做才能够把项目做好做完。这个过程跟读博期间的过程有点类似,但是又有所不同。相同的是都只能够拿到一个大致的方向,同时需要发挥自主能动性去做完细节,争取身边的各种资源,并且保证论文或者项目的落地。不同的是,工作期间并不会给下属很长的空窗期,并不会像博士期间给学生大几个月甚至一年的空闲时间去研究某个课题或者方向。基本上都是一旦制定了方向,就要立刻给出大致的方案和解决思路,然后给出项目的排期和执行计划,并且给出项目的风险点是什么,最终开始逐步落实方案和具体的工作内容。不过,在工作中,在大多数情况下也不会要求一定要做一个行业第一的产品,而且很多项目由于种种原因也无法做到行业第一。有的时候,行业第一的量化标准还不太好做,如果有明确规则的,例如挣钱的多少,日活月活多少,比赛的第一,这种是可以制定出来的。但是大多数情况下其实也不太好制定出来。不过在工作中还是可以精益求精,以行业的第一为目标来逐步提升的。可以在现有的情况和条件下把项目做得尽量完善,在提升效率方面比之前能够更加好,在节省人力方面能够做到较少人力就维护较多的事情。

在工作之后,虽然也很难体会到一篇论文读半年的时候,但是在博士期间学会的资料整理,收集,汇总,甚至日常的笔记和资料总结,都是在工作中非常常用的技能。甚至一些时间管理和项目管理的经验,也是在工作中必备的技能之一。

640-2

640-3
PHD期间的时间安排

640-4

640-5
工作的时间安排

很难说读博这件事情对所有的人都有意义,因为每个人都有着不同的生长环境和家庭条件,在如此复杂的情况下,给出一个固定的答案其实没有任何意义。何况每个人的想法也会随着时间的迁移,环境的变化而做出改变。之前想做的一些事情可能后面就不感兴趣了,一直想追求的一些目标可能也不再继续追求了。只能够根据具体的情况,在不同的阶段来定制化地给每个人相应的建议和支持(个性化推荐)。无论做什么样的事情,最好都要保持一种乐观向上的心态,不能够一直处于一种低估和不能自拔的阶段。如果在本科,硕士,甚至博士期间都没有找好自己的定位,也可以尝试在工作之后逐步把自己拉上正规,在期间调整自己的状态和节奏,让自己的幸福感逐步提升。无论在哪里,无论最终是否做科研,最终都是为了过上更好的生活。

张戎

2019年10月27日

深度学习在时间序列分类中的应用

本篇博客将会分享几篇文章,其内容主要集中在深度学习算法在时间序列分类中的应用。

无论是图像分类,文本分类,还是推荐系统的物品分类,都是机器学习中的常见问题和应用场景。同样的,时间序列的分类问题也是研究时间序列领域的重要问题之一。近期,神经网络算法被用于物体识别,人脸识别,语音分类等方向中,于是有学者用深度学习来做时间序列的分类

假设

X=\{x_{1},\cdots,x_{n}\}

是一个长度为 n 的时间序列,高维时间序列

X = \{X^{1},\cdots,X^{M}\}

则是由 M 个不同的单维时间序列而组成的,对于每一个 1\leq i\leq M 而言,时间序列 X^{i} 的长度都是 n. 而时间序列的分类数据通常来说都是这种格式:数据集

D=\{(X_{1},Y_{1}),(X_{2},Y_{2}),\cdots,(X_{N},Y_{N})\}

表示时间序列与之相应的标签,而 Y_{i} 是 one hot 编码,长度为 K(表示有 K 个类别)。

整体来看,时间序列分类的深度学习方案大体是这个样子的:输入的是时间序列,通过某个神经网络算法进行端到端的训练,最后输出相应的分类概率。

ReviewFigure1.png

而做时间序列分类的深度学习算法分成生成式(Generative)判别式(Discriminative)两种方法。在生成式里面包括 Auto Encoder 和 Echo State Networks 等算法,在判别式里面,包括时间序列的特征工程和各种有监督算法,还有端到端的深度学习方法。在端到端的深度学习方法里面,包括前馈神经网络,卷积神经网络,或者其余混合模型等常见算法。

ReviewFigure5.png

深度学习算法在时间序列分类中的应用:Baseline

这一部分将会介绍用神经网络算法来做时间序列分类的 Baseline,其中包括三种算法,分别是多层感知机(MLP),FCN(Fully Convolutional Network)和 ResNet。其论文的全名是《Time Series Classification from Scratch with Deep Neural Networks: A Strong Baseline》。这篇论文中使用的神经网络框架如下图所示:

DNN_Baseline_结构1.png

多层感知机(MLP)模型使用了全连接层,每个隐藏层大约 500 个神经元,然后使用 ReLU 作为激活函数,同时使用 Dropout 来防止过拟合,最后一层是 Softmax 层。MLP 中一个基础的块包括:

\tilde{x} = f_{dropout, p}(x),

y = W\cdot \tilde{x} + b,

h = ReLU(y).

除了前馈神经网络之外,全卷积网络(FCN)同样可以作为时间序列的特征提取工具,一个卷积块包括:

y = W \otimes x + b,

s = BN(y),

h = ReLU(s),

在这里,\otimes 指的是卷积算子,BN 指的是 Batch Normalization,ReLU 则是激活函数。

Residual Network 是在 FCN 的基础上进行的改造。令 Block_{k} 来表示第 k 个卷积块,而 Residual 块就定义为:

h_{1} = Block_{k_{1}}(x),

h_{2} = Block_{k_{2}}(h_{1}),

h_{3} = Block_{k_{3}}(h_{2}),

y=h_{3} + x,

\hat{h}=ReLU(y).

其中,k_{1} = 64, k_{2} = 128, k_{3} = 128

ReviewFigure6_ResNet.png

评价指标

Mean Per Class Error (in Multi-class Classification only) is the average of the errors of each class in your multi-class data set. This metric speaks toward misclassification of the data across the classes. The lower this metric, the better.

模型的评价指标使用的是 Mean Per-Class Error,指的是在多分类场景下,每一类(Class)错误率的平均值。换句话说,一个数据集 D=\{d_{k}\}_{1\leq k\leq K} 是由 K 个类的元素构成的,每个类的标签是 C=\{c_{k}\}_{1\leq k\leq K},通过模型其实可以计算出模型对每一个类的错误率 e_{k},那么模型的 MPCE 就是:MPCE= \sum_{1\leq k\leq K} e_{k}/K.

其实验结论是:

DNN_Baseline_实验数据1.png

MSCNN

MSCNN 的全称是 Multi-Scale Convolutional Neural Networks,相应的论文是《Multi-Scale Convolutional Neural Networks for Time Series Classification》

在时间序列的分类算法里面,通常来说,可以分成以下几种:

  1. 基于距离的方法(distance-based methods):kNN,SVM(相似核),DTW;
  2. 基于特征的方法(feature-based methods):SVM,逻辑回归等;
  3. 基于神经网络的方法(neural network-based methods):CNN 等;

正如前文所提到的,一条时间序列通常可以写作 T=\{t_{1},\cdots,t_{n}\},其中 t_{i} 表示在时间戳 i 下的取值,并且时间序列 T 的长度是 n。在时间序列分类的场景下,每一条时间序列对应着唯一的一个标签(label),也就是说 D=\{(T_{i},y_{i})\}_{i=1}^{N}。其中 D 集合里面包含 N 条时间序列,每条时间序列 T_{i} 对应着一个标签 y_{i}y_{i} 表示分类值集合 \mathcal{C} = \{1,\cdots,C\} 中的元素,C\in \mathbb{Z}^{+}

MSCNN 的整体结构:

在 Multi-Scale Convolutional Neural Network(MSCNN)中,包括几个串行的阶段,

  1. 变换阶段(Transformation Stage):包括恒等变换,下采样,谱变换等变换方式,每一种方式都是一个分支,并且也是卷积神经网络的输入;
  2. 局部卷积(Local Convolution Stage):使用卷积层来对不同的输入提取特征,不同的输入分支之间是相互独立的,输出的时候都会经过一个最大值池化(max pooling)的过程;
  3. 整体卷积(Full Convolution Stage):把上一步提取到的特征进行拼接(concatenate),然后使用全连接层并且加上一个 softmax 层来做多分类。

如下图所示,MSCNN 是一个端到端的训练网络结构,所有参数都是通过后向传播算法得到的。

MSCNN结构1.png

首先来看神经网络的第一步,变换阶段(Transformation Stage),也就是神经网络的多尺度的输入。在不同的尺度下,神经网络能够提炼到不同类型的特征。长期的特征(long-term features)反映了时间序列的整体趋势,短期的特征(short-term features)反映了时间序列的局部的微妙变化。要想判断时间序列的形状,不仅要参考整体的特征,也要参考局部的特征,这两者对于判断时间序列的形状都具有一定的辅助作用。

在 Transformation Stage,identity map 指的是恒等变换,也就是说时间序列是原封不动的作为神经网络的输入数据。对于 Smoothing Transformation,指的就是对时间序列进行必要的平滑操作,将新的时间序列作为神经网络的输入数据。在这种情况下,我们可以对时间序列 T=\{t_{1},\cdots,t_{n}\} 进行移动平滑,i.e.

T^{\ell}=(x_{i}+x_{i+1}+\cdots+x_{i+\ell-1})/\ell, 0\leq i\leq n-\ell+1,

其中的 \ell\in \mathbb{Z}^{+} 表示窗口长度。对于不同的窗口长度 \ell,我们可以的到不同的时间序列平滑序列,但是它们的长度都是一样的,都是原始的时间序列长度 n

而下采样(down sampling)指的则是对时间序列的间隔进行抽样操作。假设时间序列 T=\{t_{1},\cdots,t_{n}\},下采样的比例是 k,也就是说我们每隔 k 个点保留时间序列的取值,i.e.

T^{k} = \{t_{1+k\cdot i}\}, 0\leq i \leq [(n-1)/k].

用这种方法,我们可以对 k=1,2,3,\cdots 来进行下采样的时间序列提取。在进行了恒等变换,平滑变换,下采样之后,时间序列就可以变成多种形式,作为神经网络的输入。

其次,在神经网络部分,本文使用了一维(1-D)的卷积层和最大值池化的方法来提取特征,并且在局部卷积阶段之后把提炼到的抽象特征进行拼接(concatenate)。拼接完了之后,持续使用卷积层和池化层进行特征的提取,然后使用全连接层(fully connected layers)和 softmax 层来进行时间序列类别的预测。

数据增强

在深度学习里面,由于是端到端的训练网络,因此是需要相对多的样本数据的,于是有的时候需要进行数据增强(data augmentation)。也就是在现有的基础上获得更多的训练数据。对于时间序列 T=\{t_{1},\cdots,t_{n}\},可以定义一个子序列:

S_{i:j} = \{t_{i}, t_{i+1},\cdots,t_{j}\}, 1\leq i,\leq j\leq n

对于正整数 s\in \mathbb{Z}^{+},可以生成 n-s+1 个子序列如下所示:

Slicing(T,s) = \{S_{1:s},S_{2:s+1},\cdots,S_{n-s+1:n}\},

这些子序列的标签与原始的时间序列 T 是一样的。

本文用到的数据集情况如下表所示:

MSCNN数据集1.png

实验数据如下图所示:

MSCNN实验1MSCNN数据集2

结论

本文使用了 MCNN 来对变换之后的时间序列进行特征提取,并且进行了端到端的模型训练。并且也讨论了卷积神经网络使用在 shapelet learning 上的一些逻辑和方法,然后解释了 MSCNN 在时间序列分类上能够有不错表现的原因。但是所有的 TSC 数据集都不算特别大,对端到端的训练模式有一定的限制。

GASF 和 GADF 方法

这篇文章《Imaging Time Series to Improve Classification and Imputation》介绍了如何把时间序列转换成图像,包括 GASF 方法和 GADF 方法。

假设时间序列是 X = \{x_{1},\cdots, x_{n}\},长度是 n,我们可以使用归一化方法把时间序列压缩到 [0,1] 或者 [-1,1]

\tilde{x}_{0}^{i} = (x_{i} - \min(X))/(\max(X) -\min(X)),

\tilde{x}_{-1}^{i} = ((x_{i} - \max(X)) + (x_{i}-\min(X)))/(\max(X) - \min(X)),

此时的 \tilde{x}_{0}^{i}\in[0,1], \forall 1\leq i\leq n\tilde{x}_{-1}^{i} \in [-1,1],\forall 1\leq i\leq n。于是可以使用三角函数来代替归一化之后的值。下面通用 \tilde{x}_{i} 来表示归一化之后的时间序列,令 \phi_{i} = \arccos(\tilde{x}_{i})\tilde{x}_{i} \in [-1,1]1\leq i\leq n。因此,\phi_{i}\in[0,\pi],于是,\sin(\phi_{i}) \geq 0

定义矩阵 GASF(Gramian Angular Summation Field)

GASF = [\cos(\phi_{i}+\phi_{j})]_{1\leq i,j\leq n}

于是,

GASF = [\cos(\phi_{i})\cdot \cos(\phi_{j}) - \sin(\phi_{i})\cdot \sin(\phi_{j})]_{n\times n}

\tilde{X}=(\cos(\phi_{1}),\cdots,\cos(\phi_{n}))^{T},可以得到

GASF = \tilde{X} \cdot \tilde{X}^{T} - \sqrt{I - \tilde{X}^{2}} \cdot \sqrt{I - \tilde{X^{T}}^{2}}

以上的都是 element 乘法和加法,I 表示单位矩阵。它的对角矩阵是

diag(GASF) = \{\cos(2\phi_{1}),\cdots, \cos(2\phi_{n})\}

= \{2\cos^{2}(\phi_{1})-1,\cdots,2\cos^{2}(\phi_{n})-1)\} = \{GASF_{ii}\}_{1\leq i\leq n}.

如果是使用 min-max normalization 的话,是可以从 diag(GASF) 反推出 \tilde{x}_{i} 的。因为,2 \tilde{x}_{i}^{2} - 1 = 2\cos^{2}(\phi_{i}) - 1 = GASF_{ii},可以得到 y_{i} = \sqrt{(GASF_{ii}+1)/2}

定义 GADF(Gramian Angular Difference Field)如下:

GADF = [\sin(\phi_{i}-\phi_{j})]_{1\leq i,j\leq n}

= [\sin(\phi_{i})\cdot cos(\phi_{j}) - \cos(\phi_{i})\cdot\sin(\phi_{j})]_{1\leq i,j\leq n}

= \sqrt{1-X^{2}}\cdot X^{T} - X \cdot \sqrt{1-(X^{T})^{2}}.

GASFGADF1.png

Markov Transition Field(MTF)

除了 GSAF 和 GSDF 之外,《Imaging Time Series to Improve Classification and Imputation》,《Encoding Time Series as Images for Visual Inspection and Classification Using Tiled Convolutional Neural Networks》,《Encoding Temporal Markov Dynamics in Graph for Time Series Visualization》也提到了把时间序列转换成矩阵 Image 的算法 MTF。在 pyts 开源工具库里面,也提到了 MTF 算法的源码。

假设时间序列是 X = \{x_{1},\cdots,x_{n}\},我们把它们的值域分成 Q 个桶,那么每一个 x_{i} 都可以被映射到一个相应的 q_{j} 上。于是我们可以建立一个 Q\times Q 的矩阵 Ww_{ij} 表示在桶 j 中的元素被在桶 i 中的元素跟随的概率,也就是说 w_{ij} = P(x_{t}\in q_{i}|x_{t-1}\in q_{j}),同时,它也满足 \sum_{j=1}^{Q}w_{ij} =1。于是,得到矩阵 W = (w_{ij})_{1\leq i,j\leq Q}

MTF1.png

除此之外,我们也能够计算一个迁移概率矩阵 M。其中 $m_{ij}$ 表示桶 i 中的元素迁移至桶 j 中的概率 P(q_{i}\rightarrow q_{j}),同样有 \sum_{1\leq j\leq Q} m_{ij} =1。因此,我们同样可以构造出一个 Q\times Q 的矩阵将时间序列可视化。

时间序列的降维方法有两种:

  1. 分段聚合(PAA):使用局部平均等方法,把时间序列进行降维;
  2. 核变换(Kernel):使用 Bivariate Gaussian 核或者均值核来把时间序列进行降维。

在把时间序列进行可视化之后,对于时间序列分类的场景,就可以使用 CNN 的技术方案来做了。如下图所示:

tildeCNN.png

其实验数据效果如下:

tildeCNN实验数据1.png

Time Le-Net

在本篇文章《Data Augmentation for Time Series Classification using Convolutional Neural Networks》中,主要用到了卷积神经网络来做时间序列的分类。

time_lenet_1.png

除此之外,也使用了不少数据增强(Data Augmentation)的技术。包括前面提到的 Window Slicing(WS)方法。也考虑了 Warping 的变换技巧,例如 Warping Ratio = 1/2 或者 2。这种时间扭曲指标比率可以通过交叉验证来选择。该方法叫做 Window Warping(WW)技术。

另外也有其余论文使用卷积神经网络做时间序列分类,例如《Convolutional neural networks for time series classification》,如下图所示:

CNN_figure1.png

Multi-Channels Deep Convolutional Neural Networks

在高维时间序列的分类中,有人提出用多通道的卷积神经网络来进行建模。

multichannelcnn_figure3.png

整体来看,分成四个部分。前三个部分作为特征提取工具,最后一层作为分类工具。

  1. Filter Layer:
  2. Activation Layer:
  3. Pooling Layer:
  4. Fully-Connected Layer:

实验对比数据如下:

multichannelcnn_table1.png

结论:

在本篇博客中,列举了一些深度学习算法在时间序列分类中的应用,也介绍了部分数据增强的方法和时间序列数据变换的方法。从以上各篇文章的介绍来看,深度学习在时间序列分类领域上应该是大有可为的。

参考资料:

  1. Wang Z, Yan W, Oates T. Time series classification from scratch with deep neural networks: A strong baseline[C]//2017 international joint conference on neural networks (IJCNN). IEEE, 2017: 1578-1585.
  2. Cui Z, Chen W, Chen Y. Multi-scale convolutional neural networks for time series classification[J]. arXiv preprint arXiv:1603.06995, 2016.
  3. Wang Z, Oates T. Imaging time-series to improve classification and imputation[C]//Twenty-Fourth International Joint Conference on Artificial Intelligence. 2015.
  4. Wang Z, Oates T. Encoding time series as images for visual inspection and classification using tiled convolutional neural networks[C]//Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.
  5. Liu L. Encoding Temporal Markov Dynamics in Graph for Time Series Visualization, Arxiv, 2016.
  6. Fawaz H I, Forestier G, Weber J, et al. Deep learning for time series classification: a review[J]. Data Mining and Knowledge Discovery, 2019, 33(4): 917-963.
  7. Zhao B, Lu H, Chen S, et al. Convolutional neural networks for time series classification[J]. Journal of Systems Engineering and Electronics, 2017, 28(1): 162-169.
  8. Le Guennec A, Malinowski S, Tavenard R. Data augmentation for time series classification using convolutional neural networks[C]. 2016.

时间序列的标签

本篇文章是为了介绍一种基于少量样本标记而获得更多样本的方法,论文的原文是《Label-Less: A Semi-Automatic Labeling Tool for KPI Anomalies》,是清华大学与多家公司(必示科技,中国建设银行等)的合作论文。

在时间序列异常检测中,因为标注的成本比较大,于是需要寻找一种较少而高效地标注时间序列异常点的方法。在该论文中,Alibaba,Tencent,Baidu,eBay,Sogou提供了上千条时间序列(每条时间序列大约是2-6个月的时间跨度),作者们进行了 30 条 KPIs 的标注工作。但是其标注成本依旧是很大的,于是作者们想到了一种异常相似搜索(anomaly similarity search)的算法,目标是对已经标注好的时间序列异常模式进行模版搜索。目的就是达到 label-less,也就是较少的标注而获得更多的标注数据。

在本篇论文中,在异常检测的过程中,作者们使用了时间序列的预测模型(time series prediction models)来获得时间序列的特征,使用了孤立森林(Isolation Forest) 来对时间序列的特征来做无监督的异常检测。并且其效果由于 one class svm 算法和 local outlier factor 算法。在搜索的部分,作者使用了加速版的 DTW 算法(accelerated dynamic time warping approach)来做相似度的搜索和模式的匹配。其中也尝试了各种技巧和方法,包括 constrained DTW,LB Keogh 方法,early stopping 算法等工具。

整个 Label-Less 的架构图如下表示:

Fig2.png

其中的 Operators 指的是业务运维人员,面对着无标记的多条时间序列曲线。系统首先会进行无监督的异常检测算法啊,包括时间序列的预处理(归一化等)操作,然后使用差分(Difference),移动平均算法(moving average),带权重的移动平均算法(weighted moving average),指数移动平均(ewma),holt winters,ARIMA 等算法来做特征的提取。此时,对于不同的时间序列预测工具,我们可以得到不同的预测值,然后把预测值减去实际值并且取绝对值,就得到时间序列的误差序列。i.e. |p_{i} - x_{i}| 就作为数据点 x_{i} 的特征。

在这种情况下,由于用了六个时间序列预测算法,因此原始的时间序列 X (n\times 1) 就可以变成特征矩阵 X' (n\times 1)。对于特征矩阵 X' 可以使用 isolation forest 来做无监督的异常检测并且做阈值的设定;如下图所示:

Fig3.png

而另外的一部分的异常相似搜索(anomaly similarity search)是在第一部分的基础上在做的,Unsupervised Anomaly Detection 会输出疑似异常或者候选异常,并且基于已知的异常模板(Anomaly Template)进行相似度的匹配,此时可以使用 accelerated DTW 算法,选择出最相似的 Top-K 异常,然后运维人员进行标注,得到更多的样本。

由于,对于两条长度分别是 mn 的时间序列,DTW 相似度算法的时间复杂度是 O(mn),因此在搜索的时候需要必要的加速工作。在这种地方,作者们使用了 LB-Kim,LB-Keogh,LB-Keogh-Reverse 算法来做搜索的加速工作。而这些的时间复杂度是 O(m+n)。整体的思路是,如果两条时间序列 qc 的 LB-Kim,LB-Keogh,LB-Keogh-Reverse 的下界大于某个阈值,则不计算它们之间的 DTW 距离。否则就开始计算 DTW。并且在计算 DTW 的时候,如果大于下界,则会提前终止(early stopping),不会继续计算下去。如果都没有大于阈值,则把这个候选曲线和 dist 距离放入列表,最后根据列表中的 dist 来做距离的逆序排列。

整体流程如下:

AnomalySimilaritySearch

其运行速度也比直接使用 DTW 快不少:

Table3.png

Label-Less 的交互页面如下所示:

图(a)表示使用无监督算法获得的疑似异常;

图(b)表示使用异常搜索算法获得的异常结果。

Fig10.png

下图则表示模板,m 表示模板的长度,c 表示相似的异常候选集个数;

Fig11

总结:

整体来看,本文提供了一种通过少量人工标注无监督算法相似度算法来获得更多样本的方法。在候选的时间序列条数足够多的时候,是可以进行时间序列的相似度匹配的。这给未来在运维领域提供海量的时间序列标注数据给予了一定的技术支持。

 

怀念 Jett

​之前笔者写过不少文章,其中不仅包括技术和数学文章,还有一些日常学习工作的心得,甚至还写过几篇关于旅游的流水账,但是却很少写关于人物的文章。最近我打算写一篇关于人物的文章,用于纪念在工作中一起战斗过的伙伴 Jett。

许多年前,我还在学校读书的时候,就有前辈告诉我,交朋友的时候基本上就只能够在学校,离开了学校之后在职场中想交到合适的朋友是比较困难的。当时作为一枚职场菜鸟的我,也只能够表示对这句话的认同。直到在工作后遇到了 Jett,我对这个观点就有了自己的看法。

屏幕快照 2019-08-10 下午10.02.49

我是2015年7月作为校招生进入公司,Jett 则是2015年10月通过社招进公司的。当年虽然两人身处同一个部门,但是由于不在一个中心,也不是同一条业务线,并且这两个中心平时也没啥日常工作的交集,因此我和 Jett 同处一个部门许久却互相不认识对方。就好比在学校里面,虽然身处同一个院系,甚至同一栋宿舍楼,由于种种原因而不认识对方。

随着工作时间的增加,到 2016 年的时候笔者就已经过了新手保护期。所谓新手保护期,就是每一个新人其实都有一段适应公司的过程,公司也会给人一定的保护时间,但是一旦过了这个时间就不算新人了。大约到了2016年5月份的时候,部门内部启动了一个用机器学习的方法来做安全对抗的项目。当年的安全中心并没有机器学习的从业者,因此需要从其他中心抽调人手去支持他们的项目。在一些机缘巧合之下,我作为数据团队的代表,就和安全团队的同事们同在安全大数据项目组。在公司里面,机器学习的人员通常都是和开发人员通力合作,各司其职,共建一个项目。在项目初期,其实 Jett 也不负责与我对接,后续随着项目的进一步发展和迭代,Jett 就成为了安全中心与我对接的人。

虽然 Jett 是和我对接的人,但是 Jett 主要也是负责平台开发,之前 Jett 在进入公司之前好像没有做过前端,但是在项目初期好像做了一些前端方面的工作,在邮件里面得到了领导的赞扬。这个应该是我对 Jett 的第一印象了,那就是一个靠谱的开发人员。当时虽然是成立了项目组,但是还是作为一个试点的工作来做,无论是算法的调研和平台的工作,都由我们两个来完成。这些项目在初期都是一大堆人在里面,但是随着项目的进展,人数都会越来越少,然后领奖的时候又出现了一大堆人。在项目的初期,我当时应该也只会 SQL,连 Python 都不算很熟悉,更没有开发过大型项目了。即使是作为一个试点的项目,其实个人也有着巨大的压力,毕竟这个方向在公司当年还处于一个相对不那么清晰的状态,也不知道该怎么做,甚至也不知道有什么资料可以查。不过作为一个 PHD,虽然写代码的能力不行,但是读论文和搜索资料的能力还是有点的。当时记得花了很多时间在网上找来找去,总算找到一两家号称做这个方向的创业公司,运气够好的是当时它们居然都发表了相关的论文。后来把它们的论文整理成资料和PPT,跟相关的同事沟通了一下,就打算复现这几篇论文。

屏幕快照 2019-08-10 下午10.01.49

当然,做项目总是有着各种各样的风险,况且当年本人的技术实力确实也不怎么样,写过不少的 SQL,做过很多数据分析的工作,查过一些数据方面的问题,至于其他方面也就那么回事。在项目的调研阶段和初期,大约是5月份-8月份,其实也没有什么特别大的产出,主要也是在积攒技术经验,把 Python 的各个工具库熟悉了一下。不过在公司里面总是有考核的,到了9月份的时候压力就比较大了,毕竟最终还是要对上线的效果负责的。在9月底的时候,我和 Jett 被拉去星巴克喝了一杯咖啡,然后被下达了任务和命令,也就是在十月份完成机器学习的效果指标。

屏幕快照 2019-08-10 下午9.59.46

既然被拉到星巴克去喝咖啡,也就是说明在9月份的时候,模型的效果都不算太好,估计再这样干下去也没有办法完成既定的目标。不过目标这种事情制定的时候都是根据当时的情况来制定的,很有可能会随着时间的变化而产生变化。虽然说目标总是在发生变化,但是整体的大思路是没有改变的。当时,作为开发人员的 Jett 问我要不要修改 XGBoost 的模型源码,我连忙说不用不用,其实就算让我改,我也没有本事修改别人的源码。既然不会修改模型的源码,那就只能够从数据和特征来入手了。在机器学习领域,只要把数据和特征处理好了,基本上就能够保证模型的效果和质量。于是 Jett 和我当时把成千上万条数据一起看了一遍,结果是发现正负样本有一部分混在了一起,于是模型的效果无论如何都做不好。

屏幕快照 2019-08-10 下午10.05.45
XGBoost 的 Github 主页

对于在校学生而言,通常来说都是 Python 跑完模型,然后得到一个模型文件,用它继续离线预测就可以得到最终的结果。但是在工业界,很多机器学习项目都需要进行上线的工作。这种时候只靠一个机器学习人员的战斗力是无法解决问题的,不可避免地需要有开发人力的介入。此时 Jett 发挥了作为一位开发人员的强大战斗力,一个人就能把线上的代码全部完成,没有让我撰写任何一行 C++ 的代码。在码农界有一种“结伴编程”的说法,也就是两个人共同搞一份代码,共同搞一个项目。我是负责数据处理和离线模块,Jett 是负责平台开发。有一次在核对数据的时候,把 Python 的预测结果和 C++ 的预测结果进行核对。也就是为了交流方便,那次我把 Mac Air 搬到了 Jett 的桌子上,两个人并排坐在一起,一起核对数据的准确性和可靠性。

不过核对数据只是机器学习项目的第一步,并且也是长期需要做的一步,因为数据总是会出现各种各样的问题。即使数据没有问题,也不代表最终的模型效果达标。到了2016年10月中旬的时候,我俩的压力也已经很大,每天晚上都在万利达五楼加班到十点以后。每天我都在训练模型和数据分析,Jett 每天也在做平台开发的工作,虽然我不懂他在做什么,但是总是感觉很忙的样子。而且项目经理每两天都会催一次进度,顺带着会有各种大大小小的会议。其实当时 Jett 是作为业务部门的人,压力更大的是压在他那一边。在思考了大半个月之后,在一个星期日的夜晚,我去华润万家买了一堆小本子,把整个项目的细节仔仔细细地思考了一遍,突然灵光一现,发现其实有一个优化点,于是就顺手写在了小本子上。到了周一的时候,我把小本子上面的想法去实现了一遍,结果效果瞬间提升,业务指标瞬间完成。当我把这个好消息告诉 Jett 的时候,Jett 还在 RTX 上说了一句:“等我去哭一会”。最终我俩猛加班两天,把模型往线上一扔,效果直线上升,而此刻的报表系统早已齐备,瞬间就看到了效果的提升,甩掉前面的模型五条大马路。

6EC4948295154B525FD67EAC9B309320.jpg
当年撰写思路的小本子

在2017年初的时候,模型的整体效果已经很好了,整体的路线其实已经基本走通。因此后续更多的是平台建设方面的工作,这一块做得更多一点的是 Jett,最终他还真是完成了无算法人员参与就能够自动接入各种业务的全自动流程。不过随着时间的流逝,我俩都各自都被抽调去做其它的项目,合作的时间和机会在项目成功之后就变得越来越少了。万幸的是,在2017年9月5日-2017年9月9日,我俩共同去了台湾进行了一次团建。参见《五日台湾行》。

640

640-2
2017年的台湾

后来,由于种种原因,我也不再继续从事安全方面的工作,与 Jett 的交集也越来越少。虽然后面也有吃饭聚餐等时候,但是却没有了在一个项目中一起为了一个目标奋斗的机会,心中不免有少许遗憾。随着去年的大调整,Jett 和我已经不在同一个部门。今年 Jett 由于家庭原因离开了公司,恐怕短期内已经再也没有通力协作,互帮互助的机会了。也许这个项目是我俩共同做的最后一个项目,但是当年在万利达五楼共同奋斗的时光,却是一段珍贵的回忆。

高考志愿—谈一谈数学专业

最近,经常在知乎或者其他平台上看到

  • “高考填写志愿要不要填写数学专业?”
  • “读计算机专业是不是需要先去数学系?”
  • “从数学系转行到金融行业的前景怎么样?”

这一类的问题。最近也正值高考填志愿的时期,于是在这里说一下自己的一些想法。

math1.png

其实这个问题很难给出一个标准的答案,因为每个人的个人条件,家庭条件,就业规划都完全不一样。推荐的结果应该正如推荐系统一样,根据每个人的情况来定制化,而不是给出一个结果供所有人参考。

一般情况下,每个人都有自己的发展方向或者职业规划,基本上进入数学系有这几个常见的原因:

  • 想做数学科研,成为数学工作者;
  • 为了转行做准备,准备研究生阶段进入金融或者计算机;
  • 实在不知道想学啥,于是选择数学试试看。
  • 其他原因。

Case 1:

第一种情况,想成为数学工作者的应届生其实只能选择数学系。目前的现代数学高度专业化,已经不是一个外行人,跨专业的人或者普通职业的人能够研究的了。本科所传授的数学知识大约也就是在20世纪中期而已,后面几十年的科研工作就很难写进本科教材了。因此,对于有志向成为数学家的学生而言,进入数学系是唯一的选择。当然其实也有大神从别的专业转过来从事数学工作的,并且也能够做得很好,但是对于绝大多数人而言是不现实的。

对于这一批少数的学生而言,最好的方式就是按照数学系的标准培养模式来做。也就是听课,刷题,复习,钻研,考试这条路,每天花十个小时学习,高强度的学习几年的本科数学。然后想办法进入顶尖高校的数学系,继续从事数学科研几年时间。最后进入顶尖高校的数学系或者科研站,从事数学研究。

GTM52.png

Case 2:

第二种情况,经常都会遇到一个问题,那就是“是否有必要先读数学,然后在研究生阶段转行计算机或者金融?”先说结论:个人感觉是完全没有必要的。理由有以下几点:

  1. 金融或者计算机同样会开设各种各样的数学课,并且是结合专业的情况来开设相关课程;
  2. 数学系并不会专门提供金融或者计算机的课程;
  3. 数学系的思维方式和培养模式与金融或者计算机不太一样。

question.png

在这里,如果是为了打基础而先进入数学系再转行去其他专业其实是没有必要的。因为其他专业同样可以提供数学课,完全可以在其他专业学好数学课,没有必要专门跑来数学系学习四年数学。当然,由于高考填写志愿,或者为了进入一个更好的大学,只能够选择数学系而放弃其他专业其实是可以理解的。但是,在本科期间一定要补充其他专业技能,否则最后还是会比较吃亏。

除此之外,数学系很少会去开设金融或者计算机方面的课程,大部分开设的还是数学课,当然也不排除有的数学系会开设一大堆计算机系课程的情况。那么就来看一下数学系与计算机系的课程安排:

数学系的课程:

数学分析,高等代数,解析几何,C++,离散数学,常微分方程,偏微分方程,抽象代数,复变函数,实变函数,泛函分析,数值计算,偏微分方程数值解,拓扑学,微分几何,概率论与数理统计,随机过程等。

计算机系的课程:

微积分,线性代数,离散数学,数据结构与算法,数字电路,计算机组成原理,操作系统,编译原理,计算机网络,数据库原理,软件工程,汇编语言等。

从这两个课表的对比情况来看,如果要想从数学系转行到计算机系,那么基本上要把计算机的一些基础知识课程都大致过一遍才行,否则企业为什么不直接招聘一个计算机系的,而需要一个跨专业的人呢?在这种情况下,对数学系的人其实提出了很高的挑战,因为在数学系繁重的课程下,想要同时兼顾数学系和计算机系两个专业的课程是比较困难的,需要耗费巨大的时间和精力才能够做好。

balance

在这种情况下,如果是计划研究生期间转行,就需要额外花很多的功夫了。毕竟金融或者计算机其实是有一定的课程量的,不仅要保证数学系课程的学习,还要去学好金融或者计算机其实是有一定的挑战的。但是,为了最终要转行到其他领域这也是一条必经之路。因为只有补平了自己与科班人员的差距,才能够在其他领域发挥自己的数学能力。例如在计算机领域,只有编码能力过关了,才能够逐步展示数学能力。如果基础能力不太够的话,就只能够先做补基础的工作了。

experiments

数学系与其他专业的培养模式其实不太一样。在数学系,强调的一般都是听课,刷题,复习,钻研,考试等一系列流程。在这种情况下,对于想成为数学工作者的学生是比较友好的。但是对于大多数需要转行的学生而言就不算友好了。因为其他专业更多强调实践,无论是金融还是计算机都会把实践放在第一位。在金融领域,实习或者社交其实是一个比较关键的因素,但是在数学系,这些能力是无法得到锻炼的。在计算机领域,通常接触到的都是业界相对新的东西,需要在实践中一边查资料一边干活才能够逐步掌握知识点。在数学系,也会有机会进行实践,但是时间往往比其他专业会延后许多。在数学本科或者硕士阶段,其实绝大多数人是没有能力搞数学科研的,最后的毕业论文无非也就是整理一下资料和笔记而已。直到博士阶段,数学系的学生才需要进行资料的收集,论文的阅读,从而进行数学科研的工作。整体来看,数学系从事实践的时间往往会比其他专业延后许多,如果是以就业为目的来攻读数学专业其实是不合适的。

Case 3:

第三种情况,实在是不知道想学啥,如果自身条件还不错,家庭条件也还算可以的话,其实学数学专业也是一种选择。因为在数学系期间,最终的选择面还是比较广的,主要包括:

  • 科研工作者:数学方向,金融经济方向,计算机方向等;
  • 计算机行业;
  • 金融行业;
  • 教育培训行业;
  • 其他行业。

选择面广有的时候是一件好事,有的时候不见得是一件好事。选择面太广就容易让人迷茫,尤其是对于那些目标不明确的人而言。导致的结果就是这批学生什么都去了解,什么都去学习,什么都是浅尝辄止,最终其实并没有掌握任何东西。最怕的事情就是,在数学系的时候并没有把数学弄懂,然后在其他领域又没有办法和科班竞争,从而最终荒废了自己。因此,如果实在是不清楚学什么的话,来数学系是可以的,但是肯定需要把数学弄明白。最终,突然有一天这批学生想转行或者做其他的事情,数学能力能够给人带来很大的帮助。

choice

如果萌发了转行的想法,那么最好就是找相关的人士咨询一下其他行业,或者去招聘网站上看相关的岗位需要什么样的技能,能否通过自学或者听课或者其他方式找到一份实习。然后根据自己的最终目标来反推自己当前的决定,也就是要达到这样的目标需要多少时间,多少精力才能够达成。就个人经验来看,转行是需要花大量的时间和精力的,并且越到后面(研究生或者博士阶段),转行的困难就会越来越大。因此,如果要转行的话,其实可以趁早做决定,越早决定就越有优势。

另外需要注意的一点就是,在转行期间不需要在乎数学系那一套评价指标,因为按照数学系的评价指标,不学习不科研就是不误正业了。但是对于转行的人而言,实战才是硬道理,实习才能够了解工业界的具体需求。在学校里面猛刷题或者猛看书其实只是其中的一个步骤而已,是达不到转行的要求的。

结论:

每个人都有自己的局限性,只能够根据自己的成长经历给出判断的标准和依据,并不适用于所有的人,只能建议大家根据自身的情况来选择一套适合自己的方案。毕竟人生只有一次,路也是自己走出来的。

challenge

 

时间序列的联动分析

背景介绍

在互联网公司里面,通常都会监控成千上万的时间序列,用于保障整个系统或者平台的稳定性。在这种情况下,如果能够对多条时间序列之间判断其是否相关,则对于监控而言是非常有效的。基于以上的实际情况,清华大学与 Alibaba 集团在2019年一起合作了论文《CoFlux: Robustly Correlating KPIs by Fluctuations for Service Troubleshooting》,并且发表在 IWQos 2019 上。CoFlux 这个方法可以对多条时间序列来做分析,并且主要用途包括以下几点:

  1. 告警压缩和收敛;
  2. 推荐与已知告警相关的 Top N 的告警;
  3. 在已有的业务范围内(例如数据库的实例)构建异常波动传播链;

kpis.png

CoFlux 的整体介绍

从论文的介绍中来看,CoFlux 的输入和输出分别是:

输入:两条时间序列

输出:这两条时间序列的以下信息

  1. 波动相关性:两条时间序列是否存在波动相关性?
  2. 前后顺序:如果两条时间序列相关,那么它们的前后波动顺序是什么?是同时发生异常还是存在固定的前后顺序?
  3. 方向性:如果两条时间序列是波动相关的,那么它们的波动方向是什么?是一致还是相反?

Remark. CoFlux 的关键点就是并没有对时间序列做异常检测算法,而是直接从时间序列的历史数据(历史半个月或者一个月)出发,判断两条时间序列之间的波动相关性,并且进一步的分析先后顺序与波动方向。

从论文的介绍中来看,CoFlux 的流程图如下图所示:

coflux流程图1

如果两条时间序列 XY 存在波动相关性,则需要输出这两条时间序列的波动先后顺序和是否同向波动。如果两条时间序列 XY 并不存在波动相关性的话,则不需要判断波动先后顺序和是否同向波动。

coflux流程图2

CoFlux 的细节阐述

已知一个长度是 n 的时间序列 S=\{s_{1},\cdots,s_{n}\},对于任意一个 detector,可以得到一条关于 S 的预测值曲线 P=\{p_{1},\cdots,p_{n}\}。于是针对某个 detector 可以得到一个波动特征序列 E=\{\epsilon_{1},\cdots,\epsilon_{n}\},其中 \epsilon_{i} = s_{i} - p_{i}1\leq i\leq n。因此,一个detector 可以对应一个波动序列特征,也是一个时间序列。因此,对于 m 个 detector,可以对应 m 条波动特征序列,并且它们的长度都是 n

在 CoFlux 算法的内部,根据不同的参数使用了总共 86 个 detector,大致列举如下:

  • Difference:根据昨天,七天前的数据来做差分;
  • Holt-Winters:\{\alpha,\beta,\gamma\} \in \{0.2,0.4,0.6,0.8\}
  • 历史上的均值 & 历史上的中位数:1,2,3,4 周;
  • TSD & TSD 中位数:1,2,3,4 周;
  • Wavelet:1,3,5,7 天;
  • 移动平均算法:MA,WMA,EWMA。PS:根据作者们的说法,在这里,MA等方法并不适用。

detectors

根据直觉来看,

  • 对于任何一条时间序列 kpi,总有一个 detector 可以相对准确地提炼到其波动特征;
  • 如果两条时间序列 XY 波动相关,那么 X 的一个波动特征序列与 Y 的一个波动特征序列应该也是相关的;

Remark. 两条时间序列的波动特征可以对齐同一个 detector,也可以不做对齐工作。如果是前者的话,时间复杂度低;后者的话,时间复杂度高。

下图是从时间序列中提取波动特征曲线的案例:

fluxfeatures.png

提炼时间序列的波动曲线特征只是第一步,后续 CoFlux 还有几个关键的步骤:

  • 特征工程的扩大(amplify): 对波动序列特征进行放大,让某些波动序列特征更加明显;
  • Correlation Measurement:用于解决时间序列存在时间前后的漂移,两条时间序列之间存在 lag 的情况,因此需要对其中一条时间序列做平移操作;
  • CoFlux 考虑了历史数据(历史半个月或者一个月)作为参考,并且一个范围内的 kpi 数量不超过 60 条;

下面来一一讲解这些技术方案,对于每一条波动特征曲线(Flux-Features),按照以下几个步骤来进行操作:

Step 1:对波动特征曲线 E=\{\epsilon_{1},\cdots,\epsilon_{n}\} 做 z-score 的归一化,i.e.

\mu = \frac{\sum_{i=1}^{n}\epsilon_{i}}{n},
\delta = \sqrt{\frac{\sum_{i=1}^{n}(\epsilon_{i}-\mu)^{2}}{n}}.

Step 2:对归一化之后的波动特征曲线做特征放大(feature amplification):定义函数 f_{\alpha,\beta}(x) 如下:

f_{\alpha,\beta}(x)= \begin{cases} e^{\alpha\min(x,\beta)} - 1, \text{ when } x\geq 0,\\ -e^{\alpha\min(|x|,\beta)} + 1, \text{ when } x< 0. \end{cases}

E=\{\epsilon_{1},\cdots,\epsilon_{n}\} 放大之后的波动特征曲线(amplified flux feature)就是:\hat{E}=\{f(\epsilon_{1}),\cdots,f(\epsilon_{n})\}.

Step 3:对于两条放大之后的波动特征曲线(amplified flux features)G=\{g_{1},\cdots,g_{\ell}\}H=\{h_{1},\cdots,h_{\ell}\},可以计算它们之间的相关性,先后顺序,是否同向。

G_{s}= \begin{cases} \{0,\cdots,0,g_{1},\cdots, g_{\ell-s}\}, \text{ when } s\geq 0, \\ \{g_{1-s},\cdots,g_{\ell},0,\cdots,0\}, \text{ when } s< 0. \end{cases}

这里的 0 的个数是 |s| 个。其中,-\ell<s<\ell。特别地,当 s=0 时,G_{0}=\{g_{1},\cdots,g_{s}\}=G,那么我们可以定义 G_{s}H 的内积是:R(G_{s},H) = G_{s}\cdot H,

这里的 \cdot 指的是向量之间的内积(inner product)。同时可以定义相关性(Cross Correlation)为:CC(G_{s},H) = \frac{R(G_{s},H)}{\sqrt{R(G_{s},G_{s})\cdot R(H,H)}}.

由于波动有可能是反向的,那么在这里我们不仅要考虑相关性是大于零的情况,也需要考虑小于零的情况。于是,

minCC = \min_{-\ell<s<\ell}CC(G_{s},H),
maxCC = \max_{-\ell<s<\ell}CC(G_{s},H).

则最小值或者最大值的指标分别是

s_{1}=argmin_{-\ell<s<\ell}CC(G_{s},H),
s_{2}=argmax_{-\ell<s<\ell}CC(G_{s},H).


FCC(G,H) = \begin{cases} (minCC, s_{1}), \text{ when } |maxCC|<|minCC|, \\ (maxCC, s_{2}), \text{ when } |maxCC|\geq|minCC|. \end{cases}

从定义中可以看出,FCC(G,H) 是一个元组,里面蕴含着三个信息,分别是相关性,波动方向,前后顺序。FCC(G,H) \in [-1,1],越接近 1 或者 -1 就表示放大之后的波动特征曲线 GH 越相关。正值的 FCC(G,H) 表示 GH 的波动方向相同,是正相关;负值的 FCC(G,H) 表示 GH 的波动方向想法,是负相关。通过对 s<0 或者 s\geq 0 的分析就可以判断先后顺序。因此,CoFlux 方法的是通过对 FCC(G,H) 的分析来得到最终结果的。

在最后的相关性分析里面,其实伪代码正如论文中所示。先考虑是否存在相关性,再考虑基于相关性下的先后顺序和波动方向。

correlationmeasurement

 

CoFlux 的实战效果

从论文中看,CoFlux 的数据集基本上是小于 60 条时间序列曲线。其中包括 CPU,错误率,错误数,内存使用率,成功率等不同的指标。

datasets

datasets2.png

从运行时间上来看,对于一周的时间序列集合(< 60条)而言,CoFlux 基本上能够在 30 分钟内计算完毕,得到最终的运算结果。

executiontime.png

其效果的评价指标基本上就是机器学习中的常见评价指标了,准确率,召回率之类的。

评价指标

从 F1-Score 的评价指标来看,CoFlux 的效果优于其他算法。

experiments.png

告警压缩

如果对时间序列之间进行告警压缩的话,其实可以大量减少运维人员的工作量。在 CoFlux 里面,时间序列曲线被分成了三类,也就是三个颜色最深的模块。因此 21 条时间序列的告警量在实际中有可能只有三条告警。

alarmclustering

告警关联

在实际运维场景中,除了对告警进行压缩之外,也需要对告警进行关联性的分析。例如一条告警发生了,运维人员都希望知道与它相关的其他告警是什么,这样可以方便运维人员定位问题。

alarmcorrelation

构建告警关系链

在一些相对封闭的场景下,例如 mysql 数据库,通过对它里面的时间序列进行分析。不仅可以得到告警之间是否存在相关性,还可以对先后顺序,波动顺序进行分析。

mysql

 

结论

时间序列之间的联动分析是在运维领域场景下的常见技术,不仅可以做告警的压缩,也能够做告警的关联,还能够构建告警的关系链。在未来的工作中,作者们提到将会用深度学习的方法来进行关联和告警的分析,从而进一步加深对时间序列的研究。

本科学数学专业是一个很好的选择吗?

知乎问题:https://www.zhihu.com/question/319574112

选专业这件事情其实是因人而异的,很难对所有的人给出一个标准的答案,肯定是基于每个人的不同条件来给出完全不同的建议。这是一个千人千面的问题,而不是一个数学题,通常只有一个标准的解答。

就个人这几年的经验来看,无论选择什么专业,都会有这个专业的优势和劣势,好比科技是一把双刃剑,专业也是同样的道理。在这种情况下,我们就需要分析数学专业究竟有哪些优势,有哪些劣势。只有这样,我们才能够根据自身的情况来具体分析,然后决定最终是否选择数学专业。

数学专业的劣势

于是,我们来看一下数学专业的劣势有哪些:

  • 理论知识太多;
  • 实用技能偏少;
  • 转行需要时间。

下面来逐一解读以上几点。我们可以先看一下数学系的常见课表:

  • 第一年:数学分析,高等代数,解析几何,C++等;
  • 第二年:常微分方程,离散数学,复分析,概率论,数值计算,抽象代数等;
  • 第三年:实分析,泛函分析,偏微分方程,拓扑学,微分几何,偏微分方程数值解,随机过程,数理统计等。

从课表上面来看,基本上可以确定几个结论。首先,数学专业作为基础学科,其特点就是理论知识偏多,而学习到的技能偏少,毕竟所学的内容都是理论型,培养的学生都是理论型选手。因此直接导致的结果就是数学系的学生掌握了一堆理论,但是却没有办法把它们直接转化成生产力。在实战中,总不能就靠一门 C++ 来谋求工作吧。其次,既然数学系传授给学生的实用的技能偏少,那么数学系的学生在需要转行的话,就肯定要补充新的技能。在从理论派走向实战派的过程中,不仅要找好自己的前进方向,还需要花费一定的时间和精力去转行。在这里需要澄清一点,转行并不是轻轻松松,而是需要花费时间,勇气和精力的。

如果不想继续从事数学科研的话,其实还是建议数学系的学生可以早一点进入公司去实习或者工作,至少在公司能够体验一下与学术界完全不同的人生。人生总是有多种可能性的,其实可以在本科或者硕士阶段多去体验一下人生。与数学系不同的是,对于计算机或者工程类专业的学生而言,到了本科一定的阶段,都会从事某个项目或者大作业,这种时候他们就会在边看边学中得到一定的成长,实践能力的训练其实比数学系的人会早很多。其实数学系也有实践,只不过延后了许多,一般只有到了博士生的阶段才需要进行科研的训练和动手的操作,在本科和硕士阶段一般是不需要的,因为现代数学的发展已经不是大部分硕士生能够完成的了,当然优秀的人总是有的。

数学专业的优势

在讲了数学专业的劣势之后,也需要强调一下数学专业的优势,其优势包括:

  • 底层通用技能;
  • 技能不易淘汰;
  • 逻辑思维能力;
  • 转行就业面广。

众所周知,无论是在学术界,还是工业界,数学基本上就是一切的基础。如果计算机行业没有数学,那就是XX计算机学院与XX培训班的区别;如果金融行业没有数学,那就是文艺复兴公司与XX小银行的区别。虽然我们不能够一味的拔高数学在各个行业的作用,但是很多行业还是离不开数学的。这就是所谓的底层通用技能,无论是计算机,金融还是其他领域,都离不开数学的支持。

除此之外,再次回到那张数学系的常见课表:

  • 第一年:数学分析,高等代数,解析几何,C++等;
  • 第二年:常微分方程,离散数学,复分析,概率论,数值计算,抽象代数等;
  • 第三年:实分析,泛函分析,偏微分方程,拓扑学,微分几何,偏微分方程数值解,随机过程,数理统计等。

当年读本科的时候是这张课表,其实过了十年,也是这张课表。本科的数学课程基本上集中在20世纪初之前的数学内容,最多到了20世纪中期。而微积分的发展时间则更加久远了。对于数学系的教育而言,很难做到跳过数学分析,高等代数的教育直接进入实分析和泛函分析。就算老师能够教,学生也听不懂啊,还是只能够从基础一步一步开始。而工业界用到的数学,通常也就是数学本科三年级的所有课程就能够包括了。很难用到很多研究生方面的知识,甚至很多时候也就用用微积分和线性代数,概率论就足够了。因此,一旦学会了这些课程,则是终身受益的知识,因为数学的另外一个特点就是永恒性。无论个人发生什么,学校发生什么,世界发生了什么,数学定理就是数学定理,一旦被证明且确定了证明是正确的,那就是永恒的。个人会死亡,学校也有可能走向没落,世界也有可能发生变化,但是数学定理就像一个永恒的石头永远放在那里。

除了以上两点,数学是最能够培养学生逻辑思维的学科。在以上的本科生课程里面,几乎所有东西都是从几个公理出发,然后通过严格的证明,一点一点地得到最终的结论,并且构建出整个数学大厦。在本科教育里面,数学系的学生只要认真学习,通常来说,逻辑思维能力和数学推导能力都会得到一个很大的提升。并且在后续的学习或者工作中,数学的烙印都会深深地印在身上。

最后,数学的就业面其实是相对宽广很多,主要包括:

  • 科研工作者:数学界,金融界,经济界,计算机方向等;
  • 计算机行业;
  • 金融行业;
  • 教育培训行业;
  • 其他行业。

除了可以继续从事本专业之外,其他方向无论是金融还是计算机都可以转。

结论: 整体来看,其实如果自身条件 OK 的话,并且也愿意在本科期间选择数学专业的话。其实选择数学专业是一个不错的选择。在数学系本科这几年可以根据自身的情况来继续选择合适自己的发展方向,并且在研究生或者工作的时候选择一个适合自己的舞台。

机器学习算法工程师的日常

目前笔者已经在互联网行业从事机器学习方向三年有余,经常也被问到做机器学习算法工程师是一个什么样的体验,同时也常常在其他平台上看到其他人问类似的问题。于是提笔写下此文,供有志投身于这个行业的人参考。

日常生活

数学博士的时候,通常的日子是这样的:

根据论文或者某个讲座得到的信息来提出某个数学猜想 -> 然后开始在 Google 上搜索论文 -> 再花费几周到几个月的时间来读论文,并且思考这些论文的优点和缺点 -> 思考 -> 思考 -> 思考 -> 继续读更多的论文 -> 思考 -> 思考 -> 思考 ->…-> 放弃。。。。

在互联网公司做机器学习的时候,通常的日子是这样的:

根据行业的PPT或者业务中的某些痛点来提出技术方案 -> 然后开始收集数据,不仅要问遍组内,还要去其他组收集各种各样的需求 -> 根据之前的技术方案来进行数据的预处理 -> 撰写特征工程 -> 训练模型 -> 调参 -> 调参 -> 重新收集数据 -> 数据的预处理 -> 收集更多数据 -> 调参 -> 调参 -> 调参 ->…->放弃。。。。

1

业务理解

就做机器学习的经验来看,通常来说在做业务之前,一定要清楚的弄明白项目的业务需求是什么,弄清楚这个问题是什么比一开始就写代码重要得多。意思就是在回答问题之前,一定要把问题的内容弄清楚。有的时候,虽然看上去是一个很大的需求,但是实际操作起来的时候使用一些简单的办法也能够达到项目指标。有的时候,虽然看上去很简单,但是实际操作起来并不是一件容易的事情。从之前做理论数学的经验来看,通常数学里面的一些问题是是非题,不能够添加条件的。在 PDE 等方程领域,定理的条件越多,表示定理越不值钱。不过在工作中,这些条条框框会相对减少很多,只要能够达成项目目标,无论是添加样本,添加特征,添加服务器数量其实都是可以的,并且要把机器学习模型业务指标有机结合才能够达到最终的项目指标。

2

一般搞数学科研的时候都是单打独斗,通常来说都是自己干自己的事情,别人也没办法帮自己。但是在工作中是不一样的,工作中除了干好自己的事情之外,周边的很多资源其实是可以在一个合理的范围内去争取的。无论是人员的数量,还是人员的种类,只要最终能够达成项目目标即可。无论是算法人员,还是开发人员,产品经理,最终都是要为一个项目的结果负责的。之前听过一句经典的话“失败的项目里没有成功的个人”,因此,无论怎么做,最终都要保证项目尽量成功。

3

数据清洗和特征工程

而在机器学习算法工程师的日常生活中,除了上面的小段子之外,其实最重要的是样本层和特征层的处理工作。在学术界,都是使用开源的数据,别人都已经完全标记好了,学术圈的人通常来说只需要在这些数据的基础上提出更好的模型,更创新的算法即可。但是在工业界就完全不一样了,不要说有人帮你标记数据了,有的时候连数据在哪里都不知道,数据的质量如何也不知道,因此更多的时候是进行数据的处理和清洗工作。之前做一个项目的时候,准确率和召回率始终上不去,但是等把样本里面的脏数据清理掉之后,模型的效果瞬间提升了一个档次。在脏数据面前,再好的模型都是没有用的,在训练模型之前,一定要先看一下数据层的问题。

4

除了数据的问题,通常来说在一些场景下,样本的数量并没有那么大,因此深度学习等方案不一定特别适合。在这种情况下,一般就会使用传统的机器学习方法,并且会使用一些基于业务的特征工程。这种时候就需要机器学习从业者对业务有一个精准的理解,只要业务理解得好,有的时候写一些简单的规则就可以解决问题。特征工程也是机器学习里面的一个重要问题。

持续学习

在人工智能这个领域,无论是 CV,NLP,还是机器学习,里面的技术迭代都是非常快的,而且是需要相对专业的人才能够从事这些领域。在这种情况下,机器学习从业者的持续学习就显得尤其重要,几年前的技术在新的业务场景下就未必适合,可能需要使用其他的模型或者框架才能够更好地解决问题。所以,除了完成日常的搬砖工作之外,建议每天抽一点时间来阅读论文,保持对业界技术的跟进和迭代。不过这个行业鱼龙混杂,有的时候论文或者 PPT 里面的技术框架其实没有办法复现,能够精准地判断哪些方案好,哪些方案差绝对是算法工程师必备的关键能力之一。

5

编程能力

如果是在工业界的话,编程能力是非常重要的。因为从事算法的人通常来说会有一些算法上的优化,工程上的改进,数据分析之类的工作。在这种情况下,首先需要有一定的业务直觉。而业务的经验积累需要通过各种各样的基础数据提取,在海量的数据分析工作中逐渐积累的。在这种情况下,提取数据的工具就是必须要掌握的,例如 SQL 等。其次,分析数据的工作也是必须要具备的,无论是使用 SQL 来进行分析,还是使用 Python 来做数据分析,都是自行编程解决的。再次,在从事机器学习方向的时候,不可避免的就会进行算法的效果对比。而在这种情况下,算法的效果对比是需要机器学习从业者通过写程序来实现的。最后,工业界的算法通常来说都强调上线,如果能够自行把离线,上线,效果验证,ABTest都做完,其实是最好的状况。在这种情况下,通常 Python 就不太够了,需要使用 C++ 或者 Java 等其他编程语言。因此,熟练使用多种编程语言也是一个算法工程师的能力。

6

常用工具

在互联网公司里面笔者用过的机器学习工具大概有这几个:

  1. XGBoost:做分类的工具,提供离线的Python训练和在线的C++调用功能,方便机器学习从业者训练模型和线上部署;不仅在推荐场景可以用,在安全,运维等领域都有着用武之地。
  2. Tensorflow:这个也不用多说了,深度学习的经典工具之一,离线训练和在线服务都是不错的。
  3. ScikitLearn:单机版本的机器学习工具。方便学生在校学习知识,文档详细感人,关键是还开源。其实在工业界,如果数据量不大的话,其实用 ScikitLearn 就基本上够用了。
  4. Pandas:表格类数据或者时间序列数据的经典工具。尤其是在时间序列的处理上面有特别独到的优势,应该还有其他功能,但是笔者暂时了解不多。Pandas 的接口和函数特别多,每次遇到问题的时候可以搜一下,其实比自己重头写好得多。
  5. Spark:在大数据的情况下用得比较多,通常是推荐系统一类的,海量样本的前提下,单机版的模型根本搞不定,因此会用分布式的工具。
  6. SQL:提数工具。如果不掌握这个的话,基本上什么都做不了。。。。。
  7. FbProphet:稍微小众一些,Facebook 的开源工具之一,在时间序列预测的场景下才能用到。

7

工作感受

给自己压力。一般来说,转专业求职是一个艰苦的过程,但是入职之后的生活则更加辛苦。因为公司的考核是每半年甚至两个月就一次,所以,在这种情况下,任何人都需要有一个上手的速度。有的人因为在学校学过相关的内容,或者之前实习过,因此上手的时候比较快;但是有的人转专业就面临上手慢的情况。其实这些对于应届生来说都可以理解,毕竟所有的人都需要有一个适应的过程。在这种情况下,在工作的初期一定要给自己一定的压力。意思就是说:在刚工作的第一年,每三个月就要让自己有一个飞速的提升;在工作的第二年,每半年就要让自己有一个提升;后续的话,每一年都要让自己有提升才是关键。因此,无论是本专业还是转专业的同学,都建议在前两年工作的时候,多给自己一些压力,只有这样,才能够让自己有更好的进步空间。

对业务的理解。公司里面有很多东西并不是直接使用开源代码就能够发挥作用的,在公司里面无论做什么事情,最重要的一点就是对业务的理解。在对业务的理解方面,老员工相对于新人来说确实有着不少的优势。其次,在做业务的过程中,通常都会经历很多的坑,无论是别人主动挖的,还是自己踩坑踩出来的,都是自身宝贵的财富和经验。而这些经验只能够通过靠做大量的业务来获得。如果要想长期保持自身的优势,通过长期的训练和学习确实是一个有效的办法。无论是天才还是普通人,要想提升自身的技术,不花一定的时间去学习是不可行的。因此,无论在任何时候都不能够放弃让自己学习和充电的机会。

勇于接受新的挑战。公司里面除了已有的项目之外,通常来说都会开启各种各样的新项目,在这种情况下,如果有机会做新的项目,也就是别人没有做过的项目。这种机会已经要把握住,因为对于新人来说,能够接触全新的项目肯定是好过维护已有的项目的。但是几乎所有的人都是从维护旧的项目开始的,只有旧的项目做好了,才有机会拿到新的项目。

不要永远抱着已有的方向不放手。在公司里面,业务方向总会或多或少的发生变化,随着部门的调整,方向的变化,所做的内容总会发生一些变化。在工作的时候,最好不要抱着我就是来做这个方向的,除了这个方向之外其他的内容我一概不想做。因为当时的工作岗位未必能够提供你想做的方向,但是说不定能够提供其他的研究方向。有的时候,在公司里面,根据方向的变化来调整自己的工作内容也是一个必要的技能。而且,在公司的时候,一定要多做一些有挑战的项目,只有通过这些项目,才能够让自己的技术壁垒更加深厚。当然,在求职的时候,每个人都有着自己的想法和选择,所以,在求职的时候,是可以选择一个自己喜欢的方向来做的。

8

经验总结

通常来说,在干了两三年算法工程师之后:(以下是从其他地方看到的小段子,出处忘记了~~~)

  1. 能够熟练写各种脚本;
  2. 80%的时间在写脚本;
  3. 能够说出几种机器学习算法的名字;
  4. 轻松完成各种脏活累活(叫小弟做);
  5. 对无法解释的结果已经习以为常,能够强行解释一波,让领导信服;
  6. 调参前,都会去寺庙烧柱香;
  7. 桌上堆着很多崭新的技术书籍,没怎么翻过,大概都会有一本叫做《统计学习方法》的书。

9

 

2019年的博客

个人使用时间最长的博客平台就是 WordPress,从 2011 年开始算起,大约有 8 年时间了。

当年笔者还在南京大学本科读数学专业的时候,就见到大神 Terence Tao 建立了个人的网站:What’s new(terrytao.wordpress.com),并且后续数十年如一日的更新个人 Blog。在他的 Blog 上面,除了常见的数学基础知识和课程安排之外,更多的是当前数学界的一些新发展和新方向。由于数学系的博文或者论文除了文字之外,更多的是各种各样的数学公式,而这些数学公式使用公式编辑器一类的东西来处理是极其繁琐的,只能够使用 LaTex 等工具来写。恰好的是,WordPress 除了能够支持日常的文本编辑之外,还能够使用 LaTex 来对数学公式进行撰写,也就是说用户只需要在编辑框内写 LaTex,就能够编译成数学公式。因此,WordPress 对数学公式的支持是相对友好的,这对数学系爱好写数学博客的学生,工作人士提供了非常便利的条件。

除了整理数学公式比较容易之外,WordPress 上面还可以相对方便的选择各种各样的主题,这样的话刚注册的新用户也可以较为容易的上路,不用一开始就陷入编辑网站等一些繁琐的事情上面。同时,WordPress 上也有各种各样的小工具,包括日历(可以查看发表 Blog 的时间),文章的目录,比较受欢迎的文章或页面,文章的类别等内容。用户可以根据自己的爱好自行选择栏目,从而可以轻易地搭建出一个个人网站。另外,WordPress 可以统计出 Blog 的点击数量,包括每天,每周,每月,每年的具体点击数量。

第一次使用 WordPress(zr9558.com)正好是攻读博士学位一年,除了日常的科研工作之外,也打算写点东西来记录一下自己的成长。后续读博士期间也逐渐的写了一些数学方面的文章,不过后续回想起来其实应该在读本科的时候就开始写 Blog。如果这样的话,当年所学过的各种数学知识,整理过的各种资料都会更加清晰一些,也更加容易保存一些。毕竟写 Blog 的一个重要目的是给自己回顾用的,看看这段时间自己的积累是什么,自己学到了什么知识,相比去年成长了多少。其实,有的时候偶尔去浏览一下 Terence Tao 的博客,虽然也看不懂,但是可以明显地感受到“大神”的努力程度。牛人尚且如此努力,我等凡人有什么理由不努力呢。

当年在 NUS 读博士的时候也承担了一些教学的工作,并且也会给学生们讲解习题课。但是每年讲课的内容其实都差不多,于是在讲解习题课的时候,尤其是大学数学(MA1505),曾经做过一份 Tutorials,也就是把习题课的内容写在 WordPress 上面。不仅可以在课堂上方便地给学生们讲解,也可以让学生在课后方便的复习。时过境迁,当年听课的学生(还是大一)早已本科毕业,后面可能也会有学生看到这份资料,希望对大家有所帮助吧。链接在这里:MA 1505 Mathematics ITutorials

后面进入公司之后,有的时候工作繁忙,整理 Blog 的时间就会减少许多。但是一份工作除了能够给人带来必要的薪资之外,更重要的是给自己不停地积攒经验。无论是现在还是将来都可以让自己在职场中更加值钱。因此,除了日常的搬砖工作之外,也要时刻注意自己的成长和经验的积累。而搬砖的经验会随着项目的结束和时间的迁移在记忆中逐渐淡忘而去,于是,适当的记录就成为了必要的工作。俗话说得好,“好记性不如烂笔头”。因此,隔一段时间(通常来说可以设定为一到两个月的时长)就整理一下经验就显得尤为重要,也是提升个人技术和经验的方法之一。但是在整理 Blog 的时候,一定要注意 Blog 的质量,只有不断地提炼自己 Blog 里面的内容才能够保证文章的质量。

不过现在的 Blog 远没有当年受欢迎,在各种各样 APP 横行的时代,已经比较少有人主动去看别人的 Blog 了。不过在使用搜索引擎来搜索某些关键字的时候,有的时候还是能够看到一些高质量的 Blog。在学习这些 Blog 的同时,其实也可以互相比较一下,取长补短才能够使自己的博客越做越好。其实,无论有没有人读自己所写的内容,都要坚持写下去,因为:

即使最后没有人为你鼓掌,也要优雅地谢幕,感谢自己的认真付出。

计算机视觉中的注意力机制

引言

在机器翻译(Machine Translation)或者自然语言处理(Natural Language Processing)领域,以前都是使用数理统计的方法来进行分析和处理。近些年来,随着 AlphaGo 的兴起,除了在游戏AI领域,深度学习在计算机视觉领域,机器翻译和自然语言处理领域也有着巨大的用武之地。在 2016 年,随着深度学习的进一步发展,seq2seq 的训练模式和翻译模式已经开始进入人们的视野。除此之外,在端到端的训练方法中,除了需要海量的业务数据之外,在网络结构中加入一些重要的模块也是非常必要的。在此情形下,基于循环神经网咯(Recurrent Neural Network)的注意力机制(Attention Mechanism)进入了人们的视野。除了之前提到的机器翻译和自然语言处理领域之外,计算机视觉中的注意力机制也是十分有趣的,本文将会简要介绍一下计算机视觉领域中的注意力方法。在此事先声明一下,笔者并不是从事这几个领域的,可能在撰写文章的过程中会有些理解不到位的地方,请各位读者指出其中的不足。

LSTM_1

注意力机制

顾名思义,注意力机制是本质上是为了模仿人类观察物品的方式。通常来说,人们在看一张图片的时候,除了从整体把握一幅图片之外,也会更加关注图片的某个局部信息,例如局部桌子的位置,商品的种类等等。在翻译领域,每次人们翻译一段话的时候,通常都是从句子入手,但是在阅读整个句子的时候,肯定就需要关注词语本身的信息,以及词语前后关系的信息和上下文的信息。在自然语言处理方向,如果要进行情感分类的话,在某个句子里面,肯定会涉及到表达情感的词语,包括但不限于“高兴”,“沮丧”,“开心”等关键词。而这些句子里面的其他词语,则是上下文的关系,并不是它们没有用,而是它们所起的作用没有那些表达情感的关键词大。

在以上描述下,注意力机制其实包含两个部分

  1. 注意力机制需要决定整段输入的哪个部分需要更加关注;
  2. 从关键的部分进行特征提取,得到重要的信息。

通常来说,在机器翻译或者自然语言处理领域,人们阅读和理解一句话或者一段话其实是有着一定的先后顺序的,并且按照语言学的语法规则来进行阅读理解。在图片分类领域,人们看一幅图也是按照先整体再局部,或者先局部再整体来看的。再看局部的时候,尤其是手写的手机号,门牌号等信息,都是有先后顺序的。为了模拟人脑的思维方式和理解模式,循环神经网络(RNN)在处理这种具有明显先后顺序的问题上有着独特的优势,因此,Attention 机制通常都会应用在循环神经网络上面。

虽然,按照上面的描述,机器翻译,自然语言处理,计算机视觉领域的注意力机制差不多,但是其实仔细推敲起来,这三者的注意力机制是有明显区别的。

  1. 在机器翻译领域,翻译人员需要把已有的一句话翻译成另外一种语言的一句话。例如把一句话从英文翻译到中文,把中文翻译到法语。在这种情况下,输入语言和输出语言的词语之间的先后顺序其实是相对固定的,是具有一定的语法规则的;
  2. 在视频分类或者情感识别领域,视频的先后顺序是由时间戳和相应的片段组成的,输入的就是一段视频里面的关键片段,也就是一系列具有先后顺序的图片的组合。NLP 中的情感识别问题也是一样的,语言本身就具有先后顺序的特点;
  3. 图像识别,物体检测领域与前面两个有本质的不同。因为物体检测其实是在一幅图里面挖掘出必要的物体结构或者位置信息,在这种情况下,它的输入就是一幅图片,并没有非常明显的先后顺序,而且从人脑的角度来看,由于个体的差异性,很难找到一个通用的观察图片的方法。由于每个人都有着自己观察的先后顺序,因此很难统一成一个整体。

在这种情况下,机器翻译和自然语言处理领域使用基于 RNN 的 Attention 机制就变得相对自然,而计算机视觉领域领域则需要必要的改造才能够使用 Attention 机制。

LSTM_3

基于 RNN 的注意力机制

通常来说,RNN 等深度神经网络可以进行端到端的训练和预测,在机器翻译领域和或者文本识别领域有着独特的优势。对于端到端的 RNN 来说,有一个更简洁的名字叫做 sequence to sequence,简写就是 seq2seq。顾名思义,输入层是一句话,输出层是另外一句话,中间层包括编码和解码两个步骤。

而基于 RNN 的注意力机制指的是,对于 seq2seq 的诸多问题,在输入层和输出层之间,也就是词语(Items)与词语之间,存在着某种隐含的联系。例如:“中国” -> “China”,“Excellent” -> “优秀的”。在这种情况下,每次进行机器翻译的时候,模型需要了解当前更加关注某个词语或者某几个词语,只有这样才能够在整句话中进行必要的提炼。在这些初步的思考下,基于 RNN 的 Attention 机制就是:

  1. 建立一个编码(Encoder)和解码(Decoder)的非线性模型,神经网络的参数足够多,能够存储足够的信息;
  2. 除了关注句子的整体信息之外,每次翻译下一个词语的时候,需要对不同的词语赋予不同的权重,在这种情况下,再解码的时候,就可以同时考虑到整体的信息和局部的信息。

LSTM_4

注意力机制的种类

从初步的调研情况来看,注意力机制有两种方法,一种是基于强化学习(Reinforcement Learning)来做的,另外一种是基于梯度下降(Gradient Decent)来做的。强化学习的机制是通过收益函数(Reward)来激励,让模型更加关注到某个局部的细节。梯度下降法是通过目标函数以及相应的优化函数来做的。无论是 NLP 还是 CV 领域,都可以考虑这些方法来添加注意力机制。

LSTM_5

计算机视觉领域的 Attention 部分论文整理

下面将会简单的介绍几篇近期阅读的计算机视觉领域的关于注意力机制的文章。

Look Closer to See Better:Recurrent Attention Convolutional Neural Network for Fine-grained Image Recognition

在图像识别领域,通常都会遇到给图片中的鸟类进行分类,包括种类的识别,属性的识别等内容。为了区分不同的鸟,除了从整体来对图片把握之外,更加关注的是一个局部的信息,也就是鸟的样子,包括头部,身体,脚,颜色等内容。至于周边信息,例如花花草草之类的,则显得没有那么重要,它们只能作为一些参照物。因为不同的鸟类会停留在树木上,草地上,关注树木和草地的信息对鸟类的识别并不能够起到至关重要的作用。所以,在图像识别领域引入注意力机制就是一个非常关键的技术,让深度学习模型更加关注某个局部的信息。

RA_CNN_1

在这篇文章里面,作者们提出了一个基于 CNN 的注意力机制,叫做 recurrent attention convolutional neural network(RA-CNN),该模型递归地分析局部信息,从局部的信息中提取必要的特征。同时,在 RA-CNN 中的子网络(sub-network)中存在分类结构,也就是说从不同区域的图片里面,都能够得到一个对鸟类种类划分的概率。除此之外,还引入了 attention 机制,让整个网络结构不仅关注整体信息,还关注局部信息,也就是所谓的 Attention Proposal Sub-Network(APN)。这个 APN 结构是从整个图片(full-image)出发,迭代式地生成子区域,并且对这些子区域进行必要的预测,并将子区域所得到的预测结果进行必要的整合,从而得到整张图片的分类预测概率。

RA_CNN_2

RA-CNN 的特点是进行一个端到端的优化,并不需要提前标注 box,区域等信息就能够进行鸟类的识别和图像种类的划分。在数据集上面,该论文不仅在鸟类数据集(CUB Birds)上面进行了实验,也在狗类识别(Stanford Dogs)和车辆识别(Stanford Cars)上进行了实验,并且都取得了不错的效果。

RA_CNN_4

从深度学习的网络结构来看,RA-CNN 的输入时是整幅图片(Full Image),输出的时候就是分类的概率。而提取图片特征的方法通常来说都是使用卷积神经网络(CNN)的结构,然后把 Attention 机制加入到整个网络结构中。从下图来看,一开始,整幅图片从上方输入,然后判断出一个分类概率;然后中间层输出一个坐标值和尺寸大小,其中坐标值表示的是子图的中心点,尺寸大小表示子图的尺寸。在这种基础上,下一幅子图就是从坐标值和尺寸大小得到的图片,第二个网络就是在这种基础上构建的;再迭代持续放大图片,从而不停地聚焦在图片中的某些关键位置。不同尺寸的图片都能够输出不同的分类概率,再将其分类概率进行必要的融合,最终的到对整幅图片的鸟类识别概率。

因此,在整篇论文中,有几个关键点需要注意:

  1. 分类概率的计算,也就是最终的 loss 函数的设计;
  2. 从上一幅图片到下一幅图片的坐标值和尺寸大小。

只要获得了这些指标,就可以把整个 RA-CNN 网络搭建起来。

大体来说,第一步就是给定了一幅输入图片 X, 需要提取它的特征,可以记录为 W_{c}*X,这里的 * 指的是卷积等各种各样的操作。所以得到的概率分布情况其实就是 p(X) = f(W_{c}*X)f 指的是从 CNN 的特征层到全连接层的函数,外层使用了 Softmax 激活函数来计算鸟类的概率。

第二步就是计算下一个 box 的坐标 (t_{x}, t_{y}) 和尺寸大小 t_{\ell},其中 t_{x}, t_{y} 分别指的是横纵坐标,正方形的边长其实是 2*t_{\ell}。用数学公式来记录这个流程就是 [t_{x}, t_{y}, t_{\ell}] = g(W_{c}*X)。在坐标值的基础上,我们可以得到以下四个值,分别表示 x, y 两个坐标轴的上下界:

t_{x(t\ell)} = t_{x} - t_{\ell}, t_{x(br)} = t_{x} + t_{\ell},

t_{y(t\ell)} = t_{y} - t_{\ell}, t_{y(br)} = t_{y} + t_{\ell}.

局部注意力和放大策略(Attention Localization and Amplification)指的是:从上面的方法中拿到坐标值和尺寸,然后把图像进行必要的放大。为了提炼局部的信息,其实就需要在整张图片 X 的基础上加上一个面具(Mask)。所谓面具,指的是在原始图片的基础上进行点乘 0 或者 1 的操作,把一些数据丢失掉,把一些数据留下。在图片领域,就是把周边的信息丢掉,把鸟的信息留下。但是,有的时候,如果直接进行 0 或者 1 的硬编码,会显得网络结构不够连续或者光滑,因此就有其他的替代函数。

在激活函数里面,逻辑回归函数(Logistic Regression)是很常见的。其实通过逻辑回归函数,我们可以构造出近似的阶梯函数或者面具函数。

sigmoid_1

对于逻辑回归函数 \sigma(x) = 1/(1+e^{-kx}) 而言,当 k 足够大的时候,\sigma(x) \approx 1x \geq 0\sigma(x) \approx 0x<0。此时的逻辑回归函数近似于一个阶梯函数。如果假设 x_{0}<x_{1},那么 \sigma(x-x_{0}) - \sigma(x-x_{1}) 就是光滑一点的阶梯函数,\sigma(x-x_{0}) - \sigma(x-x_{1}) \approx 0x < x_{0} \text{ or } x > x_{1}\sigma(x-x_{0}) - \sigma(x-x_{1}) \approx 1x_{0}\leq x\leq x_{1}

因此,基于以上的分析和假设,我们可以构造如下的函数:X^{attr} = X \odot M(t_{x}, t_{y}, t_{\ell}), 其中,X^{attr} 表示图片需要关注的区域,M(\cdot) 函数就是 M(t_{x}, t_{y}, t_{\ell}) = [\sigma(x-t_{x(t\ell)}) - \sigma(x-t_{x(br)})]\cdot[\sigma(y-t_{y(t\ell)}) - \sigma(y-t_{y(br)})], 这里的 \sigma 函数对应了一个足够大的 k 值。

当然,从一张完整的图片到小图片,在实际操作的时候,需要把小图片继续放大,在放大的过程中,可以考虑使用双线性插值算法来扩大。也就是说:

X_{(i,j)}^{amp} = \sum_{\alpha,\beta=0}^{1}|1-\alpha-\{i/\lambda\}|\cdot|1-\beta-\{j/\lambda\}|\cdot X_{(m,n)}^{att},

其中 m = [i/\lambda] + \alpha, n = [j/\lambda] + \beta\lambda 表示上采样因子,[\cdot], \{\cdot\} 分别表示一个实数的正数部分和小数部分。

在分类(Classification)和排序(Ranking)部分,RA-CNN 也有着自己的方法论。在损失函数(Loss Function)里面有两个重要的部分,第一个部分就是三幅图片的 LOSS 函数相加,也就是所谓的 classification loss,Y^{(s)} 表示预测类别的概率,Y 表示真实的类别。除此之外,另外一个部分就是排序的部分,L_{rank}(p_{t}^{(s)}, p_{t}^{(s+1)}) = \max\{0,p_{t}^{(s)}-p_{t+1}^{(s+1)}+margin\}, 其中 p^{(s)} 表示在第 s 个尺寸下所得到的类别 t 的预测概率,并且最大值函数强制了该深度学习模型在训练中可以保证 p_{t}^{(s+1)} > p_{t}^{(s)} + margin,也就是说,局部预测的概率值应该高于整体的概率值。

L(X) = \sum_{s=1}^{3}\{L_{cls}(Y^{(s)},Y^{*})\} + \sum_{s=1}^{2}\{L_{rank}(p_{t}^{(s)},p_{t}^{(s+1)})\}.

RA_CNN_3

在这种 Attention 机制下,可以使用训练好的 conv5_4 或者 VGG-19 来进行特征的提取。在图像领域,location 的位置是需要通过训练而得到的,因为每张图片的鸟的位置都有所不同。进一步通过数学计算可以得到,t_{\ell} 会随着网络而变得越来越小,也就是一个层次递进的关系,越来越关注到局部信息的提取。简单来看,

\frac{\partial L_{rank}}{\partial t_{x}} \propto D_{top} \odot \frac{\partial M(t_{x},t_{y},t_{\ell})}{\partial t_{x}},

这里的 \odot 表示元素的点乘,D_{top} 表示之前的网络所得到的导数。

x\rightarrow t_{x(t\ell)}\frac{\partial M}{\partial t_{x}}<0;

x \rightarrow t_{x(br)}\frac{\partial M}{\partial t_{x}}>0;

其余情况,\frac{\partial M}{\partial t_{x}}=0.

y\rightarrow t_{y(t\ell)}\frac{\partial M}{\partial t_{y}}<0;

y \rightarrow t_{y(br)}\frac{\partial M}{\partial t_{y}}>0;

其余情况,\frac{\partial M}{\partial t_{y}}=0.

x \rightarrow t_{x(t\ell)}\text{ or } x \rightarrow t_{x(br)}\text{ or } y \rightarrow t_{y(t\ell)}\text{ or } y \rightarrow t_{y(br)}, \frac{\partial M}{\partial t_{\ell}}>0;

其余情况,\frac{\partial M}{\partial t_{\ell}}<0.

因此,t_{\ell} 在迭代的过程中会越来越小,也就是说关注的区域会越来越集中。

RA-CNN 的实验效果如下:

RA_CNN_5.png

 

Multiple Granularity Descriptors for Fine-grained Categorization

这篇文中同样做了鸟类的分类工作,与 RA-CNN 不同之处在于它使用了层次的结构,因为鸟类的区分是按照一定的层次关系来进行的,粗糙来看,有科 -> 属 -> 种三个层次结构。

MC_CNN_1

因此,在设计网络结构的过程中,需要有并行的网络结构,分别对应科,属,种三个层次。从前往后的顺序是检测网络(Detection Network),区域发现(Region Discovery),描述网络(Description Network)。并行的结构是 Family-grained CNN + Family-grained Descriptor,Genus-grained CNN + Genus-grained Descriptor,Species-grained CNN + Species-grained Descriptor。而在区域发现的地方,作者使用了 energy 的思想,让神经网络分别聚焦在图片中的不同部分,最终的到鸟类的预测结果。

MC_CNN_2MC_CNN_3

Recurrent Models of Visual Attention

在计算机视觉中引入注意力机制,DeepMind 的这篇文章 recurrent models of visual attention 发表于 2014 年。在这篇文章中,作者使用了基于强化学习方法的注意力机制,并且使用收益函数来进行模型的训练。从网络结构来看,不仅从整体来观察图片,也从局部来提取必要的信息。

DeepMind_1

DeepMind_2DeepMind_3

整体来看,其网络结构是 RNN,上一个阶段得到的信息和坐标会被传递到下一个阶段。这个网络只在最后一步进行分类的概率判断,这是与 RA-CNN 不同之处。这是为了模拟人类看物品的方式,人类并非会一直把注意力放在整张图片上,而是按照某种潜在的顺序对图像进行扫描。Recurrent Models of Visual Attention 本质上是把图片按照某种时间序列的形式进行输入,一次处理原始图片的一部分信息,并且在处理信息的过程中,需要根据过去的信息和任务选择下一个合适的位置进行处理。这样就可以不需要进行事先的位置标记和物品定位了。

DeepMind_4

正如上图所示,enc 指的是对图片进行编码,r_{i}^{(1)} 表示解码的过程,x_{i} 表示图片的一个子区域。而 y_{s} 表示对图片的预测概率或者预测标签。

 

Multiple Object Recognition with Visual Attention

这篇文章同样是 DeepMind 的论文,与 Recurrent Models of Visual Attention 不同之处在于,它是一个两层的 RNN 结构,并且在最上层把原始图片进行输入。其中 enc 是编码网络,r^{(1)}_{i} 是解码网络,r_{i}^{(2)} 是注意力网络,输出概率在解码网络的最后一个单元输出。

deep_recurrent_attention_model_1

在门牌识别里面,该网络是按照从左到右的顺序来进行图片扫描的,这与人类识别物品的方式极其相似。除了门牌识别之外,该论文也对手写字体进行了识别,同样取得了不错的效果。

deep_recurrent_attention_model_3deep_recurrent_attention_model_2

实验效果如下:

deep_recurrent_attention_model_4.png

总结

本篇 Blog 初步介绍了计算机视觉中的 Attention 机制,除了这些方法之外,应该还有一些更巧妙的方法,希望各位读者多多指教。

参考文献

  1. Look Closer to See Better:Recurrent Attention Convolutional Neural Network for Fine-grained Image Recognition,CVPR,2017.
  2. Recurrent Models of Visual Attention,NIPS,2014
  3. GitHub 代码:Recurrent-Attention-CNN,https://github.com/Jianlong-Fu/Recurrent-Attention-CNN
  4. Multiple Granularity Descriptors for Fine-grained Categorization,ICCV,2015
  5. Multiple Object Recognition with Visual Attention,ICRL,2015
  6. Understanding LSTM Networks,Colah’s Blog,2015,http://colah.github.io/posts/2015-08-Understanding-LSTMs/
  7. Survey on the attention based RNN model and its applications in computer vision,2016

 

时间序列的聚类

在机器学习领域,聚类问题一直是一个非常常见的问题。无论是在传统的机器学习(Machine Learning)领域,还是自然语言处理(Natural Language Processing)领域,都可以用聚类算法做很多的事情。例如在数据分析领域,我们可以把某个物品用特征来描述出来,例如该房子的面积,价格,朝向等内容,然后使用聚类算法来把相似的房子聚集到一起;在自然语言处理领域,通常都会寻找一些相似的新闻或者把相似的文本信息聚集到一起,在这种情况下,可以用 Word2Vec 把自然语言处理成向量特征,然后使用 KMeans 等机器学习算法来作聚类。除此之外,另外一种做法是使用 Jaccard 相似度来计算两个文本内容之间的相似性,然后使用层次聚类(Hierarchical Clustering)的方法来作聚类。

word2vec1

本文将会从常见的聚类算法出发,然后介绍时间序列聚类的常见算法。

机器学习的聚类算法

KMeans — 基于距离的机器学习聚类算法

KMeans 算法的目的是把欧氏空间 \mathbb{R}^{m} 中的 n 个节点,基于它们之间的距离公式,把它们划分成 K 个类别,其中类别 K 的个数是需要在执行算法之前人为设定的。

kmeans1

从数学语言上来说,假设已知的欧式空间点集为 \{x_{1},\cdots,x_{n}\},事先设定的类别个数是 K,当然 K\leq n 是必须要满足的,因为类别的数目不能够多于点集的元素个数。算法的目标是寻找到合适的集合 \{S_{i}\}_{1\leq i\leq K} 使得 argmin_{S_{i}}\sum_{x\in S_{i}}||x-\mu_{i}||^{2} 达到最小,其中 \mu_{i} 表示集合 S_{i} 中的所有点的均值。

上面的 ||\cdot|| 表示欧式空间的欧几里得距离,在这种情况下,除了使用 L^{2} 范数之外,还可以使用 L^{1} 范数和其余的 L^{p},p\geq 1 范数。只要该范数满足距离的三个性质即可,也就是非负数,对称,三角不等式。

层次聚类 — 基于相似性的机器学习聚类算法

层次聚类通常来说有两种方法,一种是凝聚,另外一种是分裂。

hierarchicalclustering1

所谓凝聚,其大体思想就是在一开始的时候,把点集集合中的每个元素都当做一类,然后计算每两个类之前的相似度,也就是元素与元素之间的距离;然后计算集合与集合之前的距离,把相似的集合放在一起,不相似的集合就不需要合并;不停地重复以上操作,直到达到某个限制条件或者不能够继续合并集合为止。

所谓分裂,正好与聚合方法相反。其大体思想就是在刚开始的时候把所有元素都放在一类里面,然后计算两个元素之间的相似性,把不相似元素或者集合进行划分,直到达到某个限制条件或者不能够继续分裂集合为止。

在层次聚类里面,相似度的计算函数就是关键所在。在这种情况下,可以设置两个元素之间的距离公式,例如欧氏空间中两个点的欧式距离。在这种情况下,距离越小表示两者之间越相似,距离越大则表示两者之间越不相似。除此之外,还可以设置两个元素之间的相似度。例如两个集合中的公共元素的个数就可以作为这两个集合之间的相似性。在文本里面,通常可以计算句子和句子的相似度,简单来看就是计算两个句子之间的公共词语的个数。

时间序列的聚类算法

通过以上的描述,如果要做时间序列的聚类,通常来说也有多种方法来做,可以使用基于距离的聚类算法 KMeans,也可以使用基于相似度计算的层次聚类算法。

时间序列的特征提取

之前写过很多时间序列特征提取的方法,无论是常见的时间序列特征,例如最大值,最小值,均值,中位数,方差,值域等内容之外。还可以计算时间序列的熵以及分桶的情况,其分桶的熵指的是把时间序列的值域进行切分,就像 Lebesgue 积分一样,查看落入那些等分桶的时间序列的概率分布情况,就可以进行时间序列的分类。除了 Binned Entropy 之外,还有 Sample Entropy 等各种各样的特征。除了时域特征之外,也可以对时间序列的频域做特征,例如小波分析,傅里叶分析等等。因此,在这种情况下,其实只要做好了时间序列的特征,使用 KMeans 算法就可以得到时间序列的聚类效果,也就是把相似的曲线放在一起。参考文章:时间序列的表示与信息提取。

在提取时间序列的特征之前,通常可以对时间序列进行基线的提取,把时间序列分成基线和误差项。而基线提取的最简单方法就是进行移动平均算法的拟合过程,在这种情况下,可以把原始的时间序列 \{x_{1},\cdots,x_{n}\} 分成两个部分 \{baseline_{1},\cdots,baseline_{n}\}\{residual_{1},\cdots,residual_{n}\}。i.e. x_{i} = baseline_{i} + residual_{i}。有的时候,提取完时间序列的基线之后,其实对时间序列的基线做特征,有的时候分类效果会优于对原始的时间序列做特征。参考文章:两篇关于时间序列的论文。

时间序列的相似度计算

如果要计算时间序列的相似度,通常来说除了欧几里得距离等 L^{p} 距离之外,还可以使用 DTW 等方法。在这种情况下,DTW 是基于动态规划算法来做的,基本想法是根据动态规划原理,来进行时间序列的“扭曲”,从而把时间序列进行必要的错位,计算出最合适的距离。一个简单的例子就是把 y=\sin(x)y=\cos(x) 进行必要的横坐标平移,计算出两条时间序列的最合适距离。但是,从 DTW 的算法描述来看,它的算法复杂度是相对高的,是 O(n^{2}) 量级的,其中 n 表示时间序列的长度。参考文章:时间序列的搜索。

dtw1

如果不考虑时间序列的“扭曲”的话,也可以直接使用欧氏距离,无论是 L^{1}, L^{2} 还是 L^{p} 都有它的用武之地。除了距离公式之外,也可以考虑两条时间序列之间的 Pearson 系数,如果两条时间序列相似的话,那么它们之间的 Pearson 系数接近于 1;如果它们之间是负相关的,那么它们之间的 Pearson 系数接近于 -1;如果它们之间没有相关性,Pearson 系数接近于0。除了 Pearson 系数之外,也可以考虑它们之间的线性相关性,毕竟线性相关性与 Pearson 系数是等价的。参考文章:时间序列的相似性。

除此之外,我们也可以用 Auto Encoder 等自编码器技术对时间序列进行特征的编码,也就是说该自编码器的输入层和输出层是恒等的,中间层的神经元个数少于输入层和输出层。在这种情况下,是可以做到对时间序列进行特征的压缩和构造的。除了 Auto Encoder 等无监督方法之外,如果使用其他有监督的神经网络结构的话,例如前馈神经网络,循环神经网络,卷积神经网络等网络结构,可以把归一化之后的时间序列当做输入层,输出层就是时间序列的各种标签,无论是该时间序列的形状种类还是时间序列的异常/正常标签。当该神经网络训练好了之后,中间层的输出都可以作为 Time Series To Vector 的一种模式。i.e. 也就是把时间序列压缩成一个更短一点的向量,然后基于 COSINE 相似度等方法来计算原始时间序列的相似度。参考文章:基于自编码器的时间序列异常检测算法基于前馈神经网络的时间序列异常检测算法。

总结

如果想对时间序列进行聚类,其方法是非常多的。无论是时间序列的特征构造,还是时间序列的相似度方法,都是需要基于一些人工经验来做的。如果使用深度学习的方法的话,要么就提供大量的标签数据;要么就只能够使用一些无监督的编码器的方法了。本文目前初步介绍了一些时间序列的聚类算法,后续将会基于笔者的学习情况来做进一步的撰写工作。

参考文献

  1. 聚类分析:https://en.wikipedia.org/wiki/Cluster_analysis
  2. Dynamic Time Warping:https://en.wikipedia.org/wiki/Dynamic_time_warping
  3. Pearson Coefficient:https://en.wikipedia.org/wiki/Pearson_correlation_coefficient
  4. Auto Encoder:https://en.wikipedia.org/wiki/Autoencoder
  5. Word2Vec:https://en.wikipedia.org/wiki/Word2vec,https://samyzaf.com/ML/nlp/nlp.html

时间序列的单调性

在时间序列的众多研究方向上,除了时间序列异常检测,时间序列的相似性,时间序列的趋势预测之外,无论是在量化交易领域还是其余领域,时间序列的单调性都是一个重要课题。本文将会对时间序列的单调性作简单的介绍。

连续函数的单调性

导数1

在微积分里面,通常都会研究可微函数的导数,因为导数是反映可微函数单调性的一个重要指标。假设 f(x) 是定义域 (a,b) 上的可导函数,那么某个点 x_{0}\in(a,b) 的导数则定义为:

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

对于区间 (a,b) 上的可导函数 f(x) 而言,假设 x_{0}\in (a,b)。如果 f'(x_{0})>0,那么在 x_{0} 的附近,f(x) 是严格单调递增函数;如果 f'(x_{0})<0,那么在 x_{0} 的附近,f(x) 是严格单调递减函数;如果 f'(x_{0})=0,则基于这个事实无法轻易的判断 f(x)x_{0} 附近的单调性。可以参考这两个例子:(1)f(x)=x^{2}x_{0}=0;(2)f(x) = x^{3}x_{0}=0。这两个例子在 x_{0}=0 的导数都是零,并且第一个例子在 x_{0}=0 附近没有单调性,x_{0}=0 就是最小值点;但是第二个例子在 x_{0}=0 处是严格递增的。

平方函数

立方函数

时间序列的单调性

通常来说,时间序列分成上涨下跌两种趋势。如果要严格来写的话,当 x_{n-i+1}<\cdots<x_{n} 时,表示时间序列在 [n-i+1,n] 这个区间内是严格单调递增的;当 x_{n-i+1}>\cdots>x_{n} 时,表示时间序列在 [n-i+1, n] 这个区间内是严格单调下跌的。但是,在现实环境中,较难找到这种严格递增或者严格递减的情况。在大部分情况下,只存在一个上涨或者下跌的趋势,一旦聚焦到某个时间戳附近时间序列是有可能存在抖动性的。所以我们需要给出一个定义,用来描述时间序列在一个区间内的趋势是上升还是下跌。

考虑时间序列 X_{N} = [x_{1},\cdots,x_{N}] 的一个子序列 [x_{i},x_{i+1},\cdots,x_{j}],其中 i<j。如果存在某个 k\in (i,j] 和一组非负实数 [w_{i}, w_{i+1},\cdots,w_{j}] 使得

\sum_{m=k}^{j}w_{m}x_{m} > \sum_{m=i}^{k-1} w_{m}x_{m}, 其中\sum_{m=k}^{j}w_{m} = \sum_{m=i}^{k-1}w_{m}.

就称时间序列 [x_{i},x_{i+1},\cdots,x_{j}]上涨的趋势。

如果存在某个 k\in (i,j] 和一组非负实数 [w_{i}, w_{i+1},\cdots,w_{j}] 使得

\sum_{m=k}^{j}w_{m}x_{m} < \sum_{m=i}^{k-1} w_{m}x_{m}, 其中 \sum_{m=k}^{j}w_{m} = \sum_{m=i}^{k-1}w_{m}.

就称时间序列 [x_{i},x_{i+1},\cdots,x_{j}]下跌的趋势。

时间序列的单调性 — 均线方法

虽然时间序列是离散的,但是却可以把连续函数的思想应用在上面。

假设现在有一个时间序列是 X = [x_{1},\cdots,x_{N}],可以考虑第 i 个点 x_{i} 附近的单调性,按照导数的思想来看就是:当 k\geq 1 时,

(x_{i+k}-x_{i})/((i+k)-i) = (x_{i+k}-x_{i})/k,
(x_{i} - x_{i-k})/(i-(i-k)) = (x_{i} -x_{i-k})/k.

考虑特殊的情形,假设 k=1,当第一个公式大于零时,表示 x_{i+1}>x_{i},i.e. 处于单调上升的趋势中。当第一个公式小于零时,表示 x_{i}<x_{i-1},i.e. 处于单调下降的趋势中。

但是,时间序列有可能有一定的波动性,也就是说时间序列有可能其实看上去是单调上升的,但是有一定的噪声或者毛刺。所以需要想办法处理掉一些噪声和毛刺。于是,就有人提出了以下几种方法。

双均线1

简单的移动平均算法

在时间序列领域,简单的移动平均算法 (Simple Moving Average) 是最常见的算法之一。假设原始的时间序列是 X=[x_{1},\cdots,x_{N}],如果考虑时间戳 n 的移动平均值,那就是考虑从时间戳 n 开始,历史上某个窗口上面的所有序列的平均值,用数学公式来描述就是:

M_{w}(n) = \frac{x_{n-w+1}+\cdots+x_{n}}{w} = \frac{\sum_{j=n-w+1}^{n}x_{j}}{w},

其中 w\geq 1 指的就是窗口的大小。

命题 1. 假设窗口值 \ell>s\geq 1M_{s}(n) - M_{\ell}(n) >0, 表示短线上穿长线,曲线有上涨的趋势;M_{s}(n) - M_{\ell}(n) <0, 表示短线下穿长线,曲线有下跌的趋势。

在这里,短线指的是窗口值 s 所对应的移动平均线,长线指的是窗口值 \ell 所对应的移动平均线。

证明.
根据条件可以得到,n-\ell+1\leq n-s<n-s+1<n。假设 M_{s}(n) > M_{\ell}(n),那么通过数学推导可以得到:

M_{s}(n) > M_{\ell}(n)
\Leftrightarrow \frac{\sum_{j=n-s+1}^{n}x_{j}}{s} > \frac{\sum_{j=n-\ell+1}^{n}x_{j}}{\ell} = \frac{\sum_{j=n-\ell+1}^{n-s}x_{j} + \sum_{j=n-s+1}^{n}x_{j}}{\ell}
\Leftrightarrow M_{s}(n)=\frac{\sum_{j=n-s+1}^{n}x_{j}}{s} > \frac{\sum_{j=n-\ell+1}^{n-s}x_{j}}{\ell-s} = M_{\ell-s}(n-s),

此时说明 x_{n} 历史上的 s 个点的平均值大于 x_{n-s} 历史上的 \ell - s 个点的平均值,该序列有上涨的趋势。反之,如果 M_{s}(n) < M_{\ell}(n),那么该序列有下跌的趋势。

带权重的移动平均算法

如果窗口值是 w,对于简单移动平均算法,那么 x_{n-w+1}, \cdots, x_{n} 每个元素的权重都是 1/w,它们都是一样的权重。有的时候我们不希望权重都是恒等的,因为近期的点照理来说是比历史悠久的点更加重要,于是有人提出带权重的移动平均算法 (Weighted Moving Average)。从数学上来看,带权重的移动平均算法指的是

WMA_{w}(n) = \frac{x_{n-w+1}+2\cdot x_{n-w+2}+\cdots + w\cdot x_{n}}{1+2+\cdots+w} = \frac{\sum_{j=1}^{w}j \cdot x_{n-w+j}}{w\ \cdot (w+1)/2}.

wma

命题 2. 
假设窗口值 \ell > s,那么WMA_{s}(n) - WMA_{\ell}(n) >0, 表示短线上穿长线,曲线有上涨的趋势;WMA_{s}(n) - WMA_{\ell}(n) <0, 表示短线下穿长线,曲线有下跌的趋势。

在这里,短线指的是窗口值 s 所对应的带权重的移动平均线,长线指的是窗口值 \ell 所对应的带权重的移动平均线。

证明.
根据假设条件可以得到:n-\ell + 1 \leq n-s < n-s < n。假设 WMA_{s}(n) > WMA_{\ell}(n),那么

WMA_{s}(n) > WMA_{\ell}(n)
\Leftrightarrow \frac{\sum_{j=1}^{s} j \cdot x_{n-s+j}}{s\cdot(s+1)/2} > \frac{\sum_{j=1}^{\ell}j\cdot x_{n-\ell +j}}{\ell\cdot(\ell+1)/2} = \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+s} + \sum_{j=\ell -s + 1}^{\ell}j\cdot x_{n-\ell + j}}{\ell\cdot(\ell+1)/2}
\Leftrightarrow \frac{\sum_{j=1}^{s} j \cdot x_{n-s+j}}{s\cdot(s+1)/2} > \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+s} + \sum_{j=1}^{s}(j+\ell-s)\cdot x_{n- s + j}}{\ell\cdot(\ell+1)/2}
\Leftrightarrow \sum_{j=1}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) \cdot x_{n-s+j} > \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+j}}{\ell\cdot(\ell+1)/2}
\Leftrightarrow \sum_{j=j_{0}}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) \cdot x_{n-s+j} > \frac{\sum_{j=1}^{\ell-s}j\cdot x_{n-\ell+j}}{\ell\cdot(\ell+1)/2}
+ \sum_{j=1}^{j_{0}-1} \bigg(\frac{j+\ell -s}{\ell\cdot(\ell+1)/2}- \frac{j}{s\cdot(s+1)/2}\bigg) \cdot x_{n-s+j},

其中 j_{0}=[s\cdot(s+1)/(\ell + s-1)],这里的 [\cdot] 表示 Gauss 取整函数。因为

\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \geq 0 \Leftrightarrow j \geq \frac{s\cdot(s+1)}{\ell+s-1},

所以不等式两边的系数都是非负数。而 n-\ell + 1 \leq n - s < n-s+1 < n - s + j_{0} -1 < n - s + j_{0} < n,于是距离当前点 x_{n} 的时间序列相比之前的时间序列有上涨的趋势,并且该不等式两边的系数之和是相等的。这是因为

\sum_{j=j_{0}}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) = \frac{\sum_{j=1}^{\ell-s}j}{\ell\cdot(\ell+1)/2} + \sum_{j=1}^{j_{0}-1} \bigg(\frac{j+\ell -s}{\ell\cdot(\ell+1)/2}- \frac{j}{s\cdot(s+1)/2}\bigg)
\Leftrightarrow \sum_{j=1}^{s}\bigg(\frac{j}{s\cdot(s+1)/2} - \frac{j+\ell -s}{\ell\cdot(\ell+1)/2} \bigg) = \frac{\sum_{j=1}^{\ell-s}j}{\ell\cdot(\ell+1)/2},

以上等式易得。于是,当 WMA_{s}(n) >WMA_{\ell}(n) 时,表示时间序列有上涨的趋势;当 WMA_{s}(n) < WMA_{\ell}(n) 时,表示时间序列有下跌的趋势。

指数移动平均算法

指数移动平均算法 (Exponentially Weighted Moving Average) 指的也是移动平均算法,但是它的权重并不是线性递减的,而是呈指数形式递减的。具体来说,如果时间序列是 \{x_{i}, i\geq 1\},那么它的指数移动平均算法就是:

\text{EWMA}(\alpha, i) = x_{1}, \text{ when } i = 1,
\text{EWMA}(\alpha, i) = \alpha \cdot x_{i} + (1-\alpha) \cdot \text{EWMA}(\alpha, i-1), \text{ when } i \geq 2,

在这里 \alpha\in (0,1)

ewma

从数学公式可以推导得出:

\text{EWMA}(\alpha, i) = \alpha x_{i} + \alpha(1-\alpha) x_{i-1} + \cdots \alpha(1-\alpha)^{k}x_{i-k} + (1-\alpha)^{k+1}\text{EWMA}(\alpha, t-(k+1)).

在这种情况下,假设 s<\ell,那么短线和长线则分别是:

\text{EWMA}_{s}(\alpha, n) = \alpha x_{n} + \alpha(1-\alpha) x_{n-1} + \cdots + \alpha(1-\alpha)^{s-2}x_{n-s+2} + (1-\alpha)^{s-1}x_{n-s+1},
\text{EWMA}_{\ell}(\beta, n) = \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{\ell-2}x_{n-\ell+2} + (1-\beta)^{\ell-1}x_{n-\ell+1}.

在这里,\alpha 是与 s 相关的值,\beta 是与 \ell 相关的值。

命题 3. 
假设 s<\ell,当 0<\beta<\alpha<\min\{1,1/(s-1)\} 时,\text{EWMA}_{s}(\alpha, n) - \text{EWMA}_{\ell}(\beta, n) > 0, 表示短线上穿长线,曲线有上涨的趋势;\text{EWMA}_{s}(\alpha, n) - \text{EWMA}_{\ell}(\beta, n) <0, 表示短线下穿长线,曲线有下跌的趋势。注:当 s=1 时,1/(s-1) 可以看做 +\infty.

证明.
s=1 时,\text{EWMA}_{s}(\alpha,n) = x_{n}。那么

\text{EWMA}_{s}(\alpha, n) > \text{EWMA}_{\ell}(\beta,n)
\Leftrightarrow x_{n} > \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{\ell-2}x_{n-\ell+2} + (1-\beta)^{\ell-1}x_{n-\ell+1}
\Leftrightarrow x_{n} > \beta x_{n-1} + \cdots + \beta(1-\beta)^{\ell-3}x_{n-\ell+2}+ (1-\beta)^{\ell-2}x_{n-\ell+1}.

这表示时间序列有上涨的趋势。反之,当 \text{EWMA}_{s}(\alpha, n) = x_{n} < \text{EWMA}_{\ell}(\beta, n) 时,表示时间序列有下跌的趋势。

s\geq 2 时,根据假设有 0<\beta<\alpha<1/(s-1),并且

\text{EWMA}_{s}(\alpha, n) = \alpha x_{n} + \alpha(1-\alpha) x_{n-1} + \cdots + \alpha(1-\alpha)^{s-2}x_{n-s+2} + (1-\alpha)^{s-1}x_{n-s+1},
\text{EWMA}_{\ell}(\beta, n) = \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{\ell-2}x_{n-\ell+2} + (1-\beta)^{\ell-1}x_{n-\ell+1}
= \beta x_{n} + \beta(1-\beta) x_{n-1} + \cdots + \beta(1-\beta)^{s-2}x_{n-s+2} + \beta(1-\beta)^{s-1}x_{n-s+1}
+ \beta(1-\beta)^{s}x_{n-s} + \cdots + (1-\beta)^{\ell-1}x_{n-\ell+1}.

假设 g(x) = x(1-x)^{n},通过计算可以得到 g'(x) = (1-x)^{n-1}(1-(n+1)x),也就是说 g(x)(0, 1/(n+1)) 上是递增函数,在 (1/(n+1), 1) 是递减函数。于是当 0<\beta<\alpha<1/(s-1) 时,

\alpha > \beta,
\alpha(1-\alpha) > \beta(1-\beta),
\cdots
\alpha(1-\alpha)^{s-2} > \beta(1-\beta)^{s-2}.

如果 (1-\alpha)^{s-1} > \beta(1-\beta)^{s-1},那么 \text{EWMA}_{s}(\alpha, n) > \text{EWMA}_{\ell}(\beta, n) 可以写成

(\alpha -\beta)x_{n} +\cdots + (\alpha(1-\alpha)^{s-2}-\beta(1-\beta)^{s-2})x_{n-s+2} + ((1-\alpha)^{s-1}-\beta(1-\beta)^{s-1})x_{n-s+1}
> \beta(1-\beta)^{s}x_{n-s} +\cdots + (1-\beta)^{\ell-1}x_{n-\ell+1},

说明在这种情况下时间序列有上涨的趋势。如果 (1-\alpha)^{s-1} < \beta(1-\beta)^{s-1},那么 \text{EWMA}_{s}(\alpha, n)> \text{EWMA}_{\ell}(\beta, n) 可以写成

(\alpha -\beta)x_{n} + \cdots + (\alpha(1-\alpha)^{s-2}-\beta(1-\beta)^{s-2})x_{n-s+2}
> (\beta(1-\beta)^{s-1} - (1-\alpha)^{s-1})x_{n-s+1} + \beta(1-\beta)^{s}x_{n-s} +\cdots + (1-\beta)^{\ell-1}x_{n-\ell+1},

说明在这种情况下,时间序列有上涨的趋势。

反之,当 \text{EWMA}_{s}(\alpha, n) < \text{EWMA}_{\ell}(\beta, n) 时,也可以使用同样的方法证明时间序列有下跌的趋势。

时间序列的单调性 — 带状方法

根据时间序列的走势,其实可以按照一定的规则计算出它的置信区间,也就是所谓的上界和下界。当最后一些点超过上界或者低于下界的时候,就可以说明这个时间序列的当前的趋势。

控制图1

3-\sigma 控制图

假设时间序列是 X_{N} = [x_{1},\cdots, x_{N}],为了计算某个时间戳 nx_{n} 的走势,需要考虑该时间序列历史上的一些点。假设我们考虑 [x_{1},x_{2},\cdots, x_{n}] 中的所有点,可以计算出均值和方差如下:

\mu = \frac{x_{1}+\cdots+x_{n}}{n},
\sigma^{2} = \frac{(x_{1}-\mu)^{2}+\cdots+(x_{n}-\mu)^{2}}{n}.

那么就可以计算出上界,中间线,下界分别是:

\text{UCL} = \mu + L \cdot \sigma,
\text{Center Line} = \mu,
\text{LCL} = \mu - L \cdot \sigma,

这里的 L 表示系数,通常选择 L=3

命题 4. x_{n} > \text{UCL},那么说明 x_{n} 有上涨的趋势;当 x_{n} < \text{LCL} 时,那么说明 x_{n} 有下跌的趋势;这里的 UCL 和 LCL 是基于 3-\sigma 原理所得到的上下界。

Moving Average 控制图

假设我们考虑的时间序列为 X_{N} = [x_{1},\cdots, x_{N}],那么基于窗口 w 的移动平均值就是

M_{w}(n) = \frac{x_{n-w+1}+\cdots + x_{n}}{w} = \frac{\sum_{j=n-w+1}^{n}x_{j}}{w}.

那么 M_{w}(n) 的方差是

V(M_{w}) = \frac{1}{w^{2}}\sum_{j=n-w+1}^{n} V(x_{j}) = \frac{1}{w^{2}}\sum_{j=n-w+1}^{n}\sigma^{2} = \frac{\sigma^{2}}{w}.

于是,基于移动平均算法的控制图就是:

\text{UCL} = \mu + L\cdot \frac{\sigma}{\sqrt{w}},
\text{Center Line} = \mu,
\text{LCL} = \mu - L \cdot \frac{\sigma}{\sqrt{w}},

这里的 L 表示系数,通常选择 L=3

命题 5. x_{n} > \text{UCL},那么说明 x_{n} 有上涨的趋势;当 x_{n} < \text{LCL} 时,那么说明 x_{n} 有下跌的趋势;这里的 UCL 和 LCL 是基于移动平均算法的控制图所得到的上下界。

macontrolchart

EWMA 控制图

假设 X_{N} = [x_{1},\cdots, x_{N}],那么根据指数移动平均算法可以得到:

z_{i} = x_{1}, \text{ when } i=1,
z_{i} = \lambda x_{i} + (1-\lambda) z_{i-1}, \text{ when } i\geq 2.

进一步分析可以得到:z_{i} 的方差是:

\sigma_{z_{i}}^{2}= \lambda^{2} \sigma^{2} + (1-\lambda)^{2} \sigma_{z_{i-1}}^{2},

于是,
\sigma_{z_{i}}^{2} = \frac{\lambda^{2}}{1-(1-\lambda)^{2}} \sigma^{2} \Rightarrow \sigma_{z_{i}} = \sqrt{\frac{\lambda}{2-\lambda}}\sigma.

因此,基于 EWMA 的控制图指的是:

\text{UCL} = \mu + L\sigma\sqrt{\frac{\lambda}{2-\lambda}},
\text{Center Line} = \mu,
\text{LCL} = \mu - L\sigma\sqrt{\frac{\lambda}{2-\lambda}},

这里的 L 是系数,通常取 L= 3

命题 6. x_{n} > \text{UCL},那么说明 x_{n} 有上涨的趋势;当 x_{n} < \text{LCL} 时,那么说明 x_{n} 有下跌的趋势;这里的 UCL 和 LCL 是基于 EWMA 的控制图所得到的上下界。

ewmacontrolchart

时间序列的单调性 — 柱状方法

macd1

MACD 方法

MACD 算法是比较常见的用于判断时间序列单调性的方法,它的大致思路分成以下几步:

  • 根据长短窗口分别计算两条指数移动平均线(EWMA short, EWMA long);
  • 计算两条指数移动平均线之间的距离,作为离差值(DIF);
  • 计算离差值(DIF)的指数移动平均线,作为DEA;
  • 将 (DIF-DEA) * 2 作为 MACD 柱状图。

用数学公式来详细描述就是:令 \ell = 26, s = 12, signal = 9,基于时间序列 X_{N} = [x_{1},\cdots,x_{N}],可以计算基于指数移动平均的两条线,对于所有的 1\leq n\leq N,有

\text{EWMA}_{s}(\alpha, n) = (1-\alpha) \cdot \text{EWMA}_{s}(\alpha, n-1) + \alpha \cdot x_{n},
\text{EWMA}_{\ell}(\beta,n) = (1-\beta) \cdot \text{EWMA}_{\ell}(\beta, n-1) + \beta \cdot x_{n},

其中

\alpha = \frac{2}{s+1} = \frac{2}{13},
\beta = \frac{2}{\ell+1} = \frac{2}{27}.

进一步可以计算离差值 (DIF) 如下:

\text{DIF}(n) = \text{EWMA}_{s}(\alpha, n) - \text{EWMA}_{\ell}(\beta,n).

\gamma = 2 / (signal + 1),计算 DEA 如下:

\text{DEA}(\gamma, n) = \gamma * \text{DIF}(n) + (1-\gamma) * \text{DEA}(\gamma, n).

最后可以计算 MACD 柱状图,对任意的 \forall \text{ }1\leq n\leq N

\text{MACD}(n) = (\text{DIF}(n) - \text{DEA}(\gamma, n)) * 2.

命题 7. 关于 MACD 的部分性质如下:

  • 当 DIF(n) 与 DEA(n) 都大于零时,表示时间序列有上涨的趋势;
  • 当 DIF(n) 与 DEA(n) 都小于零时,表示时间序列有递减的趋势;
  • 当 DIF(n) 下穿 DEA(n) 时,此时 MACD(n) 小于零,表示时间序列有下跌的趋势;
  • 当 DIF(n) 上穿 DEA(n) 时,此时 MACD(n) 大于零,表示时间序列有上涨的趋势;
  • MACD(n) 附近的向上或者向下的面积,可以作为时间序列上涨或者下跌幅度的标志。

PS:算法可以从指数移动平均算法换成移动平均算法或者带权重的移动平均算法,长短线的周期可以不局限于 26 和 12,信号线的周期也不局限于 9。

 

参考资料

  1. Moving Average:https://en.wikipedia.org/wiki/Moving_average
  2. Double Exponentially Moving Average:https://www.investopedia.com/articles/trading/10/double-exponential-moving-average.asp
  3. Control Chart:https://en.wikipedia.org/wiki/Control_chart
  4. MACD:https://www.investopedia.com/terms/m/macd.asp
  5. Introduction to Statistical Quality Control 6th edition,Douglas C.Montgomery

基于前馈神经网络的时间序列异常检测算法

引言

在时间序列异常检测中,特征工程往往是非常繁琐而复杂的,怎样才能够减少时间序列的特征工程工作量一直是一个关键问题。在本文中,作者们提出了一个新的思路,使用深度学习的办法来进行端到端的训练,从而减少时间序列的特征工程。

提到深度学习,大家都能够想到卷积神经网络(Convolutional Neural Network )在图像识别中的优异表现,能够想到循环神经网络(Recurrent Neural Network)在机器翻译和文本挖掘领域中所取得的成绩。而一旦提到时间序列,一般的人都能够想到使用 ARIMA 模型或者 LSTM 模型来拟合周期型的时间序列,或者使用其他算法来进行时间序列的异常检测。在这篇文章中,既不谈 CNN 和 LSTM 等深度学习模型,也不谈如何使用 LSTM 来拟合时间序列,本文将会介绍如何使用前馈神经网络 FNN 来进行时间序列的异常检测。并且将会介绍如何使用前馈神经网络,来拟合各种各样的时间序列特征。本篇论文《Feedforward Neural Network for Time Series Anomaly Detection》目前已经挂在 Arxiv 上,有兴趣的读者可以自行参阅:https://arxiv.org/abs/1812.08389

时间序列异常检测

时间序列异常检测的目的就是在时间序列中寻找不符合常见规律的异常点,无论是在学术界还是工业界这都是一个非常重要的问题。而时间序列异常检测的算法也是层出不穷,无论是统计学中的控制图理论,还是指数移动平均算法,甚至近些年最火的深度学习,都可以应用在时间序列的异常检测上面。在通常情况下,时间序列的异常点是十分稀少的,正常点是非常多的,因此,通常的套路都是使用统计判别算法无监督算法作为第一层,把有监督算法作为第二层,形成一个无监督与有监督相结合的框架。使用无监督算法可以过滤掉大量的正常样本,将我们标注的注意力放在少数的候选集上;使用有监督算法可以大量的提升准确率,可以把时间序列异常点精确地挑选出来。这个框架之前也说过多次,因此在这里就不再做赘述。

异常检测技术框架1

提到第二层的有监督学习算法,通常来说就包括逻辑回归,随机森林,GBDT,XGBoost,LightGBM 等算法。在使用这些算法的时候,不可避免地就需要构造时间序列的特征,也就是人工撰写特征工程的工作。提到时间序列的特征,一般都会想到各种各样的统计特征,例如最大值,最小值,均值等等。除了统计特征之外,我们还可以使用一些简单的时间序列模型,例如移动平均算法,指数移动平均算法等去拟合现有的时间序列,所得到的拟合值与实际值的差值就可以作为时间序列的拟合特征。除了统计特征和拟合特征之外,我们还可以根据时间序列的走势,例如周期型,毛刺型,定时任务型来构造出时间序列的分类特征,用于时间序列形状的多分类问题。因此,就笔者的个人观点,时间序列的特征大体上可以分成统计特征,拟合特征,周期性特征,分类特征等几大类。

时间序列的特征工程1

在机器学习领域下,可以使用准确率和召回率来评价一个系统或者一个模型的好坏。在这里,我们可以使用 negative 标签来表示时间序列的异常,使用 positive 标签来表示时间序列的正常。因此模型的召回率准确率F1-Score 可以如下表示:

\text{Recall}=\frac{\text{the number of true anomalous points detected}}{\text{the number of true anomalous points}}=\frac{TN}{TN+FP},

\text{Precision}=\frac{\text{the number of true anomalous points detected}}{\text{the number of anomalous points detected}}=\frac{TN}{TN+FN},

\text{F1-Score} = \frac{2 \cdot \text{precision} \cdot \text{recall}}{\text{precision}+\text{recall}}.

Table1

而时间序列异常检测工作也不是一件容易的事情,通常来说它具有以下几个难点:

  1. 海量时间序列。通常情况下,时间序列不仅仅是按照天来收集数据的,有可能是按照小时,甚至分钟量级来收集数据。因此,在一些情况下,时间序列的数量和长度都是非常大的。
  2. 类别不均衡。一般来说,在时间序列异常检测领域,正常样本是非常多的,异常样本是非常少的。在这种情况下,训练模型的时候通常都会遇到类别不均衡的问题。
  3. 样本不完整。通常来说,时间序列异常检测领域,是需要用人工来标注样本的,这与推荐系统是非常不一样的。这种情况下,很难通过人工标注的方式,来获得所有类型的样本数据。
  4. 特征工程复杂。时间序列有着自己的特点,通过特征工程的方式,确实可以获得不少的特征,但是随着时间序列种类的变多,特征工程将会越来越复杂。

基于以上几个难点,本篇论文提出了一种端到端(End to End)的训练方法,可以解决上面的一些问题。

深度学习的简单回顾

其实最简单的深度学习模型还不是 CNN 和 RNN,最简单的深度学习模型应该是前馈神经网络,也就是所谓的 FNN 模型。当隐藏层的层数较少的时候,当前的前馈神经网络可以称为浅层神经网络;当隐藏层的层数达到一定的数量的时候,当前的前馈神经网络就是所谓的深度前馈神经网络。下面就是一个最简单的前馈神经网络的例子,最左侧是输入层,中间有两个隐藏层,最右侧是输出层。

forwardneuralnetworks1

通常来说,前馈神经网络会涉及到必要的矩阵运算,激活函数的设置等。其中,激活函数的选择有很多,有兴趣的读者可以参见 tensorflow 的官网。比较常见的激活函数有 Sigmoid 函数,tanh 函数,relu 函数以及 relu 函数的各种变种形式(Leaky Relu, PreLu, Elu),以及 Softplus 函数等。

详细来说,以上的激活函数的具体函数表达式如下:

\sigma(x) = 1/(1+e^{-x}),

\tanh(x) = \sinh(x)/\cosh(x),

ReLU(x) = \max\{0,x\},

Leaky \text{ }ReLu(x) = \mathcal{I}_{\{x<0\}}\cdot(\alpha x) + \mathcal{I}_{\{x\geq 0\}}\cdot(x), \alpha\in \mathbb{R},

ELU(x) = \mathcal{I}_{\{x<0\}}\cdot(\alpha(e^{x}-1)) + \mathcal{I}_{\{x\geq 0\}}\cdot(x),

PreLU(x) = \mathcal{I}_{\{x_{j}<0\}}\cdot(a_{j}x_{j})+\mathcal{I}_{\{x_{j}\geq 0\}}(x_{j}),

selu(x) = \lambda\cdot(\mathcal{I}_{\{x<0\}}\cdot(\alpha e^{x}-\alpha) + \mathcal{I}_{\{x\geq 0\}}\cdot x), \lambda,\alpha\in\mathbb{R},

softplus(x) = \ln(1+e^{x}).

 

深度学习与时间序列的特征工程

通常来说,基于人工的时间序列特征工程会比较复杂,不仅需要包括均值方差等内容,还包括各种各样的特征,如统计特征,拟合特征,分类特征等。在这种情况下,随着时间的迁移,特征工程将会变得越来越复杂,并且在预测的时候,时间复杂度也会大量增加。那么有没有办法来解决这个问题呢?答案是肯定的。时间序列的一部分特征可以按照如下表格 Table 2 来表示:其中包括均值,方差等特征,也包括拟合特征和部分分类特征。

Table2.png

基于 Table 2,本篇论文的主要定理陈述如下:

Main Theorem. 对于任意正整数 n\geq 1,存在一个前馈神经网络 D 使得对于所有的时间序列 \boldsymbol{X}_{n}=[x_{1},\cdots,x_{n}],该神经网络的输入和输出分别是 \boldsymbol{X}_{n} 和表格 2 中 \boldsymbol{X}_{n} 的特征层。

下面,我们就来尝试使用深度学习模型来构造出时间序列的统计特征。首先,我们可以从几个简单的统计特征开始构造,那就是加法(add),减法(minus),最大值(max),最小值(min),均值(avg),绝对值(abs)。在构造时间序列 X_{n} = [x_{1},\cdots, x_{n}] 的以上统计特征之前,我们可以先使用神经网络构造出这几种运算方法。

加法 add(x,y) = x+y 与减法 sub(x,y) = x-y 的构造十分简单,如下图构造即可:

绝对值函数 abs(x) = |x|,  通过计算可以得到 abs(x) = relu(x) + relu(-x).  所以,可以构造如下的神经网络来表示绝对值函数:

functionABS

最大值函数 \max(x,y), 通过计算可以得到

\max(x,y) = (|x-y| + x+ y)/2.

所以,只要能够使用前面的神经网络来构造出绝对值模块,然后使用加减法就可以构造出最大值函数。

functionMAX

最小值函数 \min(x,y), 通过计算可以得到

\min(x,y) = (x+y-|x-y|)/2.

所以,同样使用前面的神经网络来构造出绝对值模块,然后使用加减法就可以构造出最小值函数。

functionMIN

在这种情况下,只要能够构造出两个元素的最大值,最小值函数,就可以轻易的构造出 n 个元素的最大最小值函数,因为

\max(x_{1},\cdots,x_{n}) = \max(x_{1},\max(x_{2},\max(x_{3},\cdots,\max(x_{n-1},x_{n}))),

\min(x_{1},\cdots,x_{n}) = \min(x_{1},\min(x_{2},\max(x_{3},\cdots,\min(x_{n-1},x_{n}))).

平均值函数 avg 指的是 avg(x_{1},\cdots, x_{n}) = (x_{1}+\cdots + x_{n})/n.

functionAVG

平方函数 y = x^{2}, 这个函数可以使用 Softplus 激活函数来表达。令 Softplus 为

f(x) = softplus(x) = \ln(1+e^{x}),

通过计算可以得到:

f(0) = \ln(2),

Df(x) = \sigma(x), Df(0) = 1/2,

D^{2}f(x) = \sigma'(x) = \sigma(x)\cdot(1-\sigma(x)), D^{2}f(0) = 1/4,

D^{3}f(x) = \sigma''(x), D^{3}f(0) = 0,

因此,Softplus 函数的 Taylor Series 是:

f(x) = softplus(x) = f(0) + Df(0)x+ \frac{1}{2!}D^{2}f(0)x^{2} + \frac{1}{3!}D^{3}f(0)x^{3}+o(x^{3})

= \ln(2) +\frac{1}{2}x+\frac{1}{8}x^{2}+o(x^{3}),

因此,x^{2} \approx 8\cdot(f(x) - \ln(2)-\frac{1}{2}x) = 8\cdot(\ln(1+e^{x})-\ln(2)-\frac{1}{2}x). y=x^{2} 就可以用神经网络来近似表示:

functionPower2

立方函数 y = x^{3}, 这个函数可以使用 Sigmoid 激活函数来表达。因为 Sigmoid 函数的 Taylor Series 是

\sigma(x) = \frac{1}{2}+\frac{1}{4}x-\frac{1}{48}x^{3}+o(x^{3}),

那么 x^{3} \approx -48\cdot(\sigma(x) - \frac{1}{2} -\frac{1}{4}x). y=x^{3} 就可以用神经网络来近似表示:

functionPower3

深度学习与时间序列的统计特征

提到时间序列的统计特征,一般指的都是已知的时间序列 X_{n} =[x_{1},\cdots,x_{n}] 的最大值,最小值等各种各样的统计指标。如果按照上文所描述的,以下特征都可以用神经网络轻松构造出来:

max:

\max_{1\leq i\leq n}\{x_{1},\cdots,x_{n}\},

min:

\min_{1\leq i\leq n}\{x_{1},\cdots,x_{n}\},

avg:

\mu = \sum_{i=1}^{n}x_{i}/n,

variance:

\sigma^{2}= \sum_{i=1}^{n}(x_{i}-\mu)^{2}/n, \text{ where } \mu = \sum_{i=1}^{n}x_{i}/n,

skewness:

\sum_{i=1}^{n}[(x_{i}-\mu)/\sigma]^{3},

kurtosis:

\sum_{i=1}^{n}[(x_{i}-\mu)/\sigma]^{4},

difference:

x_{2}-x_{1}, x_{3}-x_{2},\cdots, x_{n}-x_{n-1},

integration:

\sum_{i=1}^{n}x_{i},

absolute_sum_of_changes:

E=\sum_{i=1}^{n-1}|x_{i+1}-x_{i}|,

mean_change:

\frac{1}{n}\sum_{i=1}^{n-1}(x_{i+1}-x_{i}) = \frac{1}{n}(x_{n}-x_{1}),

mean_second_derivative_central:

\frac{1}{2n}\sum_{i=1}^{n-2}(x_{i+2}-2x_{i+1}+x_{i}),

除了以上比较容易构造的特征之外,还有一类特征只为了计算个数的,例如 count_above_mean,count_below_mean 分别是为了计算大于均值的元素个数,小于均值的元素个数。那么最重要的就是要构造出计数函数 count。

回顾一下 NOT 逻辑计算门是:

1 \rightarrow 0, 0 \rightarrow 1.

这个逻辑门可以使用逻辑回归函数来估计,可以参见 \sigma 函数的图像,当 x>10 的时候,\sigma(x) \approx 1;x<-10 的时候,\sigma(x)\approx 0. 因此,可以使用函数 f(x) =\sigma(-20x+10) 来估计 NOT 逻辑门。

x=1 时,f(x) = f(1) = \sigma(-10) \approx 0;

x=0 时,f(x) = f(0) = \sigma(10)\approx 1.

下面,我们来考虑如何构造出一个函数来判断待测试值 x 是否大于常数 a.

f_{1}(x) = \sigma(-2\cdot 10^{4} \cdot relu(-x+a) + 10), 可以得到

x>a 时,f_{1}(x) = \sigma(10) \approx 1;

x<a-10^{-3} 时,f_{1}(x) = \sigma(-2\cdot 10^{4}\cdot (a-x) + 10)<\sigma(-10) \approx 0.

因此,所构造的函数 f_{1}(x) 近似于判断待测试值 x 是否大于常数 a.

下面,可以构造一个类似的函数来判断待测试值 x 是否小于常数 a.f_{2}(x) = \sigma(-2\cdot 10^{4} \cdot relu(x-a) + 10), 可以得到

x<a 时,f_{2}(x) = \sigma(10)\approx 1;

x>a+10^{-3} 时,f_{2}(x) = \sigma(-2\cdot 10^{4}\cdot (x-a)+10) < \sigma(-10)\approx 0.

因此,所构造的函数 f_{2}(x) 近似于判断待测试值 x 是否小于常数 a.

回到时间序列的特征 count_above_mean 与 count_below_mean,可以先计算出均值 mean,然后计算时间序列 X_{n}=[x_{1},\cdots,x_{n}] 每个点与均值的差值,然后使用前面的神经网络模块计算出大于零的差值个数与小于零的差值个数即可。

functionCountAboveZero

functionCountBelowZero

深度学习与时间序列的拟合特征

时间序列的拟合特征的基本想法是用一些简单的时间序列算法去拟合数据,然后使用拟合数据和真实数据来形成必要的特征。在这里,我们经常使用的算法包括移动平均算法,带权重的移动平均算法,指数移动平均算法等。下面,我们来看一下如何使用神经网络算法来构造出这几个算法。

移动平均算法

移动平均算法指的是,已知时间序列 X_{n} = [x_{1},\cdots,x_{n}], 我们可以使用一个窗口值 w\geq 1 得到一组光滑后的时间序列,具体来说就是:

SMA_{j}=\sum_{k=1}^{w}x_{j-w+k}/w = (x_{j-w+1}+\cdots+x_{j})/w,

特别地,如果针对时间序列的最后一个点,就可以得到:

SMA_{n} = \sum_{k=1}^{w}x_{n-w+k}/w = (x_{n-w+1}+\cdots+x_{n})/w.

因此,当前的实际值与光滑后所得到的值的差值就可以作为特征,i.e. SMA_{n}-x_{n} 就可以作为一个特征。然后根据不同的窗口长度 w\geq 1 就可以得到不同的特征值。

用和之前类似的方法,我们同样可以构造出一个神经网络算法来得到这个特征。

functionSMA

带权重的移动平均算法

带权重的移动平均算法指的是计算平均值的时候将不同的点带上不同的数值,i.e.

WMA_{j} = \sum_{k=1}^{w}k \cdot x_{j-w+k}/\sum_{k=1}^{w}k.

特别地,如果针对时间序列的最后一个点,就可以得到:

WMA_{n} = \sum_{k=1}^{w}k \cdot x_{n-w+k}/\sum_{k=1}^{w}k.

用和之前类似的方法,我们同样可以构造出一个神经网络算法来得到这个特征。

functionWMA

指数移动平均算法

指数移动平均算法指的是在已知时间序列的基础上进行加权操作,而权重的大小是呈指数衰减的。用公式来描述就是,已知时间序列 X_{n} = [x_{1},\cdots,x_{n}],

EWMA_{1}=x_{1},

EWMA_{j} = \alpha \cdot x_{j-1} + (1-\alpha)\cdot EWMA_{j-1}, \forall j\geq 1.

从定义上可以得到:

EWMA_{n}

= \alpha[x_{n-1}+(1-\alpha)x_{n-2}+\cdots+(1-\alpha)^{k}x_{n-(k+1)}] + (1-\alpha)^{k+1}EWMA_{n-(k+1)}

\approx \alpha[x_{n-1}+(1-\alpha)x_{n-2}+\cdots+(1-\alpha)^{k}x_{n-(k+1)}]

因此,只需要构建一个加权求和,然后计算 EWMA_{n}-x_{n} 的取值就可以得到特征。所以,神经网络可以构建为如下形式:

functionEWMA

深度学习与时间序列的周期性特征

在这里,时间序列的周期性特征就是指当前点与昨天同一个时刻,七天前同一个时刻的差值等指标。可以假设时间序列 X_{n} = [x_{week}, x_{yesterday}, x_{today}] 可以拆分成三个部分 x_{week}, x_{yesterday}, x_{today}, 分别是一周前的数据,昨天的数据,今天的数据,假设它们的长度都是 [n/3],最后一点都表示不同天但是同一个时刻的取值。所以,同环比特征

x_{today}[-1] - x_{yesterday}[-1]x_{today}[-1] - x_{week}[-1] 都是可以通过神经网络构造出来。

mean(x_{today}) - mean(x_{yesterday})mean(x_{today}) - mean(x_{week}) 这一类特征也可以构造出来。

有一些特征时用来计算是否高于历史一段时间的最大值,或者低于历史一段时间的最小值,在这里可以先构造 \max, min 等函数,再计算两者的差值即可。例如,我们可以构造一个特征用于计算当前值是否高过昨天的峰值,以及超出的幅度是多少。用公式来表示那就是:

\max\{x_{today}[-1]-\max\{x_{yesterday}\}, 0\},

如果当前值 x_{today}[-1] 大于昨天的最大值,就返回它高出的幅度;否则就返回0。

也可以构造一个特征用于计算当前值是否低于一周前的最低值,以及低于的幅度是多少。用公式来表示那就是:

\min\{x_{today}[-1]-\min\{x_{week}\},0\},

如果当前值 x_{today}[-1] 小于一周前的最低值,就返回它低于的幅度;否则就返回0。

这两个特征只需要使用神经网络表示出 \max, \min, minus 激活函数使用 ReLU 即可。

深度学习与时间序列的分类特征

在时间序列的分类特征里面,有一种特征叫做值分布特征。假设时间序列的值域在 [0,1] 之内,值分布特征的意思是计算出一个时间序列 X_{n} = [x_{1},\cdots,x_{n}] 的取值在 [0,0.1), [0.1,0.2),\cdots,[0.9,1] 这十个桶的个数,进一步得到它们落入这十个桶的概率是多少。这一类特征可以通过之前所构造的 count 函数来生成。因此,分类特征也是可以通过构造神经网络来形成的。

深度学习与时间序列的特征总结

至此,我们已经证明,对于任意长度 n\geq 1,存在一个神经网络,它的输入和输出分别是原始的时间序列与 Table 2 中的时间序列特征层。整体来看,

1. 存在多个前馈神经网络可以生成时间序列的特征;

2. 深度学习+时间序列异常检测可以实现端到端(End to End)的训练过程,也就是说:输入数据是归一化之后的原始数据(normalized raw data),输出的是两个标签(正常&异常),神经网络的权重可以通过大量数据集和目标函数训练出来。

3. 如果神经网络的输入是归一化之后的 raw data,输出是标签 1 或者 0。此时的前馈神经网络需要至少两个以上的隐藏层,才能够达到较好地提取特征的目的。

基于前馈神经网络的时间序列异常检测算法

通过前面的陈述,我们可以构造一个端到端(End to End)的前馈神经网络,意思就是说:前馈神经网络的输入层是原始的时间序列(归一化之后的数据),前馈神经网络的输出层是标签。

在这里,我们考虑的是三天数据的子序列,以 20180810 的 10:00am 为例,考虑当天历史三小时的数据(07:00-10:00),昨天 20180809 前后三小时的数据(07:00-13:00),再考虑一周前 20180803 前后三小时的数据(07:00-13:00)。这样就形成了一个子序列,总共有 903 个点。然后我们可以使用最大最小归一化获得神经网络的输入数据,而输出数据指的就是最后一个点是异常点(label = 0)还是正常(label = 1)。

Figure4

Table3
Figure5

Figure 5 指出了前馈神经网络的结构图,输入层是归一化之后的时间序列原始数据,中间两层是隐藏层,输出层就是异常或者正常的概率值。而中间层的激活函数可以使用 ReLU 或者 Leaky ReLU,在这里我们通过实验发现 Leaky ReLU 的效果略好于 ReLU。而最后一层的激活函数使用的是 Softmax 函数,输出的两个概率值之和永远都是 1。

在这种神经网络结构下,神经网络的参数量级大约是 10 万量级,在这种情况下,使用少量的几百几千个样本几乎是无法训练出来的。在这里,我们使用了大约 10 万 的样本数据,才得到一个还不错的效果。在这里,我们使用 3-Sigma 算法EWMA 控制图算法多项式回归算法孤立森林算法XGBoost + 特征工程前馈神经网络来进行算法的对比。通过数据的对比可以得到,XGBoost 与 DNN 其实差不多,都能够达到实际使用的上线标准。

Table4Table5

Table6

从深度学习的基础知识可以得到,CNN 的中间层可以用来提取图片的特征,因此,这里的前馈神经网络的隐藏层的输出同样可以作为时间序列的特征层。于是,我们通过实验,基于隐藏层的输出可以作为时间序列的隐藏特征,也就是所谓的 Time Series To Vector。通过 Time Series To Vector,我们可以既可以对时间序列进行聚类(KMeans),也可以对时间序列进行 Cosine 相似度的计算,进而得到同一类时间序列和相似的时间序列。

Figure8Figure9

论文的主要结论

从本文的主要定理和实验效果来看,前馈神经网络是一个非常有效地可以用作时间序列异常检测的工具。本篇论文不仅提供了一个端到端的训练方法,并且不需要对时间序列进行特征工程的操作。从实验数据来看,使用前馈神经网络(feedforward neural network)可以得到与 XGBoost 差不多的效果。并且,前馈神经网络隐藏层的输出可以作为时间序列的隐藏特征(Time Series To Vector),使用 Cosine 相似度或者 KMeans 算法就可以对时间序列进行相似度的计算和聚类操作。在时间序列异常检测领域,使用特征工程 + 有监督算法的方法论比较多,而使用端到端的训练方法,也就是前馈神经网络的方法应该还是相对较少的。因此,端到端的前馈神经网络算法应该是本文的方法与其他方法论的最大不同点。

参考文献

  1. 《企业级 AIOps 实施建议》白皮书-V0.6 版本
  2. 《腾讯运维的AI实践》— 2018年4月 GOPS 全球运维大会
  3. Feedforward Neural Network for Time Series Anomaly Detection》,Arxiv,2018年12月18日
  4. Github:https://github.com/Tencent/Metis

zr9558's Blog