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

<p>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. </p>

<p>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. </p>

<p>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?</p>

<p>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}$. </p>

<p>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. </p>

CC BY-SA 4.0
2018-05-10T06:14:19.973Z
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](https://en.wikipedia.org/wiki/Horn_clause), by any chance?
Andrej Bauer
CC BY-SA 4.0
2018-05-10T06:27:25.417Z
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.
CC BY-SA 4.0
2018-05-10T06:28:42.153Z
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.
CC BY-SA 4.0
2018-05-10T08:46:42.637Z
@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
CC BY-SA 4.0
2018-05-10T15:52:17.513Z
@AndrejBauer, Yeah, that seems like it should change the answer if the atomic predicates are simple enough.
D.W.
<lo.logic><machine-learning><lg.learning><st.statistics>
To what extent supervised learning ERM learn first-order knowledge
Daniel
# To what extent supervised learning ERM learn first-order knowledge

(Asked by: username_0 on 2018-05-10)

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.

**Tags:** lo.logic, machine-learning, lg.learning, st.statistics
> **Comments:**
> **username_1**: 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](https://en.wikipedia.org/wiki/Horn_clause), by any chance?  
> **username_2**: 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)$?  
> **username_2**: 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$.  
> **username_1**: @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.)  
> **username_2**: @AndrejBauer, Yeah, that seems like it should change the answer if the atomic predicates are simple enough.  

---

## 0 answers

