Algoritmus zpětného šíření chyby

metoda učení umělých neuronových sítí

Algoritmus zpětného šíření chyby nebo anglicky backpropagation je metoda učení umělých neuronových sítí. Používá se u vícevrstvých sítí při učení s učitelem, tedy pokud je na množině případů použitých k učení vždy znám požadovaný výstup sítě. Zpětné šíření chyby je speciální případ obecné metody gradientního sestupu.

DějinyEditovat

Podle různých zdrojů[1][2][3] byly základy metody v kontextu teorie řízení odvozeny z principů dynamického programování; konkrétně se na tom podíleli Henry J. Kelley[4] v roce 1960 a Arthur E. Bryson v roce 1961.[5] Roku 1962 publikoval Stuart Dreyfus jednodušší odvození pomocí řetězového pravidla.[6] Vladimir Vapnik cituje ve své knize o support vector machines článek z roku 1963.[7] V roce 1969 Bryson a Yu-Chi Ho algoritmus popsali jako vícestupňovou optimalizaci dynamických systémů.[8][9]

Konečně v roce 1970 Seppo Linnainmaa publikoval obecnou metodu automatického derivování (AD) diskrétních sítí vnořených diferencovatelných funkcí.[10][11] Jedná se o moderní variantu metody zpětného šíření chyby, která je efektivní i v řídkých sítích.[12][13][2][3]

V roce 1973 Stuart Dreyfus pomocí zpětného šíření chyby upravoval parametry řídicích systémů úměrně jejich chybovým gradientům.[14] Paul Werbos zmínil možnost uplatnění tohoto principu na umělé neuronové sítě roku 1974 [15] a v roce 1982 tak učinil způsobem, který se používá nyní.[16][3] O čtyři roky později David E. Rumelhart, Geoffrey E. Hinton a Ronald J. Williams experimentálně prokázali, že tato metoda může vést k užitečným interním reprezentacím vstupních dat v hlubších vrstvách neuronových sítí, což je základem hlubokého učení.[17] V roce 1993 byl Eric A. Wan první[2] kdo vyhrál pomocí backpropagace mezinárodní soutěž v modelování dat.[18]

AlgoritmusEditovat

Kvalita umělé neuronové sítě je popsána chybovou funkcí, nejčastěji kvadratickou chybou:

  .

Zde je

  chyba,
  počet vzorků předložených síti,
  požadovaný výstup nebo cílová hodnota (target) a
  vypočítaný skutečný výstup sítě.

Faktor   je přidán pouze pro zjednodušení vzorce pro derivaci.

Cílem je nyní minimalizovat tuto chybovou funkci, přičemž gradientní sestup obecně najde pouze lokální minimum. Učení umělé neuronové sítě spočívá ve změně vah vstupů neuronů.

Algoritmus zpětného šíření chyby v každém kroku postupuje v následujících třech fázích:

  • Aplikují se vstupní data a postupně se směrem vpřed napočítá výstup (vstupní signál se sítí šíří směrem dopředu).
  • Výstup ze sítě se porovná s požadovaným výstupem, tj. spočte se chyba, jak byla popsána výše.
  • Počítá se gradient chybové funkce, tj. jak chyba závisí na vahách neuronů. Výpočet postupuje pozadu od výstupní vrstvy až po vstupní vrstvu, přičemž se pro odvození parciálních derivací v následujících vrstvách využívá řetězové pravidlo. Váhy se zároveň mění podle jejich vlivu na chybu. To zaručuje, že po takové změně vah bude chyba na stejném vstupu již menší.

Název algoritmu je podle posledního kroku, kdy se vliv chyby posouvá sítí pozadu (anglicky error back-propagation, zpětné šíření chyby).

ReferenceEditovat

V tomto článku byl použit překlad textu z článku Backpropagation na německé Wikipedii.

  1. Stuart Dreyfus: Artificial Neural Networks, Back Propagation and the Kelley-Bryson Gradient Procedure. In: J. Guidance, Control and Dynamics. 1990.
  2. a b c Jürgen Schmidhuber: Deep learning in neural networks: An overview. In: Neural Networks. 61, 2015, S. 85–117. ArXiv
  3. a b c Jürgen Schmidhuber: Deep Learning. In: Scholarpedia. 10(11), 2015, S. 328–332. Section on Backpropagation
  4. Henry J. Kelley: Gradient theory of optimal flight paths. In: Ars Journal. 30(10), 1960, S. 947–954. (online)
  5. Arthur E. Bryson: A gradient method for optimizing multi-stage allocation processes. In: Proceedings of the Harvard Univ. Symposium on digital computers and their applications. April 1961.
  6. Stuart Dreyfus: The numerical solution of variational problems. In: Journal of Mathematical Analysis and Applications. 5(1), 1962, S. 30–45. (online)
  7. A. E. Bryson, W. F. Denham, S. E. Dreyfus: Optimal programming problems with inequality constraints. I: Necessary conditions for extremal solutions. In: AIAA J. 1, 11, 1963, S. 2544–2550.
  8. Stuart Russell, Peter Norvig. [s.l.]: [s.n.] 
  9. Arthur Earl Bryson, Yu-Chi Ho. [s.l.]: [s.n.] 
  10. Seppo Linnainmaa: The representation of the cumulative rounding error of an algorithm as a Taylor expansion of the local rounding errors. Master’s Thesis (in Finnish), Univ. Helsinki, 1970, S. 6–7.
  11. Seppo Linnainmaa: Taylor expansion of the accumulated rounding error.In: BIT Numerical Mathematics. 16(2), 1976, S. 146–160.
  12. Andreas Griewank: Who Invented the Reverse Mode of Differentiation? Optimization Stories. In: Documenta Matematica. Extra Volume ISMP, 2012, S. 389–400.
  13. Andreas Griewank, Andrea Walther: Principles and Techniques of Algorithmic Differentiation. 2. Auflage. SIAM, 2008.
  14. Stuart Dreyfus: The computational solution of optimal control problems with time lag. In: IEEE Transactions on Automatic Control. 18(4), 1973, S. 383–385.
  15. Paul Werbos: Beyond regression: New tools for prediction and analysis in the behavioral sciences. PhD thesis. Harvard University 1974.
  16. Paul Werbos: Applications of advances in nonlinear sensitivity analysis. In: System modeling and optimization. Springer, Berlin/ Heidelberg 1982, S. 762–770. (online)
  17. David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams: Learning representations by back-propagating errors. In: Nature. Band 323, 1986, S. 533–536.
  18. Eric A. Wan: Time series prediction by using a connectionist network with internal delay lines. In: Santa Fe Institute Studies in the Sciences of Complexity-Proceedings. Vol. 15, Addison-Wesley Publishing Co., 1993, S. 195–195.