Mbinu ya gradient. Mapitio ya njia za upinde rangi katika matatizo ya uboreshaji wa hisabati

Mbinu ya kushuka kwa gradient.

Mwelekeo wa kushuka kwa kasi zaidi unalingana na mwelekeo wa upungufu mkubwa wa kazi. Inajulikana kuwa mwelekeo wa ongezeko kubwa zaidi katika kazi ya vigezo viwili u = f (x, y) ina sifa ya upinde rangi:

wapi e1, e2 - vekta za kitengo(orts) katika mwelekeo wa shoka za kuratibu. Kwa hivyo, mwelekeo ulio kinyume na upinde rangi utaonyesha mwelekeo wa kupungua zaidi kwa kazi. Mbinu kulingana na kuchagua njia ya uboreshaji kwa kutumia gradient zinaitwa upinde rangi.

Wazo la njia ya kushuka kwa gradient ni kama ifuatavyo. Kuchagua mahali pa kuanzia

Tunahesabu gradient ya chaguo za kukokotoa zinazozingatiwa ndani yake. Tunachukua hatua kwa mwelekeo tofauti na gradient:

Mchakato unaendelea hadi thamani ya chini zaidi inapatikana kazi ya lengo. Kwa kusema kabisa, mwisho wa utafutaji utatokea wakati harakati kutoka kwa hatua iliyopatikana na hatua yoyote inaongoza kwa ongezeko la thamani ya kazi ya lengo. Ikiwa kiwango cha chini cha kazi kinafikiwa ndani ya eneo linalozingatiwa, basi katika hatua hii gradient ni sifuri, ambayo inaweza pia kutumika kama ishara kuhusu mwisho wa mchakato wa uboreshaji.

Njia ya mteremko wa gradient ina hasara sawa na njia ya kuratibu ya kushuka: mbele ya mifereji ya maji juu ya uso, muunganisho wa njia ni polepole sana.

Katika njia iliyoelezewa, inahitajika kuhesabu upinde rangi ya lengo la kukokotoa f(x) katika kila hatua ya utoshelezaji:

Fomula za derivatives za sehemu zinaweza kupatikana kwa uwazi tu katika kesi wakati kazi ya lengo imebainishwa kwa uchanganuzi. Vinginevyo, derivatives hizi huhesabiwa kwa kutumia utofautishaji wa nambari:

Unapotumia mteremko wa kushuka katika matatizo ya uboreshaji, wingi wa hesabu kwa kawaida huangukia kwenye kukokotoa upinde rangi ya chaguo za kukokotoa katika kila sehemu ya mteremko wa mteremko. Kwa hiyo, ni vyema kupunguza idadi ya pointi hizo bila kuacha suluhisho yenyewe. Hii inafanikiwa katika baadhi ya njia ambazo ni marekebisho ya asili ya gradient. Mmoja wao ni njia ya kushuka kwa kasi zaidi. Kwa mujibu wa njia hii, baada ya kuamua katika hatua ya awali mwelekeo kinyume na gradient ya kazi ya lengo, tatizo la optimization moja-dimensional linatatuliwa kwa kupunguza kazi kando ya mwelekeo huu. Yaani, kazi imepunguzwa:

Ili kupunguza Unaweza kutumia mojawapo ya mbinu za uboreshaji zenye mwelekeo mmoja. Unaweza tu kuelekea upande ulio kinyume na gradient, bila kuchukua hatua moja, lakini hatua kadhaa hadi kazi ya lengo itaacha kupungua. Katika hatua mpya iliyopatikana, mwelekeo wa kushuka umedhamiriwa tena (kwa kutumia gradient) na hatua mpya ya chini ya kazi ya lengo inatafutwa, nk Kwa njia hii, kushuka hutokea kwa hatua kubwa zaidi, na gradient ya kazi ni. imehesabiwa ndani wachache pointi. Tofauti ni kwamba hapa mwelekeo wa optimization moja-dimensional imedhamiriwa na gradient ya kazi ya lengo, wakati kuratibu kushuka unafanywa kwa kila hatua pamoja na moja ya maelekezo ya kuratibu.

Mbinu ya mteremko yenye mwinuko zaidi kwa kesi ya chaguo za kukokotoa za vigeu viwili z = f(x,y).

Kwanza, ni rahisi kuonyesha kwamba gradient ya kazi ni perpendicular kwa tangent kwa mstari wa ngazi katika hatua fulani. Kwa hiyo, katika njia za gradient kushuka hutokea kwa kawaida hadi mstari wa ngazi. Pili, katika hatua ambayo kiwango cha chini cha kazi ya lengo kando ya mwelekeo hufikiwa, derivative ya kazi kando ya mwelekeo huu inakuwa sifuri. Lakini derivative ya kazi ni sifuri katika mwelekeo tangent kwa mstari wa ngazi. Inafuata kwamba gradient ya kazi ya lengo katika hatua mpya ni perpendicular kwa mwelekeo wa optimization moja-dimensional katika hatua ya awali, yaani, kushuka kwa hatua mbili mfululizo hufanywa kwa mwelekeo wa pande zote.

Mbinu za gradient

