BO
GIAO DUC VA DAO TAO
• • •
TRUONG DAI HOC KINH TE TP.HO
CHi
MINH
• •
DE
TAl
NGHIEN
ciru
KHOA
HOC
CAP
CO
SO
•
. ' .
PHAN
TiCH
HOI
QUY BANG
SUPPORT
VECTOR
MACHINES (SVM)
MA
SO: CS-2007-01
BQ
GIAO
DUC.DAOTAO-
. .

CO
SO
•
' " , ;t,.
PHAN
TICH
HOI
QUY BANG
SUPPORT
VECTOR
MACHINES (SVM)
MA
SO: CS-2007-01
CHU NHI¢M: ThS. GVC HUYNH
VAN
DUC
THANH VrEN:
ThS. GV NGUYEN CONG
TRi
TP. HO
CHi
MINH NAM 2009
Ngay nay chung
ta
dang dung
tru&c
mot kh6i
luQ'ng
du kh6ng
16

nhung thuoc
tinh khac, ddn d8n du quan sat
duQ'c
thuang
c6 s6 chiSu
rAt
l&n
lam cho
cac phuang phap truySn th6ng gap nhiSu kh6 khan.
Sau thai ky hoang kim cua thJng
ke
rieng phdn (cac thap nien
1930-
1960,
v&i
phuang
phap
clfe
dc,zi
likelihood do Fisher
dS
xuAt
vao
dfiu
thap nien 1930, v6n lam
rAt
t6t
v&i
dfr
lieu c6 s6 chiSu nh6),

tidu tbn thdt cdu true (Structural Risk Minimization - SRM) da
duQ'c
xufit vao gifra
thap nien 1970
thvc nguyen ly
ERM
c6 kiSm soat
S\1'
phuc cua khong gian
gia thi8t.
Sau d6 (1990), cac mo hinh Support Vector Machines (SVM)
duQ'c
gi&i
nhu
Ia
mot
phuang phap cai dat
nguyen ly SRM.
Tu
d6 nay, cac thuat toan SVM da chung to
duQ'c
kha nang lam qua
v&i
dii c6 s6 chiSu
l&n.
Trang
dS
tai nay, chung toi
gi&i
mo hinh SVM nhu

