고요한 하늘

 EM  for Gaussian Mixture

공분산(Covariance) : 공분산(共分散, Covariance)은 확률론과 통계학분야에서 2개의 확률변수의 상관정도를 나타내는 값이다.(1개의 변수의 이산정도를 나타내는 분산과는 별개임) 만약 2개의 변수중 하나의 값이 상승하는 경향을 보일 때, 다른 값도 상승하는 경향의 상관관계에 있다면, 공분산의 값은 양수가 될 것이다. 반대로 2개의 변수중 하나의 값이 상승하는 경향을 보일 때, 다른 값이 하강하는 경향을 보인다면 공분산의 값은 음수가 된다. 이렇게 공분산은 상관관계의 상승 혹은 하강하는 경향을 이해할 수 있으나 2개 변수의 측정 단위의 크기에 따라 값이 달라지므로 상관분석을 통해 정도를 파악하기에는 부적절하다. 상관분석에서는 상관관계의 정도를 나타내는 단위로 모상관계수 ρ를 사용한다.

LINK : http://ko.wikipedia.org/wiki/%EA%B3%B5%EB%B6%84%EC%82%B0

다변량정규분포 - Multivariate Normal Distribution( multivariate Gaussian distribution ) : http://it4lnu.hannam.ac.kr/Book/MDA/dist_mda_wolfpack.pdf

LINK : http://enc.daum.net/dic100/contents.do?query1=20XXX50347

 

 그림 출처 : nlp.korea.ac.kr/new/seminar/2000spring/fsnlp/Chap14_Clustering.ppt

POS Tagging에서의 EM

1. Complete data : 문장, 대응하는 태그열

2. 관측 데이터 : 문장

3. 비관측 데이터 : 태그열

4. 모델 : transition/emission 확률 테이블

   
   

Synonyms(동의어) : 같은 의미를 가진 모양이 다른 단어

eg > 'car' & 'automobile'

재현율이 작아지는 원인

Polysemys(다의어) : 여러가지 뜻이 있는 단어

eg > 'saturn'

정확률을 낮춘다

Topics과 words 사이의 불일치 문제

LSA의 목적은 문서 속에 있는 Topics에 대해서 단어 뒤에 숨겨진 의미에 대해서 찾아 내는것이다.

Topics과 Words사이의 찾이점:

Word : 관측할수 있다.

Topics : 관측할수 없다.  숨겨져 있다.

LINK : http://www.springerlink.com/content/l5656365840672g8/fulltext.pdf

LINK : http://www2007.org/posters/poster859.pdf

LINK: http://www.dcs.shef.ac.uk/~genevieve/lsa_tutorial.htm

LINK :  www.aclweb.org/anthology-new/E/E06/E06-1014.pdf

LINK : http://en.wikipedia.org/wiki/Probabilistic_latent_semantic_analysis

LINK : www.csie.ntu.edu.tw/~b94063/files/PP06.doc

LINK : rakaposhi.eas.asu.edu/cse494/notes/s07-plsa.ppt  

LINK : http://bi.snu.ac.kr/Publications/Conferences/Domestic/KISS06F_ChangJH.pdf( Topographic non-negative matrix factorization에 기반한 텍스트 문서로부터의 토픽 가시화 )

LINK : http://www.nature.com/nbt/journal/v26/n8/fig_tab/nbt1406_F1.html

이 글은 스프링노트에서 작성되었습니다.

EM 알고리즘은 확률 모델에서 MLE parameters를 찾기위해 사용한다.


EM 알고리즘은 두단계를 거치는데

첫번째 단계는

               E단계( Expectation step )

두번째 단계는

              M단계( Maximization step )이다.

 running 과정에서는 이 두 단계가 계속 반복된다.

 간단한 예를 살펴보면

1. 초기값 설정

2. 반복 과정

               2.1 E-STEP : 주어진 현재 파라미터 추정치로 unknown 변수가 특정 class에 속하는지에 대한 기대값을 추정한다.

               2.2 M-STEP : unknown 변수의 기대 추정치를 가지고 데이터의 최대 확률값(MLE)을 재 추정한다.

