Альтернативная стратегия - найти требуемые PW2 параметров за W шагов метода первого порядка, затратив на каждом шаге P W операций. Именно такую скорость сходимости ( W итераций) имеют лучшие алгоритмы первого порядка (например, метод сопряженного градиента). В обоих случаях оптимистическая оценка сложности обучения сети (т.к. она [c.62]
Решение этой задачи может быть осуществлено методом сопряженных градиентов (см. 51), или, если позволяют возможности машины, решением системы линейных уравнений [c.138]
Значительный перерасход машинного времени был связан с тем, что метод сопряженных градиентов был не конечным, как это-утверждает теория, а лишь итерационным. Это связано с влиянием ошибок округления, не учитываемых теорией. [c.453]
Используется какой-нибудь алгоритм безусловной оптимизации, например, метод градиента, усиленный привлечением идей метода сопряженных градиентов. Точка и используется, как начальная в этом процессе спуска. После этого в новой точке и, g, л делается пересчет множителей Лагранжа [c.462]
МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ 469 [c.469]
Метод сопряженных градиентов [c.469]
Метод сопряженных градиентов является итерационным методом нахождения минимума квадратичной формы. Характерная его особенность — конечность минимум достигается не более, чем за п шагов (тг-размерность пространства). Вычислительная схема метода сопряженных градиентов была обобщена на задачи нахождения минимума общих функций, не являющихся квадратичными. Опыт вычислений показал высокую эффективность метода, особенно в ситуациях, когда метод простого спуска по градиенту оказывался практически неработоспособным в силу крайне меД ленной сходимости. Ниже излагается вычислительная схема ме -тода в случае квадратичной функции, затем будет приведено его формальное обоснование. В заключение будет приведено обобщение вычислительной схемы в случае неквадратичной функции. [c.469]
I. Вычислительная схема метода сопряженных градиентов [c.470]
Существуют различные вычислительные схемы метода сопряженных градиентов, отличающиеся видом расчетных формул. Будучи формально эквивалентными, эти разные схемы отличаются друг от друга объемом хранимой в процессе вычислений информации, числом операций на стандартный шаг и степенью чувствительности алгоритма к ошибкам округления. Все эти факторы становятся особенно важными при решении задач достаточно высокой размерности. [c.474]
Кроме того, различные формы алгоритма приводят к различным обобщениям его на задачи с произвольными, не квадратичными функциями. Эти обобщения, разумеется, уже не эквивалентны друг другу и с формальной точки зрения. Ниже мы приведем некоторые формы метода сопряженных градиентов и соответствующие их обобщения на задачи min / (x) с произвольной [c.474]
Другие формы метода сопряженных градиентов и их обобщения. ([62]). Алгоритм II. Рассмотрим задачу с квадратичной формой [c.475]
МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ 477 [c.477]
Не ясно, как включить в схему метода сопряженных градиентов условия Ft [и ( )]=() ( 0), i = l, 2,. . ., т. Конечно, здесь, как и в других затруднительных ситуациях, можно сослаться на метод штрафных функций и избавиться от условий F,.=0, заменив минимизируемый функционал F0 [и ( )] на составной [c.477]
Метод сопряженных направлений. В линейной алгебре этот метод известен как метод сопряженных. градиентов решения систем линейных алгебраических уравнений АХ=Ь, а следовательно, как метод минимизации квадратичной функции f
Лучшее возможное решение задачи может быть найдено разнообразными способами. В некоторых случаях задача может быть решена простым методом проб и ошибок, особенно если поиск решения не полностью автоматизирован, а проводится вручную . В других случаях могут потребоваться сложные процедуры и алгоритмы. Например, симуляция процесса эволюции (в генетическом оптимизаторе) — очень мощный метод поиска качественных решений для сложных задач. В некоторых случаях лучшее решение — аналитическая (вычислительная) процедура, например метод сопряженных градиентов. Аналитическая оптимизация — эффективный подход для задач с гладкими (дифференцируемыми) функциями пригодности, например задач, встречающихся при обучении нейронных сетей или разработке множественных моделей линейной регрессии. [c.48]
Многие методы перебора данных, используемые для решения многовариантных проблем оптимизации, применяют в том или ином виде метод сопряженных градиентов (максимальной крутизны). В общем виде оптимизация методом сопряженных градиентов ведется следующим образом. Некоторым образом выбирается точка на поверхности функции пригодности. Вектор градиента поверхности в данной точке оценивается с помощью дифференцирования функции пригодности по каждому из параметров. Полученный градиент указывает направление максимального роста функции пригодности в n-мерном пространстве параметров. В направлении градиента делаются шаги до тех пор, пока функция пригодности не перестанет расти. [c.58]
Для применения оптимизации по методу сопряженных градиентов необходимо разработать правила определения размеров каждого шага, а также правила корректировки направления, задаваемого градиентом. Примитивные версии исходят из того, что существует поверхность функции пригодности (приближаемая сходящимися степенными рядами), где имеются холмы , по которым следует подниматься. Более продвинутые версии идут далее, исходя из того, что функция пригодности может быть неплохо приближена квадратичной формой. Если функция пригодности соответствует этому предположению, то найти решение можно гораздо быстрее. Впрочем, если поверхность функции пригодности имеет сильно изрезанную форму с впадинами и выступами неправильных очертаний, квадратичные формы часто не могут дать хорошего приближения. В таких случаях сложные методы могут вовсе не находить решения или по крайней мере работать гораздо медленнее. [c.58]
Тем не менее низкая скорость оптимизации не является главным препятствием на пути аналитика. Гораздо сложнее справиться с так называемой проблемой локальных решений. Почти все аналитические методы, будь они простыми или сложными, легко попадаются в ловушку локальных максимумов при наличии множества впадин и выступов на поверхности они не могут найти наилучшее глобальное решение. Метод наименьших квадратов, моделирование нейронными сетями дают поверхности функции пригодности неправильной формы с большим количеством локальных экстремумов. Данные поверхности чрезвычайно сложны для стандартных аналитических методов, таких как метод сопряженных градиентов или алгоритм обратного распространения, применяемый в нейронных сетях. Впрочем, местные максимумы можно обойти, соединив аналитический метод с генетическим. Для поверхностей, которые можно исследовать аналитическими методами, такой двойной алгоритм может оказаться наилучшим решением он позволит быстро и с большой точностью найти глобальные оптимумы. [c.58]
Мы не затронули здесь более изощренных методов обучения, таких как метод сопряженного градиента, а также методов второго порядка, которые используют не только информацию о градиенте функции ошибки, но и информацию о вторых производных. Их разбор вряд ли уместен при первом кратком знакомстве с основами нейрокомпьютинга. [c.62]
При более последовательном подходе для улучшения процесса обучения можно использовать информацию о производных второго порядка от функции невязки. Соответствующие методы оптимизации называются квадратичными. Вся указанная информация собрана в матрице гессиана Н, имеющей размеры Nw х Nw, где Nw — число весов. Эта матрица содержит информацию о том, как изменяется градиент при малых смещениях по различным направлениям в пространстве весов. Прямое вычисление матрицы требует большого времени, поэтому разработаны методы, позволяющие избежать вычисления и хранения матрицы (спуск по сопряженному градиенту, масштабированный метод сопряженных градиентов (см. [197]), RBa kProp (см. [212]), квази-ньютоновский метод, метод Левенбер-га-Маркара). [c.32]
При относительно хорошем начальном приближении 0, Т] метод Ньютона имеет заметное преимущество, быстро приводя к практически точному решению. Метод Нейштадта в этой ситуации, даже усиленный идеями метода сопряженных градиентов, сходится довольно медленно. [c.196]
Решение задачи методом сопряженных градиентов описано в [62] (оттуда и заимствованы значения Т=2, Х0=0, Xi=l, 2). Использовалась аппроксимация типа (6) (при N=50) и задача решалась, как конечномерная задача поиска минимума. За 370 итераций метода сопряженных градиентов (1508 вычислений градиента) получено решение с 9-ю знаками F и 8-ю знаками х. [c.227]
Используются два способа решения (10) метод покоординатного спуска и метод сопряженных градиентов. Большое число переменных 5Я, га М, и наличие ограничений s sa s+, а также специфика задачи, состоящая в том, что векторы ,, для близких индексов п близки между собой, потребовали введения некоторых дополнений в эти стандартные алгоритмы. Прежде всего вводится последовательность признаков тся, п=1,. . ., 7V, причем =0 для п М и т-п > 0 для п (и М. Решение задачи (10) начинается методом покоординатного спуска. Управление процессом осуществляется с помощью двух признаков lt 2, смысл которых будет разъяснен ниже. [c.448]
Поясним смысл такого управления. Временное исключение переменных имеет следующую цель пусть переменная sn вышла на s можно предположить, что и в дальнейшем в целях минимизации x e эту переменную следует увеличить, но это уже неосуществимо. Поэтому лучше не тратить времени на вычисление для нее величины 8. Но этот вывод нестрог, так как после выхода sn на s точка х за счет изменения других sn изменилась и, может быть, нужно менять sn в другую сторону. Поэтому различаются два случая (с и d) при %2=0 если в цикле 2 не было случаев выхода на границу, но часть переменных была исключена (Sx=l), то следует снова включить все sn в работу. Если же =0 при =0, то это означает, что в решении задачи (10) ограничения s , s+ перестали играть роль (тоже, может быть, лишь временно) и задача (10) стала задачей минимизации без ограничений. В этой ситуации метод покоординатного спуска становится неэффективным, и целесообразно перейти к методу сопряженных градиентов. Правда, перед этим переходом полученная ситуация подвергается анализу (см. выше). Если анализ показывает необходимость более точного решения задачи (10), это делается следующим образом. [c.449]
Выше описан основной цикл метода сопряженных градиентов. Таких циклов делается — т, после чего происходит снова возврат к покоординатному спуску (п. 1). Поясним, почему сразу не используется метод сопряженных градиентов. В этом методе все переменные sn изменяются одновременно, и шаг определяется наименьшим расстоянием одной из переменных до своей границы s (s+). Пусть этот шаг определяется переменной s .. Однако в процессе участвуют векторы hn, близкие к hj (напомним, что hn суть сеточное представление непрерывной функции w (t) в (1)). Поэтому многие переменные 5Я лишь немного не дотянут до своих границ. На следующем цикле процесса на границу выйдет одна из этих переменных, причем смещение будет очень малым, затем еще одна и т. д. В целом процесс будет неэффективен, так как каждая итерация метода сопряженных градиентов требует значительных предварительных вычислений. [c.450]
В таблицах показана эволюция в процессе решения следующих величин v — номер итерации, F (g), А (х), 1Ы1< , п — число индексов в множестве Ms, i — число итераций метода сопряженных градиентов при решении задачи (2), (в этих расчетах метод покоординатного спуска не использовался), и, наконец, Е. В этой задаче е= , 0,. . ., 0 . Расчеты отличались лишь различными требованиями к точности определения TJ =0,002 (табл. 1), TJ = =0,02 (табл. 2) и Yj =0,01 (табл. 3). Отметим следующие характерные черты работы алгоритма. [c.453]
Здесь используется та же самая комбинация покоординатного спуска и метода сопряженных градиентов, что и в 48 (закрепленные переменные, разумеется, в процессе минимизации не участвуют). После некоторого количества итераций полученная точка х (s) подвергается анализу. [c.455]
В табл. 1 показаны в зависимости от номера итерации v величины min (x, g) и X E. Все происходит так, как предписывает теория min (x, g) монотонно растет, x e стремится к нулю (немонотонно, естественно). Только уж очень медленно Разумеется, такие эксперименты следует трактовать осторожно. Не исключено, что можно ускорить сходимость классического алгоритма строго выпуклого программирования, используя, например, метод сопряженных градиентов при решении задачи maxF(g ), где F(g) [c.457]
Метод сопряженных градиентов использовался автором не только в серийных расчетах задач оптимального управления (в качестве одного из блоков решения задачи линейного или квадратичного программирования), но и в методических расчетах в условиях сравнительно высокой размерности. В частности, в 48 представлены результаты решения задачи линейного программирования итерационным методом, включающим и метод сопряженных градиентов. Видно, что сходимость метода не соответствует теоретическим предсказаниям, что приводит к определенному (и заметному) перерасходу машинного времени. Были проведены и специальные эксперименты по минимизации формы (Вх, Вх) (G=B B) со случайной матрицей В размером 100x100. Использовалась схема типа III. Алгоритм не давал нужной точности после 300 — 400 шагов. Для уменьшения влияния ошибок округления была применена комбинация схем II и III четыре итерации проводились с вычислением В по схеме III, а каждая пятая — по более громоздкой формуле схемы II. Это привело к улучшению сходимости (выигрыш можно оценить числом л 2), но проблемы не решило. [c.477]
Как известно, в методе сопряженных градиентов последовательно вычисляемые направления спуска г "1/ образуют G-орто-гональную систему векторов. Были проведены эксперименты с целью выяснить, как постепенно из-за ошибок округления утрачивается ортогональность. Для этого в процессе решения запоминались некоторые из г, отстоящие от текущего г<+1/2 На 20 — 30 итераций таких г было три г, г", г ". По мере роста номера итерации i эти векторы обновлялись (самый старый из них забывался и заменялся текущим г / ). Вычислялись величины у = (Сг, г ), т" = ( г, г ), т " = (Сг, r "). Результаты показали, что величины у быстро становятся ненулевыми, хотя очень больших значений не достигают. Обычно они колеблются в пределах 0,01-0,1. [c.477]
Поляк Б. Т. Метод сопряженных градиентов в задачах на якстрс-мум. — ЖВМ и МФ, 1969, 9, № 4, с. 807—821. [c.481]
Поляк Б. Т. Метод сопряженных градиентов в задачах на экстремум. — Журн. вычисл. матем. и матем. физ., 1969, т. 9, № 4, с. 807—821. [c.464]
Для обучения сети используются различные алгоритмы обучения и их модификации [9, И, 22, 42, 70, 139]. Очень трудно определить, какой обучающий алгоритм будет самым быстрым при решении той или иной задачи. Наибольший интерес для нас представляет алгоритм обратного распространения ошибки, так как является эффективным средством для обучения многослойных нейронных сетей прямого распространения [85, 127]. Алгоритм минимизирует среднеквадратичную ошибку нейронной сети. Для этого с целью настройки синаптических связей используется метод градиентного спуска в пространстве весовых коэффициентов и порогов нейронной сети. Следует отметить, что для настройки синаптических связей сети используется не только метод градиентного спуска, но и методы сопряженных градиентов, Ньютона, квазиньютоновский метод [94]. Для ускорения процедуры обучения вместо постоянного шага обучения предложено использовать адаптивный шаг обучения a(t). Алгоритм с адаптивным шагом обучения работает в 4 раза быстрее. На каждом этапе обучения сети он выбирается таким, чтобы минимизировать среднеквадратическую ошибку сети [29, 36]. [c.65]
Перед использованием нейронной сети производится ее обучение, что представляет собой итерационный процесс настройки весовых коэффициентов. Для обучения применяются специальные алгоритмы. Наибольшее распространение получили градиентные методы обучения - алгоритм обратного распространения ошибки (Ba k Propagation), сопряженных градиентов, RProp и другие. Для проверки адекватности построенной нейронной сети используется специальный прием - тестовое подтверждение. [c.17]
Смотреть страницы где упоминается термин Метод сопряженных градиентов
: [c.188] [c.192] [c.196] [c.440] [c.449] [c.457] [c.471] [c.473] [c.475] [c.478] [c.312] [c.67] [c.263] [c.258] [c.127]Смотреть главы в:
Приближенное решение задач оптимального управления -> Метод сопряженных градиентов