Unsupervised competitive learning algorithm from scratch in javascript

Question

I'm a mathematician who is new to programming and I'm currently reading the book "Theory of Neural Networks" by Rojas. To become better, I try to program every algorithm that is described in the book using javascript (to be precise: the p5js editor). Let \$X=\{x_{1},\ldots,x_{N}\}\subset\mathbb{R}^{n}\$ be a set of points viewed as vectors. Let's assume I want to find \$ k\$ clusters in the set \$X\$. The algorithm goes as follows:

start: Initialize a set of \$k\$ normalized random vectors \$\{w_{1},\ldots,w_{k}\}\$, called weight vectors.

test: Select \$x_{j}\in X\$ randomly and compute the dotproduct \$x_{j}\cdot w_{i}\,\forall\,i\in\{1,\ldots,k\}\$. Find \$m\in\{1,\ldots,k\}\$ such that \$x_{j}\cdot w_{m}\geq x_{j}\cdot w_{i}\,\,\forall\,i\in\{1,\ldots,k\}\$.

corrcet: Substitute \$w_{m}\$ by \$w_{m}+x_{j}\$ and normalize. Then go back to test.

Here is my code:

let off = 20;  // offset to not touch boundary

class Point {
  constructor() {
    this.x = random(-width/2 + off , width / 2 - off);
    this.y = random(-height / 2 + off, height / 2 - off);
  }
  show() {
    stroke(239, 12, 12);
    strokeWeight(4);
    point(this.x, this.y);
  }
}

// function for initializing random weight vectors
function setWeights(l) {
  let weights = [];
  let v;
  for (let i = 0; i < l; i++) {
    v = createVector(
      random(-width / 2 , width / 2 ),
      random(-height / 2 , height / 2 )
    );
    weights.push(p5.Vector.mult(v, 1 / v.mag()));
  }
  return weights;
}

// k = # of weight vectors, N = # of learningsessions
function computeClusters(inpts, k, N) {
  let w = setWeights(k);
  let erg, dotprods, ind, e, m, maxIndex;
  for (let j = 0; j < N; j++) {
    dotprods = [];
    ind = floor(random(0, inpts.length));
    e = inpts[ind];
    for (let i = 0; i < w.length; i++) {
      dotprods.push(e.dot(w[i]));
    }
    m = max(dotprods);
    maxIndex = 0;
    for (let i = 0; i < dotprods.length; i++) {
      if (dotprods[i] == m) {
        maxIndex = i;
      }
    }
    erg = e.add(w[maxIndex]);
    w[maxIndex] = erg.mult(100/erg.mag());
  }
  return w;
}

// function for displaying vector in an "appropriate" way
function drawVector(vec, mycolor) {
  let arrowSize = vec.mag() / 10;
  push();
  stroke(mycolor);
  strokeWeight(1.5);
  fill(mycolor);
  line(0, 0, vec.x, vec.y);
  rotate(vec.heading());
  translate(vec.mag() - arrowSize, 0);
  triangle(0, arrowSize / 4, 0, -arrowSize / 4, arrowSize, 0);
  pop();
}

let points = [];
let vectors = [];
let w = [];
function setup() {
  createCanvas(400, 400);
  for (let i = 0; i < 10; i++) {
    let p = new Point();
    points.push(p);
    vectors.push(createVector(p.x, p.y));
  }
  w = computeClusters(vectors, 3, 10);
}

function draw() {
  background(165, 195, 239);
  translate(width / 2, height / 2);
  scale(1, -1);
  push();
  strokeWeight(0.5);
  stroke(125);
  line(-width / 2, 0, width / 2, 0);
  line(0, -height / 2, 0, height / 2);
  pop();
  for (var i = 0; i < points.length; i++) {
    points[i].show();
  }
  push();
  for (let j = 0; j < w.length; j++) {
    drawVector(w[j], color(50, 175, 150));
  }
  pop();
}

Now, the algorithm seems to performe quite well, see the attached pictures. The only problem I have is: why does my code sometimes produce two and sometimes produce three weight vecotrs, although I declared to create three: see w = computeClusters(vectors, 3, 10);?

Thanks in advance for your help. If you have any general suggestions regarding my code, feel free to give me some input. :)

Answer 1

In some cases where it seems that it only produces two weight vectors instead of three, the x and y Vector properties are less than 1. I played around with your code to be able to provide a visual of this effect, such as using different colors for each weight vector and showing the values of the x and y properties in a table. If you are not seeing one of the weights, check the values in the table.

