PaperlayerView exact revision on arXiv

Source-linked AI summary

A Brief Introduction to Machine Learning for Engineers

Osvaldo Simeone

arXiv:1709.02840v3cs.LGcs.ITstat.ML

TL;DR

The monograph addresses how to learn from data using a unified introduction to machine-learning concepts, algorithms, and theory. It develops probabilistic treatments of supervised and unsupervised learning, organized across major modeling and inference categories. The text provides foundational coverage alongside advanced topics and literature pointers, with scope limited by issues including adversarial examples.

  • Problem

    The monograph addresses the need for an accessible, broad introduction to machine-learning concepts, algorithms, and theoretical results for readers with probability and linear-algebra backgrounds.

  • Method

    It develops probabilistic models for supervised and unsupervised learning from first principles within a unified notation and framework spanning major modeling and inference categories.

  • Results

    The monograph presents a broad overview of foundational concepts, algorithms, and theoretical results while exposing readers to advanced topics and research literature.

  • Takeaways & Limitations

    The text serves as an entry point for researchers seeking systematic coverage of probabilistic machine learning and pointers to advanced research directions.

  • Takeaways & Limitations

    The discussion notes that adversarially chosen examples can cause machine failure, making robustness to such examples an active research area.

Abstract

from arXiv · show

This monograph aims at providing an introduction to key concepts, algorithms, and theoretical results in machine learning. The treatment concentrates on probabilistic models for supervised and unsupervised learning problems. It introduces fundamental concepts and algorithms by building on first principles, while also exposing the reader to more advanced topics with extensive pointers to the literature, within a unified notation and mathematical framework. The material is organized according to clearly defined categories, such as discriminative and generative models, frequentist and Bayesian approaches, exact and approximate inference, as well as directed and undirected models. This monograph is meant as an entry point for researchers with a background in probability and linear algebra.

Notation

The notation establishes conventions for random variables, distributions, expectations, vectors, matrices, norms, sets, and common mathematical operators.

  • Random variables and their values use distinct typefaces, while vectors are column-form and matrices use uppercase fonts.
  • Distributions, conditional distributions, expectations, and sampling relationships are written using p, p(x|y), E, and ∼ notation.
  • The logarithm notation distinguishes base-two log from natural logarithm ln, and Gaussian and uniform distributions use N and U notation.
  • The notation defines delta and indicator functions, vector norms, identity and all-ones objects, real-number sets, set cardinality, and indexed variable sets.

Acronyms

The acronym list defines abbreviations spanning probabilistic modeling, optimization, inference, learning frameworks, and common machine-learning methods.

  • The list includes abbreviations for probabilistic models and learning frameworks, including BN, DAG, GLM, HMM, ERM, GAN, MDL, and VAE.
  • It also defines abbreviations for inference, optimization, and sampling methods, including AMP, ELBO, EM, LBP, MFVI, MC, MCMC, and SGD.
  • Common algorithms and representations include LASSO, PCA, PPCA, QDA, RBM, SVM, and VC.

Introduction

The introduction contrasts conventional engineering design with data-driven machine learning and outlines the tasks, suitability criteria, and probabilistic focus of the monograph. It presents the book as a broad entry point covering supervised and unsupervised learning within a unified framework.

  • Introduction: The conventional engineering flow analyzes a domain, builds a mathematical model, and derives hand-crafted solutions using expert knowledge.
  • Introduction: Machine learning replaces much hand-crafted modeling with large data sets and general-purpose algorithms trained for tasks such as prediction or representation learning.
  • When to Use Machine Learning?: Machine learning is presented as useful when development cost or time matters, or when the problem is too complex for full general analysis, but it may reduce performance or interpretability.
  • When to Use Machine Learning?: Suitable tasks generally have well-defined inputs and outputs, available input-output data, clear feedback, and tolerance for error.
  • When to Use Machine Learning?: Machine learning is less suitable for tasks requiring long chains of common-sense reasoning, detailed explanations, or rapidly changing learned phenomena.
  • Goals and Outline: The monograph focuses on probabilistic models for supervised and unsupervised learning, organized across discriminative/generative, frequentist/Bayesian, exact/approximate, and directed/undirected categories.

