Biểu diễn văn phạm pcfg probabilistic context-free grammar năm 2024

TÛm tắt Trong b‡i n‡y, ch ̇ng tÙi nghiÍn cứu phương ph·p xử l ̋ hiện tượng nhập nhằng v‡ c·c hiện tượng c ̇ ph·p phụ thuộc từ trong ph‚n tÌch c ̇ ph·p tiếng Việt. Ch ̇ng tÙi đề xuất việc x‚y dựng một cÙng cụ ph‚n tÌch c ̇ ph·p dựa trÍn văn phạm phi ngữ cảnh với luật cÛ chứa thÙng tin về x·c suất v‡ từ v ựng. X·c suất luật được tÌnh dựa trÍn tập ngữ liệu mẫu, sử d ụng mÙ hÏnh bigram, kết hợp với phương ph·p l‡m trơn nội suy tuyến tÌnh để giảm ảnh hưởng của từ cụ thể đối với x·c suất. Việc ph‚n tÌch c ̇ ph·p c‚u được tiến h‡nh dựa trÍn từ trọng t‚m của c‚u (từ điều khiển trung t‚m). C·c kết quả đạt được bước đầu cho thấy c·ch tiếp cận n‡y khả thi.

Từ kho· : xử l ̋ ngÙn ngữ tự nhiÍn, ph‚n tÌch c ̇ ph·p, x·c suất, văn phạm phi ngữ cảnh

1. Giới thiệu

Ph‚n tÌch c ̇ ph·p l‡ một vấn đề cơ bản v‡ quan trọng trong xử l ̋ ngÙn ngữ tự nhiÍn. Với một cÙng cụ ph‚n tÌch c ̇ ph·p tốt, ch ̇ng ta cÛ thể tÌch hợp v‡o nhiều ứng dụng trong xử l ̋ ngÙn ngữ tự nhiÍn như dịch m·y, tÛm tắt văn bản, c·c hệ thống hỏi đ·p, Ö để tăng tÌnh chÌnh x·c của c·c ứng dụng đÛ. Hiện nay, c·c cÙng cụ ph‚n tÌch c ̇ ph·p tiếng Việt đ„ đạt được một số kết quả nhất định. Tuy nhiÍn, phần lớn c·c kết quả đạt được mới dừng ở một số trường hợp c‚u cơ bản như c‚u đơn v‡ c·c c‚u ghÈp đơn giản. Hiện tượng nhập nhằng v‡ những trường hợp đặc biệt trong ph‚n tÌch c‚u vẫn chưa được giải quyết thoả đ·ng. Trong b‡i n‡y, ch ̇ng tÙi sẽ đề xuất c·ch giải quyết c·c vấn đề đÛ thÙng qua văn phạm phi ngữ cảnh cÛ bổ sung thÙng tin về từ vựng v‡ x·c suất v‡o luật c ̇ ph·p. Việc ph‚n tÌch c ̇ ph·p c‚u được tiến h‡nh dựa trÍn từ trọng t‚m của c‚u, sử dụng một phương ph·p cải tiến của mÙ hÏnh x·c suất thống kÍ Collins [5]. Trong phần sau, ch ̇ng tÙi sẽ trÏnh b‡y một số v ấn đề cÚn tồn tại trong ph‚n tÌch c ̇ ph·p tiếng Việt v‡ đề xuất c·ch giải quyết cho c·c vấn đề đÛ. Phần 3 giới thiệu một số nÈt chÌnh trong việc sử dụng văn phạm phi ngữ c ảnh từ vựng ho· kết hợp x·c suất (Lexicalized Probability Context Free Grammar ñ LPCFG) v‡o ph‚n tÌch c ̇ ph·p tiếng Việt. C·ch tÌnh x·c suất luật d ̆ng trong LPCFG được thảo luận phần 4. Tiếp theo, ch ̇ng tÙi sẽ mÙ tả thuật to·n ph‚n tÌch c ̇ ph·p sử dụng LPCFG. Phần 6 giới thiệu một số kết quả đạt được. Cuối c ̆ng l‡ kết luận v‡ hướng ph·t triển của nghiÍn cứu n‡y.

2. Một số vấn đề trong ph‚n tÌch c ̇ ph·p tiếng Việt

2. Hiện tượng nhập nhằng trong ph‚n tÌch c ̇ ph·p tiếng Việt

