[smokel]

> single bit neural networks are decision trees.

I didn't exactly understood what was meant here, so I went out and read a little. There is an interesting paper called "Neural Networks are Decision Trees" [1]. Thing is, this does not imply a nice mapping of neural networks onto decision trees. The trees that correspond to the neural networks are huge. And I get the idea that the paper is stretching the concept of decision trees a bit.

Also, I still don't know exactly what you mean, so would you care to elaborate a bit? :)

[1] https://arxiv.org/pdf/2210.05189

[lioeters]

Closest thing I found was:

Single Bit Neural Nets Did Not Work - https://fpga.mit.edu/videos/2023/team04/report.pdf

> We originally planned to make and train a neural network with single bit activations, weights, and gradients, but unfortunately the neural network did not train very well. We were left with a peculiar looking CPU that we tried adapting to mine bitcoin and run Brainfuck.

[fooker]

> I still don't know exactly what you mean

Straight forward quantization, just to one bit instead of 8 or 16 or 32. Training a one bit neural network from scratch is apparently an unsolved problem though.

> The trees that correspond to the neural networks are huge.

Yes, if the task is inherently 'fuzzy'. Many neural networks are effectively large decision trees in disguise and those are the ones which have potential with this kind of approach.

[cubefox]

> Training a one bit neural network from scratch is apparently an unsolved problem though.

It was until recently, but there is a new method which trains them directly without any floating point math, using "Boolean variation" instead of Newton/Leibniz differentiation:

https://proceedings.neurips.cc/paper_files/paper/2024/hash/7...

[fooker]

Nice!

[cubefox]

Unfortunately the paper seems to have been mostly overlooked. It has only a few citations. I think one practical issue is that that existing training hardware is optimized for floating point operations.

[imtringued]

>Many neural networks are effectively large decision trees in disguise and those are the ones which have potential with this kind of approach.

I don't see how that is true. Decision trees look at one parameter at a time and potentially split to multiple branches (aka more than 2 branches are possible). Single input -> discrete multi valued output.

Neural networks do the exact opposite. A neural network neuron takes multiple inputs and calculates a weighted sum, which is then fed into an activation function. That activation function produces a scalar value where low values mean inactive and high values mean active. Multiple inputs -> continuous binary output.

Quantization doesn't change anything about this. If you have a 1 bit parameter, that parameter doesn't perform any splitting, it merely decides whether a given parameter is used in the weighted sum or not. The weighted sum would still be performed with 16 bit or 8 bit activations.

I'm honestly tired of these terrible analogies that don't explain anything.

[fooker]

> I'm honestly tired of these terrible analogies that don't explain anything.

Well, step one should be trying to understand something instead of complaining :)

> Single input -> discrete multi valued output.

A single node in a decision tree is single input. The decision tree as a whole is not. Suppose you have a 28x28 image, each 'pixel' being eight bits wide. Your decision tree can query 28x28x8 possible inputs as a whole.

> A neural network neuron takes multiple inputs and calculates a weighted sum, which is then fed into an activation function.

Do not confuse the 'how' with 'what'.

You can train a neural network that, for example, tells you if the 28x28 image is darker at the top or darker at the bottom or has a dark band in the middle.

Can you think of a way to do this with a decision tree with reasonable accuracy?

[fc417fc802]

> Training a one bit neural network from scratch is apparently an unsolved problem though.

I don't think it's correct to call it unsolved. The established methods are much less efficient than those for "regular" neural nets but they do exist.

Also note that the usual approach when going binary is to make the units stochastic. https://en.wikipedia.org/wiki/Boltzmann_machine#Deep_Boltzma...

[fooker]

Interesting.

By unsolved I guess I meant: this looks like it should be easy and efficient but we don't know how to do it yet.

Usually this means we are missing some important science in the classification/complexity of problems. I don't know what it could be.

[fc417fc802]

Perhaps. It's also possible that the approach simply precludes the use of the best tool for the job. Backprop is quite powerful and it just doesn't work in the face of heavy quantization.

Whereas if you're already using evolution strategies or a genetic algorithm or similar then I don't expect changing the bit width (or pretty much anything else) to make any difference to the overall training efficiency (which is presumably already abysmal outside of a few specific domains such as RL applied to a sufficiently ambiguous continuous control problem).