I H C QU C GIA TP. HCM
I H C BÁCH KHOA
--------------------------

HU NH MINH HUY

PHÂN GI I NH P NH NG TH C TH
B
C MÁY

Chuyên ngành: Khoa H c Máy Tính
Mã s : 60.48.01

LU

TP. H

CHÍ MINH, tháng 11


Cơng tr

c hồn thành t i:

i H c Bách Khoa

-HCM

Cán b
ng d n khoa h c: GS.TS. Cao Hoàng Tr ......................................................
(Ghi rõ h , tên, h c hàm, h c v và ch ký)

Cán b ch m nh n xét 1: ...................................................................................................
(Ghi rõ h , tên, h c hàm, h c v và ch ký)
Cán b ch m nh n xét 2: ...................................................................................................
(Ghi rõ h , tên, h c hàm, h c v và ch ký)

Lu

c b o v t

Thành ph n H

i H

m:

1. GS.TS. Cao Hoàng Tr
2. GS.TS Phan Th
3. PGS.TS Qu
4. TS. H B o Qu c
5. TS. Nguy n H a Phùng
Xác nh n c a Ch t ch H
khi lu
c s a ch a (n u có).
CH T CH H

NG

ng Khoa qu n lý chuyên ngành sau



I H C QU C GIA TP.HCM
I H C BÁCH KHOA

C NG HÒA XÃ H I CH
c l p -T do -H nh phúc

T NAM

NHI M V LU
H và tên h c viên: HU NH MINH HUY ........................... MSHV: 11070453.................
01/01/1988 .......................................

NG .....

Chuyên ngành: KHOA H C MÁY TÍNH ............................ Mã s : 604801 ......................

I.
TÀI: PHÂN GI I NH P NH NG TH C TH B NG
H C MÁY

...................

NHI M V VÀ N I DUNG: ................................................................................................
..................................................................................................................................................
..................................................................................................................................................
II. NGÀY GIAO NHI M V : 20/08/2012
III. NGÀY HOÀN THÀNH NHI M V : 22/11
IV. CÁN B

CÁN B


NG D N: GS.TS. CAO HOÀNG TR

NG D N

(H tên và ch ký)

GS.TS. CAO HOÀNG TR

(H tên và ch ký)


L IC
c h t, tôi xin g i l i c
n th
ng d n c a
tơi, GS.TS. Cao Hồng Tr . Trong su t quá trình làm lu
này, th
n tình,
kiên nh n ch d n tơi t
ng xun khích l tôi. S
ng d n và l i
khuyên quý báu t th y là m t nhân t không th thi
tôi có th hồn thành
c lu
này.
il ic
ki n
th


u
ng d n lu

n TS. Nguy n Thanh Hiên, ng
ng nghiên c
a tôi GS.TS Cao Hồng Tr .

Tơi xin g i l i c
i luôn ng h , c
u ki n t t nh t cho vi c h c t p và nghiên c u c a tôi.
Xin chân thành bi
t
ih
thu t Máy tính.

u
c

và t o

t n tình gi ng d
c a t t c quý th y cô
c bi t là các th y cô trong khoa Khoa h c và K


TÓM T T
Trong m
ng t n t i nh ng c m t (nhãn tham chi u) b nh p
nh ng. Tùy thu c vào ng c nh c
n mà c m t

mang các
khác nhau. Vi
nh chính xác
cho các c m t
b
c g i là phân gi i nh p nh ng.
M c tiêu c a lu
n
n vi c phân gi i nh p nh ng và ánh x các
c m t xu t hi
n vào các th c th
ng trong Wikipedia. D a
n n c a Milne và Witten (2008), chúng tôi c i ti n
c a h b ng vi c tích h p m t s các k thu t
ng tham chi u, heuristic, l p
c i thi n d n và s d ng t g c. K t qu nh
c
i kh quan, hi u su t
i rõ khi so sánh v
n n c a Milne và Witten
(2008)
c cho là tân th i c a Ratinov và các c ng s (2011).

