14 ms·

Reverse engineering a neural network's clever solution to binary addition

562 points by Ameo 4y ago

dejongh 4y ago
Interesting idea to reverse engineer the network. Are there other sources that have done this?
- SonOfLilit 4y ago
  The field of NN explainability tries, but usually there's only handwavy things to be done (because too many weights). This project involved intentionally building very very small networks that can be understood completely.
- nerdponx 4y ago
  Maybe not exactly what you had in mind, but is a lot of literature in general on trying to extract interpretations from neural network models, and to a lesser extent from other complicated nonlinear models like gradient boosted trees. Somewhat famously, you can plot the weight activations on a heatmap from a CNN for image processing and obtain a visual representation of the "filter" that the model has learned, which the model (conceptually) slides across the image until it matches something. For example: https://towardsdatascience.com/convolutional-neural-network-feature-map-and-filter-visualization-f75012a5a49c https://towardsdatascience.com/convolutional-neural-network-... Many techniques don't look directly at the numbers in the model. Instead, they construct inputs to the model that attempt to trace out its behavior under various constraints. Examples include Partial Dependence, LIME, and SHAP. Also, those "deep dream" images that were popular a couple years ago are generated by running parts of a deep NN model without running the whole thing.
  - zozbot234 4y ago
    Yes, more generally this entails looking at the numbers learned by a model not as singular "weights" (which doesn't scale as the model gets larger) but more as a way of approximating a non-parametric representation (i.e. something function-like or perhaps even more general). There's a well-established field of variously "explainable" semi-parametric and non-parametric modeling and statistics, which aims to seamlessly scale to large volumes of data and modeling complexity much like NN's do.
greenbit 4y ago
That's awesome - the network's solution is essentially to convert the input to analog, perform the actual addition in analog, and then convert that back to digital. And the first two parts of that all happened in the input weights, no less.
- agapron1 4y ago
  An 8 bit adder is too small and allows such 'hack'. He should try training a 32 or 64 bit adder, decrease the weights accuracy to bfloat16, introduce dropout regularization (or other kind of noise) to get more 'interesting' results. Addendum: another interesting variation to try is a small transformer network, and feeding the bits sequentially as symbols. This kind of architecture could compute bignum-sized integers.
  - nine_k 4y ago
    A sequential one-bit adder, like in pocket calculators or earliest computers with delay-line memory, could likely be invented in the process.
  - Jensson 4y ago
    Yeah, the current solution is similar to overfitting, this wont generalize to harder math where the operation doesn't correspond to the activation function of the network.
    - rileymat2 4y ago
      Is this true? If it can add, it can probably subtract? If it can add and subtract it may be able to multiply (repeated addition) and divide? If it can multiply it can do exponents? I don’t know, but cannot jump to your conclusion without much more domain knowledge.
      - eru 4y ago
        > If it can add and subtract it may be able to multiply (repeated addition) and divide? If it can multiply it can do exponents? It was just a simple feed-forward network. It can't do arbitrary amounts of repeated addition (nor repeat any other operation arbitrarily often).
agapon 4y ago
Very interesting. But I missed how the network handled the overflow. Spotted one small typo: digital to audio converter should be digital to analog.
- SonOfLilit 4y ago
  Do you know how DAC/ADC circuits work? Build one that can handle one more bit of input than you have and you have overflow handling.
- Ameo 4y ago
  Oh nice catch on the typo - thanks!!
- sebzim4500 4y ago
  It converted the inputs to analog so there isn't really a notion of 'overflow'.
  - ilyt 4y ago
    Of course it is, there is whole business around overflowing analog signals in right way in analog guitar effects pedal
  - krisoft 4y ago
    Putting aside the idea that "analog" doesn't have overflow. (Any physical implementation of that analog signal would have limits in the real world. If nothing else, then how much current or voltage your PSU can supply, or how much current can go through your wire.) But that is not even the real issue. The real issue that it is not analog, it is just "analog" with quotes. The neural network is executed by a digital computer, on digital hardware. So that "analog" is just the underlying float type of the of the CPU or GPU executing the network. That is still very much digital. Just on a different abstraction level.
    - allisdust 4y ago
      Are there any true analog adder circuits? If so are they also less error prone like digital.
juunge 4y ago
Awesome reverse engineering project. Next up: reverse engineer a NN's solution to Fourier Transform!
- mananaysiempre 4y ago
  The Fourier transform is also linear, so the same solution should work. No clue if an NN would find it though.
  - perihelions 4y ago
    What's an analog implementation of a Fourier transform look like? It sounds interesting!
    - bradrn 4y ago
      It looks like Albert Michelson's Harmonic Analyzer: see https://engineerguy.com/fourier/ https://engineerguy.com/fourier/ (and don’t miss the accompanying video series! It’s pretty cool.)
    - mananaysiempre 4y ago
      Depends on what kind of “analog” you want. In an NN context, given that you already have “transform with a matrix” as a primitive, probably something very much like sticking a https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix somewhere. (You are already extremely familliar with the 2-input DFT, for example: it’s the (x, y) ↦ (x+y, x−y) map.) If you want a physical implementation of a Fourier transform, it gets a little more fun. A sibling comment already mentioned one possibility. Another is that far-field (i.e. long-distance; “Fraunhofer”) diffraction of coherent light on a semi-transparent planar screen gives you the Fourier transform of the transmissivity (i.e. transparency) of that screen[1]. That’s extremely neat and covers all textbook examples of diffraction (e.g. a finite-width slit gives a sinc for the usual reasons), but probably impractical to mention in an introductory course because the derivation is to get a gnarly general formula then apply the far-field approximation to it. A related application is any time the “reciprocal lattice” is mentioned in solid-state physics; e.g. in X-ray crystallography, what you see on the CRT screen in the simplest case once the X-rays have passed through the sample is the (continuous) Fourier transform of (a bunch of Dirac deltas stuck at each center of) its crystal lattice[2], and that’s because it’s basically the same thing as the Fraunhofer diffraction in the previous paragraph. Of course, the mammalian inner ear is also a spectral analyzer[3]. [1] https://en.wikipedia.org/wiki/Fourier_optics#The_far_field_approximation https://en.wikipedia.org/wiki/Fourier_optics#The_far_field_a... [2] https://en.wikipedia.org/wiki/Laue_equations https://en.wikipedia.org/wiki/Laue_equations [3] https://en.wikipedia.org/wiki/Basilar_membrane#Frequency_dispersion https://en.wikipedia.org/wiki/Basilar_membrane#Frequency_dis...
nerdponx 4y ago
I liked this article a lot, but > One thought that occurred to me after this investigation was the premise that the immense bleeding-edge models of today with billions of parameters might be able to be built using orders of magnitude fewer network resources by using more efficient or custom-designed architectures. Transformer units themselves are already specialized things. Wikipedia says that GPT-3 is a standard transformer network, so I'm sure there is additional room for specialization. But that's not a new idea either, and it's often the case that a after a model is released, smaller versions tend to follow.
- sebzim4500 4y ago
  Transformers are specialized to run on our hardware, whereas the article is suggesting architectures which are specialized for a specific task.
  - nerdponx 4y ago
    Are transformers not already very specialized to the task of learning from sequences of word vectors? I'm sure there is more that can be done with them other than making the input sequences really long, but my point was that LLMs are hardly lacking in design specialized to their purpose.
    - sebzim4500 4y ago
      > Are transformers not already very specialized to the task of learning from sequences of word vectors? No, you can use transformers for vision, image generation, audio generation/recognition, etc. They are 'specialized' in that they are for working with sequences of data, but almost everything can be nicely encoded as a sequence. In order to input images, for example, you typically split the image into blocks and then use a CNN to produce a token for each block. Then you concatenate the tokens and feed them into a transformer.
      - nerdponx 4y ago
        That's fair, and I didn't realize people were using them for images that way. I would still argue that they are at least somewhat more specialized than plain fully-connected layers, much like convolutional layers. It is definitely interesting that we can do so much with a relatively small number of generic "primitive" components in these big models. but I suppose that's part of the point.
aargh_aargh 4y ago
The essay linked from the article is interesting: http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html
- version_five 4y ago
  Yes I just read it too. It appears to have been discussed here multiple times: https://hn.algolia.com/?q=bitter+lesson https://hn.algolia.com/?q=bitter+lesson I'd say it has aged well and there are probably lots of new takes on it based on some of the achievements of the last 6 months. At the same time, I don't agree with it. To simplify, the opposite of "don't over-optimize" isn't "it's too complicated to understand so never try". It is thought provoking though
- sva_ 4y ago
  I think there is no doubt that there must be more efficient model architectures out there, take for example the sample efficiency of GPT-3: > If you think about what a human, a human probably in a human’s lifetime, 70 years, processes probably about a half a billion words, maybe a billion, let’s say a billion. So when you think about it, GPT-3 has been trained on 57 billion times the number of words that a human in his or her lifetime will ever perceive.[0] 0. https://hai.stanford.edu/news/gpt-3-intelligent-directors-conversation-oren-etzioni https://hai.stanford.edu/news/gpt-3-intelligent-directors-co...
  - lostmsu 4y ago
    Humans are not trianed on words.
    - lgas 4y ago
      What do you mean? That we are not trained ONLY on words? Or that the training we receive on words is not the same as the training of a NN? Or something else?
      - lostmsu 4y ago
YesThatTom2 4y ago
Is this going to change how 8-but adders are implemented in chips?
- GTP 4y ago
  No, there was a time where we had analog calculators but there are good reasons why digital electronics won in the computing space.
hoseja 4y ago
Reminded me of the 0xFFFF0000 0xFF00FF00 0xF0F0F0F0 0xCCCCCCCC 0XAAAAAAAA trick, the use of which I don't currently recall... edit: several, but probably not very relevant https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
dagss 4y ago
Impressive. Am I right that what is really going on here is that the network is implementing the "+" operator by actually having the CPU of the host carrying out the "+" when executing the network? I.e., the network converts the binary input and output to floating point, and then it is the CPU of the host the network is running on that really does the addition in floating point. So usually one does a bunch of FLOPs to get "emerging" behaviour that isn't doing arithmetic. But in this case, instead the network does a bunch of transforms in and out so that in a critical point, the addition executed in the network runner is used for exactly its original purpose: Addition. And I guess saying it is "analog" is a good analogy for this..
- Filligree 4y ago
  That's an accurate enough description of what's going on here, yeah, but I'm very curious if this could be implemented in hardware. What we've got is an inexact not-quite-binary adder, but one that's potentially smaller and faster than the regular binary ones.
  - garganzol 4y ago
    It can be implemented in hardware but the implementation would be more complex than a digital adder based on logical gates.
    - em3rgent0rdr 4y ago
      Analog addition is actually really easy if you can tolerate noise and heat and can convert to/from representing the signal as an analog current. Using Kirchhoff's Current Law, addition of N currents from current sources is achieved by joining those N wires to a shared exit wire which contains the summed current.
      - garganzol 4y ago
        Addition is easy, DAC is relatively easy, but ADC is not.
  - 4y ago
jccalhoun 4y ago
These stories remind me of a story from Discover Magazine https://www.discovermagazine.com/technology/evolving-a-conscious-machine https://www.discovermagazine.com/technology/evolving-a-consc... A researcher was using a process to "evolve" a FPGA and the result was a circuit that was super efficient but worked in ways that were unexpected: part of the circuit seemed unconnected to the rest but if removed the whole thing stopped working and it would only work at a specific temperature.
- qikInNdOutReply 4y ago
  Ah, the good old radio component you can program into fpgas.
  - pjc50 4y ago
    Very easy to design a radio component into electronics, much harder to design it out.
    - nkrisc 4y ago
      I’ve had all kinds of cheap electronics that came with unadvertised radio features for free.
      - TeMPOraL 4y ago
        It's sad that those pesky regulators from the FCC make it so hard to get devices with unintended radio functionality these days!
        gumby 4y ago
        I know, if people really cared about devices rejecting interference the free market would sort that out, amirite?
        WalterBright 4y ago
MontyCarloHall 4y ago
A couple questions: 1. How much of this outcome is due to the unusual (pseudo) periodic activation function? Seems like a lot of the DAC-like behavior is coming from the periodicity of the first layer’s output, which seems to be due to the unique activation function. 2. Would the behavior of the network change if the binary strings were encoded differently? The author encodes them as 1D arrays with 1 corresponding to 1 and 0 corresponding to -1, which is an unusual way of doing things. What if the author encoded them as literal binary arrays (i.e. 1->1, 0->0)? What about one-hot arrays (i.e. 2D arrays with 1->[1, 0] and 0->[0, 1]), which is the most common way to encode categorical data?
- Ameo 4y ago
  I think that the activation function definitely is important for this particular case, but it's not actually periodic; it saturates (with a configurable amount of leakyness) on both ends. The periodic behavior happens due to patterns in individual bits as you count up. As for the encoding, I think it's a pretty normal way to encode binary inputs like this. Having the values be -1 and 1 is pretty common since it makes the data centered at 0 rather than 0.5 which can lead to better training results.
- evrimoztamur 4y ago
  For 1., the author used Ameo (the weird activation function) in the first layer and tanh for others, later on notes: "While playing around with this setup, I tried re-training the network with the activation function for the first layer replaced with sin(x) and it ends up working pretty much the same way. Interestingly, the weights learned in that case are fractions of π rather than 1." By the looks of it, any activation function that maps a positive and negative range should work. Haven't tested that myself. The 1 vs π is likely due to the peaks of the functions, Ameo at 1 and sine at π/2. Regardless, it's not Ameo.
- sebzim4500 4y ago
  1. The author has prior blog posts talking about this activation function, and apparently it does help to learn binary logic tasks. 2. I doubt this matters at all here. For some architectures having inputs be 0 on average is useful, so the author probably just picked it as the default choice.
AstralStorm 4y ago
When you expect your network to learn a binary adder and it learns FFT addition instead. :) (For an ANN FFT is more natural as it's a projection algorithm.)
allisdust 4y ago
totally off topic: Any pointers to tutorials/articles that teach implementation of common neural network models in javascript/rust (from scratch) ?
puttycat 4y ago
Recent work on NNs where applying Kolmogorov complexity optimization leads to a network that solves binary addition with a carry-over counter and 100% provable accuracy: (see Results section) https://arxiv.org/abs/2111.00600 https://arxiv.org/abs/2111.00600
moyix 4y ago
Related: an independent reverse engineering of a network that "grokked" modular addition: https://www.alignmentforum.org/posts/N6WM6hs7RQMKDhYjB/a-mechanistic-interpretability-analysis-of-grokking https://www.alignmentforum.org/posts/N6WM6hs7RQMKDhYjB/a-mec... One interesting thing is that this network similarly does addition using a Fourier transform.
rehevkor5 4y ago
Not too surprising. Each layer can multiply each input by a set of weights, and add them up. That's all you need, in order to convert from base 2 to base 10. In base 2, we calculate the value of a set of digits by multiplying each by 2^0, 2^1, ..., 2^n. Each weight is twice the previous. The activation function is just making it easier to center those factors on zero to reduce the magnitude of the regularization term. I am guessing you could probably get the job done with just two neurons in the first layer, which output the real value of each input, one neuron in the second layer to do the addition (weights 1, 1), and 8 neurons in the final layer to convert back to binary digits.
- tonmoy 4y ago
  While your analysis sounds good, I don’t think you mean base 10, you probably mean a “single float”?
KhoomeiK 4y ago
A more theoretical but increasingly popular approach to identifying behavior like this is interchange intervention: https://ai.stanford.edu/blog/causal-abstraction/ https://ai.stanford.edu/blog/causal-abstraction/
wwarner 4y ago
So important. Here’s a prediction. Work like this on model explainability will continue and eventually will reveal patterns in the input that reliably produce features in the resulting models. That knowledge will tell us about nature, in addition to ML.
kens 4y ago
The trick of performing binary addition by using analog voltages was used in the IAS family of computers (1952), designed by John von Neumann. It implemented a full adder by converting two input bits and a carry in bit into voltages that were summed. Vacuum tubes converted the analog voltage back into bits by using a threshold to generate the carry-out and more complex thresholds to generate the sum-out bit.
- elcritch 4y ago
  Nifty, makes one wonder if logarithmic or sigmoid functions for ML could be done using this method. Especially as we approach the node size limit, perhaps dealing with fuzzy analog will become more valuable.
  - djmips 4y ago
    There are a few startups making analog ML compute. Mythic & Aspinity for example https://www.eetimes.com/aspinity-puts-neural-networks-back-to-analog/ https://www.eetimes.com/aspinity-puts-neural-networks-back-t...
    - shagie 4y ago
      Veritasium has a bit of an video on Mythic - Future Computers Will Be Radically Different (Analog Computing) - https://youtu.be/GVsUOuSjvcg https://youtu.be/GVsUOuSjvcg
      - westurner 4y ago
        From "Faraday and Babbage: Semiconductors and Computing in 1833" https://news.ycombinator.com/item?id=32888210 https://news.ycombinator.com/item?id=32888210 and then "Qubit: Quantum register: Qudits and qutrits" https://news.ycombinator.com/item?id=31983110 https://news.ycombinator.com/item?id=31983110: >>> The following is an incomplete list of physical implementations of qubits, and the choices of basis are by convention only: [...] Qubit#Physical_implementations: https://en.wikipedia.org/wiki/Qubit#Physical_implementations https://en.wikipedia.org/wiki/Qubit#Physical_implementations > - note the "electrons" row of the table According to this Table on wikipedia, it's possible to use electron charge (instead of 'spin') to do Quantum Logic with Qubits. How is that doing quantum logical computations with electron charge different from from what e.g. Cirq or Tequila do (optionally with simulated noise to simulate the Quantum Computer Engineering hardware)? FWIU, analog and digital component qualities are not within sufficient tolerance to do precise analog computation? (Though that's probably debatable for certain applications at least, but not for general purpose computing architectures?) That is, while you can build adders out of voltage potentials quantified more specifically than 0 or 1, you might shouldn't without sufficient component spec tolerances because noise and thus error. IMHO, Turing Tumble and Spintronics are neat analog computer games. (Are Qubits, by Church-Turing-Deutsch, sufficient to; 1) simuluate arbitrary quantum physical systems; or 2) run quantum logical simulations as circuits with low error due to high coherence? https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93... ) >> See also: "Quantum logic gate" https://en.wikipedia.org/wiki/Quantum_logic_gate https://en.wikipedia.org/wiki/Quantum_logic_gate Analog computers > Electronic analog computers aren't Electronic digital computers: https://en.wikipedia.org/wiki/Analog_computer#Electronic_analog_computers_2 https://en.wikipedia.org/wiki/Analog_computer#Electronic_ana...
2bitencryption 4y ago
> One thought that occurred to me after this investigation was the premise that the immense bleeding-edge models of today with billions of parameters might be able to be built using orders of magnitude fewer network resources by using more efficient or custom-designed architectures. I'm pretty convinced that something equivalent to GPT could run on consumer hardware today, and the only reason it doesn't is because OpenAI has a vested interest in selling it as a service. It's the same as Dall-E and Stable Diffusion - Dall-E makes no attempt to run on consumer hardware because it benefits OpenAI to make it so large that you must rely on someone with huge resources (i.e. them) to use it. Then some new research shows that effectively the same thing can be done on a consumer GPU. I'm aware that there's plenty of other GPT-like models available on Huggingface, but (to my knowledge) there is nothing that reaches the same quality that can run on consumer hardware - yet.
WalterBright 4y ago
In a similar vein, in the 1980s a "superoptimizer" was built for optimizing snippets of assembler by doing an exhaustive search of all combinations of instructions. It found several delightful and unexpected optimizations, which quickly became incorporated into compiler code generators.
- convolvatron 4y ago
  you can mention Massalin by name. she's pretty brilliant, idk where she is now
  - WalterBright 4y ago
    I don't recall who wrote the paper, thanks for the tip, enabling me to find the paper: H. Massalin, “Superoptimizer - A Look at the Smallest Program,” ACM SIGARCH Comput. Archit. News, pp. 122–126, 1987. https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf https://web.stanford.edu/class/cs343/resources/superoptimize... The H is for "Henry".
    - mgliwka 4y ago
      It’s Alexia Massalin now: https://en.m.wikipedia.org/wiki/Alexia_Massalin https://en.m.wikipedia.org/wiki/Alexia_Massalin
Lisa_Novak 4y ago
[dead]
GeorgeTirebiter 4y ago
Small nit: the analog DAC circuit has MSB and LSB reversed. That is, the LSB goes into the top 128k resistor. If you think of it one bit at a time, the gain of the circuit = -Rf/R --- where R is one of the resistors in the ladder. (Rf is the feedback resistor, which is unlabeled and un-valued in the article.) Clearly, you get bigger output when R is smaller.
nnurmanov 4y ago
I wonder if is possible to reverse engineer passwords. One can input passwords, train them on known values. What to expect?
etherio 4y ago
Relevant: reverse engineering modular addition https://twitter.com/NeelNanda5/status/1559060507524403200 https://twitter.com/NeelNanda5/status/1559060507524403200
imtringued 4y ago
I don't see how this is surprising. It's cool but come on, you have a network consisting of addition and multiplication and you expect it to not use them? What else is it supposed to do? Memorize every input output pair like a look up table?

562 points by Ameo 4y ago

dejongh 4y ago

Interesting idea to reverse engineer the network. Are there other sources that have done this?

SonOfLilit 4y ago
The field of NN explainability tries, but usually there's only handwavy things to be done (because too many weights). This project involved intentionally building very very small networks that can be understood completely.
nerdponx 4y ago
Maybe not exactly what you had in mind, but is a lot of literature in general on trying to extract interpretations from neural network models, and to a lesser extent from other complicated nonlinear models like gradient boosted trees. Somewhat famously, you can plot the weight activations on a heatmap from a CNN for image processing and obtain a visual representation of the "filter" that the model has learned, which the model (conceptually) slides across the image until it matches something. For example: https://towardsdatascience.com/convolutional-neural-network-feature-map-and-filter-visualization-f75012a5a49c https://towardsdatascience.com/convolutional-neural-network-... Many techniques don't look directly at the numbers in the model. Instead, they construct inputs to the model that attempt to trace out its behavior under various constraints. Examples include Partial Dependence, LIME, and SHAP. Also, those "deep dream" images that were popular a couple years ago are generated by running parts of a deep NN model without running the whole thing.
- zozbot234 4y ago
  Yes, more generally this entails looking at the numbers learned by a model not as singular "weights" (which doesn't scale as the model gets larger) but more as a way of approximating a non-parametric representation (i.e. something function-like or perhaps even more general). There's a well-established field of variously "explainable" semi-parametric and non-parametric modeling and statistics, which aims to seamlessly scale to large volumes of data and modeling complexity much like NN's do.

greenbit 4y ago

That's awesome - the network's solution is essentially to convert the input to analog, perform the actual addition in analog, and then convert that back to digital. And the first two parts of that all happened in the input weights, no less.

agapron1 4y ago
An 8 bit adder is too small and allows such 'hack'. He should try training a 32 or 64 bit adder, decrease the weights accuracy to bfloat16, introduce dropout regularization (or other kind of noise) to get more 'interesting' results. Addendum: another interesting variation to try is a small transformer network, and feeding the bits sequentially as symbols. This kind of architecture could compute bignum-sized integers.
- nine_k 4y ago
  A sequential one-bit adder, like in pocket calculators or earliest computers with delay-line memory, could likely be invented in the process.
- Jensson 4y ago
  Yeah, the current solution is similar to overfitting, this wont generalize to harder math where the operation doesn't correspond to the activation function of the network.
  - rileymat2 4y ago
    Is this true? If it can add, it can probably subtract? If it can add and subtract it may be able to multiply (repeated addition) and divide? If it can multiply it can do exponents? I don’t know, but cannot jump to your conclusion without much more domain knowledge.
    - eru 4y ago
      > If it can add and subtract it may be able to multiply (repeated addition) and divide? If it can multiply it can do exponents? It was just a simple feed-forward network. It can't do arbitrary amounts of repeated addition (nor repeat any other operation arbitrarily often).

agapon 4y ago

Very interesting. But I missed how the network handled the overflow. Spotted one small typo: digital to audio converter should be digital to analog.

SonOfLilit 4y ago
Do you know how DAC/ADC circuits work? Build one that can handle one more bit of input than you have and you have overflow handling.
Ameo 4y ago
Oh nice catch on the typo - thanks!!
sebzim4500 4y ago
It converted the inputs to analog so there isn't really a notion of 'overflow'.
- ilyt 4y ago
  Of course it is, there is whole business around overflowing analog signals in right way in analog guitar effects pedal
- krisoft 4y ago
  Putting aside the idea that "analog" doesn't have overflow. (Any physical implementation of that analog signal would have limits in the real world. If nothing else, then how much current or voltage your PSU can supply, or how much current can go through your wire.) But that is not even the real issue. The real issue that it is not analog, it is just "analog" with quotes. The neural network is executed by a digital computer, on digital hardware. So that "analog" is just the underlying float type of the of the CPU or GPU executing the network. That is still very much digital. Just on a different abstraction level.
  - allisdust 4y ago
    Are there any true analog adder circuits? If so are they also less error prone like digital.

juunge 4y ago

Awesome reverse engineering project. Next up: reverse engineer a NN's solution to Fourier Transform!

mananaysiempre 4y ago
The Fourier transform is also linear, so the same solution should work. No clue if an NN would find it though.
- perihelions 4y ago
  What's an analog implementation of a Fourier transform look like? It sounds interesting!
  - bradrn 4y ago
    It looks like Albert Michelson's Harmonic Analyzer: see https://engineerguy.com/fourier/ https://engineerguy.com/fourier/ (and don’t miss the accompanying video series! It’s pretty cool.)
  - mananaysiempre 4y ago
    Depends on what kind of “analog” you want. In an NN context, given that you already have “transform with a matrix” as a primitive, probably something very much like sticking a https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix somewhere. (You are already extremely familliar with the 2-input DFT, for example: it’s the (x, y) ↦ (x+y, x−y) map.) If you want a physical implementation of a Fourier transform, it gets a little more fun. A sibling comment already mentioned one possibility. Another is that far-field (i.e. long-distance; “Fraunhofer”) diffraction of coherent light on a semi-transparent planar screen gives you the Fourier transform of the transmissivity (i.e. transparency) of that screen[1]. That’s extremely neat and covers all textbook examples of diffraction (e.g. a finite-width slit gives a sinc for the usual reasons), but probably impractical to mention in an introductory course because the derivation is to get a gnarly general formula then apply the far-field approximation to it. A related application is any time the “reciprocal lattice” is mentioned in solid-state physics; e.g. in X-ray crystallography, what you see on the CRT screen in the simplest case once the X-rays have passed through the sample is the (continuous) Fourier transform of (a bunch of Dirac deltas stuck at each center of) its crystal lattice[2], and that’s because it’s basically the same thing as the Fraunhofer diffraction in the previous paragraph. Of course, the mammalian inner ear is also a spectral analyzer[3]. [1] https://en.wikipedia.org/wiki/Fourier_optics#The_far_field_approximation https://en.wikipedia.org/wiki/Fourier_optics#The_far_field_a... [2] https://en.wikipedia.org/wiki/Laue_equations https://en.wikipedia.org/wiki/Laue_equations [3] https://en.wikipedia.org/wiki/Basilar_membrane#Frequency_dispersion https://en.wikipedia.org/wiki/Basilar_membrane#Frequency_dis...

nerdponx 4y ago

I liked this article a lot, but > One thought that occurred to me after this investigation was the premise that the immense bleeding-edge models of today with billions of parameters might be able to be built using orders of magnitude fewer network resources by using more efficient or custom-designed architectures. Transformer units themselves are already specialized things. Wikipedia says that GPT-3 is a standard transformer network, so I'm sure there is additional room for specialization. But that's not a new idea either, and it's often the case that a after a model is released, smaller versions tend to follow.

sebzim4500 4y ago
Transformers are specialized to run on our hardware, whereas the article is suggesting architectures which are specialized for a specific task.
- nerdponx 4y ago
  Are transformers not already very specialized to the task of learning from sequences of word vectors? I'm sure there is more that can be done with them other than making the input sequences really long, but my point was that LLMs are hardly lacking in design specialized to their purpose.
  - sebzim4500 4y ago
    > Are transformers not already very specialized to the task of learning from sequences of word vectors? No, you can use transformers for vision, image generation, audio generation/recognition, etc. They are 'specialized' in that they are for working with sequences of data, but almost everything can be nicely encoded as a sequence. In order to input images, for example, you typically split the image into blocks and then use a CNN to produce a token for each block. Then you concatenate the tokens and feed them into a transformer.
    - nerdponx 4y ago
      That's fair, and I didn't realize people were using them for images that way. I would still argue that they are at least somewhat more specialized than plain fully-connected layers, much like convolutional layers. It is definitely interesting that we can do so much with a relatively small number of generic "primitive" components in these big models. but I suppose that's part of the point.

aargh_aargh 4y ago

The essay linked from the article is interesting: http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html

version_five 4y ago
Yes I just read it too. It appears to have been discussed here multiple times: https://hn.algolia.com/?q=bitter+lesson https://hn.algolia.com/?q=bitter+lesson I'd say it has aged well and there are probably lots of new takes on it based on some of the achievements of the last 6 months. At the same time, I don't agree with it. To simplify, the opposite of "don't over-optimize" isn't "it's too complicated to understand so never try". It is thought provoking though
sva_ 4y ago
I think there is no doubt that there must be more efficient model architectures out there, take for example the sample efficiency of GPT-3: > If you think about what a human, a human probably in a human’s lifetime, 70 years, processes probably about a half a billion words, maybe a billion, let’s say a billion. So when you think about it, GPT-3 has been trained on 57 billion times the number of words that a human in his or her lifetime will ever perceive.[0] 0. https://hai.stanford.edu/news/gpt-3-intelligent-directors-conversation-oren-etzioni https://hai.stanford.edu/news/gpt-3-intelligent-directors-co...
- lostmsu 4y ago
  Humans are not trianed on words.
  - lgas 4y ago
    What do you mean? That we are not trained ONLY on words? Or that the training we receive on words is not the same as the training of a NN? Or something else?
    - lostmsu 4y ago

YesThatTom2 4y ago

Is this going to change how 8-but adders are implemented in chips?

GTP 4y ago
No, there was a time where we had analog calculators but there are good reasons why digital electronics won in the computing space.

hoseja 4y ago

Reminded me of the 0xFFFF0000 0xFF00FF00 0xF0F0F0F0 0xCCCCCCCC 0XAAAAAAAA trick, the use of which I don't currently recall... edit: several, but probably not very relevant https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html

dagss 4y ago

Impressive. Am I right that what is really going on here is that the network is implementing the "+" operator by actually having the CPU of the host carrying out the "+" when executing the network? I.e., the network converts the binary input and output to floating point, and then it is the CPU of the host the network is running on that really does the addition in floating point. So usually one does a bunch of FLOPs to get "emerging" behaviour that isn't doing arithmetic. But in this case, instead the network does a bunch of transforms in and out so that in a critical point, the addition executed in the network runner is used for exactly its original purpose: Addition. And I guess saying it is "analog" is a good analogy for this..

Filligree 4y ago
That's an accurate enough description of what's going on here, yeah, but I'm very curious if this could be implemented in hardware. What we've got is an inexact not-quite-binary adder, but one that's potentially smaller and faster than the regular binary ones.
- garganzol 4y ago
  It can be implemented in hardware but the implementation would be more complex than a digital adder based on logical gates.
  - em3rgent0rdr 4y ago
    Analog addition is actually really easy if you can tolerate noise and heat and can convert to/from representing the signal as an analog current. Using Kirchhoff's Current Law, addition of N currents from current sources is achieved by joining those N wires to a shared exit wire which contains the summed current.
    - garganzol 4y ago
      Addition is easy, DAC is relatively easy, but ADC is not.
- 4y ago

jccalhoun 4y ago

These stories remind me of a story from Discover Magazine https://www.discovermagazine.com/technology/evolving-a-conscious-machine https://www.discovermagazine.com/technology/evolving-a-consc... A researcher was using a process to "evolve" a FPGA and the result was a circuit that was super efficient but worked in ways that were unexpected: part of the circuit seemed unconnected to the rest but if removed the whole thing stopped working and it would only work at a specific temperature.

qikInNdOutReply 4y ago
Ah, the good old radio component you can program into fpgas.
- pjc50 4y ago
  Very easy to design a radio component into electronics, much harder to design it out.
  - nkrisc 4y ago
    I’ve had all kinds of cheap electronics that came with unadvertised radio features for free.
    - TeMPOraL 4y ago
      It's sad that those pesky regulators from the FCC make it so hard to get devices with unintended radio functionality these days!
      - gumby 4y ago
        I know, if people really cared about devices rejecting interference the free market would sort that out, amirite?
        WalterBright 4y ago

MontyCarloHall 4y ago

A couple questions: 1. How much of this outcome is due to the unusual (pseudo) periodic activation function? Seems like a lot of the DAC-like behavior is coming from the periodicity of the first layer’s output, which seems to be due to the unique activation function. 2. Would the behavior of the network change if the binary strings were encoded differently? The author encodes them as 1D arrays with 1 corresponding to 1 and 0 corresponding to -1, which is an unusual way of doing things. What if the author encoded them as literal binary arrays (i.e. 1->1, 0->0)? What about one-hot arrays (i.e. 2D arrays with 1->[1, 0] and 0->[0, 1]), which is the most common way to encode categorical data?

Ameo 4y ago
I think that the activation function definitely is important for this particular case, but it's not actually periodic; it saturates (with a configurable amount of leakyness) on both ends. The periodic behavior happens due to patterns in individual bits as you count up. As for the encoding, I think it's a pretty normal way to encode binary inputs like this. Having the values be -1 and 1 is pretty common since it makes the data centered at 0 rather than 0.5 which can lead to better training results.
evrimoztamur 4y ago
For 1., the author used Ameo (the weird activation function) in the first layer and tanh for others, later on notes: "While playing around with this setup, I tried re-training the network with the activation function for the first layer replaced with sin(x) and it ends up working pretty much the same way. Interestingly, the weights learned in that case are fractions of π rather than 1." By the looks of it, any activation function that maps a positive and negative range should work. Haven't tested that myself. The 1 vs π is likely due to the peaks of the functions, Ameo at 1 and sine at π/2. Regardless, it's not Ameo.
sebzim4500 4y ago
1. The author has prior blog posts talking about this activation function, and apparently it does help to learn binary logic tasks. 2. I doubt this matters at all here. For some architectures having inputs be 0 on average is useful, so the author probably just picked it as the default choice.

AstralStorm 4y ago

When you expect your network to learn a binary adder and it learns FFT addition instead. :) (For an ANN FFT is more natural as it's a projection algorithm.)

allisdust 4y ago

totally off topic: Any pointers to tutorials/articles that teach implementation of common neural network models in javascript/rust (from scratch) ?

puttycat 4y ago

Recent work on NNs where applying Kolmogorov complexity optimization leads to a network that solves binary addition with a carry-over counter and 100% provable accuracy: (see Results section) https://arxiv.org/abs/2111.00600 https://arxiv.org/abs/2111.00600

moyix 4y ago

Related: an independent reverse engineering of a network that "grokked" modular addition: https://www.alignmentforum.org/posts/N6WM6hs7RQMKDhYjB/a-mechanistic-interpretability-analysis-of-grokking https://www.alignmentforum.org/posts/N6WM6hs7RQMKDhYjB/a-mec... One interesting thing is that this network similarly does addition using a Fourier transform.

rehevkor5 4y ago

Not too surprising. Each layer can multiply each input by a set of weights, and add them up. That's all you need, in order to convert from base 2 to base 10. In base 2, we calculate the value of a set of digits by multiplying each by 2^0, 2^1, ..., 2^n. Each weight is twice the previous. The activation function is just making it easier to center those factors on zero to reduce the magnitude of the regularization term. I am guessing you could probably get the job done with just two neurons in the first layer, which output the real value of each input, one neuron in the second layer to do the addition (weights 1, 1), and 8 neurons in the final layer to convert back to binary digits.

tonmoy 4y ago
While your analysis sounds good, I don’t think you mean base 10, you probably mean a “single float”?

KhoomeiK 4y ago

A more theoretical but increasingly popular approach to identifying behavior like this is interchange intervention: https://ai.stanford.edu/blog/causal-abstraction/ https://ai.stanford.edu/blog/causal-abstraction/

wwarner 4y ago

So important. Here’s a prediction. Work like this on model explainability will continue and eventually will reveal patterns in the input that reliably produce features in the resulting models. That knowledge will tell us about nature, in addition to ML.

kens 4y ago

The trick of performing binary addition by using analog voltages was used in the IAS family of computers (1952), designed by John von Neumann. It implemented a full adder by converting two input bits and a carry in bit into voltages that were summed. Vacuum tubes converted the analog voltage back into bits by using a threshold to generate the carry-out and more complex thresholds to generate the sum-out bit.

elcritch 4y ago
Nifty, makes one wonder if logarithmic or sigmoid functions for ML could be done using this method. Especially as we approach the node size limit, perhaps dealing with fuzzy analog will become more valuable.
- djmips 4y ago
  There are a few startups making analog ML compute. Mythic & Aspinity for example https://www.eetimes.com/aspinity-puts-neural-networks-back-to-analog/ https://www.eetimes.com/aspinity-puts-neural-networks-back-t...
  - shagie 4y ago
    Veritasium has a bit of an video on Mythic - Future Computers Will Be Radically Different (Analog Computing) - https://youtu.be/GVsUOuSjvcg https://youtu.be/GVsUOuSjvcg
    - westurner 4y ago
      From "Faraday and Babbage: Semiconductors and Computing in 1833" https://news.ycombinator.com/item?id=32888210 https://news.ycombinator.com/item?id=32888210 and then "Qubit: Quantum register: Qudits and qutrits" https://news.ycombinator.com/item?id=31983110 https://news.ycombinator.com/item?id=31983110: >>> The following is an incomplete list of physical implementations of qubits, and the choices of basis are by convention only: [...] Qubit#Physical_implementations: https://en.wikipedia.org/wiki/Qubit#Physical_implementations https://en.wikipedia.org/wiki/Qubit#Physical_implementations > - note the "electrons" row of the table According to this Table on wikipedia, it's possible to use electron charge (instead of 'spin') to do Quantum Logic with Qubits. How is that doing quantum logical computations with electron charge different from from what e.g. Cirq or Tequila do (optionally with simulated noise to simulate the Quantum Computer Engineering hardware)? FWIU, analog and digital component qualities are not within sufficient tolerance to do precise analog computation? (Though that's probably debatable for certain applications at least, but not for general purpose computing architectures?) That is, while you can build adders out of voltage potentials quantified more specifically than 0 or 1, you might shouldn't without sufficient component spec tolerances because noise and thus error. IMHO, Turing Tumble and Spintronics are neat analog computer games. (Are Qubits, by Church-Turing-Deutsch, sufficient to; 1) simuluate arbitrary quantum physical systems; or 2) run quantum logical simulations as circuits with low error due to high coherence? https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93... ) >> See also: "Quantum logic gate" https://en.wikipedia.org/wiki/Quantum_logic_gate https://en.wikipedia.org/wiki/Quantum_logic_gate Analog computers > Electronic analog computers aren't Electronic digital computers: https://en.wikipedia.org/wiki/Analog_computer#Electronic_analog_computers_2 https://en.wikipedia.org/wiki/Analog_computer#Electronic_ana...

2bitencryption 4y ago

> One thought that occurred to me after this investigation was the premise that the immense bleeding-edge models of today with billions of parameters might be able to be built using orders of magnitude fewer network resources by using more efficient or custom-designed architectures. I'm pretty convinced that something equivalent to GPT could run on consumer hardware today, and the only reason it doesn't is because OpenAI has a vested interest in selling it as a service. It's the same as Dall-E and Stable Diffusion - Dall-E makes no attempt to run on consumer hardware because it benefits OpenAI to make it so large that you must rely on someone with huge resources (i.e. them) to use it. Then some new research shows that effectively the same thing can be done on a consumer GPU. I'm aware that there's plenty of other GPT-like models available on Huggingface, but (to my knowledge) there is nothing that reaches the same quality that can run on consumer hardware - yet.

WalterBright 4y ago

In a similar vein, in the 1980s a "superoptimizer" was built for optimizing snippets of assembler by doing an exhaustive search of all combinations of instructions. It found several delightful and unexpected optimizations, which quickly became incorporated into compiler code generators.

convolvatron 4y ago
you can mention Massalin by name. she's pretty brilliant, idk where she is now
- WalterBright 4y ago
  I don't recall who wrote the paper, thanks for the tip, enabling me to find the paper: H. Massalin, “Superoptimizer - A Look at the Smallest Program,” ACM SIGARCH Comput. Archit. News, pp. 122–126, 1987. https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf https://web.stanford.edu/class/cs343/resources/superoptimize... The H is for "Henry".
  - mgliwka 4y ago
    It’s Alexia Massalin now: https://en.m.wikipedia.org/wiki/Alexia_Massalin https://en.m.wikipedia.org/wiki/Alexia_Massalin

Lisa_Novak 4y ago

[dead]

GeorgeTirebiter 4y ago

Small nit: the analog DAC circuit has MSB and LSB reversed. That is, the LSB goes into the top 128k resistor. If you think of it one bit at a time, the gain of the circuit = -Rf/R --- where R is one of the resistors in the ladder. (Rf is the feedback resistor, which is unlabeled and un-valued in the article.) Clearly, you get bigger output when R is smaller.

nnurmanov 4y ago

I wonder if is possible to reverse engineer passwords. One can input passwords, train them on known values. What to expect?

etherio 4y ago

Relevant: reverse engineering modular addition https://twitter.com/NeelNanda5/status/1559060507524403200 https://twitter.com/NeelNanda5/status/1559060507524403200

imtringued 4y ago

I don't see how this is surprising. It's cool but come on, you have a network consisting of addition and multiplication and you expect it to not use them? What else is it supposed to do? Memorize every input output pair like a look up table?