EXAMPLE >>
[STEP1] 4,10 , ? , ?

                                Initial mean value : 0

[STEP2] 4, 10, 0 , 0

                                New Mean : 3.5{ ( 4 + 10 + 0 + 0 ) /4 }

[STEP3] 4, 10, 3.5, 3.5

                                New Mean : 5.5

[STEP4] 4, 10, 5.25, 5.25

                                New Mean : 6.125

[STEP5] 4, 10, 6.125, 6.125

                                New Mean : 6.5625

[STEP6] 4, 10, 6.5626, 6.5625

                                New Mean : 6.7825

[STEP7] 4, 10, 6.7825, 6.7825

이 과정을 반복하다 보면 Mean이 7에 가까워지는것을 볼 수 있다.

 

 파라미터를 추정하는 방법론이기 때문에 수렴 속도가 빨라지거나 하지는 않는다

LINK : http://en.wikipedia.org/wiki/Expectation-maximization_algorithm

LINK : Foundations of Statistical Natural Language Processing

LINK : http://nlp.korea.ac.kr/new/seminar/2000spring/fsnlp/Chap14_Clustering.ppt

-----------------------------------------------------------------------------------------------------

 

보면 알겠는데
누가 설명해 달라면 입이 닫힌다...
잊어 버릴때마다 정리를 해야겠다.

조건부 확률 이라함은.
P(A|B) 이런식으로 표현을 하고
사건 B가 일어나고  사건A가 일어날 확률을 구하는 문제이다.
( 이 말은 B가  전체 도메인이 되었다는 것을 의미한다. {B = 전체도메인} 이 표현이 없다면 A,B를 포함하고 있는 전체 박스가 전체 도메인이다 )
단순하게 생각하면 A와 B의 교집합을 구하는 문제로 생각할수 있는데
항상 P(A|B) = P(B|A)가 아니기 때문에 이말은 틀린 말이다.


보통 이식은 다음과 같이 풀어진다.
P(A|B) = P(B|A)*P(A)/P(B)

유도과정을 살펴보면

먼저 P(A|B)는 아래와 같다


그러면 반대로 사건 A가 일어 났을때  사건 B가 일어날 확률은 아래와 같다.

P(A|B)=P(A^B)/P(B)
=> P(A|B)*P(B) = P(A^B)가 되고

P(B|A)=P(A^B)/P(A)
=> P(B|A)*P(A)=P(A^B)가 된다.

이두식의 우변이 같으므로
결과적으로 아래와 같은 식이 성립한다.


그러면 P(A|B)를 구하기 위해서는 결과적으로 아래의 식과같이 유도가 된다.


P(A|B)를 구하기 위해서는
P(B|A) ,
P(A),
P(B) 의 값을 알고 있어야 한다.

 결론적으로 P(B|A)를 알고  있으면 P(A|B)를 구할수 있다.


간단히
참고 :
1. http://synap.tistory.com/entry/%EC%A1%B0%EA%B1%B4%EB%B6%80-%ED%99%95%EB%A5%A0%EB%B2%A0%EC%9D%B4%EC%A7%80%EC%95%88%EC%9D%98-%EC%9D%B4%ED%95%B4%EB%A5%BC-%EC%9C%84%ED%95%9C-%EC%98%88%EC%A0%9C-%EB%B0%8F-%ED%92%80%EC%9D%B4
2. http://enc.daum.net/dic100/contents.do?query1=20XXXX5791

Machine learning 공부할때 자주 나오는 개념

http://statgen.iop.kcl.ac.uk/bgim/mle/sslike_3.html

간단히 설명하면

사전 X가 나올 확률 P(X|p)로 표현하고

우도값은 L( p | x ) 이렇게 표현한다

동전 던지기 테스트

동전던지기를 100회 시행 해서

56번 앞면이 나왔을때

p = 0.52일 경우

p = 0.5일 경우

(계산 방법은 아래 excel 파일 참조)

p 값을 다양하게 해서 테스트를 해보면

p값이 0.56일때  우도값(likelihood)이 가장 크다

결국 Maximum Likelihood Estimation은 0.56이 된다.

