RUВход: минимум на прямой
Функция $f(x)=(x^1)^2+2(x^2)^2$ на плоскости. Где она меньше всего, если точка обязана лежать на прямой $x^1+x^2=3$? Без ограничения ответ — начало координат, но оно на прямую не попадает. Чтобы ответить, нужны три вещи из сегодняшней лекции: производная вдоль прямой (цепное правило), условие «производная равна нулю» (теорема Ферма) и способ учесть ограничение (множители Лагранжа). Ответ — в конце раздела про Лагранжа.
Производная — это линейное отображение
Лекция началась с уточнения. Матрица $A\in M_{D\times N}$ задаёт отображение $u\mapsto Au$, и оно линейно: $A(u+v)=Au+Av$, $A(\lambda u)=\lambda Au$. Любое линейное отображение $\R^N\to\R^D$ записывается такой матрицей. Поэтому в определении из лекции 1
$$f(x_0+u)-f(x_0)=Df(x_0)\,u+o(\lVert u\rVert)$$производная $Df(x_0)$ по своей природе — линейное отображение, а матрица — способ его записать.
Способ записи — выбор, как выбор системы координат. Линейные функции $\R^N\to\R$ записывают строками: строка $a^t$ действует по правилу $u\mapsto a^tu$. Поэтому при $D=1$ производная — строка. Если же аргумент — матрица, нужна другая запись.
Производная функции от матрицы (соглашение лектора)Линейная функция $M_{m\times n}\to\R$ записывается матрицей $C\in M_{n\times m}$, которая действует по правилу $U\mapsto\tr(CU)$. Для $f:M_{m\times n}\to\R$ производная $Df(X_0)\in M_{n\times m}$ определяется равенством
$$f(X_0+U)-f(X_0)=\tr\big(Df(X_0)\,U\big)+o(\lVert U\rVert).$$Практическая форма: если для всех $U$ выполнено $\lim_{h\to0}\frac{f(X_0+hU)-f(X_0)}{h}=\tr(ZU)$, а $f$ дифференцируема, то $Z=Df(X_0)$.
Размеры сходятся: $C$ размера $n\times m$, $U$ размера $m\times n$, произведение $CU$ квадратное $n\times n$, и у него есть след. Лектор сказал прямо: «это моё соглашение». Оно объясняет ответ $b\,a^t$ для $f(X)=a^tXb$ из лекции 1: там $a^tUb=\tr(a^tUb)=\tr(b\,a^tU)$.
Пример. $f(X)=\tr(X^tX)=\lVert X\rVert^2$, $X\in M_{m\times n}$. Подставляем $X_0+hU$ и раскрываем скобки:
$$f(X_0+hU)=\tr(X_0^tX_0)+h\,\tr(U^tX_0)+h\,\tr(X_0^tU)+h^2\tr(U^tU).$$Матрица и транспонированная имеют один след, поэтому $\tr(U^tX_0)=\tr\big((X_0^tU)^t\big)=\tr(X_0^tU)$. Делим разность на $h$ и устремляем $h\to0$: остаётся $2\tr(X_0^tU)$. Значит, $Df(X_0)=2X_0^t$, размер $n\times m$.
Транспонирование, которое теряютБиблиотеки машинного обучения хранят градиент по матрице весов $W$ в форме самой $W$. Это $(Df)^t$, а не $Df$. Внутри одного решения держись одного соглашения: в этом курсе $Df(X_0)$ стоит слева от $U$ под следом. Проверка размером: для $X\in M_{m\times n}$ матрица $Df(X_0)$ обязана иметь размер $n\times m$.
Зачем это в MLСлой сети — это $x\mapsto Wx$ с матрицей весов $W$. Шаг обучения сдвигает $W$ на $-\eta\,(Df)^t$, поэтому производную по матрице считают для каждого слоя на каждом шаге.
Доказательство цепного правила
Идея в одной фразе: даём $t$ приращение $\Delta t$, смотрим, насколько сдвинулось $u$ (это $\Delta u$), и насколько изменилось $f$. Лектор разобрал основной случай: $y=f(u^1,\dots,u^N)$, $u^j=g_j(t)$, производная $Df(u_0)$ существует, все $g_j'(t_0)$ существуют, $u_0=g(t_0)$.
Шаг 1. Вспомогательная функция $G$. По определению производной $f(u_0+\Delta u)-f(u_0)=Df(u_0)\Delta u+o(\lVert\Delta u\rVert)$. Положим
$$G(\Delta u)=\begin{cases}\dfrac{f(u_0+\Delta u)-f(u_0)-Df(u_0)\Delta u}{\lVert\Delta u\rVert}, & \Delta u\neq0,\\[4pt] 0, & \Delta u=0.\end{cases}$$Тогда $\lim_{\Delta u\to0}G(\Delta u)=0$, и равенство
$$f(u_0+\Delta u)-f(u_0)=Df(u_0)\Delta u+G(\Delta u)\,\lVert\Delta u\rVert$$верно для любого $\Delta u$: при $\Delta u\ne0$ это определение $G$, умноженное на $\lVert\Delta u\rVert$, а при $\Delta u=0$ обе части равны нулю.
Зачем $G$. Дальше мы делим на $\Delta t$, а $\Delta u$ может оказаться нулём при $\Delta t\ne0$ (например, если $g$ постоянна около $t_0$). Делить на $\lVert\Delta u\rVert$ тогда нельзя, а форма с $G$ этот случай покрывает.
Шаг 2. Подстановка. Берём $\Delta u=g(t_0+\Delta t)-g(t_0)$ и делим на $\Delta t$:
$$\frac{f(g(t_0+\Delta t))-f(g(t_0))}{\Delta t}=\sum_{j=1}^{N}\frac{\partial f}{\partial u^j}(u_0)\,\frac{g_j(t_0+\Delta t)-g_j(t_0)}{\Delta t}+G(\Delta u)\frac{\lVert\Delta u\rVert}{\Delta t}.$$Шаг 3. Лишнее слагаемое стремится к нулю. Его модуль равен $\lvert G(\Delta u)\rvert\cdot\big\lVert\frac{\Delta u}{\Delta t}\big\rVert$. Каждая $g_j$ дифференцируема, значит непрерывна, поэтому $\Delta u\to0$ и $G(\Delta u)\to0$. Второй множитель стремится к длине конечного вектора $(g_1'(t_0),\dots,g_N'(t_0))^t$. Произведение стремится к нулю, и
$$\left.\frac{dy}{dt}\right|_{t_0}=\sum_{j=1}^{N}\frac{\partial f}{\partial u^j}(u_0)\,g_j'(t_0).\qquad\blacksquare$$При $N=1$ это то же доказательство обычного цепного правила.
Цепное правило в общем видеДля отображений $G:\R^N\to\R^M$ и $F:\R^M\to\R^D$ (здесь $G$ — другое отображение, не функция из доказательства)
$$D(F\circ G)(x_0)=DF\big(G(x_0)\big)\,DG(x_0).$$Справа композиция линейных отображений, в матрицах — произведение размеров $(D\times M)(M\times N)$.
Лектор: производная так важна потому, что превращает композицию нелинейных отображений в композицию линейных и сохраняет саму композицию.
Зачем это в MLОбратное распространение ошибки — это ровно эта формула для сети из многих слоёв: матрицы Якоби слоёв перемножаются, начиная с последнего слоя.
Производная по направлению
Положим $g(t)=f(x_0+tu)$: это $f$, суженная на прямую через $x_0$ с направлением $u$. Внутренняя функция $t\mapsto x_0+tu$ имеет производную $u$, поэтому по цепному правилу
$$g'(0)=Df(x_0)\,u=\langle\nabla f(x_0),u\rangle.$$Это производная по направлению: скорость изменения $f$, когда точка движется только вдоль этой прямой.
Пример. $f(x)=(x^1)^2x^2$, $x_0=(1,2)^t$, $u=(1,1)^t$. Частные производные $2x^1x^2=4$ и $(x^1)^2=1$, значит $Df(x_0)=(4,\ 1)$ и $g'(0)=4\cdot1+1\cdot1=5$. Проверка подстановкой: $g(t)=(1+t)^2(2+t)$, $g'(t)=2(1+t)(2+t)+(1+t)^2$, $g'(0)=4+1=5$.
Две ошибки, которые лектор исправил у доскиНе пиши $f'$ для функции многих переменных — пиши $Df$. Порядок важен: $u$ стоит справа от $Df(x_0)$, потому что это произведение матриц. И производная берётся при $t=0$: в ответе не должно остаться $t$.
Если двигаться не по прямой, а по кривой $\gamma(t)$, то так же $\frac{d}{dt}f(\gamma(t))=Df(\gamma(t))\,\gamma'(t)$.
Тейлор для функции многих переменных
Возьмём $f:\R^N\to\R$ и точки $a,b\in\R^N$. Сузим $f$ на отрезок между ними:
$$g(t)=f\big((1-t)a+tb\big),\qquad t\in[0,1].$$Внутренняя функция имеет производную $b-a$. Все частные производные ниже берутся в точке $(1-t)a+tb$:
$$g'(t)=\sum_{i=1}^{N}\frac{\partial f}{\partial x^i}\,(b^i-a^i),$$$$g''(t)=\sum_{i=1}^{N}\sum_{j=1}^{N}\frac{\partial^2 f}{\partial x^j\partial x^i}\,(b^j-a^j)(b^i-a^i),$$$$g'''(t)=\sum_{k=1}^{N}\sum_{j=1}^{N}\sum_{i=1}^{N}\frac{\partial^3 f}{\partial x^k\partial x^j\partial x^i}\,(b^k-a^k)(b^j-a^j)(b^i-a^i).$$Каждая следующая производная добавляет ещё одну сумму и ещё один множитель вида $(b-a)$: к $g'$ применяется то же цепное правило, только вместо $f$ стоит $\partial f/\partial x^i$. Формула Тейлора одной переменной для $g$ на $[0,1]$ и равенство $f(b)-f(a)=g(1)-g(0)$ дают конечную формулу Тейлора для $f$.
ДополнениеНа лекции это не было сказано (на доске начато «Remark», текст не виден). Матрица вторых производных $H_{ij}=\frac{\partial^2f}{\partial x^i\partial x^j}$ называется матрицей Гессе; для дважды непрерывно дифференцируемой $f$ она симметрична. Тогда $g''(t)=(b-a)^tH(b-a)$ и
$$f(b)=f(a)+Df(a)(b-a)+\tfrac12(b-a)^tH(\xi)(b-a),\qquad \xi=(1-\tau)a+\tau b,\ \tau\in(0,1).$$ Пример. $f(x)=x^1x^2$, $a=(0,0)^t$, $b=(1,2)^t$. Здесь $H=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ и $(b-a)^tH(b-a)=2\cdot1\cdot2=4$. Проверка: $g(t)=t\cdot2t=2t^2$, $g''(t)=4$.
Зачем это в MLКвадратичный член $\frac12u^tHu$ описывает кривизну функции потерь. Из-за него слишком большой шаг градиентного спуска перескакивает минимум, а метод Ньютона делит шаг на кривизну.
Замена переменных: полярные координаты
Пусть $f(x,y)$ — функция на плоскости, и $x=r\cos\theta$, $y=r\sin\theta$. Функция $F(r,\theta)=f(r\cos\theta,r\sin\theta)$ — композиция, и на доске цепное правило дало
$$\frac{\partial f}{\partial r}=\frac{\partial f}{\partial x}\cos\theta+\frac{\partial f}{\partial y}\sin\theta,\qquad
\frac{\partial f}{\partial\theta}=\frac{\partial f}{\partial x}(-r\sin\theta)+\frac{\partial f}{\partial y}\,r\cos\theta.$$В матричной форме это строка, умноженная на матрицу производной замены:
$$\Big(\frac{\partial f}{\partial r},\ \frac{\partial f}{\partial\theta}\Big)=\Big(\frac{\partial f}{\partial x},\ \frac{\partial f}{\partial y}\Big)\begin{pmatrix}\cos\theta&-r\sin\theta\\ \sin\theta&r\cos\theta\end{pmatrix}.$$Пример. $f(x,y)=x^2+y^2$. Тогда $\frac{\partial f}{\partial r}=2x\cos\theta+2y\sin\theta=2r$ и $\frac{\partial f}{\partial\theta}=-2xr\sin\theta+2yr\cos\theta=0$. Проверка: $F(r,\theta)=r^2$ от $\theta$ не зависит.
Обратная задача (первая часть пункта 2 домашнего задания) — выразить $\partial f/\partial x$ и $\partial f/\partial y$ через $\partial f/\partial r$, $\partial f/\partial\theta$: это система $2\times2$ с матрицей выше.
Вторые производные. Коротко: $f_x=\partial f/\partial x$, $f_{xy}=\partial^2f/\partial x\partial y$. Главное правило: $f_x$ — тоже функция от $x,y$, а значит, через замену — от новых переменных. Для любой замены $x=x(s,t)$, $y=y(s,t)$
$$\frac{\partial}{\partial s}\Big[f_x\big(x(s,t),y(s,t)\big)\Big]=f_{xx}\,\frac{\partial x}{\partial s}+f_{xy}\,\frac{\partial y}{\partial s}.$$А произведение $f_x\cdot\frac{\partial x}{\partial s}$ дифференцируется по правилу произведения: второе слагаемое $f_x\,\frac{\partial^2x}{\partial s^2}$ пропадает, только когда $\frac{\partial^2x}{\partial s^2}=0$ (например, у линейной замены; у полярной — при дифференцировании по $r$, но не по $\theta$).
Слагаемое, которое теряютЧастая ошибка во второй производной — продифференцировать только $f_x$ и забыть про коэффициент замены. У полярных координат коэффициент $\partial x/\partial\theta=-r\sin\theta$ сам зависит от $\theta$, поэтому в $\partial^2f/\partial\theta^2$ появятся первые производные $f_x$, $f_y$. Проверка: возьми $f$, для которой ответ известен заранее (например, $x^2+y^2=r^2$), и подставь.
Лектор назвал эти выкладки проверкой: кто проводит их без ошибок, тот владеет цепным правилом.
Зачем это в MLЗамена переменных в модели (нормировка признаков, переход к логарифмам, другая параметризация весов) меняет градиент ровно по этому правилу: строка производных умножается на матрицу производной замены.
Оптимизация: что можно минимизировать
Две оговорки лектора. Целевая функция должна быть вещественной: сравнивать по величине можно только вещественные числа; у векторов и даже у комплексных чисел пригодного порядка нет. Область определения теперь важна: дифференциальное исчисление локально, а вопрос о минимуме зависит от того, где область кончается.
Теорема Ферма
Теорема Ферма (необходимое условие)Пусть $f:D\to\R$, $D\subseteq\R^N$, принимает наименьшее (или наибольшее) значение на $D$ в точке $x_0$, производная $Df(x_0)$ существует и $x_0$ — внутренняя точка $D$. Тогда $Df(x_0)=0$, то есть все частные производные в $x_0$ равны нулю.
Внутренняя точка$x_0$ — внутренняя точка $D$, если есть $\varepsilon>0$, при котором открытый шар $B(x_0,\varepsilon)=\{x:\lVert x-x_0\rVert<\varepsilon\}$ целиком лежит в $D$.
Каждая точка интервала $(0,1)$ внутренняя; точка $0$ для отрезка $[0,1]$ — нет: любой шар вокруг неё вылезает влево. Лектор привёл контрпример без условия «внутренняя»: линейную функцию на $[0,1]$ (в записи слышно «twice», вероятно $f(x)=2x$). Минимум в $x=0$, а $f'(0)=2\ne0$ — потому что $0$ лежит на границе.
Идея доказательства. Для каждого направления $u$ функция $g(t)=f(x_0+tu)$ имеет минимум при $t=0$, и $0$ — внутренняя точка её области. По теореме Ферма одной переменной $g'(0)=Df(x_0)\,u=0$ для всех $u$, значит $Df(x_0)=0$. Полное доказательство — задача m0209.
Необходимое — не значит достаточное$f(x)=x^3$ на $[-1,1]$: $f'(0)=0$, но в нуле нет ни минимума, ни максимума, а минимум достигается в $x=-1$. Условие $Df=0$ только сужает поиск: кандидаты — точки с $Df=0$ внутри области и отдельно граница.
Зачем это в MLГрадиент функции потерь равен нулю и в минимумах, и в максимумах, и в седловых точках. Поэтому «градиентный спуск остановился» ещё не значит «найден минимум».
Наименьшие квадраты
Дано $A\in M_{D\times N}$, $b\in\R^D$; ищем минимум $f(x)=\lVert b-Ax\rVert^2$ по $x\in\R^N$. Область — всё $\R^N$, поэтому каждая точка внутренняя. Совет лектора: минимизируй квадрат расстояния, а не расстояние — точка минимума та же, а функция гладкая. Из лекции 1 $Df(x)=-2(b-Ax)^tA$; приравниваем нулю, как на доске:
$$-2(b-Ax)^tA=0\ \Rightarrow\ -2(b-Ax)^t(A^t)^t=0\ \Rightarrow\ -2(A^tb-A^tAx)^t=0\ \Rightarrow\ A^tb-A^tAx=0.$$Нормальные уравненияТочка минимума $\lVert b-Ax\rVert^2$ удовлетворяет системе $A^tAx=A^tb$ размера $N\times N$.
Пример. Приблизим три числа $1, 2, 6$ одной константой $x$: $A=(1,1,1)^t$, $b=(1,2,6)^t$. Тогда $A^tA=3$, $A^tb=9$, $x=3$ — среднее арифметическое. Проверка: невязка $b-Ax=(-2,-1,3)^t$ ортогональна столбцу $A$, сумма её координат равна $0$.
Лектор перечислил вопросы, которые нужно задать всегда. Существует ли минимум? Здесь да; а максимума нет: при $A\ne0$ функция уходит в бесконечность. Есть ли у уравнения решение? Единственно ли оно? Для наименьших квадратов решение есть всегда, может быть не единственным, и любое решение даёт минимум. Доказательство лектор отложил до линейной алгебры.
Зачем это в MLСтроки $A$ — объекты, столбцы — признаки, $b$ — ответы. Нормальные уравнения дают веса линейной регрессии без градиентного спуска. Если два признака коллинеарны, $A^tA$ вырождена, и решение перестаёт быть единственным.
Ограничения: геометрия Лагранжа
Задача с доски. Дан треугольник $ABC$. Точки $P$ с $\lvert PA\rvert+\lvert PB\rvert=d_1$ образуют эллипс с фокусами $A$, $B$ — это кривая ограничения. Найти минимум $\lvert PC\rvert$ (целевой функции) на этом эллипсе. Если $d_1=\lvert AB\rvert$, эллипс вырождается в отрезок $AB$, и ответ — расстояние от $C$ до отрезка.
Ответ. Минимум достигается в точке $P_0$, где отрезок $CP_0$ ортогонален эллипсу, то есть касательной к нему.
Переформулировка. Множества уровня целевой функции $\{P:\lvert PC\rvert=\text{const}\}$ — окружности с центром $C$. Радиус перпендикулярен касательной к окружности, поэтому «$CP_0$ ортогонален эллипсу» значит: линия уровня целевой функции через $P_0$ касается кривой ограничения.
Почему это необходимо. Если линия уровня пересекает кривую ограничения, а не касается её, то движение вдоль ограничения в одну сторону уменьшает целевую функцию, а в другую — увеличивает. Значит, $P_0$ не минимум и не максимум. Это и есть геометрическая форма метода множителей Лагранжа.
По оптическому свойству эллипса касательная образует равные углы с отрезками до фокусов, поэтому $CP_0\perp$ эллипсу $\iff\angle AP_0C=\angle BP_0C$. Отсюда точка Ферма: минимум $\lvert PA\rvert+\lvert PB\rvert+\lvert PC\rvert$ может быть только там, где все три угла при $P$ равны $120°$, если минимум не в вершине треугольника (в вершине $\lvert PA\rvert$ не дифференцируема). Это снова необходимое условие: существование минимума нужно знать отдельно.
Теорема о множителях Лагранжа
Теорема Лагранжа (необходимое условие)Пусть $f$ на множестве $\{x\in\R^N: g_1(x)=0,\dots,g_r(x)=0\}$, $r<N$, принимает наименьшее или наибольшее значение в точке $x_0$, функции гладкие, а матрица Якоби отображения $(g_1,\dots,g_r)$ в $x_0$ имеет полный ранг $r$. Тогда существуют числа $\lambda_1,\dots,\lambda_r$ (множители Лагранжа), для которых
$$\nabla f(x_0)=\lambda_1\nabla g_1(x_0)+\dots+\lambda_r\nabla g_r(x_0).$$ Формулировка записана по аудио: на фотографиях доски её нет. Условие $r<N$: при $r\ge N$ ограничения обычно оставляют лишь отдельные точки. Перевести геометрическое условие касания в эту формулу лектор оставил как упражнение — это пункт 5 домашнего задания. Лектор: «геометрия — ангел, алгебра — дьявол, но с ангелом вечно не проживёшь».
Счёт уравнений. Неизвестных $N+r$: координаты $x^1,\dots,x^N$ и множители $\lambda_1,\dots,\lambda_r$. Уравнений столько же: $N$ из векторного равенства и $r$ ограничений.
Вход, решение. $f(x)=(x^1)^2+2(x^2)^2$, $g(x)=x^1+x^2-3$. Ранг строки $Dg=(1,\ 1)$ равен $1$. Условие $\nabla f=\lambda\nabla g$: $2x^1=\lambda$, $4x^2=\lambda$, значит $x^1=2x^2$. Из ограничения $3x^2=3$, $x^2=1$, $x^1=2$, $f=4+2=6$. Проверка подстановкой $x^1=3-x^2$: $(3-x^2)^2+2(x^2)^2$ имеет производную $6x^2-6$, ноль при $x^2=1$. Минимум существует: на прямой $f\to\infty$ в обе стороны.
Зачем это в MLОграничения в ML повсюду: вероятности в сумме дают $1$, норма весов ограничена, в методе опорных векторов отступы не меньше $1$. Множители Лагранжа — общий способ решать такие задачи.
Максимум энтропии
Пример лектора: минимизировать $f(x)=\sum_{i=1}^{N}x^i\ln x^i$ при $x^i\in[0,1]$ и ограничении $\sum_ix^i=1$.
Граница. При $x^i=0$ логарифма нет. По Лопиталю $x\ln x=\frac{\ln x}{1/x}$, и $\lim_{x\to0^+}\frac{1/x}{-1/x^2}=\lim_{x\to0^+}(-x)=0$. Поэтому полагают $0\ln0=0$, и $f$ непрерывна вплоть до границы.
Условие Лагранжа. $\nabla f=(\ln x^i+1)_i$, $\nabla g=(1,\dots,1)^t$. Равенство $\nabla f=\lambda\nabla g$ даёт $\ln x^i+1=\lambda$ для каждого $i$, то есть все $x^i$ равны. Это $N$ уравнений, вместе с ограничением $N+1$ на $N+1$ неизвестных. Ответ: $x^i=1/N$.
СмыслЧисла $x^i$ образуют распределение вероятностей, а $H(x)=-\sum_ix^i\ln x^i$ — его энтропия. Минимум $\sum x^i\ln x^i$ — это максимум энтропии, и кандидат — равномерное распределение. Что это действительно минимум, лектор обещал показать позже.
Зачем это в MLПерекрёстная энтропия — стандартная функция потерь классификатора. Если к условию $\sum p^i=1$ добавить ограничение на среднее, максимум энтропии даёт $p^i$, пропорциональные $e^{\lambda k_i}$, — форму softmax (финал m0220).
Что должно остаться в голове
- Производная — линейное отображение; для $f:M_{m\times n}\to\R$ она записывается матрицей $Df(X_0)\in M_{n\times m}$, действующей по правилу $U\mapsto\tr(Df(X_0)\,U)$.
- $D(F\circ G)=DF\cdot DG$: композиция нелинейных отображений переходит в произведение матриц.
- Сужение на прямую или отрезок, $g(t)=f(x_0+tu)$, сводит многомерный вопрос к одной переменной: $g'(0)=Df(x_0)\,u$.
- $g''$ на отрезке — квадратичная форма $(b-a)^tH(b-a)$; отсюда второй порядок Тейлора.
- При замене переменных строка производных умножается на матрицу производной замены; во вторых производных дифференцируй и $f_x$, и коэффициенты замены.
- $Df=0$ — только необходимое условие и только во внутренних точках; границу проверяют отдельно.
- Минимум $\lVert b-Ax\rVert^2$: нормальные уравнения $A^tAx=A^tb$.
- С ограничениями: $\nabla f=\sum\lambda_i\nabla g_i$ при полном ранге; уравнений $N+r$, неизвестных $N+r$.
- Максимум энтропии при одном ограничении $\sum p^i=1$ — равномерное распределение.
ENEntry: a minimum on a line
Take the function $f(x)=(x^1)^2+2(x^2)^2$ on the plane. Where is it smallest if the point must lie on the line $x^1+x^2=3$? Without the constraint the answer is the origin, but the origin is not on the line. To answer, you need three things from today’s lecture: the derivative along a line (chain rule), the condition “the derivative is zero” (Fermat’s theorem), and a way to take the constraint into account (Lagrange multipliers). The answer is at the end of the Lagrange section.
The derivative is a linear map
The lecture began with a clarification. A matrix $A\in M_{D\times N}$ defines the map $u\mapsto Au$, and this map is linear: $A(u+v)=Au+Av$, $A(\lambda u)=\lambda Au$. Every linear map $\R^N\to\R^D$ is written by such a matrix. So in the definition from lecture 1
$$f(x_0+u)-f(x_0)=Df(x_0)\,u+o(\lVert u\rVert)$$the derivative $Df(x_0)$ is by nature a linear map, and the matrix is a way to write it down.
How you write it is a choice, like choosing a coordinate system. Linear functions $\R^N\to\R$ are written as rows: the row $a^t$ acts by $u\mapsto a^tu$. So when $D=1$, the derivative is a row. If the argument is a matrix, a different way of writing is needed.
Derivative of a function of a matrix (the lecturer’s convention)A linear function $M_{m\times n}\to\R$ is written as a matrix $C\in M_{n\times m}$ acting by $U\mapsto\tr(CU)$. For $f:M_{m\times n}\to\R$ the derivative $Df(X_0)\in M_{n\times m}$ is defined by
$$f(X_0+U)-f(X_0)=\tr\big(Df(X_0)\,U\big)+o(\lVert U\rVert).$$Working form: if $\lim_{h\to0}\frac{f(X_0+hU)-f(X_0)}{h}=\tr(ZU)$ for every $U$ and $f$ is differentiable, then $Z=Df(X_0)$.
The sizes match: $C$ is $n\times m$, $U$ is $m\times n$, the product $CU$ is a square $n\times n$ matrix, and it has a trace. The lecturer said it plainly: “this is my convention.” It explains the answer $b\,a^t$ for $f(X)=a^tXb$ from lecture 1: there $a^tUb=\tr(a^tUb)=\tr(b\,a^tU)$.
Example. $f(X)=\tr(X^tX)=\lVert X\rVert^2$, $X\in M_{m\times n}$. Substitute $X_0+hU$ and expand:
$$f(X_0+hU)=\tr(X_0^tX_0)+h\,\tr(U^tX_0)+h\,\tr(X_0^tU)+h^2\tr(U^tU).$$A matrix and its transpose have the same trace, so $\tr(U^tX_0)=\tr\big((X_0^tU)^t\big)=\tr(X_0^tU)$. Divide the difference by $h$ and let $h\to0$: what remains is $2\tr(X_0^tU)$. Hence $Df(X_0)=2X_0^t$, of size $n\times m$.
The transpose that gets lostMachine learning libraries store the gradient with respect to a weight matrix $W$ in the shape of $W$ itself. That is $(Df)^t$, not $Df$. Within one solution, keep one convention: in this course $Df(X_0)$ stands to the left of $U$ under the trace. Size check: for $X\in M_{m\times n}$ the matrix $Df(X_0)$ must have size $n\times m$.
Why this matters for MLA network layer is $x\mapsto Wx$ with a weight matrix $W$. A training step changes $W$ by $-\eta\,(Df)^t$, so the derivative with respect to a matrix is computed for every layer at every step.
Proof of the chain rule
The idea in one sentence: give $t$ an increment $\Delta t$, see how far $u$ moved (that is $\Delta u$), and how much $f$ changed. The lecturer treated the essential case: $y=f(u^1,\dots,u^N)$, $u^j=g_j(t)$, the derivative $Df(u_0)$ exists, every $g_j'(t_0)$ exists, $u_0=g(t_0)$.
Step 1. The helper function $G$. By the definition of the derivative $f(u_0+\Delta u)-f(u_0)=Df(u_0)\Delta u+o(\lVert\Delta u\rVert)$. Define
$$G(\Delta u)=\begin{cases}\dfrac{f(u_0+\Delta u)-f(u_0)-Df(u_0)\Delta u}{\lVert\Delta u\rVert}, & \Delta u\neq0,\\[4pt] 0, & \Delta u=0.\end{cases}$$Then $\lim_{\Delta u\to0}G(\Delta u)=0$, and the equality
$$f(u_0+\Delta u)-f(u_0)=Df(u_0)\Delta u+G(\Delta u)\,\lVert\Delta u\rVert$$holds for every $\Delta u$: for $\Delta u\ne0$ it is the definition of $G$ multiplied by $\lVert\Delta u\rVert$, and for $\Delta u=0$ both sides are zero.
Why $G$. Next we divide by $\Delta t$, and $\Delta u$ can be zero while $\Delta t\ne0$ (for example, if $g$ is constant near $t_0$). Dividing by $\lVert\Delta u\rVert$ is then impossible, while the form with $G$ covers this case.
Step 2. Substitute. Take $\Delta u=g(t_0+\Delta t)-g(t_0)$ and divide by $\Delta t$:
$$\frac{f(g(t_0+\Delta t))-f(g(t_0))}{\Delta t}=\sum_{j=1}^{N}\frac{\partial f}{\partial u^j}(u_0)\,\frac{g_j(t_0+\Delta t)-g_j(t_0)}{\Delta t}+G(\Delta u)\frac{\lVert\Delta u\rVert}{\Delta t}.$$Step 3. The extra term goes to zero. Its absolute value is $\lvert G(\Delta u)\rvert\cdot\big\lVert\frac{\Delta u}{\Delta t}\big\rVert$. Each $g_j$ is differentiable, hence continuous, so $\Delta u\to0$ and $G(\Delta u)\to0$. The second factor tends to the length of the finite vector $(g_1'(t_0),\dots,g_N'(t_0))^t$. The product tends to zero, and
$$\left.\frac{dy}{dt}\right|_{t_0}=\sum_{j=1}^{N}\frac{\partial f}{\partial u^j}(u_0)\,g_j'(t_0).\qquad\blacksquare$$For $N=1$ this is the same proof of the ordinary chain rule.
The chain rule in general formFor maps $G:\R^N\to\R^M$ and $F:\R^M\to\R^D$ (here $G$ is another map, not the function from the proof)
$$D(F\circ G)(x_0)=DF\big(G(x_0)\big)\,DG(x_0).$$On the right is a composition of linear maps; in matrices, a product of sizes $(D\times M)(M\times N)$.
The lecturer: the derivative is so important because it turns a composition of nonlinear maps into a composition of linear ones and keeps the composition itself.
Why this matters for MLBackpropagation is exactly this formula for a network with many layers: the layers’ Jacobian matrices are multiplied, starting from the last layer.
Directional derivative
Let $g(t)=f(x_0+tu)$: this is $f$ restricted to the line through $x_0$ with direction $u$. The inner function $t\mapsto x_0+tu$ has derivative $u$, so by the chain rule
$$g'(0)=Df(x_0)\,u=\langle\nabla f(x_0),u\rangle.$$This is the directional derivative: the rate of change of $f$ when the point moves only along this line.
Example. $f(x)=(x^1)^2x^2$, $x_0=(1,2)^t$, $u=(1,1)^t$. The partial derivatives are $2x^1x^2=4$ and $(x^1)^2=1$, so $Df(x_0)=(4,\ 1)$ and $g'(0)=4\cdot1+1\cdot1=5$. Check by substitution: $g(t)=(1+t)^2(2+t)$, $g'(t)=2(1+t)(2+t)+(1+t)^2$, $g'(0)=4+1=5$.
Two mistakes the lecturer corrected at the boardDo not write $f'$ for a multivariable function — write $Df$. Order matters: $u$ stands to the right of $Df(x_0)$, because this is a matrix product. And the derivative is taken at $t=0$: no $t$ may remain in the answer.
If the point moves along a curve $\gamma(t)$ instead of a line, then in the same way $\frac{d}{dt}f(\gamma(t))=Df(\gamma(t))\,\gamma'(t)$.
Taylor for a multivariable function
Take $f:\R^N\to\R$ and points $a,b\in\R^N$. Restrict $f$ to the segment between them:
$$g(t)=f\big((1-t)a+tb\big),\qquad t\in[0,1].$$The inner function has derivative $b-a$. All partial derivatives below are evaluated at the point $(1-t)a+tb$:
$$g'(t)=\sum_{i=1}^{N}\frac{\partial f}{\partial x^i}\,(b^i-a^i),$$$$g''(t)=\sum_{i=1}^{N}\sum_{j=1}^{N}\frac{\partial^2 f}{\partial x^j\partial x^i}\,(b^j-a^j)(b^i-a^i),$$$$g'''(t)=\sum_{k=1}^{N}\sum_{j=1}^{N}\sum_{i=1}^{N}\frac{\partial^3 f}{\partial x^k\partial x^j\partial x^i}\,(b^k-a^k)(b^j-a^j)(b^i-a^i).$$Each new derivative adds one more sum and one more factor of the form $(b-a)$: the same chain rule is applied to $g'$, only with $\partial f/\partial x^i$ in place of $f$. Taylor’s formula in one variable for $g$ on $[0,1]$ and the equality $f(b)-f(a)=g(1)-g(0)$ give the finite Taylor formula for $f$.
Not from the lectureThis was not said in class (the board shows a started “Remark” whose text is not visible). The matrix of second derivatives $H_{ij}=\frac{\partial^2f}{\partial x^i\partial x^j}$ is called the Hessian matrix; for a twice continuously differentiable $f$ it is symmetric. Then $g''(t)=(b-a)^tH(b-a)$ and
$$f(b)=f(a)+Df(a)(b-a)+\tfrac12(b-a)^tH(\xi)(b-a),\qquad \xi=(1-\tau)a+\tau b,\ \tau\in(0,1).$$ Example. $f(x)=x^1x^2$, $a=(0,0)^t$, $b=(1,2)^t$. Here $H=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ and $(b-a)^tH(b-a)=2\cdot1\cdot2=4$. Check: $g(t)=t\cdot2t=2t^2$, $g''(t)=4$.
Why this matters for MLThe quadratic term $\frac12u^tHu$ describes the curvature of the loss. Because of it, a gradient descent step that is too large overshoots the minimum, and Newton’s method divides the step by the curvature.
Change of variables: polar coordinates
Let $f(x,y)$ be a function on the plane, and $x=r\cos\theta$, $y=r\sin\theta$. The function $F(r,\theta)=f(r\cos\theta,r\sin\theta)$ is a composition, and on the board the chain rule gave
$$\frac{\partial f}{\partial r}=\frac{\partial f}{\partial x}\cos\theta+\frac{\partial f}{\partial y}\sin\theta,\qquad
\frac{\partial f}{\partial\theta}=\frac{\partial f}{\partial x}(-r\sin\theta)+\frac{\partial f}{\partial y}\,r\cos\theta.$$In matrix form, this is a row multiplied by the derivative matrix of the change of variables:
$$\Big(\frac{\partial f}{\partial r},\ \frac{\partial f}{\partial\theta}\Big)=\Big(\frac{\partial f}{\partial x},\ \frac{\partial f}{\partial y}\Big)\begin{pmatrix}\cos\theta&-r\sin\theta\\ \sin\theta&r\cos\theta\end{pmatrix}.$$Example. $f(x,y)=x^2+y^2$. Then $\frac{\partial f}{\partial r}=2x\cos\theta+2y\sin\theta=2r$ and $\frac{\partial f}{\partial\theta}=-2xr\sin\theta+2yr\cos\theta=0$. Check: $F(r,\theta)=r^2$ does not depend on $\theta$.
The inverse problem (the first part of homework item 2) is to express $\partial f/\partial x$ and $\partial f/\partial y$ through $\partial f/\partial r$, $\partial f/\partial\theta$: this is a $2\times2$ system with the matrix above.
Second derivatives. Shorthand: $f_x=\partial f/\partial x$, $f_{xy}=\partial^2f/\partial x\partial y$. The main rule: $f_x$ is also a function of $x,y$, and therefore, through the change of variables, of the new variables. For any change $x=x(s,t)$, $y=y(s,t)$
$$\frac{\partial}{\partial s}\Big[f_x\big(x(s,t),y(s,t)\big)\Big]=f_{xx}\,\frac{\partial x}{\partial s}+f_{xy}\,\frac{\partial y}{\partial s}.$$And the product $f_x\cdot\frac{\partial x}{\partial s}$ is differentiated by the product rule: the second term $f_x\,\frac{\partial^2x}{\partial s^2}$ vanishes only when $\frac{\partial^2x}{\partial s^2}=0$ (for example, for a linear change; for the polar one, when differentiating in $r$ but not in $\theta$).
The term that gets lostA common mistake in a second derivative is to differentiate only $f_x$ and forget the coefficient of the change. In polar coordinates the coefficient $\partial x/\partial\theta=-r\sin\theta$ itself depends on $\theta$, so $\partial^2f/\partial\theta^2$ will contain the first derivatives $f_x$, $f_y$. Check: take an $f$ whose answer you know in advance (for example, $x^2+y^2=r^2$) and substitute.
The lecturer called these computations a test: whoever carries them out without mistakes can handle the chain rule.
Why this matters for MLA change of variables in a model (feature scaling, switching to logarithms, a different parametrization of the weights) changes the gradient exactly by this rule: the row of derivatives is multiplied by the derivative matrix of the change.
Optimization: what can be minimized
Two caveats from the lecturer. The objective function must be real-valued: only real numbers can be compared by size; vectors and even complex numbers have no usable order. The domain matters now: differential calculus is local, while the question of a minimum depends on where the domain ends.
Fermat’s theorem
Fermat’s theorem (necessary condition)Suppose $f:D\to\R$, $D\subseteq\R^N$, attains its smallest (or largest) value on $D$ at a point $x_0$, the derivative $Df(x_0)$ exists, and $x_0$ is an interior point of $D$. Then $Df(x_0)=0$, that is, all partial derivatives at $x_0$ are zero.
Interior point$x_0$ is an interior point of $D$ if there is $\varepsilon>0$ such that the open ball $B(x_0,\varepsilon)=\{x:\lVert x-x_0\rVert<\varepsilon\}$ lies entirely in $D$.
Every point of the open interval $(0,1)$ is interior; the point $0$ of the segment $[0,1]$ is not: every ball around it sticks out to the left. The lecturer gave a counterexample without the “interior” condition: a linear function on $[0,1]$ (the recording sounds like “twice”, probably $f(x)=2x$). The minimum is at $x=0$, but $f'(0)=2\ne0$ — because $0$ lies on the boundary.
Proof idea. For each direction $u$ the function $g(t)=f(x_0+tu)$ has a minimum at $t=0$, and $0$ is an interior point of its domain. By Fermat’s theorem in one variable $g'(0)=Df(x_0)\,u=0$ for all $u$, hence $Df(x_0)=0$. The full proof is problem m0209.
Necessary does not mean sufficient$f(x)=x^3$ on $[-1,1]$: $f'(0)=0$, but there is neither a minimum nor a maximum at zero, and the minimum is attained at $x=-1$. The condition $Df=0$ only narrows the search: the candidates are points with $Df=0$ inside the domain, plus the boundary separately.
Why this matters for MLThe gradient of the loss is zero at minima, at maxima, and at saddle points. So “gradient descent stopped” does not yet mean “a minimum was found.”
Least squares
Given $A\in M_{D\times N}$, $b\in\R^D$, we look for the minimum of $f(x)=\lVert b-Ax\rVert^2$ over $x\in\R^N$. The domain is all of $\R^N$, so every point is interior. The lecturer’s advice: minimize the squared distance, not the distance — the minimizer is the same, and the function is smooth. From lecture 1 $Df(x)=-2(b-Ax)^tA$; set it to zero, as on the board:
$$-2(b-Ax)^tA=0\ \Rightarrow\ -2(b-Ax)^t(A^t)^t=0\ \Rightarrow\ -2(A^tb-A^tAx)^t=0\ \Rightarrow\ A^tb-A^tAx=0.$$Normal equationsThe minimizer of $\lVert b-Ax\rVert^2$ satisfies the $N\times N$ system $A^tAx=A^tb$.
Example. Approximate the three numbers $1, 2, 6$ by one constant $x$: $A=(1,1,1)^t$, $b=(1,2,6)^t$. Then $A^tA=3$, $A^tb=9$, $x=3$ — the arithmetic mean. Check: the residual $b-Ax=(-2,-1,3)^t$ is orthogonal to the column of $A$; the sum of its coordinates is $0$.
The lecturer listed the questions you must always ask. Does a minimum exist? Here, yes; but there is no maximum: for $A\ne0$ the function goes to infinity. Does the equation have a solution? Is it unique? For least squares a solution always exists, it may be non-unique, and any solution gives the minimum. The lecturer postponed the proof to the linear algebra part.
Why this matters for MLThe rows of $A$ are objects, the columns are features, $b$ holds the targets. The normal equations give the weights of linear regression without gradient descent. If two features are collinear, $A^tA$ is singular, and the solution stops being unique.
Constraints: Lagrange geometry
The problem from the board. A triangle $ABC$ is given. The points $P$ with $\lvert PA\rvert+\lvert PB\rvert=d_1$ form an ellipse with foci $A$, $B$ — this is the constraint curve. Find the minimum of $\lvert PC\rvert$ (the objective function) on this ellipse. If $d_1=\lvert AB\rvert$, the ellipse degenerates into the segment $AB$, and the answer is the distance from $C$ to the segment.
Answer. The minimum is attained at the point $P_0$ where the segment $CP_0$ is orthogonal to the ellipse, that is, to its tangent line.
Reformulation. The level sets of the objective $\{P:\lvert PC\rvert=\text{const}\}$ are circles centered at $C$. A radius is perpendicular to the tangent of the circle, so “$CP_0$ is orthogonal to the ellipse” means: the level curve of the objective through $P_0$ is tangent to the constraint curve.
Why this is necessary. If the level curve crosses the constraint curve instead of touching it, then moving along the constraint one way lowers the objective, and moving the other way raises it. So $P_0$ is neither a minimum nor a maximum. This is the geometric form of the Lagrange multiplier method.
By the reflection property of the ellipse, the tangent makes equal angles with the segments to the foci, so $CP_0\perp$ ellipse $\iff\angle AP_0C=\angle BP_0C$. This gives the Fermat point: the minimum of $\lvert PA\rvert+\lvert PB\rvert+\lvert PC\rvert$ can only be where all three angles at $P$ equal $120°$, unless the minimum is at a vertex of the triangle (at a vertex, $\lvert PA\rvert$ is not differentiable). Again a necessary condition: the existence of the minimum must be known separately.
The Lagrange multiplier theorem
Lagrange’s theorem (necessary condition)Suppose $f$ on the set $\{x\in\R^N: g_1(x)=0,\dots,g_r(x)=0\}$, $r<N$, attains its smallest or largest value at a point $x_0$, the functions are smooth, and the Jacobian matrix of the map $(g_1,\dots,g_r)$ at $x_0$ has full rank $r$. Then there are numbers $\lambda_1,\dots,\lambda_r$ (Lagrange multipliers) such that
$$\nabla f(x_0)=\lambda_1\nabla g_1(x_0)+\dots+\lambda_r\nabla g_r(x_0).$$ The statement is taken from the audio: it is not on the board photos. The condition $r<N$: for $r\ge N$ the constraints usually leave only isolated points. The lecturer left translating the geometric tangency condition into this formula as an exercise — it is item 5 of the homework. The lecturer: “geometry is the angel and algebra is the devil, but you cannot live with an angel forever.”
Counting equations. There are $N+r$ unknowns: the coordinates $x^1,\dots,x^N$ and the multipliers $\lambda_1,\dots,\lambda_r$. There are as many equations: $N$ from the vector equality and $r$ constraints.
Entry, solved. $f(x)=(x^1)^2+2(x^2)^2$, $g(x)=x^1+x^2-3$. The rank of the row $Dg=(1,\ 1)$ is $1$. The condition $\nabla f=\lambda\nabla g$: $2x^1=\lambda$, $4x^2=\lambda$, so $x^1=2x^2$. From the constraint $3x^2=3$, $x^2=1$, $x^1=2$, $f=4+2=6$. Check by substituting $x^1=3-x^2$: $(3-x^2)^2+2(x^2)^2$ has derivative $6x^2-6$, which is zero at $x^2=1$. The minimum exists: along the line $f\to\infty$ in both directions.
Why this matters for MLConstraints are everywhere in ML: probabilities sum to $1$, the norm of the weights is bounded, in support vector machines the margins are at least $1$. Lagrange multipliers are the general way to solve such problems.
Maximum entropy
The lecturer’s example: minimize $f(x)=\sum_{i=1}^{N}x^i\ln x^i$ over $x^i\in[0,1]$ subject to $\sum_ix^i=1$.
The boundary. At $x^i=0$ the logarithm is undefined. By L’Hôpital, $x\ln x=\frac{\ln x}{1/x}$, and $\lim_{x\to0^+}\frac{1/x}{-1/x^2}=\lim_{x\to0^+}(-x)=0$. So one sets $0\ln0=0$, and $f$ is continuous up to the boundary.
The Lagrange condition. $\nabla f=(\ln x^i+1)_i$, $\nabla g=(1,\dots,1)^t$. The equality $\nabla f=\lambda\nabla g$ gives $\ln x^i+1=\lambda$ for every $i$, so all $x^i$ are equal. That is $N$ equations, together with the constraint $N+1$ for $N+1$ unknowns. The answer: $x^i=1/N$.
MeaningThe numbers $x^i$ form a probability distribution, and $H(x)=-\sum_ix^i\ln x^i$ is its entropy. The minimum of $\sum x^i\ln x^i$ is the maximum of entropy, and the candidate is the uniform distribution. That it really is the minimum, the lecturer promised to show later.
Why this matters for MLCross-entropy is the standard loss of a classifier. If a constraint on the mean is added to $\sum p^i=1$, maximum entropy gives $p^i$ proportional to $e^{\lambda k_i}$ — the softmax form (final m0220).
What should stay with you
- The derivative is a linear map; for $f:M_{m\times n}\to\R$ it is written as a matrix $Df(X_0)\in M_{n\times m}$ acting by $U\mapsto\tr(Df(X_0)\,U)$.
- $D(F\circ G)=DF\cdot DG$: a composition of nonlinear maps becomes a product of matrices.
- Restricting to a line or a segment, $g(t)=f(x_0+tu)$, reduces a multivariable question to one variable: $g'(0)=Df(x_0)\,u$.
- $g''$ on a segment is the quadratic form $(b-a)^tH(b-a)$; this gives second-order Taylor.
- Under a change of variables the row of derivatives is multiplied by the derivative matrix of the change; in second derivatives, differentiate both $f_x$ and the coefficients of the change.
- $Df=0$ is only a necessary condition and only at interior points; the boundary is checked separately.
- Minimum of $\lVert b-Ax\rVert^2$: the normal equations $A^tAx=A^tb$.
- With constraints: $\nabla f=\sum\lambda_i\nabla g_i$ under full rank; $N+r$ equations, $N+r$ unknowns.
- Maximum entropy with the single constraint $\sum p^i=1$ is the uniform distribution.