sau han
vS
n6.
Ngmli ra chung toi cling da cai mot thuat toan
huAn
SVM, da trinh bay Hoi
thao Qu6c
gia
lfin
thu
Ill
Nghien
c(ru
ca
ban va
ung
d1,1ng
Cong thong tin nam 2007
(Hoi thao
F AIR07), va xay dvng mot chuang trinh minh hoa. Chung toi
da
dung chuang
tiinh nay
du
thvc t8
lAy
tu
mot
dS
tai nghien cuu

loi cam an chan thimh Phong
Qufm
ly khoa
hQc
-
HQ'p
tcic
quBc
da
kien cho chung toi hoan
tAt
tai nay; Cam
an
cac d6ng nghiep trong khoa Tin
hQc
quan
ly,
cac d6ng nghiep
tu
Khoa Cong ngM thong tin,
hQc
Khoa
hQc
t1,r
nhien
TpHCM, da tham gia va dong g6p cac y quy bau trong cac bu6i seminar
duQ'c
t6
chuc
cho tai nay.

MO
hinh
SVM
7
1.
Mo
hinh SVM tach
tuydn
tlnh 9
Bai toan tach 9
Mo hinh toan hoc 9
Mo hinh chiu
16i

12
2.
Mo
hinh tach phi tuyin
15
3.
Mo
hinh hdi quy
SVM.

19
C
J.
'
khA
•

ngau .
chinh phuong an 27
Xay d\fng bang tinh toan 29
Minh
hQa
29
Minh
hQa
trubng
hQl>
phi
31
toan SMO cua Platt [25]. 32
Heuristic tim i 33
Heuristic
ti1n
j , 3 3
2.
Thugt toan SMO
cho
biti
toim
hdi quy 34
Xay d\fng bang tinh toan
'"""'
37
Minh
hQa
38
K@t

qua thir nghiem 50
Chi
ml}c
• • • • • 52
Ill
ChU'ong
1:
D(it
vftn
d@
Bai toan
suy
luqn
quy
nqp
da c6
tu
han 2000 nam qua. Tuy nhien mai thS ky XVIII,
mf>i
lien he gifra nganh khoa
h(JC
thl!C
va
CRC
nganh khoa
h(JC
chinh
Xac
khac
nhu

Gauss
va
Laplace,
nhung
n8n tang that
S\1'
cua ly thuySt chi
dUQ'C
ddu vito
cu6i thap nien
1920. a
thai
d6, cite th6ng ke
mota
hfiu
nhu
daddy
du v6i nhi8u quy
luqt th6ng ke cho phep
mota
t6t cite biSn c6 xay ra trong thS gi6i thuc. Cling vao nhung
nam
1920 nay, cite
mo
hinh
ca
sa
cho
ca
hai tiSp can:

ke
hien trong thai ky
nay la cua
Karl Popper, Glivenko, Cantelli, Andrei N. Kolmogorov
va
Ronald A. Fisher
[1].
Karl Popper, vito
nhung
nam
dfiu
cua thap ky 1930, da
xem
xet
bai toan quy
tU
khia
triSt hoc. Nguyen ly phiin cua ong t6ng quat,
dua
tren khai niem v8 kha nang
sai (falsifiability)
cua
ly thuySt. Lfin
dfiu
tien ong da lien kSt kha nang t6ng quat h6a v6i
khai niem
dung lut;mg (capacity).
Cling vito
nhung
nam ddu cua thap ky 1930 nay, Andrei N. Kolmogorov xet bai toan

qua nay
la
ca
SO
chfnh
cua
S\1'
phat cua nguyen ly
thJng
ke
tJng
quat.
Cling trong
thai
ky
nay, Ronald
A.
Fisher
da
xet bai toan quy
tu
khia
thf>ng
ke
ung
d1.mg.
Do
ap
luc
cong viec luc gia

dUQ'C
goi
la
th6ng ke tham
s6
1
.
Trong luc mo hinh
th6ng ke
t6ng
quat phat cham, thi
mo
hinh th6ng
ke
tham
sf>
phat nhanh.
ddu
tu
thap nien 1930, chi trong vong
10
nam sau cite
tf>
chinh cua mo hinh
thf>ng
1
ngfr
dung cila n6
Ia
th6ng

thiSt
chinh cua
mo
hinh
th&ng
ke
tham
sf>
Ia
[1]:
1.
tim
mot quan
phlJ
thu(Jc
ham
tir
dfr
cac nha th6ng
ke
dinh nghla
mot
tap
cac
ham
phl,l
thuoc tham
sf>,
v&i
sf>

khi
n6i
dSn
luQ'c
dB
cua Fisher nguai
ta
hay
goi
Ia
th5ng
ke
c6
Th5ng
ke
cfl
di8n
di
giai
ba
bai
toan:
U'cYC
lu()11g
ham
m(it
dQ,
U'cYC
lw;mg
hJi quy va

giai
mot
bai
toan
qt'c
tidu
phidm
ham
dva vao du thvc
V&i
each
Ic\m
rieng
phdn
cua Fisher,
ly
thuySt
th5ng
ke
c6
di8n
da
khong
xem
xet mot
each
chi
tiSt
bai
toan Cl,lC

dt,mg
a
day
Ia
phuang
phap
t6ng binh
phUV11g
be
nhdt va phuang phap t6ng modul
be
nhdt
dtrQ'c
Gauss va Laplace
dS
xufit
trong thai
gian
dai
trong qua
khu.
Tuy
nhien
nhfrng
phan tich
vS
cac
phuang
phap
nay

sau
khi
James va Stein (1961)
xay dvng
mOt
u&c
ltrQ'ng
ky
vong cua
mot
vecta nhien
(n
;:::
3)
c6
phan
ph&i
chudn
v&i
rna
tran tuang quan dan
vi.
U'&c
ltrQ'ng
nay
cMch
va
v&i
kich
thu&c

vao
d6,
trong
cac
bai
toan thvc
tS,
khong
phai
tfit
ca
sac
gia
thiSt
cua
mo
hinh
th6ng
ke
tham
s6
duQ'c
thoa
man.
Cac
bai
toan
ngay
nay
c6

phuang
phap t6t
nhfit
(James va Stein)
[1].
Da
c6
nhfrng
c5
VUQ'tqua
chS
nay:
1.
P.
Huber (1960) phat
tiSp
can
robust
cho
phep
gia
thiSt
phan
ph5i
chudn
cua thanh
phdn
nhien;
2
Bill

phuang
sai
be
nhAt.
Vao
nhfrng
nc1m
1960
ly
cac
bill
toan
y6u
(ill-posed problems) dua
ra
mot
phuang
phap
xay
d\l'ng
cac
u&c
luQ'ng
cMch. sau y
tu&ng
nay
duQ'c
dung
cho
bill

DE
2.
J. Nedler (1970)
xuAt
mo
hinh tuySn tinh
t6ng
quat
cho
phep chon
mo
hinh t6t
nhAt;
3.
L. Breiman, P.
Huber
va
J.
Friedman
xet
ham
phi tuySn theo tham s6 va
dung
phuang
phap
ClfC
tiJu ham thi¢t hqi thlfc nghi¢m (Empirical Risk
Minimization-
ERM)
thay cho eve likelihood.

nguai
ta
xem
xet
biSu d6 cua
Fisher
va
quay
th6ng
ke
t6ng
quat.
I>a
c6
c6
trong
giai bai toan voi s6 chiSu Ion.
Truoc
nam 1970 can
chinh cho bai
toan
uoc
luQ'ng
hBi
quy chiSu Ia
phuang
phap t6ng binh
phuang
be
nhAt

luQ'ng cac he s6.
Phuong
phap nay gBm Projection Pursuit (Friedman
va
Stuetzle (1981),
Huber
(1985));
MARS (Multivariate Adaptive Regression Spline) (see
Friedman
(1991))
rAt
thu hut
va
tra
thanh
cong
Cl,l
chinh trong phan tich nhiSu chiSu.
Tra
hti
can
t6ng
quat
da
bi quen
lang
trong su6t
20
nam. Nam 1958 F. Rosenblatt,
mot

duQ'c
chAp
nhan, chinh Ia
nguyen ly ERM. Sau
d6
ly thuySt
ERM
cho bai toan nhan mdu
da
duQ'c
xay
dvng
vao cu6i nam 1960.
Nam
1963,
Novikoff
dua
ra dinh ly
SIJ
hoi
tl,l
cua thuat toan perceptron (Hoi nghi hoc
may
Vien
Khoa
hoc
diSu Moscow) c6 anh
huang
dSn nhfrng nguai tham
dv.

mot
trong nhfrng bai toan tang (bai toan
Glivenko-Cantelli) da ddn ly thuySt thdng ke tdng quat,
dva
vao
du
true cua ho cac
khong gian gia thiJt IBng nhau [1]. Theo d6, ben
chAt
lUQ'ng
cua
xAp
xi, tiSp can nay
con
quan tam dSn
SIJ
phuc
cua
cac khong gian
gia
thiSt.
Nhu
vay
viec soat cac
khong
gian
gia
thiSt Ia
mot
trong nhfrng cong

khong
soat
KhoaTHQL
3
PHAN
TiCH
HOI
QUY
BANG
SVM
d9 phuc cua khong gian
gia
c6 lien quan ly
sv
h9i
tl,l
C6
ba
khai niem d9 phuc
cua
khong gian
gia
duqc
cap (xem
[1
],
chuang
2) la d(j
h6n
d(m

eve
ham l6i v6i s6 VC nho
duqc
goi la nguyen ly qrc tiJu
hqi cdu true (Structural Rist
Minimization-
SRM)
Su phat
tl,lc
cua nguyen ly nay da
m9t
thuat toan m6i
duqc
goi la
may
vectO'
(Support Vector
Machines-
SVM) [1, 2]. Gi6ng v6i
mo
hinh perceptron,
cac thuat toan
SVM
cung
t6ng
quat h6a
tu
viec giai bai toan tach tinh.
Tu
mo hinh perceptron

khac nhau
da
chung
to
kha
nang cua thuat toan nay [8,
9,
10,
11].
biet trong
m9t
tra
gfin day
[9]
(Xindong Wu, 2007) da
SVM
trong top
10
cac thuat toan khai khoang
du
Ngay nay
luqng
du
tang gftp doi sau m6i 20 thang (Sever Hayri, 1998). Rftt
quy luat
An
chua
ben
trong kh6i
luqng

ramo
hinh, dinh
mo
hinh
cfin
phai
xu
ly
du
phuang nao
d6
nghien cuu trong kinh c6 d6ng
nhAt
v6i
dfr
·
Hai
phuang
phap chinh dung phan tich
du
duQ'c
su
dl,lng trong kinh la
phuang
phap ky thuat va
phuang
phap
ca
ban [20].
Phuang

anh
huang
l6n qua. Lam nao
lfty
mftu phu
hO'P
v&i
vAn
nghien
cuu
trong ngfr canh nay? Them vao d6, cling v6i toan
du
hoa
kinh
t6
rAt
m6i dang tac d()ng vao cac kinh Vai tro tac d()ng cua
cMng
dang
An
chua
trong
du
rna
lAy
mfiu khong chinh xac co lam sai
qua phan tich.
Thi truong chung khoan
tu
lau

ngfr
may vecta
h6
tr(Y.
4
DE TAl CAP
Cd
sd
Chuang
1:
DA
TV
AN
DE
cu
cho riing (Yunos,
Zaid,
Jamaluddin, Shamsuddin, Sallehuddin, & Alwi, 2001) phan
tich ky thuat
khong
c6
kha
nang
du
bao
chinh
xac
gia
chung
khoan.

chung
to
tinh qua trong
bai toan
du
baa
gia
chung
khoan (Yoon & Swales, 1991 ),
c6
kha
nang
giai rna tinh phi
cua
du
lieu,
mo
ta
cac
dl,ic
trung
cua thi
truang
chung
khoan (Lapedes & Farber,
1987),
du
baa
chi s6 thi
truang

ky thuat
mai
trong
viec
xu
ly dfr ngay cang
Ian.
phuang
phap
va
ky
thuat khai
pha
dfr phat tri
thuc
da
dang
vase
COn
dUQ'C
dua
ra
da
chtrng
to
tinh
qua
CUa
chung
trong

vai
tang
toan
h<;>c
vfrng Ngoai
ra
cac
mo
hinh
SVM
da
duqc
chung
to
tinh
nang
qua
cua
n6
so
vai
mo
hinh ncrron
nhan
va
mo
hinh th6ng
ke
khac [21].
Chung

duqc
ph1,1c
thong
qua
h<;>c
cac tap dfr
miu.
c6
tra
lai
cac cau hoi tren
mot
each
thea
dang
chung
ta
cAn
quay
trcr
ly
va
lam
cac
nghien
cuu
mang
tinh
CO'
ban

dl,it
ra cho mot
mo
hinh
SVM
Cl,l
Ia:
1.
Mo
hinh nay
c6
vfrng khong? _
2.
Lam
thB
nao
soat
duqc
cac
khong
gian
gia
If>ng
nhau?
3.
Do
phuc
cua
thuat
toan hufin

Cac
mo
hinh
SVM
CO'
ban
2.
Giai
thieu
thuat
toan hufin
nhanh
3.
Xay
dung
mot
cai
dl,it
thl'r
Thong
qua
tai
chung
toi mu6n
giai
mot
m6
hinh
cho
bai toan

hinh
hf>i
quy tinh
thea
can
th6ng
ke
tham
sf>
[20].
Cac
mo
hinh
SVM
ca
ban
duqc
trinh
bay
tu
cac tai [1, 2, 21, 22, 23, 24].
Thuat
toan hufin nhanh
la
thuat
toan SMO [25, 26, 27, 28]
duqc
ch<;>n
trinh
bay

DE
TAI
cAP
co
sd
ChU'O'Dg
2:
Mo hinh SVM
Trong
ly
hoc th6ng ke, bai
tocm
hQc
c6 giam sat
duqc
hinh thanh nhu sau
[I,
2,
21]. Cho
tap
dfr
hoc
{(xi,
Yi)}
duqc
lAy
theo phan b6 xac
suAt
chua p(x, y).
Gia

tim lai giai trong mot lop ham (
duqc
goi
Ia
kh6ng gian gia
each
qrc
tiJu ham hgi
thT:rc
(Empirical Risk Minimization, ERM):
(
2.2)
Gia
su
[*
Ia lai giai cua bai toan C\l'C ham (2.1) va
/Ia
lai giai cua bai
toan
C\l'C ham thvc (2.2). Goi L
Ia
gia tri cua ham ung
v6i
[*
vaLE
Ia
gia tri cua ham thvc ung v6i
/.
Ta
c6

phuc
cua khong gian gia
C6 mot s6 khai do do phuc cua mot ho cac ham [1]. Trong tai nay chung toi
chon gi6i khai s6 chidu
VC
6
(VC dimension) (1, 2]. Chung toi se dinh nghla
chi khai nay trong qua trinh mo hinh h6a.
Trong
vi
cua
tai chung toi khong di
;vao
nghien
cuu
cac danh gia S\l'
khcic
gifraL (2.3) vaLE (2.4) rna tap trung vao qua trinh mo hinh h6a
va
thuat toan
hufin
Tuy nhien
tru6c
khi di vao chi chung toi cling mu6n
gi&i
mot dinh ly cho thfiy .
vai
tro cua s6 chidu
vc
trong dua ra cac danh gia.

VIa
s6
VC
cita kh6ng gian gia
H,
m
Ia
kich thu&c cita
tcjp
du
V&i
xac sudt
1-
1'f,
IJi
kj;
vr;mg
be
nhdt L va IJi
thTJc
be
nhdt
LE
thoa
rang bu9c
v(
1
+log
c;)
)-log(%)

s6
chiBu
vc cua cac khong gian gia
con
phiii
huu
Bai toan v6i s6
chiBu
l6n
Ia
bai toan phuc (R.Bellman 1960). Mo hinh SVM duqc xay
dvng dva tren
nguyen ly SRM, c6 kha nang kiSm soat do phuc cua khong gian gia
cho phep giai bai
to{m
v6i s6 l6n. phat
tu
bai toan tach tinh c6
t6ng quat duqc (mo hinh perceptron cua
F.
Rosenblatt, 1950), mo hinh SVM duqc xay
dvng va
dAn
tra thanh mot trong nhung phucmg phap qua ghii bai toan uoc luqng
ham
tu
du thvc Dva tren
mo
hinh perceptron, mo hinh SVM di tim mot sieu
tach t6i uu theo nghia cvc

ta
dfJi
tuqng.
Chung toi thua nhan
dfJi
tUQ'ng
duqc
mo
ta hoi mot vee
tO'
n cac s6 va tap trung vao
cac
mo hinh toan hoc. Cac mo hinh toan hoc duqc gi6i trong chuang bao g6m:
mo
hinh tach tinh, mo hinh chiu
I6i,
mo
hinh tach phi va mo hinh h6i quy.
8
DE
TAl
CAP
CO
sd
Chuang
2:
MO
HiNH
SVM
Bai

t6i
uu.
trvc
giac, sieu nay xac dinh do rong lon
nhAt
cua
duang
bien
duqc
xac
dinh
bai
sieu
Hinh sau minh
hoa
cac khai quan trong cua
SVM
bao
gam
sieu
ph&ng
tdi
uu,
w!cta
tl:fa va
M.
Theo d6 sieu t6i uu la sieu tach
c6
lon
nhAt

duy nhdt.
Cho
tapJifr
{(xi,
Yi)
}i = I m, trong d6
Yi
E ( -1,
1}.
Xet sieu tuy
y,
w\: + b = 0,
wrxi
+ b
d+
=min
lwl
Yt=1
wrxi
+ b
d_ =
max
: :
Yi=-1
lwl
d =
d+-
d_
Sieu nay la lai giai cua bai toan tach tuySn tinh nSu d >
0.

wrx+
b
dlwl/2
=
0
9
PHAN
TICH
HOI
QUY
BANG
SVM
Ia phuang trinh diSn cua sieu
han
nua
wTxi + b
1 =
Yt=l
dlwl/2
wTxi + b
-1
-
max
fiiil
-
Yt=-1
dlwl/2
' '
Phurmg trinh thoa
rimg

mo
hinh toan hoc cua SVM cho bai toan tach tinh
Ia
bai
toan
quy ho(lch toan
phuang
sau (con duqc goi
Ia
bai toan gBc):
1
-wrw
2
(
wT
xi + b
)Yi
;:::
1
(
2.9)
trong d6
{(xi,yi)}i=l,m
Ia
dfr
lieu cua m
dBi
tuc,mg,
Yi
E {0,1} xac dinh lap cua d6i tuqng

bai toan
dBi
ngfiu cua bai toan g6c (2.1
O)
la
1
-aTDa
2
trong d6
10
( 2.10 )
(
2.11)
DE
TAl
CAP
CO
sd
Chuang
2:
MO
HiNH
SVM
Tu
ly
d6i ta c6 cite rang buoc d6i (xem
ph1,1ll,lc
3):
1
Yi(wTxi

M4
Ms
XJ
1
3
4
1
3
x2
y
1 1
2
1
4 1
5
-1
6
-1
Ta c6 m = 5, n = 2. Bai toan quy toan phuong luc nay:
1
2 2
2
(w
1
+ w
2
)
w1
+w2
+b

;

··:
:·

::·
. . . .
·:·
. .

·.··

·:··.·.··®··.=··
·=··
Giai phuong trinh ung vai cac vecto
tl,l'a
dUQ'C
WI=
0.4, Wz =
-0.8
Va
b = 2.6.
KhoaTHQL
+b
-b
-b
1
1
1
1

0.
Cac
rang
bu<)c
thu
2
va
3 cho
ta
l
4a
3
-a4
-3a
5
4a
3
-Sa4
-6a
5
a
3
-a4
-a
5
c6
a3
=as=
0.4,
l4

xung
d<)t
nhau:
vua
bao dam
d<)
r<)ng
cua bien Ian nhfit,
vua
bao dam
lfli
phan tach nho nhfit.
• • •
j !
I • I
L

,,,_,_,,,,,,,,,,, ,./t w ,_,,,,.,,,_,_,,,J
Tru6c
chung ta
din
dinh nghia s6
chidu
VC
cho bai toan tach.
Giil
sir

ham
thu9c
F
Gia
sir cac vectcr
du
duqc
Ifiy
trong
JR{n.
Xet ho ham diSn cac sieu
la ho ham ph\l
thu<)c
tharn s6 a E
JR{n,
F = {
Ia
: x E
JR{n
a'
1
'x
+ b}. Ta c6 s6
chidu
VC
cua F
b&ng
n +
1.
Nhu

cua cac kh6ng gian ghi vai
dfr
duqc
ldy
trong mot bi cua
Jru.n.
Cho
tcjp
dft
li?u
v&i
thimh phdn x c6
d(J
l6n bi
chcjn
tren
b&i
giit
tr;
D va kh6ng
gian
gia
thih
g6m cac sieu
phimg
chinh tlic
v&i
w c6
d(J
l6n bt

s6 VC bi chan.
Yi(wTxi
+b)<
1
Chung
ta
c6
m6
hinh toan hoc cua
m6
hinh chiu I6i
Ia
bai toan quy toan phuong
sau
(duqc
du&i
rna
tran):
1
-WTW +
CeTz
2
fYT
XT
W +
by
e - z
t
(
2.12)

2 2
Z(w1 + w
2
)
+ C(z
1
+ z
2
+ z
3
+ z
4
+ z
5
) +
min
w
1
+ w
2
+ b 1 - z
1
3w
1
+2w
2
+b
1-
z
2

f
yra
= 0
to:::;;
a:::;;
c
Khoa
THQL
(
2.13)
13
PHAN TiCH HOI QUY BANG SVM
trong
d6
D =
yr
xr
XY
vi
d\l
tren, tinh:
Suy
ra
D=
XY
=
(1
1
3 4
-1

ngfiu
Ia:
af
+
Sa
1
a
2
+
8a
1
a
3
-
6a
1
a
4
-
9a
1
a
5
+
20a
2
a
3
-
13a

a
3
-
a
4
-
a
5
+
min
{
a1
+
az
+
a3
- «s = 0
0
::::;;
ai
::::;;
C,
(t
- 1 5)
Ctic
rang
buoc d6i
ngfiu
bao
g6m:

vcri
thanh
phAn
CXj
ducrng
va
be
han c
Ia
vectO'
tva.
Vi
d\l
sau
cho
thAy
vai
tro cua
C.
14
Vfin
dfr
lieu
duQ'c
cho trong
vi
du
1.
-
Vcri

Ham muc tieu gia
tri
nho
nhAt
0.4.
DE
TAl
CAP
Cd
sd
Chuang
2:
MO HINH SVM
V&i
c = 0.2. phucrng
an:
wT
= (0.25,
-0.5),
b = 1.25,
zT
=
(0,
0,
0.75, 0, 0)
CUa
bai toan
g{)c
va
aT=

v&i
thvc
Trong bai toan tach tinh, lai giai (sieu tach) c6 thuang khong duy nhat.
can may vecta
t11cl
(Support Vector
Machines-
SVM) dua ra mot tieu
chuAn
t5i uu
cho phep chi ra lai giai t5t nhat trong s5 cac lai giai kha di. biet can.nay xac dinh
sieu
tach qua cac vecta
t11a
(Support Vector) thay
vi
mot phucrng trinh
tuang
minh.
V&i
cac vectcr
tva
chung ta c6 phep thay d6i khong gian bai toan rna khong
cAn
tuang minh phep d6i. can nay cho phep xay dvng cac mo hinh tach phi
mot each deo va hieu qua.
Hinh sau minh hoa truang
hQ'p
tach phi trong d6 thay cho duong tach
Ia

hinh
va
mfru)
khOng
pMi
Ia
hien tuqng
t6t.
Viec
qua khop voi
mfru
c6
tl
- ,
h;;'
T ,. '
1'
ct'
I - '
eu
m
IvU
eng
Iv
ung ngu vecta o
trc;r.
rong tat
Ivu
nay
c mng


·.
+
'\t,(i):
·.
b ) ,
.•
r\·:t
. : ·
r
+ttl)
'·
·
. . lj!{(i}

'
•·
. . .LCI
·:
•n:
. .
"·x,
L. : ;

;
)
Bang
dfr
m6i Ia tach
duQ'c
trong khong gian m6i.
X
(x-
5)
2
y
1
16
1
2
9
1
4
1
-1
5
0
-1
6
1
-1
8
9 1
9
16

'"(·"·"·"·"·"·"-'"·"·"·""·"·"·"·"·"·"·"·"·"·"·""·"""·"·"-""·""""·"·"·"·"·"·"·"""-'"·"·"·"·"·"·"·"·"·"·""·"·"·"-""·"·"·""·"·"·"·"-'"·"·"·""·"""·""·"·"·"·""·"""·""·"·"·"·"·"·"·""·""""""·"·"·'"-"·"·"·"·"·"·"·"·"""·"·"·"""·"·""·""·"·"·"·"·"·"·"·"·"
6

!

.
4

1

, .
1
0

;

.,

,

,,

®·····

·······:········-························;·························
0
2:

chung ta khong
phai
ban
dim
d8n
di8u
nay
vi
l<Yi
giai
cua
bai
toim
tuong
duang
v&i
viec xac dinh
cac
vee
ta tua. That
vay:
m
x wTx + b
=I
aiyi(xi,x) + b
=I
aiyi(xi,x) + b
i=l
a
1

Bai toan
d6i
ng[u cling khong khac
gi
so
v&i
tach tuy8n tinh
1
-aTDa-
min
2
{
yTa
= 0
o:s;;a:s;;c
( 2.14)
trir
viec thay
th8
cac thanh
phAn
cua
rna
tran
d6i
xung
XT
X,
cac
phAn

Trong nhi8u trucrng
hQ'p
nola
ham cua tich vo huang
kii
=
kernel((xi,xi))
Nghien
Cll'U
vi cac ham kernel
VUQ't
khoi
phl;lm
vi
cua
d8
tai. Trong
d8
tai nay chung toi
gioi
mot s6 ham kernel thong dvng [2]
Bang
cac lo\li
ham
kernel
thong
dvng
Logi
Bteu
thuc

din
quay v8 khong gian ban
dAu.
V
Oi
X, ta dinh X
thUOC
lop naa d\Ia vaa qua:
x
wr
cl>(x)
+ b
=I
yjaj
( ci>(xj) f
cl>(x)
+ b
a
1
>o
=I
yjajk(xi,x)
+ b
aJ>O

.
v8
ban
chfit
SVM la

phuang phap cai nguyen ly SRM voi
cfiu
true cac khong gian ham I6ng nhau c6
s6
chi8u VC
hfru
[1]. Trong d6 tham s6 C cua mo hinh dung saat s6 chi8u VC
cua
cac khong gian gia con nay.
xac dinh gia tri t6t nhfit cpa tham s6 C chung ta phai
di
giai mot bai taan t6i
uu
[1].
Day la mot chu
d8
khac cua SVM ngoai vi
d8
tai cho nen chung toi chi
d8
cap
nhu la mot dam bao cho ung dvng cac mo hinh SVM
vaa
cac bai toan thvc
18
DE
TAl
CAP
CO
sd

1
3
2 3
3
3
4 5
4
6
7
6
Phuang
trinh h6i quy la:
'
.

:
:J.
,j

·0
.\

,

1
• • • • ••.••• •
,
• •• •.•••
each nhan doi m6i va
dfiy

._.,.,, ,
§.
.

?.

s
19
PHAN TiCH HOI QUY BANG SVM
Tu
true giac tren chung
ta
di
xay dvng mo hinh toan hoc.
thAy
mo
hinh toan hoc duqc
Hip
nhu nao, chung ta xet chu6i d6i hinh thuc sau.
Bai toan SVM cho vee
to
du
mai x va phap
m6'i

hai
mai
chi a cho hai
lap
Ia (xi,
Yi
- 1 -
c)
thuoc
lap
c6 nhan 1
va
(xi,yi + 1 +c) thuoc
lap
c6 nhan -1,
ta
c6 bai toan:
1
-WTW + CeTz
2
{
xr
w - y +
be
;:::
-£e
-
z+
-xrw+y-be
;:::-Ee-z-

vai
bai toan. Tuy nhien chung ta
rAt
d.n
djnh
l1;1i
mo
hinh nay. Chung ta phai bao dam
lcri
giai cua mo hinh Ia mot
uac
luQ'ng
vfrng cho bai toan h6i quy. Vai can SVM chung ta se phai cap s6
VC.
Mo
hinh SVM giai bai toan tach
su
d1,mg
cac sieu
ph!ng
theo each sau:
"'
{-1,
y=
1,
wrx+b<O
wTx+b;:::O
Khi
Ay
tAt