QxRed » 2008年 » 2月
随想
风暴红QxRed 发表于 2008-02-24 16:33:56
今天wc时产生了一个想法。对n元凸函数f(x)来说，假设其最优点为x*，假若记z为x的前k个分量构成的向量，y为x的后t个分量构成的向量，且k+t<n
固定z，只对剩下的变量优化，得到一个最优解f(x1)，以及固定y只对剩下的分量进行优化，得到一个最优解f(x2)，那么该命题是否成立：x在由x1,x2构成的矩形中？
如果不是，加上什么额外条件就可以使得该命题成立呢？
固定z，只对剩下的变量优化，得到一个最优解f(x1)，以及固定y只对剩下的分量进行优化，得到一个最优解f(x2)，那么该命题是否成立：x在由x1,x2构成的矩形中？
如果不是，加上什么额外条件就可以使得该命题成立呢？
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
LR(1)分析器
风暴红QxRed 发表于 2008-02-20 08:34:13
Build FIRST:
for each X \in N, FIRST(X)=NULL;
for each x \in T, FIRST(x)={x};
do
OLD_FIRST=FIRST;
for each generation X-> alpha_1 alpha_2 ... alpha_k
if alpha_1 alpha_2 ... alpha_k == e
FIRST(X)+={e};
else
add_e=true;
for i=1 to k and add_e
FIRST(X) += FIRST(alpha_i)-{e};
if e \not\in FIRST(alpha_i)
add_e=false;
if add_e
FIRST(X) += {e};
while OLD_FIRST!=FIRST;
output FIRST;
Build FOLLOW:
for start state S, FOLLOW(S) = #;
for each X \in N, FOLLOW(X)=NULL;
for each x \in T, FOLLOW(x)=NULL;
do
OLD_FOLLOW=FOLLOW;
for each generation X-> alpha_1 alpha_2 ... alpha_k
FOLLOW(alpha_k)+=FOLLOW(X);
FOLLOW_X=FOLLOW(X);
for i=k to 2
if e \not\in FIRST(alpha_i)
FOLLOW_X=NULL;
FOLLOW(alpha_{i-1})+=FIRST(alpha_i)-{e} + FOLLOW_X;
while OLD_FIRST!=FIRST;
output FIRST;
build CLOSURE:
for each iterm set I
CLOSURE(I)=I;
OLD_CLOSURE(I)=CLOSURE(I);
do
for each [X->alpha_1 . Y alpha_2 ,a] in I,
for each b \in FIRST(alpha_2 a), each generator Y->.gama
CLOSURE(I)+={[Y->.gama, b]}
while OLD_CLOSURE(I)!=CLOSURE(I);
build GO:
for iterm set I,
GO(I,zeta)=CLOSURE({ [X->alpha zeta . beta, a]|[X->alpha . zeta beta, a] \in I})
build GO_SET C:
build FIRST;
build FOLLOW;
I_1=CLOSURE({S'->[.S,#]})
C={I_1}
s=1;
do
OLD_C=C;
for each item [X->alpha .zeta beta, a] in I_i
I=GO(I_i,zeta);
j=index of I \in C;
if I \not\in C
C+=I;
j=|C|;
I_j=I;
I_j=GO(I_i,a);
while OLD_C!=C;
build ACTION, GOTO table:
build GO_SET C;
for i=1 to n
for each item [X-> ... , b] in I_i
if item has form [X-> alpha . a beta, b]
I_j=GO(I_i,a);
ACTION(i,a)=sj;
else if item has form [X-> alpha a. , b]
j=index of generator X-> alpha a;
ACTION(i,b)=rj;
else if iterm is [S'->S. , #]
ACTION(i,#)=acc;
for each X
GOTO(i,X)=GO(i,X);
recognition:
state_stack={1};
symbol_stack=NULL;
add "#" to the end of input_string queue s=a_1 a_2 ... a_n
while true
action=ACTION(state_stack.top(),s.head())
if action==sj
state_stack.push(j);
symbol_stack.push(s.head())
s.pop();
else if action==rj
get j th generator X-> alpha_1,...,alpha_k
state_stack.pop(k);
symbol_stack.pop(k);
symbol_stack.push(X);
state_stack.push(GOTO(state_stack.top(),X))
else if action==acc
return success;
else
return error;
example:
S->BB
B->aB
B->b
reform the grammar:
1) S'->S
2) S->BB
3) B->aB
4) B->b
build FIRST_SET and FOLLOW_SET:
|
|
FIRST
|
FOLLOW
|
|
S'
|
a,b
|
#
|
|
S
|
a,b
|
#
|
|
B
|
a,b
|
a,b,#
|
|
a
|
a
|
a,b
|
|
b
|
b
|
b
|
build GO_SET:
(here the index start with 0)
start with [S'->.S,#]
I_0=CLOSURE({[S'->.S,#]})
=
[S'->.S,#]
[S->.BB,#]
[B->.aB,a/b]
[B->.b,a/b]
Here a/b comes from FIRST(B #)={a,b}
Build other SETS in the same way
Build ACTION and GOTO table:
Recognition example:
abab#
|
state_stack
|
symbol_stack
|
string_queue
|
action
|
|
0
|
|
abab#
|
s3
|
|
03
|
a
|
bab#
|
s4
|
|
034
|
ab
|
ab#
|
r3
|
|
038
|
aB
|
ab#
|
r2
|
|
02
|
B
|
ab#
|
s6
|
|
026
|
Ba
|
b#
|
s7
|
|
0267
|
Bab
|
#
|
r3
|
|
0269
|
BaB
|
#
|
r2
|
|
025
|
BB
|
#
|
r1
|
|
01
|
S
|
#
|
acc
|
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
移进规约冲突的消除
风暴红QxRed 发表于 2008-02-19 15:39:30
对于项目集I：
A->B.
A->C.a b
A1-> ...
其中A,B,C为非终结符，a 为终结符或非终结符，b为终结符或非终结符组成的字符串
此时会产生移进规约冲突，补救方法：
记S=所有右边首个符号集合，如果S 交 FOLLOW(B)= NULL，则可以通过向前看一个输入字符（终结符）判断
为何不是 FIRST(S) 交FOLLOW(B)?
因为如果a\in S为终结符，则a==FIRST(a)
如果a为非终结符，则存在
a->.c
c为终结符或非终结符组成的字符串，且该项也在项目集I中
如果c为终结符，则c=FIRST(c) \in S，因此FIRST(a) 交 FOLLOW(B)=NULL
如果c为非终结符，则存在
c->.d
...
所以S 交 FOLLOW(B)=NULL 等价于 FIRST(S) 交FOLLOW(B)=NULL
A->B.
A->C.a b
A1-> ...
其中A,B,C为非终结符，a 为终结符或非终结符，b为终结符或非终结符组成的字符串
此时会产生移进规约冲突，补救方法：
记S=所有右边首个符号集合，如果S 交 FOLLOW(B)= NULL，则可以通过向前看一个输入字符（终结符）判断
为何不是 FIRST(S) 交FOLLOW(B)?
因为如果a\in S为终结符，则a==FIRST(a)
如果a为非终结符，则存在
a->.c
c为终结符或非终结符组成的字符串，且该项也在项目集I中
如果c为终结符，则c=FIRST(c) \in S，因此FIRST(a) 交 FOLLOW(B)=NULL
如果c为非终结符，则存在
c->.d
...
所以S 交 FOLLOW(B)=NULL 等价于 FIRST(S) 交FOLLOW(B)=NULL
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
最近好烦
风暴红QxRed 发表于 2008-02-19 07:06:58
看编译原理看得累死了，进入左递归了！不知道怎么搞的，计划里没有这一项的。本来下半年继续看Convex的，现在还没动。烦死了，真想放弃编译原理。
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
如果这样的教材多一些就好了
风暴红QxRed 发表于 2008-02-12 14:45:23
http://www.ebookdown.net/down.asp?id=2036&downid=0
编译原理基础，刘坚，西安电子科技大学出版社
别的不多说了，请看29页，例2.12，原来NFA->DFA竟然可以如此形象，如此简单
对于该书作者，只有admire！谢谢你！
编译原理基础，刘坚，西安电子科技大学出版社
别的不多说了，请看29页，例2.12，原来NFA->DFA竟然可以如此形象，如此简单
对于该书作者，只有admire！谢谢你！
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
SVM-hmm测试结果
风暴红QxRed 发表于 2008-02-09 16:23:49
SVM-hmm是SVM struct在序列标注方面的应用，其优化目标和M3N一样，只不过采用cutting plane SMO加快优化速度
http://www.cs.cornell.edu/People/tj/svm_light/svm_hmm.html
在CRF++ base NP语料上的测试结果
其优化速度非常快，linear kernel 只用了0.52s，而且效果比Pocket M3N好，(pocket M3N C=1时 F=86.87, C=5时 F=86.97)
但是在quadratic kernel上，SVM-hmm训练时有warning
在中文分词上的测试结果
不知道为什么，结果如此之差。训练时间只要3分钟
http://www.cs.cornell.edu/People/tj/svm_light/svm_hmm.html
在CRF++ base NP语料上的测试结果
|
kernel
|
parameter
|
F-value
|
|
<a,b>
|
e=0.5, C=1
|
86.95
|
|
<a,b>
|
e=0.5, C=5
|
87.35
|
|
(<a,b>+1)2
|
e=0.5, C=5
|
74.73
|
|
<a,b>2
|
e=0.5, C=5
|
58.33
|
但是在quadratic kernel上，SVM-hmm训练时有warning
在中文分词上的测试结果
|
SVMhmm (C=1, e=0.5, linear kernel)
|
3 minutes
|
62.79
|
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
