序列间距离测度的优化及应用

1049序列匹配丙素1，港华21中国科学院软件研究所集成信息系统科学技术重点实验室北京100190 2微软研究院{subingats，ganghua} @ gmail.com摘要提出了一种新的序列间距离测度，该测度可以处理局部时间失真和任意起始点的周期序列。通过将序列的实例看作未知分布的经验样本，我们将序列间距离的计算转化为最优传输问题。为了保留序列中实例的内在时间关系，我们使用两个新的时间正则化项来平滑最优运输问题逆差分矩正则化强制局部均匀结构的传输，并且具有先验分布正则化的KL-发散防止具有远时间位置的实例之间的传输。我们表明，这个问题可以有效地优化，通过mak-scaling算法。 在不同分类器下的多数据集上的实验表明，该距离优于传统的DTW变量和没有时间正则化的平滑最优传输距离。1. 介绍有效地测量序列之间的距离在广泛的序列模式分析问题中起着基础性的作用由于序列数据的固有复杂性，定义序列的距离度量可能比定义向量的距离度量困难得多。首先，不同序列中实例的进化速度可能会有很大差异。例如，不同的主体可以以不同的速度执行相同的动作。不同序列的采样率也可以不同。因此，尽管序列中的实例具有固定的维度，但是不同的序列通常具有不同数量的实例。因此，传统的向量距离度量，如欧几里德距离，Lp范数，和Maha-lanobis距离不能直接应用于序列。其次，序列中实例的演化是（一）（b）第（1）款（c）第（1）款图1.同一联机字的两个笔画序列在前三位和后三位的局部顺序不同。(a)由DTW生成的对准受到这种局部或- der反转的干扰(b)如果只考虑笔划形状，Sinkhorn（平滑OT）会对齐出现在不同时间位置的相同笔划（c）所提出的（b）和（c）中所示的对齐是与学习的OT中的第二序列的实例相关联的最大传输不是统一的。例如，当执行“踢球”的相同动作时因此，不同序列的实例在同一节奏-1050每个位置可以对应于不同的姿态。因此，在比较不同序列时，时间比对是必要的。此外，描述相同模式的序列中的实例的局部时间排序也可以变化。我们在图中显示了一个例子。第1（a）段。正确的笔画顺序写的汉字显示在顶部。这个字符的一个非常常见的错误笔画顺序显示在底部，其中点的顺序在开始和接近结束时颠倒。这意味着可以不对对齐施加严格的等级保持。第三，同一序列中的实例不是独立的样本，而是时间相关的。例如，如果不考虑帧的顺序，由同一个人执行的两个动作“站起来”和“坐下”就不能区分。这防止了集合、分布或袋之间的距离的应用，例如Jaccard指数、Brackoff距离[11，28]和KL分歧[15]。最后但并非最不重要的是，对于周期性模式或事件，不同的序列样本可以从不同的实例开始。例如，如图2所示。2、都执行动作“慢跑”，一个人可以从抬起左腿同时伸展右臂开始，另一个人可以从抬起右腿同时伸展左臂开始。不同序列的起点（终点）不能强制对齐，需要灵活对齐。已经做出了很多努力来找到可以解决这些问题的序列之间的有意义的距离度量。动态时间规整（DTW）[22]可能是最广泛采用的。DTW能够比对具有不同长度、速度和非均匀性的序列。然而，DTW确定的对齐严格保持顺序，即。，在一个序列中的实例在前一步骤中对齐之前，不允许该实例与另一序列中的实例对齐。如图1、当存在局部反转或时间失真时，错误对准不可避免，这也影响其他规则对准。DTW的边界条件要求两个序列的起点和终点对齐。这将导致具有不同起始点的周期性序列的错误对齐，如图12所示。第2段（a）分段。通过将序列中的实例视为来自概率分布或一组向量点的经验样本，最优传输（OT）[31]或其平滑且计算有效的版本，Sinkhorn距离[9]，提供了一种自动提升实例之间的几何形状以定义两个序列的距离度量的规范方法，其具有许多优秀的属性，例如存在性，最优映射的性质、可分性和完备性。学习的传输自然地定义了两个集合之间的灵活对齐。通常，最优传输仅将大权重分配给最相似的实例对。（一）（b）第（1）款（c）第（1）款图2.“慢跑”动作的两个周期序列从不同的右臂在顶部顺序中首先被举起，而左臂在底部顺序中首先被举起（a）由于时间上的严格限制，戴德梁行引入了偏差。(b)Sinkhorn对齐表示最相似姿势的帧，即使两个帧的相对时间位置因此，在路线中经常出现长连接线。一个序列的前几个帧与另一个序列的后帧在完整的周期性循环中对齐。(c)所提出的OPW将一个序列中的每个帧与另一个序列中具有相同姿态的时间相邻周期的帧对齐。生成的路线显示周期性线段。OT虽然能够解决局部秩反转和不同起点的问题，但它完全忽略了实例固有的时间依赖性如图1（b）所示，如果只考虑形状特征，则右部的两个点大部分被传输到左部的点。在图中，姿势主要是在遥远的循环中被传送到最相似的姿势。第2段（b）分段。为了结合最优传输和保序比对的灵活性的优点，我们通过对最优传输施加时间约束，发展了一种新的序列间距离度量，即保序Wasserstein（OPW）距离.由此产生的met-ric继承了OT的一些优秀的属性，同时捕捉一般的时间顺序的实例，导致灵活的时间敏感的对齐。如图1（c）和图2（c），所提出的距离测量可以适当地解决DTW和OT存在问题的这些问题。本文的主要贡献概括如下：1.我们采用最优传输作为序列之间距离测量的基础，这具有许多前1051×→······∈×+N N MM······良好的数学特性，对局部秩逆和不同起点的周期模式具有鲁棒性2. 我们提出了两种新的时间正则化，以双关语传输或具有遥远时间位置的实例之间的对齐，使得学习的最佳传输能够保持序列中实例的时间依赖性; 3.我们证明了正则化OT问题可以通过Sinkhorn的矩阵缩放算法有效地解决我们的经验表明，建议的OPW距离优于DTW和Sinkhorn距离不同的任务与不同的分类。2. 相关工作序列距离测度的研究主要集中在改进DTW上。在[19]中，局部约束用于约束翘曲量。开发了各种方法来加速DTW的计算，例如FastDTW [23]和SparseDTW[1]，或者加速所有成对DTW矩阵的计算[25]。最初，最长公共子序列（LCSS）距离[6]和编辑距离[18]旨在比较最近，最优运输受到越来越多的关注，例如快速计算[9，4]，计算重心的应用[10]，PCA的生成[24]和损失定义[13]。据我们所知，我们是第一个适应OT作为序列的相似性度量。3. 最佳运输最优运输[31]，也称为Wasserstein距离，测量度量空间上两个概率分布之间的差异。直观地说，如果每个分布被视为在空间上堆积单位量的污垢的方式，则Wasserstein距离是将一个分布的堆运输到另一个分布的堆中的最小成本。因此，瓦瑟斯坦距离也被称为地球移动器形式上，给定一个完备可分度量空间（d，d），其中d： R是s-空间上的度量，设P（k）表示k上所有Borel概率测度的集合。给定两个样本点集X=（x1，· · ·，xN）和Y=（y1，，yM），可以估计它们相应的经验概率测度字符串序列。一些努力[32，17]试图将它们扩展到处理连续多维序列，为f= ∑Ni=1αiδxi ∈P（n）且g=∑Mj=1βjδyj ∈P（n），re-并产生类似DTW的算法。 经典时间扭曲ing [36]和广义时间规整[35]扩展了DTW以处理其实例可能具有不同维度的多模态序列。这些方法通常是基于DTW的，并且遭受DTW的类似问题。在[20]中，通过映射其中δx是x在π中位置上的狄拉克单位质量，N和M分别是两个集合X和Y中的点数。αi是xi上单位质量的重量。由于f是一个概率分布，相应的权向量α=（α1，· · ·，αN）位于单形原始序列到学习的半连续HM-提取状态的混合权向量。的ΘN：={α∈RN|αi≥ 0, ∀i = 1,···, N,∑Ni=1 αi= 1}。原始序列之间的距离定义为DTW序列之间的权值距离。在[27，29]中，从每个序列集合中提取基于HMM的统计量统计量之间的DTW距离被用作序列或序列类集合之间的距离度量。这些方法也是基于DTW的，并且需要对HMM进行预训练。在[30]中，基于传输平方根向量场，类似地，β=（β1，βM）ΘM。在没有关于样本的任何先验知识的情况下，可以将点视为从每个分布均匀采样，并且可以分别将权重估计为α=（1，，1）和β=（1，，1）（X，Y）的经验联合概率测度可以估计为：表示，率不变的距离推导出的投射，这是进一步应用于动作识别∑N ∑Mh=γij（δxi，δyj），（1）在[3]中。类似于DTW，该距离也是严格保序的。相比之下，本文提出的方法允许局部重排序，可以处理局部时间不规则演化和离群帧，同时不影响不同类别序列的区分。通常，用于学习比对的方法，例如[34，14]不仅需要使用地面实况比对或类别标签的监督学习在本文中，我们开发了一个无监督的距离测量的任何类型的序列。任何两个序列之间的距离可以直接计算，而无需来自其他序列的监督或无监督训练。i=1j=1其边际测度w.r.t. X和Y各自为f和g。因此，权重矩阵[γij]ij是NM非负矩阵，行和列边缘分别为α和β。所有可行权矩阵的集合被定义为α和β的运输多面体U（α，β）：U（α，β）：={T∈RN×M|T1M=α，TT1N=β}。（ 二）一个可行T的元素t ij可以被看作是从xi到yj的质量转移量。xi和yj之间的距离由度量d提升到1052p···Nλ1···2M）NNMMX不⟨ ⟩ ⟨⟩pT ∈U（α，β）鲍尔山口X中元素之间的所有成对距离和Y被存储在矩阵D中，即，、D：=[d（xi，yj）p]ij∈RN×M.（3）给定运输T，将f运输到g的成本为：T，D，其中T，D=tr（T D）是Frobenius点积。经验概率测度f和g之间的p次Wasserstein距离可以公式化为：Wp （ f ， g ） =dW （ α ， β ， D ） =minDallas，Dallas（4）其中Wp（f，g）是α，β和D的函数，因此也可以写为dW（α，β，D）。在本文中，我们只考虑p= 1，为了简单起见，在下文中省略p在计算上，要得到（4）的最优解是相当昂贵的. 最近，Cuturi [9]提出在运输多面体上增加一个熵约束，这是一个熵正则化的最优运输问题，从而得到Sinkhorn距离，即、Y中的元素y1，，yM，但是这些元素的顺序关系被完全忽略。如图1（b）和图。2（b），一个序列的第一个实例可以被匹配（传输）到另一个序列的倒数第二个实例。因此，Wasserstein距离只能度量元素空间分布的差异，而不能区分元素的时间如果两个序列只是元素的顺序不同，那么Wasserstein距离和Sinkhorn距离都不能将它们分开。为了考虑到固有的时间信息，期望一个序列的一个时间位置中的样本只能被传输到另一个序列的附近时间位置中的元件也就是说，两个序列中具有相对较远时间顺序的元素不能匹配。我们用i来度量元素xi在序列X中的相对时间顺序或位置。回想一下，N是序列X的长度。X中所有元素的所有增加的相对时间位置形成与序列X相关联的顺序先验序列OX，即， 、λ⟨λ⟩dS（α，β，D）=T，DO=[1，2，···，N −1，1]。S.T. T λ= arg min <$T，D<$− 1 h（T），（5）N N n∑N其中h（T）=−T ∈U（α，β）∑Mtijlogtij是T的熵。的如果一个序列中的元素被传输到另一个序列中具有相似相对时间位置的那些元素中，则传输矩阵T应显示局部同态，i=1j =1最小化（5）的最优Tλ具有简单形式，即、Tλ=diag（κ1）e−λDdiag（κ2），（6）其中e−λD是矩阵的元素指数异质结构也就是说，大值出现在T的对角线附近的区域，而T的其他区域的值为零或非常小。测量这种局部同质性的输运矩阵T的逆差矩[2−λD，κ1∈RN和κ2∈RM是非负左它是：∑N ∑M以及直到乘以因子为止唯一的右缩放向量。κ和κ可以通过下式有效地确定：I（T）=tij、（8）（i−jSinkhorns不动点迭代因此，与原问题（4）相比，计算复杂性大大降低4. 保序Wasserstein距离其中，如果运输T的大值主要沿对角线分布，则I（T）将具有大值理想地，最大化I（T）w.r.t. T在U（α，β）上没有任何其他约束将导致一个矩阵，其非零值仅出现在i=j的位置。鼓励N M给定两个序列X= [x1，· · ·，xN]和Y=[y1，，yM]，Wasserstein距离可以通过将每个序列中的元素视为独立样本来应用为它们之间的距离度量，即，、为了匹配时间上接近的元素，倾斜T的逆差矩I（T）应该尽可能大。T中的值的一般理想分布是峰值出现在对角线上，并且值沿垂直于对角线的方向逐渐减小这dO（X，Y）= minT ∈U（α，β） 住宿加早餐旅馆（7）可以通过二维分布来建模，其边缘分布沿着垂直于二维分布的任何线在这种情况下，每个序列被视为一组点独立于分布采样，因此α=（1，···，1）和β=（1，···，1）。瓦瑟斯坦一家-偏角是以对角线上的交点为中心的高斯分布，即、tance度量运输分布的最小成本-1−2（i，j）i=1j=1N+1σ2π210531元素x，···，x的作用在X中的分布pij：=P（i，j）=√e2σ2，（9）N1054O⟨⟩−||pij）+11普雷特2+NM不-λ0.8我们将保序Wasserstein（OPW）距离定义为两个序列X和Y之间的距离度量，0.6dO（X，Y）=minD. D.（十一）0.42001年，2002年T∈U 2001年，2002年（α，β）0.208从建模的角度来看，该公式类似于最大化T的逆差矩，最小化T和先验P的KL发散，同时要求约束运输成本。由于仅具有相似相对位置的元素优选被匹配，因此两个序列的排序关系如下：图3.传输矩阵的先验分布。其中，f（i，j）是从位置（i，j）到对角线的距离，即，、（i，j）=|i/N − j/M|.1/N2 + 1/M2在计算距离时保留。此外，类似于熵平滑Wasserstein距离，附加约束大大降低了计算最优传输的计算复杂度。本文通过引入两个Lagrange乘子来考虑对偶保序Wasserstein距离，即逆差矩约束和KL-发散约束。，λ1>0和λ2>0：我们使用等式（9）作为值的先验分布，dλ1，λ2（X，Y）：=⟨λ1，λ2，DT，如图所示。3.第三章。如可以观察到的，一个序列中的一个元素在时间顺序方面离另一个序列中的另一个元素越远，它被传输到该元素的可能性就越小 由于T中的值可以被视为代表运输的比例S.T. T λ1，λ2 =arg min T，Dλ1I（T）+λ2KL（TP）T ∈U（α，β）（十二）根据对偶理论，对于等式（11）中的每个对λ1，λ2，存在对应的对λ1>0，λ2>0，使得dλ1，λ2（X，Y）=dO（X，Y）将序列的一个时间位置中的堆放置到另一个序列中的相应时间位置，学习T中的值的分布和先验分布应该尽可能地相似，以鼓励平滑和合理的分配或运输。O2001，2002对（X，Y）。 这两个约束可以看作是正则化项（12）。Tλ1，λ2表示等式中约束的最优传输矩阵（12），即它优化了为了鼓励不同顺序的元素，相似的时间位置被匹配，min∈RN×M+λT，Dλ − λ1I（T）+ λ2KL（T ||P）.（十三）这样的匹配是光滑的，我们通过对集合U（α，β）施加两个附加约束来引入传输矩阵T的以下可行集合：U∈ R，N（α，β）={T∈RN×M|T1M= α，S.T. T 1M= α，T T1N= β由于（13）中的目标集和可行集都是凸的，所以最优Tλ1，λ2存在且唯一。为了获得最佳Tλ1、λ2，我们从方程（13）TT1N= β，I（T）≥ λ1，KL（T||P）≤ 100}∑N ∑M∑N ∑ML（T，μ，ν）=（dijtijtij1（i−j2）+1其中KL（T||P）=不logtij是库尔贝克人i=1 j=1NMIJi=1j =1pij+λ2tijlogtij）+μT（T1M−α）+νT（TT1N−β）两个矩阵之间的Leibler（KL）散度这意味传输矩阵T是可行的，只有当它的逆差矩被约束为位于预定义的阈值以上，而T和先验矩阵之间的KL发散（十四）其中μ和ν分别是两个等式约束T1M=α和TT1N=β的对偶变量L（T，μ，ν）的导数w.r.t.对于一对（i，j），tij是分布P不能超过另一个预定义的阈值。因此，两个序列中的元素具有非常L（T，µ，ν）tij=dij−λ1（i−j2+λ2logTIJPIJ.（十五）不同的时间位置不太可能被匹配两个序列中元素的输运比例均随其温度的升高而减小+λ2+μi+νj将WTL（T，µ，ν）设为零，我们得到：IJ根据高斯函数计算的孔隙距离。 可以6846422不、（10）101055-1−µi1（sλ1−d）−1−νj很容易观察到，U，（α，β）是一个凸集。tij=pije2λ2eλ2ijije2λ2，（16）1 21056∈∈不其中sλ1=λ1。我们表示K=ij（i−j21（sλ1−d）NM）+1-1−µi-1−νj[pijeλ2IjIj ]ij，则tij=e2λ2Kije2λ2，以及Tλ1，λ2=ediag（−1−µ）2λ2diag（−1−ν）2λ2K的所有元素都是严格幂次的，因为eS是矩阵S的元素指数。根据Sinkhorn定理（定理1），存在具有严格正对角元的对角矩阵diag（κ 1）和diag（κ 2），diag（κ1）Kdiag（κ2）是唯一的，并且两个对角矩阵也是唯一的，直到一个标量因子。定理1. [26，7，8]：对任意N×M矩阵A，存在对角矩阵B1和B2，使得B1AB2属于U（α，β）。B1和B2具有严格的正对角值，并且在正标量因子下是唯一的。最佳Tλ1，λ2的方程。U（α，β）中的矩阵（13）与diag（κ1）Kdiag（κ2）具有相同的形式，因此恰好是U（α，β）中唯一的矩阵，它是K的重标度版本。κ1和κ2是唯一的非负左和右缩放向量，直到缩放因子。因此，它们可以通过Sinkhorn-Knopp迭代矩阵缩放算法有效地获得：κ1← α./ Kκ2，（17）κ2←β./ （K）κ1。（18）本文只使用了20次迭代，因为一个小-Sinkhorn算法的固定迭代次数计算OPW距离的复杂度为O（d′NM），其中d′是序列X和Y中向量的维数。 OPW避免了内点法等优化方法求解传统最优运输问题的计算量大的缺点。5. 实验5.1. 数据集MSR Sports 3D数据集[16]。该数据集由来自20个运动动作的402个深度动作序列组成。10名受试者执行每个动作三次。这些序列总共包含23，797帧。在[33，34]之后，根据受试者将数据集分为训练集和测试集，其中十个受试者中的一半执行的动作序列用于训练，其余序列用于测试。MSR Daily Activity3D数据集[33]。该数据集包含来自16种活动类型的320个日常活动序列。一般来说，十个受试者在生活中执行每一项活动房间有两种姿势：“坐在沙发上”和“站着”。当图4.类似的网络汉字样本。“sitting on sofa” or the subject stands close to the sofa, the3D大多数活动都涉及人与物体的相互作用。根据[33，34]中的实验设置，将数据集分为训练集和测试集。“Spoken Arabic Digits (SAD)” dataset from the U-CI Machine Learning Repository [ 该数据集包含来自10个阿拉伯语数字的8，800个矢量序列序列中的向量是从语音信号中提取的梅尔倒谱系数（MFCC）特征。每个数字类有880个序列样本，由44名男性和44名女性阿拉伯语母语者讲十次。数据集被分成训练集和测试集。每个类的660个样本用于训练，其余的用于测试。联机汉字数据集。 我们选择一从收集的数据集中收集一组相似的在线中文字符[29]。该集合由共用相同或相似偏旁的12个相似字符组成。107个人写一次每个实例和相应的GBK代码这些特征如图所示4.第一章我们将每个字符的样本分为五个子集，进行五重交叉验证。5.2. 实验装置全帧功能。对于RISK 3D数据集和Activity3D数据集，每个动作样本都由一系列帧范围的特征表示。我们分别采用[34]和[33]的作者提供的特征。这些特征是结构件中所有3D关节的相对位置对于RISK 3D数据集和Activity3D数据集，帧范围特征的维数分别为192和390。在SAD数据集中，每个数字样本由13维MFCC特征序列表示对于相似字符集，我们从字符样本的每个笔画中提取10个特征.这些特征包括位置、形状、方向、相关性和角点。分类方法和评价措施。采用了两种基于距离的分类器：最近均值（NM）分类器和k以执行分类。对于NM，柯.1057757065605550450 24（一）6 8 10σ85807570656055500 2 4（b）第（1）款6 8 10σ(a) NM分类器图5.（a）NM分类器;（b）NN分类器。计算每个类中的所有成对序列。与同一类中所有其他序列的距离之和最小的序列被确定为该类的均值。对于一个测试序列，它到一个类的均值序列的距离被用作它和类之间的相异性。具有最小相异度的类被确定为测试序列的标签。准确度和平均精密度（MAP）被用作评价措施。对于k-NN，计算测试序列与所有训练序列之间的距离。测试序列通过其k个最近邻的分别取k=1，3，5，15，以精度作为评价指标。当k= 1时，测试序列也被视为检索训练序列的查询，并且计算MAP。5.3. 参数影响建议的OPW距离有三个参数：先验分布的标准偏差σ控制翘曲的期望带宽，λ1控制逆差矩正则化的权重，λ2控制正则化在KL-发散与先验分布方面的平衡。我们首先评估NM和NN分类器在MSR 3D数据集上随着σλ1和λ2固定为50和0。1所示。结果示于图五、我们可以发现，对于不同的评价方法和分类器，σ的最优值是不同的。但一般来说，当σ >5时，精度下降，因为大的σ意味着允许在较远的相对时间位置之间传输，因此丢失了更多的时间信息。然后，我们固定σ为1，并评估OPW的性能与不同的λ1和λ2。当改变λ2（λ1）时，λ1（λ2）固定为50（0.①的人。结果示于图六、当λ1>1时，OPW对λ1不太敏感。大λ2会降低性能，因为先验距离用于限制时间灵活性的宽度，并且学习的传输不应该太接近它。当λ1>500，λ2≤0时，出现突变。01是（b）NN分类器表1. MSR Sports 3D数据集上的结果。所有距离测量中的最佳结果以红色显示，第二位置结果以蓝色显示。方法DTWlDTWnDTW Sinkhorn OPW精度地图40.6333.2533.7537.4738.7531.3737.5032.1438.7533.35(a) NM分类器距离DTWlDTWnDTW Sinkhorn OPW地图33.7928.8130.5630.6634.621-NN58.7550.0055.6354.3758.133-NN50.6243.7547.5048.1350.625-邻硝基甲苯49.3850.0052.5050.6253.7515-NN43.1338.7540.0041.2544.37(b) NN分类器表2.MSR Daily Activity3D数据集。因为K的某些条目超过了机器精度限制。5.4. 不同距离测量的比较我们比较了NM和NN分类器的性能，通过使用不同的序列之间的距离措施。四个数据集的结果显示在选项卡中。1到Tab。4，分别。lDTW和nDTW分别是通过测试序列的长度和匹配步骤归一化对于Sinkhorn距离和建议的OPW距离，使用最佳参数报告结果。我们可以发现，建议OPW距离优于- s最广泛采用的DTW距离及其变体，以及Sinkhorn距离，在大多数数据集上具有不同的分类器和评估措施。在OPW的性能不是最佳的情况下，通过不同的距离获得最佳结果，OPW实现非常接近最佳结果的第二最佳结果。在四个数据集中的三个数据集上，OPW实现了最高的准确率，并且在所有分类器中实现了MAP。在部分-准确性映射准确度、1-NN准确度、3-NN准确度、5-NN准确度、15-NNMAP、1-NN性能性能距离DTWlDTWnDTW Sinkhorn OPW精度地图71.0650.7773.6358.0570.7056.5566.6751.4374.3659.10距离DTWlDTWnDTW Sinkhorn OPW地图58.9556.6756.5254.5858.701-NN81.3282.7879.8578.0284.253-NN81.3282.0579.1277.6682.785-邻硝基甲苯80.9579.1276.9274.7380.2215-NN82.7875.8276.1969.9677.291058准确性映射准确度，1-NN准确度，3-NN准确度， 5-NN准确度，15-NNMAP，1-NN准确性映射性能性能80 8080 8060 6060 6040402020404020200-6-4-2 0 2 46log（λ）1（一）0-6-4-2 0 2 46log（λ）1（b）第（1）款0-6-4-2 0 2 46log（λ）2(c)0-6-4-2 0 2 4 6log（λ）2(d)图6. NM分类器随着（a）λ 1的增加的性能;（b）NN分类器的λ 1;（c）NM分类器的λ 2;（d）NN分类器的λ 2。方法DTWlDTWnDTW Sinkhorn OPW精度地图82.5573.2380.1876.2976.2767.7577.0065.1187.2782.23(a) NM分类器距离DTWlDTWnDTW Sinkhorn OPW地图28.27（0.30）27.09（0.40）23.87（0.34）19.41（0.32）32.12（1.14）1-NN62.4466.0860.3157.5472.25（3.03）（2.31）（1.97）（3.34）（三时）3-NN59.9569.7863.0257.9773.62（2.40）（1.84）（1.89）（1.62） （2.01）5-邻硝基甲苯62.3669.9864.3960.5376.99（2.18）（2.16）（2.31）（2.04） （2.01）15-NN63.7772.1964.2461.2978.38（1.76）（4.33）（2.77）（2.49） （2.49）(b) NN分类器表3.联机相似汉字识别结果。标准偏差显示在括号中。通常，OPW优于次优结果，在相似字符识别上，NM分类器的准确率和MAP为7%，在SAD数据集上，NM和1-NN分类器的MAPs为5%。通常，Sinkhorn距离导致比DTW距离更差的结果，而所提出的OPW实现了更好的结果。这意味着直接将基于OT的距离应用于序列是不利的，并且时间调节在采用时间信息中起重要作用。6. 结论本 文 提 出 了 一 种 新 的 序 列 间 距 离 测 度 -- 保 序Wasserstein距离。OPW距离适用于序列数据的众所周知的最佳传输，其中一个序列中的物质分布被传输以匹配另一个序列的分布，具有最小的成本。所学习的(a) NM分类器距离DTWlDTWnDTW Sinkhorn OPW地图56.5856.0348.4743.2762.711-NN96.3696.7395.0587.9596.683-NN96.9196.8295.7389.0597.455-邻硝基甲苯97.2396.7396.0989.2397.1415-NN97.3696.5095.9190.7397.41(b) NN分类器表4. SAD数据集上的结果。传输还保留了实例的时间顺序，使得一个序列中的每个实例应当传输到具有相似相对时间位置的另一序列中的实例 为此，两个新的正则化条款，即。逆差矩正则化和先验分布正则化的我们表明，OPW距离可以有效地计算矩阵缩放。 在四个不同数据集上的实验表明，OPW距离能够实现灵活的保序对齐，从而解决任意起始点的周期模式和局部时间反转或失真问题。确认本工作得到了国家自然科学基金项目批准号：61603373. Gang Hua博士的部分资助项目为国家自然科学基金（61629301）。引用[1] G. Al-Naymat，S. Chawla和J.塔赫里Sparsedtw：一种加速动态时间规整的新方法。在澳大利亚，2009年。3准确度，1-NN准确度，3-NN准确度，5-NN准确度，15-NNMAP，1-NN性能性能方法DTWlDTWnDTW Sinkhorn OPW精度45.0146.1041.3134.9757.75（2.21）（3.92）（3.40）（1.84） （2.62）地图40.0240.5035.2128.7647.40（1.75）（2.76）（2.07）（1.12） （2.64）1059[2] F.阿尔布雷森从灰度共生矩阵计算的统计纹理度量。俄勒冈大学信息学系图像处理实验室，2008年5月。4[3] B. B. Amor，J. Su，and A.斯里瓦斯塔瓦。使用骨骼形状轨迹的速率不变分析的T-PAMI，38（1）：1-13，2016. 3[4] G. 奥德湾Cuturi湾 Pe y re′和F. 巴赫. 大规模最优运输的随机优化2016. 3[5] K. Bache和M.利希曼UCI机器学习库。加州大学欧文分校信息与计算机科学学院6[6] L. Bergroth，H. Hakonen和T.蕾塔最长公共子序列算法综述。字符串处理与信息检索国际专题论文集，2000年。3[7] A. Borobia和R. 不能。矩阵缩放：辛克霍恩定理的几何证明线性代数及其应用，268：1-8，1998. 6[8] R. A. Brualdi，S. V. Parter和H.施耐德非负矩阵与随机矩阵 的对 角 等 价。 Journal of Mathematical Analysis andApplications，16（1）：31-50，1966. 6[9] M.库图里Sinkhorn距离：最佳运输的光速计算。在NIPS，2013年。二三四六[10] M. Cuturi 和 A. 杜 塞 瓦 瑟 斯 坦 重 心 的 快 速 计 算 。InICML，2014. 3[11] R. Duin和M.看线性降维vi-一个lda的异方差扩展：Chernoff准则。TPAMI，26（6）：732-739，2004. 2[12] R. Flamary，M. Cuturi，N. Courty和A.拉库托阿蒙- jy。Wasserstein判别分析arXiv预印本arX- iv：1608.08063，2016年。6[13] C.弗罗格纳角Zhang，H. Mobahi，M. Araya和T. A. 波焦。学习与瓦瑟斯坦损失。2015年，在NIPS中。3[14] D.加罗河Lajugie，S. Arlot和F.巴赫.时间序列比对的度量学习。在NIPS，2014。3[15] S. Kullback和R. A.莱布勒关于信息和充足性。数学统计年鉴，22（1）：79-86，1951年。2[16] W. Li，Z. zhang和Z.刘某 基于一袋三维点的动作识别。在CVPR人类交流行为分析研讨会上，2010年。6[17] P. - F.马托时间扭曲编辑距离与刚度调整时间序列匹配。TPAMI，31（2）：306-318，2009. 3[18] G.纳瓦罗 近似字符串匹配的导游。ACM计算调查，33（1）：31-88，2001年。3[19] C. A. Ratanamahatana和E.基奥使用学习约束使时间序列分类更准确。见SDM，2004年。3[20] J. Rodriguez-Serrano和F.佩罗宁基于模型的序列相似度及其在手写体中的应用观察TPAMI，34（11）：2108-2120，2012. 3[21] Y. 鲁伯湖Guibas和C.托马西地球移动器的距离，多维缩放，和基于颜色的图像检索。ARPA图像理解研讨会论文集，第661-668页，1997年。3[22] H. Sakoe和S.千叶语音识别的动态规划算法- m优化。TASSP，26（1）：43-49，1978. 2[23] S. Salvador和P.陈在线性时间和空间中实现精确的动态时间弯曲。智能数据分析，11（5）：561-580，2007年。3[24] V.Seguy和M.库图里最优迁移度量下概率测度的主测地线分析。2015年，在NIPS中。3[25] D. F. Silva和G. E.巴蒂斯塔加速全两动态时间规整矩阵的计算。在SDM，2016年。3[26] R.辛克霍恩列和与行和预先给定的矩阵的对角等价性.美国数学月刊，74（4）：402-405，1967年。三、六[27] B. Su和X.丁线性序列判别分析：一种基于模型的向量序列降维方法。InICCV，2013. 3[28] B. Su，X.丁角，澳-地Liu和Y.吴异方差最大最小距离分析CVPR，2015。2[29] B. Su，X.Ding，H.Wang和Y.吴多维序列的判别维数约简TPAMI，2017。三、六[30] J. Su，S. Kurtek、E. Klassen，A. Srivastava等人黎曼流形上轨迹的统计分析：鸟类迁徙，飓风跟踪和视频监视。应用统计年鉴，8（1）：530-552，2014年。3[31] C.维拉尼 最佳运输：《新与旧》卷338Springer Science Business Media，2008. 二、三[32] M.弗拉丘斯，M.Hadjieleftheriou，D.Gunopulos和E.基奥 多维时间序列索引。VLD-B，15（1）：1-20，2006. 3[33] J. Wang，Z. Liu和Y.吴挖掘actionlet集成用于深度相机的动作识别。CVPR，2012。6[34] J.Wang和Y.吴学习最大间隔时间翘曲的动作识别。InICCV，2013. 三、六[35] F. Zhou和F.德拉·托雷广义时间规整用于人体运动的多模态对齐。CVPR，2012。3[36] F. Zhou和F.托瑞人类行为校准的规范时间扭曲NIPS，2009年。3