Математикалық оптимизацияда кері іздеу әдісі

Кіріспе

Математикалық оңтайландыру әдісі

(Шектеусіз) математикалық оңтайландыруда, кері іздеу – берілген іздеу бағыты бойынша қозғалу мөлшерін анықтауға арналған жол іздеу әдісі. Оны қолдану үшін мақсатты функция дифференциалдануы және оның градиенті белгілі болуы керек. Бұл әдіс жол іздеу бағыты бойынша қозғалыс үшін қадам өлшемін салыстырмалы түрде үлкен мәннен бастауды және қадам өлшемін қайта-қайта кішірейте беруді (яғни, «керіге қарай жылжуды») қамтиды, осылайша қадам өлшемі мен мақсатты функцияның жергілікті градиентіне сүйене отырып, күтілетін төмендеуге сай келетін мақсатты функцияның төмендеуі байқалады. Көп қолданылатын тоқтату шарты – Армижо-Голдштейн шарты. Кері іздеу әдетте градиенттік төмен түсу (GD) үшін қолданылады, бірақ оны басқа жағдайларда да қолдануға болады. Мысалы, Гессиан матрицасы оң анықталған болса, оны Ньютон әдісімен де қолдануға болады.

Оқу деңгейінің төменгі шегі

Бұл f функциясы, нүкте және түсу бағытына байланысты оң санды табудың жүйелі жолы бар ма, сонда барлық оқу жылдамдықтары Армихо шартын қанағаттандырады деген сұраққа жауап береді. Егер , онда біз шамамен таңдауымыз мүмкін, мұнда – нүкте маңындағы градиент үшін жергілікті Липшиц тұрақтысы (Липшиц үздіксіздігін қараңыз). Егер функция болса, онда нүктедегі функцияның Гессиан матрицасына жақын болады. Толықрақ мәлімет алу үшін қараңыз.

Оқу деңгейінің жоғарғы шегі

Бірдей жағдайда, қызықты сұрақ Армихо шартында (яғни, «Функцияны практикада кері іздеуді пайдалану арқылы азайту» бөлімінде анықталғандай, шектеу жоқ кезде) қандай үлкен оқыту жылдамдықтарын таңдауға болады, себебі үлкен оқыту жылдамдықтары шекті нүктеге жақын болғанда (егер бар болса) конвергенцияны жылдамдатуға мүмкіндік береді. Мысалы, Вулф шарттарында бұл туралы еске салынбаған, бірақ қисықтық шарты деп аталатын басқа шарт енгізілген. Егер құрастырылған тізбек дегенерацияланбаған сындық нүктеге жақын түсуі керек болса, оқу жылдамдықтарының жоғарғы шегі бар екені көрсетілген, қараңыз: Оқу жылдамдықтары жоғарыдан шамамен шектелуі керек. Мұнда H – функцияның шекті нүктедегі Гессиан, оның керісі және сызықтық оператордың нормасы. Осылайша, бұл нәтиже мысалы, Морзе функциялары үшін кері іздеуді пайдаланғанда қолданылады. 1-өлшемде бұл сан екенін ескеріңіз, сондықтан бұл жоғарғы шек «Оқу жылдамдығы үшін төменгі шек» бөліміндегі төменгі шекпен бірдей. Екінші жағынан, егер шекті нүкте дегенеративті болса, онда оқыту жылдамдықтары шексіз болуы мүмкін. Мысалы, кері іздеудің шексіз кері іздеу градиентінің түсуі деп аталатын модификациясы (қараңыз) оқу жылдамдығын жартысына дейін азайтуға мүмкіндік береді, мұндағы – тұрақты. Қарапайым функциялармен жасалған тәжірибелер «Тәжірибеде кері іздеуді пайдалану арқылы функцияны азайту» бөлімінде сипатталған негізгі нұсқаға қарағанда шексіз кері іздеу градиентінің төмендеуінің әлдеқайда жылдам конвергенциясын көрсетеді.

Уақыт тиімділігі

