Przykład automatycznego różnicowania w trybie odwrotnym

Nie jestem pewien, czy to pytanie należy tutaj, ale jest ściśle związane z metodami gradientu w optymalizacji, co wydaje się być tutaj na temat. W każdym razie możesz swobodnie przeprowadzić migrację, jeśli uważasz, że inna społeczność ma lepsze doświadczenie w tym temacie.

Krótko mówiąc, szukam krok po kroku przykładu automatycznego różnicowania w trybie wstecznym . Nie ma zbyt wiele literatury na ten temat, a istniejąca implementacja (taka jak w TensorFlow ) jest trudna do zrozumienia bez znajomości stojącej za nią teorii. Tak więc byłbym bardzo wdzięczny jeśli ktoś mógłby pokazać szczegółowo, co przekazać w , jak my go przetworzyć , a czego wyjąć obliczeniowej wykresie.

Kilka pytań, z którymi mam najwięcej trudności:

nasiona - dlaczego w ogóle ich potrzebujemy?
zasady odwrotnego różnicowania - wiem, jak wprowadzić różnicowanie do przodu, ale jak cofamy się? Np. W przykładzie z tej sekcji , skąd wiemy, że $\bar{w_2}=\bar{w_3}w_1$ ?
czy pracujemy tylko z symbolami czy przekazujemy rzeczywiste wartości ? Np. W tym samym przykładzie , czy $w_i$ i $\bar{w_i}$ symbole lub wartości?

— przyjaciel
źródło

„Praktyczne uczenie maszynowe za pomocą Scikit-Learn i TensorFlow” Dodatek D zawiera moim zdaniem bardzo dobre wyjaśnienie. Polecam to.

— Agustin Barrachina

Powiedzmy, że mamy wyrażenie $z = x_1x_2 + \sin(x_1)$ i chcemy znaleźć pochodne $\frac{dz}{dx_1}$ i $\frac{dz}{dx_2}$ . AD w trybie do tyłu dzieli to zadanie na 2 części, mianowicie do przodu i do tyłu.

Przekaż do przodu

Po pierwsze, rozkładamy nasze złożone wyrażenie na zbiór pierwotnych, tj. Wyrażeń składających się z co najwyżej jednego wywołania funkcji. Zauważ też, że zmieniam nazwę zmiennych wejściowych i wyjściowych dla zachowania spójności, chociaż nie jest to konieczne:

w_{1} = x_{1}

$w_1 = x_1$

w_{2} = x_{2}

$w_2 = x_2$

w_{3} = w_{1} w_{2}

$w_3 = w_1w_2$

w_{4} = \sin (w_{1})

$w_4 = \sin(w_1)$

w_{5} = w_{3} + w_{4}

$w_5 = w_3 + w_4$

z = w_{5}

$z = w_5$

Zaletą tej reprezentacji jest to, że reguły różnicowania dla każdego oddzielnego wyrażenia są już znane. Na przykład wiemy, że pochodną $\sin$ jest $\cos$ , a więc $\frac{dw_4}{dw_1} = \cos(w_1)$ . Wykorzystamy ten fakt w przekazaniu wstecznym poniżej.

Zasadniczo przekazanie dalej polega na ocenie każdego z tych wyrażeń i zapisaniu wyników. Powiedzmy, że nasze dane wejściowe to: $x_1 = 2$ i $x_2 = 3$ . Następnie mamy:

w_{1} = x_{1} = 2

$w_1 = x_1 = 2$

w_{2} = x_{2} = 3

$w_2 = x_2 = 3$

w_{3} = w_{1} w_{2} = 6

$w_3 = w_1w_2 = 6$

w_{4} = \sin (w_{1}) = 0.9

$w_4 = \sin(w_1) ~= 0.9$

w_{5} = w_{3} + w_{4} = 6.9

$w_5 = w_3 + w_4 = 6.9$

z = w_{5} = 6.9

$z = w_5 = 6.9$

Przełęcz wsteczny

