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

I. Foundations of Machine Learning

Algorithm Characteristics and Analysis

An algorithm is a finite sequence of well-defined instructions. Key characteristics:

• Input: Zero or more quantities.

• Output: At least one quantity.

• Definiteness: Each step precisely defined.

• Effectiveness: Each step feasible with basic operations.

• Finiteness: Terminates after finite steps.

Tools to Analyze Algorithms

• Time Complexity: Measures execution time as function of input size, expressed using Big O notation (worst-case), Omega (best-case), Theta (average-case).

• Space Complexity: Memory required during execution.

[!TIP] For exams, focus on deriving Big O for loops, recursion (Master Theorem), and common ML algorithms (e.g., O(n) for linear regression training).

Well-Posed Learning Problems

A learning problem is well-posed if:

1. Task (T): Clear objective (e.g., classification, regression).

2. Performance Measure (P): Quantifiable metric (e.g., accuracy, MSE).

3. Experience (E): Data source for learning (e.g., training dataset).

Example: Spam filtering—Task: classify emails; P: accuracy; E: labeled emails.

Data Description and Preparation

• Data Types: Numerical (continuous, discrete), Categorical (nominal, ordinal).

• Preparation Steps:

  1. Cleaning: Handle missing values (imputation, removal), outliers.

  2. Transformation: Normalization (min-max, z-score), encoding (one-hot, label).

  3. Feature Engineering: Create new features, dimensionality reduction (PCA).

Divide and Conquer Technique

• Break problem into smaller subproblems, solve recursively, combine solutions.

• Example: Merge sort (divide array, sort halves, merge).

• Complexity: Often O(n log n) for sorting.

Dynamic Programming in Machine Learning

• Used for optimization with optimal substructure and overlapping subproblems.

• Example: Viterbi algorithm for HMMs (finding most likely hidden state sequence).

• Approach: Memoization (top-down) or tabulation (bottom-up).

Lazy and Eager Learning

• Lazy Learning: Delays generalization until query time.

  • Example: k-Nearest Neighbors (stores all training data).

  • Pros: Adapts to new data easily; Cons: Slow prediction, high memory.

• Eager Learning: Constructs general model during training.

  • Example: Decision trees, neural networks.

  • Pros: Fast prediction; Cons: Retraining needed for new data.

II. Supervised Learning

A. Decision Trees

Recursive Induction

• Top-down, greedy approach:

  1. Select best attribute to split (using entropy/Gini).

  2. Create child nodes for each attribute value.

  3. Recurse on subsets until stopping condition (pure node, max depth).

• Algorithms: ID3 (entropy), C4.5 (gain ratio), CART (Gini impurity).

Entropy and Information Gain

• Entropy measures impurity of a set S:

$$H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i$$

where \(p_i\) is proportion of class i in S.

• Information Gain (IG) for attribute A:

$$IG(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)$$

where \(S_v\) is subset where A = v.

Calculation Example (from Paper B):

Dataset:

| Sample | Credit Score | Loan Approved |

|--------|--------------|---------------|

| 1 | High | Yes |

| 2 | Medium | No |

| 3 | Low | No |

| 4 | High | Yes |

| 5 | Medium | Yes |

| 6 | Low | No |

| 7 | High | No |

• Total samples: 7. Loan Approved: Yes (3), No (4).

• \(H(S) = -\frac{3}{7}\log_2\frac{3}{7} - \frac{4}{7}\log_2\frac{4}{7} \approx 0.985\).

• For Credit Score:

• High (3 samples: 2 Yes, 1 No): \(H(\text{High}) \approx 0.918\).

• Medium (2 samples: 1 Yes, 1 No): \(H(\text{Medium}) = 1.0\).

• Low (2 samples: 0 Yes, 2 No): \(H(\text{Low}) = 0\).

• Weighted avg: \(\frac{3}{7} \times 0.918 + \frac{2}{7} \times 1.0 + \frac{2}{7} \times 0 \approx 0.679\).

• \(IG(\text{Credit Score}) = 0.985 - 0.679 = 0.306\).

\boxed{IG(\text{Credit Score}) \approx 0.306}

Handling Noisy Data

• Pruning: Remove branches that fit noise (pre-pruning: stop early; post-pruning: grow full tree then trim).

• Ensemble Methods: Use bagging/boosting to reduce variance.

