Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

8
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử" được nghiên cứu với mục tiêu: Nghiên cứu cấu trúc dàn mở rộng làm cơ sở cho mô hình và lập luận trên đồ thị; Nghiên cứu phương pháp biểu diễn, các tính của đồ thị nhận thức LCM sử dụng ĐSGT; Nghiên cứu các thuật toán lập luận trên đồ thị LCM.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN HÁN NGHIÊN CỨU PHƯƠNG PHÁP LẬP LUẬN MỜ TRÊN ĐỒ THỊ NHẬN THỨC SỬ DỤNG ĐẠI SỐ GIA TỬ NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 9480101 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: 1. TS. NGUYỄN CÔNG HÀO 2. PGS. TSKH. NGUYỄN CÁT HỒ HUẾ, NĂM 2023
Công trình được hoàn thành tại: Khoa Công nghệ Thông tin, Trường Đại học Khoa học, Đại học Huế Người hướng dẫn khoa học: 1. TS. Nguyễn Công Hào 2. PGS. TSKH. Nguyễn Cát Hồ • Phản biện 1: PGS. TS. Nguyễn Long Giang, Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. • Phản biện 2: PGS. TS. Hồ Cẩm Hà, Trường Đại học Sư phạm Hà Nội • Phản biện 3: TS. Dương Thăng Long, Trường Đại học Mở Hà Nội Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Huế họp tại: ........................................................................................... ........................................................................................... .Vào hồi..........giờ..........ngày.........tháng.......năm 2023 Có thể tìm luận án tại thư viện : 1. Trung tâm thông tin thư viện 2. Trường Đại học Khoa học, Đại học Huế
MỞ ĐẦU 1. Lý do chọn đề tài Logic mờ dựa trên lý thuyết tập mờ và biến ngôn ngữ của L. A. Zadeh. Tập mờ cùng với các phép toán logic được phát triển từ tập hợp kinh điển là mô hình toán học cho phép biểu diễn và tính toán trên các giá trị ngôn ngữ. Nhờ đó, giải quyết được lớp bài toán lập luận xấp xỉ trên máy tính mà đã không giải quyết được bằng logic kinh điển. Lập luận xấp xỉ cho lớp bài toán với thông tin vào - ra không chắc chắn được hình thức hóa theo cách tư duy tự nhiên của con người. Phương pháp suy diễn gần đúng từ một họ các tiên đề không chắc chắn và mang các đặc trưng định tính nhiều hơn định lượng. Ứng dụng của tập mờ để biểu diễn tri thức và lập luận trên đồ thị thường có dạng như Hình 1. Theo mô hình này, các kết quả vào ra là các giá trị từ, giai đoạn chuyển sang số chỉ là giai đoạn trung gian để thực hiện việc lập luận. Như vậy, việc lập luận trên đồ thị theo phương pháp trước đây gặp một số vấn đề sau đây: • Vấn đề thứ nhất Thiếu một cấu trúc toán học để biểu diễn miền trị ngôn ngữ cho các từ. • Giải quyết Dùng phương pháp của N. C. Ho và W. Wechler, theo phương pháp này, mỗi giá trị ngôn ngữ được sinh ra từ một biến ngôn ngữ thuộc một cấu trúc đại số trừu tượng được gọi là đại số gia tử (ĐSGT). Cấu trúc này đã đại số hóa miền giá trị của biến ngôn ngữ để 1
C1 FCM 1 2 4 5 Từ Số Số Từ C2 C3 3 Hình 1: Sơ đồ vào ra dữ liệu cho đồ thị FCM thực hiện phương pháp lập luận trên từ mà không phải chuyển sang số . • Vấn đề thứ hai Độ phức tạp tính toán cao do phải thực hiện thêm các phép toán trung gian trong việc chuyển đổi từ số qua từ và ngược lại trước và sau khi tính toán. • Giải quyết Dùng đại số gia tử cùng các phép toán đã được định nghĩa trên tập giá trị ngôn ngữ. Các phép toán được tính toán trực tiếp trên giá trị ngôn ngữ mà không phải chuyển sang số như Hình 2. Như vậy, số phép toán giảm do đó làm giảm độ phức tạp tính toán. Với các nhận xét trên, việc nghiên cứu một phương pháp biểu diễn và lập luận trên đồ thị sử dụng biến ngôn ngữ là cần thiết, phù hợp với các ứng dụng trong thực tế và suy luận tự nhiên của con người. Đó là lý do để luận án nghiên cứu và phát triển đề tài: Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử 2
C1 LCM 1 3 Từ Từ C2 C3 2 Hình 2: Sơ đồ vào ra dữ liệu cho LCM 2. Đối tượng và phạm vi nghiên cứu Để mô hình hóa, lập luận và kiểm chứng trên đồ thị nhận thức, luận án bắt đầu từ việc nghiên cứu một dàn mở rộng trên miền trị ngôn ngữ. Cấu trúc và các phép toán mở rộng trên dàn là cơ sở cho mô hình hóa và các phép toán vector và ma trận liên quan đến đồ thị LCM. Các thuật toán lập luận theo nhánh, lập luận theo không gian trạng thái và độ phức tạp tính toán. Khảo sát sự biến đổi của không gian trạng thái và tính hội tụ của nó. 3. Phương pháp nghiên cứu Luận án tập trung vào hai phương pháp nghiên cứu chính: • Phương pháp nghiên cứu tài liệu, phân tích, tổng hợp và hệ thống hóa: Thu thập tài liệu về các công trình khoa học đã nghiên cứu và công bố trên các bài báo hội nghị trong nước và quốc tế về cấu trúc đồ thị mờ FCM, phân tích những ưu nhược điểm trong việc mô hình, lập luận và kiểm chứng của đồ thị FCM. Đề xuất cấu trúc đồ thị LCM là một cấu trúc đồ thị nhận thức, việc mô hình, lập luận và kiểm chứng chỉ thực 3
hiện hoàn toàn trên miền trị ngôn ngữ. • Phương pháp logic hình thức: Phương pháp này nhằm đặc tả các đối tượng nghiên cứu: Dàn mở rộng ELL, các phép toán đa ngôi trên dàn. Đồ thị nhận thức LCM được hình thức hóa thành các tập đỉnh, cạnh và quan hệ nhân - quả giữa các đỉnh. Các tính chất tổ hợp trên đồ thị LCM được phát biểu thành các biểu thức, công thức, tính chất và được chứng minh. Các thuật toán lập luận theo nhánh và theo trạng thái được đánh giá chính xác về độ phức tạp. Tính hội tụ của trạng thái của đồ thị được phát biểu và chứng minh chặt chẽ, logic về mặt toán học. 4. Mục tiêu của luận án Luận án đưa ra các mục tiêu nghiên cứu chính như sau: • Nghiên cứu cấu trúc dàn mở rộng làm cơ sở cho mô hình và lập luận trên đồ thị [CT4] • Nghiên cứu phương pháp biểu diễn, các tính của đồ thị nhận thức LCM sử dụng ĐSGT [CT6, CT7] • Nghiên cứu các thuật toán lập luận trên đồ thịLCM [CT3, CT5]. 5. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học Những đóng góp chính của luận án về mặt khoa học: • Đề xuất một cấu trúc dàn mở rộng trên miền trị ngôn ngữ. • Xây dựng một cấu trúc đồ thị nhận thức LCM trên miền ngôn ngữ và các tính chất tổ hợp của đồ thị. • Xây dựng các thuật toán lập luận trên đồ thị nhận thức. 4
Ý nghĩa thực tiễn • Luận án cung cấp một nền tảng lý thuyết về dàn mờ, phương pháp mô hình và lập luận mờ trên đồ thị. • Khẳng định ưu điểm của ĐSGT trong biểu diễn và lập luận trên đồ thị nhận thức 6. Bố cục của luận án Về bố cục của luận án, ngoài phần mở đầu và phần kết luận, nội dung chính được chia thành 3 chương như sau: • Chương 1: Tổng quan các kiến thức cơ bản về tập mờ, về ĐSGT. Chương này đề xuất một cấu trúc đại số trừu tượng trên miền ngôn ngữ là dàn mở rộng. Các phép toán mở rộng trên dàn, khảo sát tính chất topo và tính trực giao của dàn. • Chương 2: Trình bày cấu trúc của đồ thị nhận thức LCM sử dụng miền trị ngôn ngữ theo hai cách tiếp cận. Cách tiếp cận thứ nhất kế thừa từ đồ thị nhận thức mờ FCM và cách tiệp cận thứ hai dựa vào lý thuyết mô hình. • Chương 3. Trình bày hai phương pháp lập luận trên đồ thị là lập luận tĩnh và lập luận động. Các thuật toán và độ phức tạp tính toán được phân tích và chứng minh. Chương này khảo sát tính chất hội tụ của trạng thái bằng việc phát biểu và chứng minh các tính chất toán học. 5
Chương 1. CẤU TRÚC DÀN MỞ RỘNG TRÊN MIỀN TRỊ NGÔN NGỮ SỬ DỤNG ĐẠI SỐ GIA TỬ 1.1. Cấu trúc dàn mờ trên miền trị ngôn ngữ [CT1, CT4] Định nghĩa 1.1. Xét một cấu trúc đại số L trên miền giá trị ngôn ngữ L như sau: L = L, , , ∧, ∨, →, ⊥, (1.1) được gọi là dàn mở rộng ELL (Extended linguistic ted lattice). Trong đó, L là ngôn ngữ được sinh ra từ ĐSGT và ý nghĩa của các ký hiệu như sau: Ký hiệu Phép toán Ý nghĩa L: Tập các giá trị ngôn ngữ ∧: L×L→L Phép toán logic và ∨: L×L→L Phép toán logic hoặc ai lần : L × ··· × L → L Phép toán lấyMin ai lần : L × ··· × L → L Phép toán lấyMax : = sup{L} Phần tử lớn nhất trên L ⊥ : ⊥ = inf {L} Phần tử bé nhất trên L Các hằng số = sup{L} = 1 và ⊥ = inf {L} = 0. 6
1.2. Các tính chất cùa dàn ELL Dàn L trong Biểu thức 1.1 có các tính chất sau đây: Tính chất 1.1. Các tính chất của dàn: 1. Dàn L bảo toàn thứ tự ≤ với các phép toán ∧, ∨, và . 2. (L, ∧, 1) là nửa nhóm với phần tử đơn vị là 1. 3. Với 1, 2, 3 ∈ L, giữa hai phép toán ∧ và → có mối liên hệ: 1 ∧ 2 ≤ 3 ⇔ 1 ≤ 2 → 3. (1.2) 4. Dàn L là dàn thặng dư ELL 1.3. Tiểu kết chương 1 Chương này trình bày một cấu trúc đại số là dàn mở rộng trên miền giá trị ngôn ngữ được sinh ra từ đại số gia tử. Cấu trúc dàn cùng các phép toán mở rộng được dùng làm cơ sở nền tảng cho Chương 2 và Chương 3. Miền trị ngôn ngữ L được dùng trong việc biểu diễn tri thức cho đồ thị nhận thức trong Chương 2. Đồ thị mờ với tập đỉnh và tập cạnh là các giá trị ngôn ngữ thể hiện trực quan và tự nhiên gần với ngôn ngữ con người. Các phép toán logic trên dàn ELL bao gồm phép toán "và" ∧, phép toán "hoặc" ∨ là các phép toán lấy giá trị Min và Max của hai toán hạng. Phép toán và là phép toán lấy Min và Max của nhiều toán hạng. Các phép toán này (∧, ∨, , ) được dùng để lập luận trên các thuật toán trong Chương 3. 7
Chương 2. CẤU TRÚC ĐỒ THỊ NHẬN THỨC TRÊN MIỀN TRỊ NGÔN NGỮ 2.1. Đồ thị nhận thức mờ dựa trên ĐSGT [CT6] Định nghĩa 2.1. Một đồ thị nhận thức mờ dựa trên biến ngôn ngữ LCM (linguistic cognitive map) là một bộ 4: LCM = {C, E, C, f } (2.1) Trong đó: 1. C = {C1 , C2 , . . . , Cn } là tập N mệnh đề mờ tạo thành các nút của đồ thị LCM. 2. E : (Ci , Cj ) −→ eij ∈ L là một hàm số kết hợp eij với một cặp mệnh đề mờ (Ci , Cj ), với eij là trọng số cạnh có hướng từ Ci đến Cj . Ma trận kết nối là ma trận vuông cấp N × N , E(N × N ) ∈ LN ×N , với:   e11 e12 . . . e1N  . . .. .  E(N × N ) =  .  . . . . .  .  eN 1 eN 2 . . . eN N 3. Ánh xạ: C : Ci −→ Ci (t) là một hàm số kết hợp mỗi một mệnh đề mờ Ci với một giá trị mờ trên tập ngôn ngữ L, Ci (t) ∈ L. 8
4. Với C(0) = [C1 (0), C2 (0), . . . , CN (0)] ∈ LN là giá trị khởi tạo cho các mệnh đề mờ thì C(t) = [C1 (t), C2 (t), . . . , CN (t)] ∈ LN là giá trị của các mệnh đề mờ Ci ở thời điểm t. 5. Cj (t + 1) ∈ L là giá trị của các mệnh đề mờ Cj ở thời điểm t + 1 là tổ hợp Max của các Min và được tính truy hồi theo phương trình: N Cj (t + 1) = Ci (t) ∧ eij (2.2) i=1 Trong đó phép toán là phép lấy Max của nhiều toán hạng và phép toán ∧ là phép toán hai ngôi, phép lấy Min. Để có thể mờ hóa khoảng đơn vị I = [0, 1] với L, chúng ta cần một số lượng lớn các gia tử. Giả sử c = hn hn−1 . . . h1 c, tính chính xác trong biểu diễn khoảng đơn vị I phải tỷ lệ với length( ). Gọi | | = length( ), một câu hỏi đặt ra là giá trị kích thước | | bằng bao nhiêu là đủ tốt cho việc mờ hóa mà không tăng tính phức tạp khi sử dụng quá nhiều gia tử. Tính chất sau đây làm sáng tỏ câu hỏi này. Tính chất 2.1. Biểu diễn đoạn I bằng biến ngôn ngữ [CT6] • Gọi dãy {Ij }k là k phân hoạch của I, I là tập con của tập chỉ số, với j=1 ∀j, l ∈ I ∧ j = l I = ∪k Ij ; Ij ∩ Il = ∅ j=1 (2.3) • Gọi: c = hn hn−1 . . . h1 c (2.4) là biến ngôn ngữ, c ∈ L, là phép lấy Max, H là một tập các gia tử hi , i ∈ I. 9
Thì: log( k−1 ) k | |< (2.5) log( hi ∈H fm(hi )) Tính chất 2.1 quan trọng trong việc giới hạn kích thước của các gia tử dùng cho việc mờ hóa các tri thức mờ.. 2.2. Mô hình LCM theo lý thuyết mô hình Phần này sử dụng logic trên cấu trúc với các quan hệ trên tập ký tự để hình thức hóa đồ thị LCM. Định nghĩa 2.2. [CT7] Một chữ ký quan hệ nhị phân G là một bộ: G = {labα , succβ } (2.6) Trong đó: α ∈ L và β ∈ L. labα , succβ là các quan hệ trên tập ký tự. Các cấu trúc được sinh ra từ G được gọi là struct[ G]. Sử dụng struct[ G], tập đỉnh C và tập cạnh E của LCM có thể hình thức hóa như sau: Định nghĩa 2.3. [CT7] Một C struct[ G] là một bộ: C = C, labC , succC α β (2.7) Trong đó : • C là tập xác định của C • labC là quan hệ một ngôi (monadic hoặc unary relation): {∃C ∈ C | labC C}, α α α∈L • succC là quan hệ hai ngôi (binary relation): {C1 , C2 ∈ C | succC (C1 , C2 )}, β β β ∈ L. C2 là liền kề sau (sucessor) của C1 và (C1 , C2 ) là cạnh có hướng. 10
Tổ hợp trên cấu trúc mờ Đưa ra một C struct[ G] trong (2.7), độ phức tạp của không gian C tỷ lệ với C , labα và succβ - Ký hiệu . chỉ kích thước. Tính chất 2.2. [CT7] Ta có: C +1 22×( 2 ) (2.8) C struct[ G] khác nhau với kích thước C . 2.3. Tiểu kết chương 2 Chương này trình bày mô hình toán học của đồ thị mờ LCM theo hai cách tiếp cận. Cách tiếp cận theo phương pháp kế thừa từ các nghiên cứu trước đó về đồ thị FCM và cách tiệp cận thứ hai theo phương pháp mô hình. Nghiên cứu các tính chất tổ hợp của đồ thị LCM. Đồ thị nhận thức LCM biểu diễn mới quan hệ nhân - quả giữa các đỉnh. Thuật toán lập luận và độ phức tạp tính toán được trình bày trong Chương 3 tiếp theo. 11
Chương 3. PHƯƠNG PHÁP LẬP LUẬN TRÊN ĐỒ THỊ NHẬN THỨC 3.1. Lập luận tĩnh theo nhánh [CT3] Lập luận theo nhánh của đồ thị LCM xác định mối quan hệ nhân - quả L giữa hai đỉnh bất kỳ Ci và Cj trên đường đi bất kỳ Ci ; Cj và giá trị chân lý của mệnh đề If Ci then Cj là truth( If Ci then Cj ) phải là giá trị ngôn ngữ, nói cách khác truth( If Ci then Cj ) ∈ L Thuật toán dùng một hàng đợi để chứa các phần tử đã được xét và cũng là điều kiện dừng cho thuật toán khi mà đỉnh đích cuối cùng ở trong hàng đợi Q. Thuật toán làm việc như sau: • Khởi tạo giá trị lớn nhất trên tập L cho đỉnh nguồn s, các đỉnh khác khởi tạo giá trị nhỏ nhất, tập Q lúc đầu là tập rỗng. • Lặp lại việc gán nhãn trong khi đỉnh d chưa nằm trong tập Q; Với u là đỉnh 1. u là đỉnh chưa ở trong Q mà có nhãn lớn nhất thì đưa u vào Q 2. Lặp lại với mỗi đỉnh v chưa ở trong Q: Nếu L(u) ∧ e(u, v) ≥ L(v) thì L(v) ← L(u) ∧ e(u, v), với ← là phép gán. • ← L(d): Giá trị đường đi từ nguồn s đến đích d. Với chú thích được đặt sau ký hiệu , mã giả của thuật toán được trình bày trong Thuật toán 1 12
Thuật toán 1 Thuật toán lập luận theo nhánh Vào: Đồ thị LCM = (V, E) LCM với các đỉnh là: s=C1 , . . . , Cn = d và trọng số các cạnh e(vi , vj ) ∈ L Ra: L(d) L(d) ∈ L là độ dài đường đi từ s tới d 1: foreach Ci ∈ V do Khởi tạo nhãn cho các đỉnh 2: L(Ci ) ← 0 Nhãn của các đỉnh được gán bằng 0 (0 = Min{L}) 3: end foreach 4: L(s) = 1 Nhãn của các đỉnh nguồn được gán bằng 1 (1 = Max{L}) 5: Q=∅ Ban đầu hàng đợi Q là rỗng 6: while d ∈ Q do / Trong khi đỉnh đích d chưa ở trong hàng đợi Q 7: u ← Đỉnh thuộc V − Q với nhãn L(u) lớn nhất u là đỉnh không thuộc Q mà có nhãn lớn nhất 8: Q = Q ∪ {u} Đưa vào Q đỉnh có nhãn lớn nhất 9: foreach v ∈ Q do / 10: if L(u) ∧ e(u, v) ≥ L(v) then 11: L(v) ← L(u) ∧ e(u, v) Cập nhật lại nhãn cho đỉnh v 12: end if 13: end foreach 14: end while 15: return L(d) L(d) là độ dài dường đi từ s đến d Độ phức tạp tính toán của Thuật toán 1 được thể hiện trong tính chất sau: Tính chất 3.1. Gọi |V | là kích thước của tập đỉnh các mệnh đề mờ, độ phức tạp của Thuật toán 1 là O(|V |)2 . Phương pháp lập luận theo nhánh áp dụng được cho hai đỉnh bất kỳ của 13
đồ thị LCM, khẳng định này được thể hiện qua Tính chất 3.2. L Tính chất 3.2. Mỗi đường đi Ci ; Cj giữa hai đỉnh bất kỳ Ci và Cj trên đồ thị LCM là một phép lập luận. 3.2. Lập luận động theo biến đổi trạng thái [CT5] Một trạng thái của đồ thị là một vector các giá trị ngôn ngữ được gán cho các mệnh đề mờ của tập đỉnh. Các đỉnh thành phần ký hiệu bằng các chữ in hoa C1 , C2 , . . . , các trạng thái ký hiệu là C và không gian trạng thái ký hiệu là C. Hàm biến đổi trạng thái có dạng như sau: [CT4, CT5]. N Cj (t + 1) = Ci (t) ∧ eij (3.1) i=1 Trong đó: • N là số mệnh đề mờ tạo nên các đỉnh của đồ thị LCM, các đỉnh tính từ 1 đến N theo biến chạy i. • Ký hiệu Ci (t), với hai tham số i và t, trong đó i nói lên mệnh đề mờ thứ i trong N khái niệm mờ C1 , C2 , . . . , Ci , . . . , CN và tham số t nói lên lần lặp thứ t. • Ký hiệu CJ (t + 1) là giá trị của mệnh đề mờ Cj tại thời điểm (t+1) • eij là trọng số cạnh có hướng nối Ci và Cj • Phép toán ∧ và ∨ là các phép toán logic được định nghĩa trên ĐSGT. Phép toán ∧ có độ ưu tiên cao hơn phép toán ∨ • Ký hiệu Ci là một mệnh đề mờ và Ci (t) là giá trị của mệnh đề mờ tại thời điểm (t), Ci (t) ∈ L. 14
Thuật toán 2 Lập luận động theo trạng thái Vào: Vector khởi tạo C(0), ma trận E Ra: Vector điểm cố định C(f ix) 1: for i ← 1 to n do Khởi tạo giá trị cho các mệnh đề mờ 2: Ci ← Ci (0) n là số đỉnh 3: end for 4: for i ← 1 to n do Khởi tạo giá trị cho các cạnh 5: for j ← 1 to n do 6: (Ci , Cj ) ← ei,j Trọng số cạnh (Ci , Cj ) là eij 7: end for 8: end for Tiến trình lặp để tìm vector cố định 9: Time ← 0 Time đóng vai trò t trong Phương trình 3.1 10: while C(Time + 1) = C(Time) do 11: for j ← 1 to n do Tìm giá trị cho các mệnh đề mờ C1 , . . . , Cj , Cn n 12: Max ← 0 Tính tổng Max = i=1 Ci (Time) ∧ eij 13: for i ← 1 to n do 14: Max ← Max ∨ Ci (Time) ∧ eij 15: end for n Tính Cj (Time + 1) = i=1 Ci (Time) ∧ eij 16: Cj (Time + 1) ← Max 17: end for 18: Time ← Time + 1 19: end while 20: C(f ix) ← C(Time) 21: return C(f ix) Mã giả của giải thuật được trình bày trong Thuật toán 2. Các lệnh chú 15
thích đạt sau ký hiệu và 21 dòng lệnh chính như sau: • Dòng 1 đến dòng 3: Khởi tạo giá trị ban đầu (t=0) cho các mệnh đề mờ C1 , . các giá trị C1 (0), . . . , Cn (0) và là các giá trị ngôn ngữ thuộc tập L. • Dòng 4 đến dòng 8: Khởi tạo giá trị ma trận trọng số E cho cạnh có hướng (Ci , Cj ) với giá trị tương ứng là eij là các giá trị ngôn ngữ thuộc tập L. • Dòng 9 đến dòng 19: Là các kỹ thuật để tính toán Phương trình truy hồi 3.1, trong đó biến t được thay thế bởi biến Time để nhấn mạnh sự điều khiển theo thời gian rời rạc. Quá trình này gồm hai giai đoạn chính: • Dòng 11 đến dòng 15: Tổng riêng n i=1 Ci (t) ∧ eij được lưu vào một biến tạm có tên là Max. • Dòng 16: Nhờ có biến Max làm trung gian, giá trị của mệnh đề mờ Cj ở thời điểm (Time + 1) được tính qua hai bước theo công thức: n Cj (Time + 1) = i=1 Ci (Time) ∧ eij Cj (Time + 1) =Max n = Ci (Time) ∧ eij i=1 • Dòng 19, 20: Khi thuật toán dừng, điểm cố định C(f ix) sẽ lưu trong vector C(Time) và trả về cho chương trình. Tính chất 3.3. Với LCM = (V, E) có kích thước tập đỉnh là |V | thì độ phức tạp của Thuật toán 2 là O(|V |)3 Thuật toán lập luận trên đồ thị của luận án tính toán trực tiếp trên từ và có các tính chất [CT4, CT5]: 16
• Tính toán trực tiếp trên từ • Giảm độ phức tạp tính toán vì giảm số phép toán do không phải chuyển đổi qua qua lại giữa số và từ. • Thời gian chạy nhanh vì độ phức tạp tính toán thấp Trạng thái của hệ sẽ luôn luôn hội tụ trong các trường hợp nêu trong Tính chất 3.4 sau đây: Tính chất 3.4. [CT4] Hệ sẽ đạt tới điểm cố định C(f ix) khi vector C(1) phụ thuộc vào vector khởi tạo C(0) trong các trường hợp sau: C(1) = C(0) (3.2) C(1) > C(0) (3.3) C(1) < C(0) (3.4) Tính chất 3.4 chỉ ra hệ thống hội tụ khi có sự liên hệ giữa C(1) và C(0) theo các Phương trình 3.2, 3.3 và 3.4. Tuy nhiên, hệ thống có thể hội tụ tại thời điểm t nào đó trong không gian trạng thái như Tính chất 3.5 sau đây: Tính chất 3.5. [CT4] Tại thời điểm t bất kỳ, hệ sẽ đạt tới điểm cố định C(f ix) khi vector C(t + 1) phụ thuộc truy hồi vào vector C(t) trong các trường hợp sau: C(t + 1) ≥ C(t) (3.5) C(t + 1) ≤ C(t) (3.6) 3.3. Tiểu kết Chương 3 Chương 3 nghiên cứu các thuật toán lập luận trên đồ thị nhận thức LCM bao gồm lập luận theo nhánh và lập luận theo trạng thái. Lập luận theo 17
nhánh dựa trên kỹ thuật dán nhãn để tìm tổ hợp giá trị lớn nhất từ các đường đi đơn riêng lẻ. Thuật toán lập luận theo trạng thái dựa trên phương trình chuyển trạng thái của đồ thị nhận thức LCM. Độ phức tạp tính toán trong các thuật toán lập luận được chứng minh chặt chẽ về mặt toán học. Thuật toán lập luận động theo trạng thái luôn luôn tiến về một vector cô định, bất động, khi thỏa mãn các Tính chất 3.4 và 3.5. 18