- 2010B.
-

trong
!

Trang 1


Trang 2


1
2
3
6
7
8
Ư

1.

11

1.1

.................................................................................................... 11

1.2

Ki n trúc c a h th ng trích rút thông tin................................................................ 15

1.2.1

Trích rút th c th - Named Entity Recognition (NER) ..................................... 16

1.2.2

Gi i quy

1.2.3

Xây d ng m u ph n t - Template Element Construction (TE)........................ 18

1.2.4

Xây d ng m u quan h .................................................................................... 19

1.2.5

u k ch b n ....................................................................................... 19

ng tham chi u ............................................................................. 17

1.3

Bài toán trích rút th c th ....................................................................................... 20

1.4

....................................................................... 23


1.4.1

Trích rút thông tin t

n .......................................................................... 23

1.4.2

..................................................................................... 23

1.4.3

H tr h th ng tr l i câu hỏi t

1.4.4

C i thi n k t qu c a h th ng tìm ki m .......................................................... 24

Ư
2.
Ư
TRÍCH RÚT THÔNG TIN

ng ............................................................ 24

25

2.1


(hand-written regular expressions) .................................... 25

2.2

idden Markov Model - HMM) ..................................... 26

2.3

Mô hình Markov c

2.4

T ng k

Ư
3.1

3. MÔ

i hóa Entropy (MEMM) .................................................... 28

.................................................................................................... 32

Ư

33

ng ng

u ki n - CRFs ................................... 33


Trang 3


3.2

............................................................................... 35

3.2.1

.................................................................................. 35

3.2.2

........................................................ 35

3.2.3

....................................................................... 36

3.3

................................................................... 38

3.4

............................................................. 39

3.5


........................................................... 41

3.6

ch nhãn................................................... 43

3.7

.................................................................................................... 44

Ư

4.

45

4.1
4.2

............................................. 45
Ứng d

t ........................................... 50

4.2.1

d ng CRF .......................................... 50

4.2.2


....................................................................................... 50

4.2.3

....................................................................................... 54

4.3

d

n: ....................... 55

4.3.1

ng: ............................................................................................... 56

4.3.2

ng câu .......................................................................................... 56

4.3.3

ng câu ............................................................ 57

4.3.4

ng câu .............................. 57

4.4


................................................................................................... 60

Ư

5.

Ư
61

5.1
5.2

t ................................................... 61
Thi t k

............................................................... 61

5.2.1

Bi

lu ng d li u các m c ........................................................................ 61

5.2.2

Bi

phân c p ch

5.2.3


Các bi

............................................................................ 63

lu ng th hi n ch

Trang 4

th ng ............................................... 64


5.2.4
5.3

Thi t k

Xây d

d li u ...................................................................................... 67
........................................................................................... 68

5.3.1

L a ch n ngôn ng và công c l p trình .......................................................... 68

5.3.2

Các l


5.4

.................................................................... 69

Thi t k giao di n và s d

5.5

............................................................ 72
............................................................................. 75

5.5.1

................................................................................... 75

5.5.2

................................................... 76

5.5.3

...................................................................................... 76

78
.......................................................................................................... 78
.......................................................................................................... 79

80

Trang 5



1-1: Ki n trúc c a h th ng trích rút thông tin ...............................................................16
1-2: Ki n trúc c a h th ng trích rút th c th ................................................................20
1-3: H th ng tìm ki m .................................................................................................24
...................................................................27
.........................................................29
2-3: V
5-1: Bi
5-2: Bi
-

sai l ch nhãn ..............................................................................................30
.................................................................................34
..........................................................................................36
n .............................................................42
ch nhãn ...................43
........................................................................................47
.........................................................................................48
...........................................................................49
...............................................................50
......................................................51
..............................................................................................52
.........................53
..............................................................................................55
lu ng d li u m c khung c nh ..................................................................62
lu ng d li u m
nh .............................................................................62
..................................................................................63
.......................................................64

.................................................................66
.....................................................67
............................................................................................................69
............................................................................................70
............................................................................................71
.....................................................................................................71

-

...................................................................................................72
........................................................................................72
............................................................................73
..................................................................74

-

..........................................................74

Trang 6


-

.....................................15

-

.......................................................17

-


............................................................................18

-

...........................................................................19

-

....................................................................................19

-

................................................................................22

-

..............................31

4-1.

..........53

-

affection, jealous and gossip) .......................................58

-

affection, jealous and gossip) ..................................59


-

...................................................................................68

-

....................................................75

-

..................................................76

-

..............................................................................................77

Trang 7


