В 1958 году в своей статье «Автоматическое создание аннотаций» Ханс Питер Лун предположил, что «частота встречаемости слова в статье является мерой значимости слова», что до сих пор, вероятно, является одной из наиболее фундаментальных теорий в Информационном Поиске и в той или иной степени используется во всех известных поисковых системах, начиная с глобальных поисковиков типа Google и Yahoo и заканчивая кастомными решениями типа ElasticSearch и Manticore Search.

Значимость предположения Луна невозможно переоценить, и многие дальнейшие научные исследования в области Информационного Поиска основывались на нём, хотя и не во всех из них упомянута его работа. Вероятно потому, что со временем это стало аксиомой. В этой статье мы попытаемся показать на конкретных простых примерах как TF (“term frequency” - “частота термина”), и его противовес IDF (“inverse document frequency” - “обратная частота документа”) влияют на качество поиска. Для примера возьмем 5 документов:

1. Игра может длиться до истечения игрового времени, до открытия последней карты или до того момента, когда в игре остается только один участник.
2. Качественно нарисованные карты, на которых были изображены все особенности местности, имели тогда огромное значение для  путешественников.
3. Напротив нас висели старые карты города, и, глядя на эти карты, можно было проследить динамику его развития вплоть до начала нынешнего века.
4. Нота - это графическое обозначение звука музыкального произведения, один из основных символов современной музыкальной нотации.
5. У нас вы можете приобрести как мелкомасштабные карты, так и карты более крупных масштабов по самым низким ценам.

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

Пусть вес документа = 1, если в нем содержится слово из запроса, иначе вес = 0

Запрос: «карты».

Обратите внимание: мы не знаем, что именно подразумевает слово «карты» в запросе - «игровые карты» или же «географические карты». Итак, что мы можем сделать, чтобы отранжировать документы? Первое, что приходит на ум - это то, что если документ вообще не содержит слова «карты», то, вероятно, он наименее релевантен. Таким образом, порядок ранжирования может быть следующим:

1. Игра может длиться до истечения игрового времени,  до открытия последней <b>карты</b> или до того момента, когда в игре остается только один участник.
2. Качественно нарисованные <b>карты</b>, на которых были изображены все особенности местности, имели тогда огромное значение для  путешественников.
3. Напротив нас висели старые <b>карты</b> города, и, глядя на эти <b>карты</b>, можно было проследить динамику его развития вплоть до начала нынешнего века.
5. У нас вы можете приобрести как мелкомасштабные <b>карты</b>, так и <b>карты</b> более крупных масштабов по самым низким ценам.
4. Нота - это графическое обозначение звука музыкального произведения, один из основных символов современной музыкальной нотации.

