<div id="readability-page-1" class="page"><div>MECAB 논문 정리

Mecab 논문인 "<a href="https://aclanthology.org/W04-3230.pdf" target="_blank" rel="noopener">Applying Conditional Random Fields to Japanese Morphological Analysis</a>"를 읽고 정리해봤다. (아직 정리 중이라는 표현이 적절할 듯. 아직 정리 중이다)

본 포스팅은 다음의 4가지를 다룬다.

1. 일본어 형태소 분석기 모델들
2. CRF 이전 모델들의 문제점
3. CRF(conditional random fields)
4. Experiments of CRFs
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style6">
<h2 data-ke-size="size26">💡 일본어 형태소 분석기 모델들</h2>

**일본어 형태소 분석
<figure data-origin-width="861" data-origin-height="345" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/zvybx/btrax63BFjH/0xtNECuO9ODPqkpztpfXkK/img.png" data-origin-width="861" data-origin-height="345" data-ke-mobilestyle="widthOrigin"><figcaption>일본어 형태소 분석</figcaption></figure>
**모델들 (6가지)
1) Chasen: hierarchical structure 사용, IPA tagset 사용
**IPA tagset은 세 가지 부분으로 구성됨. POS, conjugation form(cform), conjugate type(ctype)&nbsp;
cform이랑 ctype은 단어랑 conjugate에만 지정되고, POS는 4레벨의 subcategory가 있음.&nbsp;
e.g. 명사-일반명사
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-고유명사
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-사람
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-조직
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-장소

2) rule-based analyzer (JUMAN): hierarchical structure 사용

3) HMMs (Hidden Markov Models)
<figure data-origin-width="988" data-origin-height="401" width="594" height="241" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/sagZH/btrasuc7fkY/232nY8wLVcJcYnTUu2bSkk/img.png" data-origin-width="988" data-origin-height="401" width="594" height="241" data-ke-mobilestyle="widthOrigin"><figcaption>HMM</figcaption></figure>
-hidden state에 영향을 미치는 것은 바로 이전의 hidden state뿐
-hidden state 찾는 법: conditional probability 이용
<figure data-origin-width="568" data-origin-height="39" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/c3O5Ii/btrasuc76dg/14gW3xucKGkPVDX2EtvcD1/img.png" data-origin-width="568" data-origin-height="39" data-ke-mobilestyle="widthOrigin"></figure>
-단점: Markov 가정에 의해서 이전 hidden state에 의존적이므로 Label Bias의 가능성이 높음

4) MEMMs (Maximum Entropy Markov Models)
<figure data-origin-width="985" data-origin-height="393" width="592" height="237" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/cCbslV/btrasuxpHCV/7PLkti3nb2NN9nmvSYOvSK/img.png" data-origin-width="985" data-origin-height="393" width="592" height="237" data-ke-mobilestyle="widthOrigin"></figure>
-hidden state에 영향을 미치는 것은 바로 이전 hidden state와 observation
-hidden state 찾는 법: conditional probability 이용
<figure data-origin-width="273" data-origin-height="39" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/XhsmF/btrastywxCx/MX89gDGeGqFvKNWG86ZQ2K/img.png" data-origin-width="273" data-origin-height="39" data-ke-mobilestyle="widthOrigin"></figure>
-단점: Markov 가정에 의해서 이전 hidden state에 의존적이므로 Label Bias의 가능성이 높음

5) E-HMMs (extended Hidden Markov Models)


6) CRFs (Conditional Random Fields)
<figure data-origin-width="987" data-origin-height="399" width="583" height="236" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/9F5IR/btrasuKXHOJ/rtC1iokEoj0aF1n1Ogt4l1/img.png" data-origin-width="987" data-origin-height="399" width="583" height="236" data-ke-mobilestyle="widthOrigin"></figure>
-hidden state에 영향을 미치는 것은 모든 hidden state와 observation
-hidden state 찾는 법: 모든 종류의 hidden state에 대해서 가장 높은 확률을 고름
<figure data-origin-width="209" data-origin-height="33" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/bnreKJ/btrasUWKqQf/2aaM6KvKBGln2aG5Ksqd60/img.png" data-origin-width="209" data-origin-height="33" data-ke-mobilestyle="widthOrigin"></figure>


