Одной из самых крутых функций, которые может иметь приложение, чтобы оно выглядело как приложение, управляемое интеллектом или поддерживающее хорошие отношения с клиентами, является функция рекомендаций. Это один из наиболее распространенных, но ценных вариантов использования машинного обучения. Этот пост является выражением моего первого опыта работы с рекомендательной системой, которую я создал в рамках своей учебной программы.

Проблема в руке

В мире, где доставка еды осуществляется за считанные минуты, поиск подходящего ресторана на основе вкуса пользователя занимает гораздо больше времени, учитывая множество вариантов. Кроме того, о каждом ресторане судят по отзывам и рейтингам клиентов. Целью этого проекта является создание гибридной системы рекомендаций для ресторанов в Филадельфии, основанной на прошлом опыте и отзывах конкретного пользователя. Система также направлена ​​на то, чтобы предоставить владельцам ресторанов информацию о том, что «работает хорошо» и что можно улучшить», что может помочь ресторану сохранить хорошее обслуживание и импровизировать на ущербных.

Алгоритмы, которые я изучал

Я в основном изучил 3 основных алгоритма машинного обучения.

  1. Алгоритм альтернативных наименьших квадратов (ALS)
  2. Косинусное сходство
  3. Линейный SVM

Первые два являются довольно распространенным рецептом, когда речь идет о рекомендациях, но SVM более полезен в задачах, где нужен способ четко различать несколько разных классов в наборе данных. Поэтому в моем случае я использовал его для классификации необработанных текстов отзывов от пользователей на положительные и отрицательные отзывы, которые, по моему мнению, будут очень удобны для владельцев ресторанов, чтобы улучшить свои деловые стандарты.

Забегая вперед, я хотел бы осветить суть каждого из этих алгоритмов, их сложность и то, как они объединяются для создания удобного и универсального механизма рекомендаций по сравнению с традиционными вариантами использования рекомендаций в отдельных частях. Это часть 1, посвященная алгоритму ALS.

Чередование метода наименьших квадратов:

Цель этого поста — передать мой опыт изучения этих умных математических методов читателям, не имеющим опыта в области компьютерных наук или математики. Давай погрузимся,

Совместная фильтрация фильтрует информацию, используя взаимодействия и данные, собранные системой от других пользователей. Он основан на идее, что люди, которые согласились в своих оценках определенных пунктов, скорее всего, согласятся снова в будущем.

Совместная фильтрация в основном использует 2 очень умных математических метода, называемых:

  1. Матричная факторизация
  2. Чередование метода наименьших квадратов

Эти 2 метода составляют основу магии, которую создает этот алгоритм. Прежде чем пытаться изучить эти методы, давайте создадим проблему и научимся на примере.

Предположим, мы пытаемся создать рекомендательную систему на основе оценок пользователей из базы данных фильмов.

На изображении выше показана матрица с людьми в строках и фильмами в столбцах (M1, M2, M3, M4, M5). Это желаемая структура данных при работе с методом чередующихся наименьших квадратов. Переходя к сути, как, по вашему мнению, люди ведут себя с точки зрения «нравится» и «не нравится» или какая из трех матриц кажется наиболее близкой к реальному сценарию?

Хорошо, было бы легко исключить первое, выбор между 2-м и 3-м мог быть сложным. И ответ таков,

Причина в том, что первая матрица предполагает, что вкус каждого фильма у всех одинаков. Если это реальный мир, то я думаю, что потратил семестр на то, чтобы рекомендовать полезные объекты пользователям. К счастью, это не так. Третья матрица заполнена исключительно случайными числами, что указывает на то, что вкусы всех пользователей для всех фильмов были совершенно разными. В этом случае вы не увидите больше 2-3 человек в кинотеатре каждый раз, когда вы посещаете. К счастью, это тоже не так. Тот факт, что 2-я матрица имеет некоторое количество случайных + линейных зависимостей внутри матрицы, делает возможным существование таких волшебных математических методов, решающих проблемы, которые мы сегодня обсуждаем.