• Robust Splitting Criteria: Use gain ratio or chi-square test to avoid overfitting noisy attributes.

Application in Game Development

• NPC behavior trees (e.g., combat decisions: attack, defend, flee).

• Real-time strategy: unit movement, resource management.

• DiagramSEARCH: decision tree for game NPC behavior

B. Neural Networks

Multi-Layer Perceptron: Architecture and Learning Process

• Architecture:

  • Input layer (features), one or more hidden layers, output layer (predictions).

  • Fully connected: each neuron in layer l connected to all in layer l+1.

  • Activation functions: Sigmoid, ReLU, tanh (introduce non-linearity).

• Learning Process (Backpropagation):

  1. Forward Pass: Compute output for given input.

  2. Loss Calculation: e.g., MSE for regression, cross-entropy for classification.

  3. Backward Pass: Compute gradient of loss w.r.t. weights using chain rule.

  4. Weight Update: \(w_{ij} \leftarrow w_{ij} - \alpha \frac{\partial \mathcal{L}}{\partial w_{ij}}\), where \(\alpha\) is learning rate.

• Optimizers: SGD, Adam, RMSprop.

C. Linear and Least Squares Methods

Least Squares Methods

• Objective: Minimize sum of squared errors (SSE) between predicted and actual values.

• For linear regression: \(h(x) = w^T x\), minimize \(J(w) = \frac{1}{2} \sum_{i=1}^n (y_i - w^T x_i)^2\).

• Closed-form Solution: \(w = (X^T X)^{-1} X^T y\) (if \(X^T X\) invertible).

Least Squared Error Hypothesis

• Hypothesis function: \(h(x) = w_0 + w_1 x_1 + \dots + w_p x_p\).

• Assumes linear relationship, errors normally distributed, homoscedasticity.

Linear Regression using Gradient Descent

• Gradient Descent: Iterative optimization:

$$w_j := w_j - \alpha \frac{\partial J(w)}{\partial w_j}$$

where \(\frac{\partial J}{\partial w_j} = -\sum_{i=1}^n (y_i - w^T x_i) x_{ij}\).

• Steps:

  1. Initialize weights randomly.

  2. Repeat until convergence: compute gradient, update weights.

  3. Learning rate \(\alpha\) controls step size.

Gradient Descent Delta Rule

• Specific to perceptron (single-layer NN):

$$\Delta w_i = \alpha (t - y) x_i$$

where \(t\) is target, \(y\) is output.

• Updates weights to reduce error for misclassified points.

III. Ensemble Methods

Bagging vs Boosting

Random Forest Algorithm

• Ensemble of decision trees using bagging and feature randomness.

• Steps:

  1. For each tree: bootstrap sample from training data.

  2. At each split, consider random subset of features.

  3. Grow tree to maximum depth (no pruning).

  4. Prediction: majority vote (classification) or average (regression).

• Advantages: Reduces overfitting, handles high dimensions, estimates feature importance.

Robustness of Ensemble Methods

• Why robust?

  • Averages out biases and variances of individual models.

  • Less sensitive to noise and outliers.

  • Improves generalization by combining diverse hypotheses.

[!TIP] Ensemble methods often win competitions (e.g., Kaggle) due to robustness.

IV. Reinforcement Learning

Bellman Equations

• State-Value Function: \(V(s) = \max_a \mathbb{E}[R_{t+1} + \gamma V(s_{t+1}) \mid s_t = s, a_t = a]\).

