Продвинутые методы многомерной оптимизации. решение слау с помощью метода сопряжённых градиентов

Рассмотрим методы отыскания экстремума функции R ( x ) без активных ограничений. Активными принято называть такие ограничения, на границе которых находится решение. Величина шага  х в соотношении

x i +1 = x i +  x i

вычисляется с использованием градиента целевой функции R ( x ), т.е.

x i =  ( gradR ( x i )),

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

Вычисление градиента предполагает непрерывность функции многих переменных

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

Рис. 3.5 . Иллюстрация траекторий поиска минимума функции градиентными

методами:

1 - оптимум; 2 -- траектория метода градиента; 3 - траектория метода

тяжелого шарика; 4 - траектория метода наискорейшего спуска;

5 - траектория метода сопряженных градиентов;

Кроме того, для всех приведенных траекторий выбраны различные начальные условия, с тем, чтобы не загромождать построения. На этом и последующих рисунках зависимость R ( x 1 , x 2 ) приведена в виде линий уровня на плоскости в координатах x 1 - x 2 .

Основные методы

Метод градиента.

Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента R ( x ) в текущей точке поиска. Простейший алгоритм поиска min R ( x ) записывается в векторной форме следующим образом:

или в скалярном виде:

- порядковый номер аргумента,

Величина рабочего шага в направлении градиента h grad R ( x ) зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага h , с помощью которого можно управлять эффективностью метода.

Поиск каждой новой точки состоит из двух этапов:

1) оценка градиента R ( x ) путем вычисления частных производных от R ( x ) по каждой переменной х j ,

2) рабочий шаг по всем переменным одновременно.

Величина h сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по переменной определяется направляющими косинусами градиента.

где cosφ j =

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

Наибольшее распространение получили следующие алгоритмы:

1. h i = const = h (без коррекции);

2. h i = h i -1 /2, если R (x i ) < R (x i -1 ) ; h i = h i -1 , R (x i ) > R (x i -1 ) ;

3. h i = h i -1 , если  1 ≤  ≤ 2 ; h i =2h i -1 , если 1 >;
если 2 < .

где  - угол между градиентами на предыдущем и текущем шаге;  1 и  2 - заданные пороговые значения выбираются субъективно (например,  1 = π/6,  2 = π/3).

Вдали от оптимума направление градиента меняется мало, потому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R ( x ) большой), поэтому h сокращается (третье выражение).

Для оценки частных производных используются разностные методы:

1 . Алгоритм с центральной пробой

2. Алгоритм с парными пробами

где g j - пробный шаг по j -й переменной, выбираемый достаточно малым для разностной оценки производной.

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

На рис. приведена одна из возможных траекторий поиска минимума двумерной функции градиентным методом (наряду с другими ниже рассматриваемыми методами).

Условием окончания поиска может являться малость модуля градиента R ( x ) , т.е. |grad R ( x ) | <  .

Рис. Иллюстрация получения производной с центральной и парными пробами.

Пример 1.

Требуется найти минимумфункции

R ( x 1 , x 2 ) = х 1 3 + 2 х 2 2 - 3х 1 - 4x 2 ,

2. Интервал поиска квадрат: х 1нач = -2, х 1кон = 2, х 2нач = -2, х 2кон = 2.

3. Начальная точка: х 10 = - 0,5, х 20 = -1.

4. Параметры поиска: коэффициент шага h = 0,1, пробный g = 0,01, погрешность  = 0,01.

5. Алгоритм метода: алгоритм 1 (х i +1 =х i - h grad R ( x i ) ).

6. Алгоритм коррекции шага: без коррекции коэффициента пропорциональности шага (h = const).

7. Способ вычисления производной: вычисление grad R с парными пробами.

Результаты вычислений . В начальной точке вычисляем градиент функции:

Значение критерия R = 7,3750. Делаем рабочий шаг по формуле 5, получаем

х 1 = - 0,275, х 2 = - 0,2.

В новой точке опять вычисляем производные:

Значение критерия R = 1,3750.

Делаем рабочий шаг, получаем x 1 = 0,002, х 2 = 0,280.

Таблица 18

			dR /dx 1	dR /dx 2

В последней точке модуль градиента меньше заданной погрешности (0,0063 < 0,01), поэтому поиск прекращается.

Построить зависимость градиента от № шага

Пример 2.

Отличается от предыдущего только величиной коэффициента пропорциональности шага h , теперь h = 0,4. Ниже, в табл. 19 приведены только первые 14 шагов (как и в предыдущем случае). Целесообразно сопоставить их путем построения траекторий поиска при обоих значениях h в координатах х 1 – х 2 .

Таблица 19

			dR /dx 1	dR /dx 2

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

номер итерации	параметр оптимизации h=0,4	параметр оптимизации h=0, 1

Рис. 2.5. Сравнение сходимости градиентного метода при использовании различного шага.

Метод наискорейшего спуска.

Основным недостатком градиентного метода является необходимость частого вычисления производных от R ( x ) . Этого недостатка лишен метод наискорейшего спуска, который заключается в следующем.

В текущей точке вычисляется grad R ( x ) , и затем в направлении градиента ищется min R ( x ) . Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению - направлению градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad R ( x ) .

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

Метод, как и все градиентные методы, обладает невысокой эффективностью в овражных функциях. В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска min по направлению (задается величиной h - шагом поиска по направлению).

Условием окончания может являться малость модуля градиента R ( x ) | grad R ( x ) | <  . Можно также использовать и малость приращений по переменным в результате шага, но только в том случае, если на данном шаге мы "проскочили" оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптимуму, а малостью коэффициента пропорциональности шага h .

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

Одна из возможных траекторий поиска минимума двумерной функции методом наискорейшего спуска приведена на рис. выше.

Пример.

Для сравнения с методом градиента рассмотрим решение предыдущего примера при h = 0,1.

Результаты расчетов. Расчет производных детально рассмотрен выше, поэтому здесь не приводится. Ниже, в табл. 20 приводятся результаты движения по градиенту с постоянным шагом.

Таблица 20

			dR /dx 1	dR /dx 2

В следующей точке (0,400, 2,00) значение критерия (R = -0,256) оказывается хуже, чем в последней (R =-2,1996). Поэтому в найденной точке оптимума по направлению снова вычисляем градиент и по нему совершаем шаги, до тех пор, пока не найдем наилучшую точку (табл. 21).

Таблица 21

	dR /d х 1	dR /d х 2
Второй поиск по градиенту




Третий поиск по градиенту



Четвертый поиск по градиенту



Пятый поиск по градиенту

Метод сопряженных градиентов (пропустить).