A Gentle Introduction through Linear Regression

Supervised learning requires assumptions linking inputs to targets, and linear regression illustrates how model complexity, data size, regularization, and Bayesian inference affect generalization. The examples show that fitting training data alone can underfit or overfit, while additional data and probabilistic modeling improve assessment of predictive uncertainty.

  • Supervised learning: Without assumptions about how x and t are related, predictions for unseen inputs are impossible under the no free lunch theorem.The assumed mechanism may include properties such as smoothness.
  • Maximum likelihood: With M = 1, maximum likelihood underfits because the model cannot capture observed variation, producing large training loss.
  • Maximum likelihood: With M = 9, maximum likelihood overfits: training loss is small, but predictions outside the training set are inaccurate and generalization loss is large.Overfitting corresponds to memorizing training examples rather than learning to generalize.
  • Maximum likelihood: As model order increases, training loss decreases while generalization loss eventually rises; in this example, M > 7 overfits and M < 3 underfits.The widening gap between training and generalization losses signals overfitting.
  • Data size and bias: As N grows, training and generalization losses converge toward the minimum loss for the chosen model, while smaller models retain an irreducible bias floor.More data reduces estimation error but cannot remove bias caused by restricting the hypothesis class.
  • Regularization and Bayesian inference: Regularization penalizes implausibly large weights and effectively reduces model capacity, while MAP approaches ML as N grows because the prior contribution decreases as 1/N.The Bayesian predictive distribution additionally represents input-dependent uncertainty, often smaller near observed training points.

Probabilistic Models for Learning

The chapter develops probabilistic models through exponential-family structure, sufficient statistics, and maximum-entropy principles, then connects frequentist and Bayesian estimation to predictive behavior as data grows.

  • The exponential family includes many common probability models, including Gaussian, Laplace, Gamma, Beta, Dirichlet, Bernoulli, categorical, multinomial, and Poisson distributions.
  • Exponential-family models are specified through sufficient statistics, a base measure, and natural parameters constrained by a finite log-partition function.The partition function normalizes the distribution, while the sufficient-statistic vector captures the data dependence relevant to estimating natural parameters.
  • The log-likelihood depends only on K sufficient statistics, whose dimension does not grow with the number of observations, a distinctive property of the exponential family.This finite-dimensional reduction is associated with the Koopman–Pitman–Darmois theorem under the stated support condition.
  • Maximum-likelihood estimation in exponential families matches model ensemble averages to empirical data averages through moment matching.The result follows from the likelihood optimality condition under the stated concavity and regularity assumptions.
  • Maximum-likelihood estimates are consistent under correct model specification as the sample size tends to infinity, but finite samples may still produce overfitting.
  • Bayesian predictive distributions combine prior and data information: with small samples they approach the prior mean, while with large samples they approach the maximum-likelihood solution.For the Beta-Bernoulli example, the predictive probability approaches a/(a + b) for small N and N[1]/N for large N.
  • Exponential-family distributions maximize entropy among distributions satisfying the specified expected sufficient-statistic constraints.

Classification

