構造化kNN

構造化k近傍法（SkNN）^{[ 1 ] [ 2 ] [ 3 ]}は、 k近傍法（k -NN） を一般化した機械学習アルゴリズムです。k - NNは二値分類、多クラス分類、回帰をサポートしていますが^{[ 4 ]}、 SkNNは一般的な構造化出力のための分類器のトレーニングを可能にします。

例えば、データサンプルは自然言語の文であり、出力は注釈付きの構文解析ツリーである。分類器のトレーニングは、正解となるサンプルと出力のペアを多数提示することによって行われる。トレーニング後、SkNNモデルは、新しい未知のサンプルインスタンスに対して対応する出力を予測できるようになる。つまり、自然言語の文が与えられると、分類器は最も可能性の高い構文解析ツリーを生成できる。

SkNNは、トレーニングセットとして、クラスラベルが付いた要素のシーケンスを受け入れます。要素の型は問いません。唯一の要件は、セット内の各要素ペア間の距離を示す定義済みのメトリック関数です。

SkNNは、各ノードがクラスラベルを表すグラフを作成するという考え方に基づいています。トレーニングセットに、対応するクラスを持つ2つの要素のシーケンスが存在する場合、ノードのペア間にエッジが存在します。SkNNトレーニングの最初のステップは、トレーニングシーケンスからこのようなグラフを構築することです。グラフには、文の開始と終了に対応する2つの特別なノードがあります。シーケンスがクラスCで始まる場合、ノードSTARTとノードCの間にエッジを作成する必要があります。

通常のk -NNと同様に、SkNNのトレーニングの第2段階では、トレーニングシーケンスの要素を特定の方法で格納します。トレーニングシーケンスの各要素は、シーケンス内の前の要素のクラスに関連付けられたノードに格納されます。すべての最初の要素はSTARTノードに格納されます。

SkNNによる入力シーケンスのラベリングは、ノードSTARTから始まるグラフ内の遷移シーケンスを見つけることから成ります。各遷移は、入力シーケンスの単一の要素に対応します。結果として、各要素のラベルは、遷移のターゲットノードのラベルとして決定されます。パスのコストは、すべての遷移の合計として定義され、ノードAからノードBへの遷移のコストは、現在の入力シーケンス要素からノードAに格納されているクラスBの最も近い要素までの距離になります。最適なパスの決定は、修正されたビタビアルゴリズムを使用して実行できます（元のアルゴリズムが確率の積を最大化するのとは異なり、距離の合計が最小化されます）。

• 実装例