Рейтинг (поиск информации)

Метод сортировки при поиске информации

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

История

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

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

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

Модели ранжирования

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

Модели IR можно в целом разделить на три типа: булевы модели или BIR, модели векторного пространства и вероятностные модели . ^[9] Различные сравнения между моделями поиска можно найти в литературе (например, ^[10] ).

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

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

Модель векторного пространства

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

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

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

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

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

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

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

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

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

Несколько экспериментов показали, что вероятностная модель может давать хорошие результаты. Однако такие результаты не были достаточно лучше, чем те, которые были получены с использованием булевой или векторной модели. ^{[12] [13]}

Меры оценки

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

Точность

Точность измеряет точность процесса поиска. Если фактический набор соответствующих документов обозначен как I, а извлеченный набор документов обозначен как O, то точность определяется как: $${\displaystyle {\text{Precision}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{O}}\}|}}}$$

Отзывать

Полнота — это мера полноты процесса IR. Если фактический набор соответствующих документов обозначен как I, а извлеченный набор документов обозначен как O, то полнота определяется как: $${\displaystyle {\text{Recall}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{I}}\}|}}}$$

Оценка F1

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

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

Алгоритм ранжирования страниц

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

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

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

Алгоритм HITS

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

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

• Обучение ранжированию : применение машинного обучения к проблеме ранжирования
• Семантический поиск

Ссылки

1. Пикколи, Габриэле; Пиньи, Федерико (июль 2018 г.). Информационные системы для менеджеров: с кейсами (издание 4.0 ред.). Prospect Press. стр. 28. ISBN 978-1-943153-50-3. Получено 25 ноября 2018 г.
2. Mogotsi, IC "Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze: Introduction to information retrieval: Cambridge University Press, Cambridge, England, 2008, 482 pp, ISBN: 978-0-521-86571-5". Information Retrieval . 13 (2): 192–195. doi :10.1007/s10791-009-9115-y. ISSN  1386-4564. S2CID  31674042.
3. "Что такое информационный поиск?". GeeksforGeeks . 2020-07-02 . Получено 2022-03-02 .
4. «Алгоритм поиска и система ранжирования Google — Поиск Google». www.google.com . Получено 2022-03-02 .
5. "Ученый нашел алгоритм PageRank-Type из 1940-х годов". MIT Technology Review . Получено 2022-03-02 .
6. Пински, Габриэль; Нарин, Фрэнсис (1976). «Влияние цитирования на журнальные совокупности научных публикаций: теория с применением к литературе по физике». Обработка информации и управление . 12 (5): 297–312. doi :10.1016/0306-4573(76)90048-0.
7. «Что такое функции SERP?». www.accuranker.com . 2019-03-28 . Получено 2022-03-02 .
8. Франческет, Массимо (17 февраля 2010 г.). «Ученый находит алгоритм типа PageRank из 1940-х годов». www.technologyreview.com.
9. Датта, Джойдип (16 апреля 2010 г.). «Рейтинг в информационном поиске» (PDF) . Кафедра компьютерных наук и инженерии, Индийский технологический институт. стр. 7. Получено 25 апреля 2019 г.
10. Turtle, Howard R.; Croft, W.Bruce (1992). «Сравнение моделей поиска текста». The Computer Journal . 35 (3). OUP: 279–290. doi : 10.1093/comjnl/35.3.279 .
11. Хартер, Стивен П. (1984-07-01). «Введение в современный поиск информации (Джерард Солтон и Майкл Дж. Макгилл)». Образование для информации . 2 (3): 237–238. doi :10.3233/EFI-1984-2307.
12. Чу, Х. Представление и поиск информации в цифровую эпоху. Нью-Дели: Ess Ess Publication.
13. GGChoudhary. Введение в современный информационный поиск. Facet Publishing.
14. Мэннинг, Кристофер; Рагхаван, Прабхакар; Шютце, Хинрих. Оценка ранжированных результатов поиска. Издательство Кембриджского университета.
15. Танасе, Ракула; Раду, Ремус (16 апреля 2010 г.). «Лекция № 4: Алгоритм HITS — концентраторы и авторитеты в Интернете».