Janis Kalofolias

Esther Galbrun

Pauli Miettinen

From Sets of Good Redescriptions to Good Sets of Redescriptions

Keywords: Data mining, Redescription mining, Pattern selection, Maximum-entropy, Subjective interestingness

Redescription mining aims at finding pairs of queries over data variables that describe roughly the same set of observations. These redescriptions can be used to obtain different views on the same set of entities. So far, redescription mining methods have aimed at listing all redescriptions supported by the data. Such an approach can result in many redundant redescriptions and hinder the user's ability to understand the overall characteristics of the data.

In this work, we present an approach to identify and remove the redundant redescriptions, that is, an approach to move from a set of good redescriptions to a good set of redescriptions. We measure the redundancy of a redescription using a framework inspired by the concept of subjective interestingness based on maximum-entropy distributions as proposed by De Bie in 2011. Redescriptions, however, generate specific requirements on the framework, and our solution differs significantly from the existing ones. Notably, our approach can handle disjunctions and conjunctions in the queries, whereas the existing approaches are limited only to conjunctive queries. Our framework can also handle data with Boolean, nominal, or real-valued data, possibly containing missing values, making it applicable to a wide variety of data sets. Our experiments show that our framework can efficiently reduce the redundancy even on large data sets.

Introduction

Redescription mining is a data mining task that aims at finding alternative characterisations of (roughly) the same objects. The motivation behind this is simple and intuitive: if some objects can be described in alternative ways, then they form a particularly coherent group. Furthermore, identifying such alternative descriptions tells us something about the properties appearing in such synonymous characterisations.

Take for instance the case of areas of the globe, for which records of observed animal species and also climatic information are available. Areas that host particular species and share a particular climatic profile form a coherent group, closely related to the concept of an environmental niche in ecology. As another example, in medicine, identifying groups of patients who share similar profiles might help relate genetic traits, disease symptoms, and treatment outcomes. The same idea can also be of interest in other fields, including ethnography, sociology, and chemistry.

Like many other data mining tasks, redescription mining is subject to the issue of pattern explosion, wherein a large number of results are returned by the mining algorithm-many of them slight variations of one another. As a result, we face the challenge of identifying an interesting non-redundant subset, worth further inspection.

The problem we address in this paper is that of pattern selection. Considering a data set that consists of a pair of matrices over the same objects, and given a collection of redescriptions that has been mined from this data set, we want to select a subset of redescriptions that is informative and non-redundant. Note that we are not introducing any new pattern formalism nor any new algorithm for mining redescriptions. Instead, we focus on the problem of ranking and filtering redescriptions in post-processing.

One approach to evaluating the interestingness of patterns, which we adopt here, is to use them to construct a statistical model of the data. A pattern can be seen as an observation from the data and can be evaluated against the current model. If the current model already accounts for the observation, that is, the pattern does not provide any new information about the data, it is considered redundant and can be discarded. Otherwise, the pattern is deemed interesting and is integrated into the model, thereby increasing its quality.

We propose an iterative approach. At each step, the candidate redescriptions are evaluated against a model that incorporates the current knowledge available about the data, namely the information contained in the redescriptions selected so far. Using our proposed score, we can measure the novel information each candidate redescription contains with respect to the current state. We then rank these redescriptions and select the most informative one to be incorporated into the model. Next, the candidate scores are updated to reflect the new model and we proceed with selecting the best one. This process is iterated until no additional information can be incorporated into the model, that is, until only redundant candidate redescriptions are left.

