Hacker News Reader

Comment by brilee | Hacker News Reader

This technique figures out how to find a subset of neural network edge weights that can replicate most of the full model's performance, and is indeed quite simple. The catch is that this sparse subset of NN edge weights has no structure, so it doesn't get efficient execution on a GPU. If you're on a CPU with no specialized matrix math, this does in fact cut down on execution costs, but if you have an embedded ML chip, this doesn't really help.

Distillation is another shrinkage technique that is also pretty foolproof, but allows you to pick an arbitrary architecture - this way, you can make full use of whatever hardware you're deploying too.

View on HN

> The catch is that this sparse subset of NN edge weights has no structure, so it doesn't get efficient execution...

I would love to be able to model each artificial neuron as a separate object in code, making it trivial to group/ungroup neurons into irregularly shaped and/or overlapping groups and easily shrink/expand/alter such groups on the fly without incurring a performance penalty. Easy pruning would be just one application.

As you point out, right now, those things not practical with frameworks like PyTorch and TensorFlow if we want decent performance. Currently we have little choice but to pigeonhole all our designs explicitly into layers that operate on grid-like structures of fixed size and resort to things like masking so we can have fast multiply-sum operations.

By coincidence I was just talking about this on an unrelated thread: https://news.ycombinator.com/item?id=23118348

> separate object in code

I hope you don't mean object in the OOP sense, but in a more general way, because that would be the slowest thing ever, no matter how smart your compiler/framework.

You'd probably be better off to just have each group as a copy of the original one.

> not practical with frameworks like PyTorch and TensorFlow

The problem is not the frameworks, the problem is hardware, and physics.

We've hit the wall with clock speeds, we've hit the wall with pipeline depth, we've hit the wall with branch prediction.

The only thing we have left is specialised hardware, parallel hardware, and bigger caches. But all of these only work with SIMD, because it makes data fetches predictable, it makes the cores simpler and it makes adding more compute cheaper (no separate fetch decode silicon required).

For the memory hierarchy to work you want stuff packed like in ECS systems for games, or Matrices for ML.

Even with specialised hardware, changing your neural architecture on the fly would be ridiculously expensive because of all the communication overhead.

The problem is more complex than "just" hardware. If I may paraphrase a recent paper out of Google Brain: the current systems (hardware and software) we use for for numerical computing are "stuck in a local basin of performance and programmability."[a]

[a] https://dl.acm.org/doi/pdf/10.1145/3317550.3321441?download=...

Using a sparse adjacency matrix in combination with regular matrix operations solves the problem of fitting any graph topology into matrices (used in graph neural nets). You can put multiple graphs together in the same adjacency matrix and batch them up for efficient computation.

You would think so, but the problem is more complex than it appears to be: https://dl.acm.org/doi/pdf/10.1145/3317550.3321441?download=...

There's a big "impedance mismatch" between (1) "programmability" (by which I mean, being able to write high-level code that under-the-hood requires dynamic modification, reshaping, and/or combination-optimization of those adjacency matrices you mention, without worrying about performance) and (2) existing infrastructure (frameworks that rely on highly optimized computation "kernels" that cleverly exploit the memory layout and other features of accelerated hardware, i.e., GPUs/TPUs).

I have thought about that as well. I think it should be pretty straightforward. You need an algorithm that can divide your graph (weights and activations) into batches where no member of a batch depends on values that have not yet been calculated. I think, but am not sure, that this will result in alternating batches of weights and activations.

Then you can calculate the results of applying the weights in the first batch to every example in a minibatch in parallel. Then you move on to calculate the results of applying the activations in the second batch to the results of the first batch, and so on until you have finished all the batches.

The hard part is making the batches, although it feels like the kind of classical algorithms 101 problem that has some great solutions out there already. Maybe it is an application of graph coloring or something.

I have not really pursued this because I'm not sure if there is a benefit to breaking the neurons out of their orderly layers. It would be interesting to just try training a few randomly generated networks, but I haven't had the time so far.

Email me at hi at jehan dot email if you want to talk about this.

I'm not so sure.

Say we want to build a CNN that accepts batches of images of different size without having to resize and/or pad them to the same size. Or say we want to build a convolutional layer in which kernels need not be rectangular and of the same shape and size but can be of different shapes and sizes (e.g., circular kernels that vary in size as we move away from the center of attention). Or say we want to remove connections with low weights (as proposed in this paper) and randomly add new connections between arbitrary individual neurons in different layers between backprop updates.

These are just a few examples off the top of my head of things that in principle would be easy to code in any modern high-level language (e.g., Python, Swift) but look very hard to get to run efficiently using today's software + hardware infrastructure (PyTorch/TensorFlow + GPUs/TPUs).

Just need to find a way to put together batches of operations that can happen in parallel, right?

No. Unfortunately, the problem is more complex than that: https://dl.acm.org/doi/pdf/10.1145/3317550.3321441?download=...

I’m not super familiar with the technique, but something like NEAT or hyperNEAT might be wgat you are looking for?

Why can't you model each neuron as an individual object with a unique UID in code?

