빔 서치는
무엇을 찾고 있는가

Deep Speech 2의 신경망은 문장을 출력하지 않습니다. 프레임마다 "이 40ms는 어떤 글자일까"라는 확률표를 뱉을 뿐입니다. 그 확률표 더미에서 문장 하나를 뽑아내는 게 디코딩이고, DS2가 쓰는 방법이 빔 서치입니다. 그런데 각 프레임의 1등을 이어 붙이면 틀립니다. 왜 틀리는지, 빔 서치가 대신 무엇을 세고 있는지, 그리고 논문의 Q(y) = log p_ctc(y|x) + α log p_lm(y) + β·단어수가 무슨 뜻인지 직접 돌려 봅니다.

원 논문: Deep Speech 2: End-to-End Speech Recognition in English and Mandarin (Amodei et al., Baidu Research, arXiv:1512.02595 · ICML 2016) — 언어 모델·디코딩은 3.8절, 배포 최적화는 7.3절 · 디코딩 알고리즘 원전: Hannun et al., 2014

§1 신경망이 실제로 내놓는 것 — 문장이 아니라 확률표

DS2의 출력층을 논문은 이렇게 설명합니다.

"At each output time-step t, the RNN makes a prediction over characters, p(ℓ_t|x), where ℓ_t is either a character in the alphabet or the blank symbol. In English we have ℓ_t ∈ {a, b, c, …, z, space, apostrophe, blank}."

즉 출력은 T개 프레임 × 알파벳 크기짜리 확률 행렬입니다. 5초 발화면 T는 백 단위, 알파벳은 영어 29개(중국어는 6천 개 규모). 여기서 문장 하나를 골라내야 합니다.

여기 blank(빈칸, _로 표기)라는 낯선 기호가 하나 끼어 있습니다. 이건 "이 프레임에는 출력할 글자가 없다"는 뜻입니다. 왜 필요할까요? 글자 하나가 여러 프레임에 걸쳐 발음되기 때문입니다. "cat"의 /a/가 4프레임 동안 이어지면 신경망은 a a a a를 내놓을 텐데, 이걸 그대로 읽으면 "aaaa"가 되죠. 그래서 CTC는 축약 규칙을 씁니다.

§2 CTC 축약 규칙 — 여러 정렬이 한 문장이 된다

프레임마다 기호를 하나씩 고른 것을 정렬(alignment)이라고 합니다. 정렬을 문장으로 바꾸는 규칙은 딱 두 단계, 그리고 순서가 중요합니다.

① 연속으로 같은 기호가 나오면 하나로 병합   c c _ _ a t t  →  c _ a t
② 남은 blank(_)를 전부 제거                  c _ a t        →  c a t

①을 먼저 하는 덕분에 blank가 "글자 경계 표시" 역할을 합니다. 진짜로 같은 글자가 두 번 나와야 하는 "letter"의 tt는 t _ t처럼 사이에 blank를 끼워 표현합니다. blank가 없으면 "tt"와 "t"를 구별할 방법이 없습니다.

p(y | x)  =   Σ         p(정렬 | x)
            정렬 ∈ 축약⁻¹(y)

§3 greedy는 왜 틀리는가 — 최선의 "정렬" ≠ 최선의 "문장"

가장 단순한 디코딩은 프레임마다 1등 글자를 고르고 축약하는 것입니다(greedy 또는 best path 디코딩). 빠르고, 대부분은 잘 됩니다. 그런데 이건 가장 확률 높은 정렬 하나를 찾을 뿐이지 가장 확률 높은 문장을 찾는 게 아닙니다. 둘은 다릅니다.

아래는 그 차이가 드러나도록 만든 6프레임짜리 장난감 확률표입니다. 파란 칸이 각 프레임의 1등입니다.

결과를 보면 greedy는 "ct"를 내놓지만, 실제로 확률이 가장 높은 문장은 "cat"입니다. 두 배 이상 차이가 납니다. 왜 이런 일이 생길까요?

