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

I. Foundations of Machine Learning and Algorithmic Analysis

Algorithm Design and Characteristics

An algorithm must have:

• Well-defined input

• Well-defined output

• Definiteness (each step precise)

• Finiteness (terminates in finite steps)

• Effectiveness (each step executable)

Tools for Algorithm Analysis

• Time Complexity: Measured using Big O notation; estimates growth rate as input size increases.

• Space Complexity: Memory required during execution.

• Correctness Proof: Logical verification that algorithm produces desired output for all valid inputs.

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

[!TIP]

Common Pitfall: Confusing time complexity with actual runtime; complexity is asymptotic, not absolute.

Well-Posed Learning Problems

A problem is well-posed if:

1. Task (T) is clearly defined (e.g., classification, regression).

2. Performance Measure (P) is quantifiable (e.g., accuracy, MSE).

3. Experience (E) is available for learning (e.g., training data).
   Example: Spam filtering—Task: classify emails as spam/ham; P: accuracy; E: labeled email dataset.

Divide and Conquer in ML

• Break problem into smaller subproblems.

• Solve subproblems recursively.

• Combine solutions.
  Example: Decision tree induction (ID3/C4.5) splits dataset on attributes, recurses on subsets.

Dynamic Programming in ML

Used when problem has optimal substructure and overlapping subproblems.
Example: Viterbi algorithm for Hidden Markov Models (HMMs) finds most likely hidden state sequence.

Lazy vs Eager Learning

II. Data Preparation, Evaluation, and Model Assessment

Data Preparation Steps

1. Extraction: Collect data from sources (databases, APIs, web scraping).

2. Description: Summarize statistics (mean, variance, distributions).

3. Cleaning: Handle missing values, outliers, errors.

4. Transformation: Normalization, standardization, encoding categorical variables.

5. Reduction: Dimensionality reduction (PCA), feature selection.

Holdout and Cross-Validation

• Holdout Method: Split data into training set and test set (e.g., 70%/30%). Simple but may be unstable with small data.

• k-Fold Cross-Validation:

  • Split data into k equal folds.

  • Train on k-1 folds, test on remaining fold; repeat k times.

  • Average performance across folds.

• Stratified k-Fold: Preserves class distribution in each fold (important for imbalanced datasets).

Evaluation Metrics for Classifiers

Given Confusion Matrix:

• Accuracy: $$\displaystyle \frac{TP + TN}{TP + TN + FP + FN} $$

• Precision: $$\displaystyle \frac{TP}{TP + FP} $$ (exactness of positive predictions)

• Recall (Sensitivity): $$\displaystyle \frac{TP}{TP + FN} $$ (coverage of actual positives)

• F1-Score: $$\displaystyle 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} $$ (harmonic mean)

• ROC-AUC: Area under ROC curve; measures trade-off between TPR (Recall) and FPR ($$\displaystyle \frac{FP}{FP+TN} $$).

[!EXAMPLE]

Spam Detection: High precision means few non-spam emails marked as spam (important for user experience). High recall means most spam emails caught (important for security).

Overfitting and Underfitting

III. Core Predictive Models

A. Decision Trees

Entropy and Information Gain

• Entropy (impurity measure for set S):

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

where $$\displaystyle p_i $$ = proportion of class i in S, c = number of classes.

• Information Gain (reduction in entropy after splitting on attribute A):

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

[!CALCULATION]

Given dataset:

| Sample | Credit Score | Loan Approved |

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

| 1 | High | Yes |

| 2 | Medium | No |

| 3 | Low | No |

| 4 | High | Yes |

| 5 | Medium | Yes |

| 6 | Low | No |

| 7 | High | No |

Overall Entropy:

• Yes: 3/7, No: 4/7 → $$\displaystyle H(S) = -\frac{3}{7}\log_2\frac{3}{7} - \frac{4}{7}\log_2\frac{4}{7} \approx 0.985 $$

Information Gain for Credit Score:

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

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

• Low (2 samples: 0 Yes, 2 No): $$\displaystyle H(\text{Low}) = 0 $$