This chapter develops classification through stochastic optimization, deterministic and probabilistic discriminative models, and probabilistic generative models. It shows how model assumptions and regularization affect separability, convergence, generalization, and feature learning.

  • Chapter roadmap: Classification is introduced after SGD, then developed through deterministic, probabilistic discriminative, and probabilistic generative models.The chapter applies SGD beyond classification and uses it throughout the monograph for other learning problems.
  • Stochastic Gradient Descent: SGD repeatedly selects a mini-batch and updates parameters in a descent direction using a learning-rate schedule.The cost is decomposed over training examples, and mini-batches may be selected in a predetermined order or randomly.
  • Linear classification: Nonlinear or nonseparable data can make linear classifiers ineffective, producing large average losses or complete perceptron failure.The perceptron converges finitely on linearly separable data, but fails on nonseparable examples such as XOR.
  • Support Vector Machines: SVM combines regularization with convex optimization, providing theoretical generalization guarantees and resistance to significant overfitting in the illustrated higher-order model.For the example, SVM effectively partitions the classes at M = 3 and remains apparently robust at M = 8.
  • Neural networks: A multilayer network learns features that improve classification where a linear-feature logistic model cannot capture the data structure.The example uses N = 300 training examples, one hidden layer, and six sigmoid hidden neurons; both models are trained using SGD.
  • Generative probabilistic models: QDA performs well when covariates are modeled by Gaussian components with different covariance matrices, whereas equal-covariance LDA fails in the example.The chapter attributes LDA’s failure to the bias induced by its equal class-dependent covariance assumption.
  • Convergence: SGD converges to the optimum for strictly convex objectives and to stationary points for non-convex objectives with bounded curvature.Larger mini-batches reduce gradient-estimate variance near stationary points, while smaller batches can improve convergence speed far from the optimum and generalization.

Appendix B: Kernel Methods∗

Kernel methods solve the SVM problem in a dual, quadratic, convex form and express the optimal activation through kernel functions. This makes decisions depend on support vectors and permits kernels corresponding to high-dimensional or implicit feature spaces.

  • Dual formulation: SVM optimization can be transformed into a quadratic, convex problem over dual variables using Lagrange duality.The dual variables are the Lagrange multipliers.
  • Kernel representation: The optimal activation expresses an input’s label decision through kernel evaluations involving support vectors.A kernel measures correlation, informally interpreted as similarity, between two input vectors.
  • Kernel representation: The representer theorem shows that the optimal weight vector is a linear combination of the feature vectors associated with training examples.This provides an alternative justification for the kernel-based activation.
  • Computational perspective: Dual optimization can be computationally advantageous when the number of primal variables exceeds the number of dual variables.The primal variable dimension is the size of the weight vector, whereas the dual variable count is tied to the number of training examples.
  • Kernel choices: Kernel functions need not be explicitly defined through a feature map, enabling polynomial and Gaussian kernels for implicit high-dimensional representations.The polynomial kernel corresponds to an inner product in a high-dimensional space.
  • Related methods: k-NN uses data-dependent kernels and assumes that nearby inputs have similar labels rather than relying on a parametric input-output model.It is presented as an example of a nonparametric learning rule.

Statistical Learning Theory∗

Statistical learning theory studies how model capacity and sample size govern generalization in binary classification. PAC learning formalizes universal accuracy and confidence guarantees, while ERM achieves bounds whose dependence on capacity is characterized by finite-class results and VC dimension.

  • Scope and objective: Statistical learning theory formalizes the trade-off between available data and generalization performance through capacity, estimation error, and bias.The chapter focuses on discriminative deterministic binary classifiers under 0-1 loss.
  • Learning objective: The learning objective is to select a hypothesis in H with generalization error as close as possible to the minimum achievable within H.The optimal predictor depends on the unknown true distribution, so it cannot be obtained directly.
  • Learning objective: Because the data distribution is unknown and the training set is random, learning rules can only approximate minimum generalization loss with probabilistic guarantees.ERM is one such rule, and its output is random because it depends on the training set.
  • PAC framework: PAC learning requires an accuracy guarantee that holds with confidence 1 − δ universally over all data distributions.The accuracy parameter ε is also described as estimation error or generalization gap.
  • PAC framework: As the sample size increases, empirical risk becomes an increasingly reliable uniform estimate of generalization loss across hypotheses.The required sample count grows with the capacity of the hypothesis class.
  • Finite classes: Finite hypothesis classes are PAC learnable, and ERM achieves the corresponding upper-bound sample complexity for any desired accuracy and confidence once N exceeds the threshold.The finite-class result establishes PAC learnability for every finite class.
  • Finite classes: For finite classes, capacity is measured by ln |H| in nats or log2 |H| in bits, and sample complexity increases more sharply when accuracy improves than when confidence improves.The capacity equals the number of bits or nats required to index the hypotheses.
  • Finite classes: The ERM generalization estimation error scales with the square root of model capacity and the inverse square root of N.This bound holds with probability 1 − δ.