Градиентные методы, базирующиеся только на вычислении градиента R ( x ) , являются методами первого порядка, так как на интервале шага они заменяют нелинейную функцию R ( x ) линейной.

Более эффективными могут быть методы второго порядка, которые используют при вычислении не только первые, но и вторые производные от R ( x ) в текущей точке. Однако у этих методов есть свои труднорешаемые проблемы - вычисление вторых производных в точке, к тому же вдали от оптимума матрица вторых производных может быть плохо обусловлена.

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядка с исключением их недостатков. На начальных этапах (вдали от оптимума) метод ведет себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.

Первый шаг аналогичен первому шагу метода наискорейшего спуска, второй и следующий шаги выбираются каждый раз в направлении, образуемом в виде линейной комбинации векторов градиента в данной точке и предшествующего направления.

Алгоритм метода можно записать следующим образом (в векторной форме):

Величина  может быть приближенно найдена из выражения

Алгоритм работает следующим образом. Из начальной точки х 0 ищут min R ( x ) в направлении градиента (методом наискорейшего спуска), затем, начиная с найденной точки и далее, направление поиска min определяется по второму выражению. Поиск минимума по направлению может осуществляться любым способом: можно использовать метод последовательного сканирования без коррекции шага сканирования при переходе минимума, поэтому точность достижения минимума по направлению зависит от величины шага h .

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

Одна из возможных траекторий поиска минимума двумерной функции методом сопряженных градиентов приведена на рис. 17.

Аннотация: Данная лекция рассматривает основные методы решения задач многомерной оптимизации, в частности, такие как метод Хука – Дживса, метод Нелдера – Мида, метод полного перебора (метод сеток), метод покоординатного спуска, метод градиентного спуска.

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

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

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

1. Метод Хука – Дживса

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

Описание этой процедуры представлено ниже:

А . Выбрать начальную базисную точку b 1 и шаг длиной h j для каждой переменной x j , j = 1, 2, ..., n . В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.

Б . Вычислить f(x) в базисной точке b 1 с целью получения сведений о локальном поведении функции f(x) . Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b 1 находится следующим образом:

1. Вычисляется значение функции f(b 1) в базисной точке b 1 .

2. Каждая переменная по очереди изменяется прибавлением длины шага.

Таким образом, мы вычисляем значение функции f(b 1 + h 1 e 1) , где e 1 - единичный вектор в направлении оси х 1 . Если это приводит к уменьшению значения функции, то b 1 заменяется на b 1 + h 1 e 1 . В противном случае вычисляется значение функции f(b 1 – h 1 e 1) , и если ее значение уменьшилось, то b 1 заменяем на b 1 -h 1 e 1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1 остается неизменной и рассматриваются изменения в направлении оси х 2 , т.е. находится значение функции f(b 1 + h 2 e 2) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2 .

3. Если b 2 = b 1 , т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b 1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если , то производится поиск по образцу.

В . При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b 1 в направлении b 2 - b 1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

(1.1)

Размер: px

Начинать показ со страницы:

Транскрипт

1 Курс: Методы оптимизации в машинном обучении, Продвинутые методы многомерной оптимизации Рассмотрим задачу безусловной оптимизации в многомерном пространстве: f(x) min x R N. Ранее для решения этой задачи были рассмотрены методы покоординатного и градиентного спуска, метод Ньютона, а также комбинированные методы. Во всех этих подходах очередное направление оптимизации d вычисляется только с использованием информации от оракула в текущей точке x. Таким образом, траектория оптимизации никак не учитывается. В методах оптимизации, рассматриваемых ниже, очередное направление оптимизации d существенно зависит от траектории оптимизации и, в частности, зависит от предыдущих направлений d,...,d. Решение СЛАУ с помощью метода сопряжённых градиентов Рассмотрим задачу минимизации квадратичной функции с положительно-определённым гессианом: Приравнивая к нулю градиент f, получаем: f(x) = xt Ax x T b min x, A = A T. () f(x) = Ax b = Ax = b. Таким образом, задача минимизации f эквивалентна решению СЛАУ Ax = b. Назовём набор векторов {d i } сопряжённым относительно положительно-определённой матрицы A, если выполнено условие: d T i Ad j = i j. Примером сопряжённых направлений является набор собственных векторов матрицы A. Действительно, в этом случае d T i Ad j = λ i d T i d j =. Последнее условие выполнено, т.к. собственные вектора, отвечающие различным собственным значениям, ортогональны, а среди собственных векторов с одинаковым собственным значением всегда можно выбрать ортогональный набор. Набор сопряжённых векторов является линейно-независимым. Рассмотрим нетривиальную линейную комбинацию сопряжённых векторов: α i d i =, α i. Домножим слева это уравнение на d T j A для некоторого j. В результате получим: α i d T j Ad i = α j = α j =. Последнее условие следует из того, что матрица A является строго положительно-определённой. Из линейной независимости вытекает, что сопряжённый набор{d i } N является базисом всего пространстваrn. В частности, решение СЛАУ x можно разложить по этому базису с некоторыми коэффициентами α i: Домножая это уравнение слева на d T j A, получаем: d T j Ax = N x = N α i d T j Ad i = α j α j = dt j Ax α i d i. () = dt j b d T j Ad. () j это не совсем так при использовании адаптивной коррекции длины шага На самом деле набор сопряжённых векторов можно рассматривать как ортогональный базис относительно скалярного произведения x,y = x T Ay. Отсюда становится очевидным линейная независимость векторов, а также то, что матрица A должна быть положительно-определённой (иначе не будет скалярного произведения).

