Luận văn: Xây dựng mô hình mở rộng truy vấn trong truy xuất thông tin văn bản

Chia sẻ: Nguyễn Văn Biên | Ngày: | Loại File: PDF | Số trang:223

Thêm vào BST

Báo xấu

108
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong truy xuất thông tin (Information Retrieval, IR), do những yếu tố khác nhau, người sử dụng thường dùng các truy vấn dạng đơn giản biểu diễn yêu cầu cần tìm. Việc này dẫn đến kết quả tìm được không đáp ứng đủ nhu cầu mong muốn, hoặc chất lượng thấp. Do đó, mở rộng truy vấn là vấn đề cần thiết, để từ đó giúp hệ thống truy xuất thông tin có thêm thông tin theo ngữ cảnh nhằm cải tiến các kết quả truy vấn. Thông tin theo ngữ cảnh có thể thu được từ những thông tin...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: Xây dựng mô hình mở rộng truy vấn trong truy xuất thông tin văn bản

Đ I H C QU C GIA TP. HCM TRƯ NG Đ I H C BÁCH KHOA TP.HCM NGUY N CHÁNH THÀNH XÂY D NG MÔ HÌNH M R NG TRUY V N TRONG TRUY XU T THÔNG TIN VĂN B N LU N ÁN TI N SĨ K THU T TP.H CHÍ MINH – 2010
Đ I H C QU C GIA TP. HCM TRƯ NG Đ I H C BÁCH KHOA TP.HCM NGUY N CHÁNH THÀNH XÂY D NG MÔ HÌNH M R NG TRUY V N TRONG TRUY XU T THÔNG TIN VĂN B N Chuyên ngành: KHOA H C MÁY TÍNH Mã s : 62.48.01.01 LU N ÁN TI N SĨ K THU T NGƯ I HƯ NG D N KHOA H C PGS.TS. PHAN TH TƯƠI TP.H CHÍ MINH – 2010
L I CAM ĐOAN Tôi cam ñoan r ng n i dung c a lu n án này là k t qu nghiên c u c a b n thân. T t c nh ng tham kh o t các nghiên c u liên quan ñi u ñư c nêu ngu n g c m t cách rõ ràng t danh m c tài li u tham kh o trong lu n án. Nh ng ñóng góp trong lu n án là k t qu nghiên c u c a tác gi ñã ñư c công b trong các bài báo khoa h c trong ph n “Các công trình khoa h c” c a lu n án và chưa ñư c công b trong b t kỳ công trình khoa h c nào khác. Tác gi lu n án Nguy n Chánh Thành
L I C M ƠN Trong quá trình hoàn thành lu n án này, tôi ñã ñư c các th y cô nơi cơ s ñào t o giúp ñ t n tình, cơ quan nơi công tác t o m i ñi u ki n thu n l i và b n bè cùng gia ñình thư ng xuyên ñ ng viên khích l . Lu n án này không th hoàn thành t t n u không có s t n tình hư ng d n và s giúp ñ quí báu c a PGS.TS. Phan Th Tươi, giáo viên hư ng d n mà tôi tôn vinh và mu n ñư c bày t lòng bi t ơn sâu s c nh t. Tôi cũng mu n ñư c bày t lòng bi t ơn ñ i v i t p th các th y cô khoa Khoa h c và K thu t Máy tính trư ng Đ i h c Bách khoa TP. H Chí Minh ñã giúp ñ và t o ñi u ki n cho tôi r t nhi u trong quá trình h c t p và nghiên c u Khoa; ñ c bi t PGS.TS. Cao Hoàng Tr , PGS.TS. Dương Tu n Anh, PGS.TS. Đ Phúc và TS. Đ ng Tr n Khánh ñã có nh ng l i khuyên quý giá trong quá trình làm NCS và vi t lu n án này; c m ơn Phòng qu n lý Sau Đ i h c v s h tr các th t c hoàn thành lu n án. S bi t ơn c a tôi xin ñư c g i ñ n gia ñình, v con và ngư i thân, ñã h tr ñ ng viên và t o m i ñi u ki n thu n l i cho tôi trong su t quá trình hoàn thành khóa h c NCS. Cu i cùng tôi c m ơn anh Ngô Hùng Phương cùng t t c b n bè, ñ c bi t các thành viên trong nhóm nghiên c u BK-NLP (thu c trư ng Đ i h c Bách khoa Tp.HCM) ñã góp nhi u ý ki n thi t th c và có nh ng l i ñ ng viên khích l quý báu giúp tôi vư t qua khó khăn và hoàn thành t t lu n án. Tác gi lu n án Nguy n Chánh Thành
TÓM T T Trong truy xu t thông tin (Information Retrieval, IR), do nh ng y u t khác nhau, ngư i s d ng thư ng dùng các truy v n d ng ñơn gi n bi u di n yêu c u c n tìm. Vi c này d n ñ n k t qu tìm ñư c không ñáp ng ñ nhu c u mong mu n, ho c ch t lư ng th p. Do ñó, m r ng truy v n là v n ñ c n thi t, ñ t ñó giúp h th ng truy xu t thông tin có thêm thông tin theo ng c nh nh m c i ti n các k t qu truy v n. Thông tin theo ng c nh có th thu ñư c t nh ng thông tin ph n h i liên quan, t ñ ng hi n hay mô hình tri th c như b n th h c (ontology). Vi c ng d ng ontology ñ tr giúp vi c m r ng truy v n ñư c nghiên c u t ñ u th p niên 1990 v i m t s thành công. Trong bài toán m r ng truy v n, m t s nhóm nghiên c u trên th gi i ñã s d ng ontology WordNet. M t s nhóm khác ñã phát tri n ontology ñ ph c v nhu c u m r ng truy v n. Nh ng ñ nh hư ng ñ c bi t v c u trúc ontology c n xây d ng bao g m ñ xu t v nhóm thành ph n l p, th hi n, thu c tính, hay ñ xu t v nhóm th hi n, thu c tính, khái ni m và quan h r i r c (disjointness), IS-A, và tương ñương (equivalence), ho c phát tri n m t mô hình m i v m ng ng nghĩa d a trên nh ng quan h trích d n t WordNet như quan h thư ng danh (hypernymy), h danh (hyponymy) … cùng m t s quan h ñư c ñ nh nghĩa thêm như chú gi i (gloss), ch ñ và mi n (domain). Lu n án này ñ xu t phương pháp m r ng truy v n d a trên cơ s b n th h c (ontology-based query expansion). Đ th c hi n m c tiêu trên, lu n án ph i gi i quy t các v n ñ chính: (1) ñ xu t cơ s lý thuy t v các mô hình m r ng truy v n d a trên ontology; (2) phát tri n và hu n luy n ontology b ng phương pháp khai thác kho ng li u s n có và phương pháp rút trích d li u t WordNet; (3) ñ xu t phương pháp hoàn thi n và m r ng truy v n. Ph n th c nghi m c a lu n án ñư c ti n hành cho ngôn ng ti ng Anh d a trên ngu n d li u và truy v n ti ng Anh t ngu n TREC (Text REtrieval Conference) trong m t s lĩnh v c. Các k t qu th c nghi m ph n ánh tính kh thi c a nh ng phương pháp ñ xu t trong lu n án, ñ ng th i cho th y nhi u tri n v ng phát tri n c a các ñ xu t lý thuy t trong lu n án.
i M CL C M CL C ..................................................................................................................... i DANH M C CÁC B NG ............................................................................................... iii DANH M C CÁC HÌNH ..................................................................................................v DANH M C CÁC GI I THU T ................................................................................. vii DANH M C CÁC T VI T T T............................................................................... viii Chương 1 GI I THI U ..............................................................................................1 1.1 Đ ng cơ nghiên c u .............................................................................................1 1.2 M c tiêu và ph m vi nghiên c u .........................................................................5 1.3 Đóng góp chính c a lu n án ................................................................................8 1.4 C u trúc c a lu n án...........................................................................................10 1.5 Các quy ư c .......................................................................................................13 1.6 Tóm t t n i dung lu n án ...................................................................................13 Chương 2 CÁC NGHIÊN C U LIÊN QUAN ........................................................14 2.1 Gi i thi u ...........................................................................................................14 2.2 Các nghiên c u liên quan trong nư c ................................................................15 2.3 Các nghiên c u v ontology ..............................................................................19 2.4 Các nghiên c u v m r ng truy v n .................................................................23 2.5 Khai thác d li u t WordNet ............................................................................39 2.6 Tóm lư c ............................................................................................................44 Chương 3 XÂY D NG N N T NG H TH NG .................................................46 3.1 Gi i thi u ...........................................................................................................46 3.2 Bài toán Xây d ng ontology và bài toán Hoàn ch nh m r ng truy v n ...........46 3.3 Các mô hình cho bài toán m r ng truy v n ......................................................60 3.4 M u nh n d ng c m danh t ..............................................................................65 3.5 Phương pháp th c nghi m và ñánh giá ..............................................................70 3.6 Ngu n d li u th c nghi m ...............................................................................74 3.7 Tóm lư c ............................................................................................................88 Chương 4 XÂY D NG ONTOLOGY OOMP ........................................................90 4.1 Gi i thi u ...........................................................................................................90 4.2 Xây d ng ontology OOMP ................................................................................90 4.3 Phương pháp hu n luy n d a trên kho ng li u ................................................95 4.4 Phương pháp hu n luy n d a trên WordNet ...................................................100 4.5 Cơ ch t hu n luy n c a ontology OOMP .....................................................107 4.6 Các ng d ng c a ontology và quan h ...........................................................109 4.7 Tóm lư c ..........................................................................................................110 Chương 5 HOÀN CH NH VÀ RÚT G N TRUY V N.......................................112 5.1 Gi i thi u .........................................................................................................112
ii 5.2 Hoàn ch nh và rút g n truy v n .......................................................................113 5.3 Ki m tra c m danh t hoàn ch nh ....................................................................114 5.4 T o c m danh t hoàn ch nh............................................................................121 5.5 T o c m danh t rút g n ..................................................................................122 5.6 Hoàn ch nh c m danh t ..................................................................................123 5.7 Gi i thu t rút g n thành ph n c m danh t ......................................................135 5.8 Tóm lư c ..........................................................................................................140 Chương 6 M R NG TRUY V N........................................................................142 6.1 M r ng truy v n cho ñ ng cơ tìm ki m trên Web .........................................142 6.2 M r ng truy v n cho h th ng truy xu t thông tin có s n ..............................153 6.3 Tóm lư c ..........................................................................................................165 Chương 7 K T LU N .............................................................................................167 7.1 Các k t qu ñ t ñư c........................................................................................167 7.2 Hư ng phát tri n ..............................................................................................171 7.3 L i k t ..............................................................................................................172 CÁC CÔNG TRÌNH KHOA H C C A TÁC GI ...................................................174 TÀI LI U THAM KH O .............................................................................................177 Ph l c A. Tóm lư c v WordNet ...............................................................................a Ph l c B. C u trúc c m danh t ti ng Anh .............................................................. c Ph l c C. Danh m c t lo i ti ng Anh ......................................................................g Ph l c D. Danh m c lu t sinh d ng c m danh t c a văn ph m ti ng Anh xây d ng d a trên TreeBank ................................................................................................... i Ph l c E. Tính ch t nh-t o nh trong toán h c .....................................................o Ph l c F. C u trúc ñ nh d ng tài li u TREC .......................................................... p Ph l c G. T ch c cơ s d li u c a th c nghi m trong lu n án ........................... s
iii DANH M C CÁC B NG B ng 3.1. Danh sách mã l i quy ư c ................................................................................... 57 B ng 3.2. Các trư ng h p liên k t gi a q và q’ ñ tính ℘(q | q' ) ...................................... 63 B ng 3.3. Các trư ng h p liên k t gi a q và q’ ñ tính ℘(q' ) ............................................ 63 B ng 3.4.T p lu t sinh ti ng Anh liên quan c m danh t (ngu n [2]) ................................ 67 B ng 3.5. Danh sách m u cơ b n ñ c t c m danh t ......................................................... 68 B ng 3.6. Th ng kê thành ph n d li u t TREC ............................................................... 76 B ng 3.7. Danh sách t p ch m c xây d ng t ngu n d li u trong b ng 3.6 ..................... 78 B ng 3.8. Th ng kê m c t , tài li u và liên k t c a ngu n d li u ..................................... 79 B ng 3.9. Th ng kê các tài li u liên quan theo ngu n d li u............................................. 81 B ng 3.10. Danh sách m u s d ng trong th c nghi m ...................................................... 83 B ng 3.11. Th ng kê c m danh t phân bi t rút trích t kho ng li u ti ng Anh ............... 84 B ng 4.1. Th ng kê s lư ng c m danh t theo d ng m u ................................................. 98 B ng 4.2. D li u d tuy n rút trích ñư c trong gi i thu t CB-KBT .................................. 99 B ng 4.3. D li u d tuy n rút trích ñư c trong gi i thu t CB-KBT .................................. 99 B ng 4.4. Các th ng kê cho d li u hu n luy n ................................................................ 100 B ng 4.5. Danh m c phân l p t v ng s d ng trong WordNet ....................................... 105 B ng 4.6.Th ng kê các m c t dùng trong quá trình hu n luy n WB-BKT ..................... 106 B ng 4.7. D li u ñư c rút trích t WordNet trong gi i thu t WB-KBT .......................... 106 B ng 4.8. Các th ng kê cho d li u hu n luy n ................................................................ 106 B ng 4.9. D li u b sung t o b i gi i thu t A-KBT ........................................................ 108 B ng 5.1. Th ng kê v th i gian th c thi c a gi i thu t CNPV ........................................ 117 B ng 5.2. Các trư ng h p x lý trong gi i thu t CNPV theo d ng l i .............................. 117 B ng 5.3. Các trư ng h p x lý trong gi i thu t CNPV theo d ng l i và m u ................. 118 B ng 5.4. S li u th ng kê các ph n t phân tích trung gian ............................................ 120 B ng 5.5. Th ng kê v th i gian th c thi c a gi i thu t NPC ........................................... 129 B ng 5.6. Th ng kê các trư ng h p x lý trong gi i thu t NPC theo d ng l i ................. 130 B ng 5.7. Th ng kê các trư ng h p x lý trong gi i thu t NPC theo d ng m u............... 130 B ng 5.8. Th ng kê các ph n t phân tích trung gian c a gi i thu t NPC ........................ 131
iv B ng 5.9. K t qu th c nghi m c a gi i thu t CNPG trên d li u trung gian c a gi i thu t NPC .................................................................................................................................... 131 B ng 5.10. Phân tích k t qu th c nghi m c a gi i thu t NPC ......................................... 133 B ng 5.11. So sánh k t qu c a phương pháp tìm ki m thô và NPC ................................ 134 B ng 5.12. Th ng kê v th i gian th c thi c a gi i thu t NPMR...................................... 137 B ng 5.13. Th ng kê các ph n t phân tích trung gian c a gi i thu t NPMR .................. 137 B ng 5.14. K t qu th c nghi m c a gi i thu t RNPG trên d li u trung gian c a gi i thu t NPMR ................................................................................................................................ 137 B ng 5.15. Phân tích k t qu th c nghi m c a gi i thu t NPMR ..................................... 139 B ng 5.16. So sánh k t qu c a phương pháp tìm ki m thô và NPMR............................. 140 B ng 6.1. Th ng kê v th i gian th c thi c a gi i thu t SNPE ......................................... 148 B ng 6.2. Th ng kê các trư ng h p x lý trong gi i thu t SNPE theo d ng l i ............... 148 B ng 6.3. Th ng kê các ph n t phân tích trung gian c a gi i thu t SNPE ...................... 149 B ng 6.4. K t qu th c nghi m c a gi i thu t CNPG trên d li u trung gian c a gi i thu t SNPE.................................................................................................................................. 149 B ng 6.5. Phân tích k t qu th c nghi m c a gi i thu t SNPE ......................................... 151 B ng 6.6. So sánh k t qu c a phương pháp tìm ki m thô và SNPE ................................ 153 B ng 6.7. Th ng kê s li u th c nghi m trong gi i thu t SIC........................................... 160 B ng 6.8. S li u chi ti t c a t p si_TermLink t o ra t gi i thu t SIC ............................ 161 B ng 6.9. Th ng kê k t qu trong t p si_TermLink t o ra t gi i thu t SIC .................... 161 B ng 6.10. So sánh k t qu th c nghi m 1 ........................................................................ 163 B ng 6.11. So sánh k t qu th c nghi m 2 ........................................................................ 164 B ng 6.12. So sánh k t qu th c nghi m 3 ........................................................................ 165
v DANH M C CÁC HÌNH Hình 1.1. M i quan h gi a mô hình c a lu n án và h th ng truy xu t thông tin ............... 6 Hình 1.2. Tóm t t phân b n i dung các v n ñ trình bày trong lu n án ............................. 13 Hình 2.1. T ch c h th ng WordNet phiên b n 3.0 (*) ..................................................... 41 Hình 2.2. C u trúc ontology v hình nh c a S.Zinger ....................................................... 43 Hình 2.3. Đ th quan h ng nghĩa c a Boris .................................................................... 43 Hình 3.1. Quan h k t h p OMP ......................................................................................... 55 Hình 3.2. Ví d v cây phân tích (hình b) ñư c xây d ng t quan h ROMP (hình a) .......... 56 Hình 3.3. Đ th ng nghĩa G có phân l p ........................................................................... 59 Hình 3.4. T ch c phân c p các mô hình ............................................................................ 61 Hình 3.5. Ví d v ñ c t các m u trong JAPE ................................................................... 70 Hình 3.6. T l phân b các m c tài li u .............................................................................. 76 Hình 3.7. Cài ñ t ch c năng xây d ng ch m c cho d li u d ng XML ............................. 77 Hình 3.8. T ch c lưu tr v t lý c a các t p ch m c .......................................................... 78 Hình 3.9. T ch c cơ s d li u lưu tr thông tin c a các ch m c ..................................... 79 Hình 3.10. Cài ñ t ch c năng n p d li u ch m c vào cơ s d li u ................................. 80 Hình 3.11. Th ng kê s lư ng tài li u liên quan xác ñ nh ñư c .......................................... 81 Hình 3.12. T l tài li u liên quan xác ñ nh ñư c ................................................................ 82 Hình 3.13. Th ng kê t p m u s d ng trong th c nghi m .................................................. 82 Hình 3.14. T l ch n l c c m danh t h p l theo chi u dài c m danh t ......................... 85 Hình 3.15. K t qu rút trích c m danh t h p l trong hu n luy n ..................................... 85 Hình 3.16. T ch c lưu tr c m danh t rút trích t các ngu n d li u .............................. 86 Hình 3.17. Phân b c m danh t trong t p TRAINING_DATA theo d ng m u ................ 86 Hình 3.18. Phân b c m danh t trong t p TEST_DATA theo các nhóm m u .................. 87 Hình 4.1. C u trúc m c lu n lý c a ontology OOMP ......................................................... 91 Hình 4.2. C u trúc ontology OOMP v t ch c cơ s d li u quan h ............................... 91 Hình 4.3. Đ c t lu n lý cho c u trúc ontology OOMP ....................................................... 92 Hình 4.4. Các phương pháp hu n luy n ontology OOMP ................................................... 95 Hình 4.5. Phương pháp hu n luy n d a trên kho ng li u .................................................. 95 Hình 4.6. Quan h Rm ñư c xây d ng t quan h holonymy trong WordNet ................... 101
vi Hình 4.7. Quan h Rm ñư c xây d ng t quan h meronymy trong WordNet .................. 101 Hình 4.8. Quan h Rp ñư c xây d ng t quan h attribute trong WordNet....................... 101 Hình 4.9. Quan h Rm ñư c xây d ng t quan h similar trong WordNet ........................ 101 Hình 4.10. Quan h Rm và Rp ñư c xây d ng t quan h similar trong WordNet ............ 102 Hình 4.11. Quan h Rp ñư c xây d ng t quan h similar trong WordNet ....................... 102 Hình 4.12. T ch c d li u c a WordNet phiên b n 3.0 ................................................... 104 Hình 4.13. Th ng kê s lư ng các quan h trong WordNet .............................................. 104 Hình 5.1. Mô hình h th ng hoàn ch nh và rút g n truy v n ............................................. 113 Hình 5.2. Các trư ng h p x lý trong gi i thu t CNPV theo d ng l i và m u ................. 120 Hình 5.3. Th ng kê các trư ng h p x lý theo d ng l i m c chi ti t ............................. 129 Hình 5.4. Cài ñ t ch c năng tìm ki m cho truy v n sinh t gi i thu t NPC ..................... 132 Hình 5.5. Th ng kê s li u các ñ ño theo ngu n d li u ................................................. 132 Hình 5.6. Th ng kê s lư ng k t qu th c nghi m theo ngu n d li u............................. 133 Hình 5.7. Cài ñ t ch c năng tìm ki m cho truy v n sinh t gi i thu t NPMR .................. 138 Hình 5.8. Th ng kê s li u các ñ ño theo ngu n d li u ................................................. 139 Hình 5.9. Th ng kê s lư ng k t qu th c nghi m theo ngu n d li u............................. 140 Hình 6.1. Mô hình h th ng m r ng truy v n v i ñ ng cơ tìm ki m thông tin ............... 143 Hình 6.2. Cài ñ t ch c năng tìm ki m cho truy v n sinh t gi i thu t SNPE ................... 150 Hình 6.3. Th ng kê s lư ng k t qu th c nghi m theo ngu n d li u............................. 152 Hình 6.4. Th ng kê s li u các ñ ño theo ngu n d li u ................................................. 152 Hình 6.5. Minh h a tính ch t (6.1) .................................................................................... 154 Hình 6.6. ng d ng tính ch t (6.1) vào m r ng k t qu tìm ki m .................................. 155 Hình 6.7. Mô hình h th ng m r ng truy v n k t h p h th ng truy xu t thông tin d ng s n ...................................................................................................................................... 155 Hình 6.8. Mô hình t ch c ch m c hư ng ng nghĩa ....................................................... 156 Hình 6.9. So sánh s liên k t t o thành theo ngu n d li u............................................... 162 Hình 6.10. So sánh t l liên k t t o thành theo ngu n d li u .......................................... 162 Hình 7.1. Phương pháp th c hi n c a v n ñ 4 ................................................................. 172
vii DANH M C CÁC GI I THU T Gi i thu t 4.1. Hu n luy n ontology d a trên kho ng li u .......................................... 96 Gi i thu t 4.2. Hu n luy n ontology d a trên WordNet .............................................. 103 Gi i thu t 4.3. Hu n luy n ontology t ñ ng ................................................................ 107 Gi i thu t 5.1. Ki m tra c m danh t hoàn ch nh ........................................................ 114 Gi i thu t 5.2. T o c m danh t hoàn ch nh................................................................. 121 Gi i thu t 5.3. T o c m danh t rút g n ....................................................................... 122 Gi i thu t 5.4. Hoàn ch nh c m danh t ....................................................................... 123 Gi i thu t 5.5. Rút g n thành ph n c m danh t ......................................................... 135 Gi i thu t 6.1. M r ng c m danh t tương ñương ..................................................... 144 Gi i thu t 6.2. T o ch m c hư ng ng nghĩa............................................................... 157 Gi i thu t 6.3. Tìm ki m k t h p ................................................................................... 158
viii DANH M C CÁC T VI T T T STT T vi t t t Di n gi i ti ng Anh Di n gi i ti ng Vi t 1 A-KBT Auto Knowledge Base Hu n luy n ontology t ñ ng Training 2 CB-KBT Corpus-Based Knowledge Hu n luy n ontology d a trên kho Base Training ng li u 3 CL Concept Lattice Lư i khái ni m 4 CLIR Cross-Language Truy xu t thông tin xuyên ngôn ng Information Retrieval 5 CNPV Complete Noun Phrase Ki m tra tính hoàn ch nh c a c m Verification danh t 6 CREOLE Collection of REusable T p ñ i tư ng kh tái s d ng cho Object for Language ñ ng cơ ngôn ng Engineering 7 DC Dice Coefficient H s kh i 8 EEM External Expansion Model Mô hình m r ng ngo i vi 9 FCA Formal Concept Analysis Phân tích Khái ni m Chính quy 10 GATE General Architecture for Ki n trúc t ng quát cho ñ ng cơ Text Engineering văn b n 11 HS Hybrid Search Tìm ki m k t h p 12 IDF Inverse-Document T n su t ngh ch ñ o tài li u Frequency 13 IR Information Retrieval Truy xu t thông tin 14 ISE Internal Search Engine Đ ng cơ tìm ki m thông tin c c b 15 JAPE Java Annotation Patterns Đ ng cơ m u chú gi i Java Engine 16 MAP Mean Average Precision Đ chính xác trung bình bình quân 17 NPC Noun Phrase Completion Hoàn ch nh thành ph n c m danh t 18 NPRM Noun Phrase Member Rút g n thành ph n c m danh t Reduction 19 OMP Object-Member-Property Đ i tư ng-Thành ph n-Tính ch t 20 OOMP Ontology of Object- Cơ s tri th c c a Đ i tư ng-Thành Member-Property ph n-Tính ch t 21 QEM Query Expansion Model Mô hình m r ng truy v n 22 SIC Semantic Index Creation T o ch m c hư ng ng nghĩa 23 SNPE Similar Noun Phrase M r ng c m danh t tương ñương Expansion 24 TREC Text REtrieval Conference H i ngh v Truy xu t văn b n 25 WB-KBT WordNet-Based Knowledge Hu n luy n ontology d a trên Base Training WordNet
1 Chương 1 GI I THI U 1.1 Đ ng cơ nghiên c u Như chúng ta ñã bi t, internet (web)a ñư c xem là ngu n thông tin kh ng l c a nhân lo i. Theo th i gian, ngu n thông tin này không ng ng ñư c chia s , m r ng và phát tri n. Các thông tin trên Web h u h t ñư c th hi n d ng văn b n bi u di n b i ngôn ng t nhiên, trong ñó ph n l n là thông qua các trang Web, thư ng ch phù h p v i kh năng ñ c hi u c a ngư i s d ng. Đ ng th i v i s phát tri n c a Web là s gia tăng r t l n v nhu c u truy xu t thông tin c a ngư i s d ng, trong ñó vi c tìm ki m các thông tin th hi n trong ngôn ng ti ng Anh chi m t l ñáng k . Đ c bi t trong nh ng năm g n ñây, nhu c u truy c p tin t c trên Web c a ngư i dân Vi t nam r t cao (theo [4], giai ño n 1997-2007 internet Vi t Nam ñã liên t c phát tri n v i kho ng 18 tri u ngư i tham gia s d ng, tương ñương 21% dân s ) xu t phát t các nhu c u ch y u như xem tin t c, trao ñ i thông tin, và ñ c bi t s lư ng r t l n là tác v tìm ki m thông tin c n thi t. Đ ph c v cho nh ng nhu c u tìm ki m thông tin c a ngư i s d ng, các h th ng truy xu t thông tin (IR) ñã ñư c nghiên c u và phát tri n, trong ñó thành công nh t là m t s ñ ng cơ tìm ki m (search engine) n i ti ng như Google [148] – Yahoo [165] – Alta Vista [145] và Bing [152] trong th i gian g n ñây... Tuy nhiên, thông qua các h th ng ñó, vi c tìm ki m thông tin thư ng không nh n ñư c ñ y ñ a internet còn ñư c g i là World Wide Web, vi t g n là WWW hay Web
2 k t qu c n thi t như mong mu n cũng như hi u su t c a chúng còn có m t s gi i h n nh t ñ nh. Nguyên nhân ch y u nh hư ng ñ n v n ñ này là: − Ng nghĩa c a tài li u b m t ñi do cách bi u di n truy v n dư i d ng m t t p các t khóa. − Yêu c u thông tin (truy v n) c a ngư i s d ng thư ng ch bao g m m t vài t khóa c t lõi, không th hi n ñ ng nghĩa c n thi t. − Ngư i s d ng không cung c p ñ thông tin truy v n c n thi t cho ñ ng cơ tìm ki m. − Đ ng cơ tìm ki m thông tin ho t ñ ng d a trên cơ ch so trùng t khóa và chưa quan tâm ñúng m c ñ n y u t ng nghĩa trong tương tác và h tr ngư i dùng. − Các ñ ng cơ tìm ki m hi n có thư ng h tr chính cho ti ng Anh, nhưng thi u công c tr giúp cho ngôn ng khác … Đi u này d n ñ n tình tr ng: − Ngư i s d ng ph i dành m t lư ng th i gian khá l n ñ ñ c hi u và ch n l c l i các thông tin ñ có nh ng k t qu mong mu n. − Ngư i s d ng g p khó khăn trong vi c di n ñ t n i dung c a v n ñ c n tìm. − Ngư i s d ng không nh n ñư c m t k t qu tr l i tr n v n hoàn ch nh (dù ch c n m c tóm lư c ng n g n) như mong mu n v m t v n ñ c n tìm. − Thi u m t h th ng tìm ki m thông tin nhanh và linh ho t ñ không ch có th tìm các thông tin trong tài li u ti ng Anh (như truy n th ng) và ti ng Vi t theo cơ ch so trùng t khóa, mà còn có th tr l i các câu h i c a ngư i s d ng (trong ph m vi xác ñ nh cho ti ng Vi t). − H th ng chưa th c s ñ m nh ñ nh n bi t ng nghĩa c a truy v n.
3 T các phân tích trên, chúng ta nh n th y nguyên nhân chính là các h th ng tìm ki m thông tin chưa ñ m nh nên k t qu ñưa ra không th h tr ngư i dùng như mong ñ i. Truy v n c a ngư i dùng cũng chưa ph n ánh ñ y ñ ng nghĩa ñ h tr cho các quá trình tìm ki m và truy xu t thông tin ñư c t t hơn. Vì v y, vi c b sung ng nghĩa vào truy v n ban ñ u c a ngư i dùng là yêu c u c n thi t. M t bài toán kinh ñi n trong lĩnh v c Truy xu t thông tin là M r ng truy v n. Đó là quá trình b sung m t s t vào truy v n c a ngư i dùng nh m t o ra các truy v n m i tương ñ ng ng nghĩa. Bài toán này là v n ñ ñư c quan tâm vì nó có th lo i b nh p nh ng ng nghĩa c a truy v n trong ngôn ng t nhiên, cũng như kh c ph c nh ng h n ch c a vi c s d ng t khóa ñ th hi n m t khái ni m thông tin. Krovetz và Croft [109] ñã quan sát th y ph n l n các l i ích thu ñư c trong vi c tìm ki m thông tin có ñ truy h i cao ph thu c vào vi c so trùng các t khóa. Đ i v i vi c m r ng truy v n, h th ng xác ñ nh ng nghĩa truy v n ñư c chính xác hơn, ñi u ñó cho phép k t qu truy v n t t hơn. Thông qua k t qu truy v n m r ng, ngư i dùng có th h c t p cách phát bi u truy v n rõ ràng và chính xác hơn ñ thu ñư c các k t qu h u ích. T m t truy v n c a ngư i dùng, m r ng truy v n s b sung vào ñó m t s t hay thu t ng liên quan và t o ra d ng truy v n m i có th bao ph thông tin r ng hơn. Như v y, tài li u mong ñ i ñ thu nh n s nhi u hơn d n ñ n t l bao ph thông tin tăng lên tương ng. Quá trình thêm nh ng thu t ng này có th th c hi n b ng tay, t ñ ng ho c có ngư i dùng tr giúp. Vi c m r ng truy v n b ng tay d a vào s am hi u và thành th o c a con ngư i ñ ñưa ra quy t ñ nh, nh m nhúng các thu t ng vào truy v n m i. Trong trư ng h p m r ng t ñ ng truy v n, các tr ng s ñư c tính cho t t c các thu t ng nh m giúp h th ng thêm nh ng thu t ng có tr ng s cao nh t vào truy v n ban ñ u. Các hàm tính tr ng s khác nhau ñưa ra nh ng k t qu khác nhau, do ñó hi u su t c a vi c truy v n ph thu c vào cách th c tính các tr ng s . V i d ng m r ng truy v n có ngư i dùng tr giúp, h th ng s sinh ra các thu t ng phù h p cho vi c m r ng truy v n và ngư i dùng t ch n m t s trong các thu t ng ñó ñ thêm vào.
4 V n ñ c t lõi c a bài toán m r ng truy v n là xác ñ nh các t thích h p ñ thêm vào truy v n c a ngư i dùng. Nhi u nghiên c u ñư c công b v m r ng truy v n trong ñó hư ng ñ n vi c s d ng thông tin ng c nh ñ xác ñ nh các t c n thêm m t cách h p lý. Thông tin theo ng c nh có th thu ñư c t các thông tin ph n h i liên quan (relevance feedback), t các t ñ ng hi n (co-occurrence term) và trong th i gian g n ñây là t các mô hình tri th c như b n th h c (ontology). Hi n nay, thông tin liên quan ng c nh c a truy v n là m t v n ñ ñang ñư c các nhà nghiên c u khai thác nh m c i ti n quá trình truy xu t thông tin. Theo Finkelstein [92] ng c nh chưa có ñ nh nghĩa chu n xác, nhưng theo [124] thì có hai ñ nh nghĩa v ng c nh. Đ nh nghĩa th nh t theo ngôn ng h c “ng c nh là các ph n c a bài lu n bao quanh t hay ño n văn và có th làm sáng t nghĩa c a nó”b. Đ nh nghĩa th hai d a trên tình hu ng “các ñi u ki n tương quan trong ñó m t ñi u gì ñó t n t i hay x y ra”c . T ñó, m t nh n ñ nh chung là thông qua tương tác c a ngư i dùng lên h th ng truy xu t thông tin, ng c nh tương ng s bao g m nh ng thông tin liên quan ñ n nh ng hành ñ ng, nh ng quy t ñ nh c a ngư i dùng. Ng c nh trong truy xu t thông tin bao g m nhi u v n ñ trong ñó có m r ng truy v n. M t khó khăn là làm sao bi u di n ñư c nghĩa c a truy v n b ng các thu t ng (term) m t cách chính xác. Do v y, m r ng truy v n cho phép ngư i dùng th c hi n tìm ki m thông tin b ng truy v n m i có các thu t ng là s bi n ñ i hình thái c a thu t ng ban ñ u và (ho c) m t s thu t ng m i ñư c thêm vào truy v n nh k t qu kh nh p nh ng nghĩa c a truy v n ban ñ u. Nhi u phương pháp ti p c n khác nhau ñư c ñ xu t hư ng ñ n vi c m r ng truy v n. Trong ñó, có nhi u nghiên c u hư ng ñ n vi c s d ng ontology ñ h tr suy lu n ng c nh cho các truy v n nh p nh ng. Các khái ni m trong ontology ñư c dùng ñ kh nh p nh ng ng nghĩa c a t và h tr ñ m r ng truy v n. Vi c m r ng truy v n ñ t thành công m t m c ñ nh t ñ nh nhưng v n còn nhi u v n ñ c n c i thi n v k b Nguyên văn: “the parts of a discourse that surround a word or passage and can throw light on its meaning” c Nguyên văn: “the interrelated conditions in which something exists or occurs”
5 thu t, giao di n ho c gi i thu t ñ xác ñ nh ng nghĩa m t cách chính xác hơn t ñó c i ti n k t qu truy v n. T t m quan tr ng v tính hi u qu c a quá trình truy xu t thông tin (trên internet), cùng v i hư ng gi i quy t làm sao ñ h th ng IR có th hi u nhi u hơn và thông minh hơn khi x lý truy v n ban ñ u c a ngư i dùng, thì yêu c u v m t h th ng truy xu t thông tin có kh năng t o ra nh ng truy v n tương ñ ng ho c cùng m c tiêu là bài toán quan tr ng. Do ñó, thông qua nh ng kh o sát phân tích nêu trên, v n ñ m r ng truy v n là bài toán quan tr ng mà lu n án này nghiên c u và ñ xu t phương pháp gi i quy t. 1.2 M c tiêu và ph m vi nghiên c u T ñ ng cơ nghiên c u nêu trên, lu n án ñ xu t m t s phương pháp m r ng truy v n ban ñ u c a ngư i dùng. Đây là v n ñ c t lõi và ñ ng th i là m c tiêu nghiên c u c a lu n án. Hi n nay trên th gi i nhi u phương pháp ti p c n bài toán m r ng truy v n trên cơ s s d ng cơ s tri th c ñã ñư c công b như: − M r ng truy v n s d ng cơ s tri th c có tương tác kho ng li u (công trình [11] [22] [60] [86] [61] [102] [106] [116] [137] và [141] ...) − M r ng truy v n s d ng các cơ s tri th c không tương tác kho ng li u (công trình [29] [53] [54] [56] [59] [66] [76] [89] [92] [110] [136] …) M i phương pháp ñ u có ưu, như c ñi m cùng v i nh ng công trình nghiên c u và các th c nghi m liên quan. T vi c kh o sát phân tích nh ng phương pháp này (xem chương 2), d a trên nh ng gi i pháp kh thi ñã ñư c công b trên th gi i, hư ng ti p c n chính c a lu n án là m r ng truy v n s d ng cơ s tri th c không tương tác kho ng li u. Đ lu n án mang tính kh thi c v lý thuy t l n th c ti n và mang l i k t qu như mong mu n, tác gi ñã th c hi n:
6 (a) Nghiên c u và phát tri n cơ s lý thuy t c a phương pháp ti p c n m i cho vi c m r ng truy v n, trên cơ s k t h p v i ontologyd. (b) Nghiên c u và phát tri n c u trúc t ch c ontology cùng gi i pháp hu n luy n t o d li u ban ñ u nh m ki m ch ng k t qu nghiên c u (a) và có th tri n khai trong th c t ñ mang l i k t qu truy xu t thông tin t t hơn. Như ñ nh hư ng nêu trên, ph m vi nghiên c u c a lu n án ñư c th hi n trong hình 1.1 (trong khung ñư ng g ch ñ t nét). (A) (B) Nh p: Xu t: B x lý Đ ng cơ Câu truy v n m r ng Các câu truy tìm ki m d ng c m truy v n v n: thông tin danh t trên cơ s - d ng c m k th pv i danh t , ontology - ñã ñư c m r ng có d ng K t qu tr truy v n hoàn v (t p tài ch nh. li u) (C) Hình 1.1. M i quan h gi a mô hình c a lu n án và h th ng truy xu t thông tin (A) Mô hình x lý c a lu n án (ph m vi nghiên c u c a lu n án) (B) Đ ng cơ tìm ki m thông tin (thu c h th ng truy xu t thông tin) (C) K t qu tìm ki m thông tin t yêu c u c a các câu truy v n ñã m r ng V i mô hình ñư c mô t hình 1.1, trong m c (A), câu truy v n nh p (d ng c m danh t bao g m các thành ph n là tính t hay ch có danh t ñơn) ñư c x lý ñ tr v t p các câu truy v n ñã ñư c m r ng (c m danh t có d ng truy v n hoàn ch nhe). Trong ph m vi lu n án, d a trên gi i pháp rút trích các t ñ c trưng c t lõi d Khái ni m ontology còn ñư c di n d ch là “cây ph h tri th c” hay “cơ s tri th c” e Tham kh o thêm ñ nh nghĩa 3.10-Truy v n hoàn ch nh, m c 3.2.6, chương 3.
7 cho m t câu ([23] [149]), câu truy v n ban ñ u c a ngư i dùng ñư c ti n x lý ñ lo i b các thành ph n không quan tr ng nh m gi l i nh ng thành ph n chính th a ñi u ki n truy v n hoàn ch nh. Đi u ñó s giúp gi m ñư c ñ ph c t p hay d ng bi u di n ph c h p c a truy v n, ñ ng th i còn giúp ñ m b o tính duy nh t c a t ng thành ph n trong truy v n th a ñi u ki n truy v n hoàn ch nh. M c (B) c a hình trên g m ñ ng cơ tìm ki m thông tin (search engine). Đây là m t b ph n quan tr ng c a h th ng Truy xu t Thông tin (Information Retrieval). Đ ng cơ tìm ki m thông tin gi i quy t ba v n ñ c t lõi là mô hình bi u di n văn b n, thu t toán tìm ki m so trùng t khóa - ñ i sánh ng nghĩa tương ng v i các truy v n và cơ ch l c k t qu truy xu t. Hi n t i trên th gi i có nh ng ñ ng cơ tìm ki m thông tin n i ti ng như Google, Yahoo, Microsoft Bing … Tuy nhiên, nghiên c u c a lu n án ch s d ng nh ng ñ ng cơ này như m t công c h tr vi c tìm ki m thông tin cho truy v n ñã m r ng b ng phương pháp x lý c a lu n án và không ñ t m c tiêu nghiên c u ba v n ñ nêu trên. Vì v y lu n án ñã không trình bày ba v n ñ này. Mô hình x lý c a lu n án (trong m c (A)) ch th c hi n vi c m r ng n i dung c a truy v n nh p nên hoàn toàn không làm nh hư ng ñ n ba khía c nh nêu trên trong quá trình v n hành c a ñ ng cơ tìm ki m m c (B). Đi u này còn cho th y ph m vi nghiên c u c a lu n án hư ng ñ n bài toán m r ng truy v n d a trên ontology và hoàn toàn khác bi t so v i ba khía c nh ñã nêu. T nh ng trình bày trên, các bài toán chính c n gi i quy t trong ph m vi lu n án bao g m: Bài toán 1 - Xây d ng ontology OOMP Nghiên c u và phát tri n c u trúc ontology OOMP (Ontology of Object- Member-Property) cùng cơ ch hu n luy n d li u. D a trên t p tài li u ti ng Anhf t ngu n TREC và khai thác d li u t WordNet ñ hu n luy n d li u ontology OOMP nh m ph c v yêu c u c a bài toán 2. N u bài toán 1 ñư c gi i quy t thành f Tham kh o ph n gi i thi u c a chương 4 v lý do s d ng ngu n tài li u ti ng Anh trong th c nghi m.