Решение линейной регрессии: матричные уравнения и градиентный спуск, математический вывод и реализация NumPy

Формулы лучше отображаются на моем сайте,Мистер Лу.info/machine- сейчас..., Добро пожаловать в гости.

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

Normal Equation

Для функции потерь вы можете сделать ее производную равной нулю и найти экстремум функции потерь.

Одномерная линейная регрессия

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

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

Две приведенные выше формулы являются функциями потерьправильноиПроведите смещение. Когда производная равна 0, можно получить минимальное значение функции потерь, то есть оптимальное решение можно получить из двух приведенных выше формул.и.

Оптимальное решение:

в,, которыйсреднее значение .

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

Множественная линейная регрессия

В более общем случае признаки многомерны:

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

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

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

Обратите внимание, что выделенные жирным шрифтом символы в формуле представляют скаляры, а жирные — векторы или матрицы.

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

Множественная линейная регрессия обычно находит оптимальную гиперплоскость

Функция потерь множественной линейной регрессии по-прежнему рассчитывается с использованием квадрата «прогнозируемое значение — истинное значение», а приведенная выше формула представляет собой векторное представление функции потерь всей модели. Здесь появляется вертикальная линия, которую называют квадратом нормы L2. Норма обычно используется для векторов, а также является математическим символом, часто используемым в области машинного обучения.Следующая формула показывает векторКвадрат L2-нормы и ее производные.

Для вектора в формуле функции потерь линейной регрессииВозьмем производную, приравняв производную к нулю:

Приведенная выше формула представляет собой вектор, которое является матричным уравнением. Использование этого метода для поиска оптимального решения фактически является решением матричного уравнения, которое на английском языке называется Normal Equation.

У этого метода есть проблема, которая должна была быть упомянута в курсе линейной алгебры,Система уравнений может быть решена только в том случае, если она является полноранговой или положительно определенной. Что именно означает «полный ранг» или «положительная концентрация»? С точки зрения непрофессионала, данные в выборке должны быть достаточно богатыми и репрезентативными, чтобы иметь единственное решение матричного уравнения, иначе матричное уравнение будет иметь несколько наборов решений. Если функции имеют десятки тысяч измерений, но для обучения используются только десятки выборок, нам трудно получить удовлетворительное оптимальное решение.

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

Я потратил некоторое время на описание процесса решения линейной регрессии, и есть много формул.Как и многие друзья, я ненавидел смотреть на формулы.Когда я видел некоторые формулы, у меня была большая голова, поэтому я чувствовал, что машинное обучение очень сложное . Однако, если вы остановитесь и внимательно прочитаете, вы обнаружите, что эти формулы на самом деле используют более базовые части исчисления и линейной алгебры и не требуют дополнительных знаний.Друзья с научным и инженерным образованием должны быть в состоянии их понять. Кроме того, освежение знаний о матрицах и выводах помогает нам понять некоторые математические принципы глубокого обучения.

Градиентный спуск

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

В частности, мы можем рассмотреть использование метода градиентного спуска (Gradient Descent), этот метод из определенногоНачните с начального значения , а затем постепенно обновляйте веса, или каждый раз перезаписывайте исходные значения вновь вычисленными значениями:

здесьТакже известен как скорость обучения,это Градиент. В классе исчисления упоминалось, что в определенной точке функция быстрее всего изменяется по направлению градиента. Потому что мы хотим минимизировать функцию потерь, поэтому каждый раз спускаемся по градиенту,Опустите самое быстрое направление движения.

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

вернуться к скорости обученияначальство,Представляет, насколько мы уверены в градиенте в определенной точке. В целом,.Чем больше значение, тем быстрее мы хотим, чтобы функция потерь падала,Чем он меньше, тем медленнее мы хотим, чтобы функция потерь падала. еслиЕсли он установлен неправильно, каждый раз, когда шаг слишком велик, функция потерь может не быстро сходиться к минимальному значению. Как показано ниже, функция потерь также изо всех сил пытается сходиться к минимальному значению после длительного времени. В практических приложенияхОн часто меняется в зависимости от количества итераций, например, в начале он больше, а затем постепенно становится меньше.

Мы упоминали ранее,является вектором, предполагая, что онобъемный, обновление, мы одновременновсе размерызначение обновляется, гдеИзмерение должно использовать приведенную выше формулу обновления веса.

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

Для одной обучающей выборки правила обновления для каждого градиента следующие:

У этого правила есть несколько свойств, которые кажутся естественными и интуитивно понятными:

• обновленный размер спропорциональный.
• Когда мы сталкиваемся с предсказанным значением обучающей выборкииКогда истинное значение очень близко, вы обнаружите, что в основном нет необходимости изменять параметры; наоборот, если наше предсказанное значениеиЕсли истинное значение имеет большую погрешность (например, расстояние очень большое), то параметры нужно больше подгонять. Это также соответствует динамическому графику градиентного спуска, показанному ранее.

пакетный градиентный спуск

Когда имеется только одна обучающая выборка, мы выводим правило LMS. Когда тренировочный наборПри использовании обучающей выборки. При выводе необходимо добавить только данные нескольких обучающих выборок.

Таким образом, можно сделать вывод, что каждыйПроизводное от :

В частности, алгоритм такой:

В этом методе используются все образцы во всем обучающем наборе для обновления параметров на каждой итерации, также известный как пакетный градиентный спуск (BGD). Функция потерь для линейной регрессииЭто выпуклая квадратичная функция (Convex Quadratic Function), локальное минимальное значение выпуклой функции является глобальным минимальным значением, а оптимизационная задача линейной регрессии имеет только одно глобальное решение. То есть, если предположить, что скорость обучения неЕсли параметр слишком велик, а количество итераций достаточно велико, метод градиентного спуска всегда будет сходиться к глобальному минимуму.

