Mathematical Morphology in Machine Learning

技術要約：機械学習における数学形態学

問題提起
数学形態学（Mathematical Morphology: MM）は、形状、サイズ、凸性に基づいてグラフィカルな対象を分析するための視覚コンピューティングにおける確立された理論であるが、機械学習への応用は依然として十分に活用されていない。既存の機械学習技術は、形状や密度に関する情報を十分に活用できていないことが多い。さらに、現在のクラスタリングおよび分類手法は、MMの原則に完全には準拠していないヒューリスティックに依存しているか、あるいは、フラクタル情報、形状、および密度を同時にモデリングする能力を欠いている。加えて、離散的な環境（GPUベースの処理など）において、標準的な距離指標はトレードオフを提示する。ユークリッド距離は計算コストが高く量子化を必要とする一方、チェビシェフ距離やマンハッタン距離は高速ではあるが「正方形」の性質を持ち、ユークリッド距離の円形の反復を効果的に近似できない。

手法
本論文は、以下の3つの主要コンポーネントを通じて、数学形態学を機械学習に統合するフレームワークを提案している。

1. k-形態学的集合（k-MS）クラスタリングアルゴリズム:

   • このアルゴリズムは、従来のバイナリ形態学クラスタリングアルゴリズムとは異なり、二値演算ではなく形態学的再構成を利用する。
   • データインスタンスがマッピングされたグリッド上で動作する。構造要素 $B$（初期状態はゼロを含む）とマスク $M$ を使用して再構成を行う。
   • アルゴリズムは、構造要素のサイズを制御するために内部変数 $\delta$ を用いる。$\delta$ を反復的に増加させることで、冪等状態に達するか、あらかじめ定義された最大クラスター数（$k$）に近づくまでクラスターを成長させる。
   • 固有のクラスターインデックスの数が $k$ を超えた場合、$\delta$ は増分され、再構成が非冪等（クラスターの結合）になった場合は、$\delta$ を1にリセットしてプロセスを繰り返す。
   • この手法は、追加の処理コストなしに、ノイズを小さな独立したクラスターへと本質的にセグメント化する。

2. 新規距離指標:

   • 離散空間（特にGPU実装用）における近傍反復を最適化するため、新しい距離指標を提案する。
   • これは、チェビシェフ距離とミンコフスキー距離の加重結合である（式1: $d_{R^p}(x,y) = w_1 \sum |x_i - y_i|^p + w_2 \max |x_i - y_i|$）。
   • 重み $w_1$ と $w_2$ およびパラメータ $p$ を調整することで、この指標はチェビシェフまたはミンコフスキーの挙動へと収束させることができる。
   • 2次元（$R^2$）において、この距離は八角形を生成し、マンハッタン距離やチェビシェフ距離が生成する正方形よりも、幾何学的にユークリッド距離の円形に近い形状となる。

3. 形態学的分類器:

   • 著者らは、ラベルのない空間を覆うために膨張（dilation）を用いて訓練インスタンスを成長させる分類器を提案している。
   • これらの分類器は、グリッドセルが同時に成長する並列処理を活用するために、グラフィックス処理装置（GPU）上に実装されている。
   • 成長中に交差が発生した場合、投票スキームによってラベルが決定される。

主な貢献

• k-MS アルゴリズム: 形状と密度を保持し、作成可能な最大クラスター数の本質的な感覚（$k$ に関わらず）を提供し、追加のオーバーヘッドなしにノイズを除去するクラスタリング手法。
• ハイブリッド距離指標: チェビシェフ距離とミンコフスキー距離を組み合わせた新しい指標であり、「正方形」の距離の計算効率とユークリッド距離の幾何学的精度のバランスを実現。
• GPU最適化実装: 低レベルのGPU環境に特化した形態学的分類器および距離計算の開発。これにより、低速なカーネルアクセスや不定のカーネルサイズを回避する。
• 包括的な評価: 33個のUCIデータセットを用いた、提案された距離指標のk-最近傍法（k-NN）による広範なテスト。

結果

• クラスタリングの効率: k-MSアルゴリズムは、ノイズ除去や形状保存といった独自の機能を提供しつつ、最先端の密度ベースのクラスタリング手法よりも高速であることが判明した。並列k-means（CPU）との時間分析比較において、k-MSは、特にクラスター数が増加するにつれて早期終了の最適化により、競争力のある、あるいは優れた性能を示した。
• 距離指標の性能:
  • 速度: $Z^2$ における離散近傍反復タスクにおいて、提案された距離はマンハッタン距離よりも約1.3倍速く、ユークリッド距離よりも329.5倍高速であった。
  • 精度: 33のUCIデータセットに対するk-NNでの評価において、提案された距離は、14の他の距離の平均よりも高い精度を33ケース中26ケースで達成した。また、33ケース中9ケースで単独最高の精度を記録した。
• 視覚的クラスタリング: ノイズの多いデータセットにおいて、k-MSは真のクラスターと外れ値を正常に分離したが、他のアルゴリズム（Chameleonなど）は外れ値を真のクラスターにグループ化してしまうことがあり、また他のアルゴリズム（Mitosisなど）はノイズの分離に失敗した。

意義と主張
著者らは、本研究が、ヒューリスティックな接続を超え、完全に数学形態学の技術に依拠した分類およびクラスタリング手法の最初の提案であると主張している。論文は、現在の文献において、形状、密度、およびフラクタル情報を同時に適切にモデリングできる分類器は他に存在しないと断言している。

本研究の意義は、視覚コンピューティング理論と機械学習の間の溝を埋めることにあり、形状と密度に関して理論的に健全であるだけでなく、現代のハードウェア（GPU）にとって計算効率の高いツールを提供することにある。提案された距離指標は、ユークリッド距離が遅すぎ、マンハッタン/チェビシェフ距離が十分な幾何学的忠実性を欠く高パフォーマンス・コンピューティング環境における実用的な解決策として強調されている。著者らは、これらの貢献がすでに Pattern Recognition や Pattern Recognition Letters といった定評のあるジャーナルへの複数の出版につながっていることを述べている。