NLP 학습 노트 (1): 텍스트 처리와 통계적 방법 - Bojin Li

멜버른대학교에서 COMP90042 NLP 수업을 들으며 정리한 노트다. 이번 글에서는 텍스트 전처리, BPE, N-gram과 평활화, 텍스트 분류, POS, HMM, Viterbi를 다룬다.

1. 텍스트 전처리

1.1 기본 정의

용어	정의
Word: 단어	의미 또는 문법적 기능을 지닌 문자열(a sequence of characters with a meaning and/or function)
Sentence: 문장	단어를 문법 규칙에 따라 배열하여 하나의 완결된 의미를 표현하는 단위. 문장 부호나 구조적 경계에서 끝난다
Document: 문서	뉴스 기사나 이메일처럼 여러 문장으로 이루어진 연속된 텍스트 단위
Corpus: 말뭉치	학습이나 평가를 위해 일정 규모로 수집한 텍스트의 집합(단수형은 corpus, 복수형은 corpora)
Word token: 단어 토큰(개별 출현)	텍스트에서 단어가 출현할 때마다 하나씩 세는 단위. "to be or not to be"에는 토큰이 6개 있다
Word type: 단어 타입	중복을 제거한 서로 다른 단어. "to be or not to be"에는 타입이 4개 있다
Lexicon: 어휘집	한 언어나 분야에 속한 모든 단어 타입과 그 어휘 항목 정보의 집합

기억할 점: 토큰 수 ≥ 타입 수. 말뭉치의 규모는 흔히 $\vert V\vert$ (어휘 크기)와 전체 토큰 수로 나타낸다.

1.2 전처리가 필요한 이유

Language is compositional. 사람은 문서를 구성 요소로 나누어 이해할 수 있다. 컴퓨터가 언어를 이해하도록 하려면 비슷하게 분해하는 과정이 필요하다.

전처리는 원시 문자열을 작업에 적합한 표현으로 단계적으로 바꾼다. 다음은 전통적인 텍스트 처리 과정을 간략히 나타낸 것이다.

TEXT

"<p> Hi there. I'm TARS. </p>"
  → 서식 제거       "Hi there. I'm TARS."
  → 문장 분리       ["Hi there.", "I'm TARS."]
  → 단어 토큰화     [["Hi","there","."], ["I","'m","TARS","."]]
  → 정규화          [["hi","there","."], ["i","be","tars","."]]
  → 불용어 제거     [["hi","tars","."]]        (예시)

1.3 전처리의 다섯 단계

작업에 따라 필요한 단계를 선택한다. 모든 모델에서 전 단계를 수행하는 것은 아니다. 언어 모델은 보통 문장 부호, 단어 형태, 기능어를 유지해야 한다. 현대의 사전 학습 모델도 학습 때와 동일한 토크나이저를 사용해야 한다.

그림 1-1　텍스트 전처리의 다섯 단계와 각 단계를 거친 동일한 문장의 모습.

단계	영문 명칭	목적
1	Remove unwanted formatting	HTML/XML 태그, Markdown 기호, 불필요한 공백, 이스케이프 문자를 제거한다
2	Sentence segmentation: 문장 분리	문서를 문장으로 나눈다
3	Word tokenisation: 단어 토큰화	문장을 토큰으로 나눈다. BPE 같은 서브워드 방식도 포함한다
4	Word normalisation: 단어 정규화	대소문자, 철자, 단어 형태를 통일한다(표제어 추출 / 어간 추출)
5	Stopword removal: 불용어 제거	빈도는 높지만 정보량은 적은 기능어를 제거한다

2단계: 문장 분리(Sentence Segmentation)

간단한 것부터 네 가지 방법이 있다.

문장 부호로 분리: . ! ?에서 문장을 나눈다.
- 문제: 약어(Dr. Smith), 소수(3.14), URL(example.com)을 잘못 분리할 수 있다.
정규 표현식으로 분리: 패턴 매칭으로 흔한 예외를 처리한다. 예를 들어 (?<!\bDr)\.\s+ 패턴을 사용하거나, 마침표 뒤에 대문자가 와야 한다는 조건을 둔다.
사전 기반 방법: 약어와 예외 사전(Mr., Dr., U.S.A., e.g.)을 관리하고, 사전에 있는 항목은 분리하지 않는다.
기계 학습(시퀀스 레이블링):
- Method: 각 경계 후보(보통 문장 부호)에 대해 이진 분류로 '여기가 실제 문장 경계인가'를 판단한다. 전체를 시퀀스 레이블링 문제로 다룰 수도 있다.
- Model: 로지스틱 회귀 / 최대 엔트로피 / CRF / BiLSTM-CRF / 소형 Transformer 분류기.
- Features:
- - 현재 문장 부호 자체(. vs ? vs !)
  - 직전 토큰과 그 형태(약어 여부, 숫자 여부, 길이, 대문자 여부)
  - 직후 토큰이 대문자로 시작하는지, 흔한 문장 첫 단어인지
  - 문장 부호 바로 뒤에 닫는 따옴표나 괄호 등이 있는지
  - 문맥 윈도 내 토큰의 n-gram 특징과 약어 사전 포함 여부

3단계: 단어 토큰화(Word Tokenisation)

영어: 먼저 공백으로 나누고 문장 부호와 축약형·약어를 처리한다(Penn Treebank 규칙의 예: don't → do + n't, U.S. → U.S.는 하나의 토큰으로 유지한다). 어려운 질문은 what's a word?(New York는 한 단어인가, 두 단어인가?)
중국어: 단어 사이에 공백이 없으므로 단어 분할이 필요하다. MaxMatch(최대 일치법)를 참고한다.
서브워드(Subword): BPE 등이 있다. 2절 참고.

중국어 MaxMatch(최대 일치법)

아이디어: 사전이 주어지면 왼쪽(또는 오른쪽)에서 탐욕적으로 사전에 있는 가장 긴 일치 문자열을 단어로 선택한다.

예시:

TEXT

사전: {去买新, 西兰花, 西兰花新}
입력 문장: 去买新西兰花

정방향 최대 일치법(FMM, 왼쪽→오른쪽, 최장 일치 우선):
  위치 0: "去买新"을 시도(길이 3, 사전에 있음) → 「去买新」 선택
  위치 3: "西兰花"를 시도(길이 3, 사전에 있음) → 「西兰花」 선택
  결과: 去买新 / 西兰花

핵심과 한계:

FMM(정방향 최대 일치법)과 RMM(역방향 최대 일치법)의 결과는 다를 수 있다. 실제로는 둘 다 실행하고 규칙으로 중의성을 해소하는 경우가 많다.
탐욕 전략은 전역 최적해를 보장하지 않는다: 중의적인 문자열(예: 「新西兰/花」와 「新/西兰花」)을 잘못 나누기 쉽다.
사전에 없는 미등록어(OOV)는 처리하지 못하므로 규칙이나 통계 모델(HMM/CRF 단어 분할, jieba 등)과 함께 사용해야 한다.
장점: 구현이 매우 간단하고 빠르며 학습 데이터가 필요 없다.

4단계: 단어 정규화(Word Normalisation)

목적:

어휘 크기를 줄이고(USA / U.S.A. / usa → 같은 단어), 데이터 희소성을 완화한다.
서로 다른 단어 형태를 같은 의미 단위로 대응시켜, 제한된 데이터에서도 더 안정적인 통계량을 학습하게 한다.
대소문자, 전각·반각, 철자 변형을 통일해 매칭과 검색을 쉽게 한다.

