UNIT 4: ADVANCED PREDICTIVE ANALYTICS TECHNIQUES

I. DATA PRODUCT STRATEGY AND MANAGEMENT

A. Steps for Building a Successful Data Product Strategy

1. Define Clear Business Objective: Align the data product with a specific, measurable business problem or opportunity (e.g., reduce customer churn by 10%).

2. Identify Key Stakeholders & Users: Understand who will use the product (data scientists, business analysts, customers) and their needs.

3. Assess Data Availability & Quality: Audit existing data sources, structure, and quality. Identify gaps requiring new collection or integration.

4. Choose Appropriate Technology Stack: Select tools for storage (data lake/warehouse), processing (Spark, Pandas), modeling (scikit-learn, TensorFlow), and deployment (APIs, dashboards).

5. Develop MVP & Iterate: Build a Minimum Viable Product with core predictive functionality. Gather user feedback and refine.

6. Establish Governance & Monitoring: Define data lineage, model versioning, performance metrics (e.g., prediction drift), and retraining schedules.

7. Plan for Scalability & Maintenance: Design for increasing data volume and user load. Ensure operational sustainability.

B. Types of Data Products Based on Functionality

II. DATA ENGINEERING AND PREPROCESSING

A. Data Extraction

• Tools & Techniques in Python:

  • APIs: requests library to fetch data from RESTful APIs (JSON/XML).

  • Web Scraping: BeautifulSoup (with requests) for parsing HTML/XML. Scrapy for large-scale, structured scraping.

  • Databases: SQLAlchemy (ORM) or pyodbc/psycopg2 for direct DB connections.

  • File Systems: os/glob for local file traversal.

B. Data Formats and Parsing

• CSV Files:

  
  import pandas as pd
  
  df = pd.read_csv('data.csv')  # Reading
  
  df.to_csv('output.csv', index=False)  # Writing
  
  

• JSON Files:

  
  import json
  
  # Reading
  
  with open('data.json') as f:
  
      data = json.load(f)  # Converts to Python dict/list
  
  # Writing
  
  with open('output.json', 'w') as f:
  
      json.dump(data, f, indent=4)
  
  # String to JSON Array
  
  json_string = '[{"id":1}, {"id":2}]'
  
  json_array = json.loads(json_string)
  
  

• JSON Parsers: Standard library json (fast, secure), simplejson (more features), ujson (ultra-fast for large files).

C. Text Processing (Python Libraries)

• NLTK: Comprehensive toolkit for tokenization, stemming, lemmatization, POS tagging, stopwords. Good for education/research.

• spaCy: Industrial-strength, optimized for performance. Provides pre-trained models for NER, dependency parsing. Faster than NLTK for production.

• TextBlob: Simple API for common tasks (sentiment analysis, translation) built on NLTK.

• Gensim: Specialized for topic modeling (LDA, LSI) and document similarity (Word2Vec, Doc2Vec).

D. Data Manipulation with NumPy

• Core Object: ndarray (n-dimensional array).

• Matrix Operations:

  
  import numpy as np
  
  A = np.array([[1, 2], [3, 4]])
  
  A_inv = np.linalg.inv(A)  # Matrix inverse
  
  

• Statistical Calculations:

  
  data = np.array([1, 2, 3, 4, 5])
  
  avg = np.mean(data)
  
  var = np.var(data, ddof=1)  # Sample variance
  
  std = np.std(data, ddof=1)
  
  

E. Data Visualization: Matplotlib

• Purpose: Foundational 2D plotting library for Python. Provides low-level control to create static, animated, and interactive visualizations.

• Applications: Histograms, scatter plots, line charts, bar charts, subplots, customization (labels, titles, legends).

• Creating a Bar Chart Example:

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

F. Data Preparation

1. Data Description: Use df.info(), df.describe(), df.head(), df.shape (Pandas) to understand structure, statistics, and missingness.

2. Handling Missing Values:

   • Deletion: Drop rows/columns (df.dropna()).

   • Imputation: Fill with mean/median/mode (df.fillna(df.median())), or use predictive models (KNN imputer).

   • Flagging: Add a binary column indicating imputation.

3. Handling Noisy Data:

   • Binning: Smooth data by binning (equal-width/frequency).

   • Regression: Fit a regression line to smooth outliers.

   • Clustering: Group similar instances and treat cluster centroids as clean data.

   • Manual Correction: If domain knowledge allows.

   • Robust Models: Use algorithms inherently resistant to noise (e.g., Random Forest).

