時系列データ分類に超高速な選択肢現る

Time-series 2021年10月05日

3つの要点
✔️ 時系列分類に対して、新しい観点の手法が提案
✔️ 予測精度の高い線形分類をベースに学習時間を大幅に短縮
✔️ 時系列データをシンボル表現に変換、トライ木の探索を途中で打ち切る（枝刈り）基準にχ二乗限界を使用

MrSQM: Fast Time Series Classification with Symbolic Representations
written by Thach Le Nguyen, Georgiana Ifrim
(Submitted on 2 Sep 2021)
Comments: Published on arxiv.
Subjects: Machine Learning (cs.LG)

code：

本記事で使用している画像は論文中のもの、紹介スライドのもの、またはそれを参考に作成したものを使用しております。

はじめに

時系列データの分類についての論文です。特徴は、シンボル表現(symbolic representation)を用いているということと、χ（カイ）二乗限界によるパターンマイニングを使用していることです。モデルの名称は、"Multiple Representations Sequence Miner", 略称MrSQMです。先行する線形分類をベースに、精度、学習効率をより改善したものです。

先行研究

時系列分類(TSC)の先行研究のベースラインとしては、1-Nearest-Neighbor分類(1NN-DTW)を挙げています。このモデルはシンプルですが、ノイズへのロバスト性に欠ける問題があり、その後3つのグループで発展してきました。

1) アンサンブル分類

HIVE-COTEがポピュラーであり、異なるデータ表現、特徴量を用いた多数の分類器を、それぞれの分類の質に応じて重み付けしてアンサンブルします。

UEA/UCRベンチマークの学習に2週間以上かかるという問題があります。

2) 深層学習分類

最近、熱心に取り組まれています。FCN, Resnetなどが効率的であり、HIVE-COTEと同等の精度を示しています。学習データ数が少ないと過学習になる傾向と分散が大きい課題があります。InceptionTimeは精度と分散の改善をしたものですが、学習にはやはり数週間かかります。

3) 線形分類

伝統的手法ですが、最近時系列libに対しては良い結果を出しているようです。特徴量空間を大きくとることで、非線形分類器の必要性を下げています。LIBLINEARなどの大規模分類に、このアイデアが取り込まれて成功しています。

TSCでは、WEASELが大規模なSFA（後述）語特徴量空間を生成、χ二乗特徴量選択でフィルタリングし、ロジスティック回帰分類器を学習します。MrSEOLはSAX（後述）とSFAの大規模な特徴量空間を用い、グリーディ勾配降下とロジスティック回帰を行います。最近のROCKETでは、多数のランダム畳み込みカーネルを生成、max poolingとppvという新しい特徴量を用います。

アンサンブル学習や深層学習と同等の精度を数桁早い学習で実現できます。UEA/UCRベンチマークの学習は数時間で行えます。

もう一つの特徴は、手法が3段階に分割することができ、コンセプト的にシンプルであることです。1) データ変換, 2) 特徴量選択、3)線形分類です。

手法説明

先行研究より、線形回帰をベースにしています。入力された時系列データは、SAX, SFAなどのシンボル表現に変換されます。シンボル表現は、文書マイニングで開発した技術で、SAXはSymbolic Aggregation Approximation、SFAはSymbolic Fourier Approximationです。全体のワークフローはFig.1の通りです。

時系列のシンボル表現

SAX, SFAは共通して次の3ステップを取ってデータ変換します。

1) スライディングウィンドウで時系列のセグメントを抽出する

2) それぞれのセグメントを、通常、より短い長さのベクトルで近似する

3) 近似を離散化してシンボルワード(abbaccなど)を得る

SAXとSFAの主な違いは、近似と離散化のテクニックです。Table 1にまとめてあります。

シンボルシーケンスのための特徴量選択

・教師あり手法

χ二乗テストは特徴量候補をランク付けするよく知られた手法です。クラス特徴量c_kの測定された頻度O_kと期待頻度E_kに対してChi2は次のように求められます。

シンボル表現に現れるそれぞれのサブワードが特徴量の候補です。すべてを網羅的に評価して、Chi2を用いてランク付けするのは高価です。Chi2統計量には上限があり、特にシーケンシャルデータでは有用です。上限値は、次のように表されます。

シーケンシャルデータの反単調性により、シーケンスはそのプレフィックスのようにしか頻発しないと保証されます。そこで、候補特徴量のChi2スコアは(2)式によりそのプレフィックスを調べることにより早期に限界づけられます。効率的に探索し、上限値を効果的に使うために、トライ木(trie)を使ってサブシーケンスを保存します。トライ木はツリーデータ構造でエッジはシンボルに、ノードはルートからそのノードまでの経路のエッジをすべて結合(concatenate)して形成するサブシーケンスに対応します。