왜 MLE에 우리는 많은 시간을 소비하는가?

이런 예제는 너무 간단해서 눈으로도 대략 MLE를 추정할수 있지만

우리가 접하는 모든 문제가 이렇게 간단하지만은 않기 때문이다.

LSA에 관한 여러 문서를 살펴본 결과 LSA를 WSD( Word Sense Disambiguation )에 사용할수 있을 것 같아서
테스트를 해보았다.

첨부한 input.txt파일을 입력으로 테스트를 진행하였고
input.txt파일의  내용은 '다음검색'에서 검색을 통해 구축했다.
검색어는 '피지'로 하였고
남태평양의 섬 '피지'에 대한 것과 피부 분비물 '피지' 각각 눈으로 선별하여 6개 4개로 총 10개의 문서로 구성되었다.

결과를 살펴보면
DOC1과 가장 관련이 깊은 문서는 DOC4이고
DOC2와 가장 관련이 깊은 문서는 DOC3이다.
input.txt 파일을 열어 보시면 알겠지만 테스트 결과를 확인하기 쉽게 하기 위해
문서 번호 1,2,3,4,5는 남태평양의 섬 '피지'에 관한 문서이고, 6,7,8.9,10은 피부 분비물 '피지'에 관한 것이다.
문서 6번부터 문서 10번까지 붉게 표신된 것들을 살펴보면 유사한 문서들이 모두 6번에서 10번 문서 사이에 존재하는 것을 알수 있다.
이결과만 놓고 판단할때는 LSA를 WSD에 사용해도 의미 있는 결과를 얻을수 있을것 같다.

LSA를 이용한 내용기반 검색엔진 시스템.pdf

Singular_Value_Decomposition_Tutorial.pdf

http://www.miislita.com/
LSA(Latent Semantic Analysis)를 구현하기 위해서 알아야 할 것들이 몇 가지 있다.
우선 SVD( Singular Value Decompositon )을 알아야 한다.
SVD에 대한 설명 아래 블로그에 가서 보면 도움이 될것이다.
SVD 설명 : http://blog.daum.net/hazzling/15807155
SVD 라이브러리 : http://tedlab.mit.edu/~dr/SVDLIBC/
svd 공부하기전에 알아야 할 것들

• vector length  = [4, 11, 8, 10]  |v| = sqrt(4^2 + 11^2 + 8^2 + 10^2) = p301 = 17.35
• Orthogonality = [2, 1,-2, 4] and [3,-6, 4, 2] [2, 1,-2, 4] * [3,-6, 4, 2] = 2(3) + 1(-6) - 2(4) + 4(2) = 0
• Normal vector = unit vector = vector length가 1인 vector
• transpose = 행렬의 행과 열은 바꾸는 것

 

• Orthogonal Matrix = A^T와 A는 orthogonal하다
  

• digonal matrix  = 대각선에만 값이 있는 행렬
  
  

  

   
• Determinant =
  n = 2

  

  n > 2
  

  

  
  
  
  
  그리고 또한가지 일반적으로 백터의 유사도를 계산하기 위해서 사용하는 코사인 유사도( cosine similarity )는

위에 있는 공식만 알면 된다.

대용량에서 문서와 문서와의 관계 텀과 텀의 관계에서 어떤 보이지 않는 정보를 추출할때 사용하는 방법론이 LSA이다.
간단하게 작은 샘플을 가지고 어떤 능력이 있는지 살펴보자

우선
6개의 문서가 있다.
문서 1: cosmonaut, moon, car
문서 2 : astronaut, moon
문서 3 : cosmonaut
문서 4 : car, truck
문서 5 : car
문서 6 : truck

이렇게 6개의 문서가 있는데
사람이 보고 유사한 문서를 찾으면
term을 기준으로 같은 텀이 들어간 4,5번 문서가 유사하고, 1,2번 문서가 유사하다고 말할것이다.
그런데 LSA는 이것말고 이 안에 숨겨진 다른 정보를 보여준다.
우선
위 6개의 문서를 행렬로 표현하면
A =  

	d1	d2	d3	d4	d5	d6
