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

UNIT 4: Advanced Machine Learning and AI for Data Science

1. Algorithmic Foundations

Characteristics of Algorithms

• Definiteness: Each step is precisely defined.

• Input: Zero or more well-defined inputs.

• Output: One or more well-defined outputs.

• Finiteness: Terminates after a finite number of steps.

• Effectiveness: Each step is basic and feasible.

Tools for Algorithm Analysis

• Time Complexity: Measures the amount of time an algorithm takes as a function of input size. Expressed using Big O notation (e.g., $O(n)$, $$\displaystyle O(n^2) $$, $O(\log n)$).

• Space Complexity: Measures the amount of memory an algorithm uses as a function of input size.

• Best, Average, Worst-case Analysis: Evaluates performance under different input scenarios.

Divide and Conquer Technique

• Principle: Break a problem into smaller sub-problems, solve them recursively, and combine their solutions.

• ML Example: Decision Tree Induction. The dataset is recursively split (divide) based on an attribute, and the process continues on subsets (conquer) until a stopping criterion is met. The final tree is the combination of all splits.

  • Complexity: Often $O(n \log n)$ for balanced trees, $$\displaystyle O(n^2) $$ for unbalanced.

Dynamic Programming in Machine Learning

• Principle: Solves complex problems by breaking them into overlapping sub-problems and storing their solutions (memoization) to avoid redundant computation.

• Importance: Crucial for optimization problems with optimal substructure.

• ML Example: Sequence Alignment in bioinformatics (e.g., Needleman-Wunsch algorithm for global alignment). It builds a matrix of optimal scores for subsequences, using previously computed values.

Well-Posed Learning Problems

• Definition (Hadamard): A problem is well-posed if a solution:

  1. Exists (there is a hypothesis that fits the data reasonably).

  2. Is Unique (the learning algorithm finds a single, consistent solution).

  3. Is Stable (small changes in the training data lead to small changes in the learned hypothesis).

• Example: Linear regression with more data points than features and no multicollinearity is generally well-posed. An underdetermined system (fewer samples than features) is ill-posed (non-unique solutions).

Lazy vs Eager Learning

[!TIP] Exam Focus: Be ready to compute Entropy and Information Gain for a given dataset (like the Credit Score example from past papers). Know the formulas:

Entropy(S):

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

Information Gain(S, A):

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

2. Decision Trees and Ensemble Methods

Decision Tree Induction: Recursive Process

1. Start: Begin with the entire training set at the root node.

2. Select Best Attribute: Choose the attribute that best splits the data (using criteria like Information Gain or Gini Index).

3. Split: Partition the data based on the selected attribute's values.

4. Recurse: For each subset, repeat steps 2-3 until a stopping condition is met (e.g., all instances belong to same class, no more attributes, minimum samples per node).

5. Leaf Node: Assign the majority class of the subset to the leaf.

Handling Noisy Data: Effects & Strategies

• Effect: Noise causes overfitting. The tree becomes overly complex, capturing random fluctuations, leading to poor generalization on unseen data.

• Strategies:

  • Pre-pruning (Early Stopping): Halt tree growth early (e.g., set minimum samples per split, maximum tree depth).

  • Post-pruning: Build full tree, then remove branches that seem to generalize poorly (e.g., reduced error pruning, cost-complexity pruning).

  • Ensemble Methods: Use bagging/boosting to average out noise.

Ensemble Learning: Bagging vs Boosting

Random Forest: Architecture & Mechanism

• Architecture: Ensemble of decision trees.

• Working Mechanism:

  1. Bootstrap Sampling: For each tree, create a random sample of the training data (with replacement).

  2. Feature Randomness: At each node split, consider only a random subset of features (not all). This decorrelates the trees.

  3. Aggregation: Final prediction is the mode (classification) or mean (regression) of all individual tree predictions.

• Key Hyperparameter: n_estimators (number of trees), max_features.

Robustness of Ensemble Methods

• Error Reduction: Ensembles reduce both bias (boosting) and variance (bagging).

• Averaging Effect: Individual model errors (especially random errors/noise) tend to cancel out when averaged.

• Diversity: Different models make different errors. Combining diverse models leads to a more robust, stable predictor.

• Theoretical Guarantee: If base learners are "weak" (slightly better than random), boosting can create a "strong" learner (arbitrarily accurate).

