ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÁO CÁO THU HOẠCH MÔN HỌC
BIỂU DIỄN TRI THỨC VÀ ỨNG DỤNG
ĐỀ TÀI:
MẠNG NGỮ NGHĨA CHO CƠ CHẾ SUY DIỄN
GIẢI BÀI TOÁN TAM GIÁC
GIẢNG VIÊN : PGS.TS ĐỖ VĂN NHƠN
HỌC VIÊN : ĐINH ĐỨC KHOA
MÃ SỐ : CH11002003
LỚP : CAO HỌC K6
HÀ NỘI - 12/2012
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
MỤC LỤC
PHẦN I: MỞ ĐẦU
Cùng vời nhiều ngành khoa học khác. Khoa học máy tính và Công nghệ thông
tin đã góp phần không nhỏ vào sự tiến bộ của toàn xã hội. Trí tuệ nhân tạo là một
lĩnh vực khoa học máy tính nhằm nghiên cứu phát triển các hệ thống máy tính ngày
càng thông minh hơn; hỗ trợ tốt hơn cho hoạt động xử lý thông tin và xử lý tri thức,
tính toán và điều khiển, v.v Trí tuệ nhân tạo đã xâm nhập vào nhiều mặt đời sống
xã hội và đã trở thành phương pháp rất hiệu lực để giải quyết nhiều bài toán phức tạp
trong thực tế.
Sự khác biệt giữa các hệ cơ sở tri thức và các chương trình truyền thống nằm
ở cấu trúc. Trong các chương trình truyền thống, cách thức xử lý hành vi của chương
trình đã được ấn định sẵn qua các dòng lệnh của chương trình dựa trên một thuật giải
đã định sẵn. Trong các hệ cơ sở tri thức, có hai chức năng tách biệt nhau, trường hợp
đơn giản có hai khối; khối tri thức hay còn được gọi là cơ sở tri thức và khối điều
khiển hay còn được gọi là động cơ suy diễn. Với các hệ thống phức tạp, bản thân
động cơ suy diễn cũng có thể là một hệ cơ sở tri thức chứa ccas siêu tri thức (tri thức
về cách sử dụng các tri thức khác).
Việc tách biệt tri thức khỏi các cơ chế điều khiển giúp ta dễ dàng thêm vào các

quát biểu diễn tri thức là thể hiện các mô tả về thế giới bên ngoài dưới dạng sao cho
các máy thông minh có thể đưa tới những kết luận về môi trường xung quanh nó, trên
cơ sở một cách hình thức các mô tả này, còn kỹ nghệ tri thức bao gồm trong nó các
kỹ thuật cấu trúc tri thức, suy diễn, quản trị tri thức và học tự động. Vào những năm
đầu thập kỷ 80 sự phát triển của khoa học tri thức mà các nhà nghiên cứu đã đúc kết
lại những điểm khá chung nhau và các phương pháp biểu diễn tri thức đươc quan tâm
chủ yếu là:
- Biểu diễn nhờ lôgic hình thức
- Biểu diễn nhờ hệ sản xuất
- Biểu diễn nhờ mạng ngữ nghĩa
- Biểu diễn nhờ các frame.
Trong các phương pháp biểu diễn này là tạo ra cơ sở tri thức tường minh trong
các hệ thống khoa học trí tuệ nhân tạo dựa trên tri thức, điều đó phải đòi hỏi xây
dựng các ngôn ngữ khoa học trí tuệ biểu diễn tri thức, thêm vào đó các ngôn ngữ này
phải cung cấp các công cụ truy nhập tới các sự kiện không tường minh có trong cơ sở
tri thức, nghĩa là phải bao gồm trong nó cơ chế suy diễn tự động. Như vậy trong bất
kỳ một hệ thống biểu diễn tri thức nào, bao giờ cũng phải chứa ba yếu tố: Ngôn ngữ
biểu diễn, cơ chế suy dẫn và công cụ lập cơ sở tri thức cho từng lĩnh vực cụ thể.
II.1/ Phân loại tri thức
Dựa vào cách thức con người giải quyết vấn đề, các nhà nghiên cứu đã xây
dựng các kỹ thuật biểu diễn các dạng tri thức khác nhau trên máy tính, mặc dù vậy
CH1102003 - ĐINH ĐỨC KHOA Trang 4
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
không có một kỹ thuật riêng lẻ nào có thể giải thích đầy đủ cơ chế tổ chức tri thức
trong các chương trình máy tính. Để giải quyết vấn đề, chúng ta chỉ chọ dạng biểu
diễn nào thích hợp nhất, sau đây là các dạng biểu diễn tri thức thường gặp.
Tri thức thủ tục mô tả cách thức giải quyết một vấn đề loại tri thức này đưa
ra giải pháp để thực hiện một công việc nào đó. Các dạng tri thức thủ tục tiêu biểu
thường là các luật, chiến lược, lịch trình, và thủ tục.
Tri thức khai báo cho biết một vấn đề được thấy như thế nào. Loại tri thức