Unsupervised Learning

Unsupervised learning seeks useful properties of an unknown data distribution, typically using latent variables to explain observed structure. The chapter develops clustering, generative models, ELBO-based inference, EM, GANs, and representation-learning methods.

  • Latent variables commonly help explain the structure or generation of observed data.
  • The chapter covers K-means, directed and undirected generative models, discriminative models, and autoencoders.
  • Unsupervised learning operates on unlabelled data and aims to learn useful properties of the unknown distribution p(x).
  • The ELBO is a global lower bound on log-likelihood, with equality when the variational distribution matches the posterior; it is concave under stated conditions.
  • EM exploits ELBO optimization to produce a procedure guaranteed to converge to a stationary point of the original maximum-likelihood problem.
  • GANs adaptively select a divergence through discriminator optimization and estimate likelihood ratios between data and model distributions.

probabilistic graphical models.

Probabilistic graphical models represent supervised and unsupervised learning relationships through structured dependencies and conditional independences. Bayesian networks encode directed factorizations, while examples such as naive Bayes and image denoising show how structural assumptions reduce complexity or capture correlations.

  • Structured probabilistic models use observed variables as inputs or targets and latent variables to help explain or generate observations.
  • Naive Bayes: Naive Bayes assumes word indicators are conditionally independent given the topic, enabling an exponential reduction in parameters.
  • Graphical structure corresponds to conditional-independence assumptions that induce factorizations of joint distributions.
  • Bayesian networks: A Bayesian network is a directed acyclic graph whose joint distribution factorizes according to each variable and its parents.
  • Bayesian networks: In a Bayesian network, parent variables encode local conditional dependencies, while plates represent independent replicas of graph components.

Fully Observed Data with Separate Parameters

For fully observed data with separate parameters, likelihood factorization allows parameter estimates to be computed independently for each parent configuration. This simplifies learning but can create overfitting through data fragmentation.

  • The log-likelihood factorizes over observations and parent configurations in a Bayesian network.
  • Separate parameters allow each conditional-distribution parameter to be estimated independently from the observations sharing its parent configuration.
  • Data fragmentation can cause overfitting when separate parameters are learned from sparsely populated parent configurations.
  • For binary variables, the maximum-likelihood estimate is formed from the corresponding parent-conditioned observations.

Notes on the General Case

Markov random fields encode compatibility through undirected graphs, complementing Bayesian networks’ directed dependence structure. Their partition function supports normalized joint distributions but makes probability evaluation and parameter learning difficult, motivating specialized inference methods.

  • Markov random fields: Markov random fields encode probability factorizations through undirected graphs rather than directed graphs.
  • Markov random fields: MRF factors assign larger values to more compatible clique configurations without distinguishing conditioning from conditioned variables.
  • MRFs are suited to mutual compatibility relationships, whereas Bayesian networks are suited to causality effects.
  • Inference and learning: The partition function generally makes evaluating probabilities and sampling in large MRFs intractable.
  • Inference and learning: Because the partition function couples parameters across cliques, MRF parameters cannot generally be estimated independently.
  • Bayesian inference: Bayesian inference computes posteriors of latent variables given observations, and EM requires these posteriors for its latent-variable updates.
  • Bayesian inference: Belief propagation evaluates posteriors with complexity of order |Z|^2, avoiding exponential scaling with the number of time samples.

