Scalable Analytics: Chapter 8

Large-Scale Machine Learning and Analytics

• Machine learning at scale involves managing high-dimensional data, graph-based data, and infinite streams of data.

• Key focus areas include:

  • High Dimensional Data: Utilizing locality-sensitive hashing (LSH), clustering, and dimensionality reduction.

  • Graph Data: Implementing algorithms like PageRank, SimRank, community detection, and spam detection.

  • Infinite Data: Managing data streams through filtering, web advertising, and processing queries on streams.

  • Machine Learning Algorithms: Decisions trees, Perceptron, k-Nearest Neighbors (kNN), Support Vector Machines (SVM), and Deep Learning.

  • Applications: Recommender systems, association rules, and duplicate document detection.

Supervised Learning Foundations

• The goal of supervised learning is prediction by learning a function $f(x)$ such that $y = f(x)$.

• The target variable $y$ can take several forms:

  • Regression: When $y$ is a real number.

  • Classification: When $y$ is categorical.

  • Complex Objects: When the target involves more structured data.

• Data in supervised learning is labeled, consisting of pairs $\{(x_n, y_n)\}$.

• The process typically involves splitting data into a training set and a test set.

Linear Models: The Perceptron

• The Perceptron is an early linear model (Rosenblatt, 1958) used for binary classification.

• Example: Spam Filtering:

  • Instance space $x \in X$ where $|X| = n$ data points.

  • Features are binary or real-valued vectors based on word occurrences (e.g., "viagra", "dating", "nigeria").

  • There are $d$ features in total.

  • Class labels $y \in Y$ where $y = +1$ for Spam and $y = -1$ for Ham.

• Classification Logic:

  • The decision boundary is linear.

  • $f(x) = +1$ if $w_1 x_1 + w_2 x_2 + ... + w_d x_d \ge \theta$

  • $f(x) = -1$ otherwise.

  • Vectors $x^{(j)}$ are real-valued and normalized such that $x_2 = 1$.

  • The goal is to find the weight vector $w = (w_1, w_2, ..., w_d)$.

• Neuron Motivation:

  • Inputs represent feature values, each with a weight $w_i$.

  • The activation is the sum: $f(x) = \sum_i w_i x_i = w \cdot x$.

  • Prediction is $+1$ if the activation is positive and $-1$ if negative.

• Perceptron Learning Algorithm (PLA):

  • Iterative process: Pick a currently misclassified point $(x_t, y_t)$.

  • Update rule: $w(t + 1) = w(t) + y(t)x(t)$.

• Strengths and Weaknesses:

  • Good: Perceptron convergence theorem states that if data is linearly separable, the algorithm will converge.

  • Bad: If data is not separable, the weights will cycle indefinitely without converging.

  • Bad: It has mediocre generalization because it finds a "barely" separating solution.

Support Vector Machines (SVM)

• SVMs aim to separate data classes using a line or hyperplane with the largest possible margin.

• Large Margin Principle:

  • Distance from the separating hyperplane corresponds to prediction confidence.

  • The margin $\gamma$ is the distance of the closest example from the decision boundary.

  • Prediction is given by $\text{sign}(w \cdot x + b)$.

  • Confidence for the $i$-th point is $\gamma_i = y_i (w \cdot x_i + b)$.

  • The goal is to solve $\max_w \min_i \gamma_i$.

• Deriving the Margin:

  • Consider Line $L: w \cdot x + b = 0$, where $w = (w^{(1)}, w^{(2)})$.

  • For a point $A = (x_A(1), x_A(2))$ and a point $M$ on the line:

  • $d(A, L) = |(A - M) \cdot w| = x_A^{(1)} w^{(1)} + x_A^{(2)} w^{(2)} + b = w \cdot A + b$.

  • Note: This assumes $||w||_2 = 1$.

• Canonical Hyperplane and Normalization:

  • Scaling $w$ and $b$ increases the margin artificially.

  • Solution: Normalize weights such that $y_i (w \cdot x_i + b) \ge 1$ for the closest points.

  • Let $x_1$ be on the $+1$ plane and $x_2$ on the $-1$ plane.

  • Relation: $x_1 = x_2 + 2\gamma \frac{w}{||w||}$.

  • Since $w \cdot x_1 + b = 1$ and $w \cdot x_2 + b = -1$, it follows that the distance between planes is $w \cdot (x_1 - x_2) = 2$.

  • Substituting for $x_1$: $w \cdot (2\gamma \frac{w}{||w||}) = 2 \Rightarrow 2\gamma \frac{||w||^2}{||w||} = 2 \Rightarrow \gamma = \frac{1}{||w||}$.

• Hard Constraint Optimization:

  • To maximize $\gamma$, we minimize $||w||$.

  • Final objective: $\min_{w,b} \frac{1}{2} ||w||^2$ subject to $y_i (w \cdot x_i + b) \ge 1, \forall i$.

Non-linearly Separable Data and Slack Variables

• If data is not separable, hard margins fail. A penalty is introduced to allow for mistakes.

• Slack Variables (\xi_i):

  • If point $x_i$ is on the wrong side of the margin, it incurs a penalty $\xi_i$.

  • Objective with slack: $\min_{w,b,\xi} \frac{1}{2} ||w||^2 + C \sum_{i=1}^n \xi_i$

  • Subject to: $y_i (w \cdot x_i + b) \ge 1 - \xi_i$ and $\xi_i \ge 0$.