프레임 3·4를 보세요. _(0.45)가 a(0.40)보다 아주 조금 높습니다. 그래서 greedy는 두 프레임 모두 blank를 고르고 a를 통째로 버립니다. 하지만 "cat"은 a가 프레임 3에만, 4에만, 또는 둘 다 나타나는 여러 정렬로 실현될 수 있고, 그 확률들이 합쳐지면 하나뿐인 blank 경로를 압도합니다.

§4 prefix beam search — 알고리즘을 한 프레임씩 실행하기

그럼 모든 정렬을 다 세면 되지 않을까요? 안 됩니다. T=100, 알파벳 29개면 정렬은 29¹⁰⁰개입니다.

해법은 정렬이 아니라 문장 접두사(prefix)를 후보로 관리하는 것입니다. 같은 접두사로 축약되는 정렬들을 하나로 묶어서 확률을 합쳐 두고, 상위 몇 개만 남기며 진행합니다. 이게 prefix beam search입니다.

왜 확률을 두 개로 나눠 들고 다니나

구현에서 가장 헷갈리는 부분입니다. 각 접두사마다 확률을 둘로 나눠 보관합니다.

예를 들어 접두사가 "ca"이고 다음 프레임에 또 a가 온다면:

• … c a(글자로 끝남) 뒤에 a → … c a a → 병합되어 여전히 "ca"
• … c a _(blank로 끝남) 뒤에 a → … c a _ a → blank가 경계를 만들어 "caa"

같은 접두사, 같은 다음 글자인데 결과가 다릅니다. 그래서 둘을 섞어 두면 안 됩니다.

경우의 수를 다 나열하면 끝

사실 규칙이랄 게 따로 없습니다. 이전 상태 2가지 × 이번 기호 3가지 = 6가지를 전부 적어 두면 그게 알고리즘입니다. 이전 상태는 blank로 끝났는지 글자로 끝났는지 둘 중 하나고, 이번 기호는 blank인지 · 직전과 같은 글자인지 · 다른 글자인지 셋 중 하나니까요. 접두사를 ℓ, 그 마지막 글자를 x, 그와 다른 글자를 y라고 하면:

여기서 3·4번 두 줄만 이전 상태에 따라 도착지가 갈립니다. 입력이 ℓ과 x로 똑같은데 결과가 ℓ과 ℓ+x로 달라지죠. 나머지 네 줄(1·2번, 5·6번)은 이전 상태가 무엇이든 같은 칸으로 갑니다 — 그래서 아래 코드가 s["pb"] + s["pnb"]로 더해서 한 번에 보냅니다. 확률을 둘로 나눠 들고 다녀야 하는 이유는 저 두 줄 하나뿐이고, 나머지는 그 대가로 치르는 부기(bookkeeping)입니다.

# prefix beam search — 핵심 갱신 규칙 (선형 확률 기준)
for t in range(T):
    next = defaultdict(lambda: {"pb": 0.0, "pnb": 0.0})
    for prefix, s in beams.items():
        last = prefix[-1] if prefix else None
        for ch, pc in dist[t].items():

            if ch == BLANK:
                # blank: 접두사 그대로, blank로 끝남
                next[prefix]["pb"] += pc * (s["pb"] + s["pnb"])

            elif ch == last:
                # 직전과 같은 글자 — 두 갈래로 갈린다
                next[prefix]["pnb"]      += pc * s["pnb"]   # 병합 → 그대로
                next[prefix + ch]["pnb"] += pc * s["pb"]    # blank 경계 → 확장

            else:
                # 새로운 글자 — 무조건 확장
                next[prefix + ch]["pnb"] += pc * (s["pb"] + s["pnb"])

    # 상위 beam_width 개만 남긴다  ← 여기가 "빔"
    beams = top_k(next, key=lambda s: s["pb"] + s["pnb"], k=beam_width)

순서도로 보면 세 가지가 눈에 들어옵니다.