let off = 20; // offset to not touch boundary
var vectorColors = [];

// added for clean output details
function output(obj) {
  let [w1, w2, w3] = obj;
  vector1x.textContent = String(w1.x.toPrecision(4));
  vector1y.textContent = String(w1.y.toPrecision(4));
  vector2x.textContent = String(w2.x.toPrecision(4));
  vector2y.textContent = String(w2.y.toPrecision(4));
  vector3x.textContent = String(w3.x.toPrecision(4));
  vector3y.textContent = String(w3.y.toPrecision(4));
}

class Point {
  constructor() {
    this.x = random(-width / 2 + off, width / 2 - off);
    this.y = random(-height / 2 + off, height / 2 - off);
  }
  show() {
    stroke(239, 12, 12);
    strokeWeight(4);
    point(this.x, this.y);
  }
}

// function for initializing random weight vectors
function setWeights(l) {
  let weights = [];
  let v;
  for (let i = 0; i < l; i++) {
    v = createVector(
      random(-width / 2, width / 2),
      random(-height / 2, height / 2)
    );
    weights.push(p5.Vector.mult(v, 1 / v.mag()));
  }
  return weights;
}

// k = # of weight vectors, N = # of learningsessions
function computeClusters(inpts, k, N) {
  let w = setWeights(k);
  let erg, dotprods, ind, e, m, maxIndex;
  for (let j = 0; j < N; j++) {
    dotprods = [];
    ind = floor(random(0, inpts.length));
    e = inpts[ind];
    for (let i = 0; i < w.length; i++) {
      dotprods.push(e.dot(w[i]));
    }
    m = max(dotprods);
    maxIndex = 0;
    for (let i = 0; i < dotprods.length; i++) {
      if (dotprods[i] == m) {
        maxIndex = i;
      }
    }
    erg = e.add(w[maxIndex]);
    w[maxIndex] = erg.mult(100 / erg.mag());
  }
  output(w);
  return w;
}

// function for displaying vector in an "appropriate" way
function drawVector(vec, mycolor) {
  let arrowSize = vec.mag() / 10;
  push();
  stroke(mycolor);
  strokeWeight(1.5);
  fill(mycolor);
  line(0, 0, vec.x, vec.y);
  rotate(vec.heading());
  translate(vec.mag() - arrowSize, 0);
  triangle(0, arrowSize / 4, 0, -arrowSize / 4, arrowSize, 0);
  pop();
}

let points = [];
let vectors = [];
let w = [];

function setup() {
  createCanvas(400, 400);
  for (let i = 0; i < 10; i++) {
    let p = new Point();
    points.push(p);
    vectors.push(createVector(p.x, p.y));
  }
  w = computeClusters(vectors, 3, 10);
  vectorColors.push(color(255, 0, 0), color(0, 255, 0), color(0, 0, 255));
}

function draw() {
  background(165, 195, 239);
  translate(width / 2, height / 2);
  scale(1, -1);
  push();
  strokeWeight(0.5);
  stroke(125);
  line(-width / 2, 0, width / 2, 0);
  line(0, -height / 2, 0, height / 2);
  pop();
  for (var i = 0; i < points.length; i++) {
    points[i].show();
  }
  push();
  for (let j = 0; j < w.length; j++) {
    drawVector(w[j], vectorColors[j]);
  }
  pop();
}

table {
  float: right;
  width: 40%;
}

td {
  border: 1px solid black;
  font-family: monospace;
  text-align: center;
  white-space: pre;
  width: 50%;
}

[id^=vector1] {
  background-color: pink;
}

[id^=vector2] {
  background-color: lightgreen;
}

[id^=vector3] {
  background-color: lightblue;
}

<script src="https://cdn.jsdelivr.net/npm/p5@1.4.0/lib/p5.min.js"></script>
<table>
  <thead>
    <tr>
      <th>x</th>
      <th>y</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td id="vector1x"></td>
      <td id="vector1y"></td>
    </tr>
    <tr>
      <td id="vector2x"></td>
      <td id="vector2y"></td>
    </tr>
    <tr>
      <td id="vector3x"></td>
      <td id="vector3y"></td>
    </tr>
  </tbody>
</table>

