Op papier kunnen quantumcomputers een aantal rekenproblemen ordegroottes versnellen. Machine learning zou hiervan kunnen profiteren. Onderzoekers van onder meer Nasa onderzochten of de ‘quantum-annealers’ van D-Wave een simpele vraag kunnen beantwoorden: waar staan de bomen op luchtfoto’s van Californië?
Machine learning heeft de wereld van beeldverwerking aardig opgeschud dankzij de soms spectaculaire resultaten. De algoritmes hebben echter ook hun nadelen. Zo moeten er doorgaans grote hoeveelheden bekende voorbeeldgegevens beschikbaar zijn en is het trainen van dergelijke algoritmes vaak een rekenintensieve klus.
Een groep researchers van Nasa en enkele Amerikaanse universiteiten heeft onlangs gekeken of quantumcomputers een handje kunnen helpen bij dat laatste probleem. Hun onderzoek richtte zich op luchtfoto’s met een resolutie van beter dan een meter. De simpele vraag die ze wilden beantwoorden: welke pixels bevatten er bomen?
Het lijkt een eenvoudige vraag om te beantwoorden met software, maar luchtfoto’s kampen met een grote variatie in belichting, atmosferische omstandigheden, enzovoorts. Daarmee is het een uitgelezen toepassing voor machine learning, dat juist door het combineren van allerhande kleine hints een betrouwbaar oordeel kan vellen. Het aantal parameters dat moet worden ingesteld, loopt echter makkelijk in de duizenden en de datasets lopen in de gigabytes.
Het dal in
Gelukkig heeft Nasa de beschikking over een quantumcomputer: een systeem van het Canadese D-Wave met 1152 qubits. D-Wave is een beetje een vreemde eend in de bijt van de quantumcomputers. Waar de meeste spelers de machine nog als een toekomstig iets zien, hebben de Canadezen al werkende exemplaren staan bij klanten. Al een tijdje zelfs.
Device lifecycle management for fleets of IoT devices
Microchip gives insight on device management, what exactly is it, how to implement it and how to roll over the device management during the roll out phase when the products are in the field. Read more. .
Dat komt omdat de D-Wave-systemen geen ‘algemene’ quantumcomputers zijn, waar meestal op gedoeld wordt met de term. Ze zijn bedoeld voor een veel beperkter toepassingsdomein, dat aanzienlijk makkelijker te realiseren is. Het befaamde algoritme van Shor, dat onder meer snel getallen moet kunnen ontbinden, kan er niet op worden gebruikt en publieke-sleutelcryptografie heeft niets te vrezen van de Canadese aanpak.
D-Wave zelf heeft het over ‘quantum-annealers’. De term ‘annealing’, wat in het Nederlands zoiets als ‘nagloeien’ betekent, komt uit de metallurgie en duidt op een proces waarbij metaal van een hoge temperatuur via een strikt regime wordt afgekoeld om het kristallisatieproces in de hand te houden. Dat heeft allemaal niet zo veel te maken met D-Wave, maar dit metallurgische proces vormt de inspiratiebron voor simulated annealing, een optimalisatiealgoritme op klassieke computers waar D-Wave op voortborduurt.
Simulated annealing is gericht op het vinden van het globale minimum van een functie. Dit is een veelvoorkomend probleem in toepassingen uiteenlopend van kunstmatige intelligentie tot biochemie. Biologen die de vorm van een eiwit willen voorspellen, krijgen er bijvoorbeeld mee te maken. Eiwitten zijn lange ketens van een handvol verschillende aminozuren, en in het lichaam vouwen die zich vanzelf in een driedimensionale vorm zodanig dat er de minste spanningen op de structuur staan.
Het is echter zeer lastig om die vorm wiskundig te beredeneren. Een specifieke configuratie doorrekenen is simpel, maar de beste configuratie vinden niet: de enige manier is eigenlijk om een voor een elke mogelijke vorm door te rekenen. Het aantal berekeningen neemt exponentieel toe met het aantal aminozuren.
Er zijn algoritmes die dit proberen te omzeilen door iteratief naar de optimale vorm toe te stappen. Ze beginnen met een willekeurige vorm en rekenen hiervan de directe-buurconfiguraties door. Daaruit kiezen ze de meest gunstige en vervolgens calculeren ze daarvan alle omliggende configuraties. Zo wandelen ze in het landschap aan spanningsconfiguraties vanzelf stapje voor stapje het ‘dal’ in.
Aan deze aanpak kleeft een groot nadeel: dit soort landschappen zijn doorgaans zeer grillig en bevatten allerlei kleine pieken en dalen. Om in het allerlaagste dal te komen, moet je vaak eerst over een berg heen, maar dat kan het stap-algoritme niet weten zonder alle mogelijke configuraties door te rekenen.
Daarvoor is simulated annealing bedacht. Dit werkt grotendeels hetzelfde als het stap-algoritme, maar met het verschil dat er in het begin ook net zo goed tegen de berg opgeklommen mag worden. Naarmate de tijd vordert, wordt dit steeds minder toegestaan en uiteindelijk mag het algoritme alleen nog maar bergafwaarts lopen.
De overeenkomst met de metallurgie is het gecontroleerd terugbrengen van een ‘temperatuur’-parameter. Deze waarde bepaalt in welke mate het algoritme in een ongunstige richting mag bewegen. Door die waarde aan het begin hoog te houden, kan het algoritme de oplossingsruimte vrijelijk verkennen. In de loop van de tijd wordt de temperatuur-parameter gecontroleerd teruggebracht, zodat het algoritme steeds meer blijft hangen in de dalen.
De aanpak werkt vrij goed, maar is wel een compromis: het resultaat is vrij waarschijnlijk het globale minimum, maar zeker is dat niet. Voor de meeste toepassingen is dat goed genoeg. Het algoritme kan desnoods een paar keer worden herhaald om meer zekerheid te krijgen. Dat is altijd nog beter dan alles klakkeloos doorrekenen.
Geavanceerd experiment
D-Wave voert hier een quantumvariant van uit. De machines richten zich op hetzelfde probleemdomein, geven ook een probabilistisch antwoord en gebruiken bovendien een soort proces dat de omstandigheden gecontroleerd verandert.
De systemen bestaan uit netwerken van qubits die zich in het begin allemaal bevinden in een willekeurige superpositie van 0 en 1: een waarde die hun kans bepaalt op een van de twee waarden wanneer ze uiteindelijk worden gemeten. Heel gecontroleerd worden de omgevingsomstandigheden veranderd en worden de qubits als het ware gedwongen hun keuze te maken. Daarbij oefenen ze echter invloed uit op elkaar. Door die onderlinge invloed juist in te stellen, is het antwoord op het vraagstuk verscholen in de waardes die ze uiteindelijk aannemen (zie kader).
Het grote voordeel van de quantumaanpak is dat de bergen in het landschap geen probleem vormen: het algoritme kan er door het quantumtunneling-verschijnsel dwars doorheen. Daarmee moet het systeem ordegroottes sneller werken dan de stapsgewijze aanpak op een klassieke computer.
Voorlopig komt daar nog maar weinig van terecht. De systemen bevatten nog te weinig qubits om de problemen aan te kunnen waar klassieke computers op stuklopen. Bovendien moet het uitvoeren van een programma op een quantum-annealer nog altijd meer worden gezien als een geavanceerd experiment dan het opstarten van een stukje software op een computer.
De quantumprocessor werkt bij temperaturen vlak boven het absolute nulpunt en vereist een forse installatie met koeling, supergeleidende structuren, afscherming van radiogolven, enzovoorts – al wel helemaal geïndustrialiseerd door D-Wave overigens. Daarbij lukt het om de quantumtoestand twintig tot dertig microseconden vast te houden, dus dat is de maximale runtime van een berekening. Maar met koelen, initialiseren, uitlezen en dergelijke erbij duurt een experiment veel langer.
Dertig microseconden
De Amerikaanse onderzoekers keken of ze quantum annealing kunnen gebruiken voor een boosting-algoritme, een machine learning-techniek waarbij het oordeel van een aantal matige, op zichzelf staande classifiers bij elkaar wordt geveegd om een veel betrouwbaardere uitkomst te krijgen. De leerfase bestaat eruit dat met een lading bekende voorbeelden wordt bepaald hoeveel elke individuele classifier moet bijdragen aan het eindantwoord.
Aan de deelclassifiers was niks quantum; hiervoor werden in feite simpele drempelwaarden ingezet. Als bijvoorbeeld de intensiteit van de kleur groen in een stukje van het beeld boven de drempelwaarde uitkomt, wordt het beeld als ‘met bomen’ bestempeld. Een volgende classifier kan kijken naar de textuur van een pixelblokje. Allemaal niet erg betrouwbaar, maar door ze samen te voegen, wordt de voorspelling een stuk beter.
Om de invloed van elke classifier te bepalen, moet een kostenfunctie worden opgesteld die voor elk van de voorbeelden uitrekent hoeveel de gezamenlijke voorspelling ernaast zit. Daarmee worden tijdens het trainen de parameters stapje voor stapje bijgesteld om deze fout te minimaliseren.
Het bleek dat die kostenfunctie zich makkelijk laat herschrijven naar een vergelijking voor de D-Wave-computer: de versterkingsfactoren hierin werden ingesteld op de mate waarin elke classifier overeenkomt met het gewenste resultaat, en de onderlinge invloed op de mate waarin twee classifiers overeenkomen (als ze sterk correleren, zijn ze redundant en moet er maar een worden meegeteld).
Wanneer dit in de D-Wave-processor wordt geplugd, rolt er een bitpatroon uit dat bepaalt hoeveel elke classifier moet worden meegewogen in het eindresultaat. Of eigenlijk: óf antwoorden wel en niet meegeteld moeten worden – een 0 voor niet, een 1 voor wel.
Binnen dertig microseconden hadden de onderzoekers steeds een antwoord. En die waarden bleken heel aardig te werken, met succespercentages rond de negentig procent. De getrainde verzamel-classifier is bovendien compact en gebruikt relatief weinig cpu-tijd. De onderzoekers denken dat de resultaten nog verder te verbeteren zijn door het aantal deelclassifiers te vergroten.
Maar of het nou echt bruikbaar is? Het onderzoek werd uitgevoerd als onderdeel van de ontwikkeling van een groter platform voor het classificeren van luchtfoto’s. Binnen dat kader was al een diep neuraal netwerk ontwikkeld dat beter werkt dan de boosting-aanpak. Volgens de onderzoekers zal het nut van de quantumcomputer voor machine learning dan ook sterk afhangen van de ontwikkelingen die de technologie de komende jaren doormaakt.