Поиск и семантическая революция XXI века
Данила Корнев – ИТ-специалист, стартапер, визионер и просто хороший человек – делится с читателями ms4press-информацией о развитии технологий поиска информации в Интернете.
Чуть более 20 лет тому сэр Тим Бернерс-Ли, тогда еще молодой английский ученый, работал в Европейской лаборатории по ядерным исследованиям CERN. В 1989 году он предложил глобальный гипертекстовый проект, ныне известный как Всемирная паутина. Ключевой особенностью этого проекта стала возможность связывания различных документов между собой посредством так называемых гиперссылок. Гиперссылки могли вести на различные части документа и в то же время вести пользователя к документам, размещенным на совершенно других компьютерах.
Одной из важнейших задач, вставших перед учеными, стал поиск необходимой информации, рассредоточенной по всему миру.
Первым и по-своему простейшим способом нахождения информации стала система ручного упорядочивания в виде каталогов (e.g., Yahoo Sites). Преимуществом системы был ручной отбор ссылок модераторами и их категоризация (присвоение той или иной категории заданной ссылке на тот или иной документ). В преимуществе этой системы лежал и ее фатальный недостаток – из-за ускоряющегося роста объемов цифровой информации поддержание ручной обработки ссылок стало все менее реалистичной задачей.
Второй способ нахождения информации – анализ текста. Для ввода текстовой информации необходимо сравнить текстовый запрос, введенный пользователем, с текстом страниц, ссылки на которые сохранены в поисковой системе. У этого подхода существует масса недостатков, один из которых – вопрос ранжирования полученных результатов. К примеру, если ввести слово «контакт», как именно следует трактовать это слово? Означает ли оно контакт человека в адресной книжке? Или же речь идет о научно-фантастическом фильме, созданном на основе одноименного произведения знаменитого астронома Карла Сагана? Или же, наконец, речь идет об элементе электронной микросхемы? Конечно же, пользователь волен уточнить запрос, добавив одно или более дополнительных слов, но в этом случае задача усложняется – как далеко эти слова должны находиться в тексте друг от друга?
Наиболее удачным способом ранжирования информации на конец XX века стала реализация алгоритма PageRank. Молодые ученые Ларри Пейдж и Сергей Брин заметили, что в научной литературе можно определить наиболее качественные работы по количеству их цитирований. Если применить этот подход для Интернета, где одни веб-страницы ссылаются на другие, то те страницы, на которые ссылается большее количество других веб-страниц, и следует показать первыми в списке выдачи результатов. Реализация этой идеи позволила молодым ученым основать мультмиллиардный бизнес – Google, но PageRank как подход для ранжирования результатов поиска также обладает рядом недостатков. Один из ключевых недостатков – низкая эффективность системы при поиске непопулярных информационных источников – так называемый long tail, так как алгоритм ранжирования PageRank будет давать низкий rank для таких ресурсов и пользователю потребуется просмотреть достаточно много результатов поиска, чтобы найти искомую страницу.
Над решением проблемы более эффективного способа ранжирования поисковых результатов бьются ученые во многих государственных и частных исследовательских лабораториях.
И одна из больших трудностей, с которой они столкнулись, – задача определения смысла поискового запроса, сделанного пользователем, вкупе с задачей получения смысла документов, по которым идет поиск. Несмотря на то что технологии получения, структурирования и анализа данных сделали достаточно большие шаги на пути к определению смысла информации, в начале 2000-х их возможностей было недостаточно для решения поставленной задачи.
Одно из таких решений – специальное тегирование веб-страниц, позволяющее внести объяснения или уточнения упоминаемых в тексте терминов. Разработку этой концепции, названной Семантической паутиной (Semantic Web), также предложил сэр Тим Бернерс-Ли. Одна из ключевых идей – описание информации в виде так называемых троек (triples). Каждая тройка – это высказывание вида субъект-предикат-объект (e.g., «рыбак ловит рыбу», где субъектом служит «рыбак» как действующее лицо, предикатом – глагол «ловит», описывающий действие субъекта, и, наконец, объектом действия является «рыба»). Используя комбинации троек, можно построить достаточно сложные конструкции, позволяющие наделить смыслом тексты веб-страниц. К сожалению, не все идеи принимаются одинаково хорошо, и, невзирая на растущую среди предпринимателей и ученых популярность этой концепции, ее применение не стало стандартом де-факто для современного Интернета.
Новую надежду на решение проблемы получения смысла как документов, так и самого текстового запроса дают технологии определения смысла слов, фраз и текстов. О некоторых из этих технологий, разработанных в стенах Microsoft и Microsoft Research, будет рассказано далее.
Powerset, Bing, Microsoft Semantic Engine & SQL Server Semantic Search
В середине 2007 года в стенах Microsoft появился новый проект, известный как MicrosoftSemanticEngine. Целью данного проекта стало ни много ни мало решение проблемы определения смысла с целью создания более эффективных инструментов для определения контекста поискового запроса и получения осмысленных рекомендаций. С другой стороны, над этими же задачами работали специалисты компании Powerset (позднее ставшие частью Microsoft) и разработчики и исследователи из группы Bing (поисковик Microsoft).
Чтобы понять суть этих задач, рассмотрим следующий пример. Допустим, пользователь ввел запрос «отдых в Турции». Обычный поисковый запрос с помощью технологии полнотекстового поиска вкупе с ранжированием с помощью PageRank предложит веб-страницы, где в тексте один и более раз встречается сочетание слов «отдых в Турции» в виде фразы или и в виде отдельных, но недалеко стоящих друг от друга слов. В данном случае достаточно полезным и эффективным источником информации являются личные впечатления людей, уже отдохнувших в Турции. Обычно эти впечатления сохраняются в виде текстовых заметок в блогах или в социальных сетях, и, конечно же, вполне может быть, что текстовый запрос не будет включать в себя либо слово «отдых», либо «Турция» (но включит в себя название конкретного курорта, скажем, «Алания» или «Кемер»). В случае использования традиционного подхода такие веб-страницы не попадут в результаты поиска, и пользователь не сможет узнать, например, о том, что в городе Алания есть замечательная старинная пиратская база, а Кемер в древности мог быть городом химеры, с которой столкнулся герой греческого эпоса Одиссей, а значит, пропустит интересные факты об этих местах.
Но если бы компьютер мог понять, что под словами «отдых в Турции» пользователь имеет в виду именно «отдых» и именно «в Турции», то в результаты поиска попали бы веб-страницы с впечатлениями отдыхавших в Кемере и Алании туристов, которые не написали в своих путевых заметках, что у них был именно «отдых в Турции». То есть для этого нужно понять, что слово «Турция» означает одноименную страну, и в этом случае поисковое поле можно было ограничить документами, где так или иначе упомянуты географические объекты, находящиеся внутри «Турции».
Общий подход к определению смысла слова называется word sense disambiguation (WDS). Рассмотрим применение этого подхода в случае со словом «Турция». На английском языке слово «Турция» может означать страну в политическом, экономическом, туристическом, историческом и прочих контекстах и в то же время означать «индейка». Таким образом, имея лишь одно слово, вероятность того, что пользователь подразумевал слово «Турция» будет, в общем, равна вероятности того, что пользователь подразумевал «индейку». Действительно, если воспользоваться поиском Bing по этому слову, то можно увидеть, что разные понимания этого слова дают совершенно различные результаты.
1. Первым результатом поиска является выдача энциклопедической статьи по данной теме.
2. В связи с тем, что данный поиск был выполнен на английском языке от имени пользователя, зарегистрированного в США, второй результат выдачи – это страница, посвященная данной стране на сайте Правительства США.
3. Третий результат посвящен поиску релевантных изображений. Заметьте, что представлены как фотографии птиц, так и карты страны.
4. Четвертый результат посвящен последним новостям из Турции.
5. Пятый результат посвящен другому трактованию слова «Turkey» – «индейка», и снова идет ссылка на соответствующую страницу Википедии.
6. Шестой результат посвящен политической статье, давая последние политические новости об этой стране.
7. Седьмой результат дает представление о Турции как о стране для туристов, давая короткие ссылки на карту, информацию об авиарейсах и местных достопримечательностях.
Как можно заметить, подход word sense disambiguation работает достаточно неплохо в случае с одним словом. Одной из реализаций данной идеи является технология, разработанная в компании Powerset и последовательно развитая в рамках поискового интерфейса Bing, тем самым став естественной частью системы.
Другой подход, используемый для определения смысла тех или иных объектов, называется phrase sense disambiguation. В своей работе «Смысл и значение» современный ученый Г. Фреге пишет о том, что не только слово, но и предложение имеет смысл и значение. Эта задача отличается от предыдущей. В частности, в отличие от слова предложение может содержать мысли, которые не выражены в нем напрямую. Например, фраза «Альфред еще не пришел» содержит косвенное указание на то, что прихода Альфреда ожидают, причем это указывается косвенно.
Существует несколько различных способов определения смысла и схожести смысла фраз. Одним из таких подходов является так называемый latent semantic indexing, или LSI. Данный подход позволяет не только определять ключевые слова в документах, но также сравнивать различные документы друг с другом на предмет схожести частоты упоминания этих ключевых слов. Считается, что документы семантически (по смыслу) похожи, если частота использования тех или иных ключевых слов у них более или менее одинакова, в противном случае считается, что документы не являются похожими друг на друга. Примером высокоэффективной реализации данного подхода является алгоритм SQL Server Semantic Search, разработанный в рамках проекта Microsoft Semantic Engine и ставший частью Microsoft SQL Server 2012. В данном алгоритме используются сложные статистические языковые модели. В отличие от базового подхода в данном случае слова из предоставленного пользователем документа сравниваются с существующими статистическими данными о среднем распределении этих же слов в документах, после чего выделяются те из них, которые упоминаются в этом документе чаще, чем обычно. Затем применяется исходный подход для определения схожести между документами.
Другой подход опирается на более сложную идею, сформулированную другим современным ученым Л. Витгейнштейном, о том, что одно и то же предложение может играть разную роль в зависимости от ситуации, то есть быть приказом, просьбой, объяснением, описанием и т.д. Иными словами, фраза сама по себе задает некоторый контекст. В то же время, абзац, в котором находится эта статья, также может задавать контекст, что позволяет определить контекст этой фразы. Одним из примеров реализации данной задачи являются труды ученого Сильвиу-Петру Кукерцана из Microsoft Research, разработавшего технологию Concept Extraction. В качестве источника первоначальных знаний используется Википедия. Этот подход, пожалуй, наиболее сложный из описанных выше, так как он включает в себя такие элементы и параметры, как ключевые термины и понятия из Википедии (большинство статей в Википедии связаны с той или иной сущностью/концептом), их принадлежность к тому или иному классу сущностей, если эта информация доступна («человек», «географическое место», «организация» или «другое»), их формы (слова, используемые для обозначения этих сущностей в тексте), контекстные признаки (слова, наиболее часто употребляемые вместе с этими сущностями) и, наконец, теги «тем» (к которым относятся данные сущности). Результаты применения данной технологии как на новостных материалах, так и на данных из Википедии показали уровень точности в 91% и 88% соответственно.
Как в случае с технологиями Powerset, Bing и SQL Server Semantic Search, подход Сильвиу-Петру Кукерцана делает еще один достаточно важный шаг на пути к определению компьютером смысла данной ему информации.
