LDA ( LATENT DIRICHLET ALLOCATION )

LSA라는 개념을 처음 접했을때만 해도 상당히 신기한 알고리즘이라고 생각을 했다.

서로 다른 두개의 문서 하나의 문서에서는 자동차라는 의미로 automobile로 표현하고 다른 하나의 문서에서는 car 라고 표현했다고 했을때

두개의 문서가 모두 자동차에 대한 문서이면 단어들이 유사할테고

다른 단어들의 유사성을 바탕으로 automobile과 car과 동일한 의미의 단어일것이다를

행렬 인수 분해를 통해 밝혀내는 방법이다.

이 방법은 앞에서 이야기한대로 행렬 인수분해를 통해 차원 축수를 하고 텀과 문서의 특징들을 축소된 차원에 표현하는 건데

안타깝게 계산량이 많은데에 반해 병렬처리가 어렵다고 한다.

그래서 구글에서 뉴스를 보는 사용자들에 대해서 클러스터링을 시도 하였는데 LSA가 아니고 PLSA라는 방법을 선택하였다.

전자는 행렬 인수 분해라는 방법이고 후자는 조건부 확률로 계산이 가능한 방법이다. 두번째 방법은 병렬처리가 가능하여 많은 수의 사용자를 

클러스터링하는 문제에서도 mapreduce 프레임웍을 통해 많은 시간을 단축시킬수 있었다고 한다.

이 포스트에서는 적고자 하는 것은 위에서 언급한 LSA나 PLSA가 아니고 이런 종류의 알고리즘중에 가장 성능이 좋다는 LDA라는 방법이다.

LDA라는 방법에 대한 논문이나 자료는 많으니 직접 찾아서 공부하면 될것 같고 LSA관련 소스를 하나 찾았는데

이 소스를 분석하고자 한다.

첨언 : plsa와 lda의 차이점을 보자면 plsa는 학습 데이터에 상당히 의존적인 알고리즘으로 경우에 따라서는 over fitting 되는 문제가 있을수 있다.

그에 비해 lda는 알파 베타 값이라는 임의의 변수로 smoothing하여 over fitting이 덜하다고 한다.

우선 관련 자료는 http://www.cs.princeton.edu/~blei/lda-c/에 있다.

LDA 논문 : http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf

이사이트에 보면 ap.tgz 라는 테스트 데이터 파일이 있는데

우선 이파일을 구조와 정보에 대해서 보면 다음과 같다.

-rw-r--r-- 1 jchern jchern 1926191 10월 22  2004 ap.dat

-rw-r--r-- 1 jchern jchern 5745932 10월 22  2004 ap.txt

-rw-r--r-- 1 jchern jchern   85532 10월 22  2004 vocab.txt

위 내용처럼

압축을 풀면 ap.dat, ap.txt, vocab.txt 라는 3개의 파일이 있다.

ap.dat파일의 내용을 보면

186 0:1 6144:1 3586:2 3:1 4:1 1541:1 8:1 .....

로 표현돼 있다.

첫번째 필드는 이 문서의 unique한 단어수이고 두번째 0:1로 돼 있는 부분에서 0은 term_id 기리고 :1에서 1은 해당 텀이 해당 문서에서 발생한 빌도수이다.

ap.txt 파일은

<DOC>

<DOCNO> AP881218-0003 </DOCNO>

<TEXT>

 A 16-year-old student at a private Baptist school who allegedly 

처럼 돼 있고

ap.dat, vocab.txt 파일을 만들기 위한 소스 문서이다.

vocab.txt 파일은

i

new

percent

people

year

two

million

위 내용처럼 뉴라인으로 구분된 단어 리스트이다.

ap.txt 파일의 첫번째 문서를 보면 Baptist 라는 단어가 있다.

이 단어를 vocab.txt 에서 찾으면(case insensetive)

 5273 baptist

5273번째 라인에 있다. 0부터 index를 시작하면 5272가 되고

ap.dat에 5273이 있는지 확인하면 

5272:2  1번 문서에 5272 term이 2번 출연한다.

 private Baptist school ...

Shores Baptist Church...

첫번째 문서에 Baptist 단어가 두번 존재하는 것을 볼수 있다.

여기서 설명할 lda 소스에 입력으로 사용할 파일들을

위에 설명한 내용을 참고해 생성해 놓아야 한다.

ap.txt 파일을 최초의 소스 파일이고 이파일을 가지고

vocab.txt와 ap.dat 파일을 만들어 이파일을 lda의 입력으로 사용

* ap.dat 파일에 보면 term 순서대로 되어 있지 않고 어떤 순서인지 알수 없는 순서로 term들이 나열돼 있는데 이것은 term counting을 계산하기 위해서 hash를 사용했고 이것을 화면에 출력하다보니 이런 순서로 출력된게 아닐까 추축된다.

* [TIP] vi에서 혹시 직접 키워드의 위치 및 빈도 정보가 맞는지 확인하실때는 /\c키워드 로 입력하시면 대소문자 무시하고 검색됩니다.

프로그램 설명

./lda est 0.1 10 settings.txt ap.dat random output

lda-c-dist.tgz압축을 풀면

lda-c-dist 디렉토리가 생성이 되고

해당 디렉토리에서 컴파일을 하면(make)

lda라는 바이너리가 생성된다.

이 바이너리는 두가지 방식으로 실행할수 있다.

첫번째> ./lda est [initial alpha] [k] [settings] [data] [random/seeded/*] [directory]

두번째> ./lda inf [settings] [model] [data] [name]

첫번째 실행에 대해서 설명하면

 ./lda est 0.1 10 settings.txt ap.dat random output

첫번째는 est로 설정하거나 inf로 설정

두번째는 alpha의 초기값(double)

k는 latent layer의 개수

settings 기타 다른 설정값이 있는 settings.txt 파일

data 파일( ex> ap.dat)

어떤식으로 초기값을 설정할지( random or seeded or * )

그리고 마지막 output 디렉토리명