Hướng dẫn này sẽ cung cấp cho bạn lời giải thích chi tiết về các mô hình đồ họa trong lập trình R. Trước hết, chúng ta sẽ thảo luận về khái niệm mô hình đồ họa, các loại và ứng dụng của nó trong cuộc sống thực, sau đó, chúng ta sẽ nghiên cứu về tính độc lập và tách biệt có điều kiện trong đồ thị, và phân rã với đồ thị có hướng và vô hướng.
Các bài viết liên quan:
Vì vậy, chúng ta hãy bắt đầu.
R graphical Models là gì?
Mô hình đồ họa R đề cập đến một đồ thị biểu thị mối quan hệ giữa một tập hợp các biến. Bằng một tập hợp các nút (đỉnh) và các cạnh, chúng tôi thiết kế các mô hình này để kết nối các nút đó.
Xác định đồ thị G theo phương trình sau:
G = (V, E)
Nơi đây:
- V là một tập hợp hữu hạn các đỉnh hoặc nút.
- E ⊆ V × V là một tập hợp hữu hạn các cạnh, liên kết hoặc cung.
Một mô hình đồ họa mã hóa các giả định về tính độc lập có điều kiện giữa các biến. Nó đại diện cho các biến ngẫu nhiên dưới dạng các nút hoặc đỉnh và các giả định độc lập có điều kiện dưới dạng các cung bị thiếu.
Một số ví dụ thực tế về mô hình đồ họa sử dụng các nút và cạnh là:
- Road Maps – Biểu thị các giao lộ và đường phố.
- Electrical Circuits – Biểu diễn các linh kiện điện tử và các cạnh.
- Computer Networks – Đại diện cho máy tính và kết nối.
- World Wide Web – Đại diện cho các trang web và liên kết.
- Flowcharts – Biểu diễn các hộp và mũi tên.
Mô hình đồ họa R đại diện cho một lớp phân phối xác suất dưới dạng đồ thị. Chúng kết hợp sự không chắc chắn và cấu trúc logic thành một hiện tượng đáng tin cậy trong thế giới thực. Chúng cung cấp một cách hiệu quả để kết nối các dấu chấm và lập luận về các quan sát không giới hạn và các biến số sẵn có xung quanh chúng ta.
Đây là một mô hình xác suất mà đồ thị biểu thị cấu trúc phụ thuộc giữa các biến ngẫu nhiên. Chúng thường được sử dụng trong lý thuyết xác suất, thống kê, đặc biệt là thống kê Bayes và Học máy để xác định các phụ thuộc trong một miền đang nghiên cứu. Các hàm phân phối có điều kiện đại diện cho thông tin định lượng về miền ở cuối ước tính nhu cầu của nó. Cách tiếp cận này là mệt mỏi và tốn thời gian. Ví dụ: – Các miền lớn như bán lẻ có 1000 biến.
Chúng ta hãy xem trong hình ảnh x ∈ X đã cho, tư thế người được ước lượng như thế nào trong hình ảnh y ∈ Y.
Việc tính toán bắt đầu với việc ước tính các bộ phận cơ thể khác nhau, như sau.
Công thức tính, ví dụ ước tính phần đầu, yhead = (u; v; Θ) trong đó:
- (u; v) center, trong đó: (u; v) ∈ {1,…., M} X {1,…., n};
- Θ phép quay, trong đó: Θ ∈ {0, 45˚, 90˚,}};
Như được hiển thị trong hình, ước tính một bộ phân loại đầu là:
- Với bộ phân loại này, hãy kiểm tra điểm và ghi lại tất cả các vị trí trong hình.
- Lặp lại quy trình này cho tất cả các bộ phận cơ thể và lặp lại cho đến khi quét toàn bộ hình ảnh cho các bộ phân loại cơ thể khác nhau, như thể hiện trong hình trong trang trình bày sau:
Dự đoán tư thế con người chính xác nhất là:
- Để nắm bắt tính không chắc chắn của một hiện tượng được đưa ra bởi một số dữ liệu, chúng tôi sử dụng phân phối xác suất như sau:
- Trang trình bày sau đây trình bày một ví dụ về đồ thị phân phối xác suất.
- Đồ thị mô tả một biến nhị phân, là y ∈ Y = {0,1}.
- Nó có 2 giá trị và 1 bậc tự do.
Trong đồ thị này, phân phối xác suất có điều kiện là:
Các loại mô hình đồ họa R
Có hai loại mô hình đồ họa chính trong R :
- Mô hình đồ họa vô hướng [Trường ngẫu nhiên Markow (MRF)] – Trong trường hợp này của Mạng Markov, chúng dựa trên biểu đồ vô hướng. Do đó, chúng được gọi là mô hình đồ họa vô hướng.
- Mạng được hướng hoặc Bayesian – Trong trường hợp này, Mạng Bayes được dựa trên các biểu đồ có hướng. Do đó, chúng được gọi là mô hình đồ họa R có hướng.
Cả hai họ đều bao gồm các thuộc tính của thừa số hóa và tính độc lập. Chúng khác nhau về tập hợp các tính chất độc lập mà chúng có thể mã hóa và sự phân bố nhân tử mà chúng tạo ra.
Mô hình đồ họa R vô hướng
Đồ thị vô hướng là đồ thị có các cạnh không có bất kỳ dạng định hướng nào. Trong đồ thị này, cạnh của (a, b) trùng với cạnh (b, a). Điều này có nghĩa là chúng không có thứ tự nhưng có hai bộ đỉnh. Số cạnh lớn nhất trong một đồ thị vô hướng không có vòng lặp tự trị là n (n – 1) / 2 .
Một đồ thị G là gián tiếp nếu ∀A, B ∈ V: (A, B) ∈ E ⇒ (B, A) ∈ E.
Xác định hai cặp có thứ tự (A, B) và (B, A) và chỉ biểu diễn bằng một cạnh vô hướng.
Một loại mô hình nằm trên một đồ thị vô hướng là Mạng Markov, hay còn được gọi là Trường ngẫu nhiên Markov.
Các mô hình này có thể được sử dụng để mô hình hóa nhiều hiện tượng mà người ta không thể mô tả một hướng cho sự tương tác giữa các biến. Với sự trợ giúp của đồ thị vô hướng, chúng ta có thể có một quan điểm đơn giản hơn nhiều về mô hình có hướng. Họ chia sẻ các điều khoản về cấu trúc độc lập cũng như nhiệm vụ suy luận.
MRF là một đồ thị độc lập có điều kiện vô hướng của một phân phối xác suất. Phân phối xác suất dọc theo họ các hàm không âm M bao gồm phân tích thừa được tạo bởi đồ thị.
Giả sử rằng G = (V, E).
Ở đây, tập đỉnh V = {0,1,2,3,4,5,6} và tập cạnh E = {(0,2), (0,4), (0,5), (1,0) , (2,1), (2,5), (3,1), (3,6), (4,0), (4,5), (6,3), (6,5)}.
Thuật ngữ đồ thị vô hướng
Hãy cho chúng tôi xem một số thuật ngữ liên quan đến đồ thị vô hướng:
1. Nút lân cận – Một nút B ∈ V tiếp giáp với một nút A ∈ V hoặc một lân cận của A.
Nếu và chỉ khi có một cạnh giữa chúng thì (A, B) ∈ E.
Hai nút kề nhau nếu chúng có chung một cạnh trong trường hợp đó cạnh chung là nối hai đỉnh. Hai điểm cuối của một cạnh cũng được cho là cạnh nhau.
2. Tập các lân cận – Tập tất cả các lân cận của A là các lân cận (A) = {B ∈ V | (A, B) ∈ E}. Các lân cận của tập hợp (A) đôi khi còn được gọi là biên của A.
3. Bậc của nút – Bậc của nút A (số cạnh tới) là deg (A) = | hàng xóm (A) |. Bậc của một nút là số cạnh kết nối với nó, trong đó một cạnh kết nối với nút ở cả hai đầu (một vòng lặp). Đếm cạnh hai lần. Mức độ của một đỉnh là thước đo mức độ liền kề ngay lập tức.
4. Đóng của nút – Đóng của nút A là biên của A cùng với chính A. close (A) = hàng xóm (A) ∪ {A}.
5. Các nút liên thông – Hai nút phân biệt A, B ∈ V được gọi là liên thông trong G nếu và chỉ khi tồn tại một dãy C1 ,. ., Ck, k ≥ 2 , của các nút khác biệt, được gọi là đường đi, với C1 = A, Ck = B và ∀i, 1 ≤ i <k: (Ci, Ci + 1) ∈ E.
6. Cây – Một đồ thị vô hướng được kết nối đơn lẻ hoặc một cây nếu và chỉ kết nối nếu bất kỳ cặp nút riêng biệt nào bằng chính xác một đường đi. Cây đóng vai trò của một đồ thị liên thông không chứa chu trình. Nối 2 đỉnh cuối bằng đúng 1 đường đơn.
7. Đồ thị con – Đồ thị con là một tập hợp con của các cạnh của đồ thị (và các đỉnh liên quan) tạo thành một đồ thị. Đồ thị vô hướng GX = (X, EX) được gọi là đồ thị con của G (do X quy nạp) nếu và chỉ khi X ⊆ V và EX = (X × X) ∩ E, nghĩa là nếu nó chứa một tập con các nút trong G và tất cả các cạnh tương ứng.
8. Đồ thị hoàn chỉnh – Đồ thị hoàn chỉnh Kn bậc n là một đồ thị đơn giản có n đỉnh trong đó mọi đỉnh đều cạnh nhau. Một đồ thị vô hướng G = (V, E) là hoàn chỉnh nếu tập các cạnh của nó là đầy đủ, nghĩa là, nếu tất cả các cạnh có thể có, hoặc nếu: E = V × V – {(A, A) | A ∈ V}.
9. Clique – Một clique trong đồ thị là một tập hợp các đỉnh kề nhau theo từng cặp. Hai đồ thị con của clique và một đồ thị con hoàn chỉnh được sử dụng thay thế cho nhau vì bản thân một đồ thị con của một clique là một đồ thị con hoàn chỉnh. Một đồ thị con hoàn chỉnh được gọi là một clique. Một nhóm là cực đại nếu nó không phải là một đồ thị con của một nhóm lớn hơn, nghĩa là một nhóm có nhiều nút hơn.
Mô hình đồ họa R được hướng dẫn
Đồ thị có hướng hoặc đồ thị là một cặp có thứ tự D = (V, A) với:
- Tập hợp V có các phần tử được gọi là đỉnh hoặc nút, và
- Một tập hợp các cặp đỉnh có thứ tự, được gọi là cung, cạnh có hướng hoặc mũi tên.
Giả sử chúng ta có một cạnh (A, B) và hướng nó về phía B từ A.
Các mô hình đồ họa R có hướng còn được gọi là mạng Bayes hoặc lưới Bayes (BN).
Mạng Bayes là một đồ thị độc lập có điều kiện có hướng của phân phối xác suất. Nó cùng với họ các xác suất có điều kiện của quá trình thừa số hóa do đồ thị mang lại.
Một mạng Bayes, mạng Bayes, mạng niềm tin, mô hình Bayes (ian) là một mô hình đồ họa xác suất. Nó đại diện cho một tập hợp các biến ngẫu nhiên và các phụ thuộc có điều kiện của chúng thông qua biểu đồ xoay chiều có hướng (DAG). Ví dụ – Nó có thể đại diện cho các mối quan hệ xác suất giữa các bệnh và các triệu chứng. Với các triệu chứng, mạng có thể được sử dụng để tính toán xác suất của sự hiện diện của các bệnh khác nhau.
Giả sử, tập đỉnh V = {0,1,2,3,4,5,6} và tập cạnh E = {(0,2), (0,4), (0,5), (1,0) , (2,1), (2,5), (3,1), (3,6), (4,0), (4,5), (6,3), (6,5)}. Chúng ta có thể tạo một đồ thị có hướng từ nó.
Đã đến lúc nắm vững khái niệm về Mạng Bayes trong R
Các thuật ngữ đồ thị có hướng
Hãy cho chúng tôi xem một số thuật ngữ liên quan đến biểu đồ được hướng dẫn:
- Lưu ý cha và con – Cho một cạnh, nút mà cạnh đó trỏ đến được gọi là cha và nút mà cạnh trỏ đến được gọi là con. Một nút B ∈ V được gọi là nút cha của nút A ∈ V. A được gọi là nút con của B, nếu có một cạnh hướng từ B đến A, nghĩa là, nếu và chỉ khi (B, A) ∈ E.
B được gọi là liền kề với A, nếu nó là cha hoặc con của A và biểu thị tập hợp tất cả cha mẹ của một nút A:
Parent (A) = {B ∈ V | (B, A) ∈ E}
Ký hiệu nhóm con của nó:
Child (A) = {B ∈ V | (A, B) ∈ E}
- Các nút liên thông D – Hai nút A, B ∈ V được gọi là liên thông d trong G, nếu có một chuỗi C1,., Ck, k ≥ 2, gồm các nút khác nhau, được gọi là đường có hướng, với C1 = A, Ck = B và ∀i, 1 ≤ i <k: (Ci, Ci + 1) ∈ E.
x và y được nối d nếu có một đường đi không bị chặn giữa chúng.
Ví dụ:
Đồ thị này chứa một máy va chạm, tại t. Bỏ chặn đường dẫn xrst, do đó x và t được kết nối với nhau. Đường dẫn cũng vậy, do đó t và y được nối với d, cũng như các cặp u andy, t và v, t, và u, x và s, v.v. Tuy nhiên, x và y không nối d; Không có cách nào để vạch ra một đường đi từ x đến y mà không đi qua máy va chạm tại t.
- Các nút được kết nối – Hai nút A, B ∈ V được gọi là kết nối trong G, nếu và chỉ khi có một chuỗi C1 ,. ., Ck, k ≥ 2, của các nút khác biệt, được gọi là đường đi, với C1 = A, Ck = B và ∀i, 1 ≤ i <k: (Ci, Ci + 1) ∈ E ∨ (Ci + 1, Ci) ∈ E
- Polytree – Một đồ thị xoay chiều có hướng được gọi là liên thông đơn lẻ hoặc polytree nếu mỗi cặp nút riêng biệt được nối với nhau bằng đúng một đường dẫn.
- Cây – Một đồ thị xoay chiều có hướng được gọi là cây (có hướng) nếu nó là một cây đa và chính xác một nút (nút gốc) không có cha mẹ.
Độc lập có điều kiện trong đồ thị
Trong trường hợp này, mỗi đỉnh hoặc nút đại diện cho một thuộc tính để mô tả miền trong nghiên cứu. Mỗi cạnh thể hiện sự phụ thuộc trực tiếp giữa hai thuộc tính.
Một mô hình đồ họa chịu trách nhiệm vẽ một mối quan hệ có độc lập có điều kiện giữa một số biến từ các dạng tham số chuẩn của chúng.
Về nguyên tắc, tất cả các bộ phận phụ thuộc vào nhau. Biết đâu là đầu sẽ đặt ra những ràng buộc đối với nơi có thể của chân. Giả sử bạn muốn biết vị trí của chân trái có phụ thuộc vào vị trí của thân mà bạn biết vị trí của chân trái hay không. Độc lập có điều kiện ở trạng thái đồ thị mà nó không.
Xác định tính độc lập có điều kiện là:
Hoặc là
Ở đây, (· ⊥⊥ · | ·) mô tả mối quan hệ ba vị trí.
Một số ví dụ thực tế về tính độc lập có điều kiện như sau:
- Chạy quá tốc độ tốt ⊥⊥ loại ô tô | tốc độ, vận tốc
- Ung thư phổi ⊥⊥ răng vàng | người hút thuốc
Độc lập có điều kiện và phân tách trong đồ thị
Liên kết sự độc lập có điều kiện với sự phân tách trong đồ thị. Ở đây, ‘phân tách’ phụ thuộc vào việc biểu đồ là vô hướng hay có hướng:
1. Đồ thị vô hướng
- G = (V, E) trong đó, X, Y và Z là ba tập con rời rạc của các nút.
- Nếu tất cả các đường dẫn từ một nút trong X đến một nút trong Y chứa một nút trong Z, thì nó phân tách X và Y trong G, được viết là <X | Z | Y> G.
- Một đường dẫn có chứa một nút trong Z được gọi là bị chặn (bởi Z), ngược lại, nó được gọi là hoạt động.
- Vì vậy, tách biệt có nghĩa là tất cả các đường dẫn nhận được một khối.
2. Đồ thị hướng
- G = (V, E) X, Y và Z là ba tập con rời rạc của các nút.
- Nếu có một đường đi không bị chặn giữa X và Y, chúng được nối với nhau.
- X và Y được kết nối d và được điều kiện hóa trên tập Z các nút nếu có một đường cây va chạm giữa X và Y đi qua không có thành viên nào của Z. Nếu không có đường dẫn cây va chạm như vậy, thì X và Y là d -phân cách bởi Z. Nói cách khác, Z chặn mọi con đường giữa X và Y.
- Một đường dẫn thỏa mãn các điều kiện trên được gọi là hoạt động, nếu không, chúng ta có thể nói bị chặn (bởi Z). Như vậy, tách biệt có nghĩa là tất cả các con đường đều bị chặn.
- Z d-tách X và Y trong G, được viết <X | Z | Y> G, nếu không có đường dẫn từ một nút trong X đến một nút trong Y cùng với hai điều kiện sau:
- Mọi nút có các cạnh hội tụ (từ nút tiền nhiệm và nút kế nhiệm của nó trên đường dẫn) nằm trong Z hoặc có một nút con trong Z
- Mọi nút khác không nằm trong Z.
Xem thêm Phân khối khóa (key) trong mã hóa
Phân rã hoặc thừa số hóa trong đồ thị
Sự độc lập có điều kiện trong đồ thị chỉ là một con đường để tìm ra sự phân rã của một phân phối.
Để xác định nó cho một phân phối nhất định cũng giống như xác định các điều khoản cần thiết trong một phân tích phân phối.
Tìm một đồ thị độc lập có điều kiện tối thiểu cũng giống như việc tìm ra phép phân rã tốt nhất.
Bây giờ chúng ta sẽ nghiên cứu những điều sau:
- Phân tích hoặc thừa số hóa wrt đồ thị vô hướng.
- Đồ thị có hướng wrt phân tích hoặc thừa số hóa.
Đồ thị phân rã và vô hướng
- Một phân phối xác suất trên một tập hợp các thuộc tính U được gọi. Nó cũng có thể gọi là thừa số đối với đồ thị vô hướng G = (U, E) và viết nó dưới dạng tích của các hàm không âm trên các mặt cực đại của G.
- M là một họ các tập con của các thuộc tính, sao cho các đồ thị con của G sinh ra bởi các tập M ∈ M là các nhóm cực đại của G.
- Khi đó, các hàm φM: EM → IR + 0, M∈M:
- Phân phối khả năng πU trên U được gọi là có thể phân tách đối với đồ thị vô hướng G = (U, E) nếu nó được viết dưới dạng phân bố khả năng biên nhỏ nhất trên các vùng cực đại của G, nghĩa là, nếu:
Hình thể hiện sự phân rã / phân tích nhân tử thành bốn số hạng cho một đồ thị vô hướng:
4 số hạng này tương ứng với 4 khối cực đại được tạo ra bởi bốn tập hợp {A1, A2, A3}, {A3, A5, A6}, {A2, A4} và {A4, A6}.
Đồ thị phân rã và có hướng
- Một phân phối xác suất pu trên một tập thuộc tính U được gọi. Nó cũng có thể gọi là thừa số đối với đồ thị xoay chiều có hướng G = (U, E). Nếu nó được viết dưới dạng tích của các xác suất có điều kiện của các thuộc tính được cung cấp cho cha mẹ của chúng trong G, nếu:
- Phân phối khả năng πU trên U được gọi là khả vi đối với đồ thị xoay chiều có hướng G = (U, E). Nếu nó được viết dưới dạng xác suất có điều kiện nhỏ nhất của các thuộc tính được cung cấp cho cha mẹ của chúng trong G, nếu:
- Hình thể hiện sự phân rã / phân tích nhân tử thành bốn số hạng cho một biểu đồ có hướng:
Bản tóm tắt
Chúng ta đã thảo luận về toàn bộ khái niệm về mô hình đồ họa R với các kiểu của nó và tìm hiểu về tính độc lập và phân rã có điều kiện trong đồ thị.
