В 1958 году Ханс Питер Люн предположил в своей статье "The Automatic Creation of Literature Abstracts", что "the frequency of word occurrence in an article furnishes a useful measurement of word significance", что до сих пор, вероятно, является одним из самых значимых открытий в науке о поисковой информации и используется во всех известных больших и малых поисковых системах, начиная от Google и Yahoo до кастомных решений, таких как ElasticSearch и Manticore Search.

Значимость предположения Люна невозможно переоценить, и многие последующие научные исследования в области информационного поиска опирались на это предположение, хотя не все из них упоминали его, вероятно, потому что со временем оно стало аксиомой.

В этой статье я постараюсь на простых примерах показать, как TF, означающий «частота терма», и его counterpart IDF, означающий «обратная частота документа», помогают находить то, что вы ищете.

Возьмём 5 документов:

1. My dog doesn't like all my pets, but me and my wife do love them all. A dog cannot be a cat lover
2. Cats and dogs do not like each other, but my cat does like dogs
3. Walking a dog is a good start of the day
4. Not all cats like walking, but some cats do
5. All dogs like walking, but mine doesn't like. It's like so weird

и попробуем ранжировать их (т.е. найти самые и наименее релевантные и порядок) для разных запросов.

Вес = 1, если слово встречается, и 0 иначе

Запрос: 'like'.

Обратите внимание, что мы не знаем, что подразумевается под «like» в запросе: «A is like B» или «I like smth». Что же мы можем сделать, чтобы ранжировать документы?

Первое, что приходит в голову, — если документ вовсе не содержит слово «like», то он, вероятно, менее релевантен. Таким образом порядок может быть:

1. My dog doesn't <b>like</b> all my pets, but me and my wife do love them all. A dog cannot be a cat lover
2. Cats and dogs do not <b>like</b> each other, but my cat does <b>like</b> dogs
4. Not all cats <b>like</b> walking, but some cats do
5. All dogs <b>like</b> walking, but mine doesn't <b>like</b>. It's <b>like</b> so weird
3. Walking a dog is a good start of the day

Мы поместили документ №3 в самый конец, поскольку он не содержит «like». Что касается остальных, мы не меняли их порядок, так как они все содержат «like». Является ли такое ранжирование достаточно качественным? Я так не считаю, поскольку среди первых четырёх документов есть два (№5 и №2), которые кажутся более релевантными, чем остальные, так как они предоставляют больше фактов, связанных с запросным термином «like» (помним, что мы не знаем, что именно подразумевается под «like»), но они не находятся в топ‑2. Что же мы можем с этим сделать?

Вес = частота терма

Запрос: 'like'.

Как уже говорилось, согласно предположению Люна, документы, содержащие больше вхождений терма запроса, могут быть более релевантными. Давайте ранжируем документы по их частоте терма (заметьте, что здесь и в области информационного поиска в целом «частота» означает просто количество, а не количество, делённое на что‑то, как в физике):

5. All dogs <b>like</b> walking, but mine doesn't <b>like</b>. It's <b>like</b> so weird | tf = 3
2. Cats and dogs do not <b>like</b> each other, but my cat does <b>like</b> dogs | tf = 2
1. My dog doesn't <b>like</b> all my pets, but me and my wife do love them all. A dog cannot be a cat lover | tf = 1
4. Not all cats <b>like</b> walking, but some cats do | tf = 1
3. Walking a dog is a good start of the day | tf = 0

Это решает проблему, теперь документы №5 и №2 находятся в самом верху.

Но теперь попробуем другой запрос — 'my day':

1. <b>My</b> dog doesn't like all <b>my</b> pets, but me and <b>my</b> wife do love them all. A dog cannot be a cat lover | tf = 3
2. Cats and dogs do not like each other, but <b>my</b> cat does like dogs | tf = 1
3. Walking a dog is a good start of the <b>day</b> | tf = 1
4. Not all cats like walking, but some cats do | tf = 0
5. All dogs like walking, but mine doesn't like. It's like so weird | tf = 0

Документы №1 и №2 получают высшие позиции, но правильно ли это? Они ничего не говорят о «day», только о «my»: мои питомцы, моя жена, мой кот — это может быть важно для запроса, но, скорее всего, нет. Документ №3 получает более низкую позицию, хотя, кажется, он самый релевантный. Как поднять его выше?

Подумайте, что же так отличается в «my» по сравнению с «day» и другими словами. «Day» кажется гораздо более специфичным, тогда как «my» может относиться к практически чему угодно, и в документах «my» встречается гораздо чаще, чем «day» и другие более специфичные термы. Здесь вступает в игру «частота документа» — ещё одна важная часть формулы и второй краеугольный камень взвешивания термов.

