# Maximum Entropy Models And Subjective Interestingness: An Application To Tiles In Binary Databases

Tijl De Bie Intelligent Systems Laboratory, University of Bristol tijl.debie@gmail.com August 2010

## Abstract

Recent research has highlighted the practical benefits of subjective interestingness measures, which quantify the novelty or unexpectedness of a pattern when contrasted with any prior information of the data miner
(Silberschatz and Tuzhilin, 1995; Geng and Hamilton, 2006). A key challenge here is the formalization of this prior information in **a way that**
lends itself to the definition of an interestingness subjective measure that is both meaningful and practical.

In this paper, we outline a general strategy **of how this could be**
achieved, before working out the details for a use case **that is important**
in its own right.

Our general strategy is based on considering prior information as constraints on a probabilistic model representing the uncertainty about the data. More specifically, we represent the prior information **by the maximum entropy (MaxEnt) distribution subject to these constraints. We**
briefly outline various measures that could subsequently be **used to contrast patterns with this MaxEnt model, thus quantifying their subjective**
interestingness.

We demonstrate this strategy for rectangular databases with knowledge of the row and column sums. This situation has been considered before using computation intensive approaches based on swap randomizations, allowing for the computation of empirical p-values as interestingness measures (Gionis et al, 2007). We show how the MaxEnt **model**
can be computed remarkably efficiently in this situation, and **how it can**
be used for the same purpose as swap randomizations but computationally more efficiently. More importantly, being an explicitly **represented** distribution, the MaxEnt model can additionally be used to define analytically computable interestingness measures, as we demonstrate for tiles
(Geerts et al, 2004) in binary databases.

Keywords: **Maximum Entropy Principle, Subjective Interestingness**
Measures, Prior Information, Rectangular Databases, Swap **Randomizations**