Janis Kalofolias
email: kalofolias@mpi-inf.mpg.de

Esther Galbrun
email: esther.galbrun@inria.fr

Pauli Miettinen
email: pauli.miettinen@mpi-inf.mpg.de

From Sets of Good Redescriptions to Good Sets of Redescriptions

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 find a good set of redescriptions, instead of finding a set of good redescriptions. That is, we present a way to remove the redundant redescriptions from a given set of redescriptions. We measure the redundancy using a framework inspired by the subjective interestingness based on maximum-entropy distributions as proposed by De Bie in 2011. Redescriptions, however, raise their unique 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. The framework also reduces the redundancy in the redescription mining results, as we show in our empirical evaluation.

I. INTRODUCTION

Redescription mining is a data mining task that aims at finding alternative characterizations 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 synonymic characterizations.

Take for instance the case of areas of the globe, for which climatic information as well as records of observed animal species are available. Areas that share a particular climatic profile and host particular species 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, or chemistry, for instance.

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

Thus, the problem we address in this paper is one of pattern selection. Considering a dataset that consists of a pair of matrices over the same objects, and given a collection of redescriptions that has been mined from this dataset, we want to select a redescription set 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 as a post-process.

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, i.e. the pattern does not provide any new information about the data, it is considered to be redundant and can be discarded. Otherwise, the pattern is deemed interesting and is integrated into the model, increasing its quality.

Our approach is iterative: at each step the candidate redescriptions are evaluated against the model that encapsulates the current knowledge available about the data, i.e. the information about the dataset acquired through the redescriptions selected so far. We can compute a score for each candidate indicating how much novel information it contains with respect to the current state, allowing us to rank the redescriptions. We then select the most informative one and incorporate it into the model. Next, we proceed with updating the scores of the candidates and selecting the best one, until no additional information can be incorporated into the model; that is, until only redundant candidate redescriptions are left.

Our modeling techniques rely on the Maximum Entropy distribution and the framework of subjective interestingness, as proposed by De Bie [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF]. In brief, we keep up a maximum entropy distribution conditioned on all of the already-seen redescriptions to model what is already known, and consider redundant all redescriptions that have a high likelihood under this distribution. We emphasize, however, that our model differs from that of [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF] 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.

The approach presented here rests on two main lines of work. Redescription mining, on one hand, provides us with a rich pattern language, while maximum entropy modeling, on the other hand, provides us with well-grounded selection principles. The next section where we cover the related research, is divided between these two domains upon which we build.

II. RELATED WORK

A. Redescription Mining

