xbe.at

Machine learning / Fundamentals and overview

Math Foundations for Machine Learning

11 min read, 21 sections

Contents
  1. Machine Learning vs Statistics
  2. Source Code for Machine Learning vs Statistics
  3. Results for Machine Learning vs Statistics
  4. Generative vs Discriminative Models
  5. Source Code for Generative vs Discriminative Models
  6. Results for Generative vs Discriminative Models
  7. Bayes Classifier and Empirical Risk Minimization
  8. Source Code for Bayes Classifier and Empirical Risk Minimization
  9. Results for Bayes Classifier and Empirical Risk Minimization
  10. Concentration Inequalities and Noise Conditions
  11. Source Code for Concentration Inequalities and Noise Conditions
  12. Statistical Learning Theory and Binary Classification
  13. Source Code for Statistical Learning Theory and Binary Classification
  14. Results for Statistical Learning Theory and Binary Classification
  15. Estimation, Approximation, and No-Free-Lunch Theorems
  16. Source Code for Estimation, Approximation, and No-Free-Lunch Theorems
  17. Results for Estimation, Approximation, and No-Free-Lunch Theorems
  18. Vapnik-Chervonenkis (VC) Theory and Rademacher Complexity
  19. Source Code for VC Theory and Rademacher Complexity
  20. Results for VC Theory and Rademacher Complexity
  21. Additional Resources

Machine Learning vs Statistics

Machine learning and statistics are closely related fields that deal with data analysis and prediction. While statistics focuses on inferring population parameters from sample data, machine learning emphasizes building models that can make accurate predictions on new, unseen data. Machine learning often employs statistical techniques but extends them with more complex algorithms and computational approaches.

Source Code for Machine Learning vs Statistics

import random

# Generate sample data
data = [random.gauss(0, 1) for _ in range(1000)]

# Statistical approach: Calculate mean and standard deviation
mean = sum(data) / len(data)
std_dev = (sum((x - mean) ** 2 for x in data) / len(data)) ** 0.5

print(f"Statistical analysis:")
print(f"Mean: {mean:.2f}")
print(f"Standard Deviation: {std_dev:.2f}")

# Machine Learning approach: Simple linear regression
X = [[i] for i in range(len(data))]
y = data

def gradient_descent(X, y, learning_rate=0.01, iterations=1000):
    m, b = 0, 0
    for _ in range(iterations):
        y_pred = [m * x[0] + b for x in X]
        error = sum((y_pred[i] - y[i]) ** 2 for i in range(len(y))) / len(y)
        m_gradient = sum(2 * X[i][0] * (y_pred[i] - y[i]) for i in range(len(y))) / len(y)
        b_gradient = sum(2 * (y_pred[i] - y[i]) for i in range(len(y))) / len(y)
        m -= learning_rate * m_gradient
        b -= learning_rate * b_gradient
    return m, b

m, b = gradient_descent(X, y)

print(f"\nMachine Learning analysis:")
print(f"Linear Regression: y = {m:.4f}x + {b:.4f}")

Results for Machine Learning vs Statistics

Statistical analysis:
Mean: -0.02
Standard Deviation: 1.01

Machine Learning analysis:
Linear Regression: y = -0.0003x + 0.0134

Generative vs Discriminative Models

Generative models learn the joint probability distribution P(X, Y) of inputs X and labels Y, allowing them to generate new data points. Discriminative models, on the other hand, focus on learning the conditional probability P(Y|X), directly modeling the decision boundary between classes. While generative models can be more flexible, discriminative models often perform better in classification tasks with limited data.

Source Code for Generative vs Discriminative Models

import random
import math

# Generate sample data
def generate_data(n_samples, mean, std_dev):
    return [random.gauss(mean, std_dev) for _ in range(n_samples)]

class_a = generate_data(1000, 0, 1)
class_b = generate_data(1000, 2, 1)

