Machine Learning Part C - Hypothesis Space and Inductive Bias

Introduction

• Inductive learning/prediction: given examples of data (x, y).
• x = input feature values, y = output attribute.
• Aim: learn function f(x) mapping input vector to output.

Types of Supervised Learning

• Classification: f(x) is discrete.
• Regression: f(x) is continuous.
• Probability Estimation: f(x) is the probability of x.

Inductive Learning

• Given data, identify a function explaining the data.
• Unlike deduction, induction is not well-defined without restrictive assumptions.

Features and Feature Space

• Features: properties describing each instance quantitatively.
• Feature Vector: a vector of multiple features.
• Example: if describing with 10 features, a feature vector of size 10.
• Feature Space: n-dimensional space defined by features. Example:
  • Two features x1 and x2 defining a 2D space.
  • Instances as points/vectors in this space.

Classification Problem Illustration

• Two-class problem: Instances of class 1 (positive) and class 2 (negative).
• Training set: subset of instances marked as class 1 or class 2.
• Goal: learn function to predict class of new instance based on training data.
• Visualization: function (e.g., line) separating positive and negative instances.

Hypothesis Space

• Set of all possible legal functions from which a learning algorithm picks the best hypothesis.
• Need to define the hypothesis space before learning.

Function Representation

• Function in terms of features and language/class of function.
• Examples: linear functions, decision trees, neural networks, etc.

Hypothesis Space and Hypothesis

• Hypothesis Space (H): Set of all possible legal hypotheses.
• Learning Algorithm Output: a hypothesis (h) from H, based on data and constraints/bias.

Example with Boolean Features

• For N Boolean features:
  • Possible instances: 2^N.
  • Possible functions: 2^(2^N).
• Large hypothesis space necessitates restrictions.

Bias in Machine Learning

• Language Bias: restrictions on the type of functions (e.g., linear functions).
• Preference Bias: preferences within a chosen hypothesis language (e.g., simpler functions).

Inductive Bias

• Choosing a hypothesis space involves assumptions/biases.
• Bias can help restrict hypothesis space and improve learning efficacy.

Inductive Learning Hypothesis

• Hypothesis h approximates target function c well over a large training set.

Learning as Hypothesis Space Search

• Finding a hypothesis involves searching through the hypothesis space guided by bias and training data.

Errors in Machine Learning

• Bias Error: Incorrect assumptions/restrictions on hypothesis space.
• Variance Error: Differences in model estimation across different training sets.

Overfitting and Underfitting

• Overfitting: Model does well on training data but poorly on test data (often due to too few training examples or overly complex function).
• Underfitting: Model too simple to capture data nuances.

Conclusion

• Machine learning involves finding a function that generalizes well and managing errors (bias and variance) and fitting issues (overfitting/underfitting).

Important Concepts to Explore Further

• Different learning algorithms and how they handle bias and hypothesis space.
• Specifics of overfitting and underfitting.