Approximate Inference and Learning

Exact posterior computation becomes intractable for large hidden-variable spaces, motivating approximate inference. The chapter introduces Monte Carlo and variational methods, examines projection choices, and discusses their use in learning.

  • Posterior computation can become intractable when the hidden variable alphabet is sufficiently large, except for certain tractable graphical-model classes.
  • The chapter introduces Monte Carlo and Variational Inference as lower-complexity approaches to inference and learning.
  • Monte Carlo Methods: Monte Carlo methods replace ensemble averages with empirical averages over randomly generated samples, with consistency guaranteed as the sample count grows.
  • Monte Carlo Methods: Sampling from an undirected model's marginal can be difficult because ancestral sampling is unavailable for Markov random fields.
  • Variational Inference: Amortized variational inference applies a learned inference distribution directly to previously unseen inputs instead of recomputing projections.
  • Variational Inference: The I-projection is mode-seeking and often underestimates variance, whereas the M-projection is inclusive and spans the posterior support.
  • Mean Field Variational Inference: Mean-field variational inference uses only the joint distribution and converges to a stationary point, but its factorization can impose a nonzero KL-divergence floor.
  • The monograph also covers approximate inference in learning while noting that improved techniques remain an active research area.

A.1 Entropy

Entropy measures uncertainty through the loss incurred by optimal estimation, with definitions depending on whether point values or distributions are predicted. Under log-loss, Shannon entropy is the minimum average log-loss, while generalized entropy is concave.

  • Point Estimates: Generalized entropy measures the average loss of the best prior estimate under a specified loss function.
  • Point Estimates: For quadratic loss, generalized entropy equals variance, while for 0-1 loss it equals the minimum probability of detection error.
  • Distributional Estimates: Distributional estimation chooses a probability mass function as the prediction, representing beliefs or wagered fractions over possible outcomes.
  • Distributional Estimates: Log-loss is motivated by lossless compression because a prefix-free code can represent outcome x using ⌈−log ˆp(x)⌉ bits.
  • Distributional Estimates: Shannon entropy is the minimum average log-loss when optimizing over all probability mass functions.
  • Distributional Estimates: For alphabets with more than two elements, log-loss is the only loss in the stated class for which the true pmf is optimal.
  • Generalized entropy is concave, so mixtures have entropy at least as large as the corresponding mixture of component entropies.

A.2 Conditional Entropy and Mutual Information

The section develops generalized conditional entropy and mutual information from loss-based inference, then connects binary hypothesis testing to divergences between probability models. It shows how common losses recover familiar quantities and how optimal detectors induce f-divergences.

  • Conditional entropy: Generalized conditional entropy averages the minimum loss for estimating x after observing y under a specified loss function.Its value depends on the joint distribution pxy, whereas the conditional quantity for a fixed observation depends only on px|y=y.
  • Conditional entropy: Under squared error, generalized conditional entropy is the average conditional variance, with the posterior mean as the optimal estimate.Under 0-1 loss, it becomes the minimum detection error, achieved by the MAP estimate.
  • Mutual information: Observing y cannot increase generalized conditional entropy on average, with equality when x and y are independent.However, the conditional entropy for an individual observation need not be smaller than the unconditional entropy.
  • Mutual information: Generalized mutual information measures the decrease in average loss from observing y rather than relying only on prior information about x.With log-loss, it reduces to Shannon mutual information.
  • Divergences: Binary hypothesis testing constructs divergences by optimizing a decision rule that favors observations generated by one pmf while penalizing errors favoring the other.The rule is linked to the likelihood ratio, and convex duality yields the family of f-divergences.
  • Divergences: f-divergences include KL and Jensen-Shannon divergence as special cases and satisfy the data processing inequality.For exponential-family distributions, KL divergence can also be expressed as a Bregman divergence generated by the log-partition function.
Loading 1709.02840v3…