Ngram Algorithm

Ngram Algorithm

SPHINX SQL를 서비스를 준비하면서 스핑크스가 가진 특이한 검색 방법에 고민을 많이했다.

N-GRAM 개념

N-gram은 통계학 기반의 언어 모델중 하나로 다음 단어를 예측할 때 문장에서의 모든 단어를 고려하지 않고 특정 단어(TOKEN)의 개수(N)만 고려한다.

ex) “산에서 들개 떼를 만났다” 등산 사고 민원 예고 울렸다

N	모델명	구현
1	Unigram	“산에서 / 들개 / 떼를 / 만났다” / 등산 / 사고 / 민원 / 예고 / 울렸다
2	Bigram	“산에서 들개 / 떼를 만났다” / 등산 사고 / 민원 예고 / 울렸다
3	Trigram	“산에서 들개 떼를 / 만났다” 등산 사고 / 민원 예고 울렸다
4	4-gram	“산에서 들개 떼를 만났다” / 등산 사고 민원 예고 / 울렸다

N-GRAM 고질적 문제

검색 속도만 봐도 알수 있듯, 단순한 할고리즘을 적용하여 검색 속도가 빠른편에 속한다.

또한 어떤 언어로든 구현할 수 있는 정도의 알고리즘으로 적용하기가 쉽다.

이러한 이점과는 반대로 검색 서비스 구현에 있어서는 지나칠 수 없는 큰 문제를 가지고 있다.

좋게 말하면 "검색 누락이 없다." 이지만 다르게 말하면 "의도하지 않은 정보도 등장한다." 일것이다.

실제 서비스에 적용하는 단계에 있어서는 정확한 그리고 의도한 결과가 나타나야 좋지만 N-GRAM 방식은 가능한 모두 가져다 준다.

너가 뭘 좋아할지 몰라 다 준비했어.

때문에 이러한 알고리즘을 적용한 스핑크스가 노이즈가 많은 SQL 이라는 말이 등장한 것이다.

ex) "들개"

의도) “산에서 들개 떼를 만났다” 등산 사고 민원 예고 울렸다...

결과) 이들 개미가 발견된 컨테이너는 베트남 하이퐁에서 인천항을 통해 지난 10일 국내로 수입됐으며 21일 해당 물류센터로 옮겨졌습니다.

문제를 어떻게 해결할 것인가?

검색 서비스에 적용하기 위해서는 N-GRAM의 노이즈 문제를 해결해야한다.

1. N 의 수를 늘리자

2. TOKEN을 많이 가져가자

ex) "산에서 들개"

의도) “산에서 들개 떼를 만났다” 등산 사고 민원 예고 울렸다...

결과) “산에서 들개 떼를 만났다” 등산 사고 민원 예고 울렸다...

-	Unigram	Bigram	Trigram
Perplexity	962	170	109

Perplexity의 값이 작을 수록 좋은 성능을 나타내며 표에서 보듯 N의 값이 클수록 이상적인 결과를 볼수 있다.

TOKEN을 늘리는 것이 항상 좋은 방향일까?

딥러닝 문서에서는 N이 커진다 하여 좋은 결과를 보이지 못한다고 말한다.
이를 Trade-off라고 하며 가장 좋은 결과를 보기 위해서는 N의 값을 1~4에서 지정하는 것이 가장 좋다고 한다.

REFERENCE

• 딥러닝을 이용한 자연어 처리 입문
• Elastic 가이드북