Thống kê (toán học) là bộ môn toán học rất quan trọng và có nhiều ứng dụng to
lớn trong thực tế, giúp con người rút ra thông tin từ dữ liệu quan sát, nhằm giải quyết
các bài toán thực tế trong cuộcsống.
Trong khóa luận này trình bày về một tiếp cận thống kê trong việc dự đoán sự
kiện dựa vào lý thuyết Bayes. Lý thuyết này nói về việc tính xác suất của sự kiện dựa
vào các kết quả thống kê các sự kiện trong quá khứ. Sau việc tính toán mỗi sự kiện
được gán xác xuất hay điểm (tùy vào mỗi phương pháp đánh giá) ứng với khả năng có
thể xảy ra với sự kiện đó. Và cuối cùng dựa vào ngưỡng để phân loại cho các sự kiện.
Sau phần lý thuyết chúng ta sẽ tìm hiểu về bài toán thực tế trong ngành công
nghệ thông tin. Bài toán về việc lọc thư rác tự động. Giải quyết bài này là sự kết hợp
từ rất nhiều phương án như DNS Blacklist, kiểm tra người nhận, người gửi,dùng bộ
lọc Bayes, chặn địa chỉ IP, Blacklist/Whitelist,. Dùng bộ lọc Bayes là phương án
thông minh nó gần gũi với người dùng bởi chính người dùng đã huấn luyện nó nhận
biết thư rác. Khóa luận này tập chung vào việc tìm hiểu bộ lọc thư rác Bayesspam –
mã nguồn mở, cài đặt cho hệ thống email có tên là SquirrelMail –mã nguồn mở đang
được dùng cho hệ thống email của trường đại học Công nghệ - Coltech Mail. Kết quả
cho thấy bộ lọccó mức độ hoạt độnghiệu quả là khác nhau tùy thuộc việc người dùng
huấn luyện cho bộ lọc thông qua các thư điện tử mà họ cho là thư rác nhưng nói chung
bộ lọc đã đem lại hiệu quả khá tốt.
50 trang |
Chia sẻ: oanhnt | Lượt xem: 2971 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Khóa luận Thuật toán bayes và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
------------------
Nguyễn Văn Huy
THUẬT TOÁN BAYES VÀ ỨNG DỤNG
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành : Công Nghệ Thông Tin
HÀ NỘI – 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
------------------
Nguyễn Văn Huy
THUẬT TOÁN BAYES VÀ ỨNG DỤNG
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành : Công Nghệ Thông Tin
Cán bộ hướng dẫn: ThS. Nguyễn Nam Hải
Cán bộ đồng hướng dẫn: ThS. Đỗ Hoàng Kiên
HÀ NỘI – 2009
Thuật toán Bayes và ứng dụng
ii
Lời cảm ơn
Viết khóa luận khoa học là một trong những việc khó khăn nhất mà em phải
hoàn thành từ trước đến nay. Trong quá trình thực hiện đề tài em đã gặp rất nhiều khó
khăn và bỡ ngỡ. Nếu không có những sự giúp đỡ và lời động viên chân thành của
nhiều thầy cô bạn bè và gia gia đình có lẽ em khó có thể hoàn thành luận văn này.
Đầu tiên em xin gửi lời cảm ơn chân thành đến thày Nguyễn Nam Hải và thày
Đỗ Hoàng Kiên đã trực tiếp hướng dẫn em hoàn thành luận văn này. Nhờ có thày mà
em được tiếp cận với nguồn tài liệu giá trị cũng như những góp ý quý giá sau này. Bên
cạnh sự giúp đỡ đó, em còn được các thày bên Trung tâm máy tính tạo mọi điều kiện
tốt nhất về cơ sở vật chất cũng như hướng dẫn chỉ bảo ân cần để em được tiếp cận với
hệ thống. Em biết ơn những ngày tháng được làm việc bên các thày, em không thể nào
quên những ngày tháng tuyệt vời đó.
Trong quá trình góp nhặt những kiến thức quý báu, các thày, cô, bạn bè là
những người đã cùng em sát cánh trong suốt thời gian em học tập và nghiên cứu dưới
mái trường Đại học Công nghệ.
Trong những nỗ lực đó, không thể không kể đến công lao to lớn không gì có thể
đền đáp của cha mẹ những người đã sinh thành, dưỡng dục con nên người, luôn nhắc
nhở, động viên con hoàn thành tốt nhiệm vụ.
Hà Nội
Tháng 5, 2009
Nguyễn Văn Huy
Thuật toán Bayes và ứng dụng
iii
Tóm tắt nội dung
Thống kê (toán học) là bộ môn toán học rất quan trọng và có nhiều ứng dụng to
lớn trong thực tế, giúp con người rút ra thông tin từ dữ liệu quan sát, nhằm giải quyết
các bài toán thực tế trong cuộc sống.
Trong khóa luận này trình bày về một tiếp cận thống kê trong việc dự đoán sự
kiện dựa vào lý thuyết Bayes. Lý thuyết này nói về việc tính xác suất của sự kiện dựa
vào các kết quả thống kê các sự kiện trong quá khứ. Sau việc tính toán mỗi sự kiện
được gán xác xuất hay điểm (tùy vào mỗi phương pháp đánh giá) ứng với khả năng có
thể xảy ra với sự kiện đó. Và cuối cùng dựa vào ngưỡng để phân loại cho các sự kiện.
Sau phần lý thuyết chúng ta sẽ tìm hiểu về bài toán thực tế trong ngành công
nghệ thông tin. Bài toán về việc lọc thư rác tự động. Giải quyết bài này là sự kết hợp
từ rất nhiều phương án như DNS Blacklist, kiểm tra người nhận, người gửi, dùng bộ
lọc Bayes, chặn địa chỉ IP, Blacklist/Whitelist,.... Dùng bộ lọc Bayes là phương án
thông minh nó gần gũi với người dùng bởi chính người dùng đã huấn luyện nó nhận
biết thư rác. Khóa luận này tập chung vào việc tìm hiểu bộ lọc thư rác Bayesspam –
mã nguồn mở, cài đặt cho hệ thống email có tên là SquirrelMail – mã nguồn mở đang
được dùng cho hệ thống email của trường đại học Công nghệ - Coltech Mail. Kết quả
cho thấy bộ lọc có mức độ hoạt động hiệu quả là khác nhau tùy thuộc việc người dùng
huấn luyện cho bộ lọc thông qua các thư điện tử mà họ cho là thư rác nhưng nói chung
bộ lọc đã đem lại hiệu quả khá tốt.
Thuật toán Bayes và ứng dụng
iv
Mục lục
Chương 1 Giới thiệu .................................................................................. 1
1.1 Tổng quan.......................................................................................................1
1.2 Cấu trúc ..........................................................................................................3
Chương 2 Cơ sở lý thuyết.......................................................................... 4
2.1 Phát biểu định lý Bayes ..................................................................................4
2.2 Cực tiểu hóa rủi ro trong bài toán phân lớp Bayes...........................................5
2.3 Phân lớp Bayes chuẩn tắc .............................................................................13
2.4 Miền quyết định............................................................................................20
Chương 3 Phân lớp Naive Bayes............................................................. 22
3.1 Định nghĩa ....................................................................................................22
3.2 Các mô hình xác suất Naive Bayes ...............................................................23
3.3 Ước lượng tham số .......................................................................................24
3.4 Xây dựng một classifier từ mô hình xác suất.................................................25
3.5 Thuật toán phân loại văn bản Naive Bayes....................................................25
Ví dụ: Phân loại thư điện tử bằng Naive Bayes classifier...................................27
Chương 4 Giải quyết bài toán lọc thư rác .............................................. 30
4.1 Đặt vấn đề ....................................................................................................30
4.2 Bài toán ........................................................................................................31
4.3 Tiền xử lý mỗi lá thư điện tử.........................................................................31
4.4 Dùng luật Bayes tính xác suất .......................................................................32
4.5 Huấn luyện cho bộ lọc Bayes........................................................................33
4.6 Lọc thư đến, có là thư rác không? .................................................................34
4.7 Bộ lọc BayesSpam........................................................................................35
4.8 Một số cải tiến cho bộ lọc BayesSpam..........................................................38
Chương 5 Kết luận .................................................................................. 40
Thuật toán Bayes và ứng dụng
v
Phụ lục A Cơ sở dữ liệu của bộ lọc .......................................................... 43
Tài liệu tham khảo 44
Thuật toán Bayes và ứng dụng
1
Chương 1 Giới thiệu
1.1 Tổng quan
Khoa học thống kê đóng một vai trò cực kỳ quan trọng, một vai trò không thể
thiếu được trong bất cứ công trình nghiên cứu khoa học, nhất là khoa học thực nghiệm
như y khoa, sinh học, nông nghiệp, hóa học, và ngay cả xã hội học. Thí nghiệm dựa
vào các phương pháp thống kê học có thể cung cấp cho khoa học những câu trả lời
khách quan nhất cho những vấn đề khó khăn nhất.
Khoa học thống kê là khoa học về thu thập, phân tích, diễn giải và trình bày
các dữ liệu để từ đó tìm ra bản chất và tính quy luật của các hiện tượng kinh tế, xã hội
- tự nhiên. Khoa học thống kê dựa vào lý thuyết thống kê, một loại toán học ứng dụng.
Trong lý thuyết thống kê, tính chất ngẫu nhiên và sự không chắc chắn có thể làm mô
hình dựa vào lý thuyết xác suất. Vì mục đích của khoa học thống kê là để tạo ra thông
tin "đúng nhất" theo dữ liệu có sẵn, có nhiều học giả nhìn khoa thống kê như một loại
lý thuyết quyết định.
Thống kê là một trong những công cụ quản lý vĩ mô quan trọng, cung cấp các
thông tin thống kê trung thực, khách quan, chính xác, đầy đủ, kịp thời trong việc đánh
giá, dự báo tình hình, hoạch định chiến lược, chính sách, xây dựng kế hoạch phát triển
kinh tế - xã hội và đáp ứng nhu cầu thông tin thống kê của các tổ chức, cá nhân. Trong
số những vai trò quan trọng thì dự báo tình hình là một trong những vai trò mang
nhiều ý nghĩa, nó có cả một quá trình huấn luyện bên trong và có tính xử lý tự động
khi đã được huấn luyện. Hay nói khác hơn là khi đã có tri thức lấy từ các dữ liệu thống
kê hay kinh nghiệm của người dùng kết hợp với một phương pháp học (huấn luyện)
dựa trên lý thuyết thống kê ta sẽ có được một cỗ máy có tri thức để tự nó có thể đưa ra
được những quyết định với độ chính xác khá cao.
Phân tích thống kê là một khâu quan trọng không thể thiếu được trong các
công trình nghiên cứu khoa học, nhất là khoa học thực nghiệm. Một công trình nghiên
cứu khoa học, cho dù có tốn kém và quan trọng cỡ nào, nếu không được phân tích
đúng phương pháp sẽ không bao giờ có cơ hội được xuất hiện trong các tập san khoa
học. Ngày nay, chỉ cần nhìn qua tất cả các tập san nghiên cứu khoa học trên thế giới,
hầu như bất cứ bài báo y học nào cũng có phần “Statistical Analysis” (Phân tích thống
kê), nơi mà tác giả phải mô tả cẩn thận phương pháp phân tích, tính toán như thế nào,
và giải thích ngắn gọn tại sao sử dụng những phương pháp đó để hàm ý “bảo kê” hay
Thuật toán Bayes và ứng dụng
2
tăng trọng lượng khoa học cho những phát biểu trong bài báo. Các tập san y học có uy
tín càng cao yêu cầu về phân tích thống kê càng nặng. Không có phần phân tích thống
kê, bài báo không thể xem là một “bài báo khoa học”. Không có phân tích thống kê,
công trình nghiên cứu chưa được xem là hoàn tất.
Trong khoa học thống kê, có hai trường phái “cạnh tranh” song song với nhau,
đó là trường phái tần số (frequentist school) và trường phái Bayes (Bayesian school).
Phần lớn các phương pháp thống kê đang sử dụng ngày nay được phát triển từ trường
phái tần số, nhưng hiện nay, trường phái Bayes đang trên đà “chinh phục” khoa học
bằng một suy nghĩ “mới” về khoa học và suy luận khoa học. Phương pháp thống kê
thuộc trường phái tần số thường đơn giản hơn các phương pháp thuộc trường phái
Bayes. Có người từng ví von rằng những ai làm thống kê theo trường phái Bayes là
những thiên tài!
Để hiểu sự khác biệt cơ bản giữa hai trường phái này, có lẽ cần phải nói đôi
qua vài dòng về triết lý khoa học thống kê bằng một ví dụ về nghiên cứu y khoa. Để
biết hai thuật điều trị có hiệu quả giống nhau hay không, nhà nghiên cứu phải thu thập
dữ liệu trong hai nhóm bệnh nhân (một nhóm được điều trị bằng phương pháp A, và
một nhóm được điều trị bằng phương pháp B). Trường phái tần số đặt câu hỏi rằng
“nếu hai thuật điều trị có hiệu quả như nhau, xác suất mà dữ liệu quan sát là bao
nhiêu”, nhưng trường phái Bayes hỏi khác: “Với dữ liệu quan sát được, xác suất mà
thuật điều trị A có hiệu quả cao hơn thuật điều trị B là bao nhiêu”. Tuy hai cách hỏi
thoạt đầu mới đọc qua thì chẳng có gì khác nhau, nhưng suy nghĩ kỹ chúng ta sẽ thấy
đó là sự khác biệt mang tính triết lý khoa học và ý nghĩa của nó rất quan trọng. Đối với
người bác sĩ (hay nhà khoa học nói chung), suy luận theo trường phái Bayes là rất tự
nhiên, rất hợp với thực tế. Trong y khoa lâm sàng, người bác sĩ phải sử dụng kết quả
xét nghiệm để phán đoán bệnh nhân mắc hay không mắc ung thư (cũng giống như
trong nghiên cứu khoa học, chúng ta phải sử dụng số liệu để suy luận về khả năng của
một giả thiết).
Thuật toán Bayes và ứng dụng
3
1.2 Cấu trúc
Các phần còn lại của khóa luận có cấu trúc như sau:
Chương 2 trình bày cơ sở lý thuyết Bayes các khái niệm, phương pháp được
sử dụng trong khoá luận.
Chương 3 trình bày lý thuyết Bayes nâng cao - Naive Bayes. Chương này sẽ
đề cập đến khái niệm, ưu điểm và ứng dụng phân loại của nó từ đó căn cứ nghiên cứu
xây dựng hệ thống phân loại văn bản.
Chương 4 trình bày chi tiết về bộ lọc bao gồm các vấn đề về cơ sở tri thức,
việc huấn luyện cho bộ lọc, cách thức làm việc và hướng cải tiến trong việc lọc thư
rác.
Chương 5 trình bày kết luận về chương trình ứng dụng bộ lọc BayesSpam cài
đặt trên hệ thống thư điện tử Squirrelmail.
Thuật toán Bayes và ứng dụng
4
Chương 2 Cơ sở lý thuyết
2.1 Phát biểu định lý Bayes
Định lý Bayes cho phép tính xác suất xảy ra của một sự kiện ngẫu nhiên A khi
biết sự kiện liên quan B đã xảy ra. Xác suất này được ký hiệu là P(A|B), và đọc là
"xác suất của A nếu có B". Đại lượng này được gọi xác suất có điều kiện hay xác suất
hậu nghiệm vì nó được rút ra từ giá trị được cho của B hoặc phụ thuộc vào giá trị đó.
Theo định lí Bayes, xác suất xảy ra A khi biết B sẽ phụ thuộc vào 3 yếu tố:
Xác suất xảy ra A của riêng nó, không quan tâm đến B. Kí hiệu là
P(A) và đọc là xác suất của A. Đây được gọi là xác suất biên duyên
hay xác suất tiên nghiệm, nó là "tiên nghiệm" theo nghĩa rằng nó không
quan tâm đến bất kỳ thông tin nào về B.
Xác suất xảy ra B của riêng nó, không quan tâm đến A. Kí hiệu là
P(B) và đọc là "xác suất của B". Đại lượng này còn gọi là hằng số
chuẩn hóa (normalising constant), vì nó luôn giống nhau, không phụ
thuộc vào sự kiện A đang muốn biết.
Xác suất xảy ra B khi biết A xảy ra. Kí hiệu là P(B|A) và đọc là "xác
suất của B nếu có A". Đại lượng này gọi là khả năng (likelihood) xảy
ra B khi biết A đã xảy ra. Chú ý không nhầm lẫn giữa khả năng xảy ra
A khi biết B và xác suất xảy ra A khi biết B.
Khi biết ba đại lượng này, xác suất của A khi biết B cho bởi công thức:
Thuật toán Bayes và ứng dụng
5
.
2.2 Cực tiểu hóa rủi ro trong bài toán phân lớp
Bayes
Bây giờ xem xét bài toán nút chai, hãy hình dung rằng nhà máy sản xuất được 2
loại là: w1 = Super và w2 = Average
Giả sử thêm rằng nhà máy có một hồ sơ của các kho chứa sản phẩm để lưu giữ,
tóm lược lại như sau:
Số nút chai của lớp w1: n1 = 901 420
Số nút chai của lớp w2: n2 = 1 352 130
Tổng số nút chai: n = 2 253 550
Theo đó ta dễ dàng tính được xác suất để một nút chai thuộc lớp nào trong 2
lớp, đây gọi là xác suất tiên nghiệm hay là prevalences:
P(w1) = n1/n = 0.4 P(w2) = n2/n = 0.6 (1-1)
Để ý rằng xác suất tiên nghiệm trên không phải hoàn toàn phụ thuộc vào nhà
máy sản xuất mà nó chủ yếu vào chất lượng của nguyên liệu. Tương tự một bác sĩ
chuyên khoa tim không thể nào kiểm soát xác suất bệnh nhồi máu cơ tim của một
nhóm dân cư. Prevalences có thể làm điều đó bởi vì nó liên quan đến trạng thái tự
nhiên.
Giả sử bài toán yêu cầu thực hiện một quyết định không rõ ràng, chẳng hạn
chọn lớp cho cái nút chai bất kỳ mà không biết gì về nút chai đó. Nếu chỉ có thông tin
là xác suất tiên nghiệm thì ta sẽ chọn lớp w2. Với cách này chúng ta mong rằng nó chỉ
sai 40% số lần.
Giả sử rằng chúng ta có thể đo được vecto đặc trưng của nút chai, p(wi|x) là
xác suất có điều kiện mô tả xác suất để đối tượng x thuộc lớp wi. Nếu chúng ta có thể
xác định xác suất p(w1|x) và p(w2|x) dễ thấy rằng:
Nếu P(w1| x) > P(w2|x) ta phân x vào w1;
Nếu P(w1| x) < P(w2|x) ta phân x vào w2;
Nếu P(w1| x) = P(w2| x) chọn tùy ý
Tóm lại:
if P(w1|x) > P(w2|x) then x w1 else x w2. (1-2a)
Thuật toán Bayes và ứng dụng
6
Xác suất hậu nghiệm P(wi|x) có thể tính được nếu chúng ta biết pdfs (các hàm
mật độ xác suất) của các phân phối vec tơ đặc trưng của 2 lớp. Sau đó ta tính các xác
suất p(x|wi) , là xác suất để đối tượng thuộc lớp wi có đặc trưng là x gọi là
likelihood of x tạm dịch là khả năng xảy ra x hay là hợp lý của x. Thực tế ta dùng
công thức Bayes:
(1-3)
Với:
Lưu ý rằng P(wi) và P(wi|x) là các xác suất rời rạc, trái lại p(x|wi) và p(x) là
các giá trị của hàm mật độ xác suất. Để ý rằng khi so sánh (1-2a) ta có giá trị chung là
p(x) do đó ta viết lại:
if p(x|w1) P(w1) > p(x|w2)P(w2) then x w1 else x w2. (1-4)
Hay là:
then x w1 else x w2. (1-4a)
Trong công thức (1-4a) thì v(x) gọi là tỷ số hợp lý (likelihood ratio)
1
( ) ( | w ) (w )
c
i i
i
p x p x P
( | w ) (w )(w | )
( )
i i
i
p x Pp x
p x
1 2
2 1
( | w ) (w )( )
( | w ) (w )
p x pv x
p x p
Thuật toán Bayes và ứng dụng
7
Hình 1: Biểu đồ của đặc trưng N cho hai lớp học của các nút chai. Giá trị
ngưỡng N = 65 được đánh dấu bằng một đường thẳng đứng
Giả sử rằng mỗi nút chai chỉ có một đặc trưng là N, tức là vec tơ đặc trưng là x = [N],
giả sử có một nút chai có x = [65].
Từ đồ thị ta tính được các xác suất likelihood:
p(x|w1) = 20/24 = 0.833 → P(w1) p(x|w1) = 0.333 (1-5a)
p(x|w2) = 16/23 = 0.696 → P(w2) p(x|w1) = 0.418 (1-5b)
Ta sẽ phân x = [65] vào lớp w2 mặc dù hợp lý(likelihood) của w1 lớn hơn
của w2
Hình 2 minh họa ảnh hưởng của việc điều chỉnh ngưỡng xác suất tiên nghiệm
đến các hàm mật độ xác suất.
Xác suất tiên nghiệm đồng nhất (equal prevalences). Với các hàm mật độ
xác suất đồng nhất, ngưỡng quy định là một nửa khoảng cách đến phần tử
trung bình. Số lượng các trường hợp phân lớp sai tương ứng với vùng được
tô đậm. Đây là vùng mà khoảng cách phân lớp là nhỏ nhất.
Xác suất tiên nghiệm của w1 lớn hơn của w2. Ngưỡng quyết định thay thế
các lớp có xác suất tiên nghiệm nhỏ hơn. Vì vậy giảm số trường hợp của lớp
có xác suất tiên nghiệm cao dường như có vẻ thuận tiện.
Thuật toán Bayes và ứng dụng
8
Hình 2: Xác suất tiên nghiệm đồng nhất (a), không đồng nhất (b).
Chúng ta thấy rằng thật sự độ lệch ngưỡng quyết định đã dẫn đến lớp w2 tốt
hơn lớp w1. Điều này nghe có vẻ hợp lý kể từ khi mà bây giờ lớp w2 xuất hiện thường
xuyên hơn. Khi độ sai toàn phần tăng lên điều kỳ lạ là sự ảnh hưởng của xác suất tiên
nghiệm là có lợi. Câu trả lời cho câu hỏi này là liên quan đến chủ đề phân lớp mạo
hiểm, mà sẽ được trình bày ngay bây giờ.
Chúng ta giả định rằng giá của một nút chai (cork stopper) thuộc lớp w1 là
0.025£, lớp w2 là 0.015£. Giả sử là các nút chai lớp w1 được dùng cho các chai đặc
biệt, còn các nút chai lớp w2 thì dùng cho các chai bình thường.
Nếu ta phân lớp sai một nút chai lớp w1 thì sẽ bị mất 0.025-0.015=0.01£.
Nếu phân lớp sai một nút chai lớp w2 thì dẫn đến nó sẽ bị loại bỏ và sẽ bị mất 0.015£.
Ta ký hiệu:
SB - Hành động của việc sử dụng một nút chai(cork stopper) để phân
cho loại chai đặc biệt.
NB - Hành động của việc sử dụng một nút chai(cork stopper) để phân
cho loại chai bình thường.
w1 = S (siêu lớp); w2 = A (lớp trung bình)
Thuật toán Bayes và ứng dụng
9
Hình 3: Kết quả phân lớp của cork stoppers với xác suất tiên nghiệm không đồng
nhất: 0.4 cho lớp w1 và 0.6 cho lớp w2
Định nghĩa:
λij = λ(αi | wj ) là độ mất mát với hành động αi khi mà lớp đúng là wj, với
αi{SB, NB}.
λ11 = λ(α1 | w1 ) = λ(SB | S) = 0,
λ12 = λ(α1 | w2 ) = λ(SB | A) = 0.015,
λ21 = λ(α2 | w1 ) = λ(NB | S) = 0.01,
λ22 = λ(α2 | w2 ) = λ(NB | A) = 0.
Thuật toán Bayes và ứng dụng
10
Chúng ta có thể sắp xếp λij thành ma trận hao phí Λ.
Λ = (1-6)
Vì thế độ mất mát với hành động sử dụng một nút chai (mô tả bởi vectơ đặc
trưng x) và phân vào cho những chai đặc biệt có thể được biểu thị như sau:
R(α1 | x) = R(SB | x) = λ(SB | S)P(S | x) + λ(SB | A)P(A | x) (1-6a)
R(α1 | x) = 0.015 P(A | x)
Tương tự cho trường hợp nếu phân cho những chai thông thường:
R(α2 | x) = R(NB | x) = λ(NB | S)P(S | x) + λ(NB | A)P(A | x) (1-6b)
R(α2 | x) = 0.01P(S | x)
Chúng ta giả định rằng đánh giá rủi ro chỉ chịu ảnh hưởng từ quyết định sai.
Do vậy một quyết định chính xác sẽ không gây ra thiệt hại λii=0, như trong (1-6).
Nếu thay vì 2 lớp chúng ta có c lớp thì sự mất mát ứng với một hành động αi sẽ là:
(1-6c)
Chúng ta quan tâm đến việc giảm thiểu mức rủi ro trung bình tính cho một
lượng lớn nút chai bất kỳ. Công thức Bayes cho rủi ro nhỏ nhất làm được điều này
bằng cách cực tiểu hóa các rủi ro có điều kiện R(αi | x).
Giả sử ban đầu rằng các quyết định sai lầm có cùng một mất mát, chúng có tỉ lệ
với một đơn vị mất mát:
(1-7a)
Trong trường hợp này từ tất cả các xác suất hậu nghiệm đều tăng lên một,
chúng ta cần phải cực tiểu hóa:
(1-7b)
0 0.015
0.01 0
i
1
( | ) ( | ) ( | )
c
i j j
j
R x P x
i
0
( | )
1ij j
if i j
if j j
( | ) ( | ) 1 ( | )i j j
i j
R x P x P x
Thuật toán Bayes và ứng dụng
11
Điều này tương đương với việc chúng ta cực đại P(wi | x), luật quyết định
Bayes cho rủi ro cực tiểu tương ứng với việc tổng quát hóa vấn đề:
Phân lớp wi nếu P(wi | x)