Et lite mattespørsmål for spesielt interesserte

[Hr. Kules]

Det er 10 år siden sist jeg hadde statistikk på universitetet, så jeg er litt rusten.

Jeg har følgende oppgave:
Gitt en variabel, x ∈ [0,X).

Jeg skal så legge til normalfordelt støy med snitt 0, og varians σ²; dvs. z_t = N(0, σ²)

x_t+1 er da gitt ved x_t+1 = x_t + z_t

Hvordan kan jeg da forsikre meg om at svaret havner innen det definerte intervallet uten å la det gå på bekostning av fordelingen?

Er det nok å kassere og velge ny z_t dersom x_t+1 ∉ [0,X)? Jeg har på følelsen av at dette er korrekt, uten egentlig å kunne vise dette matematisk. (Er litt for rusten til å ta beviset på sparket.) Forklar gjerne evt. hvorfor ikke.

Eller er det andre fordelinger som er mer hensiktsmessig å bruke i slike intervaller? Jeg tar gjerne i mot lenker og henvisninger som kan forklare litt mer rundt fordelinger i intervaller.

[UpAndComming]

Du må vel ha noen betingelser her for å sikre deg det vel ? Har du skrevet opp alt du har av info ? Jeg føler at det er noe som mangler her.

For jeg antar at dette skal gjelde for alle mulig t ??

[Hr. Kules]

æøå
Mens jeg venter på jobb holder jeg på å programmere et c-bibliotek for "cartesian genetic programming" (CGP) og evolusjonsstrategi (ES.)

Den ES'en som gjerne brukes til CGP er en veldig simpel versjon av den opprinnelige ES-metoden. Problemet mitt er at jeg prøver å lage et ES-bibliotek som takler både den opprinnelige og simple versjonen, og det blir derfor litt utveksling av funksjonalitet mellom disse. Den simple ES'en opererer med heltall i gitte intervall, mens den opprinnelige opererer med relle tall i intervallet (-∞,∞). Videre er den simple versjonen basert på at x_t+1 blir trekt fra en uniform fordeling i et intervall med en gitt sannsynlighet ellers beholder den sin opprinnelige verdi, mens den opprinnelige versjonen baserer seg på at x_t+1 er summen av den opprinnelige verdien og en viss støy.

Det jeg vil ha, er den opprinnelige metoden med mulighet for å definere intervaller med gyldige verdier. Det er her problemet oppstår, siden jeg da ønsker en normalfordelt støy som ikke fører til at neste verdi havner utenfor det gitte intervallet. Det meste av betingelser velger jeg jo tross alt selv, men jeg vil jo gjerne at biblioteket skal kunne være tro mot de etablerte metodene.

t er gyldig for alle t ≥ 0. x₀ er vilkårlig valgt i det gitte untervallet.

[UpAndComming]

Men jeg kan ikke se at dette vil virke. Intervallet ditt er f.eks, [0, 9). Dersom vi antar x0 = 0, vil jo halvparten av tilfellene du trekker fra en normalfordeling med forventning 0 medføre at x1 er utenfor [0, 9).

Du kan jo selvsagt legge en betingelse på variansen din avhengig av avstanden fra grensene, men det er kanskje ikke meningen ?

Men det er klart, for t stor nok skal den alltid komme tilbake igjen i intervallet sitt, for det er jo på mange klassisk virrevandring det snakk om, bare med andre verdien enn {-1, 0, 1}.

Men det er sikkert mulig å legge på begrensninger på støyen din slik at du alltid vil være i det gitte intervallet, enten ved tilleggsligninger, grenseverdier eller som nevnt begrensninger på din sigma.

Definerer du dette som en klassisk Ohrnstein-Uhlenbeck prosess vil du oppnå det du ønsker.

Eller har jeg misforstått deg helt ?

[Hr. Kules]

Takker for svar.

Du har vel ikke en henvisning til bok/ artikler som gir en grei innføring i OU-prosesser? Jeg har tross alt bare 15 vekttall i matematikk.

