Вычисление матриц Якоби и Гессе

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Содержание

1 Введение
- 1.1 Постановка математической задачи
  - 1.1.1 Вычисление матрицы Якоби
  - 1.1.2 Вычисление матрицы Гессе
2 Методы вычисления матрицы Якоби
- 2.1 Прямое вычисление частных производных
  - 2.1.1 Оценка погрешности метода
- 2.2 Метод Бройдена
3 Методы вычисления матрицы Гессе
4 Численный эксперимент
5 Рекомендации программисту
6 Заключение
7 Список литературы

Введение

Постановка математической задачи

Вычисление матрицы Якоби

Пусть задана система $n$ функций $y_1(x_1, x_2, \dots x_m) \dots y_n(x_1, x_2, \dots x_m)$ от $m$ переменных. Матрицей Якоби или якобианом данной системы функций называется матрица, составленная из частных производных этих функций по всем переменным.

$J=\begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_m} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_n}{\partial x_1} & \cdots & \frac{\partial y_n}{\partial x_m} \end{bmatrix}.$

Если в некоторой точке $x_1 \dots x_m$ очень сложно или невозможно вычислить частные производные, $\frac{\partial y_i}{\partial x_j}$ , то для вычисления матрицы Якоби применяются методы численного дифференцирования.

Вычисление матрицы Гессе

Матрицей Гессе функции $m$ переменных $y(x_1 \dots x_m)$ называется матрица, составленная из вторых производных функции $y(x_1 \dots x_m)$ по всем переменным

$H(f) = \begin{bmatrix} \frac{\partial^2 y}{\partial x_1^2} & \frac{\partial^2 y}{\partial x_1\,\partial x_2} & \cdots & \frac{\partial^2 y}{\partial x_1\,\partial x_m} \\ \\ \frac{\partial^2 y}{\partial x_2\,\partial x_1} & \frac{\partial^2 y}{\partial x_2^2} & \cdots & \frac{\partial^2 y}{\partial x_2\,\partial x_m} \\ \\ \vdots & \vdots & \ddots & \vdots \\ \\ \frac{\partial^2 y}{\partial x_m\,\partial x_1} & \frac{\partial^2 y}{\partial x_m\,\partial x_2} & \cdots & \frac{\partial^2 y}{\partial x_m^2} \end{bmatrix}$

Если в некоторой точке $x_1 \dots x_m$ очень сложно или невозможно вычислить частные производные, $\frac{\partial^2 y}{\partial x_i\ \partial x_j}$ , то для вычисления матрицы Гессе применяются методы численного дифференцирования.

Методы вычисления матрицы Якоби

Прямое вычисление частных производных

Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления производной $\frac{\partial y_i}{\partial x_j}$ применяются методы вычисления первой производной.

Формула для элемента якобиана при использовании правой разностной производной:
$J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_m)} {h_{ij} }$

Формула для элемента якобиана при использовании центральной разностной производной:
$J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_j - h_{ij} \dots x_m)} {2*h_{ij}}$

Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в $m * (n + 1)$ точках. Если использовать центральную производную, то нужно находить значения функций $y_1 \dots y_n$ в $2 * m * n$ точках. С другой, стороны погрешность правой производной имеет порядок $O(h)$ а центральной - $O(h^2)$ . В большинстве случаев вычисление значения функции $y_i$ - это затратная по времени операция, поэтому используется правая разностная производная.

Оценка погрешности метода

Основная проблема при вычислении каждого элемента матрицы Якоби - как правильно выбрать шаг метода $h_{ij}$ . Шаг выбирается независимо для каждого элемента матрицы.

Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной. Для сокращения записи введём обозначения $f(\xi_j) = y_i(x_1 \dots \xi_j \dots x_m)$ . Остаточный член в соотношении $f(x)' \approx \frac{f(x+ h) - f1}{h}$ имеет вид $r_1 = - f''(\xi)h/2$ . Если $|f''(\xi)| \le M_2$ , то $|r_1| \le M_2*h/2$ Если значения $f1$ и $f2$ заданы с погрешностями $\vareps_1, \vareps_2 \le E$ , то погрешность будет содержать ещё одно слагаемое $r_2 = - \frac{\vareps_1 - \vareps_2}{h} \le 2E/h$ . Таким образом, оценка суммарной погрешности имеет вид $|r| \le |r_1| + |r_2| \le f(h) = M_2 h/2 + 2E/h$ . Эта оценка достигает минимума при $h_0 = 2 \sqrt {E/M_2}$ . При этом $f(h_0) = 2 \sqrt{M_2 E}$ . Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. При величине шага, близкой к $h_0$ погрешность имеет порядок $O(\sqrt E)$ .