Trong ph‚n tÌch c ̇ ph·p tiếng Việt, hiện tượng nhập nhằng xảy ra ở nhiều mức, từ mức từ, từ loại đến mức c ̇ ph·p c‚u. Điều n‡y dẫn đến một c‚u cÛ thể được ph‚n tÌch theo nhiều c·ch kh·c nhau, trong khi chỉ cÛ một v‡i c·ch ph‚n tÌch trong số đÛ đ ̇ng. Trong b‡i n‡y, ch ̇ng tÙi ch ̇ trọng giải quyết vấn đề ở m ức c ̇ ph·p. Qua khảo s·t việc ph‚n tÌch c ̇ ph·p c·c c‚u tiếng Việt, ch ̇ng tÙi thấy cÛ hai loại nhập nhằng. Một loại nhập nhằng do c‚u cÛ thể hiểu theo nhiều nghĩa kh·c nhau dẫn đến c·c c‚y c ̇ ph·p kh·c nhau. Trong trường hợp n‡y, mỗi c·ch hiểu sẽ ứng với một c‚y c ̇ ph·p v‡ c·c c‚y c ̇ ph·p đÛ đều được chấp nhận. VÌ

dụ c‚u ì TÙi nhÏn thấy anh Hải ở tầng hai î cÛ thể hiểu theo hai c·ch. C·ch thứ nhất, khi tÙi nhÏn thấy anh Hải thÏ anh ấy đang ở tầng hai. Trong trường hợp n‡y, ở tầng hai bổ nghĩa cho danh ngữ anh Hải. C·ch hiểu thứ hai, khi tÙi đứng ở tầng hai thÏ tÙi nhÏn thấy anh Hải. Trong trường hợp n‡y, ở tầng hai l‡ bổ ngữ của tÙi nhÏn thấy anh Hải. Với loại nhập nhằng thứ hai, c‚u chỉ cÛ một nghĩa nhưng bộ ph‚n tÌch c ̇ ph·p vẫn tạo ra nhiều c‚y c ̇ ph·p, trong đÛ chỉ cÛ một c‚y đ ̇ng. L ̋ do của sự nhập nhằng n‡y l‡ qu· trÏnh ph‚n tÌch c ̇ ph·p đ„ lược bỏ ngữ nghĩa từ/ngữ m‡ chỉ quan t‚m đến nh„n c ̇ ph·p của ch ̇ng, dẫn đến nhiều luật c ̇ ph·p cÛ thể ·p dụng để ph‚n tÌch c‚u. VÌ dụ, với c‚u ì HÙm nay trời mưa î, tập luật c ̇ ph·p thuộc văn phạm phi ngữ cảnh (Context Free Grammar ñ CFG) 1 cần để ph‚n tÌch c‚u n‡y l‡:

1. Æ
2. Æ
3. Æ
4. Æ
5. Æ
6. Æ
7. Æ<Động ngữ>
8. Æ<Động từ> Trong từ điển từ, hÙm nay l‡ danh từ hoặc phÛ từ, trời l‡ danh từ, cÚn mưa l‡ động từ. Với tập luật c ̇ ph·p trÍn, c·c c‚y c ̇ ph·p cÛ thể sinh ra cho c‚u n‡y được biểu diễn ở hÏnh 1.

Trong hai c‚y c ̇ ph·p ở hÏnh 1 chỉ cÛ c‚y (a) đ ̇ng, c‚y (b) cần được loại bỏ hoặc khÙng sinh ra trong qu· trÏnh ph‚n tÌch c ̇ ph·p. Một trong những c·ch giải quyết vấn đề trÍn l‡ ph‚n loại chi tiết hơn c·c nh„n từ loại/ngữ loại v‡ kiểm so·t khả năng kết hợp giữa ch ̇ng. Thay vÏ luật Æ, ta đưa ra luật Æ. Nhược điểm của phương ph·p n‡y l‡:

• Hiện nay, việc đặt tÍn cho c·c từ loại/ngữ loại vẫn cÚn nhiều điểm chưa thống nhất. VÏ vậy việc ph‚n chia từ loại ở mức chi tiết hơn nữa sẽ c‡ng cÛ nhiều bất đồng quan điểm. Nếu việc n‡y khÙng phải do c·c nh‡ ngÙn ngữ chuyÍn về tiếng Việt l‡m thÏ khả năng sai sÛt l‡ rất lớn.
• Khi ph‚n loại chi tiết c·c từ loại/ngữ loại, kÌch thước tập luật c ̇ ph·p tăng lÍn đ·ng kể.
• Với phương ph·p n‡y, muốn cÛ một bộ ph‚n tÌch c ̇ ph·p chÌnh x·c, ch ̇ng ta sẽ phải x‚y dựng một c·ch thủ cÙng tập luật c ̇ ph·p ứng với tập nh„n từ loại mới. Việc x‚y dựng một c·ch đầy đủ t ập tất cả c·c luật ở m ức chi tiết như v ậy l‡ một giải ph·p khÛ thực hiện do khÛ kiểm so·t được tÌnh chÌnh x·c v‡ chặt chẽ của ch ̇ng. Ho‡ng Vĩnh Sơn [7] sử dụng c·ch tiếp cận n‡y. Do việc đặt tÍn từ loại ở mức chi tiết cÛ nhiều chỗ khÙng hợp l ̋ (từ loại đặt tÍn sai hoặc một từ cÛ thÍm nhiều từ loại chi tiết) v‡ tập luật c ̇ ph·p chưa chuẩn, bộ ph‚n tÌch c ̇ ph·p trong [7] đưa ra qu· nhiều c‚y c ̇ ph·p tương tự nhau (chỉ kh·c tÍn từ loại) v‡ nhiều c‚y c ̇ ph·p sai cho một c‚u đầu v‡o. Thay vÏ x‚y dựng

