VPRO Digitaal

Ik heb in het kader van de masteropleiding Game & Media Technology (Informatica, Universiteit Utrecht) enkele maanden stage gelopen bij VPRO Digitaal. Ik heb onderzoek gedaan naar de geschiktheid van zogenaamde passieve coöperatieve filtering voor aanbevelingssystemen voor de VPRO. Ik heb 3VOOR12 gebruikt als case study, maar de techniek is generiek en is dus in principe breder in te zetten. Op vrijdag 17 oktober heb ik een presentatie gegeven voor VPRO Digitaal, maar voor degenen die daar niet bij konden zijn en voor degenen die nog eens willen nalezen wat mijn bevindingen ook alweer waren is er nu deze blogpost. De complete scriptie is op aanvraag beschikbaar.

Aanbevelingssystemen

Aanbevelingssystemen hebben de afgelopen jaren een grote vlucht genomen op internet. Bijna elke webshop probeert je te adviseren, want de winkelier heeft gemerkt dat hij meer verdient als hij zijn klanten goede aanbevelingen kan doen. Maar ook op sites waar niet direct iets verkocht wordt, worden aanbevelingssystemen ingezet: je kent vast de lijstje met gerelateerde filmpjes op YouTube.

Onderzoekers zijn misschien bekend met MovieLens en hun gratis datasets. En de Netflix Prize is een wedstrijd waarbij het team dat een aanbevelingssysteem ontwikkelt dat minimaal 10% beter presteert dan het huidige systeem (CineMatch) een miljoen dollar kan verdienen. Kortom: aanbevelingssystemen zijn big business!

Relaties

Om aanbevelingen te kunnen doen, moeten er relaties bekend zijn. Wil je boek aan iemand aanraden op basis van het boek dat hij net gelezen heeft en waar hij erg enthousiast over was, dan zul je gerelateerde boeken moeten kennen. Er zijn diverse manieren om relaties te indentificeren. Zo kun je bijvoorbeeld metadata (titel, auteur, artiest, genre, jaar, tags, etc.) gebruiken om objecten aan elkaar te relateren. Dit is echter lastig wanneer het om verschillende soorten objecten gaat, want verschillende soorten objecten hebben vaak ook verschillende soorten metadata. Vergelijkbaar met die bekende stuatie met appels en peren.

Een tweede manier om objecten te vergelijken is op basis van inhoud (content-based). Er wordt in het geval van muziek dan bijvoorbeeld een analyse van de golfvorm gedaan en bepaalde eigenschappen hiervan of patronen hierin kunnen dan gebruikt worden voor het relateren van muziek. Wederom is het probleem dat je niet objecten van verschillende typen op deze manier automatisch kunt relateren. Hoe zou je moeten zeggen dat een foto op een muziekstuk lijkt?

Een derde manier om relaties voor aanbevelingssystemen te identificeren is gebruik maken van waarderingen. Op sites als Amazon en YouTube kunnen gebruikers laten weten wat ze van het aangebodene vinden door middel van punten of sterren. Door de waarderingen van een heleboel gebruikers te combineren kunnen aanbevelingen gedaan worden. De methode die hiervoor gebruikt wordt wordt actieve coöperatieve filtering (active collaborative filtering) genoemd. ‘Actief’ omdat de gebruiker een speciale actie moet uitvoeren om zijn waardering kenbaar te maken aan het systeem.

Traditioneel werden gebruikers aan gebruikers gerelateerd (user-to-user collaborative filtering), maar voor Amazon zijn methoden ontwikkeld om producten aan elkaar te relateren (item-to-item collaborative filtering), omdat dit veel minder rekenkracht kostte en betere aanbevelingen opleverde.

Gedrag als basis voor aanbevelingen

