Khóa luận Tìm hiểu mô hình CRF và ứng dụng trong trích chọn thông tin trong tiếng Việt

ký hiệu cho một giá trị đơn như một dữ liệu quan sát hay một trạng thái. S là tập các hữu hạn trạng thái. O là tập dữ liệu quan sát được. 2.1. MÔ HÌNH MARKOV ẨN- HMM Mô hình Markov được giới thiệu vào cuối những năm 1960 [12]. Cho đến hiện nay nó có một ứng dụng khá rộng như trong nhận dạng giọng nói, tính toán sinh học (Computational Biology ), và xử lý ngôn ngữ tự nhiên. HMM là mô hình máy hữu hạn trạng thái với các tham số biểu diễn xác suất chuyển trạng thái và xác suất sinh dữ liệu quan sát tại mỗi trạng thái. Mô hình Markov ẩn là mô hình thống kê trong đó hệ thống được mô hình hóa được cho là một quá trình Markov với các tham số không biết trước, nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Trong bài toán trích chọn thông tin nhà đất thì các tham số quan sát được đó chính là các từ trong câu, còn các trạng thái chính là các nhãn B-DC, I-DC, B-DT, I-DT.. Trong một mô hình Markov điển hình, trạng thái được quan sát trực tiếp bởi người quan sát [21], và vì vậy các xác suất chuyển tiếp trạng thái là các tham số duy nhất (hình 5 có thể mô tả rõ cho điều này). Hình 5. HMM - xi — Các trạng thái trong mô hình Markov - aij — Các xác suất chuyển tiếp - bij — Các xác suất đầu ra- yi — Các dữ liệu quan sát Mô hình Markov ẩn thêm vào các đầu ra: mỗi trạng thái có xác suất phân bố trên các biểu hiện đầu ra có thể. Vì vậy, nhìn vào dãy của các biểu hiện được sinh ra bởi HMM không trực tiếp chỉ ra dãy các trạng thái. Ta có tìm ra được chuỗi các trạng thái mô tả tốt nhất cho chuỗi dữ liệu quan sát được bằng cách tính. (2.1) Y1 Y2 … … … Yn X1 X2 … … … Xn Hình 6. Đồ thị vô hướng HMM Ở đó Yn là trạng thái tại thời điểm thứ t=n trong chuỗi trạng thái Y, Xn là dữ liệu quan sát được tại thời điểm thứ t=n trong chuỗi X. Do trạng thái hiện tại chỉ phụ thuộc vào trạng thái ngay trước đó với giả thiết rằng dữ liệu quan sát được tại thời điểm t chỉ phụ thuộc và trạng thái t. Ta có thể tính P(Y, X). (2.2) Một số hạn chế của mô hình Markov để tính được xác suất P(Y,X) thông thường ta phải liệt kê hết các trường hợp có thể của chuỗi Y và chuỗi X. Thực tế thì chuỗi Y là hữu hạn có thể liệt kê được, còn X (các dữ liệu quan sát) là rất phong phú. Để giải quyết các vấn đề này HMM đưa ra giả thiết về sự độc lập giữa các dữ liệu quan sát: Dữ liệu quan sát được tại thời điểm t chỉ phụ thuộc vào trạng thái tại thời điểm đó. Hạn chế thứ hai gặp phải là việc sử dụng xác suất đồng thời P(Y, X) đôi khi không chính xác vì với một số bài toán thì việc sử dụng xác suất điều kiện P(Y | X) cho kết quả tốt hơn rất nhiều. 2.2. MÔ HÌNH CỰC ĐẠI HÓA ENTROPY-MEMM Mô hình MEMM [4] thay thế các xác suất chuyển trạng thái và các xác suất sinh quan sát trong HMM bởi một hàm xác suất duy nhất P(Si | Si-1, Oi) (xác suất dịch chuyển từ trạng thái hiện tại là Si-1 tới trạng thái trước đó là Si với dữ liệu quan sát hiện tại là Oi) thay vì sử dụng P(Si | Si-1) và P(Oi | Si). Mô hình MEMM quan niệm rằng các quan sát đã được cho trước và chúng ta không cần quan tâm đến xác suất sinh ra chúng mà chỉ quan tâm vào xác suất chuyển trạng thái. Dưới đây là đồ thị có hướng mô tả cho mô hình MEMM. S1 S2 … … … Sn S1:n Hình 7. Đồ thị có hướng mô tả cho mô hinh MEMM Qua đồ thị ta nhận thấy rằng quan sát hiện tại không chỉ phụ thuộc vào trạng thái hiện tại mà còn có thể phụ thuộc vào trạng thái trước đó. Xác suất P(S | O) có thể tính như sau: (2.3) MEMM coi dữ liệu quan sát là các điều kiện cho trước thay vì coi chúng là các thành phần được sinh bởi mô hình như trong HMM vì thế xác suất chuyển trạng thái có thể phụ thuộc vào các thuộc tính đa dạng của chuỗi dữ liệu quan sát. Với mô hình này ta chia thành các hàm dịch chuyển được huấn luyện một cách riêng biệt trong |S| - tập hợp trạng thái. Như sau: McCallum xác định phân phối cho xác suất chuyển trạng thái có dạng hàm mũ sau: (2.4) Ở đây là các tham số cần được huấn luyện; Z(Ot, St) là thừa số chuẩn hóa để tổng xác suất chuyển từ trạng St-1 sang St kề với nó đều bằng 1; fa(Ot, St) là hàm thuộc tính tại vị trí thứ i trong chuỗi dữ liệu quan sát và trong chuỗi trạng thái. Ở đây ta định nghĩa mỗi một thuộc tính fa có hai đối số: Dữ liệu quan sát hiện tại và trạng thái hiện tại. McCallum cũng đinh nghĩa a= trong đó b chỉ phụ thuộc vào dữ liệu quan sát hiện tại. 1 nếu dữ liệu quan sát hiện tại là “1tỷ” b(Ot)= 0 nếu ngược lại Hàm thuộc tính fa xác định nếu b(Ot) nhận một giá trị xác định: 1 nếu b(Ot)=1 và St=St-1 f(Ot,St)=  0 nếu ngược lại Vấn đề “label alias” gặp phải trong mô hình MEMM Vấn đề gặp phải ở mô hình MEMM [14] “lable alias”. Xét một ví dụ đơn giản sau: Hình 8. label alias Giả sử ta cần xác định chuỗi trạng thái khi xuất hiện chuỗi quan sát là “rob” do vậy chuỗi trạng thái đúng là 0345 vì vậy ta mong đợi xác suất. P( 0345|rob ) > P( 0125|rob) Lại có P(0125|rob) = P(0)*P(1|0, r)*P(2|1,o )*P(5|2, b). Do xác suất chuyển trạng thái của 2 trạng thái kề nhau là l. Do vậy: P(0125 | rob)=P(0)*P(1 | 0, r). Tương tự ta cũng có P(0345 | rob)=P(0)*P(3 | 0, r). Nếu trong tập huấn luyện “rib”xuất hiện nhiều hơn “rob” thì chuỗi trạng thái S=0125 luôn được chọn dù chuỗi quan sát là rib hay rob. Đây là hạn chế gặp phải trong mô hình MEMM, hạn chế này ảnh hưởng rất lớn đến quá trình gán nhãn của MEMM. Để giải quyết vấn đề alias Léon Bottou (1991) [4] đưa ra một số cách sau: Thứ nhất như mô hình ở trên ta có thể gộp trạng thái 1 và 4 và trì hoãn việc phân nhánh cho đến khi gặp một quan sát xác định ( Discriminating Observation ). Nhưng đối với máy hữu hạn trạng thái thì điều này không thể vì xảy ra sự bùng nổ tổ hợp. giải pháp thứ hai là ta có thể luôn thay đổi cấu trúc trạng thái của mô hình điều này có nghĩa xác suất của toàn bộ chuỗi trạng thái sẽ không được bảo tồn mà có thể bị thay đổi trong một vài bước chuyển tùy thuộc vào quan sát đó. Trên đây là những vấn đề hạn chế của HMM và MEMM từ đó cho thấy nhu cầu cần thiết của mô hình CRF có thể giải quyết những hạn chế trên. 2.3. MÔ HÌNH CONDITIONAL RANDOM FIELDS CRF được giới thiệu vào những năm 2001 bởi Lafferty và các đồng nghiệp [14] [11]. CRF là mô hình dựa trên xác xuất điều kiện, thường được sử dụng trong gán nhãn và phân tích dữ liệu tuần tự ví dụ ký tự, ngôn ngữ tự nhiên. Khác với mô hình MEMM, CRF là mô hình đồ thị vô hướng. Điều này cho phép CRF có thể định nghĩa phân phối xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát hiện tại như trong mô hình MEMM. Chính những tính chất này của CRF mà mô hình này giải quyết được vấn đề “label bias”. 2.3.1. Việc gán nhãn cho dữ liệu tuần tự Nhiệm vụ của gán nhãn tuần tự [13] để thiết lập chuỗi quan sát được xuất hiện trong nhiều trường. Một trong những phương thức phổ biến để thực hiện gán nhãn và phân đoạn là sử dụng quy tắc HMM hoặc mô hình máy hữu hạn trạng thái để định nghĩa chuỗi các nhãn có thể xảy ra nhất cho những từ của bất cứ câu nào. Theo những nghiên cứu về mô hình Markov ẩn và mô hình cực đại hóa Entropy ở trên. Thì CRF đã giải quyết được toàn bộ những vấn đề mà hai mô hình trên mắc phải như “ label alias ”[11]. Conditional random fields là một probabilistic framework (theo xác suất) cho việc gán nhãn và phân đoạn dữ liệu tuần tự. Thay vì sử dụng xác suất độc lập trên chuỗi nhãn và chuỗi quan sát, ta sử dụng xác suất có điều kiện P(Y | X) trên toàn bộ chuỗi nhãn được đưa bởi chuỗi mỗi chuỗi quan sát X. CRF là một mô hình đồ thị vô hướng định nghĩa một phân bố tuyến tính đơn trên các chuỗi nhãn (trình tự nhãn) được đưa ra bởi các chuỗi quan sát được. CRFs thuận lợi hơn các mô hình Markov và MEMM. Nó làm tốt hơn cả của MEMM và HMM trên số lượng chuỗi gán nhãn lớn.Ví dụ: xét ngôn ngữ tự nhiên, việc gán nhãn cho các từ trong câu sẽ tương ứng với loại từ vựng. Ở đây các câu sẽ là dữ liệu tuần tự còn nhãn cần gán chính là các từ loại [NP He ] [VP reckons ] [NP the current account deficit ] [VP will narrow ] [PP to ] [NP only # 1.8 billion ] [PP in ] [NP September ] Trong đó ý nghĩa của các nhãn là: NP: nounse phrase, VP: verb phrase… Trong bài toán trích chọn thông tin nhà đất của mình thì dữ liệu tuần tự ở đây chính là các bản tin nhà đất, còn các nhãn cần gán đó là các thông tin về địa chỉ (B-DC, I-DC) hoặc diện tích (B-DT,I-DT)… 2.3.2. Định nghĩa CRF Trước khi xem định nghĩa trường ngẫu nhiên điều kiện ta xem định nghĩa thế nào là một trường ngẫu nhiên [9] Cho một đồ thị vô hướng không có chu trình G(V,E), ở đây V là tập các đỉnh của đồ thị và E là tập các cạnh vô hướng nối các đỉnh của đồ thị nếu thỏa mãn: thì V gọi là trường ngẫu nhiên (2.5) Y5 Y1 Y4 Y3 Y2 Y6 Hình 9. Một trường ngẫu nhiên P(Y5| Yi)=P(Y5|Y4,Y6) . Vậy Y={Y5, Y4,Y6} là trường ngẫu nhiên. Tiếp đến chúng ta định nghĩa trường ngẫu nhiên có điều kiện như sau: X là biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần phải gán nhãn.Y là biến ngẫu nhiên nhận giá trị là chuỗi nhãn tương ứng. Mỗi thành phần Yi của Y là một biến ngẫu nhiên nhận giá trị trong tập hữu hạn các trạng thái S. Các đỉnh V biểu diễn các thành phần của biến ngẫu nhiên Y sao cho tồn tại ánh xạ một – một giữa các đỉnh và một thành phần Yv của Y. Ta nói: CRF được định nghĩa: (Y | X) là một trường ngẫu nhiên điều kiện (Conditional Random Field) với điều kiện X khi ta chỉ tính được xác xuất có điệu kiện P(Yi | Xi) với YiY và Xi X và với mỗi Xi ta chọn được argmaxYiP(Yi | Xi). Trong bài toán dữ liệu dạng chuỗi, G có thể được biểu diễn như sau: G = ( V={1,2,3,…m}, E={i,i+1}i=1…m-1). Kí hiệu X=(X1, X2…Xn), Y=(Y1, Y2,…Yn). Ta có mô hình đồ thị vô hướng của CRF có dạng sau: Hình 10. Đồ thị vô hướng mô tả cho CRF Gọi C là tập hợp tất cả các đồ thị con đầy đủ của đồ thị G (đồ thị biểu diễn cấu trúc của một CRF). Theo kết quả của Hammerly-Clifford cho các trường Markov, ta thừa số hóa được p(y | x) – xác suất của chuỗi nhãn với điều kiện biết chuỗi dữ liệu quan sát – thành tích các hàm tiềm năng: P(y|x)= (2.6) Có thể mô phỏng như hình sau: Yt+3 Y t Yt+1 Ψ2 Yt+2 Ψ3 Ψ1 X1:n Hình 11. Mô tả các hàm tiềm năng Tính chất của trường ngẫu nhiên có điệu kiện là: Mô hình phân biệt (discriminative models) Mô hình chuỗi (sequential models) Mô hình đồ thị vô hướng (Undirected graphical models) 2.3.3. Nguyên lý cực đại hóa Entropy Laferty xác định các hàm tiềm năng cho các mô hình CRF dựa trên nguyên lý cực đại hóa Entropy [7]. Nguyên lý này cho phép đánh giá các phân phối xác suất từ một tập các dữ liệu huấn luyện. 2.3.3.1. Độ đo Entropy điều kiện Entropy là độ đo tính đồng đều hay tính không chắc chắn của một phân phối xác suất [7]. Độ đo Entropy điều kiện của một phân phối mô hình trên “một chuỗi trạng thái với điều kiện biết chuỗi dữ liệu quan sát ” p(y | x) có dạng sau: H(y | x) = - p(x, y)*log p(y | x) (2.7) = - p^(x)*p(y | x)*log p(y | x) 2.3.3.2. Các ràng buộc đối với phân phối mô hình Vấn đề chính là phải tìm ra chuỗi p*(y|x) sao cho thỏa mãn hàm mục tiêu sau: p* (y|x) = argmaxH(y|x) (2.8) Các ràng buộc đối với mô hình được thiết lập bằng cách thống kê các thuộc tính được rút ra từ tập dữ liệu huấn luyện. Ví dụ về một thuộc tính 1 nếu y=name, x=Mister fi(x,y)= 0 nếu ngược lại Tập các thuộc tính là tập hợp các thông tin quan trọng trong dữ liệu huấn luyện. Ký hiệu kì vọng của thuộc tính f theo phân phối xác suất thực nghiệm : = (2.9) Ở đây p^(x,y) là phân phối thực nghiệm trong dữ liệu huấn luyện. Dữ liệu huấn luyện gồm N cặp, mỗi cặp gồm một chuỗi dữ liệu quan sát và một chuỗi nhãn D={(xi,yi)}, khi đó phân phối thực nghiệm trong dữ liệu huấn luyện được tính như sau: = 1/N * số lần xuất hiện đồng thời của x,y trong tập huấn luyện Kỳ vọng của thuộc tính f theo phân phối xác suất trong mô hình Ep[f] = (2.10) Phân phối mô hình thống nhất với phân phối thực nghiệm chỉ khi kỳ vọng của mọi thuộc tính theo phân phối xác suất phải xấp xỉ bằng kì vọng của thuộc tính đó theo phân phối mô hình : (2.11) Từ công thức (2.11) có thể thấy rõ các ràng buộc của mô hình. 2.3.3.3. Nguyên lý cực đại hóa Entropy Gọi P là không gian của tất cả các phân phối xác suất điều kiện, và n là số các thuộc tính rút ra từ dữ liệu huấn luyện. P’ là tập con của P, P’ được xác định như sau: P’={ p} (2.12) Tư tưởng chính của nguyên lý cực đại hóa Entropy là ta phải xác định một phân phối mô hình sao cho: phân phối mô hình phải thỏa mãn mọi ràng buộc được rút ra từ thực nghiệm, và phải gần nhất với phân phối đều. Có nghĩa là ta phải tìm phân phối mô hình p( y | x ) thỏa mãn hai điều kiện thứ nhất phải thuộc tập P’ thứ hai là nó phải làm cực đại hóa Entropy điều kiện (2.7) Hay nói cách khác khi và p(y | x)≥0 và ta sẽ có (2.7) Với mỗi một thuộc tính fi ta đưa vào một thừa số langrange λi, ta định nghĩa hàm Lagrange L(p, λ) như sau: L(p, λ) = H(p)+ (2.13) Phân phối p(y | x) làm cực đại hóa độ đo Entropy H(p) và thỏa mãn n ràng buộc (2.11) cũng sẽ làm cực đại hàm L(p, λ). Từ (2.13) suy ra P(y | x) = (2.14) Ở đây Zλ(x) là thừa số chuẩn hóa để đảm bảo =1 với mọi x: Zλ(x)= (2.15) 2.3.4. Hàm tiềm năng của các mô hình CRF Bằng cách áp dụng nguyên lý cực đại hóa Entropy, Lafferty xác định hàm tiềm năng của một CRF có dạng hàm số mũ. ΨA(A|x)=exp (2.16) Trong đó: fk là một thuộc tính của chuỗi dữ liệu quan sát yk là trọng số chỉ mức độ biểu đạt thông tin của thuộc tính fk A là đồ thị con của đồ thị vô hướng G 2.3.5. Conditional Random Fields Mô hình CRFs cho phép các quan sát trên toàn bộ X, nhờ đó chúng ta có thể sử dụng nhiều thuộc tính hơn phương pháp Hidden Markov Model. Một cách hình thức chúng ta có thể xác định được quan hệ giữa một dãy các nhãn y và một câu đầu vào x qua công thức sau. (2.17) Ở đây x,y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; tk(yi-1,yi,x,i): là thuộc tính của toàn bộ chuỗi quan sát và các trạng thái tại vị trí i-1, i trong chuỗi trạng thái; sk(yi,x,i): là thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại vị trí i trong chuỗi trạng thái; λj, μk: là các tham số được thiết lập từ dữ liệu huấn luyện. Khi định nghĩa các thuộc tính , chúng ta xây dựng 1 chuỗi các thuộc tính b(x,i) của chuỗi dữ liệu quan sát để diễn tả vài đặc trưng nào đó của phân phối thực nghiệm của dữ liệu huấn luyện. Ví dụ : 1 nếu quan sát ở vị trí i và từ là = “Đình” b(x,i) = 0 nếu khác Mỗi một hàm mô tả sẽ nhận một giá trị của một trong số các giá trị thực b(x,i) là trạng thái hiện tại( nếu trong trường hợp hàm trạng thái ) hoặc là trạng thái trước và trạng thái hiện tại (trong trường hợp là hàm dịch chuyển) nhận giá trị riêng. Do đó toàn bộ hàm mô tả có giá trị thực. Hàm trạng thái sk(yi,x,i) dùng để xác định định danh của trạng thái Trong bài toán trích chọn thông tin nhà đất thì ví dụ một hàm trạng thái như sau: 1 nếu xi= “chuỗi các số” và yi =B-DD si = 0 nếu ngược lại Hàm dịch chuyển giúp thêm vào mối quan hệ giữa một nhãn và các nhãn liền kệ với nó. 1 nếu xi-1= “Mỹ”, xi= “ Đình” và yi-1=B_DC, yi=I_DC ti= 0 nếu ngược lại. Ở đó Z(x) là thừa số chuẩn hóa. Và được tính theo công thức sau: Z(x)= (2.18) θ(λ1 ,λ2…..,μ1, μ2) là các véctơ tham số của mô hình . θ sẽ được ước lượng giá trị trong phần tiếp theo. Chú ý rằng đối với các công thức (2.17) và (2.18) ta có thể viết một cách đơn giản như sau: sk(yi,x,i)= sk(yi-1, yi,x,i) và Fj(y,x)= . Ở đó fj(yi-1,yi,x,i) là hàm trạng thái sk(yi-1, yi,x,i) hoặc hàm dich chuyển tk(yi-1, yi,x,i). Điều này cho ta tính được xác suất của nhãn y khi biết chuỗi quan sát x: P(y|x,λ) =exp() (2.19) 2.3.6. So sánh với các mô hình khác Bản chất của phân phối toàn cục của CRF giúp cho các mô hình này tránh được vấn đề label alias . Qua quá trình thực nghiệm cho thấy tỉ lệ lỗi của CRF là thấp hơn cả so với MEMM và HMM Với 2000 mẫu dữ liệu huấn luyện và 500 mẫu test kết quả là tỷ lệ lỗi của CRF là 4.6%, của MEMM tỷ lệ lỗi là 42% [14]. Dữ liệu tăng theo chiều tăng của mũi tên Hình 12. Tỷ lệ lỗi của CRF so với các mô hình học máy khác 2.4. TỔNG KẾT CHƯƠNG Chương này giới thiệu những vấn đề cơ bản về CRF : định nghĩa CRF, việc gán nhãn cho dữ liệu dạng chuỗi, hàm tiềm năng cho các mô hình CRF, chứng tỏ được rằng CRF giải quyết được vấn đề label alias. Qua đó thấy được rằng CRF có khả năng xử lý dữ liệu tốt hơn rất nhiều so với các mô hình khác như HMM hay MEMM. Chương 3. THUẬT TOÁN GÁN NHÃN VÀ ƯỚC LƯỢNG THAM SỐ CỦA MÔ HÌNH CRF VÀ CÔNG CỤ CRF ++ Hai vấn đề quan trọng cần phải được đề cập đến khi nghiên cứu về mô hình CRF [8] đó là: thứ nhất khi đưa chuỗi nhãn y và một chuỗi quan sát x làm thế nào tìm ra một tham số λ của CRF để làm cực đại hóa xác suất p(y|x, λ) vấn đề này tạm gọi là huấn luyện (training). Thứ hai khi đưa ra một chuỗi quan xát x và một tham số λ làm thế nào để tìm được chuỗi các nhãn y phù hợp nhất tạm gọi vấn đề này quy nạp (inference). Ở chương này sẽ đi giải quyết từng vấn đề nêu ở trên. Đồng thời cũng giới thiệu được công cụ CRF++, một công cụ xây dựng dựa trên mô hình CRF. 3.1. THUẬT TOÁN GÁN NHÃN CHO DỮ LIỆU DẠNG CHUỖI Mục đích của việc gán nhãn là làm sao tìm được chuỗi y* sao cho cực đại hóa xác suất p(y|x, λ). Hay nói cách khác mục đích của thuật toán là làm sao tìm ra chuỗi nhãn phù hợp nhất với chuỗi dữ liệu quan sát. Với bài toán trích chọn thông tin nhà đất thì việc sử dụng thuật toán Virterbi đóng vai trò quan trọng. Thuật toán làm làm cho quá trình trích chọn chính xác hơn. Thay việc tính xác suất tổng các xác suất ta chỉ cần tính giá trị lớn nhất của xác suất dịch chuyển. Khi đó chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu quan sát x là nghiệm của phương trình. y*=argmax{p(y|x)} (3.1) =argmaxyexp =argmaxy Vì Z(x) không phụ thuộc vào nhãn riêng biệt x và số mũ là một hàm đơn điệu. Nên ta bỏ qua Z(x) trong công thức (3.1). Để tìm được y*, thỏa mãn (3.1) thì gặp phải một khó khăn trong thời gian tính toán, vì thời gian tính toán là hàm mũ. Chuỗi y* được xác đinh bằng thuật toán Virterbi [17]. Định nghĩa ∂i(y) là xác suất của chuỗi trạng thái độ dài i kết thúc bởi trạng thái y và có xác suất lớn nhất biết chuỗi quan sát là x. Trong đó ∂1(yk) là xác suất đầu tiên của mỗi trạng thái yk. Ta định nghĩa để ghi lại nhãn thứ i-1 có xác suất lớn nhất. Thuật toán dừng khi có giá trị là 1. Thuật toán Viterbi có thể được mô tả qua các bước sau: Bước 1: Khởi tạo ∂1(yk) = Bước 2: Đệ quy ∂i+1(yk) = Bước 3: Dừng Đệ quy dừng khi i=n= chiều dài của chuỗi Để có thể tìm được y* bằng cách sử dụng kỹ thuật backtracking. Khi đó y* sẽ là một dàng buộc, Những ràng buộc trong công thức (3.4) sẽ được chuyển qua ràng buộc bởi các chuỗi nhãn con C được định nghĩa như sau C=. Ràng buộc sẽ được viết đệ quy lại như sau: ∂t+1(yk)= 0 nếu ngược lại Trong ngữ cảnh của chúng ta thì ràng buộc C tương ứng với các chuỗi dữ liệu quan sát được chính xác bởi người sử dụng 3.2. XÁC SUẤT CRF ĐƯỢC TÍNH NHƯ MỘT MA TRẬN Để việc tính p(y|x, λ) – xác suất của chuỗi nhãn y khi biết chuỗi quan sát x một cách hiệu quả ta có thể tính được thông qua một ma trận [14] cách tính như sau: Ở chuỗi các nhãn ta thêm vào hai trạng thái start state và end state tương đương với nó là y0 và yn+1. Ta định nghĩa n+1 ma trận {Mi(x) có cỡ || với i=1,2..n ; là cạnh nỗi các nhãn y’ tới y}. Khi đó các phần tử trong ma trận được tính theo công thức sau: Mi(y’,y|x)=exp Khi đó xác suất của chuỗi nhãn y khi biết chuỗi quan sát x có thể được viết như kết quả xấp xỉ của các phần tử của n+1 ma trận cho từng cặp chuỗi p(y|x, λ)= Trong đó Z(x) được tính như sau Z(x)= 3.3. ƯỚC LƯỢNG THAM SỐ CHO MÔ HÌNH CRF Kỹ thuật được sử dụng để đánh giá tham số cho một mô hình CRF [11] là làm cực đại hóa độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm. Giả sử dữ liệu huấn luyện gồm cặp một chuỗi quan sát và một chuỗi trạng thái {x(k),y(k)} . Độ đo lilelihood giữa tập huấn luyện và mô hình điều kiện tương ứng p(y|x,θ) là: L(θ)= (2.20) Ở đây θ(λ1,λ2,...μ1,μ2) là các tham số mô hình và là phân phối thực nghiệm đồng thời của x, y trong tập huấn luyện. Nguyên lý cực đại likelihood: các tham số tốt nhất của mô hình là các tham số làm cực đại hàm likehood. θML=argmax θL(θ) (2.21) θML đảm bảo những dữ liệu quan sát được trong tập huấn luyện sẽ nhận xác suất cao trong mô hình. Để tính θ trong công thức (2.20 ) rất khó khăn ta lấy logarit 2 vế ( gọi tắt là log-likelihood ): l(θ) = (2.22) Vì hàm logarit là hàm đơn điệu nên việc làm này không thay đổi giá trị của θ được chọn . Thay p(y|x, θ) của mô hình CRF vào công thức (2.14): l(θ)= (2.23) Ở đây λ(λ1, λ2…λn) và μ(μ1, μ2.. μn) là các vector tham số của mô hình, t là vector các thuộc tính chuyển ; t là các vector thuộc tính chuyển (t1(yi-1,yi,x) ,t2(yi-1,yi,x)..); s là vector các thuộc tính trạng thái (s1(yi,x) , s2(yi,x) Hàm log-likelihood cho mô hình CRF là một hàm lõm và trơn trong toàn bộ không gian của tham số. Đạo hàm (2.23) theo λj ta được = = (2.24) Ở đólà phân phối thực nghiệm đồng thời của x,y trong tập huấn luyện Việc thiết lập phương trình trên bằng 0 tương đương với việc đưa ra một ràng buộc cho mô hình: giá trị trung bình của tk theo phân phối bằng giá trị trung bình của tk theo phân phối thực nghiệm. Thực chất bài toán ước lượng tham số cho một mô hình CRF là bài toán tìm cực đại của hàm log-kikelihood. Ở đây chúng ta sử dụng phương pháp lặp để tìm ra vector θ làm cực đại log-likelihood. Mục đích của phương pháp lặp là luôn cập nhất các tham số theo công thức sau: λk λk+ δλk μk μk + δμk Ở đây các giá trị δμk,, δλk được chọn sao cho giá trị của hàm log-likelihood gần với cực đại hơn. Trong phương pháp lặp ta tìm ra một cách thức cập nhật tham số mô hình sao cho log-likelihood nhận giá trị càng gần với cực đại càng tốt. Việc cập nhật tham số sẽ dừng khi hàm log-likelihood hội tụ. ISS cập nhật tham số δλk theo cách sau = = Ở đó T(x,y)= Việc cập nhật δμk làm tương tự. Tuy nhiên việc tính toán về phải của công thức trên là cả một vấn đề lớn bởi vì T(x,y) là biến toàn cục của x,y. Dưới đây trình bày hai thuật toán được dựa trên sự cải tiến của thuật toán Improved Iterative Scaling- IIS. 3.3.1. Thuật toán S Để giải quyết vấn đề trên ta sử dụng hàm yếu (slack feature) [14] được định nghĩa như sau: s(x,y)= S - Trong đó S là một hằng số để s(x(i),y) ≥0 cho tất cả các nhãn y và tất cả các vector của chuỗi quan sát x(i) trong tập huấn luyện. Đặc tính s là toàn cục tức là nó không tương ứng với một đỉnh hoặc một cạnh bất kỳ nào của đồ thị vô hướng. Với mỗi giá trị i= 0,…, n+1. Ta định nghĩa một forward vector như sau: 1 nếu y=start 0 nếu ngược lại Quy lạp =Mi(x) Tương tự ta cũng xác định backward vector được định nghĩa như sau: 1 nếu stop = 0 nếu ngược lại Và T =Mi+1(x) . Các tham số được cập nhật theo công thức sau: δλk=log δμk= Ở đó : Efk=* Esk= Tốc độ hội tụ của thuật toán S phụ thuộc vào độ lớn của S, độ lớn của S tỷ lệ nghịch với số lượng các bước cập nhật. 3.3.2. Thuật toán T Thuật toán đưa ra xấp xỉ T(x,y) ≈ T(x) = maxyT(x,y) Ta định nghĩa ak, t là kỳ vọng của tk bk,t là kỳ vọng của sk đưa ra T(x) = m. Khi đó ta cập nhật tham số là = log, δλk =log . Ở đó và được định nghĩa trong đa thức sau: =, = Để đơn giản ta chỉ xét trường hợp cập nhật tham số λk. Đưa ra hai tham số θ =(λ1, λ2,..) và θ’=( λ1+δλ1, λ2+δλ2.....) . Ta định nghĩa một hàm phụ như sau: -= = () -log ≥ () - = δλ . -δλ.t(x,y) ≥ δλ . -= Nhận xét rằng l(θ’) - l(θ) ≥ nên δλi làm cực đại cũng sẽ làm cực đại gia số của hàm log-likelihood. 3.4. CÔNG CỤ CRF++ TOOLKIT 3.4.1. Giới thiệu CRF ++ là một công cụ cài đặt mô hình CRF và được phân phối dưới dạng mã nguồn mở có thể dùng để phân đoạn và gán nhãn dữ liệu tuần tự [19]. CRF++ được thiết kế cho cùng một mục đích phổ dụng có thể ứng dụng trong những bài toán xử lý ngôn ngữ tự nhiên như nhận dạng thực thể tên, trích chọn thông tin và đóng khung văn bản. Hệ thống được hoạt động theo phương pháp học nửa giám sát được thực hiện gồm các bước sau: Bước 1: Tạo bộ dữ liệu huấn luyện bé. Bước này được thực hiện bằng tay Bước 2: Sử dụng mô hình CRFs để huấn luyện trên tập dữ liệu này. Bước 3: Tạo tập test và sử dụng CRFs để gán nhãn Bước 4: Bộ dữ liệu mới được sinh ra bằng cách bổ sung các nhãn cho tập dữ liệu test CRF++ được chia làm 2 modulo chính có thể mô tả như hình (13) như sau: Dữ liệu CRFs Model file Decoding Câu tiếng Việt Output Giai đoạn huấn luyện Giai đoạn thực hiện Hình 13. Mô hình hoạt động của CRF++ 3.4.2. Tính năng - Có thể định nghĩa lại các tính năng đã có, ta có thể tùy biến để thêm các đặc trưng mới phù hợp với bài toán cụ thể. - Viết bằng C++, là phần mềm mã nguồn mở - Bộ nhớ nhỏ sử dụng trong cả kiểm tra và phân tích - Có thể đưa ra xác suất lề cho tất cả những đầu vào. 3.4.3. Cài đặt và cách sử dụng 3.4.3.1 Cài đặt Chuyển vào thư mục chứa công cụ CRF++ Dùng lênh chmod 777 ./configure make clean && make 3.4.3.2. File định dạng huấn luyện và test Để sử dụng được CRF++ ta cần phải có 2 file dữ liệu, 1 file dùng cho quá trìn