Ранжирование (поиск информации) - Ranking (information retrieval)

Рейтинг запроса - одна из основных проблем в поиск информации ^[1] (IR), научная / инженерная дисциплина, лежащая в основе поисковые системы. Учитывая запрос q и коллекция D документов, соответствующих запросу, проблема заключается в ранжировании, то есть сортировке документов в D в соответствии с некоторым критерием, так что «лучшие» результаты появляются раньше в списке результатов, отображаемом пользователю. Ранжирование с точки зрения поиска информации является важным понятием в информатике и используется во многих различных приложениях, таких как запросы поисковых систем и рекомендательные системы. Большинство поисковых систем используют алгоритмы ранжирования, чтобы предоставлять пользователям точные и релевантные результаты.

История

Понятие рейтинга страниц восходит к 1940-м годам, а идея возникла в области экономики. В 1941 году Василий Леонтьев разработал итерационный метод оценки сектора страны, основанный на важности других секторов, которые поставляли ему ресурсы. В 1965 году Чарльз Хаббелл из Калифорнийского университета в Санта-Барбаре опубликовал методику определения важности людей на основе важности людей, которые их поддерживают.

Габриэль Пински и Фрэнсис Нарин предложили подход к ранжированию журналов. Их правило заключалось в том, что журнал важен, если на него ссылаются другие важные журналы. Джон Кляйнберг, специалист по информатике в Корнелл Университет, разработала почти идентичный подход к PageRank, который назывался гипертекстовым тематическим поиском или HITS, и рассматривал веб-страницы как «центры» и «авторитеты».

Алгоритм Google PageRank был разработан в 1998 году основателями Google Сергеем Брином и Ларри Пейджем и является ключевой частью метода Google для ранжирования веб-страниц в результатах поиска. Все вышеперечисленные методы в чем-то похожи, поскольку все они используют структуру ссылок и требуют итеративного подхода.^[2]

Рейтинговые модели

Функции ранжирования оцениваются различными способами; один из самых простых - определение точность из первых k лучшие результаты для некоторых фиксированных k; например, доля 10 лучших результатов, релевантных в среднем по многим запросам.

IR-модели можно условно разделить на три типа: булевы модели или BIR, модели векторного пространства и вероятностные модели.^[3]

Булевы модели

Логическая модель или ЗБИ - это простая базовая модель запроса, в которой каждый запрос следует базовым принципам реляционной алгебры с алгебраическими выражениями и где документы не выбираются, если они полностью не совпадают друг с другом. Поскольку запрос либо извлекает документ (1), либо не извлекает документ (0), нет методологии для их ранжирования.

Векторная модель пространства

Поскольку логическая модель выбирает только полные совпадения, она не решает проблему частичного совпадения документов. В Векторная модель пространства решает эту проблему, вводя векторы элементов индекса, каждому из которых присвоены веса. Веса варьируются от положительного (если совпадают полностью или в некоторой степени) до отрицательного (если не совпадают или совпадают полностью противоположно), если документы присутствуют. Частота термина - обратная частота документа (tf-idf ) - один из самых популярных методов, где веса - это термины (например, слова, ключевые слова, фразы и т. д.), а размеры - это количество слов в корпусе.

Оценка сходства между запросом и документом может быть найдена путем вычисления значения косинуса между вектором веса запроса и вектором веса документа с использованием подобия косинуса. Требуемые документы могут быть получены путем ранжирования их в соответствии с оценкой сходства и из k документов, которые имеют самые высокие оценки или наиболее релевантны вектору запроса.

Вероятностная модель

В вероятностной модели теория вероятностей использовалась в качестве основного средства для моделирования процесса поиска в математических терминах. Вероятностная модель поиска информации была введена Мароном и Кунсом в 1960 году и далее развита Роберстоном и другими исследователями. Согласно Спаку Джонсу и Уиллетту (1997): Основание для введения вероятностных концепций очевидно: системы IR работают с естественным языком, и это слишком неточно, чтобы система могла с уверенностью утверждать, какой документ будет иметь отношение к конкретному запросу.

Модель применяет теорию вероятности к поиску информации (вероятность возникновения события составляет от 0 до 100 процентов). т.е. в вероятностной модели актуальность выражается в терминах вероятности. Здесь документы ранжируются в порядке уменьшения вероятности релевантности. Он принимает во внимание элемент неопределенности в IR-процессе. то есть неуверенность в том, соответствуют ли документы, полученные системой, заданному запросу.

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

В модели используются различные методы для определения вероятности релевантности запросов и документов. Релевантность в вероятностной модели оценивается по сходству между запросами и документами. Оценка подобия дополнительно зависит от частоты термина.

