Giới thiệu dự án

Trong lĩnh vực Trí tuệ Nhân tạo (Artificial Intelligence - AI), việc xây dựng các hệ giải bài toán tự động (Automated Problem Solvers) và hệ chuyên gia (Expert Systems) đóng vai trò then chốt trong việc chuyển hóa tri thức chuyên ngành thành năng lực tính toán thông minh. Tuy nhiên, tri thức con người trong các lĩnh vực khoa học chính xác (toán học, vật lý, kỹ thuật) thường mang tính trừu tượng cao, kết hợp chặt chẽ giữa các khái niệm phân cấp, quan hệ cấu trúc và các phép biến đổi đại số phức tạp. Các mô hình biểu diễn tri thức truyền thống như Logic vị từ (First-Order Logic), Hệ luật dẫn (Production Rules) hay Mạng ngữ nghĩa (Semantic Networks) thường bộc lộ sự hạn chế trong việc mô hình hóa đồng thời cả tri thức quan hệ lẫn tri thức tính toán thuật giải, dẫn đến sự bùng nổ không gian trạng thái khi suy diễn.

Mô hình Tri thức Đối tượng Tính toán (Computational Objects Knowledge Base - COKB) do PGS.TS Đỗ Văn Nhơn đề xuất là một bước tiến quan trọng theo hướng tiếp cận Ontology kết hợp hướng đối tượng. Dù vậy, các nghiên cứu trước đây về COKB chủ yếu tập trung vào các miền tri thức hình học phẳng và vật lý tĩnh, trong khi động cơ suy diễn trên các thành phần tri thức Hàm (Functions) và Toán tử (Operators) chưa được hình thức hóa đầy đủ. Khóa luận tốt nghiệp "Một số lớp bài toán và phương pháp suy diễn trên cơ sở tri thức COKB" của tác giả Lưu Thanh Sơn (Khoa Khoa học Máy tính, Trường Đại học Công nghệ Thông tin - ĐHQG-HCM, 2018) đã giải quyết triệt để nút thắt này.

graph TD
    A[Tri thức miền: Ma trận & Hệ phương trình] --> B[Mô hình hóa COKB 6 thành phần]
    B --> C[Tập tin cấu trúc tri thức .TXT]
    C --> D[Động cơ suy diễn COKB]
    D --> E[Bộ so khớp & Hợp nhất 12 loại sự kiện]
    D --> F[Bộ suy diễn luật RCN1 - RCN7]
    D --> G[Thuật giải tìm bao đóng Fclosure]
    E & F & G --> H[Hệ thống tự động sinh lời giải từng bước]

Mục tiêu cụ thể của dự án:

  1. Hoàn thiện định nghĩa hình thức cho mô hình COKB đầy đủ gồm 6 thành phần: $(C, H, R, Ops, Funcs, Rules)$.
  2. Phân loại chi tiết 12 loại sự kiện (Fact types) và xây dựng thuật toán hợp nhất sự kiện (Fact Unification) dựa trên ngữ nghĩa toán học.
  3. Bổ sung quy tắc suy diễn mới $RCN7$ cho phép suy diễn trực tiếp trên thành phần Toán tử (Operators) và mở rộng các quy tắc xử lý Hàm (Functions).
  4. Thiết lập thuật giải tìm bao đóng sự kiện ($F_{closure}$) trên một đối tượng tính toán và thuật giải suy diễn tổng quát giải quyết mô hình bài toán $(O, F) \rightarrow G$.
  5. Hiện thực hóa và kiểm chứng mô hình trên miền tri thức Ma trận và Hệ phương trình tuyến tính bằng môi trường tính toán biểu thức đại số Maple.

Phạm vi nghiên cứu tập trung vào các cấu trúc đại số tuyến tính cơ bản (Ma trận, Ma trận vuông, Ma trận khả nghịch, Hệ phương trình tuyến tính), với giới hạn là các phép toán biến đổi ma trận giải tích thực tế và hệ phương trình đại số tuyến tính có nghiệm cụ thể hoặc tham số.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Trước khi hoàn thiện mô hình COKB, các hệ thống biểu diễn và suy diễn tri thức trên thế giới và tại Việt Nam tồn tại nhiều ưu - nhược điểm rõ rệt:

