Giới thiệu về nghiên cứu Bài viết này trình bày một phương pháp phân loại văn bản mới bằng cách sử dụng tất cả các chuỗi con như các đặc trưng. Trong các phương pháp truyền thống, một chuỗi con hiệu quả cho việc phân loại văn bản thường là những từ hoặc ngữ tách được lấy ra trong quá trình phân tích từ. Số lượng của tất cả các chuỗi con là lũy thừa cơ số 2 với chiều dài của văn bản, và một phương pháp học máy bằng cách sử dụng tất cả các chuỗi con này đòi hỏi một chi phí tính toán cực lớn.
Nghiên cứu này chứng minh rằng có thể tính toán tất cả các chuỗi con một cách hiệu quả bằng cách kiểm tra chuỗi con cực đại, những chuỗi con này được liệt kê trong thời gian tuyến tính bằng cách sử dụng các mảng hậu tố nâng cao (suffix array). Nghiên cứu sử dụng chuẩn L_1 để có được một kết quả học tập nhỏ gọn. Chúng tôi cho thấy rằng nhiều đặc trưng truyền thống (tf idf, kết quả từ phân tách từ ngữ ) có thể được bao gồm trong phương pháp này một cách tự nhiên. Trong các thực nghiệm, kết quả cho thấy rằng mô hình này có thể trích ra một chuỗi hiệu quả, và có độ chính xác phân loại cao hơn so với sử dụng BOW truyền thống.
Nghiên cứu này thực sự là 1 nghiên cứu thú vị và có tính ứng dụng rất cao. Hy vọng sẽ sớm có ứng dụng phân loại văn bản tiếng Việt từ phương pháp này.
Download / Download
Ghi chú :
- Mô hình hồi qui Logistic (L1-LR) dạng chính tắc L1
- Máy phân loại đa lớp.
- Đặc điểm của dạng chính tắc L1 : rất nhiều trọng số bằng 0. Những trọng số này sẽ được coi là không cần thiết, và có thể loại bỏ để giảm kích thước máy phân loại.
- Kết hợp với Grafting để tăng tính hiệu quả cho việc học máy và sinh ra nhiều hơn các trọng số bằng 0.
- Mảng hậu tố nâng cao (enhanced suffix array):
- Cấu trúc dữ liệu Trie : dạng cấu trúc sử dụng khá nhiều trong các thao tác chuỗi, kí tự và văn bản. Ưu điểm là tốc độ xử lý nhanh và hiệu quả, nhưng lại khá tốn bộ nhớ ( thường khoảng 20 lần độ dài văn bản ).
- mảng hậu tố nâng cao ESA : tổ hợp của mảng hậu tố SA và LCP (Longest Common Prefix), có ưu điểm là sử dụng ít bộ nhớ hơn ( khoảng 9 lần ) nhưng vẫn đảm bảo tốc độ tương đương Trie trong 1 số thao tác cơ bản.
- Burrows Wheeler's transform (BWT) : có nhiều thuật toán để giải bài toán này với những độ phức tạp khác nhau như O(N), O(NlogN), O(NloglogN) , nhưng thực tế với xử lý ngôn ngữ, thì thường sử dụng thuật toán NlogN vì tốc độ khá nhanh và tiết kiệm bộ nhớ.
- Chuỗi con cực đại :
- Trong 1 văn bản luôn có 1 nhóm các kí tự luôn đi cùng nhau, ví dụ : "độc lập tự do". Những chuỗi này sẽ bị tính nhiều lần, ví dụ : "độc lập tự", "lập tự do" sẽ luôn có cùng số lần xuất hiện với "độc lập tự do", hay nói cách khác : vị trí xuất hiện của những nhóm chuỗi con này luôn trùng nhau.
- Chuỗi con cực đại là chuỗi con dài nhất trong những chuỗi con trên. Ở ví dụ trên, chuỗi con cực đại có độ dài bằng 4, "độc lập tự do".
- Phương pháp nãy sẽ rất hiệu quả với những từ mới như danh từ riêng, các nhóm từ ghép, ...
- Sử dụng ESA có thể lấy ra một cách hiệu quả những chuỗi con cực đại xuất hiện 2 lần.
|
|
