Skip to content
検索結果に戻る

ラベル伝播

提唱者
Zhu, X. & Ghahramani, Z.
年
2002
種類
Graph-based semi-supervised classification

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

文字サイズ

何をする手法か?

ラベル伝播(Label Propagation)は、2002年にZhuとGhahramaniによって導入されたグラフベースの半教師あり学習アルゴリズムであり、少数のラベル付きノードから多数のラベルなしノードへクラスラベルを伝播させる。これは、類似性グラフのエッジに沿ってラベル情報を反復的に拡散させることで行われ、データの多様体構造を利用する。

手法の背後にある直感

少数の人々が既にカテゴリに割り当てられているソーシャルネットワークを想像してほしい。噂は自然に広がる:各人は、近隣の最も一般的なラベルを採用する傾向がある。ラベル伝播はこの直感を形式化する。それは、類似したデータポイントが強いエッジで接続される重み付きグラフを構築し、既知のラベルがステップバイステップで外側に流れ、全てのラベルなしポイントが分類されるのに十分な信号を吸収するまで拡散させる。拡散は、任意の決定境界ではなく、データの幾何学的構造に従うため、ラベル付き例が少ない場合でも非常に正確な予測を生成できる。

歴史学

ラベル伝播は、Xiaojin (Jerry) ZhuとZoubin Ghahramaniによって、2002年のカーネギーメロン大学技術報告書(CMU-CALD-02-107)で導入された。翌年、Zhu、Ghahramani、John Laffertyは、ICML 2003で密接に関連するガウス場と調和関数フレームワークを発表し、ランダムウォークとガウスマルコフ確率場を介した確率的解釈を提供した。これらの研究は、2000年代半ばを通じてグラフベースの半教師あり手法の波を触発した。Dengyong Zhouと共同研究者は2004年にラベルスプレッディング(Label Spreading)を提案した。これは、ラベル付き注釈に対するロバスト性を提供する、ラベル情報がクランプされたラベルを部分的に上書きすることを可能にする正則化されたバリアントである。両手法は現在、半教師あり学習ベンチマークの標準的なベースラインとなっており、広く使用されている機械学習ライブラリに含まれている。2010年代のグラフニューラルネットワークの台頭に伴い、ラベル伝播は概念的な前駆体および競争力のあるベースラインとなり、その単純さと閉形式の保証のために依然として引用されている。

使うべき場面

ラベル伝播は、ラベル付き例がデータセット全体のサイズに対して少ない場合、類似性グラフが捉えることができるクラスタまたは多様体構造の基盤がある場合、そして平滑性仮説(特徴空間内の近くの点は同じラベルを共有する傾向がある)が成り立つ理由がある場合に適切である。典型的なシナリオには、注釈付きドキュメントが少ないテキスト分類、疎な人間のラベルを持つ画像分類、およびネットワークノード分類が含まれる。この手法は、グラフが連結であること(または少なくとも全てのラベルなしノードがラベル付きノードから到達可能であること)を必要とする。特徴空間が意味的類似性を反映しない場合、決定境界が密な領域を横切る場合、または全てのデータが既にラベル付けされている場合には適さない。

限界と注意点

  • スケーラビリティ:大規模データセットに対して、疎近似なしではn x n重み行列の格納と操作は実行不可能である。
  • グラフ構築は、カーネル帯域幅σと近傍サイズkの選択に敏感であり、不適切な選択は精度を大幅に低下させる。
  • 平滑性(クラスタ)仮説を仮定する:これを違反すると(決定境界が密な領域を通過する場合)、体系的な誤分類につながる。
  • デフォルトで転移学習的:新しい、未知のテストポイントの予測には、アルゴリズムの再実行または帰納的拡張が必要である。
  • ラベルなしノードのラベルノイズが伝播し、グラフの大部分を破損させる可能性がある。

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

強み

  • ラベル付き例が非常に少ない場合でも、高い精度が得られ、ラベルなしデータを効果的に活用する。
  • 閉形式の収束保証:反復更新は常に一意の不動点に到達する。
  • 追加の変更なしに、自然にマルチクラス問題を処理する。
  • グラフ拡散と調和解析に根ざした直感的な幾何学的解釈。
  • グラフ構築の選択(カーネル帯域幅、近傍サイズ)を超えて最適化するモデルパラメータがない。