Op 3VOOR12 bestaat de mogelijkheid om sterren uit te delen aan de aangeboden mediafragmenten: audio en video. Om dit te kunnen doen moet je echter wel inloggen en voor het kenbaar maken van een waardering blijkt een wat hoge drempel voor veel mensen. Het grootste deel van het aanbod van 3VOOR12 is zonder in te loggen beschikbaar en dat zal er zeker mee te maken hebben.

De centrale vraag in mijn onderzoek was of het gedrag van gebruikers bruikbaar is als basis voor aanbevelingssystemen. Het idee is om waarderingen indirect af te leiden uit het gedrag van gebruikers. De gebruiker hoeft dus geen speciale actie uit te voeren en hiermee betreden we het terrein van de passieve coöperatieve filtering. Het nadeel hiervan is dat de waarderingen indirect afgeleid worden en dus minder accuraat zullen zijn, maar het grote voordeel is dat elke gebruiker automatisch informatie levert die bruikbaar is voor aanbevelingen, alleen door te doen wat hij altijd al deed: gewoon de site gebruiken. Dat er veel meer informatie beschikbaar is, zou wel eens ruimschoots kunnen compenseren voor het gebrek aan accuratesse.

Ik ben aan de slag gegaan met 3VOOR12, maar wel met in het achterhoofd het idee om iets te ontwikkelen die niet specifiek toegespitst is op 3VOOR12, maar dusdanig generiek is dat het in principe ook voor andere VPRO-sites bruikbaar is. 3VOOR12 kent vier categoriën van media-aanbod: luisterpaal (tijdelijk beschikbare, complete albums), on demand (permanent archief van audio- en video-fragmenten), tv (live video-streams) en radio (live audio-streams). De live-streams heb ik voor mijn onderzoek buiten beschouwing gelaten.

Relatiemethoden

Ik heb in mijn scriptie een aantal relatiemethoden gedefinieerd, die allen gebaseerd zijn op het idee van paarfrequenties. Kort door de bocht: tellen hoe vaak paren van mediafragmenten samen opgevraagd worden. Een onderverdeling die ik gemaakt heb is tussen methoden die naar paren binnen sessies kijken (een sessie is een bezoek aan de site) en methoden die naar paren bekeken door gebruikers (over al hun sessies heen). De andere onderverdeling is tussen methoden die het absolute aantal keer dat een paar opgevraagd is tellen en methoden die hier intelligenter mee om proberen te gaan door een relatieve score te berekenen voor een paar. Zo’n relatieve score is een getal tussen 0 en 1 dat de sterkte van een relatie aangeeft. Het resultaat van een relatiemethode is een relatienetwerk. Het genereren van aanbevelingen aan de hand van een relatienetwerk is triviaal: zoek de gerelateerde objecten en maak een lijst, aflopend op relatiescore. Voor verder details over relatiemethoden en hun relatiescores verwijs ik naar mijn scriptie.

Problemen van Coöperatieve Filtering

Er zijn enkele problemen waarmee bij elk coöperatief filteringsysteem rekening gehouden moet worden:

• Sparsity. Objecten die niet van waarderingen voorzien zijn, kunnen niet gerelateerd worden aan andere objecten. Concreet: mediafragmenten die niet zijn opgevraagd, zullen ook nooit in aanbevelingen terechtkomen.
• Schaalbaarheid. Bij grote hoeveelheden gebruikers en/of objecten kan coöperatieve filtering erg veel resources gaan vragen.
• Overfitting. Methoden kunnen heel specifiek voor een bepaalde dataset getweakt worden, maar dit betekent vaak dat de methode niet erg goed werkt op andere datasets.
• Feedback. Wanneer aanbevelingen aangeboden worden als (alternatieve) methode voor navigatie op een site, bestaat de kans dat gebruikers veelvuldig kiezen voor het hoogst aangeraden object. Dit levert een feedback-lus op, want hierdoor wordt de relatiescore tussen het zojuist bekeken object en het hoogst aangeraden object verhoogd en wordt de positie als hoogst aangeraden object alleen maar steeds sterker. De kans bestaat dat een aanbevelingssysteem door dit effect een beetje dichtslibt.

