Ett dilemma som lärare ställs inför, och i allt högre grad designers av pedagogisk programvara, är kompromissen mellan att lära ut nytt material och att se över det som redan har lärts ut. Att komplicera saker och ting är bara användbart om det varken är för tidigt eller för sent. Dessutom måste olika studenter granska i olika takt. Vi presenterar en matematisk modell som fångar dessa frågor i idealiserad form. Studentens behov är modellerade som begränsningar i schemat enligt vilka utbildningsmaterial och granskning är fördelade över tid. Våra resultat inkluderar algoritmer för att konstruera scheman som följer olika avståndsbegränsningar, och gränser för i vilken takt nytt material kan införas under dessa scheman. Asymptotic analyse  på schemaläggning I n hans 2009 tal till National Academy of Sciences, president Barack Obama uppmanade publiken att föreställa sig några av de saker som kunde göras möjligt genom ett engagemang för vetenskaplig forskning, inklusive uppfinningen av "inlärning programvara så effektiv som en privat handledare" (1). Detta dokument är ett blygsamt steg i den riktningen. En viktig utmaning för utformningen av pedagogisk programvara är att införliva resultaten av empirisk forskning om hur människor lär sig. Sådan forskning strävar efter att ge principer för hur man väljer vad som lärs ut, hur man presenterar det och hur man ordnar materialet. I slutändan kommer utbildningsprogram att kräva mekanismer för att hantera de begränsningar som uppstår när dessa principer tillämpas i olika miljöer. Här utvecklar och analyserar vi en idealiserad matematisk modell för att inkorporera en grundläggande klass av sådana begränsningar i utbildningsprogram-constraints som uppstår från betydelsen av timing och översyn i presentationen av nytt material. Till exempel måste programvara för att bygga ordförråd avgöra när man ska införa nya ord som studenten ännu inte har lärt sig, och när man ska granska ord vars definitioner studenten framgångsrikt har återkallat tidigare. Frågan liknar den som en matematiklärare i high school ställs inför och bestämmer hur ofta man ska schemalägga lektioner som inbegriper trigonometri, eller av en pianolärare som behöver bestämma hur mycket tid en elev ska ägna åt att öva skalor samtidigt som han lär sig att spela nya pjäser. Undersökningen av timingens betydelse när det gäller granskningsdatum till minst 1885 (2). Föreställningen att det är bättre att sprida studierna över tiden istället för att göra allt på en gång kallas avståndseffekten. 1988 konstaterade Dempster att "separationseffekterna är ett av de mest studerade fenomenen i den 100-åriga inlärningsforskningens historia" (3). Som Balota et al. i sina granskningar (4): "Snabbare effekter förekommer mellan olika domäner (t.ex. inlärning av perceptuella motoriska uppgifter jämfört med inlärningslistor över ord), mellan olika arter (t.ex. råttor, duvor och människor), mellan åldersgrupper och individer med olika minnesnedsättningar, och över retentionsintervall mellan sekunder och månader." Se domaren. 5 och 6 för recensioner. För ytterligare resultat och bakgrund, se ref. Sjuttioåtta. För arbete med att utnyttja avståndseffekten för att bygga ordförråd (i människor), se refs. 10-13. Recensioner är en viktig del av inlärningsprocessen, men i vilken utsträckning det behövs granskning varierar mellan studenterna. Vissa elever behöver gå igenom tidigt och ofta, medan andra kan lära sig mycket utan någon översyn alls. Personlig utbildning programvara för framtiden kan passa en modell för användaren och sedan schemalägga översyn på ett sätt som är skräddarsytt för modellen. Med sådan pedagogisk programvara i åtanke, vi föreställer oss ett system där programvarudesignern kan ange ett schema för införandet av nytt material, tillsammans med ett schema genom vilket granskning av befintligt material är utrymme över tiden. Vad vi dock finner är att de resulterande schemaläggningsproblemen är matematiskt subtila: Befintliga tekniker hanterar inte schemaläggningsproblem med avståndsbegränsningar av denna typ. Vårt huvudsakliga bidrag är att utveckla en strategi för resonemang om genomförbarheten av scheman under avstånd begränsningar. Vi börjar med att införa en stiliserad matematisk modell för de begränsningar som uppstår från avståndseffekten, och sedan överväga utformningen av scheman som införlivar dessa begränsningar. Grovt taget modellerar vi introduktionen och genomgången av material som en sekvens av abstrakta utbildningsenheter, och vi modellerar studentens behov med hjälp av två sekvenser, fa k g och fb k g: Efter att en utbildningsenhet har introducerats, är den "ideala" tiden för studenten att se den för ðk 1-st tiden mellan en k-b k tidssteg efter att ha sett den för k:te gången. Vi modellerar också olika utbildningsresultat som designern av utbildningsprogramvaran kan sträva efter att uppnå. Närmare uppgifter ges nedan. Utbildningsprocessen. Vi föreställer oss den underliggande utbildningsprogramvaran som genomför en process som presenterar en sekvens av abstrakta utbildningsenheter som kan representera fakta som definitioner av ordförrådsord, begrepp som trigonometriska identiteter eller färdigheter som att spela en skala på pianot. Till exempel, sekvensen u 1, u 2, u 3, u 1, u 4 ;..., indikerar att utbildningsenheten u 1 infördes vid första steget och recenserades vid fjärde steget. Denna sekvens definierar schemat enligt vilket enheterna kommer att presenteras. Vi tillåter också våra scheman att innehålla luckor, eller tidssteg där ingen utbildningsenhet presenteras, vilket innebär att ett godtyckligt schema kommer att ha varje inträde som är lika med antingen en utbildningsenhet eller ett blanktecken. Denna modell är mycket idealiserad. Den ignorerar möjliga relationer mellan enheter, såsom det etymologiska (och potentiellt pedagogiskt användbara) sambandet mellan vokabulärorden "neofyt" och "neologism", till exempel, eller beroendet av trigonometri på mer grundläggande begrepp i geometri. Det behandlar också alla enheter som lika. Således fångar det inte, till exempel, att en erfaren pianist kan ha större nytta av att öva en skala än att öva Twinkle Twinkle Little Star. Den verkliga utbildningsprocessen är nyanserad, komplex och kontextberoende. Framtida arbete med att bygga modeller för pedagogisk programvara kan medföra mer komplexitet i denna modell, eller helt enkelt minska omfattningen och modellera mer specifika situationer. Här bidrar författaren: T.P.N., J.M.K. och S.H.S. designad forskning, utfört forskning, analyserat data och skrivit tidningen. Meddelande om intressekonflikt: T.PN. är ägare till ett litet, helägt företag, Flash of Genius, LLC, som säljer pedagogisk programvara. Denna artikel är en PNAS Direkt Inlämning. Vi använder denna mycket enkla modell av den allmänna utbildningsprocessen för att skapa en formalism som fångar upp avståndsbegränsningar och deras roll när det gäller att granska material efter det att det har införts. Avståndsbegränsningar. En stor mängd empiriskt arbete inom lärande forskning har studerat den expanderande naturen av optimal granskning. Till exempel, när eleverna först lär sig ett nytt ordförråd ord, de måste granska det snart eller annars de sannolikt förlorar förmågan att korrekt återkalla definitionen. Om de gör en översyn innan de glömmer det, kommer de då i allmänhet att kunna gå längre än tidigare utan att behöva ses över. Genom att gång på gång granska, "bygger upp" studenten förmågan att gå längre och längre utan att se ordet samtidigt som förmågan att komma ihåg sin definition. Men att gå igenom ett ord för tidigt efter att ha studerat det kan minska nyttan av översynen. Dessa är principerna för den väletablerade teorin om utökad hämtning; se ref. 4 för en granskning specifikt om utökad hämtning. Mer allmänt, se domaren. Tre-tre-tre-tre-tre-tre-tre. Vi vill ha en enkel formalism som fångar behovet av att granska en utbildningsenhet på ett schema som "expanderar" avståndet mellan på varandra följande visningar. Vi vill lämna den exakta expansionstakten under kontroll av programvarudesignern, motiverad av målet att skapa olika scheman för olika studenter. Vi föreställer oss alltså att programvarans konstruktör specificerar en uppsättning avståndsbegränsningar, som består av en oändlig sekvens av beställda par ða 1 ;b 1  och ða 2 ;b 2  till;...;ða k ;b k  till;..., där en k ≤ b k är positiva heltal för alla k. Intuitivt är tanken att, för varje utbildningsenhet u i schemat, designern vill gapet i schemat mellan kth och ðk 1 och st förekomster av u i att ha längd i det stängda intervallet 1⁄2a k ;b k. Det faktum att en student kan gå längre mellan förekomster som de får kännedom om utbildningsenheten representeras av antagandet att siffrorna en k och b k är svagt ökande: Vi inför kravet att en k ≤ en k ≤ 1 och b k ≤ kπ1 för alla k. Således är vår nyckeldefinition att ett schema uppfyller en uppsättning mellanslagsbegränsningar om, för varje u i schemat, ðk 1 och st förekomst av u i schemat (k) kommer mellan k och k (k) Ungefär så modellerar siffrorna b k hur länge studenten kan behålla inlärt material. Siffrorna en k modell hur länge en student ska vänta innan översyn är fördelaktigt, fånga uppfattningen att det finns en idealisk tid att granska. Om översynen görs för tidigt är den mindre fördelaktig. Om det görs för sent, kommer den studerande att glömma materialet under mellantiden. Denna modell är, genom utformning, en förenkling av avståndsbegränsningarna och deras roll i lärandet. En mer nyanserad modell kan tillåta "blurry" gränser för intervallen 1⁄2a k ;b k, där det finns en numerisk påföljd för att missa intervallet med en liten mängd. En annan förbättring skulle vara att låta modellen diskriminera mellan utbildningsenheterna för att återspegla att vissa saker är lättare att lära än andra. Men vår enkla modell fångar kärnan i det fenomen vi undersöker, och kommer att möjliggöra matematisk analys som klargör mekaniken i schemaläggning översyn på ett optimalt sätt. Utbildningsmål. Vi anser att två naturliga mål för designern av utbildningsprogramvaran. Programvarans uppgift skulle kunna vara att lära eleverna på ett sådant sätt att de växer sin kunskap utan att bli bundna, aldrig glömma något på vägen; ett slags "livslångt lärande" förhållningssätt till utbildning. Alternativt kan uppdraget helt enkelt vara att få eleverna bekanta med en viss uppsättning utbildningsenheter vid en viss tidpunkt, oavsett om de är avsedda att glömma vad de lärde sig snabbt därefter; något som liknar den studieteknik som kallas "kramning". Vi tar upp båda målen i detta dokument. Vi modellerar det första målet genom att säga att ett schema uppvisar oändligt perfekt lärande med avseende på vissa avståndsbegränsningar om (i) det uppfyller avståndsbegränsningarna, och (ii) det innehåller oändligt många utbildningsenheter, som var och en inträffar oändligt ofta. Om begränsningarna alltså representerade en elevs behov, skulle den studerande med ett sådant schema under loppet av den oändliga sekvensen lära sig en oändlig uppsättning undervisningsenheter utan att någonsin glömma något. För det andra målet överväger vi en ändlig sekvens, som representerar presentationen av material upp till ett test eller prestanda. För ett positivt heltal n, säger vi att sekvensen är en crumming sekvens, och uppvisar begränsad inlärning av ordning n, om (i) den uppfyller avståndsbegränsningarna, och (ii) den innehåller minst n distinkta utbildningsenheter sådan att, om en enhet inträffar totalt k gånger i sekvensen, dess sista förekomst är inom b k positioner i slutet av sekvensen. Villkor ii) fångar kravet att studenten fortfarande ska kunna återkalla alla n utbildningsenheter i slutet av sekvensen, vilket var hela punkten för kramp. Observera att även om avståndsbegränsningarna har respekterats fram till slutet av den finita sekvensen, finns det ingen garanti för att sekvensen kan förlängas samtidigt som den fortsätter att uppfylla avståndsbegränsningarna. Med avseende på oändligt perfekt lärande kommer vi att vara intresserade av den takt med vilken den studerande skulle lära sig om han undervisade enligt schemat. I detta syfte definierar vi den inledande tidsfunktionen: För ett visst schema över utbildningsenheter, låt t n ange positionen i schemat för den första förekomsten av den n:te distinkta utbildningsenheten. Ju långsammare tillväxten av t n, desto snabbare nya utbildningsenheter införs. Vi kommer att överväga följande frågor. Med tanke på avståndsbegränsningar fða k ;b k  skag, finns det ett schema som uppvisar oändligt perfekt lärande, eller begränsat lärande, med hänsyn till begränsningarna? Hur kan vi i så fall konstruera sådana scheman? Och när ett sådant schema finns, vilken inlärningshastighet (mätt enligt sekvensen t 1 ; t 2 ;...) är möjlig? Dessa är grundläggande problem som skulle mötas av en pedagogisk programvarudesigner som försöker införliva avståndsbegränsningar i utformningen av de underliggande algoritmerna. Som vi kommer att se, trots den helt enkelt angivna formuleringen av dessa frågor, de kombinatoriska utmaningar som de leder till snabbt bli ganska invecklade. Avståndet begränsningar beskrivs av två oändliga sekvenser av parametrar, fa k g och fb k g. I detta avsnitt beskriver vi hur val för dessa parametrar påverkar hastigheten med vilken nya utbildningsenheter kan införas i schemat och hur scheman kan anpassas till särskilda parameter regimer och utbildningsmål. Översikt över resultaten. Vi börjar med att undersöka den första huvudfrågan i detta dokument: avvägningen mellan i) den takt med vilken b k växer som en funktion av k och ii) den takt med vilken t n växer som en funktion av n. Informellt, om b k växer relativt långsamt, då en hel del tid måste spenderas på översyn snarare än på att införa nya enheter, och därmed t n måste växa snabbare, vilket motsvarar långsammare lärande. Det är tydligt att t n ≥ n för alla scheman, eftersom även utan översyn kan vi bara införa en utbildningsenhet per steg. Med dessa överväganden i åtanke undersöker vi följande två frågor som utforskar de två sidorna av kompromissen. För det första, finns det en uppsättning av avstånd begränsningar för vilka t n är nära denna triviala bunden, växer nästan linjärt i n? För det andra, eftersom vi behöver b k för att växa långsammare som en funktion av k, blir det svårare att uppnå oändligt perfekt lärande. Finns det en uppsättning avståndsbegränsningar för vilka oändligt perfekt inlärning är möjlig, och för vilka b k växer som en polynom funktion av k? Vi besvarar båda dessa frågor jakande. I The Recap Method beskriver vi en uppsättning avståndsbegränsningar för vilka ett schema kan konstrueras som uppvisar oändligt perfekt lärande, och där inlärningshastigheten är relativt snabb. I schemat som vi konstruerar, t n växer som  och i själva verket t n ≤ n · ð till log 2 n. Vi erinrar om att vi måste ha t n ≥ n för alla 2 av 6  på www.pnas.org/cgi/doi/10.1073/pnas.1109863109 Novikoff et al. n för alla scheman, ser vi att recap schemat uppnår oändligt perfekt lärande med endast en blygsam ökning på denna gräns-det vill säga, med en relativt liten mängd översyn. I SI Text visar vi hur man konstruerar ett schema där t n växer i en takt som på något sätt kan vara så nära linjär som önskat. I Superlinearity of the Introduction Time Function, visar vi att det inte kan finnas något schema som helst sådan att t n växer som Oðn. I The Slow Flashcard Schema visar vi en uppsättning avståndsbegränsningar för vilka en k och b k växer polynomiskt i k och för vilka oändligt perfekt lärande är möjligt. Med dessa avståndsbegränsningar baserade på mycket mindre en k och b k, schemat vi konstruerar har en långsammare takt av lärande; t n begränsas nedan av  och avgränsas ovan av Oðn 3  och i motsats till schemat från Recap Method för vilken introduktionstiden funktion växer som. Klyftan mellan den lägre kvadratiska gränsen och den övre kubikgränsen är en intressant öppen fråga; vi ger numeriska bevis för att den nedre gränsen i själva verket kan vara snäv, och att t n växer som Oðn 2. Mycket av denna analys görs i SI-texten. Efter dessa resultat går vi över till den andra huvudfrågan i detta dokument, som är att identifiera allmänna möjligheter och omöjliga resultat för att tillfredställa klasser av avståndsbegränsningar. Vi visar först, i Flexible Students, att svårigheten att uppnå oändliga perfekt lärande stammar, i en mening, från det faktum att siffrorna en k växer: specifikt, Vi visar att för alla avstånd begränsningar där en k 1⁄4 1 och b k → ❌, är det möjligt att bygga ett schema som uppvisar oändligt perfekt lärande. Den konstruktion som införs här visar en allmän metod som kan anpassas till många uppsättningar av avståndsbegränsningar med en k > 1 också. Hittills har vi bara övervägt avståndsbegränsningar som gör det möjligt att bygga scheman som uppvisar oändligt perfekt lärande. I The Finicky Slow Student visar vi att det finns avståndsbegränsningar för vilka inget schema kan uppvisa oändligt perfekt lärande. I synnerhet bygger vi denna omöjlighet till följd av ett extremt fall, där en k 1⁄4 b k 1⁄4 f ðk en funktion som växer långsamt i k. Dessa begränsningar representerar en miljö där studenten insisterar på att granska material på en extremt exakt och ploding schema, utan utrymme för fel. Svårigheten med att skapa en tidsplan för en sådan uppsättning begränsningar är att eftersom kunskapsbasen – antalet utbildningsenheter som introduceras – växer, så ökar behovet av att se över, och därmed ökar risken för schemaläggning av konflikter. Ju långsammare studenten [ju långsammare tillväxten av f ðk till], desto färre utbildningsenheter kan sättas på bakbrännaren, så att säga, medan studenten fokuserar på nya enheter. Ju mer fiffig studenten (ju mindre fönster b k − a k ), desto mindre vicka rum finns det i schemaläggning översyn. Alla dessa punkter stämmer överens med intuitionen. Studenter som inte behöver granska mycket och inte är alltför kräsna om när recensionen behöver hända kan läras ut mycket, och snabbt. Men elever som behöver en hel del översyn och som bara drar nytta av mycket lägliga översyn kommer att vara svårare att undervisa. Det pedagogiska mantrat är "varje barn kan lära sig", men designers av personlig pedagogisk programvara kan finna att schemaläggningen av utbildningsprocessen för vissa elever åtminstone är svårare för vissa än för andra. I Cramming visar vi att varje elev kan kramp. Mer exakt, vi visar att för varje uppsättning av avstånd begränsningar och alla n, är det möjligt att konstruera en ändlig sekvens som uppvisar begränsad inlärning av ordning n. I överensstämmelse med den diskussion som åtföljde definitionen av avgränsat lärande tidigare, garanterar konstruktionen ingenting om huruvida sekvensen kan förlängas bortom detta ögonblick av "expertis" i slutet. Slutligen, även i Cramming, undersöker vi frågan om hur mycket som kan fyllas på en viss tid. Med tanke på en uppsättning avståndsbegränsningar och ett ändligt antal T, härleder vi en icke-trivial övre gräns på de n för vilka begränsat lärande av ordning n är möjligt med endast T-tid steg. Rekapsmetoden. Här utforskar vi avståndsbegränsningar som möjliggör oändligt perfekt lärande med en snabb inlärningshastighet - det vill säga där introduktionstidens funktion, t n, växer långsamt. Betrakta avståndsbegränsningarna en k 1⁄4 2 k och b k 1⁄4 2 k−1 ðk. Ett schema som möjliggör oändligt perfekt lärande med avseende på dessa avståndsbegränsningar kan beskrivas som följer. För att hitta den första ðk 1 till · 2 k poster i schemat, överväga en djup-första postorder traversal av en full binärt träd av djup k med 2 k blad märkta u 1, u 2 ;...; u 2 k från vänster till höger. (En djup-första postorder traversal av ett träd är en särskild ordning för att besöka noderna av ett träd, definieras enligt följande. Börjar vid roten v av trädet, är djup-första postorder traversal först tillämpas rekursivt till varje delträd nedanför v en i taget; efter alla dessa traversals görs, sedan roten v deklareras att besökas.) Börja med en tom sekvens. Varje gång ett blad besöks, bifoga sekvensen med motsvarande utbildningsenhet. Varje gång en nonleaf node besöks, bifoga sekvensen med de enheter som motsvarar alla ättlingsblad, i vänster-till-höger ordning. Den resulterande sekvensen ger de första posterna i schemat. Med hjälp av k 1⁄4 2 har vi alltså att de första 12 posterna i schemat är u 1 ; u 2 ; u 1 ; u 2 ; u 3 ; u 4 ; u 3 ; u 4 ; u 1 ; u 2 ; u 3 ; u 4. Vi kallar detta schema "rekap schema" eftersom det innehåller periodisk översyn av allt som har lärts hittills, som en lärare som säger "okej, låt oss sammanfatta." I detta schema är antalet tidssteg mellan kth och ðk 1-st förekomst av en viss enhet alltid mellan 2 k1 och 2 k-1 ðk 1-, med båda gränserna faktiskt uppnås för varje k. Detta faktum-tillsammans med det faktum att oändligt många enheter förekommer oändligt ofta på grund av egenskaper djup-första traversals-etablerar att recap schemat möjliggör oändligt perfekt lärande med avseende på de givna avstånd begränsningar. Beräkningar som fastställer dessa fakta visas i SI-texten. Ytterligare beräkningar, som också visas i SI-texten, visar att t n växer i takt med att t n växer i takt med att............................................................................................................. Mer exakt, 1 2 · n · ð till log 2 n på ett sätt som är mer generellt för träd kan vi visa att för en stor klass av funktioner kan scheman konstrueras som uppvisar oändligt perfekt inlärning för vilken t n växer som t n · r −1 ðn på ett enkelt sätt. Klassen omfattar funktioner som rðn och som växer godtyckligt snabbt, och så i den meningen kan vi skapa scheman för vilka t n växer i en takt som är så nära linjär som önskat. Nackdelen med dessa scheman är att de kräver allt mer slappa avståndsbegränsningar när tillväxthastigheten för t n närmar sig linearitet: De scheman som vi konstruerar för vilka t n växer som t n · r −1 ðn och kräver b k, samt b k − a k, att växa som............................................................................... Beräkningar som också fastställer dessa fakta visas i SI-texten. Superlinjäritet av introduktionstiden funktion. Även om våra konstruktioner kan uppnå introduktionstider t n som växer godtyckligt nära linjärt i n, kan vi också visa att en faktisk linjär tillväxthastighet inte är möjlig: För scheman som uppvisar oändligt perfekt lärande, måste introduktionstiden funktion t n vara superlinjär. Mer exakt, vi visar att för alla scheman som uppvisar oändligt perfekt lärande med avseende på eventuella avstånd begränsningar fða k ;b k  på g, det kan inte finnas en konstant c sådan att t n ≤ cn för alla n. För att bevisa detta uttalande, anser vi en godtycklig uppsättning av avstånd begränsningar fða k ;b k  på ett godtyckligt schema som uppvisar oändligt perfekt lärande med avseende på dessa begränsningar, och anta för motsägelsens skull att det finns en konstant c sådan att t n ≤ cn för alla n. Letb k 1⁄4  och k j1⁄41 b j och låt n 0 vara något heltal sådan att n 0 >b c  och 1. Med vårt antagande, minst n 0 utbildningsenheter har införts av tiden steg cn 0. I allmänhet, för alla Novikoff et al. PNAS Early Edition 3 av 6 schema som uppvisar oändliga perfekt lärande, varje enhet som har införts av tiden steg t kommer att ha inträffat k gånger per tid steg t  och k, genom definitionen av b k. Således minst n 0 enheter kommer att ha inträffat c 1 gånger per tid steg cn 0. Detta beror på att varje steg motsvarar högst en utbildningsenhet. Subtrahera cn 0 från båda sidor, vi har att b c och 1 ≥ n 0, vilket motsäger vårt val av n 0. Således kan det inte finnas en konstant c sådan att t n ≤ cn för alla n. Slow Flashcard schema. Man kan beskriva konstruktionen av recap schema utan att använda djup-första traversals eller full binära träd, utan snarare med hjälp av ett kortlek. Att göra det kommer att kasta lite ljus på recap schemat, och kommer också att fungera som en användbar hopp-off-punkt för att diskutera den mycket annorlunda schema som är fokus för detta avsnitt. Så vi börjar vår diskussion här genom att se över schemat. Föreställ dig en kortlek av flashcards, med kth kort som motsvarar en utbildningsenhet u k. Således det översta kortet motsvarar u 1, nästa kort motsvarar u 2, etc. Sedan konstruerar vi ett schema enligt följande. Vid varje steg presenterar vi för studenten den utbildningsenhet som motsvarar det översta kortet, och sedan infoga kortet på position 2 k, där k är antalet gånger vi har presenterat den utbildningsenhet som motsvarar det kortet, fram till och med denna senaste tid steg. Så först presenterar vi u 1, sedan tar vi bort den från däcket och sätter in den i position 2 i däcket. Sedan presenterar vi u 2, sedan ta bort den och återinföra den i position 2 i däcket. Sedan är u 1 igen på toppen och så presenterar vi den för en andra gång och sedan ta bort den och återinföra den i position 2 2 1⁄4 4. Denna process producerar recap schemat. I detta avsnitt, Vi anser ett schema som är mycket svårare att beskriva uttryckligen än recap schema, men vars konstruktion kan på liknande sätt beskrivas i termer av ett kortlek. Istället för att återinsätta oss i position 2 k som ovan, återinsätter vi oss i position k 1. Noggrann tillämpning av denna regel visar de första få posterna i schemat att vara u 1 ; u 2 ; u 1 ; u 2 ; u 3 ; u 1 ; u 3 ; u 2 ; u 4 ; u 3. Av alla scheman som kan konstrueras med ett liknande flashcard-återinsättningsschema med hjälp av några strikt ökande återinsättningsfunktion rðk på med rð1 på > 1, är det detta schema, konstruerat med hjälp av rðk på 1⁄4 k på 1, som fortskrider genom däcket den långsammaste. Därför kallar vi detta schema "det långsamma snabbkortsschemat". I SI-texten visar vi att det långsamma snabbkortsschemat uppvisar oändligt perfekt inlärning med avseende på avståndsbegränsningarna med ða k ;b k 1⁄4 ðk;k 2. Således det långsamma flashcard schemat ger ett dramatiskt alternativ till recap schemat. Medan b k och b k - en k båda växte exponentiellt i k i recap schemat, här växer de kvadratiskt och ändå tillåter oändligt perfekt lärande. Numeriska simuleringar som visas i SI Text tyder på att detta schema i själva verket uppvisar oändligt perfekt lärande även med avseende på de mycket snävare avstånd begränsningar med ða k ;b k  på 1⁄4 ðk;2k. Om så är fallet, skulle kontrasten mot recap schemat vara ännu mer skarp. Avvägningen för denna långsamma tillväxt i b k är den hastighet med vilken kunskapsbasen växer. Medan t n, den tid som krävs för kunskapsbasen för att uppnå storlek n, växte som  på log n en i recap schemat, här begränsas den nedan av.. Ett bevis på detta kan hittas i SI-texten, tillsammans med numeriska bevis för att den faktiskt växer i takt med att den växer som.................................................................................................... Avståndsbegränsningarna i Recap-metoden och The Slow Flashcard-schemat är skräddarsydda för att möjliggöra existensbevis för att vissa gränser på t n, b k, och b k - en k kan uppnås i samband med oändligt perfekt lärande. De metoder som används för att beskriva scheman, dock, föreslår allmänna principer för hur man konstruerar scheman med önskvärda egenskaper. Dessutom noterar vi att scheman konstruerade är relevanta för varje uppsättning av avstånd begränsningar som är mer avslappnade än de givna: Om ett schema uppvisar oändligt perfekt lärande med avseende på avstånd begränsningar fða k ;b k  skag, då det också uppvisar oändligt perfekt lärande med avseende på fða 0 k ;b 0 k  till när en 0 k ≤ a k och b 0 k ≥ b k för alla k. I nästa avsnitt, Flexibla Studenter, börjar vi med en allmän klass av elever och bygga scheman skräddarsydda för varje enskild elev i klassen. Flexibla studenter. Hur är det då om den studerande inte alls behövde vänta för att få nytta av att studera? Med andra ord, tänk om en k 1⁄4 1 för alla k? I detta fall kan vi använda en teknik för att konstruera scheman som vi kallar "hold-build": sekvensera de utbildningsenheter som är kända för studenten i ett "holding mönster" så att de uppfyller avståndsbegränsningarna, samtidigt som de visar nya utbildningsenheter i snabb repetition (därigenom "bygga upp" dem). De enda antaganden som behövs för konstruktionen, förutom en k  på 1, är att b 1 ≥ 2 och att b k → ∞. (Observera att b k redan måste öka svagt.) Vi definierar sekvensen HB m att vara den oändliga sekvensen som börjar med u m, innehåller u m i varje annan post, och cyklar genom enheter u 1 ;...;u m−1 i de återstående posterna. Så till exempel HB 2 1⁄4 u 2 ;u 1 ;u 2 ;u 1 ;u 2 ;u 1 ;... HB 3 1⁄4 u 3 ;u 1 ;u 3 ;u 3 ;u 3 ;u 2 ;u 3 ;u 1 ;... HB 4 1⁄ 4 ;u 1 ;u 4 ;u 2 ;u 4 ;u 3 ;u 4 ;u 1 ;u 4 ;u 4 ;u 2 ;u 4 ;u 4 ;u 4 ;... Nu, överväga en godtycklig uppsättning av avstånd begränsningar sådan att en k 1 ≥ 2, och b k → ∞. För att underlätta diskussionen, säger vi att en utbildningsenhet är på nivå k när det har visats exakt k gånger. Vi konstruerar schemat som garanterar oändligt perfekt inlärning enligt följande. För det första, nuvarande enhet u 1. Sedan presentera enheter enligt HB 2. Hittills så bra; så länge enheter presenteras enligt HB 2, Vi vet att avstånd begränsningar kommer att uppfyllas, eftersom b k ≥ 2 för alla k. Under tiden, nivåerna för u 1 och u 2 kan byggas upp utan bindning. Fortsätt HB 2 så länge det är nödvändigt tills det är möjligt att gå vidare till HB 3. Med andra ord, visa tillräckligt av HB 2 så att om schemat fram till den punkten följdes av en obestämd körning av HB 3, då avståndsbegränsningarna skulle uppfyllas. Detta villkor är garanterat att vara sant efter ett begränsat antal tidssteg eftersom b k → ∞ och HB 2 är periodisk. Således, när tillräckligt av HB 2 har visats, visar vi så mycket av HB 3 som behövs tills vi har råd att gå vidare till HB 4. Sedan visar vi så mycket av HB 4 som behövs tills vi har råd att gå vidare till HB 5, och vi fortsätter att bygga schemat så här på obestämd tid. Schemat som bildas genom att konktenera hold-build mönster på detta sätt garanterar oändligt perfekt lärande, och det gäller alla uppsättningar av avstånd begränsningar med en k  på 1, b 1 ≥ 2, och b k → ❌. Således har vi faktiskt en klass av avstånd begränsningar där oändligt perfekt lärande är möjligt och ändå kan b k växa godtyckligt långsamt. Kompromissen för en ytterst långsamt växande b k kommer återigen att bli en snabbväxande t n, vilket motsvarar en långsam inlärningstakt. Den exakta hastigheten kommer att bero på den exakta tillväxthastigheten för b k. För att ge ett konkret exempel på denna hold-build konstruktion och en åtföljande beräkning av t n, kan vi överväga det enkla fallet där b k 1⁄4 k 1. (Observera att, eftersom vi bara kräver att b k är svagt ökande, det finns mycket långsammare växande val för b k än denna.) Sedan, genom att utföra konstruktionen ovan, har vi att sekvensen är u 1 ;u 2 ;u 1 ;u 2 ;u 1 ;u 2 ;flfflfflfflfflfflfflffl} HB 2 ;u 3 ;u 1 ;u 3 ;u 3 ;u 3 ;u 3 ;u 1 ;u 3 ;u 2 ;u 3 ;u 3 ;u 3 ;ffflfflfflfflfflfflfflfflfflffffl ffl} med 4k − 3 steg spenderas i HB k för varje k. Således, eftersom u jag kommer att införas ett steg efter att ha avslutat HB i−1 del av schemat, har vi att Tanken bakom hold-build konstruktion, nämligen metoden att sätta vissa enheter i ett holding mönster medan andra är perfekt inlärande 1 k − 3 steg spenderas i HB k för varje k. Således, eftersom u jag kommer att introduceras en gång steg efter att slutföra HB i−1 del av schemat, vi har att idén bakom hold-build konstruktion, nämligen att sätta några enheter i ett hold-flfflfflfffffffffffffffffffffffffffffffffffffffffffflfffffffl } Det är ett verktyg som kan användas för att skräddarsy utbildningsprocesser för att modellera studenter i allmänhet. Den Finicky Slow Studenten. Vi ger nu en uppsättning av avstånd begränsningar fða k ;b k  tillg för vilka inget schema kan uppvisa oändligt perfekt lärande. De är helt enkelt de begränsningar som definieras av en k 1⁄4 b k 1⁄4 k. Vi kallar denna uppsättning begränsningar "finicky slow student" eftersom b k - en k är så liten, och eftersom b k växer så långsamt som en funktion av k. Vi visar att inget schema kan uppvisa oändligt perfekt lärande med avseende på finicky slow student. Antag, för motsägelsens skull, att det fanns ett schema som visade ett oändligt perfekt lärande med avseende på den fåniga långsamma eleven. Vi säger att ett schema innehåller utbildningsenhet u i om enheten inträffar oändligt många gånger, och om sekvensen av händelser uppfyller avståndsbegränsningarna. Således, med tanke på detaljerna hos den finky långsamma studenten, om en enhet u i inkorporeras, och om det först inträffar i steg τ, då måste det också ske i steg τ 1, τ 3 τ 6 τ 10;.... Enligt planerna omfattar schemat oändligt många utbildningsenheter. Vi kan anta, utan förlust av allmängiltighet, att utbildningsenheten u 1 är inkorporerad och att dess första förekomst är vid tidpunkten steg τ 0 1⁄4 0. (Att låta tiden börja vid noll här gör det möjligt för renare beräkningar.) Då vet vi att u 1 också förekommer på exakt de steg τ 1, τ 2, τ 3 ;..., där τ i 1⁄4 i k1⁄41 a k. Det kommer att vara tillräckligt att visa att ingen annan enhet kan införlivas utan att skapa en schemaläggning konflikt-med andra ord, utan att behöva så småningom schemaläggas i ett steg av formuläret τ i. Antag att en annan enhet, kalla det u 2, införlivades, med sin första förekomst i steg s 0. Då vet vi att u 2 också måste ske på exakt de steg s 1, s 2, s 3 ;..., där s i 1⁄4 s 0  och i k1⁄41 a k. Vi visar att det måste finnas några steg gemensamt för båda sekvenserna fs i g och fτ i g. Således kommer vi att ha en motsägelse eftersom, som mest, en utbildningsenhet kan visas i varje post i schemat. Vi börjar med att notera att s i − τ i 1⁄4 s 0 för alla i, och att sålunda för tillräckligt stor k, vi har att τ kί1 > s k. Nu låt m vara det minsta antalet sådan att τ mί1 > s m. Vi vet m ≥ 1, eftersom τ 0 1⁄4 0 och τ 1 1⁄4 1 genom konstruktion. Vi hävdar att τ m 1⁄4 s m−1. Om τ m > s m-1, då m skulle inte vara det minsta antalet sådan att τ m-1 > s m (eftersom då m − 1 skulle också kvalificera), så τ m  pås m-1. Om τ m < s m−1, då har vi att τ m < s m-1 < s m < τ m-1, vilket innebär att s m − s m‐1 ≤ τ m-1 − τ m − 2, eftersom alla s i och τ i är heltal värderas. Således en m ≤ en m- 1 - 2, så en m- 1 - a m ≥ 2, vilket inte är möjligt eftersom en k- 1 - a k 1⁄ 4 1 för alla k. Så τ m- 1. Således har vi att τ m 1⁄4 s m−1, vilket är en motsägelse, naturligtvis, eftersom endast en utbildningsenhet kan schemaläggas för varje givet steg. Således kan inget schema uppvisa oändligt perfekt lärande med avseende på den fjantiga långsamma eleven; i själva verket, den fjantiga långsamma eleven tillåter inte ens att införliva mer än en utbildningsenhet. Detta bevis innehåller inte bara för avståndsbegränsningarna, där f ðk en heltalssekvens sådan att f ð1 på 1⁄4 1, f ðk på 0. 0. 1g, och f ðk på → ∞. Det exakta valet spelar ingen roll. Finickinessen (a k 1⁄4 b k ) och långsamheten [f ð1 ska 1⁄4 1 och f ðk ∂ 1 ska − f ðk på 0; 1 g] är tillräckliga för att utföra beviset som skrivet, men med det slutliga argumentet med hjälp av en kö1 − en k ≤ 1 i stället för en kö1 − en k 1⁄4 1. Kramande. Fokus hittills har varit på oändligt perfekt lärande, men det kan finnas mindre ambitiösa mål för en student. Vi riktar nu vår uppmärksamhet mot propp. I slutet av detta avsnitt tar vi upp frågan om hur mycket kramp kan göras under en viss tid. Vi börjar här med ett positivt resultat, visar att för varje positivt heltal n och varje uppsättning av avstånd begränsningar med b k → ❌, finns det en sekvens som uppnår begränsad inlärning av ordning n. Vi anser att en godtycklig uppsättning av avstånd begränsningar med b k → ❌ och gå vidare genom induktion på n. Det är klart att begränsad inlärning är möjligt för n 1⁄4 1; sekvensen består helt enkelt av u 1 uppfyller definitionen. Nu, låt S n vara en sekvens av längd T n som uppnår avgränsad inlärning av ordning n. För att slutföra induktionen, konstruerar vi en ny sekvens, S nc1 av längd T nc1, som uppnår avgränsad inlärning av ordning n 1. Kom ihåg från Flexible Students att nivån på en utbildningsenhet vid tid t i en sekvens är antalet gånger det har dykt upp före tid t. Grundidén bakom byggandet av S nc1 är att börja med att bygga upp nivån u 1 tills det är på en nivå m sådan att b m > T n. Sedan använder vi nästa T n steg för att presentera enheter u 2, u 3 ;...;u nc1 enligt sekvensen S n. När det görs, har tidsfristen för b m fortfarande inte uppnåtts för u 1, och därmed sekvensen uppfyller definitionen av avgränsat lärande av ordning n c 1. Formellt, låt m vara det minsta heltal sådan att b m > T n. Sedan presentera enhet u 1 vid tiden t 1⁄4 0 och ibland t 1⁄4  på j i1⁄41 a i för j 1⁄4 1,2;...;m − 1. Presentera en tom i sekvensen vid varje annan tidpunkt steg emellan. Sedan, med början vid tiden t 1⁄4 1  och 1 i1⁄41 a i, nuvarande enheter u 2 ;u 3 ;...;u nc1 enligt T n elementen i sekvensen S n. Denna sekvens, genom tiden T nc.1 1⁄4 T n  och 1 i1⁄41 a i, är vår nya sekvens S nc.1. Genom konstruktion uppfyller den villkoren för begränsad inlärning av ordning nr 1. Genom induktion, då, begränsad inlärning av ordning n är möjligt för alla positiva heltal n för varje uppsättning av avstånd begränsningar med b k → ❌. I konstruktionen ovan är det helt möjligt att en eller flera enheter skulle börja bryta mot avståndsbegränsningarna även ett steg senare. Det finns inte mycket annat som garanteras än de utbildningsenheter som har uppfyllt tidtabellsbegränsningarna fram till ett visst tidssteg. Vi kallar denna typ av konstruktion kramp eftersom det presenterar materialet med en viss måltid i sikte och utan hänsyn till schemaläggning av material efter denna måltid, som en student kramp för en slutexamen som inte oroar sig för hur mycket kommer att behållas efter testet. Villkor (ii) av vår definition av avgränsade lärande modeller begreppet att studera upp till en punkt i tiden och sedan kunna komma ihåg allt som studerades för minst en tid steg, som om det fanns en frågesport som varar en tid steg som skulle inträffa i tid steg omedelbart efter krampsekvensen. Vi skulle på liknande sätt kunna modellera begreppet en frågesport som varar d tid steg genom att kräva att om en enhet sista händelse är s tid steg från slutet av sekvensen, och enheten inträffar totalt k gånger i sekvensen, då s måste vara mindre än eller lika med b k. Vi noterar att våra resultat när det gäller kramp sekvenser kan anpassas till en sådan alternativ modell. Vi övergår nu till frågan om hur mycket som kan fyllas på en viss tid. Med tanke på en uppsättning av avstånd begränsningar fða k ;b k  skag, och ett positivt heltal T, kan vi sätta en övre gräns på de nummer n för vilka begränsad inlärning av ordning n är möjligt i T-tid steg. Om vi låter mði påvisar det minsta heltal k sådan att b k ≥ i, då kan det visas att n måste tillfredsställa Novikoff et al. PNAS Early Edition 5 av 6  till n i1⁄41 mði till ≤ T och  till mðn på 1 j1⁄41 a j  på n ≤ T. Varje ojämlikhet implicit begränsar n ovanifrån. Dessa gränser återspeglar de begränsningar som följer av det begränsade antalet tillgängliga tidssteg och de föreställningar som fa k g och fb k g utgör begränsningar av hur snabbt en utbildningsenhet kan byggas upp och hur länge man kan komma ihåg utbildningsenheterna. Detaljer finns i SI-texten. Trots de negativa konnotationer som är förknippade med kramp, kan grundidén faktiskt vara användbar i ett antal inställningar i verkliga livet. En resenär kan bara bry sig om att lära sig ett språk tillräckligt för att resa i ett främmande land bara en gång, till exempel, eller en artist kan bara behöva ha en viss färdighet inställd på dagen för en föreställning och inte nödvändigtvis efter det. Kanske kommer framtidens pedagogiska programvara att ha upplösbara parametrar som gör det möjligt för den studerande (eller läraren eller föräldern) att sätta upp målet för utbildningsprocessen. På så sätt kan programvaran inte bara anpassa sig till elevernas naturliga förmågor, utan också till deras personliga mål. Möjligheterna till framtida arbete verkar gränslösa. En mer fullständig teori om oändligt perfekt lärande kan vara ett mål. En sådan teori skulle omfatta fler tekniker för att bygga utbildningsprocesser som är skräddarsydda för studenter, och en mer komplett teori som relaterar en k och b k till den maximala takt med vilken modellen student kan tillfalla kunskap. Ett viktigt mål bör vara en verkligt anpassningsbar utbildningsprocess: en som anpassar sig till studenten i realtid. I denna uppsats modellerar vi till exempel utbildningsprocessen som en sekvens som är utformad för att uppfylla en uppsättning begränsningar som fastställts i förväg, men ett alternativt tillvägagångssätt skulle vara att testa studentens kunskaper under hela processen, och att schemat ska styras av en onlinealgoritm som väljer nästa enhet baserat på de svar som studenten har gett. Ett sådant system skulle vara en förebild för en lärare som iakttar elevernas framsteg innan han bestämde sig för vad han skulle undervisa härnäst. Att modellera denna situation skulle vara en spännande utmaning. Interaktionen mellan de två onlinealgoritmerna, en modellering av studenten och den andra modellering av läraren, lovar att vara komplex och fascinerande, och förhoppningsvis upplysande och användbar för framtida designers och ingenjörer av pedagogisk programvara. Det finns många möjligheter här för matematisk modellering, teoretiska beräkningar och numeriska simuleringar som belyser vad som gör en effektiv lärare och hur pedagogisk programvara kan anpassas i realtid till användarens beteende. Ett annat område för framtida arbete är design och analys av modeller som är skräddarsydda för specifika ämnen. Kanske en modell med ett nätverk av utbildningsenheter skulle kunna användas för att undersöka fenomenet att det ofta är lättare att lära sig en uppsättning fakta som på något sätt "stärker" varandra än en uppsättning orelaterade fakta. Att införa relationer mellan utbildningsenheterna kräver nya modeller för studentens mottagande av enheterna, vilket i sin tur kräver olika utbildningsprocesser. Ytterligare en forskningsväg är empiriskt arbete. Teknikerna och intuitionerna från det teoretiska arbetet bör användas för att skapa verklig utbildningsprogramvara. Då kan data från riktiga studenter samlas in och processen med att använda data för att validera och förfina modellerna kan börja. Slutligen skulle matematiken för hantering av avståndsbegränsningar i sekvenser kunna hitta ytterligare tillämpningar utöver dem som nämns ovan, till exempel för hantering av uppgifter vid parallell bearbetning eller studier av multitasking hos människor. De modeller som presenteras i denna uppsats är enkla och teoretiska. Designer av utbildningsprogramvara kommer sannolikt att behöva implementera modeller och algoritmer som är mer komplexa och anpassade till det utbildningsinnehåll som levereras. Det är vår förhoppning att arbetet med enkla teoretiska modeller kommer att utgöra grunden för intuition för designers av pedagogisk programvara, på ungefär samma sätt som algoritmisk spelteori gör för ingenjörer som arbetar i online annonsauktioner och andra relaterade områden. Med den nuvarande boomen i utbildningsprogram-för att inte tala om humanoid robot lärare industrin (14)-är det tydligt att det är dags att utveckla en teori om algoritmisk utbildning.
Ett anmärkningsvärt arbete i detta avseende är Novikoff et al. REF, som föreslår en teoretisk ram för rymdrepetition baserad på en uppsättning deterministiska operationer på en oändlig sträng av innehåll bitar.
Education of a model student
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Computer Science', 'Medicine']}