Since the introduction of redescription mining by Ramakrishnan et al. in 2004 [START_REF] Ramakrishnan | Turning CARTwheels: an Alternating Algorithm for Mining Redescriptions[END_REF], a few problem variants [START_REF] Galbrun | Methods for Redescription Mining[END_REF], [START_REF] Parida | Redescription Mining: Structure Theory and Algorithms[END_REF], [START_REF] Zaki | Reasoning About Sets Using Redescription Mining[END_REF], several algorithms [START_REF] Galbrun | Finding Relational Redescriptions[END_REF], [START_REF] Gallo | Finding Subgroups having Several Descriptions: Algorithms for Redescription Mining[END_REF], [START_REF] Ramakrishnan | Turning CARTwheels: an Alternating Algorithm for Mining Redescriptions[END_REF], [START_REF] Zinchenko | Mining Predictive Redescriptions with Trees [Demo[END_REF], as well as an interactive mining tool [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions[END_REF], [START_REF] Galbrun | Interactive Redescription Mining[END_REF] have been introduced. Redescription mining is a descriptive approach, tailored towards exploratory data analysis. Redescriptions are local patterns in the sense that they characterize subsets of the data, rather than capturing properties of the dataset as a whole. 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] Agrawal | Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[END_REF], [START_REF] Kröger | Subspace Clustering Techniques[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 datasets is a distinguishing feature.

B. Maximum Entropy modeling

The maximum entropy principle, formalized by Jaynes [START_REF] Jaynes | Probability Theory: The Logic of Science[END_REF], allows to build a probability distribution over possible datasets under constraints, with the advantage of not adding extra bias beyond what is assumed from the constraints.

It is a versatile principle which has been applied to ecological modeling [START_REF] Phillips | Maximum Entropy Modeling of Species Geographic Distributions[END_REF] as well as to natural language processing (NLP) [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF], and has been used to construct a condensed representation of the dataset to be used for query approximation [START_REF] Mannila | Prediction with Local Patterns Using Cross-entropy[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].

De Bie [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF] proposed to use maximum entropy models to evaluate subjective interestingness and in the present work we follow his general idea. Importantly, unlike the previous work (e.g. [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF], [START_REF] Kontonasios | Maximum Entropy Models for Iteratively Identifying Subjectively Interesting Structure in Real-Valued Data[END_REF], [START_REF] Tatti | Maximum entropy based significance of itemsets[END_REF]), we need to also handle disjunctions, rather than just conjunctions of the variables. On the other hand, 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. Mampaey et al. [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.

A further distinction is between approaches which model rows of the dataset [START_REF] Mampaey | Summarizing Data Succinctly with the Most Informative Itemsets[END_REF], [START_REF] Tatti | Maximum entropy based significance of itemsets[END_REF] versus those which consider the dataset as a whole [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF], handling 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 | Maximum Entropy Modelling for Assessing Results on Real-Valued Data[END_REF]. Related modeling 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] Van Leeuwen | Association discovery in two-view data[END_REF], [START_REF] Vreeken | KRIMP: Mining itemsets that compress[END_REF], but do not offer a similar flexibility and modeling power.

III. BACKGROUND

A. Maximum Entropy modeling

The maximum entropy distribution p subject to the constraints C = {(f c , π c )} is defined as the solution to the following program:

max p∈P - V p(x) log p(x)dx (1) such that V p(x)f c (x)dx = π c ∀c ∈ C. ( 2
)
The optimisation is over the set P of distributions p over V (i.e. such that p(x) ≥ 0 and V p(x)dx = 1).

The solution to this optimisation problem can be computed using standard tools from constrained variational optimisation in order to obtain

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 Lagrange multipliers λ in Eq. ( 4) can be computed as the solution of the convex dual

q(λ) = log Z λ - c∈C λ c π c ,
which can be shown to be equivalent to the conditions

Ep [f c (r)] = π c ∀c ∈ C. (5)

B. Redescription Mining

In the formulation of redescription mining considered here, the input data consist of entities with two sets of characterizing variables, thus forming a dataset 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 over two sets of variables V L and V R , respectively. The domains of the variables are denoted by V L and V R , respectively, and they can be either continuous or discrete. The set of entities characterized by the two sides is denoted by E, thus both matrices have |E| rows. The value of D(i, j) is the value of variable v j ∈ V for entity

d i ∈ E.
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.

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 Iverson notation, e.g. [a ≤ v ≤ b], except for Boolean variables where the truth assignment [v = True] is denoted simply as v. These truth assignments and their negations are combined into logical statements using the Boolean operators ∧ (and) and ∨ (or).

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).

To measure the accuracy of a redescription R, we use the Jaccard coefficient of the supports of the queries

J(R) = J(q L , q R ) = |supp(q L ) ∩ supp(q R )| |supp(q L ) ∪ supp(q R )| ,
being at once a simple, symmetric, and intuitive measure. Accuracy, however, is a local feature of the redescription and 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 datasets, 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 in modeling the conjunction of the two queries that make up a redescription, and the intersection of their supports that is simply 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 dataset 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 dataset D is a matrix with N = |V | columns and M = |E| rows.

IV. 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. Next, we explain how to represent an entire dataset based on this row model, using a mixture model that comes in two variants.

A. Modeling Rows

Let r represent a vector sampled from the domain of the variables

V = V 1 × • • • × V N .
Our goal in this section is to define p(r | S), the probability that an arbitrary dataset row takes on values r, assuming the presence of a given collection of logical statements S. We denote this probability simply as p(r) when the constraining set of statements is clear from the context. Each statement s ∈ S is associated to a probability π s that a random instance r satisfies it, with respect to the probability measure defined by the model p M . Thus, in our setting, the conditions of Eq. ( 5) can be specified formally as

Ep M [χ s (r)] = π s ∀s ∈ S , (6)
where χ s (r) is the characteristic function of the statement s: χ s (r) = 1 if s holds true on r, and χ s (r) = 0 otherwise.

We can assume that these conditions are satisfiable since they are derived from actual observations. Then, plugging them as constraint functions into Eq. ( 3) and ( 4), we obtain the solution and partition function

p λ (r) = 1 Z λ exp s∈S λ s χ s (r) , (7)
Z λ = V exp s∈S λ s χ s (x) dx . (8)
However, this formal solution to the maximum entropy optimisation problem cannot be used directly. Indeed, in this general form the model is computationally too complex and we need to exploit the problem structure to simplify it.

Factorising the distribution:

In its general form, the integration in the partition function of Eq. ( 8) runs over the domain of the entire set of variables, whereas each logical statement typically only involves a small subset of them. Therefore, to simplify the computation we can split the statements into groups, so that the computation of each group involves as few variables as possible and can be carried out independently. The requirement for this is that the sets of variables appearing in the different groups be disjoint from one another, which also allows the sums within the exponents of Eq. ( 7) and ( 8) to be similarly split into groups.

Hence, we define a partitioning K of the variables 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. Then, the sets {S K , K ∈ K} form a partitioning of S and we can write

exp s∈S λ s χ s (r) = K∈K exp s∈S K λ s χ s (r) .
The integral in the partition function can also be split into integrals over domains V K of the variables in K. We obtain

p λ (r) = K∈K p λ K (r) , (9)
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 ,
and the normalisation can be performed per each Z K (λ) term.

Example. Consider a dataset 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 Fig. 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 Fig. 1 (top). Suppose that at this point the constraint [START_REF] Phillips | Maximum Entropy Modeling of Species Geographic Distributions[END_REF] is added. To fulfill the containment requirement, we now need to merge K 1 and K 2 , resulting in the clustering shown in Fig. 1 (bottom). To further speed-up the computation, we can also perform a re-parametrization (or factorisation) of the distribution, for instance using the Junction Tree algorithm [START_REF] Jensen | Optimal Junction Trees[END_REF].

s 6 = v C ∨ ¬[v D <
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}
Quantising the domains: A further source of complexity results from integrating over the domain of the variable set. We can exploit the fact that the redescriptions consider intervals over the continuous variables to quantise the variables into discrete bins defined over these intervals.

Looking at the truth table for the statements in S, we group together the regions of the domain where the same combination of statements are satisfied. Formally, adopting an arbitrary ordering s 1 , . . . , s σ of the statements in S, for a vector (t 1 , . . . , t σ ) ∈ {0, 1} σ of truth values for the statements we denote the corresponding collection of regions as

T t1•••tσ = {r ∈ V : χ si (r) = t i for all s i ∈ S} .
The resulting partitioning of the domain is denoted as T . Using a similar notation for the subscripts, we denote the combinations of Lagrange multipliers as

ζ t1•••tσ (λ) = λ 1 • t 1 + • • • + λ σ • t σ .
We can now express Eq. ( 7) and ( 8) as

p λ (r) = 1 Z(λ) exp ζ t(r) (λ) , (10)
Z(λ) = Tt∈T Tt exp (ζ t (λ))dx (11) = Tt∈T |T t (λ)| exp (ζ t (λ)) ,
where t(r) = (χ s1 (r), . . . , χ sσ (r)) is the truth vector of the statements for the current point.

Example. Going back to our example, 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 Fig. 1). The truth table of these statements is shown in Tab. I (left). The terms can be gathered based on the satisfiability of the constraints in the just 5 different combinations of Tab. I (right). The partition function of Eq. ( 11) 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 .
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
) := Q p(x)dx. Q v D v E χs 4 χs 5 Tt |Tt| ζ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 λ 4 + λ 5 2/(40 • 15) 0.1 Q 4 [20, 50] [2, 5] 1 1 +30 • 3 0.3
In this small example, the number of terms has been reduced from 2 3 = 8 to 5. As the number of variables per factor 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. From the optimality conditions of Eq. ( 6) 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

