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

Trong bài trước chúng ta đã cùng thảo luận thuật toán token BPE - sử dụng tần suất xuất hiện của những cặp ký tự để xây dựng từ điển. Xem chi tiết thêm tại đây.

Hôm nay chúng ta sẽ cùng nghiên cứu một thuật toán có tên WordPiece. Một mô hình rất nổi tiếng dùng thuật toán này đó chính là BERT - Bidirectional Encoder Representations from Transformers.

1) Tách từ thành các ký tự

Ví dụ trong mô hình Bert, một từ "ProtonX" sẽ được tách thành các ký tự và thêm ## vào phía trước

Ví dụ

Đầu vào:

ProtonX

Đầu ra:

P ##r ##o ##t ##o ##n ##X

Chú ý: Chỉ riêng từ ở đầu là không thêm "##"

2) Điểm khác biệt với thuật toán BPE

Thuật toán BPE đếm số cặp hai token xuất hiện liền nhau và lưu token hợp của chúng vào trong từ điển. Thuật toán WordPiece cũng đếm tuy nhiên thay vì chỉ lựa chọn cặp token xuất hiện nhiều nhất, thuật toán này sẽ thêm yếu tố tần suất của từng ký tự trong cặp này.

Công thức sẽ như sau:

Điểm (score) = (Số lần xuất hiện của cặp token) / (Số lần xuất hiện của token 1 x Số lần xuất hiện của token 2)

Các cặp token có điểm càng cao sẽ ưu tiên hợp (merge) trước.

Ý nghĩa của việc này là gì nhỉ?

Khi nhìn vào công thức chúng ta sẽ thấy nếu chúng ta có hai cặp token:

Cặp 1: "g ##a"
Cặp 2: "g #ấu"

Nếu số lượng xuất hiện của cả hai cặp này tuơng đương nhau, bộ học token (Token learner) sẽ ưu tiên cặp "g ##ấu" hơn vì token "##ấu" trong cặp này sẽ xuất hiện ít hơn nhiều so với token "##a" trong cặp "g ##a". Cả hai cặp token cùng chung token đầu "g".

Thậm chí cặp 1 cũng không cần hợp vì đơn giản là hai token xuất hiện rất nhiều trong bộ từ điển.

3) Thuật toán

3.1) Ví dụ đơn giản

Ngữ liệu:

5 g ##a 
6 g ##ấ ##u
8 g ##a ##n
7 g ##ấ ##m 
3 h ##a

Từ điển

'##a', '##m', '##n', '##u', '##ấ', 'g', 'h'

Trong ngữ liệu này:

Token "g" xuất hiện 5 + 6 + 7 + 8 = 26 lần
Token "##a" xuất hiện 5 + 8 + 3 = 16 lần
Token "##ấ" xuất hiện 6 + 7 = 13 lần
Cặp token "g ##a" xuất hiện 5 + 8 = 13 lần
Cặp token "g ##ấ" xuất hiện 6 + 7 = 13 lần

Điểm của cặp "g ##a" = (Số lần xuất hiện của cặp "g ##a") / (Số lần xuất hiện của token "g" x Số lần xuất hiện của token "##a") = 13 / (26 x 16) = 0.03125

Điểm của cặp "g ##ấ" = (Số lần xuất hiện của cặp "g ##ấ") / (Số lần xuất hiện của token "g" x Số lần xuất hiện của token "##ấ") = 13 / (26 x 13) = 0.0385

Trong trường hợp này điểm của cặp "g ##ấ" lớn hơn nên sẽ ưu tiên hợp cặp này vào từ điển hơn.

3.2) Cách hợp

Nếu ta hợp "g" và "##ấ" ta sẽ bỏ "##" trước "##ấ" ta sẽ có "gấ"
Nếu ta hợp "##ấ" và "##m" ta sẽ bỏ "##" trước "##m" ta sẽ có "##ấm"

Sau đó token hợp này sẽ được thêm vào từ điển.

3.3) Ví dụ phức tạp

3.3.1) Tiến hành đếm

Ngữ liệu có 2 câu:

"ProtonX là một công ty AI",
"ProtonX là một nơi ươm mầm tài năng AI"

Bộ đếm

'ProtonX': 2,
'là': 2,
'một': 2,
'công': 1,
'ty': 1,
'AI': 2,
'nơi': 1,
'ươm': 1,
'mầm': 1,
'tài': 1,
'năng': 1

Những ký tự đứng đầu câu thì không thêm '##'
Những ký tự đứng sau ký tự đầu đều thêm '##' vào phía trước

Ví dụ với từ "ProtonX" ta có kết quả như sau

'ProtonX': ['P', '##r', '##o', '##t', '##o', '##n', '##X']

