Kunstmatige intelligentie blogreeks: Het probleem van de meerarmige bandieten

554Views
80 Shares

Welkom bij het zesde artikel in de blogreeks “Kunstmatige intelligentie”. Het vijfde deel gaat over “Het theorema van Bayes”. In dit deel wordt ingegaan op het probleem wat wordt besproken in hoofdstuk 6: Het probleem van de meerarmige bandieten.

6. HET PROBLEEM VAN DE MEERARMIGE BANDIETEN

Systemen met kunstmatige intelligentie moeten in de praktijk constant een afweging maken tussen leren en optimaal presteren. Een systeem dat altijd probeert de optimale keuze te maken met de informatie die op dat moment beschikbaar is, zal zelden iets nieuws proberen. Terwijl iets nieuws, uit een onverwachte hoek, misschien zelfs nog beter kan werken dan de beste keuze die we nu kennen. Dit is een afweging tussen ‘exploratie’, het verkennen van alle mogelijkheden, en ‘exploitatie’, het gebruiken van de huidige kennis om optimaal te presteren.

Bespeel het casino

Je hebt ze vast wel eens gezien, in een casino, of in een hoekje van een café: gokautomaten. Je gooit een munt in de machine, drukt op de knop en als je geluk hebt, stopt het scherm op precies de juiste plaatjes. Bingo! In het Engels worden deze apparaten ook wel one-armed bandits genoemd. De ‘ene arm’ komt van de grote hendel waarmee je oudere versies van het apparaat vaak bediende. De bijnaam ‘bandiet’ komt van het feit dat je portemonnee in een mum van tijd leeg raakt als je te veel speelt. Helaas vallen de plaatjes vaker verkeerd dan goed.

In een casino heb je vaak hele rijen van dit soort one-armed bandits. Stel je eens voor dat je in een casino de kans krijgt om een vast bedrag te besteden aan de verschillende automaten die ze daar rijk zijn. Natuurlijk kun je ervan uitgaan dat de kans groot is dat je dit bedrag zal verliezen. Zo zit een casino immers in elkaar. Maar de verschillende automaten zullen ook verschillende kansen op winst hebben, waar je mogelijk je voordeel mee kan doen. Alleen weet je van tevoren niet hoe dat precies in elkaar zit. Wat wordt nu je strategie? Hoe kies je welke automaten je gaat bespelen? Zomaar lukraak? Nee, dat kan niet de beste aanpak zijn. Hoe kun je je beginbedrag nou zo goed mogelijk besteden om je uiteindelijke winst zo groot mogelijk te maken?

De keus tussen leren en presteren

Dit vraagstuk lijkt op het eerste gezicht misschien weinig met kunstmatige intelligentie te maken te hebben. Toch is dit een befaamd probleem binnen dit vakgebied. Ook veel systemen die gebruik maken van kunstmatige intelligentie moeten kunnen omgaan met dit soort afwegingen. Dat heeft te maken met de beslissingen die je tijdens het spelen neemt om je winst zo groot mogelijk te maken. Stel, je hebt inmiddels vijftien keer gespeeld: vijf keer op automaat A en tien keer op automaat B. Op automaat A heb je twee keer gewonnen, op automaat B slechts één keer. Met deze informatie kun je inschatten dat automaat A een winstkans heeft van ongeveer 40% en B van slechts 10%. In de volgende ronde heb je nu een keuze te maken. Kies je ervoor om met de huidige informatie de meest winstgevende automaat te bespelen, of kies je voor het bespelen van een nieuwe automaat? Misschien heeft deze derde automaat, automaat C, immers nog betere winstkansen dan automaat A.

De strategie waarin je teruggaat naar de meest kansrijke machine staat bekend als een ‘exploitatie’-strategie. Je ‘exploiteert’ de kennis die je op dat moment hebt om de verwachte winst van je volgende ronde zo hoog mogelijk te maken. De tweede optie is een ‘exploratie’-strategie. Bij deze strategie ga je op ontdekkingstocht om zo veel mogelijk informatie te winnen. Deze informatie helpt je weer in de volgende rondes, want hoe meer informatie je hebt, hoe beter je je volgende keuze kunt maken.

