Aantekeningen Ch. 4 Artificial neural networks

Aantekeningen Ch. 4 Artificial neural networks Gerard Vreeswijk Samenvatting Dit zijn aantekeningen gemaakt die ik in 1998 heb gemaakt i.h.k. van een college Machine Learning aan de Universiteit van Groningen. Ik weet niet of alles wat er in staat nog even waar is, maar denk wel dat sommige delen ervan nog steeds bruikbaar zijn.

1

Inleiding

In dit college1 zullen neurale netwerken worden behandeld. Neurale netwerken zijn de laatste 40 jaar bijzonder intensief onderzocht en toegepast. Naar mijn mening is Chapter 4 (uit Mitchell) in vergelijking met andere hoofdstukken uit het boek goed te bestuderen. Mitchell legt alles duidelijk uit, en laat nergens “gaten” vallen. Ook in algemene zin is het één van de betere inleidingen in neurale netwerken. De tekst spreekt meestal voor zichzelf en daarom zie ik weinig noodzaak om zaken nog eens opnieuw uit te leggen, zoals ik soms in vorige hand-outs gewend was te doen. Deze keer zal ik hier en daar, per bladzijde, wat opmerkingen plaatsen. E.e.a. is opgenomen onder het kopje “leeshulp”.

2

Leeshulp

Wat punten:

1

Hiermee wordt dus het college ML uit 1998 bedoeld.

1

Aantekeningen Ch. 4 Artificial neural networks, 15 juni 2009

2

Blz. 86 - Onderaan de bladzijde wordt het concept “hyperplane” gebruikt. Een hyperplane is een vlak in IRn , met n > 3. Bijvoorbeeld, in IR5 is een hyperplane een 4-dimensionale ruimte die IR5 in tweeën deelt. - Verder kunnen we stellen dat - H = {w |w ∈ IRn+1 } - D = {(x1 , t1 ), (x2 , t2 ), (x3 , t3 ), . . . , (xn , tn )} waarbij elke xi de input en elke ti de (reëlwaardige) output van het i-de trainingsvoorbeeld is. - X = {x | x fungeert als input voor een specifiek ANN} - c : X → correcte targetwaarden Blz. 88 - De (ongenummerde) vergelijking Δwi = η(t − o)xi is het centrale item in Sectie 4.4.2, dat de meeste aandacht zal vergen bij het begrijpen van de werking van de perceptron training rule. Deze vergelijking zegt dat de gewichtscorrectie Δwi van wi in eerste instantie bepaald wordt door t − o. Als t en o ver van elkaar af liggen, zal t − o groot zijn, en als t en o dicht bij elkaar liggen zal t − o klein zijn, zodat de daaruit volgende correcties in eerste instantie ook groot resp. klein zullen zijn. Verder wordt de gewichtscorrectie bepaald door de input xi zelf . Als door kanaal i namelijk steeds relatief grote waarden komen (bv. 10233, 10245, 10201, etc.) dan zal het bijbehorende gewicht wi ook in die orde van grootte gecorrigeerd dienen te worden ten opzichte van de andere gewichtswaarden. Vandaar de term xi in het product. Tenslotte staat η voor een reductiefactor, om correcties niet te ‘wild’ te laten verlopen. Probeer verder de redenering bovenaan blz. 89 even te volgen. Blz. 89 - Misschien is het nuttig om je bij Vergelijking (4.2) te realiseren dat de kleinstekwadraten fout van w over D gegeven wordt door (td − od )2 kleinste-kwadraten-fout(w) = d∈D

Dus vergelijking (4.2) is bijna gelijk aan de kleinste-kwadraten fout, maar toch niet helemaal, omdat de term zonder wortel verderop handiger werkt bij het nemen van de afgeleide.


3

Blz. 91 - Onderstaande figuur stelt de dwarsdoorsnede van een foutenoppervlak voor.

dimensie idwarsdoorsnede van het E(w) oppervlak:

E(w)

