Является ли коэффициент ошибок выпуклой функцией лямбда-параметра регуляризации?

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

Интуитивно понятно, что между данными и обучающим набором не должно быть математически необходимых отношений. Мы должны быть в состоянии найти данные обучения, для которых модель изначально плоха, улучшается с некоторой регуляризацией, а затем снова ухудшается. Кривая ошибки не может быть выпуклой в этом случае - по крайней мере, если мы сделаем параметр регуляризации от до . $0$ $\infty$

Обратите внимание, что выпуклость не эквивалентна наличию уникального минимума! Тем не менее, аналогичные идеи предполагают, что возможны несколько локальных минимумов: во время регуляризации сначала подобранная модель может улучшиться для некоторых данных обучения, в то время как незначительно изменяется для других данных обучения, а затем позже она улучшится для других данных обучения и т. Д. Сочетание таких обучающих данных должно давать несколько локальных минимумов. Для простоты анализа я не буду пытаться показать это.

Изменить (чтобы ответить на измененный вопрос)

Я был настолько уверен в анализе, представленном ниже, и интуиции за ним, что я решил найти пример самым грубым способом: я сгенерировал небольшие случайные наборы данных, запустил на них лассо, вычислил общую квадратичную ошибку для небольшого тренировочного набора, и построил свою кривую ошибок. Несколько попыток дали одну с двумя минимумами, которые я опишу. Векторы имеют вид для признаков и и отклика . $(x_1,x_2,y)$ $x_1$ $x_2$ $y$

Тренировочные данные

(1, 1, - 0.1), (2, 1, 0.8), (1, 2, 1.2), (2, 2, 0.9)

$(1,1,-0.1),\ (2,1,0.8),\ (1,2,1.2),\ (2,2,0.9)$

Тестовые данные

(1, 1, 0.2), (1, 2, 0.4)

$(1,1,0.2),\ (1,2,0.4)$

Лассо был запущен с использованием glmnet::glmmetin R, все аргументы остались по умолчанию. Значения на оси x являются обратными величинами значений, сообщаемых этим программным обеспечением (поскольку оно параметризует свой штраф с ). $\lambda$ $1/\lambda$

Кривая ошибки с несколькими локальными минимумами

Анализ

Давайте рассмотрим любой метод регуляризации подгонки параметров к данным и соответствующим ответам которые имеют эти свойства, общие для регрессии Риджа и Лассо: $\beta=(\beta_1, \ldots, \beta_p)$ $x_i$ $y_i$

(Параметризация) Метод параметризуется действительными числами , причем нерегулярная модель соответствует . $\lambda \in [0, \infty)$ $\lambda=0$
(Непрерывность) Оценка параметров непрерывно зависит от и предсказанные значения для любых функций непрерывно меняются в зависимости от . $\hat\beta$ $\lambda$ $\hat\beta$
(Усадка) Как , . $\lambda\to\infty$ $\hat\beta\to 0$
(Конечность) Для любого вектора признаков , а , предсказание . $x$ $\hat\beta\to 0$ $\hat y(x) = f(x, \hat\beta) \to 0$
(Монотонная ошибка) Функция ошибки сравнивая любое значение к значению предсказанного , , возрастает с несоответствием так что, с некоторым злоупотреблением нотации, мы можем выразить как . $y$ $\hat y$ $\mathcal{L}(y, \hat y)$ $|\hat y - y|$ $\mathcal{L}(|\hat y - y|)$

(Ноль в можно заменить любой константой.) $(4)$

Предположим , что данные таковы , что начальная (нерегуляризованное) оценка параметра не равен нулю. Давайте конструкт набор данных обучения , состоящий из одного наблюдения , для которых . (Если невозможно найти такой , тогда начальная модель не будет очень интересной!) Установите $\hat\beta(0)$ $(x_0, y_0)$ $f(x_0, \hat\beta(0))\ne 0$ $x_0$ . $y_0=f(x_0, \hat\beta(0))/2$