Voor veel systemen waarin kunstmatige intelligentie gebruikt wordt, is de afweging tussen exploratie- en exploitatiestrategieën een keuze die aan de lopende band moet worden gemaakt. Zo’n systeem moet zo goed mogelijke beslissingen maken, maar idealiter ook leren van de uitkomsten. Systemen die tegelijkertijd willen leren én presteren zullen dus slim om moeten gaan met de kansen die ze krijgen voor exploratie en exploitatie.

De ‘multi-armed-bandit’ van Netflix

Een bekend voorbeeld van een systeem waarvoor dat van groot belang is, is het systeem dat Netflix gebruikt om series en films bij gebruikers aan te bevelen. Volgens schattingen van Netflix verliezen gebruikers interesse in het platform als ze na anderhalve minuut zoeken nog geen leuke serie hebben gevonden. Het is daarom voor het bedrijf van groot belang om haar pagina’s zo in te richten dat je zo snel mogelijk een serie, documentaire of film vindt die bij je smaak past. Zo niet, dan loopt Netflix het risico dat je interesse verliest en er misschien uiteindelijk zelfs voor kiest je abonnement op te zeggen.

Het is dus aan de streaming-gigant gelegen om de homepagina zo in te richten dat jij als gebruiker op je wenken bediend wordt. Alleen is de ene gebruiker natuurlijk de andere niet. Smaken verschillen tussen de gebruikers en daarnaast ontwikkelt smaak zich. Wie zich twee jaar geleden nog helemaal verloor in sciencefictionseries kan inmiddels een voorliefde hebben ontdekt voor natuurdocumentaires. Zoals de gebruikers zich ontwikkelen, zo verandert ook het aanbod dat Netflix kan laten zien constant. Het platform vult de collectie continu aan met nieuwe series en films, maar ook verdwijnen er aan de lopende band weer oude titels. Om goed met al deze ontwikkelingen rekening te houden, is het belangrijk dat de systemen van Netflix exploratie en exploitatie blijven afwisselen. De titels zijn de ‘bandits’ die kunnen worden bespeeld door ze op de homepagina te plaatsen. Als er juist gespeeld wordt, zal de kijker binnen 90 seconden een fijne aflevering gevonden hebben om haar avond mee te vullen. Daarmee heeft Netflix weer een tevreden gebruiker.

Het kraken van het probleem

Een simpele, bekende aanpak voor dit probleem heet de ‘hebzuchtige methode’. In deze methode kies je ervoor om exploratie en exploitatie af te wisselen. Een deel van de tijd kies je ervoor om de beste bandit te bespelen en in de overige gevallen kies je een willekeurige. We gaan even terug naar het casino. Als je hier een hebzuchtige strategie toepast, kies je bijvoorbeeld in de helft van je spellen willekeurig een automaat. In de andere helft van je spellen kies je de automaat die in de vorige spellen de hoogste winstkans had. Zo leer je in de helft van je zetten van willekeurige automaten, en zet je in de andere helft van de zetten in op een zo hoog mogelijke winst met de kennis van dat moment.

De hebzuchtige methode is een makkelijke methode, maar lang niet altijd de beste. In het casino heb je bijvoorbeeld aan het eind van je bezoek de meeste automaten al een paar keer bespeeld. Op dat moment weet je al een stuk beter welke automaten je wel of niet wilt bespelen. Dan wil je afwijken van de hebzuchtige strategie om te voorkomen dat je alsnog deze automaten kiest in je willekeurige keuzes. Er zijn naast de hebzuchtige methode nog tal van ingewikkeldere strategieën ontwikkeld die speciaal bedoeld zijn om in specifieke situaties goed te werken. Zo heb je bijvoorbeeld de ‘optimistische strategie’. Hierin hecht je extra waarde aan onbekende automaten, zodat je zo snel mogelijk alle automaten bespeeld hebt. In ons voorbeeld zou automaat C bijvoorbeeld een grote kans toegekend krijgen om bespeeld te worden, want daar weten we nog niets van. Daarmee weet je dus zo snel mogelijk van iedere automaat wat je ongeveer kan verwachten.

