あなたは、数時間に及ぶ膨大な都市の街頭録音の中から、特定の繰り返される音を見つけ出そうとしている探偵だと想像してください。その音が何度も繰り返されることは分かっていますが、それがどのくらいの長さなのかは全く分かりません。それは短い鋭い「ピー」という音でしょうか？それとも、長く引き延ばされた「ハミング」でしょうか？あるいは、中程度の長さの「チャープ（鳥の鳴き声のような音）」でしょうか？もし、録音全体を何度も聞き直し、最初は「ピー」だと仮定して探し、次は「ハミング」だと仮定して探し、その次は「チャープ」だと仮定して探すということをすれば、永遠に終わらないでしょう。これは、心拍数、株価、地震の揺れといった、時間の経過とともに変化する数値のリストである時系列データを扱うデータサイエンティストたちの日常的な苦闘です。彼らは、隠れた繰り返されるパターンであるモチーフを見つけ出したいと考えています。厄介なのは、彼らが多くの場合、その「持続時間」（そのパターンが何秒間、あるいは何データポイント続くのか）を事前に知らないことです。これを解決するために、彼らは通常、あらゆる可能な長さをチェックしなければなりません。それは、まるで一本一本の藁を何度も何度も繰り返しチェックしながら、干し草の山の中から針を探すようなものです。

そこに、超スマートな「ワンパス（一度の通過）」で行う探偵として機能する新しい手法、Panacheが登場します。録音を止めて巻き戻しては異なる長さをチェックするのではなく、Panacheは録音を一度だけ再生します。音が流れ込むにつれて、Panacheはあらゆる可能な長さに対して、同時に、即座に繰り返されるパターンを特定します。これは、音を「スペクトル指紋」——単なる音量ではなく、波の形状に基づいたユニークな署名——に変換することで実現されます。もし二つの音が似ていれば、それらの指紋は一致し、Panacheはそれらを詳しく調査すべきだと判断します。一致しなければ、即座に無視します。その結果、Panльшеは古い遅い手法と同じパターンを見つけ出しながら、それを極めて短時間で行います。テストでは、他の手法が膨大なデータセットの分析に数時間を要した一方で、Panacheはわずか数分で完了し、一度の作業で正しい答えを得るために作業を繰り返す必要はないことを証明しました。

問題点：「ゴルディロックス」の窓

時系列データの世界では、「モチーフ」とは繰り返されるパターンを指します。しかし、パターンとは単なる形ではありません。それは「形」と「持続時間」の組み合わせです。ビデオの中で特定のダンスの動きを探している場面を想像してみてください。もし窓（見る範囲）が短すぎると、足踏みしか見えません。もし窓が長すぎると、足踏みに加えて次の動きや背景、さらにはダンサーの衣装まで混ざり込んでしまいます。あなたは、その動き全体を明確に捉えるための、ちょうど良い長さの「ゴルディロックス（適度な）」窓を必要としているのです。

問題は、探索的データ解析において、その「ちょうど良い」長さが何であるかを私たちが事前には知らないことが多い点です。10ポイントから1,000ポイントまでの長さをチェックする必要があるかもしれません。Pan Matrix Profile (PMP) と呼ばれる従来の手法は、非常に丁寧ですが、信じられないほど遅い司書のようなものでした。あらゆる長さに最適な一致を見つけるために、この司書は長さ10のために大規模な探索を実行し、次にまた最初から始めて長さ11を行い、次に長さ12を行い……という作業を繰り返さなければなりませんでした。もしチェックすべき長さが50種類あれば、司書はその本を50回読み直さなければならないことになります。これは「二次自己結合（quadratic self-joins）」と呼ばれます。これは、あらゆるデータ片を他のあらゆるデータ片と比較することを、何度も何度も繰り返すという、非常に凝った言い方です。これは機能しますが、データが大きくなるにつれて、耐え難いほど遅くなります。

Panacheの解決策：ワンパス、全長

この論文の著者であるTej Sanibh Ranadeは、この「Pan Matrix Profile」の仕事を一度のパスで実行できる最初のアルゴリズムであるPanacheを紹介しています。テープを50回巻き戻す代わりに、Panacheはデータストリームを正確に一度だけ読み取ります。新しい数値が到着するたびに、Panacheは関心のあるすべての異なる長さに対して、内部状態を同時に更新します。

どのようにしてこの魔法のようなトリックを実現しているのでしょうか？それは、数学に関する巧妙な観察に基づいています。データの塊を取り出し、それを「正規化（平均をゼロにし、標準偏差を1に調整することで、実質的に音量を取り除き、形状だけに焦 Focus すること）」すると、驚くべきことが起こります。データの数学的な「スペクトル（フーリエ変換）」のうち、変化するのはDC成分（平均）のみです。残りのスペクトル——実際の波の形を記述する部分——は、平均に関わらず、全く同じままなのです。