• 루프가 3중첩 — 비용은 T × 살아 있는 빔 수 × 알파벳 크기입니다. 전수 열거의 29¹⁰⁰이 100 × 500 × 29로 내려오는데, 그 일을 하는 칸은 맨 아래 top_k 하나뿐입니다.
• p_b는 A에서만 늘어난다 — 새로 확장된 접두사(prefix+ch)는 B·C에서 p_nb만 받습니다. 그 접두사가 p_b를 갖는 건 다음 프레임에 blank가 와서 A를 타는 순간뿐이고, 이게 "blank가 경계를 만든다"는 말의 구현입니다.
• 갈라지는 칸은 B 하나 — A와 C는 p_b와 p_nb를 더해서 한 군데로 보냅니다(= 구분할 필요가 없음). 둘을 나눠 들고 다녀야 할 이유가 생기는 곳은 B뿐이고, 나머지 두 칸은 그 대가로 치르는 부기(bookkeeping)입니다.

순서도를 데모 2의 확률표로 한 번 돌려 보기 (빔 폭 3)

코드와 순서도만으로는 손에 잘 안 잡힙니다. 그래서 §3 데모 2의 확률표를 그대로 넣고 6프레임을 끝까지 돌려 보겠습니다. 각 프레임마다 어떤 빔에 어떤 기호가 붙어 어떤 규칙을 타고 어디에 얼마를 더했는지를 한 줄도 빼지 않고 적었습니다. 규칙 칸의 A·B·C는 위 순서도의 세 상자와 같습니다.

여섯 프레임을 한 줄씩으로 줄이면

최종 1위는 "cat", 추정 확률 0.391608입니다. 데모 2의 전수 열거가 알려 준 참값은 0.424863(정렬 84개의 합)이니 빔 폭 3으로 그 92%를 주워 담은 셈입니다. 남은 8%는 잘려 나간 후보들이 들고 있던 몫이라 영영 못 찾지만, 순위를 맞히는 데는 지장이 없었습니다. 같은 표에서 greedy는 "ct"를 내놓았다는 것과 비교해 보세요.

아래에서 이 알고리즘을 실제로 한 프레임씩 돌려 볼 수 있습니다. 위 확률표를 그대로 씁니다.

§5 빔 크기 — 얼마나 넓게 볼 것인가

빔 폭은 "매 프레임 상위 몇 개를 살려 둘 것인가"입니다. 넓을수록 정확하고 느립니다. 장난감 예제에서 폭을 바꿔 가며 최종 결과를 보면 이렇습니다. 왜 하필 "빔"인가 ↓

폭 1은 "ct"로 망하고, 폭 2에서 이미 "cat"을 찾습니다. 그다음부터는 확률 추정치만 조금씩 정밀해질 뿐 답이 바뀌지 않죠. 이 포화 현상이 실전에서도 그대로 나타납니다. 논문은 6.2절에서 Mandarin에 대해 이렇게 씁니다.

"the performance of the beam search during decoding levels off at a smaller beam size. This allows us to use a beam size of 200 with a negligible degradation in CER."

그래서 최종 설정은 영어 500, 중국어 200입니다. 영어가 더 큰 이유는 알파벳이 작아 한 글자에 담긴 정보가 적고(4.9 bits/char vs 12.6), 초당 글자 수가 많아(14.1자 vs 3.3자) 애매한 갈림길이 훨씬 자주 생기기 때문입니다.

§6 언어 모델 붙이기 — Q(y)의 세 항

여기까지는 음향 정보만 썼습니다. 그런데 신경망은 "recognize speech"와 "wreck a nice beach"를 소리만으로는 구분하기 어렵습니다. 사람도 그렇죠. 구분하는 건 어느 쪽이 있을 법한 말인가라는 지식입니다.

언어 모델이란 무엇인가 — 소리를 안 보고 문장에만 점수를 매기는 표