방법:

대소문자 통일(case folding): The → the(고유 명사와 약어의 정보가 사라질 수 있음에 주의)
철자 정규화: colour → color, organise → organize
숫자·날짜 정규화: 2024-01-01, 3.14의 공통 표기는 <NUM>
단어 형태 환원: Lemmatisation 또는 Stemming(아래 참고)

Removing Morphology: 두 가지 형태 변화의 차이

유형	Inflectional Morphology(굴절)	Derivational Morphology(파생)
의미	같은 단어의 서로 다른 문법적 형태	기존 단어로 새 단어를 만든다
예시	명사의 복수형 +s, 동사의 3인칭 단수형 +s, 시제 +ed/+ing, 형용사의 비교급 +er, 최상급 +est	접미사로 품사를 바꾼다: person → personally, 접두사로 의미를 바꾼다: write → rewrite
품사나 의미가 바뀌는가	바뀌지 않는다	바뀐다

Lemmatisation과 Stemming 비교

비교 항목	Lemmatisation(표제어 추출)	Stemming(어간 추출)
처리 대상	굴절을 제거하고 lemma(사전의 표제어)로 되돌린다	접미사를 제거하고 어간을 남긴다
방식	Lexicon-based(사전과 품사에 의존)	Rule-based(보통 접사 제거 규칙의 집합)
출력	의미가 있는 실제 단어	의미 없는 어간일 수도 있다(studies → studi)
속도	비교적 느림(사전이나 품사 확인이 필요)	비교적 빠름
적합한 작업	실제 단어 형태가 필요하고 의미에 민감한 작업(생성이나 높은 가독성이 필요한 경우 등)	대규모 통계 처리, 검색, 분류(단어 형태만 일관되면 되는 경우)

Porter Stemmer

가장 널리 쓰이는 영어 어간 추출 알고리즘. Porter가 1980년에 제안했으며, 규칙과 조건(measure $m$ )에 따라 동작한다.
처리 순서: 먼저 굴절 접미사를 제거(inflectional: -s, -es, -ed, -ing), 그다음 파생 접미사를 제거(derivational: -ational, -fulness, -ness, -ment).
특징: 빠르고 사전이 필요 없다. 다만 어간을 지나치게 자르거나 덜 자를 수 있다(university → univers, generously → gener).

5단계: 불용어 제거(Stopword Removal)

정의: 말뭉치에 자주 나타나지만 주제 정보는 거의 담고 있지 않은 단어. 예를 들어 the, a, of, is, and, to.
목적:
- 특징 차원을 줄이고 계산·저장 비용을 낮춘다.
- 잡음을 제거하고 모델이 내용어에 집중하게 한다.
- 일반적으로 검색·주제 분류 같은 작업에 유용하다.
선정 방법:
1. 폐쇄 부류 단어·기능어: 한정사, 전치사, 접속사, 대명사, 조동사 등(closed-class words. 수가 제한적이고 새 단어가 거의 추가되지 않는다).
2. 고빈도 단어: 말뭉치의 빈도를 집계해 상위 $k$ 개를 선택한다(not, no 같은 부정어를 잘못 제거하지 않도록 사람이 검토해야 한다).
3. 기존 단어 목록: NLTK의 stopwords, spaCy의 불용어 목록(언어별로 불러올 수 있다).
주의: 감정 분석, 부정 표현 탐지, 구문 분석 등의 작업에는 불용어 목록을 그대로 적용하면 안 된다. 예를 들어 not good에서 not을 제거하면 의미가 달라진다. 제거 여부는 작업과 검증 결과에 따라 결정해야 한다.

2. BPE 서브워드 분할

2.1 동기

어휘 크기의 딜레마: 너무 크면 매개변수가 폭증하고 데이터가 희소해진다. 너무 작으면 미등록어(OOV)가 많아진다.
서브워드는 그 절충안이다. 자주 쓰이는 단어는 통째로 유지하고, 드문 단어는 더 작고 의미 있는 조각으로 나눈다.
- Colourless green ideas sleep furiously → [colour] [less] [green] [idea] [s] [sleep] [furious] [ly]

2.2 알고리즘(Byte-Pair Encoding)

학습(병합 규칙 학습)

모든 단어를 문자 시퀀스로 분해하고 단어 끝에 종료 기호 _(또는 </w>)를 붙여 단어 빈도를 집계한다.
모든 인접 기호 쌍(pair)의 출현 빈도를 집계한다.
가장 빈도가 높은 쌍을 병합해 새 기호로 만들고 어휘에 추가한다.
미리 정한 병합 횟수 $k$ (또는 어휘 크기)에 도달할 때까지 2~3단계를 반복한다.
출력: 학습 순서대로 정렬된 병합 규칙 목록과 최종 서브워드 어휘.

인코딩(새 텍스트 토큰화)

학습한 병합 순서대로 규칙을 적용한다. 어떤 규칙에도 해당하지 않는 부분은 한 글자씩 남는다. 따라서 인코딩은 결정적이며 빈도를 다시 집계할 필요가 없다.

2.3 전체 예시

말뭉치(단어 끝은 _로 표시):

Corpus	Frequency
o l d _	7
o l d e r _	3
f i n e s t _	9
l o w e s t _	4

초기 인접 쌍의 빈도

Pair	Count	설명
(e, s)	13	finest_ 9 + lowest_ 4
(s, t)	13	finest_ 9 + lowest_ 4
(t, _)	13	finest_ 9 + lowest_ 4
(o, l)	10	old_ 7 + older_ 3
(l, d)	10	old_ 7 + older_ 3
(f, i)	9	finest_ 9
(i, n)	9	finest_ 9
(n, e)	9	finest_ 9
(d, _)	7	old_ 7
(l, o)	4	lowest_ 4
(o, w)	4	lowest_ 4
(w, e)	4	lowest_ 4
(d, e)	3	older_ 3
(e, r)	3	older_ 3
(r, _)	3	older_ 3

병합 과정(빈도가 같으면 구현의 규약에 따라 하나를 고른다. 먼저 나타난 쌍이나 사전순으로 가장 앞선 쌍을 고르는 방법이 흔하다)

차례	병합	빈도	결과 말뭉치
1	e + s → es	13	o l d _(7) o l d e r _(3) f i n es t _(9) l o w es t _(4)
2	es + t → est	13	f i n est _(9) l o w est _(4)
3	est + _ → est_	13	f i n est_(9) l o w est_(4)
4	o + l → ol	10	ol d _(7) ol d e r _(3)
5	ol + d → old	10	old _(7) old e r _(3)
6	f + i → fi	9	fi n est_(9)
7	fi + n → fin	9	fin est_(9)
8	fin + est_ → finest_	9	finest_(9)
9	old + _ → old_	7	old_(7)

각 행에는 해당 병합으로 바뀐 단어만 표시했다. 나머지 단어는 그대로다.

최종 어휘(일부): o, l, d, e, r, f, i, n, s, t, w, _, es, est, est_, ol, old, fi, fin, finest_, old_, …

그림 2-1　BPE가 말뭉치에서 학습한 병합 연산(r · → r·, l o → lo, lo w → low, e r· → er·). 논문의 원래 예시를 사용했다. 출처: Sennrich et al., Neural Machine Translation of Rare Words with Subword Units, ACL 2016, Figure 1.

2.4 핵심과 확장