Q 1 Q 2 Q 3 Q 4 0 10 5 50 2 20 v E v D s 4 s 5
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

B. Modeling a dataset

Our models take as input an original dataset D and a collection of logical statements S. To each deterministic row d i in D we associate a random counterpart denoted by r i , constrained by those statements in S that are satisfied on d i . Let us denote this subset of statements by S i , that is

S i = {s ∈ S : χ s (d i ) = 1}.
Using the row model introduced in the previous section, henceforth denoted by p ROW , the probability of the row values can now be defined as

P (r i | D, S) := p ROW (r i | S i ) . ( 12
)
Given the row probabilities, our goal is to combine them into a probability over all possible values of a dataset.

A naïve approach would be to model the data as a set of independent rows so that the total probability is a simple product. This has a major drawback, though: the total probability depends too much on the probabilities of the individual rows. For instance, if the satisfiability probability of a statement on a row is halved, the total probability will be halved too.

Instead, our models compute the total probability as a weighted average of row models. In our first model variant, called MEALL, the average runs over all the rows in the dataset, while our second model variant, called MEBLK, considers only those rows which satisfy the given query statement.

Both MEALL and MEBLK are mixture models. MEALL is represented by the solid arrows of the graphical model in Fig. 3. Each of the M plates represents a variable r i depending on S and d i through S i , as explained above. The mixing coefficient ρ acts as a prior probability over the row indices. It specifies which row models should be mixed together to obtain the final distribution over the values of r, a single row summarizing the entire dataset. To enforce the selection behaviour r = r ρ , the row selecting function can be expressed as where δ (•) is the Dirac delta function. 1 The row prior ρ is the uniform distribution over the row indices. We denote by q the satisfiability of a query statement s on a row r, which is constant given s and r:

P (r | r 1 , . . . , r M , ρ) := δ (r -r ρ ) , (13)
P (q | r, s) := χ s (r) . ( 14
)
Now the posterior distribution of MEALL becomes

P (q | s; D, S) = M ρ=1 P (ρ) V,V1,...,V M P (r | r 1 , . . . , r M , ρ) × P (q | r, s) × M i=1 P (r i | D, S) drdr 1 • • • dr M (15)
which simplifies by substituting the specific distributions to

p ALL (q | s; D, S) = 1 M M i=1 p ROW (q | s; S i ) , (16)
with p ROW (q | s; S i ) := E [χ s (r i ) | S i ] being the probability that the query statement s is satisfied on row r i . The quantity in Eq. ( 16) 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 s exclusively,

P (ρ | d 1 , . . . , d M , s) := χ s (d ρ ) M i=1 χ s (d i ) , (17)
we obtain the MEBLK model, shown as the dotted dependencies in Fig. 3. Note that MEALL possesses the useful property that p ALL (q|¬s; •) = 1 -p ALL (q|s; •), which does not generally hold under MEBLK. The latter, however, offers a more intuitive interpretation of the occurrence probability, in accordance to the framework of De Bie [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF]. In particular, it is better suited to comparing queries without penalizing support size and yields qualitatively better results, as well as generally lower computational complexity.

V. ALGORITHMS

The models described in Section IV can be used for different tasks which include generating synthetic datasets 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 occurence 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.

A. 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 factorized 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 dataset, and

J i = {f ∈ F | vars(f ) ∩ vars(s) = ∅, i ∈ I f } (18)
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 by construction. For any given statement s, vars(s) and supp(s) also define a tile in the dataset.

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 with a newly appended statement, while updating the set of factors so that independence is preserved by avoiding overlaps.

Algorithm 1: TRAINMODEL

input : model F , new statement s output : updated model F 1 J ← {J i : i ∈ supp(s)} ; // See Eq. (18) 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 ;
The pseudo-code for this procedure, TRAINMODEL, is presented in Alg. 1. It 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 Eq. ( 18) (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).

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
In the example shown in Fig. 4, 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. 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 Alg. 1 to the case of an empty row cluster J = ∅). The updated f 1 , now covering fewer rows, remains, 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 dataset rows.

B. 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 dataset and a pattern extracted from the dataset, the aim is to evaluate the occurence probability of the pattern.

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

Algorithm 2: QUERYMODELROW input : model F , statement s output : probability pROW (s|D; F ) 1 Fs ← {f ∈ F | vars(f ) ∩ vars(s) = ∅}; 2 (w, v) ← QUANTIZATION(s, Fs); 3 Zs ← 1 T w; 4 p ← (v ⊗ w)/Zs ;
// ⊗ is the element-wise product 5 p ← MARGINALIZEANDNORMALIZE(s, Fs, p); 6 return p;

Querying a row model:

Each row model is parameterised by the subsets of statements that occur on the corresponding data row. The occurrence probability p ROW (s | D; F) of a statement for a given row model is computed by QUERYMODELROW as shown in Alg. 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. Sec. IV-A). 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, 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 and the corresponding constraints respected, to finally yield the probability of statement s.

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 dataset, while MEBLK only averages over rows that satisfy the statement under evaluation, i.e. over supp(s).

C. A ranking scheme

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

Algorithm 3: RANKPATTERNS

input : dataset 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, minimizing QUERYMODEL(F , D, s); 5 F ← TRAINMODEL(F , s * ); 6 O ← (O, s * ); S ← S \ {s * }; 7 return O;
This procedure takes as input a dataset and a collection of statements, with one of them designated to initialize 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 (line 6). The procedure iterates until all statements have been ranked. Note that this method closely resembles the dynamic iterative ranking scheme of Mampaey et al. [START_REF] Mampaey | Tell Me What I Need To Know: Succinctly Summarizing Data with Itemsets[END_REF].

VI. 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 algorithm2 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 [START_REF] Galbrun | From Black and White to Full Color: Extending Redescription Mining Outside the Boolean World[END_REF] in the Siren redescription mining interface3 [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, REREMI offers the most flexible query language and is simultaneously rather suceptible to redundancy in the result set.

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

A. Evaluation on synthetic datasets

Our goal in this series of experiments with synthetic datasets 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.

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 consider two statements, s t and s q , used to constrain and to query the model, respectively. In other words, we first train the model with s t , then query the trained model to evaluate the occurrence probability of s q .

We call width of a statement the number of distinct variables it contains, i.e. width(s t ) = |vars(s t )|, while the overlap between two statements is simply the number of variables they have in common, i.e. 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 dataset 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 running times for training and querying. The results are reported in Fig. 5. The markers and the error bars indicate respectively the mean running times and twice the standard deviation for 10 repetitions of each configuration.

The first parameter we consider is the number of rows in the dataset (Fig. 5a), 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 (Fig. 5b). 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 (Fig. 5c). Indeed, in both cases factors of equal sizes need to be evaluated.

We look at 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 Fig. 5d. On the other hand, the impact of varying row overlap, as measured by J(s t , s q ), is shown in Fig. 5e. The latter shows further 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 dataset has a major impact on the running times.

To further investigate the complexity arising from the structure of the dataset 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 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 ∧ κ =i v κ ∨ ¬ κ =i v κ . 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 datasets, each with M = 1024 rows. The first one only contains rows from {0, 1}, i.e. 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 dataset contains rows from the standard basis {e κ : κ = 1, . . . , 10}, so that the number of clusters increases by one with each added training statement. Finally, the third dataset 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 running times for each iteration on these three datasets are reported in Fig. 5f-5h, respectively. We observe that the running time 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.

B. Evaluation on real-world datasets

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

Our first example illustrates the iterative ranking process. Using the REREMI algorithm, we mined redescriptions from redescription is then added to the model, the probabilities recomputed and the ranking updated. The iterations continue until the entire list has been processed.

Tab. III 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 7th step, ICML appears in the right-hand side of two redescriptions that have already been included in the model.

Our second dataset, 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] In Tab. IV we 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 Tab. V. The top redescriptions selected by our algorithm exhibit a much greater diversity. In particular, the redescriptions about the Polar Bear do not take all the top spots any longer: albeit very accurate, they are highly redundant and of limited interest when taken together.

Our last dataset, Cover5 , 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).

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 dataset, Fig. 5i depicts the average time required to query the occurence 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 Sec. IV, our algorithms use factorisation and quantisation to reduce the computational cost of evaluating occurence 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 numerical 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 lower in the ranking, with the beneficial consequence of delaying the formation of larger factors to later iterations of the algorithm.

VII. 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, conditioned on the redescriptions previously seen. Thus, our approach fits into the general framework of De Bie [START_REF] Bie | Maximum Entropy Models and Subjective Interestingness: An Application to Tiles in Binary Databases[END_REF].

However, working with redescriptions comes with its own challenges. 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 method. Therefore, we had to develop an approach that can also handle disjunctive queries.

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). Incorporating such constraints into our model is an interesting topic for future work.

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.

Figure 1 :

 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).

Figure 2 :

 2 Figure 2: Regions of the domains of v D and v E . Example. 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 Fig. 1, respectively; 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 Fig.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 Tab. II. 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

Figure 3 :

 3 Figure 3: Graphical Representation of MEALL (solid lines) and MEBLK (all lines).

Figure 4 :

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

  t ) ∩ vars(s q )| (d) Variables overlap.

  Real world results: mean runtime per query for MEALL (solid lines) and MEBLK (dashed lines).

Figure 5 :

 5 Figure 5: Experimental results: (a-h) synthetic datasets (running times for training and querying averaged over 10 repetitions, the width of the error bars equals twice the standard deviation) and (i) real world datasets (averaged querying times).

  (|E| = 2575, |V L | = 194 and |V R | = 48; the species records are Boolean and the climate variables real-valued).

Table I :

 I 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).

Table II :

 II 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

  r satisfies all s ∈ S, and 0 otherwise , 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.

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

http://www.informatik.uni-trier.de/ ∼ ley/db/

https://archive.ics.uci.edu/ml/datasets/Covertype

the DBLP dataset. This dataset is extracted from the popular computer science bibliography. 4 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). In Tab. III we show the evolution of the top-ranked redescriptions over a few steps.

Initially, the redescriptions fed to the algorithm are sorted by accuracy. 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


Vidit Jain
email: viditj@yahoo-inc.com