[!TIP] Exam Focus: Be ready to write short Python code snippets for reading/writing CSV/JSON, creating a basic plot, and calculating NumPy statistics.

III. ADVANCED SUPERVISED LEARNING ALGORITHMS

A. Decision Trees

• Recursive Induction: Top-down, greedy process.

  1. Start with entire training set at root node.

  2. Select the best attribute (using Information Gain/Gini Index) to split the data.

  3. Create a branch for each attribute value, partitioning the data.

  4. Recursively repeat steps 2-3 on each branch until:

     • All instances belong to the same class (pure node).

     • No more attributes to split on.

     • Pre-pruning criteria met (e.g., minimum samples per leaf).

• Entropy & Information Gain:

  • Entropy (H): Measure of impurity/uncertainty in a set S.

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

    where $$\displaystyle p_i $$ is the proportion of class *i* in *S*, *c* is number of classes. Pure set has **Entropy = 0**.

*   **Information Gain (IG):** Reduction in entropy after splitting on attribute *A*.

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

    where $$\displaystyle S_v $$ is the subset of *S* for which attribute *A* has value *v*.

*   **Calculation Example (from past paper):**

    *   Total Entropy *H(S)* for 7 samples (4 Yes, 3 No):

        $$\displaystyle H(S) = -\left(\frac{4}{7}\log_2\frac{4}{7} + \frac{3}{7}\log_2\frac{3}{7}\right) \approx 0.985 $$

    *   Split on **Credit Score**:

        *   *High* (3 samples: 2 Yes, 1 No) → $H(High) \approx 0.918$

        *   *Medium* (2 samples: 1 Yes, 1 No) → $$\displaystyle H(Medium) = 1.0 $$

        *   *Low* (2 samples: 0 Yes, 2 No) → $$\displaystyle H(Low) = 0.0 $$

    *   $$\displaystyle IG(S, CreditScore) = 0.985 - \left(\frac{3}{7}*0.918 + \frac{2}{7}*1.0 + \frac{2}{7}*0.0\right) \approx 0.985 - 0.683 = 0.302 $$

• Handling Noisy Data:

  1. Pre-pruning: Stop tree growth early (set max_depth, min_samples_split).

  2. Post-pruning: Grow full tree, then remove branches that don't improve validation accuracy (cost-complexity pruning).

  3. Ensemble Methods: Use Random Forests (see below) which average many trees to reduce variance.

• Application in Game Development: Decision trees model NPC (Non-Player Character) behavior logic (e.g., if health < 30% AND enemy_near → flee). They are interpretable "if-then" rules for game AI.

B. Ensemble Methods

• Bagging vs Boosting:

  | Feature | Bagging (e.g., Random Forest) | Boosting (e.g., AdaBoost, XGBoost) | |-------------------|----------------------------------------------------|---------------------------------------------------| | Core Idea | Parallel, independent models. Reduce variance. | Sequential, dependent models. Reduce bias. | | Sampling | Bootstrap samples (with replacement). | Re-weight instances; focus on misclassified ones.| | Weighting | All models vote equally. | Models are weighted by their accuracy. | | Goal | Make complex models stable/variance reduction. | Convert weak learners into strong learners. | | Overfitting | Less prone (averaging reduces variance). | Can overfit if too many rounds/no regularization.|

• Random Forest Algorithm:

  1. For b = 1 to B (number of trees):

     • Draw a bootstrap sample from training data.

     • Grow a decision tree on this sample. At each split, randomly select m features from total M (m ≈ √M) and find the best split only among these m.

  2. Output prediction = majority vote (classification) or average (regression) of all trees.

  • Why Robust? Decorrelates trees via feature randomness and bootstrap sampling. Averaging reduces variance significantly. Handles high-dimensional data well and provides feature importance.

• Why Ensembles Outperform Individual Models?

  • Statistical: Averages many "weak" models (high variance, low bias) to produce a "strong" model with lower variance. Error reduction follows: $$\displaystyle E_{ensemble} = E_{individual} - Covariance_{models} $$. Ensembles aim to make covariance negative.

  • Computational: Algorithms like boosting perform iterative search in hypothesis space, escaping local minima better than a single model's greedy search.

  • Representational: Can represent more complex functions than any single model in the ensemble.

C. Neural Networks: Multi-Layer Perceptron (MLP)

• Architecture:

  • Input Layer: One neuron per feature. Passes signals forward.

  • Hidden Layer(s): One or more layers of neurons with non-linear activation functions (ReLU, Sigmoid, Tanh). This is where learning/complex pattern extraction happens.

  • Output Layer: Number of neurons = number of classes (classification, with Softmax) or 1 (regression, linear).

  • Fully Connected: Each neuron in layer l is connected to all neurons in layer l+1.