Njia za uboreshaji zisizo na kikomo za gradient hutumia tu derivatives ya kwanza ya kazi ya lengo na ni mbinu za kukadiria kwa mstari kwa kila hatua, i.e. kazi ya lengo katika kila hatua inabadilishwa na hyperplane ya tangent kwa grafu yake katika hatua ya sasa.

Washa k-th hatua Njia za gradient, mabadiliko kutoka kwa uhakika Xk hadi Xk+1 yanaelezewa na uhusiano:

ambapo k ni saizi ya hatua, k ni vekta katika mwelekeo Xk+1-Xk.

Mbinu za Kushuka kwa kasi zaidi

Njia hii ilizingatiwa kwanza na kutumiwa na O. Cauchy katika karne ya 18. Wazo lake ni rahisi: gradient ya kazi ya lengo f(X) katika hatua yoyote ni vekta katika mwelekeo wa ongezeko kubwa la thamani ya kazi. Kwa hiyo, antigradient itaelekezwa kwa mwelekeo wa kupungua zaidi kwa kazi na ni mwelekeo wa kushuka kwa kasi zaidi. Kinza upinde rangi (na upinde rangi) ni ya othogonal kwa uso wa kiwango f(X) katika hatua ya X. Tukitambulisha mwelekeo katika (1.2)

basi hii itakuwa mwelekeo wa kushuka kwa kasi zaidi kwa uhakika Xk.

Mchakato wa kubadilisha XK kwa X+1 ni:

Antigradient inatoa tu mwelekeo wa kushuka, lakini sio ukubwa wa hatua. KATIKA kesi ya jumla hatua moja haitoi kiwango cha chini, hivyo utaratibu wa kushuka lazima urudiwe mara kadhaa. Katika hatua ya chini, vipengele vyote vya gradient ni sawa na sifuri.

Njia zote za gradient hutumia wazo lililotajwa na hutofautiana kutoka kwa kila mmoja katika maelezo ya kiufundi: hesabu ya derivatives kwa kutumia fomula ya uchambuzi au makadirio ya tofauti ya mwisho; saizi ya hatua inaweza kuwa ya mara kwa mara, kubadilika kulingana na sheria fulani, au kuchaguliwa baada ya kutumia njia za uboreshaji wa mwelekeo mmoja katika mwelekeo wa antigradient, nk. Nakadhalika.

Hatutaingia kwa undani, kwa sababu ... Njia ya mteremko yenye mwinuko zaidi haipendekezwi kwa ujumla kama utaratibu wa uboreshaji madhubuti.

Mojawapo ya ubaya wa njia hii ni kwamba inabadilika hadi mahali popote, pamoja na sehemu ya tandiko, ambayo haiwezi kuwa suluhisho.

Lakini jambo muhimu zaidi ni muunganiko wa polepole sana wa asili ya mwinuko katika hali ya jumla. Jambo ni kwamba kushuka ni "haraka zaidi" kwa maana ya ndani. Ikiwa hyperspace ya utafutaji imepanuliwa sana ("ravine"), basi antigradient inaelekezwa karibu na orthogonally hadi chini ya "bonde," i.e. mwelekeo bora wa kufikia kiwango cha chini. Kwa maana hii, tafsiri ya moja kwa moja Neno la Kiingereza"mteremko mkali zaidi", i.e. asili ya mteremko mkali inaendana zaidi na hali ya mambo kuliko neno "haraka zaidi", lililopitishwa katika fasihi maalum ya lugha ya Kirusi. Njia moja ya kutoka katika hali hii ni kutumia habari iliyotolewa na derivatives ya pili ya sehemu. Njia nyingine ya nje ni kubadilisha mizani ya vigezo.

ukadirio wa upinde rangi wa derivative wa mstari

Mbinu ya upinde rangi ya Fletcher-Reeves

Katika njia ya gradient ya conjugate, mlolongo wa maelekezo ya utafutaji hujengwa, ambayo ni mchanganyiko wa mstari wa mwelekeo wa sasa wa kushuka kwa kasi zaidi, na maelekezo ya awali ya utafutaji, i.e.

Zaidi ya hayo, mgawo huchaguliwa ili kufanya maelekezo ya utafutaji kuunganishwa. Imethibitishwa hivyo

na hii ni matokeo ya thamani sana ambayo inakuwezesha kujenga algorithm ya utoshelezaji haraka na yenye ufanisi.

Algorithm ya Fletcher-Reeves

1. Katika X0 imehesabiwa.

2. Katika hatua ya kth, kwa kutumia utafutaji wa mwelekeo mmoja katika mwelekeo, kiwango cha chini cha f (X) kinapatikana, ambacho huamua uhakika Xk +1.

• 3. f(Xk+1) na huhesabiwa.
• 4. Mwelekeo umedhamiriwa kutoka kwa uhusiano:

• 5. Baada ya kurudia (n+1)th (yaani wakati k=n), kuanzisha upya kunafanywa: X0=Xn+1 inachukuliwa na mpito hadi hatua ya 1 unafanywa.
• 6. Algorithm inacha wakati

ambapo ni mara kwa mara kiholela.

