PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximum entropy models and subjective interestingness: an application to tiles in binary databases

Tijl De Bie

arXiv:1008.3314v1cs.AI

TL;DR

The paper addresses how to formalize prior information for subjective interestingness measures. It proposes MaxEnt distributions constrained by that information and develops a tile interestingness measure, reporting that it more effectively finds embedded tiles than a related measure.

  • Problem

    Formalizing prior information into meaningful and practical subjective interestingness measures remains a key challenge in data mining.

  • Method

    The paper models prior information as constraints on a MaxEnt distribution, then develops the compression ratio measure for tiles using row and column sums.

  • Results

    The compression ratio approach is reported to be much more effective than surface-based interestingness at finding an embedded tile.

  • Takeaways & Limitations

    The MaxEnt framework compactly represents constrained rectangular databases, supports efficient sampling, and enables tile interestingness measures that account for row and column sums.

  • Takeaways & Limitations

    MaxEnt sampling conserves transaction sizes only in expectation, which can produce qualitatively different results when transaction sizes are fixed.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses how to formalize prior information so patterns can be assessed for subjective interestingness rather than merely rediscovering expected structure. It proposes maximum-entropy probabilistic models as an explicit background model and develops the approach for rectangular databases and tiles.

  • Motivation: Data mining should identify departures from prior information rather than patterns trivially implied by it.For example, jointly frequent items may be expected under an independence model when their individual frequencies are known.
  • Motivation: Subjective interestingness measures assess pattern novelty relative to the data miner’s prior information, unlike objective measures based only on the data.Prior information must be formalized before patterns can be contrasted with it meaningfully.
  • Paper strategy: The paper focuses primarily on designing background models that incorporate prior information, while outlining how those models can define subjective interestingness measures.It demonstrates one such measure in greater detail on a practical use case.
  • Prior work: Earlier approaches formalized prior information as independent beliefs or Bayesian networks, but Bayesian networks can be difficult to design and cannot represent prior information about individual transactions.The Bayesian-network approach also treats transactions as i.i.d. random variables.
  • Prior work: Swap randomizations assess significance under fixed row and column sums by approximately sampling databases with those sums, but the computation is intensive.The method has also been extended to real-valued data and more complex constraints.
  • Contributions: The general framework uses maximum entropy to construct explicitly representable probabilistic models for broad classes of prior information.The paper then applies this framework to rectangular databases with row and column marginal constraints and tile patterns.

2 Formalizing prior information, and subjective interestingness measures: a general approach

The paper formalizes prior information as constraints on a maximum-entropy probability distribution, then proposes contrasting patterns with that model to measure subjective interestingness.

  • 2 Formalizing prior information, and subjective interestingness measures: a general approach: The general strategy represents prior information through constraints on a probabilistic model of uncertainty and uses the maximum-entropy distribution satisfying them.The approach is intended as a general framework before being specialized to particular data, prior-information, and pattern types.
  • 2.1 The maximum entropy principle to model prior information: The general framework is deliberately not specialized to one data or pattern type, so further development is needed for practical applications.The paper develops a concrete use case later rather than fully analyzing general optimization efficiency.
  • 2.1 The maximum entropy principle to model prior information: The MaxEnt distribution is chosen because unspecified assumptions are avoided while the stated constraints are retained.The paper also gives a game-theoretic justification based on minimax-optimal coding under distributions satisfying the constraints.
  • 2.1 The maximum entropy principle to model prior information: The constrained optimization produces an exponential-family model parameterized by Lagrange multipliers and a partition function.The multipliers are obtained by minimizing a convex Lagrange-dual objective.
  • 2.2 Using the MaxEnt model to define subjective interestingness measures: Subjective interestingness can be quantified by contrasting a pattern with its MaxEnt model using self-information, information compression ratio, or a p-value.Lower pattern probability or a smaller p-value indicates greater surprise under the encoded prior information.
  • 2.2 Using the MaxEnt model to define subjective interestingness measures: Self-information uses negative log-probability under MaxEnt, while compression ratio additionally accounts for the complexity of describing the pattern.The p-value option treats the MaxEnt model as the null hypothesis and evaluates the pattern or a stronger instantiation.

3 MaxEnt Distributions for Rectangular Databases

