Descriptive Complexity Approaches To Inductive Inference

Abstract

We present a critical review of descriptive complexity approaches to inductive inference. Inductive inference is defined as any process by which a model of the world is formed from observations. The descriptive complexity approach is a formalization of Occam's razor: choose the simplest model consistent with the data. Descriptive complexity as defined by Kolmogorov, Chaitin and Solomonoff is presented as a generalization of Shannon's entropy. We discuss its relationship with randomness and present examples. However, a major result of the theory is negative: descriptive complexity is uncomputable. Rissanen's minimum description length (MDL) principle is presented as a restricted form of the descriptive complexity which avoids the uncomputability problem. We demonstrate the effectiveness of MDL through its application to AR processes. Lastly, we present and discuss LeClerc's application of MDL to the problem of image segmentation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1991
Accession Number
ADA356664

Entities

People

  • Kevin Atteson

Organizations

  • University of Pennsylvania

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Coding
  • Computer Programming
  • Computer Programs
  • Computer Vision
  • Computers
  • Information Science
  • Information Theory
  • Mathematical Filters
  • Measure Theory
  • Probabilistic Models
  • Probability
  • Probability Distributions
  • Random Variables
  • Real Numbers
  • Statistical Inference
  • Stochastic Processes

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Artificial Intelligence
  • Mathematical Modeling and Probability Theory.

Technology Areas

  • AI & ML