- Phương pháp biểu diễn hổn hợp: Frame
Mong muốn của các chuyên gia về xử lý tri thức là tạo ra được các hệ thống
cho phép người sử dụng mô tả bài toán bằng ngôn ngữ mô tả, sau đó giải chúng theo
chế độ tương tác và hội thoại cao.
II.2.1/ Biểu diễn tri thức nhờ logic
Đây là dạng biểu diễn tri thức cổ điển nhất trong máy tính là logic, với hai
dạng phổ biến là logic mệnh đề và logic vị từ, cả hai kỹ thuật này đều dùng ký hiệu
để thể hiện tri thức và các toán tử áp lên các ký hiệu để suy luận logic. Logic đã cung
cấp cho nhà nghiên cứu một công cụ hình thức để biểu diễn và suy luận tri thức.
Phép
toán
AND OR NOT Kéo theo Tương
đương
Kí hiệu ^, &, v,, +
Logic mệnh đề biểu diễn và lập luận với các mệnh đề toán học. Mệnh đề là
một câu nhận giá trị hoặc đúng hoặc sai giá trị này gọi là chân trị của mệnh đề. Logic
mệnh đề gán một bước ký hiệu vào một mệnh đề, ví dụ A= “Xe sẽ khởi động”.
CH1102003 - ĐINH ĐỨC KHOA Trang 6
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
Khi cần kiểm tra chân trị của câu trên trong bài toán sử dụng logic mệnh đề
người ta kiểm tra giá trị của A. Nhiều bài toán sử dụng logic mệnh đề để thể hiện tri
thức và giải quyết vấn đề, bài toán loại này được đưa về bài toán xử lý các luật, mỗi
phần giải thiết và kết luận của luật có thể có nhiều mệnh đề.
IF Xe không khởi động được  A
AND Khoảng cách từ nhà đến chổ làm là xa  B
THEN Sẽ trể giờ làm  C
Luật trên có thể biểu diễn lại như sau: A^B -> C
Các phép toán quen thuộc trên các mệnh đề được cho trong bảng sau:
A B A^B A B A B A
T T F T T T T

đòi hỏi một khả năng rút ra được kết luận từ các sự kiện đã có, việc lấy ra thông tin
mới từ các thông tin đã biết và các luật là trong tâm của tập luận trong hệ chuyên gia,
quá trình lập luận được hình thức hóa trong bài toán suy luận.
II.2.2/ Bộ ba đối tượng - Thuộc tính – Giá trị
Cơ chế tổ chức nhận thức của con người thường được xây dựng dựa trên các
sự kiện (fact), xem như các đơn vị cơ bản nhất, một sự kiện là một dạng tri thức khai
báo. Nó cung cấp một số hiểu biết về một biến cố hay một vấn đề nào đó.
Một cách biểu diễn khác là nhờ sử dụng bộ ba đối tượng – thuộc tính – giá trị
(Object – Attribute – Value) để chỉ sự kiện rằng “Đối tượng” với “Thuộc tính” đã
cho có một “giá trị” nào đó.
Màu
Sơ đồ biểu diễn tri thức theo bộ ba (O-A-V)
CH1102003 - ĐINH ĐỨC KHOA Trang 8
Ghế
Nâu
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
Trong các sự kiện O – A – V một đối tượng có thể có nhiều thuộc tính với các
kiểu giá trị khác nhau hơn nữa một thuộc tính cũng có thể có một hay nhiều giá trị
chúng được gọi là các sự kiện đơn trị (single-value) hoặc đa trị (multi-value), điều
này cho phép các hệ tri thức linh động trong việc biểu diễn các tri thức cần thiết, cần
phân biệt hai đối tượng: đối tượng tĩnh và đối tượng động các đối tượng tĩnh được
lưu trong nội bộ nhớ dài hạn và khi cần được đưa vào bộ nhớ làm việc để xử lý,
ngược lại trong quá trình làm việc khi cần sẽ khởi tạo các giá trị thuộc tính của các
đối tượng động và chúng được lưu ở bộ nhớ trong phục vụ cho việc xử lý tiếp theo.
Các sự kiện không phải lúc nào cũng đảm bảo là đúng hay sai với độ chắc
chắn hoàn toàn, vì thế khi xem xét các sự kiện người ta còn sử dụng thêm một khái
niệm là độ tin cậy, phương pháp truyền thống để quản lý thông tin không chắc chắn
là sử dụng nhân tố chắc chắn CF (ceratinly factor) được dùng trong hệ MYCIN
(khoảng năm 1975).
Ngoài ra, khi các sự kiện mang tính “nhập nhằng” việc biểu diễn tri thức dựa