Faida ya algorithm ya Fletcher-Reeves ni kwamba hauitaji ubadilishaji wa matrix na huhifadhi kumbukumbu ya kompyuta, kwani hauitaji matrices inayotumiwa katika njia za Newtonian, lakini wakati huo huo ni sawa na algorithms ya quasi-Newtonian. Kwa sababu maelekezo ya utafutaji yanaunganishwa, basi kazi ya quadratic itapunguzwa kwa si zaidi ya hatua n. Katika hali ya jumla, kuanzisha upya hutumiwa, ambayo inakuwezesha kupata matokeo.

Algorithm ya Fletcher-Reeves ni nyeti kwa usahihi wa utafutaji wa moja-dimensional, hivyo wakati wa kutumia, ni muhimu kuondokana na makosa yoyote ya kuzunguka ambayo yanaweza kutokea. Kwa kuongeza, algorithm inaweza kushindwa katika hali ambapo Hessian inakuwa na hali mbaya. Algorithm haina dhamana ya muunganisho kila wakati na kila mahali, ingawa mazoezi yanaonyesha kuwa algorithm karibu kila wakati hutoa matokeo.

Mbinu za Newton

Mwelekeo wa utafutaji unaolingana na ukoo wa mwinuko unahusiana na ukadiriaji wa mstari kazi inayolengwa. Njia za kutumia derivatives ya pili zilitoka kwa makadirio ya quadratic ya kazi ya lengo, yaani, wakati wa kupanua kazi katika mfululizo wa Taylor, masharti ya amri ya tatu na ya juu yanatupwa.

iko wapi tumbo la Hessian.

Kiwango cha chini cha upande wa kulia (ikiwa kipo) kinapatikana mahali sawa na kiwango cha chini fomu ya quadratic. Wacha tuandike fomula ili kuamua mwelekeo wa utaftaji:

Kiwango cha chini kinafikiwa

Algorithm ya uboreshaji ambayo mwelekeo wa utaftaji umedhamiriwa kutoka kwa uhusiano huu inaitwa njia ya Newton, na mwelekeo unaitwa mwelekeo wa Newton.

Katika matatizo ya kupata kiwango cha chini cha kiholela kazi ya quadratic na matrix chanya ya derivatives ya pili, njia ya Newton inatoa suluhisho katika iteration moja, bila kujali uchaguzi wa kuanzia.

Uainishaji wa njia za Newton

Mbinu ya Newton yenyewe inajumuisha kutumia mwelekeo wa Newton mara moja ili kuboresha utendaji wa quadratic. Ikiwa kipengele cha kukokotoa si cha quadratic, basi nadharia ifuatayo ni kweli.

Nadharia 1.4. Ikiwa matrix ya Hessian ya fomula f isiyo ya mstari ya fomu ya jumla katika kiwango cha chini cha X* ni chanya dhahiri, mahali pa kuanzia huchaguliwa vya kutosha karibu na X* na urefu wa hatua huchaguliwa kwa usahihi, basi njia ya Newton hubadilika hadi X* na quadratic. kiwango.

Njia ya Newton inachukuliwa kuwa njia ya kumbukumbu; Walakini, njia ya Newton ni nzuri tu kwa matrix chanya ya Hessian iliyo na hali nzuri (kiashiria chake lazima kiwe kikubwa. Juu ya sifuri, kwa usahihi, uwiano wa eigenvalues ​​kubwa na ndogo inapaswa kuwa karibu na moja). Ili kuondokana na upungufu huu, tumia njia zilizobadilishwa Newton, kwa kutumia maelekezo ya Newton wakati wowote inapowezekana na kupotoka kutoka kwao tu inapobidi.

Kanuni ya jumla ya marekebisho ya njia ya Newton ni kama ifuatavyo: kwa kila marudio, matrix fulani chanya "inayohusishwa" na inaundwa kwanza, na kisha kuhesabiwa kwa kutumia fomula.

Kwa kuwa ni chanya uhakika, basi - itakuwa lazima kuwa mwelekeo wa ukoo. Utaratibu wa ujenzi umepangwa ili sanjari na tumbo la Hessian ikiwa ni chanya dhahiri. Taratibu hizi zinatokana na mtengano fulani wa matrix.

Kundi lingine la njia, kwa kweli sio duni kwa kasi kwa njia ya Newton, ni msingi wa makadirio ya matrix ya Hessian kwa kutumia tofauti za kikomo, kwa sababu. Sio lazima kutumia maadili halisi ya derivatives kwa uboreshaji. Njia hizi ni muhimu wakati hesabu ya uchambuzi wa derivatives ni ngumu au haiwezekani tu. Njia kama hizo huitwa njia tofauti za Newton.

Ufunguo wa ufanisi wa mbinu za aina ya Newton ni kuzingatia maelezo kuhusu mkunjo wa kazi iliyopunguzwa, iliyo katika tumbo la Hessian na kuruhusu ujenzi wa miundo sahihi ya ndani ya quadratic ya utendaji wa lengo. Lakini inawezekana kukusanya na kukusanya taarifa kuhusu mkunjo wa chaguo za kukokotoa kulingana na kuangalia mabadiliko ya upinde rangi wakati wa marudio ya mteremko.

