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ị $G=(V,E)$ sao cho

${\boldsymbol {Y}}=({\boldsymbol {Y}}_{v})_{v\in V}$,

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

Ta gọi $({\boldsymbol {X}},{\boldsymbol {Y}})$ là một conditional random field khi biến ${\boldsymbol {Y}}_{v}$, điều kiện ${\boldsymbol {X}}$, tuân theo tính chất Markov property đối với đồ thị: $p({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},{\boldsymbol {Y}}_{w},w\neq v)=p({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},{\boldsymbol {Y}}_{w},w\sim v)$, ${\mathit {w}}\sim v$ nghĩa là  $w$ và $v$ là hai đỉnh kề trong đồ thị $G$.

Đ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 ${\displaystyle }$ và ${\displaystyle }$, mẫu quan sát và biến đầu ra, respectively; phân phối có điều kiện ${\displaystyle }$ đượ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. 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 Viterbi 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ố $\theta$ ta thường dùng maximum likelihood để học $p(Y_{i}|X_{i};\theta )$. 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 ${\displaystyle }$ được biểu diễn bằng chuỗi những mẫu quan sát và ${\displaystyle }$ là những biến chưa biết phải được suy ra từ những mẫu quan sát. ${\displaystyle }$ được sắp xếp thành một chuỗi, với những cạnh giữa mỗi cặp ${\displaystyle }$ và ${\displaystyle }$. Và cũng có những miêu tả cơ bản cho ${\displaystyle }$ 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 ${\displaystyle }$ 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 ${\displaystyle }$ khi cho trước $X$.
• inference, tìm ra nhãn có khả năng nhất khi cho trước $X$.

Những lệ thuộc có điều kiện của mỗi ${\displaystyle }$ trên ${\displaystyle }$ được xác định qua một chuỗi các hàm thuộc tính (feature function) có dạng ${\displaystyle }$ ${\displaystyle }$. 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 ${\displaystyle }$.

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 ${\displaystyle }$ ở 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 ${\displaystyle }$ phụ thuộc vào ${\displaystyle }$  biến trước nó ${\displaystyle }$. Huấn luyện và inference chỉ thực hiện được cho giá trị nhỏ của ${\displaystyle }$ (như o ≤ 5), vì độ phức tạp tính toán tăng theo hàm mũ của ${\displaystyle }$ . 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 ${\displaystyle }$. 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 ${\displaystyle }$ 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:

${\displaystyle }$

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 Lưu trữ 2016-06-25 tại Wayback Machine CRFs dựa vào mạng nơ ron hồi quy (C#,.NET)
• CRF-ADF Lưu trữ 2013-12-24 tại Wayback Machine 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++ Lưu trữ 2010-04-21 tại Wayback Machine Linear-chain CRFs (C++)
• FlexCRFs First-order and second-order Markov CRFs (C++)
• crf-chain1 First-order, linear-chain CRFs (Haskell)
• imageCRF Lưu trữ 2016-06-22 tại Wayback Machine 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 Lưu trữ 2010-01-12 tại Wayback Machine CRF  dự đoán gen cơ sở (java)
• Stanford NER nhận biết tên vật thể(named entity recognizer) (java)
• BANNER Lưu trữ 2010-07-07 tại Wayback Machine 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