The Aalto Dictionary of Machine Learning
Full text
The A”alto Dictionary of Machine Learning Alexander Jung1, Konstantina Olioumtsevits1, Ekkehard Schnoor1, Tommi Flores Ryynänen1, Juliette Gronier2, and Salvatore Rastelli1 1Aalto University 2ENS Lyon October 5, 2025 please cite as: A. Jung, K. Olioumtsevits, E. Schnoor, T. Ryynänen, J. Gronier, and S. Rastelli, The Aalto Dictionary of Machine Learning. Espoo, Finland: Aalto University, 2025. 1
Acknowledgment This dictionary of machine learning evolved through the development and teaching of several courses, including CS-E3210 Machine Learning: Basic Principles, CS-C3240 Machine Learning, CS-E4800 Artificial Intelligence, CS-EJ3211 Machine Learning with Python, CS-EJ3311 Deep Learning with Python, CS-E4740 Federated Learning, and CS-E407507 Human-Centered Machine Learning. These courses were offered at Aalto University https: //www.aalto.fi/en , to adult learners via The Finnish Institute of Technology (FITech) https://fitech.io/en/ , and to international students through the European University Alliance Unite! https://www.aalto.fi/en/unite. We are grateful to the students who provided valuable feedback that helped shape this dictionary. Special thanks to Mikko Seesto for his meticulous proofreading. This work was supported by •the Research Council of Finland (grants 331197, 363624, 349966); •the European Union (grant 952410); •the Jane and Aatos Erkko Foundation (grant A835); • Business Finland, as part of the project Forward-Looking AI Governance in Banking and Insurance (FLAIG). 2
Contents Tools 21 Machine Learning Concepts 33 3
Lists of Symbols Sets and Functions a∈ A The object ais an element of the set A. a:= bWe use aas a shorthand for b. |A| The cardinality (i.e., number of elements) of a finite set A. A ⊆ B A is a subset of B. A ⊂ B A is a strict subset of B. A×B The Cartesian product of the sets Aand B. NThe natural numbers 1,2, . . . . RThe real numbers x[1]. R+The nonnegative real numbers x≥0. R++ The positive real numbers x > 0. {0,1}The set consisting of the two real numbers 0and 1. [0,1] The closed interval of real numbers xwith 0≤x≤1. 4
arg min w f(w) The set of minimizers for a real-valued function f (w). See also: function. S(n)The set of unit-norm vectors in Rn+1. See also: norm, vector. exp (a) The exponential function evaluated at the real number a∈R. See also: function. log aThe logarithm of the positive number a∈R++. f(·):A→B:a7→f(a) A function (or map) from a set A to a set B , which assigns to each input a∈ A a well-defined output f ( a ) ∈ B . The set A is the domain of the function f and the set B is the co-domain of f . Machine learning (ML) aims to learn a function h that maps features x of a data point to a prediction h(x)for its label y. See also: function, map, ML, feature, data point, prediction, label. epi(f)The epigraph of a real-valued function f:Rd→R. See also: epigraph, function. ∂f(w1, . . . , wd) ∂wj The partial derivative (if it exists) of a real-valued function f:Rd→Rwith respect to wj[2, Ch. 9]. See also: function. 5
∇f(w) The gradient of a differentiable real-valued function f : Rd→R is the vector ∇f (w) = ∂f/∂w1, . . . , ∂f/∂wdT∈Rd[2, Ch. 9]. See also: gradient, differentiable, function, vector. 6
Matrices and Vectors x=x1, . . . , xd)TA vector of length d, with its jth entry being xj. See also: vector. Rd The set of vectors x= x1, . . . , xdT consisting of d realvalued entries x1, . . . , xd∈R. See also: vector. Il×d A generalized identity matrix with l rows and d columns. The entries of I l×d∈Rl×d are equal to 1along the main diagonal and otherwise equal to 0. See also: matrix. Id,I A square identity matrix of size d×d . If the size is clear from context, we drop the subscript. See also: matrix. ∥x∥2 The Euclidean (or ℓ2 ) norm of the vector x= x1, . . . , xdT∈Rddefined as ∥x∥2:= qPd j=1 x2 j. See also: norm, vector. ∥x∥ Some norm of the vector x ∈Rd [3]. Unless otherwise specified, we mean the Euclidean norm ∥x∥2. See also: norm, vector. xT The transpose of a matrix that has the vector x ∈Rd as its single column. See also: matrix, vector. 7
XT The transpose of a matrix X ∈Rm×d . A square real-valued matrix X∈Rm×mis called symmetric if X=XT. See also: matrix. X−1The inverse matrix of a matrix X∈Rd×d. See also: inverse matrix, matrix. 0=0, . . . , 0TThe vector in Rdwith each entry equal to zero. See also: vector. 1=1, . . . , 1TThe vector in Rdwith each entry equal to one. See also: vector. vT,wTT The vector of length d + d′ obtained by concatenating the entries of vector v∈Rdwith the entries of w∈Rd′. See also: vector. span (B) The span of a matrix B ∈Ra×b , which is the subspace of all linear combinations of the columns of B, such that span (B) = Ba :a∈Rb⊆Ra. See also: matrix. null (A) The nullspace of a matrix A ∈Ra×b , which is the subspace of vectors a∈Rbsuch that Aa =0. See also: nullspace, matrix, vector. 8
det (C)The determinant of the matrix C. See also: determinant, matrix. A⊗BThe Kronecker product of Aand B[4]. See also: Kronecker product. 9
Et The training error of a hypothesis h , which is its average loss incurred over a training set. See also: training error, hypothesis, loss, training set. t A discrete-time index t = 0 , 1 , . . . used to enumerate sequential events (or time instants). See also: event. t An index that enumerates learning tasks within a multitask learning problem. See also: learning task, multitask learning. α A regularization parameter that controls the amount of regularization. See also: regularization, parameter. λjQ The j th eigenvalue (sorted in either ascending or descending order) of a positive semi-definite (psd) matrix Q. We also use the shorthand λjif the corresponding matrix is clear from context. See also: eigenvalue, psd, matrix. σ(·) The activation function used by an artificial neuron within an artificial neural network (ANN). See also: activation function, ANN. Rˆy A decision region within a feature space. See also: decision region, feature space. 16
w A parameter vector w= w1, . . . , wdT of a model, e.g., the weights of a linear model or an ANN. See also: parameter, vector, model, weights, linear model, ANN. h(w)(·) A hypothesis map that involves tunable model parameters w1, . . . , wdstacked into the vector w=w1, . . . , wdT. See also: hypothesis, map, model parameters, vector. ϕ(·) A feature map ϕ : X → X′ :x 7→ ϕ x that transforms the feature vector xof a data point into a new feature vector x ′ = ϕ x ∈ X′ . See also: feature map. K·,· Given some feature space X , a kernel is a map K : X ×X → C that is psd. See also: feature space, kernel, map, psd. VCdim (H) The Vapnik–Chervonenkis dimension (VC dimension) of the hypothesis space H. See also: VC dimension, hypothesis space. 17
Federated Learning G= (V,E) An undirected graph whose nodes i∈ V represent devices within a federated learning network (FL network). The undirected weighted edges E represent connectivity between devices and statistical similarities between their datasets and learning tasks. See also: graph, device, FL network, dataset, learning task. i∈ V A node that represents some device within an FL network. The device can access a local dataset and train a local model. See also: device, FL network, local dataset, local model. G(C)The induced subgraph of Gusing the nodes in C ⊆ V. L(G)The Laplacian matrix of a graph G. See also: Laplacian matrix, graph. L(C)The Laplacian matrix of the induced graph G(C). See also: Laplacian matrix, graph. N(i)The neighborhood of the node iin a graph G. See also: neighborhood, graph. d(i)The weighted node degree d(i):=Pi′∈N (i)Ai,i′of node i. See also: node degree. d(G) max The maximum weighted node degree of a graph G. See also: maximum, node degree, graph. 18
D(i) The local dataset D(i) carried by node i∈ V of an FL network. See also: local dataset, FL network. mi The number of data points (i.e., sample size) contained in the local dataset D(i)at node i∈ V. See also: data point, sample size, local dataset. x(i,r) The features of the r th data point in the local dataset D(i). See also: feature, data point, local dataset. y(i,r) The label of the r th data point in the local dataset D(i). See also: label, data point, local dataset. w(i) The local model parameters of device i within an FL network. See also: model parameters, device, FL network. Li(w) The local loss function used by device i to measure the usefulness of some choice wfor the local model parameters. See also: loss function, device, model parameters. L(d) x, hx, h′x The loss incurred by a hypothesis h′ on a data point with features xand label h x that is obtained from another hypothesis. See also: loss, hypothesis, data point, feature, label. 19
stackw(i)n i=1 The vector w (1)T, . . . , w (n)TT∈Rdn that is obtained by vertically stacking the local model parameters w(i)∈Rd, for i= 1, . . . , n. See also: vector, model parameters. 20
Tools characteristic function The characteristic function of a real-valued RV x is the function [6, Sec. 26] ϕx(t) := Eexp (jtx)with j=√−1. The characteristic function uniquely determines the probability distribution of x. See also: RV, probability distribution. continuous A function f : Rd→R is continuous at a point x ′∈Rd if for every ϵ > 0there is a δ > 0such that for all x ∈Rd with ∥x−x′∥2< δ , it holds that |f (x) −f (x ′ ) |< ϵ [2]. In other words, we can make f (x) arbitrarily close to f (x ′ )by choosing xsufficiently close to x ′ . If f is continuous at every point x ′∈Rd , then f is said to be continuous on Rd . The notion of a continuous function can be naturally extended to functions between general metric spaces [2]. See also: Euclidean space, metric. convergence TBD. convex optimization TBD. determinant The determinant det (A)of a square matrix A= a (1), . . . , a (d)∈Rd×d is a function of its columns a (1), . . . , a (d)∈Rd , i.e., it satisfies the following properties [9]: 21
•Normalized: det (I) = 1 •Multilinear: det a(1), . . . , αu+βv, . . . , a(d)=αdet a(1), . . . , u, . . . , a(d) +βdet a(1), . . . , v, . . . , a(d) •Antisymmetric: det . . . , a(j), . . . , a(j′), . . . =−det . . . , a(j′), . . . , a(j), . . . . We can interpret a matrix Aas a linear transformation on Rd . The determinant det (A)characterizes how volumes in Rd (and their orientation) are altered by this transformation (see Fig. 1) [3], [10]. In particular, det (A) > 0preserves orientation, det (A) < 0reverses orientation, and det (A) = 0 collapses volume entirely, indicating that Ais non-invertible. The determinant also satisfies det (AB) = det (A) ·det (B), and if Ais diagonalizable with eigenvalues λ1, . . . , λd , then det (A) = Qd j=1 λj [11]. For the special cases d = 2 (i.e., two-dimensional or 2-D) and d = 3 (i.e., three-dimensional or 3-D), the determinant can be interpreted as an oriented area or volume spanned by the column vectors of A. 22
x y Ax Ay det (A) A Fig. 1. We can interpret a square matrix Aas a linear transformation of Rd into itself. The determinant det (A)characterizes how this transformation alters an oriented volume. See also: eigenvalue, inverse matrix. function A function between two sets U and V assigns each element u∈ U exactly one element f(u)∈ V [2]. We write this as f:U → V :u7→ f(u) where U is the domain and V the co-domain of f . That is, a function f defines a unique output f(u)∈ V for every input u∈ U (see Fig. 2). 23
a b c 1 2 3 U V Fig. 2. A function f:{a, b, c}→{ 1 , 2 , 3 } mapping each element of the domain to exactly one element of the co-domain. Hessian Consider a function f : Rd→R for which the second-order partial derivatives exist at x ′ . Then, the Hessian ∇2f (x ′ )of f at xis defined as the matrix of second-order partial derivatives of fat x′, ∇2f(x′) = ∂2f ∂x2 1 ∂2f ∂x1∂x2··· ∂2f ∂x1∂xd ∂2f ∂x2∂x1 ∂2f ∂x2 2··· ∂2f ∂x2∂xd . . .. . ..... . . ∂2f ∂xd∂x1 ∂2f ∂xd∂x2··· ∂2f ∂x2 d . If the second-order partial derivatives are continuous in a neighborhood around x ′ , then the Hessian is a symmetric matrix, i.e., ∂2f ∂xj∂xj′ = ∂2f ∂xj′∂xj for all j, j′ [2]. If additionally f is convex, then the Hessian is a psd matrix [12]. 24
f(x) g(x) q(x)x′ Fig. 3. A function f (x)that is sufficiently smooth at a point x ′ can be locally approximated by a quadratic function q (x)which allows for a more accurate approximation compared to a linear function g(x). The Hessian ∇2f(x′)can be used to compute a quadratic function q(x) = (1/2)(x−x′)T∇2f(x′) | {z } Hessian (x−x′)+(x−x′)T∇f(x′) | {z } gradient +f(x′) that approximates flocally around x′. See also: differentiable, matrix, function, quadratic function. inverse matrix An inverse matrix A −1 is defined for a square matrix A ∈ Rn×n that is of full rank, meaning its columns are linearly independent. In this case, Ais said to be invertible, and its inverse satisfies AA−1=A−1A=I. A square matrix is invertible if and only if its determinant is non-zero. Inverse matrices are fundamental in solving systems of linear equations and in the closed-form solution of linear regression [10], [13]. The concept of an inverse matrix can be extended to matrices that are not square or does not have full rank. One may define a “left inverse” B satisfying BA =Ior a “right inverse” Csatisfying AC =I. For general 25
v w v+w αv 0 Fig. 8. A vector space V is a collection of vectors such that scaling and adding them always yields another vector in V. A common example of a vector space is the Euclidean space Rn , which is widely used in ML to represent datasets. We can also use Rn to represent, either exactly or approximately, the hypothesis space used by an ML method. Another example of a vector space, which is naturally associated with every probability space P = Ω ,R,P ( · ) , is the collection of all real-valued RVs x: Ω →R[1], [20]. See also: vector, Euclidean space, linear model, linear map. 32
Machine Learning Concepts k-fold cross-validation A method for evaluating the generalization gap of an empirical risk minimization (ERM)-based ML method. The idea is to divide dataset D evenly into k subsets (or folds) D(1),...,D(k) For fold 1 fold 2 fold 3 fold 4 fold 5 D(1) D(2) D(3) D(4) D(5) Fig. 9. In k -fold cross-validation, the available dataset D is evenly divided into k folds D(1),...,D(k) . Each fold is used once as a validation set, while the remaining k−1folds form the training set. each fold b = 1 , . . . , k , train the model on the union of all folds except D(b) and validate it on D(b) . The overall performance is obtained by averaging the validation results across all kfolds. See also: validation, validation error. absolute error loss Consider a data point with features x ∈ X and numeric label y∈R . As its name suggests, the absolute error loss incurred by a hypothesis h:X → Ris defined as L((x, y), h) = |y−h(x)|. Fig. 10 depicts the absolute error loss for a fixed data point with feature vector xand label y . It also indicates the loss values incurred by two 33
different hypotheses h′ and h′′ . Similar to the squared error loss, the absolute error loss is also a convex function of the prediction ˆy = h (x). However, in contrast to the squared error loss, the absolute error loss is non-smooth, as it is not differentiable at the optimal prediction ˆy = y . This property makes ERM-based methods using the absolute error loss computationally more demanding [16], [21]. To build intuition, it is useful to consider the two hypotheses depicted in Fig. 10. Just by inspecting the slope of L around h′ (x)and h′′ (x), it is impossible to determine whether we are very close to the optimum (at h′ ) or still far away (at h′′ ). As a result, any optimization method that is based on local approximations of the loss function (such as subgradient descent) must use a decreasing learning rate to avoid overshooting when approaching the optimum. This required decrease in learning rate tends to slow down the convergence of the optimization method. Besides the increased computational complexity, using absolute error loss in ERM can be beneficial in the presence of outliers in the training set. In contrast to the squared error loss, the slope of the absolute error loss does not increase with increasing prediction error y−h (x). As a result, the effect of introducing an outlier with large prediction error on the solution ˆ h of ERM with absolute error loss is much smaller compared with the effect on the solution of ERM with squared error loss. 34
y L((x, y), h′) h′(x)h′′(x) L((x, y), h′′) ˆy Fig. 10. For a data point with numeric label y∈R , the absolute error |y−h (x) | can be used as a loss function to guide the learning of a hypothesis h. See also: data point, feature, label, loss, ERM, subgradient descent, least absolute deviation regression. accuracy Consider data points characterized by features x ∈ X and a categorical label y that takes on values from a finite label space Y . The accuracy of a hypothesis h : X → Y , when applied to the data points in a dataset D = x (1), y(1), . . . , x (m), y(m) , is then defined as 1−(1/m)Pm r=1 L(0/1) x(r), y(r), husing the 0/1loss L(0/1) (·,·). See also: 0/1loss, loss, metric. activation The output of an artificial neuron within an ANN is referred to as its activation. In particular, the activation is obtained by applying a (typically nonlinear) activation function to a weighted sum of its inputs. See also: ANN, deep net. activation function Each artificial neuron within an ANN is assigned an activation function σ ( · )that maps a weighted combination of the neuron 35
inputs x1, . . . , xd to a single output value a = σw1x1 + . . . + wdxd . Note that each neuron is parameterized by the weights w1, . . . , wd. See also: ANN, activation, function, weights. algebraic connectivity The algebraic connectivity of an undirected graph is the second-smallest eigenvalue λ2 of its Laplacian matrix. A graph is connected if and only if λ2>0. See also: graph, eigenvalue, Laplacian matrix. algorithm An algorithm is a precise, step-by-step specification for producing an output from a given input within a finite number of computational steps [22]. For example, an algorithm to train a linear model explicitly describes how to transform a given training set into model parameters through a sequence of gradient steps. To study algorithms rigorously, we can represent (or approximate) them by different mathematical structures [23]. One approach is to represent an algorithm as a collection of possible executions. Each individual execution is then a sequence of the form input, s1, s2, . . . , sT,output. This sequence starts from an input and progresses via intermediate steps until an output is delivered. Crucially, an algorithm encompasses more than just a mapping from input to output; it also includes intermediate computational steps s1, . . . , sT. See also: linear model, training set, model parameters, gradient step, model, stochastic. application programming interface (API) An API is a formal mecha36
nism that allows software components to interact in a structured and modular way [24]. In the context of ML, APIs are commonly used to provide access to a trained ML model. Users—whether humans or machines—can submit the feature vector of a data point and receive a corresponding prediction. Suppose a trained ML model is defined as bh ( x ) := 2 x + 1. Through an API, a user can input x = 3 and receive the output bh (3) = 7 without knowledge of the detailed structure of the ML model or its training. In practice, the model is typically deployed on a server connected to the Internet. Clients send requests containing feature values to the server, which responds with the computed prediction bh (x). APIs promote modularity in ML system design, i.e., one team can develop and train the model, while another team handles integration and user interaction. Publishing a trained model via an API also offers practical advantages. For instance, the server can centralize computational resources that are required to compute predictions. Furthermore, the internal structure of the model remains hidden—which is useful for protecting intellectual property or trade secrets. However, APIs are not without risk. Techniques such as model inversion can potentially reconstruct a model from its predictions using carefully selected feature vectors. See also: ML, model, feature vector, data point, prediction, feature, model inversion. artificial intelligence (AI) AI refers to systems that behave rationally in the sense of maximizing a long-term reward. The ML-based approach to AI is to train a model to predict optimal actions. These predictions 37
are computed from observations about the state of the environment. The choice of loss function sets AI applications apart from more basic ML applications. AI systems rarely have access to a labeled training set that allows the average loss to be measured for any possible choice of model parameters. Instead, AI systems use observed reward signals to estimate the loss incurred by the current choice of model parameters. See also: ML, reinforcement learning (RL). artificial neural network (ANN) An ANN is a graphical (signal-flow) representation of a function that maps features of a data point at its input to a prediction for the corresponding label at its output. The fundamental unit of an ANN is the artificial neuron, which applies an activation function to its weighted inputs. The outputs of these neurons serve as inputs for other neurons, forming interconnected layers. See also: function, feature, data point, prediction, label, activation function, layer. attack An attack on an ML system refers to an intentional action—either active or passive—that compromises the system’s integrity, availability, or confidentiality. Active attacks involve perturbing components such as datasets (via data poisoning) or communication links between devices within an ML application. Passive attacks, such as privacy attacks, aim to infer sensitive attributes without modifying the system. Depending on their goal, we distinguish among denial-of-service attacks, backdoor attacks, and privacy attacks. See also: data poisoning, privacy attack, sensitive attribute, denial-of38
service attack, backdoor. attention Some ML applications involve data points composed of smaller units, known as tokens. For example, a sentence consists of words, an image of pixel patches, and a network of nodes. In practice, the tokens within a single data point are typically not independent of one another, but rather, each token pays attention to specific other tokens. Probabilistic models provide a principled framework for representing and analyzing such dependencies [25]. Attention mechanisms use a more direct approach without explicit reference to a probabilistic model. The idea is to represent the relationship between two tokens i and i′ using a parameterized function f(w) ( i, i′ ), where the parameters ware learned via a variant of ERM. Practical attention mechanisms differ in their precise choice of attention model f(w) ( i, i′ )as well as in the precise ERM variant used to learn the parameters w. One widely used family of attention mechanisms defines the parameters win terms of two vectors associated with each token i , i.e., a query vector q (i) and a key vector k (i′) . For a given token i with query q (i) , and another token i′ with key k (i′) , the quantity q (i)⊤ k (i′) quantifies the extent to which token iattends to (or depends on) token i′(see Fig. 11). 39
All human beings are born free and equal i q(i),k(i) i′ q(i′),k(i′) f(w)(i, i′) Fig. 11. Attention mechanisms learn a parameterized function f(w) ( i, i′ )to measure how much token i attends to token i′ . One widely used construction of f(w) ( i, i′ )uses query and key vectors, denoted by q (i) and k (i) , assigned to each token i[26]. See also: function. autoencoder An autoencoder is an ML method that simultaneously learns an encoder map h ( · ) ∈ H and a decoder map h∗ ( · ) ∈ H∗ . It is an instance of ERM using a loss computed from the reconstruction error x−h∗hx. See also: feature learning, dimensionality reduction. backdoor A backdoor attack refers to the intentional manipulation of the training process underlying an ML method. This manipulation can be implemented by perturbing the training set (i.e., through data poisoning) or via the optimization algorithm used by an ERM-based method. The goal of a backdoor attack is to nudge the learned hypothesis ˆ h toward specific predictions for a certain range of feature values. This range of feature values serves as a key (or trigger) to unlock a backdoor 40
in the sense of delivering anomalous predictions. The key xand the corresponding anomalous prediction ˆ h (x)are only known to the attacker. See also: ML, training set, data poisoning, algorithm, ERM, hypothesis, prediction, feature. backpropagation Backpropagation is an algorithm for computing the gradient ∇wf (w)of an objective function f (w)that depends on the model parameters wof an ANN. One example of such an objective function is the average loss incurred by the ANN on a batch of data points. This algorithm is a direct application of the chain rule from calculus to efficiently compute partial derivatives of the loss function with respect to the model parameters. Backpropagation consists of two consecutive phases, also illustrated in Fig. 12. The first phase includes the forward pass, where a batch of data points is fed into the ANN. The ANN processes the input through its layers using its current weights, ultimately producing a prediction at its output. The prediction of the batch is compared to the true label using a loss function, which quantifies the prediction error. The second phase includes the backward pass (i.e., backpropagation), where the error is backpropagated through the ANN layers. The obtained partial derivatives with respect to the ANN parameters w1, . . . , wd constitute the gradient ∇f (w), which can be used, in turn, to implement a gradient step. 41
obtain a deep decision tree. Boosting can be understood as a generalization of gradient-based methods for ERM using parametric models and smooth loss functions [31]. Just as GD iteratively updates model parameters to reduce the empirical risk, boosting iteratively combines (e.g., by summation) hypothesis maps to reduce the empirical risk (see Fig. 15). A widely used instance of the generic boosting idea is referred to as gradient boosting, which uses gradients of the loss function for combining the weak learners [31]. h L(z, h) h(0) h(1) h(2) h(3) Fig. 15. Boosting methods construct a sequence of hypothesis maps h(0), h(1), . . . that are increasingly strong learners (i.e., incurring a smaller loss). See also: optimization method, generalization, gradient-based method, ERM. 48
bootstrap For the analysis of ML methods, it is often useful to interpret a given set of data points D = z (1), . . . , z (m) as realizations of i.i.d. RVs drawn from a common probability distribution p (z). In practice, the probability distribution p (z)is unknown and must be estimated from D . The bootstrap approach uses the histogram of D as an estimator for p(z). See also: i.i.d., RV, probability distribution, histogram. central limit theorem (CLT) Consider a sequence of i.i.d. RVs x(r) , for r = 1 , 2 , . . . , each with mean zero and finite variance σ2> 0. The CLT states that the normalized sum s(m):= 1 √m m X r=1 x(r) converges in distribution to a Gaussian RV with mean zero and variance σ2 as m→ ∞ [32, Proposition 2.17]. One elegant way to derive the CLT is via the characteristic function of the normalized sum s(m) . Let ϕ ( t ) = Eexp jtx (with the imaginary unit j = √−1 ) be the common characteristic function of each sum and x(r) , and let ϕ(m) ( t ) denote the characteristic function of s(m) . Define an operator T acting on characteristic functions such that ϕ(m)(t) = T(ϕ(m−1))(t) := ϕt √m·ϕ(m−1) √m−1 √mt. This fixed-point iteration captures the effect of recursively adding an i.i.d. RV x (m) and rescaling. Iteratively applying T leads to convergence of ϕ(m)(t)toward the fixed point ϕ∗(t) = exp (−t2σ2/2) 49
which is the characteristic function of a Gaussian RV with mean zero and variance σ2 . Generalizations of the CLT allow for dependent or nonidentically distributed RVs [32, Sec. 2.8]. −3−2−1 1 2 3 0.5 1 ϕ(m)(t) t m= 1 m= 2 m= 3 exp (−t2/2) Fig. 16. Characteristic functions of normalized sums of i.i.d. RVs x(r)∈ {−1,1}for r= 1, . . . , m compared to the Gaussian limit. See also: RV, Gaussian RV. classification Classification is the task of determining a discrete-valued label y for a given data point, based solely on its features x. The label y belongs to a finite set, such as y∈ {− 1 , 1 } or y∈ { 1 , . . . , 19 } , and represents the category to which the corresponding data point belongs. See also: label, data point, feature. classifier A classifier is a hypothesis (i.e., a map) h (x)used to predict a label taking on values from a finite label space. We might use the function value h (x)itself as a prediction ˆy for the label. However, it is customary to use a map h ( · )that delivers a numeric quantity. The prediction is 50
then obtained by a simple thresholding step. For example, in a binary classification problem with a label space Y ∈ {− 1 , 1 } , we might use a real-valued hypothesis map h (x) ∈R as a classifier. A prediction ˆy can then be obtained via thresholding, ˆy= 1 for h(x)≥0and ˆy=−1otherwise. (1) We can characterize a classifier by its decision regions Ra , for every possible label value a∈ Y. See also: hypothesis, classification, decision region. cluster A cluster is a subset of data points that are more similar to each other than to the data points outside the cluster. The quantitative measure of similarity between data points is a design choice. If data points are characterized by Euclidean feature vectors x ∈Rd , we can define the similarity between two data points via the Euclidean distance between their feature vectors. An example of such clusters is shown in Fig. 17. 51
0 2 4 6 8 10 0 2 4 6 8 10 x1 x2 Clusters of Data Points Cluster 1 Cluster 2 Cluster 3 Fig. 17. Illustration of three clusters in a 2-D feature space. Each cluster groups data points that are more similar to each other than to those in other clusters, based on the Euclidean distance. See also: data point, feature vector, feature space. cluster centroid Clustering methods decompose a given dataset into few clusters. Different clustering methods use different representations for these clusters. If data points are characterized by numerical feature vectors x ∈Rd , we can use some vector µ∈Rd , referred to as cluster centroid, to represent a cluster. For example, if a cluster consists of a set of data points, we use the average of their feature vectors as a cluster centroid. However, there are also other choices for how to construct a 52
cluster centroid. See also: clustering, feature vector, k-means. clustered federated learning (CFL) CFL trains local models for the devices in a federated learning (FL) application by using a clustering assumption, i.e., the devices of an FL network form clusters. Two devices in the same cluster generate local datasets with similar statistical properties. CFL pools the local datasets of devices in the same cluster to obtain a training set for a cluster-specific model. Generalized total variation minimization (GTVMin) clusters devices implicitly by enforcing approximate similarity of model parameters across well-connected nodes of the FL network. See also: FL, clustering assumption, FL network, cluster, graph clustering. clustering Clustering methods decompose a given set of data points into a few subsets, which are referred to as clusters. Each cluster consists of data points that are more similar to each other than to data points outside the cluster. Different clustering methods use different measures for the similarity between data points and different forms of cluster representations. The clustering method k -means uses the average feature vector of a cluster (i.e., the cluster mean) as its representative. A popular soft clustering method based on Gaussian mixture model (GMM) represents a cluster by a multivariate normal distribution. See also: cluster, k-means, soft clustering, GMM. clustering assumption The clustering assumption postulates that data 53
points in a dataset form a (small) number of groups or clusters. Data points in the same cluster are more similar to each other than those outside the cluster [33]. We obtain different clustering methods by using different notions of similarity between data points. See also: clustering, data point, dataset, cluster. computational aspects By computational aspects of an ML method, we mainly refer to the computational resources required for its implementation. For example, if an ML method uses iterative optimization techniques to solve ERM, then its computational aspects include: 1) how many arithmetic operations are needed to implement a single iteration (i.e., a gradient step); and 2) how many iterations are needed to obtain useful model parameters. One important example of an iterative optimization technique is GD. See also: ML, ERM, gradient step, model parameters, GD. concentration inequality An upper bound on the probability that an RV deviates more than a prescribed amount from its expectation [34]. See also: probability, RV, expectation. concept activation vector (CAV) Consider a deep net, consisting of several hidden layers, trained to predict the label of a data point from its feature vector. One way to explain the behavior of the trained deep net is by using the activations of a hidden layer as a new feature vector z. We then probe the geometry of the resulting new feature space by applying the deep net to data points that represent a specific concept C . By applying the deep net also to data points that do not belong to this 54
concept, we can train a binary linear classifier g (z)that distinguishes between concept and non-concept data points based on the activations of the hidden layer. The resulting decision boundary is a hyperplane whose normal vector is the CAV for the concept C. See also: deep net, linear model, trustworthy artificial intelligence (trustworthy AI), interpretability, transparency. condition number The condition number κ (Q) ≥ 1of a positive definite matrix Q ∈Rd×d is the ratio α/β between the largest α and the smallest β eigenvalue of Q. The condition number is useful for the analysis of ML methods. The computational complexity of gradient-based methods for linear regression crucially depends on the condition number of the matrix Q=XX T , with the feature matrix Xof the training set. Thus, from a computational perspective, we prefer features of data points such that Qhas a condition number close to 1. See also: matrix, eigenvalue, ML, gradient-based method, linear regression, feature matrix, training set, feature, data point. confusion matrix Consider data points characterized by features xand corresponding labels y . The labels take on values in a finite label space Y = { 1 , . . . , k} . For a given hypothesis h , the confusion matrix is a k×k matrix where each row corresponds to a different value of the true label y∈ Y and each column to a different value of the prediction h (x) ∈ Y . The ( c, c′ )th entry of the confusion matrix represents the fraction of data points with a true label y = c that are predicted as h (x) = c′ . The main diagonal of the confusion matrix contains the fractions of correctly 55
classified data points (i.e., those for which y = h (x)). The off-diagonal entries contain the fractions of data points that are misclassified by h . See also: label, label space, hypothesis, matrix, classification. connected graph An undirected graph G = (V,E) is connected if every non-empty subset V′⊂ V has at least one edge connecting it to V \V′ . See also: graph. contraction operator An operator F : Rd→Rd is a contraction if, for some κ∈[0,1), ∥Fw−Fw′∥2≤κ∥w−w′∥2holds for any w,w′∈Rd. convex A subset C ⊆ Rd of the Euclidean space Rd is referred to as convex if it contains the line segment between any two points x , y ∈C in that set. A function f : Rd→R is convex if its epigraph w T, tT∈Rd+1 : t≥f (w) } is a convex set [12]. We illustrate one example of a convex set and a convex function in Fig. 18. w w′ C (a) f(w) (b) Fig. 18. (a) A convex set C ⊆ Rd. (b) A convex function f:Rd→R. See also: Euclidean space, function, epigraph. 56
convex clustering Consider a dataset x (1), . . . , x (m)∈Rd . Convex clustering learns vectors w(1), . . . , w(m)by minimizing m X r=1 x(r)−w(r) 2 2+αX i,i′∈V w(i)−w(i′) p. Here, ∥u∥p := Pd j=1 |uj|p1/p denotes the p -norm (for p≥ 1). It turns out that many of the optimal vectors b w(1), . . . , b w(m) coincide. A cluster then consists of those data points r∈ { 1 , . . . , m} with identical b w(r)[35], [36]. See also: dataset, convex, clustering, vector, norm, cluster, data point. Courant–Fischer–Weyl min–max characterization Consider a psd matrix Q ∈Rd×d with eigenvalue decomposition (EVD) (or spectral decomposition), i.e., Q= d X j=1 λju(j)u(j)T. Here, we use the ordered (in ascending order) eigenvalues λ1≤. . . ≤λn. The Courant–Fischer–Weyl min–max characterization [3, Th. 8.1.2] represents the eigenvalues of Qas the solutions to certain optimization problems. See also: psd, matrix, EVD, eigenvalue, optimization problem. covariance The covariance between two real-valued RVs x and y , defined on a common probability space, measures their linear dependence. It is defined as cov (x, y) = Ex−E{x}y−E{y}. 57
as humans or animals) or abstract objects (such as numbers). For illustration, Fig. 22 depicts a dataset whose data points are cows. Fig. 22. A cow herd somewhere in the Alps. Quite often, an ML engineer does not have direct access to the underlying dataset. For instance, accessing the dataset in Fig. 22 would require visiting the cow herd. In practice, we work with a more convenient representation (or approximation) of the dataset. Various mathematical models have been developed for this purpose [45], [46], [47], [48]. One of the most widely used is the relational model, which organizes data as a table (or relation) [49], [45]. A table consists of rows and columns: each row corresponds to a single data point, while each column represents a specific attribute of a data point. ML methods typically interpret these attributes as features or as a label of a data point. As an illustration, Table I shows a relational representation of the dataset from Fig. 22. In the relational model, the order of rows is immaterial, and each attribute (column) is associated with a domain that specifies the set of admissible values. In ML applications, these attribute domains correspond to the feature space and the label space. 64
TABLE I A Relation (or Table) That Represents the Dataset in Fig. 22 Name Weight Age Height Stomach temperature Zenzi 100 4 100 25 Berta 140 3 130 23 Resi 120 4 120 31 While the relational model is useful for the study of many ML applications, it may be insufficient regarding the requirements for trustworthy AI. Modern approaches like datasheets for datasets provide more comprehensive documentation, including details about the data collection process, intended use, and other contextual information [50]. See also: data point, data, feature, sample, feature space, label space. decision boundary Consider a hypothesis map h that reads in a feature vector x ∈Rd and delivers a value from a finite set Y . The decision boundary of h is the set of vectors x ∈Rd that lie between different decision regions. More precisely, a vector xbelongs to the decision boundary if and only if each neighborhood { x ′ : ∥ x − x ′∥ ≤ ε} , for any ε > 0, contains at least two vectors with different function values. See also: hypothesis, map, feature vector, vector, decision region, neighborhood, function. decision region Consider a hypothesis map h that delivers values from a finite set Y . For each label value (i.e., category) a∈ Y , the hypothesis h determines a subset of feature values x ∈ X that result in the same 65
output h (x) = a . We refer to this subset as a decision region of the hypothesis h. See also: hypothesis, map, label, feature. decision tree A decision tree is a flowchart-like representation of a hypothesis map h . More formally, a decision tree is a directed graph containing a root node that reads in the feature vector xof a data point. The root node then forwards the data point to one of its child nodes based on some elementary test on the features x. If the receiving child node is not a leaf node, i.e., it has child nodes itself, it represents another test. Based on the test result, the data point is forwarded to one of its descendants. This testing and forwarding of the data point is continued until the data point ends up in a leaf node without any children. See Fig. 23 for visual illustrations. 66
∥x−u∥ ≤ ε? h(x) = ˆy1∥x−v∥ ≤ ε? h(x) = ˆy2h(x) = ˆy3 no yes no yes (a) ˆy3 ˆy2 ˆy1 u v (b) Fig. 23. (a) A decision tree is a flowchart-like representation of a piecewise constant hypothesis h : X → R . Each piece is a decision region Rˆy := x ∈ X : h (x) = ˆy . The depicted decision tree can be applied to numeric feature vectors, i.e., X ⊆ Rd . It is parameterized by the threshold ε > 0and the vectors u , v ∈Rd . (b) A decision tree partitions the feature space X into decision regions. Each decision region Rˆy⊆X corresponds to a specific leaf node in the decision tree. See also: decision region. deep net A deep net is an ANN with a (relatively) large number of hidden layers. Deep learning is an umbrella term for ML methods that use a deep net as their model [51]. See also: ANN, layer, ML, model. degree of belonging Degree of belonging is a number that indicates the extent to which a data point belongs to a cluster [8, Ch. 8]. The degree of belonging can be interpreted as a soft cluster assignment. 67
Soft clustering methods can encode the degree of belonging with a real number in the interval [0 , 1]. Hard clustering is obtained as the extreme case when the degree of belonging only takes on values 0or 1. See also: data point, cluster, soft clustering, hard clustering. denial-of-service attack A denial-of-service attack aims (e.g., via data poisoning) to steer the training of a model such that it performs poorly for typical data points. See also: attack, data poisoning, model, data point. density-based spatial clustering of applications with noise (DBSCAN) DBSCAN refers to a clustering algorithm for data points that are characterized by numeric feature vectors. Like k -means and soft clustering via GMM, DBSCAN also uses the Euclidean distances between feature vectors to determine the clusters. However, in contrast to k -means and GMM, DBSCAN uses a different notion of similarity between data points. DBSCAN considers two data points as similar if they are connected via a sequence (i.e., path) of nearby intermediate data points. Thus, DBSCAN might consider two data points as similar (and therefore belonging to the same cluster) even if their feature vectors have a large Euclidean distance. See also: clustering, k-means, GMM, cluster, graph. device A physical system that can store and process data. In the context of ML, the term typically refers to a computer capable of reading data points from different sources and using them to train an ML model [52]. See also: data, ML, data point, model. 68
differentiable A real-valued function f : Rd→R is differentiable if it can be approximated locally at any point by a linear function. The local linear approximation at the point xis determined by the gradient ∇f (x)[2]. See also: function, gradient. differential entropy For a real-valued RV x ∈Rd with a probability density function (pdf) p(x), the differential entropy is defined as [42] h(x) := −Zp(x) log p(x)dx. Differential entropy can be negative and lacks some properties of entropy for discrete-valued RVs, such as invariance under a change of variables [42]. Among all RVs with a given mean µ and covariance matrix Σ, h(x)is maximized by x∼ N (µ,Σ). See also: uncertainty, probabilistic model. differential privacy (DP) Consider some ML method A that reads in a dataset (e.g., the training set used for ERM) and delivers some output A ( D ). The output could be either the learned model parameters or the predictions for specific data points. DP is a precise measure of privacy leakage incurred by revealing the output. Roughly speaking, an ML method is differentially private if the probability distribution of the output A ( D )remains largely unchanged if the sensitive attribute of one data point in the training set is changed. Note that DP builds on a probabilistic model for an ML method, i.e., we interpret its output A ( D )as the realization of an RV. The randomness in the output can be ensured by intentionally adding the realization of an auxiliary RV (i.e., adding noise) to the output of the ML method. 69
See also: privacy leakage, sensitive attribute, privacy attack, privacy funnel. dimensionality reduction Dimensionality reduction refers to methods that learn a transformation h : Rd→Rd′ of a (typically large) set of raw features x1, . . . , xd into a smaller set of informative features z1, . . . , zd′ . Using a smaller set of features is beneficial in several ways: • Statistical benefit: It typically reduces the risk of overfitting, as reducing the number of features often reduces the effective dimension of a model. • Computational benefit: Using fewer features means less computation for the training of ML models. As a case in point, linear regression methods need to invert a matrix whose size is determined by the number of features. • Visualization: Dimensionality reduction is also instrumental for data visualization. For example, we can learn a transformation that delivers two features z1, z2 , which we can use, in turn, as the coordinates of a scatterplot. Fig. 24 depicts the scatterplot of handwritten digits that are placed using transformed features. Here, the data points are naturally represented by a large number of greyscale values (one value for each pixel). 70
z1 z2 3 81 6 9 7 2 Fig. 24. Example of dimensionality reduction: High-dimensional image data (e.g., high-resolution images of handwritten digits) embedded into 2-D using learned features (z1, z2)and visualized in a scatterplot. See also: overfitting, effective dimension, model, scatterplot. discrepancy Consider an FL application with networked data represented by an FL network. FL methods use a discrepancy measure to compare hypothesis maps from local models at nodes i, i′ , connected by an edge in the FL network. See also: FL, FL network, local model. distributed algorithm A distributed algorithm is an algorithm designed for a special type of computer, i.e., a collection of interconnected computing devices (or nodes). These devices communicate and coordinate their local computations by exchanging messages over a network [53], [54]. Unlike a classical algorithm, which is implemented on a single device, a distributed algorithm is executed concurrently on multiple devices with computational capabilities. Similar to a classical algorithm, a 71
distributed algorithm can be modeled as a set of potential executions. However, each execution in the distributed setting involves both local computations and message-passing events. A generic execution might look as follows: Node 1: input1, s(1) 1, s(1) 2, . . . , s(1) T1,output1; Node 2: input2, s(2) 1, s(2) 2, . . . , s(2) T2,output2; . . . Node N: inputN, s(N) 1, s(N) 2, . . . , s(N) TN,outputN. Each device i starts from its own local input and performs a sequence of intermediate computations s(i) k at discrete-time instants k = 1 , . . . , Ti . These computations may depend on both the previous local computations at the device and the messages received from other devices. One important application of distributed algorithms is in FL where a network of devices collaboratively trains a personal model for each device. See also: algorithm, device, event, FL, model. dual norm Every norm ∥·∥ defined on a Euclidean space Rd has an associated dual norm, which is denoted by ∥·∥∗ and defined as ∥y∥∗ := sup∥x∥≤1 y T x. The dual norm measures the largest possible inner product between yand any vector in the unit ball of the original norm. For further details, see [12, Sec. A.1.6]. See also: norm, Euclidean space, vector. edge weight Each edge {i, i′} of an FL network is assigned a nonnegative edge weight Ai,i′≥ 0. A zero edge weight Ai,i′ = 0 indicates the absence 72
of an edge between nodes i, i′∈ V. See also: FL network. effective dimension The effective dimension deff (H) of an infinite hypothesis space H is a measure of its size. Loosely speaking, the effective dimension is equal to the effective number of independent tunable model parameters. These parameters might be the coefficients used in a linear map or the weights and bias terms of an ANN. See also: hypothesis space, model parameters, ANN. eigenvalue We refer to a number λ∈R as an eigenvalue of a square matrix A ∈Rd×d if there exists a nonzero vector x ∈Rd\ { 0 } such that Ax =λx. See also: matrix, vector. eigenvalue decomposition (EVD) The EVD for a square matrix A ∈ Rd×dis a factorization of the form A=VΛV−1. The columns of the matrix V= v (1), . . . , v (d) are the eigenvectors of the matrix V. The diagonal matrix Λ= diagλ1, . . . , λdcontains the eigenvalues λj corresponding to the eigenvectors v (j) . Note that the above decomposition exists only if the matrix Ais diagonalizable. See also: matrix, eigenvector, eigenvalue. eigenvector An eigenvector of a matrix A ∈Rd×d is a nonzero vector x∈Rd\{0}such that Ax =λxwith some eigenvalue λ. See also: matrix, vector, eigenvalue. 73
mizing P ( D;w ). However, the resulting optimization problem might be computationally challenging. EM approximates the maximum likelihood estimator by introducing a latent RV zsuch that maximizing P ( D,z;w ) would be easier [30], [58], [59]. Since we do not observe z, we need to estimate it from the observed dataset D using a conditional expectation. The resulting estimate bz is then used to compute a new estimate b w by solving maxwP ( D,bz;w ). The crux is that the conditional expectation bz depends on the model parameters b w , which we have updated based on bz . Thus, we have to recalculate bz , which, in turn, results in a new choice b w for the model parameters. In practice, we repeat the computation of the conditional expectation (i.e., the E-step) and the update of the model parameters (i.e., the M-step) until some stopping criterion is met. See also: probabilistic model, maximum likelihood, optimization problem. expert ML aims to learn a hypothesis h that accurately predicts the label of a data point based on its features. We measure the prediction error using some loss function. Ideally, we want to find a hypothesis that incurs minimal loss on any data point. We can make this informal goal precise via the i.i.d. assumption and by using the Bayes risk as the baseline for the (average) loss of a hypothesis. An alternative approach to obtaining a baseline is to use the hypothesis h′ learned by an existing ML method. We refer to this hypothesis h′ as an expert [60]. Regret minimization methods learn a hypothesis that incurs a loss comparable to the best expert [60], [61]. See also: loss function, baseline, regret. 80
explainability We define the (subjective) explainability of an ML method as the level of simulatability [62] of the predictions delivered by an ML system to a human user. Quantitative measures for the (subjective) explainability of a trained model can be constructed by comparing its predictions with the predictions provided by a user on a test set [62], [63]. Alternatively, we can use probabilistic models for data and measure the explainability of a trained ML model via the conditional (or differential) entropy of its predictions, given the user’s predictions [64], [65]. See also: trustworthy AI, regularization. explainable empirical risk minimization (EERM) EERM is an instance of structural risk minimization (SRM) that adds a regularization term to the average loss in the objective function of ERM. The regularization term is chosen to favor hypothesis maps that are intrinsically explainable for a specific user. This user is characterized by their predictions provided for the data points in a training set [63]. See also: SRM, regularization, ERM, training set. explainable machine learning (XML) XML methods aim to complement each prediction with an explanation of how the prediction has been obtained. The construction of an explicit explanation might not be necessary if the ML method uses a sufficiently simple (or interpretable) model [66]. See also: prediction, explanation, ML, model. explanation One approach to enhance the transparency of an ML method for its human user is to provide an explanation alongside the predictions 81
delivered by the method. Explanations can take different forms. For instance, they may consist of human-readable text or quantitative indicators, such as feature importance scores for the individual features of a given data point [67]. Alternatively, explanations can be visual—for example, intensity maps that highlight image regions that drive the prediction [68]. Fig. 28 illustrates two types of explanations. The first is a local linear approximation g (x)of a nonlinear trained model ˆ h (x) around a specific feature vector x ′ , as used in the method LIME. The second form of explanation depicted in the figure is a sparse set of predictions ˆ h (x (1) ) ,ˆ h (x (2) ) ,ˆ h (x (3) )at selected feature vectors, offering concrete reference points for the user. ˆ h(x) g(x) x′ x(1) x(2) x(3) Fig. 28. A trained model ˆ h (x)can be explained locally at some point x ′ by a linear approximation g (x). For a differentiable ˆ h (x), this approximation is determined by the gradient ∇ˆ h (x ′ ). Another form of explanation could be the function values ˆ hx(r)for r= 1,2,3. See also: ML, prediction, feature, data point, classification. feature A feature of a data point is one of its properties that can be measured or computed easily without the need for human supervision. For exam82
x1 x2 Fig. 29. An audio signal (blue waveform) and its discretized signal samples (red dots) which can be used as its features x1, . . . , xd. ple, if a data point is a digital image (e.g., stored as a .jpeg file), then we could use the red–green–blue (RGB) intensities of its pixels as features. Another example is shown in Fig. 29, where the the signal samples of a finite-duration audio signal are used as its features. Domain-specific synonyms for the term feature are "covariate," "explanatory variable," "independent variable," "input (variable)," "predictor (variable)," or "regressor" [69], [70], [37]. See also: data point. feature learning Consider an ML application with data points characterized by raw features x ∈ X . Feature learning refers to the task of learning a map Φ:X → X′:x7→ x′ that reads in the features x ∈ X of a data point and delivers new features x ′∈ X′ from a new feature space X′ . Different feature learning methods are obtained for different design choices of X,X′ , for a hypothesis space H of potential maps Φ, and for a quantitative measure of the usefulness of a specific Φ ∈ H . For example, principal component analysis (PCA) 83
uses X:= Rd,X′:= Rd′with d′< d, and a hypothesis space H:= Φ:Rd→Rd′:x′:=Fx with some F∈Rd′ ×d. PCA measures the usefulness of a specific map Φ(x) = Fx by the minimum linear reconstruction error incurred on a dataset such that min G∈Rd×d′ m X r=1 GFx(r)−x(r) 2 2. See also: feature, feature space, hypothesis space, PCA. feature map A feature map refers to a function Φ:X → X′,x7→ x′ that transforms a feature vector x ∈ X of a data point into a new feature vector x ′∈ X′ , where X′ is typically different from X . The transformed representation x ′ is often more useful than the original x. For instance, the geometry of data points may become more linear in X′ , allowing the application of a linear model to x ′ . This idea is central to the design of kernel methods [71]. Other benefits of using a feature map include reducing overfitting and improving interpretability [72]. A common use case is data visualization, where a feature map with two output dimensions allows the representation of data points in a 2-D scatterplot. Some ML methods employ trainable feature maps, whose parameters are learned from data. An example is the use of hidden layers in a deep net, which act as successive feature maps [73]. A principled way to train a feature map is through ERM, using a loss 84
function that measures reconstruction quality, e.g., L = ∥ x −r (x ′ ) ∥2 , where r ( · )is a trainable map that attempts to reconstruct xfrom the transformed feature vector x′. See also: feature, map, kernel method, feature learning, PCA. feature matrix Consider a dataset D with m data points with feature vectors x (1), . . . , x (m)∈Rd . It is convenient to collect the individual feature vectors into a feature matrix X:= x (1), . . . , x (m)T of size m×d. See also: dataset, data point, feature vector, feature, matrix. feature space The feature space of a given ML application or method is constituted by all potential values that the feature vector of a data point can take on. For data points described by a fixed number d of numerical features, a common choice for the feature space is the Euclidean space Rd . However, the mere presence of d numeric features does not imply that Rd is the most appropriate representation of the feature space. Indeed, the numerical features might be assigned to data points in a largely arbitrary or random manner, resulting in data points that are randomly scattered throughout Rd without any meaningful geometric structure. Feature learning methods try to learn a transformation of the original (potentially non-numeric) features to ensure a more meaningful arrangement of data points in Rd . Three examples of feature spaces are shown in Fig. 30. 85
x1 x(1)x(2) x(3) X(1) (a) x(1) x(2) x(3) X(2) (b) x(1) x(2) x(3) x(4) X(3) (c) Fig. 30. Three different feature spaces. (a) A linear space X(1) = R . (b) A bounded convex set X(2) ⊆R2 . (c) A discrete space X(3) whose elements are nodes of an undirected graph. See also: feature vector, Euclidean space. feature vector Feature vector refers to a vector x= x1, . . . , xdT whose entries are individual features x1, . . . , xd . Many ML methods use feature vectors that belong to some finite-dimensional Euclidean space Rd . For some ML methods, however, it can be more convenient to work with feature vectors that belong to an infinite-dimensional vector space (e.g., see kernel method). See also: feature, vector, ML, Euclidean space, vector space. federated averaging (FedAvg) FedAvg refers to a family of iterative FL algorithms. It uses a server-client setting and alternates between clientwise local models retraining, followed by the aggregation of updated model parameters at the server [74]. The local update at client i = 1 , . . . , n 86
at time k starts from the current model parameters w (k) provided by the server and typically amounts to executing few iterations of SGD. After completing the local updates, they are aggregated by the server (e.g., by averaging them). Fig. 31 illustrates the execution of a single iteration of FedAvg. broadcast local update aggregate . . . w(k)w(k) . . . w(k,1) w(k,n) w(k+1) . . . w(k,1) w(k,n) Fig. 31. Illustration of a single iteration of FedAvg, which consists of broadcasting model parameters by the server, performing local updates at clients, and aggregating the updates by the server. See also: FL, algorithm, local model, SGD. federated gradient descent (FedGD) An FL distributed algorithm that can be implemented as message passing across an FL network. See also: FL, distributed algorithm, FL network, gradient step, gradientbased method. federated learning (FL) FL is an umbrella term for ML methods that train models in a collaborative fashion using decentralized data and computation. See also: ML, model, data. 87
federated learning network (FL network) An FL network consists of an undirected weighted graph G . The nodes of G represent devices that can access a local dataset and train a local model. The edges of G represent communication links between devices as well as statistical similarities between their local datasets. A principled approach to train the local models is GTVMin. The solutions of GTVMin are local model parameters that optimally balance the loss incurred on local datasets with their discrepancy across the edges of G. See also: FL, graph, device, GTVMin. federated proximal (FedProx) FedProx refers to an iterative FL algorithm that alternates between separately training local models and combining the updated local model parameters. In contrast to FedAvg, which uses SGD to train local models, FedProx uses a proximal operator for the training [75]. See also: FL, algorithm, local model, model parameters, FedAvg, SGD, proximal operator. federated relaxed (FedRelax) An FL distributed algorithm. See also: FL, distributed algorithm. federated stochastic gradient descent (FedSGD) An FL distributed algorithm that can be implemented as message passing across an FL network. See also: FL, distributed algorithm, FL network, gradient step, gradientbased method, SGD. Finnish Meteorological Institute (FMI) The FMI is a government agency 88
responsible for gathering and reporting weather data in Finland. See also: data. fixed-point iteration A fixed-point iteration is an iterative method for solving a given optimization problem. It constructs a sequence w (0), w (1), . . . by repeatedly applying an operator F, i.e., w(k+1) =Fw(k), for k= 0,1, . . . . (2) The operator F is chosen such that any of its fixed points is a solution b w to the given optimization problem. For example, given a differentiable and convex function f (w), the fixed points of the operator F :w 7→ w − ∇f (w)coincide with the minimizers of f (w). In general, for a given optimization problem with solution b w , there are many different operators F whose fixed points are b w . Clearly, we should use an operator Fin (2) that reduces the distance to a solution such that w(k+1) −b w 2 | {z } (2) =∥Fw(k)−F b w∥2 ≤ w(k)−b w 2. Thus, we require F to be at least non-expansive, i.e., the iteration (2) should not result in worse model parameters that have a larger distance to a solution b w . Furthermore, each iteration (2) should also make some progress, i.e., reduce the distance to a solution b w . This requirement can be made precise using the notion of a contraction operator [76], [77]. The operator Fis a contraction operator if, for some κ∈[0,1), ∥Fw−Fw′∥2≤κ∥w−w′∥2holds for any w,w′. 89
much if we slightly change the features xof a data point z. For example, an object detector trained on smartphone photos should still detect the object if a few random pixels are masked [84]. Similarly, it should deliver the same result if we rotate the object in the image [73]. See Fig. 34 for a visual illustration. p(z) z(1) z(2) ˆ h Fig. 34. Two data points z (1), z (2) that are used as a training set to learn a hypothesis ˆ h via ERM. We can evaluate ˆ h outside D(train) either by an i.i.d. assumption with some underlying probability distribution p (z)or by perturbing the data points. See also: ERM, i.i.d. assumption, overfitting, validation. generalization gap Generalization gap is the difference between the performance of a trained model on the training set D(train) and its performance on data points outside D(train) . We can make this notion precise by using a probabilistic model that allows us to compute the risk of a trained model as the expected loss. However, the probability distribution underlying this expectation is typically unknown and needs to be somehow estimated. Validation techniques use different constructions 96
of a validation set, which is different from the training set, to estimate the generalization gap. See also: generalization, validation, ERM, loss function. generalized total variation (GTV) GTV is a measure of the variation of trained local models h(i) (or their model parameters w (i) ) assigned to the nodes i = 1 , . . . , n of an undirected weighted graph G with edges E . Given a measure d(h,h′) for the discrepancy between hypothesis maps h, h′, the GTV is X {i,i′}∈E Ai,i′d(h(i),h(i′)). Here, Ai,i′>0denotes the weight of the undirected edge {i, i′} ∈ E. See also: local model, model parameters, graph, discrepancy, hypothesis, map. generalized total variation minimization (GTVMin) GTVMin is an instance of regularized empirical risk minimization (RERM) using the GTV of local model parameters as a regularizer [85]. See also: RERM, GTV, regularizer. geometric median (GM) The GM of a set of input vectors x (1), . . . , x (m) in Rd is a point z ∈Rd that minimizes the sum of distances to the vectors [12] such that z∈arg min y∈Rd m X r=1 y−x(r) 2.(3) Fig. 35 illustrates a fundamental property of the GM: If zdoes not coincide with any of the input vectors, then the unit vectors pointing 97
from zto each x (r) must sum to zero—this is the zero-subgradient (optimality) condition for (3) . It turns out that the solution to (3) cannot be arbitrarily pulled away from trustworthy input vectors as long as they are the majority [86, Th. 2.2]. z x(1) x(2) clean x(2)−z ∥x(2)−z∥2 perturbed x(3) Fig. 35. Consider a solution zof (3) that does not coincide with any of the input vectors. The optimality condition for (3) requires that the unit vectors from zto the input vectors sum to zero. See also: vector, subgradient. gradient For a real-valued function f : Rd→R :w 7→ f (w), if a vector g exists such that limw→w′f(w)−f(w′) + gT(w−w′)/∥w−w′∥ = 0, it is referred to as the gradient of f at w ′ . If it exists, the gradient is unique and denoted by ∇f(w′)or ∇f(w)w′[2]. See also: function, vector. gradient descent (GD) GD is an iterative method for finding the minimum of a differentiable function f : Rd→R . GD generates a sequence of estimates w (0), w (1), w (2), . . . that (ideally) converge to a minimum of f . At each iteration k , GD refines the current estimate w (k) by taking a step in the direction of the steepest descent of a local linear approximation. 98
This direction is given by the negative gradient ∇f (w (k) )of the function fat the current estimate w(k). The resulting update rule is given by w(k+1) =w(k)−η∇f(w(k))(4) where η > 0is a suitably small step size. For a suitably choosen step size η , the update typically reduces the function value, i.e., f (w (k+1) ) < f(w(k)). Fig. 36 illustrates a single GD step. ∆wT∇f(w(k)) −η∇f(w(k)) ∆w w f(w) ww(k) w(k+1) 1 2 3 4 Fig. 36. A single gradient step (4) toward the minimizer wof f(w). See also: minimum, differentiable, gradient, step size, gradient step. gradient step Given a differentiable real-valued function f ( · ) : Rd→R and a vector w ∈Rd , the gradient step updates wby adding the scaled negative gradient ∇f(w)to obtain the new vector (see Fig. 37) b w:= w−η∇f(w).(5) Mathematically, the gradient step is an operator T(f,η) that is parametrized by the function fand the step size η. 99
∇f(w(k)) −η∇f(w(k)) 1 f(·) ww T(f,η)(w) Fig. 37. The basic gradient step (5) maps a given vector wto the updated vector w′. It defines an operator T(f,η)(·) : Rd→Rd:w7→ b w. Note that the gradient step (5) optimizes locally—in a neighborhood whose size is determined by the step size η —a linear approximation to the function f ( · ). A natural generalization of (5) is to locally optimize the function itself—instead of its linear approximation—such that b w= arg min w′∈Rd f(w′)+ 1 η∥w−w′∥2 2.(6) We intentionally use the same symbol η for the parameter in (6) as we used for the step size in (5) . The larger the η we choose in (6) , the more progress the update will make toward reducing the function value f ( b w ). Note that, much like the gradient step (5) , the update (6) also defines an operator that is parameterized by the function f ( · )and the learning rate η . For a convex function f ( · ), this operator is known as the proximal operator of f(·)[78]. See also: differentiable, function, vector, gradient, step size, neigh100
borhood, generalization, parameter, learning rate, convex, proximal operator. gradient-based method A Gradient-based method is an iterative technique for finding the minimum (or maximum) of a differentiable objective function f (w)of the model parameters w. Such a method constructs a sequence of approximations to an optimal choice for w. As the name indicates, a gradient-based method uses the gradients of the objective function evaluated during previous iterations to construct new, (hopefully) improved model parameters. One important example of a gradient-based method is GD. See also: gradient, differentiable, objective function, optimization method, GD. graph A graph G = (V,E) is a pair that consists of a node set V and an edge set E . In its most general form, a graph is specified by a map that assigns each edge e∈ E a pair of nodes [87]. One important family of graphs is simple undirected graphs. A simple undirected graph is obtained by identifying each edge e∈ E with two different nodes {i, i′} . Weighted graphs also specify numeric weights Aefor each edge e∈ E. See also: map, weights. graph clustering Graph clustering aims to cluster data points that are represented as the nodes of a graph G . The edges of G represent pairwise similarities between data points. We can sometimes quantify the extent of these similarities by an edge weight [79], [88]. See also: graph, clustering, data point, edge weight. 101
hard clustering Hard clustering refers to the task of partitioning a given set of data points into (a few) nonoverlapping clusters. The most widely used hard clustering method is k-means. See also: clustering, data point, cluster, k-means. high-dimensional regime The high-dimensional regime of ERM is characterized by the effective dimension of the model being larger than the sample size, i.e., the number of (labeled) data points in the training set. For example, linear regression methods operate in the high-dimensional regime whenever the number d of features used to characterize data points exceeds the number of data points in the training set. Another example of ML methods that operate in the high-dimensional regime is large ANNs, which have far more tunable weights (and bias terms) than the total number of data points in the training set. High-dimensional statistics is a recent main thread of probability theory that studies the behavior of ML methods in the high-dimensional regime [34], [89]. See also: ERM, effective dimension, overfitting, regularization. Hilbert space A Hilbert space is a complete inner product space [90]. That is, it is a vector space equipped with an inner product between pairs of vectors, and it satisfies the additional requirement of completeness, i.e., every Cauchy sequence of vectors converges to a limit within the space. A canonical example of a Hilbert space is the Euclidean space Rd , for some dimension d , consisting of vectors u= u1, . . . , udT and the standard inner product uTv. See also: vector space, vector, Euclidean space. 102
hinge loss Consider a data point characterized by a feature vector x ∈Rd and a binary label y∈ {− 1 , 1 } . The hinge loss incurred by a real-valued hypothesis map h(x)is defined as L((x, y), h) := max{0,1−yh(x)}.(7) −3−2−1 1 2 3 1 2 yh(x) L((x, y), h) Fig. 38. The hinge loss incurred by the prediction h (x) ∈R for a data point with label y∈ {− 1 , 1 } . A regularized variant of the hinge loss is used by the support vector machine (SVM) [91]. See also: SVM, classification, classifier. histogram Consider a dataset D that consists of m data points z (1), . . . , z (m) , each of them belonging to some cell [ −U, U ] ×. . . × [ −U, U ] ⊆Rd with side length U . We partition this cell evenly into smaller elementary cells with side length ∆. The histogram of D assigns each elementary cell to the corresponding fraction of data points in D that fall into this elementary cell. A visual example of such a histogram is provided in 103
Fig. 39. [0,1) [1,2) [2,3) [3,4) [4,5) 1 2 3 4 5 6 Value Frequency Histogram of Sample Data Fig. 39. A histogram representing the frequency of data points falling within discrete value ranges (i.e., bins). Each bar height shows the count of samples in the corresponding interval. See also: dataset, data point, sample. horizontal federated learning (HFL) HFL uses local datasets constituted by different data points but uses the same features to characterize them [92]. For example, weather forecasting uses a network of spatially distributed weather (observation) stations. Each weather station measures the same quantities, such as daily temperature, air pressure, and precipitation. However, different weather stations measure the characteristics or features of different spatiotemporal regions. Each spatiotemporal region represents an individual data point, each charac104
terized by the same features (e.g., daily temperature or air pressure). See also: semi-supervised learning (SSL), FL, vertical federated learning (VFL). Huber loss The Huber loss unifies the squared error loss and the absolute error loss. See also: loss, squared error loss, absolute error loss. Huber regression Huber regression refers to ERM-based methods that use the Huber loss as a measure of the prediction error. Two important special cases of Huber regression are least absolute deviation regression and linear regression. Tuning the threshold parameter of the Huber loss allows the user to trade the robustness of the absolute error loss against the computational benefits of the smooth squared error loss. See also: least absolute deviation regression, linear regression, absolute error loss, squared error loss. hypothesis A hypothesis refers to a map (or function) h : X → Y from the feature space X to the label space Y . Given a data point with features x, we use a hypothesis map h to estimate (or approximate) the label y using the prediction ˆy = h (x). ML is all about learning (or finding) a hypothesis map h such that y≈h (x)for any data point (with features xand label y ). Practical ML methods, limited by finite computational resources, must restrict learning to a subset of all possible hypothesis maps. This subset is called the hypothesis space or simply the model underlying the method. See also: map, function, prediction, model. 105
x(r) µ(1) µ(2) Fig. 43. A scatterplot of data points, indexed by r = 1 , . . . , m and characterized by feature vectors x (r)∈R2 . The scatterplot also includes two cluster centroids µ(1),µ(2) ∈R2. In general, the k -means problem is a challenging optimization problem [96]. However, there is a simple iterative method for finding approximately optimal cluster centroids. This method, referred to as Lloyd’s method, alternates between: 1) updating the cluster assignments based on the nearest current cluster centroid; and 2) recalculating the cluster centroids given the updated cluster assignments [97]. See also: hard clustering, cluster. kernel Consider a set of data points, each represented by a feature vector x ∈ X , where X denotes the feature space. A (real-valued) kernel is a function K : X ×X → R that assigns to every pair of feature vectors x , x ′∈ X a real number K x , x ′ . This value is typically interpreted as a similarity measure between xand x ′ . The defining property of a kernel is that it is symmetric, i.e., K x , x ′ = K x ′, x , and that for 112
any finite set of feature vectors x1, . . . , xn∈ X, the matrix K= Kx1,x1Kx1,x2. . . Kx1,xn Kx2,x1Kx2,x2. . . Kx2,xn . . .. . ..... . . Kxn,x1Kxn,x2. . . Kxn,xn ∈Rn×n is psd. A kernel naturally defines a transformation of a feature vector xinto a function z= K x ,· . The function zmaps an input x ′∈ X to the value K x , x ′ . We can view the function zas a new feature vector that belongs to a feature space X′ that is typically different from X . This new feature space X′ has a particular mathematical structure, i.e., it is a reproducing kernel Hilbert space (RKHS) [71], [91]. Since zbelongs to a RKHS, which is a vector space, we can interpret it as a generalized feature vector. Note that a finite-length feature vector x= x1, . . . , xdT∈Rd can be viewed as a function x: { 1 , . . . , d} → R that assigns a real value to each index j∈ {1, . . . , d}. See also: feature vector, feature space, Hilbert space, kernel method. kernel method A kernel method is an ML method that uses a kernel K to map the original (i.e., raw) feature vector xof a data point to a new (transformed) feature vector z= K x ,· [71], [91]. The motivation for transforming the feature vectors is that, by using a suitable kernel, the data points have a more "pleasant" geometry in the transformed feature space. For example, in a binary classification problem, using transformed feature vectors zmight allow us to use linear models, even if the data points are not linearly separable in the original feature space (see Fig. 44). 113
x(5) x(4) x(3) x(2) x(1) z(5)z(4)z(3)z(2) z(1) z=Kx,· Fig. 44. Five data points characterized by feature vectors x (r) and labels y(r)∈ {◦,□} , for r = 1 , . . . , 5. With these feature vectors, there is no way to separate the two classes by a straight line (representing the decision boundary of a linear classifier). In contrast, the transformed feature vectors z (r) = K x (r),· allow us to separate the data points using a linear classifier. See also: kernel, feature vector, feature space, linear classifier. Kronecker product The Kronecker product of two matrices A ∈Rm×n and B∈Rp×qis a block matrix denoted by A⊗Band defined as [3], [11] A⊗B= a11B··· a1nB . . ..... . . am1B··· amnB ∈Rmp×nq. The Kronecker product is a special case of the tensor product for matrices and is widely used in multivariate statistics, linear algebra, and structured ML models. It satisfies the identity (A ⊗ B)(x ⊗ y) = (Ax)⊗(By)for vectors xand yof compatible dimensions. See also: matrix, ML, model, vector. Kullback–Leibler divergence (KL divergence) The KL divergence is a quantitative measure of how different one probability distribution is 114
from another [42]. See also: probability distribution. label A higher-level fact or quantity of interest associated with a data point. For example, if the data point is an image, the label could indicate whether the image contains a cat or not. Synonyms for label, commonly used in specific domains, include "response variable," "output variable," and "target" [69], [70], [37]. See also: data point, label space. label space In a ML application, each data point is described by a set of features together with an associated label. The set of all admissible label values is called the label space, denoted by Y . Importantly, Y may include values that no observed data point has as its label value. To a large extent, the choice of Y is up to the ML engineer and depends on the problem formulation. Fig. 45 shows some examples of label spaces that are commonly used in ML applications. 115
(a) Y=R(regression) (b) Y=R2(multi-label regression) “hot” “cold” (c) |Y| = 2 Binary classification 1 2 3 4 (d) Y={1,2,3,4}(ordinal regression) Fig. 45. Examples of label spaces and corresponding flavours of ML. The choice of label space Y determines the flavour of ML methods appropriate for the application at hand. Regression methods use the Y = R while binary classification methods use a label space Y that consists of two different elements, i.e., |Y| = 2. Ordinal regression methods use a finite, ordered set of label values, e.g., Y = { 1 , 2 , 3 , 4 } with the natural ordering 1<2<3<4. See also: data point,label, regression, classification. labeled data point A data point whose label is known or has been determined by some means that might require human labor. See also: data point, label. Laplacian matrix The structure of a graph G , with nodes i = 1 , . . . , n , can be analyzed using the properties of special matrices that are associated with G . One such matrix is the graph Laplacian matrix L (G)∈Rn×n , which is defined for an undirected and weighted graph [88], [98]. It is 116
defined elementwise as (see Fig. 46) L(G) i,i′:= −Ai,i′,for i=i′,{i, i′}∈E; P i′′=i Ai,i′′ ,for i=i′; 0,else. Here, Ai,i′denotes the edge weight of an edge {i, i′} ∈ E. 1 2 3 (a) L(G)= 2−1−1 −1 1 0 −1 0 1 (b) Fig. 46. (a) Some undirected graph G with three nodes i = 1 , 2 , 3. (b) The Laplacian matrix L(G)∈R3×3of G. See also: graph, matrix, edge weight. large language model (LLM) LLM is an umbrella term for ML methods that process and generate humanlike text. These methods typically use deep nets with billions (or even trillions) of parameters. A widely used choice for the network architecture is referred to as Transformers [26]. The training of LLMs is often based on the task of predicting a few words that are intentionally removed from a large text corpus. Thus, we can construct labeled data points simply by selecting some words from a given text as labels and the remaining words as features of data 117
points. This construction requires very little human supervision and allows for generating sufficiently large training sets for LLMs. See also: deep net, labeled data point. law of large numbers The law of large numbers refers to the convergence of the average of an increasing (large) number of i.i.d. RVs to the mean of their common probability distribution. Different instances of the law of large numbers are obtained by using different notions of convergence [18]. See also: convergence, i.i.d., RV, mean, probability distribution. layer A deep net is an ANN that consists of consecutive layers, indexed by ℓ = 1 , 2 , . . . , L . The ℓ -th layer consists of artificial neurons a(ℓ) 1, . . . , a(ℓ) d(ℓ) with the layer width d(ℓ) . Each of these artificial neurons evaluates an activation function for a weighted sum of the outputs (or activations) of the previous layer ℓ− 1. The input to layer ℓ = 1 is formed from weighted sums of the features of the data point for which the deep net computes a prediction. The outputs of the neurons in layer ℓ are then, in turn, used to form the inputs for the neurons in the next layer. The final (output) layer consists of a single neuron whose output is used as the prediction delivered by the deep net. See also: deep net, ANN. learning rate Consider an iterative ML method for finding or learning a useful hypothesis h∈ H . Such an iterative method repeats similar computational (update) steps that adjust or modify the current hypothesis to obtain an improved hypothesis. One well-known example 118
of such an iterative learning method is GD and its variants, SGD and projected gradient descent (projected GD). A key parameter of an iterative method is the learning rate. The learning rate controls the extent to which the current hypothesis can be modified during a single iteration. A well-known example of such a parameter is the step size used in GD [8, Ch. 5]. See also: ML, hypothesis, GD, SGD, projected GD, parameter, step size. learning task Consider a dataset D consisting of multiple data points z (1), . . . , z (m) . For example, D can be a collection of images in an image database. A learning task is defined by specifying those properties (or attributes) of a data point that are used as its features and labels. Given a choice of model H and loss function, a learning task leads to an instance of ERM and can thus be represented by the associated objective function b Lh|D for h∈ H . Importantly, multiple distinct learning tasks can be constructed from the same dataset by selecting different sets of features and labels (see Fig. 47). 119
An image showing cows grazing in the Austrian countryside. Task 1 (regression): Features are the RGB values of all image pixels, and the label is the number of cows depicted. Task 2 (classification): Features include the average green intensity of the image, and the label indicates whether cows should be moved to another location (i.e., yes/no). Fig. 47. Two learning tasks constructed from a single image dataset. These tasks differ in feature selection and choice of label (i.e., the objective), but are both derived from the same dataset. Different learning tasks arising from the same underlying dataset are often coupled. For example, when a probabilistic model is used to generate data points, statistical dependencies among different labels induce dependencies among the corresponding learning tasks. In general, 120
solving learning tasks jointly, e.g., using multitask learning methods, tends to be more effective than solving them independently (thereby ignoring dependencies among learning tasks) [99], [100], [101]. See also: dataset, model, loss function, objective function, multitask learning, label space. least absolute deviation regression Least absolute deviation regression is an instance of ERM using the absolute error loss. It is a special case of Huber regression. bw= med (D) (a) bw= med e D outlier (b) Fig. 48. For the simple parametric model h(w) (x) = w , ERM with absolute error loss amounts to computing the median. (a) Original dataset D . (b) Noisy dataset e Dincluding an outlier. For the parametric model h(w) (x) = w , ERM with absolute error loss is solved by the median. Using squared error loss instead for the same parametric model, makes ERM computing the mean. See also: ERM, absolute error loss, Huber regression. 121
might arise from probabilistic models or communication infrastructure and are encoded in the edges of an FL network. See also: dataset, data point, feature, label, ML, probabilistic model, FL network. local interpretable model-agnostic explanations (LIME) Consider a trained model (or learned hypothesis) bh∈ H , which maps the feature vector of a data point to the prediction by = bh . LIME is a technique for explaining the behavior of bh , locally around a data point with feature vector x (0) [72]. The explanation is given in the form of a local approximation g∈ H′ of bh (see Fig. 51). This approximation can be obtained by an instance of ERM with a carefully designed training set. In particular, the training set consists of data points with feature vectors centered around x (0) and the (pseudo-)label bh (x). Note that we can use a different model H′ for the approximation from the original model H . For example, we can use a decision tree to locally approximate a deep net. Another widely used choice for H′is the linear model. 128
bh(x) g(x) x(0) x y Fig. 51. To explain a trained model bh∈ H , around a given feature vector x(0), we can use a local approximation g∈ H′. See also: model, explanation, ERM, training set, label, decision tree, deep net, linear model. local model Consider a collection of devices that are represented as nodes V of an FL network. A local model H(i) is a hypothesis space assigned to a node i∈ V . Different nodes can have different hypothesis spaces, i.e., in general, H(i)=H(i′)for different nodes i, i′∈ V. See also: device, FL network, model, hypothesis space. logistic loss Consider a data point characterized by the features xand a binary label y∈ {− 1 , 1 } . We use a real-valued hypothesis h to predict the label y from the features x. The logistic loss incurred by this prediction is defined as L((x, y), h) := log (1 + exp (−yh(x))).(9) 129
−3−2−1 1 2 3 1 2 yh(x) L((x, y), h) Fig. 52. The logistic loss incurred by the prediction h (x) ∈R for a data point with label y∈ {−1,1}. Note that the expression (9) for the logistic loss applies only for the label space Y={−1,1}and when using the thresholding rule (1). See also: data point, feature, label, hypothesis, loss, prediction, label space. logistic regression Logistic regression learns a linear hypothesis map (or classifier) h (x) = w T xto predict a binary label y based on the numeric feature vector xof a data point. The quality of a linear hypothesis map is measured by the average logistic loss on some labeled data points (i.e., the training set). See also: regression, hypothesis, map, classifier, label, feature vector, data point, logistic loss, labeled data point, training set. loss ML methods use a loss function L(z, h) to measure the error incurred by applying a specific hypothesis to a specific data point. With a slight 130
abuse of notation, we use the term loss for both the loss function L itself and the specific value L(z, h) , for a data point zand hypothesis h. See also: loss function, empirical risk. loss function A loss function is a map L:X ×Y ×H → R+:x, y, h7→ L((x, y), h). It assigns a nonnegative real number (i.e., the loss) L((x, y), h) to a pair that consists of a data point, with features xand label y , and a hypothesis h∈ H . The value L((x, y), h) quantifies the discrepancy between the true label y and the prediction h (x). Lower (closer to zero) values L((x, y), h) indicate a smaller discrepancy between prediction h (x)and label y . Fig. 53 depicts a loss function for a given data point, with features xand label y, as a function of the hypothesis h∈ H. h(x) L((x, y), h) Fig. 53. Some loss function L((x, y), h) for a fixed data point, with feature vector xand label y , and a varying hypothesis h . ML methods try to find (or learn) a hypothesis that incurs minimal loss. See also: loss, label, feature vector, ERM. 131
machine learning (ML) ML aims to predict a label from the features of a data point. ML methods achieve this by learning a hypothesis from a hypothesis space (or model) through the minimization of a loss function [8], [103]. One precise formulation of this principle is ERM. Different ML methods are obtained from different design choices for data points (i.e., their features and label), the model, and the loss function [8, Ch. 3]. See also: model, data, loss. Markov decision process (MDP) An MDP is a mathematical structure that can be used to study RL applications. An MDP formalizes how reward signals depend on the predictions (and corresponding actions) made by an RL method. Formally, an MDP is a specific type of stochastic process defined by •a state space S; • an action space A (where each action a∈ A corresponds to a specific prediction made by the RL method); • a transition function P ( s′|s, a )specifying the probability distribution over the next state s′∈ S, given the current state s∈ S and action a∈ A; • a reward function r ( s, a ) ∈R that assigns a numerical reward to each state-action pair. The defining property of an MDP is the Markov property. That is, the next state s′ and reward only depend on the current state s and action 132
a, not on the entire history of interactions. See also: RL, reward, prediction, stochastic process, function, probability distribution. maximum The maximum of a set A ⊆ R of real numbers is the greatest element in that set, if such an element exists. A set A has a maximum if it is bounded above and attains its supremum (or least upper bound) [2, Sec. 1.4]. See also: supremum. maximum likelihood Consider data points D = z (1), . . . , z (m)} that are interpreted as the realizations of i.i.d. RVs with a common probability distribution P ( z;w ), which depends on the model parameters w ∈ W ⊆ Rn . Maximum likelihood methods learn model parameters wby maximizing the probability (density) P ( D;w ) = Qm r=1 P ( z(r);w )of the observed dataset. Thus, the maximum likelihood estimator is a solution to the optimization problem maxw∈W P(D;w). See also: probability distribution, optimization problem, probabilistic model. mean The mean of an RV x, which takes on values in a Euclidean space Rd , is its expectation E{ x } . It is defined as the Lebesgue integral of xwith respect to the underlying probability distribution P (e.g., see [2] or [6]), i.e., E{x}=ZRd xdP(x). We also use the term to refer to the average of a finite dataset D = x(1), . . . , x(m)∈Rd . However, these two definitions are essentially 133
the same. Indeed, we can use a dataset to construct a discrete RV e x(D) =x (I) on the sample space { 1 , . . . , m} . Here, the index I is chosen uniformly at random, P ( I=r ) = 1 /m for all r = 1 , . . . , m . The mean of e x(D) is precisely the average (1 /m ) Pm r=1 x (r) . For a RV with finite second-order moment, i.e., E{∥x∥2 2} is well-defined and fnite, the mean is characterized as the solution of the following risk minimization problem [7]: E{x}= arg min c∈Rd E∥x−c∥2 2. For the RV e x(D) , associated with a dataset, this optimization problem reduces to ERM with squared error loss on D. See also: RV, expectation, probability distribution, ERM. mean squared estimation error (MSEE) Consider an ML method that learns model parameters b w based on some dataset D . If we interpret the data points in D as i.i.d. realizations of an RV z, we define the estimation error ∆w:= bw−w . Here, w denotes the true model parameters of the probability distribution of z. The MSEE is defined as the expectation E ∆w 2 of the squared Euclidean norm of the estimation error [28], [56]. See also: RV, estimation error, probabilistic model, squared error loss. measurable Consider a random experiment, such as recording the air temperature at an FMI weather station. The corresponding sample space Ω consists of all possible outcomes ω (e.g., all possible temperature values in degree Celsius). In many ML applications, we are not interested in the exact outcome ω , but only whether it belongs to a subset A ⊆ Ω 134
(e.g., “is the temperature below zero degrees?”). We call such a subset A measurable if it is possible to decide, for any outcome ω , whether ω∈ A or not (see Fig. 54). temperature (◦C) –20 –10 0 10 20 30 40 50 60 ω < 0◦C35 ◦C< ω < 55 ◦C Fig. 54. A sample space constituted by all possible temperature values ω that may be experienced at an FMI station. Two measurable subsets of temperature values, denoted by A(1) and A(2) , are highlighted. For any actual temperature value ω , it is possible to determine whether ω∈ A(1) and whether ω∈ A(2). In principle, measurable sets could be chosen freely (e.g., depending on the resolution of the measuring equipment). However, it is often useful to impose certain completeness requirements on the collection of measurable sets. For example, the sample space itself should be measurable, and the union of two measurable sets should also be measurable. These completeness requirements can be formalized via the concept of σ -algebra (or σ -field) [1], [6], [104]. A measurable space is a pair X,F that consists of an arbitrary set X and a collection F of measurable subsets of Xthat form a σ-algebra. See also: sample space, probability. 135
median A median med ( x )of a real-valued RV x is any number M∈R such that P(x≤M)≥1/2and P(x≥M)≥1/2(see Fig. 55) [28]. 0.5 1P(x≤η) M η Fig. 55. The median of a real-valued RV is any number M that partitions R into two rays with equal probability. We can define the median med ( D )of a dataset D = {x(1), . . . , x(m)∈ R} via a specific RV ˜x(D) that is naturally associated with D . In particular, this RV is defined on the sample space { 1 , . . . , m} via ˜x(D) := x(I) . Here, the index I is chosen uniformly at random, i.e., P ( I=r )=1 /m for all r = 1 , . . . , m . If the RV x is integrable, any median of xsolves the optimization problem: min x′∈R E|x−x′|. For a the above RV ˜x (constructed from a dataset D ), this optimization problem is ERM on D using absolute error loss. Like the mean, the median of a dataset D can also be used to estimate parameters of an underlying probabilistic model. Compared with the mean, the median is more robust to outliers. For example, a median of a dataset D with 136
more than one data point does not change even if we arbitrarily increase the largest element of D (see Fig. 56). In contrast, the mean will increase arbitrarily. med (D)=mean(D) (a) mean e D med e D outlier (b) Fig. 56. The median is robust against outlier contamination. (a) Original dataset D. (b) Noisy dataset e Dincluding an outlier. See also: mean, outlier, robustness, least absolute deviation regression. metric In its most general form, a metric is a quantitative measure used to compare or evaluate objects. In mathematics, a metric measures the distance between two points and must follow specific rules, i.e., the distance is always nonnegative, zero only if the points are the same, symmetric, and it satisfies the triangle inequality [2]. In ML, a metric is a quantitative measure of how well a model performs. Examples include accuracy, precision, and the average 0 / 1loss on a test set [51], [58]. A loss function is used to train models, while a metric is used to compare trained models. 137
is defined as {x′∈ X :d(x,x′)≤ϵ}. If X is an undirected graph, which is a special case of a metric space, the neighborhood of a node i∈ V is the set of its neighbors. See also: neighbors, metric. neighbors The neighbors of a node i∈ V within an FL network are those nodes i′∈ V \{i}that are connected (via an edge) to node i. See also: FL network. networked data Networked data consist of local datasets that are related by some notion of pairwise similarity. We can represent networked data using a graph whose nodes carry local datasets and whose edges encode pairwise similarities. An example of networked data can be found in FL applications where local datasets are generated by spatially distributed devices. See also: data, local dataset, graph, FL, device. networked exponential families (nExpFam) A collection of exponential families, each of them assigned to a node of an FL network. The model parameters are coupled via the network structure by requiring them to have a small GTV [111]. See also: FL network, model parameters, GTV. networked federated learning (NFL) NFL refers to methods that learn personalized models in a distributed fashion. These methods learn from local datasets that are related by an intrinsic network structure. See also: model, local dataset, FL. 144
networked model A networked model over an FL network G = (V,E) assigns a local model (i.e., a hypothesis space) to each node i∈ V of the FL network G. See also: model, FL network, local model, hypothesis space. node degree The degree d(i) of a node i∈ V in an undirected graph is the number of its neighbors, i.e., d(i):= N(i). See also: graph, neighbors. non-smooth We refer to a function as non-smooth if it is not smooth [16]. See also: function, smooth. norm A norm is a function that maps each (vector) element of a vector space to a nonnegative real number. This function must be homogeneous and definite, and it must satisfy the triangle inequality [11]. See also: function, vector, vector space. nullspace The nullspace of a matrix A ∈Rd′×d , denoted by null (A) , is the set of all vectors n∈Rdsuch that An =0. Consider a feature learning method that uses the matrix Ato transform a feature vector x ∈Rd of a data point into a new feature vector z=Ax ∈Rd′ . The nullspace null (() A)characterizes all directions in the original feature space Rd along which the transformation Ax remains unchanged. In other words, adding any vector from the nullspace to a feature vector xdoes not affect the transformed representation z. This property can be exploited to enforce invariances in the predictions 145
(computed from Ax). Fig. 59 illustrates one such invariance. It shows rotated versions of two handwritten digits, which approximately lie along 1-D curves in the original feature space. These curves are aligned with a direction vector n ∈Rd . To ensure that the trained model is invariant to such rotations, we can choose the transformation matrix A such that n ∈null (A) . This ensures that Ax, and hence the resulting prediction, is approximately insensitive to rotations of the input image. Fig. 59. Rotated handwritings of two different digits. The rotations are approximately aligned along straight lines parallel to the vector n. For a binary classifier distinguishing between these digits, a natural choice is a linear feature map x 7→ Ax with a matrix Awhose nullspace contains n, i.e., n∈null(A). See also: matrix, feature map, feature learning. Python demo: click me 146
objective function An objective function is a map that assigns a numeric objective value f (w)to each choice wof some variable that we want to optimize (see Fig. 60). In the context of ML, the optimization variable could be the model parameters of a hypothesis h(w) . Common objective functions include the risk (i.e., expected loss) or the empirical risk (i.e., average loss over a training set). ML methods apply optimization techniques, such as gradient-based methods, to find the choice wwith the optimal value (e.g., the minimum or the maximum) of the objective function. w f(w) Fig. 60. An objective function maps each possible value wof an optimization variable, such as the model parameters of an ML model, to a value f (w)that measures the usefulness of w. See also: loss, empirical risk, ERM, optimization problem. online algorithm An online algorithm processes input data incrementally, receiving data points sequentially and making decisions or producing outputs (or decisions) immediately without having access to the entire 147
input in advance [60], [61]. Unlike an offline algorithm, which has the entire input available from the start, an online algorithm must handle uncertainty about future inputs and cannot revise past decisions. Similar to an offline algorithm, we represent an online algorithm formally as a collection of possible executions. However, the execution sequence for an online algorithm has a distinct structure as follows: in1, s1,out1,in2, s2,out2, . . . , inT, sT,outT. Each execution begins from an initial state (i.e., in1 ) and proceeds through alternating computational steps, outputs (or decisions), and inputs. Specifically, at step k , the algorithm performs a computational step sk , generates an output outk , and then subsequently receives the next input (data point) ink+1 . A notable example of an online algorithm in ML is online gradient descent (online GD), which incrementally updates model parameters as new data points arrive. See also: algorithm, data, data point, uncertainty, ML, online GD, model parameters, online learning. online gradient descent (online GD) Consider an ML method that learns model parameters wfrom some parameter space W ⊆ Rd . The learning process uses data points z (t) that arrive at consecutive time instants t= 1,2, . . . . Let us interpret the data points z(t)as i.i.d. copies of an RV z. The risk E{L(z,w)}of a hypothesis h(w)can then (under mild conditions) be obtained as the limit limT→∞ (1 /T ) Pt=1 TLz(t),w . We might use this limit as the objective function for learning the model parameters w. Unfortunately, this limit can only be evaluated if we wait 148
infinitely long in order to collect all data points. Some ML applications require methods that learn online, i.e., as soon as a new data point z (t) arrives at time t , we update the current model parameters w (t) . Note that the new data point z (t) contributes the component Lz(t),w to the risk. As its name suggests, online GD updates w (t) via a (projected) gradient step such that w(t+1) := PWw(t)−ηt∇wLz(t),w.(10) Note that (10) is a gradient step for the current component Lz(t),· of the risk. The update (10) ignores all previous components Lz(t′),· , for t′< t . It might therefore happen that, compared with w (t) , the updated model parameters w (t+1) increase the retrospective average loss Pt−1 t′=1 Lz(t′),· . However, for a suitably chosen learning rate ηt , online GD can be shown to be optimal in practically relevant settings. By optimal, we mean that the model parameters w (T+1) delivered by online GD after observing T data points z (1), . . . , z (T) are at least as good as those delivered by any other learning method [61], [112]. 149
t= 1 t= 2 t= 3 t= 4 t= 5 z(1) z(2) z(3) z(4) z(5) w(1) w(2) w(3) w(4) w(5) Fig. 61. An instance of online GD that updates the model parameters w (t) using the data point z (t) = x(t) arriving at time t . This instance uses the squared error loss Lz(t), w= (x(t)−w)2. See also: objective function, GD, gradient step, online learning. online learning Some ML methods are designed to process data in a sequential manner, updating their model parameters one at a time, as new data points become available. A typical example is time-series data, such as daily minimum and maximum temperatures recorded by an FMI weather station. These values form a chronological sequence of observations. During each time step t , online learning methods update (or refine) the current hypothesis h(t) (or model parameters w (t) ) based on the newly observed data point z(t). See also: online GD, online algorithm. optimism in the face of uncertainty ML methods learn model parameters waccording to some performance criterion ¯ f (w). However, they usually cannot access ¯ f (w)directly but rely on an estimate (or ap150
proximation) f (w)of ¯ f (w). As a case in point, ERM-based methods use the average loss on a given dataset (i.e., the training set) as an estimate for the risk of a hypothesis. Using a probabilistic model, one can construct a confidence interval l(w), u(w) for each choice wfor the model parameters. One simple construction is l(w) := f (w) −σ/ 2, u(w) := f (w) + σ/ 2, with σ being a measure of the (expected) deviation of f(w)from ¯ f(w). We can also use other constructions for this interval as long as they ensure that ¯ f (w) ∈l(w), u(w) with a sufficiently high probability. An optimist chooses the model parameters according to the most favorable—yet still plausible—value ˜ f (w) := l(w) of the performance criterion (see Fig. 62). Two examples of ML methods that use such an optimistic construction of an objective function are SRM [83, Ch. 11] and upper confidence bound (UCB) methods for sequential decision making [108, Sec. 2.2]. 151
f(w) ˜ f(w) l(w) ,u(w) Fig. 62. ML methods learn model parameters wby using some estimate of f (w)for the ultimate performance criterion ¯ f (w). Using a probabilistic model, one can use f (w)to construct confidence intervals l(w), u(w) , which contain ¯ f (w)with a high probability. The best plausible performance measure for a specific choice wof model parameters is ˜ f(w) := l(w). See also: objective function, optimization method, gradient-based method, UCB. optimization method An optimization method is an algorithm that reads in a representation of an optimization problem and delivers an (approximate) solution as its output [12], [15], [16]. See also: algorithm, optimization problem. outlier Many ML methods are motivated by the i.i.d. assumption, which interprets data points as realizations of i.i.d. RVs with a common probability distribution. The i.i.d. assumption is useful for applications where the statistical properties of the data generation process are 152
stationary (or time-invariant) [19]. However, in some applications, the data consist of a majority of regular data points that conform with the i.i.d. assumption as well as a small number of data points that have fundamentally different statistical properties compared with the regular data points. We refer to a data point that substantially deviates from the statistical properties of most data points as an outlier. Different methods for outlier detection use different measures for this deviation. Statistical learning theory studies fundamental limits on the ability to mitigate outliers reliably [113], [114]. See also: robustness, stability, Huber regression, probabilistic model. overfitting Consider an ML method that uses ERM to learn a hypothesis with the minimum empirical risk on a given training set. Such a method is overfitting the training set if it learns a hypothesis with a low empirical risk on the training set but a significantly higher loss outside the training set. See also: ERM, generalization, validation, generalization gap. parameter The parameter of an ML model is a tunable (i.e., learnable or adjustable) quantity that allows us to choose between different hypothesis maps. For example, the linear model H := {h(w) : h(w) ( x ) = w1x + w2} consists of all hypothesis maps h(w) ( x ) = w1x + w2 with a particular choice for the parameters w= w1, w2T∈R2 . Another example of a model parameter is the weights assigned to a connection between two neurons of an ANN. See also: ML, model, hypothesis, map, linear model, weights, ANN. 153