murawakiのコメント: CRF (スコア 1) 2
言語は系列データなので、一般のグラフアルゴリズムよりも、系列データであることを利用した手法を使うことが多いです。
タグ付けで標準的なのは (linear chain) CRFです。
https://pytorch.org/tutorials/beginner/nlp/advanced_tutorial.html
https://pytorch-crf.readthedocs.io/en/stable/
トークンごとの分類器が吐く logit を CRF における emission スコアとみなしたうえで、transition スコアを追加していることになります。
BIタギングなら、(品詞の異なり数 x 2) ^ 2 大きさの transition table を訓練データから学習します。
B-a + I-b のような不正な系列は訓練データに出てこないので、普通に学習するだけテスト時に出てこなくなります。
これはこれでオーバーキル感がありますが、確立された手法なので使うことがあるといったところです。