• Action-Value Function: \(Q(s,a) = \mathbb{E}[R_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') \mid s_t = s, a_t = a]\).

• Key Idea: Value of state equals immediate reward plus discounted future value.

Q-learning vs SARSA

Policy Gradient Methods

• Directly optimize policy \(\pi(a \mid s; \theta)\) by gradient ascent on expected reward:

$$\nabla J(\theta) = \mathbb{E}_{\pi}[\nabla \log \pi(a \mid s; \theta) \cdot Q^{\pi}(s,a)]$$

• REINFORCE: Monte Carlo policy gradient.

• Advantage: Works with stochastic policies, continuous action spaces.

Temporal Difference Learning vs Monte Carlo Methods

Generative Adversarial Imitation Learning (GAIL)

• Imitation learning using GANs: discriminator distinguishes expert vs agent trajectories, generator (policy) tries to fool discriminator.

• Advantage: No need for reward function; learns from expert demonstrations.

Value Iteration and Policy Iteration

• Value Iteration:

  1. Initialize \(V(s)\) arbitrarily.

  2. Repeat: \(V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s,a)[R(s,a,s') + \gamma V_k(s')]\).

  3. Extract policy: \(\pi(s) = \arg\max_a \sum_{s'} P(s' \mid s,a)[R(s,a,s') + \gamma V(s')]\).

• Policy Iteration:

  1. Initialize policy \(\pi\).

  2. Policy Evaluation: compute \(V^{\pi}\).

  3. Policy Improvement: \(\pi' = \arg\max_a \sum_{s'} P(s' \mid s,a)[R(s,a,s') + \gamma V^{\pi}(s')]\).

  4. Repeat until \(\pi\) stable.

Recent Trends in RL Architectures

• Deep RL: DQN, A3C, PPO (deep neural nets for function approximation).

• Model-Based RL: Learn environment model, plan with it (e.g., Dreamer).

• Multi-Agent RL: Independent learners, communication, cooperation/competition.

• Meta-RL: Learn to learn (fast adaptation to new tasks).

V. Game AI and Theory

Game Theory and its Application to AI

• Game Theory: Study of strategic interactions where outcome depends on others' choices.

• Application to AI:

  • Multi-agent systems (e.g., autonomous vehicles, negotiation bots).

  • Mechanism design (auctions, voting).

  • Adversarial planning (chess, Go).

Minimax Algorithm and its Functions

• Minimax: For zero-sum games, assume opponent minimizes your payoff.

• Functions:

  • Evaluation Function: Heuristic score for non-terminal states.

  • Alpha-Beta Pruning: Skip branches that won't affect decision (reduces search space).

  • Iterative Deepening: Combine with depth-limited search for time constraints.

DiagramSEARCH: minimax algorithm tree with alpha-beta pruning

Rule-Based Systems

• Definition: Systems using IF-THEN rules to infer conclusions from facts.

• Example: Expert system for medical diagnosis:

  IF fever AND cough THEN possible flu.

• Components: Knowledge base (rules), inference engine (forward/backward chaining).

3D Representations: Static vs Kinematic

• Static: Fixed positions/orientations (e.g., environment geometry).

• Kinematic: Dynamic, includes movement and animation (e.g., character rigs, skeletal animation).

Components of Coordinated Movement

• Path Planning: Find collision-free path (A*, Dijkstra).

• Steering Behaviors: Seek, flee, arrive, obstacle avoidance (Reynolds).

• Animation Blending: Smooth transitions between animations.

• Inverse Kinematics: Compute joint angles for end-effector position.

Pathfinding Algorithms: A and Breadth-First Search*

• Breadth-First Search (BFS):

  • Unweighted graphs, guarantees shortest path.

  • Uses queue, explores level by level.

  • Time: O(V+E), Space: O(V).

• A Search*:

  • Uses heuristic \(h(n)\) (admissible, consistent).

  • \(f(n) = g(n) + h(n)\), where \(g(n)\) is cost from start.

  • Optimal if heuristic admissible.

DiagramSEARCH: A* algorithm example with heuristic

State Machines vs Behavior Trees

Finite State Machines

• Definition: Model with states, transitions, actions.

• Construction Example (from Paper A):

  Guard behavior:

  i) If no thief → Guard state.

  ii) Guard → see thief → Fight state; Fight → strong thief → Flee state.

  iii) Fight → losing → Flee state.

  iv) Flee → Guard state.

  States: {Guard, Fight, Flee}. Transitions:

  Guard --see_thief--> Fight

  Fight --strong--> Flee

  Fight --losing--> Flee

  Flee --escape--> Guard

Fuzzy Time Series and Markov Chains

• Fuzzy Time Series: Handle uncertainty in time series data using fuzzy logic (e.g., fuzzy sets for linguistic variables).

• Markov Chains: Stochastic model where next state depends only on current state.

• Combined: Fuzzy Markov chains for uncertain transitions (e.g., weather prediction with fuzzy states).

DiagramCANVAS: flowchart of fuzzy time series forecasting

Payoff Matrices and Nash Equilibrium

• Payoff Matrix: Represents payoffs for players in normal-form game.

