Random Warping Series: A Random Features Method for Time-Series Embedding - todo314 @ ウィキ

• Random Warping Series: A Random Features Method for Time-Series Embedding
  • Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, Michael Witbrock
  • AISTATS 2018

概要

• 課題：Gram行列の対角優位と自乗時間
• random features approximationを採用
• DTW距離
  • 2つの時系列$$x_i, x_j$$に対する任意のalignment $$a$$を考える
  • 対応する各要素対のdissimilarityの和の最小が距離
  • $$ S(x,y) = \min_{a} \sum_{1 \leq t \leq |a|} \tau(x[a_1(t)], y[a_2(t)]) $$
• Global alignment kernel
  • 任意のalignmentに関する和
  • $$ k(x,y) = \sum_{a} \prod_{1 \leq t \leq |a|} \kappa(x[a_1(t)], y[a_2(t)]) $$
• 提案手法
  • ランダム時系列を$$p(\omega)$$に従って発生させる
    • カクカクした粗い時系列でOK（長さもランダム）
  • $$ k(x,y) = \int_{\omega}\phi_\omega(x) \phi_\omega(y) $$
  • $$ \phi_\omega(x) := \sum_{a} p(a \mid \omega) \tau(\omega, x; a) $$
  • 結局有限個のωをサンプルして近似すれば良い
    • 適当にやるとバウンドが出る
• 対角優位が解決される理由はあまり書いてなかった。

まとめ

• かなり簡単だけど、良い性能が出るんですね…。
• というかrandom featuresがすごい

AISTATS 時系列データ2018/05/19