Gzip và KNN vượt qua Transformers trong phân loại văn bản
(twitter.com/LukeGessler)- Đề xuất một phương pháp phân loại văn bản phi tham số (non-parametric), kết hợp bộ nén đơn giản như gzip với bộ phân loại k-láng giềng gần nhất (kNN)
- Không có bất kỳ tham số huấn luyện nào nhưng vẫn nhẹ và đa dụng, với chi phí tính toán thấp hơn so với DNN
- Đạt kết quả cạnh tranh trên 6 bộ dữ liệu in-distribution so với các phương pháp học sâu không được tiền huấn luyện
- Vượt qua BERT trên toàn bộ 5 bộ dữ liệu OOD (out-of-distribution), bao gồm 4 ngôn ngữ ít tài nguyên
- Thể hiện hiệu năng tốt ngay cả trong môi trường few-shot, nơi dữ liệu gắn nhãn quá ít khiến việc huấn luyện DNN trở nên khó khăn
Bối cảnh và vấn đề đặt ra
- DNN được sử dụng rộng rãi trong phân loại văn bản nhờ độ chính xác cao
- Tuy nhiên, chúng đòi hỏi hàng triệu tham số và lượng lớn dữ liệu gắn nhãn, nên chi phí tính toán cao
- Vì vậy, việc sử dụng, tối ưu hóa và chuyển giao sang các tình huống OOD (out-of-distribution) trở thành những tác vụ tốn kém trong thực tế
Phương pháp đề xuất
- Đưa ra một phương pháp phi tham số dễ dùng, nhẹ và đa dụng thay thế cho DNN
- Có cấu trúc kết hợp bộ nén đơn giản như gzip với bộ phân loại k-láng giềng gần nhất
- Đặc điểm cốt lõi là hoàn toàn không có tham số huấn luyện
Kết quả thử nghiệm
- Hiệu năng ở mức có thể cạnh tranh với các phương pháp học sâu không được tiền huấn luyện trên 6 bộ dữ liệu in-distribution
- Vượt qua BERT trên toàn bộ 5 bộ dữ liệu OOD, bao gồm 4 ngôn ngữ ít tài nguyên
- Có lợi thế ngay cả trong môi trường few-shot, nơi dữ liệu gắn nhãn quá ít để huấn luyện DNN một cách hiệu quả
1 bình luận
Bình luận trên Hacker News
Link trực tiếp tới bài báo: https://aclanthology.org/2023.findings-acl.426.pdf
Về mặt trực giác, cốt lõi là khi có các tài liệu x1, x2 và tài liệu mới x, nếu tính quy luật thống kê của x gần với x1 hơn x2 thì
len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)). Ở đâycatlà phép nối chuỗi, còncompresslà bộ nén như gzipNói đúng ra,
len(compress(cat(x1,x))) - len(compress(x))là số byte bổ sung cần thiết để nén tính quy luật thống kê của x1 khi đã biết tính quy luật thống kê của x. x1 và x càng giống nhau thì số byte tăng thêm để néncat(x1,x)so với chỉ nén x sẽ càng ítCác tác giả dùng một hàm khoảng cách gọi là Normalized Compression Distance (NCD) dựa trên ý tưởng này, rồi áp dụng k-láng giềng gần nhất (kNN) lên các tài liệu đã nén. Bài viết cũng đề cập mối liên hệ giữa NCD với thông tin, entropy Shannon và độ phức tạp Kolmogorov
Điều đáng ngạc nhiên là phương pháp đơn giản và trực quan này lại vượt BERT trong nhiều tác vụ phân loại zero-shot. Tuy vậy, điều đó không có nghĩa là nó nhất định thắng cả các Transformer lớn hơn và mới hơn
Tức là so sánh kích thước nén khi dùng tài liệu làm từ điển nén và khi không dùng. zstd, ít nhất ở mức 20+, cho tỷ lệ nén cao hơn gzip rất nhiều, nên nếu lý do gzip hiệu quả là vì nó xấp xỉ độ phức tạp Kolmogorov thì có thể cách này còn hoạt động tốt hơn
Nếu x1 là tiếng Anh còn x là bản dịch tiếng Do Thái của cùng một tài liệu, tôi đoán LLM sẽ làm tốt hơn chứ
Gần đây tôi thử xử lý ảnh và xuất JPEG, và nhận ra từ cùng một tập pixel nền tảng có thể tạo ra rất nhiều hình ảnh khác nhau. Điều thú vị là ảnh càng nhiều nhiễu và càng ngẫu nhiên thì file JPG càng lớn, còn càng trông giống ảnh chụp thì kích thước JPG lại càng nhỏ
Nếu bạn quan tâm đến tính tương đương giữa AI và nén, hãy xem Hutter Prize :) http://prize.hutter1.net/
Large Text Compression Benchmark cũng rất đáng xem http://mattmahoney.net/dc/text.html - hiện bộ nén tốt nhất thế giới là một mạng nơ-ron của Fabrice Bellard, người nổi tiếng vì đã tạo ra ffmpeg và QEMU
Tôi cũng thực sự thích phong cách chỉ-văn-bản phù hợp của những trang như thế này
Chúng điều chỉnh mã hóa số học(https://en.wikipedia.org/wiki/Arithmetic_coding) tùy theo ngữ cảnh của byte/bit cần dự đoán, nên dự đoán phần tiếp theo càng chính xác thì mã hóa càng hiệu quả. Bản thân tác vụ này rất giống Transformer như GPT
Nếu dự đoán hoàn hảo, khoảng số học sẽ không thu hẹp lại nên gần như không có chi phí lưu trữ bổ sung, và vì thế cũng không cần lưu bit nào. Tuy nhiên, để benchmark công bằng thì cũng phải tính cả kích thước của bộ giải nén
Đây là một ý tưởng khá cũ, xem [1,2] là được. Cũ nhưng vẫn cực kỳ hữu ích, giống như perceptron
[1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
[2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
Lý thuyết giống như một câu chuyện giải thích được nhiều thứ chỉ với cùng một số “nhân vật”. Ở đây các nhân vật gần với khái niệm hơn, ví dụ như nguyên tử
Tôi muốn chỉ ra rằng việc phương pháp này mạnh hơn chỉ giới hạn trong tin tức
Trên Yahoo Questions, nó không phải tốt nhất. Tin tức thường được viết theo kiểu tương tự nhau và đôi khi còn sao chép một phần, nên không quá vô lý khi cho rằng chúng có nhiều từ chung
Yahoo Questions là diễn đàn nên biến thể từ vựng sẽ lớn hơn, nhưng giữa các từ lại có sự tương đồng về ngữ nghĩa
Nói cách khác, gzip mạnh khi có nhiều từ chồng lấp (mức tăng kích thước khi nén bằng gzip nhỏ), còn khi sự tương đồng ngữ nghĩa quan trọng thì DNN luôn thắng
Kết quả này thú vị, nhưng theo tôi không thú vị đến mức như cách nó được nói tới
Điều rất quan trọng là phải nhìn nhận rằng kết quả này đến từ dữ liệu ngoài phân phối. Ví dụ là tin tức bằng các ngôn ngữ như ‘Kinyarwanda, Kirundi, Pinyin’
Trong các thiết lập phổ biến hơn, BERT vẫn thắng áp đảo
Thật tuyệt khi một phương pháp đơn giản như vậy có thể hiệu quả đến thế, nhưng không nên thổi phồng quá mức
Nhưng nhìn vào các điều kiện được trích dẫn thì ngược lại khá trực quan. Phân loại văn bản trong một ngôn ngữ hoàn toàn xa lạ thực chất là gì? Nếu bảo bạn phân loại văn bản Kirundi, bạn hoàn toàn không biết ý nghĩa của nó, và điều tốt nhất bạn có thể làm là tìm tần suất của các chuỗi từ hoặc ký tự rồi nhóm những văn bản có “dấu vân tay” tần suất tương tự nhau lại
Bạn vẫn không biết nghĩa thực sự, nhưng vẫn có thể làm tốt hơn ngẫu nhiên, và thực tế đúng là như vậy. Tin tốt là đó chính xác là điều gzip+kNN làm, đó là chuyên môn cốt lõi và lý do tồn tại của chúng
Nếu cố đọc và hiểu văn bản này hoặc cố dự đoán ký tự tiếp theo thì bạn cũng không thu được mấy. Một người bình thường, vì không biết ngôn ngữ đó, ngay từ đầu đã chẳng thèm thử. Đáng tiếc là BERT lại làm đúng việc đó. Vì đó là việc duy nhất BERT biết làm. Dù vậy, việc nó còn khai thác được nhiều giá trị hơn cả một con người bình thường, có lẽ cả con người không bình thường nữa, vẫn đáng được chúc mừng
Thực sự rất thông minh và cũng dễ hiểu theo trực giác
Nếu ghép hai đoạn văn bản tương tự nhau lại, chúng sẽ được nén tốt hơn so với khi ghép hai đoạn văn bản khác nhau
Điều này có vẻ không hẳn là chiến thắng của phương pháp đó, mà gần hơn với một tín hiệu tiêu cực về độ tương đồng dựa trên deep learning
Trong làn sóng cuồng nhiệt quanh LLM, đúng là LLM rất ấn tượng, nhưng có vẻ nhiều người đang mặc định rằng cũng đã có tiến bộ tương tự ở các lớp embedding chỉ dùng cho độ tương đồng văn bản thuần túy
Vì thế mới có cơn sốt đủ loại cơ sở dữ liệu embedding, nhưng theo tôi thì hầu như không có bằng chứng nào hậu thuẫn điều đó
Liên kết nên trỏ tới bản PDF của bài báo là https://aclanthology.org/2023.findings-acl.426.pdf
Thuật toán nén là sự tiết kiệm/nén không gian, tức bit và byte. Mô hình học máy, đặc biệt là mô hình sinh, là sự tiết kiệm/nén biểu đạt và tư duy của con người
Phân loại văn bản là một dạng nén trên biểu đạt của con người. Liệu có tồn tại một thuộc tính nền tảng nào đó của ngôn ngữ và dữ liệu loài người có thể giải thích cái nào sẽ làm tốt hơn trong các tác vụ học máy?
Nếu một ngày nào đó một lý thuyết như vậy thành hình, thì có lẽ sẽ không còn quá ngạc nhiên khi cách mã hóa các bit/byte đã nén và biểu đạt con người đã nén lại liên hệ chặt chẽ với nhau trong một kiểu không gian nào đó, để rồi hai thứ ấy bằng cách nào đó được kết nối. Trên thực tế, những lý thuyết như vậy, chẳng hạn lý thuyết dựa trên entropy hoặc dựa trên vật lý, có thể giúp chọn nên dùng thuật toán nén hay mô hình học máy cho những loại nén biểu đạt con người nhất định
Nhìn theo hướng dữ liệu, các ví dụ âm khó khiến loại thuật toán này hoạt động kém sẽ là gì? Có lẽ hiện tại ta chỉ có thể xấp xỉ lý thuyết đó từ góc độ các loại dữ liệu văn bản khác nhau của con người. Ví dụ, dự đoán hỗn hợp bằng mô hình chủ đề thống kê hoạt động tốt với văn bản học thuật nhưng gặp khó khăn với văn bản trên internet
Ngoài Wolfram Physics ra, có ai nghiên cứu kiểu lý thuyết này không?
https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
Hoàn toàn hợp lý. Nén là về việc “hiểu”, tức biểu diễn đầu vào theo cách có thể nhận diện và gắn nhãn được
Nếu phần bit đã được nhận diện lớn hơn nhãn thì bùm, bạn có nén. Việc gzip có thể làm tốt hơn DNN trong tác vụ này không có gì đáng ngạc nhiên
Tôi gọi đó là tập con vì hiểu mang tính tổng quát hơn. Một thuật toán nén cụ thể có thể hoạt động tốt với số dấu phẩy động. Ngược lại, não bộ và mạng nơ-ron nhân tạo, dù hiệu năng có thể kém hơn, có lẽ lại có thể nén bất kỳ kiểu mẫu đầu vào nào
Tôi không hiểu gzip có thể xử lý những từ như “not”, thứ có thể đảo ngược ý nghĩa của cả câu, theo cách nào
Có ai hiểu không?