To właśnie tam zaczyna się magia i zaczyna się ona od reguły łańcucha . W swojej podstawowej formie, reguła łańcuch stwierdza, że jeśli masz zmienną $t(u(v))$ , który zależy od $u$ , który z kolei zależy od $v$ , a następnie:

\frac{d t}{d v} = \frac{d t}{d u} \frac{d u}{d v}

$\frac{dt}{dv} = \frac{dt}{du}\frac{du}{dv}$

lub, jeżeli $t$ zależy od $v$ przez kilka ścieżek / zmiennych $u_i$ , np .:

u_{1} = f (v)

$u_1 = f(v)$

u_{2} = g (v)

$u_2 = g(v)$

t = h (u_{1}, u_{2})

$t = h(u_1, u_2)$

następnie (patrz dowód tutaj ):

\frac{d t}{d v} = \sum_{i} \frac{d t}{d u_{i}} \frac{d u_{i}}{d v}

$\frac{dt}{dv} = \sum_i \frac{dt}{du_i}\frac{du_i}{dv}$

Jeśli chodzi o graf wyrażeń, jeśli mamy końcowy węzeł $z$ i węzły wejściowe $w_i$ , a ścieżka od $z$ do $w_i$ przechodzi przez węzły pośrednie $w_p$ (tj. $z = g(w_p)$ gdzie $w_p = f(w_i)$ ), możemy znaleźć pochodną $\frac{dz}{dw_i}$ as

\frac{d z}{d w_{i}} = \sum_{p \in p a r e n t s (i)} \frac{d z}{d w_{p}} \frac{d w_{p}}{d w_{i}}

$\frac{dz}{dw_i} = \sum_{p \in parents(i)} \frac{dz}{dw_p} \frac{dw_p}{dw_i}$

Innymi słowy, aby obliczyć pochodną zmiennej wyjściowej $z$ wrt dowolnej zmiennej pośredniej lub wejściowej $w_i$ , musimy jedynie znać pochodne jej rodziców i wzór do obliczenia pochodnej pierwotnego wyrażenia $w_p = f(w_i)$ .

Przebieg wsteczny rozpoczyna się na końcu (tj. $\frac{dz}{dz}$ ) i propaguje wstecz do wszystkich zależności. Oto mamy (wyrażenie na „seed”):

\frac{d z}{d z} = 1

$\frac{dz}{dz} = 1$

Można to odczytać jako „zmiana w $z$ powoduje dokładnie taką samą zmianę w $z$ ”, co jest dość oczywiste.

Następnie wiemy, że $z = w_5$ i tak:

\frac{d z}{d w_{5}} = 1

$\frac{dz}{dw_5} = 1$

$w_5$ liniowo zależy od $w_3$ i $w_4$ , więc $\frac{dw_5}{dw_3} = 1$ i $\frac{dw_5}{dw_4} = 1$ . Stosując regułę łańcucha, znajdujemy:

\frac{d z}{d w_{3}} = \frac{d z}{d w_{5}} \frac{d w_{5}}{d w_{3}} = 1 \times 1 = 1

$\frac{dz}{dw_3} = \frac{dz}{dw_5} \frac{dw_5}{dw_3} = 1 \times 1 = 1$

\frac{d z}{d w_{4}} = \frac{d z}{d w_{5}} \frac{d w_{5}}{d w_{4}} = 1 \times 1 = 1

$\frac{dz}{dw_4} = \frac{dz}{dw_5} \frac{dw_5}{dw_4} = 1 \times 1 = 1$

Z definicji $w_3 = w_1w_2$ i reguł pochodnych cząstkowych wynika, że $\frac{dw_3}{dw_2} = w_1$ . A zatem:

\frac{d z}{d w_{2}} = \frac{d z}{d w_{3}} \frac{d w_{3}}{d w_{2}} = 1 \times w_{1} = w_{1}

$\frac{dz}{dw_2} = \frac{dz}{dw_3} \frac{dw_3}{dw_2} = 1 \times w_1 = w_1$

Co, jak już wiemy z przekazania, to:

\frac{d z}{d w_{2}} = w_{1} = 2

