gzipt: Thử nghiệm mô hình ngôn ngữ bằng thuật toán nén gzip

Cách đây một thời gian, tôi đã viết về mô hình ngôn ngữ không sử dụng mạng thần kinh (neural network), nơi tôi tạo ra văn bản kiểu Shakespeare bằng mô hình n-gram không giới hạn: không trọng số, không huấn luyện, chỉ đơn thuần là đếm. Thật tình cờ, tôi bắt gặp bài báo "Language Modeling is Compression" (Mô hình hóa ngôn ngữ chính là nén dữ liệu), trong đó đề cập đến sự tương đương giữa nén và dự đoán:

mọi mô hình dự đoán về bản chất đều là một bộ nén, và mọi thuật toán nén đều là các mô hình dự đoán.

Điều này dẫn đến một câu hỏi tự nhiên: liệu gzip có thể thực hiện mô hình hóa ngôn ngữ không? Không mạng thần kinh, không tham số học được, không gì cả. Chỉ là bộ nén đi kèm với hệ điều hành của bạn. Bạn nạp cho nó một kho ngữ liệu (corpus), đưa cho nó một đoạn văn bản gợi ý (prompt), và nó sẽ tiếp tục đoạn văn bản đó bằng cách tìm kiếm các chuỗi byte nén tốt nhất. Dưới đây là một số kết quả thực tế, chưa qua chỉnh sửa sau khi nạp dữ liệu từ tập tiny Shakespeare:

Hóa ra là có, theo một cách nào đó? Nó không hẳn là văn bản mạch lạc, nhưng rõ ràng nó biết một vài điều về văn bản đó. Nhiều hơn những gì tôi mong đợi ở gzip. Vậy làm thế nào một bộ nén có thể tạo ra kết quả này?

Nén chính là dự đoán#

Hãy nghĩ về những gì một bộ nén thực hiện. Nó tốn ít byte cho dữ liệu mà nó “mong đợi” và tốn nhiều byte cho dữ liệu mà nó không mong đợi. Nếu tôi đưa cho bạn một tệp chứa chữ A lặp lại một triệu lần, bạn có thể mô tả nó chỉ trong một câu. Ngược lại, một triệu byte ngẫu nhiên không có cấu trúc nào để khai thác và hầu như không thể nén được.

Đây không phải là sự trùng hợp; đó là cốt lõi của lý thuyết thông tin. Số bit cần thiết để mã hóa một ký hiệu là $-\log_2 p$, trong đó $p$ là xác suất mà mô hình gán cho ký hiệu đó. Xác suất cao đồng nghĩa với ít bit. Vì vậy, bất kỳ bộ nén nào cũng ẩn chứa một mô hình xác suất bên trong, bất kể có ai đó đã viết nó ra hay chưa.

gzip sử dụng DEFLATE, thuật toán nén các byte tiếp theo bằng cách tìm kiếm các đoạn khớp với văn bản gần đây trong một cửa sổ trượt 32 KiB. Nếu một phần tiếp nối lặp lại nội dung đã có trong cửa sổ, DEFLATE sẽ mã hóa nó thành một tham chiếu ngược (back-reference) tiết kiệm thay vì các byte nguyên bản. Vì vậy:

Một phần tiếp nối mà gzip “mong đợi”, vì nó lặp lại văn bản đã có trong cửa sổ của nó, sẽ nén lại gần như bằng không.

Điều đó mang lại cho chúng ta một điểm số. Nếu tôi có một ngữ cảnh và muốn biết một phần tiếp nối ứng viên tốt đến mức nào, tôi chỉ cần đo lường:

$$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$

Độ dài sau khi nén càng nhỏ, ứng viên đó càng được “dự đoán” chính xác. Để nạp dữ liệu cho mô hình, tôi đưa một kho ngữ liệu vào cửa sổ của gzip. Bất kỳ phần tiếp nối nào trông giống với kho ngữ liệu sẽ nén lại với dung lượng nhỏ, và bất kỳ phần nào không giống sẽ nén lại với dung lượng lớn.

Tạo văn bản bằng tìm kiếm chùm (beam search)#

Chấm điểm là một chuyện; tạo văn bản lại là chuyện khác. Cách tiếp cận ngây thơ là chọn byte tiếp theo nén tốt nhất sẽ thất bại thảm hại, vì một lý do tinh tế: gzip chỉ đưa ra độ dài byte là số nguyên (không có phân số). Việc thêm một byte thường không làm thay đổi độ dài nén, vì vậy nhiều ứng viên có điểm số ngang nhau và tín hiệu bị chôn vùi trong nhiễu lượng tử hóa.

Giải pháp là nhìn trước một khoảng toàn bộ trước khi quyết định. gzipt chạy tìm kiếm chùm (beam search) trên các chuỗi byte. Tại mỗi bước, ngữ cảnh hiện tại là:

Sau đó, gzipt thử các byte tiếp theo có thể. Mỗi ứng viên tiếp nối được chấm điểm bằng cách nén (ngữ cảnh + ứng viên) và kiểm tra xem kết quả nén chiếm bao nhiêu byte.

Vòng lặp là:

Một chi tiết quan trọng là chỉ những byte cuối cùng của đầu ra được tạo mới nằm trong ngữ cảnh chấm điểm. DEFLATE mã hóa các đoạn khớp gần đó rẻ hơn so với các đoạn xa, vì vậy nếu gzip có thể nhìn thấy toàn bộ lịch sử của nó, hành động rẻ nhất thường là rơi vào các vòng lặp nguyên văn, lặp đi lặp lại việc sao chép văn bản mà nó vừa tạo ra.

Bạn có thể thấy quá trình giải mã và chấm điểm trong hình ảnh động ở trên, đó chính là bản phát lại giống như ở đầu bài. Toàn bộ chương trình là một tệp Python sử dụng thư viện chuẩn (chỉ dùng zlib). Mã nguồn có trên GitHub nếu bạn muốn thử nghiệm.

Bài báo gốc đã thử cách này, nhưng kết quả thực hiện khá kém. Việc thêm tìm kiếm chùm (beam search) đã cải thiện đáng kể chất lượng tạo văn bản (một ý tưởng mà họ đã đề cập), điều này được thảo luận ở dưới. ↩︎

Mã nguồn thực tế sử dụng zlib thay vì khởi chạy một tiến trình gzip, nhưng cái tên GziPT nghe rất hay. Tôi tin rằng cả hai đều sử dụng cùng một thuật toán DEFLATE bên dưới. ↩︎