Predictive Analytics (AL-702 (C)) - Unit 5 Short Notes

UNIT 5: PREDICTIVE ANALYTICS - EXAM-FOCUSED SHORT NOTES

I. FOUNDATIONAL MACHINE LEARNING MODELS

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

• Architecture: Composed of an input layer (features), one or more hidden layers (computational neurons), and an output layer (predictions). Each neuron applies: z = W·X + b (weighted sum + bias), followed by an activation function (e.g., Sigmoid, ReLU) to introduce non-linearity.

• Learning Process:

  1. Forward Propagation: Input data flows through layers to compute output/prediction.

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

  3. Backpropagation: Compute gradient of loss w.r.t. each weight using the chain rule, propagating error backward.

  4. Weight Update: Adjust weights using an optimizer (e.g., Gradient Descent): W_new = W_old - η * ∇L.

• vs. Single-Layer Perceptron: MLP with hidden layers can learn non-linear decision boundaries (via activation functions), while a single-layer perceptron is limited to linearly separable problems.

[!TIP] Exam Focus: Be prepared to draw the MLP architecture and trace one forward/backward pass with a small example. Key differentiator: non-linearity from hidden layers.

B. Decision Trees

• Core Concepts:

  • Recursive Induction: Top-down, greedy algorithm. At each node, select the attribute that best splits the data into purer child nodes.

  • Splitting Criteria:

    • Entropy (measure of impurity): H(S) = -∑ p_i log₂(p_i).

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

    IG(S, A) = H(S) - ∑ (|S_v|/|S|) * H(S_v)

    where S_v are subsets after split.

  • Handling Attributes: Categorical → split by subset. Numerical → find threshold that maximizes IG.

• Performance & Robustness:

  • Impact of Noisy Data: Leads to overfitting—tree becomes overly complex, capturing noise instead of signal.

  • Strategies to Overcome Noise:

    1. Pruning: Remove branches with low predictive power.

       • Pre-pruning: Stop growth early (e.g., min samples per leaf, max depth).

       • Post-pruning: Grow full tree, then remove branches (e.g., reduced error pruning).

    2. Ensemble Methods: Use Random Forest (see II.B.1) to average many trees, reducing variance.

• Application in Game Development: Used for AI decision-making (e.g., NPC behavior selection), where attributes are game state features (health, distance to player) and leaf nodes are actions (attack, flee).

[!TIP] Common Pitfall: Confusing Entropy and Gini Index calculations. Practice a full IG calculation for a small dataset (like the credit score example from Paper B).

II. ENSEMBLE LEARNING METHODS (HIGH FREQUENCY)

A. Fundamental Concepts

• Why Ensembles? Combine multiple weak learners to create a strong learner. Primary benefit: Variance Reduction (for unstable models like trees) and improved bias-variance tradeoff. Diversity among base models is key.

• Bagging vs. Boosting:

B. Specific Algorithms

• 1. Random Forest (Very High Frequency)

  • Working Mechanism:

    1. Bootstrap Aggregating (Bagging): Create N bootstrap samples from training data.

    2. Feature Randomness: At each split in a tree, consider only a random subset of m features (m ≈ √p for classification).

    3. Tree Construction: Grow a full decision tree on each bootstrap sample using random feature subset at splits (no pruning).

    4. Aggregation: For classification, majority vote; for regression, average of all tree predictions.

  • Advantages:

    • Robust to overfitting.

    • Handles high-dimensional data well.

    • Provides feature importance scores (mean decrease in impurity/Gini).

    • Handles missing values and outliers reasonably well.

[!TIP] Key Distinction: In Random Forest, both data (bootstrap) and features (random subset at splits) are randomized. This is what creates diversity and reduces correlation between trees.

• 2. Boosting Family (Conceptual)

  • Principle: Sequentially train models where each new model focuses on correcting errors made by previous ones.

  • AdaBoost: Increases weights of misclassified instances. Final prediction is weighted majority vote.

  • Gradient Boosting: Fits each new learner to the negative gradient of the loss function (i.e., the residual errors) of the previous ensemble. More general and powerful.

III. REINFORCEMENT LEARNING (RL) (VERY HIGH FREQUENCY)

A. Core Framework & Equations

