Byte Pair Encoding

BPE(byte pair encoding)은 1994년에 위의 논문을 통해 제안된 정보 압축 알고리즘인데, 최근에는 자연어 처리 모델로 많이 쓰이고 있다. 자연어... 아직까진 그냥 이름만 봐도 어려워 보인다. 차근차근 공부해보자.

기계에게 어마무시한 양의 단어를 학습시킨다 해도 세상의 모든 단어를 입력할 수는 없다. 너무 많으니까. 기계는 모르는 단어가 나오면 그 단어를 '단어 사전에 없는 단어'라는 의미에서 'UNK(unknown token)'로 표현한다. 영어 독해를 한다치면 빈칸이 되는 것이다. 영어문제를 풀어본 적이 있다면 누구나 알겠지만, 모르는 단어가 많아질수록 문맥, 주제 파악등이 아주 어려워진다. 기계도 역시 마찬가지로, 모르는 단어가 있으면 문제 푸는 것이 까다로워진다. 이런 상황을 'OOV(out of vocabulary)' 라고 부른다. 

BPE는 이 문제를 완화시키는 대표적인 알고리즘이다. 나는 위에서 BPE를 '정보 압축 알고리즘'이라고 했는데, 어떤 식으로 압축한다는 소리일까? 아래 예시를 보자.

aaabdaaabac

위의 데이터를 입력받은 기계는 자신만의 단어장을 만드는데, 맨 처음에는 데이터의 글자(a,b,c,d)들만으로 단어장을 구성한다. 단어장을 펼치면 a, b, c, d가 입력돼있는 것이다. 근데 위의 데이터를 잘 보면 aa가 제일 자주 나타나는 패턴임을 알 수 있다. 그래서 이 기계씨는 aa를 X로 치환한다. 그럼 위의 데이터는 다음과 같이 바뀐다.

XabdXabac

그리고 기계씨가 갖고 있는 단어장에는 X가 추가되어, {a, b, c, d, X}가 입력돼있다. 또, 데이터를 다시 잘 보면 이제 ab가 제일 자주 나타나는 패턴인 것이 보인다. 기계씨는 이제 ab를 Y로 치환하고, 단어장에는 Y가 추가되며 위의 데이터는

XYdXYac

로 바뀐다. 물론 ab대신 Xa를 치환해도 되겠지만, 빈도수가 서로 같으면 알파벳순으로 앞선 쪽을 먼저 치환한다. 그리고 아까와 마찬가지로 이제 어떤 패턴이 제일 자주 나타나는가를 다시 보면, XY 역시 Z로 치환가능함을 알 수 있다. 최종적으로 데이터의 모양은 다음과 같이 되었고, 기계씨의 단어장에는 {a, b, c, d, X, Y, Z}가 입력돼있다.

XdXac 

이런 방식으로 BPE는 단어장크기를 효율적으로 늘리면서도 데이터 길이 역시 효과적으로 압축할 수 있다. 즉, 말뭉치에서 자주 나타나는 문자열을 덩어리(토큰)로 분석하는 것이다. 위에 설명한 과정을 '토크나이즈'라고 하며, 이런 식으로 하나의 문자열을 '의미있는 서브워드들의 조합'으로 다루는 기법을 '서브워드 분리(subword segmentation)'라고 부른다.    실제로 한국어나 영어는 이런 방법을 시도했을 때 꽤 효과적이라고 한다.

토크나이즈 절차는 크게 두 부분으로 나눌 수 있다.

1. 어휘 집합 구축: 사전과 단어장을 생성하고, 치환된 문자열을 추가하는 과정들                                                  2. 토큰화: 빈도수가 높은 글자 패턴을 병합하여 치환하는 과정들

BPE의 특징은, 이 토크나이즈 과정을 몇 번 반복할지는 사용자가 지정한다는 점이다. 이런 문자열이 있다고 해보자.

'나는 책상 위의 사과를 먹었다 알고 보니 그 사과는 Jason 것이었다 그래서 Jason에게 사과를 했다'

맨 처음 할 일은, 단어 횟수를 기록한 사전을 만드는 것이다. 이 때 단어를 세는 기준은 띄어쓰기이며, 사전의 글자 단어는 모두 띄어 표현한다. 즉,

'나 는' : 1,   '책 상' : 1,   '위 의' : 1,   '사 과 를' : 2,   '먹 었 다' : 1,   '알 고' : 1,   '보 니' : 1,   '그' : 1   '사 과 는' : 1,     'J a s o n' : 1,   '것 이 었 다' : 1,   '그 래 서' : 1,   'J a s o n 에 게' : 1,  '했 다' : 1

위와 같은 사전이 만들어진다. 단어장은 다음과 같다.

{나, 는, 책, 상, 위, 의, 사, 과, 를, 먹, 었, 다, 알, 고, 보, 니, 그, 는, J, a, s, o, n, 것, 이, 래, 서, 에, 게, 했}

쓰기 매우매우 귀찮으니까 토크나이즈 과정을 3회 반복한다고 해보자.

1번째 스텝: 제일 많이 보이는 조합은 '사'+'과'이고, 이 둘을 합친 '사과'가 단어장에 새로 추가된다. 사전은 다음과 같이 바뀌었다.

'나 는' : 1,   '책 상' : 1,   '위 의' : 1,   '사과 를' : 2,   '먹 었 다' : 1,   '알 고' : 1,   '보 니' : 1,   '그' : 1   '사과 는' : 1,     'J a s o n' : 1,   '것 이 었 다' : 1,   '그 래 서' : 1,   'J a s o n 에 게' : 1,   '했 다' : 1     

2번째 스텝: 제일 많이 보이는 조합은 '사과'+'를'이므로, 이 둘을 합친 '사과를' 역시 단어장에 새로 추가된다. 아까와 같은 방식으로 사전은 다음과 같이 변한다. 

'나 는' : 1,   '책 상' : 1,   '위 의' : 1,   '사과를' : 2,   '먹 었 다' : 1,   '알 고' : 1,   '보 니' : 1,   '그' : 1   '사과 는' : 1,     'J a s o n' : 1,   '것 이 었 다' : 1,   '그 래 서' : 1,   'J a s o n 에 게' : 1,   '했 다' : 1     

3번째 스텝: 이제 제일 많이 보이는 조합은 '었'+'다'이니까, 이 둘을 합친 '었다'가 단어장에 새로 입장한다. 역시 사전은 다음과 같이 변한다.

'나 는' : 1,   '책 상' : 1,   '위 의' : 1,   '사과를' : 2,   '먹 었다' : 1,   '알 고' : 1,   '보 니' : 1,   '그' : 1   '사과 는' : 1,     'J a s o n' : 1,   '것 이 었다' : 1,   '그 래 서' : 1,   'J a s o n 에 게' : 1,  '했 다' : 1     

만약 사전과 단어장에 입력된 데이터가 많고, 이런 토크나이즈 과정을 훨씬 많이 반복한다면?

웬만한 새로운 단어는 단어장 내부 토큰들의 조합으로 표현 가능해질 것이다!