フェルマー距離にもとづく高次元セミ教師あり分類

要旨: ラベルなしデータが大量である一方、ラベル付きデータは限られているという状況で生じる半教師あり分類は、機械学習の応用においてしばしば現れます。本研究では、準解析的データ（高次元データ）に対して、マンフォールド仮定とクラスター仮定を活用することでこの課題に取り組みます。クラスター仮定を自然に符号化する密度に敏感な距離であるフェルマー距離に基づき、加重付き k 近傍（NN）分類器と、MDS（多次元尺度構成法）に誘導される分類器を提案します。大きな目標次元を用いる MDS により、複雑なマンフォールドデータに対して線形分類器を効果的に適用できるようになります。理論的に、クラスター内での期待超過リスクに対する鋭い下界を導出し、真のフェルマー距離を用いた加重付き k-NN 分類器がミニマックス最適であることを証明します。さらに、フェルマー距離の推定に起因する誤差が、プールされたサンプルサイズに対して指数関数的に減衰することを示すことで、ラベルなしデータの有用性を明示的に定量化します。この減衰率は、関連する文献で報告されている率よりもはるかに速いものです。合成データおよび実データに対する大規模な実験により、提案手法が、最先端のグラフベース半教師あり分類器と比べて競争的、あるいは優れた性能を示すことが確認されます。