Giới thiệu

Nhiều ứng dụng trong xử lý ngôn ngữ tự nhiên (NLP) như dịch máy, chatbot,... đều có output dưới dạng văn bản. Ngoài ra, các ứng dụng như mô tả hình ảnh (image captioning) hoặc nhận dạng giọng nói tự động (Speech-to-Text) cũng tạo ra văn bản, mặc dù chúng không hoàn toàn thuộc lĩnh vực NLP. Để tạo ra kết quả, các ứng dụng này thường sử dụng một số thuật toán phổ biến trong bước cuối cùng của quá trình xử lý.

Greedy Search là một trong những thuật toán thường được sử dụng vì tính đơn giản và tốc độ của nó. Tuy nhiên, một lựa chọn khác là Beam Search. Mặc dù Beam Search yêu cầu nhiều tính toán hơn, nhưng nó rất phổ biến vì thường mang lại kết quả tốt hơn nhiều.

Trong bài viết này, chúng ta sẽ tìm hiểu Beam Search, giải thích lý do tại sao nó được sử dụng và cách nó hoạt động. Chúng ta cũng sẽ so sánh với Greedy Search để hiểu rõ hơn cách Beam Search cải thiện kết quả so với Greedy Search.

Cách các model NLP truyền thống generate output

Mô hình sequence-to-sequence (seq2seq) là một kiến trúc học sâu phổ biến, được sử dụng rộng rãi trong các ứng dụng như dịch máy, chatbot, và tóm tắt văn bản. Các mô hình này có khả năng chuyển đổi một chuỗi đầu vào (ví dụ: một câu trong ngôn ngữ ban đầu) thành một chuỗi đầu ra (ví dụ: câu tương đương trong ngôn ngữ đích). Để hiểu rõ hơn về cách hoạt động của mô hình seq2seq, chúng ta sẽ lấy ví dụ về dịch máy từ tiếng Anh sang tiếng Tây Ban Nha.

Văn bản được xem như là một chuỗi các từ hoặc ký tự. Đầu tiên, mô hình NLP sẽ xây dựng một bộ từ vựng bao gồm toàn bộ các từ trong cả ngôn ngữ ban đầu và ngôn ngữ đích. Khi nhận được một câu từ ngôn ngữ ban đầu (ví dụ: "You are welcome"), câu này sẽ được đưa vào lớp Embedding, khi đó mỗi từ được ánh xạ thành một vector số học để mô hình có thể xử lý. Sau đó, các vector này được truyền qua một Encoder. Encoder có nhiệm vụ biến đổi chuỗi các vector từ vựng thành một biểu diễn mã hóa (encoded representation), là một vector duy nhất chứa các đặc trưng quan trọng của câu ban đầu.

Encoded representation từ Encoder sau đó được đưa vào Decoder cùng với một token đặc biệt <START>, đánh dấu sự bắt đầu của quá trình tạo output. Decoder sử dụng encoded representation và token <START> để bắt đầu sinh ra chuỗi các từ trong ngôn ngữ đích. Mỗi bước trong quá trình này, Decoder sẽ dự đoán từ tiếp theo trong câu đích dựa trên thông tin từ các bước trước đó và encoded representation ban đầu. Điều này giúp đảm bảo rằng câu đích được tạo ra có ý nghĩa và ngữ pháp chính xác.

Sau khi Decoder tạo ra encoded representation của câu trong ngôn ngữ đích, biểu diễn này sẽ được đưa qua một hoặc nhiều layer Linear, mỗi layer này tính toán điểm số cho mỗi từ trong từ vựng. Điểm số này thể hiện xác suất của từng từ xuất hiện tại mỗi vị trí trong câu đầu ra. Sau đó, các điểm số này được chuyển qua một layer Softmax, layer này sẽ chuyển đổi các điểm số thành các xác suất thực tế.

Vocab | Position 1 | Position 2 | ... | Position n |
-----------|------------|------------|-----|------------|
**A** | 0.12 | 0.09 | ... | 0.82 |
**B** | 0.05 | | ... | 0.07 |
... | ... | ... | ... | ... |
**Z** | 0.03 | | ... | |
**END** | 0.01 | | ... | |

Mặc dù các xác suất là đầu ra trực tiếp của mô hình, mục tiêu cuối cùng của chúng ta là tạo ra một câu hoàn chỉnh trong ngôn ngữ đích. Để làm điều này, mô hình phải quyết định từ nào có xác suất cao nhất tại mỗi vị trí trong câu và sử dụng các từ đó để tạo ra câu cuối cùng. Ví dụ, mô hình có thể dự đoán rằng từ "De" có xác suất cao nhất cho vị trí đầu tiên và "nada" cho vị trí thứ hai, từ đó tạo ra câu "De nada" trong tiếng Tây Ban Nha.

 +------------+ | "De Nada" | +------------+ | v +----------------+ | ?? Prediction ??| +----------------+ | v
Vocab | Position 1 | Position 2 | ... | Position n |
-----------|------------|------------|-----|------------|
**A** | 0.12 | 0.09 | ... | 0.82 |
**B** | 0.05 | | ... | 0.07 |
... | ... | ... | ... | ... |
**Z** | 0.03 | | ... | |
**END** | 0.01 | | ... | |

