Algoritmes en een database: een advies

1 Voorwoord

In dit essay zal ik twee vragen beantwoorden met betrekking tot ons onderzoek. Om onderzoek te kunnen doen naar nepnieuws rondom het COVID-19 virus, hebben we besloten teksten te classificeren als nepnieuws of waarheid met behulp van een algoritme, wat zal worden beïnvloed door de uitkomst van een kwalitatief onderzoek naar nepnieuws. Hiervoor zijn zowel een passend algoritme als een database nodig. In dit essay zal ik over beide onderwerpen een advies geven qua aanpak en dit onderbouwen met literatuur. Om de structuur enigszins te bewaren, zal ik de vragen een voor een behandelen.

2 Welk algoritme gebruiken we?

2.1 Introductie

De keuze voor een bepaald algoritme is geen triviale. Binnen het veld dat zich bezighoudt met het computationeel verwerken van tekst (of spraak), Natural Language Processing (NLP), zijn door de jaren heen vele algoritmes ontwikkeld, waarvan sommige al meer dan 50 jaar oud zijn. Tussen al deze algoritmen bestaan subtiele verschillen die het ene algoritme net iets meer geschikt maken dan het andere. Hoe wordt dan gekozen welk algoritme het beste is?

Het antwoord op deze vraag is van meerdere factoren afhankelijk. Het is onder andere belangrijk om te weten wat het algoritme precies moet kunnen, of er meer waarde wordt gehecht aan snelheid of efficiënt omgaan met geheugen, hoe groot de database is, waar programmeurs al ervaring mee hebben, etc. Van de mogelijkheden die er zijn,  ben ik er drie tegengekomen in de gelezen literatuur die goede kandidaten zijn. Voor elk algoritme zal ik kort beschrijven hoe het functioneert en de mogelijke voor- en nadelen toelichten die de keuze voor dat algoritme beïnvloeden.

2.2 Knowledge graph

De werking van een knowledge graph (kennisgraaf) wordt gedetailleerd beschreven in Zhou & Zafarani (2018) als een van de mogelijkheden om nepnieuws mee op te sporen. Wanneer een stuk tekst in een kennisgraaf wordt verwerkt, krijgt het een authenticiteitsscore. Deze geeft bijvoorbeeld weer hoeveel procent van de uitspraken in de tekst juist zijn volgens het algoritme. Een graaf is binnen de informatica een boomstructuur, met knopen en takken. In de knopen wordt ‘informatie’ opgeslagen en de takken tussen bepaalde knopen geven de relatie tussen die stukken informatie weer. Bijvoorbeeld, de knoop met het label ‘Mark Rutte’ en de knoop met het label ‘Minister-President’ zijn verbonden door de tak met het label ‘Baan’. Een knoop is door takken verbonden met minstens één andere knoop, maar er is geen bovengrens. Bij een kennisgraaf bouw je de kennis dus in het programma. Op het moment dat er kennis moet worden gecheckt op waarheid, komt dit binnen in de vorm (S,P,O). Hierbij staat het subject op de eerste plaats, de relatie op de tweede plaats en het object op de derde. In ons voorbeeld zou het dus zijn (Mark Rutte, baan, Minister-President). Het algoritme checkt vervolgens of er in de kennisgraaf twee knopen zijn die overeenkomen met het subject en object en kijkt of de tak met het label van de relatie tussen deze knopen loopt. Als al deze drie dingen gevonden kunnen worden, kan er dus worden gesproken over ware kennis. Deze kennis staat dan immers in de kennisgraaf. In het geval dat een van de drie elementen mist, kan het algoritme dus niet met zekerheid zeggen dat de kennis waar is. Wat kan er dan wel worden gezegd over deze kennis? De programmeur beslist hier wat voor strategie het algoritme hanteert om zo’n situatie te verwerken. Een optie is om simpelweg te zeggen dat alle kennis die niet in de kennisgraaf staat, onwaar is. Dit kan soms echter te kort door de bocht zijn, aangezien er kennis bestaat die misschien niet expliciet staat opgeslagen in de kennisgraaf. Er bestaan daarom ook andere, genuanceerdere opties, zoals het algoritme leren logische conclusies te kunnen trekken. Deze opties zijn echter vaak moeilijk te implementeren.

