Luận văn Phương pháp học bán giám sát cho bài toán trích chọn thông tin và ứng dụng trích chọn thực thể tên máy ảnh số

ể kiểm tra xem chúng có thể trích chọn ra được các hạt giống mới nào không; nếu cặp chưa có trong tập quan hệ đích thì thêm cặp hạt giống mới này vào tập quan hệ đích R, coi đây là quan hệ hạt giống sử dụng cho các vòng lặp tiếp theo.  Bước 4: Quay lại bước 2 để tìm ra những hạt giống và mẫu mới cho tới khi số lượng tập quan hệ R gần như không thay đổi, hay số lượng các cặp quan hệ mới phát hiện ra thêm là rất ít. Bài toán mà luận văn đề cập đến là trích chọn cặp quan hệ tên máy ảnh – nhà sản xuất, với mỗi loại máy ảnh sẽ có một hãng sản xuất ra nó. Do vậy cách biểu diễn nó trên tài liệu sẽ có một quy luật nào đó. Nhận thấy rằng, ngữ cảnh ở giữa cặp thực thể tên máy ảnh số và nhà sản xuất thường ở một dạng nhất định, quy luật có thể lặp lại nhiều lần ở các tài liệu khác nhau. Ví dụ như: “Sony has announced the SLT A35, the latest addition to its innovative range of fixed-mirror DSLRs”, “Panasonic has announced the DMC-G3 Micro Four Thirds mirrorless interchangeable lens camera”. Cấu trúc “has announced the” có xu hướng xuất hiện nhiều lần trong các bài báo giới thiệu về các loại máy ảnh. Do đó mẫu này có khả năng dẫn đến các trích dẫn khác như: “Pentax has announced the Optio RS1500 compact camera with interchangeable, user designable covers” hay “Samsung has announced the ST93 compact camera”… Từ các cặp quan hệ mới này, ta có thể sử dụng để sinh ra các mẫu trích chọn mới. Và có một đặc điểm thuận lợi nữa để giải quyết bài toán đã đề xuất là tên các loại máy ảnh thường ở dạng kí tự in hoa, có thể bao gồm cả chữ và số; tập các hãng sản xuất máy ảnh là hữu hạn, ta có thể liệt kê một cách dễ dàng. Trong bài toán trích chọn tên máy ảnh số:  Bộ quan hệ: cặp  Một mẫu là bộ - 4: (order, tag1, middle, tag2); trong đó tag1 và tag2 là thực thể và . Order là thứ tự xuất hiện của tag1và tag2 trong câu. Middle là ngữ cảnh ở giữa giới hạn bởi tag1và tag2.  Một bộ quan hệ sẽ được trích chọn vào bảng quan hệ đích nếu có một thể hiện trong văn bản phù hợp với một trong hai biểu thức: camera middle producer hoặc producer middle camera 35 3.3. Mô hình hệ thống Hình 9: Mô hình hệ thống trích chọn tên máy ảnh số Xuất phát từ tập tài liệu HTML, sau pha tiền xử lí, ta sẽ thu được tập các câu chứa tên các hãng sản xuất máy ảnh, việc trích chọn sẽ sử dụng tập các câu này. Dựa vào 5 quan hệ hạt giống ban đầu, hệ thống sẽ tiến hành tìm kiếm các câu chứa đồng thời tên hãng sản xuất và tên máy ảnh trong bộ quan hệ hạt giống, phân tích ngữ cảnh xung quanh các bộ quan hệ, sinh ra các mẫu, dựa vào các mẫu này, hệ thống sẽ sinh ra được các bộ quan hệ mới, đưa vào bảng quan hệ đích. Bảng quan hệ đích này lại trở thành bảng quan hệ hạt giống mới, và quá trình trích chọn lại bắt đầu ở vòng lặp mới. Mỗi vòng lặp luôn có sự đánh giá các mẫu được sinh ra để việc trích chọn ra các bộ quan hệ mới càng nhiều cáng tốt và phải bảo đảm sự chính xác cao. Quá trình trích chọn sẽ dừng lại khi không có một bộ quan hệ mới nào được sinh ra. Chi tiết mô hình hệ thống được mô tả trong hình 9. Tuy nhiên, để việc trích chọn hiệu quả, hệ thống sẽ được tích hợp thêm tập các tri thức của con người, bao gồm 2 bộ từ điển: - Tập tên các hãng sản xuất máy ảnh: P ={Canon, Casio, Concord, Contax, Cool-icam, Creative, Fujifilm, GE, Gateway, HP, Kodak, Konica, Kyocera, Minolta, Mustek, Nikon, Olympus, Panasonic, Pentax, Polaroid, Ricoh, Samsung, Sanyo, Sealife, Sharp, Sigma, Sony, Toshiba} - Tập các thuộc tính liên quan đến tên các nhà sản xuất máy ảnh: {PowerShot, EOS, Exilim, Optio, Lumix, Finepix, FineCam, DC-Cam, CoolPix, Tài liệu html Các câu chứa tên các hãng sản xuất máy ảnh Pha sinh các bộ quan hệ mới Tập các thuộc tính đi kèm với tên máy ảnh Pha tiền xử lí Tìm các sự kiện liên quan Pha sinh các mẫu Bảng quan hệ đích <camera, Tập hãng sản xuất máy ảnh 36 Digimax, DSC, Cyber-Shot, DMC, EasyShare, SD, GXR, Alpha, Tough, Stylus, IXUS, DSLR, Mju} 3.3.1. Pha tiền xử lí Hình 10: Mô hình của pha tiền xử lí Trong pha này, nhận đầu vào một tập các trang web trên một miền ứng dụng quan tâm là máy ảnh kĩ thuật số, sau quá trình xử lý hệ thống thu được một tập các câu tiềm năng có thể chứa các quan hệ cần trích chọn, chứa tên các hãng sản xuất máy ảnh đang xem xét. Công việc trích chọn sau này chỉ thực hiện trên tập các câu tiềm năng thu được sau pha này. a. Bước 1: Loại bỏ các thẻ html Trong một trang web, không chỉ chứa nội dung trang web, còn chứa các thông tin khác như dòng quảng cáo, các đường liên kết đến hình ảnh, đến các trang web khác… Tất cả các thông tin đó không phải đều có lợi cho hệ thống trích chọn. Các thông tin này thường được đánh dấu trong các thẻ html. Việc cần làm là loại bỏ các thẻ hmtl, chỉ giữa lại nội dung của các trang web. Nội dung trong các trang web thường được đánh dấu trong cặp thẻ và . Tuy nhiên tiêu đề của các bài báo thường cũng ẩn chứa những thông tin có giá trị, cụ thể trong tiêu đề của các bài báo nói về máy ảnh, thường trong đó chứa cặp quan hệ tên máy ảnh và hãng sản xuất, do đó ngoài việc giữ lại nội dung của trang web, ta cần giữ lại cả tiêu đề của các trang web đó. Đọc từng file có trong tập các trang web, với mỗi file, từng dòng được đọc, nếu dòng đó chứa thẻ bắt đầu bằng thẻ và kết thúc là thẻ hoặc nếu trong dòng văn bản đó chứa thì ghi lại nội dung chứa trong cặp thẻ đó vào file văn bản sau khi đã loại bỏ các dấu \t, chuyển các kí tự html về dạng chuẩn. Giải thuật: Đầu vào: tập các tài liệu HTML Đầu ra: tập tài liệu ở dạng trơn (plain text) B1: Loại bỏ thẻ html B2: Tách câu B3: Loại bỏ các câu không liên quan 37 void StripHTML() for each file_html in corpus_html for each line in file_html if line Contain () { RemoveTag(line); Write(file_text, line); } if (line Contain ()) or (line Contain ()) { RemoveTag(line); Write(file_text, line); } return file_text; b. Bước 2: Tách câu Việc trích chọn các loại tên máy ảnh kĩ thuật số giới hạn trong một câu, có nghĩa nếu tên hãng sản xuất và tên máy ảnh xuất hiện trong cùng một câu thì ta sẽ đưa chúng vào bảng quan hệ đích, và thông thường mỗi câu ta chỉ trích chọn một bộ quan hệ mà thôi. Do đó, khi có một tập các tài liệu, công việc đầu tiên hệ thống cần phải làm là tách các câu trong một đoạn thành các câu đơn lẻ, và việc trích chọn chỉ thực hiện trên từng câu đơn lẻ. Thông thường, trong một đoạn văn bản, các câu thường được ngăn cách bởi một trong các dấu ngắt ‘.’, ‘!’, ‘?’. Nếu chúng ta có một đoạn văn bản đưa vào một biến xâu input, cách đơn giản để cắt chúng thành các câu là ta sẽ sử dụng input.Split(‘.’, ’!’, ’?’), cách này rất hiệu quả với các tài liệu văn bản tiếng Việt. Tuy nhiên với tiếng Anh các dấu ngắt đó có thể đánh dấu kết thúc một câu nhưng cũng có thể xuất hiện giữa câu ví dụ như dấu “.” trong văn bản thường để ngăn cách hàng thập phân trong số thực, ngăn cách địa chỉ IP,... trong khi hệ thống trích chọn đang thực hiện trên tập tài liệu tiếng Anh, do đó việc sử dụng các dấu ngắt và phương thức Split để tách câu không đem lại hiệu quả thực sự. Chẳng hạn như câu: “The Coolpix P80 comes with a 10.1 MP sensor. The camera features an electronic viewfinder to allow accurate composition throughout the zoom range and also includes a large 2.7 inch monitor with anti-reflection coating and a wide viewing angle.” Nếu sử dụng phương thức Split thì kết quả trả về gồm 4 thành phần: 1. The Coolpix P80 comes with a 10 2. 1 MP sensor 38 3. The camera features an electronic viewfinder to allow accurate composition throughout the zoom range and also includes a large 2 4. 7 inch monitor with anti-reflection coating and a wide viewing angle trong khi ta cần đầu ra chỉ gồm có 2 câu: 5. The Coolpix P80 comes with a 10.1 MP sensor 6. The camera features an electronic viewfinder to allow accurate composition throughout the zoom range and also includes a large 2.7 inch monitor with anti- reflection coating and a wide viewing angle Để thực hiện việc này, hệ thống sẽ quét trên toàn bộ đoạn văn bản đầu vào, mỗi khi gặp các kí tự ngắt câu, ta cần quyết định xem liệu chúng có phải đánh dấu điểm kết thúc của câu hay không. Một đặc điểm dễ nhận ra đó là nếu một trong các dấu ‘.’, ‘!’, ‘?’ đánh dấu kết thúc câu thì liền sau chúng là một dấu cách và kí tự tiếp theo phải là một trong các kí tự in hoa. Ta sẽ sử dụng biểu thức quy tắc để tách các câu. "(?<=[A-Za-z0-9][\.\!\?])\s+(?=[A-Z])" Biểu thức này được diễn giải là: bắt bằng một nhóm các kí tự chữ hoa, chữ thường và số, tiếp theo các là kí tự dấu ngắt ‘.’, ‘!’, ‘?’, kết thúc là một dấu cách; nhóm thứ 2 bắt đầu là các kí tự viết hoa từ A đến Z. Biểu thức so khớp tất cả các chuỗi con nào có chứa các dấu ‘.’, ‘!’, ‘?’ và sau nó là một kí tự chữ hoa, nếu so khớp là đúng, kết quả trả về là một chuỗi con từ vị trí đầu câu đến trước dấu. ! hoặc ?. Giải thuật tách câu: Đầu vào: Đoạn văn bản Đầu ra: Danh sách các câu đơn trong đoạn văn bản void SplitSentences(sSourceText) sTemp = sSource Text ; if sTemp Start_with {‘A’..’Z’} and sTemp Contain {‘.’, ‘?’, ‘!’} and Next_Char in {‘A’..’Z’} splitSentences = sTemp.Split(); for each single_sentence in splitSentences { RemoveSpace(single_sentence); return single_sentence; } Để tiết kiệm không gian lưu trữ và thời gian tìm kiếm, hệ thống loại bỏ các từ dừng - những từ xuất hiện thường xuyên trong văn bản mà sự xuất hiện của nó không có ý nghĩa gì trong việc tìm kiếm và trích chọn thông tin. 39 Sau khi tách các câu, hệ thống tiến hành tách các từ trong mỗi câu, với mỗi từ vừa tách, kiểm tra xem từ đó có phải là từ dừng không, nếu đúng loại bỏ từ đó ra khỏi văn bản. Mỗi bài báo thường có những định dạng khác nhau, bài này có từ viết hoa nhưng bài kia thì không, có động từ ở dạng nguyên thể, nhưng cũng động từ đó ở bài báo khác lại ở thì bị động, chẳng hạn như “announces”, “announed”… Đặc biệt liên quan đến tên các hãng sản xuất, tên các thuộc tính kèm theo, ví dụ cặp từ “Panasonics” và “Panasonic”, hoặc “PowerShot” và “powershot” thực chất ý nghĩa của chúng đều giống nhau, nhưng cách viết khác nhau, điều này sẽ gây nhiễu cho quá trình tìm kiếm và kết quả trích chọn thường không chính xác. Hệ thống tiến hành chuyển hóa tất cả các từ trong văn bản thành các kí tự chữ thường, chuyển tất cả các thể hiện về tên máy ảnh, tên thuộc tính kèm theo về một dạng thống nhất chung, chuyển tất cả các động từ ở các thời khác nhau về dạng nguyên thể của nó. Giải thuật chuyển các từ về dạng gốc của nó: Các động từ thường có các dạng: nguyên thể, V_ed, V_ing, V_s - Nếu động từ có dạng V_s: Nếu động từ kết thúc bằng: + “sses”  “ss” caresses  caress + “ies”  “i” nếu trước nó có nhiều hơn 1 kí tự, còn lại ies  ie ties  tie skies  ski + “s”: xóa bỏ “s” nếu kí tự trước nó là một phụ âm rồi kế trước là một nguyên âm caress  caress cats  cat + “ss”, “us”: giữ nguyên - Nếu động từ có dạng V_ed hoặc V_ing: Nếu động từ kết thúc bằng: + “eed”  “ee” agreed  agree + Xóa “ed” hoặc “ing”, và sau khi xóa từ còn lại: +) kết thúc bằng: “at”, “bl”, “iz” thì thêm “e” luxuriaitng  luxuriate +) kết thúc bằng một kí tự kép khác ‘l’, ‘s’, ;z’ thì xóa một kí tự cuối hopping  hop +) là âm tiết ngắn thì thêm “e” hoped  hope 40 Giải thuật chuẩn hóa các từ về dạng gốc: Đầu vào: Một từ Đầu ra: Từ gốc của nó void Stemmer(verb) 1. k = Length(verb); if (verb[k] = ‘s’) { if (verb End_With “sses” ) k = k - 2; else if (verb End_With “ies” ) and (Length(verb) > 4) k = k - 2; else k = k - 1; else if (verb[k-1] != ‘s’) k = k - 1; } 2. if (verb End_With “eed”) k = k - 1; 3. if (verd End_With “ed”) or (verb End_With “ing”) { Remove(verb, “ed”, “ing”); k = Length(verb); if (verb End_With {at”, “bl”, “iz”}) Add(verb, “e”); else if (verb End_With double(k)) { k = k – 1; ch = verb[k]; if (ch in {“l”, “s”, “z”}) k = k + 1; } else if Is_short_word(verb) add(verb, “e”); } 3. return verb; Tuy nhiên dựa vào đặc điểm của một tên máy ảnh, ví dụ có dạng DMC- FX500, thường có dạng một chuỗi kí tự gồm các kí tự chữ cái được viết hoa, kèm theo là các kí tự số. Do đó ta dễ dàng kiểm tra được một xâu có phải là một tên máy ảnh xác định hay không, loại bỏ những trường hợp không thỏa mãn để kết quả trích chọn sẽ chính xác hơn. Nếu ta chuyển toàn bộ các kí tự về dạng chữ thường thì việc kiểm tra một chuỗi có phải là tên máy ảnh hay không sẽ khó khăn hơn, nên việc chuẩn hóa các từ về dạng chữ thường không áp dụng với tên của hãng máy ảnh, tên máy ảnh và tên các thuộc tính kèm theo máy ảnh. 41 Giải thuật loại bỏ từ dừng, chuẩn hóa các từ trong câu: Đầu vào: Một câu văn bản Đầu ra: Một câu mới loại bỏ các từ dừng, các động từ ở dạng gốc. void Token(sentence) 1. filter = ; tokens =  tokens = sentence.Split(); for each token in tokens { if (not Is_Stop_Word(token)) filter = filter  {token}; } 2. s = “”; for each token in filter { for each attribute in set_attributes { if (Lower(token) = Lower(attribute)) token = attribute; } for each producer in set_producers { if (Lower(token) contain Lower(producer)) token = producer; } if (not Check_Camera(token) and not Check_Producer(token) and not Check_Attribute(token)) Stemmer(Lower(token); s = s + token; } 3. return s; c. B3: Loại bỏ các câu không liên quan Công việc tiếp theo là tìm các câu tiềm năng, những câu có khả năng chứa các cặp quan hệ cần trích chọn. Vì số lượng tập tài liệu là khá lớn, số lượng câu sau khi tách cũng rất nhiều, trong các câu có những câu không giúp ích gì trong quá trình trích chọn. Việc trích chọn ra được bộ quan hệ đích chỉ thực hiện khi tên hãng sản xuất và tên máy ảnh đứng gần nhau trong cùng một câu, do đó ta chỉ quan tâm đến những câu nào chứa một trong các tên hãng sản xuất máy ảnh, 42 các câu còn lại ta sẽ loại bỏ khỏi CSDL, tránh mất thời gian trong việc tìm kiếm và trích chọn. Hệ thống tiến hành quét trên tất cả các câu, nếu chúng chứa một trong các tên các hãng máy ảnh có trong tập P, giữ lại các câu đó, loại bỏ các câu không thỏa mãn. Chẳng hạn ta có đoạn bài báo: “Samsung has released the TL110 and TL105 ultra compact cameras. The 14.2 megapixel TL110 (ST70 in Europe) and 12 megapixel TL105 (ST60) offer 2.7 inch LCDs, wide angle zoom lenses starting at 27mm equivalent and offer 720p HD video recording using H.264 compression. Both include scene modes such as Fisheye, Lomo and a DeFog Clear/Fog Lifting mode that claims to cut through haze to take clearer images.“, sau pha tiền xử lí, kết quả thu được là câu “Samsung release TL110 TL105 ultra compact cameras”. Giải thuật: Đầu vào: Tập các tài liệu dạng text Đầu ra: Các câu chứa tên các hãng sản xuất máy ảnh void ExploreDirectory( ) 1. set_sentences = ; paragraph = “”; 2. for each file_text in corpus_text { read_to_end(file_text, paragraph); for each single_sentence in SplitSentences(paragraph) { s = token(single_sentence); for each pro in producers if (s Contain pro) set_sentences = set_sentences  {s}; } } return set_sentences; 43 3.3.2. Pha sinh các mẫu Hình 11: Mô hình thuật toán sinh mẫu từ một bộ quan hệ a. Bước1: Sinh các mẫu Dựa vào các quan hệ trong tập hạt giống ban đầu, tìm tất cả các thể hiện chứa các quan hệ hạt giống đó, trích chọn ra các mẫu. Giả sử với một cặp quan hệ hạt giống nào đó, ta lấy toàn bộ ngữ cảnh giữa P và C đưa vào vectơ mc. Tuy nhiên ta giới hạn chỉ giữ lại những vectơ mc có độ dài không quá 5 từ. Mẫu mc nếu P đứng trước C trong câu, hoặc mc nếu P đứng sau C trong câu, được sinh ra. Bộ quan hệ Thể hiện Fujifilm release finepix Z35 digital compact Casio release EX-Z1000 firmware update  release b. Bước 2: Làm giàu tập mẫu Tuy nhiên, để việc sinh ra các bộ quan hệ mới có hiệu quả, tập các mẫu càng nhiều càng tốt. Trong bước này luận văn đề xuất sử dụng WordNet [1, 6]. WordNet là dự án từ điển đơn ngữ (tiếng Anh) thiên về ngữ nghĩa, do Princeton University phát triển. WordNet đã tạo ra một tập hợp từ vựng khá lớn, theo đó các từ được sắp xếp trong dãy của những tập hợp đồng nghĩa (synonym set viết tắt là synset), giúp cho việc xác định nghĩa của từ và để phân biệt được nghĩa đang xét với các nghĩa khác. Nguyên lí tổ chức chung của WordNet là mạng lưới quan hệ ngữ nghĩa. [Phụ lục] WordNet phân biệt giữa danh từ, động từ, tính từ, trạng từ bởi chúng theo các quy tắc ngữ pháp khác nhau. Mọi synset (tập các từ đồng nghĩa) đều chứa một nhóm các từ đồng nghĩa; ý nghĩa khác nhau của một từ được đặt vào các Tập các mẫu WordNet B2: Làm giàu tập mẫu B1: Sinh các mẫu Google B3: Thẩm định các mẫu 44 synset khác nhau. Nghĩa của một từ được trình bày bởi một danh sách các dạng thức của từ đó có thể được sử dụng để biểu thị nó. Chẳng hạn, thông tin tập đồng nghĩa của từ “introduce” được miêu tả trong WordNet như sau: The verb introduce has 10 senses (first 8 from tagged texts) 1. (22) introduce, present, acquaint -- (cause to come to know personally; "permit me to acquaint you with my son"; "introduce the new neighbors to the community") 2. (11) introduce, innovate -- (bring something new to an environment; "A new word processor was introduced") 3. (9) insert, enclose, inclose, stick in, put in, introduce -- (introduce; "Insert your ticket here") 4. (7) bring in, introduce -- (bring in a new person or object into a familiar environment; "He brought in a new judge"; "The new secretary introduced a nasty rumor") 5. (1) introduce -- (bring in or establish in a new place or environment; "introduce a rule"; "introduce exotic fruits") 6. (1) insert, infix, enter, introduce -- (put or introduce into something; "insert a picture into the text") 7. (1) introduce, bring out -- (bring before the public for the first time, as of an actor, song, etc.) 8. (1) introduce -- (put before (a body); "introduce legislation") 9. precede, preface, premise, introduce -- (furnish with a preface or introduction; "She always precedes her lectures with a joke"; "He prefaced his lecture with a critical remark about the institution") 10. inaugurate, usher in, introduce -- (be a precursor of; "The fall of the Berlin Wall ushered in the post-Cold War period") Trong đó mỗi một mục là một nghĩa (sense) của từ “introduce”. Như vậy chúng ta có thể khai thác để sử dụng WordNet vào làm giàu tập mẫu. Giả sử ta có mẫu announce , sử dụng Wordnet, tìm tất cả các từ đồng nghĩa với “announce”, giả sử là {present, declare, post, introduce, communicate, launch, inform...}. Khi đó ta có các mẫu mới: present declare post introduce communicate launch … Ở đây, hệ thống chỉ làm giàu các mẫu trong trường hợp mẫu này có độ dài bằng 1, nghĩa là mẫu chỉ là một động từ, còn các trường hợp còn lại, ta bỏ qua giai đoạn làm giàu. 45 Giả sử ta đưa vào trong WordNet một từ text nào đó, ta cần xác định tập từ đồng nghĩa của text. Trước tiên, WordNet kiểm tra xem từ đó có trong cơ sở dữ liệu WordNet không, nếu có sẽ tiến hành xác định từ loại của text. WnLexicon.WordInfo wordinfo = WnLexicon.Lexicon.FindWordInfo(text, true); Một mảng xâu chứa các từ đồng nghĩa của text sẽ được trả về dựa vào thông tin về loại từ đã xác định. string[] synonyms = WnLexicon.Lexicon.FindSynonyms(text, wordinfo.partOfSpeech, true); Việc tìm các từ đồng nghĩa có thể được thực hiện thông qua một số giao diện lập trình được WordNet cung cấp như trong bảng 6. Tên hàm Tham số Thông tin trả về findtheinfo findtheinfo_ds word syntantic category search type sense number Các kết quả tìm kiếm đã được định dạng trong bộ đệm hoặc cấu trúc dữ liệu. is_defined word pos Tìm từ word có trong từ điển với kiểu từ loại pos. morphstr morphword word pos Dạng thức cơ bản của từ word hoặc null nếu không tìm thấy bất kì sự phù hợp nào trong CSDL. bin_search word streamreader Tìm kiếm từ trong file index, trả về chỉ mục của bản ghi chứa từ đó. search() word morph pos searchtype sn Thực hiện việc tìm kiếm từ word theo loại từ pos, kiểu tìm kiếm searchtype, sử dụng MorphStr nếu morph nhận giá trị true. Trả về tất cả các ý nghĩa của từ nếu sn có giá trị bằng 0. Bảng 6: Một số lớp thường dùng trong WordNet Tuy nhiên việc xây dựng tập đồng nghĩa cho động từ gặp nhiều khó khăn do khó xác định từ đồng nghĩa. Ta thấy trong tiếng Anh, có một số động từ đồng nghĩa như begin – commence, end – terminate, buy – purchase, hide – conceal… nhưng thực chất việc dùng lẫn lộn các động từ đồng nghĩa này không phải lúc nào cũng đúng. Do đó việc thay thế một động từ nào đó bằng từ đồng nghĩa của nó không phải luôn đúng trong mọi ngữ cảnh trong văn bản. Ở đây hệ thống cần phải thẩm định xem tập mẫu vừa làm giàu liệu có khả năng sinh ra bộ quan hệ nào hay không. 46 c. Bước 3: Thẩm định các mẫu Các mẫu tiềm năng sẽ góp phần sinh ra các quan hệ đúng, chính xác. Tuy nhiên, sau thao tác làm giàu tập mẫu, sẽ có những mẫu có xu hướng tạo ra các quan hệ không chính xác, gây nhiễu cho quá trình trích chọn. Do đó, với mỗi mẫu vừa sinh ra, ta cần đánh giá độ tin cậy của mẫu đó. Các mẫu có xu hướng được sử dụng nhiều sẽ tiềm ẩn khả năng tạo ra nhiều quan hệ tiềm năng. Vì tập dữ liệu được lấy từ các trang web, nên ta sẽ sử dụng công cụ tìm kiếm Google để thẩm định các mẫu. Ví dụ với câu Pentax announce Optio E90 budget camera … tương ứng với mẫu announce , ta tra cứu cụm Pentax * Optio E90, nếu cụm từ “Pentax announce Optio E90” xuất hiện ít nhất 1 lần trong 10 kết quả tìm kiếm đầu tiên  mẫu announce được đánh giá là có tiềm năng  đưa mẫu đó vào tập các mẫu để sinh ra các cặp mới. Để lấy được các kết quả tìm kiếm khi nhập vào một khóa trong Google, hệ thống sử dụng Google Search API for.NET 0.4 alpha dựa trên Google Ajax Search API.[19] The Google Web search API cho phép chúng ta đặt kết quả tìm kiếm Google vào các trang web của mình, ta có nhúng một hộp tìm kiếm động đơn giản và hiển thị kết quả tìm kiếm bao gồm các đoạn trích dẫn và các url vào trong các trang web hoặc sử dụng các kết quả một cách sáng tạo theo nhu cầu mục đích của từng cá nhân. Hỗ trợ 8 dịch vụ tìm kiếm là: 1. Tìm kiếm web 3. Tìm kiếm video 2. Tìm kiếm tin tức 5. Tìm kiếm địa phương 4. Tìm kiếm blog 6. Các bản đồ Google Google AJAX Search API được tạo bởi nhiều lớp đối tượng: - GSearchControl - Lớp này cung cấp giao diện người sử dụng và phối hợp với một số đối tượng tìm kiếm, trong đó mỗi đối tượng tìm kiếm được thiết kế để thực hiện các công việc tìm kiếm và trả về một lớp cụ thể của kết quả (Web Search, Local Search vv.) - GSearch - Lớp cơ sở này là lớp mà từ đó tất cả đối tượng tìm kiếm kế thừa. Nó định nghĩa các giao diện mà tất cả các dịch vụ tìm kiếm phải thực hiện. - GResult - Lớp cơ sở đóng gói các kết quả tìm kiếm được tạo ra bởi các đối tượng tìm kiếm. - GsearchOptions - Lớp này thiết lập hành vi của các đối tượng tìm kiếm khi thêm vào một điều khiển tìm kiếm. 47 Hệ thống sử dụng dịch vụ tìm kiếm web, giới hạn 10 kết quả tìm kiếm đầu tiên, việc tìm kiếm trên các trang web tiếng Anh. Kết quả trả về gồm CacheUrl Content; Title; Url; VisibleUrl., tuy nhiên ta chỉ quan tâm đến các kết quả trích dẫn, do đó hệ thống chỉ giữ lại phần Content trong kết quả tìm kiếm để thẩm định các mẫu. Giải thuật sinh ra các mẫu từ bộ quan hệ nào đó trong tập các bộ quan hệ hạt giống. Đầu vào: các bộ quan hệ hạt giống , tập các câu trong CSDL Đầu ra: tập các mẫu sinh bởi void Generate_Pattern_One_Tuple(pro, cam) 1. list_pattern = ; 2. for each sentence in set_sentences if (sentence Contain ) pattern = Cut_Middle(s, pro, cam); 3. synonym = generate_synonym(pattern); for each syn in synonym string = pro + " " + syn + " " + cam; for each result in Search_google(pro + " * " + cam) if (result Contain string) list_pattern = list_pattern  {syn}; 4. return list_pattern; Tuy nhiên không phải bất kì mẫu nào được sinh ra hệ thống đều đưa vào tập mẫu của mình, chỉ có những mẫu có tiềm năng tạo ra nhiều bộ quan hệ thì mới được giữ lại. Với mỗi mẫu được sinh ra, tạm thời ta lưu vào một danh sách, đánh dấu số lượng các bộ quan hệ hỗ trợ để sinh ra mẫu đó. Kết thúc, ta sẽ kiểm tra, nếu số lượng bộ quan hệ hỗ trợ vượt qua ngưỡng sup nào đó, ta sẽ thêm mẫu đó vào tập mẫu trích chọn. Trong thực nghiệm sup có giá trị bằng 2. Do đó hệ thống loại bỏ tất cả các mẫu được hỗ trợ bởi ít hơn 2 bộ quan hệ hạt giống. Thuật toán sinh ra tất cả các mẫu dựa vào các bộ quan hệ hạt giống, chỉ giữ lại các mẫu được hỗ trợ bởi ít nhất sup bộ quan hệ. Đầu vào: Tập các bộ quan hệ hạt giống Đầu ra: Tập các mẫu tiền năng set_patterns = ; Void Generate_Pattern() 1. for each in set_tuples 48 list_pattern = generate_pattern_one_tuple(cam, pro); 2. for each pattern in list_pattern If (Count_Appear(pattern, list_pattern) >= sup ) and (not set_patterns Contain pattern) set_patterns = set_patterns  {pattern}; 3. return set_pattern; 3.3.3. Pha sinh các bộ quan hệ mới Quét tất cả các câu có chứa tên các hãng sản xuất máy ảnh, nếu câu có chứa mẫu pattern, hệ thống phân tích ngữ cảnh phía trước before, ngữ cảnh phía sau after của pattern trong câu:  Nếu before phù hợp với tên nhà sản xuất và after phù hợp với tên máy ảnh (tương ứng với thể hiện middle ) thì ta thêm cặp vào trong bảng kết quả.  Hoặc nếu before phù hợp với tên máy ảnh và after phù hợp với tên nhà sản xuất (tương ứng với thể hiện middle ) thì ta thêm cặp vào bảng kết quả đích. Thuật toán được trình bày như sau: Đầu vào: Một mẫu nào đó trong tập các mẫu đã được sinh ra ở pha trước Đầu ra: Các bộ quan hệ mới void Generate_Tuple(pattern) for each s in set_sentences if (s Contain pattern) before  copy_before(s, pattern); after  copy_after(s, pattern); 1. if Check_Camera(after) and Check_Producer(before) and after  set_tuples) set_tuples = set_tuples  {}; 2. if Check_Camera(before) and Check_Producer(after) and before  set_tuples) set_tuples = set_tuples  {}; 3. return set_tuples; Chẳng hạn với câu “Fujifilm announce introduction Finepix S1000fd” và mẫu “announce introduction” thì quan hệ ta có thể trích chọn được là <Finepix S1000fd, Fujifilm>. Hoặc với câu “Panasonic release DMC-FS25 digtal camera” và mẫu “release” thì hệ thống phải trích chọn ra được bộ quan hệ <DMC-FS25, Panasonic>. 49 Trong tập văn bản, có những thể hiện tên máy ảnh đi liền với tên hãng sản xuất, ví dụ ta có câu “Canons 40D update version 1” thì ta trích chọn được bộ quan hệ . Những thể hiện dạng này, ngữ cảnh giữa tên máy ảnh và tên hãng sản xuất là rỗng, do đó ta sẽ có thủ tục để trích chọn ra các bộ quan hệ có thể hiện hoặc thể hiện . Để thực hiện việc này, hệ thống sẽ kiểm tra tất cả các câu thu được sau pha tiền xử lí, với mỗi tên hãng sản xuất producer máy ảnh:  Lấy ngữ cảnh bên phải after của nó (tương ứng với thể hiện )  Hoặc lấy ngữ cảnh bên trái before của nó (tương ứng với thể hiện ) Sau đó kiểm tra liệu after hoặc before có khả năng là tên một loại máy ảnh hay không, nếu đúng, đưa cặp hoặc vào tập quan hệ đích. Giải thuật: Đầu vào: Tập các câu tiền năng chứa tên các hãng máy ảnh Đầu ra: Các bộ quan hệ sinh bởi mẫu void Generate_Empty_Tuple(); for each s in set_sentences for each producer in set_producers after  copy_after(s, producer); 1. If (Check_Camera(after) and after  set_tuples) set_tuples = set_tuples  {}; 2. else If (Check_Camera(before) and before  set_tuples) set_tuples = set_tuples  {}; 3. return set_tuples; 50 CHƯƠNG 4. THỰC NGHIỆM 4.1. Môi trường thực nghiệm Thực nghiệm được tiến hành trên máy PC có cấu hình phần cứng như bảng 7. Công cụ phát triển là ngôn ngữ C#, cụ thể được liệt kê trong bảng . Ngoài ra còn sử dụng một số thư viện chẳng hạn như thư viện truy cập WordNet bằng giao diện C#, công cụ truy vấn Google như liệt kê trong bảng 9. Thành phần Chỉ số Bộ xử lí Intel(T) Core™2 Dual T5870 @ 2.00GHz Bộ nhớ trong 2GB Ổ cứng 80GB Hệ điều hành Microsoft Windows XP2 Bảng 7: Cấu hình của máy PC dùng trong thực nghiệm STT Tên phần mềm Tác giả Nguồn 1 Visual studio 2008 Microsoft Corporation 2 WordNet 2.1 Princeton University Bảng 8: Các công cụ sử dụng trong thực nghiệm STT Tên thư viện Tác giả Nguồn 1 WordNet.Net Troy Simpson, Malcolm Crowe 2 Google Search API for.NET 0.4 alpha for-dotnet/ #Google_Search_API_for _.NET_0.4_alpha Bảng 9: Các thư viện sử dụng trong thực nghiệm 4.2. Dữ liệu thực nghiệm Dữ liệu dùng trong thực nghiệm được lấy từ hai địa chỉ, nơi chứa nhiều thông tin liên quan đến máy ảnh kĩ thuật số, đó là: 1. 2. Dữ liệu thực nghiệm được chia thành 2 tập:  Tập 1200 (tập kiểm thử) bao gồm 1263 trang web, chuyển các trang này thành các tài liệu, sau đó tiến hành gán nhãn bằng tay. Tập dữ liệu này được dùng để đánh giá chất lượng giải thuật.  Tập 5000 bao gồm 4934 trang web, cũng tiến hành chuyển các trang này thành các tài liệu dạng thô. Tập này dùng để sinh ra tập 51 các mẫu trích chọn, sau đó áp dụng tập mẫu này vào tập 1200 để sinh ra các bộ quan hệ trong tập 1200. Thông tin chi tiết về hai tập dữ liệu này được liệt kê ở trong bảng 10. Dữ liệu Nguồn Số lượng 587 Tập 1200 676 2016 Tập 5000 2918 Bảng 10: Dữ liệu kiểm thử và dữ liệu huấn luyện 4.3. Đánh giá hệ thống Hệ thống được đánh giá chất lượng qua các độ đo: Precision (độ chính xác) và Recall (độ hồi tưởng) và F1 được tính theo công thức dưới đây: oducedPr_Answers Answers_CorrectPrecision  Correct_Possible_Total Answers_CorrectcallRe  callReecisionPr callRe*ecisionPr*F   2 1 Để thẩm định các cặp quan hệ được tạo ra, luận văn tạo ra một file kết quả, chứa tất cả các cặp quan hệ có thể được tạo ra trong tập dữ liệu kiểm thử - tập 1200, từ đó so sánh với các cặp quan hệ do hệ thống trích chọn, tính toán được giá trị Precision, Recall và F1 qua các vòng lặp. 4.4. Thực nghiệm FinePix A345 Fujifilm NX10 Samsung PowerShot S3IS Canon PowerShot SD780 Canon DSC-T30 Sony Bảng 11: Tập các quan hệ hạt giống ban đầu Thực nghiệm 1 Thực nghiệm thứ nhất chúng tôi tiến hành trên tập dữ liệu kiểm thử (Tập 1200). Bắt đầu với 5 quan hệ ở bảng 11, hệ thống tạo ra được 10 mẫu. Trong 10 mẫu này chúng tôi chỉ giữ lại các mẫu được hỗ trợ bởi ít nhất 2 cặp quan hệ hạt giống, và dùng các mẫu này để trích chọn các cặp quan hệ mới. Các mẫu rút trích được trong lần lặp đầu tiên là: post firmware update release firmware update 52 Tại vòng lặp đầu tiên sử dụng các mẫu vừa được tạo cùng với mẫu và , hệ thống sinh ra được 457 cặp quan hệ mới, trong đó có 415 cặp quan hệ chính xác trên tổng số 746 cặp quan hệ có thể lấy ra được từ tập CSDL ban đầu. Một số cặp quan hệ được trích chọn ở vòng lặp đầu tiên được liệt kê trong bảng 12. Tên hãng sản xuất Tên máy ảnh Nikon CoolPix S230 Fujifilm FinePix JZ500 Pentax Optio RS1000 Nikon CoolPix L110 Olympus FE-5010 Panasonic Lumix ZS1 Olympus C8080 Olympus SP-800UZ Kodak DC215 Canon EOS 500D Canon 430EX Sony TRV30 Kodak DVC325 Nikon CoolPix S8100 Canon S600 Kodak EasyShare CX6230 Nikon CoolPix S630 Nikon CoolPix 900 Bảng 12: Một số cặp ở lần lặp đầu tiên Từ vòng lặp thứ 4, số lượng cặp quan hệ được tạo ra không thay đổi. Giá trị của Precision và Recall, F1 qua mỗi vòng lặp được chỉ ra ở bảng 13. Số lần lặp Precision Recall F1 1 90.81 55.93 69.22 2 87.32 81.67 84.40 3 85.87 86.79 86.33 4 85.36 87.20 86.27 Bảng 13: Giá trị Precision, Recall và F1 sau các vòng lặp Hướng tiếp cận của hệ thống xuất phát từ các mẫu có độ hồi tưởng thấp, độ chính xác cao, kết hợp các tri thức để lọc kết quả. Ở vòng lặp đầu tiên, tuy rằng số lượng các cặp quan hệ trích chọn được còn ít (457 trên tổng số 746 bộ quan hệ), nhưng độ chính xác của các bộ quan hệ đó lại khá cao (khoảng 90%), 53 do đó kết quả nhận được có giá trị độ hồi tưởng thấp. Tại các vòng lặp tiếp theo, số lượng các bộ quan hệ trích chọn được tăng dần, tuy nhiên độ chính xác lại có xu hướng giảm dần. Từ vòng lặp số 4, số lượng các bộ quan hệ mà hệ thống trích ra được không thay đổi, lúc này giá trị độ hồi tưởng đã vượt quá 87%, còn giá trị độ chính xác dao động quanh khoảng 85%. Biểu đồ mô tả độ chính xác và độ hồi tưởng được trình bày ở hình 12. 50 55 60 65 70 75 80 85 90 95 1 2 3 4 Số lần lặp % Precision Recall F1 Hình 12: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 1200 Hệ thống trích chọn còn sử dụng một tham số là sup để đánh giá độ chất lượng của các mẫu được sinh ra, hệ thống chỉ sử dụng các mẫu được sinh bởi từ sup bộ quan hệ hạt giống trở lên. Bảng 14 phía dưới thể hiện số lượng các bộ quan hệ mà hệ thống trích chọn được, số lượng các bộ quan hệ chính xác tùy thuộc vào các giá trị khác nhau của sup. Từ kết quả chúng tôi nhận thấy rằng, nếu giá trị sup càng lớn, số lượng các bộ quan hệ trích chọn được lại giảm. Là do giá trị sup càng tăng, số lượng các mẫu trích chọn được và được sử dụng cho vòng lặp tiếp theo càng ít, chỉ những mẫu được sinh bởi càng nhiều bộ quan hệ mới được dùng để trích chọn các bộ quan hệ mới, những mẫu ít chất lượng hơn sẽ bị loại bỏ, do đó những bộ quan hệ được sinh bởi những mẫu kém chất lượng hơn sẽ không được hệ thống 54 trích chọn và đưa vào bảng quan hệ đích. Do đó, độ chính xác có xu hướng tăng, còn độ hồi tưởng có xu hướng giảm dần. Số lượng các bộ quan hệ trích chọn được Giá trị các độ đo sup Tổng số Chính xác Precision Recall F1 1 802 662 82.54 89.22 85.75 2 758 647 85.36 87.20 86.27 3 703 612 87.06 82.48 84.71 4 639 569 89.05 76.68 82.40 5 637 567 89.01 76.42 82.24 Bảng 14: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup Biểu đồ thể hiện sự tương quan giữa các giá trị Precision, Recall, F1 phụ thuộc vào giá trị của sup được trình bày ở hình 13. 70 75 80 85 90 95 100 1 2 3 4 5 tsup % Precision Recall F1 Hình 13: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup Thực nghiệm 2 Thực nghiệm tiếp theo chúng tôi cho hệ thống chạy thử trên Tập 5000 để thu các tập mẫu được sinh ra. Sau đó chúng tôi dùng tập mẫu này để trích chọn các cặp quan hệ trong Tập 1200. 55 Kết quả cho thấy, khi thực nghiệm với Tập 5000, số lượng mẫu thu được khá lớn là 435 mẫu (so với 100 mẫu khi thực nghiệm trên Tập 1200), tuy nhiên số lượng các bộ quan hệ sinh ra lại tăng không đáng kể. Kết quả cụ thể của thực nghiệm được liệt kê ở bảng 15 và 16. Số lần lặp Precision Recall F1 1 83.18 88.01 85.53 2 82.98 90.03 86.36 3 81.86 90.03 85.75 4 81.86 90.03 85.75 Bảng 15: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 5000 Số lượng các bộ quan hệ trích chọn được Giá trị các độ đo Thực nghiệm Tổng số Chính xác Precision Recall F1 Thực nghiệm 1 758 647 85.36 87.20 86.27 Thực nghiệm 2 816 668 81.86 90.03 85.75 Bảng 16: Kết quả so sánh giữa thực nghiệm 1 và 2 So sánh kết quả của thực nghiệm này với thực nghiệm thứ nhất chúng tôi thấy chất lượng không chênh lệch nhau là mấy. Việc sử dụng huấn luyện để trích chọn ra tập các mẫu, với số lượng các tài liệu lớn hơn, các mẫu trích chọn được sẽ nhiều hơn và có tính chuyên biệt hơn, do đó kết quả sẽ tốt hơn với việc không sử dụng tập 1200 (thu được nhiều bộ quan hệ chính xác hơn). Tuy nhiên số lượng các bộ quan hệ trích chọn ra được tăng không đáng kể, là do dữ liệu trên tập 1200 và 5000 đều lấy từ 2 địa chỉ website, các bài viết trên mỗi địa chỉ thường có định dạng giống nhau nhau, những mẫu chất lượng sinh ra bởi tập 5000 cũng được sinh ra ở tập 1200, những mẫu còn lại trong tập 5000 có tính khả dụng kém hơn nên khi áp dụng các mẫu này cho tập 1200, số lượng bộ quan hệ sinh ra không đáng kể. Thậm chí, số lượng mẫu tăng, bộ quan hệ sinh ra có tăng, kèm theo đó là độ chính xác của các bộ sinh ra thấp, làm cho giá trị Precision cuối cùng thấp hơn, giá trị F1 vì thế thấp hơn so với thực nghiệm 1. Để đánh giá tính hiệu quả của giải mà luận văn đã đề xuất, chúng tôi cũng cài đặt giải thuật DIPRE. Thực nghiệm 3 Chúng tôi cho giải thuật DIPRE thực hiện trên tập 1200. Ở vòng lặp đầu tiên, số lượng bộ quan hệ trích chọn được là vô cùng nhỏ - 14 bộ quan hệ, trong đó chỉ có 11 bộ quan hệ là chính xác. Ở các vòng lặp tiếp theo, số lượng bộ quan hệ trích chọn được có tăng, nhưng với số lượng thấp. Cụ thể, kết quả thực nghiệm được chỉ ra ở bảng 17. 56 Số lần lặp Precision Recall F1 1 71.43 1.28 2.51 2 50.00 4.85 8.84 3 47.62 8.93 15.04 4 42.54 14.54 21.67 7 41.16 18.11 25.15 Bảng 17: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 1200 Thực nghiệm 4 Chúng tôi cũng tiến hành thực nghiệm đối với giải thuật DIPRE thực hiện trên tập 5000, thu thập các mẫu, sau đó sử dụng tập mẫu này để trích chọn các bộ quan hệ trên tập 1200. Kết quả khả quan hơn thực nghiệm 3, kết quả cụ thể được trình bày trong bảng 18. Số lần lặp Precision Recall F-score 1 36.10 34.44 35.25 2 33.67 38.52 35.93 3 31.88 39.16 35.15 4 31.15 39.41 34.80 Bảng 18: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 5000 Kết quả thực nghiệm với DIPRE thống kê trên số lượng các bộ quan hệ trích chọn được trình bày trong bảng 19. Số lượng các bộ quan hệ trích chọn được Thực nghiệm Tổng số Chính xác Thực nghiệm 3 345 142 Thực nghiệm 4 992 309 Bảng 19: Bảng thống kê kết quả trích chọn khi áp dụng giải thuật DIPRE cho bài toán trích chọn tên máy ảnh số Dựa vào kết quả thực nghiệm 3 và 4 đối với giải thuật DIPRE, nhận thấy giải thuật do luận văn đề xuất hiệu quả hơn rất nhiều so với giải thuật DIPRE áp dụng cho bài toán trích chọn tên máy ảnh số. Biểu đồ so sánh kết quả trích chọn của giải thuật DIPRE và giải thuật do luận văn đề xuất được chỉ ra ở hình 14. 57 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 Số lần lặp % Luận văn DIPRE (a) 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 Số lần lặp % Luận văn DIPRE (b) Hình 14: Kết quả thực nghiệm 3 (a) và thực nghiệm 4 (b) đối với giá trị F1 Thực nghiệm 5 Chúng tôi tiến hành thực nghiệm trích chọn các cặp trên Tập 1200; giá trị sup = 2; độ dài lớn nhất của mỗi mẫu = 10. 58 Kết quả thực nghiệm được thống kê trong bảng 20. Tổng số cặp hệ thống trích chọn được Tổng số cặp trong CSDL Chính xác Không chính xác Tổng 746 648 111 758 Bảng 20: Kết quả thực nghiệm 5 với số lượng các cặp tìm được Trong thực nghiệm này, chúng tôi tiến hành thống kê những mẫu có chất lượng nhất, có khả năng trích chọn ra được nhiều tên máy ảnh nhất. Danh sách các mẫu này cùng với một số bộ quan hệ được sinh bởi chúng được trình bày trong bảng 21, trong đó mẫu chất lượng nhất là mẫu . Mẫu Ví dụ Nikon D3 Samsung NX10 update firmware Canon EOS 7D Ricoh CX3 unveil Toshiba PDR-M3 Panasonic Lumix DMC-ZS7 introduce Canon PowerShot SX210 Fujifilm FinePix S3 launch Panasonic Lumix DMC-TS2 Fujifilm FinePix XP10 release Canon PowerShot S1 Panasonic Lumix DMC-FX66 announce firmware update Canon EOS 5D Panasonic DMC-G1 release firmware update Panasonic DMC-LX3 Nikon CoolPix P90 post firmware update Olympus E-P1 Pentax K-7 announce price Panasonic DMC-GH1 Nikon D100 Bảng 21: Kết quả thực nghiệm 5 - Một số mẫu có độ chính xác cao và xuất hiện nhiều Chúng tôi cũng tiến hành thống kê tên các loại máy ảnh có xuất hiện nhiều nhất trong tập dữ liệu mà hệ thống trích chọn ra được. Đứng đầu danh sách là máy ảnh Nikon D3 với 68 lần xuất hiện, tiếp theo là Samsung NX100, Nikon D70…, cho thấy mức độ quan tâm của người dùng về các loại máy ảnh này là khá cao. Kết quả được thể hiện trong bảng 22. 59 Trong kết quả thực nghiệm, hãng sản xuất có số lượng máy ảnh nhiều nhất trích chọn ra được là Canon với 103 loại máy ảnh khác nhau, tiếp theo là Panasonic với 93 máy ảnh, thứ ba là hãng Nikon với 91 loại máy ảnh... Kết quả cụ thể được thể hiện trong bảng 23. Tên hãng sản xuất Tên máy ảnh Số lần xuất hiện Nikon D3 68 Samsung NX10 50 Nikon D70 46 Olympus E-PL1 37 Panasonic G1 33 Canon 5D 28 Sigma SD1 28 Nikon D3S 27 Nikon D700 26 Olympus E-5 24 Sony NEX-3 24 Sony NEX-5 24 Fujifilm S1 23 Canon 1D 22 Canon 50D 22 Nikon 950 21 Sony A55 19 Nikon CoolPix 950 19 Nikon D7000 19 Olympus E-3 19 Nikon D1 18 Sigma DP2 18 Olympus E-P2 18 Panasonic F3 17 Canon 7D 16 Nikon D300 16 Samsung NX100 16 Pentax 645D 15 Ricoh CX3 15 Olympus E-P1 15 Bảng 22: Kết quả thực nghiệm 5 - Thống kê các loại máy ảnh phổ biến nhất 60 Tên nhà sản xuất Số lượng máy ảnh Canon 103 Panasonic 93 Nikon 91 Fujifilm 78 Sony 72 Pentax 51 Casio 36 Olympus 35 Kodak 32 Samsung 24 Sanyo 20 Ricoh 17 Bảng 23: Kết quả thực nghiệm 5 - Thống kê số lượng máy ảnh theo hãng sản xuất 61 Kết luận và hướng phát triển tương lai Từ việc nghiên cứu bài toán trích chọn quan hệ, luận văn đã đưa ra mô hình trích chọn tên máy ảnh kĩ thuật số từ tập văn bản. Qua thực nghiệm cho thấy mô hình là khả thi và có thể áp dụng được. Về mặt nội dung, khóa luận đã đạt những kết quả sau: - Giới thiệu bài toán trích chọn quan hệ và các khái niệm liên quan. - Tìm hiểu và phân tích các phương pháp trích chọn quan hệ điển hình, trong đó tập trung vào phương pháp học bán giám sát để trích chọn thực thể tên. - Áp dụng mô hình học bán giám sát để xây dựng mô hình trích chọn tên máy ảnh kĩ thuật số và đạt được một số kết quả khả quan. Bên cạnh đó, do hạn chế về thời gian và kiến thức, luận văn còn một số hạn chế sau: - Khóa luận mới dừng lại ở việc trích chọn tên máy ảnh mà chưa trích chọn được các thuộc tính liên quan đến máy ảnh như độ phân giải, độ zoom,… Trong một câu thường chỉ trích chọn ra được một cặp , các câu có dạng … … thì chỉ trích chọn được cặp . Kết quả thực nghiệm còn nhiều trường hợp chưa đạt được độ chính xác như mong muốn. Về định hướng nghiên cứu, việc giải quyết bài toán theo tiếp cận bán giám sát là bước khởi đầu tốt. Trong thời gian tới, luận văn sẽ được phát triển theo các hướng sau: - Mở rộng hệ thống, không dừng lại ở việc trích chọn tên máy ảnh mà còn trích chọn các đặc trưng (thuộc tính, tham số kỹ thuật) của máy ảnh. Tiếp đến là có thể phát triển các thuật toán trích chọn các ý kiến đánh giá chất lượng của các loại máy ảnh hay so sánh các thuộc tính của người dùng từ đó có thể đưa ra các thông tin hữu ích giúp người dùng trước khi mua máy ảnh có thể tham khảo. - Cải tiến chương trình để đạt được các kết quả chính xác hơn. 62 Tài liệu tham khảo [1] George A.Miller, Richard Beckwith, Christiane Fellbaum, Derek Gross and Katherine Miller (1993), Introduction to WordNet: An On-line Lexical database, International Journal of Lexicography, pp. 235-312. [2] Eugene Agichtein and Luis Gravano (2000), Snowball: Extracting Relations from Large Plain text Collections, Proceedings of the 5th ACM International Conference on Digital Libraries, pp. 185-194. [3] Sergey Brin (1998), Extraction Patterns and Relation from the World Wide Web, Proceedings of the 6th International Conference on Extending Database Technology, pp. 172-183. [4] Mary E. Calif and Raymond J. Mooney (1998), Relational learning of Pattern – Match Rules for Information Extraction, Proceedings of AAAI Spring Symposium on Applying Machine Learning, pp 328-334. [5] Douglas E.Appelt, David J.Israel (1999), Introduction to Information Extraction, A Tutorial Prepared for IJCAI-99. [6] Christiane Fellbaum (1998), WordNet: An Electronic Lexical Database and Some of Its Applications, MIT Press, [7] Claudio Giuliano, Albert Olavelli and Lorenza Romano (2007), Relation Extraction and the Influence of Automatic Named-Entity Recognition, ACM Trans. Speech Lang. Process. 5, pp. 9-15. [8] Ralph Grishman and Beth Sundheim (1996), Message Understanding Conference - 6: A Brief History, Proceedings of the 16th International Conference on Computational Linguistics (COLING), pp. 466-471. [9] Ralph Grishman (1997), Information extraction: Techniques and challenges, In Information Extraction (International Summer School SCIE-97), pp. 10- 27. [10] Ralph Grishman, Silja Huttunen and Roman Yangarber (2002), Information Extraction for Enhanced Access to Disease Outbreak Reports , Journal of Biomedical Informatics, pp. 462-477. [11] M. Hassel (2003), Exploitation of Named Entities in Automatic Text Summarization for Swedish, In Proceedings of NODALIDA 03 - 14 th Nordic Conference on Computational Linguistics. [12] U. Hermjakob, K. Knight, and H. Daume (2008), Name Translation in Statistical Machine Translation: Learning When to Transliterate, Proc. ACL, pp. 389-397. [13] GuXu, Shuang-HongYang and HangLi (2009), Named Entity Mining from Click-Through Data Using Weakly Supervised Latent Dirichlet Allocation, 63 Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1365-1374. [14] Nozomi Kobayashi, Kentaro Inui and Yuji Matsumoto (2007), Opinion Mining from Web documents: Extraction and Structurization, Journal of Japanese Society for Artificial Intelligence, pp. 326-335. [15] Giridhar Kumaran and James Allan (2004), Text Classification and Named Entities for New Event Detection, Proceedings of the 27PthP Annual International ACM SIGIR Conference, pp. 297-304. [16] Diego Molla, Mennovan Zaanen and Daniel Smith (2006), Named Entity Recognition for Question Answering, Proceedings ALTW, pp. 51-58. [17] Marius Pasca (2004), Acquisition of Categorized Named Entities for Web Search, ACM Press, pp. 137-145. [18] Ellen Riloff (1996), Automatically Generating Extraction Patterns from Untagged text, In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pp. 1044-1049. [19] Google AJAX Search API 64 Phụ lục. Mối quan hệ ngữ nghĩa trong WordNet WordNet là một hệ cơ sở tri thức cho từ vựng tiếng anh. Các từ vựng trong WordNet được phân loại và tổ chức thành các tập đồng nghĩa synset. Mỗi tập synset biểu diễn một nghĩa. WordNet tổ chức 25 cấu trúc cây phân cấp riêng biệt tương ứng với các lĩnh vực có ngữ nghĩa khác nhau cho synset. Quan hệ ngữ nghĩa trong WordNet được trình bày trong bảng 24. Thông thường, người ta thường hay sử dụng WordNet cho việc tìm kiếm các mối quan hệ ngữ nghĩa. Đồng thời, dựa vào các mối quan hệ này, một từ trong WordNet có thể tìm được các mối liên hệ với các khái niệm khác. Bảng 24: Các quan hệ ngữ nghĩa trong WordNet * Quan hệ đồng nghĩa (synonymy) Các tập đồng nghĩa được gọi là có quan hệ đồng nghĩa với nhau khi chúng có thể thay thế cho nhau trong một số ngữ cảnh nào đó. Vì thế WordNet đã được chia thành nhóm danh từ (noun), động từ (verb), tính từ (adjective), và trạng từ (adverb). Và những mối quan hệ đồng nghĩa chỉ tồn tại giữa các tập đồng nghĩa ở cùng dạng từ loại. Điều này cũng thật dễ hiểu, bởi vì các danh từ sẽ diễn tả những khái niệm thuộc về danh từ, động từ thì diễn tả những khái 65 niệm chỉ hành động, còn tính từ và trạng từ thì giúp ta có thể diễn tả mức độ của những khái niệm trên. * Quan hệ trái nghĩa (antonymy) Một từ trái nghĩa của từ x thông thường sẽ là not-x, nhưng không phải lúc nào cũng đúng như vậy. Chẳng hạn, ta có từ rich (giàu) và poor (nghèo) là hai từ trái nghĩa, nhưng ta không thể nói rằng một người không giàu là một người nghèo. Quan hệ trái nghĩa là một quan hệ giữa các từ với nhau chứ không phải là quan hệ giữa các nghĩa của từ với nhau. * Quan hệ cấp bậc (hyponymy/ hypernymy) Ngược với quan hệ đồng nghĩa và trái nghĩa là các quan hệ giữa các từ với nhau, quan hệ cấp bậc (hạ danh/ thượng danh) là quan hệ giữa các nghĩa của từ. Ví dụ: tree (cây) là một hyponym của plant (thực vật). * Quan hệ bộ phận/ toàn thể (meronymy/ holonym) Một loại quan hệ ngữ nghĩa khác được định nghĩa trong WordNet đó là quan hệ bộ phận và toàn thể (part-whole relation) còn gọi là meronym/ holonym. Một ý niệm tương ứng với synset {x, x, ...} được gọi là một meronym của ý niệm tương ứng với synset {y, y, ...} khi chúng ta có thể nói “một y có một x” (a y has an x) hoặc “một x là một phần của y” (an x is a part of a y). * Quan hệ kéo theo đối với động từ (entailment): Quan hệ kéo theo có phần nào giống quan hệ bộ phân nhưng không thích hợp cho ý nghĩa V1 là bộ phận V2 giống như bên danh từ. Ngoài ra quan hệ giữa 2 động từ còn phụ thuộc vào thời gian thực hiện, xảy ra hành động, biến cố (bên danh từ: quan hệ bộ phận không phụ thuộc vào thời gain). Một hành động hay biến cố được gọi là một bộ phận của một hành động hay biến cố khác chỉ khi nó là một phần, một giai đoạn trong quá trình thực hiện của hành động kia. * Quan hệ cách thức đặc biệt của động từ (troponymy) Ví dụ “limp” (đi khập khiễng) có quan hệ cách thức đặc biệt với “walk” (đi bộ) vì “đi khập khiễng mà một cách thức đi bộ đặc biệt”. Trong quan hệ cách thức đặc biệt bao giờ cũng có quan hệ kéo theo, ví dụ như khi diễn ra hành động “đi khập khiễng” thì hiển nhiên lúc đó phải diễn ra hành động “đi bộ”. Một quan hệ kéo theo mà trong đó thời gian diễn ra 2 hành động của 2 động từ trùng nhau thì ta có quan hệ cách thức đặc biệt, ví dụ giữa “buy/ pay” hay “snore/ sleep” chỉ là quan hệ kéo theo thôi chứ không có quan hệ cách thức đặc biệt vì thời gian diễn ra của 2 hành động không trùng nhau.