ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN
BIỂU DIỄN TRI THỨC VÀ SUY LUẬN
ĐỀ TÀI
TÌM HIỂU MÔ HÌNH COKB- ONTO
SUY DIỄN SỬ DỤNG BÀI TOÁN MẪU
GVHD: PGS.TS. Đỗ Văn Nhơn
SVTH: Nguyễn Hải Yến
MSSV: CH1301074
LỚP : Cao học CNTT khoá 9
TP. Hồ Chí Minh, ngày 29 tháng 03 năm 2014
t
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
LỜI NÓI ĐẦU
Biểu diễn tri thức có vai trò quan trọng trong việc thiết kế hệ thống CSTT
(KBS) và hệ chuyên gia (ES), đặc biệt là trong lĩnh vực giáo dục. Có rất nhiều mô
hình và phương pháp khác nhau để biểu diễn tri thức (mô hình logic vị từ, mô
hình mạng ngữ nghĩa, mô hình hệ luật dẫn, mô hình mạng nơ-ron, đồ thị khái
niệm,… ) đã được đề xuất và áp dụng trong nhiều lĩnh vực của khoa học. Nhưng
những mô hình này có những hạn chế nhất định trong biểu diễn và suy luận trên
các tri thức phức tạp. Ontology là một hướng đang được nghiên cứu và phát triển.
Ontology về tri thức các đối tượng tính toán COKB-ONTO là mô hình được sử
dụng rất hiệu quả trong việc biểu diễn cơ sở tri thức phức tạp. COKB-ONT bao
gồm mô hình, ngôn ngữ đặc tả, ngôn ngữ truy vấn và kỹ thuật xử lý hay suy diễn
Sau khi mô hình hóa cho cơ sở tri thức thì việc thiết kế một bộ suy diễn
trên cơ sở tri thức đó ( thiết kế thuật toán suy diễn) là một bước rất quan trọng.
Nó là nhân tố ảnh hưởng lớn đến hiệu quả xử lý bài toán. Để cải thiện thời gian
suy diễn thì phương pháp suy diễn kết hợp hueristic hay suy diễn sử dụng các bài
toán mẫu được đề xuất. Và sau đây là bài thu hoạch của em về “ Tìm hiểu mô
hình COKB-ONTO và suy diễn sử dụng các bài toán mẫu”.

phân loại, áp dụng cơ chế kế thừa. Có các loại khái niệm sau:
− Khái niệm nền: kiểu boolean, số tự nhiên, số nguyên, số hữu tỉ, số thực,
tập hợp và danh sách hay một số kiểu tự định nghĩa.
− Khái niệm cơ bản: có cấu trúc rỗng hoặc có một số thuộc tính có khái
niệm nền. Ví dụ khái niệm đối tượng DIEM có kiểu mô tả không có cấu
trúc thiết lập. Các khái niệm này làm nền cho các khái niệm cấp cao
hơn.
− Khái niệm cấp 1: Các đối tượng này chỉ có các thuộc tính kiểu khái
niệm nền và có thể được thiết lập trên một danh sách nền các đối tượng
cơ bản. Ví dụ: đối tượng DOAN[A,B] trong đó A, B là các đối tượng cơ
bản loại DIEM, thuộc tính a biểu thị độ dài đoạn thẳng có kiểu tương
ứng là “real”.
SVTH : CH1301074 – Nguyễn Hải Yến 4
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
− Khái niệm cấp 2: có các thuộc tính là khái niệm nền và khái niệm cấp 1,
có thể thiết lập từ danh sách các khái niệm nền hoặc cơ bản. Mỗi khái
niệm cấp 2 là một đối tượng tính toán gồm các thành phần:
(Name, Constructs, Isa, Attrs, Constraints, F, Facts, Rules)
Trong đó:
− Name: tên của khái niệm
− Constructs: các thuộc tính xác định khái niệm
− Isa: phân cấp khái niệm
− Attrs: tập hợp các thuộc tính của khái niệm
− Constraints: tập hợp các điều kiện ràng buộc trên các thuộc tính
− F: tập hợp các quan hệ suy diễn tính toán
− Facts: tập hợp các tính chất hay các sự kiện vốn có của khái niệm
− Rules: tập hợp các luật suy diễn trên các sự kiện liên quan đến các thuộc
tính cũng như liên quan đến bản thân khái niệm.
Ví dụ : Tri thức về tam giác gồm các yếu tố như: 3 cạnh a, b, c; 3 góc tương
ứng A, B, C; 3 đường cao tương ứng ha, hb, hc; diện tính S; chu vi P; Các công

