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 ALC Refinement Operator;
    • an EL Refinement Operator,
  • 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):
  • Laplace Operator.
• 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: Definition 3 (Refinement Operator). Given a quasi-ordered space [math]\displaystyle{ (S,op) }[/math] an upward refinement operator [math]\displaystyle{ r }[/math] is a mapping from [math]\displaystyle{ S }[/math] to [math]\displaystyle{ 2^S }[/math] such that [math]\displaystyle{ \displaystyle \forall_{s \in S} : s' \in r(S) \Rightarrow op(s,s') }[/math]. [math]\displaystyle{ s' }[/math] is then called a generalization of [math]\displaystyle{ s }[/math].

    We define our refinement operator over the space [math]\displaystyle{ (\mathcal{P}, \preceq) }[/math]. First, we begin by ordering the elements of [math]\displaystyle{ \mathcal{P} }[/math] according to their score in ascending order, i.e., [math]\displaystyle{ \displaystyle\forall_{p_i,p_j \in \mathcal{P}},i \leq j \Rightarrow score(p_i) \leq score(p_j) }[/math]. Then, we can define our operator as follows:

    [math]\displaystyle{ \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]

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 refinement after the other. A refinement 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 refinement operator providing all specializations of a clause is denoted by [math]\displaystyle{ \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 refinement operators. Properties like ideality, completeness, finiteness, 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 refinement 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 refinement operator properties is closed by showing that ideal refinement 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]\displaystyle{ \rho }[/math] suggests a logically weaker plausible replacement to a hypothesis refuted by the diagnosis algorithm outlined in Section 2. Formally, [math]\displaystyle{ q }[/math] is a refinement of [math]\displaystyle{ p }[/math] if it satisfies the following two criteria:

1. [math]\displaystyle{ p \vdash q }[/math], i.e. everything provable from [math]\displaystyle{ q }[/math] is provable from [math]\displaystyle{ p }[/math], or equivalently, [math]\displaystyle{ p }[/math] is at least as general as [math]\displaystyle{ q }[/math].

2. [math]\displaystyle{ size(p) \lt size(q) }[/math] under some size metric. In logic programming terms, Shapiro uses the following:

The [math]\displaystyle{ size }[/math] of a sentence [math]\displaystyle{ p }[/math], [math]\displaystyle{ size(p) }[/math], is the number of symbol occurrences in [math]\displaystyle{ p }[/math] (excluding punctuation symbols) minus the number of distinct variables occurring in [math]\displaystyle{ p }[/math].

Intuitively, building a monotonic size increase into the notion of refinement means that all refinements of [math]\displaystyle{ p }[/math] are more specific/weaker than [math]\displaystyle{ 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]\displaystyle{ \rho }[/math] is then defined to be a set-valued function that maps a statement [math]\displaystyle{ p }[/math] to a subset of its refinements, with some technical side-conditions.

---