Application: Decision Trees in Game Development

• Used for NPC (Non-Player Character) behavior and decision-making.

• Example: An AI guard's decision tree:

  • Root: SeesPlayer?

    • Yes: PlayerWeaponDrawn?

      • Yes: Attack or TakeCover (based on health/ammo).

      • No: Investigate or Ignore (based on distance).

    • No: Patrol or Idle.

• Advantage: Transparent, easy to debug and tweak for designers.

3. Neural Networks and Linear Models

Multi-Layer Perceptron (MLP)

• Architecture:

  • Input Layer: One neuron per feature.

  • Hidden Layer(s): Apply non-linear transformations. Number of layers/neurons is a hyperparameter.

  • Output Layer: Produces the final prediction (e.g., class probabilities via Softmax).

  • Activation Functions: Introduce non-linearity (e.g., ReLU, Sigmoid, Tanh).

• Learning Process (Backpropagation):

  1. Forward Pass: Compute output for a given input using current weights.

  2. Compute Loss: Compare prediction with true label using a loss function (e.g., Cross-Entropy, MSE).

  3. Backward Pass (Backpropagation): Calculate gradient of loss w.r.t. each weight using the chain rule.

  4. Weight Update: Update weights using an optimization algorithm (e.g., Gradient Descent):

$$w_{new} = w_{old} - \eta \cdot \frac{\partial L}{\partial w}$$

where $\eta$ is the learning rate.

Least Squares Methods

• Least Squared Error Hypothesis: Find parameters $\theta$ that minimize the sum of squared differences between predicted $$\displaystyle \hat{y}_i = f(x_i; \theta) $$ and actual $$\displaystyle y_i $$ values.

$$\min_{\theta} \sum_{i=1}^{n} (y_i - f(x_i; \theta))^2$$

• Linear Regression using Gradient Descent:

  • Model: $$\displaystyle \hat{y} = w^T x + b $$

  • Loss (MSE): $$\displaystyle L = \frac{1}{n} \sum (y_i - (w^T x_i + b))^2 $$

  • Gradients: $$\displaystyle \frac{\partial L}{\partial w} = -\frac{2}{n} \sum x_i (y_i - \hat{y}_i) $$, $$\displaystyle \frac{\partial L}{\partial b} = -\frac{2}{n} \sum (y_i - \hat{y}_i) $$

  • Update rules applied iteratively.

Gradient Descent Techniques

• Gradient Descent Delta Rule: A specific weight update rule for linear units using gradient descent on the squared error. For a single weight $$\displaystyle w_j $$:

$$\Delta w_j = \eta (t - y) x_j$$

where $t$ is target, $y$ is output, $$\displaystyle x_j $$ is input.

• Mini-Batch Gradient Descent:

  • Compromise between Batch GD (uses entire dataset, slow, stable) and Stochastic GD (uses one sample, noisy, fast).

  • Uses a small random subset (mini-batch) of the training data for each update.

  • Advantages: More frequent updates than Batch, less noisy than SGD, computationally efficient (vectorized operations).

• Gradient Descent Steps in TensorFlow (Keras API):

  1. Define model architecture (Sequential, Dense layers).

  2. Compile model: Specify optimizer (e.g., Adam, SGD), loss function (e.g., mse, categorical_crossentropy), and metrics.

  3. Fit model: model.fit(X_train, y_train, batch_size=32, epochs=10). TensorFlow automatically handles mini-batch creation, forward/backward passes, and weight updates.

4. Reinforcement Learning (RL)

Fundamentals

• Markov Decision Process (MDP): Formal framework defined by $(S, A, P, R, \gamma)$:

  • $S$: Set of states.

  • $A$: Set of actions.

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

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

  • $\gamma \in [0,1]$: Discount factor for future rewards.

• Goal: Find a policy $\pi(a|s)$ that maximizes expected cumulative discounted reward (Return $$\displaystyle G_t $$).

Bellman Equations

• Value Function (State-Value): Expected return starting from state $s$, following policy $\pi$.

