전에 포스팅에서 구글 엔지니어에게 Map&Reduce가 어디에 쓰이는지 여쭈어 본적이 있었다고 글을 썼다.

오늘 스팸 처리 알고리즘 모듈을 생각하다가, 이거 스팸처리 하는 확률을 계산하는데, complexity가 상당히 높게 나오고, 스팸 리포팅들어오면 거의 모든 텀의 스팸 확률을 재계산 해야 한다는 그런 어려움(?) 생길거 같다는 생각을 해보다가, 결국 MapReduce로 분산처리를 해볼수 있을거라는 생각을 해봤다.

만일 스팸처리 자체가 텀의 독립성 가정을 하지 않는다면, 위와같은 MapReduce 모델은 쉽게 나오지 않을거구, 만일 나온다 하더라도 굉장히 노드단과 노드사이에 복잡한 확률 계산을 해야할 것이다.  (occam’s razer 같은 말도 있으니, 일단 간단하게 접근해 보자구.)

여기서부터는 구글이 이렇게 처리할것이라는 개인적인 예상을 기반으로  기술적인 접근을 해봤다.

구글도 독립성 가정을 하고 naive baysian rule같은 방법으로 처리를 하리라 예상을 해본다. (카이제곱을 쓴다고 해도 개별텀의 확률 계산은 해야한다.)

내가 하고 있는 중심생각은..

(구글이)각 텀의 확률 계산을 분산해서 처리할거라는 생각이다.

구글 엔지니어가 그당시 MapReduce를 스팸처리에 사용한다는 말을 하지 않았더라면 이런 생각을 안했을텐데 말이다. 하지만 스팸에 대한 확률 자체도 엄청난 데이터의 결과라는 이야기다.
매우 큰 학습 데이터가 있다면 스팸의 결과도 정밀해 지고, 몇개의 오류 학습 data로 인한 bisa도 줄것이다.

근데 이거 스팸 처리 알고리즘에 대해서 설명하자면, 수식이 좀 나오는데, 이걸 한번 처음부터 접근해보자.

일단 baysian rule은 위와같은 식으로 표현된다. 아래 식은 total probability formula에 의해 계산된 식이고 처음 나오는 식이 베이지언 룰의 핵심이 되는 식이다.

우리가 알고자 하는것은 P(c|x) 이다. c는 스팸집합을 의미하고 x는 어떤 특정 문서를 의미한다. conditional probability라고 하고는데 말로 풀면, x라는 문서가 주어졌을때 c라는 스팸 카테고리에 포함된 확률을 얻고자 하는것이다.
 
바로 알기는 힘드니까… 우항 계산식에 의해서 스팸이라고 리포팅된 x라는 문서가 포함될 확률을 사용자 리포팅에 의해서 계산할 수 있다. –> P(x|c)
P(c)는 전체 문서집합에서 스팸 문서가 차지하는 비율을 의미한다. 이것은 리포팅 된 값을 통해서 쉽게 알수 있다.

마지막으로 분모가 되는것은 모든 문서가 같은 같을 가지니 생략하면 분자만 남게 된고, P(c)에 대한 계산값도 바로 알수 있다. (하지만 이 P(c)값도 모든 문서에서 같은 값을 사용하므로 계산 결과에 큰 영향을 미치지 않을것이다. )

마지막으로 P(x|c)라는 값을 구해야 하는데, P(c|x)를 구하기 위해 문서를 텀단위로 나누고, 각각의 텀이 상호 독립적이라는 가정을 가지고 계산을 하도록 하자. 이 독립성 가정은 naive룰의 핵심이다. (하지만 원래 스팸에 포함된 단어가 독립적이지는 않지만…계산복잡도가 훨씬 줄어든다.)
따라서 아래와 같은 식이 나온다.

Wk가 나오지 않을 경우 모든 확률은 0이 되어 버리니, 아래와 같은 보정식을 사용한다.

vacabulary는 모든 학습된 문서에서 포함되지 않은 서로 다른 단어의 갯수이다.

n_c는 c카테고리(스팸)에 속한 모든 텀의 빈도수의 합, n_cw는 c카테고리에서 나오는 w라는 텀의 빈도수의 합이다.

