UNIT 3: ADVANCED PREDICTIVE ANALYTICS & MACHINE LEARNING

I. FOUNDATIONS: DATA HANDLING & PREPROCESSING

Data Product Strategy

A data product strategy defines how data assets are transformed into valuable, scalable products or services. Steps for building a successful strategy:

1. Identify business problem & value proposition: Define the core user need and how data solves it.

2. Data sourcing & acquisition: Determine internal/external data sources (APIs, databases, web scraping).

3. Data processing & modeling: Clean, transform, and apply ML/statistical models.

4. Product integration & deployment: Embed insights into applications, dashboards, or APIs.

5. Monitoring & iteration: Track performance, data drift, and retrain models.

Types based on functionality:

[!TIP] Exam Focus: Be prepared to list steps and classify a given example (e.g., Netflix recommendations = Decision Automator).

File Formats & Data Extraction in Python

CSV (Comma-Separated Values):

• Simple, text-based, columnar format.

• Reading: pandas.read_csv('file.csv')

• Writing: df.to_csv('output.csv', index=False)

JSON (JavaScript Object Notation):

• Hierarchical, key-value pair format, supports nested structures.

• Reading: pandas.read_json('file.json') or json.load(open('file.json'))

• Writing: df.to_json('output.json') or json.dump(data, open('file.json','w'))

Data Extraction Tools & Techniques:

• Web Scraping: BeautifulSoup (parses HTML/XML), Scrapy (framework).

• APIs: requests library to fetch data from RESTful endpoints (returns often JSON).

• Code Snippet - String to JSON Array:

  
  import json
  
  data_string = '[{"name":"Alice","age":30},{"name":"Bob","age":25}]'
  
  json_array = json.loads(data_string)  # Converts string to Python list of dicts
  
  

Text Processing Libraries:

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

• re (built-in): Regular expressions for pattern matching.

• TextBlob: Simplified text processing (sentiment, translation).

Numerical Computing with NumPy

• Core library for multi-dimensional arrays (ndarray) and mathematical operations.

• Matrix Operations:

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

• Statistical Computations:

  
  data = np.array([1,2,3,4,5])
  
  mean = np.mean(data)
  
  variance = np.var(data)  # Population variance by default
  
  std_dev = np.std(data)
  
  

Data Visualization with Matplotlib

• Primary purpose: Create static, interactive, and animated visualizations in Python.

• Applications: Exploratory data analysis (EDA), presenting results, creating publication-quality figures.

• Basic 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()
  
  

II. CORE MACHINE LEARNING ALGORITHMS

A. Decision Trees

Recursive Induction: The top-down, greedy process of splitting the dataset.

1. Start with entire training set at root node.

2. Select the best attribute (using a criterion like Information Gain) that splits the data most homogeneously.

3. Create a branch for each value of that attribute.

4. Recurse on the resulting subsets (child nodes) using only attributes not yet used.

5. Stop when: all instances in a node belong to same class, no attributes left, or no instances remain.

Entropy & Information Gain (IG):

• Entropy: Measures impurity/uncertainty in a set of examples.

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

where \(p_i\) is the proportion of class \(i\) in set \(S\), \(c\) is number of classes.

\boxed{H(S) = 0 \text{ (pure)}, H(S) = 1 \text{ (max impurity for binary)}}.

• Information Gain: 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 \(S_v\) is the subset of \(S\) where attribute \(A\) has value \(v\).

Numerical Example (from Paper B):

Dataset: 7 samples (4 Yes, 3 No for Loan Approved).

1. Root Entropy: \(H(S) = -\frac{4}{7}\log_2\frac{4}{7} - \frac{3}{7}\log_2\frac{3}{7} \approx 0.985\)

2. Split on Credit Score (High, Medium, Low):

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

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

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

3. Weighted Avg Entropy after split: \(\frac{3}{7}*0.918 + \frac{2}{7}*1.0 + \frac{2}{7}*0.0 \approx 0.653\)

4. IG(Credit Score): \(0.985 - 0.653 = 0.332\)

Repeat for other attributes; choose the one with highest IG.

Handling Noisy Data (Overfitting):

• Pre-pruning (Early stopping): Stop tree growth based on criteria (min samples per leaf, max depth, min IG threshold).

• Post-pruning: Grow full tree, then remove branches that don't improve accuracy on a validation set.

• Ensemble methods: Use Random Forests (see below) which average many trees.

Application in Game Development: Decision trees model NPC behavior logic (e.g., if player_visible AND health > 50% then attack else flee).

