Уловка картографа XIX века, основанная на современных линейных моделях и симуляциях Монте-Карло
Андре-Луи Холески представляет собой причуду среди математиков: его работа была опубликована посмертно после того, как он погиб в бою во время Первой мировой войны. Он открыл метод линейной алгебры, который носит его имя благодаря его работе в качестве создателя карт конца 19 века, но он продолжает оставаться эффективным трюком, который питает многие модели машинного обучения. В этой статье будут обсуждаться математические основы метода и показаны два приложения к линейной регрессии и моделированию Монте-Карло.
Как это работает
Я постараюсь сделать линейную алгебру краткой, но это неизбежно: осознайте, что линейная алгебра - это просто метод эффективного решения систем уравнений, а также осознайте, что передовые методы линейной алгебры являются основой машинного обучения. Помимо извинений, давайте перейдем к делу.
Разложение Холецкого сводит симметричную матрицу к нижнетреугольной матрице, которая при умножении на транспонирование дает исходную симметричную матрицу. Если это не имело смысла, то вот как это выглядит:
from numpy import array from numpy.linalg import cholesky # define a 3x3 matrix A = array([[36, 30, 18], [30, 41, 23], [18, 23, 14]]) print(L) # Cholesky decomposition L = cholesky(A) print(L) print(L.T) # reconstruct B = L.dot(L.T) print(B)
Интуиция этого метода немного усложняется - я представлю его здесь, но это будет та часть сообщения, которую стоит пропустить из-за ловкости сердца - забавные вещи (приложения) ниже). Мы будем использовать обозначение A [1,1] для обозначения строки = 1, столбца = 1 в матрице A.
Разложение Холецкого - итеративный процесс. Я буду придерживаться обозначений систем уравнений ниже, но когда мы дойдем до третьей строки, вы увидите, что запись этого с помощью линейной алгебры будет иметь большой смысл. Эта запись хорошо объясняет нотацию матричной алгебры. Обратите внимание, что есть и другие методы для нахождения разложения Холецкого - Википедия объясняет несколько. Все следуют одинаковому типу потока.
Ладно, и что? Теперь самое интересное: с помощью разложения Холецкого мы можем решать системы уравнений любого размера за 2 шага. Предположим, мы хотим найти a, b и c: помните, что это также можно записать в виде системы из трех уравнений.
Обычно мы складываем 3 уравнения друг на друга, решаем одну переменную, зависящую от двух других, подключаем ее и т. Д. Используя разложение Холецкого, у нас есть гораздо более эффективный метод.
Матрица 3x3 немного разочаровывает, но мы уже можем начать оценивать эффективность этого метода на очень большой матрице.
Приложения - регрессия наименьших квадратов
Линейная регрессия имеет вид Y = X * β, где Y - вектор зависимых переменных, а X - вектор независимых переменных. Регрессия наименьших квадратов относится к нахождению вектора β, в котором квадраты разностей между прогнозируемыми и фактическими значениями Y (т.е. RSS = «Остаточная сумма квадратов» или «Сумма квадратов ошибок») сведены к минимуму.
Если это не имеет смысла, сосредоточьтесь на одном выводе: разложение Холецкого примерно вдвое эффективнее, чем другие методы решения систем линейных уравнений.
Приложения - моделирование методом Монте-Карло
Самое крутое приложение я оставил напоследок. Представьте, что вы хотите сгенерировать много коррелированных нормальных случайных величин, но не хотите иметь дело с массивной многомерной нормой. Разложение Холецкого позволяет моделировать некоррелированные нормальные переменные и преобразовывать их в коррелированные переменные noraml - круто!
Предположим, 3 нормальные (0,1) случайные величины, мы хотим следовать ковариационной матрице ниже, представляющей лежащие в основе матрицы корреляции и стандартного отклонения:
Мы находим разложение Холецкого ковариационной матрицы и умножаем его на матрицу некоррелированных случайных величин, чтобы создать коррелированные переменные.
import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
x_uncor = np.random.normal(0, 1, (3, 10000))
cov = np.array([[ 10.0, -2.00, 2.00],
[-2.00, 20.00, 0.50],
[ 2.00, 0.50, 0.50]])
L = np.linalg.cholesky(cov)
x_cor = np.dot(L, x_uncor)
corr_simulated = pd.DataFrame(x_cor).T.corr()
std_ = np.sqrt(np.diag(cov))
corr_empirical = cov / np.outer(std_, std_)
x_uncor = pd.DataFrame(x_uncor.T)
x_cor = pd.DataFrame(x_cor.T)
sns.pairplot(x_uncor, kind="reg")
sns.pairplot(x_cor, kind="reg")
Вуаля! Идем от некоррелированных:
Чтобы соотнести:
В соответствии с матрицами корреляции и стандартного отклонения, представленными выше, столбцы 0 и 2 имеют строго положительную корреляцию, 0 и 1 - слегка отрицательную, 1 и 2 - слегка положительную. Стандартное отклонение переменной 2 содержится, в то время как 0 и 1 намного шире.
Обратите внимание, что это не работает таким же образом для ненормальных случайных величин. В приведенном выше примере наши коррелированные переменные сохранили нормальное распределение. Если мы применим этот метод к случайным величинам, генерируемым гамма-излучением, мы увидим, что процесс не выполняется.
Некоррелированная гамма (1, 5) - все в порядке.
И коррелировано:
Здесь мы видим, что переменные больше не имеют гамма-распределения - это наиболее очевидный признак того, что переменная 1 принимает отрицательные значения, в то время как гамма-распределение строго положительно. Существует простое приближение с задним ходом, которое включает моделирование коррелированных случайных величин, нахождение их обратных величин и последующее извлечение из желаемого распределения с использованием значений обратно-коррелированных нормальных величин. Это не совсем так, но работа может быть выполнена. Точные методы обычно довольно экзотичны.
Заключение
Разложение Холецкого - это хитрый прием, лежащий в основе многих приложений машинного обучения, два из которых были описаны здесь: регрессия по методу наименьших квадратов и моделирование Монте-Карло с использованием коррелированных нормальных переменных. Хотя линейная алгебра может быть немного пугающей, важно помнить, что это просто эффективный метод записи систем линейных уравнений, и что понимание методов линейной алгебры на высоком уровне имеет решающее значение для понимания современных алгоритмов машинного обучения.
