Математикалық оптимизацияда сенім аймағының талдауы
Trust region
Математикалық оптимизациядағы сенім аймағы – мақсатты функцияның модельмен жуықталған бөлігі. Жақсы жуықтама болса, кеңейеді, нашар болса, тарылады. SEO үшін оптимизацияланған.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Математикалық оңтайландыруда сенім аймағы – модельдік функция (көбінесе квадраттық) арқылы жуықталған мақсатты функция аймағының ішкі жиыны. Егер сенім аймағында мақсатты функцияның жеткілікті моделі табылмаса, аймақ кеңейтіледі; ал жуықтау нашар болса, керісінше аймақ қысқартылады. Модельдік жуықтаудан күтілетін жақсарту мен мақсатты функциядағы нақты жақсарту арақатынасын салыстыру арқылы сәйкестік бағаланады. Бұл арақатынастың қарапайым шекті мәні кеңейту және қысқарту критерийі ретінде қолданылады – модельдік функция тек онымен орынды жуықтауға болатын аймақта ғана "сенімді" деп есептеледі. Сенім аймағы әдістері белгілі бір жағдайда сызықты іздеу әдістеріне қарама-қарсы болып табылады: сенім аймағы әдістері алдымен қадамның мөлшерін (сенім аймағының мөлшері) және содан кейін қадам бағытын таңдайды, ал сызықты іздеу әдістері алдымен қадам бағытын, содан кейін қадамның мөлшерін таңдайды. Сенім аймағы әдістерінің жалпы идеясы көптеген атаулармен белгілі; терминнің алғашқы қолданылуы Соренсеннің (1982) еңбегінде кездеседі. Флетчердің (1980) танымал оқулығында бұл алгоритмдер шектеулі қадам әдістері деп аталады. Сонымен қатар, әдіс бойынша алғашқы негізгі жұмыста Голдфельд, Куандт және Троттер (1966) оны квадраттық төбеге көтерілу деп атайды.
In mathematical optimization, a trust region is the subset of the region of the objective function that is approximated using a model function (often a quadratic). If an adequate model of the objective function is found within the trust region, then the region is expanded; conversely, if the approximation is poor, then the region is contracted. The fit is evaluated by comparing the ratio of expected improvement from the model approximation with the actual improvement observed in the objective function. Simple thresholding of the ratio is used as the criterion for expansion and contraction—a model function is "trusted" only in the region where it provides a reasonable approximation. Trust region methods are in some sense dual to line search methods: trust region methods first choose a step size (the size of the trust region) and then a step direction, while line search methods first choose a step direction and then a step size. The general idea behind trust region methods is known by many names; the earliest use of the term seems to be by Sorensen (1982). A popular textbook by Fletcher (1980) calls these algorithms restricted step methods. Additionally, in an early foundational work on the method, Goldfeld, Quandt, and Trotter (1966) refer to it as quadratic hill climbing.
Мысал
Концептуалды тұрғыдан алғанда, Левенберг-Маркардт алгоритмінде мақсаттық функция итеративті түрде квадраттық бетке жуықталады, содан кейін сызықтық шешімді қолдану арқылы бағалау жаңартылады. Бұл ғана бастапқы шама оптималдан тым алыс болса, жақсы конвергенцияға қол жеткізу мүмкін болмайды. Осы себепті алгоритм әр қадамды шектейді, осылайша "тыртықтап" кететін қадамдардың алдын алады. "Тыртықтау" ұғымын келесідей іске асырады. , үшін шешудің орнына , шешіледі, мұнда – A матрицасының диагональдарымен бірдей диагональдарға ие диагональдық матрица, ал λ – сенім аймағының мөлшерін бақылайтын параметр. Геометриялық тұрғыдан алғанда, бұл квадраттық формаға ортасы болып табылатын параболоидты қосады, нәтижесінде кішірек қадам жасалады. Сенім аймағының мөлшерін өзгертудің (λ) маңызы зор. Әр итерацияда, төмендетілген квадраттық сәйкестік шығын функциясының қандай да бір төмендеуін болжайды, , оның нақты төмендеуден кішірек болуын күтеміз. берілген жағдайда, мынаны бағалауға болады.
Conceptually, in the Levenberg–Marquardt algorithm, the objective function is iteratively approximated by a quadratic surface, then using a linear solver, the estimate is updated. This alone may not converge nicely if the initial guess is too far from the optimum. For this reason, the algorithm instead restricts each step, preventing it from stepping "too far". It operationalizes "too far" as follows. Rather than solving for , it solves , where is the diagonal matrix with the same diagonal as A, and λ is a parameter that controls the trust region size. Geometrically, this adds a paraboloid centered at to the quadratic form, resulting in a smaller step. The trick is to change the trust region size (λ). At each iteration, the damped quadratic fit predicts a certain reduction in the cost function, , which we would expect to be a smaller reduction than the true reduction. Given , we can evaluate
қатынасын қарастыру арқылы сенім аймағының мөлшерін реттеуге болады. Жалпы, -нің -ден сәл кішірек болуын күтеміз, сондықтан қатынас, мысалы, 0,25 пен 0,5 аралығында болуы керек. Егер қатынас 0,5-тен жоғары болса, онда қадам тым көп демпингтелген, сондықтан сенім аймағын кеңейту қажет (λ-ді азайту) және итерацияны қайталау керек. Егер қатынас 0,25-тен төмен болса, онда нақты функция сенім аймағының шамасынан "тыртықтап" кетеді, сондықтан сенім аймағын қысқарту қажет (λ-ді арттыру) және қайтадан талқылау керек.
By looking at the ratio , we can adjust the trust region size. In general, we expect to be a bit smaller than , and so the ratio would be between, say, 0.25 and 0.5. If the ratio is more than 0.5, then we are damping the step too much, so expand the trust region (decrease λ) and iterate. If the ratio is smaller than 0.25, then the true function is diverging "too much" from the trust region approximation, so shrink the trust region (increase λ) and try again.