<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style6">
<h2 data-ke-size="size26">💡 CRF 이전 모델들의 문제점</h2>
1) word boundary ambiguity
-character based Begin/Inside tagging: character를 token으로 취급해서 Begin/Inside를 tagging하도록 만드는 것
-&gt; 단점 2가지
① word segmentation에 대해 미리 정보가 있는 lexicon을 활용하기 힘듬
② redundant candidates가 많이 생겨 decoding 속도가 많이 느려짐

2) long-standing problems
① Hierarchical Tagset
-ChaSen, Juman은 hierarchical structure 사용
-hierarchical strcutre에서 1) suffix나 character같은 atomic feature를 잘 사용하면서도 2) 각 레벨을 incorporate하는 게 중요함

**왜 각 level을 잘 incorporate하는 게 중요하지?
-bottom lebel만을 이용하면 data sparseness problem 발생
-top level만을 이용하면, 세밀한 차이를 잡아내기 위한 granularity of POS가 부족함!!
(예1) 어떤 suffix들은 이름 뒤에 나옴 -&gt; Name POS 사용하는 게 좋음
(예2) conjugation form (cform)도 반드시 구별되어야 하는데, 특정 단어 뒤에 나타나기 때문에!! (?)

-&gt; extended HMMs의 경우 이러한 incorporate를 잘하기 위해 3가지 방식 이용
1) position-wise grouping 2) word-level statistics 3) smoothing of word and POS level statistics
-&gt; 그러나 여전히 1) non-independent feature를 구별해내지 못한다는 점, 2) smoothing parameter를 ad-hoc 방식으로 선택한다는 한계 존재


② Label Bias and Length Bias
-next state classifier를 활용하는 dicrimitinative model 대부분은 label bias나 length bias가 존재
-HMM이나 MEMM은 label bias 존재

<figure data-origin-width="512" data-origin-height="254" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/TbRJB/btraoDhPxxP/D3KhtrL4dkegg6VfTsktyK/img.png" data-origin-width="512" data-origin-height="254" data-ke-mobilestyle="widthOrigin"><figcaption>label bias</figcaption></figure><figure data-origin-width="520" data-origin-height="256" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/NfEDW/btrawBJm4t6/0atWJJQrBkCb6Kxh68hjmk/img.png" data-origin-width="520" data-origin-height="256" data-ke-mobilestyle="widthOrigin"><figcaption>length bias</figcaption></figure>


=&gt; 이 2가지 문제를 해결하기 위해 CRF 나옴!!
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style6">
<h2 data-ke-size="size26">💡 CRF(conditional random fields)</h2>
1) a number of correlated features for hierarchical tagsets can be incorporated which was not possible in HMMs
2) influences of label and length bias are minimized which caused errors in MEMMs

CRF식
<figure data-origin-width="385" data-origin-height="57" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/47OQ4/btraqSSQjNM/tZY67kRzNKX8HztFXu8slK/img.png" data-origin-width="385" data-origin-height="57" data-ke-mobilestyle="widthOrigin"><figcaption>, where</figcaption></figure><figure data-origin-width="376" data-origin-height="82" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/dR06sT/btrat2glGcj/3GJ0dflXoswq8j6HyPcOmk/img.png" data-origin-width="376" data-origin-height="82" data-ke-mobilestyle="widthOrigin"></figure>
-fk((wi−1,ti−1),(wi,ti)): i, i−1번째의 토큰의 feature fuction
-λk: learned weight

cf. 기존 CRF식과 Mecab에서 이용하는 CRF식이 뭐가 다른지?
: Mecab꺼는 word boundary ambiguity를 해결하기 위한 것으로 output sequence의 길이가 고정되어 있지 않음

global feature vector
<figure data-origin-width="300" data-origin-height="64" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/K3Gk4/btraqsGdoBM/NgaNKFffP4kfMj1w44rYTK/img.png" data-origin-width="300" data-origin-height="64" data-ke-mobilestyle="widthOrigin"></figure>
(근데 왜 global feature vector 정의하는거지??)


