[NLP] Byte-Pair Encoding tokenization

바이트 페어 인코딩(BPE)는 'Byte'라는 단어에서 유래한 것 처럼 본래 정보를 압축하는 알고리즘으로 쓰였으나, 최근에는 NLP모델에 널리 쓰이고 있는 토큰화 기법입니다.

예를 들어, GPT같은 NLP 모델에서 BPE 기법으로 토큰화를 수행하며, BERT에서도 BPE와 유사한 word-piece를 토크나이저로 사용하고 있습니다.

 

0. Subword Segmentation(단어 분리)

- 하나의 토큰이 여러 개의 subword의 조합으로 이루어져 있다는 가정 하에, subword단위의 tokenization을 수행하여 단어를 이해하려는 목적을 갖는 전처리 기법

 

▷Byte-Pair Encoding은 Subword Segmentation의 대표적인 알고리즘입니다.

 

1. BPE 알고리즘

기본적으로 문장이 모두 이어져있는 것이 아닌, 띄어쓰기 등으로 1차 분리되어 있다던가  pre-tokenize 되어 있다고 가정합니다. 

예시 문장 : {"hug", "pug", "pun", "bun", "hugs"}의 다섯 개의 단어들로 구성되어 있다고 가정합시다.

 

▷ base vocabulary(처음 사전)는  ["b", "g", "h", "n", "p", "s", "u"] 가 될 것입니다.

 

▷문장 내에서 단어들이 가지고 있는 빈도수가 아래와 같이 나타난다고 가정합시다.

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

 

▶ 단어(어절 단위)를 문자 단위로 split해줍니다.

("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)

해석:
- ("h", "u") 쌍은 "hug"와 "hugs" 두 곳에 동시에 존재하는 쌍입니다. 따라서 총합을 10+5 = 15로 표현할 수 있습니다.

- ("u", "g") 쌍은 "hug", "pug", "hugs" 세 곳에 동시에 존재하므로, 10+5+5 =20번 나타난다고 표현할 수 있습니다.
이때, ug쌍이 가장 큰 빈도수로 표현됩니다. 합병할 쌍으로 첫 번째 선택!)

 

▶ 첫 번째 합병 규칙을 ("u", "g") → "ug" 로 설정하여 ug를 사전에 추가합니다.

합병 후의 전체 corpus는 다음과 같습니다.

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)

 

▶ 그 다음의 빈도수가 높은 쌍은 ("h", "ug") - 10+5 = 15가 될 것이며, 따라서 다음 합병 규칙을 ("h", "ug") → "hug"로 설정합니다.

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]
Corpus: ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)

 

→ 이런 과정을 미리 정해둔 vocabulary 사이즈가 될 때 까지 반복합니다.

 

 

---

2. Code

• corpus 예시

corpus = [
    '이 영화를 영화관에서 직접 보지 못한 것을 평생 후회할 것 같다. 보는 내내 감탄을 자아냈고 절대 잊지 못할 여운으로 남을 것이다.',
    '평점이 이해되지 않는다 최소 9점은 받아야 한다 반전이 정말 끝내준다',
    '말로 표현할 수 없다 완벽한 영화 보는 내내 소름이 돋았다'
]

 

• 어절 단위 분리(띄어쓰기)

def get_dictionary(corpus):
    """ 데이터를 읽어와 단어 사전 구축
    Args:
        corpus: 여러 텍스트 데이터가 담긴 리스트
    Returns:
        dict(vocab): 문장 데이터 별 character 단위로 구분된(띄어쓰기) 후보 사전
    """
    dictionary = defaultdict(int)
    for line in corpus:
        tokens = preprocess(line).strip().split(" ")
        for token in tokens:
            dictionary[" ".join(list(token)) + " </w>"] += 1
    
    return dict(dictionary)

실행결과, 다음과 같은 사전이 생성됩니다.

dictionary = get_dictionary(corpus)
print(dictionary)
 
{'이 </w>': 1,
 '영 화 를 </w>': 1,
 '영 화 관 에 서 </w>': 1,
 '직 접 </w>': 1,
 '보 지 </w>': 1,
 '못 한 </w>': 1,
 '것 을 </w>': 1,
 '평 생 </w>': 1,
 '후 회 할 </w>': 1,
 '것 </w>': 1,
 '같 다 </w>': 1,
 '보 는 </w>': 2,
 '내 내 </w>': 2,
 '감 탄 을 </w>': 1,
 ...}

 

• 가장 많이 등장한(빈도수가 높은) character pair 찾기

def get_pairs(dictionary):
    """ 딕셔너리를 활용한 바이그램 페어 구축
        Args: 
            dictionary: 어절 token 별 character 단위로 분리된 dictionary
        Returns:
            pairs: bi-gram pair
    """
    pairs = defaultdict(int)
    for word, freq in dictionary.items():
        word_lst = word.split()
        for i in range(len(word_lst)-1):
            pairs[(word_lst[i], word_lst[i+1])] += freq
            
    return dict(pairs)
    
    #함수의 실행 결과는 다음과 같습니다.
    
pairs = get_pairs(dictionary)
print(pairs)
 
{('이', '</w>'): 4,
 ('영', '화'): 3,
 ('화', '를'): 1,
 ('를', '</w>'): 1,
 ('화', '관'): 1,
 ('관', '에'): 1,
 ('에', '서'): 1,
 ('서', '</w>'): 1,
 ('직', '접'): 1,
 ('접', '</w>'): 1,
 ('보', '지'): 1,
 ('지', '</w>'): 3,
 ('못', '한'): 1,
 ('한', '</w>'): 2,
 ('것', '을'): 1,
 ('을', '</w>'): 3,
 ('평', '생'): 1,
 ...}

