Рохан # 3: Вывод нормального уравнения с использованием матричного исчисления
Понимание аналитического решения линейной регрессии.
Это третья запись в моем путешествии по расширению моих знаний об искусственном интеллекте в 2016 году. Узнайте больше о моих мотивах в этом вводном посте.
Прежде чем я начну изучать новые алгоритмы / методы машинного обучения и компании, я хочу сначала уточнить свои текущие знания. Частично это связано с заполнением пробелов в контенте, который я не смог понять или исследовать во время моих предыдущих усилий в области искусственного интеллекта. Сегодня я обращусь к нормальному уравнению в контексте регрессии. Я не собираюсь подробно изучать машинное обучение (но вы можете узнать о нем больше в моих предыдущих двух постах), поэтому эта статья предполагает базовое понимание алгоритмов регрессии контролируемого машинного обучения. Это также предполагает некоторый фон для матричного исчисления, но интуиции как исчисления, так и линейной алгебры по отдельности будет достаточно.
Сегодня мы пытаемся вывести и понять это тождество / уравнение:
Напомним, что управляемый регрессионный алгоритм машинного обучения исследует набор точек данных в декартовом пространстве экземпляров и пытается определить модель, которая «соответствует» указанному набору данных с высокой точностью. В этом контексте модель - это любая линейная или нелинейная функция.
Как видите, синяя линия отражает тенденцию (то есть, как точки данных перемещаются по пространству экземпляра) в этом двухмерном шумном примере. Термин «остатки», который в основном используется в статистике и редко в машинном обучении, может быть новым для многих из вас. Остатки, вертикальные линии серого цвета, представляют собой расстояния между каждой из y-координат точек данных и их соответствующими прогнозами на модели. При TV = 0 наша модель предсказала значение Продажи = 6,5, хотя фактическое значение было Продажи = 1 (я нахожу балую это!). Следовательно, остаток для этого экземпляра равен 5,5.
Мы интуитивно предполагаем, что меньший остаток предпочтительнее большего остатка, однако модель может не (и, опять же, мы не можем захотеть переобучать) быть способной приспособиться к изменению своих выходных данных для одну точку данных и сохраните ее выход постоянным для всех остальных точек данных. Вместо этого мы говорим, что хотим рассчитать минимальную среднюю невязку. То есть мы хотим минимизировать значение суммирования остатка каждой точки данных, деленного на количество точек данных. Мы можем обозначить это как «функцию стоимости» для нашей модели, а результат этой функции - как «стоимость».
Последний шаг - оценить, как мы используем остаток в функции затрат (основная единица функции затрат). Простое суммирование остатков (которые представляют собой простые разности / вычитания) на самом деле не подходит, потому что оно может привести к отрицательным значениям и не сможет уловить идею декартова «расстояния» (что привело бы к тому, что наша окончательная стоимость быть неточным). Правильным решением было бы заключить абсолютное значение в выражение вычитания. Другой подход - возвести выражение в квадрат. Последний обычно предпочтительнее из-за его математического удобства при выполнении дифференциального исчисления.
OK. Подойдем к этому математически. Во-первых, мы определим нашу модель как:
Это почти что y = mx + c, но в многомерном пространстве, где x является вектором значений. Приведенная выше диаграмма разброса продаж телепрограмм является двухмерной и, следовательно, имеет один x: TV, однако это не всегда так.
Обратите внимание, что это «скалярное произведение» между векторами Θ и x. Мы можем переписать это, используя удобство записи линейной алгебры:
Θ хранит реальные коэффициенты (или «веса») входных характеристик x и, следовательно, имеет ту же размерность, что и x. Важно отметить, что мы добавляем к вектору x префикс 1, чтобы мы могли добавить поддержку постоянного члена в нашу модель.
Теперь мы можем ожидать, что подставим любое значение x для ТВ и получим точный прогноз количества продаж, которые мы планируем сделать. . Единственная проблема в том, что мы должны вычислить значения Θ, которые образуют точную модель. Как люди, мы можем угадать несколько значений, но а) это не применимо к приложениям с более высокой размерностью б) компьютер не может делать «догадки» в) мы хотим найти наиболее точные Θ .
x представляет собой любую отдельную точку данных, которую мы вводим для получения прогноза. Теперь мы можем определить X как вектор всех входных данных для точек данных A-Priori, которые мы используем для формирования нашей модели. Обратите внимание, что каждая точка данных является вектором сама по себе, поэтому X - это большая матрица (обозначаемая «матрица плана»), в которой каждая строка (мы используем обозначение X произвольно надстрочный index i) - это один вектор x. y - это, наоборот, выходы для этих априорных точек данных. Мы определяем m как количество строк в X или, иначе, количество точек данных A-Priori. В машинном обучении это называется «обучающий набор».
Надеюсь, ясно, что здесь Θ по существу определяет модель. Все остальное остается неизменным. Итак, чтобы найти наиболее точную модель, нам нужно найти Θ с наименьшими затратами (наименьшая средняя невязка - поверх функции - как указывалось ранее). Обозначим нашу функцию затрат в математической записи:
Остаток - это просто разница между фактическим значением и прогнозируемым значением (входными значениями, подаваемыми через модель):
Ранее мы обсуждали различные способы взаимодействия с остатком для создания основной единицы затрат. Разница в квадрате является предпочтительной:
Вставка этого выражения вместе с функцией стоимости оставляет нам:
Обратите внимание, как мы увеличили общее выражение вдвое. Мы делаем это, как обычно, для математического удобства.
К сожалению, прежде чем мы сможем продолжить, нам нужно будет представить функцию стоимости в векторизованном (с использованием линейной алгебры) формате. Вместо явного суммирования квадратных остатков мы можем вычислить квадратные остатки с помощью матричных операций.
Если бы мы собрали все остатки в один вектор, это выглядело бы примерно так:
Мы можем разделить это дальше:
Следующий:
Теперь давайте упростим левый вектор:
А потом:
И бац, мы ясно видим, что это упрощает:
Но мы забываем кое-что важное; каждый остаток возводится в квадрат. Это создает проблему, потому что мы не можем просто возвести в квадрат общее выражение XΘ - y. Почему? Проще говоря, квадрат вектора / матрицы не равен квадрату каждого из его внутренних значений. Итак - что мы на самом деле хотим делать? Мы хотим взять каждое значение в векторе XΘ - y и умножить его само на себя. Вот что мы можем сформулировать:
Если мы хотим, чтобы каждое значение в XΘ - y умножалось само на себя, мы можем использовать второй XΘ - y и умножить каждое значение в первом векторе на значение с тем же индексом во втором векторе. Это точечный продукт. Напомним, что когда мы формулировали нашу гипотезу / модельную функцию, мы взяли скалярное произведение двух векторов как умножение между одним из транспонированных векторов и другим вектором. Следовательно, чтобы получить квадратные остатки, мы получаем следующее выражение:
Добавив член деления в начало выражения, мы должны получить окончательное выражение линейной алгебры / векторизованное выражение для нашей функции стоимости:
Итак, теперь, когда мы можем «забить» Θ, конечная цель проста:
Другими словами, найдите Θ, который минимизирует выход функции стоимости и, следовательно, представляет наиболее точную модель с наименьшей средней невязкой.
Итак, как мы подойдем к этому? Надеюсь, это станет ясно из этого графика:
Верно - с помощью линейной регрессии можно доказать, что Стоимость (Θ) является выпуклой функцией! Итак, на данный момент это кажется довольно простым: применить дифференциальное исчисление для решения с наименьшими затратами. Давайте начнем!
Мы собираемся дифференцировать, как и ожидалось, Θ. На этом этапе мы можем отказаться от члена деления, потому что, когда мы приравниваем производную к нулю, она обнуляется.
Мы снова собираемся упростить функцию стоимости (RHS), на этот раз используя тождество распределения транспонирования матрицы, в частности (AB) ’≡ B’A’:
РЕДАКТИРОВАТЬ: здесь я ошибаюсь и делаю (AB) ’= A’B’, поэтому мне приходится переупорядочивать (что в противном случае было бы незаконным из-за некоммутативного характера умножения матриц). Это не имеет значения при определении окончательной производной.
На этом этапе мы можем раскрыть две скобки:
Поскольку векторы y и XΘ имеют одинаковую размерность и оба являются векторами, они (или, скорее, транспонирование одного в другой) удовлетворяют свойству коммутативности (которое гласит, что * b = b * a - если вы не знали, это свойство не относится к многомерным матрицам). Следовательно, два средних члена можно объединить в один термин:
Давайте попробуем удалить все экземпляры транспонирования (опять же, используя идентификаторы распределения):
Мы можем удалить последний член, потому что при выводе по отношению к Θ он не имеет никакого эффекта и производная равна нулю (поскольку термин Θ не используется):
Давайте сначала оценим левый член:
Обратите внимание, что члены X - это просто константы / скаляры в этой частной производной, поэтому мы можем «вынуть это» (используя правила дифференцирования) следующим образом:
Используя следующее скалярное тождество матричного исчисления:
РЕДАКТИРОВАТЬ: Я хочу добавить здесь интуицию к правилу. Вспомните, что вектор, умноженный на его транспонирование, дает вектор, в котором каждое значение возведено в квадрат, но это не то же самое, что квадрат самого вектора. Если бы мы взяли производную этого вектора по отношению к исходному вектору, мы применили бы основной принцип, который гласит, что мы получаем по каждому значению в векторе отдельно:
Это упрощает:
Итак, теперь, используя это тождество, мы можем решить производную левого члена следующим образом:
Давайте двигаться дальше. Правильный термин решить намного проще:
Используя следующее правило сопряженного транспонирования матричного исчисления:
РЕДАКТИРОВАТЬ: Я надеюсь, что интуиция, лежащая в основе этой идентичности, станет ясной с использованием тех же принципов, что и в предыдущем объяснении.
Мы это видим:
Теперь мы можем объединить два члена вместе, чтобы сформулировать окончательную производную для функции стоимости:
Напомним, что единственной поворотной точкой - точкой, где мгновенный градиент равен нулю - для выпуклой функции будет глобальный минимум / максимум функция. Итак, мы устанавливаем производную равной нулю и, следовательно, находим указанную точку минимума:
Теперь мы подставляем нашу вычисленную производную:
С некоторой базовой алгеброй мы в пути !:
Замедлять, ! Поскольку матрицы не коммутативны, мы не можем изолировать Θ, просто «опустив» члены X. Вместо этого мы умножаем обе части на обратное указанное число (помните, что деление такое же, как умножение обратного):
Любое значение, обратное умножению на само значение, равно 1, поэтому…:
Вот оно - наконец! Это наше решение для Θ, где стоимость минимальна.
Слон в комнате - почему это не предпочтительнее градиентного спуска‽ Какое элегантное решение, скажете вы. Что ж, вот основная причина: вычисление кажущейся безобидной инверсии этой матрицы (m * n) на (n * m) с помощью самого эффективного на сегодняшний день алгоритма информатики составляет кубическая временная сложность! Это означает, что по мере увеличения размеров X количество операций, необходимых для вычисления окончательного результата, увеличивается по кубической тенденции. Если X был довольно маленьким и особенно имел низкое значение для n / не имел больших размеров, то можно было бы использовать нормальное уравнение. Но для любого промышленного приложения с большими наборами данных нормальное уравнение может занять чрезвычайно - иногда бессмысленно - много времени.
Надеюсь, это было для вас наградой. Это определенно было для меня. Это был мой первый шаг к матричному исчислению, который оказался стимулирующим вызовом. Следующая статья будет еще более смелой: полный математический обзор обратного распространения ошибки! Тогда увидимся!