Кстати, что такое линейные зависимости? Линейные зависимости — это в основном отношения между переменными, величина которых может быть количественно определена с помощью чисел, таких как «Я в 3 раза выше своей мамы», «Мой друг в 0,5 раза тупее меня». Теперь давайте попробуем применить эту концепцию к нашей второй матрице и выясним линейные зависимости, которые существуют внутри матрицы.

Этих двоих было довольно легко распутать. Дайте своему мозгу хорошо провести время, обнаруживая более неявные из них.

Неявных намного больше. Но прежде чем я пропущу их и продолжу, позвольте мне дать вам еще один,

Без существования этих зависимостей математика просто не может продолжаться. Вот в чем красота, один фокус ведет к другому.

Вам все еще может быть интересно, в чем на самом деле проблема. Проблема в реальном мире заключается в том, что эти матрицы взаимодействия зрителей и фильмов не полностью заполнены оценками, как показано на изображениях выше. На самом деле матрица, с которой я имел дело, была разреженной на 99,4%, то есть 99,4% ячеек в этих матрицах были пустыми (не имели рейтинга) и только 0,6% ячеек имели запись (рейтинг). Подумайте об этом, это вполне естественно. Есть миллионы фильмов, сколько фильмов мы вообще оценили за всю свою жизнь? Этот вопрос делает 0,6% значимыми. Таким образом, проблема заключается в том, чтобы предсказать рейтинги для оставшихся незаполненных 99,4% и изучить их на основе доступных 0,6%.

Сейчас самое время вспомнить эти два волшебных слова: Матричная факторизация и метод чередующихся наименьших квадратов, потому что именно они помогут нам заполнить эти пробелы.

Матричная факторизация

В математике факторизация или факторизация состоит в записи числа или другого математического объекта как произведения нескольких факторов, обычно меньших или более простых объектов того же типа.

Матричная факторизация включает в себя в основном разделение матрицы на две части: пользовательскую матрицу и матрицу элементов (фильмы в нашем примере). Мы разделяем их таким образом, что скалярное произведение (будет объяснено ниже) двух матриц возвращает исходная матрица NxM, где N — количество пользователей, а M — количество фильмов. Перед разделением есть еще одно волшебство, которое делает этот алгоритм. В основном предполагается, что пользователи и элементы имеют некоторые общие черты, которые могут помочь алгоритму прогнозировать оценки. Например, давайте предположим, что функции — это боевик и комедия, обозначающие, сколько действия и комедии нравится пользователю и сколько действия и комедии содержится в фильме. Это может звучать как настоящее волшебство и может вызвать у вас в голове следующий вопрос: Знает ли уже алгоритм эти функции? или он учится этому во время обучения? Откуда он знает, что комедия и действие - единственные особенности? Откуда он знает, что есть только 2 функции, которые описывают общие атрибуты пользователей и элементов? Все эти ответы скоро появятся!

Алгоритм ничего не знает об особенностях, если честно. Числовые характеристики также являются гиперпараметром (что означает, что он может быть настроен пользователем). Например, если пользователь указывает количество функций равным 2, то алгоритм назначает две функции F1 и F2 как фильмам, так и пользователям, и изначально присваивает им случайные значения или нули. Сказав это, позвольте мне поделиться сюжетом, который я придумал.

Это ошибка в предсказании по сравнению с графиком количества признаков. Может быть удивительно видеть, что только 1 функция (нижняя точка по оси X) дала мне самую низкую ошибку. Это означает, что инициализация всего одной общей функции для пользователей и элементов позволила лучше прогнозировать оценки. Но я все еще не уверен в этом наблюдении. В реальном мире должно быть множество факторов, определяющих рейтинг пользователя тому или иному ресторану. Все эти концепции должны витать в воздухе прямо сейчас. Визуальное представление теперь может закрепить понимание.