Our modelling techniques rely on the maximum entropy distribution and the framework of subjective interestingness, as proposed by De Bie (2011). In brief, we maintain a maximum entropy distribution conditioned on all of the alreadyseen redescriptions to model what is already known, and consider redundant all redescriptions that have a high likelihood under this distribution. We emphasise, however, that our model differs from that of De Bie (2011) and subsequent work (e.g. [START_REF] Kontonasios | Maximum Entropy Models for Iteratively Identifying Subjectively Interesting Structure in Real-Valued Data[END_REF] in significant ways, as the patterns we are studying-namely redescriptions-are more intricate than the patterns studied in prior work. 1The approach presented here rests on two main lines of work. Redescription mining on the one hand provides us with a rich pattern language, while on the other hand maximum entropy modelling provides us with well-grounded selection principles. We cover the basics of these two fields in Section 2, while general related work is discussed in Section 6. Our main model is discussed in Section 3, and is extended to handle missing values in Section 4. We present our algorithms for calculating the model and ranking the redescriptions in Section 5. An empirical evaluation is provided in Section 7.

Background

In this section, we give the basic definitions of redescription mining and maximum entropy modelling. Further information on redescription mining can be found, for instance, from the work of [START_REF] Galbrun | Redescription Mining[END_REF]; maximum entropy modelling, especially as applicable to data analysis, is discussed by De Bie (2011).

Redescription mining

In the formulation of redescription mining considered here, the input data consist of entities with two sets of characterising variables, thus forming a data set with two sides. We generally refer to these two sides as the left-and right-hand sides, and represent them using two matrices D L and D R , respectively. The columns of these matrices correspond to the sets of variables V L and V R . The domains of the variables are denoted by V L and V R , respectively, and they can be either continuous or discrete. The rows of the matrices correspond to the entities. The set of entities characterised by the two sides is denoted by E, and so both matrices have |E| rows. The value of D(i, j) is the value of variable v j ∈ V for entity d i ∈ E.

Truth assignments are then defined over the variables by requiring them to take values within a subset of their domain. We denote these truth assignments using the notation [a ≤ v ≤ b], except for Boolean variables where the truth assignment [v = True] is denoted simply as v. These truth assignments and their negations can be combined into logical statements using the Boolean operators ∧ (and) and ∨ (or).

The output of redescription mining consists of a collection of query pairs, the redescriptions, of the form R = (q L , q R ), where the queries q L and q R are logical statements over the variables in D L and D R , respectively.

For instance, the following pair of queries q L = greater white-toothed shrew ∧ Egyptian mongoose q R = [15.6 ≤ t - 8 ≤ 19] ∧ [1.62 ≤ p 8 ≤ 7.44] ∧ [66.2 ≤ p 12 ≤ 137] ∨ [13.9 ≤ t ∼ 3 ≤ 14.3] constitutes a redescription. This redescription was extracted from the Bio data set, which we use in our experiments. This data set comes from the ecological domain and characterises geographic areas in terms of the fauna that inhabits them and of their climatic profile. More details about this data set can be found in Section 7. The left-hand side query is a simple conjunction of Boolean variables and states that both the greater white-toothed shrew and the Egyptian mongoose are present. The right-hand side query is more complex and requires the values of the temperatures of March (t ∼

3 ) and August (t - 8 ) as well as the precipitation of August (p 8 ) and December (p 12 ) to take value within the specified ranges.

This query language, combining Boolean and numerical variables into conjunctions and disjunctions, is at once rich enough to capture patterns that are more expressive than purely Boolean conjunctions, but still constrained enough that the queries remain interpretable and that we are able to devise algorithms to find them. Since we aim to evaluate the interestingness of the patterns by using them to build a statistical model of the data, we need to design a modelling approach that is able to accommodate this expressive query language. In other words, we need a flexible approach with strong modelling power.

The support of a query q is the subset of entities for which the query holds true, that is, supp(q) = {d i : q is true for d i ∈ D}. The support of a redescription R is the set of entities that satisfy both logical statements supp(R) = supp(q L ) ∩ supp(q R ). The set of variables over which q is expressed is denoted as vars(q).

In essence, a redescription provides alternative characterisations for a set of entities; the similarity of the support of the queries that constitute it is therefore a core property of a redescription, which we refer to as its accuracy. Following the established practice in the redescription mining literature (see, e.g. [START_REF] Ramakrishnan | Turning CARTwheels: an Alternating Algorithm for Mining Redescriptions[END_REF][START_REF] Parida | Redescription Mining: Structure Theory and Algorithms[END_REF]Galbrun and Miettinen, 2012a;Zinchenko, Galbrun and Miettinen, 2015;[START_REF] Mihelčić | InterSet: Interactive Redescription Set Exploration[END_REF][START_REF] Galbrun | Redescription Mining[END_REF], we measure the accuracy using the Jaccard coefficient: given a redescription R, its accuracy is the Jaccard coefficient of its support,

J(R) = J(q L , q R ) = |supp(q L ) ∩ supp(q R )| |supp(q L ) ∪ supp(q R )| .
Using the Jaccard coefficient to measure the accuracy comes with many known benefits (see, e.g. [START_REF] Galbrun | Redescription Mining[END_REF]. Accuracy, however, is a local feature of the redescription in that it informs on the quality of an individual redescription, but does not help in finding a good set of redescriptions. Therefore, we need to look at the variables and values at play in the logical statements of the redescriptions. We will use these logical statements to constrain a maximum entropy distribution over possible data sets, allowing us to evaluate the probability of observing a certain redescription given those we already know to be present.

Most interesting in a redescription is the association between the two queries, and the entities that satisfy both of them. For this reason, our main objective here is to model the conjunction of the two queries that make up a redescription and the intersection of their supports, that is, the support of the redescription. Henceforth, we will treat a redescription R = (q L , q R ) as the logical statement s = q L ∧ q R , with its associated support supp(s) = supp(q L ) ∩ supp(q R ) = supp(R), evaluated over the data set D resulting from the concatenation of D L and D R ; similarly, the variables in V L and V R are pooled together to form V . Thus, our data set D is a matrix with N = |V | columns and M = |E| rows. At first, we assume that the data set is complete. We will explain how our model can be extended to handle missing values in Section 4.

Note that our ranking procedure is applied in post-processing, given a set of redescriptions obtained with a mining algorithm. Our procedure is thus dependent on the ability of the mining algorithm to return a sufficiently diverse set of redescriptions, among which our algorithm will then identify the most interesting and non-redundant ones.

Maximum entropy modelling

Let P be a set of probability distributions over V. That is, for every p ∈ P and every x ∈ V, p(x) ≥ 0 and V p(x) dx = 1. The distribution p ∈ P is the maximum entropy distribution subject to the constraints {(f c , π c ) : c ∈ C} if it is the solution to the following program:

max p∈P - V p(x) log p(x) dx (1) subject to V p(x)f c (x) dx = π c for all c ∈ C. (2)
In the framework of this paper, the constraints (f c , π c ) encode our current knowledge of the data, obtained from the already-seen redescriptions (see Section 3). Before presenting our specific model, however, we will briefly discuss the general approach of finding the maximum-entropy distribution.

The objective function of maximum entropy is strictly concave and continuous. We can therefore use standard tools from constrained variational optimisation in order to obtain the solution

p λ (r) = 1 Z λc exp c∈C λ c f c (r) , (3)
where λ c are the Lagrange multipliers for the constraints and Z λc is the partition function

Z λc = V exp c∈C λ c f c (x) dx . (4)
The role of the latter is to ensure proper normalisation of the distribution p λ . Under the condition that the constraints of (2) are satisfiable, strong duality holds, and we can thus compute the Lagrange multipliers λ = (λ c ) c∈C by solving the convex dual of the problem in Equations ( 1) and ( 2

), min λc≥0, c∈C max p∈P - V p(x) log p(x) dx - c∈C λ c V p(x)f c (x) dx -π c .
(5)

Solving the corresponding Euler-Lagrange equation, the dual objective can be maximised with respect to p, which yields the new objective of the dual problem

q(λ) = log Z λ - c∈C λ c π c . (6)
The objective q(λ) of the dual problem is convex, which allows for the optimal vector of the Lagrange multipliers λ * to be computed as the points where the gradient of q vanishes. The gradient of q is

∂q ∂λ c = 1 Z λc V exp c∈C λ c f c (r) f c (r) dr -π c , (7)
and the points where it vanishes are the ones that satisfy the conditions

Ep [f c (r)] = π c for all c ∈ C , (8)
that is, exactly the constraints that were enforced in the original problem formulation (2).

Theory

We now introduce our probabilistic models for the data. First we explain how to model the values occurring within an arbitrary row while accounting for the presence of a given set of statements, using the maximum entropy principle. Then we explain how to represent an entire data set based on this row model, using a mixture model that comes in two variants.

Modelling rows

In this section, our aim is to identify the maximum entropy distribution over the values that a database row may assume while satisfying a set of constraints, each with a given probability.

In the following, we consider a database row to be an assignment of values to each variable of the data set. Let r ∈ V be a random vector of such value assignments, where

V = V 1 × • • • × V N is
the Cartesian product of the domains of the variables. Further let S be the set of constraints, where each constraint s ∈ S takes the form of a logical statement, which must be satisfied with a given validity probability π s ∈ [0, 1]. These statements encode prior knowledge on the specific row and are assumed to be satisfied by a nonempty set of distributions over V. Among those distributions, we want to identify the one with maximum entropy p M ROW (r | S), which we will simply denote as p ROW (r), when the set of constraints S and the model M are clear from the context. Since the constraints are logical statements, we can adapt the derivation of Section 2.2 by substituting the constraint function of Equation (2) with

f s (r) = χ s (r) , (9)
where χ s (r) is the characteristic function of statement s, that is, χ s (r) = 1 if s holds true on r and χ s (r) = 0 otherwise. As a result, the optimality conditions of Equation (8) now take the form

EM [χ s (r)] = π s for all s ∈ S , (10)
while the solution and partition functions of Equations ( 3) and (4) become, respectively,

p λ (r) = 1 Z λ exp s∈S λ s χ s (r) (11)
and

Z λ = V exp s∈S λ s χ s (r) dr . (12)
In practice, however, although the quantity in the exponent of ( 11) is trivial to compute for a given row r, the partition function Z λc is much more complex. Indeed, the integral of (4) runs over all the possible values that the random row r may assume. In addition, computing the integral itself is difficult, since the general formulation of the maximum entropy problem does not accept an analytical solution, making numerical approximation methods necessary (cf. [START_REF] Burden | Numerical Analysis[END_REF]. Numerical methods are also necessary in computing the Lagrange multipliers and require multiple evaluations of the value or the derivatives of the dual objective function of Equation ( 6). In the rest of this section we mitigate these issues by exploiting intrinsic properties of our models.

Factorising the distribution. In its general form, the integration in the partition function (12) runs over the entire domain V. However, each logical statement s only involves a small subset of variables vars(s) ⊆ V .

This observation allows for a simplification of the computation by aggregating the statements into groups, such that each group involves as few variables as possible and can be computed independently. When the variables involved in computing the statements of a group do not overlap with the variables involved in another group, we can split the sums within the exponents of Equations ( 11) and ( 12) into corresponding groups.

Formally, we define a partitioning K of the variables in V such that for all s ∈ S there exists a K ∈ K with vars(s) ⊆ K, and denote by S K = {s ∈ S : vars(s) ⊆ K} the subset of statements that only contain variables in K. Now the sets S K form a partitioning of S and we can split the sums over these partitions

exp s∈S λ s χ s (r) = K∈K exp s∈S K λ s χ s (r) .
The integral in the partition function can similarly be split into a product of sub-integrals, each over the domain V K of all variables in K. Thus, we obtain

p λ (r) = K∈K p λ K (r) , (13)
which is a product of sub-probabilities defined over independent subsets of the original variables

p λ K (r) = 1 Z K (λ) exp s∈S K λ s χ s (r) Z K (λ) = V K exp s∈S K λ s χ s (x) dx , (14)
v A v B v C v D v E v F s 1 s 2 s 3 s 4 s 5 K 1 K 2 K 3 v A v B v C v D v E v F s 1 s 2 s 3 s 4 s 5 s 6 s 6 K 1 K 2 s 1 = v A s 2 = v B ∧ v C s 3 = v A ∨ v B ∨ v C s 4 = [2 < v E ] s 5 = [20 < v D ]∨[2 < v E ] s 6 = v C ∨¬[v D < 30] v A , v B , v C ∈ {0, 1} v D ∈ [10, 50] v E ∈ [0, 5] v F ∈ {0, 1}
Figure 1. Clustering of the six data variables v A , . . . , v F of a row model with five logical statements s 1 , . . . , s 5 (top) and after the addition of a sixth statement s 6 (bottom).

and the normalisation can be performed per each Z K (λ) term. To maximise computational efficiency, we aim for the finest partitioning possible.

Example 1. Consider a data set over six variables, {v A , . . . , v F }, and a collection of five logical statements over these variables S = {s 1 , . . . , s 5 }, as shown in Figure 1 (right). In this case, the finest partitioning of the variables, so that all statements are completely contained within one cluster, consists of the 3 groups

K 1 = {v A , v B , v C }, K 2 = {v D , v E }, and K 3 = {v F }, as shown in Figure 1 (top left)
. Suppose that at this point the constraint 30] is added. To fulfil the containment requirement, we now need to merge K 1 and K 2 , resulting in the clustering shown in Figure 1 (bottom left).

s 6 = v C ∨ ¬[v D <
To further speed-up the computation, we can also perform a re-parametrisation (or factorisation) of the distribution, for instance, using the Junction Tree algorithm [START_REF] Jensen | Optimal Junction Trees[END_REF].

Quantising the domain. A further source of complexity in Equation ( 14) results from integrating over the domain of the variable set. Since the real-valued variables are constrained through the interval notation, we can quantise these variables into discrete bins aligned with these intervals, in order to reduce the integral into an equivalent summation.

We achieve this by consulting the truth table for the statements in S, to group together the regions of the domain where the same combination of statements are satisfied. Formally, for an arbitrary ordering s 1 , . . . , s σ of all statements in S, we define a truth vector (t 1 , . . . , t σ ) ∈ {0, 1} σ , assigning a value to the truth of each statement. Each such vector defines a region of the variable domain over which the truth of each statement matches the respective element of the truth vector

T t1•••tσ = {r ∈ V : χ si (r) = t i for all s i ∈ S} .
All these regions together form a partitioning of the domain, denoted as T . Note that unfeasible truth assignments correspond to empty regions and can be safely ignored. Using a similar subscript notation, we denote the combinations of Lagrange multipliers as

ζ t1•••tσ (λ) = λ 1 • t 1 + • • • + λ σ • t σ .
Table 1. Domain quantisation for the statements {s 1 , s 2 , s 3 } over the Boolean variables {v A , v B , v C } from K 1 . Statements truth table (left) and accumulated terms (right).

v A v B v C χs 1 χs 2 χs 3 T t 0 0 0 0 0 0 T 000 1 0 0 1 0 1 T 101 0 1 0 0 0 1 T 001 1 1 0 1 0 1 T 101 0 0 1 0 0 1 T 001 1 0 1 1 0 1 T 101 0 1 1 0 1 1 T 011 1 1 1 1 1 1 T 111 T t |T t | ζ t T 000 1 0 T 001 2 λ 3 T 011 1 λ 2 + λ 3 T 101 3 λ 1 + λ 3 T 111 1 λ 1 + λ 2 + λ 3
Table 2. Domain quantisation for the statements {s 4 , s 5 } over the real-valued variables {v D , v E } from K 2 . From statement truths to region probabilities

P (Q) := Q p(x)dx. Q v D v E χs 4 χs 5 T t |T t | ζ t p(x) P (Q) Q 1 [10, 20] [0, 2] 0 0 T 00 10 • 2 0 1/40 0.5 Q 2 [20, 50] [0, 2] 0 1 T 01 30 • 2 λ 5 1/(40 • 15) 0.1 Q 3 [10, 20] [2, 5] 1 1 T 11 10 • 3 + 30 • 3 λ 4 + λ 5 2/(40 • 15) 0.1 Q 4 [20, 50] [2, 5] 1 1 0.3
We can now express Equations ( 11) and ( 12) as

p λ (r) = 1 Z(λ) exp ζ τ (r) (λ) , (15)
Z(λ) = Tt∈T Tt exp (ζ t (λ)) dx = Tt∈T |T t (λ)| exp (ζ t (λ)) , (16)
where τ (r) = (χ s1 (r), . . . , χ sσ (r)) is the truth vector of the statements computed at the value assignment r.

Example 2. Going back to Example 1, consider the computation of the factor associated to group K 1 = {v A , v B , v C }, involving statements s 1 , s 2 and s 3 (see Figure 1). The truth table of these statements is shown in Table 1 (left). The terms can be gathered based on the satisfiability of the constraints in the just 5 different combinations of Table 1 (right). The partition function of Equation ( 16) can then be written with one term per combination, as

Z K1 (λ) = 1 • e ζ000 + 2 • e ζ001 + 1 • e ζ011 + 3 • e ζ101 + 1 • e ζ111 .
In this small example, the number of terms has been reduced from 2 3 = 8 to 5.

As the number of variables rises, this simplification can become more dramatic.

In the more general case involving non-Boolean variables, the boundaries delimiting the regions of the domain can be easily identified from the thresholds of the intervals.

Example 3. Consider now the computation of the factor associated to group K 2 = {v D , v E }, involving the statements s 4 and s 5 of Figure 1, respectively;

v E v D s 4 s 5 Q 1 Q 2 Q 3 Q 4 10 20 50 0 2 5 Figure 2. Regions of the domains of v D and v E .
we assume satisfiability probabilities π s4 = 0.4 and π s5 = 0.5, and use domains

v D ∈ [10, 50] and v E ∈ [0, 5]. The literals involved are [2 < v E ] and [20 < v D ]
, so the relevant thresholds are (0, 2, 5) for v E and (10, 20, 50) for v D , respectively. The resulting quantisation is depicted in Figure 2, where each of the four blocks represents one region of the domain, denoted as Q 1 , . . . , Q 4 . For each region, the satisfiabilities of both statements are shown in Table 2. This combination determines the partition T t to which the region is assigned. The measure |T t | of a partition is simply the sum of the areas of the regions it consists of. Using these partitions and the corresponding combinations of Lagrange multipliers, we can write the partition function as From the optimality conditions of Equation ( 8) it follows that 120 e λ4+λ5 /Z K2 = π s4 = 0.4 60 e λ5 + 120 e λ4+λ5 /Z K2 = π s5 = 0.5 , which can be solved analytically to obtain e λ * 4 = 2, e λ * 5 = 1/15, and Z K2 = 40, giving the probability measure

Z K2 (λ) =
p λ * (r) = 1/40 • 2 χs 4 (r) • 1/15 χs 5 (r) .
The case of certain satisfiability. A special case which allows the problem to be simplified consists of sets of statements such that all the statements are certain (i.e. π s = 1). Indeed, we can show that the maximum entropy distribution incorporating a set of statements S all with π s = 1 is

p(r) = 1/Z if r satisfies all s ∈ S 0 otherwise , (17)
where Z = |T 1 | is the measure of the subset T 1 , which consists of the regions where all the statements in S are satisfied.

Modelling a data set

Having presented our row model in Section 3.1, we now proceed to describe the means to assemble several such row models into a model for an entire data set.

Our database models take as input an original data set D and a collection of logical statements S mined from this data set. We consider the data set as consisting of multiple entities, each encoded as a database row. In the development of our models we assume that these entities are independent, and therefore the order of the rows within the database can be disregarded. On the other hand, we do not assume that these entities are identically distributed and we allow for a different subset of statements to apply as prior knowledge on different entities. In other words, we allow each entity to follow a local distribution, that may differ from that of the other entities. Each of these distributions corresponds to a row model constrained with a particular subset of statements. Thus, we compute the overall probability for the data set by combining these local distributions.

Formally, let d i be the values observed in the data set D on the i-th row and r i the corresponding random variable, both taking values over the domain of the row values V. We denote as κ q the event that a statement q is satisfied on a data row d. One of our goals is to make a decision about the validity of the event, a decision that we represent by the function φ(q, d). At this point, knowing d deterministically defines the outcome, which matches the characteristic function of the statement on d, that is, φ(q, d) = χ q (d) .

(18)

We denote as S i the subset of statements to be applied to the i-th row model as constraints (S i ⊂ S). This subset contains those statements from S that are satisfied on the observed row d i , formally defined as

S i := s ∈ S : φi (s, d i ) = 1 . (19)
Note that this formulation will later allow us to extend inference for the case of missing values in Section 4, making the usefulness of the φ function more obvious.

Using the row model introduced in the previous section, henceforth denoted by p ROW , the probability of the row values r i can now be defined as

P (r i | D, S) = P (r i | d i , S) = p ROW (r i | S i ) . ( 20
)
Given the row probabilities, we now aim to combine them into a probability over all possible values of a data set.

A naïve approach that satisfies the assumption that rows follow a local distribution would be to model the data as a bag-of-rows, resulting in a database probability that degenerates into a product of row probabilities. However, this imposes the very strict assumption that all rows are independent and has the major practical drawback that the final probability depends too much on the individual probability of each row. Consider, for instance, two queries q 1 and q 2 with the same validities on all but one row, on which q 1 is twice as likely as q 2 . Under the bag-of-rows model the data set probability of q 1 is double that of q 2 . Instead, our models compute the total probability as a weighted average of the probabilities obtained from the relevant row models. We present two variants for the overall model, which differ in the entities that are considered relevant for computing the overall probability. The first model variant considers all entities in the data set. In other words, it takes into account all the row models, and we therefore refer to it as the MEALL model. The second model variant, which we call the MEBLK model, only considers the entities containing the query statement, that is, it only takes into account the row models associated to entities that satisfy the statement being evaluated.

Intuitively, evaluating the occurrence probability of a statement can be thought of as first selecting a relevant entity, then computing the probability that the statement occurs on that entity. The entity must be selected with a probability that reflects its representativity in the data set, which can motivate the use of a non-uniform entity-selecting distribution in certain cases. For instance, in a data set where the entities correspond to different geographic areas, recording, for example, species occurrences or voting outcomes, it might make sense to weight entities based on the size of the region. Likewise, with entities representing time spans of varying duration, one might want to select them with probabilities proportional to the time they span. However, unless more information is available, the uniform distribution over the relevant entities constitutes an obvious choice of entity-selecting distribution for this purpose, which we adopt here. This evaluation procedure can be statistically formalised as a mixture model, where the mixture coefficient determines the probability of selecting a particular entity and thus its associated row model. The graphical representation of both MEALL and MEBLK models is presented in Figure 3 (excluding the elements in blue).

Each of the M plates represents a variable r i depending on S and d i through S i , as explained in Equation ( 19). The mixing coefficient ρ acts as a prior probability over the row indices: it formally specifies which row models should be mixed together to obtain the final distribution over the values of r, a single row summarising the entire data set. To enforce the selection behaviour r = r ρ , the row selecting function can be expressed as

P (r | r 1 , . . . , r M , ρ) := δ (r -r ρ ) , (21)
where δ (•) is the Dirac delta function. 2 The row prior ρ is the uniform distribution over the row indices. For a fixed row vector r, the satisfiability of a statement q can be asserted deterministically, and we have

P (κ q | q, r) = χ q (r) , (22)
where κ q is the event that statement q is satisfied by the value assignment r.

S (j-1) i S (j+1) i d i S (j) i S r i ρ r κ q q φi M Legend q Query statement d i i-
P (κ q | q, D, S) = M ρ=1 P (ρ) V,V1,...,V M P (r | r 1 , . . . , r M , ρ) × P (κ q | q, r) × M i=1 P (r i | D, S) dr dr 1 • • • dr M , (23)
which can be simplified by substituting the specific distributions to

p ALL (κ q | q, D, S) = 1 M M i=1 p ROW (κ q | q, S i ) , (24)
with p ROW (κ q | q, S i ) := E [χ q (r i ) | S i ] being the probability that the query state- ment q is satisfied on row r i . The quantity in Equation ( 24) is essentially an average over all the probabilities assigned by the rows. If we change the row prior distribution to be uniform over the rows which support the query statement q exclusively,

P (ρ | d 1 , . . . , d M , q) := φi (q, d ρ ) M i=1 φi (q, d i ) , (25)
we obtain the MEBLK model, represented by the additional dotted dependencies in Figure 3.

The key difference between our two models, MEALL and MEBLK, lies in the different subsets of entities considered when evaluating a query statement, which manifests in the use of a different mixing coefficient ρ.

In concrete terms, MEALL evaluates the probability of the query statement being satisfied in the data set overall, while MEBLK evaluates the probability of the query statement being satisfied on the rows where it was observed to hold in the original data set. As a result, MEALL possesses the potentially useful property that the occurrence probability of a statement and that of its negation sum to unity, p ALL (κ q | q, •) = 1 -p ALL (κ ¬q | q, •), which does not generally hold under MEBLK. On the other hand, MEBLK offers a more intuitive interpretation of the satisfiability probability, in accordance with the framework of De Bie (2011). Also, once a statement has been incorporated into MEBLK, the query probability of that same statement is certain. That is, if the query statement has been previously added to the model, under MEBLK it will be assigned an occurrence probability of one and deemed unsurprising.

In addition, MEALL is better suited to comparing queries without penalising support size, while MEBLK favours greater support sizes. As a simple example illustrating this effect, consider three Boolean conjunctive statements s, q 1 , and q 2 such that supp(q 1 ) > supp(q 2 ) and s is contained into both q 1 and q 2 . Imagine that s has been previously incorporated into the model and we now want to evaluate q 1 and q 2 . MEALL assigns the same occurrence probability to both statements, whereas MEBLK favours the one with the larger support as more surprising.

Finally, MEBLK yields qualitatively better results as well as generally lower computational complexity, as evidenced by the experiments of Section 7.

Handling Missing Values

Data sets are oftentimes incomplete, in the sense that the values for some entries are indicated as missing. In this section, we explain how our models are extended to take into account the presence of missing values in the data sets.

First, note that in the case of nominal variables, a naive way to handle missing values is to consider them as an extra category. By adopting such an approach, our model as presented so far can already be used to handle missing values. An obvious downside of this approach, however, is that it cannot be applied to real-valued variables. Another and more crucial downside is that using a distinct but deterministic value does not capture the true interpretation of a missing value: the absence of information. This absence has to be accounted for probabilistically, reflecting the implied uncertainty. In this section, we explain how we extend our model to do just that.

Inferring statement satisfiability

A key component of computing the model of Section 3.2 is the ability to evaluate the satisfiability of a statement on a specific row of the data set. For rows containing no missing values, the probability of this event equals the characteristic function of the statement, as stated in Equation ( 22). If, however, a row in the database contains entries with missing values, this is no longer true. Instead, a verdict can only be made probabilistically, using the known part as observations and inferring the missing one from the beliefs dictated by the model.

Recall that d denotes the N -dimensional vector containing the values of a data set row. Some entries in this vector might be missing, and it is helpful to distinguish the missing values from the known ones. Hence, we overload the notation and let d = (d k , r µ ), where d k is the vector of values for the known variables and r µ is the random variable that corresponds to the missing values. In other words, if we use µ ⊆ {1, . . . , N } to index the variables whose value is missing, we have r µ = (r i ) i∈µ taking values in the domain V µ = Ś i∈µ V i . In this section, we are interested in the event that a given statement q is satisfied on a random row r sampled according to probability p M , in the presence of evidence from a database row d. We denote this event as κ q , and write the associated probability as

P (κ q | q, d, M) = EM [χ q (r) | d] = EM [χ q (r µ ) | d k ] = Vµ χ q ((d k , r µ )) p M ((d k , r µ )) dr µ , (26)
where from now on we omit the implied dependency on the model M.

Note that the probability is conditioned on both the model and the statement to emphasise that we are only interested in whether or not the statement holds true, rather than in the model prior or the choice of the statement itself.

In the case of fully known data d = (d k , ∅), as expected, this probability simplifies into the characteristic function

P (κ q | q, d) = χ q (d k ) . ( 27
)
Using Equation ( 17), the probability density assigned to r can be written as

p M (r) = 1 Z s∈S χ s (r), (28)
where the product runs over the characteristic functions χ s (r) of all constraint statements that are embedded in the model. Then, to compute the satisfiability probability of statement q over row d = (d k , r µ ), we take the expectation over the random part r µ . Expressing the model probability as per Equation (28) yields

P (κ q | q, d) = 1 Z Vµ χ q ((d k , r µ )) s∈S χ s ((d k , r µ )) dr µ . ( 29
)
As in Section 3.1, we can use domain quantisation to compute the integrals in Equation ( 29) more efficiently. In other words, we exploit the fact that the statements in S ∪ {q} partition the domain into regions within which the probabilistic density is constant.

Given the statements in S and a row (d k , r µ ), we consider the regions of the domain V that at once contain the known values d k and satisfy the statements in S. We denote the size of these regions by w S ((d k , r µ )). Notice that w S∪{q} (•) bounds both w S (•) and w {q} (•) from below. We can now rewrite Equation (29) as

P (κ q | q, d) = 1 Z w S∪{q} (d k ) . (30
= [v D < 20] ∨ [3 < v E ].
Our task is to assess the probability that the query statement q = [30

< v D ] ∨ [3 < v E ] is
satisfied on the data value combinations x 1 , x 2 , and x 3 listed on the right-hand side of Figure 4. Each value combination consists of a pair of values, one for

v E v D q s Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 10 20 30 50 0 3 5 x 2 x 1 s = [v D < 20] ∨ [3 < v E ] q = [30 < v D ] ∨ [3 < v E ]
x 1

x 2 x 3 (15, 4) (∅, 1) (∅, ∅) When computing the satisfiability probability for fully known value combinations only one region per combination needs to be considered: the region where the corresponding data point lies. Hence, for the complete data value x 1 we only need to consult region Q 4 . For the data value x 2 , the set of regions {Q 1 , Q 2 , Q 3 } must be consulted. Since both of its entries are missing, the entire domain must be consulted, when computing the satisfiability probability of x 3 .

w {s} (x) 30

Selecting constraining statements

The presence of missing values introduces uncertainty when evaluating whether a statement holds on particular data row, and therefore we need to redefine the decision function φ. In fact, we can no longer use the characteristic functions to select the subset of statements that constrain the model associated to a given data row, as in Equations ( 18) and ( 19).

Instead, for each data set row d i and its associated set of constraining statements S i , we decide whether statement s or its complement is satisfied on the row depending which of these two events is more likely. Then, if the statement is more likely to be satisfied than its complement, we embed it in the row model, associated to a certain probability π s = 1. Essentially, selecting the model constraints in this way corresponds to employing the maximum likelihood criterion in order to decide between the complementary events "s is satisfied on d i " and "¬ s is satisfied on d i ".

To avoid dependency on the partition function Z, we base the decision on the likelihood ratio between the occurrence of the statement and the occurrence of its complement, defined as

lr(s, d i , S i ) := P (κ s | s, d i , S i ) P (κ ¬ s | s, d i , S i ) = w Si∪{s} (d i ) w S (d i ) -w Si∪{s} (d i ) , (31)
where the last equality uses the formula for the probabilities introduced in Equation ( 30), as well as the fact that

P (κ s | s, d i , S i ) = 1 -P (κ ¬ s | s, d i , S i ).
Finally, we define φ to be the function that returns a hard decision based on the likelihoods ratio between the events κ s and ¬ κ s , φ(s, d i , S i ) := 1 if lr(s, d i , S i ) > 1, and 0 otherwise ,

which we use as a replacement for the characteristic function χ s (d) for selecting the constraining statements.

Notice that the model is built by incorporating statements iteratively. Hence, when considering whether to embed a statement s, the decision relies on the likelihood ratio computed based on the statements previously added into the model. To reflect this, we consider the set of constraints to be ordered, making it effectively a sequence S = (s 1 , . . . , s n ). Let us denote S (j) i the set of constraints applied on the i-th row at stage j. It can be defined recursively as follows

S (0) i := ∅ , S (j+1) i := S (j) i ∪ {s j } if φ(s j , d i , S (j)
i ) = 1 and S (j) i otherwise , because a constraint's satisfiability probability can only increase once the constraint has been added to the model.

The extended models are depicted in the graphical model of Figure 3 (including the elements in blue).

Algorithms

The models described in Section 3 can be used for different tasks, such as generating synthetic data sets and ranking patterns. We focus on the latter, which in turn involves two main operations: (i) training the model by incorporating new information in the form of patterns and (ii) querying the model, i.e. evaluating the satisfiability probability for a pattern. In this section, we present the algorithmic procedures for carrying out these two main operations in practice.

Recall that the patterns considered here consist of logical statements (redescriptions) and their supporting rows.

Training the model

As explained in the previous section, our models are mixtures of row models. Each of the row models is maintained in a factorised form where different factors involve disjoint sets of variables that do not interact in any statements, so as to allow independent computations. In addition, any given factor is shared by only a subset of the row models.

Our models are maintained as a set of factors F. Each factor f contains a set of statements S f and applies to a subset of rows I f . Accordingly, it is represented as the pair f = (S f , I f ). Overloading the notation, we denote by vars(f ) the set of data variables associated with f , that is, vars(f ) = s∈S f vars(s). For any given factor f , vars(f ) and I f define a tile in the data set, and is the set of all factors which overlap with a statement s and contain row i in their tile. Note that factor tiles do not overlap, due to the way they are constructed. For any given statement s, vars(s) and supp(s) also define a tile in the data set.

J i = {f ∈ F : vars(f ) ∩ vars(s) = ∅, i ∈ I f } (33) Algorithm 1: TrainModel input : model F , new statement s output : updated model F 1 J ← {J i : i ∈ supp(s)} ; // See Equation (33) 2 foreach J ∈ J do 3 I J ← f ∈J I f ; // Collect cluster rows 4 F ← F ∪ {s} ∪ f ∈J S f , I J ; // Add new factor 5 foreach f ∈ J do // Update overlapping factors 6 I f ← I f \ I J ; // Update rows 7 if I f = ∅ then 8 F ← F \ ∪{f }; // Delete 9 return F ; f 1 f 2 s vars(s) supp(s) vars(f 1 ) vars(f 2 ) I 1 I 2 N M f 1 f m3 f m2 f m1 f n
Training the model entails incrementally incorporating new statements into it. At each step, the task of the main training procedure is to update the model factors to incorporate the newly appended statement, while preventing factors from overlapping, so that their independence is preserved.

The pseudo-code for this procedure, TrainModel, is presented in Algorithm 1, and works as follows. When adding a new statement s to the model, we form the collection J of the sets of existing factors that overlap with s as per Equation (33) (line 1). Then, for each cluster J we create a new factor and add it to the model (line 4). The new factor applies exactly to the rows of the cluster (line 3) and contains all statements from the existing overlapping factors, in addition to s. We also update the set of rows to which the existing overlapping factors apply (line 6), deleting the factor altogether if it no longer applies to any row (line 8).

In the example shown in Figure 5, the model contains two factors, f 1 and f 2 . A new statement s is to be added, triggering the creation of several new factors. The factors f m1 , f m3 and f m2 are created by merging the rows where s overlaps respectively with f 1 , with f 2 , and with both, while factor f n is created for the rows that did not overlap with either (corresponding in Algorithm 1 to the case

Algorithm 2: QueryModelRow input : model F , statement s output : probability p ROW (s | D; F ) 1 Fs ← {f ∈ F : vars(f ) ∩ vars(s) = ∅}; 2 (w, v) ← Quantisation(s, Fs); 3 Zs ← i w i ; 4 p ← (v ⊗ w)/Zs ;
// ⊗ is the element-wise product 5 p ← MarginaliseAndNormalise(s, Fs, p); 6 return p; of an empty row cluster J = ∅). The updated f 1 remains, although it now covers fewer rows, whereas f 2 has been deleted.

Note that the type of the domain of the variables only affects TrainModel implicitly, through the satisfiability assessment χ s (•) of the newly appended statement s over the data set rows.

Querying the model

We now turn to the procedure that allows us to query a model. That is, given a model that has been trained as explained above, the original data set and a pattern extracted from the data set, the aim is to evaluate the satisfiability probability of the pattern.

The main building block in computing this probability is the evaluation of the satisfiability probabilities over single rows, essentially the probabilities predicted by the row models.

Querying a row model. Each row model is parameterised by the subsets of statements that occur on the corresponding data row. The satisfiability probability p ROW (s | D; F) of a statement for a given row model is computed by QueryModelRow as shown in Algorithm 2 and works as follows.

At first, we collect in F s the factors of the model that share variables with statement s. Next, the domain of the variables can be partitioned into regions over which the value of the characteristic function of s is constant, by syntactically parsing the statement and collecting all the involved thresholds (cf. Section 3.1). Since, by construction, the value of the characteristic function of s is the same in all points of a region, we can compactly represent the result of this quantisation by a pair of vectors (w, v), where w i measures the area of region i, and v i indicates whether s is satisfied on that region (line 2). Using this information, we are able to compute the probabilities for the different regions satisfying the statement (lines 3-4). Finally, the probability of each region of the domain is appropriately re-weighted with respect to the different factors in F s (line 5). More specifically, the statement s together with the subset F s form a Junction Tree [START_REF] Barber | Bayesian Reasoning and Machine Learning[END_REF], and we may therefore employ the Message Passing steps of the Junction tree algorithm to efficiently re-scale the initial probabilities. In this way, the effect of each overlapping factor is taken into account, while the corresponding constraints are respected, to finally yield the probability of statement s.

Note that the complexity of the querying procedure is dominated by the computation of the partition function (lines 2-3) and is exponential with respect to the number of variables involved. This computation yields vectors w and v of size exponential with respect to the number of variables appearing in the model F and statement s. Indeed, in the case of Boolean variables, the problem of computing the partition function Z s (line 3) can be trivially reduced to the #SAT problem (counting the number of satisfying assignments of a Boolean expression) and vice-versa. Since the latter is a known #P-complete problem, so is the former. Additionally, Boolean variables constitute a subset of the query language that we support, so our problem is at least #P-hard. Furthermore, it can be shown that querying the maximum entropy probability of a statement is PP-hard [START_REF] Tatti | Computational complexity of queries based on itemsets[END_REF], even for queries without disjunctions, so that in general, approximations of the partition function are also intractable. Interestingly, while an exact evaluation would still need an exponential evaluation time, the partition function could be approximated more efficiently in the case of largely uneven quantisations of the variable domains. Such an approximation scheme could evaluate the validity on the domain partitions, starting from the largest ones and progressively tightening an upper and lower bound on the partition function value, until a sufficiently tight interval is obtained.

Putting the rows together. Now that we know how to compute the probabilities for individual rows, we need to combine them together. The two models, MEBLK and MEALL, offer two alternatives for doing so. The overall probability returned by MEALL is simply the average of p ROW (s | D; F i ) over all rows i in the data set, while MEBLK only averages over rows that satisfy the statement under evaluation, that is, over supp(s).

A ranking scheme

Combining the two main operations of training and evaluation explained above, the procedure for ranking patterns is presented in Algorithm 3.

This procedure takes as input a data set and a collection of statements, with one of them designated to initialise the model training (line 1). This method then iteratively constructs a ranking of all the statements. In each step, the model is queried to identify the statement with lowest predicted probability (line 4), which is essentially the statement whose observation is most surprising at that point. This statement is incorporated into the model (line 5), appended to the list of results and removed from the set of candidates (lines 6 and 7). The procedure iterates until all statements have been ranked.

Related Work

Redescription mining. Redescription mining was introduced by [START_REF] Ramakrishnan | Turning CARTwheels: an Alternating Algorithm for Mining Redescriptions[END_REF] for Boolean data. Later, [START_REF] Zaki | Reasoning About Sets Using Redescription Mining[END_REF] and [START_REF] Parida | Redescription Mining: Structure Theory and Algorithms[END_REF] further developed the theory of Boolean redescription mining, Galbrun and Miettinen (2012a) extended it to real-valued data, and [START_REF] Galbrun | Finding Relational Redescriptions[END_REF] studied redescription mining in relational data.

Various algorithms have been proposed for mining the redescriptions. These can be divided into methods based on decision-tree induction [START_REF] Ramakrishnan | Turning CARTwheels: an Alternating Algorithm for Mining Redescriptions[END_REF]Zinchenko et al., 2015) and methods that grow the queries using a greedy heuristic [START_REF] Gallo | Finding Subgroups having Several Descriptions: Algorithms for Redescription Mining[END_REF]Galbrun and Miettinen, 2012a) (see also [START_REF] Galbrun | Redescription Mining[END_REF]. In addition, some methods have also been proposed to visualise and interact with the redescriptions [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions[END_REF][START_REF] Galbrun | Interactive Redescription Mining[END_REF][START_REF] Mihelčić | InterSet: Interactive Redescription Set Exploration[END_REF] Redescription mining is related to rule mining techniques that aim at discovering association rules [START_REF] Agrawal | Fast Algorithms for Mining Association Rules in Large Databases[END_REF] or subgroups [START_REF] Novak | Supervised Descriptive Rule Discovery: A Unifying Survey of Contrast Set, Emerging Pattern and Subgroup Mining[END_REF], for instance, and to classification and clustering techniques including subspace clustering [START_REF] Kröger | Subspace Clustering Techniques[END_REF][START_REF] Agrawal | Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[END_REF] and multi-view clustering [START_REF] Bickel | Multi-View Clustering[END_REF], among others. However, its goal of finding descriptive, interpretable patterns across several data sets is a distinguishing feature.

Maximum entropy models. The maximum entropy principle, formalised by [START_REF] Jaynes | Probability Theory: The Logic of Science[END_REF] and based on his earlier work [START_REF] Jaynes | On the rationale of maximum-entropy methods[END_REF], states that the distribution that has the maximum entropy, subject to given constraints, does not add any bias beyond what is assumed in these constraints.

It is a versatile principle which has been applied from ecological modelling [START_REF] Phillips | Maximum Entropy Modeling of Species Geographic Distributions[END_REF] to natural language processing [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF], and has been used to construct a condensed representation of the data set to be used for query approximation [START_REF] Mannila | Prediction with Local Patterns Using Crossentropy[END_REF][START_REF] Pavlov | Beyond independence: Probabilistic models for query approximation on binary transaction data[END_REF] or to compute degrees of belief [START_REF] Grove | Random worlds and maximum entropy[END_REF], to name but a few examples.

De Bie (2011) proposed to use maximum entropy models to evaluate the subjective interestingness of patterns and in the present work we follow his general idea. In another line of work, [START_REF] Tatti | Comparing apples and oranges[END_REF] proposed an approach based on maximum entropy and Kullback-Leibler divergence for comparing sets of noisy tiles mined from Boolean data sets and a maximum entropy model to iteratively discover biclusters over multiple related data sets was later presented [START_REF] Wu | Uncovering the plot: detecting surprising coalitions of entities in multi-relational schemas[END_REF].

Related modelling approaches include the use of Markov Random Fields [START_REF] Wang | Summarizing Itemset Patterns Using Probabilistic Models[END_REF] and the minimum description length (MDL) principle [START_REF] Vreeken | KRIMP: Mining itemsets that compress[END_REF][START_REF] Van Leeuwen | Association discovery in two-view data[END_REF], but do not offer a similar flexibility and modelling power to accommodate an expressive query language.

Similarly to most existing approaches [START_REF] Jaroszewicz | Pruning Redundant Association Rules using Maximum Entropy Principle[END_REF][START_REF] Tatti | Maximum entropy based significance of itemsets[END_REF], we apply ranking and filtering as a post-processing, meaning that we require as an input a collection of candidate patterns. [START_REF] Mampaey | Summarizing Data Succinctly with the Most Informative Itemsets[END_REF] proposed a method for finding interesting itemsets which mines candidates on the fly.

Pattern-based maximum entropy models. De Bie (2011) proposed a maxi-mum entropy model to identify interesting tiles in Boolean data sets while taking into account assumptions on the expected row and column sums, that is, with prior information given as the parameters of the Rasch model [START_REF] Rasch | Probabilistic models for some intelligence and achievement tests[END_REF]. [START_REF] Kontonasios | Maximum Entropy Modelling for Assessing Results on Real-Valued Data[END_REF] extended this approach to real valued data, with prior information taking the form of means, variances and histograms for the rows and columns. An iterative ranking scheme [START_REF] Kontonasios | Maximum Entropy Models for Iteratively Identifying Subjectively Interesting Structure in Real-Valued Data[END_REF], like ours, was then derived from this static model, which was also further extended to increasingly complex priors and pattern types [START_REF] Kontonasios | Formalizing Complex Prior Information to Quantify Subjective Interestingness of Frequent Pattern Sets[END_REF][START_REF] Kontonasios | Subjectively interesting alternative clusterings[END_REF].

Concurrently, [START_REF] Mampaey | Tell Me What I Need To Know: Succinctly Summarizing Data with Itemsets[END_REF] presented a maximum entropy model, named MTV, for iteratively mining interesting itemsets from a Boolean data set, using as prior knowledge the frequencies of individual items.

The most obvious difference between these models is on the type of prior information and patterns that they handle. Some of these works (e.g. De Bie, 2011; [START_REF] Mampaey | Tell Me What I Need To Know: Succinctly Summarizing Data with Itemsets[END_REF] are limited to binary tiles (or itemsets). These can be represented as monotone, conjunctive Boolean queries, and comprise only a subset of the patterns we can handle.

The method of [START_REF] Kontonasios | Maximum Entropy Modelling for Assessing Results on Real-Valued Data[END_REF] handles numerical data, like ours, but it deals with tile-like blocks. That is, their patterns are defined by specifying row and column indices, then looking at the distribution of values. Our patterns, redescriptions, are instead defined by specifying value ranges for some variables, then selecting the rows which satisfy these conditions. Our domain quantisation approach shares similarities with the maintenance of tiles histograms. We start with a coarse histogram and progressively adjust the bins based on the thresholds appearing in the predicates of the constraining statements.

To the best of our knowledge, we are the first to deal with arbitrary logical patterns, including disjunctions and negations, beyond the typical conjunctions.

A further distinction is between approaches which model rows of the data set individually [START_REF] Tatti | Maximum entropy based significance of itemsets[END_REF][START_REF] Mampaey | Tell Me What I Need To Know: Succinctly Summarizing Data with Itemsets[END_REF][START_REF] Mampaey | Summarizing Data Succinctly with the Most Informative Itemsets[END_REF] versus those which consider the data set as a whole [START_REF] De Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF]. The MTV model corresponds to a special case of our row model (see Section 3.1) for non-certain validities. We enforce each pattern on the relevant subset of entities of the data set, whereas in their model all patterns are applied on the same, single row. In other words, they assume that the entities of the data set are identically distributed. In this respect, our approach is similar to that of De Bie (2011), which assumes that the distribution of tiles might differ from one another.

Another important difference with the MTV model is that we do not incorporate the absence of a pattern as information into either of our models. This is one more reason why the information contained in our models deviates from simple pattern frequencies.

Despite the similarities between our models and the original model of De Bie (2011), there is no straightforward way to compare them. In particular, De Bie (2011) employs an information-content criterion that cannot be transferred to the case of redescriptions, like other works in the literature [START_REF] Kontonasios | Maximum Entropy Modelling for Assessing Results on Real-Valued Data[END_REF][START_REF] Kontonasios | Maximum Entropy Models for Iteratively Identifying Subjectively Interesting Structure in Real-Valued Data[END_REF]. The numerical extension of the last two models are also further unsuitable as competitors, since they cannot handle the requirements on value ranges specified in the predicates of redescriptions.

Experimental Evaluation

In this section, we present experiments to investigate the behaviour and performance of our algorithms and compare our two models MEALL and MEBLK.

We implemented our algorithm3 using MATLAB for the high level procedures and C++ for the core operations. All experiments were run on a cluster with 16 cores (at 2.4 GHz and with 48 GB of memory). The sets of redescriptions for the real-world data were mined in advance using the ReReMi algorithm (Galbrun and Miettinen, 2012a) in the Siren redescription mining interface4 [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions[END_REF][START_REF] Galbrun | Interactive Redescription Mining[END_REF].

Among existing redescription mining algorithms, we selected the ReReMi algorithm (Galbrun and Miettinen, 2012a). This choice is motivated by several properties of this algorithm: (i) it offers a rich query language that provides hard instances for the maximum-entropy calculations, (ii) it can handle missing values, (iii) it is rather susceptible to redundancy in the result set.

We proceed with a series of experiments on synthetic data sets, before moving on to real-world data.

Evaluation on synthetic data sets

Our goal in this series of experiments with synthetic data sets is to shed light on the different aspects that impact the complexity of the computations in a controlled experimental setting. Our focus here is on the quantitative evaluation of the performance of the algorithms and our primary measure in these experiments is therefore the wall-clock time for training and querying the model.

Note, however, that our objective here is not to present a highly efficient and fully optimised algorithm, but to demonstrate the feasibility of the approach. The evaluation on synthetic data is therefore designed to compare empirically the impact of the various aspects of the data and the queries on the runtimes.

We start by considering the simplest case of a model trained with a single Boolean statement and queried with another Boolean statement. That is, we first train the model with statement s t , then query the trained model to evaluate the occurrence probability of statement s q .

We call width of a statement the number of distinct variables it contains, that is, width(s t ) = |vars(s t )|, while the overlap between two statements is simply the number of variables they have in common, that is, over(s t , s q ) = |vars(s t ) ∩ vars(s q )|. We can fully control these parameters by using logical conjunctions and choosing suitable sets of variables for our statements.

Our base case is as follows. We let

s t = v A ∧ v B ∧ v C and s q = v B ∧ v C ∧ v D ,
so that width(s t ) = width(s q ) = 3 and over(s t , s q ) = 2. We fix the number of rows in our data set to M = 1000, of which 70% satisfy both s t and s q while the rest are evenly distributed over the remaining 3 truth combinations.

Starting from this base case, we can study the impact of different parameters in turn, by repeating the training and querying of our model while varying a chosen parameter of the problem. For each configuration, we record the total runtimes for training and querying. The results are reported in Figure 6. The The first parameter we consider is the number of rows in the data set (Figure 6a), and the second parameter is the number of query evaluations, that is, we train the model once with s t , before repeatedly querying it with the same statement s q (Figure 6b). In both cases, the behaviour of both models is linear.

Next, we study the impact of the shape of the statements by fixing the width of one statement to 3, while increasing that of the other, always keeping their overlap constant. The models show the same exponential increase of time in both cases (Figure 6c). Indeed, in both cases factors of equal sizes need to be evaluated.

Let us now study the impact of interactions between the statements, in terms of shared variables and of shared rows. The impact of varying variable overlap, as measured by over(s t , s q ), with constant widths width(s t ) = width(s q ) = 11, is shown in Figure 6d. On the other hand, the impact of varying row overlap, measured by J(s t , s q ), is shown in Figure 6e. The latter shows evidence that the number of different value combinations matters, rather than the number of rows in the overlap. Indeed, since the algorithm processes rows clustered according to the combination of factors they participate in, the number of such clusters in the data set has a major impact on the runtimes.

To further investigate the complexity arising from the structure of the data set through the number of clusters it induces, we modify our setup as follows.

Starting with an empty model, in each iteration i we add a different statement s i and then query the updated model with the same statement s q . All statements are defined over 10 Boolean variables. The query statement is a simple conjunction s q = v 1 ∧ . . . ∧ v 10 , whereas the training statement added at the i-th iteration has the form

s i = v i ∧ k =i v k ∨ ¬ k =i v k .
The training statements s i all have width(s i ) = 10 and over(s i , s q ) = 10, but have all distinct truth tables.

Next, we create 3 different data sets, each with M = 1024 rows. The first one only contains rows from {0, 1}, that is, with all of their values equal, so that at most 2 clusters will be created, regardless of the number of training statements added to the model. The second data set contains rows from the standard basis {e k : k = 1, . . . , 10}, so that the number of clusters increases by one with each added training statement. Finally, the third data set contains rows with all the possible Boolean combinations of the 10 variables, so that the number of clusters grows exponentially, reaching 2 i at the i-th iteration and thus representing the worst case scenario.

The runtimes for each iteration on these three data sets are reported in Figures 6f-h, respectively. We observe that the runtime for the MEALL model closely follows the number of clusters, since they all have to be evaluated. On the other hand, the MEBLK model only evaluates the clusters that support s q . The small additional overhead for the MEBLK model in the last case is due to the training phase, which still needs to track all clusters.

Finally, we look at the impact of the presence of missing values on the runtime. As a starting point, we use a subset of the DBLP data set, a fully Boolean data set which we present in more details in Section 7.2. We generate synthetic variants with different densities of missing values by deleting some entries at random. More specifically, we select a fraction α of the rows from the data set then replace a fraction β of the values on these rows by the missing value token. We mined redescriptions from the complete data set and let our models rank these redescriptions with each data set variant. The runtimes for ranking 20 queries while keeping α = 1, that is, spreading the missing values over the entire data set, but for different values of β, that is, varying the ratio of deleted values, is shown in Figure 7 (left). Vice-versa, in Figure 7 (right) we fixed the ratio of deleted values but vary the ratio of rows affected. Note that the cases where α = 0 or β = 0 correspond to using the complete data set. We observe that the presence of missing values results in longer runs with MEALL. As the amount missing values increases, the runtime decreases, but never reaches the runtimes on the complete data. The effect on MEBLK is similar, in the sense that more missing values result in shorter runs, but without the initial cost of having any missing entries at all.

Evaluation on real-world data sets

After this systematic investigation of the performance of our algorithms and models on synthetic data sets, we now present results from real-world data for a qualitative assessment.

Our goal with these experiments is to show that the approach is applicable to real-world data and that the proposed approach provides added value, in the sense that the rankings obtained with this advanced mechanism cannot be matched with some straightforward ranking criterion, such as accuracy or coverage.

We first provide quantitative evidence that the obtained rankings differ from those obtained with other methods. Then, we show top ranked redescriptions from real-world examples; these serve as subjective evidence that the selected redescriptions indeed provide a more nuanced representation, as well as a better insight into the data than, for instance, simply considering the most accurate redescriptions.

Data sets. We use four data sets, coming from four different domains and having different properties, in terms of their sizes and of the types of variables they involve.

First, the DBLP data set is extracted from the popular computer science bibliography. 5 The entities are researchers and one side records major conferences where they published, while the other side records the co-authorship graph (|E| = 2345, |V L | = 19, and |V R | = 2345; both sides are Boolean).

Our second data set, Bio, comes from the domain of ecology. The entities represent geographic areas of Europe, the left-hand side records the presence of various mammals species [START_REF] Mitchell-Jones | The Atlas of European Mammals[END_REF], while the right-hand side consists of bioclimatic variables, that is, monthly average rainfall and monthly average, minimum, and maximum temperatures [START_REF] Hijmans | Very High Resolution Interpolated Climate Surfaces for Global Land Areas[END_REF] Finally, we consider a fourth data set, which contains missing values. The EthnoAtlas data set combines ethnographic information about the cultural norms and practices of various societies around the world, assembled from several sources [START_REF] Murdock | Ethnographic atlas: a summary[END_REF][START_REF] Gray | A corrected ethnographic atlas[END_REF] and made available online,7 with the climatic profile of the regions where they live (|E| = 1267, |V L | = 90, and |V R | = 23; all variables on the right are real-valued except for the major habitat type which is nominal). We use different variants of this data set, one where the ethnographic variables are considered as real-valued variables and one where they are considered as nominal, that is, consisting of unordered values. We obtain further variants with different amounts of missing values by disregarding variables that contain more than 50 (|V L | = 75) and more than 25 (|V L | = 49) percent of missing values respectively. We use indices R and N to denote the real-valued and nominal variants, respectively, combined, when relevant, with indices .5 and .25 for the variants with fewer missing values.

Runtimes. The RankPatterns algorithm was run to rank sets of redescriptions of size |S| = 100, 60, and 230, extracted from DBLP, Bio, and Cover, respectively. For each data set, Figure 8 depicts the average time required to query the occurrence probability for each of the remaining candidate redescriptions, during each iteration of the ranking algorithm, ignoring the negligible time required for training the model.

These plots show steep rises in the query times that correspond to iterations where the last training redescription overlaps with the largest factor in the model, which must therefore be extended. As explained in Section 3, our algorithms use factorisation and quantisation to reduce the computational cost of evaluating occurrence probabilities. For this reason, the runtime complexity is dominated by the size of the largest factor in terms of value combinations, which may grow arbitrarily large as the degree of overlap increases. This effect is exacerbated in the case of real-valued variables due to the quantisation becoming finer following some model updates.

Fortunately, statements involving variables that have occurred in earlier selected statements are typically assigned higher probabilities. This means that such overlapping redescriptions are generally deemed uninteresting and pushed

MEALL MEBLK q

L q R p(R) p(R) COLT ∧ ICML R. Schapire - - EDBT ∧ PODS A. Silberschatz - - FOCS ∧ SODA N. Alon - - ICDM ∧ SDM P. Yu
selected by MEALL and MEBLK are identical, but the probabilities assigned to the remaining redrescriptions differ. In particular, the duplicate of the first redescription is assigned a probability of 1 by MEBLK, but a probability of 0.1313 by MEALL. Still, it is considered uninteresting under all models.

Overall, the MTV model assigns much lower probabilities than our models and its updates tend to be more conservative. Note that the MTV model takes into account the frequencies of individual variables as prior information, allowing to build rankings in a more informed manner than our models where ties are broken based on accuracy. Incorporating such information into our model is an interesting avenue for future work.

We observe that our models tend to strongly push down redescriptions that share variables with previously selected redescriptions, MEBLK even more so than MEALL, so that similar redescriptions are ranked far away from each other. This behaviour is desirable since as soon as one redescription is reported, interest on similar ones quickly drops. As a result, redescriptions ranked at the top by our models clearly constitute a more diverse set than those selected by MTV. Indeed, the first four redescriptions selected by our models cover the fields of machine learning, databases, theoretical computer science, and data mining, respectively, compared to only machine learning and data mining for MTV.

Ability to generalise. Next, we consider the ability of the redescriptions to generalise. More specifically, we study whether the redescriptions that are ranked as the most interesting by our models behave differently in terms of their ability to generalise as compared to lower ranked ones. To this aim, we follow the procedure introduced by Zinchenko et al. (2015). That is, we split the entities of the data set into five subsets, mine redescriptions while holding out one subset, then assess the accuracy of the obtained redescriptions on the full original data set. For the DBLP data set, entities were split at random between training set and hold-out set. For Bio, we sampled longitudinal stripes, so as to take into account the north-south trends in climate data. For each redescription, we compute the ratio between its accuracy in the training set and overall.

The reason why we consider the accuracy in the overall data rather than only in the hold-out set is that, in contrast to the models validated in a typical cross-fold setup, our redescriptions constitute local models of the data. More specifically, the accuracy of a redescription only considers the entities that are in the supports of either of the queries. If none of the entities in the hold-out set is included in either of the supports, the redescription's accuracy in the hold-out set is undefined.

Here, our aim is not to evaluate whether the models hold everywhere but, instead, where they hold, whether they do so with varying accuracies. Table 4 shows the average of this ratio for redescriptions ranked among the top 10 % as compared to the rest of the redescriptions, for both data sets and both models. The ability to generalise of the top ranked redescriptions appears to be very similar to that of the rest of the redescriptions, meaning that selecting the topranked redescriptions per our model does not harm the ability of the results to generalise and that the rank of a redescription is not directly related to its ability to generalise.

Coverage. In this experiment, we compare the rankings obtained with our models to other methods for ranking the redescriptions. More precisely, we look at how the set of entities is covered by the top redescriptions when picked according to different rankings, as a means to assess how similar these rankings are.

Figure 9 shows the cumulative ratio of entities that are covered by the ten first redescriptions for each ranking. Beside the rankings obtained with our MEALL and MEBLK models, we consider two further rankings. First, we rank the redescriptions in order of decreasing accuracy, denoted by J in Figure 9. Second, we rank the redescriptions by selecting at each step the redescription that covers the most currently uncovered entities. Clearly, this latter ranking provides the upper-bound for the achievable coverage, and it is denoted by the grey shading in Figure 9.

One further criterion for ranking would be the p-values computed for each redescription, indicating how likely it would be that two independent queries with the observed marginals have as large an intersection as the redescription support. However, this is not useful in practice, due to the fact that most of these p-values are essentially zero by construction.

We observe that MEALL either yields a clearly better coverage than MEBLK or is on par with it. When it comes to comparing our models to ordering the redescriptions by accuracy, the best coverage depends very much on which data set and what number of redescriptions we consider. This shows that the surprisingness does not reduce to coverage. On first thought, one might guess that the most surprising redescription per our models is the one that covers most of the not-yet-covered observations, but as these results show, that is not the case.

This experiment clearly shows that the rankings obtained with our approach are not equivalent to using a straightforward criterion such as accuracy or coverage.

Example rankings. Finally, we turn to a more qualitative assessment of our proposed ranking procedure.

Our first example illustrates the iterative ranking process on the DBLP data set, showing the evolution of the top-ranked redescriptions over a few steps in Table 5.

Using the ReReMi algorithm, we mined redescriptions from this data set, which were then sorted by accuracy and fed to the ranking algorithm. In the first step, the top redescription is added to the model, the probabilities for the other redescriptions are computed and the list is sorted by increasing occurrence probability, since higher probabilities are associated to less surprising and thus less interesting redescriptions. The second redescription is then added to the model, the probabilities recomputed and the ranking updated. The iterations continue until the entire list has been processed.

Table 5 shows how the redundant redescriptions are pushed away from the top of the list. For example, after adding the first redescription, all other redescriptions with SDM on the left-hand side are pushed out of the table. Notice, however, that some overlap is possible, if the redescriptions are otherwise surprising enough: for example, in the 7-th step, ICML appears in the right-hand side of two redescriptions that have already been included in the model.

In this example, the redescriptions typically represent fields of computer sciences, by associating major conferences and key researchers from these fields. Three fields are represented among the most accurate redescriptions (Step 0, Table 5 top left), namely (i) data mining, with for instance the SIAM International Conference on Data Mining (SDM) and researchers including Phillip S. Yu and Jiawei Han, (ii) databases, with the International Conference on Database Theory (IDBT), Renée J. Miller and Serge Abiteboul, as well as (iii) machine learning, with the International Conference on Machine Learning (ICML), the Conference on Learning Theory (COLT), and Robert E. Shapire. Redescriptions selected by our ranking procedure (Step 7, Table 5 bottom right) better represent the diversity of fields in computer science. At the same time, they often combine several conferences to delimit more specific subfields.

Next, we consider redescriptions mined from the Bio data set. In Table 6 we conditioned on the redescriptions seen previously. Thus, our approach fits into the general framework of subjective interestingness as proposed by De Bie (2011).

Working with redescriptions comes with its own challenges, though. Most notably, restricting redescriptions only to conjunctive queries -as is (implicitly) done in the existing work on subjective interestingness -severely limits the usability of the approach, and hence we extended our maximum-entropy model to handle also disjunctive queries. Many real-world data sets contain missing values, and our model can also handle them.

Another significant difference with the existing line of work on subjective interestingness is that we do not enforce any a priori conditions on the data (such as row and column marginals). With heterogeneous variable types (some variables are Boolean, others nominal, and yet others real-valued), these kinds of a priori conditions become less intuitive. Incorporating them to our model is also not straightforward, and we leave it as a topic for future work.

One potential extension of the current model is to take the amount of missing values into account: an observation with more missing values should be less trustworthy than a more completely observed one. In our model, this could be achieved via the row prior ρ, but a proper use of this approach would require us to know the model for the missing values (e.g. whether they appear uniformly or in bursts).

Finally, another natural direction for future work is to develop methods that can directly mine the most surprising redescription given the current model; the work presented in this paper can only be applied as a post-processing step. Designing a scalable method for directly mining the most surprising redescriptions is not straightforward. For example, it not clear how to effectively employ the quantisation and partition approaches presented in this work when one has to consider arbitrary statements.

'Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'05) ', pp. 364-373. Zinchenko, T., Galbrun, E. and Miettinen, P. (2015), Mining predictive redescriptions with trees, in 'IEEE International Conference on Data Mining Workshops', pp. 1672-1675.

=

  |T 00 | e 0 + |T 01 | e λ5 + |T 11 | e λ4+λ5 = 20 + 60 e λ5+ 120 e λ4+λ5 .

)

  Example 4. Consider the two real-valued variables v D and v E from our previous examples, with domains respectively [10, 50] and [0, 5]. Assume that the current model contains the single constraint statement s

Figure 4 .

 4 Figure 4. Partitions of the variable domains and region sizes for three different value combinations; s and q are the constraint and query statements respectively.

Figure 5 .

 5 Figure 5. From two existing factors and a new statement (left) to the updated model containing five factors (right).

Algorithm 3 :F←

 3 RankPatterns input : data set D, set of statements S with selected statement s 0 output : ordered list of statements O 1 F ← TrainModel(∅, s 0 ); 2 O ← (s 0 ); S ← S \ {s 0 }; 3 while S = ∅ do 4 s * ← s ∈ S, minimising QueryModel(F , D, s); 5 TrainModel(F , s * ); 6 O ← (O, s * ); 7 S ← S \ {s * }; 8 return O;

Figure 6 .

 6 Figure 6. Experimental results on synthetic data sets: runtimes for training and querying averaged over 10 repetitions. The width of the error bars equals twice the standard deviation.

Figure 7 .

 7 Figure 7. Runtimes for ranking 20 queries from a data set with various levels of missing values.

  (|E| = 2575, |V L | = 194, and |V R | = 48; the species records are Boolean and the climate variables real-valued). Our third data set, Cover, 6 also comes from the domain of ecology. The entities represent geographic areas of a national forest in Colorado, USA. The wilderness area, soil type, and cover type constitute the right-hand side variables, while other, topographic variables, such as elevation and slope, are on the left-hand side (|E| = 581012, |V L | = 10, and |V R | = 45; all variables on the right are Boolean except for the cover type which is nominal, and all those on the left are real-valued).

Figure 8 .

 8 Figure8. Experimental results on real world data sets: mean runtime per query for MEALL (solid lines) and MEBLK (dashed lines).

Figure 9 .

 9 Figure9. Cumulative ratio of entities covered by the redescriptions when selected according to various rankings.

Table 3 .

 3 Ranking conjunctive redescriptions from DBLP with MEALL, MEBLK, and MTV. Step 4.

Table 4 .

 4 Average accuracy ratio between testing and training sets for the top ranked redescriptions versus the rest.

	Data set Model	J ratio top	J ratio rest
	DBLP	MEBLK	0.733 (42 values) 0.707 (425 values)
	DBLP	MEALL	0.733 (42 values) 0.707 (425 values)
	Bio	MEBLK	0.839 (37 values) 0.910 (403 values)
	Bio	MEALL	0.819 (33 values) 0.911 (407 values)
	DBLP		Cover	Bio

The present work is an extended version of our earlier conference publication(Kalofolias, Galbrun and Miettinen,

2016).

The Dirac delta, which is the continuous equivalent of the Kronecker delta, is a generalised function that assumes an infinite mass when its argument is zero, in our case effectively ensuring that only the case of r = rρ is possible.

The source code is available at http://siren.mpi-inf.mpg.de/max-ent/.

http://siren.gforge.inria.fr, accessed 13 December 2017

http://www.informatik.uni-trier.de/ ~ley/db/, accessed 13 December 2017

https://archive.ics.uci.edu/ml/datasets/Covertype, accessed 13 December 2017

http://intersci.ss.uci.edu/wiki/index.php/Ethnographic_Atlas#Rdata_format_ version_of_Ethnographic_Atlas, accessed 13 December 2017

--VLDB ∧ ICDT H. Garcia-Molina .1250 .1250 ICDT ∧ SIGMOD S. Abiteboul .1250 .1250 UAI ∧ ICML D. Koller .1259 .1484 SDM ∧ KDD J. Han .1261 .2083 ICDT ∧ PODS S. Abiteboul .1265 .1331 COLT ∧ ICML M. Kearns .1277 .2500 COLT ∧ ICML A. Blum .1277 .2054 SDM ∧ KDD P. Yu .1284 .4674 ICDM ∧ SDM H. Wang .1284 .4250 PKDD ∧ SDM P. Yu .1284 .3977 FOCS ∧ COLT Y. Mansour .1292 .1667 COLT ∧ ICML R. Schapire .1313 1.

MTV

lower in the ranking, with the beneficial consequence of delaying the formation of larger factors to later iterations of the algorithm.

Comparison to the MTV model. In this section we compare the ranking obtained with our models to the ranking obtained with the model of [START_REF] Mampaey | Tell Me What I Need To Know: Succinctly Summarizing Data with Itemsets[END_REF], denoted as MTV.

The MTV algorithm originally mines interesting itemsets. In this comparison, we consider only the DBLP data set, which is fully Boolean, and focus on the subset of redescriptions that consist purely of conjunctions, to accommodate the more restricted pattern language of MTV. Furthermore, we bypassed the tile mining scheme proposed by the authors, using the model to rank the collection of pre-mined redescriptions.

The rankings produced by our models and by MTV after the first four redescriptions have been ranked are shown in Table 3, together with the probabilities assigned at that stage to the remaining redescriptions.

All three models are initialised by first incorporating the most accurate redescription. Note that up to the stage shown here, the top redescriptions show the top of the list of redescriptions, sorted by accuracy, which were fed to the ranking procedure. The top of the output list is shown in Table 7.

In this example, the redescriptions characterise geographic areas based on the mammals species that inhabit them on one hand (q L ) and based on the climatic profile, on the other hand (q R ). More specifically, the right-hand side variables contain the minimum, maximum, and average monthly temperatures, and total monthly precipitations at the different locations. For instance, variables t ∼ 5 , t + 10 , p 8 denote the average temperature of May, the maximum temperature of October, and the precipitation of August, respectively.

When ranking the redescriptions by accuracy, we note that the first six all characterise the habitat of the polar bear in terms of temperature. While the conditions are different, with the first climate query fixing the range of the average temperature in May, the second fixing the range of the average temperature in March, and so on, they all impose a similar requirement: low temperatures. Hence, while very accurate, those redescriptions are also highly redundant, and of limited interest when taken together. Instead, the top redescriptions selected by our algorithm exhibit a much greater diversity, involving various species and climate conditions and having support of different sizes spreading over various geographic areas. While they are optimal neither in terms of accuracy nor in terms of entity coverage, these redescriptions are still of fairly high quality when considered individually, while they form a set of good quality when considered together.

Conclusions

Thus far, redescription mining was mostly focused on the problem of finding good redescriptions, ignoring the more global problem of finding a good set of redescriptions. In this work, we have approached this latter problem from the point of view of maximum-entropy distributions: a redescription is non-redundant if and only if it has a low likelihood under the maximum-entropy distribution, Table 6. Redescriptions from Bio ranked by accuracy.