Mô hình sequence-to-sequence sử dụng một quá trình phức tạp nhưng hiệu quả để dịch các câu từ ngôn ngữ này sang ngôn ngữ khác. Bằng cách encode văn bản input thành một biểu diễn vector và sau đó decode biểu diễn này thành câu đích dựa trên các xác suất từ vựng, mô hình seq2seq có thể tạo ra các bản dịch chính xác và tự nhiên. Điều này cho thấy sức mạnh của deep learning trong việc xử lý ngôn ngữ tự nhiên và các ứng dụng liên quan.

Vậy thì, chúng ta sẽ lấy các từ có xác suất cao nhất? hay còn có thêm cách nào khác? Hãy tiếp tục tìm hiểu trong phần dưới nhé

Giới thiệu Greedy Search

Nghe cái tên hẳn bạn cũng sẽ đoán được cách hoạt động của phương pháp này. Về cơ bản, ta chỉ cần chọn những từ có xác suất xảy ra cao nhất tại mỗi vị trí. Ví dụ trong bảng dưới

Khi mô hình của chúng ta xuất ra token <eos> hoặc khi đạt đến độ dài tối đa, chuỗi đầu ra sẽ hoàn tất. Chiến lược này có vẻ hợp lý và thực tế là nó cũng ... không tệ Xét về độ hiệu quả tính toán, Greedy Search là một lựa chọn khá oke. Tuy nhiên, nếu chúng ta bỏ qua yếu tố tiết kiệm thời gian, có thể thấy rằng việc tìm kiếm chuỗi có xác suất cao nhất thay vì các token có xác suất cao nhất tại từng bước có vẻ hợp lý hơn

Hai phương pháp này có thể dẫn đến những kết quả rất khác nhau. Chuỗi có xác suất cao nhất là chuỗi tối đa hóa biểu thức $P(Y | X)$. Trong ví dụ dịch máy, nếu decoder khôi phục đúng xác suất của quá trình sinh ngẫu nhiên, thì điều này sẽ cho chúng ta bản dịch có xác suất cao nhất. Tuy nhiên, không có gì đảm bảo rằng Greedy Search sẽ cho chúng ta chuỗi này.

Hãy xem ví dụ sau, giả sử có bốn token “A”, “B”, “C”, và <eos> trong từ điển đầu ra. Trong bảng dưới đây, bốn con số dưới mỗi bước thời gian đại diện cho xác suất điều kiện của việc tạo ra các token “A”, “B”, “C”, và <eos> tương ứng tại bước thời gian đó.

Theo timestep, Greedy Search chọn token có xác suất điều kiện cao nhất. Do đó, chuỗi đầu ra “A”, “B”, “C”, và <eos> sẽ được dự đoán. Xác suất điều kiện của chuỗi đầu ra này là $P(A, B, C, <eos> | X) = 0.5 \times 0.4 \times 0.4 \times 0.6 = 0.048$.

Tiếp theo, hãy xét một ví dụ khác. Khác với ví dụ trước, tại timestep 2, chúng ta chọn token “C”, token có xác suất điều kiện cao thứ hai. Do các chuỗi con đầu ra tại các timestep 1 và 2, mà timestep 3 dựa vào, đã thay đổi từ “A” và “B” thành “A” và “C”, xác suất điều kiện của mỗi token tại timestep 3 cũng đã thay đổi.

Giả sử chúng ta chọn token “B” tại timestep 3. Bây giờ, timestep 4 sẽ phụ thuộc vào chuỗi con đầu ra tại ba timestep đầu “A”, “C”, và “B”, đã thay đổi từ “A”, “B”, và “C”. Do đó, xác suất điều kiện của việc tạo ra mỗi token tại bước thời gian 4 cũng khác. Kết quả là, xác suất điều kiện của chuỗi đầu ra “A”, “C”, “B”, và <eos> là $P(A, C, B, <eos> | X) 0.5 \times 0.3 \times 0.6 \times 0.6 = 0.054$, lớn hơn so với Greedy Search trong ví dụ trước. Trong ví dụ này, chuỗi đầu ra “A”, “B”, “C”, và <eos> thu được từ Greedy Search không phải là tối ưu.

Chiến lược Greedy Search là một phương pháp đơn giản và hiệu quả về mặt tính toán, nhưng không đảm bảo rằng nó sẽ tìm thấy chuỗi có xác suất cao nhất. Bằng cách chỉ chọn các token có xác suất cao nhất tại mỗi bước, Greedy Search có thể bỏ lỡ các chuỗi có xác suất tổng thể cao hơn. Ví dụ minh họa cho thấy rằng, trong một số trường hợp, việc chọn token không có xác suất cao nhất tại một bước cụ thể có thể dẫn đến chuỗi đầu ra tối ưu hơn.

Giới thiệu Beam Search

Beam Search mang lại 2 cải tiến đáng kể so với Greedy Search.

