Hypothesis Space and Inductive Bias:

Hypothesis Space $H$: Set of all hypotheses learner can potentially output. Defines representational capacity.

• Example Boolean $n$ attributes: $|H|=2^{2^n}$ all functions, but conjunctive class $H_c$ size $3^n$ (each attribute +/−/don't care).
• For linear models: $H=\{w^T x + b : w\in\mathbb{R}^d, b\in\mathbb{R}\}$.
• Larger $H$ → higher variance, needs more data, may overfit; smaller $H$ → may underfit if true concept outside $H$.

Inductive Bias: Assumptions learner uses to generalize beyond training data and prefer one consistent hypothesis over others. Without bias, no generalization.

Mitchell: "any basis for choosing one generalization over another, other than strict consistency with observed training instances."

Types:

• Restriction bias: Restrict $H$ (e.g., only linear separators) — strong, excludes some concepts.
• Preference bias: Order search (e.g., Occam's razor — prefer simpler hypothesis, shorter decision tree, smaller $||w||$, regularization). $H$ contains all but search prefers simpler.

Example: Candidate Elimination with conjunctions: bias = target is conjunction → cannot learn $X\lor Y$. Decision Tree preference for shorter trees with high information gain.

Why needed: No bias → all hypotheses consistent with data equally valid, learner cannot classify unseen instance (No Free Lunch). Bias enables generalization but if wrong → inductive bias mismatch causes error.

Relation: Hypothesis space + bias determine learnability; PAC bounds show sample complexity $m\propto \log|H|$ or $VC(H)$. Good bias (e.g., smoothness for images) reduces sample needs.