(2-1) .....................................................................................................................27
(2-2) .....................................................................................................................27
(2-3) .....................................................................................................................29
(2-4) .....................................................................................................................29
(2-5) .....................................................................................................................30
(2-6) .....................................................................................................................30
(2-7) .....................................................................................................................31
(3-1) .....................................................................................................................34
(3-2) .....................................................................................................................34
(3-3) .....................................................................................................................35

(3-4) .....................................................................................................................35
(3-5) .....................................................................................................................35
(3-6) .....................................................................................................................36
(3-7) .....................................................................................................................36
(3-8) .....................................................................................................................36
(3-9) .....................................................................................................................37
(3-10) ...................................................................................................................37
(3-11) ...................................................................................................................38
(3-12) ...................................................................................................................38
(3-13) ...................................................................................................................38
(3-14) ...................................................................................................................38
(3-15) ...................................................................................................................39
(3-16) ...................................................................................................................39
(3-17) ...................................................................................................................39
(3-18) ...................................................................................................................40
(3-19) ...................................................................................................................40
(3-20) ...................................................................................................................41
(3-21) ...................................................................................................................41
(3-22) ...................................................................................................................41
(3-23) ...................................................................................................................41
(3-24) ...................................................................................................................42
(4-1) .....................................................................................................................58
(4-2) .....................................................................................................................58
(5-1) .....................................................................................................................76
(5-2) .....................................................................................................................76
(5-3) .....................................................................................................................76

Trang 8



I
I
“

”
I f

–I )
ễ

ỹ
trong bài toán trích rút

ò
ẽ

ò

ỹ

mô
– CRF), mô hình
–

)

(Maximum Entropy Markov Model- MEMM)…
1
ẽ


Trang 9


2

3

ẽ
4

5

.

Trang 10


Ư
1.1

1.
c
c quan tr ng trong khai phá d li

h th ng

n,

c hi n vi c trích rút các thông tin t các d li u phi


c u trúc ho c bán c u trúc chuy n thành d li u có c u trúc. Nói cách khác, m t h
th

c v các th c

th và m i quan h gi a các th c th t m
n nh ng thông tin này vào m

i d ng ngôn ng t nhiên
n ghi d li u có c u trúc ho c m t d ng

m

um
)

nh các th c th
)

trích ch n thông tin t

nh quan h gi a các th c th

nh và theo dõi các s ki n và các k ch b n (Event and
)

)

n


ng tham chi u (Co-reference

c s d ng trong trích ch n thông tin g m có: phân

n, phân l p, k t h p và phân c m [1].
)
ng

For years, Microsoft CorporationCEOBill Gates
railed against the economic philosophy of opensource software with Orwellian fervor, denouncing
its communal licensing as a "cancer" that stifled
technological innovation.
Today, Microsoft claims to "love" the open-source
concept, by which software code is made public to
encourage improvement and development by
outside programmers. Gates himself says Microsoft
will gladly disclose its crown jewels--the coveted
code behind the Windows operating system--to
select customers.
"We can be open source. We love the concept of
shared source," said Bill Veghte, a MicrosoftVP.
"That's a super-important shift for us in terms of
e a ess.“
Richard Stallman, founder of the Free Software
Foundation,
e e sa
…
Trang 11

Microsoft Corporation

CEO
Bill Gates
Microsoft
Gates
Microsoft
Bill Veghte
Microsoft
VP
Richard Stallman
founder
Free Software Foundation


For years, Microsoft CorporationCEOBill Gates
railed against the economic philosophy of opensource software with Orwellian fervor, denouncing
its communal licensing as a "cancer" that stifled
technological innovation.
Today, Microsoft claims to "love" the open-source
concept, by which software code is made public to
encourage improvement and development by
outside programmers. Gates himself says Microsoft
will gladly disclose its crown jewels--the coveted
code behind the Windows operating system--to
select customers.
"We can be open source. We love the concept of
shared source," said Bill Veghte, a MicrosoftVP.
"That's a super-important shift for us in terms of
e a ess.“
Richard Stallman, founder of the Free Software
Foundation,

e e sa
…

Trang 12

Microsoft Corporation
CEO
Bill Gates
Microsoft
Gates
Microsoft
Bill Veghte
Microsoft
VP
Richard Stallman
founder
Free Software Foundation


ng d ng trích ch n thông tin trên Internet, h tr
th ng tr l i t

ng d ng web ng

ng, h th ng h tr tìm ki m chính xác.... Các ng d ng

th c t

, th i gian
…T


t
tin cò

c ng d ng vào vi

