Chương 2: Mô Hình Trường Ngẫu Nhiên Có điều Kiện - Tài Liệu Text

Có thể bạn quan tâm

Trang chủ >
Luận Văn - Báo Cáo >
Công nghệ thông tin >

Chương 2: Mô hình trường ngẫu nhiên có điều kiện

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.56 MB, 55 trang )

14đại (Maximum entropy Markov models, MEMMs) [18] và các mô hình Markov cóđiều kiện dựa trên mô hình đồ thị có hướng. CRFs cho kết quả tốt hơn cả MEMMs vàHMMs trong nhiều bài toán gãn nhãn chuỗi dữ liệu trong thế giới thực [8, 23].Phần sau sẽ trình bày những nét khái quát về mô hình đồ thị, làm cơ sở để từ đógiới thiệu về mô hình CRFs.2.1. Mô hình đồ thịCho G  (V , E ) là một đồ thị với V là tập các đỉnh và E là tập các cạnh. Trongđó V  X  Y với X, Y là tập các biến ngẫu nhiên, được biểu diễn bằng các nút hìnhtròn. X thường là tập các biến đầu vào mà ta quan sát được, và Y là tập các biến đầu ramà ta cần dự đoán. Nếu giữa hai nút không có cạnh nối thì hai nút đó độc lập có điềukiện. Độc lập có điều kiện nghĩa là hai biến ngẫu nhiên a, b độc lập với một biến ngẫunhiên cho trước c nếu hai biến này độc lập với phân phối xác suất có điều kiện củachúng, hay p(a, b | c)  p(a | c) p(b | c) . Những đồ thị biểu diễn được tính chất độc lập cóđiều kiện của các phân phối cơ sở như này được gọi là đồ thị độc lập, vì đồ thị có thểbiểu diễn tính chất độc lập có điều kiện của các phân phối cơ sở.Độc lập có điều kiện là một khái niệm quan trọng vì nó có thể được sử dụng đểphân tích một phân phối xác suất phức tạp thành tích của các thừa số, trong đó mỗithừa số chứa tập con các biến ngẫu nhiên tương ứng. Khái niệm này giúp cho các tínhtoán phức tạp trở nên hiệu quả hơn.Kí hiệu các chữ thường đậm x, y, s, v… là vector biểu diễn chuỗi dữ liệu quansát, vector biểu diễn chuỗi trạng thái.…. Phân phối xác suất đồng thời sẽ được phântích thành tích các thừa số  s với v s là tập con các biến ngẫu nhiên tương ứng cấuthành nên thừa số  s này.p( v)    s ( v s )s(2.1)Hai dạng phổ biến nhất của mô hình đồ thị là mô hình đồ thị có hướng và môhình đồ thị vô hướng. Điểm khác nhau của hai dạng này là cách phân tích phân phốixác suất đồng thời thành tích các thừa số. Phần sau sẽ trình bày về mô hình đồ thị vôhướng.Mô hình đồ thị vô hướngKhái niệm clique: Trong lý thuyết đồ thị, một clique trong một đồ thị vô hướngG là một tập các đỉnh V thoả mãn: với mỗi cặp đỉnh thuộc V luôn tồn tại một cạnh nối.15Do vậy một đồ thị con được tạo ra từ V sẽ là một đồ thị đầy đủ. Kích thước của mộtclique là số đỉnh của nó.Một clique tối đa (maximal clique) là tập các đỉnh V sao cho đồ thị con đượctạo ra từ V là một đồ thị con đầy đủ và không là tập đỉnh con của bất kỳ đồ thị đầy đủlớn hơn nào khác.Kí hiệu C là tập clique tối đa của đồ thị. Với mỗi clique c  C , gọi  c ( v c ) làhàm tiềm năng của các biến ngẫu nhiên v C . Mô hình đồ thị vô hướng sẽ phân tích xácsuất đồng thời p( v) thành tích các hàm tiềm năng:p( v) 1 C (v C )Z cC(2.2)Hàm tiềm năng có thể là hàm bất kỳ nhưng phải thoả mãn điều kiện hàmdương, nhận giá trị thực. Vì tính tổng quát này nên hàm tiềm năng không nhất thiếtphải là một hàm xác suất. Do đó, cần đưa thêm hệ số chuẩn hoá Z đảm bảo tổng xácsuất của tất cả các chuỗi đầu vào bằng 1 tức là p( v)  1 . Hệ số Z được tính theovcông thức:Z    c ( v c )v(2.3)cCViệc tính toán Z là một trong những thách thức khi học tham số mô hình. Đểđơn giản, các nhà nghiên cứu thường xấp xỉ giá trị này.2.2. Mô hình trường ngẫu nhiên có điều kiệnKí hiệu X là biến ngẫu nhiên tương ứng với chuỗi quan sát và Y là biến ngẫunhiên tương ứng với chuỗi nhãn. Mỗi thành phần Y i của Y là một biến ngẫu nhiênnhận trá trị trong tập hữu hạn các trạng thái S.Một CRF là một mô hình đồ thị vô hướng phụ thuộc toàn cục vào biến ngẫunhiên biểu diễn chuỗi quan sát. Một cách hình thức, định nghĩa G  (V , E ) là một đồ thịvô hướng sao cho mỗi nút v V tương ứng với một biến ngẫu nhiên biểu diễn thànhphần Yv của Y. Nếu biến ngẫu nhiên Y v tuân theo tính chất Markov đối với đồ thị G tức là xác suất của biến ngẫu nhiên Y v khi đã biết X và tất cả các biến ngẫu nhiên khácY{u|u  v, {u,v}  V} bằng xác suất của biến ngẫu nhiên Y v khi đã biết X và các biếnngẫu nhiên khác tương ứng với các đỉnh kề với đỉnh v trong đồ thị:p(Yv | X, Yu, u  v, {u,v}  V) = p(Yv | X, Yu, (u,v)  E)16thì (X, Y) là một trường ngẫu nhiên có điều kiện.Về lý thuyết, cấu trúc của đồ thị G có thể tuỳ ý sao cho có thể mô hình hoá tínhchất độc lập có điều kiện của các thành phần trong chuỗi trạng thái; Tuy nhiên, khi môhình hoá dữ liệu, cấu trúc đồ thị đơn giản và phổ biến nhất là cấu trúc dạng chuỗituyến tính; Tức là các nút tương ứng với các thành phần của Y tạo thành chuỗi bậcmột đơn giản. CRFs có cấu trúc như này được gọi là CRFs chuỗi tuyến tính, minh hoạnhư hình vẽ sau:Hình 6: Mô hình đồ thị CRFsCRFs tính xác suất p(y | x) của chuỗi trạng thái có thể y  ( y1 ,..., yn )  n vớiđiều kiện đã biết chuỗi quan sát x  ( x1 ,..., xn ) n . Từ công thức 2.1, xác suất có điềukiện p(y | x) có thể được viết lại như sau:p ( y | x) =p(x, y )=p ( x)p(x, y ) y' p(y', x)1 cC  c (xc , y c )Z1   c (xc , y 'c )Z y' cCTừ đó ta có công thức tính xác suất p(y|x) của CRFs:p ( y | x) 1  c (xc , y c )Z (x) cC(2.4)(2.5)Trong đó  C là các nhân tố khác nhau tương ứng với các clique trong đồ thị(Kschischang 2001). Thừa số chuẩn hóa Z(x):Z (x)   cC  c (xc , y')(2.6)y'Đối với CRFs chuỗi tuyến tính, clique tối đa trong đồ thị gồm các đỉnh yi, yi-1 và x;Tức là tập clique tối đa C   j ( y j , y j 1 , x) | j 1,..., n . Do đó công thức 2.6 trởthành:p ( y | x) 1 n  j (x, y)Z (x) j 1(2.7)17Với thừa số chuẩn hóa:nZ (x)    j (x, y')y'(2.8)j 1Lafferty định nghĩa hàm tiềm năng cho CRFs chuỗi tuyến tính có dạng sau: i (x, y )  exp   k tk ( yi 1 , yi , x)   k sk ( yi , x) k k(2.9)Trong đó tk là hàm chuyển trạng thái của chuỗi quan sát x từ trạng thái yi-1 sangtrạng thái yi. sk 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 trongchuỗi trạng thái. k và  k là các tham số được ước lượng từ dữ liệu huấn luyện.Thay vào (2.8) ta có xác suất của chuỗi trạng thái y khi biết chuỗi quan sát x là:P ( y | x) 1exp    k t k (y i 1 , y i , x)    k s k (y i , x) Z ( x)  i kik(2.10)Ở đây, thừa số chuẩn hóa Z(x) được tính theo công thức:Z (x)   exp    k t k (y i 1 , y i , x)    k s k (y i , x) yik i k(2.11)Với cấu trúc chuỗi tuyến tính của CRF, vấn đề ước lượng tham số và suy diễnđược định nghĩa tương tự như mô hình Markov ẩn: Cho trước chuỗi quan sát x và một CRF M, hãy tìm chuỗi trạng thái y phùhợp nhất với chuỗi quan sát x. Cho tập các chuỗi quan sát x và các chuỗi trạng thái y tương ứng, hãy tìmcác tham số của CRF M sao cho cực đại xác suất p(y|x, M).2.3. Ước lượng tham số và suy diễn CRFs2.3.1. Ước lượng tham số cho CRFsHai phương pháp được sử dụng để ước lượng tham số cho mô hình từ tập dữliệu huấn luyện là ước lượng bằng phương pháp cực đại hoá khả năng (MaximumLikelihood Estimation - MLE) và cực đại phân phối tiên nghiệm (Maximum a PrioriEstimation - MPE). Phần này sẽ trình bày sơ lược về phương pháp cực đại hoá khảnăng, phương pháp mà hiện nay được nhiều nhà nghiên cứu áp dung.Giả sử dữ liệu huấn luyện gồm một tập N cặp , mỗi că ̣p gồ m mô ̣t chuỗi quan, D={(x(i),y(i))} i  1 N . Độ đo likel ihoodgiữa tập huấ n luyê ̣n và mô hinh điề u kiê ̣n tương ứng p(y|x,  ) là:̀sát và một chuỗi trạng thái tương ứng18L( )   p( y | x,  ) p ( x , y )(2.12)x, yỞ đây  (1 , 2 ,..., 1,  2 ..) là các tham số của mô hình và~(x, y ) là phân phốipthực nghiê ̣m đồ ng thời của x,y trong tâ ̣p huấ n luyê ̣n.Hai tính chất của hàm likelihood cho phép nó được sử dụng để đánh giá chấtlượng của một mô hình p( y | x, ) là:L( )  0 và L( )  0 khi và chỉ khi p( x, y)  0 với mọi p( y | x, )  1MLE sử dụng hàm likelihood để xếp hạng các giá trị có thể của  . Nguyên lýcực đại hoá entropy phát biểu rằng giá trị  sẽ được chọn sao cho nó làm cực đại hàmlikelihood:ML  arg max L( ) ML(2.13)đảm bảo những dữ liệu mà chúng ta quan sát được trong tập huấn luyệnsẽ nhận được xác suất cao trong mô hình. Nói cách khác, các tham số làm cực đại hàmlikelihood sẽ làm phân phối trong mô hình gần nhất với phân phối thực nghiệm trongtập huấn luyện. Vì việc tính teta dựa theo công thức (2.1) rất khó khăn nên thay vì tínhtoán trực tiếp, ta đi xác định teta làm cực đại logarit của hàm likelihood (thườ ng đươ ̣cgọi tắt là log-likelihood):l ( )   p( x, y) log  p( y | x,  ) (2.14)x, yHàm logarit là hàm đơn điệu nên việc này không làm 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.3), ta có:n n1l ( )   ~(x, y )   * t    * s   ~(x) * log Zppx,yi 1 i 1 x(2.15)Ở đây,  (1 , 2 ,..n ) và  (1 ,  2 ,...,  m ) là các vector tham số của mô hình, t làvector các thuộc tính chuyể n (t1(yi-1,yi,x),t2(yi-1,yi,x),…), s là vector các thuộc tínhtrạng thái (s1(yi,x),s2(yi,x),…).Hàm log-likelihood cho mô hình CRF là một hàm lồi và trơn trong toàn bộkhông gian của tham số. Bản chất hàm lồi của log-likelihood cho phép ta có thể tìmđược giá trị cực đại toàn cục  bằng cách thiết lập các thành phần của vector gradientcủa hàm log-likelihood bằng không. Mỗi thành phầ n trong vector gradient của hàmlog-likelihood là đa ̣o hàm của hàm log -likelihood theo mô ̣t tham số của mô hình . Đạohàm hàm log – likelihood theo tham số  k ta được:19l ( ) E ~ ( x,y )  f k   E p ( y|x, )  f k pk(2.16)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àngbuộc cho mô hình: giá trị kỳ vọng của tk theo phân phối ~(x) p(y | x, ) bằng giá trị kỳpvọng của tk theo phân phối thực nghiệm ~(x, y) .pVề phương diê ̣n toán ho ̣c , bài toán ước lượng tham số cho một mô hình CRFchính là bài toán tìm cực đa ̣i của hàm log-likelihood. Tuy nhiên, thiết lập phương trìnhtrên bằng 0 và giải phương trình để tìm  không phải lúc nào cũng khả thi. Do đó, cáctham số làm cực đại hàm likelihood thường được chọn bằng cách sử dụng phươngpháp lặp (IIS và GIS), các phương pháp tối ưu số (Conjugate Gradient, phương phápNewton…).2.3.2. Suy diễn CRFsTa xem xét hai vấn đề suy diễn trong CRFs chuỗi tuyến tính. Thứ nhất, trongquá trình huấn luyện mô hình, để tính toán gradient cần phải tính phân phối lớn nhấtp(yt|x). Thứ hai, để gán nhãn cho chuỗi quan sát mới, chúng ta phải tính chuỗi trạngthái phù hợp nhất với chuỗi trạng thái này. Điều này tương đương với việc làm cực đạiphân phối xác suất giữa chuỗi trạng thái y và dữ liệu quan sát x. Chuỗi trạng thái y*mô tả tốt nhất chuỗi dữ liệu quan sát x sẽ là nghiệm của phương trìnhy*  arg max{ p( y | x)}Với CRFs chuỗi tuyến tính, cả hai bài toán suy diễn trên đều có thể giải quyếtmột hiệu quả và chính xác bởi các thuật toán quy hoạch động như thuật toán Viterbi,thuật toán tiến-lùi (Forward-Backward). Ngoài ra hướng tiếp cận dựa trên lấy mẫu sẽhội tụ sau một số vòng lặp như chuỗi Markov Monte Carlo cũng được sử dụng, tuykhông phổ biến. Phần sau sẽ trình bày về thuật toán Viterbi, một trong những thuậttoán điển hình và hiệu quả đã được áp dụng rộng rãi trong mô hình Markov ẩn.Gọi  j ( s | x) là xác suất lớn nhất của chuỗi trạng thái có độ dài j, kết thúc ởtrạng thái s: j (s | x)  max p( y1 , y2 ,..., y j  s | x)y1 , y2 ,..., y j 1(2.17)Bước quy nạp là: j 1 (s | x)  max  j ( s | x). j 1 ( x, s, s ')s 'SMảng  j ( s) lưu giá trị của j và s. Thật toán thực hiện như sau:(2.18)201. Khởi tạoGiá trị của tất cả các bước từ trạng thái bắt đầu  tới tất cả các trạng thái có thểbắt đầu được khởi tạo như sau:s  S :1 ( s)  1 ( x, , s) j ( s) (2.19)2. Đệ quyGiá trị ở bước tiếp theo được tính bằng giá trị hiện tại và giá trị lớn nhất của tấtcả các giá trị s‟ có thể:s  S :1  j  n : j ( s)  max  j 1 ( s '). ( x, s, s ')s 'S j ( s)  arg max  j 1 ( s ').( x, s, s ')(1.20)s 'S3. Kết thúcp*  max  n ( s ')s 'S(2.21)*yn  arg max  n ( s ')s 'S4. Chuỗi trạng thái tối ưu:Tính toán chuỗi tối ưu bằng cách lần theo vết của  tyt*   t 1 ( yt*1 )t  n  1, n  2,...,1(2.22)21Chương 3: Đặc điểm cụm danh từ tiêng Việt và phương phápxây dựng tập dữ liệu3.1. Đặc điểm cụm danh từ tiếng ViệtTiếng Việt là ngôn ngữ của người Việt và là ngôn ngữ chính thống tại ViệtNam. Tiếng Việt là ngôn ngữ có nguồn gốc bản địa, xuất thân từ nền văn minh nôngnghiệp tại nơi mà ngày nay là khu vực phía bắc lưu vực sông Hồng và sông Mã củaViệt Nam. Do quá trình tiếp xúc lâu dài giữa tiếng Việt và tiếng Hán đã đưa vào tiếngViệt một khối lượng từ ngữ rất lớn của tiếng Hán. Tỉ lệ vay mượn tiếng Hán trongtiếng Việt rất lớn nhưng đại đa số những từ đó đều đã được Việt hóa cho phù hợp vớinhận thức của người Việt.Hệ thống chữ viết chính thức hiện nay của tiếng Việt là chữ Quốc Ngữ - đượcxây dựng dựa trên chữ cái Latin, thêm các chữ ghép và 9 dấu phụ trong đó có 4 dấutạo ra các âm mới và năm dấu còn lại để thể hiện thanh điệu của từ.Giống như nhiều ngôn ngữ khác ở Đông Nam Á, tiếng Việt thuộc loại hìnhngôn ngữ đơn lập. Những ngôn ngữ thuộc loại hình này còn được gọi là các ngôn ngữkhông có hình thái, ngôn ngữ không biến hình hoặc ngôn ngữ phân tiết. Các đặc điểmchính của từ tiếng Việt là:Từ trong tiếng Việt được cấu tạo bằng một âm tiết hoặc là tổ hợp nhiều âm tiếtđược kết hợp theo các cách khác nhau. Phụ thuộc vào sự kết hợp của các âmtiết, chúng ta có thể phân loại từ tiếng Việt thành ba nhóm: từ đơn, từ ghép, từláy. Với các từ được cấu tạo từ hai âm tiết trở lên, các âm tiết được phân cáchnhau bởi dấu cách trống, ví dụ “Việt Nam”, “sinh viên”… Vì vậy, dấu cáchtrống không phải là dấu hiệu để nhận ra ranh giới giữa các từ. Theo các nhàngôn ngữ học thì tiếng Việt có đến 80% là các từ gồm hai âm tiết (theo [2]).Từ không biến đổi hình thái: hình thái của từ không chỉ ra quan hệ giữa các từtrong câu. Vì vậy, quan hệ ngữ pháp chỉ được diễn đạt bằng trật tự trước saucủa từ và/hoặc bằng các hư từ.Ví dụ: Anh ấy đã cho tôi một cuốn sách (1)Tôi cũng cho anh ấy hai cuốn sách (2)22Xét về mặt ngữ âm và sự thể hiện bằng chữ viết Anh ấy ở cả hai câu hoàn toànkhông có sự thay đổi. Tuy nhiên, về vai trò ngữ pháp trong câu, Anh ấy trongcâu (1) đóng vai trò là chủ ngữ, ở câu (2) lại giữ vai trò bổ ngữ.Vấn đề xác định từ loại cho từ trong tiếng Việt phức tạp hơn các tiếng châu Âudo chúng ta không thể dựa vào các đặc tính đặc biệt về hình thái học của từ đểxác định loại từ. Trong tiếng anh, các danh từ chỉ các khái niệm phi sự vậtthường dễ dàng được nhận diện một cách độc lập thông qua việc thêm các thànhtố phụ vào phía trước hoặc phía sau các động từ, tính từ tương ứng. Ví dụ cáctừ: develop (phát triển) là động từ, thêm thành tố ment vào phía sau thành danhtừ development (sự phát triển); educate (giáo dục) là động từ, thêm thành tố ionvào phía sau thành danh từ education (sự giáo dục, nền giáo dục)… Tiếng Việtkhông có hiện tượng này nên việc xác định từ loại của các từ khó hơn vì chúngcó cùng vỏ ngữ âm và ý nghĩa diễn tả như các từ loại khác. Ví dụ từ “thànhcông” khi xuất hiện trong các ngữ cảnh khác nhau sẽ có từ loại tương ứng khácnhau:(1) Thành công của dự án đã tạo tiếng vang lớn(2) Anh ấy rất thành công trong nghiên cứu khoa học(3) Buổi biểu diễn đã thành côngTrong câu (1) từ „thành công‟ là một danh từ, trong câu (2) từ „thànhcông‟ là một động từ và trong câu (3) từ „thành công‟ lại là một tính từ. Vì vậy,việc nhận dạng từ loại của từ tiếng Việt chủ yếu dựa vào ngữ cảnh xuất hiện,tức là dựa vào khả năng kết hợp giữa các từ với nhau.Cấu trúc của cụm danh từ tiếng Việt hiện cũng là một vấn đề còn nhiều tranhluận giữa các nhà ngôn ngữ học. Cụm từ tiếng Việt và cụm danh từ tiếng Việt đượcnhiều nhà ngôn ngữ học trong và ngoài nước quan tâm nghiên cứu như Nguyễn TàiCẩn, Nguyễn Kim Thản, Diệp Quang Ban, Tuong Hung Nguyen (theo [5]).Theo quan điểm của Nguyễn Tài Cẩn [4], cụm danh từ gồm có một bộ phậntrung tâm do danh từ đảm nhiệm và các thành tố phụ. Các thành tố này chia làm hai bộphận: một số thành tố phụ đứng trước danh từ trung tâm tạo thành phần đầu của cụmdanh từ, một số khác thì đứng sau danh từ trung tậm, tạo thành phần cuối của cụmdanh từ. Cụm danh từ có dạng đầy đủ gồm có ba phần: phần đầu, phần trung tâm, phầncuối; dạng không đầy đủ chỉ có hai phần, thí dụ:Cụm danh từ đầy đủ: Ba học sinh nàyCụm không đầy đủ gồm phần đầu và danh từ trung tâm: Ba học sinh

Xem Thêm