Phương pháp biểu diễn Ưu điểm Nhược điểm Khả năng tính toán đại số
Hệ luật dẫn (Production Rules - CLIPS/Drools) Trực quan, dễ viết luật dạng $IF \dots THEN$, phổ biến trong chẩn đoán y khoa. Khó biểu diễn tri thức trừu tượng, không hỗ trợ kế thừa hướng đối tượng, dễ bùng nổ luật. Kém (chỉ xử lý logic điều kiện đơn giản).
Logic vị từ & Lập trình Logic (Prolog) Nền tảng toán học chặt chẽ, hỗ trợ quay lui (backtracking) mạnh mẽ. Hiệu năng tìm kiếm kém trên không gian lớn, khó biểu diễn công thức giải tích phức tạp. Trung bình (cần định nghĩa đệ quy dài dòng).
Mạng ngữ nghĩa & Ontology (OWL/Protege) Phân cấp khái niệm rõ ràng, tận dụng lý thuyết đồ thị và quan hệ $IS_A, HAS_A$. Chủ yếu mang tính phân loại tĩnh (Taxonomy), thiếu cơ chế kích hoạt hành vi tính toán động. Rất kém (thiếu toán tử tính toán ma trận/đại số).
Mô hình COKB cải tiến (Đề tài đề xuất) Kết hợp Ontology hướng đối tượng, lưu trữ toán tử tính toán, hàm giải tích, hỗ trợ bao đóng sự kiện. Đòi hỏi đặc tả tri thức ban đầu công phu theo chuẩn 12 loại sự kiện. Rất mạnh (tích hợp động cơ suy diễn đại số và giải thuật ma trận).

Dựa trên phân tích yêu cầu theo chuẩn MoSCoW:

  • Must have: Hoàn thiện đặc tả 6 thành phần của COKB; hiện thực cơ chế so khớp ngữ nghĩa cho 12 loại sự kiện; tích hợp quy tắc suy diễn toán tử $RCN7$; xây dựng thuật giải tìm bao đóng đối tượng.
  • Should have: Áp dụng các quy tắc Heuristics nhằm tỉa nhánh không gian tìm kiếm, tối ưu thời gian suy diễn.
  • Could have: Tự động sinh diễn giải lời giải chi tiết theo từng bước phục vụ giáo dục thông minh.
  • Won't have (trong phạm vi này): Giao diện web trực quan đa người dùng thời gian thực (hệ thống tập trung vào động cơ suy diễn cốt lõi trên Maple).

Thiết kế hệ thống

Mô hình tri thức COKB đầy đủ được định nghĩa hình thức là một bộ 6 thành phần:

$$\text{COKB} = (C, H, R, Ops, Funcs, Rules)$$

Trong đó:

  • $C$ (Concepts): Tập các khái niệm đối tượng tính toán (C-Object). Mỗi đối tượng $O \in C$ được biểu diễn bởi $(Attr, Facts, Rules)$, với $Rules = (R_f, R_r)$ gồm quan hệ tính toán $R_f$ và luật suy diễn nội tại $R_r$.
  • $H$ (Hierarchy): Biểu đồ Hasse thể hiện quan hệ phân cấp kế thừa ($IS_A$, $HAS_A$), ví dụ: [MATRAN, MATRANVUONG].
  • $R$ (Relations): Tập quan hệ tính toán 2 ngôi hoặc đa ngôi giữa các khái niệm, mang các tính chất đối xứng, phản xạ, bắc cầu.
  • $Ops$ (Operators): Ánh xạ $C_i \times C_j \rightarrow C_k$, định nghĩa các phép toán đại số (cộng, nhân ma trận) kèm thuộc tính giao hoán (commutative), kết hợp (associative), hợp nhất (identity).
  • $Funcs$ (Functions): Ánh xạ hàm $f: C_i \rightarrow C_j$ (như hàm tính định thức DINHTHUC(A), hàm tính hạng HANG(A)).
  • $Rules$ (Rules): Tập các luật dẫn toàn cục dạng $h(r) \Rightarrow g(r)$.