2 Последнее равенство вытекает из того, что x решение СЛАУ, т.е. Ax = b. Здесь становится очевидным преимущество сопряжённого набора векторов относительно других базисов для поиска x: для сопряжённого набора коэффициенты разложения α j вычисляются аналитически. Поиск x по формуле () с коэффициентами () можно представить в виде итерационного процесса: x =, x + = x +α d, α = dt b d T Ad, =,...,N. В результате x N+ = x. Теперь получим аналогичный итерационный процесс для поиска x, который начинается с произвольного ненулевого вектора x. Для этого разложим вектор x x по сопряжённому базису: Домножая это равенство на d T j A слева, получаем: x x = N d T j A(x x) = α j α j = dt j A(x x) α i d i. = dt j (b Ax) = dt j g = dt j g j d T j Ad. (4) j Здесь и далее через g j обозначается градиент функции f в точке x j. Для квадратичной функции g j = Ax j b. Докажем последний переход в формуле (4): (j) d T j (g j g) = d T j (Ax j b Ax +b) = d T j A j α i d i = α i d T j Ad i = d T j g j = d T j g. (5) Таким образом, получаем следующий итерационный процесс для поиска x из произвольного начального приближения x: x + = x +α d, α = dt g d T Ad, =,...,N. (6) Можно показать, что данный итерационный процесс является процессом наискорейшего спуска для функции f вдоль сопряжённых направлений {d i } N. Для этого достаточно убедиться в том, что коэффициент α j, вычисляемый по формуле (4), доставляет минимум по α функции f(x j +αd j). Действительно, α f(x j +αd j) = f(x j +α j d j) T d j = g T j+d j = (Ax j +α j Ad j b) T d j = α=αj = (Ax j b) T d j +α j = g T j d j d T j g j =. (7) Одновременно здесь было доказано, что g T j+ d j =. Покажем, что g T j+ d i = i j. Действительно, g T j+ d i = (Ax j+ b) T d i = (A(x + j α i d i) b) T d i = (Ax b) T d i +α i d T i Ad i = g T d i g T i d i =. Последнее равенство следует из (5). Условие ортогональности градиента g j+ всем предыдущим направлениям оптимизации означает, что x j+ доставляет минимум функции f в линейной оболочке L(d,...,d j). Более того, можно показать, что точка x j +αd j минимизирует функцию f в линейной оболочке L(d,...,d j) для любого α. Действительно, f(x j +αd j) T d i = (A(x j +αd j) b) T d i = (Ax j b) T d i +αd T j Ad i = g T j d i =. i < j. Таким образом, при движении вдоль очередного сопряжённого направления оптимизацию по предыдущим направлениям проводить не нужно. Это одна из отличительных особенностей метода сопряжённых направлений. Для проведения итерационного процесса (6) необходимо указать полный набор сопряжённых направлений для матрицы A. Рассмотрим следующую схему генерации d: d = g, d + = g + +β d, β = gt + Ad d T Ad, =,...,N. (8) Верна следующая последовательность рассуждений: d = g L(g), g = g +α Ad = g α Ag L(g,Ag), d = g +β d L(g,Ag), g = g +α Ad L(g,Ag,A g), d = g +β d L(g,Ag,A g),...

3 В результате набор {d,...,d i }, генерируемый по схеме (8), и набор {g,...,g i } принадлежат одному и тому же линейному пространству L(g,Ag,...,A i g). Следовательно, вектор Ad i можно представить в базисе {d,...,d }, > i, а вектор g i можно представить в базисе {d,...,d i }: Ad i = g i = a j d j, (9) j= i b j d j. () j= Покажем теперь, что схема (8) позволяет построить набор сопряжённых направлений для матрицы A. Кроме того, покажем, что при её использовании g T d i = i < и g T g i = i <. Проведём доказательство по индукции. Пусть известно, что g T d i = i <, d T Ad i = i <, g T g i = i <. Докажем, что аналогичные утверждения верны для +. Из рассуждений (7) следует, что g T + d =. Далее g T +d i = (g +α Ad) T d i = g T d i +α d T Ad i =. Последнее утверждение выполняется, исходя из предположения индукции. Покажем теперь, что d T + Ad i = i. Используя (8), получим, что d T + Ad = (g + +β d) T Ad = g T + Ad +g T + Ad =. Далее с помощью (9) заключаем, что для i < d T + Ad i = (g + +β d) T Ad i = g + Ad i = g + a j d j = Осталось показать, что g T + g i = i <. Используя (), получаем i g T + g i = g T + b j d j = j= j= i b j g T + d j =. j= a j g T + d j =. В результате получаем, что набор {d,...,d N } действительно является сопряжённым относительно матрицы A. Заметим, что в доказательстве сопряжённости существенно используется тот факт, что первое направление выбирается в соответствии с антиградиентом. При другом выборе d итерационный процесс (8) не приводит к набору сопряжённых направлений. С помощью доказанных выше свойств g T d i = i < и g T g i = i < можно несколько упростить выражения для α и β в итерационных процессах (6), (8): α = g d d T Ad β = gt + Ad d T Ad = g (g +β d) d T Ad = gt g d T Ad, = gt + (g + g) d T Ad = gt + g + α g T g. () В результате получаем итоговый алгоритм решения СЛАУ Ax = b, который получил название метода сопряжённых градиентов:. Задаём начальное приближение x и требуемую точность ε;. Инициализация d = g, = ;. x + = x +α d, где α = gt g d T Ad ; 4. Если α d < ε, то стоп; Пространства такого вида известны в линейной алгебре как пространства Крылова j=

4 5. d + = g + +β d, где β = gt + g + g T g ; 6. = + и переход к шагу. Данный алгоритм гарантированно сходится к решению за N шагов, где N размерность пространства решения. На каждом шаге итерационного процесса требуется проводить только одно умножение матрицы A на вектор d (векторax + при этом вычисляется какax +α Ad). Остальные операции в алгоритме являются векторными: скалярное произведение двух векторов и сумма двух векторов. На рис. показан пример применения этого алгоритма. Для сравнения показана также траектория метода наискорейшего спуска Рис. : Пример работы метода наискорейшего спуска (зеленая траектория) и метода сопряжённых градиентов (красная траектория) для оптимизации квадратичной функции. Основные преимущества метода сопряжённых градиентов связаны с пространствами большой размерности. При N методы решения СЛАУ, основанные на матричных разложениях, например, разложении Холецкого или QR-разложении, перестают быть применимыми в силу необходимости итерационного пересчета матриц, размер которых совпадает с размером матрицы A. Напротив, в методе сопряжённых градиентов все операции производятся только для векторов размерности N, а самая сложная операция в алгоритме это умножение матрицы A на очередной вектор d. Для ряда матриц специального вида, например, разреженных матриц или матриц, представляющих базис Фурье, такое умножение может быть проведено эффективнее общего случая. Метод сопряжённых градиентов для минимизации произвольной функции Рассмотрим теперь задачу оптимизации произвольной гладкой функции f. Тогда в схеме метода сопряжённых градиентов матрицаaзаменяется на гессианh в текущей точкеx. Практически данный подход превращается в метод Ньютона, в котором квадратичная аппроксимация функции минимизируется с помощью сопряжённых градиентов. Поэтому метод сопряжённых градиентов имеет квадратичную скорость сходимости в малой окрестности оптимального решения. Для того, чтобы застраховаться от возможной неадекватности квадратичного приближения функции f в текущей точке, в методе сопряжённых градиентов предлагается решать одномерную задачу оптимизации при движении вдоль очередного направления d: x + = x +α d, α = argmin α f(x +αd). Заметим, что в этом случае отпадает необходимость вычисления гессиана, и метод превращается в метод оптимизации первого порядка. При использовании формулы () для β соответствующий метод сопряжённых градиентов получил название Флетчера-Ривса (Fletcher-Reeves). В методе Полака-Рибье (Pola-Ribiere) предлагается использовать другую формулу для β: β = gt + g + g T + g g T g. Для случая квадратичной функции последняя формула переходит в формулу (), т.к. g T + g =. Однако, для произвольной функции она позволяет добиться более устойчивой и качественной работы метода. В методе сопряжённых градиентов направление d + зависит от d, а, значит, неявно зависит от всех предыдущих направлений d,...,d. Для повышения устойчивости работы метода для неквадратичной функции предлагается устанавливать β = после каждой N-ой итерации, т.е. периодически «очищать» предысторию, в которой могут накапливаться неудачные направления. Обнуление β соответствует выбору направления оптимизации по антиградиенту. На рис.,a показан пример применения метода сопряжённых градиентов без использования обнуления. В результате в ходе итераций метод «проскочил» оптимальную точку [,] T за счет 4

