はじめに

異常検知の論文のPatch Coreの数式を理解するためのメモです。

PatchCore論文(2021)
Towards Total Recall in Industrial Anomaly Detection
https://arxiv.org/abs/2106.08265

Warming up

以下の数式の意味を理解する。

この数式は、数学的最適化の問題を表しています。具体的には、M_C^* を見つける問題で、それは集合 M の部分集合 M_C の中で、特定の最適化基準を満たすものです。この基準は、m と n の間のユークリッド距離（||m - n||_2 と表される）に基づいています。

数式を部分ごとに分解してみましょう：

||m - n||_2：ベクトル m と n の間のユークリッド距離（L2ノルム）を表します。
min_{n ∈ M_C} ||m - n||_2：M_C の各要素 n に対して、ベクトル m からの距離が最小となる n を見つけます。これは M_C 内で m に最も近い点を見つけることに相当します。
max_{m ∈ M} min_{n ∈ M_C} ||m - n||_2：集合 M の全要素 m に対して、それぞれの m から M_C の中で最も近い n までの距離のうち、最大のものを見つけます。これは、最悪のケース（すなわち、最も遠いペア）を見つける操作です。
argmin_{M_C ⊆ M}：最後に、この最大距離を最も小さくするような部分集合 M_C を見つけることが目的です。つまり、M の中でどのような M_C を選べば、その中のどの点も M の他の点から遠くなりすぎないようにすることができるか、ということです。

この種の最適化問題は、クラスタリングや、データポイント間の最適なマッチングを見つけるための問題設定など、様々な文脈で出現します。例えば、ファシリティロケーション問題の一種で、クライアント集合 M からサービス施設の最適なサブセット M_C を選択する際に、この種の最適化が使用されることがあります。この場合、最も遠いクライアントまでの距離を最小化することで、全体としてのサービスの質を最大化するサブセットを見つけることが目標です。

PatchCore memory bankのアルゴリズム

以下のアルゴリズムの実装手順です。

この手順は、"PatchCore memory bank"というアルゴリズムに関するものです。このアルゴリズムは、おそらく異常検出や特徴抽出に関連していると思われます。具体的には、入力データからパッチレベルの記憶バンク（メモリバンク）を構築する手順を示しています。以下に、アルゴリズムの各ステップを説明します。

1. 入力:

φ: 事前に訓練されたモデルや特徴抽出器。
j: 階層。これは、おそらくネットワークの異なるレイヤーや特徴の階層を指していると思われます。
χN: 名目上のデータセット。正常なデータや基準となるデータのことを指している可能性があります。
s: ストライド。これは、データをどのように取り出すか（ステップサイズ）を決定します。
p: パッチサイズ。データからどれだけの大きさで特徴を取り出すかを決定します。
l: コアセットターゲット。最終的に選ばれる特徴の数を指している可能性があります。
ψ: ランダムな線形射影。データの次元削減や特徴空間への変換を行う関数のことです。

2. 出力:

パッチレベルのメモリバンク M。

3. アルゴリズム:

空のメモリバンク M を初期化します。
入力データ χN の各要素 xi に対して、事前に訓練されたモデル φ で特徴を抽出し、その特徴をパッチサイズ p とストライド s を使用して取り出し、メモリバンク M に追加します。
貪欲なコアセット選択を適用します。これは、メモリバンクから最も代表的な要素を選び出し、ターゲットの数 l だけ保持するプロセスです。この選択には、射影 ψ を使用して、選ばれていないメモリ要素と最も遠い要素を見つけることによって行われます。
このアルゴリズムは、データから重要な特徴を効率的に選び出し、その特徴を用いて異常検出や分類などのタスクに利用することができるでしょう。特に、大量のデータから小さな記憶バンクを構築することによって、リアルタイムの処理やリソースが限られている環境での使用が想定されています。

3.1 アルゴリズムの詳細:

アルゴリズムのこの部分は、異常検出やその他の機械学習タスクにおいて、データから特徴を効率よく抽出し、記憶する手順を説明しています。以下に、各ステップをさらに詳細に説明します。

1.メモリバンクの初期化:

M ← {}: メモリバンク M を空のセットとして初期化します。このメモリバンクは後に、データから抽出された特徴のコレクションを保持します。

2. 特徴抽出とパッチの取り出し:

for xi ∈ χN do: 入力データセット χN の全要素 xi に対してループを実行します。
M ← M ∪ Ps,p(φj(xi)): 事前に訓練されたモデル φ を用いてデータ xi の特徴を抽出します。階層 j はモデル内の特定の層やレベルを指定するかもしれません。Ps,p はストライド s とパッチサイズ p を使用して特徴を取り出す関数です。これによって、データから一定のサイズと間隔で局所的な特徴を取り出し、それをメモリバンク M に追加します。

3. 貪欲なコアセット選択:

/ * Apply greedy coreset selection. */: コメントは、次のステップで貪欲なコアセット選択が適用されることを示しています。
MC ← {}: 新しいセット MC を初期化します。これは、選ばれたコアセット、つまり代表的な特徴のセットを保持します。
for i ∈ [0, ..., l − 1] do: ターゲットの数 l までループを実行します。これは、メモリバンクから選び出す特徴の数を指定します。
mi ← argmax min ||ψ(m) − ψ(n)||2: これは、既に選ばれたセット MC に含まれていないメモリ要素 m の中で、既に MC に含まれている要素 n と最も距離（この場合、ユークリッド距離）が大きい要素 m を見つける操作です。ψ は特徴を別の空間に射影する関数で、ここではデータの類似性や距離を計算するために使用されます。
MC ← MC ∪ {mi}: 選ばれた要素 mi をコアセット MC に追加します。
このプロセスにより、M は最終的に、入力データセット χN を代表する最も重要な特徴のみを含むコアセット MC に更新されます。これにより、データセットのサイズを大幅に削減しながら、その特徴的な情報を保持することができます。特にリソースが限られている環境や、リアルタイムでの処理が要求されるシナリオにおいて重要です。

参考文献

https://tech.anytech.co.jp/entry/2023/03/24/100000
https://zenn.dev/kwashizzz/articles/ml-anomaly-det-patchcore
https://techblog.leapmind.io/blog/20220701-introduction_to_patchcore/
https://scikit-learn.org/stable/modules/random_projection.html
https://www.chowagiken.co.jp/blog/padim-patchcore
https://arxiv.org/abs/2307.10792