most probable path
<figure data-origin-width="418" data-origin-height="77" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/F6Z4U/btrapssTSZI/Xw2krC91G8EdkYmxUbHr7K/img.png" data-origin-width="418" data-origin-height="77" data-ke-mobilestyle="widthOrigin"></figure>
-Viterbi algorithm (viterbi 이해 못함)

**특이한 지점: CRFs의 decoding 과정이 모든 global features에 대해 simple linear combination 문제로 줄여짐!!
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style6">
<h2 data-ke-size="size26">💡 Experiments of CRFs</h2>
<table data-ke-align="alignLeft">
<tbody>
<tr>
<td>Dataset</td>
<td>1) Kyota University Corpus ver 2.0 (KC) 2) RWCP Text Corpus (RWCP)</td>
</tr>
<tr>
<td>train</td>
<td>standard maximum likelihood estimation&nbsp;이용</td>
</tr>
<tr>
<td>regularization 2가지</td>
<td>① L1-CRFs -sparse solution (대부분의 weight들이 0일 때) ② L2-CRFs -non-sparse solution (대부분의 weight들이 non-zero일 때)</td>
</tr>
<tr>
<td>Evaluation</td>
<td>1) evaluation metric: F1-score(seg/to/all) seg: only the word segmentation is evaluated top: word segmentation and the top level of POS are evaluated all: all information is used for evaluation2) evaluation 방식: McNemar's test -convert outputs into character-based B/I labels -&gt; emply McNemar's paired test on labeling disagreements</td>
</tr>
<tr>
<td>Results</td>
<td>L2-CRFs가 성능 제일 좋았음</td>
</tr>
</tbody>
</table>

<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style6">
****아직 더 조사해봐야할 부분들
-viterbi 알고리즘?
-McNemar's test 뭔지?
-기존 CRF는 뭔지? Mecab의 CRF랑 어떻게 다른지?
-왜 global feature vector 정의하는거지??
-markov 모델?? 장단점??
-label bias, length bias 부분


-참고문헌
 
</div></div>

sohyunwriter

MECAB 논문 정리
 
Mecab 논문인 "Applying Conditional Random Fields to Japanese Morphological Analysis"를 읽고 정리해봤다. (아직 정리 중이라는 표현이 적절할 듯. 아직 정리 중이다)
 
본 포스팅은 다음의 4가지를 다룬다.
 
1. 일본어 형태소 분석기 모델들
2. CRF 이전 모델들의 문제점
3. CRF(conditional random fields)
4. Experiments of CRFs
  일본어 형태소 분석기 모델들
 
**일본어 형태소 분석
**모델들 (6가지)
1) Chasen: hierarchical structure 사용, IPA tagset 사용
**IPA tagset은 세 가지 부분으로 구성됨. POS, conjugation form(cform), conjugate type(ctype) 
cform이랑 ctype은 단어랑 conjugate에만 지정되고, POS는 4레벨의 subcategory가 있음. 
e.g. 명사-일반명사
           -고유명사
             -사람
             -조직
             -장소
 
2) rule-based analyzer (JUMAN): hierarchical structure 사용
 
3) HMMs (Hidden Markov Models)
-hidden state에 영향을 미치는 것은 바로 이전의 hidden state뿐
-hidden state 찾는 법: conditional probability 이용
-단점: Markov 가정에 의해서 이전 hidden state에 의존적이므로 Label Bias의 가능성이 높음
 
4) MEMMs (Maximum Entropy Markov Models)
-hidden state에 영향을 미치는 것은 바로 이전 hidden state와 observation
-hidden state 찾는 법: conditional probability 이용
-단점: Markov 가정에 의해서 이전 hidden state에 의존적이므로 Label Bias의 가능성이 높음
 
5) E-HMMs (extended Hidden Markov Models)
 
 
6) CRFs (Conditional Random Fields)
-hidden state에 영향을 미치는 것은 모든 hidden state와 observation
-hidden state 찾는 법: 모든 종류의 hidden state에 대해서 가장 높은 확률을 고름
 
 
  CRF 이전 모델들의 문제점
