MÔ HÌNH TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN (CONDITIONAL ...

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

CHưƠNG 3: MÔ HÌNH TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN (CONDITIONAL RANDOM FIELDS -CRFS)

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 (2.09 MB, 57 trang )

30- Chữ viết thƣờng không đậm nhƣ , ,… là ký hiệu các giá trị đơn nhƣmột dữ liệu quan sát hay một trạng thái.- S: tập hữu hạn các trạng thái của một mô hình CRF.Khái niệm CRFsKý hiệunhãn vàphầnilà biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần phải gánlà biến ngẫu nhiên nhận giá trị là chuỗi nhãn tƣơng ứng. Mỗi thànhcủalà một biến ngẫu nhiên nhận giá trị trong tập hữu hạn các trạngthái S. Trong bài toán nhận diện thực thể,có thể nhận giá trị là các câu tronglà một chuỗi ngẫu nhiên các tên thực thể tƣơng ứng vớingôn ngữ tự nhiên,các câu này và mỗi thành phầnicủacó miền giá trị là tập tất cả các nhãn tênthực thể (tên ngƣời, tên địa danh,…).Cho một đồ thị vô hƣớng không có chu trình= ( , ), ở đâ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 đồ thị. Các đỉnhbiểu diễn các thành phần của biến ngẫu nhiênmột giữa một đỉnh và một thành phần củavsao cho tồn tại ánh xạ một –của . Ta nói ( , ) là một trƣờngngẫu nhiên điều kiện (CRFs) khi với điều kiện , các biến ngẫu nhiêntuântheo tính chất Markov đối với đồ thị :(Ở đây,v| ,,≠v) = (v| , Y, (v))(3.1)(v) là tập tất cả các đỉnh kề với v.Nhƣ vậy, một CRF là một trƣờng ngẫy nhiên phụ thuộc toàn cục vàoTrong các bài toán xử lý dữ liệu dạng chuỗi,( = {1, 2, …, m},n).= {(i,i+1)}). Ký hiệuMô hình đồ thị cho CRF có dạng nhƣ sau.đơn giản chỉ là dạng chuỗi= ( 1,2,…,n),= ( 1,.=2,…,31Mô hình CRFlà tập hợp tất cả các đồ thị con đầy đủ của đồ thịGọi– đồ thị biểu diễncấu trúc của một CRFs. Áp dụng kết quả của Hammerley – Clifford cho cáctrƣờng ngẫu nhiên Markov, thừa số hóa đƣợc phân phối p(y|x) thành tích củahàm tiềm năng:Vì trong bài toán xử lý dữ liệu dạng chuỗi, đồ thị biểu diễn cấu trúc củamột CRFs có dạng đƣờng thẳng nhƣ trên, nên tập phải là hợp của và ,trong đólà tập các cạnh của đồ thịvàlà tập các đỉnh của , hay nói cáchkhác, đồ thị con A hoặc là gồm một đỉnh, hoặc gồm một cạnh của . Bằng cácháp dụng nguyên lý cực đại ghóa entropy, Lafferty xác định hàm tiềm năng củamột CRFs có dạng một hàm mũ :Ở đâylà một thuộc tính của chuỗi dữ liệu quan sát vàLagrange liên kết vớitin của thuộc tính, nói cách khác,là thừa sốlà trọng số chỉ mức biểu đạt thông.Có hai loại thuộc tính cạnh (ký hiệu là ) và thuộc tính đỉnh (ký hiệu là )tùy thuộc vàolà đồ thị gồm một đỉnh hay một cạnh của . Thay các hàm tiềmnăng vào công thức (3.2) và thêm vào một thừa số chuẩn hóa (x) (để đảm bảotổng xác suất của tất cả các chuỗi nhãn tƣơng ứng với một chuỗi dữ liệu quan sátbằng 1) ta đƣợc :32Ở đây, x, y là chuỗi dữ liệu quan sát và chuỗi trạng thái tƣơng ứng; fk làthuộc tính của toàn bộ chuỗi quan sát và các trƣờng trạng thái tại vị trí i-1, itrong chuỗi trạng thái ; gk là thuộc tính của toàn bộ chuỗi quan sát và trạng tháitại vị trí i trong chuỗi trạng thái. Thừa số chuẩn hóa Z(x) đƣợc cho nhƣ sau:(là các vector các tham số của mô hình,sẽ đƣợc ƣớclƣợng giá trị nhờ các phƣơng pháp ƣớc lƣợng tham số cho mô hình.3.2. Ƣớc lƣợng tham số mô hình CRFsKỹ thuật sử dụng để đánh giá tham số cho mô hình CRFs là làm cực đạihóa độ đo likelihood của tập huấn luyện.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ỗiquan sát và một chuỗi trạng thái tƣơng ứng = {( (i), (i))} i = 1... }. Độ đolikelihood giữa tập huấn luyện và mô hình điều kiện tƣơng ứng ( | , ) làở đây (là cáctham số của mô hình vàlà phân phốithự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àmlikelihood.ML = arg max L()(3.7)ML đảm bảo những dữ liệu mà chúng ta quan sát đƣợc trong tập huấnluyện sẽ nhận đƣợc xác suất cao trong mô hình. Nói cách khác, các tham số làm33cực đại hàm likelihood sẽ làm phân phối trong mô hình gần nhất với phân phốithực nghiệm trong tập huấn luyện. Vì việc tính  dựa theo công chức (3.7) rấtkhó khăn, nên thay vì tính toán trực tiếp, cần xác định  làm cực đại logarit củahàm likelihood:Vì hàm logarit là hàm đơn điệu, nên việc làm 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 (3.8), ta có:ở đây, (1, 2,…, n) và (1, 1,…, 1) là các vector tham số của mô hình, f làvector các thuộc tính (f1(yi-1, yi, x), f2(yi-1, yi, x),…), g là vector các thuộc tính(g1(yi, x), g2(yi, x),…).Hàm log likelihood cho mô hình CRFs là một hàm lõm và trơn trong toànbộ không gian của tham số. Bản chất của hàm lõm của log-likelihood cho phépta 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ầncủa vector gradient của log-likelihood bằng không. Mỗi thành phần trong vectorgradient của hàm log-likelihood là đạo hàm log-likelihood theo tham số k, nhậnđƣợc:34Việc thiết lập phƣơng trình trên bằng 0 tƣơng đƣơng với việc đƣa ra mộtràng buộc cho mô hình: giá trị trung bình của fk theo phân phối)bằng giá trị trung bình của fk theo phân phối thực nghiệm.Về phƣơng diện toán học, bài toán ƣớc lƣợng tham số cho một mô hìnhCRFs chính là bài toán tìm cực trị của hàm log-likelihood. Trong các phƣơngpháp tìm cực trị của hàm đa biến bằng cách sử dụng các thông tin về vectorgradient, phƣơng pháp L-BFGS đƣợc đánh giá là hội tụ nhanh và hiệu quả hơnso với các phƣơng pháp khác. Ƣu điểm của phƣơng pháp này là tránh đƣợc việctính toán trực tiếp ma trận Hessian của hàm log-likelihood trong quá trình tìmcực trị.Thuật toán gán nhãn cho dữ liệu dạng chuỗi:Tại mỗi vị trí i trong chuỗi quan sát, ta xác định ma trận |S|*|S| nhƣ sau :(3.11)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ệmcủa phƣơng trình :*=(3.13)Thuật toán Viterbi tìm chuỗi y*:là xác suất của “chuỗi trạng thái độ dài kết thúc bởi trạng tháiGọivà có xác suất lớn nhất”, biết chuỗi quan sát là x. Với mọi trạng thái ‟ trong tậptrạng thái :(3.14)Đặt(3.15)Giả sử chuỗi dữ liệu quan sát x có độ dài n, sử dụng kỹ thuật quay lui đểtìm chuỗi trạng thái * tƣơng ứng nhƣ sau:Bước 1: Với mọi*thuộc tập trạng thái tìm35Bước lặp: Chừng nào*3.3. Ứng dụng CRFs trong trích chọn thông tinCRFs đƣợc ứng dụng thành công rất nhiều trong các lĩnh vực nhƣ tin- sinhhọc, xử lý ngôn ngữ tự nhiên và khai phá Text/Web. Ở đây điểm qua một số vídụ thành công của CRFs trong trích chọn thông tin.- Ứng dụng CRFs trong trích chọn thông tin bảng biểu từ văn bản [17].Trong ứng dụng này, CRFs đƣợc sử dụng để đoán nhận các dòng trongvăn bản xem dòng nào thuộc các đoạn văn thông thƣờng, dòng nào chứathông tin về bảng biểu. Thông tin đƣợc đoán nhận dựa rất nhiều vào đặcđiểm của các dòng văn bản và các kỹ tự đặc biệt (ký tự tạo bảng). Cácdòng kề nhau cũng có tính phụ thuộc lẫn nhau và rất thích hợp để mô hìnhhóa bằng CRFs. Kết quả cho thấy CRFs cho độ chính xác cao hơn đángkể so với các phƣơng pháp khác.- Ứng dụng CRFs trong trích chọn thông tin từ văn bản nhằm hỗ trợ quátrình điền form (form filling) bán tự động [18]. Trong ứng dụng này CRFsđƣợc thay đổi một chút với các ràng buộc (constraints) đƣợc tích hợp vàothuật toán giải mã Viterbi cho phép thông tin trích chọn từ các văn bảnkhi điền vào form có tính phụ thuộc và ràng buộc lẫn nhau. Ví dụ, nếumột trƣờng đã là họ tên thì các trƣờng khác không thể là họ tên, hoặc nếumột trƣờng đã là số điện thoại văn phòng thì các trƣờng khác ít có khảnăng là số điện thoại văn phong nữa, vì thƣờng chỉ có một số điện thoạivăn phòng. Bằng cách đó, ngƣời ta nâng độ chính xác của điền form bántự động lên đáng kể. Bài toán này quan trọng khi các công ty nhận đƣợcnhững đơn đặt hàng hoặc hợp đồng qua email bằng văn xuôi và hệ thốngsẽ trích chọn thông tin từ các email này một cách bán tự động để điền vàocơ sở dữ liệu. Ứng dụng này sẽ giảm đáng kể công sức của nhân viênnhập dữ liệu ở những công ty, tổ chức có lƣợng giao dịch lớn.Ngoài ra CRFs còn có nhiều ứng dụng khác nhƣ trong bài toán nhận dạngthực thể, trích chọn thông tin từ đầu mục của các bài báo nghiên cứu. Ngoài raCFRs cũng đƣợc chỉnh sửa thay đổi để phù hợp với các bài toán trích chọn dữliệu trên Web. Sau đây là một số ứng dụng:36- Ứng dụng CRFs cho bài toán nhận biết thực thể (named entityrecognition) [25].- Ứng dụng CRFs trong trích chọn thông tin từ các bài báo nghiên cứu [26].- Ứng dụng CRFs để trích chọn các nguồn ý kiến đánh giá [27].- Ứng dụng CRFs hai chiều để trích chọn thông tin trên Web [28].37CHƢƠNG 4: ỨNG DỤNG GPU SONG SONGTỪNG PHẦN CÔNG CỤ CRF++4.2. Công cụ CRF++Tác giả của CRF++ là Taku Kudo [16], một chuyên gia ngƣời Nhật,chuyên về các lĩnh vực nhƣ:Xử lý ngôn ngữ tự nhiênPhân tích thống kê, phân tích phụ thuộc thống kê, chunking, phân tíchhình thái học.Học máy (Support Vector Machines, Boosting, Maximal MarginClassifiers).Khai phá dữ liệu, khai phá văn bản.CRF++ [9] là một phần mềm nguồn mở, có thể tùy chỉnh đƣợc, dùng choviệc phân đoạn, tách từ, gán nhãn dữ liệu tuần tự của mô hình trƣờng ngẫu nhiêncó điều kiện (Conditional Random Fields – CRFs). CRF++ đƣợc thiết kế chomục đích chung chung và đƣợc áp dụng cho một loạt các tác vụ xử lý ngôn ngữtự nhiên (NLP) nhƣ nhận dạng thực thể tên (Named Entity Recognition), tríchchọn thông tin (Information Extraction) và Text Chunking.Đặc điểm của CRF++:Có thể định nghĩa lại tập thuộc tính.Viết bằng ngôn ngữ C++ theo STL (Standard Template Library).Huấn luyện nhanh dựa trên thuật toán LBFGS, là một thuận toán quasinewton cho bài toán tối ƣu với dữ liệu lớn.Sử dụng ít bộ nhớ trong huấn luyện và kiểm thử.Mã hóa và giải mã trong thời gian thực.Có thể cho kết quả là n đầu ra tốt nhất.Có thể thực hiện huấn luyện MIRA (đơn tốt nhất).Có thể cho ra xác xuất biên cho tất cả ứng cử viên.Đƣợc viết dƣới dạng một phần mềm nguồn mở.38CRF++ có hai module độc lập, đó là module huấn luyện (crf_training) vàmodule kiểm thử (crf_test).Để chạy phần training và testing cần phải định nghĩa trƣớc tệp huấn luyện(training) và kiểm thử (test). Và các tệp tin này phải có định dạng riêng choCRF++. Nói chung training và testing gồm nhiều thẻ (tokens). Mỗi thẻ gồmnhiều cột. Định nghĩa của thẻ phụ thuộc vào tác vụ cụ thể. Tuy nhiên, trong hầuhết các trƣờng hợp, chúng đơn giản tƣơng ứng với chữ. Mỗi thẻ phải đƣợc thểhiện trên một dòng, với các cột đƣợc phân cách với nhau bởi khoảng trắng. Mộtchuỗi các thẻ tạo thành một câu. Để xác định ranh giới giữa các câu, một dòngtrống đƣợc đặt vào. Có thể có nhiều cột, tuy nhiên số lƣợng các cột trong các thẻphải bằng nhau. Hơn nữa có một số ngữ nghĩa giữa tƣơng ứng với các cột. Ví dụcột thứ nhất là từ (word), cột thứ hai là „POS tag‟, cột thứ ba là „sub-category ofPOS‟, v.v….Cột cuối cùng thể hiện một thẻ trả lời đúng sẽ đƣợc huấn luyện bởiCRF.Ví dụ của file trainingThe DT B-NPrisks NNS I-NPfor IN B-PPsterling NN B-NPof IN B-PPa DT B-NPbad JJ I-NPtrade NN I-NPfigure NN I-NPare VBP B-VPvery RB B-ADVPheavily RB I-ADVPon IN B-PPthe DT B-NPdown JJ I-NPHình 12: Ví dụ tệp tin huấn luyệnTrong ví dụ này, có ba cột trong một thẻ. Cột 1 là từ, cột 2 là từ loại, và cột3 là tag trả lời thể hiện ở định dạng IOB2.CRF++ là công cụ đƣợc thiết kế cho mục đích đa dụng. Phải định nghĩa filemẫu đặc điểm (feature template), và file này mô tả các đặc điểm đƣợc dùngtrong training và testing.Mỗi dòng trong file template biểu thị một template. Trong mỗi template,macro %x[row,col] sẽ đƣợc dùng để chỉ một token trong dữ liệu đầu vào. Row

Xem Thêm

Tài liệu liên quan

• Lập trình song song trên nền đơn vị xử lý đồ họa và ứng dụng
  • 57
  • 983
  • 0
• Hạch toán vật liệu và công cụ, dụng cụ với việc nâng cao hiệu quả sử dụng vốn lưu động tại Công ty In Công đoàn Việt Nam
  • 118
  • 285
  • 0
• Hoàn thiện công tác kế toán xác định kết quả kinh doanh và phân tích kết quả kinh doanh tại Công ty Vật tư vận tải xi măng
  • 60
  • 428
  • 0

Tải bản đầy đủ (.pdf) (57 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(2.09 MB) - Lập trình song song trên nền đơn vị xử lý đồ họa và ứng dụng-57 (trang) Tải bản đầy đủ ngay ×