Skip to content
検索結果に戻る

半教師ありK近傍法

提唱者
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
年
2002 (semi-supervised extension); 1967 (KNN base)
種類
Semi-supervised classifier / label propagation
系統
Machine learning

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

半教師ありKNNは、古典的なK近傍法アルゴリズムを拡張し、少数のラベル付きデータセットと大量のラベルなしデータを活用します。すべての観測値にわたってKNNグラフを構築し、既知のラベルをグラフのエッジを通じて伝播させることで、すべてのサンプルに高価な手動アノテーションを必要とせずに、ラベルなし点のラベルを推論します。

手法の背後にある直感

ごく一部の生徒だけが名札を付けていて、残りは匿名である教室を想像してみてください。標準的なKNNは、近くにいる少数の名札付きの隣人を見ることでしか匿名生徒を分類できません。一方、半教師ありKNNは、部屋全体をネットワークとしてマッピングします。各生徒は最も近い隣人とつながっており、名札付きの生徒からインクが濡れた紙に広がるようにラベルが外側に伝播します。このネットワークはデータの全体的な構造を捉えているため、ラベルは、ラベルなしの大部分を無視するのではなく、根底にある幾何学的構造を尊重する原理的な方法でラベルなし点に到達します。

歴史学

KNNグラフ上のラベル伝播は、VapnikのトランスダクティブSVMと初期のグラフベースの拡散のアイデアに基づいて、ZhuとGhahramaniによって2002年に体系化されました。このフレームワークは、MIT Pressの書籍『Semi-Supervised Learning』(Chapelle et al., 2006)で統合され、これが標準的な参考文献となっています。その後、スケーラブルな近似KNNライブラリ(FAISS、Annoy)により、このアプローチは数百万の点に対して実用的になり、半教師あり画像およびテキスト分類の強力なベースラインとして引き続き使用されています。

使うべき場面

半教師ありKNNは、同じ分布から得られた少数のラベル付きセットと大量のラベルなしプールがあり、データが比較的低次元空間(約50未満の特徴)に存在し、隣接する点が同じクラスを共有すると考えられる場合に使用します。画像パッチ分類、スパースなアノテーションを持つテキスト分類、および専門家によるラベリングが高価な医療スクリーニングタスクに適しています。ラベル付きデータとラベルなしデータが異なる分布から得られる場合(共変量シフト)、特徴空間が非常に高次元である場合(KNNグラフが信頼できなくなる)、データセットが十分に小さく、完全に教師ありKNNで十分な場合、またはクラス境界がデータの局所的な密度構造と一致しない場合は避けてください。

限界と注意点

  • 近似最近傍法を使用しない限り、グラフ構築はデータセットサイズに対して二次的にスケールします。
  • 距離指標が識別力を失う高次元空間では、性能が急激に低下します。
  • ラベル付きデータとラベルなしデータが同じ分布から抽出されることを前提としています。共変量シフトはメソッドを破綻させます。
  • k、エッジ重みの帯域幅、および伝播混合パラメータの慎重なチューニングが必要です。
  • ラベル伝播は、グラフの大部分にわたって初期のラベリングエラーを増幅する可能性があります。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 安価なラベルなしデータを活用して、ラベル付きセット単独で可能な範囲を超える精度を向上させます。
  • パラメトリックモデルの仮定なし:局所的な近傍の幾何学的構造のみに依存します。
  • 変更なしで多クラス問題を自然に処理します。
  • KNNグラフの構築は透過的で検査が容易です。
  • クラスが特徴空間でコンパクトで明確に分離されたクラスターを形成する場合にうまく機能します。

応用

  • 少数のラベル付き画像と大量のラベルなしコーパスを用いた画像分類。
  • 手動ラベリングが高価なテキストおよび文書分類。
  • 限られた専門家のアノテーションによる医療記録または病理スライド分類。
  • 確認済みの不正事例が少数しか利用できない場合の不正検出。
  • スパースなグラウンドトゥルースイベントを持つ産業用IoT設定でのセンサーデータラベリング。

