Month: July 2014

TF-IDF와 Cosine-similarity는 보통 문서를 검색할 때 쿼리와 문서간의 유사도를 측정하여 순위를 정하는데에 쓰인다. 하지만 난 질문/답의 모음을 똑같이 적용해보면 어떨까 생각해서 AutoTweet이라는 프로젝트를 만들었다. 이 프로젝트는 내가 트위터에서 멘션을 달면 원본 트윗과 내가 단 멘션을 자동으로 수집하고 그것을 이용하여 나중에 질문에 대한 적절한 답을 뽑아준다.

질문/답의 세트(앞으로는 “문서”라고 한다)가 1000개가 넘어가니 gram의 수가 10000개를 넘어섰다. (gram은 각 문서를 2글자 단위로 쪼갠 조각들이다.) 이 gram들에 대해 idf값을 구해야 하는데 양이 그렇게까지 방대한 건 아니지만 부담이 될 정도로 오래(CPython2.7로 돌렸을 때 7초 가량) 걸리기는 한다.

그래서 영어로 된 논문도 읽어보고 별 삽질을 다 해본 결과 정확하게 구하려면 어떻게 하든 오래 걸린다. 응답을 뽑아낼 때 계산하는 건 부담이 되니 문서를 추가할 때에만 시간을 소모하게 하는 게 제일 나은 방법이긴 하지만 정확도를 약간 희생하더라도 속도를 올리는 방법이 있었다.

• 처음으로 적용한 방법은 gram이 하나도 겹치지 않는 문서들은 애초에 cosine-similarity를 계산할 때 제외시켰다. 정확도에 영향을 끼치지 않는 좋은 방법이지만 그렇게 빨라지지는 않았다.
• idf가 평균보다 낮은 gram은 계산에서 제외시켜 보았다. 정확도에 영향을 끼치지만 속도에 별 차이가 없었다. 애초에 cosine-similarity를 구하는 건 별로 느리지 않았다.
• idf를 다시 계산하는 걸 포기했다. 어차피 대부분의 경우 gram이 포함된 문서의 수는 그대로인채 전체 문서의 수만 1 증가할 뿐이다. 1000개가 넘은 시점에서 그게 그렇게 차이가 나지는 않을 것이다.

idf는 log(<전체 문서의 수> / (1 +<gram이 들어있는 문서의 수>))로 구하는 게 일반적이다. 전체 문서의 수는 워낙 커서 1 증가한다 해도 차이가 별로 없을 것이라 생각했다. 반면 분모에 들어가는 부분은 변화가 상대적으로 클 것 같았고 언제 변하는지도 예측이 가능하다. 추가할 문서에 들어있으면 변화한다. 그리고 질문이 들어왔을 때 그 질문에 들어있는 gram들은 얼마 되지도 않으니 그 경우도 idf를 다시 계산했다. 그래서 다음과 같은 두 경우만 idf를 다시 계산하게 했다.

• 추가하는 문서에 들어있는 gram들 (문서를 추가할 때 계산)
• 질문에 들어있는 gram들 (질문이 들어올 때 다시 계산)

질문에 들어있는 gram들을 가진 문서에 들어있는 gram들을 전부 다시 계산하면 정확도는 100%가 되지만 실험해보니 7개만 계산하면 될 것을 3000개 정도 계산하고 있었다. 그래서 빼버렸다. 해당 커밋은 여기다. 그렇게 오차가 크지도 않고 계산할 양은 많이 줄었으니 충분히 효과적이라 할 수 있겠다.