For rectangular databases with expected row and column sums, the paper derives MaxEnt models across several value domains and shows that the models are efficiently computable and compactly representable.

  • 3 MaxEnt Distributions for Rectangular Databases: The paper applies the general MaxEnt strategy to rectangular databases with prior information about row and column sums.It considers binary, positive integer-valued, and positive real-valued matrix entries.
  • 3 MaxEnt Distributions for Rectangular Databases: Swap randomizations preserve row and column sums and can approximately sample the corresponding uniform distribution, but convergence rates lack theoretical results.The MaxEnt approach uses the same invariants in relaxed form by constraining expected rather than fixed sums.
  • 3 MaxEnt Distributions for Rectangular Databases: The partition function for the matrix model is a product of the partition functions of the individual element distributions.This establishes the factorized exponential-family form for the matrix distribution.
  • 3 MaxEnt Distributions for Rectangular Databases: The MaxEnt distribution for matrix entries factorizes into independent element-wise distributions as a consequence of the MaxEnt objective.Independence is not imposed as an initial assumption.
  • 3 MaxEnt Distributions for Rectangular Databases: For binary matrices, the element-wise distributions reduce to independent Bernoulli distributions.The corresponding normalization and parameter expressions are obtained from the general MaxEnt form.
  • 3 MaxEnt Distributions for Rectangular Databases: For positive integer-valued matrices, the element-wise distributions reduce to independent geometric distributions.For positive real-valued matrices, they reduce to independent exponential distributions.
  • 3 MaxEnt Distributions for Rectangular Databases: The Lagrange multipliers can be optimized with standard convex-optimization methods such as Newton’s method or gradient descent.The derivatives have interpretations in terms of differences between expected and constrained row or column sums.
  • 3 MaxEnt Distributions for Rectangular Databases: The resulting model supports constant-time probability computation for any matrix element and requires O(m + n) storage, sublinear in the data size.These properties make the approach suitable for very large-scale practical problems.

4 The Invariance of the MaxEnt Matrix Distribution to δ-Swaps

The MaxEnt distribution is invariant under allowed δ-swaps and, more generally, assigns equal probability to matrices sharing row and column sums. This establishes its connection to swap-randomization null models while retaining an explicit probability representation.

  • δ-swaps: a randomization operation on matrices: An allowed δ-swap preserves the MaxEnt probability of a matrix under equality constraints on expected row and column sums.The operation adds δ to two diagonal entries and subtracts δ from the two off-diagonal entries, provided all resulting values remain in the domain.
  • Invariance under fixed marginals: The MaxEnt distribution assigns the same probability to any two matrices with identical row and column sums.Thus, row and column sums are sufficient statistics for the MaxEnt distribution.
  • Connection to swap randomization: The MaxEnt distribution conditioned on row and column sum constraints is identical to the uniform distribution over all databases satisfying those constraints.This formalizes the relationship with distributions sampled through swap randomizations.
  • Special cases of δ-swaps: For binary databases, allowed δ-swaps reduce to the swaps used by Gionis et al. (2007), while for positive real-valued databases they reduce to Ojala et al.’s Addition Mask method.These earlier invariants are special cases of the generalized δ-swap operation.

5 Using the MaxEnt model: Randomizing Databases, and Subjective Interestingness of Tiles

The MaxEnt model supports direct, efficient database randomization and enables subjective interestingness measures for tiles. For tiles, interestingness is based on how much unexpected information is communicated relative to description length, and tile sets can be selected greedily.

  • Overview: The MaxEnt model provides an alternative to swap randomizations for database randomization and supports subjective interestingness measures for binary-database tiles.The section focuses on using prior information encoded by row and column sums.
  • Randomizing databases: Direct Bernoulli sampling of every database entry has complexity O(mn), making it prohibitive for large sparse databases.Each entry is sampled using its MaxEnt success probability.
  • Randomizing databases: 38?
  • Randomizing databases: The direct MaxEnt sampler cannot replace swapping when row and column sums must be preserved exactly rather than in expectation.This limitation can arise for categorical data represented as a binary matrix.
  • Subjective interestingness of tiles: A tile’s compression ratio measures self-information under the MaxEnt model per bit required to describe the tile, so larger ratios identify more efficient communication of unexpected information.The self-information increases as the tile probability decreases.
  • Finding interesting sets of tiles: The greedy tile-set algorithm selects the tile maximizing the ratio of uncovered-entry weights to the tile’s description length, an approximation to budgeted maximum coverage.In the first iteration, this criterion coincides with the single-tile compression-ratio measure.