Voor complexere situaties, zoals problemen waar bedrijven als Netflix zich voor gesteld zien staan, zijn nog geavanceerdere oplossingen ontwikkeld. Vaak werken die methodes met ingewikkelde kansmodellen om te bepalen welke ‘automaat’ op welk moment het beste bespeeld kan worden. Op basis van de uitkomsten van elke ‘spelronde’ worden de kansmodellen en de strategie vervolgens aangepast. Zo kun je op elk moment wiskundig bepalen wat de beste strategie is.

In de algoritmen die Netflix gebruikt om zijn pagina’s in te delen is er plaats voor een hele verzameling verschillende strategieën. Netflix deelt haar gebruikers in tientallen verschillende interessegroepen in en test constant nieuwe manieren om deze groepen zo goed mogelijk te bedienen. Hierin kiest het bedrijf per situatie

de strategie die het meest succesvol is op dat moment. Vrijwel niemand heeft dezelfde homepagina op Netflix, vanwege de constante stroom aan beslissingen die op de achtergrond gemaakt wordt door de kunstmatige intelligentie van het streamingbedrijf.

Een waardevolle afweging

Hoewel Netflix een voorloper is in het aanpakken van dit probleem zijn ze natuurlijk niet de enige die hiermee kampen. Vrijwel alle advertenties die je op het internet automatisch te zien krijgt, worden je voorgeschoteld door kunstmatig intelligente systemen. Elk van deze systemen is constant op zoek naar de optimale balans tussen exploratie en exploitatie.

Overigens zie je vergelijkbare uitdagingen ook in andere vakgebieden, bijvoorbeeld in de ontwikkeling van nieuwe geneesmiddelen. Een nieuw geneesmiddel voor een bekende ziekte werkt mogelijk beter dan de huidige behandelmethoden. Om dat zeker te weten, moet je een ‘exploratie’ doen door dit nieuwe middel te testen. Je kunt je voorstellen dat er in de medische wereld heel voorzichtig omgesprongen wordt met de keus tussen ‘exploratie’ en ‘exploitatie’, het gebruik van bekende geneesmiddelen. Het risico van een minder goed geneesmiddel toedienen is natuurlijk een stuk groter dan het risico dat je een verkeerde advertentie of suggestie voor een serie voorgeschoteld krijgt.

Het vraagstuk van de gokautomaten in casino’s is bekend geworden als het probleem van de multi-armed bandit. Het werd al in de jaren vijftig voor het eerst beschreven, maar nog steeds wordt er onderzoek gedaan naar de beste manier om dit soort problemen aan te pakken. Nog altijd verschijnen er nieuwe onderzoeksartikelen van wetenschappers die varianten van de multi-armed bandit oplossen of bestaande oplossingen verbeteren. Het geeft maar weer aan dat oude problemen nog altijd een bron kunnen zijn voor nieuwe ideeën. Trouwens, hoe goed je de automaten ook bespeelt in het casino, al gebruik je de allernieuwste topstrategie, het zal je niet snel meer opleveren dan de Netflixalgoritmen het bedrijf opleveren. Honderden mensen hebben al aan hun ‘recommender system’ gewerkt en dat heeft ze geen windeieren gelegd. Naar eigen schatting levert de kunstmatige intelligentie die jouw Netflixpagina’s indeelt het bedrijf ruim een miljard dollar per jaar op. Geen gek bedrag voor een clubje algoritmen!

Geïnteresseerd in het boek?
Bestel het hier

Leave a Reply

Your email address will not be published.