Sammanhangsblandning

Kontextblandning är en typ av datakomprimeringsalgoritm där nästa symbolförutsägelser från två eller flera statistiska modeller kombineras för att ge en förutsägelse som ofta är mer exakt än någon av de individuella förutsägelserna . Till exempel är en enkel metod (inte nödvändigtvis den bästa) att ta ett genomsnitt av sannolikheterna som tilldelats av varje modell . Den slumpmässiga skogen är en annan metod: den matar ut förutsägelsen som är läget för förutsägelserna som matas ut av enskilda modeller. Att kombinera modeller är ett aktivt forskningsområde inom maskininlärning . ^{[ citat behövs ]}

PAQ - serien av datakomprimeringsprogram använder kontextblandning för att tilldela sannolikheter till enskilda bitar av ingången.

Applikation för datakomprimering

Antag att vi får två villkorade sannolikheter, $P(X|A)$ och $P(X|B)$ , och vi vill uppskatta $P(X|A,B)$ , sannolikheten för händelse X givet både villkoren $A$ och $B$ . Det finns inte tillräckligt med information för att sannolikhetsteorin ska ge ett resultat. Det är faktiskt möjligt att konstruera scenarier där resultatet kan bli vad som helst. Men intuitivt skulle vi förvänta oss att resultatet skulle vara något slags medelvärde av de två.