Стохастический градиентный спуск

Пакетный градиентный спуск учитывает все выборки при обновлении параметров. Когда объем данных большой и признаков много, использовать весь объем данных в каждой итерации нереально, а сам полный объем данных содержит много избыточной информации, Чем больше объем данных, тем больше избыточная информация При поиске оптимального решения избыточная информация мало помогала. Компромисс состоит в том, чтобы каждый раз при обновлении параметров случайным образом брать частичную выборку. В крайнем случае выборка случайным образом выбирается на каждой итерации, и одна выборка используется для обновления параметров этой итерации.Этот алгоритм называется стохастическим градиентным спуском (SGD) следующим образом:

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

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

NumPy реализация градиентного спуска

Столько всего было выведено ранее, Обсуждайте дешево, Покажите какой-нибудь код. Затем мы реализуем модель линейной регрессии с использованием NumPy, используя пакетный градиентный спуск и стохастический градиентный спуск соответственно. В процессе реализации мы обнаружим, что некоторые проблемы являются техническими проблемами, которые не будут упомянуты при выводе формулы Например, данные в процессе расчета слишком велики и превышаютfloat64представимый диапазон. Инженерная реализация отражает разницу между теорией и практикой, и на самом деле часто именно эти инженерные детали определяют простоту использования фреймворков машинного обучения.

import numpy as np

class LinearRegression:

    def __init__(self):
        # the weight vector
        self.W = None

    def train(self, X, y, method='bgd', learning_rate=1e-2, num_iters=100, verbose=False):
        """
        Train linear regression using batch gradient descent or stochastic gradient descent

        Parameters
        ----------
        X: training data, shape (num_of_samples x num_of_features), num_of_samples rows of training sample, each training sample has num_of_features-dimension features.
        y: target, shape (num_of_samples, 1). 
        method: (string) 'bgd' for Batch Gradient Descent or 'sgd' for Stochastic Gradient Descent
        learning_rate: (float) learning rate or alpha
        num_iters: (integer) number of steps to iterate for optimization
        verbose: (boolean) if True, print out the progress

        Returns
        -------
        losses_history: (list) of losses at each training iteration
        """
        num_of_samples, num_of_features = X.shape

        if self.W is None:
            # initilize weights with values
            # shape (num_of_features, 1)
            self.W = np.random.randn(num_of_features, 1) * 0.001
        losses_history = []

        for i in range(num_iters):

            if method == 'sgd':
                # randomly choose a sample
                idx = np.random.choice(num_of_samples)
                loss, grad = self.loss_and_gradient(X[idx, np.newaxis], y[idx, np.newaxis])
            else:
                loss, grad = self.loss_and_gradient(X, y)
            losses_history.append(loss)

            # Update weights using matrix computing (vectorized)
            self.W -= learning_rate * grad

            if verbose and i % (num_iters / 10) == 0:
                print('iteration %d / %d : loss %f' %(i, num_iters, loss))
        return losses_history


    def predict(self, X):
        """
        Predict value of y using trained weights

        Parameters
        ----------
        X: predict data, shape (num_of_samples x num_of_features), each row is a sample with num_of_features-dimension features.

        Returns
        -------
        pred_ys: predicted data, shape (num_of_samples, 1)
        """
        pred_ys = X.dot(self.W)
        return pred_ys


    def loss_and_gradient(self, X, y, vectorized=True):
        """
        Compute the loss and gradients

        Parameters
        ----------
        The same as self.train function

        Returns
        -------
        tuple of two items (loss, gradient)
        loss: (float)
        gradient: (array) with respect to self.W 
        """
        if vectorized:
            return linear_loss_grad_vectorized(self.W, X, y)
        else:
            return linear_loss_grad_for_loop(self.W, X, y)


def linear_loss_grad_vectorized(W, X, y):
    """
    Compute the loss and gradients with weights, vectorized version
    """
    # vectorized implementation 
    num_of_samples = X.shape[0]
    # (num_of_samples, num_of_features) * (num_of_features, 1)
    f_mat = X.dot(W)

    # (num_of_samples, 1) - (num_of_samples, 1)
    diff = f_mat - y 
    loss = 1.0 / 2 * np.sum(diff * diff)
    
    # {(num_of_samples, 1).T dot (num_of_samples, num_of_features)}.T
    gradient = ((diff.T).dot(X)).T

    return (loss, gradient)


def linear_loss_grad_for_loop(W, X, y):
    """
    Compute the loss and gradients with weights, for loop version
    """
    
    # num_of_samples rows of training data
    num_of_samples = X.shape[0]
    
    # num_of_samples columns of features
    num_of_features = X.shape[1]
    
    loss = 0
    
    # shape (num_of_features, 1) same with W
    gradient = np.zeros_like(W) 
    
    for i in range(num_of_samples):
        X_i = X[i, :] # i-th sample from training data
        f = 0
        for j in range(num_of_features):
            f += X_i[j] * W[j, 0]
        diff = f - y[i, 0]
        loss += np.power(diff, 2)
        for j in range(num_of_features):
            gradient[j, 0] += diff * X_i[j]
            
    loss = 1.0 / 2 * loss

    return (loss, gradient)

использованная литература

1. Andrew Ng: CS229 Lecture Notes
2. Чжоу Чжихуа: «Машинное обучение»
3. Post-Line Sequence.GitHub.IO/2015/03/31/…