Esther Galbrun
email: galbrun@cs.helsinki.fi

Topical Organization of User Comments and Application to Content Recommendation

Keywords: H.4 [Information Systems Applications]: Miscellaneous Algorithm, User Generated Content, Recommendation

On a news website, an article may receive thousands of comments from its readers on a variety of topics. The usual display of these comments in a ranked list, e.g. by popularity, does not allow the user to follow discussions on a particular topic. Organizing them by semantic topics enables the user not only to selectively browse comments on a topic, but also to discover other significant topics of discussion in comments. This topical organization further allows to explicitly capture the immediate interests of the user even when she is not logged in. Here we use this information to recommend content that is relevant in the context of the comments being read by the user. We present an algorithm for building such a topical organization in a practical setting and study different recommendation schemes. In a pilot study, we observe these comments-to-article recommendations to be preferred over the standard article-to-article recommendations.

INTRODUCTION

Consider the example of an article about a recent tornado in Alabama. The main topics appearing in the comments for this article are displayed in a compact and interactive interface (see Figure 1(a)). Each block corresponds to one cluster, summarized by a tag cloud of the entities that occur in it. In this illustration, the user is reading the comments that discuss the emergency responses of the Federal Emergency Management Agency (FEMA) after this natural disaster (cluster highlighted in a darker shade). At a different time, this user may be reading other comments that question the legitimacy of government's spending of billions of dollars as foreign aid. In the first case, the user is likely to be more interested in reading about the responses after similar natural disasters, such as hurricane Katrina, as opposed to information on foreign aid efforts. Existing systems either use only the article text along with a global personalization model [START_REF] Galbrun | Personalized recommendation of user comments via factor models[END_REF], or enrich the parent article with a holistic analysis of all of the associated comments [START_REF] Wang | User comments for news recommendation in social media[END_REF] to recommend articles. These systems fail to distinguish between the above two different information needs of a single user. Our system addresses this issue by recommending an article relevant to the specific context of a semantically coherent cluster of comments (Figure 1(b)).

Our conclusions do not compete with, but complement, other approaches that model user profiles [START_REF] Galbrun | Personalized recommendation of user comments via factor models[END_REF] and user similarities [START_REF] Linden | com recommendations: item-to-item collaborative filtering[END_REF] for providing personalized recommendations.

TOPICAL ORGANIZATION

Building topical organization for user comments has its unique challenges. The difference in the language skills and seriousness of comment writers leads to a huge variation in the language and content across comments. The standard natural language processing and information extraction systems perform poorly on these noisy, short pieces of text. Also, for popular articles, the comments arrive at a high rate and the topics of discussions evolve rapidly over time. On a typical news website, the desired system need to compute these topics for thousands of articles every few minutes. Another constraint is due to the actual representation of the extracted topics to the users -in order to provide a consistent user experience across different articles, the hosting website prescribed that at most five different clusters Here we compute topics as clusters of comments. Even though individual comments show diverse and unreliable language, the entities mentioned in them provide a useful signal for clustering comments to form topics. Here they are identified using a system [START_REF] Mccallum | Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons[END_REF] optimized for news domain. The set of these entities, however, varies significantly across articles and the comment count for different entities follows a heavy-tailed distribution. Hence a global set of important entities is ineffective for clustering comments into topics across articles; the topics need to be computed separately for each article from all of its corresponding comments.

Entity-based clustering (EBC). To address the latency and other requirements mentioned above, we designed an algorithm that highlights entities. We first extract the named-entities and selective parts of speech, e.g. nouns and adjectives from the comments. While clustering, only these extracted terms are used to represent the comments. Then, we partition the comments into small initial subsets based solely on the occurrences of named-entities. Next, we construct a graph where each vertex represents an initial subset. The weight of the edge between every pair of vertices is computed as the inner product of the two tf-idf representations of the comments belonging to the corresponding partitions. Finally, the METIS k-way partitioning algorithm 1 is used to obtain five partitions of this graph as the clusters of comments. Table 1 shows a comparison of EBC with other computationally feasible alternatives on 19,320 articles, each of which received at least 100 comments. Based on these observations, we choose EBC for the rest of our experiments.

CONTENT RECOMMENDATION

We consider three recommendation schemes (see Figure 2). The traditional setting for article recommendation (AA) selects the best matching article for a given source article. The second scheme (CA) selects the best matching article for the comments belonging to a given source cluster of comments. Finally, the third scheme (CCA) finds the best matching cluster of comments and selects the parent article of this matching cluster as the target recommendation. These schemes are implemented using a retrieval engine similar to Lucene, which allows a rapid indexing of large volumes of textual data. We use the standard tf-idf representation for the news articles. However, since the com- . The inverse document frequencies of different terms are computed separately for articles and clusters, and denoted by idf clu (t) and idfart(t). The relevance of an indexed document d to a source document s is then defined as R(s, d) = t∈d tfT (t, s) * tfRS(t, d) * idfT (t) 2 , where T ∈ {clu, art} is the type of the source document and tfRS the term frequency computed by the retrieval engine.

We collected the comments for 1884 popular articles (each with at least 500 user comments) from Yahoo! News. In all, we obtained about 9000 clusters (over 2 million comments), for each of which we generated the recommendations using the above schemes. In our pilot study, we first asked users to read comments from a (source) topic. Then they were shown recommendations from each of the above schemes, and asked to choose the most relevant one in the context of the source cluster. As seen in Figure 3, CA is preferred significantly more than both of the AA and CCA schemes. We observed that using topical clusters as sources enables us to identify engaging topics that are latent in the article but are made explicit in the comments. We further investigated machinelearned ensemble techniques that select one of these three recommendations based on the source document. As shown in Table 2, a Gaussian-process based ensemble method was found to perform the best.