5 (a) (b) (c) Рис. : Примеры работы метода сопряжённых градиентов для функции Розенблока. Случай (a): без использования обнуления β, всего 64 итерации, случай (b): с использованием обнуления, всего 6 итераций, случай (c): использование bactracing, всего 6 итераций. сильной зависимости от предыдущих направлений. Напротив, использование обнуления (см. рис.,b) позволило успешно обнаружить минимум за меньшее число итераций. Как было отмечено выше, в методе сопряжённых градиентов очередное направление оптимизации выбирается таким образом, чтобы при движении вдоль него сохранить минимум по всем предыдущим направлениям. За счёт этого удаётся избежать ступенчатого поведения, характерного для покоординатного и градиентного спуска. Однако, такой подход неявно предполагает, что вдоль очередного направления проводится точная оптимизация, т.к. в дальнейшем возврат к этому направлению не запланирован. На рис.,c показан пример работы метода, в котором на этапе одномерной оптимизации используется bactracing. В результате метод начинает работать крайне неустойчиво, а сходимость достигается только за 6 итераций. В реальности метод сопряжённых градиентов может устойчиво сходиться и при использовании неточной одномерной оптимизации. Однако, её использование связано с определёнными рисками. Квази-ньютоновские методы В квази-ньютоновских методах оптимизации пересчёт осуществляется по формуле x + = x α S g. () Здесь S некоторая положительно-определённая матрица. Условие положительной определённости S гарантирует возможность уменьшения функции f вдоль направления d = S g. Действительно, α f(x αs g) = g T S g <. α= Если S = I, то () переходит в градиентный спуск. Если S = H, то () переходит в метод Ньютона. По аналогии с методом сопряжённых градиентов, рассмотрим сначала квази-ньютоновские методы для случая минимизации квадратичной функции (). Введем обозначения: δ = x + x = α S g, γ = g + g. Для квадратичной функции γ = g + g = Aδ. В результате [γ γ... γ N ] = A[δ δ... δ N ]. Пусть в первый момент времени задано некоторое начальное приближение x. Положим S = I 4 и будем пересчитывать S по правилу S + = S + C, где C некоторая матрица. Проведем N шагов вида () и получим набор {δ,...,δ N }, набор {γ,...,γ N } и набор матриц S,S,...,S N. Если оказывается, что S N [γ γ... γ N ] = [δ δ... δ N ], то матрица S N = A и следующий шаг по схеме () соответствует шагу Ньютона, т.е. x N+ = x. По аналогии с методом сопряжённых градиентов, в котором существуют разные формулы для β и, соответственно, разные итерационные схемы пересчета d, для квази-ньютоновских методов также предложено несколько способов выбора C. Однако, все эти способы гарантируют выполнение следующих свойств:. Метод сходится за N шагов для квадратичной функции; 4 это соответствует использованию направления антиградиента 5

6 (a) (b) Рис. : Примеры работы метода L-BFGS для функции Розенблока. Случай (a): точная одномерная оптимизация, случай (b): использование метода Флетчера.. Для квадратичной функции набор векторов {δ,...,δ N } образует сопряжённый базис относительно матрицы A;. Матрица S всегда остаётся положительно-определённой. Последнее свойство важно для принципиальной возможности уменьшения f на каждой итерации. Рассмотрим несколько схем выбора C: Схема DFP (Davidon-Fletcher-Powell). Схема BFGS (Broyden-Fletcher-Goldfarb-Shanno). S + = S + δ δ T δ T γ S γ γ T S γ T S. γ (S + = S + + γt S) γ δ δ T γ T δ γ T δ δ γ T S +S γ δ T γ T δ. Схема L-BGFS (Limited Memory BFGS). Формула пересчета аналогична BFGS, но для S = I: Подставляя эту формулу в (), получаем: (S + = I + + γt γ) δ δ T γ T δ γ T δ δ γ T +γ δ T γ T δ. d + = S + g + = g + +A δ +B γ, A = gt + δ (γ T δ + γt γ) γ T δ + gt + γ γ T δ, B = gt + δ γ T δ. Заметим, что все квази-ньютоновские методы являются методами первого порядка. В случае квадратичной функции направления δ,...,δ N являются сопряжёнными относительно A. Поэтому в этом случае все квази-ньютоновские методы эквивалентны методу сопряжённых градиентов. При этом существенным моментом является использование направления антиградиента в первый момент времени (S = I). При использовании другой матрицы S генерируемые направления оптимизации δ,...,δ N теряют свойства сопряжённости, а сам метод свойство гарантированной сходимости за N итераций. На рис.,а показан пример работы метода L-BFGS для функции Розенблока. Заметим, что в отличие от метода сопряжённых градиентов, в квази-ньютоновских методах нет необходимости «очищать» предысторию и периодически приравнивать S = I. Кроме того, квази-ньютоновские методы являются более толерантными к использованию неточной одномерной оптимизации (см. рис.,b). 6

Лекция 4 МЕТОДЫ ПЕРВОГО ПОРЯДКА Постановка задачи Пусть дана функция f (), ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех его точках. Требуется найти локальный минимум

ЛЕКЦИЯ 6 1. Метод покоординатного спуска 2. Градиентный метод 3. Метод Ньютона Методы решения конечномерных задач оптимизации (Задачи безусловной оптимизации) -1- Численные методы НЛП Задача поиска безусловного

