Opdracht 1: Het Willshaw netwerk

A. Wat is Willshaw?

Een Willshaw-netwerk is een uiterst eenvoudig algoritme waarmee de werking van een connectionistisch netwerk geïllustreerd kan worden. Het is één van de weinige netwerken die je met de hand kunt doorrekenen. Een Willshaw-netwerk bestaat uit een aantal inputknopen en een aantal outputknopen. Knopen kunnen waarde 1 (actief) of 0 (niet-actief) hebben, gewichten op de connecties tussen knopen zijn ook of 1 (connectie aanwezig) of 0 (connectie niet aanwezig). Je zet het inputpatroon uit als een kolom, en het outputpatroon als een rij. In de matrix die zo ontstaat (zie fig. 1) kan je de gewichten invullen: in elke cel (i,j) van de matrix staat het gewicht tussen de i-de inputknoop (in de kolom links van de matrix) en de j-de outputknoop (in de rij boven de matrix). Voor het leren van een input-outputcombinatie stel je in elke cel waar zowel in de input als in de output een 1 staat, het gewicht gelijk aan 1. Aangezien een 1 in de gewichtenmatrix staat voor dat twee knopen verbonden worden, kan je dit herformuleren als: de actieve inputknoop raken verbonden met de actieve outputknopen. Op alle andere plekken blijft het gewicht zoals het is (gewichten kunnen dus nooit van 1 weer terug naar 0 gaan).

Fig. 1: een Willshaw netwerk dat een aantal patronen leert. De drie kolommen links van het vierkant zijn de inputpatronen, de drie rijen boven het vierkant de outputpatronen. Het meest linkse inputpatroon is gekoppeld aan het bovenste outputpatroon, de twee middelsten zijn gekoppeld en de meest rechtse is gekoppeld met het onderste outputpatroon. Op elke plek waar een inputpatroon en zijn gekoppeld outputpatroon allebei een 1 hebben, daar wordt het gewicht op 1 gezet. Bijvoorbeeld, in de eerste rij heeft het tweede inputpatroon een 1. Op elke plek waarin het bijbehorende, middelste outputpatroon ook een 1 heeft (kolommen 3, 5 en 6) komt een 1 te staan in de gewichtenmatrix (het vierkant). Alle open plekken blijven 0. Van elke 1 in de matrix kan je nagaan hoe hij er gekomen is: welke combinatie van input-en outputpatronen beiden een 1 hadden op die plaats.

Het ophalen van een patroon gaat als volgt (zie fig. 2): presenteer een inputpatroon aan het model. Bereken voor elke outputknoop de input. Dit doe je door te kijken naar alle actieve inputknopen. Als het gewicht tussen een actieve inputknoop en de outputknoop 1 is, tel 1 op bij de input. De input is dus gelijk aan het aantal actieve inputknopen die verbonden zijn met de outputknoop. Vervolgens deel je de input van elke outputknoop door het aantal actieve inputknopen. In fig. 2 zijn er drie actieve inputknopen, dus wordt de input van elke outputknoop gedeeld door 3. Elke outputknoop die nu een input heeft van 1 (hoger kan niet, aangezien een gewicht enkel gelijk aan 1 kan zijn) geldt als actief, elke knoop die een lagere input dan 1 heeft geldt als niet actief. De actieve outputknopen vormen nu het opgehaalde outputpatroon (onderste regel in fig. 2). Dat patroon kan je vergelijken met het oorspronkelijk geleerde outputpatroon, dat in fig. 2, tussen haakjes, boven de gewichtenmatrix is gezet. In fig. 2 is dit patroon perfect opgehaald.

Fig. 2: het ophalen van het middenpatroon uit fig. 1 m.b.v de gewichtenmatrix. Zie tekst voor uitleg.

Fig. 3. Het ophalen van een patroon met behulp van een partieel inputpatroon. Van het inputpatroon zijn maar 2 van de drie knopen actief. Toch wordt het hele patroon opgehaald, omdat in plaats van door 3 de input van outputknopen nu door 2 gedeeld wordt (dit omdat er maar 2 inputknopen actief zijn).

Hoewel Willshaw een heel simpel model is, heeft het al een heel aantal van de eigenschappen die netwerkmodellen nuttig maken. Zo kan het vanuit het partiële inputpatroon het gehele outputpatroon ophalen ("pattern completion"; zie fig. 3). Ook is the goed bestand tegen kleine leasies ("graceful degradation").

B. Praktikumopdrachten

1.1

Construeer een netwerk als volgt: "leer" eerst de combinatie van het inputpatroon (1, 0, 1, 1, 0) en het outputpatroon (1, 0, 0, 1), d.w.z., zet het inputpatroon verticaal uit, het outputpatroon horizontaal (als een rij) en vul alle gewichten aan: zet een 1 op elke plek waar zowel in de input als in de output een 1 staat.

Presenteer nu het patroon (1,0,0,0,0) aan het netwerk. Hoeveel procent van het outputpatroon wordt actief?

1.2. XOR met Willshaw

XOR is informatica-speak voor een logische operatie, de "exclusieve of". Zoals je misschien weet worden vier operaties meestal gepresenteerd als de basis van de logica: "en", "of", "als…dan" en "is equivalent aan". De basis-"of" is de inclusieve "of": A, of B, of A en B allebei; de exclusieve "of" is: A of B, maar niet beiden. Die "of" bedoelen we meestal als we bijvoorbeeld vragen: "bier of wijn?"; we bedoelen niet: "bier, wijn, of wil je ze allebei?".