1 Theo [8], văn phạm phi ngữ cảnh l‡ lựa chọn thÌch hợp để ph‚n tÌch c ̇ ph·p tiếng Việt.

HÙm nay trời mưa

PhÛ từ Danh từ Động từ

Trạng ngữ Chủ ngữ Vị ngữ

C‚u

HÙm nay trời mưa

Danh từ Danh từ Động từ

Danh ngữ

Chủ ngữ

Vị ngữ

C‚u

(a) (b) HÏnh 1 ñ C·c c‚y c ̇ ph·p dựa trÍn tập luật phi ngữ cảnh của c‚u ì HÙm nay trời mưa î

Hai c‚y (2), (2) c ̆ng ·p dụng một tập luật ph‚n tÌch c ̇ ph·p như nhau nhưng với thứ tự kh·c nhau. Theo c·ch tÌnh P(c‚y)=TÌch(P(c·c luật ·p dụng)) ), hai c‚y c ̇ ph·p cÛ gi· trị x·c suất ngang nhau nhưng chỉ cÛ c‚y (2) đ ̇ng. Điểm mấu chốt trong ph‚n tÌch danh ngữ n‡y l‡: từ ì v‡ î thường d ̆ng để kết nối hai phần cÛ nội dung tương đương nhau, ì phần trước î v‡ ì phần n‡y î tương đương nhau hơn l‡ ì vấn đề trong phần trước î v‡ ì phần n‡y î. VÏ vậy c‚y c ̇ ph·p (2) được chọn. Với những trường hợp như v ậy, ngo‡i việc sử d ụng x·c suất, việc đưa thÙng tin của từ v‡o trong tập luật c ̇ ph·p l‡ cần thiết.

2 Việc x·c định c‚u đ ̇ng c ̇ ph·p đÙi khi phụ thuộc v‡o c·c từ cụ thể cấu tạo nÍn c‚u

Như đ„ nÛi ở phần trÍn, để giải quyết nhập nhằng trong ph‚n tÌch c ̇ ph·p, đÙi khi ch ̇ng ta cần đến thÙng tin về từ cụ thể. Ch ̇ng ta cÚn gặp nhiều trường hợp kh·c trong tiếng Việt m‡ việc x·c định c‚u đ ̇ng c ̇ ph·p hay khÙng phụ thuộc v‡o từ cụ thể cấu tạo nÍn c‚u. VÌ dụ ì TÙi ăn î Ìt khi được chấp nhận l‡ một c‚u ho‡n chỉnh trong một ngữ cảnh chung. TÌnh ho‡n chỉnh ở đ‚y nhÏn từ phÌa cảm nhận của người nghe, anh ta cÛ cảm thấy thỏa m„n một lượng thÙng tin hay khÙng. Trong ngữ cảnh chung ì TÙi ăn î mang một gi· trị thÙng tin nhỏ. Với c‚u n‡y, nếu ta chỉ d ựa trÍn c·c từ loại của c‚u v‡ luật c ̇ ph·p c‚u cÛ thể được hÏnh th‡nh từ m ột danh từ đứng trước một động từ thÏ c‚u trÍn ho‡n to‡n đ ̇ng ngữ ph·p. ì TÙi đang ăn î dễ được chấp nhận l‡ c‚u ho‡n chỉnh hơn vÏ trong một ngữ c ảnh chung mệnh đề trÍn mang một gi· trị thÙng tin kh· lớn. Với những trường hợp nÛi trÍn, ch ̇ng ta phải dựa trÍn tÌnh chất cụ thể của từ giữ vai trÚ chÌnh trong c‚u hoặc ngữ để x·c định xem c‚u/ngữ đÛ cÛ đ ̇ng c ̇ ph·p hay khÙng. Trong ph‚n tÌch c ̇ ph·p tiếng Việt, ch ̇ng ta cÚn thấy hiện tượng nhập nhằng do lược bỏ quan hệ t ừ. Ch ̇ng ta cÛ thể nÛi bạn tÙi, con tÙi m‡ khÙng nÛi con chÛ tÙi, con mËo tÙi. Trong trường hợp n‡y, bạn tÙi, con tÙi cần được coi l‡ c·c danh ngữ, trong khi con chÛ tÙi, con mËo tÙi cần được coi l‡ c·c cụm từ sai ngữ ph·p. Qua c·c vấn đề đ„ ph‚n tÌch ở trÍn, ch ̇ng tÙi thấy rằng bản th‚n từ c ũng cÛ vai trÚ quan trọng trong qu· trÏnh ph‚n tÌch c ̇ ph·p. VÏ vậy, ch ̇ng tÙi đề xuất việc x‚y dựng một cÙng cụ ph‚n tÌch c ̇ ph·p cho phÈp ph‚n tÌch s‚u hơn văn phạm phi ngữ c ảnh kết hợp x·c suất bằng c·ch đưa thÙng tin từ vựng v‡o văn phạm. Văn phạm n‡y sẽ được trÏnh b‡y kỹ hơn ở phần sau.

