Каждый день мы пользуемся поисковой строкой и видим рекомендации
товаров, услуг или фильмов в интернете. Как устроена эта система
изнутри и очем мы не задумываемся, кликая по ссылке или оставляя
лайк под фотографией? Об устройстве и способностях поисковых и
рекомендательных систем расскажет специалист по
машинномуобучениюСтанислав Протасов.Как работают поисковики и
рекомендацииПредставьте, что вы заходите в отделение банка, чтобы
открыть счет. Для начала вам нужно идентифицироваться. Вы сообщаете
сотруднику банка свое имя, фамилию и номер паспорта. С помощью
имеющейся информации вас находят в базе данных. Ваша личная
информация это ключ, по которому сотрудник банка найдет ваш
банковский профиль. Исходя из ваших данных, можно узнать, как давно
вы являетесь клиентом и имеете ли какие-то задолженности перед
банком. Этот пример самая простая задача точного поиска.Постановку
задачи можно расширить и усложнить. Представьте, что вы ищете
определенный товар в интернет-магазине. На любой из таких площадок
есть фильтры, то есть параметры, по которым вы будете отбирать свой
товар. Вы отмечаете галочкой нужные характеристики, ограничиваете
диапазон цен, выбираете производителя. К примеру, вы хотите найти
смартфон синего цвета за примерно 2025тысяч рублей. Это постановка
задачи по диапазону (range search). Если при поиске вы используете
много критериев, каждый изкоторых обязательно должен быть учтен,это
задача логического поиска (boolean retrieval).После тогокак вы
нашли, купили или не купили нужный товар, в дело вступает
рекомендательная система. Она нужна для того, чтобы показывать вам
подходящие по какому-либо признаку вещи. Вы можете читать книги
определенных авторов, смотреть любимые фильмы или слушать новую
музыку рекомендательная система запоминает ваши предпочтения и
предлагает похожий контент, выводя его на первые строки поисковых
запросов или же сразу показывая их в отдельном блоке интерфейса:
Вам также может понравиться. При этомрекомендательная система будет
опираться не только на ваш единичный выбор. Она устроена намного
сложнее и будет учитывать также ваше местоположение, время суток,
день недели или возраст, если что-либо из этого ей уже известно. Но
даже если о вас известно мало, рекомендательная система все равно
составит ваш пользовательский портрет. Например, используя
музыкальный сервис, вы пролистнете трек, который вам не понравится,
и теперь рекомендательная система не будет предлагать подобную
музыку, а будет показывать то, что понравится вам с наибольшей
вероятностью. Также она будет периодически предлагать новые треки
похожих, неизвестных вам исполнителей, чтобы не надоедала одна и та
же музыка. Так вы проведете гораздо больше времени на данном
ресурсе.Поисковые программы появились раньше рекомендательных, и
функционально они кажутся нам разными. Но с математической точки
зренияэти системы работают практически одинаково. И они стали еще
более похожими сейчас, когда их задача состоит не просто в поиске,
а в предложении контента, лучше всего удовлетворяющего вашу
потребность в информации. Такой контент называют релевантным.Графы,
теория шести рукопожатий и navigable small worldГраф это
математический объект, состоящий из множества вершин (узлов) и
ребер, соединяющих эти вершины. Понятие позволяет модельно
описывать сложные системы, например движение транспорта или
электрические схемы. Основы теории заложил ещеЛеонард Эйлер в 1736
году, но понятие графа ввели позже, лишь в 1878-м. В рамках теории
были предложены типы графов, подходящие для описания различных
явлений. Среди нихрегулярные, случайные, бесконечные, вероятностные
и так далее.При этомрегулярные и случайные две разновидности
графов, которые могут пересекаться (то есть один и тот же
конкретный граф может быть одновременно регулярным и случайным).
Регулярные графы те, в которых каждая вершина связана ребрами ровно
с K другими (K-регулярный граф). Случайные графы строятся для
заранее известного множества вершин, а его ребра создаются
некоторым вероятностным процессом. У каждого типа графов есть свои
особенности и закономерности.Давайте представим, что регулярный
граф это город, где некоторые соседи знакомы между собой. Чтобы
передать сообщение по цепочке знакомств от одного к
другому,потребуется пройти довольно большое расстояние. Если даже
кратчайшая дорога известна, по пути нужно будет сделать несколько
остановок и пересадок. В случайных графах с высокой вероятностью
передача такого сообщения по кратчайшему возможному пути займет
гораздо меньше времени.В 1967году социолог Стэнли Милгрэм провел
серию экспериментов по определению длины кратчайшего пути среди
попарных личных знакомств. В те времена общество было принято
моделировать с помощью регулярных или случайных графов, однако
экспериментального подтверждения для этого не было. Для
исследования Милгрэм выбрал удаленные друг от друга города в США. В
два города он отправил незнакомым между собой людям письма с
информацией об этом эксперименте и человеке из третьего города.
Этот человек являлся конечным звеном в цепочке знакомств, и именно
ему нужно было направить сообщение, используя свои личные
знакомства и связи. Участники передавали письмо от одного адресата
другому, пока конверт не дошел до нужного человека. Оказалось, что
по пути от стартовой до конечной точки письмо в среднем проходило
через шесть рук. Это исследование изначально получило название Мир
тесен, а после стало известнокак Теория шести рукопожатий. Таким
образом, социальный эксперимент показал не только особенности
общества и взаимосвязь людей, но и то, как может работать алгоритм
поиска. Важным открытием с точки зрения математики стало то, что
граф знакомств людей обладает свойствами, не похожими ни на чисто
регулярные, ни на случайные графы. Это какой-то другой, ранее
неизвестный вид графов. На этой основе американские математики
Дункан Ваттс и Стивен Строгац предложили новый тип графов мир
тесен(small world) и показали, как его можно сгенерировать.В 2013
году произошел очередной прорыв в технологиях поисковых и
рекомендательных систем. Российские ученые Юрий Мальков и Дмитрий
Яшунин предложили совместить идею графа мир тесен и метрическое
пространство. Оказалось, чтоэта идея значительно расширяет
возможности поиска. Ученые назвали модель navigable small
world(граф мир тесенс возможностью навигации). Мальков и Яшунин
дополнили модель графа мир тесен,поместили его вершины в
метрическое пространство (условно дали им географические
координаты) и разрешили вычислять расстояние между парами вершин,
даже если они не связаны ребром. Эта комбинация позволила быстрее
находить искомый элементлибо, если искомого элемента нет,
максимально похожие на него элементы.Чтобы понять, как это
работает, представьте, что вы ищете студента третьего курса
Университета Иннополис Ивана Петрова. Вы прилетели в Казань
(длинный перелет), сели в такси и приехали в город (еще60
километров). Далее спросили у местного, где тут университет (в 200
метрах). Зашли в здание, узнали в расписании, где проходят занятия
третьего курса (в 30 метрах от входа). Вошли в аудиторию и спросили
у ближайшего к выходу студента, где тут Иван Петров. Но оказалось,
что такого студента не существует. Однаковы только что увидели всех
его однокурсников, то есть тех, кто наиболее похож на Ивана Петрова
по социальным признакам.Поиск: индексные структуры, векторы и
деревьяПоисковая система ворота в мир интернета. Но мы не можем
искать информацию во всем интернете сразу, потому что он невероятно
велик. Для быстрого поиска потребовалось создать буферные
пространства, в которых хранятся сильно сжатые копии страниц и
файлов. Перебором и сжатием информации занимаются поисковые
роботы(веб-краулеры), которые складывают уменьшенные копии на
сервера поисковых компаний. К разным страницам нужен разный подход,
так как они могут быть статическими или динамическими, как,
например, главная страница соцсетей с новостной лентой, которая
постоянно обновляется, или страницы,формирующиеся специально под
запрос пользователя.
Чтобы находить даже сжатые представления документов среди миллионов
и миллиардов кандидатов, необходимо снабдить их индексными
структурами. Индекс это структура данных, где искомый элемент
сопоставляется с местом его хранения. Типичный пример индекса это
что-то вроде оглавления в книге. Бывает и так, что в конце учебника
вы видите не оглавление, а список терминов и страниц, на которых
они встречаются. Такой индекс называется инвертированным. Он хранит
в себе информацию о том, что определенные слова встречаются на
определенных страницах. Чем больше слов в вашем поисковом запросе,
тем сильнее фильтруются данные и тем точнее результат выдачи.
Индексы помогают быстро находить информацию.А теперь представьте,
что у вас скопилось множество документов, видео, фото и других
файлов. Нужно проиндексировать все ваши данные некоторым
универсальным способом, не зависящим от типа документа. Для этого
можно попробовать представить ваши документы унифицированно, в виде
наборов чисел. Самым популярным способом записи объектов в
современных рекомендательных и поисковых системах является вектор.
Вектор это просто упорядоченный набор чисел, где каждое число
отвечает за определенное свойство документа. Получение векторов
отдельная большая задача. Одни векторные представления можно
получить автоматическим процессом, напримерс помощью машинного
обучения. В этом случае мы не будем знать смысл каждого из чисел в
векторе. Другие представления можно собрать по определенным
правилам, заданным разработчиками. Тогда мы сами определим, какие
признаки важны для объекта. Например, если проиндексировать запись
о человеке, то важным будет знать его возраст, место жительства,
уровень дохода, то есть его социально-демографический профиль.
Поиск в интернете основывается на векторах, представляющих ваш
запрос, предпочтения и контекст.Продолжая тему о структуре данных,
нельзя не упомянуть советских ученых Георгия Адельсона-Вельского и
Евгения Ландиса. В 1962 году они придумали структуру данных под
названием АВЛ-дерево (название было образовано от первых букв
фамилий авторов). Это один из видов двоичных деревьев поиска, где
каждое разветвление (узел) имеет не более двух веток. Важной
особенностью конкретно этого дерева является то, что оно
гарантирует быстрое время поиска элемента вне зависимости от того,
сколько объектов вы добавили, удалили или изменили с момента его
создания. Это свойство деревьев называется
самобалансирующиеся.Принцип работы двоичного дерева поиска наглядно
демонстрирует популярная игра Акинатор 2007 года, где джинн
практически всегда безошибочно отгадывает любого загаданного вами
героя. Представьте, что в мире существует огромное количество
разнообразных персонажей: актеров, ученых или мультгероев. Про
каждого есть та или иная информация, которая разбита по
категориям-признакам. Например, блондин это или брюнет, молодой или
пожилой, женщина или мужчина. Как и любому объекту, каждому
признаку в интернет-пространстве присвоено любое число. Когда вы
отвечаете на вопрос в игре джина из Акинатора, алгоритм делит и
отсекает половину неподходящих персонажей. Каждый раз количество
вариантов уменьшается вдвое, пока не дойдет до единственного
оставшегося варианта. Таким образом, имея тысячи персонажей, игра
почти гарантированно угадает одного за десятьвопросов.В 1970-е годы
появились другие виды деревьев: quad-tree (дерево квадрантов),
которое делится уже не на две, а на четыреветки, и k-d деревья,
позволяющие искать информацию в трехмерном идругих многомерных
пространствах (k-мерные деревья). Такое развитие позволило
расширить возможности поисковых алгоритмов с чисел и строк на более
сложные типы документов, для которых были понятны принципы
построения векторного представления.В 2013 году шведский
разработчик Эрик Бернхардссон предложил новый подход к индексации
(то есть подготовке вспомогательной структуры данных, которая
позволяет быстро находить элементы, словно картотека в библиотеке)
музыкальных треков. Он предложил использовать для поиска не одно, а
сразу сотни деревьев одновременно и делить пространство не на
равные, а случайные части, определяемые специальной
процедурой.1Новую, индустриально значимую структуру назвали Annoy
(Approximate Nearest Neighbors Oh Yeah). Annoy позволяет работать с
векторными представлениями большой размерности, а точность зависит
в первую очередьот числа объектов. В теории структура опирается на
лемму Джонсона Линденштрауса о малом искажении, которая, в свою
очередь, обеспечивает высокую вероятность, что поиск вернет
достаточно много настоящих ближайших соседей. Так Annoy позволила
делать с многомерными данными (обладающими множеством параметром)
то, что ранее требовало существенно больших вычислительных
ресурсов.Релевантность и похожесть: как поиск угадывает ваш
запросРелевантность субъективная мера того, насколько найденные
документы удовлетворяют вашу потребность в информации. Можно думать
о ней не только какподходит под запрос или нет, но и как о некой
шкале соответствия вашим ожиданиям (например, это то, что нужно,
почти то, что нужно и так далее). Релевантностьсубъективна, но в
математике невозможно работать с субъективными мерами. Поэтому
приходится приближать (или моделировать) значение релевантности
числами, являющимися метрикой (расстоянием) в пространстве
документов. Например, расстояние между похожими объектами
(документами) можно считать маленьким, а расстояние между
непохожими объектами большим. В свою очередь, похожесть
(similarity) уже более точное понятие, мы можем придумать
какую-нибудь функцию, которая еевычисляет. Она также выражается в
числах.Когда два документа находятся рядом в метрическом
пространстве, они будут считаться похожими. Если объекты идентичны,
то расстояние между ними равно 0, а похожесть (моделирующая
релевантность) можно принять равной 1. И наоборот, максимально
непохожие объекты будут иметь большое расстояние, а похожестьбудет
равна 0. Представьте себе географическую карту и подумайте,
архитектура каких городов похожа между собой.Скорее всего, это
города с близкими географическими координатами, напримерРига и
Таллин, потому что у них схожая история и ландшафты. В многомерном
пространстве поддерживается то же правило.Поисковик очень хотел бы,
но не знает вашего исходного намерения, ион должен будет его
угадать. Например, если вы напишете фамилию Пушкин, имея в виду
дату его рождения, поиск выдаст вам биографию, стихотворения и
ближайшие заведения с таким названием. Контекст, о котором вы не
сообщили, лежит за пределами понимания системы. Она не сможет
догадаться о ваших реальных намерениях, но попытается отсортировать
или отранжировать объекты по степени релевантности. Самые
подходящие варианты окажутся наверху, а менее подходящие внизу.
Каждый запрос формируется индивидуально в соответствии с вашими
интересами, временем года и географическим положением. Когда вы
пишете слово погода в поисковой строке, вам показывают погоду
именно в вашем городе. Система также будет опираться на новизну
контента в данный период времени. Если вы захотите посмотреть
новости, то увидите, что самые свежие будут находиться на верхних
позициях. Но за процессом оценки контента всегда стоит человек и
его субъективное мнение о релевантности. Часто контекст, который вы
имели в виду, остается скрыт за рамками запроса. Поэтому невозможно
построить идеальную поисковую или рекомендательную систему, которая
на 100% угадает ваши намерения.Стереотипы и коллаборативная
фильтрацияОдним из видов построения рекомендательной системы
является коллаборативная фильтрация. Этот подход основан на
человеческих стереотипах. Выработка стереотипов первичная задача
машинного обучения.Каждый человек уникален, но при этом все люди
хорошо делятся на типы или кластеризуются. Например, существует
стереотип: типичный московский хипстер из медиаиздания или типичный
воронежский водитель такси. Мы примерно представляем, как выглядят
эти люди, что они любят и как себя ведут. Одни будут кликать на
биографию политика в интернете, другие на новости, связанные с
изменением политики любимого приложения. Предположим, что одни
более склонны к изучению истории, а вторые к отслеживанию последних
событий. Оказывается, опираясь только на поведение пользователей,
можно вычислять их социально-демографические признаки, такие как
уровень дохода, политические предпочтенияили наличие детей,
группировать людей и достаточно точно предсказывать их поведение,
опираясь на соседей по типу. Коллаборативная фильтрация как раз
направлена на анализ паттернов поведения.
Показателен пример с интернет-магазином: вы хотите не только
продавать, но и предлагать людям новые похожие товары.
Рекомендательная система сможет опираться на действия посетителей,
чтобы предлагать им релевантные варианты. Во-первых, она может
определить, на какие ссылки вы нажимали или просто наводили курсор.
Во-вторых, учитывает время просмотра страницы: ведь когда вы
находитесь на странице продолжительное время, алгоритм
предполагает, что вам интересно ее содержимое. В-третьих, система
будет опираться на лайки и оценки. Если вас заинтересовал товар, вы
можете сохранить его в избранном или оценить его качество. На
основании этой информации будут сформированы рекомендации и для
других, похожих на вас людей. Ваше поведение является источником
данных для коллаборативной фильтрации.Современные разработки и
тренды будущегоВ мире постоянно появляются новые алгоритмы, которые
не всегда напрямую связаны с рекомендательными или поисковыми
системами, но каждая разработка влияет на общие тенденции в сфере
цифровых технологий. Сегодня все более востребованными и быстро
развивающимися становятся системы, генерирующие контент: нейросети,
которые могут разработать дизайн логотипа или слоган компании; или
технологии, позволяющие сконструировать собственный выпуск новостей
или презентацию из имеющегося набора элементов; или манипуляции с
изображением, когда система комбинирует фото и картинки, создавая
несуществующих персонажей. Генерация игровых миров, deep learning
(глубокое обучение) или написание стихов работа искусственного
интеллекта, генерирующего контент без участия человека.Генерация
контента может повлиять как на привычный вид сервисов, так и на
естественность происхождения всех объектов в интернете. Сейчас,
открывая тот или иной поисковой запрос, вы видите список с кратким
описанием каждого элемента сниппетом. В нем содержится максимально
полезнаясжатая информация об объекте. По ней мы понимаем, подходит
ли нам этот сайт, либо спускаемся дальше по списку. Краткая
информация, указанная в блоке-сниппете, должна максимально
соответствовать смыслу страницы и содержать уникальные данные.
Сейчас описание настраивает человек (владелец контента или сайта),
но в ближайшем будущем такие тексты смогут писать нейронные сети:
они способны быстро оценить документ и сгенерировать его краткий
обзор.Но также искусственная генерация может усложнить определение
естественности контента. Если текст, фотографию или товарный знак
можно защитить авторским правом и проверить по реестру
интеллектуальной собственности, то проверить картинку из интернета
будет сложнее. Изображение, созданное машиной, также нельзя
использовать в суде в качестве вещественного доказательства.
Сегодня специальные модели только учатся различать объекты
человеческого и машинного творчества по определенным признакам.
Например, признаки экспертности или компетентности в том или ином
виде деятельности нельзя выразить единым числом, но можно присвоить
этим понятиям характерные косвенные признаки. К ним можно отнести
профессиональную терминологию, типичные штрихи, а также
интенсивность и частоту их использования. Задача определения
естественности контента стоит перед учеными уже сейчас.Крупные
сервисы с многомиллионными пользователями и огромными базами данных
сталкиваются с задачами billion-scale с такими, число объектов в
которых порядка миллиардов. Среди разнородного контента их ресурсов
становится все труднее найти, отсортировать и рекомендовать ту или
иную информацию. Сегодня ведется множество математических
исследований в области усовершенствования поисковых и
рекомендательных систем. Ученые постоянно изучают новые методы, а
разработчики стараются получить максимум из возможностей
технических устройств.Что читать, смотреть и слушатьPodlodka
Podcast 129-й выпуск Как работает поиск с Андреем
АксеновымТеоретический минимум по Big Data Анналин н, Кеннет Су,
издательство Питер, 2020 г.в оригинале Numsense! Data science for
the Layman, издательство Annalyn Ng & Kenneth Soo, 2017 г.Фильм
Она (Her), Режиссер: Спайк Джонс, в ролях: Хоакин Феникс, Скарлетт
Йоханссон, Эми Адамс, США, 2013 г.Г. М. Адельсон-Вельский, Е. М.
Ландис, доклад Один алгоритм организации, 1962 г.R. A. Finkel &
J. L. Bentley, Quad trees a data structure for retrieval on
composite keys, 1974 г.J. L. Bentley, Multidimensional binary
search trees used for associative searching, 1975 г.Y. Malkov, A.
Ponomarenko, A. Loginov, V. Krylov Approximate nearest neighbor
algorithm based on navigable small world graphs, 2013 г.S. Milgram,
The Small World Problem, Psychology Today,Ziff-Davis Publishing
Company, 1967 г.D. J. Watts, S. H. Strogatz, Collective dynamics of
small-world networks, 1998 г.Y. Malkov, D. Yashunin, Efficient and
robust approximate nearest neighbor search using Hierarchical
Navigable Small World graphs, 2016 г.