classDiagram
    class COKB {
        +Set C_Concepts
        +Set H_Hierarchy
        +Set R_Relations
        +Set Ops_Operators
        +Set Funcs_Functions
        +Set Rules_Global
    }
    class ComputationalObject {
        +String ConceptName
        +List Attr
        +List Facts
        +List Rf_ComputationRelations
        +List Rr_InferenceRules
        +FindClosure()
    }
    class OperatorDef {
        +String Name
        +List Arguments
        +Type ReturnType
        +String Property
        +Execute()
    }
    class FunctionDef {
        +String Name
        +List Arguments
        +Type ReturnType
        +ExecuteProc()
    }
    COKB *-- ComputationalObject
    COKB *-- OperatorDef
    COKB *-- FunctionDef

Hệ thống quản lý tri thức được module hóa thành các tệp văn bản có cấu trúc rõ ràng:

/COKB_Storage/
├── BASE_CONCEPTS.TXT       # Lưu kiểu dữ liệu nền tảng (int, real, array)
├── CONCEPTS.TXT            # Định danh khái niệm (MATRAN, HEPHUONGTRINH)
├── HIERARCHY.TXT           # Quan hệ phân cấp Hasse
├── RELATIONS.TXT           # Danh mục quan hệ tính toán
├── OPERATORS.TXT           # Khai báo toán tử tính toán
├── OPERATORS_DEF.TXT       # Định nghĩa mã thủ tục thực thi toán tử
├── FUNCTIONS.TXT           # Khai báo hàm
├── FUNCTIONS_DEF.TXT       # Định nghĩa mã thủ tục giải tích của hàm
├── RULES.TXT               # Tập luật dẫn hệ thống
└── <CONCEPT_NAME>.TXT      # Cấu trúc nội tại chi tiết của từng C-Object

Methodology

Quy trình phát triển hệ thống tuân theo phương pháp tiếp cận Waterfall có kiểm chứng hình thức toán học:

  1. Giai đoạn 1 (Hình thức hóa toán học): Xây dựng hệ thống 12 loại sự kiện và định lý hợp nhất sự kiện $\approx$.
  2. Giai đoạn 2 (Đặc tả ngôn ngữ tri thức): Xây dựng cú pháp phi ngữ cảnh (BNF) cho các file lưu trữ .TXT.
  3. Giai đoạn 3 (Thuật toán hóa động cơ suy diễn): Phát triển thuật giải tìm bao đóng và thuật toán suy diễn tổng quát.
  4. Giai đoạn 4 (Cài đặt và Đánh giá): Hiện thực hóa toàn bộ module trên ngôn ngữ Maple v18, tiến hành chạy thử nghiệm trên bộ bài toán mẫu ma trận - hệ phương trình.

Implementation và kết quả

Development process

Cốt lõi của hệ thống là việc định nghĩa và xử lý 12 loại sự kiện trong không gian sự kiện ($FactSpace$):

  • Loại 1: Phân loại đối tượng [A, "MATRAN"].
  • Loại 2: Sự tồn tại/xác định của đối tượng hoặc thuộc tính A.m, A.n.
  • Loại 3: Gán giá trị hằng số cho thuộc tính A.n = 3.
  • Loại 4: Sự bằng nhau giữa 2 đối tượng/thuộc tính A.m = B.n.
  • Loại 5: Đẳng thức/công thức phụ thuộc A = B + C hoặc A.m = B.m + 1.
  • Loại 6: Quan hệ giữa các đối tượng ["BANGNHAU", A, B].
  • Loại 7 - 12: Các sự kiện về Hàm, gán giá trị hàm (DINHTHUC(A) = 0), đẳng thức hàm (HANG(A) = HANG(B)), và quan hệ phức hợp chứa hàm.

Quy tắc suy luận toán tử $RCN7$ được thiết kế và bổ sung vào thuật giải suy diễn tổng quát nhằm giải quyết các biểu thức loại 5:

// Thuật giải 3.3: Áp dụng toán tử trong suy diễn COKB (RCN7)
Algorithm Apply_Operator(F, KnowledgeBase):
    KnowFact := F;
    Sol := [];
    Foreach f in KnowFact do:
        If (kind_of_fact(f) == 5) then
            kfact := KnowFact;
            op := Find_Operator_In_Expression(f);
            If (op != NULL and Arguments_Satisfied(op, kfact, KnowledgeBase)) then
                new_fact := Execute_Operator_Procedure(op, kfact);
                KnowFact := KnowFact ∪ { new_fact };
                Sol := Sol + ["Applying operator " + op.name, new_fact, kfact];
            End if;
        End if;
    End foreach;
    Return (KnowFact, Sol);

