📄Работа №152149
Тема: Разработка быстрых алгоритмов расчета дельта-гиперболичности данных в задачах коллаборативной фильтрации на языке Python
Тип работы
Бакалаврская работа
Предмет
Информационные системы
Объем:
38 листов
Год:
2024
Просмотров:
135
4760
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
2. Постановка задачи 7
3. Обзор 8
3.1. 6-гиперболичность в коллаборативной фильтрации ... 8
3.2. Алгоритмы подсчета 6-гиперболичности 11
3.3. Выводы 15
4. Реализация 16
4.1. Выбор инструментария 16
4.2. Реализация алгоритма CCL для различных архитектур . 19
4.3. Подсчет матрицы расстояний 23
4.4. Параллельный подсчет 5-гиперболичности для несколь¬
ких выборок 25
5. Эксперименты 26
5.1. Тестовый стенд 26
5.2. Исследовательские вопросы 27
5.3. Выводы 31
6. Заключение 32
Список литературы 33
2. Постановка задачи 7
3. Обзор 8
3.1. 6-гиперболичность в коллаборативной фильтрации ... 8
3.2. Алгоритмы подсчета 6-гиперболичности 11
3.3. Выводы 15
4. Реализация 16
4.1. Выбор инструментария 16
4.2. Реализация алгоритма CCL для различных архитектур . 19
4.3. Подсчет матрицы расстояний 23
4.4. Параллельный подсчет 5-гиперболичности для несколь¬
ких выборок 25
5. Эксперименты 26
5.1. Тестовый стенд 26
5.2. Исследовательские вопросы 27
5.3. Выводы 31
6. Заключение 32
Список литературы 33
📖 Введение
Успешная деятельность большинства крупных современных компаний, таких как 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образом, в рамках продолжения исследований по применению гиперболической геометрии в рекомендательных системах был сформулирован
запрос на разработку алгоритма подсчета δ-гиперболичности, который
более точно аппроксимирует базовый алгоритм и менее ресурсоемок.
конкретным пользователем товаров и услуг, предлагаемых компанией,
и рекомендуют наиболее подходящие.
Одним из основных методов, использующихся при создании рекомендательных систем, является коллаборативная фильтрация, что подтверждается большим количеством исследований на эту тему, например [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.
• Проведен обзор существующих подходов для ускорения подсчета
δ-гиперболичности (наивный подход, алгоритм 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.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.