4 ms·

> 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 arti

by cs702 7y ago

> 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 https://news.ycombinator.com/item?id=23118348

j-pb 7y ago
> 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.
- cs702 7y ago
  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=true https://dl.acm.org/doi/pdf/10.1145/3317550.3321441?download=...
- visarga 7y ago
  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.
  - cs702 7y ago
    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=true 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).
woah 7y ago
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.
- cs702 7y ago
  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).
  - woah 7y ago
    Just need to find a way to put together batches of operations that can happen in parallel, right?
gavinray 7y ago
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-backpropagation-example/ 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/app.ts 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?
- cs702 7y ago
  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.)
  - goatlover 7y ago
    Could there be a transpiling step that converts the objects to arrays, targeting PyTorch or TensorFlow?
  - gavinray 7y ago
    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?
amelius 7y ago
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.

by cs702 7y ago

j-pb 7y ago

> 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.

cs702 7y ago
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=true https://dl.acm.org/doi/pdf/10.1145/3317550.3321441?download=...
visarga 7y ago
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.
- cs702 7y ago
  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=true 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).

woah 7y ago

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.

cs702 7y ago
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).
- woah 7y ago
  Just need to find a way to put together batches of operations that can happen in parallel, right?

gavinray 7y ago

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-backpropagation-example/ 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/app.ts 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?

cs702 7y ago
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.)
- goatlover 7y ago
  Could there be a transpiling step that converts the objects to arrays, targeting PyTorch or TensorFlow?
- gavinray 7y ago
  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?

amelius 7y ago

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.