De kennisgraaf lijkt een aantrekkelijke kandidaat voor dit onderzoek. Ten eerste heeft het onderzoek een specifiek onderwerp, waardoor een beperkte hoeveelheid kennis in de graaf moet worden opgenomen. Om uitspraken over het coronavirus te checken is immers niet zoveel kennis nodig als bij het checken van uitspraken over politiek of klimaat, aangezien er daarbij bredere kennis komt kijken. Daarnaast is het een groot voordeel dat de werking van het algoritme inzichtelijk is. Bij machine learning zijn de conclusies die worden getrokken door algoritmes namelijk vaak niet te verklaren door de programmeurs.[1] Een kennisgraaf kan echter makkelijk worden bekeken en mogelijk aangepast.

Echter heeft het opstellen van een kennisgraaf in dit onderzoek ook enkele nadelen. De teksten die ons algoritme moet gaan classificeren, zijn namelijk afkomstig uit verschillende periodes van de coronacrisis. Gedurende deze crisis is de kennis over het virus en de aanpak ervan ook veel veranderd. Neem bijvoorbeeld het aftreden van minister Bruins: na zijn aftreden zouden alle stukken waar hij nog minister van Volksgezondheid wordt genoemd, worden gelabeld als nepnieuws. Op het moment van schrijven was dit echter wel de ‘ware’ kennis. Om dit probleem te vermijden, zou er een soort tijdsdimensie worden toegevoegd aan de graaf, waarbij voor ieder stuk kennis waarvan we weten dat het is veranderd, een soort ‘uiterste houdbaarheidsdatum’ wordt vermeld. Dit zou de kennisgraaf echter verschrikkelijk ingewikkeld maken en zoveel werk vragen van de programmeurs, dat men zich zou kunnen afvragen of het ontwikkelen van het algoritme wel tijd bespaart.

2.3 Naive-Bayes

Waar het bij kennisgrafen een uitdaging is om rekening te houden met onzekerheid, is dat bij de Naive-Bayes methode niet het geval. Naive-Bayes methode van tekstclassificatie is gebaseerd op het theorema van Bayes, een belangrijk theorema binnen de statistiek, dat een formule geeft om de kans van een bepaalde gebeurtenis te bepalen. Je kan hiermee specifiek de kans berekenen dat een bepaalde gebeurtenis A plaatsvindt, gegeven dat een zekere stelling B waar is. Zo wordt deze methode bijvoorbeeld gebruikt om de kans dat iemand kanker heeft (A) te bepalen aan de hand van een bepaald symptoom (B).  Binnen NLP is dit handig, aangezien je kan bepalen wat de kans is dat een tekst nepnieuws is (A) gegeven de tekst (B). De Naive-Bayes methode heeft wel een bekend nadeel, namelijk de naïve aanname dat de gebeurtenis A slechts afhangt van B en niets anders. Zo hangt het ontwikkelen van kanker niet slechts af van het vertonen van één symptoom, maar spelen er veel andere variabelen mee. In de praktijk blijkt echter dat deze aanname niet voor grote problemen in nauwkeurigheid zorgt. (Zhou & Zafarani, 2018)

