A Primer on the Signature Method in Machine Learning
A Primer on the Signature Method in Machine Learning
Path Signature的基础知识
1、path
path被定义为一个将连续取值区间[a,b]转换到多维空间$R^d$的映射。其最简单的理解就是物体运动的轨迹，假定物体在二维平面上从$t_1$时刻持续运动到$t_2$时刻，每个时刻的位置都可以用一个二维向量表示，这一轨迹就构成了一条path，$X:[t_1,t_2]\to R^2，X_t={X_t^1,X_t^2}$，它的每个维度都表示了物体在对应方向上随时间变化的规律；更一般的path可以被定义为：$X:[a,b]\to R^d，X_t={X_t^1,X_t^2,\cdots,X_t^d},$在实际应用中，我们能够获得的path通常并不是连续的，而是它在取值区间内的不均匀采样，因此我们通常需要进行不同的插值以获得时间上分布均匀且更加密集的path。
2、path integral
path signature实际上是path的不同阶路径积分（path integral）的集合，我们首先来介绍路径积分。假定存在两个一维path：$X_t,Y_t$，且记$X_t^{‘}=\mathrm{d}X_t/\mathrm{d}_t$，则我们定义路径积分为：$\int_a^bY_tX_t^{‘}\mathrm{d}t=\int_a^bY_t\mathrm{d}X_t$，其意义就是在参变量由a变换至b时$Y_t$对$X_t$的积分，这一形式的路径积分是后续所有阶路径积分的基础。
path signature有两个重要的性质：
平移不变性。我们对路径X进行平移之后，并不会对路径积分产生任何的影响，数学描述如下：
$$
\int_a^bY_t\mathrm{d}X_t=\int_a^bY_t\mathrm{d}Z_t,Z_t=X_t+c
$$重参数不变性。路径积分的结果只和$X_t,Y_t$的相对关系有关，与参变量t无关。
$$
\int_a^bY_t\mathrm{d}X_t=\int_{k_1a}^{k_2b}Y_r\mathrm{d}X_r
$$
其中
$$
Y_t(X_t)=Y_r(X_r),X_t(a)=X_r(k_1a),X_t(b)=X_r(k_2b)
$$
对于一条多维path：$X:[a,b]\to R^d$，首先我们给出其一阶path integral的表达式为：
$$
S(X)^n_{a,t}=\int_a^t\mathrm{d}X_c^n,t\in[a,b]
$$
其中 $Y_t=1,X_t=X_c^n,X_c^n$ 表示路径X的第n个维度在c时刻的取值。对于一个d维的path，其一阶path signature有d个。由于一阶path signature的积分上限是变化的t，而非定值b，所以实际上$S(X) _ {a,t}^n$也是一个一维path:$X^{‘}:[a,b]\to R^d,X_t^{‘}={S(X) _ {a,t}^n}$，因此我们可以对它再次求取路径积分得到了二阶path integral：
$$
S(X) _ {a,t}^{n,m}=\int_a^tS(X) _ {a,c}^n\mathrm{d}X_c^m=\int_a^t\int_a^c\mathrm{d}X_s^n\mathrm{d}X_c^m
$$
显然，二阶PS特征有 $d^2$ 个。以此类推，我们可以得到k阶path integral：
$$
S(X) _ {a,t}^{i_1,\cdots,i_k}=\int_{a<t_k<t}\cdots\int_{a<t_1<t_2}\mathrm{d}X_{t_1}^{i_1}\cdots\mathrm{d}X_{t_k}^{i_k}
$$
3、path signature
总的来说path signature（路径签名）是一种从数据中提取属性特征的非参数方法，它捕获了路径的许多重要的解析和几何属性。这种方法通常首先使用多种嵌入算法将数据转化成多维路径，然后去计算总结了数据中包含信息的签名的单个项。因此，一句话进行总结：签名方法就是将原始数据转换为一组用于机器学习任务的特征的方法。
一条路径X的签名，被记为$S(X) _ {a,b}$，是路径X的所有阶路径积分的集合，它被定义为：
$$
Sig(X) _ {a,b}=(1,S(X) _ {a,b}^1,\cdots,S(X) _ {a,b}^d,S(X) _ {a,b}^{1,1},\cdots,S(X) _ {a,b}^{d,d},\cdots)
$$
4、path signature的动机——Picard 迭代
签名方法自然诞生于常微分方程领域，其基石是Picard方法。对于一个一阶常微分方程：
$$
\frac{dy}{dx}=f(x,y), y(x_0)=y_0
$$
Picard方法允许我们用迭代级数的方式来构造该方程的近似解，该方程的积分形式变为：
$$
y(x)=y(x_0)+\int_{x_0}^xf(t,y(t))dt
$$
如果我们定义一系列的函数$y_k(x)$，其中第一项是常数函数$y_0(x)=y(x_0)$，那么我们可以归纳地定义
$$
y_k(x)=y(x_0)+\int_{x_0}^{x}f(t,y_{k-1}(t))dt
$$
Picard定理表明，在适当的条件下，该微分方程的解由$y(x)=\lim_{k\to\infty}y_k(x)$给出。
更一般的，对于$Y_t=y+\int_a^tV(Y_s)dX_s$，可以将整个Picard迭代写为如下过程：
容易发现上图中的式子中包含了我们之前提到的多阶路径积分，这便促使Terry Lyons提出了路径签名，签名中包含了所有的高阶路径积分，可以用于计算微分方程的近似解。
5、signature的重要属性
唯一性：任意一个非树状路径均可被其PS唯一确定。
平移不变性、旋转不变性：PS与路径的起始位置点无关；某些阶的PS及其组合具有旋转不变性。
在时间重参数化下的不变性、在不同时间跨度下的不变性：对采样率、丢失采样点、添加随机噪声等不太敏感。
洗牌乘积等效性：使用PS作为特征时，签名中两个低阶项的乘积可以用高阶项的线性组合等效表示，即两个路径积分$S(X) _ {a,b}^{i_1,\cdots,i_k}$和$S(X) _ {a,b}^{j_1,\cdots,j_m}$的乘积可以被路径签名$S(X) _ {a,b}$的高阶项的某个集合之和表示。
证明（以式子1为例）：
$$
\begin{aligned}
左式&=S(X) _ {a,b}^1S(X) _ {a,b}^2\\&=\int_a^bdX_t^1\int_a^bdX_t^2\\&=(X_b^1-X_a^1)(X_b^2-X_a^2)\\&=X_b^1X_b^2+X_a^1X_a^2-X_a^1X_b^2-X_b^1X_a^2
\end{aligned}
$$$$
\begin{aligned}
右式&=S(X) _ {a,b}^{1,2}+S(X) _ {a,b}^{2,1}\\&=\int_a^b\int_a^{t_2}dX_{t_1}^1dX_{t_2}^2+\int_a^b\int_a^{t_2}dX_{t_1}^2dX_{t_2}^1\\&=\int_a^b(X_{t_2}^1-X_a^1)dX_{t_2}^2+\int_a^b(X_{t_2}^2-X_a^2)dX_{t_2}^1\\&=\int_a^bX_{t_2}^1dX_{t_2}^2+\int_a^bX_{t_2}^2dX_{t_2}^1-X_a^1(X_b^2-X_a^2)-X_a^2(X_b^1-X_a^1)\\&=X_t^1X_t^2|_a^b-X_a^1X_b^2+X_a^1X_a^2-X_a^2X_b^1+X_a^2X_a^1\\&=X_b^1X_b^2+X_a^1X_a^2-X_a^1X_b^2-X_b^1X_a^2
\end{aligned}
$$显然，左式=右式，命题证毕。
陈氏恒等式
首先定义符号$\otimes$有如下含义：
$$
e_{i_1}\cdots e_{i_k}\otimes e_{j_1}\cdots e_{j_m}=e_{i_1}\cdots e_{i_k}e_{j_1}\cdots e_{j_m}
$$
在形式幂级数中有（注意：这里的e是formal indeterminates，是一种不定项，可以理解为C中的占位符）：
$$
(\sum_{k=0}^\infty\sum_{i_1,\cdots,i_k\in{1,\cdots,d} }\lambda_{i_1,\cdots,i_k}e_{i_1}\cdots e_{i_k})\otimes(\sum_{k=0}^\infty\sum_{i_1,\cdots,i_k\in{1,\cdots,d} }\mu_{i_1,\cdots,i_k}e_{i_1}\cdots e_{i_k})\\=\lambda_0\mu_0+\sum_{i=1}^d(\lambda_0\mu_i+\lambda_i\mu_0)e_i+\sum_{i,j=1}^d(\lambda_0\mu_{i,j}+\lambda_i\mu_j+\lambda_{i,j}\mu_0)e_ie_j+\cdots
$$
基于此，路径X的签名可以使用形式幂级数来进行表示：
$$
Sig(X) _ {a,b}=\sum _ {k=0}^\infty \sum _ {i_1,\cdots,i_k\in{1,\cdots,d} }S(X) _ {a,b}^{i_1,\cdots,i_k}e_{i_1}\cdots e_{i_k}
$$于是两条路径$X:[a,b]\to R^d$和$Y:[b,c]\to R^d$的拼接$ X \ast Y $的路径签名可以转换成$ \otimes $形式：
$$
Sig(X \ast Y) _ {a,c}=Sig(X) _ {a,b} \otimes Sig(Y) _ {b,c}
$$时间翻转
路径X的签名是反向运行X得到的签名的$\otimes$的倒数。
定义路径$X:[a,b]\to R^d$的时间反转为路径$\mathop{X}\limits^{\gets}:[a,b]\to R^d$，其中$\mathop{X_t}\limits^{\gets}=X_{a+b-t},t\in[a,b]$。则有：
$$
Sig(X) _ {a,b}\otimes Sig(\mathop{X}\limits^{\gets}) _ {a,b}=1
$$对数签名
对数签名是路径签名的一种变换，本质上是形式幂级数的形式对数。对于如下的形式幂级数：
$$
x=\sum_{k=0}^\infty\sum_{i_1,\cdots,i_k\in{1,\cdots,d} }\lambda_{i_1,\cdots,i_k}e_{i_1}\cdots e_{i_k}
$$
其对数形式被定义为：
$$
log(x)=log(\lambda_0)+\sum_{n\ge 1}\frac{(-1)^n}{n}(1-\frac{x}{\lambda_0})^{\otimes n}
$$
其中$\otimes n$表示关于该乘积的n次幂。类似的，路径X的对数签名的形式幂级数定义为：
$$
logSig(X) _ {a,b}=\sum_{i=1}^dS(X) _ {a,b}^ie_i+\sum_{1\le i<j\le d}\frac{1}{2}(S(X) _ {a,b}^{i,j}-S(X) _ {a,b}^{j,i})[e_i,e_j]+\cdots
$$
其中$[x,y]=x\otimes y-y\otimes x$。
Path Signature的实际应用
签名变换的实际应用之一是机器学习算法。正如之前所述，路径签名总结了关于路径的重要信息。当路径由一个顺序的数据流${Xi}$组成时，其签名$S(X)^{ijk\cdots}$的项是数据流的特征的极佳候选项。洗牌积性质允许我们将签名中低阶项的非线性函数表示为签名中高阶项的线性组合。这类似于基函数扩充，自然适用于回归模型的计算。下面就介绍一些具体的例子：
1、二阶路径签名及二阶对数签名的例子：
$$
X_i^1={1,3,5,8}\\X_i^2={1,4,2,6}\\t_i={0,1,2,3}
$$
则其二阶路径签名及二阶对数签名为：
$$
\begin{aligned}
Sig(X)&=(1,S^{(1)},S^{(2)},S^{(1,1)},S^{(1,2)},S^{(2,1)},S^{(2,2)})\\&=(1,7,5,24.5,19,16,12.5)\\log Sig(X)&=(S^{(1)},S^{(2)},S^{[1,2]})=(7,5,1.5)\\其中S^{[1,2]}&=\frac{1}{2}(S^{(1,2)}-S^{(2,1)})
\end{aligned}
$$
以$S^{(1,1)}$为例：
$$
\begin{aligned}
S^{(1,1)}&=\int_0^3\int_0^tdX_s^1dX_t^1\\&=\int_0^3(X_t^1-1)dX_t^1\\&=\frac{(X_t^1)^2}{2}-X_t^1|_0^3\\&=(32-8)-(0.5-1)\\&=24.5
\end{aligned}
$$
2、路径所围绕区域的面积和方向
对于$S^{(1,2)}$，内层积分是横坐标，外层积分是纵坐标，因此是左图；对于$S^{(2,1)}$内层积分是纵坐标，外层积分是横坐标，因此是右图。
可以使用右手螺旋定则判定方向。
3、签名方法在机器学习中的应用
比如用于时间序列分析、处理时间序列中的缺失值等。
4、近年来的一些进展
从财务数据流的签名中提取信息
使用基于粗糙路径的方法对声音进行压缩
数字识别
在图像识别任务中，路径是几何对象的一个很好的候选。比如在手写数字识别任务中，可以将数字看做是连续的路径，然后签名方法就成为了解决分类问题的一个自然的方法。将签名方法和深度神经网络相结合的方法，在ICDAR2013汉字识别大赛中达到了0.9553的准确率。
从过去进行学习，预测未来的统计数据，学习一个不断发展的系统
MEG扫描中的模式识别
学习治疗对双向情感障碍患者行为模式的影响