R Notebook

Stream Name: Texaschikkita
Stream URL: https://rpubs.com/Texaschikkita
Stream ID: 9962324179
Measurement Id: G-CV2648GQMK
—

Module 14: Data Parallelism and Graph Parallelism

1. Introduction to Data Parallelism

Big Data Overview

• Mathematical Representation of Parallel Computation: Given a dataset \(D\) and a task \(T\), the task can be divided into \(n\) parts: \[ T(D) = \sum_{i=1}^n T(D_i) \] where \(D_i\) are subsets of the data \(D\), processed independently.

• Throughput Analysis: The speedup \(S\) of parallel processing compared to serial processing: \[ S = \frac{T_{\text{serial}}}{T_{\text{parallel}}} \] where \(T_{\text{serial}}\) is the time for sequential execution, and \(T_{\text{parallel}}\) is the execution time with \(n\) parallel units.

---

2. Data Parallelism

MapReduce Framework

• Mathematical Steps:

  • Mapping: Transform data into intermediate key-value pairs: \[ f(x) = (k, v) \] where \(k\) is the key and \(v\) is the value extracted from data \(x\).

  • Reducing: Aggregate values based on the keys: \[ g(k, [v_1, v_2, ..., v_m]) = \text{Result} \]

Grid Search Parameter Tuning

• Given parameters \(\Theta_1, \Theta_2, \ldots, \Theta_k\), the Cartesian product of these parameters defines the grid: \[ G = \Theta_1 \times \Theta_2 \times \ldots \times \Theta_k \]
  • Example: For \(\text{gamma} = \{1000, 10000, 100000\}\) and \(\text{C} = \{1, 10, 100\}\): \[ G = \{(1000, 1), (1000, 10), \ldots, (100000, 100)\} \]
• Cross-validation error for each parameter combination: \[ E(\theta) = \frac{1}{k} \sum_{i=1}^k \text{Loss}(\hat{y}_i, y_i) \] where \(k\) is the number of folds, \(\hat{y}_i\) is the predicted value, and \(y_i\) is the true value.

---

3. Visualization of Parameter Search

• Use heatmaps to visualize performance over the parameter space.
• Mathematical Representation: The grid search performance matrix: \[ M(i, j) = \text{mean\_score}(C_i, \gamma_j) \] where \(M(i, j)\) stores the cross-validation score for parameter combination \((C_i, \gamma_j)\).

import matplotlib.pyplot as plt
import numpy as np

# Simulated results for visualization
scores = np.array([[0.8, 0.85, 0.87], [0.83, 0.88, 0.89], [0.85, 0.89, 0.9]])
C_values = [1, 10, 100]
gamma_values = [1000, 10000, 100000]

# Heatmap
plt.imshow(scores, interpolation='nearest', cmap='viridis')
plt.title('Grid Search Performance')
plt.colorbar()
plt.xticks(range(len(gamma_values)), gamma_values)
plt.yticks(range(len(C_values)), C_values)
plt.xlabel('Gamma')
plt.ylabel('C')
plt.show()

---

4. Randomized Search Optimization

Mathematical Optimization:

• Instead of evaluating all grid points, sample \(n\) random points: \[ \Theta_{\text{sampled}} \subset \Theta \]
• Choose the best parameters based on sampled evaluations: \[ \theta^* = \arg\min_{\theta \in \Theta_{\text{sampled}}} E(\theta) \]

---

5. Challenges and Insights

Challenges of Iterative Algorithms:

• Many machine learning algorithms, like Gradient Descent, are difficult to parallelize due to iterative dependencies: \[ \theta_{t+1} = \theta_t - \eta \nabla f(\theta_t) \] where \(\theta_t\) is the parameter at iteration \(t\), \(\eta\) is the learning rate, and \(\nabla f\) is the gradient of the objective function.

Fault Tolerance in Distributed Systems:

• Use techniques like checkpointing: \[ S = \frac{T_{\text{failure-recovery}}}{T_{\text{no-failure}}} \] where \(S\) is the system’s fault tolerance efficiency.

---

6. Summary

Mathematical insights enhance our understanding of parallel and distributed computing: 1. Data Parallelism: - Divide and conquer: \(T(D) = \sum_{i=1}^n T(D_i)\). - Effective for tasks like grid search and MapReduce. 2. Graph Parallelism: - Future modules will explore partitioning nodes and edges in complex tasks.

Tools like Scikit-learn and visualization techniques (e.g., heatmaps) make these concepts practical and accessible.

---

library(Rgraphviz)

# Example graph
g <- new("graphNEL", nodes = c("A", "B", "C"), edgemode = "directed")
g <- addEdge("A", "B", g)
g <- addEdge("B", "C", g)

# Render graph
plot(g)

library(DiagrammeR)

grViz("
  digraph dot {
    A -> B -> C;
    B -> D;
  }
")