I am fortunate enough to have a friend that's fairly accomplished in ML and a really nice guy. He spent a video chat + code session with me where he helped me build an NN from scratch in Typescript, we replicated the network in the paper here:

https://mattmazur.com/2015/03/17/a-step-by-step-backpropagat...

Here's the Codesandbox link, if you notice the console output it (approximately) matches the figures from the paper above:

https://codesandbox.io/s/node-typescript-vqszi?file=/example...

I don't really understand much about ML or neural networks, but from a code perspective, if you have these data structures:

    class Neuron {
      id: number | void = neuronUidGen.next().value;
      incoming: Connection[];
      outgoing: Connection[];
      rate: number;
      bias: number;
      output: number;
      error: number;
    }

    class Connection {
      id: number | void = connectionUidGen.next().value;
      from: Neuron;
      to: Neuron;
      weight: number;
   }

Why couldn't you manipulate these however you see fit? There's a Layer implementation in there that's commented out because it doesn't function right that could roughly accomplish something like this theoretically, right?

You could. But that's not the hard part. The hard part, for the foreseeable future, is that if you write your code like that, you will find it very difficult to get decent performance out of existing frameworks (PyTorch/TensorFlow) and accelerated hardware (GPUs/TPUs) which operate on neurons arranged as arrays of the same shape. (Oversimplifying a bit.)

Could there be a transpiling step that converts the objects to arrays, targeting PyTorch or TensorFlow?

But the Neuron and Connections are just metadata objects like pointers that hold arrays, I don't understand.

Surely in PyTorch/TF, the ND-Arrays of NN's must also be associated to an object reference?

> existing frameworks (PyTorch/TensorFlow) and accelerated hardware (GPUs/TPUs) which operate on neurons arranged as arrays of the same shape.

    const dot = (inputs: number[], weights: number[]) => {
      let total = 0;
      const length = Math.min(inputs.length, weights.length);
      for (let i = 0; i < length; i++) {
        total += inputs[i] * weights[i];
      }
      return total;
    };

  activate(input?: number): number {
    if (!this.incoming.length) {
      this.output = input;
    } else {
      const inputs = this.incoming.map(connection => connection.from.output)
      const weights = this.incoming.map(connection => connection.weight);
      this.output = squash(dot(inputs, weights) + this.bias);
    }
    return this.output;
  }

This is on principle the same concept right?

Unfortunately, the problem is more complex than that: https://dl.acm.org/doi/pdf/10.1145/3317550.3321441?download=... (I oversimplified things in my comment above).

You first need to demonstrate that the path you wish to take is promising, e.g. by running simulations that take weeks but give better results than our current results which are fast.

Only then would it make sense to consider a different computational approach.

I'm just speculating (and haven't read the paper yet), but it may be possible to achieve similar speedups on GPUs by pruning the smallest 20% of blocks of size ≥K×K to produce block-sparse weights[0], rather than pruning the smallest 20% of weights.

[0] https://openai.com/blog/block-sparse-gpu-kernels/

A month or so ago a paper about a deep learning model using a cpu beating the best (4000$ or so) nvidia gpu was on hn, the trick was a quick hashing technique similar to nearest neighbour, so the algorithm keep only the most active neurons. I think the gpu price was about 4000$ and the computer was 60% of that based on some ball park estimates from the comments in HN.

Edited: This is the paper:https://news.ycombinator.com/item?id=22502131

Perhaps both techniques can be used together, since the paper take advantage of sparcity to beat gpu when computation are on a sparse subset.

Does a GPU run a pruned network slower than unpruned, or just not as faster as the modern shrinkages would suggest?

A naive GPU implementation on a non-block sparse network will be just as slow as the full un-pruned network.

Another approach would be to lower precision. By going from 32bits to 16 or 8 you can get massive speedups in memory operations and computation.

Yes, that'll work. But it's orthogonal to this paper.

The trick is to combine these 2 approaches. Quantizing to bytes helps a lot, but forces you to use much larger pruning group size to see any speed up from pruning.

Nvidia's apex.amp does just this - attempts half-precision training where possible, and adjusts scaling factors during training. I achieved a very significant speedup using this on my RTX 2080 Super, though it doesn't support Windows that well.

> The catch is that this sparse subset of NN edge weights has no structure, so it doesn't get efficient execution

I you parallelize your computation along the training data dimension, the problem is embarrassingly parallel and the structure of your neural network does not matter on bit.

Having seen a bunch of people fail to make distillation work in the sense of training a better model than by training the smaller model from scratch, I don't think it's really fool proof...

> The catch is that this sparse subset of NN edge weights has no structure, so it doesn't get efficient execution on a GPU

Could you elaborate a little on this aspect?

I could be off-base here, but I think they’re saying that a sparse matrix (for holding the edge weights) is ultimately something like a list-of-lists format, rather than a dense n x m array (for which GPUs have optimized routines). Except I that there are libraries doing sparse matrix operations on GPU (https://developer.nvidia.com/cusparse).

How optimized are current neural networks to specific GPU architectures?

Reply on news.ycombinator.com