− Facts: các sự kiện định nghĩa quan hệ.
Quan hệ có tính chất: phản xạ, đối xứng, phản xứng và bắc cầu.
Ví dụ : Quan hệ vuông góc giữa hai đường thằng được mô tả như sau:
Name: VUONG
Args: a,b: DUONGTHANG
Facts: A, B là hai điểm; A thuộc a và A không thuộc b; B thuộc b và B không
thuộc a; Góc tạo bởi A, B và giao điểm của a, b là góc vuông.
SVTH : CH1301074 – Nguyễn Hải Yến 6
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
1.1.4. Tập các hàm
Hàm thể hiện các quy tắc tính toán trên các loại khái niệm. Có hai loại:
− Hàm cơ bản: các hàm trên số tự nhiên, số nguyên, số hữu tỉ, số thực và
số phức.
− Hàm cấp n (n>0): được mô tả bằng tập các sự kiện và trong cấu trúc mô
tả bao gồm các khái niệm, quan hệ, hàm và toán tử. Trong cấu trúc mô
tả phải xuất hiện ít nhất các khái niệm, quan hệ, hàm và toán tử có cấp
n.
Mỗi hàm gồm các thành phần: (Name, Args, Return, Facts)
Trong đó:
− Name: tên của hàm
− Args: đối số của hàm là các đối tượng thuộc kiểu khái niệm.
− Return: khái niệm trả về của hàm
− Facts: các sự kiện định nghĩa hàm.
Ví dụ : Hàm xác định giao điểm của hai đường thẳng
Name: GIAODIEM
Args: a,b: DUONGTHANG
Return: X: DIEM
Facts: X thuộc a và X thuộc b
1.1.5. Tập các toán tử
Gồm các phép toán trên các biến thuộc các loại khái niệm. Có hai loại:

Name: “TAM_GIAC_BANG_NHAU”
Kind: “BANG_NHAU”
Vars: tg1, tg2: TAMGIAC
Hypothesis: 3 cạnh của tg1 bằng với 3 cạnh tương ứng của tg2
Facts: tg1 = tg2
SVTH : CH1301074 – Nguyễn Hải Yến 8
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
1.2. Các loại sự kiện trong mô hình COKB-ONTO
Có 11 loại sự kiện :
• Sự kiện loại 1: Sự kiện thông tin về loại của đối tượng.
Cấu trúc sự kiện:
[<đối tượng>, <loại đối tượng>]
Ví dụ: Tam giác cân ABC được định nghĩa như sau :
[TAMGIAC[A,B,C], “TAMGIACCAN”].
• Sự kiện loại 2: Sự kiện về tính xác định của một đối tượng hay của một thuộc
tính của đối tượng.
Cấu trúc sự kiện:
<đối tượng>|<đối tượng >.<thuộc tính>
Ví dụ: Trong tam giác ABC ta có các cạnh AB, AC, BC và các góc ABC,
góc BAC và góc ACB được định nghĩa như sau:
− Các cạnh: DOAN[A,B], DOAN[A,C], DOAN[B,C].
− Các góc: GOC[A,B,C], GOC[B,A,C], GOC[A,C,B].
• Sự kiện loại 3: Sự kiện về tính xác định của một đối tượng hay của một thuộc
tính của đối tượng thông qua biểu thức hằng.
Cấu trúc sự kiện:
<đối tượng> | <đối tượng >.<thuộc tính> = <biểu thức hằng>
Ví dụ: DOAN[A,B].a = 5; GOC[A,B,C] = Pi/2.
• Sự kiện loại 4: Sự kiện về sự bằng nhau của một đối tượng hay một thuộc tính
của đối tượng với một đối tượng hay một thuộc tính khác.
Cấu trúc sự kiện:

Ví dụ : GOC[A,B,C] = GOC(d1, d2), H1 = HINHCHIEU(A, d)
SVTH : CH1301074 – Nguyễn Hải Yến 10
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
• Sự kiện loại 10: Sự kiện về sự bằng nhau của một hàm với một hàm khác.
Cấu trúc sự kiện:
<hàm> = <hàm>
Ví dụ: KHOANGCACH(d,d1) = KHOANGCACH(d1,d2)
• Sự kiện loại 11: Sự kiện về sự phụ thuộc của một hàm theo các hàm hay các đối
tượng khác thông qua một công thức tính toán.
Cấu trúc sự kiện:
<hàm> = <biểu thức theo các hàm hay các đối tượng>
Ví dụ: GOC(d,d1) = GOC(d,d2) + GOC(d,d3).
1.3. Mô hình bài toán
1.3.1. Bài toán
Dựa vào mạng các các đối tượng tính toán , ta có mô hình bài toán của
ontology COKB-ONT gồm 3 thành phần:
O = {O
1
, O
2
, . . ., O
n
},
F = {f
1
, f
2
, . . ., f
m
},

