Trường điều kiện ngẫu nhiên

Trường điều kiện ngẫu nhiên (CRFs) là một dạng của Mô hình xác suất  thường được áp dụng cho Dự đoán cấu trúc trong 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
và trong Thị giác máy tính.
Đặc biệt, CRFs có thể ứng dụng trong phân tích cấu trúc câu, nhận diện những thực thể tên trong văn bản, tìm gen và peptide có vai trò quan trọng trong một khu vực tìm kiếm,
trong số ứng dụng khác nó cũng liên quan tới 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 định nghĩa CRF trên một mẫu quan sát và biến ngẫu nhiên như sau:Cho một đồ thị formula_1 sao cho

formula_2,

Ta gọi formula_5 là một conditional random field khi biến formula_6, điều kiện formula_7, tuân theo tính chất Markov property đối với đồ thị: formula_8, formula_9 nghĩa là  formula_10 và formula_11 là hai đỉnh kề trong đồ thị formula_4.
Đ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 formula_13 ta thường dùng maximum likelihood để học formula_14. 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. 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 formula_15.
- "inference", tìm ra nhãn có khả năng nhất khi cho trước formula_16.
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), 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 />. 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:
Nó tìm ra cấu trúc latent giữa mẫu quan sát và nhãn. 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. 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 và shallow parsing (phân tích cấu trúc đơn giản).

== Phần mềm ==
Sau đây là list các phần mềm có CRF tool.
- RNNSharp CRFs dựa vào mạng nơ ron hồi quy (C#.NET)
- CRF-ADF Linear-chain CRFs với fast ADF training (C#.NET)
- CRFSharp Linear-chain CRFs (C#.NET)
- GCO CRFs dùng submodular energy functions (C++, Matlab)
- DGM CRFs (C++)
- GRMM CRFs (Java)
- factorie CRFs (Scala)
- CRFall CRFs (Matlab)
- Sarawagi's CRF Linear-chain CRFs (Java)
- HCRF library Hidden-state CRFs (C++, Matlab)
- Accord.NET Linear-chain CRF, HCRF and HMMs (C#.NET)
- Wapiti Fast linear-chain CRFs (C)
- CRFSuite Fast restricted linear-chain CRFs (C)
- CRF++ Linear-chain CRFs (C++)
- FlexCRFs First-order and second-order Markov CRFs (C++)
- crf-chain1 First-order, linear-chain CRFs (Haskell)
- imageCRF CRF dùng phân mảnh ảnh và dung lượng (C++)
- MALLET Linear-chain dùng phân tích cú pháp câu (Java)
- PyStruct Structured Learning bằng Python (Python)
- 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.
- Conrad CRF  dự đoán gen cơ sở (java)
- Stanford NER nhận biết tên vật thể(named entity recognizer) (java)
- BANNER 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)

== Đọ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.: 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) 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. Online PDF