w Probeer in dit vlak eens de vector te schetsen in het punt (w, E(w)) die bij de hoort. Stel, η = 0.5. Probeer vervolgens in dit partiële afgeleide ∂E(w)/∂w i vlak de vector te schetsen in het punt (w, E(w)) die bij de waarde Δwi hoort. Blz. 92 - Derde regel van boven: “(. . . ) in terms of the linear inputs xid , outputs td , and (. . . )” moet zijn: “(. . . ) in terms of the linear inputs xid , outputs od , and (. . . )”. - Vergelijk Vergelijking (4.7) met de (ongenummerde) vergelijking Δwi = η(t − o)xi op blz. 88. Wat valt je op? - In de tekst wordt niet direct uitgelegd waar het voorvoegsel “stochastic” voor staat. Welnu, zoals in Sectie 4.4.3.3 door Mitchell wordt uitgelegd. kan de standaard backpropagation methode zowel incrementeel (per d ∈ D) als in batch (per D) worden toegepast. Echter, de incrementele variant convergeert i.h.a. niet naar een locaal minimum op het foutenoppervlak. Om toch convergentie te krijgen, word vaak de learning rate η geleidelijk verkleind. Omdat elk element d ∈ D slechts een indicatie geeft van de richting waarin moet worden bewogen op het foutoppervlak, wordt deze methode ook wel stochastische benadering genoemd. - De pure, i.e. niet-incrementele vorm van gradient descent wordt voor de duidelijkheid vaak aangeduid met batch processing. Op zich is er voor batch processing geen reden om nadeel te ondervinden van trage convergentie en het eindeloze afstellen van de learning rate η, omdat de uiteindelijke gradient precies de goede richting op wijst. Bij de stochastische methode is dit niet het geval. (Daarom wordt bij de stochastische methode η ook altijd kleiner gekozen.)


4

Blz. 94 - In de passage op het midden van bladzijde 94 wordt pas ingegaan op de verschillen tussen de delta- en de perceptron-regel. Belangrijk. (Verder duidelijke passage.) Blz. 96 - Bovenaan wordt beweerd dat meerdere lagen van lineaire eenheden alleen maar weer lineaire eenheden produceren. Hoe valt dit in te zien? In theorie door alles uit te schrijven, maar dat is een beetje overdreven. Misschien wél door je te realiseren dat de uitkomsten van perceptrons (op zich lineaire eenheden) weer lineair gecombineerd worden door andere perceptrons. Blz. 97 - Boven het midden staat: dσ(y) = σ(y)· (1 − σ(y)) dy Deze gelijkheid is niet triviaal. Controleer zelf eens of hij klopt. - Backpropagation is zonder meer het meest moeilijke algorithme uit dit hoofdstuk. De moeilijkheid van het algorithme zit hem nog niet eens zozeer in het gebruik ervan (immers: domweg vergelijking T4.4 op blz. 98 toepassen), maar in de theoretische onderbouwing.

