Mục lục
MỞ ĐẦU 1
1 Xếp hạng đối tượng 2
1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Phương pháp PageRank . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Xếp hạng đối tượng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Phương pháp đánh giá xếp hạng . . . . . . . . . . . . . . . . . . . . . 6
1.5 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Học xếp hạng 9
2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Phương pháp học xếp hạng . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Hồi quy có thứ tự và Pairwise . . . . . . . . . . . . . . . . . . 11
2.2.2 Học xếp hạng danh sách Listwise . . . . . . . . . . . . . . . . 13
2.3 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Xếp hạng trong máy tìm kiếm thực thể 16
3.1 Máy tìm kiếm thực thể . . . . . . . . . . . . . . . . . . . . . . . . . . 17
MỤC LỤC v
3.2 Xếp hạng thực thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Mô hình Impression . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.2 Nhận xét, đánh giá mô hình Impression . . . . . . . . . . . . . 27
3.2.3 Mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 Công cụ sử dụng . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.2 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.3 Kết quả và đánh giá . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Tạo nhãn cụm tài liệu 37
4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Phương pháp lựa chọn nhãn . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Học xếp hạng nhãn cụm . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.1 Các đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.2 Học hàm tính hạng . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4.1 Nguồn dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4.2 Dữ liệu học . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.3 Kết quả và đánh giá . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Kết luận 49
Tài liệu tham khảo
71 trang |
Chia sẻ: maiphuongdc | Lượt xem: 1496 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Học xếp hạng trong tính hạng đối tượng và tạo nhãn cụm tài liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
thể trả về cho người dùng kết quả là danh sách các thực thể.
Không chỉ tìm được thực thể mà vấn đề của máy tìm kiếm là những thực thể phù
hợp nhất với truy vấn cần được đưa lên từ những kết quả đầu tiên trả về cho người
dùng. Do đó xếp hạng thực thể là vấn đề quan trọng, cốt lõi của máy tìm kiếm thực
thể.
Giả thiết có tập tài liệuD = {d1, d2, ..., dn}, tập các kiểu thực thểE = {E1, ..., EN},
truy vấn q = α(E1, ..., Em, k1, ..., kl) với kj là các từ khóa, và bộ các thực thể
t = (e1, ..., em). Khi đó độ phù hợp của t đối với truy vấn q trên tập tài liệu D được
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 22
xác định bởi:
Score(q(t)) = p(q(t)|D) =
∑
d∈D
p(d)× p(q(t)|d) (3.1)
Với p(q(t)|d) là xác suất xảy ra quan hệ α của t trên tài liệu d.
Giá trị của Score(q(t)) được dùng để xếp hạng các bộ kết quả trả về, do đó việc
xác định hàm Score(q(t)) là vấn đề quan trọng chúng ta quan tâm.
Những đặc điểm của tìm kiếm thực thể có ảnh hưởng tới giá trị xếp hạng Score()
đã được đưa ra trong [18]:
R-Contextual : Xác suất liên kết giữa thực thể và từ khóa phụ thuộc vào các ngữ
cảnh khác nhau và ảnh hưởng bởi hai yếu tố chính:
• Pattern: Từ khóa và thực thể có thể liên kết với nhau theo các mẫu, ví
dụ: tên thường xuất hiện liền trước số điện thoại.
• Proximity: Từ khóa và thực thể có thể xuất hiện nhiều lần trong trang
web và không giống nhau, khi chúng càng gần nhau thì mối quan hệ càng
có ý nghĩa cao hơn.
R-Holistic: Một thực thể có thể xuất hiện cùng với từ khóa nhiều lần trong một
trang, do đó cần ước lượng tìm liên kết phù hợp nhất
R-Uncertainty: Việc rút trích thực thể không chính xác tuyệt đối, do đó cần có
giá trị độ tin cậy tương ứng cho mỗi thực thể.
R-Associative: Cần phân biệt liên kết giữa từ khóa và thực thể là liên kết mang ý
nghĩa thực hay chỉ là sự xuất hiện ngẫu nhiên giữa chúng. Do đó cần có kiểm
định để loại bỏ những liên kết ngẫu nhiên.
R-Discriminative: Các thực thể trên các trang phổ biến hơn sẽ được đánh giá
cao hơn so với trên trang ít phổ biến hơn.
3.2.1 Mô hình Impression
Từ những phân tích về máy tìm kiếm thực thể, nhóm tác giả Tao Cheng[18] đã
đưa ra mô hình xếp hạng "Impression Model" hình 3.4. Mô hình gồm 3 tầng: Truy
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 23
Global Access Layer
Local Recognition Layer
Global Access Layer
Local Recognition Layer
Validation Layer
Collection E over D Virtual Collection E’ over D’
... ... ... ... ... ...
: ??
: ??
... ... ... ... ... ...
: ??
: ??
... ... ... ... ... ...
: ??
: ??
randomize
Hình 3.4: Impression model [18]
nhập toàn cục (Global Access), nhận dạng cục bộ (Local Recognition), đánh giá
(Validation).
Tầng truy nhập
Để đảm bảo tính "R-Discriminative" của tìm kiếm thực thể, nhiệm vụ của modul
này xác định trọng số toàn cục p(d), là khả năng để một tài liệu d được quan sát,
xét tới. Trong ngữ cảnh máy tìm kiếm với các tài liệu web, giá trị này là độ phổ
biến của trang web, hay chính là độ quan trọng của trang web - hạng trang. Và do
đó tác giả Tao Cheng đã chọn PageRank (PR) [43] để xác định: p(d) = PR[d]. Ta
có:
Score(q(t)) =
∑
d∈D
PR[d]× p(q(t)|d) (3.2)
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 24
DICLOFENAC
Tên gốc: Diclofenac
Tên thương mại: VOLTAREN, CATAFLAM, VOLTAREN-XR
Nhóm thuốc và cơ chế: Diclofenac là một thuốc chống viêm phi steroid
(NSAID) hiệu quả trong điều trị sốt, đau và viêm trong cơ thể. Các NSAID là
những thuốc không gây ngủ giảm các chứng đau từ nhẹ đến vừa do nhiều
nguyên nhân gây ra, như chấn thương, thống kinh, viêm khớp và các chứng
bệnh cơ xương khác. Vì mỗi bệnh nhân có đáp ứng khác nhau với NSAID,
O1
O2
. . .
Hình 3.5: Ví dụ rút trích thực thể thuốc
Tầng nhận dạng
Với mỗi tài liệu d được xét ở tầng truy nhập, trọng số cục bộ - xác suất xuất hiện
của từng bộ thực thể t = (e1, ..., em) với các từ khóa k = {k1, ..., kl} trong tài liệu
đó được xác định bởi p(q(t)|d). Gọi γ = (o1, ..., og) là một quan sát (xuất hiện)
của q(t) = α(e1, ..., em, k1, ..., kl) trên d (có g = m + l). Ví dụ: trong hình 3.5 với
E = {#drug}, k ="viêm", q = {"viêm"#drug} thì ta có một quan sát γ = (o1, o2).
Trong mỗi tài liệu có thể có nhiều quan sát γ (tính chất R-Holistic) và do đó p(q(t)|d)
cần được ước lượng trên tất cả các quan sát γ đó, [18] đưa ra công thức ước lượng:
p(q(t)|d) = max
γ
p(α(γ)) (3.3)
Với p(α(γ)) là xác suất/khả năng mà một quan sát γ phù hợp với hàm ngữ cảnh α.
Tuy nhiên khi được rút trích từ tài liệu d, các quan sát oi biểu diễn một thực thể
ei là một thể hiện của kiểu Ei và được xác định với một xác suất p(ei ∈ Ei|d) (tính
chất R-Uncertainty). Giá trị này do modul rút trích xác định, và lưu lại trong khi
đánh chỉ mục nên có thể được xác định một cách đơn giản bằng ei.conf . Vì vậy, ta
có:
p(α(γ)) =
∏
ei∈γ
ei.conf × pcontext(α(γ) (3.4)
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 25
Thay vào công thức 3.3 suy ra:
p(q(t)|d) = max
γ
(∏
ei∈γ
ei.conf × pcontext(α(γ)
)
(3.5)
Theo tính chất R-Contextual, độ phù hợp của γ trong ngữ cảnh α phụ thuộc vào
hai yếu tố: độ phù hợp mẫu (pattern) gọi là αB và độ gần nhau (proximity) giữa
thực thể và từ khóa gọi là αP . Do đó ta có:
pcontext(α(γ)) = αB(γ)× αP (γ)
• αB là hàm lô-gic trả về giá trị 0 hoặc 1, cho biết quan sát γ với các oi có thỏa
mãn ràng buộc về mẫu không. Ví dụ mẫu phrase(o1, ..., om) yêu cầu các oi
phải xuất hiện đúng thứ tự như xác định.
• αP là xác suất quan sát γ phù hợp với t trong cửa sổ quan sát s. Để đơn giản,
trong [18] các tác giả đã sử dụng mô hình Span Proximity để ước lượng xác
suất này, và đưa ra công thức: αP (γ) = p(s|γ).
Thay vào công thức 3.5 ta được:
p(q(t)|d) = max
γ
(∏
ei∈γ
ei.conf × αB(γ)× p(s|γ)
)
(3.6)
Vậy công thức Score(q(t)) được xác định:
Score(q(t)) =
∑
d∈D
PR[d]×max
γ
(∏
ei∈γ
ei.conf × αB(γ)× p(s|γ)
)
(3.7)
Tầng đánh giá
Phía bên phải của mô hình (hình 3.4) gọi là một quan sát ảo, tập dữ liệu D′ được
lấy ngẫu nhiên từ D để làm đối chứng so sánh những nhận định trên D. Tầng đánh
giá kiểm định giả thuyết thống kê, với giả thuyết không H0 (null hypothesis) và
G-test theo [18] để đánh giá độ tin cậy thông tin nhận được từ D.
Giả thuyết không: giả thiết rằng liên kết giữa các thực thể, từ khóa trong t =
(e1, ..., em, k1, ..., kl) xảy ra ngẫu nhiên. Tập D′ được lấy ngẫu nhiên từ tập D, D′
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 26
cần "giống" với D ngoại trừ trong D′ liên kết của các từ khóa và các thực thể hoàn
toàn là ngẫu nhiên. Xây dựng tập D′ từ D bằng việc tạo các tài liệu d′ ngẫu nhiên:
Đưa ngẫu nhiên các thực thể và từ khóa vào d′, mỗi thực thể, từ khóa được đưa vào
độc lập, với xác suất giống như xác suất xuất hiện của chúng trong D. Do đó mối
liên hệ giữa thực thể và từ khóa là ngẫu nhiên, nhưng vẫn đảm bảo xác suất quan
sát một từ khóa, hay thực thể trong D′ cũng giống như trong D:
p(ei ∈ d
′) =
∑
ei∈d,d∈D
p(d) ; p(kj ∈ d
′) =
∑
kj∈d,d∈D
p(d)
Do đặc điểm của D′ trên nên giá trị trung bình của độ tin cậy của tất cả các thực
thể ej trong D cũng là độ tin cậy của các thực thể ej (xác suất ej là Ej) trong D′:
ej .conf . Và ta có nếu q(t) không xuất hiện trong d′ thì p(q(t)|d′) = 0, ngược lại nếu
q(t) ∈ d′ thì p(q(t)|d′) là như nhau với mọi d′. Do đó:
p(q(t)|D′) =
∑
d′∈D′&q(t)∈d′
p(d′)× p(q(t)|d′)
= p(q(t)|d′)×
∑
d′∈D′&q(t)∈d′
p(d′)
= p(q(t)|d′)× p(q(t) ∈ d′) (3.8)
Trong đó p(q(t) ∈ d′) là xác suất của t xuất hiện trong d′. Do từ khóa và các thực
thể được lấy độc lập vào d′ nên xác suất xuất hiện của q(t) trong d′ được tính bởi:
p(q(t) ∈ d′) =
j=1∏
m
p(ej ∈ d
′)
l∏
i=1
p(ki ∈ d
′)
Tương tự như công thức 3.5, lấy giá trị trung bình ta có:
p(q(t)|d′) = (
m∏
j=1
ej.conf)× pcontext(q(t)|d
′)
Trong đó, với q(t) ∈ d′, tương tự công thức tính pcontext(q(t)|d) có:
pcontext(q(t)|d
′) = p(q(t)|s)
Từ đó suy ra:
pcontext(q(t)|d
′) = p(q(t)|s) =
∑
s p(q(t)|s)
|s|
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 27
Với |s| là số các giá trị s được xét.
Thay các công thức trên vào 3.8 được:
p(q(t)|D′) =
j=1∏
m
p(ej ∈ d
′)
l∏
i=1
p(ki ∈ d
′)×
× (
m∏
j=1
ej .conf)×
∑
s p(q(t)|s)
|s|
(3.9)
Sử dụng kiểm định giả thiết thống kê G-test so sánh quan sát p0 với ngẫu nhiên pr
để kiểm tra quan sát p0 có phải là ngẫu nhiên không:
Score(q(t)) = 2(p0 log
p0
pr
+ (1− po) log
1− p0
1− pr
) (3.10)
Do p0, pr 1 nên công thức 3.10 có thể ước lượng:
Score(q(t)) ∝ p0 log
p0
pr
Trong đó:
p0 = p(q(t)|D) =
∑
d∈D
PR(d)×max
γ
(
∏
ei∈γ
ei.conf × αB(γ)× p(s|γ))
pτ = p(q(t)|D
′) =
m∏
j=1
(
∑
ej∈d,d∈D
p(d))×
l∏
i=1
(
∑
ki∈d,d∈D
p(d))×
×
m∏
j=1
ej.conf ×
∑
s p(q(t)|s)
|s|
3.2.2 Nhận xét, đánh giá mô hình Impression
Ưu điểm
Với những đặc điểm của tìm kiếm thực thể được phân tích, mô hình Impression đã
bám sát và xác định hàm tính hạng Score(q(t)) để đảm bảo các tính chất đó:
1. Tính chất R-Contextual được thể hiện ở các trọng số αB và p(s|γ)
2. Xác định giá trị cực đại theo γ để chọn ra quan sát "phù hợp" nhất (R-Holistic)
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 28
3. Tính chất R-Uncertainty của việc rút trích các thực thể và đánh giá các thực
thể được thể hiện ở trọng số ei.conf
4. Bằng kiểm định giả thiết thống kê trong tầng đánh giá (Validate), tính chất
R-Associative được đảm bảo
5. Sử dụng trọng số PR - độ quan trọng/phổ biến của trang web (đảm bảo tính
chất R-Discriminative)
Đánh giá chất lượng của xếp hạng các bộ thực thể t tìm được, [18] giới thiệu các
phương pháp xếp hạng làm đối sánh:
• N (Naive): xếp hạng theo phần trăm các tài liệu có chứa t.
• L (Local Model Only): xếp hạng dựa theo trọng số cục bộ cao nhất của t trong
từng tài liệu.
• G (Global Aggregation Only): xếp hạng theo tổng trọng số của các tài liệu có
chứa t. Và PR được chọn là trọng số cho mỗi tài liệu.
• C (Combination of Local Model and Global Aggregation): xếp hạng theo tổng
trọng số cục bộ của t trong tất cả các tài liệu chứa t.
• W (EntityRank Without G-test): xếp hạng theo trọng số tổng hợp của Entity
Rank nhưng không sử dụng đánh giá G-test (p0).
Và theo đánh giá trong [18] (hình 3.6) độ chính xác kết quả xếp hạng của thuật
toán EntityRank (xếp hạng với mô hình Impression) có MRR u 0.65 cao hơn gấp
nhiều lần những phương pháp xếp hạng đối sánh được đưa ra.
Nhược điểm
Trong tài liệu d, một thực thể có thể xuất hiện nhiều lần và phù hợp với ngữ cảnh
truy vấn (các quan sát γ) theo tính chất R-Holistic. Việc ước lượng với công thức
3.5 chỉ mang ý nghĩa lựa chọn quan sát phù hợp nhất trong tài liệu. Tuy nhiên, ta
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 29
Measure EntityRank L N G C W
M R R 0.648 0.047 0.037 0.050 0.266 0.379
M R R 0.648 0.125 0.106 0.138 0.316 0.387
Query Type I MRR Comparison
Measure EntityRank L N G C W
M R R 0.659 0.112 0.451 0.053 0.573 0.509
M R R 0.660 0.168 0.454 0.119 0.578 0.520
Query Type II MRR Comparison
Hình 3.6: So sánh độ chính xác MRR [18]
có thể dễ dàng nhận thấy số lần xuất hiện trong tài liệu của thực thể mà phù hợp
ngữ cảnh cũng có một vai trò quan trọng, ảnh hưởng hạng của thực thể.
Ví dụ: trong tài liệu trích chọn các thực thể thuốc hình 3.5, với truy vấn
q = {"viêm"#drug}. Nếu chỉ xét trên tài liệu này thì một cách trực giác ta
thấy các thực thể thuốc nên được xếp hạng {"Diclofenac", "NSAID", "Voltaren",
"Catafram","Voltaren-XR","steroid"}. Nếu chỉ dựa vào công thức 3.5, thì rõ ràng
ở đây thuốc "steroid" được xếp hạng đầu tiên- như vậy không hợp lý.
Thêm nữa, từ bảng so sánh độ chính xác của một số phương pháp xếp hạng
hình 3.6, ta dễ dàng nhận thấy độ đo C có ý nghĩa cao hơn hẳn L, tức độ đo dựa
vào tổng trọng số cục bộ trong từng tài liệu có ý nghĩa cao hơn lấy trọng số cục bộ
cao nhất.
3.2.3 Mô hình đề xuất
Mô hình xếp hạng Impression, công thức xác định giá trị để xếp hạng thực thể được
đưa ra hoàn toàn dựa vào việc phân tích các đặc điểm và tìm công thức để thỏa mãn
các nhận định đó. Tuy nhiên sau khi phân tích nhược điểm ở trên đã cho thấy như
vậy là chưa đầy đủ. Học xếp hạng cho ta giải pháp để giải quyết vấn đề, tìm hàm
tính hạng "tốt nhất" với các đặc trưng xác định. Qua phân tích các đặc điểm của
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 30
tìm kiếm để đưa ra các trọng số tương ứng với các đặc trưng của thực thể. Mô hình
học xếp hạng thực thể trong máy tìm kiếm thực thể đề xuất hình 3.7. Trong mô
Learning
Ranking
Mô hình
),( tqf
),(,
),(,
22
11
tqft
tqft
ii
ii
)1(
2
)1(
1
)1(
t
t
q
)(
2
)(
1
)(
m
m
m
t
t
q
Truy vấn
Dữ liệu học
?),(......,
?),(?),,( 21
nt
tt
q
Hàm
th
ự
c
th
ể
...
..
.
...
..
.
...
..
.
Hình 3.7: Mô hình học xếp hạng trong máy tìm kiếm thực thể
hình, thành phần được bao đen là một thành phần xếp hạng trong máy tìm kiếm.
Mô-dul học xếp hạng độc lập với phần tìm kiếm, có nhiệm vụ học hàm xếp hạng
(có thể chỉ cần một lần) để đưa ra mô hình/hàm xếp hạng phù hợp cho mô-dul xếp
hạng của máy tìm kiếm.
Dữ liệu học
Tập dữ liệu học gồm DT tài liệu- đã xác định các thực thể trong mỗi tài liệu, và tập
truy vấn QT . Với mỗi truy vấn q ∈ QT , q = α(e1, ..., em, k1, ..., kl) có danh sách các
thực thể (t(1..m)i ) tương ứng phù hợp truy vấn q và được sắp xếp giảm dần độ phù
hợp. Mỗi bộ thực thể t có các đặc trưng tương ứng với mỗi truy vấn q, từ những
phân tích về máy tìm kiếm thực thể và xếp hạng thực thể, tôi xác định các đặc
trưng của thực thể:
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 31
1. Tỷ lệ trang tài liệu chứa t phù hợp với q:
N =
|D′|
|DT |
với ∀d ∈ D′có q(t) ∈ d
2. Tổng trọng số PR của các trang tài liệu chứa t phù hợp với q:
G =
∑
d∈DT , q(t)∈d
PR[d]
3. Trọng số cục bộ lớn nhất (công thức 3.3) của t với truy vấn q trên tất cả các
tài liệu:
L = max
d∈DT , q(t)∈d
max
γ∈d
p(α(γ))
Với γ là một quan sát của t trên tài liệu d
4. Tổng trọng số cục bộ của t trong tất cả các tài liệu chứa t phù hợp q:
SL =
∑
d∈DT , q(t)∈d, γ∈d
p(α(γ))
5. Tổng các tích trọng số cục bộ của t trong từng tài liệu chứa t phù hợp q nhân
với PR của tài liệu đó:
GL =
∑
d∈DT , q(t)∈d, γ∈d
(
p(α(γ))×PR[d]
)
6. Giá trị cực đại của tích trọng số cục bộ của t nhân PR của tài liệu chứa t
tương ứng:
M = max
d∈DT , q(t)∈d, γ∈d
(
p(α(γ))×PR[d]
)
Trong các công thức trên, p(α(γ)) là trọng số cục bộ của thực thể t ứng với quan
sát γ trong tài liệu d đang xét. Với các phạm vi (domain ) tìm kiếm thực thể khác
nhau, giá trị trọng số cục bộ có thể được thay đổi phù hợp. Thực nghiệm với domain
cụ thể dưới đây, tôi sẽ đưa ra cách tính cho đại lượng này.
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 32
3.3 Thực nghiệm
Hiện nay, đang có một dự án nghiên cứu xây dựng "hệ theo dõi sức khỏe toàn cầu"
mang tên BioCaster∗ giúp tìm kiếm những thông tin về y-sinh học một cách chính
xác hơn các máy tìm kiếm thông thường. Điều đó cho thấy việc xây dựng hệ tìm
kiếm y tế đang rất được quan tâm. Tiếp cận vấn đề thời sự về xếp hạng thực thể và
tìm kiếm y tế, tôi tiến hành thử nghiệm mô hình xếp hạng thực thể của mình vào
máy tìm kiếm trong lĩnh vực y tế tiếng Việt, mà cụ thể là tìm kiếm thực thể thuốc.
Vấn đề rút trích thực thể không nằm trong phạm vi của luận văn này, với thử
nghiệm của mình, khi khảo sát dữ liệu, tôi đưa ra cách xác định thực thể thuốc đơn
giản như sau:
• Thực thể thuốc trên trang web tiếng Việt: tên thuốc thường là tiếng Anh,
ngoại trừ tên các nước, tên viết tắt của doanh nghiệp (tuân theo một số mẫu
xác định, ví dụ: "Rottapharm., Ltd", "dược phẩm Hà Nội HAPHARCO").
• Một thực thể đã được xác định là thuốc thì chắc chắn đó là thuốc.
Như mô hình đã đưa ra, trọng số cục bộ của một quan sát γ trên d cần được
xác định. Với quan nhận định: mối liên kết giữa thực thể và từ khóa ngữ cảnh càng
khăng khít khi chúng càng gần nhau, nên trọng số cục bộ được xách định:
p(α(γ)) =
1
Sγ
Với Sγ là kích thước của đoạn tài liệu bao quan sát γ, ví dụ hình 3.8.
3.3.1 Công cụ sử dụng
Các chương trình phần mềm mã mở đã được sử dụng trong thực nghiệm này:
SVMmap† là công cụ (tool) học giám sát với tối ưu MAP để học xếp hạng tài
liệu. Trong thực nghiệm tôi sử dụng công cụ này áp dụng vào học mô hình xếp hạng
thực thể.
∗
†
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 33
Tài liệu: d = “Desipramin1 là2 thuốc3 được4 dùng5 điều6 trị7 trầm8 cảm9”
Truy vấn: q=("trầm cảm" #drug)
Với quan sát: γ=(o1,o2) thì
o1 o2
Hình 3.8: Ví dụ xác định trọng số cục bộ p(α(γ))
Lucene‡ là một máy tìm kiếm văn bản (text) mã mở được lựa chọn để tiến hành
cài đặt các modul:
• Rút trích thực thể thuốc
• Đánh chỉ mục (index) thực thể
• Xếp hạng thực thể thuốc
3.3.2 Dữ liệu
Dữ liệu tìm kiếm
Tiến hành thu thập (crawl) các trang web về y tế tiếng Việt, từ nguồn của 10 web
site (phụ lục A.1)
• Tổng số trang web tiếng Việt được crawl và index: 6217 trang (không index
những trang web có nội dung quá ngắn- dưới 20 từ, và các trang web chỉ chứa
liên kết)
• Kích thước dữ liệu: sấp xỉ 180MB
• Số thể hiện của thực thể thuốc được index: 14794
‡
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 34
Các mẫu truy vấn được sử dụng
1. q=(context #drug): Tìm thực thể thuốc với ngữ cảnh context mà truy
vấn xác định.
2. q=(context #drug=[Thuoc] #drug): Tìm thực thể thuốc có quan hệ
với thực thể thuốc Thuoc trong ngữ cảnh context được xác định trong truy
vấn.
Xây dựng tập dữ liệu học đưa vào mô-dul học hàm tính hạng
Tạo 5 truy vấn cho mỗi mẫu truy vấn trên, với mỗi truy vấn xác định 10 thực thể
trả về đầu tiên tương ứng và sắp xếp theo độ phù hợp giảm dần. Khi tìm kiếm người
dùng quan tâm tới các kết quả trả về đầu tiên, việc xếp hạng đúng các thực thể vào
10 kết quả đầu tiên quan trọng hơn việc các xếp hạng sau đó. Do giới hạn thời gian
làm thực nghiệm, nên tôi chỉ xây dựng tập dữ liệu học với 10 thực thể xếp hạng
đầu tiên cho mỗi truy vấn. Cách xác định 10 thực thể đầu tiên:
• Tìm kiếm thực thể với mô hình xếp hạng Impression (Cài đặt Impression với
hàm p(s|γ) = 1
s
) để tìm các thực thể với các trang chứa thực thể tương ứng
• Tìm kiếm thuốc với máy tìm kiếm thông thường (cài đặt Lucene với hàm xếp
hạng BM25[63]) có được các trang tốt nhất theo đánh giá BM25.
• Từ 2 kết quả trên, lựa chọn 10 thực thể tốt nhất và sắp xếp để được kết quả
trả về "đúng" cần có.
3.3.3 Kết quả và đánh giá
Kết quả có hàm tính hạng:
rf(t) = 0.0010×N + 0.0011×G + 0.0120× L+
+ 0.3305× SL+ 0.2953×GL + 0.3601×M
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 35
Bảng 3.2: So sánh MRR, MAP của BM25, Impression, LTR
Phương pháp BM25 Impression LTR
MRR 0.283 0.767 0.800
MAP 0.275 0.651 0.705
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1 2 3 4 5
A
v
e
ra
g
e
P
re
ce
si
o
n
Query
BM25
ER
LTR
Hình 3.9: So sánh độ chính xác trung bình AP trên 5 query
Từ hàm tính hạng trên, cho ta thấy vai trò quan trọng của trọng số: M, SL và GL.
Trọng số N, G ít quan trọng nhất, có thể bỏ qua - do giá trị N, G thường rất nhỏ,
mà hệ số lại nhỏ nên thành phần đó không có ảnh hưởng lớn tới kết quả xếp hạng.
Và trọng số L (cực đại trọng số cục bộ) có ít giá trị hơn trọng số SL (tổng trọng số
cục bộ)
Áp dụng hàm tính hạng vào mô-dul xếp hạng thực thể trong máy tìm kiếm, thực
hiện tìm kiếm trên 5 query khác nhau để đánh giá. Bảng 3.2 so sánh MRR và MAP
của ba phương pháp sử dụng Okapi BM25 để xếp hạng, với mô hình Impression của
EntityRank trong phần trước và với mô hình học xếp hạng (gọi tắt LTR: Learn To
Rank).
Các nhận xét:
• LTR và Impression có MRR, MAP hơn hẳn BM25, cho thấy việc tìm kiếm
CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 36
thực thể trả lại kết quả tốt hơn cho người dùng.
• MRR của LTR là 0.8 cao hơn của mô hình Impression bằng 0.767 (+0.023)
chứng tỏ kết quả đúng đầu tiên của LTR trả về xuất hiện ở thứ hạng tốt hơn
(thấp hơn) của Impression.
• So sánh MAP cho thấy độ chính xác trung bình của LTR cũng cao hơn của
Impression (+0.054).
• Biểu đồ so sánh chi tiết độ chính xác trung bình AP trên từng truy vấn (hình
3.9) càng cho ta khẳng định phương pháp LTR đã học hàm tính hạng thực
thể hiệu quả.
3.4 Tổng kết chương
Qua phân tích một mô hình xếp hạng thực thể trong máy tìm kiếm thực thể [17,
18, 19], và học xếp hạng để học hàm tính hạng thực thể hiệu quả trên lĩnh vực tìm
kiếm thực thể thuốc. Các kết quả thu được đã chứng minh vai trò và hiệu quả của
học xếp hạng áp dụng vào máy tìm kiếm.
C h ư ơ n g 4
Tạo nhãn cụm tài liệu
Chương này giới thiệu các phương pháp tạo nhãn cụm tài liệu, và tự động tạo nhãn
cho cây phân cấp tài liệu.
4.1 Giới thiệu
Máy tìm kiếm ngày nay được sử dụng rộng rãi và trở thành một công cụ không thể
thiếu của người dùng khi tìm kiếm thông tin trên môi trường web. Kết quả trả về
của máy tìm kiếm cho mỗi truy vấn thường rất lớn (từ vài nghìn tới hàng triệu kết
quả). Với cùng truy vấn nhưng mỗi người dùng khác nhau có thể có mong muốn
khác nhau, ví dụ khi tìm kiếm "phân cụm" (cluster) có người quan tâm tới các
phương pháp và thuật toán phân cụm nhưng có người lại quan tâm tới tính toán
cụm. Để nâng cao chất lượng của máy tìm kiếm và giúp định hướng chủ đề cho
người dùng, một nhu cầu đặt ra đó là phân cụm kết quả trả về của máy tìm kiếm
37
CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 38
giống như Vivisimo∗ hay Carrot†.
Phân cụm không phải là lĩnh vực mới nhưng vấn đề phân cụm các kết quả
trả về từ máy tìm kiếm được nhiều nhà khoa học quan tâm trong những năm
gần đây, với các nghiên cứu về phân cụm để cải tiến chất lượng tìm kiếm web
[65, 41, 31, 28, 27, 67]. Kết quả trả về của máy tìm kiếm được phân thành các tập
nhỏ hơn, mỗi cụm này bao gồm các tài liệu tương tự nhau, khi đó các tài liệu trong
một cụm sẽ cùng hướng tới một chủ đề chung nào đó. Mỗi cụm cần được tạo nhãn
chủ đề giúp định hướng nội dung cho người dùng về các tài liệu thuộc cụm đó. Do
đó việc tạo nhãn cho cụm tài liệu là một bài toán quan trọng, và nó cũng thể hiện
chất lượng phân cụm tài liệu. Vấn đề tạo nhãn cho cụm tài liệu cũng được nhiều
nhà khoa học [28, 42, 39, 38, 65, 5] quan tâm.
Không chỉ tạo nhãn cho các kết quả trả về từ máy tìm kiếm, vấn đề tạo nhãn
có thể được áp dụng để tạo nên các danh bạ web (Web directory) như Dmoz của
ODP∗ hay Yahoo!Directory† mà hiện nay trong tiếng Việt có Zing‡ đang phát triển
một danh bạ web. Và các trang web cũng thường được phân loại (category) và tổ
chức thành cấu trúc cây phân loại như các trang tin tức (vietnamnet, vnexpress).
Tất cả đều được tổ chức dạng cấu trúc cây phân cấp gọi là cây phân cấp chủ đề.
Cách tổ chức dạng cây phân cấp khá phổ biến bởi nó biểu diễn thông tin ở các mức
chi tiết khác nhau: từ đỉnh của cây càng đi xuống sâu hơn càng nhận được thông
tin chi tiết hơn về chủ đề riêng giúp người dùng tiếp cận thông tin có định hướng và
dễ dàng hơn. Mỗi đỉnh của cây phân cấp có một tập các tài liệu và có nhãn tương
ứng về chủ để các tài liệu đó (cụm tài liệu). Ví dụ của báo vnexpress có: mục "Văn
hóa" chứa các mục con "âm nhạc", "thời trang", "điện ảnh",... Mục tiêu của phân
cấp tài liệu là để cải thiện khả năng cho người dùng hiển thị thông tin, vì vậy một
cây tốt cần có mô tả tốt - tức có nhãn cụm tài liệu ở các đỉnh tốt.
Dmoz[25] là cây phân cấp chủ đề Web lớn nhất đã được xây dựng và được tổ chức
theo từng ngôn ngữ khác nhau Anh, Pháp, Nhật, Trung Quốc, Hàn Quốc,...chưa
∗http:/vivisimo.com
†
∗
†
‡
CHƯƠNG 4. TẠO NHÃN CỤM TÀI LIỆU 39
có tiếng Việt. Dmoz cung cấp cấu trúc phân cấp chủ đề cho các trang Web từ tổng
quát tới chi tiết và được sử dụng trong tìm kiếm nâng cao của Google.
Nhu cầu xây dựng cây phân cấp chủ đề Web tiếng Việt được đặt ra, nhằm mục
đích hỗ trợ người dùng việc tìm kiếm theo từng chủ đề. Và Zing!Directory là một
cây phân cấp chủ đề Web tiếng Việt đang được xây dựng.
Với sự phát triển của các danh bạ web (tiếng Anh), C.Yang và J.Lin [60] năm
2007, T.C. Wu và W.L. Hsu [57] năm 2006 đã đưa ra hướng tích hợp các danh bạ
web có sẵn để tạo một cây phân cấp chủ đề duy nhất, hỗ trợ người dùng tìm kiếm
thông tin từ nhiều nguồn khác nhau. Kỹ thuật tích hợp cho phép mở rộng, sửa
đổi cây phân loại bằng cách học cách tổ chức các tài liệu từ các cây nguồn để tạo
cây mới [60], và dựa vào mô hình trường ngẫu nhiên (CRFs: Conditional Random
Fields)[57]. Trong tiếng Việt, danh bạ web của trang tin tức việt nam§ là danh bạ
trang web của các tổ chức đã đăng ký, hoạt động trong các lĩnh vực khác nhau và
được cấu trúc dạng cây phân cấp chủ đề nhưng mới chỉ có chủ đề tới mức 3. Hay
một số danh bạ web tiếng Việt khác như vnn777.com hướng các chủ đề về tin tức
và giải trí, và các danh bạ đó chỉ có phân cấp cao nhất tới mức 3. Nên không đặt
vấn đề tích hợp các danh bạ web cho tiếng Việt.
Một câu hỏi đưa ra: làm thế nào tạo cây phân cấp chủ đề cho các trang web
tiếng Việt giống như Dmoz? Qua các phân tích về phân cụm và tạo nhãn cụm tài
liệu, một phương pháp khả thi đó là phân cụm phân cấp các trang web [1], sau đó
xác định chủ đề cho từng cụm ở mỗi cấp.
Vấn đề tạo nhãn cụm tài liệu có vai quan trọng trong cả bài toán phân cụm kết
quả trả về của máy tìm kiếm và xây dựng cây phân cấp chủ đề. Nghiên cứu và đưa
ra mô hình học tạo
Các file đính kèm theo tài liệu này:
- MSc09_Nguyen_Thu_Trang.pdf