2
$\begingroup$

Can neural networks be used to study (elementary) number theoretic problems? What are examples where this has been done in the past? Or is there on the contrary an understanding that neural networks are not helpful for such problems?

To make the question more concrete, let me give an example of the kind of number theoretic problem I'm thinking of: given two natural numbers a and b I may want to compute the rounded down quotient int(a/b). Naively I would restrict to 64 bit unsigned numbers and build a neural network that has 128 neurons in the input layer and 64 neurons in the output layer representing the binary expansion of the numbers. Assuming I laid out the network properly and trained it well, would I be expected to get useful output? In particular, would I be able to interpret the output as a number and would it often be the right answer?

Note: the reason why I think of this as problem as "number theoretic" is because I want to compute int(a/b) rather than the rational number a/b. This is essentially a step in Euclid's algorithm. So the non-linear behaviour int(4/3) = 1, int(5/3) = 1, int(6/3) = 2 is crucial and would need to be recognizable in the output.

$\endgroup$
  • $\begingroup$ Hi, did you find an answer? I'm interested as well $\endgroup$ – Stefano Giacone Feb 3 '18 at 17:54
  • $\begingroup$ No, I didn't find a formal answer. Heuristically my impression is that neural networks would perform rather badly. $\endgroup$ – Stefan Witzel Feb 12 '18 at 8:00
  • $\begingroup$ I'd bet that you can gain nothing as number theory is rather abstract and you'd need a system working with formulas in order to gain any useful knowledge. However, your integer divisor problem can definitely be learned as it's a final optimization problem. What's unclear is the number of neurons needed - you probably don't want to use 2**128 of them. AFAIK no CPU has a single-step 64:64 bit divider, so you most probably have to use some feedback network, too. $\endgroup$ – maaartinus Apr 10 '18 at 1:10
1
$\begingroup$

The simplest form of a neural network is the McCulloch Pitts neuron. It was invented in the 1940s and is equal to a logicgate network. What is a logicgate? A logicgate is a combination of AND, OR and NOT circuit which can be used to model a half-bit adder and a complete computer. This was important for the history of computing. Usually a computer is used to run a program (stored program computer) but it is also possible to construct of the AND, OR and NOT elements, the algorithm itself. This technology is used in modern ASIC computers which have a fixed algorithm.

The OP was a about a number theoretic problem, called int(a/b). Solving the task has to do with implementing an algorithm. It can be implemented on any Turing-compatible computer. The normal way in doing so is with sourcecode in the C-language, but the same algorithm can be implemented with pure logicgates too. Logicgates are the same like the McCUlloch Pitts neuron. So the answer is yes: a neural network is turing-compatible, it is some kind of trainable ASIC computer. The bottleneck is only to find the weights. In the area of ASIC design, the needed amount of logicgates is generated by compilers. They are taking c-sourcecode and converting it into hardware specification which can be realized on a Printed Circuit Board. If the hardware is equal to McCulloch Pitts neuron, the synthesis is a bit complicated. Finding the weights is equal to train the neural network. This is usually done with the back-propagation algorithm.

In the literature the term “Neural Cryptography” is used for describing the relationship between neural networks and number theory. The main problem is here also that the state space of possible weights is too big and so called training algorithm are very slow. The number one speed up method for finding the weights has to do with heuristics. This allows the neural network to run a certain algorithm. But this goes a bit out of the scope of the question.

$\endgroup$
  • $\begingroup$ Thanks, that is very helpful (in particular the keyword to look for)! In principle the connection to logical networks is clear but it seems to that you would need to already feed in the "right" network (or one containing it) with unassigned gates and then the training would only determine which gate is an "and" which is an "or" etc. Perhaps that's not so different from other neural networks but the logic network I would think of would involve a 32 bit ALU which has some of its outputs (eventually) connected back to itself. So as a neural network it would be horrible. $\endgroup$ – Stefan Witzel Sep 6 '18 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.