언어 모델(LM)은 음성을 전혀 모릅니다. 글자·단어의 나열 하나를 받아 "이게 실제 텍스트에 나올 법한가"만 확률로 답합니다. 지금까지 다룬 음향 모델(CTC 신경망)과는 따로 학습해서, 디코딩할 때만 합칩니다. 그래서 §1의 확률표에는 LM이 관여한 적이 없습니다.

DS2가 쓰는 LM은 신경망이 아니라 n-gram입니다. 거대한 텍스트 뭉치에서 단어 나열의 빈도를 세어 만든 조회 표이고, 가정은 하나뿐입니다 — 다음 단어는 바로 앞 n−1개 단어에만 의존한다. 영어 모델이 5-gram이니 앞 4단어만 봅니다.

p_lm("wreck a nice beach")
  = p(wreck | <s>) · p(a | <s> wreck) · p(nice | <s> wreck a) · p(beach | <s> wreck a nice)

텍스트에서 센 결과 (예시 수치):
  "recognize speech"  흔함  →  p(speech | … recognize)  = 0.021
  "nice beach"        흔함  →  p(beach  | … a nice)     = 0.008
  "wreck a"           드묾  →  p(a      | … wreck)      = 0.0004   ← 여기서 벌어진다

소리가 거의 같아도 단어 나열을 세어 보면 차이가 납니다. 빔 서치는 빔을 확장할 때마다 이 표를 두드려서 그 차이를 점수에 반영합니다. 아래는 표 뒤에 숨은 용어들입니다.

DS2는 외부 n-gram 언어 모델을 붙이고, 빔 서치가 최대화하는 목적함수를 이렇게 바꿉니다 (식 12).

Q(y) = log p_ctc(y | x)  +  α · log p_lm(y)  +  β · word_count(y)
       └─ 음향: 소리와      └─ 언어: 말이       └─ 단어 삽입 보너스
          맞는가?              되는가?

β가 왜 필요한지가 특히 헷갈리는 지점입니다. log p_lm은 단어를 하나 더할 때마다 음수 값이 더해지므로, 언어 모델은 본질적으로 짧은 문장을 선호합니다. 이걸 그냥 두면 디코더가 단어를 슬금슬금 빠뜨립니다. β는 그 편향을 상쇄하는 평형추입니다 — 다만 너무 키우면 반대로 없는 단어를 만들어 냅니다. 직접 확인해 보세요.

언어 모델의 실제 규모 (3.8절)

§7 배포 — 40ms마다 100만 번 조회를 어떻게 줄였나

여기서 실전 문제가 터집니다. 빔 서치는 매 프레임, 모든 빔 × 모든 후보 글자에 대해 언어 모델을 조회해야 합니다. 그리고 n-gram 조회는 대부분 캐시에 없는 메모리 읽기입니다.

"The direct implementation of beam search means that each time-step dispatches one lookup per character for each beam. In Mandarin, this results in over 1M lookups per 40ms stride of speech data, which is too slow for deployment."

해법은 놀랍도록 단순합니다.

"Rather than considering all characters as viable additions to the beam, we only consider the fewest number of characters whose cumulative probability is at least p. In practice, we have found that p = 0.99 works well. Additionally, we limit ourselves to no more than 40 characters. This speeds up the Mandarin language model lookup time by a factor of 150x, and has a negligible effect on the CER (0.1-0.3% relative)."

즉 확률 낮은 글자는 아예 후보에서 뺍니다. ASR 출력 분포는 대개 매우 뾰족해서, 누적 확률 99%를 채우는 데 몇 글자면 충분합니다. 나머지 수천 글자를 조회하는 건 순수한 낭비죠.

λ 슬라이더를 왼쪽으로 밀어 보세요. 신경망이 확신에 찬 프레임에서는 후보 대여섯 개면 누적 99%가 채워지고, 가속은 150배를 훌쩍 넘습니다. 즉 150배는 상한 40자가 걸리는 최악의 경우이고, 평균적으로는 더 절약됩니다. 반대로 λ를 키우면 상한이 없을 때 후보가 수십~수백 개로 불어나는데, 논문이 p=0.99 외에 "최대 40자"라는 하드 리밋을 하나 더 둔 이유가 여기 있습니다 — 애매한 프레임에서 비용이 터지는 걸 막는 안전핀입니다.

