Complexity measures and concept learning

DOI10.1016/J.JMP.2015.01.001MaRDI QIDQ2348075zbMATH OpenOpenAlexFDO

Authors Andreas Duus Pape, Kenneth J. Kurtz, Hiroki Sayama

Publication date 10 June 2015

Published in Journal of Mathematical Psychology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.7424

zbMATH Keywords

complexityconceptsinductionlearning

Mathematics Subject Classification ID

Rationality and learning in game theory (91A26) Cognitive psychology (91E10) Memory and learning in psychology (91E40)

Abstract: The nature of concept learning is a core question in cognitive science. Theories must account for the relative difficulty of acquiring different concepts by supervised learners. For a canonical set of six category types, two distinct orderings of classification difficulty have been found. One ordering, which we call paradigm-specific, occurs when adult human learners classify objects with easily distinguishable characteristics such as size, shape, and shading. The general order occurs in all other known cases: when adult humans classify objects with characteristics that are not readily distinguished (e.g., brightness, saturation, hue); for children and monkeys; and when categorization difficulty is extrapolated from errors in identification learning. The paradigm-specific order was found to be predictable mathematically by measuring the logical complexity of tasks, i.e., how concisely the solution can be represented by logical rules. However, logical complexity explains only the paradigm-specific order but not the general order. Here we propose a new difficulty measurement, information complexity, that calculates the amount of uncertainty remaining when a subset of the dimensions are specified. This measurement is based on Shannon entropy. We show that, when the metric extracts minimal uncertainties, this new measurement predicts the paradigm-specific order for the canonical six category types, and when the metric extracts average uncertainties, this new measurement predicts the general order. Moreover, for learning category types beyond the canonical six, we find that the minimal-uncertainty formulation correctly predicts the paradigm-specific order as well or better than existing metrics (Boolean complexity and GIST) in most cases.

Recommendations

• Categorical invariance and structural complexity in human concept learning
• Complexity minimization in rule-based category learning: revising the catalog of Boolean concepts and evidence for non-minimal rules
• On the intrinsic complexity of learning
• Intrinsic complexity of learning geometrical concepts from positive data
• A theory of the learnable

Cites work

• A catalog of Boolean concepts.
• A Mathematical Theory of Communication
• A note on the complexity of Boolean concepts
• An algebra of human concept learning
• An introduction to Kolmogorov complexity and its applications
• Categorical invariance and structural complexity in human concept learning
• Complexity minimization in rule-based category learning: revising the catalog of Boolean concepts and evidence for non-minimal rules
• Evaluating case-based decision theory: predicting empirical patterns of human classification learning

Cited in

(6)

• scientific article; zbMATH DE number 910359 (Why is no real title available?)
• Predicting the ease of human category learning using radial basis function networks
• The information complexity of learning tasks, their structure and their distance
• Information lattice learning
• Categorical invariance and structural complexity in human concept learning
• Complexity minimization in rule-based category learning: revising the catalog of Boolean concepts and evidence for non-minimal rules

This page was built for publication: Complexity measures and concept learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348075)