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ớpBiệ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
43 trang |
Chia sẻ: trungkhoi17 | Lượt xem: 446 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Phân loại bằng Bayes (Bản hay), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
PhânPhân lolo ii bb ngng BayesBayes
Lê Phong
DDàànn bb ààii
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
GiGi ii thithi uu
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 w 1, w 2,, w c.
x
?
?
? ?
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ê.
GiGi ii thithi uu (tt)(tt)
Gi s t tr c xác su t ti n nh
P(w = w i) i = 1..c
G i p( x|w i) là m t xác su t c a c tr ng x trong
l p w i.
Khi ó, xác su t h u nh i t ng có c tr ng
x thu c l p w i là
◦ Trong ó
ng n g n, vi t
GiGi ii thithi uu (tt)(tt)
p(x|w i), i=1..c
x
P(w |x)
1 P(w 2|x) P(w i|x) P(w c|x)
w1 w2 wc
P(w ) P(w )
1 P(w 2) P(w i) c
D a trên P(w i|x) quy t nh i t ng x thu c
l p nào.
DDàànn bb ààii
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ýLý thuythuy tt rara quyquy tt nhnh BayesBayes
V m t c m quan, ch n l p w best sao cho
P(w best |x) = min P(w i|x) i=1..c
Xem xét 2 ng h p
◦ Tr ng h p ơ n gi n 2 l p
◦ Tr ng h p t ng quát
TrTr ngng hh pp ơ ơ nn gigi nn
Có 2 l p w 1 và w2
TrTr ngng hh pp ơ ơ nn gigi nn (tt)(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 ơ ng
làm c c ti u hóa trung bình xác su t l i
TrTr ngng hh pp tt ngng ququ áátt
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 ng i là
phân x vào l p w i).
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 ng h p i t ng
thu c l p w j (ví d à chi phí khi phân lo i sai).
TrTr ngng hh pp tt ngng ququ áátt (tt)(tt)
Xác su t l i c t ng quát hóa b ng r i ro có u
ki n
Th hi n cái giá ph i tr cho hành ng i 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.
TrTr ngng hh pp tt ngng ququ áátt (tt)(tt)
Lu t 2 t c c c ti u cho R* - c g i là
r i ro Bayes.
HHààmm tiêutiêu tt nn ii xx ngng
Tr ng h p c bi t: i là hành ng phân i
t ng x vào l p w i 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ó u ki n
VVíí dd
2 l p P(w 1)=2/3, P(w 2)=1/3
3 hành ng
◦ 1 = “x p i t ng vào l p w 1”
◦ 2 = “x p i t ng vào l p w 2”
◦ 3 = “không phân l p”
Hàm tiêu t n λ
VVíí dd (tt)(tt)
Tính
VVíí dd (tt)(tt)
1 3 2
DDàànn bb ààii
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
BiBi tt hh ààmm
M i l p w i 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 w i n u
BiBi tt hh ààmm (tt)(tt)
M t s ng h p
◦ Tính chi phí b ng xác su t l i trung bình
ho c
◦ Tính chi phí b ng r i ro toàn c c
VVùùngng rara quyquy tt nhnh
Phân ho ch không gian c tr ng ra c ph n không
giao nhau R 1,, R c v i x thu c R i n u x c phân
vào l p w i
Ri c g i là vùng ra quy t nh (decision region)
Biên bao quanh các R i c g i là biên ra quy t
nh (decision boundary)
VVùùngng rara quyquy tt nhnh (tt)(tt)
BiBi tt hh ààmm chocho phânphân phph ii chuchu nn
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 ó
2
TrTr ngng hh pp 1:1: Σi = σ I
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 σ 2
Biên ra quy t nh có c nh gi i ph ơ ng trình
gi()x= g j () x
T
Suy ra biên w( x− x 0 ) = 0
◦ Trong ó w =µi − µ j
1 σ 2 P(ω )
x =+−(µµ ) lni ( µµ − )
0 2i j 2 P (ω ) i j
µi− µ j j
2
TrTr ngng hh pp 1:1: Σi = σ I
N u P(w i) = P(w j)
2
TrTr ngng hh pp 1:1: Σi = σ I
N u P(w i) P(w j)
TrTr ngng hh pp 2:2: Σi = Σ
Hi p ph ơ ng sai m i l p u nh nhau và b t k
Biên ra quy t nh
T
w( x− x 0 ) = 0
◦ Trong ó
−1
w =Σ( µi − µ j )
1 1 P(ω )
=+−i −
x0 (µµi j )T −1 ln ( µµi j )
2 (µij− µ )( Σµ ij − µ )()P ω j
TrTr ngng hh pp 2:2: Σi = Σ
TrTr ngng hh pp 3:3: Σ i bb tt kk
y là 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
1T−1 T − 1 T − 1 1
gi(x )=− x Σ ix − 2µ iiiii Σ x +µΣµ − ln Σ i + lnP (ω i )
2 2
T T
=xWxi + w i x + w i 0
Biên ra quy t nh có th là hyperquadaric
(hyperplane, c p hyperplane, hypersphare,)
TrTr ngng hh pp 3:3: Σ i bb tt kk
TrTr ngng hh pp 3:3: Σ i bb tt kk
TrTr ngng hh pp 3:3: Σ i bb tt kk
VVíí dd ::
2 l p w 1, w 2 v i P(w 1) = P(w 2) = 0.5
1 1 x2
p( xω1 )= N (0,3) = exp − .
2π 3 2 3
1 1
pxN(ω )= (2,1) = exp −− ( x 2) 2
2 2π 2
VVíí dd (tt)(tt)
Bi t hàm
1 1
gx( )=− x2 − ln 3 + ln P (ω )
1 6 2 1
1
gx()=− xx2 + 2 −+ 2ln() P ω
2 2 2
Vùng ra quy t nh R 1 th a g 1(x) > g 2(x)
1 1 1
−x2 −ln3ln() + Pω >− xxP2 +−+ 2 2ln() ω
6 21 2 2
2
⇔−+−+2xx 12 12 3ln3 6ln P (ω1 ) − 6ln P ( ω 2 ) > 0
⇔x ∈()() −∞,0.84 ∪ 5.16, ∞
VVíí dd (tt)(tt)
DDàànn bb ààii
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
cc trtr ngng rr ii rr cc
d
x ch nh n 1 trong m giá tr v1,, v m ∈ ℜ
Thay p( x|w) b ng P( x|w)
cc trtr ngng bb thithi uu vv àà bibi nn dd ngng bb ii
nhinhi uu
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)
DDàànn bb ààii
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âyXây dd ngng hh phânphân ll pp
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 c 1
◦ Dtest c 2
BB cc 1:1: huhu nn luyluy nn
P(w i) i=1..c
cost
BB cc 2:2: kiki mm tratra
c
(i)
∑ n cc
i=1
Dtest
cost
IndependentIndependent TestTest SampleSample
c ng d ng khi t p m u l n
-Lấy ng ẫu nhiên n train đối t ượng ở D cho vào
Dtrain , ph ần còn l ại n test đối t ượng cho vào
Dtest .
- Dùng D train để hu ấn luy ện
- Dùng D test để ki ểm tra
- Xác định t ỉ lệ phân lo ại đúng
c
(i)
∑ n cc
P(CC ) = i=1
Dtest
CrossCross --validationvalidation
c ng d ng khi t p m u nh
- Chia t ập m ẫu thành k ph ần b ằng nhau D 1,, D k
-Ncc := 0
- For i t ừ 1 k
Dtrain = D\Di; D test = D i
Dùng D train để hu ấn luy ện
Dùng D test để ki ểm tra
c
(i)
Ncc := Ncc + ∑ n cc
- End for i=1
N
P(CC ) = cc
D
Các file đính kèm theo tài liệu này:
- bai_giang_phan_loai_bang_bayes_ban_hay.pdf