B. Ensemble Methods

Bagging (Bootstrap Aggregating) vs. Boosting:

Random Forest Architecture & Working:

1. Bootstrap Sampling: Create n_estimators different training subsets by sampling with replacement.

2. Tree Growth: For each subset, grow a decision tree. At each split, consider only a random subset of features (e.g., sqrt(total_features)). This decorrelates trees.

3. Aggregation: For classification, final prediction = majority vote of all trees. For regression, average of all tree outputs.

\boxed{\text{Random Forest reduces variance by averaging many high-variance, low-bias trees.}}

Why Ensembles are More Robust:

• Variance Reduction (Bagging): Averages out noisy fluctuations from individual models.

• Bias Reduction (Boosting): Sequentially corrects systematic errors.

• Error Diversity: Different models make different errors; voting/averaging cancels out individual mistakes.

• Mitigates Overfitting: Especially in Random Forest, feature randomness and averaging prevent any single tree from dominating.

C. Linear Models & Gradient Descent

Linear Regression using Gradient Descent:

• Model: \(y = \beta_0 + \beta_1 x_1 + ... + \beta_n x_n + \epsilon\) or vector form \(y = X\beta + \epsilon\).

• Cost Function (Mean Squared Error - MSE): \(J(\beta) = \frac{1}{2m} \sum_{i=1}^{m} (h_\beta(x^{(i)}) - y^{(i)})^2\). (Factor 1/2 for convenience in derivative).

• Gradient Descent Update Rule:

$$\beta_j := \beta_j - \alpha \frac{\partial}{\partial \beta_j} J(\beta)$$

where \(\alpha\) is the **learning rate**.

For all \(j\) simultaneously:

$$\beta_j := \beta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_\beta(x^{(i)}) - y^{(i)}) x_j^{(i)}$$

\boxed{\beta := \beta - \alpha \cdot \frac{1}{m} X^T (X\beta - y)} (Vectorized form).

Gradient Descent in TensorFlow (Steps):

1. Define model parameters (tf.Variable).

2. Define loss function (e.g., tf.reduce_mean(tf.square(y_pred - y_true))).

3. Choose optimizer (e.g., tf.keras.optimizers.SGD(learning_rate=alpha)).

4. In a training loop:

   
   with tf.GradientTape() as tape:
   
       y_pred = model(x_batch)
   
       loss = loss_fn(y_batch, y_pred)
   
   gradients = tape.gradient(loss, model.trainable_variables)
   
   optimizer.apply_gradients(zip(gradients, model.trainable_variables))
   
   

Mini-Batch Gradient Descent:

• Compromise between Batch GD (uses all m samples) and Stochastic GD (uses 1 sample).

• Uses a small random subset (mini-batch) of training examples per iteration.

• Advantages: Faster convergence than Batch GD, more stable than SGD, leverages vectorized hardware (GPUs).

• Common batch sizes: 32, 64, 128.

Least Squared Error (LSE) Hypothesis (Paper D):

• The foundational assumption in linear regression: The true relationship is linear, and errors (\(\epsilon\)) are independent, identically distributed (i.i.d.) with mean zero and constant variance (homoscedasticity).

• Goal: Find \(\hat{\beta}\) that minimizes the sum of squared residuals (LSE).

• Closed-form solution (Normal Equation): \(\hat{\beta} = (X^TX)^{-1}X^Ty\).

D. Neural Networks - Multi-Layer Perceptron (MLP)

Architecture:

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

• Hidden Layer(s): One or more layers of neurons with non-linear activation functions (ReLU, Sigmoid, Tanh). This enables learning complex patterns.

• Output Layer: Transforms hidden layer output to final prediction. Activation depends on task:

  • Regression: Linear (or ReLU for non-negative).

  • Binary Classification: Sigmoid (outputs probability 0-1).

  • Multi-class Classification: Softmax (outputs probability distribution).

Learning Process (Backpropagation):

1. Forward Pass: Input \(x\) is passed through network, layer by layer, applying weights \(W\), biases \(b\), and activation functions to produce prediction \(\hat{y}\).

2. Compute Loss: Calculate error between \(\hat{y}\) and true \(y\) using a loss function (MSE, Cross-Entropy).

3. Backward Pass (Backpropagation): Apply chain rule to compute gradient of loss w.r.t. every weight and bias in the network. This shows how much each parameter contributed to the error.