하이퍼파라미터: 병합 횟수 또는 목표 어휘 크기. 단어 단위와 문자 단위 사이의 절충을 결정한다.
장점: 어휘 크기를 조절할 수 있다. 고빈도 단어는 통째로 유지하고 저빈도 단어는 서브워드로 나누어 희소성을 완화한다. 필요한 문자가 모두 초기 문자 집합에 들어 있으면 계속 분할할 수 있다. 포함되지 않은 문자는 여전히 미지 기호가 될 수 있으며, byte-level BPE나 byte fallback으로 이를 추가로 처리할 수 있다.
단점: 의미가 아니라 빈도에 따라 분할하므로 경계가 부자연스러울 수 있다. 말뭉치나 분야가 달라지면 학습되는 분할도 달라진다.
자주 쓰이는 방식: BPE, WordPiece(BERT에서 사용) 및 Unigram(T5에서 사용). SentencePiece는 도구 모음이다. BPE, Unigram 등의 알고리즘을 지원하며, 먼저 공백으로 단어를 나누지 않고도 원시 텍스트를 직접 처리할 수 있다. 도구의 이름을 특정 알고리즘의 동의어로 취급하면 안 된다.

3. N-gram 언어 모델

3.1 작업

언어 모델(Language Model, LM)은 단어 시퀀스에 확률 $P(w_1, w_2, \dots, w_m)$ 을 부여한다.

문장 생성 방법: $P(w_t \mid w_{<t})$ 에서 순서대로 샘플링하거나 argmax를 취해 한 번에 한 단어씩 생성한다. 이 과정을 <eos>가 나올 때까지 반복한다.
어떤 문장이 더 나은지 판단하는 방법: 모델이 부여한 전체 문장의 확률, 로그 확률, 퍼플렉시티를 비교한다. 같은 모델과 같은 토큰화 규칙에서는 보통 확률이 높을수록 학습 데이터의 분포에 잘 맞는다는 뜻이다. 길이가 다른 문장을 비교할 때는 길이 정규화에도 주의해야 한다.

3.2 응용

맞춤법 교정 / 입력기 후보 순위 결정(I have a gu → guy? gun? gut?)
음성 인식(동음이의어 구별)
기계 번역(더 자연스러운 번역 선택)
텍스트 생성과 요약의 유창성 평가

3.3 N-gram이란

N-gram: 연속된 $n$ 개의 토큰으로 이루어진 조각.

$n$	명칭	예시(the dog barks)
1	unigram	the / dog / barks
2	bigram	the dog / dog barks
3	trigram	the dog barks

N-gram 언어 모델의 가정: $t$ 번째 단어는 바로 앞의 $n-1$ 개 단어에만 의존한다.

3.4 N-gram을 뒷받침하는 세 가지 개념과 가정

(a) 결합 확률에서 조건부 확률로(Chain Rule)

예를 들어 I like apple의 경우:

결합 확률: $P(\text{I like apple}) = P(\text{I}) \cdot P(\text{like} \mid \text{I}) \cdot P(\text{apple} \mid \text{I like})$
연쇄 법칙(모든 길이에 성립):

P(w_1, w_2, \dots, w_m) = \prod_{i=1}^{m} P(w_i \mid w_1, \dots, w_{i-1})

문제: 뒤쪽의 조건부 확률 항일수록 조건에 포함되는 문맥이 길어져 말뭉치에서 추정하기가 사실상 불가능해진다(데이터 희소성). 문장이 길어지면 매개변수 수도 기하급수적으로 늘어난다.
조건부 확률: $P(A\mid B) = \dfrac{P(A,B)}{P(B)}$ .

(b) 마르코프 가정(Markov Assumption)

전체 이력 대신 바로 앞의 $n-1$ 개 단어에만 의존한다고 가정한다.

P(w_1, \dots, w_m) \approx \prod_{i=1}^{m} P(w_i \mid w_{i-n+1}, \dots, w_{i-1})

$n$	모델	수식
1	unigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i)$
2	bigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-1})$
3	trigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-2}, w_{i-1})$

상대 빈도로 조건부 확률을 추정한다.

P(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}, \qquad P(w_i) = \frac{C(w_i)}{M}

여기서 $C(\cdot)$ 는 빈도이고, $M$ 은 전체 토큰 수다.

손으로 계산하는 예시

말뭉치(두 문장. 문장의 시작과 끝은 <s> <eos>로 표시):

TEXT

<s> yes no no no no yes <eos>
<s> no no no yes yes no <eos>

확률	계산	결과
$P(\text{yes} \mid \text{<s>})$	$1 / 2$	0.5
$P(\text{no} \mid \text{yes})$	$2 / 4$	0.5
$P(\text{no} \mid \text{no})$	$5 / 8$	0.625
$P(\text{yes} \mid \text{no})$	$2 / 8$	0.25
$P(\text{<eos>} \mid \text{yes})$	$1 / 4$	0.25
$P(\text{<eos>} \mid \text{no})$	$1 / 8$	0.125

말뭉치에서 yes는 4번, no는 8번 나타난다. 같은 선행 단어에 이어지는 후보에는 문장 종료 기호도 포함해야 한다. 예를 들어 no 다음에 오는 단어들의 확률은 $5/8+2/8+1/8=1$ .

3.5 N-gram의 세 가지 문제

문제	현상	대응
a) 언어에는 장거리 의존성이 있다	바로 앞의 $n-1$ 개 단어만 보므로 먼 문맥을 무시한다("The trophy would not fit in the suitcase because it was too big"에서 it의 지시 대상을 알아내려면 먼 문맥이 필요하다)	더 큰 $n$ (단, 데이터가 희소해짐), 캐시 모델, RNN/Transformer
b) 확률은 대개 매우 작다	수십 개의 $<1$ 인 수를 계속 곱하면 언더플로로 0이 된다	대신 로그 확률을 더한다: $\log P = \sum \log P(w_i\mid\cdot)$ . 퍼플렉시티를 계산할 때도 먼저 평균 음의 로그 확률을 구한다
c) 관측되지 않은 경우(확률 0)	학습 데이터에 없는 n-gram의 빈도는 0 → 전체 문장의 확률이 0이 된다	평활화(Smoothing), 4절 참고

4. 평활화(Smoothing)

목표: 관측되지 않은 n-gram에 0이 아닌 확률을 부여하면서도 전체 확률의 합을 1로 유지한다(확률 질량 보존).

4.1 Add-one(Laplace) 평활화

기본 아이디어: 모든 n-gram이 적어도 한 번은 관측되었다고 가정한다. 즉, 모든 빈도에 $+1$ 을 더한다.

P_{\text{add1}}(w_i) = \frac{C(w_i) + 1}{M + \vert V\vert } \qquad\text{(unigram)}

P_{\text{add1}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i) + 1}{C(w_{i-1}) + \vert V\vert } \qquad\text{(bigram)}

분모에 $\vert V\vert$ 를 더하는 이유는 확률의 합을 1로 유지하기 위해서다( $\vert V\vert$ 개 후보를 각각 한 번씩 더 센 것이므로).

문제: $+1$ 은 저빈도 단어나 희소한 말뭉치에 지나치게 큰 값이다. 미관측 사건에 확률 질량을 너무 많이 나누어 주어 관측된 n-gram의 확률을 크게 낮추므로 편향이 크다.

4.2 Add-k(Lidstone) 평활화

P_{\text{add-}k}(w_i \mid w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i) + k}{C(w_{i-2}, w_{i-1}) + k\,\vert V\vert }

