COMP572

Neural Networks

Ludovic Hilde

Email: [email protected]

Summer 2008

06/11/08

Assignment 1

A. Post a copy of the code.

The source code of the k-winner network has been written in Java.

Click on the link below to access the source code of the k-winner network program:

k-winner network source code

Click on the link below to launch the Java Applet:

k-winner network applet

1. Does the Energy decrease at each iteration?

The data shows that the energy decreases after each iteration.

The Energy as a function of t is plotted below:

NOTE:

Step1 = 0.005

Step2 = 0.025

Step3 = 0.05

Step4 = 0.1

Ext1 = 0.5

1. Does the network converge to a state that corresponds to "k-winners"?

Note: All k-winners have been bolded

Case 1: Ext=0.5 and Step=0.005.

There is only 1 k-winner; it is the neuron with the largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.2808294929250935

0.9155753910306337

0.04246503724834605

0.6196046834788637

0.6690751137031209

0.5491307229147274

0.3142257462041448

0.6898920947049867

0.7738815883461695

0.310617023510796

0.941456279811668

0.9744048310952396->Largest initial activation

0.9265208824896938

0.5437988883865476

0.45500172171388265

0.1978731942874089

0.8796083830032624

0.05692922748712159

0.5653029123935496

0.13558654309534457

/-------------------------------------

Final Activation

/-------------------------------------

5.912541704248916E-5

0.00472558903599195

6.334056388836447E-6

2.9573412632753055E-4

3.859179237489572E-4

2.114145278808389E-4

7.132155863217423E-5

4.3846541126886046E-4

7.691511565870279E-4

7.070581813870681E-5

0.012770853981506522

0.9332001244377529->k-winner

0.0069259202959666396

2.113871948839552E-4

1.4120752577462056E-4

3.797464139690203E-5

0.002446498214189754

9.011195708732707E-6

2.367559710243518E-4

2.394811600026174E-5

Case 2: Ext=0.5 and Step=0.025.

There is only 1 k-winner; it is the neuron with the largest activation state.

The data is shown below:

/-------------------------------------

Final Activation

/-------------------------------------

4.252970443947093E-5

2.071223171553923E-5

9.198306382208342E-4

2.598052277571819E-5

5.350798895635603E-6

0.9888846724092155->Largest initial activation

2.3436329881083195E-4

2.2938084089592524E-5

1.0332418209143469E-5

1.1684592016767399E-4

0.0030009222006266434

1.5044850470991897E-5

3.431467580635163E-4

1.6588544003701486E-5

3.642064415265403E-5

7.758353542486005E-5

2.127657272030241E-6

2.7394304453988413E-5

1.8200747468764755E-5

1.4083689903757025E-5

/-------------------------------------

Initial Activation

/-------------------------------------

0.4721173667767823

0.32708567235105956

0.8517108973278641

0.36438354811787343

0.11998404877767199

0.9341430979443337->k-winner

0.7390264913886117

0.3334134986015276

0.19623990345245979

0.6373655230718229

0.8845425070059818

0.24727578932699135

0.7673679861236885

0.25887409671564976

0.4049681877833382

0.5494417396123363

0.046432554213382105

0.343503462577772

0.26677349054389776

0.22319640486816117

Case 3: Ext=0.5 and Step=0.05.

There is only 1 k-winner; it is the neuron with the largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.47598145835249495

0.22266911081020102

0.06731673605369426

0.5762271998884199

0.18617399029785764

0.3210965539758629

0.15803470115271856

0.9386570211553874->Largest initial activation

0.030320862908699397

0.11786007142270916

0.517900198209804

0.8375082882311509

0.885456580892957

0.6623164665314388

0.7764423667626787

0.6491616177132605

0.9142428503445676

0.1670832965817316

0.16681444124461942

0.34351994745518233

/-------------------------------------

Final Activation

/-------------------------------------

2.5223454834776795E-6

6.230432647368347E-7

1.3931302940631355E-7

4.605408201429513E-6

5.104448752835027E-7

1.2144366065193974E-6

4.2333532880784155E-7

0.9951315035083956->k-winner

6.440242950660733E-8

2.958449729818368E-7

3.6485879186677005E-6

4.96844948621526E-5

1.5949222790681916E-4

9.985590263882155E-6

2.7201212647197786E-5

1.0046953539810325E-5

0.0026009776671154293

6.429116817004908E-7

6.488439225315187E-7

2.019954125094361E-6

Case 4: Ext=0.5 and Step=0.1.

There is only 1 k-winner; it is the neuron with the largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.3908716672295718

0.8135897986286917

0.7128320814902042

0.14215454869115496

0.4637919235751936

0.33823897944098136

0.6344611528096689

0.5864002141484107

0.8247760148922518->Largest initial activation

0.2723217859696484

0.705668666957291

