Mô hình văn phạm liên kết tiếng Việt - 20
Luận án chưa thử nghiệm trên câu phức là dạng câu có từ hai cụm chủ vị trở lên nhưng có một cụm bao các cụm còn lại, ví dụ “cái áo hôm qua cậu mua rất đẹp” có hai cụm chủ vị “cậu mua” “cái áo đẹp” , cụm “cái áo đẹp” bao cụm còn lại. Thật ra, một số trường hợp đã có thể phân tích với bộ phân tích câu ghép của chúng tôi, như câu “Nó bảo rằng nó không đi nữa”.Tuy nhiên một số trường hợp cần dùng phương pháp học máy để nhận ra giới hạn mệnh đề.
3.2.5. Độ phức tạp tính toán
Theo Sleator [111], chi phí thời gian của giải thuật phân tích liên kết (khi chưa lược tỉa) là với một văn phạm xác định là O(n3 ) với n là độ dài câu (số từ trong câu), chi phí này cũng tương đương với chi phí thời gian của các giải thuật phân tích sử dụng văn phạm phi ngữ cảnh. Khi phân tích cú pháp ngôn ngữ tự nhiên, n không lớn nên phần lớn chi phí thời gian là do việc tìm kiếm các luật phù hợp trong văn phạm. Nếu xét cả kích thước văn phạm thì giải thuật phân tích liên kết có chi phí O(n3m), m là số dạng tuyển trung bình của các từ trong câu. Trong khi đó, độ phức tạp của các giải thuật CYK và Earley cho văn phạm phi ngữ cảnh theo Jurafsky [70] là O(n3 |G|), |G| là số sản xuất của văn phạm phi ngữ cảnh.
Chi phí thời gian chủ yếu chính là do giai đoạn lược tỉa. Trong tiếng Việt, do từ không biến đổi hình thái nên mỗi từ phải có nhiều mối liên hệ với các từ chỉ thì, thể, số…, Số lượng dạng tuyển trung bình (chưa lược tỉa) của mỗi từ khoảng 10.000. Từ [111] có thể thấy giải thuật lược tỉa có chi phí O(nm).
Nếu quá trình phân đoạn diễn ngôn chia câu thành k mệnh đề, độ dài trung bình mỗi mệnh đề còn n/k, chi phí thời gian trung bình sẽ giảm k2 lần. Chi phí phân đoạn diễn ngôn là O(n), chi phí duyệt cây diễn ngôn là cây nhị phân gồm k/2 nút lá (không duyệt nút lá) ứng với k mệnh đề không quá O(k).Như vậy k càng lớn, chi phí thời gian sẽ càng nhỏ. Tuy nhiên nếu k bằng 1 thì chi phí sẽ lớn hơn chi phí phân tích câu đơn.
Thực nghiệm với tập câu mẫu thứ nhất ở bảng 3.5, cho thấy thời gian để phân tích tập mẫu theo kiểu liên kết liên từ là 296.153 mili giây, trong khi thời gian phân tích câu đó bằng cách phân tích riêng từng mệnh đề là 217.324 mili giây, giảm đáng kể so với phân tích kiểu liên kết liên từ.
3.3.Khử nhập nhằng
Như đã trình bày ở chương 2, Jurafsky [70] nêu ra hai vấn đề chủ yếu trong nhập nhằng cú pháp: nhập nhằng thành phần và nhập nhằng liên hợp. Nhập nhằng thành phần (attachment ambiguation) xảy ra khi một cấu trúc có thể tham gia các bộ phận khác nhau trên cây phân tích, tạo ra những phân tích khác nhau. Nhập nhằng liên hợp (cordination ambiguation) xảy ra khi gặp những cụm từ liên kết với nhau bằng liên từ liên hợp “và”, “hoặc”, “hay”…Nhập nhằng địa phương (local ambiguation) cũng được tính đến khi một từ có thể nhận các nhãn từ loại khác nhau. Vấn đề nhập nhằng địa phương của mô hình liên kết một phần đã được giải quyết trong quá trình phân tích cú pháp. Khác với các mô hình khác, từ không được gán nhãn trước khi phân tích cú pháp mà được gán nhãn dựa trên liên kết mà nó tham gia. Một từ có nhiều nghĩa sẽ xuất hiện trong những công thức khác nhau, tuy nhiên chỉ những tổ hợp các từ và nhãn thỏa các yêu cầu liên kết mới được chấp nhận. Do vậy số lượng phân tích liên kết của mỗi câu nhỏ hơn đáng kể so với số lượng cây cú pháp của mô hình phi ngữ cảnh.
Trong phần này nói đến việc giải quyêt vấn đề nhập nhằng thành phần và nhập nhằng liên hợp. Đối với nhập nhằng thành phần, luận án đã chọn cách tiếp cận của Lafferty và đồng nghiệp [79] với mô tả chung về một mô hình xác suất trigram. Từ mô tả này, luận án phải xây dựng giải thuật khử nhập nhằng cho ứng dụng của mình.
Có thể bạn quan tâm!
-
Mô hình văn phạm liên kết tiếng Việt - 17
-
Mô hình văn phạm liên kết tiếng Việt - 18
-
Mô hình văn phạm liên kết tiếng Việt - 19
-
Mô hình văn phạm liên kết tiếng Việt - 21
-
Mô hình văn phạm liên kết tiếng Việt - 22
-
Mô hình văn phạm liên kết tiếng Việt - 23
Xem toàn bộ 305 trang: Mô hình văn phạm liên kết tiếng Việt
3.3.1. Khử nhập nhằng thành phần
Vấn đề nhập nhằng thành phần xảy ra khi một câu có nhiều hơn một phân tích liên kết. Câu đươc xét ở đây là câu đơn. Nếu là câu ghép, sau khi phân tách thành mệnh đề, mới giải quyết vấn đề nhập nhằng.
Theo mô hình trigram [79], việc khử nhập nhằng không phải là tính xác suất của mỗi phân tích, tìm ra câu có xác suất lớn nhất, mà là sử dụng mô hình Markov ẩn (HMM) dự đoán câu có xác suất lớn nhất. Hai vấn đề chính cần giải quyết phục vụ mục đích này là:
- Tìm câu có xác suất lớn nhất theo giải thuật kiểu Viterbi.
- Cập nhật lại xác suất của các sản xuất.
3.3.1.1. Giải thuật kiểu Viterbi để tìm phân tích tốt nhất
Trong [79] đã giới thiệu mô hình xác suất cho văn phạm liên kết tương tự như mô hình đã được mô tả ở mục 1.1.2. cho văn phạm phi ngữ cảnh. Nếu trong văn phạm phi ngữ cảnh, thao tác cơ bản là viết lại thì trong văn phạm liên kết, thao tác cơ bản lại là tìm liên kết. Đối tượng tương đương với sản xuất của văn phạm phi ngữ cảnh trong văn phạm liên kết là liên kết. Mỗi liên kết phụ thuộc vào hai kết nối: kết nối phải và kết nối trái cùng tên nối hai từ L và R . Như vậy tham số của văn phạm liên kết là:
Pr ( W, d, O | L, R, l, r ) (3.1)
O có thể nhận các giá trị →, ←, ↔ thể hiện hướng liên kết. Có thể hiểu là: cho từ L có kết nối phải là l và từ R có kết nối trái r, tham số là xác suất của sự kiện: tồn tại từ W nằm giữa L và R, dạng tuyển d của W liên kết được với L hoặc R hoặc cả hai. Xác suất (3.1) phân rã thành:
Pr ( W, d, O | L, R, l, r ) =
Pr (W | L, R, l, r ) × Pr ( d | W, L, R, l, r ) × Pr ( O | d, t, p, q, l, r ) (3.2)
Vì ta đang xét đến các xác suất điều kiện trên một tập sự kiện quá lớn cho một văn phạm với từ vựng của ngôn ngữ tự nhiên, trên thực tế không thể ước lượng được xác suất này. Do vậy nó cần được xấp xỉ bằng công thức [79]:
Pr ( W, d, O | L, R, l, r ) ≈ Pr (W | L, R, l, r ) × Pr (d | W, l, r ) × Pr (O | d, l, r ) (3.3)
Xác suất của một phân tích liên kết (linkage) là tích của xác suất của mọi liên kết trong nó. Bây giờ cần biểu diễn phân tích liên kết L bởi một tập các liên kết L = {(W, d, O, L, R, l, r)} cùng với dạng tuyển đầu tiên d0. Xác suất của L là:
Pr ( S, L ) = Pr ( W0, d0 ) ∏ Pr ( W, d, O | L, R, l, r )
Ví dụ: Một văn phạm liên kết xác suất có lưu trữ các tham số sau (Từ thứ n là từ “giả” Wn được dùng trong phân tích theo giải thuật trong hình 3.4):
Pr ( tôi, ( ) ( SV ) ) = 0.7
Pr ( mua, (SV)(O), ← | tôi, Wn , SV, NIL) = 0.06
Pr ( hoa, ( O, NcNt3 )( ), ← | mua, Wn , O, NIL) = 0.03
Pr ( bông, (McN)(NcNt3), → | mua, hoa, NIL, NcNt3) = 0.05
Pr ( một, ( )(McN), → | mua, bông, NIL, McN) = 0.06
Pr ( bông, (O, McN)(NcNt3), ↔ | mua, Wn , O, NIL) = 0.00001
Pr ( hoa, (NcNt3)( ) ← | bông, Wn, NcNt3, NIL) = 0.07 (3.4)
Giả sử câu “Tôi mua một bông hoa” có hai phân tích L1 và L2 như trong hình 3.20 dưới đây:
Hình 3.20. Hai phân tích của câu “Tôi mua một bông hoa”
Xác suất cho phân tích L1 (hình 3.20 (A)) là:
Pr (L1) = Pr ( 0, ( )( SV ) ) × Pr ( 1, (SV)(O), ← | 0, 5 , SV, NIL ) ×
Pr ( 4, ( O, NcNt3 )( ), ← | 1, n, O, NIL ) ×
Pr ( 3, (McN)(NcNt3), → | 1, 4, NIL, NcNt3 ) ×
Pr ( 2, ( )(McN), → | 1, 3, NIL, McN )
= 0.7 * 0.06 * 0.03 * 0.05 * 0.06
= 3.78E-5
Trong khi xác suất của phân tích L2 (hình 3.20. (B)) là:
Pr (L2) = Pr ( 0, ( )( SV ) ) × Pr ( 1, (SV)(O), ← | 0, 5 , SV, NIL ) ×
Pr ( bông, (O, McN)(NcNt3), ↔ | mua, Wn , O, NIL ) ×
Pr ( một, ( )(McN), → | mua, bông, NIL, McN ) ×
Pr ( hoa, (NcNt3)( ) ← | bông, Wn, NcNt3, NIL )
= 0.7 × 0.06 × 0.00001 × 0.06 × 0,7
= 2E-8
Nếu phải chọn một trong hai phân tích thì L1 sẽ được chọn.
Trong [79] chỉ đưa ra mô hình xác suất cho văn phạm liên kết với xác suất trong và xác suất ngoài tương tự xác suất tiến và xác suất lùi trong mô hình HMM. Luận án đã đề xuất giải thuật kiểu Viterbi cho mô hình văn phạm liên kết.
Hình 3.21. Giải thuật kiểu Viterbi để dự đoán phân tích có xác suất cao nhất