Njia zinazolingana, kulingana na uwezekano wa kukadiria mzingo wa kazi isiyo ya mstari bila kuunda matrix yake ya Hessian, huitwa njia za quasi-Newtonian.

Kumbuka kwamba wakati wa kujenga utaratibu wa utoshelezaji wa aina ya Newtonian (ikiwa ni pamoja na quasi-Newtonian), ni muhimu kuzingatia uwezekano wa kuonekana kwa hatua ya saddle. Katika kesi hii, vector ya mwelekeo bora zaidi wa utafutaji daima itaelekezwa kuelekea hatua ya tandiko, badala ya kuhamia mbali nayo kwa mwelekeo wa chini.

Njia ya Newton-Raphson

Njia hii inajumuisha kurudia kutumia mwelekeo wa Newton wakati wa kuboresha utendaji ambao sio wa quadratic.

Kuu formula ya kurudia uboreshaji wa multidimensional

inatumika kwa njia hii wakati wa kuchagua mwelekeo wa utoshelezaji kutoka kwa uhusiano

Urefu wa hatua halisi umefichwa katika mwelekeo wa Newtonian usio wa kawaida.

Kwa kuwa njia hii haihitaji thamani ya kazi ya lengo katika hatua ya sasa, wakati mwingine inaitwa moja kwa moja au njia ya uchambuzi uboreshaji. Uwezo wake wa kuamua kiwango cha chini cha kazi ya quadratic katika hesabu moja inaonekana kuvutia sana kwa mtazamo wa kwanza. Hata hivyo, hii "hesabu moja" inahitaji gharama kubwa. Kwanza kabisa, ni muhimu kuhesabu n derivatives ya sehemu ya utaratibu wa kwanza na n (n+1)/2 - ya pili. Kwa kuongeza, tumbo la Hessian lazima ligeuzwe. Hii inahitaji utendakazi wa kimahesabu wa n3. Kwa gharama sawa, mbinu za mwelekeo wa kuunganisha au mbinu za gradient za kuunganisha zinaweza kuchukua kuhusu hatua za n, i.e. kufikia karibu matokeo sawa. Kwa hivyo, kurudia kwa njia ya Newton-Raphson haitoi faida katika kesi ya kazi ya quadratic.

Ikiwa kazi sio quadratic, basi

• - mwelekeo wa awali, kwa ujumla, hauonyeshi tena kiwango cha chini kabisa, ambayo inamaanisha kuwa marudio lazima yarudiwe mara nyingi;
• - hatua ya urefu wa kitengo inaweza kusababisha hatua na thamani mbaya zaidi utendakazi wa lengo, na utafutaji unaweza kurudisha mwelekeo usio sahihi ikiwa, kwa mfano, Hessian si chanya uhakika;
• - Hessian inaweza kuwa na hali mbaya, na hivyo haiwezekani kuipindua, i.e. kuamua mwelekeo wa marudio yanayofuata.

Mkakati wenyewe hautofautishi ni sehemu gani ya stationary (kiwango cha chini, kiwango cha juu, sehemu ya tandiko) utafutaji unakaribia, na mahesabu ya maadili ya kazi ya lengo, ambayo inaweza kutumika kufuatilia kama kazi inaongezeka, haijafanywa. Hii ina maana kwamba kila kitu kinategemea eneo gani la kivutio hatua ya stationary inageuka kuwa sehemu ya kuanzia ya utafutaji. Mkakati wa Newton-Raphson hautumiwi peke yake bila marekebisho ya aina moja au nyingine.

Mbinu za Pearson

Pearson alipendekeza mbinu kadhaa zinazokadiria Hessian inverse bila kukokotoa kwa uwazi derivatives ya pili, i.e. kwa kuangalia mabadiliko katika mwelekeo wa antigradient. Katika kesi hii, maelekezo ya kuunganisha yanapatikana. Algorithms hizi hutofautiana tu katika maelezo. Tunawasilisha wale waliopokea zaidi matumizi mapana katika maeneo yaliyotumika.

Pearson Algorithm No. 2.

Katika algorithm hii, Hessian inverse inakadiriwa na matrix Hk, iliyohesabiwa kwa kila hatua kwa kutumia fomula.

Matrix ya ulinganifu chanya bila mpangilio huchaguliwa kama matriki ya awali H0.

Algorithm hii ya Pearson mara nyingi husababisha hali ambapo matrix Hk inakuwa na hali mbaya, ambayo ni, huanza kuzunguka, ikizunguka kati ya uhakika chanya na isiyo chanya, wakati kiashiria cha tumbo kiko karibu na sifuri. Ili kuepuka hali hii, ni muhimu kufafanua upya matrix kila hatua n, kuilinganisha na H0.

Pearson Algorithm No. 3.

Katika algorithm hii, matrix Hk + 1 imedhamiriwa kutoka kwa formula

Hk+1 = Hk +

Njia ya kushuka inayotokana na algorithm ni sawa na tabia ya algoriti ya Davidon-Fletcher-Powell, lakini hatua ni fupi kidogo. Pearson pia alipendekeza tofauti ya algorithm hii na uwekaji upya wa matrix ya mzunguko.

Algorithm ya Projective ya Newton-Raphson

Pearson alipendekeza wazo la algorithm ambayo matrix huhesabiwa kutoka kwa uhusiano