Chẩn đoán
IF Sốt cao
AND Ho nhiều
AND Họng đỏ
THEN Viêm họng
Thiết kế
IF Cao 1m75
AND Da sẫm
THEN Chọn áo vải sáng
AND Chọn tấm vải khổ 1m40
Mở rộng cho các luật cần thực hiện cùng một phép toán trên một tập hay các đối
tượng giống nhau lúc này cần các luạt có biến
CH1102003 - ĐINH ĐỨC KHOA Trang 10
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
IF X là nhân viên
AND Tuổi của X >65
THEN X có thẻ nghỉ hưu
Khi mệnh đề phát biểu về sự kiện hay bản thân sự kiện có thể không chắc
chắn, người ta dùng hệ số chắc chắn CF, luật thiết lập quan hệ không chính xác giữa
các sự kiện giải thiết và kết luận được gọi là luật không chắc chắn ví dụ nếu “lạm
phát cao” thì “hầu như chắc chắn lãi suất sẽ cao” luật này có thể viết lại với giá trị CF
có thể như sau.
IF Lạm phát cao
THEN Lãi suất cao, CF=0,8
Dạng siêu luật một luật với chức năng mô tả cách thức dùng các luật khác sẽ
đưa ra chiến lượt sử dụng các luật theo lĩnh vực chuyên dụng, thay vì đưa ra thông tin
mới.
IF Xe không khởi động
AND Hệ thống điện làm việc bình thường
THEN Có thể sử dụng các luật liên quan đến hệ thống điện

PHẦN III: MẠNG NGỮ NGHĨA VÀ GIẢI THUẬT LAN TRUYỀN
Như đã trình bày ở phần mở đầu [I] để máy tính có thể sử dụng được tri thức,
có thể xử lý được tri thức, chúng ta cần phải biểu diễn tri thức dưới dạng thuận tiện
cho máy tính, đó là mục tiêu của biểu diễn tri thức sau nhiều cố gắng các nhà trí tuệ
nhân tạo đã phát triển một số cách biểu diễn (thể hiện) tri thức có hiệu quả trong máy
tính đặc biệt một trong số biểu diễn mà người viết muốn nhắc đến mạng ngữ nghĩa và
tính toán lan truyền trong mạng.
III.1/ Mạng ngữ nghĩa
Mạng ngữ nghĩa là một công cụ trực quan giúp chúng ta biểu diễn được các
mối liên hệ giữa các tri thức tổng quát, khái niệm, các sự việc mà chúng có mối liên
hệ. Mạng ngữ nghĩa là một phương pháp biểu diễn tri thức đầu tiên và cũng là
phương pháp dễ hiểu, để biểu diễn một mạng ngữ nghĩa thì người ta dùng phương
pháp đồ thị, trong đó đỉnh là các đối tượng (khái niệm, tri thức, sự việc) nào đó, còn
các cung giữa các đỉnh nó thể hiện các mối liên hệ giữa các đối tượng.
Mạng ngữ nghĩa sử dụng công cụ là đồ thị nên nó thừa hưởng tất cả những
mặt mạnh của công cụ đồ thị. Các thuật toán đã được cài đặt và phát triển trên máy
CH1102003 - ĐINH ĐỨC KHOA Trang 13
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
tính, khi áp dụng chúng ta có thể giải quyết nhiều vấn đề khác nhau ở trên mạng. Cho
đến nay mạng ngữ nghĩa được ứng dụng nhiều trong hai lĩnh vực:
+ Xử lý ngữ nghĩa tự nhiên.
+ Giải các bài toán thông minh.
Người ta có thể nới rộng mạng ngữ nghĩa bằng cách thêm các nút và nối
chúng vào đồ thị, các nút mới ứng với các đối tượng bổ sung, thông thường có thể
nới rộng mạng ngữ nghĩa theo ba cách:
- Thêm một đối tượng tương tự
- Thêm một đối tượng đặc biệt hơn
- Thêm một đối tượng tổng quát hơn
Thứ nhất thêm “cách cụt” thể hiện một loại chim mới thứ hai thêm “chip”
cũng có nghĩa nó là con “sẻ” và đồng thời là “chim”, thứ ba có thể đưa ra đối tượng

