構造化予測

構造化予測または構造化出力学習は、離散値や実数値ではなく構造化されたオブジェクトを予測する教師あり機械学習技術の総称です。 ^[1]

一般的に使用される教師あり学習手法と同様に、構造化予測モデルは通常、予測値が真実値と比較される観測データによってトレーニングされ、これを使用してモデルパラメータが調整されます。モデルの複雑さと予測変数の相互関係により、モデルのトレーニングと推論のプロセスは計算上実行不可能な場合が多く、そのため近似推論と学習方法が使用されます。

応用例としては、自然言語の文を構文木などの構文表現に変換する問題が挙げられます。これは、構造化出力ドメインがすべての可能な構文木の集合である構造化予測問題^{[2]として考えることができます。構造化予測は、}バイオインフォマティクス、自然言語処理(NLP)、音声認識、コンピュータービジョンなど、さまざまな分野で使用されています。

シーケンス タグ付けは、入力データが連続していることが多い NLP でよく見られる問題の一種で、たとえばテキストの文などです。シーケンス タグ付けの問題は、品詞タグ付け(POS タグ付け) や固有表現認識など、さまざまな形で現れます。たとえば、POS タグ付けでは、シーケンス内の各単語に、単語の種類を表す クラス ラベルを「タグ付け」する必要があります。

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

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

確率的グラフィカル モデルは、構造化予測モデルの大きなクラスを形成します。特に、ベイジアン ネットワークとランダム フィールドが人気です。構造化予測の他のアルゴリズムとモデルには、帰納的論理プログラミング、事例ベース推論、構造化 SVM、マルコフ論理ネットワーク、確率的ソフト ロジック、制約条件モデルなどがあります。主な手法は次のとおりです。

• 条件付きランダムフィールド
• 構造化サポートベクターマシン
• 構造化されたk近傍法
• リカレントニューラルネットワーク、特にエルマンネットワーク。

一般的な構造化予測アルゴリズムを理解する最も簡単な方法の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 の検索は、指数関数的に大きな候補セットを 徹底的に検索するのではなく、 Viterbi やmax-sumなどのアルゴリズムを使用して行われます。${\displaystyle {GEN}({x})}$

学習の考え方は、マルチクラスパーセプトロンの場合と似ています。

• ノア・スミス、「言語構造予測」、2011 年。
• マイケル・コリンズ、「隠れマルコフモデルの識別的トレーニング法」、2002 年。

• コリンズ構造化パーセプトロンの実装