集合的分類

ネットワーク理論では、集団分類は複数のオブジェクトのラベルを同時に予測することであり、各ラベルはオブジェクトの観測された特徴、その近傍の観測された特徴とラベル、およびその近傍の観測されていないラベルに関する情報を使用して予測されます。^[1]集団分類問題は、ランダム変数のネットワークの観点から定義され、ネットワーク構造がランダム変数間の関係を決定します。推論は、通常、ネットワーク内のノード間で情報を伝播して近似推論を実行することにより、複数のランダム変数に対して同時に実行されます。集団分類を使用するアプローチでは、推論を実行するときに関係情報を利用できます。集団分類の例には、ソーシャルネットワーク内の個人の属性（性別、年齢、政党所属など）の予測、ワールドワイドウェブでのウェブページの分類、科学出版物データセットでの論文の研究分野の推論などがあります。

従来、機械学習の主な焦点は分類問題を解決することです。(たとえば、電子メールのコレクションが与えられた場合、どれがスパムでどれがそうでないかを判断したいとします。) このタスクを実行する多くの機械学習モデルは、各アイテムを個別に分類しようとし、クラスラベルを個別に予測することに焦点を当てます。ただし、値を推測する必要があるラベルの予測精度は、関連するアイテムの正しいクラスラベルを知っていれば向上できます。たとえば、Web ページのトピックを予測するのは、そのページにリンクしている Web ページのトピックがわかれば簡単です。同様に、文の前の単語が名詞であることがわかれば、特定の単語が動詞である可能性が高くなります。単語の最初の数文字がわかれば、残りの文字を識別するのがはるかに簡単になります。多くの研究者が、各サンプルを個別に扱うのではなく、共同または集合的にサンプルを分類しようとする手法を提案しており、これらの手法により分類精度が大幅に向上しました。^{[1] [2]}

ソーシャル ネットワーク内のユーザーの政治的所属を推測するタスクを考えてみましょう。これらの所属の一部は観察され、残りは観察されません。各ユーザーには、プロフィール情報などのローカル フィーチャがあり、このソーシャル ネットワーク内の友人であるユーザー間にはリンクが存在します。ユーザーを集合的に分類しないアプローチでは、ネットワーク内の各ユーザーを個別に検討し、ローカル フィーチャを使用して政党の所属を推測します。集合的に分類するアプローチでは、友人であるユーザーは同様の政治的見解を持つ傾向があると想定し、ソーシャル ネットワークの豊富な関係構造を活用しながら、観察されていないすべての政党の所属を共同で推測できます。

ノードのラベルのサブセットに関する知識を使用して、ネットワーク内のノードにラベルを割り当てる半教師あり学習の問題を考えてみましょう。具体的には、ノードのセットとノード間の関係を表すエッジ セットを含むグラフ で表されるネットワークが与えられます。各ノードは、その属性、つまり特徴ベクトルとそのラベル (またはクラス)によって記述されます。 ${\displaystyle G}$${\displaystyle V}$${\displaystyle E}$${\displaystyle v_{i}\in V}$${\displaystyle x_{i}\in X}$${\displaystyle y_{i}\in Y}$

${\displaystyle V}$はさらに 2 つのノード セットに分けられます。は正しいラベル値 (観測変数) がわかっているノード セットで、 はラベルを推測する必要があるノードです。集合的な分類タスクは、 内のノードにラベル セットからのラベルを付けることです。 ${\displaystyle L}$${\displaystyle U}$${\displaystyle U}$${\displaystyle L=\{L_{1},\cdots L_{q}\}}$

このような設定では、従来の分類アルゴリズムは、データが何らかの分布 (iid) から独立して同一に抽出されると想定します。つまり、ラベルが観測されていないノードに対して推定されるラベルは、互いに独立しています。集合分類を実行するときは、この想定は行いません。代わりに、分類またはラベルを決定するために利用できる 3 つの異なるタイプの相関関係があります。 ${\displaystyle v}$

1. のラベルとの観測された属性との間の相関関係。特徴ベクトルを使用する従来の iid 分類器は、この相関関係を使用するアプローチの一例です。${\displaystyle v}$${\displaystyle v}$
2. のラベルと、 の近傍にあるノードの観測された属性 (観測されたラベルを含む)との間の相関関係。${\displaystyle v}$${\displaystyle v}$
3. のラベルと、 の近傍にあるオブジェクトの観測されていないラベルとの間の相関関係。${\displaystyle v}$${\displaystyle v}$

集合分類とは、上記の 3 種類の情報を使用して、相互にリンクされたオブジェクトのセットを統合して分類することを指します。

集団分類にはいくつかのアプローチが存在する。2つの主要な方法は反復法と確率的グラフィカルモデルに基づく方法である。^[3]

反復法の一般的な考え方は、個々のノードの予測を反復的に組み合わせて修正し、均衡点に到達することです。個々のノードの予測の更新が高速な操作である場合、これらの反復法の複雑さは、収束に必要な反復回数になります。収束と最適性は必ずしも数学的に保証されるわけではありませんが、実際には、これらのアプローチは、グラフ構造と問題の複雑さに応じて、通常、優れたソリューションに迅速に収束します。このセクションで説明する方法は、この反復アプローチの代表的なものです。

