고요한 하늘

• q() quote
• qq() double quote
• qw() quote( split by space )
• qqw() double quote( split by space )
• double quote 안에서는 interpolation 가능

 MAP 함수는 배열을 INPUT으로 받아서 배열을 OUTPUT으로 만든다.

파일 삭제

SHIFT를 사용해서 하나씩 assign 할수도 있고

@_를 가지고 하나씩 변수를 할당할수도 있다.

HELP 옵션과 VERBOSE 설정을 예로

3개의 변수에 대해서 초기화

첨언 : 글을 쓰다 보니 LSH를 어디에 사용하는지 쓰지 않은것 같다.

LSH는 문서를 몇개의 signature( 고유값 )으로 표현하는 방법이다. 일반적으로 문서 하나가 100여개의 단어로 구성되어 있다면 이를 벡터로 표현했을때 100차원이라고 볼수 있다. 이것은 제한된 크기 n차원으로 줄이는 기술이다.

n이 크면 클수록 원본 데이터에 유사해지지만 속도가 느려지고 작아지면 속도가 빨리진다.
물론 차원을 줄여 속도가 빨라진다고 퀄리티까지 형편 없어지면 알고리즘이고 불리지도 않았을 것이다.

차원이 줄어들면 문서의 중복 제거나 클러스터링이 가능할것 같다.

구글에서는 이기술을 map & reduce와 접목시켜 개인화된 뉴스 클러스터링을 한다고 한다.

Locality sensitive hashing : 고차원 데이터의 차원 확률에 기반한 차원 축소 방법론

Basic idea : 해시 함수에서 같은 데이터는 같은 buket에 들어간다.

간단한게 LSH를 설명하면 다음과 같다

두개의 문서가 있을때

문서에 나타나는 모든 키워드에 ID를 부여한다.( ID는 unique 해야 하고, 두번째 출연한 키워드에 대해서는 이미 부여된 ID가 주어진다 )
id가 부여되면

문서1 = 1,2,3,4,5

문서2  = 1,2,3,4,6,7,8

이런 모습이 될것이다.

여기에 1차원 함수를 n 개 만든다.

예를 들면

각각의 문서에서 일정한 간격  k개 마다  term id  n개를 추출한다.

간격(k)은 임의대로 설정해서 4로 설정하고 첫번째는 5, 두번째는 7, 세번째는 15, 네번째는 20

추출된 n개의 ID에서 가장 작은 값을 선택한다.( get the signature )

그러면 결과적으로

첫번째 문서에서 추출한 id가 4개

두번재 문서에서 추출한 id가 4개가 된다.

이렇게 추출한 ID가 같으면 두개의 문서는 유사할 가능성이 높은 문서로 판단한다.

간격 k를 더 많이 설정하여 추출하면 더 많은 id가 추출될 것이고 신뢰성도 높아질 것이다.( 물론 계산량은 많이지고 속도는 떨어질 것이다 )

실제 알고리즘은 여기에 prime number와  universal hash, random permutation 과 같은 개념들이 추가된다.

 BOOL prime_number (int x)
  {
  for ( int i = 2; i<=sqrt(double(x)); i++)

     if( x % i == 0 )
        return FALSE;

   return TRUE;
}

약 240,000개 문서에 대해서

문서당 signature를 추출하는 과정까지 테스트 했을때 1분 30초 정도가 소요되었다.

속도가 중요한 경우에는 사용해 볼만한 알고리즘이다.

LINK :

http://people.csail.mit.edu/indyk/mmds.pdf

KNN : http://sj21.wo.to/tt/320?category=4

MIN HASH : http://www.stanford.edu/class/cs276b/handouts/minhash.pdf

 위 내용이 이해가 어렵다면

문서 A, B가 있고

우선 문서 A에서 다음 규칙에 의해서 키워드를 선택한다.

3, 6, 9 12.. 번째 키워드를 가져와 정렬한 후에 최상위에 오는 키워드를 선택한다.( 선택된 키워드는 k1 )

5, 10, 15 ...번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k2)

7, 14, 21... 번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k3)

그럼 A문서는 { k1, k2, k3 }가 되고  A`으로 표현

다음 문서 B에서 다음 규칙에 의해서 키워드를 선택한다.

3, 6, 9 12.. 번째 키워드를 가져와 정렬한 후에 최상위에 오는 키워드를 선택한다.( 선택된 키워드는 k1 )

5, 10, 15 ...번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k2)

7, 14, 21... 번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k3)

그럼 B문서는 { k1, k2, k3 }가 되고 B`으로 표현

만약 A` = B`이라면 문서 A와 문서 B가 같을 확률이 높다고 할수 있다.

조금더 정확히 하려면 키워드를 좀더 많이 선택해서 비교하면 된다

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

 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에 기반한 텍스트 문서로부터의 토픽 가시화 )

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

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


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

첫번째 단계는

               E단계( Expectation step )

두번째 단계는

              M단계( Maximization step )이다.

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

 간단한 예를 살펴보면

1. 초기값 설정

2. 반복 과정

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

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