使い方

使い方

1

ラベル付きとラベルなしの両方のすべての観測値にわたってグラフが構築されます。各ノードは1つのデータ点に対応し、有向または無向のエッジが特徴空間における各ノードのk個の最近傍と接続します。kの選択は、ラベルが局所的に伝播するか、大域的に伝播するかを制御します。kが小さいと伝播は密接に保たれ、kが大きいとラベルはより大きなギャップを越えて伝播できます。

2

エッジの重みは、接続されたノード間の類似性の強さを捉え、通常は特徴ベクトル間のユークリッド距離にガウス(RBF)カーネルを適用することで計算されます。帯域幅パラメータsigmaは、距離とともに類似性がどれだけ速く減衰するかを制御します。より強いエッジは、伝播中により容易にラベルを伝達します。

数式
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

ラベルは、ラベル付きノードからラベルなしの隣接ノードへ反復的に伝播されます。各反復で、すべてのノードは、隣接ノードの現在の分布と自身の初期ラベル(ラベル付きの場合)の重み付き組み合わせとして、そのソフトラベル分布を更新します。混合パラメータalphaは、グラフ構造の影響とハードラベルの影響のバランスを取り、分布が収束するまで反復が続行されます。

数式
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

伝播が収束すると、各ラベルなしノードには、収束した分布で最も高いソフトラベルスコアを持つクラスが割り当てられます。ラベル付きノードは、その真のラベルに固定されたままであるため、既知のラベルが上書きされることはありません。

数式
\hat{y}_i = \arg\max_c F_{ic}

よくある落とし穴

  • 特徴を正規化せずにKNNグラフを構築し、高分散の特徴が距離計算を支配してしまう。
  • kを大きすぎると設定し、真のクラス境界を平滑化し、過度に平滑化されたラベル分布を生成してしまう。
  • ラベルなしデータがラベル付きセットに対して分布外である可能性を無視する。
  • ラベルなしノードの精度を、偏りのないテストセット推定値であるかのように報告する — ラベルなしノードはトレーニング中にグラフに漏洩している。
  • 収束チェックをスキップし、固定された任意の数の伝播反復を使用する。

よくある質問

kはどのように選択すればよいですか?

kを5〜15の範囲で開始し、ホールドアウトされたラベル付き検証精度によって調整します。kが小さいほど、よりシャープで局所的な境界が得られます。kが大きいほど、ラベルはより遠くまで伝播できますが、真のクラス境界を越えるリスクがあります。

ほとんどのデータがラベルなしの場合、この方法を正直に評価できますか?

グラフに決して追加されない専用のラベル付きテストセットを保持します。グラフ内のノード(ラベルなしノードであっても)はトレーニングの一部であるため、グラフ構築に参加するラベル付きノードはテストポイントとして機能してはなりません。

データセットが大きすぎて完全なKNNグラフを構築できない場合はどうすればよいですか?

FAISSやAnnoyなどの近似最近傍ライブラリを使用して、O(n^2)ではなくO(n log n)でグラフを構築し、そのスパースな近似グラフ上でラベル伝播を適用します。

半教師ありKNNは常に教師ありKNNを上回りますか?

必ずしもそうではありません。ラベルなしデータが分布外であるか、特徴空間が非常に高次元である場合、グラフはノイズが多く、伝播が性能を損なう可能性があります。ラベルなしデータからの利点を主張する前に、常に教師ありKNNベースラインと比較してください。

これはscikit-learnのラベル伝播またはラベル拡散と同じですか?

密接に関連しています。scikit-learnのLabelPropagationとLabelSpreadingは、KNNまたはRBFカーネルグラフを使用してZhuとGhahramaniのフレームワークを実装しているため、ここで説明されているメソッドの直接的な実装です。

関連する手法

参考文献

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    出版物の文献を開く
    コピーしました。
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN:978-0-262-03358-9
    コピーしました。