3. Ph‚n tÌch c ̇ ph·p sử dụng Văn phạm phi ngữ cảnh từ vựng ho· kết hợp x·c suất

Văn phạm phi ngữ cảnh từ vựng ho· kết hợp x·c suất (Lexicalized Probability Context Free Grammar ñ LPCFG) l‡ một biến thể c ủa văn phạm phi ngữ c ảnh 2 b ằng c·ch đưa thÍm x·c suất luật v‡ thÙng tin từ vựng v‡o c·c luật c ̇ ph·p. Trong văn phạm n‡y, từ vựng đÛng vai trÚ quan trọng trong việc x·c định c·c từ/ngữ n‡o cÛ thể kết hợp với nÛ.

Th‡nh phần chÌnh trong CFG l‡ tập luật c ̇ ph·p. Với mÙ hÏnh PCFG, mỗi luật c ̇ ph·p được gắn với x·c suất sử dụng của nÛ. Nếu ta lưu c·c luật LPCFG theo c·ch lưu của mÙ hÏnh CFG/PCFG, với mỗi luật đi kËm với c·c từ cụ thể thÏ khÙng khả thi vÏ l ̇c đÛ số lượng c·c luật cần đưa v‡o bộ ph‚n tÌch c ̇ ph·p qu· lớn. Để giải quyết vấn đề n‡y, ta sử dụng c·ch lưu trữ luật kh·c: ta chỉ ghi lại c·c th‡nh phần chÌnh của luật thay vÏ cả luật. VÌ dụ: (1) C‚u → Động ngữ (3) C‚u → TÌnh ngữ (2) Động ngữ → Động từ (4) TÌnh ngữ → TÌnh từ Luật (1) cÛ thể hiểu l‡ một cụm từ cÛ th‡nh phần trung t‚m l‡ động ngữ thÏ cÛ thể ph·t triển lÍn th‡nh c‚u. Luật (2) cÛ thể hiểu l‡ một cụm từ cÛ th‡nh phần trung t‚m l‡ động từ thÏ cÛ thể ph·t triển lÍn th‡nh động ngữ.

2 Trong b‡i n‡y, ch ̇ng tÙi giả thiết người đọc đ„ cÛ kiến thức về văn phạm phi ngữ cảnh [9] v‡ văn phạm phi ngữ cảnh d ̆ng trong ph‚n tÌch c ̇ ph·p tiếng Việt.

Một th‡nh phần phụ cÛ kết hợp được với th‡nh phần trung t‚m hay khÙng phụ thuộc v‡o x·c suất kết hợp với trung t‚m, tÌnh được dựa trÍn tập mẫu. Với mỗi tập mẫu cho trước, trước tiÍn ch ̇ng ta tiến h‡nh trÌch r ̇t luật dựa trÍn tần số xuất hiện của nÛ trong tập mẫu, sau đÛ r ̇t ra c·c x·c suất phụ thuộc giữa từ loại v‡ k ̋ hiệu khÙng kết th ̇c. C·ch biểu diễn luật v‡ c·ch tÌnh x·c suất luật c ̇ ph·p trong LPCFG được mÙ tả trong phần 4. Khi ph‚n tÌch c‚u theo LPCFG, ch ̇ng ta dựa trÍn từ chÌnh trong c·c th‡nh phần c‚u. Thuật to·n ph‚n tÌch c ̇ ph·p LPCFG được trÏnh b‡y ở phần 5. Mỗi th‡nh phần c‚u trong c·ch biểu diễn phi ngữ cảnh được gắn với từ chÌnh v‡ từ loại tương ứng của nÛ. VÌ dụ, c‚y c ̇ ph·p của c‚u ì TÙi đang thuyết trÏnh î trong LPCFG được biểu diễn như sau:

