木オートマトン•トランスデューサによる自然言語処理

Size: px

Start display at page:

Download "木オートマトン•トランスデューサによる自然言語処理"

ふじよしはぎにわ
9 years ago
Views:

1 木オートマトントランスデューサによる自然言語処理林克彦 NTTコミュニケーション科学基礎研究所

2 n

6 I T 1 T 2 I T 1 Pro j(i T 1 T 2 )

9 (Σ,rk) Σ rk : Σ N {0} nσ (n) rk(σ) = n σ Σ n Σ (n) Σ (n)(σ,rk)σ

10 Σ 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)

12 ε pos(t) = {ε} {i.v 1 i k,v pos(t i )}

13 ε pos(t) = {ε} {i.v 1 i k,v pos(t i )} v pos(t) t(v) t(ε) = t(3.3) =

14 ε 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 =

15 ε 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 =

16 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 =

17 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

19 G = (N,Σ,P,I) N I N Σ P n u P n N u T Σ (N)

20 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

21 G = (N,Σ,P,I) N = { } Σ = { } I = {} P

22 G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 1

23 G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 2 p 1 p 2

24 p 1 G = (N,Σ,P,I) N = { } Σ = { } I = {} P p 1 p 2 p 3 p 2 p 3

25 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

26 {, }

28 {,,,, } {b 2n n 0}

29 {,,,, } {b 2n n 0} 0 b 0 1 ( 0 ) 1 (x) a x x

31 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

32 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E

33 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1.1)= ρ(2)= ρ(3.1.1)= ρ(3.2)= ρ(3.3.1)=

34 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1.1)= ρ(3.2)= ρ(3.3.1)=

35 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1)= ρ(3.1.1)= ρ(3.2)= ρ(3.3.1)=

36 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1)= ρ(3.1.1)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=

37 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=

38 A = (Q,Σ,F,E) Q = { } F = {} Σ = { } E ρ(1)= ρ(1.1)= ρ(2)= ρ(ε)= ρ(3.1)= ρ(3.1.1)= ρ(3)= ρ(3.2)= ρ(3.3)= ρ(3.3.1)=

39 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)=

40 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

41 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)=

42 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)=

43 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)=

44 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)=

45 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)=

46 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)=

47 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)=

48 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)=

49 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)=

50 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)=

51 = F I σ(q 1,...,q k ) q σ(q) (q 1,...,q k ) {, } = =

52 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

53 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 )

54 g n n n A = {Q,Σ,F,E,π} r = σ(q 1,...,q k ) w q E π(r) = w

55 k k

56 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

57 k 1 k???? 1? k

58 k =

59 k =

60 k =

61 k =

62 k =

63 k = O( E + Q k logk)

65 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 )

66 (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 )

67 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 (, ) (, )

68 M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R ( )

69 M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 ( ) ( )

70 M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 ( ) ( )

71 M = (Q,Σ,,I,R) Q = { } I = {} Σ = { } = { } R x 1,x 2,x 3 x 1 x 3 x 1 x 1 ( )

72 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 ( ) ( )

73 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 ( ) ( )

74 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 ( )

75 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 ( )

76 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

77 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}

80 M = (Q,Σ,,I,R,π) r = (q,σ (k) (x 1,...,x k )) w u π(r) = w (,(x 1,x 2,x 3 )) ((,x 1 ),(,x 3 ),(,x 1 )) (,(x 1,x 2 )) ((,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.588

82 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

83 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

84 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 ))

85 M 1 M 2 M 1 M 2 A M A M A M A M = =

86 M 1 M 2 M 1 M 2 A M A M A M A M = =

88 (, a ) x 1 (,b) b (,x 1 ) a (,x 1 ) a b b q a(q) q a a. b

89 (, a ) x 1 (,b) b (,x 1 ) a (,x 1 ) a b b q a(q) q a a. b {,,,, }

90 σ M f 1 M γ 2 σ β f g ξ λ δ α α a a b λ λ λ M 1 M 2

91 M 1 = {Q,Σ,Γ,I 1,R 1 }M 2 = {P,Γ,,I 2,R 2 } M 1 ΓM 2 Γ

92 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

93 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}

94 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 )

95 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 ),...}

96 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 )

97 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 )

98 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 )

99 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 )

100 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 ),β)... δ λ

101 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

102 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

103 M 2 = =...

104

105 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 )

106 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 )

107 M 1 M 2

108

109

110

111 k

112 k k

113

木オートマトン•トランスデューサによる 自然言語処理

木オートマトン•トランスデューサによる自然言語処理