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

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

История [ править ]

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

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

Алгоритм Google PageRank был разработан в 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, то точность определяется как:

{\text{Precision}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{O}}\}|}}

Напомним [ править ]

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

{\text{Recall}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{I}}\}|}}

Оценка F1 [ править ]

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

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

Алгоритм ранга страницы [ править ]

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

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 использует анализ ссылок для анализа релевантности страниц, но работает только с небольшими наборами подграфов (а не со всем веб-графом), а также зависит от запроса. Подграфы ранжируются в соответствии с весами в хабах и авторитетных источниках, где выбираются и отображаются страницы с самым высоким рейтингом. ^[15]

См. также [ править ]

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

Ссылки [ править ]

^ Пикколи, Габриэле; Пиньи, Федерико (июль 2018 г.). Информационные системы для менеджеров: с кейсами (Изд. 4.0). Проспект Пресс. п. 28. ISBN 978-1-943153-50-3 . Проверено 25 ноября 2018 г.
^ Могоци, IC «Кристофер Д. Мэннинг, Прабхакар Рагхаван и Хинрих Шютце: Введение в поиск информации: Издательство Кембриджского университета, Кембридж, Англия, 2008, 482 стр., ISBN: 978-0-521-86571-5» . Информационный поиск . 13 (2): 192–195. дои : 10.1007/s10791-009-9115-y . ISSN 1386-4564 . S2CID 31674042 .
^ «Что такое поиск информации?» . Гики для Гиков . 2020-07-02 . Проверено 02 марта 2022 г.
^ «Алгоритм поиска и система ранжирования Google — Поиск Google» . www.google.com . Проверено 02 марта 2022 г.
^ «Ученый нашел алгоритм PageRank 1940-х годов» . Обзор технологий Массачусетского технологического института . Проверено 02 марта 2022 г.
^ Пински, Габриэль; Нарин, Фрэнсис (1976). «Влияние цитируемости на журнальные совокупности научных публикаций: Теория с применением к физической литературе» . Обработка информации и управление . 12 (5): 297–312. дои : 10.1016/0306-4573(76)90048-0 .
^ «Что такое функции поисковой выдачи?» . www.accuranker.com . 28 марта 2019 г. Проверено 02 марта 2022 г.
^ Франческе, Массимо (17 февраля 2010 г.). «Ученый нашел алгоритм PageRank 1940-х годов» . www.technologyreview.com.
^ Датта, Джойдип (16 апреля 2010 г.). «Рейтинг в информационном поиске» (PDF) . Департамент компьютерных наук и инженерии Индийского технологического института. п. 7 . Проверено 25 апреля 2019 г.
^ Черепаха, Ховард Р.; Крофт, В.Брюс (1992). «Сравнение моделей текстового поиска» . Компьютерный журнал . 35 (3). ОУП: 279–290. дои : 10.1093/comjnl/35.3.279 .
^ Хартер, Стивен П. (1 июля 1984 г.). «Введение в современный поиск информации (Джерард Солтон и Майкл Дж. МакГилл)» . Образование для информации . 2 (3): 237–238. дои : 10.3233/EFI-1984-2307 .
^ Чу, Х. Представление и поиск информации в эпоху цифровых технологий. Нью-Дели: Публикация Ess Ess.
^ Г.Чоудхари. Введение в современный поиск информации. Издательство Фасет.
^ Мэннинг, Кристофер; Рагхаван, Прабхакар; Шютце, Хинрих. Оценка ранжированных результатов поиска . Издательство Кембриджского университета.
^ Танасе, Ракула; Раду, Ремус (16 апреля 2010 г.). «Лекция №4: Алгоритм HITS — хабы и авторитеты в Интернете» .

[1] Пикколи, Габриэле; Пиньи, Федерико (июль 2018 г.). Информационные системы для менеджеров: с кейсами (Изд. 4.0). Проспект Пресс. п. 28. ISBN 978-1-943153-50-3 . Проверено 25 ноября 2018 г.

[2] Могоци, IC «Кристофер Д. Мэннинг, Прабхакар Рагхаван и Хинрих Шютце: Введение в поиск информации: Издательство Кембриджского университета, Кембридж, Англия, 2008, 482 стр., ISBN: 978-0-521-86571-5» . Информационный поиск . 13 (2): 192–195. дои : 10.1007/s10791-009-9115-y . ISSN 1386-4564 . S2CID 31674042 .

[3] «Что такое поиск информации?» . Гики для Гиков . 2020-07-02 . Проверено 02 марта 2022 г.

[4] «Алгоритм поиска и система ранжирования Google — Поиск Google» . www.google.com . Проверено 02 марта 2022 г.

[5] «Ученый нашел алгоритм PageRank 1940-х годов» . Обзор технологий Массачусетского технологического института . Проверено 02 марта 2022 г.

[6] Пински, Габриэль; Нарин, Фрэнсис (1976). «Влияние цитируемости на журнальные совокупности научных публикаций: Теория с применением к физической литературе» . Обработка информации и управление . 12 (5): 297–312. дои : 10.1016/0306-4573(76)90048-0 .

[7] «Что такое функции поисковой выдачи?» . www.accuranker.com . 28 марта 2019 г. Проверено 02 марта 2022 г.

[8] Франческе, Массимо (17 февраля 2010 г.). «Ученый нашел алгоритм PageRank 1940-х годов» . www.technologyreview.com.

[9] Датта, Джойдип (16 апреля 2010 г.). «Рейтинг в информационном поиске» (PDF) . Департамент компьютерных наук и инженерии Индийского технологического института. п. 7 . Проверено 25 апреля 2019 г.

[10] Черепаха, Ховард Р.; Крофт, В.Брюс (1992). «Сравнение моделей текстового поиска» . Компьютерный журнал . 35 (3). ОУП: 279–290. дои : 10.1093/comjnl/35.3.279 .

[11] Хартер, Стивен П. (1 июля 1984 г.). «Введение в современный поиск информации (Джерард Солтон и Майкл Дж. МакГилл)» . Образование для информации . 2 (3): 237–238. дои : 10.3233/EFI-1984-2307 .

[12] Чу, Х. Представление и поиск информации в эпоху цифровых технологий. Нью-Дели: Публикация Ess Ess.

[13] Г.Чоудхари. Введение в современный поиск информации. Издательство Фасет.

[14] Мэннинг, Кристофер; Рагхаван, Прабхакар; Шютце, Хинрих. Оценка ранжированных результатов поиска . Издательство Кембриджского университета.

[15] Танасе, Ракула; Раду, Ремус (16 апреля 2010 г.). «Лекция №4: Алгоритм HITS — хабы и авторитеты в Интернете» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]