$k$ 는 직접 선택해야 하는 하이퍼파라미터다. $0<k<1$ 이 보통 $k=1$ 보다 낫지만, 최적의 $k$ 는 실험을 통해 검증 데이터에서 정해야 한다.
단점:
1. 하이퍼파라미터 $k$ 를 직접 선택해야 한다. $k$ 값에 따라 평활화 효과가 크게 달라진다.
2. 같은 문맥에서 모든 미관측 n-gram에 동일한 확률을 부여한다. 빈도가 0인 것들 사이에 차이가 없어, 관측될 법하지만 아직 안 나온 경우와 거의 불가능한 경우를 구별하지 못한다.
3. 원래 빈도 사이의 비율을 바꾼다.

4.3 Absolute Discounting(절대 할인법)

아이디어: 관측된 각 단어의 빈도에서 일정한 값 $d$ (예: $d=0.1$ )를 가져와 미관측 단어에 그 확률 질량을 나누어 준다.

P_{\text{abs}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) - d}{C(w_{i-1})}, \quad \text{단, } C(w_{i-1},w_i) > 0

예시(context = alleged, 관측된 바이그램 5개, 미관측 바이그램 2개)

단어	counts	평활화 전 확률	Add-α(α=0.1)의 유효 빈도	Add-α 평활화 확률	Discounting(d=0.1)의 유효 빈도	Discounting 평활화 확률
impropriety	8	0.4	7.826	0.391	7.9	0.395
offense	5	0.25	4.928	0.246	4.9	0.245
damage	4	0.2	3.961	0.198	3.9	0.195
deficiencies	2	0.1	2.029	0.101	1.9	0.095
outbreak	1	0.05	1.063	0.053	0.9	0.045
infirmity	0	0	0.097	0.005	0.25	0.013
alleged	0	0	0.097	0.005	0.25	0.013
합계	20	1.0	20	1.0	20	1.0

할인 후 관측된 각 단어의 빈도는 $8-0.1=7.9$ , $5-0.1=4.9$ 등이 된다. 가져온 유효 빈도의 합은 $5\times0.1=0.5$ 이며, 이에 해당하는 확률 질량은 $0.5/20=0.025$ 이다.
가져온 $0.5$ 의 유효 빈도를 미관측 단어 2개에 똑같이 나누면: $0.5/2 = 0.25$ (유효 빈도). 정규화하면 $0.25/20=0.0125\approx0.013$ .

4.4 Katz Backoff(백오프)

아이디어: 관측된 경우에는 할인한 확률을 쓰고, 미관측인 경우에는 lower-order model(저차 모델)에 따라 남겨 둔 확률 질량을 재분배한다.

P_{\text{katz}}(w \mid h) = \begin{cases} \dfrac{C^*(h,w)}{C(h)}, & \text{if } C(h,w) > 0 \\[2mm] \alpha(h)\,P_{\text{lower}}(w), & \text{otherwise} \end{cases}

여기서 $h=w_{i-1}$ 는 문맥, $C^*(h,w)$ 는 할인한 빈도다. Katz는 보통 Good–Turing에 기반한 빈도 할인을 사용한다. 모든 관측 빈도에서 같은 상수를 일괄적으로 빼는 방법은 아니다. 백오프 가중치는 다음과 같다.

\alpha(h)=\frac{1-\sum_{w:C(h,w)>0}C^*(h,w)/C(h)}{\sum_{w:C(h,w)=0}P_{\text{lower}}(w)}

분자는 고차 모델에서 남겨 둔 확률 질량이고, 분모는 현재 문맥에서 관측되지 않은 단어들의 저차 확률을 합한 값이다. 이 둘로 최종 분포가 정규화된다.

Katz의 문제

백오프는 저차 모델의 원래 확률만 본다. 이 확률 자체로는 해당 단어가 새로운 문맥에 얼마나 잘 이어질 수 있는지 알 수 없다.
예시: I can not see without my reading ______
- 직관적인 답: glasses(reading glasses: 독서용 안경)
- 가령 reading glasses와 reading Kong이 모두 관측되지 않았고, 말뭉치에서는 King Kong이 매우 흔하다고 하자. 유니그램만 보면 $P(\text{Kong})$ 가 $P(\text{glasses})$ 보다 높을 수 있다. Kong이 거의 항상 King 뒤에만 나오더라도 잘못 선택될 수 있다.
- 근본 원인: 유니그램 확률이 높다고 해서 reading 뒤에 어울리는 것은 아니다. Kneser–Ney는 연속 확률(continuation probability)로 이 문제를 보완한다.

4.5 Kneser–Ney 평활화

아이디어: 할인한 확률 질량을 원래 빈도가 아니라 다양성(versatility), 즉 해당 단어가 몇 종류의 서로 다른 단어 뒤에 나타나는지에 따라 나누어 준다.

다양성은 낮지만 빈도는 높음: 예를 들어 Francisco가 San 뒤에만 나온다면 전체 빈도가 높아도 서로 다른 선행 문맥 수는 1이다. 관측되지 않은 문맥을 완성할 때 단어 빈도만 높다는 이유로 높은 확률을 주어서는 안 된다.
다양성이 높음: glasses는 reading, sun, wine, beer, eye… 뒤에 나올 수 있다 → 서로 다른 선행 문맥 수가 많아 백오프할 때 오히려 선택되기 쉽다. 이로써 Katz의 오류를 보완한다.

수식: 보간 형태

다음은 널리 쓰이는 보간형 Kneser–Ney다. 저차 분포는 고차 빈도가 0일 때만 사용되는 것이 아니라, 할인한 고차 확률에 더해진다.

P_{KN}(w_i \mid w_{i-1}) = \frac{\max(C(w_{i-1},w_i)-D,0)}{C(w_{i-1})} +\lambda(w_{i-1})\,P_{\text{cont}}(w_i)

P_{\text{cont}}(w_i)= \frac{\vert\{u:C(u,w_i)>0\}\vert}{\vert\{(u,v):C(u,v)>0\}\vert},\qquad \lambda(h)=\frac{D\,\vert\{v:C(h,v)>0\}\vert}{C(h)}

분자: 몇 종류의 서로 다른 선행 단어 뒤에 $w_i$ 가 나타났는가(즉, $w_i$ 의 '문맥 유형 수').
분모: 모든 단어의 문맥 유형 수를 합한 값(정규화).
$\lambda(h)$ : 문맥 $h$ 에서 할인한 전체 확률 질량이다. $0<D<1$ 이면 관측된 각 후속 단어가 $D/C(h)$ 씩 기여한다. 고차 분포와 저차 분포를 더한 뒤에도 확률의 합은 1이다.

4.6 Interpolation(보간)

아이디어: 둘 중 하나를 택해 백오프하는 대신, 차수가 다른 n-gram 모델을 가중 혼합한다. 가중치는 홀드아웃 데이터에서 학습해 정한다.