H0=R0, ambapo matrix R0 ni sawa na matrices ya awali katika algoriti za awali.

Wakati k ni kizidishio cha nambari ya vigeu huru n, matrix Hk inabadilishwa na matrix Rk+1, iliyohesabiwa kama jumla.

Kiasi Hk(f(Xk+1) - f(Xk)) ni makadirio ya vekta ya nyongeza ya gradient (f(Xk+1) - f(Xk)), orthogonal kwa vekta zote za nyongeza za gradient katika hatua za awali. Baada ya kila hatua n, Rk ni makadirio ya kinyume cha Hessian H-1(Xk), ili kimsingi utafutaji wa Newton ufanywe (takriban).

Mbinu ya Davidon-Fletcher-Powell

Njia hii ina majina mengine - njia ya metri ya kutofautiana, njia ya quasi-Newton, kwa sababu anatumia mbinu hizi zote mbili.

Mbinu ya Davidon-Fletcher-Powell (DFP) inategemea matumizi ya maelekezo ya Newton, lakini hauhitaji hesabu ya Hessian inverse katika kila hatua.

Mwelekeo wa utafutaji katika hatua k ni mwelekeo

ambapo Hi ni matrix chanya ya ulinganifu ambayo inasasishwa kwa kila hatua na katika kikomo inakuwa sawa na Hessian kinyume. Matrix ya kitambulisho kawaida huchaguliwa kama matrix ya mwanzo ya H. Utaratibu wa kurudia wa DFT unaweza kuwakilishwa kama ifuatavyo:

• 1. Katika hatua k kuna uhakika Xk na chanya uhakika tumbo Hk.
• 2. Chagua kama mwelekeo mpya wa utafutaji

3. Utafutaji wa mwelekeo mmoja (kawaida tafsiri ya ujazo) kando ya mwelekeo huamua k, ambayo hupunguza kazi.

4. Mategemeo.

5. Mategemeo.

6. Imedhamiriwa. Ikiwa Vk au ni ndogo ya kutosha, utaratibu unaisha.

• 7. Inachukuliwa kuwa Uk = f(Xk+1) - f(Xk).
• 8. Matrix Hk inasasishwa kulingana na fomula

9. Ongeza k kwa moja na urudi kwenye hatua ya 2.

Njia hiyo ni nzuri katika mazoezi ikiwa hitilafu katika mahesabu ya gradient ni ndogo na tumbo Hk haina hali mbaya.

Matrix Ak inahakikisha muunganiko wa Hk hadi G-1, matrix Bk inahakikisha uhakika chanya wa Hk+1 katika hatua zote na haijumuishi H0 katika kikomo.

Katika kesi ya kazi ya quadratic

hizo. Algorithm ya DFP hutumia maelekezo ya kuunganisha.

Kwa hivyo, njia ya DFT hutumia mawazo yote ya mbinu ya Newtonian na sifa za maelekezo ya kuunganisha, na wakati wa kupunguza kazi ya quadratic, inaunganishwa kwa si zaidi ya n iterations. Ikiwa kazi iliyoboreshwa ina fomu karibu na kazi ya quadratic, basi njia ya DFT ni nzuri kutokana na ukadiriaji mzuri wa G-1 (njia ya Newton). Ikiwa kazi ya lengo ina fomu ya jumla, basi njia ya DFT ni nzuri kutokana na matumizi ya maelekezo ya conjugate.

Wacha tuzingatie shida ya upunguzaji usio na masharti wa kazi inayoweza kutofautishwa ya anuwai nyingi Acha thamani ya upinde rangi ifikiwe kwa kiwango cha chini kazi inatolewa na antigradient Sifa hii inatumika kwa kiasi kikubwa katika idadi ya mbinu za kupunguza. Katika njia ya gradient inayozingatiwa hapa chini, mwelekeo wa kushuka kutoka kwa uhakika huchaguliwa moja kwa moja

Zipo njia mbalimbali kuchagua hatua, ambayo kila moja inabainisha chaguo maalum njia ya gradient.

1. Njia ya kushuka kwa kasi zaidi.

Hebu tuchunguze kazi ya kigezo kimoja cha kadiri na tuchague kama thamani ambayo usawa unashikilia

Njia hii, iliyopendekezwa mnamo 1845 na O. Cauchy, sasa inajulikana kama njia ya kushuka kwa kasi zaidi.

Katika Mtini. Mchoro 10.5 unaonyesha mchoro wa kijiometri wa njia hii kwa ajili ya kupunguza utendaji wa vigezo viwili. Kutoka hatua ya kuanzia perpendicular kwa mstari wa ngazi katika mwelekeo wa kushuka, kushuka kunaendelea mpaka thamani ya chini ya kazi pamoja na ray inafikiwa. Katika hatua iliyopatikana, ray hii inagusa mstari wa ngazi Kisha, kushuka hufanywa kutoka kwa uhakika katika mwelekeo wa mstari hadi mstari wa ngazi mpaka ray inayofanana inagusa mstari wa ngazi unaopitia hatua hii kwa uhakika, nk.