trong đÛ C l‡ c‚u, DDT l‡ động từ, DDN l‡ động ngữ, PT-T l‡ phụ t ừ chỉ thời gian, DT l‡ danh từ, D-C l‡ đối tượng l‡m đối thể hay chủ thể của c‚u.

4. TÌnh x·c suất luật c ̇ ph·p trong văn phạm LPCFG

Luật c ̇ ph·p trong LPCFG ch ̇ trọng đến từ chÌnh trong đoạn m‡ nÛ ph‚n tÌch. Dựa trÍn từ chÌnh, bộ ph‚n tÌch c ̇ ph·p mở rộng sang tr·i v‡ phải để x‚y dựng ngữ v‡ c‚u. Một luật c ̇ ph·p LPCFG được biểu diễn như sau: PP(h)ÆLn(ln)Ö L 1 (l 1 ) H(h) R 1 (r 1 )Ö Rm(rm), với PP, Li, Ri tương ứng với ngữ loại/từ loại của ngữ với từ chÌnh h, từ li, từ ri. Ta gọi phÌa bÍn tr·i của luật l‡ LHS (Left Hand Side), phÌa phải của luật l‡ RHS (Right Hand Side). H l‡ th‡nh phần trung t‚m (Head) của luật PP, được thừa hưởng từ chÌnh h của luật PP. Ngữ chứa từ chÌnh H được mở rộng sang hai bÍn bằng c·c cặp nh„n/từ Li(li) v‡ Ri(ri). Đ‚y l‡ c·c th‡nh phần phụ cho trung t‚m H(h) để tạo th‡nh PP. Trong trường hợp n= v‡ m=0, ta cÛ thể hiểu l‡ con chÌnh H khÙng thể mở rộng sang hai bÍn được nữa. Trong c·ch viết mở rộng, ta bổ sung v‡o phÌa phải của luật PP hai th‡nh phần Ln+1 = Start, Rm+1 = Stop, ứng với c·c k ̋ hiệu bắt đầu v‡ kết th ̇c ngữ. VÌ dụ, xÈt luật: C(DDT,thuyết trÏnh)ÆD-C(Dt,tÙi)DDN(DDT,thuyết trÏnh) với C l‡ c‚u, DDT l‡ động từ, DDN l‡ động ngữ, D-C l‡ đối tượng l‡m đối thể hay chủ thể của c‚u, Dt l‡ đại từ. Th‡nh phần chÌnh trong vế phải của luật l‡ động ngữ. C·c tham số của luật PP trong trường hợp n‡y l‡: n = 1 m = 0 PP = C H = DDN L 1 = D-C L 2 = Start h = (DDT,thuyết trÏnh) l 1 = (Dt,tÙi) R 1 = Stop X·c suất luật được tÌnh theo cÙng thức P(RHS/LHS)=đếm(RHS)/đếm(LHS). Tuy nhiÍn, do ta đưa từ vựng v‡o luật nÍn x·c suất luật sẽ rất nhỏ. Để giải quyết vấn đề n‡y, ch ̇ng tÙi loại bỏ c·c th‡nh phần độc lập hoặc phụ thuộc rất Ìt v‡o luật. NÛi c·ch kh·c, ch ̇ng tÙi chia

C

(DDT,thuyết trÏnh)

D-C

(Dt,tÙi)

Dt (Dt,tÙi)

DDN

(DDT,thuyết trÏnh)

DDT

(DDT,thuyết trÏnh)

PT-T

(PT-T,đang)

HÏnh 3 ñ C‚y c ̇ ph·p của c‚u ì TÙi đang thuyết trÏnh î

