Module 1 Introduction to Machine Learning and Prerequisites

Vocabulary flashcards covering key ML concepts, PAC theory, version spaces, hypothesis concepts, and common algorithms from the lecture notes.

Machine Learning (ML)

A field where systems learn from past experiences and data to improve performance, as defined by learning from experience (E) with respect to tasks (T) and a performance measure (P).

Learning Paradigms

Categories of ML such as supervised learning, unsupervised learning, and reinforcement learning used to learn from data or interactions.

PAC Learning

Probably Approximately Correct learning; a theoretical framework describing how much data is needed for reliable generalization to unseen data.

ε (epsilon)

The upper bound on the error rate of a hypothesis on unseen data in PAC learning.

δ (delta)

The probability of failure in achieving the ε-accuracy; confidence is 1 minus δ.

Version Space

The set of all hypotheses in the hypothesis space that are consistent with the observed training examples.

Target Concept

The true boolean-valued function to be learned, denoted as c, defined over the instance space.

Hypothesis

A candidate function h in the hypothesis space that maps instances to labels (0/1) to approximate the target concept.

Hypothesis Space (H)

The set of all hypotheses the learner may consider, such as conjunctions of literals in some tasks.

EnjoySport

A toy concept-learning task where the goal is to learn when EnjoySport is true based on attributes like Sky, AirTemp, Humidity, etc.

Positive Example

An instance x for which the target concept c(x) equals 1 (belongs to the concept).

Negative Example

An instance x for which the target concept c(x) equals 0 (does not belong to the concept).

Inductive Learning Hypothesis

The assumption that hypotheses fitting the training data well will also fit unseen data if the training set is sufficiently large.

Inductive Learning

The process of deriving general rules or hypotheses from specific training examples.

FIND-S Algorithm

Starts with the most specific hypothesis and only generalizes to cover positive examples; ignores negative examples.

Most General Hypothesis

The broadest hypothesis, often with “don’t care” values (e.g., with ? placeholders).

Most Specific Hypothesis

The narrowest hypothesis, typically the fully constrained form (often with φ or fully specified attributes).

Hypothesis Representation

The way hypotheses are encoded, such as conjunctions of attribute constraints.

Conjunctions of Literals

A common hypothesis form where multiple attribute constraints are combined using AND.

Don’t Care (?)

A placeholder value indicating that an attribute can take any value in a constraint.

ɸ (phi)

The symbol for the empty set of instances, representing no positive coverage.

Target Function c

The true function mapping each instance to 0 or 1 in a learning task.

Positive Training Example

A training pair

Negative Training Example

A training pair

Training Sample

The set of examples used to train a learning algorithm.

Validation Sample

The set of examples used to tune the parameters of a learning algorithm.

Test Sample

The set of examples used to evaluate the performance of a learned model on unseen data.

Loss Function

A function that measures the difference between predicted labels and true labels.

Features

The set of attributes (attributes or attributes vectors) associated with each example.

Labels

The values or categories assigned to examples (the target outputs).