Армижо шартының қанағаттандырылуы қымбат болғандықтан, артқа қарай іздеуді пайдалануға қарсы аргумент бар, әсіресе үлкен масштабты оңтайландыруда. Онымен айналып өтудің бір жолы бар (екі жолды артқа қарай іздеу деп аталады), жақсы теориялық кепілдіктері бар және терең нейрондық желілерде жақсы нәтижелермен сынақтан өткен, қараңыз. (Онда Армижо шартының жақсы/тұрақты іске асырылымдарын және оның Momentum және NAG сияқты танымал алгоритмдермен үйлесімділігін, Cifar10 және Cifar100 сияқты деректер жиынтықтарында табуға болады.) Егер тізбек конвергенцияға жақын болса (итеративті оңтайландыру әдісін қолданғанда тілек етілгендей), оқу жылдамдықтарының тізбегі n жеткілікті үлкен болғанда аз өзгеруі керек. Сондықтан, егер іздеу кезінде әрқашан бастаса, тізбек алыс болса, көп уақытты жоғалтады. Оның орнына, бастап іздеу керек. Екінші байқау – мүмкін, үлкен болса, оқу жылдамдығын арттыруға рұқсат ету керек (алгоритм бөліміндегідей тек азайту емес). Екі жолды артқа қарай іздеу алгоритмі: n қадамында:

орнатыңыз және итерация санағын (Армижо шарты орындалса, оқу жылдамдығын арттырыңыз). Егер болса, онда бұл шарт және шарт орындалғанда, j-ді қайта-қайта орнатып, арттырыңыз. (Армижо шарты орындалмаса, оқу жылдамдығын азайтыңыз). Керісінше, егер болса, онда шарт орындалғанға дейін қайта-қайта арттырып, орнатыңыз. Оқу жылдамдығы үшін қайтарыңыз. (Жоғарыда аталған мақалада терең нейрондық желілерде бұрын сынақтан өтпеген 1), 3) және 4) алгоритмінің сипаттамасын табуға болады). Екі жолды артқа қарай іздеу және негізгі стандартты градиенттік төмендеу алгоритмі арасындағы гибридті қоспа арқылы уақытты үнемдеуге болады. Бұл процедураның да жақсы теориялық кепілдігі және жақсы сынақ нәтижелері бар. Шамамен айтқанда, екі жолды артқа қарай іздеуді бірнеше рет орындап, содан кейін алынған оқу жылдамдығын функция мәні өспесе өзгеріссіз пайдаланамыз. Мұны дәл осылай істеу керек. Алдын ала санды таңдап, итерация санағын j=0 деп орнатыңыз. қадамдарында екі жолды артқа қарай іздеуді қолданыңыз. Әр қадамда k жиынында: Егер болса, онда таңдаңыз және (Осы жағдайда оқу жылдамдығын өзгеріссіз пайдаланыңыз). Әйтпесе, егер болса, екі жолды артқа қарай іздеуді қолданыңыз. k-ны 1-ге арттырып, қайталаңыз. j-ді 1-ге арттырыңыз.

Теориялық кепілдік (дегенмен төмен түсетінде)

