[Python/NLP] 서브워드 토크나이저 (Subward Tokenizer) :: BPE

---

Subward Tokenizer

 

기계를 아무리 많이 학습시킨다한들, 세상에 있는 모든 단어들을 가르쳐 줄 순 없다.

이 단어들을 OOV(Out-Of-Vocabulary) 또는 UNK(Unkown Token) 이라고 표현한다.

이 경우, 모델링이 까다로워진다. 

 

이 때 서브워드 분리(Subward Segmentation) 작업을 진행하면

하나의 단어가 더 작은 단위의 의미있는여러 서브워드들(예를 들면 Birthday  = Birth + Day, 하늘색 = 하늘 + 색)의 조합으로 구성된 경우가 많기 때문에, 하나의 단어를 여러 서브워드로 분리해서 단어를 인코딩 및 임베딩하겠다는 의도를 가진 전처리 작업이다. 이를 통해 희귀단어나 신조어와 같은 문제를 해결할 수 있다.

실제로 언어의 특성에 따라서 영어나 한국어는 서브워드 분리를 했을 때 어느정도 유의미한 결과를 도출한다.

 

내가 본 책에서는 이런 작업을 하는 Tokenizer 를 서브워드 토크나이저라고 명명했다.

 

 

BPE (Byte Pair Encoding)

---

https://arxiv.org/abs/1508.07909

Neural Machine Translation of Rare Words with Subword Units

 

BPE(Byte Pair Encdoing) 알고리즘은 1994년에 제안된 압축 알고리즘이지만, 이후 자연어 처리의 서브워드 분리에서 두각을 나타내 응용되게 되었다. 

OpenAI 에서 GPT 모델을 사전 학습시킬 때 토큰화를 위해 사용되었다.

GPT, GPT-2, RoBERTa, BART 및 DeBERTa 를 포함한 많은 Transformer 모델에서 사용된다.

 

aaabdaaabacc 

 

라는 문자열을 BPE 를 수행한다고 해보자.

 

BPE 는 기본적으로 연속적으로 가장 많이 등장한 글자의 쌍을 찾아서 하나의 글자로 병합하는 방식을 사용한다.

여기서는 글자라는 말 대신 byte (바이트) 라고 한다.

예를 들어, 위의 문자열에서 가장 많이 등장하는 바이트의 쌍(pair)은 'aa' 이다.

우리는 단일 글자가 아니라 쌍으로 본다.

이 'aa' 를 하나의 바이트인 Z 로 치환시켜보자.

 

ZabdZabacc

Z = aa

 

이제 남아있는 위의 쌍에서 가장 많이 등장하는 쌍은 ab이다.

ab 를 Y로 치환해보자.

 

ZYdZYacc

Y = ab
Z = aa

 

이제 가장 많이 남아있는 바이트의 쌍은 ZY 이다.

ZY 를 X로 치환시켜보자.

 

ZdZacc

Y = ab
Z = aa
X = ZY

 

이제 더 이상 병합할 바이트의 쌍이 남아있지 않으므로, BPE 는 위의 결과를 최종 결과로 하여 종료된다.

이것이 BPE (Byte Pair Encoding) 이다.

 

 

 

 

자연어 처리에서의 BPE(Byte Pair Encdoing)

---

그렇다면 자연어 처리에서는 이를 어떻게 응용할까?

위와 같은 알고리즘을 우리는 서브워드 분리를 할 때 사용한다. 기존의 있던 단어를 쪼개어 쌍으로 본다.

자연어처리에서의 BPE 는 글자 단위에서 점차적으로 단어 집합 (vocabulary) 를 만들어내는 Bottom Up 형식의 접근을 사용한다.

train 데이터에 있는 단어들을 모든 글자나 유니코드 단위로 단어 집합(vocabulary) 로 만들고, 가장 많이 등장하는 유니그램을 하나의 유니그램으로 통합한다.

 

우리가 어떠한 데이터로부터 각 단어들의 빈도수를 카운트 했다고 해보자. 그리고 각 단어와 그 단어의 빈도수가 기록ㄷㅚ어져 있는 해당 결과는 임의로 dictionary 라는 이름을 붙였다.

# Dictionary
# 훈련 데이터에 있는 단어와 등장 빈도수
low : 5, lower : 2, newset : 6, widest : 3

 

이 데이터에는 low 라는 단어가 5회 등장했고, lower 는 2번, newest 는 6번, widest는 3번 등장했다는 의미이다.

그렇다면 이 Dictionary 로부터 훈련 데이터의 단어 집합을 얻는 것은 간단하다.

 

# Vocabulary
low, lower, newset, widest

이 단어들을 모델에 학습시킨다면, 우리 모델은 lowest 라는 단어는 vocabulary 에 없으므로 해당 단어에 대해서 제대로 대응하지 못하는 OOV 문제가 발생한다.