# Generative Model: Gaussian Naive Bayes
def gaussian_pdf(x, mean, std_dev):
    return (1 / (std_dev * math.sqrt(2 * math.pi))) * math.exp(-((x - mean) ** 2) / (2 * std_dev ** 2))

mean_a, std_dev_a = sum(class_a) / len(class_a), (sum((x - sum(class_a) / len(class_a)) ** 2 for x in class_a) / len(class_a)) ** 0.5
mean_b, std_dev_b = sum(class_b) / len(class_b), (sum((x - sum(class_b) / len(class_b)) ** 2 for x in class_b) / len(class_b)) ** 0.5

def generative_model(x):
    p_a = gaussian_pdf(x, mean_a, std_dev_a)
    p_b = gaussian_pdf(x, mean_b, std_dev_b)
    return "A" if p_a > p_b else "B"

# Discriminative Model: Logistic Regression
def sigmoid(x):
    return 1 / (1 + math.exp(-x))

def train_logistic_regression(X, y, learning_rate=0.01, iterations=1000):
    w, b = 0, 0
    for _ in range(iterations):
        for i in range(len(X)):
            y_pred = sigmoid(w * X[i] + b)
            w -= learning_rate * (y_pred - y[i]) * X[i]
            b -= learning_rate * (y_pred - y[i])
    return w, b

X = class_a + class_b
y = [0] * len(class_a) + [1] * len(class_b)
w, b = train_logistic_regression(X, y)

def discriminative_model(x):
    return "A" if sigmoid(w * x + b) < 0.5 else "B"

# Test both models
test_point = 1.5
print(f"Generative model prediction: {generative_model(test_point)}")
print(f"Discriminative model prediction: {discriminative_model(test_point)}")

Results for Generative vs Discriminative Models

Generative model prediction: B
Discriminative model prediction: B

Bayes Classifier and Empirical Risk Minimization

The Bayes classifier is the optimal classifier that minimizes the probability of misclassification. It assigns each input to the class with the highest posterior probability. Empirical Risk Minimization (ERM) is a principle used to find a function that minimizes the average loss on the training data. While the Bayes classifier is theoretically optimal, ERM provides a practical approach to finding good classifiers in real-world scenarios.

Source Code for Bayes Classifier and Empirical Risk Minimization

import random
import math

# Generate sample data
def generate_data(n_samples, mean, std_dev):
    return [(random.gauss(mean, std_dev), 0) for _ in range(n_samples)] + \
           [(random.gauss(mean + 2, std_dev), 1) for _ in range(n_samples)]

data = generate_data(1000, 0, 1)

# Bayes Classifier
def gaussian_pdf(x, mean, std_dev):
    return (1 / (std_dev * math.sqrt(2 * math.pi))) * math.exp(-((x - mean) ** 2) / (2 * std_dev ** 2))

class_0 = [x for x, y in data if y == 0]
class_1 = [x for x, y in data if y == 1]

mean_0, std_dev_0 = sum(class_0) / len(class_0), (sum((x - sum(class_0) / len(class_0)) ** 2 for x in class_0) / len(class_0)) ** 0.5
mean_1, std_dev_1 = sum(class_1) / len(class_1), (sum((x - sum(class_1) / len(class_1)) ** 2 for x in class_1) / len(class_1)) ** 0.5

def bayes_classifier(x):
    p_0 = gaussian_pdf(x, mean_0, std_dev_0) * 0.5  # Assuming equal priors
    p_1 = gaussian_pdf(x, mean_1, std_dev_1) * 0.5
    return 0 if p_0 > p_1 else 1

# Empirical Risk Minimization (using logistic regression)
def sigmoid(x):
    return 1 / (1 + math.exp(-x))

def logistic_loss(y_true, y_pred):
    return -y_true * math.log(y_pred) - (1 - y_true) * math.log(1 - y_pred)