$$V^{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s] = \sum_a \pi(a|s) \sum_{s',r} P(s',r | s,a) [r + \gamma V^{\pi}(s')]$$

• Action-Value Function (Q-Function): Expected return taking action $a$ in state $s$, then following $\pi$.

$$Q^{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a] = \sum_{s',r} P(s',r | s,a) [r + \gamma \sum_{a'} \pi(a'|s') Q^{\pi}(s',a')]$$

• Optimality: $$\displaystyle V^*(s) = \max_a Q^*(s,a) $$, $$\displaystyle Q^*(s,a) = \sum_{s',r} P(s',r|s,a)[r + \gamma \max_{a'} Q^*(s',a')] $$.

Core RL Algorithms

• Value Iteration: Iteratively applies the Bellman optimality equation to update $V(s)$ until convergence. Model-based, finds optimal value function, then derives policy.

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

• Policy Iteration: Alternates between:

  1. Policy Evaluation: Compute $$\displaystyle V^{\pi} $$ for current policy $\pi$.

  2. Policy Improvement: Update policy greedily: $$\displaystyle \pi'(s) = \arg\max_a \sum_{s',r} P(s',r|s,a)[r + \gamma V^{\pi}(s')] $$. Repeat until policy stable.

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

  | Feature | Temporal Difference (TD) | Monte Carlo (MC) | | :--- | :--- | :--- | | Update | Updates using bootstrapped estimates (current estimate of $V(s')$). $$\displaystyle V(s) \leftarrow V(s) + \alpha [r + \gamma V(s') - V(s)] $$ | Updates only after episode completion using actual return $$\displaystyle G_t $$. $$\displaystyle V(s) \leftarrow V(s) + \alpha [G_t - V(s)] $$ | | Model | Model-free. Does not require full knowledge of $P, R$. | Model-free. | | Variance | Lower variance (uses current estimate). | Higher variance (depends on sampled returns). | | Bias | Can be biased due to bootstrapping. | Unbiased (uses actual returns). | | Example | SARSA, Q-learning | Every-Visit MC |

• Q-learning vs SARSA

  | Feature | Q-learning | SARSA | | :--- | :--- | :--- | | Type | Off-policy. Learns optimal $$\displaystyle Q^* $$ independent of behavior policy. | On-policy. Learns $$\displaystyle Q^{\pi} $$ for the same policy being followed. | | 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 (e.g., $\epsilon$-greedy). | Learns policy including exploration. Safer in risky environments. | | Convergence | Converges to optimal $$\displaystyle Q^* $$ with proper conditions. | Converges to $$\displaystyle Q^{\pi} $$ for the exploration policy. |

Advanced RL Methods

• Policy Gradient Methods: Directly optimize the policy $$\displaystyle \pi_\theta(a|s) $$ by gradient ascent on expected return $$\displaystyle J(\theta) = \mathbb{E}_{\pi_\theta}[G] $$. Uses the policy gradient theorem: $$\displaystyle \nabla J(\theta) = \mathbb{E}_{\pi_\theta}[\nabla \log \pi_\theta(a|s) \cdot Q^{\pi}(s,a)] $$. Examples: REINFORCE, Actor-Critic, PPO.

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

  • Standard RL: Agent learns from scalar rewards provided by the environment. Goal: maximize cumulative reward.

  • GAIL: Inverse RL/Imitation Learning. Agent learns by matching the behavior of an expert demonstrator, without needing the reward function. Uses a discriminator (like GAN) to distinguish expert vs agent trajectories, and the agent's policy is trained to fool the discriminator.

• Recent Trends in RL Architectures:

  • Deep RL: Combining deep neural networks with RL (e.g., DQN, DDPG, A3C).

  • Model-Based RL: Learning a model of the environment dynamics ($P, R$) and using it for planning/imagining.

  • Hierarchical RL: Decomposing tasks into sub-policies (options).

  • Meta-RL: Learning to learn—algorithms that adapt quickly to new tasks.

RL Applications in Data Science: Prediction of Preterm Birth

• Problem: Preterm birth (<37 weeks) is a major health challenge. Early prediction allows for intervention.

• RL Approach: Model the clinical decision process as an MDP.

  • States: Patient's health status (vital signs, medical history, test results).

  • Actions: Clinical interventions (medication, monitoring, discharge, etc.).

  • Rewards: + for healthy birth, - for complications, costs for interventions.

  • Goal: Learn a policy that recommends optimal, personalized intervention sequences to maximize maternal/fetal health outcomes over time.

5. Probabilistic and Statistical Learning

Probabilistic Modeling and Inference

• Probabilistic Modeling: Represents uncertainty explicitly using probability distributions. Models the joint distribution $P(X, Y)$ or conditional $P(Y|X)$.

  • Example: Naive Bayes Classifier. Assumes feature independence given class: $$\displaystyle P(Y|X_1,...,X_n) \propto P(Y) \prod_i P(X_i|Y) $$. Uses Bayes' theorem for prediction.

• Probabilistic Inference: The process of computing posterior probabilities given observed evidence.

  • Need in ML: Real-world data is noisy and incomplete. Inference allows reasoning under uncertainty, making predictions robust to missing data, and understanding model confidence.

  • Usage: In Bayesian networks, HMMs, topic models (LDA). Used for prediction, diagnosis, and decision-making.

Model Evaluation Metrics

• Precision and Recall (for Classification):

  • Built from Confusion Matrix (TP, TN, FP, FN).

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

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

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

  • Example: In disease prediction, high recall is critical (find all sick patients), even if precision is moderate. In spam detection, high precision is critical (don't mark good emails as spam).

• Methods for Evaluating Classifiers:

  • Holdout/Test Set Accuracy: Simple but can be high variance.

  • Cross-Validation (k-fold): More robust. Data split into $k$ folds; model trained $k$ times, each time on $k-1$ folds, tested on the held-out fold. Average performance.

  • Confusion Matrix & Derived Metrics: Precision, Recall, F1, Specificity.

  • ROC Curve & AUC: Plots TPR (Recall) vs FPR at different thresholds. AUC measures overall separability.

• Overfitting and Underfitting:

  • Overfitting: Model learns noise in training data. High training accuracy, low test accuracy. High variance. Cause: Model too complex (too many parameters).

  • Underfitting: Model fails to capture underlying pattern. Low training & test accuracy. High bias. Cause: Model too simple.

  • Bias-Variance Tradeoff: Increasing model complexity reduces bias but increases variance. Optimal complexity minimizes total error.

Validation Techniques: Holdout Method

• Detailed Process:

  1. Split Data: Randomly partition dataset into Training Set (e.g., 70%) and Test Set (e.g., 30%). Ensure stratification for classification.

  2. Train: Build the model only on the Training Set.

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

  4. Estimate Performance: The test set accuracy is the estimate of generalization error.

• Pros: Simple, fast, good for large datasets.

• Cons: High variance in estimate (depends on random split). Not suitable for small datasets (wastes data). No model selection—if you tune hyperparameters on the test set, you overfit to it.

• Best Practice: Use a three-way split: Train / Validation (for tuning) / Test (for final unbiased evaluation).

6. Data Engineering and Visualization for ML

Data Formats and I/O in Python

• CSV (Comma-Separated Values): Plain text, rows are records, columns are features.

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

• JSON (JavaScript Object Notation): Hierarchical, key-value pairs. Good for nested data.

  
  import json
  
  # Read
  
  with open('data.json', 'r') as f:
  
      data = json.load(f)  # Returns dict/list
  
  # Write
  
  with open('output.json', 'w') as f:
  
      json.dump(data, f, indent=4)
  
  

• JSON Parsing and String to JSON Array Conversion:

  
  import json
  
  json_string = '[{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]'
  
  # Parse string to Python list of dicts
  
  data_list = json.loads(json_string)
  
  # Convert Python object back to JSON string
  
  new_json_string = json.dumps(data_list, indent=2)
  
  

• Data Extraction Tools:

  • pandas: read_csv, read_json, read_sql, read_html.

  • Web Scraping: requests (fetch HTML) + BeautifulSoup (parse HTML).

Text Processing Libraries

• NLTK (Natural Language Toolkit): Comprehensive suite for tokenization, stemming, lemmatization, POS tagging, parsing. Good for education and research.

• spaCy: Industrial-strength, fast, pre-trained models for NLP pipelines (tokenization, POS, NER, dependency parsing). Optimized for production.

• BeautifulSoup: For parsing HTML/XML. Extracts data from web pages. Works with requests.

  
  from bs4 import BeautifulSoup
  
  import requests
  
  response = requests.get('https://example.com')
  
  soup = BeautifulSoup(response.content, 'html.parser')
  
  titles = soup.find_all('h1')  # Extract all h1 tags
  
  

Numerical Computing with NumPy

• Matrix Operations:

  
  import numpy as np
  
  A = np.array([[1, 2], [3, 4]])
  
  B = np.array([[5, 6], [7, 8]])
  
  # Matrix multiplication
  
  C = A.dot(B)  # or A @ B
  
  # Matrix inversion
  
  A_inv = np.linalg.inv(A)
  
  

• Statistical Measures:

  
  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

• Purpose: Create static, interactive, and animated visualizations in Python. Essential for Exploratory Data Analysis (EDA), understanding data distributions, relationships, and model performance.

• Applications: Histograms, scatter plots, line charts, bar charts, box plots, heatmaps.

• Example: Bar Chart

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

Data Product Strategy

• Steps for Building Strategy:

  1. Identify Business Problem & Value: Define the core objective and how ML will create value.

  2. Data Assessment: Inventory available data, identify gaps, plan collection/engineering.

  3. Model & Architecture Design: Choose appropriate ML approach, define data pipeline, infrastructure.

  4. Development & Iteration: Build, train, validate models. Iterate based on feedback.

  5. Deployment & Monitoring: Deploy to production (API, batch). Monitor performance, data drift, and business impact.

  6. Maintenance & Evolution: Retrain models, update features, scale as needed.

• Types of Data Products by Functionality:

  • Automation: Replacing manual processes (e.g., invoice processing, chatbots).

  • Insight Generation: Dashboards, reports, anomaly detection (e.g., sales forecasting, fraud alerts).

  • Recommendation: Personalized suggestions (e.g., Netflix, Amazon).

  • Prediction: Forecasting future outcomes (e.g., credit scoring, demand prediction).

  • Optimization: Finding best parameters under constraints (e.g., route optimization, pricing).

7. Applications of ML in Specialized Domains

ML in Graph Algorithms

• Graphs: Represent entities (nodes) and relationships (edges). Common in social networks, knowledge graphs, molecules.

• ML Applications:

  • Node Classification: Predict node labels (e.g., user category in social network). Uses Graph Neural Networks (GNNs) that aggregate neighbor information.

  • Link Prediction: Predict missing/ future edges (e.g., friend recommendation). Uses node embeddings (Node2Vec, DeepWalk).

  • Graph Classification: Classify entire graphs (e.g., molecule property prediction).

  • Community Detection: Finding clusters—can use ML to improve traditional algorithms.

ML for Map Searching

• Problem: Find optimal (shortest/fastest) path between locations.

• ML Enhancement:

  • Predicting Travel Time: ML models (e.g., Gradient Boosting) use historical traffic, weather, time-of-day to predict edge weights more accurately than static maps.

  • Personalized Routing: Incorporate user preferences (avoid tolls, scenic routes) learned from past behavior.

  • ETA Estimation: More accurate arrival time predictions.

  • Dynamic Routing: Reinforcement learning can learn routing policies in complex, changing environments (e.g., delivery logistics).

Stable Marriages Problem in Machine Learning

• Classic Problem: Match two sets (e.g., men/women) with preferences such that no pair prefers each other over their current partners (stable matching).

• ML Application: Matching Problems where entities have preferences and stability is desirable.

  • Examples:

    • Job Market: Matching medical residents to hospitals (NRMP uses Gale-Shapley algorithm).

    • School Choice: Matching students to schools.

    • Ride-Sharing: Matching drivers to riders (stability ensures no mutually beneficial swaps).

  • ML Angle: Learn preference rankings from data (e.g., from historical matches, surveys) instead of relying on stated preferences. Use ML to predict match quality/success.

Biomedical Informatics: Interconnectedness on Personal Genomes

• Concept: Human genomes are not just sequences of A,T,C,G. Genes interact (epistasis), regulatory elements are connected, and variants have context-dependent effects.

• ML for Interconnectedness:

  • Network-Based Models: Represent genes/proteins as nodes in a biological network (e.g., protein-protein interaction network). Use GNNs to predict disease associations or gene functions by leveraging network topology.

  • Multi-Omics Integration: Combine genomic, transcriptomic, epigenomic data. ML models (e.g., multi-view learning) capture interactions across these data layers.

  • Variant Effect Prediction: Predict pathogenicity of genetic variants by considering their position in 3D genome structure and regulatory networks.

Prediction of Preterm Birth (Revisited)

• ML Approach (General): Use clinical data (maternal age, history, biomarkers, ultrasound measurements) as features. Train classifiers (Random Forest, XGBoost, Neural Nets) to predict binary outcome (preterm vs term) or gestational age.

• RL Approach (from Unit 4): Formulate as sequential decision problem for clinical management.

8. Game Theory and AI for Games

Game Theory Fundamentals

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

• Application to AI: Provides formal framework for designing agents that interact with other agents (NPCs, humans, other AIs). Used for adversarial planning, multi-agent systems, and mechanism design.

• Solving Payoff Matrices & Equilibria:

  • Payoff Matrix: Represents outcomes (payoffs) for each combination of players' strategies.

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

  • Example (2x2):

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

    • Pure Strategy NE: Check each cell. (Right, Left) gives (1.7, 0.4). Goalie would switch to Right (0.4 > 0.6? No, 0.4<0.6). Kicker would switch to Left (1.5>1.7? No). No pure NE.

    • Mixed Strategy NE: Let Kicker play Left with prob $p$, Goalie play Left with prob $q$.

      • Kicker indifferent: $$\displaystyle 0.6p + 0.4(1-p) = 0.5p + 0.5(1-p) $$ → $$\displaystyle 0.6p+0.4-0.4p = 0.5 $$ → $$\displaystyle 0.2p = 0.1 $$ → $$\displaystyle p=0.5 $$.

      • Goalie indifferent: $$\displaystyle 1.4q + 1.7(1-q) = 1.5q + 1.5(1-q) $$ → $$\displaystyle 1.4q+1.7-1.7q = 1.5 $$ → $$\displaystyle -0.3q = -0.2 $$ → $$\displaystyle q=2/3 $$.

      • Equilibrium: Kicker: (L:0.5, R:0.5); Goalie: (L:2/3, R:1/3). Expected payoff to Kicker: $1.5$.

Search and Pathfinding

• Minimax Algorithm:

  • Purpose: For zero-sum, deterministic, perfect-information games (e.g., chess, tic-tac-toe). Assumes opponent plays optimally.

  • Functions:

    1. MAX node: AI's turn. Chooses move with maximum minimax value.

    2. MIN node: Opponent's turn. Assumes opponent chooses move with minimum minimax value (worst-case for AI).

    3. Terminal Node: Returns utility (win=+1, loss=-1, draw=0).

  • Process: Recursively explores game tree, propagating values up from leaves.

• Breadth-First Search (BFS) for Pathfinding:

  • Mechanism: 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.

  • Example: Maze solving. Start at S, explore all adjacent cells, then their neighbors, etc., until Goal is found.

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

• A Pathfinding Algorithm:*

  • Mechanism: Best-first search using 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). E.g., Manhattan distance, Euclidean distance.

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

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

  • Efficiency: More efficient than BFS by guiding search towards goal. Complexity depends on heuristic quality.

• Problem Complexity & Heuristic Limitations:

  • Curse of Dimensionality: Search space grows exponentially with problem size (e.g., chess has $$\displaystyle \sim 10^{120} $$ possible games).

  • Heuristic Limitations:

    • Inadmissible Heuristic: Overestimates cost → may miss optimal path.

    • Weak Heuristic: Close to zero → A* degrades to BFS (slow).

    • Computing Heuristic: Heuristic itself must be cheap to compute; otherwise overhead negates benefit.

AI Architecture for Games

• Rule-Based Systems:

  • Definition: Systems where behavior is defined by explicit "if-then" rules created by designers.

  • Example: IF (player_in_sight AND health > 50) THEN attack ELSE take_cover.

  • Pros: Transparent, predictable, easy to design/test.

  • Cons: Brittle, hard to scale to complex behaviors, not adaptive.

• Model of Game AI: Typically a sense-plan-act loop:

  1. Sense: Gather information (player position, health, environment).

  2. Plan/Decide: Choose action based on AI model (rules, behavior tree, utility system).

  3. Act: Execute animation/movement.

• Finite State Machines (FSM) vs Behavior Trees (BT):

  | Feature | Finite State Machine (FSM) | Behavior Tree (BT) | | :--- | :--- | :--- | | Structure | States connected by transitions. One active state at a time. | Hierarchical tree of nodes (tasks/composites). | | Control Flow | Implicit in transitions. Can lead to spaghetti code with many states. | Explicit via node types (Sequence, Selector, Parallel). More modular. | | Flexibility | Low. Adding new behavior often requires modifying existing states/transitions. | High. New behaviors are new subtrees; easy to reuse and combine. | | Debugging | Hard. State transitions can be non-obvious. | Easier. Tree structure shows execution path clearly. | | Example | Guard AI: States: Patrol, Chase, Attack, Flee. Transitions triggered by events. | Guard AI: Root Selector: [SeePlayer? -> ChaseTask, PatrolTask]. ChaseTask is a Sequence: [MoveToPlayer, AttackIfInRange]. |

• Constructing Finite State Machines: Guard/Thief Scenario

  • States: StandGuard, Fight, Flee, Escape.

  • Transitions:

    • StandGuard --(see thief)--> Fight

    • Fight --(thief strong)--> Flee

    • Fight --(win)--> StandGuard

    • Flee --(safe)--> Escape

    • Escape --(timeout)--> StandGuard

  • Diagram: Circular flow between StandGuard and Fight, with Flee as a branch from Fight leading to Escape, which returns to StandGuard.

Movement and Representation

• Static vs Kinematic Representation in 3D:

  • Static Representation: Describes position and orientation only. No velocity/acceleration. Used for keyframes in animation, initial placements.

  • Kinematic Representation: Describes position, orientation, velocity, and acceleration. Used for physics-based movement, steering behaviors. Allows smooth interpolation and force application.

• Components of Coordinated Movement:

  1. Pathfinding: High-level route (A* on navigation mesh).

  2. Steering: Low-level, real-time adjustment of velocity/orientation to follow path, avoid obstacles, align to target (e.g., Craig Reynolds' steering behaviors: seek, flee, arrive, obstacle avoidance).

  3. Animation: Playing appropriate locomotion animations (walk, run, turn) based on movement parameters (speed, direction). Often uses blending.

  4. Motion Matching (Advanced): Selects the best animation clip from a database that matches current trajectory, reducing "foot-sliding".

Movement Algorithm Structure

• Components:

  1. Perception: Sensing environment (raycasts, triggers, navmesh queries).

  2. Decision: High-level goal selection (from BT/FSM/utility system).

  3. Path Planning: Compute path to target (A*, Dijkstra).

  4. Steering: Generate desired velocity/acceleration to follow path, avoid local obstacles, maintain social distance (ORCA).

  5. Animation Control: Map desired velocity to animation parameters (speed, direction) and select/blend clips.

  6. Physics Integration: Apply steering forces to rigidbody/collider.

Stages of Motor Learning in Game AI

1. Cognitive Stage: AI "understands" the task. Uses explicit rules or simple heuristics. Performance is slow, inconsistent, error-prone.

2. Associative Stage: AI refines its model through practice/experience. Patterns are recognized, movements become smoother, errors decrease. May use reinforcement learning to tune parameters.

3. Autonomous Stage: Skill becomes automatic, fast, and robust. Requires minimal computational resources. Can be represented by a highly optimized policy or a compact neural network.

Advanced Game AI Techniques: Fuzzy Time Series & Markov Chain (Modified Frequency Partitioning)

• Flowchart Explanation:

  1. Input: Historical sequence of game states/actions (e.g., player positions over time).

  2. Fuzzification: Partition the state/action space into fuzzy sets (e.g., "near", "medium", "far" for distance) using modified frequency partitioning (determine membership functions based on data distribution, not arbitrary).

  3. Fuzzy Time Series Generation: Convert crisp historical data into sequences of fuzzy linguistic labels.

  4. Markov Chain Modeling: Treat fuzzy label sequences as states in a first-order Markov chain. Compute transition matrix $$\displaystyle P_{ij} $$ = probability of moving from fuzzy state $i$ to $j$.

  5. Prediction/Decision: Given current fuzzy state, use transition matrix to predict next likely fuzzy state(s). Defuzzify to get crisp prediction or choose action associated with predicted state.

  6. Output: Predicted next state or recommended action (e.g., "player likely to move to 'medium' distance → choose 'intercept' action").

  • Advantage: Handles uncertainty in human behavior modeling better than crisp Markov models. Modified frequency partitioning adapts to actual data distribution.