Метод Бройдена

Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений. При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации. Вычисление якобиана требует вычисления функций в $O(m * n)$ точках. Это сложная и затратная по времени операция. Суть метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации, а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций $y_1 \dots y_n$ и их производных.

Пусть задана система нелинейных уравнений $F(x) = 0$ , где $F:R^m \to R^n$ . Тогда якобиан на $n$ -ой итерации выражается по формуле
$J_n = J_{n - 1} + \frac{F(x_n) - F(x_{n-1}) - J_{n - 1} (x_n - x_{n-1})} { ||x_n - x_{n-1}||^2} (x_n - x_{n-1})^T$

После этого следующее приближение вычисляется по формуле

$x_{n + 1} = x_n - J_n^{-1} F(x_n)$

Методы вычисления матрицы Гессе

Как и матрица Якоби, матрица Гессе может быть вычислена с помощью разностной аппроксимации производных. $\frac{\partial^2 f}{\partial x_i\,\partial x_j} = \frac{ f(x + (e_i + e_j) h) - f(x + e_i h) - f(x + e_j h) + f(x) } {h^2}$ , где $x$ - вектор переменных, а $e_i$ и $e_j$ - единичные вектора. Эта формула требует вычисления значений функции $f$ в $\frac {n (n + 1)} {2}$ точках. Погрешность формулы имеет порядок $O(h)$ .

Численный эксперимент

В качестве примера рассчитаем с помощью вышеизложенного метода матрицу Гессе функции $x^2 * \sqrt y$ в точке (1, 1)

Величина шага	Численный результат	Истинное значение	Погрешность
0.01	$\begin{bmatrix} 1.999999999999780 & 1.002499984530392 \\ \\ 1.002499984530392 & -0.250007812910846 \end{bmatrix}$	$\begin{bmatrix} 2 & 1 \\ \\ 1 & -0.25 \end{bmatrix}$	$\begin{bmatrix} 0.000000000000220 & 0.002499984530392 \\ \\ 0.002499984530392 & 0.500007812910846 \end{bmatrix}$
0.001	$\begin{bmatrix} 1.999999999724444 & 1.000249999938419 \\1.000249999938419 & -0.250000078083623 \end{bmatrix}$	$\begin{bmatrix} 2 & 1 \\ \\ 1 & -0.25 \end{bmatrix}$	$\begin{bmatrix} 0.000000000275556 & 0.000249999938418 \\ \\ 0.000249999938418 & 0.500000078083623 \end{bmatrix}$
0.0001	$\begin{bmatrix} 1.999999998947288 & 1.000024996145044 \\ \\ 1.000024996145044 & -0.250000009582863 \end{bmatrix}$	$\begin{bmatrix} 2 & 1 \\ \\ 1 & -0.25 \end{bmatrix}$	$\begin{bmatrix} 0.000000001052712 & 0.000024996145044 \\ \\ 0.000024996145044 & 0.500000009582863 \end{bmatrix}$
0.00001	$\begin{bmatrix} 2.000002385926791 & 1.000002303186420 \\ \\ 1.000002303186420 & -0.250000020685093 \end{bmatrix}$	$\begin{bmatrix} 2 & 1 \\ \\ 1 & -0.25 \end{bmatrix}$	$\begin{bmatrix} 0.000002385926791 & 0.000002303186420 \\ \\ 0.000002303186420 & 0.500000020685093 \end{bmatrix}$

Заключение

Список литературы