ネットワーク分類における自然な仮定は、隣接するノードは同じラベル（つまり、伝染または同質性）を持つ可能性が高いということです。ラベル伝播法を使用したノードの予測子は、隣接するラベルの加重平均です^[4]${\displaystyle V_{i}}$${\displaystyle Y_{N_{i}}}$

ラベル伝播は驚くほど効果的ですが、複雑な関係のダイナミクスを捉えられないこともあります。より洗練されたアプローチでは、より豊富な予測子を使用できます。ノードの特徴とその近傍の特徴とラベルに基づいてノードを分類するようにトレーニングされた分類器があるとします。反復分類では、各ノードに対してローカル分類器を使用します。ローカル分類器は、現在の予測に関する情報とノードの近傍に関する真実情報を使用し、ローカル予測がグローバルソリューションに収束するまで反復します。反復分類は、予測子の選択に依存しない「アルゴリズムフレームワーク」です。これにより、集合分類のための非常に多用途なツールになります。 ^{[5] [6] [7]}${\displaystyle h}$${\displaystyle v_{i}}$${\displaystyle X_{i}}$${\displaystyle X_{N_{i}}}$${\displaystyle Y_{N_{i}}}$${\displaystyle N_{i}}$

集団分類のもう 1 つのアプローチは、問題をグラフィカル モデルで表現し、グラフィカル モデリング アプローチの学習および推論手法を使用して正しい分類に到達することです。グラフィカル モデルは、共同の確率推論のツールであるため、集団分類に最適です。グラフィカル モデルは、確率分布のグラフィカル表現を特徴とし、ランダム変数はグラフ内のノードになります。グラフィカル モデルは、基礎となるグラフが有向グラフ (ベイジアン ネットワークやローカル分類器のコレクションなど) か無向グラフ (マルコフ ランダム フィールド(MRF) など)かによって大まかに分類できます。 ${\displaystyle P}$${\displaystyle G}$

ギブスサンプリングは、分布を近似するための一般的なフレームワークです。これは、分布の現在の推定値から反復的にサンプリングし、ターゲット（定常）分布に収束するマルコフ連鎖を構築するという点で、マルコフ連鎖モンテカルロアルゴリズムです。ギブスサンプリングの基本的な考え方は、固定回数の反復でローカル分類器を使用して、ノードのすべての値が与えられた場合に、ノードの最良のラベル推定値をサンプリングすることです。その後、それぞれについてラベルをサンプリングし、ノードのラベルをサンプリングした回数のカウント統計を維持します。このようなサンプルを定義済みの数収集した後、サンプル収集中に割り当てられた回数が最も多かったラベルを選択して、ノードの最良のラベル割り当てを出力します。 ^{[8] [9]}${\displaystyle y_{i}}$${\displaystyle N_{i}}$${\displaystyle f}$${\displaystyle y_{i}\in Y}$${\displaystyle l}$${\displaystyle y_{i}}$${\displaystyle y_{i}}$${\displaystyle y_{i}}$

特定の無向グラフィカルモデルでは、メッセージパッシングまたは信念伝播アルゴリズムを介して正確な推論を効率的に実行できます。^[10]これらのアルゴリズムは、単純な反復パターンに従います。各変数は、隣接する変数の周辺分布に関する「信念」を渡し、その後、自身の値に関する受信メッセージを使用して信念を更新します。真の周辺分布への収束は、ツリー構造のMRFでは保証されていますが、サイクルのあるMRFでは保証されていません。

統計的関係学習は、集団分類問題に対処するためによく使用されます。集団分類の設定には、さまざまな SRL 手法が適用されています。これらの手法には、確率的関係モデル (PRM) ^[11]などの直接的な手法、リンクベース分類などの結合条件モデル^{[12] 、}マルコフ論理ネットワーク(MLN) ^[13]や確率的ソフトロジック(PSL) ^[14] などの間接的な手法が含まれます。

集合的分類は、次のような関係構造を示す多くのドメインに適用されます。

• ソーシャルネットワーク分析では、悪意のあるユーザーの検出などのノード分類タスクに対する集合的なアプローチにより、ノード間の関係性に関する情報を活用できます。^{[15] [16]}
• エンティティ解決では、共著者関係を利用して論文の著者を特定することができます。^[17]
• 名前付きエンティティ認識では、いくつかのアプローチではこれをテキストシーケンスのラベル付け問題として扱い、通常は文中の隣接する単語のラベル間の依存関係の線形連鎖をモデル化する条件付きランダムフィールドを使用して、文中のすべての単語のラベルを共同で推論します。^[18]
• 文書分類では、例えば文書間の意味的類似性を集合的に利用して、特定の文書が同じクラスに属していることを示す信号として利用することができます。^[19]
• 計算生物学では、マルコフ確率場などのグラフィカルモデルを利用して、遺伝子などの生物学的実体間の関係を共同で推測します。^[20]
• コンピュータビジョンでは、例えば集団分類は複数の物体を同時に認識するために適用できる。^[21]

• 機械学習
• 分類
• 類似性（ネットワーク科学）
• グラフ（離散数学）
• 統計的関係学習
• ベイジアンネットワーク
• マルコフ確率場