Нужен ли градиентный спуск, чтобы найти коэффициенты модели линейной регрессии?

31

Я пытался научиться машинному обучению, используя материал Coursera . В этой лекции Эндрю Нг использует алгоритм градиентного спуска, чтобы найти коэффициенты модели линейной регрессии, которая минимизирует функцию ошибки (функцию стоимости).

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

regression machine-learning linear-model gradient-descent Виктор
источник
3
С 1700-х годов линейные модели были достойно обработаны. Есть множество способов справиться с ними, которые не требуют градиентного спуска (GD). Существуют нелинейные модели, в которых большинство из этих методов не имеют успеха. Эндрю заставляет вас использовать незнакомый, но очень полезный метод против очень простой проблемы, чтобы вы могли отладить свой подход. Когда вы хорошо разбираетесь в методе, вы можете применить его к потрясающе нелинейным задачам, для которых GD является единственным методом для получения результатов.
EngrStudent - Восстановить Монику
10
Нет, вам не нужно использовать подходы, такие как градиентный спуск (в любом случае, это не единственный метод оптимизации). Вы действительно можете аналитически решить это, как вы предлагаете; Вы различаете по каждому параметру, поэтому вы получаете одно уравнение для каждого параметра. Но полезно решать простые проблемы, которые можно решить другими способами; если вы уже знаете ответ, вы можете быть уверены, когда получите правильный ответ с градиентным спуском.
Glen_b
Если функция стоимости является обычным квадратичным («дистанционным») штрафом, существует решение в закрытой форме. Тем не менее, градиентный спуск, как правило, гораздо быстрее, поэтому он обычно используется.
Агиненский
Кроме того, градиентный спуск может быть использован для нахождения численных решений задач, которые аналитически неразрешимы. Я подозреваю, что он использует градиентный спуск на ранней стадии, чтобы привыкнуть к нему. Я считаю, что он затем использует градиентный спуск с нейронными сетями. Излишне говорить, что ситуация с нейронными сетями более сложная. Я думаю, что из педагогической ситуации, увидев ее ранее, с линейными моделями, градиентный спуск для использования с нейронными сетями кажется более разумным.
Агиненский
3
Спасибо за размещение ссылки на видео Andre Ng, которые я смотрел несколько раз. Я уже знал это, хотя и не до такой степени, но страшно видеть, чему учится подавляющее большинство людей, «изучающих» оптимизацию, не говоря уже о том, что, по крайней мере, некоторые из них учатся статистическим вычислениям. Джин Голуб, пионер в области вычислительной техники и использования SVD, перевернулся бы в могиле, если бы он знал, чему сейчас учат в его отделении информатики в Стэнфорде. «Самое смешное» видео - youtube.com/watch?v=B3vseKmgi8E , который рекомендует и сравнивает 2 худших алгоритма для наименьших квадратов
Марк Л. Стоун

Ответы:

43

Линейные наименьшие квадраты могут быть решены с помощью

0) Использование высококачественного решателя линейных наименьших квадратов на основе SVD или QR, как описано ниже, для неограниченных линейных наименьших квадратов или на основе версии Квадратичного программирования или Конической оптимизации для связанных или линейно ограниченных наименьших квадратов, как описано ниже. Такой решатель предварительно консервирован, тщательно протестирован и готов к работе - используйте его.

1) SVD, который является наиболее надежным и численно точным методом, но также требует больше вычислений, чем альтернативы. В MATLAB SVD-решение неограниченной линейной задачи наименьших квадратов A * X = b имеет тип pinv (A) * b, что очень точно и надежно.

2) QR, который достаточно надежен и численно точен, но не так сильно, как SVD, и быстрее, чем SVD. В MATLAB QR-решение неограниченной линейной задачи наименьших квадратов A * X = b - это A \ b, что довольно точно и надежно, за исключением случаев, когда A плохо обусловлен, т. Е. Имеет большое число условий. A \ b быстрее вычисляется, чем pinv (A) * b, но не так надежно или точно.

3) Формирование нормальных уравнений (УЖАСНЫЕ с точки зрения надежности и числовой точности, потому что они возводят в квадрат число условий, что очень плохо делать) и

3a) решение по факторизации Холецкого (не хорошо)

3б) явно инвертирующая матрица (УЖАСНАЯ)

4) Решение задачи квадратичного программирования или конуса второго порядка

4a) Решить с помощью высококачественного программного обеспечения для квадратичного программирования. Это надежно и численно точно, но занимает больше времени, чем SVD или QR. Однако легко добавить связанные или общие линейные ограничения, или линейные или квадратичные (две нормы) штрафные или регуляризованные члены к целевой функции, и все же решить проблему, используя программное обеспечение для квадратичного программирования.

4b) Решить проблему конуса второго порядка с помощью высококачественного программного обеспечения Conic Optimization. Замечания те же, что и для программного обеспечения Quadratic Programming, но вы также можете добавить связанные или общие линейные ограничения и другие конические ограничения или термины целевой функции, такие как штрафные или регуляризованные условия в различных нормах.