P_{IN}(w_i \mid w_{i-1}, w_{i-2}) = \lambda_3 P_3(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P_2(w_i \mid w_{i-1}) + \lambda_1 P_1(w_i)

\sum_k \lambda_k = 1, \qquad \lambda_k \ge 0

$\lambda$ 는 홀드아웃 데이터에서 학습한다(EM 또는 그리드 탐색). 임의로 정하는 값이 아니다.
장점: 고차 모델의 정밀함을 유지하면서 저차 모델로 보완하므로, 보통 순수 백오프보다 낫다.

4.7 평활화 방법 비교

방법	핵심 아이디어	장점	단점
Add-1	모든 빈도에 +1	가장 간단하며 0이 아닌 확률과 정규화를 보장	희소 데이터에 너무 많이 더해 관측된 확률을 크게 낮춤
Add-k	모든 빈도에 +k	add-1보다 완만함	조정이 필요한 $k$ . 미관측 단어의 확률이 모두 같으며 원래 비율을 바꿈
Absolute Discounting	관측된 단어의 빈도에서 일괄적으로 $d$ 를 빼고 나머지를 미관측 단어에 배분	간단하며 add-k보다 효과가 좋음	저차 문맥의 정보량을 구별하지 않음
Katz Backoff	관측되지 않으면 저차 모델로 백오프	고차 모델의 정밀함 유지	원래 확률로 백오프하므로 문맥의 다양성을 무시함(reading Kong 문제)
Kneser-Ney	할인한 확률 질량을 연속 확률에 따라 배분	고전적인 n-gram 모델의 강력한 베이스라인	수식이 비교적 복잡하고 두 종류의 빈도 집계가 필요함
Interpolation	차수가 다른 모델의 가중 혼합	안정적이며 보통 백오프보다 나음	홀드아웃 데이터에서 조정해야 하는 $\lambda$

5. 텍스트 분류

5.1 작업 정의

입력: 문서 $d$ (보통 특징 벡터 vector of features로 표현)와 고정된 범주 집합 $C=\{c_1, c_2, \dots, c_k\}$ (categorical, 연속값이나 순서가 있는 값이 아님).
출력: 예측한 범주 $\hat{c} \in C$ .

5.2 응용

Topic classification: 주제 분류(경제/정치/스포츠)
Sentiment analysis: 감정 분석
Native-language identification: 모어 식별(외국어로 쓴 글에서 작성자의 모어 배경을 판단하는 경우 등)
Natural language inference: 자연어 추론(함의/모순/중립)
Automatic fact-checking: 자동 사실 검증
Paraphrase: 바꿔 쓴 문장인지 판별

5.3 표준 절차

Identify a task of interest —— 작업 정의
Collect an appropriate corpus —— 데이터 수집
Carry out annotation —— 수작업 주석
Select features —— 특징 선택(단어 가방, n-gram, TF-IDF, 임베딩 등)
Choose a machine learning algorithm —— 모델 선택
Train model and tune hyper-parameters using held-out development data —— 개발 데이터로 하이퍼파라미터 조정
Repeat earlier steps as needed —— 필요한 단계 반복
Train final model —— 최종 모델 학습
Evaluate model on held-out test data —— 테스트 데이터로 평가

5.4 방법을 선택할 때 살펴볼 요소

요소	의미
편향(Bias)	모델의 제약이나 단순화 가정 때문에 발생하는 체계적인 오차. 가정이 실제 데이터와 맞지 않으면 편향이 커질 수 있다
분산(Variance)	모델이 학습 데이터에 민감한 정도. 민감할수록 데이터를 바꿨을 때 결과가 크게 흔들린다(과적합되기 쉬움)
내재된 가정	모델이 의존하는 조건(특징의 독립성, 선형 경계, 의미 있는 거리 등). 조건에서 벗어나면 성능에 영향을 줄 수 있다
복잡도	학습·추론의 시간과 공간 비용, 대규모 데이터로 확장할 수 있는지
속도	학습과 예측의 지연 시간이 서비스 요구를 충족하는지

편향–분산 절충: 높은 편향은 흔히 과소적합에, 높은 분산은 과적합에 대응한다. 제곱 손실에서는 기대 예측 오차를 편향², 분산, 줄일 수 없는 잡음으로 분해할 수 있다. 분류 작업에서도 이 관점으로 모델 사이의 절충을 이해할 수 있다.

5.5 주요 알고리즘 비교

(1) Naïve Bayes

기본 아이디어: 베이즈 법칙에 따라 사후 확률이 가장 높은 범주를 선택한다.

P(C\mid F) \propto P(F\mid C)\,P(C)

즉, '범주 사전 확률 × 해당 범주에서 이 특징들이 나타날 확률'이다.

나이브 가정: 특징들은 조건부로 독립이다:

P(F \mid C) = \prod_{f \in F} P(f \mid C)

Pro: 매우 빠르고 학습에 빈도만 필요하다. 소량 데이터나 고차원 희소 특징에 안정적이며, 다중 범주 분류를 자연스럽게 지원하고 점진적 갱신이 가능하다.
Con: 독립성 가정은 거의 성립하지 않는다(단어 사이에는 강한 상관관계가 있다). 확률값의 보정이 부정확해 0/1 같은 극단값을 내기 쉽다. 확률 0은 평활화로 처리해야 한다.

(2) Logistic Regression(로지스틱 회귀 / 최대 엔트로피)

이름에는 regression이 들어가지만 실제로는 분류기다.
선형 모델이며, softmax를 사용해 선형 점수를 유효한 확률로 변환한다.

P(y=c \mid x) = \frac{\exp(w_c^\top x + b_c)}{\sum_{c'} \exp(w_{c'}^\top x + b_{c'})}

학습 목표: 학습 데이터의 확률을 최대화한다(교차 엔트로피 최소화와 동치). 여기에 정규화를 더해 가중치가 작거나 희소하도록 유도한다.
Pro: 출력 확률을 해석할 수 있고 학습이 빠르다. L1/L2 정규화로 특징을 선택할 수 있으며, 선형 모델이므로 대규모 말뭉치로 확장하기 쉽다.
Con: 선형 결정 경계만 학습한다(비선형 관계를 표현하려면 특징 간 교차항을 직접 만들어야 한다). 특징 스케일에 민감하며 범주가 극도로 불균형하면 가중치를 조정해야 한다.

(3) Support Vector Machine (SVM)

정의: 학습 데이터를 분리하면서 마진(margin)이 최대인 초평면을 찾는다.

\min_{w,b}\ \tfrac{1}{2}\Vert w\Vert ^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1

Pro: 고차원 희소 텍스트에 강하다(텍스트 분류의 고전적인 강력한 베이스라인). 최대 마진으로 좋은 일반화 성능을 얻으며, 커널 함수로 비선형 관계를 처리할 수 있다.
Con: 기본적으로 이진 분류를 수행한다(다중 범주에는 one-vs-rest 등이 필요). 커널 SVM은 표본이 많으면 학습 비용이 높고 보정된 확률을 직접 출력하지 않는다. 선형 SVM에는 더 효율적인 최적화 방법을 쓸 수 있으므로 복잡도를 일괄적으로 말할 수는 없다.

(4) K-Nearest Neighbour (KNN)

정의: 특징 공간에서 가장 가까운 학습 표본 $k$ 개를 찾고, 이들의 다수 범주로 분류한다.
'가장 가까움'의 기준은 다양하다: 유클리드 거리, 코사인 거리(길이 대신 방향만 보므로 텍스트에서 자주 사용).
Pro: 학습이 필요 없고(lazy learning), 다중 범주 분류를 자연스럽게 지원한다. 결정 경계가 매우 비선형일 수 있으며 구현이 쉽다.
Con: 예측할 때 모든 거리를 계산해야 하므로 추론이 느리고 메모리를 많이 사용한다. 특징 스케일과 거리 척도에 매우 민감하다. 고차원에서는 거리의 유효성이 떨어지며(차원의 저주), 범주가 불균형하면 다수 범주가 유리하다.

(5) Decision Tree

정의: 트리를 구성한다. 내부 노드는 하나의 특징에 대한 검사이고 잎 노드는 최종 범주다. 정보 이득, Gini 불순도 등의 기준으로 분할을 탐욕적으로 선택한다.
Pro: 해석할 수 있고 규칙을 읽기 쉽다. 특징 스케일 조정이 필요 없으며, 비선형 관계와 특징 간 상호작용을 처리하고 학습이 빠르다.
Con: 과적합되기 매우 쉽다(가지치기나 깊이 제한 필요). 탐욕적 분할은 국소 최적일 뿐이며, 데이터 변동에 불안정하고 분산이 크다. 가능한 값이 많은 특징에 편향된다.

(6) Random Forest

정의: 앙상블 분류기로, 서로 다른 학습 부분집합(bootstrap)과 서로 다른 특징 부분집합으로 학습한 여러 결정 트리로 구성된다. 최종 결과는 다수결 투표로 정한다.
Pro: 분산을 크게 줄이고 과적합을 억제하며, 보통 잡음에 강하고 특징 중요도를 제공할 수 있다. 그래도 작업에 맞춰 트리 깊이와 잎 노드 크기 등을 조정해야 하며, 결측값 지원 여부는 구현에 따라 다르다.
Con: 해석 가능성이 떨어진다(읽기 쉬운 하나의 트리가 아니다). 모델이 크고 단일 트리보다 추론이 느리다. 고차원 희소 텍스트에서는 선형 모델만큼 효율적이지 않다.

(7) Neural Network

정의: 서로 연결된 노드들의 집합으로, 보통 입력층(특징), 출력층(범주 확률), 여러 은닉층으로 나뉜다. 각 노드는 이전 층의 입력을 선형 가중합으로 결합하고 활성화 함수를 거쳐 다음 층으로 전달한다.
Pro: 특징 표현을 자동으로 학습하고 표현력이 뛰어나다. 종단 간 학습이 가능하며, 대규모 데이터와 사전 학습으로 확장할 수 있다.
Con: 많은 데이터와 연산 자원이 필요하고, 하이퍼파라미터가 많으며 해석하기 어렵다. 과적합되기 쉬워 정규화나 dropout이 필요하고, 소량 데이터에서는 선형 모델보다 낫다고 보장할 수 없다.

5.6 하이퍼파라미터 조정과 평가

Hold-out(홀드아웃): 데이터를 train / dev(validation) / test로 나눈다. dev로 하이퍼파라미터를 선택하고 test는 최종 결과를 보고할 때 한 번만 사용한다.

혼동 행렬(이진 분류 예시)

	Classified As A	Classified As B
True A	79 (TP)	13 (FN)
True B	8 (FP)	10 (TN)

평가 지표 계산

Accuracy: 정확도

\text{Accuracy} = \frac{TP + TN}{N} = \frac{79+10}{110} = 0.809

Precision: 정밀도: 양성으로 예측한 것 중 실제 양성인 비율

P = \frac{TP}{TP + FP} = \frac{79}{79+8} = 0.908

Recall: 재현율: 실제 양성 중 찾아낸 비율

R = \frac{TP}{TP + FN} = \frac{79}{79+13} = 0.859

F1-Score: 정밀도와 재현율의 조화 평균

F_1 = \frac{2PR}{P+R} = \frac{2 \times 0.908 \times 0.859}{0.908 + 0.859} = 0.883

산술 평균 대신 조화 평균을 쓰는 이유는? 조화 평균은 작은 값의 영향을 크게 받는다. P와 R이 모두 높아야 F1도 높아지므로, 재현율만 높고 정밀도는 낮거나 그 반대인 경우에 높은 점수가 나오는 것을 막는다.

다중 범주 분류 지표

지표	방법	특징
Macro-average	각 범주의 P/R/F1을 구한 다음 범주별 산술 평균을 구한다	각 범주에 동일한 가중치를 준다. 소수 범주의 영향이 커져 롱테일 성능 저하를 드러낼 수 있다
Micro-average	모든 범주의 TP/FP/FN을 합산한 뒤 P/R/F1을 한 번 계산한다	각 표본에 같은 가중치를 주며 큰 범주가 지배한다. 단일 레이블 다중 범주 분류에서는 micro-F1 = accuracy

6. 품사 태깅(POS Tagging)

6.1 POS란

정의: 문장의 각 단어에 문법 범주(품사)를 부여하는 것.

예시: Janet/NNP will/MD back/VB the/DT bill/NN

여기서 back은 동사('지지하다')이며 명사나 부사가 아니다. 품사는 문맥에 따라 정해진다.

응용:

Constituency parsing(구성 성분 구문 분석)의 선행 단계: 품사를 알아야 구 구조를 만들 수 있다.
Information extraction(정보 추출)의 선행 단계: 개체와 관계를 식별할 때 품사에 의존한다(예: NN/NNP 구만 추출).
특징으로 사용: NER, 감정 분석, 번역 등 다른 작업에 언어학적 특징을 제공한다.
음성 합성(발음·강세 결정), 사전 편찬, 문장 교정.

6.2 품사 분류

개방 부류(Open class): 새 단어가 추가되거나 기존 단어가 사라질 수 있다

대분류	세부 분류
Nouns: 명사	Proper: 고유 명사(Melbourne) / Common: 보통 명사. 보통 명사는 Mass: 불가산 명사(water) / Count: 가산 명사(chair)로 나뉜다
Lexical verbs: 실질 동사	굴절 형태가 다양할 수 있다(sing/sang/sung). 용법에 따라 타동사와 자동사로 구분한다
Adjectives: 형용사	Gradable: 정도를 나타낼 수 있음(very tall) / Non-gradable: 정도를 나타낼 수 없음(dead)
Adverbs: 부사	Locative: 장소(here, there) / Degree: 정도(very, extremely)

폐쇄 부류(Closed class): 비교적 고정되어 쉽게 늘거나 줄지 않는다

Preposition: 전치사(of, in, on)
Particles: 소사(up, off. 예: give up)
Determiners: 한정사(the, a, this)
Pronouns: 대명사(he, they, who)
Conjunctions: 접속사(and, but, because)
Auxiliary / Modal Verbs: 조동사와 양태 동사(be, have, do, can, must, should. 구체적인 분류는 태그 체계에 따라 다름)

6.3 과제: 중의성(Ambiguity)

같은 단어 형태가 여러 품사에 대응할 수 있고, 그 분포도 매우 불균형하다.

back: 명사('등') / 동사('지지하다') / 부사('뒤로') / 형용사
flies: 복수 명사('파리들') / 3인칭 단수 동사('날다')
like: 전치사('~처럼') / 동사('좋아하다')

간단한 베이스라인은 각 단어에 학습 데이터에서 가장 흔한 품사를 부여하는 방법이다. 품사 분포의 불균형은 활용하지만 현재 문맥으로 중의성을 해소하지는 못한다. 정확도는 말뭉치와 미등록어 처리 방식에 따라 달라진다.

6.4 POS Tagsets: 품사 태그 집합

태그 집합	태그 수	특징
Brown	87	초기 말뭉치 태그 집합 중 하나로, 세밀하게 분류한다
Penn Treebank (PTB)	45	NLP에서 가장 널리 쓰이는 태그 집합. 예: NN, NNS, NNP, VB, VBD, VBG, JJ, RB, IN, DT, MD, CC, PRP…
CLAWS5 / BNC	61	CLAWS의 한 버전. 태그 수는 버전마다 다르다
초기 Universal Tagset	12	NOUN, VERB, ADJ, ADV, PRON, DET, ADP, NUM, CONJ, PRT, ., X. Universal Dependencies의 17개 UPOS 범주와 혼동하지 말 것

고전적인 중의성 예시(Penn Treebank 태그)

TEXT

Time  flies like an arrow
Time/NN  flies/VBZ  like/IN  an/DT  arrow/NN

Fruit flies like a banana
Fruit/NN  flies/NNS  like/VBP  a/DT  banana/NN

같은 flies라도 첫 문장에서는 동사('시간이 쏜살같이 지나간다'), 둘째 문장에서는 명사('초파리')다. 문맥으로만 판단할 수 있다.

7. 은닉 마르코프 모델(HMM)

7.1 HMM이 필요한 이유

작업: POS tagging. 전체 단어 시퀀스 $W = w_1 \dots w_n$ 에 대한 최적의 태그 시퀀스 $T = t_1 \dots t_n$ 를 찾는다.

기존 방법의 문제: 단어마다 독립적으로 예측하면 태그 사이의 의존성을 활용할 수 없다. 앞서 예측한 태그에 의존하는 탐욕적 분류기를 쓰면, 앞선 태그의 오류가 뒤의 예측에 영향을 주는 오류 전파(error propagation)가 발생할 수 있다.

새로운 아이디어: 문장 전체를 모델에 넣고 전체 태그 시퀀스를 출력하게 한다.

새로운 문제: 문장 길이는 일정하지 않으며 가능한 태그 조합의 수는 $\vert T\vert ^n$ , 지수적이어서 전부 열거할 수 없다.

해결 방법: 단어 단위로 모델링하되 학습과 예측에서는 문장 전체를 하나의 단위로 다룬다. 이를 sequence labelling, 또는 structured prediction이라고 한다.

HMM의 동작 방식: 문장(단어 시퀀스)이 주어지면 가능한 모든 태그 시퀀스 중에서 확률이 가장 높은 것을 찾는다.

장점:

규칙을 직접 설계할 필요가 없다(데이터 기반)
단어마다 탐욕적으로 고르는 대신 전역적으로 최적의 태그 시퀀스를 고려한다
주석된 말뭉치에서 매개변수를 학습할 수 있다(data-informed)

7.2 수식

\hat{T} = \arg\max_{T} P(T \mid W) = \arg\max_{T} \frac{P(W \mid T)\,P(T)}{P(W)} = \arg\max_{T} P(W \mid T)\,P(T)

( $P(W)$ 는 $T$ 와 무관하므로 생략할 수 있다. 이는 베이즈 법칙으로 분모를 제거한 것이다)

그림 7-1　HMM의 확률 그래프 모델. 실선은 상태 전이 $P(t_i\mid t_{i-1})$ (행렬 A), 점선은 방출 $P(w_i\mid t_i)$ (행렬 O)을 나타낸다.

7.3 두 가지 가정

가정	내용	역할
Output independence(출력 독립성)	위치 $i$ 의 단어는 위치 $i$ 의 태그에만 의존하고, 다른 단어나 태그에는 의존하지 않는다: $P(W\mid T)=\prod_i P(w_i\mid t_i)$	태그 시퀀스가 주어졌을 때 문장 전체의 확률을 단어별 확률의 곱으로 분해한다
Markov assumption(마르코프 가정)	현재 태그는 직전 태그에만 의존한다: $P(T)=\prod_i P(t_i \mid t_{i-1})$	태그 시퀀스의 확률을 1차 전이 확률의 곱으로 분해한다

따라서

\hat{T} = \arg\max_{T} \prod_{i=1}^{n} \underbrace{P(w_i \mid t_i)}_{\text{emission}} \cdot \underbrace{P(t_i \mid t_{i-1})}_{\text{transition}}

HMM이 생성(generative) 모델인 이유도 여기에 있다. 결합 확률 $P(W,T) = P(T)P(W\mid T)$ 를 모델링한다.

7.4 학습: 두 확률표 계산

매개변수	명칭	의미
$P(w_i \mid t_i)$	Emission(방출·관측) 확률 O	어떤 태그가 어떤 단어를 생성할 확률
$P(t_i \mid t_{i-1})$	Transition(전이) 확률 A	직전 태그 다음에 어떤 태그가 올 확률

계산 방법: 여기서도 최대우도추정(MLE), 즉 빈도를 이용한다.

P(w_i \mid t_i) = \frac{\text{Count}(w_i, t_i)}{\text{Count}(t_i)}, \qquad P(t_i \mid t_{i-1}) = \frac{\text{Count}(t_{i-1}, t_i)}{\text{Count}(t_{i-1})}

첫 번째 태그의 확률은 어떻게 구하는가? 각 문장 앞에 특별한 시작 기호 <s>를 붙이면 첫 항은 $P(t_1 \mid \text{<s>})$ :

P(t_1 \mid \text{<s>}) = \frac{\text{Count}(\text{<s>}, t_1)}{\text{Count}(\text{<s>})}

같은 방식으로 문장 끝에 </s>를 붙여 $P(\text{</s>} \mid t_n)$ 도 학습 가능한 전이로 만든다. 앞의 곱에서는 간결함을 위해 이 문장 종료 인자를 생략했지만, 전체 경로 확률에는 이 인자를 추가로 곱해야 한다.

미등록어는 어떻게 처리하는가? 여기서도 평활화(4절)를 사용한다. 방출 확률표에 add-k / add-one을 적용하거나, 저빈도 단어를 <UNK>로 묶어 <UNK>의 방출 확률을 모든 저빈도 단어가 공유하게 한다.

7.5 예측

학습된 HMM(두 개의 표: 전이 행렬 A와 방출 행렬 O)으로 입력 문장의 태그 시퀀스를 예측한다.

핵심 아이디어: 모든 태그 조합 중에서 결합 확률이 가장 높은 것을 선택한다.

\hat{t} = \arg\max_{t} P(W \mid t)\,P(t) = \arg\max_{t} \prod_{i=1}^{n} P(w_i \mid t_i)\,P(t_i \mid t_{i-1})

한 단어씩 예측하면 안 되는 이유는? (탐욕적 디코딩의 한계)

단어별로 argmax를 취하면 국소 최적해만 얻는다. 현재 단어에 최적인 태그가 다음 단어에 최적인 태그의 확률을 매우 낮게 만들 수 있다.
문장 전체의 최적화는 전역적인 문제이므로 앞뒤의 선택을 함께 고려해야 한다.
하지만 $\vert T\vert ^n$ 개를 전부 열거하는 것은 비현실적이다 → Viterbi 동적 계획법으로 전역 최적해를 구한다. 태그 집합의 크기가 고정되어 있으면 실행 시간은 문장 길이에 비례해 늘어난다.

7.6 생성 모델과 판별 모델

비교 항목	Generative(HMM)	Discriminative(판별 모델: CRF / 분류기)
모델링 대상	결합 확률 $P(X, Y)$	조건부 확률 $P(Y \mid X)$ (또는 $P(T\mid W)$ )
주요 용도	언어를 생성할 수 있다. HMM은 비지도 학습도 가능하다	분류, 예측, 시퀀스 레이블링
학습 방식	보통 지도·반지도 학습. EM을 통한 비지도 학습도 가능	보통 지도 학습
특징	관측 자체의 방출 확률을 사용하므로 특징에 제약이 있다	접두사·접미사, 단어 형태, 문맥 단어, 외부 사전 등 풍부한 특징을 사용할 수 있다
데이터 규모	단순한 구조 가정이 소량 데이터 학습에 유리할 수 있다	데이터와 특징이 충분하면 보통 예측 성능이 더 좋지만, 작업과 모델에 따라 다르다
대표 모델	Naïve Bayes, HMM. 신경망 언어 모델도 생성 방식으로 모델링할 수 있다	로지스틱 회귀, CRF, SVM, 분류용 신경망

판별 모델은 '입력이 주어졌을 때 출력을 예측하는 것'을 직접 최적화하며, 입력 분포 $P(W)$ 를 명시적으로 모델링할 필요가 없다. 예측 작업에 집중할 수 있지만 어느 쪽이 더 나은지는 작업, 데이터, 모델에 따라 달라진다.

8. Viterbi 알고리즘

8.1 핵심 아이디어

'현재 단어의 최적 태그'만 유지하지 말고, '각 후보 태그로 끝나는 최적 경로의 점수'를 유지하면서 다음 단어를 처리할 때 모든 조합을 고려한다.

즉, 각 위치 $t$ 와 각 태그 $j$ 에 대해 태그 $j$ 로 끝나는 최적 경로의 누적 점수 $\delta_t(j)$ 와 역추적 포인터 $\psi_t(j)$ 를 기록한다.

8.2 점화식

\delta_1(j) = P(t_1 = j \mid \text{<s>}) \cdot P(w_1 \mid j)

\delta_t(j) = \max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j \mid i)\Big]\cdot P(w_t \mid j)

\psi_t(j) = \arg\max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j\mid i)\Big]

