畳み込みシェープレット変換で繰り返しパターンの精度改善

Time-series 2021年11月26日

3つの要点
✔️ シェープレットは説明性は高いが、モデリング精度では劣っていた
✔️ 畳み込みなどカーネルアプローチは精度は高いが、説明性は低いという課題が発覚
✔️ 拡張(dilation)をシェープレットに組み合わせ、両方を満たす

Convolutional Shapelet Transform: A new approach for time series shapelets
written by Antoine Guillaume, Christel Vrain, Elloumi Wael
(Submitted on 28 Sep 2021)
Comments: Published on arxiv.
Subjects: Computer Vision and Pattern Recognition (cs.CV); Machine Learning (cs.LG)

code：

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

はじめに

例えばロボットアームの駆動のように一連の特徴的な動きを繰り返すケースはよく見られます。一連の動きを単位として取り扱えるシェープレットという概念がありますが、モデリングの精度については改善の余地があるようです。この論文では、そのような領域について提案をしています。

時系列データは様々な分野で利用されていますが，アルゴリズムを現場で安全に利用するためには，問題を効率的に解決することと，判断の背景にある理由を理解することが同じくらい重要になることがあります．最近の時系列分類の研究では，時間効率の悪さを犠牲にして精度の高いアルゴリズムが生み出されてきました。同様の性能を持ちながら極めて高いスケーラビリティを持つ畳み込みカーネルアプローチがその方向です。しかし，これらの手法，特にカーネルアプローチは，どれも簡単に解釈できるものではありません．一方、シェープレット(shapelet)に基づく手法は、これらのアプローチにかないませんが、ドメイン専門家にとって理解しやすい結果を出すことができます。

この論文では，畳み込みカーネルで用いられる拡張(dilation)の概念をシェープレットに導入した，時系列シェープレットを適応した畳み込みシェープレット変換（Convolutional Shapelet Transform: CST）を紹介しています。また、畳み込みカーネルから識別性の高い畳み込みシェープレットを抽出するアルゴリズムを提案しています。このアルゴリズムにより、時系列の長さに依存しない、連続しない小さな識別性の高い部分列を生成することができます。このアプローチは、新しいシェープレットベースのアルゴリズムであり、最先端のシェープレット法と競合するだけでなく、畳み込みカーネル法を解釈するためのツールとして見ることができることを示しています。この論文の貢献は以下のようにまとめられます。

- 時系列のシェープレットを拡張して使用できるようにした。

- 畳み込みカーネルの出力とそのデータ識別能力に依拠した、畳み込みシェープレットの抽出方法。

- 最も重要なシェープレットおよび畳み込みカーネル法との比較研究。

- 畳み込みカーネルの解釈可能性を提供する方法

この論文を直観的に理解するための例が挙げられています。古典的な「GunPoint」データセット[17]を使った視覚的な例です（Figure 1参照）。このデータセットは、アクターの片手の動きをセンサーで記録したものです。クラス0は、アクターが銃を取り出したり、向けたり、ホルスターに戻したりしている様子を表し、クラス1は、銃を出さずに同じ動きをしている様子を表しています。

背景

背景として、紹介するアプローチの中核となる2つの手法に焦点を当てます。

シェープレット

シェープレットは、クラス・メンバーシップを代表する時系列サブシーケンスと定義されます。多くの場合、シェープレットベースのアルゴリズムは、シェープレット候補の生成、フィルタリング、評価の3つのステップによって区別されます。オリジナル・アプローチでは、シェープレットを用いて「シェープレット・ツリー」を構築します。候補は、木のノードの時系列に存在する長さlのすべてのサブシーケンスを列挙することで抽出されます。そして、入力への距離を計算して評価し、現在のノードを分割するための最良の候補を情報利得によって選択します。S = {v1,...,vl}を長さlのシェープレットとし、値をz正規化（すなわちμS = 0とσS = 1）し、X = {x1,...,xn}を時系列とすると、シェープレット距離は、SとXの長さlのすべてのz正規化されたサブシーケンスとの間の最小距離となります。

