thuật toán bayes và ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.75 MB, 50 trang )

Bạn đang đọc: thuật toán bayes và ứng dụng

ĐẠ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

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

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

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à: w
1
= Super và w
2
= 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 w
1
: n
1
= 901 420
 Số nút chai của lớp w
2
: n
2
= 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(w
1
) = n
1
/n = 0.4 P(w
2
) = n
2
/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 w
2
. 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(w
i
|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 w
i
. Nếu chúng ta có thể
xác định xác suất p(w
1
|x) và p(w
2
|x) dễ thấy rằng:
 Nếu P(w
1
| x) > P(w
2
|x) ta phân x vào w
1
;
 Nếu P(w

1
| x) < P(w
2
|x) ta phân x vào w
2
;
 Nếu P(w
1
| x) = P(w
2
| x) chọn tùy ý
Tóm lại:
if P(w
1
|x) > P(w
2|
x) then x

w
1
else x

w
2
. (1-2a)
Thuật toán Bayes và ứng dụng

6
Xác suất hậu nghiệm P(w
i

|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|w
i
), là xác suất để đối tượng thuộc lớp w
i
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(w
i
) và P(w
i
|x) là các xác suất rời rạc, trái lại p(x|w
i
) 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|w
1
) P(w
1
) > p(x|w

2
)P(w
2
) then x

w
1
else x

w
2
. (1-4)

Hay là:

then x

w
1
else x

w
2
. (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 P
p x
p x

1 2
2 1
( | w ) (w )
( )
( | w ) (w )
p x p
v 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|w
1
) = 20/24 = 0.833 → P(w
1
) p(x|w
1
) = 0.333 (1-5a)
p(x|w
2
) = 16/23 = 0.696 → P(w
2
) p(x|w
1
) = 0.418 (1-5b)
Ta sẽ phân x = [65] vào lớp w
2
mặc dù hợp lý(likelihood) của w
1
lớn hơn
của w
2
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 w
1
lớn hơn của w
2
. 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

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 w
2
tốt
hơn lớp w
1
. Điều này nghe có vẻ hợp lý kể từ khi mà bây giờ lớp w
2
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 w
1
là
0.025£, lớp w
2

Xem thêm: Top 19 cách edit truyện trên điện thoại ios mới nhất 2021

là 0.015£. Giả sử là các nút chai lớp w
1
được dùng cho các chai đặc
biệt, còn các nút chai lớp w
2
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 w
1
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 w
2
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.
 w
1
= S (siêu lớp); w
2
= A (lớp trung bình)

Thuật toán Bayes và ứng dụng

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
| w
j
) là độ mất mát với hành động α
i
khi mà lớp đúng là w
j
, với
α
i

{SB, NB}.
λ
11
= λ(α
1
| w
1
) = λ(SB | S) = 0,

Thuật toán Bayes và ứng dụng

Chúng ta có thể sắp xếp λ
ij
thành ma trận hao phí Λ.

Λ = (1-6)