Вольфтың шартымен салыстырғанда Армихо шарты теориялық тұрғыдан жақсырақ. Шындығында, бүгінгі күнге дейін кері іздеу және оның модификациялары барлық сандық оңтайландыру алгоритмдерінің ішінде теориялық тұрғыдан ең сенімді әдістер болып табылады. Критикалық нүктелер – мақсатты функцияның градиенті 0 болатын нүктелер. Жергілікті минимумдар – бұл сынды нүктелер, бірақ барлық сынды нүктелер жергілікті минимумдар емес. Мысалы, ат құйрығын қарастырайық. Седлолық нүктелер – функцияның кем дегенде бір бағытта (жергілікті) максимумы болатын сынды нүктелер. Сондықтан бұл нүктелер жергілікті минимумдардан өте алыс. Мысалы, егер функцияның кем дегенде бір седлолық нүктесі болса, онда ол дөңес бола алмайды. Седлолық нүктелердің оңтайландыру алгоритмдеріне қатысы бар: үлкен масштабтағы (яғни жоғары өлшемді) оңтайландыруда минимумдардан гөрі көбірек седлолық нүктелер кездеседі. Сондықтан жақсы оңтайландыру алгоритмі седлолық нүктелерден аулақ болуы керек. Тераң оқытуда да седлолық нүктелер жиі кездеседі, қараңыз. Критикалық нүктелерге жуықтасу үшін: Мысалы, егер шығын функциясы нақты аналитикалық функция болса, онда жуықтасу кепілдігі көрсетілген. Негізгі идея – нақты аналитикалық функцияға тән Лояшевич теңсіздігін пайдалану. Лояшевич теңсіздігін қанағаттандыратын тегіс емес функциялар үшін жоғарыдағы жуықтасу кепілі кеңейтіледі, қараңыз. Артқа қарай іздеу арқылы құрылған әрбір тізбектегі кластерлік нүкте (яғни, егер кіші тізбек конвергенцияланса, онда оның лимиті) – сынды нүкте болып табылады. Ең көп дегенде саналатын сынды нүктелер саны бар функция (мысалы, Морзе функциясы) және тығыз субдеңгейлерге ие, сондай-ақ Липшиц үздіксіз градиенті бар және стандартты GD оқу жылдамдығымен <1/L қолданылса («Стохастикалық градиент түсуі» бөлімін қараңыз), онда жуықтасу кепілдігі бар, мысалы, қараңыз. Мұндағы тығыз субдеңгейлер туралы болжам Евклид кеңістігінің тығыз жиынтықтарымен жұмыс істеуді қамтамасыз ету үшін жасалған. Жалпы жағдайда, тек саналатын сынды нүктелер саны бар деп есептегенде, жуықтасу кепілдігі бар, қараңыз. Сол сілтемеде кері іздеу сызығының басқа модификациялары үшін де (мысалы, «Оқу жылдамдықтары үшін жоғарғы шекте» бөлімінде айтылған шексіз кері іздеу градиентінің төмендеуі) ұқсас жуықтасу кепілдігі бар. Тіпті функцияның санауға болатын емес сынды нүктелер саны болса да, жуықтасу мінез-құлқы туралы кейбір маңызды фактілерді шығаруға болады. Стохастикалық жағдайда, градиент Липшиц үздіксіз деп есептегенде және оқу жылдамдығының азайту схемасының (оқу жылдамдықтарының қосындысы шексіз және оқу жылдамдықтарының квадраттарының қосындысы шекті болуын талап ететін) шектеулі нұсқасын қолданғанда (қараңыз «Стохастикалық градиент түсуі» бөлімін) және функция қатаң дөңес болса, онда жуықтасу белгілі нәтижеде орнатылады. Осы нәтижелердің ешқайсысы (конвекс емес функциялар үшін) осы уақытқа дейін басқа оңтайландыру алгоритмі үшін дәлелденген жоқ. Седлолық нүктелерден аулақ болу үшін: Мысалы, егер шығын функциясының градиенті Липшиц үздіксіз болса және стандартты GD оқу жылдамдығы <1/L таңдалса, онда бастапқы нүкте кездейсоқ таңдалғанда (дәлірек айтқанда, Лебегтің нөлдік өлшемі жиынтығынан тыс), құрылған тізбек дегенерацияланбаған седлолық нүктеге (яғни, седлолық нүктеге) конвергенцияланбайды (дегенерацияланған седлолық нүктеге) конвергенцияланбайды. Градиент Липшиц үздіксіз және оқу жылдамдығының азайту схемасы қолданылса («Стохастикалық градиент түсуі» бөлімін қараңыз), онда седлолық нүктелерден аулақ болу орнатылады.

Compared with Wolfe's conditions, which is more complicated, Armijo's condition has a better theoretical guarantee. Indeed, so far backtracking line search and its modifications are the most theoretically guaranteed methods among all numerical optimization algorithms concerning convergence to critical points and avoidance of saddle points, see below. Critical points are points where the gradient of the objective function is 0. Local minima are critical points, but there are critical points which are not local minima. An example is saddle points. Saddle points are critical points, at which there are at least one direction where the function is (local) maximum. Therefore, these points are far from being local minima. For example, if a function has at least one saddle point, then it cannot be convex. The relevance of saddle points to optimisation algorithms is that in large scale (i. e. high dimensional) optimisation, one likely sees more saddle points than minima, see Hence, a good optimisation algorithm should be able to avoid saddle points. In the setting of deep learning, saddle points are also prevalent, see Thus, to apply in deep learning, one needs results for non convex functions. For convergence to critical points: For example, if the cost function is a real analytic function, then it is shown in that convergence is guaranteed. The main idea is to use Łojasiewicz inequality which is enjoyed by a real analytic function. For non smooth functions satisfying Łojasiewicz inequality, the above convergence guarantee is extended, see In , there is a proof that for every sequence constructed by backtracking line search, a cluster point (i. e. the limit of one subsequence, if the subsequence converges) is a critical point. For the case of a function with at most countably many critical points (such as a Morse function) and compact sublevels, as well as with Lipschitz continuous gradient where one uses standard GD with learning rate <1/L (see the section "Stochastic gradient descent"), then convergence is guaranteed, see for example Chapter 12 in Here the assumption about compact sublevels is to make sure that one deals with compact sets of the Euclidean space only. In the general case, where is only assumed to be and have at most countably many critical points, convergence is guaranteed, see In the same reference, similarly convergence is guaranteed for other modifications of Backtracking line search (such as Unbounded backtracking gradient descent mentioned in the section "Upper bound for learning rates"), and even if the function has uncountably many critical points still one can deduce some non trivial facts about convergence behaviour. In the stochastic setting, under the same assumption that the gradient is Lipschitz continuous and one uses a more restrictive version (requiring in addition that the sum of learning rates is infinite and the sum of squares of learning rates is finite) of diminishing learning rate scheme (see section "Stochastic gradient descent") and moreover the function is strictly convex, then the convergence is established in the well known result , see for generalisations to less restrictive versions of a diminishing learning rate scheme. None of these results (for non convex functions) have been proven for any other optimization algorithm so far. For avoidance of saddle points: For example, if the gradient of the cost function is Lipschitz continuous and one chooses standard GD with learning rate <1/L, then with a random choice of initial point (more precisely, outside a set of Lebesgue measure zero), the sequence constructed will not converge to a non degenerate saddle point (proven in ), and more generally it is also true that the sequence constructed will not converge to a degenerate saddle point (proven in ). Under the same assumption that the gradient is Lipschitz continuous and one uses a diminishing learning rate scheme (see the section "Stochastic gradient descent"), then avoidance of saddle points is established in .