シェープレット変換アルゴリズムでは，ツリーの各ステップでのシェープレットの評価を避け、代わりに，N個の入力時系列からM個のシェープレット候補を抽出した後，評価は1回だけ行い，その結果，分類器の入力データとしてN×Mの距離行列が得られます。この行列を「シェープレット変換」と呼びます。Figure 2は、2つのシェープレットを用いた場合の例である。シェープレットに基づいて多くのアルゴリズムが設計されており、離散化やランダム選択を用いてシェープレット候補をフィルタリングするものや、データからシェープレットの位置指標を構築して限られた数の候補を生成するものなどがあります。最近の研究では、進化的アプローチやニューラルネットワークのために、特徴としてシェープレットの位置を含むものもあり、また、我々の方法と同様に、入力データの異なる表現からシェープレットを抽出するものもあります。

ランダム畳み込みカーネル変換

The RandOm Convolutional KErnel Transfrom (ROCKET) は、膨大な数（デフォルトでは10.000）のコンボリューション・カーネルをランダムに初期化します。このようなカーネルは、K = {l, {w₁,..., w_l},b,d,p}と定義でき、lはカーネルの長さ、wは重み、bはバイアス、dはダイレーション（拡張）、pはパディングです。このカーネルを用いて，時系列の畳み込みから特徴量を作成し，分類器に与えることができます（Figure 3）。時系列X ={x₁,...,x_n}とカーネルKに対して、畳み込みは、サイズn-((l-1)×d)+2pのベクトルCを生成し、ここで、ベクトルの位置iは次のように定義されます。

この文脈では、1つの点x_i∈Xは、Cを計算する際に複数回使用することができます。（例えば、x_iは、拡張と長さに応じて、任意のc∈（c0,...,ci）を計算するために使用することができる）。パディングを使用する場合，カーネルがすべての点を中心とするように，Xの最初と最後にゼロを追加します。各カーネルは，最大値（max）と，畳み込みによって生成されたベクトルにおける正の値の割合（ppv）の2つの特徴を生成します。N個のカーネルが生成された場合，変換では2N個の特徴量が出力されます。Mini-ROCKETは、ROCKETのほぼ決定論的で高速なバージョンです。重みは{-1,2}で選択され、ppv特徴のみが抽出されます。

以下では、倍数列XとカーネルKが与えられたときに、畳み込みCを生成する関数をC_K(X)と呼び、すべてのX∈ $ \chi $ に対する畳み込み空間をC_K(X)の集合と呼びます。

畳み込みシェープレット変換

カーネルKが与えられたとき、Kが生成した畳み込み空間から抽出されたppv統計量が、データをより純粋な（情報利得の意味で）部分集合に分割できる場合、それは入力空間の各部分集合に特有のパターンから生じる畳み込み空間の違いの結果であることを意味するからです。さらに、ppvは畳み込みにおいて正の値を持つ点の割合に基づいているため、Kが生成した畳み込み空間を考えると、インデックスiの点がデータのあるサブセットではppvに正の寄与をし、他のサブセットでは負の寄与をする場合、このi番目の値の畳み込みを計算するのに使われた入力空間の点が、サブセットの識別に役立つパターンを形成していることを意味します。この論文では、畳み込み空間に見られる違いを利用して、入力空間からそのような識別パターンを抽出し、その抽出されたパターンに基づいて時系列を比較する畳み込みシェープレットを構築します。畳み込みシェープレットを S = {d,l, {v1,..., vl}} と定義します。d は拡張パラメータ、l は長さ、{v1,...,vl} は Z 正規化された値です。時系列Xのシェープレット距離は、Xのサイズlのすべての部分列を要素間の拡張dで考慮することによって定義されます。畳み込みシェープレットSと時系列Xとの距離関数Dは、次のように書かれます：

この距離関数と畳み込みシェープレットのセットを用いて、シェープレット変換を構築し、分類アルゴリズムで利用することができるようになります。アルゴリズム1は、X ={X1,...,Xn}を偶数長の入力時系列のセット、Y ={y₁,...,y_n}をそれぞれのクラスとし、アプローチの概要を示しています。

カーネルとデータ分割生成

