Machine Learning for Data Science (AL-702 (D)) Unit 2 Notes

UNIT 2: MACHINE LEARNING FUNDAMENTALS AND APPLICATIONS

1. ALGORITHMIC FOUNDATIONS IN MACHINE LEARNING

Characteristics of Algorithms

An algorithm is a finite sequence of well-defined, executable instructions for solving a problem. Key characteristics:

Definiteness: Each step is precisely defined.
Input/Output: Zero or more inputs, at least one output.
Effectiveness: Each instruction is basic enough to be carried out.
Finiteness: Terminates after a finite number of steps.
Correctness: Produces the correct output for all valid inputs.

[!TIP] Exam often asks to list and explain these characteristics with examples from ML (e.g., gradient descent as an algorithm).

Tools for Algorithm Analysis

Time Complexity: Measures computational time as a function of input size. Expressed using Big O notation (e.g., $O(n)$, $$\displaystyle O(n^2) $$, $O(\log n)$).
Space Complexity: Measures memory usage.
Empirical Evaluation: Actual runtime measurement on specific hardware/data.
Best/Average/Worst-case Analysis: Different scenarios for performance.

Big O Notation Rules:

Drop constants and lower-order terms.
Example: $$\displaystyle 3n^2 + 2n + 1 \rightarrow O(n^2) $$.

Well-Posed Learning Problems (Tom Mitchell)

A learning problem is well-posed if:

Task (T): The goal (e.g., classification, regression).
Experience (E): Data or interactions available.
Performance Measure (P): Metric to evaluate success (e.g., accuracy, MSE).

Example: Task $T$ = predict house prices; Experience $E$ = historical housing data; Performance $P$ = mean squared error.

Divide and Conquer Technique

Principle: Break problem into smaller subproblems, solve recursively, combine solutions. Steps:

Divide: Split input into smaller instances.
Conquer: Solve subproblems recursively.
Combine: Merge sub-solutions.

Example in ML: Decision Tree Construction (e.g., ID3, C4.5).

At each node, split dataset based on feature that maximizes information gain.
Recursively build left/right subtrees until stopping condition (pure node or max depth).

[!TIP] Recursive induction in decision trees is a classic divide-and-conquer application.

Dynamic Programming in Machine Learning

Principle of Optimality: Optimal solution contains optimal solutions to subproblems. Uses memoization (store results of subproblems to avoid recomputation).

Examples:

Sequence Alignment (bioinformatics): Needleman-Wunsch algorithm.
Value Iteration (Reinforcement Learning): Solves Bellman equation $$\displaystyle V^*(s) = \max_a \mathbb{E}[R_{t+1} + \gamma V^*(S_{t+1})|S_t=s, A_t=a] $$ iteratively.
Policy Iteration: Alternates between policy evaluation and improvement.

[!TIP] Dynamic programming is key for optimal planning in RL; memoization reduces exponential time to polynomial.

2. DATA HANDLING AND MODEL EVALUATION

Data Description and Preparation

Data Types: Numerical (continuous, discrete), Categorical (nominal, ordinal).
Summary Statistics: Mean, median, mode, variance, standard deviation, quartiles.
Handling Missing Values: Deletion (listwise, pairwise), Imputation (mean/median/mode, regression, KNN).
Feature Scaling/Normalization:
- Min-Max Scaling: $$\displaystyle X' = \frac{X - X_{\min}}{X_{\max} - X_{\min}} $$ (range [0,1]).
- Z-score Normalization: $$\displaystyle X' = \frac{X - \mu}{\sigma} $$ (mean 0, std 1).
- Crucial for distance-based algorithms (k-NN, SVM, gradient descent).

Holdout Method

Procedure: Randomly split data into training set, validation set (for hyperparameter tuning), and test set (for final evaluation).
Common Splits: 60-20-20 or 70-15-15.
Stratified Sampling: Maintains class distribution in splits (important for imbalanced datasets).
Advantages: Simple, fast.
Disadvantages: High variance if data small; test set performance may be unstable.

[!TIP] Avoid data leakage: Ensure preprocessing (scaling, imputation) is fit on training set only, then applied to validation/test sets.

3. LEARNING PARADIGMS AND PROBABILISTIC APPROACHES

Lazy vs. Eager Learning

Aspect	Lazy Learning (e.g., k-NN)	Eager Learning (e.g., Decision Trees, Neural Nets)
Training Phase	Minimal; just stores training data.	Computationally expensive; builds explicit model.
Prediction Phase	Expensive; computes distances to all stored instances.	Fast; uses learned model for prediction.
Generalization	Local; sensitive to noise/irrelevant features.	Global; may overfit if model complex.
Adaptability	Easy to update with new data.	Requires retraining.

