# To what extent supervised learning ERM learn first-order knowledge

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.

• 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? – Andrej Bauer May 10 '18 at 6:14
• 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)$? – D.W. May 10 '18 at 6:27
• 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$. – D.W. May 10 '18 at 6:28
• @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.) – Andrej Bauer May 10 '18 at 8:46
• @AndrejBauer, Yeah, that seems like it should change the answer if the atomic predicates are simple enough. – D.W. May 10 '18 at 15:52