이렇게 해서 마지막 식(1)을 사용해서 계산을 하면 x라는 문서가 스팸일 확률을 구할 수 있다. 그렇기 위해서는 각 텀의 스팸 확률을 구해야 하는데, 이 텀의 스팸일 확률이 매번 스팸 리포팅이 들어갈때마다 전체가 다시 계산이 되어야 해서 가장 복잡도가 큰 부분이 된다. 이 부분을 분산처리를 하는게 아닐까 하는 생각을 해본다. 그럼 분산 처리를 위한 공식을 만들어 보자!

i개의 Node로 분산을 한다고할때… 위 P(w|c)를 어떻게 구할까?

우리가 구하고자 하는 값은

P( w | c | N_i ) 이다. (N_i는 i번째노드일 확률이다. )

P(w|c)와 P(N_i)는 통계적으로 독립적인 사건이기 때문에. P(w|c) * P(N_i)로 나타낼수 있다. (스팸일 확률과 n노드로 분배되는것은 관련이 없다.)
P(N_n)은 전체텀갯수중에서 노드 n에 분배되어 있는 텀의 갯수의 비율이다. 그러니 독립적인 노드에서는 P(N_n) 값은 일정하게 유지되어서 중복계산할 필요가 없으므로,  중점적으로구할 부분은 각 노드별로 P(w|c)
 
그럼 n노드로 분산되어 있는 텀 P(w|c)의 확률은 이렇게 구할수 있다.

위의 식을 이용해 (1)번식을 구할수 있고, 그에따라 문서의 스팸 확률을 구할 수 있다.

여기서 중요한것은 각 노드에 있는 텀의 확률값을 계산하여 분산시켜 놓는다는 중요한 의미와 그리고 그 분산되어 있는 확률값을 가져와 텀의 전체 확률을 계산할 수 있다는 것이다.

1) Map Process : 학습대상이 되는 스팸인문서에서 term을 추출하여,  (term, spam_term_count) 튜플쌍을 만든다.
2) Combine Process : (3)번식을 이용해서 노드별로 term 확률을 계산한다.
3) Reduce Process : (2)번 식을 이용해서 P(w|c)를 계산하고  (term, P(w|c))를 계산하여 오름차순(내림차순)으로 저장해 둔다. (binary search를 위해) – hadoop은 오름차순이 기본 정렬이니 그냥 써도 되겠다.

이렇게 처리해 두면 각 term의 확률값을 binary search로 logn의 복잡도만으로 접근해서 쓸수 있다.

물론 스팸메일 리포팅이 올때마다. 1,2,3번프로세스를 하는건 넌센스일 것이다. 대용량 메일 시스템이라면 아마도 중간에 버퍼를 둬서 일정한 기간에 한번씩 확률을 계산하지 않을까 한다.(물론 스팸에 대한 처리는 바로 되어야 하기 때문에 전체 계산 결과에 대한 최근 계산결과의 후처리 과정이 들어갈 것이란 예상을 해본다.) 

베이지언을 쓰던 카이제곱 방법을 쓰던지간에 term의 확률을 구하는것은 꼭 필요한 Process이다. 그리고 확률계산Processing이 시간을 가장 많이 잡아먹는 부분이여서 분산으로 처리하는 방법을 생각해 봤다.

전적으로 뒤의 분산 프로세스 방법과 분산처리된 노드의 확률계산식은 내가 만든거라서 검증은 안된거지만 충분히 설득력은 있으리라 본다. ^^; (오류가 있으면 지적해 주세용…)
좀더 발전시켜서 논문으로 써볼까도 하지만, 그럴 시간은 없고 이곳에 그냥 써봤다. 헤헤

에고… 여기까지 학교 텀 프로젝트인 스팸 서버 구현에 대한 function을 정리하다가, 분산처리하는 생각까지 와봤다.  ㅡㅡ;

나만의 결론은 그 구글 엔지니어가 말한 “Gmail 스팸처리를 MapReduce의 방법을 사용해 쓴다”는 말을 그당시에는 그러려니 했지만, 이제 나름 이렇게 하지 않을까 정리를 해보니, 꽤나 나 자신에게 설득력이 있게 보인다.

이상 요즘 분산처리와 hadoop의 매력에 빠져서 어우적 대는 gogamza 였습니다. 햐~~오랜만에 장문의 포스팅이네. ㅋ

주말에 고민해본 Distribute Spam sniping. by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.