cosmonaut	1	0	1	0	0	0
astronaut	0	1	0	0	0	0
moon	1	1	0	0	0	0
car	1	0	0	1	1	0
truck	0	0	0	1	0	1

A라는 행렬에 숨겨진 정보를 찾기 위해서 SVD라는 것을 사용하는데
간단하게 설명하면 원본 행렬 A를 3개의 행렬로 분리하는 것이다.
공식으로 쓰면 A = USV 라고 쓰고
아래 보이는 테이블이 첫부분에 소개한 svdlibc로 얻은 값이다.

          
U=
 

	dim1	dim2	dim3	dim4	dim5
cosmonaut	-0.44	-0.3	0.57	0.58	0.25
astronaut	-0.13	-0.33	-0.59	0	0.73
moon	-0.48	-0.51	-0.37	0	-0.61
car	-0.7	0.35	0.15	-0.58	0.16
truck	-0.26	0.65	-0.41	0.58	-0.09

S=
 

2.16	0.00	0.00	0.00	0.00
0.00	1.59	0.00	0.00	0.00
0.00	0.00	1.28	0.00	0.00
0.00	0.00	0.00	1.00	0.00
0.00	0.00	0.00	0.00	0.39

V =

	d1	d2	d3	d4	d5	d6
dimension1	-0.75	-0.28	-0.2	-0.45	-0.33	-0.12
dimension2	-0.29	-0.53	-0.19	0.63	0.22	0.41
dimension3	0.28	-0.75	0.45	-0.2	0.12	-0.33
dimension4	0	0	0.58	0	-0.58	0.58
dimension5	-0.53	0.29	0.63	0.19	0.41	-0.22

이렇게 계산된 값중에 행렬 S에서 2*2만을 위하여
V와 곱한다.
B=S*V

그러면 아래와 같은 행렬이 만들어진다.
 

	d1	d2	d3	d4	d5	d6
dimension1	-1.62	-0.60	-0.40	-0.97	-0.71	-0.26
dimension2	-0.46	-0.84	-0.30	1.00	0.35	0.65

이들 사이의 cosine 유사도를 계산하면
                   DOC1        DOC2        DOC3       DOC4       DOC5     DOC6
   DOC1           1             0               0              0             0             0
   DOC2    0.781837           1              0              0             0             0
   DOC3    0.950136    0.937276           1              0             0             0
   DOC4    0.474432   -0.177918    0.176269           1             0             0
   DOC5    0.740118    0.159375    0.493512    0.943112          1              0
   DOC6    0.110596    -0.53319   -0.204841    0.927362    0.750205         1




위에 언급한 svdlibc 라이브러리고 위의 예제를 테스트 해본 결과 화면( cosine similarity를 사용 )

처음 데이터를 보면 d2,d3에는 하나의 공통 단어도 존재하지 않는다.

따라서 처음 데이터를 가지고 유사도를 계산한다면 0에 가까운 값이 나올 것이다.

그런데 SVD후에 유사도를 보면 유사도가 0.93으로 나온다.

문서 2에는 cosmonaut라는(러시아 우주비행사)가 있고 문서 3에는 astronaut(우주비행사)라는 의미적으로 유사한 단어가 포함되어 있음을 겉으로 드러낸 결과라고 할수 있다.









continue ---

최근 2개월간 나의 최대 관심사는 띄어쓰기이다.

물런 2개월 이전에도 관심을 가지고 논문 몇편을 보긴 했었다. 하지만 회사에서나 집에서나 대부분의 시간을 이문제에 대해서 생각한건 최근 2개월 동안이었던것 같다.

논문을 쓰기 위한 고민이 아니었기 때문에 고민의 가지수는 더 많아졌고,

그 고민들중 두가지는 필드에서 사용가능한 퀄리티와 속도였다.

이런 프로그래을 개발하는 것은 마치  두마리 토끼를 동시에 잡는 것과 비슷한 느낌의 일이었다.

보통 한국어 띄어쓰기의 경우 손쉽게 생각해 볼수 있는 방법이 통계적 방법을 이용하는 것이고 그중에서도 속도나 데이터 부족 문제를 피하기 위해서 바이그램(음절)을 사용하는 경우가 제일 쉬운 접근 방법일 것이다.