Với Greedy Search, chúng ta chỉ chọn token tốt nhất tại mỗi vị trí. Ngược lại, Beam Search mở rộng phạm vi này và chọn ra 'N' token tốt nhất. Điều này có nghĩa là thay vì chỉ xét từng từ đơn lẻ, Beam Search xem xét cả một nhóm token tại mỗi bước.

Với Greedy Search, chúng ta xem xét từng vị trí một cách độc lập. Sau khi xác định từ tốt nhất cho vị trí đó, chúng ta không kiểm tra những từ trước đó (ở vị trí trước) hoặc sau đó. Beam Search thì khác, nó chọn 'N' chuỗi tốt nhất cho đến thời điểm hiện tại và xem xét xác suất của sự kết hợp của tất cả các từ trước đó cùng với từ ở vị trí hiện tại.

Nói cách khác, Beam Search mở rộng "các hướng tìm kiếm" của nó rộng hơn một chút so với Greedy Search, và đó là lý do tại sao nó được gọi là Beam Search. Hyperparameter 'N' được gọi là độ rộng Beam (Beam width).

Một cách trực quan, điều này giúp Beam Search mang lại kết quả tốt hơn so với Greedy Search. Lý do là vì điều chúng ta thực sự quan tâm là câu hoàn chỉnh tốt nhất, và chúng ta có thể bỏ qua câu đó nếu chỉ chọn từ tốt nhất ở mỗi vị trí một cách riêng lẻ.

Xét trong 1 thuật toán Beam Search với N = 2, quy trình sẽ như sau:

• Vị trí đầu tiên:

  • Mô hình bắt đầu với token <START> và thu được xác suất cho mỗi từ.
  • Nó chọn hai ký tự tốt nhất tại vị trí này, ví dụ: “A” và “C”.

• Vị trí thứ hai:

  • Khi đến vị trí thứ hai, mô hình chạy lại hai lần để tạo ra xác suất bằng cách cố định các ký tự có thể có ở vị trí đầu tiên.
  • Cụ thể, nó giới hạn ký tự ở vị trí đầu tiên là “A” hoặc “C” và tạo ra hai nhánh với hai tập xác suất.
  • Nhánh đầu tiên tương ứng với việc có “A” ở vị trí 1, và nhánh thứ hai tương ứng với việc có “C” ở vị trí 1.
  • Mô hình sau đó chọn hai cặp ký tự tốt nhất dựa trên xác suất kết hợp của hai ký tự đầu tiên từ cả hai tập xác suất. Ví dụ: “AB” và “AE”.

• Vị trí thứ ba:

  • Khi đến vị trí thứ ba, mô hình lặp lại quá trình. Nó chạy lại hai lần bằng cách giới hạn hai vị trí đầu tiên là “AB” hoặc “AE” và tạo ra hai tập xác suất.
  • Một lần nữa, mô hình chọn hai bộ ba ký tự tốt nhất dựa trên xác suất kết hợp của ba ký tự đầu tiên từ cả hai tập xác suất. Ví dụ: “ABC” và “AED”.

• Lặp lại đến khi token “<END>” xuất hiện:

  • Quá trình này tiếp tục đến khi mô hình chọn token “<END>” làm ký tự tốt nhất cho một vị trí nào đó, kết thúc nhánh của chuỗi đó.
  • Cuối cùng, mô hình kết thúc với hai chuỗi tốt nhất và dự đoán chuỗi có xác suất tổng thể cao hơn.

Ý tưởng rất đơn giản phải không nào Nhìn qua có vẻ giống thuật toán tìm kiếm theo chiều rộng mà các bạn được học trong môn CTDLGT

Kết luận

Ưu và nhược điểm của 2 thuật toán trên như sau:

• Greedy Search:

  • Ưu điểm:
    • Đơn giản và nhanh chóng.
    • Yêu cầu tính toán thấp, dễ dàng triển khai.
  • Nhược điểm:
    • Không luôn đảm bảo tìm được chuỗi có xác suất cao nhất.
    • Chỉ xem xét từng từ một cách độc lập, có thể bỏ lỡ các kết hợp từ tối ưu.

• Beam Search:

  • Ưu điểm:
    • Tìm kiếm các chuỗi có xác suất cao nhất bằng cách xem xét nhiều khả năng tại mỗi bước.
    • Xem xét toàn bộ chuỗi từ đã chọn trước đó, dẫn đến kết quả chính xác và tối ưu hơn.
  • Nhược điểm:
    • Yêu cầu tính toán cao hơn so với Greedy Search.
    • Độ rộng Beam (Beam width) cần được tinh chỉnh cẩn thận để cân bằng giữa độ chính xác và hiệu suất tính toán.

Greedy Search và Beam Search đều có những ưu điểm và nhược điểm riêng, phù hợp với các tình huống khác nhau. Greedy Search phù hợp khi cần giải pháp nhanh chóng và tính toán đơn giản, trong khi Beam Search lại mang lại kết quả chính xác hơn khi yêu cầu tối ưu hóa cao và có thể chấp nhận chi phí tính toán cao hơn. Lựa chọn thuật toán nào phụ thuộc vào yêu cầu cụ thể của bài toán và tài nguyên tính toán có sẵn.