Om Naive-Bayes te implementeren voor tekst-classificatie, moet gebruik worden gemaakt van zogenaamde features. Dit zijn eigenschappen van een tekst, zoals aantal woorden, complexiteit, titel, etc. De programmeurs kiezen enkele van deze features en het algoritme bepaalt de waarde van de features voor elke tekst. Een tekst heeft bijvoorbeeld een hoge complexiteit maar weinig woorden. Vervolgens kijkt het algoritme of er een patroon te vinden is tussen een bepaalde feature en het waarheidsgehalte van een tekst. Zo zou het bijvoorbeeld kunnen dat de kans groot is dat een tekst met nepnieuws relatief kort is en een lage complexiteit heeft. Dit proces heet het trainen van een algoritme. Nadat de training is afgerond, classificeert het algoritme nieuwe teksten op basis van deze patronen. Op dat moment zou een korte tekst door het algoritme eerder worden gelabeld als nepnieuws dan een langere tekst.

Hoewel het veel werk lijkt, is veel van de implementatie van Naive-Bayes al eerder gedaan en makkelijk beschikbaar in Python[2]. Ook is het in een recente studie de beste gebleken van 7 algoritmes die werden getest op hun vermogen om nepnieuws te classificeren. (Zhou & Zafarani, 2018) Tenslotte hebben enkele studenten die meewerken aan dit onderzoek al eerder intensief gewerkt met Naive-Bayes, wat het proces aanzienlijk sneller kan maken.

Echter heeft Naive-Bayes ook een aantal nadelen. Naast het feit dat de nauwkeurigheid zeker beter kan, is dit algoritme een grote ‘black box’. Binnen de informatica duidt dit op een algoritme wat slechts beschreven kan worden in termen van de input en output van het programma, aangezien de specifieke werking van het programma niet te achterhalen is. (Wikipedia, 2020) De patronen die Naive-Bayes ontdekt zijn namelijk niet inzichtelijk voor de programmeurs en de classificatie die wordt gemaakt is dus ook niet uit te leggen. Deze is erg afhankelijk van de data en de features waarop wordt getraind. De training-data moet divers zijn, zodat er niet bij toeval een verkeerd patroon erg sterk wordt vastgelegd in het algoritme. Tegelijkertijd moet de data ook representatief zijn voor de teksten, zodat de juiste patronen wel worden ontdekt. Van de features waarmee wordt getraind, die worden bepaald door het close-reading deel van dit onderzoek, is dus ook niet meteen duidelijk waarom een bepaalde feature de nauwkeurigheid van het algoritme vergroot of juist verlaagt. Kortom, als het werkt is niet uit te leggen waarom.

2.4 Linear support Vector Machine

Voor mij was de Linear Support Vector Machine (LSVM) een nieuw algoritme. Uit de literatuur blijkt echter dat dit algoritme een enorm hoge nauwkeurigheid kan behalen, ook als implementatie om nepnieuws te classificeren, namelijk 92%. (Ahmed, Traore, & Saad, 2017) Ook dit algoritme werkt, net als Naive-Bayes, op basis van features. Iedere tekst krijgt een set features, die als het ware in een grafiek worden gezet. Als voorbeeld neem ik graag een set van twee features, zodat de grafiek makkelijk te illustreren is.

Figuur 1 (Wikipedia, Support Vector Machine, 2020)  geeft een voorbeeld van zo’n grafiek. Stel nu dat de witte datapunten alle teksten zijn met ware informatie en de zwarte datapunten de teksten met nepnieuws. LSVM probeert een lijn te trekken in deze grafiek, zodat van een nieuw datapunt kan worden bepaald tot welke categorie het behoort door te kijken aan welke kant van de lijn het valt. Deze lijn geeft dus de ‘grens’ tussen waar-  en nepnieuws weer. In de grafiek zijn drie voorbeelden van zo’n lijn te zien, maar er zijn grote verschillen. Naast het feit dat lijn H1 de twee groepen helemaal niet scheidt, is te zien dat er vele verschillende lijnen te trekken zijn die dit wel doen. Lijn H2 en H3 zijn compleet verschillende lijnen, maar scheiden allebei de twee groepen. Hoe kiest LSVM welke lijn de beste is?

