0
$\begingroup$

I'd like to use machine learning to guess a mathematical pattern: the input are certain polynomials in four variables $q_1,q_2,q_3,q_4$, the output can be zero or one.

Allowed polynomials are such that (i) all their non-zero coefficients are equal to one, (ii) they do not contain monomials of the form $q_1^j$ for $j \geq 0$, and (iii) if an allowed polynomial contains a monomial $m=q_1^a q_2^b q_3^c q_4^d$ for some non-negative integers $a,b,c,d$, then it also contains $m'=q_1^{a-1} q_2^b q_3^c q_4^d$, provided this does not violate (ii) and $a \geq 1$; similarly for $b \to b-1$, $c \to c-1$, and $d \to d-1$.

Here's an example batch, given by pairs {input, output}: $\{q_2,1\},\{q_3,1\},\{q_4,1\}$

Here's a second batch: $\{q_2+q_1 q_2,0\},\{q_2+q_2^2,0\},\{q_2+q_3,1\},\{q_3+q_1 q_3,0\},\{q_3+q_3^2,0\},\{q_2+q_4,1\},\{q_3+q_4,1\},\{q_4+q_1 q_4,0\},\{q_4+q_4^2,1\}$

I can construct larger and larger batches using Mathematica, and I'd like to know how to practically go from here, to instructing an AI to guess a simple function of $q$'s that reproduces the behavior, namely that can guess the correct output for previously unknown admissible polynomials.

What are the typical batch size and computational power required for such a program to succeed?

My idea is to use a function $\phi$ from the space of allowed polynomials $\mathcal P$ to the set $\mathbb Z_2=\{0,1\}$, of the form $\phi:\mathcal P \to \mathbb Z_2$, $p=\sum_{i \in I} m_i \mapsto \phi(p):= \sum_{i \in I' \subset I} m_i|_1 \mod 2$, where $m_i|_1$ means the $i$-th monomial inside $p$ evaluated at $q_1=q_2=q_3=q_4=1$, and come up with the form of $I'$ as function of $I$.

Notice there's no linear structure on $\mathcal P$.

Remark: of course instead of polynomials one could use punctured solid partitions.

$\endgroup$
4
  • $\begingroup$ Is there a limit on a,b,c,d? if there is such a limit, we have an upper bound(Number of dimensions = abcd) on types of monomials and hence we can applyit to finite dimensional NN $\endgroup$ – Diza Feb 17 '19 at 10:54
  • $\begingroup$ ai.stackexchange.com/questions/2008/… Considering each monomial as a word, this can be treated using RNNs or Recursive NNs $\endgroup$ – Diza Feb 17 '19 at 13:02
  • $\begingroup$ @ZaidSyedMMd I agree that one can impose a cutoff and deal with the reduced case of finite a,b,c,d, although the initial problem does not have one. Does your second comment imply that one can deal also with the case of no bound (the real problem I'm interested in)? $\endgroup$ – jj_p Feb 17 '19 at 14:25
  • $\begingroup$ Sorry i'm not aware of how RNNs work. "reduced case of finite a,b,c,d, " problem can be easily solved with digital logic network containing comparators(non-linearilty) and there is no need of "learning" required in the to-be-realised function. $\endgroup$ – Diza Feb 17 '19 at 17:25

Your Answer

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

Browse other questions tagged or ask your own question.