- 4 -
gia. Dựa theo nền tảng lý thuyết cơ bản đợc giới thiệu trong chơng 1, các độ
đo tin cậy, độ đo hợp lý đợc trình bày. Khái niệm về mệnh đề không rõ ràng
và cách ớc lợng giá trị đúng đắn của một mệnh đề đợc xem xét tơng đối
kỹ lỡng. Cách tiếp cận logic và tiếp cận hàm xây dựng các mô hình suy luận
trong hệ chuyên gia từ các tiền đề không chắc chắn sử dụng các luật Modus
ponens và Modus tollens đã đợc nghiên cứu khá cơ bản trong chơng này.
- "Tìm kiếm tri thức và độ đo gần đúng" là tiêu đề của chơng 3. Nội
dung của chơng nêu lên quan điểm các độ đo gần đúng cũng là kết quả của
khai phá dữ liệu và tìm kiếm tri thức. Các nội dung cơ bản của tìm kiếm tri
thức mà một trong những tri thức đó là các độ đo trong lĩnh vực lập luận gần
đúng đã đợc trình bày. Một số độ đo liên quan đến lĩnh vực lập luận xấp xỉ,
đặc biệt các độ đo liên quan đến khái niệm tập thô đợc hệ thống hóa. Giá trị
tìm đợc từ các độ đo nói trên cho phép đa ra một số đánh giá về độ tin cậy
trong suy luận gần đúng.
- Chơng 4 với tiêu đề "Đề xuất một độ đo gần đúng và áp dụng" là
bớc phát triển nội dung của chơng 3. Độ đo đợc đề xuất tuy cha đợc
đánh giá so sánh với các độ đo ở chơng 3 song độ đo đó vẫn có ý nghĩa trong
một lớp mô hình không quá hạn hẹp.
Luận án này hoàn thành đợc trớc hết là nhờ có sự giúp đỡ hớng dẫn
khoa học tận tình của PTS. Hà Quang Thụy, PTS. Đỗ Văn Thành. Vì vậy, với
tất cả tấm lòng của mình tôi xin bầy tỏ lòng biết ơn sâu sắc của mình tới hai
ngời thầy đã trực tiếp giúp đỡ hớng dẫn tôi làm luận án. Và tôi cũng xin
chân thành gửi lời cám ơn của mình tới các thầy cô giáo khoa Công nghệ
thông tin, các thầy cô giáo thuộc Phòng Đào tạo sau đại học-trờng Đại học
Khoa học tự nhiên đã tạo mọi điều kiện giúp đỡ tôi trong suốt quá trình học.
Ngoài ra tôi cũng vô cùng cảm ơn mọi ngời trong gia đình và các bạn bè thân
của tôi, đã cho tôi nhiều sự động viên khích lệ để tôi có thể hoàn thành luận án
của mình.
- 5 -
Với tất cả mọi tập thể và cá nhân đã giúp đỡ tôi ở trên, tôi xin chân
thành gửi cám ơn của mình tới tất cả mọi ngời.
- 6 -
Chơng 1
Tập mờ và các độ đo không chính xác
1. độ đo khả năng và tập mờ
Một trong những cách tiếp cận không truyền thống đối với tính không
chính xác và tính không chắc chắn là cách tiếp cận tới phép đo khả năng.
Trớc hết, chúng ta xem xét các khái niệm tính không chính xác và tính
không chắc chắn.
1.1. khái niệm về tính không chính xác và tính không chắc chắn
Tính không chính xác và tính không chắc chắn có thể đợc coi là hai
khía cạnh cơ bản của tính chất xác thực liên quan đến thông tin không hoàn
hảo. Một mục (gói) thông tin có thể là đợc trình bầy nh là một mệnh đề
logic và một kho tri thức đợc thu gom từ các mục thông tin từ các cá nhân
(hoặc một hệ thống máy tính, hoặc một nhóm cá nhân) và liên quan đến ít
nhất một vấn đề.
Những khẳng định xuất hiện trong quá trình biểu diễn thông tin có thể
đợc giải thích nh là những tập con của một miền tham khảo. Một mệnh đề
cũng có thể đợc coi là một xác nhận liên quan tới sự xuất hiện của một sự
kiện. Những sự kiện nh vậy có thể tự đợc trình bầy nh là những tập con
của miền tham khảo, vì vậy đợc gọi là sự kiện chắc chắn. Chúng ta có ba
cách tơng đơng để thu thập các mục thông tin: hoặc dựa theo cấu trúc (khía
cạnh logic), hoặc dựa theo nội dung mục thông tin (khía cạnh lý thuyết tập),
hoặc dựa theo mối liên hệ của các mục thông tin với các sự kiện thực (khía
cạnh thực tế).
Theo quan điểm thực tế, một mục thông tin đợc định nghĩa là một bộ-
bốn (thuộc tính, đối tợng, giá trị, độ tin cậy).
- 7 -
Đối tợng (object) chỉ ra đợc phần tử trong một tập tổng thể các đối
tợng đang đợc chúng ta quan tâm, nghiên cứu. Trong mục thông tin, thành
phần đối tợng đợc trình bày là tên đối tợng cụ thể liên quan đến mục thông
tin đã cho.
Thuộc tính (attribute) đợc đề cập nh một hàm gắn một giá trị (hoặc
một tập giá trị) với đối tợng (object). Thuộc tính thờng liên quan đến một
"tính chất" nào đó của các đối tợng đang đợc xem xét.
Giá trị (value) thuộc về một tập con của vùng tham khảo liên quan với
thuộc tính. Trong mục thông tin, thành phần giá trị là một phần tử (hoặc một
tập con các phần tử) liên quan đến đối tợng cụ thể trong mục thông tin.
Độ tin cậy (confident) xác định độ xác thực của mục thông tin.
Mục thông tin có thể đợc mở rộng theo hớng mỗi một thành phần
trong đó có thể là tổ hợp (một vài đối tợng, một vài thuộc tính, mảng n-tính
chất, các mức độ tin cậy khác nhau).
Trong ngữ cảnh này, chúng ta có thể nhận thấy sự phân biệt rõ ràng
khái niệm không chính xác (imprecision) với khái niệm không chắc chắn
(uncertainty): tính không chính xác liên quan tới nội dung một mục thông tin
(thành phần giá trị), còn trong khi đó, tính không chắc chắn liên quan tới tính
đúng đắn của mục thông tin, đợc hiểu nh là tính xác thực (thành phần tin
cậy).
* Tính không chắc chắn
Tính không chắc chắn của một mục thông tin có thể đợc đánh giá
thông qua những từ nh: có thể (probable), khả năng, cần thiết, hợp
lý hoặc đáng tin mà chúng ta mong muốn cố gắng gán cho chúng một ý
nghĩa chính xác nào đó. Mô hình có thể đã từng đợc nghiên cứu rộng rãi và
nó liên quan tới hai ý nghĩa khác nhau. ý nghĩa đầu tiên là ý nghĩa vật lý, ràng
buộc tới các thí nghiệm thống kê, và liên quan tới tần số xuất hiện của một sự
- 8 -
kiện. ý nghĩa thứ 2 (epistemic) là: ở đây có thể nói đến một cách đánh
giá chủ quan nào đó.
Đối với những mô hình khả năng và cần thiết, ta nhấn mạnh tính
đối ngẫu của chúng, nếu một sự kiện là cần thiết, thì sự kiện đối ngẫu là
không có khả năng. Trái ngợc với khái niệm có thể và khả năng, khái
niệm cần thiết thờng xuyên đợc coi nh là phạm trù tất cả hoặc không có
gì. Nhng, cũng giống nh có thể, khả năng có hai cách giải thích: vật
lý, và epistemic. Mặt khác cần thiết là một khái niệm mạnh hơn nhiều,
trong mỗi ý nghĩa vật lý hoặc epistemic . Những khái niệm hợp lý và
đáng tin là đặc biệt epistemic và liên quan lần lợt đến các khái niệm
khả năng và cần thiết. Từng khái niệm tơng ứng tới một cách thức suy
luận dựa trên một kho tri thức đợc đa ra: bất cứ điều gì mà có thể suy luận
từ kho tri thức là đáng tin; bất cứ điều gì mà không mâu thuẫn với kho tri
thức là hợp lý (khía cạnh qui nạp).
Dới đây là một vài ví dụ về những mệnh đề không chắc chắn:
- Có thể Nam cao ít nhất 1.70 m.
(độ cao, Nam, 1.7 m, có thể)
-Xác suất lợng ma ngày mai đạt10 mm là 0.5
(lợng, ma ngày mai, 10 mm, xác suất = 0.5)
* Tính không chính xác
Một mục của thông tin sẽ đợc gọi là chính xác khi tập con tơng ứng
với thành phần giá trị không thể chia nhỏ thêm. Dựa trên khía cạnh của
thông tin đang đợc nhấn mạnh, chúng ta có thể phát biểu một mệnh đề sơ
cấp, của một singleton (khía cạnh lý thuyết tập), hoặc là một sự kiện cơ bản.
Tính chính xác dựa trên cách xác định miền tham khảo. Trong một số trờng
hợp, chúng ta có thể phát biểu thông tin không chính xác (imprecise).
Trong ngôn ngữ tự nhiên có những từ liên quan tới tính không chính
xác, ví dụ nh không rõ ràng, mờ, tổng quát. Tổng quát cũng là một
- 9 -
dạng không chính xác giống với quá trình trừu tợng hoá. Một mục thông tin
đợc gọi là tổng quát nếu nó chỉ dẫn một lớp đối tợng mà các đối tợng đó
cùng biểu diễn một tính chất chung. Nhng giữa tính không rõ ràng và tính
mờ trong một mục thông tin là không có một ngăn cách rõ ràng khi xem xét
tập giá trị đợc gắn tới các đối tợng liên quan.
1.2 Độ đo tin tởng (confidence)
Trong việc nghiên cứu kho tri thức không chính xác và không chắc
chắn, sự kiện là tập con của một tập tham khảo cho trớc.
Tập rỗng đợc đồng nhất với sự kiện không có khả năng.
Giả sử rằng với một sự kiện A cho tơng ứng với một số thực g(A)
đợc gọi là độ tin tởng về khả năng xuất hiện sự kiện A (qui ớc, g(A) tăng
cùng với sự tăng độ tin cậy). Thực tế g(A) đợc cung cấp từ ngời sở hữu kho
tri thức (hoặc từ một thủ tục xử lý dữ liệu đợc áp dụng đối với thông tin đợc
lu giữ trong bộ nhớ của một hệ thống máy tính).
Hơn nữa, nếu A là một sự kiện chắc chắn thì g(A)=1, và nếu A là một
sự kiện không có khả năng, thì g(A)=0, đặc biệt
g()=0 và g()=1 (1.1)
Tuy nhiên, g(A)=1 (hoặc 0) không nhất thiết có nghĩa là A là chắc chắn
(hoặc không có khả năng).
Tiên đề 1.1 (Tiên đề đơn điệu yếu):
Giả sử là tập tham khảo, với mọi sự kiện A thì g(A) đo độ tin
tởng khả năng xuất hiện sự kiện A. Khi đó:
A B g(A) g(B) (1.2)
Định nghĩa 1.1 (độ đo confident):
- 10 -
Giả sử là tập tham khảo, với mọi sự kiện A thì g(A) đo độ tin
tởng khả năng xuất hiện sự kiện A. Khi đó nếu g thoả mãn tiên đề đơn điệu
yếu (tiên đề 1.1) thì g đợc gọi là độ đo confident.
Tiên đề 1.2 (Tiên đề liên tục):
Khi là một tập tham khảo vô hạn, khi đó với mọi dãy lồng nhau (A
n
)
n
các tập, giả sử:
A
0
A
1
A
n
, hoặc A
0
A
1
A
n
thì
(
)
n
Aglim
n
=
()
n
Alimg
n
(1.3)
Một độ đo confidence đợc coi là thoả mãn tiên đề liên tục nếu nó thỏa
mãn ít nhất một hoặc hai kiểu dãy tăng hoặc giảm.
1.2.1. độ đo khả năng và độ đo cần thiết
Những bất đẳng thức dới đây là hệ quả trực tiếp của tiên đề đơn điệu
(1.2), và liên quan tới các phép hợp (AB) và giao (AB) của các sự kiện:
A,B , g(AB) max (g(A), g(B))
g(AB) min (g(A), g(B))
Một trong những bài toán đặt ra là tìm kiếm một cách tự nhiên, những
trờng hợp hạn chế các phép đo confidence. Sau đây ta sẽ giới thiệu hai độ đo
khả năng và độ đo cần thiết.
*Độ đo khả năng:
Định nghĩa 1.2:
Ký hiệu là một độ đo confident thoả mãn:
A,B, (AB) = max ((A), (B)) (1.4)
Khi đó đợc gọi là độ đo khả năng, trong đó A, B không nhất thiết
phải là các tập rời nhau.
- 11 -
Dễ dàng kiểm tra nhận thấy rằng nếu (1.4) là đúng đối với mọi cặp A, B
rời nhau (AB = ) thì nó đúng cho mọi cặp các sự kiện. Từ nhận định này,
việc kiểm tra một độ đo có là độ đo khả năng hay không chỉ hạn chế trên các
cặp tập rời nhau.
Sự tồn tại độ đo khả năng có thể đợc khẳng định từ cách xây dựng một
độ đo khả năng nh sau:
- Giả sử rằng E là một sự kiện đợc coi là chắc chắn. Một hàm
lấy giá trị trong {0, 1} và thoả mãn (1.4), là dễ dàng đợc định nghĩa nh sau:
(A) = 1 nếu AE
= 0 nếu AE =
Hiển nhiên đợc xây dựng nh vậy là một độ đo khả năng
Tính chất 1.1:
Nếu A và
A là hai sự kiện trái ngợc (A là phần bù của A trong ), khi
đó ta có:
max((A), (
A )) =1
Tính chất trên có thể đợc chứng minh dễ dàng nh sau:
max((A), (
A
)) = (A
A
) = () = 1
Định nghĩa 1.3:
Giả sử là hữu hạn, khi đó mọi độ đo khả năng có thể đợc định
nghĩa dới dạng theo giá trị của nó trên các phần tử của nh sau:
A (A) = sup {()| A} (1.5)
trong đó () = ({}); là một ánh xạ từ vào [0, 1] đợc gọi là phân phối
khả năng.
Định nghĩa 1.4:
là một phân phối khả năng. Khi đó đợc gọi là chuẩn hoá nếu
, () = 1 (1.6)
- 12 -
vì () = 1.
Trên thực tế, chúng ta luôn luôn bắt đầu với một phân phối khả năng và
xây dựng nhờ (1.5).
Nói chung, độ đo khả năng không thoả mãn tiên đề liên tục (1.3) đối
với dãy các tập lồng nhau giảm dần.
Tính chất 1.2:
Nếu là độ đo khả năng thì thoả mãn tính chất sau:
(A) + (
A
) 1
*Độ đo cần thiết:
Tơng tự, ta định nghĩa độ đo cần thiết (dới đây đợc ký hiệu bởi N)
dựa theo quan hệ sau:
Định nghĩa 1.5:
Giả sử N là một độ đo confident thoả mãn:
A,B, N(AB) = min (N(A), N(B)) (1.7)
Khi đó N đợc gọi là độ đo khả năng
Một hàm N với những giá trị trong {0, 1} có thể dễ dàng đợc xây dựng
nhờ một sự kiện chắc chắn E nh sau:
N(A)
= 1 nếu E A
= 0 nếu E A
Rõ ràng là hàm N đợc xây dựng nh vậy là một độ đo cần thiết.
N(A) = 1 mang ý nghĩa A là chắc chắn.
Mệnh đề 1.1:
Một hàm tập N thoả mãn (1.7) nếu và chỉ nếu hàm đợc định nghĩa
bởi
A, (A) = 1 - N(
A
) (1.8)
là một phép đo khả năng.
- 13 -
Phơng trình (1.8) trình bày sự biểu diễn số mối quan hệ đối ngẫu giữa
các mô hình khả năng và mô hình cần thiết. Quan hệ đối ngẫu cho phép chúng
ta luôn xây dựng đợc một hàm cần thiết từ một phân phối khả năng thông
qua biểu thức:
N(A) = inf{1- ()| A} (1.9)
Ta có một số tính chất sau:
Tính chất 1.3: min(N(A), N(
A
)) = N(A(
A
)) = N() = 0
Tính chất 1.4: A, (A) N(A)
Chứng minh:
A, (A)=1-N(
A )-N(A)+N(A)
=(1-(N(
A
)+N(A)))+N(A) N(A)
Tính chất 1.3 cho một nhận xét trực giác rằng một sự kiện là có khả
năng trớc khi là cần thiết. Ngoài ra ta còn có các quan hệ sau:
Tính chất 1.5: N(A) > 0 (A) = 1
Chứng minh:
N(A) > 0 N(
A ) = 0 (do min(N(A), N( A )) = 0)
(A) = 1- N(
A ) = 1
Tơng tự ta có:
Tính chất 1.6: (A) < 1 N(A) = 0
Tính chất 1.7: N(A) + N(
A
) 1
1.2.2. khả năng và xác suất
Định nghĩa 1.6:
Sự kiện xuất hiện thông qua việc quan sát thờng xuyên các sự kiện cơ
bản nhận đợc một độ đo confidence P thoả mãn tiên đề cộng một cách tự
nhiên:
A, B, và AB = , P(AB) = P(A) + P(B) (1.10)
Không có nhận xét nào:
Đăng nhận xét