c tìm ki m và trích

ch n ra các thông tin c

a ch , email, s

n tho i r i

d li u hay tham gia vào h th ng qu n lý thông tin cá nhân. G
c bi

c chú tr

cyh

báo nghiên c u và ng d ng c

u bài
c nh n d ng các th c

th trong ngành y ví d
t thông tin [5][7][18]

công


“

Trang 13

”


)
)

-

Random Field - CRFs)

trích rútthông

tin.

s
HMM

ch nó có th gi i quy

c v

CRFs

ph thu c gi a các t . Ngoài ra,
ch có th gi


cv

sai l ch

nhãn. CRFs

ờng Nguyễn Xiể

m2. Giá

5.5 tỷ. Sổ ỏ chính chủ. Liên h : 090.324.7686 (Mai)
V ib

t trên ta ch c

a ch , di n tích,

n tho i liên h . Do v y không nh t thi t ph i hi
a bài toán trích ch n th

c các thông tin
…

a ch , di

-

n, m c


m t kh i d li u

ờng Nguyễn_Xiể

-

-

46 <B-DT> m2 <I-DT>. Giá 5.5 <B-GB> tỷ <I-GB>. Sổ ỏ chính
chủ. Liên_h : <B-LH> 090.324.7686 <I-LH> (Mai)<I-LH>

Trang 14


V

c các nhãn cho các t t

:

a
-LN là t b

LN

u lo i nhà, I-LN là t

ti p theo c a lo i nhà.
-DC là t b


DC

và I-DC là các t ti p theo c

a ch

a ch

-DT là t b

DT

uc

u c a di n tích và I-DT

t ti p theo c a di n tích
B-GB là t b

GB

u c a giá bán và I-GB là

các t ti p theo c a giá bán
-LH là t b

LH

nh và I-LH là các t ti p theo c a


uc as

ng, s c

n tho i liên l c

UL
1-1.

ò
)
ẽ

trong CSDL.
l
trong

1.2 Kiến trúc của h thống trích rút thông tin
Quá trình trích rút thông tin g

b

nh ng thông tin riêng lẻ t nh ng t p ng li

Trang 15

u tiên h th ng trích rút
th ng



sẽ k t h

l p lu n này v

t o ra nh

l p lu n l

th m chí c các các l p lu n m i.
f

Theo MUC (Message Under

)

H th ng trích rút thông tin
u vào
c ti n x lý

Trích rút th c th

Gi i quy

ng tham chi u

Xây d ng m u ph n t

Xây d ng m u quan h

u k ch

b n
M u trích rút
1-1: Ki n trúc của h th ng trích rút thông tin

1.2.1

Trích rút thực thể - Named Entity Recognition (NER)

n trong m t h th ng trích rút thông
n ra các tên riêng (hay các th c th )

tin. M
giá kh

n d ng tên riêng c a m t h th ng, MUC m i ch khoanh vùng
t

s

ki u

th c

th

nh

ORGANIZATION, TIME. Tiêu chu

nh:


PERSON,

LOCATION,

t h th ng là: so sánh k t qu

Trang 16


nh n di n c a h th

i k t qu nh n di

c. C th nh ng ki u th c th

c MUC th c hi n b ng tay

c xem xét là:




chính xác c a các h th
t t nh

t cao, h th ng

chính xác lên t i 96%. Các danh từ riêng chi m kho ng 70% s
ờ


li u (corpus) c a MUC,
chi

chi m 25%,

i 5%. Trong các danh t riêng thì tên các tổ chức
ể

chi m kho ng 45-50%, các

ời chi m kho ng

chi m t 12-32%, và

23-39%.
V i các ngôn ng khác nhau vi

nh tên th c th sẽ

chính xác

khác nhau:

96%
93.04 %
92.12 %
84.51 %
ủa


1-2.

1.2.2

s

Giải quyế đồng tham chiếu

ng tham chi u (Coreference Resolution – CO) là vi c nh n

Gi i quy
d

ng tham chi u gi a các th c th b ng cách k t h p nh ng thông tin mô

t n mr

n t i các th c th mà nó tham chi u. Thao tác này mang

tính ch t h tr cho các thao tác khác. Nó ít b
b

ng b

i dùng, lo

c.
Ví d : Mary said she would help me
Ở
“


“
”

”

“

t tham chi

”

u cù
n th c th

Trang 17

nm

ng là Mary.
“

”


1.2.3 Xây dựng mẫu phần tử - Template Element Construction (TE)

M i Template Element (TE) là m t l

c tính mô t m