Bài viết tương tự
- Kinh doanh các dịch vụ liên quan đến rác thải mô hình tại Nhật Bản và bài học kinh nghiệm đối với Việt Nam
- Phân tách cụm danh từ cơ sở tiếng việt sử dụng mô hình crfs
- Nghiên cứu xây dựng mô hình nữ vận động viên chạy 100m cấp cao Việt Nam
- Mô hình tố tụng hình sự Việt Nam và vấn đề áp dụng tố tụng tranh tụng
- Tình hình song ngữ khmer-việt tại đồng bằng sông cửu long – một số vấn đề lý thuyết và thực tiễn
Gửi tin nhắn
Danh mục
Bài viết tương tự
-
Luận cứ khoa học về xác định mô hình quản lý rủi ro tín dụng tại hệ thống ngân hàng thương mại Việt Nam
-
KHẢO SÁT NHANH CÁC LOẠI HÌNH CHỨNG KHOÁN PHÁI SINH VÀ SẢN PHẨM GIAO DỊCH MỚI TRÊN THỊ TRƯỜNG CHỨNG KHOÁN VIỆT NAM
-
Ảnh hưởng của văn hoá phương Đông đến hành vi tiêu dùng hàng thực phẩm của người Việt Nam
-
Dịch vụ phân phối và những vấn đề đặt ra trong việc thực hiện cam kết của Việt Nam khi gia nhập WTO
-
Mô hình chiến lược" Đại dương xanh" và thực tế áp dụng đối với các doanh nghiệp Việt Nam
-
Kinh nghiệm phát triển mô hình Keiretsu ở Nhật Bản, Chaebol ở Hàn Quốc và định hướng cho các tập đoàn kinh tế của Việt Nam
-
Mô hình bán lẻ chuyên biệt và triển vọng phát triển tại Việt Nam
-
Mô hình cửa hàng tiện lợi tại Việt Nam: Thực trạng và giải pháp
-
Mô hình kinh doanh Báo mạng tại Việt Nam: thực trạng và giải pháp
-
Mô hình quản lý kinh doanh rác thải phù hợp cho Việt Nam
-
Mô hình tập đoàn kinh tế - hoạt động của tập đoàn dầu khí Việt Nam giai đoạn 2006 - 2008 và xu hướng phát triển
-
Mô hình tập đoàn kinh tế Việt Nam - Hiện trạng và xu hướng phát triển trong thời gian tới
-
Mô hình và hoạt động của các công ty chứng khoán trên thị trường chứng khoán Việt Nam hiện nay
-
Nghiên cứu mô hình đấu giá trực tuyến của EBAY và những đề xuất cho Việt Nam
-
Nghiên cứu mô hình tập đoàn ở một số nước Đông Nam Á và bài học cho Việt Nam
-
Nghiên cứu mô hình xúc tiến và hỗ trợ thương mại điện tử cho doanh nghiệp - Kinh nghiệm trên thế giới và bài học đối với Việt Nam
-
Phân tích mô hình quản trị chuỗi cung ứng của Toyta và bài học kinh nghiệm cho các doanh nghiệp sản xuất ô tô của Việt Nam
-
Mô hình chủ sở hữu nhà nước tại doanh nghiệp có vốn nhà nước ở Việt Nam
-
Một số vấn đề cơ bản để giảm và tiến tới xóa bỏ hình phạt tử hình trong Luật hình sự Việt Nam
-
Tội tàng trữ, vận chuyển, mua bán trái phép chất ma túy trong luật hình sự Việt Nam
-
Các tình tiết tăng nặng trách nhiệm hình sự thuộc về nhân thân người phạm tội trong luật hình sự Việt Nam (trên cơ sở thực tiễn tại địa bàn tỉnh Hà Giang)
-
Văn hóa gia đình tại các khu đô thị mới ở Hà Nội với việc tiếp nhận truyền hình đa nền tảng ở Việt Nam
-
Nghiên cứu đặc điểm lâm sàng, giải phẫu bệnh và kết quả điều trị ung thư ống tiêu hóa không thuộc biểu mô tại bệnh viện Việt Đức
Tin nhắn