Problemet är viktigt för datakomprimering. I den här applikationen $A$ och $B$ sammanhang, $X$ är händelsen att nästa bit eller symbol för data som ska komprimeras har ett speciellt värde, och $P(X|A)$ och $P(X|B)$ är sannolikhetsuppskattningarna av två oberoende modeller. Kompressionsförhållandet beror på hur nära den uppskattade sannolikheten närmar sig den sanna men okända sannolikheten för händelse $\displaystyle X}$ { . Det är ofta så att sammanhangen $A$ och $B$ har förekommit tillräckligt ofta för att exakt uppskatta $P(X|A)$ och $P(X|B)$ genom att räkna förekomster av $X$ i varje sammanhang, men de två sammanhangen har antingen inte förekommit ofta tillsammans, eller så finns det otillräckliga beräkningsresurser (tid och minne) för att samla in statistik för det kombinerade fallet.

Anta till exempel att vi komprimerar en textfil. Vi vill förutsäga om nästa tecken kommer att vara en radmatning, givet att det föregående tecknet var en punkt (kontext $A$ ) och att den senaste radmatningen inträffade för 72 tecken sedan (kontext $B$ ). Antag att en radmatning tidigare inträffade efter 1 av de senaste 5 perioderna ( $P(X|A=0.2$ ) och i 5 av de senaste 10 raderna i kolumn 72 ( $P(X|B)=0.5$ ) Hur ska dessa förutsägelser kombineras?

Två generella tillvägagångssätt har använts, linjär och logistisk blandning. Linjär blandning använder ett viktat medelvärde av förutsägelserna viktade med bevis. I det här exemplet $P(X|B)$ mer vikt än $P(X|A)$ eftersom $P(X|B)$ baseras på ett större antal tester. Äldre versioner av PAQ använder detta tillvägagångssätt. Nyare versioner använder logistisk (eller neuralt nätverk ) blandning genom att först omvandla förutsägelserna till den logistiska domänen, log(p/(1-p)) innan medelvärdet beräknas. Detta ger i praktiken större vikt åt förutsägelser nära 0 eller 1, i detta fall $P(X|A)$ . I båda fallen kan ytterligare vikter ges till var och en av ingångsmodellerna och anpassas för att gynna de modeller som har gett de mest exakta förutsägelserna tidigare. Alla utom de äldsta versionerna av PAQ använder adaptiv viktning.

De flesta kontextblandningskompressorer förutsäger en bit av input i taget. Utgångssannolikheten är helt enkelt sannolikheten att nästa bit blir en 1.

Linjär blandning

Vi får en uppsättning förutsägelser P _i (1) = n _1i /n _i , där n _i = n _0i + n _1i , och n _0i och n _1i är räkningarna av 0 respektive 1 bitar för den i:te modellen . Sannolikheterna beräknas genom viktad addition av 0- och 1-tal:

₀ S = Σ _i w _i n _0i
S1 ₌ Σ _i w _i n _1i
₀ S = S + S ₁
₀ P(0) = S /S
P(1) = S ₁ / S

Vikterna w _i är initialt lika och summerar alltid till 1. Under de initiala förhållandena viktas varje modell i proportion till bevis. Vikterna justeras sedan för att gynna de mer exakta modellerna. Antag att vi får att den faktiska biten som förutsägs är y (0 eller 1). Då är viktjusteringen:

ni = _noi + _ni_{_}
fel = y – P(1)
₀ w _i ← w _i + [(S n _1i - S ₁ n _i ) / (S S ₁ )] fel

₀ Kompressionen kan förbättras genom att begränsa n _i så att modellviktningen blir bättre balanserad. I PAQ6, närhelst en av biträkningarna inkrementeras, halveras den del av den andra räkningen som överstiger 2. Till exempel, efter sekvensen 000000001, skulle räkningarna gå från (n , n ₁ ) = (8, 0) till (5, 1).

Logistisk blandning

Låt P _i (1) vara förutsägelsen av den i:te modellen att nästa bit kommer att vara en 1. Sedan beräknas den slutliga förutsägelsen P(1):

x _i = sträcka(P _i (1))
P(1) = squash(Σ _i w _i x _i )

där P(1) är sannolikheten att nästa bit kommer att vara en 1, Pi ( ₁ ) är sannolikheten uppskattad av den i:te modellen, och

sträcka(x) = ln(x / (1 - x))
squash(x) = 1 / (1 + e ^−x ) (invers av sträckning).

Efter varje förutsägelse uppdateras modellen genom att justera vikterna för att minimera kodningskostnaden.

w _i ← w _i + η x _i (y - P(1))

där n är inlärningshastigheten (typiskt 0,002 till 0,01), y är den predikterade biten och (y - P(1)) är prediktionsfelet.

Lista över kontextblandningskompressorer

Alla versioner nedan använder logistisk blandning om inget annat anges.

Alla PAQ- versioner (Matt Mahoney, Serge Osnach, Alexander Ratushnyak, Przemysław Skibiński, Jan Ondrus och andra) [1] . PAQAR och versioner före PAQ7 använde linjär blandning. Senare versioner använde logistisk blandning.
Alla LPAQ-versioner (Matt Mahoney, Alexander Ratushnyak) [2] .
ZPAQ (Matt Mahoney) [3] .
WinRK 3.0.3 (Malcolm Taylor) i PWCM-läge för maximal komprimering [4] . Version 3.0.2 baserades på linjär blandning.
NanoZip (Sami Runsas) i maximalt komprimeringsläge (alternativ -cc) [5] .
xwrt 3.2 (Przemysław Skibiński) i maximalt komprimeringsläge (alternativ -i10 till -i14) [6] som en backend till en ordbokskodare.
cmm1 till cmm4, M1 och M1X2 (Christopher Mattern) använder ett litet antal sammanhang för hög hastighet. M1 och M1X2 använder en genetisk algoritm för att välja två bitars maskerade sammanhang i ett separat optimeringspass.
ccm (Christian Martelock).
bit (Osman Turan) [7] .
pimple, pimple2, tc och px (Ilia Muraviev) [8] .
enc (Serge Osnach) provar flera metoder baserade på PPM och (linjär) kontextblandning och väljer den bästa. [9]
fpaq2 (Nania Francesco Antonio) med fast viktmedelvärde för hög hastighet.
cmix (Byron Knoll) blandar många modeller och är för närvarande rankad först i riktmärket Large Text Compression, såväl som i Silesia corpus och har överträffat det vinnande bidraget för Hutter Prize även om det inte är berättigat på grund av att det används för mycket minne.