• Learning Process (Backpropagation):

  1. Forward Pass: Input data is propagated through the network. Each neuron computes: $$\displaystyle z = \sum w_i x_i + b $$, then applies activation $$\displaystyle a = f(z) $$.

  2. Compute Loss: Calculate error between network output and true label using a loss function (Cross-Entropy for classification, MSE for regression).

  3. Backward Pass (Backpropagation): Apply chain rule to compute gradient of loss w.r.t. every weight and bias in the network.

  4. Update Weights: Use an optimizer (e.g., Stochastic Gradient Descent, Adam) to update weights: $$\displaystyle w_{new} = w_{old} - \eta \cdot \frac{\partial Loss}{\partial w} $$.

  • This cycle repeats for many epochs until convergence.

D. Least Squares Methods

• Least Squared Error Hypothesis: The best-fitting model is the one that minimizes the sum of the squared differences (residuals) between observed values and predicted values.

$$\text{Minimize } SSE = \sum_{i=1}^{n} (y_i - \hat{y}_i)^2$$

• Linear Regression using Gradient Descent:

  1. Initialize weights ($w$) and bias ($b$) randomly.

  2. Forward Pass: $$\displaystyle \hat{y} = w^T X + b $$.

  3. Compute MSE Loss: $$\displaystyle L = \frac{1}{n} \sum (y - \hat{y})^2 $$.

  4. Compute Gradients:

     $$\displaystyle \frac{\partial L}{\partial w} = -\frac{2}{n} X^T (y - \hat{y}) $$

     $$\displaystyle \frac{\partial L}{\partial b} = -\frac{2}{n} \sum (y - \hat{y}) $$

  5. Update Parameters: $$\displaystyle w = w - \alpha \frac{\partial L}{\partial w} $$, $$\displaystyle b = b - \alpha \frac{\partial L}{\partial b} $$ ($\alpha$ = learning rate).

  6. Repeat steps 2-5 until convergence.

• Matrix Inversion (Closed-Form Solution): For ordinary least squares (OLS), the optimal weight vector is:

$$\mathbf{w} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$$

*   **Python Implementation:**

    ```python

    import numpy as np

    X = np.array([[1, x1], [1, x2], ...])  # With intercept column

    y = np.array([y1, y2, ...])

    w = np.linalg.inv(X.T @ X) @ X.T @ y

    ```

IV. REINFORCEMENT LEARNING

A. Core Concepts

• Markov Decision Process (MDP): Formalization of RL problems. Defined by tuple $(S, A, P, R, \gamma)$:

  • $S$: Set of states.

  • $A$: Set of actions.

  • $P(s' | s, a)$: State transition probability (Markov property: next state depends only on current state and action).

  • $R(s, a, s')$: Reward function.

  • $\gamma$: Discount factor ($0 \leq \gamma \leq 1$).

• Bellman Equations: Fundamental recursive equations defining optimal value functions.

  • State-Value Function $$\displaystyle V^*(s) $$: Maximum expected discounted return starting from state s.

$$V^*(s) = \max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V^*(s')]$$

*   **Action-Value Function $$\displaystyle Q^*(s,a) $$:** Maximum expected discounted return starting from state *s*, taking action *a*.

$$Q^*(s,a) = \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma \max_{a'} Q^*(s', a')]$$

• Temporal Difference (TD) Learning vs Monte Carlo (MC):

  | Feature | Temporal Difference (TD) | Monte Carlo (MC) | |----------------------|--------------------------------------------------|-------------------------------------------------| | Update Trigger | After every step (bootstrapping). | After end of episode. | | Bias/Variance | Bias (bootstrapping from current estimate). | Unbiased (uses actual return). | | Sample Efficiency| Higher (learns from incomplete sequences). | Lower (requires full episodes). | | Convergence | To $$\displaystyle V^\pi $$ for any policy (if learning rate decays properly). | To $$\displaystyle V^\pi $$ for any policy. | | Example | SARSA, Q-learning. | Every-Visit MC, First-Visit MC. |

B. Value-Based Methods

• Q-learning vs SARSA:

  | Aspect | Q-learning | SARSA | |----------------------|-------------------------------------------------|-------------------------------------------------| | Policy Type | Off-policy. Learns $$\displaystyle Q^* $$ independent of behavior policy. | On-policy. Learns $$\displaystyle Q^\pi $$ for the current behavior policy. | | Update Rule | $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)] $$ | $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s',a') - Q(s,a)] $$ where $a'$ is action actually taken in $s'$. | | Exploration | Can learn optimal policy even while exploring (uses $\max$). | Learns policy including exploration effects. | | Risk | Can be unstable in stochastic environments (max operator). | More stable, learns safer policies. |

