Узнайте, как реализовать алгоритм матричной факторизации, который Google использовал для реализации моделей совместной фильтрации.

Вступление

Матрица стала важной темой в вопросах собеседования, независимо от того, являетесь ли вы разработчиком или инженером по данным. Работа с матричными индексами и их преобразование - это исключительная способность для понимания инженером данных.
Идея состоит в том, чтобы под ним изучать математику. Когда вы поймете алгоритм, все, что вам нужно сделать, это поиграть с индексами, чтобы получить ответ.

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

Что представляет собой реальное приложение Matrix Factorization?

Факторизация матрицы - важный подход во многих приложениях. Существуют суперкомпьютеры, предназначенные для матричной факторизации. Например, радары, отслеживающие полеты, используют стратегию, называемую фильтрацией Калмана. В основе фильтрации Калмана лежит деятельность по матричной факторизации. Фильтры Калмана освещают четкие рамки условий, когда они отслеживают ваш полет с помощью радаров. Еще один отличный пример - Google, где факторизация Matrix применялась для разработки модели совместной фильтрации.

Понимание математики

Алгоритмы матричной факторизации работают путем разложения исходной матрицы на две матрицы, одна из которых является верхним треугольником (U), а другая - нижним треугольником (L). В этом уроке я бы придерживался факторизации квадратной матрицы A в LU, как показано ниже.

Обратите внимание: для простоты нам не нужно беспокоиться о перестановке строк A, и мы можем предположить, что A меньше 5x5. Наконец, точка входа в матрицу (точка поворота) не равна нулю. Цель этого руководства - понять математику и преобразовать ее в код. Более сложная версия скоро будет опубликована в отдельной статье.

Матрица A представляет собой квадратную матрицу i на j, разложенную на матрицы L и U. Цель состоит в том, чтобы получить нули в верхнем правом углу матрицы - (L) и нули в нижнем левом углу матрицы - (U).

U-матрица

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

Чтобы понять больше, давайте рассмотрим пример, предположим, что у нас есть квадратная матрица размером 3 X 3, как показано ниже.

Чтобы получить нули в нижнем левом углу этой матрицы, мы должны сделать следующее:

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

Повторите эти шаги в третьем ряду. Обратите внимание, что первая строка должна остаться прежней.

Теперь нам нужно уменьшить 6 до 0. Мы можем сделать это, реализовав следующее:

Обратите внимание, что я использовал R2 вместо R1, потому что я не хочу терять ноль, полученный в третьей строке. Соответственно, я применил уравнение ко второй строке поочередно.

L-матрица

L-матрица прямая и понятная. Это эшелонированная диагональная матрица - единицы по диагонали и нули в правом верхнем углу. Значения напоминания будут множителями, которые мы получили путем сокращения строк с U-матрицей, расположенной в тех же индексах.

Таким образом, окончательное значение L-матрицы будет выглядеть так:

Компьютерный алгоритм

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

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

Вот реализация алгоритма с использованием R-языка. Вы можете реализовать то же самое, используя любой язык, который вам нравится.

Временная сложность этого алгоритма составляет O (n2) из-за выполнения двух вложенных циклов for - reference.

Заключительные примечания

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

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