未来を予測するパーツ!時系列特徴Shapeletsとは?

3つの要点

✔️未来を予測するパーツの生成手法。その名もGENDIS
✔️高精度かつ高速に生成可能
✔️進化計算を使うことで計算量削減

未来を予測したいという時系列問題は、人間的にとってもっともらしい欲求です。一般的な時系列問題(株価の予測や天気の予測)では、時系列特徴Shapeletsを捉えることの重要性が議論されています。しかし、Shapeletsの抽出は計算時間がかかることや、正確な抽出が難しいことが問題となっています。今回は「進化計算を使った高速かつ正確な抽出手法」についてお話しします。

Shapeletsとは

Shapeletsとは簡単に言えば学習データの重要なサブシーケンス(一部分)です。

上の図は概念図ですが、学習データの重要なサブシーケンスが判明していれば、テスト時にそれを使って未来予測をすることが容易です。例えば、単純な予測方法として、0〜[t-1]時間までのテスト系列に近いShapeletsのt時間目の値を予測結果として出すことが考えられます。

従来手法とその問題点

では、どうやってShapeletsを抽出するのでしょうか?

Shapeletsが提案された2009年には、シーケンスからすべてのサブシーケンスを抽出する方法が提案されています。しかし、この手法はデータ数が増えると爆発的に計算時間が増えるため現実的ではありません。その後、逐次的にShapeletsを求めるShapelets Transform(ST)と呼ばれる手法が2012年に登場します。STは非常に強力な手法ですが、計算時間がデータ数に依存することが依然として解決されていません。

その後、機械学習によるShapeletsの抽出手法 Learning Timeseries Shapelets(LTS)が2014年に提案されます。LTSはSTよりわずかに精度は劣りますが、大幅に計算時間を減らすことに成功します。しかし、LTSはもっとも重要なパラメータの一つであるShapeletsの長さ自体をHyper Parameterとして持つため、チューニングに時間がかかってしまいます。

まとめるとこんな感じです

精度 計算時間
Shapelets Transform(ST) 良い 悪い
Learning Timeseries Shapelets(LTS) 普通 普通(Shapelets長の調整が必要)

ちなみにSTは、2017年に85個の時系列データセットで36個の手法と比較した結果、もっとも良い精度を納めています。

進化計算によるShapelets抽出

提案する手法の目的は、短時間でかつ良い精度を出すことです。そして、総計算時間を短くするためにはShapelets長を事前に指定せずに、抽出することが不可欠です。

そこで、メタヒューリスティックの手法かつ、柔軟な目的関数を設定可能な進化計算を使います。進化計算を使うことで次の利点が得られます。

  • メタヒューリスティックの手法なのでSTと比べて、短時間で実行可能
  • 柔軟な目的関数(=解表現)が可能なため、Shapelets長を固定しなくても良い

進化計算の目的関数は、次のように設定しています。Shapeletsと入力データの距離行列から、学習された関数と真の値との誤差が、Shapletsの評価値です。提案手法では、hにはロジスティック回帰を使っています。

また、一般的にはShapeletsは学習データのサブシーケンスですが、提案する手法では、サブシーケンスではなく、テスト時に有効な特徴量としています。そのため、より高次な特徴量が得られることも利点として挙げられます。

これは進化計算の最中に、2つの解(Shapelets)を混ぜる操作があるのですが、このときに、二つのShapeletsの平均値を新しい解(Shapelets)とすることで、学習データには含まれないシーケンスを生み出すことが可能です。

上の図は二つの解S’とS”を混ぜて新しい解S*を作るイメージです。提案手法では、このような操作を繰り返して行うことで、時系列クラス分類を行うために最も適したShapeletsを求めます。

実験

実験では、85個の時系列データセットに対して有効性を検証しました。85個のデータセットにおける平均順位は下の図のとおりです。

値が低いほうが、平均順位が高いことを表します。最も順位が高いのはSTです。そしてその次が提案手法であるGENEDIS。その下がLTSと続きます。そして、STとGENDISの間の黒い太線は、検定をした結果、有意差はなかったことを表しています。

この結果から、提案手法はSTとほとんど同じ精度を出すことがわかります。また、明らかにSTよりも高速に探索できます。

まとめ

今回の論文をまとめると、Shapeletsを探索する手法は提案手法によって以下のように分類できます。

精度 計算時間
提案手法 (GENDIS) 良い 良い
Shapelets Transform(ST) 良い 悪い
Learning Timeseries Shapelets(LTS) 普通 普通(Shapelets長の調整が必要)

今回紹介したShapeletsはマイナーな手法に分類されます。しかし、時系列特徴を抽出することは明らかに有効です。Shapeletsが流行らない大きな原因は、計算時間です。今回はこれを解決する提案手法を提示しました。もしも、さらに良い手法が提案され続いていくのであれば、今後Shapeletsが時系列クラス分類・回帰のブレイクスルーになるかもしれません。

GENDIS: GENetic DIscovery of Shapelets
written by Gilles Vandewiele, Femke Ongenae, Filip De Turck

(Submitted on 13 Sep 2019)
Subjects: Neural and Evolutionary Computing (cs.NE); Machine Learning (cs.LG); Machine Learning (stat.ML)

 

この記事をシェアする

コメント

Yuta Kashino  @yutakashino
2019/12/15 02:00

未来を予測するパーツ!時系列特徴Shapeletsとは? | AI-SCHOLAR https://t.co/536vAcjcXS 時系列の部分的形状から予測をするこれ系の研究、株式投資手法のテクニカル分析みが強すぎる気が…

NGO  @ngomshr
2019/12/14 10:03

Shapelets知らなかった https://t.co/pjaPyZ70SP

Yuji Tokuda  @dakuton
2019/12/14 09:59

時間可変でうまく特徴が残るように時系列データのセグメンテーションを行う / 未来を予測するパーツ!時系列特徴Shapeletsとは? | AI-SCHOLAR https://t.co/DZW9YxRnN2

積山 功  @tsumi130
2019/12/14 09:45

ほお。時系列解析なんて懐かしい https://t.co/91PuJLNQTh

shinmura0 | 2/15見学者募集中  @shinmura0
2019/12/14 08:34

後で読む。 https://t.co/eosE4E3GEa