Kumbuka kwamba katika kila iteration, uchaguzi wa hatua inahusisha kutatua tatizo moja-dimensional minimization (10.23). Wakati mwingine operesheni hii inaweza kufanywa kwa uchambuzi, kwa mfano kwa kazi ya quadratic.

Wacha tutumie njia ya mteremko mwinuko zaidi ili kupunguza utendaji wa quadratic

yenye matriki ya uhakika ya ulinganifu chanya A.

Kulingana na formula (10.8), katika kesi hii, kwa hivyo, formula (10.22) inaonekana kama hii:

taarifa, hiyo

Chaguo hili la kukokotoa ni kazi ya kukokotoa ya kigezo a na hufikia kiwango cha chini kwa thamani ambayo kwayo

Hivyo, kuhusiana na kupunguza quadratic

kazi (10.24), njia ya mteremko mwinuko zaidi ni sawa na hesabu kwa kutumia fomula (10.25), ambapo

Kumbuka 1. Kwa kuwa kiwango cha chini cha utendaji (10.24) kinapatana na suluhisho la mfumo, njia ya kushuka yenye mwinuko zaidi (10.25), (10.26) pia inaweza kutumika kama njia ya kurudia suluhisho kwa mifumo ya mstari milinganyo ya algebra iliyo na alama za ulinganifu chanya.

Kumbuka 2. Kumbuka kwamba uwiano wa Rayleigh uko wapi (tazama § 8.1).

Mfano 10.1. Wacha tutumie njia ya mteremko mwinuko zaidi ili kupunguza utendaji wa quadratic

Kumbuka kwamba Kwa hiyo, tunajua thamani halisi ya hatua ya chini mapema. Hebu tuandike kipengele hiki katika fomu (10.24), ambapo matrix na vekta Kama ni rahisi kuona,

Wacha tuchukue makadirio ya awali na tufanye mahesabu kwa kutumia fomula (10.25), (10.26).

Narudia.

II marudio.

Inaweza kuonyeshwa kuwa kwa marudio yote maadili yatapatikana

Kumbuka kwamba kwa hivyo,

mlolongo unaopatikana kwa njia ya mteremko mwinuko zaidi huungana na kasi maendeleo ya kijiometri, ambaye dhehebu lake

Katika Mtini. Mchoro 10.5 unaonyesha hasa njia ya mteremko ambayo ilipatikana katika mfano huu.

Kwa kesi ya kupunguza utendaji wa quadratic, yafuatayo yanashikilia: matokeo ya jumla.

Nadharia 10.1. Acha A iwe linganifu chanya bainifu na utendaji wa quadratic (10.24) umepunguzwa. Halafu, kwa chaguo lolote la makadirio ya awali, njia ya mteremko mwinuko zaidi (10.25), (10.26) huungana na makadirio ya makosa yafuatayo ni sahihi:

Hapa na Lado ndio viwango vya chini na vya juu zaidi vya matrix A.

Kumbuka kuwa njia hii inabadilika kwa kiwango cha ukuaji wa kijiometri, dhehebu ambayo, ikiwa iko karibu, ni ndogo na njia inabadilika haraka sana. Kwa mfano, katika Mfano wa 10.1 tunayo na kwa hivyo Ikiwa Aschach, basi 1 na tunapaswa kutarajia muunganiko wa polepole wa njia ya mteremko mwinuko zaidi.

Mfano 10.2. Utumiaji wa mbinu ya mteremko yenye mwinuko zaidi ili kupunguza utendaji wa quadratic wakati wa ukadiriaji wa awali hutoa mlolongo wa makadirio ambapo Njia ya mteremko imeonyeshwa kwenye Mtini. 10.6.

Mlolongo hubadilika hapa kwa kasi ya maendeleo ya kijiometri, dhehebu ambayo ni sawa na, i.e., polepole sana,

Nitajaribu kuliko ile iliyopita. Kwa kuwa hapa matokeo yaliyopatikana yanaendana kabisa na makadirio (10.27).

Kumbuka 1. Tuliunda nadharia juu ya muunganiko wa njia ya mteremko mwinuko zaidi katika hali ambapo kipengele cha kukokotoa ni cha quadratic. Katika hali ya jumla, ikiwa kazi ya kupunguzwa ni laini kabisa na ina kiwango cha chini cha x, basi, bila kujali chaguo la makadirio ya awali, mlolongo uliopatikana kwa njia hii hubadilika hadi x saa . Katika kesi hii, baada ya kuingia kitongoji kidogo cha kiwango cha chini, muunganisho unakuwa wa mstari na dhehebu la maendeleo ya kijiometri inayolingana inakadiriwa kutoka juu na thamani na ambapo kiwango cha chini na cha juu. eigenvalues Matrices ya Hessian

Rekea 2. Kwa utendaji kazi wa lengo la quadratic (10.24), suluhu la tatizo la upunguzaji wa mwelekeo mmoja (10.23) linaweza kupatikana kwa njia ya fomula rahisi iliyo wazi (10.26). Walakini, kwa wengine wengi kazi zisizo za mstari Hili haliwezi kufanywa na kukokotoa njia ya mteremko mwinuko zaidi unayopaswa kutumia njia za nambari upunguzaji wa mwelekeo mmoja wa aina iliyojadiliwa katika sura iliyotangulia.