Deze XOR-operatie heeft een belangrijke rol gespeeld in de geschiedenis van het connectionisme. Dit komt uitgebreid aan de orde in college 3. Het draait allemaal om de stelling van Minsky en Papert dat neurale netten geen XOR-operatie uit kunnen voeren. Je kunt een neuraal net niet zo inrichten dat hij patroon A en patroon B allebei herkent als behorende bij een bepaalde categorie, maar de combinatie van A en B verwerpt. Minsky en Papert geven zelf al aan dat dit alleen van toepassing is op netwerken met twee lagen, een input- en een outputlaag. Meerlagige netwerken kunnen het X-OR-probleem wel oplossen.

In deze opdracht gaan we testen of een Willshaw netwerk in staat is om een XOR-operatie uit te voeren.

- Maak twee inputpatronen A en B. Deze inputs moeten bezitten: features die A en B allebei hebben (=een plaats in de kolom waarin ze allebei een 1 hebben), features die ze allebei niet hebben (=een plaats in de kolom waarin ze allebei een 0 hebben), features die de A wel heeft maar B niet, en ongekeerd. Definieer het disjunctiepatroon van A en B als het patroon dat een 1 heeft op alle plaatsen waar of A, of B, of allebei een 1 hebben. Definieer het negatiepatroon van A en B als het patroon dat overal een 0 heeft waar of A of B een 1 heeft, en een 1 overal waar zowel A en B een 0 hebben. Als je het goed doet zijn het disjunctiepatroon en het negatiepatroon elkaars spiegelbeeld.

- Verzin twee outputpatronen C en D (je bent hier vrij in). C is het XOR-patroon: dit patroon moet actief worden als A het inputpatroon is of als B het inputpatroon is, maar niet bij het disjunctiepatroon van A en B of bij het negatiepatroon van A en B.

a) Leer het netwerk de combinatie van A en C, en van B en C (=pas de gewichtenmatrix aan). Laat zien dat het netwerk bij het aanbieden van A en B het juiste patroon (C) produceert.

b) Probeer nu met het netwerk zoals het er na vraag 1.2a uit ziet wat er gebeurt als je het de combinatie van het disjunctiepatroon als inputpatroon en D als outputpatroon laat leren. Hoe reageert het netwerk nu op A of B?

c) Wat gebeurt er als je ook de combinatie van het negatiepatroon en D leert?

In te leveren: de patronen die je gebruikt hebt, antwoorden op de vragen, de gewichtenmatrix na het leren van de patronen (a la hoe het in de figuren hier staat).

1.3 Meerlagige Willshaw

Willshaw-netwerken zijn per definitie tweelagige netwerken. Willen we testen hoe het zich zou gedragen bij meerdere lagen, dan zullen we zelf een procedure moeten bedenken om zo"n netwerk op te bouwen. De simpelste manier: gewoon twee Willshaw-netwerken achter elkaar plakken. De output van netwerk 1 is de input van netwerk 2. In een Willshaw-netwerk heb je enkel "supervised learning". Daarom moeten we tijdens het leren weten wat de outputpatronen zullen zijn voor het eerste Willshaw netwerk. Leren gebeurt daarom in twee fases: in de eerste mag je het eerste netwerk trainen, in de tweede gebruik je het eerste netwerk om een output te produceren, die je vervolgens gebruikt als input voor het tweede netwerk. Leer dan de associaties tussen deze inputpatronen en twee outputpatronen.

Concreet moet je het volgende doen.

-Neem de twee inputpatronen A en B uit vraag 1.2, en ook de disjunctie- en negatiepatronen.

-Construeer twee outputpatronen, C en D, voor laag 2. Deze kunnen heel simpel zijn: (1,0) en (0,1) bijvoorbeeld. Je moet er, net als bij 1.2, voor zorgen dat C actief wordt bij de inputpatronen A en B, en D bij het disjunctiepatroon van A en B, en bij het negatiepatroon.

-Construeer een set van middenpatronen: patronen die de output zijn in laag 1, en de input voor laag 2.

-Bedenk een leerschema voor laag 1, een schema dat aangeeft welke combinaties geleerd worden. Bedenk dus welk middenpatroon met welke input of inputs (A, B, het disjunctiepatroon en/of het negatiepatroon) gekoppeld moet worden. Pas de gewichten aan in laag 1.

-Geef een input in laag 1, bereken de output, geef dit als inputpatroon aan laag 2. Zet het goede ouputpatroon aan in laag 2 (=outputpatroon C als de input in laag 1 A of B was, outputpatroon D als de input het disjunctiepatroon of het negatiepatroon). Pas de gewichten aan in laag 2.

-Test je netwerk. Reken alle inputpatronen door in laag 1, reken de output van laag 1 als input in laag 2 door, kijk of je het goede outputpatroon (C of D) in laag 2 activeert.

Probeer het probleem op te lossen.

* Als het kan, laat dat met een voorbeeld zien, en geef aan in welke gevallen het wel kan en in welke niet.

* Als het niet kan, laat dit ook met een voorbeeld zien en geef redenen waarom het volgens jou niet kan.