TS-DIST: Learning Adaptive Distance Metric in Time Series Sets

Patent metadata

Field	Value
Publication number	US-2016239000-A1
Application number	US-201615003395-A
Country	US
Kind code	A1
Filing date	Jan 21, 2016
Priority date	Feb 12, 2015
Publication date	Aug 18, 2016
Grant date	—

Abstract

A process to control a machine by receiving data captured from one or more sensors in the machine generating high-dimensional time series sets in a machine; performing structure precomputing to obtain structures of different sets and time series in each set; performing supervised distance learning by imposing label information to the obtained structures, learning a transformation matrix; transforming the data to shrink a distance between sets with the same label and to stretch the distance between sets with different labels; and applying the transformed data to control the machine responsive to the time series data.

First claim

What is claimed is:

1 . A process to control a machine, comprising:
receiving data captured from one or more sensors in the machine generating high-dimensional time series sets in a machine; performing structure precomputing to obtain structures of different sets and time series in each set; performing supervised distance learning by imposing label information to the obtained structures, learning a transformation matrix; transforming the data to shrink a distance between sets with the same label and to stretch the distance between sets with different labels; and applying the transformed data to control the machine responsive to the time series data.

2 . The process of claim 1 , comprising performing a structure-preserved projection that reduces the dimension and preserves dependencies of the input time series sets.

3 . The process of claim 1 , comprising generating a library of distance functions to quantify similarity of each time series set.

4 . The process of claim 1 , comprising obtaining global structures and dependencies of time series across all sets by computing dissimilarity matrices.

5 . The process of claim 1 , comprising reducing high dimensional time series sets to a low-dimensional matrix with a structure-preserved projection.

6 . The process of claim 1 , comprising capturing an inter-set local structure using k-Nearest Neighbors (kNN) to capture original local dependencies of the input time series.

7 . The process of claim 1 , comprising formulating a convex problem that allows the distance learning problem to be exactly solved with an optimal solution.

8 . The process of claim 1 , comprising formulating the distance learning requirement to a semi-definite programming (SDP) that covers all objectives.

9 . The process of claim 9 , comprising solving the SDP to get an optimal solution.

10 . The process of claim 1 , comprising applying Largest Margin Nearest Neighbor (LMNN) to formulate a Semi-Definite Programming (SDP) problem.

11 . The process of claim 1 , wherein the performing structure precomputing comprises treating each type of time series in the sets as a feature and obtaining structure dependency between different time series sets, and for each type of time series, analyzing the series across all sets and determining a dissimilarity matrix based on the feature.

12 . The process of claim 11 , comprising generating a Multidimensional Scaling (MDS) matrix to project each of the calculated dissimilarity matrix to a row vector, where each projected vector corresponds to a time series feature that represents coordinates of the input time series sets along the feature.

13 . The process of claim 12 , comprising assembling the row vectors and obtaining a matrix, where each column stores coordinates of corresponding original time series set along all features and projecting high dimensional time series sets into a low-dimensional matrix while at the same time capture the structure across all the sets.

14 . The process of claim 11 , wherein each time series set identify k Nearest Neighbors (kNN) from sets with the same labels based on information from the MDS matrix.

15 . The process of claim 11 , comprising learning a linear transformation matrix that projects an input matrix to a new space such that each set is closer to its identified kNN than sets with different labels.

16 . The process of claim 10 , comprising solving with Semi-Definite Programming (SDP), obtaining a learnt transformation matrix, and projecting the input MDS matrix to a new space where a desired distance metric is defined.

17 . The process of claim 16 , comprising determining an objective function as:

min


(

1
-
μ

)



Σ

i
,

j
→
i



(

x
i

→

,

x
j

→

)

τ



M


(

x
i

→

,

x
j

→

)

+

Assignees

• Nec Lab America Inc

Inventors

• Yan Tan
• Chen Haifeng
• Jiang Guofei

Classifications

• G06F2218/18

  by plotting the signal segments against each other, e.g. analysing scattergrams · CPC title

• G06F18/2415

  based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate · CPC title

• G05B13/0265 Primary

  the criterion being a learning criterion · CPC title

• G06F17/11

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title