• Weighted avg: $$\displaystyle \frac{3}{7} \times 0.918 + \frac{2}{7} \times 1.0 + \frac{2}{7} \times 0 \approx 0.684 $$

• $$\displaystyle IG = 0.985 - 0.684 = 0.301 $$

Recursive Induction (Splitting Process)

1. Start with entire dataset at root.

2. For each attribute, compute information gain (or Gini impurity).

3. Select attribute with highest gain as splitting node.

4. Create branches for each attribute value.

5. Recurse on each branch with subset of data until:

   • All samples in a node belong to same class.

   • No remaining attributes.

   • Minimum samples per node reached.

Handling Noisy Data

• Pruning: Remove branches that fit noise (post-pruning after tree built, or pre-pruning during construction).

• Smoothing: Assign probabilities instead of hard class labels (e.g., Laplace correction).

• Ensemble Methods: Use Random Forests or boosting to reduce variance.

• Set Minimum Samples: Require minimum samples per leaf to avoid overfitting to small noisy subsets.

Decision Trees in Game Development

• NPC Behavior: Tree of conditions (e.g., health, ammo, enemy distance) → actions (attack, flee, reload).

• Dialogue Systems: Branching conversations based on player choices.

• Adaptive Difficulty: Adjust game parameters based on player performance metrics.

B. Ensemble Methods

Bagging vs Boosting

Random Forest Architecture

1. Bootstrap Aggregation (Bagging):

   • For each tree, sample N instances with replacement from training set (same size N).

2. Feature Randomness:

   • At each split, consider only random subset of m features (typically $$\displaystyle m = \sqrt{p} $$ for classification, $p/3$ for regression, where p = total features).

3. Tree Construction:

   • Grow each tree fully (no pruning) using best split from random feature subset.

4. Prediction:

   • Classification: Majority vote across trees.

   • Regression: Average output.

Why Ensembles Offer Greater Robustness

• Bias-Variance Trade-off:

  • Single high-variance model (e.g., deep tree) → bagging reduces variance.

  • Single high-bias model (e.g., shallow tree) → boosting reduces bias.

• Diversity: Models make different errors; averaging cancels out individual mistakes.

• Stability: Less sensitive to noise, outliers, and specific hyperparameters.

C. Neural Networks

Multi-Layer Perceptron (MLP) Architecture

• Layers:

  • Input Layer: One neuron per feature.

  • Hidden Layer(s): One or more; apply non-linear activation.

  • Output Layer: Number of neurons = number of classes (softmax for classification) or 1 (regression).

• Connectivity: Fully connected (dense) between consecutive layers.

• Activation Functions:

  • Sigmoid: $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$ (output 0–1, suffers vanishing gradient).

  • ReLU: $$\displaystyle \text{ReLU}(z) = \max(0, z) $$ (faster convergence, sparse activations).

  • Tanh: $\tanh(z)$ (output –1 to 1, zero-centered).

Learning Process

1. Forward Propagation:

   • Compute $$\displaystyle z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)} $$ for layer l.

   • Apply activation: $$\displaystyle a^{(l)} = g(z^{(l)}) $$.

   • Final output: $$\displaystyle \hat{y} = a^{(L)} $$ (output layer).

2. Loss Calculation:

   • Cross-entropy for classification: $$\displaystyle J = -\frac{1}{m} \sum_{i=1}^m y_i \log(\hat{y}_i) $$.

   • MSE for regression: $$\displaystyle J = \frac{1}{2m} \sum_{i=1}^m (\hat{y}_i - y_i)^2 $$.

3. Backpropagation:

   • Compute gradient of loss w.r.t. weights using chain rule.

   • Output layer error: $$\displaystyle \delta^{(L)} = \nabla_a J \odot g'(z^{(L)}) $$.

   • Hidden layer error: $$\displaystyle \delta^{(l)} = (W^{(l+1)})^T \delta^{(l+1)} \odot g'(z^{(l)}) $$.

