Dictionary of Applied Machine Learning
The notation used throughout the entries, in the sections of the book's own List of Symbols. Each cross-reference links the term that defines the concept.
Sets and Functions · Vector Spaces · Probability Theory · Machine Learning · Federated Learning · Reinforcement Learning · Clustering · Convex Optimization
The object $a$ is an element of the set $\mathcal{A}$.
See also: data point, dataset, feature space.
The left-hand side $a$ is defined to equal $b$.
See also: function, hypothesis, loss.
The real-valued functions $f$ and $g$ are proportional, i.e., $f(x) = c\, g(x)$ for every $x$, with some nonzero constant $c \in \reals$.
See also: function, regularization.
The cardinality (i.e., number of elements) of a finite set $\mathcal{A}$.
See also: dataset, sample size, label space.
$\mathcal{A}$ is a subset of $\mathcal{B}$.
See also: subspace, hypothesis space, feature space.
$\mathcal{A}$ is a strict subset of $\mathcal{B}$.
See also: subspace, hypothesis space, feature space.
The Cartesian product of the sets $\mathcal{A}$ and $\mathcal{B}$.
See also: feature space, label space, data point.
The union of the sets $\mathcal{A}$ and $\mathcal{B}$, i.e., the set of all elements that belong to $\mathcal{A}$ or to $\mathcal{B}$ (or to both).
See also: dataset, label space, feature space.
The set difference of $\mathcal{A}$ and $\mathcal{B}$, i.e., the set of all elements of $\mathcal{A}$ that do not belong to $\mathcal{B}$.
See also: dataset, training set, test set.
The power set of $\mathcal{A}$, i.e., the set of all subsets of $\mathcal{A}$ (including the empty set and $\mathcal{A}$ itself). Each subset corresponds to an indicator map $\mathcal{A} \rightarrow \{0,1\}$, which explains the notation $2^{\mathcal{A}}$.
See also: label space, feature space, dataset.
The natural numbers $1, \,2, \,\dots$.
See also: sequence, sample size, iteration.
The positive real numbers $x> 0$.
See also: norm, eigenvalue, variance.
The imaginary unit $\imagunit = \sqrt{-1}$, used in the characteristic function.
See also: characteristic function, central limit theorem, random variable.
The set consisting of the two real numbers $0$ and $1$.
See also: binary classification, label, label space.
The closed interval $\{x \in \reals : 0 \leq x \leq 1\}$.
See also: probability, prediction, calibration.
The set of $\weights \in \mathcal{C}$ minimizing the real-valued function $f: \mathcal{C} \rightarrow \reals$.
See also: function, optimization problem, empirical risk minimization.
The unit sphere in $\reals^{\featuredim}$, i.e., the set of unit-norm vectors $\featurevec \in \reals^{\featuredim}$ with $\norm{\featurevec} = 1$. As for the probability simplex, the superscript is the intrinsic dimension of the sphere, one less than that of the ambient space: $\sphere{1}$ is the unit circle in $\reals^{2}$.
See also: norm, vector, Euclidean norm.
The exponential function evaluated at the real number $a \in \reals$.
See also: function, moment generating function, softmax function.
The softmax function $S\!: \reals^{\nrcluster} \rightarrow \simplex{\nrcluster-1}$, mapping a vector $\weights \in \reals^{\nrcluster}$ (logits) onto the probability simplex. Each output component is nonnegative and the components sum to one. When applied to a matrix whose rows are vectors of logits (as in attention), $\operatorname{softmax}(\mA)$ denotes row-wise application: each row of $\mA$ is mapped independently onto $\simplex{\nrcluster-1}$.
See also: softmax function, probability simplex, probability mass function, attention.
The logarithm of the positive number $a \in \reals_{++}$.
See also: function, entropy, logistic loss.
The cosine of the angle $\theta$, in radians, between two nonzero vectors $\featurevec, \featurevec'$ of an inner product space, $\cos \theta \defeq \innerprod{\featurevec}{\featurevec'} / \big( \norm{\featurevec} \norm{\featurevec'} \big)$. Since $\cos$ decreases strictly from $1$ to $-1$ on $[0,\pi]$, this determines one angle $\theta \in [0,\pi]$: the value $1$ at $\theta = 0$ for vectors of the same direction, $0$ at $\theta = \pi/2$ for orthogonal ones, and $-1$ at $\theta = \pi$ for opposite directions.
See also: inner product, norm, Cauchy-Schwarz inequality, orthogonal projection.
The binomial coefficient "$n$ choose $k$", equal to $\frac{n!}{k!(n-k)!}$ for integers $0 \leq k \leq n$. Counts the number of $k$-element subsets of an $n$-element set. For example, $\binom{\nrnodes}{2}$ is the number of unordered pairs of distinct nodes in a graph on $\nrnodes$ nodes (i.e., the number of possible undirected edges).
See also: Erdős–Rényi graph, graph.
A function (or map) from a set $\mathcal{A}$ to a set $\mathcal{B}$, assigning to each $a \in \mathcal{A}$ a unique $f(a) \in \mathcal{B}$. The set $\mathcal{A}$ is the domain and $\mathcal{B}$ the co-domain of $f$.
See also: function, domain, co-domain.
The composition of two functions (or maps) $f: \mathcal{A} \rightarrow \mathcal{B}$ and $g: \mathcal{B} \rightarrow \mathcal{C}$, defined by $(g \circ f)(a) = g(f(a))$ for every $a \in \mathcal{A}$.
See also: function, map.
The epigraph of a real-valued function $f: \reals^{\featuredim}\rightarrow \reals$.
See also: epigraph, function, convex.
A sequence of elements.
See also: sequence, convergence, iteration.
The indicator function of a set $\mathcal{A}$ evaluates to $1$ for any $x \in \mathcal{A}$ and to $0$ otherwise.
See also: indicator function, function, event.
The support function of a set $\mathcal{C} \subseteq \reals^{\featuredim}$, defined as $\supportfunc{\va}{\mathcal{C}} = \sup_{\weights \in \mathcal{C}} \va^{\top} \weights$. A closed convex set is fully described by its support function through linear inequalities: $\weights \in \mathcal{C}$ if and only if $\va^{\top} \weights \leq \supportfunc{\va}{\mathcal{C}}$ holds for every $\va \in \reals^{\featuredim}$ (Rockafellar, 1970, Sect. 13).
See also: convex, halfspace, supporting hyperplane.
The partial derivative (if it exists) of a real-valued function $f: \reals^{\featuredim}\rightarrow \reals$ with respect to $\weight_{\featureidx}$ (Rudin, 1976, Ch. 9).
See also: partial derivative, function, gradient.
The gradient of a differentiable real-valued function $f: \reals^{\featuredim}\rightarrow \reals$ is the vector $\nabla f(\weights) = \big( {\partial f}/{\partial \weight_{1}}, \,\ldots, \,{\partial f}/{\partial \weight_{\featuredim}} \big)^{\top} \in \reals^{\featuredim}$ (Rudin, 1976, Ch. 9).
See also: gradient, differentiable, gradient descent.
The subdifferential of a real-valued function $f: \reals^{\featuredim}\rightarrow \reals$ at $\weights$, i.e., the set of all subgradients $\va \in \reals^{\featuredim}$ satisfying $f(\weights') \geq f(\weights) + \big(\weights'-\weights\big)^{\top}\va$ for every $\weights' \in \reals^{\featuredim}$. For a convex function $f$, the subdifferential is non-empty at every interior point of the domain of $f$. The definition carries over to a real-valued function $f: \hilbertspace \rightarrow \reals$ on a Hilbert space $\hilbertspace$, with the inner product $\innerprod{\weights'-\weights}{\va}$ of $\hilbertspace$ replacing $\big(\weights'-\weights\big)^{\top}\va$ (Bertsekas, 2016, Sect. 6.3; Bauschke and Combettes, 2011, Ch. 16).
See also: subgradient, convex, Hilbert space, subgradient descent.
The distance between two elements $\featurevec, \featurevec'$ of a metric space. For the Euclidean space $\reals^{\featuredim}$, the default choice is the Euclidean norm of the difference, $\metric{\featurevec}{\featurevec'} = \normgeneric{\featurevec - \featurevec'}{2}$.
See also: distance, metric space, norm.
The boundary of a subset $\mathcal{C}$ of some metric space.
See also: boundary, metric space, decision boundary.
The identity operator.
See also: operator, linear map, function.
A vector space. Equipped with an inner product $\innerprod{\cdot}{\cdot}$, it forms an inner product space $(\vecspace, \innerprod{\cdot}{\cdot})$.
See also: vector space, inner product, Hilbert space.
A vector of length $\featuredim$, with its $\featureidx$th entry being $\feature_{\featureidx}$.
See also: vector, feature, feature vector.
The set of all vectors $\featurevec=\big(\feature_{1}, \,\ldots, \,\feature_{\featuredim}\big)^{\top}$ consisting of $\featuredim$ real-valued entries $\feature_{1}, \,\ldots, \,\feature_{\featuredim} \in \reals$.
See also: vector, feature space, Euclidean space.
A matrix with $\samplesize$ rows and $\featuredim$ columns. Bold uppercase letters denote matrices. The entry in row $\sampleidx$ and column $\featureidx$ is denoted by $A_{\sampleidx,\featureidx}$ (non-bold, italic) or equivalently $[\mA]_{\sampleidx,\featureidx}$.
See also: matrix, feature matrix, linear map.
A generalized identity matrix with $\samplesize$ rows and $\featuredim$ columns. The entries of $\mI_{\samplesize \times \featuredim} \in \reals^{\samplesize \times \featuredim}$ are equal to $1$ along the main diagonal and $0$ otherwise.
See also: matrix, linear map, projection.
A square identity matrix of size $\featuredim \times \featuredim$. If the size is clear from context, the subscript is omitted.
See also: matrix, linear map, projection.
The diagonal matrix in $\reals^{\featuredim \times \featuredim}$ whose $\featureidx$th diagonal entry is $a_{\featureidx}$ and whose off-diagonal entries are zero.
See also: matrix, eigenvalue, diagonalizable.
The Euclidean (or $\ell_{2}$) norm of the vector $\featurevec=\big(\feature_{1}, \,\ldots, \,\feature_{\featuredim}\big)^{\top} \in \reals^{\featuredim}$ defined as $\| \featurevec \|_{2} \defeq \sqrt{\sum_{\featureidx=1}^{\featuredim} \feature_{\featureidx}^{2}}$.
See also: norm, vector, Euclidean norm.
The vector in $\reals^{\featuredim}$ with each entry equal to zero.
See also: vector, nullspace, norm.
The vector in $\reals^{\featuredim}$ with each entry equal to one.
See also: vector, mean, basis.
The $\featureidx$th canonical basis vector in $\reals^{\featuredim}$, with a one in position $\featureidx$ and zeros elsewhere, i.e., $\ve^{(\featureidx)} = \big(0,\ldots,0,1,0,\ldots,0\big)^{\top}$. Subscripts on vectors index entries (components); the superscript in parentheses indexes which basis vector.
See also: basis, vector, subspace.
A generic expansion coefficient in a linear combination, such as the basis expansion $\featurevec = \sum_{\featureidx=1}^{\featuredim} \expcoeff_{\featureidx} \ve^{(\featureidx)}$; the coefficients form the vector $\boldsymbol{\expcoeff} = \big(\expcoeff_{1}, \,\ldots, \,\expcoeff_{\featuredim}\big)^{\top}$. Also used for the support-vector expansion of an support vector machine (SVM) and for kernel expansions. Not to be confused with the regularization parameter $\regparam$.
See also: basis, support vector machine, kernel.
The vector of length $\featuredim+\featuredim'$ obtained by concatenating the entries of the vector $\vv \in \reals^{\featuredim}$ with the entries of $\vw \in \reals^{\featuredim'}$.
See also: vector, feature vector, stacking.
The determinant of a square matrix $\mX \in \reals^{\featuredim \times \featuredim}$.
See also: determinant, matrix, eigenvalue.
The trace of a square matrix $\mX \in \reals^{\featuredim \times \featuredim}$.
See also: trace, matrix, eigenvalue.
The condition number of a positive semi-definite (psd) matrix $\mA$, defined as the ratio of its largest and smallest eigenvalues, $\condnumber{\mA} = \eigval{\max}/\eigval{\min} \geq 1$. Quantifies how elongated the level sets of $\featurevec^{\top} \mA \featurevec$ are; for $\mA = \featuremtx^{\top}\featuremtx$ it governs the convergence rate of gradient descent (GD) for linear regression.
See also: condition number, matrix, eigenvalue, gradient descent.
The Hadamard (element-wise) product of vectors $\va, \vb \in \reals^{\featuredim}$, yielding the vector with entries $(\va \odot \vb)_{\featureidx} = a_{\featureidx}\, b_{\featureidx}$ for $\featureidx = 1, \ldots, \featuredim$.
See also: vector, adaptive moment estimation optimizer, matrix.
Element-wise division of vectors $\va, \vb \in \reals^{\featuredim}$, yielding the vector with entries $(\va \oslash \vb)_{\featureidx} = a_{\featureidx} / b_{\featureidx}$ for $\featureidx = 1, \ldots, \featuredim$ (assuming $b_{\featureidx} \neq 0$).
See also: vector, adaptive moment estimation optimizer, matrix.
Entrywise inequality between vectors $\va, \vb \in \reals^{\featuredim}$, i.e., $a_{\featureidx} \geq b_{\featureidx}$ for $\featureidx=1,\,\ldots,\,\featuredim$.
See also: vector, convex, optimization problem.
A closed ball in some metric space that contains all points whose distance from $\featurevec$ is at most $\varepsilon$.
See also: metric space, distance, neighborhood.
A Hilbert space, i.e., a vector space that is equipped with an inner product $\innerprod{\cdot}{\cdot}$ and complete with respect to the induced norm $\normgeneric{\cdot}{\hilbertspace}$.
See also: Hilbert space, inner product, reproducing kernel Hilbert space.
The inner product between two vectors $\vu, \vv$ of a Hilbert space $\hilbertspace$. For the Euclidean space $\reals^{\featuredim}$, $\innerprod{\vu}{\vv} = \vu^{\top}\vv = \sum_{\featureidx=1}^{\featuredim} u_{\featureidx} v_{\featureidx}$.
See also: inner product, Hilbert space, kernel.
The inner product of the Hilbert space $\hilbertspace$; the subscript names the space whose inner product is meant when several spaces are in play, e.g., in the reproducing property $\hypothesis(\featurevec) = \innerprodgeneric{\hypothesis}{\kernelmap{\featurevec}{\cdot}}{\hilbertspace}$ of a reproducing kernel Hilbert space (RKHS). If the underlying Hilbert space is clear from the context, the subscript is dropped.
See also: inner product, Hilbert space, reproducing kernel Hilbert space.
The norm of a vector $\weights \in \hilbertspace$ induced by the inner product of the Hilbert space $\hilbertspace$, $\normgeneric{\weights}{\hilbertspace} = \sqrt{\innerprodgeneric{\weights}{\weights}{\hilbertspace}}$.
See also: norm, Hilbert space, reproducing kernel Hilbert space.
The random variable (RV) $\featurevec$ is distributed according to the probability distribution $\probdist$ (Billingsley, 1986; Klenke, 2020).
See also: random variable, probability distribution, independent and identically distributed.
The random variables (RVs) $x^{(1)},\,\ldots,\,x^{(\samplesize)}$ are drawn independent and identically distributed (i.i.d.) from the probability distribution $\probdist$.
See also: random variable, probability distribution, independent and identically distributed.
The expectation of an random variable (RV) $f(\datapoint)$ under the probability distribution $\probdist$. When $\probdist$ is clear from context, shortened to $\expect \{ f(\datapoint) \}$.
See also: expectation, random variable, probability distribution.
The covariance between two real-valued random variables (RVs) defined over a common probability space.
See also: covariance, random variable, probability distribution.
The covariance matrix $\covmtx{\featurevec} = \expect\big\{ \featurevec \featurevec^{\top} \big\}$ of the features $\featurevec$ (for a zero-mean feature vector).
See also: covariance, covariance matrix, feature vector.
A (joint) probability distribution of an random variable (RV) whose realizations are data points with features $\featurevec$ and label $\truelabel$.
See also: probability distribution, data point, label.
A conditional probability distribution of an random variable (RV) $\truelabel$ given (or conditioned on) the value of another RV $\featurevec$ (Bertsekas and Tsitsiklis, 2008, Sec. 3.5).
See also: conditional probability distribution, random variable, classification.
The probability of the measurable event $\genericevent$.
See also: probability, measurable, event.
The moment generating function (MGF) of an random variable (RV) $x$.
See also: moment generating function, probability distribution, expectation.
The probability density function (pdf) (for a continuous random variable (RV)) or probability mass function (pmf) (for a discrete random variable (discrete RV)) of an RV $\featurevec$, evaluated at $\va$. The superscript names the RV whose probability distribution is meant.
See also: probability density function, probability mass function, probability distribution.
A probability distribution of an random variable (RV) $\featurevec$, parameterized by a vector $\weights$. For example, $\probdist^{(\featurevec;\weights)}$ could be a multivariate normal distribution whose mean and covariance matrix are determined by $\weights$.
See also: probability distribution, parameter, probabilistic model.
The probability distribution of a Gaussian random variable (Gaussian RV) $\feature \in \reals$ with mean (or expectation) $\mu= \expect \{ \feature \}$ and variance $\sigma^{2} = \expect \big\{ ( \feature - \mu )^2 \big\}$.
See also: probability distribution, Gaussian random variable, variance.
The multivariate normal distribution of a vector-valued Gaussian random variable (Gaussian RV) $\featurevec \in \reals^{\featuredim}$ with mean (or expectation) $\meanvecgeneric= \expect \{ \featurevec \}$ and covariance matrix $\covmtxgeneric = \expect \big\{ \big( \featurevec - \meanvecgeneric \big)\big( \featurevec - \meanvecgeneric \big)^{\top} \big\}$.
See also: multivariate normal distribution, Gaussian random variable, covariance matrix.
The degree of belonging of data point $\sampleidx$ in cluster $\clusteridx$. In the fuzzy clustering formulation, the degrees of belonging are nonnegative and satisfy $\sum_{\clusteridx=1}^{\nrcluster}\dob{\clusteridx}{\sampleidx}=1$, so the degrees of belonging of one data point form a vector of the probability simplex $\simplex{\nrcluster-1}$.
See also: degree of belonging, cluster, soft clustering, probability simplex.
The probability simplex, which consists of all vectors $\vp = \big( p_{1}, \,\ldots, \,p_{\nrcluster} \big)^{\top} \in \reals^{\nrcluster}$ with nonnegative entries that sum to one, i.e., $p_{\clusteridx} \geq 0$ for $\clusteridx=1, \,\ldots, \,\nrcluster$ and $\sum_{\clusteridx=1}^{\nrcluster} p_{\clusteridx} = 1$. The superscript is the number of free entries, one fewer than the number of entries, because the last is fixed by the other $\nrcluster-1$.
See also: probability simplex, probability mass function, softmax function.
The entropy of a discrete random variable (discrete RV) $x$.
See also: entropy, discrete random variable, cross-entropy.
The Kullback–Leibler divergence (KL divergence) between two probability distributions $\probdist$ and $\probdist'$.
See also: Kullback–Leibler divergence, probability distribution, cross-entropy.
A sample space of all possible outcomes of a random experiment.
See also: sample space, event, random experiment.
An outcome of a random experiment, i.e., an element of the sample space $\samplespace$. An random variable (RV) is a measurable map that assigns to each outcome $\outcome$ a value.
See also: outcome, random experiment, random variable.
A collection of measurable subsets of a sample space $\samplespace$.
See also: $\sigma$-algebra, sample space, event.
A generic event, i.e., a measurable subset $\genericevent \in \sigmaalgebra$ of a sample space $\samplespace$. In a measure space that is not a probability space, the same symbol denotes a measurable set.
See also: event, $\sigma$-algebra, measurable, sample space.
A probability space, written as the triple it consists of: a sample space $\samplespace$, a $\sigma$-algebra $\sigmaalgebra$ of measurable subsets of $\samplespace$, and a probability distribution $\probdist$ assigning a probability $\prob{\cdot}$ to each of them.
See also: sample space, measurable, probability distribution.
A vector of sufficient statistics of a feature vector $\featurevec$: it retains everything the feature vector says about a parameter $\weights$. An exponential family is defined through such a vector.
See also: sufficient statistic, exponential family, feature transformation.
An index $\sampleidx=1, \,2, \,\ldots$ that enumerates data points.
See also: data point, dataset, sample size.
The number of data points in (i.e., the size of) a dataset.
See also: data point, dataset, sample size.
The number of pixel rows, of pixel columns, and of color channels of an image. The image is the array $\mT \in \reals^{\nrrows \times \nrcols \times \nrchannels}$ with entries $T_{i,j,c}$, and a convolutional neural network (CNN) processes it along these axes.
See also: array, convolutional neural network, feature map.
The number of feature maps delivered by a convolutional layer, and the index running over them, $\featuremapidx = 1, \ldots, \nrfeaturemaps$. One filter of the layer produces one feature map $\mA^{(\featuremapidx)}$, whose activations $A^{(\featuremapidx)}_{i,j}$ sit on a grid coarser than the $\nrrows \times \nrcols$ pixel grid.
See also: feature map, filter, convolutional neural network, class activation map.
A dataset $\dataset = \{ \datapoint^{(1)}, \,\ldots, \,\datapoint^{(\samplesize)} \}$ consisting of $\samplesize$ individual data points.
See also: dataset, data point, training set.
A training set, i.e., the data points used to learn a hypothesis $\learnthypothesis$ via empirical risk minimization (ERM). The spelled-out roman superscript $\mathrm{train}$ avoids confusion with the time index $\timeidx$.
See also: training set, dataset, test set.
A validation set, i.e., the data points used to evaluate a learned hypothesis and choose between models, kept separate from the training set.
See also: validation set, training set, test set.
A test set, i.e., data points used neither to train a model nor to choose between models; reserved for a final performance estimate.
See also: test set, training set, validation set.
The number of features that characterize a data point.
See also: feature, data point, feature space.
The $\featureidx$th feature of a data point. The first feature is denoted by $\feature_{1}$, the second feature $\feature_{2}$, and so on.
See also: feature, data point, feature vector.
The feature vector $\featurevec=\big(\feature_{1}, \,\ldots, \,\feature_{\featuredim}\big)^{\top}$ of a data point. The vector's entries are the individual features of a data point.
See also: feature vector, data point, feature.
The feature space $\featurespace$ is the set of all possible values that the features $\featurevec$ of a data point can take on.
See also: feature space, feature, data point.
The set of all data points $\datapoint \in \datapointspace$ arising in an application. A data point is treated via its raw features (cf. $\rawfeaturevec$); a feature transformation maps $\datapointspace$ into a feature space.
See also: data point, feature, feature transformation.
An alternative symbol for a vector whose entries are the individual features of a data point. Two different symbols ($\featurevec$ and $\rawfeaturevec$) are used to distinguish between raw and learned features (Jung, 2022, Ch. 9).
See also: vector, feature, data point.
The feature vector of the $\sampleidx$th data point within a dataset.
See also: feature vector, data point, dataset.
The $\featureidx$th feature of the $\sampleidx$th data point within a dataset.
See also: feature, data point, dataset.
A mini-batch (or subset) of randomly chosen data points.
See also: batch, data point, subgradient descent.
The size of (i.e., the number of data points in) a mini-batch.
See also: batch, data point, subgradient descent.
The label (or quantity of interest) of a data point.
See also: label, data point, label space.
The label of the $\sampleidx$th data point.
See also: label, data point, dataset.
The features and label of the $\sampleidx$th data point.
See also: feature, label, data point.
The set of all possible label values. Numeric label spaces ($\labelspace = \reals$) correspond to regression; discrete label spaces ($\labelspace = \{0,1\}$) to classification.
See also: label space, regression, classification.
Learning rate (or step size) used by gradient-based methods.
See also: learning rate, step size, gradient-based method.
A hypothesis map that maps the features of a data point to a prediction $\hat{\truelabel}=\hypothesis(\featurevec)$ for its label $\truelabel$.
See also: hypothesis, map, prediction.
Given two sets $\featurespace$ and $\labelspace$, the notation $\labelspace^{\featurespace}$ denotes the set of all possible hypothesis maps $\hypothesis: \featurespace \rightarrow \labelspace$.
See also: hypothesis, map, hypothesis space.
A hypothesis space or model used by a machine learning (ML) method. The hypothesis space consists of different hypothesis maps $\hypothesis: \featurespace \rightarrow \labelspace$ between which the ML method must choose.
See also: hypothesis space, model, hypothesis.
The effective dimension of a hypothesis space $\hypospace$.
See also: effective dimension, hypothesis space, Vapnik–Chervonenkis dimension.
The squared bias of a learned hypothesis $\learnthypothesis$, or its parameters. Note that $\learnthypothesis$ becomes a random variable (RV) if it is learned from data points being RVs themselves.
See also: bias, hypothesis, variance.
The variance of a learned hypothesis $\learnthypothesis$, or its parameters. Note that $\learnthypothesis$ becomes an random variable (RV) if it is learned from data points being RVs themselves.
See also: variance, hypothesis, bias.
The loss incurred by predicting the label $\truelabel$ of a data point using the prediction $\hat{\truelabel}=h(\featurevec)$. The prediction $\hat{\truelabel}$ is obtained by evaluating the hypothesis $\hypothesis \in \hypospace$ for the feature vector $\featurevec$ of the data point.
See also: loss, hypothesis, data point.
The validation error of a hypothesis $\hypothesis$, which is its average loss incurred over a validation set.
See also: validation error, loss, validation set.
The empirical risk, or average loss, incurred by the hypothesis $\hypothesis$ on a dataset $\dataset$.
The training error of a hypothesis $\hypothesis$, which is its average loss incurred over a training set.
See also: training error, loss, training set.
A discrete-time index $\timeidx=0, \,1, \,\ldots$ used to enumerate sequential events (or time instants).
See also: event, iteration, sequence.
An index $\iteridx = 0, 1, \ldots$ that enumerates the iterations of an iterative method, as in the iterates $\weights^{(\iteridx)}$. Where discrete iterations co-occur with a continuous time variable (e.g. gradient flow), the discrete index is written $\itercntr$ instead.
See also: iteration, fixed-point iteration, gradient descent.
The number of iterations performed by an iterative method, as in the final iterate $\weights^{(\nriter)}$ of a fixed-point iteration. The actual number of iterations can vary between executions of the same algorithm (e.g., with the initialization or a data-dependent stopping criterion); $\nriter$ denotes the count of the execution under consideration.
See also: iteration, convergence, gradient descent.
An index that enumerates learning tasks within a multitask learning problem.
See also: learning task, multitask learning, federated learning.
A regularization parameter that controls the amount of regularization.
See also: regularization, parameter, hyperparameter.
The $\featureidx$th eigenvalue of a positive semi-definite (psd) matrix $\mQ$, sorted in descending order, $\eigval{1} \geq \eigval{2} \geq \ldots$, so that $\eigval{1} = \eigval{\max}$ is the largest and $\eigval{\min}$ the smallest eigenvalue, as in the condition number $\condnumber{\mQ} = \eigval{\max}/\eigval{\min}$. The shorthand $\eigval{\featureidx}$ is used when the corresponding matrix is clear from context.
See also: eigenvalue, positive semi-definite, matrix.
The activation function used by an artificial neuron within an artificial neural network (ANN).
See also: activation function, artificial neuron, artificial neural network.
A decision region within a feature space: the set of all feature vectors that a classifier maps to the same prediction $\predictedlabel$.
See also: decision region, feature space, classification.
A parameter vector $\weights = \big(\weight_{1}, \,\ldots, \,\weight_{\featuredim}\big)^{\top}$ of a model, e.g., the weights of a linear model or an artificial neural network (ANN).
See also: parameter, model, weight.
The offset (also called bias) of an affine hypothesis: it shifts a hyperplane, such as the decision boundary of a linear classifier $\hypothesis(\featurevec) = \operatorname{sign}\big(\weights^{\top}\featurevec + \offset\big)$, away from the origin.
See also: hypothesis, hyperplane, decision boundary, linear classifier, support vector machine.
A hypothesis map that involves tunable model parameters $\weight_{1}, \,\ldots, \,\weight_{\featuredim}$ stacked into the vector $\weights=\big(\weight_{1}, \,\ldots, \,\weight_{\featuredim} \big)^{\top}$.
See also: hypothesis, map, model parameter.
A feature transformation $\featuretrafo: \featurespace \rightarrow \featurespace' : \featurevec \mapsto \featuretrafo\big( \featurevec \big)$ that transforms the feature vector $\featurevec$ of a data point into a new feature vector $\featurevec'= \featuretrafo\big( \featurevec \big) \in \featurespace'$.
See also: feature transformation, feature space, kernel.
Given some feature space $\featurespace$, a (real-valued) kernel is a map $\kernel: \featurespace \times \featurespace \rightarrow \reals$ that is positive semi-definite (psd).
See also: kernel, feature transformation, positive semi-definite.
The Vapnik–Chervonenkis dimension (VC dimension) of the hypothesis space $\hypospace$.
See also: Vapnik–Chervonenkis dimension, hypothesis space, effective dimension.
A data point $\datapoint = \big( \featurevec, \truelabel \big)$, characterized by its features $\featurevec$ and label $\truelabel$.
See also: data point, feature, label.
The hypothesis learned by an machine learning (ML) method, e.g., the minimizer of the training error in empirical risk minimization (ERM). It becomes an random variable (RV) when the data points used for training are themselves RVs.
See also: hypothesis, empirical risk minimization, training.
The map defined by a training method: it reads in a training set $\trainset$ and delivers a learned hypothesis $\learnthypothesis = \algomap\big(\trainset\big) \in \hypospace$, e.g., a minimizer of the training error in empirical risk minimization (ERM).
See also: training, empirical risk minimization, hypothesis.
The prediction for the label of a data point, obtained by evaluating a hypothesis $\hypothesis$ at the feature vector $\featurevec$.
See also: prediction, label, hypothesis.
The risk (or expected loss) of a hypothesis $\hypothesis$ under a probability distribution $\probdist$, i.e., $\risk{\hypothesis} = \expect \big\{ \lossfunc{\datapoint}{\hypothesis} \big\}$. The empirical risk is its estimate from a dataset.
See also: risk, loss, empirical risk.
A hypothesis that minimizes the risk over all possible hypotheses, attaining the Bayes risk.
See also: risk, Bayes risk, hypothesis.
The feature matrix (or data matrix) $\featuremtx \in \reals^{\samplesize \times \featuredim}$ whose $\sampleidx$th row is the transposed feature vector $\big(\featurevec^{(\sampleidx)}\big)^{\top}$ of the $\sampleidx$th data point.
See also: feature matrix, feature vector, linear regression.
A regularizer that measures the complexity of a hypothesis $\hypothesis$ (or its model parameters); it is added to the training error to implement regularization.
See also: regularizer, regularization, model parameter.
The parameter space, i.e., the set of all allowed values for the model parameters $\weights$ of a model.
See also: model parameter, model, hypothesis space.
The vocabulary of an large language model (LLM), i.e., the finite set of tokens from which input and output sequences are formed. The same glyph $\mathcal{V}$ also denotes the node set $\nodes$ of a graph; the intended meaning is clear from context.
See also: vocabulary, token, large language model.
The context window length, i.e., the number of tokens in the input sequence processed by a transformer. The same glyph $n$ also denotes the number of nodes $\nrnodes$ of a graph; the intended meaning is clear from context.
See also: context window, token, transformer.
A human-interpretable concept, treated as the set of data points that carry it. A concept activation vector (CAV) is the normal vector of a hyperplane separating the activations of data points that carry the concept from those that do not. The same glyph $\mathcal{C}$ also denotes a cluster; the intended meaning is clear from context.
See also: concept activation vector, explainability.
An undirected graph whose nodes $\nodeidx \in \nodes$ represent devices within a federated learning network (FL network). The undirected weighted edges $\edges$ represent connectivity between devices and statistical similarities between their datasets and learning tasks.
See also: undirected graph, device, federated learning network.
The Cartesian product of two graphs $\graph_{1}$ and $\graph_{2}$: vertices are pairs $(\nodeidx_{1}, \nodeidx_{2})$ from $\graph_{1} \times \graph_{2}$, with an edge between $(\nodeidx_{1}, \nodeidx_{2})$ and $(\nodeidx_{1}', \nodeidx_{2}')$ iff ($\nodeidx_{1} = \nodeidx_{1}'$ and $\nodeidx_{2} \sim \nodeidx_{2}'$ in $\graph_{2}$) or ($\nodeidx_{1} \sim \nodeidx_{1}'$ in $\graph_{1}$ and $\nodeidx_{2} = \nodeidx_{2}'$). The product of $\nrnodes$ path graphs $\pathgraph{d_{1}} \cartgraphprod \cdots \cartgraphprod \pathgraph{d_{\nrnodes}}$ is the $\nrnodes$-dimensional grid graph whose vertices index a rank-$\nrnodes$ array.
See also: graph, array.
The two Erdős–Rényi graph (ER graph) models on $\nrnodes$ nodes. Independent-edge model $\ergraph{\nrnodes}{p}$: each of the $\binom{\nrnodes}{2}$ possible undirected edges is included independently with probability $p \in [0, 1]$. Uniform model $\ergraph{\nrnodes}{M}$: a graph on $\nrnodes$ nodes is drawn uniformly at random from the set of all such graphs with exactly $M \in \{0, 1, \ldots, \binom{\nrnodes}{2}\}$ edges.
See also: Erdős–Rényi graph, graph.
A node that represents some device within an federated learning network (FL network). The device can access a local dataset and train a local model.
See also: device, federated learning network, local dataset.
The node set of a graph $\graph = (\nodes, \edges)$, where each node $\nodeidx \in \nodes$ represents, e.g., a device in an federated learning network (FL network). The same symbol is also used for the token vocabulary in natural language processing (NLP)/large language model (LLM) contexts, where $v \in \{1,\ldots,|\nodes|\}$ indexes a token. The intended meaning is clear from context.
See also: undirected graph, token, vocabulary, large language model.
The induced subgraph of $\graph$ using the nodes in $\cluster \subseteq \nodes$.
See also: subgraph, graph, graph clustering.
The Laplacian matrix of a graph $\graph$.
See also: Laplacian matrix, graph, eigenvalue.
The Laplacian matrix of the induced graph $\indsubgraph{\graph}{\cluster}$.
See also: Laplacian matrix, graph, subgraph.
The retarded time index: the iteration at which the most recent copy of the local model parameters $\localparams{\nodeidx'}$ available to device $\nodeidx$ at iteration $\iteridx$ was computed. Satisfies $\retardtime{\nodeidx'}{\nodeidx}{\iteridx} \leq \iteridx$; the difference $\iteridx - \retardtime{\nodeidx'}{\nodeidx}{\iteridx}$ is the communication delay.
See also: distributed algorithm, fixed-point iteration.
The neighborhood of node $\nodeidx$ in a graph $\graph$.
See also: neighborhood, graph, node degree.
The weighted node degree $\nodedegree{\nodeidx}\!\defeq\!\sum_{\nodeidx' \in \neighbourhood{\nodeidx}}\hspace{-1mm} \edgeweight_{\nodeidx,\nodeidx'}$ of node $\nodeidx$.
See also: node degree, graph, neighborhood.
The maximum weighted node degree of a graph $\graph$.
See also: maximum, node degree, graph.
The local dataset $\localdataset{\nodeidx}$ carried by node $\nodeidx\in \nodes$ of an federated learning network (FL network).
See also: local dataset, federated learning network, device.
The number of data points (i.e., the sample size) contained in the local dataset $\localdataset{\nodeidx}$ at node $\nodeidx\in \nodes$.
See also: data point, sample size, local dataset.
The features of the $\sampleidx$th data point in the local dataset $\localdataset{\nodeidx}$.
See also: feature, data point, local dataset.
The label of the $\sampleidx$th data point in the local dataset $\localdataset{\nodeidx}$.
See also: label, data point, local dataset.
The local model parameters of device $\nodeidx$ within an federated learning network (FL network).
See also: model parameter, device, federated learning network.
The local loss function used by device $\nodeidx$ to measure the usefulness of some choice $\weights$ for the local model parameters.
See also: loss function, device, model parameter.
The loss incurred by a hypothesis $\hypothesis'$ on a data point with features $\featurevec$ and label $\hypothesis\big( \featurevec\big)$ that is obtained from another hypothesis.
See also: loss, hypothesis, data point.
The vector $\bigg( \big(\weights^{(1)} \big)^{\top}, \,\ldots, \,\big(\weights^{(\nrnodes)} \big)^{\top} \bigg)^{\top} \in \reals^{\dimlocalmodel\nrnodes}$ that is obtained by vertically stacking the local model parameters $\weights^{(\nodeidx)} \in \reals^{\dimlocalmodel}$ for $\nodeidx=1,\,\ldots,\,\nrnodes$.
See also: vector, model parameter, stacking.
A hypothesis $\localhypothesis{\nodeidx}\in \localmodel{\nodeidx}$ at some node $\nodeidx$ within an federated learning network (FL network).
See also: hypothesis, federated learning network, federated learning.
A learned hypothesis $\learntlocalhypothesis{\nodeidx}\in \localmodel{\nodeidx}$, obtained by some federated learning (FL) method, at some node $\nodeidx$ within an federated learning network (FL network).
See also: hypothesis, federated learning network, federated learning.
A Markov decision process (MDP), specified by a state space $\statespace$, an action space $\actionspace$, a transition function $\transition$, a reward function $\reward$, and a discount factor $\discountfac$.
See also: Markov decision process, state space, action space.
The state space of the underlying Markov decision process (MDP), i.e., the set of all possible states $\state \in \statespace$ of an environment.
See also: state space, state, Markov decision process.
The action space of the underlying Markov decision process (MDP), i.e., the set of all actions available to the agent.
See also: action space, action, agent.
A policy $\policy$ that maps each state $\state$ to an action (or to a probability distribution over actions).
See also: policy, action, state.
An optimal policy, i.e., one that maximizes the expected return.
See also: policy, return, value iteration.
The reward $\reward$ received by the agent after taking an action in a given state.
See also: reward, action, agent.
The return $\return$, i.e., the discounted sum of rewards accumulated by the agent from some time index onward.
See also: return, reward, Markov decision process.
The discount factor $\discountfac \in [0,1]$ that down-weights future rewards when forming the return.
See also: return, reward, Markov decision process.
A generic value function $\valuefunc: \statespace \rightarrow \reals$ that assigns to each state $\state \in \statespace$ an expected return. The value function of an optimal policy is a fixed point of the Bellman operator and is computed by value iteration.
See also: state-value function, value iteration, return.
The state-value function $\statevaluefunc{\policy}(\state)$ of a policy $\policy$, i.e., the expected return when starting from state $\state$ and following $\policy$.
See also: state-value function, policy, return.
The action-value (or $q$-) function $\actionvalue{\policy}(\state,\arm)$ of a policy $\policy$, i.e., the expected return after taking action $\arm$ in state $\state$ and following $\policy$ thereafter.
See also: Q-learning, state-value function, policy.
The number of clusters in a clustering problem.
See also: clustering, cluster, $k$-means.
An index $\clusteridx = 1, \,\ldots, \,\nrcluster$ that enumerates the clusters.
See also: cluster, clustering, $k$-means.
The $\clusteridx$th cluster, i.e., the set of data points assigned to it by a hard clustering method.
See also: cluster, hard clustering, clustering.
The centroid (or cluster representative) $\clustercentroid{\clusteridx}$ of the $\clusteridx$th cluster, e.g., the mean of its data points in $k$-means.
See also: cluster centroid, $k$-means, cluster.
The proximal operator of a function $f$ evaluated at $\featurevec$.
See also: proximal operator, proximal algorithm, function.
The orthogonal projection of $\weights$ onto a closed convex set $\mathcal{C} \subseteq \reals^{\featuredim}$, i.e., the element of $\mathcal{C}$ closest to $\weights$ in the Euclidean norm: $\projection{\mathcal{C}}{\weights} = \argmin_{\weights' \in \mathcal{C}} \normgeneric{\weights - \weights'}{2}$.
See also: orthogonal projection, proximal operator, convex.
An operator whose repeated application defines a fixed-point iteration; its fixed points characterize the solutions of the underlying optimization problem.
See also: fixed point, fixed-point iteration, Banach's fixed-point theorem.
The gradient descent (GD) step operator with learning rate $\lrate$; it maps $\weights$ to $\gdstep{\lrate}(\weights) = \weights - \lrate \nabla f(\weights)$. Its fixed points are the stationary points of the objective function $f$.
See also: gradient descent, gradient step, learning rate, fixed-point iteration.
The Lipschitz constant of the gradient of a differentiable function $f$: the smallest constant satisfying $\norm{\nabla f(\weights) - \nabla f(\weights')} \le L\,\norm{\weights - \weights'}$ for all $\weights, \weights'$. Such an $f$ is also called $L$-smooth. Not to be confused with the loss function $\lossfunc{\cdot}{\cdot}$, which is always written with its arguments.
See also: Lipschitz continuity, smooth, gradient descent, convergence.
The strong convexity parameter of a function $f$: the largest $\mu > 0$ such that $f(\weights) - (\mu/2)\,\norm{\weights}^{2}$ is convex. Not to be confused with the mean $\mu$ of a scalar Gaussian random variable (Gaussian RV).
See also: convex, gradient descent, contractive operator.
The contraction factor $\contractfac \in [0,1)$ of a contractive operator; it bounds the per-step error reduction of the associated fixed-point iteration. For gradient descent (GD) on a $\mu$-strongly convex function with $L$-Lipschitz gradient and step size $\lrate \leq 1/L$, $\contractfac = 1 - \mu \lrate$.
See also: contractive operator, fixed-point iteration, condition number.