Inductive Bias

• References :

  • Reading:
    • Tom Mitchell Lectures slides of chapter 2
    • Tom Mitchell, Machine Learning Chapter 2
  • To Read:
    • https://en.wikipedia.org/wiki/Inductive%5Fbias

• Questions :

The inductive bias of a learning algorithm is the set of assumptions that the learner uses to predict outputs given inputs that it has not encountered.

• Consider a concept learning algorithm L for the set of instances X. Let c be an arbitrary concept defined over X, and let \(D_c\) = {<x,c(x)>} be an arbitrary set of training examples of c. Let \(L(x_i, D_c)\) denote the classification assigned to the instance \(x_i\) by L after training on the data \(D_c\). The inductive bias of L is any minimal set of assertions/assumptions B such that for any target concept c and corresponding training examples \(D_c\).
  • \( ( \forall x_i \in X) [ (B \land D_c \land x_i) \vdash L(x_i, D_c) ] \)
  • where the notation y \(\vdash\) z indicates that z follows deductively from y (i.e., that z is provable from y).

Fundamental Property of inductive inference

• a learner that makes no a priori assumptions regarding the identity of thetarget concept has no rational basis for classifying any unseen instances.
  • This is the futility of Bias-Free Learning