Backpropagation is denk ik het best uit te leggen door eerst het probleem te formuleren dat er de oorzaak van is dat een relatief ingewikkelde techniek als backpropagation moet worden toegepast. 1. Het probleem. Welnu, de moeilijkheid doet zich voor bij het aanpassen van de gewichten in meer-lagige netwerken. Deze netwerken bestaan uit eenheden (knopen) waarvan de output per knoop door de sigmo¨ıde-functie wordt bepaald. Dat laatste is op zich geen probleem. Wat wél een probleem is, is dat voor het toepassen van een leeralgorithme op een meer-lagig netwerk voor zowel uitwendig (input/output) als inwendig, een fout bekend moet zijn. Deze fout moet uitdrukken hoe ver de output-waarde van een bepaalde knoop naast de gewenste waarde zit, zodat de gewichtswaarden in die knoop gecorrigeerd kunnen worden. Maar het punt is dat alleen voor de laatste (uitwendige) output-knopen de gewenste waarden, en dus de respectievelijk fouten, bekend zijn. Voor inwendige knopen zijn de fouten—laat staan gewenste output-waarden—onbekend. [Formule (4.13) is daarom overigens een beetje misleidend: daar verschijnt tdk als targetwaarde van onder


5

ander inwendige knopen, maar deze tdk ’s bestaan helemaal niet. Noch in het verhaal hierboven als in het backpropagation algorithme zelf.] In zoveel woorden is dit het probleem dat zich voordoet bij het aanpassen van gewichten in meer-lagige netwerken. 2. Een mogelijke oplossing. Backpropagation (letterlijk: “terug-voortplanting”) van fouten van de laatste knopen door het netwerk, terug door het netwerk heen, is één van de mogelijk oplossingen om toch nog een fout te definieëren voor inwendige knopen. Het idee hierbij is dat elke inwendige knoop verantwoordelijk is voor de fouten van zijn opvolgers. Immers, elke inwendige knoop bewerkt informatie ten behoeve van zijn opvolgers en als deze inwendige knoop dat niet goed doet, maken zijn opvolgers fouten. De filosofie is dat niet alleen de gewichten van de opvolgers, maar ook de gewichten van de inwendige knoop naar aanleiding van deze fouten aangepast moeten worden. Per inductie zijn de fouten van opvolgers bekend, zodat ze kunnen worden doorberekend naar hun voorgangers. De verdeelsleutel die daarbij gehanteerd wordt, wordt bepaald door de gewichtswaarden die liggen op de takken die ontspruiten uit de inwendige knoop (naar de opvolgers). 3. Fout van een inwendige knoop. De fout van een inwendige knoop wordt bepaald door een soort gewogen gemiddelde van de fouten van de opvolgers.2 Als een inwendige knoop bijvoorbeeld een tak heeft met een hoge capaciteit (i.e. hoge gewichtswaarde) en die tak leidt naar een opvolger die op dat moment een grote fout maakt, dan kan deze fout voor een belangrijk deel toegeschreven worden aan de toeleverende inwendige knoop. Immers, die inwendige knoop heeft een groot getal aangeleverd, mede waardoor z’n opvolger een grote fout maakt. 4. Dit was de intu¨ıtieve motitivatie. Een wiskundige onderbouwing (eindigend in dezelfde conclusie) is te vinden in Sectie 4.5.3 (p. 101, Mitchell). Blz. 98 - Het zojuist besproken idee is terug te vinden in Vergelijking (T4.4). De grootheid oh (1 − oh ) is de afgeleide van de sigmo¨ıde functie. 2

“Soort,” omdat voor een gewogen gemiddelde nog door het aantal opvolgers gedeeld moet worden.


6

Blz. 100 - In Sectie 4.5.2.1 wordt gesproken over “adding momentum”. In de literatuur is deze methode ook wel bekend onder de naam “heavy ball method”. Blz. 101 - Het is misschien nuttig om bij de lijst onderaan, een paar perceptrons te tekenen met daarbij de verschillende xji ’s, wji ’s, netj ’s, etc. - Mijn ervaring met de uitleg in Sectie 4.5.3 is dat deze netjes verloopt, vrij compleet is, en nergens zaken weglaat. Herleidingen worden gedaan in kleine stappen en zijn goed te volgen. Blz. 112 - Zoals vermeld in de web-pages, zijn de bijbehorende sources geplaatst op de TCW-machines, in de directory /usr/local/bin/ml/facetrain Copieer deze files naar een directory onder je home-directory en type “make”. De executable “facetrain” zal dan aangemaakt worden. Type dan “doit” om de werking van facetrain te testen met specifieke parameters. Lees verder de files “readme.txt,” “homework96.ps,” en faces.html”. Ook voor DOS is facetrain beschikbaar. Zie http://tcw2.ppsw.rug.nl/˜gerard/ml/software.html en download het bestand “facetrain.zip” (405 Kb).


7