이를 예방하기 위해 우리는 BPE 를 적용한다.

 

위의 Dictionary 에 BPE 를 적용해보자.

Dictionary 의 모든 단어를 글자 단위로 분리한다. 이후 이 딕셔너리는 계속 업데이트되고, 단어 집합을 업데이트 하기 위해 지속적으로 참고되는 참고자료의 역할을 하게 된다.

# Dictionary
l o w : 5, l o w e r : 2, n e w e s t : 6, w i d e s t : 3

 

그리고 위의 딕셔너리를 참고로 한 초기 단어 집합 (Vocabulary) 는 다음과 같다.

# vocabulary
l, o, w, e, r, n, s, t, i, d

vocabulary 에 중복된 값은 없다.

vocabulary 가 단일 알파벳으로 구성되는 것이다.

BPE의 특징은 알고리즘의 동작을 몇 번 반복(iteration) 할 지 사용자가 정한다는 것이다.

그러니까, 위에서 했던 쌍들을 치환시키는 것을 몇 번 반복할 지 사용자가 정한다.

위의 딕셔너리를 봤을 때, 현재 빈도수가 가장 높은 쌍은 (e,s)이다. (9회)

 

그럼 이 (e,s) 쌍을 es로 묶어보자.

 

# Dictionary Update

l o w : 5,
l o w e r : 2,
n e w es t : 6,
w i d es t : 3

# Vocabulary Update
l, o, w, e, r, n, s, t, d, es

vocabulary 에 es가 업데이트 되었다.

 

이제 빈도수가 가장 높은 쌍은 (es, t) 이다.

이를 est 로 통합해보자.

 

# Dictionary Update
l o w : 5,
l o w e r : 2,
n e w est : 6
w i d est : 3

# Vocabulary Update
l, o, w, e, r, n, s, t, i, d, es, est

이제 빈도수가 가장 높은 쌍은 l, o 이다. lo로 통합하자.

 

# Dictionary Uddate
lo w : 4,
lo w e r : 2,
n e w est : 6,
w i d est : 3

# Vocabulary Update
l, o, w, e, r, n, s, t, i, d, es, est, lo

이를 10회 반복한다고 했을 때 (iteration = 10)

얻은 최종 딕셔너리와 vocabulary 는 다음과 같다.

 

# dictionary update!
low : 5,
low e r : 2,
newest : 6,
widest : 3

# vocabulary update!
l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new, newest, wi, wid, widest

이제 이 경우엔, 테스트 과정에서 'lowest' 라는 단어가 등장한다면,

기존에는 OOV 에 해당하는 단어가 되었겠지만 BPE 알고리즘을 사용한 단어 집합에서는 'lowest' 가 OOV가 아니다.

기계는 우선 'lowest' 를 글자 단위로 분할한다. 즉 'l, o, w, e, s, t'가 된다.

이후 기계는 위의 vocabulary 를 참고로 해서 low 와 est 를 찾아낼 것이다.

이후 lowest 를 기계는 low 와 est 로 인코딩 할 것이다.

그리고 이 두 단어는 둘 다 단어 집합에 있는 단어이므로 OOV가 아니다.

 

이를 그림으로 표현한다면 이와 같다.

https://wikidocs.net/22592

 

 

 

실습

---

환경은 Colab 환경에서 작업했다.

import re, collections 
# collections : Python 의 컨테이너 라이브러리. 
# dict, list, set 및 tuple에 대한 대안을 제공하는 특수 컨테이너 데이터형을 구현합니다.

from IPython.display import display, Markdown, Latex

# BPE를 몇 번 반복할 지 정하기 : 10회
num_merges = 10

dictionary = {'l o w </w>' : 5,
         'l o w e r </w>' : 2,
         'n e w e s t </w>':6,
         'w i d e s t </w>':3
         }

def get_stats(dictionary):
    # 유니그램의 pair들의 빈도수를 카운트
    pairs = collections.defaultdict(int)
    for word, freq in dictionary.items():
        symbols = word.split()
        for i in range(len(symbols)-1):
            pairs[symbols[i],symbols[i+1]] += freq
    print('현재 pair들의 빈도수 :', dict(pairs))
    return pairs

def merge_dictionary(pair, v_in):
    v_out = {}
    bigram = re.escape(' '.join(pair))
    p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out

bpe_codes = {}
bpe_codes_reverse = {}

for i in range(num_merges):
    display(Markdown("### Iteration {}".format(i + 1)))
    pairs = get_stats(dictionary)
    best = max(pairs, key=pairs.get)
    dictionary = merge_dictionary(best, dictionary)

    bpe_codes[best] = i
    bpe_codes_reverse[best[0] + best[1]] = best

    print("new merge: {}".format(best))
    print("dictionary: {}".format(dictionary))