0.440873462895201

0.1374234212825337

0.025898791008399535

0.6606164301095715

0.4836834500776568

0.015657207485752167

0.6193953325107078

0.6505587200201867

0.5109489927861172

/-------------------------------------

Final Activation

/-------------------------------------

3.846426864344656E-6

3.6342579292949996E-4

6.081465035785375E-5

6.911610151303671E-7

8.790689427653388E-6

4.071620521165413E-6

3.63206031321157E-5

2.686937797797186E-5

0.9973765675723787->k-winner

3.387883514629236E-6

1.1254439624907987E-4

1.229691120163427E-5

1.3864089174240637E-6

1.8817546135019207E-7

8.297297856146732E-5

2.010229859480519E-5

1.371338992876341E-7

6.675577285711473E-5

1.0881943702367791E-4

3.2610007556471556E-5

Case 5: Ext=1.5 and Step=0.005.

There are 2 k-winner; it is the neurons with the 2 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.7907694942679742

0.987531625788485->Largest initial activation

0.6885714533350419

0.8122334523086241

0.06584592755929852

0.5579449832669484

0.90696065715154

0.46021307831339986

0.2896263204832581

0.9205699600322015

0.5760745305738583

0.29072232907904627

0.2436730472552462

0.9761409699631581

0.8869527822669696

0.06996687713398242

0.9816633281565044->Largest initial activation

0.01265351915329449

0.20446660230679703

0.7450741283739594

/-------------------------------------

Final Activation

/-------------------------------------

4.853153498161114E-5

0.995395998285699->k-winner

2.463583203561182E-5

5.874471120230751E-5

5.951899070149491E-7

1.2762036581923033E-5

2.030296460226228E-4

8.237956872599194E-6

3.694414905059017E-6

2.8054311392385496E-4

1.4142790246489092E-5

3.7503438529986092E-6

2.9093321768263036E-6

0.055442495341140416

1.4644874235799344E-4

6.561499268713138E-7

0.9599043749886225->k-winner

1.1043821203358318E-7

2.3204188281604784E-6

3.657484745288103E-5

Case 6: Ext=1.5 and Step=0.025.

There are 2 k-winner; it is the neurons with the 2 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.12094005241086414

0.4225086742255345

0.7921665925339668

0.0872663241907925

0.78058120218932

0.29029143229449705

0.780549979140316

0.3656646224038882

0.052324853473814215

0.9341564940208744->Largest initial activation

0.6828396876482589

0.6730918210371375

0.8184041917005803

0.6622716310492168

0.310996632904872

0.939581683029052->Largest initial activation

0.8971216532299208

0.811585972891448

0.630574858845271

0.7938602899118626

/-------------------------------------

Final Activation

/-------------------------------------

2.969711005859517E-6

1.948433115933972E-5

2.1319173079605586E-4

2.10829308959985E-6

1.9443903105749325E-4

1.043998906809075E-5

2.0269652494842296E-4

1.6060294441507484E-5

1.2793138534903558E-6

0.9924944253001873->k-winner

9.26152922130945E-5

8.860043307004566E-5

3.652101301795465E-4

8.652750488842978E-5

1.3275094537100103E-5

0.9984681840112336->k-winner

0.004760323348846106

3.7528400890820635E-4

7.700676040587691E-5

3.147506827554808E-4

Case 7: Ext=1.5 and Step=0.05.

There are 2 k-winner; it is the neurons with the 2 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.6934289952088167

0.26753807517354955

0.7337309802523909

0.9750807228170841->Largest initial activation

0.036075606882956746

0.7117076378147079

0.5241972941189017

0.5267455461387747

0.45589677978040466

0.2620323271652193

0.9213077859554548

0.05552517704357951

0.3782592015490456

0.17348915543524568

0.0736150120697191

0.9416896237589749->Largest initial activation

0.02835002559046107

0.5018715539519621

0.6313880172983015

0.8879864791097088

/-------------------------------------

Final Activation

/-------------------------------------

1.7510135651254034E-5

1.5888288980041485E-6

2.5581338758716246E-5

0.9999070338433633->k-winner

1.4253774214588562E-7

2.2609825643122945E-5

7.218522671549844E-6

7.572669798626235E-6

5.3499229801607806E-6

1.895678239686039E-6

0.0024785233035690317

2.831650934582581E-7

3.926026276413256E-6

1.143219945805377E-6

4.0448403779020727E-7

0.9954283459699654->k-winner

1.444131969955191E-7

7.923489977943713E-6

1.746825790221699E-5

5.21632343071011E-4

Case 8: Ext=1.5 and Step=0.1.

There are 2 k-winner; it is the neurons with the 2 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.8473729339296241

0.7074774827885115

0.40095570985208817

0.5387840998944059

0.04857515383313549

0.599774550546761

