Co uzasadnia to obliczenie pochodnej funkcji macierzowej?

W kursie uczenia maszynowego Andrew Nga używa tej formuły:

$\nabla_A tr(ABA^TC) = CAB + C^TAB^T$

i robi szybki dowód, który pokazano poniżej:

$\nabla_A tr(ABA^TC) \\ = \nabla_A tr(f(A)A^TC) \\ = \nabla_{\circ} tr(f(\circ)A^TC) + \nabla_{\circ}tr(f(A)\circ^T C)\\ =(A^TC)^Tf'(\circ) + (\nabla_{\circ^T}tr(f(A)\circ^T C)^T \\ = C^TAB^T + (\nabla_{\circ^T}tr(\circ^T)Cf(A))^T \\ =C^TAB^T + ((Cf(A))^T)^T \\ = C^TAB^T + CAB$

Dowód wydaje się bardzo gęsty bez żadnych komentarzy i mam problem z jego zrozumieniem. Co dokładnie wydarzyło się od drugiej do trzeciej równości?

machine-learning matrix derivative

— MoneyBall
źródło

Musi przyjmować specjalne założenia dotyczące wymiarów , i , ponieważ w przeciwnym razie ta formuła nie ma sensu w ogóle. Na lewej bocznej musi być macierzy z matrycy i matrycę dowolnych nieujemne liczby całkowite . Ale wtedy produkty po prawej stronie nie byłyby zdefiniowane, chyba że .

A

$A$

B

$B$

C

$C$

A

$A$

i \times j

$i\times j$

B

$B$

j \times j

$j\times j$

C

$C$

i \times m

$i\times m$

i, j, m

$i,j,m$

i = m

$i=m$

— whuber

@ whuber Rozumiem. Biorąc pod uwagę założenia, nadal nie rozumiem, jak nastąpiło przejście z drugiej do trzeciej linii, w której wprowadza .

\circ

$\circ$

— MoneyBall

Pomiędzy drugą i trzecią linią pozwala . Między drugą a trzecią linią stosował zasadę produktu. później używa reguły łańcucha, aby pozbyć się .

f (A) = A B

$f(A)=AB$

f ()

$f()$

— Brian Borchers

Istnieje subtelne, ale ciężkie nadużycie zapisu, które powoduje, że wiele kroków jest mylących. Zajmijmy się tym problemem, wracając do definicji mnożenia macierzy, transpozycji, śladów i pochodnych. Dla tych, którzy chcą pominąć wyjaśnienia, wystarczy przejść do ostatniej części „Składanie wszystkiego razem”, aby zobaczyć, jak krótka i prosta może być rygorystyczna demonstracja.

Notacja i pojęcia

Wymiary

Aby wyrażenie miała sens, gdy jest macierzą , musi być macierzą (kwadratową) , a musi być macierzą , skąd iloczynem jest macierz. Aby pobrać ślad (który jest sumą elementów ukośnych, nazwa ), a następnie , czyniąc kwadratową macierzą. $ABA^\prime C$ $A$ $m\times n$ $B$ $n\times n$ $C$ $m\times p$ $m\times p$ $\operatorname{Tr}(X)=\sum_i X_{ii}$ $p=m$ $C$

Pochodne

Oznaczenie „ ” pojawia się w odniesieniu do pochodnej wyrażenia względem . Zwykle, różnicowanie jest to operacja wykonywana w funkcji . Pochodna w punkcie jest przekształcenie liniowe . Po wybraniu zasad dla tych przestrzeni wektorowych transformacja taka może być reprezentowana jako macierz Nie o to chodzi w tym przypadku! $\nabla_A$ $A$ $f:\mathbb{R}^N\to\mathbb{R}^M$ $x\in \mathbb{R}^N$ $Df(x):\mathbb{R}^N\to\mathbb{R}^M$ $M\times N$

Macierze jako wektory

Zamiast tego jest uważany za element : jego współczynniki są rozwijane (zwykle albo rząd po rzędzie lub kolumna po kolumnie) do wektora o długości . Funkcja ma rzeczywiste wartości, skąd . W związku z tym musi być macierzą : to wektor wiersza reprezentujący formę liniową na . Jednak obliczenia w pytaniu wykorzystują inny sposób reprezentowania form liniowych: ich współczynniki są zwijane z powrotem do macierzy . $A$ $\mathbb{R}^{mn}$ $N=mn$ $f(A)=\operatorname{Tr}(ABA^\prime C)$ $M=1$ $Df(x)$ $1\times mn$ $\mathbb{R}^{mn}$ $m\times n$

Ślad jako forma liniowa

Niech będzie stałą macierzy. Następnie, z definicji śladu i mnożenia macierzy, $\omega$ $m\times n$