그 후, 최대 빈도수 찾기

print(max(pairs, key=pairs.get))

('다', '</w>')

 

• 찾은 쌍을 합병하고 사전에 추가하여 업데이트 하기

def merge_dictionary(pairs, dictionary):
    """ 가장 자주 등장한 bi-gram pair를 merge(공백 제거)
    Args:
        pairs: bi-gram pair
        dictionary: 문장 데이터 별 character 단위로 구분된(띄어쓰기) 후보 사전
    Returns:
        dict(result): 가장 자주 등장한 bi-gram pair를 merge한 dictionary
    """
    result = defaultdict(int)
    best_pair = max(pairs, key=pairs.get)
    for word, freq in dictionary.items():
        paired = word.replace(" ".join(best_pair), "".join(best_pair))
        result[paired] = dictionary[word]
    return dict(result)

 

예를 들어 현재 상태의 dictionary와 pair를 통해 dictionary를 업데이트 할 경우 아래와 같은 결과를 얻을 수 있습니다.

가장 많이 등장한 ('다', '</w>')의 경우 공백이 제거된 모습을 볼 수 있습니다.

temp = merge_dictionary(pairs, dictionary)
print(temp)
 
{...
 '것 </w>': 1,
 '같 다</w>': 1,
  ...
 '돋 았 다</w>': 1}

 

• 반복을 통해 사전 업데이트
  • 반복 횟수는 사전의 크기에 도달할 때 까지이므로, 사용자가 지정하는 하이퍼파라미터입니다.

  iter_nums = 20
  dictionary = get_dictionary(corpus)
  for i in range(iter_nums):
      pairs = get_pairs(dictionary)
      dictionary = merge_dictionary(pairs, dictionary)

 

그 결과 아래의 dictionary를 얻을 수 있습니다.

공백이 포함되었던 어절 token 중 일부에서 공백이 제거된 모습을 확인 하실 수 있습니다.

print(dictionary)
 
{'이</w>': 1,
 '영화를</w>': 1,
 '영화관에서</w>': 1,
 '직접</w>': 1,
 '보 지</w>': 1,
 '못 한</w>': 1,
 '것 을</w>': 1,
 '평 생 </w>': 1,
 '후 회 할</w>': 1,
 '것 </w>': 1,
 '같 다</w>': 1,
 '보는</w>': 2,
 '내내</w>': 2,
 '감 탄 을</w>': 1,
 '자 아 냈 고 </w>': 1,
 '절 대 </w>': 1,
 '잊 지</w>': 1,
 '못 할</w>': 1,
 '여 운 으 로</w>': 1,
 '남 을</w>': 1,
 '것 이 다</w>': 1,
 '평 점 이</w>': 1,
 '이 해 되 지</w>': 1,
 '않 는 다</w>': 1,
 '최 소 </w>': 1,
 '점 은 </w>': 1,
 '받 아 야 </w>': 1,
 '한 다</w>': 1,
 '반 전 이</w>': 1,
 '정 말 </w>': 1,
 '끝 내 준 다</w>': 1,
 '말 로</w>': 1,
 '표 현 할</w>': 1,
 '수 </w>': 1,
 '없 다</w>': 1,
 '완 벽 한</w>': 1,
 '영화 </w>': 1,
 '소 름 이</w>': 1,
 '돋 았 다</w>': 1}

 

• 최종 vocabulary 생성

vocabulary는 dictionary를 띄어쓰기 단위로 분리한 뒤, 그중 unique한 값들만 취하면 됩니다.

def get_vocab(dictionary):
    """ dictionary에서 최종 vocabulary를 만드는 함수
    Args:
        dictionary: merge가 수행된 dictionary
    Returns:
        dict(vocab): 최종 vocabulary
    """
    result = defaultdict(int)
    for word, freq in dictionary.items():
        tokens = word.split()
        for token in tokens:
            result[token] += freq
    return dict(result)

 

마지막으로 생성된 vocabulary를 확인 해 볼까요?

vocab = get_vocab(dictionary)
print(vocab)
 
{'이</w>': 4,
 '영화를</w>': 1,
 '영화관에서</w>': 1,
 '직접</w>': 1,
 '보': 1,
 '지</w>': 3,
 '못': 2,
 '한</w>': 2,
 '것': 3,
 '을</w>': 3,
 '평': 2,
 '생': 1,
 '</w>': 10,
 '후': 1,
 '회': 1,
 '할</w>': 3,
 '같': 1,
 '다</w>': 7,
 '보는</w>': 2,
 '내내</w>': 2,
 '감': 1,
 '탄': 1,
 '자': 1,
 '아': 2,
 '냈': 1,
 '고': 1,
 '절': 1,
 '대': 1,
 '잊': 1,
 '여': 1,
 '운': 1,
 '으': 1,
 '로</w>': 2,
 '남': 1,
 '이': 2,
 '점': 2,
 '해': 1,
 '되': 1,
 '않': 1,
 '는': 1,
 '최': 1,
 '소': 2,
 '은': 1,
 '받': 1,
 '야': 1,
 '한': 1,
 '반': 1,
 '전': 1,
 '정': 1,
 '말': 2,
 '끝': 1,
 '내': 1,
 '준': 1,
 '표': 1,
 '현': 1,
 '수': 1,
 '없': 1,
 '완': 1,
 '벽': 1,
 '영화': 1,
 '름': 1,
 '돋': 1,
 '았': 1}

 

References

• Byte-Pair Encoding tokenization - Hugging Face NLP Course