First-Order Regression Tree System
A First-Order Regression Tree System is a Binary Decision Tree System that implements a First-Order Regression Tree Algorithm to solve a First-Order Regression Tree Task.
- AKA: Logical Regression Tree System, Relational Regression Tree System.
- …
- Counter-Example(s):
See: First-Order Rule; Inductive Logic Programming; Relational Reinforcement Learning.
References
2017
- (Sammut & Webb, 2017) ⇒ Claude Sammut (editor), and Geoffrey I. Webb (editor). (2017). "First-Order Regression Tree"]. In: "Encyclopedia of Machine Learning and Data Mining" pp 521-521.
- QUOTE: A first-order regression tree can be defined as follows:
Definition 1 (First-Order Regression Tree)
A first-order regression tree is a binary tree in which
- Every internal node contains a test which is a conjunction of first-order literals.
- Every leaf (terminal node) of the tree contains a real valued prediction.
- QUOTE: A first-order regression tree can be defined as follows:
- An extra constraint placed on the first-order literals that are used as tests in internal nodes is that a variable that is introduced in a node (i.e., it does not occur in higher nodes) does not occur in the right subtree of the node.
Figure 1 gives an example of a first-order regression tree. The test in a node should be read as the existentially quantified conjunction of all literals in the nodes in the path from the root of the tree to that node. In the left subtree of a node, the test of the node is added to the conjunction, for the right subtree, the negation of the test should be added. For the example state description of Fig. 2, the tree would predict a Qvalue = 0. 9, since there exists no block that is both on the floor and clear, but there is a block which is on the floor and has another block on top of it. To see this, substitute BlockA in the tree with 2 (or 4) and BlockB with 1 (or 4).
The constraint on the use of variables stems from the fact that variables in the tests of internal nodes are existentially quantified. Suppose a node introduces a new variable X. Where the left subtree of a node corresponds to the fact that a substitution for X has been found to make the conjunction true, the right side corresponds to the situation where no substitution for X exists, i.e., there is no such X. Therefore, it makes no sense to refer to X in the right subtree.
- An extra constraint placed on the first-order literals that are used as tests in internal nodes is that a variable that is introduced in a node (i.e., it does not occur in higher nodes) does not occur in the right subtree of the node.
