Thành viên:Chúc Thành/Lan truyền độ tin cậy

(Đang dịch từ en:Belief propagation)

Lan truyền độ tin cậy là một thuật toán trong họ thuật toán truyền thông điệp thực hiện suy luận thống kê trên các mô hình đồ họa (graphical model), chẳng hạn các mạng Beyesian (en:Bayesian network) và trường ngẫu nhiên Markov (en:Markov random filed). Thuật toán này tính phân bố biên duyên (en: marginal distribution) cho mỗi đỉnh không quan sát được (đỉnh ẩn), lấy trong điều kiện của các đỉnh được quan sát. Thuật toán lan truyền độ tin cậy dùng trong lĩnh vực trí tuệ nhân tạo và lý thuyết thông tin đã cho nhiều thành công, trong đó có các low-density parity-check codes, mã Turbo en:turbo code, xấp xỷ năng lượng tự do và lý thuyết khả thi (en:satisfiability). /(đang kiểm tra link)/

Thuật toán được đề xuất bởi Judea Pearl năm 1982,, người đã phát triển thuật toán trên đồ thị kiểu cây, sau đó mở rộng sang các đồ thị cây phức (polytree). Nó cũng được chứng tỏ là thuật toán xáp xỉ hữu ích với các đồ thị tổng quát.

Giả sử X=(X_v) là một tập hợp các biến ngẫu nhiên rời rạc với hàm phân bố đồng thời joint p, phân bố biên duyên của biến X_i đơn giản là tổng của p lấy theo tất cả các tập giá trị của biến khác:

$p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ').$

Tuy nhiên biểu thức này nhanh chóng trở nên cồng kềnh: giả sử ta có 100 biến số nhị phân, khi đó ta phải cộng 2⁹⁹ ≈ 6.338 × 10²⁹ các giá trị khả dĩ. Bằng cách sử dụng cấu trúc đồ họa, thuật toán lan truyền độ tin cậy cho phép phép lấy điều kiện đó trở nên hiệu quả hơn về mặt tính toán.

Mô tả thuật toán tổng và tích

Thuật toán lan truyền độ tin cậy hoạt động trên một đồ thị nhân tử (en:factor graph): một đồ thị hai thành phần chứa các nút tương ứng với các biến V và nhân tử (factor) U, cùng với cách cạnh nối các biến và tác nhân. Ta có thể viết hàm phân bố đồng thời (rời rạc)

$p(\mathbf {x} )=\prod _{u\in U}f_{u}(\mathbf {x} _{u})$

trong đó x_u là vector của các nút lân cận tương ứng với các biến của một nhân tử. Một mạng Bayesian (en:Bayesian network) bất kỳ hoặc một trường Markov ngẫu nhiên (en:Markov random field) có thể biểu diện bằng một đồ thị với các nhân tử.

Thuật toán hoạt động bằng cách truyền các hàm biến thực gọi là "thông điệp" dọc theo các cạnh giữa các nút. Các thông điệp này chứa đựng thông tin mà một biến ảnh hưởng đến biến kia. Có hai dạng của thông điệp:

• Một thông điệp từ một biến v đến một tác nhân u là tích của các thông điệp từ tất cả các nhân tử lân cận (trừ nhân tử nhận; nói các khác tác nhân nhận truyền thông điệp đơn vị, 1).

$\mu _{v\to u}(x_{v})=\prod _{u^{*}\in N(v)\setminus \{u\}}\mu _{u^{*}\to v}(x_{v}).$

trong đó N(v) là tập của các tác nhân lân cận với v. Nếu $N(v)\setminus \{u\}$ rỗng, $\mu _{v\to u}(x_{v})$ sẽ được dùng bởi phân bố đều.

• Một thông điệp từ một tác nhân u đến một biến v là tích của các nút nhân tử với thông điệp từ tất cả các nút khác, lấy điều kiện x_v:

$\mu _{u\to v}(x_{v})=\sum _{\mathbf {x} '_{u}:x'_{v}=x_{v}}f_{u}(\mathbf {x} '_{u})\prod _{v^{*}\in N(u)\setminus \{v\}}\mu _{v^{*}\to u}(x'_{u}).$