• Nash Equilibrium: Strategy profile where no player can improve by unilateral deviation.

• Example (from Paper A):

  Solve:

  | A\B | I | II |

  |-----|-----|-----|

  | I | 5 | 9 |

  | II | 6 | 14 |

  For Player A: max min = max(5,6)=6 (choose II).

  For Player B: min max = min(9,14)=9 (choose I).

  Equilibrium: (II, I) with payoff (6,9).

Model of Game AI

• Perception: Sense environment (vision, audio).

• Decision: Choose action (planning, utility-based, behavior trees).

• Action: Execute (animation, movement).

DiagramSEARCH: game AI architecture diagram

Stages of Motor Learning

1. Cognitive Stage: Conscious effort, high error.

2. Associative Stage: Refining, less error.

3. Autonomous Stage: Automatic, minimal cognitive load.

Board Game Theory

• Combinatorial Game Theory: Analyze deterministic, perfect-information games (e.g., chess, Go).

• Concepts: Game tree, minimax, alpha-beta, solved games (e.g., checkers).

• Applications: AI for board games (AlphaGo, Stockfish).

VI. Data Handling and Preprocessing

Data Product Strategy and Types

• Steps for Strategy:

  1. Define problem and KPIs.

  2. Identify data sources.

  3. Build and validate model.

  4. Deploy as product (API, app).

  5. Monitor and update.

• Types:

  • Analytical: Insights/reports (e.g., Tableau dashboards).

  • Operational: Real-time decisions (e.g., recommendation systems).

  • Transactional: Embedded in processes (e.g., fraud detection in banking).

Data Extraction: Tools and Techniques in Python

• APIs: requests library (RESTful).

• Web Scraping: BeautifulSoup (HTML parsing), Scrapy (crawling).

• Databases: SQLAlchemy (SQL), pymongo (MongoDB).

• Files: pandas for CSV/Excel, json for JSON.

CSV and JSON Files in Python

• CSV:

  
  import pandas as pd
  
  df = pd.read_csv('data.csv')
  
  

• JSON:

  
  import json
  
  with open('data.json') as f:
  
      data = json.load(f)
  
  df = pd.DataFrame(data)
  
  

String to JSON Array Conversion

• Steps:

  1. Ensure string is valid JSON format (e.g., '[{"a":1},{"a":2}]').

  2. Use json.loads():

     
     import json
     
     json_str = '[{"a":1},{"a":2}]'
     
     arr = json.loads(json_str)  # arr is list of dicts
     
     

Text Processing Libraries in Python

• NLTK: Tokenization, stemming, lemmatization, POS tagging.

• spaCy: Industrial-strength, fast, pre-trained models.

• TextBlob: Simple API for common tasks.

• Gensim: Topic modeling (LDA), word embeddings (Word2Vec).

VII. Python Libraries and Implementation

NumPy: Numerical Operations

• Average: np.mean(arr)

• Variance: np.var(arr)

• Standard Deviation: np.std(arr)

• Matrix Inversion: np.linalg.inv(matrix)

Example:

import numpy as np

arr = np.array([1,2,3,4,5])

print(np.mean(arr)) # 3.0

print(np.var(arr)) # 2.0

print(np.std(arr)) # 1.4142

matrix = np.array([[1,2],[3,4]])

print(np.linalg.inv(matrix))

Matplotlib: Data Visualization

• Purpose: Create static, interactive, animated visualizations.

• Bar Chart Example:

  
  import matplotlib.pyplot as plt
  
  subjects = ['English','Hindi','Maths','Science','GK']
  
  marks = [69,90,76,88,91]
  
  plt.bar(subjects, marks)
  
  plt.xlabel('Subject')
  
  plt.ylabel('Marks')
  
  plt.title('Student Marks')
  
  plt.show()
  
  

DiagramSEARCH: matplotlib bar chart example

BeautifulSoup Library

• Parse HTML/XML documents.

• Example: Extract all links:

  
  from bs4 import BeautifulSoup
  
  import requests
  
  response = requests.get('https://example.com')
  
  soup = BeautifulSoup(response.text, 'html.parser')
  
  for link in soup.find_all('a'):
  
      print(link.get('href'))
  
  

JSON Parser

• Built-in json module:

  • json.loads(): parse JSON string to Python object.

  • json.dumps(): convert Python object to JSON string.