Multi-class SVM Naïve-Bayes GP-ensemble -3.6% +1.8% +8.5%

  (a) Example UI for clusters of comments (b) Recommendation is shown below the comments

Figure 1 :

 1 Figure 1: Recommending content in the context of user comments.

1Figure 2 :Figure 3 :

 23 Figure 2: Different recommendation schemes.

Table 1 :

 1 Comparison of clustering algorithms.

	k-means	0.542 4.353 0.120	0.474
	METIS	0.517 23.003 0.858 0.511
	EBC	0.511 14.960 1.912 0.505
			Aver-
	age values of the entropy of intra-cluster term fre-
	quencies (TE), per article inter-cluster overlap be-
	tween top-5 terms (TO), entropy of topic sizes (CE),
	and fraction of comments assigned a topic (COV).
	be shown per article. While it is interesting to study other
	choices of number of topics as well, we focus only on obtain-
	ing up to five topics per article in this work. In addition, the
	usual properties (i.e., intra-topic semantic coherence, inter-
	topic semantic distinction, and balanced distribution of topic
	sizes) for any topical organization are desired.

Table 2 :

 2 Improvement (over CA) in predicting user preferences using ensemble methods.


Tetiana Zinchenko
email: zinchenko@mpi-inf.mpg.de

Esther Galbrun
email: galbrun@cs.bu.edu

Pauli Miettinen
email: pmiettin@mpi-inf.mpg.de

Mining Predictive Redescriptions with Trees

Keywords: Redescription mining, Decision trees, Interactive data mining, Visualization

In many areas of science, scientists need to find distinct common characterizations of the same objects and, vice versa, identify sets of objects that admit multiple shared descriptions. For example, a biologist might want to find a set of bioclimatic conditions and a set of species, such that this bioclimatic profile adequately characterizes the areas inhabited by these fauna. In data analysis, the task of automatically generating such alternative characterizations is called redescription mining. A number of algorithms have been proposed for mining redescriptions which usually differ on the type of redescriptions they construct. In this paper, we demonstrate the power of treebased redescriptions and present two new algorithms for mining them. Tree-based redescriptions can have very strong predictive power (i.e. they generalize well to unseen data), but unfortunately they are not always easy to interpret. To alleviate this major drawback, we present an adapted visualization, integrated into an existing interactive mining framework.

I. INTRODUCTION

Redescription mining is a method that aims at finding alternative descriptions of the same objects, or, in other words, providing information on the same entities from different perspectives. It is a tool for knowledge discovery that helps integrate multiple characterizing data sets of diverse origins and reason across them. Matching the objects across the available datasets-for instance by exploiting information shared between the datasets via entity resolution and matching techniques-is a prerequisite for redescription mining.

Several approaches have been proposed to mine redescriptions. Here, we consider the case of two data sets and we focus on approaches based on decision tree induction [START_REF] Quinlan | Induction of decision trees[END_REF]. Applying such techniques to redescription mining is not a new idea [START_REF] Ramakrishnan | Turning CARTwheels: an alternating algorithm for mining redescriptions[END_REF]. Our algorithms, however, differ from the existing ones both in their inner working and in their capabilities. Indeed, we present two algorithms based on decision tree induction which unlike existing tree-based methods can handle non-binary data, and scale well. Importantly, our methods also generalize well to unseen data.

While tree-based redescription mining algorithms can have many desirable properties, they all share an important weakness: expressing the decision trees as Boolean formulae makes them very hard to interpret. To help interpreting the redescrip-tions, we present an interactive visualization method for treebased redescriptions.

We have integrated our tree-based algorithms and visualizations into our redescription-mining tool Siren. This allows the user to use both tree-based and other algorithms and compare and visualize (and edit) their results in an intuitive and powerfull way.

We briefly explain our tree-based algorithms in Section III, and discuss the visualization of the trees in Section V.

II. BACKGROUND AND RELATED WORK

The input of our methods is a pair of data matrices, where one side contains only Boolean variables while the other side may contain real-valued variables. Throughout, we refer to the two sides as the left and right-hand sides and assume, without loss of generality, that the former is the fully Boolean side. We will represent the data using two matrices D L and D R over two sets of variables, V L and V R , respectively.

The set of entities characterized by the two sides is denoted by E, hence both matrices have |E| rows. The value of D L (i, j) is the value of variable v j ∈ V L for entity e i ∈ E.

If v ∈ V is Boolean, we interpret the column corresponding to it as a truth value assignment for e ∈ E in a natural way. If v ∈ V is real-valued, we consider a threshold t and the truth value assignments induced by relations such as t < v or v ≤ t. These truth assignments and their negations constitute the set of literals which can then be combined into queries with operators ∧ (and) and ∨ (or). A redescription R is a pair of queries (q L , q R ) over variables from V L and from V R , respectively.

The support of a query q, supp(q), is the set of entities for which the query holds true, and the support of a redescription is simply the intersection of supports of its two queries.

The main quality of a redescription is the similarity of the supports of the two queries that it consists of, also called its accuracy. The Jaccard similarity coefficient is the measure of choice to evaluate the accuracy of redescriptions, being at once simple, symmetric and intuitive. It is defined as follows:

J(R) = J(q L , q R ) = |supp(qL)∩supp(qR)| |supp(qL)∪supp(qR)| .
Besides accuracy, several other factors impact the quality of a redescription. For instance, we are not interested in redescriptions which are supported by only a handful of entities or conversely by almost all of them, i.e. redescriptions for which |supp(q L ) ∩ supp(q R )| is too small or too large.