종료 처리:

\hat{t}_n = \arg\max_{j}\big[\delta_n(j)\,P(\text{</s>}\mid j)\big], \qquad \hat{t}_{t} = \psi_{t+1}(\hat{t}_{t+1}) \ \text{(역추적)}

명시적인 문장 종료 상태가 없는 모델이라면 종료 시 $\delta_n(j)$ 를 바로 비교하면 된다. 아래 두 예시는 모두 이 단순화를 사용한다.

직관적인 예시: Can Play

단어 can에 대해 MD(양태 동사)와 NN(명사)의 점수를 각각 기록한다.
다음 단어 play를 처리할 때 각 후보 태그(VB, NN):
- 다음을 조합한다: 'can의 각 태그 점수 × 전이 확률 × 방출 확률'.
- 전체 확률이 가장 높은 경로를 찾는다.
마지막에 문장 끝의 각 태그가 가진 누적 점수를 비교하고, 최댓값에서 역추적하여 전체 경로를 복원한다.

8.3 예시 1: Janet will back the bill

전이 행렬(일부 발췌. 조건이 되는 사건은 행에 놓인다: $P(\cdot\mid \text{row})$ )

	NNP	MD	VB	JJ	NN	RB	DT
<s>	0.2767	0.0006	0.0031	0.0453	0.0449	0.0510	0.2026
NNP	0.3777	0.0110	0.0009	0.0084	0.0584	0.0090	0.0025
MD	0.0008	0.0002	0.7968	0.0005	0.0008	0.1698	0.0041
VB	0.0322	0.0005	0.0050	0.0837	0.0615	0.0514	0.2231
JJ	0.0366	0.0004	0.0001	0.0733	0.4509	0.0036	0.0036
NN	0.0096	0.0176	0.0014	0.0086	0.1216	0.0177	0.0068
RB	0.0068	0.0102	0.1011	0.1012	0.0120	0.0728	0.0479
DT	0.1147	0.0021	0.0002	0.2157	0.4744	0.0102	0.0017

