На самом деле, я хотел спросить вас, как я могу определить условие завершения градиентного спуска.
Могу ли я остановить его, основываясь на количестве итераций, т.е. учитывая значения параметров, скажем, для 100 итераций?
Или мне следует подождать, чтобы различия в значениях двух параметров 'new' и 'old' были очень малы, скажем, ? Это определенно займет много времени.
Какой самый лучший способ? В моем случае даже одна итерация занимает значительное время. В этой ситуации, если я подожду 2-го условия, это может занять недели, я думаю.
Так какой подход я должен использовать. Как справиться с этим сценарием?
algorithms
optimization
gradient-descent
user31820
источник
источник
ftolabs
ftolrel
xtolabs
Ответы:
Хороший вопрос Я видел много правил остановки в литературе, и у каждого есть свои преимущества и недостатки, в зависимости от контекста.
optim
Функция в R, например, имеет по крайней мере три разные правила останова:maxit
заранее определенное максимальное количество итераций. Еще одна похожая альтернатива, которую я видел в литературе, это максимальное количество секунд до истечения времени ожидания. Если все, что вам нужно, это приблизительное решение, это может быть очень разумным. Фактически, есть классы моделей (особенно линейных моделей), для которых ранняя остановка аналогична установке гауссовского априора в значениях ваших параметров. Частый участник сказал бы, что у вас есть «норма L2», а не априор, но они также считают это разумным поступком. Я только просмотрел эту статью , но она рассказывает о взаимосвязи между ранней остановкой и регуляризацией и может помочь вам получить больше информации. Но короткая версия, да, ранняя остановка может быть вполне респектабельной вещью, в зависимости от того, что выabstol
остановка, когда функция становится «достаточно близкой» к нулю. Это может не относиться к вам (не похоже, что вы ожидаете ноль), поэтому я пропущу это.reltol
Это как ваше второе предложение - прекратите, когда улучшение падает ниже порога. На самом деле я не знаю, насколько много теории на этот счет, но вы, вероятно, будете стремиться получить меньшие минимумы таким образом, чем с небольшим максимальным числом итераций. Если это важно для вас, возможно, стоит выполнить код для дополнительных итераций.Другое семейство правил остановки связано с оптимизацией функции стоимости для набора данных проверки (или перекрестной проверки), а не для данных обучения. В зависимости от того, для чего вы хотите использовать свою модель, вы, возможно, захотите хорошо остановиться, прежде чем доберетесь до локального минимума в ваших тренировочных данных, поскольку это может привести к переобучению. Я почти уверен, что Тревор Хасти написал о хороших способах сделать это, но я не могу вспомнить цитату.
Другие возможные варианты нахождения более низких минимумов за разумное время могут включать:
Стохастический градиентный спуск, который требует только оценки градиентов для небольшой части ваших данных за один раз (например, одна точка данных для «чистого» SGD или небольших мини-пакетов).
Более продвинутые функции оптимизации (например, методы типа Ньютона или Conjugate Gradient), которые используют информацию о кривизне вашей целевой функции, чтобы помочь вам указывать в более точных направлениях и делать шаги лучшего размера при движении вниз по склону.
Термин «импульс» в вашем правиле обновления, так что ваш оптимизатор лучше справляется с укатом, чем с ограничением стен каньона в вашей целевой функции.
Все эти подходы обсуждаются в лекционных заметках, которые я нашел в Интернете.
Надеюсь это поможет!
Отредактируйте « о», и вы также можете попытаться получить лучшие начальные значения (например, решая более простую версию задачи), так что требуется меньше итераций, чтобы приблизиться к оптимальному с вашего «горячего старта».
источник
reltol
(то есть, когда перестает быть «улучшение») означает. Первое улучшение означает уменьшение функции стоимости. Поэтому я предполагаю, что вы имеете в виду, что, когда функция стоимости перестает достаточно уменьшаться (или начинает расти), вы останавливаетесь, верно? На самом деле никто не делает "| старый - новый |" тип правила обновления, верно?abstol
Параметр имеет смысл только тогда , когда вы принимаете допуск градиента функции затрат, а не сама функция затрат. В локальном оптимизаторе значение градиента равно нулю; но не значение функции.