11 Часть I. Компоненты 14 Глава Компьютерная
жүктеу/скачать 4,29 Mb.
|
nikolaev is mitrenina ov lando tm red prikladnaia i kompiute
- Бұл бет үшін навигация:
- Фильтрация и ранжирование
- Факторы ранжирования
- Оценки релевантности
- Не все слова одинаково полезны
| Точность поиска (precision) показывает, насколько хороши найден- ные документы, она определяется как доля релевантных документов в числе всех найденных.
Полнота поиска (recall) показывает, не остались ли ненайденными полезные документы, она определяется как доля найденных документов в числе всех релевантных документов в коллекции. Нашему гипотетическому библиотечному ученому важна полнота по- иска: он не хочет пропустить ни одной статьи по нужной теме, даже если для этого придется просмотреть пару лишних. Но сегодня нам с вами важнее точность: мы совсем не хотим тратить время на неподходящие страницы и очень часто удовлетворяемся всего одной подходящей. Когда мы заботимся главным образом о полноте, документы в прин- ципе можно выдавать в любом порядке. А вот если приоритетом является точность, то нам очень хочется видеть ранжированную поисковую вы- дачу: чтобы поисковик в первую очередь выдавал те документы, которые считает наиболее релевантными. Если среди первых 100 документов на- ходится 95 релевантных, то точность при такой выдаче равна 95 %. Но если на первых пяти строчках при этом оказались нерелевантные доку- менты, результат поиска может разочаровать. Для оценки поиска нужны совсем другие метрики качества, и их при- думано очень много. В этой статье, к сожалению, не хватит места даже для краткого их обзора, но в качестве отправной точки их изучения можно взять, например, статью [Агеев и др. 2010]. Фильтрация и ранжированиеПользователю нужна точность или полнота, но он в любом случае не хочет просматривать совсем не подходящие документы. Поэтому первое, что должен сделать поисковик, — постараться сразу отбросить такие до- кументы. Их можно отсеивать разными способами. Например, документ точно не подходит, если в нем нет ни одного из слов запроса; уже знако- мый нам инвертированный индекс делает такую проверку очень простой. Этот метод начинает работать хуже и пропускать много лишнего на длин- ных запросах или на запросах с так называемыми стоп-словами (это час- тотные слова вроде союзов или предлогов, которые часто можно выбро- сить без потери содержания запроса). На этот случай есть другие методы. Один из них использует понятие, которое в Яндексе называется кворумом. Оно приблизительно означает «в документе встретилась достаточная доля слов запроса, взвешенных по частотности». Так или иначе, после того как ненужные документы выброшены, ос- тавшиеся нужно упорядочить по предположительной релевантности. Со- временные поисковые системы решают эту задачу методами машинного обучения с учителем. Будем считать, что релевантность (которая, напомним, задана для па- ры <запрос, документ>) — это число, тогда ранжирование сводится к сор- тировке документов по этому числу. Если так, то нам нужна некоторая функция, которая, если ей дать пару запрос-документ, умеет возвращать число. Факторы ранжированияЧтобы программа могла сортировать документы, ей нужны факторы ранжирования (ranking features) — признаки, которые можно извлечь из запроса и/или из документа и которые можно выразить числом. Например, такие: доля слов запроса, встретившихся в документе; доля слов запроса, встретившихся в документе ровно в такой же фор- ме, как в запросе; доля биграмм запроса, встретившихся в документе. Все это примеры текстовых факторов, т. е. таких, которые извлека- ют информацию из текста документа. Но могут быть и нетекстовые фак- торы. Например: веб-документы могут ссылаться друг на друга посредст- вом гиперссылок. Документы, на которые часто ссылаются, нередко бы- вают более качественными (никто же не станет ставить ссылку на плохие документы, думали все, пока кто-то не изобрел торговлю этими ссылками). Самая известный алгоритм, учитывающий ссылочные факторы, называ- ется PageRank [Brin, Page 1998]. Поскольку гиперссылка содержит текст, можно использовать его для расчета факторов: например, смотреть, часто ли встречаются слова запроса в текстах ссылок на данный документ. Можно заметить, что чисто ссылочные факторы вообще не использу- ют информацию о запросе и зависят только от документа. В принципе, таких факторов, которые задают «априорную» релевантность, можно при- думать много: возраст сайта, доля опечаток в тексте документа, доля слов, набранных заглавными буквами, количество смайликов на абзац, да что угодно, лишь бы работало. Еще одна важная разновидность факторов — поведенческие. Поис- ковая система имеет возможность «наблюдать» за тем, что пользователи делают с результатами поиска: сколько документов просматривают, какие именно и как долго, переформулируют ли запрос (если да, то, наверное, по исходному запросу ничего путного не нашлось) и т. п. Нечистые на руку владельцы сайтов, заинтересованные в том, чтобы их документы показывались высоко в поисковой выдаче, постоянно пы- таются «накручивать» любые факторы, включая поведенческие, — и им это иногда удается. Поэтому разработчики поисковиков вынуждены по- стоянно придумывать новые признаки, иначе качество поиска будет быст- ро ухудшаться. Приходится бежать со всех ног, чтобы только остаться на том же месте. К примеру, поиск Яндекса по состоянию на 2015 год ис- пользует порядка тысячи факторов. Для работы некоторых факторов требуется включать дополнительные данные в инвертированный индекс или вообще создавать отдельный ин- декс. Это влечет определенные накладные расходы, которые оправдыва- ются, если фактор улучшает общее качество поиска. Оценки релевантностиФакторы ранжирования — это способ разложить такие сложные объ- екты, как запрос и документ, на простые численные составляющие, по- нятные машине. Но их, очевидно, недостаточно, ведь нужна еще какая-то информация, позволяющая делать выводы о том, какие комбинации значе- ний факторов свидетельствуют о высокой релевантности, а какие нет. Как я уже упоминал, алгоритм ранжирования — это чаще всего обу- чение с учителем. Оно предполагает, что машине нужно показать какое-то количество троек запрос-документ-релевантность, где релевантность уже известна. Эти тройки являются обучающей выборкой — чем их больше, тем лучше. Для их создания можно попросить группу людей оценивать пары запрос-документ: насколько этот документ с их точки зрения реле- вантен данному запросу. Эти люди называются асессорами и, конечно, никто не заставляет их подбирать числа для каждого случая; вместо этого они пользуются шкалой типа «нерелевантный — слабо релевантный — очень релевантный» (на самом деле шкала длиннее), а эти дискретные оценки потом каким-то образом переводятся в число. В итоге получится обучающее множество вместе с оценками, где до- кументы и запросы выражены в виде значений факторов. Дальше остается чисто инженерно-математическая задача: отдать это множество некоему алгоритму, который построит формулу ранжирования. Введение в эти ал- горитмы дано в нашей книге в главе 5 «Машинное обучение в лингвисти- ке». Можно упомянуть также, что алгоритм MatrixNet [Gulin, Karpovich 2009], используемый в Яндексе, основан на деревьях решений и относится к семейству oblivious boosted decision trees. Не все слова одинаково полезныСложные алгоритмы ранжирования с машинным обучением, естест- венно, появились далеко не сразу. До них было предложено множество более простых моделей, причем нельзя сказать, что они совсем уж ушли в прошлое — идеи или даже готовые формулы из них, такие как BM25 [Spärck Jones et al. 2000], вполне пригодны в качестве факторов ранжиро- вания. Одно из известных семейств классических моделей поиска — это векторные модели. Векторное представление — в целом довольно попу- лярный способ работать с разнообразными лингвистическими объектами. В случае с поиском основную идею можно описать так: пусть у нас есть пространство, заданное всеми возможными терминами (возможно, норма- лизованными). Представим каждый документ как вектор в этом простран- стве: значением каждой координаты вектора будем пока считать количест- во употреблений соответствующего термина в этом документе (это модель «мешка слов», когда порядок следования терминов не важен). Далее каж- дый запрос тоже будем представлять как вектор в этом же пространстве. Тогда значение релевантности можно вычислить, например, как косинус угла между вектором запроса V (q) и вектором документа V (d): 𝑠𝑐o𝑟e(𝑞, 𝑑) = (𝑉(𝑞), 𝑉(𝑑)) ‖𝑉(𝑞)‖‖𝑉(𝑑)‖ Рассмотрим немного искусственный пример. Пусть у нас есть микро- коллекция из трех документов и запрос q1 = [разводка мостов петербург]. Документы я запишу сразу в виде векторов частоты терминов:
жүктеу/скачать 4,29 Mb. Достарыңызбен бөлісу:
|