5
$\begingroup$

Canonical Time Warping is a state-of-the-art technique for time alignment. According to the original paper, it helps account for individual varieties when aligning sequences derived from different subjects performing similar event (e.g., aligning sensor data referred to two subjects' walking), by maximizing sequences correlation in a projected subspace.

Consider the iterative procedure of CTW that combines Canonical Coef. Analysis (CCA) and Dynamic Time Warping (DTW): Given a pair of temporally misaligned time-series that are in the same dimension, DTW is performed to initialize the warping matrices.

  1. Then, CCA is performed on the warped time-series (not necessarily well aligned) to give a pair of projection matrices.
  2. Multiply the original input (unwarped sequences) by the corresponding projection matrix obtained in 1, on which DTW is then performed. The warping matrices will be used in the next iteration.
  3. Before next iteration, warp (obtained in 2) the input and multiply it with projection matrices (obtained in 1), and assess the Euclidean distance of two sequences. The iteration stops as the Euclidean loss reaches a threshold.

My question is, how does CCA help time-alignmnet in first step of iteration? Since warping matrices given by DTW is not well tuned, it might not make sense to force maximal correlation between two not-well-aligned or misaligned sequences.

For example, consider an extreme case: two same, but out-of-phase time-sequences are firstly analyzed by CCA, followed by DTW. The resulting warping path can be diagonal (45 degree) if the projected sequences are flattened to zeros by CCA, which is totally wrong. Even if not zeros, making similar the two temporally misaligned time-series can harm the performance of DTW, so I see no benefit of CCA in CTW.

Could some give a straight forward explanation about it? Or correct my understanding of CTW, please.

$\endgroup$
  • 1
    $\begingroup$ A related question/answer this site with an excellent explanation of CCA is How to visualize what canonical correlation analysis does (in comparison to what principal component analysis does)? $\endgroup$ – user77876 Sep 18 '17 at 13:15
  • 2
    $\begingroup$ Thanks for the great reference. But traditionally CCA is applied to simultaneous pair of data. E.g., a video recording of a subject speaking (visual data) and its simultaneously recorded audio stream (audio data). In such case, visual and audio data are well aligned, on which CCA performs and makes sense; no temporal misalignment. On the other hand, it doesn't make sense to me if one try to perform CCA on a pair of temporally misaligned data. $\endgroup$ – Gene Sep 18 '17 at 15:58
0
$\begingroup$

I think you raise a valid question, which is that "without an initial time-aligned pair of datasets, how can CCA perform well?"

My guess is that the answer is that "CCA doesn't perform well in the first step". The reason I say this is because the initial estimates "CCA" projectors don't require time-alignment, because PCA is used for each data matrix ($X,Y$) separately to estimate their initial "spatial" projections, respectively ($V_x, V_y$).

According the (Zhou and de la Torre 2009):

The algorithm starts by initializing $V_x$ and $V_y$ with identity matrices. Alternatively, PCA can be applied independently to each set, and used as initial estimation of $V_x$ and $V_y$ if $d_x\ne d_y$. In the case of high-dimensional data, the generalized eigenvalue problem is solved by regularizing the covariance matrices adding a scaled identity matrix. The dimension $b$ [referring to the reduced dimension, i.e., number of canonical/principal vectors] is selected to preserve 90% of the total correlation.

In other words, the first DTW is applied to the "high variance" portion of each dataset. From there onward, the first DTW estimate is used to align the matrices.

Also, note that according the paper, when the data dimensions match ($d_x=d_y$), identity matrices are used for the initial CCA projections, meaning that in effect DTW is applied first. So, whether PCA is used or not, the CTW algorithm always applies CCA to an initially time-aligned sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.