ABSTRACT
In a document, there may contain several terms (mentions) whose meanings are
ambiguous. That is, depending on the context, the meaning of the same term may
vary between different documents. The task of identifying correct meaning of a
term is called disambiguation.
The goal of this thesis is to disambiguate and link terms to their correct referent
entities in Wikipedia. Based upon Milne and Witten's work (2008), we enhancing it

by integrating with various techniques; in particular, the coreference relations,
heuristics, incremental and stemming. The results of our experiments show that our
method achieves better performance than the baseline method, which is Milne and
Witten's method (2008), and Ratinov et al's method (2011), which is considered the
state-of-the-art one.


L IC

tôi th c hi
c p m

ng, ngo i tr các k t qu tham kh o t các công trình khác
i dung trình bày trong lu
n n i dung nào c a lu
cn
l y b ng
ng khác.
TP.HCM,

Hu nh Minh Huy


M CL C
M C L C ................................................................................................................... i
DANH M C HÌNH .................................................................................................. iii
DANH M C B NG ................................................................................................. iv
NG QUAN ........................................................................................1
Gi i thi u..........................................................................................................1
Bài toán và ph m vi .........................................................................................3

Các cơng trình liên quan ..................................................................................4
C

LÝ THUY T ............................................................................7
Wikipedia .........................................................................................................7
Th c th và nhãn tham chi u .........................................................................11
H c máy .........................................................................................................13
Nh n d ng nhãn tham chi u ...........................................................................17
Phân gi

ng tham chi u .............................................................................18

Gom c m th c th n

tri th c ..................................................20

n ..........................................................................................22
XU T ...............................................................24
n ............................................................................................24
i ti n ......................................................................................28
.............................................................35
T p hu n luy n ...............................................................................................35
T

...................................................................................................36
....................................................................................37

K t qu thí nghi m .........................................................................................42
NG K T..........................................................................................47
..................................................................................................47


i


ng phát tri n ............................................................................................47
TÀI LI U THAM KH O.........................................................................................49

ii


DANH M C HÌNH
Hình 1.1: Trích t [21] cho th y c m t
c chú thích thêm thơng tin t
Wikipedia. ...................................................................................................................2
Hình 1.2: M t mơ hình phân gi i nh p nh ng th c th có tên [23]. ...........................5
Hình 2.1: M t trang th c th trong Wikipedia............................................................9
Hình 2.2: Các trang chuy
ng. ..........................................................................10
Hình 2.3: Trang phân gi i nh p nh ng ......................................................................11
Hình 2.4: Minh h a cho h th ng phân lo i c a Wikipedia .....................................12
Hình 2.5: M t ví d v gi i thu t C4.5 .....................................................................16
Hình 2.6: M t ví d v các chu
ng tham chi u. .................................................19
Hình 2.7: M t ví d v gom c m th c th n
tri th c. .......................21
Hình 3.1: Mơ hình t ng qt v MACH. ..................................................................25
Hình 3.2: M t ví d v truy h i ng viên v i nhãn tham chi
i di n ..................29
Hình 3.3: M t ví d v heuristic l c ng viên ..........................................................30


iii


DANH M C B NG
B ng 3.1: K t qu phân gi i c a các gi i thu t h c máy theo Milne. .......................25
B ng 4.1: Các t
thông ......................................................................36
B ng 4.2: Các t
AC .......................................................................36
B ng 4.3: K t qu MAA c
thông. .....43
B ng 4.4: K t qu F BOT c
n các t
thông. ......43
B ng 4.5: K t qu MAA c a các mơ hình trên t p
TAC 2011 và 2012. ....45
B ng 4.6: Hi u su t c a MACH trên t
................................45
B ng 4.7: So sánh k t qu F B-Cubed+ c a MACH và m t s
d
u
trên TAC 2012...........................................................................................................46
B ng 4.8: S
d ng trong phân gi i nh p nh ng. ........................46

iv


T NG QUAN


Gi i thi u
t vai trò quan tr ng trong vi
xu t b n tài li
ng g i t