Bij deze beslissing komt erg veel wiskunde kijken, maar het komt erop neer dat LSVM de lijn kiest met de grootste ‘buffer’. Dit houdt in dat er wordt geprobeerd een zo groot mogelijke afstand tussen de lijn en de datapunten te houden. In figuur 1 is dit geïllustreerd met de lijnen die naar H3 lopen. Deze grote buffer zorgt dat een nieuw datapunt met meer zekerheid in een van de categorieën kan worden geplaatst, aangezien het verschil tussen de categorieën groter is dan bij H2.

Door de hoge nauwkeurigheid die LSVM eerder heeft gehaald in een context van nepnieuws, lijkt het zeker een aantrekkelijke toepassing. Daarnaast maakt het sneller nieuwe voorspellingen en kost het minder computergeheugen dan Naive-Bayes. Tenslotte heeft een van de programmeurs van dit onderzoek al eerder gewerkt met SVM’s, waardoor er een mooie kans is voor de anderen om iets nieuws te leren.

Helaas komt er wel een kleine complicatie kijken bij onze implementatie van LSVM: het is enorm ingewikkeld. Het aantal features dat wij gaan gebruiken is namelijk niet twee, maar zal, naar mijn verwachting, minstens tien zijn. Dit betekent dat er dus in minstens tien dimensies gerekend moet worden door het algoritme. Deze complicatie maakt dan ook dat LSVM een langere tijd nodig heeft om te trainen dan Naive-Bayes. Hierbij moet wel worden gezegd dat dit effect groter is naarmate de database groter is. Ik verwacht echter dat onze database niet van zulke grootte gaat zijn dat dit een enorm verschil maakt, maar dat is niet van tevoren met zekerheid te zeggen. Ook is LSVM uiteindelijk, net als Naive-Bayes, een black box.

3 Conclusie

Na deze drie algoritmes kort te hebben toegelicht, is hopelijk duidelijk geworden dat de keuze voor een algoritme niet simpel gemaakt is. Aan de ene kant is er de kennisgraaf, waarbij het proces inzichtelijk blijft voor de programmeurs en welke echt gebaseerd is op de inhoud van een tekst, maar ook grote moeite kost om te implementeren. Aan de andere kant zijn er Naive-Bayes en LSVM, die beide een black box zijn en de tekst niet beoordelen op basis van de inhoud maar op basis van de schrijfstijl, maar waarbij een groot deel van de implementatie al gedaan is en met enkele regels code te gebruiken.

Aangezien kennis rondom de coronacrisis vaak moet worden bijgesteld, zou ik aanraden de kennisgraaf achter ons te laten. Het succesvol vangen van de kennis over het virus en de aanpak ervan in een graaf lijkt een opgave van een enorm formaat en misschien niet eens praktisch te realiseren.

Dan rest ons nog de keuze tussen Naive-Bayes en LSVM, met elk hun eigen voor- en nadelen. Naive-Bayes is zeer bekend bij de programmeurs van dit onderzoek, is erg simpel te implementeren en kost relatief weinig tijd om te trainen, maar de nauwkeurigheid is vaak niet extreem hoog. Daarentegen is LSVM wel een ingewikkeld algoritme, maar kan het een extreem hoge nauwkeurigheid halen, maakt het snellere voorspellingen en biedt het de kans om met een nieuw algoritme te leren werken.

In plaats van een harde keuze maken tussen deze twee algoritmes, zou ik aanraden om beide te implementeren. Hierbij zou Naive-Bayes als eerste geïmplementeerd worden, zodat er in ieder geval een werkend algoritme is. Wanneer dit is bereikt, kan de focus worden verlegd naar LSVM. Als beide algoritmes uiteindelijk werken, kan worden bekeken welk algoritme de hoogste nauwkeurigheid kan krijgen. Dit algoritme zal dan uiteindelijk het ‘eindproduct’ zijn.

Hoe maken we een database?

1 Introductie