• Value Iteration: Directly applies Bellman optimality equation iteratively until $V$ converges.

$$V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V_k(s')]$$

*   **Policy** is derived at the end: $$\displaystyle \pi(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V(s')] $$.

• Policy Iteration: Alternates between:

  1. Policy Evaluation: Compute $$\displaystyle V^\pi $$ for current (deterministic) policy $\pi$ (solve linear system).

  2. Policy Improvement: Make policy greedy w.r.t. $$\displaystyle V^\pi $$: $$\displaystyle \pi'(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V^\pi(s')] $$.

  • Repeat until $$\displaystyle \pi = \pi' $$ (policy stable).

C. Policy-Based Methods

• Policy Gradient Methods: Directly learn/optimize the policy function $\pi(a|s, \theta)$ (parameterized by $\theta$), without a value function.

  • Objective: Maximize expected return $$\displaystyle J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [R(\tau)] $$.

  • Key Theorem (Policy Gradient):

$$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot R(\tau) \right]$$

*   **REINFORCE Algorithm:** Sample trajectories, compute returns $R(\tau)$, and update: $$\displaystyle \theta \leftarrow \theta + \alpha \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot G_t $$.

*   **Advantage:** Can learn stochastic policies, suitable for high-dimensional/continuous action spaces.

*   **Disadvantage:** High variance, slow convergence. Often combined with value networks (Actor-Critic).

D. Advanced RL Paradigms

• Generative Adversarial Imitation Learning (GAIL) vs Standard RL:

  • Standard RL: Agent learns a policy to maximize a provided reward signal via trial-and-error (e.g., Q-learning).

  • GAIL: Agent learns a policy to match the behavior of an expert demonstrator without an explicit reward function.

    • Architecture: Two adversarial networks:

      1. Generator (Policy): Outputs actions.

      2. Discriminator: Tries to distinguish between agent trajectories and expert trajectories.

    • Objective: Train policy to "fool" the discriminator (minimax game). The discriminator's output serves as the reward signal.

    • Use Case: Learning from human demonstrations (e.g., robotics), avoiding manual reward engineering.

• Recent Trends in RL Architectures:

  1. Deep Reinforcement Learning: Combining deep NNs with RL (DQN, A3C, PPO, SAC) for high-dimensional state spaces.

  2. Model-Based RL: Learning a model of the environment dynamics ($P, R$) and using it for planning (e.g., Dreamer, MuZero).

  3. Multi-Agent RL (MARL): Training multiple interacting agents (cooperative, competitive, mixed).

  4. Hierarchical RL: Decomposing tasks into sub-policies (options) for long-horizon problems.

  5. Meta-RL: "Learning to learn" – algorithms that adapt quickly to new tasks.

V. MODEL EVALUATION AND OPTIMIZATION

A. Evaluation Metrics for Classification

• From Confusion Matrix (TP, TN, FP, FN):

  • Precision: $$\displaystyle \text{Precision} = \frac{TP}{TP + FP} $$ → "Of all predicted positives, how many are correct?" (Minimizes false alarms).

  • Recall (Sensitivity): $$\displaystyle \text{Recall} = \frac{TP}{TP + FN} $$ → "Of all actual positives, how many did we find?" (Minimizes missed cases).

  • F1-Score: $$\displaystyle F1 = 2 \cdot \frac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} $$ → Harmonic mean.

• ROC Curve & AUC:

  • ROC Curve: Plots True Positive Rate (Recall) vs False Positive Rate (FPR = FP/(FP+TN)) at various classification thresholds.

  • AUC (Area Under Curve): Single metric summarizing model's ability to discriminate between classes. AUC=1 (perfect), AUC=0.5 (random).

• Other Methods:

  • Accuracy: $(TP+TN)/Total$. Misleading with class imbalance.

  • Log Loss: Directly measures probabilistic calibration. Penalizes confident wrong predictions.

  • Precision-Recall Curve: More informative than ROC for highly imbalanced datasets.

B. Generalization Issues

