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

UNIT 5: Machine Learning for Data Science

I. Foundations of Machine Learning

Characteristics of Algorithms

• Definiteness: Each step is precisely defined.

• Input: Zero or more well-defined inputs.

• Output: At least one well-defined output.

• Finiteness: Terminates after a finite number of steps.

• Effectiveness: Each step is basic and feasible.

Tools for Algorithm Analysis

• Asymptotic Notation (Big O, Ω, Θ): Describes upper/lower/tight bounds on time/space complexity.

• Recurrence Relations: For divide-and-conquer and DP algorithms (e.g., Master Theorem).

• Empirical Analysis: Timing experiments on real hardware.

Well-Posed Learning Problem

A problem is well-posed if:

1. A task (T) is defined (e.g., classification, regression).

2. A performance measure (P) is defined (e.g., accuracy, MSE).

3. There exists experience (E) from which the system can learn.

\boxed{\text{Task (T) + Performance Measure (P) + Experience (E)}}

Lazy vs Eager Learning

Divide and Conquer Technique

1. Divide: Break the problem into smaller subproblems.

2. Conquer: Solve subproblems recursively.

3. Combine: Merge solutions to subproblems.

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

• Time Complexity: Often given by recurrence: T(n) = aT(n/b) + f(n).

Dynamic Programming in Machine Learning

• Used for optimal sequential decision problems with overlapping subproblems.

• Key Idea: Store solutions to subproblems to avoid recomputation (memoization).

• RL Application: Value Iteration and Policy Iteration for solving MDPs (Bellman Equations).

II. Data Preparation and Handling

Data Description and Preparation

• Description: Summarize data (statistics: mean, median, mode, std dev, quartiles).

• Preparation: Cleaning (handle missing values, outliers), Transformation (normalization, standardization), Feature Engineering, Dimensionality Reduction (PCA).

Data Extraction Tools & Techniques in Python

• Files: pandas.read_csv(), pandas.read_json().

• Databases: sqlalchemy, pymongo.

• Web/APIs: requests library, BeautifulSoup for HTML parsing.

• Streaming: Apache Kafka clients.

Reading CSV and JSON Files

# CSV

import pandas as pd

df = pd.read_csv('file.csv', delimiter=',', header=0)

# JSON

df = pd.read_json('file.json')  # or json.load(open('file.json'))

Text Processing Libraries in Python

• nltk: Tokenization, stemming, lemmatization, stop words.

• spaCy: Industrial-strength NLP, entity recognition, dependency parsing.

• scikit-learn: CountVectorizer, TfidfVectorizer for feature extraction.

• re: Regular expressions for pattern matching.

Holdout Method

• Procedure: Split dataset into Training Set (e.g., 70-80%) and Test Set (e.g., 20-30%).

• Purpose: Evaluate model performance on unseen data.

• Limitation: High variance in estimate if dataset is small; doesn't use all data for training.

• Common Variant: Train-Validation-Test Split (e.g., 60-20-20).

III. Supervised Learning Algorithms

A. Decision Trees

Recursive Induction

• Top-down, greedy algorithm.

• At each node, select the best attribute (using a splitting criterion like Information Gain) to partition the data.

• Recurse on each partitioned subset until a stopping condition (pure node, max depth, min samples).

Entropy and Information Gain

• Entropy (H): Measure of impurity/uncertainty in a set of examples 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.

\boxed{H(S) = 0 \text{ (pure)}, H(S) = \log_2 c \text{ (max impurity)}}

• 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 subset of S for which attribute A has value v.

Calculation Example (From Past Paper)

Dataset:

1. Overall Entropy H(S):

   • Total samples |S| = 7

   • Yes: 3, No: 4 → $$\displaystyle p_{yes}=3/7 $$, $$\displaystyle p_{no}=4/7 $$

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

2. IG for "Credit Score":

   • High (3 samples): Yes=2, No=1 → $$\displaystyle H(High)=-\left(\frac{2}{3}\log_2\frac{2}{3}+\frac{1}{3}\log_2\frac{1}{3}\right) \approx 0.918 $$

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

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

   • $$\displaystyle IG(S, Credit) = 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

• Strategies:

  1. Pruning: Remove branches that fit noise (Pre-pruning: stop early; Post-pruning: grow full tree then trim).

  2. Use Robust Splitting Criteria: Gain Ratio (corrects IG bias towards many-valued attributes).

  3. Ensemble Methods: Random Forest (averaging reduces variance).

  4. Set Minimum Samples: Require minimum samples per leaf/node.