우선 바이그램 정보를 어떻게 추출하는지 살펴보면

바이그램으로 데이터를 트레이닝한다고 할때에도 여러가지 방법이 있을수 있다. 외부에 보여지는 두개의 음절이외에 어떤 정보를 추가적으로 담을 것인가..

트라이 그램보다는 바이그램 정보가 작고, 정보량도 부족하기 때문에 바이그램이 담을수 있는 최대치의 정보를 담기 위해서 노력했다.

예를 들면

[띄어쓰기가 더 쉽다 ]

이런 문장이 있다고 할때 여기서 바이그램을 추출하면

(공백 대신 => _ )

[ 띄어], [어쓰], [쓰기], [가가_], [가_더], [_더_쉽], [쉽다_]

 위와 같이 추출된다. (꺽쇠 괄호 안의 음절수는 항상 2이다)

 [_더_쉽]의 경우 음절 바이그램이지만 총 4개의(공백 포함) 정보를 담고 있다.

이처럼 바이그램이지만 비교적 정보를 많이 담았다고 생각했지만

아래의 예제와 같은 경우를 만나는 순간 바이그램의 한계를 직감할수 있었다.

ex> [먹는데이가아파요]

위 문자열에 대한 바이그램 정보를 다음과 같다.

먹는    2042 5848 0 1 8388 15699 8 21
는데    179998 187 53367 90 328859 309 113573 153
데이    73361 73171 76141 29836 10477 949 9636 307
이가    5692 2605 223119 25558 115146 3166 705 18
가아    2112 85 153333 331 4 1 166 0
아파    68547 166835 2413 213 6551 1309 17 2
파요    467 2 109 0 33 0 0 0

위의 테이블에 대해서 간단하게 설명하명

[먹는] 라는 바이그램 음절은

[먹는] 앞,중앙,뒤 공백없이 사용된 횟수가 2042 번이다.

[_먹는] 앞부분에 공백, 중간,뒤 공백없이 사용된 횟수가 5848 이다.

[먹_는] 중간에만 공백이 들어간 횟수가 0 번이다.

[_먹_는] 앞과 중간에 공백이 들어간 횟수가 1 번이다.

[먹는_] 뒤에 공백이 들어간 횟수가 8388 이다.

[_먹는_] 앞과 뒤에 공백이 들어간 횟수는 15699 이다

[먹_는_] 중간과 뒤에 공백이 들어간 횟수는 8이다.

[_먹_는_] 앞,중간,뒤 모두에 공백이 들어간 횟수는 21이다.

처음 시작은 공백이 있다고 가정한다.

다시 말하면 [_먹는데이가아파요_]와 같은 문장이 입력으로 들어왔다고 가정한다.

그렇게 되면

처음 시작은

[_먹는]     5848

[_먹_는]    1

[_먹_는_]    21

[_먹는_]    15699

이정도의 경우의 수가 생길것이다.

이중에서 가장 빈도가 높은 것은 [_먹는_] 이 된다.

문서 상에서는 "먹는 방법" 먹는 이유" 먹는 자세" 등과 같은 형태가 많기 때문에 당연히 [_먹는_]과 같은 형태가 고빈도로 나타난다.

그런데 우리는 [_먹는_]을 선택하면 안된다.

왜냐하면 우리가 원하는 것은 [_먹는_]이 아니고 [_먹는] 이어야 다음 [는데]를 시작할수 있기 때문이다.

시작이 틀리면 다음에 오는 분석에 영향을 미치기 때문에 우리는 다음단계의 확률 더나아가 다다음단계의 확률까지 계산을 해야할지도 모른다.

현재 상태에서는 일단 [_먹는_]이 확률이 가장 높기 때문에 이 다음 확률이 어떻게 되는지 살펴볼 필요가 있다.

다음 확률 값은 "는데"
는데    179998 187 53367 90 328859 309 113573 153

[는데]      179998

[_는데]    187

[는_데]     53367

[_는_데]   90

[는데_]     328859

[_는데_]   309

[는_데_]   113573

[_는_데_]  153

