Этот пост является частью серии статей о машинном обучении в языке программирования Dart:
- Машинное обучение на языке программирования Dart
- Нежное введение в линейную регрессию: способ Dart
- Линейная регрессия: краткое описание метода наименьших квадратов
Всем привет,
В своей предыдущей статье я объяснил Обыкновенную задачу наименьших квадратов. Я упомянул, что есть несколько способов решить эту проблему, и один из них — решение с закрытой формой.
Сегодня мы собираемся:
- выяснить, что такое закрытая форма
- вывести формулу решения в закрытой форме для линейной регрессии
- коснитесь живого примера линейной регрессии с использованием языка программирования Dart
Давай начнем!
Что такое решение в закрытой форме?
Давайте рассмотрим элементарный пример:
Я полагаю, что каждый может найти x, это 3. Если мы заменим 2 на a, а 6 на b, мы получим формулу для x:
Теперь рассмотрим более сложный пример:
Как вы могли заметить, это квадратное уравнение. Итак, если мы заменим 2 на a, 7 на b и 3 на c, мы можем использовать известную формулу, чтобы найти все возможные значения x:
Опять же, ответы найти легко: 3 и 0,5.
Что общего между этими двумя примерами? Верно, обе они могут быть выражены формулой, которая предполагает достижение единственно возможного решения за конечное число простых математических операций.
Давайте теперь посмотрим на другой пример:
перефразируя это простым языком, мы должны дифференцировать функцию квадрата x.
Вспомним, что такое дифференциация. Это процесс, в котором мы немного меняем аргумент и наблюдаем за поведением функции, чтобы понять, насколько функция чувствительна к изменению. Такой процесс можно выразить формулой:
Как видите, найти точное значение y невозможно. Мы можем изменять аргумент функции бесконечное число раз и все равно не иметь окончательного решения.
Случай, когда у нас есть единственное возможное решение проблемы, которое мы можем получить за конечное число простых математических операций, называется Решением в закрытой форме. Первые два уравнения — отличные примеры такого решения; их можно сделать просто и свести к единственному возможному ответу. Последний, очевидно, не имеет закрытой формы.
Теперь мы знаем, что такое закрытая форма. Есть ли у задачи линейной регрессии такое решение? Да, это так. Чтобы вывести формулу, нужно вспомнить задачу об обычных методах наименьших квадратов — рекомендую прочитать статью об обычных методах наименьших квадратов:
Итак, у нас есть функция ошибок, которую нужно минимизировать:
где
w_0_0 и wx0 неизвестные термины; мы должны найти их. Как вы помните, решение нашей задачи — это минимально возможная ошибка. Аналитически это точка минимума функции ошибок. Поскольку функция дифференцируема, мы можем просто получить выражение для производной функции и сделать ее равной нулю.
Почему мы должны сделать его равным нулю?
Как вы помните, значение производной — это наклон касательной к некоторой точке:
На картинке выше мы видим две касательные в точках A и B. Очевидно, линии имеют некоторый наклон, а это означает, что значение абсолютной производной в этих точках больше 0.
Если значение производной равно нулю, это означает, что касательная в этой точке не имеет наклона; он параллелен оси X:
Это означает, что точка является минимумом функции.
Конечно, точка с такой касательной может быть и максимальной:
но из-за характера нашей проблемы наша функция ошибок имеет только глобальный минимум:
Хорошо, но функция состоит из двух неизвестных переменных, w_0_1 и wx0. Как найти производную такой функции?
Мы можем просто найти выражение для частной производной по каждому неизвестному члену и сделать выражения равными нулю:
В приведенном выше примере мы получили выражения только для одного термина y с одним признаком — термином x.
Представьте, что у нас много функций. Это означает, что x терминов может быть очень много. Кроме того, может быть не одно y — обычно может быть много значений. Давайте посмотрим на проблему с матричной точки зрения: есть матрица признаков, содержащая x значений, матрица весов, содержащая wзначения, и матрица результатов, содержащая y значений.
В соответствии с этим составим более общее выражение для частной производной:
где:
j— это индекс функции (или индекс веса функции), обозначает столбец в матрице функций.i— индекс наблюдения, обозначает индекс строки в матрице признаков.y_i— результат для i-го наблюдения (для i-й строки)x_i_j— это конкретное значение признака (значение из i-й строки j-го столбца в матрице признаков)Nэто ряд особенностей
Отлично, теперь мы знаем, как найти производную по весу признака на основе одного наблюдения, но у нас может быть много наблюдений. Согласно Обычной задаче наименьших квадратов, если у нас много наблюдений, мы должны просуммировать все значения ошибок для каждого наблюдения:
где M — количество наблюдений.
Рассмотрим факт суммирования для выражения частной производной:
Мы должны итеративно применить эту формулу к нашим данным, изменяя j термин в соответствии со следующим шаблоном: j = 0 … N-1, поскольку у нас есть N признаков и N весов.
Чтобы немного упростить задачу, мы можем выразить результаты, y значения, в виде матрицы Y размерности M x 1, признаков, x значений в виде матрицы X размерности M x N и весов, w значений, в виде матрицы W размерности N x 1. Перепишем приведенное выше уравнение в матричной записи:
Проверим размерность матриц в уравнении:
- Произведение
XиWдает нам матрицу-столбец размером M x 1, поскольку мы умножилиXматрицу размерности M x N наWматрицу размерности N x 1. Существует простое эмпирическое правило: размерность выходной матрицы равнаnumber of rows of the first matrixxnumber of columns of the second matrix, поэтому в результате получаем матрицу размерности M x 1. - Вычитание
YиXWдопустимо, поскольку оба термина являются матрицами с одинаковым количеством строк и столбцов. - Нам пришлось транспонировать матрицу
X, чтобы она соответствовала размерности, так какY-XWявляется матрицей размерности M x 1, а матрицаXимеет размер M x N: мы не можем умножить матрицу размерности M x N на матрицу размерности M x 1. После транспонирования матрицаXимеет размерность N x M, что идеально, и теперь мы можем найти произведение. В результате у нас есть матрица N x 1.
Отлично, размерность нашего уравнения соответствует. Наша цель — матрица W. Выразим это из уравнения.
Во-первых, давайте избавимся от -2, так как мы можем разделить обе части уравнения на это значение:
Тогда давайте избавимся от скобок. Для этого нам нужно умножить X (транспонированное) на Y и вычесть из него произведение X (транспонированное), X и W:
Теперь перенесем первый член уравнения в правую часть:
И последний шаг — теперь мы можем умножить обе части уравнения на:
В матричном мире умножить матрицу на ее инвертированную версию (исходную матрицу в степени минус один) означает то же самое, что умножить число на обратное число, например 5 * 1/5. В мире чисел последний пример приводит к 1. В матричном мире умножение на перевернутую матрицу аналогично; это приводит к единичной матрице, которая почти такая же, как 1 для чисел. Итак, после того как мы умножили обе части уравнения на инвертированную матрицу, мы имеем:
Мы получили формулу решения в закрытой форме для задачи линейной регрессии.
Давайте кодировать!
Используя библиотеку ml_linalg, мы можем легко создать программу для нахождения матрицы W по приведенной выше формуле.
Лучше придумать синтетические данные, которые легко проверить. Скажем, пусть следующие записи:
x1 | x2 ------- 2 | 3 4 | 6 6 | 12 8 | 24
будет нашей матрицей признаков X и следующими значениями:
y -- 13 26 48 88
будет наша матрица результатов Y
Веса признаков очень легко найти вручную — это 2 и 3:
2*2 + 3*3 = 13 4*2 + 6*3 = 26 6*2 + 12*3 = 48 8*2 + 24*3 = 88
Давайте применим нашу формулу к данным и проверим, хорошо ли она работает:
Последняя инструкция печатает следующее:
Matrix 2 x 1: (2.0000219345092773) (2.9999969005584717)
значения выглядят действительными. Это именно то, что мы ожидали (правда, с некоторыми ошибками округления).
Кажется, мы выполнили линейную регрессию всего в одной строке кода (строка 16 во фрагменте выше)!
Что может помешать нам использовать это простое и элегантное решение каждый раз?
Попробуем проанализировать сложность алгоритма. Он имеет шаг обращения матрицы кубической сложности — O(n³). Представьте, если ваша матрица признаков 100 000 на 1 000 000. Таким образом, общее количество итераций только для обращения матрицы составляет примерно (100 000 * 1 000 000)³! Нам не поможет даже архитектура SIMD, стоящая за библиотекой ml_linalg; слишком много итераций. Вот почему мы не можем каждый раз использовать закрытое решение для линейной регрессии.
Существует другой метод преодоления барьера больших данных, называемый градиентным спуском, но на сегодняшний день это слишком много. Оставим это для следующей статьи.
И это почти все. Теперь вы знаете, что такое закрытое решение для линейной регрессии!
Ваше здоровье :)
Вам также может понравиться следующее:
