Xem mã nguồn của Trường điều kiện ngẫu nhiên

{{wikify}}
'''Trường điều kiện ngẫu nhiên (CRFs)''' là một dạng của [[statistical model|Mô hình xác suất]]  thường được áp dụng cho [[structured prediction|Dự đoán cấu trúc]] trong [[Nhận dạng mẫu|Nhận diện mẫu]] và [[Học máy]]. Một mô hình phân lớp bình thường dự đoán nhãn cho một sample mà không quan tâm đến ngữ cảnh của sample đó (neighboring samples),còn một CRF có thể đưa ngữ cảnh tham gia vào quá trình gán nhãn; Ví dụ mô hình linear chain CRF nổi tiếng trong [[Xử lý ngôn ngữ tự nhiên]] dự đoán chuỗi các nhãn cho chuỗi samples đầu vào.

CRFs là một kiểu Mô hình đồ thị vô hướng xác suất. Nó dùng để mã hóa những mối quan hệ của những mẫu quan sát được và xây dựng nên những đặc tả phù hợp. Nó thường dùng để gán nhãn hay [[phân tích cú pháp]]  của một chuỗi dữ liệu, giống như những đoạn text bình thường hay chuỗi sinh học<ref name="Laf:McC:Per01">{{Chú thích hội nghị|authors=Lafferty, J., McCallum, A., Pereira, F.|title=Conditional random fields: Probabilistic models for segmenting and labeling sequence data|book-title=Proc. 18th International Conf. on Machine Learning|publisher=Morgan Kaufmann|date=2001|pages=282–289|url=http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers}}</ref>
và trong [[Thị giác máy tính]].<ref>{{Chú thích báo|title=Multiscale conditional random fields for image labeling|last1=He|first1=X.|authorlink=Xuming He|last2=Zemel|first2=R.S.|last3=Carreira-Perpinñán|first3=M.A.|date=2004|publisher=IEEE Computer Society|id={{citeseerx|10.1.1.3.7826}}}}</ref>
Đặc biệt, CRFs có thể ứng dụng trong phân tích cấu trúc câu,<ref>{{Chú thích hội nghị|title=shallow parsing with conditional random fields|author=Sha, F., Pereira, F.|date=2003|url=http://portal.acm.org/ft_gateway.cfm?id=1073473&type=pdf&CFID=4684435&CFTOKEN=39459323}}</ref> nhận diện những thực thể tên trong văn bản,<ref>{{Chú thích hội nghị|url=http://www.aclweb.org/anthology/W04-1221.pdf|title=Biomedical named entity recognition using conditional random fields and rich feature sets|author=Settles, B.|date=2004|book-title=Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications|pages=104–107}}</ref> tìm gen và peptide có vai trò quan trọng trong một khu vực tìm kiếm,<ref>{{Chú thích hội nghị|title=Analysis and Prediction of the Critical Regions of Antimicrobial Peptides Based on Conditional Random Fields.|publisher=PLoS ONE|author1=Chang KY|author2=Lin T-p|author3=Shih L-Y|author4=Wang C-K|date=2015|url=http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0119490}}</ref>
trong số ứng dụng khác nó cũng liên quan tới [[Mô hình Markov ẩn|hidden Markov models]](HMMs). Trong thị giác máy tính, CRFs thường được dùng để nhận biết đối tượng hoặc phân vùng ảnh.

== Mô tả ==
Lafferty, McCallum và Pereira<ref name="Laf:McC:Per01">{{Chú thích hội nghị|authors=Lafferty, J., McCallum, A., Pereira, F.|title=Conditional random fields: Probabilistic models for segmenting and labeling sequence data|book-title=Proc. 18th International Conf. on Machine Learning|publisher=Morgan Kaufmann|date=2001|pages=282–289|url=http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers}}</ref> định nghĩa CRF trên một mẫu quan sát và [[biến ngẫu nhiên]] như sau:<blockquote class="">Cho một đồ thị <math>G = (V, E)</math> sao cho

<math>\boldsymbol{Y} = (\boldsymbol{Y}_v)_{v\in V}</math>,

 tức là với mỗi phần tử trong <math>\boldsymbol{Y}</math> có một  ánh xạ tới một đỉnh của đồ thị <math>G</math>.

Ta gọi <math>(\boldsymbol{X}, \boldsymbol{Y})</math> là một conditional random field khi biến <math>\boldsymbol{Y}_v</math>, điều kiện <math>\boldsymbol{X}</math>, tuân theo tính chất [[Thuộc tính Markov|Markov property]] đối với đồ thị: <math>p(\boldsymbol{Y}_v |\boldsymbol{X}, \boldsymbol{Y}_w, w \neq v) = p(\boldsymbol{Y}_v |\boldsymbol{X}, \boldsymbol{Y}_w, w \sim v)</math>, <math>\mathit{w} \sim v</math> nghĩa là  <math>w</math> và <math>v</math> là hai đỉnh kề trong đồ thị <math>G</math>.
</blockquote>Điều này có nghĩa là một CRF là một mô hình đồ thị vô hướng mà những đỉnh có thể chia thành hai tập rời nhau <math /> và <math />, mẫu quan sát và biến đầu ra, respectively; phân phối có điều kiện <math /> được mô hình hóa.

=== Inference ===

Với những đồ thị bình thường thì những kết quả chính xác hoàn toàn (exact inference) trong CRFs cơ bản là không thể.Vấn đề inference của một CRF là cơ bản giống với MRF.<ref name="SuttonIntroduction">{{Chú thích arXiv|last1=Sutton|first1=Charles|last2=McCallum|first2=Andrew|class=stat.ML|year=2010|eprint=1011.4088v1|title=An Introduction to Conditional Random Fields}}</ref>
Tuy nhiên, vẫn tồn tại trường hợp đặc biệt mà exact inference là khả thi:
* Nếu đồ thị là dạng chuỗi hay cây, giải pháp là message passing algorithms.Thuật toán dùng trong trường hợp này giống với thuật toán forward-backward và thuật toán [[Viterb]]<nowiki/>i trong trường hợp của HMMs.
* Nếu CRF chỉ chứa pair-wise potentials và năng lượng là hàm submodular, combinatorial min cut/max flow algorithms là giải thuật.
Exact inference là không thể,nhưng cũng có vài thuật toán có thể dùng để thay thế được. Chúng bao gồm:
* Loopy belief propagation
* Alpha expansion
* Mean field inference
* Linear programming relaxations

=== Học tham số ===
Khi học tham số <math>\theta</math> ta thường dùng [[Hợp lí cực đại|maximum likelihood]] để học <math>p(Y_i|X_i; \theta)</math>. Nếu tất cả các nốt trong đồ thị có [[phân phối mũ]] and tất cả đều được quan sát trong quá trình trainning,hàm tối ưu là [[hàm lồi]].<ref name="SuttonIntroduction">{{Chú thích arXiv|last1=Sutton|first1=Charles|last2=McCallum|first2=Andrew|class=stat.ML|year=2010|eprint=1011.4088v1|title=An Introduction to Conditional Random Fields}}</ref> Có thể giải bằng thuật toán gradient descent hoặc Quasi-Newton methods như là thuật toán L-BFGS. Nói một cách khác nếu một vài node không được quan sát thì inference problem phải được giải quyết cho những biến này. Exact inference là không thể đối với những đồ thị bình thường nên ta phải dùng những thuật toán thay thê.

=== Thí dụ ===
Trong sequence modeling, người ta thường dùng đồ thị dạng chuỗi. Một chuỗi biến <math /> được biểu diễn bằng chuỗi những mẫu quan sát và <math /> là những biến chưa biết phải được suy ra từ những mẫu quan sát. <math /> được sắp xếp thành một chuỗi, với những cạnh giữa mỗi cặp <math /> và <math />. Và cũng có những miêu tả cơ bản cho <math /> như là "nhãn" cho mỗi phần tử trong chuỗi đầu vào, có thể sử dụng những thuật toán sau:
* Huấn luyện mô hình, phải học phân phối có điều kiện của <math /> và hàm thuộc tính được tìm ra từ dữ liệu huấn luyện.
* Giải mã, tìm ra xác suất của một chuỗi nhãn <math /> khi cho trước <math>X</math>.
* ''inference'', tìm ra nhãn có khả năng nhất khi cho trước <math>X</math>.
Những lệ thuộc có điều kiện của mỗi <math /> trên <math /> được xác định qua một chuỗi các hàm thuộc tính (feature function) có dạng <math /> <math />. Mô hình gán cho mỗi thuộc tính một trọng số và kết hợp những thuộc tính đó để xác định xác suất cho <math />.

Linear-chain CRFs có rất nhiều những ứng dụng tương tự đơn giản hơn hidden Markov models (HMMs), nhưng cần một số giả định về phân phối của các chuỗi input output.Một HMM có thể được hiểu là một CRF với những hàm thuộc tính rất đặc biệt nó dùng những xác suất bất biến để model những lần chuyển trạng thái. Ngược lại, một CRF có thể loosely được hiểu là một trường hợp tổng quát của một HMM.

Trái với HMMs, CRFs có thể chứa bất kỳ một lượng các hàm thuộc tính, hàm thuộc tính có thể kiểm tra toàn bộ chuỗi đầu vào <math /> ở bất cứ lúc nào trong quá trình inference, và các hàm thuộc tính không cần thiết phải được biểu diễn theo xác suất nào cả.

== Biến thể ==

=== Higher-order CRFs và semi-Markov CRFs ===
CRFs có thể trở thành higher-order models bằng việc làm cho mỗi <math /> phụ thuộc vào <math />  biến trước nó <math />. Huấn luyện và inference chỉ thực hiện được cho giá trị nhỏ của <math /> (như ''o'' ≤ 5),<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#x5B;''<span title="This claim needs references to reliable sources. (December 2008)">phạt cần</span>''&#x5D;</sup> vì độ phức tạp tính toán tăng theo [[hàm mũ]] của <math /> . Large-margin models cho dự đoán cấu trúc, như [[structured Support Vector Machine]] có thể nhìn thấy như là một sự thay thế huấn luyện thủ tục CRFs.

Có một trường hợp tổng quát khác của CRFs, '''semi-Markov conditional random field (bán CRF)''',nó mô hình hóa variable-length segmentations nhãn của chuỗi <math />.<ref>{{Chú thích sách|publisher=MIT Press|pages=1185–1192|editor=Lawrence K. Saul, Yair Weiss, Léon Bottou |last=Sarawagi|first=Sunita|last2=Cohen|first2=William W.|chapter=Semi-Markov conditional random fields for information extraction|chapter-url=http://papers.nips.cc/paper/2648-semi-markov-conditional-random-fields-for-information-extraction.pdf|title=Advances in Neural Information Processing Systems 17|url=http://papers.nips.cc/book/advances-in-neural-information-processing-systems-17-2004|location=Cambridge, MA|year=2005|access-date=2016-07-10|archive-date=2019-11-30|archive-url=https://web.archive.org/web/20191130080920/http://papers.nips.cc/book/advances-in-neural-information-processing-systems-17-2004}}</ref> Phương pháp này cung cấp nhiều khả năng của higher-order CRFs để mô hình hóa long-range dependencies của <math /> với độ phức tạp hợp ly.

=== Latent-dynamic conditional random field ===
'''Latent-dynamic Trường điều kiện ngẫu nhiên''' ('''LDCRF''') hay '''discriminative probabilistic latent variable models''' ('''DPLVM''') cũng là một kiểu CRFs cho bài toán dán nhãn chuỗi.Và là latent variable models được huấn luyện đặc biệt.

Trong LDCRF, giống như sequence tagging, một chuỗi mẫu quan sát đầu vào '''x''' = x ₁,... xₙ, vấn đề chính ở đây là làm cách nào để tìm ra chuỗi các nhãn '''y''' = y ₁,... yₙ từ tập nhãn Y. Thay vì trực tiếp mô hình hóa P('''y'''|'''x''') như linear-chain CRF,một bộ biến latent h được thêm vào giữa '''x''' và '''y''' bằng luật chain rule of probability:<ref name="lvperceptron">{{Chú thích hội nghị|author1=Xu Sun|author2=Takuya Matsuzaki|author3=Daisuke Okanohara|author4=Jun'ichi Tsujii|title=Latent Variable Perceptron Algorithm for Structured Classification|conference=IJCAI|year=2009|pages=1236–1242}}</ref>
: <math />
Nó tìm ra cấu trúc latent giữa mẫu quan sát và nhãn.<ref name="morency">{{Chú thích sách|last1=Morency|first1=L. P.|last2=Quattoni|first2=A.|last3=Darrell|first3=T.|doi=10.1109/CVPR.2007.383299|chapter=Latent-Dynamic Discriminative Models for Continuous Gesture Recognition|title=2007 IEEE Conference on Computer Vision and Pattern Recognition|pages=1|year=2007|isbn=1-4244-1179-3|pmid=|pmc=|url=http://dspace.mit.edu/bitstream/handle/1721.1/35276/MIT-CSAIL-TR-2007-002.pdf}}</ref> LDCRFs có thể train bằng quasi-newton, một version đặc biệt của thuật toán perceptron có tên là '''latent-variable perceptron''' đã được phát triển, dựa vào thuật toán structured perceptron.<ref name="lvperceptron">{{Chú thích hội nghị|author1=Xu Sun|author2=Takuya Matsuzaki|author3=Daisuke Okanohara|author4=Jun'ichi Tsujii|title=Latent Variable Perceptron Algorithm for Structured Classification|conference=IJCAI|year=2009|pages=1236–1242}}</ref> Mô hình này có thể ứng dụng trong thị giác máy, đặc biệt là nhận biết cử chỉ trong các video stream<ref name="morency">{{Chú thích sách|last1=Morency|first1=L. P.|last2=Quattoni|first2=A.|last3=Darrell|first3=T.|doi=10.1109/CVPR.2007.383299|chapter=Latent-Dynamic Discriminative Models for Continuous Gesture Recognition|title=2007 IEEE Conference on Computer Vision and Pattern Recognition|pages=1|year=2007|isbn=1-4244-1179-3|pmid=|pmc=|url=http://dspace.mit.edu/bitstream/handle/1721.1/35276/MIT-CSAIL-TR-2007-002.pdf}}</ref> và shallow parsing (phân tích cấu trúc đơn giản).<ref name="lvperceptron">{{Chú thích hội nghị|author1=Xu Sun|author2=Takuya Matsuzaki|author3=Daisuke Okanohara|author4=Jun'ichi Tsujii|title=Latent Variable Perceptron Algorithm for Structured Classification|conference=IJCAI|year=2009|pages=1236–1242}}</ref>

== Phần mềm ==
Sau đây là list các phần mềm có CRF tool.
* [http://rnnsharp.codeplex.com/ RNNSharp] {{Webarchive|url=https://web.archive.org/web/20160625074258/http://rnnsharp.codeplex.com/ |date=2016-06-25 }} CRFs dựa vào mạng nơ ron hồi quy (C#,.NET)
* [http://klcl.pku.edu.cn/member/sunxu/code.htm CRF-ADF] {{Webarchive|url=https://web.archive.org/web/20131224113826/http://klcl.pku.edu.cn/member/sunxu/code.htm |date = ngày 24 tháng 12 năm 2013}} Linear-chain CRFs với fast ADF training (C#,.NET)
* [http://github.com/zhongkaifu/CRFSharp CRFSharp] Linear-chain CRFs (C#,.NET)
* [http://vision.csd.uwo.ca/code/ GCO] CRFs dùng submodular energy functions (C++, [[MATLAB|Matlab]])
* [http://research.project-10.de/dgm DGM] CRFs (C++)
* [http://mallet.cs.umass.edu/grmm/index.php GRMM] CRFs (Java)
* [http://factorie.cs.umass.edu/ factorie] CRFs (Scala)
* [http://www.cs.ubc.ca/~murphyk/Software/CRFall.zip CRFall] CRFs (Matlab)
* [http://crf.sourceforge.net/ Sarawagi's CRF] Linear-chain CRFs (Java)
* [http://sourceforge.net/projects/hcrf/ HCRF library] Hidden-state CRFs (C++, Matlab)
* [http://accord-framework.net Accord.NET] Linear-chain CRF, HCRF and HMMs (C#,.NET)
* [http://wapiti.limsi.fr/ Wapiti] Fast linear-chain CRFs (C)<ref>T. Lavergne, O. Cappé and F. Yvon (2010).</ref>
* [http://www.chokkan.org/software/crfsuite/ CRFSuite] Fast restricted linear-chain CRFs (C)
* [http://crfpp.sourceforge.net/ CRF++] {{Webarchive|url=https://web.archive.org/web/20100421020327/http://crfpp.sourceforge.net/ |date = ngày 21 tháng 4 năm 2010}} Linear-chain CRFs (C++)
* [http://flexcrfs.sourceforge.net/ FlexCRFs] First-order and second-order Markov CRFs (C++)
* [http://hackage.haskell.org/package/crf-chain1 crf-chain1] First-order, linear-chain CRFs (Haskell)
* [http://www.cs.rochester.edu/~bhole/code/crf/ imageCRF] {{Webarchive|url=https://web.archive.org/web/20160622052053/http://www.cs.rochester.edu/~bhole/code/crf/ |date = ngày 22 tháng 6 năm 2016}} CRF dùng phân mảnh ảnh và dung lượng (C++)
* [http://mallet.cs.umass.edu/ MALLET] Linear-chain dùng phân tích cú pháp câu (Java)
* [https://pystruct.github.io/ PyStruct] Structured Learning bằng Python (Python)
* [https://github.com/p2t2/figaro Figaro] Một ngôn ngữ lập trình xác suất có thể xây dựng CRFs và mô hình đồ thị khác (Scala)
Dưới đây là một số phần mềm sử dụng CRF.
* [http://www.broadinstitute.org/annotation/conrad Conrad] {{Webarchive|url=https://web.archive.org/web/20100112222803/http://www.broadinstitute.org/annotation/conrad/ |date = ngày 12 tháng 1 năm 2010}} CRF  dự đoán gen cơ sở ([[Java (ngôn ngữ lập trình)|java]])
* [http://nlp.stanford.edu/software/CRF-NER.shtml Stanford NER] nhận biết tên vật thể(named entity recognizer) ([[Java (ngôn ngữ lập trình)|java]])
* [http://cbioc.eas.asu.edu/banner/ BANNER] {{Webarchive|url=https://web.archive.org/web/20100707042144/http://cbioc.eas.asu.edu/banner/ |date = ngày 7 tháng 7 năm 2010}} nhận biết tên vật thể (java)

== Xem thêm ==
* Hammersley–Clifford theorem
* Mô hình đồ thị
* Trường ngẫu nhiên markov
* Mô hình cực đại [[entropy]] markov (MEMM)

== Tham khảo ==
{{tham khảo|30em}}

== Đọc thêm ==
* McCallum, A.: Efficiently inducing features of Trường điều kiện ngẫu nhiên. In: ''Proc. 19th Conference on Uncertainty in Artificial Intelligence''. (2003)
* Wallach, H.M.: [http://www.cs.umass.edu/~wallach/technical_reports/wallach04conditional.pdf Trường điều kiện ngẫu nhiên: An introduction]. Technical report MS-CIS-04-21, University of Pennsylvania (2004)
* Sutton, C., McCallum, A.: An Introduction to Trường điều kiện ngẫu nhiên for Relational Learning. In "Introduction to Statistical Relational Learning". Edited by Lise Getoor and Ben Taskar. MIT Press. (2006) [http://www.cs.umass.edu/~mccallum/papers/crf-tutorial.pdf Online PDF]
* Klinger, R., Tomanek, K.: Classical Probabilistic Models and Trường điều kiện ngẫu nhiên. Algorithm Engineering Report TR07-2-013, Department of Computer Science, Dortmund University of Technology, December 2007. ISSN 1864-4503. [https://ls11-www.cs.uni-dortmund.de/_media/techreports/tr07-13.pdf Online PDF]{{Liên kết hỏng|date = ngày 25 tháng 5 năm 2021 |bot=InternetArchiveBot }}

[[Thể loại:Học máy]]