Может ли быть несколько локальных оптимальных решений, когда мы решаем линейную регрессию?

19

Я прочитал это утверждение на одном старом истинном / ложном экзамене:

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

Решение: Неверно

У меня вопрос, какая часть этого вопроса не так? Почему это утверждение неверно?

Анжела Миноу
источник

Ответы:

8

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

Подводя итог некоторым идеям из комментариев к другим ответам, я хотел бы отметить, что есть как минимум два способа, которыми «линейная регрессия» может привести к неуникальным решениям - не только теоретически, но и на практике.

Недостаток идентификации

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

Рассмотрим, например, регрессирует против х и у (с перехватом) для ( х , у , г ) данные ( 1 , - 1 , 0 ) , ( 2 , - 2 , - 1 ) , ( 3 , - 3 , - 2 ) . Одним из решений является г = 1 + у . Другой гzxy(x,y,z)(1,-1,0),(2,-2,-1),(3,-3,-2)Z^знак равно1+Y . Чтобы увидеть, что должно быть несколько решений, параметризовать модель с тремя действительными параметрами ( λ , µ , ν ) и ошибочным членом ε в видеZ^знак равно1-Икс(λ,μ,ν)ε

Zзнак равно1+μ+(λ+ν-1)Икс+(λ-ν)Y+ε,

Сумма квадратов остатков упрощается до

SSRзнак равно3μ2+24μν+56ν2,

(Это ограничивающий случай целевых функций, возникающих на практике, например, обсуждаемый в разделе «Может ли эмпирический гессиан М-оценки быть неопределенным?» , Где вы можете прочитать подробный анализ и просмотреть графики функции.)

Поскольку коэффициенты квадратов ( и 56 ) являются положительными и определитель 3 × 56 - ( 24 / 2 ) 2 = 24 является положительным, то это положительно полуопределена квадратичной формой ( ц , v , , Л ) . Оно минимизируется, когда μ = ν = 0 , но λ может иметь любое значение. Поскольку целевая функция ССР не зависит от λ3563×56-(24/2)2знак равно24(μ,ν,λ)μзнак равноνзнак равно0λSSRλни его градиент (ни какие-либо другие производные). Следовательно, любой алгоритм градиентного спуска - если он не вносит каких-либо произвольных изменений направления - установит для решения значение равным любому начальному значению.λ

Даже когда градиентный спуск не используется, решение может варьироваться. В R, например, есть два простых, эквивалентные способы указать эту модель: как z ~ x + yили z ~ y + x. Первый дает г = 1 - х , но второе дает г = 1 + у . Z^знак равно1-ИксZ^знак равно1+Y

> x <- 1:3
> y <- -x
> z <- y+1

> lm(z ~ x + y)
Coefficients:
(Intercept)            x            y  
          1           -1           NA  


> lm(z ~ y + x)
Coefficients:
(Intercept)            y            x  
          1            1           NA 

( NAЗначения следует интерпретировать как нули, но с предупреждением о том, что существует несколько решений. Предупреждение стало возможным благодаря предварительному анализу, выполняемому Rнезависимо от метода его решения. Метод градиентного спуска, скорее всего, не обнаружит возможность нескольких решений, хотя хороший предупредит вас о некоторой неуверенности, что она достигла оптимального значения.)

Ограничения параметров

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

Очень простой пример дает задача оценки «среднего» для данных - 1 , 1 с учетом ограничения | μ | 1 / 2 . Это моделирует ситуацию, которая является своего рода противоположностью методов регуляризации, таких как Регрессия Риджа, Лассо или Эластичная Сеть: она настаивает на том, чтобы параметр модели не становился слишком маленьким. (На этом сайте появились различные вопросы о том, как решить проблемы регрессии с такими ограничениями параметров, показывая, что они возникают на практике.)μ-1,1|μ|1/2

В этом примере есть два решения наименьших квадратов, оба одинаково хороши. Их находят путем минимизации учетом ограничения | μ | 1 / 2 . Два раствора μ = ± 1 / 2 . Более чем одно решение может возникнуть из - за ограничение делает параметр домена М ( - , - 1 / 2 ] (1-μ)2+(-1-μ)2|μ|1/2μзнак равно±1/2 невыпуклый:μ(-,-1/2][1/2,)

График суммы квадратов против $ \ mu $

Парабола является графиком (строго) выпуклой функции. Толстая красная часть является частью ограничивается областью : она имеет две низкие точки , в ц = ± 1 / 2 , где сумма квадратов составляет 5 / 2 . Остальная часть параболы (показана пунктирной) удаляется ограничением, тем самым исключая ее уникальный минимум из рассмотрения.μμзнак равно±1/25/2

μзнак равно1/2μзнак равно-1/2