\begin{aligned} Tr (A ω^{'}) & = \sum_{i = 1}^{m} (A ω^{'})_{i i} = \sum_{i = 1}^{m} (\sum_{j = 1}^{n} A_{i j} (ω^{'})_{j i}) = \sum_{i, j} ω_{i j} A_{i j} \end{aligned}

$\eqalign{ \operatorname{Tr}(A\omega^\prime) &= \sum_{i=1}^m(A\omega^\prime)_{ii} = \sum_{i=1}^m\left(\sum_{j=1}^n A_{ij}(\omega^\prime)_{ji}\right) = \sum_{i,j} \omega_{ij}A_{ij} }$

Wyraża to najbardziej ogólną możliwą kombinację liniową współczynników : jest macierzą o tym samym kształcie co a jej współczynnik w rzędzie i kolumnie jest współczynnikiem w kombinacji liniowej. Ponieważ , role i mogą się zmieniać, dając równoważne wyrażenie $A$ $\omega$ $A$ $i$ $j$ $A_{ij}$ $\omega_{ij}A_{ij}=A_{ij}\omega_{ij}$ $\omega$ $A$

\begin{matrix} (1) & \sum_{i, j} ω_{i j} A_{i j} = Tr (A ω^{'}) = Tr (ω A^{'}) . \end{matrix}

$\sum_{i,j} \omega_{ij}A_{ij} = \operatorname{Tr}(A\omega^\prime) = \operatorname{Tr}(\omega A^\prime).\tag{1}$

Poprzez identyfikację stałej macierzy pomocą jednej z funkcji nazwa lub , możemy reprezentować liniowy formuje się na przestrzeni macierzy jako macierzy. (Nie myl ich z pochodnymi funkcji z do !) $\omega$ $A\to \operatorname{Tr}(A \omega^\prime)$ $A\to \operatorname{Tr}(\omega A^\prime)$ $m\times n$ $m\times n$ $\mathbb{R}^n$ $\mathbb{R}^m$

Obliczanie pochodnej

Definicja

Pochodne wielu funkcji macierzowych spotykanych w statystykach można najłatwiej i rzetelnie obliczyć z definicji: tak naprawdę nie trzeba uciekać się do skomplikowanych reguł różnicowania macierzy. Definicja ta mówi, że jest różniczkowalna dla wtedy i tylko wtedy, gdy istnieje transformacja liniowa taka, że $f$ $x$ $L$

f (x + h) - f (x) = L h + o (| h |)

$f(x+h) - f(x) = Lh + o(|h|)$

na dowolnie małe przemieszczenia . Notacja little-oh oznacza, że błąd popełniony w przybliżeniu różnicy przez jest arbitralnie mniejszy niż rozmiar dla wystarczająco małego . W szczególności zawsze możemy ignorować błędy, które są proporcjonalne do . $h\in \mathbb{R}^N$ $f(x+h)-f(x)$ $Lh$ $h$ $h$ $|h|^2$

Kalkulacja

Zastosujmy definicję do omawianej funkcji. Pomnożenie, rozwinięcie i zignorowanie terminu z iloczynem dwóch , $h$

\begin{matrix} (2) & \begin{aligned} f (A + h) - f (A) & = Tr ((A + h) B (A + h)^{'} C) - Tr (A B A^{'} C) \\ = Tr (h B A^{'} C) + Tr (A B h^{'} C) + o (| h |) . \end{aligned} \end{matrix}

$\eqalign{ f(A+h)-f(A) &= \operatorname{Tr}((A+h)B(A+h)^\prime C) - \operatorname{Tr}(ABA^\prime C) \\ &= \operatorname{Tr}(hBA^\prime C) +\operatorname{Tr}(ABh^\prime C) + o(|h|).\tag{2} }$

Aby zidentyfikować pochodną , musimy wprowadzić ją do postaci . Pierwszy składnik po prawej stronie znajduje się już w tej postaci z . Drugi termin po prawej stronie ma postać nazwa dla . Napiszmy to: $L=Df(A)$ $(1)$ $\omega = BA^\prime C$ $\operatorname{Tr}(Xh^\prime C)$ $X=AB$

\begin{matrix} (3) & Tr (X h^{'} C) = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{m} X_{i j} h_{k j} C_{k i} = \sum_{i, j, k} h_{k j} (C_{k i} X_{i j}) = Tr ((C X) h^{'}) . \end{matrix}

$\operatorname{Tr}(Xh^\prime C) = \sum_{i=1}^m\sum_{j=1}^n\sum_{k=1}^m X_{ij} h_{kj} C_{ki} = \sum_{i,j,k}h_{kj} \left(C_{ki}X_{ij}\right) =\operatorname{Tr}((CX)h^\prime).\tag{3}$

Przywołując , można przepisać $X=AB$ $(2)$

f (A + h) - f (A) = Tr (h B A^{'} C) + Tr (C A B h^{'}) + o (| h |) .

$f(A+h) - f(A) = \operatorname{Tr}(h\, BA^\prime C\,) + \operatorname{Tr}(CAB\, h^\prime\,)+o(|h|).$

W tym sensie możemy uznać pochodną w za ponieważ te macierze grają role we wzorach śledzenia . $f$ $A$

D f (A) = (B A^{'} C)^{'} + C A B = C^{'} A B^{'} + C A B,

$Df(A) = (BA^\prime C)^\prime + CAB = C^\prime A B^\prime + CAB,$

ω

$\omega$

(1)

$(1)$

Kładąc wszystko razem

Oto kompletne rozwiązanie.

Niech będzie macierzą macierzy, an macierzy, a an macierzy. Niech . Niech będzie macierzą macierzy o dowolnie małych współczynnikach. Ponieważ (według tożsamości ) jest różniczkowalna, a jej pochodna jest formą liniową określoną przez macierz $A$ $m\times n$ $B$ $n\times n$ $C$ $m\times m$ $f(A) = \operatorname{Tr}(ABA^\prime C)$ $h$ $m\times n$ $(3)$
$\begin{aligned} f (A + h) - f (A) & = Tr (h B A^{'} C) + Tr (A B h^{'} C) + o (| h |) \\ = Tr (h (C^{'} A B^{'})^{'} + (C A B) h^{'}) + o (| h |), \end{aligned}$ $\eqalign{f(A+h) - f(A) &= \operatorname{Tr}(hBA^\prime C) +\operatorname{Tr}(ABh^\prime C) + o(|h|) \\ &=\operatorname{Tr}(h(C^\prime A B^\prime)^\prime + (CAB)h^\prime) + o(|h|),}$ $f$ $C^{'} A B^{'} + C A B .$ $C^\prime A B^\prime + CAB.$

Ponieważ zajmuje to tylko około połowy pracy i obejmuje tylko najbardziej podstawowe manipulacje macierzami i śladami (mnożenie i transpozycja), należy to uznać za prostszą - i prawdopodobnie bardziej widoczną - demonstrację wyniku. Jeśli naprawdę chcesz zrozumieć poszczególne etapy oryginalnej demonstracji, może okazać się owocne porównanie ich z przedstawionymi tutaj obliczeniami.

— Whuber
źródło

Warto wiedzieć, że ogólnie gdy macierze mają kompatybilne rozmiary. Wiedząc o tym, uczyń (3) trywialnym krokiem.

tr (A B C) = tr (C A B)

$\mbox{tr}(ABC)=\mbox{tr}(CAB)$

— Brian Borchers

@Amoeba Nie wiem, czy starasz się być zabawny, czy nie. Ani pytanie, ani odpowiedź nie mają bezpośredniego związku z częściowymi pochodnymi. Forma wyraźnie jest zdefiniowane w formie liniowej przestrzeni wektor z rzeczywiste macierzy. Gdy ktoś twierdzi, że pochodna funkcji nazwa w punkcie jest równa pewnej macierzy , oznacza to, że jest liniowy formularz podany przez .

(1)

$(1)$

Mat (m, n)

$\operatorname{Mat}(m,n)$

m \times n

$m\times n$

f : Mat (m, n) \to R

$f:\operatorname{Mat}(m,n)\to\mathbb{R}$

A

$A$

ω

$\omega$

D f (A)

$Df(A)$

X :\to Tr (X ω^{'})

$X:\to\operatorname{Tr}(X\omega^{\,\prime})$

— whuber

@Amoeba Dokładnie tak - dokładnie uzasadnia twierdzenia z pierwszego wiersza tej odpowiedzi. Właśnie dlatego napisałem „w tym sensie”, a później w streszczeniu użyłem wyrażenia „zdeterminowany przez” zamiast „równa się”. Nie zaprzeczę, że wyjaśnienie było trudne; Zastanowię się, jak to wyjaśnić i doceniam wszystkie komentarze i sugestie.

— whuber

@ user10324 Większość tego, co publikuję na tej stronie, to moje własne sformułowanie - rzadko korzystam ze źródeł (i dokumentuję je, kiedy to robię). Te posty są destylacją z czytania wielu książek i artykułów. Niektóre z najlepszych książek nie były tymi, które są całkowicie rygorystyczne matematycznie, ale które pięknie wyjaśniły i zilustrowały leżące u ich podstaw idee. Pierwszymi, które przychodzą na myśl - w kolejności złożoności - są Freedman, Pisani i Purves, Statistics (dowolne wydanie); Jack Kiefer, Wprowadzenie do wnioskowania statystycznego ; oraz Steven Shreve, Stochastic Calculus for Finance II .

— whuber

@ whuber W końcu rozumiem, jaka jest liniowa postać śladu. Przepraszam, że ponownie zadałem to samo pytanie w oddzielnych postach, gdy mogłem uważniej przeczytać twoje wyjaśnienie. Mam jeszcze jedno pytanie. Jeśli twoje równanie można zastosować do znalezienia pochodnych dowolnej funkcji macierzowej, czy ma taki sam wymiar jak ? Więc jeśli , to ?

f (x + h) - f (x) = L h + o (| h |)

$f(x+h)−f(x)=Lh+o(|h|)$

h

$h$

x

$x$

x \in R^{m \times n}

$x \in \mathbb{R}^{m \times n}$

h \in R^{m \times n}

$h \in \mathbb{R}^{m \times n}$

— MoneyBall 31.01.17