Blz. 117 • Het optellen van (gekwadrateerde) gewichten bij de standaard kleinstekwadraten fout staat bekend onder de naam weight decay. De bijkomende foutterm heeft er, per definitie, een bias tegen hoge gewichtswaarden. De bijkomende foutterm in weight decay zorgt ervoor dat de gewichten naar kleinere waarden convergeren dan ze anders zouden doen. Het laat de capaciteiten van de kanalen om het zo maar te zeggen, niet groter worden dan strikt noodzakelijk is. Grote gewichten zijn namelijk op twee manieren nadelig. (a) Grote gewichten naar inwendige kopen kunnen ervoor zorgen dat de output zich ‘te abrupt’ of zelfs discontinu gaat gedragen. (b) Grote gewichten naar uitwendige output knopen kunnen ervoor zorgen dat de output een excessief groot bereik gaat aannemen—groter dan wat wordt afgegrensd door de data. Weight decay is een deelklasse van regulatiemethoden. Andere regularisatiemethoden kunnen niet alleen betrekking hebben op de gewichten, maar ook op andere afgeleiden van de output. • Het optellen van een fout t.a.v. de glooiing betreft het betrekken van 2e of 3e orde afgeleiden in het berekenen van Δw. Met 1e-orde afgeleiden worden de nieuwe gewichtswaarden met behulp van een raakvlak aan het foutoppervlak, bepaald. Met het toevoegen van 2-orde afgeleiden wordt dit raakvlak vervangen door een kwadratisch (parabolisch) vlak, wat mee kan krommen met het foutoppervlak, en zo de aanpassing in gewichten beter kan voorspellen. Dit kan verder worden gegeneraliseerd tot het nemen van n-e orde afgeleiden, waarbij het benaderende oppervlak n´ og beter mee kan krommmen met het foutoppervlak. Het uitrekenen van hogere-orde afgeleiden kost (uiteraard) extra inspanning, en het is niet altijd duidelijk of deze extra rekenslag terug verdient wordt door een snellere convergentie. outputwaarden. Blz. 118 • Minimaliseren van kruis-entropie wil zeggen dat je het netwerk toestaat continue outputwaarden te genereren die variëren over de gehele range, maar dat je tegelijkertijd het netwerk stimuleert te kiezen voor geprononceerde outputwaarden. • Het samennemen van ‘kanalen’ waarvan de gewichten gedurende enkele iteraties gelijk oplopen is een techniek die appelleert aan de intu¨ıtie dat aan dergelijke kanalen een benoembare domeinvariabele ten grondslag ligt. Hiermee gaan we een beetje de richting op van Bayesiaanse belief-netwerken. Zie blz.184-191, Mitchell.


8

Blz. 119 - Recurrente netwerken zijn met name ontworpen om cyclische verschijnselen, zoals bv. de dagelijkse aandelenkoersen, te modelleren. Backpropagation werkt in grote lijnen als gebruikelijk.

3

Historie

Disclaimer: onderstaand overzicht is incompleet. Personen

Jaar

Mijlpaal

1943

Introductie van de symbolische representatie van een neuron d.m.v. gewichten en drempelwaarden die overschreden moeten worden.

N. Wiener

1948

Met zijn cybernetica, welke onder meer handelt over feed-back loops, draagt Norbert Wiener bij aan het leren van ANN’n.

F, Rosenblatt

1960

Vond het eerste bewijs van de perceptron convergentie stelling.

Minsky & Papert

1969

Karakterisering van (on)mogelijkheden van perceptron. Onderzoek naar neurale netwerken zakt tijdelijk in.

Paul J. Werbos, Harvard U.

1974

Backpropagation

David E. Rumelhart, U. of California, San Diego, David B. Parker, Stanford

jaren ’80

Pakken idee van backpropagation weer op.

Rumelhart, Ronald J. Williams, Geoffrey E. Hinton

1986