2. Tatizo la "mifereji".

Kutoka kwa majadiliano hapo juu inafuata kwamba njia ya upinde rangi hubadilika haraka sana ikiwa, kwa kazi inayopunguzwa, nyuso za kiwango ziko karibu na nyanja (ikiwa mistari ya kiwango iko karibu na miduara). Kwa utendakazi kama huo na 1. Nadharia 10.1, Alama 1, pamoja na tokeo la Mfano 10.2 zinaonyesha kuwa kiwango cha muunganiko hushuka sana kadiri thamani inavyoongezeka chaguo za kukokotoa zinazopunguzwa zimerefushwa sana katika mwelekeo fulani. Katika kesi mbili-dimensional, misaada ya uso sambamba inafanana na ardhi ya eneo na bonde (Mchoro 10.7). Kwa hivyo, kazi kama hizo kawaida huitwa kazi za gully. Pamoja na maelekezo yanayoashiria "chini ya bonde," kazi ya gully inabadilika kidogo, lakini katika mwelekeo mwingine unaoonyesha "mteremko wa bonde," mabadiliko makali katika kazi hutokea.

Ikiwa mahali pa kuanzia huanguka kwenye "mteremko wa bonde", basi mwelekeo wa asili ya gradient unageuka kuwa karibu kabisa na "chini ya bonde" na njia inayofuata iko kwenye "mteremko wa bonde". Hatua inayofuata kuelekea "chini ya bonde" inarudisha njia ya "mteremko wa bonde" la asili. Matokeo yake, badala ya kusonga kando ya "chini ya bonde" kuelekea hatua ya chini, trajectory ya kushuka hufanya zigzag kuruka kwenye "bonde", karibu kamwe kukaribia lengo (Mchoro 10.7).

Ili kuharakisha muunganisho wa njia ya upinde rangi huku ukipunguza kazi za gully, mbinu kadhaa maalum za "gully" zimetengenezwa. Wacha tutoe wazo la moja ya mbinu rahisi zaidi. Kutoka kwa pointi mbili za kuanzia karibu hufanya kushuka kwa gradient hadi "chini ya bonde". Mstari wa moja kwa moja hutolewa kupitia pointi zilizopatikana, ambazo hatua kubwa ya "gully" inachukuliwa (Mchoro 10.8). Kutoka kwa hatua iliyopatikana kwa njia hii, hatua moja ya kushuka kwa gradient inachukuliwa tena kwa uhakika Kisha hatua ya pili ya "gully" inachukuliwa pamoja na mstari wa moja kwa moja unaopitia pointi. Kama matokeo, harakati kando ya "chini ya bonde" hadi kiwango cha chini huharakishwa sana.

Zaidi maelezo ya kina kuhusu shida ya njia za "mifereji ya maji" na "gully" zinaweza kupatikana, kwa mfano, katika,.

3. Mbinu nyingine za kuamua hatua ya kushuka.