Decision Trees for Game Development

• Use: AI decision-making for NPCs (e.g., combat choices, dialogue).

• Advantage: Interpretable, fast evaluation.

• Limitation: Can become large/unwieldy for complex state spaces; not ideal for real-time strategy.

B. Linear Models and Gradient Descent

Least Squared Error Hypothesis

• Goal: Find linear function $$\displaystyle h(x) = w^T x + b $$ that minimizes Mean Squared Error (MSE).

• Cost Function (MSE):

$$J(w, b) = \frac{1}{2m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)})^2$$

(Factor 1/2 for convenience in derivative).

• Closed-Form Solution (Normal Equation):

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

(Computationally expensive for large features).

Gradient Descent Delta Rule

• Idea: Iteratively adjust weights in direction of negative gradient of cost function.

• Update Rule (for weight $$\displaystyle w_j $$):

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

where $\alpha$ is the **learning rate**.

• For Linear Regression (MSE):

$$\frac{\partial J}{\partial w_j} = \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)}) x_j^{(i)}$$

\boxed{w_j := w_j - \alpha \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)}) x_j^{(i)}}

Implementing Linear Regression with Gradient Descent

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

2. Repeat until convergence:

   • Compute predictions: $$\displaystyle h = Xw + b $$.

   • Compute error: $$\displaystyle error = h - y $$.

   • Update weights: $$\displaystyle w := w - \alpha \frac{1}{m} X^T(error) $$.

   • Update bias: $$\displaystyle b := b - \alpha \frac{1}{m} \sum(error) $$.

3. Convergence Criteria: Cost change < threshold, max iterations.

Gradient Descent in TensorFlow

import tensorflow as tf

# Model

model = tf.keras.Sequential([tf.keras.layers.Dense(1, input_shape=(n_features,))])

# Compile with SGD optimizer

model.compile(optimizer=tf.keras.optimizers.SGD(learning_rate=alpha),

              loss='mse')

# Train

model.fit(X_train, y_train, epochs=100, batch_size=m)

Mini-Batch Gradient Descent

• Idea: Use a small random subset (mini-batch) of training examples to compute gradient per update.

• Advantages:

  • Faster than Batch GD (fewer iterations per epoch).

  • More stable convergence than Stochastic GD (less noisy gradient).

  • Leverages vectorized hardware (GPUs).

• Common Batch Sizes: 32, 64, 128, 256.

IV. Ensemble Learning

Bagging vs Boosting

Random Forest Algorithm

1. For t = 1 to T (number of trees):

   • Draw a bootstrap sample (with replacement) from training data.

   • Grow a decision tree on this sample. At each split, consider only a random subset of features (e.g., √p for classification).

2. For classification: Aggregate predictions by majority vote. For regression: average predictions.

• Key Hyperparameters: n_estimators, max_features, max_depth.

Robustness of Ensemble Methods

• Error Averaging: Random errors of individual models cancel out.

• Reduced Variance: Especially with Bagging; models are de-correlated.

• Bias Reduction: Boosting sequentially corrects errors.

• Stability: Less sensitive to noise, outliers, and specific hyperparameter choices than a single complex model.

• Theoretical Guarantee: As number of base learners increases, ensemble error converges to a lower bound (under i.i.d. assumptions).

Random Forest (Short Note)

• Ensemble of Decision Trees using Bagging + Random Feature Selection.

• Advantages: High accuracy, handles non-linearities, robust to outliers/noise, provides feature importance, reduces overfitting.

• Disadvantages: Less interpretable than single tree, can be slow for prediction, biased toward features with more levels.

• Applications: Classification/regression in finance, bioinformatics, remote sensing.

V. Reinforcement Learning

Bellman Equations

• Core Idea: Express value of a state/action in terms of immediate reward and value of successor state/action.

• Bellman Expectation Equation (State Value):

$$V(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]$$

• Bellman Expectation Equation (Action Value):