• Overfitting:

  • Cause: Model learns noise/training data details. High complexity (too many parameters) vs. too little data.

  • Detection: Large gap between training accuracy (high) and validation/test accuracy (low). Validation curve shows increasing validation error.

  • Mitigation: More training data, regularization (L1/L2), feature reduction, early stopping, pruning (trees), dropout (NNs), ensemble methods.

• Underfitting:

  • Cause: Model too simple to capture underlying pattern. High bias.

  • Detection: Both training and validation accuracy are low.

  • Mitigation: Increase model complexity (more features, deeper trees, more NN layers), reduce regularization, longer training.

C. Validation Strategies

• Holdout Method: Split data into Training Set and Test Set (e.g., 70/30). Simple but performance estimate can be unstable (high variance) if data is small.

• Cross-Validation (Implied): k-Fold CV is standard. Data split into k folds. Model trained k times, each time on k-1 folds, validated on the held-out fold. Final metric = average of k validation scores. Provides more robust estimate and uses all data for training/validation.

D. Optimization Algorithms

• Gradient Descent Variants:

  | Variant | Batch Size | Update Frequency | Pros | Cons | |-------------------|----------------|----------------------|-----------------------------------|---------------------------------------| | Batch GD | Full dataset | Per epoch | Stable convergence, accurate gradient. | Very slow, memory intensive. | | Stochastic GD (SGD) | 1 sample | Per sample | Fast updates, can escape shallow minima. | Noisy, oscillatory convergence. | | Mini-Batch GD | n samples (e.g., 32, 64) | Per mini-batch | Best of both worlds. Efficient, stable, leverages vectorization. | Requires tuning batch size. |

• Gradient Descent Delta Rule: Classic weight update for a single-layer perceptron (linear unit) using gradient descent on MSE.

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

where $t$ = target, $y$ = output, $$\displaystyle x_i $$ = input feature, $\eta$ = learning rate. Equivalent to $$\displaystyle w_i \leftarrow w_i + \eta (t - y) x_i $$.

• Implementing Gradient Descent in TensorFlow (High-Level):

  
  import tensorflow as tf
  
  model = tf.keras.Sequential([...])  # Define model
  
  model.compile(optimizer=tf.keras.optimizers.SGD(learning_rate=0.01),
  
                loss='mse', metrics=['accuracy'])
  
  model.fit(X_train, y_train, epochs=100, batch_size=32, validation_split=0.2)
  
  

  • optimizer: SGD, Adam, RMSprop.

  • loss: MSE, BinaryCrossentropy, CategoricalCrossentropy.

  • fit: Handles mini-batch creation, forward/backward pass, weight updates automatically.

VI. ALGORITHMIC FOUNDATIONS AND THEORETICAL CONCEPTS

A. Algorithm Analysis

• Characteristics of Algorithms: Input, Output, Definiteness, Effectiveness (all steps doable), Finiteness, Correctness.

• Tools to Analyze:

  • Time Complexity: Asymptotic notation (Big O, Ω, Θ). Measures growth rate of runtime w.r.t. input size n. E.g., $$\displaystyle O(n^2) $$, $O(n \log n)$.

  • Space Complexity: Asymptotic growth of memory usage.

  • Empirical Analysis: Actual runtime measurement on specific hardware/inputs.

• Efficiency & Heuristics: For NP-hard problems (e.g., TSP), optimal algorithms are infeasible for large n. Heuristics (rules of thumb, e.g., nearest neighbor for TSP) provide "good enough" solutions quickly, sacrificing optimality for tractability.

B. Algorithm Design Techniques

• Divide and Conquer: Break problem into smaller sub-problems, solve recursively, combine solutions.

  • Example: Merge Sort, Quick Sort, Binary Search.

  • ML Example: Training decision trees (split data on feature), some ensemble methods (train on subsets).

• Dynamic Programming (DP): Break problem into overlapping sub-problems, store solutions to sub-problems (memoization) to avoid recomputation.

  • Importance in ML: Foundational for sequence models (Viterbi algorithm for HMMs, dynamic programming in CRFs), optimization (e.g., sequence alignment in bioinformatics), and some reinforcement learning algorithms (Value Iteration is a form of DP).

  • Classic Example (Fibonacci):

    
    memo = {}
    
    def fib(n):
    
        if n in memo: return memo[n]
    
        if n <= 1: return n
    
        res = fib(n-1) + fib(n-2)
    
        memo[n] = res
    
        return res
    
    

C. Probabilistic Methods

• Probabilistic Modeling in ML: Models that incorporate uncertainty and probability distributions.

  • Example: Naive Bayes Classifier. Assumes features are conditionally independent given class C.