và truy n t i
thông tin c a nhân lo
i d ng s và
ph bi
n ra
m nh m
o nên s bùng n
i có th d dàng
ti p c
c ngu n thông tin ch
ng nhi u tri th
a
m t kho tàng tri th c kh ng l
y, có nhi u kh
is b l cl i
c thông tin c n thi t n u khơng có s tr giúp c a cơng c h u
hi u có th t
ng c hi u và trích rút các thơng tin quan tr ng t các tài li u
trên Web.
Tuy v y, các trang web ph n l n là phi ho c bán c u trúc, chi m 80% kh i
trên Web; trong khi, n i dung c
c di
t b ng
ngôn ng t nhiên ch phù h
c hi u [25]

máy tính có th
i trong vi c tìm ki m thơng tin thì nó ph i hi
c n i dung
c
y nhi u k thu t và ng d
lý
ngôn ng t nhiên (Nature Language Processing) giúp cho máy tính ph n nào hi u
c ngơn ng
i.

chu

ng ti p c n nh m hi u m
ng
a
i phân tích ngơn t
cs d
iv im
c cho là khá t do và h
u này là không kh thi. M
ng ti
t bu c máy ph i hi u rõ n i dung c
1

m

n trên
n ph i th t
n trong truy n t i
p c n khác h p lý

i d ng ngôn ng


c
i thì ta ch c n yêu c u chúng n m b
c các n i dung chính quan
tr
hi n. Các n i dung này là các ch
nói v các khái ni m
hay v th c th
c th hi
i d ng các c m t (nhãn tham chi u) xu t hi n
n và các m i quan h gi
c các thông này s giúp
b sung thêm thông tin chú thích cho n i dung các trang web d
tri
th
Ví d trong m
n có ch a câu: "The Chicago Bulls announced
yesterda
", ta có th
nh các th c th trong câu
g m "Chicago Bulls" là m
i bóng r chuyên nghi p và "Michael Jordan" là m t
c u th bóng r . Bi t
c th c th
s
c câu tr l i phù h
i dùng. Ví d
câu trên, "Michael Jordan" có th là m t v

ng viên bóng r ho c là m t chính
tr
i Ai-len, gi s
i dùng mu n tìm ki m thơng tin v "c u th bóng
r Michael Jordan" thì vi c hi
n có ch a th c th v c u th bóng r
Michael Jordan s giúp máy tính tr v
c k t qu phù h
c
máy t
nh các th c th và liên k t nó v i các bài vi t trong ngu n tri
1
th
s giúp cho vi
c hi u n i dung bài vi
nh
c chú thích d a trên Wikipedia.

Hình 1.1: Trích t [21] cho th y c m t
Wikipedia.

1



2

c chú thích thêm thơng tin t



Bài toán và ph m vi
iv im
c m t nhãn tham chi u
n
nói v th c th nào trong th gi i th
ch tb
i có m t
ngu n tri th
Và d a vào n i dung ng c nh c
n mà
nhãn tham chi u
c pm
c
n th c th nào
trong ngu n tri th
iv
có th "bi
c m t nhãn
tham chi u
n nói v th c th
n có m t ngu n tri th c có
s n. Ngu n tri th
máy có th s d ng có th là các
cm
KIMO, YAGO, Wikipedia...
Tuy nhiên, vi
nh chính xác th c th cho nhãn tham chi u làm phát sinh
v
v nh p nh ng th c th , t c m t nhãn tham chi u có th ám ch các th c th
khác nhau tùy vào ng c nh c

n ch a
Jordan" có th là v
ng viên bóng r
c
là m t chính tr
i Ai-len tên Michael Jordan, hay t "Tiger" có th
v con h ho c là h
u hành Mac OS X Tiger c a hãng Apple.
V
nh chính xác th c th (trong m t ngu n tri th
c) mà
m t nhãn tham chi u
n
phân gi i nh p
nh ng th c th t ng quát (Entity Disambiguation hay Entity Linking) v i m c tiêu
nh và ánh x các nhãn tham chi u xu t hi n trong m
th c th t n t i trong m t ngu n tri th c có s n. Nói t ng quát, khi phân gi i nh p
nh ng th c th cho m t nhãn tham chi u thì s
ng h p chính x y ra:
-

