Стохастикалық градиенттік түсу алгоритмі: даму тарихы мен қолданылуы

Кіріспе

Оптимизациялау алгоритмі

Стохастикалық градиент түсіру (көбінесе SGD деп қысқартылады) – бұл жарамды тегіс қасиеттері бар (мысалы, дифференциалданатын немесе субдифференциалданатын) мақсаттық функцияны оңтайландыруға арналған итеративтік әдіс. Оны градиент түсіру оңтайландыруының стохастикалық жуықтауы ретінде қарастыруға болады, себебі ол нақты градиентті (барлық деректер жиынтығынан есептелген) оның бағалауымен (деректердің кездейсоқ таңдалған кіші жиынтығынан есептелген) ауыстырады. Әсіресе жоғары өлшемді оңтайландыру мәселелерінде бұл өте жоғары есептеу жүктемесін азайтады, төмендеу жылдамдығына қарамастан, жылдам итерацияға мүмкіндік береді. Стохастикалық жуықтаудың негізгі идеясы 1950 жылдардағы Роббинс-Монро алгоритміне дейін жетеді. Бүгінде стохастикалық градиент түсіру машиналық оқытудағы маңызды оңтайландыру әдісіне айналды.

Тарих

1951 жылы Герберт Роббинс пен Саттон Монро стохастикалық градиенттік түсіруге дейінгі ең алғашқы стохастикалық жуықтама әдістерін ұсынды. Осы жұмыстың негізінде бір жыл өткен соң Джек Кифер мен Джейкоб Вольфовиц градиенттің шамамен есептеуі ретінде орталық айырмашылықтарды қолдана отырып, стохастикалық градиенттік түсіруге өте жақын оптимизациялық алгоритмді жариялады. Кейін 1950 жылдары Фрэнк Розенблатт SGD-ді өзінің перцептрон моделін оңтайландыру үшін пайдаланып, нейрондық желілерге стохастикалық градиенттік түсірудің алғашқы қолданылуын көрсетті. Кері таралу алғаш рет 1986 жылы сипатталды, онда көп қабатты нейрондық желілердегі параметрлерді тиімді оңтайландыру үшін стохастикалық градиенттік түсіру қолданылды. Содан кейін тағы бір жетістікке қол жеткізілді: шағын топтамалық градиенттік түсіру, онда жеке мысалдардың орнына деректердің шағын топтамалары қолданылады. 1997 жылы мұндай шағын топтамалармен қол жеткізілетін векторлық тиімділік алғаш рет зерттелді, бұл машиналық оқытуда тиімді оңтайландыруға жол ашты. 2023 жылға қарай бұл шағын топтамалық тәсіл нейрондық желілерді оқытудың стандартты тәсілі болып қала береді, стохастикалық градиенттік түсірудің және градиенттік түсірудің артықшылықтарын теңестіреді. 1980 жылдары импульс енгізілді және 1986 жылы SGD оңтайландыру әдістеріне қосылды. Дегенмен, бұл оңтайландыру әдістері тұрақты гиперпараметрлерді, яғни белгілі бір оқыту жылдамдығы мен импульс параметрін болжайды. 2010 жылдары параметрлік оқыту жылдамдығымен SGD-ні қолданудың адаптивті тәсілдері енгізілді, 2011 жылы AdaGrad ("Адаптивті градиент" үшін) және 2012 жылы RMSprop ("Төртінші дәрежелі орташа тарату" үшін). 2014 жылы Adam ("Адаптивті моментті бағалау" үшін) жарияланды, ол RMSprop-тың адаптивті тәсілдерін импульсқа қолданды; содан кейін Adam-ның көптеген жақсартулары мен тармақтары жасалды, мысалы, Adadelta, Adagrad, AdamW және Adamax. Машиналық оқытуда 2023 жылғы оңтайландыру тәсілдері негізінен Adam-нан туындаған оптимизаторлармен доминацияланады. TensorFlow және PyTorch, ең танымал машиналық оқыту кітапханалары, 2023 жылға қарай негізінен Adam-нан туындаған оптимизаторларды, сондай-ақ Adam-ның алдыңғыларын, мысалы, RMSprop және классикалық SGD-ні қамтиды. PyTorch сонымен қатар шектеулі жад BFGS, сызықтық іздеу әдісін ішінара қолдайды, бірақ тек параметрлік топтарсыз бір құрылғыда орнату үшін ғана.