Допущения означают ошибки кривой имеет следующие свойства: $e: \lambda \to \mathcal{L}(y_0, f(x_0, \hat\beta(\lambda))$

(изза выбора ). $e(0) = \mathcal{L}(y_0, f(x_0, \hat\beta(0)) = \mathcal{L}(y_0, 2y_0) = \mathcal{L}(|y_0|)$ $y_0$
(потому чтокак , , откуда ). $\lim_{\lambda\to\infty}e(\lambda) = \mathcal{L}(y_0, 0) = \mathcal{L}(|y_0|)$ $\lambda\to\infty$ $\hat\beta(\lambda)\to 0$ $\hat{y}(x_0)\to 0$

Таким образом, его граф непрерывно соединяет две одинаково высокие (и конечные) конечные точки.

Качественно, есть три возможности:

Прогноз для тренировочного набора никогда не меняется. Это маловероятно - практически любой выбранный вами пример не будет иметь этого свойства.
Некоторые промежуточные предсказания для являются хуже , чем в начале или в пределе . Эта функция не может быть выпуклой. $0\lt \lambda \lt \infty$ $\lambda=0$ $\lambda\to\infty$
Все промежуточные прогнозы лежат между и . Непрерывность подразумевает наличие хотя бы одного минимума , вблизи которого должно быть выпуклым. Но поскольку приближается к конечной постоянной асимптотически, она не может быть выпуклой при достаточно большом . $0$ $2y_0$ $e$ $e$ $e(\lambda)$ $\lambda$

Вертикальная пунктирная линия на рисунке показывает, где график меняется с выпуклого (слева) на невыпуклый (справа). (Существует также область невыпуклости вблизи на этом рисунке, но это не обязательно будет иметь место в общем.) $\lambda\approx 0$

Whuber
источник

Спасибо за ваш сложный ответ. Если возможно, просмотрите вопрос, как я отредактировал, и обновите ваш ответ.

rf7

Отличный ответ (+1). На практике, я думаю, что часто не так уж и мало данных о тренировках и тестах. Изменится ли вывод этого ответа, когда будет достаточно данных для обучения и тестирования, взятых из одного (фиксированного и достаточно регулярного) распределения? В частности, при этом сценарии существует ли уникальный локальный минимум с высокой вероятностью?

user795305

@Ben Важно не количество контрольных точек: этот результат полностью зависит от распределения контрольных точек относительно распределения тренировочных точек. Поэтому вопрос «с высокой вероятностью» не будет отвечать без принятия некоторых конкретных предположений о многомерном распределении переменных регрессора. Кроме того, при наличии множества переменных этот феномен множественных локальных минимумов будет гораздо более вероятным. Я подозреваю, что случайный выбор большого набора тестов (с количеством наблюдений во много раз больше переменных) часто может иметь уникальный глобальный минимум.

whuber

(x, y)

$(\mathbf x, y)$

n

$n$

n \to \infty

$n \to \infty$

p

$p$

n

$n$

$\newcommand{\dbeta}{\frac{\partial}{\partial \lambda} \hat\beta_\lambda}$ $\newcommand{\ddbeta}{\frac{\partial^2}{{\partial \lambda}^2} \hat\beta_\lambda}$

Этот ответ конкретно касается лассо (и не относится к регрессии гребня).

Настроить

$p$ $n$ $m$

$X_{(1)} \in \mathbb{R}^{n \times p}$ $y_{(1)} \in \mathbb{R}^n$

\begin{matrix} (1) & {\hat{β}}_{λ} = \arg min_{β \in R^{p}} ‖ y_{(1)} - X_{(1)} β ‖_{2}^{2} + λ ‖ β ‖_{1}, \end{matrix}

$\hat\beta_\lambda = \arg\min_{\beta \in \mathbb{R}^p} \|y_{(1)} - X_{(1)} \beta\|_2^2 + \lambda \|\beta\|_1, \tag{1}$

{\hat{β}}_{λ}

$\hat\beta_\lambda$

X_{(2)} \in R^{m \times p}

$X_{(2)} \in \mathbb{R}^{m \times p}$

y_{(2)} \in R^{m}

$y_{(2)} \in \mathbb{R}^m$

\begin{matrix} (2) & \hat{λ} = \arg min_{λ \in R_{+}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}, \end{matrix}

$\hat\lambda = \arg\min_{\lambda \in \mathbb{R}_+} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2, \tag{2}$

e (λ) = ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}

$e(\lambda) = \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2$

{\hat{β}}_{\hat{λ}}

$\hat\beta_{\hat\lambda}$

расчет

$(2)$ $X$ $y$

\begin{aligned} \frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} & = \frac{\partial}{\partial λ} {- 2 y_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} + 2 {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ}} \\ = - 2 y_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 {({\hat{β}}_{λ})}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 \frac{\partial}{\partial λ} {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)}^{T} \frac{\partial}{\partial λ} {\hat{β}}_{λ} \\ = - 2 {{(y_{(2)} - X_{(2)} {\hat{β}}_{λ})}^{T} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} - ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2}} . \end{aligned}

$\begin{align*} \frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 & = \frac{\partial}{\partial \lambda} \left\{ -2 y_{(2)}^T X_{(2)} \dbeta + 2 \hat\beta_\lambda^T X_{(2)}^T X_{(2)} \dbeta \right\} \\ & = -2 y_{(2)}^T X_{(2)} \ddbeta + 2 \left( \hat\beta_\lambda \right)^T X_{(2)}^T X_{(2)} \ddbeta + 2 \dbeta^T X_{(2)}^T X_{(2)}^T \dbeta \\ & = -2 \left\{ \left( y_{(2)} - X_{(2)} \hat\beta_\lambda \right)^T \ddbeta - \|X_{(2)} \dbeta\|_2^2 \right\}. \end{align*}$

{\hat{β}}_{λ}

$\hat\beta_\lambda$

λ \notin K

$\lambda \not\in K$

K

$K$

\frac{\partial}{\partial λ} {\hat{β}}_{λ}

$\dbeta$

\frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ}

$\ddbeta$

λ \notin K

$\lambda \not\in K$

\frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} = 2 ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2},

$\frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 = 2 \|X_{(2)} \dbeta\|_2^2,$

λ

$\lambda$

Вывод

$X_{(2)}$ $\{X_{(1)}, y_{(1)} \}$ $X_{(2)} \dbeta \neq 0$ $\lambda < \lambda_\max$ $e(\lambda)$ $\mathbb{R} \setminus K$ $\hat\beta_\lambda$ $e(\lambda)$

Наконец, из лассо-дуала мы знаем, что $\|X_{(1)} \hat\beta_\lambda\|_2^2$ $\lambda$ $\|X_{(2)} \hat\beta_\lambda\|_2^2$ $e(\lambda)$ $\mathcal{L} \left( X_{(1)} \right) = \mathcal{L} \left( X_{(2)} \right)$

user795305
источник

Вы полагаетесь только на

является непрерывной кусочно - линейной функцией

\hat{β}

$\hat\beta$

λ

$\lambda$

\hat{e}

$\hat e$

\hat{β} (λ) = | λ - [λ] |

$\hat\beta(\lambda)=|\lambda-[\lambda]|$

[]

$[]$

y_{(2)} = 0

$y_{(2)}=0$

X_{(2)} = 1

$X_{(2)}=1$

\hat{e} (λ) = \hat{β} (λ)^{2}

$\hat {e}(\lambda)=\hat\beta(\lambda)^2$

@whuber Хорошая мысль! Благодаря! Я скоро отредактирую этот пост.