基于保序最优传输的序列距离.pdf

中国科学院软件研究所学术年会’2019 暨计算机科学国家重点实验室开放周 学术论文 基于保序最优传输的序列距离 Bing Su, Gang Hua “Order-preserving Optimal Transport for Distances between Sequences” IEEE Trans. on Pattern Analysis and Machine Intelligence, 2018. 苏冰，13661284169，subingats@gmail.com • Motivation  Measuring the distance between sequences plays a fundamental role in sequence analysis problems. • can be much more difficult than for vectors.  Various evolution speed & sampling rate: • Different sequences may have different numbers of instances.  Evolutions are not uniform: • Temporal alignments are necessary.  Instances in the same sequence are not independent: • Instances are temporally related. Order-preserving is required.  Local disorders may exist:  Objective • Strict order preservation may not be imposed to the alignment. • Adding the regularization terms to the OT objective  Arbitrary starting point for periodic patterns • Order-Preserving Wasserstein Distance  Cast alignment as the optimal transport problem • Given two sequences and apply the optimal transport (OT) by viewing instances as independent samples:  Optimization , • Problem: the ordering relationship is totally ignored.  Temporal order preserving regularizations • Preserve the inherent temporal relationships of the instances • Desired: elements in one sequence are transported into those in the other sequence with similar relative temporal positions • The transport T should show local homogeneous structures: large values appear in the area near the diagonal, while the values in other areas are zero or very small. inverse difference moment (IDM) regularization • A general ideal distribution of the values in T is that the peaks appear on the diagonal, and the values decrease gradually along the direction perpendicular to the diagonal. KL divergence with the Prior distribution • By setting the Lagrangian function obtain to 0, • According to the Sinkhorn's theorem, the optimal transport T with this form is a rescaled version of K: • Efficiently solved by the Sinkhorn-Knopp iterative matrix scaling algorithm: • Experimental Results  Comparison with other sequence distances