Th c th

n th c s t n t
tri th c và nhi m v
c
nhãn tham chi u
th c th này.
Th c th
n không t n t

tri th c và nhãn tham chi u
c
c ánh x vào NIL, m t th c th
t th c th
nói n khơng t n t
tri th c.

Vi
c các th c th này không ch s giúp b sung, làm giàu thêm
thông tin cho các trang web t các ngu n tri th c mà cịn h tr cho vi c tìm ki m,
khai thác thơng tin nh vào vi c phân tích các thông tin b sung t các ngu n tri
th c có s n.
Nh
v

Text Analysis Conference (TAC) t ch c nhi u cu c thi
c x lý ngôn ng t
cu c thi chuyên bi t v bài toán

3


phân gi i nh p nh ng th c th (TAC Entity Linking) v i m t s yêu c u nâng cao.
Ngoài vi c ánh x c m t vào th c th t n t
tri th c, bài tốn cịn u
c u gom c m các nhãn tham chi u cùng nói v m t th c th n
tri
th c; yêu c u này
là m t bài toán con và
c g i là gom c m th c

th n
tri th c (NIL Clustering). Cu c thi này ngày càng thu hút s
quan tâm trên toàn th gi i và có nhi u nghiên c
c th c hi n cho riêng bài
toán phân gi i nh p nh ng th c th
i TAC.
Trong lu
p trung vào vi c gi i quy t bài toán phân gi i
nh p nh ng th c th t ng quát và th s c v i bài toán phân gi i nh p nh ng th c
th
a TAC.

Các cơng trình liên quan
Phân gi i nh p nh ng th c th là m
ng h p t
a bài toán
"phân gi i nh p nh ng th c th có tên" (Named Entity Disambiguation). Bài toán
phân gi i nh p nh ng th c th có tên
t bài tốn tr
m và có
nhi u nghiên c
[24] [4] [2]
i ta nh n th y r ng,
không ph i ch các th c th có tên (Named Entity)
ng trong
bi u di n n i dung c
n, mà các khái ni m chung (Abstract Concept).
v
bài toán phân gi i nh p nh ng th c th có tên
c m r ng lên thành

bài toán phân gi i nh p nh ng th c th . Trong khi bài toán phân gi i nh p nh ng
th c th có tên ch chú tr
n vi c phân gi i các th c th có tên riêng (con
i, t ch c,
n...) thì bài tốn phân gi i nh p nh ng th c th l i phân gi i
c nh ng th c th là các khái ni m chung
Có nhi u cơng trình nghiên c
n phân gi i nh p nh ng th c th
[25] [15] [19] [30] [21]. Các
gi i nh p nh ng th c th có tên u g
c chính là ti n x lý và phân
gi i nh p nh ng. Hình 1.2 cho th y m t ví d tiêu bi u v m t h th ng phân gi i
nh p nh ng th c th có tên.
p c n cho bài tốn phân gi i nh p nh ng th c
th có th chia thành ba lo i là: c c b (local), toàn c c (global) ho c t p th
cb
u cho r ng các nhãn tham chi u
cl p
v i nhau và phân gi i d
c nh c c b c a nhãn tham chi u và
các
c và t p th thì cho r ng các th c th t n t i

4


trong m
n có liên h ng
Semantic Relatedness) v i nhau nên vi c
nh th c th cho các nhãn tham chi u

c l p mà ph thu c l n nhau.
c phân gi i l
t t ng nhãn tham chi u thì
p th l i phân gi i các nhãn tham chi u m
ng th i.

