바이트 페어 인코딩이란?
바이트 페어 인코딩(Byte Pair Encoding, BPE)은 원래 정보를 압축하는 알고리즘으로 제안되었는데 최근에는 자연어 처리 모델에 널리 쓰이고 있는 토큰화 기법입니다. GPT 모델은 BPE 기법으로 토큰화를 수행하며, BERT 모델은 BPE와 유사한 워드피스(wordpiece)를 토크나이저로 사용합니다. 이 절에서는 BPE 기법을 살펴보겠습니다.
BPE란 무엇일까?
BPE는 1994년 제안된 정보 압축 알고리즘으로, 데이터에서 가장 많이 등장한 문자열을 병합해서 데이터를 압축하는 기법입니다. 예를 들어 다음과 같은 데이터가 있다고 가정해 봅시다.
- aaabdaaabac
BPE는 데이터에 등장한 글자(a, b, c, d)를 초기 사전으로 구성하며, 연속된 두 글자를 한 글자로 병합합니다. 이 문자열에선 aa가 가장 많이 나타났으므로 이를 Z로 병합(치환)하면 위의 문자열을 다음과 같이 압축할 수 있습니다.
- ZabdZabac
이 문자열은 한번 더 압축 가능합니다. 살펴보니 ab가 가장 많이 나타났으므로* 이를 Y로 병합(치환)합니다. 다음과 같습니다.
- ZYdZYac
* 물론 ab 대신 Za를 병합할 수도 있는데요, 하지만 둘의 빈도수가 2로 같으므로 알파벳 순으로 앞선 ab를 먼저 병합합니다.
ZY 역시 X로 병합할 수 있습니다. 이미 병합된 문자열 역시 한 번 더 병합할 수 있다는 얘기입니다. 다음과 같습니다.
- XdXac
BPE 수행 이전에는 원래 데이터를 표현하기 위한 사전 크기가 4개(a, b, c, d)였습니다. 그런데 수행 이후엔 그 크기가 7개(a, b, c, d, Z, Y, X)로 늘었습니다. 반면 데이터의 길이는 11에서 5로 줄었습니다. 이처럼 BPE는 사전 크기를 지나치게 늘리지 않으면서도 각 데이터 길이를 효율적으로 압축할 수 있도록 합니다.
BPE 기반 토큰화 기법은 분석 대상 언어에 대한 지식이 필요 없습니다. 말뭉치에서 자주 나타나는 문자열(서브워드)을 토큰으로 분석하기 때문입니다. 실제로 자연어 처리에서 BPE가 처음 쓰인 것은 기계 번역 분야입니다. BPE를 활용한 토크나이즈 절차는 다음과 같습니다.
- 어휘 집합 구축 : 자주 등장하는 문자열를 병합하고 이를 어휘 집합에 추가합니다. 이를 원하는 어휘 집합 크기가 될 때까지 반복합니다.
- 토큰화 : 토큰화 대상 문장 내 각 어절(띄어쓰기로 문장을 나눈 것)에서 어휘 집합에 있는 서브워드가 포함되어 있을 때 해당 서브워드를 어절에서 분리합니다.
이제부터 각 단계를 차례대로 살펴보겠습니다.
BPE 어휘 집합 구축하기
BPE 어휘 집합 구축 절차를 구체적으로 살펴보겠습니다. 어휘 집합을 만드려면 우선 말뭉치를 준비해야 합니다. 말뭉치의 모든 문장을 공백으로 나눠줍니다. 이를 프리토크나이즈(pre-tokenize)라고 합니다. 본격적인 토큰화에 앞서 미리 분석했다는 의미에서 이런 이름이 붙었습니다. 물론 공백 말고 다른 기준으로 프리토크나이즈를 수행할 수도 있습니다.
우리가 가진 말뭉치에 프리토크나이즈를 실시하고 그 빈도를 모두 세어서 표1을 얻었다고 가정해 봅시다.
표1 프리토크나이즈 결과
| 토큰 | 빈도 |
|---|---|
| hug | 10 |
| pug | 5 |
| pun | 12 |
| bun | 4 |
| hugs | 5 |
BPE를 문자(character) 단위로 수행할 경우 초기의 어휘 집합은 다음과 같습니다.
b,g,h,n,p,s,u
이 7개 문자로도 표1의 모든 토큰을 표현할 수 있습니다. 하지만 우리는 어휘 집합 크기가 약간 증가하더라도 토큰 시퀀스 길이를 줄이려는(정보를 압축하려는) 목적을 가지고 있으므로 BPE를 수행해 줄 계획입니다. 초기 어휘 집합을 바탕으로 표1을 다시 쓰면 표2와 같습니다.
표2 BPE 어휘 집합 구축 (1)
| 토큰 | 빈도 |
|---|---|
| h, u, g | 10 |
| p, u, g | 5 |
| p, u, n | 12 |
| b, u, n | 4 |
| h, u, g, s | 5 |
표3은 표2의 토큰을 두 개(바이그램; bigram)씩 묶어 쭉 나열한 것입니다. 표2와 표3의 본질은 동일합니다.
표3 BPE 어휘 집합 구축 (2)
| 바이그램 쌍 | 빈도 |
|---|---|
| h, u | 10 |
| u, g | 10 |
| p, u | 5 |
| u, g | 5 |
| p, u | 12 |
| u, n | 12 |
| b, u | 4 |
| u, n | 4 |
| h, u | 5 |
| u, g | 5 |
| g, s | 5 |
이제 할 일은 다음 그림처럼 바이그램 쌍이 같은 것끼리 그 빈도를 합쳐주는 것입니다. 표4와 같습니다.
표4 BPE 어휘 집합 구축 (3)
| 바이그램 쌍 | 빈도 |
|---|---|
| b, u | 4 |
| g, s | 5 |
| h, u | 15 |
| p, u | 17 |
| u, g | 20 |
| u, n | 16 |
가장 많이 등장한 바이그램 쌍은 u, g로 총 20회입니다. 따라서 u와 g를 합친 ug를 어휘 집합에 추가합니다. 다음과 같습니다.
b,g,h,n,p,s,u, ug
표5는 표2를 새로운 어휘 집합에 맞게 다시 쓴 결과입니다. u와 g를 병합했으므로 표2의 각 빈도는 그대로인 채 ①h, u, g가 h, ug로 ②p, u, g가 p, ug로 ③h, u, g, s가 h, ug, s로 바뀌었음을 확인할 수 있습니다.
표5 BPE 어휘 집합 구축 (4)
| 토큰 | 빈도 |
|---|---|
| h, ug | 10 |
| p, ug | 5 |
| p, u, n | 12 |
| b, u, n | 4 |
| h, ug, s | 5 |
표6은 표5를 바이그램 쌍 빈도로 나타낸 결과입니다. 계산 과정은 표3에서 표4를 얻었던 것과 같습니다.
표6 BPE 어휘 집합 구축 (5)
| 바이그램 쌍 | 빈도 |
|---|---|
| b, u | 4 |
| h, ug | 15 |
| p, u | 12 |
| p, ug | 5 |
| u, n | 16 |
| ug, s | 5 |
이번에 가장 많이 등장한 바이그램 쌍은 u, n으로 총 16회입니다. 따라서 u와 n을 합친 un을 어휘 집합에 추가합니다. 다음과 같습니다.
b,g,h,n,p,s,u,ug, un
표7은 표5를 새로운 어휘 집합에 맞게 다시 쓴 결과이고, 표8은 표7을 바탕으로 바이그램 쌍 빈도를 나타낸 결과입니다.
표7 BPE 어휘 집합 구축 (6)
| 토큰 | 빈도 |
|---|---|
| h, ug | 10 |
| p, ug | 5 |
| p, un | 12 |
| b, un | 4 |
| h, ug, s | 5 |
표8 BPE 어휘 집합 구축 (7)
| 바이그램 쌍 | 빈도 |
|---|---|
| b, un | 4 |
| h, ug | 15 |
| p, ug | 5 |
| p, un | 12 |
| ug, s | 5 |
이번에 가장 많이 등장한 바이그램 쌍은 h, ug로 총 15회입니다. 따라서 h와 ug를 합친 hug를 어휘 집합에 추가합니다. 다음과 같습니다.
BPE 어휘 집합 구축 결과 (1) vocab.json
b,g,h,n,p,s,u,ug,un, hug
BPE 어휘 집합 구축은 어휘 집합이 사용자가 정한 크기가 될 때까지 반복해서 수행합니다. 만일 어휘 집합 크기를 10개로 정해놓았다면, 어휘가 10개가 되었으므로 여기에서 BPE 어휘 집합 구축 절차를 마칩니다. 참고로 위의 어휘 집합은 허깅페이스 토크나이저 패키지를 활용한 실습에서 vocab.json 형태로 저장됩니다.
한편 지금까지 가장 많이 등장한 바이그램 쌍을 병합(merge)하는 방식으로 BPE 어휘 집합을 구축해왔는데요. 표9는 그 병합 이력을 한 눈에 보기 좋게 모아놓은 것입니다. 왼쪽부터 차례로 표4, 표6, 표8에 각각 대응합니다. 표9를 활용해 merge.txt라는 자료를 만듭니다. 이는 BPE 토큰화 과정에서 서브워드 병합 우선 순위를 정하는 데 쓰입니다.
표9 바이그램 쌍 병합 이력
처음 병합한 대상은 u, g, 두번째는 u, n, 마지막은 h, ug였음을 확인할 수 있습니다. 이 내용 그대로 merges.txt 형태로 저장합니다. 다음과 같습니다.
BPE 어휘 집합 구축 결과 (2) merges.txt
- u g
- u n
- h ug
BPE 토큰화
어휘 집합(vocab.json)과 병합 우선순위(merge.txt)가 있으면 토큰화를 수행할 수 있습니다. 예컨대 pug bug mug라는 문장을 토큰화한다고 가정해 봅시다. 그러면 일단 이 문장에 프리토크나이즈를 수행해 공백 단위로 분리합니다. 다음과 같습니다.
pug bug mug>pug,bug,mug
이렇게 분리된 토큰들 각각에 대해 BPE 토큰화를 수행합니다. 가장 먼저 토큰화를 수행할 대상은 pug입니다. 우리는 BPE 기본 단위로 문자를 상정하고 있으니, pug를 문자 단위로 분리합니다.
pug>p,u,g
이후 merges.txt를 참고해 병합 우선 순위를 부여합니다.
p,u:merges.txt에 존재하지 않음 (=우선 순위 없음)u,g:merges.txt에서 첫번째 우선 순위
둘 중에 u와 g의 우선순위가 높으므로 이들을 먼저 합쳐 줍니다. 다음과 같습니다.
p,u,g>p,ug
merges.txt를 한번 더 참고해 병합 우선 순위를 부여합니다.
p,ug: 해당 바이그램 쌍이merges.txt에 존재하지 않음 (=우선 순위 없음)
더 이상 병합 대상이 존재하지 않으므로 병합을 그만둡니다. 그 다음으로는 p, ug가 각각 어휘 집합(vocab.json)에 있는지를 검사합니다. 둘 모두 있으므로 pug의 토큰화 최종 결과는 p, ug입니다.
이번엔 bug 차례입니다. bug를 문자 단위로 분리합니다.
bug>b,u,g
이후 merges.txt를 참고해 병합 우선 순위를 부여합니다.
b,u:merges.txt에 존재하지 않음 (=우선 순위 없음)u,g:merges.txt에서 첫번째 우선 순위
둘 중에 u와 g의 우선순위가 높으므로 이들을 먼저 합쳐 줍니다. 다음과 같습니다.
b,u,g>b,ug
merges.txt를 한번 더 참고해 병합 우선 순위를 부여합니다.
b,ug: 해당 바이그램 쌍이merges.txt에 존재하지 않음 (=우선 순위 없음)
더 이상 병합 대상이 존재하지 않으므로 병합을 그만둡니다. 그 다음으로는 b, ug가 각각 어휘 집합(vocab.json)에 있는지를 검사합니다. 둘 모두 있으므로 bug의 토큰화 최종 결과는 b, ug입니다.
마지막으로 토큰화를 수행할 대상은 mug입니다. merges.txt를 참고해 병합 우선 순위를 따져보면 ug를 먼저 합치게 됩니다. 따라서 병합 결과는 m, ug이 될텐데요. 이 가운데 m은 어휘 집합에 없으므로 mug의 최종 토큰화 결과는 <unk>, ug가 됩니다. 여기서 <unk>는 미등록 토큰을 의미합니다
결론적으로 pug bug mug라는 문장의 BPE 토큰화 결과는 다음과 같습니다.
pug bug mug>p,ug,b,ug,<unk>,ug
일반적으로 알파벳 등 개별 문자들은 BPE 어휘 집합을 구축할 때 초기 사전에 들어가므로 m의 사례처럼 미등록 토큰이 발생하는 경우는 많지 않습니다. BPE가 어휘 집합 크기를 합리적으 로 유지하면서도 어휘를 구축할 때 보지 못했던 단어(신조어 등)에 대해서 유의미한 분절을 수행할 수 있는 배경입니다.
워드피스
워드피스(wordpiece)는 말뭉치에서 자주 등장한 문자열을 토큰으로 인식한다는 점에서 BPE와 본질적으로 유사합니다. 다만 어휘 집합을 구축할 때 문자열을 병합하는 기준이 다릅니다. 워드피스는 BPE처럼 단순히 빈도를 기준으로 병합하는 것이 아니라, 병합했을 때 말뭉치의 우도(likelihood)를 가장 높이는 쌍을 병합합니다.
다음 식은 병합 후보가 $a$, $b$일 때 판단의 근거가 되는 값을 계산하는 방법입니다. 다음 식에서 $\text{#}a$, $\text{#}b$, $\text{#}ab$는 각각 $a$, $b$, $ab$라는 문자열의 빈도수, $n$은 전체 글자 수를 가리킵니다. 즉, 분자는 $ab$가 연이어 등장할 확률, 분모는 $a$, $b$가 각각 등장할 확률의 곱입니다.
수식1 병합 후보가 a, b일 때 워드피스의 병합 기준
\[\frac{\frac{\text{#}ab}{n}}{\frac{\text{#}a}{n} \times \frac{\text{#}b}{n}}\]이 수식의 값이 커지려면 $a$와 $b$가 서로 독립(각각의 등장이 서로의 등장에 전혀 영향을 주지 않는 상태)임을 가정했을 때보다 둘이 자주 동시에 등장해야 합니다. 즉, 워드피스에서는 병합 후보에 오른 쌍을 미리 병합해 보고 잃는 것과 가치 등을 판단한 후에 병합합니다. 워드피스는 병합 대상 전체 후보들 가운데 위와 같이 계산한 값이 가장 높은 쌍을 합칩니다.
허깅페이스 tokenizers를 사용한다면 토큰화를 수행하는 방식도 BPE와 워드피스가 약간 다릅니다. BPE는 어절별로 병합 우선순위(merges.txt)가 높은 바이그램 쌍을 반복해서 병합합니다. 그다음에 병합된 토큰이 어휘 집합(vocab.json)에 있는지 확인해 최종 결과를 도출합니다.
그런데 워드피스는 어휘 집합(vocab.txt)만 가지고 토큰화합니다. 워드피스에서는 분석 대상 어절에 어휘 집합에 있는 서브워드가 포함돼 있을 때 해당 서브워드를 어절에서 분리합니다. 단, 이러한 서브워드 후보가 여럿 있을 경우 가장 긴 서브워드를 선택합니다. 이후 어절의 나머지에서 어휘 집합에 있는 서브워드를 다시 찾고(최장 일치 기준), 또 분리합니다. 분석 대상 문자열에서 서브워드 후보가 하나도 없으면 해당 문자열 전체를 미등록 단어로 취급합니다.