(데이터 출처: Jurafsky와 Martin의 Speech and Language Processing 18장 Figure 18.12. WSJ 말뭉치에 기반하며 평활화하지 않았다. 태그 일부만 제시했으므로 각 행의 합은 1일 필요가 없다. 정규화되는 것은 전체 전이 분포다.)

방출 행렬(Emission Matrix, Speech and Language Processing, Figure 18.13)

	Janet	will	back	the	bill
NNP	0.000032	0	0	0.000048	0
MD	0	0.308431	0	0	0
VB	0	0.000028	0.000672	0	0.000028
JJ	0	0	0.000340	0	0
NN	0	0.000200	0.000223	0	0.002337
RB	0	0	0.010446	0	0
DT	0	0	0	0.506099	0

알고리즘 절차: $\vert T\vert \times n$ 크기의 격자(trellis)를 만들고 열마다 $\delta$ 를 채운다. 각 칸에 '이전 열의 어느 태그에서 왔는가'를 기록하고, 마지막 열의 최댓값에서 역추적한다.

8.4 예시 2: they fish(손으로 계산해 확인할 수 있음)

동적 계획법을 설명하기 위해 두 상태로 구성한 토이 모델이며 수치는 인위적으로 설정했다. N과 V는 상태 레이블일 뿐, 실제 영어에서 they가 동사라는 뜻은 아니다.