それぞれのノードは対応するサブシーケンスの転置インデックス（位置のリスト）を保存します。このようにして、子ノードは、位置のリストを通して繰り返すことにより素早く生成できます。簡単のため、2クラスシーケンスデータで、境になるサブシーケンスを探しているとします。O^j値は、それより上位のノード以下です。従って、ある時点で、スレショルドを切ると、それより下は探索しなくても、すべてスレショルド以下であることがわかります。従って、トライ木より枝刈り(prune)を行います。

この手法が時系列データに適用されるのは初めてです。シンボル表現時系列分類の効率的なアルゴリズムを獲得できました。

有用な特徴量を選択する他の手法に情報獲得(Information Gain: IG)があります。IGは予測がターゲット変数上でデータをいかにうまく区切ることができるかを表します。しかし、分割性能はChi2と同等で、多クラスへの適用ができないため、Chi2を採用します。

・教師なし手法

シーケンスデータに対するサブシーケンスの依存性は高いです。その中に一つがChi2スコアにより区切りである場合、他のサブシーケンスも区切りであり、ともに選ばれます。Chi2テストあるいは類似の特徴量を独立にランキングする教師あり手法は、この共線性問題に漸弱な傾向があります。言い換えると、上位ランクの特徴量は、互いに相関が高く、選択した特徴量集合に冗長性があることになります。ランダムな特徴量選択は、多様性を増します。

時系列のシンボル表現に対しては、シンボルのサブワード（部分文字列）が特徴量候補になります。ランダム特徴量選定器は、単純に時系列のインデックス、時系列の中での位置、サブワードの長さをサンプリングします。

・ハイブリッド手法

それぞれに利点、欠点があるため教師あり手法、教師なし手法を組み合わせます。MrSQMでは２つの組み合わせ方があります。1) 教師ありで特徴量を選定し、教師なしでフィルタリングする。2) 教師なしで選定し、教師ありでフィルタリングする。

MrSQM分類器変型

以上のコンセプトから、４つの型を選びました。

1) MrSQM-R:　特徴値のランダムサンプリングによる教師なし特徴量選定

2) MrSQM-RS:ハイブリッド手法。MrSQM-Rで候補を選び、教師ありChi2テストで絞り込む

3) MrSQM-S:　Chi2上限で全サブシーケンス特徴量を教師あり選定で枝刈りし、Chi2テストで上位kサブシーケンスの最適集合を選択する

4) MrSQM-SR:ハイブリッド手法。教師ありMrSQM-Sで特徴量候補を生成し、ランダムサンプリングでフィルタリングする。

評価

設定

データセットは、UEA/UCR TSC Archiveからの１１２の固定長単変量時系列データです。MrSQMは可変長への拡張も可能です。精度ゲインはHolm修正付きWilcoxon符号付ランクテストにより行い、Critical Difference(CD)図で視覚化しました。CDの計算にはRライブラリscmampを用いています。CDは複数のデータセットに対して、精度ランクの平均についての、複数の手法のランキングを示しています。統計的に有意差がない手法間は横線（CD内を示す）で接続して、有意差の有無がわかりやすくなっています。

感度分析

・枝刈り効果分析

枝刈り(Chi2限界)によりサブシーケンスの数が大幅に減少しています。

・SAX, SFAの比較

SAX, SFAのいずれかの特徴量を選択したモデル間には、統計的な有意差はありません。両方を選択したMrSQM-R-SSとの間には有意差が確認されました。

・特徴量選択アプローチの比較

MrSQM-RS, MrSQM-Rの間、MrSQM-R,MrSQM-SR, MrSQM-Sの間には有意差はありません。MRSQM-RS,MrSQM-RとMrSQM-SR, MrSQM-Sの間には有意差があります。学習、推論時間は70分です。

SAX, SFAの両方の特徴量を用いると、どちらか一方を用いるのに比べ、ランタイムが約2倍かかります。

・MrSQM vs. SOTA シンボリックTSC

MrSQMと従来のシンボリックTSC (WEASEL, MrSEQL, BOSS, cBOSS, S-BOSS)の間には、精度の有意差は見られません。ただし、従来のSOTAは訓練に１０～１２時間以上かかります。

・MrSQM vs. 他のSOTA TSC

今まで、最も精度が高い時系列分類器は、HIVE-COTE 1.0, TS-CHIEL, ROCKET, Inception Timeです。ROCKET以外は、学習にコンピュータ資源を必要とし、数日もしくは数週間必要です。Fig.7はそれぞれのMrSQM-RSとの精度比較です。

MrSQM-RSの精度は、それほど劣りません。学習速度は格段に速いです。ROCKETのみは、学習、推論時間が1.5時間でMrSQM-RSとさほど違いません。しかし、ROCKETではいくつかのデータセットに対して精度が劣化します。MrSQM-RSには、それはありません。HIVE-COTE等は、集中的なハイパーパラメータのチューニングが必要ですが、MrSQMではすべてのデータセットに対して、デフォールトパラメータを使用しています。