Та же самая ситуация может произойти с большими наборами данных и в более высоких измерениях (то есть с большим количеством параметров регрессии, чтобы соответствовать).

Whuber
источник
1
е(Икс,Y)знак равно(Икс-Y)2Yзнак равноИкс
1
@ Kjetil Спасибо, это правда. Хитрость заключается в том, чтобы показать, как такие функции действительно возникают в регрессионных ситуациях. Ваша функция - именно то, что послужило вдохновением для первого примера, который я предложил.
whuber
Наглядный пример stats.stackexchange.com/a/151351/171583 .
ayorgo
2

Боюсь, на ваш вопрос нет бинарного ответа. Если линейная регрессия является строго выпуклой (без ограничений на коэффициенты, без регуляризатора и т. Д.), То градиентный спуск будет иметь уникальное решение и будет глобальным оптимумом. Градиентный спуск может и даст несколько решений, если у вас есть невыпуклая проблема.

Хотя OP запрашивает линейную регрессию, приведенный ниже пример демонстрирует минимизацию наименьших квадратов, хотя нелинейная (в отличие от линейной регрессии, которую хочет OP) может иметь несколько решений, а градиентный спуск может возвращать другое решение.

Я могу показать эмпирически на простом примере, что

  1. Сумма квадратов ошибок может быть не выпуклой, поэтому иметь несколько решений
  2. Метод градиентного спуска может обеспечить несколько решений.

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

введите описание изображения здесь

весa

a12знак равно9,a13знак равно1/9,a23знак равно9,a31знак равно1/9

мяNямяZе (9-вес1вес2)2+(19-вес1вес3)2+(19-вес2вес1)2+(9-вес2вес3)2+(9-вес3вес1)2+(19-вес3вес2)2

Вышеуказанная проблема имеет 3 различных решения, и они заключаются в следующем:

весзнак равно(0,670,0,242,0,080),обJзнак равно165,2

весзнак равно(0,080,0,242,0,670),обJзнак равно165,2

весзнак равно(0,242,0,670,0,080),обJзнак равно165,2

Как показано выше, задача наименьших квадратов может быть невыпуклой и иметь многократное решение. Тогда вышеупомянутая проблема может быть решена с использованием метода градиентного спуска, такого как Microsoft Excel Excel Solver, и каждый раз, когда мы запускаем, мы получаем другое решение. поскольку градиентный спуск является локальным оптимизатором и может застрять в локальном решении, нам нужно использовать разные начальные значения, чтобы получить истинные глобальные оптимумы. Такая проблема зависит от начальных значений.

предсказатель
источник
2
Я не думаю, что это отвечает на вопрос OP, потому что OP спрашивает конкретно о линейной регрессии , а не об оптимизации вообще.
Sycorax говорит восстановить Monica
1
Нет, это не так, но просто попытка указать на проблемы с оптимизацией, будет обновлять с предостережениями
прогнозист
@ user777 ты прав. это очень актуальный вопрос на старом экзамене от MIT. Я уверен, что ответ неверен благодаря прогнозу.
Анжела Миноу
так ты уверен, что я прав?
Анжела Миноу
@AnjelaMinoeu, я обновил свой ответ.
синоптик
1

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

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

Владислав Довгальец
источник
4
Выпуклость не означает единственного минимума. Обычно вам нужно обратиться к строгой выпуклости целевой функции, определенной в выпуклой области. Также проблемой здесь являются критерии завершения для градиентного спуска с использованием арифметики с плавающей запятой: даже когда целевая функция является строго выпуклой, алгоритм может находить различные решения (в зависимости от начальных значений), когда функция почти плоская вблизи своего минимума.
whuber
@whuber не могли бы вы сделать это проще и понятнее для меня?
Анжела Миноу
@whuber Я думаю, что первая проблема заключается в использовании терминологии. Во-вторых, выпуклость подразумевает уникальный минимум. Я не вижу дифференцируемой вогнутой функции, которая не имеет ни одного минимума / максимума. Смотрите доказательство здесь: planetmath.org/localminimumof выпуклой функции обязательно глобально
Владислав Довгальец
3
Я не удосужился прочитать доказательство, потому что оно должно вызывать строгую выпуклость, чтобы быть правильным. Задача наименьших квадратов с неидентифицируемыми коэффициентами будет выпуклой, но не строго выпуклой, и, таким образом, будет иметь (бесконечно) много решений. Но это не совсем относится к градиентному спуску, у которого есть свои проблемы - некоторые из которых четко обсуждаются в статье Википедии . Таким образом, как в теоретическом, так и в практическом смысле правильный ответ на вопрос верен : градиентный спуск может - и будет - давать несколько решений.
whuber
@whuber Да, доказательство апеллирует к строгой выпуклости.
Владислав Довгальец