Успешная деятельность большинства крупных современных компаний, таких как Google и Яндекс, Amazon и Walmart, была бы невозможна без использования рекомендательных систем. Речь идет о системах, которые делают предположения относительно оценки каждым
конкретным пользователем товаров и услуг, предлагаемых компанией,
и рекомендуют наиболее подходящие.
Одним из основных методов, использующихся при создании рекомендательных систем, является коллаборативная фильтрация, что подтверждается большим количеством исследований на эту тему, например [25], [28] и [14]. Метод позволяет предсказать выбор конкретного
пользователя на основании уже имеющихся данных о поведении других
пользователей. Основная идея метода заключается в том, что пользователям, демонстрирующим схожее поведение, можно рекомендовать
похожие товары.
Хорошим примером использования коллаборативой фильтрации являются такие сервисы как Netflix, Ozon, Okko. Кроме того, существуют
наборы данных, такие как Amazon [26] и MovieLens [13], которые находятся в открытом доступе, предназначаясь для тренировки различных
рекомендательных систем в исследовательских целях, и будут использованы в этой работе для валидации результатов.
В последние годы было предложено множество различных техник
для применения коллаборативной фильтрации к реальным задачам.
Некоторые обобщают подходы матричной факторизации [1], другие же
используют нейросетевые архитектуры, такие как вариационные автокодировщики [8] или системы с обучением на последовательностях [24].
Из-за того что модели машинного обучения способны интерпретировать
лишь математические объекты, а реальные данные не всегда являются
таковыми (это могут быть строки, или id-номера, состоящие из цифр
и букв), необходимо предварительно кодировать объекты и субъекты
информационного процесса в числовые пространства. Правильный подход к проведению этого этапа может привести к значительному повыше-
4нию эффективности работы рекомендательных систем, таких как [16]
и [24]. Компании, заинтересованные в повышении качества рекомендаций, мотивируют дальнейшие исследования в этой области. Одним из
перспективных направлений для изучения является внедрение гиперболической геометрии в архитектуру нейронных сетей.
Применение гиперболической геометрии — один из способов качественно отобразить реальные данные на числовое пространство для
использования в машинном обучении [33]. За счет некоторых полезных свойств гиперболическая геометрия обеспечивает интерпретируемое вложение данных с иерархической структурой в пространство скрытых факторов, что было показано в работе [21].
Важной характеристикой гиперболического пространства является
кривизна. В некоторых исследованиях кривизна фиксируется как константа — например, в работах [44], [11] авторы фиксируют кривизну
как единицу. Однако при дальнейшем изучении было установлено, что
модели с точно выбранной кривизной, соответствующей специфике конкретного набора данных, показывают лучшие результаты [17].
Вычислить кривизну можно с помощью такой характеристики данных как дельта-гиперболичность, которая была введена Михаилом Леонидовичем Громовым в работе [12]. Основная сложность состоит в том,
что асимптотика базового подхода к вычислению этой величины составляет O(n4) относительно количества элементов в наборе данных,
что делает работу в реальных случаях очень ресурсоемкой. Несмотря
на это, алгоритм точно вычисляет δ-гиперболичность, поэтому может
быть использован для подтверждения корректности других алгоритмов. Для приблизительной оценки этой величины, а также для исследования ее поведения при изменении размера выборки и размерности
пространства, исследователями лаборатории «Вычислительного Интеллекта» [40] Сколтеха был предложен алгоритм, вычисляющий эту величину параллельно на небольших порциях данных. Экспериментальным путем было выяснено, что даже этот алгоритм не подходит для
работы на наборах реальных данных также из-за высокой ресурсоемкости и значительной ошибки относительно базового алгоритма. Таким
5образом, в рамках продолжения исследований по применению гиперболической геометрии в рекомендательных системах был сформулирован
запрос на разработку алгоритма подсчета δ-гиперболичности, который
более точно аппроксимирует базовый алгоритм и менее ресурсоемок.
В ходе выполнения дипломной работы получены следующие результаты.
• Проведен обзор существующих подходов для ускорения подсчета
δ-гиперболичности (наивный подход, алгоритм Condensed), набора модификаций алгоритма CCL (базовый алгоритм, алгоритм с
использованием ограниченного вычислительного бюджета). С учетом специфики данных для реализации на различных целевых архитектурах (СPU, GPU) были выбраны модификации алгоритма
CCL.
• Написана Python-библиотека, реализующая алгоритмы
Condenced, CCL и naive и поддерживающая версии для центрального и графического процессоров. Также библиотека
содержит версию алгоритма CCL для расчета δ-гиперболичности
на наборах данных произвольного размера.
• Выполнено экспериментальное исследование:
– проверена корректность реализованных алгоритмов посредством сравнения с эталонным решением (наивный подход),
реализованным для CPU и GPU на синтетических данных и
на наборах данных Amazon и MovieLens;
– сделаны замеры производительности относительно эвристики, разработанной в лаборатории «Вычислительного интеллекта», наилучшие результаты показал алгоритм CCL, реализованный на GPU.
С кодом библиотеки можно ознакомится по ссылке – https://
github.com/tnmtvv/hypdelta/tree/main.
Эксперименты проводились с помощью скриптов, представленных в репозитории – https://github.com/tnmtvv/
Gromov-delta-estimation/tree/main.
