中文分词词性和序列标注之CRF-5-参数优化
5 对数似然
$ \tilde{p} $是经验分布概率，由样本简单统计得到。
$$ \begin{align} L_\tilde{P}(P_w) &= \log \prod_{x,y}p(y|x)^{\tilde{p}(x,y)} \\ &= \sum_{x,y} \tilde{p}(x,y) \log p(y|x) \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_{k=1} w_k f_k(x,y) – \sum_{x} \tilde{p}(x) \log Z_w(x) \end{align} $$
5.1 改进的迭代尺度法
按极大估计优化，并且参考 MEMM IIS 完全相同的方法得到：
$$ \begin{align} \frac{\partial B}{\partial \delta_k} & = \sum_{x,y} \tilde{p}(x,y) f_k(x,y) – \sum_{x,y} \tilde{p}(x) p_w(y|x) f_k(x,y) \exp(\delta_k f^\#(x,y)) \\ & = E_{\tilde{p}}(f_k) – \sum_{x,y} \tilde{p}(x) p_w(y|x) f_k(x,y) \exp(\delta_k f^\#(x,y)) \end{align} $$
$$ \begin{align} f_k(y,x) &= \sum_i f_k(y_{i-1}, y_i, x_i) \\ f^\#(x,y) &= \sum_k \sum_i f_k(y_{i-1}, y_i, x_i) \end{align} $$
5.1.1
因每组(x,y) 特征数量并不相同。所以设置$ M - f^\#(x,y) \geq 0 $ 于是可用下式更新.
$$ \delta_k = \frac{1}{M} \log \frac{E_{\tilde{p}(f_k)}}{E_p(f_k)} $$
5.2 拟牛顿法
按惯例定义为最小化对数似然。为减轻过拟合和提高优化速度, 加上$L2$正则项。
$$ \begin{align} min_w f(w) &= -L_\tilde{P}(P_w) + \sum_k \frac{w_k^2}{2 \sigma^2 } \\ &= -\log \prod_{x,y}p(y|x)^{\tilde{p}(x,y)} + \sum_k \frac{w_k^2}{2 \sigma^2 } \\ &= -\sum_{x,y} \tilde{p}(x,y) \log p(y|x) + \sum_k \frac{w_k^2}{2 \sigma^2 } \\ &= \sum_{x} \tilde{p}(x) \log Z_w(x) - \sum_{x,y} \tilde{p}(x,y) \sum_k w_k f_k(x,y) + \sum_k \frac{w_k^2}{2 \sigma^2 } \end{align} $$
梯度：
$$ \nabla f(w) = \left[\frac{\partial f(w)}{\partial w_1},\frac{\partial f(w)}{\partial w_2},\frac{\partial f(w)}{\partial w_3},\cdots \right]^T $$
$$ \begin{align} \frac{\partial f(w)}{\partial w_k} &= \sum_{x,y} \tilde{p}(x) p_w(y|x) f_k(x,y) – \sum_{x,y} \tilde{p}(x,y) f_k(x,y) + \frac{w_k}{\sigma^2} \\ &= \sum_{x,y} \tilde{p}(x) p_w(y|x) \sum_i f_k(y_{i-1}, y_i, x_i) \\ &\quad - \sum_{x, y} \tilde{p}(x,y) \sum_i f_k(y_{i-1}, y_i, x_i) + \frac{w_k}{\sigma^2} \\ &= \sum_x \tilde{p}(x) \sum_i \sum_{y_{i-1}, y_i} \sum_{y_1,\cdots, y_{i-2}, y_{i+1}, \cdots, y_n} p_w(y_{i-1}, y_i | x) p_w(y_1,\cdots, y_{i-2}, y_{i+1}, \cdots, y_n | x) f_k(y_{i-1}, y_i, x_i) \\ &\quad - \sum_{x, y} \tilde{p}(x,y) \sum_i f_k(y_{i-1}, y_i, x_i) + \frac{w_k}{\sigma^2} \\ &= \sum_x \tilde{p}(x) \sum_i \sum_{s, s^\prime} p_w(y_{i-1}=s, y_i=s^\prime | x) f_k(s, s^\prime, x_i) \\ &\quad - \sum_{x, y} \tilde{p}(x,y) \sum_i f_k(y_{i-1}, y_i, x_i) + \frac{w_k}{\sigma^2} \end{align} $$
正则化参数依赖于训练数据集大小，通常情况下$ \sigma^2=10 $，此值需扫描尝试,
参考资料：
[1] 李航; 统计机器学习
[2] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models
[3] Lafferty, J., McCallum, A., Pereira, F. (2001). “Conditional random fields: Probabilistic models for segmenting and labeling sequence data”. Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289.
[4] An Introduction to Conditional Random Fields Charles Sutton1 and Andrew McCallum2