木オートマトン トランスデューサによる 自然言語処理 林 克彦 NTTコミュニケーション科学基礎研究所 hayashi.katsuhiko@lab.ntt.co.jp
n
I T 1 T 2 I T 1 Pro j(i T 1 T 2 )
(Σ,rk) Σ rk : Σ N {0} nσ (n) rk(σ) = n σ Σ n Σ (n) Σ (n)(σ,rk)σ
Σ T Σ (A) A A (0) σ A Σ (0) σ T Σ (A) σ Σ (k) σ(t 1,...,t k ) T Σ (A) t 1,...,t k T Σ (A) Σ = {σ (0),λ (0),γ (0),ξ (0),δ (0),α (1),θ (1),σ (5) } A = {β} σ (0) α (1) σ (5) γ (0) γ (0) β (0) α (1) θ (1) δ (0) ξ (0) β (0)
ε 1 2 3 1.1 3.1 3.2 3.3 3.1.1 3.3.1 pos(t) = {ε} {i.v 1 i k,v pos(t i )}
ε 1 2 3 1.1 3.1 3.2 3.3 3.1.1 3.3.1 pos(t) = {ε} {i.v 1 i k,v pos(t i )} v pos(t) t(v) t(ε) = t(3.3) =
ε 1 2 3 1.1 3.1 3.2 3.3 3.1.1 3.3.1 pos(t) = {ε} {i.v 1 i k,v pos(t i )} v pos(t) t(v) t(ε) = t(3.3) = t v t 3.3 =
ε 1 2 3 1.1 3.1 3.2 3.3 3.1.1 3.3.1 pos(t) = {ε} {i.v 1 i k,v pos(t i )} v pos(t) t(v) t(ε) = t(3.3) = t v t 3.3 = s t[s] v t[ ] 3.3 =
pos(t) = {ε} {i.v 1 i k,v pos(t i )} v pos(t) t(v) t(ε) = t(3.3) = t v t 3.3 = s t[s] v t[ ] 3.3 =
X = {x 1,x 2,...} X k = {x 1,...,x k } φ : X T Σ (X) (φ) = {x X φ(x) x} (φ) = {x 1,...,x k }φ(x i ) = t i φ{x 1 t 1,...,x k t k } φ : T Σ (X) T Σ (X) φ(σ(s 1,...,s k )) = σ( φ(s 1 ),..., φ(s k )) φ = {x 1 a,x 2 b,x 3 c} α α φ ( β x 2 ) γ = β b γ x 1 x 3 a c
G = (N,Σ,P,I) N I N Σ P n u P n N u T Σ (N)
G = (N,Σ,P,I) N I N Σ P n u P n N u T Σ (N) s p G t s,t T Σ(N) p = n u P pn u n N u T Σ (N) v pos(s) s(v) = n s[u] v = t p = p
G = (N,Σ,P,I) N = { } Σ = { } I = {} P
G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 1
G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 2 p 1 p 2
p 1 G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 2 p 3 p 2 p 3
p 1 G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 2 p 3 L(G) = {t T Σ G t, I} p 2 p 3
{, }
{,,,, } {b 2n n 0}
{,,,, } {b 2n n 0} 0 b 0 1 ( 0 ) 1 (x) a x x
A = (Q,Σ,F,E) Q F Q Σ k {}}{ E Q Q Σ (k) Q σ(q 1,...,q k ) q E q,q 1,...,q k Qσ Σ (k) σ (k) Σq 1,...,q k ρ pos(t) Q t(v) = σ (k) v pos(t) σ(ρ(v.1),...,ρ(v.k)) ρ(v) E
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1.1)= ρ(2)= ρ(3.1.1)= ρ(3.2)= ρ(3.3.1)=
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1.1)= ρ(3.2)= ρ(3.3.1)=
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1)= ρ(3.1.1)= ρ(3.2)= ρ(3.3.1)=
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1)= ρ(3.1.1)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=
A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= L(A) = {t T Σ ρ(ε) Fρ} ρ(ε)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(ε)= ρ(1)= ρ(2)= ρ(3)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(ε)= ρ(2)= ρ(3)= ρ(1.1)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(ε)= ρ(2)= ρ(3)= ρ(1.1)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(ε)= ρ(2)= ρ(3)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3)= ρ(3.2)= ρ(3.3)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.1.1)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.1.1)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=
A = (Q,Σ,I,E) I Q k {}}{ E Q Σ (k) Q Q σ(q) (q 1,...,q k ) E q,q 1,...,q k Qσ Σ (k) I = {} E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=
= F I σ(q 1,...,q k ) q σ(q) (q 1,...,q k ) {, } = =
q t t Σ (0) t N t = σ (k) (q 1,...,q k ) σ Σ q 1,...,q k N σ (0) q ε(q 1 ) q σ (k) (q 1,...,q k ) q
L(A) = {t t L(A)} = L(A) L(A 1 ) L(A 2 ) = L(A 1 A 2 ) L(A 1 ) L(A 2 ) = L(A 1 A 2 )
1 1 1 0 2 3 4 2 3 4 2 g n n n A = {Q,Σ,F,E,π} r = σ(q 1,...,q k ) w q E π(r) = w
k k
A 1 = {Q 1,Σ,F 1,E 1,π 1 } A 2 = {Q 2,Σ,F 2,E 2,π 2 } E = /0 (q,q ) Q 1 Q 2 σ (k) Σ σ (k) (q 1,...,q k ) w 1 q E 1 σ (k) (q 1,...,q k ) w 2 q E 2 r σ (k) ((q 1,q 1 ),...,(q k,q k )) w 1+w 2 (q,q ) E E {r} π(r) w 1 + w 2 A = {Q 1 Q 2,Σ,F 1 F 2,E,π} O( E 1 E 2 ) A 2
k 1 k???? 1? k
k 0 3 3 3 + 3 3 = 18 2 1 2 0.5 0 0.6 0.4 0.3 0.9 1 0.5 0.3 4 3 4 0.3 0 0.8 0.2 0.1 0.8 3 0.4 0.2 3
k 0 3 3 3 + 3 3 = 18 2 1 2 0.5 0 0.6 0.4 0.3 0.9 0.27 1 0.5 0.3 4 3 4 0.3 0 0.8 0.2 0.1 0.8 0.192 3 0.4 0.2 0.27 0.192 3
k 0 3 3 3 + 3 3 = 18 2 1 2 0.5 0 0.6 0.4 0.3 0.9 1 0.18 1 0.5 0.15 0.3 4 3 4 0.3 0 0.8 0.2 0.1 0.8 0.192 3 0.4 0.2 0.192 0.18 0.15 3 0.27
k 0 3 3 3 + 3 3 = 18 2 1 2 0.5 0 0.6 0.4 0.3 0.9 1 0.18 1 0.5 0.15 0.3 4 3 4 0.3 0 0.8 0.2 0.1 0.8 2 0.048 3 0.4 0.096 0.2 0.18 0.15 0.096 0.048 3 0.27 0.192
k 0 3 3 3 + 3 3 = 18 2 1 2 0.5 0 0.6 0.4 0.3 0.9 1 3 1 0.5 0.15 0.3 4 3 4 0.3 0 0.8 0.2 0.1 0.8 2 0.048 3 0.4 0.096 0.2 0.15 0.096 0.048 3 0.27 0.192 0.18
k 0 3 3 3 + 3 3 = 18 2 1 2 0.5 0 0.6 0.4 0.3 0.9 1 3 1 0.5 0.15 0.3 4 3 4 0.3 0 0.8 0.2 0.1 0.8 2 0.048 3 0.4 0.096 0.2 0.15 0.096 0.048 3 0.27 0.192 0.18 O( E + Q k logk)
M = (Q,Σ,,I,R) Q I Q Σ R (Q Σ(X)) T ((Q X)) r R (q,σ (k) (x 1,...,x k )) u q Qσ (k) Σx 1,...,x k X u T ((Q X k )) (, (x 1,x 2,x 3 )) ((,x 1 )(,x 3 )) (, x 1 x 2 x 3 ) (,x 1 ) (,x 3 )
(q,σ (k) (x 1,...,x k )) u q Qσ (k) Σ q Qσ (k) Σ x 1,...,x k ( 0, x 1 x 2 ) ( 1,x 2 ) ( 2,x 2 ) ( 0,x 1 ) x 1,...,x k ( 1, ) x 1 x 2 ( 0,x 2 )
s r M t s,t T ((Q T Σ )) r = (q,σ(x 1,...,x k )) u v pos(s) s(v) = (q,σ(s 1,...,s k )) s[ φ(u)] v = t s 1,...,s k T ((Q X)) φ = {(q 1,x 1 ) (q 1,s 1 ),...,(q k,x k ) (q k,s k )} r = (, (x 1,x 2,x 3 )) ((,x 1 )(,x 3 )) φ = {(,x 1 ) (, ),(,x 3 ) (, )} (, ) r (, ) (, )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 ( ) ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 ( ) ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 x 1,x 2,x 3 x 3 x 1 ( ) ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 x 1,x 2,x 3 x 3 x 1 x 1 x 1 ( ) ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 x 1,x 2,x 3 x 3 x 1 x 1 x 1 ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 x 1,x 2,x 3 x 3 x 1 x 1 x 1 ( )
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 x 1,x 2,x 3 x 3 x 1 x 1 x 1
M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 x 1,x 2,x 3 x 3 x 1 x 1 x 1 Tr(M) = {(s,t) T Σ T (q,s) M t,q I}
M = (Q,Σ,,I,R,π) r = (q,σ (k) (x 1,...,x k )) w u π(r) = w (,(x 1,x 2,x 3 )) 0.723 ((,x 1 ),(,x 3 ),(,x 1 )) (,(x 1,x 2 )) 0.893 ((,x 2 ),(,x 1 )) (,) 1.0 (,(x 1,x 2 )) 0.91 (,(,x 1 ),(,x 2 )) (,(x 1,x 2,x 3 )) 1.0 (,(,x 1 ),(,x 2 ),(,x 3 )) (,) 0.853 (,) 0.588
A = {Q,Σ,F,E,π 1 } R = /0 σ (k) (q 1,...,q k ) w q E r (q,σ (k) (x 1,...,x k )) w σ (k) ((q 1,x 1 ),...,(q k,x k )) R R {r} π(r) w M = {Q,Σ,Σ,F,R,π} O( E ) α t 3 σ t 1 α t 4 σ t 0 β t 2
A = {Q,Σ,F,E,π 1 } R = /0 σ (k) (q 1,...,q k ) w q E r (q,σ (k) (x 1,...,x k )) w σ (k) ((q 1,x 1 ),...,(q k,x k )) R R {r} π(r) w M = {Q,Σ,Σ,F,R,π} O( E ) αα t 3 σσ t 1 αα t 4 σσ t 0 ββ t 2
M = {Q,Σ,,I,R,π 1 } P = /0 q Q x X φ((q,x)) = q (q,σ (k) (x 1,...,x k )) w t R r q w φ(t) P P {r} π(r) w G = {Q,,P,π,I} O( R max r R size(r)) (q,σ (k) (x 1,x 2 )) α (β((q 1,x 1 )) β((q 2,x 2 ))) q w α(β(q 1 ) β(q 2 ))
M 1 M 2 M 1 M 2 A M A M A M A M = =
M 1 M 2 M 1 M 2 A M A M A M A M = =
(, a ) x 1 (,b) b (,x 1 ) a (,x 1 ) a b b q a(q) q a a. b
(, a ) x 1 (,b) b (,x 1 ) a (,x 1 ) a b b q a(q) q a a. b {,,,, }
σ M f 1 M γ 2 σ β f g ξ λ δ α α a a b λ λ λ M 1 M 2
M 1 = {Q,Σ,Γ,I 1,R 1 }M 2 = {P,Γ,,I 2,R 2 } M 1 ΓM 2 Γ
M 1 = {Q,Σ,Γ,I 1,R 1 }M 2 = {P,Γ,,I 2,R 2 } M 1 ΓM 2 Γ M 1 M 2 = {P Q,Σ,,I 2 I 1,R} M 2 Σ (Q X) ((P Q) X) p Pq Q(p,(q,x i )) ((p,q),x i )R 2
M 1 = {Q,Σ,Γ,I 1,R 1 }M 2 = {P,Γ,,I 2,R 2 } M 1 ΓM 2 Γ M 1 M 2 = {P Q,Σ,,I 2 I 1,R} M 2 Σ (Q X) ((P Q) X) p Pq Q(p,(q,x i )) ((p,q),x i )R 2 R = {((p,q),σ (k) (x 1,...,x k )) u (q,σ (k) (x 1,...,x k )) w R 1,u Tr(p,w)} Tr(p,w) = {u T (((P Q) X)) (p,w) M 2 u}
M 1 = {Q,Σ,Γ,I 1,R 1 } Q = { 0, 1, 2 } I 1 = { 0 } Σ = {σ (2),α (0),β (0) } Γ = { f (2),g (1),a (0),b (0) } R 1 = {(1.1),(1.2),(1.3),(1.4)} ( 0, σ ) f x 1 x 2 ( 1,x 1 ) ( 2,x 2 ) ( 1, σ ) f x 1 x 2 ( 2,x 1 ) ( 2,x 2 ) ( 2,α) ( 2,β) a g b M 2 = {P,Γ,,I 2,R 2 } P = { 0, 1, 2 } I 2 = { 0 } Γ = { f (2),g (1),a (0),b (0) } = {γ (3),ξ (2),δ (1),λ (0) } R 2 = {(2.1),(2.2),(2.3),(2.4),(2.5)} ( 0, f x 1 ( 1, f x 1 x 2 x 2 ( 2,a) ( 2, g ) x 1 ( 2,b) ) ) λ ( 1,x 1 ) δ ( 2,x 1 ) λ ( 2,x 1 ) γ λ ξ ( 2,x 2 ) ( 2,x 2 )
M 1 = {Q,Σ,Γ,I 1,R 1 } Q = { 0, 1, 2 } I 1 = { 0 } Σ = {σ (2),α (0),β (0) } Γ = { f (2),g (1),a (0),b (0) } R 1 = {(1.1),(1.2),(1.3),(1.4)} M 2 = {P,Γ,,I 2,R 2 } Γ = { f (2),g (1),a (0),b (0) } {( 1,x 1 ),( 2,x 2 ),...} = {γ (3),ξ (2),δ (1),λ (0) } {(( 1, 1 ),x 1 ),(( 2, 2 ),x 2 ),...} R 2 = {(2.1),...,(2.5)} { ( 1,( 1,x 1 )) (( 1, 1 ),x 1 ), ( 2,( 2,x 2 )) (( 2, 2 ),x 2 ),...}
M 1 M 2 = {P Q,Σ,,I 2 I 1,R} P Q = {( 0, 0 ),( 1, 1 ),( 2, 2 ),...} I 2 I 1 = {( 0, 0 )} ( 0, σ ) f ( 0, f ) γ x 1 x 2 ( 1,x 1 ) ( 2,x 2 ) x 1 x 2 ( 1,x 1 ) λ ( 2,x 2 ) ( 1,( 1,x 1 )) (( 1, 1 ),x 1 ) ( 2,( 2,x 2 )) (( 2, 2 ),x 2 )
M 1 M 2 = {P Q,Σ,,I 2 I 1,R} P Q = {( 0, 0 ),( 1, 1 ),( 2, 2 ),...} I 2 I 1 = {( 0, 0 )} (( 0, 0 ), σ ) γ x 1 x 2 ( 1,( 1,x 1 )) λ ( 2,( 2,x 2 )) ( 1,( 1,x 1 )) (( 1, 1 ),x 1 ) ( 2,( 2,x 2 )) (( 2, 2 ),x 2 )
M 1 M 2 = {P Q,Σ,,I 2 I 1,R} P Q = {( 0, 0 ),( 1, 1 ),( 2, 2 ),...} I 2 I 1 = {( 0, 0 )} (( 0, 0 ), σ x 1 x 2 ) γ (( 1, 1 ),x 1 ) λ ( 2,( 2,x 2 )) ( 2,( 2,x 2 )) (( 2, 2 ),x 2 )
M 1 M 2 = {P Q,Σ,,I 2 I 1,R} P Q = {( 0, 0 ),( 1, 1 ),( 2, 2 ),...} I 2 I 1 = {( 0, 0 )} (( 0, 0 ), σ x 1 x 2 ) γ (( 1, 1 ),x 1 ) λ (( 2, 2 ),x 2 )
M 1 M 2 = {P Q,Σ,,I 2 I 1,R} P Q = {( 0, 0 ),( 1, 1 ),( 2, 2 ),...} I 2 I 1 = {( 0, 0 )} (( 0, 0 ), (( 1, 1 ), σ x 1 (( 2, 2 ),α) σ x 1 x 2 ) x 2 λ ) γ (( 1, 1 ),x 1 ) λ (( 2, 2 ),x 1 ) ξ (( 2, 2 ),x 2 ) (( 2, 2 ),x 2 ) (( 2, 2 ),β)... δ λ
Tr(M 1 ) Tr(M 2 ) Tr(M 1 ) Tr(M 2 ) = {(s,u) T Σ T (s,t) Tr(M 1 ) (t,u) Tr(M 2 )} Tr(M 1 ) Tr(M 2 ) = Tr(M 1 M 2 ) M 2 M 1 M 2 M 1 M 1 M 2
M (s,t) T Σ T Γ τ M (s,t) = q I (q,s) r 1M r k M t k i=1 π(r i) τ M1 M 2 (s,u) = t TΓ { τm1 (s,t) + τ M2 (t,u) } M 1 M 2 M 2
M 2 = =...
R (Q Σ(X)) T ((Q X)) r R (q,σ (k) (x 1,...,x k )) u R ext (Q T Σ (X)) T ((Q X)) (, ) x 1 x 2 (,x 1 ) (,x 2 )
M ( 0, x 1 x 2 ) ( 1, ) x 1 x 2 ( 2, ) x 1 x 2 ( 1,x 2 ) ( 0,x 2 ) ( 0,x 1 ) ( 2,x 2 ) ( 0,x 1 ) (, x 1 x 2 x 3 ) (,x 3 ) (,x 2 ) (,x 1 )
M 1 M 2
k
k k
https://github.com/isi-nlp/tiburon http://staffwww.dcs.shef.ac.uk/people/t.cohn/t3/