Следующая часть моего путешествия - убедиться, что у меня есть твердое понимание математики, необходимой для машинного обучения. Это концепции, которые я где-то изучал раньше, когда-то в процессе обучения, и, следовательно, они послужат напоминанием и, возможно, дадут мне новые идеи.
Я поступил на курс «Математика для машинного обучения» Имперского колледжа Лондона на Coursera. Этот курс по линейной алгебре - первая часть из трех. Итак, я делал заметки и практиковался в визуализации концепций с помощью аналогий, и это то, что я узнал из этого курса.
Векторы
Векторы можно рассматривать как атрибуты. В геометрической интерпретации векторы имеют длину и направление. Векторы можно масштабировать, называя скалярным кратным вектора. Также векторы можно складывать вместе.
Векторы обладают ассоциативностью в сложении векторов (r + s) + t = r + (s + t). То же самое и с векторным вычитанием.
Точечное произведение, модуль и проекция векторов
Скалярное произведение вектора на другой вектор - это величина одного вектора в направлении другого вектора, умноженная на длину второго вектора.
Во-первых, скалярное произведение двух векторов может быть вычислено как таковое:
r · s = r1s1 + r2s2 +… + rnsn
Длину вектора также можно назвать его размером или величиной. Это определяется как | r | для вектора r. Эту величину можно вычислить с помощью теоремы Пифагора, где a² + b² = c².
Следовательно, | r | = √ (a² + b²) для r = [a, b].
Особый случай, на который следует обратить внимание, - это скалярное произведение самого вектора. Скалярное произведение вектора на себя - это просто длина вектора в квадрате. г · г = | г | ².
Пусть r вектор [r1, r2]. r · r тогда будет r1r1 + r2r2 или r¹² + r²². Вспоминая теорему Пифагора, это дает нам длину вектора в квадрате, | r | ².
Векторные скалярные произведения коммутативны, то есть r · s = s · r.
Кроме того, они дистрибутивны по сложению, r · (s + t) = r · s + r · t.
Наконец, существует ассоциативное сверх скалярное умножение, r · (as) = a (r · s) и r (as) + R (aS) = a (rs + RS).
Величину одного вектора в направлении другого вектора можно также рассматривать как тень, которую первый вектор отбрасывает на другой вектор. Эта длина равна | s | cos θ.
Учитывая два вектора r и s, мы можем использовать правило косинуса, чтобы найти скалярное произведение r · s.
Правило косинуса выглядит следующим образом: c² = a² + b² -2abcos (θ). Используя векторное вычитание, мы получим c² как | r-s | ². Затем, после подстановки векторов в, | r-s | ² = | r | ² + | s | ² -2 | r || s | cos (θ).
Как мы знаем, r · r = | r | ², (r-s) · (r-s) = r · r -s · r -s · r -s · s = | r | ² -2s · r + | s | ²
Поскольку (r-s) · (r-s) = | r-s | ² аналогично тому, что было показано выше, мы получаем следующее:
| r | ² + | s | ² -2 | r || s | cos (θ) = | r | ² -2s · r + | s | ²
-2 | r || s | cos (θ) = -2s · r
Отсюда получаем r · s = | r || s | cos (θ), где θ - угол между r и s.
Из графика, зная, что косинус задается смежной длиной, деленной на гипотенузы, мы получаем | s | cos (θ) как равное скалярной проекции s на r. r · s = | r | * скалярная проекция или (r.s) / | r | = | s | cos (θ).
Скалярная проекция дает нам длину проекции. Вектор, задаваемый проекцией, является векторной проекцией одного вектора на другой. Проекция вектора s на r задается скалярной проекцией как скалярное кратное вектора единичной длины в направлении r.
Получение вектора единичной длины вектора - это просто сам вектор, деленный на его длину, r / | r |.
Векторная проекция = Скалярная проекция * r как единичная длина
= [(r · s) / (| r || r |)] * Вектор r
= [(r · s) / (r · r)] * Вектор r
Основы и природные основы
Базис - это базовый единичный вектор в координатном пространстве.
Базисные наборы состоят из базисных векторов, которые линейно независимы, что означает, что они не являются линейной комбинацией других линейных векторов в базисном наборе. Например, для базисных наборов в трехмерном пространстве линейная зависимость достигается, когда bi = xbj + ybk не выполняется ни для какой комбинации векторов как bi, bj и bk.
Другой способ определить линейную независимость - взять одновременное уравнение a [x1, x2, x3] + b [x1, x2, x3] + c [x1, x2, x3] = [0,0,0] и найти если a = b = c. Если все переменные равны друг другу, векторы линейно независимы.
Базисные векторы в естественном базисном наборе должны охватывать пространство, то есть векторы в наборе должны занимать все n-мерное пространство, равное количеству векторов.
Natural Bases или Стандартные базы - это специальные базы единичной длины. Набор ортонормированных базисных векторов состоит из этих специальных естественных базисных векторов единичной длины, где, кроме того, все эти векторы перпендикулярны друг другу.
Системы координат и их базисные векторы
Стандартная система координат, используемая в двумерных графиках, использует x как горизонтальную координату, а y как вертикальную. Каждая система координат использует базисные векторы, фундаментальную единицу, используемую для измерения координат в системе. Для стандартной двумерной системы координат двумя базисными векторами являются ê1 = [1, 0] и ê2 = [0, 1].
Базисные векторы в системе координат могут использоваться для описания векторов. Например, вектор r, описанный в стандартной системе координат, может быть состояниями как таковыми. r = [3, 4] = 3ê1 + 4ê2.
Векторы можно переводить с одной основы на другую. В альтернативном базисе b у нас есть два новых базисных вектора b1 и b2.
Если эти два базисных вектора перпендикулярны друг другу, то можно использовать проекцию, чтобы найти r в альтернативном базисе. Чтобы проверить перпендикулярность, мы гарантируем, что (b1 · b2) = 0 или cos (θ) = 0.
Чтобы найти r в альтернативном базисе b, мы берем скалярное произведение r на два базисных вектора b соответственно. Для r = [r1, r2] возьмем (r1 · b1) / | b1 | ² как R1 и (r2 · b2) / | b2 | ² как R2. вектор в новом базисе будет R = [R1, R2]. Общее правило: для каждого измерения j в базисном векторном пространстве Ri = ri · bj / | bj | ².
Базисные векторы в одной системе координат также могут быть описаны в другой системе координат. Преобразование этих векторов формирует матрицу, которую затем можно использовать для перевода векторов из одного базиса в другой.
Матрицы
Матрица представляет собой прямоугольную сетку значений формы m на n, где m - количество строк в матрице, а n - количество столбцов.
Умножение матриц работает путем умножения каждого элемента в i-й строке первой матрицы на соответствующий ему элемент в j-м столбце второй матрицы, суммирования результатов и применения его к результирующей матрице в i-й строке и j-й столбец. Повторите эти действия для всех объектов в матрице, чтобы завершить умножение матрицы.
Для матричного умножения матрицы m1 на n1 на матрицу m2 на n2 результирующая матрица будет иметь размер m1 на n2. Кроме того, чтобы умножение матриц работало, значения n1 и m2 должны быть равны.
([a, b], [c, d])·(x1, x2) = (ax1 + bx2, cx1 + dx2)
Другой способ взглянуть на матрицы - это рассматривать их как преобразование базисных векторов. Для вектора в системе координат с базисными векторами [1, 0] и [0, 1] умножение матрицы на ([a, b], [c, d]) преобразует два базисных вектора в [a, c] и [b, d] соответственно. Фактически, это переводит вектор в альтернативную систему координат с базисными векторами [a, c] и [b, d].
Специальные типы матриц
Матрица идентичности
Обозначается буквой «I», единичная матрица состоит из единиц по главной диагонали и нулей во всех остальных местах. Ведущая диагональ начинается от левой верхней ячейки до правой нижней ячейки.
Зеркала
Это матрицы, отражающие векторы вдоль плоскости. Все эти примеры предполагают стандартный набор начальных базисных векторов [1, 0] и [0, 1].
([0, 1], [1, 0]) отражает векторы вдоль противодиагональной плоскости. Проходит через начало координат под углом 45 градусов к горизонтальной плоскости.
([1, 0], [0, -1]) отражает векторы вдоль горизонтальной плоскости.
([-1, 0], [0, 1]) отражает векторы вдоль вертикальной плоскости.
([0, -1], [-1, 0]) отражает векторы вдоль ведущей диагональной плоскости.
Ножницы
Эти матрицы сдвигают только один базисный вектор по плоскости, перпендикулярной его направлению.
([1, 0], [1, 1]) сдвигает единицу длины [0, 1] вектора 1 вправо.
Повороты
Эти матрицы вращают базисные векторы вокруг начала координат. Матрица, соответствующая желаемой величине поворота, задается формулой ([cos (θ), sin (θ)], [-sin (θ), cos (θ)]), где θ - угол поворота против часовой стрелки.
Порядок, в котором применяются эти манипуляции с матрицами, определяет получаемые результаты, умножение матриц не является коммутативным.
Обратная матрица
Если взять скалярное произведение матрицы на обратную, получится матрица идентичности. Это специальное матричное умножение коммутативно.
Возьмем пример, где есть матрица A и два вектора, r и s, где r неизвестно, а s известно. Если Ar = s, найти значение вектора r можно с помощью исключения Гаусса и обратной замены.
После выполнения исключения по Гауссу матрица будет иметь форму эшелона строк. Это треугольная матрица, в которой все элементы ниже главной диагонали имеют нулевое значение. Найдите значения вектора, подставив нижние строки в верхние.
Выполнение исключения по Гауссу:
Вычтите строку 1 из строки 2 и строки 3.
В строке 3 получается (0, 0, -1) [c] = [-2], поэтому мы умножаем его на -1.
Это подводит нас к форме Row Echelon Form.
Выполните обратную замену:
Подставляя строку 3 в строку 2, строка 2 становится (0, 1, 0) [b] = [4]. Подставляя строку 2 в строку 1, строка 1 становится (1, 0, 0) [a] = [5].
После этих замен мы придем к матрице идентичности.
Проделывая описанные выше манипуляции, обязательно проделайте ту же операцию с вектором справа. Результирующий вектор будет решением для вектора r.
Используя те же шаги, мы можем найти обратную матрицу. Используя уравнение AA-¹ = I, мы устанавливаем каждую сущность в A-¹ как неизвестную. Решение можно выполнять по одному столбцу за раз, используя метод, описанный выше.
В качестве альтернативы также возможно одновременное решение для всех векторных решений. Сначала начните с матрицы слева и единичной матрицы справа. Выполните все действия по исключению и замене как для левой, так и для правой матрицы. Когда левая матрица преобразуется в единичную матрицу, правая матрица будет обратной по отношению к исходной матрице.
Определитель матрицы
Площадь или определитель матрицы A ([a, b], [c, d]) - это ad-bc или обозначается как | A |.
Для матрицы 2x2 обратное преобразование можно построить, поменяв местами элементы a и d в матрице, умножив элементы b и c на -1 и уменьшив масштаб всей матрицы на коэффициент, равный значению определителя.
Определитель также можно рассматривать как величину масштабирования исходного пространства, заключенного предыдущим базисным вектором.
Пониженная размерность
Точечное произведение матрицы с другой матрицей, состоящей из векторов, которые не являются линейно независимыми, вызовет потерю информации по мере уменьшения векторного пространства. Матрица с векторами, которые не являются линейно независимыми, называется сингулярной матрицей, поскольку у нее нет обратной. Следовательно, из-за своей сингулярной природы или отсутствия инверсии преобразованное векторное пространство не может восстановить информацию о потерях при возврате в пространство более высокого измерения.
Конвенция Эйнштейна о суммировании
Пусть матрица A = ([a11, a12,… a1n], [a21, a22,… a2n]… [an1, an2,… ann]), матрица n на n. Первое число обозначает строку, а второе число обозначает столбец. Пусть матрица B будет другой матрицей n на n с тем же соглашением. AB будет матричным умножением матрицы A и матрицы B.
Возьмем, к примеру, ячейку в матрице во 2-й строке и 3-м столбце, ab23.
ab23 = a21b13 + a22b23 +… + a2nbn3
Обобщая, для i-й строки и k-го столбца в преобразованной матрице мы находим, что abik = ∑ (aijbjk) для каждой ячейки j в строке или столбце соответственно. В соглашении Эйнштейна о суммировании это обозначается как abik = aijbjk.
Изменение основы
Для перехода от стандартного базиса [1, 0] и [0, 1] к альтернативному базису [3, 1] и [1, 1] потребуется преобразование вектора с помощью матрицы преобразования. Вектор, который равен [3/2, 1/2] в альтернативном базисе, будет ([3, 1], [1, 1]) · [3/2, 1/2] или [5, 2] в оригинальная основа.
Вычисления проекции вектора также могут работать, если базовая система использует ортонормированный базисный набор векторов.
В качестве примера упражнения можно найти поворот на 45 градусов против часовой стрелки для вектора, координаты которого находятся в альтернативном базисе. Поиск правильной матрицы для выполнения вращения в альтернативном базисе был бы сложным подходом к проблеме. Мы знаем формулу матрицы вращения в стандартном базисе, и, таким образом, выполнить вращение в стандартном базисе будет проще.
- Изменение основы с альтернативной на стандартную
- Поворот в стандартном базисе с использованием ([cos (θ), sin (θ)], [-sin (θ), cos (θ)])
- Изменение основы обратно на альтернативную основу
Транспонирование матрицы
Транспонирование матрицы включает зеркальное отображение всех ячеек матрицы по ведущей диагонали, так что каждая строка становится каждым столбцом соответственно и наоборот. AijT = Aji, где i - номер строки, а j - номер столбца.
Для ортогональной матрицы A обратная ей также является транспонированной матрицей. Таким образом, вычисление обратного просто требует транспонирования матрицы. A-¹ = AT
Процесс Грама-Шмидта
Этот процесс позволяет нам производить ортогональную матрицу из неортогональной.
В этом примере будет использоваться трехмерная матрица. Начните с маркировки трех векторов: v1, v2 и v3. Эти векторы могут быть или не быть перпендикулярными друг другу, но мы будем предполагать, что вместе эти три вектора охватывают трехмерное пространство. Цель состоит в том, чтобы найти три ортонормированных базисных вектора из этих векторов и пометить их как e1, e2 и e3.
- Пусть e1 будет v1 / | v1 |. Первый вектор просто нормализован.
- v2 состоит из части, параллельной e1, и части, перпендикулярной e1. Пусть u2 - перпендикулярная часть.
v2 = (v2 ·e1)e1 + u2
u2 = v2-(v2 ·e1)e1
e2 = u2/|u2|
3. v3 состоит из частей, параллельных e1 и e2 соответственно, и части, перпендикулярной им обоим.
v3 = (v3 ·e1)e1 +(v3 ·e2)e2 + u3
u3 = v3-(v3 ·e1)e1 +(v3 ·e2)e2
e3 = u3/|u3|
Это завершает процесс Грама-Шмидта и дает нам три ортонормированных базисных вектора: e1, e2 и e3.
Пример изменения базиса и процесса Грама-Шмидта
В этом примере используются две концепции. Координатное пространство трехмерное. Цель состоит в том, чтобы отразить вектор от плоскости в альтернативной основе. Для данного вектора в стандартном базисе определить координаты вектора в стандартном базисе при отражении от плоскости в альтернативном базисе. В этом примере мы предполагаем, что плоскость в альтернативном базисе является его первыми двумя базисными векторами.
Нахождение матрицы, в которой вектор отражается относительно плоскости в альтернативном базисе при вычислениях в стандартном базисе, является трудным и включает в себя множество сложной тригонометрии. Однако, как упоминалось ранее, самым простым способом было бы выполнить зеркальное отображение после изменения основы.
- Используйте процесс Грама-Шмидта, чтобы найти набор ортонормированных базисных векторов для альтернативного базиса.
- Измените вектор на альтернативный базис, используя матричную форму из набора ортонормированных базисных векторов.
- Отразите вектор в альтернативном базисе. Просто отразите третий вектор, изменив его с [0, 0, 1] в третьей строке единичной матрицы на [0, 0, -1].
- Верните вектор к стандартному основанию. Поскольку начальное преобразование в альтернативный базис использует набор ортонормированных базисных векторов, обратное преобразование - это просто транспонирование матрицы.
Собственные проблемы
Eigen означает характеристику. В случае матричных преобразований векторы могут изменяться по масштабу и направлению. Собственный вектор матричного преобразования - это вектор, который не меняет направления после того, как преобразование имело место. Собственное значение этого собственного вектора является масштабным кратным величине собственного вектора до и после преобразования матрицы. Собственные значения могут находиться в диапазоне от отрицательной бесконечности до положительной бесконечности. Частный случай собственного значения, равного нулю, - это когда размер пространства коллапсирует.
Различные матричные преобразования имеют разные собственные векторы. Здесь мы смотрим на масштаб, сдвиг и вращение в двухмерном пространстве.
Однонаправленная шкала имеет два собственных вектора: один в направлениях масштабирования с собственным значением, равным величине масштабирования, а другой - в перпендикулярном направлении с собственным значением, равным единице.
Если масштаб является однородным во всех направлениях, все векторы являются собственными векторами с собственными значениями, равными величине масштабирования.
Чистый сдвиг имеет только один собственный вектор, базисный вектор, который не изменяется. Поскольку базисный вектор не изменяется, величина постоянна с собственным значением, равным единице.
Вращение не имеет собственных векторов. Исключением может быть поворот на 180 градусов, при котором все векторы являются собственными векторами с отрицательными собственными значениями.
В трехмерном пространстве вращение в двумерном пространстве будет иметь собственный вектор на оси вращения с собственным значением, равным единице.
Определение собственных векторов матричного преобразования
Для собственного вектора x Ax = λx, где A - матрица преобразования n на n.
Управляя уравнением, (A- λI) x = 0. Игнорируя тривиальное решение x = 0, мы вместо этого решаем для A- λI = 0. Это означает нахождение, когда det (A- λI) = 0.
Пусть A = ([a, b], [c, d]).
det (([a, b], [c, d]) - ([λ, 0], [0, λ])) = 0
det ([a- λ, b], [c, d- λ]) = 0
λ²-(a+d)λ + ad-bc = 0
λ - решение для поиска собственных векторов. Решений может быть два, один или ни одного. Для каждого решения подставьте значение λ в уравнение A · ([x1, x2]), чтобы узнать возможные значения и то, как базисный вектор соотносится друг с другом и, следовательно, с возможными собственными векторами.
Примеры отношений и как их интерпретировать:
[0, x2] = 0, следовательно, λ = [t, 0], где t произвольно.
[x1-x2, x1-x2] = 0, x1 = x2, следовательно, λ = [t, t]
[x1 + 4x2, x1 + 4x2] = 0, x1 = -4x2, следовательно, λ = [-4t, t]
Диагонализация и матрица преобразования собственного базиса
Иногда преобразования матрицы необходимо повторять несколько раз. По мере увеличения количества повторов время вычислений также увеличивается. Использование диагонализации с помощью матрицы преобразования собственного базиса сокращает требуемые вычисления.
Диагонализированная матрица - это, по сути, единичная матрица, за исключением того, что каждое значение в ведущей диагонали заменяется собственным значением собственного вектора, представленного в столбце. Матрица преобразования собственного базиса использует особые свойства диагонализованных матриц, где применение матрицы n раз аналогично применению только одной матрицы, где каждое значение умножается в степень n.
Этот метод в основном используется, когда матрицу необходимо применить несколько раз. Преобразование матрицы в альтернативный базис, где матрица теперь является диагонализованной матрицей, упрощает процесс вычисления для нескольких приложений матрицы. Результаты, которые теперь находятся в альтернативной основе, затем могут быть переведены обратно в исходную основу для получения решения.
Вот как использовать матрицу преобразования собственного базиса для матрицы T.
- Найти собственные векторы и их собственные значения матрицы T
- Пусть C будет матрицей преобразования, где каждый столбец содержит собственный вектор матрицы T, это преобразует матрицу из альтернативного базиса обратно в стандартный базис
- Пусть D будет матрицей T в новом альтернативном базисе, где значение каждого столбца изменяется на собственное значение соответствующего столбца в матрице C
- Найдите C-¹, который преобразуется в альтернативный базис
- Используя формулу T ^ n = CD ^ nC-¹, чтобы выполнить желаемое количество преобразований матрицы T
Алгоритм ранжирования страницы
Известный алгоритм поискового ранжирования Google использует вероятность клика. Предпосылка заключается в том, что страницы связаны с другими страницами через ссылки. Таким образом, предполагается, что каждая из этих связанных страниц с равной вероятностью станет следующей страницей, на которую перейдет пользователь.
Пусть L будет матрицей, содержащей векторы в столбцах вероятности ссылки каждой страницы на следующую страницу.
В этом примере мини-интернета присутствуют только четыре страницы: A, B, C и D. A ссылки на B, C и D. B ссылки на A и D. C ссылки только на D. D ссылки на B и C. Если предположить, что пользователь нажимает на каждую ссылку одинаково, вероятность ссылки на каждую страницу будет равна единице, деленной на количество ссылок на странице.
LA = [0, 1/3, 1/3, 1/3]
LB = [1/2, 0, 0, 1/2]
LC = [0, 0, 0, 1]
LD = [0, 1/2, 1/2, 0]
Каждый столбец представляет собой нормированные на случайность внешние ссылки. Каждая строка представляет собой внутренние ссылки с других страниц.
Другая матрица R хранит ранги этих четырех страниц. В этом алгоритме для расчета рейтинга конкретной страницы необходимы три вещи: ранги всех других страниц, информация о входящих ссылках на страницу и общее количество исходящих ссылок с каждой страницы.
Формула для расчета рейтинга каждой страницы приведена. Для страницы A RA = ∑i (LAi * Ri). Используя соглашение Эйнштейна о суммировании, получаем R = LR.
Поскольку для вычисления значения ранга в первую очередь требуется значение ранга, нам нужно иметь начальное значение. После вычисления каждой итерации для всех рангов это значение приблизит нас к фактическому значению ранга.
Начальное значение для каждого ранга будет установлено путем усреднения по всем страницам, 1 / n, где n = количество страниц. В случае, который мы используем, мы получаем 1/4 в качестве значения рейтинга для каждой страницы.
R (итерация i + 1) = LR (итерация i)
Продолжайте выполнять уравнение, пока R не сойдется, или пока изменение значения между итерациями не станет ниже определенного порога.
Преобразование всегда будет удерживать общую сумму R равной единице, поскольку матрица L состоит из собственных векторов с собственным значением, равным единице. Это обеспечивается вероятностной структурой, на которой построена L.
Настоящий Интернет использует гораздо более разреженную матрицу, поскольку каждая страница обычно ссылается только на несколько других страниц. Общее количество страниц в Интернете намного превышает количество ссылок на каждой странице. Следовательно, эта простая формула требует нескольких дополнительных параметров для более точной оценки рейтинга страницы.
Коэффициент демпфирования
Предыдущий алгоритм был обновлен по сравнению с его предыдущей формой и теперь включает коэффициент демпфирования.
Этот коэффициент демпфирования учитывает вероятность того, что пользователь может выбрать доступ к случайной странице в Интернете, введя ее URL-адрес в адресную строку.
При включении коэффициента демпфирования формула изменяется как таковая.
R (итерация i + 1) = d (LR (итерация i)) + (1-d) / n, где вторая часть формулы, представляющая вероятность того, что пользователь просматривает новую страницу по URL-адресу, а не по ссылке.