Kama ilivyo rahisi kuelewa, kwa kila marudio itakuwa muhimu kuchagua mwelekeo wa asili karibu na mwelekeo ambao harakati inaongoza kutoka hatua hadi hatua x. Kwa bahati mbaya, antigradient (kama sheria, mwelekeo usio na mafanikio wa ukoo. Hii inatamkwa haswa kwa kazi za gully. Kwa hivyo, shaka inazuka juu ya ushauri wa utaftaji kamili wa suluhisho la shida ya upunguzaji wa mwelekeo mmoja (10.23) na kuna hamu ya kuchukua hatua kama hiyo tu katika mwelekeo ambao utahakikisha "kupungua kwa kiasi kikubwa" kwa kazi Zaidi ya hayo, katika mazoezi, wakati mwingine wanaridhika na kufafanua thamani ambayo inahakikisha tu kupungua kwa thamani ya kazi ya lengo.

Unaweza pia kutafuta si kwa uhakika bora katika mwelekeo wa gradient, lakini kwa moja bora kuliko ya sasa.

Njia rahisi zaidi ya kutekeleza kati ya njia zote za uboreshaji za ndani. Ina hali dhaifu ya muunganisho, lakini kiwango cha muunganiko ni cha chini kabisa (mstari). Hatua ya njia ya upinde rangi hutumiwa mara nyingi kama sehemu ya mbinu nyingine za uboreshaji, kama vile mbinu ya Fletcher–Reeves.

Maelezo [ | ]

Maboresho[ | ]

Njia ya mteremko wa gradient inageuka kuwa polepole sana wakati wa kusonga kando ya bonde, na kadiri idadi ya vigeu katika utendaji wa lengo inavyoongezeka, tabia hii ya njia inakuwa ya kawaida. Ili kupambana na jambo hili, hutumiwa, kiini cha ambayo ni rahisi sana. Baada ya kufanya hatua mbili za asili ya gradient na kupata pointi tatu, hatua ya tatu inapaswa kuchukuliwa kwa mwelekeo wa vector kuunganisha pointi ya kwanza na ya tatu, kando ya chini ya bonde.

Kwa vitendakazi vilivyo karibu na quadratic, mbinu ya upinde rangi ya unganisha ni nzuri.

Maombi katika mitandao ya neva bandia[ | ]

Mbinu ya mteremko wa upinde rangi, iliyo na urekebishaji fulani, inatumika sana kwa mafunzo ya perceptron na inajulikana katika nadharia ya mitandao ya neva bandia kama mbinu ya uenezaji nyuma. Wakati wa kufunza mtandao wa neural wa aina ya perceptron, ni muhimu kubadilisha mgawo wa uzani wa mtandao ili kupunguza kosa la wastani wakati wa kutoka mtandao wa neva wakati mlolongo wa data ya pembejeo ya mafunzo hutolewa kwa pembejeo. Hapo awali, ili kuchukua hatua moja tu kwa kutumia njia ya asili ya gradient (fanya mabadiliko moja tu katika vigezo vya mtandao), ni muhimu kuwasilisha seti nzima ya data ya mafunzo kwa pembejeo ya mtandao, kuhesabu makosa kwa kila kitu. data ya mafunzo na uhesabu marekebisho muhimu ya mgawo wa mtandao (lakini usifanye marekebisho haya), na baada ya kuwasilisha data zote, hesabu kiasi katika urekebishaji wa kila mgawo wa mtandao (jumla ya gradients) na urekebishe mgawo "hatua moja" . Ni wazi, na seti kubwa ya data ya mafunzo, algorithm itafanya kazi polepole sana, kwa hivyo kwa mazoezi, mgawo wa mtandao mara nyingi hurekebishwa baada ya kila kipengele cha mafunzo, ambapo thamani ya gradient inakadiriwa na gradient ya kazi ya gharama, iliyohesabiwa kwa mafunzo moja tu. kipengele. Njia hii inaitwa kushuka kwa gradient ya stochastic au kushuka kwa gradient ya uendeshaji . Kushuka kwa gradient ya Stochastic ni aina ya makadirio ya stochastic. Nadharia ya makadirio ya stochastiki hutoa masharti ya muunganiko wa njia ya mteremko wa stochastic.

Viungo [ | ]

• J. Mathayo. Moduli ya Kushuka kwa Mteremko Mkali au Mbinu ya Gradient. (kiungo hakipatikani)

Fasihi [ | ]

• Akulich I.L. Programu ya hisabati katika mifano na matatizo. -M.: shule ya kuhitimu, 1986. - ukurasa wa 298-310.
• Gill F., Murray W., Wright M. Uboreshaji wa kivitendo = Uboreshaji wa Vitendo. - M.: Mir, 1985.
• Korshunov, M., Korshunov. Misingi ya Hisabati cybernetics. - M.: Energoatomizdat, 1972.
• Maksimov Yu., Fillipovskaya E. A. Algorithms ya kutatua shida za programu zisizo za mstari. - M.: MEPhI, 1982.
• Maximov Yu. Algorithms ya upangaji laini na wa kipekee. - M.: MEPhI, 1980.
• Korn G., Korn T. Kitabu cha hisabati kwa wanasayansi na wahandisi. - M.: Nauka, 1970. - P. 575-576.
• S. Yu. Gorodetsky, V. A. Grishagin. Upangaji usio wa mstari na uboreshaji wa hali nyingi. - Nizhny Novgorod: Nyumba ya uchapishaji Chuo Kikuu cha Nizhny Novgorod, 2007. - ukurasa wa 357-363.

Hatimaye, parameta m inaweza kuwekwa mara kwa mara katika marudio yote. Hata hivyo, lini maadili makubwa m mchakato wa utafutaji unaweza kutofautiana. Kwa njia nzuri Uchaguzi wa m inaweza kuwa uamuzi wake katika iteration ya kwanza kutoka hali ya extremum katika mwelekeo wa gradient. Katika marudio yanayofuata, m inabaki mara kwa mara. Hii hurahisisha mahesabu hata zaidi.

Kwa mfano, kwa kazi katika na makadirio ya upinde rangi imedhamiriwa na njia ya kushuka kwa kasi zaidi. Wacha tuchukue kigezo mara kwa mara kwa marudio yote.

Kokotoa viwianishi vya x (1):

Ili kuhesabu kuratibu za nukta x (2), tunapata makadirio ya gradient katika hatua x (1) : , kisha

na kadhalika.

Mlolongo huu pia hukutana.

Mbinu ya hatua ya gradient

Njia hii ilitengenezwa na wahandisi na inajumuisha ukweli kwamba hatua ya moja ya vigezo inachukuliwa mara kwa mara, na kwa vigezo vingine huchaguliwa kulingana na uwiano wa gradients ya pointi. Hivi ndivyo uso uliokithiri unavyopunguzwa, kwa sababu Muunganisho sio sawa kwa anuwai zote. Kwa hivyo, kwa kuchagua hatua tofauti za kuratibu, wanajaribu kufanya kiwango cha muunganisho kuwa sawa kwa anuwai zote.

Acha kazi inayoweza kutenganishwa na nukta ya awali itolewe . Wacha tuweke hatua ya mara kwa mara kando ya uratibu wa x 1, acha Dx 1 =0.2. Hatua kando ya uratibu wa x2 hupatikana kutoka kwa uwiano wa gradients na hatua.