Scalable Analytics: Chapter 7

Principles of Supervised Learning

• Definition and Goals: Supervised learning aims to learn a function $f(x)$ such that $y = f(x)$. It is used for prediction based on a labeled dataset consisting of pairs $\text{\{(}x_n, y_n\text{)\}}$.

• Types of Output ($y$):

  • Regression: When the target variable is a real number.

  • Classification: When the target variable is categorical.

  • Complex Object: Predictions involving structured or multi-faceted outputs.

• Data Organization: The data is typically divided into a training set and a test set to evaluate model performance.

Large-Scale Machine Learning and the Effectiveness of Data

• The Unreasonable Effectiveness of Data: Research findings indicate that model performance increases logarithmically based on the volume of training data ($D_{train}$).

• Scalability Drivers: The complexity of modern machine learning models, such as deep neural networks, allows for significant performance gains when combined with large datasets.

• Core Question: The primary focus of large-scale analytics is determining how to efficiently train models on massive amounts of data.

• Methods Considered:

  • $k$-Nearest Neighbor ($k$-NN)

  • Decision Trees (DT)

  • Perceptron algorithms

  • Support Vector Machines (SVM)

  • Deep Learning

Fundamentals of Decision Trees

• Historical Context: Decision trees have been part of machine learning since the 1980s, introduced by Leo Breiman in 1984. Notable early algorithms include ID3 and C4.5.

• Modern Relevance: Even though they are older, hand-engineered, and based on heuristics, they remain the preferred method for tabular data and Kaggle competitions. Recent innovations include Boosted Decision Trees (Gradient Boosted DT) and Random Forests.

• Structural Components:

  • Internal Nodes: Data is split based on specific attributes.

  • Leaf Nodes: These nodes provide the final prediction.

  • Splits: Binary splits are common, where a numerical attribute $X^{(j)}$ is tested against a value $v$ (e.g., X^{(j)} < v).

• Mathematical Representation:

  • $d$ features/attributes represented as $x^{(1)}, x^{(2)}, \dots, x^{(d)}$.

  • Each attribute $x^{(j)}$ has a domain $O_j$.

  • $Y$ is the output variable with domain $O_Y$.

  • Data $D$ consists of $N$ examples $(x_i, y_i)$ where $x_i$ is a $d$-dimensional feature vector.

Constructing the Decision Tree: The Splitting Process

• Splitting Logic: The goal is to pick an attribute and value that optimizes a specific criterion to create child nodes ($D_L$ and $D_R$) from a parent node ($D$).

• Regression - Purity Criterion: Splitting aims to maximize the reduction in variance:

  • $\text{Purity} = |D| \times Var(D) - (|D_L| \times Var(D_L) + |D_R| \times Var(D_R))$

• Classification - Information Gain: This measures how much an attribute $X$ informs us about the class $Y$. It represents the average number of bits saved when transmitting $Y$ if $X$ is known.

  • Entropy ($H(X)$): The smallest possible average number of bits per symbol needed to transmit a stream drawn from the distribution of $X$.

  • High Entropy: Characterized by a uniform distribution.

  • Low Entropy: Characterized by a varied distribution with peaks and valleys.

  • Entropy Formula: $H(X) = - \sum_i P(x_i) \log_2 P(x_i)$.

  • Specific Conditional Entropy ($H(Y | X = v)$): The entropy of $Y$ considering only records where $X = v$.

  • Conditional Entropy ($H(Y | X)$): The average of all specific conditional entropies.

  • Information Gain Formula: $IG(Y | X) = H(Y) - H(Y | X)$.

Specific Example of Information Entropy

• Scenario: Predicting if someone likes the movie "Casablanca" ($Y$) based on their College Major ($X$).

• Data Estimates:

  • $P(Y = \text{Yes}) = 0.5$

  • $P(X = \text{Math} \, \&amp; \, Y = \text{No}) = 0.25$

  • $P(X = \text{Math}) = 0.5$

  • $P(Y = \text{Yes} | X = \text{History}) = 0$

• Calculations:

  • $H(Y) = -0.5 \times \log_2(0.5) - 0.5 \times \log_2(0.5) = 1$

  • $H(X) = 1.5$

  • $H(Y | X = \text{Math}) = 1$

  • $H(Y | X = \text{History}) = 0$

  • $H(Y | X = \text{CS}) = 0$

  • $H(Y | X) = 0.5 \times 1 + 0.25 \times 0 + 0.25 \times 0 = 0.5$

  • $IG(Y | X) = 1 - 0.5 = 0.5$

Decision Tree Construction Algorithm and Stopping Criteria

• General Algorithm (InMemoryBuildNode):

  1. Find the best split for the node results in $n_{split}, D_L, D_R$.

  2. If stopping criteria for $D_L$ are met, find and store the left prediction.

  3. Otherwise, recursively call the build function for the left child.

  4. Repeat the process for the right child $D_R$.

• Stopping Criteria Heuristics:

  1. Leaf is "pure": The target variable variance is below a threshold (Var(y) < \epsilon).

  2. Sample size: The number of examples in the leaf is too small.

• Prediction Methods:

  • Regression: Predict the average $y_i$ of leaf examples or build a linear regression model within the leaf.

  • Classification: Predict the most common $y_i$ in the leaf.

Scalable Decision Trees using MapReduce (PLANET)

• PLANET (Parallel Learner for Assembling Numerous Ensemble Trees): Designed for scenarios where the tree is small enough for memory, but the dataset is too large to scan on a single machine or fit in memory.

• Setting:

  • Hundreds of numerical attributes (discrete or continuous, but not categorical).

  • Numerical target variable (Regression).

  • Binary splits (X(j) < v).

• Workflow:

  1. Master Node: Decides candidate splits and grows the tree level by level. It monitors the entire process.

  2. MapReduce Jobs:

     • Initialization: Identifies all attribute values to consider for splits. It generates "attribute metadata."

     • FindBestSplit: Mappers calculate sufficient statistics ($N$, $S = \sum y_i$, $Q = \sum y_i^2$) for their data subsets. Reducers aggregate these to compute global variance and purity.

     • InMemoryBuild: If the data at a node is small enough, it is processed locally in memory rather than via MapReduce.

• Split Selection: For large data, sorting all values is inefficient. Instead, an equi-depth histogram is computed for attribute $X^{(j)}$ on the complete dataset $D^*$, and boundary points are used as splits.

Learning Ensembles and Random Forests

• Bagging (Bootstrap Aggregating): Learns multiple trees over independent samples of the training data. For a dataset $D$ with $n$ points, a new dataset $D'$ is created by sampling $n$ points from $D$ with replacement. Final predictions are averaged across all trees.

• Random Forests: An enhancement of bagging where the learning algorithm only selects from a random subset of features at each candidate split (Feature Bagging). This breaks the correlation between individual trees and often provides state-of-the-art results for many classification problems.

Instance-Based Learning: k-Nearest Neighbor (k-NN)

• Mechanism: Unlike trees, this approach keeps the entire training dataset. For a query vector $q$, the model identifies the most similar examples.

• Requirements:

  • Distance Metric: Typically Euclidean distance.

  • Neighbor Count ($k$): The number of points to consider.

  • Weighting Function: Optional (often unused in basic models).

  • Fitting Strategy: Predict the average output among $k$ neighbors for regression, or the majority class for classification.

• Search Algorithms:

  • Main Memory: Linear scan, Tree-based (kd-tree), or Hashing.

  • Secondary Storage: R-trees.

• Applications: Range searches, collaborative filtering, and finding the nearest neighbor $p$ for a query $q$ in a set $P$.