0.4469310602874865

0.7337485939322925

0.6516895314595185

0.14147025276680503

0.32751830401390225

0.20127240238328592

0.32486258695899617

0.3717673977878345

0.8702298787611731->Largest initial activation

0.31451262212330033

0.9060470590044961->Largest initial activation

0.34567987558551494

0.6933513666212126

0.55852217976091

/-------------------------------------

Final Activation

/-------------------------------------

6.409068631154073E-4

6.694938117332507E-5

7.579442545763225E-6

2.0177852277935966E-5

2.8571362229996363E-7

3.4265286236874174E-5

1.3160542822051161E-5

1.4604207767246827E-4

6.914818404477718E-5

1.8675201212555782E-6

8.215047062807537E-6

3.5179864770245364E-6

8.815474560561701E-6

1.2547944754282303E-5

0.9979534847741764->k-winner

9.245913549791669E-6

0.9998476638204677->k-winner

1.1895758900081402E-5

1.7957659023030997E-4

5.659436352450545E-5

Case 9: Ext=2.5 and Step=0.0005.

There are 3 k-winner; it is the neurons with the 3 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.33984394408977747

0.9830144085839567->Largest initial activation

0.5606184969253323

0.03428351964874088

0.8349314920854262

0.4065116189903115

0.811950279142111

0.38098578316802567

0.08350280945299815

0.9278829604455788->Largest initial activation

0.4035067531483557

0.8656978416582979

0.5540061925297333

0.8238144299897577

0.9321114170123989->Largest initial activation

0.5051484286115477

0.669628324958426

0.1609223581367628

0.43042054635992066

0.31625675977552015

/-------------------------------------

Final Activation

/-------------------------------------

1.8887556958836502E-4

0.9995774121679624->k-winner

5.724195350247668E-4

1.1410818708615404E-5

0.006817616352718874

2.6565394121338915E-4

0.0045768632383290635

2.3588289708236887E-4

3.0162074938216057E-5

0.9692598337448682->k-winner

2.6425733050685257E-4

0.01638547814117314

5.673592741012362E-4

0.005794642616389619

0.9819321605583252->k-winner

4.4361423447199856E-4

0.0011513136285014414

6.67395113152695E-5

3.083668935702552E-4

1.7455402608482538E-4

Case 10: Ext=2.5 and Step=0.025.

There are 3 k-winner; it is the neurons with the 3 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.429214010703422

0.1608461170496186

0.33274805037376254

0.9901747877686454->Largest initial activation

0.4140408957964714

0.7311939672979423

0.7241132250938123

0.8854162833634618->Largest initial activation

0.20574031906765056

0.7363328720054128

0.31428701617562893

0.4970891921805717

0.9936615518010873->Largest initial activation

0.3198529259147652

0.280587469571147

0.7405199689710497

0.8033302750489381

0.3148267366479165

0.5973467545336634

0.8216770456795072

/-------------------------------------

Final Activation

/-------------------------------------

3.734578570428539E-5

7.803082881383171E-6

2.302997498699241E-5

0.999999783003466->k-winner

3.55427302493549E-5

2.727399616088891E-4

2.622761765197682E-4

0.9884238852848124->k-winner

1.1600164332820247E-5

3.1141779574510493E-4

2.2851004129702645E-5

6.047357874741101E-5

0.9999998834781726->k-winner

2.4134852368601952E-5

1.957767181214743E-5

3.603607501485944E-4

9.78465571196666E-4

2.4995533414028693E-5

1.194220563054046E-4

0.0018306396564937112

Case 11: Ext=2.5 and Step=0.05.

There are 3 k-winner; it is the neurons with the 3 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.11375110209729078

0.128808385243107

0.1437433277225062

0.7176890350888362

0.8903057615462387

0.09554971627514253

0.12920205177850108

0.9633597133017194->Largest initial activation

0.9106230744766846

0.14242884958365443

0.9740573123464963->Largest initial activation

0.9599150644495016->Largest initial activation

0.49125790659711266

0.6056358499196612

0.677681389063273

0.05954320592114082

0.06613369359384724

0.3956162659839243

0.27689054527859625

0.2834625533521197

/-------------------------------------

Final Activation

/-------------------------------------

1.2143289891200042E-6

1.4251745673801356E-6

1.6503133718545485E-6

5.680537505231148E-5

8.705971159576934E-4

1.1104775550830897E-6

1.6085330426426476E-6

0.9985856298042042->k-winner

0.003047389925746522

1.9279707603299945E-6

0.9995042106105084->k-winner

0.9983087416065083->k-winner

1.6071825431111966E-5

3.205883140079084E-5

5.454772179311324E-5

7.780157780734765E-7

8.775689271705842E-7

1.0865703513934933E-5

5.7709399148233286E-6

6.103841253450391E-6