5) Решить, используя высококачественное программное обеспечение нелинейной оптимизации общего назначения. Это все еще может работать хорошо, но в целом будет медленнее, чем программное обеспечение Quadratic Programming или Conic Optimization, и, возможно, не столь надежно. Однако может быть возможно включить не только ограниченные и общие линейные ограничения, но также и нелинейные ограничения в оптимизацию наименьших квадратов. Также может использоваться для нелинейных наименьших квадратов, и если к целевой функции добавляются другие нелинейные члены.

6) Решите, используя паршивые алгоритмы нелинейной оптимизации общего назначения -> НИКОГДА НЕ ДЕЛАЙТЕ ЭТОГО.

7) Решить, используя НАИБОЛЕЕ ВОЗМОЖНЫЙ алгоритм нелинейной оптимизации общего назначения, то есть градиентный спуск. Используйте это, только если вы хотите увидеть, насколько плох и ненадежен метод решения. Если кто-то скажет вам использовать градиентный спуск для решения линейных наименьших квадратов

7 i) Узнайте о статистических вычислениях от того, кто что-то знает об этом

7 ii) Изучите оптимизацию у того, кто что-то знает об этом

Марк Л. Стоун
источник
Хороший пост, почему вы думаете, что Холецкий не очень хорош, учитывая, что ваша система - PD? (а не со смешным числом условий) Кстати, я думаю, что вы хотите сказать (или добавить) понятие обобщенного обратного (очевидно, используемого в основном в образовательных целях) либо в «SVD», либо в «явно инвертирующей» точке.
usεr11852 говорит восстановить Monic
2
Кстати, смешно, как часто создаются матрицы с очень высокими числами условий, особенно немытыми массами (то есть большинством людей, делающими линейные наименьшие квадраты, особенно с учетом демократизации в доступе), которые не настроены на это.
Марк Л. Стоун
1
mldivide, т.е. Обратная косая черта, т. е. \ использует QR, когда m ~ = n (наименьших квадратов), как я уже говорил во 2-м предложении моего параграфа (2) выше. Вы будете удивлены, насколько много дерьма в MATLAB - не только в наборах инструментов, некоторые из которых абсолютно ужасны, но и в меньшей степени в некоторых основных функциях.
Марк Л. Стоун
1
@ MarkL.Stone, отличный ответ! Не могли бы вы объяснить немного больше о том, почему не рекомендуется использовать градиентный спуск для решения наименьших квадратов! (в моем понимании это просто итеративный подход по сравнению с другими (подходы к решению проблем), которые вы упомянули выше). Более того, не могли бы вы также прокомментировать проблему: «если бы у меня было n> = 30000 функций для задачи, метод нормальных уравнений будет очень медленным, поскольку инвертировать n * n матрицу было бы ужасно! С другой стороны, GD будет работать в этом дело симпатичное! любые мысли о том, как SVD & QR будет работать ". любое предложение будет полезно.
Ан
1
@ anu В качестве крайней меры используйте только градиентный спуск. и это будет только в том случае, если проблема слишком велика, чтобы ее можно было решить с помощью SVD или QR. Никогда не формируйте нормальные уравнения, не говоря уже о явном обращении матрицы для решения нормальных уравнений, НИКОГДА. 30 000 функций на сегодняшний день звучат не так уж и много.
Марк Л. Стоун
0

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

Для вычисления таких решений, много optimization techniquesбыло разработано и Gradient Descentявляется одним из них.
Таким образом, градиентный спуск не единственный способ сделать это.

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

Викас Ратури
источник
Хотя я и не ошибаюсь, я думаю, что ваш ответ не соответствует общей картине, сосредоточившись на нестандартном случае. Подавляющее большинство линейных регрессионных моделей устанавливаются с помощью QR - разложение , использующую замкнутой форме раствора. GD-градиент приличный - используется в качестве примера для введения более продвинутых методов (например, SGD- стохастик GD).
usεr11852 говорит восстановить Monic
Можете ли вы уточнить, что такое QR-разложение?
Виктор
3
Ax=bA=QRRQAx=b⇒QRx=b⇔Rx=QTbRQTQ=ISGD, Поскольку у большинства людей нет очень больших матриц, разложение QR лучше. В целом QR-разложение сформировало числовой мир; SIAM выбрал его в качестве одного из 10 лучших алгоритмов 20-го века.
usεr11852 говорит восстановить Monic
@ usεr11852 да, конечно. Это потому, что я хотел, чтобы ответ был простым, чтобы избежать таких понятий, как разложение QR, оставаясь релевантными для предметной области уровня Ng.
Викас Ратури
3
QR был одним из 10 лучших алгоритмов 20-го века. Но время идет, и хотя эффективные алгоритмы для вычисления SVD датируются 1960-ми годами, вы должны смотреть на важность областей применения. Поэтому я считаю, что SVD является ТОП-алгоритмом 21-го века. Откровенно говоря, вы когда-нибудь слышали о том, чтобы QR использовался для рекомендации фильмов? Нет, SVD используется для этого критического назначения. SVD явно является алгоритмом выбора, когда Twitter рассылает незапрашиваемые рекомендации консервативным старым чудикам относительно того, каким подросткам-знаменитостям они должны следовать. Давайте посмотрим, QR сделает это !!!
Марк Л. Стоун