the tile. The fact that it reduces to a simple sum is due to the independence of the database entries D(i, j**) under the MaxEnt distribution.**

## 5.2.2 The Description Length Of A Tile

A data miner is never merely interested in receiving as much information as possible. Indeed, the best way to achieve this would be to communicate the entire database to the data miner, which would be of little use. Instead, a data miner will be interested in hearing about patterns that convey new information as concisely as possible.

To quantify this, we also need to consider the inherent description length of the pattern, in this case the tile τ = (I, J**), or equivalently its set of rows** I and set of columns J. A sensible way to describe a set of rows I **would be** to assume a probabilistic model in which rows occur independently in I**, each**
with a certain probability p **(see below for more details). Then the description** length for the set I **under a Shannon-optimal code with respect to this model**
is given by:

DescriptionLength(I) = −
$$\begin{array}{r c l}{{\mathrm{Length}(I)}}&{{=}}&{{-\sum_{i\not\in I}\log(1-p)-\sum_{i\in I}\log(p)}}\\ {{}}&{{=}}&{{-(m-|I|)\log(1-p)-|I|\log(p),}}\\ {{}}&{{=}}&{{|I|\log\left(\frac{1-p}{p}\right)+m\log\left(\frac{1}{1-p}\right),}}\end{array}$$
Doing the same for the set of columns J **and combining both descriptions, the** description length for a tile τ = (I, J**) is given by:**

$$\begin{array}{r c l}{{\mathrm{h}(\tau)}}&{{=}}&{{\mathrm{DescriptionLength}(I)+\mathrm{DescriptionLength}(J),}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{=}}&{{(|I|+|J|)\log\left(\frac{1-p}{p}\right)+(m+n)\log\left(\frac{1}{1-p}\right)}}\end{array}$$

This means that the description length of a tile is equal to its circumference |I| + |J| **times a constant, plus another constant term, which makes intuitive**
sense as a model for the perceived complexity of a tile.

The probability parameter p **can be set by the data miner to bias the search**
toward larger or toward smaller tiles. Indeed, if p is small, the constant component (m + n**) log** 1 1−p of a tile description length is small while the variable component (|I| + |J|**) log** 1−p p
**is large, thus yielding a short description**
length for tiles with a small circumference as compared to large ones. In our experiments, we set it equal to the probability that D(i, j) = 1 for i and j sampled uniformly at random, which is equal to the density of the database p =1 mn Pi,j D.