Matrix derivative (preview)

matrix_derivative.qq

\meta 
    \title Производные и градиенты
    \author Илья Щуров
        \affiliation НИУ ВШЭ
    \project
        Машинное обучение для факультета экономики, 2017-18 учебный год
        \url http://wiki.cs.hse.ru/Машинное_обучение_(факультет_экономических_наук)
    \lang ru

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

\section Что такое производная

\definition \label def:deriv
    \emph{Производная} — это линейная функция, хорошо приближающая приращение некоторой
    другой функции.

    Подробнее, рассмотрим функцию $f\colon \mathbb R^n \to \mathbb R^m$. Зафиксируем
    некоторую точку $x \in \mathbb R^n$. Производной функции $f$ в точке $x$
    называется такая линейная функция $A\colon \mathbb R^n\to \mathbb R^m$, что

    \eq
        f(x+h)=f(x)+A(h)+o(\|h\|),
    где $h \in \mathbb R^n$ — некоторый вектор, $\|h\|$ — его норма.

\subsection Примеры

\example
    Пусть $f\colon \mathbb R^1\to \mathbb R^1$, то есть мы рассматриваем обычные
    числовые функции, как в школе. Тогда в определении \ref{def:deriv} линейное
    отображение $A$ — это линейная функция из $\mathbb R^1$ в $\mathbb R^1$. Любая
    такая линейная функция является умножением на некоторое число, то есть $Ah =
    kh$. Это число $k$ обычно и называют производной для случая числовых функций:
    $k=f'(x)$.

\example
    Пусть $f\colon \mathbb R^n \to \mathbb R^1$, то есть мы рассматриваем
    числовые функции нескольких переменных. Тогда в определении \ref{def:deriv}
    линейное отображение $A$ — это линейная функция из $\mathbb R^n$ в $\mathbb
    R^1$, то есть линейный функционал на пространстве $\mathbb R^n$. Если в
    этом пространстве введён базис и в этом базисе $h=(h_1, \ldots, h_n)$, то любой такой
    функционал имеет вид $Ah=a_1 h_1+\ldots a_n h_n$. В этом случае $a_k$,
    $k=1,\ldots, n$ — это частная производная функции $f$ по $x_k$:

    \equation \label eq:differential
        Ah = \frac{\partial f}{\partial x_1}(x)h_1+\ldots+\frac{\partial f}{\partial x_n}(x)h_n

Эта штука более известна как \emph{дифференциал} функции нескольких переменных. Мы будем обозначать его через $df_{x}$, то есть $df_{x}(h)=Ah$.

\example
    Пусть $f\colon \mathbb R^n \to \mathbb R^m$, то есть мы рассматриваем
    произвольный случай. Если на пространствах $\mathbb R^n$ и $\mathbb R^m$
    заданы базисы, то отображение $A$, как и любое линейное отображение,
    задаётся некоторой матрицей. Подробнее, пусть $x=(x_1, \ldots, x_n)$ и
    $f=(f_1, \ldots, f_m)$, где $f_k\colon \mathbb R^n \to \mathbb R^1$, $k=1,
    \ldots, m$. Тогда матрица отображения $A$ — это матрица частных производных:

    \eq
        A_{ij}=\frac{\partial f_i}{\partial x_j}(x).

    Эта матрица также известна как матрица Якоби. Мы будем обозначать
    соответствующее отображение через $D_{x}f$.

\remark
    Само понятие производной не требует введения какого-либо базиса и каких-либо
    координат. Это просто линейное отображение. Но координаты позволяют записать
    его в виде матрицы.
\remark
    Производная в заданной точке $x$ является линейным отображением от вектора
    приращения $h$. Но зависимость этого отображения от $x$ вообще говоря не
    является линейной. В каждой точке есть своя производная.

\section Что такое градиент

Пусть на $n$-мерном векторном пространстве $V^n$ задано скалярное произведение,
которое мы будем обозначать $\langle u, v \rangle$. (Возможно, вы привыкли к
тому, что скалярное произведение определяется как сумма поэлементных
произведений векторов, но вообще говоря оно может задаваться и другой формулой.)

Рассмотрим отображение $\phi_u(v)\colon V^n \to \mathbb R$, заданное следующим
нехитрым образом:

\equation \label eq:uv
    \phi_u(v)=\langle u, v\rangle.