1) word boundary ambiguity
-character based Begin/Inside tagging: character를 token으로 취급해서 Begin/Inside를 tagging하도록 만드는 것
-> 단점 2가지
① word segmentation에 대해 미리 정보가 있는 lexicon을 활용하기 힘듬
② redundant candidates가 많이 생겨 decoding 속도가 많이 느려짐
 
2) long-standing problems
① Hierarchical Tagset
-ChaSen, Juman은 hierarchical structure 사용
-hierarchical strcutre에서 1) suffix나 character같은 atomic feature를 잘 사용하면서도 2) 각 레벨을 incorporate하는 게 중요함
 
**왜 각 level을 잘 incorporate하는 게 중요하지?
-bottom lebel만을 이용하면 data sparseness problem 발생
-top level만을 이용하면, 세밀한 차이를 잡아내기 위한 granularity of POS가 부족함!!
(예1) 어떤 suffix들은 이름 뒤에 나옴 -> Name POS 사용하는 게 좋음
(예2) conjugation form (cform)도 반드시 구별되어야 하는데, 특정 단어 뒤에 나타나기 때문에!! (?)
 
-> extended HMMs의 경우 이러한 incorporate를 잘하기 위해 3가지 방식 이용
1) position-wise grouping 2) word-level statistics 3) smoothing of word and POS level statistics
-> 그러나 여전히 1) non-independent feature를 구별해내지 못한다는 점, 2) smoothing parameter를 ad-hoc 방식으로 선택한다는 한계 존재
 
 
② Label Bias and Length Bias
-next state classifier를 활용하는 dicrimitinative model 대부분은 label bias나 length bias가 존재
-HMM이나 MEMM은 label bias 존재
 
 
 
=> 이 2가지 문제를 해결하기 위해 CRF 나옴!!
  CRF(conditional random fields)
1) a number of correlated features for hierarchical tagsets can be incorporated which was not possible in HMMs
2) influences of label and length bias are minimized which caused errors in MEMMs
 
CRF식
-fk((wi−1,ti−1),(wi,ti)): i, i−1번째의 토큰의 feature fuction
-λk: learned weight
 
cf. 기존 CRF식과 Mecab에서 이용하는 CRF식이 뭐가 다른지?
: Mecab꺼는 word boundary ambiguity를 해결하기 위한 것으로 output sequence의 길이가 고정되어 있지 않음
 
global feature vector
(근데 왜 global feature vector 정의하는거지??)
 
 
most probable path
-Viterbi algorithm (viterbi 이해 못함)
 
**특이한 지점: CRFs의 decoding 과정이 모든 global features에 대해 simple linear combination 문제로 줄여짐!!
  Experiments of CRFs
Dataset
1) Kyota University Corpus ver 2.0 (KC)
2) RWCP Text Corpus (RWCP)
train
standard maximum likelihood estimation 이용
regularization 
2가지
① L1-CRFs
-sparse solution (대부분의 weight들이 0일 때)
② L2-CRFs
-non-sparse solution (대부분의 weight들이 non-zero일 때)
Evaluation
1) evaluation metric: F1-score(seg/to/all)
seg: only the word segmentation is evaluated
top: word segmentation and the top level of POS are evaluated
all: all information is used for evaluation
2) evaluation 방식: McNemar's test
-convert outputs into character-based B/I labels -> emply McNemar's paired test on labeling disagreements
Results
L2-CRFs가 성능 제일 좋았음
 
****아직 더 조사해봐야할 부분들
-viterbi 알고리즘?
-McNemar's test 뭔지?
-기존 CRF는 뭔지? Mecab의 CRF랑 어떻게 다른지?
-왜 global feature vector 정의하는거지??
-markov 모델?? 장단점??
-label bias, length bias 부분
 
 
-참고문헌
더보기
https://jeongukjae.github.io/posts/inside-look-at-mecab/
https://jrc-park.tistory.com/255
https://light-tree.tistory.com/125
https://ratsgo.github.io/data%20structure&algorithm/2017/11/14/viterbi/

Mecab 논문 정리 (작성 중)

댓글