The Futility of Bias-Free Learning

Inductive learning requires some form of prior assumptions, or inductive bias

Definition:

Consider a concept learning algorithm L for the set of instances X.

• Let c be an arbitrary concept defined over X
• Let Dc  = {(x , c(x))} be an arbitrary set of training examples of c.
• Let L (x , D ) denote the classification assigned to the instance xi by L after training on the data Dc.
• The inductive bias of L is any minimal set of assertions B such that for any target concept c and corresponding training examples Dc.
•  (" áxi Î X ) [(B Ù Dc Ù xi) ├ L (xi, Dc )]

The below figure explains

• Modelling inductive systems by equivalent deductive systems.
• The input-output behavior of the CANDIDATE-ELIMINATION algorithm using a hypothesis space H is identical to that of a deductive theorem prover utilizing the assertion "H contains the target concept." This assertion is therefore called the inductive bias of the CANDIDATE-ELIMINATION algorithm.
• Characterizing inductive systems by their inductive bias allows modelling them by their equivalent deductive systems. This provides a way to compare inductive systems according to their policies for generalizing beyond the observed training data.