4. Weight Updates (Gradient Descent):

$$W^{(l)} := W^{(l)} - \alpha \frac{\partial J}{\partial W^{(l)}}$$

where $\alpha$ = learning rate.

Gradient Descent Delta Rule (Single-Layer Perceptron)

• For linear unit with squared error:

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

where $t$ = target, $y$ = output, $$\displaystyle x_i $$ = input feature.

• For logistic unit with cross-entropy:

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

(same form due to derivative properties).

D. Regression and Optimization

Linear Regression: Least Squares Method

• Model: $$\displaystyle y = X\beta + \epsilon $$, where $X$ = design matrix (with bias column), $\beta$ = coefficient vector.

• Objective: Minimize sum of squared residuals (RSS):

$$RSS(\beta) = \sum_{i=1}^m (y_i - x_i^T \beta)^2 = (y - X\beta)^T (y - X\beta)$$

• Closed-Form Solution:

$$\hat{\beta} = (X^T X)^{-1} X^T y$$

Assumptions: $$\displaystyle X^T X $$ invertible (no perfect multicollinearity).

Gradient Descent Approach

• Cost Function: $$\displaystyle J(\beta) = \frac{1}{2m} RSS(\beta) $$.

• Gradient: $$\displaystyle \nabla J(\beta) = -\frac{1}{m} X^T (y - X\beta) $$.

• Update Rule:

$$\beta := \beta - \alpha \nabla J(\beta) = \beta + \frac{\alpha}{m} X^T (y - X\beta)$$

• Iterate until convergence (gradient near zero or max iterations).

Gradient Descent Variants

Implementing Gradient Descent in TensorFlow

1. Import: import tensorflow as tf

2. Placeholders: X = tf.placeholder(tf.float32, [None, n_features]), y = tf.placeholder(tf.float32, [None, 1])

3. Variables: W = tf.Variable(tf.random_normal([n_features, 1])), b = tf.Variable(tf.random_normal([1]))

4. Model: y_pred = tf.matmul(X, W) + b

5. Loss: loss = tf.reduce_mean(tf.square(y_pred - y))

6. Optimizer: optimizer = tf.train.GradientDescentOptimizer(learning_rate=alpha).minimize(loss)

7. Session: Initialize variables, run sess.run(optimizer, feed_dict={X: X_batch, y: y_batch}) in loop.

Least Squares Methods (General Overview)

• Used for curve fitting, parameter estimation.

• Extensions:

  • Ridge Regression: Adds L2 penalty $$\displaystyle \lambda \|\beta\|^2 $$ to handle multicollinearity.

  • Lasso: Adds L1 penalty $$\displaystyle \lambda \|\beta\|_1 $$ for feature selection.

• Applications: Linear regression, polynomial regression, signal processing.

IV. Reinforcement Learning

Bellman Equations

• Value Function (expected cumulative discounted reward from state s under policy $\pi$):

$$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t = s \right]$$

Bellman Expectation Equation:

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

• Optimal Value Function $$\displaystyle V^*(s) $$:

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

• Action-Value Function $$\displaystyle Q^\pi(s,a) $$:

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

Temporal Difference (TD) Learning vs Monte Carlo

Q-learning vs SARSA

• Q-learning (Off-policy):

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]$$

Learns optimal policy independent of behavior policy.

• SARSA (On-policy):

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q(s',a') - Q(s,a) \right]$$

where $a'$ is action actually taken in $s'$; learns policy being followed.

