Tóm tắt và trích rút tài liệu văn bản trong thư viện số

Nội dung text: Tóm tắt và trích rút tài liệu văn bản trong thư viện số

1. TÓM TẮT VÀ TRÍCH RÚT TÀI LIỆU VĂN BẢN TRONG THƯ VIỆN SỐ ĐỖ QUANG VINH Bộ môn Công nghệ Thông tin - Trường Đại học Văn hoá Hà Nội 1. MỞ ĐẦU Hiện nay, thư viện số là một trong những hướng nghiên cứu chính về công nghệ thông tin trên thế giới. Bài toán tóm tắt và trích rút tài liệu văn bản trong thư viện số đang được nhiều nhà nghiên cứu về các ngành khoa học khác nhau như tin học, toán học và ngôn ngữ học quan tâm. Mục tiêu của bài báo là nhận được một số phương pháp có thể lập trình trên máy tính, như vậy, máy tính sau khi được cung cấp một tài liệu văn bản, sẽ sản xuất một tóm tắt giàu thông tin. Nhưng bài toán tóm tắt tổng quát gặp phải khó khăn lớn vì nó bao hàm các bài toán khác, xây dựng các câu mới. Một cách tóm tắt hạn chế hơn là trích rút các câu quan trọng nhất. Tất nhiên, chúng ta còn cách khá xa một giải pháp thỏa đáng ngay cả đối với bài toán đơn giản hơn về trích rút tài liệu. Ở đây, chúng tôi trình bày một số kết quả nghiên cứu lý thuyết về bài toán. Cách tiếp cận của chúng tôi chủ yếu là áp dụng các phương pháp lấy mẫu và ước lượng thống kê tài liệu văn bản trong thư viện số. 2. TÓM TẮT TỐI ƯU Cho T là một văn bản cho trước và A là một tóm tắt của T. Cho I(T) và I(A) tương ứng là thông tin chứa trong T và A, L(T) và L(A) là độ dài của T và A. Ở đây, bài toán đánh giá I và L không được xét và được thảo luận ở mục 4. Bây giờ, chúng ta có thể yêu cầu A chứa một phần thông tin định rõ chứa trong T. Điều này cực tiểu hoá độ dài trong tất cả tóm tắt thoả mãn yêu cầu trên, sau đó có thể được coi là tối ưu. Như một lựa chọn, chúng tôi yêu cầu độ dài của A là một phần định rõ của tóm tắt về T và xác định là tối ưu chứa lượng thông tin cực đại. Chính xác hơn, chúng tôi có: Định nghĩa 1 Một tóm tắt AL của một văn bản cho trước T được gọi là một tóm tắt có độ dài cực tiểu chứa lượng thông tin liên quan nếu I(AL) = . I(T) và L(AL) L(A) đối với mọi tóm tắt của A về T sao cho I(A) = . I(T). Một tóm tắt AI của T được gọi là tóm tắt thông tin cực đại có độ dài  liên quan, nếu L(AI) =  . L(T) và I(AI) I(A) sao cho L(A) =  . L(T). Nhận xét 1 Có thể xuất hiện các yêu cầu có thể là I(A) . I(T) và L(A)  . L(T) tương ứng. Nhưng một tóm tắt A đối với I(A) > . I(T) chẳng hạn, không thể là loại có độ 1
2. dài cực tiểu. Bởi vì L(A) tương ứng có thể bị giảm bằng cách loại bỏ lượng thông tin thừa I(A) - . I(T). Bài toán tổng quát nhận được độ dài cực tiểu hoặc các tóm tắt thông tin cực đại rõ ràng là khó giải quyết, vì nó yêu cầu xây dựng các câu mới. Tiếp theo, sự đưa vào công thức hạn chế hơn dựa vào trích rút câu được định nghĩa và khảo sát. Cho s là câu bất kỳ trong T và I(s) và L(s) là thông tin chứa trong s và độ dài của s tương ứng. Chúng tôi giả thiết I(s) 0 và L(s) > 0 đối với mọi s trong T và nếu E là một trích rút, nghĩa là, một tập câu của T thì I(E) và L(E), thông tin chứa trong E và độ dài E là như sau: I(E) = ∑I(s) và L(E) = ∑ L(s) (1) s∈E s∈ E Ở các ứng dụng thực tế, chúng tôi cho rằng giả thiết trên liên quan đến L(E) là hợp lý. Mặt khác, giả thiết về I(E) phải được coi chỉ là một xấp xỉ. Thực tế, nó được đưa vào rộng rãi để tiện thao tác toán học. Tuy nhiên, nó cũng nên chú ý rằng bằng câu chúng tôi không cần thiết hiểu là một câu theo nghĩa truyền thống. Nó có thể là một nhóm câu hoặc một đoạn v.v Nếu có các trường hợp, giả thiết về I(E) có khả năng được thoả mãn hơn. Để nhận được một đoạn trích rút, chúng tôi lựa chọn một phần nhất định trong số câu từ T và loại bỏ các câu còn lại. Ở đây, chỉ có hai khả năng, nghĩa là, lựa chọn và loại bỏ. Tuy nhiên, đối với một số lý do kỹ thuật được giải thích sau đây, chúng tôi đưa xác suất vào quá trình lựa chọn. Định nghĩa 2 Một hàm trích rút ngẫu nhiên F(s) là một hàm định nghĩa đối với mọi s T sao cho 0 F(s) 1. Để sản xuất một đoạn trích rút bằng cách dùng một F(s) cho trước, chúng tôi tiến hành như sau. Đối với mọi s T, kiểm tra giá trị của F(s). Nếu F(s) = 1, s được lựa chọn. Nếu F(s) = 0 , s bị loại bỏ. Nếu 0 < F(s) < 1, chúng tôi thực hiện một thử nghiệm ngẫu nhiên và lựa chọn s với xác suất F(s). Loại kỹ thuật ngẫu nhiên này hay được sử dụng trong thống kê và có các ưu điểm nhất định. Mục đích của chúng tôi là thiết lập định lý 1. Vì có khả năng bị bao hàm, F(s) giống nhau, áp dụng cho lần thứ 2, có thể không sinh ra trích rút như nhau như lần 1. Nhưng lượng thông tin trung bình I(F) và độ dài L(F) có thể được định nghĩa, trong đó I(F) = ∑F(s) I(s), L(F) = ∑F(s) L(s) (2) s∈T s∈ T 3. HÀM TRÍCH RÚT TỐI ƯU Bây giờ, chúng tôi đưa vào hai loại hàm trích rút tối ưu. Định nghĩa 3 2
3. Một hàm trích rút F*(s) được coi là loại có độ dài cực tiểu, tương ứng với một cho trước, 0 1, nếu I(F*) = . I(T) và L(F*) L(F) đối với mọi hàm trích rút F sao cho I(F) = . I(T). F*(s) được coi là loại thông tin cực đại, tương ứng với một  cho trước, 0  1, nếu L(F*) =  . L(T) và I(F*) I(F) đối với mọi F sao cho L(F) =  . L(T). Các đoạn trích rút sản xuất bởi hàm trích rút độ dài cực tiểu hoặc thông tin cực đại được đặt tên phù hợp. Ở đây, chúng tôi chứng minh Định lý 1 Cho Fc(s) là một hàm trích rút sao cho Fc(s) = 1 nếu I(s) > c . L(s), = p nếu I(s) = c . L(s), (3) = 0 nếu I(s) c . L(s), I(s) = c . L(s), I(s) 0. Đối với s T1 , Fc(s) – F(s) 0 và L(s) 0 và I(s) = 0 tương ứng và T3 rỗng. Vì I(F)  F(s) I(s) I(F0 )  F0 (s) I(s) I(T) , chúng ta nhận thấy F(s) = 1. s T1 s T1 3
4. Do đó, Fc (s) F(s) L(s) 0 . Hơn nữa, vì p = 0, F0(s) F(s) đối với mọi s T2 và s T1 Fc (s) F(s) L(s) 0 . Vì vậy, chúng ta lại có L 0 (F) L(F) 0 . Cuối cùng, theo cách s T1 tương tự chúng ta chỉ ra I(Fc) I(F) đối với mọi F sao cho L(F) =  . L(T). Nhận xét 2 Định lý trên phát biểu một câu s được trích rút chỉ nếu I(s)/L(s) c. Định lý tương tự với Bổ đề Neyman Pearson nổi tiếng trong lý thuyết thống kê về kiểm định giả thuyết ([4], [7]). Bây giờ, chúng tôi chỉ ra đối với và  cho trước, tồn tại c và p sao cho F tương ứng của (3) là một hàm trích rút có độ dài cực tiểu tương ứng với hoặc một hàm trích rút thông tin cực đại tương ứng với . Chúng tôi cũng chỉ ra c và p có thể được xác định hoặc ước lượng chính xác như thế nào. Định lý 2 Đối với 0 ,  1, tồn tại một Fc và một Fc có dạng cho trước bởi (3) sao cho . . I(Fc ) = I(T) và L(Fc) =  L(T). Chứng minh: Chúng ta sẽ chỉ ra tồn tại F sao cho I(Fc) = . I(T). Nếu c = 0 thì I(Fc) = I(T). Cho c’ > c. Bằng định nghĩa về Fc’ , Fc’ 0 chỉ nếu I(s) c’. L(s) đưa đến I(s) c . L(s). Do đó, Fc’(s) 0 chỉ nếu Fc’(s) = 1, hoặc Fc’(s) Fc(s) đối với mọi s T. Tiếp theo I(Fc’) I(Fc), hoặc Fc là hàm không tăng của c (không quan tâm đến giá trị p). Hơn nữa, vì T là một tập hữu hạn và L(s) > 0, tồn tại các số K1 và K2 dương sao cho I(s) K2 đối với mọi s T. Bây giờ, đối với c đủ lớn, K1 c và I( Fc ) I(t) nếu c < c . Chúng ta nhận thấy I( F1 ) . I(t) và I( F 2 ) . I(t) ([4]). Cho T và T c c 1 2 là các tập của tất cả s T sao cho I(s) c . L(s) và I(s) = c . L(s) tương ứng. Vì I(F1 ) I(s) và I(F 2 ) I(s), chúng ta nhận thấy I(s) p I(s) , trong đó c  c    s T1 T2 s T1 s T1 s T2 p  I(s) /  I(s) , nếu  I(s) 0 và p = 0 nếu khác. Cho Fc được định nghĩa s T1 s T2 s T2 4
5. . bởi c = c và p = p thì I(Fc ) = I(T). Bằng cách tương tự, chúng ta chỉ ra tồn tại . một Fc sao cho L(Fc) =  L(T). Định lý trên chỉ ra đối với và  cho trước, tồn tại các hàm trích rút tối ưu Fc và Fc. Bây giờ, chúng ta xét bài toán xác định và ước lượng Fc và Fc . Bài toán ước lượng tăng lên khi xác định chính xác bao hàm quá nhiều công việc. Để xác định Fc hoặc Fc , chúng tôi có thể tính giá trị của I(s)/ L(s) đối với mỗi một s T và sắp xếp tất cả câu theo thứ tự giảm dần của I(s)/ L(s). Sau đó, các câu được trích rút lần lượt, s1. s2 , , sn , bắt đầu từ các câu có các giá trị lớn nhất của I(s)/ L(s), cho đến khi tổng tích luỹ của I(s) hoặc L(s) của các câu trích rút bằng hoặc vượt . I(T) hoặc  . L(T) đối với lần thứ nhất. Giả sử n n 1  I(si )  I(T),  I(s n )  I(T) i 1 i 1 và I(sn+2)/ L(sn+2) < I(sn+1)/ L(sn+1) < I(sn)/ L(sn) Sau đó, n c = I(sn+1)/ L(sn+1) , p  I(T)  I(si ) / I(si 1 ) i 1 và Fc được xác định. Các trường hợp khác có thể được giải quyết theo cách tương tự. Chú ý rằng không có nhu cầu tự sắp xếp thực sự các câu. Mỗi một câu được cho một khoá hoặc số định danh và các khoá được sắp xếp theo thứ tự giảm dần của I(s)/ L(s) tương ứng. Sau đó, chúng ta trích rút các khoá và câu tương ứng. Phương pháp trên xác định chính xác các hàm trích rút tối ưu tương ứng với và . Nhưng phương pháp có một khiếm khuyết trong đó sắp xếp câu của T theo dãy có thể mất khá nhiều thời gian. Hơn nữa, từ quan điểm thực hành, không có nhu cầu thực nào xác định chính xác Fc và Fc, vì với và  hầu như được chọn tuỳ ý. Do đó, chúng ta đi đến bài toán tìm kiếm cách ước lượng Fc và Fc. Tiếp theo, chúng tôi đề xuất hai phương pháp dựa vào lý thuyết ước lượng thống kê. Phương pháp thứ nhất chúng tôi thảo luận dựa vào giả thiết phân bố I(s) và L(s) của s trong T là siêu bội hoặc đa thức. Cho một mẫu ngẫu nhiên n câu được lấy từ văn bản cho trước T chứa tổng cộng N câu. Đối với mục đích thực hành, lấy mẫu hệ thống hoặc nhóm có thể được xem xét ([4]). Chúng tôi sử dụng lấy mẫu ngẫu nhiên chỉ để minh hoạ ý tưởng. Cho Tn là tập hợp tất cả câu trong mẫu. Bây giờ áp dụng phương pháp trước để nhận được các trích rút tối ưu từ T . Cho F n và F n là các hàm trích rút n c c có độ dài cực tiểu và thông tin cực đại tương ứng với và . Chúng tôi sẽ chỉ ra F n và c F n là tối ưu theo ngữ nghĩa của định lý tiếp theo, khi sử dụng như các hàm trích rút đối c với văn bản cho trước T. 5
6. Định lý 3 Vì kích thước mẫu n tăng vô hạn I( F n ) và L( F n ) tiến tới .I(T) và .L(T). tương c c ứng theo xác suất. Tăng vô hạn nghĩa là tăng tới N đối với lấy mẫu không có thay thế và tăng tới đối với lấy mẫu có thay thế. Chứng minh: Cho xi và yj trong đó i, j = 1, 2, , là các giá trị riêng biệt của I(s) và L(s) tương ứng được giả thiết phù hợp với mọi s thuộc T. Cho p(xi, yj) và pn(xi, yj) là mật độ và phân bố xác suất mẫu của I(s) và L(s), nghĩa là, tỷ lệ câu s thuộc T và Tn mà I(s) và L(s) của chúng bằng xi và yj , i, j = 1, 2, Cho Fc(xi, yj) được xác định trong giới hạn của Fc(s), nghĩa là, Fc(xi, yj) =1 nếu xi > cyj v.v Sau đó, đối với Tn , I (F n ) n x F n (x ,y )p (x ,y ) , (5) n c  i c i j n i j trong đó lấy tổng đối với tất cả giá trị có thể của i và j. Do đó, đối với T, I (F n )  I(T) N x F n (x ,y )p(x ,y ) p (x ,y ) (N / n)I (F n )  I(T ) n c  i c i j i j n i j n c n (6) N I(Tn ) / n I(T) / N Thành phần thứ hai ở vế phải của (6) bằng 0. Bằng luật số lớn đối với các biến ngẫu nhiên độc lập và phụ thuộc ([8]) vì n tăng vô hạn, I(Tn)/ n tiến tới I(T)/ N theo xác suất và đối với xi và yj cố định, pn(xi, yj) tiến tới p(xi, yj) theo xác suất. Vì chỉ có một số xi và yj riêng biệt hữu hạn, thành phần thứ nhất ở vế phải của (6) tiến tới 0 về xác suất. Như vậy, I (F n )tiến tới . I(T) về xác suất. Bằng cách tương tự chúng ta thiết lập n c mệnh đề về L(F n ) . c Nhận xét 3 Vì F n và F n có dạng (3), đối với mỗi một n chúng có các hàm trích rút tối ưu khi c c áp dụng vào T. Định lý 3 phát biểu nếu n đủ lớn, chúng ta có thể kỳ vọng hầu như chắc chắn I (F n )và L(F n ) gần tới . I(T) và  . L(T). Một người nào đó có thể hỏi tại sao n c c không định nghĩa  = N/ n,  = N/ n và dùng các đoạn trích rút nhận được bằng cách áp dụng F n và F n cho T , vì I (F n )   I(T ) , L(F n )   L(T ) và   I(T ) và c c n n c n c n n   L(T ) tiến tới . I(T) và  . L(T) về xác suất. Câu trả lời là trừ khi F n và F n được n c c áp dụng vào T, các đoạn trích rút được sản xuất không phải là tối ưu đối với T. Một sự lựa chọn cho bài toán ước lượng là giả thiết rằng p(x,y) có thể được xấp xỉ bởi một hàm liên tục hai chiều f(x,y,) trong đó  là một tham số (vô hướng hoặc . . vector). Các yêu cầu I(Fc ) = I(T) và L(Fc) =  L(T) trở thành 6
7. x F (x,y)f(x,y,) dxdy x f(x,y,) dxdy c (7) x F (x,y)f(x,y,) dxdy  x f(x,y,) dxdy c  Đối với và  cho trước, c và c là hàm của , tức là c () và c(). Bây giờ,  có thể được ước lượng bằng cách lấy một mẫu câu ngẫu nhiên. Cho  là một ước lượng của , sau đó c (  ) và c(  ) là ước lượng của c () và c() tương ứng. Bài toán ước lượng p và p không tăng lên ở trường hợp này, vì xác suất của x = cy bằng 0. Ở đây, dường như hợp lý giả sử p(x,y) có thể được xấp xỉ bằng một phân bố chuẩn hai chiều. Để đơn giản hoá tính toán, chúng tôi giả sử tương quan giữa x và y bằng 0, hoặc 2 2 2 2 (x 1 ) / 1 (x 2 ) / 2 f(x,y,) (1/ 2 1 )e (1/ 2 2 )e (8) 2 2 Ở đây,  = (1, 2, 1 , 2 ) là một vector 4 chiều. Bổ đề Đối với và  cho trước, 0 ,  1, cho c và c thoả mãn (7) trong đó f(x, y, F) được cho bởi (8). Sau đó, 2 2 2 2 2 2 2 2 2 2 1 / 1 c 2 g (c 2 1) / 1 c 2 1G (c 2 1) / 1 c 2 1 (9.1) 2 2 2 2 2 2 2 2 2 2 c2 / 1 c2 g (1 c2 ) / 1 c2 2G (1 c2 ) / 1 c2 (1 )2 (9.2) trong đó: 2 g(x) (1/ 2 )e x / 2 vµ G(x) g(t)dt (9.3) x Hơn nữa, nếu 0 > 1 và 2 >> 2, nghĩa là, 1 và 2 lớn hơn nhiều 1 và 2 thì c , c > 0 Từ bổ đề, chúng ta nhận thấy nói chung không thể tìm được c và c trong phạm vi của  rõ ràng, dù đối với  cho trước, các giá trị tương ứng của c và c có thể nhận được bằng tích phân số. Tuy nhiên, các xấp xỉ đối với c và c có thể nhận được dưới các điều kiện hợp lý chung. Chúng ta có Định lý 4 Nếu 0 ,  1 và c và c thoả mãn (9.1) và (9.2) trong bổ đề thì c 1/ 2 hoặc c (1 + d 1) / 2 và c 1/ 2 hoặc c (1 - d1- 1) / 2, 7
8. trong đó G(d ) = , G(d1-) = 1 -  và G(x) được cho bởi (9.3). Nếu 1 >> 1 >> 2 , nghĩa là, 1 lớn hơn nhiều 1 và 1 lớn hơn nhiều 2 thì cận dưới đối với c và cận trên đối với c có thể được sử dụng như xấp xỉ đối với c và c tương ứng. Chứng minh: Nếu c 2 - 1 0 thì c 1/ 2. Mặt khác, từ (9.1), chúng ta nhận thấy nếu c 2 2 2 2 - 1 0, G (c 2 1) / 1 c 2 G(c 2 1) / 1 Do đó, (c 2 - 1)/ 1 d và c (1 + d 1) / 2 . Hơn nữa, nếu 1 >> 1 >> 2 , 2 2 2 2 chúng ta có thể xấp xỉ 1 c 2 bằng 1 và xoá thành phần thứ nhất ở vế trái của (9.1). Tiếp theo, (1 + d 1) / 2 là một xấp xỉ đối với c . Bẵng cách tương tự chúng ta chỉ ra mệnh đề liên quan đến c . Nhận xét 4 Điều kiện 1 >> 1 >> 2 , nghĩa là sự thay đổi về độ dài câu nhỏ hơn nhiều so với sự thay đổi về nội dung thông tin, mà nó lại nhỏ hơn nhiều so với nội dung thông tin trung bình của các câu. Các điều kiện dường như hợp lý đối với các ứng dụng thực tế. Các loại xấp xỉ khác đối với c và c cũng có thể nhận được. Bây giờ, chúng ta đi đến bài toán ước lượng. Để ước lượng  trung bình và độ lệch chuẩn  của một phân bố chuẩn, các phương pháp khác nhau có sẵn ([4], [7]). Giả sử một mẫu n câu ngẫu nhiên được rút ra bằng phép thay thế và các giá trị I(s) và L(s) n n n 2 là xi và yi , i = 1, 2, , n. Cho x  x i / n, y  y i / n vµ S a n (x i x) / n , i 1 i 1 i 1 trong đó a n n / 2((n 1) / 2) / (n / 2) vµ (x) là hàm Gamma. Chúng ta có: Định lý 5 Nếu 1 >> 1 >> 2 thì c (x d S1 ) / y vµ c (x d1 S1 ) / y là các ước lượng vững của c và c theo nghĩa là c và c tiến tới c và c về xác suất khi n . Chứng minh: x , y và S1 là các ước lượng vững của 1, 2 và 1 tương ứng ([4]). Theo định lý Slutsky, chúng ta nhận thấy c và c tiến tới c và c về xác suất. 4. ĐÁNH GIÁ VỀ THÔNG TIN VÀ ĐỘ DÀI Ở các mục trước, chúng tôi định nghĩa và đề xuất một số phương pháp để nhận được các tóm tắt tối ưu. Tuy nhiên, trước khi áp dụng các phương pháp này, chúng ta 8
9. phải biết cách đánh giá thông tin và độ dài của một câu. Tiếp theo, chúng tôi duyệt lại một số phương pháp nổi tiếng nhằm đánh giá các đại lượng và đề xuất một số phương pháp mới cùng với một phương pháp ước lượng cho đánh giá thông tin. Độ dài L(s) của câu s dường như đánh giá tương đối dễ. Chẳng hạn, chúng tôi có thể định nghĩa L(s) là số từ hoặc chữ chứa trong s. Hình thành các cách đánh giá L(s) khác là khá khó khăn, dù cho xác suất không nên bị loại bỏ không có khảo sát sâu hơn. Mặt khác, thông tin I(s) chứa trong s rõ ràng không đến mức dễ đánh giá. Nói ngắn gọn, đề xuất được mô tả sau đây: 1. I(s) là một hàm thông tin I(w) chứa trong từ w của s. 2. I(w) có thể được định nghĩa là tích F(w) và G(w), trong đó F(w) là tần suất xuất hiện tương đối của w trong văn bản cho trước T và G(w) là trọng số của w. Hàm F(w) được định nghĩa là tỷ số của tần suất xuất hiện của w trong T với tần suất của w trong tất cả tài liệu, hoặc hạn chế hơn, tất cả tài liệu của loại nhất định thuộc về T. Như vậy, các từ thông thường như the, and, v.v không có tần suất tương đối cao, vì chúng xuất hiện khắp nơi với khoảng tần suất như nhau. Chúng cũng không chứa nhiều thông tin. Mặt khác, nếu từ tóm tắt xuất hiện thường xuyên trong một tài liệu nhất định, chỉ thị tài liệu hầu như chắc chắn liên quan gần với tóm tắt. Do đó, dường như hợp lý giả thiết I(w) tỉ lệ với F(w). Khái niệm tần suất tương đối là do Edmundson và Wylls đưa ra và là sự cải tiến về khái niệm tần suất của Luhn. Trọng số của một từ chắc chắn là một đánh giá về ý nghĩa thực chất của nó. Chẳng hạn, nó được đề xuất bởi Edmundson và Wylls, nếu một từ mang tiêu đề hoặc chỉ thị tóm tắt (như là tóm tắt, kết luận, v.v ), nên được cho một trọng số tương đối cao, dù cho nó có thể xuất hiện chỉ ít lần trong văn bản. Nó được coi là một loại trọng số chủ quan, nên được đưa vào. Chẳng hạn, nếu người nào đó quan tâm đến tập hợp tất cả định lý đã chứng minh trong một bài báo toán học, anh ta nên gán trọng số cao cho từ định lý, như vậy, anh ta có thể tin chắn tất cả định lý sẽ được trích rút. Mặt khác, nếu anh ta chỉ muốn một tóm tắt ngắn, sự mô tả về một định lý có thể là quá dài để được trích rút. Ở trường hợp này, không có một trọng số cao nào cần được gán cho từ định lý. Bây giờ, chúng tôi đi đến bài toán đánh giá I(s): I(s) nên là một hàm của I(w). Nhưng loại hàm gì ? Luhn đề xuất I(s) nên là một hàm của phân bố của các từ có nghĩa, tức là, với I(w) bên trong câu. Như vậy, các câu chứa các từ biệt lập có nghĩa không được coi là có nghĩa. Một câu s có nghĩa và I(s) tương ứng nên lớn chỉ nếu nó chứa cụm từ có nghĩa. Người ta khó phát biểu loại quan hệ hàm gì thực sự tồn tại giữa I(s) và I(w) trong đó w s. Từ quan điểm lý thuyết, chúng ta đưa ra các mẫu sau đây về đánh giá I(s): 9
10. I(s) Max I(w), I(s) Min I(w), vµ I(s)  I(w) w s w s w s Nếu công thức thứ nhất được dùng, một câu có ý nghĩa nếu một trong số từ của nó có ý nghĩa. Nếu công thức thứ hai được dùng, một câu có ý nghĩa chỉ nếu tất cả từ của nó có ý nghĩa. Nếu công thức cuối cùng được dùng và L(s) được định nghĩa là số từ chứa trong s, thì I(s)/ L(s) là thông tin trung bình chứa trong một từ của s. Tới một mức độ nhất định, đại lượng này tương thích với đánh giá ý nghĩa một câu của Luhn. Để kết luận, chúng tôi cho một phương pháp ước lượng tần suất xuất hiện p của từ w trong một văn bản T cho trước. Sau đó, dựa vào ước lượng p, chúng tôi có thể ước lượng I(w) vì tần suất xuất hiện w trong tất cả tài liệu và trọng số G(w) của w có thể giả sử biết rõ. Hơn nữa, chúng tôi có thể ước lượng I(s) đối với một đánh giá I(s) cho trước. Các phương pháp ước lượng giá trị p nên quan tâm thực hành, vì tìm giá trị thực có thể mất thời gian. Cho tổng số câu và từ chứa trong T là N và M tương ứng. Giả sử một mẫu ngẫu nhiên có n câu được rút ra có hoặc không có thay thế. Đối với một từ cho trước w, cho xi bằng số xuất hiện w trong câu thứ i ở mẫu. Định nghĩa n x xi . Dễ dàng nhận thấy Nx/ nM là một ước lượng không chệch p. Đối với E(Nx/ i 1 nM) = (N/ M) E(xi) = p ([4], [7]). 5. KẾT LUẬN Ở mục 2, chúng tôi đưa vào khái niệm tóm tắt và trích rút tối ưu. Hai loại tóm tắt và trích rút tối ưu được định nghĩa, nghĩa là, độ dài cực tiểu và tóm tắt và trích rút thông tin cực đại (định nghĩa 1 và 3). Để nhận được trích rút tối ưu, sử dụng hàm trích rút ngẫu nhiên được đề xuất ở định nghĩa 2. Ở định lý 1, chúng tôi trình bày các hàm trích rút tối ưu phải có một dạng nhất định. Ở định lý 2, chúng tôi trình bày đối với và  cho trước, 0 ,  1, tồn tại độ dài cực tiểu và các hàm trích rút thông tin cực đại sinh ra đoạn trích rút mà nội dung thông tin và độ dài liên quan của nó về trung bình bằng và  tương ứng. Ở mục 3, trước tiên chúng tôi thảo luận cách xác định chính xác các hàm trích rút tối ưu tương ứng với và  theo ngữ cảnh trên. Tiếp theo, chúng tôi thảo luận cách tiết kiệm thời gian và cố gắng tìm kiếm các hàm trích rút tối ưu chỉ tương ứng gần đúng với và . Hai loại phương pháp được đề xuất, phụ thuộc vào bản chất của phân bố thông tin chứa đựng các câu của văn bản cho trước và độ dài. Nếu phân bố là siêu bội hoặc đa thức, chúng tôi trình bày ở định lý 3 tồn tại các hàm trích rút mẫu hội tụ xác suất tới hàm trích rút tối ưu thực vì kích thước mẫu tăng lên. Nếu phân bố có thể được xấp xỉ bởi một phân bố chuẩn, chúng tôi trình bày ở định lý 4 và 5 có thể xác định và ước lượng bằng cách lấy mẫu ngẫu nhiên, các hằng số xác định các hàm trích rút tối ưu thực. Dưới các điều kiện chung hợp lý, các công thức xấp 10
11. xỉ đơn giản nhận được. Ở mục 4, chúng tôi thảo luận các phương pháp đánh giá thông tin chứa trong một câu và độ dài câu. TÀI LIỆU THAM KHẢO [1] Arms W.Y., Digital Libraries, MIT Press, Cambridge, 2003. [2] Chen H., Houston A.L., Digital Libraries: social issues and technological advances, Advanced in Computers 48, 1999, pp. 257-314. [3] Chowdhary G.G., Digital Library Research: major issues and trends, Journal of Documentation 55(4), 1999, pp. 409-448. [4] Cramér H., Phương pháp toán học trong thống kê, 2 tập, Nxb Khoa học và kỹ thuật, Hà Nội, 1970. [5] Nguyễn Đức Dân, Đặng Thái Ninh, Nhập môn thống kê ngôn ngữ học, Nxb Giáo dục, Hà Nội, 1998. [6] Nguyễn Đức Dân, Đặng Thái Ninh, Thống kê ngôn ngữ học – một số ứng dụng, Nxb Giáo dục, Hà Nội, 1999. [7] Trần Tuấn Điệp, Lý Hoàng Tú, Lý thuyết xác suất và thống kê toán học, xuất bản lần 3, Nxb Giáo dục, Hà Nội, 1999. [8] Feller W., An Introduction to Probability Theory and Its Applications, vol.1, 3rd Edition, John Wiley, New York, 1971. [9] Đào Hữu Hồ, Nguyễn Văn Hữu, Hoàng Hữu Như, Thống kê toán học, Nxb Đại học và trung học chuyên nghiệp, Hà Nội, 1984. [10] Fox E.A., Advanced Digital Libraries, Virginia Polytechnic Institue and State University, 2000. [11] Journal of Network and Computer Applications, Special Issue of JNCA on Digital Libraries 20 (1-2), 1997. [12] Lesk M., Practical Digital Libraries, Morgan Kaufmann, San Francisco, 1997. [13] Mendelhall W., Sincich T., Statistics for the Engineering and Computer Science, 2nd Edition, Collier Macmillan, London, 1989. [14] Ross S.M., Probability Models for Computer Science, Harcourt Academic Press, San Diego, 2002. [15] Sun Microsystems, Digital Library Technology Trends, 2002. 11
12. SUMMARY ABSTRACTING AND EXTRACTING TEXT DOCUMENTS IN DIGITAL LIBRARIES This article presents some results of a theoretical study of abstracting and extracting text documents in digital libraries. Our approach is the use of statistical sampling and estimation of text document. We introduce the concept of optimal abstracting and extracting. Two types of optimal abstracts and extracts are defined: minimum lenth and maximum information abstracts and extracts (definitions 1 and 3). Next we suggest a randomized extracting function to obtain optimal extracs (definition 2). In theorem 1, we show that extracting function must have a certain form. In theorem 2, we show that for given and , 0 ,  1, there exist minimum length and maximum information extracting function. In section 3, we dicuss how to determine exactly optimal extracting functions corresponding to and . Then we discuss how to save some time and effort by finding optimal extracting functions which correcpond approximately to and . We suggest two types of methods. If the distribution is hypergeometric or multinomial, we show that in theorem 3 there exist example extracting functions which converge in probability to actual optimal extracting functions. If the distribution may be approximated by a normal distribution, we show in theorem 4 and 5 that it is possible to determine and estimate the contants by random sampling. Finally, we discuss methods for measuring the information contained in and the length of a sentence. 12