Hình 1.2: M t mơ hình phân gi i nh p nh ng th c th có tên [23].
Bunescu và Pasca [2]
xu
i nh p nh ng th c th d a
trên Wikipedia. Các tác gi tri n khai m t mơ hình h
h
ng
c nh xung quanh m t nhãn tham chi u và ng c nh c a
nm i
a các t v i các th lo i (category) trong wikipedia. Ng c nh c a
m t tham chi u mà [2] s d ng là 55 t xung quanh, còn ng c nh c a ng viên là
tồn b t trong bài vi t mơ t v ng viên trong Wikipedia. Mihalcea and Csomai
[19]
hai gi i thu t riêng bi t. M t gi i thu t d a trên m
ch ng l p
ng
i thu t cịn l i tri n khai mơ hình h c phân lo
phân
gi i nh p nh ng. Drezed và CS2 [8]
c phân h ng thay vì s d ng
mơ hình phân l p. Zhang và CS [36] thì s d ng Labelled Latent Dirichlet
Allocation (LDA) k t h p v i các th lo i trong Wi
khai thác ng c nh
n và so sánh v i ng viên.


2

C m t nh ng c ng s

c chúng tôi vi t t t thành CS.

5


Cucerzan [4]
u tiên khai thác s liên k t gi a các th c th
b n. Trong [4] tác gi mơ hình hóa m i liên k t gi a các th c th b ng s trùng l p
các th lo i trong Wikipedia gi a các th c th . Nguy n [23] thì s d ng các
ng kê v i ng c
c l p c i thi n d n
(incremental); nói các khác, tác gi s d ng th c th c a các nhãn tham chi u
c phân gi i
ti p t c phân gi i cho các nhãn tham chi u v n còn nh p nh ng.
Milne và Witten [21]
c phân h ng ng viên d a trên ba nhân
t
ph bi n (C
c nh (Semantic Relatedness) và
ch
ng c a ng c nh (Context Quality). Ng c nh trong [21] s d ng là các
nhãn tham chi u
c cho là không b nh p nh ng; nói cách khác là nh ng nhãn
tham chi u ch có duy nh t m t th c th ng viên. Ratinov và CS [30] thì k t h p
c hai cách ti p c n c c b và tồn c c vào trong mơ hình h c phân h ng SVM

ch n ra ng viên t t nh t. Tác gi còn nh
nh r ng thách th c l n
cịn l
nh khi nào thì m t tham chi u s nói v m t th c th không t n t i
trong ngu n tri th c.
Kulkarni và CS [15]
ng ti p c n t p th . Trong
[15], tác gi phân gi i các ng c viên m
ng th i và mơ ph ng bài tốn
thành bài toán t
ng xu t hi n gi a các tham chi u và các th c th mà
nó ánh x
n. Tác gi s d ng thu
i và quy ho
gi i
quy t bài toán t
Ti p n
ng ti p c n t p th , Han và CS [12]
ng c i thi n ng c nh t
c b ng cách s d ng các d u hi
(evidence) xu t hi n xung quanh nhãn tham chi u.

6


LÝ THUY T

Wikipedia
Wikipedia là m t ngu
ng chính th c vào ngày

kho tri th c m
dùng trên th gi i

n tri th c m to l n c a
c
vào ho t
15/1/2001 b i Jimmy Wales và Larry Sanger. Hi n t i,
thành ngu n
y cho r t nhi
i
ng truy c p x p vào trong top 10 theo Alexa3.

Có nhi u nghiên c u
Wikipedia,
v
tin
c y; h
ra r
chính xác c a Wikipedia có th sánh ngang v i các ngu n
tri th
u c a Giles [10]
tác gi so sánh
Wikipedia và t
Britannica4. Tác gi thu th p ng u nhiên
41 bài vi t v các ch
n khoa h c trên c hai t
n bách khoa, k t
qu có 162 l i trên các bài vi t c a Wikipedia so v i 123 l i c a các bài vi t l y t
Britannica. Ngồi ra, cịn có m t s nghiên c u khác c a Weaver và CS [35]
giá m

chính xác c a liên k t gi a các bài vi t trong Wikipedia
u
này có th kh
nh r ng Wikipedia có m
tin c y cao và là ngu n tri th c

Trong ph m vi lu

này, chúng tôi s d ng b n Wikipedia vào ngày 22
tri th c cho vi c phân gi i nh p nh ng. M t s chi ti t
c th v phiên b ng Wikiped
c s d ng
3
4

S trang th c th : 3,573,789 trang.
S trang phân gi i nh p nh ng: 148,818.
/> />
7


-

S trang th lo i: 739,980
S trang chuy
ng: 5,001,026.

T
tôi quan tâm.


gi i thi u b n thành ph n chính c a Wikipedia mà chúng

Trang th c th
Trang th c th là thành ph n quan tr ng nh t c a Wikipedia và ph n l
u là
do c
ng
i trang th c th là m t bài vi t bi u di n
cho m t th c th duy nh t t n t i trong Wikipedia. M i trang th c th
c xác
nh b ng m
(title) mô t v th c th
nh danh c a th c th
i v i nh ng
b nh p nh ng thì s có
n phân
gi i nh p nh ng
phía sau. Ví d
"Set" có th là "Set (mathematics)"
(t p h p trong toán h c) ho
là "Set (computer science)" (m t d ng
c u trúc d li u bi u di n cho t p h p trong khoa h c máy tính).
ra, cịn có m t s thành ph n khác
infobox, liên k t vào (ingoing link), liên k t ra (out-going link)
x là n i dung tóm t t quan tr ng v
th c th ho c ch a liên k
n các th c th có liên h m t thi
ng
c bi u di
i d ng m t b ng (table) n m góc ph i ngồi cùng c a m t

trang th c th .
Liên k t vào là t p h p nh ng liên k t tr vào th c th hi n t
m xu t
phát t n i dung các trang th c th khác. Ví d : trang th c th "United States" có
m t s liên k
n trang này d
"The State", "United States", "U.S"...
c l i, liên k t ra là liên k t xu t phát t n i dung c a trang th c th hi n t i
n nh ng th c th khác.
Trang chuy

ng

n m t th c th
t tên g i chính
th
u tên g i ho c bí danh khác nhau cho cùng m t th c th .
ng lu t này cho các th c th . N u tên g i chính th c cho m t
th c th
(c a trang th c th ) thì các bí danh và các tên g i khác c a th c
th
c bi u hi
i d ng các trang chuy
ng. M i trang chuy
ng
bi u di n cho m t tên ho c m t bí danh c a th c th và ch a m t tham chi
n
trang th c th .

8



Hình 2.1: M t trang th c th trong Wikipedia
9


Ví d trong Hình 2.2, trang th c th "Vietnam" có các trang chuy
ng là
"C ng Hịa Xã H i Ch
t Nam", "Vi t Nam" M
m thú v là theo
th i gian, tên g i chính th
c a trang th c th ) có th b
ib i
i dùng, và nh ng tên g
a th c th s tr thành nh ng trang chuy n
ng.