다행히 [는데_]의 빈도가 328859 로 가장 높다.

그러면 [는데_]가 될수 있도록 하려면 [_먹는]이 선택되어야 한다.

두가지 경우의 수만 가지고 판단을 하면

1. [_먹는]  [는데_] => [_먹는데_] => 5848 + 328859  = 334,707

2. [_먹는_][는_데] => [_먹는_데] => 15699 + 113573 = 129,272

   
   

   이와 같은  방식으로 마지막 음절까지 최대 빈도값을 추적해 가면

   먹는데/이가/아파요 라는 문장을 얻을수 있을 것이다.

   다음 포스트에서는 바이그램으로는 절대 처리할수 없는 예에 대해서 설명하겠다.
   

이 글은 스프링노트에서 작성되었습니다.

검색에 의존적인 언어처리를 하다보니

전에는 전혀 고민의 대상이 되지 않았던 것들이 큰 부담거리로 다가온다.

대학원에서 형태소 분석기의 입력은 모두 띄어쓰기가 올바로 되어 있다고 가정하고,

띄어쓰기 오류가 틀렸다고 하더라도 그건 형태소 분석기의 몫이 아니기 때문에

처리하지 않아도 되는냥 생각했었다.

그러나 실제 서비스를 하는 필드에 와서는 앞에서 언급한 가정들이 모두 무시된다.

사용자가 잘못한것도 수정을 하여야 하고, 검색엔진의 부담을 덜어주기 위해서도 수정이 필요하다.

띄어쓰기 오류가 있는 문장은 형태소 분석기로 보내기 전에 띄어쓰기 오류를 수정하여야 하고

하나의 어절과 같이 사용되어야 하는 복합명사 형태의 단일어는 떨어져 들어오더라도 붙여서 분석을

해주어야 검색엔진의 부담을 덜어줄수 있다.(검색엔진의 부담을 덜어준다는것은 검색엔진이 위치정보를 계산한다면 두개의 어절이 입력했는지 계산하는것보다 색인시에 단일어로 만들어주는것이 검색시 시간효율이 생긴다는 의미이다. 물론 이방법을 검색에 사용할 시간을 색인시에 사용하다로 이야기할수 있다)

전자는 띄어쓰기 모듈을 개발함으로써 해결할수 있는데 후자에 언급한 떨어져 들어오는 쿼리를 하나의 어절로 만들어주는건

어떤 방법으로 구현할까..

만약 저런식으로 처리해야할 대상 어절이 많다면....그 처리 속도는...

이런 고민을 해결할수 있도록 도와준 알고리즘이 aho-corasick(이하 AC)이다.

문자열 매칭 알고리즘중 유명한것이 BM(Boyer-Moore algorithm)과 KMP(Knuth-Morris-Pratt algorithm )인데 이둘은 하나의 단어를 문장에서 찾고자 할때 효과를 볼수 있는 방법이다.

이에 반해 AC는 하나의 어절보다는 찾고자 하는 패턴이 다수일때 성능이 발휘된다.

AC를 개발하기 알아두어야 할 내용은 다음과 같다.

TRIE : 어떤 TRIE도 상관은 없다. array를 사용하는 TRIE든 Linked-list를 사용하는 TRIE든 아니면 다른 TRIE든 하나의 Node에 하나의 엔트리만 저장하는 구조라면 상관없다.

FAIL FUNCTION : KMP나 BM에서 시간을 절약하기 위해 앞에 비교한 패턴정보를 다음에 비교할 패턴에 이용한다. 흔히 FAIL FUNCTION이라고 하는데 이것에 대한 이해가 있어야 한다.

팀에 프로그램 구현능력이 좋은 분이 계셔서 테스트 버전을 7-8시간정도 걸려서 구현한것 같다.

이렇게 구현된 AC로

대상 문서 1.5G 문서

대상 패턴 : 13만개

비교시간 : 5분(딱 5분)

서버 사양은 회사기밀이라서....

여러개의 패턴을 하나의 문서에서 찾고자 한다면 AC만큼 좋은것도 찾기 어려울것 같다.

관련 자료
http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html

http://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/