Algoritma Numerike

Ne focuse vëmendjen tonë në këtë pjesë të algoritma te përdor 'gradient metodës', pasi që këto janë të algoritma te të përdoren në econometrics. Pra, le të fillojë me një shpjegim të përgjithshme atë që po ndodh në qoftë se ne përdorim një algorithm tillë për të gjetur një parametër kombinim i cili maximizes një kriter të funksionojë. Çdo algorithm nevojat disa në shkallë të parë për fillimin e vlerave? dhe ajo është e madhe për të zgjedhur të përdorin duke filluar nga vlera shumë të afërt me optimale dhe, nëse është e mundur është larg nga të papërcaktuar pjesë e një kriter të funksionojë për të garantuar sukses të madh të optimization. Pastaj e algorithm fillon të funksionojë për të vlerësuar në këtë pikë dhe atë parametër të updates parametër vector pas ekuacion ? s = 1? s + Asgs, (42) ku? s është parametër pika në të cilën është vetëm funksionin vlerësohet,? s 1 është parametër vector përdoren për vlerësim në hapin tjetër s 1, gs = @ QN (?) @? ? s është i pjerrët vector vlerësohen në pikën? s dhe AK × Si është në varësi të matricës k? s (kështu që është gjithmonë vlerësohen në parametrat hap nga s) .10 Tani, algoritma te ndryshme gradient të përdorin metoda të ndryshme matricat Si, e cila mund të shihet si koeficient matricat si ata 'peshë' gradient të vlerësohen në një farë parametër kombinim. Matricat e pronës duhet të kenë të jetë pozitiv për të caktuar për Arsyeja e mëposhtme: kriter të vlerësohen në funksion një hap 1 s do të jenë më të larta në vlerë vlerësohet se në atë parametër në vektor hap s; se është zyrtarisht QN (? s +1)> QN (? s). Kjo mund të shpjegohet më mirë duke konsideruar Taylor për zgjerimin QN (? S +1) rreth vlera QN (? s): QN (? S +1) = QN (? S) + g0s (? S 1 -? S) + R QN (? S +1) - QN (? S) = g0s (? S + Asgs -? S) + R QN (? S +1) - QN (? S) = g0sAsg (Z)> 0 nëse Pos. def. + R. (43) R Këtu është vetëm një term me pjesën tjetër të papërfillshme gabim. I matricës Si duhet të zgjidhet vetëm në një mënyrë të drejtë, si në qoftë se ajo është shumë e vogël e algorithm është tepër i ngadalshëm (si atëherë gradient ponderuar është shumë më pak) dhe në qoftë se ajo është shumë e madhe e algorithm do ia kaloj optimale dhe ndoshta do të kaloni nëpër vlerë optimale pa converging. Ky fakt jep të rritet në një pyetje tjetër. Në pikën e cila do të bëjë të algorithm ndalesa? The algorithm ndalesa në qoftë se ajo ka gjetur një opimum, por kjo është si analytically unfeasible, ajo vetëm approximates vlera dhe ndalesa në qoftë se është "afër për 'të optimale. Nuk mund të jenë të shënuara disa rregulla të cilat janë zbatuar në pothuajse çdo algorithm: algorithm e ka arritur konvergjencë nëse 1. relative të ndryshojë në funksion QN kriter është shumë e vogël dhe 2. ndryshimin e pjerrët në krahasim me pëlhurë kërpi për çanta është shumë e vogël dhe 3. relative ndryshim i parameter vektor është shumë e vogël. Një vlerë konservatore për konvergjencës është 10-6. Për të shmangur një pushim i kompjuterit në qoftë se nuk algorithm konvergjoj normalisht është dhënë një numër maksimal të iterations dhe nëse ky numër i hapave të arritur algorithm ndalesa dhe i jep një porosi se konvergjencės nuk ka të arrihet.
Le të marrë në konsideratë informatikë e pjerrët e cila është duke u përdorur për një algorithm optimization duke përdorur metodën e gradient. I pjerrët është një drejtim në të cilin të pjesshme derivateve në respekt të çdo parametër janë bërë pirg. Si zakonisht e derivateve janë gjithashtu nuk analytically llogaritshëm, numerike approximations janë përdorur. Kjo bëhet duke përdorur formulën e mëposhtme: ? QN (? S) ?? j = QN (? S + Hej) - QN (? S - Hej) 2h . (44) Këtu? J është komponent i jth parameter vektor (dmth. e jth parametër i tona kriter funksion), h është vend i vogël pozitiv scalar dhe ej është një vektor me unitet në jth komponent dhe të gjitha elementet e mbetur zero. Kjo do të thotë për të rrjedhura prej jth, e algorithm computes ndryshimin në një kriter të funksionojë në qoftë se të bëjmë një hap mjaft i vogël larg jth parametër në vlerë? s. Si duam jo vetëm e konsiderojnë pozitiv drejtime por edhe ne drejtime negative të marrë diferencën e një kriter për funksionet parametër vlerat në të dyja drejtimet (më tej këtë përafrimin e bën më të mirë si një alternativë). Kjo është bërë për të gjitha parametrave ne? S dhe më pas ne e dimë që nga matematika, se kjo vector pikë në hapësirën e parametrave në drejtim të ardhura më të larta të kriter funksion (p.sh. në rast se ne të ndryshojë në të gjitha parametrat? s në drejtim të dhënë nga gradient, kriteri funksion do të rritet) .11 Nëse ne e konsiderojnë (44), shprehje na tregon se ne duhet të vlerësojë të gjithë i prejardhur approximations k parametrave dhe për secilin nga dy herë si N vërejtje ne kemi dy kriter në funksion të vlerave të enumerator. Më tutje, në çdo hap të gradient ka të llogaritet përsëri, e cila do të thotë që ne duhet të bëj llogaritje e approximations për hapat S 2 k N S. Nëse ne i përdorim në vend të kësaj analitike derivateve vetëm N k S computations mbeten dhe përveç kësaj vlera e saktë që do të jetë i prejardhur dhe jo një afrimit. Ne do të vijnë në këtë pikë më vonë në qoftë se ne konsiderojmë tonë optimization problemin në dorë. Tani le të konsiderojnë disa algoritma te posaçme. 7.1.1 Të BHHH-algorithm Kjo ishte zhvilluar nga algorithm Berndt, Hall, Hall dhe Hausman në 1974,12 Siç u përmend më lart, algoritma te ndryshme gradient përdorin metoda të ndryshme dhe matricat Si të përdor BHHH e mëposhtme: Si =-H-1 BHHH; s, (45) ku - HBHHH; s = -- 1 N XI N = 1 @ Qi (?) ? @ Qi (?) ? 0 ? S, (46) dhe QN (?) = XI N = 1 Qi (?). (47) 11It duhet të jetë e qartë se h duhet të jenë shumë të vogla si @ QN (? S) @? j = Limh! 0 ? QN (? S) ?? j. 12For më shumë informacion shih Fletçer (1981).
Kjo është e BHHH përdor anasjellë e matricës approximated pëlhurë kërpi për çanta negative nga ana e jashtme e produktit e gradient.13 I përdorimit të afrimit këtë metodë mund të jetë pranuar nga konsideron se në rrethanat e ML vlerësim. Në ML QN (?) = PN i = 1 log (fi (?)) dhe të matricës pëlhurë kërpi për çanta nuk është asgjë tjetër por negative anasjellë e informacionit matricës I (?) = E-h @ 2LN (?) @? @? 0 i. Si është e anasjellë e matricës ajo mban informacion: - H (?) = E? @ 2LN (?) @? @? 0? E = "N = 1 XI @ Log (fi (?)) @? XI N = 1 @ Log (fi (?)) @? 0 # i.i.d. = XI N = 1 E? @ Log (fi (?)) @? @ Log (fi (?)) @? 0? . (48) Tani, interchanging shpresa e saj nga sample ekuivalente të kemi (46). Pra, e intuitë prapa BHHH mund të shihet nga rishqyrtimin (42). Për thjeshtim ne supozojmë se ne kemi vetëm një parametër. Pastaj, atë parametër i hap s + 1 është parametër i hap aktuale s shtoi nga e para të rrjedhura prej herë negative inversed dytë. Kjo do të thotë nëse ne jemi larg nga e optimale do të jetë shumë i pjerrët lartë dhe i dyti i prejardhur, matjen e grafik e kriter të funksionojë në pikë? s normalisht është shumë i ulët. Pra tep të ardhshëm do të jetë e gjerë. Nëse ne jemi në vend të ngushtë në të optimale, ndryshimi do të jetë i vogël dhe negative të dytë do të jetë i madh i prejardhur (për një maksimum) kështu që ne kemi marrë një hap tjetër shumë i vogël. Ne mund të shohim se i anasjellë pëlhurë kërpi për çanta Matrica është një metodë e përshtatshme për kompensim të pjerrët në ripërtëritjen funksion (42). 7.1.2 Të Levenberg-Marquardt algorithm Algorithm Kjo është një metodë e cila përmirëson BHHH mëtejshëm. Ai përdor të barabartë me të BHHH negative të pëlhurë kërpi për çanta, por shton ai që ka në disa vlera të mëtejshëm: ? s = 1? s + (+ Hs-ci) 1gs-c> 0. (49) Kjo ka një arsye të cilat mund të shpjegohet me konsideron invertion ofthe pëlhurë kërpi për çanta matricës. Nëse pëlhurë kërpi për çanta matricës është gati njëjës kjo mund të jetë fakti se një afrimit mund të mos jenë të përmbysur. Për ta bërë një matricë nonsingular vlerë është shtuar në çdo diagonale dhe element nga nonsingularity që mund të arrihet si tani ajo është më pak e mundshme që e KOLONAT e matricës rezultuar janë linearly varur. Si e Levenberg-Marquardt algorithm është më e fuqishme se është përdorur edhe në EViews gjasat për optimization e funksioneve.