3.5 Algoritmes die ons (digitale) leven dirigeren

Ongetwijfeld heb je het woord al eens gehoord: een algoritme. Het heeft niks met ritmische muziek te maken alhoewel Shazam wel algoritmes gebruikt voor patroonherkenning in muziek. Google gebrukt het PageRank-zoekalgoritme en wanneer je naar een MP3-muziekbestand luistert dan is dit eerst met een compressie-algoritme tot een relatief klein bestand herleid vooraleer het op je mediaspeler is beland. Algoritmes spelen een cruciale rol in de verwerking van big data. Algoritmes zijn in de digitale wereld alomtegenwoordig, maar wat zijn het eigenlijk? Een nette verklaring van het begrip vinden we op Wikipedia:

“(een algoritme) is een eindige reeks instructies die vanuit een gegeven begintoestand naar een beoogd doel leiden. Algoritmen staan in beginsel los van computerprogramma's, al worden voor de uitvoering van algoritmen vaak computers gebruikt. Het doel van een algoritme kan van alles zijn met een duidelijk resultaat. De instructies kunnen in het algemeen omgaan met eventualiteiten die bij het uitvoeren kunnen optreden. Algoritmen hebben in het algemeen stappen die zich herhalen (iteratie) of die beslissingen (logica of vergelijkingen) vereisen om de taak te voltooien.”¹

3.5.1 Sorteeralgoritmes

In wezen gaat het om een stappenplan waarvan je weet dat je tot een bepaald resultaat zal leiden. Het gaat dus verder dan lukraak proberen een bepaald resultaat te bereiken. Je weet heel goed welke stappen je na elkaar moet zetten om tot een resultaat te komen. Op school leer je bijvoorbeeld woordjes alfabetisch rangschikken. Dat doe je in eerste instantie door naar de eerste letter te kijken. Bevatten veel woorden dezelfde beginletters, dan rangschik je die woorden door naar de tweede letter en vervolgens naar de volgende letters te kijken. Rangschikking vereist dus een algoritme, een strikt stappenplan om tot het beoogde eindresultaat (een alfabetische volgorde) te bereiken. Algoritmes blijven dus niet beperkt tot computerwetenschappen, maar je vindt ze al een “eeuwigheid” terug in de wiskunde. In het tweede millennium voor Chr. gebruikten de Babyloniërs algoritmes voor het berekenen van machten en vierkantswortels.

Het alfabetisch rangschikken van woorden en het ordenen volgens grootte van getallen lijkt voor ons erg makkelijk. Maar het vraagt wel een stappenplan in ons hoofd, ook al doe je het na een tijdje zonder na te denken. Hoe beter het algoritme, hoe sneller de procedure. Dit soort algoritmes wordt reeds van in de beginjaren van de computer gebruikt in de computerwetenschappen. John von Neumann bedacht het “sort merge”-algoritme in de 1945. Het sorteert gegevens door het splitsen, ordenen en weer samenvoegen (merge) van data. Tony Hoare bedacht in 1959 het Quicksort-algoritme, dat zoals de naam al doet vermoeden, sneller werkt dan “sort merge”.² In 1964 bedacht J.W.J. Williams het “heapsort”-sorteeralgoritme.³

Zonder dit soort “sorteeralgoritmes” zouden heel wat moderne computertechnieken zoals data mining, AI, linkanalyse... ondenkbaar zijn.

3.5.2 Conversie en compressie

De het Fourier-transformatie-algoritme en de Fast Fourier-transformatie of het FFT-algoritme liggen aan de basis van heel wat compressie-algoritmen zoals JPG en MP3. Een Fourier-tansformatie zet een geluidssignaal of lichtintensiteit om in een golffunctie. Het internet, WiFi, een smartphone, computer, router, communicatiesatellieten enz., zo wat alle toestellen waarin een soort computer aanwezig is, gebruikt het deze algoritmen. Het meet analoge signalen doorheen de tijd en tekent die uit als een golf op basis van de gemeten frequenties. Door signalen op te zetten in (golf)functies, kan de intensiteit van de golf eveneens getransformeerd (vervormd) worden. Het FFT-algoritme wordt bijvoorbeed gebruikt bij afbeeldingsfilters waarbij men de intensiteit van kleuren of belichting 'transformeert'. Bij compressie worden lage intensiteitsverschillen weggegooid waardoor de bestandsgrootte erg verkleind.

