Inductive Bias and Hypothesis Space:

Hypothesis Space $H$: Set of all hypotheses / functions learner can represent. e.g., for Boolean concepts with $n$ attributes, $|H|=3^n$ (general-to-specific). For linear regression, $H=\{w^T x + b : w\in\mathbb{R}^d\}$.

Inductive Bias: Set of assumptions that learner uses to generalize beyond training data and choose one hypothesis among many consistent ones. Without bias, learner cannot generalize (cannot classify unseen instances).

Mitchell definition: Any basis for choosing one generalization over another beyond consistency with data.

Types:

1. Language / Restriction Bias: Restrict $H$ (e.g., only conjunctive hypotheses, only linear separators). If true concept not in $H$, cannot learn.
2. Preference / Search Bias: Prefer certain hypotheses (e.g., Occam's razor — prefer simpler, smaller trees, smaller weights; regularization prefers low norm). $H$ may still contain all, but search ordered.

Example — Candidate Elimination: $H$ = conjunctions of attributes. Bias: $c \in H$ is conjunctive — cannot learn disjunction $X\lor Y$.

Example — Decision Tree: Bias: prefers shorter trees (information gain heuristic) that fit data.

Why needed: No Free Lunch — without bias, all hypotheses consistent with data are equally valid, no prediction on unseen point. Bias makes learning possible but limits learnability; incorrect bias → underfitting.

Relation to Occam's Razor: "Prefer simplest hypothesis fitting data" — implemented via MDL, regularization, pruning.