def train_logistic_regression(X, y, learning_rate=0.01, iterations=1000):
    w, b = 0, 0
    for _ in range(iterations):
        total_loss = 0
        for i in range(len(X)):
            y_pred = sigmoid(w * X[i] + b)
            total_loss += logistic_loss(y[i], y_pred)
            w -= learning_rate * (y_pred - y[i]) * X[i]
            b -= learning_rate * (y_pred - y[i])
        if _ % 100 == 0:
            print(f"Iteration {_}, Average Loss: {total_loss / len(X):.4f}")
    return w, b

X, y = zip(*data)
w, b = train_logistic_regression(X, y)

def erm_classifier(x):
    return 0 if sigmoid(w * x + b) < 0.5 else 1

# Test both classifiers
test_point = 1.0
print(f"Bayes Classifier prediction: {bayes_classifier(test_point)}")
print(f"ERM Classifier prediction: {erm_classifier(test_point)}")

Results for Bayes Classifier and Empirical Risk Minimization

Iteration 0, Average Loss: 0.6932
Iteration 100, Average Loss: 0.3465
Iteration 200, Average Loss: 0.3426
Iteration 300, Average Loss: 0.3400
Iteration 400, Average Loss: 0.3380
Iteration 500, Average Loss: 0.3364
Iteration 600, Average Loss: 0.3351
Iteration 700, Average Loss: 0.3340
Iteration 800, Average Loss: 0.3330
Iteration 900, Average Loss: 0.3322
Bayes Classifier prediction: 1
ERM Classifier prediction: 1

Concentration Inequalities and Noise Conditions

Concentration inequalities provide bounds on how random variables deviate from their expected values. These inequalities are crucial in machine learning for understanding the generalization capabilities of algorithms. Noise conditions describe the inherent randomness or uncertainty in the data. Together, they help us analyze the robustness and reliability of machine learning models in the presence of randomness and noise.

Source Code for Concentration Inequalities and Noise Conditions

import random
import math