応用

  • 文書のごく一部のみが人間によって割り当てられたラベルを持つ場合の、テキストおよび文書分類。
  • 手動ラベリングが高価で、ラベルなし画像が豊富にある場合の、画像またはビデオ注釈。
  • ソーシャルネットワークおよび引用グラフのノード分類(例:ユーザーの興味や論文のトピックの推測)。
  • 部分的に注釈付けされた生物学的ネットワークからの遺伝子機能またはタンパク質相互作用の役割の予測におけるバイオインフォマティクス。
  • 類似性グラフを通じて既知の正常/異常ラベルを伝播することによる、半教師あり異常検出。

使い方

使い方

1

全てのデータポイント(ラベル付きとラベルなしの両方)上に重み付き類似性グラフが構築される。一般的な選択肢はガウス(RBF)カーネルである:エッジの重みW_ijは、帯域幅パラメータσによって制御される、ポイントiとjの間のユークリッド距離の二乗の減少関数である。k最近傍またはε半径近傍のみが保持されるため、グラフは疎のままである。

数式
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

重み行列Wは、行確率的遷移行列Tを生成するために列正規化される。ここで、各エントリT_ijは、ノードjからノードiへラベル情報が流れる確率を表す。これにより、各ノードが受信する総影響力が1に合計されることが保証される。

数式
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

初期ラベル行列F(クラスごとに1列)から開始して、アルゴリズムは反復する:FをTで乗算し、次にラベル付きノードに対応する行を実際のワンホットラベルY_Lにクランプする。このクランプは、既知のラベルがドリフトするのを防ぎ、吸収境界条件として機能する。反復は、Fのラベルなしエントリが収束するまで繰り返される。

数式
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

ラベルなしブロックF_U*の不動点解は、(I - T_UU)^{-1} T_UL Y_Lとして閉形式で与えられる。ここで、T_UUはラベルなしノード間の遷移の部分行列であり、T_ULはラベル付きからラベルなしノードへの遷移を捉える。実際には、行列の逆算を回避するため、大規模グラフでは反復バージョンが好まれる。どちらの経路も同じ一意の解を生成する。

数式
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

よくある落とし穴

  • 疎近似なしの完全連結グラフを使用すること。これは局所構造を不明瞭にし、大規模では計算上実行不可能である。
  • ラベル付きセットでクロスバリデーションせずにデフォルトでσを選択すること。これにより、過剰または過小な平滑化されたラベル分布が生じる。
  • クラス不均衡の無視:1つのクラスがラベル付きセットを支配する場合、そのラベルがグラフ全体に氾濫する。再重み付けまたはサンプリングが必要である。
  • 転移学習的な予測を訓練済みモデルとして扱い、帰納的ラッパーなしで新しいポイントに適用すること。
  • グラフ接続性のチェックの失敗:孤立したコンポーネントのラベルなしノードは信号を受け取らず、均一なクラス確率にデフォルトする。

よくある質問

ラベル伝播とラベルスプレッディングの違いは何ですか?

Zhouら(2004)によって提案されたラベルスプレッディングは、各ノードが初期ラベルを保持する度合いと近傍のラベルを採用する度合いを制御する正則化パラメータαを導入する。古典的なラベル伝播では、ラベル付きノードは厳密にクランプされ、完全に吸収される。ラベルスプレッディングは、ラベル付きノードが部分的に上書きされることを可能にし、追加のハイパーパラメータ1つを犠牲にして、ラベルノイズに対するロバスト性を高める。

ラベル伝播は大規模データセットにスケールしますか?

単純な閉形式解は(n_U x n_U)行列の逆算を必要とし、これは大規模nには実行不可能である。実際には、疎なk最近傍またはε半径グラフはメモリをO(nk)に削減し、反復更新はその後、反復ごとのエッジ数に対してほぼ線形にスケールする。非常に大規模なグラフの場合、近似最近傍手法とミニバッチバリアントが使用される。

いくつのラベル付き例が必要ですか?

ラベル伝播は、極端にラベルが少ない状況のために特別に設計されている。グラフ構造がクラス境界と一致していれば、クラスごとに1つのラベル付きノードだけでも意味のある予測を生成できるが、信頼性のためにクラスごとに少なくとも数個のラベル付き例があることが強く推奨される。パフォーマンスは、ラベルノイズが増加するにつれて、またはグラフがクラスメンバーシップについてあまり情報を提供しなくなるにつれて低下する。

ラベル伝播は新しい、未知のデータポイントで予測できますか?

標準的な転移学習形式では、いいえ。アルゴリズムは固定グラフ上で動作し、そのグラフ外での予測メカニズムを持たない。帰納的用途には、新しいポイントを既存のグラフ内のk最近傍に接続して部分的な伝播ステップを実行するか、収束したラベル行列を使用して2番目のステージとして標準的な教師あり分類器を訓練する一般的なアプローチがある。

関連する手法

参考文献

  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. Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.

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

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