最初のステップは、カーネルのセットを生成し、そこからppv統計量と、各サンプルX∈χと各カーネルK∈Κについて、正の値を生成するC_K(χ)の畳み込み演算にXの各点が何回出現したかをカウントする行列Lを抽出することです。カーネルの生成は、Mini-ROCKETと同じ方法論に依っています。

入力が生成されると、次のステップでは、データをより純粋なサブセットに分割することができる、判別可能なカーネルを分離します。この考えを反映させるため、ExtractNodes関数では、すべてのカーネルのppv統計を特徴として、n_treesの決定木のフォレストを生成します。次に、フォレスト内の各ノードを抽出し、このノードの入力データ、ノードが出力する2つのパーティション、およびノードの入力データを分割するために使用された特徴（すなわちカーネル）を格納します。これにより、入力データのより純粋なサブセットを作成するためにカーネルが使用されているノードのアンサンブルを探索することができます。なお、決定木のアンサンブルを使用することで、潜在的な引き分けを考慮し、重複するノードも削除しています。

シェープレット抽出

前のステップから、行列Lと木のノードのセットが得られます。各ノードには，データを分割するために使用されたppv特徴を生成したカーネルK_i，そのノードで使用された入力時系列をX，そのノードで行われた分割をYで表しています。ツリーノードのカーネルK_iが与えられた場合，ppvの差を生じさせる畳み込み空間のポイントを特定し，Yのクラス間でこの差が最も大きくなるところにシェープレットを抽出します。この差を計算するためには，まず，Xの各サンプルについて，畳み込み空間の各点のスコアを求め，次に，差を計算するためのクラスごとのスコアを構築する必要があります。このクラス・スコアは，畳み込み空間のある点が，このクラスのサンプルに対して正の値を導く可能性を測定することを目的としています。Xの各サンプルのスコアを計算するには，行列Lで示されるXの各サンプルについて，畳み込み空間の各畳み込み演算で使用されるすべての点の寄与度を合計します．これにより，形態 (|X|,|X| - (l - 1) × d)の行列Lが得られ，L[j,c]は，カーネルK_iによるサンプルjのコンボリューションのc番目のポイントのスコアとなります．この行列から，あるクラスの各サンプルのLを合計することで，クラスごとのスコアLCが得られます。これらの2つの新しい行列が与えられた場合、パーティションY内の2つのクラスのそれぞれについて候補となるシェープレットを抽出するために、クラスのLCと他のクラスのLCとの差を計算し、その結果、各クラスのベクトルDが得られます。前述したように、この操作は、Dのある点の値が大きいほど、その点において、あるクラスのサンプルではKiのコンボリューションが正の値を出力し、もう一方のクラスでは負の値を出力する可能性が高いという直感的なものです。次に、Figure 4に示されるように、Dの中でパーセンタイルP以上の部分を見れば、どこで候補を抽出すればよいかがわかります。抽出自体は、事前にPで選択された各領域を対象とし、領域の最大値のインデックスにmを記し、現在のクラスのどのサンプルjがL[j,m]を最大化するかを検索します。それが見つかると、K_iのm回目の畳み込み演算で使われたこのサンプルの値を使って候補が作られます。

最後に、RemoveSimilar(Candidates,n_bins) 関数は，同じ拡張を共有する候補のすべての値を，一様に間隔を空けた n_bins で離散化します．すべての候補値が離散化されると，重複する候補値を削除し，その他の候補値をシェイプレットとして保持し，シェープレット変換に使用します。次の2点を強調しておきます。

- 畳み込みシェープレットの長さは、入力時系列の長さには依存せず、カーネルの長さにのみ依存します。さらに、ダイレーションを使用することで、シェープレットが連続した部分配列であるという要件がなくなります。

- 離散化は候補の数を減らし、入力空間に必ずしも存在しないシェープレットを生成し、過学習を制限します。

実験

