AD602PC: MACHINE LEARNING
[Link]. III Year II Sem. | R22 Syllabus | JNTU Hyderabad
UNIT - I: Learning, Supervised Learning & Concept Learning
1. Learning - Introduction
Definition (Tom Mitchell, 1997): A computer program is said to learn from experience E with respect to
task T and performance measure P, if its performance on T as measured by P improves with experience
E.
Why Machine Learning?
• Tasks too complex to program explicitly (e.g., speech recognition, image classification).
• Tasks requiring adaptation to changing environments (e.g., spam filters).
• Tasks where human expertise is hard to articulate (e.g., medical diagnosis).
• Mining large databases to discover useful patterns humans cannot manually find.
2. Types of Machine Learning
Type Description Examples
Supervised Learning Trained on labeled data (input-output pairs). Classification, Regression,
Learns f: X→Y. SVM, Decision Trees
Unsupervised No labeled outputs. Discovers hidden patterns in K-Means Clustering, PCA
Learning unlabeled data.
Semi-Supervised Mix of labeled and unlabeled data; uses large Text/image classification
Learning unlabeled sets. with few labels
Reinforcement Agent learns via rewards/penalties from Game playing (Chess, Go),
Learning environment interaction. Robotics
3. Supervised Learning
In supervised learning, the algorithm is provided training data consisting of input-output pairs (x, y). Goal:
Learn a function f: X → Y so that for new input x, predicted output f(x) closely approximates true y.
Two Main Tasks:
• Classification: Output is a discrete class label. E.g., spam/not-spam, disease detection.
• Regression: Output is a continuous numerical value. E.g., house price, stock forecasting.
Supervised Learning Process:
1. Collect and preprocess training data (features + correct labels).
2. Choose a model/hypothesis space (linear, tree-based, neural network).
3. Train: Minimize a loss function (MSE, Cross-Entropy) via optimization.
4. Validate: Evaluate on held-out validation set; tune hyperparameters.
5. Test: Final evaluation on unseen test data to measure generalization.
4. The Brain and the Neuron
ML draws inspiration from the human brain which contains ~1011 neurons interconnected via synapses —
forming a massively parallel processing system.
Biological Neuron:
• Dendrites: Receive input signals from other neurons.
• Cell Body (Soma): Integrates received signals; sums inputs.
• Axon: Transmits output signal to other neurons.
• Synapse: Junction between neurons; determines signal strength (analogous to weights in ANN).
Biological vs Artificial Neuron:
Biological Neuron Artificial Neuron
Dendrites Input features (x1, x2, ..., xn)
Synapse strength Weights (w1, w2, ..., wn)
Cell body integration Weighted sum: z = w.x + b
Firing threshold Activation function f(z)
Axon output Output: y = f(z)
5. Design a Learning System
Mitchell identifies four core components of any learning system:
• Performance Element: Takes actions/decisions using the learned knowledge.
• Critic: Provides feedback by evaluating performance against a fixed standard.
• Learning Element: Modifies the performance element based on critic's feedback — the actual
learning.
• Problem Generator: Suggests exploratory actions to discover new/better knowledge.
Key Design Choices:
• What data/experience will the system learn from?
• What exactly is to be learned (target function)?
• How to represent the target function (linear, tree, neural network)?
• What learning algorithm to use (gradient descent, ID3, backpropagation)?
• How to evaluate performance (accuracy, MSE, F1-score)?
6. Perspectives and Issues in Machine Learning
Perspectives (Different Views of ML):
• Statistical View: ML as statistical inference — learning a probability distribution from data samples.
• CS View: ML as a search through hypothesis space for the best fitting function.
• Neuroscience View: ML inspired by brain structure and biological learning mechanisms.
• Evolutionary View: Learning via selection, variation, survival of the fittest (Genetic Algorithms).
Key Issues / Challenges:
• Overfitting: Model memorizes noise in training data; fails to generalize to new data.
• Underfitting: Model too simple to capture underlying patterns in data.
• Bias-Variance Tradeoff: High bias = underfitting; High variance = overfitting; need optimal balance.
• Curse of Dimensionality: Data becomes sparse in high-dimensional spaces, making learning
harder.
• Noisy/Missing Data: Real-world imperfect data requires careful preprocessing and handling.
• Feature Selection: Choosing the right input features significantly impacts model performance.
• Interpretability: Complex models (deep learning) are often black-boxes, hard to explain.
7. Concept Learning Task
Concept Learning refers to inferring a boolean-valued function from training examples. The goal is to
learn a concept (category/class) from labeled examples of positive (+) and negative (−) instances.
Key Terminology:
• Concept / Target Function c: Boolean function c: X→{0,1}; maps instances to positive/negative
class.
• Instance (x): A single input example described by a set of attributes.
• Hypothesis (h): A candidate function from hypothesis space H that approximates concept c.
• Training Examples (D): Set of instances labeled as positive (+) or negative (−).
• Hypothesis Space (H): Set of all possible hypotheses the learner can consider.
• Consistent Hypothesis: h is consistent if it correctly classifies all training examples in D.
Hypothesis Representation:
Each attribute constraint in hypothesis h can be:
• '?': Any value accepted (wildcard).
• Specific value: E.g., Sky=Sunny — only this value accepted.
• 'null / empty': No value accepted — rejects all instances (most specific hypothesis).
Example (EnjoySport): h = <Sunny, ?, Normal, Strong, ?, Same> — represents concept 'enjoy sport when
sky is sunny, humidity normal, wind strong, forecast same.'
8. Concept Learning as Search
Concept learning = search problem through hypothesis space H for the hypothesis best fitting training
data. H is organized in a partial order based on generality.
General-to-Specific Ordering:
• h1 is MORE GENERAL than h2 (h1 >=g h2) if every instance positive under h2 is also positive under
h1.
• Most General hypothesis: h = <?, ?, ?, ?, ?, ?> — classifies ALL instances as positive.
• Most Specific hypothesis: h = <null,...,null> — classifies NO instance as positive.
• Learner searches from specific to general (or vice versa) to find consistent hypotheses.
9. Finding a Maximally Specific Hypothesis — FIND-S Algorithm
FIND-S algorithm finds the most specific hypothesis consistent with all positive training examples. It
ignores negative examples.
Algorithm Steps:
• Initialize h to most specific hypothesis: h = <null, null, ..., null>.
• For each POSITIVE training example x:
• For each attribute constraint ai in h:
• If ai is satisfied by x: do nothing.
• Else: generalize ai to next more general constraint that covers x.
• Output final hypothesis h.
Limitations of FIND-S:
• Cannot detect inconsistent/noisy training data.
• Ignores negative examples entirely.
• Outputs only ONE hypothesis — may miss other equally consistent ones.
• No indication whether the hypothesis is unique or if multiple solutions exist.
10. Version Spaces and Candidate Elimination Algorithm
Version Space (VS):
The Version Space VS(H,D) is the subset of hypotheses from H that are consistent with ALL training
examples in D. It represents all possible correct target concepts.
Two Boundaries of Version Space:
• S Boundary (Specific): Set of maximally SPECIFIC consistent hypotheses. Starts as most specific
h.
• G Boundary (General): Set of maximally GENERAL consistent hypotheses. Starts as most general
h.
VS = {h in H | exists s in S, exists g in G such that g >=g h >=g s} — all hypotheses between S and G.
Candidate Elimination Algorithm Steps:
• Initialize: S = {most specific h} = {<null,...,null>}; G = {most general h} = {<?,...,?>}.
• For each POSITIVE training example d+:
• Remove from G any hypothesis inconsistent with d+.
• For each s in S not consistent with d+: generalize s minimally to cover d+.
• Remove from S any hypothesis more general than another in S.
• For each NEGATIVE training example d-:
• Remove from S any hypothesis inconsistent with d-.
• For each g in G inconsistent with d-: specialize g minimally to exclude d-.
• Remove from G any hypothesis more specific than another in G.
• Output final version space [S, G].
Advantages over FIND-S:
• Considers BOTH positive and negative training examples.
• Outputs the ENTIRE set of consistent hypotheses (complete representation).
• Can detect if training data is inconsistent (S and G fail to converge/empty VS).
• Can determine if the learned concept is unique or ambiguous.
11. Linear Discriminants
A Linear Discriminant separates classes using a linear boundary (line in 2D, hyperplane in nD). Decision
boundary equation: w . x + b = 0, where w = weight vector, b = bias.
11.1 The Perceptron
The Perceptron (Rosenblatt, 1958) is the simplest neural network — a single-layer linear binary classifier.
Perceptron Components:
• Inputs: x = (x1, x2, ..., xn) — feature vector.
• Weights: w = (w1, w2, ..., wn) — learned parameters.
• Bias: b (or w0) — shifts the decision boundary.
• Net Input (Weighted Sum): z = w1x1 + w2x2 + ... + wnxn + b.
• Activation: Step function → Output y = +1 if z >= 0, else y = -1.
Perceptron Learning Rule (Weight Update):
w <-- w + n*(t - y)*x and b <-- b + n*(t - y)
where n = learning rate (0 < n <= 1), t = target/true output, y = predicted output.
Perceptron Convergence Theorem: If training data is linearly separable, Perceptron Learning is guaranteed
to converge to a perfect classifier in finite steps.
11.2 Linear Separability
A dataset is linearly separable if a hyperplane exists that perfectly divides positive from negative
examples with NO misclassification.
• In 2D: A straight line separates the two classes.
• In 3D: A plane separates the two classes.
• In n-D: A hyperplane (n-1 dimensional) is the decision boundary.
• XOR problem: Classic NON-linearly separable problem — cannot be solved by single Perceptron.
• Non-linearly separable data requires Multi-Layer Perceptrons (MLP) or kernel methods (SVM).
11.3 Linear Regression
Linear Regression is a supervised learning algorithm for predicting a continuous output using a linear
relationship between input features and output variable.
Model Equation:
y_hat = w0 + w1*x1 + w2*x2 + ... + wn*xn = w . x + b
Key Concepts:
• Cost Function (MSE): J(w) = (1/2m) * Sum(y_hat_i - y_i)^2 — minimized to find optimal weights.
• Gradient Descent: Iterative optimization: w <-- w - n*(dJ/dw). Moves weights toward minimum loss.
• Normal Equation: Closed-form: w = (X^T X)^(-1) X^T y — direct solution without iteration.
• Key Assumptions: Linearity, independence of errors, constant variance, normality of residuals.
• Evaluation Metrics: MSE, RMSE, MAE (Mean Absolute Error), R-squared (goodness of fit).
Quick Revision - Unit I Key Points
[OK] ML Definition: Program learns from Experience E on Task T, improving Performance P (Mitchell, 1997)
[OK] 4 Types: Supervised (labeled data) | Unsupervised (no labels) | Semi-supervised | Reinforcement
[OK] Biological Neuron analogy: Dendrites=Inputs, Synapse=Weights, Cell Body=Sum, Axon=Output
[OK] Learning System = Performance Element + Critic + Learning Element + Problem Generator
[OK] Key Issues: Overfitting, Underfitting, Bias-Variance Tradeoff, Curse of Dimensionality
[OK] Concept = Boolean function c: X->{0,1} learned from labeled examples
[OK] FIND-S: Initializes most specific h; generalizes only on positive examples; ignores negatives
[OK] Version Space = all consistent hypotheses between S boundary (specific) and G boundary (general)
[OK] Candidate Elimination: Updates both S and G using positive AND negative examples
[OK] Perceptron: Single-layer linear classifier; converges if data is linearly separable
[OK] XOR is NOT linearly separable -- needs Multi-Layer Perceptron (MLP)
[OK] Linear Regression: y_hat = w.x+b; minimizes MSE using Gradient Descent or Normal Equation
Prepared for AD602PC Machine Learning | JNTU Hyderabad | R22 [Link] AI & DS