ng c th thu c l

là vi c xây d ng các m u thông

tin mô t t i th c th NE.

c xây d ng d a trên NE và CO t

t khuôn m u thông tin chung cho các th c th . Th c ch t nó là s m
r ng c a bài toán NE.V

d li u.

Ví d :
Date-001:
Value:

04-august-2004

Organisation-001:
Type:

Government

Name:

“

”


Aliases:

“

” “

ff

Organisation-002:
Type:

Media-news

Name:

“

I

”

Person-001:
Name:

i

“

w


”

Location-001:
Type:

Country

Name:

“

Aliases:

“

”
” “

”

Location-002:
Type:

Country

Name:

“


Aliases:

“

f
” “

”

Location-003:
Type:

City

Name:

“

”

1-3.

Trang 18

”

”

ẽ



1.2.4 Xây dựng mẫu quan h

Xây d ng m u quan h (Template Relation Construction – TR) là vi c tìm và
trích rút ra quan h gi a các th c th

a m t th c th

thu c tính c a nó ph thu c vào bài toán c th và b n ch t c
tích, nên quan h gi

thu c v

Relation-001:
Type:
Location:
Entity:
Relation-002:
Type:
Location:
Entity:
Relation-002:
Type:
Employer:
Employee:

c c th .

Located-in
Location-001

Organisation-001
Located-in
Location-003
Person-001
Works-for
Organisation-002
Person-001
a

1-4.

1.2.5

c phân

ưa ra mẫu kịch bản

u k ch b n (Scenario Template production –ST) là vi
nguyên m

nh d

u ra c a h th ng IE. Chúng ràng bu c các th c th TE

v i nhau trong s ki n hay m i quan h

u ch nh các k t qu TE và TR cho phù

h p v i các k ch b n s vi c c th


a IE.

Ví d :
Succession-Event-001:
Date:
Post:
Person-In:
Person-Out:
Organisation:
1-5.

Date-001
“
”
Person-003
Person-010
Organisation-001
a a

Trang 19


y n u ta ph i x lý nhi

nv

c khó hay v i nhi u

n TR (tìm quan h gi a các th c th )


k ch b n ph c t

u

ch nh k t qu TE và TR cho phù h p v i k ch b n) là r t khó.

1.3 Bài toán trích rút thực thể
Trích rút th c th là bài toán con c a bài toán trích rút thông tin th c hi n tìm
ki m v trí và phân lo i các
t ch

a ch , s

i, tên

…

Ki n trúc của h th ng trích rút th c thể
Vi c trích rút và nh n d ng các th c th

ng

c sau:

H th ng trích rút th c thể
u vào

Tách câu

Tách t


Gán nhãn t
lo i
Phân c m

Dò tìm tên th c th

M u trích rút

1-2: Ki n trúc của h th ng trích rút th c thể

Trang 20


Tách câu
)

Tách câu (Sentence splitter ho
b n thành các câu riêng bi
“ ” “?” “!”

c hi

ng sẽ d a vào s xu t hi n c a các kí t sau

c coi là d u hi u k

u này không ph i lúc

xu t hi n c a “ ”


trong t vi t t t, trong m

ng

n tho …

d n URL, trong m t s
Đ u vào : m

n.

Đ u ra : danh sách các câu.
Tách từ
Tách t (tokenizer) là m
"

thành các token. Ví d chu

li

u vào và tách nó

"

nh kho ng

tr ng là phân cách gi a các token. Thì m t tokenizer sẽ tách chu
Đ u vào


n.

Đ u ra : danh sách các t .
Gán nhãn từ loại
Gán nhãn t lo i (Part of speech Tagger – O )
trong câu. M i t sẽ

c gán m t nhãn v t lo i b ng cách s d ng t

ẵn.

ẽ

a.

)

b.

)

c. Adjective (Adj) :
)

d.
)

e.

)


f.

)

g.
)

h.
i.
Đ u vào

j

c s d ng sau khi tách t

)
n, t

n nhãn

Trang 21

n nhãn


Đ u ra : danh sách các t

c gán nhãn


Ví d v POSTag:
Ta có câu sau : John Smith will eat the beans
Sau khi POSTag : John/N Smith/N will/V eat/V the/N beans/N
Phân cụm
)

Phân c
O

Chunking ch th c hi
c m t theo ch

c hi

ẽ

n câu.

n câu thành nhóm các

pháp. Ở

d ng m t t

dành cho c m t . Ví d t p nhãn c a Penn Treebank
ADJP

Adjective Phrase

ADVP


Adverb Phrase