• Slack Penalty $C$:

  • High $C$: Strict separation; values weights of $\xi$ heavily (hard margin approach).

  • Low $C$: Permissive of mistakes to achieve a wider margin.

  • $C = 0$: Ignores the data (weights become zero).

• Hinge Loss Form:

  • The "natural" form of SVM uses hinge loss for empirical error:

  • $\text{argmin}_{w,b} \frac{1}{2} w \cdot w + C \sum_{i=1}^n \max(0, 1 - y_i (w \cdot x_i + b))$

SVM Optimization and Solvers

• Standard solvers use quadratic programming (minimizing a quadratic function under linear constraints).

• Problem: Quadratic solvers are inefficient for massive datasets.

• Alternative: Gradient Descent:

  • Used for minimizing convex functions $g(z)$.

  • Iterative update: $z_{t+1} \leftarrow z_t - \eta \nabla g(z_t)$, where $\eta$ is the learning rate.

• Stochastic Gradient Descent (SGD):

  • Instead of computing gradients over all $n$ examples (which takes $O(n)$ time), evaluate per individual example.

  • For each iteration:

  • For $i = 1$ to $n$:

    • Update weights: $w^{(j)} \leftarrow w^{(j)} - \eta \nabla f^{(j)}(x_i)$.

• Case Study: Text Categorization:

  • Dataset: Reuters RCV1 documents.

  • Stats: $n = 781,000$ training examples, $23,000$ test examples, $d = 50,000$ features (words).

  • Finding: SGD-SVM is super fast and achieves a test error comparable to standard SVM solvers.

• Practical Parameters:

  • Choose $t_0$ so initial updates match expected weight sizes.

  • Choose $\eta$ by testing small subsamples (e.g., $10, 1, 0.1, 0.01$) and picking the one that reduces cost most.

  • Use early stopping with a validation set; stop when validation loss stops decreasing.

Deep Learning and Neural Networks

• Deep neural networks use linear transformations combined with non-linear activation functions.

• Inspired by the brain's massive modeling power:

  • Human neuron switching time is $\approx 0.001\,s$.

  • Human brain has $\approx 10^{10}$ neurons.

  • Scene recognition in humans takes $\approx 0.1\,s$.

• Multi-Layer Perceptron (MLP):

  • Modern MLPs use multiple layers and differentiable activations like the Sigmoid function.

  • Sigmoid function: $\sigma(net) = \frac{1}{1 + e^{-net}}$.

  • The derivative is $\frac{d\sigma(y)}{dy} = \sigma(y)(1 - \sigma(y))$.

  • Capable of capturing highly non-linear surfaces via backpropagation.

• Convolutional Neural Networks (CNNs):

  • Take advantage of spatial information.

  • Feature translation invariance and weight sharing.

  • Hierarchical feature extraction.

• Hyperparameter Optimization:

  • Common methods: Grid search, Random search, Bayesian optimization.

  • Tools: HyperOpt, Optuna.

  • Optimizer of choice: Adam (Adaptive optimizer based on gradients).

Parallelization in Machine Learning

• Scale: Performance increases logarithmically relative to training data volume ($D_{train}$).

• Parallelization Strategies:

  • Model Parallelism: Different machines handle different parts of the model.

  • Data Parallelism: Data is partitioned (sharded) and processed by different workers.

• Parameter Server Architecture:

  • A Key/Value store where Keys index model parameters (weights) and Values are the weights themselves.

  • Challenges include bandwidth limits, synchronization, and fault tolerance.

• Asynchronous SGD (Async SGD):

  • Workers overwrite parameters opportunistically without central synchronization.

  • Theoretical slower convergence, but practically the same when gradients are sparse.

  • Example research: "HOGWILD!" (Recht et al., 2011).

  • Google's Large Scale Distributed Deep Networks (2012) combined model/data parallelism with Async SGD, fueling modern deep learning.

Reinforcement Learning (RL) and Specialized Architectures

• RL involves an agent interacting with an environment through actions, receiving states and rewards.

• Deep Q-Networks (DQN) (Mnih et al., 2015):

  • Neural networks used to approximate action-value functions.

  • Improved versions include DDQN, Prioritized DDQN, Dueling DDQN, and Rainbow.

• A3C (Asynchronous Advantage Actor-Critic):

  • Global network updated by multiple individual workers interacting with their own environments.

• AlphaGo:

  • AlphaGo Fan, AlphaGo Lee, AlphaGo Master, and AlphaGo Zero.

  • AlphaGo Zero (Silver, 2017) utilized 40 blocks and surpassed previous versions within days, reaching an Elo rating over 5,000.

Discussion and Events

• Upcoming Events and Exam Materials:

  • Invited talk by Jelena Grujic (Dataminded): Focus on industry application of big data (Attendance expected for exam preparation).

  • Flip the classroom: Scalability to facilitate LLMs.

  • Deep Dive into LLMs (Andrej Karpathy): Essential video material for the course covering ChatGPT and Transformers.

• Ethics: Balancing risk and innovation in big data is critical for responsible ML development with real-world impact.