6 Discussion

The MaxEnt framework connects rectangular-database modeling to network models, psychometrics, and existing tiling approaches. It also clarifies scope boundaries and motivates extensions to non-binary databases and weighted networks.

  • Networks: Network edge swaps preserve node in- and out-degrees, paralleling swap randomizations used for database matrices.The MaxEnt framework is applied to adjacency matrices under corresponding constraints.
  • Networks: The rectangular-database theory extends with minor changes to unweighted or weighted, directed or undirected networks, with or without self-loops.Network adjacency matrices can impose symmetry or diagonal-zero constraints as needed.
  • Connections to existing models: The binary-matrix MaxEnt model is formally identical to the Rasch model, while the p1 network model is formally identical to it for unweighted adjacency matrices.The paper presents MaxEnt as an additional perspective on these established models.
  • Extensions: The paper presents the MaxEnt approach as suggesting generalizations toward non-binary databases and weighted networks.
  • Model limitations: The Chung–Lu model represents a valid probability distribution only if max_i,j d_i d_j ≤ s, a condition that may fail in practical power-law graphs.The paper attributes this limitation to excessive preference for connections between high-degree nodes, producing edge probabilities above 1.
  • Relation to tiling methods: The method refines database tiling by assigning MaxEnt-derived weights to entries and description-length-dependent costs to tiles.The paper reports that these changes substantially affect the subjective quality of the resulting tile sets.

7 Experiments

Experiments evaluate MaxEnt fitting, sampling, comparison with swap randomizations, network scalability, and tile-ranking behavior across databases and networks. The results show rapid convergence, similar randomized-data behavior with greater efficiency, scalable network fitting, and apparently less redundant tile rankings.

  • Experimental setup: The experiments evaluate MaxEnt fitting, sampling, swap-randomization comparisons, network scalability, and compression-ratio-based tile interestingness.They use ten databases, including standard benchmark and text-derived datasets, with expected row and column sums matched to the observed data.
  • MaxEnt fitting: The gradient and Lagrange-dual objective converge very quickly, with apparently exponential gradient decrease and convergence in just a few iterations.Iterations stop when the normalized squared gradient norm falls below 10^-12.
  • Database randomization: MaxEnt sampling produces closed-itemset results broadly similar to swap randomizations, while retaining plots that show which itemset sizes are significant.The largest difference occurs for Mushroom, where transaction sizes are fixed but preserved only in expectation by MaxEnt sampling.
  • Computational cost: MaxEnt randomization is five to fifteen times more efficient for one randomized database and about thirty times more efficient when sampling several databases.The comparison includes the overhead of fitting the MaxEnt model for one database; repeated sampling mainly repeats the sampling component.
  • Network scalability: Network MaxEnt fitting takes under 30 seconds for the largest 10^6-node network and fewer than 50 Newton iterations across the tested models and degree distributions.The experiments attribute controlled memory requirements and fast performance to having relatively few distinct observed degrees.
  • Tile interestingness: The proposed compression-ratio ranking is argued to produce more non-redundant and interesting top tiles, and it identifies embedded tiles more effectively than surface-based ranking.The authors report that top-ranked tiles often coincide with major topics and that meaningful tiles cannot be attributed to randomness.

8 Conclusions

The paper introduces maximum entropy modeling as a framework for formalizing prior information and defining subjective interestingness measures. For rectangular databases constrained by row and column sums, it provides an efficient MaxEnt model, sampling procedure, and tile-specific compression-ratio measure, while identifying further use cases for investigation.

  • The paper introduces a maximum entropy approach for modeling prior information, with fitting reduced to a well-posed convex optimization problem.
  • For rectangular databases with row and column sum constraints, the MaxEnt model has a compact representation that enables substantially more efficient computation.
  • The framework supports efficient sampling of random databases that satisfy the specified prior information.
  • The paper develops compression ratio as a new tile interestingness measure incorporating row and column sums as prior information.
  • Future work will examine other prior information for rectangular databases, including variance within rows or columns and corresponding Gaussian MaxEnt models.
Loading 1008.3314v1…