Vi överväger problemet med att förutsäga nästa observation med tanke på en sekvens av tidigare observationer, och överväga i vilken utsträckning exakt förutsägelse kräver komplexa algoritmer som uttryckligen utnyttjar långdistansberoenden. Kanske överraskande, våra positiva resultat visar att för en bred klass av sekvenser, finns det en algoritm som förutspår väl i genomsnitt, och baserar sina förutsägelser endast på de senaste få observation tillsammans med en uppsättning enkel sammanfattande statistik över tidigare observationer. Specifikt visar vi att för all distribution över observationer, om den ömsesidiga informationen mellan tidigare observationer och framtida observationer är övre begränsas av I, då en enkel Markov modell över de senaste I /ε observationer får förväntat KL fel ε-och därmed l 1 fel ε-när det gäller den optimala prediktor som har tillgång till hela det förflutna och känner till datagenererande distribution. För en dold Markov modell med n dolda tillstånd, Jag begränsas av log n, en kvantitet som inte beror på blandningstiden, och vi visar att triviala förutsägelse algoritm baserad på empiriska frekvenser av längd O (log n/ε ) fönster observationer uppnår detta fel, förutsatt att längden på sekvensen är d  och (log n/ε ), där d är storleken på observation alfabetet. Vi konstaterar också att detta resultat inte kan förbättras, inte ens för klassen HMMs, i följande två sinnen: För det första, för HMMs med n dolda tillstånd, en fönsterlängd log n/ε är informationteoretiskt nödvändigt för att uppnå förväntat KL fel ε, eller l 1 fel ε. För det andra, de d-prov (log n/ε ) som krävs för att korrekt uppskatta Markov-modellen när observationer hämtas från ett alfabet av storlek d är nödvändiga för beräkningsbart lärande/prediktionsalgoritm, förutsatt att hårdheten hos starkt vederlägga en viss klass av CSPs. * En fullständig version av detta dokument finns på https://arxiv.org/abs/1612.02526. Vatsal och Gregorys bidrag stöddes delvis av NSF Award CCF-1704417 och av ONR Award N00014-17-1-2562. Shams bidrag stöddes delvis av NSF Award CCF-1703574. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org.  Vi anser att problemet med att förutsäga nästa observation x t ges en sekvens av tidigare observationer, x 1, x 2,. ..,x t −1, som kan ha komplexa och lång räckvidd beroenden. Denna sekventiella förutsägelse problem är en av de mest grundläggande lärande uppgifter och möter hela naturligt språk modellering, talsyntes, ekonomisk prognos, och ett antal andra domäner som har en sekventiell eller kronologiska element. Det abstrakta problemet har fått stor uppmärksamhet under det senaste halvseklet från flera samhällen, inklusive TCS, maskininlärning och kodningsteori. Den grundläggande frågan är: Hur konsoliderar och refererar vi minnen om det förflutna för att på ett effektivt sätt kunna förutsäga framtiden? Med tanke på den enorma praktiska betydelsen av denna förutsägelse problem, har det gjorts en enorm ansträngning att utforska olika algoritmer för att lagra och referera information om sekvensen, vilket har lett till utvecklingen av flera populära modeller såsom n-gram modeller och dolda Markov modeller (HMMs). Nyligen har det funnits ett betydande intresse för återkommande neurala nätverk (RNN) [1]-som kodar det förflutna som en verklig vektor av fast längd som uppdateras efter varje observation-och specifika klasser av sådana nätverk, såsom Long Short-Term Memory (LSTM) nätverk [2, 3]. Andra nyligen populära modeller som har explicita föreställningar om minne inkluderar neural Turing maskiner [4], minnesnätverk [5], olika neurala datorer [6], uppmärksamhetsbaserade modeller [7, 8], etc. Dessa modeller har varit ganska framgångsrika (se t.ex. [9, 10] ); icke desto mindre, konsekvent lärande långdistans beroenden, i miljöer som naturligt språk, förblir ett mycket aktivt forskningsområde. Parallellt med dessa försök att utforma system som uttryckligen använder minnet har det gjorts stora ansträngningar från neurovetenskapens sida för att förstå hur människor och djur kan göra 1074
Vi noterar att det senaste arbetet med REF tar upp problemet med att förutsäga fördelningen av nästa observation i datasekvensen ur ett annat perspektiv.
Prediction with a short memory
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}