Мы поместили документ №4 в самый конец, так как он не содержит слова «карты». Порядок следования остальных документов остался без изменений, поскольку слово «карты» содержится в каждом из них. Достаточно ли качественно такое ранжирование? Не факт, потому что среди первых 4 документов есть 2 (# 3 и # 5), которые выглядят более релевантными, поскольку в них содержится больше информации, относящейся к нашему поисковому термину «карты» (помните, что нам не известно, какие именно «карты» имеются в виду в запросе), но они не входят в топ-2 поисковой выдачи. Что делать?

Вес = частота термина.

Запрос: «карты».

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

3. Напротив нас висели старые <b>карты</b> города, и, глядя на эти <b>карты</b>, можно было проследить динамику его развития вплоть до начала нынешнего века.  | TF = 2
5. У нас вы можете приобрести как мелкомасштабные <b>карты</b>, так и <b>карты</b> более крупных масштабов по самым низким ценам.  | TF = 2
1. Игра может длиться до истечения игрового времени,  до открытия последней <b>карты</b> или до того момента, когда в игре остается только один участник.  | TF = 1
2. Качественно нарисованные <b>карты</b>, на которых были изображены все особенности местности, имели тогда огромное значение для  путешественников.  | TF = 1
4. Нота - это графическое обозначение звука музыкального произведения, один из основных символов современной музыкальной нотации.   | TF = 0

Проблема решена? Теперь документы № 3 и № 5 находятся в самом верху. Но давайте теперь попробуем задать другой запрос - «Нота до»:

1. Игра может длиться <b>до</b> истечения игрового времени,  <b>до</b> открытия последней карты или <b>до</b> того момента, когда в игре остается только один участник.  | TF = 3
3. Напротив нас висели старые карты города, и, глядя на эти карты, можно было проследить динамику его развития вплоть до начала нынешнего века.  | TF = 1
4. <b>Нота</b> - это графическое обозначение звука музыкального произведения, один из основных символов современной музыкальной нотации.  | TF = 1
2. Качественно нарисованные карты, на которых были изображены все особенности местности, имели тогда огромное значение для  путешественников. | TF = 0
5. У нас вы можете приобрести как мелкомасштабные карты, так и карты более крупных масштабов по самым низким ценам.  | TF = 0

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

Давайте подумаем, чем же так отличает слово «до» от слова «нота» и других слов. Слово «нота» кажется гораздо более специфичным, тогда как «до» может использоваться буквально везде, и в документах «до» будет встречаться гораздо чаще, чем «нота» и другие более конкретные термины. Отсюда появляется понятие «документная частота» - еще одна важная часть формулы TF-IDF и второй краеугольный камень для определения весов терминов.

В 1972 году Карен Спарк Джонс, британский ученый в области информатики, писала в одной из своих научных работ: «полнота описания документа определяется количеством терминов, которые он содержит, а специфичность термина - количеством документов, в которых он встречается». Мы уже использовали первую часть этого утверждения, давайте теперь посмотрим, как изменится порядок документов в результатах поиска, если мы учтем и вторую часть.

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

Запрос: «Нота до».

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

1. Игра может длиться <b>до</b> истечения игрового времени, <b>до</b> открытия последней карты или <b>до</b> того момента, когда в игре остается только один участник. Вес = 3 (tf для 'до') * 2,5 (idf для 'до') + 0 (tf для 'нота') * 5 (idf для 'нота') = 7,5
4. <b>Нота</b> - это графическое обозначение звука музыкального произведения, один из основных символов современной музыкальной нотации. Вес = 0  * 2,5 + 1 * 5 = 5
3. Напротив нас висели старые карты города, и, глядя на эти карты, можно было проследить динамику его развития вплоть <b>до</b> начала нынешнего века. Вес = 1  * 2,5 + 0 * 5 = 2,5
2. Качественно нарисованные карты, на которых были изображены все особенности местности, имели тогда огромное значение для  путешественников. Вес = 0  * 2,5 + 0 * 5 = 0
5. У нас вы можете приобрести как мелкомасштабные карты, так и карты более крупных масштабов по самым низким ценам. Вес = 0  * 2,5 + 0 * 5 = 0

С помощью IDF нам удалось поместить релевантный документ 4 на одну позицию выше, но он все еще не на самом верху. В чем причина? Слово «до» встречается слишком часто, что перевешивает важность IDF для слова «нота». Как мы можем решить этот вопрос? Нам нужно что-то, что снизит вклад TF. За прошедшие годы было предложено и исследовано много вариантов нормализации TF, от просто логарифмирования до так называемой «кривой насыщения частоты терминов». Для простоты давайте возьмем логарифмический вариант.

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

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

Посмотрим, решит ли это нашу проблему:
Запрос: «нота до».

4. <b>Нота</b> - это графическое обозначение звука музыкального произведения, один из основных символов современной музыкальной нотации. Вес = log(1+0) * 2,5 + log(1+1) * 5 = 0 + 3,47 = 3,47
1. Игра может длиться <b>до</b> истечения игрового времени,  <b>до</b> открытия последней карты или <b>до</b> того момента, когда в игре остается только один участник. Вес = log(1+3) * 2,5 + log(1+0) * 5 = 3,47 + 0 = 3,47
3. Напротив нас висели старые карты города, и, глядя на эти карты, можно было проследить динамику его развития вплоть <b>до</b> начала нынешнего века. Вес = log(1+1) * 2,5 + log(1+0) * 5 = 1,73
2. Качественно нарисованные карты, на которых были изображены все особенности местности, имели тогда огромное значение для  путешественников. Вес = log(1+0)  * 2,5 + log(1+0) * 5 = 0 + 0 = 0
5. У нас вы можете приобрести как мелкомасштабные карты, так и карты более крупных масштабов по самым низким ценам. Вес = log(1+0)  * 2,5 + log(1+0) * 5 = 0 + 0 = 0

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

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

Заключение

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

В дальнейшем TF-IDF развилась в разных направлениях, наиболее известное её продолжение - BM25, в основе которой лежат, в частности, ранее упомянутый термин «кривая насыщения частоты термина», и совсем другой - вероятностный подход к заданию весовой формулы (еще раз, помните, что мы никогда не знаем, что в действительности является релевантным для пользователя, отсюда и вероятностный подход). В целом, сутью BM25 по-прежнему является TF-IDF (+ нормализация с учетом длины документа), но предпосылки у BM25 совершенно иные. Мы осветим это в другой статье. Подписывайтесь на нашу рассылку, чтобы ничего не пропустить.