Một thuật toán lọc công tác cho trường hợp ít dữ liệu

Tóm tắt Một thuật toán lọc công tác cho trường hợp ít dữ liệu: ...au do´ ru´t go.n k´ıch thu .´o.c ma traˆ.n ba`˘ng ca´ch chı’ giu˜ . la. i nhu˜ .ng vecto. rieˆng tu.o.ng u´.ng vo´.i nhu˜.ng gia´ tri. rieˆng lo´ .n nhaˆ´t. Nho`. vaˆ.y, nhu˜ .ng da˘.c tru .ng ban da`ˆu du.o.. c bieˆ´n doˆ’i tha`nh da˘.c tru .ng mo´.i. Da˘. c dieˆ’m cu’a da˘.c tru .ng mo´...m(x), ta co´ theˆ’ vieˆ´t: fm(x) = argmin fm E[e−yF (x)(y − fm(x)) 2]. (7) Thay ky` vo.ng ba`˘ng gia´ tri. trung b`ınh treˆn du˜ . lieˆ.u huaˆ´n luyeˆ.n va` su .’ du. ng ky´ hieˆ.u tro.ng soˆ´ wi = e −yiF (xi), (7) du.o.. c vieˆ´t la. i nhu . sau: fm(x) = argmin fm N∑ i=1 wi(yi − fm(x...ong (7) va` (11) ba`˘ng gia´ tri. trung b`ınh cho ca’ K boˆ. phaˆn loa. i. Dieˆ’m kha´c nhau duy nhaˆ´t o .’ daˆy la` ta. i moˆ˜i bu .´o.c la˘.p, thuaˆ. t toa´n co´ theˆ’ khoˆng t`ım du .o.. c ha`m f k m() cho sai soˆ´ nho’ nhaˆ´t do pha’ i xa´c di.nh taˆ.p con S(t) moˆ. t ca´ch tham lam va`...

pdf13 trang | Chia sẻ: havih72 | Lượt xem: 278 | Lượt tải: 0download
Nội dung tài liệu Một thuật toán lọc công tác cho trường hợp ít dữ liệu, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
t qua’ toˆ´t. Chu´ng toˆi
cu˜ng su.’ du. ng soˆ´ bu
.´o.c la˘.p na`y trong thu
.’ nghieˆ.m cu’a mı`nh.
3.3. Boosting doˆ`ng tho`.i cho nhie`ˆu ba`i toa´n phaˆn loa. i
Trong pha`ˆn na`y, chu´ng toˆi de`ˆ xuaˆ´t su.’ du.ng phu
.o.ng pha´p boosting ca’ i tieˆ´n da˜ du.o.. c tr`ınh
ba`y trong ta`i lieˆ.u tham kha’o [14] deˆ’ thu
.
. c hieˆ.n doˆ`ng tho`
.i cho nhie`ˆu ba`i toa´n phaˆn loa. i, tu
.o.ng
u´.ng vo´.i nhie`ˆu ngu.`o.i du`ng trong tru.`o.ng ho.. p lo. c coˆ.ng ta´c.
Vo´.i taˆ.p K ngu
.`o.i du`ng U ;N ma˘. t ha`ng G va` gia´ tri. da´nh gia´ rij nhu
. da˜ cho trong pha`ˆn 2,
ta co´ taˆ´t ca’ K ba`i toa´n phaˆn loa. i, ba`i toa´n thu´
. k, k = 1, ..., K du.o.. c cho bo
.’ i N v´ı du. huaˆ´n
luyeˆ.n (x
k
1, y
k
1), ..., (x
k
N, y
k
N ), trong do´ y
k
j = r
k
j tu´
.c la` da´nh gia´ cu’a ngu.`o.i du`ng k cho ma˘.t ha`ng
j, va` xkj = (r1j, ..., r(k−1)j, r(k+1)j, ..., rKj) tu´
.c la` da´nh gia´ cu’a taˆ´t ca’ ngu.`o.i du`ng cho ma˘. t
ha`ng j tru`. ngu.`o.i du`ng k. Ca`ˆn lu.u y´ ra`˘ng, chı’ nhu˜.ng coˆ.t co´ rkj 6= φ mo´
.i du.o.. c su
.’ du.ng la`m
v´ı du. huaˆ´n luyeˆ.n trong ba`i toa´n thu´
. k (coˆ.t cu’a ma˘. t ha`ng 1,2,3 trong v´ı du. o
.’ Ba’ng 1). Tuy
nhieˆn, deˆ’ cho do.n gia’n, ta vaˆ˜n lieˆ. t keˆ ca’ nhu˜
.ng v´ı du. co´ rkj = φ. Nhu˜
.ng v´ı du. na`y sau do´ se˜
du.o.. c ga´n tro.ng soˆ´ ba`˘ng 0 va` do vaˆ.y khoˆng a’nh hu
.o.’ ng to´.i keˆ´t qua’ huaˆ´n luyeˆ.n.
Dieˆ’m kha´c bieˆ.t chu’ yeˆ´u cu’a thuaˆ.t toa´n boosting cho nhie`ˆu ba`i toa´n doˆ`ng tho`
.i la` ta. i moˆ˜i
vo`ng la˘.p, thuaˆ.t toa´n se˜ t`ım moˆ.t da˘.c tru
.ng cho phe´p gia’m sai soˆ´ du.. doa´n doˆ`ng tho`
.i cho moˆ. t
taˆ.p con ca´c ba`i toa´n phaˆn loa. i thay v`ı gia’m sai soˆ´ cu’a moˆ.t ba`i toa´n phaˆn loa. i nhu
. moˆ ta’ o.’
treˆn. Da˘.c tru
.ng na`y do´ng vai tro` da˘.c tru
.ng chung cho taˆ´t ca’ ca´c ba`i toa´n phaˆn loa. i trong taˆ.p
con du.o.. c cho.n. Ca´c taˆ.p con du
.o.. c cho.n trong nhu˜
.ng vo`ng kha´c nhau cu’a thuaˆ. t toa´n co´ theˆ’
giao nhau.
Cu. theˆ’, thuaˆ.t toa´n boosting se˜ du
.o.. c thay doˆ’i nhu
. sau. Moˆ˜i v´ı du. huaˆ´n luyeˆ.n thu´
. j se˜ co´
k tro.ng soˆ´ w
k
j , k = 1, ..., K. Moˆ˜i tro.ng soˆ´ du
.o.. c su
.’ du.ng khi v´ı du. do´ du
.o.. c du`ng vo´
.i boˆ. phaˆn
MOˆ. T THUAˆ. T TOA´N LO. C COˆ. NG TA´C CHO TRU
.
O`
.
NG HO.
.
P I´T DU˜
.
LIEˆ. U 67
loa. i thu´
. k. wkj = 0 neˆ´u r
k
j = 0 tu´
.c la` v´ı du. j khoˆng tham gia va`o huaˆ´n luyeˆ.n boˆ. phaˆn loa. i k.
Sai soˆ´ phaˆn loa. i du
.o.. c t´ınh ba˘`ng toˆ’ng sai soˆ´ cho taˆ´t ca’ K boˆ. phaˆn loa. i:
J =
K∑
k=1
N∑
i=1
wki (y
k
i − f
k
m(xi))
2. (13)
Ta.i moˆ˜i vo`ng la˘.p m, go. i S(t) la` taˆ.p con ca´c ba`i toa´n. Thay v`ı xa´c di.nh da˘.c tru
.ng f toˆ´t
nhaˆ´t cho tu`.ng ba`i toa´n rieˆng le’ nhu. o.’ pha`ˆn tru.´o.c, thuaˆ.t toa´n ca`ˆn xa´c di.nh da˘.c tru
.ng chung
cho taˆ´t ca’ ba`i toa´n thuoˆ.c S(t) va` cho.n goˆ´c quyeˆ´t di.nh tu
.o.ng u´.ng sao cho sai soˆ´ (13) la` nho’
nhaˆ´t. Goˆ´c caˆy quyeˆ´t di.nh se˜ co´ da.ng nhu
. sau:
fkm(x, t) =
{
aSδ(x
f > 0) + bSδ(x
f ≤ 0) khi k ∈ S(t)
ck khi k 6∈ S(t)
(14)
O
.’ daˆy, gia´ tri. goˆ´c caˆy quyeˆ´t di.nh phu. thuoˆ.c va`o vieˆ.c taˆ.p con S(t) du
.o.. c cho.n la` taˆ.p con na`o
va` v`ı vaˆ.y ta ky´ hieˆ.u ha`m fm la` ha`m cu’a t. Ky´ hieˆ.u f
k
m(x, t) du
.o.. c hieˆ’u la` ha`m phaˆn loa. i yeˆ´u
ta. i bu
.´o.c thu´. m cho ba`i toa´n thu´. k va` ha`m na`y chung cho taˆ.p con S(t) ca´c ba`i toa´n phaˆn
loa. i. Do gia´ tri. ha`m loˆ˜i (13) cu˜ng phu. thuoˆ.c va`o taˆ.p con S(t) neˆn ha`m loˆ˜i (13) cu˜ng ca`ˆn vieˆ´t
la. i tha`nh ha`m cu’a tham soˆ´ t nhu
. sau:
J(t) =
K∑
k=1
N∑
i=1
wki (y
k
i − f
k
m(xi, t))
2. (15)
Dieˆ’m kha´c nhau co. ba’n so vo´.i goˆ´c quyeˆ´t di.nh o
.’ pha`ˆn tru.´o.c la` goˆ´c quyeˆ´t di.nh (14) phaˆn
bieˆ.t tru
.`o.ng ho..p ba`i toa´n k thuoˆ.c taˆ.p con S(t) va` tru
.`o.ng ho.. p khoˆng thuoˆ.c. Trong tru
.`o.ng
ho.. p k khoˆng thuoˆ.c S(t), ha`m fm(x) se˜ du
.o.. c da˘.t ba`˘ng ha`˘ng soˆ´ c
k deˆ’ tra´nh tru.`o.ng ho.. p lu
.
. a
cho.n boˆ. phaˆn loa. i moˆ. t ca´ch t`ınh co`
. do cheˆnh leˆ.ch soˆ´ lu
.o.. ng giu˜
.a v´ı du. huaˆ´n luyeˆ.n 1 va` −1
(cha˘’ ng ha.n trong tru
.`o.ng ho.. p qua´ nhie`ˆu v´ı du. 1 th`ı co´ theˆ’ luoˆn du
.
. doa´n nha˜n la` 1 khoˆng ca`ˆn
quan taˆm to´.i da˘. c tru
.ng).
Vo´.i moˆ˜i taˆ.p con S(t), gia’ i ba`i toa´n cu
.
. c tieˆ’u hoa´ sai soˆ´ (13) se˜ cho keˆ´t qua’ sau:
aS(f) =
∑
k∈S(t)
∑
i w
k
i y
k
i δ(x
f
i > 0)∑
k∈S(t)
∑
iw
k
i δ(x
f
i > 0)
, (16)
bS(f) =
∑
k∈S(t)
∑
iw
k
i y
k
i δ(x
f
i ≤ 0)∑
k∈S(t)
∑
i w
k
i δ(x
f
i ≤ 0)
, (17)
ck =
∑
i w
k
i y
k
i∑
iw
k
i , k 6∈ S(t)
. (18)
Ta.i moˆ˜i bu
.´o.c la˘.p, thuaˆ.t toa´n se˜ lu
.
. a cho.n taˆ.p con S(t) toˆ´t nhaˆ´t, tu´
.c la` taˆ.p con cho gia´ tri.
ha`m loˆ˜i (13) nho’ nhaˆ´t va` goˆ´c quyeˆ´t di.nh toˆ´t nhaˆ´t cho taˆ.p con do´. Ky´ hieˆ.u F
k(x) la` boˆ. phaˆn
loa. i ch´ınh xa´c cho ba`i toa´n phaˆn loa. i thu´
. k, ta co´ thuaˆ.t toa´n boosting mo´
.i du.o.. c theˆ’ hieˆ.n nhu
.
sau.
Thuaˆ.t toa´n 2. Thuaˆ.t toa´n boosting ca’ i tieˆ´n su
.’ du.ng da˘. c tru
.ng chung cho nhie`ˆu ba`i toa´n
1. Kho.’ i ta.o w
k
j = 1 neˆ´u r
k
j 6= φ va` w
k
j = 0 neˆ´u r
k
j = φ, i = 1, .., N ; k = 1, .., K
Kho.’ i ta.o F
k(x) = 0
68 NGUYE˜ˆN DUY PHU.O.NG, TU`. MINH PHU.O.NG
2. La˘.p vo´
.i m = 1, ...,M
a. La˘.p vo´
.i taˆ.p con ca´c ba`i toa´n S(t)
i. T´ınh tham soˆ´ aS, bS, va` c
k theo (16), (17), (18)
ii. T´ınh sai soˆ´ J(t) =
∑K
k=1
∑N
i=1 w
k
i (y
k
i − f
k
m(xi, t))
2
b. Cho.n taˆ.p S(t) toˆ´t nhaˆ´t t
∗ = argminJ(t)
c. Caˆ.p nhaˆ.t F
k(x)← F k(x) + fkm(x, t
∗)
d. Caˆ.p nhaˆ.t tro.ng soˆ´ w
k
i ← w
k
i e
−yk
i
fm(xi,t
∗)
3. Tra’ ve`ˆ boˆ. phaˆn loa. i sign[F
k(x)]
Moˆ.t chi tieˆ´t ca`ˆn la`m ro˜ doˆ´i vo´
.i thuaˆ.t toa´n treˆn la` ca´ch xa´c di.nh taˆ.p con S(t). Neˆ´u lieˆ. t
keˆ taˆ´t ca’ taˆ.p con S(t) tu`
. K ba`i toa´n th`ı soˆ´ lu.o.. ng taˆ.p con se˜ la` O(2
K). Do vaˆ.y, thay v`ı lieˆ. t
keˆ, chu´ng toˆi su.’ du. ng phu
.o.ng pha´p t`ım kieˆ´m tham lam. Tru.´o.c tieˆn, xa´c di.nh taˆ.p con t chı’
bao goˆ`m 1 ba`i toa´n va` co´ sai soˆ´ (13) nho’ nhaˆ´t. Sau do´ theˆm moˆ. t ba`i toa´n kha´c va`o taˆ.p con t
tru.´o.c do´ sao cho t mo´.i co´ sai soˆ´ nho’ nhaˆ´t. Tieˆ´p tu. c nhu
. vaˆ.y cho deˆ´n khi theˆm taˆ´t ca’ K ba`i
toa´n va`o t. Trong soˆ´ ca´c taˆ.p t nhu
. vaˆ.y lu
.
. a cho.n t co´ sai soˆ´ nho’ nhaˆ´t. Doˆ. phu´
.c ta.p t´ınh toa´n
khi do´ se˜ la` O(K2) cho moˆ˜i bu.´o.c la˘.p va` O(MK
2) cho toa`n boˆ. thuaˆ.t toa´n.
Phaˆn t´ıch ly´ thuyeˆ´t
Ca´c phaˆn t´ıch ly´ thuyeˆ´t doˆ´i vo´.i thuaˆ.t toa´n gentleboost o
.’ Mu. c 3.1 vaˆ˜n du´ng doˆ´i vo´
.i Thuaˆ.t
toa´n 2 neˆ´u thay ha`m loˆ˜i (6) ba`˘ng exp(−
∑
k y
kF k(x)) va` thay ky` vo.ng trong (7) va` (11) ba`˘ng
gia´ tri. trung b`ınh cho ca’ K boˆ. phaˆn loa. i. Dieˆ’m kha´c nhau duy nhaˆ´t o
.’ daˆy la` ta. i moˆ˜i bu
.´o.c
la˘.p, thuaˆ. t toa´n co´ theˆ’ khoˆng t`ım du
.o.. c ha`m f
k
m() cho sai soˆ´ nho’ nhaˆ´t do pha’ i xa´c di.nh taˆ.p
con S(t) moˆ. t ca´ch tham lam va` do vaˆ.y toˆ´c doˆ. hoˆ. i tu. se˜ chaˆ.m ho
.n so tru.`o.ng ho.. p t`ım du
.o.. c
fkm() toˆ´i u
.u. Tuy nhieˆn, thuaˆ.t toa´n vaˆ˜n cho phe´p gia’m da`ˆn loˆ˜i phaˆn loa. i ta. i moˆ˜i bu
.´o.c la˘.p va`
cho keˆ´t qua’ toˆ´t trong ca´c thu.’ nghieˆ.m.
Ca´c keˆ´t qua’ lieˆn quan
Nhu. da˜ no´i o.’ treˆn, phu.o.ng pha´p lo. c coˆ.ng ta´c vu`
.a tr`ınh ba`y du.. a treˆn vieˆ.c su
.’ du.ng thuaˆ.t
toa´n boosting vo´.i ca´c da˘.c tru
.ng chung do Torralba et al. de`ˆ xuaˆ´t cho ba`i toa´n nhaˆ.n da.ng
a’nh va` du.o.. c tr`ınh ba`y trong ta`i lieˆ.u [14]. Tuy nhieˆn, t´ınh chaˆ´t ba`i toa´n cu˜ng nhu
. mu. c d´ıch
su.’ du. ng da˘.c tru
.ng chung trong hai tru.`o.ng ho.. p la` kha´c nhau:
- Trong [14], thuaˆ.t toa´n du
.o.. c de`ˆ xuaˆ´t cho phaˆn loa. i doˆ´i tu
.o.. ng a’nh. Ba`i toa´n phaˆn loa. i ca´c
doˆ´i tu.o.. ng a’nh trong [14] voˆ´n la` moˆ. t ba`i toa´n phaˆn loa. i nhie`ˆu lo´
.p (multiclass classification),
trong khi do´ ba`i toa´n lo. c coˆ.ng ta´c o
.’ daˆy bao goˆ`m nhie`ˆu ba`i toa´n phaˆn loa. i hai lo´
.p (binary
classification). Su.. kha´c nhau na`y do`i ho’ i ca´ch bieˆ’u die˜ˆn phu` ho
.
.p deˆ’ a´p du. ng thuaˆ.t toa´n
boosting vu`.a tr`ınh ba`y.
- Mu. c tieˆu su
.’ du.ng boosting ca’ i tieˆ´n trong [14] la` pha´t hieˆ.n da˘. c tru
.ng chung ma` ca´c doˆ´i
tu.o.. ng a’nh chia se’ deˆ’ ta˘ng toˆ´c doˆ. (do khoˆng pha’ i chia ba`i toa´n nhie`ˆu lo´
.p tha`nh nhie`ˆu ba`i
toa´n hai lo´.p) va` gia’m du˜. lieˆ.u huaˆ´n luyeˆ.n, trong khi do´ mu. c tieˆu cu’a lo. c coˆ.ng ta´c la` pha´t
hieˆ.n nhu˜
.ng ngu.`o.i du`ng tu.o.ng tu.. nhau va` gia’ i quyeˆ´t vaˆ´n de`ˆ du˜
. lieˆ.u thu
.a tho´.t (nhie`ˆu du˜. lieˆ.u
thieˆ´u). Vieˆ.c t`ım ra ca´c taˆ.p con S(t) (tu
.o.ng u´.ng vo´.i taˆ.p ngu
.`o.i du`ng cu`ng so.’ th´ıch) se˜ co´ y´
ngh˜ıa quan tro. ng doˆ´i vo´
.i lo. c coˆ.ng ta´c khi ca`ˆn gia’ i th´ıch ly´ do du
.a ra quyeˆ´t di.nh.
MOˆ. T THUAˆ. T TOA´N LO. C COˆ. NG TA´C CHO TRU
.
O`
.
NG HO.
.
P I´T DU˜
.
LIEˆ. U 69
4. THU
.’ NGHIEˆ.M VA` KEˆ´T QUA
’
Hieˆ.u qua’ lo. c coˆ.ng ta´c du
.o.. c xa´c di.nh du
.
. a treˆn kha’ na˘ng thuaˆ.t toa´n du
.
. doa´n ch´ınh xa´c
da´nh gia´ cu’a kha´ch ha`ng. Phu.o.ng pha´p tr`ınh ba`ˆy o.’ treˆn du.o.. c da´nh gia´ va` so sa´nh vo´
.i ca´c
phu.o.ng pha´p kha´c theo thu’ tu. c moˆ ta’ du
.´o.i daˆy.
Tru.´o.c tieˆn, toa`n boˆ. kha´ch ha`ng du
.o.. c chia tha`nh hai pha`ˆn, moˆ. t pha`ˆn Utr du
.o.. c su
.’ du. ng
la`m du˜. lieˆ.u huaˆ´n luyeˆ.n, pha`ˆn co`n la. i Ute du
.o.. c su
.’ du. ng deˆ’ kieˆ’m tra. Du˜
. lieˆ.u huaˆ´n luyeˆ.n du
.o.. c
su.’ du.ng deˆ’ xaˆy du
.
. ng moˆ h`ınh theo thuaˆ.t toa´n moˆ ta’ o
.’ treˆn. Vo´.i moˆ˜i kha´ch ha`ng thuoˆ. c taˆ.p
du˜. lieˆ.u kieˆ’m tra u, ca´c da´nh gia´ (da˜ co´) cu’a kha´ch ha`ng du
.o.. c chia la`m hai pha`ˆn Ou va` Pu.
Ou du
.o.. c coi la` da˜ bieˆ´t, trong khi do´ Pu la` da´nh gia´ ca`ˆn du
.
. doa´n tu`
. du˜. lieˆ.u huaˆ´n luyeˆ.n va`
Ou.
Sai soˆ´ du.. doa´n MAEu vo´
.i moˆ˜i kha´ch ha`ng u thuoˆ.c taˆ.p du˜
. lieˆ.u kieˆ’m tra du
.o.. c t´ınh ba`˘ng
trung coˆ.ng sai soˆ´ tuyeˆ.t doˆ´i giu˜
.a gia´ tri. du
.
. doa´n va` gia´ tri. thu
.
. c doˆ´i vo´
.i taˆ´t ca’ ma˘. t ha`ng thuoˆ.c
taˆ.p Pu.
MAEu =
1
|Pu|
∑
y∈Pu
|rˆuy − r
u
y |.
Sai soˆ´ du.. doa´n treˆn toa`n taˆ.p du˜
. lieˆ.u kieˆ’m tra du
.o.. c t´ınh ba`˘ng trung b`ınh coˆ.ng sai soˆ´ du
.
.
doa´n cho moˆ˜i kha´ch ha`ng thuoˆ.c Ute.
MAE =
∑
u∈Ute
MAEu
|Ute|
.
Gia´ tri. MAE ca`ng nho’ ca`ng toˆ´t, tu´
.c la` phu.o.ng pha´p ca`ng ch´ınh xa´c.
4.1. Du˜. lieˆ.u thu
.’ nghieˆ.m
Thuaˆ.t toa´n lo. c coˆ.ng ta´c du
.o.. c thu
.’ nghieˆ.m treˆn hai boˆ. du˜
. lieˆ.u EachMovie [16] va` MovieLens
[17]. Daˆy la` hai boˆ. du˜
. lieˆ.u thu
.`o.ng du.o.. c su
.’ du. ng deˆ’ da´nh gia´ ca´c phu
.o.ng pha´p lo. c.
EachMovie du.o.. c xaˆy du
.
. ng bo
.’ i trung taˆm nghieˆn cu´.u heˆ. thoˆ´ng thoˆng tin cu’a ha˜ng Compaq.
Boˆ. du˜
. lieˆ.u na`y goˆ`m 72916 ngu
.`o.i du`ng, 1628 boˆ. phim vo´
.i 2811983 da´nh gia´, ca´c mu´.c da´nh
gia´ du.o.. c cho tu`
. 1 deˆ´n 6 (ch´ınh xa´c la` 0.0, 0.2, 0.4, 0.6, 0.8, 1.0) , trung b`ınh soˆ´ lu.o.. ng phim
ngu.`o.i du`ng chu.a da´nh gia´ la` 97.6%. Hai mu´.c da´nh gia´ cao nhaˆ´t (0.8 va` 1.0) du.o.. c bieˆ´n doˆ’i
tha`nh “th´ıch” (+1) va` boˆ´n mu´.c da´nh gia´ co`n la. i du
.o.. c bieˆ´n doˆ’i tha`nh “khoˆng th´ıch” (−1)
(daˆy la` phu.o.ng pha´p bieˆ´n doˆ’i du.o.. c su
.’ du. ng trong [5]).
MovieLens la` co. so.’ du˜. lieˆ.u du
.o.. c xaˆy du
.
. ng bo
.’ i nho´m nghieˆn cu´.u GroupLens cu’a tru.`o.ng
da. i ho.c Minnesota. MovieLans co´ 6040 ngu
.`o.i du`ng, 3900 boˆ. phim, 1000209 da´nh gia´, ca´c
mu´.c da´nh gia´ cho tu`. 1 deˆ´n 5, trung b`ınh soˆ´ lu.o.. ng phim ngu
.`o.i du`ng chu.a da´nh gia´ la` 95.7%.
Tu.o.ng tu.. nhu
. treˆn, hai mu´.c da´nh gia´ cao nhaˆ´t du.o.. c bieˆ´n doˆ’i tha`nh “th´ıch”, ca´c mu´
.c co`n la. i
tha`nh “khoˆng th´ıch”.
Deˆ’ ha.n cheˆ´ a’nh hu
.o.’ ng cu’a t`ınh tra.ng du˜
. lieˆ.u qua´ thu
.a tho´.t, chu´ng toˆi chı’ lu.. a cho.n nhu˜
.ng
kha´ch ha`ng co´ da´nh gia´ ı´t nhaˆ´t cho 20 boˆ. phim. Trong soˆ´ nhu˜
.ng ngu.`o.i du`ng thoa’ ma˜n die`ˆu
kieˆ.n na`y, chu´ng toˆi cho.n ra boˆ. du˜
. lieˆ.u thu´
. nhaˆ´t tu`. EachMovie bao goˆ`m 10000 ngu.`o.i du`ng.
Boˆ. du˜
. lieˆ.u thu´
. hai tu`. MovieLens bao goˆ`m da´nh gia´ cu’a 500 ngu.`o.i du`ng.
70 NGUYE˜ˆN DUY PHU.O.NG, TU`. MINH PHU.O.NG
4.2. So sa´nh va` keˆ´t qua’
Phu.o.ng pha´p boosting vo´.i da˘.c tru
.ng chung (ky´ hieˆ.u la` MC Boost) tr`ınh ba`y trong pha`ˆn
3.2 du.o.. c so sa´nh vo´
.i nhu˜.ng phu.o.ng pha´p sau:
- Phu.o.ng pha´p k ha`ng xo´m ga`ˆn nhaˆ´t su.’ du.ng doˆ. tu
.o.ng quan Pearson (ky´ hieˆ.u la` KPC)
[6]. Daˆy la` phu.o.ng pha´p lo. c coˆ.ng ta´c thoˆng du. ng nhaˆ´t va` thu
.`o.ng du.o.. c su
.’ du. ng nhu
. phu.o.ng
pha´p tieˆu chuaˆ’n khi so sa´nh.
- Phu.o.ng pha´p boosting khoˆng su.’ du.ng da˘.c tru
.ng chung nhu. tr`ınh ba`y trong Mu. c 3.1.
Ca´ch thu´.c tieˆ´n ha`nh thu.’ nghieˆ.m va` so sa´nh nhu
. sau:
La`ˆn lu.o.. t 100, 200, va` 300 ngu
.`o.i du`ng du.o.. c lu
.
. a cho.n ngaˆ˜u nhieˆn tu`
. boˆ. du˜
. lieˆ.u MovieLens
va` du.o.. c du`ng la`m du˜
. lieˆ.u huaˆ´n luyeˆ.n, 200 ngu
.`o.i du`ng du.o.. c lu
.
. a cho.n ngaˆ˜u nhieˆn trong soˆ´
co`n la. i deˆ’ la`m taˆ.p kieˆ’m tra.
Doˆ´i vo´.i boˆ. du˜
. lieˆ.u EachMovies, la`ˆn lu
.o.. t 1000, 2000, va` 6000 ngu
.`o.i du`ng du.o.. c cho.n la`m
taˆ.p huaˆ´n luyeˆ.n, 4000 ngu
.`o.i du`ng co`n la. i du
.o.. c du`ng deˆ’ kieˆ’m tra.
Deˆ’ thu.’ nghieˆ.m kha’ na˘ng cu’a phu
.o.ng pha´p mo´.i de`ˆ xuaˆ´t so vo´.i nhu˜.ng phu.o.ng pha´p kha´c
trong tru.`o.ng ho.. p co´ ı´t du˜
. lieˆ.u, chu´ng toˆi thay doˆ’i soˆ´ lu
.o.. ng da´nh gia´ cu’a moˆ˜i ngu
.`o.i du`ng
trong taˆ.p kieˆ’m tra sao cho soˆ´ lu
.o.. ng da´nh gia´ da˜ bieˆ´t la`ˆn lu
.o.. t la` 5, 10 va` 20, pha`ˆn co`n la. i la`
nhu˜.ng da´nh gia´ ca`ˆn du.. doa´n. Gia´ tri. MAE khi thu
.’ nghieˆ.m vo´
.i hai boˆ. du˜
. lieˆ.u MovieLens va`
EachMovies du.o.. c theˆ’ hieˆ.n trong Ba’ng 2 va` Ba’ng 3. Nhu
. da˜ no´i o.’ treˆn, gia´ tri. MAE nho’ ho
.n
chu´.ng to’ phu.o.ng pha´p ch´ınh xa´c ho.n.
Ba’ng 2. Keˆ´t qua’ thu.’ nghieˆ.m vo´
.i MovieLens
Keˆ´t qua’ thu.’ nghieˆ.m cho thaˆ´y ca’ hai phu
.o.ng pha´p lo.c coˆ.ng ta´c ba`˘ng phaˆn loa. i boosting
de`ˆu cho keˆ´t qua’ toˆ´t ho.n so vo´.i phu.o.ng pha´p truye`ˆn thoˆ´ng su.’ du.ng doˆ. tu
.o.ng quan Pearson.
Sai soˆ´ cu’a boosting vo´.i mo. i k´ıch thu
.´o.c du˜. lieˆ.u huaˆ´n luyeˆ.n va` soˆ´ lu
.o.. ng da´nh gia´ cho tru
.´o.c
cu’a ngu.`o.i du`ng kieˆ’m tra de`ˆu nho’ ho.n phu.o.ng pha´p tu.o.ng quan Pearson.
Trong tru.`o.ng ho.. p du’ du˜
. lieˆ.u, cu. theˆ’ la` khi bieˆ´t tru
.´o.c nhie`ˆu da´nh gia´ cu’a ngu.`o.i du`ng
trong taˆ.p kieˆ’m tra, phu
.o.ng pha´p GentleBoost cho keˆ´t qua’ toˆ´t ho.n so vo´.i MC Boost. Co´ theˆ’
gia’ i th´ıch keˆ´t qua’ na`y la` do GentBoost cho phe´p cho.n da˘. c tru
.ng toˆ´i u.u ho.n doˆ´i vo´.i tu`.ng ba`i
toa´n phaˆn loa. i trong khi MC Boost chı’ cho.n du
.o.. c da˘.c tru
.ng toˆ´i u.u cho ca’ nho´m ba`i toa´n
phaˆn loa. i.
Tuy nhieˆn, khi du˜. lieˆ.u ı´t di, cu. theˆ’ la` khi chı’ bieˆ´t tru
.´o.c 5 hoa˘.c 10 da´nh gia´ cu’a ngu
.`o.i du`ng
kieˆ’m tra th`ı trong da soˆ´ tru.`o.ng ho.. p, MC Boost cho sai soˆ´ MAE nho’ ho
.n so vo´.i GentleBoost.
Ly´ do chu’ yeˆ´u la` do MC Boost cho phe´p keˆ´t ho.. p thoˆng tin tu`
. nhu˜.ng ngu.`o.i du`ng tu.o.ng tu..
MOˆ. T THUAˆ. T TOA´N LO. C COˆ. NG TA´C CHO TRU
.
O`
.
NG HO.
.
P I´T DU˜
.
LIEˆ. U 71
vo´.i ngu.`o.i du`ng kieˆ’m tra thoˆng qua ca´c da˘.c tru
.ng chung va` do vaˆ.y gia’m du
.o.. c a’nh hu
.o.’ ng cu’a
vieˆ.c thieˆ´u nha˜n phaˆn loa. i.
Ba’ng 3. Keˆ´t qua’ thu.’ nghieˆ.m vo´
.i EachMovies
5. KEˆ´T LUAˆ. N
Ba`i ba´o da˜ tr`ınh ba`y moˆ. t phu
.o.ng pha´p lo. c coˆ.ng ta´c ba`˘ng ca´ch su
.’ du. ng ky˜ thuaˆ.t phaˆn
loa. i boosting va` goˆ´c caˆy quyeˆ´t di.nh doˆ`ng tho`
.i cho nhie`ˆu ngu.`o.i du`ng. Daˆy la` moˆ.t ca’ i tieˆ´n cu’a
thuaˆ.t toa´n boosting, trong do´ vieˆ.c lu
.
. a cho.n da˘.c tru
.ng cho moˆ˜i boˆ. phaˆn loa. i yeˆ´u du
.o.. c thu
.
. c
hieˆ.n doˆ`ng tho`
.i treˆn moˆ. t nho´m ngu
.`o.i du`ng tu.o.ng tu.. nhau. U
.
u dieˆ’m chu’ yeˆ´u cu’a phu.o.ng
pha´p na`y la` vieˆ.c phaˆn loa. i doˆ`ng tho`
.i tu`.ng nho´m ngu.`o.i du`ng cho phe´p su.’ du. ng thoˆng tin tu`
.
nhu˜.ng ngu.`o.i du`ng tu.o.ng tu.. nhau va` nho`
. vaˆ.y ca’ i thieˆ.n doˆ. ch´ınh xa´c phaˆn loa. i khi co´ ı´t du˜
.
lieˆ.u, v´ı du. khi ngu
.`o.i du`ng ca`ˆn du.. doa´n chı’ da´nh gia´ raˆ´t ı´t ma˘.t ha`ng tru
.´o.c do´. Keˆ´t qua’ thu.’
nghieˆ.m treˆn hai boˆ. du˜
. lieˆ.u MovieLens va` EachMovies da˜ cho thaˆ´y phu
.o.ng pha´p de`ˆ xuaˆ´t cho
keˆ´t qua’ toˆ´t ho.n hai phu.o.ng pha´p kha´c trong tru.`o.ng ho.. p ı´t du˜
. lieˆ.u.
TA`I LIEˆ. U THAM KHA
’O
[1] G. Adomavicius, A. Tuzhilin, Toward the next generation of recommender systems: A survey
of the state-of-the-art and possible extensions, IEEE Transactions On Knowledge And Data
Engineering 17 (6) (2005).
[2] M. Balabanovic and Y. Shoham, Fab: content-based, collaborative recommendation, Comm.
ACM 40 (3) (1997) , 66–72.
[3] C. Basu, H. Hirsh, W. Cohen, Recommendation as classification: Using social and content-based
information in recommendation, Proc. of 15 Nat. Conf. on Artificial Intelligence (AAAI-98),
Madison, WI, USA, 1998 (714–720).
[4] J. Baxter, A model for inductive bias learning, J. of Artificial Intelligence Research 12 (2000)
149–198.
[5] D. Billsus and M. Pazzani, Learning collaborative information filters, Proc. Int’l Conf. Machine
Learning, Madison, WI, USA, 1998.
[6] J. S. Breese, D. Heckerman, and C. Kadie, Empirical analysis of predictive algorithms for col-
laborative filtering, Proc. of 14th Conf. on Uncertainty in Artificial Intelligence, Madison,
WI, USA, 1998 (43–52).
72 NGUYE˜ˆN DUY PHU.O.NG, TU`. MINH PHU.O.NG
[7] R. Caruana, Multi-task learning, Machine Learning 28 (1997) 41–75.
[8] Y. Freund and R. Schapire, Experiments with a new boosting algorithm, In Machine Learning,
Proceedings of the Thirteenth International Conference, Bari, Italy, 1996 (148–156).
[9] J. Friedman, T. Hastie, and R. Tibshirani, Additive logistic regression: a statistical view of
boosting, The Annals of Statistics 38 (2) (April, 2000) 337–374.
[10] J. Herlocker, J. Konstan, A. Borchers, and J. Riedl, An algorithmic framework for performing
collaborative filtering, Proceedings of the 22nd Annual International ACM SIGIR Confer-
ence on Research and Development in Information Retrieval, SIGIR ’99, Berkeley, CA,
USA, 1999 ( 230–237).
[11] J. Herlocker, L.G. Konstan, Terveen, and J. Riedl, Evaluating collaborative filtering recom-
mender systems, ACM Transactions on Information Systems 22 (1) (2004) 5–53.
[12] R.E. Schapire, The boosting approach to machine learning: an overview, Proc. MSRI Work-
shop Nonlinear Estimation and Classification , Berkeley, CA, Mar. 2001.
[13] U. Shardanand and P. Maes, Social information filtering: algorithms for automating ‘Word of
Mouth’, Proc. Conf. Human Factors in Computing Systems, Denver, Colorado, USA, 1995.
[14] A. Torralba, K.P. Murphy, and W.T. Freeman, Sharing visual features for multiclass and multi-
view object detection, IEEE Trans. On Pattern Analysis And Machine Intelligence 29 (5)
(May 2007).
[15] G.R. Xue, C. Lin, Q. Yang, W. Xi, H. J. Zeng, Y. Yu, and Z. Chen, Scalable collaborative
filtering using cluster-based smoothing, Proc. of SIGIR, Salvador, Brazil, 2005 (114–121).
[16] 
[17] 
Nhaˆ. n ba`i nga`y 1 - 10 - 2007
Nhaˆ. n la. i sau su
.’ a nga`y 22 - 2 -2008

File đính kèm:

  • pdfmot_thuat_toan_loc_cong_tac_cho_truong_hop_it_du_lieu.pdf
Ebook liên quan