I have been exploring the application and behavior of deep neural networks in context of some mathematical problems. I am trying to observe which mathematical problems blend well and can be answered with deep networks and which do not seem to be solvable by such learning models. Let me summarize my findings in point by point format for easy reading. Questions and concerns are mentioned along with them so please feel free to comment if you are aware of any direction or input. Many apologies for long post.
1) Properties or function of a number x, which can be answered by just exploring and manipulating bits of this given number can be solvable by deep neural networks. For example, it can learn finding square root/cubic root/square/polynomial function of x.
Answering questions like “Is x even or not”? (classification problem) is also solvable by such models, reason being that answer is imbedded in the bits of x. By same logic, we can make a neural network which can answer if a number is divisible by 7 or not, or 7 and 9 together or not.
2) Answering those properties of x, which depend on bits of unknown other numbers too, a network would fail to do so. For example, a classification problem would be “is x prime?”. Answer to this question depends on “bit information” of unknown number of other primes which are less than x. Any network won’t be able to explore these unknown numbers hence it will fail to answer them.
Information present in bits of x is not sufficient to answer the question about its primality.
By this logic, finding x! (x factorial) seems to be a difficult job for a network. Could not test “x factorial” logic, for small x, factorial value gets too big to be handled by my python code. Is it a valid claim?
3) For each x, what would be size of Collatz sequence starting at x also seems to be unanswerable by deep networks. Reason seems to be, bit values of x don’t seem to contain enough information (entropy) to answer this question.
4) A deep neural network has capability to solve quadratic, cubic, 4th, 5th, 6th and 7th equation. Does that mean, these equations have closed form solution or they can be approximated by a Taylor’s series? I went through https://math.stackexchange.com/questions/291909/closed-form-expression-for-roots-of-a-polynomial, but based on my experiments, it seems like coefficients of polynomial equations have enough information in them to produce the roots. Additionally, if it can be learnt by a network, it might not be very complex or has a simpler approximating function.
Also, these approximating or actual functions for the roots are strictly ordered i.e. if for a n degree polynomial equation, root function produces i-th root in magnitude sense. Then for all other equations of n-th degree, root function would be producing i-th root only in magnitude sense. It gets clear when we look at the format of root function for quadratic, cubic equations. They are in an order. One function is strictly greater than other and so on, no matter what the coefficients are.
5) We know that to know the roots of a polynomial, Newton-Raphson method is used, which uses derivatives and successive iterations to converge at a root. It seems like, deep networks are also good at the same task, so are Newton-Raphson and back propagation algorithms somehow related? May be mirror image or sides of a coin. Which would lead me to think that problem of “is this image of a cat” can be translated somehow to a polynomial function of x (pixel information), whose real root is a “cat” and all other roots are imaginary. Real task would be to construct the equivalent polynomial equation from the image, so that Newton-Raphson converges to value “cat”. I myself is not sure if these thoughts make any sense or feasible. Would love to know if any community member has any views on it.
6) Prime Factor (Thank god) also seems to a difficult problem to be learnt by a deep network. However, I limited my tests to only few thousand numbers.
7) Primality of a number is manmade notion, these number is highly useful in our environment hence this property has become important in our day to day life. If we consider bit string of a number x, its finite in length hence implying information present in the bit string can answer only finite number of properties of number. Even, odd, perfect, palindrome, prime etc. However, we humans can come up with infinite number of properties, implying that a network would not be able to answer all properties (a sense of pigeonhole principle or Church Turing thesis that a program cannot answer non-trivial properties of another program). For example:
Let’s call “Pythagorean number to be a number whose 7th and 9th bit is set and it is coprime with all smaller perfect numbers”. Such classification problems seem to be unsolvable by a deep network because it won’t know how many and what other numbers are determining the answers.