Hình 2.2: Các trang chuy

ng.

Trang phân gi i nh p nh ng
Khác v i trang chuy
ng, trang phân gi i nh p nh ng là trang t p h p
nh ng liên k t c a nh ng th c th có tên g i gi ng nhau ho c g
l i mang ng
t ng c
c t o nên v i
m

tr
i tìm ki m, phân bi
nh th c th
i dùng
Tuy nhiên, không ph i t t c các th c th b nh p nh
có trang phân gi
ng.
C
t tên c a trang phân gi i nh p nh ng có d ng: tên/c m t nh p
nh ng + (disambiguation). Ví d trong Hình 2.3 là m t trang phân gi i nh p nh ng
"Cleveland (Disambiguation)" cho tên "Cleveland".
Trang th lo i
ti n cho
i dùng và các nhà nghiên c u, Wikipedia khuy
i
dùng phân lo i bài vi t c a mình theo m t cây phân c p th lo
c. C u trúc
cây r t ph c t
n, có nhi u b c, có m t s trang l i thu c cùng nhi u
nhánh con khác nhau do n i dung c a chúng mang tính liên ngành. M i trang th
lo i, thì s d
n nh ng trang th lo i con c a nó. N
u tiên

10


c a h th ng phân c p này, chúng ta s
phân lo i c a toàn b Wikipedia.