Bij dit onderzoek geldt: zonder database, geen onderzoek. Zowel de close- als distant-reading delen van het onderzoek baseren zich op deze database, wat het een belangrijk deel van het onderzoek maakt. De data waar we naar op zoek zijn, zijn teksten over het coronavirus. Hier is nog geen bestaande database van, dus zullen we deze zelf moeten maken. Hierbij komen meteen een aantal vragen kijken, die ik hieronder zal beantwoorden. Daarna zal ik, op basis van de vragen, een plan van aanpak voorstellen.

2 Wat zijn de randvoorwaarden voor de data?

Gelukkig zijn er specifiek voor databases met fake news al negen randvoorwaarden gesteld (Pérez-Rosas, Kleinberg, Lefevre, & Mihalcea, 2017), die wij ook zullen volgen. Volgens deze randvoorwaarden moet de dataset (1) zowel nepnieuws als echt nieuws bevatten, (2) alleen tekst-objecten hebben, (3) te verifiëren zijn in de echte wereld, (4) ongeveer van gelijke lengte en (5) schrijfstijl zijn, (6) nieuws bevatten van binnen een bepaalde tijdsspanne, (7) op dezelfde manier en voor hetzelfde doel zijn geschreven (bv: humor, journaal), (8) openbaar beschikbaar zijn en (9) taal en culturele verschillen in acht nemen.

Aangezien wij alleen Nederlandse data zullen opnemen in onze database, zullen wij ons vooral bezighouden met criteria 1 t/m 8. Verder zullen we proberen (ongeveer) evenveel nepnieuws als echt nieuws in de dataset op te nemen, waarbij we de lijn van vorige onderzoeken voortzetten.

3 Hoeveel data moet het zijn?

Het makkelijke maar onpraktische antwoord op deze vraag is: zo veel mogelijk. Hoe meer data het algoritme heeft om te trainen, hoe kleiner de kans dat het fouten maakt. Een schatting van hoeveel data minimaal nodig is, is voor de onderzoekers wel erg fijn.

Hier lijkt echter geen consensus over te bestaan. De grootte van de datasets in de literatuur verschilt ook sterk. Een onderzoek gebruikte 2000 datapunten (Ahmed, Traore, & Saad, 2017), een ander 50.000 (Resende, et al., 2019). Qua haalbaarheid lijkt het logisch dat wij meer richting de 2000 datapunten gaan dan 50.000, hoewel meer natuurlijk altijd beter is.

4 Hoe verzamelen we de data?

Er zijn veel verschillende manieren om data te verzamelen, maar het belangrijkste verschil lijkt te zijn of het verzamelen handmatig of automatisch plaatsvindt. Aangezien we een zo groot mogelijke database willen creëren, is het nuttig om de tijd die het verzamelen kost te minimaliseren. Het spreekt vanzelf dat er dan zoveel mogelijk automatisch verzameld moet worden.

Gelukkig zijn er veel manieren om automatisch data te verzamelen. In een onderzoek werden bijvoorbeeld meer dan 50.000 WhatsApp berichten automatisch verzameld uit openbare WhatsApp groepen (Resende, et al., 2019). Iets dergelijks zouden wij ook zeker kunnen proberen, mits er in zulke groepen (nep)nieuws wordt gedeeld over het coronavirus. Vergelijkbare strategieën kunnen gebruikt worden om (nep)nieuws te verzamelen van bijvoorbeeld de NOS, het RIVM, Facebook of Twitter.

Aangezien Twitter een platform is waar veel data van vrijwel dezelfde lengte openbaar wordt gedeeld, lijkt het een logisch platform om te beginnen.[3] Op deze manier voldoen we automatisch al aan een aantal van de acht randvoorwaarden.

5 Hoe verwerken we data?

