Fast exact maximum likelihood estimation for mixture of language models

http://dx.doi.org/10.1145/1277741.1277948
情報検索の一部（）で使われている、片方の分布が未知の混合ユニグラムモデルにおいて、
厳密かつ、線形時間な解法が得られた。

p, q を多項分布に従う確率変数、\alpha を実数とするとき、
r = \alpha p + (1-\alpha) q
（rはpとqの混合、または線形補完と呼ばれる）

r の標本値がたくさん
p の分布（パラメタ）
\alpha の値
がわかっているときに、q のパラメタ（多項分布の各項の重み）を求めるのが問題。

証明が面白い。
でも、正当性きちんと検証できるほど読み込めてはいない。

実用的なインパクトはあまりないと思うけれど、
安易な「EMで近似解」ではないアプローチとして、価値があると思う。