Из свойств скалярного произведения мгновенно следует, что $\phi_u$ — линейное
отображение, то есть линейный функциионал на $V^n$.

Таким образом каждый вектор $u \in  V^n$ задаёт некоторый линейный
функционал на $V^n$. Оказывается, верно и обратное: любой линейный
функционал $\phi$ представляется в виде \ref{eq:uv} для некоторого вектора $u$.

\definition
    Рассмотрим отображение $f\colon \mathbb R^n\to \mathbb R^1$. Его
    \emph{градиентом} в точке $x$ называется такой вектор $u$, что
    \eq
        df_{x}(h)=\langle u, h\rangle,
    где $df_{x}$ — дифференциал функции $f$ в точке $x$.

Это определение замечательно своей бескоординатностью: оно не требует введения
частных производных, а требует только наличия скалярного произведения. Тем не
менее, если скалярное произведение задаётся стандартным образом ($\langle u, v
\rangle = u_1 v_1 + \ldots + u_n v_n$), то градиент оказывается вектором,
составленным из частных производных, как мы и привыкли. Действительно, в правой
части формулы \ref{eq:differential} написано скалярное произведение вектора
$\frac{\partial f}{\partial x_1}(x), \ldots, \frac{\partial f}{\partial
x_n}(x)$ и вектора $h$.

Мы будем обозначать градиент через $\nabla_{x} f$.

\section Некоторые стандартные производные
Здесь мы используем данные выше определения для вычисления некоторых производных
и градиентов. В дальнейшем мы будем использовать матричную нотацию, вектор $u\in
\mathbb R^n$ будет отождествляться с вектор-столбцом (матрицей с одним столбцом
и $n$ строками), транспонирование будет обозначаться верхним индексом $T$. 

Мы будем считать, что задано стандартное скалярное произведение $\langle u,
v\rangle = u_1 v_1 + \ldots + u_n v_n$. Его также можно находить как матричное
произведение вектор-строки $u$ на вектор-столбец $v$, то есть $u^T v$, или
наоборот, $v^T u$. 

\subsection Производная скалярного произведения
Рассмотрим отображение $f\colon \mathbb R^n \to \mathbb R$, заданное как
$f(u)=a^T u=\langle a, u\rangle$, где $a$ — некоторый фиксированнй вектор. 
    
В этом случае

\eq
    f(x+h)=a^T(x+h)=f(x) + a^T h
Отсюда мгновенно следует, что $df_{x}(h)=a^T h = \langle a, h \rangle$. Отсюда
и из определения градиента следует, что градиент равен вектору $a$.

\subsection Производная квадратичной формы

Рассмотрим отображение $f\colon \mathbb R^n \to \mathbb R$, заданное следующим
образом:

\eq
    f(u)=u^T A u = \langle u, Au \rangle.
Найдём его производную. Запишем:
\equation \label eq:xAx
    f(x+h)=(x+h)^T A(x + h)=(x)^T A x + (x)^T A h + h^T A x + h^T
    A h
Последнее слагаемое имеет порядок малости $o(\|h\|)$. Заметим, что всё выражение
является числом, а значит и каждое слагаемое является числом. Числа можно
транспонировать, они от этого не меняются. Значит,
\eq
    h^T A x = x^T A^T h.
Здесь мы воспользовались тем фактом, что при транспонировании произведения
сомножители переставляются. Таким образом, правая часть \ref{eq:xAx}
представляется в виде:
\eq
    f(x+h)=f(x)+x^T (A + A^T) h + o(\|h\|)
то есть $df_{x}(h)=x^T (A + A^T) h$. Это выражение также является
скалярным произведением вектор-строки $x^T (A+A^T)$ на вектор-столбец $h$.
Значит, градиентом является вектор $x^T (A+A^T)$. Но поскольку мы по
умолчанию записываем векторы в виде вектор-столбцов, для приведения градиента к
стандартной записи нужно транспонировать указанное выше выражение. Имеем:

\eq
    \nabla_{x}(h)=(A+A^T)x.

\subsection След
Рассмотрим функцию «след» $\newcommand{\Tr}{\mathop{\mathrm{Tr}}}\Tr$ из пространства матриц в числа. Для матрицы $A=(a_{ij})$ след определяется как сумма диагональных элементов:

\eq
    \Tr A = a_{11} + \ldots + a_{nn}