"Fourier-transformaties worden gebruikt bij het omzetten van analoge signalen in digitale data en worden onder meer toegepast bij signaalverwerking, maar spelen ook een rol bij de compressie van beelden. Een complex signaal wordt met fft gereduceerd tot een aantal eenvoudig digitaal te representeren componenten. Daarvoor wordt een analoog sample opgedeeld in kleine stukjes, waarna de stukjes worden geanalyseerd en geconverteerd naar een digitaal signaal."⁴

Compressie-algoritmes spelen een bijzonder belangrijke rol. Ze zorgen ervoor dat data kleiner worden, maar vaak gaat dit gepaard met kwaliteitsverlies. De algoritmes maken een afweging tussen kwaliteit en kwantiteit. In 3.2.5 (Compressie) leerde je al meer over de belangrijkste compressie-algoritmes voor afbeelding. In deel 6.2.7 (Codecs en containers) lees je meer over compressie van film.

3.5.3 Foutcorrectie

Het klinkt in de eerste plaats al indrukwekkend, het “Proportional Integral Derivative Algorithm” maar wat het doet is al even tot de verbeelding sprekend. Een PID-controller berekent constant foutwaardes als het verschil tussen de gemeten signaalwaarde en het gewenste resultaat en werkt vervolgens de fout weg. PID-controllers worden in de industrie toegepast, maar ook in meer populaire toepassingen. Zangers zingen in een opnamestudio niet altijd netjes op de toon, doorheen een zangpartij zitten ze vaak wel eens net boven of net onder de juiste toon. Dat wil nog niet zeggen dat ze ronduit vals zingen, maar ze zitten zelden loepzuiver op de toon. Autotuning zorgt ervoor dat al die foutjes verdwijnen in de uiteindelijke gemixte opname. Het lied “Believe” van de zangeres Cher zou de eerste popsong zijn die van autotuning gebruik heeft gemaakt. Je merkt meteen het verschil als je naar opnames uit de jaren 1960 of 1970 luistert en die vergelijkt met opnames uit de digitale periode vanaf 1984. Beluister bijvoorbeeld eens het album “Communique” van Dire Straits en het loepzuivere digitale geluid van “Brothers in Arms” van diezelfde groep. Niet dat we Dire Straits en Mark Knopfler “verdenken” van autotuning, maar de digitaliseringsalgoritmes hebben een blijvende “stempel” gedrukt op alle opnames vanaf de komst van de CD.

3.5.4 Dijkstra

Het Dijkstra-algoritme is vooral bekend als het kortste pad-algoritme. Het beschrijft de kortste afstand tussen twee punten.

“Het algoritme van Dijkstra wordt gebruikt door verschillende internetprotocollen, voor het vinden van de kortste route tussen computers of routers. Het algoritme van Dijkstra geeft gegarandeerd het kortste pad, als er überhaupt een pad tussen A en B bestaat, maar kan hier wel lang over doen. De snelheid van het algoritme is afhankelijk van de manier waarop de punten en lijnen opgeslagen zijn in het geheugen van de computer.”⁵

3.5.5 Linkanalyse

Welke links bovenaan verschijnen in Googles zoekresultaten wordt bepaald door het PageRank-algoritme. Facebook toont bij iedere gebruiker een andere newsfeed gebaseerd op de “vrienden” met wie je het meest contact hebt (op Facebook dan toch), berichten die de meeste “likes” hebben gekregen enz. Wat je te zien krijgt, hangt dus af van een heleboel factoren en wordt bepaald door een linkanalyse-algoritme. Uiteraard verschillen de algoritmen maar de basis voor linkanalyse werd gelegd in 1976 door Gabriel Pinski en Francis Narin.

“Who uses this algorithm? Google in its Page Rank, Facebook when it shows you your news feed (this is the reason why Facebook news feed is not an algorithm but the result of one), Google+ and Facebook friend suggestion, LinkedIn suggestions for jobs and contacts, Netflix and Hulu for movies, YouTube for videos, etc. Each one has a different objective and different parameters, but the math behind each remains the same.

Finally, I’d like to say that even thought it seems like Google was the first company to work with this type of algorithms, in 1996 (two years before Google) a little search engine called “RankDex” , founded by Robin Li, was already using this idea for page ranking. Finally Massimo Marchiori, the founder of “HyperSearch”, used an algorithm of page rank based on the relations between single pages. (The two founders are mentioned in the patents of Google).”⁶

3.5.6 Suggesties?

