Toevalscomputer klopt gangbare computer met factor duizend bij patroonherkenning

Stochastische computers zijn in de jaren zeventig afgedaan als een dood spoor. Onterecht, zeggen computerwetenschappers. Hun unieke eigenschappen maken ze voor enkele taken verre superieur aan standaard computers en maken bijvoorbeeld automatische voertuigen mogelijk.

Hoe werken stochastische computers?
We kennen allemaal digitale computers, computers, die met nullen en enen rekenen. Alle berekeningen op een standaard computer komen neer op optellen en enkele simpele, zogeheten Booleanse logische bewerkingen.

De RASCEL_stochastische_computer uit 1969. Stochastische computers zijn nu vrijwel uitgestorven. Terecht? Bron: Wikipedia Commons

Stochastische computers, voor het eerst voorgesteld door de geniale John von Neumann in 1953,  werken niet met bits en bytes, maar met stromen data van een toevalsgenerator, bijvoorbeeld een kwantumsysteem. Deze datastromen bestaan uit nullen en enen met een bepaalde waarschijnlijkheid van een 1. Als de waarschijnlijkheid van een 1 in de datastroom bijvoorbeeld 0,6 is, dan komen er gemiddeld 3 enen op 2 nullen voor. Deze nullen en enen mogen willekeurig gegroepeerd zijn, zolang hun verhouding maar hetzelfde blijft.

Op het eerste  gezicht lijkt het absurd om met toevallige data te willen rekenen. De stochastische computer heeft ten opzichte van de digitale computer echter enkele voordelen. Ten eerste is er de grotere ongevoeligheid voor ruis. De kansverdeling van een datastroom wordt immers nauwelijks beïnvloed als er af en toe een één in een nul verandert of andersom, terwijl slechts één foutje voldoende is om een digitale computer lam te leggen. Kortom: stochastische computers in bijvoorbeeld ruimtevaartuigen die voortdurend bloot worden gesteld aan kosmische straling zouden wel eens veel stabieler kunnen zijn dan digitale computers.

Een tweede groot voordeel is dat de stochastische computer even makkelijk optelt als vermenigvuldigt. Voor een digitale computer stijgt het aantal benodigde berekeningen kwadratisch als beide operatoren twee keer zoveel cijfers krijgen. Voor de stochastische computer wordt deze net als bij optellen slechts twee keer zo groot. De reden: vermenigvuldigen van twee kansen, bijvoorbeeld 0,25 en 0,7, komt neer op het tellen van het aantal malen dat er in beide toevalsstromen een 1 voorkomt. Dit kan met een simpele AND-check (die hier zou uitwijzen dat in 0,175 deel van de gevallen beide stromen tegelijk een 1 opleveren).

Er is echter een belangrijk nadeel. Toevalsgetallen, zoals statistische variabelen, kunnen alleen nauwkeurig worden gelezen door heel veel metingen. Erg onpraktisch en de reden dat je dit stukje niet op een stochastische computer, maar op een snelle digitale computer leest.

Toevalscomputer berekent snelste weg
Vicente Jose Canals en zijn collega’s van de groep Electronic Systems van de Universiteit van de Balearische Eilanden in Palma de Mallorca laten een goed voorbeeld zien. Als mensen van een kleine, geïsoleerde universiteit zijn ze niet bang originele ideeën te proberen. Ze hebben stochastische rekenmethodes toegepast voor patroonherkenning. Het probleem hier is een inputsignaal (de te herkennen data) te vergelijken met een referentiesignaal (het patroon) om vast te stellen of deze overeen komen. In de echte wereld komt er nogal wat ruis voor in inputsignalen, waardoor de grote ruistolerantie van stochastische computers grote voordelen heeft. Canals en zijn collega’s gebruiken hun techniek om een zelfsturend voertuigje door een eenvoudige omgeving te loodsen waarvoor het beschikt over een interne kaart. Voor deze taak moest het de afstanden tot de muren meten en bepalen waar het precies is op de kaart. Het berekent vervolgens de optimale route naar zijn bestemming.

De groep beweert dat hun voertuig in verschillende tests de optimale route berekende die het moest nemen. Helaas publiceerden ze niet de details van hoe ze dit voor elkaar kregen – een zwak punt dat mogelijk systematische fouten maskeert.

Parallelle verwerking compenseert langzame werking
Volgens Canals en zijn groep werkt een conventionele chip zeventig maal sneller dan een stochastische chip, maar kan een conventionele chip alleen signalen sequentieel, achter elkaar dus, verwerken. Een stochastische chip kan echter de signalen tegelijkertijd verwerken, wat de chip drie ordes van grootte (duizenden malen) sneller maakt dan een conventionele chip in het oplossen van de patroonherkenningstaak. Een enorme verbetering. Toch zou ons dit niet moeten verrassen. Immers, denken veel hersenonderzoekers, ook ons brein heeft veel trekjes van een stochastische computer. Voortdurend geven neuronen korte stroomstootjes af in een bepaalde frequentie. Zou dit de sleutel zijn tot veel krachtiger hardware?

Bron
Vincent Canals et al., Stochastic-Based Pattern Recognition Analysis, ArXiv (2012)