Furthermore, redescriptions should also be statistically significant. To evaluate the significance of results, we use p-values as in [START_REF] Galbrun | From black and white to full color: Extending redescription mining outside the Boolean world[END_REF]. Our algorithms incorporate parameters to account for these preferences.

In short, given two data matrices, redescription mining is the task of searching for the best matching pairs of queries, one query over each of the data sets.

Related Work. The problem of mining redescriptions was introduced by Ramakrishnan et al. [START_REF] Ramakrishnan | Turning CARTwheels: an alternating algorithm for mining redescriptions[END_REF]. They proposed an algorithm called CARTwheels based on decision trees, with an alternating approach to grow decision trees from which redescriptions are then extracted [START_REF] Kumar | Redescription mining: Algorithms and applications in bioinformatics[END_REF].

Algorithms employing heuristics-rather than growing decision trees-to produce pairs of queries that are almost equivalent on the given data set were presented in [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF]. Theses algorithms rely on different strategies to prune the search space. By means of an efficient on-the-fly discretization, such heuristics were extended to real-valued data, resulting in the ReReMi algorithm [START_REF] Galbrun | From black and white to full color: Extending redescription mining outside the Boolean world[END_REF].

The main feature of redescriptions is their ability to describe data from different points of view, i.e. their "multi-view" aspect. A similar approach is taken by some other methods such as Multi-label Classification [START_REF] Tsoumakas | Mining multi-label data[END_REF], Emerging Patterns [START_REF] Novak | Supervised Descriptive Rule Discovery: A Unifying Survey of Contrast Set, Emerging Pattern and Subgroup Mining[END_REF], and Subgroup Discovery [START_REF] Umek | Subgroup Discovery in Data Sets with Multi-dimensional Responses: A Method and a Case Study in Traumatology[END_REF] to name a few (see [START_REF] Galbrun | From black and white to full color: Extending redescription mining outside the Boolean world[END_REF] for more details). The main differences between redescription mining and these methods are that redescription mining aims to find multiple descriptions simultaneously for a subset of entities which is not specified a priori, it selects only relevant variables from a potentially large number, and it is symmetric, in the sense that it handles both sides of the data similarly.

III. ALGORITHMS

Our algorithms rely on decision tree induction for mining redescriptions. More specifically, we grow two trees in opposite directions, gradually increasing their depth and matching their leaves. We use classification and regression trees (CART) [START_REF] Breiman | Classification and regression trees[END_REF] for this purpose, but any other approach to induce decision trees can be exploited as well. What follows is a succinct description of the algorithms; more detailed explanation can be found in [START_REF] Zinchenko | Redescription mining over non-binary data sets using decision trees[END_REF].

Growing Trees. Our input is a pair of data matrices, where one side (w.l.o.g. the left-hand side) contains Boolean attributes while the other side may contain real-valued attributes.

We use the Boolean variables to initialize our procedure. That is, a column of D L provides the target vector for building the first tree. The vector of predictions output at one step is then used as the target vector when growing a tree over attributes from the other side during the next step, in alternating iterations.

This procedure continues to alternate between growing trees over either side of the data, until any of the following three stopping conditions is met: i) no tree can be induced with the given parameters, ii) the maximal tree depth chosen by the user is reached, or iii) the prediction vector obtained from the new tree is identical to the one previously obtained on that side, i.e. the tree growing procedure has reached a fixed point.

A tunable parameter, l min , controls the minimum number of entities allowed in any leaf of the tree. This helps to combat overfitting and terminate the tree induction earlier.

We present two algorithms which follow the process described above but differ in their strategy for growing trees.

The SplitT Algorithm. Our first algorithm grows a new classification tree at each iteration while progressively increasing their depth. As explained above, a column from the Boolean side, D L , is initially used as target vector to induce a tree over the other side, D R . This first iteration produces a tree of depth one with two leaves, which are labelled according to the majority class of the entities they contain, one positive and one negative. The corresponding binary prediction vector for the entities is then used as a target vector to grow a new tree over D R , this time of depth two. In turn, the prediction vector is used as a target to learn from scratch a tree of depth two over D R , and so on.

The LayeredT Algorithm. Our second algorithm grows trees layer by layer instead of building a new tree from scratch in each iteration. One layer is added to the current candidate tree by appending a new decision tree of depth one to each of its branches, each learnt independently from the others.

Extracting Redescriptions. At the end of the alternating process we obtain a pair of decision trees, over either sets of variables. Their leaves are labelled as belonging either to the positive or the negative class and matched throught the common entities.

The extraction of a redescription from such a pair of decision treesworks as follows. From either tree we obtain a query over the variables from that side charaterizing the positive class. One literal is constructed for each node of the decision tree using the associated splitting variable and threshold. Then, literals leading to the positive leaves are combined into a query, using conjunctions (∧) to combine literals within one branch and disjunctions (∨) to combine different branches.

The output of our algorithms consists of the collected redescriptions over all induced tree pairs. Extending to fully non-Boolean settings. Both of our proposed algorithms can be applied when neither side is fully Boolean. In such cases, a binarization or a clustering routine can be applied to one of the sides to process real-valued and categorical attributes as necessary. However, this might require domain knowledge and some amount of trial and error to determine the most appropriate discretization settings.

IV. EXPERIMENTAL EVALUATION

In this section we investigate the predictive power of redescriptions. Extensive experiments on the behaviour of our tree-based algorithm on synthetic and real-world data can be found in [START_REF] Zinchenko | Redescription mining over non-binary data sets using decision trees[END_REF].