P(li+1w | PP, li+1t lit liw) = λ 1 * P(li+1w | PP, li+1t lit liw)+(1- λ 1 )( λ 2 * P(li+1w | PP, li+1t lit)+(1- λ 2 )* P(li+1w| PP, li+1t). (4) Trong cÙng thức (3), nếu λ = 0, từ v‡ từ loại cÛ vai trÚ ngang nhau trong việc ước lượng x·c suất P(li+1t | PP, lit liw). Nếu λ = 0, x·c suất P(li+1t | PP, lit liw) chỉ phụ thuộc từ loại m‡ khÙng phụ thuộc từ. Tương tự với cÙng thức (4). C·ch ước lượng n‡y đem lại tÌnh linh động cho mÙ hÏnh. NÛ cho phÈp biểu diễn luật phụ thuộc từ m ức c·c k ̋ hiệu khÙng kết th ̇c đến mức từ. Khi điều kiện ở m ức chi tiết hơn khÙng đ·p ứng được, hệ thống cÛ thể điều chỉnh hệ số l‡m trơn để quy về mức thÙ hơn. Nếu một c‚u đầu v‡o n‡o đÛ sử dụng c·c từ kh·c xa so với c·c c‚u trong tập mẫu, bộ ph‚n tÌch vẫn cÛ thể đưa ra được c‚y ph‚n tÌch cho c‚u đÛ nếu trong tập mẫu cÛ c·c luật c ̇ ph·p ph ̆ hợp. Trường hợp n‡y tương tự như trường hợp khÙng đưa từ v ựng v‡o luật ph‚n tÌch c ̇ ph·p vÏ c·c x·c suất cÛ kết hợp từ vựng được giảm nhẹ về trường hợp khÙng kết hợp từ vựng.

Điều chỉnh hệ số l‡m trơn λ Vấn đề quan trọng ở đ‚y l‡ tÏm gi· trị λ thÌch hợp. Để x·c định gi· trị của λ , ch ̇ng tÙi d ̆ng cÙng thức l‡ biến thể của cÙng thức đề xuất bởi Witten and Bell [10]: λ=f/(Hs*u+f) với Hs l‡ gi· trị trọng số nhằm thay đổi ảnh hưởng của u trong cÙng thức tÌnh. Trong ph‚n tÌch c ̇ ph·p tiếng Anh d ̆ng Wall Street Journal của Penn Treebank, hệ s ố n‡y nhận gi· trị trong khoảng 2Æ5. Ch ̇ng tÙi chọn gi· trị Hs = 4. Để hiểu ̋ nghĩa của λ , ch ̇ng tÙi xin lấy một vÌ dụ sau. Giả sử cần tÏm P(A|BC). CÙng thức ước lượng x·c suất d ̆ng phương ph·p l‡m trơn nội suy tuyến tÌnh l‡ ^P(A|BC)= λ *P(A|BC)+(1- λ)P(A|B). Khi đÛ f = số lần suất hiện của c·c bộ 3 XBC thống kÍ được trong tập mẫu với mọi X. u= số lần xuất hiện bộ ba XBC ph‚n biệt trong tập mẫu. Nếu ta thống kÍ được f=10, u=1 v‡ giả sử chọn Hs=1. Khi đÛ ta cÛ λ = 10/(110+1)=10/11. ^P(A|BC)= 10/11 P(A|BC)+1/11P(A|B).

5. Thuật to·n ph‚n tÌch c ̇ ph·p Sau bước t·ch từ ta cÛ c·c cụm ‚m tiết kh·c nhau, trong đÛ mỗi cụm cÛ thể cÛ hơn một nh„n từ loại. VÌ dụ c‚u ìHọc sinh học sinh họcî sau khi thực hiện bước t·ch từ ta cÛ c·c từ v‡ nh„n từ loại tương ứng được biểu diễn trong đồ thị ở HÏnh 4.

học (0,1) (ĐT)

Học sinh (0,2) (DT)

sinh (1,2) (ĐT_N) sinh (3,4) (ĐT_N)

học (2,3) (ĐT)

Sinh học (1,3) (DT)

Học sinh (2,4) (DT) Sinh học (3,5) (DT)

học (4,5) (ĐT)

Start Stop

sinh (1,2) (DT) sinh (3,4) (DT)

HÏnh 4 - Từ v‡ từ loại sau khi thực hiện bước t·ch từ với c‚u ì Học sinh học sinh học î

Trong qu· trÏnh ph‚n tÌch c ̇ ph·p, c‚u được biểu diễn th‡nh c·c trung t‚m với trung t‚m nhỏ nhất l‡ từ cÛ được sau bước t·ch từ. Mỗi trung t‚m lưu c·c thÙng tin về vị trÌ của cụm từ, nh„n từ loại/ngữ loại tương ứng v‡ nh„n ngữ loại m‡ nh„n cụm từ cÛ thể ph·t triển lÍn. VÌ dụ, từ ì học î đầu tiÍn trong c‚u ì Học sinh học sinh học î được biểu diễn th‡nh c·c trung t‚m sau l‡ ((0,1), động từ, động từ) → ((0,1), động từ, động ngữ) → ((0,1), động từ, c‚u). Ch ̇ng tÙi sử dụng thuật to·n ph‚n tÌch c ̇ ph·p theo kiểu tÏm kiếm s‚u v‡ duyệt theo trÏnh tự tr·i-phải dưới-lÍn. Thuật to·n được mÙ tả như sau:

Duyệt lần lượt qua c·c trung t‚m (tr·i sang phải). Tại mỗi trung t‚m: I. Duyệt qua c·c điểm l‡m việc từ tr·i qua phải, tÏm xem cÛ th‡nh phần n‡o kết hợp được với nÛ khÙng. Nếu cÛ th‡nh phần như vậy: 1. Trường hợp trung t‚m PH tÏm được bổ sung cho trung t‚m đang xÈt TT a) Kết hợp hai trung t‚m PH v‡o TT, đ·nh dấu kết th ̇c cho c·c điểm l‡m việc đÛ v‡ c·c điểm cấp trÍn. (vÌ dụ TT l‡ Động ngữ, PH l‡ Phụ tố khẳng định/phủ định, sau khi kết hợp, đ·nh thÍm dấu kết th ̇c cho Trung t‚m TT-Động ngữ, v‡ Trung t‚m cấp trÍn l‡ TTí-C‚u ph·t triển từ TT-Động ngữ v‡ cấp trÍn của TTí-C‚u đÛ) b) Nhảy tới c·c điểm l‡m việc mới vừa tạo ra.(TT l‡m trung t‚m, Điểm phụ PH, v‡ TTí(cấp trÍn của TT)l‡m trung t‚m, điểm phụ l‡ điểm vừa bị ảnh hưởng do PH kết nạp v‡o TT). c) Gọi đệ quy thủ tục (Quay lại bước I, với mỗi điểm l‡m việc mới). 2. Trường hợp trung t‚m đang xÈt TT l‡ bổ sung cho trung t‚m mới PH (vÌ dụ TT l‡ Phụ tố khẳng định/phủ định, v‡ Trung t‚m PH l‡ Động ngữ) a) Kết hợp trung t‚m TT v‡o PH, đ·nh dấu kết th ̇c cho c·c cho điểm l‡m việc đÛ v‡ c·c điểm cấp trÍn. b) Nhảy tới vị trÌ mới vừa tạo ra. c) Gọi đệ quy thủ tục (Quay lại bước I). II. Nhảy sang trung t‚m chưa duyệt.