Popularisering van de generalized delta-rule door overtuigende toepassingen. (Handschriftherkenning, voorspellen van aandelenkoersen, maximaliseren van de opbrengst van chemische processen, etc.)

McCullough Pitts

&


Neural network community

4

1985 - nu

9

Uitbreidingen en aanpassingen op backpropagation (algorithmische veranderingen, toevoegen van heuristieken, toevoegen van kosten termen op gewichten) onder namen als Quickprop (Fahlman 1989), RPROP (Riedmiller en Braun 1993), etc. Verdere inbedding in reguliere industriële en dienstverlenende processen. Kortom, neurale netwerken zijn vanaf 1985 zo’n beetje gesettled.

Nawoord

Zoals in de introductie al opgemerkt zijn neurale netwerken de laatste 40 jaar bijzonder intensief onderzocht en toegepast. Veel is er gedaan t.a.v. de volgende deelonderwerpen: Implementatie cq. programmering.

Een grote verscheidenheid aan ANN’n zijn reeds uitgeprobeerd. In de praktijk levert het programmeren niet eens het meeste werk op, maar blijkt het zoeken en prepareren van de data juist de bottleneck te zijn. (“Data-acquisition bottleneck.”)

Empirisch onderzoek.

Veel zaken (juiste aantal knopen in hidden layer, learning rate, convergentiecriteria, etc. etc.) zijn in de loop der tijd empirisch, d.w.z. proefondervindelijk, d.w.z. door uitproberen, vastgesteld.

Relatie met statistiek en kansrekening.

Sommige neurale netwerken hebben geen raakvlak met statistiek (bv. netwerken die biologische systemen modelleren), andere neurale netwerken leren anders (Hopfield netten) en hebben daarom, om die reden, weinig van doen met statistiek. Maar de meeste neurale netwerken zijn wel verwant aan statistische methoden, omdat ze zijn ontworpen om te leren op basis van ‘vervuilde’ (noisy) gegevens. Zo’n 20 jaar geleden was de neurale-netwerk gemeenschap nog voornamelijk geconcentreerd op de principes van neurale netwerken zelf , zonder in dat stadium veel oog te hebben voor de dwarsverbanden met statistiek. Inmiddels zijn die dwarsverbanden gelegd (Balakrishnan, 1994, Cheng, 1993, en vele anderen). De verbanden zijn groot: in de neural-net FAQ worden feedforward netten (met of zonder


10

interne knopen), Kohonen netten, en Hebbiaans leren, expliciet gerelateerd aan meer of minder bekende statistische methoden. Daarbij gaat het bij neurale netwerkers vooral om het algorithme, i.e. het proces, terwijl het de statistici vaak om het resultaat gaat. Standaard backpropagation, Quickprop en Levenberg-Marquardt, bijvoorbeeld, zullen door een statisticus worden gezien als verschillende algorithmen om het statistische concept “feedforward net” te implementeren. Aan de andere kant zien statistici verschillende trainingscriteria, zoals kleinste-kwadraten en minimum kruis-entropie, als fundamenteel verschillende schattingsmethoden met verschillende statistische eigenschappen. Veel moet nog worden gedaan t.a.v. de volgende deelonderwerpen: Garanties t.a.v convergentie en snelheid van convergentie.

Zijn er haast niet. Zie discussie in Sectie 7.4.4 (blz. 218 e.v.) Mitchell. Voor multi-layer perceptron netwerken kan men een Vapnik-Chervonenkis dimensie van de hypotheseruimte bepalen, maar voor knopen met sigmo¨ıde-eenheden (zie blz. 96, Mitchell) kan men dit (nog) niet. (Zie onderaan blz. 219, Mitchell.)

Optimale vorm v.h. netwerk.

Weinig tot niets over bekend. Wordt nu nog vaak proefondervindelijk of heuristisch [bv. met cascade-correlatie (blz. 121, Mitchell)] bepaald.

Theorievorming in het algemeen. Einde document.

Aantekeningen Ch. 4 Artificial neural networks

Recommend Documents