構造化予測

シーケンスタグ付けは、自然言語処理（NLP）でよく見られる問題群であり、入力データはテキストの文など、多くの場合、順序立てて並んでいます。シーケンスタグ付けの問題は、品詞タグ付け（POSタグ付け）や固有表現認識など、さまざまな形で現れます。たとえば、POSタグ付けでは、シーケンス内の各単語に、単語の種類を表すクラスラベルを「タグ付け」する必要があります。

この問題の主な課題は、曖昧さを解消することです。上記の例では、英語の「sentence」と「tagged」は動詞にもなり得ます。

この問題は個々のトークンを分類することで解決できますが、このアプローチではタグが独立して発生しないという経験的事実が考慮されていません。実際には、各タグは前の単語のタグに強い条件付き依存性を示します。この事実は、隠れマルコフモデルや条件付き確率場^{[ 2 ]}などのシーケンスモデルで利用でき、ビタビアルゴリズムを使用して（個々のタグだけでなく）文全体のタグシーケンスを予測します。

一般的な構造化予測のためのアルゴリズムを理解する最も簡単な方法の 1 つは、コリンズによる構造化パーセプトロンです。^{[ 3 ]}このアルゴリズムは、線形分類器を学習するためのパーセプトロンアルゴリズムと推論アルゴリズム (シーケンス データに使用される場合は、従来はビタビ アルゴリズム) を組み合わせたもので、抽象的に次のように説明できます。

1. まず、関数を定義します。${\displaystyle \phi (x,y)}$トレーニングサンプルをマッピングする${\displaystyle x}$そして候補者の予測${\displaystyle y}$長さのベクトルへ${\displaystyle n}$（${\displaystyle x}$そして${\displaystyle y}$どのような構造でも構わない。${\displaystyle n}$問題に依存しますが、各モデルごとに固定する必要があります。${\displaystyle GEN}$候補予測を生成する関数である。
2. それから：

させて${\displaystyle w}$長さの重みベクトルとする${\displaystyle n}$

あらかじめ定められた回数の反復処理について：

各サンプルについて${\displaystyle x}$真の出力を持つトレーニングセットにおいて${\displaystyle t}$:

予測を立てる${\displaystyle {\hat {y}}}$:${\displaystyle {\hat {y}}={\operatorname {arg\,max} }\,\{y\in GEN(x)\}\,(w^{T},\phi (x,y))}$

アップデート${\displaystyle w}$（から${\displaystyle {\hat {y}}}$に向かって${\displaystyle t}$):${\displaystyle w=w+c(-\phi (x,{\hat {y}})+\phi (x,t))}$、 どこ${\displaystyle c}$は学習率です。

実際には、argmax を見つけるには${\displaystyle {GEN}({x})}$これは、指数関数的に大きな候補セットを網羅的に探索するのではなく、ビタビ法や最大和法などのアルゴリズムを使用して行われます。

学習の考え方は、多クラスパーセプトロンのそれと似ている。