# Refinement Operator

A Refinement Operator is a Set-Valued Function that maps a statement to a subset of its refinements.

**Context:**- It can alter a current Model.
- It can range from being a Downward Refinement Operator, to being a Top-Down Refinement Operator, to being a Upward Refinement Operator.

**Example(s):**- a Description Logic Refinement Operator such as:
- an Inductive Logic Programming Refinement Operator,
- a Multi-Instance Learning Numerical Refinement Operator,
- a Progol's Refinement Operator,
- a Refinement Operator for Key Discovery (ROCKER),
- One can substitute a literal for another, or one can add a literal to the body of a clause.

**Counter-Example(s):****See:**Refinement Modal Logic, Inductive Logic Programming, Description Logics, Concept Learning.

## References

### 2015

- (Soru et al., 2015) ⇒ Tommaso Soru, Edgard Marx, and Axel-Cyrille Ngonga Ngomo. (2015). “ROCKER: A Refinement Operator for Key Discovery.” In: Proceedings of the 24th International Conference on World Wide Web. ISBN:978-1-4503-3469-3 doi:10.1145/2736277.2741642
- QUOTE:
**Deﬁnition 3**(Reﬁnement Operator). Given a quasi-ordered space [math](S,op)[/math] an upward reﬁnement operator [math]r[/math] is a mapping from [math]S[/math] to [math]2^S[/math] such that [math] \displaystyle \forall_{s \in S} : s' \in r(S) \Rightarrow op(s,s')[/math]. [math]s'[/math] is then called a generalization of [math]s[/math].We deﬁne our reﬁnement operator over the space [math](\mathcal{P}, \preceq)[/math]. First, we begin by ordering the elements of [math]\mathcal{P}[/math] according to their score in ascending order, i.e., [math]\displaystyle\forall_{p_i,p_j \in \mathcal{P}},i \leq j \Rightarrow score(p_i) \leq score(p_j)[/math]. Then, we can deﬁne our operator as follows:

[math] \rho(P) = \begin{cases} \mathcal{P} \text{ iff } P=\emptyset \\ \{P\cup{p_1},\cdots,P\cup {p_i}\} \text{ where } p_j \in P \Rightarrow i\lt j. \end{cases} \quad \quad (5)[/math]

- QUOTE:

### 2010

- (Alphonse et al., 2010) ⇒ Erick Alphonse, Tobias Girschick, Fabian Buchwald, and Stefan Kramer. (2010). “A Numerical Refinement Operator based on Multi-instance Learning.” In: Proceedings of the 20th international conference on Inductive logic programming. ISBN:978-3-642-21294-9
- QUOTE: Due to the size of the search space, clauses are built in a greedy manner, with one reﬁnement after the other. A reﬁnement consists of the addition of one or several literals to the body of a clause according to the modes of a language bias declaration. The reﬁnement operator providing all specializations of a clause is denoted by [math]\rho(C)[/math].

### 2009

- (Lehmann & Haase, 2009) ⇒ Jens Lehmann, and Christoph Haase. (2009). “Ideal Downward Refinement in the EL Description Logic.” In: Proceedings of the 19th international conference on Inductive logic programming. ISBN:3-642-13839-X, 978-3-642-13839-3
- QUOTE: Many concept learning methods borrow ideas from Inductive Logic Programming including the use of reﬁnement operators. Properties like ideality, completeness, ﬁniteness, piopeiness, minimality and non—redundancy are used as theoretical criteria for the suitability of such operators. It has been shown in [12] that no ideal reﬁnement operator for DLs such as ALC, SHOIN, and SROIQ can exist (the two latter DLs are underlying OWL and OWL 2, respectively). In this article, an important gap in the the analysis of reﬁnement operator properties is closed by showing that ideal reﬁnement operators for the DL EL do exist, which in turn can lead to an advance in DL concept learning.

### 2008

- (Tamaddoni-Nezhad & Muggleton, 2008) ⇒ Alireza Tamaddoni-Nezhad, and Stephen Muggleton. (2008). “A Note on Refinement Operators for IE-Based ILP Systems.” In: Proceedings of the 18th international conference on Inductive Logic Programming. ISBN:978-3-540-85927-7 doi:10.1007/978-3-540-85928-4_23

### 2007a

- (Fredouille et al., 2007) ⇒ Daniel C. Fredouille, Christopher H. Bryant, Channa K. Jayawickreme, Steven Jupe, and Simon Topp. (2007). “An ILP Refinement Operator for Biological Grammar Learning.” In: Inductive Logic Programming. ISBN:978-3-540-73846-6 doi:10.1007/978-3-540-73847-3_24

### 2007b

- (Lehmann & Hitzler, 2007) ⇒ Jens Lehmann, and Pascal Hitzler. (2007). “A Refinement Operator based Learning Algorithm for the ALC Description Logic.” In: Proceedings of the 17th international conference on Inductive logic programming. ISBN:3-540-78468-3, 978-3-540-78468-5

### 2001

- (Gammie, 2001) ⇒ Peter Gammie (2001). http://www.cse.unsw.edu.au/~cs9417ml/MIS/doc/html/node3.html
- QUOTE: A refinement operator [math]\rho[/math] suggests a logically weaker plausible replacement to a hypothesis refuted by the diagnosis algorithm outlined in Section 2. Formally, [math]q[/math] is a refinement of [math]p[/math] if it satisfies the following two criteria:

- 1. [math]p \vdash q[/math], i.e. everything provable from [math]q[/math] is provable from [math]p[/math], or equivalently, [math]p[/math] is at least as general as [math]q[/math].
- 2. [math]size(p) \lt size(q)[/math] under some size metric. In logic programming terms, Shapiro uses the following:
- The [math]size[/math] of a sentence [math]p[/math], [math]size(p)[/math], is the number of symbol occurrences in [math]p[/math] (excluding punctuation symbols) minus the number of distinct variables occurring in [math]p[/math].

- Intuitively, building a monotonic size increase into the notion of refinement means that all refinements of [math]p[/math] are more specific/weaker than [math]p[/math], as it requires more things to be provable (in the case of adding a body goal) or more structure to be present in the query (if a function symbol is introduced, or two or more variables are unified). This exploits the intimate relationship between the syntax and semantics of logic programs.

- A refinement operator [math]\rho[/math] is then defined to be a set-valued function that maps a statement [math]p[/math] to a subset of its refinements, with some technical side-conditions.

Facts about "Refinement Operator"

Author | Tommaso Soru +, Edgard Marx +, Axel-Cyrille Ngonga Ngomo +, Erick Alphonse +, Tobias Girschick +, Fabian Buchwald +, Stefan Kramer +, Jens Lehmann +, Christoph Haase +, Alireza Tamaddoni-Nezhad +, Stephen Muggleton +, Daniel C. Fredouille +, Christopher H. Bryant +, Channa K. Jayawickreme +, Steven Jupe +, Simon Topp + and Pascal Hitzler + |

year | 2015 +, 2010 +, 2009 +, 2008 + and 2007 + |