Chi tiết thuật toán tách token Byte-Pair Encoding (BPE)

Thuật toán tách token Byte-Pair Encoding

Trong xử lý ngôn ngữ tự nhiên, token là đơn vị nhỏ nhất để biểu diễn từ ngữ. Token có thể là một từ, là một ký tự hay cũng có thể là tập hợp từ, tập hợp ký tự.

Thuật toán tách token là chia các văn bản thành nhiều đơn vị nhỏ (token) nhằm số hóa chúng sau đó đưa dữ liệu này vào đào tạo các mô hình.

Cách đơn giản nhất đó là tách câu theo từ tuy nhiên cách này có một điểm yếu rất lớn. Đó là vấn đề từ không biết (unknown words) và để khắc phục vấn đề này chúng ta sẽ sử dụng thuật toán Byte-Pair Encoding, viết tắt là BPE.

1) Vấn đề từ không biết - unknown words

Ví dụ trong ngữ liệu (corpus) của chúng ta có những văn bản như sau:

Tôi rất thích đi học
Xích bích là một trận đấu hay

Nếu chúng ta dùng cách token hóa theo từ tức là tách câu thành các từ dựa trên khoảng trắng giữa chúng, thì ta sẽ thu được về một bộ từ điển (vocabulary) chứa các token sau:

{"Tôi", "rất", "thích", "đi", "học", "Xích", "bích", "là", "một", "trận", "đấu", "hay"}

Trong trường hợp này một token là một từ.

Nhưng nếu sau này khi xử lý ngôn ngữ tự nhiên bạn cần xử lý câu sau:

Tôi rất thích lái xe

Trong trường hợp này từ "lái" và "xe" không tồn tại trong bộ từ điển bên trên vì vậy bạn sẽ coi hai từ này là từ không biết (unknow words). Điều này là một điểm bất lợi khi làm ngôn ngữ tự nhiên khi chưa khai phá được bản chất của từ ngữ được hình thành bởi những cụm ký tự giống nhau.

Ví dụ từ "thích" và "Xích" và "bích" đều được hình thành khi có nhóm ký tự "ích". Đây là một hình vị (morpheme) - đơn vị có ý nghĩa nhỏ nhất trong ngôn ngữ.

Vì vậy sẽ tốt hơn nếu ta coi "ích" là một token? Hiển nhiên là cần thiết . Vì việc làm này sẽ giúp chúng ta tránh được hiện tượng từ không biết như bên trên.

2) Bộ token hóa - Tokenizer

Quá trình token hóa sẽ bao gồm hai phần

Bộ học token (Token learner)
Bộ tách token (Token segmenter)

Xem kỹ video về cách làm này tại đây.

2.1) Bộ học token (Token learner)

Ví dụ bên trên là cách token hóa theo từ. Bộ học token đếm số lượng các từ trong tất cả các câu. Từ nào xuất hiện càng nhiều thì sẽ có giá trị nhỏ trong từ điển. Từ không biết <unkown_word> có giá trị nhỏ nhất bằng 1

2.2) Bộ tách token (Token segmenter)

Bộ tách token gán các giá trị tương ứng trong từ điển của các từ trong câu đầu vào để tạo ra chuỗi số tương ứng.

3) Thuật toán Byte-Pair Encoding

Như đã đề cập bên trên, các thuật toán token hóa hiện đại sẽ chia nhỏ câu thành nhiều token thấp hơn mức từ. Thuật toán Byte-Pair Encoding (BPE) là một ví dụ điển hình, thuật toán này sẽ chia từ thành các đơn vị thông qua việc đếm số lượng các cặp ký tự.

Ví dụ cho một ngữ liệu như sau. Mỗi dòng bắt đầu bởi số lượng từ, tiếp theo là từ đó

Ngữ liệu

5 c a m _         # Ý nghĩa dòng này là có 5 từ cam

4 n h a m _

3 t a m _

6 c a n _

4 h a m _

Từ điển hiện tại

_, a, c, h, m ,n, t

Ký tự đặc biệt _ là ký hiệu đại diện cho kết thúc của một từ. Ký hiệu này sẽ được dùng để giải mã (decode) trong tương lai.

3.1) Vòng lặp đầu tiên

Thuật toán sẽ đếm tất cả những cặp ký tự - 2 ký tự trong ngữ liệu và tìm ra cặp nào xuất hiện nhiều nhất. Ví dụ trong trường hợp này số lượng các cặp xuất hiện sẽ như sau:

{'am': 16, 'm_': 16, 'ca': 11, 'ha': 8, 'an': 6, 'n_': 6, 'nh': 4, 'ta': 3}