$$P(C|X) \propto P(C) \prod_{i} P(x_i|C)$$

    Predicts class with highest posterior probability. Simple, fast, works well with high-dimensional text data.

• Probabilistic Inference: Process of computing posterior distributions (or quantities like MAP estimate) given observed evidence and a probabilistic model.

  • Need in ML: To make predictions under uncertainty, update beliefs with new data (Bayesian inference), handle missing data (EM algorithm), and perform causal reasoning.

  • Example: In a Bayesian Network, inferring the probability of "Disease" given observed "Symptoms" using Bayes' rule or belief propagation.

D. Learning Paradigms

• Lazy vs Eager Learning:

  | Lazy Learning (e.g., k-NN) | Eager Learning (e.g., Decision Trees, NN, SVM) | |---------------------------------------------------------|----------------------------------------------------------| | Training: Simply stores training data. "No learning." | Training: Computes/constructs a general model from data. | | Prediction: Computationally expensive (search entire dataset). | Prediction: Fast (just evaluate model). |

  Adapts quickly to new data. | Training is expensive, but prediction is fast. |

  Example: k-Nearest Neighbors. | Example: Most other supervised algorithms. |

• Well-Posed Learning Problems (Tom Mitchell Definition):

  A learning problem is well-posed if:

  1. There exists a target function f (the true concept) we wish to learn.

  2. There is a large set of examples (training data) from which to learn.

  3. There is a set of potential hypotheses H (the hypothesis space) that contains or approximates f.

  4. There is a learning algorithm that can find a good hypothesis in H given the examples.

  5. There is a performance measure (e.g., accuracy) to evaluate the learned hypothesis on unseen data.

VII. GAME THEORY AND AI IN STRATEGIC ENVIRONMENTS

A. Game Theory Fundamentals

• Definition & AI Application: Study of mathematical models of strategic interaction among rational agents. In AI, used to design agents that make optimal decisions in multi-agent settings (e.g., auctions, negotiations, competitive games, autonomous driving).

• Payoff Matrices & Nash Equilibrium (NE):

  • Payoff Matrix: Tabular representation of payoffs for each combination of players' strategies.

  • Nash Equilibrium: A profile of strategies (one per player) such that no player can unilaterally deviate and improve their payoff, given others' strategies.

• Case Study: Penalty Kick Game (from past paper):

  | Kicker\Goalie | Left | Right | |----------------|--------|--------| | Left | 1.4,0.6| 1.5,0.5| | Right | 1.7,0.4| 1.5,0.4|

  • Mixed Strategy NE: Kicker plays Left with probability p, Right with (1-p). Goalie plays Left with q, Right with (1-q).

  • Kicker's Indifference: Expected payoff for Kicker choosing Left = Expected payoff for choosing Right.

    $$\displaystyle q \cdot 1.4 + (1-q) \cdot 1.5 = q \cdot 1.7 + (1-q) \cdot 1.5 $$

    Solving: $$\displaystyle 1.4q + 1.5 - 1.5q = 1.7q + 1.5 - 1.5q $$ → $$\displaystyle -0.1q = 0.2q $$ → $$\displaystyle q = 0.5 $$.

  • Goalie's Indifference: Expected payoff for Goalie choosing Left = Expected payoff for choosing Right.

    $$\displaystyle p \cdot 0.6 + (1-p) \cdot 0.4 = p \cdot 0.5 + (1-p) \cdot 0.4 $$

    Solving: $$\displaystyle 0.6p + 0.4 - 0.4p = 0.5p + 0.4 - 0.4p $$ → $$\displaystyle 0.2p = 0.1p $$ → $$\displaystyle p = 0.5 $$.

  • NE: (Kicker: 0.5L, 0.5R), (Goalie: 0.5L, 0.5R). Expected payoff to Kicker = 1.45.

• Board Game Theory: Application of game theory to deterministic, perfect-information, zero-sum games (Chess, Go). Focus on minimax search, evaluation functions, and solving endgame tablebases.

B. Search Algorithms for Games

• Minimax Algorithm: For two-player, zero-sum, perfect-information games.

  • Function: Assumes both players play optimally. Maximizing player (MAX) chooses move to maximize score, minimizing player (MIN) chooses move to minimize MAX's score.

  • Process: Recursively explores game tree to a fixed depth. At leaf nodes, uses an evaluation function eval(state) to estimate utility for MAX. Backs up values: MAX takes max of children, MIN takes min.

  • Pseudocode:

    
    function minimax(state, depth, maximizingPlayer):
    
        if depth==0 or state is terminal:
    
            return eval(state)
    
        if maximizingPlayer:
    
            value = -∞
    
            for each child of state:
    
                value = max(value, minimax(child, depth-1, false))
    
            return value
    
        else:
    
            value = +∞
    
            for each child of state:
    
                value = min(value, minimax(child, depth-1, true))
    
            return value
    
    

