- Một thử nghiệm đưa bài toán phân loại chữ số viết tay MNIST lên khoảng 78% độ chính xác chỉ bằng nén GZIP và k-láng giềng gần nhất (k-NN), cho thấy nén có thể được dùng như một công cụ phân loại không cần mô hình
- Tính khoảng cách nén chuẩn hóa (NCD) dựa trên việc độ dài thay đổi ra sao khi nén chung hai mẫu ảnh, rồi dùng nó làm chỉ số đo độ tương đồng giữa các ảnh
- Mỗi mẫu kiểm thử được so sánh với 100 mẫu huấn luyện, và nhãn đa số của k=5 láng giềng có khoảng cách gần nhất trở thành giá trị dự đoán
- Do chi phí tính toán, độ chính xác được đo trên một phần ảnh kiểm thử thay vì toàn bộ tập kiểm thử; dùng toàn bộ tập có thể cho đánh giá chính xác hơn
- Trong ví dụ công khai vẫn còn một lỗi refactor: tạo cache độ dài nén nhưng không dùng trong phép tính NCD thực tế, nên cần loại bỏ cache hoặc phản ánh nó vào
compute_ncd
Phân loại MNIST bằng GZIP + k-NN
- Thử nghiệm phân loại tập dữ liệu chữ số viết tay MNIST bằng tổ hợp GZIP + k-NN
- Ví dụ mã ngắn dùng độ dài kết quả của
gzip.compress(z.tobytes())làm độ dài nén, tính NCD, rồi chọn nhãn xuất hiện nhiều nhất trong 5 láng giềng gần nhất - Ví dụ có thể chạy nằm trong Jupyter Notebook
- Mục tiêu không phải là đạt độ chính xác cao nhất, mà là kiểm chứng đơn giản ý tưởng dùng nén như một công cụ phân loại không cần mô hình
- Đoạn mã chưa đến 10 dòng giống một yếu tố code golf để tạo sự thú vị hơn là phần cốt lõi của thử nghiệm
Cách tính độ tương đồng và quy trình phân loại
- NCD đo độ tương đồng bằng cách chuẩn hóa mức chi phí khi nén chung hai điểm dữ liệu khác ra sao so với khi nén riêng từng điểm
- Độ dài nén được tính theo dạng sau
Cx1 = len(gzip.compress(x1.tobytes()))Cx2 = len(gzip.compress(x2.tobytes()))Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
- Công thức NCD có dạng
(Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2) - Việc phân loại tính khoảng cách giữa từng ảnh kiểm thử và các ảnh huấn luyện, sắp xếp theo thứ tự gần nhất, rồi dùng biểu quyết đa số của 5 ảnh gần nhất
- Trong thử nghiệm, việc so sánh dựa trên 100 mẫu huấn luyện, và do chi phí tính toán nên tập kiểm thử cũng chỉ dùng một phần
Ý tưởng tham khảo và lưu ý trong mã
- Cách tiếp cận này được lấy cảm hứng từ bài viết text generation from data compression và bài báo parameter free text classification
- Sau khi viết bài, tác giả cũng phát hiện bài MNIST by ZIP do Andreas Kirsch viết năm 2019 theo cách tương tự
- Mã ví dụ tạo sẵn cache độ dài nén của các mẫu huấn luyện, nhưng trong vòng lặp thực tế lại không dùng giá trị cache đó
- Cả phiên bản thông thường lẫn phiên bản được làm rối đều tạo
compressed_lengthshoặccls, nhưng không dùng độ dài đã cache trong phép tính NCD - Nếu loại bỏ cache và dùng trực tiếp
training_set, hoặc sửacompute_ncdđể tận dụng giá trị cache, thì ý đồ của mã và phần triển khai sẽ khớp nhau hơn
- Cả phiên bản thông thường lẫn phiên bản được làm rối đều tạo
1 bình luận
Các ý kiến trên Hacker News
Khi thử thay hàm khoảng cách trong mã bằng một thước đo đơn giản hơn, khoảng cách GZIP trong phân loại MNIST vừa có độ chính xác thấp hơn, vừa tốn tính toán hơn nhiều
Khoảng cách Gzip: khoảng 3 phút, độ chính xác 78% / khoảng cách Euclid: khoảng 0,5 giây, 93% / khoảng cách Jaccard: khoảng 0,7 giây, 94% / độ bất tương đồng Dice: khoảng 0,8 giây, 94%
Jaccard và Dice được đo sau khi nhị phân hóa ảnh
Tôi không quen lắm với thuật toán GZIP, nhưng việc kết quả thấp như vậy khá thú vị, và cũng tò mò liệu một thuật toán nén thiên về hình ảnh có thể tốt hơn không
Bài viết tự thân rất sáng tạo, mã và phần giải thích cũng tốt, nhưng tôi nghĩ các baseline trên giúp bổ sung ngữ cảnh cho điểm số của gzip
NMI skimage: khoảng 30 giây, độ chính xác 95% / NMI numba: khoảng 0,6 giây, độ chính xác 95%
Tôi đã dùng mã
numbado ChatGPT đưa để tính đếm liên hợp 2x2, entropy và thông tin tương hỗ chuẩn hóaCá nhân tôi quan tâm đến việc huấn luyện nhanh CIFAR10, nên cách tiếp cận này có vẻ cũng khá hữu ích ở các miền khác
https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
Thử thêm zstandard thì Zstd(level=3) đạt độ chính xác 88% trong khoảng 3,5 giây, nhanh hơn gzip rất nhiều
Khi tính
Cx1x2, nếu dùng(x1-x2)*2thay vìx1+x2thì zstd tăng lên đến độ chính xác 93%Nếu không cộng hai mảng mà xếp chúng trên dưới nhau thì hiệu năng sụp hẳn xuống dưới 20%, nhưng có vẻ cách đó lại hiệu quả trong phân loại chuỗi, nên khá thú vị
So với các kỹ thuật khác, Linear SVC khoảng 92%, SVC kernel RBF 96,4%, SVC kernel đa thức 94,5%, hồi quy logistic 89%, Naive Bayes khoảng 81%
Nguồn: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
Nhìn các bài viết trên mạng thì có vẻ chỉ K-NN thôi cũng có thể cho kết quả tốt hơn nhiều, nên cũng có thể tác giả đã tự làm việc khó hơn bằng cách dùng gzip
Tôi thích bắt đầu bằng mô hình đơn giản rồi tăng độ phức tạp sau, nhưng thường nghe người ta nói “hồi quy logistic không được” ngay cả với những bài toán mà thực tế nó hoạt động tốt
Khi hỏi họ nghĩ hiệu năng baseline trên MNIST sẽ khoảng bao nhiêu, nhiều người đoán 20–30%
Ngay cả những người làm machine learning cũng thường đánh giá thấp mức lợi ích giảm dần đến nhanh thế nào khi tăng mạnh độ phức tạp mô hình
Trong nhiều trường hợp, nếu mô hình đơn giản cho hiệu năng không tốt thì cũng khó đạt hiệu năng xuất sắc với mô hình phức tạp hơn
Bài báo gốc giới thiệu bộ dữ liệu MNIST cũng đạt độ chính xác khoảng 98%, còn các mạng nơ-ron ngày nay lên tới 99,87%
https://paperswithcode.com/sota/image-classification-on-mnis...
Nén vốn là để làm bài toán khó hơn, và thực tế nó vẫn hoạt động như vậy
Các mô hình khác có xu hướng thêm nhiễu ở đâu đó, nên tôi tự hỏi nếu đưa feature engineering vào trước gzip thì sao
Ví dụ có vẻ cũng có thể áp dụng Gaussian blur và tích chập trước, rồi dùng deep learning để chọn đặc trưng
Mã có thể thanh lịch và ngắn, nhưng độ chính xác 78% trên MNIST là rất tệ
Một mô hình dummy làm bằng TensorFlow cũng dễ dàng đạt độ chính xác 90%, còn mô hình tốt nhất là 99,87%
Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...
Phần thú vị là có thể dùng nén để phân loại mà không cần huấn luyện mô hình
Vì vậy nó khiến ta hỏi liệu có thể dùng các thước đo lý thuyết thông tin khác rẻ hơn và có mất mát hay không
To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review
[https://arxiv.org/abs/2304.09355\)" class="ud link">https://arxiv.org/abs/2304.09355\](https://arxiv.org/abs/2304.09355\)*
Điều thú vị không phải là GZip có đạt hiệu năng tốt nhất hiện đại hay không, mà là thực tế nó phân loại được tàm tạm
Giống như điều đáng ngạc nhiên không phải là một con gấu có tái hiện Mozart hoàn hảo hay không, mà là bản thân việc nó có thể chơi piano
Dù vậy nó vẫn tốt hơn baseline 8 lần và cho thấy nén có thể học biểu diễn
Nếu đổi
compute_ncdsang khoảng cách Euclid thì độ chính xác kiểm thử tăng thêm 15 điểm phần trăm và khối lượng tính toán cũng giảm đáng kểChỉ cần đổi thành kiểu như
distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths]Cuốn sách hay nhất về mối liên hệ sâu sắc giữa lý thuyết thông tin, nén và thuật toán học mà tôi từng đọc là MacKay
Với những người được đào tạo bài bản thì có thể đây là kiến thức phổ thông, nhưng với một người tự học machine learning theo hướng thực hành như tôi, việc thấy chủ đề này còn nối sang các lĩnh vực như vật lý hạt và vũ trụ học đã tạo ra một khoảnh khắc “à ha!” rất mạnh
Tôi để lại bình luận này với hy vọng ít nhất một người cũng có được sự khai sáng tương tự
Tôi khá ấn tượng khi biết rằng nén Lempel-Ziv gốc, một trong các nền tảng của gzip, xuất phát từ nghiên cứu về “độ phức tạp của chuỗi hữu hạn” hơn là đơn thuần là nỗ lực giảm kích thước
https://ieeexplore.ieee.org/document/1055501
Công bằng mà nói, MNIST chỉ cần đưa qua UMAP là đã được tách gần như hoàn hảo
Tôi nghĩ ngày nay muốn có hiệu năng kém trên MNIST thì cũng phải khá cố gắng
https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
Có lẽ đã đến lúc cho bộ dữ liệu này nghỉ hưu; những bộ như QuickDraw hợp lý hơn nhiều
Bản thân điều này khó coi là một thành tựu lớn, nhưng vẫn thú vị khi thấy nó hoạt động
Khi về nhà tôi sẽ bổ sung vào bài rằng việc giải MNIST tương đối dễ
Dù vậy, hầu hết các thuật toán đơn giản và hợp lý đều đạt độ chính xác 97%, nên nó vẫn có giá trị như một công cụ giáo dục hoặc bộ dữ liệu Hello world
Ngay cả khi tự xây công cụ từ đầu thì vẫn vừa tầm bài tập, và đây là một nhiệm vụ hữu ích ai cũng hiểu được, kiểu “nhận dạng chữ số trên thư”
Nếu hiểu về nén, cách tiếp cận này cũng chỉ là một ý tưởng rất đơn giản, nên nó đã có thể được viết ngay trong ngày đầu MNIST được công bố và vẫn đạt độ chính xác 78%
Điểm đó khiến tôi thấy khá đáng kinh ngạc
Kho lưu trữ cũng không định nghĩa UMAP, nhưng nếu tin ChatGPT thì UMAP là viết tắt của Uniform Manifold Approximation and Projection, một kỹ thuật giảm chiều và trực quan hóa dùng trong machine learning và phân tích dữ liệu
Tôi chỉ ở mức sở thích trong lĩnh vực này, nhưng dữ liệu được nén mạnh chẳng phải có entropy cao giống dữ liệu đã mã hóa sao
Nếu tìm được mẫu trong dữ liệu đã nén để suy ra chữ số gốc, chẳng phải có thể dùng mẫu đó để nén tốt hơn hay sao
Ý tưởng là “7 7” phải nén tốt hơn “7 3”, và ảnh raster của “7 7” cũng sẽ nén tốt hơn “7 3”
Tính không thể nén là một đặc trưng của phép toán mật mã hiệu quả
Xem phần về nén trong bài Kolmogorov complexity: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
Một trong những khái niệm tôi thích trong nén là nguyên lý chuồng bồ câu, nói rằng với mọi thuật toán nén, chắc chắn sẽ tồn tại đầu ra lớn hơn đầu vào
Ta vẫn có thể thử nén một payload mã hóa được thiết kế tốt, nhưng trung bình đầu ra sẽ lớn hơn đầu vào, khiến việc nén trở nên vô dụng, nên ta gọi nó là “không thể nén”
https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...
Tôi nhớ vài năm trước từng có trường hợp dùng kích thước của ảnh MNIST làm “đặc trưng meta”, nhưng giờ chưa tìm lại được ngay
Theo tôi nhớ, chỉ riêng đặc trưng đó, thậm chí không nhìn vào ảnh, cũng cho độ chính xác khoảng 90%
Là kích thước sau khi nén bằng gzip chăng? Nếu chỉ đơn giản nhìn xem ảnh MNIST tối đến mức nào, tức tỷ lệ pixel tối, thì độ chính xác khoảng 20%, tốt gấp đôi đoán ngẫu nhiên nhưng còn rất xa 90%
Tôi nghi là các tác giả của bài báo đó đã mắc lỗi khiến kết quả vọt lên nhóm đầu benchmark
Sau vụ đó tôi cho rằng lý thuyết không nhất quán, nhưng dù sao chỉ với GZIP mà đạt độ chính xác 78% vẫn rất ấn tượng
Bất kể bài toán này có phải ứng dụng tốt cho mẹo nén hay không, những người thử nghiệm nên ngừng dùng
gzipvà dùngzlibthì hơnNếu đổi dòng đầu tiên từ
gzip.compresssangzlib.compress, tốc độ sẽ nhanh gấp 3 lần với cùng hiệu năng phân loại