Методы оптимизации, ФКН ВШЭ, зима 2017 Практическое задание 2: Продвинутые методы безусловной оптимизации. Срок сдачи: 9 марта 2017 (23:59). Язык программирования: Python 3. 1 Алгоритмы В этом задании

Методы оптимизации, ФКН ВШЭ, зима 2017 Семинар 7: Квазиньютоновские методы 21 февраля 2017 г 1 Квазиньютоновские методы 11 Мотивация Рассмотрим стандартную задачу гладкой безусловной оптимизации: min f(x),

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики процессов управления А. П. ИВАНОВ, Ю. В. ОЛЕМСКОЙ ПРАКТИКУМ ПО ЧИСЛЕННЫМ МЕТОДАМ МИНИМИЗАЦИЯ КВАДРАТИЧНОЙ ФУНКЦИИ Методические

ЛЕКЦИЯ 11 МНОГОМЕРНАЯ ИНТЕРПОЛЯЦИЯ ЗАДАЧА ОПТИМИЗАЦИИ На прошлой лекции были рассмотрены методы решения нелинейных уравнений Были рассмотрены двухточечные методы, которые используют локализацию корня,

УДК 59.8 О. А. Юдин, аспирант ПОИСК МИНИМУМА ФУНКЦИЙ, КОТОРЫЕ ИМЕЮТ РАЗРЫВЫ ЧАСТНЫХ ПРОИЗВОДНЫХ Проанализированы возможные варианты решения задачи поиска минимума функции, которая имеет разрыв частной

ЛЕКЦИЯ 14 Численные методы нелинейного программирования 1. Градиентный метод 2. Теоремы сходимости 3. Метод Такахаши (дуализация/градиентный метод) -1- Численные методы НЛП Задача поиска безусловного минимума:

ОПТИМАЛЬНЫЙ ГРАДИЕНТНЫЙ МЕТОД МИНИМИЗАЦИИ ВЫПУКЛЫХ ФУНКЦИЙ М. В. Долгополик [email protected] 10 ноября 2016 г. Аннотация. В докладе обсуждается в некотором смысле оптимальный градиентный метод

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Ортогональные и ортонормированные наборы векторов Из определения угла между векторами

К. В. Григорьева Методические указания Тема. Методы решения задачи минимизации квадратичной функции Факультет ПМ-ПУ СПбГУ 7 г. ОГЛАВЛЕНИЕ. ПОСТАНОВКА ЗАДАЧИ. ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ.... МЕТОДЫ СПУСКА

Семинары по линейным классификаторам Евгений Соколов 27 октября 2013 г. Пусть X R d пространство объектов, Y = { 1,+1} множество допустимых ответов, X l = (x i,y i) l i=1 обучающая выборка. Каждый объект

ЛЕКЦИЯ 15 1. Метод Ньютона (метод второго порядка) 2. Метод внешних штрафов 3. Метод внутренних штрафов 4. Метод покоординатного спуска -1- МЕТОД НЬЮТОНА Пусть f дважды непрерывно дифференцируемая функция

Лекция 5 Постановка и возможные пути решения задачи обучения нейронных сетей Частичная задача обучения Пусть у нас есть некоторая нейросеть N. В процессе функционирования эта нейронная сеть формирует выходной

Санкт-Петербургский государственный политехнический университет Факультет технической кибернетики Кафедра распределённых вычислений и компьютерных сетей Реферат Тема: «Методы оптимизации без ограничений,

ЛЕКЦИЯ 6 СПЕКТРАЛЬНЫЕ ЗАДАЧИ. Методы спуска На прошлой лекции были рассмотрены итерационные методы вариационного типа. Для системы Au = f, для которой выполняется A = A, был введен функционал Φ(u, u)

Тема 2-11: Собственные векторы и собственные значения А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия

Лекция 0. Глава 4. Матрицы. В этой главе мы рассмотрим основные виды матриц, операции над ними, понятие ранга матрицы и их приложения к решению систем линейных алгебраических уравнений. 4.. Основные понятия.

ГЛАВА 8. ПОДПРОСТРАНСТВА 1 1. СУММА И ПЕРЕСЕЧЕНИЕ ПОДПРОСТРАНСТВ Множество L векторов линейного пространства X называется подпространством, если из того, что x, y L вытекает, что αx + βy L при любых комплексных

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,

Методы оптимизации в машинном обучении, ВМК+Физтех, осень 2017 Практическое задание 3: Метод барьеров. 1 Метод барьеров Срок сдачи: 15 ноября 2017 (среда), 23:59 для ВМК 17 ноября 2017 (пятница), 23:59

Перечень методов,включенных в задачи к экзаменационным билетам. Билет 20 (метка) Метод Ньютона Билет 12 (метка) калькулятор http://math.semestr.ru/simplex/simplex_manual.php Построить двойственную задачу

Тема 2-4: Подпространства А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (2 семестр)

Содержание Элеметарная теория погрешностей. Решение СЛАУ. 4. Нормы в конечномерных пространствах... 4. Обусловленность СЛАУ............ 5.3 Итерационные методы решения линейных систем......................

Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем

А.П.Попов Методы оптимальных решений Пособие для студентов экономических специальностей вузов Ростов-на-Дону 01 1 Введение В прикладной математике имеется несколько направления, нацеленных в первую очередь

1 Материалы к установочной лекции Вопрос 37. Итеративные методы решения уравнений. Метод Ньютона. 1. Решение скалярных уравнений. Метод Чебышева Рассмотрим уравнение f(x) =0,x , и пусть на указанном

Московский государственный технический университет имени НЭ Баумана Факультет «Фундаментальные науки» Кафедра «Высшая математика» Е Б Павельева В Я Томашпольский Линейная алгебра Методические указания

Решение нелинейных уравнений Не всегда алгебраические или трансцендентные уравнения могут быть решены точно Понятие точности решения подразумевает:) возможность написания «точной формулы», а точнее говоря

Линейные преобразования Определение линейного преобразования Пусть V линейное пространство Если указано правило по которому каждому вектору x из V ставится в соответствие единственный вектор y из V то

Системы линейных алгебраических уравнений Основные понятия Системой линейных алгебраических уравнений (СЛАУ) называется система вида a a a, a a a, a a a Ее можно представить в виде матричного уравнения

ПРИМЕНЕНИЕ МЕТОДА НЬЮТОНА В СИММЕТРИЧНОЙ ПРОБЛЕМЕ СОБСТВЕННЫХ ЗНАЧЕНИЙ О.О. Хамисов Иркутский госуниверситет Существует множество различных проблем, таких как устойчивость системы линейных уравнений или