Gradient Descent in TensorFlow

• Use tf.GradientTape for automatic differentiation:

  
  import tensorflow as tf
  
  w = tf.Variable([1.0])
  
  with tf.GradientTape() as tape:
  
      loss = w**2 - 10*w + 25  # example loss
  
  grad = tape.gradient(loss, w)
  
  w.assign_sub(0.1 * grad)  # update
  
  

Mini-Batch Gradient Descent

• Use subset (batch) of data per update for efficiency and stability.

• Steps:

  1. Shuffle training data.

  2. For each batch: compute gradient, update weights.

  3. Repeat for epochs.

• Advantage: Faster than batch GD, less noisy than SGD.

VIII. Model Evaluation and Optimization

Precision and Recall in Classification

• Precision: \( \text{Precision} = \frac{TP}{TP + FP} \) (accuracy of positive predictions).

• Recall: \( \text{Recall} = \frac{TP}{TP + FN} \) (coverage of actual positives).

• F1-Score: Harmonic mean: \( F1 = 2 \cdot \frac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} \).

Example: Spam detection—high precision means few non-spam marked as spam; high recall means few spam missed.

Methods for Evaluating Classifiers

• Confusion Matrix: TP, TN, FP, FN.

• Accuracy: \(\frac{TP+TN}{Total}\) (misleading for imbalanced data).

• ROC-AUC: Trade-off between TPR and FPR.

• Cross-Validation: k-fold CV for robust estimate.

Holdout Method

• Split data into training set and test set (e.g., 70%-30%).

• Train on training set, evaluate on test set.

• Limitation: Sensitive to split; use cross-validation for better estimate.

Overfitting and Underfitting

• Overfitting: Model fits noise, high variance, poor generalization.

  • Causes: Too complex, insufficient data.

  • Remedies: Regularization (L1/L2), pruning, more data, dropout.

• Underfitting: Model too simple, high bias, poor performance on train/test.

  • Causes: Under-trained, wrong model.

  • Remedies: More features, complex model, less regularization.

[!TIP] Bias-variance tradeoff: ideal model balances both.

IX. Probabilistic Methods

Probabilistic Modeling in Machine Learning

• Models uncertainty using probability distributions.

• Examples:

  • Naive Bayes: \(P(y \mid x) \propto P(y) \prod P(x_i \mid y)\).

  • Hidden Markov Models (HMMs): States and observations with transition/emission probabilities.

  • Bayesian Networks: Directed acyclic graphs representing conditional dependencies.

Probabilistic Inference: Need and Usage

• Need: Real-world data is noisy/incomplete; probabilistic models handle uncertainty.

• Usage:

  • Predict posterior probabilities (e.g., \(P(\text{disease} \mid \text{symptoms})\)).

  • Decision making under uncertainty (e.g., medical diagnosis).

  • Algorithms: Exact inference (variable elimination), approximate (MCMC, variational inference).

X. Advanced Applications

Machine Learning in Graphs, Maps, and Map Searching

• Graph ML: Graph Neural Networks (GNNs) for node classification, link prediction.

• Map Searching:

  • Shortest path: A* with learned heuristics.

  • Traffic prediction: Time-series forecasting (LSTM).

  • Autonomous navigation: Reinforcement learning for path planning.

Stable Marriages Algorithms in Machine Learning

• Gale-Shapley Algorithm: Solve stable matching (e.g., residents to hospitals).

• ML Application:

  • Matching users to items (recommender systems).

  • Federated learning: Match clients to servers.

  • Job scheduling in distributed systems.

Interconnectedness on Personal Genomes

• Goal: Analyze genomic data to find gene interactions (epistasis) linked to diseases.

• ML Approach:

  • Use Bayesian networks or GNNs on gene regulatory networks.

  • Identify SNP combinations affecting traits.

• Challenge: High dimensionality, small sample size.

Prediction of Preterm Birth

• Problem: Predict early birth (<37 weeks) from clinical data.

• Data: Maternal history, biomarkers, ultrasound, EHRs.

• Models: Logistic regression, random forests, deep learning (RNNs for time-series).

• Impact: Early intervention, resource allocation.

Note: All topics aligned with RGPV past papers (Papers A, B, C, D). Key formulas and examples boxed for quick revision. Use diagrams for visual topics (pathfinding, FSM, game AI).