Probabilistic Modelling in Machine Learning

Bayesian Networks: Directed acyclic graphs representing conditional dependencies among variables. Nodes = random variables; edges = conditional dependencies.
Generative vs. Discriminative:
- Generative (e.g., Naïve Bayes, Gaussian Mixture Models): Models joint distribution $P(X,Y)$; can generate new data.
- Discriminative (e.g., Logistic Regression, SVM): Models conditional distribution $P(Y|X)$; focuses on decision boundary.

Probabilistic Inference

Goal: Compute posterior probabilities given evidence.
Exact Inference: Variable Elimination (sums out hidden variables), Junction Tree Algorithm. Computationally expensive (NP-hard in general).
Approximate Inference: Markov Chain Monte Carlo (MCMC), Variational Inference. Used when exact inference intractable.
Role: Handles uncertainty, missing data, and complex dependencies.

4. OPTIMIZATION AND HYPOTHESIS FORMATION

Gradient Descent and Delta Rule

Gradient Descent:

Iterative optimization: $$\displaystyle \theta_{t+1} = \theta_t - \eta \nabla J(\theta_t) $$.
Batch GD: Uses entire dataset per update (stable but slow).
Stochastic GD (SGD): Uses one sample per update (noisy but fast, escapes local minima).
Learning Rate ($\eta$): Critical hyperparameter; too large → divergence; too small → slow convergence.
Convergence: For convex problems, GD converges to global minimum; for non-convex, to local minimum.

Delta Rule (for single-layer perceptron):

Update rule: $$\displaystyle \Delta w_{ij} = \eta (t_j - y_j) x_i $$, where $$\displaystyle t_j $$ = target, $$\displaystyle y_j $$ = output, $$\displaystyle x_i $$ = input.
Minimizes squared error $$\displaystyle E = \frac{1}{2} \sum (t_j - y_j)^2 $$ via gradient descent.
Only converges for linearly separable data.

Least Squared Error Hypothesis

Linear Regression: Predict $$\displaystyle y = \theta^T x $$.
Cost Function: $$\displaystyle J(\theta) = \frac{1}{2m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 $$.
Normal Equation (closed-form solution):

$$\theta = (X^TX)^{-1}X^Ty$$

Geometric Interpretation: $\hat{y}$ is orthogonal projection of $y$ onto column space of $X$.
Assumptions: Linear relationship, homoscedasticity, no multicollinearity, normal errors.

[!TIP] Normal equation avoids choosing learning rate but $$\displaystyle O(n^3) $$ complexity; use GD for large $n$.

5. APPLICATION-SPECIFIC MACHINE LEARNING

ML in Graphs, Maps, and Map Searching

Graph Representation: Nodes (locations), edges (paths/roads) with weights (distance/time).
Shortest Path Algorithms:
- Dijkstra's: Non-negative weights, greedy.
- A*: Uses heuristic $h(n)$; optimal if heuristic admissible ($h(n) \leq$ true cost).
Recommendation Systems: Use graph-based collaborative filtering (user-item bipartite graph).
Spatial Data Analysis: Clustering (DBSCAN), regression for geographic trends.

Stable Marriages Algorithms in ML

Problem: Match two sets (e.g., jobs/applicants, servers/requests) with preferences; find stable matching (no pair prefers each other over current match).
Gale-Shapley Algorithm:
1. Proposing set (e.g., men) propose to preferred partner.
2. Receiving set (e.g., women) tentatively accept best proposal, reject others.
3. Repeat until all matched.
Applications: Matching markets (residency matching, school choice), resource allocation in distributed systems.

Interconnectedness on Personal Genomes

Network Analysis: Genomic data as networks (genes as nodes, interactions as edges).
Feature Correlation: Identify gene-gene interactions, co-expression networks (WGCNA).
Population Genetics: Model allele frequencies, linkage disequilibrium.
ML Applications: Predict disease risk, identify biomarkers using graph neural networks (GNNs).

Prediction of Preterm Birth

Data Sources: Electronic health records (EHR), ultrasound, biomarkers, demographics.
Relevant Features: Maternal age, history of preterm birth, cervical length, fetal fibronectin, stress levels.
Model Types: Logistic regression, random forests, deep learning (RNNs for time-series data).
Evaluation Metrics: Sensitivity (recall), specificity, AUC-ROC (critical for early detection).
Challenges: Class imbalance (preterm rare), noisy data, ethical considerations.

[!TIP] For preterm birth, high recall is often prioritized to minimize false negatives (missed high-risk cases).

Account

Machine Learning for Data Science (AL-702 (D)) - Unit 2 Short Notes