• Efficiency & Heuristics: Game trees have exponential size (branching factor b, depth d → $$\displaystyle O(b^d) $$ nodes). Heuristics are crucial:

  • Alpha-Beta Pruning: Eliminates branches that cannot affect final decision. Reduces effective branching factor.

  • Iterative Deepening: Repeatedly runs depth-limited search with increasing depth. Allows time-bounded search.

  • Move Ordering: Explore best moves first to maximize alpha-beta pruning.

  • Transposition Tables: Cache evaluations of previously seen states (hashing).

• A Pathfinding Algorithm:*

  • Idea: Best-first search that uses heuristic h(n) (estimated cost from node n to goal) to guide search towards goal efficiently.

  • Evaluation Function: $$\displaystyle f(n) = g(n) + h(n) $$

    • $g(n)$: Actual cost from start to node n.

    • $h(n)$: Heuristic estimate from n to goal (must be admissible - never overestimates true cost - for optimality).

  • Example: Grid pathfinding with Manhattan distance as h(n).

  • Guarantee: If h(n) is admissible and consistent, A* is optimal and complete.

• Breadth-First Search (BFS) for Pathfinding:

  • Explores all nodes at current depth before moving to next depth.

  • Guaranteed to find shortest path (in terms of number of steps) in an unweighted graph/grid.

  • Uses a queue (FIFO). Inefficient for large spaces due to memory ($$\displaystyle O(b^d) $$) but complete and optimal for unit-cost steps.

C. Game AI Architectures

• Rule-Based Systems: AI that uses a set of human-defined IF-THEN rules to make decisions.

  • Example: IF (enemy_in_sight AND health > 50%) THEN attack; ELSE IF (health < 30%) THEN flee; ELSE patrol.

  • Pros: Transparent, predictable, easy to debug.

  • Cons: Brittle, hard to scale to complex situations, requires expert knowledge.

• State Machines vs Behavior Trees:

  | Finite State Machine (FSM) | Behavior Tree (BT) | |---------------------------------------------------------|---------------------------------------------------------| | Structure: States + Transitions (triggered by events/conditions). | Structure: Hierarchical tree of nodes (Tasks, Conditions, Composites: Sequence, Selector, Parallel). | | Control Flow: Explicitly defined in transitions. | Control Flow: Defined by node types (Sequence: run children in order until one fails; Selector: run children until one succeeds). | | Complexity: Can become a "spaghetti" of transitions (explosion of states) for complex behaviors. | Scalability: More modular, reusable, easier to design complex, reactive behaviors. | | Example: Guard AI: States = Patrol, Chase, Fight, Flee. Transitions based on SeeThief, HealthLow. | Example: Root -> Selector -> (Sequence: IsThiefVisible? -> Chase), (Sequence: IsHealthLow? -> Flee), Patrol. |

• Finite State Machine Construction (from past paper - Guard Example):

  • States: Guard, Fight, Flee.

  • Transitions:

    • Guard → Fight: IF SeeThief AND ThiefStrength <= MyStrength.

    • Guard → Flee: IF SeeThief AND ThiefStrength > MyStrength.

    • Fight → Flee: IF HealthLow (during fight).

    • Flee → Guard: IF Escaped (after fleeing).

• Model of Game AI: Often a layered architecture:

  1. Decision Layer: High-level goals (FSM, BT, GOAP - Goal-Oriented Action Planning).

  2. Movement Layer: Pathfinding (A*, NavMesh) and steering (boids, potential fields).

  3. Animation/Physics Layer: Executes movement and actions.

• Static vs Kinematic Representation in 3D:

  • Static Representation: Defines the final pose/configuration of an object or character at a point in time (position, orientation, joint angles). Used for keyframes in animation. No information about motion.

  • Kinematic Representation: Defines motion over time. Includes velocity, acceleration, and the functions describing how position/orientation change. Used for procedural animation, physics-based movement, and motion planning.

D. Motor Learning and Movement

• Stages of Motor Learning (Fitts & Posner):

  1. Cognitive Stage: Learner understands the task, makes many errors. Requires conscious attention.

  2. Associative Stage: Learner refines movement, reduces errors. Performance becomes smoother, less conscious thought needed.

  3. Autonomous Stage: Skill is automatic, requires little attention. Can perform while doing other tasks.