以下では、Convolutional Shapelet Transformを分類器としてRidge Classifierを使用し、CSTと表記します。あらゆるデータセットで本手法を実行するためのコミュニティ標準を用いたpythonパッケージと、実験で使用したスクリプトおよびデータを提供します。比較研究ではUCRアーカイブの108個の一変量データセットを、感度分析ではそのサブセットを、スケーラビリティ分析では2つの大規模データセットを使用しました。結果は、臨界差図を用いてオブジェクトの平均ランクを表示し、Wilcoxon-Holmのポストホック分析を用いて計算したクリーク（水平バーでの接続）を追加します。クリークは，オブジェクト間の差が統計的に有意でないことを示します。以下では，CSTを，Shapelet Forest Classifier (SFC)，MrSEQL，Shapelet Transform Classifier (STC)，Mini-ROCKET (MiniRKT)と比較します。

パラメータの感度分析

ビンについては、比較した中では有意差は見られませんでした。Pについては、80を超えて有意差が現れています。ツリー数は250異常では、改善が見られなくなっています。

スケーラビリティ

Figure 6は，並列スレッド数を20に制限して10個のリサンプルを行った場合の，シェイプレットの抽出，距離計算，分類，予測を含む各手法の平均総実行時間を示しています。SFCとCSTの実行時間の違いは、現在のバージョンでは、木のノードの抽出とシェープレット距離の計算が1つのスレッドで実行されていることにも起因しています。1つのスレッドだけで比較した場合、その差は非常に小さくなります。MrSEQLは、アルゴリズムにSAXのような近似技術を使用していることが理由の1つで、長い時系列ではCSTよりも効率的ですが、この利点はサンプル数には当てはまりません。

比較評価

Figure 7によると、平均してCSTは他のシェープレットベースのアルゴリズムよりもわずかに優れていますが、その差は有意ではありません。Table 1によると、CSTはECGやEPGで記録されたデータでは他のアルゴリズムよりも効果的であるが、シミュレーションデータでは劣ることがわかります。なお、CSTの結果の中には、Adiacデータセットのように、Random Forestのような非線形モデルを使用することで向上するものがあります（Adiacでは約10%の精度）。これらのデータセットでは、CSTは、線形モデルが効率的に使用できないクラスに直接結びついていない多くのシェープレットを生成していると考えられます。MiniRKTは、平均的にはまだCSTよりも優れています。

解釈性

Figure 8は、解釈プロセスがどのような段階に見えるかの例を示しています。シェープレットについては、クラスごとのシェープレット距離の逆数のボックスプロットを表示し、分析したいサンプルまでの距離を赤い線で示しています。0に近い距離は、シェープレットとサンプルの間のマッチングが良好であることを示すことが多いため、逆距離を使用して視覚化しています。ボックスプロットの後、z正規化された値を持つシェープレットが、その拡張を示すx軸ラベルとともに表示されます。最後に、テストサンプルとシェープレットの間で最もマッチした位置を表示します。シェープレットは、それが配置されているサブシーケンスと同じスケールを持つように、z正規化を逆にしてスケーリングされています。カーネルのすべてのシェープレットを可視化して、その挙動を把握することができます。このようなプロットは、決定木においてサンプルの決定経路にある各シェープレットを表示したり、線形モデルにおいて各クラスの係数が最も高いシェープレットを選択したりすることができます。この手法をオンラインリポジトリの任意のデータセットでテストするためのインターフェースを提供しています。

まとめ

畳み込みシェープレット変換は、時系列のシェープレットにアプローチする新しい方法であり、拡張を利用することで、連続していない非常に小さな部分配列をシェープレットとして使用することができ、データの関心領域を効率的にカバーすることができます。この新しい手法は、他のシェープレットベースのアルゴリズムと比較して、合理的な計算コストで最先端のシェープレットアルゴリズムを向上させることが実験で示されています。ここでは、畳み込みカーネルの結果を解釈するために、この手法をどのように使用するかという基本的な例を示しただけですが、今後は、畳み込みカーネルを使用する手法のための信頼性の高い解釈ツールを構築するために、この手法が提供する可能性をより深く追求していきたいとしています。また、最近の論文のように、畳み込みから抽出された統計量をより多く使用できるように、この手法を強化したいともしています。これにより、より多様なパターンを畳み込みシェープレットで識別できるようになりそうです。さらに、このアルゴリズムを多変量解析に拡張し、シェープレットの抽出に他のモデルを使用することを検討されています。これに加えて、さらなる最適化を行うことで、本手法の時間的性能を大幅に向上させることができそうです。