Matrycowa forma propagacji wstecznej z normalizacją partii

12

Normalizacji partii przypisano znaczną poprawę wydajności w głębokich sieciach neuronowych. Wiele materiałów w Internecie pokazuje, jak wdrożyć je na zasadzie aktywacja po aktywacji. Zaimplementowałem już backprop za pomocą algebry macierzy i biorąc pod uwagę, że pracuję w językach wysokiego poziomu (polegając na Rcpp(i ewentualnie GPU) na gęstym mnożeniu macierzy), zgrywanie wszystkiego i uciekanie się do forpętli prawdopodobnie spowolniłoby mój kod zasadniczo, oprócz tego, że jest ogromnym bólem.

Funkcja normalizacji partii to gdzie

b(xp)=γ(xpμxp)σxp1+β
  • pxp jest tym węzłem, zanim zostanie aktywowanyp
  • βγ i są parametrami skalarnymiβ
  • σ x p x pμxp i są średnią i SD . (Zauważ, że zwykle stosowany jest pierwiastek kwadratowy wariancji plus współczynnik krówki - załóżmy, że elementy są niezerowe).σxpxp

W postaci macierzowej normalizacja partii dla całej warstwy to gdzie

b(X)=(γ1p)(XμX)σX1+(β1p)
  • N × pX toN×p
  • 1N jest wektorem kolumnowym jedności
  • β pγ i są teraz wierszami wektorów parametrów normalizacji dla poszczególnych warstwβp
  • σ X N × p NμX i są macierzami , gdzie każda kolumna jest wektorem wektorów średnich i odchyleń standardowychσXN×pN
  • to produkt Kronecker, a to produkt elementowy (Hadamard)

Bardzo prosta jednowarstwowa sieć neuronowa bez normalizacji partii i ciągłym wynikiem jest

y=a(XΓ1)Γ2+ϵ

gdzie

  • Γ1 top1×p2
  • p 2 × 1Γ2 top2×1
  • a(.) to funkcja aktywacji

Jeśli utrata wynosi , wówczas gradienty to RR=N1(yy^)2

RΓ1=2VTϵ^RΓ2=XT(a(XΓ1)2ϵ^Γ2T)

gdzie

  • V=a(XΓ1)
  • ϵ^=yy^