§8 논문의 결과 — 언어 모델은 얼마나 도왔나

논문 Table 6은 같은 모델을 언어 모델 없이 / 있게 디코딩한 결과입니다 (영어는 WER, 중국어는 CER, 낮을수록 좋음).

논문의 해석은 이렇습니다 — 순환층이 깊어질수록 신경망이 내부에 더 강한 암묵적 언어 모델을 학습하므로, 외부 언어 모델이 보탤 게 줄어듭니다. 실제로 3.8절은 DS2가 외부 제약 없이도 철자를 꽤 잘 쓰고, 동음이의어를 문맥으로 구분해 내는 사례가 많다고 언급합니다.

그리고 영어가 중국어보다 언어 모델 이득이 큽니다. 영어 문자 모델은 철자를 지어내기 쉬운 반면("beach" vs "beech"), 중국어는 문자 하나하나가 이미 의미 단위라 음향만으로도 제약이 강하기 때문입니다.

§9 정리 — 한 문장으로

헷갈리기 쉬운 것들

§10 이해도 퀴즈

부록 · 왜 하필 "빔"인가

이 글에서 빔은 줄곧 "지금 살아남은 문장 후보 목록"이라는 뜻으로 썼습니다. 그런데 후보 목록을 왜 하필 빛줄기에 빗댔을까요. 이름의 출처는 이 글과 같은 동네 — 음성 인식입니다.

1976년, HARPY

카네기멜런의 Bruce Lowerre가 박사논문에서 HARPY 음성 인식 시스템을 만들며 붙인 이름입니다. DARPA 음성 이해 연구(SUR) 프로그램 과제였고, 상태가 1만 5천 개쯤 되는 네트워크를 매 시점 훑어야 하는데 전부 열어 볼 수는 없었습니다. 그래서 유망한 것만 남기고 나머지를 버리는 방식을 썼고, 거기에 beam search라는 이름이 붙었습니다.

원래 "빔"은 개수가 아니라 점수 창이었다

여기가 이름이 납득되는 지점입니다. Lowerre의 원래 빔은 "상위 몇 개"가 아니었습니다.

이번 시점 1등 점수에서 일정 폭 안에 드는 후보는 전부 남긴다.

그러면 매 시점 살아남은 후보들의 점수가 1등 주변으로 띠를 이루고, 그 띠가 시간축을 따라 훑고 지나갑니다. 손전등 빔이 어둠 속을 좁게 비추며 지나가는 모양이죠. "빔 폭(width)"이라는 말이 자연스러운 것도 그게 원래 진짜 폭 — 점수 창의 넓이였기 때문입니다. 개수를 세는 거였다면 폭이 아니라 개수라고 불렀을 겁니다.

그래서 §4의 top_k는 엄밀히는 빔이 아니다

beams = top_k(next, key=lambda s: s["pb"] + s["pnb"], k=beam_width)

이건 고정 폭(fixed-width) 변형입니다. 점수와 무관하게 무조건 상위 N개만 남기죠. 구현이 간단하고 메모리 상한이 보장돼서 지금은 이쪽이 사실상 표준이 됐고, §5의 500 / 200도 이 방식입니다.

다만 실전 ASR 디코더는 아직 둘 다 들고 있습니다. 예를 들어 Kaldi는 --beam(1등 대비 로그 확률 임계값 — 원래 의미)과 --max-active(활성 상태 개수 상한 — top_k)를 따로 받고, 보통은 두 개를 같이 겁니다. 어려운 구간에서는 임계값만으로 후보가 터지기 때문인데, §7에서 논문이 누적 확률 p = 0.99 말고 "최대 40자"라는 하드 리밋을 하나 더 둔 것과 정확히 같은 동기입니다.

↩ §5 빔 크기로 돌아가기