Implementatie

Ik heb de relatiemethoden die ik heb gedefinieerd ook geïmplementeerd voor gebruik met 3VOOR12. Voor het verzamelen van de benodigde informatie is gekozen voor een combinatie van het loggen van extra informatie en een parser die de informatie voor relatiemethoden uit de logbestanden van de servers extraheert. Een efficiëntere manier zou misschien zijn om de benodigde informatie in de media servicelaag van 3VOOR12 op te vangen, maar voor dit onderzoek wilden we zo min mogelijk aanpassingen in 3VOOR12 hoeven doorvoeren.

Iets om rekening mee te houden was het feit dat niet alle mediafragmenten op 3VOOR12 ten alle tijde beschikbaar zijn. Albums op de luisterpaal verdwijnen vanwege contractafspraken meestal weer na een tijd en het kan in het algemeen natuurlijk gebeuren dat iets niet langer beschikbaar gemaakt wordt. Een gebruiker zal het zeker niet waarderen wanneer hij een link volgt om een aanbevolen fragment te bekijken en hij te zien krijgt dat het bewuste mediafragmente niet langer beschikbaar is. Dit is opgelost door middel van een witte lijst, die regelmatig in de 3VOOR12-database nagaat welke mediafragmenten meegenomen mogen worden in het relatieproces. Ik heb ook een eenvoudige web interface gemaakt voor het opvragen van aanbevelingen.

Gebruikersonderzoek

Om te bepalen welke relatiemethode het best presteert en om na te gaan of ze überhaupt acceptabele resultaten opleveren, heb ik een gebruikersonderzoek uitgevoerd. Ik heb een gevarieerde testset gegenereerd en ik heb vervolgens zes relatiemethoden op elk mediafragment in deze testset losgelaten. Een aanbeveling bestond in dit geval uit een lijstje van vijf mediafragmenten. Die zes relatiemethoden waren: mijn eigen vier implementaties, een extern ontwikkelde implementatie en een ‘nepmethode’ die aanbevelingen met willekeurig gekozen mediafragmenten oplevert. Die laatste is meegenomen omdat alle methoden als waardeloos bestempeld kunnen worden wanneer ze niet beter presteren dan een relatiemethode die op willekeur gebaseerd is.

Van de testset en de gegenereerde aanbevelingen is een enquête gemaakt en de respondenten werd gevraagd om elke aanbeveling met een cijfer van 1 tot 10 te waarderen, zonder dat zij wisten op welke manier een aanbeveling tot stand gekomen was. In totaal zijn er 1491 aanbevelingen van een waardering voorzien (niet iedereen kent alles en het was dus ook toegestaan om aanbevelingen over te slaan) en de methoden die paren binnen sessies beschouwen kwamen als beste uit de bus met een gemiddelde waardering van bijna een 7. De best presterende methode was ook nog eens de snelste: het genereren van een compleet relatienetwerk met meer dan een miljoen relaties kost minder dan 4 minuten. In theorie zou het relatienetwerk dus meerdere keren per uur bijgewerkt kunnen worden. De willekeurige methode viel gelukkig door de mand, met een gemiddelde waardering onder de 4.

Een kanttekening hierbij is dat de methoden die relatieve relatiescores gebruikten veel meer rekenkracht nodig hebben en daarom slechts een deel van de beschikbare gedragsgegevens konden verwerken. Er is samen met een databasespecialist gekeken naar een oplossing, maar die is niet gevonden. Als de performance van deze methoden op het niveau van de andere methoden gebracht zou kunnen worden, zouden deze uiteindelijk mogelijk toch beter kunnen scoren wanneer zij wel grote hoeveelheden gedragsdata binnen afzienbare tijd kunnen verwerken.

Opvallend

Er vielen enkele zaken op tijdens de analyse van de uitkomsten van het gebruikersonderzoek:

• De willekeurige methode scoorde ook voor geen enkel individueel mediafragment van de testset een voldoende. Gelukkig maar, m’n werk was dus niet voor niets.
• De aanbevelingen voor twee van de drie luisterpaalfragmenten in de testset scoorden gemiddeld óók geen voldoende. Mijn theorie is dat de relatiemethoden minder geschikt zijn voor de luisterpaal, omdat dit mediafragmenten zijn die slechts een beperkte tijd beschikbaar zijn en omdat de bezoekers van de luisterpaal meestal fragmenten zal opvragen die voornamelijk gerelateerd zijn door de het moment dat ze online gezet zijn en veel minder doordat ze muzikaal gezien een relatie hebben.
• Incomplete of zelfs lege lijstjes met aanbevelingen werden erg slecht gewaardeerd. Dit is misschien op te lossen door een hybride aanbevelingssysteem dat naast gedrag bijvoorbeeld ook metadata gebruikt of eventueel zelfs door dan willekeurige fragmenten te leveren.
• Verschillende gebruikers hebben verschillende verwachtingen van een aanbevelingssysteem. De één geeft aan bij een filmpje van artiest X graag meer filmpjes van artiest X aanbevolen te willen krijgen, maar de ander wil dat juist niet en waardeert ‘avontuurlijkere’ aanbevelingen juist veel beter.
• Kennis helpt relaties begrijpen en waarderen. Wanneer je weet dat de bassist van de band waar je naar zit te kijken ook in een andere band speelt die aanbevolen wordt, zal je die aanbeveling beter waarderen dan wanneer je dit niet weet.

Conclusie

Passieve coöperatieve filtering werkt goed voor online aanbevelingssystemen en is zeker een interessante optie wanneer er niet genoeg waarderingen zijn voor traditionele actieve coöperatieve filtering. In het geval van 3VOOR12 ging dit zeker op. Feedback is een effect om zeker rekening mee te houden, hoewel ik geen metingen heb verricht om te zien hoe sterk dit effect in praktijk zou zijn. De ontwikkelde methoden zijn generiek, want ze gebruiken geen ander enkele eigenschap dan het feit dat objecten in een bepaalde context opgevraagd zijn. De methoden zijn dus in principe ook bruikbaar in andere omgevingen dan 3VOOR12.

Toekomst

Wetenschap is nooit af en dus kan dit project ook weer een startpunt voor toekomstige projecten zijn. In mijn scriptie is een opzet voor een methode op basis van gerichte relatiegrafen en relatieve relatiescores te vinden. Mijn verwachting is dat deze methode betere resultaten oplevert dan de methoden die ik geïmplementeerd heb en op ongerichte relatiegrafen gebaseerd zijn. Het aantal berekeningen verdubbelt dan, maar het berekenen van een relatiescore wordt wel eenvoudiger. Dit zou zelfs kunnen betekenen dat het performanceprobleem van de eerder beschreven methode bij deze aanpak geen issue meer zou kunnen zijn.

Een voor de hand liggende uitbreiding is om bij objecten die een bepaalde tijdsduur hebben (zoals audio en video) te kijken naar het gedrag binnen het bekijken of beluisteren van zo’n fragment. Wanneer een filmpje helemaal bekeken wordt is het waarschijnlijker dat de gebruiker dit filmpje goed waardeerde dan wanneer hij het na enkele seconden alweer afzette. Wanneer de tijd die iemand op een webpagina doorbrengt meetbaar is, zou dit mogelijk ook gebruikt kunnen worden. Over dit soort methoden bestaan al enkele publicaties en het zou interessant zijn om te zien of dit bruikbaar en haalbaar is binnen de VPRO.

Zie mijn scriptie voor meer ideeën voor de toekomst.

Bedankt

Iedereen bij VPRO Digitaal, bedankt voor de leuke en interessante stage die ik bij jullie heb kunnen uitvoeren. Het was top!