• Key Difference: Q-learning uses $$\displaystyle \max_{a'} Q(s',a') $$ (greedy), SARSA uses next action from current policy (may be exploratory).

Value Iteration and Policy Iteration

• Value Iteration:

  1. Initialize $V(s)$ arbitrarily.

  2. Repeat until convergence:

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

3. Derive greedy policy: $$\displaystyle \pi(s) = \arg\max_a \sum_{s',r} P(s',r|s,a) \left[ r + \gamma V(s') \right] $$.

• Policy Iteration:

  1. Initialize policy $\pi$.

  2. Policy Evaluation: Compute $$\displaystyle V^\pi $$ by solving linear system or iterating:

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

3. Policy Improvement:

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

4. If $$\displaystyle \pi' = \pi $$, stop; else $$\displaystyle \pi \leftarrow \pi' $$ and repeat.

• Comparison: Value iteration simpler (no policy evaluation step), but policy iteration often faster per iteration.

Policy Gradient Methods

• Directly optimize policy parameterized by $\theta$ (e.g., neural network).

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

• REINFORCE Algorithm (Monte Carlo policy gradient):

$$\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta) \approx \alpha \sum_t \nabla_\theta \log \pi_\theta(a_t|s_t) G_t$$

where $$\displaystyle G_t $$ = return from time t.

• Advantages: Handles continuous actions, stochastic policies.

• Challenges: High variance, slow convergence.

Recent Trends in RL Architectures

• Deep RL: Combining deep learning with RL (e.g., DQN, A3C, PPO).

• Model-Based RL: Learn environment model, plan using it (e.g., Dreamer, MuZero).

• Hierarchical RL: Decompose tasks into subtasks (options, feudal networks).

• Multi-Agent RL: Independent learners, cooperative/competitive settings.

• Meta-RL: Learn to adapt quickly to new tasks.

Generative Adversarial Imitation Learning (GAIL) vs Standard RL

• Standard RL: Agent learns from reward signal provided by environment.

• GAIL:

  • Learns policy from expert demonstrations (no reward).

  • Uses adversarial training: discriminator distinguishes expert vs agent trajectories; policy trained to fool discriminator.

  • Objective: Minimize distance between expert and agent state-action distributions.

• Key Difference: GAIL is inverse RL + GANs; avoids reward engineering.

V. Game Theory and AI for Games

Game Theory Definition and Applications

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

• Applications in AI:

  • Multi-agent systems (cooperative/competitive).

  • Auction design, mechanism design.

  • Negotiation, conflict resolution.

  • Game AI (NPC decision-making, balancing).

Minimax Algorithm

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

• Utility Function: Evaluates terminal states (win/loss/draw).

• Recursion:

$$\text{minimax}(s) = \begin{cases} \text{utility}(s) & \text{if terminal} \\ \max_{a} \min_{a'} \text{minimax}(s') & \text{if max player} \\ \min_{a} \max_{a'} \text{minimax}(s') & \text{if min player} \end{cases}$$

• Alpha-Beta Pruning: Optimizes by pruning branches that cannot affect final decision.

Solving Payoff Matrices and Nash Equilibria

• Payoff Matrix: Rows = Player A strategies, Columns = Player B strategies; entries = (payoff_A, payoff_B).

• Nash Equilibrium: Strategy profile where no player can improve payoff by unilaterally deviating.

• Mixed Strategies: Players randomize over actions with probabilities.

• Example (Penalty Kicks):

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

  • Find mixed NE: Let kicker play Left with p, Right with 1–p. Goalie indifferent:

$$1.4p + 1.7(1-p) = 1.5p + 1.5(1-p) \Rightarrow p^* = 0.4$$

Similarly for goalie.

Pathfinding Algorithms

• A* Algorithm:

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

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

    • $h(n)$: admissible heuristic (never overestimates true cost to goal, e.g., Manhattan distance).

  • Guarantee: Optimal if heuristic admissible.

  • Example: Grid pathfinding with obstacles.

• Breadth-First Search (BFS):

  • Explores all nodes at current depth before moving deeper.

  • Uses queue (FIFO).

  • Finds shortest path in unweighted graphs.

  • Example: Maze solving with unit step costs.

State Machines vs Behavior Trees

Finite State Machine (FSM) Construction
Scenario: Guard-Thief-Fight

• States: Guard, SeeThief, Fight, Flee

• Transitions:

  • Guard → SeeThief if thief_detected.

  • SeeThief → Fight if thief_strength ≤ guard_strength.

  • SeeThief → Flee if thief_strength > guard_strength.

  • Fight → Flee if health_low.

  • Flee → Guard if safe.

• Actions: patrol, chase, attack, run_away.

Model of Game AI

Components:

1. Perception: Sensors (vision, hearing) to gather world state.

2. Decision-Making:

   • Goal arbitration (select current goal).

   • Planning (pathfinding, action selection).

   • Utility-based or behavior tree evaluation.

3. Action Execution: Animation, movement, physics.

4. World Representation: Knowledge base (e.g., waypoints, remembered enemy positions).

Board Game Theory

• Application of minimax with alpha-beta pruning and evaluation functions (heuristics for non-terminal states).

• Opening Books: Precomputed move sequences for early game.

• Endgame Tablebases: Perfect play for simplified endgames (e.g., chess with ≤7 pieces).

• Monte Carlo Tree Search (MCTS): Used in Go, combines random playouts with tree expansion.

Decision Trees in Game Development

• NPC Decision Making: Tree of conditions → actions (e.g., combat: if health_low → potion, else if ammo_low → reload, else attack).

• Dialogue Systems: Branching conversations based on player choices.

• Adaptive AI: Trees updated based on player behavior (dynamic difficulty).

Stages of Motor Learning in AI Agents

1. Cognitive Stage: Agent explores actions, learns basic cause-effect (high error).

2. Associative Stage: Refines movements, reduces error through practice.

3. Autonomous Stage: Actions become smooth, automatic; low cognitive load.

3D Representations: Static vs Kinematic

• Static Representation: Fixed positions/orientations; used for initial setup, occlusion culling.

• Kinematic Representation: Includes motion over time (keyframes, skeletal animation); used for character movement, physics simulation.

Components of Coordinated Movement

1. Pathfinding: Global route (A*, navmesh).

2. Steering Behaviors: Local adjustments (seek, flee, obstacle avoidance).

3. Animation Blending: Smooth transitions between animations.

4. Physics Integration: Ragdoll, rigidbody dynamics.

5. Synchronization: Multiple agents (flocking, formation).

Movement Algorithm Structure

Sense Environment → Plan Path (global) → Generate Steering Forces (local) → Apply Physics → Animate → Repeat

Problem Tendency Decreasing Efficiency (Heuristic Limitations)

• Heuristics may be inadmissible (overestimate) → suboptimal solutions.

• Domain-specific: Heuristic tuned for one problem may fail for similar problems.

• Complexity: In high-dimensional spaces, heuristics become less informative (curse of dimensionality).

• Non-monotonic: Heuristic may not decrease consistently along path, causing inefficiency.

VI. Python for Predictive Analytics

A. Data Handling and Processing

Reading CSV and JSON Files

• CSV:

  
  import pandas as pd
  
  df = pd.read_csv('data.csv')  # Returns DataFrame
  
  

• JSON:

  
  import json
  
  with open('data.json') as f:
  
      data = json.load(f)  # Returns dict/list
  
  # Or with pandas:
  
  df = pd.read_json('data.json')
  
  

Converting Strings to JSON Arrays

import json

string = '[{"name":"Alice","age":30},{"name":"Bob","age":25}]'

json_array = json.loads(string)  # Converts to Python list of dicts

Data Extraction Tools and Techniques

• BeautifulSoup: HTML/XML parsing.

  
  from bs4 import BeautifulSoup
  
  import requests
  
  response = requests.get(url)
  
  soup = BeautifulSoup(response.text, 'html.parser')
  
  titles = soup.find_all('h1')
  
  

• Scrapy: Full web crawling framework (spiders, pipelines).

• APIs: Use requests to fetch JSON/XML from REST endpoints.

• Databases: sqlite3, SQLAlchemy for SQL; pymongo for MongoDB.

Text Processing Libraries

• NLTK: Tokenization, stemming, POS tagging, WordNet.

  
  import nltk
  
  tokens = nltk.word_tokenize(text)
  
  

• spaCy: Industrial-strength NLP; fast, pre-trained models for NER, dependency parsing.

  
  import spacy
  
  nlp = spacy.load('en_core_web_sm')
  
  doc = nlp(text)
  
  

• TextBlob: Simplified API for common tasks (sentiment, translation).

  
  from textblob import TextBlob
  
  blob = TextBlob(text)
  
  sentiment = blob.sentiment
  
  

B. Numerical Computing with NumPy

Matrix Operations

import numpy as np

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

A_inv = np.linalg.inv(A)  # Inverse

C = np.dot(A, A_inv)      # Multiplication

# Or: C = A @ A_inv (Python 3.5+)

Statistical Computations

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

avg = np.mean(data)       # 3.0

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

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

# For sample variance: np.var(data, ddof=1)

C. Data Visualization with Matplotlib

Purpose and Applications

• Create static, interactive, or animated visualizations.

• Explore data distributions, relationships, trends.

• Communicate findings in reports/presentations.

Creating Charts

import matplotlib.pyplot as plt

# Bar chart (marks example)

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

# Line plot

x = [1,2,3,4]

y = [10,20,15,25]

plt.plot(x, y, marker='o')

plt.show()

# Histogram

data = np.random.randn(1000)

plt.hist(data, bins=30, edgecolor='black')

plt.show()

D. Implementation of ML Algorithms

Linear Regression using Gradient Descent

import numpy as np

# Generate sample data

X = 2 * np.random.rand(100, 1)  # Feature

y = 4 + 3 * X + np.random.randn(100, 1)  # Target with noise

# Add bias term (x0 = 1)

X_b = np.c_[np.ones((100, 1)), X]  # Shape (100,2)

# Hyperparameters

alpha = 0.1  # Learning rate

n_iterations = 1000

m = len(X_b)

# Initialize weights

theta = np.random.randn(2, 1)

# Gradient Descent

for iteration in range(n_iterations):

    gradients = (1/m) * X_b.T.dot(X_b.dot(theta) - y)

    theta = theta - alpha * gradients

print(f"Intercept: {theta[0][0]}, Coefficient: {theta[1][0]}")

Gradient Descent in TensorFlow

import tensorflow as tf

# Parameters

learning_rate = 0.01

n_epochs = 1000

# Placeholders

X = tf.placeholder(tf.float32, shape=[None, 1])

y = tf.placeholder(tf.float32, shape=[None, 1])

# Variables (weights)

W = tf.Variable(tf.random_normal([1,1]))

b = tf.Variable(tf.random_normal([1]))

# Model

y_pred = tf.matmul(X, W) + b

# Loss (MSE)

loss = tf.reduce_mean(tf.square(y_pred - y))

# Optimizer

optimizer = tf.train.GradientDescentOptimizer(learning_rate).minimize(loss)

# Session

init = tf.global_variables_initializer()

with tf.Session() as sess:

    sess.run(init)

    for epoch in range(n_epochs):

        sess.run(optimizer, feed_dict={X: X_b[:,1].reshape(-1,1), y: y})

    final_W, final_b = sess.run([W, b])

Mini-Batch Gradient Descent

• Split training data into small batches (e.g., 32 samples).

• For each epoch:

  1. Shuffle data.

  2. For each batch:

     • Compute gradient on batch.

     • Update parameters.

• Implementation:

  
  batch_size = 32
  
  for epoch in range(n_epochs):
  
      shuffled_indices = np.random.permutation(m)
  
      X_b_shuffled = X_b[shuffled_indices]
  
      y_shuffled = y[shuffled_indices]
  
      for i in range(0, m, batch_size):
  
          X_batch = X_b_shuffled[i:i+batch_size]
  
          y_batch = y_shuffled[i:i+batch_size]
  
          gradients = (1/batch_size) * X_batch.T.dot(X_batch.dot(theta) - y_batch)
  
          theta = theta - alpha * gradients
  
  

VII. Advanced Applications and Specialized Topics

Machine Learning in Graphs, Maps, and Map Searching

• Graph Neural Networks (GNNs): Node classification, link prediction, graph classification.

• Map Searching: Reinforcement learning for route optimization (e.g., Google Maps traffic prediction).

• Spatial Analysis: Clustering (DBSCAN) for location-based services, predictive modeling for urban planning.

Stable Marriages Algorithm in ML

• Gale-Shapley Algorithm: Finds stable matching between two sets (e.g., residents and hospitals).

• ML Applications:

  • Matching problems: job-market matching, organ donation allocation.

  • Recommendation systems: stable assignment of users to items.

  • Federated learning: matching clients and servers.

Probabilistic Modeling in ML

• Definition: Models that incorporate uncertainty using probability distributions.

• Example: Naive Bayes classifier:

$$P(y|x) \propto P(y) \prod_{i} P(x_i|y)$$

Assumes feature independence given class.

• Applications: Spam detection, medical diagnosis, sentiment analysis.

Probabilistic Inference in ML

• Need: Compute posterior probabilities for decision-making under uncertainty.

• Usage:

  • Bayesian networks: exact inference (variable elimination, junction tree).

  • Approximate inference: Markov Chain Monte Carlo (MCMC), variational inference.

• Algorithms:

  • Variable Elimination: Sum out hidden variables.

  • Belief Propagation: Message passing on graphs.

  • MCMC: Sample from posterior (e.g., Gibbs sampling).

Rule-Based Systems

• Definition: Systems that use "if-then" rules for reasoning.

• Example: Expert system for medical diagnosis:

  
  IF fever AND cough THEN possible_flu = 0.7
  
  IF fever AND rash THEN possible_measles = 0.8
  
  

• Components: Knowledge base (rules), inference engine (forward/backward chaining).

• Limitations: Brittle, hard to maintain, lacks learning.

Time Series Forecasting

• Average-Based Fuzzy Time Series:

  1. Partition time series into intervals (fuzzy sets).

  2. Compute fuzzy average for each interval.

  3. Forecast by mapping current fuzzy state to next interval’s average.

• Markov Chain with Modified Frequency Partitioning:

  1. Partition state space based on frequency of occurrences.

  2. Build transition matrix from observed transitions.

  3. Forecast next state as most probable transition from current state.

  Flowchart:

  DiagramCANVAS: Time series → Partition → Count transitions → Transition matrix → Predict next state

Applications in Healthcare and Biology

• Interconnectedness on Personal Genomes:

  • Use ML (e.g., deep learning) to analyze gene interactions, predict disease risk from genomic data.

  • Techniques: CNNs for DNA sequences, graph networks for gene regulatory networks.

• Prediction of Preterm Birth:

  • Features: maternal age, history, biomarkers (e.g., cervical length).

  • Models: Logistic regression, random forests, LSTMs for longitudinal data.

  • Goal: Early warning system for high-risk pregnancies.

Data Product Strategy
Steps for Building Successful Strategy:

1. Define Problem & Objectives: Align with business goals.

2. Data Acquisition & Governance: Ensure quality, compliance (GDPR, HIPAA).

3. Model Development: Choose appropriate algorithms, validate rigorously.

4. Deployment & Monitoring: APIs, batch processing; monitor drift, performance.

5. Feedback Loop: Retrain with new data, iterate.

Types of Data Products by Functionality:

Key Formulas Boxed

• Entropy: $$\displaystyle \boxed{H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i} $$

• Information Gain: $$\displaystyle \boxed{IG(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)} $$

• Linear Regression (Least Squares): $$\displaystyle \boxed{\hat{\beta} = (X^T X)^{-1} X^T y} $$

• Gradient Descent Update: $$\displaystyle \boxed{\theta := \theta - \alpha \nabla J(\theta)} $$

• Bellman Optimality: $$\displaystyle \boxed{V^*(s) = \max_a \sum_{s',r} P(s',r|s,a) \left[ r + \gamma V^*(s') \right]} $$

• Q-learning Update: $$\displaystyle \boxed{Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]} $$

• A* Cost: $$\displaystyle \boxed{f(n) = g(n) + h(n)} $$