# 生物信息之ME, HMM, MEMM, CRF

f(x,y) = 1 如果x,y满足一些条件，比如x=记者*,y＝人名
0 otherwise

(最大熵模型里的特征概念不同于模式识别里的特征，这里的特征即特征函数，通常是二值函数，也有直接定义成实数的，比如 jeon-sigir06里直接把f定义为KDE距离，不是很明白那样定义的好处。)

E_p(f) = E_{tilde p}(f)

E_p(f) = sum_{x, y}p(x, y)f(x, y) = sum_{x, y}p(x)p(y|x)f(x,y) approx sum_{x, y} tilde p(x)p(y|x)f(x,y)
tilde p(f) = sum_{x, y} tilde p(x, y)f(x, y),

H(p)=-sum_{x,y} tilde p(x) p(y|x) log p(y|x)

p* =argmax_{p in P} -sum{x, y} p(y|x)tilde p(x) log p(y|x)
where P={p(y|x) | all f_i : sum_{x,y}p(y|x)tilde p(x)f_i(x,y) = sum_{x,y}tilde p(x,y)f_i(x,y), all x : sum_y p(y|x) = 1}

p(y|x) = exp(sum_i lambda_i f_i(x,y)) / Zx
where Zx = sum_y exp(sum_i lambda_i f_i(x,y))

P(O) = sum_x P(O|X)P(X)

P(X)=p(x_1)p(x_{2..n}|x_1)
=p(x_1)p(x_2|x_1)p(x_{3..n}|x_1,x_2)
……

P(X)=p(x_1)p(x_2|x_1)p(x_3|x_2)……

P(O|X)=p(o_1|x_{1..n})p(o_{2..n}|o_1x_{1..n})
=p(o_1|x_{1..n})p(o_2|o_1x_{1..n})p(o_{3..n}|o_{1,2},x_{1..n})
……

P(O|X)=p(o_1|x_1)p(o_2|x_2)……

P(O)=sum_x p(x_1)p(x_2|x_1)p(o_1|x_1)p(x_3|x_2)p(o_2|x_2)……

alpha_j(t)=sum_{i=1}^N alpha_ip(x_{t}=j|x_{t-1}=i)p(o_t=i|x_t=i)

beta_i(t)=sum_{j=1}^N p(x_{t}=j|x_{t+1}=i)p(o_{t}=i|x_{t}=i) beta_j(t+1)

P(O, X_t=i) = alpha_i(t)beta_i(t)

HMM的缺点是根据观测序列决定状态序列，是用联合模型解决条件问题；另外，几乎不可能枚举所有所有可能的观测序列。

P(S|O)=P(s_1|O)P(s_{2..n}|s_1,O)
=P(s_1|O)P(s_2|s_1,O)P(s_{3..n}|s_1,s_2,O)
……

P(S|O)=P(s_1|O)P(s_{2..n}|s_1,O)
=P(s_1|o_1)P(s_2|s_1,o_2)P(s_{3..n}|s_1,s_2,o_3)
……

a=<b,r>
b是指示函数用于指示当前观测
r是状态值
f_a(o_t, S_t) = 1 if b(o_t) is true and s_t = r

E_a = sum_{k=1}^m_{s'}sum_{s in S}P(s|s', o_k)f_a(o_k, s) / m_s' = sum_{k=1}^m_{s'} f_a(o_k, s_k) = F_a

P(s|s', o)=exp(sum_a lambda_a f_a(o, s)) / Z(o, s')

P(s|o) = P(s_0)P(s_1|s_0,o_0)P(s_2|s_1, o_1)……

MEMM其实是用局部信息去优化全局，会有label bias的问题。比如rib和rob，有如下的状态设计：
/r 1i - 2
0             b 3
r 4o - 5 /

p(y|x)propto exp(sum_ilumbda_k f_k(y_{i-1}, y_i, x)+sum_k lumbda_kg_k(x_k, x))

p_theta(y|x) = exp(sun_{ein E, k}lambda_k f_k(e,y|_e, x)+sum_{v in V,k}mu_k g_k(v, y|_v, x))
x是上下文，y是标注序列，y|_s是y中与子图S相连的部分

Y是类别个数
M_i(y', y|x) = exp(sum_j lambda_j f_j(y', y, x, i))

Zx = multi_{i=1}^{n+1}M_i(x)
Zx只是保证概率之和为1

John Lafferty, Andrew McCallum这两个人无比牛啊!! 几乎引领着CRF这一领域的发展：虽然ME不是1拉最先提出来的，但是1拉从96年就开始研究crf相关的东西，

https://blog.sciencenet.cn/blog-260809-573755.html

## 相关博文

GMT+8, 2022-8-20 07:55