UIUC CS410 — Document Length in VSM

Wonhee Jung
Sep 8, 2018 · 4 min read

4주차 끝까지 갔다가 거기서 만난 일부 수학표현이 이해가 되지 않아 다시 Week 2 에서 다루었던 Vector Space Model 에서의 document length관련 내용으로 돌아온 김에 다시 정리.

Document Length가 뭐…?

사용자가 문서 검색을 위해서 다음의 질의문장을 사용했다고 하자. “일리노이 대학교 입학 절차”. 여기서 각각의 “일리노이”, “대학교”, “입학”, 그리고 “절차” 가 각각의 검색단어로 인식이 되었다 치자.

문서1)

어쩌구 저쩌구 대학교 어저구저쩌구 입학 어쩌구저쩌구 어쩌구 저쩌구 이러쿵저러쿵 절차를 통해 구구절절...

문서2)

어쩌구저쩌구 입학 이래저저래…
50 라인 이후에
대학교가 이러쿵저러쿵… 구구절절…
또 다시 100라인 쯤 뒤에
그래서 일리노이에서는
또다시 50라인 쯤 이후에
그래서 입학 절차가 이러쿵저러쿵

문서1과 문서2를 살펴보면, 총 4개의 검색어 중 문서 1은 대략 2줄 정도의 내용에 3개의 검색어가 보이고 “일리노이” 라는 검색어는 찾을 수 없다. 문서 2는 최소 200라인 이상의 내용에 (아마도 수천 단어 중) 검색어에 포함된 모든 단어를 가지고 있다.

문서 2는 검색어에 포함된 모든 단어를 찾을 수 있었고, 문서1은 그 중 1개를 제외한 모든 단어를 찾을 수 있었다. 그럼 여기서 질문

사용자가 찾는 문서가 문서1일 가능성이 높을까? 아니면 문서2가 높을까? (혹은 보다 더 관련있을까?)

생각해 보면 사용자가 어떤 질의를 검색 시스템이 하던간에 어떤 문서 d가 엄청나게 긴 문서라면 어떻게든 해당 검색어들을 문서 내에서 찾을 수 있을 가능성이 아주 높아진다. 그럼 과연 그 문서가 사용자가 찾는 문서인가? 그럴수도 있겠지만 그렇지 않을 가능성이 아주 높다. 오히려 달랑 10문장 밖에 되지 않는 문서에서 질의에 사용된 5개의 단어 중 4개를 찾을 수 있었다면 그 문서가 우리가 찾는 문서일 가능성이 더 크다.

그래서 우리는 검색을 할 때 찾아낸 문서 중에서 길이가 긴 문서들은 가중치를 줄 때 오히려 벌점을 주고(penalizing), 길이가 짧은 문서들은 벌점을 더 주거나 오히려 reward를 줘서 검색결과 노출시 유리하게 만들 필요가 있다. 이걸 Document Length Normalization이라고 하는데, 말은 거창한데 뭐 별다른 건 없고 바로 앞에서 설명했듯이 doc length normalizer를 이용해서 각각의 문서들을 doc length에 따라 penalizing을 하겠다는 이야기다.

그중 수업내용이 다루는 건 Pivotal Length Normalization과 BM25/Okapi 두가지.

Pivotal Length Normalization

Pivotal length normalization에서의 normalizer는 문서의 길이 |d| 가 평균 문서의 길이(avdl, average doc length) 와 같은 경우, 즉 |d| = avdl 인 경우 1이다.
좀 더 자세히 적어보자면

normalizer = 1 — b + b * |d|/avdl, where 0≤ b ≤ 1

로써 그래프를 그려보면 x축이 문서 길이 |d|이고 y축은 1 — b 값인, 그리고 기울기가 b / advl 이다. advl의 경우 문서의 평균 길이는 정해진 값일 것이기 때문에 그냥 상수취급하면 이 그래프는 기울기가 b에 의해서 좌지우지되는 셈이다. 즉 b가 커지면 기울기가 급격히 커져서 문서의 길이가 advl보다 크면 클수록 더욱 더 penalize되고, 짧으면 짧을수록 reward가 커지는 형태. d = advl 이면 리워드도 패널티도 없다.

그래서 이 내용을 다시 그 이 내용 전에 배웠던 TF(term frequency)쪽 내용에 끼워넣으면 다음과 같은 식이 나오고, 이걸 Pivotal Nength Normalization VSM이라고 부른다.

결국 이 식은 기존의 TF 에 문서길이에 따라 penalizing을 하기 위한 Inverse Document Frequency (IDF)를 결합한 식이다. 문서가 커질 수록 전체 값은 작아지고, 문서가 짧아질수록 결과값은 커진다.

자 이번건 여기까지. 다시 이제 Week4로 넘어갈 차례.

Wonhee Jung

Written by

Daughter's daddy, husband, lifelong gamer and learner. Senior Software Engineer@Blizzard Entertainment and studies for master’s degree in CS@UIUC.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade