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

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

В этой статье я постараюсь наглядно показать на простых примерах, как TF, означающая "частота термина", и ее противоположность 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 похож на B' или 'Мне нравится что-то'. Что мы можем сделать, чтобы ранжировать документы?

Первое, что приходит в голову, что если документ не содержит слова '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'. Достаточно ли хорошо такое ранжирование? Я не думаю, так как среди первых 4 документов есть 2 (#5 и #2), которые кажутся более релевантными, чем остальные, поскольку они предоставляют больше фактов, связанных с термином запроса 'like' (помните, мы не знаем точно, что означает 'like' в запросе), но они не являются top 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 находятся наверху.

Но теперь попробуем другой запрос - 'мой день':

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 получают самые высокие позиции, но правильно ли это? Они ничего не говорят о 'день', только о 'мой': мои питомцы, моя жена, мой кот, что может быть важно с учетом запроса, но скорее всего нет. Документ №3 получает более низкую позицию, хотя кажется наиболее релевантным. Как его можно поднять выше?

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

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

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

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

Запрос: 'мой день'.

'Мой' встречается в 2 документах, 'день' - только в одном, поэтому IDF (обратная частота документа) для 'мой' равна 5 (общее количество документов) / 2 = 2,5, для 'день' - 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 мы смогли поднять релевантный документ 'Прогулка с собакой - хорошее начало дня' на одну позицию выше, но он все еще не на самом верху. В чем причина? Потому что 'мой' встречается слишком часто, что перевешивает важность IDF для 'день'. Как это решить? Нам нужно что-то, что снизит вклад TF. За годы было предложено и исследовано много вариантов нормализации TF - от простого log(TF) до так называемой "кривой насыщения частоты термина". Для простоты возьмем логарифмический вариант.

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

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

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

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. Правильно это или нет? Это сложный вопрос, так как мы никогда точно не знаем, что релевантно для запрашивающего. Есть шанс, что, спрашивая 'мой день', он или она также сочтет релевантным второй документ, поскольку он дает ряд фактов для 'мой', в то время как первый документ говорит только об одном факте для 'день'. Так что вполне может быть справедливо, что они получают одинаковый вес.

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

Заключение

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

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