Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Say we have a vector representation of any integer of magnitude n, V_n

This vector is the input to a machine learning algorithm.

First question : For what type of representations is it possible to learn the primality/compositeness of n using a neural network or some other vector-to-bit ML mapping. This is purely theoretical -- the neural network could be possibly unbounded in size.

Let's ignore representations that are already related to primality testing such as : the null separated list of factors of n, or the existence of a compositeness witness such as in Miller Rabin. Let's instead focus on representations in different radices, or representations as coefficient vectors of (possibly multivariate) polynomials. Or other exotic ones as are posited.

Second question : for what, if any, types of ML algorithm will learning this be impossible regardless of the specifics of the representation vector? Again, let's leave out 'forbidden by triviality' representations of which examples are given above.

The output of the machine learning algorithm is a single bit, 0 for prime, 1 for composite.

The title of this question reflects my assessment that the consensus for question 1 is 'unknown' and the consensus for question 2 is 'probably most ML algorithms'. I'm asking this as I don't know any more than this and I am hoping someone can point the way.

The main motivation, if there is one, of this question is : is there an 'information theoretic' limit to the structure of the set of primes that can be captured in a neural network of a particular size? As I'm not expert in this kind of terminology let me rephrase this idea a few times and see if I get a Monte-Carlo approximation to the concept : what is the algorithmic complexity of the set of primes? Can the fact that the primes are Diophantine recursively enumerable (and can satisfy a particular large diophantine equation) be used to capture the same structure in a neural network with the inputs and outputs described above.

share|improve this question
9  
From the theory perspective, your problem isn't well-defined. What are the inputs to the machine learning algorithm? How are they generated? What does the algorithm know in advance of its learning task? –  Lev Reyzin Jan 10 '13 at 20:55
3  
I don't think this is a good question in its current form for this site. –  Kaveh Jan 10 '13 at 21:02
4  
It can. But in machine learning we want to minimize error on testing dataset. Now, if you train on $[1, 20]$ you might end up learning $f(n) = n^2 - n + 41$ and which works perfectly for numbers less that $41$. But after that its performance is no good. People have tried this(manually :-) ) and so far without much success. In ML we try to find patterns but what if there isn't any pattern? –  Pratik Deoghare Jan 11 '13 at 0:10
1  
You seem to be asking whether there is an algorithm that given a function from finite sequences of natural numbers to predicates on the natural numbers, can correctly output a primality predicate given a sequence of primes, subject to additional constraints on the algorithm. Articulating your restriction further is non-trivial, if at all possible. If you try to make it precise, you may see. –  Vijay D Jan 11 '13 at 1:25
1  
A simple answer, because it is difficult to approximate the search space $S$ of the prime number function $f$ you are looking for (that is, $f(n)$ returns 1 if $n$ is prime and 0 otherwise for every $n$). In relation to @PratikDeoghare comment, it is difficult to find a pattern in $S$. –  AJed Jan 11 '13 at 3:12
show 3 more comments

3 Answers

up vote -9 down vote accepted

this is an old question/problem with many, many connections deep into number theory, mathematics, TCS and in particular Automated Theorem Proving.[5]

the old, near-ancient question is, "is there a formula for computing primes"

the answer is, yes, in a sense, there are various algorithms to compute it.

the Riemann zeta function can be reoriented as an "algorithm" to find primes.

seems possible to me that a GA, genetic-algorithm approach may succeed on this problem some day with an ingenious setup, ie GAs are the nearest known technology that have the most chance of succeeding.[6][7] its the problem of finding an algorithm from a finite set of examples, ie machine learning, which is very similar to mathematical induction. however there does not seem to be much research into application of GAs in number theory so far.

the nearest to this in existing literature seems to be eg [8] that discusses developing the twin prime conjecture in an automated way ie "automated conjecture making".

another approach is a program that has a large set of tables of standard functions, along with some sophisticated conversion logic, to recognize standard integer sequences. this is a new function built into Mathematica called findsequence [3]

its also connected to a relatively new field called "experimental mathematics" [9,10] or what is also called "empirical" research in TCS.

another basic point to make here is that the sequence of primes is not "smooth", highly irregular, chaotic, fractal, and standard machine learning algorithms are historically based on numerical optimization and minimizing error (eg gradient descent), and do not do so well on finding exact answers to discrete problems. but again GAs can succeed and have been shown to succeed in this area/regime.

[1] is there a math eqn for the nth prime, math.se

[2] formula for primes, wikipedia

[3] wolfram findsequence function

[4] riemann zeta function

[5] top successes of automated theorem proving

[6] applications of genetic algorithms in real world

[7] applying genetic algorithms to automated thm proving by Wang

[8] Automated Conjecture Making in Number Theory using HR, Otter and Maple colton

[9] Are there applications of experimental mathematics in TCS?

[10] A reading list on experimental algorithmics

share|improve this answer
1  
this is a great answer. Not sure if the site will agree, but it was what I was looking for. A bunch of new directions to explore and age old connections. Thanks, really appreciate that. Particularly GAs. Also, you read between the lines and generalized from machine learning to 'formular for primes'. That is very helpful thanks. –  Cris Stringfellow Jan 11 '13 at 16:20
7  
@Cris, there is almost nothing in this answer which is about machine learning. From your comment on Aryeh's answer it seems to me that you are not familiar with machine learning (may I ask where have you seen a machine learn an algorithm like primality testing from a list of examples?) –  Kaveh Jan 11 '13 at 16:49
3  
GA can "learn" a primality testing algorithm in the same sense in which the proverbial infinite monkey will one day type the full works of Shakespeare –  Sasho Nikolov Jan 12 '13 at 0:25
    