УДК 519.615.7 Физико-математические науки Предлагается квазиньютоновский численный метод безусловной минимизации, показываются его преимущества перед методом Бройдена Флетчера Гольдфарба Шанно. Ключевые

Лекция3. 3. Метод Ньютона (касательных. Зададим некоторое начальное приближение [,b] и линеаризуем функцию f(в окрестности с помощью отрезка ряда Тейлора f(= f(+ f "((-. (5 Вместо уравнения (решим

Решения задач по алгебре за второй семестр Д.В. Горковец, Ф.Г. Кораблев, В.В. Кораблева 1 Линейные векторные пространства Задача 1. Линейно зависимы ли векторы в R 4? a 1 = (4, 5, 2, 6), a 2 = (2, 2, 1,

Лабораторная работа Методы минимизации функций одной переменной, использующие информацию о производных целевой функции Постановка задачи: Требуется найти безусловный минимум функции одной переменной (

Методы решения сеточных уравнений 1 Прямые и итерационные методы В результате разностной аппроксимации краевых задач математической физики получаются СЛАУ, матрицы которых обладают следующими свойствами:

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА Механико математический факультет Кафедра вычислительной математики И. О. Арушанян Практикум на ЭВМ Безусловная минимизация функций многих переменных

ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ В разделе «Численные методы линейной алгебры» рассматриваются численные методы решения систем линейных алгебраических уравнений (СЛАУ) и численные методы решения задач

41 Симметрические операторы Линейные операторы, действующие в евклидовых пространствах, обладают дополнительными свойствами по сравнению с линейными операторами в векторных пространствах без скалярного

Занятие 1. Векторный анализ. 1.1. Краткое теоретическое введение. Физические величины, Z Z (M) для определения которых K достаточно задать одно число Y K (положительное или Y отрицательное) называются

4 Итерационные методы решения СЛАУ Метод простых итераций При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми на ЭВМ прежде всего из-за

ЛЕКЦИЯ 3 ЧИСЛЕННОЕ РЕШЕНИЕ СЛАУ Вспомним основные результаты, полученные на предыдущей лекции 1 Норма вектора = u Были введены следующие нормы вектора: =1 1 Октаэдрическая норма: 1 = max u, где p = 2 Кубическая

Лекция 11. Оптимальное управление 11.1 Постановка задачи Задана динамическая система с управлением, описываемая системой дифференциальных уравнений в форме Коши { ẋi = f i (x, u(t)), (11.1) (i = 1,...,

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики процессов управления М. Э. АББАСОВ МЕТОДЫ ОПТИМИЗАЦИИ Учебное пособие Санкт-Петербург 014 УДК 519.85 ББК.18 А 13 Р е ц е

ЛИНЕЙНАЯ АЛГЕБРА ВМЕСТЕ С MAPLE Усов В.В. 1 Скалярное произведение в арифметическом пространстве 1.1 Определение. Основные свойства Скалярное произведение (X, Y) векторов X = (x 1, x 2,..., x n), Y =

Методы решения сеточных уравнений 1 Прямые и итерационные методы В результате разностной аппроксимации краевых и начально-краевых задач математической физики получаются СЛАУ матрицы которых обладают следующими

Math-Net.Ru Общероссийский математический портал Л. Н. Полякова, Некоторые методы минимизации максимума квадратичных функций, Владикавк. матем. журн., 2006, том 8, номер 4, 46 57 Использование Общероссийского

6 Методы приближения функций. Наилучшее приближение. Рассмотренные в прошлой главе методы приближения требуют строгой принадлежности узлов сеточной функции результирующему интерполянту. Если не требовать

Тема 2-15: Ортогональность А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (2 семестр)

12. Линейные операторы на векторных пространствах (продолжение) Единственность жордановой нормальной формы F алгебраически замкнутое поле Теорема 9. τ Пусть A M n (F), A J и A J где J, J жордановы матрицы.

1. Численные методы решения уравнений 1. Системы линейных уравнений. 1.1. Прямые методы. 1.2. Итерационные методы. 2. Нелинейные уравнения. 2.1. Уравнения с одним неизвестным. 2.2. Системы уравнений. 1.

79 Линейные функции Определение и примеры линейных функций Определение Будем говорить, что на линейном пространстве L задана функция от одного вектора, если каждому вектору x L сопоставлено число (x)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ Методические указания к выполнению лабораторных работ ПЕНЗА 7 Приведена методика и

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический

Митюков В.В. Ульяновское высшее авиационное училище гражданской авиации институт, программист ОВТИ, [email protected] Универсальное моделирование дискретно заданных множеств непрерывными зависимостями КЛЮЧЕВЫЕ

Планы ответов на вопросы экзаменационных билетов госэкзамена по курсу ОПТИМИЗАЦИЯ И ЧИСЛЕННЫЕ МЕТОДЫ, лектор проф. М. М. Потапов Вопрос: 4. Симплекс-метод для канонической задачи линейного программирования:

345 4 Ряды Фурье по ортогональным системам функций Пусть ((x - ортогональная система функций в L [ ; ] Выражение c (x + c1 (x + 1 c (x + + (c (x = c (x (41 = называется обобщенным рядом Фурье по

Численная оптимизация Функции многих переменных: условная оптимизация 26 ноября 2012 г. Численная оптимизация 26 ноября 2012 г. 1 / 27 x (l) i f(x) min, g j (x) 0, h k (x) = 0, x R n j = 1,..., J k = 1,...,

Таблица 1

Таблица 2

№	Вид квадратичной формы	Вид ограничений
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.	2

Таблица 3

Координаты начальной точки
№	1	2	3	4	5	6	7	8	9	10	11	12	13
	3	0	-2	5	6	7,5	3	3	1	4	7	4	7
	-2	1	12	-3	-2	-2	0	4	2	3	1	4	3

Этапы проектирования

Постановка задачи в соответствии с вариантом задания.
Представление заданной квадратичной формы в матричной форме записи.
Исследование характера экстремума.
Описание в матричной форме метода поиска и составление алгоритма.
Составление структурной схемы алгоритма поиска.
Программирование в среде Math Cad.
Расчет.
Выводы по работе.

Постановка и решение задач многомерной безусловной оптимизации

Задачи многомерной безусловной минимизации

Для заданной функции решить задачу многомерной безусловной минимизации f(x 1 , x 2), xX (XR) и начальной точки x 0 .
Пусть f(x) = f(x 1 , x 2 , … ,x n) – действительная функция n переменных, определенная на множестве X Ì R n . Точка x* Î X называется точкой локального минимума f(x) на множестве X, если существует такая
e-окрестность этой точки, что для всех x из этой окрестности, т. е., если
|| x - x*|| < e, выполняется условие f(x*) £ f(x).
Если выполняется условие f(x*) < f(x), то x* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x*Î X называется точкой глобального минимума f(x) на множестве X, если для всех x Î X выполняется условие f(x*) £ f(x). Значение функции f(x*) называется минимальным значением f(x) на множестве X. Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение. В дальнейшем будем рассматривать задачу нахождения локального минимума.

Теорема 1 (необходимое условие экстремума)
Пусть есть точка локального минимума (максимума) функции f(x) на множестве и она дифференцируема в точке х*. Тогда градиент функции в точке х* равен нулю:

Теорема 2 (достаточное условие)
Пусть функция f(x) в точке х* дважды дифференцируема, ее градиент равен нулю, а матрица Гессе является положительно определенной (отрицательно определенной), т. е.

Тогда точка х* есть точка локального минимума (максимума) функции на множестве .
Для определения знака матрицы Гессе используется критерий Сильвестра.

Задание 1.1 Найти минимум функции классическим методом , используя необходимые и достаточные условия.
Данную задачу будем решать для функции f(x 1 ,x 2).
Начальная точка x 0
; x 0 =(1.5,1.5)

Найдем частные производные первого порядка функции f(x):

; ; ;

Найдем производные второго порядка функции f(x):

Составим матрицу Гессе

Классифицируем матрицу Гессе, используя критерий Сильвестра:

Следовательно, матрица является положительно определенной.
Используя критерии проверки достаточных условий экстремума, можно сделать вывод: точка - является точкой локального минимума.
Значение функции в точке минимума:
;

Задание 1.2
Найти минимум данной функции методом градиентного спуска с дроблением шага.

Метод градиентного спуска с дроблением шага

Метод градиентного спуска является одним из самых распространенных и самых простых методов решения задачи безусловной оптимизации. Он основан на свойстве градиента функции, согласно которому направление градиента совпадает с направлением наискорейшего возрастания функции, а направление антиградиента – с направлением наискорейшего убывания функции. При решении задачи безусловной минимизации за направление спуска из точки x(m) выбирается

p(m) = –g(x(m)) = –f "(x(m)).

Таким образом, итерационная процедура для этого метода имеет вид

x(m+1) = x(m) – a(m)g(x(m)) (*)

Для выбора шага a(m) можно использовать процедуру дробления шага, которая состоит в следующем. Произвольно фиксируют начальное значение шага a(m) = a(m – 1) = a. Если в точке x(m+1), вычисленной в соответствии с (2.24), выполняется неравенство

f(x(m+1)) > f(x(m)),

то шаг дробится, например, пополам, т.е. полагается a(m +1) = 0.5a(m).
Применим метод градиентного спуска с дроблением шага для минимизации квадратичной функции

В результате решения данной задачи был найден минимум
x* = (-0.182; -0.091),
значение функции f(x*) = -0.091,
количество итераций n = 17.

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

Градиентный спуск

В прошлой части был показан пример вычисления параметров линейной регрессии с помощью метода наименьших квадратов. Параметры были найдены аналитически - , где - псевдообратная матрица. Это решение наглядное, точное и короткое. Но есть проблема, которую можно решить численно. Градиентный спуск - метод численной оптимизации, который может быть использован во многих алгоритмах, где требуется найти экстремум функции - нейронные сети, SVM, k-средних, регрессии. Однако проще его воспринять в чистом виде (и проще модифицировать).

Проблема заключается в том, что вычисление псевдообратной матрицы очень затратно : 2 умножения по , нахождение обратной матрицы - , умножение матрицы вектор , где n - количество элементов в матрице A (количество признаков * количество элементов в тестовой выборке) Если количество элементов в матрице A велико (> 10^6 - например), то даже если в наличии 10000 ядер, нахождение решения аналитически может затянуться. Также первая производная может оказаться нелинейной, что усложнит решение, аналитического решения может не оказаться вовсе или данные могут просто не влезть в память и потребуется итеративный алгоритм. Бывает, что в плюсы записывают и то, что численное решение не идеально точное. В связи с этим функцию стоимости минимизируют численными методами. Задачу нахождения экстремума называют задачей оптимизации. В этой части я остановлюсь на методе оптимизации, который называется градиентный спуск.

Не будем отходить от линейной регрессии и МНК и обозначим функцию потерь как - она осталась неизменной. Напомню, что градиент - это вектор вида , где - это частная производная. Одним из свойств градиента является то, что он указывает направление, в котором некоторая функция f возрастает больше всего. Доказательство этого следует из определения производной. Пара доказательств . Возьмем некоторую точку a - в окрестности этой точки функция F должна быть определена и дифференцируема, тогда вектор антиградиента будет указывать на направление, в котором функция F убывает быстрее всего. Отсюда делается вывод, что в некоторой точке b, равной , при некотором малом значение функции будет меньше либо равным значению в точке а. Можно представить это, как движение вниз по холму - сделав шаг вниз, текущая позиция будет ниже, чем предыдущая. Таким образом, на каждом следующем шаге высота будет как минимум не увеличиваться. Формальное определение . Исходя из этих определений можно получить формулу для нахождения неизвестных параметров (это просто переписанная версия формулы выше):

Это шаг метода. В задачах машинного обучения его называют скоростью обучения.

Метод очень прост и интуитивен, возьмем простой двумерный пример для демонстрации:

Необходимо минимизировать функцию вида . Минимизировать значит найти при каком значении функция принимает минимальное значение. Определим последовательность действий:

1) Необходима производная по :
2) Установим начальное значение = 0
3) Установим размер шага - попробуем несколько значений - 0.1, 0.9, 1.2, чтобы посмотреть как этот выбор повлияет на сходимость.
4) 25 раз подряд выполним указанную выше формулу: Так как неизвестный параметр только один, то и формула только одна.

Код крайне прост. Исключая определение функций, весь алгоритм уместился в 3 строки:

simple_gd_console.py

STEP_COUNT = 25 STEP_SIZE = 0.1 # Скорость обучения def func(x): return (x - 5) ** 2 def func_derivative(x): return 2 * (x - 5) previous_x, current_x = 0, 0 for i in range(STEP_COUNT): current_x = previous_x - STEP_SIZE * func_derivative(previous_x) previous_x = current_x print("After", STEP_COUNT, "steps theta=", format(current_x, ".6f"), "function value=", format(func(current_x), ".6f"))

Весь процесс можно визуализировать примерно так (синяя точка - значение на предыдущем шаге, красная - текущее):

Или же для шага другого размера:

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

Код для генерации гифок

import matplotlib.pyplot as plt import matplotlib.animation as anim import numpy as np STEP_COUNT = 25 STEP_SIZE = 0.1 # Скорость обучения X = def func(x): return (x - 5) ** 2 def bad_func(x): return (x - 5) ** 2 + 50 * np.sin(x) + 50 Y = def func_derivative(x): return 2 * (x - 5) def bad_func_derivative(x): return 2 * (x + 25 * np.cos(x) - 5) # Какая-то жажа и первый кадр пропускается skip_first = True def draw_gradient_points(num, points, line, cost_caption, step_caption, theta_caption): global previous_x, skip_first, ax if skip_first: skip_first = False return points, line current_x = previous_x - STEP_SIZE * func_derivative(previous_x) step_caption.set_text("Step: " + str(num)) cost_caption.set_text("Func value=" + format(func(current_x), ".3f")) theta_caption.set_text("$\\theta$=" + format(current_x, ".3f")) print("Step:", num, "Previous:", previous_x, "Current", current_x) points.set_data(previous_x, func(previous_x)) points.set_data(current_x, func(current_x)) # points.set_data(, ) line.set_data(, ) if np.abs(func(previous_x) - func(current_x)) < 0.5: ax.axis() if np.abs(func(previous_x) - func(current_x)) < 0.1: ax.axis() if np.abs(func(previous_x) - func(current_x)) < 0.01: ax.axis() previous_x = current_x return points, line previous_x = 0 fig, ax = plt.subplots() p = ax.get_position() ax.set_position() ax.set_xlabel("$\\theta$", fontsize=18) ax.set_ylabel("$f(\\theta)$", fontsize=18) ax.plot(X, Y, "-r", linewidth=2.0) ax.axvline(5, color="black", linestyle="--") start_point, = ax.plot(, "bo", markersize=10.0) end_point, = ax.plot(, "ro") rate_capt = ax.text(-0.3, 1.05, "Rate: " + str(STEP_SIZE), fontsize=18, transform=ax.transAxes) step_caption = ax.text(-0.3, 1, "Step: ", fontsize=16, transform=ax.transAxes) cost_caption = ax.text(-0.3, 0.95, "Func value: ", fontsize=12, transform=ax.transAxes) theta_caption = ax.text(-0.3, 0.9, "$\\theta$=", fontsize=12, transform=ax.transAxes) points = (start_point, end_point) line, = ax.plot(, "g--") gradient_anim = anim.FuncAnimation(fig, draw_gradient_points, frames=STEP_COUNT, fargs=(points, line, cost_caption, step_caption, theta_caption), interval=1500) # Для того, чтобы получить гифку необходимо установить ImageMagick # Можно получить.mp4 файл без всяких magick-shmagick gradient_anim.save("images/animation.gif", writer="imagemagick")

Вот еще пример с «плохой» функцией. В первой анимации метод также расходится и будет долго блуждать по холмам из-за слишком высокого шага. Во втором случае был найден локальный минимум и варьируя значение скорости не получится заставить метод найти минимум глобальный. Этот факт является одним недостатков метода - он может найти глобальный минимум только если функция выпуклая и гладкая. Или если повезет с начальными значениями.

Плохая функция

Плохая функция:

Также возможно рассмотреть работу алгоритма на трехмерном графике. Часто рисуют только изолинии какой-то фигуры. Я взял простой параболоид вращения: . В 3D выглядит он так:
, а график с изолиниями - «вид сверху».

Contour plot

Генерация графика с изолиниями

import matplotlib.pyplot as plt import matplotlib.animation as anim import numpy as np STEP_COUNT = 25 STEP_SIZE = 0.005 # Скорость обучения X = np.array() Y = np.array() def func(X, Y): return 4 * (X ** 2) + 16 * (Y ** 2) def dx(x): return 8 * x def dy(y): return 32 * y # Какая-то жажа и первый кадр пропускается skip_first = True def draw_gradient_points(num, point, line): global previous_x, previous_y, skip_first, ax if skip_first: skip_first = False return point current_x = previous_x - STEP_SIZE * dx(previous_x) current_y = previous_y - STEP_SIZE * dy(previous_y) print("Step:", num, "CurX:", current_x, "CurY", current_y, "Fun:", func(current_x, current_y)) point.set_data(, ) # Blah-blah new_x = list(line.get_xdata()) + new_y = list(line.get_ydata()) + line.set_xdata(new_x) line.set_ydata(new_y) previous_x = current_x previous_y = current_y return point previous_x, previous_y = 8.8, 8.5 fig, ax = plt.subplots() p = ax.get_position() ax.set_position() ax.set_xlabel("X", fontsize=18) ax.set_ylabel("Y", fontsize=18) X, Y = np.meshgrid(X, Y) plt.contour(X, Y, func(X, Y)) point, = plt.plot(, , "bo") line, = plt.plot(, color="black") gradient_anim = anim.FuncAnimation(fig, draw_gradient_points, frames=STEP_COUNT, fargs=(point, line), interval=1500) # Для того, чтобы получить гифку необходимо установить ImageMagick # Можно получить.mp4 файл без всяких magick-shmagick gradient_anim.save("images/contour_plot.gif", writer="imagemagick")

Также обратите внимание, что все линии градиента, направлены перпендикулярно изолиниям. Это означает, что двигаясь в сторону антиградиента, не получится за один шаг сразу же прыгнуть в минимум - градиент указывает совсем не туда.

После графического пояснения, найдем формулу для вычисления неизвестных параметров линейной регрессии с МНК.

Если бы количество элементов в тестовой выборке было равно единице, то формулу можно было бы так и оставить и считать. В случае, когда в наличии n элементов алгоритм выглядит так:

Повторять v раз
{

для каждого j одновременно.
}, где n - количество элементов в обучающей выборке, v - количество итераций

Требование одновременности означает, что производная должна быть вычислена со старыми значениями theta, не стоит вычислять сначала отдельно первый параметр, затем второй и т.д., потому что после изменения первого параметра отдельно, производная также изменит свое значение. Псевдокод одновременного изменения:

For i in train_samples: new_theta = old_theta + a * derivative(old_theta) new_theta = old_theta + a * derivative(old_theta) old_theta = new_theta

Если вычислять значения параметров по одиночке, то это уже будет не градиентный спуск. Допустим, у нас трехмерная фигура и если вычислять параметры один за одним, то можно представить этот процесс как движение только по одной координате за раз - один шажок по x координате, затем шажок по y координате и т.д. ступеньками, вместо движения в сторону вектора антиградиента.

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

While abs(S_current - S_previous) >= Epsilon: # do something

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