QxRed

Max Margin Markov Networks for sequence labeling原理
参考文献
Max Margin Markov Networks

设训练集S有n个序列，S={(X1,Y1),...,(Xn,Yn)},长度分别为l1,...,ln。其中Xi=X_{i,1},...,X_{i,l_i},Yi=Y_{i,1},...,Y_{i,l_i}，类标记个数为k
对于某个序列(X,Y)来说，序列中的每个边(X,Y_{s-1},Y_s),都是一个r维的特征向量:
f_(X_s,Y_s)=[f_1(X,Y_{s-1},Y_s),...,f_r(X,Y_{s-1},Y_s)]'
记f(X,Y)=\sum_s f_(X,Y_{s-1},Y_s)，即所有节点特征向量之和。（这里和CRF完全相同,定义在节点上的特征也包含在了f中）
一个序列(X,Y)的经验错误为其所有节点经验错误之和：
ε(X,Y)=\sum_i (Y_i!=t(X_i))
t(X_i)为X_i的正确类别
根据多类SVM最小化样本经验错误的上界准则类似，M3N试图找到一个r维的投影方向，使得序列(X,Y)经验错误的上界为0：(见"多类SVM原理及求解")
\forall Y: w'Δf(X,Y)>=Δt(X,Y)
其中Δf(X,Y)=f(X,t(X))-f(X,Y), Δt(X,Y)=ε(X,Y)
同时M3N又试图最小化泛化错误，即最小化||w||_2，这样就形成了M3N的原问题：
min_w 1/2 ||w||_2^2
s.t. \forall Y: w'Δf(X,Y)>=Δt(X,Y)
当训练样本集合线性不可分时，上式无解。为此，引入松弛向量ξ_X>=0:

min_{w,ξ} 1/2 w'w + C \sum_X ξ_X
s.t.  w'Δf(X,Y)>=Δt(X,Y)-ξ_X, \forall X,Y         (1)

这就是M3N的原问题了。注意，当Y=t(X)时，(1)的约束就成为ξ_X>=0
(1)的对偶问题为：
max_a min_{w,ξ} L(w,ξ,a)=1/2 w'w + C \sum_X ξ_X + \sum_{X,Y} a_X(Y)[Δt(X,Y)-ξ_X-w'Δf(X,Y)]
s.t. a_X(Y)>=0

dL/dw=0 => w = \sum_{X,Y} a_X(Y)Δf(X,Y)
dL/ξ_X=0 => \sum_Y a_X(Y) = C

把上面两式代入(1)，得到的对偶问题为：
min_a 1/2 ||\sum_{X,Y} a_X(Y)Δf(X,Y)||_2^2 - \sum_{X,Y} a_X(Y) Δt(X,Y)
s.t. \sum_Y a_X(Y) = C
     a_X(Y)>=0,      \forall X,Y        (2)

 

由于|Y|是序列长度的指数大小：|Y|=k^l，所以(2)中的a_X(Y)>=0的约束有指数个。直接优化是不可能的。但事实上，(2)可以用多项式个约束表达
注意\sum_Y a_X(Y) = C,a_X(Y)>=0
所以a_X(Y)是一个分布。

