岡野原大輔 『汎用的データにおける確率的言語モデルの抽出とその応用』

非自然言語データの上で確率的言語モデルを構築し、圧縮する。
単語分割（WX法）とクラス推定を、教師なし学習により行う。

まず、単語の最大長 n を与えた上で、
suffix array の一致数（辞書順ソートでの隣接接尾辞の最長共通接頭辞の長さ）の切り替わりを見て、
単語候補集合を得る。
候補はすべて n 文字以内。

第一段階の分割として、
圧縮率に関して貪欲に単語候補を選び、対象データを単語に置き換えていく。
圧縮率は、文字単位0-gram（ようするに文字数）に対する単語1-gramのエントロピーの比としている。
これにより、単語候補集合を用いた最適符号化の荒い近似が得られる。
ここでの単語出現確率を、ほんとうの最適符号化での単語出現確率の近似として、
次の動的計画法の適用に用いる。

対象文字列中の位置 i までの最適な分割は、
位置 i-1 までの最適な分割の最後の半端分を含む単語候補のうち、最適な分割を与える単語を選んだもの。
として動的計画法を適用する。
このときの評価は第一段階の分割における出現確率をもちいた、エントロピーの合計値。

品詞クラスタリングに相当する Class Model については省略。

比較：
プレーンデータを教師なしで単語分割する、という点は共通で、
候補の評価に用いる圧縮率、エントロピーもしくはパープレキシティは本質的に同じ。

計算効率の点では、WX法がはるかに優れる。

最適性の近似精度に関しては、
WX 法では荒い近似からより精密な近似を行っていることから優れているように思われるが、
第一段の近似の精度がどれほど信頼できるかにかかっている。
提案手法の貪欲な連結による近似との比較は実験的になされるしかない。

自然言語の統計的言語モデル構築を目的とした場合、
提案手法は分割法、より正確には分割のための（連結の）手順と、そこから導かれる辞書を生成し、
実際の言語モデル構築は既存のN-gram言語モデルツールキットにまかせる。

WX法によって自然言語の統計的言語モデルを構築しようとすると、
圧縮後（言語モデル構築後）に与えられた新たな文字列に対する分割の計算は明らかでなく、
何らかの付加的作業が必要。
新たな文字列をコーパスに加えて再分割、というのがもっともナイーブだが、
計算効率のメリットは薄れる。

WX法では単語の最大長の制限が過学習の歯止めになっていると思われるが、
提案手法では辞書サイズが歯止めになっている。
これらの制限は、ヒューリスティックに過学習を防ぐものであり、
どちらが優れているかは明らかでない。

候補の評価に関して、
提案手法は 2-gram エントロピーによる評価が可能となったが、
WX 法では明らかではない。
ただし、最適性に対してどのように近似しているかが明示されているWX法の枠組で
2-gram への拡張が自明でないことは、
提案手法の 2-gram への拡張が
貪欲探索において近似の精度を著しく落としていることを示唆するように思われ、
これが性能悪化の原因になったのかもしれない。

WX法では、単語の最大長が制限されている。
これは計算の効率、より高次のモデルへの移行を考慮したものだが、
自然言語への適用ではあまり問題にならないと思う。