Panacheはこの事実を利用して、スライディング・スペクトル状態を維持します。ウィンドウ内のデータが前方に一歩スライドする際、アルゴリズムは全体の形状を最初から計算し直すことはありません。代わりに、「スライディングDFT（離散フーリエ変換）」の再帰を使用します。これは、材料のコンベアベルトのようなものです。新しい材料が入ってきたとき、レシピ全体を捨てて作り直すのではなく、後ろにある古い材料を一つ取り除き、前にある新しい材料を一つ追加して、数学的な調整を行うだけです。これにより、Panacheはすべてのウィンドウの長さにわたって、常に最新の形状の「指紋」を保持することができます。

探偵のツールキット：ハッシングと拒絶

これらのスペクトル指紋を手に入れた後、Panacheはどの指紋が一致するかを見つける必要があります。すべての指紋を他のすべての指紋と比較することは、それでは依然として遅すぎるため、Panacheは**局所敏感ハッシュ（Locality-Sensitive Hash: LSH）**を使用します。これは、似た指紋が自動的に同じ引き出しに分類される巨大なファイルキャビネットのようなものです。もし二つのウィンドウの形状が似ていれば、それらのハッシュ（デジタル署名）は非常に近くなり、同じバケット（箱）に入ります。

しかし、二つのものが同じバケットに入っているからといって、それらが完璧に一致することを意味するわけではありません。バケット内のすべてのペアに対して高コストな厳密な計算を行うことを避けるため、Panaceは**パセバルの下界（Parseval lower bound）**を使用します。これは数学的なセーフティネットです。スペクトルの指紋のみに基づいて、二つの形状間の「最小の可能な距離」を計算します。もしこの最小距離がすでに一致するには大きすぎる場合、Panacheはそのペアを検討することなく破棄します。これは、クラブのドアマンがIDをチェックするようなものです。IDが偽物に見えたら、顔を確認することさえせずに入場を拒否します。このステップにより、ほとんどの「惜しい一致」を排除し、膨大な時間を節約しています。

「アンカー」戦略

これらのトリックを使っても、あらゆる単一の長さ（例えば10から1,000まで）をすべてメモリに保持しておくことは困難です。そこで、Panacheは**アンカー長（Anchor Lengths）**と呼ばれる戦略を採用しています。すべての長さをアクティブな探索対象として維持する代わりに、ステップストーン（踏み石）のように間隔を空けて配置された、いくつかの選択された長さに対してのみ「アクティブ」な探索を実行します。

論文では、モチーフは「粘着性がある」と主張しています。もしある長さ20でパターンが良い一致を示すなら、そのパターンは長さ19や21でも良い一致を示す可能性が非常に高いのです。したがって、Panacheはアンカー長における一致を見つけ、その後、その間の長さに対して迅速なローカルチェックを行います。これにより、すべての長さに対して重い処理を行うことなく、それでも答えを見つけ出すことができます。なぜなら、「良い」長さは互いに集まっているからです。

結果：速度と精度

著者らは、心拍数（ECG）、地震、株式市場などの実世界のデータを含む17種類の構成でPanacheをテストしました。彼らは、強力なGPU（高速計算に使用されるグラフィックスカード）上で動作するものを含む、既存の最高の手法と比較しました。

結果は驚くべきものでした。500万のデータポイントと51の異なる長さをチェックするWaferというデータセットにおいて：

• 最速の既存のCPU手法は、7.95時間かかりました。
• トップクラスのGPU手法（H100上のScamp）は、38.3分かかりました。
• Panacheは、初期スキャンを2.9分で完了し、最終的な正確なモチーフを6.0分で出力しました。

Panacheは、テストしたすべてのCPUおよびGPUのベースラインよりも高速でした。さらに重要なことに、精度を犠牲にしませんでした。Panacheは、低速で厳密な手法が見つけたトップ20のモチーフを**100%**回収しました。報告されたすべてのパターンは、有効な隣接点への厳密な距離を持つものでした。

なぜこれが重要なのか

この論文は、Panacheが、ストリーミング形式かつリアルタイムで、精度を損なうことなく、未知の長さの繰り返されるパターンを見つけるという、データマイニングにおける長年の課題を解決したと結論付けています。繰り返しの多い、遅い「巻き戻して検索する」アプローチを、スペクトル指紋と数学的なショートカットを用いた、単一のスマートなパスに置き換えることで、Panacheは膨大なデータストリームを数時間ではなく数分で分析することを可能にします。これは、古い手法の厳密な結果を得つつ、現代的なストリーミングアルゴリズムのスピードも手に入れられることを証明しています。唯一のトレードオフはメモリです。高速なルックアップを行うために多くのデータをRAMに保持するため、単純な手法よりも多くのメモリを必要としますが、提供されるスピードを考えれば、著者らはそれは価値のある代償であると示唆しています。