\sum_{X,Y} a_X(Y)Δf(X,Y)
=\sum_X [\sum_Y a_X(Y)Δf(X,Y)]
=\sum_X [\sum_Y a_X(Y)\sum_{q \in X's edge set} Δf(q)δ(Y,q)]
=\sum_X [\sum_{q \in X's edge set}Δf(q) \sum_Y a_X(Y) δ(Y,q)]
=\sum_X [\sum_{q \in X's edge set}Δf(q) \sum_{Y~q} a_X(Y)]
=\sum_X \sum_{q \in X's edge set} μ_q Δf(q)
=\sum_X \sum_{i-1,i,Y_{i-1},Y_i} μ_{Y_{i-1},Y_i} Δf(X,Y_{i-1},Y_i)
δ(Y,q)=1 如果 Y 包含q这条边，否则=0
Y~q表示所有含有q的Y的集合
μ_q表示q这条边的边际概率
X's edge set：
设X含有l个节点，每个节点可能标记为y1..,yk中的一个，则下图k*l个点构成的网格中所有坐标为
(x_{i-1} y_j),(x_i y_m)连成的边的集合就是X's edge set
    X1    X2    X3    ..    Xl
y1
y2
..
yk

\sum_{X,Y} a_X(Y) Δt(X,Y)
=\sum_X [\sum_Y a_X(Y) Δt(X,Y)]
=\sum_X [\sum_Y a_X(Y) \sum_{p \in X's node set} Δt(p)δ(Y,p)]
=\sum_X [\sum_{p \in X's node set} Δt(p)\sum_Y a_X(Y) δ(Y,p)]
=\sum_X [\sum_{p \in X's node set} Δt(p)\sum_{Y~p} a_X(Y)]
=\sum_X [\sum_{p \in X's node set} μ_p Δt(p)]
=\sum_X \sum_{i,Y_i} μ_{Y_i} Δt(X,Y_i)]
δ(Y,p)=1 如果 Y 包含p这个点，否则=0
Y~p表示所有含有p的Y的集合
μ_p表示p这个点的边际概率
X's node set：即上图中所有的k*l个点

同一个点出发的所有边的边际概率之和应该等于该点的边际概率：
\sum_Y μ_{Y_{i-1},Y_i}=μ_{Y_i}

这样(2)就化为:

min_μ 1/2 ||\sum_X \sum_{i-1,i,Y_{i-1},Y_i} μ_{Y_{i-1},Y_i} Δf(X,Y_{i-1},Y_i)||_2^2 - \sum_X \sum_{i,Y_i} μ_{Y_i} Δt(X,Y_i)]
s.t. \sum_Y μ_{Y_{i-1},Y_i}=μ_{Y_i}
     \sum_{Y_i}μ_{Y_i}=C
     \sum_Y μ_{Y_{i-1},Y_i}>=0

即：

min_μ 1/2 \sum_{X,X`}\sum_{i,j,Y_{i-1},Y_i,Y`_{j-1},Y`_j} K(X,X`Y_{i-1},Y_i,Y`_{j-1},Y`_j)μ_{Y_{i-1},Y_i} μ_{Y`_{j-1},Y`_j} - \sum_X \sum_{i,Y_i} μ_{Y_i} Δt(X,Y_i)]
s.t. \sum_Y μ_{Y_{i-1},Y_i}=μ_{Y_i}
     \sum_{Y_i}μ_{Y_i}=C
     \sum_Y μ_{Y_{i-1},Y_i}>=0            (3)

其中K(X,X`Y_{i-1},Y_i,Y`_{j-1},Y`_j)=Δf'(X,Y_{i-1},Y_i)Δf(X,Y_{j-1},Y_j)
k*k*(l1+...ln)的kernel matrix

SVM的对偶问题为
min 1/2 a'Qa - a'e
s.t. 0<= a <= C e
     a' y = 0
其中a=[a1,...,an]', Q_{ij}=Kijyiyj, e=[1,...,1]', y=[y1,...,yn]'

记P=[x1y1,...,xnyn] (一个m*n的矩阵)
则上式可以化为标准形式：
min 1/2 a'P'Pa - a'e
s.t. -a<=0
     a-C e<=0
     a'y=0

对3个约束分别引入拉格朗日乘子μ,λ,b，则其对偶问题为
max_{μ,λ,b} min_a L(μ,λ,b,a) = 1/2 a'P'Pa - a'e - μ'a + λ'(a-C e) + b a'y
s.t. μ>=0 λ>=0

dL/da=0
=>
P'Pa-e-μ+λ+by=0
=>(-e-μ+λ+by)'a=-a'P'Pa
代入原目标函数，得
max_{μ,λ,b} -1/2 aP'Pa -  C λ'e
s.t. μ>=0 λ>=0
     P'Pa-e-μ+λ+by=0

记w=Pa则上式化为
min_{w,b,μ,λ} 1/2 w'w + C λ'e
s.t. P'w=e+μ-λ-by
     μ>=0 λ>=0           (1)

由P'w=e+μ-λ-by得
P'w+by-e+λ=μ>=0
=>
P'w+by>=e-λ
=>
(P'w)_i+(by)_i>=(e-λ)_i
=>
(xiyi)'w + b yi >= 1-λi
=>
yi(w'xi + b) >= 1-λi

因此(1)化为
min_{w,b} 1/2 w'w + C λ'e
s.t. yi(w'xi + b)>=1-λi    \forall i
     λ>=0
这就是SVM的原问题

参考文献：
On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines

设训练集合S={(x1,y1),(x2,y2),...,(xm,ym)}. xi为观察值，yi为对应的类别标记。类个数为k。
支持向量机(SVM)分类器H_M是一个关于观察值的函数：
H_M(xi)=argmax_i M xi             (1)
M为该分类器的参数
对于某个观察值x(类标记y)来说，分类器的经验错误为
e(S,M,x)= H_M(x)!=y
分类器的经验错误为
e(S,M)=1/m \sum_x e(S,M,x)
由于计算量太大，直接求一个最小化经验错误e(S,M)的M是不可行的。为此，SVM所求的M是最小化经验错误的上界函数。对于(x,y)来说，经验错误的上界为：
e'(S,M,x)=max_r{Mr x+1-d(y,r)}-My x          (2)
其中 d(a,b)=1 if a=b, else =0
简单分析一下，
a)当\forall r!=y, My x>=Mr x+1时，由(1)，分类正确，e(S,M,x)=0;由(2)y=max_r{Mr x+1-d(y,r)} => e'(S,M,x)=0。 所以在这种情况下e'=e
b)当\forall r!=y, My x>=Mr x，且max_r{Mr x}+1>My x 时，由(1)，分类正确，e(S,M,x)=0;由(2)e(S,M,x)=Mr x+1-My x => 0<e'(S,M,x)=0<=1，所以此时e'(S,M,x)>=e(S,M,x)
c)当max_r{Mr x}>My x时，由(1)知，分类错误,e(S,M,x)=1，由(2)知，e'(S,M,x)=max_r{Mr x}+1-My x>1 => e'(S,M,x)>e(S,M,x)

所以\forall (x,y)  e'(S,M,x)>=e(S,M,x)
记e'(S,M)=1/m \sum_x e'(S,M,x)
可知，e'(S,M)>=e(S,M)，e'(S,M)为SVM所要最小化的上界函数：
M*=argmin_M e'(S,M)
SVM试图求一个M使得e'(S,M)=0
即：\forall i
max_r{Mr xi+1-d(yi,r)}-Myi xi = 0
即：\forall i,r
Myi xi+d(yi,r)-Mr xi >=1

同时，SVM要最小化泛化错误，因为泛化错误与||M||_2有关，所以SVM需要最小化||M||_2，这样就形成了SVM的目标函数：
min 1/2||M||_2^2
s.t. \forall i,r     Myi xi+d(yi,r)-Mr xi >=1
当S不是线性可分的时候，不存在M满足上面的不等式约束，为此引入松弛向量z>=0使得
Myi xi+d(yi,r)-Mr xi >=1-zi
这样就得到了新的SVM目标函数：
min 1/2 b||M||_2^2+\sum_i zi
s.t. \forall i,r     Myi xi+d(yi,r)-Mr xi >=1-zi       (3)
其中b>0是一个常数,\forall i, zi>=0这个约束隐含在上面的约束中：令r=yi就可以得到z>=0
(3)的对偶问题为：
max_h min_{M,z} L(M,z,h)=1/2 b||M||_2^2+\sum_i zi + \sum_{i,r}h_{i,r}[Mr xi+1-zi-Myi xi-d(yi,r)]
s.t. \forall i,r h_{i,r}>=0                            (4)
(3)是一个凸函数，因为目标函数为二次函数，而约束是线性不等式约束，且存在一个内点z->+\inf使得不等式严格成立，所以强对偶成立，(4)和(3)有相同的最优点
dL/dz=0 => \forall i, 1-\sum_{i,r}h_{i,r}=0 => \sum_r h_{i,r}=1            (5)
dL/dMr=0 =>
b Mr + \sum_i h_{i,r} xi - d[\sum_i Myi xi \sum_s h_{i,s}]/dMr = 0
=>b Mr + \sum_i h_{i,r} xi - \sum_{i,yi=r} xi = 0
=>b Mr + \sum_i h_{i,r} xi - \sum_i d(yi,r) xi =0
Mr=1/b [\sum_i( d(yi,r)-h_{i,r} )xi]                   (6)
将(6)(5)代入(4)，化简得到：
max_h Q(h)=-1/(2b)  \sum_{i,j} xi xj [\sum_r(d(yi,r)-h_{i,r})(d(yi,r)-h_{i,r})] - \sum_{i,r} h_{i,r}d(yi,r)         (7)

具体步骤：
由(4),
1/2 b||M||_2^2+\sum_i zi + \sum_{i,r}h_{i,r}[Mr xi+1-zi-Myi xi-d(yi,r)]
=1/2 b||M||_2^2 + \sum_i zi + \sum_{i,r}h_{i,r} Mr xi + \sum_{i,r}h_{i,r} - \sum_{i,r}h_{i,r}zi - \sum_{i,r}h_{i,r}Myi xi - \sum_{i,r}h_{i,r}d(yi,r)
=\sum_{i,r}h_{i,r} Mr xi - \sum_{i,r}h_{i,r}Myi xi + 1/2 b||M||_2^2 + (\sum_i zi - \sum_i zi \sum_r h_{i,r}) + (\sum_{i,r}h_{i,r} -  \sum_{i,r}h_{i,r}d(yi,r) )
=S1-S2+S3 + 0 + [m- \sum_{i,r}h_{i,r}d(yi,r)]
把(6)代入S1:
S1=\sum_{i,r}h_{i,r} Mr xi
  =\sum_{i,r}h_{i,r} xi 1/b [\sum_j( d(yj,r)-h_{j,r} )xj]
  =1/b \sum_{i,j} xi xj \sum_r h{i,r}(d(yj,r)-h_{j,r})
S2=\sum_{i,r}h_{i,r}Myi xi
  =\sum_{i,r}h_{i,r}xi 1/b \sum_j xj(d(yj,yi)-h_{j,yi})
  =1/b \sum_{i,j}xi xj \sum_r h_{i,r}(d(yj,yi)-h_{j,yi})
  =1/b \sum_{i,j}xi xj (d(yj,yi)-h_{j,yi})\sum_r h_{i,r}
  =1/b \sum_{i,j}xi xj (d(yj,yi)-h_{j,yi})
  =1/b \sum_{i,j}xi xj \sum_r d(yi,r)(d(yj,r)-h_{j,r})
S3= 1/2 b||M||_2^2
  = 1/2 b \sum_r Mr' Mr
  = 1/2 b \sum_r ( 1/b [\sum_i( d(yi,r)-h_{i,r} )xi] )(1/b [\sum_j( d(yj,r)-h_{j,r} )xj] )
  = 1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} )
所以
S1-S2=-1/b \sum_{i,j}xi xj \sum_r[(d(yi,r)-h_{i,r})d(yj,r)-h_{j,r})]
S1-S2+S3=-1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} )
Q(h)=-1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} ) + [m- \sum_{i,r}h_{i,r}d(yi,r)]
由于求的是使得Q(h)最优的h*，所以加或者乘常数项不影响h*
所以h*=argmax_h Q'(h)=-1/(2b) \sum_{i,j} xi xj \sum_r ( d(yi,r)-h_{i,r} )( d(yi,r)-h_{i,r} )-\sum_{i,r}h_{i,r}d(yi,r)
即(7)式

记１i=第i行为1其他行为0的列向量。１为所有元素为1的列向量。ti=１yi-h_i则，
Mr=1/b \sum_i t_{i,r} xi         (8)
(7)式变为
max_t -1/2 \sum_{i,j} Kij(ti tj) + b\sum_i ti １yi
s.t.  \forall i ti<=１yi, ti１=0             (9)
其中，(7)乘了b，但这不影响t*, Kij=xi xj

SMO算法
通过数值方法，解出(9)。每次选取一个观察值xp进行优化
把(9)的目标函数表达成xp的多项式：
Q(tp)=-1/2 Kpp(tp tp)-1/2\sum_{i!=p,p}Kip(ti tp)-1/2\sum_{p,j!=p}Kpj(tp tj)-1/2\sum_{i!=p,j!=p)Kij(ti tj)+b tp １yp + \sum_{i!=p} ti １yi
=-1/2Kpp tp^2 -\sum_{i!=p,p}Kip(ti,tp)+b tp １yp + Cp
=-1/2Kpp tp^2 -[\sum_{i!=p}Kip ti-b１yp]tp + Cp
=-1/2Ap tp^2 - Bp tp + Cp
其中Ap,Bp,Cp都是与tp无关的常数
Bp=\sum_{i!=p}Kip ti-b１yp              (10)
这样，目标函数就变为：
tp*=min_tp 1/2 Ap tp^2 + Bp tp
s.t. tp<=１yp, tp１=0                    (11)
接着看看如何选这个xp，与两类SVM的SMO算法类似，选取最不符合KKT条件的那个。
(9)的对偶问题为
L(u,v,t) = min_{u,v} max_t -1/2 \sum_{i,j} Kij(ti tj) + b\sum_i ti １yi + \sum_{i,r}u_{i,r}(t_{i,r}-d(yi,r)) - v \sum_r t_{i,r}
s.t. u>=0
则第一个KKT条件为
dL/dt=0 =>
\sum_j Kij t_{j,r}-b d(yi,r)+u_{i,r}-vi=0
记F_{i,r}=\sum_j Kij t_{j,r}-b d(yi,r)  (*****)
=>F_i=\sum_j Kij tj - b１yi
=>F_i=\sum_{j!=i} Kji tj - b１yi + Kii ti
=>F_i=Bi+Kiiti                (参见(10))
=>F_{i,r}=B_{i,r}+Kii t_{i,r}          (12)
于是dL/dt=0 =>
F_{i,r} + u_{i,r}-vi=0  ,剩下的KKT条件为 (13)
u_{i,r}(t_{i,r}-d(yi,r))=0               (14)
u_{i,r}>=0                               (15)
t_{i,r}-d(yi,r)<=0                       (16)
\sum_r t_{i,r}=0                         (17)
对于(17)，类似于两类SMO，参数将在直线\sum_r t_{i,r}=0上优化，因此该条件在优化时用掉
下面将用(13)~(16)的充要条件来找出xp
由(15)(13)得：
F_{i,r}<=vi
a)t_{i,r}=d(yi,r),此时
F_{i,r}<=vi                              (18)
b)t_{i,r}<d(yi,r),此时
u_{i,r}=0=>F_{i,r}=vi => F_{i,r}<=vi, F_{i,r}>=vi   (19)
由(18)(19)得
max_r F_{i,r} <= vi <= min_{t_{i,r}<d(yi,r)} F_{i,r} (20)
显然max_r F_{i,r} >= max_{t_{i,r}<d(yi,r)} F_{i,r} >= min_{t_{i,r}<d(yi,r)} F_{i,r}
因此，phi_i=max_r F_{i,r}-min_{t_{i,r}<d(yi,r)} F_{i,r}>=0  (*)
所以p=argmin_i phi_i

找到需要优化的xp后，看看如何优化，这里去掉下标p
由(11)得到
t*=min_t 1/2 A t^2 + B t
=min_tp 1/2 A[t+B/A]'[t+B/A] + B'B/(2A)
=min_tp 1/2 A[t+B/A]'[t+B/A]
记w=t+B/A, D=B/A+１y                (**)
这样(11)就变为
min_w Q(w)=1/2 ||w||_2^2
s.t. w<=D, w'１=D'１-1              (21)
其对偶问题为
max_{a,θ} min 1/2 ||w||_2^2 + a'(w-D)-θ(w'１-D'１+1)
s.t. a>=0
其KKT条件为
dQ/dw=0 => w + a - θ=0 <=> w_r+a_r-θ=0  (22)
a>=0 <=> a_r>=0           (23)
w<=D <=>w_r <= D_r         (24)
a_r(w_r-D_r)=0              (25)
w'１=D'１-1                 (26)
由(23)(22),
w_r<=θ
由(24),
w_r<=min{θ,D_r}
由(23),当a_r=0时w_r=θ,
由(25),当a_r>0时w_r=D_r
所以
w_r=min{θ,D_r}               (***)
由(26)
\sum_r min{θ,D_r}=\sum_r D_r - 1
此时必定存在一个θ使得上式成立。因为左边是关于θ的单调连续增函数，当θ->-\inf时左边=-\inf,当θ->\inf时，左边=sum_r D_r>右边
利用θ+D_r=max{θ,D_r}+min{θ,D_r}，得到
\sum_r [θ+D_r - max{θ,D_r}] = \sum_r D_r -1
=> k θ = \sum_r max{θ,D_r} - 1
=> θ=1/k \sum_r max{θ,D_r} - 1/k   (****)
因此可以通过叠代的方法求出θ，论文中证明了，只要初始θ足够小，θ就可以通过
θ(l+1)=1/k \sum_r max{θ(l),D_r} - 1/k
叠代求得。因此选择θ(1)=min{D_r}得到
θ(2)=1/k \sum_r D_r - 1/k         (27)
这个初始值
补充一下：
这里的(26)相当于(17)，因此算法保证了整个优化过程在直线上进行

整个算法框架如下：
输入{(x1,y1)...(xm,ym)},k个类别
初始化
for i=1 to m
ti=0        (满足(17))
F_{i,r}=-b d(r,yi)   (r=1,..,k, 见(12)(10))
Ai=Kii

重复
a) 寻找需要优化的点：p=argmax_i phi_i
phi_i=max_r F_{i,r}-min_{t_{i,r}<d(yi,r)} F_{i,r}
  见(*)
b) 优化xp:
  初始化D_r=B_{p,r}/Ap+d(r,yp)=F_{p,r}/Ap-t_{p,r}+d(r,yp)
    见(10)(12)(**)
  θ(0)=1/k \sum_r D_r - 1/k
    见(27)
  由(****)叠代求解θ
  由(***)求出w,再由(**)求出t*
c) 更新F,t:
  Δt=t*-t
  for i=1 to m , r=1 to k
    F_{i,r}=F_{i,r}+Δt_{p,r} Kpi
     见(*****)
  t=t*
直到phi_i=0

输出
H(x)=argmax_r{Mr x}
    =argmax_r{\sum_i t_{i,r}(xi,x) }  (见(8))

 

房东家的圣诞树

在洛杉矶的星光大道上找到了成龙的星星

洛杉矶市中心


洛杉矶universal studio里的可爱服饰

universal studio的圣诞树


洛杉矶海边

好莱坞

好莱坞


death valley中的绿洲

death valley中的盐湖


拉斯维加斯


大峡谷


Hoover Dam

今天用CRF++ 0.49做了sighan bake off 4的部分实验（待补充），实验结果如下
template:

U00:%x[-1,0]
U01:%x[0,0]
U02:%x[1,0]
U03:%x[-1,0]/%x[0,0]
U04:%x[0,0]/%x[1,0]
U05:%x[-1,0]/%x[1,0]
B

用B B2 B3 M E S 6 tagging 方法，命令行
crf_learn -c 100 template train model
测试工具用sighan bakeoff 2的工具
测试结果
ctb: F-value  0.95
ncc: F-value 0.9329

感觉自己的功底太弱了。convex才看了第2章。而且真正掌握的机器学习方法没有几个。
连最经典的分类器svm都没有好好学习过。要好好向taku学习，认真读TinySVM。恩！
还有boosting...学不完的东西啊.

Taku kudo的好东西还真不少，嘿嘿！
http://chasen.org/~taku/software/TinySVM/
要是有大猪头指导就好了

目前crf在machine learning中仍旧活跃。对于crf的研究可以分为以下几个方面：(欢迎大家补充 ^^)

1) 改变结构,使得crf可以适应更复杂的任务
比如：Dynamic crf
http://www.cs.umass.edu/~mccallum/papers/dcrf-nips03.pdf
skip chain crf
http://www.cs.umass.edu/~mccallum/papers/tr-04-49.pdf

2) 加快crf训练速度
piecewise linear crf
http://www.machinelearning.org/proceedings/icml2007/papers/549.pdf
EG algorithm for crf training
http://people.csail.mit.edu/gamir/pubs/olcrf.pdf

3) feature selection
http://www.cs.umass.edu/~mccallum/papers/ifcrf-uai2003.pdf

4) semi supervised crf
http://www.metabolomics.ca/News/publications/Jiao_et_al.pdf
http://pages.cs.wisc.edu/~jerryzhu/pub/kcrf-revised.pdf

5) other:
semi crf
http://www.cs.cmu.edu/~wcohen/postscript/semiCRF.pdf
sparse crf
http://www.cs.umass.edu/~mccallum/papers/sparse-fb.pdf

基督徒都相信这个世界上真的有一个万能的神。他安排了我们每个人的一生，我们所需要做的事。这听起来很悬。
我并太赞同这个观点。然而，我并不否认它。自从考研的那一天起，我就不再相信人的主观能动性的作用了。明明决定找工作的我，最后还是难以抵挡考研。自己似乎可以选择工作，但事实上却没有选择。
我觉得一个人有自己的轨道。我们以为自己可以左右自己的人生，但事实上是无济于事的。
这个现象，也许可以用神去解释吧，但不管怎么样，这只是一个解释。所以，也许这是真的，但有可能另有他因。
无论事实怎样，这都与我们的决定无关，因为我们是没有选择的。该出国的不会留在国内，不该出国的，出去了也会回来。该做research的，他就注定不会成为一个工程师。所以，好好做自己的事吧。

http://www.cdw.com/shop/products/specs.aspx?EDC=1297853&cm_sp=Product-_-Specs-_-Main+Tab

HP ProLiant DL580 G5 High Performance - Quad-Core Xeon X7350 2.93 GHz

4个4核的 2.93G cpu:

Processor

64-bit Computing	Yes
Clock Speed	2.93 GHz
Installed Qty	4
Manufacturer	Intel
Max Supported Qty	4
Multi-Core Technology	Quad-Core
Processor Number	X7350
Server Scalability	4-way
Type	Quad-Core Xeon

RAM

Configuration Features	4 x 2 GB
Data Integrity Check	Advanced ECC
Features	Memory Mirroring, Online Spare Memory
Form Factor	FB-DIMM
Installed Size	8 GB
Max Supported Size	128 GB
Memory Specification Compliance	PC2-5300
Memory Speed	667 MHz
Technology	DDR II SDRAM

Cache Memory

Installed Size	32 MB
Multi-Core Cache Configuration	2 x 4MB (4MB per core pair)
Per Processor Size	8 MB
Type	L2 cache

如果用这样的机器跑CRF...