Toán học - Phân loại bằng Bayes

Phân loại bằng Bayes Lê Phong Dàn bài
Giới thiệu ◦ Bài tóan ◦ Hướng tiếp cận Bayes
Lý thuyết ra quyết định Bayes
Phân lớp bằng biệt hàm
Một số vấn đề mở rộng
Xây dựng hệ phân lớp Giới thiệu
Bài toán phân loại (Pattern Classification) Xác định đối tượng có đặc trưng x thuộc lớp nào trong c lớp w1, w2,, wc.
Lý thuyết ra quyết định Bayes là nền tảng cho các phương pháp phân lớp thống kê. w1 w2 wc x ? ? ? ? Giới thiệu (tt)
Giả sử đã biết trước xác suất tiền định P(w = wi) i = 1..c
Gọi p(x|wi) là mật độ xác suất của đặc trưng x trong lớp wi.
Khi đó, xác suất hậu định để đối tượng có đặc trưng x thuộc lớp wi là ◦ Trong đó
Để ngắn gọn, viết Giới thiệu (tt) w1 w2 wc x P(w1|x) P(w2|x) P(wi|x) P(wc|x) P(w1) P(w2) P(wi) P(wc) p(x|wi), i=1..c
Dựa trên P(wi|x) để quyết định đối tượng x thuộc lớp nào. Dàn bài
Giới thiệu
Lý thuyết ra quyết định Bayes ◦ Trường hợp đơn giản – 2 lớp ◦ Trường hợp tổng quát ◦ Ví dụ
Phân lớp bằng biệt hàm
Một số vấn đề mở rộng
Xây dựng hệ phân lớp Lý thuyết ra quyết định Bayes
Về mặt cảm quan, chọn lớp wbest sao cho P(wbest|x) = min P(wi|x) i=1..c
Xem xét 2 trường hợp ◦ Trường hợp đơn giản 2 lớp ◦ Trường hợp tổng quát Trường hợp đơn giản
Có 2 lớp w1 và w2 Trường hợp đơn giản (tt)
Trung bình xác suất lỗi (average probability of error) ◦ Trong đó là xác suất lỗi khi đưa ra quyết định
Luật 1 tương ứng làm cực tiểu hóa trung bình xác suất lỗi Trường hợp tổng quát
Mở rộng giả thiết với 1. Số lớp là bất kỳ. 2. a hành động α1, α2,, αa (ví dụ như hành động αi là phân x vào lớp wi). 3. Hàm tiêu tốn λ(αi|wj) thể hiện cái giá phải trả khi thực hiện hành động αi trong trường hợp đối tượng thuộc lớp wj (ví dụ như là chi phí khi phân loại sai). Trường hợp tổng quát (tt)
Xác suất lỗi được tổng quát hóa bằng rủi ro có điều kiện Thể hiện cái giá phải trả cho hành động αi khi đối tượng có đặc trưng x
Xác suất lỗi trung bình được tổng quát hóa bằng rủi ro toàn bộ ◦ Trong đó α(x) nhận các hành động αi (i=1..a) tương ứng với đặc trưng x
tìm α(x) để đạt cực tiểu R. Trường hợp tổng quát (tt)
Luật 2 đạt được cực tiểu cho R* - còn được gọi là rủi ro Bayes. Hàm tiêu tốn đối xứng
Trường hợp đặc biệt: αi là hành động phân đối tượng x vào lớp wi với hàm tiêu tốn
Ý nghĩa: không trả giá nếu phân loại đúng, ngược lại trả giá là 1.
Hàm rủi ro có điều kiện Ví dụ
2 lớp P(w1)=2/3, P(w2)=1/3
3 hành động ◦ α1 = “xếp đối tượng vào lớp w1” ◦ α2 = “xếp đối tượng vào lớp w2” ◦ α3 = “không phân lớp”
Hàm tiêu tốn λ Ví dụ (tt)
Tính Ví dụ (tt) α1 α3 α2 Dàn bài
Giới thiệu
Lý thuyết ra quyết định Bayes
Phân lớp bằng biệt hàm ◦ Biệt hàm, vùng ra quyết định ◦ Biệt hàm cho phân phối chuẩn
Một số vấn đề mở rộng
Xây dựng hệ phân lớp Biệt hàm
Mỗi lớp wi có một biệt hàm (discriminant function) gi(x). Với mỗi đối tượng có đặc trưng x, hệ phân lớp sẽ phân x và lớp wi nếu Biệt hàm (tt)
Một số trường hợp ◦ Tính chi phí bằng xác suất lỗi trung bình ◦ Tính chi phí bằng rủi ro toàn cục hoặc Vùng ra quyết định
Phân hoạch không gian đặc trưng ra c phần không giao nhau R1,, Rc với x thuộc Ri nếu x được phân vào lớp wi
Ri được gọi là vùng ra quyết định (decision region)
Biên bao quanh các Ri được gọi là biên ra quyết định (decision boundary) Vùng ra quyết định (tt) Biệt hàm cho phân phối chuẩn
Xây dựng hệ phân lớp với tiêu chí cực tiểu hóa trung bình xác suất lỗi
Sử dụng biệt hàm
Giả thiết do đó Trường hợp 1:
Ở mọi lớp: các đặc trưng thành phần độc lập với nhau và có cùng phương sai
Biên ra quyết định có được nhờ giải phương trình
Suy ra biên ◦ Trong đó 2 i σ=Σ I 2σ ( ) ( )i jg g=x x 0( ) 0T − =w x x i j= −w µ µ 2 0 2 ( )1 ( ) ln ( ) 2 ( ) i i j i j ji j P P ωσ ω = + − − − x µ µ µ µ µ µ Trường hợp 1:
Nếu P(wi) = P(wj) 2 i σ=Σ I Trường hợp 1:
Nếu P(wi) ≠ P(wj) 2 i σ=Σ I Trường hợp 2:
Hiệp phương sai ở mọi lớp đều như nhau và bất kỳ
Biên ra quyết định ◦ Trong đó i =Σ Σ 0( ) 0T − =w x x 1( )i j−= −w Σ µ µ 0 1 ( )1 1( ) ln ( ) 2 ( ) ( ) ( ) i i j i jT i j i j j P P ω ω− = + − − − − x µ µ µ µ µ µ Σ µ µ Trường hợp 2: i =Σ Σ Trường hợp 3: bất kỳ
Đầy là trường hợp tổng quát nhất: các ma trận hiệp phương sai không nhất thiết bằng nhau.
Biệt hàm là hàm bậc 2
Biên ra quyết định có thể là hyperquadaric (hyperplane, cặp hyperplane, hypersphare,) iΣ 1 1 1 0 1 1( ) 2 ln ln ( ) 2 2 T T T i i i i i i i i i T T i i i g P w ω− − − = − − + − +  = + + x x Σ x µ Σ x µ Σ µ Σ x Wx w x Trường hợp 3: bất kỳiΣ Trường hợp 3: bất kỳiΣ Trường hợp 3: bất kỳiΣ Ví dụ:
2 lớp w1, w2 với P(w1) = P(w2) = 0.5 2 1 2 2 1 1( ) (0,3) exp . 2 32 3 1 1( ) (2,1) exp ( 2) 22 xp x N p x N x ω pi ω pi   = = −      = = − −    Ví dụ (tt)
Biệt hàm
Vùng ra quyết định R1 thỏa g1(x) > g2(x) 2 1 1 2 2 2 1 1( ) ln 3 ln ( ) 6 2 1( ) 2 2 ln ( ) 2 g x x P g x x x P ω ω = − − + = − + − + ( ) ( ) 2 2 1 2 2 1 2 1 1 1ln3 ln ( ) 2 2 ln ( ) 6 2 2 2 12 12 3ln 3 6ln ( ) 6 ln ( ) 0 ,0.84 5.16, x P x x P x x P P x ω ω ω ω − − + > − + − + ⇔ − + − + − > ⇔ ∈ −∞ ∪ ∞ Ví dụ (tt) Dàn bài
Giới thiệu
Lý thuyết ra quyết định Bayes
Phân lớp bằng biệt hàm
Một số vấn đềmở rộng ◦ Đặc trưng rời rạc ◦ Đặc trưng khiếm khuyết
Xây dựng hệ phân lớp Đặc trưng rời rạc
x chỉ nhận 1 trong m giá trị v1,, vm ∈ ℜd
Thay p(x|w) bằng P(x|w) Đặc trưng bị thiếu và biến dạng bởi nhiễu
Khi đã xây dựng xong hệ phân lớp.
Với một đặc trưng mới có khiếm khuyết đưa vào ◦ Do thiếu một vài đặc trưng thành phần ◦ Do nhiễu
Cần phải khắc phục những khiếm khuyết đó
(tự tìm hiểu trong Phân lớp Bayes.pdf) Dàn bài
Giới thiệu
Lý thuyết ra quyết định Bayes
Phân lớp bằng biệt hàm
Một số vấn đề mở rộng
Xây dựng hệ phân lớp ◦ Huấn luyện và kiểm tra ◦ Independent Test Sample ◦ Cross-validation Xây dựng hệ phân lớp
Tập dữ liệu D = {x1, x2, , xn}
2 bước xây dựng hệ phân lớp ◦ B1: Huấn luyện để tìm ra tham số cho mô hình phân lớp ◦ B2: Kiểm tra ‘độ tốt’ của hệ phân lớp tìm được
Cần chia D ra làm 2 tập ◦ Dtrain cho bước 1 ◦ Dtest cho bước 2 Bước 1: huấn luyện P(wi) i=1..c cost Bước 2: kiểm tra cost test c i cc i D n∑ =1 )( Independent Test Sample
Được ứng dụng khi tập mẫu lớn - Lấy ngẫu nhiên ntrain đối tượng ở D cho vào Dtrain, phần còn lại ntest đối tượng cho vào Dtest. - Dùng Dtrain để huấn luyện - Dùng Dtest để kiểm tra - Xác định tỉ lệ phân loại đúng test c i cc i D n CCP ∑ = = 1 )( )( Cross-validation
Được ứng dụng khi tập mẫu nhỏ - Chia tập mẫu thành k phần bằng nhau D1,, Dk - Ncc := 0 - For i từ 1
k Dtrain = D\Di; Dtest = Di Dùng Dtrain để huấn luyện Dùng Dtest để kiểm tra Ncc := Ncc + - End for ∑ = c i cc in 1 )( D NCCP cc=)(