Glidande Medelvärde Online Algoritm

Jag vill implementera en iterativ algoritm, som beräknar vägt genomsnitt. Den specifika viktlagstiftningen spelar ingen roll, men den borde vara nära 1 för de nyaste värdena och nära 0 till de äldsta. Algoritmen ska vara iterativ. Dvs det bör inte komma ihåg alla tidigare värden. Det borde bara veta ett nyaste värde och någon aggregerande information om tidigare, som tidigare värden av medelvärdet, summan, räkningen etc. Till exempel kan följande algoritm vara: Det kommer att ge exponentiell minskande vikt, vilket kanske inte är bra. Är det möjligt att få steg minskande vikt eller något Kraven på vägningslag är följande: 1) Vikten minskar till förflutna 2) Jag har viss genomsnittlig eller karakteristisk längd så att värden äldre denna längd är betydligt mindre än nyare 3) Jag bör kunna ställa in denna längd jag behöver följande. Antag att vi är värden, där v1 är den första. Antag också att wi är vikter. Men w0 är senast. Så efter det första värdet kom jag till första genomsnittet Efter det andra värdet v2 kom, borde jag ha genomsnittet Med nästa värde borde jag ha Obs, den viktprofilen rör sig med mig medan jag flyttar längs värdesekvensen. Dvs. varje värde har inte sin egen vikt hela tiden. Mitt mål är att få denna vikt lägre medan man går förbi. Gt Men min uppgift är att ha omräknat genomsnittsvärde varje gång nytt värde kommer att ha gamla värden reweighted. OP Din uppgift är nästan alltid omöjlig, även med exceptionellt enkla viktningsplaner. Du ber att, med O (1) minne, ge medelvärden med ett ändrat viktningsschema. Till exempel, när nya värden skickas in, för vissa nästan vildväxande vikter sekvens. Detta är omöjligt på grund av injicerbarhet. När du slår samman siffrorna ihop förlorar du en enorm mängd information. Till exempel, även om du hade vektvektorn. Du kunde inte återställa originalvärdesvektorn, eller vice versa. Det finns bara två fall som jag kan tänka på var du kunde komma undan med detta: Konstanta vikter som 2,2,2. 2: det här motsvarar en online-algoritm, som du inte vill ha eftersom de gamla värdena inte reweightes. De relativa vikterna av tidigare svar ändras inte. Till exempel kan du göra vikter på 8,4,2,1. Och lägg till i ett nytt element med godtycklig vikt som. 1. men du måste öka allt tidigare med samma multiplikativa faktor, som 16,8,4,21. Således lägger du till en ny godtycklig vikt vid varje steg och en ny godtycklig omkalkning av det förflutna, så du har 2 frihetsgrader (endast 1 om du behöver behålla din punktprodukt normaliserad). De viktvektorer du får kommer att se ut: Således kan ett viktningsschema som du ser ut så fungera (om du inte behöver hålla saken normaliserad med summan av vikter, då måste du sedan dela det nya genomsnittet av det nya Summan, som du kan beräkna genom att bara behålla O (1) minne). Merligen multiplicera det föregående genomsnittet av de nya s (vilket implicit distribuerar över punktprodukten till vikterna) och tack på den nya wnewValue. Svarade mar 29 12 på 21:27 Här antar du att vikterna ska summeras till 1. Så länge du kan skapa en relativ vikt utan att den ändras i framtiden, kan du sluta med en lösning som efterliknar detta beteende. Det är, anta att du definierade dina vikter som en sekvens och definierade inmatningen som sekvens. Tänk på formuläret: summa (s0i0 s1i1 s2i2. Snin) summa (s0 s1 s2. Sn). Observera att det är triviellt möjligt att beräkna detta inkrementellt med ett par aggregeringsräknare: Naturligtvis beräknar viWeightFromCounter () i det här fallet inte att generera vikter som summan till en - tricket här är att vi är genomsnittliga genom att dividera med summan av vikterna Så att i slutändan tycks vikterna nästan vara summa. Det verkliga tricket är hur du gör calculateWeightFromCounter (). Du kan helt enkelt återvända räknaren själv, till exempel, notera att det sista viktiga numret inte skulle vara nära summan av räknarna nödvändigtvis, så du kanske inte hamnar med de exakta egenskaperna du vill ha. (Det är svårt att säga eftersom du, som sagt, har lämnat ett ganska öppet problem.) Svarat mar 28 12 kl 21:45 Problemet är att vikterna förändras med varje nytt värde. I ditt fall är de inte det. ndash Suzan Cioc Mar 29 12 kl 14:43 De faktiska använda vikterna förändras med varje nytt värde - kvoten kvot delas med ett successivt större antal, vilket gör att de faktiska använda vikterna alltid summeras till 1. ndash Kaganar mar 29 12 klockan 14:45 Det här är för långt att skriva in en kommentar, men det kan vara användbart att veta. Antag att du har: w0vn. Wnv0 (väl kalla det här w0..nvn..0 för korta) Sedan är nästa steg: w0vn1. Wn1v0 (och detta är w0..n1vn1..0 för kort) Det betyder att vi behöver ett sätt att beräkna w1..n1vn..0 från w0..nvn..0. Det är säkert möjligt att vn..0 är 0. 0, z, 0. 0 där z är på någon plats x. Om vi ​​inte har någon extra lagring, då f (zw (x)) zw (x 1) där w (x) är vikten för plats x. Omordna ekvationen, w (x 1) f (zw (x)) z. Tja, w (x 1) är bättre konstant för en konstant x, så f (zw (x)) z är bättre konstant. Därför måste f föra z propagera - det vill säga f (zw (x)) zf (w (x)). Men här har vi igen ett problem. Observera att om z (vilket kan vara vilket som helst nummer) kan sprida sig via f. då kan w (x) säkert. Så f (zw (x)) w (x) f (z). Således f (w (x)) w (x) f (z). Men för en konstant x. W (x) är konstant, och därmed är f (w (x)) bättre också konstant. W (x) är konstant, så f (z) är bättre konstant så att w (x) f (z) är konstant. Således är f (w (x)) w (x) c där c är en konstant. Så, f (x) cx där c är en konstant när x är ett viktvärde. Det vill säga varje vikt är en multipel av det föregående. Vikten tar sålunda formen w (x) mbx. Observera att detta förutsätter att den enda informationen f har är det sista aggregerade värdet. Observera att du vid något tillfälle kommer att reduceras till detta fall om du inte är villig att lagra en icke-konstant mängd data som representerar din inmatning. Du kan inte representera en oändlig längdvektor av reella tal med ett reellt tal, men du kan approximera dem på något sätt i en konstant, ändlig mängd lagring. Men detta skulle bara vara en approximation. Även om jag inte har bevisat det på ett strikt sätt, är det min slutsats att det du vill ha är omöjligt att göra med en hög grad av precision, men du kan kanske använda log (n) - utrymme (vilket också kan vara O (1) för många praktiska tillämpningar) för att skapa en kvalitativ approximation. Du kan kanske använda ännu mindre. Svarade mar 29 12 kl 23:01 Jag försökte praktiskt taget koda något (i Java). Som sagt har målet inte uppnåtts. Du kan bara räkna medeltal från ett antal senast bortkomna värden. Om du inte behöver vara exakt kan du approximera de äldre värdena. Jag försökte göra det genom att komma ihåg de senaste 5 värderingarna exakt och äldre värden endast SUMmed av 5 värden, kom ihåg de senaste 5 SUM. Då är komplexiteten O (2n) för att komma ihåg de senaste nnn-värdena. Detta är en mycket grov approximation. Du kan ändra de senaste valerna och lasAggregatedSums array storlekarna som du vill. Se den här ascii-art-bilden som försöker visa en graf över de senaste värdena, vilket visar att de första kolumnerna (äldre data) kommer ihågs som aggregerat värde (inte individuellt) och endast de första 5 värdena kommer ihåg individuellt. Utmaning 1. Mitt exempel räknar inte vikter, men jag tror att det inte borde vara problem för dig att lägga till vikter för de senasteAggregatedSummen på lämpligt sätt - det enda problemet är att om du vill ha lägre vikter för äldre värden, skulle det vara svårare, eftersom matrisen roterar, så Det är inte lätt att veta vilken vikt för vilken medlem i gruppen. Kanske kan du modifiera algoritmen för att alltid flytta värden i matrisen istället för att rotera. Då lägger vikter inte vara ett problem. Utmaning 2. Arrayerna initialiseras med 0 värden, och dessa värden räknar med i genomsnitt från början, även när vi inte får tillräckligt med värden. Om du kör algoritmen länge, stör du förmodligen inte att den lär dig någon gång i början. Om du gör det kan du skicka en ändring -) svarat Jan 21 14 kl 15:59 Ditt svar 2017 Stack Exchange, IncA Närmare titt på Advanced CODAS Moving Average Algorithm Mångsidigt glidande medelvärde i Advanced CODAS-algoritmen filtrerar vågformstörningar, extraktmedel och eliminerar baslinjedrift. Det rörliga genomsnittet är en enkel matematisk teknik som används för att eliminera avvikelser och avslöja den verkliga trenden i en samling datapunkter. Du kanske är bekant med det från medelvärde bullriga data i ett freshman-fysikprov eller från att spåra värdet av en investering. Du kanske inte vet att det rörliga genomsnittsvärdet också är en prototyp av det ändliga impulsresponsfiltret, den vanligaste typen av filter som används i datorbaserad instrumentering. I fall där en given vågform är störd med brus, där ett medel måste extraheras från en periodisk signal eller där en långsamt drivande baslinje behöver elimineras från en högre frekvenssignal, kan ett glidande medelfilter appliceras för att uppnå önskat resultat. Den flytta genomsnittliga algoritmen för Advanced CODAS erbjuder denna typ av vågformsfiltreringsprestanda. Advanced CODAS är ett analyspaket som fungerar på befintliga vågformatfiler skapade av WinDaq eller andra generationens WinDaq-datainsamlingspaket. Förutom den rörliga genomsnittsalgoritmen innehåller Advanced CODAS även en rapportgenerator och programrutiner för vågformsintegration, differentiering, topp - och dalfångande, rätning och aritmetiska operationer. Flytta genomsnittlig filterteori DATAQ Instruments rörlig medelalgoritm möjliggör stor flexibilitet vid vågformsfiltrering. Den kan användas som ett lågpassfilter för att dämpa bruset som är inneboende i många typer av vågformer, eller som ett högpassfilter för att eliminera en drivande baslinje från en högre frekvenssignal. Förfarandet som används av algoritmen för att bestämma mängden filtrering innebär användning av en utjämningsfaktor. Denna utjämningsfaktor, som styrs av dig via mjukvaran, kan ökas eller minskas för att ange antalet faktiska vågformsdatapunkter eller prover som det rörliga genomsnittet kommer att spänna över. Vilken periodisk vågform som helst kan anses vara en lång sträng eller samling av datapunkter. Algoritmen åstadkommer ett glidande medelvärde genom att ta två eller flera av dessa datapunkter från den förvärvade vågformen, addera dem, dividera deras summa med det totala antalet datapunkter som adderas, ersätta den första datapunkten för vågformen med det genomsnittliga justerade beräkningen, och Upprepa stegen med andra, tredje och så vidare datapunkter tills slutet av data uppnås. Resultatet är en andra eller genererad vågform bestående av den genomsnittliga data och med samma antal punkter som den ursprungliga vågformen. Figur 1 8212 Varje periodisk vågform kan ses som en lång sträng eller samling av datapunkter. I ovanstående illustration representeras i följd vågformsdatapunkter av quotyquot för att illustrera hur det rörliga genomsnittet beräknas. I detta fall användes en utjämningsfaktor på tre, vilket innebär att tre på varandra följande datapunkter från den ursprungliga vågformen läggs till, deras summa dividerat med tre, och sedan är denna kvot plottad som den första datapunkten för en genererad vågform. Processen upprepar sig med den andra, tredje och så vidare datapunkterna i den ursprungliga vågformen tills slutet av data uppnås. En speciell quotfeatheringquot-teknik är genomsnittlig början och slutpunkten för den ursprungliga vågformen för att säkerställa att den genererade vågformen innehåller samma antal datapunkter som originalet. Figur 1 illustrerar hur den glidande medelalgoritmen appliceras på vågformade datapunkter (som representeras av y). Illustrationen har en utjämningsfaktor på 3, vilket innebär att medelvärdet (representerat av a) kommer att beräknas över 3 på varandra följande vågformdata. Observera överlappningen som finns i de rörliga medelberäkningarna. Det är denna överlappande teknik, tillsammans med en särskild start - och slutpunktsbehandling som genererar samma antal datapunkter i den genomsnittliga vågformen som existerade i originalet. Hur algoritmen beräknar ett glidande medelvärde förtjänar en närmare titt och kan illustreras med ett exempel. Säg att vi har varit på en diet i två veckor och vi vill beräkna vår genomsnittliga vikt under de senaste 7 dagarna. Vi skulle summera vår vikt på dag 7 med vår vikt på dagarna 8, 9, 10, 11, 12 och 13 och multiplicera sedan med 17. För att formalisera processen kan detta uttryckas som: a (7) 17 (y 7) y (8) y (9). Y (13)) Denna ekvation kan vidare generaliseras. Det rörliga genomsnittet för en vågform kan beräknas med: Var: ett medelvärde n datapunktsläge s utjämningsfaktor y faktiskt datapunktvärde Figur 2 8212 Vågformen för belastningscellens utgång visas ursprungligt och ofiltrerat i toppkanalen och som en 11-punkts Flytta medelvärdet vågform i bottenkanalen. Bullret som uppstod på den ursprungliga vågformen berodde på de intensiva vibrationer som pressen skapade under förpackningsoperationen. Nyckeln till denna flexibilitet i algoritmer är dess brett utbud av utjämnade utjämningsfaktorer (från 2 till 1000). Utjämningsfaktorn bestämmer hur många faktiska datapunkter eller prover som ska beräknas. Att ange en positiv utjämningsfaktor simulerar ett lågpassfilter medan specificering av en negativ utjämningsfaktor simulerar ett högpassfilter. Med tanke på det absoluta värdet av utjämningsfaktorn gäller högre värden för större utjämningsbegränsningar på den resulterande vågformen och omvänt gäller lägre värden mindre utjämning. Med tillämpningen av den korrekta utjämningsfaktorn kan algoritmen också användas för att extrahera medelvärdet av en given periodisk vågform. En högre positiv utjämningsfaktor används vanligtvis för att generera medelvärdesvågformvärden. Tillämpning av den rörliga medelalgoritmen Ett framträdande inslag i den glidande medelalgoritmen är att det kan appliceras många gånger till samma vågform om det behövs för att få önskat filtreringsresultat. Vågformsfiltrering är en mycket subjektiv övning. Vad som kan vara en ordentligt filtrerad vågform till en användare kan vara oacceptabelt bullrigt mot en annan. Bara du kan bedöma om antalet genomsnittliga poäng som valts var för högt, för lågt eller bara rätt. Flexibiliteten i algoritmen gör att du kan justera utjämningsfaktorn och göra ett annat pass genom algoritmen när tillfredsställande resultat inte uppnås med det ursprungliga försöket. Ansökan och förmågan hos den glidande medelalgoritmen kan illustreras bäst av följande exempel. Figur 3 8212 EKG-vågformen visades original och ofiltrerad i toppkanalen och som en 97-punkts rörlig medelvärdesvågform i bottenkanalen. Observera frånvaron av baslinjedrift i bottenkanalen. Båda vågformerna visas i komprimerat tillstånd för presentation. En brusreduktionsansökan I fall där en given vågform är störd med brus kan det glidande medelfiltret appliceras för att undertrycka bruset och ge en tydligare bild av vågformen. En avancerad CODAS-kund använde till exempel en press och en lastcell i en förpackningsoperation. Deras produkt skulle komprimeras till en förutbestämd nivå (övervakad av lastcellen) för att minska storleken på det förpackning som krävs för att innehålla produkten. Av kvalitetsskäl beslutade de att övervaka pressoperationen med instrumentation. Ett oväntat problem uppstod när de började se realtidsladdningscellutgången. Eftersom pressmaskinen vibrerades avsevärt under drift var belastningscellens utgångsvågform svår att skilja eftersom den innehöll en stor mängd brus på grund av vibrationen som visas i toppkanalen i figur 2. Detta brus eliminerades genom att generera en 11-punkts rörlig medelkanal som visas i bottenkanalen i Figur 2. Resultatet var en mycket tydligare bild av belastningscellerna. En applikation för att eliminera baslinjedrift I de fall då en långsamt drivande baslinje måste avlägsnas från en högre frekvenssignal, kan det glidande medelfiltret appliceras för att eliminera drivlinjen. Exempelvis uppvisar en EKG-vågform vanligen en viss grad av baslinjevandring, vilket kan ses i toppkanalen i figur 3. Denna baslinjedrift kan elimineras utan att förändra eller störa karaktären hos vågformen som visas i bottenkanalen i Figur 3. Detta åstadkoms genom att man tillämpar en lämplig utjämningsfaktor för negativ värde under den glidande medelberäkningen. Den lämpliga utjämningsfaktorn bestäms genom att dela en vågformsperiod (i sekunder) av kanalintervallintervallet. Kanalprovintervallet är helt enkelt den ömsesidiga av kanalens samplingsfrekvens och visas bekvämt på den glidande genomsnittliga verktygsmenyn. Vågformsperioden bestäms enkelt från bildskärmen genom att placera markören på en lämplig punkt på vågformen, ställa in en tidsmarkör och sedan flytta markören en fullständig cykel bort från den visade tidsmarkören. Tidsskillnaden mellan markör och tidmarkör är en vågformsperiod och visas längst ner på skärmen om några sekunder. I vårt EKG-exempel hade vågformen ett kanalprovintervall på 0,004 sekunder (erhållet från den glidande genomsnittliga användarmenyn) och en vågformsperiod uppmättes till spänningen 0,388 sekunder. Att dela upp vågformsperioden med kanalintervallintervallet gav oss en utjämningsfaktor på 97. Eftersom det är baslinjedriften som vi är intresserade av att eliminera tillämpade vi en negativ utjämningsfaktor (-97) på den glidande medelalgoritmen. Detta subtraherade i själva verket det rörliga genomsnittliga resultatet från den ursprungliga vågformsignalen, vilket eliminerade baslinjedriften utan störande vågformsinformation. Andra vågformsrörande genomsnittsproblem Oavsett tillämpningen är universell orsak för att tillämpa ett glidande medelfilter att kväve utväcka de höga och låga avvikelserna och avslöja ett mer representativt mellanvågformvärde. När du gör det, bör programvaran inte äventyra andra funktioner i den ursprungliga vågformen i processen att generera en rörlig medellång vågform. Till exempel bör mjukvaran automatiskt justera kalibreringsinformationen som är associerad med den ursprungliga datafilen, så att den rörliga genomsnittliga vågformen ligger i lämpliga ingenjörsenheter när den genereras. Alla avläsningar i figurerna togs med hjälp av WinDaq Data Acquisition-programvaranOnline-algoritmer inom högfrekvent handel. Utmaningarna för konkurrerande HFT-algoritmer Jacob Loveless, Sasha Stoikov och Rolf Waeber HFT (högfrekvent handel) har framträtt som en kraftfull kraft i moderna finansiella marknader. För bara 20 år sedan inträffade det mesta av handelsvolymen i utbyten som New York Stock Exchange, där människor klädda i färgade outfits skulle gestikulera och skrika deras handelsintentioner. Numera sker handel för det mesta i elektroniska servrar i datacenter där datorer kommunicerar sina handelsintentioner genom nätverksmeddelanden. Denna övergång från fysiska utbyten till elektroniska plattformar har varit särskilt lönsam för HFT-företag, som investerat kraftigt i infrastrukturen för den nya miljön. Även om utseendet på platsen och dess deltagare har förändrats dramatiskt, är målet för alla handlare, vare sig elektroniska eller mänskliga, detsamma: att köpa en tillgång från en platstrader och sälja den till en annan platstrader till ett högre pris. Den avgörande skillnaden mellan en människahandlare och en HFT är att den senare kan reagera snabbare, oftare och har mycket korta portföljhållande perioder. En typisk HFT-algoritm fungerar vid den sub-millisekunda tidsskalaen, där mänskliga handlare inte kan tävla, eftersom blinkningen av ett mänskligt öga tar ungefär 300 millisekunder. Eftersom HFT-algoritmer konkurrerar med varandra möter de två utmaningar: tjur De mottar stora mängder data varje mikrosekund. tjur De måste kunna agera extremt snabbt på de mottagna uppgifterna, eftersom lönsamheten hos de signaler de observerar sönderfall snabbt. Online algoritmer ger en naturlig klass av algoritmer lämpliga för HFT-applikationer. I ett online problem avslöjas nya inmatningsvariabler i följd. Efter varje ny ingång behöver algoritmen göra ett beslutsfattande, till exempel om man vill lämna in en handel eller ej. Detta står i stark kontrast till ett offlineproblem, vilket förutsätter att hela ingående data är tillgänglig vid beslutsfattandet. Många praktiska optimeringsproblem som tas upp i datavetenskap och operativa forskningsapplikationer är onlineproblem. 1 Förutom att lösa ett online problem måste HFT-algoritmer också reagera extremt snabbt på marknadsuppdateringar. För att garantera en snabb reaktionstid är effektiv minneshantering en nödvändighet för en live-handelsalgoritm. Att hålla en stor mängd data i minnet saktar ner någon CPU, så det är viktigt att en algoritm endast använder en minimal mängd data och parametrar, som kan lagras i snabb åtkomst som L1-cacheminnet. Dessutom bör dessa faktorer återspegla marknadens nuvarande tillstånd och uppdateras i realtid när nya datapunkter följs. Sammanfattningsvis är det mindre antal faktorer som behöver behållas i minnet och ju enklare beräkningen är nödvändig för att uppdatera varje faktor, desto snabbare en algoritm kan reagera på marknadsuppdateringar. Baserat på hastighetskravet och online-naturen hos HFT-problem är klassen av en-pass-algoritmer särskilt lämplig för HFT-applikationer. Dessa algoritmer mottar en datapunkt åt gången och använder den för att uppdatera en uppsättning faktorer. Efter uppdateringen kasseras datapunkten och endast de uppdaterade faktorerna sparas i minnet. Tre problem kan uppstå i HFT-algoritmer. Den första är uppskattningen av ett löpande medel för likviditet, vilket kan vara användbart för en HFT vid bestämning av storleken på en order som sannolikt kommer att utföras framgångsrikt på en viss elektronisk utbyte. Det andra problemet är en löpande volatilitetsbedömning som kan hjälpa till att kvantifiera den kortfristiga risken för en position. Det tredje problemet är en löpande linjär regression, som kan användas i handelspar av relaterade tillgångar. Vart och ett av dessa problem kan lösas effektivt med en online-en-pass-algoritm. I den här artikeln analyserar vi prestanda för en-pass-algoritmer på gränsbokningsdata för högt likvida ETF (valutahandel) och beskriver hur man kalibrerar dessa algoritmer i praktiken. Online-algoritmer i HFT Den ena fördelen att HFT har över andra marknadsaktörer är reaktionshastigheten. HFT-företag kan se varje åtgärd i marketmdashthat, den information som finns i gränsvärdena bookmdashand reagerar inom mikrosekunder. Även om vissa HFT-algoritmer kan basera sina handlingar på en källa till information utanför marknaden (t. ex. genom att analysera nyhetsrapporter, mäta temperatur eller mäta marknadssynpunkt), baserar de flesta sina beslut uteslutande på meddelandena som kommer till marknaden. Av vissa uppskattningar finns cirka 215 000 citatuppdateringar per sekund på New York Stock Exchange. 4 Utmaningen för HFTs är att bearbeta dessa data på ett sätt som gör det möjligt för dem att fatta beslut, t. ex. när man ska gå in i positioner eller minska risken. Exemplen som används i den här artikeln förutsätter att HFTs kan observera varje uppdatering i det bästa budet och fråga priserna, inklusive de bästa bud - och frågestorlekarna. Denna delmängd av information som finns i gränsvärdesboken kallas ofta Nivå-I-orderbokinformationen. Följande tre exempel på onlinealgoritmer, var och en motiverad med en applikation i HFT, beskrivs i detalj i den här artikeln: tjur Online-medelalgoritmen. Illustrerad genom att bygga en faktor som förutsäger den tillgängliga likviditeten, definierad som summan av storlekarna vid bästa budet och det bästa frågar, vid en fast horisont i framtiden. Denna kvantitet kan vara användbar vid uppskattning av vilken orderstorlek som sannolikt kommer att utföras vid de bästa citaten vid en given latens. tjur Online varians algoritm. Illustreras genom att bygga en faktor som förutspår den realiserade volatiliteten över en fast horisont i framtiden. Denna kvantitet kan vara användbar vid uppskattning av den kortfristiga risken att inneha inventering. Tjur Online regression algoritm. Illustrerad genom att bygga en faktor som förutspår den förväntade PNL (vinst och förlust) av en lång kort position i två relaterade tillgångar. Detta kan vara användbart vid konstruktion av en signal som indikerar när en lång kort position sannolikt kommer att vara lönsam. I alla tre fall har algoritmen en enda parameter, alfa, som styr frekvensen vid vilken gammal information är bortglömd. Figur 1 visar den råa likviditetsmåttet (budstorlek plus askstorlek) i blått. Rött och grönt representerar online-likviditetsfaktorn, med alpha0.9 respektive alpha0.99. Observera att när alfa närmar sig ett värde på 1 spår signalen mjukare och effektivt spårningen i underliggande data. Figur 2 visar onlinevolatilitetsmåttet för olika värden av alfa. Återigen märker att åtgärden är mjukare för större alfa. Även om en större alfa ger en mjukare signal, ligger den också längre bakom den underliggande trenden, eftersom den ger mycket vikt åt äldre data. Som diskuteras senare, väljer ett värde för alfa översättas till en avvägning mellan en slät signal och en minskad minskning av trenden. För att illustrera online-regressionsalgoritmen tittar vi på tidsserierna för mittenpriser för SPY och SSO, två högt relaterade ETFs (SSO är den dubbla levererade versionen av SPY). Som framgår av figur 3 verkar förhållandet mellan de två tillgångarna mycket nära linjärt under en dag. Figur 4 visar online-medelvärdet och avlyssnar för två värden av alfa. En-pass-algoritmer Såsom anges av dess namn läser en enpass-algoritm varje ingångsvariabel exakt en gång och kasserar den sedan. Denna typ av algoritm är mycket effektiv när det gäller minneshantering, eftersom det bara kräver en minimal mängd data som ska lagras i minnet. I det här avsnittet presenteras tre viktiga exempel på online one-pass-algoritmer: exponentiellt rörligt medelvärde, exponentiellt vägt varians och exponentiellt vägt regression. Nästa avsnitt beskriver sedan tillämpningen av dessa algoritmer för HFT. Först kan vi titta kort på det enkla glidande medlet av en tidsserie. Detta är en uppskattning av medelvärdet av en tidsserie över ett rörligt fönster med en fast storlek. I finans används det ofta för att upptäcka trender i pris, särskilt genom att jämföra två enkla glidande medelvärden: ett över ett långt fönster och ett över ett kort fönster. I en annan applikation kan den genomsnittliga handlade volymen under de senaste fem minuterna tjäna som en förutsägelse för volymen som handlas i nästa minut. I motsats till det exponentiella rörliga medlet kan det enkla glidande medlet inte lösas med en enpass-algoritm. Låt (X t) t X 0, X 1, X 2. Var den observerade sekvensen av ingångsvariablerna. Vid varje tillfälle t vill vi förutse nästa resultat X t1. För M gt ​​0 och t ge M. Det enkla glidande medlet med fönsterstorlek M definieras som genomsnittet av de sista M-observationerna i tidsserierna (X t) t mdashthat, dvs. Det rörliga genomsnittet kan också beräknas via följande rekursion: Medan det här är en onlinealgoritm, är det inte en enpass-algoritm, eftersom den behöver tillgång till varje ingångsdatapunkt exakt två gånger: en gång för att lägga till den i glidande medelvärdet och sedan Igen för att släppa den ut ur den rörliga genomsnittliga uppskattningen. En sådan algoritm kallas en tvåpass-algoritm och kräver att man håller en hel uppsättning av storlek M i minnet. Exempel 1: Exponentialviktat medelvärde I motsats till det normala genomsnittet tilldelas det exponentiella viktade medelvärdet en exponentiellt minskande vikt till äldre observationer: Här är alfa en viktningsparameter vald av användaren och behöver tillfredsställa 0 lt alfa le 1. As Detta exponentiella vägda genomsnittsvärdet ger större betydelse för senare inmatning jämfört med äldre datapunkter, det anses ofta vara en god approximation av det enkla glidande medlet. Jämfört med det enkla rörliga genomsnittet tar det exponentiella viktade genomsnittet med alla tidigare data, inte bara de sista M-observationerna. För att jämföra det enkla glidande medlet och det exponentiella vägda genomsnittet ytterligare, visar figur 5 hur många datapunkter som mottas 80, 90, 95, 99 och 99,9 procent av vikten i uppskattningen som en funktion av alfa. Till exempel, om alfa 0,95, så bidrar de sista M 90 observerade datapunkterna till 99 procent av det uppskattade värdet. Som en varning, om tidsserien (X t) t har mycket tunga svansar, kan det exponentiella släta medlet domineras av en extrem observation, medan det rörliga genomsnittet är mindre benäget för extrema observationer eftersom dessa så småningom faller ur observationsfönstret . Frekvent omstart av uppskattningsförfarandet kan lösa denna långsiktiga minneseffekt av exponentiell utjämning. Orsaken till att det exponentiella rörliga medlet över det enkla rörliga medlet i HFT är att det kan lösas effektivt med en enpass-algoritm, som ursprungligen introducerades i Brown (1956). 3 Denna formel ger också en enkel tolkning av parametern alfa som en kontroll av hur mycket vikt som ges till den senaste observationen jämfört med alla tidigare observationer. Exempel 2: Exponentialvägt variant med en passering Den exponentiella utjämningen som beskrivs i föregående avsnitt uppskattar ett glidande medelvärde av en tidsserie. I ekonomi är volatiliteten i en tidsserie ofta också en viktig faktor. I stort sett bör volatiliteten fånga hur mycket en tidsserie fluktuerar kring sin genomsnittliga. Det finns ingen allmänt accepterad definition av volatilitet för högfrekventa finansiella data. I det här avsnittet ses volatiliteten som standardavvikelsen (kvadratroten av variansen) för en datapunkt i tidsserierna (X t) t. På samma sätt som det exponentiellt viktade glidande medlet från föregående avsnitt kan en online-en-pass-algoritm konstrueras som uppskattar tidsseriens volatilitet (X t) t med ett exponentiellt viktningsschema. Variansen för en slumpmässig variabel definieras som Var (X) E X - E X) 2. Beräkning av exponentialvikten av tidsserien kräver två estimatorer: en som uppskattar medelvärdet EX och en som uppskattar variansen: Standardavvikelsen för nästa mätpunkt X t1 beräknas därefter som. Återigen väljs ingångsparametern alpha isin (0,1) av användaren och återspeglar hur mycket vikt som tilldelas äldre datapunkter jämfört med den senaste observerade datainmatningen. Här initierade vi estimatorn för variansen med 1, vilket är ett ganska godtyckligt val. Ett annat sätt är att ha en initial inbränningsperiod för vilken tidsserien (X t) t observeras och en standardvariantberäkare av serien över det här inbrottstidsfönstret kan användas för att initiera estimatorn. Naturligtvis kan en liknande metod användas för att initiera estimatorn för den exponentiellt vägda genomsnittliga estimatorn. Exempel 3: En-pass-algoritm för exponentiellt viktad linjär regression Det sista exemplet är en online-en-pass-algoritm för den exponentiellt viktade linjära regressionsmodellen. Denna modell liknar vanlig linjär regression, men ger återigen större betydelse (enligt exponentiell viktning) till senaste observationer än vid äldre observationer. Som redan visat är sådana regressionsmetoder väldigt användbara i HFT-strategier för att uppskatta förhållandet mellan olika tillgångar, vilket exempelvis kan utnyttjas för att skapa parhandelstrategier. I denna modell betraktar vi en tvådimensionell tidsserie (X t, Y t) t och gissning att variablerna X och Y är relaterade via ett linjärt förhållande som är korrumperat av en ljudterm epsilon t med nollvärde. Det vill säga, variabeln Y kallas svarvariabeln, medan X kallas förklarande variabeln. För enkelhet kan vi bara anta en förklarande variabel här, men utvidgningen till flera förklarande variabler är okomplicerad. I standard offline-tillvägagångssätt för linjär regression kalibreras parametrarna beta 0 och beta 1 när alla datapunkter är observerade. Dessa datapunkter samlas in i en vektor Y (Y0, Y1, Yt) T och en matris. Kolumnen av de i matrisen X motsvarar avlyssningen i ekvation 3. Om vi ​​vidare skriver parametrarna beta 0 och beta 1 Som en vectormdashthat är beta (beta 0, beta 1) T mdashthen kan förhållandet mellan Y och X bekvämt skrivas i matrixnotation som där epsilon är en vektor av stokastiska brusvillkor, och var och en av dessa felvillkor har nollvärde. Det vanligaste sättet att uppskatta parametervärdet använder vanliga minsta kvadrater uppskattning. Det är, betet är valt så att det minimerar summan av kvadrerade rester. Lösningen på detta minimeringsproblem är. Precis som i medelvärdes - och variansuppskattningar bör de senaste datapunkterna vara viktigare för uppskattningen av parametern beta. Dessutom krävs en en-pass-algoritm för beta för snabb beräkning. Nästa kan överväga en rekursiv metod som uppdaterar bete sekventiellt och minimerar Igen måste parametern alfa vara i intervallet (0,1) och väljs av användaren. Parametrarna Beta 0 och Beta 1 i den viktade minsta kvadrera uppskattningen kan beräknas med en effektiv online en-pass-algoritm. Vid varje steg i algoritmen behöver en 2 gånger 2 matris Mt och en 2 gånger 1 vektor V t sparas i minnet och uppdateras med en ny datapunkt enligt följande rekursion: När det gäller medelvärdes - och variansberäknaren initierades initialiseringen av rekursionen kan göras med en inbränningsperiod. Slutligen, efter tiden t. Den bästa uppskattningen av beta är. I litteraturen kallas denna metod även rekursiva minsta kvadrater med exponentiell glömma. 2 Beräkning av Alpha Hur bestämmer man det optimala värdet av alfa, den ena parametern för alla dessa onlinemodeller Vår metod för alla tre modeller är att definiera en svarfunktion som vi strävar efter att förutse och minimera kvadreringsfelet mellan svaret ri och Vår faktor fi. Metoden finner den optimala alfabet på en historisk tidsserie. Ett annat tillvägagångssätt är att uppskatta den optimala alfa online också. Detta kräver dock mer arbete och går utöver omfattningen av denna artikel. Vi tillhandahåller nu detaljerna på de online estimatorer som beskrivits och uppskattar den optimala alfanumeriska på en given dataset. 1. Den genomsnittliga likviditetsestimatorn definieras som där indexet I representerar citat tid. Svaret definieras som likviditeten på 10 sekunder: där bs i (10) representerar budstorleken 10 sekunder efter det första citatet. Att köra en optimeringsrutin över alfa visar att den optimala alfanumeriska för den givna data är 0,97, som visas i figur 6 som en scatterplot av faktorn och svaret. 2. Volatilitetsestimatorn definieras som där indexet I representerar realtid i sekunder. Svaret definieras som den realiserade volatiliteten under nästa minut: Återigen söker över olika värden av alfa en optimal alfa på 0,985 för den givna datasatsen. Figur 7 visar en scatterplot av faktorn och svaret. 3. Parhandelens regressionsestimator definieras som var indexet representerar citattid. Faktorn representerar värdet av SPY i förhållande till SSOmdashthat är, om kvantiteten är positiv, är SPY relativt billigt och en handel som är lång SPY är sannolikt lönsam. Svaret definieras som PNL under nästa minut i en handel som är lång en del av SPY och korta beta-andelar i SSO: var representerar priset på SPY 60 sekunder efter. Svaret r representerar PNL för följande långvariga strategi: Köp 1 andel SPY och sälj beta-aktier av SSO vid tidpunkten i. lämna positionen efter 60 sekunder. I den analyserade datasatsen visar sig den optimala alfa vara 0.996. Figur 8 är en scatterplot av faktorn och svaret. Slutsats Online one-pass-algoritmer bidrar till högfrekvenshandel, där de mottar stora mängder data varje mikrosekund och måste kunna agera extremt snabbt på mottagna data. Denna artikel har behandlat tre problem som HFT-algoritmer står inför: uppskattningen av ett löpande medel för likviditet vilket kan vara användbart vid bestämning av storleken på en order som sannolikt kommer att genomföras framgångsrikt på en viss elektronisk utbyte, en löpande volatilitetsbedömning som kan hjälpa Kvantifiera den kortsiktiga risken för en position och en löpande linjär regression som kan användas i handelspar av relaterade tillgångar. Online one-pass-algoritmer kan hjälpa till att lösa alla dessa problem. Referenser 1. Albers, S. 2003. Online algoritmer: en undersökning. Matematisk programmering 97 (1-2): 3-26. 2. Astrom, A. Wittenmark, B. 1994. Adaptive Control, andra upplagan. Addison Wesley. 3. Brown, R. G. 1956. Exponentiell utjämning för att förutsäga efterfrågan. Arthur D. Little Inc. s. 15 ÄLSKAR DET, HAT DET LÄR KUN JACOB LOVELESS är VD för Lucera och tidigare chef för High Frequency Trading för Cantor Fitzgerald. Mr. Loveless har arbetat för både högfrekventa handelsgrupper och utbyten under de senaste 10 åren i nästan alla elektroniska tillgångar. Innan ett liv i finans var Mr. Loveless en särskild entreprenör för Förenta staternas försvarsdepartement med fokus på heuristisk analys på saker som inte kan diskuteras. Före det var han CTO och grundare av Data Scientific, en pionjär inom distribuerad systemanalys. SASHA STOIKOV är en ledande forskningsassistent på Cornell Financial Engineering Manhattan (CFEM) och en tidigare VP i High Frequency Trading-koncernen på Cantor Fitzgerald. Han har arbetat som konsult hos Galleon Group och Morgan Stanley och var instruktör vid Courant Institute of NYU och vid Columbias IEOR-avdelning. Han har en Ph. D. från University of Texas och en BS från MIT. ROLF WAEBER är en kvantitativ forskningsassistent hos Lucera och har tidigare varit en kvantitativ forskare vid Cantor Fitzgeralds High Frequency Trading Group. Han deltog i studier om likviditetsriskjusteringar inom Basel IIIII-regelverket vid Deutsche Bundesbank. Rolf fick sin Ph. D. i Operations Research and Information Engineering från Cornell University i 2013. Han har en BS och en MS i matematik från ETH Zürich, Schweiz. Kopiera 2013 ACM 1542-7730130800 10,00 Ursprungligen publicerad i Queue vol. 11, nr. 8 8212 se den här artikeln i ACMs digitala bibliotek Ivar Jacobson, Ian Spence, Ed Seidewitz - Industrial Scale Agile - från Craft to Engineering Essence bidrar till att flytta mjukvaruutveckling mot en sann teknikdisciplin. Andre Medeiros - Förändringsdynamik: Varför Reaktivitetsfrågor Tämma förändringsdynamiken genom att centralisera varje fråga i sin egen modul. Brendan Gregg - The Flame Graph Denna visualisering av programkörning är en ny nödvändighet för prestanda profilering och felsökning. Ivar Jacobson, Ian Spence, Brian Kerr - Användningsfall 2.0 Huben för mjukvaruutveckling handlar du även Fri, 05 Aug 2016 19:07:59 UTC Om du också handlar, är du intresserad av att bli med dig Brandon Sun, 08 maj 2016 21 : 39: 10 UTC Jag håller fast vid beräkningen av medel - och variansberäkningarna som används för att beräkna beta. Artikeln säger att vid varje steg i algoritmen måste en 2 2 matris Mt och en 2 1 vektor Vt sparas i minnet och uppdateras med en ny datapunkt enligt följande rekursion. När det gäller medelvärdet och variansberäkningen kan initialiseringen av rekursionen göras med en inbränningsperiod. Problemet jag har är att jag inte är säker på vilka värden parametrarna M och V bör initieras för att använda en inbränningsperiod. Jag är inte säker på vilka värden 2x2-matrisen eller 2x1-vektorn ska vara. Mperez fre, 08 jan 2016 21:47:19 UTC Varför, när man mäter volatilitet, beräknar de standardavvikelsen i stället för att bara använda variansen. De förlorar tiden när man räknar kvadratroten. Xxx må 21 okt 2013 07:48:57 UTC Författarens namn, Loveless. Tai diao le copy 2016 ACM, Inc. Alla rättigheter reserverade. Jag försöker hitta ett sätt att beräkna ett rörligt kumulativt genomsnitt utan att lagra räkningen och den totala data som hittills har tagits emot. Jag kom fram med två algoritmer men båda måste lagra räkningen: nytt medelvärde (gamla gammal data) nästa data) nästa räkna nytt genomsnittligt gammalt genomsnitt (nästa data - gammalt medelvärde) nästa räkning Problemet med dessa metoder är att räkningen Blir större och större vilket resulterar i att man förlorar precision i det resulterande genomsnittet. Den första metoden använder den gamla räkningen och nästa räkning som uppenbarligen är 1 från varandra. Det här fick mig att tänka på att det kanske finns ett sätt att ta bort räkningen men tyvärr har jag inte hittat det ännu. Det fick mig lite längre men resulterade i den andra metoden men räkningen är fortfarande närvarande. Är det möjligt, eller söker jag bara efter det omöjliga frågade den 28 september 12 kl 8:46