$\frac{dz}{dw_2} = w_1 = 2$

Wreszcie, $w_1$ przyczynia się do $z$ poprzez $w_3$ i $w_4$ . Po raz kolejny z zasad pochodnych cząstkowych wiemy, że $\frac{dw_3}{dw_1} = w_2$ i $\frac{dw_4}{dw_1} = \cos(w_1)$ . A zatem:

\frac{d z}{d w_{1}} = \frac{d z}{d w_{3}} \frac{d w_{3}}{d w_{1}} + \frac{d z}{d w_{4}} \frac{d w_{4}}{d w_{1}} = w_{2} + \cos (w_{1})

$\frac{dz}{dw_1} = \frac{dz}{dw_3} \frac{dw_3}{dw_1} + \frac{dz}{dw_4} \frac{dw_4}{dw_1} = w_2 + \cos(w_1)$

I znowu, biorąc pod uwagę znane dane wejściowe, możemy to obliczyć:

\frac{d z}{d w_{1}} = w_{2} + \cos (w_{1}) = 3 + \cos (2) = 2.58

$\frac{dz}{dw_1} = w_2 + \cos(w_1) = 3 + \cos(2) ~= 2.58$

Since $w_1$ and $w_2$ are just aliases for $x_1$ and $x_2$ , we get our answer:

\frac{d z}{d x_{1}} = 2.58

$\frac{dz}{dx_1} = 2.58$

\frac{d z}{d x_{2}} = 2

$\frac{dz}{dx_2} = 2$

And that's it!

This description concerns only scalar inputs, i.e. numbers, but in fact it can also be applied to multidimensional arrays such as vectors and matrices. Two things that one should keep in mind when differentiating expressions with such objects:

Derivatives may have much higher dimensionality than inputs or output, e.g. derivative of vector w.r.t. vector is a matrix and derivative of matrix w.r.t. matrix is a 4-dimensional array (sometimes referred to as a tensor). In many cases such derivatives are very sparse.
Each component in output array is an independent function of 1 or more components of input array(s). E.g. if $y = f(x)$ and both $x$ and $y$ are vectors, $y_i$ never depends on $y_j$ , but only on subset of $x_k$ . In particular, this means that finding derivative $\frac{dy_i}{dx_j}$ boils down to tracking how $y_i$ depends on $x_j$ .

The power of automatic differentiation is that it can deal with complicated structures from programming languages like conditions and loops. However, if all you need is algebraic expressions and you have good enough framework to work with symbolic representations, it's possible to construct fully symbolic expressions. In fact, in this example we could produce expression $\frac{dz}{dw_1} = w_2 + \cos(w_1) = x_2 + \cos(x_1)$ and calculate this derivative for whatever inputs we want.

— ffriend
źródło

Very useful question/answer. Thanks. Just a litte criticism: you seem to move on a tree structure without explaining (that's when you start talking about parents, etc..)

— MadHatter

Also it won't hurt clarifying why we need seeds.

— MadHatter

@MadHatter thanks for the comment. I tried to rephrase a couple of paragraphs (these that refer to parents) to emphasize a graph structure. I also added "seed" to the text, although this name itself may be misleading in my opinion: in AD seed is always a fixed expression -

\frac{d z}{d z} = 1

$\frac{dz}{dz} = 1$ , not something you can choose or generate.

— ffriend

Thanks! I noticed when you have to set more than one "seed", generally one chooses 1 and 0. I'd like to know why. I mean, one takes the "quotient" of a differential w.r.t. itself, so "1" is at least intuitively justified.. But what about 0? And what if one has to pick more than 2 seeds?

— MadHatter

As far as I understand, more than one seed is used only in forward-mode AD. In this case you set the seed to 1 for an input variable you want to differentiate with respect to and set the seed to 0 for all the other input variables so that they don't contribute to the output value. In reverse-mode you set the seed to an output variable, and you normally have only one output variable. I guess, you can construct reverse-mode AD pipeline with several output variables and set all of them but one to 0 to get the same effect as in forward mode, but I have never investigated this option.

— ffriend