Đặc tả đối tượng tính toán Ma trận khả nghịch (MATRANKHANGHICH.TXT):

begin_concept: MATRANKHANGHICH[MATRANVUONG]
begin_variables
    m: int;
    n: int;
    K: array[m][n];
    INV: array[m][n];
end_variables
begin_constraints
    m = n;
    DINHTHUC(K) <> 0;
end_constraints
begin_computation_relations
    begin_relation
        flag = 0
        Mf = {K}
        rf = 1
        vf = {INV}
        expr : ` Gauss_Jordan_Inverse(K) `
        cost = 15
    end_relation
end_computation_relations
end_concept

Thuật giải tìm bao đóng đối tượng $F_{closure}(GT)$ thực hiện việc mở rộng tối đa tập sự kiện dựa trên việc lặp các quy tắc $RC1 \rightarrow RC5$:

// Thuật giải 3.1: Tìm bao đóng của một đối tượng tính toán (C-Object)
Algorithm Find_Object_Closure(GT, Object_O):
    KnowFact := GT ∪ Object_O.Facts;
    Flag := true;
    While (Flag == true) do:
        newf1 := Generate_Facts_RC1(KnowFact);
        newf2 := Apply_Substitution_Rules_RC2(KnowFact, Object_O.Rf);
        newf3 := Apply_Production_Rules_RC3(KnowFact, Object_O.Rr);
        newf4 := Solve_Equations_System_RC4(KnowFact, Object_O.Rf);
        newf5 := Execute_Internal_Behaviors_RC5(KnowFact, Object_O);
        
        NewGenerated := newf1 ∪ newf2 ∪ newf3 ∪ newf4 ∪ newf5;
        If (NewGenerated ⊆ KnowFact or NewGenerated == ∅) then
            Flag := false;
        Else
            KnowFact := KnowFact ∪ NewGenerated;
        End if;
    End do;
    Return KnowFact;

Testing và validation

Hệ thống được thử nghiệm trên tập dữ liệu gồm 45 bài toán đại số tuyến tính thuộc các lớp:

  • Xác định kiểu đối tượng (Chứng minh ma trận vuông, ma trận đối xứng, ma trận khả nghịch).
  • Tính toán giá trị giải tích (Tính định thức cấp $n$, tìm hạng ma trận $r(A)$, tìm ma trận nghịch đảo $A^{-1}$).
  • Biện luận và giải hệ phương trình tuyến tính $m$ phương trình $n$ ẩn theo định lý Kronecker-Capelli ($r(A) = r(A|B) = n$).
Dữ liệu kiểm thử mẫu:
Ma trận A: [ [1, 2, 3, 4], [4, 3, 5, 7], [5, 6, 8, 6], [2, 1, 0, 9] ]
Mục tiêu G: Xác định tính khả nghịch và tìm A^(-1)

Kết quả đo đạc thực nghiệm về hiệu năng khi áp dụng Heuristic tỉa nhánh tìm kiếm:

Không gian tìm kiếm không Heuristic:  [████████████████████] 100% (Duyệt 142 trạng thái)
Không gian tìm kiếm CÓ Heuristic:     [███████░░░░░░░░░░░░░]  34% (Duyệt 48 trạng thái)
Thời gian suy diễn trung bình giảm:   48.6%
Lớp bài toán thực nghiệm Số bài test Tỷ lệ giải đúng (%) Thời gian TB không Heuristic (s) Thời gian TB có Heuristic (s) Mức độ tối ưu thời gian (%)
Xác định ma trận vuông / khả nghịch 15 100% 0.42 0.18 57.1%
Tính định thức và ma trận nghịch đảo 15 100% 1.85 0.94 49.2%
Giải & Biện luận Hệ phương trình tuyến tính 15 93.3% 3.12 1.76 43.6%

Kết quả đạt được

  • Hoàn thiện trọn vẹn lý thuyết động cơ suy diễn trên mô hình COKB, đặc biệt là bổ sung thành công quy tắc $RCN7$ xử lý tri thức toán tử và hàm.
  • Tự động sinh ra chuỗi các bước suy diễn logic tường minh kèm biểu thức toán học tương ứng, không chỉ đưa ra đáp số mà còn cung cấp lời giải sư phạm chi tiết.
  • Tỷ lệ giải quyết thành công đạt 97.7% trên tổng số 45 bài toán mẫu thực nghiệm.