• Ngưỡng kích hoạt F là một số thực nằm trong khoảng [0.0 1.0].
• Yếu tố suy biến D (Decay factor) là một số thực nằm trong khoảng [0.0, ,
1.0].
Các bước thực hiện thuật toán:
• Khởi tạo đồ thị, cài đặt tất cả các kích hoạt giá trị A[i] = 0, thiết lập một hoặc
thêm các nút gốc để kích hoạt một giá trị ban đầu lớn hơn ngưỡng F. Giá trị
khởi tạo thông thường là 1.
• Đối với mỗi node[i] chưa được kích hoạt trong đồ thị có một kích hoạt A[i]
lớn hơn giá trị node ngưỡng kích hoạt F.
• Đối với mỗi Link[i, j] kết nối node[i] với mục tiêu node[j] , điều chỉnh:
o A [j] = A [j] + (A [i] * W [i, j] * D) trong đó D là yếu tố suy biến.
• Nếu một nút nhận được một mục tiêu điều chỉnh giá trị kích hoạt của nó sẽ
vượt quá 1.0, sau đó đặt giá trị kích hoạt mới của nó là 1.0. Tương tự như vậy,
duy trì 0.0 như một giá trị ràng buộc kích hoạt thấp hơn, các nút mục tiêu của
nó sẽ nhận được giá trị điều chỉnh xuống dưới 0.0.
• Khi một nút đã kích hoạt nó có thể kích hoạt lại một lần nữa, mặc dù các biến
thể của thuật toán cơ bản cho phép bỏ qua việc lặp đi lặp lại và vòng qua đồ
thị.
• Các nút nhận được giá trị kích hoạt mới có vượt quá ngưỡng kích hoạt F được
đánh dấu để kích hoạt vào chu trình kích hoạt tiếp theo.
• Nếu kích hoạt bắt nguồn từ nhiều hơn một nút, một biến của thuật toán sẽ cho
phép đánh dấu các kích hoạt đã đi qua để phân biệt với các con đường chưa
được kích hoạt trên đồ thị.
• Thủ tục chấm dứt khi một trong hai không có thêm các nút để kích hoạt trong
trường hợp các dấu hiệu chuyển từ nhiều nguồn gốc, khi có nhiều hơn một con
đường xuất phát từ một nút. Các biến sử dụng trong thuật toán cho phép lặp
đi, lặp lại hoặc sa thải nút hoặc dòng kích hoạt trong đồ thị, chấm dứt sau khi
một trạng thái kích hoạt ổn định, đối với một số trường, được đạt tới, hoặc số
lần lặp vượt quá mức tối đa.
CH1102003 - ĐINH ĐỨC KHOA Trang 17

ABC
, δ =
¼
ACB
CH1102003 - ĐINH ĐỨC KHOA Trang 19
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
o 3 cạnh a, b, c
o 3 đường cao h
a
, h
b
, h
c

o 3 đường trung tuyến i
a
, i
b
, i
c
o Chu vi C
o Diện tích S
• Mối liên hệ:
o Tổng 3 góc α + β + δ =
π
o Chu vi C = 2P, P =
1
2
(a + b + c)
o Diện tích S =

