Khóa luận Xây dựng chương trình chuyển đổi cây cú pháp trong hệ dịch tự động Anh - Việt

mặt tốc độ. Phần 3.3 là mô hình áp dụng, mô hình học chuyển đổi cây cú pháp do chúng em tự xây dựng dựa trên thuật toán học FnTBL áp dụng cho việc chuyển đổi cây cú pháp. Các thuật toán liên quan cũng được trình bày trong phần này. Phần cuối cùng (3.4) là một số kỹ thuật nhằm nâng cao tính mở rộng của chương trình. 3.1 Phương pháp học hướng lỗi dựa trên sự chuyển trạng thái (TBL) Phương pháp học dựa trên sự chuyển trạng thái được Eric Brill đưa ra trong luận án tiến sĩ của ông năm 1993 [8]. Từ đó đến nay TBL đã chứng tỏ được sức mạnh của nó trong nhiều bài toán liên quan đến học từ ngữ liệu, đặc biệt là những bài toán liên quan đến xử lý ngôn ngữ. Từ ý tưởng ban đầu của Eric Brill và thuật toán TBL gốc, nhiều thuật toán cải tiến đã ra đời với những ưu điểm về mặt thời gian huấn luyện (tốc độ), bộ nhớ, và dạng luật như µ TBL, mTBL, k-bestTBL,… Và gần đây là thuật toán TBL nhanh fnTBL. 3.1.1 Ý tưởng Chỉ cần cung cấp cho hệ thống học một ngữ liệu đã được gán nhãn chính xác và dạng luật. Hệ thống sẽ bỏ các nhãn chính xác đi, gán cho ngữ liệu bộ nhãn thô, sau đó tự động rút ra các luật chuyển đổi nhãn dần dần để ngữ liệu biến đổi đến Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 67 trạng thái có nhãn đúng như ban đầu. Các luật chi tiết hơn sẽ sửa sai cho những luật tổng quát hơn gây ra. Trong bài giảng về TBL, Samuel đã ví quá trình này cũng giống như tô màu một bức hình theo mẫu [10]. Chẳng hạn như ta có hình mẫu cần tô như sau : Quá trình tô diễn ra theo thứ tự: 1. Giấy vẽ trắng 2. Tô nền màu xám bằng cọ lớn 3. Dùng cọ vừa tô màu xanh lên toàn bộ phần nón 4. Tô màu vàng lên phần nơ 5. Tô các chấm màu đỏ bằng cọ nhỏ 6. Dùng cọ thật nhỏ để tô phần nền màu xám ở phần kẽ nơ Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 68 3.1.2 Thuật toán học TBL của Eric Brill Phần này sẽ giới thiệu tổng quan về phương pháp học hướng lỗi dựa trên sự chuyển trạng thái TBL. Trước hết để giải một bài toán bằng phương pháp này, chúng ta cần quy bài toán về dạng bài toán gán nhãn. Ý tưởng của cách tiếp cận là: học từ ngữ liệu một bộ luật có thứ tự. Một luật khi áp dụng lên một thực thể sẽ làm thay đổi nhãn của nó làm cho thực thể chuyển từ trạng thái cũ sang trạng thái mới. Và sau khi áp dụng toàn bộ các luật trong bộ luật lên một thực thể, thì thực thể đó sẽ có trạng thái gần với trạng thái đúng nhất. Phương pháp học dựa trên sự chuyển trạng thái là một phương pháp học có giám sát. Trước khi đi vào quá trình học của TBL, có một số thuật ngữ mà chúng ta cần hiểu rõ: ™ Đầu vào - Ngữ liệu huấn luyện : Là ngữ liệu chứa các mẫu huấn luyện chưa được gán nhãn. - Ngữ liệu vàng : Là ngữ liệu bao gồm các mẫu huấn luyện đã được gán nhãn đúng. Ngữ liệu vàng do người tạo ra theo cách thủ công hoàn toàn hoặc bán tự động, phải chính xác và đủ lớn. Có thể nói ngữ liệu huấn luyện chính là ngữ liệu vàng đã được gỡ bỏ nhãn. - Các khung luật chuyển đổi: thể hiện tất cả các dạng chuyển đổi trạng thái nhãn có thể có. Khung luật là sự tổng quát hoá các luật. Mỗi khung luật có 2 phần. Phần đầu là các vị từ có ý nghĩa do ta qui định, phần sau là hành động thay đổi nhãn (trạng thái). Vị từ chứa các biến, chúng có giá trị sẽ được xác định trong quá trình học. Ví dụ : Khung luật Nếu nhãn trước là Z thì chuyển đổi nhãn từ X thành Y. • X, Y, Z là các biến • Nhãn trước là Z là một vị từ chứa biến Z • Chuyển đổi nhãn từ X thành Y là hành động thay đổi trạng thái Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 69 Khi tất cả các biến trong khung luật đã nhận giá trị thực thì ta có một luật cụ thể. Số lượng khung luật thường nhỏ. Tuy nhiên, phải đảm bảo có khung luật “rộng” (ít điều kiện), có khung luật “hẹp” (điều kiện áp dụng chặt hơn) để có thể rút ra được các luật có độ mịn khác nhau, luật “rộng” có thể sửa được nhiều lỗi và luật “hẹp” có thể sửa các lỗi gây ra bởi việc áp dụng luật “rộng”. ™ Đầu ra - Danh sách luật có thứ tự Quá trình học diễn ra như sau : - Bước 0: Ngữ liệu chưa gán nhãn được đưa vào hệ thống. - Bước 1: Hệ thống sử dụng tri thức về trạng thái khởi đầu đã có sẵn để gán nhãn cho ngữ liệu luyện. Trạng thái ban đầu này có thể rất đơn giản, chẳng hạn như gán nhãn ngẫu nhiên, nhưng cũng có thể rất kỳ công như được con người gán nhãn bằng tay. - Bước 2: Ngữ liệu huấn luyện sẽ được so sánh nhãn với ngữ liệu vàng. Từ những sai khác giữa ngữ liệu huấn luyện và ngữ liệu vàng mà ta có thể gọi là lỗi, hệ thống sẽ tự động rút ra luật sửa lỗi có dạng thức theo các khung luật đã được cung cấp. Đồng thời, tính điểm cho các luật được rút ra. Điểm luật = số lỗi của ngữ liệu hiện hành được sửa bởi luật - số lỗi gây ra bởi áp dụng luật lên trạng thái ngữ liệu hiện hành. - Bước 3: Chọn luật có điểm cao nhất và so sánh điểm với ngưỡng. o Nếu (điểm cao nhất > ngưỡng) thì thực hiện bước 4. o Ngược lại, (điểm cao nhất <= ngưỡng), dừng quá trình học. - Bước 4: Đưa luật có điểm cao nhất vào tập luật. Áp dụng luật vừa chọn được lên ngữ liệu huấn luyện. Lặp lại bước 2. Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 70 Hình 16: Sơ đồ phương pháp học TBL tổng quát 3.1.3 Nhận xét 3.1.3.1 Ưu điểm ™ Bộ học dựa trên sự chuyển trạng thái có tính dễ mở rộng cao. Chúng ta có thể thêm khung luật chuyển đổi nếu nhận thấy bộ học cần rút ra luật theo một dạng luật mới. Nếu một khung luật không hữu dụng thì không có luật nào được rút ra theo khung luật đó, vì thế khung luật thừa cũng không làm chất lượng học bị giảm mà chỉ có thể làm tăng thời gian học. ™ Bộ học dựa trên sự chuyển trạng thái có thể được sử dụng như một bộ phận hậu xử lý cho kết quả gán nhãn bởi con người hoặc một bộ gán nhãn tự động khác. Điều này được thực hiện rất đơn giản bằng cách sử dụng kết quả gán nhãn từ nguồn khác làm kết quả của bộ gán nhãn cơ sở. Thay vì sử dụng một cách gán nhãn cơ sở đơn giản, ta có thể sử dụng một cách gán nhãn phức tạp hơn và nhiệm vụ của bộ học lúc này chỉ là rút ra những luật sửa sai làm hoàn chỉnh thêm kết xuất. Ngữ liệu được gán nhãn Bộ gán nhãn cơ sở Bộ học (rút luật, đánh giá và chọn luật) Bộ luật Ngữ liệu vàng Các khung luật Ngữ liệu huấn luyện chưa có nhãn Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 71 ™ Tri thức ngôn ngữ và tri thức riêng của ngữ liệu không được lập trình “cứng” trong mã nguồn, do đó bộ học có tính uyển chuyển cao. Tri thức được học ra dưới dạng luật theo khung luật dưới dạng ký hiệu, do đó rất dễ hiểu đối với các chuyên gia về ngôn ngữ. ™ Một khi có danh sách luật chuyển đổi, khi áp dụng lên một thực thể mới, những việc cần làm chỉ đơn giản là đưa thực thể đó qua bộ gán nhãn cơ sở rồi áp dụng từng luật theo thứ tự lên thực thể đó. Ở bước áp dụng, không có sự lựa chọn luật, thời gian gán nhãn dựa trên sự chuyển trạng thái tỉ lệ tuyến tính với chiều dài của thực thể đầu vào. 3.1.3.2 Nhược điểm ™ Thời gian huấn luyện khá lâu đối với khối lượng ngữ liệu lớn ™ Các luật rút ra có thể là luật tối ưu cục bộ, do đó có thể làm giảm kết quả thực thi tổng thể. Tuy nhiên những luật như thế không nhiều, rất dễ phát hiện và được loại bỏ khỏi tập luật. 3.2 Thuật toán học nhanh FnTBL Mặc dù TBL là thuật toán học rất hiệu quả trong các ứng dụng về xử lý ngôn ngữ, nhưng đặc điểm chung của các ứng dụng này là khối lượng ngữ liệu học rất lớn. Nếu dùng thuật toán TBL chuẩn như trình bày ở phần trên thì thời gian huấn luyện rất lâu. Chẳng hạn như một bộ đánh nhãn từ loại sử dụng phương pháp chuyển trạng thái được cài đặt rất tốt cũng cần tiêu tốn hơn 38 giờ để hoàn tất việc huấn luyện trên ngữ liệu có 1 triệu từ. Để khắc phục hạn chế về mặt tốc độ đó, dựa trên thuật toán TBL chuẩn, Radu Florian và Grace Ngai đã xây dựng thuật toán học FnTBL dựa trên ý tưởng về miền lân cận. Để hiểu thuật toán FnTBL một cách rõ ràng hơn, chúng em trình bày tóm tắt TBL dưới dạng hình thức hoá và sử dụng dạng hình thức hoá này cho FnTBL. Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 72 3.2.1 Hình thức hóa TBL Có thể thấy ý tưởng chính của phương pháp học dựa trên sự chuyển trạng thái là học ra được một danh sách luật có thứ tự. Tập luật này có khả năng cải tiến dần dần trạng thái hiện tại của tập huấn luyện. Trạng thái khởi đầu dựa trên những thống kê đơn giản, sau đó các luật được học theo cách thức “tham lam” để sửa những lỗi sai. Các luật dần được rút ra cho đến khi không thể cải thiện thêm được nữa. Một số ký hiệu : ™ S : Không gian mẫu ™ C : Tập hợp các nhãn có thể có của các mẫu ™ C[s] : Nhãn của mẫu s ™ T[s] : Nhãn đúng của s ™ p : Vị từ được định nghĩa trên S ™ r : luật gồm có một cặp(cắp) vị từ - nhãn lớp (p,t), trong đó Ct∈ là đích của luật r ™ R : tập hợp tất cả các luật ™ Nếu r=(p,t) , pr biểu diễn cho thành phần p và tr biểu diễn cho thành phần t trong luật r. Luật r=(pr,tr) áp dụng được lên mẫu s nếu như ps(s) = true và [ ]sCtr ≠ Như đã trình bày trong phần 1, để sử dụng phương pháp học này, cần có: ™ Bộ gán nhãn cơ sở ™ Các khung luật có thể có ™ Hàm lượng giá f cho việc học. Khác những thuật toán học khác, hàm lượng giá cho TBL sẽ trực tiếp tối ưu hoá hàm đánh giá. Một ví dụ điển hình của hàm lượng giá là )()()( rbadrgoodrf −= Trong đó [ ] ( )[ ] ( ){ }sTsrCsTsCsrgood =Λ≠= ][/)( [ ] ( )[ ] ( ){ }sTsrCsTsCsrbad ≠Λ== ][/)( Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 73 Những luật cho giá trị hàm lượng giá âm đồng nghĩa với luật đó làm cho ngữ liệu chuyển sang trạng thái sai hơn trước, và đương nhiên sẽ bị loại bỏ. Do đó chúng ta chỉ quan tâm đến những luật có giá trị hàm lượng giá dương. Như vậy, ta có thể thay đổi cách tiếp cận của thuật toán như sau: 1. Sử dụng tập khung luật để tạo ra các luật có khả năng sửa ít nhất một lỗi good(r) > 0, bằng cách xem xét các mẫu sai (Mẫu sai s là mẫu có [ ] [ ]sTsC ≠ ) 2. Tính giá trị bad(.) cho mỗi luật r thoả điều kiện good(r) > f(b), lưu luật b có điểm cao nhất lại, và trong quá trình tính bad(r), ta tiếp tục tính cho luật khác nếu như )()( bfrf < Do đó, hệ thống sẽ học ra một danh sách luật theo kiểm “tham lam”. Khi không còn luật nào có thể cải thiện được trạng thái hiện hành của tập huấn luyện, hoặc khả năng cải thiện quá thấp (điểm nhỏ hơn ngưỡng đặt trước) thì ngừng quá trình học. Trong quá trình áp dụng, tập đánh giá sẽ được gán nhãn cơ sở bằng bộ gán nhãn cơ sở. Sau đó, từng luật trong tập luật được áp dụng theo thứ tự lên tập đánh giá. Khi tất cả luật đã được áp dụng, ta sẽ được trạng thái kết quả. 3.2.2 Thuật toán FnTBL 3.2.2.1 Một số định nghĩa Trong cách tiếp cận này, ở mỗi bước lặp chương trình không phát sinh lại toàn bộ tập luật từ các khung luật và các sai khác giữa ngữ liệu huấn luyện và ngữ liệu vàng. Các luật sẽ được phát sinh một lần và được lưu trong bộ nhớ cùng với hai giá trị good(r), bad(r). 1. Định nghĩa: ( ) [ ] [ ]{ }sTttsCtruespSsrG rrr =≠=∈= andand|)( ( ) [ ] [ ] [ ]{ }sTsCtsCtruespSsrB rr =≠=∈= andand|)( Æ good(r) là số mẫu sau khi áp dụng luật r thì sẽ được chuyển từ trạng thái sai sang trạng thái đúng, khi đó : ( ) ( )rGrgood = Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 74 Æ bad(r) là số mẫu sau khi áp dụng luật r thì sẽ được chuyển từ trạng thái đúng sang trạng thái sai, khi đó : ( ) ( )rBrbad = Ở mỗi bước lặp, giá trị good(d) và bad(r) sẽ được cập nhật lại và chương trình chỉ phát sinh luật mới khi cần thiết. Như vậy, khi áp dụng luật b (luật tốt nhất được chọn) lên tập ngữ liệu S, ta phải xác định được những luật nào làm ảnh hưởng đến hai tập hợp [ ]rG , [ ]rB . Nếu hai tập hợp này đều không bị ảnh hưởng bởi luật b thì số điểm của nó không đổi, ta không cần cập nhật các giá trị good(.), bad(.). Trong các ứng dụng xử lý ngôn ngữ tự nhiên, các mẫu trong tập mẫu thường không hoàn toàn độc lập với nhau. Thay đổi nhãn của mẫu này sẽ làm ảnh hưởng đến việc xác định nhãn của một mẫu lân cận nó. Từ đó, ta có khái niệm về lân cận của một mẫu: 2. Định nghĩa: Lân cận của mẫu s ( )sV là tập hợp các mẫu mà nhãn của mẫu s có thể phụ thuộc vào. Có thể thấy Æ s cũng thuộc lân cận của nó )(sVs∈ Æ Nếu các mẫu trong tập mẫu độc lập nhau thì ( ) { }ssV = 3.2.2.2 Phát sinh luật Gọi s là mẫu mà luật b áp dụng lên ( ( )[ ] ( )sCsbC ≠ ). Ta cần xác định những luật nào bị ảnh hưởng bởi sự thay đổi từ ( )sbs → . Giả sử r là một luật bị ảnh hưởng. ( )rf phải được cập nhật khi và chỉ khi tồn tại ít nhất một mẫu 's sao cho ( ) ( ) ( )rGsbrGs ∉∈ '' vaø hay (1) ( ) ( ) ( )rBsbrBs ∉∈ '' vaø hay (2) ( ) ( ) ( )rGsbrGs ∈∉ '' vaø hay (3) ( ) ( ) ( )rBsbrBs ∈∉ '' vaø (4) Mỗi điều kiện trên tương ứng với một trường hợp cập nhật xác định cho )(rgood hay )(rbad . Cụ thể là )(rgood và )(rbad bị giảm trong trường hợp (1) và (2), )(rgood và )(rbad tăng ứng với hai trường hợp (3) và (4). Trong phần sau, ta Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 75 sẽ xác định điều kiện của một luật thoả trường hợp (1) và (2). Trường hợp (3), (4) tương tự. Ý tưởng cải tiến chính của thuật toán là: khi xem xét ảnh hưởng của việc áp dụng luật b lên mẫu s , ta chỉ cần kiểm tra những mẫu 's thuộc về tập lân cận của s. Có thể bỏ qua những mẫu 's không thuộc về tập { } ( )sVsbs ñoåi thay| ∪ vì ( )'' sbs = . Vì thế, có thể sử dụng công thức này để “phát sinh” luật thỏa ít nhất một trong các công thức từ (1)-(4). Chúng ta sẽ khai triển và khảo sát các công thức trên để được những điều kiện cụ thể hơn mà có thể sử dụng để “phát sinh” luật. Nếu luật được “phát sinh” đã tồn tại rồi thì cần cập nhật các giá trị (.)good , (.)bad . Nếu luật chưa có trong tập luật thì cần tạo và thêm luật đó vào tập luật, đồng thời tính (.)good , (.)bad cho nó. Gọi ( )sVs∈' là một mẫu trong vùng lân cận của mẫu s. Có 2 trường hợp xảy ra: trường hợp b có ảnh hưởng lên 's và trường hợp b không ảnh hưởng lên 's : 1. Trường hợp 1 : [ ] ( )[ ]'' sbCsC = (b không làm thay đổi nhãn của mẫu 's ). Ta có: ( ) ( ) ( ) ( ) [ ] [ ] ( )( ) ( )[ ] ( )[ ]( ) [ ] ( )[ ] [ ] ( )[ ] ( ) [ ] [ ] ( )( ) [ ] [ ]( ) ( ) [ ] [ ] ( )( ) falsesbpsTttsCtruesp sTttsCfalsesbpsTttsCtruesp sbTttsbCfalsesbpsTttsCtruesp rGsbrGs rrrr rrrrrr sbCsC sbTsTrrrrrr =∧=∧≠∧= ⇔≠∨=∨=∧=∧≠∧= ⇔≠∨=∨=∧=∧≠∧= ⇔∉∧∈ = = '''' '''''' '''''' '' '' '' sử dụng luật De Morgan và giả thiết [ ] [ ] [ ] [ ]( )[ ] falsesTttsCsTttsC rrrr =≠∨=∧=∧≠ '''' Như vậy : Điều kiện ( ) ( ) ( )rGsbrGs ∉∈ '' vaø tương đương với ( ) [ ] [ ] ( )( ) falsesbpsTttsCtruesp rrrr =∧=∧≠∧= '''' (5) Công thức này cho chúng ta cách thức để phát sinh luật r bị ảnh hưởng bởi sự thay đổi ( )'' sbs → gồm các bước sau: 1. Tạo tất cả những vị từ p áp dụng được trên mẫu 's (sử dụng các khung vị từ trong khung luật). 2. Nếu [ ] [ ]'' sTsC ≠ thì Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 76 a. Nếu [ ]( ) falsesbp =' thì Giảm ( )rgood , r là luật đã được tạo ra có vị từ p và đích là [ ]'sT 3. Ngược lại a. Nếu [ ]( ) falsesbp =' thì Giảm ( )rbad cho mọi luật r có vị từ là p và [ ]'sCtr ≠ Thuật toán phát sinh những luật r cần tăng ( )rgood trong công thức (4) có thể được suy ra từ công thức (1), và trường hợp tăng ( )rbad trong công thức (3) được suy ra từ công thức (2). Điều này được thực hiện dễ dàng bằng cách chuyển trạng thái của 's và ( )'sb )( falsetrue ↔ . Trường hợp (3), khi ( )'' sbs → , ta phải phát sinh mới tất cả những luật có thể có. 2. Trường hợp 2 [ ] ( )[ ]'' sbCsC ≠ (b thay đổi nhãn của mẫu 's ) Trong trường hợp này, công thức (5) trở thành: ( ) ( ) [ ] ( )( ) [ ]( )( )''''' sbCtfalsesbpsTttsCtruesp rrrrr =∨=∧=∧≠∧= (6) Thật vậy, ( ) ( ) ( ) ( ) [ ] [ ] ( )( ) ( )[ ] ( )[ ]( ) [ ] ( )[ ] ( ) [ ] [ ] ( )( ) ( )[ ]( )''''' '''''' '' '' sbCtfalsesbpsTttsCtruesp sbTttsbCfalsesbpsTttsCtruesp rGsbrGs rrrrr sbTsTrrrrrr =∨=∧=∧≠∧= ⇔≠∨=∨=∧=∧≠∧= ⇔≠∧∈ = Tuy nhiên, trong trường hợp (2) thì đơn giản hơn. Từ điều kiện [ ] ( )[ ]'' sbCsC ≠ và ( )rBs∈ , có thể suy ra ( ) ( )rBsb ∉' ; thật ra, điều kiện cần thiết để mẫu 's thuộc về tập ( )rB là 's được gán nhãn phân loại chính xác [ ] [ ]'' sTsC = . Do [ ] ( )[ ]'' sbCsT ≠ , kéo theo ( )[ ] [ ]'' sTsbC ≠ , và do đó ( ) ( )rBsb ∉' . Khi đó, điều kiện (4) tương đương với ( ) [ ] [ ] [ ]'''' sTsCtsCtruesp rr =∧≠∧= (7) Trong thuật toán, thay điều kiện kiểm tra ( )( ) falsesbpr =' bằng kiểm tra điều kiện ( )( ) ( )[ ] rr tsbCfalsesbp =∨=' trong công thức (1) và tương tự cho trường hợp (2). Công thức được sử dụng để phát sinh luật r trong trường hợp (3) và (4) được làm tương tự như trường hợp (1) và (2) bằng cách thay đổi vai trò của s và b(s). Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 77 3.2.2.3 Thuật toán Đối với mỗi mẫu s thoả điều kiện [ ] [ ]sTsC ≠ Phát sinh tất cả các luật r sửa sai cho s, tăng )(rgood . Đối với mỗi mẫu s thoả điều kiện [ ] [ ]sTsC = Phát sinh tất cả các vị từ p sao cho ( ) truesp = ; đối với mỗi luật r có ppr = và [ ]sCtr ≠ , tăng )(rbad 1: Tìm luật ( )rfb Rr∈= maxarg Nếu ( ( )bf < Ngưỡng) thì Thoát. Đối với mỗi vị từ p, Đặt ( )pR là tập luật có vị từ là p(hay ( ) { }pprpR r == | Đối với mỗi mẫu ', ss sao cho [ ] ( )[ ]sbCsC ≠ và ( )sVs∈' : Nếu [ ] ( )[ ]'' sbCsC = thì Đối với mỗi vị từ p thoả ( ) truesp =' Nếu [ ] [ ]'' sTsC ≠ thì Nếu ( )( ) falsesbp =' thì { Giảm )(rgood với [ ][ ]', sTpr = là luật được tạo ra với vị từ p và đích [ ]'sT } Ngược lại Nếu ( )( ) falsesbp =' thì { Với tất cả các luật ( )pRr∈ có [ ]'sCtr ≠ , giảm )(rbad } Đối với mỗi vị từ p sao cho ( )( ) truesbp =' Nếu [ ] [ ]'' sTsC ≠ thì Nếu ( )( ) falsesbp =' thì { tăng )(rgood , với [ ][ ]', sTpr = } Ngược lại Nếu ( )( ) falsesbp =' thì { Với tất cả các luật ( )pRr∈ có [ ]'sCtr ≠ , tăng )(rbad } Ngược lại Đối với mỗi vị từ p sao cho ( ) truesp =' Nếu [ ] [ ]'' sTsC ≠ thì Nếu ( )( ) ( )[ ] rtsbCfalsesbp =∨= '' thì { giảm )(rgood , với [ ][ ]', sTpr = } Ngược lại { Với mỗi luật ( )pRr∈ có [ ]'sCtr ≠ , giảm )(rbad } Đối với mỗi vị từ p sao cho ( )( ) truesbp =' Nếu ( )[ ] [ ]'' sTsbC ≠ thì Nếu ( ) [ ] rtsCfalsesp =∨= '' thì { tăng )(rgood , với [ ][ ]', sTpr = } Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 78 Ngược lại Với mỗi luật ( )pRr∈ có ( )[ ]'sbCtr ≠ , tăng )(rbad Lặp lại từ bước 1: 3.3 Mô hình chuyển đổi cây cú pháp sử dụng thuật toán FnTBL Đầu vào của chương trình chuyển đổi cây cú pháp là câu tiếng Anh đã được phân tích cú pháp theo dạng cây cú pháp (hình 17). Chương trình chuyển đổi cây cú pháp thực hiện việc chuyển vị trí, chèn, xoá các thành phần trong cây cú pháp. Và sau khi các từ tiếng Anh được gán ngữ nghĩa, ta sẽ có được câu tiếng Việt có nghĩa tuy chưa tự nhiên lắm. Để được câu hoàn chỉnh cần một số xử lý thêm về mặt hình thái tiếng Việt. S1 NP VP DT NN AUX VP VBD PP IN NP is plugged into microprocessor . S The . NP NN DT NN POS motherboard the computer ‘s (a) Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 79 Hình 17: Minh hoạ chuyển đổi cây cú pháp cho câu “The microprocessor is plugged into the computer’s motherboard.” a: Trước khi chuyển đổi b: Sau khi chuyển đổi (Các thành phần bị xoá chỉ được đánh dấu xoá, không xoá trực tiếp trên cây cú pháp) Sau khi gắn nghĩa vào cây ta có kết quả như sau: Câu tiếng Anh The microprocessor is plugged into the computer ‘s motherboard Chuyển 0 1 2 3 4 0 7 6 5 S1 NP VP DT NN AUX VP VBD PP IN NP is plugged into microprocessor . S The . NP NN DT NN POS motherboard the computer‘s (b) Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 80 đổi cấu trúc (thể hiện) bị xóa bị xóa Chuyển đổi từ vựng bộ vi xử lý đư ợc gắn vào máy tính của bản mạch chính Câu tiếng Việt Bộ vi xử lý được gắn vào bản mạch chính của máy tính 3.3.1 Mô hình áp dụng chuyển đổi cây cú pháp Quá trình chuyển đổi cây cú pháp cho một câu tiếng Anh diễn ra theo 4 bước: 1. Chuyển đổi trật tự theo nguyên tắc: Chuyển đổi trật tự các thành phần con của một thành phần cú pháp không kết thúc theo các nguyên tắc phổ biến được thống kê từ ngữ liệu dựa trên các mối quan hệ ngữ pháp. Bước này phải đóng vai trò là bộ gán nhãn chuyển đổi cơ sở trong quá trình học để rút luật sửa sai. 2. Chuyển đổi trật tự cùng cấp: Áp dụng luật học bằng phương pháp FnTBL từ ngữ liệu song ngữ để chuyển đổi trật tự các thành phần con của một thành phần cú pháp không kết thúc. Thực chất là quá trình sửa sai và hoàn chỉnh thêm cho bước 1. 3. Chuyển đổi trật tự khác cấp: Áp dụng luật chuyển đổi được rút ra từ ngữ liệu song ngữ dạng cây bằng phương pháp FnTBL. Bước này nhằm chuyển những thành phần về đúng vị trí của nó, vị trí mới và vị trí cũ có thể không cùng thành phần cha. 4. Chèn, xoá: Bước này có nhiệm vụ chèn thêm những từ tiếng Việt có vai trò ngữ pháp trong câu mà không thuộc phạm vi chuyển đổi từ vựng (Chẳng hạn như “phải không” trong câu hỏi). Ngoài ra, nó còn đảm nhiệm việc xoá những thành phần không có vai trò ngữ pháp trong câu tiếng Việt (Chẳng hạn như trợ động từ). Thực chất của việc xoá chỉ là đánh dấu xoá chứ không xoá hẳn khỏi cây cú pháp. Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 81 Hình 18: Mô hình áp dụng chuyển đổi cây cú pháp Sau đây, chúng em sẽ trình bày mô hình học FnTBL để rút luật chuyển đổi và mô hình gán nhãn chuyển đổi cơ sở theo nguyên tắc. Cây phân tích cú pháp của câu tiếng Anh Cây phân tích quan hệ của câu tiếng Anh Chuyển đổi trật tự theo nguyên tắc (Gán nhãn cơ sở) Chuyển đổi trật tự cùng cấp (Áp dụng luật chuyển đổi bước 1) Chuyển đổi trật tự khác cấp (Áp dụng luật chuyển đổi bước 2) Chèn, xoá (Áp dụng luật chèn xoá) Kết quả chuyển đổi cây cú pháp Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 82 3.3.2 Mô hình học luật chuyển đổi bằng phương pháp học FnTBL Hình 19: Mô hình học luật chuyển đổi cây cú pháp theo thuật toán FnTBL Gán nhãn ban đầu (Bộ gán nhãn theo nguyên tắc) Ngữ liệu huấn luyện bước 1 chưa được gán nhãn Danh sách luật bước 2 Danh sách luật bước 1 Bộ áp dụng luật bước 1 Ngữ liệu huấn luyện bước 1 đã được gán nhãn Ngữ liệu vàng bước 1 Khung luật bước 1 BỘ HỌC 1 Ngữ liệu vàng bước 2 Khung luật bước 2 BỘ HỌC 2 Ngữ liệu huấn luyện bước 2 đã được gán nhãn Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 83 3.3.2.1 Gán nhãn chuyển đổi cơ sở theo nguyên tắc Trong một ngữ, trật tự các thành phần bổ nghĩa thường đứng trước hoặc đứng sau từ được bổ nghĩa. Cùng một loại bổ nghĩa, đối với các ngôn ngữ khác nhau thì vị trí tương đối này vẫn có thể không giống nhau. Chẳng hạn như tính từ miêu tả trong tiếng Việt thường đứng sau từ mà nó bổ nghĩa, còn trong tiếng Anh thì ngược lại (old book ≠ cuốn sách cũ). Phân tích quan hệ ngữ pháp trong câu nhằm mục tiêu xác định và phân loại tất cả các quan hệ ngữ pháp có thể có trong câu. Nói cách khác, một câu được phân tích quan hệ ngữ pháp sẽ cho chúng ta biết từ nào trong câu bổ nghĩa cho từ nào. Điều này không những có ý nghĩa rất lớn trong việc khử nhập nhằng ngữ nghĩa của câu, giúp cho việc chọn nghĩa tốt hơn, mà còn có thể giúp cho chúng ta thiết lập trật tự các thành phần của câu. Bài toán đặt ra là “Cho một ngữ tiếng Anh, tập hợp tất cả các mối quan hệ trong ngữ đó và những nghĩa tiếng Việt tương ứng của mỗi từ trong ngữ tiếng Anh (từ không được gắn nghĩa có nghĩa rỗng). Hãy xây dựng ngữ tiếng Việt.” Một cách làm đơn giản như sau: ™ Ánh xạ các quan hệ ngữ pháp sang tiếng Việt ™ Xây dựng ngữ tiếng Việt từ các quan hệ đã ánh xạ theo thứ tự từ quan hệ cấp thấp đến quan hệ cấp cao. Sở dĩ ta có thể thực hiện việc ánh xạ các quan hệ và xây dựng ngữ từ các quan hệ này nhờ vào nguyên lý “Tương ứng trực tiếp” (Direct Corresponding Assumption) [17]. Chúng em chỉ sử dụng các quan hệ ngữ pháp để tái tạo ngữ tiếng Việt mà không tái tạo toàn bộ cây là do đối với những câu dài, việc tái tạo còn liên quan đến xác định mẫu câu dựa trên quan hệ vị từ-đối số khá phức tạp. Bộ phân tích quan hệ có sẵn chưa xác định được chính xác các quan hệ ở mức câu này. 3.3.2.1.1 Xác định ánh xạ quan hệ Trong luận văn này giải quyết vấn đề chuyển đổi cấu trúc. Do đó, chúng em chỉ xây dựng ánh xạ quan hệ ngữ pháp về mặt trật tự. Có nghĩa là với một loại quan Chương 3 – Mô hình chuyển đổi cây cú pháp Trang 84 hệ nào đó, ta cần xác định trật tự tương đối của thành phần bổ nghĩa so với thành phần được bổ nghĩa. Ánh xạ này sẽ được rút ra từ ngữ liệu theo phương pháp thống kê. Mỗi quan hệ được lưu với thông tin về loại ngữ xuất hiện quan hệ, trật tự tương đối phổ biến nhất cùng với các ngoại lệ. Loại ngữ Quan hệ tiếng Anh Quan hệ tiếng Việt Ngoại lệ Ví dụ Danh ngữ PRP$ Æ(gen) NN NNÅ(gen)PRP$ My bookÆCuốn sách của tôi DTÆ(det)NN NNÅ(det)DT the, a, an That bookÆCuốn