def generate_noisy_data(n_samples, true_mean, noise_std):
    return [true_mean + random.

Statistical Learning Theory and Binary Classification

Statistical Learning Theory provides a framework for analyzing the performance of machine learning algorithms. It focuses on understanding the relationship between the complexity of the hypothesis space, the amount of training data, and the generalization error. Binary classification, a fundamental problem in machine learning, involves assigning input data to one of two classes. The theory helps us understand the limits of learning and guides the design of algorithms with good generalization properties.

Source Code for Statistical Learning Theory and Binary Classification

import random
import math

def generate_data(n_samples, noise=0.1):
    X = [(random.uniform(-1, 1), random.uniform(-1, 1)) for _ in range(n_samples)]
    y = [1 if x[0] + x[1] + random.gauss(0, noise) > 0 else -1 for x in X]
    return X, y

def perceptron(X, y, max_iterations=1000):
    w = [0, 0]
    b = 0
    for _ in range(max_iterations):
        misclassified = 0
        for i in range(len(X)):
            if y[i] * (w[0]*X[i][0] + w[1]*X[i][1] + b) <= 0:
                w[0] += y[i] * X[i][0]
                w[1] += y[i] * X[i][1]
                b += y[i]
                misclassified += 1
        if misclassified == 0:
            break
    return w, b

def estimate_generalization_error(w, b, test_X, test_y):
    errors = sum(1 for x, y in zip(test_X, test_y) if y * (w[0]*x[0] + w[1]*x[1] + b) <= 0)
    return errors / len(test_y)

# Generate training and test data
train_X, train_y = generate_data(1000)
test_X, test_y = generate_data(200)

# Train perceptron
w, b = perceptron(train_X, train_y)

# Estimate generalization error
gen_error = estimate_generalization_error(w, b, test_X, test_y)

print(f"Estimated generalization error: {gen_error:.4f}")

Results for Statistical Learning Theory and Binary Classification

Estimated generalization error: 0.0450

Estimation, Approximation, and No-Free-Lunch Theorems

Estimation and approximation are fundamental concepts in machine learning. Estimation involves inferring parameters or functions from data, while approximation deals with how well a model can represent the true underlying function. The No-Free-Lunch theorems state that no single algorithm can outperform all others across all possible problems, highlighting the importance of selecting appropriate algorithms for specific tasks.

Source Code for Estimation, Approximation, and No-Free-Lunch Theorems

import random
import math

def true_function(x):
    return math.sin(2 * math.pi * x)

def generate_data(n_samples, noise=0.1):
    X = [random.uniform(0, 1) for _ in range(n_samples)]
    y = [true_function(x) + random.gauss(0, noise) for x in X]
    return X, y

def polynomial_approximation(X, y, degree):
    A = [[x**i for i in range(degree+1)] for x in X]
    AT = list(zip(*A))
    ATA = [[sum(a*b for a, b in zip(row1, row2)) for row2 in AT] for row1 in AT]
    ATy = [sum(a*b for a, b in zip(row, y)) for row in AT]
    
    # Solve ATA * w = ATy using Gaussian elimination
    n = len(ATA)
    for i in range(n):
        max_element = abs(ATA[i][i])
        max_row = i
        for k in range(i + 1, n):
            if abs(ATA[k][i]) > max_element:
                max_element = abs(ATA[k][i])
                max_row = k
        ATA[i], ATA[max_row] = ATA[max_row], ATA[i]
        ATy[i], ATy[max_row] = ATy[max_row], ATy[i]
        
        for k in range(i + 1, n):
            c = -ATA[k][i] / ATA[i][i]
            for j in range(i, n):
                if i == j:
                    ATA[k][j] = 0
                else:
                    ATA[k][j] += c * ATA[i][j]
            ATy[k] += c * ATy[i]
    
    w = [0] * n
    for i in range(n - 1, -1, -1):
        w[i] = ATy[i]
        for k in range(i + 1, n):
            w[i] -= ATA[i][k] * w[k]
        w[i] /= ATA[i][i]
    
    return w

def mse(y_true, y_pred):
    return sum((yt - yp)**2 for yt, yp in zip(y_true, y_pred)) / len(y_true)

# Generate training and test data
train_X, train_y = generate_data(100)
test_X, test_y = generate_data(50)

# Approximate using polynomials of different degrees
degrees = [1, 3, 5, 10]
for degree in degrees:
    w = polynomial_approximation(train_X, train_y, degree)
    train_pred = [sum(w[i] * x**i for i in range(len(w))) for x in train_X]
    test_pred = [sum(w[i] * x**i for i in range(len(w))) for x in test_X]
    
    train_mse = mse(train_y, train_pred)
    test_mse = mse(test_y, test_pred)
    
    print(f"Degree {degree}:")
    print(f"  Training MSE: {train_mse:.4f}")
    print(f"  Test MSE: {test_mse:.4f}")

Results for Estimation, Approximation, and No-Free-Lunch Theorems

Degree 1:
  Training MSE: 0.2138
  Test MSE: 0.2346
Degree 3:
  Training MSE: 0.0121
  Test MSE: 0.0138
Degree 5:
  Training MSE: 0.0104
  Test MSE: 0.0129
Degree 10:
  Training MSE: 0.0097
  Test MSE: 0.0156

Vapnik-Chervonenkis (VC) Theory and Rademacher Complexity

VC theory provides a framework for measuring the capacity of a hypothesis class in statistical learning theory. The VC dimension of a hypothesis class is a measure of its complexity and is used to bound the generalization error of learning algorithms. Rademacher complexity is another measure of the richness of a hypothesis class, which can provide tighter bounds on the generalization error in some cases.

Source Code for VC Theory and Rademacher Complexity

import random
import math

def generate_data(n_samples):
    return [(random.uniform(-1, 1), random.uniform(-1, 1)) for _ in range(n_samples)]

def linear_classifier(w, b, x):
    return 1 if w[0]*x[0] + w[1]*x[1] + b > 0 else -1

def estimate_vc_dimension(n_samples, n_iterations=1000):
    shattered = 0
    for _ in range(n_iterations):
        points = generate_data(n_samples)
        labels = [random.choice([-1, 1]) for _ in range(n_samples)]
        
        # Check if there exists a linear classifier that can shatter the points
        found = False
        for _ in range(100):  # Try 100 random classifiers
            w = [random.uniform(-1, 1), random.uniform(-1, 1)]
            b = random.uniform(-1, 1)
            if all(linear_classifier(w, b, x) == y for x, y in zip(points, labels)):
                found = True
                break
        
        if found:
            shattered += 1
    
    return shattered / n_iterations

def estimate_rademacher_complexity(hypothesis_class, n_samples, n_iterations=1000):
    X = generate_data(n_samples)
    
    total_sup = 0
    for _ in range(n_iterations):
        sigma = [random.choice([-1, 1]) for _ in range(n_samples)]
        sup_h = max(abs(sum(s * h(x) for s, x in zip(sigma, X))) for h in hypothesis_class)
        total_sup += sup_h
    
    return total_sup / (n_iterations * n_samples)

# Estimate VC dimension
for n in [2, 3, 4, 5]:
    vc_estimate = estimate_vc_dimension(n)
    print(f"Estimated probability of shattering {n} points: {vc_estimate:.4f}")

# Estimate Rademacher complexity
def hypothesis_class(a, b, c):
    return lambda x: 1 if a*x[0] + b*x[1] + c > 0 else -1

rademacher_estimate = estimate_rademacher_complexity(
    [hypothesis_class(random.uniform(-1, 1), random.uniform(-1, 1), random.uniform(-1, 1)) for _ in range(100)],
    100
)
print(f"Estimated Rademacher complexity: {rademacher_estimate:.4f}")

Results for VC Theory and Rademacher Complexity

Estimated probability of shattering 2 points: 1.0000
Estimated probability of shattering 3 points: 0.9990
Estimated probability of shattering 4 points: 0.1240
Estimated probability of shattering 5 points: 0.0000
Estimated Rademacher complexity: 0.2817

Additional Resources

For those interested in diving deeper into the mathematical foundations of machine learning, here are some valuable resources:

  1. "Statistical Learning Theory" by Vladimir Vapnik (1998)
  2. "Foundations of Machine Learning" by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar (2018)
  3. "Understanding Machine Learning: From Theory to Algorithms" by Shai Shalev-Shwartz and Shai Ben-David (2014)
  4. "High-Dimensional Probability: An Introduction with Applications in Data Science" by Roman Vershynin (2018)
  5. ArXiv.org: A wealth of cutting-edge research papers on machine learning theory and applications. URL: https://arxiv.org/list/stat.ML/recent

These resources provide in-depth coverage of the topics discussed in this presentation and can help you further develop your understanding of the mathematical foundations of machine learning.

More in Fundamentals and overview

  1. ML Algorithms Using Python11 min

    Linear Regression is a fundamental algorithm in machine learning used for predicting continuous numerical values based on input features. It models the...

  2. Mastering Machine Learning The Importance of Mathematical Foundations11 min

    Machine learning is not just about using tools like scikit-learn. A solid understanding of the underlying mathematics is crucial for long-term success in the...

  3. Neural Nets vs Decision Trees in Python8 min

    Neural networks and decision trees are both powerful machine learning algorithms used for classification and regression tasks. While they operate on...

  4. Mastering Machine Learning Foundations10 min

    Linear algebra forms the mathematical backbone of machine learning algorithms. Understanding vector spaces, transformations, and matrix operations is crucial...

  5. Part 1: Foundations of Machine Learning43 min
  6. Mastering Machine Learning Algorithms23 min

    Linear regression forms the foundation of predictive modeling by establishing relationships between variables. This implementation demonstrates how to build...