Арнайы жағдай: (стандартты) стохастикалық градиент түсімі (SGD)

Егер шығындар функциясының градиенті Липшиц тұрақтысы L болатын Липшиц үздіксіз болса, онда оқыту жылдамдығын тұрақты және өлшемі таңдау , градиент түсу үшін кері іздеудің ерекше жағдайы болып табылады. Бұл кем дегенде осы схемада қолданылған, бірақ L үшін жақсы бағалау қажет, әйтпесе егер оқыту жылдамдығы 1/L-ге қатысты тым жоғары болса, схеманың конвергенция кепілі болмайды. Егер шығындар функциясы f(t)=|t| функциясының тегістеуі болса, онда ненің дұрыс емес екенін көруге болады. Алайда, мұндай жақсы бағалау үлкен өлшемдерде қиын және еңбекті талап етеді. Сонымен қатар, егер функцияның градиенті жаһандық Липшиц үздіксіз болмаса, онда бұл схеманың конвергенция кепілі болмайды. Мысалы, бұл , шығын функциясы үшін және кез келген тұрақты оқыту жылдамдығы үшін таңдалған жаттығуға ұқсас, кездейсоқ бастапқы нүктесі бар реттілік осы ерекше схемамен құрылғанда жаһандық минимум 0-ға жиналмайды. Егер оқыту жылдамдығы 1/L-мен шектелуі керек деген шартқа мән бермесе, онда бұл ерекше схема әлдеқайда ертерек, кем дегенде 1847 жылдан бері Коши қолданған, оны стандартты GD деп атауға болады (мұндағы SGD, яғни стохастикалық градиентпен шатастыруға болмайды). Стохастикалық жағдайда (мысалы, терең оқытудағы шағын топтамалық жағдайда) стандартты GD стохастикалық градиент түсуі немесе SGD деп аталады. Шығын функциясының жаһандық үздіксіз градиенті болса да, терең оқытудағы шығын функциялары үшін Липшиц тұрақтысының жақсы бағалауы терең нейрондық желілердің өте жоғары өлшемдерін ескере отырып, мүмкін емес немесе қажетсіз болуы мүмкін. Сондықтан, стандартты GD немесе SGD қолдану кезінде оқыту жылдамдығын нақты реттеу әдісі бар. Бір жолы – жақсы нәтиже беруі мүмкін деген үмітпен, желілік іздеуден көптеген оқыту жылдамдықтарын таңдау. (Егер жоғалту функциясының Липшиц үздіксіз градиенті болмаса, онда жоғарыдағы мысалдан торды іздеудің көмектеспейтінін көреміз.) Тағы бір тәсіл – адаптивті стандартты GD немесе SGD, олардың кейбір өкілдері Adam, Adadelta, RMSProp және т.б., Стохастикалық градиент түсуі туралы мақаланы қараңыз. Адаптивті стандартты GD немесе SGD-де оқыту жылдамдықтары әрбір итерациялық n қадамда өзгеруге рұқсат етіледі, бірақ градиент түсу үшін кері іздеу сызығынан өзгеше. Армихо шарты орындалғанша кері іздеуді пайдалану қымбатқа түседі, өйткені адаптивті стандартты GD немесе SGD үшін бұранда іздеу қажет емес. Бұл адаптивті стандартты GD немесе SGD-нің көпшілігі барлық n үшін төмендеу қасиетіне ие емес, кері іздеу сызығы градиент түсуін іздейді. Бұл қасиетке ие бірнеше ғана, және олар жақсы теориялық қасиеттерге ие, бірақ олар Армихо шартының немесе жалпы Армихо шартының ерекше жағдайлары болып табылады. Біріншісі, егер L үшін жақсы бағалау мүмкін болса, үйрену жылдамдығын тұрақты <1/L деп таңдау, жоғарыда айтылғандай. Екіншісі – бұл төмендеу үйрену жылдамдығы, белгілі қағазда қолданылады , егер функцияның жаһандық Липшиц үздіксіз градиенті болса (бірақ Липшиц тұрақты белгісіз болуы мүмкін) және үйрену жылдамдықтары 0-ға жақындаса.