Самарский А. А. , Гулин А. В. Численные методы. Москва «Наука», 1989.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. Лаборатория Базовых Знаний, 2003.
Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна. — М.:ФИЗМАТЛИТ, 2002. — 496 с.
Хайкин С. Нейронные сети, полный курс. 2е издание, испр. — М: Вильямс. 2008. — 1103 с ISBN 978-5-8459-0890-2
Bishop C. Exact calculation of the Hessian matrix for the multilayer perceptron / Neural Computation. Volume 4, Issue 4 (July 1992). Pp. 494—501. ISSN:0899-7667
MacKay D. How do you evaluate the Hessian in the first place?

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86_%D0%AF%D0%BA%D0%BE%D0%B1%D0%B8_%D0%B8_%D0%93%D0%B5%D1%81%D1%81%D0%B5»

Категории: Незавершённые статьи | Численное дифференцирование | Учебные задачи | Регрессионный анализ

@@ Строка 5: / Строка 5: @@
 ==== Вычисление матрицы Якоби ====
-Пусть задана система <tex>m</tex> функций <tex>y_1(x_1, x_2, \dots x_n) \dots y_m(x_1, x_2, \dots x_n)</tex> от <tex>m</tex> переменных. '''Матрицей Якоби''' данной системы функций называется
+Пусть задана система <tex>n</tex> функций <tex>y_1(x_1, x_2, \dots x_m) \dots y_n(x_1, x_2, \dots x_m)</tex> от <tex>m</tex> переменных. '''Матрицей Якоби''' или '''якобианом''' данной системы функций называется
 матрица, составленная из частных производных этих функций по всем переменным.
-<p align = "center">
 <tex>
-J=\begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_m}{\partial x_1} & \cdots & \frac{\partial y_m}{\partial x_n} \end{bmatrix}.
+J=\begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_m} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_n}{\partial x_1} & \cdots & \frac{\partial y_n}{\partial x_m} \end{bmatrix}.
 </tex>