Таким образом, для запроса, состоящего только из одного термина (B), вероятность того, что конкретный документ (Dm) будет сочтена релевантным, представляет собой соотношение пользователей, которые отправляют термин запроса (B) и считают документ (Dm) релевантным в отношение к количеству пользователей, представивших термин (B). Как представлено в модели Марона и Куна, это может быть представлено как вероятность того, что пользователи, отправляющие определенный термин запроса (B), сочтут отдельный документ (Dm) релевантным.

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

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

^[4]

^[5]

Меры оценки

Наиболее распространенными критериями оценки являются точность, отзывчивость и f-балл. Они вычисляются с использованием неупорядоченных наборов документов. Эти меры должны быть расширены или должны быть определены новые меры, чтобы оценить результаты ранжированного поиска, которые являются стандартными для современных поисковых систем. В контексте ранжированного поиска подходящие наборы извлеченных документов, естественно, задаются первыми k извлеченными документами. Для каждого такого набора значения точности и отзыва могут быть нанесены на график, чтобы получить кривую точности-отзыва.^[6]

Точность

Точность измеряет точность процесса поиска. Если фактический набор соответствующих документов обозначен I, а полученный набор документов обозначен O, то точность определяется следующим образом:

$${displaystyle { ext{Precision}}={frac {|{{ ext{I}}}cap {{ ext{O}}}|}{|{{ ext{O}}}|}}}$$

Отзывать

Отзыв - это мера полноты IR-процесса. Если фактический набор соответствующих документов обозначен I, а извлеченный набор документов обозначен O, то отзыв определяется как:

$${displaystyle { ext{Recall}}={frac {|{{ ext{I}}}cap {{ ext{O}}}|}{|{{ ext{I}}}|}}}$$

Оценка F1

F1 Score пытается объединить точность и отзывчивость. Это гармоническое среднее из двух. Если P - точность, а R - отзыв, тогда оценка F определяется по формуле:

${displaystyle F_{1}=2cdot {frac {mathrm {P} cdot mathrm {R} }{mathrm {P} +mathrm {R} }}}$

Алгоритм Page Rank

В PageRank Алгоритм выводит распределение вероятностей, используемое для представления вероятности того, что человек, случайным образом нажимающий на ссылки, попадет на любую конкретную страницу. PageRank можно рассчитать для коллекций документов любого размера. В нескольких исследовательских работах предполагается, что распределение равномерно распределяется между всеми документами в коллекции в начале вычислительного процесса. Для вычисления PageRank требуется несколько проходов через коллекцию, чтобы скорректировать приблизительные значения PageRank, чтобы они более точно отражали теоретическое истинное значение. Формулы приведены ниже:

${displaystyle PR(u)=sum _{vin B_{u}}{frac {PR(v)}{L(v)}}}$

то есть значение PageRank для страницы ты зависит от значений PageRank для каждой страницы v содержится в наборе B_ты (набор, содержащий все страницы, ссылающиеся на страницу ты), деленное на число L(v) ссылок со страницы v.

HITS алгоритм

Подобно PageRank, HITS использует анализ ссылок для анализа релевантности страниц, но работает только с небольшими наборами подграфов (а не с целым веб-графом) и зависит от запроса. Подграфы ранжируются в соответствии с весами в центрах и органах власти, где выбираются и отображаются страницы с наивысшим рейтингом.^[7]

Смотрите также

• Учимся ранжировать: применение машинное обучение к проблеме ранжирования

Рекомендации

1. Пикколи, Габриэле; Пиньи, Федерико (июль 2018 г.). Информационные системы для менеджеров: с кейсами (Издание 4.0 изд.). Проспект Пресс. п. 28. ISBN  978-1-943153-50-3. Получено 25 ноября 2018.
2. Франческе, Массимо (17 февраля 2010 г.). «Ученый находит алгоритм типа PageRank 1940-х годов». www.technologyreview.com.
3. Датта, Джойдип (16 апреля 2010 г.). «Рейтинг в поиске информации» (PDF). Департамент компьютерных наук и инженерии Индийского технологического института. п. 7. Получено 25 апреля 2019.
4. Чу, Х. Представление и поиск информации в эпоху цифровых технологий. Нью-Дели: Публикация Ess Ess.
5. Г. Г. Чоудхари. Введение в современный поиск информации. Facet Publishing.
6. Мэннинг, Кристофер; Рагхаван, Прабхакар; Schutze, Hinrich. Оценка результатов ранжированного поиска. Издательство Кембриджского университета.
7. Тэнасе, Ракула; Раду, Ремус (16 апреля 2010 г.). «Лекция №4: Алгоритм HITS - хабы и авторитеты в Интернете».