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`...
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:
- mot_thuat_toan_loc_cong_tac_cho_truong_hop_it_du_lieu.pdf