In 1951, Herbert Robbins and Sutton Monro introduced the earliest stochastic approximation methods, preceding stochastic gradient descent. Building on this work one year later, Jack Kiefer and Jacob Wolfowitz published an optimization algorithm very close to stochastic gradient descent, using central differences as an approximation of the gradient. Later in the 1950s, Frank Rosenblatt used SGD to optimize his perceptron model, demonstrating the first applicability of stochastic gradient descent to neural networks. Backpropagation was first described in 1986, with stochastic gradient descent being used to efficiently optimize parameters across neural networks with multiple hidden layers. Soon after, another improvement was developed: mini batch gradient descent, where small batches of data are substituted for single samples. In 1997, the practical performance benefits from vectorization achievable with such small batches were first explored, paving the way for efficient optimization in machine learning. As of 2023, this mini batch approach remains the norm for training neural networks, balancing the benefits of stochastic gradient descent with gradient descent. By the 1980s, momentum had already been introduced, and was added to SGD optimization techniques in 1986. However, these optimization techniques assumed constant hyperparameters, i. e. a fixed learning rate and momentum parameter. In the 2010s, adaptive approaches to applying SGD with a per parameter learning rate were introduced with AdaGrad (for "Adaptive Gradient") in 2011 and RMSprop (for "Root Mean Square Propagation") in 2012. In 2014, Adam (for "Adaptive Moment Estimation") was published, applying the adaptive approaches of RMSprop to momentum; many improvements and branches of Adam were then developed such as Adadelta, Adagrad, AdamW, and Adamax. Within machine learning, approaches to optimization in 2023 are dominated by Adam derived optimizers. TensorFlow and PyTorch, by far the most popular machine learning libraries, as of 2023 largely only include Adam derived optimizers, as well as predecessors to Adam such as RMSprop and classic SGD. PyTorch also partially supports Limited memory BFGS, a line search method, but only for single device setups without parameter groups.

Белгілі қолданулар

Стохастикалық градиент түсіру – машиналық оқытуда кең ауқымды модельдерді оқытуға арналған танымал алгоритм, соның ішінде (сызықтық) қолдау векторлық машиналар, логистикалық регрессия (мысалы, Vowpal Wabbit қараңыз) және графикалық модельдер. Артқа таралу алгоритмімен үйлестірілгенде, бұл жасанды нейрондық желілерді оқытудың де-факто стандартты алгоритмі болып табылады. Оның геофизика саласында, әсіресе толық толқын пішінінің инверсиясы (FWI) қолданбаларында қолданылуы туралы да хабарланған. Стохастикалық градиент түсіру L-BFGS алгоритмімен бәсекелеседі, ол да кеңінен қолданылады. Стохастикалық градиент түсіру кем дегенде 1960 жылдан бері сызықтық регрессия модельдерін оқыту үшін қолданылып келеді, бастапқыда ADALINE деген атпен белгілі болған. Тағы бір стохастикалық градиент түсіру алгоритмі – ең кіші орташа квадраттар (LMS) адаптивті сүзгісі.

Кеңейтулер мен нұсқалар

Негізгі стохастикалық градиент түсіру алгоритміне көптеген жақсартулар ұсынылып, қолданылған. Атап айтқанда, машиналық оқытуда оқу жылдамдығын (қадам өлшемін) таңдау қажеттілігі мәселілі болып саналады. Бұл параметрді тым жоғары деңгейге орнату алгоритмнің тұрақтанбауына алып келуі мүмкін, ал тым төмен деңгейге орнату конвергенцияны баяулатады. Стохастикалық градиент түсірудің түсінік жүзінде қарапайым кеңейтілген түрі оқу жылдамдығын итерация санының ηt төмендеу функциясы етіп белгілейді, осылайша оқу жылдамдығы кестесін құрады. Бұл кесте алғашқы итерацияларда параметрлерде үлкен өзгерістерге, ал кейінгілерінде тек нақты реттеулерге мүмкіндік береді. Мұндай кестелер Маккуиннің k-орталықтар кластерлеуі жөніндегі еңбегінен бері белгілі. Spall СГД-ның бірнеше түрінде қадам өлшемін таңдау бойынша практикалық кеңестер береді.

Орташалау

1980 жылдардың аяғында Рупперт пен Поляк дербес түрде ойлап тапқан орташаланған стохастикалық градиент түсірілімі – уақыт өте келе параметрлік векторларының орташа мәнін сақтайтын қарапайым стохастикалық градиент түсірілімі. Яғни, жаңарту қарапайым стохастикалық градиент түсіріліміне ұқсас, бірақ алгоритм сондай-ақ орташа есептелген параметрлік векторды сақтайды.