-</p>
-Если в некоторой точке <tex>x_1 \dots x_m </tex> очень сложно или невозможно вычислить частные производные, <tex>\frac{\partial y_i}{\partial x_j} </tex>, то для вsчисления матрицы Якоби применяются методы численного дифференцирования.
+Если в некоторой точке <tex>x_1 \dots x_m </tex> очень сложно или невозможно вычислить частные производные, <tex>\frac{\partial y_i}{\partial x_j} </tex>, то для вычисления матрицы Якоби применяются методы численного дифференцирования.
+==== Вычисление матрицы Гессе ====
+'''Матрицей Гессе''' функции <tex>m</tex> переменных <tex>y(x_1 \dots x_m) </tex> называется матрица, составленная из вторых производных функции <tex>y(x_1 \dots x_m) </tex>  по всем переменным
+<tex>
+H(f) = \begin{bmatrix}
+\frac{\partial^2 y}{\partial x_1^2} & \frac{\partial^2 y}{\partial x_1\,\partial x_2} & \cdots & \frac{\partial^2 y}{\partial x_1\,\partial x_m} \\  \\
+\frac{\partial^2 y}{\partial x_2\,\partial x_1} & \frac{\partial^2 y}{\partial x_2^2} & \cdots & \frac{\partial^2 y}{\partial x_2\,\partial x_m} \\  \\
+\vdots & \vdots & \ddots & \vdots \\  \\
+\frac{\partial^2 y}{\partial x_m\,\partial x_1} & \frac{\partial^2 y}{\partial x_m\,\partial x_2} & \cdots & \frac{\partial^2 y}{\partial x_m^2}
+\end{bmatrix}
+</tex>
-== Изложение метода ==
+Если в некоторой точке <tex>x_1 \dots x_m </tex> очень сложно или невозможно вычислить частные производные, <tex>\frac{\partial^2 y}{\partial x_i\ \partial x_j} </tex>, то для вычисления матрицы Гессе применяются методы численного дифференцирования.
+== Методы вычисления матрицы Якоби ==
+=== Прямое вычисление частных производных ===
+Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления
+производной <tex>\frac{\partial y_i}{\partial x_j} </tex> применяются методы [[ Вычисление первой производной|вычисления первой производной]].
+Формула для элемента якобиана при использовании правой разностной производной: <br/>
+<tex> J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_m)} {h_{ij} } </tex>
+Формула для элемента якобиана при использовании центральной разностной производной:
+<br/>
+<tex> J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_j - h_{ij} \dots x_m)} {2*h_{ij}} </tex>
+<br/>
+Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в  <tex>m * (n + 1) </tex>
+точках. Если использовать центральную производную, то нужно находить значения функций <tex> y_1 \dots y_n </tex> в <tex>2 * m * n   </tex> точках. С другой, стороны погрешность правой производной имеет порядок <tex>O(h)</tex> а центральной - <tex>O(h^2)</tex>.
+В большинстве случаев вычисление значения функции <tex>y_i</tex> - это затратная по времени операция, поэтому используется правая разностная производная.
+====Оценка погрешности метода====
+Основная проблема при вычислении каждого элемента матрицы Якоби - как правильно выбрать шаг метода <tex> h_{ij} </tex>. Шаг выбирается независимо для каждого элемента матрицы.
+Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной.
+Для сокращения записи введём обозначения <tex>f(\xi_j) = y_i(x_1 \dots \xi_j \dots x_m)</tex>.
+Остаточный член в соотношении <tex> f(x)' \approx \frac{f(x+ h) - f1}{h} </tex> имеет вид
+<tex>r_1 = - f''(\xi)h/2 </tex>.
+Если <tex> |f''(\xi)| \le M_2 </tex>, то <tex>|r_1| \le M_2*h/2 </tex>
+Если значения <tex>f1</tex> и <tex>f2</tex> заданы с погрешностями <tex>\vareps_1, \vareps_2 \le E</tex> , то погрешность будет
+содержать ещё одно слагаемое <tex> r_2 = - \frac{\vareps_1 - \vareps_2}{h} \le 2E/h </tex>. Таким образом, оценка суммарной погрешности имеет вид <tex>|r| \le |r_1| + |r_2| \le f(h) = M_2 h/2 + 2E/h </tex>. Эта оценка достигает минимума при
+<tex>h_0 = 2 \sqrt {E/M_2}</tex>. При этом <tex> f(h_0) = 2 \sqrt{M_2 E} </tex>.
+Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. При величине шага, близкой к <tex>h_0</tex> погрешность имеет порядок <tex>O(\sqrt E) </tex>.
+===Метод Бройдена===
+Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений.
+При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации.
+Вычисление якобиана требует вычисления функций в <tex>O(m * n)</tex> точках. Это сложная и затратная по времени операция. Суть
+метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации,
+а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций <tex>y_1 \dots y_n</tex> и их производных.
+Пусть задана система нелинейных уравнений <tex>F(x) = 0</tex>, где <tex> F:R^m \to R^n </tex>.
+Тогда якобиан на <tex>n</tex>-ой итерации выражается по формуле <br/>
+<tex>
+J_n = J_{n - 1} + \frac{F(x_n) - F(x_{n-1}) - J_{n - 1} (x_n - x_{n-1})} { ||x_n - x_{n-1}||^2} (x_n - x_{n-1})^T
+</tex>
+После этого следующее приближение вычисляется по формуле
+<tex>x_{n + 1} = x_n - J_n^{-1} F(x_n) </tex>
+== Методы вычисления матрицы Гессе ==
+Как и матрица Якоби, матрица Гессе может быть вычислена с помощью разностной аппроксимации производных.
+<tex> \frac{\partial^2 f}{\partial x_i\,\partial x_j} =
+\frac{ f(x + (e_i + e_j) h) - f(x + e_i h) - f(x + e_j h) + f(x) } {h^2}</tex>, где
+<tex>x </tex> -  вектор переменных, а <tex>e_i</tex> и <tex>e_j</tex> - единичные вектора.
+Эта формула требует вычисления значений функции <tex> f </tex> в <tex> \frac {n (n + 1)} {2} </tex> точках.
+Погрешность формулы имеет порядок <tex>O(h)</tex>.
+== Численный эксперимент==
+В качестве примера рассчитаем с помощью вышеизложенного метода матрицу Гессе функции <tex>x^2 * \sqrt y </tex> в точке (1, 1)
+{| class="standard"
+|-
+! Величина шага||Численный результат || Истинное значение || Погрешность
+|-
+|0.01
+||
+<tex>
+\begin{bmatrix} 1.999999999999780 &  1.002499984530392 \\ \\  1.002499984530392 & -0.250007812910846 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix} 2 &  1 \\ \\  1 & -0.25 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix}
+.000000000000220 & 0.002499984530392 \\ \\ 0.002499984530392 & 0.500007812910846   \end{bmatrix}
+</tex>
+|-
+| 0.001||
+<tex>
+\begin{bmatrix} 1.999999999724444 & 1.000249999938419 \\1.000249999938419 & -0.250000078083623 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix} 2 &  1 \\ \\  1 & -0.25 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix}
+.000000000275556 & 0.000249999938418 \\ \\ 0.000249999938418 & 0.500000078083623  \end{bmatrix}
+</tex>
+|-
+| 0.0001||
+<tex>
+\begin{bmatrix} 1.999999998947288 & 1.000024996145044 \\ \\ 1.000024996145044 & -0.250000009582863 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix} 2 &  1 \\ \\  1 & -0.25 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix} 0.000000001052712 & 0.000024996145044 \\ \\ 0.000024996145044 & 0.500000009582863  \end{bmatrix}
+</tex>
+|-
+|0.00001 ||
+<tex>
+\begin{bmatrix} 2.000002385926791 & 1.000002303186420 \\ \\ 1.000002303186420 & -0.250000020685093  \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix} 2 &  1 \\ \\  1 & -0.25 \end{bmatrix}
+</tex>
+||
+<tex>
+\begin{bmatrix} 0.000002385926791 & 0.000002303186420 \\ \\ 0.000002303186420 & 0.500000020685093  \end{bmatrix}
+</tex>
+|}
-== Числовой пример ==
 == Рекомендации программисту ==