2
, , t
m
] là một danh sách các phần tử trong F ∪ O. Ký hiệu A0
= A, A
1
= t
1
(A
0
), . . ., A
m
= t
m
(A
m-1
), và D(A) = A
m
. Ta có A
0
⊆ A
1
⊆ . . . ⊆ A
m
=
D(A) ⊆ M.
Một vấn đề H→G được gọi là khó thể giải được nếu tồn tại một danh sách
D ⊆ F ∪ O như là D(A) ⊇ B. Trong trường hợp này, ta nói D chính là giải pháp để
giải quyết vấn đề trên.
Thuật toán sau dùng để tìm bài giải cho một H→G trên mạng các đối tượng

begin
Select O
i
∈ O such thatO
i
(H) ≠ H;
if (the selection is successful) then
begin
H ← O
i
(H);
Add O
i
to Solution;
if (G ⊆ H) then
begin
Solution_found ← true;
goto step 5;
end;
else
goto step 3;
end;
end;
Step 5: if not Solution_found then
There is no solution found;
else
Solution is a solution of the problem;
Ví dụ: xem xét mạng các đối tượng tính toán (O, F) trong ví dụ ở phần trước, và
vấn đề H→G, trong đó H = {O
1

2
.c , O
3
.a },
M(f
5
) = { O
1
.α , O
2
.α },
SVTH : CH1301074 – Nguyễn Hải Yến 13
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
M = { O
1
.a, O
1
.b, O
1
.c, O
1
.A, O
2
.b, O
2
.c, O
2
.A , O
2
.a, O

1
O
 →
A
2

1
f
 →

A
3

2
f
 →
A
4

3
f
 →
A
5

4
f
 →

A

.A, O
2
.A, O
1
.b, O
1
.c },
A
3
= {O
1
.a , O
1
.A, O
2
.A, O
1
.b, O
1
.c, O
3
.a},
A
4
= {O
1
.a , O
1
.A, O
2

= {O
1
.a , O
1
.A, O
2
.A, O
1
.b, O
1
.c, O
3
.a, O
4
.a, O
2
.b, O
2
.c},
A
7
= {O
1
.a , O
1
.A, O
2
.A, O
1
.b, O

Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
MAP
SERIES
FUNCTION
DERIVATION
INITIAL_FUNCTION

end_Objects
− Tập tin HIERARCHY.txt lưu trữ các sơ đồ Hasse đại diện cho thành
phần H của mô hình COKB.
begin_Hierarchy
[<high-order object>, <low-grade object>]
[<high-order object>, <low-grade object>]

end_Hierarchy
Ví dụ
begin_Hierarchy
INJECTION, MAP
SURJECTION, MAP
BIJECTION, MAP
IDENTITY_MAPPING, MAP
POWER_FUNCTION, FUNCTION
EXPONENTIAL, FUNCTION
LOGARIT_FUNCTION, FUNCTION
POSITIVE_SERIES, SERIES
FUNCTIONS_SERIES, SERIES

end_Hierarchy
− Các tập tin RELATIONS.txt và RELATIONS_DEF.txt lưu trữ các đặc
điểm kỹ thuật của các quan hệ (thành phần R của mô hình COKB).

begin_contains
<path to file which stores object content>
SVTH : CH1301074 – Nguyễn Hải Yến 16
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
end_contains
end_object
Ví dụ:
COLLECTION.txt:
begin_object: COLLECTION
begin_variables:
n: NUMBER_OF_ITEM
A: ARRAY#LIST_OF_ITEM
end_variables
begin_contains
\Contains_Object\COLLECTION
end_contains
end_object
− Các tập tin FUNCTIONS.txt và FUNCTIONS_DEF.txt lưu trữ các đặc
điểm kỹ thuật của các hàm (thành phần funcs của mô hình COKB).
Begin_Functions
Begin_Function<name of function>([<list of
arguments>])
<argument>:<kind>
Return <variable result>:<kind>
Begin_description
<path to the file which describes function>
End_description
End_Function
Begin_Function<name of function>([<list of
arguments>])

Begin_Method< name of method>
Begin_description
<path to the file which describes method>
End_description
End_Method
SVTH : CH1301074 – Nguyễn Hải Yến 18
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
Begin_Method<name of method>
Begin_description
<path to the file which describes method>
End_description
End_Method

End_Methods
Ví dụ :
Begin_Methods
Begin_Method INDETERMINATE_FORM_ELIMINATION
Begin_description
\Contains_Object\
INDETERMINATE_FORM_ELIMINATION
End_description
End_Method
Begin_Method FUNCTION_EXPLORATION_PROCESS
Begin_description
\Contains_Object\
FUNCTION_EXPLORATION_PROCESS
End_description
End_Method

End_Methods

− Tập tin SOMEOBJECTS.txt lưu trữ các đối tượng nhất định.
• Giai đoạn 4: Mô hình hóa các vấn đề và thiết kế thuật toán. Vấn đề được
trình bày bằng cách sử dụng một mô hình được gọi là mạng lưới của C-
objects. Nó bao gồm ba bộ dưới đây.
O = {O1, O2, . , On}.
F = {f1, f2,. . Fm.},
SVTH : CH1301074 – Nguyễn Hải Yến 20
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
Goal = {g1, g2,. . , Gm}.
Trong mô hình trên, tập O bao gồm n C-objects, F là tập hợp các sự kiện
được đưa ra trên các đối tượng, và Goal bao gồm các mục tiêu.
Việc thiết kế các thuật toán suy luận để giải quyết vấn đề và thiết kế giao
diện của hệ thống có thể được phát triển bởi ba bước cho mô hình:
− Bước 1: Phân loại bài toán chẳng hạn như sườn bài, bài toán xác định
hoặc chứng minh của một sự kiện, các bài toán tìm kiếm các đối tượng
hoặc sự kiện, vv
− Bước 2: Phân loại các sự kiện và trình bày dựa trên các loại sự kiện của
mô hình COKB.
− Bước 3: Mô hình hóa phân loại các bài toán trong bước 1 và 2. Từ các
mô hình của từng loại, chúng ta có thể xây dựng một mô hình chung
cho các bài toán, cho hệ thống để giải quyết chúng.
Kỹ thuật cơ bản để thiết kế các thuật toán suy luận là sự thống nhất của các sự
kiện. Dựa trên các loại sự kiện và cấu trúc của nó, sẽ có tiêu chuẩn cho sự thống
nhất
Sau đó, nó tạo ra các thuật toán để kiểm tra sự thống nhất của hai sự kiện.
Công việc quan trọng tiếp theo là làm nghiên cứu về chiến lược khấu trừ để giải
quyết các bài toán trên máy tính. Điều khó khăn nhất là mô hình cho thử nghiệm,
cho phản ứng hợp lý, và trực giác của con người để tìm các quy tắc rút kinh
nghiệm, có thể bắt chước tư duy của con người để giải quyết bài toán.
• Giai đoạn 5: Tạo một ngôn ngữ truy vấn cho mô hình.Ngôn ngữ giúp thiết

SVTH : CH1301074 – Nguyễn Hải Yến 22
Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
- {…} : có thể lặp lại với số lần tùy ý.
Ví dụ:
<số>::= -<số thập phân>|<số thập phân>
<số thập phân> ::= <dãy chữ số> | <dãy chữ số>.<dãy chữ số>
<dãy chữ số> ::= <chữ số> | <chữ số><dãy chữ số>
<chữ số> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<If-stm> ::= IF <Expression> THEN <stms> [ELSE <Stms> ] end
1.6.2. Định nghĩa C-Object
Khái niệm C-Object được định nghĩa trong cặp từ khóa COBJECT,
ENDCOBJECT. Mỗi khái niệm có một tên duy nhất. Khi định nghĩa một khái
niệm C-Object mới, có thể định nghĩa phân cấp khái niệm đó qua từ khóa ISA.
cobject-type ::= COBJECT name
[description]
[isa]
[attributes]
[constructs]
[constraints]
[crelations]
[facts]
[rules]
ENDCOBJECT
• Mô tả khái niệm
description ::= DESCRIPTION: string;
• Thuộc tính
Hầu hết các khái niệm đều có thuộc tính. Các giá trị thuộc tính có kiểu cơ
bản (số nguyên, số thực…) hoặc có kiểu đối tượng C-Object. Khai báo thuộc tính
của khái niệm bắt đầu bằng từ khóa ATTRIBUTE và nằm trong phần định nghĩa
khái niệm.

Biểu diễn tri thức và suy luận PGS.TS Đỗ Văn Nhơn
m > 0;
n > 0;
ENDCONSTRAINT

ENDCOBJECT
• Quan hệ tính toán
Các quan hệ tính toán thể hiện mối liên hệ giữa các thuộc tính của khái
niệm đang định nghĩa. Có thể đặt trong khai báo khái niệm COBJECT hoặc định
nghĩa thành một tập riêng. Nếu đặt trong COBJECT thì phải đặt trong từ khóa
CRELATION.
crelations ::= CRELATION:
crelation-def+
ENDCRELATION;
crelation-def ::= CR name;
MF: name <, name>*;
MFEXP: equation;
ENDCR;
equation ::= expr = expr
Ví dụ: khai báo các mối quan hệ suy diễn tính toán trong khái niệm tam giác
của hình học phẳng.
CRELATION:
CR r1;
MF: GocA, GocB, GocC;
MFEXP: GocA + GocB + GocC = Pi;
ENDCR;
CR r2;
MF: a, b, c, GocA;
SVTH : CH1301074 – Nguyễn Hải Yến 25