$$Q(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \sum_{a'} \pi(a'|s') Q(s',a')$$

• Bellman Optimality Equation:

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

\boxed{V^*(s) = \max_a \mathbb{E}[R_{t+1} + \gamma V^*(S_{t+1}) | S_t=s, A_t=a]}

Q-learning vs SARSA

Policy Gradient Methods

• Directly parameterize policy: $\pi(a|s, \theta)$ (e.g., softmax over linear scores).

• 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]$$

• Update: $$\displaystyle \theta \leftarrow \theta + \alpha \nabla_\theta J(\theta) $$.

• Examples: REINFORCE, Actor-Critic (A2C/A3C), PPO, TRPO.

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

Generative Adversarial Imitation Learning (GAIL)

• Goal: Learn policy by imitating expert demonstrations, not from reward.

• Architecture:

  1. Generator (Policy $$\displaystyle \pi_\theta $$): Produces trajectories.

  2. Discriminator (D): Trained to distinguish expert trajectories from policy trajectories.

• Objective: Minimize JS divergence between expert and policy state-action distributions.

$$\min_\theta \max_D V(\pi_\theta, D) = \mathbb{E}_{\pi_E}[\log D(s,a)] + \mathbb{E}_{\pi_\theta}[\log(1-D(s,a))]$$

• Difference from RL: No hand-designed reward; reward is implicit from discriminator (like GANs).

Value Iteration and Policy Iteration

• Value Iteration:

  1. Initialize $V(s)$ arbitrarily.

  2. Repeat until convergence:

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

3.  Extract greedy policy: $$\displaystyle \pi(s) = \arg\max_a Q(s,a) $$.

*   **Pros:** Simple, no policy evaluation loop. **Cons:** Slow convergence.

• Policy Iteration:

  1. Initialize policy $$\displaystyle \pi_0 $$.

  2. Policy Evaluation: Solve $$\displaystyle V^{\pi_k} $$ exactly (via linear solve or iterative).

  3. Policy Improvement: $$\displaystyle \pi_{k+1}(s) = \arg\max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^{\pi_k}(s') \right] $$.

  4. Repeat until $$\displaystyle \pi_{k+1} = \pi_k $$.

  • Pros: Fast convergence (often few iterations). Cons: Policy evaluation step can be expensive.

Recent Trends in RL Architectures

• Deep RL: Combining deep neural networks with RL (DQN, DDPG, PPO).

• Model-Based RL: Learn dynamics model $P(s'|s,a)$ for planning (e.g., MuZero).

• Hierarchical RL: Options, sub-policies for temporal abstraction.

• Meta-RL: Learning to adapt quickly to new tasks (e.g., MAML).

• Multi-Agent RL: Independent/cooperative learning (MADDPG, QMIX).

• Offline RL: Learning from fixed dataset without environment interaction (BCQ, CQL).

VI. Probabilistic Methods

Probabilistic Modelling with Example

• Idea: Model uncertainty using probability distributions. Parameters are random variables.

• Example: Naive Bayes Classifier.

  • Model: $$\displaystyle P(C|X) \propto P(C) \prod_i P(X_i|C) $$ (conditional independence assumption).

  • Learning: Estimate $P(C)$ (prior) and $$\displaystyle P(X_i|C) $$ (likelihood) from training data (counts with Laplace smoothing).

  • Prediction: $$\displaystyle \hat{C} = \arg\max_C P(C) \prod_i P(x_i|C) $$.

Probabilistic Inference in Machine Learning

• Task: Compute posterior distributions $P(H|D)$ given observed data $D$ and hypothesis/model $H$.

• Methods:

  • Exact Inference: Enumeration, Variable Elimination (for small graphs).

  • Approximate Inference:

    • Sampling: MCMC (Gibbs, Metropolis-Hastings), Importance Sampling.

    • Variational Inference: Approximate posterior $q(z|\theta)$ by minimizing KL divergence to true posterior $p(z|D)$.

• Application: Bayesian Neural Networks, Gaussian Processes, Latent Variable Models (LDA, HMM).

VII. Model Evaluation and Validation

Precision and Recall with Example

• Confusion Matrix:

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

• Precision (P): Of all predicted positives, how many are correct?

$$P = \frac{TP}{TP + FP}$$

• Recall (R): Of all actual positives, how many did we find?

$$R = \frac{TP}{TP + FN}$$

• Example (Spam Filter):

  • TP=50 (spam correctly flagged), FP=5 (good mail flagged spam), FN=10 (spam missed).

  • Precision = 50/(50+5) = 0.91 → "When we flag spam, we're right 91% of the time."

  • Recall = 50/(50+10) = 0.83 → "We catch 83% of all spam."

Methods for Evaluating Classifiers

1. Holdout/Cross-Validation: Estimate generalization accuracy.

2. Confusion Matrix & Derived Metrics: Accuracy, Precision, Recall, F1-Score, Specificity.

3. ROC Curve & AUC: Trade-off between TPR (Recall) and FPR across thresholds.

4. Precision-Recall Curve: Especially useful for imbalanced datasets.

5. Log Loss: For probabilistic classifiers.

6. Cost-Sensitive Evaluation: When errors have different costs.

Overfitting and Underfitting

VIII. Applications of Machine Learning

A. Graphs, Maps, and Search

ML in Graphs, Maps, and Map Searching

• Graph Applications: Social network analysis (community detection, link prediction), fraud detection, recommendation systems (as bipartite graphs).

• Map/Search Applications:

  • Shortest Path: Dijkstra, A* (heuristic-guided).

  • Traffic Prediction: Using historical GPS/traffic data (time-series forecasting).

  • ETA Estimation: Regression on distance, time, congestion features.

  • Geospatial ML: Clustering points of interest, predicting crime hotspots.

A Pathfinding Algorithm*

• Idea: Best-first search using heuristic $h(n)$ (estimated cost to goal).

• Evaluation Function: $$\displaystyle 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).

• Optimality: Guaranteed if $h(n)$ is admissible and consistent (monotone).

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

Breadth-First Search (BFS) for Pathfinding

• Mechanism: Explore all nodes at current depth ($d$) before depth ($d+1$). Uses queue (FIFO).

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

• Completeness: Yes (if graph is finite).

• Time/Space Complexity: $$\displaystyle O(b^d) $$, where $b$ = branching factor, $d$ = depth of shallowest solution.

• Limitation: Memory intensive for large graphs.

Efficiency in Complex Problems (Heuristics)

• Problem: State space explosion (combinatorial explosion).

• Solution: Use informed search with heuristics (domain-specific knowledge).

• Heuristic Properties:

  • Admissible: $$\displaystyle h(n) \leq h^*(n) $$ (true cost).

  • Consistent: $h(n) \leq c(n,a,n') + h(n')$ for every neighbor $n'$.

• Trade-off: Better heuristic → fewer nodes expanded → faster, but heuristic computation itself has cost.

B. Matching and Allocation

Stable Marriages Algorithms in ML

• Problem: Match two sets (e.g., users-items, tasks-agents) with preferences, ensuring stability (no pair prefers each other over current match).

• Gale-Shapley Algorithm (Deferred Acceptance):

  1. All unmatched proposers propose to their most-preferred acceptor.

  2. Each acceptor temporarily holds the best proposal and rejects others.

  3. Repeat until all are matched.

• ML Applications:

  • Recommendation Systems: Stable matching for user-item pairs.

  • School Choice/Residency Matching: Matching applicants to programs.

  • Task Allocation: Matching workers to tasks in crowdsourcing.

C. Biology and Healthcare

Interconnectedness on Personal Genomes

• Goal: Understand gene-gene and gene-environment interactions.

• ML Methods:

  • Network Inference: Bayesian networks, graphical models to infer regulatory networks.

  • Feature Selection: Identify interacting SNPs (single nucleotide polymorphisms) for disease prediction.

  • Multi-omics Integration: Combine genomic, transcriptomic, epigenomic data using multi-view learning.

• Challenge: High dimensionality ($$\displaystyle p >> n $$), noise, complex non-linear interactions.

Prediction of Preterm Birth

• Task: Binary classification (preterm vs term) using clinical, genomic, and behavioral data.

• Data Sources: Electronic Health Records (EHR), cervical length (ultrasound), fetal fibronectin tests, wearable sensor data.

• ML Models: Logistic Regression, Random Forest, Gradient Boosting, RNNs/LSTMs for longitudinal data.

• Key Challenge: Class imbalance (preterm is rare), interpretability for clinicians.

D. Gaming and AI

Game Theory and its Application to AI

• Game Theory: Study of strategic interaction where outcome depends on choices of multiple rational agents.

• AI Application: Model multi-agent systems (adversarial/cooperative).

  • Adversarial: Chess, Go (minimax, MCTS).

  • Cooperative/Competitive: Autonomous driving (interaction prediction), multi-robot systems.

  • Mechanism Design: Creating rules (auctions, markets) to achieve desired outcomes.

Minimax Algorithm and its Functions

• Purpose: Determine optimal move for a zero-sum, perfect-information, turn-based game.

• Idea: Assume opponent plays optimally to minimize your score. Maximize your minimum possible payoff.

• Functions:

  1. max_value(state): Returns utility of best move for maximizer.

  2. min_value(state): Returns utility of best move for minimizer.

• Pseudocode:

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

• Enhancements: Alpha-Beta pruning (cuts branches that won't affect decision).

Rule-Based Systems

• Architecture: IF <condition> THEN <action> (production rules) + Inference Engine (forward/backward chaining) + Knowledge Base.

• Example: MYCIN (medical diagnosis).

• Advantages: Transparent, explainable, easy to encode expert knowledge.

• Disadvantages: Brittle, hard to maintain, doesn't learn, knowledge acquisition bottleneck.

Static vs Kinematic Representation in 3D

• Static Representation: Describes geometry only (vertices, edges, polygons, textures). What the object is.

  • Example: 3D model file (.obj, .fbx).

• Kinematic Representation: Describes motion and articulation (joints, degrees of freedom, movement constraints). How the object moves.

  • Example: Skeleton hierarchy for character animation, joint rotation/translation parameters.

• In Game AI: Static for rendering; kinematic for animation systems, ragdoll physics.

Components of Coordinated Movement

1. Path Planning: Global route (A*, navigation mesh).

2. Motion Planning: Local, collision-free trajectory (RRT*, potential fields).

3. Animation: Playing/ blending motion capture or procedural animations.

4. Locomotion: Gait generation (walk, run, jump).

5. Steering: Low-level adjustments (seek, flee, arrive, obstacle avoidance).

6. Physics: Ragdoll, inverse kinematics (IK) for foot placement.

State Machines vs Behavior Trees

Finite State Machine Construction (Example: Guard AI)

States: Guard, Fight, Flee.

Transitions:

• Guard → Fight if see_thief == true.

• Fight → Flee if health_low == true AND thief_strong == true.

• Flee → Guard if safe == true.

• (Self-loops for staying in state if conditions not met).

Fuzzy Time Series and Markov Chains

• Fuzzy Time Series: Uses fuzzy logic (linguistic terms like "high", "medium") to model uncertainty in time series data. Steps: Fuzzify, establish fuzzy relationships, forecast, defuzzify.

• Markov Chains: Stochastic model where next state depends only on current state (memoryless property). Transition matrix $$\displaystyle P_{ij} = P(S_{t+1}=j | S_t=i) $$.

• Combined (FMC): States are fuzzy sets; transition probabilities between fuzzy states. Used for forecasting with uncertainty (e.g., stock prices, weather).

Solving Pay-off Matrices

• For 2x2 Games: Use dominance or mixed strategy Nash equilibrium.

  • Pure Strategy: Choose row/column with maximin/minimax.

  • Mixed Strategy: Solve for probabilities $p, (1-p)$ for row player that make column player indifferent.

$$E[\text{Column}] = p \cdot A_{11} + (1-p) \cdot A_{21} = p \cdot A_{12} + (1-p) \cdot A_{22}$$

    Solve for $p$.

• For Larger Games: Linear programming (solve for optimal mixed strategies).

Nash Equilibrium (Penalty Kicks Example)

• Find Mixed NE: Let kicker play Left with prob $p$, Goalie play Left with prob $q$.

• Kicker's Indifference (to make Goalie indifferent):

  • Goalie's payoff if Left: $$\displaystyle 0.6p + 0.4(1-p) = 0.4 + 0.2p $$

  • Goalie's payoff if Right: $$\displaystyle 0.5p + 0.4(1-p) = 0.4 + 0.1p $$

  • Set equal: $$\displaystyle 0.4 + 0.2p = 0.4 + 0.1p \Rightarrow p=0 $$ (only pure? Check).

  • Actually, kicker wants to maximize own payoff. Compute kicker's best response to each $q$.

  • Kicker's payoff if Left: $$\displaystyle 1.4q + 1.7(1-q) = 1.7 - 0.3q $$

  • Kicker's payoff if Right: $$\displaystyle 1.5q + 1.5(1-q) = 1.5 $$

  • If $$\displaystyle q < 2/3 $$, Left gives >1.5. If $$\displaystyle q > 2/3 $$, Right gives 1.5. If $$\displaystyle q=2/3 $$, indifferent.

  • Goalie's payoff if Left: $$\displaystyle 0.6p + 0.4(1-p) = 0.4 + 0.2p $$

  • Goalie's payoff if Right: $$\displaystyle 0.5p + 0.4(1-p) = 0.4 + 0.1p $$

  • Goalie always prefers Left if $$\displaystyle p>0 $$. So pure NE: (Kicker Right, Goalie Left) → (1.7, 0.4)? But kicker would deviate to Left for 1.7? Check: If Goalie plays Left, Kicker best is Right (1.7 > 1.4). If Kicker plays Right, Goalie best is Left (0.4 > 0.4? equal). So (Right, Left) is NE: payoffs (1.7, 0.4). Also (Right, Right) is NE? Kicker: 1.5 vs 1.7→ no. (Left, Left): Kicker 1.4 vs 1.7→ no. So only one pure NE: (Kicker: Right, Goalie: Left). Mixed NE exists if both indifferent simultaneously—here not possible as Goalie always prefers Left unless $$\displaystyle p=0 $$ (kicker never Left). So only pure NE.

Model of Game AI

• Layered Architecture:

  1. High-Level Strategy (Planning): Goals, resource management, long-term plans (e.g., GOAP - Goal-Oriented Action Planning).

  2. Mid-Level Tactics (Decision Making): Choose actions to achieve goals (Behavior Trees, Utility AI, FSMs).

  3. Low-Level Execution (Movement/Animation): Pathfinding, steering, animation blending.

  4. Perception: Sensing world (raycasts, audio triggers).

  5. World Model: Knowledge representation (blackboard, spatial awareness).

Stages of Motor Learning

1. Cognitive Stage: Understand task, high error, conscious control.

2. Associative Stage: Error decreases, movement becomes smoother, still requires attention.

3. Autonomous Stage: Skill is automatic, low cognitive load, resistant to stress/distraction.

Board Game Theory

• Perfect Information, Deterministic, Turn-Based games.

• Key Concepts:

  • Game Tree: States as nodes, moves as edges.

  • Minimax: Optimal play assuming opponent is perfect.

  • Alpha-Beta Pruning: Reduce tree search complexity.

  • Monte Carlo Tree Search (MCTS): Simulate random playouts from current state; balance exploration/exploitation (UCB formula). Used in AlphaGo.

  • Evaluation Function: Heuristic to estimate non-terminal state value (e.g., material count in chess).

  • Opening Books/Endgame Tablebases: Precomputed knowledge.

IX. Python Implementation for Data Science

Matrix Inversion with Python Libraries

import numpy as np

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

A_inv = np.linalg.inv(A)  # Throws LinAlgError if singular

# Or solve Ax = b: x = np.linalg.solve(A, b)

Data Visualization with Matplotlib

• Core: import matplotlib.pyplot as plt

• Workflow: plt.figure(), plt.plot()/scatter()/bar(), plt.xlabel(), plt.ylabel(), plt.title(), plt.legend(), plt.show().

• Object-Oriented API: fig, ax = plt.subplots(); ax.plot(...) for more control.

Creating Bar Charts in Python

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 Marks')

plt.ylim(0, 100)

plt.show()

Statistical Calculations with NumPy

import numpy as np

data = np.array([69, 90, 76, 88, 91])

avg = np.mean(data)        # 82.8

var = np.var(data)         # Population variance by default

std = np.std(data)         # Population std dev

# For sample variance/std: ddof=1

var_sample = np.var(data, ddof=1)

BeautifulSoup Library for Web Scraping

from bs4 import BeautifulSoup

import requests

url = "http://example.com"

response = requests.get(url)

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

# Find all <a> tags

links = soup.find_all('a')

for link in links:

    print(link.get('href'), link.text)

JSON Parsing in Python

import json

# From file

with open('data.json') as f:

    data = json.load(f)  # Returns dict/list

# From string

json_string = '{"name": "Alice", "age": 30}'

data = json.loads(json_string)

# To string

json_out = json.dumps(data, indent=2)

[!TIP] Exam Focus

• Decision Trees: Be expert at calculating Entropy & Information Gain (past paper question).

• Ensemble Learning: Clearly contrast Bagging vs Boosting and explain Random Forest mechanism.

• Reinforcement Learning: Distinguish Q-learning vs SARSA (on/off-policy) and TD vs MC. Know Bellman Equations.

• Python: Expect short code snippets for reading files, plotting, NumPy stats, matrix inversion.

• Applications (Gaming): Minimax, FSM vs BT, and A* are high-frequency.

• Foundations: Lazy vs Eager, Divide & Conquer, Dynamic Programming (in RL context) are theoretical must-knows.