Оптимизация аяқталған кезде, осы орташаланған параметрлік вектор w-ның орнына қолданылады.

AdaGrad

AdaGrad (адаптивтік градиент алгоритмі үшін) – 2011 жылы алғаш рет жарияланған, параметрлік оқыту жылдамдығын қолданатын модификацияланған стохастикалық градиент түсініс алгоритмі. Шартты түрде айтқанда, бұл сирек кездесетін параметрлер үшін оқыту жылдамдығын арттырады, ал жиі кездесетін параметрлер үшін төмендетеді. Бұл стратегия деректердің сиректігі жоғары және сирек параметрлер маңыздырақ болған жағдайларда стандартты стохастикалық градиент түсінісімен салыстырғанда конвергенцияның тиімділігін жақсартады. Мұндай қолданыстарға табиғи тілді өңдеу және бейнелерді тану жатады.

Белгіге негізделген стохастикалық градиент түсімі

Белгіге негізделген оңтайландыру бұрынғыда айтылған Rprop-қа дейін бар болғанымен, 2018 жылы зерттеушілер Адам алгоритмін стохастикалық градиенттің мөлшерін ескермей, тек оның таңбасын ғана қарастыра отырып, қарапайымдауға тырысты.

Қайта іздеу желісі

Артқа қарай сызық іздеу – градиенттік түсудің тағы бір түрі. Төмендегі мәліметтердің бәрі аталған сілтемеден алынған. Ол Армижо-Голдштейн шартына негізделген. Екі әдіс те оқыту жылдамдығын әр итерацияда өзгертуге мүмкіндік береді, бірақ өзгерту әдісі әртүрлі. Артқа қарай сызық іздеу Армижо шартын тексеру үшін функцияның мәнін бағалайды, ал принципте оқыту жылдамдығын анықтау алгоритміндегі цикл ұзақ болуы және алдын ала белгілі болмауы мүмкін. Адаптивті SGD оқыту деңгейін анықтау үшін циклді қажет етпейді. Екінші жағынан, адаптивті SGD «түсу қасиетіне» кепілдік бермейді – бұл артқа қарай сызық іздеуге тән, яғни ол барлық n үшін орындалады. Егер шығын функциясының градиенті Lipschitz тұрақтысы L-мен Lipschitz үздік болса және оқыту жылдамдығы 1/L шамасында таңдалса, онда SGD-нің стандартты нұсқасы артқа қарай сызық іздеудің ерекше жағдайы болып табылады.

Екінші реттік әдістер

Стандартты (детерминистік) Ньютон-Рафсон алгоритмінің (екінші реттік) стохастикалық аналогы (егерде "екінші реттік" әдісі) стохастикалық жақындасу орнатуда итерациялық оптимизацияның асимптотикалық оптималды немесе оптималдыққа жақын түрін ұсынады. Эмпирикалық тәуекел функциясының қосылғыштарының Гессиан матрицаларын тікелей өлшеуді пайдаланатын әдісті Берд, Хансен, Ноцедал және Сингер әзірледі. Дегенмен, оңтайландыру үшін қажетті Гессиан матрицаларын тәжірибеде тікелей анықтау мүмкін болмауы мүмкін. Гессианға тікелей ақпарат қажет етпейтін SGD-нің екінші реттік нұсқалары үшін практикалық және теориялық тұрғыдан дұрыс әдістерді Spall және басқалар ұсынады. (Руперт бір мезгілдегі бұзылыстардың орнына шекті айырмашылықтарға негізделген тиімділігі төмен әдісті ұсынады.) Хессиан матрицасын жақындастырудың тағы бір тәсілі – оны Фишер ақпарат матрицасымен алмастыру, ол әдеттегі градиентті табиғи градиентке түрлендіреді. Тікелей Гессиан ақпаратын қажет етпейтін бұл әдістер жоғарыда аталған эмпирикалық тәуекел функциясының қосылғыштарының мәндеріне немесе қосылғыштардың градиенттерінің мәндеріне (яғни SGD кірісіне) негізделген. Атап айтқанда, эмпирикалық тәуекел функциясының қосылғыштарының Гессиан матрицаларын тікелей есептемей, екінші реттік оптималдыққа асимптотикалық түрде қол жеткізуге болады.