След играет важную роль в дальнейшем, поскольку с его помощью можно легко
записать скалярное произведение между матрицами. Действительно, давайте введём в
пространстве матриц базис, состоящий из матриц, у которых на $ij$-ом месте стоит
1, а на всех остальных местах — нули. Иными словами, мы отождествляем матрицу
$n\times n$ с вектором из пространства $\mathbb R^{n^2}$, записывая, например,
все компоненты матрицы по строкам в качестве компонент этого вектора. Так
матрица

\eq
    \begin{pmatrix} a_{11} & a_{12} \\\\
                    a_{21} & a_{22}
    \end{pmatrix}
превращается в вектор $(a_{11}, a_{12}, a_{21}, a_{22})$.

Если ввести теперь на матрицах скалярное произведение так же, как на векторах,
то оно будет записываться в виде
\equation \label eq:ABTR
    \langle A, B \rangle = \Tr (A^TB).
Проверка этого факта проводится непосредственым вычислением, которое мы
предлагаем сделать читателю самостоятельно.

\subsection Производная и градиент следа
Найдём теперь производную следа в точке $X$. Аргументом следа является
матрица, поэтому мы получим «производную по матрице» и $X$ тоже является
матрицей.

\eq
    \Tr(X+H)=\Tr(X)+\Tr(H).
Это равенство следует из определения следа. Таким образом, производная следа
— это тоже след, $D_{X} \Tr(H)=\Tr(H)$.

Чему равен градиент следа? Иными словами, какую матрицу $W$ нужно взять, чтобы
скалярное произведение $H$ с этой матрицей равнялось $\Tr(H)$. Из формулы
\ref{eq:ABTR} видим, что $W=E$, тождественная матрица.

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

\subsection Производная и градиент определителя
Рассмотрим отображение $f(A)=\det A$. Это снова отображение из пространства
матриц в числа. Найдём его производную и градиент.

\equation \label eq:det
    \det (X + H) = \det (X(E+X^{-1} H)) = \det(X)\det (E+X^{-1}H).
Здесь мы воспользовались мультипликативностью определителя: $\det AB = \det A
\det B$, которая мгновенно следует из его геометрического смысла (если матрицы
$A$ растягиваем объем в $\det A$ раз, а матрица $B$ в $\det B$ раз, то их
последовательное применение растянет объём в произведение определителей раз).

Обозначим матрицу $X^{-1}H$ через $Y$. Пусть собственные значения $Y$ равны
$\lambda_1, \ldots, \lambda_n$. Поскольку $H$ маленькая, то $Y$ тоже маленькая и
её собственные значения маленькие. Определитель не меняется при заменах базиса,
поэтому перейдём к жорданову базису для $H$. Матрица $E$ при этом переходе не
изменится (она вообще в любом базисе выглядит как тождественная). Получающаяся
при этом матрица верхнетреугольная и на её диагонали стоят числа $1+\lambda_1,
\ldots, 1+\lambda_n$. Определитель верхнетреугольной матрицы равен произведению
чисел на диагонали и значит

\eq
    \det (E+Y)=(1+\lambda_1)\cdot(1+\lambda_n)=1+(\lambda_1 + \ldots +
    \lambda_n)+o(\|Y\|)
Здесь мы воспользовались тем, что собственные значения маленкие и их
произведения имеют ещё больший порядок малости.

Сумма собственных значений матрицы равна её следу (это верно в жордановом
базисе, но след не зависит от базиса и собственные числа тоже, значит это верно
в любом базисе). Значит
\eq
    \det(E+Y)=1+\Tr(Y)+o(\|Y\|)
Подставляя это в уравнение \ref{eq:det}, имеем:
\eq
    \det (X + H) = \det(X) (1 + \Tr(X^{-1} H)+o(\|H\|)) =\det (X) + \det
    X\Tr(X^{-1} H) + o(\|H\|)
Отсюда следует, что производная определителя в точке $X$ равна
\eq
    (d_{X}\det)(H)=\det (X)\Tr(X^{-1} H)
Можно внести $\det X$ под знак следа (в силу линейности следа). Тогда имеем:
\eq
    (d_{X}\det)(H)=\Tr(\det (X) X^{-1} H)
Значит градиентом является $(\det(X)X^{-1})^T=\det(X)(X^{-1})^T$.