4. Parameter Update: Use an optimizer (SGD, Adam) to update all weights and biases in the direction that reduces loss (using the gradients).

E. Learning Paradigms

Lazy vs. Eager Learning:

Well-Posed Learning Problems (Paper D):

A learning problem is well-posed if:

1. The performance measure (e.g., accuracy) is definable and quantifiable.

2. The task is repetitive and predictable (similar inputs yield similar outputs).

3. There exists a large, representative dataset from the target population.

4. There is a learnable pattern or relationship between inputs and outputs (not purely random). Example: Predicting house prices from features (size, location) is well-posed. Predicting next week's lottery numbers is ill-posed.

III. MODEL EVALUATION & VALIDATION

Classification Metrics

• Confusion Matrix: Foundation for all metrics.

  | | Predicted + | Predicted - | | :--- | :--- | :--- | | Actual + | TP (True Positive) | FN (False Negative) | | Actual - | FP (False Positive) | TN (True Negative) |

• Precision: Of all predicted positives, how many are correct? \(Precision = \frac{TP}{TP+FP}\). "How precise is my positive prediction?"

• Recall (Sensitivity): Of all actual positives, how many did I find? \(Recall = \frac{TP}{TP+FN}\). "How many actual positives did I capture?"

• F1-Score: Harmonic mean of Precision and Recall.

$$F1 = 2 \cdot \frac{Precision \cdot Recall}{Precision + Recall}$$

Useful when you need a balance between Precision and Recall (class imbalance).

• ROC Curve: Plots True Positive Rate (Recall) vs. False Positive Rate (\(FPR = \frac{FP}{FP+TN}\)) at various classification thresholds. Area Under Curve (AUC) measures overall separability performance (AUC=1 is perfect).

Validation Techniques

• Holdout Method:

  1. Randomly split data into Training Set (e.g., 70%) and Test Set (e.g., 30%).

  2. Train model on Training Set.

  3. Evaluate final model once on the unseen Test Set.

  • Disadvantage: Performance estimate can be high-variance if split is unlucky. Test set is used only once.

• Cross-Validation (k-Fold CV - Most Common):

  1. Split data into k equal-sized folds.

  2. For each fold i:

     • Use fold i as validation set.

     • Use remaining k-1 folds as training set.

     • Train model, evaluate on validation fold, record score.

  3. Final performance = average of the k validation scores.

  • Advantage: More robust, uses all data for training and validation. Common k=5 or 10.

Bias-Variance Tradeoff

• Bias: Error from erroneous assumptions in the model (e.g., linear model for non-linear data). High bias → Underfitting.

• Variance: Error from sensitivity to small fluctuations in the training set. High variance → Overfitting.

• Tradeoff: As model complexity increases, bias decreases but variance increases.

  
  graph LR
  
  A[Model Complexity] --> B[Low Bias, High Variance <br/> Overfitting]
  
  A --> C[High Bias, Low Variance <br/> Underfitting]
  
  A --> D[Optimal Balance <br/> Generalization]
  
  

• Mitigation Strategies:

  • Underfitting (High Bias): Use more complex model, add features, reduce regularization.

  • Overfitting (High Variance): Get more data, use regularization (L1/L2), reduce model complexity (prune trees, reduce layers/neurons), use dropout (NNs), apply cross-validation for early stopping.

IV. REINFORCEMENT LEARNING (RL)

A. Fundamental Concepts

• Markov Decision Process (MDP): Formal framework for RL.

  • Components: Set of States \(S\), set of Actions \(A\), Transition Probability \(P(s' | s, a)\) (probability of next state \(s'\) given state \(s\) and action \(a\)), Reward Function \(R(s, a, s')\), Discount Factor \(\gamma \in [0,1]\).

  • Markov Property: Future state depends only on current state and action, not on the sequence of events that preceded it.

• Bellman Equations: Define the relationship between the value of a state/action and its successors.

  • State-Value Function \(V^\pi(s)\): Expected discounted return starting from state \(s\) and following policy \(\pi\).

$$V^\pi(s) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s \right]$$

*   **Action-Value Function \(Q^\pi(s,a)\):** Expected discounted return starting from state \(s\), taking action \(a\), then following policy \(\pi\).

$$Q^\pi(s,a) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a \right]$$

\boxed{\text{They are recursive equations, central to all RL solution algorithms.}}

• Policy \(\pi\): Strategy mapping states to actions. Can be deterministic (\(\pi(s)=a\)) or stochastic (\(\pi(a|s)\)).

