Branching Entropy
06 May 2017 | tokenize
이번 글에서는 말뭉치에서 단어를 추출하는 기법 가운데 하나인 Branching Entropy(이하 BE)에 대해 살펴보도록 하겠습니다. BE는 Jin&Tanaka(2006)이 제안한 모델인데요, 이 글은 김현중 서울대 박사과정이 진행한 2017 패스트캠퍼스 강의와 코드를 참고하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
기법 개요
Jin&Tanaka(2006)의 아이디어는 생각보다 간단합니다. 단어 내부에서는 불확실성(uncertainty), 엔트로피(entropy)가 줄어들고, 경계에서는 증가하는 현상을 모델링한 것입니다. 아래 그림을 먼저 볼까요?
알파벳 ‘n’ 한 글자만 주어졌을 땐 이 정보만으로는 어떤 단어가 등장할지 정확히 알기 어렵습니다(불확실성이 높은 상태). 하지만 글자가 ‘natur’까지 등장했다면 ‘nature’이거나 ‘natural’ 두 가지 경우의 수뿐입니다(불확실성이 낮은 상태). 그럼 ‘nature’ 다음에 나오는 글자는 무엇일까요? 다시 예측하기 어려워집니다. 이는 ‘natural’도 마찬가지입니다.
이미 주어진 글자정보를 활용해 다음 글자의 불확실성을 계산해보면 아래와 같은 그래프를 그릴 수 있습니다. 단어 내부에선 불확실성이 줄어들다가 단어 경계에서 불확실성이 다시 증가하기 때문입니다. Jin&Tanaka(2006)는 이런 점에 착안해 그 경계의 불확실성이 높은 글자들의 나열을 ‘단어’로 보자고 제안했습니다. 이때 쓰이는 불확실성 관련 지표가 바로 BE입니다.
BE는 아래와 같이 정의됩니다.
\[H(X|{ X }_{ n })=-\sum _{ x\in X }^{ }{ P(x|{ x }_{ n })\times \log { (P(x|{ x }_{ n })) } }\]
분석 예시
영화 리뷰 사이트 ‘왓챠’에서 655만306개의 리뷰를 수집했습니다. 우선 이를 글자 단위로 세었습니다. 전체 결과 가운데 세 글자로 이뤄진 문자열 ‘아직까’를 포함하는 모든 단어들의 빈도는 아래 표와 같습니다. 우리는 아래 표로부터 ‘아직까’의 출현빈도는 5349라는 사실 또한 알 수 있습니다.
구분
빈도수
아직까지
4714
아직까진
632
아직까니
3
총합
5349
그렇다면 ‘아직까’의 엔트로피는 어떻게 구할까요? 아래와 같습니다.
\(\begin{align*}
H(X|아직까)=&-P(아직까지|아직까)\times \log { (P(아직까지|아직까)) } \\&-P(아직까진|아직까)\times \log { (P(아직까진|아직까)) } \\&-P(아직까니|아직까)\times \log { (P(아직까니|아직까)) }\\\\=&-\frac { 4714 }{ 5349 } \times\log { \frac { 4714 }{ 5349 } } -\frac { 632 }{ 5349 } \times\log { \frac { 632 }{ 5349 } } -\frac { 3 }{ 5349 } \times\log { \frac { 3 }{ 5349 } } \\\\ =&0.3679
\end{align*}\)
위와 동일한 방식으로 ‘아직’, ‘아직까지’, ‘아직까지도’의 BE를 구해 비교하면 아래 표와 같습니다.
구분
아직
아직까
아직까지
아직까지도
BE
2.95
0.37
3.46
4.69
위 표를 해석하면 이렇습니다. 우리가 온전한 단어로 쓰는 ‘아직’, ‘아직까지’, ‘아직까지도’는 그 경계에 다양한 글자들이 올 수 있으므로 BE가 비교적 높습니다. 하지만 ‘아직까’라는 문자열은 ‘아직까지’, ‘아직까지도’라는 단어의 내부에 있으므로 BE가 낮습니다. 바꿔 말해 BE가 높은 문자열을 단어 취급해도 크게 나쁘지 않은 결과를 낼 수 있다는 것입니다.
BE와 계열관계
형태소란 의미를 지니는 최소 단위인데요, 형태소를 분석하는 기준으로는 계열관계(系列關係paradigmatic relation)가 있습니다. 계열관계는 그 자리에 다른 형태소가 ‘대치’될 수 있는가를 따지는 것입니다. 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
어쨌든 BE는 사실상 형태소(morpheme) 추출 기법입니다. 말뭉치에서 어떤 문자열이 자주 쓰이는지 빈도를 세어 문자열마다 형태소가 될 만한 지표를 반환(엔트로피가 높을 수록 형태소일 확률이 큼)해 주는데요. 이는 BE가 형태소의 중요 분석기준인 계열관계와 밀접한 관련을 맺고 있기 때문입니다. 아래 그림을 볼까요?
위 예시에서 ‘엔진’이라는 명사 뒤에는 조사 ‘-이’, ‘-에서’, ‘-을’ 등이 올 수 있습니다. 여기에서 ‘-이’, ‘-에서’, ‘-을’은 대치해서 쓸 수 있기 때문에 계열관계를 이룬다고 말할 수 있습니다. 그런데 이 경우 ‘엔진’의 BE는 매우 높을 겁니다. ‘엔진’ 뒤에 다양한 문자열이 등장할 수 있어 불확실성이 크기 때문입니다.
지금까지는 왼쪽에서 오른쪽으로 빈도수를 세는 걸 기준으로 설명을 해드렸지만, 오른쪽에서 왼쪽으로 빈도를 세어 BE를 계산하는 경우에도 마찬가지입니다. 아래 그림에서 ‘엔진’은 ‘Bracket’, ‘Head’와 계열관계를 맺고 있습니다. 아울러 ‘-에서’의 BE 또한 높습니다.
말뭉치 분석 결과
왓챠 리뷰 655만306개 리뷰를 학습해 BE 상위 500개 문자열을 나열한 결과는 아래와 같습니다. (left-side BE * right-side BE 결과를 내림차순 정렬)
코드
김현중 박사과정이 작성한 BE 코드를 사용했습니다. 저 역시 정리 용도로 남긴 것이니 문제되면 바로 삭제하겠습니다. 최신 코드는 김현중 박사과정의 깃헙 https://github.com/lovit/soy을 참고하시기 바랍니다.
사용법은 아래와 같습니다. 아래 코드에서 MaxScoreTokenizer 역시 김현중 박사과정이 만든 코드로 말뭉치에서 학습한 BE를 바탕으로 문장을 토큰으로 나눠주는 함수입니다.
import branching_entropy as tool
branching = tool.BranchingEntropy()
branching.train(reviews)
branchingtokenizer = tool.MaxScoreTokenizer(scores=branching.get_all_branching_entropies())
branching_tokenized_reviews = [branchingtokenizer.tokenize(review) for review in reviews]
이번 글에서는 말뭉치에서 단어를 추출하는 기법 가운데 하나인 Branching Entropy(이하 BE)에 대해 살펴보도록 하겠습니다. BE는 Jin&Tanaka(2006)이 제안한 모델인데요, 이 글은 김현중 서울대 박사과정이 진행한 2017 패스트캠퍼스 강의와 코드를 참고하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
기법 개요
Jin&Tanaka(2006)의 아이디어는 생각보다 간단합니다. 단어 내부에서는 불확실성(uncertainty), 엔트로피(entropy)가 줄어들고, 경계에서는 증가하는 현상을 모델링한 것입니다. 아래 그림을 먼저 볼까요?
알파벳 ‘n’ 한 글자만 주어졌을 땐 이 정보만으로는 어떤 단어가 등장할지 정확히 알기 어렵습니다(불확실성이 높은 상태). 하지만 글자가 ‘natur’까지 등장했다면 ‘nature’이거나 ‘natural’ 두 가지 경우의 수뿐입니다(불확실성이 낮은 상태). 그럼 ‘nature’ 다음에 나오는 글자는 무엇일까요? 다시 예측하기 어려워집니다. 이는 ‘natural’도 마찬가지입니다.
이미 주어진 글자정보를 활용해 다음 글자의 불확실성을 계산해보면 아래와 같은 그래프를 그릴 수 있습니다. 단어 내부에선 불확실성이 줄어들다가 단어 경계에서 불확실성이 다시 증가하기 때문입니다. Jin&Tanaka(2006)는 이런 점에 착안해 그 경계의 불확실성이 높은 글자들의 나열을 ‘단어’로 보자고 제안했습니다. 이때 쓰이는 불확실성 관련 지표가 바로 BE입니다.
BE는 아래와 같이 정의됩니다.
\[H(X|{ X }_{ n })=-\sum _{ x\in X }^{ }{ P(x|{ x }_{ n })\times \log { (P(x|{ x }_{ n })) } }\]분석 예시
영화 리뷰 사이트 ‘왓챠’에서 655만306개의 리뷰를 수집했습니다. 우선 이를 글자 단위로 세었습니다. 전체 결과 가운데 세 글자로 이뤄진 문자열 ‘아직까’를 포함하는 모든 단어들의 빈도는 아래 표와 같습니다. 우리는 아래 표로부터 ‘아직까’의 출현빈도는 5349라는 사실 또한 알 수 있습니다.
구분 | 빈도수 |
---|---|
아직까지 | 4714 |
아직까진 | 632 |
아직까니 | 3 |
총합 | 5349 |
그렇다면 ‘아직까’의 엔트로피는 어떻게 구할까요? 아래와 같습니다.
\(\begin{align*}
H(X|아직까)=&-P(아직까지|아직까)\times \log { (P(아직까지|아직까)) } \\&-P(아직까진|아직까)\times \log { (P(아직까진|아직까)) } \\&-P(아직까니|아직까)\times \log { (P(아직까니|아직까)) }\\\\=&-\frac { 4714 }{ 5349 } \times\log { \frac { 4714 }{ 5349 } } -\frac { 632 }{ 5349 } \times\log { \frac { 632 }{ 5349 } } -\frac { 3 }{ 5349 } \times\log { \frac { 3 }{ 5349 } } \\\\ =&0.3679
\end{align*}\)
위와 동일한 방식으로 ‘아직’, ‘아직까지’, ‘아직까지도’의 BE를 구해 비교하면 아래 표와 같습니다.
구분 | 아직 | 아직까 | 아직까지 | 아직까지도 |
---|---|---|---|---|
BE | 2.95 | 0.37 | 3.46 | 4.69 |
위 표를 해석하면 이렇습니다. 우리가 온전한 단어로 쓰는 ‘아직’, ‘아직까지’, ‘아직까지도’는 그 경계에 다양한 글자들이 올 수 있으므로 BE가 비교적 높습니다. 하지만 ‘아직까’라는 문자열은 ‘아직까지’, ‘아직까지도’라는 단어의 내부에 있으므로 BE가 낮습니다. 바꿔 말해 BE가 높은 문자열을 단어 취급해도 크게 나쁘지 않은 결과를 낼 수 있다는 것입니다.
BE와 계열관계
형태소란 의미를 지니는 최소 단위인데요, 형태소를 분석하는 기준으로는 계열관계(系列關係paradigmatic relation)가 있습니다. 계열관계는 그 자리에 다른 형태소가 ‘대치’될 수 있는가를 따지는 것입니다. 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
어쨌든 BE는 사실상 형태소(morpheme) 추출 기법입니다. 말뭉치에서 어떤 문자열이 자주 쓰이는지 빈도를 세어 문자열마다 형태소가 될 만한 지표를 반환(엔트로피가 높을 수록 형태소일 확률이 큼)해 주는데요. 이는 BE가 형태소의 중요 분석기준인 계열관계와 밀접한 관련을 맺고 있기 때문입니다. 아래 그림을 볼까요?
위 예시에서 ‘엔진’이라는 명사 뒤에는 조사 ‘-이’, ‘-에서’, ‘-을’ 등이 올 수 있습니다. 여기에서 ‘-이’, ‘-에서’, ‘-을’은 대치해서 쓸 수 있기 때문에 계열관계를 이룬다고 말할 수 있습니다. 그런데 이 경우 ‘엔진’의 BE는 매우 높을 겁니다. ‘엔진’ 뒤에 다양한 문자열이 등장할 수 있어 불확실성이 크기 때문입니다.
지금까지는 왼쪽에서 오른쪽으로 빈도수를 세는 걸 기준으로 설명을 해드렸지만, 오른쪽에서 왼쪽으로 빈도를 세어 BE를 계산하는 경우에도 마찬가지입니다. 아래 그림에서 ‘엔진’은 ‘Bracket’, ‘Head’와 계열관계를 맺고 있습니다. 아울러 ‘-에서’의 BE 또한 높습니다.
말뭉치 분석 결과
왓챠 리뷰 655만306개 리뷰를 학습해 BE 상위 500개 문자열을 나열한 결과는 아래와 같습니다. (left-side BE * right-side BE 결과를 내림차순 정렬)
코드
김현중 박사과정이 작성한 BE 코드를 사용했습니다. 저 역시 정리 용도로 남긴 것이니 문제되면 바로 삭제하겠습니다. 최신 코드는 김현중 박사과정의 깃헙 https://github.com/lovit/soy을 참고하시기 바랍니다.
사용법은 아래와 같습니다. 아래 코드에서 MaxScoreTokenizer 역시 김현중 박사과정이 만든 코드로 말뭉치에서 학습한 BE를 바탕으로 문장을 토큰으로 나눠주는 함수입니다.
import branching_entropy as tool
branching = tool.BranchingEntropy()
branching.train(reviews)
branchingtokenizer = tool.MaxScoreTokenizer(scores=branching.get_all_branching_entropies())
branching_tokenized_reviews = [branchingtokenizer.tokenize(review) for review in reviews]
Comments