Đề tài Chứng minh một số luật trong lập luận theo xác suất khoảng

Mục lục Chứng minh một số luật trong lập luận theo xác suất khoảng 1. Giới thiệu lập luận theo xác suất 1.1. Giới thiệu Xác suất đóng một vai trò quan trọng trong việc chúng ta nhìn nhận và hiểu biết về thế giới, và trong cái cách mà chúng ta lập luận về chính thế giới chúng ta đang tồn tại. Thông tin xác suất thường được sử dụng trong các quyết định được đưa ra một cách tự động (không có sự can thiệp của con người) bởi các chương trình máy tính. Do đó, các hệ thống lập luận tự động hóa cần biết cách lập luận như thế nào với thông tin xác suất. Lý thuyết xác suất là lý thuyết được chấp nhận rộng rãi nhất cho việc lập luận về sự may rủi và sự không chắc chắn. Bởi vì các chương trình logic là một công thức tự nhiên để thiết kế các hệ chuyên gia dựa trên quy tắc, nên việc chúng cần có khả năng lập luận với thông tin xác suất là rất quan trọng. Chúng ta cũng cần phải thiết kế một mô hình trong đó thông tin xác suất có thể được diễn đạt một cách dễ dàng. Xác suất sự thật của một mệnh đề được cho bởi một số thực trong khoảng đơn vị [0, 1]. Tuy nhiên, không giống như logic thông thường, xác suất sự thật (được đo bởi một số thực) của một mệnh đề phức hợp không được diễn đạt một cách chung chung như là một hàm xác suất chân lý của các thành phần của nó, nhưng thay vào đó là các khoảng đóng của các giá trị chân lý. 1.2. Hướng tiếp cận không gian xác suất của Nilsson Không gian xác suất của Nilsson là một sự phát sinh ngữ nghĩa của logic bình thường để có được một logic xác suất. Ở đây chúng ta quan tâm hai ý tưởng thiết yếu: xác suất sự thật của một mệnh đề được xác định bởi một phân phối xác suất trên những lớp các thế giới có thể có được định nghĩa thích hợp; và tại cùng một thời điểm, xác suất sự thật này của một mệnh đề (phức hợp) được cho luôn có thể được định nghĩa một cách tương đối đối với bất kỳ tập mệnh đề nào, không nhất thiết phải là các thành phần của nó. Ví dụ. Cho các biểu thức logic sau: {, , }. Làm cách nào để tính được xác suất sự thật của mệnh đề (B®C)®A? 1.3. Hướng tiếp cận logic xác suất của Subrahmanian Hướng tiếp cận của Subrahmanian đề cập đến ba điểm: Sự đề xuất một ngôn ngữ lập trình logic và chương trình logic xác suất. Sự mô tả ngữ nghĩa của một ngôn ngữ lập trình logic, chương trình logic xác suất. Các mối quan hệ giữa lý thuyết xác suất, lý thuyết mô hình, lý thuyết điểm bất động và lý thuyết chứng minh cho những ngôn ngữ như thế. Ví dụ. Cho một cơ sở tri thức sau: ®A[0.5, 1]; ®B[0, 1]; ®C[0, 1]; ®D[0.9, 1]; ®E[0, 1]; ®G[1, 1]; ®H[0, 1]; A[1, 1]®C[0.85, 0.95]; C[0.8, 1]®B[1, 1]; G[1, 1]ÙD[0.85, 1]®C[0.8, 0.95]; H[1, 1]ÙE[0.75, 1]®C[0.85, 1]; Làm cách nào để tính được xác suất của C? 2. Một mô hình không gian xác suất cho lập luận theo xác suất Trong phần này chúng ta sẽ tìm hiểu một mô hình không gian xác suất cho việc lập luật theo xác suất, từ đó sẽ áp dụng mô hình này để chứng minh một số luật trong số 28 luật nền tảng của lập luận theo xác suất khoảng. 2.1. Thế giới có thể có (possible worlds) Các thế giới có thể có có thể được xem như là không gian xác suất. Ví dụ. Cho các biểu thức logic sau: {, , }, trong đó được hiểu là xác suất của A là 0.5. Σ = {S1=A, S2=(AÙB), S3= A®C} là tập các mệnh đề. £ = {A, B, C} là tập các biến định đề / nguyên tử trong Σ. Có 23 vector ba-thành-phần boolean biểu diễn từ (0, 0, 0) đến (1, 1, 1). Mỗi bộ ba-thành-phần được gọi là thế giới có thể có cho các mệnh đề trong Σ. Θ1=(A, B, C); Θ2=(A, -B, C); Θ3=(A, B, -C); Θ4=(-A, B, C); Θ5=(-A, -B, C); Θ6=(-A, B, -C); Θ7=(A, -B, -C); Θ8=(-A, -B, -C). Ma trận V biểu diễn các vector chân trị của các mệnh đề trong Σ: Θ1 Θ2 Θ3 Θ4 Θ5 Θ6 Θ7 Θ8 S1 1 1 1 0 0 0 1 0 S2 1 0 1 0 0 0 0 0 S3 1 1 0 1 1 1 0 1 Trong trường hợp này chúng ta có 5 vector chân trị Σ-consistent khác nhau cho các mệnh đề trong Σ, mà chúng là các cột của ma trận U sau đây: w1 w2 w3 w4 w5 S1 1 1 1 0 1 S2 1 0 1 0 0 S3 1 1 0 1 0 Θ4, Θ5, Θ6 và Θ8 được gọi là Σ-tương-đương. Mỗi lớp Σ-tương-đương sẽ tương ứng với một vector Σ-consistent. Không gian xác suất W = {w1, w2, w3, w4, w5}. Chúng ta nói rằng wi |= s nếu s thỏa thế giới có thể có wi. Ví dụ, S2 thỏa trong w1 và w3. 2.2. Xác suất mệnh đề dựa trên các thế giới có thể có Không gian xác suất của các thế giới có thể có W = {w1, w2, w3, w4, w5}. Phân phối xác suất π(.) sao cho Σiπ(wi) = 1. Các phân phối xác suất mở rộng π(.) cho các mệnh đề: π(S) = Σi{π(wi) | wi |= s} Ví dụ, π(S3) = π(w1) + π(w2) + π(w4). 2.3. Lập luận theo xác suất đơn trị - hướng tiếp cận không gian xác suất của Nilsson Thuật toán (SVPR) Cho một cơ sở tri thức: B = { | i = 1..m}. Giả sử S = Sm. Bước 1. Xác định ma trận chân trị. Bước 2. Xác định ma trận thế giới có thể có Um,k. Đặt U* là ma trận thu được từ U bằng cách loại bỏ hàng cuối cùng u tương ứng với S và thêm vào hàng đầu tiên gồm các giá trị 1. Đặt p* là vector (1, p1, p2, p3, …, pm-1). Bước 3. Xác định khoảng chân trị [a, b] cho phép nối S bằng cách giải các bài toán quy hoạch tuyến tính sau: LP1: a = maxπ(u, π) LP2: b = minπ(u, π) trong đó U*π = p*. Ví dụ. Cho các biểu thức logic sau: {, , }. Làm cách nào để tính xác suất π(C®(AÚB))? Định nghĩa: Σ’ = {S1=A, S2=(AÙB), S3=A®C, S4=C®(AÚB)}. £’ = {A, B, C}. Bước 1. Xác định ma trận chân trị V’. Θ1 Θ2 Θ3 Θ4 Θ5 Θ6 Θ7 Θ8 S1 1 1 1 0 0 0 1 0 S2 1 0 1 0 0 0 0 0 S3 1 1 0 1 1 1 0 1 S4 1 1 1 1 0 1 1 1 Bước 2. Ma trận thế giới có thể có U’. w1 w2 w3 w4 w5 w6 S1 1 1 1 0 0 1 S2 1 0 1 0 0 0 S3 1 1 0 1 1 0 S4 1 1 1 1 0 1 Θ4, Θ6 và Θ8 là Σ-tương-đương. Không gian xác suất W = {w1, w2, w3, w4, w5, w6}. Bước 3. Xác định phân phối xác suất π(.) sao cho Σiπ(wi) = Σiπi = 1 và Đối với S1 π1 + π2 + π3 + π6 = 0.8 Đối với S2 π1 + π3 = 0.4 Đối với S3 π1 + π2 + π4 + π5 = 0.6 Bước 4. Xác định xác suất π(S4) = π1 + π2 + π3 + π4 + π6. Ví dụ, π1 = 0.2, π2 = 0.2, π3 = 0.2, π4 = 0.1, π5 = 0.1, π6 = 0.2. Do đó, π(S4) = π1 + π2 + π3 + π4 + π6 = 0.9. Quả thật, π(S4) phải được chứa trong một khoảng [a, b]. Và chúng ta phải xác định khoảng này. 2.4. Lập luận theo xác suất khoảng – hướng tiếp cận không gian xác suất của Nilsson Thuật toán (IVPR) Thuật toán này hầu như giống như thuật toán SVPR. Cho một cơ sở tri thức: B = { | i = 1..m}. Giả sử S = Sm. Đặt a* là vector (1, a1, a2, a3, …, am). Đặt b* là vector (1, b1, b2, b3, …, bm). Bước 1. Xác định ma trận chân trị. Bước 2. Xác định ma trận thế giới có thể có Um,k sau đó là U*. Bước 3. Xác định khoảng chân trị I=[a, b] cho phép nối S bằng cách giải các bài toán quy hoạch tuyến tính sau: LP1: a = maxπ(u, π) LP2: b = minπ(u, π) trong đó a* £ U*π £ b*. Ví dụ. Cho các biểu thức logic {; ; }, trong đó hiểu là xác suất của A nằm trong khoảng [0.7, 1]. Làm cách nào để tính xác suất khoảng π(C®(AÚB))? Áp dụng thuật toán IVPR, hầu như tương tự như ví dụ trên ta sẽ tính được xác suất khoảng này. 3. Chứng minh một số luật trong lập luận theo xác suất khoảng 3.1. Luật 1 {, } |= Tập các mệnh đề (sentences): S = {S1 = P, S2 = Q, S3 = P Ù Q} Tập các nguyên tử (atoms) trong S: £ = {P, Q} Ta có không gian thế giới (possible worlds) có thể có: θ1 = (P, Q) θ2 = (P, -Q) θ3 = (-P, Q) θ4 = (-P, -Q) Ma trận V biểu diễn các vector chân trị của các mệnh đề trong S: V = Θ1 Θ2 Θ3 Θ4 S1 1 1 0 0 S1 1 0 1 0 S1 1 0 0 0 Loại bỏ các vector chân trị giống nhau (các cột trong ma trận V) nếu có, ta được ma trận U như sau: U = w1 w2 w3 w4 S1 1 1 0 0 S2 1 0 1 0 S3 1 0 0 0 Không gian xác suất của tập thế giới có thể có: W = {w1, w2, w3, w4} Ta có phân phối xác suất π(.) sao cho: π1 + π2 + π3 + π4 = 1 (*) Các phân phối xác suất mở rộng π(.) cho các mệnh đề tương ứng là: π(S1) = π1 + π2 Î [a, A] Þ a £ π1 + π2 £ A (1) π(S2) = π1 + π3 Î [b, B] Þ b £ π1 + π3 £ B (2) π(S3) = π1 Î [?, ?] Þ ? £ π1 £ ? 1. Để chứng minh cận dưới, ta biến đổi như sau: (1), (2) Þ a + b £ π1 + π1 + π2 + π3 (1’) (1’), (*) Þ a + b £ π1 + 1 – π4 Þ π1 ³ a + b – 1 + π4 Þ π1 ³ a + b – 1 (π4 ³ 0) Mặt khác: π1 ³ 0 Þ π1 ³ max(0, a + b – 1) Nếu π1 = 0 (0 ³ a + b – 1) thì ta có thể chọn: π1 = 0; π2 = a; π3 = b; π4 = 1 – (a + b) thỏa mãn giả thiết. Nếu π1 = a + b – 1 (a + b – 1 ³ 0) thì ta có thể chọn: π1 = a + b – 1; π2 = 1 – b; π3 = 1 – a; π4 = 0 thỏa mãn giả thiết. 2. Để chứng minh cận trên, ta biến đổi như sau: (1) Þ π1 + π2 £ A Þ π1 £ A (1’) (2) Þ π1 + π3 £ B Þ π1 £ B (2’) (1’), (2’) Þ π1 £ min(A,B) Nếu π1 = A (A £ B) thì ta có thể chọn: π1 = A; π2 = 0; π3 = B – A; π4 = 1 – B thỏa mãn giả thiết. Tương tự ta cũng chọn được bộ giá trị thích hợp cho πi (i =1..4) thỏa mãn giả thiết. Vậy π(S3) Î [max(0, a+b-1), min(A,B)] (đpcm). 3.2. Luật 2 {, } |= Tập các phát biểu (sentences): S = {S1 = P, S2 = Q, S3 = P Ú Q} Tập các nguyên tử (atoms) trong S: £ = {P, Q} Ta có không gian thế giới (possible worlds) có thể có: θ1 = (P, Q) θ2 = (P, -Q) θ3 = (-P, Q) θ4 = (-P, -Q) Ma trận V biểu diễn các vector chân trị của các phát biểu trong S: V = Θ1 Θ2 Θ3 Θ4 S1 1 1 0 0 S1 1 0 1 0 S1 1 1 1 0 Loại bỏ các vector chân trị giống nhau (các cột trong ma trận V) nếu có, ta được ma trận U như sau: U = w1 w2 w3 w4 S1 1 1 0 0 S2 1 0 1 0 S3 1 1 1 0 Không gian xác suất của tập thế giới có thể có: W = {w1, w2, w3, w4} Ta có phân phối xác suất π(.) sao cho: π1 + π2 + π3 + π4 = 1 (*) Các phân phối xác suất mở rộng π(.) cho các phát biểu tương ứng là: π(S1) = π1 + π2 Î [a, A] Þ a £ π1 + π2 £ A (1) π(S2) = π1 + π3 Î [b, B] Þ b £ π1 + π3 £ B (2) π(S3) = π1 + π2 + π3 Î [?, ?] Þ ? £ π1 + π2 + π3 £ ? 1. Để chứng minh cận dưới, ta biến đổi như sau: (1) Þ a £ π1 + π2 + π3 (π3 ³ 0) (2) Þ b £ π1 + π2 + π3 (π2 ³ 0) Þ π1 + π2 + π3 ³ max(a, b) Nếu π1 + π2 + π3 = a (a ³ b) thì ta có thể chọn: π1 = b; π2 = a – b; π3 = 0; π4 = 1 – a thỏa mãn giả thiết. Tương tự ta cũng chọn được bộ giá trị thích hợp cho πi (i =1..4) thỏa mãn giả thiết nếu π1 + π2 + π3 = b (a £ b). 2. Để chứng minh cận trên, ta biến đổi như sau: (1) Þ π1 + π2 £ A (1’’) (2) Þ π3 £ B (2’’) (1’’), (2’’) Þ π1 + π2 + π3 £ A + B (*) Þ π1 + π2 + π3 £ 1 Þ π1 + π2 + π3 £ min(1, A + B) Nếu π1 + π2 + π3 = A + B (1 £ A + B) thì ta có thể chọn: π1 = 0; π2 = A; π3 = B; π4 = 1 – (A + B) thỏa mãn giả thiết. Tương tự ta cũng chọn được bộ giá trị thích hợp cho πi (i =1..4) thỏa mãn giả thiết. Vậy π(S3) Î [max(a, b), min(1, A + B)] (đpcm). 3.3. Luật 3 {, } |= Tập các mệnh đề (sentences): S = {S1 = P, S2 = Q, S3 = P ® Q} Tập các nguyên tử (atoms) trong S: £ = {P, Q} Ta có không gian thế giới (possible worlds) có thể có: θ1 = (P, Q) θ2 = (P, -Q) θ3 = (-P, Q) θ4 = (-P, -Q) Ma trận V biểu diễn các vector chân trị của các mệnh đề trong S: V = Θ1 Θ2 Θ3 Θ4 S1 1 1 0 0 S2 1 0 1 0 S3 1 0 1 1 Loại bỏ các vector chân trị giống nhau (các cột trong ma trận V) nếu có, ta được ma trận U như sau: U = w1 w2 w3 w4 S1 1 1 0 0 S2 1 0 1 0 S3 1 0 1 1 Không gian xác suất của tập thế giới có thể có: W = {w1, w2, w3, w4} Ta có phân phối xác suất π(.) sao cho: π1 + π2 + π3 + π4 = 1 (1) Các phân phối xác suất mở rộng π(.) cho các mệnh đề tương ứng là: π(S1) = π1 + π2 Î [a, A] Þ a £ π1 + π2 £ A (2) π(S2) = π1 + π3 Î [b, B] Þ b £ π1 + π3 £ B (3) π(S3) = π1 + π3 + π4 Î [?, ?] Þ ? £ π1 + π3 + π4 £ ? 1. Để chứng minh cận dưới, ta biến đổi như sau: (1) Þ π2 = 1 - (π1 + π3 + π4) (1’) (2) Þ 1 - (π1 + π2) ³ 1-A Þ 1 - (π1 + 1 - (π1 + π3 + π4)) ³ 1-A Þ π3 + π4 ³ 1-A Þ π1 + π3 + π4 ³ 1-A (do π1 ³ 0) (2’) (3) Þ π1 + π3 + π4 ³ b (do π4 ³ 0) (3’) (2’), (3’) Þ π1 + π3 + π4 ³ max(1-A, b) Nếu π1 + π3 + π4 = 1-A (b £ 1-A Þ A+b £ 1) thì ta có thể chọn: π1 = 0; π2 = A; π3 = b; π4 = 1-(A+b) thỏa mãn giả thiết. Nếu π1 + π3 + π4 = b (1-A £ b Þ 1 £ A+b) thì ta có thể chọn: π1 = A+b-1; π2 = 1-b; π3 = 1-A; π4 = 0 thỏa mãn giả thiết. 2. Để chứng minh cận trên, ta biến đổi như sau: (1) Þ π1 + π3 + π4 £ 1 (do π2 ³ 0) (1’’) (2) Þ 1 - (π1 + π2) £ 1-a Þ 1 - (π1 + π2) + π1 + π3 £ 1-a+B (do (3)) Þ 1 + π3 - π2 £ 1-a+B Þ π3 + π1 + π3 + π4 £ 1-a+B (do (1’)) Þ π1 + π3 + π4 £ 1-a+B (do π3 ³ 0) (2’’) (1’’), (2’’) Þ π1 + π3 + π4 £ min(1, 1-a+B) Nếu π1 + π3 + π4 = 1 (1 £ 1-a+B Þ a £ B) thì ta có thể chọn: π1 = a; π2 = 0; π3 = B-a; π4 = 1-B thỏa mãn giả thiết. Nếu π1 + π3 + π4 = 1-a+B (1-a+B £ 1 Þ B £ a) thì ta có thể chọn: π1 = B; π2 = a-B; π3 = 0; π4 = 1-a thỏa mãn giả thiết. Vậy, π(S3) Î [max(1-A, b), min(1, 1-a+B)] (đpcm). 3.4. Luật 4 {} |= Tập các phát biểu (sentences): S = {S1 = P, S2 = -P} Tập các nguyên tử (atoms) trong S: £ = {P} Ta có không gian thế giới (possible worlds) có thể có: θ1 = (P) θ2 = (-P) Ma trận V biểu diễn các vector chân trị của các phát biểu trong S: V = Θ1 Θ2 S1 1 0 S2 0 1 Loại bỏ các vector chân trị giống nhau (các cột trong ma trận V) nếu có, ta được ma trận U như sau: U = w1 w2 S1 1 0 S2 0 1 Không gian xác suất của tập thế giới có thể có: W = {w1, w2} Ta có phân phối xác suất π(.) sao cho: π1 + π2 = 1 (1) Các phân phối xác suất mở rộng π(.) cho các phát biểu tương ứng là: π(S1) = π1 Î [a, A] Þ a £ π1 £ A (2) π(S2) = π2 Î [?, ?] Þ ? £ π2 £ ? Xác định cận dưới và cận trên: (1) Þ π1 = 1 - π2 (1’) (1’), (2) Þ a £ 1 - π2 £ A Þ 1-A £ π2 £ 1-a Nếu π2 = 1-A thì ta có thể chọn: π1 = A; π2 = 1-A thỏa mãn giả thiết. Nếu π2 = 1-a thì ta có thể chọn: π1 = a; π2 = 1-a thỏa mãn giả thiết. Vậy, π(S2) Î [1-A, 1-a] (đpcm). Tài liệu tham khảo [1] Nguyễn Thanh Thủy, Interval-valued probabilistic reasoning, Hanoi University of Technology, Vietnam. [2] Y.Y. Yao, A Comparison of Two Interval-valued Probabilistic Reasoning Methods, Thunder Bay, Ontario, Canada. [3] S.K.M. Wong, L.S. Wang, Y.Y.Yao, On Modeling Uncertainty with Interval Structures, July 16, 2002. [4] Nasser Noroozi, SET-BASED COMPUTATIONS, Thunder Bay, Ontario, September, 1995. [5] Jian Wang, INTERVAL-BASED UNCERTAIN REASONING, Thunder Bay, Ontario, December, 1996.