Hjärnan tolkar tvetydig sensorisk information snabbare och mer tillförlitligt än moderna datorer, med hjälp av neuroner som är långsammare och mindre tillförlitliga än logiska portar. Men Bayesian inference, som ligger till grund för många beräkningsmodeller av perception och kognition, verkar computationally utmanande även med tanke på moderna transistor hastigheter och energibudgetar. De beräkningsprinciper och strukturer som behövs för att minska denna klyfta är okända. Här visar vi hur man bygger snabba Bayesian datorer med avsiktligt stokastiska, digitala delar, minska denna effektivitet gap genom flera storleksordningar. Vi finner att genom att ansluta stokastiska digitala komponenter enligt enkla matematiska regler, kan man bygga massivt parallella, låga precisionskretsar som löser Bayesian inference problem och är kompatibla med Poisson avfyra statistik över kortikala neuroner. Vi utvärderar kretsar för djup och rörelse perception, perceptuell inlärning och orsakssamband, varje utför inference över 10 000+ latenta variabler i realtid - en 1000x hastighet fördel jämfört med råvaror mikroprocessorer. Dessa resultat tyder på en ny roll för slumpmässighet i konstruktion och omvänd konstruktion av intelligent beräkning. Vår förmåga att se, tänka och agera beror på vårt sinnes förmåga att bearbeta osäker information och identifiera sannolika förklaringar till i sig tvetydiga data. Många beräkningsmodeller av uppfattningen av rörelse 1, motorinlärning 2, högre nivå kognition 3, 4 och kognitiv utveckling 5 bygger på Bayesian inference i rika, flexibla probabilistiska modeller i världen. Maskinintelligenssystem, inklusive Watson 6, autonoma fordon 7 och andra robotar 8 och Kinect 9 system för gestural kontroll av videospel, är också alla beroende av probabilistiska slutsatser för att lösa tvetydigheter i deras sensoriska ingång. Men hjärnor löser dessa problem med större hastighet än moderna datorer, med hjälp av informationsbearbetningsenheter som är storleksordningar långsammare och mindre tillförlitliga än de växlande elementen i de tidigaste elektroniska datorer. Den ursprungliga UNIVAC I körde på 2,25 MHz 10, och RAM från tjugo år sedan hade en bit fel per 256 MB per månad 11. I kontrast, de snabbaste neuronerna i mänskliga hjärnor fungerar på mindre än 1 kHz, och synapsöverföringen kan helt misslyckas upp till 50% av tiden 12. Denna effektivitetsklyfta utgör en grundläggande utmaning för datavetenskapen. Hur är det möjligt att lösa probabilistiska inferensproblem med en effektivitet som börjar närma sig hjärnans problem? Här introducerar vi avsiktligt stokastiska men fortfarande digitala kretselement, tillsammans med kompositionslagar och designregler, som tillsammans minskar effektivitetsgapet genom flera storleksordningar. Vår strategi bygger både på och avviker från principerna bakom digital logik. Liksom traditionella digitala portar konsumerar och producerar stokastiska digitala portar diskreta symboler, som kan representeras via binära nummer. Även som digitala logik grindar, våra kretselement kan komponeras 2 och abstrakteras via enkla matematiska regler, vilket ger större beräkningsenheter som vars beteende kan analyseras i termer av deras komponenter. Vi beskriver primitiva och designregler för både statslösa och synkront urkopplade kretsar. Men till skillnad från digitala portar och kretsar är våra portar och kretsar avsiktligt stokastiska: varje utgång är ett prov från en sannolikhetsfördelning betingad på ingångarna, och (utom i degenererade fall) simulerar en krets två gånger kommer att producera olika resultat. De numeriska sannolikhetsfördelningarna själva är implicita, även om de kan uppskattas via kretsarnas långsiktiga tidsmedelvärde beteende. Och även till skillnad från digitala portar och kretsar, Bayesian resonemang uppstår naturligt via dynamiken i våra synkront klockade kretsar, helt enkelt genom att fastställa värdena för de kretselement som representerar data. Vi har byggt prototypkretsar som löser problem med djup- och rörelseuppfattning och perceptuell inlärning, plus en kompilator som automatiskt kan generera kretsar för att lösa problem med orsakssamband med en beskrivning av den underliggande kausalmodellen. Vart och ett av dessa system illustrerar användningen av stokastiska digitala kretsar för att påskynda Bayesian inference en viktig klass av probabilistiska modeller, inklusive Markov Random Fields, nonparametric Bayesian mixing modeller, och Bayesian nätverk. Våra prototyper visar att denna kombination av enkla val på hårdvarunivå - en diskret, digital representation för information, tillsammans med avsiktligt stokastiska snarare än idealt deterministiska element - har långtgående arkitektoniska konsekvenser. Till exempel, programimplementeringar av approximativa Bayesian resonemang är vanligtvis beroende av högprecision aritmetisk och seriell beräkning. Vi visar att våra synkrona stokastiska kretsar kan implementeras med mycket låg precision, vilket endast medför en försumbar minskning av noggrannheten. Denna låga precision gör att vi kan göra snabba, små, effekteffektiva kretsar i kärnan av våra konstruktioner. Vi visar också att dessa minskningar av datorenhetens storlek är tillräckliga för att vi ska kunna utnyttja den massiva parallellism som alltid har varit inneboende i komplexa probabilistiska modeller vid en granularitet som tidigare varit omöjlig att utnyttja. Den resulterande höga beräkning densitet driver prestandavinster vi ser från stokastiska digitala kretsar, minska effektivitet gapet med neural beräkning av flera storleksordningar. Vårt tillvägagångssätt skiljer sig i grunden från befintliga metoder för tillförlitlig beräkning med opålitliga komponenter [13] [14] [15], som antingen betraktar slumpmässighet som en felkälla vars inverkan behöver mildras eller som en mekanism för att approximera aritmetiska beräkningar. Våra kombinerade kretsar är avsiktligt stokastiska, och vi är beroende av att de producerar exakta prover från de sannolikhetsfördelningar de representerar. Vårt tillvägagångssätt skiljer sig också från och bygger på slutsatsen i en icke-parametrisk Bayesisk modell för vilken trosförökning inte är tillämplig. Dessutom, eftersom stokastiska digitala kretsar producerar prover snarare än sannolikheter, deras resultat fångar de komplexa beroenden mellan variabler i multi-modal sannolikhetsfördelningar, och kan också användas för att lösa annars svårhanterliga problem i beslutsteori genom att uppskatta förväntade verktyg. del från de sammansättningslagar som de stöder, som visas i figur 1B. Utgången från en grind kan anslutas till en annan ports ingång, vilket ger en krets som tar prover från sammansättningen av booleska funktioner som representeras av varje port. Den sammansatta kretsen kan också behandlas som en ny primitiv, abstraktion bort sin inre struktur. Dessa enkla lagar har visat sig förvånansvärt kraftfulla: de gör det möjligt att bygga upp komplexa kretsar av återanvändbara bitar. Stochastic digitala grindar (se figur 1C ) liknar booleska grindar, men förbrukar en källa av slumpmässiga bitar för att generera prover från villkorliga sannolikhetsfördelningar. Stochastic grindar är 5 specificerade av villkorliga sannolikhetstabeller; dessa ger sannolikheten att en given utgång kommer att resultera från en given inmatning. Digital logik motsvarar det degenererade fallet där alla sannolikheter är 0 eller 1; se figur 1D för den villkorliga sannolikhetstabellen för en AND-port. Många stokastiska grindar med m ingångsbitar och n utgångsbitar är möjliga. Figur 1E visar ett centralt exempel, THETA-porten, som genererar dragningar från ett fördomsfritt mynt vars fördomsfullhet anges på inmatningen. Kompletterande material som beskriver seriella och parallella implementationer finns på 26. Avgörande, stochastic grindar stöder generaliseringar av sammansättningen lagar från digital logik, visas i Figur 1F. Utgången från en stokastisk grind kan matas som ingång till en annan, vilket ger prover från den gemensamma sannolikhetsfördelningen över de slumpmässiga variabler som simuleras av varje grind. Den sammansatta kretsen kan också behandlas som en ny primitiv som genererar prover från den marginella fördelningen av den slutliga produktionen med tanke på den första inmatningen. Precis som med digitala portar kan en enorm variation av kretsar byggas med hjälp av dessa enkla regler. De flesta digitala system är baserade på deterministiska ändliga tillstånd maskiner; mallen för dessa maskiner visas i Figur 2A. En statslös digital krets kodar den övergångsfunktion som beräknar nästa tillstånd från det tidigare tillståndet, och urtagningsmaskineriet (som inte visas) itererar övergångsfunktionen upprepade gånger. Denna abstraktion har visat sig vara oerhört givande; de första mikroprocessorerna hade ungefär 2 20 olika tillstånd. I figur 2B visar vi den stokastiska analogen av denna synkrona tillståndsmaskin: en stokastisk övergångskrets. Vi kan skala upp till utmanande problem genom att utnyttja de kompositionslagar som stokastiska övergångskretsar stöder. Överväga en sannolikhetsfördelning definierad över tre variabler P (A, B, C) = P (A)P (B på A)P (C på A). Vi kan konstruera en övergångskrets som prover från det övergripande tillståndet (A, B, C) genom att komponera övergångskretsar för uppdatering av A-BC, B-A och C-A; denna sammansättning visas i figur 2C. Så länge som den underliggande sannolikhetsmodellen inte har några noll-sannolikhet tillstånd, ergodisk konvergens av varje beståndsdel övergångskrets då innebär ergod konvergens av hela montering 29. Det enda kravet för schemaläggning övergångar är att varje krets måste lämnas fast medan kretsar för variabler som interagerar med den är övergångar. Detta schemaläggningskrav -att en övergångskretss värde hålls fast medan andra som läser från sitt inre tillstånd eller fungerar som ingångar till sin nästa övergång uppdateras - är jämförbart med den så kallade "dynamiska disciplinen" som definierar giltiga klockscheman för traditionell sekventiell 7 logik 30. Deterministiska och stokastiska scheman, genomförande cykel eller blandning hybridkärnor 29, är båda möjliga. Denna enkla regel innebär också en enorm mängd exploaterbar parallellism i stokastiska övergångskretsar: om två variabler orsakas självständigt med tanke på den nuvarande inställningen av alla andra, kan de uppdateras samtidigt. Samlingar av stokastiska övergångskretsar implementerar Bayesian resonemang på ett enkelt sätt: genom att fixera, eller "klämma" några av variablerna i enheten. Om inga variabler är fixerade, utforskar kretsen hela den gemensamma fördelningen, som visas i figur 2E och 2F. Om en variabel är fast utforskar kretsen den villkorliga fördelningen på de återstående variablerna, som visas i figur 2G och 2H. Enkelt genom att ändra vilka övergångskretsar uppdateras, kretsen kan användas för att svara på olika probabilistiska frågor; dessa kan varieras online baserat på behoven i ansökan. ( Figur 2 här omkring.) Noggrannheten hos ultra-lågprecision stokastiska övergångskretsar. som genererar drar från en diskret sannolikhetsfördelning för output vars vikt anges på dess ingång. Till exempel, i Gibbs provtagning, denna fördelning är den villkorliga sannolikheten för en variabel med tanke på det aktuella värdet av alla andra variabler som är direkt beroende av det. Ett genomförande av denna operation visas i figur 3A; varje stokastisk övergångskrets från figur 2 kan genomföras av en sådan krets, med multiplexers för att välja log-sannolikhet värden baserat på 8 grannarna i varje slumpmässig variabel. Eftersom endast förhållandet mellan de råa sannolikheterna materia, och sannolikheterna själva naturligtvis varierar på en log skala, extremt låg precision representationer kan fortfarande ge exakta resultat. Hög entropi (dvs. nästan enhetliga) distributioner är motståndskraftiga mot trunkering eftersom deras värden är nästan lika till att börja med, skiljer sig endast något i fråga om deras låg-order bitar. Låg entropi (dvs. Nästan deterministiska) distributioner är motståndskraftiga eftersom trunkering sannolikt inte kommer att förändras vilka resultat som har icke-noll sannolikhet. Figur 3B kvantifierar denna egenskap med låga precisioner, vilket visar den relativa entropin (ett kanoniskt mått på skillnaden mellan två fördelningar) mellan utsignaldistributionerna av implementationer med låg precision av kretsen från figur 3A och ett korrekt genomförande med flyttal. Diskreta fördelningar på 1000 utfall användes, som spänner över hela skalan av möjliga entropier, från nästan 10 bitar (för en enhetlig fördelning på 1000 utfall) till 0 bitar (för en deterministisk distribution), med fel nästan odetekterbara tills färre än 8 bitar används. Figur 3C visar exempelfördelningar på 10 utfall, och figur 3D visar den resulterande effekten på dataelementets storlek. Omfattande kvantitativa bedömningar av inverkan av låg bit precision har också utförts, vilket ger ytterligare bevis för att endast mycket låg precision krävs 26. ( Figur 3 ungefär här.) Effektivitetsvinster på djup och rörelseuppfattning och perceptuella inlärningsproblem Våra huvudsakliga resultat är baserade på en implementering där varje stokastisk grind simuleras med hjälp av digital logik, konsumerar entropi från en intern pseudorandom nummergenerator 31. Detta gör det möjligt för oss att mäta prestanda och feltolerans förbättringar som härrör från stokastiska arkitekturer, oberoende av fysisk implementering. Vi finner att stokastiska kretsar gör det praktiskt att utföra stokastisk inferens över flera probabilistiska modeller med 10 000+ latenta variabler i realtid och vid låg effekt på ett enda chip. Dessa konstruktioner uppnår en 1000x hastighet fördel jämfört med råvaror mikroprocessorer, trots att använda grindar som är 10x långsammare. I 26, Vi visar också arkitekturer som uppvisar minimal försämring av noggrannhet i närvaro av felfrekvenser så hög som en bit fel för varje 100 tillstånd övergångar, i motsats till konventionella arkitekturer där felfrekvenser mäts i bitfel (fel) per miljard timmars drift 32. Vår första ansökan är att djup och rörelse perception, via Bayesian inference in lattice Markov Random Field modeller 28. Kärnproblemet är att matcha pixlar från två bilder av samma scen, tagna vid distinkta men närliggande punkter i rymden eller i tid. Matchningen är tvetydig på grundval av bilderna ensam, som flera pixlar kan dela samma värde 33 ; förkunskaper om strukturen på scenen måste tillämpas, som ofta kastas i termer av Bayesian inference 34. Figur 4A illustrerar den mallprobabilistiska modell som används mest. X-variablerna innehåller de okända vektorerna för förskjutning. Varje Y-variabel innehåller en vektor av pixellikviditetsmätningar, en per möjligt par matchade pixlar baserat på X. De parvisa potentialerna mellan X-variablerna kodar scenstrukturantaganden; i typiska problem antas okända värden variera jämnt över scenen, med ett litet antal diskontinuiteter vid objektens gränser. Figur 4B visar den villkorliga självständighetsstrukturen i detta problem: varannan X-variabel är oberoende av varandra, vilket gör det möjligt att uppdatera hela Markovkedjan över X-variablerna i en tvåfasklocka, oberoende av latticestorlek. Figur 4C visar 10 dataflödet för den programmerbara probabilistiska videoprocessorn vi utvecklade för att lösa denna familj av problem; denna processor tar en problemspecifikation baserad på pairwise potentialer och Y-värden, och producerar en ström av bakre prover. När vi jämför hårdvaran med handoptimerade C-versioner på en varuarbetsplats ser vi en prestandaförbättring på 500x. ( Figur 4 ungefär här.) Vi har också byggt stokastiska arkitekturer för att lösa perceptuella inlärningsproblem, baserat på helt Bayesian inference i Dirichlet process blandning modeller 35, 36. Dirichlet process blandningar gör det möjligt att antalet kluster i en perceptuell datauppsättning automatiskt upptäckas under inferens, utan att anta en priori gräns på modellernas komplexitet, och utgör grunden för många modeller av mänsklig kategorisering 37, 38. Vi testade vår prototyp på problemet med att upptäcka och klassificera handskrivna siffror från binära indatabilder. Vår krets för att lösa detta problem fungerar på en online dataström, och effektivt spårar antalet perceptuella kluster denna ingång; se 26 för arkitektoniska och genomförande detaljer och ytterligare karakteriseringar av prestanda. Som med vår djup och rörelse perception arkitektur, observerar vi över 2000x speedups jämfört med en högt optimerad programvara implementation. Av skillnaden på 2000x i hastighet, är ungefär 256x direkt på grund av parallellism -alla pixlar är oberoende dimensioner, och kan därför uppdateras samtidigt. ( Figur 5 ungefär här.) Automatiskt genererade kausala resonemang kretsar och spikning implementationer Digital logik grindar och deras tillhörande design regler är så enkla att kretsar för många problem kan genereras automatiskt. Digital logik ger också ett gemensamt mål för enhetsingenjörer, och har implementerats med hjälp av många olika fysiska mekanismer - klassiskt med vakuumrör, sedan med MFOSETS i kisel, och även på spintroniska enheter 39. Här ger vi två illustrationer av den analoga enkelheten och generaliteten av stokastiska digitala kretsar, båda relevanta för omvänd-engineering av intelligent beräkning i hjärnan. Vi har byggt en kompilator som automatiskt kan generera kretsar för att lösa godtyckliga orsaker Denna spikning implementation hjälper till att minska klyftan med de senaste teorierna inom beräknings neurovetenskap. Till exempel har det nyligen föreslagits att neurala spikar motsvarar prover 41, och att vissa spontana spikning aktivitet motsvarar provtagning från hjärnans oklämda tidigare distribution 42. Att kombinera dessa lokala element med hjälp av vår sammansättning och abstraktion lagar i massivt parallella, lågprecision, avsiktligt stokastiska kretsar kan bidra till att överbrygga klyftan mellan probabilistiska teorier om neural beräkning och beräkningskrav av komplexa probabilistiska modeller och ungefärlig inference 43. ( Figur 6 ungefär här.) 13 För att ytterligare minska effektivitetsklyftan med hjärnan, och skala till mer utmanande Bayesian inference problem, måste vi förbättra konvergensen i våra arkitekturer. Ett tillvägagångssätt skulle vara att initiera tillståndet i en övergångskrets via en separat, feed-forward, kombinerad krets som approximerar jämviktsfördelningen i Markovkedjan. Maskinuppfattning programvara som använder maskininlärning för att konstruera snabba, kompakta initializers är redan i bruk 9. Analysera antalet övergångar som behövs för att minska klyftan mellan en god initiering och målfördelningen kan vara svårare 44. Vissa feedfore Monte Carlo slutsatser strategier för Bayesian nätverk tydligt ge exakta uppskattningar av sannolikheter i polynom tid om den underliggande sannolikhetsmodellen är tillräckligt stokastisk 45; det återstår att se om liknande villkor gäller för stateful stochastic övergångskretsar. Det kan också vara givande att söka efter nya elektroniska apparater - eller tidigare oanvändbara dynamiska system av befintliga apparater - som är lika väl anpassade till behoven hos avsiktligt stokastiska kretsar som transistorer är till logiska inverterare, eventuellt även genom en spikning genomförande. Fysiska fenomen som visade sig alltför opålitliga för att genomföra booleska logiska grindar kan vara livskraftiga byggstenar för maskiner som utför Bayesian inference. Datorteknik har hittills fokuserat på deterministiska mekanismer av anmärkningsvärd omfattning och komplexitet: biljoner delar som förväntas göra biljoner statsövergångar med perfekt repeterbarhet 46. Men vi är nu konstruerade datorsystem för att uppvisa mer intelligens än de en gång gjorde, och identifiera sannolika förklaringar för bullriga, tvetydiga data, hämtade från stora 14 utrymmen av möjligheter, snarare än att beräkna de definitiva konsekvenserna av perfekt kända antaganden med hög precision. Den skenbara intractabilityen av probabilistic inference har komplicerat dessa ansträngningar, och utmanade livskraften av Bayesian resonemang som en grund för att konstruera intelligent beräkning och för omvänd-engineering sinnet och hjärnan. Samtidigt har det blivit allt dyrare att bevara illusionen om bergfast determinism. Ingenjörer försöker nu bygga digitala logiska kretsar i den djupa submikron regim 47 och även inuti celler 48; i båda dessa inställningar, den underliggande fysiken har stokasticitet som är svårt att undertrycka. Energibudgetarna har blivit allt mer begränsade, från omfattningen av datacenter 49 till den mobila enheten 50, men vi spenderar betydande energi för att driva transistorer i deterministiska regimer. Och ansträngningar att förstå dynamiken i biologisk beräkning - från biologiska neurala nätverk till genuttryck nätverk 51 - har alla stött på stokastiskt beteende som är svårt att förklara i deterministiska, digitala termer. Våra avsiktligt stokastiska digitala kretselement och stokastiska datorarkitekturer föreslår en ny riktning för att förena dessa trender, och möjliggör utformningen av en ny klass av snabba, Bayesian digitala datorer.
I REF baseras kretsarna på byggstenar som utför operationer (t.ex. normalisering) genom att utvärdera matematiska uttryck med dedikerad hårdvara eller genom att använda förmonterade tabeller.
Building fast Bayesian computing machines out of intentionally stochastic, digital parts
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}