sin
c
δ
(2) Chọn lọc thông tin:
Trong các thông tin đã cung cấp ở các bài toán trên ta có thể thấy một số thông tin
thừa không cần thiết như: 3 đường trung tuyến i
a
, i
b
, i
c
ở bài toán tam giác
Với các thông tin này hệ thống không bị mất đi độ chính xác nhưng sẽ làm cho
tốc độ suy luận giảm đi. Vậy nên cần được loại bỏ.
(3) Biểu diễn thông tin trên mạng ngữ nghĩa:
CH1102003 - ĐINH ĐỨC KHOA Trang 20
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
Hình 3-2 Mạng ngữ nghĩa cho bài toán hình tam giác
Trong mạng ngữ nghĩa trên, các ô tròn biểu thị cho các đối tượng của bài toán và
các ô vuông thể hiện mối quan hệ giữa các đối tượng.
IV.4/ Bài toán hình thang
(1) Xác định thông tin:
Xét hình thang ABCD
CH1102003 - ĐINH ĐỨC KHOA Trang 21
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
Hình 3-2 Ví dụ về hình thang
Ta xác định được các thông tin như bên dưới:
• Đối tượng:
o 4 góc α = DAB, β =ABC, δ =BCD, γ = CDA
o Cạnh a, b, c, d

h
- a
o Chiều dài cạnh d = C – (a + b + c)
o Chiều dài cạnh d =
h
sin
γ
o Góc γ = arsin(
h
d
)
o Góc γ = 2π – (α + β + δ )
o Góc δ = arsin(
h
b
)
o Góc δ = 2π – (α + β + γ )
o Góc α =
2
π
+ arsin(
2 2
d h
d
−
)
o Góc α = 2π – (δ + β + γ )
o Góc β =
2
π

Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
Thông tin về hai cạnh song song, không giúp ta trong việc tính toán.
Những thông tin này có thể lượt bỏ trong sơ đồ mạng ngữ nghĩa cho bài toán
hình thang này.
(3) Biểu diễn thông tin trên mạng ngữ nghĩa:
Hình 3-2 Mạng ngữ nghĩa cho bài toán hình thang
IV.5/ Biểu diễn thông tin trên máy
Vấn đề khó khăn nhất trong việc thể hiện nội dung của mạng ngữ nghĩa trên
máy tính là việc không thể xác định được giá trị nào trên mạng đã xác định và giá trị
CH1102003 - ĐINH ĐỨC KHOA Trang 24
Mạng ngữ nghĩa cho cơ chế suy diễn, giải bài toán tam giác
nào cần phải xác định. Tuy nhiên vì các đối tượng trên mạng ngữ nghĩa có các mối
quan hệ khép kín nên chỉ cần có vừa đủ các giá trị cần thiết thì các đối tượng còn lại
cũng sẽ được xác định.
Trong hai bài toán nêu trên, các đối tượng được xác định dựa trên các mối liên
hệ và các đối tượng đã được xác định có trong mối liên hệ đó.
Trong bài toán hình tam giác, ta có 11 đối tượng cần xác định lần lượt là 3
cạnh, 3 góc, 3 đường cao, chu vi và diện tích. Thuật toán đơn giản được áp dụng
trong bài toán này đó là lặp lại 11 lần các mối liên hệ để tìm ra giá trị cho các đối
tượng trong mối liên hệ đó. Nếu có (n-1) đối tượng đã xác định thì sẽ xác định được
đối tượng còn lại.
Trong bài toán hình thang, các đối tượng cần xác định lần lượt là 4 cạnh, 4
góc, đường cao, chu vi và diện tích. Cũng như bài toán tam giác, các đối tượng được
xác định thông qua các mối liên hệ giữa các đối tượng. Và cũng với (n-1) đối tượng
đã xác định thì đối tượng còn lại cũng được xác định.
Bài toán hình tam giác:
Người dùng cần nhập vào một số thông tin đối tượng đã xác định. Với các đối tượng
chưa xác định, hãy để trống nội dung. Và người dùng muốn tính toán những thông số
nào của bài toán, lựa chọn vào mục chọn giát trị cần tính. Khi các thông số đã xác
định, người dùng chọn tính để thể hiện kết quả. Nếu không thể tính toán ra kết quả,