@sasho, it hasnt been demonstrated yet but (yes, imho) its probably not due to limitations in the technology but rather lack of attempt. koza demonstrated GAs "solving/learning" complex algorithms for video games eg pacman (via lisp trees of primitives), and also constructing circuits using subcomponents. isnt that at least as hard as finding primes? the real question is, what types of primitives would the system have, and how primitive can they be & still find the solution? –  vzn Jan 12 '13 at 2:52
add comment

The success of a learning algorithm depends critically on the representation. How do you present the input to the algorithm? In an extreme case, suppose you present the numbers as sequences of prime factors -- in this case, learning is quite trivial. In another extreme, consider representing the numbers as binary strings. All the standard learning algorithms I know would fail here. Here is one that would work: find the smallest Turing machine that accepts all the positive examples and rejects all the negative ones. [Exercise: prove that this is a universal learner.] One problem with that is that the task is not Turing-computable. To put things in perspective, can you learn to recognize primality based only on the binary representation?

share|improve this answer
    
I can learn to recognize primality based in binary rep if I 'learn' , say, the Miller Rabin algorithm. But I want to go beyond things like that, and see if there is something else. Why is the task you mention not Turing-computable? –  Cris Stringfellow Jan 11 '13 at 16:26
5  
I don't understand how one can talk about a learning problem here without referring to, for instance, the target class of functions. –  Lev Reyzin Jan 11 '13 at 23:05
1  
Lev is right, of course -- but I thought a discussion of function classes would be beyond the scope of the question... :) –  Aryeh Jan 13 '13 at 12:31
add comment

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction.

There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the distinction is a social and aesthetic one, rather than a formal one.

Fix a finite alphabet $A$ and the set of all languages $\mathcal{P}(A^*)$ consisting of finite-length words over $A$. This is everything you can express in terms of $A$. Now consider a family of languages $\mathcal{F} \subseteq \mathcal{P}(A^*)$. You can think of this as the concepts you are interested in. You often have to fix the family of concepts you care about because, as others have pointed out, the representation of the concept and presentation of data are extremely important.

Imagine a teacher who is going to teach you a concept. The teacher will choose one of the languages without your knowledge. The teacher will then present information to you about the language. There are many presentations. The simplest is to give you examples. A presentation of positive data is a function $f: \mathbb{N} \to A^*$ satisfying that

$$\bigcup_{i \in \mathbb{N}} f(i) = T, \text{ for some } T \text{ in } \mathcal{F}.$$

So, a presentation of positive data is an enumeration of the target concept, often with some additional fairness conditions thrown in. You can similarly ask for a presentation that labels words depending on whether they are in the language or not. Again, you can add additional conditions to ensure fairness and coverage of all words.

Suppose we have a family $Rep$ of representations of languages. That means every element $M$ of $Rep$ defines a language $L(M)$. Examples of representations are Boolean formulae, finite automata, regular expressions, systems of linear equations, domain specific programming languages, etc. Anything you want, really, except various condition are usually imposed to ensure the representation has basic tractability properties.

A passive learner is a function $p: \mathbb{N} \to Rep$ that makes a conjecture after seeing each word provided by the teacher. We may often require that the learner is consistent. Meaning, the language $L(p(i))$ should contain all the words $f(j)$ for $j \le i$. The learner stabilizes if the learner's guess for the target language does not change. Specifically, there should exist some index $k$ such that for all $j \ge k$, $L(p(j)) = L(p(j+1))$. The learner succeeds if the final language equals the target language.

Let me emphasise that this is only one specific formalisation of one specific learning model. But this is step zero before you can start asking and studying questions that you are interested in. The learning model can be enriched by allowing interaction between the learner and the teacher. Rather than arbitrary families of languages, we can consider very specific languages, or even specific representations (such as monotone Boolean functions). There is a difference between what you can learn in each model and the complexity of learning. Here is one example of a fundamental impossibility result.

Gold [1967] No family of languages that contains all finite languages and at least one super-finite language is passively learnable from positive data alone.

One should be very very careful in interpreting this result. For example, Dana Angluin showed in the 80s that

Angluin [1982] The class of $k$-reversible languages is passively learnable in the limit from positive data.

The class of $k$-reversible languages is infinite, contains super-finite languages, but interestingly, does not contain all finite languages. Now once you change the learning model, the fundamental results change.

Angluin [1987] Regular languages are learnable from a teacher that answers equivalence queries and provides counterexamples. The algorithm is polynomial in the set of states of the minimal DFA and length of the maximal counterexample.

This is quite a strong and positive result and recently has found several applications. However, as always the details are important, as the title of the paper below already suggests.

The minimum consistent DFA problem cannot be approximated within and polynomial , Pitt and Warmuth, 1989.

Now you may be wondering, how is any of this relevant to your question? To which my answer is that the design space for a mathematical definition of your problem is very large and the specific point you choose in this space is going to affect the kind of answers you will get. The above is not meant to be a comprehensive survey of how to formalise the learning problem. It's just meant to demonstrate the direction you may want to investigate. All the references and results I quote are extremely dated, and the field has done a lot since then. There are basic textbooks you could consult to obtain the sufficient background to formulate your question in a precise manner and determine if the answer you seek already exists.

share|improve this answer
    
That's great @Vijay D, thank you for that. –  Cris Stringfellow Jan 12 '13 at 6:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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