3. Линейная регрессия

Рассмотрим задачу линейной регресии

\[ L(w) = (y - Xw)^T(y - Xw) \to \min_{w}. \]

а) Найдите \(L(w)\), выведите формулу для оптимального \(w\).

Решение

Ради интереса убедимся, что перед нами в качестве функции потерь используется именно MSE, в качестве \(x_i\) будем обозначать \(i-\)ую строчку матрицы \(X\)

\[\begin{split} (y - Xw)^T(y - Xw) = \begin{pmatrix} y_1 - x_1^Tw & \ldots & y_n - x_n^Tw \end{pmatrix} \begin{pmatrix} y_1 - x_1^Tw \\ \ldots \\ y_n - x_n^Tw \end{pmatrix} = \sum_{i=1}^n (y_i - x_i^Tw)^2. \end{split}\]

Найдём дифференциал для нашей функции потерь, держим в голове что производная берётся по вектору \(w\)

\[\begin{multline*} d L = d[(y - Xw)^T(y - Xw)] = \\ = d[(y - Xw)^T] \cdot (y - Xw) + (y - Xw)^T \cdot d[(y - Xw)] = \\ = d[(-Xw)^T] (y - Xw) - (y - Xw)^TX \cdot dw = \\ = - dw^T X^T (y - Xw) - (y - Xw)^TX dw = -2 (y - Xw)^TX dw. \end{multline*}\]

Тут мы воспользовались тем, что \( dw^T X^T (y - Xw)\) это скаляр и его можно транспонировать. Производная найдена.

\[ 2X^T(y-Xw) = 0 \qquad X^Ty = X^TX w \qquad w = (X^TX)^{-1} X^Ty. \]

При решении системы мы сделали предположение, что матрица \(X^TX\) обратима. Это так, если в матрице \(X\) нет линейно зависимых столбцов, а также наблюдений больше чем переменных.

б) Как выглядит шаг градиентного спуска в матричном виде?

Решение

Шаг градиентного спуска будет выглядеть как

\[ w_t = w_{t-1} + \gamma \cdot 2X^T(y-Xw). \]

Здесь \(\gamma\) — это скорость обучения. Приравняем производную к нулю, чтобы найти минимум для \(w\). Получается система уравнений

в) Найдите \(d^2L(w)\). Убедитесь, что мы действительно в точке минимума.

Решение

Найдём вторую производную

\[ d[-2X^T(y-Xw)] = 2X^TX dw. \]

Выходит, что \(H = 2X^TX\). Так как матрица \(X^TX\) положительно определена, по критерию Сильвестра, мы находимся в точке минимума.

Матрица \(X^TX\) положительно определена по определению. Если для любого вектора \(v \ne 0\) квадратичная форма \(v^T X^TX v > 0\), матрица \(X^TX\) положительно определена. При перемножении \(Xv\) у нас получается вектор. Обозначим его как \(z\), значит \(v^T X^TX v = z^T z = \sum_{i=1}^n z_i^2 > 0\).

Выпишем в явном виде второй дифференциал

\[ d^2 L = dw^T 2X^TX dw. \]

г) В случае Ridge-регрессии минимизируется функция со штрафом:

\[ L(w) = (y - Xw)^T(y - Xw) + \lambda w^Tw, \]

где \(\lambda\) — положительный параметр, штрафующий функцию за слишком большие значения \(w\). Как будут выглядеть \(dL(w)\), \(d^2L(w)\) и формулу для оптимального \(w\)?

Решение

Надо аккуратно проделать ровно то же самое, что мы сделали выше. Приведём тут основные формулы для расчётов.

\[\begin{equation*} \begin{aligned} & dL = 2 (y - Xw)^TX dw + 2\lambda w^T dw \\ & \nabla_w L(w) = 2 X^T (Xw - y) + 2\lambda w \\ & w = (X^TX + \lambda I)^{-1} X^Ty \\ & w_t = w_{t-1} - \gamma \cdot (2 X^T (Xw_{t-1} - y) + 2\lambda w_{t-1}) \\ & d^2 L = d{w^T}(2X^TX + 2\lambda)dw \\ & H = 2X^TX + 2\lambda \text{ положительно определена} \end{aligned} \end{equation*}\]