Wanneer we de data hebben verworven, kan het natuurlijk niet meteen door ons algoritme worden verwerkt. Eerst moeten we een aantal stappen zetten om de data te ‘pre-processen’. Ten eerste veranderen we iedere tekst in een set unigrammen, aangezien deze een hogere nauwkeurigheid geven ten opzichte van bigrammen of trigrammen (Zhou & Zafarani, 2018). Verder zullen we van ieder woord de Term Frequency-Inverse Document Frequency (TF-IDF) waarde bepalen. Deze waarde geeft van ieder woord weer hoe significant het is, door te meten hoe vaak het voorkomt in een tekst. Een probleem hiermee is dat veelvoorkomende woorden (zoals ‘de’) een enorm hoge waarde krijgen, terwijl ze niet veel informatie geven en in elke tekst veel voorkomen. Hier komt het IDF deel kijken: de frequentie van een woord in een tekst word afgezet tegen de frequentie van het woord in de hele database. Zo krijg je een meer accuraat idee van welke woorden een verschil maken binnen een tekst.

Uit (Pérez-Rosas, Kleinberg, Lefevre, & Mihalcea, 2017) blijkt dat interpunctie een rol kan spelen in het classificeren van nepnieuws. Hoewel ons close-reading onderzoek moet uitwijzen of wij dit ook gaan meenemen, lijkt het handig om interpunctie niet meteen te verwijderen, zoals vaak standaard is bij NLP databases.

Het is aannemelijk dat er hierna nog enkele stappen moeten worden gezet in het pre-processen van de data. Echter, wat er precies moet gebeuren hangt af van de features die we willen onderzoeken, wat afhankelijk is van de uitkomst van ons close-reading onderzoek. Verdere plannen voor pre-processing zullen hier dus op moeten wachten.

6 Conclusie

Het opstellen van een dataset zal een groot deel van dit onderzoek in beslag nemen. Er moet immers data worden verzameld en (deels handmatig) verwerkt. Tegelijkertijd moet er genoeg tijd overblijven om de algoritmes juist te trainen. Om een zo hoog mogelijke graad van automatiseren en dus tijdwinst te krijgen, zou ik aanraden onze database te baseren op tweets. Dit betekent dat al onze data al ongeveer van dezelfde lengte is en aangezien het ook vrij kort is, zal het makkelijker te verwerken zijn. Gelukkig is er op Twitter zowel veel nepnieuws als echt nieuws te vinden, maar moet iedere tweet wel worden gecheckt op waarheid door een van de onderzoekers.

7 Bibliography

Ahmed, H., Traore, I., & Saad, S. (2017). Detection of Online Fake News Using N-Gram Analysis and Machine Learning Techniques. Springer International Publishing, 127-138.

Pérez-Rosas, V., Kleinberg, B., Lefevre, A., & Mihalcea, R. (2017). Automatic Detection of Fake News. Proceedings of the 27th International Conference on Computational Linguistics (p. 10). New Mexico: Association for Computational Linguistics.

Resende, G., Melo, P., Reis, J. C., Vasconcelos, M., Almeida, J. M., & Benevenuto, F. (2019). Analyzing Textual (Mis)Information Shared in WhatsApp Groups. 11th ACM Conference on Web Science (p. 10). Boston: Association for Computing Machinery.

Wikipedia. (2020, April 16). Black Box. Retrieved from Wikipedia: https://en.wikipedia.org/wiki/Black_box#Computing_and_mathematics

Wikipedia. (2020, April 16). Support Vector Machine. Retrieved from Wikipedia: https://en.wikipedia.org/wiki/Support-vector_machine

Zhou, X., & Zafarani, R. (2018). Fake News: A Survey of Research, Detection Methods, and Opportunities. ACM Comput. Surv 1, 40.

[1] Waarom dit is, zal ik verder toelichten bij de bespreking van de andere algoritmes.

[2] Python heeft zich ontwikkeld tot de standaard taal voor NLP, waardoor veel algoritmes en toepassingen voor NLP erg makkelijk beschikbaar zijn in Python. Vandaar dat we ook in deze taal zullen programmeren.

[3] Wel zal nog moeten worden nagegaan of Twitter regels heeft betreffende gebruik van data.