n v i tồn b các trang th c th

c

Hình 2.3: Trang phân gi i nh p nh ng
Hình 2.4 là m
v h th ng phân lo i c
c trích ra t
lu n án ti
c a Nguyên [23]. Th lo i m c cao "People and self" có các th lo i
"People by company", "People by continent". "People by continent" l i có
các th lo
"African people", "Asian people"

Th c th và nhãn tham chi u
Theo KIM, th c th (entity) là m
ng ho c m t t
ng nào
t s t n t i riêng bi t, h u hình trong th gi i th c (George W. Bush,
t n t i d ng vơ hình, tr
n, th c th t n t
i các d ng hình nh, tên riêng, danh t , c m
danh t
it
c g i là các nhãn tham chi u (mention). Nói cách khác,
nhãn tham chi
c coi là th hi n c a th c th
i nhi u d ng
ng nh
i d ng ngôn t (và trong lu

chúng tôi ch
n th hi n d ng ngôn t ). Do v y, khái ni m nhãn tham chi u
s
c s d ng thay th cho th c th khi nói v m t th hi n c a th c th
n. Nhãn tham chi u có th
c chia làm ba lo i chính:

11


-

Nhãn tham chi u là các danh t riêng. Th c th
c bi u di n b i các nhãn
tham chi
c g i là th c th có tên (Named Entity). Ví d : London,

-

Nhãn tham chi
it
bi
c th c th
c bi u di n b i
nhãn tham chi u lo i này, chúng ta ph
t nó vào ng c nh c
n
mà nó xu t hi n. Ví d : they, it, we, you, I.
Nhãn tham chi u còn l i, không thu c hai lo i trên. Th c th
c bi u di n

b i các nhãn tham chi
c g i là các khái ni m chung (Abstract
Concept). Ví d

-

Hình 2.4: Minh h a cho h th ng phân lo i c a Wikipedia
Trong lu
quan tâm phân gi i cho các nhãn tham chi u
lo i m t và ba, t c các nhãn tham chi u là các th c th có tên và khái ni m chung.
12


H c máy
H c máy (Machine Learning) là m
c c a ngành Khoa h c Máy tính, c
th
a trí tu nhân t o; nghiên c u nh ng k thu t, c th
i
thu t c n thi t, giúp máy tính có th "h c"
c nh ng kinh nghi
t
ng cho nh ng tình hu
c a cùng m t bài tốn. Nói cách khác là
xây d ng nh
t
ng h c và c i thi n hi u qu thông qua
kinh nghi
u này r t gi ng v i quá trình h c c
c n ph i h c h i qua nh ng tình hu

r i áp d ng vào m t tình hu ng
khác.
Vi c h c bao g m nh ng y u t sau:
-

Nhi m v (task): cho bi t h
làm gì.
u qu
t qu c a vi c h c.
T p kinh nghi m (experience): là nh ng bài hu n luy n cho q trình h c,
cịn g i là t p hu n luy n (training data).
T p ki m tra (testing data): d li
ki m tra vi c h c có hi u qu hay
khơng, t
c g i là t p chu n vàng (gold data).
Các
h c (learning features): nh ng
dùng cho vi c
h c. T p h p các
c a m t nhi m v
c g i là vector
c a nhi m v

Có th l y m t ví d

c máy h c cách phân bi

n t có ph

rác

-

-

Nhi m v : phân lo
u qu : t l s
nt
c nh n di
ng
s
n t nh n d
c, ngồi ra cịn có t l s
n t nh n di n
ng s
nt
có s n c a t p ki m tra.
T p kinh nghi m: ch a nh ng t p có d li
is n
khơng.
T p ki m tra: ch a nh ng t p d li
ki m tra vi c nh n di n có hi u qu
hay không.
Các
h c: s
ng nh ng t
c nghi ng là c a
"qu ng cáo", "liên h ngay"

13



ng d ng c a h c máy r
c áp d ng r
x lý
nh và th giác máy tính, x lý ngôn ng t nhiên, khai phá d li u, nh n d ng ch
vi t, gi
d ch thu t
M t ví d
n hình là Google d ch5 (Google Translate), m t công c d ch
thu t khác v i các cơng c d
ng
m nó có phân tích cú pháp c a
t
ch l i s d ng h c
d ch. C th
Google s thu th p ý các câu c n d ch b ng ti ng Anh và
nh ng câu d ch chu
ng trong ti ng Vi t; sau khi q
c h c máy
ph c t p thì s
i dùng s d ng.
Có r t nhi u gi i thu t h
xu t
Neutron, K-means, support vector machine (SVM)
phân lo i các gi i thu t h c máy thành t
-

-

-


5

cây quy
nh, m ng
ng quát ta có th

H c máy có giám sát (Supervised Learning). T p d li u hu n luy n ch a
vector mang giá tr c a
và cho bi
c c câu tr
chính xác mong mu n. Các giá tr c a t ng
c a vector có th là
giá tr liên t c (continuous) ho c r i r c (discrete) hay nhãn c
ng
u vào mà nó bi u di n. Nhi m v chính là xây d ng mơ hình h c h p lý
c a vi c t ng quát hoá d li u.
H c máy không giám sát (Unsupervised Learning). T
c
h
ng t p hu n luy n ch có vector ch a giá tr cho các
mà khơng có câu tr l i chính xác
i thu t h c
máy s c g ng gom nhóm (clustering
u vào d a vào s
c a chúng hay nói cách khác chúng t
l i.
chính xác c
c máy khơng giám sát s
th

c máy có giám sát.
H c máy bán giám sát (Semi-Supervised Learning). Trong các bài toán
th c t , vi c có k t qu chính xác mong mu n hay gán nhãn chính xác ngay
cho t p hu n luy n không ph
c h t, ch
c
m t ph
t qu c a
c máy không giá
c yêu c
pháp h
k th
mc

/>
14


-

pháp trên. Ch gán nhãn cho m t s nh tình hu
u này có ý
t l n trong th c t .
H
ng (Reinforcement Learning). Thu t toán s
tác v i tình hu ng th c t
ng s cung c p nh ng
thông tin ph n h i ngay t
vi c h c máy thích ng v
ng

th c t
t qu có th
c h c máy này có ý
tl
i v i nh ng bài toán th i gian th c (real time).

Bagging
"Bagging"
là Bootstrap Aggregating), là m t siêu gi i thu t (meta
algorithm) trong h c máy, bên c
i thu
Boosting
hay Feature Selected.
Bagging là gi i thu t t h p các k t qu khác nhau c a cùng m t gi i thu t h c
máy,
nh ng t p hu n luy n riêng l
c trích d n t t p hu n
luy
u. L y ví d
n là khi m t b
nh thì có th
n
ơng th y thu c này n u ch khám m
n thì s khơng bi
c b nh tình
c
i b nh mà ph i ph i h p nhi u t p d li u khác nhau c
chu
m, ch p X quang, h
Thì s bi

b nh tình c a b nh nhân. Siêu
gi i thu t Bagging có th
c mô t
:
-

-

Cho m t t p d li u D
c n, siêu gi i thu t Bagging s t o ra m
t p d li u D1 n Dm con
c là n' < n. Các t p d li u con này
c trích xu t t t p d li u D b ng cách ch n ng u nhiên các m u trong D
và các m u này có th trùng nhau trong cùng m t Di con (i = 1
m) . Theo
có m t s d li
c l y l i nhi u l n, trong khi có m t s d li u
khơng h
c l y. Cách l y m
c g i là bootstrap.
M
a bootstrap là t o ra các mơ hình hu n luy n con khác nhau t
t p hu n luy
u. K t qu c a mơ hình h c t p h
c t các mơ
hình con b ng cách l y trung bình k t qu
i v i bài tốn h i quy
ho
pháp b phi
ch n k t qu

iv i
phi u, m i mơ hình h c con s
cho ra m t k t qu , k t qu cu
c ch n là k t qu c
các
mơ hình h c con.

15