Đổi mới và đóng góp

  1. Hoàn thiện lý thuyết suy diễn COKB cho Toán tử và Hàm: Khắc phục hạn chế lớn của các phiên bản COKB trước năm 2018 (vốn chỉ áp dụng tốt cho hình học), đưa ra quy tắc hình thức $RCN7$ và cơ chế thực thi hàm tính toán đại số hai ngôi.
  2. Hình thức hóa giải thuật so khớp 12 loại sự kiện: Xây dựng bảng quy tắc toán học cho phép so khớp ngữ nghĩa đẳng thức đại số ($\text{simplify}(\text{expand}(f_1 - f_2)) = 0$), giải quyết triệt để sự nhập nhằng cú pháp trong biểu thức giải tích.
  3. Cải tiến thuật giải tìm bao đóng đối tượng ($F_{closure}$): Tích hợp việc giải hệ phương trình phụ thuộc biến ($RC4$) và kích hoạt hành vi đối tượng nội tại ($RC5$), giúp giảm kích thước không gian tìm kiếm tổng thể của hệ thống lên đến 66%.

Ứng dụng thực tế và triển khai

Kịch bản ứng dụng (Real-World Use Cases)

  • Hệ thống dạy học thông minh (Intelligent Tutoring System - ITS): Tích hợp vào các phần mềm hỗ trợ học tập môn Đại số tuyến tính bậc đại học, tự động chấm điểm và gợi ý từng bước làm bài cho sinh viên.
  • Lõi tính toán tri thức cho phần mềm Toán học: Đóng vai trò là engine suy luận logic kết hợp tính toán số trị/biểu thức, vượt trội hơn các công cụ tính toán thuần túy (chỉ cho ra kết quả cuối cùng mà không có chứng minh).
sequenceDiagram
    autonumber
    actor User as Người dùng / Sinh viên
    participant UI as Giao diện bài toán
    participant Engine as Động cơ suy diễn COKB
    participant KB as Cơ sở tri thức (TXT)
    
    User->>UI: Nhập giả thiết (F) và mục tiêu (G)
    UI->>Engine: Khởi tạo mô hình bài toán (O, F) -> G
    Engine->>KB: Nạp tri thức (C, H, R, Ops, Funcs, Rules)
    Engine->>Engine: Tìm bao đóng Fclosure và áp dụng RCN1-RCN7
    Engine->>UI: Xuất chuỗi lời giải từng bước (Sol)
    UI->>User: Hiển thị chứng minh và kết quả chi tiết

Chiến lược triển khai và Yêu cầu hệ thống

  • Môi trường thực thi: Tương thích từ Maple v17/v18 trở lên trên nền tảng Linux/Windows x86-64.
  • Cấu hình tối thiểu: CPU 2 Cores 2.0 GHz, 2GB RAM, 500MB không gian lưu trữ cho tập tin tri thức.
  • Khả năng mở rộng: Cấu trúc tệp tin .TXT độc lập cho phép chuyên gia tri thức dễ dàng mở rộng sang các miền tri thức mới (Hình học giải tích không gian, Giải tích tích phân, Vật lý lượng tử) mà không cần lập trình lại lõi suy diễn.

Hạn chế và hướng phát triển

  • Hạn chế kỹ thuật:
    • Chưa xây dựng bộ phân tích ngôn ngữ tự nhiên (NLP) tiếng Việt để tự động chuyển đổi đề bài dạng văn bản thô sang tập sự kiện COKB ban đầu.
    • Khi số lượng biến và phương trình trong hệ ma trận tăng lên quá lớn ($n > 50$), chi phí thời gian cho việc tính định thức tượng trưng (symbolic determinant) trên Maple tăng đáng kể.
  • Hướng phát triển:
    • Tích hợp mạng học sâu (Deep Learning / LLM) đóng vai trò tiền xử lý (Front-end parser) để trích xuất sự kiện từ văn bản tự nhiên.
    • Chuyển đổi mã nguồn động cơ suy diễn sang C++20 hoặc Python (SymPy) để nâng cao tốc độ tính toán song song đa luồng.
    • Mở rộng cơ sở tri thức sang Không gian Vector, Ánh xạ tuyến tính và Phương trình vi phân.

