The Futility of Bias-Free Learning and Search
  Building on the view of machine learning as search, we demonstrate the
necessity of bias in learning, quantifying the role of bias (measured relative
to a collection of possible datasets, or more generally, information resources)
in increasing the probability of success. For a given degree of bias towards a
fixed target, we show that the proportion of favorable information resources is
strictly bounded from above. Furthermore, we demonstrate that bias is a
conserved quantity, such that no algorithm can be favorably biased towards many
distinct targets simultaneously. Thus bias encodes trade-offs. The probability
of success for a task can also be measured geometrically, as the angle of
agreement between what holds for the actual task and what is assumed by the
algorithm, represented in its bias. Lastly, finding a favorably biasing
distribution over a fixed set of information resources is provably difficult,
unless the set of resources itself is already favorable with respect to the
given task and algorithm.