Now, as for adjusting for this, we just need to calculate the weights and be sure that they are at least |1| for both x and y properties. This requires separating out the step of setting the length then negating randomly.

    // Using width/4 and height/4 since the total span is width/2 and height/2
    let vx = random(width / 4) + 1;
    let vy = random(height / 4) + 1;

    // Randomly negate the x- and y-value
    vx = random() < 0.5 ? vx * -1 : vx;
    vy = random() < 0.5 ? vy * -1 : vy;
    v = createVector(vx, vy);

It's up to you if you wanted to implement this part, but the following code is an example of guaranteeing minimum |1| for each property:

let off = 20; // offset to not touch boundary

// added for clean output details
function output(obj) {
  let [w1, w2, w3] = obj;
  vector1x.textContent = String(w1.x.toPrecision(4));
  vector1y.textContent = String(w1.y.toPrecision(4));
  vector2x.textContent = String(w2.x.toPrecision(4));
  vector2y.textContent = String(w2.y.toPrecision(4));
  vector3x.textContent = String(w3.x.toPrecision(4));
  vector3y.textContent = String(w3.y.toPrecision(4));
}

class Point {
  constructor() {
    this.x = random(-width / 2 + off, width / 2 - off);
    this.y = random(-height / 2 + off, height / 2 - off);
  }
  show() {
    stroke(239, 12, 12);
    strokeWeight(4);
    point(this.x, this.y);
  }
}

// function for initializing random weight vectors
function setWeights(l) {
  let weights = [];
  let v;
  for (let i = 0; i < l; i++) {
    // Using width/4 and height/4 since the total span is width/2 and height/2
    let vx = random(width / 4) + 1;
    let vy = random(height / 4) + 1;
    vx = random() < 0.5 ? vx * -1 : vx;
    vy = random() < 0.5 ? vy * -1 : vy;
    v = createVector(vx, vy);
    weights.push(v);
  }
  return weights;
}

// k = # of weight vectors, N = # of learningsessions
function computeClusters(inpts, k, N) {
  let w = setWeights(k);
  let erg, dotprods, ind, e, m, maxIndex;
  for (let j = 0; j < N; j++) {
    dotprods = [];
    ind = floor(random(0, inpts.length));
    e = inpts[ind];
    for (let i = 0; i < w.length; i++) {
      dotprods.push(e.dot(w[i]));
    }
    m = max(dotprods);
    maxIndex = 0;
    for (let i = 0; i < dotprods.length; i++) {
      if (dotprods[i] == m) {
        maxIndex = i;
      }
    }
    erg = e.add(w[maxIndex]);
    w[maxIndex] = erg.mult(100 / erg.mag());
  }
  output(w);
  return w;
}

// function for displaying vector in an "appropriate" way
function drawVector(vec, mycolor) {
  let arrowSize = vec.mag() / 10;
  push();
  stroke(mycolor);
  strokeWeight(1.5);
  fill(mycolor);
  line(0, 0, vec.x, vec.y);
  rotate(vec.heading());
  translate(vec.mag() - arrowSize, 0);
  triangle(0, arrowSize / 4, 0, -arrowSize / 4, arrowSize, 0);
  pop();
}

let points = [];
let vectors = [];
let w = [];

function setup() {
  createCanvas(400, 400);
  for (let i = 0; i < 10; i++) {
    let p = new Point();
    points.push(p);
    vectors.push(createVector(p.x, p.y));
  }
  w = computeClusters(vectors, 3, 10);
}

function draw() {
  background(165, 195, 239);
  translate(width / 2, height / 2);
  scale(1, -1);
  push();
  strokeWeight(0.5);
  stroke(125);
  line(-width / 2, 0, width / 2, 0);
  line(0, -height / 2, 0, height / 2);
  pop();
  for (var i = 0; i < points.length; i++) {
    points[i].show();
  }
  push();
  for (let j = 0; j < w.length; j++) {
    drawVector(w[j], color(50, 175, 150));
  }
  pop();
}

table {
  float: right;
  width: 40%;
}

td {
  border: 1px solid black;
  font-family: monospace;
  text-align: center;
  white-space: pre;
  width: 50%;
}

<script src="https://cdn.jsdelivr.net/npm/p5@1.4.0/lib/p5.min.js"></script>
<table>
  <thead>
    <tr>
      <th>x</th>
      <th>y</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td id="vector1x"></td>
      <td id="vector1y"></td>
    </tr>
    <tr>
      <td id="vector2x"></td>
      <td id="vector2y"></td>
    </tr>
    <tr>
      <td id="vector3x"></td>
      <td id="vector3y"></td>
    </tr>
  </tbody>
</table>