Wanneer je op twee verschillende computers van twee verschillende “mensen” dezelfde zoekterm invoert in Google krijg je vaak andere zoekresultaten. Googles PageRank baseert de zoekresultaten immers ook op uw zoekgeschiedenis en toont op basis daarvan ook andere advertenties via het Google Adwords-algoritme. Wanneer je een zoekterm begint in te voeren toont Google Suggest reeds een reeks mogelijkheden waaruit je een optie kan selecteren. Ook iTunes, Amazon en Netflix tonen op basis van uw zoekgeschiedenis en aankopen andere producten die u wellicht interesseren. Eli Pariser noemt dit “informatie determinisme”. De gebruiker zit in een soort van “filter bubbel” waar hij zelf voor een deel de controle over verliest. Je kan dus niet zelf meer kiezen wat je te zien krijgt, algoritmes bepalen dit voor u. Vraag is of je, puur uit marketingoogpunt, op die manier geen potentiële kopers van bepaalde producten mist.

Online dating is eveneens een voorbeeld van een veelgebruikte dienst die op basis van suggestie-algoritmes functioneert. Het matching-algoritme van OKCupid (een online datingdienst) werd afgeleverd door de Harvardwiskundige Christian Rudder. Het maakt een “ruwe” match op basis van gemeenschappelijke interesses. Vraag is natuurlijk of iemand met gelijkaardige interesses sowieso de beste partner is. Daarom berekent het algoritme eveneens hoe belangrijk elke vraag is voor de andere partij.

3.5.7 Veiligheid

Steeds meer computergebruikers plakken hun webcam af met een stukje plakband, iedereen weet dat je privacy wel eens kan geschonden worden door al je internetavonturen. Toch rekenen we wel op veiligheid als we online bankieren of wanneer we een reis boeken via Booking.com en onze creditcardgegevens invullen in een App Store of in PayPal. Zonder dit gevoel van zekerheid en veiligheid zou je wel gek moeten zijn om je bankkaartgegevens ergens achter te laten. Het RSA-algoritme (ooit geschreven door de firma RSA) en het Secure hash-algoritme zorgen ervoor dat onze data veilig en versleuteld worden uitgewisseld tussen onze thuiscomputer en de servers van banken en online winkels. Een ander belangrijk algoritme in de wereld van de cryptografie is het Integer factorization-algoritme.

3.5.8 Controle en voorspelling

In 1948 schreef George Orwell het boek “1984” waarin hij scherpe kritiek leverde aan het adres van de USSR. Hij schetste

“een onmenselijke dictatoriale eenpartijstaat die in alle opzichten volledig beheerst wordt door de Partij. De alom aanwezige leider van de Partij en het land wordt Big Brother genoemd. Iedere bewoner van het land wordt continu in de gaten gehouden via camera's die zelfs in de huizen zijn geïnstalleerd. Dit gebeurt onder de slogan ‘Big Brother is watching you’ (‘Grote Broer houdt je in de gaten’).”⁷Ondertussen leven wij in het westen niet in dictatoriale eenpartijstaten, maar Big Brother lijkt heel reëel. Ieder van ons wordt in de gaten gehouden, zij het niet door mensen, maar door algoritmes. Vanuit de USA houdt het National Security Agency (NSA) en zijn internationale partners (Five Eyes: US, Australië, Canada, Nieuw-Zeeland, Groot-Brittannië) wereldwijd miljoenen mensen in de gaten. Ze monitoren telefoongesprekken, SMS-berichten, e-mailberichten, webcambeelden, GPS-locaties enz. De hoeveelheid verzamelde informatie is veel te groot om te laten analyseren en interpreteren door mensen. De analyse gebeurt automatisch met behulp van krachtige algoritmes.

Sommige algoritmes zoals IBM's CRUSH, gaan nog een stukje verder. CRUSH of “ Criminal Reduction Utilizing Statistical History” zorgt voor “predictive analysis” en is in hoofdzaak bedoeld om misdaden te voorkomen. De politiediensten van Memphis konden de misdaadcijfers met 30% laten teruglopen dankzij CRUSH. Het aantal gewelddadige misdrijven liep sinds 2006 terug met 15%. Op basis van statistische gegevens, data-aggregatie en algoritmes, toont de software criminele hot spots op een kaart. Politie-eenheden kunnen op de manier pro-actief ingeschakeld worden en bij wijze van spreken aankomen voor een misdaad plaatsvindt. In de toekomst zullen criminelen heel snel opgespoord kunnen worden dankzij internetactiviteit, GPS en biosignaturen, verdacht gedrag...

“In the future, these systems will largely take over the work of analysts. Criminals will be tracked by sophisticated algorithms that monitor internet activity, GPS, personal digital assistants, biosignatures, and all communications in real time. Unmanned aerial vehicles will increasingly be used to track potential offenders to predict intent through their body movements and other visual clues.”⁸

De film Minority Report van Steven Spielberg uit 2002 toont al een glimp van waartoe dit in de toekomst kan leiden.