Case 12: Ext=2.5 and Step=0.1.

There are 3 k-winner; it is the neurons with the 3 largest activation state.

The data is shown below:

/-------------------------------------

Initial Activation

/-------------------------------------

0.30940348688615704

0.8639737267160815->Largest initial activation

0.39760369385772676

0.9862557694977688->Largest initial activation

0.5725808163202657

0.524487706338627

0.41732533596024435

0.2915646896081773

0.4437363198262825

0.2898317453251068

0.506892796904594

0.2653932392958033

0.7957787255881626

0.35560239634390955

0.7423410434800776

0.43761053981717846

0.3487530096048058

0.8380450771715069->Largest initial activation

0.5161027954598794

0.1844939242844531

/-------------------------------------

Final Activation

/-------------------------------------

1.0368599444708965E-6

0.9980391601253835->k-winner

1.961791026938761E-6

0.9999995713360298->k-winner

6.819528582987452E-6

5.257045749029917E-6

2.8006909086059138E-6

1.323836827663485E-6

3.7077703281957813E-6

1.470412045042362E-6

6.345334118519569E-6

1.4075591697156714E-6

0.0012797847395793487

2.942812634548811E-6

1.521723164538143E-4

5.8361724789470815E-6

3.5008140010964524E-6

0.9999348049020467->k-winner

1.152406256592533E-5

1.2478617831468534E-6

2. Try a case where the initial activations are all equal (non-zero).

I tried the case where all initial activation equaled 0.7; the following results were obtained

/-------------------------------------

Initial Activation

/-------------------------------------

0.7

/-------------------------------------

Final Activation

/-------------------------------------

0.03400281625470863

0.0341346027519756

0.03426690481457396

0.03439972441411308

0.03453306352867281

0.03466692414281013

0.03480130824756522

0.034936217840469304

0.03507165492554921

0.035207621513334786

0.03534411962086419

0.03548115127168948

0.03561871849588228

0.03575682333003908

0.0358954678172863

0.03603465400728488

0.03617438395623516

0.0363146597268815

0.036455483388515834

0.036596857016982696

4 a. Is there convergence to winners?

The data shows that there is no convergence to k-winner.

4 b. Does the Energy decrease at each iteration?

The first 20 iterations gave the following results:

0 85.21184564526004

1 81.85211519222945

2 78.54892950595844

3 75.31110297188359

4 72.14649507124996

5 69.0619641798801

6 66.06334622254796

7 63.15545638185341

8 60.34211136747033

9 57.62616927361955

10 55.009583786608324

11 52.493469432229176

12 50.07817464600291

13 47.763359672820386

14 45.548076619607

15 43.4308493597393

16 41.40975138947

17 39.482480138323595

18 37.64642661707185

19 35.89873963423295

20 34.23638411624757

It is seen that the energy decreases at each iteration when the initial activation is fixed for all neurons.

4 c. Demonstrate your responses by showing a specific simulation

-- Initial activations

-- Activations at convergence

The results of the initial activation and activation at convergence are shown in section 4.

-- Energy plot

The energy plot for neurons with fixed initial activation is shown below:

3. Show (mathematical proof) that the k-winner states are stable equilibrium when the external input satisfies:

k-1 < ext < k.

Hint: K-winner states are the corners of the hypercube corresponding to k neurons at maximum activation and the rest at minimum activation. To show that these states are stable equilibrium you must imagine the activation vector as being very close to, but not on, the hypercube corner. Then show that the dynamics of the network will "drive" the activation vector into the corner, as opposed to away from the corner. That is, if an activation is near the maximum, then the update will add a positive amount, and if an activation is near the minimum the update will add a negative amount.

k-1 < ext < k.

Neural activation updating equation:

a_i(t+1) = a_i(t) + step * (M-a_i(t)) * (a_i(t) - m) * net_i(t)

which is a rough approximation to the differential equation:

da/dt = (M - a_i) * (a_i- m)*( net_I)

(M - a_i) > 0 and (a_{i - m) > 0 because m £ a_i
£
M for i = 1, ..., N}

The sign of da/dt = (M - a_i) * (a_i- m) * ( net_I) is determined by ( net_i)

For a winner neuron, net_i = [Wa + ext]_i= -1 * (k-1) + ext because there are no self connection and there are k winners in total. (k is the number of winners, and ext is the external input.)

For a loser neuron, net_i = -1 * k + ext since all winners are connected to each loser.

For stability, winners or neurons at maximum activation must stay at maximum

So, da/dt must be positive and net_i= -1 * (k-1) + ext > 0 or ext > (k-1) to keep them at maximum.

For stability, losers or neurons at minimum activation must stay at minimum

So, da/dt must be negative and net_i= -1 * k + ext < 0 or k > ext to keep them at minimum.

Thus, for stability, (k-1) < ext < k