(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
( | )
1
ij 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(w
i
| 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 w

i
nếu P(w
i
| x) > P(w
j
| x), ij


(1-7c)

Tóm lại: luật quyết định Bayes cho rủi ro cực tiểu, khi sự phân lớp đúng thì không bị
mất mát và nếu như phân lớp sai thì có mất mát, ta cần phải chọn được lớp có xác
suất hậu nghiệm là cức đại.

Hàm quyết định cho lớp w
i
là:
g
i
(x) = P(w
i
| x) (4-18d)

Bây giờ hãy xem xét các tình huống khác nhau của các thiệt hại xảy ra cho
những quyết định sai lầm, để cho đơn giản giả sử c = 2. Dựa vào các biểu thức (1-6a)
và (1-6b) thật dễ nhận thấy rằng một nút chai sẽ thuộc lớp w
1
nếu:

<
Hay là (1-8)

Vì thế ngưỡng quyết định so với tỷ số hợp lý(likelihood) thì nó nghiêng về sự
mất mát. Ta có thể cài đặt luật quyết định Bayes như hình 5.
Tương tự chúng ta có thể điều chỉnh xác suất tiên nghiệm như sau:

; (1-8a)

12 2 1
21 1 2
( ) ( | )
( ) ( | )
P w P x w
P w P x w



12 2
( | )
P x
 
21 1
( | )
P x

 
*
21 1
1
21 1 12 2
( )
( )
( ) ( )
P w
P w
P w P w

 

*
12 2
2
21 1 12 2
( )
( )
( ) ( )
P w
P w
P w P w

 

Thuật toán Bayes và ứng dụng

Với sự mất mát λ
12
= 0.015 và λ
21
= 0.01, sử dụng xác suất tiên nghiệm ở
trên ta được P
*
(w
1
) = 0.308 và P
*
(w
2
) = 0.692. Sự thiệt hại sẽ là lớn hơn nếu như
phân lớp sai lớp w
2
do đó cần tăng P
*
(w
2
) lên so với P
*
(w
1
). Kết quả của việc điều
chỉnh là giảm số lượng các phần tử thuộc lớp w
2
bị phân lớp sai thành w
1

. Xem kết
quả phân lớp ở hình ở hình 6.

Ta có thể tính giá trị rủi ro trung bình trường hợp có 2 lớp:

(1-9)

1 2
12 2 21 1 12 12 21 21
( | ) ( ) ( | ) ( )
R R
R P w x p x dx P w x p x dx Pe Pe
   
   
 
Thuật toán Bayes và ứng dụng

13
R
2
và R
2
là miền quyết định của lớp
1

và lớp
2


, còn Pe
ij
là xác suất sai
số của sự quyết định lớp là
i

khi mà lớp đúng là
j


Chúng ta hãy sử dụng tập dữ liệu huấn luyện để đánh giá những sai số này,
Pe
12
=0.1 và Pe
21
=0.46 (xem hình 6). Rủi ro trung bình đối với mỗi nút chai bây giờ
là:
R = 0.015Pe
12
+ 0.01Pe
21
= 0.0061Є.
Với Ω là tập các lớp ta có công thức (1-9) tổng quát:

(1-9a)

Luật quyết định Bayes không phải là lựa chọn duy nhất trong thống kê phân
lớp. Cũng lưu ý rằng, trong thực tế một trong những cố gắng để giảm thiểu rủi ro trung
bình là sử dụng ước lượng của hàm mật độ xác suất tính được từ một tập dữ liệu huấn
luyện, như chúng ta đã làm ở trên cho cork Stoppers. Nếu chúng ta có những căn cứ để

tin rằng các hàm phân phối xác suất thỏa mãn tham số mẫu, thì ta thay thế việc tính
các tham biến thích hợp từ tập huấn luyện. Hoặc là chúng ta cũng có thể sử dụng
phương pháp cực tiểu hóa rủi ro theo kinh nghiệm (empirical risk minimization
(ERM)), nguyên tắc là cực tiểu hóa rủi ro theo kinh nghiệm thay vì rủi ro thực tế.

2.3 Phân lớp Bayes chuẩn tắc
Cho đến giờ chúng ta vẫn chưa giả định đặc trưng của phân phối mẫu cho
likelihoods. Tuy nhiên, mô hình chuẩn tắc là một giả định hợp lý. Mô hình chuẩn tắc
có liên quan đến định lý giới hạn trung tâm nổi tiếng, theo định lý này thì tổng của một
lượng lớn các biến ngẫu nhiên độc lập và phân phối đồng nhất sẽ có phân phối hội tụ
về luật chuẩn. Thực tế ta có được một xấp xỉ đến luật chuẩn tắc, thậm chí với cả một
số lượng tương đối nhỏ được thêm vào các biến ngẫu nhiên. Đối với các đặc trưng có
thể được coi là kết quả của việc bổ sung các biến độc lập, thường thì giả định là có thể
chấp nhận.
Likelihood chuẩn tắc của lớp ω
i
được biểu diễn bởi hàm mật độ xác suất:

( ( ) | ) (, ) ( ( ) | ) (, ) ( )
i i
i i i i
X X
R x P x dx x P x p x dx
 
       
 
 
 

 
Thuật toán Bayes và ứng dụng

µ
i
và ∑
i
là các tham số phân phối, đến giờ thì ta đã sử dụng các ước lượng
mẫu m
i
và C
i
.
Hình 7 minh họa phân phối chuẩn trong trường hợp có hai chiều.
Cho một tập huấn luyện có n mẫu T={x
1
, x
2
, … x
n
} được mô tả bởi một phân
phối với hàm mật độ xác suất là p(T | θ), θ là một vec tơ tham số của phân phối
(chẳng hạn như vec tơ trung bình của phân phối chuẩn). Một cách đáng chú ý tính
được ước lượng mẫu của vectơ tham biến là cực đại hóa hàm mật độ xác suất p(T | θ),
có thể coi dây là một hàm của θ gọi là likelihood of θ cho tập huấn luyện. Giả sử rằng
mỗi mẫu là đưa vào độc lập từ một tập vô hạn, chúng ta có thể biểu thị likelihood như
sau:

Khi sử dụng ước lượng hợp lý cực đại (maximum likelihood estimation) của
các biến phân phối thì nó thường dễ dàng hơn là tính cưc đại của ln[p(T|θ)], điều này
là tương đương nhau. Với phân phối Gauss ước lượng mẫu được cho bởi các công
thức (1-10a) và (1-10b) chính là ước lượng hợp lý cực đại và nó sẽ hội tụ về một giá trị
thực.

1
( | ) ( | )
n
i
i
p T p x
 



Thuật toán Bayes và ứng dụng

Như có thể nhìn thấy từ (1-10), các bề mặt của mật độ xác suất đồng nhất với
hợp lý chuẩn (normal likelihood) thỏa mãn Mahalanobis metric:

Bây giờ chúng ta tiếp tục tính hàm quyết định cho các đặc trưng của phân phối
chuẩn:
g
i
(x) = P(ω
i
| x) = P(ω
i
) p(x | ω
i
) (1-11)
biến đổi logarit ta được:
Bằng cách sử dụng những hàm quyết định, rõ ràng phụ thuộc Mahalanobis
metric, ta có thể xây dựng phân lớp Bayes với rủi ro nhỏ nhất, đây là phân lớp tối ưu.
Chú ý rằng công thức (1-11b) sử dụng giá trị thật của khoảng cách Mahalanobis, trong
khi mà trước đó chúng ta sử dụng ước lượng của khoảng cách này.
Với trường hợp covariance đồng nhất cho tất cả các lớp (∑
i
=∑) và bỏ qua các
hằng số ta được:

(1-11c)
1
1
( ) ( ) ( ) ln ( )
2
i i i i
h x x x P
  



    

Thuật toán Bayes và ứng dụng

16
Với bài toán 2 lớp, biệt số d(x) =h
1
(x)-h
2
(x) là dễ đàng tính toán:
Qua đó ta có được hàm quyết định tuyến tính

Hai lớp phân biệt với phân phối chuẩn, xác suất tiên nghiệm đồng nhất và
covariance và vẫn còn có một công thức rất đơn giản cho xác suất của lỗi của phân
lớp:

Thuật toán Bayes và ứng dụng

17
bình phương của khoảng cách Bhattacharyya, một khoảng cách Mahalanobis
của sai phân trung bình, thể hiện tính dễ tách lớp.
Hình 8 thể hiện dáng điệu của Pe với sự tăng dần của bình phương khảng cách
Bhattacharyya. Hàm này giảm dần theo cấp số mũ và nó hội tụ tiệm cận tới 0. Vì vậy
thật khó để giảm sai số phân lớp khi giá trị này là nhỏ.
Lưu ý rằng ngay cả khi các phân phối mẫu không phải là phân phối chuẩn, miễn
là chúng đối xứng và phải tuân theo Mahalanobis metric, thì chúng ta sẽ thu được mặt
phân lớp quyết định tương tự như phân lớp chuẩn, cho dù có sự khác biệt về đánh giá

Xem thêm: 10 App Chèn Sticker Vào Ảnh Bạn Nên Trải Nghiệm

sai số và xác suất hậu nghiệm. Để minh họa ta hãy xét hai lớp có xác suất tiên nghiệm
đồng nhất và có ba loại phân phối đối xứng, với cùng độ lệch tiêu chuẩn và trung bình
0 và 2.3 như hình 9.

Thuật toán Bayes và ứng dụng

18
Phân lớp tối ưu cho 3 trường hợp sử dụng cùng một ngưỡng quyết định có giá
trị 1.15, tuy nhiên các sai số phân lớp là khác nhau:

 Nomal: Pe = 1 – erf(2.3/2) = 12.5%
 Cauchy: Pe = 22.7%
 Logistic: Pe = 24.0%
Kết quả thực nghiệm cho thấy, khi ma trận covariance đưa ra độ lệch giới hạn,
thì sự phân lớp có thể thực hiện một cách tương tự với phương pháp tối ưu với điều
kiện các covariance là đồng nhất. điều này là hợp lý vì khi các covariance không khác
biệt nhau nhiều thì sự khác biệt giữa các giải pháp bậc hai và tuyến tính chỉ đáng kể
khi các mẫu cách xa nguyên mẫu như ở hình 10.
Chúng ta sẽ minh họa bằng cách sử dụng bộ dữ liệu Norm2c2d. Sai số lý
thuyết đối với trường hợp hai lớp, hai chiều và bộ dữ liệu trên là:

δ
2
=

Ước lượng sai số của bộ dữ liệu huấn luyện cho tập dữ liệu này là 5%. Bằng
cách đưa vào sai số ±0.1 vào các giá trị của ma trận ánh xạ A cho bộ dữ liệu, với độ
lệch nằm giữa 15% và 42% giá rị của covariance, ta được sai số tập huấn luyện là

6%.
 
0.8 0.8 2
2 3 8 1 ( 2) 7.9%
0.8 1.6 3
Pe erf

   
    
   

   
Thuật toán Bayes và ứng dụng

Trở lại với dữ liệu các nút chai, ta có bài toán phân lớp sử dụng 2 đặc trưng N
và PRT với xác suất tiên nghiệm đồng nhất. Lưu ý phân lớp thống kê ngoài tính toán
số nó không làm thay đổi các phép toán, vì thế mà các kết quả đạt được là giống nhau
nếu như sử dụng PRT hay PRT10.
Một danh sách riêng các xác suất hậu nghiệm hữu ích trong tính toán các sai số
phân lớp, xem hình 11.
Cho các ma trận covariances ở trong bảng 1. Độ lệch của các phần tử trong ma
trận covariance so với giá trị trung tâm nằm trong khoảng từ 5% đến 30%. Hình dáng
của các cụm là tương tự nhau, đây là bằng chứng để tin rằng việc phân lớp là gần với
tối ưu.
Bằng cách sử dụng hàm quyết định dựa trên các ma trận covariance riêng lẻ,
thay vì chỉ một ma trận tổng covariance, ta sẽ xây dựng được đường biên quyết định
bâc hai. Tuy nhiên phân lớp bằng đường bậc hai khó tính độ lệch hơn so với phân lớp
tuyến tính, đặc biệt là trong không gian nhiều chiều, và ta cần phải có một lượng lớn

tập dữ liệu huấn luyện (xem ví dụ của Fukunaga and Hayes, 1989).
HÀ NỘI – 2009 ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆ < > Nguyễn Văn HuyTHUẬT TOÁN BAYES VÀ ỨNG DỤNGKHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUYNgành : Công Nghệ Thông TinCán bộ hướng dẫn : ThS. Nguyễn Nam HảiCán bộ đồng hướng dẫn : ThS. Đỗ Hoàng KiênHÀ NỘI – 2009T huật toán Bayes và ứng dụngiiLời cảm ơnViết khóa luận khoa học là một trong những việc khó khăn vất vả nhất mà em phảihoàn thành từ trước đến nay. Trong quy trình triển khai đề tài em đã gặp rất nhiều khókhăn và kinh ngạc. Nếu không có những sự giúp sức và lời động viên chân thành củanhiều thầy cô bè bạn và gia mái ấm gia đình có lẽ rằng em khó hoàn toàn có thể triển khai xong 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 xong 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êncạnh sự trợ giúp đó, em còn được những thày bên Trung tâm máy tính tạo mọi điều kiệntố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ớihệ thống. Em biết ơn những ngày tháng được thao tác bên những thày, em không hề nàoquên những ngày tháng tuyệt vời đó. Trong quy trình góp nhặt những kỹ năng và kiến thức quý báu, những thày, cô, bạn hữu lànhững người đã cùng em sát cánh trong suốt thời hạn em học tập và điều tra và nghiên cứu dướimái trường Đại học Công nghệ. Trong những nỗ lực đó, không hề 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ắcnhở, động viên con hoàn thành xong tốt trách nhiệm. Hà NộiTháng 5, 2009N guyễn Văn HuyThuật toán Bayes và ứng dụngiiiTóm tắt nội dungThố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 tolớn trong trong thực tiễn, giúp con người rút ra thông tin từ tài liệu quan sát, nhằm mục đích giải quyếtcác bài toán trong thực tiễn trong đời sống. Trong khóa luận này trình diễn về một tiếp cận thống kê trong việc Dự kiến sựkiện dựa vào kim chỉ nan Bayes. Lý thuyết này nói về việc tính Xác Suất của sự kiện dựavào những tác dụng thống kê những sự kiện trong quá khứ. Sau việc giám sát mỗi sự kiệnđược gán xác xuất hay điểm ( tùy vào mỗi chiêu thức nhìn nhận ) ứng với năng lực cóthể xảy ra với sự kiện đó. Và ở đầu cuối dựa vào ngưỡng để phân loại cho những sự kiện. Sau phần kim chỉ nan tất cả chúng ta sẽ khám phá về bài toán thực tiễn trong ngành côngnghệ thông tin. Bài toán về việc lọc thư rác tự động hóa. Giải quyết bài này là sự kết hợptừ rất nhiều giải pháp 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 ánthông minh nó thân mật với người dùng bởi chính người dùng đã giảng dạy nó nhậnbiết thư rác. Khóa luận này tập chung vào việc khám phá bộ lọc thư rác Bayesspam – mã nguồn mở, thiết lập cho mạng lưới hệ thống email có tên là SquirrelMail – mã nguồn mở đangđược dùng cho mạng lưới hệ thống email của trường ĐH Công nghệ – Coltech Mail. Kết quảcho thấy bộ lọc có mức độ hoạt động giải trí hiệu suất cao là khác nhau tùy thuộc việc người dùnghuấn luyện cho bộ lọc trải qua những thư điện tử mà họ cho là thư rác nhưng nói chungbộ lọc đã đem lại hiệu suất cao khá tốt. Thuật toán Bayes và ứng dụngivMục lụcChương 1 Giới thiệu 11.1 Tổng quan 11.2 Cấu trúc 3C hương 2 Cơ sở kim chỉ nan 42.1 Phát biểu định lý Bayes 42.2 Cực tiểu hóa rủi ro đáng tiếc trong bài toán phân lớp Bayes 52.3 Phân lớp Bayes chuẩn tắc 132.4 Miền quyết định hành động 20C hương 3 Phân lớp Naive Bayes 223.1 Định nghĩa 223.2 Các quy mô Tỷ Lệ Naive Bayes 233.3 Ước lượng tham số 243.4 Xây dựng một classifier từ quy mô Phần Trăm 253.5 Thuật toán phân loại văn bản Naive Bayes 25V í dụ : Phân loại thư điện tử bằng Naive Bayes classifier 27C hương 4 Giải quyết bài toán lọc thư rác 304.1 Đặt yếu tố 304.2 Bài toán 314.3 Tiền giải quyết và xử lý mỗi lá thư điện tử 314.4 Dùng luật Bayes tính Tỷ Lệ 324.5 Huấn luyện cho bộ lọc Bayes 334.6 Lọc thư đến, có là thư rác không ? 344.7 Bộ lọc BayesSpam 354.8 Một số nâng cấp cải tiến cho bộ lọc BayesSpam 38C hương 5 Kết luận 40T huật toán Bayes và ứng dụngPhụ lục A Cơ sở tài liệu của bộ lọc 43T ài liệu tìm hiểu thêm 44T huật toán Bayes và ứng dụngChương 1 Giới thiệu1. 1 Tổng quanKhoa 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 kể khu công trình điều tra và nghiên cứu khoa học, nhất là khoa học thực nghiệmnhư 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ựavào những chiêu thức thống kê học hoàn toàn có thể phân phối cho khoa học những câu trả lờikhách quan nhất cho những yếu tố khó khăn vất vả nhất. Khoa học thống kê là khoa học về tích lũy, nghiên cứu và phân tích, diễn giải và trình bàycác dữ liệu để từ đó tìm ra thực chất và tính quy luật của những hiện tượng kỳ lạ kinh tế tài chính, xã hội – tự nhiên. Khoa học thống kê dựa vào triết lý thống kê, một loại toán học ứng dụng. Trong triết lý thống kê, đặc thù ngẫu nhiên và sự không chắc như đinh hoàn toàn có thể làm môhình dựa vào triết lý Xác Suất. Vì mục tiêu của khoa học thống kê là để tạo ra thôngtin ” đúng nhất ” theo tài liệu có sẵn, có nhiều học giả nhìn khoa thống kê như một loạilý thuyết quyết định hành động. Thống kê là một trong những công cụ quản trị vĩ mô quan trọng, phân phối cácthông tin thống kê trung thực, khách quan, đúng mực, rất đầy đủ, kịp thời trong việc đánhgiá, dự báo tình hình, hoạch định kế hoạch, chủ trương, kiến thiết xây dựng kế hoạch phát triểnkinh tế – xã hội và cung ứng nhu yếu thông tin thống kê của những tổ chức triển khai, cá thể. Trongsố những vai trò quan trọng thì dự báo tình hình là một trong những vai trò mangnhiều ý nghĩa, nó có cả một quy trình giảng dạy bên trong và có tính giải quyết và xử lý tự độngkhi đã được huấn luyện và đào tạo. Hay nói khác hơn là khi đã có tri thức lấy từ những tài liệu thốngkê hay kinh nghiệm tay nghề của người dùng tích hợp với một phương pháp học ( huấn luyện và đào tạo ) dựa trên kim chỉ nan thống kê ta sẽ có được một cỗ máy có tri thức để tự nó hoàn toàn có thể đưa rađược những quyết định hành động với độ đúng chuẩn khá cao. Phân tích thống kê là một khâu quan trọng không hề thiếu được trong cáccông trình nghiên cứu và điều tra khoa học, nhất là khoa học thực nghiệm. Một khu công trình nghiêncứu khoa học, mặc dầu có tốn kém và quan trọng cỡ nào, nếu không được phân tíchđúng chiêu thức sẽ không khi nào có thời cơ được Open trong những tập san khoahọc. Ngày nay, chỉ cần nhìn qua tổng thể những tập san điều tra và nghiên cứu khoa học trên quốc tế, phần đông bất kể bài báo y học nào cũng có phần “ Statistical Analysis ” ( Phân tích thốngkê ), nơi mà tác giả phải diễn đạt cẩn trọng giải pháp nghiên cứu và phân tích, giám sát như thế nào, và lý giải ngắn gọn tại sao sử dụng những chiêu thức đó để hàm ý “ bảo kê ” hayThuật toán Bayes và ứng dụngtăng khối 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ó uytín càng cao nhu yếu về nghiên cứu và phân tích thống kê càng nặng. Không có phần nghiên cứu và phân tích thốngkê, bài báo không hề xem là một “ bài báo khoa học ”. Không có nghiên cứu và phân tích thống kê, khu công trình nghiên cứu và điều tra chưa được xem là hoàn tất. Trong khoa học thống kê, có hai phe phái “ cạnh tranh đối đầu ” song song với nhau, đó là phe phái tần số ( frequentist school ) và phe phái Bayes ( Bayesian school ). Phần lớn những giải pháp thống kê đang sử dụng thời nay được tăng trưởng từ trườngphái tần số, nhưng lúc bấy giờ, phe phái Bayes đang trên đà “ chinh phục ” khoa họcbằng một tâm lý “ mới ” về khoa học và suy luận khoa học. Phương pháp thống kêthuộc phe phái tần số thường đơn thuần hơn những giải pháp thuộc trường pháiBayes. Có người từng ví von rằng những ai làm thống kê theo phe phái Bayes lànhững thiên tài ! Để hiểu sự độc lạ cơ bản giữa hai phe phái này, có lẽ rằng cần phải nói đôiqua vài dòng về triết lý khoa học thống kê bằng một ví dụ về điều tra và nghiên cứu y khoa. Đểbiết hai thuật điều trị có hiệu suất cao giống nhau hay không, nhà nghiên cứu phải thu thậpdữ liệu trong hai nhóm bệnh nhân ( một nhóm được điều trị bằng giải pháp A, vàmột nhóm được điều trị bằng giải 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 suất cao như nhau, Tỷ Lệ mà tài liệu quan sát là baonhiêu ”, nhưng phe phái Bayes hỏi khác : “ Với tài liệu quan sát được, Phần Trăm màthuật điều trị A có hiệu suất cao cao hơn thuật điều trị B là bao nhiêu ”. Tuy hai cách hỏithoạt đầu mới đọc qua thì chẳng có gì khác nhau, nhưng tâm lý kỹ tất cả chúng ta sẽ thấyđó là sự độc lạ mang tính triết lý khoa học và ý nghĩa của nó rất quan trọng. Đối vớingười bác sĩ ( hay nhà khoa học nói chung ), suy luận theo phe phái Bayes là rất tựnhiên, rất hợp với trong thực tiễn. 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 điều tra và nghiên cứu khoa học, tất cả chúng ta phải sử dụng số liệu để suy luận về năng lực củamột giả thiết ). Thuật toán Bayes và ứng dụng1. 2 Cấu trúcCá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 diễn cơ sở triết lý Bayes những khái niệm, giải pháp đượcsử dụng trong khoá luận. Chương 3 trình diễn triết lý 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ừ đó địa thế căn cứ nghiên cứuxây dựng mạng lưới hệ thống phân loại văn bản. Chương 4 trình diễn cụ thể về bộ lọc gồm có những yếu tố về cơ sở tri thức, việc giảng dạy cho bộ lọc, phương pháp thao tác và hướng nâng cấp cải tiến trong việc lọc thưrác. Chương 5 trình diễn Tóm lại về chương trình ứng dụng bộ lọc BayesSpam càiđặt trên mạng lưới hệ thống thư điện tử Squirrelmail. Thuật toán Bayes và ứng dụngChương 2 Cơ sở lý thuyết2. 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 khibiết sự kiện tương quan B đã xảy ra. Xác suất này được ký hiệu là P. ( A | B ), và đọc là ” Tỷ Lệ của A nếu có B “. Đại lượng này được gọi Tỷ Lệ có điều kiện kèm theo hay xác suấthậu nghiệm vì nó được rút ra từ giá trị được cho của B hoặc phụ thuộc vào vào giá trị đó. Theo định lí Bayes, Tỷ Lệ xảy ra A khi biết B sẽ nhờ vào vào 3 yếu tố :  Xác suất xảy ra A của riêng nó, không chăm sóc đến B. Kí hiệu làP ( A ) và đọc là Xác Suất của A. Đây được gọi là Phần Trăm biên duyênhay Tỷ Lệ tiên nghiệm, nó là ” tiên nghiệm ” theo nghĩa rằng nó khôngquan 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 chăm sóc đến A. Kí hiệu làP ( B ) và đọc là ” Tỷ Lệ 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ácsuất của B nếu có A “. Đại lượng này gọi là năng lực ( likelihood ) xảyra B khi biết A đã xảy ra. Chú ý không nhầm lẫn giữa năng lực xảy raA 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ụng2. 2 Cực tiểu hóa rủi ro đáng tiếc trong bài toán phân lớpBayesBây giờ xem xét bài toán nút chai, hãy tưởng tượng rằng nhà máy sản xuất sản xuất được 2 loại là : w = Super và w = AverageGiả sử thêm rằng xí nghiệp sản xuất có một hồ sơ của những kho chứa mẫu sản phẩm để lưu giữ, tóm lược lại như sau :  Số nút chai của lớp w : n = 901 420  Số nút chai của lớp w : n = 1 352 130  Tổng số nút chai : n = 2 253 550T heo đó ta thuận tiện tính được Tỷ Lệ để một nút chai thuộc lớp nào trong 2 lớp, đây gọi là Tỷ Lệ tiên nghiệm hay là prevalences : P. ( w ) = n / n = 0.4 P. ( w ) = n / n = 0.6 ( 1-1 ) Để ý rằng Phần Trăm tiên nghiệm trên không phải trọn vẹn phụ thuộc vào vào nhàmáy sản xuất mà nó đa phần vào chất lượng của nguyên vật liệu. Tương tự một bác sĩchuyên khoa tim không thể nào trấn áp Phần Trăm bệnh nhồi máu cơ tim của mộtnhóm dân cư. Prevalences hoàn toàn có thể làm điều đó do tại nó tương quan đến trạng thái tựnhiên. Giả sử bài toán nhu yếu thực thi một quyết định hành động không rõ ràng, chẳng hạnchọ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 tinlà Xác Suất tiên nghiệm thì ta sẽ chọn lớp w. Với cách này tất cả chúng ta mong rằng nó chỉsai 40 % số lần. Giả sử rằng tất cả chúng ta hoàn toàn có thể đo được vecto đặc trưng của nút chai, p ( w | x ) làxác suất có điều kiện kèm theo diễn đạt Xác Suất để đối tượng người dùng x thuộc lớp w. Nếu tất cả chúng ta có thểxác định Xác Suất p ( w | x ) và p ( w | x ) dễ thấy rằng :  Nếu P. ( w | x ) > P. ( w | x ) ta phân x vào w  Nếu P. ( w | x ) < P. ( w | x ) ta phân x vào w  Nếu P. ( w | x ) = P. ( w | x ) chọn tùy ýTóm lại : if P. ( w | x ) > P. ( w2 | x ) then xelse x. ( 1-2 a ) Thuật toán Bayes và ứng dụngXác suất hậu nghiệm P. ( w | x ) hoàn toàn có thể tính được nếu tất cả chúng ta biết pdfs ( những hàmmật độ Phần Trăm ) của những phân phối vec tơ đặc trưng của 2 lớp. Sau đó ta tính những xácsuất p ( x | w ), là Phần Trăm để đối tượng người dùng thuộc lớp wcó đặc trưng là x gọi làlikelihood of x tạm dịch là năng lực xảy ra x hay là hài hòa và hợp lý của x. Thực tế ta dùngcông thức Bayes : ( 1-3 ) Với : Lưu ý rằng P. ( w ) và P. ( w | x ) là những Xác Suất rời rạc, trái lại p ( x | w ) và p ( x ) làcác giá trị của hàm tỷ lệ Xác Suất. Để ý rằng khi so sánh ( 1-2 a ) ta có giá trị chung làp ( x ) do đó ta viết lại : if p ( x | w ) P. ( w ) > p ( x | w ) P. ( w ) then xelse x. ( 1-4 ) Hay là : then xelse x. ( 1-4 a ) Trong công thức ( 1-4 a ) thì v ( x ) gọi là tỷ số hài hòa và hợp lý ( likelihood ratio ) ( ) ( | w ) ( w ) i ip x p x P. ( | w ) ( w ) ( w | ) ( ) i ip x Pp xp x1 22 1 ( | w ) ( w ) ( ) ( | w ) ( w ) p x pv xp x p   Thuật toán Bayes và ứng dụngHình 1 : Biểu đồ của đặc trưng N cho hai lớp học của những nút chai. Giá trịngưỡng N = 65 được ghi lại bằng một đường thẳng đứngGiả 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 những Xác Suất likelihood : p ( x | w ) = 20/24 = 0.833 → P. ( w ) p ( x | w ) = 0.333 ( 1/5 a ) p ( x | w ) = 16/23 = 0.696 → P. ( w ) p ( x | w ) = 0.418 ( 1/5 b ) Ta sẽ phân x = [ 65 ] vào lớp wmặc dù hài hòa và hợp lý ( likelihood ) của wlớn hơncủa wHình 2 minh họa tác động ảnh hưởng của việc kiểm soát và điều chỉnh ngưỡng Phần Trăm tiên nghiệmđến những hàm tỷ lệ Xác Suất.  Xác suất tiên nghiệm giống hệt ( equal prevalences ). Với những hàm mật độxác suất như nhau, ngưỡng pháp luật là một nửa khoảng cách đến phần tửtrung bình. Số lượng những trường hợp phân lớp sai tương ứng với vùng đượctô đậ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 wlớn hơn của w. Ngưỡng quyết định hành động thay thếcác lớp có Phần Trăm tiên nghiệm nhỏ hơn. Vì vậy giảm số trường hợp của lớpcó Tỷ Lệ tiên nghiệm cao có vẻ như có vẻ như thuận tiện. Thuật toán Bayes và ứng dụngHình 2 : Xác suất tiên nghiệm giống hệt ( a ), không như nhau ( b ). Chúng ta thấy rằng thật sự độ lệch ngưỡng quyết định hành động đã dẫn đến lớp wtốthơn lớp w. Điều này nghe có vẻ như hài hòa và hợp lý kể từ khi mà giờ đây lớp wxuất hiện thườngxuyên hơn. Khi độ sai toàn phần tăng lên điều kỳ lạ là sự ảnh hưởng tác động của Tỷ Lệ tiênnghiệm là có lợi. Câu vấn đáp cho câu hỏi này là tương quan đến chủ đề phân lớp mạohiểm, mà sẽ được trình diễn ngay giờ đây. Chúng ta giả định rằng giá của một nút chai ( cork stopper ) thuộc lớp wlà0. 025 £, lớp wlà 0.015 £. Giả sử là những nút chai lớp wđược dùng cho những chai đặcbiệt, còn những nút chai lớp wthì dùng cho những chai thông thường. Nếu ta phân lớp sai một nút chai lớp wthì sẽ bị mất 0.025 – 0.015 = 0.01 £. Nếu phân lớp sai một nút chai lớp wthì dẫn đến nó sẽ bị vô hiệu 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âncho loại chai đặc biệt quan trọng.  NB – Hành động của việc sử dụng một nút chai ( cork stopper ) để phâncho loại chai thông thường.  w = S ( siêu lớp ) ; w = A ( lớp trung bình ) Thuật toán Bayes và ứng dụngHình 3 : Kết quả phân lớp của cork stoppers với Phần Trăm tiên nghiệm không đồngnhất : 0.4 cho lớp w1 và 0.6 cho lớp w2Định nghĩa : ij = λ ( α | w ) là độ mất mát với hành vi αkhi mà lớp đúng là w, với { SB, NB }. 11 = λ ( α | w ) = λ ( SB | S ) = 0,12 = λ ( α | w ) = λ ( SB | A ) = 0.015,21 = λ ( α | w ) = λ ( NB | S ) = 0.01,22 = λ ( α | w ) = λ ( NB | A ) = 0. Thuật toán Bayes và ứng dụng10Chúng ta hoàn toàn có thể sắp xếp λijthành ma trận hao phí Λ. Λ = ( 1-6 ) Vì thế độ mất mát với hành vi sử dụng một nút chai ( diễn đạt bởi vectơ đặctrưng x ) và phân vào cho những chai đặc biệt quan trọng hoàn toàn có thể được bộc lộ như sau : R ( α | x ) = R ( SB | x ) = λ ( SB | S ) P. ( S | x ) + λ ( SB | A ) P. ( A | x ) ( 1-6 a ) R ( α | 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ì : R ( α | x ) = R ( NB | x ) = λ ( NB | S ) P. ( S | x ) + λ ( NB | A ) P. ( A | x ) ( 1-6 b ) R ( α | x ) = 0.01 P. ( S | x ) Chúng ta giả định rằng nhìn nhận rủi ro đáng tiếc chỉ chịu tác động ảnh hưởng từ quyết định hành động sai. Do vậy một quyết định hành động đúng chuẩn sẽ không gây ra thiệt hại λii = 0, như trong ( 1-6 ). Nếu thay vì 2 lớp tất cả chúng ta có c lớp thì sự mất mát ứng với một hành vi αsẽ là : ( 1-6 c ) Chúng ta chăm sóc đến việc giảm thiểu mức rủi ro đáng tiếc trung bình tính cho mộtlượng lớn nút chai bất kể. Công thức Bayes cho rủi ro đáng tiếc nhỏ nhất làm được điều nàybằng cách cực tiểu hóa những rủi ro đáng tiếc có điều kiện kèm theo R ( α | x ). Giả sử bắt đầu rằng những quyết định hành động sai lầm đáng tiếc có cùng một mất mát, chúng có tỉ lệvới một đơn vị chức năng mất mát : ( 1-7 a ) Trong trường hợp này từ toàn bộ những Tỷ Lệ hậu nghiệm đều tăng lên một, tất cả chúng ta cần phải cực tiểu hóa : ( 1-7 b ) 0 0.0150.01 0       ( | ) ( | ) ( | ) i j jR x P. x      ( | ) ij jif i jif j j       ( | ) ( | ) 1 ( | ) i j ji jR x P. x P. x       Thuật toán Bayes và ứng dụng11Điều này tương tự với việc tất cả chúng ta cực lớn P. ( w | x ), luật quyết địnhBayes cho rủi ro đáng tiếc cực tiểu tương ứng với việc tổng quát hóa yếu tố : Phân lớp wnếu P. ( w | x ) > P. ( w | x ), ij ( 1-7 c ) Tóm lại : luật quyết định hành động Bayes cho rủi ro đáng tiếc cực tiểu, khi sự phân lớp đúng thì không bịmất mát và nếu như phân lớp sai thì có mất mát, ta cần phải chọn được lớp có xácsuất hậu nghiệm là cức đại. Hàm quyết định hành động cho lớp wlà : ( x ) = P. ( w | x ) ( 4-18 d ) Bây giờ hãy xem xét những trường hợp khác nhau của những thiệt hại xảy ra chonhững quyết định hành động sai lầm đáng tiếc, để cho đơn thuần giả sử c = 2. Dựa vào những biểu thức ( 1-6 a ) và ( 1-6 b ) thật dễ nhận thấy rằng một nút chai sẽ thuộc lớp wnếu : Hay là ( 1-8 ) Vì thế ngưỡng quyết định hành động so với tỷ số hài hòa và hợp lý ( likelihood ) thì nó nghiêng về sựmất mát. Ta hoàn toàn có thể setup luật quyết định hành động Bayes như hình 5. Tương tự tất cả chúng ta hoàn toàn có thể kiểm soát và điều chỉnh Tỷ Lệ tiên nghiệm như sau : ; ( 1-8 a ) 12 2 121 1 2 ( ) ( | ) ( ) ( | ) P. w P. x wP w P. x w12 2 ( | ) P. x   21 1 ( | ) P. x   21 121 1 12 2 ( ) ( ) ( ) ( ) P. wP wP w P. w   12 221 1 12 2 ( ) ( ) ( ) ( ) P. wP wP w P. w   Thuật toán Bayes và ứng dụng12Với sự mất mát λ12 = 0.015 và λ21 = 0.01, sử dụng Tỷ Lệ tiên nghiệm ởtrên ta được P. ( w ) = 0.308 và P. ( w ) = 0.692. Sự thiệt hại sẽ là lớn hơn nếu nhưphân lớp sai lớp wdo đó cần tăng P. ( w ) lên so với P. ( w ). Kết quả của việc điềuchỉnh là giảm số lượng những thành phần thuộc lớp wbị phân lớp sai thành w. Xem kếtquả phân lớp ở hình ở hình 6. Ta hoàn toàn có thể tính giá trị rủi ro đáng tiếc trung bình trường hợp có 2 lớp : ( 1-9 ) 1 212 2 21 1 12 12 21 21 ( | ) ( ) ( | ) ( ) R RR P w x p x dx P. w x p x dx Pe Pe           Thuật toán Bayes và ứng dụng13và Rlà miền quyết định hành động của lớpvà lớp, còn Peijlà Xác Suất saisố của sự quyết định hành động lớp làkhi mà lớp đúng làChúng ta hãy sử dụng tập dữ liệu đào tạo và giảng dạy để nhìn nhận những sai số này, Pe12 = 0.1 và Pe21 = 0.46 ( xem hình 6 ). Rủi ro trung bình so với mỗi nút chai bây giờlà : R = 0.015 Pe12 + 0.01 Pe21 = 0.0061 Є. Với Ω là tập những lớp ta có công thức ( 1-9 ) tổng quát : ( 1-9 a ) Luật quyết định hành động Bayes không phải là lựa chọn duy nhất trong thống kê phânlớp. Cũng quan tâm rằng, trong trong thực tiễn một trong những cố gắng nỗ lực để giảm thiểu rủi ro đáng tiếc trungbình là sử dụng ước đạt của hàm tỷ lệ Tỷ Lệ tính được từ một tập dữ liệu huấnluyện, như tất cả chúng ta đã làm ở trên cho cork Stoppers. Nếu tất cả chúng ta có những địa thế căn cứ đểtin rằng những hàm phân phối Xác Suất thỏa mãn nhu cầu tham số mẫu, thì ta thay thế sửa chữa việc tínhcác tham biến thích hợp từ tập huấn luyện. Hoặc là tất cả chúng ta cũng hoàn toàn có thể sử dụngphương pháp cực tiểu hóa rủi ro đáng tiếc theo kinh nghiệm tay nghề ( empirical risk minimization ( ERM ) ), nguyên tắc là cực tiểu hóa rủi ro đáng tiếc theo kinh nghiệm tay nghề thay vì rủi ro đáng tiếc thực tiễn. 2.3 Phân lớp Bayes chuẩn tắcCho đến giờ tất cả chúng ta vẫn chưa giả định đặc trưng của phân phối mẫu cholikelihoods. Tuy nhiên, quy mô chuẩn tắc là một giả định hài hòa và hợp lý. Mô hình chuẩn tắccó tương quan đến định lý số lượng giới hạn TT nổi tiếng, theo định lý này thì tổng của mộtlượng lớn những biến ngẫu nhiên độc lập và phân phối như nhau sẽ có phân phối hội tụvề luật chuẩn. Thực tế ta có được một giao động đến luật chuẩn tắc, thậm chí còn với cả mộtsố lượng tương đối nhỏ được thêm vào những biến ngẫu nhiên. Đối với những đặc trưng cóthể được coi là hiệu quả của việc bổ trợ những biến độc lập, thường thì giả định là có thểchấp nhận. Likelihood chuẩn tắc của lớp ωđược màn biểu diễn bởi hàm tỷ lệ Xác Suất : ( ( ) | ) (, ) ( ( ) | ) (, ) ( ) i ii i i iX XR x P. x dx x P. x p x dx                     Thuật toán Bayes và ứng dụng14và ∑ là những tham số phân phối, đến giờ thì ta đã sử dụng những ước lượngmẫu mvà CHình 7 minh họa phân phối chuẩn trong trường hợp có hai chiều. Cho một tập huấn luyện có n mẫu T = { x, x, … x } được miêu tả bởi một phânphối với hàm tỷ lệ Xác Suất là p ( T | θ ), θ là một vec tơ tham số của phân phối ( ví dụ điển hình như vec tơ trung bình của phân phối chuẩn ). Một cách đáng quan tâm tínhđược ước đạt mẫu của vectơ tham biến là cực đại hóa hàm tỷ lệ Xác Suất p ( T | θ ), hoàn toàn có thể coi dây là một hàm của θ gọi là likelihood of θ cho tập huấn luyện. Giả sử rằngmỗi mẫu là đưa vào độc lập từ một tập vô hạn, tất cả chúng ta hoàn toàn có thể biểu lộ likelihood nhưsau : Khi sử dụng ước đạt hài hòa và hợp lý cực lớn ( maximum likelihood estimation ) củacác biến phân phối thì nó thường thuận tiện hơn là tính cưc đại của ln [ p ( T | θ ) ], điều nàylà tương tự nhau. Với phân phối Gauss ước đạt mẫu được cho bởi những côngthức ( 1-10 a ) và ( 1-10 b ) chính là ước đạt hài hòa và hợp lý cực lớn và nó sẽ quy tụ về một giá trịthực. ( | ) ( | ) p T p x   Thuật toán Bayes và ứng dụng15Như hoàn toàn có thể nhìn thấy từ ( 1-10 ), những mặt phẳng của tỷ lệ Tỷ Lệ như nhau vớihợp lý chuẩn ( normal likelihood ) thỏa mãn nhu cầu Mahalanobis metric : Bây giờ tất cả chúng ta liên tục tính hàm quyết định hành động cho những đặc trưng của phân phốichuẩn : ( x ) = P. ( ω | x ) = P. ( ω ) p ( x | ω ) ( 1-11 ) đổi khác logarit ta được : Bằng cách sử dụng những hàm quyết định hành động, rõ ràng nhờ vào Mahalanobismetric, ta hoàn toàn có thể thiết kế xây dựng phân lớp Bayes với rủi ro đáng tiếc nhỏ nhất, đây là phân lớp tối ưu. Chú ý rằng công thức ( 1-11 b ) sử dụng giá trị thật của khoảng cách Mahalanobis, trongkhi mà trước đó tất cả chúng ta sử dụng ước đạt của khoảng cách này. Với trường hợp covariance như nhau cho tổng thể những lớp ( ∑ = ∑ ) và bỏ lỡ cáchằng số ta được : ( 1-11 c ) ( ) ( ) ( ) ln ( ) i i i ih x x x P         Thuật toán Bayes và ứng dụng16Với bài toán 2 lớp, biệt số d ( x ) = h ( x ) – h ( x ) là dễ đàng giám sát : Qua đó ta có được hàm quyết định hành động tuyến tínhHai lớp phân biệt với phân phối chuẩn, Phần Trăm tiên nghiệm như nhau vàcovariance và vẫn còn có một công thức rất đơn thuần cho Xác Suất của lỗi của phânlớp : Thuật toán Bayes và ứng dụng17bình phương của khoảng cách Bhattacharyya, một khoảng cách Mahalanobiscủa sai phân trung bình, biểu lộ tính dễ tách lớp. Hình 8 bộc lộ dáng điệu của Pe với sự tăng dần của bình phương khảng cáchBhattacharyya. Hàm này giảm dần theo cấp số mũ và nó quy tụ tiệm cận tới 0. Vì vậythật khó để giảm sai số phân lớp khi giá trị này là nhỏ. Lưu ý rằng ngay cả khi những phân phối mẫu không phải là phân phối chuẩn, miễnlà chúng đối xứng và phải tuân theo Mahalanobis metric, thì tất cả chúng ta sẽ thu được mặtphân lớp quyết định hành động tương tự như như phân lớp chuẩn, mặc dầu có sự độc lạ về đánh giásai số và Tỷ Lệ hậu nghiệm. Để minh họa ta hãy xét hai lớp có Phần Trăm tiên nghiệmđồng nhất và có ba loại phân phối đối xứng, với cùng độ lệch tiêu chuẩn và trung bình0 và 2.3 như hình 9. Thuật toán Bayes và ứng dụng18Phân lớp tối ưu cho 3 trường hợp sử dụng cùng một ngưỡng quyết định hành động có giátrị 1.15, tuy nhiên những sai số phân lớp là khác nhau :  Nomal : Pe = 1 – erf ( 2.3 / 2 ) = 12.5 %  Cauchy : Pe = 22.7 %  Logistic : Pe = 24.0 % Kết quả thực nghiệm cho thấy, khi ma trận covariance đưa ra độ lệch số lượng giới hạn, thì sự phân lớp hoàn toàn có thể thực thi một cách tựa như với chiêu thức tối ưu với điềukiện những covariance là giống hệt. điều này là hài hòa và hợp lý vì khi những covariance không khácbiệt nhau nhiều thì sự độc lạ giữa những giải pháp bậc hai và tuyến tính chỉ đáng kểkhi những mẫu cách xa nguyên mẫu như ở hình 10. Chúng ta sẽ minh họa bằng cách sử dụng bộ tài liệu Norm2c2d. Sai số lýthuyết so với trường hợp hai lớp, hai chiều và bộ tài liệu trên là : Ước lượng sai số của bộ tài liệu huấn luyện và đào tạo cho tập dữ liệu này là 5 %. Bằngcách đưa vào sai số ± 0.1 vào những giá trị của ma trận ánh xạ A cho bộ tài liệu, với độlệch nằm giữa 15 % và 42 % giá rị của covariance, ta được sai số tập huấn luyện là6 %.   0.8 0.8 22 3 8 1 ( 2 ) 7.9 % 0.8 1.6 3P e erf                  Thuật toán Bayes và ứng dụng19Trở lại với tài liệu những nút chai, ta có bài toán phân lớp sử dụng 2 đặc trưng Nvà PRT với Tỷ Lệ tiên nghiệm như nhau. Lưu ý phân lớp thống kê ngoài tính toánsố nó không làm biến hóa những phép toán, cho nên vì thế mà những hiệu quả đạt được là giống nhaunếu như sử dụng PRT hay PRT10. Một list riêng những Tỷ Lệ hậu nghiệm có ích trong đo lường và thống kê những sai sốphân lớp, xem hình 11. Cho những ma trận covariances ở trong bảng 1. Độ lệch của những thành phần trong matrận covariance so với giá trị TT nằm trong khoảng chừng từ 5 % đến 30 %. Hình dángcủa những cụm là tựa như nhau, đây là dẫn chứng để tin rằng việc phân lớp là gần vớitối ưu. Bằng cách sử dụng hàm quyết định hành động dựa trên những ma trận covariance riêng không liên quan gì đến nhau, thay vì chỉ một ma trận tổng covariance, ta sẽ thiết kế xây dựng được đường biên giới quyết địnhbâc hai. Tuy nhiên phân lớp bằng đường bậc hai không dễ chiều độ lệch hơn so với phân lớptuyến tính, đặc biệt quan trọng là trong khoảng trống nhiều chiều, và ta cần phải có một lượng lớntập tài liệu đào tạo và giảng dạy ( xem ví dụ của Fukunaga and Hayes, 1989 ) .

Source: https://mindovermetal.org
Category: Ứng dụng hay

5/5 - (1 vote)