CONJP

Conjunction Phrase conjunction

INTJ

Interjection

LST

List marker

NP

Noun Phrase

PP

Prepositional Phrase

PRT

Particle

SBAR

Clause introduced by a subordinating


UCP

Unlike Coordinated Phrase

VP

Verb Phrase
ủa e

1-6.

Đ u vào
Đ u ra

c gãn nhãn t lo i, t

ee a

n nhãn

nc

c gán nhãn.

Ví d v
Ta có câu sau : John Smith will eat the beans
Sau khi POSTag : John/N Smith/N will/V eat/V the/N beans/N
Sau khi chunking : [NP John/N Smith/N] [VP will/V eat/V] [NP the/N
beans/N]


Trang 22


Dò tìm tên thực thể
Dò tìm tên th c th (Named Entity detection) là quá trình dò tìm và trích rút
u k t qu . Ở

các th c th

u, h th ng nh n

các th c th nh vào tên riêng c a chúng xu t hi
xây d ng. Tuy nhiên, vi c nh n ra th c th

tri th

n d a vào tên riêng có th sai,

vì các th c th khác nhau có th có cùng tên. Ví d , Sài Gòn v a là tên c a m t
thành ph , v a là tên c a m t

ng ti p c n c

i v i bài

p th c th

d ng các


lu t, s d ng ng c nh, s d ng th t lo …
Đ u vào

n, các nhãn

Đ u ra

u các nhãn

Ví d

i h c Bách

Khoa Hà N i </org>

1.4

cứ

d

của r c r

1.4.1

Trích rút thông tin từ vă bản

…

ba

dùng bu c ph

c hi

b ng. Công vi

i

n và ghi chú t t c các thông tin trên trong m t
cs

t nhi u th i gian khi ph i x lý trên

nh ng t p d li u l n. H th ng trích rút m i quan h gi a các th c th sẽ t

ng

c nh
1.4.2

r

eb

a

ont

rút


trích

rút m i quan h gi a các

Trang 23


1.4.3

H tr h thống trả lời câu hỏi tự động

ò

ng

bi t tên c a m

i và

H th ng trích rút m i quan h gi a các th c th
trong h th ng hỏ

ng. H th ng hỏ

a ch , ch c v
vi …
1.4.4

.
Cải thi n kết quả của h thống tìm kiếm


ẵ

?

Ø
Ø

ẵ

ẵ

ẵ )

(

(

)

1-3: H th ng tìm ki m

H th ng tìm ki m thông tin nh
có ch a các t

u vào là các t khóa và tr v t p tài li u

ng k t qu tr v c a các máy tìm ki m (m t lo i h
)


th ng tìm ki

ng là r t l n có khi lên t i hàng nghìn trang web.

k t qu
Ph

ẵ

ng
ng

,m

i dùng mu

t qu tìm ki m l i có c

Hà N i do h th ng tìm theo hai t

“

mV

ng

ng Ph
”

“


ẵ ”

c i thi n k t qu chúng ta tích h p thêm h th ng trích rút m i quan h vào h
th ng tìm ki
thông tin v
tìm ki

lo i bỏ
ng Ph

t qu không mong mu
ng

Hà N i sẽ

t qu tìm ki

Trang 24

ng h p này,
c hi n th trên k t qu


Ư

2.

Ư


Trong m t s

ng h

n, vi c trích rút có th

c th c hi n m t

cách dễ dàng b ng cách s d ng các bi u th c chính quy. V i nh ng ngu
nh d ng theo m t quy t

ó th gi i quy t v

n
m t cách

chính xác. Ví d , n u mu n trích rút nh ng tên sách cùng tên tác gi cu n sách t
trang web Amazon.com, ta có th th y r ng nh ng m c này xu t hi n theo m
d ng nh

nh

m, ch a màu xanh, là hyperlink, tên tác gi

c theo sau b i t khóa "by" và là hyperlinked)

n thu th p

w


thông tin t

trích rút thông tin c n
ph i d a vào chính b n thân ngôn ng - các t ng , th t c a các t , các ng , hay
ng pháp -

th pv

Có nhi

nh d ng n u có m

pc

gi i quy t bài toán

ẽ gi i thi u m t s
v

m c a chúng t

CRFs l

2.1

c s d ng

ư

ế c


ng ti p c

it

y cùng
a trên

xây d ng h th ng

ủc

(hand-written regular expressions)
w

Yorkkhi tham gia

MUC-6 [1]

 Title Capitalized_Word => Title Person Name
w

o
o Sai

‟

Trang 25

f

)