W ramach normalizacji partii siatka staje się lub Nie mam pojęcia, jak obliczyć pochodne produktów Hadamarda i Kroneckera. Literatura na temat produktów Kronecker jest dość tajemnicza. y = a ( ( γ 1 N

y=a(b(XΓ1))Γ2
y=a((γ1N)(XΓ1μXΓ1)σXΓ11+(β1N))Γ2

Czy istnieje praktyczny sposób obliczania , i w ramach matrycy? Proste wyrażenie bez uciekania się do obliczeń węzeł-węzeł?R /β R /Γ 1R/γR/βR/Γ1

Aktualizacja 1:

Odkryłem - w pewnym sensie. Jest to: Niektóre kody R pokazują, że jest to równoważne z zapętleniem. Najpierw skonfiguruj fałszywe dane:R/β

1NT(a(XΓ1)2ϵ^Γ2T)
set.seed(1)
library(dplyr)
library(foreach)

#numbers of obs, variables, and hidden layers
N <- 10
p1 <- 7
p2 <- 4
a <- function (v) {
  v[v < 0] <- 0
  v
}
ap <- function (v) {
  v[v < 0] <- 0
  v[v >= 0] <- 1
  v
}

# parameters
G1 <- matrix(rnorm(p1*p2), nrow = p1)
G2 <- rnorm(p2)
gamma <- 1:p2+1
beta <- (1:p2+1)*-1
# error
u <- rnorm(10)

# matrix batch norm function
b <- function(x, bet = beta, gam = gamma){
  xs <- scale(x)
  gk <- t(matrix(gam)) %x% matrix(rep(1, N))
  bk <- t(matrix(bet)) %x% matrix(rep(1, N))
  gk*xs+bk
}
# activation-wise batch norm function
bi <- function(x, i){
  xs <- scale(x)
  gk <- t(matrix(gamma[i]))
  bk <- t(matrix(beta[i]))
  suppressWarnings(gk*xs[,i]+bk)
}

X <- round(runif(N*p1, -5, 5)) %>% matrix(nrow = N)
# the neural net
y <- a(b(X %*% G1)) %*% G2 + u

Następnie oblicz pochodne:

# drdbeta -- the matrix way
drdb <- matrix(rep(1, N*1), nrow = 1) %*% (-2*u %*% t(G2) * ap(b(X%*%G1)))
drdb
           [,1]      [,2]    [,3]        [,4]
[1,] -0.4460901 0.3899186 1.26758 -0.09589582
# the looping way
foreach(i = 1:4, .combine = c) %do%{
  sum(-2*u*matrix(ap(bi(X[,i, drop = FALSE]%*%G1[i,], i)))*G2[i])
}
[1] -0.44609015  0.38991862  1.26758024 -0.09589582

Pasują do siebie. Ale nadal jestem zdezorientowany, ponieważ tak naprawdę nie wiem, dlaczego to działa. Notatki MatCalc, do których odwołuje się @ Mark L. Stone, mówią, że pochodna powinna byćβ1N

ABA=(InqTmp)(Invec(B)Im)
gdzie indeksy , i , są wymiary i . jest macierzą komutacji, która jest tutaj tylko 1, ponieważ oba wejścia są wektorami. Próbuję tego i otrzymuję wynik, który nie wydaje się pomocny:mnpqABT
# playing with the kroneker derivative rule
A <- t(matrix(beta)) 
B <- matrix(rep(1, N))
diag(rep(1, ncol(A) *ncol(B))) %*% diag(rep(1, ncol(A))) %x% (B) %x% diag(nrow(A))
     [,1] [,2] [,3] [,4]
 [1,]    1    0    0    0
 [2,]    1    0    0    0
 snip
[13,]    0    1    0    0
[14,]    0    1    0    0
snip
[28,]    0    0    1    0
[29,]    0    0    1    0
[snip
[39,]    0    0    0    1
[40,]    0    0    0    1

To nie jest zgodne. Najwyraźniej nie rozumiem tych reguł pochodnych Kroneckera. Pomoc z nimi byłaby świetna. Nadal całkowicie utknąłem w innych pochodnych, dla i - są one trudniejsze, ponieważ nie wchodzą w addytywne, jak .γΓ1β1

Aktualizacja 2

Czytając podręczniki, jestem całkiem pewien, że i będą wymagały użycia operatora. Ale najwyraźniej nie jestem w stanie śledzić pochodnych w stopniu wystarczającym, aby móc je przetłumaczyć na kod. Na przykład, będzie wzięcia pochodnej w odniesieniu do , gdzie (które w tej chwili możemy traktować jako stałą macierz). R /γR/Γ1R/γvec()R/Γ1wXΓ1Γ1w(γ1)σXΓ11

Instynktownie mówię „odpowiedź brzmi ”, ale to oczywiście nie działa, ponieważ nie jest zgodne z .wXwX

Wiem, że

(AB)=AB+AB

i z tego , że

vec(wXΓ1)vec(Γ1)T=vec(XΓ1)Ivec(w)vec(Γ1)T+vec(w)Ivec(XΓ1)vec(Γ1)T
Ale nie jestem pewien, jak to ocenić, a co dopiero kodować.

Aktualizacja 3

Robię postępy tutaj. Obudziłem się wczoraj o 2 nad ranem z tym pomysłem. Matematyka nie jest dobra na sen.

Oto , po cukru notacyjnego:R/Γ1

  • w(γ1)σXΓ11
  • "stub"a(b(XΓ1))2ϵ^Γ2T

Oto, co masz po do końca reguły łańcucha: Zacznij od zrobienia tego w pętli - i subskrybują kolumny, a jest zgodną matrycą tożsamości:

RΓ1=wXΓ1Γ1("stub")
ijI
RΓij=(wiXi)T("stub"j)
RΓij=(IwiXi)T("stub"j)
RΓij=XiTIwi("stub"j)
tl; dr to w zasadzie wstępne pomnożenie kodu pośredniczącego przez czynniki skali wsadowej. Powinno to być równoważne z:
RΓ=XT("stub"w)

I w rzeczywistości jest to:

stub <- (-2*u %*% t(G2) * ap(b(X%*%G1)))
w <- t(matrix(gamma)) %x% matrix(rep(1, N)) * (apply(X%*%G1, 2, sd) %>% t %x% matrix(rep(1, N)))
drdG1 <- t(X) %*% (stub*w)

loop_drdG1 <- drdG1*NA
for (i in 1:7){
  for (j in 1:4){
    loop_drdG1[i,j] <- t(X[,i]) %*% diag(w[,j]) %*% (stub[,j])
  }
}

> loop_drdG1
           [,1]       [,2]       [,3]       [,4]
[1,] -61.531877  122.66157  360.08132 -51.666215
[2,]   7.047767  -14.04947  -41.24316   5.917769
[3,] 124.157678 -247.50384 -726.56422 104.250961
[4,]  44.151682  -88.01478 -258.37333  37.072659
[5,]  22.478082  -44.80924 -131.54056  18.874078
[6,]  22.098857  -44.05327 -129.32135  18.555655
[7,]  79.617345 -158.71430 -465.91653  66.851965
> drdG1
           [,1]       [,2]       [,3]       [,4]
[1,] -61.531877  122.66157  360.08132 -51.666215
[2,]   7.047767  -14.04947  -41.24316   5.917769
[3,] 124.157678 -247.50384 -726.56422 104.250961
[4,]  44.151682  -88.01478 -258.37333  37.072659
[5,]  22.478082  -44.80924 -131.54056  18.874078
[6,]  22.098857  -44.05327 -129.32135  18.555655
[7,]  79.617345 -158.71430 -465.91653  66.851965

Aktualizacja 4

Myślę, że tutaj jest . PierwszyR/γ

  • XΓ~(XΓμXΓ)σXΓ1
  • γ~γ1N

Podobnie jak poprzednio, reguła łańcuchowa prowadzi cię do Pętla daje Co, podobnie jak poprzednio, jest w zasadzie wstępnym pomnożeniem kodu pośredniczącego. Powinien zatem być równoważny z:

Rγ~=γ~XΓ~γ~("stub")
Rγ~i=(XΓ~)iTIγ~i("stub"i)
Rγ~=(XΓ~)T("stub"γ~)

To rodzaj dopasowań:

drdg <- t(scale(X %*% G1)) %*% (stub * t(matrix(gamma)) %x% matrix(rep(1, N)))

loop_drdg <- foreach(i = 1:4, .combine = c) %do% {
  t(scale(X %*% G1)[,i]) %*% (stub[,i, drop = F] * gamma[i])  
}

> drdg
           [,1]      [,2]       [,3]       [,4]
[1,]  0.8580574 -1.125017  -4.876398  0.4611406
[2,] -4.5463304  5.960787  25.837103 -2.4433071
[3,]  2.0706860 -2.714919 -11.767849  1.1128364
[4,] -8.5641868 11.228681  48.670853 -4.6025996
> loop_drdg
[1]   0.8580574   5.9607870 -11.7678486  -4.6025996

Przekątna na pierwszym jest taka sama jak wektor na drugim. Ale tak naprawdę, ponieważ pochodna dotyczy macierzy - aczkolwiek o określonej strukturze, wynik powinien być podobną macierzą o tej samej strukturze. Czy powinienem wziąć przekątną matrycy i po prostu przyjąć, że jest to ? Nie jestem pewny.γ

Wygląda na to, że odpowiedziałem na własne pytanie, ale nie jestem pewien, czy mam rację. W tym momencie zaakceptuję odpowiedź, która rygorystycznie udowodni (lub obali) to, co razem zhackowałem.

while(not_answered){
  print("Bueller?")
  Sys.sleep(1)
}
użytkownik_ogólny
źródło
2
Rozdział 9 sekcja 14 „Matrycowy rachunek różniczkowy z zastosowaniami w statystyce i ekonometrii” autorstwa Magnusa i Neudeckera, wydanie trzecie janmagnus.nl/misc/mdc2007-3rdedition obejmuje różnice w produktach Kronecker i kończy się ćwiczeniem na temat różnicowania produktu Hadamard. „Notes on Matrix Calculus” Paula L. Facklera www4.ncsu.edu/~pfackler/MatCalc.pdf zawiera wiele materiałów na temat różnicowania produktów Kronceker
Mark L. Stone
Dzięki za referencje. Znalazłem już te notatki MatCalc, ale nie obejmują one Hadamarda, a poza tym nigdy nie jestem pewien, czy reguła z rachunku innego niż macierzowy ma zastosowanie, czy nie ma zastosowania do wielkości macierzy. Reguły dotyczące produktów, reguły łańcuchowe itp. Zajmę się książką. Zaakceptowałbym odpowiedź, która wskaże mi wszystkie składniki, których potrzebuję, aby samodzielnie ją naszkicować ...
generic_user
dlaczego to robisz? dlaczego nie skorzystać z framewroks, takich jak Keras / TensorFlow?
Strata
1
Dokładniej, dopasowuję sieci, które wykorzystują znaną strukturę parametryczną - zarówno pod względem reprezentacji danych wejściowych liniowo w parametrach, jak i struktury podłużnej / panelowej. Ustanowione frameworki są tak mocno zoptymalizowane, że przekraczają moje możliwości hakowania / modyfikowania. Plus matematyka jest ogólnie pomocna. Wiele kluczy szyfrowych nie ma pojęcia, co robią. RcppPrzydatna jest również nauka wystarczająca do skutecznego wdrożenia.
generic_user
1
@ MarkL.Stone jest nie tylko teoretycznie solidny, ale praktycznie łatwy! Mniej lub bardziej mechaniczny proces! I% # $!
generic_user

Odpowiedzi:

1

Nie jest to kompletna odpowiedź, ale w celu zademonstrowania tego, co zasugerowałem w moim komentarzu, jeśli gdzie , i jest wektorem jedności, a następnie według reguły łańcuchowej Zwracając uwagę, że and , widzimy, że

b(X)=(XeNμXT)ΓΣX1/2+eNβT
Γ=diag(γ)ΣX1/2=diag(σX11,σX21,)eN
βR=[2ϵ^(Γ2TI)JX(a)(IeN)]T
2ϵ^(Γ2TI)=vec(2ϵ^Γ2T)TJX(a)=diag(vec(a(b(XΓ1))))
βR=(IeNT)vec(a(b(XΓ1))2ϵ^Γ2T)=eNT(a(b(XΓ1))2ϵ^Γ2T)
poprzez tożsamość . Podobnie, gdzie („stub”), a tovec(AXB)=(BTA)vec(X) W='(b(XΓ1))-2
γR=[2ϵ^(Γ2TI)JX(a)(ΣXΓ11/2(XΓ1eNμXΓ1T))K]T=KTvec((XΓ1eNμXΓ1T)TWΣXΓ11/2)=diag((XΓ1eNμXΓ1T)TWΣXΓ11/2)
W=a(b(XΓ1))2ϵ^Γ2TKNp×pmacierz binarna, która wybiera kolumny produktu Kroneckera odpowiadające elementom ukośnym macierzy kwadratowej. Wynika to z faktu, że . W przeciwieństwie do pierwszego gradientu, to wyrażenie nie jest równoważne z wyrażeniem, które wyprowadziłeś. Biorąc pod uwagę, że jest funkcją liniową wrt , nie powinno być współczynnika w gradiencie. Gradient OP, ale powiem, że dla wyprowadzenia ze stałym tworzy „wybuch”, którego autorzy artykułu starają się uniknąć. W praktyce musisz także znaleźć jakobianów z i wrtb γ i γ i Γ 1 w Σ X μ X XdΓij=0bγiγiΓ1wΣXμXX i użyj reguły produktu.
deasmhumnha
źródło