В 1972 году Кэрен Спэрк Джонс, британский учёный‑компьютерщик, сказала в одной из своих академических статей: "the exhaustivity of a document description is the number of terms it contains, and the specificity of a term is the number of documents to which it pertains".

Мы уже рассмотрели первую часть этого, теперь посмотрим, как изменится порядок документов, если посчитаем вторую.

Вес = частота терма * (количество документов / частота документа)

Запрос: 'my day'.

«My» встречается в 2 документах, «day» — только в одном, поэтому IDF (обратная частота документа) для «my» равна 5 (общее количество документов) / 2 = 2,5, а для «day» — 5/1 = 5.

1. <b>My</b> dog doesn't like all <b>my</b> pets, but me and <b>my</b> wife do love them all. A dog cannot be a cat lover
Weight = 3(tf of 'my') * 2,5(idf of 'my') + 0(tf of 'day') * 5 (its idf) = 7,5
3. Walking a dog is a good start of the <b>day</b>
Weight = 0 * 2,5 + 1 * 5 = 5
2. Cats and dogs do not like each other, but <b>my</b> cat does like dogs
Weight = 2,5
4. Not all cats like walking, but some cats do
Weight = 0
5. All dogs like walking, but mine doesn't like. It's like so weird
Weight = 0

С помощью IDF мы могли поднять релевантный документ «Walking a dog is a good start of the day» на одну позицию выше, но он всё равно не находится в самом верху. В чём причина? Потому что «my» встречается слишком часто, что перевешивает важность IDF «day». Как решить эту проблему? Нам нужно что‑то, что уменьшит вклад TF. За годы было предложено множество вариантов нормализации TF, от простого log(TF) до так называемой «кривой насыщения частоты терма». Для простоты возьмём логарифмический вариант.

Вес = log(1+TF) * (N/df)

Вся идея логарифмического сглаживания по сравнению с линейной функцией состоит в том, что чем больше аргумент, тем медленнее он растёт, т.е. он быстро растёт для небольших x и медленнее для больших x. «1+x» в функции требуется, чтобы не было 0 в аргументе при частоте терма = 0, поскольку log(0) не определён, а log(0+1) = 0, что именно то, что нам нужно для tf=0.

Посмотрим, решает ли это проблему:
Запрос: 'my day'.

3. Walking a dog is a good start of the <b>day</b>
Weight = log(1+0) * 2,5 + log(1+1) * 5 = 0 + 3,47 = 3,47
1. <b>My</b> dog doesn't like all <b>my</b> pets, but me and <b>my</b> wife do love them all. A dog cannot be a cat lover
Weight = log(1+3) * 2,5 + log(1+0) * 5 = 3,47 + 0 = 3,47
2. Cats and dogs do not like each other, but <b>my</b> cat does like dogs
Weight = 1,73
4. Not all cats like walking, but some cats do
Weight = 0
5. All dogs like walking, but mine doesn't like. It's like so weird
Weight = 0

Как видим, самый релевантный документ наконец‑то оказался на 1‑й позиции, но он делит её с другим документом с тем же весом 3,47. Правильно ли это или нет? Это сложный вопрос, поскольку мы никогда не знаем наверняка, что релевантно для запрашивающего. Есть шанс, что задав запрос «my day», пользователь сочтёт релевантным и второй документ, поскольку он даёт ряд фактов для «my», тогда как первый документ говорит только об одном факте для «day». Поэтому вполне справедливо, что они получили одинаковый вес.

И из‑за этой неопределённости, вероятно, в поисковых системах обычно возвращают не один результат, а некоторое количество: 10 или 20 или другое, позволяя пользователю самому принять окончательное решение.

Заключение

В этой статье я вкратце показал эволюцию мышления над формулой взвешивания TF‑IDF, что доказывает её работоспособность и важность каждого её компонента.

Существует продолжение TF-IDF, называемое BM25, которое основано в частности на ранее упомянутой 'term frequency saturation curve' и использует более вероятностные подходы к определению формулы взвешивания (помните, что мы никогда не знаем, что действительно релевантно, поэтому и применяем вероятностный подход). В целом это всё ещё TF-IDF (+ нормализация по длине документа), но его корни совершенно другие. Это будет рассмотрено в отдельной статье. Оставайтесь с нами и подпишитесь на наши рассылки, чтобы не пропустить это.