• Markov Decision Process (MDP): Formalization of RL problem.

  • S: Set of states.

  • A: Set of actions.

  • P(s'|s, a): Transition probability to state s' from s taking action a.

  • R(s, a, s'): Immediate reward received.

  • γ (Discount Factor): 0 ≤ γ ≤ 1. Weights immediate vs. future rewards.

• Value Functions:

  • State-Value Function V_π(s): Expected return starting from state s and following policy π.

  • Action-Value Function Q_π(s, a): Expected return starting from state s, taking action a, then following π.

• Bellman Equations (Recursive definitions of value functions):

  • Expectation Equation:

$$V_π(s) = \sum_a π(a|s) \sum_{s',r} P(s',r|s,a) [r + γ V_π(s')]$$

$$Q_π(s,a) = \sum_{s',r} P(s',r|s,a) [r + γ \sum_{a'} π(a'|s') Q_π(s',a')]$$

*   **Optimality Equation** (Defines optimal value functions `V*` and `Q*`):

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

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

[!TIP] Boxed Core Concept: The Bellman Optimality Equation is the heart of RL. It expresses that the optimal value is the maximum over actions of the immediate reward plus discounted optimal future value.

B. Algorithm Categories

• 1. Dynamic Programming (DP) Methods: Assume full knowledge of MDP (model-based).

  • Policy Iteration:

    1. Policy Evaluation: Compute V_π for current policy π (solve linear system).

    2. Policy Improvement: Make policy greedy w.r.t. V_π: π'(s) = argmax_a ∑_{s'} P(s'|s,a)[R(s,a,s') + γ V_π(s')].

    3. Repeat until policy stable.

  • Value Iteration: Directly apply Bellman optimality update until convergence:

    V_{k+1}(s) = max_a ∑_{s'} P(s'|s,a)[R(s,a,s') + γ V_k(s')]. No explicit policy representation until end.

• 2. Temporal Difference (TD) Learning: Model-free, learns from bootstrapping (updating estimates based on other estimates) from incomplete episodes.

  • Key Difference from Monte Carlo (MC):

    • TD: Updates after each step using R + γ V(S'). Lower variance, converges faster, can learn online.

    • MC: Updates only at episode end using full return G_t. Unbiased, but higher variance, requires episodic tasks.

  • TD(0) Update: V(S_t) ← V(S_t) + α [R_{t+1} + γ V(S_{t+1}) - V(S_t)].

• 3. SARSA vs. Q-Learning (TD Control - learn optimal policy):

  • SARSA: On-policy. Learns Q_π for the current behavior policy (often ε-greedy). Update uses action actually taken: Q(S_t, A_t) ← Q(S_t, A_t) + α [R + γ Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)].

  • Q-Learning: Off-policy. Learns Q* independently of behavior policy. Update uses max action at next state: Q(S_t, A_t) ← Q(S_t, A_t) + α [R + γ max_a Q(S_{t+1}, a) - Q(S_t, A_t)].

  • Key Difference: SARSA learns the value of the policy it follows (more conservative, considers exploration). Q-Learning learns the optimal policy (can be more aggressive, may overestimate if combined with function approximation).

• 4. Policy Gradient Methods: Directly parameterize policy π_θ(a|s) and optimize objective J(θ) = E_π[∑ R] using gradient ascent.

  • REINFORCE: Monte Carlo policy gradient. Update: θ ← θ + α G_t ∇ log π_θ(A_t|S_t).

C. Advanced & Recent Trends

• Generative Adversarial Imitation Learning (GAIL):

  • Difference from Standard RL: Standard RL learns from a hand-designed reward function. GAIL learns a policy by imitating expert demonstrations, without explicit reward. Uses adversarial training (like GANs) where a discriminator tries to distinguish expert vs. agent trajectories, and the agent tries to fool it.

• Recent Trends in RL Architectures:

  • Deep RL: Using deep neural networks as function approximators (e.g., DQN, PPO, SAC).

  • Model-based vs. Model-free: Model-based learns a dynamics model P(s'|s,a) and plans; model-free learns value/policy directly.

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

  • Multi-agent RL: Multiple agents learning/acting in shared environment (cooperative/competitive).

IV. GAME THEORY & AI FOR GAMES

A. Game Theory Fundamentals

• Definition & Application: Study of strategic decision-making in multi-agent systems. In AI, used for opponent modeling, Nash equilibrium computation, and designing robust agents.

• Payoff Matrices:

  • Solving for Equilibrium:

    • Pure Strategy: Single best response for each player (saddle point). Use minimax (maximin for row player).

    • Mixed Strategy: Probability distribution over actions. Find probabilities p where opponent is indifferent.

  • Example (2x2 Penalty Kick):

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

    • Kicker wants to maximize, Goalie to minimize Kicker's payoff.

    • Kicker's mixed strategy p(Left) makes Goaly indifferent:

      1.4*p + 1.7*(1-p) = 1.5*p + 1.5*(1-p) → p = 0.4.

    • Goaly's mixed strategy q(Left) makes Kicker indifferent:

      1.4*q + 1.5*(1-q) = 1.5*q + 1.5*(1-q) → q = 0.5.

    • Nash Equilibrium: (Kicker: 0.4 Left, 0.6 Right), (Goalie: 0.5 Left, 0.5 Right).

B. Search & Pathfinding Algorithms

• 1. Minimax Algorithm (for zero-sum, perfect info games):

  • Mechanism: Explores game tree to terminal states. Max nodes (AI) choose move maximizing score; Min nodes (opponent) choose move minimizing AI's score.

  • Functions:

    • Terminal-Test(state): Checks if game over.

    • Utility(state): Returns numeric outcome (win=+1, loss=-1, draw=0).

    • Min-Max-Decision(state): Returns action leading to max of min values.

  • Limitation: Exponential complexity. Use alpha-beta pruning to cut branches.

• 2. A Search Algorithm* (for pathfinding):

  • Mechanism: Best-first search using 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).

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

• 3. Breadth-First Search (BFS):

  • Algorithm: Explore all neighbors at current depth before moving deeper. Uses queue (FIFO).

  • Properties: Complete (finds solution if exists), optimal for unweighted graphs, but high memory/time complexity.

C. AI Architecture for Games

• Model of Game AI (Sense-Think-Act Cycle):

  1. Sense: Perceive game world (player position, health).

  2. Think: Process information, make decisions (via FSMs, Behavior Trees, GOAP).

  3. Act: Execute chosen action (animation, movement).

• Behavior Trees vs. Finite State Machines (FSMs):

• Constructing a Simple FSM (Guard/Thief):

  • States: Guard, Chase, Fight, Flee.

  • Transitions:

    • Guard → Chase if sees_thief.

    • Chase → Fight if close_enough.

    • Fight → Flee if losing_fight.

    • Flee → Guard if safe.

• Components of Coordinated Movement:

  • Kinematic Representation: Position (x,y), orientation θ, velocity v, rotation ω.

  • Steering Behaviors: Forces applied to achieve motion (e.g., Seek, Flee, Arrive, Pursue, Evade, Wander). Computed via steering_force = desired_velocity - current_velocity.

V. PYTHON FOR DATA SCIENCE & PREDICTIVE ANALYTICS

A. Data Handling & I/O

• CSV & JSON Files:

  • CSV: pandas.read_csv('file.csv'), df.to_csv('file.csv').

  • JSON: json.load(open('file.json')) for dict, pandas.read_json('file.json') for DataFrame.

• Data Extraction Tools:

  • Web Scraping: requests (get HTML), BeautifulSoup (parse HTML/XML).

  • APIs: requests to call endpoints, handle JSON responses.

  • Databases: sqlite3, SQLAlchemy, pandas.read_sql().

• Text Processing Libraries:

  • nltk: Comprehensive NLP toolkit (tokenization, stemming, POS tagging).

  • spaCy: Industrial-strength, fast NLP (pre-trained models, entity recognition).

  • re: Regular expressions for pattern matching.

B. Numerical Computation & Linear Algebra (NumPy)

• NumPy:

  • Array creation: np.array(), np.zeros(), np.arange().

  • Operations: Element-wise +,-,*,/, broadcasting.

  • Statistics: np.mean(), np.var(), np.std().

  • Linear Algebra: np.dot(), np.linalg.inv() (matrix inverse), np.linalg.solve().

• Least Squares Methods:

  • Concept: Find coefficients β that minimize sum of squared residuals ∑(y_i - X_iβ)².

  • Normal Equation: β = (XᵀX)⁻¹Xᵀy.

  • Implementation:

    
    beta = np.linalg.inv(X.T @ X) @ X.T @ y
    
    # or
    
    beta = np.linalg.lstsq(X, y, rcond=None)[0]
    
    

C. Machine Learning Implementation

• Linear Regression with Gradient Descent:

  1. Hypothesis: h_θ(x) = θ₀ + θ₁x₁ + ... + θₙxₙ.

  2. Cost Function (MSE): J(θ) = (1/(2m)) ∑ (h_θ(xⁱ) - yⁱ)².

  3. Gradient Descent Steps:

     • Initialize θ (e.g., zeros).

     • Repeat until convergence:

     θ_j := θ_j - α * (1/m) ∑ (h_θ(xⁱ) - yⁱ) x_jⁱ (for all j).

• Mini-Batch Gradient Descent:

  • Concept: Update parameters using a small random subset (mini-batch) of training data per iteration.

  • Advantages:

    • Computational Efficiency: Vectorized operations on mini-batches faster than single example (SGD) or full dataset (Batch GD).

    • Convergence Stability: Less noisy than SGD, often converges faster than Batch GD.

    • Memory Friendly: Fits large datasets in memory in chunks.

D. Data Visualization (Matplotlib)

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

• Basic Plotting:

  
  import matplotlib.pyplot as plt
  
  plt.bar(subjects, marks)  # Bar chart
  
  plt.plot(x, y)            # Line plot
  
  plt.scatter(x, y)         # Scatter plot
  
  

• Customization: plt.xlabel(), plt.ylabel(), plt.title(), plt.legend().

E. Model Evaluation

• Classification Metrics:

  • Precision = TP / (TP + FP). Of those predicted positive, how many are correct?

  • Recall = TP / (TP + FN). Of all actual positives, how many were found?

  • Trade-off: Increasing precision often reduces recall (and vice versa). Visualized with Precision-Recall curve.

  • F1-Score = 2 * (Precision * Recall) / (Precision + Recall). Harmonic mean.

• General Classifier Evaluation:

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

  • Accuracy: (TP+TN)/Total. Misleading with imbalanced data.

  • ROC-AUC: Area under Receiver Operating Characteristic curve (trade-off TPR vs FPR).

  • Cross-Validation (k-fold): Split data into k folds, train on k-1, test on 1, repeat k times. Reduces variance of performance estimate.

[!TIP] Exam Focus: Be ready to compute Precision, Recall, F1 from a given confusion matrix. Know when to use Accuracy vs. F1 vs. ROC-AUC.

VI. ALGORITHMIC FOUNDATIONS & ANALYSIS

A. Algorithm Design Paradigms

• 1. Divide and Conquer:

  • Steps:

    1. Divide: Break problem into smaller subproblems.

    2. Conquer: Solve subproblems recursively.

    3. Combine: Merge subproblem solutions.

  • Example: Merge Sort (divide array, sort halves, merge). In ML: Used in decision tree construction (CART) for finding best split by sorting data on feature values.

• 2. Dynamic Programming (DP):

  • Principle: Solve overlapping subproblems once, store solutions (memoization/tabulation). Requires optimal substructure.

  • Example in ML: Value Iteration in RL (Bellman update is a DP step). Sequence alignment in bioinformatics.

B. Learning Problem Formulation

• "Well-Posed Learning" Problem (Tom Mitchell): A learning task is well-posed if:

  1. Task (T): What is to be done? (e.g., classify email as spam).

  2. Performance Measure (P): How to evaluate success? (e.g., accuracy, F1-score).

  3. Experience (E): Source of training data? (e.g., labeled emails).

  • Example: Spam filter: T=classify email, P=minimize false positives, E=user-labeled inbox.

• Lazy vs. Eager Learning:

C. Probabilistic Modeling & Inference

• Probabilistic Modelling in ML: Treat unknowns as random variables with probability distributions. Models uncertainty explicitly.

  • Example: Naive Bayes Classifier: P(Class|Features) ∝ P(Class) * ∏ P(Feature_i|Class). Uses Bayes' theorem.

• Need for Probabilistic Inference: Compute posterior probabilities given observed evidence (features). Essential for:

  • Diagnosis: P(Disease|Symptoms).

  • Prediction under uncertainty: P(Next state|Current state, Action) in POMDPs.

  • Decision making: Choose action that maximizes expected utility.

D. Evaluation & Validation

• Holdout Method:

  • Procedure: Randomly split data into Training set (e.g., 70%), Validation set (e.g., 15% for tuning), Test set (e.g., 15% for final evaluation).

  • Advantages: Simple, fast.

  • Limitations: Performance estimate has high variance (depends on split). Poor for small datasets (less data for training).

E. Application-Specific ML Discussions (Brief Definitions)

• ML in Graphs, Maps & Map Searching: Shortest path algorithms (Dijkstra, A*), recommendation systems on graph data (user-item bipartite graphs), traffic prediction using GNNs.

• Stable Marriage Algorithms in ML: Used for matching problems: matching learners to tasks, resources to users