Kh·c với thuật to·n CYK truyền thống, thuật to·n n‡y luÙn quan t‚m đến từ chÌnh trong cụm từ. VÏ vậy, trong qu· trÏnh ph‚n tÌch c ̇ ph·p c‚u đầu v‡o, khi cần tÏm mối quan hệ giữa 2 trung t‚m Y v‡ Z (Z đứng liền sau Y), bộ ph‚n tÌch c ̇ ph·p sẽ xÈt hai trường hợp: (i) Y l‡ th‡nh phần trung t‚m; (ii) Z l‡ th‡nh phần trung t‚m. VÌ dụ, cụm từ ì anh ấy î gồm Danh từ( anh ), Danh ngữ( anh ) v‡ Đại từ chỉ định( ấy ). Để x·c định ngữ loại của ì anh ấy î, thuật to·n xÈt trường hợp:

1. Danh ngữ(Danh từ, anh ) l‡m th‡nh phần trung t‚m; Đại từ chỉ định(Đại từ chỉ định, ấy ) l‡m th‡nh phần phụ. Trường hợp n‡y cÛ thể kết hợp được.
2. Danh ngữ(Danh từ, anh ) l‡m th‡nh phần phụ; Đại từ chỉ định(Đại từ chỉ định, ấy ) l‡m th‡nh phần trung t‚m. Trường hợp n‡y khÙng kết hợp được.
3. Danh từ(Danh từ, anh ) l‡m th‡nh phần trung t‚m; Đại từ chỉ định(Đại từ chỉ định, ấy ) l‡m th‡nh phần phụ. Trường hợp n‡y khÙng kết hợp được.
4. Danh từ(Danh từ, anh ) l‡m th‡nh phần phụ; Đại từ chỉ định(Đại từ chỉ định, ấy ) l‡m th‡nh phần trung t‚m. Trường hợp n‡y khÙng kết hợp được.

6. Một số kết quả thử nghiệm