+Вычисление матрицы Якоби требует большого числа операций.  Поэтому при выборе метода её вычисления следует найти оптимальный баланс
+между погрешностью метода и его скоростью.
+[[Media:Slimper_Jacobian.zip| Программа для вычисления якобиана, исходный код [1кб]]]
+[[Media:Slimper_Hessian.zip| Программа для вычисления гессиана, исходный код [1кб] ]]
+[[Media:Slimper_Ublas.zip| Библиотека алгоритмов линейной алгебры [180кб] ]]
 == Заключение ==
 == Список литературы ==
-* А. А. Самарский, А. В. Гулин. Численные методы. Москва «Наука», 1989.
+* Самарский А. А. , Гулин А. В. Численные методы. Москва «Наука», 1989.
-* Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. Численные методы. Лаборатория Базовых Знаний, 2003.
+* Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. Лаборатория Базовых Знаний, 2003.
-* Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна.&nbsp;— М.:ФИЗМАТЛИТ, 2002.&nbsp;— 496&nbsp;с.
+* Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна.&nbsp;— М.:ФИЗМАТЛИТ, 2002.&nbsp;— 496&nbsp;с.
-* Хайкин С. Нейронные сети, полный курс. 2е издание, испр. - М: Вильямс. 2008. - 1103 с. ISBN 978-5-8459-0890-2
+* Хайкин С. Нейронные сети, полный курс. 2е издание, испр. — М: Вильямс. 2008. — 1103 с ISBN 978-5-8459-0890-2
+* Bishop C. Exact calculation of the Hessian matrix for the multilayer perceptron / Neural Computation. Volume 4, Issue 4 (July 1992). Pp. 494—501. ISSN:0899-7667
+* [http://www.inference.phy.cam.ac.uk/mackay/Bayes_FAQ.html#hessian MacKay D. How do you evaluate the Hessian in the first place?]
 {{stub}}
 [[Категория:Численное дифференцирование]]
 [[Категория:Учебные задачи]]
+[[Категория:Регрессионный анализ]]