Framework/스팸 필터링2009. 3. 12. 02:21

잘 알려져 있는 문제인
"n개의 도시가 있는데, 집에서 (1번 노드) 출발하여 모든 도시를 단 한번씩 거치며 집으로 돌아오는 최소 거리 경로를 찾아라." 길찾기 문제의 문제가 주어졌을 경우

아마도 깊이 우선이니, 너비우선이나 혹은 이기적 알고리즘(greedy algorithm) 같은 걸 떠올릴지 모른다. 알고리즘에 좀더 익숙하다면 분할 정복(devide and conquer), 동적 프로그래밍(dynamic programming), 한정 분기(branch and bound), 다익스트라 알고리즘 등을 사용할 수 도 있다. 이런 결정론 알고리즘은 정확한 해(전역 최적해)를 보장하지만 문제크기가 커지면 현실적인 시간 내에 풀이가 불가능 하거나 greedy algorithm처럼 지역 최적해로 수렴하게 된다.

개인적이지만 이 문제에 대해 가장 좋아하는 풀이방법은 메타 휴리스틱한 방법중 하나인 개미 군락 최적화(ant colony optimization)이다. 이 알고리즘은 자연에서 얻은 영감이 바탕이 된 개미의 군락생활에서 먹으를 집으로 이동하는 자업을 효율적으로 수행하기 위해
 - 이동 경로에 페로몬을 뿌림
 - 가한 페로몬의 경로를 선호
 - 시간에 따라 페로몬 증발 이라는 조건을 활용한다.

간단한 알고리즘을 구성하면
페로몬 값을 초기화 한다
repeat {
   해를 생성한다.  // 높은 페로몬 경로가 선택될 확률이 높다.
   페로몬을 갱신한다.
} until(멈춤 조건) ;
그동한 발생한 해중에 가장 좋은 것을 출력한다.

이 알고리즘을 좋아하는 이유는 첫번째는 처음에는 좋은 해를 찾지 못한다고 해도 시간이 지날수록 점점 더 좋은 해를 구할 가능성이 높고 두번째로 환경이 변해도(최적의 길이 변해도) 그에 대해 적응력을 발휘한다는 점이다. 여기서 프로그래밍 십계중 제 4계를 말할 수 있다. 만약 한번에 답을 찾는 것이 어려운 문제라면 연속성을 고려해라. 처음부터 옳은 답을 맞춰야 할 필요는 없다.

만약 소프트웨어가 단지 수학에 불과하다면 정확한 답과 순간적인- 측정 당시의 효율이 우선이 되겠지만 소프트웨어에서 일어나는 문제는 대부분 "잘~"에 관여한 문제이고 스팸판단도 이와 같은 문제라고 생각한다. 스팸판단에 있어 단어 사용등에 있어 수학모델을 사용하는 결정론적인 알고리즘보다 스팸일 가능성이 높은 순으로 정렬할 수 있고 변하는 환경에 대응할 수 있는 알고리즘 시스템이 나아보인다.


두번째로 생각할 것은 "여러개를 결합하면 가장 좋은 단일 알고리즘 보다 좋다"라는 Hybrid한 접근방식이다.

생체 인식에 있어 가장 많이 알려진 방법은 지문 인식이지만 역사가 오래되어서 정교한 만큼이나 그만큼 해킹 기술도 발달하였다. 지문인식이 대단한 정밀 기술로 보일지도 모르지만 아파트 현관문에 사용되는 정도의 지문 기술은 영화에 나오는 최신 기술따위를 사용하지 않아도 지문을 얻을 수 있다면 열쇠보다도 더 쉽게 뚫을 수 있다.(비록 열쇠를 가지고 다닐 필요가 없어서 편리는 하겠지만) 최근에는 지문인식은 -종이나 젤라틴 등에 - 복제된 지문데이타를 방지하기 위해 땀샘 인식을 하는 등의 좀더 복잡해졌지만 복잡해진 만큼이나 비싸지며 동일인임에도 불구하고 거부할 가능성도 높아진다.

생체인식의 분야에는 사실 영화등에서 소개된것만 해도 홍채, 열적외선, 목소리 등이 있고 발걸음이나 손등의 정맥등을 이용한 생체인식 방법도 사용되고 있다. 먼 미래에 언젠가 기술이 충분하게 성숙이 되면 가격도 싸고 인식의 오류 가능성도 극히 낮은 어떤 방법이 나올지도 모르겠지만 현재로서 프로그래밍 관점에서 생각해보면 가장 합리적인 방법은 이 여러가지 방법을 모두 적용한 하이브리드 모델이 나아보인다. 간단한 지문인식 시스템 정도는 뚫을 수 있겠지만 목소리도 비슷하고 홍채도 비슷하고 열적외선의 분포도 비슷하고 손등의 정맥위치도 비슷하고 발걸음도 비슷하게 할 수 있는 확률은 어느 한 분야의 최고의 기슬을 사용한 것보다 낮을 것이다.

단순히 계산을 빨리 해야 하는등의 문제가 아니라 좀더 "잘" 판단해야 하는 문제에 있어서는 베이지언 필터링 같은 하나의 알고리즘에 의존하기 보다는 이처럼 하이브리드 알고리즘이 더 많은 장점을 가질 수 있다.


'Framework > 스팸 필터링' 카테고리의 다른 글

판단에 있어서..  (0) 2009.03.16
구현  (0) 2009.01.12
판단의 기본 아이디어  (0) 2009.01.12
개요  (0) 2009.01.09
Posted by bleujin