Suppose I have a collection of (hidden) first-order rules: $$ \mathcal{R}: \{ Q_i(x) => P_i(x) \}_{i=1}^{k} $$ all defined over $x \in \mathcal{X}$.

I can use these rules and (automatically) generate a large collection of (training) data for my supervised system: $ \mathcal{D}: \{(x_i, y_i)\}_{i=1}^{n} $, say for $y_i \in \{-1, +1\}$, and run a supervised system on this sampled data, and test on a heldout set.

If my rules are compatible (not contradictory) a rule-based system should be able to get a perfect score on the sampled set. However, I am not sure how would a supervised do on this.

Are there any possibility/impossibility on the ability of supervised systems for learning first-order rules (possibly with some assumptions) and based on finite samples?

This is basically the reverse of rule-learning, in which the goal is to learn some rules $\mathcal{R}$, given a training data $\mathcal{D}$.

I did a little bit of Googling but didn't get anything directly relevant (all I found was algorithms for first-order rule induction or training supervised systems that use 1st order rules as features). That said, it's possible that I am missing some results on this. Would appreciate any thoughts on this.

  • 1
    $\begingroup$ What do you mean by "first-order" rules? If you are referring to first-order logic, then it sounds like $Q_i$ and $P_i$ can be arbitrary first-order formulas (involving $\forall$, $\exists$ and further nested $\Rightarrow$), in which case you umight as well just say that all your formulas are of the form $R_i(x)$ for an arbitrary formula. Do you mean Horn clauses, by any chance? $\endgroup$ – Andrej Bauer May 10 '18 at 6:14
  • $\begingroup$ How does $y_i$ relate to $x_i$ and to the rules? Is the idea that $y_i=1$ iff $x_i$ satisfies all the rules? In other words, how do you use these rules to generate the training samples $(x_i,y_i)$? $\endgroup$ – D.W. May 10 '18 at 6:27
  • 1
    $\begingroup$ Your formulation is equivalent to saying that the ruleset is $\mathcal{R} : \{R_i(x)\}_{i=1}^k$. Here you can define the predicate $R_i(x)$ to be equivalent to $Q_i(x) \implies P_i(x)$. And since you can identify any predicate $R_i(x)$ with a set $S_i$, such that $R_i(x)$ is true iff $x \in S_i$, your ruleset becomes equivalent to saying that you have a single rule that $x \in S$, where $S= S_1 \cap \cdots \cap S_k$. So you are asking how well supervised learning can learn membership in an arbitrary set. By the no free lunch theorem, it's impossible without a prior on $S$. $\endgroup$ – D.W. May 10 '18 at 6:28
  • $\begingroup$ @D.W.: is there a difference if we presume that the formulas are Horn clauses? (There's still a question of how complicated can the atomic predicates be.) $\endgroup$ – Andrej Bauer May 10 '18 at 8:46
  • $\begingroup$ @AndrejBauer, Yeah, that seems like it should change the answer if the atomic predicates are simple enough. $\endgroup$ – D.W. May 10 '18 at 15:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.