Datasets. In our first dataset, Bio, 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 righthand 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] Methods. We compared the redescriptions obtained with our proposed algorithms SplitT and LayeredT, to those returned by the ReReMi [START_REF] Galbrun | From black and white to full color: Extending redescription mining outside the Boolean world[END_REF] and CARTwheels [START_REF] Ramakrishnan | Turning CARTwheels: an alternating algorithm for mining redescriptions[END_REF] algorithms (implementations provided by the authors).

To study the ability of the redescription to generalize to unseen data, we selected 80% of the entities, mined redescriptions from this training set then assessed their accuracy on the full original data sets.

For the DBLP data set, entities were split at random between training and hold-out sets. For Bio and Bio S , we had to take into account the North-South trends in climate data: predicting conditions in North with data from South (or vice versa) is unlikely to succeed. Hence we sampled longitudes, and the hold-out set consisted of all point laying (roughly) on the sampled longitudes (in total 20% of entities were held out).

1 http://www.informatik.uni-trier.de/ ∼ ley/db/ With Bio and Bio S we set the minimum support to 200, the maximum support to 1800 (for DBLP 5 and 1300 respectively) and the maximum p-value to 0.05 for all algorithms.

Results. The CARTwheels algorithm was only able to run on the Bio S data, running out of memory with the others. As CARTwheels also requires all-binary data, we binarized the climate data in Bio S . We tested various techniques, and the results we report here are based on segmenting every variable in 4 segments, as this gave the best results with all of the tested methods.

As our goal is to find redescriptions that hold well in the unseen data, we measure the quality of the generalization using the average ratio of the accuracy of the redescriptions in the training data to their accuracy in the full data. If this ratio is significantly below 1, we conclude that the redescriptions did not generalize well.

Statistics for this experiment are reported in Table I. On Bio S , SplitT and CARTwheels achieve essentially the same quality, both returning high-accuracy redescriptions that generalize well. CARTwheels' larger number of redescriptions is due to the fact that it returned multiple almost-identical redescriptions. LayeredT also reported redescriptions that generalize well, although their overall accuracy was lower than with the other methods, while ReReMi apparently overfitted. On Bio, we observe similar behaviour from SplitT, LayeredT, and ReReMi (CARTwheels could not be used on this data) with SplitT giving the best overall results.

On the DBLP data, SplitT is the only algorithm returning results that are both accurate and generalize well, although most of its redescriptions had lower supports than the redescriptions returned by the other methods: LayeredT and vice versa for blue lines; finally the gray lines are the ones that do not belong to supp(q L ) ∪ supp(q R ).

To see the power of our visualization, consider the query q R . The root splits the entities into two sets, depending on whether March's maximum temperature is below or above 11.05. But when it is below (bottom right branch in Figure 1 left), only very few entities contribute to supp(q L )∩supp(q R ), indeed, there are only few purple lines coming out of that leaf. Consequently, the analyst could consider removing the bottom branch, leaving only q R = [11.05 < t3+] ∧ [-3.95 ≤ t2-] as the right-hand side query. Indeed, if he does so, the Jaccard coefficient drops only from 0.691 to 0.665.

VI. CONCLUSIONS

We presented two new decision-tree based algorithms for redescription mining, SplitT and LayeredT. Redescription mining is a powerful data analysis tool, but its usability is significantly reduced unless we can trust that the redescriptions found will also hold on unseen data. The goal of our algorithms is to succeed on this prediction task. Our experiments showed that our algorithms achieve this goal, generalizing much better than the state-of-the-art ReReMi. Compared to the other tree-based algorithm, CARTwheels, our algorithms were able to find more interesting redescriptions, scale to larger data sets, and most importantly, handle non-Boolean data. Combined to a tailored visualization feature integrated in the Siren interface, these algorithms significantly enhance the toolbox of redescription mining.

Fig. 1 .

 1 Fig. 1. Visualizations a redescription from Bio, its queries displayed as a pair of classification trees (left) and its support plotted on a map (right).

  (|E| = 2575, |V L | = 194 and |V R | = 48). We extract a subset of this data, which we denote as Bio S , by selecting only areas from Northern Europe, namely areas located at latitudes between 50 and 71 • North, and keeping only the average monthly temperatures and rainfall (|E| = 1271, |V L | = 194 and |V R | = 24). Our third data set, DBLP, is extracted from the popular computer science bibliography. 1 The entities are researchers and one side records the co-authorship graph while the other side records the number of their publications in each of the major conferences considered (|E| = 2345, |V L | = 2345, and |V R | = 19).

See also http://siren.mpi-inf.mpg.de/

returns redescriptions with very low accuracy, and while ReReMi's accuracy is better in the training data, it again overfits and has very low generalizability.

V. VISUALIZATION

As evidenced by the above empirical investigation, treebased redescriptions are a powerful way to explain structures in the data. Unfortunately, they can also be very hard to interpret. Consider, for example, the following redescription: This redescription encodes a tree where we can take two branches from the root (the root variable appears as itself and in a negated format), and on both branches there are one or two leaves that contribute towards the support. To help the user in understanding the redescriptions better, we propose a visualization technique for the tree-based redescriptions, seen in Figure 1, left. We included this tree-based visualizations, along with the new mining algorithms, into our interactive redescription mining framework, Siren. 2 Visualizing a decision tree is, of course, a well-known and not too complicated problem. What makes our setting special, is that instead of one decision tree, we must visualize two decision trees that are linked in their leaves. We visualize this linkage by drawing lines between the leaves: a line connects two leaves if the data has an entity for which the corresponding paths in the trees hold true. However, not every path in the tree participates in the query-otherwise we would always cover the whole data-and the color of the line encodes this information. Purple lines correspond to entities that belong to the support of the redescription, i.e. supp(q L ) ∩ supp(q R ); red lines are the ones that belong to supp(q L ) but not to supp(q R )