Skip to content
The methodOpen data
Back to the collection

Deep Differentiable Logic Gate Networks

Felix Petersen, Christian Borgelt, Hilde Kuehne, Oliver Deussen

2022 · arXiv

Machine learning
Read the paper
HN score
0
Mentions
7
Readers
7
Months
5
What’s in a score?

From the abstract

Recently, research has increasingly focused on developing efficient neural network architectures. In this work, we explore logic gate networks for machine learning tasks by learning combinations of logic gates. These networks comprise logic gates such as "AND" and "XOR", which allow for very fast execution. The difficulty in learning logic gate networks is that they are conventionally non-differentiable and therefore do not allow training with gradient descent. Thus, to allow for effective training, we propose differentiable logic gate networks, an architecture that combines real-valued logics and a continuously parameterized relaxation of the network. The resulting discretized logic gate networks achieve fast inference speeds, e.g., beyond a million images of MNIST per second on a single CPU core.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

7 selected excerpts · 7 total mentions

thesz
Neutral mention · rule
SparseCores appear to be block-sparse as opposed to element-sparse. They use 8- and 16-wide vectors to compute. Here's another inference-efficient architecture where TPUs are useless: https://arxiv.org/pdf/2210.08277 There is no matrix-vector multiplication. Parameters are estimated using Gumbel-Softmax. TPUs are of no use here. Inference is done bit-wise and most efficient inference is done after application of boolean logic simplification algorithms (ABC or mockturtle). In my (not so) humble opinion, TPUs are example case of premature optimization.
Original comment TPUs vs. GPUs and why Google is positioned to win AI race in the long term
calebh
Neutral mention · rule
Yes, you can relax logic gates into continuous versions which makes the system differentiable. An AND gate can be constructed with the function x*y and NOT by 1-x (on inputs in the range [0,1]. From there you can construct a NAND gate, which is universal and can be used to construct all other gates. Sigmoid can be used to squash the inputs into [0,1] if necessary. This paper lists out all 16 possible logic gates in Table 1 if you're interested in this sort of thing: https://arxiv.org/abs/2210.08277
Original comment Weight-sparse transformers have interpretable circuits [pdf]
andy12_
Neutral mention · rule
I also worked a long time ago in recreating the original Deep Differentiable Logic Network paper [1], so I have a couple of additions to make. > I wanted to see if I could learn the wires in addition to the gates. I still think it’s possible, but it’s something I had to abandon to get the model to converge. Actually, I read some other paper where they also learned the wiring, but they did so by alternating the training of the gates and the wires (in some iterations they learned the wiring while keeping the gates frozen, and in other they learned the gates while keeping the wiring frozen). The problem with this approach is that it is inherently non-escalable: you need a…
Read the full comment
lot of gates to approximate the behavior of a simple MLP, and if you need a full NxM learned matrix to encode the wiring, the memory needed to learn, for example, MNIST, gets huge, quickly. I think that for this there are 2 fixes: - You actually don't need to learn a full NxM matrix to increase the expressivity of the network. You can, for each output gate, select a random subset of possible input gates of size K, and then you only need a learned matrix of size KxM. I did the numbers, and even a moderately small K, like 16 or 32, wildly increases the number of circuits you can learn with a smaller number of layers and gates. - You could use a LoRA kind of matrix. Instead of a matrix NxM, use a pair of matrices NxK and KxM, where K<<N,M. Learning the wiring also has other benefits. As the output gate can learn to swap the inputs if needed, you can remove some learnable gates that are "mirrors" or "permutations" of each other (a and not b, not a and b; a or not b, not a or b), which can help scale the networks to use gates of more inputs (I tried with 3-input gates and 4-input gates). Also, as the author pointed out, it was very difficult to get the models to converge. It was very frustrating that I never managed to get a working model that performed really well on MNIST. In the end, I gave up on that and I worked on how to make the network consistently learn simple 3-input or 4-input functions with perfect accuracy, and I managed to make it learn them consistently with a couple dozen iterations, which was nice. [1] https://arxiv.org/abs/2210.08277
Original comment Compiling a neural net to C for a speedup
enricozb
Neutral mention · rule
Differentiable Logic Gate Networks [0] are super interesting. However, I still don't like that the wiring is fixed initially rather than learned. I did some extremely rough research into doing learnable wirings [1], but couldn't get past even learning ~4-bit addition. [0]: https://arxiv.org/abs/2210.08277 [1]: https://ezb.io/thoughts/program_synthesis/boolean_circuits/2...
Original comment Compiling a neural net to C for a speedup
gwern
Neutral mention · rule
The original cited paper https://arxiv.org/abs/2210.08277 "Deep Differentiable Logic Gate Networks" struck me then as very clever, ultra-efficient/small, hardly any inductive bias or prior... But you have to wonder if it's able to scale reasonably well. Differentiating continuous versions of 16 discrete operations in parallel sounds expensive, especially since you presumably need a bunch of them chained in order to approximate a single neural primitive. Even distilling an existing LLM down might be too hard.
Original comment GSoC'24: Differentiable Logic for Interactive Systems and Generative Music
dpflan
Neutral mention · rule
If you're into logic gates and deep learning: - Deep Differentiable Logic Gate Networks (https://arxiv.org/pdf/2210.08277.pdf) - Video presentation: Deep Differentiable Logic Gate Networks (https://www.youtube.com/watch?v=VulM891DhI4)
Original comment Logic Gate Simulator

Keep following the thread.

More in Machine learning

More from the same topics.