Description lattices#
The reader will find a more detailed presentation of the theory of description spaces in the seminal article [DBV+24].
Representation spaces#
A representation space is a structured family of predicates that can describe a subset of data through the predicates that characterize its boundary.
Definition
A representation space is an algebraic structure \(\langle D, P\rangle\) where:
\(D\) is the set of values of a given domain.
\(P\) is a set of monadic predicates on \(D\) with values in the Boolean set \(\mathbb{B}=\{\bot,\top\}\).
From \(D\) and \(P\), we define the pair of maps \(\langle \alpha_{D,P}, \beta_{D,P}\rangle\) between subsets of \(D\) and subsets of \(P\) as follows:
If the predicate space \(P\) is equipped with a subsumption relation \(\sqsubseteq_P\) that is compatible with conjunction, then \(\langle \alpha_{D,P}, \beta_{D,P}\rangle\) forms a Galois connection. In particular, whenever \(A \subseteq A'\), the predicate set describing \(A'\) is more specific than the one describing \(A\), i.e. \(\alpha_{D,P}(A')\sqsubseteq_P\alpha_{D,P}(A)\).
Convex representation spaces#
Definition
A convex representation space is a representation space \(\langle D, P\rangle\) such that \(\phi_{D,P}=\beta_{D,P}\circ\alpha_{D,P}\) is a convex operator, meaning that it satisfies the normalisation and anti-exchange properties.
The anti-exchange property captures the idea that convex closure behaves like a convex hull: adding a point outside a hull modifies it in a controlled way, rather than arbitrarily.
Description spaces#
In a convex representation space, each convex hull \(\phi_{D,P}(A)\) is determined by a unique basis \(B\), that is, \(\phi_{D,P}(A)=\phi_{D,P}(B)\). We focus on the extreme predicates in \(\alpha_{D,P}(A)\): these are the predicates that remain valid on the whole convex hull \(\phi_{D,P}(A)\) and describe its border.
Definition
Let \(\langle D, P\rangle\) be a convex representation space, and let \(\phi_{D,P}=\beta_{D,P}\circ\alpha_{D,P}\) be its convex operator on \(D\). For every \(A\subseteq D\), we define the set of border predicates of the convex hull of \(A\) by:
where \(\epsilon_{\phi_{P,D}}\) denotes the extreme-point operator of \(\phi_{P,D}\).
Definition
To handle degenerate cases, we also introduce predicates that state whether a value \(x\in D\) belongs to the convex hull \(\phi_{D,P}(A)\). Since \(\phi_{D,P}(A)\) has a unique basis of extreme points \(\epsilon_{\phi_{D,P}}(A)\), we define at most one additional predicate per convex hull.
Let \(\langle D, P\rangle\) be a representation space, and let \(\phi_{D,P}=\beta_{D,P}\circ\alpha_{D,P}\) be its closure operator on \(D\).
The hull-membership predicate associated with the convex hull of \(A\subseteq D\) is defined for \(x\in D\) by:
A description space is tied to a canonical convex representation space. It associates with each subset \(A\subseteq D\) a canonical description \(\delta_{D,P,H}(A)\) built from the predicates in \(\mbox{Borders}_{D,P}(A)\) and, when necessary, from a consistent set \(H\) of hull-membership predicates to handle degenerate cases.
Definition
Let \(\langle D, P\rangle\) be a canonical convex representation space, with \(\phi_{D,P}=\beta_{D,P}\circ\alpha_{D,P}\) its convex operator, and let \(H\) be a consistent set of hull-membership predicates.
The description space \(\langle D, P, H\rangle\) of \(\langle D, P\rangle\) induced by \(H\) defines two functions, \(\delta_{D,P,H}\) and \(\beta_{D,P,H}\). The function \(\delta_{D,P,H}\) is the convex hull description of \(\langle D, P\rangle\) induced by \(H\). The function \(\beta_{D,P,H}\) reconstructs the corresponding convex hull from that description.
A description space must support the construction of a hierarchy, or lattice, of convex hulls over the values of a given domain.
This framework can be used for many kinds of data domains, for example \(\mathbb{R}^n\), strings, or class parameters.