[UpAndComming]

Du har i hvert fall "Stochastic differential Equations. An Introduction with aplications" av Bernt Øksendal. Kanskje litt vanskelig å ta med en gang dersom bakgrunnen din ikke er større, men denne vil gi deg det du trenger.

Men for å forklare litt kort, så er en OU-prosess en prosess definert som

dp(t) = k[m - p(t)]dt + s*dB(t), k og s konstanter

der B(t) er en standard Brownsk bevegelse. Løsningen av denne ligningen er jo ikke nødvendigvis opplagt rent analytisk om man ikke kan en del om dette fra før av, men med hjelp av en datamaskin kan du klare dette rimelig greit.

Som du ser vil leddet k[m - p(t)] representere drift i leddet. Samtidig kan du f.eks. definere :

s = S*[K - p(t)]

der S og K er to konstanter, og K f.eks. er din maksimale grense. Da er du sikret til enhver tid at støy opp mot grensen settes mer og mer lik 0; men også her vil du kunne oppleve at du kan gå over. Men nå blir problemet 0 selvsagt, men også dette kan du behandle med å f.eks. sliptte støyen i to forskjellige prosesser. Dette er greit å gjøre, dersom du lar disse to prossessene være uavhengige av hverandre når du trekker de.

Vet ikke om du ble noe særlig mye klokere av dette, men du vil finne en del rundt dette på nett også, i tillegg til boken jeg nevnte.

[Hr. Kules]

Ut i fra prislappen på boken, ser det ut til å være et nogenlunde overkommelig nivå på den. Det ser ut som om de har den inne på informatikkbiblioteket, så jeg får ta en tur dit og sjekke.

Jeg er ikke helt stø i matematikken, men som jeg skjønner det vil variansen bli mindre jo nærmere grenseverdien man kommer. Ved nærmere eftertanke er dette egentlig en situasjon jeg vil unngå. ES er en søkealgoritme, og variansen til støyen varierer efter hvor bra løsninger som den oppdager og hvor lenge den har søkt i et område uten å forbedre resultatet. Dersom støyen i utgangspunktet går mot null nær grensene, vil det vel gi en større sannsynlighet for at søket blir fanget i et lokalt optimum.

Det var derfor jeg tenkte at et gjentrekk av støyleddet vil gi den ønskede adferden. Da blir er fortsatt det neste trekket trukket fra en normalfordeling. Støyen vil få en viss forskyvning, men de relative sannsynlighetene for gitte trekk vil vel være de samme, sett bort fra de ugyldige verdiene. Jeg tenkte også på om jeg kunne implementere grensene som en ring (håper det var riktig benevning,) slik at x_t+1 = (x_t + z_t) (mod X), hvor X er den øvre grensen. Dette vil selvfølgelig kun virke for intervaller som er avgrenset i begge retninger, og ikke for f.eks. [0, ∞).

[UpAndComming]

Da skjønner jeg enda litt mer hvor du vil, men jeg TROR ikke dette er rett frem uansett hvordan du velger å løse det. Problemet med lokale optimum er jo et kjent problem når det kommer til stokastiske prosesser, og graden av løsbarhet er vel da rimelig avhengig av hvor kompleks problemstillingen din er.

Men du kan jo sjekke ut kapitellene om kontrollteori hos Øksendal, og se om du får noe ut av det.

[Hr. Kules]

Det skal jeg gjøre. Får ta turen innom Blindern i morgen og se om jeg finner boken der. Morsomt å lære noe nytt, pluss at jeg får frisket opp matematikken litt igjen.

Det som er fint med evolusjonære algoritmer, er at de ofte har en god middelvei mellom "exploration" og "exploitation" av søkerommet, noe som passer ganske mange problemer. Men også innen EA har det vært mye forskning og ad-hoc-metoder for å unngå såkalt "prematur konvergens," at algoritmen blir fanget i et lokalt optimum.