방출 확률

	they	fish
N	0.7	0.3
V	0.4	0.6

전이 확률

	N	V
<s>	0.6	0.4
N	0.8	0.2
V	0.7	0.3

그림 8-1　they fish의 Viterbi 격자. 각 칸에는 '그 태그로 끝나는 최적 접두 경로의 점수' $\delta$ 만 남긴다. 빨간색은 역추적한 최적 경로 they/N → fish/N을 나타낸다.

네 경로를 모두 열거

경로	계산	확률
N N	$0.6\times0.7 \times 0.8\times0.3$	0.1008 ✅ 최적
N V	$0.6\times0.7 \times 0.2\times0.6$	0.0504
V N	$0.4\times0.4 \times 0.7\times0.3$	0.0336
V V	$0.4\times0.4 \times 0.3\times0.6$	0.0288

결과: they/N fish/N. fish의 방출 확률만 비교하면 $P(\text{fish}\mid V)=0.6$ 이 $P(\text{fish}\mid N)=0.3$ 보다 크다. 하지만 전이 확률까지 고려하면 최적 경로는 N으로 끝난다. 방출 확률은 태그의 사후 확률이 아니므로 이것만으로 태그를 선택할 수는 없다. 이 예시는 전이 정보의 역할을 보여 주지만, 전이도 단계적으로 고려하는 탐욕적 디코딩이 반드시 실패함을 보여 주는 반례는 아니다.

8.5 알고리즘의 특성

특성	설명
시간 복잡도	$O(T^2 N)$ : $T$ = 태그 집합 크기, $N$ = 시퀀스 길이. 위치가 모두 $N$ 개이고, 각 위치의 $T$ 개 태그마다 이전 위치의 모든 $T$ 개 태그와 비교한다
공간 복잡도	최적 점수만 필요하면 두 열을 번갈아 유지할 수 있어 공간은 $O(T)$ 이다. 전체 경로를 복원하려면 $O(TN)$ 개의 역추적 포인터를 저장해야 한다
정확하게 풀리는 이유	최적 부분 구조: 위치 $t$ 의 태그 $j$ 로 가는 최적 경로의 접두 부분은 위치 $t-1$ 의 어떤 태그로 가는 최적 경로여야 한다(그렇지 않으면 접두 부분을 바꿔 더 나은 경로를 만들 수 있다). 마르코프 성질: 현재 태그가 주어지면 미래는 그 이전의 이력과 무관하다. 따라서 각 칸에서 최적 접두 경로의 점수만 유지하고 열등한 경로는 버릴 수 있다
수치 언더플로	확률을 계속 곱하면 빠르게 0이 된다. 실제 구현에서는 모두 로그 확률을 사용한다(곱셈은 덧셈으로 바뀌지만 $O(T^2N)$ 은 그대로)
고차 변형	예를 들어 태그 트라이그램(2차 HMM): $P(t_i \mid t_{i-2}, t_{i-1})$ 과 interpolation 평활화를 사용한다. 복잡도는 $O(T^3 N)$