Когда эти две факторизованные матрицы перемножаются, можно получить большую матрицу. Подумайте об этом, факторизованные матрицы: пользовательская матрица имеет размеры 4x2, а матрица фильмов имеет размеры 2x4, при умножении этих двух мы получим 4x4 (https://www.khanacademy.org/math/precalculus/ x9e81a4f98389efdf:matrices/x9e81a4f98389efdf:properties-of-matrix-multiplication/a/matrix-multiplication-dimensions), который представляет собой размеры исходной большой матрицы. малые значения около нуля. Значения на изображении выше являются изученными значениями. Разложенные матрицы с начальными случайными значениями будут выглядеть так:

А теперь мой любимый математический фокус https://en.wikipedia.org/wiki/Dot_product. Если вы знакомы с концепцией скалярного произведения, вы знаете, что скалярное произведение пользователя и матрицы элементов даст следующее:

Теперь это наши прогнозируемые рейтинги с использованием начальных значений функций F1 и F2 для каждого взаимодействия пользователя с элементом. Обратите внимание, что это прогнозы наших обучающих данных, поэтому их всегда можно сравнить с исходной истиной (обучающие данные — это исходная правда, из которой учатся алгоритмы ML).

Если мы сравним первую ячейку обеих матриц, мы предскажем, что рейтинг первой девушки для фильма M1 будет равен 1,44, тогда как ее фактический рейтинг равен 3. Обратите внимание, что в прогнозе есть ошибка примерно 3–1,44. = 1,56, это большая ошибка. Это произошло потому, что мы случайным образом инициализировали функции F1 и F2, и это дикая догадка, сделанная моделью с использованием этих случайных значений. Поверьте мне, машинное обучение может намного лучше. Теперь, как нам минимизировать ошибку между предсказаниями и источником правды? Чередующийся метод наименьших квадратов приходит на помощь!

Чередование метода наименьших квадратов

Здесь все может стать немного пугающим, если у вас нет опыта в машинном обучении. Концепция, называемая градиентным спуском, является главным архитектором в достижении нашей конечной цели в машинном обучении: "уменьшить ошибку, настроив значения для весов". Веса в нашем случае — это характеристики. Вот ресурс, где вы можете получить представление о градиентном спуске — https://towardsdatascience.com/gradient-descent-algorithm-a-deep-dive-cf04e8115f21#:~:text=Gradient%20descent%20 (GD)%20is%20an, например,%20in%20a%20linear%20regression). Если вы не хотите читать об этом, не беда, вам просто нужно доверять математике. Что делает ALS, так это запускает градиентный спуск по пользовательской матрице и матрице элементов попеременно и настраивает значения F1 и F2 обеих матриц до тех пор, пока не возникнет ошибка между прогнозируемой матрицей оценок и нашим источником правды. максимально минимальна. После определенного этапа, на котором ошибка не падает дальше, она останавливает процесс изменения значений признаков. Для людей с фоном ML, я хочу добавить одну интересную вещь: она использует нормальное уравнение регрессии для обновления градиента.

В конце всех этих уловок мы получаем матрицу предсказаний, которая достаточно близка к Источнику Истины. Когда в систему поступает новый набор фильмов и пользователей, этот процесс можно повторить с обновленными входными матрицами (содержащими новые объекты), чтобы предсказать, какими будут рейтинги пользователей для каждого фильма, и рекомендовать лучшие k фильмов на основе прогнозируемых рейтингов. упорядочены в порядке убывания.

Сложность алгоритма

Для тех, кого не волнует сложность алгоритма, это не для вас. Для тех, кто занимается CS, временная сложность алгоритма составляет O(k*n*m), где k – количество итераций градиентного спуска, n – количество пользователей , а m – количество фильмов или элементов в целом. Преимущество матричной факторизации в том, что она преобразует пространственную сложность O(n*m) в O(n+m)

Для людей, которые знают, сколько линейного пространства (блоков, помещающихся в память) может стимулировать максимальное использование основной памяти для ускорения всего алгоритма, это может быть очень интересно.