While it is trivial to mention, if the gradient of a cost function is Lipschitz continuous, with Lipschitz constant L, then with choosing learning rate to be constant and of the size , one has a special case of backtracking line search (for gradient descent). This has been used at least in This scheme however requires that one needs to have a good estimate for L, otherwise if learning rate is too big (relative to 1/L) then the scheme has no convergence guarantee. One can see what will go wrong if the cost function is a smoothing (near the point 0) of the function f(t)=|t|. Such a good estimate is, however, difficult and laborious in large dimensions. Also, if the gradient of the function is not globally Lipschitz continuous, then this scheme has no convergence guarantee. For example, this is similar to an exercise in , for the cost function and for whatever constant learning rate one chooses, with a random initial point the sequence constructed by this special scheme does not converge to the global minimum 0. If one does not care about the condition that learning rate must be bounded by 1/L, then this special scheme has been used much older, at least since 1847 by Cauchy, which can be called standard GD (not to be confused with stochastic gradient descent, which is abbreviated herein as SGD). In the stochastic setting (such as in the mini batch setting in deep learning), standard GD is called stochastic gradient descent, or SGD. Even if the cost function has globally continuous gradient, good estimate of the Lipschitz constant for the cost functions in deep learning may not be feasible or desirable, given the very high dimensions of deep neural networks. Hence, there is a technique of fine tuning of learning rates in applying standard GD or SGD. One way is to choose many learning rates from a grid search, with the hope that some of the learning rates can give good results. (However, if the loss function does not have global Lipschitz continuous gradient, then the example with above shows that grid search cannot help.) Another way is the so called adaptive standard GD or SGD, some representatives are Adam, Adadelta, RMSProp and so on, see the article on Stochastic gradient descent. In adaptive standard GD or SGD, learning rates are allowed to vary at each iterate step n, but in a different manner from Backtracking line search for gradient descent. Apparently, it would be more expensive to use Backtracking line search for gradient descent, since one needs to do a loop search until Armijo's condition is satisfied, while for adaptive standard GD or SGD no loop search is needed. Most of these adaptive standard GD or SGD do not have the descent property , for all n, as Backtracking line search for gradient descent. Only a few has this property, and which have good theoretical properties, but they turn out to be special cases of Backtracking line search or more generally Armijo's condition The first one is when one chooses learning rate to be a constant <1/L, as mentioned above, if one can have a good estimate of L. The second is the so called diminishing learning rate, used in the well known paper by , if again the function has globally Lipschitz continuous gradient (but the Lipschitz constant may be unknown) and the learning rates converge to 0.

Қорытынды

Қорыта айтқанда, кері іздеу (және оның түрлендірілімдері) – іске асыру оңай, кез келген функцияға қолданылатын, теориялық тұрғыдан сенімді (сыни нүктелерге жуықтасу және еңіс нүктелерінен қашу бойынша) және практикада жақсы нәтиже беретін әдіс. Теориялық кепілдігі бар басқа да әдістер, мысалы, оқу жылдамдығын азайту немесе оқу жылдамдығы <1/L стандартты GD, олардың екеуі де мақсатты функцияның градиенті Липшиц үздіксіз болуын қажет етеді, кері іздеудің арнайы жағдайы болып табылады немесе Армихо шартын орындайды. Бұл әдісті қолдану үшін шығын функциясының үздіксіз түрде дифференциалдануы қажет болғанымен, практикада тығыз ашық жиынтықта үздіксіз дифференциалдалатын функцияларға да, мысалы, немесе , сәтті қолдануға болады.