Cặp 'a m' và 'm _' là hai cặp xuất hiện nhiều nhất - 16 lần. Ta lựa chọn cặp 'a m' (hoặc có thể 'm _') để tiến hành xử lý. Thuật toán sẽ làm hai việc

Thay thế cặp 'a m' trong tất cả các văn bản của ngữ liệu
Thêm cặp này vào trong từ điển

Ngữ liệu mới:

5 c am _

4 n h am _

3 t am _

6 c a n _

4 h am _

Từ điển mới

_, a, c, h, m ,n, t, am

3.2) Vòng lặp thứ hai

Trong ngữ liệu mới cặp 'am _' là xuất hiện nhiều nhất: 16 lần.

{'am_': 16, 'ham': 8, 'ca': 6, 'an': 6, 'n_': 6, 'cam': 5, 'nh': 4, 'tam': 3}

Thuật toán sẽ:

Thay thế cặp 'am _' trong tất cả văn bản của ngữ liệu
Thêm cặp này vào trong từ điển

Ngữ liệu mới:

5 c am_

4 n h am_

3 t am_

6 c a n _

4 h am_

Từ điển mới:

_, a, c, h, m ,n, t, am, am_

3.3) Vòng lặp thứ 3

Trong ngữ liệu mới cặp 'h am_' là xuất hiện nhiều nhất: 8 lần.

{'ham_': 8, 'ca': 6, 'an': 6, 'n_': 6, 'cam_': 5, 'nh': 4, 'tam_': 3}

Thuật toán sẽ:

Thay thế cặp 'h am_' trong tất cả văn bản của ngữ liệu
Thêm cặp này vào trong từ điển

Ngữ liệu mới:

5 c am_

4 n ham_

3 t am_

6 c a n _

4 ham_

Từ điển mới:

_, a, c, h, m ,n, t, am, am_, ham_

3.4) Vòng lặp thứ 4

Trong ngữ liệu mới cặp 'c a' là xuất hiện nhiều nhất: 6 lần.

{'ca': 6, 'an': 6, 'n_': 6, 'cam_': 5, 'nham_': 4, 'tam_': 3}

Thuật toán sẽ:

Thay thế cặp 'c a' trong tất cả văn bản của ngữ liệu
Thêm cặp này vào trong từ điển

Từ điển mới:

_, a, c, h, m ,n, t, am, am_, ham_, ca

Thuật toán sẽ thực hiện tiếp tục như vậy với tổng số lần lặp là k lần cài đặt trước.

3.5) Kết quả cuối cùng thu được

Kết quả sẽ là từ điển bao gồm các token và số lần xuất hiện của token đó được thể hiện như sau:

_: 1
a: 1
c: 1
h: 1
m: 1 
n: 1
t: 1
am: 16
am_: 16
ham_: 8
ca: 6

Từ điển được bố trí dưới dạng

key: value

key là token và value là số lần lặp lại của token đó.

3.6) Công thức của thuật toán

Khởi tạo từ điển V chứa tất cả các ký tự của ngữ liệu
Lặp từ 1 đến k.
- Tìm ra cặp 2 token xuất hiện nhiều nhất trong ngữ liệu
- Nối 2 token này thành token mới token_new
- Thêm token_new vào từ điển V
- Thay thế cặp 2 token ban đầu bằng token_new ở mọi nơi trong ngữ liệu
Kết quả thu được từ điển V

4) Quá trình mã hóa (encode)

Với từ mới ví dụ

tam

Tách câu đó thành các ký tự cách nhau bằng khoảng trắng và thêm ký tự _ vào cuối. Ta có: 't a m _'
Thay cặp 'a m' thành 'am'. Cặp 'a m' này được lựa chọn thay trước vì có số lần xuất hiện cao nhất trong từ điển. Kết quả 't am _'
Thay cặp 'am _' thành 'am_'. Kết quả 't am_'

5) Kết luận

Với cách sử dụng nhiều token đa dạng hơn rất nhiều như vậy giúp chúng ta có thể mô phỏng lại rất nhiều những từ không biết - unknown words bằng viết kết hợp những token hay xuất hiện. Tất nhiên vẫn sẽ có những từ rất hiếm không token được nhưng con số đó rất ít.

6) Nguồn tham khảo

Nghiên cứu gốc: https://aclanthology.org/P16-1162.pdf
Speech and Language Processing: https://web.stanford.edu/~jurafsky/slp3/ed3book.pdf

Hi vọng bài viết này hữu ích với bạn. Hẹn gặp lại bạn trong những bài tiếp theo của chuỗi bài viết liên quan đến các thuật toán tách token.

Thuật toán tách token WordPiece