Try first

The gradient for weight j sums e * x[j] over every row. Written as matrices, with X being 10 by 4 and the errors being 10 numbers, what shape is that sum and how do you get it in one operation?

Work out the shapes before reading on. The answer is forced by them.

The whole model in three lines

function predictAll(X, w, b) {
  return flatten(matmul(X, colVector(w))).map(v => v + b);
}

function lossAll(X, y, w, b) {
  const p = predictAll(X, w, b);
  let s = 0;
  for (let i = 0; i < y.length; i++) s += (y[i] - p[i]) * (y[i] - p[i]);
  return s / y.length;
}

function gradientAll(X, y, w, b) {
  const p = predictAll(X, w, b);
  const e = y.map((v, i) => v - p[i]);
  const dw = flatten(matmul(transpose(X), colVector(e))).map(v => -2 * v / y.length);
  const db = -2 * e.reduce((s, v) => s + v, 0) / y.length;
  return [dw, db];
}

Follow the shapes through gradientAll, because they are the whole explanation.

X            10 by 4
w as column    4 by 1
X * w         10 by 1     one prediction per house
e             10 numbers  one error per house

X^T            4 by 10
e as column   10 by 1
X^T * e        4 by 1     one gradient per weight

The transpose is there because the sum runs down a column of X. Entry j of X^T * e pairs row j of X^T, which is column j of X, with the errors. That is exactly sum of e * x[j], which is what the derivation in lesson 3063 asked for.

Notice you did not have to think about the loop at all. Once the shapes fit there is only one way to arrange the operation, and it is the right one. That is what people mean when they say matrix notation does the bookkeeping for you.

Check it against the loop version

Never replace working code with faster code without comparing them.

const X = scaled.map(r => r.x);
const y = scaled.map(r => r.y);
const w0 = [1, 2, 3, 4], b0 = 5;

const [dwLoop, dbLoop] = gradient(w0, b0, scaled);
const [dwMat,  dbMat ] = gradientAll(X, y, w0, b0);

log("loop  ", dwLoop.map(v => v.toFixed(6)).join(" "), dbLoop.toFixed(6));
log("matrix", dwMat.map(v => v.toFixed(6)).join(" "), dbMat.toFixed(6));

Identical to six decimal places. Same arithmetic, arranged differently.

Training with it

function trainAll(X, y, lr = 0.1, steps = 20000) {
  let w = X[0].map(() => 0), b = 0;
  for (let i = 0; i < steps; i++) {
    const [dw, db] = gradientAll(X, y, w, b);
    w = w.map((v, j) => v - lr * dw[j]);
    b -= lr * db;
  }
  return [w, b];
}

Still the update rule from lesson 3056. It has not changed since the two parameter version and it will not change again.

What vectorizing does and does not buy you

Be honest about this. In our matmul, written in plain JavaScript with three loops, the vectorized version is not meaningfully faster. It does the same multiplications in the same language.

The win comes when matmul is not your code. Hand these same operations to a library backed by tuned native code, or to a GPU, and one matrix multiply runs hundreds of times faster than the equivalent loop. Expressing the model as a few large matrix operations is what makes that substitution possible.

So the real benefit here is the shape of the code, not its speed. The speed arrives later, for free, because the shape was right.

What to watch

The bias is added to every entry after the multiply, which is a different kind of operation. Libraries call this broadcasting and do it silently, which is convenient until a shape is wrong and it broadcasts something you did not intend rather than raising an error.

Exercises

  1. Add a shape check at the top of predictAll comparing the columns of X to the length of w.
  2. Fold the bias into the weights by adding a column of ones to X. Confirm you get the same answer with one less special case.
  3. Time trainAll against the loop version for 20000 steps. Which wins, and does the answer surprise you?
  4. Rewrite lossAll using dotProduct on the error vector with itself.
PreviousNext