A sztochasztikus approximáció konvergenciájáról
2019 június
ABSTRACT
A sztochasztikus approximáció (STA) egy rekurzív paraméterbecslő, a sztochasztikus folyamatok modellezésénél gyakran alkalmazott egyszerű heurisztikus algoritmus. A konvergencia sebessége 1/n szerű, n = 1,2,3,... .A STA rekurzív becslési struktúrája felismerhető a rekurzív legkisebb négyzetes, maximum-likelihood stb. algoritmusokban. Az algoritmus korlátozó feltételekkel gyorsítjuk. A dolgozatban a predikciós hibafolyamat elemzésén alapuló algoritmust, és a hibák előjelein alapuló konvergencia sebességet szabályozó algoritmust mutatunk be, amely a predikciós hibafolyamat zérus várható értékét és előjel szimmetriáját írja elő.
BEVEZETÉS
A sztochasztikus approximáció algoritmusa (STA) egy heurisztikus rekurzív paraméter becslő algoritmus, a matematikai modellezésnél gyakran alkalmazzuk. A predikciós hibafolyamat az output mért és az előző lépésben becsült értékének a különbsége. A becsült Θ paraméterekben lineáris modellek és skalár kimenet esetén, a modell mindig az yn = Θn T gn alakra hozható, n = 1,2,3,..., ahol yn jelöli az output n -edik időpontban jósolt értékét, tehát a predikciós hibafolyamat yn,mért -yn . gn -t az irodalomban a függvénykomponensek vektorának vagy gradiens vektornak nevezik, mert gn = δ yn / δ Θ. A T transzponálást jelöl. A becsülendő paraméter vektort rekurzíve úgy módosítjuk, hogy a módosítás irányát a gn-el jelölt gradiens vektor alapján számítjuk: Θn = Θn-1 + 1/n (yn,mért - yn) gn .
A predikciós hibafolyamat és az yn -el jelölt becslési folyamat ismert paraméterek eseté korrelálatlanok és a az STA legkisebb négyzetes értelemben optimális becslés, konvergenciája 1/n → 1/(n+ const.) helyettesítés esetén bizonyított. Megj.: exponenciális felejtés esetén (1 - 1/n) Θn + 1/n (yn,mért - yn) gn alakban számítható, ahol 1 - 1/n szokásos értéke 0.90 - 0.999. Az exponenciális felejtés jó kezdőértékek aktualizálására alkalmas algoritmus. Jó a kezdőérték, ha predikciós hibák kis mintára becsült számtani közepe nulla.
A becsült paramétervektor, egyben a gradiens vektor dimenziójának növelésével a becslés konvergenciája, azaz a tanulási arány gyorsan romlik, esetleg a hibafolyamat oszcillálva divergálhat is. Megj.: gradiens segédváltozó komponenseinek kollinearitásuk azt jelenti, hogy két vagy több függvénykomponens erősen korrelál egymással, ugyanazt a információt hordozzák, ami torzítja a becsléseket és rontja a modell prediktív képességét. A kollinearitás kezelésére számos technika áll rendelkezésre, például a változó kiválasztás vagy dimenzió csökkentési módszerek. Kezdő kutatóknál előfordul, hogy nincsenek kellő figyelemmel a bemenő jelek, a függvénykomponensek változékonyságára (= persistently exiting signs), ami a zérus várható értékű kimenet előjelváltásaival ellenőrizhető.
A sztochasztikus approximáció egy kb. 70 éves algoritmus család, sok gyorsított változata ismert (https://en.wikipedia.org/wiki/Stochastic_approximation). Itt a gradiens egy normalizált változata szerepel, ezért nem divergál a nagy gradiensű esetekben:
Θn = Θn-1 + 1/n (yn - yn,mért) (Σ gi2)-1/2 gn ,
feltéve, hogy gi komponensei nem egyenlőek nullával. (Könnyen átírható diagonális mátrix alakba).
Az algoritmus a gradiens nagy értékeire - a (Σ gi2)-1/2 , és i = 1,2,..., dim g = dim Θn) tényezők következtében- kevésbé érzékeny, mint az eredeti STA algoritmus. A kis gradiensű eset numerikusan egyszerűen kezelhető. Nagy gradiens esetén célszerű a gradiens komponenseket mozgó átlagokkal helyettesíteni.
A tanulási sebesség és a hibafolyamat konvergenciája
A továbbiakban a tanulási arányt és a hibafolyamatot vizsgáljuk. A hibafolyamat Θn eltérése a valódi értékétől, azaz a ΔΘnT gn. A hibafolyamat az ismeretlen ΔΘn -el lineárisan arányos. Ha 1/n gyorsabban tart nullához, mint ΔΘn , az torzított becslést okoz, ami a hibafolyamat tulajdonságaiból számított cn skalár szorzóval próbálunk elkerülni. Az 1/n skalár szorzó neve tanulási sebesség vagy arány (az angol terminológia szerint learning rate), O (1/n) szerint csökken, ahol O ordót jelöl. Az állítás visszacsatolt lineáris irányítási (closed-loop) rendszerekre is érvényes feltéve, hogy egy lépés késleltetés van a hurokban. A bizonyítás a becslési hibára felírt Steiner-formula alapján történhet (https://en.wikipedia.org/wiki/Bias_of_an_estimator). Csak szuboptimális STA algoritmusok léteznek, de a szuboptimális tanulást is optimális al-stratégiák alkotják. A hiányos a priori ismereteink miatt a szuboptimális STA-nál: a hibafolyamat 1/n szerű csökkenésével és nulla várható értékének biztosításával lehet elérni a konvergenciát.
Amennyiben 1/n -nél lényegesen gyorsabb a csökkenés, az le is állíthatja a rekurzív becslést, torzított becslést eredményez. Pl. ha jó kezdő érték meghatározásához minden lépésben külön iterációval közel nullázzuk a hibát, ekkor zajkövető becslést kapunk, (https://en.wikipedia.org/wiki/Bias%E2%80%93variance_tradeoff), mégis gyakran alkalmazott gyorsítás. A paraméter komponensek abszolút értékeihez viszonyítva nagy, de korlátos hibák esetén: a becslések oszcillálnak, majd divergálnak, ami a lépésnagyság mesterséges, legalább 1/n szerű csökkenésével megelőzhető. (https://pp.bme.hu/ee/article/view/4974, Bencsik, I. (1974) “CONVERGENCE RATE ACCELERATION OF SUCCESSIVE APPROXIMATION ALGORITHMS IN REAL-TIME CASE ”, Periodica Polytechnica Electrical Engineering (Archives), 18(1), pp. 99-103.) Gyakori eset, hogy kis torzított becslést elfogadunk. amivel gyorsul a konvergencia. Egy, a mérési zajjal kapcsolatos probléma: egy jel valódi értékének becslése ismert szórású független mérési zaj esetén. Pl. ha a jel mérési zajos fehér zaj lenne és a szórásnégyzete adott lenne, akkor a valódi érték becslése: a fehér zaj mért pillanatnyi értéke szorzandó a
(fehér zaj szórásnégyzete - a mérési zaj szórásnégyzete)/fehér zaj szórásnégyzete
hányadossal, a Kálmán-szűrő alapján (https://en.wikipedia.org/wiki/Kalman_filter).
A rendszer zajjal - kisebb részben a mérési zajjal- kapcsolatos probléma a becslések zaj-érzékenysége: a jó kezdőértékek becslésénél egy tanuló minta segít kezelni a problémát. (A Kálmán-szűrő alapján belátható, hogy a kimenet és a paraméterek legkisebb négyzetes értelemben valóban optimális becsléshez, az u.n. extended Kalman-filterhez, a fokszám és a rendszerzaj, azaz a fehér zaj szórásnégyzetének és a mérési zaj szórásnégyzetének ismerte is szükséges. A becslés ekkor egybe esik a Bayes becsléssel, és a MLH becsléssel.) A Kálmán-szűrő zajfolyamatai a feltételezések szerint zérus várható értékű független (azaz fehér) gaussi zajok, vagy zérus várható értékű egyenletes eloszlású zajok, ez utóbbi új felismerés.
A hibafolyamat zérus várható értékét , a szuboptimális konvergencia sebességet a lépés nagyságának speciális megválasztásával biztosítjuk: egy cn -el jelölt, minden lépésben újra számolt skalár szorzó alkalmas megválasztásával: nem csak azt követeljük meg, hogy a hibafolyamat 1/n szerűen csökkenjen, hanem azt is hogy a hibafolyamat előjele a lépések ≈50% -ában különbözzön.( Előjelpróba: Vincze István: Matematikai Statisztika, Műszaki Könyvkiadó, 1968, 160. old.) A tanulási arányt ekkor cn/n jellemzi. A bemenő és általában a jelek változékonysága (angol terminológia persistenly exciting) azért fontos, mert a jelek kellő változékonysága nélkül nem módosul becslés a szükséges mértékben. Ezt a változékonyságot részben biztosíthatja, hogy a lépésnagyság cn skalár szorzóját minden lépésben úgy számítjuk*, hogy a hiba - egy egységnyi skalár szorzóval tett próbalépés után- előjelet váltson és egyidejűleg 1/n szerűen csökkenjen abszolút értékben: ez az optimális tanulási sebesség STA algoritmusok esetén. A legmeredekebb esés módszerét ekkor a zérus várható értákű hibafolyamat előjelére is alkalmazzuk. A cn › 0 skalárral 1/n -él gyorsabb konvergencia is beállítható, de a gyorsabb tanulás ára a torzított becslés.
A ZÉRUS VÁRHATÓ ÉRTÉKŰ PREDIKCIÓS HIBA FOLYAMATRÓL
A becslési, a rendszer és a mérési zaj folyamatokról feltesszük, hogy nulla várható értékű, fehér Gauss-folyamatok és korrelálatlanok a vizsgált és modellezendő folyamattal. A feltételezett zaj modellek befolyásolják a modellezést. A predikciós hibafolyamat kiértékelésére egy rövid, az utolsó 20 elemet tartalmazó mintát fogunk használni. A hibák előjeleinek szimmetriáját tesztelve található egy olyan minden lépésben újra számított cn › 0 skalár, amellyel biztosítjuk, hogy a hiba abszolút értékben O(1/n) szerint csökkenjen és a hibák előjelei azonos számban forduljanak elő. Ez utóbbit egy indikátor változó segítségével ellenőrizzük: meghatározzuk az azonos előjelek számának várható értékét.
Állítás: Valamely b alapú számrendszerben, ha 1/b a számjegyek előfordulásának valószínűsége, jelölje P(X=k) egy k hosszúságú független kísérletekkel kapott tetszőleges mintázat valószínűségét megszámlálhatóan végtelen sokaság esetén. ( Pl. a pi szám bináris alakjának megszámlálható része alapján. A mintázat fogalma a jegyek különbözőségével kapcsolatos.) Ekkor általános b-re:
P(X=k) = p (1-p)k-1 = (b-1)/b 1/b k-1 = (b-1)/bk , for k = 1, 2, 3, ...,∞
ahol (b-1)/b a geometriai eloszlás paramétere, egyben a szinglik valószínűsége. Az X valószínűségi változó várható értéke b/(b-1), ami a b-1)/b paraméter reciproka, amikor az eloszlás entrópiája maximum az exponenciális eloszlás családon belül. Az X változó szórása b/(b-1)2 -al egyenlő. b=2 esetben a várható érték 2.
A szinglik nélküli sorozat várható érték (2b-1)/(b-1) = 3, ekkor k = 2,3,4,.. , -al egyenlő.
Véges, kmax nagyságú minta esetén a (b -1) Σk b-k valószínűségek összege:
(b -1) Σk b-k = 1- b-kmax ≈ 1/2, k = 2,3.., amit max 20 -nak választottunk.
Tehát a k = 2,3,4..sorozatok P(X=k) valószínűségeinek összege egy 20 elemet tartalmazó ablakban jó közelítéssel 1/2, és egyben a szinglik előfordulásának valószínűsége is 1/2 maximális entropia esetén. Az állítás alapján a 20 elemet tartalmazó ablakban a hibák előjeleinek előfordulási gyakoriságai értékelhetőek, és cn értékei számíthatóak az STA algoritmusban úgy, hogy az előjelek szimmetrikusan forduljanak elő. (Egy további lehetséges módja a lépésnagyságot módosító cn számításnak, hogy az yn,mért - yn hibafolyamat abszolút értékére előírjuk, hogy az 1/n és 1/n1/2 közötti intervallumban csökkenjen, és minden lépésben előjelet váltson.)
*
Egy elméleti kritérium. az yn,mért - yn hibafolyamat négyzetes várható értékre vonatkozó M(y2) = M2(y) + D2 (y) összefüggés alapján, feltéve, hogy M(y2) létezik:
M2(y) / M(y2) + D2 (y) / M(y2) = 1,
tehát D2 (y) / M(y2) ≤ 1. A D2 (y) / M(y2) relatív szórásnégyzet, értéke jól becsülhető, alkalmas legkisebb négyzetes mérőszám a becslések összehasonlítására. (https://en.wikipedia.org/wiki/Bias_of_an_estimator).
A D2 (y) / M(y2) arány, a relatív szórásnégyzet hasznos kritérium az azonos, nem nulla várható értékű becslések kiértékelésénél, mert a Csebisev egyenlőtlenségben (https://en.wikipedia.org/wiki/Chebyshev%27s_inequality) ε2 helyére ε2 M (y2) -t helyettesítve, az egyenlőtlenség jobb oldala D2 (y) / ε2 M(y2) alakú lesz:
P { | y - M (y)| ≤ ε M1/2 (y2) } ≤ ε-2 (1 - D2 (y) / M (y2)) .