Kết quả ta có trên cả hai câu như sau:

['##I', '##X', '##g', '##i', '##m', '##n', '##o', '##r', '##t', '##y', '##à', '##ô', '##ă', '##ơ', '##ầ', '##ộ', 'A', 'P', 'c', 'l', 'm', 'n', 't', 'ư']

Ta bắt đầu đi tính điểm cho các cặp token cạnh nhau trong cách từ

('P', '##r'): 0.5
('##r', '##o'): 0.25
('##o', '##t'): 0.125
('##t', '##o'): 0.125
('##o', '##n'): 0.125
('##n', '##X'): 0.25
('l', '##à'): 0.3333333333333333
('m', '##ộ'): 0.3333333333333333
('##ộ', '##t'): 0.25
('c', '##ô'): 1.0
('##ô', '##n'): 0.25
('##n', '##g'): 0.25
('t', '##y'): 0.5
('A', '##I'): 0.5
('n', '##ơ'): 0.25
('##ơ', '##i'): 0.25
('ư', '##ơ'): 0.5
('##ơ', '##m'): 0.25
('m', '##ầ'): 0.3333333333333333
('##ầ', '##m'): 0.5
('t', '##à'): 0.16666666666666666
('##à', '##i'): 0.16666666666666666
('n', '##ă'): 0.5
('##ă', '##n'): 0.25

Cặp token

('c', '##ô'): 1.0

có điểm cao nhất hơn hẳn cặp ('A', '##I') mặc dù cặp AI xuất hiện hai lần trong ngữ liệu nhưng chỉ có điểm là (2) / (2 x 2) = 0.5

Điểm thấp nhất là 3 cặp

('##o', '##t'): 0.125
('##t', '##o'): 0.125
('##o', '##n'): 0.125

Ví dụ cặp ('##o', '##t') có điểm (2) / (4 x 4) = 0.125

3.3.2) Tiến hành hợp và thêm vào từ điển

Cặp ('c', '##ô') được hợp thành "cô" và thêm vào từ điển.

Từ "công" sẽ được biểu diễn như sau sau lần hợp này:

'công': ['cô', '##n', '##g']

Sau một số lượng vòng lặp cài đặt sẵn ta sẽ thu được bộ từ điển sau:

['##I', '##X', '##g', '##i', '##m', '##n', '##o', '##r', '##t', '##y', '##à', '##ô', '##ă', '##ơ', '##ầ', '##ộ', 'A', 'P', 'c', 'l', 'm', 'n', 't', 'ư', 'cô', 'Pr', 'ty', 'AI', 'ươ', 'nơ', 'nă', 'nơi', 'ươm', '##ầm', 'là', 'tà', 'tài', 'mộ', 'mầm', 'Pro', 'Prot', 'Proto', 'một', 'Proton', 'ProtonX', 'côn', 'năn', 'công', 'năng']

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

Với bộ từ điển trên thì với đầu vào câu:

"Thả tym cho ProtonX nào"

sau khi tách token sẽ có kết quả là

['[UNK]', 'ty', '##m', '[UNK]', 'ProtonX', 'n', '##à', '##o']

Từ "Thả" tính từ đầu (cố định vị trí đầu) đến cuối không chứa bất kỳ từ con (subword) nào nằm bên trong từ điển nên sẽ được kết luận là từ không biết với token "[UNK]".
- Cách lặp
  - "T" không nằm trong từ điển
  - "Th" không nằm trong từ điển
  - "Thả" không nằm trong từ điển
- Cho nên kết luận "Thả" là "[UNK]"
Từ "tym" được tách thành token "ty" và "##m"
- Từ đầu đến "y" từ "ty" là một token nằm trong từ điển. Tiến hành tách khỏi từ ban đầu ra thành "ty" và phần còn lại là "m". Thêm "##" vào "m" thành "##m" và tiếp tục tách.
- "##m" nằm trong từ điển và tách thành chính nó.

Vậy cách mã hóa ở đây sẽ là gì?

Chúng ta sẽ đặt mốc cố định là đầu chuỗi, tìm xem từ đầu đến vị trí nào chứa token dài nhất trong vocab thì ta bắt đầu tách token. Phần đằng sau sẽ thêm "##" vào phía trước.
Tiếp tục tách phần sau.
Trường hợp nào từ đầu đến đuôi của phần chuỗi đang làm việc không hề nằm trong từ điển, trả về token [UNK]

Trên đây team đã trình bày đầu đủ thuật toán WordPiece. Một trong những thuật toán tách từ quan trọng.

Hẹn gặp lại bạn tại những bài viết tiếp theo trong chuỗi bài viết về thuật toán tách từ.

Filter