Algoritmes voor predictieve analyse zijn reeds lang in gebruik in de beurswereld. De analyse van razendsnel voorbijvliegende transacties gebeurt met behulp van slimme algoritmes. Soms kloppen de predicties niet, zoals bij de “Flash Crash” van 2010.

3.5.9 Dobbelen

Als je dobbelt met een dobbelsteen of de lotto speelt, speel je letterlijk met “toeval”. Een computer kan eveneens een lukraak getal genereren. In de meeste programmeertalen kan je de functie om een random getal te genereren eenvoudig oproepen. Random-getalgenerators zijn belangrijk in beveiliging en cryptografie, games, AI enz.

3.6 Mechanische, elektronische en digitale computers

Rekenen kost veel te veel tijd, tijd die je aan aangenamer bezigheden kan besteden. Dat merkte men ook bij de Amerikaanse volkstelling van 1880: 500 ambtenaren hadden 7 jaar lang de handen vol om alle gegevens te verwerken. Herman Hollerith (1860–1929) was ambtenaar bij het landelijk bureau voor statistiek. Hij zag in dat je met de automatische verwerking van ponskaarten veel sneller zou kunnen werken. In 1890 introduceerde hij zijn Hollerithmachine. Gegevens zoals geslacht, leeftijd en nationaliteit van elke inwoner werden op ponskaarten opgeslagen. De machine telde en sorteerde! Met behulp van 42 machines slaagden hetzelfde aantal ambtenaren erin om de klus op een maand te klaren. In 1939 startte IBM met de ontwikkeling van een rekenmachine ,die vijf jaar later onder de naam Automatic Sequence Calculator (Mark I) het levenslicht zou zien. Het toestel werd samen met Harvard University ontwikkeld en was maar eventjes 15 meter lang en 2,5 meter hoog. De Duitser Konrad Zuse (1910– 1995) kende het werk van Babbage niet toen hij van start ging met zijn eigen rekenmachine, die volgens het binaire talstelsel van Leibniz werkte. Zijn eerste model (Z1) gebruikte nog mechanische schakelingen, maar beschikte wel al over een geheugen. Stilaan begon hij te experimenteren met elektromechanische verbindingen, wat resulteerde in de Z3, de eerste computer waarbij zowel het geheugen als de processor elektromagnetisch functioneerde. Het binaire talstelsel volstond niet voor de verwerking van gegevens. Een elektronische schakeling levert een 1 wanneer er een stroomstoot doorgaat en een 0 wanneer dit niet het geval is. Bij computers is het van belang meerdere schakelingen te kunnen combineren. Soms mag een stroomstoot pas worden doorgegeven wanneer meerdere schakelaars op 1 staan, in andere gevallen volstaat het dat een van beide schakelaars een stroomstoot doorgeeft. De benodigde wiskunde werd geleverd door het werk van de Schotse wiskundige George Boole (1815–1864). Hij schreef in 1847 een boek waarin hij het binaire talstelsel combineerde met de logische verbindingen and, or, not. Voor de rekeneenheden van computers leverde dit de gepaste oplossing om meerdere verbindingen te kunnen combineren. De Brit Alan Turing (1912–1954) ontwikkelde een theoretisch model voor een ‘computer’ onder de naam turingmachine. Deze Logical Computing Machine bleef bij een gedachte-experiment. Turing werd vooral beroemd omdat hij tijdens de Tweede Wereldoorlog de geheime Enigma- code kon kraken. Hiervoor ontwierp hij samen met Tommy Flowers (1905– 1998) de Colossus-computers, die voldoende rekencapaciteit hadden om de Duitse codes te kraken. In 1952 werd hij gearresteerd op verdenking van homoseksualiteit en tot een experimentele chemische castratie veroordeeld. Op 7 juni 1954 werd hij levenloos teruggevonden. Hij zou zelfmoord hebben gepleegd door te bijten in een met cyanide vergiftigde appel. Volgens de legende staat deze appel symbool voor het logo van de Amerikaanse computerfirma Apple. Over Turings dood deden al snel wilde verhalen de ronde. Volgens één complottheorie was Turing om het leven gebracht door de Britse geheime dienst omdat hij door zijn werk tijdens de oorlog op de hoogte was van veel staatsgeheimen. De Hongaar John von Neumann (1903–1957) tekende kort na de oorlog de architectuur uit voor computers. Een computer moest beschikken over een invoereenheid, een processor voor de verwerking van de invoer, een uitvoereenheid en een geheugen voor de opslag van data. De gegevens en de programma’s moesten binair (op basis van het talstelsel van Leibniz) worden opgeslagen. In 1945 bouwde hij zijn eerste edvac-computer, die echter duidelijk was afgekeken van een vroeger model van de Amerikaan John Atanasoff (1903–1995). Omdat het patent niet goed was geregeld, konden anderen met zijn ideeën aan de haal gaan. Hierdoor stond zijn toestel ook ongewild model voor de eniac (Electronic Numerical Integrator and Calculator) van John Mauchly (1907–1980) en John Eckert (1919– 1995). Zij presenteerden vol trots hun toestel als de eerste elektronische digitale computer. Dankzij de elektronenbuizen was de rekencapaciteit enorm vergroot, maar de buizen maakten het toestel ook erg kwetsbaar. Een elektronenbuis of vacuümbuis kan elektrische signalen versterken of nullen en enen doorgeven. De Mark I maakte voor zijn schakelingen gebruik van elektrische relais, die toelaten een grote stroom aan of uit te zetten met een kleine stroom. Hierdoor waren ze erg geschikt voor gebruik in computers. Maar het resulteerde wel in een zeer groot toestel met meer dan 700.000 onderdelen en 80 kilometer elektrische draden. In 1879 had Thomas Edison de elektrische gloeilamp uitgevonden. Hij leidde de stroom door een stukje verkoold katoen, waardoor het begon te gloeien en licht afgaf. Om te voorkomen dat de draad volledig verbrandde onder invloed van de lucht, plaatste hij het in een luchtledige glazen bol. Veel onderzoekers begonnen te experimenteren met de mogelijkheden van de lamp en dit leidde tot onder meer de radiobuis en de elektronenbuis, die ook perfect bruikbaar bleek als schakelaar in computers. Een relais bevatte veel bewegende onderdelen en zorgde voor relatief lange schakeltijden. Omdat een kleine wijziging in de elektronen een grote verandering kan veroorzaken in de doorgelaten stroom, was een elektronenbuis perfect bruikbaar als versterker. De ENIAC bevatte 18.000 buizen en was in alle opzichten sneller dan de Mark I. Toch had een elektronenbuis ook heel wat nadelen. Ze was niet alleen duur en erg breekbaar, maar slorpte ook massa’s energie op. De komst van de transistor in 1948 loste alle problemen op. De eerste patenten op een transistor dateren al uit 1928, maar lijken nooit in de praktijk te zijn omgezet. De transistor van William Bradford Shockley (1910–1989), John Bardeen (1908–1991), en Walter House Brattain (1902–1987) zou echter al snel de elektronenbuis verdringen. De transistor was veel kleiner, goedkoper en betrouwbaarder dan de elektronenbuis. Bovendien verbruikte hij minder elektriciteit en produceerde minder warmte. Net zoals een elektronenbuis is de transistor (transfer­resistor) een versterker, maar kan hij ook nullen en enen doorgeven. Jack Kilby (1923–2005) van Texas Instruments voegde in 1958 een tiental transistors samen in één geïntegreerde schakeling. Tegelijkertijd kwam Robert Noyce (1927–1990) van Fairchild Semiconductor met een soortgelijk circuit op de proppen. Het kreeg al snel de naam ‘ic’ (integrated circuit), maar is bij het grote publiek vooral bekend geworden onder de naam ‘chip’.