trong đó N(u) là tập các (biến) lân cận của u. Nếu $N(u)\setminus \{v\}$ là tập rỗng thì $\mu _{u\to v}(x_{v})=f_{u}(x_{v})$.

Tên của thuật toán thể hiện rõ ràng trong các công thức trên: phép lấy điều kiện toàn bộ được thu về phép lấy tổng của các tích đơn giản hơn các số hạng xuất hiện trong phân bố đồng thời đầy đủ.

Thuật toán chính xác trên các cây

Trường hợp đơn giản nhất của thuật toán là khi đồ thị nhân tử có dạng cây (lý thuyết đồ thị): các phép lấy điều kiện của xác suất trở nên chính xác và kết thúc sau hai bước.

Trước khi khởi động, đồ thị được định hướng bằng cách xác định một "gốc"; tất cả các nút không phải gốc được nối với chỉ một nút khác được gọi là "lá".

Trong bước đầu tiên, thông điệp truyền vào: bắt đầu từ các lá, mối nút truyền một thông điệp dọc theo cạnh (duy nhất) về phía gốc. Cấu trúc cây của đồ thị đảm bảo khả năng thu được các thông điệp từ tất cả cả các nút liên kết với nút trước khi nút đó truyền thông điệp. Quá trình này dừng khi gốc nhận được thông điệp từ tất cả các nút liên kết với nó.

Bước thứ hai, truyền thông điệp ra: bắt đầu từ gốc, các thông điệp được truyền theo hướng ngược trở lại. Thuật toán hoàn thành khi tất cả các lá đã nhận được thông điệp gửi đến chúng.

Khi hoàn thành, phân bố xác suất biên duyên là tích của tất cả các thông điệp của các nút nhân tử liên kết:

$p_{X_{v}}(x_{v})=\prod _{u\in N(v)}\mu _{u\to v}(x_{v}).$

Tương tự như vậy, phân bố xác suất biên duyên của tập các biến thuộc về một nút nhân tử là tích của nhân tử với thông điệp từ các biến:

$p_{X_{u}}(\mathbf {x} _{u})=f_{u}(\mathbf {x} _{u})\prod _{v\in N(u)}\mu _{v\to u}(x_{u}).$

Các kết luận này có thể chứng minh bằng phép quy nạp toán học.

Thuật toán xấp xỷ trên đồ thi tổng quát

Curiously, nearly the same algorithm is used in general graphs. The algorithm is then sometimes called "loopy" belief propagation, because graphs typically contain cycles, or loops. The procedure must be adjusted slightly because graphs might not contain any leaves. Instead, one initializes all variable messages to 1 and uses the same message definitions above, updating all messages at every iteration (although messages coming from known leaves or tree-structured subgraphs may no longer need updating after sufficient iterations). It is easy to show that in a tree, the message definitions of this modified procedure will converge to the set of message definitions given above within a number of iterations equal to the diameter of the tree.

Điều lý thú là thuật toán dùng cho đồ thị tổng quát gần như giống hệt. Thuật toán trong tường hợp này thường được gọi là lan truyền tin cậy vòng, bởi vì các đồ thị nói chung có chứa các vòng (lý thuyết đồ thị).

The precise conditions under which loopy belief propagation will converge are still not well understood; it is known that graphs containing a single loop will converge to a correct solution. Several sufficient (but not necessary) conditions for convergence of loopy belief propagation to a unique fixed point exist. There exist graphs which will fail to converge, or which will oscillate between multiple states over repeated iterations. Techniques like EXIT charts can provide an approximate visualisation of the progress of belief propagation and an approximate test for convergence.

There are other approximate methods for marginalization including variational methods and Monte Carlo methods.

One method of exact marginalization in general graphs is called the junction tree algorithm, which is simply belief propagation on a modified graph guaranteed to be a tree. The basic premise is to eliminate cycles by clustering them into single nodes.