TF-IDF в двух словах

Опубликовано: Apr 09, 2019
Автоперевод: TF-IDF in a nutshell

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

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

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

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

1. Моя собака не любит всех моих домашних животных, но я и моя жена любим их всех. Собака не может быть любителем кошек
2. Кошки и собаки не любят друг друга, но моя кошка любит собак
3. Выгуливать собаку - хорошее начало дня
4. Не все кошки любят гулять, но некоторые кошки любят

5. Все собаки любят гулять, но моя не любит. Это так странно

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

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

Запрос: ‘нравится’.
Обратите внимание, что нам не известно, что именно подразумевается под ‘нравится’ в запросе: нравится, как ‘А похож на B’ или ‘Мне нравится что-то’. И так, что мы можем сделать для ранжирования документов?
Первое, что приходит на ум, это то, что если документ вообще не содержит слово ‘нравится’, то он, вероятно, менее релевантен. Таким образом, порядок может быть:

1. Моя собака не <b>нравится</b> всем моим питомцам, но я и моя жена любим их всех. Собака не может быть любителем кошек
2. Кошки и собаки не <b>нравятся</b> друг другу, но моя кошка <b>любит</b> собак

4. Не все кошки <b>любят</b> гулять, но некоторые кошки делают
5. Все собаки <b>любят</b> гулять, но моя не <b>нравится</b>. Это <b>так</b> странно
3. Выгуливать собаку - хорошее начало дня

Мы поместили документ #3 в самый конец, так как он не содержит ‘нравится’. Что касается остальных, мы не изменили их порядок, так как все они содержат ‘нравится’. Достаточно ли хороша такая оценка? Я так не думаю, так как среди первых 4 документов есть 2 (#5 и #2), которые, кажется, более релевантны, чем другие, так как предоставляют больше фактов, связанных с запросом ‘нравится’ (помните, мы не знаем, что именно подразумевает ‘нравится’ в запросе), но они не находятся в первых 2. Что мы можем с этим сделать?

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

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

5. Все собаки <b>любят</b> гулять, но моя не <b>нравится</b>. Это <b>так</b> странно | tf = 3
2. Кошки и собаки не <b>нравятся</b> друг другу, но моя кошка <b>любит</b> собак | tf = 2

1. Моя собака не <b>нравится</b> всем моим питомцам, но я и моя жена любим их всех. Собака не может быть любителем кошек | tf = 1
4. Не все кошки <b>любят</b> гулять, но некоторые кошки делают | tf = 1
3. Выгуливать собаку - хорошее начало дня | tf = 0

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

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

1. <b>Мой</b> собака не <b>нравится</b> всем <b>моим</b> питомцам, но я и <b>моя</b> жена любим их всех. Собака не может быть любителем кошек | tf = 3

2. Кошки и собаки не <b>нравятся</b> друг другу, но <b>моя</b> кошка <b>любит</b> собак | tf = 1
3. Выгуливать собаку - хорошее начало <b>дня</b> | tf = 1
4. Не все кошки <b>любят</b> гулять, но некоторые кошки делают | tf = 0
5. Все собаки <b>любят</b> гулять, но моя не <b>нравится</b>. Это так странно | tf = 0

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

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

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

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

Запрос: ‘мой день’.
‘Мой’ встречается в 2 документах, ‘день’ - только в одном, так что IDF (обратная частота документа) ‘моего’ равен 5 (общее количество документов) / 2 = 2,5, ‘день’ - 5/1 = 5.

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

С помощью IDF мы могли поднять соответствующий документ ‘Гулять с собакой - хорошее начало дня’ на одну позицию выше, но он все еще не на самом верху. В чем причина? Дело в том, что ‘my’ встречается слишком часто, что перевешивает важность IDF слова ‘day’. Как мы можем это решить? Нам нужно что-то, что уменьшит вклад TF. На протяжении многих лет было предложено и исследовано много вариантов нормализации TF, от простого log(TF) до так называемой ‘кривой насыщения частоты термина’. Для простоты давайте просто возьмем логарифмический вариант.

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

log Вся идея логарифмического сглаживания в сравнении с линейной функцией состоит в том, что чем выше аргумент, тем медленнее он увеличивается, т.е. он растет быстро для меньших x и медленнее для больших x. ‘1+x’ в функции необходимо, чтобы не было 0 в аргументе для частоты термина = 0, поскольку log(0) неопределен, в то время как log(0+1) равно 0, что именно то, что нам нужно для tf=0.
Давайте посмотрим, решает ли это проблему:
Запрос: ‘my day’.

3. Гулять с собакой - хорошее начало <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

2. Кошки и собаки не любят друг друга, но <b>моя</b> кошка любит собак
Вес = 1,73
4. Не все кошки любят прогулки, но некоторые кошки любят
Вес = 0
5. Все собаки любят гулять, но моя не любит. Это так странно
Вес = 0

Как мы видим, самый релевантный документ наконец-то на 1-й позиции, но он делит ее с другим документом с тем же весом 3,47. Это правильно или нет? Это сложный вопрос, поскольку мы никогда не можем с уверенностью знать, что релевантно для запрашивающего. Есть вероятность, что задавая вопрос ‘my day’, он или она также сочтет второй документ релевантным, поскольку он предоставляет ряд фактов для ‘my’, в то время как 1-й документ упоминает только один факт для ‘day’. Поэтому вполне может быть справедливо, что они получают одинаковый вес.
И из-за этой неопределенности, вероятно, именно поэтому в поисковых системах типично возвращать не единственный результат, а некоторое количество: 10 или 20 или что-то еще, чтобы мы просто позволили пользователю принять окончательное решение самостоятельно.

Заключение

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

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