• Components of Coordinated Movement:

  • Trajectory Planning: Defining the path in space (e.g., Bezier curves, splines).

  • Timing: Synchronizing movement phases.

  • Dynamics: Applying forces/torques to achieve motion (inverse kinematics/dynamics).

  • Feedback Control: Using sensory input (vision, proprioception) to correct errors (e.g., PID control).

• Movement Algorithm Structure (Typical):

  1. Goal Specification: Define target pose/position.

  2. Path Planning: Generate collision-free trajectory (A*, RRT*).

  3. Trajectory Smoothing: Ensure velocity/acceleration are continuous (e.g., via splines).

  4. Inverse Kinematics (IK): Solve for joint angles to achieve end-effector pose along trajectory.

  5. Inverse Dynamics (ID): Compute required joint torques/forces to follow trajectory (considering mass, inertia).

  6. Low-Level Control: Send torque commands to actuators, use feedback loops (PID) to track desired motion.

VIII. SPECIALIZED APPLICATIONS OF MACHINE LEARNING

A. Graphs, Maps, and Geographic Data

• ML in Graph Algorithms & Map Searching:

  • Graph Neural Networks (GNNs): Learn representations for nodes/edges/graphs. Applications: node classification (fraud detection), link prediction (recommendations), graph classification (molecule property prediction).

  • Map Searching/Route Optimization: Reinforcement Learning (e.g., Deep Q-Networks) for dynamic routing. ML models predict traffic flow to estimate travel times for better pathfinding (A* with learned heuristic).

  • Geospatial Prediction: Using CNN/LSTM on satellite imagery for land use classification, predicting urban development.

B. Matching and Allocation Problems

• Stable Marriages Algorithm (Gale-Shapley) in ML:

  • Problem: Find a stable matching between two equally sized sets (e.g., residents to hospitals, users to items) where no pair prefers each other over their current match.

  • ML Application: Used as a fairness-aware allocation mechanism. Can be adapted for:

    • School-choice/college admissions: Matching students to schools with preferences.

    • Job matching: Platforms like LinkedIn/Eightfold use variants to match candidates to jobs.

    • Recommendation systems: Stable matching can ensure diversity and fairness in item-user assignments, avoiding "rich-get-richer" effects.

C. Healthcare and Bioinformatics

• Prediction of Preterm Birth using ML:

  • Goal: Predict risk of delivery before 37 weeks using clinical, demographic, and biomarker data (e.g., cervical length, fetal fibronectin, maternal age).

  • Approach: Use classification models (Logistic Regression, Random Forest, XGBoost, LSTMs for time-series data like uterine EMG).

  • Challenges: Class imbalance (preterm is rare), noisy data, ethical implications. Focus on high recall (minimize missed preterm cases).

• Interconnectedness on Personal Genomes in ML:

  • Concept: Genes and their products (proteins, RNA) do not act in isolation; they form complex, interacting biological networks (gene regulatory networks, protein-protein interaction networks).

  • ML Application: Use network-based machine learning.

    • GNNs to predict gene function, disease genes, or drug targets by propagating information through the network.

    • Network propagation algorithms (random walk with restart) to prioritize genes associated with a disease based on proximity to known disease genes in the network.

    • Multi-omics integration: Combine genomic, transcriptomic, epigenomic data as interconnected layers.

D. Time Series and Stochastic Processes

• Fuzzy Time Series & Markov Chains:

  • Idea: Combine fuzzy logic (handling linguistic uncertainty) with Markov chains (modeling state transitions) for forecasting.

  • Flowchart Explanation (Average-based Fuzzy Time Series):

    1. Fuzzify: Partition universe of discourse into linguistic intervals (e.g., Low, Medium, High). Convert historical data into fuzzy sets (e.g., Year 1 = "Medium").

    2. Establish Fuzzy Logical Relationships (FLRs): Find patterns like "If (Year t is A) THEN (Year t+1 is B)". Count occurrences.

    3. Forecast: For latest year t (fuzzy set A), find all FLRs starting with A. Use weighted average of consequent sets (B1, B2...) based on frequency to defuzzify and get forecast for t+1.

  • Markov Chain Integration: The FLRs can be seen as a first-order Markov chain where states = fuzzy sets, and transition probabilities are derived from FLR frequencies. Forecast is based on current fuzzy state and transition matrix.

  • Average-based: The final forecast value is the average of the universe values corresponding to the forecasted fuzzy set(s).