• Value Function: Measures the "goodness" of a state/action under a policy.

• Optimal Value Functions: \(V^*(s) = \max_\pi V^\pi(s)\), \(Q^*(s,a) = \max_\pi Q^\pi(s,a)\). The optimal policy \(\pi^*\) can be derived from \(Q^*\): \(\pi^*(s) = \arg\max_a Q^*(s,a)\).

B. Model-Free Algorithms

• Model-Free: Learn value functions or policies directly from interaction with the environment, without learning the transition model \(P\).

• Q-learning vs. SARSA:

  | Feature | Q-learning | SARSA | | :--- | :--- | :--- | | Type | Off-policy | On-policy | | Update Rule | \(Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]\) | \(Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s',a') - Q(s,a)]\) | | Next Action | Uses greedy action \(a' = \arg\max Q(s', \cdot)\) for bootstrap target. | Uses actual next action \(a'\) taken by current policy (e.g., \(\epsilon\)-greedy). | | Policy | Learns optimal policy \(Q^*\) regardless of exploration policy. | Learns the policy being followed (including exploration). | | Risk | Can be unstable in some environments (due to max operator). | Generally more stable, learns safer policies if exploration is cautious. |

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

  | Feature | TD Learning | Monte Carlo | | :--- | :--- | :--- | | Update | After each step: \(V(s_t) \leftarrow V(s_t) + \alpha [r_{t+1} + \gamma V(s_{t+1}) - V(s_t)]\) | After end of episode: \(V(s_t) \leftarrow V(s_t) + \alpha [G_t - V(s_t)]\) | | Bootstrap | Yes (uses current estimate \(V(s_{t+1})\)). | No (uses actual return \(G_t\)). | | Variance | Lower (bootstrapping reduces variance). | Higher (depends on full trajectory). | | Convergence | To \(v_\pi\) if step-size decays appropriately. | To \(v_\pi\) as visits → ∞. | | Applicability | Works in continuing (non-episodic) tasks. | Requires episodic tasks. |

• Policy Gradient Methods:

  • Concept: Directly optimize the policy \(\pi_\theta\) (parameterized by \(\theta\)) by gradient ascent on expected return \(J(\theta) = \mathbb{E}_\pi [G_t]\).

  • Key Theorem (REINFORCE): \(\nabla J(\theta) = \mathbb{E}_\pi [G_t \nabla \log \pi_\theta(A_t|S_t)]\).

  • Mechanism: Collect trajectories with current policy, compute returns \(G_t\), then update parameters: \(\theta \leftarrow \theta + \alpha G_t \nabla \log \pi_\theta(A_t|S_t)\).

  • Advantages: Can learn stochastic policies, suitable for continuous action spaces.

  • Applications: Robotics control, game playing (AlphaGo's policy network).

C. Advanced RL Topics

• Value Iteration & Policy Iteration (Short Note):

  • Value Iteration: Repeatedly apply Bellman Optimality Update until convergence:

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

    Simple, but requires full sweeps of state space.

  • Policy Iteration: Alternates between:

    1. Policy Evaluation: Compute \(V^\pi\) for current policy \(\pi\) (solve linear system or iterative TD).

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

    Often faster convergence but costly evaluation step.

  \boxed{\text{Both are Dynamic Programming methods, require known model } P, R.}

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

  | | Standard RL | GAIL | | :--- | :--- | :--- | | Objective | Maximize cumulative reward given a reward function \(R(s,a)\). | Imitate expert demonstrations without a predefined reward. | | Input | Reward function \(R(s,a)\). | Expert trajectories (state-action pairs). | | Mechanism | Agent learns policy \(\pi\) to maximize \(\mathbb{E}[\sum R]\). | Adversarial: Discriminator \(D\) tries to distinguish expert vs. agent trajectories. Policy \(\pi\) is trained to fool \(D\) (minimizes JS divergence between trajectory distributions). | | Analogy | "Here's the score, play to win." | "Watch a pro play, learn their style." |

• Recent Trends in RL Architectures (Paper B):

  • Deep RL: Combining deep neural networks with RL (DQN, PPO, SAC) for high-dimensional state/action spaces.

  • Model-Based RL: Learn environment model \(P\) to plan ahead (e.g., Dreamer, MuZero), improving sample efficiency.

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

  • Multi-Agent RL (MARL): Multiple agents learning jointly, with cooperation/competition (e.g., for traffic control, game AI).

  • Meta-RL: "Learning to learn" – adapt quickly to new tasks with few samples.

V. ALGORITHMIC FOUNDATIONS & DESIGN

A. Algorithm Analysis

• Characteristics of an Algorithm:

  1. Well-defined input.

  2. Well-defined output.

  3. Definiteness (each step precise).

  4. Effectiveness (each step feasible).

  5. Finiteness (terminates after finite steps).

• Tools to Analyze Algorithms:

  • Time Complexity: Measures runtime as function of input size \(n\) using asymptotic notation:

    • \(O\) (Big-O): Upper bound (worst-case).

    • \(\Omega\) (Big-Omega): Lower bound (best-case).

    • \(\Theta\) (Big-Theta): Tight bound (average-case, if same).

  • Space Complexity: Measures memory usage as function of \(n\).

  • Empirical Profiling: Actual runtime measurement on specific hardware.

B. Design Paradigms

• Divide and Conquer:

  1. Divide: Break problem into smaller sub-problems.

  2. Conquer: Solve sub-problems recursively.

  3. Combine: Merge solutions to sub-problems.

  • ML Example: Training a decision tree. At each node, "divide" the feature space based on best split, "conquer" by building subtrees on subsets, "combine" by forming the tree structure.

• Dynamic Programming (DP) in ML:

  • Solves complex problems by breaking into overlapping sub-problems and storing (memoizing) their solutions to avoid recomputation.

  • Key Principle: Optimal substructure + Overlapping sub-problems.

  • ML Example: Sequence Modeling (e.g., Hidden Markov Models, Viterbi algorithm for most likely state sequence). The probability of the best path up to time \(t\) ending in state \(k\) depends on the best path up to \(t-1\) ending in a predecessor state. DP efficiently computes this recurrence.

C. Probabilistic & Inference Methods

• Probabilistic Modeling in ML:

  • Represents uncertainty explicitly using probability distributions.

  • Example: Naive Bayes classifier. Models \(P(Class | Features) \propto P(Class) \prod P(Feature_i | Class)\). Makes predictions based on probabilistic inference.

• Need and Usage of Probabilistic Inference:

  • Need: Real-world data is noisy, incomplete, and uncertain. Deterministic models are brittle.

  • Usage:

    1. Prediction: Compute posterior distribution \(P(Y|X)\) for new \(X\).

    2. Decision Making: Choose actions that maximize expected utility under uncertainty.

    3. Learning: Fit model parameters by maximizing likelihood/probability of observed data.

    4. Handling Missing Data: Infer missing values from observed ones.

  • Methods: Exact inference (enumeration, variable elimination), Approximate inference (MCMC, variational inference).

D. Application-Specific Algorithms

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

  • Classic problem: Match two sets (e.g., men/women, students/schools) based on preferences to find a stable matching (no pair prefers each other over current match).

  • ML Application: Matching problems like assigning users to tasks, ads to auctions, or resources to agents in multi-agent systems. Ensures no two agents would prefer to swap assignments.

• ML in Graphs, Maps, and Map Searching:

  • Graphs: Node classification (e.g., predicting protein functions), link prediction (friend suggestions), graph neural networks (GNNs).

  • Maps/Pathfinding: A* search (heuristic-guided), reinforcement learning for route optimization, predicting traffic flow.

• Prediction of Preterm Birth using ML:

  • Problem: Predict risk of preterm birth (<37 weeks) from clinical data (maternal history, biomarkers, ultrasound).

  • ML Approach: Use classification models (Logistic Regression, Random Forest, XGBoost) on electronic health records (EHR). Handle class imbalance (preterm is rare). Key challenge: interpretability for clinicians.

• Interconnectedness on Personal Genomes:

  • Problem: Understand how genetic variations (SNPs) interact to influence complex traits/diseases.

  • ML Approach: Use ** epistasis detection** algorithms. High-dimensional data (millions of SNPs). Methods: Regularized regression (Lasso), tree-based methods (RF), deep learning to capture non-linear SNP-SNP interactions. Goal: Identify interacting genetic loci.

VI. GAME THEORY & STRATEGIC AI

A. Game Theory Basics

• Definition: Study of mathematical models of strategic interaction among rational decision-makers.

• Application to AI: Design agents that act optimally in multi-agent environments (adversarial or cooperative). Used in poker, StarCraft, autonomous driving negotiation.

• Key Concepts:

  • Players: Decision-makers.

  • Strategies: Complete plan of action for each possible situation.

  • Payoff Matrix: Table showing rewards for each combination of player strategies.

  • Nash Equilibrium (NE): A set of strategies where no player can unilaterally improve their payoff by changing their strategy, given others' strategies.

    • Pure Strategy NE: Specific strategy profile.

    • Mixed Strategy NE: Probability distribution over strategies.

Numerical Example - Solve Payoff Matrix (Paper A):

| Player A \ Player B | I | II | III |

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

| I | 5,9 | 9,14 | 3,4 |

| II | 6,6 | 14,9 | 4,3 |

Find Pure Strategy NE: Check each cell. A cell is NE if A's payoff is max in its column AND B's payoff is max in its row.

• (I,II): A gets 9 (max in col II? 9 vs 14 -> no). Not NE.

• (II,I): A gets 6 (max in col I? 6 vs 5 -> yes). B gets 6 (max in row II? 6 vs 14 vs 4 -> no). Not NE.

• (II,II): A gets 14 (max in col II? 14 vs 9 -> yes). B gets 9 (max in row II? 9 vs 6 vs 4 -> yes). \boxed{\text{NE at (II, II) with payoffs (14, 9)}}.

Example - Penalty Kick (Paper A):

| Kicker\Goalie | Left | Right |

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

| Left | 1.4, 0.6 | 1.5, 0.5 |

| Right | 1.7, 0.4 | 1.5, 0.4 |

Find Mixed Strategy NE: Let Kicker play Left with prob \(p\), Right with \(1-p\). Goalie must be indifferent:

• Goalie's Expected Payoff for Left: \(0.6p + 0.4(1-p) = 0.4 + 0.2p\)

• Goalie's Expected Payoff for Right: \(0.5p + 0.4(1-p) = 0.4 + 0.1p\)

Set equal: \(0.4 + 0.2p = 0.4 + 0.1p \Rightarrow p = 0\).

• Kicker's Expected Payoff for Left: \(1.4q + 1.7(1-q) = 1.7 - 0.3q\)

• Kicker's Expected Payoff for Right: \(1.5q + 1.5(1-q) = 1.5\)

Set equal: \(1.7 - 0.3q = 1.5 \Rightarrow q = 2/3 \approx 0.667\).

\boxed{\text{NE: Kicker always Right (p=0), Goalie plays Left 2/3, Right 1/3.}}

B. Search & Pathfinding

• Minimax Algorithm:

  • Used in zero-sum, perfect-information, turn-based games (chess, tic-tac-toe).

  • Idea: Assume opponent (min player) plays optimally to minimize your score. You (max player) choose move that maximizes your minimum guaranteed outcome.

  • Functions: Recursively explores game tree, assigns utility values to terminal states, propagates max (your turn) and min (opponent's turn) values up the tree.

• Alpha-Beta Pruning: Optimization of Minimax.

  • Alpha (\(\alpha\)): Best (highest) value that the max player can guarantee at that point or above.

  • Beta (\(\beta\)): Best (lowest) value that the min player can guarantee at that point or below.

  • Pruning: If at any node, \(\alpha \geq \beta\), the current branch cannot yield a better move for the player who made the choice at the ancestor node. Prune (skip exploring) the rest of that branch.

• A Pathfinding Algorithm:*

  • Best-first search using heuristic \(h(n)\) to guide towards goal.

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

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

    • \(h(n)\): Admissible heuristic (never overestimates true cost to goal). E.g., Manhattan distance for grid.

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

  • Example: Grid pathfinding with obstacles. \(g\) = steps taken, \(h\) = straight-line distance to goal.

• Breadth-First Search (BFS) for Pathfinding:

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

  • Uses a queue (FIFO).

  • Guarantee: Finds shortest path (in terms of number of edges) in an unweighted graph.

  • Disadvantage: Can be memory intensive for large graphs.

C. AI Behavior Modeling

• Rule-Based Systems:

  • Example: Expert system for medical diagnosis.

    
    IF fever AND cough THEN possible_flu = true
    
    IF possible_flu AND body_ache THEN recommend_rest = true
    
    

  • Components: Knowledge base (set of IF-THEN rules), Inference Engine (applies rules to facts).

• State Machines vs. Behavior Trees:

  | | Finite State Machine (FSM) | Behavior Tree (BT) | | :--- | :--- | :--- | | Structure | States connected by transitions. | Tree of nodes (tasks, conditions, decorators). | | Control Flow | Hard transitions between states. | Tick-based: Each node returns Success, Failure, or Running. | | Flexibility | Can become complex ("spaghetti") with many states/transitions. | Hierarchical, modular, easier to design complex behaviors. | | Reusability | Low. | High (subtrees can be reused). | | Game AI Use | Simple NPCs (guard, patrol, chase). | Modern complex AI (e.g., in Halo, The Last of Us). |

• Finite State Machine (FSM) Construction (Paper A Example):

  • States: Guard, Fight, Flee, Escape.

  • Transitions:

    • Guard -> Fight if see_thief AND thief_strength <= my_strength

    • Guard -> Flee if see_thief AND thief_strength > my_strength

    • Fight -> Flee if losing_fight

    • Flee -> Guard (always after escape)

  • Diagram: Circular flow between these states based on conditions.

D. Representations & Movement

• Static vs. Kinematic Representation in 3D:

  • Static Representation: Describes pose (position and orientation) at a single instant. No information about motion.

    • Example: A 3D model file (.obj) with vertex positions.

  • Kinematic Representation: Describes motion – how pose changes over time. Includes velocities, accelerations, joint angles over time.

    • Example: Animation keyframes, motion capture data, physics-based movement scripts.

• Components of Coordinated Movement:

  1. Trajectory Planning: Path through space/time.

  2. Inverse Kinematics (IK): Calculating joint angles to place end-effector (e.g., hand) at a desired position.

  3. Forward Kinematics: Calculating end-effector position from joint angles.

  4. Dynamics: Forces/torques required to produce motion (physics).

  5. Balance & Stability: Maintaining center of mass over support base (e.g., ZMP for humanoids).

• Stages of Motor Learning (Fitts & Posner):

  1. Cognitive Stage: Learner understands task, makes large errors. Requires conscious effort.

  2. Associative Stage: Errors decrease, performance becomes smoother. Learner refines movement.

  3. Autonomous Stage: Skill is automatic, requires little attention. Highly consistent.

E. Stochastic & Predictive Models in Games

• Fuzzy Time Series & Markov Chains (Flowchart):

  • Fuzzy Time Series: Handles uncertainty in temporal data by defining fuzzy logical relationships between fuzzy sets (e.g., "High" -> "Medium"). Used for forecasting in games (e.g., predicting resource availability).

  • Markov Chain: Models state transitions with probabilities. Current state depends only on previous state.

  • Combined Flowchart Idea:

    1. Fuzzify current game state (e.g., "player_health" -> {Low, Medium, High}).

    2. Use fuzzy relation matrix to predict next fuzzy state based on current.

    3. Defuzzify to get crisp prediction (e.g., expected health after 5 seconds).

    4. Alternatively, use Markov Chain where states are fuzzy sets, and transition matrix is learned from historical game data.

• Decision Trees in Game Development: (See Unit II.A. Application).

• Board Game Theory: Application of combinatorial game theory to board games (e.g., Go, Chess). Analyzes game trees, winning strategies, complexity classes (PSPACE-complete for many games). Concepts like zugzwang (forced move that worsens position) are analyzed.

VII. PYTHON FOR PREDICTIVE ANALYTICS

(Integrated practical implementation focus from Paper C)

Data Manipulation

import pandas as pd

# CSV

df_csv = pd.read_csv('data.csv')

df_csv.to_csv('output.csv', index=False)

# JSON

df_json = pd.read_json('data.json')

df_json.to_json('output.json')

Data Extraction from Web

import requests

from bs4 import BeautifulSoup

# API

response = requests.get('https://api.example.com/data')

data = response.json()

# Web Scraping

html = requests.get('https://example.com').text

soup = BeautifulSoup(html, 'html.parser')

titles = [tag.text for tag in soup.find_all('h1')]

Numerical & Statistical Operations (NumPy)

import numpy as np

# Matrix Algebra

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

A_inv = np.linalg.inv(A)

# Statistics

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

mean, var, std = np.mean(data), np.var(data), np.std(data)

Visualization (Matplotlib)

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()

ML Implementation

Linear Regression with Gradient Descent:

import numpy as np

# X: features (with bias term 1s), y: target

def gradient_descent(X, y, alpha=0.01, epochs=1000):

    m, n = X.shape

    theta = np.zeros(n)  # parameters

    for _ in range(epochs):

        y_pred = X @ theta

        error = y_pred - y

        gradient = (X.T @ error) / m

        theta -= alpha * gradient

    return theta

Mini-Batch Gradient Descent:

def mini_batch_gd(X, y, alpha=0.01, epochs=100, batch_size=32):

    m, n = X.shape

    theta = np.zeros(n)

    for epoch in range(epochs):

        indices = np.random.permutation(m)

        X_shuffled, y_shuffled = X[indices], y[indices]

        for i in range(0, m, batch_size):

            X_batch = X_shuffled[i:i+batch_size]

            y_batch = y_shuffled[i:i+batch_size]

            gradient = (X_batch.T @ (X_batch @ theta - y_batch)) / batch_size

            theta -= alpha * gradient

    return theta

VIII. CONCEPTUAL SYNTHESIS & RECENT TRENDS

(Short-Note Topics)

Random Forest (Short Note)

• Ensemble of decision trees using bagging and feature randomness.

• Mechanism: Builds many trees on bootstrap samples; at each split, considers only random subset of features. Final prediction = majority vote (classification) or average (regression).

• Advantages: Reduces overfitting (high variance) of single trees, handles high-dimensional data, provides feature importance.

• Disadvantages: Less interpretable than single tree, can be slow for prediction.

Recent Trends in RL Architectures

• Deep Reinforcement Learning: Combining deep NNs with RL (DQN, PPO, SAC) for high-dimensional perceptual inputs (pixels).

• Model-Based RL: Learning environment dynamics model for planning (Dreamer, MuZero) to improve sample efficiency.

• Hierarchical RL: Learning temporally extended skills (options) for long-horizon tasks (e.g., options in The Last of Us AI).

• Multi-Agent RL (MARL): Training populations of agents in cooperative/competitive settings (e.g., Google's AlphaStar in StarCraft II).

• Meta-RL: Algorithms that can adapt to new tasks quickly with minimal experience (e.g., MAML).

Overfitting and Underfitting (Short Note)

• Overfitting: Model learns noise in training data. High training accuracy, low test accuracy. High variance.

  • Causes: Model too complex, too many features, little training data.

  • Mitigation: More data, regularization (L1/L2), pruning (trees), dropout (NNs), cross-validation.

• Underfitting: Model fails to learn underlying pattern. Low training & test accuracy. High bias.

  • Causes: Model too simple, insufficient features, excessive regularization.

  • Mitigation: More complex model, feature engineering, reduce regularization.

• Bias-Variance Tradeoff: Inevitable compromise; optimal model balances both.

Least Squares Methods (Short Note)

• Goal: Find parameters that minimize sum of squared residuals between observed and predicted values.

• Linear Regression (Ordinary Least Squares - OLS): Closed-form solution \(\hat{\beta} = (X^TX)^{-1}X^Ty\). Assumptions: linearity, independence, homoscedasticity, normality of errors.

• Regularized Variants:

  • Ridge (L2): Adds \(\lambda ||\beta||_2^2\) penalty. Shrinks coefficients, handles multicollinearity.

  • Lasso (L1): Adds \(\lambda ||\beta||_1\) penalty. Can drive coefficients to zero, performing feature selection.

• Use: Fundamental for linear model fitting, baseline for regression tasks.

Decision Trees for Game Development (Short Note)

• Purpose: Model NPC decision-making logic in a readable, modifiable way.

• Structure: Hierarchical tree where internal nodes are conditions (e.g., player_in_sight?, health < 30%?), branches are outcomes, leaves are actions (e.g., attack, flee, patrol).

• Advantages: Intuitive for designers to edit, fast execution, easy to debug.

• Limitations: Can become large and repetitive; often combined with other techniques (behavior trees, utility AI) for complex behaviors.

• Example: Enemy AI: IF (player_distance < 10) AND (health > 50%) THEN attack ELSE IF (ammo < 20%) THEN reload ELSE patrol.

Board Game Theory (Short Note)

• Application of combinatorial game theory to deterministic, perfect-information, turn-based board games (Chess, Go, Checkers).

• Key Concepts:

  • Game Tree: Explodes exponentially (e.g., ~10^120 for Chess).

  • Minimax & Alpha-Beta: Core search algorithms with pruning.

  • Evaluation Function: Heuristic to estimate board strength when search depth is limited (e.g., material count in Chess).

  • Complexity: Many are PSPACE-complete or EXPTIME-complete, meaning no polynomial-time algorithm exists unless P=NP.

  • Solved Games: Tic-tac-toe, Connect Four, Checkers are "solved" (optimal play known). Go was solved by AlphaGo (using deep RL, not pure tree search).

• Modern Impact: Drives AI research in search, heuristics, and deep learning integration (AlphaZero, MuZero).