아래는 실행결과이다.

Iteration 1
현재 pair들의 빈도수 : {('l', 'o'): 7, ('o', 'w'): 7, ('w', '</w>'): 5, ('w', 'e'): 8, ('e', 'r'): 2, ('r', '</w>'): 2, ('n', 'e'): 6, ('e', 'w'): 6, ('e', 's'): 9, ('s', 't'): 9, ('t', '</w>'): 9, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'e'): 3}
new merge: ('e', 's')
dictionary: {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w es t </w>': 6, 'w i d es t </w>': 3}

Iteration 2
현재 pair들의 빈도수 : {('l', 'o'): 7, ('o', 'w'): 7, ('w', '</w>'): 5, ('w', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('n', 'e'): 6, ('e', 'w'): 6, ('w', 'es'): 6, ('es', 't'): 9, ('t', '</w>'): 9, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'es'): 3}
new merge: ('es', 't')
dictionary: {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est </w>': 6, 'w i d est </w>': 3}

Iteration 3
현재 pair들의 빈도수 : {('l', 'o'): 7, ('o', 'w'): 7, ('w', '</w>'): 5, ('w', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('n', 'e'): 6, ('e', 'w'): 6, ('w', 'est'): 6, ('est', '</w>'): 9, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est'): 3}
new merge: ('est', '</w>')
dictionary: {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}

Iteration 4
현재 pair들의 빈도수 : {('l', 'o'): 7, ('o', 'w'): 7, ('w', '</w>'): 5, ('w', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('n', 'e'): 6, ('e', 'w'): 6, ('w', 'est</w>'): 6, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('l', 'o')
dictionary: {'lo w </w>': 5, 'lo w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}

Iteration 5
현재 pair들의 빈도수 : {('lo', 'w'): 7, ('w', '</w>'): 5, ('w', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('n', 'e'): 6, ('e', 'w'): 6, ('w', 'est</w>'): 6, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('lo', 'w')
dictionary: {'low </w>': 5, 'low e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}

Iteration 6
현재 pair들의 빈도수 : {('low', '</w>'): 5, ('low', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('n', 'e'): 6, ('e', 'w'): 6, ('w', 'est</w>'): 6, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('n', 'e')
dictionary: {'low </w>': 5, 'low e r </w>': 2, 'ne w est</w>': 6, 'w i d est</w>': 3}

Iteration 7
현재 pair들의 빈도수 : {('low', '</w>'): 5, ('low', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('ne', 'w'): 6, ('w', 'est</w>'): 6, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('ne', 'w')
dictionary: {'low </w>': 5, 'low e r </w>': 2, 'new est</w>': 6, 'w i d est</w>': 3}

Iteration 8
현재 pair들의 빈도수 : {('low', '</w>'): 5, ('low', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('new', 'est</w>'): 6, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('new', 'est</w>')
dictionary: {'low </w>': 5, 'low e r </w>': 2, 'newest</w>': 6, 'w i d est</w>': 3}

Iteration 9
현재 pair들의 빈도수 : {('low', '</w>'): 5, ('low', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('low', '</w>')
dictionary: {'low</w>': 5, 'low e r </w>': 2, 'newest</w>': 6, 'w i d est</w>': 3}

Iteration 10
현재 pair들의 빈도수 : {('low', 'e'): 2, ('e', 'r'): 2, ('r', '</w>'): 2, ('w', 'i'): 3, ('i', 'd'): 3, ('d', 'est</w>'): 3}
new merge: ('w', 'i')
dictionary: {'low</w>': 5, 'low e r </w>': 2, 'newest</w>': 6, 'wi d est</w>': 3}

 

여기서 bpe_codes 를 입력하면 merge 했던 기록들을 확인할 수 있다.

{('e', 's'): 0, ('es', 't'): 1, ('est', '</w>'): 2, ('l', 'o'): 3, 
('lo', 'w'): 4, ('n', 'e'): 5, ('ne', 'w'): 6, 
('new', 'est</w>'): 7, ('low', '</w>'): 8, ('w', 'i'): 9}

이 기록은 새로운 단어가 등장했을 때 현재 갖고 있는 서브워드 단어 집합에 의거하여 분리하는 일에 참고할 수 있다.

 

 

 

 

OOV 대처하기

def get_pairs(word):
    """Return set of symbol pairs in a word.
    Word is represented as a tuple of symbols (symbols being variable-length strings).
    """
    pairs = set()
    prev_char = word[0]
    for char in word[1:]:
        pairs.add((prev_char, char))
        prev_char = char
    return pairs


def encode(orig):
    """Encode word based on list of BPE merge operations, which are applied consecutively"""

    word = tuple(orig) + ('</w>',)
    display(Markdown("__word split into characters:__ <tt>{}</tt>".format(word)))

    pairs = get_pairs(word)    

    if not pairs:
        return orig

    iteration = 0
    while True:
        iteration += 1
        display(Markdown("__Iteration {}:__".format(iteration)))

        print("bigrams in the word: {}".format(pairs))
        bigram = min(pairs, key = lambda pair: bpe_codes.get(pair, float('inf')))
        print("candidate for merging: {}".format(bigram))
        if bigram not in bpe_codes:
            display(Markdown("__Candidate not in BPE merges, algorithm stops.__"))
            break
        first, second = bigram
        new_word = []
        i = 0
        while i < len(word):
            try:
                j = word.index(first, i)
                new_word.extend(word[i:j])
                i = j
            except:
                new_word.extend(word[i:])
                break

            if word[i] == first and i < len(word)-1 and word[i+1] == second:
                new_word.append(first+second)
                i += 2
            else:
                new_word.append(word[i])
                i += 1
        new_word = tuple(new_word)
        word = new_word
        print("word after merging: {}".format(word))
        if len(word) == 1:
            break
        else:
            pairs = get_pairs(word)

    # 특별 토큰인 </w>는 출력하지 않는다.
    if word[-1] == '</w>':
        word = word[:-1]
    elif word[-1].endswith('</w>'):
        word = word[:-1] + (word[-1].replace('</w>',''),)

    return word

loki 라는 단어를 BPE 시켜보자.

encode('loki')

word split into characters: ('l', 'o', 'k', 'i', '')

Iteration 1:

bigrams in the word: {('l', 'o'), ('o', 'k'), ('k', 'i'), ('i', '</w>')}
candidate for merging: ('l', 'o')
word after merging: ('lo', 'k', 'i', '</w>')
Iteration 2:

bigrams in the word: {('k', 'i'), ('i', '</w>'), ('lo', 'k')}
candidate for merging: ('k', 'i')
Candidate not in BPE merges, algorithm stops.

('lo', 'k', 'i')

위에 dictionary 에 lo 라는 토큰이 있으므로, lo , k i 로 분리해내는 것을 볼 수 있다.

 

encode("lowest")

word split into characters: ('l', 'o', 'w', 'e', 's', 't', '')

Iteration 1:

bigrams in the word: {('l', 'o'), ('w', 'e'), ('s', 't'), ('e', 's'), ('o', 'w'), ('t', '</w>')}
candidate for merging: ('e', 's')
word after merging: ('l', 'o', 'w', 'es', 't', '</w>')
Iteration 2:

bigrams in the word: {('es', 't'), ('l', 'o'), ('w', 'es'), ('o', 'w'), ('t', '</w>')}
candidate for merging: ('es', 't')
word after merging: ('l', 'o', 'w', 'est', '</w>')
Iteration 3:

bigrams in the word: {('l', 'o'), ('w', 'est'), ('o', 'w'), ('est', '</w>')}
candidate for merging: ('est', '</w>')
word after merging: ('l', 'o', 'w', 'est</w>')
Iteration 4:

bigrams in the word: {('l', 'o'), ('o', 'w'), ('w', 'est</w>')}
candidate for merging: ('l', 'o')
word after merging: ('lo', 'w', 'est</w>')
Iteration 5:

bigrams in the word: {('w', 'est</w>'), ('lo', 'w')}
candidate for merging: ('lo', 'w')
word after merging: ('low', 'est</w>')
Iteration 6:

bigrams in the word: {('low', 'est</w>')}
candidate for merging: ('low', 'est</w>')
Candidate not in BPE merges, algorithm stops.

('low', 'est')

lowest 는 low 와 est 가 둘 다 있으므로 low 와 est 로 분리해낸다.

 

encode("highing")

word split into characters: ('h', 'i', 'g', 'h', 'i', 'n', 'g', '')

Iteration 1:

bigrams in the word: {('n', 'g'), ('g', 'h'), ('i', 'n'), ('h', 'i'), ('g', '</w>'), ('i', 'g')}
candidate for merging: ('n', 'g')
Candidate not in BPE merges, algorithm stops.

('h', 'i', 'g', 'h', 'i', 'n', 'g')

반면에 highing 은 아무것도 단어 사전에 없으므로 단일 분리로만 도출해낸다.

BPE 외에도 Wordpiece Tokenizer 나 Unigram Language Model Tokenizer 와 같은 서브워드 분리 알고리즘이 존재한다.

 

이를 실무에서 사용할 땐 sentence piece 나 tokenizers 를 사용한다.

 

 

 

 

 

참고

---

https://wikidocs.net/86649

13. 서브워드 토크나이저(Subword Tokenizer)

 

https://wikidocs.net/166825

5. Byte-Pair Encoding (BPE) 토큰화