Ch ̇ng tÙi đ„ c‡i đặt một phiÍn bản thử nghiệm cho cÙng cụ ph‚n tÌch c ̇ ph·p tiếng Việt đề xuất sử dụng ngÙn ngữ lập trÏnh Java. Trong hệ thống n‡y, c·c c‚y c ̇ ph·p được xếp hạng theo gi· trị x·c suất của c‚y đÛ. Do hiện nay ch ̇ng ta chưa cÛ một tập ngữ liệu chuẩn c·c c‚u tiếng Việt cÛ ch ̇ giải ngữ ph·p, đặc biệt l‡ c·c c‚u được ch ̇ giải theo c·ch thức của LPCFG, nÍn ch ̇ng tÙi đ„ x‚y dựng theo c·ch thủ cÙng tập ngữ liệu mẫu sử d ụng trong

lẫn giữa danh ngữ v‡ c‚u. Để giải quyết vấn đề n‡y cần bổ sung c·c vÌ dụ mẫu v‡o tập ngữ liệu liÍn quan đến danh từ ì nguyÍn tắc î. TrÍn cơ sở đÛ, hệ thống cÛ thể tÌnh được x·c suất kết hợp giữa danh từ ì nguyÍn tắc î với c·c từ/loại từ kh·c. Khi đÛ, x·c suất kết hợp ì nguyÍn tắcî v‡ ì hoạt động î l‡ c‚u sẽ nhỏ hơn l‡ danh ngữ.

7. Kết luận

Trong b‡i n‡y, ch ̇ng tÙi đề xuất một mÙ hÏnh ph‚n tÌch c ̇ ph·p sử d ụng văn phạm LPCFG. MÙ hÏnh n‡y cho phÈp xử l ̋ nhập nhằng v‡ xử l ̋ c·c trường hợp ngữ ph·p phụ thuộc từ m‡ c·c văn phạm CFG v‡ PCFG khÙng giải quyết được. Thuật to·n ph‚n tÌch c ̇ ph·p sử d ụng trong hệ thống kh· linh động so với d ̆ng thuật to·n ph‚n tÌch c ̇ ph·p CYK truyền thống. Trong thời gian tới, ch ̇ng tÙi sẽ tiếp tục cải tiến chất lượng của bộ ph‚n tÌch c ̇ ph·p bằng c·ch nghiÍn cứu c·ch x·c định c·c trung t‚m bắt đầu v‡ c·c quy tắc di chuyển giữa c·c trung t‚m, nghiÍn cứu phương ph·p tự động thay đổi gi· trị λ để điều chỉnh ảnh hưởng của từ v‡ từ loại/ngữ loại trong tập luật c ̇ ph·p. Ch ̇ng tÙi sẽ cho hệ thống học trÍn tập ngữ liệu cÛ ch ̇ giải c ̇ ph·p đầy đủ hơn v‡ đ·nh gi· độ chÌnh x·c của hệ thống trÍn tập ngữ liệu lớn.

T‡i liệu tham khảo

1. Eugene Charniak. 1997. Statistical parsing with a context-free grammar and word statistics. Proceedings of the Fourteenth National Conference on Artificial Intelligence, AAAI Press/MIT Press, Menlo Park.
2. Nguyễn T‡i Cẩn. 1999. Ngữ ph·p tiếng Việt. NXB Đại Học Quốc Gia H‡ Nội.
3. Nguyễn T‡i Cẩn. 1975. Từ loại danh từ trong tiếng Việt hiện đại. NXB Khoa học x„ hội H‡ Nội.
4. Stanley F and Joshua Goodsman. 1998. Empirical Study of Smoothing Technique for Language Modeling. Center for Research in Computing Technology Harvard University Cambrigde, Massachusetts.
5. Micheal Collins. 2003. Head-Driven Statisticcal Models for Natural Language Parsing. MIT Artificial Intelligence Laboratory.
6. Jason Eisner and Giorgio Satta. 1999. Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars. In Proceedings of the 37th Annual Meeting of the ACL.
7. Ho‡ng Vĩnh Sơn, ìPh‚n tÌch c ̇ ph·p tiếng Việtî, Đồ ·n tốt nghiệp đại học. Trường ĐHBK H‡ Nội ñ 2005.
8. LÍ Thanh Hương, Phạm Hồng Quang, Nguyễn Thanh Thuỷ. 2000. Một c·ch tiếp cận trong việc tự động ph‚n tÌch c ̇ ph·p văn bản tiếng Việt. B·o Tin học v‡ Điều khiển học, 15(4).
9. Vũ Lục. 1990. Ph‚n tÌch c ̇ ph·p. Trường Đại học B·ch khoa H‡ Nội.

Ian Witten and Timothy C. Bell. 1991. The Zero-Frequency Problem: Estimating the Probabilities of Novel Events in Adaptive Text Compression. IEEE Transactions on Information Theory, 37(4): pp ñ 1094.