Pag-unawa sa Stochastic Average Gradient

Ang gradient descent ay ang pinakasikat na diskarte sa pag-optimize sa pagmomodelo ng machine learning (ML). Pinaliit ng algorithm ang error sa pagitan ng mga hinulaang halaga at ng ground truth. Dahil isinasaalang-alang ng pamamaraan ang bawat punto ng data upang maunawaan at mabawasan ang error, ang pagganap nito ay nakasalalay sa laki ng data ng pagsasanay. Ang mga diskarte tulad ng Stochastic Gradient Descent (SGD) ay idinisenyo upang mapabuti ang pagganap ng pagkalkula ngunit sa halaga ng katumpakan ng convergence.

Binabalanse ng Stochastic Average Gradient ang klasikong diskarte, na kilala bilang Full Gradient Descent at SGD, at nag-aalok ng parehong mga benepisyo. Ngunit bago natin magamit ang algorithm, kailangan muna nating maunawaan ang kahalagahan nito para sa pag-optimize ng modelo.

Pag-optimize ng Mga Layunin ng Machine Learning na may Gradient Descent

Ang bawat algorithm ng ML ay may nauugnay na function ng pagkawala na naglalayong bawasan o pagbutihin ang pagganap ng modelo. Sa matematika, ang pagkawala ay maaaring tukuyin bilang:

Ito ay simpleng pagkakaiba sa pagitan ng aktwal at ang hinulaang output, at ang pagliit sa pagkakaibang ito ay nangangahulugan na ang aming modelo ay lumalapit sa mga pangunahing halaga ng katotohanan.

Gumagamit ang minimization algorithm ng gradient descent para madaanan ang loss function at makahanap ng global minimum. Ang bawat hakbang sa pagtawid ay nagsasangkot ng pag-update ng mga timbang ng algorithm upang ma-optimize ang output.

Plain Gradient Descent

Ginagamit ng conventional gradient descent algorithm ang average ng lahat ng gradient na kinakalkula sa buong dataset. Ang lifecycle ng isang halimbawa ng pagsasanay ay ganito ang hitsura ng sumusunod:

Ang equation ng pag-update ng timbang ay ganito ang hitsura:

Kung saan W ay kumakatawan sa mga timbang ng modelo at dJ/dW ay ang derivative ng loss function na may kinalaman sa timbang ng modelo. Ang kumbensyonal na paraan ay may mataas na convergence rate ngunit nagiging computationally mahal kapag nakikitungo sa malalaking dataset na binubuo ng milyun-milyong data point.

Stochastic Gradient Descent (SGD)

Ang pamamaraan ng SGD ay nananatiling pareho sa plain GD, ngunit sa halip na gamitin ang buong dataset para kalkulahin ang mga gradient, gumagamit ito ng maliit na batch mula sa mga input. Ang pamamaraan ay higit na mabisa ngunit maaaring umikot nang labis sa pandaigdigang minima dahil ang bawat pag-ulit ay gumagamit lamang ng isang bahagi ng data para sa pag-aaral.

Stochastic Average Gradient

Ang Stochastic Average Gradient (SAG) na diskarte ay ipinakilala bilang isang gitnang lupa sa pagitan ng GD at SGD. Pumipili ito ng random na data point at ina-update ang value nito batay sa gradient sa puntong iyon at isang weighted average ng mga nakaraang gradient na nakaimbak para sa partikular na data point na iyon.

Katulad ng SGD, inemodelo ng SAG ang bawat problema bilang isang finite sum of convex, differentiable functions. Sa anumang naibigay na pag-ulit, ginagamit nito ang kasalukuyang mga gradient at ang average ng mga nakaraang gradient para sa pag-update ng timbang. Ang equation ay tumatagal ng sumusunod na anyo:

Rate ng Convergence

Sa pagitan ng dalawang sikat na algorithm, full gradient (FG) at stochastic gradient descent (SGD), ang FG algorithm ay may mas mahusay na convergence rate dahil ginagamit nito ang buong set ng data sa bawat pag-ulit para sa pagkalkula.

Bagama't may istraktura ang SAG na katulad ng SGD, ang rate ng convergence nito ay maihahambing at minsan ay mas mahusay kaysa sa buong gradient na diskarte. Ang talahanayan 1 sa ibaba ay nagbubuod ng mga resulta mula sa mga eksperimento ng Schmidt et. al .

Karagdagang Pagbabago

Sa kabila ng kamangha-manghang pagganap nito, ilang mga pagbabago ang iminungkahi sa orihinal na SGD algorithm upang makatulong na mapabuti ang pagganap.

• Muling pagtimbang sa Maagang Pag-ulit: Ang SAG convergence ay nananatiling mabagal sa unang ilang mga pag-ulit dahil ang algorithm ay nag-normalize ng direksyon sa n (kabuuang bilang ng mga punto ng data). Nagbibigay ito ng hindi tumpak na pagtatantya dahil hindi pa nakikita ng algorithm ang maraming punto ng data. Ang pagbabago ay nagmumungkahi ng pag-normalize ng m sa halip na n, kung saan ang m ay ang bilang ng mga punto ng data na nakikita nang hindi bababa sa isang beses hanggang sa partikular na pag-ulit.
• Mini-batch: Gumagamit ang Stochastic Gradient approach ng mga mini-batch para magproseso ng maraming data point nang sabay-sabay. Ang parehong diskarte ay maaaring ilapat sa SAG. Nagbibigay-daan ito para sa vectorization at parallelization para sa pinahusay na kahusayan ng computer. Binabawasan din nito ang pagkarga ng memorya, isang kilalang hamon para sa SAG algorithm.
• Pag-eksperimento sa Step-Size: Ang laki ng hakbang na binanggit kanina (116L) ay nagbibigay ng mga kamangha-manghang resulta, ngunit ang mga may-akda ay nag-eksperimento pa sa pamamagitan ng paggamit sa laki ng hakbang na 1L. Ang huli ay nagbigay ng mas mahusay na convergence. Gayunpaman, ang mga may-akda ay hindi nakapagpakita ng isang pormal na pagsusuri ng mga pinabuting resulta. Napagpasyahan nila na ang laki ng hakbang ay dapat na eksperimento upang mahanap ang pinakamainam para sa partikular na problema.

Pangwakas na Kaisipan

Ang gradient descent ay isang tanyag na pag-optimize na ginagamit para sa paghahanap ng pandaigdigang minima ng mga ibinigay na layuning function. Ginagamit ng algorithm ang gradient ng layunin ng function upang lampasan ang slope ng function hanggang sa maabot nito ang pinakamababang punto.

Ang Full Gradient Descent (FG) at Stochastic Gradient Descent (SGD) ay dalawang sikat na variation ng algorithm. Ginagamit ng FG ang buong dataset sa bawat pag-ulit at nagbibigay ng mataas na convergence rate sa mataas na gastos sa pag-compute. Sa bawat pag-ulit, gumagamit ang SGD ng subset ng data para patakbuhin ang algorithm. Ito ay mas mahusay ngunit may isang hindi tiyak na tagpo.

Ang Stochastic Average Gradient (SAG) ay isa pang variation na nagbibigay ng mga benepisyo ng parehong nakaraang algorithm. Ginagamit nito ang average ng mga nakaraang gradient at isang subset ng dataset para magbigay ng mataas na convergence rate na may mababang computation. Ang algorithm ay maaaring higit pang mabago upang mapabuti ang kahusayan nito gamit ang vectorization at mini-batch.