Đối tượng hưởng lợi

  • Sinh viên & Học viên: Tiếp cận phương pháp biểu diễn tri thức hiện đại, hiểu sâu cơ chế sinh lời giải tự động cho các bài toán đại số phức tạp.
  • Kỹ sư AI & Nhà phát triển phần mềm: Nhận được mẫu kiến trúc hoàn chỉnh về hệ giải bài toán thông minh dựa trên Ontology kết hợp hướng đối tượng, dễ dàng tái sử dụng mô hình tệp tin .TXT.
  • Nhà nghiên cứu khoa học máy tính: Tài liệu tham khảo học thuật giá trị về lý thuyết hợp nhất sự kiện ngữ nghĩa, thuật giải tìm bao đóng và tối ưu hóa Heuristics trong lập luận tự động.

Câu hỏi thường gặp

1. Yêu cầu kỹ thuật để triển khai và chạy hệ thống là gì?

Hệ thống yêu cầu cài đặt phần mềm tính toán khoa học Maple (từ phiên bản Maple 18 hoặc Maple 2018 trở lên) trên hệ điều hành Linux (Ubuntu/Debian) hoặc Windows 10/11. Toàn bộ cơ sở tri thức được tổ chức dưới dạng tệp văn bản mã hóa UTF-8 tiêu chuẩn.

2. Mô hình COKB xử lý vấn đề bùng nổ không gian trạng thái như thế nào?

COKB phân rã tri thức thành 6 thành phần chuyên biệt và áp dụng thuật giải tìm bao đóng $F_{closure}$ trên từng đối tượng cục bộ trước khi kích hoạt quy tắc toàn cục. Kết hợp với các quy tắc Heuristics đánh giá độ ưu tiên của luật ($cost$), không gian tìm kiếm được thu hẹp lên đến 66% so với thuật toán duyệt cạn.

3. Quy tắc RCN7 khác biệt gì so với các quy tắc suy diễn trước đây?

Trước đây, các quy tắc suy diễn trên COKB chỉ hỗ trợ thế hằng số và giải hệ phương trình đại số đơn giản. Quy tắc $RCN7$ cho phép động cơ suy diễn nhận dạng trực tiếp các toán tử 2 ngôi trong sự kiện loại 5 ($A = B + C$), kiểm tra tính tương thích của đối số và kích hoạt các thủ tục tính toán đại số ma trận tương ứng để sinh ra sự kiện mới.

4. Hệ thống có thể tích hợp với các ứng dụng Web hiện đại không?

Hoàn toàn khả thi. Động cơ có thể được tái cấu trúc thành một dịch vụ backend thông qua Maple OpenMaple API (C/Java interface) hoặc porting toàn bộ giải thuật sang Python/C++ để cung cấp RESTful API cho ứng dụng Web/Mobile.

5. Chi phí đầu tư và tiềm năng chuyển giao công nghệ?

Chi phí phát triển rất tối ưu do kiến trúc tách rời giữa động cơ suy diễn và cơ sở tri thức. Để áp dụng cho một môn học mới, nhà phát triển chỉ cần xây dựng tập tin đặc tả tri thức .TXT mới mà không cần sửa đổi mã nguồn lõi.

Kết luận

Khóa luận tốt nghiệp "Một số lớp bài toán và phương pháp suy diễn trên cơ sở tri thức COKB" của tác giả Lưu Thanh Sơn đã hoàn thiện một mắt xích lý thuyết và thực nghiệm quan trọng trong dòng nghiên cứu hệ cơ sở tri thức đối tượng tính toán. Bằng việc hình thức hóa thành công tập 12 loại sự kiện, xây dựng thuật toán hợp nhất sự kiện ngữ nghĩa và đề xuất quy tắc suy diễn toán tử $RCN7$, công trình đã chứng minh tính hiệu quả vượt trội trên miền tri thức Ma trận và Hệ phương trình tuyến tính. Đây là nền tảng vững chắc cho việc phát triển các hệ thống giáo dục thông minh và các công cụ giải toán tự động thế hệ mới.