Sindsdien is de chip uitgegroeid tot het basisonderdeel van elektronische apparaten zoals de computer. Het aantal transistors op een chip zou steeds maar toenemen. Bovendien werden de transistors alsmaar kleiner, waardoor een chip in onze tijd al snel miljoenen tot zelfs meer dan een miljard transistors telt. Het groeiende aantal transistors heeft ertoe geleid dat ook de rekenkracht van computers enorm is toegenomen. Volgens de befaamde wet van Moore (Gordon Earle Moore, 1929) zou de benodigde oppervlakte voor één transistor om de twee jaar halveren. Elke twee jaar kwam er dus een nieuwe ‘chiptechnologiegeneratie’ met transistors die slechts half zo groot zijn als die van de vorige generatie. Uiteraard kan dit niet oneindig doorgaan. Men kan immers niet kleiner gaan dan de grootte van een atoom. Lange tijd daalde ook de prijs van nieuwe transistors, maar ook daaraan komt stilaan een einde. De initiële investeringen voor het ontwerp van een chip zijn door de miniaturisatie zo hoog geworden dat de prijzen enkel nog zakken bij immense productievolumes. Van grote invloed op de miniaturisatie is de consumentenelektronica met steeds lagere prijzen. De schaling leidt er ook toe dat we elektronische toestellen steeds sneller als voorbijgestreefd beschouwen, wat de wegwerpmaatschappij in de hand werkt.