# Chapter 120. Machine Learning # Chapter 120. Machine Learning Machine learning studies algorithms that improve their behavior from data. A machine learning system receives examples, extracts structure, and produces predictions, classifications, rankings, embeddings, or decisions. Linear algebra is central because data are represented as vectors and matrices, models are often linear or locally linear, and training is usually an optimization problem over parameters. Many standard learning methods can be written in the form $$ \text{data matrix} \to \text{linear map} \to \text{loss function} \to \text{optimization}. $$ This is why linear algebra appears throughout machine learning: in regression, classification, kernels, embeddings, neural networks, dimensionality reduction, and numerical optimization. Stanford CS229 notes, for example, develop regularization, kernels, SVMs, and optimization using vector and matrix notation. ## 120.1 Data as Vectors A single data point is often represented as a vector $$ x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_d \end{bmatrix} \in \mathbb{R}^d. $$ Each component is a feature. For example, a house may be represented by features such as size, number of rooms, distance to city center, and age. An image may be represented by pixel values. A document may be represented by word counts or embedding coordinates. | Object | Vector representation | |---|---| | Image | Pixel vector or feature vector | | Text | Token vector, count vector, or embedding | | Audio | Sample vector or spectral feature vector | | User | Preference vector | | Product | Attribute or embedding vector | | Sensor reading | Measurement vector | Once data are vectors, distances, inner products, projections, norms, and linear transformations become available. ## 120.2 Data Matrices A dataset with \(m\) examples and \(d\) features is stored as a matrix $$ X = \begin{bmatrix} - & x_1^T & - \\ - & x_2^T & - \\ & \vdots & \\ - & x_m^T & - \end{bmatrix} \in \mathbb{R}^{m\times d}. $$ Each row is one example. Each column is one feature. The target values are often stored as a vector $$ y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{bmatrix}. $$ The pair \((X,y)\) is the basic supervised learning dataset. The design is the same as in linear regression. Machine learning extends this framework to broader models, losses, constraints, and data types. ## 120.3 Features A feature is a numerical quantity used by a model. A feature map converts raw input into a vector: $$ \phi : \mathcal{X} \to \mathbb{R}^d. $$ For an input object \(a\), the model uses $$ x=\phi(a). $$ Feature maps may be simple or complex. | Raw object | Possible features | |---|---| | Text | Word counts, TF-IDF, embeddings | | Image | Pixels, patches, learned features | | Graph | Degrees, neighborhoods, spectral features | | User behavior | Counts, recency, preferences | | Time series | Lags, moving averages, Fourier coefficients | Feature design changes the geometry of the learning problem. A model that is linear in one feature space may represent nonlinear behavior in the original input space. ## 120.4 Linear Prediction The simplest prediction model is linear: $$ \hat{y}=w^Tx+b. $$ Here \(w\in\mathbb{R}^d\) is the weight vector and \(b\in\mathbb{R}\) is the bias. The value \(w_j\) measures how feature \(j\) contributes to the prediction. For the full dataset, $$ \hat{y}=Xw+b\mathbf{1}. $$ If the bias is included as an extra feature equal to \(1\), then the model becomes $$ \hat{y}=Xw. $$ This is the same matrix form used in least squares. ## 120.5 Loss Functions A loss function measures prediction error. For regression, a common loss is squared error: $$ \ell(\hat{y},y)=(\hat{y}-y)^2. $$ For a dataset, the empirical risk is $$ L(w)=\frac{1}{m}\sum_{i=1}^m (w^Tx_i-y_i)^2. $$ In matrix form, $$ L(w)=\frac{1}{m}\|Xw-y\|^2. $$ Thus linear regression is a least squares problem. Other learning problems use different losses. | Problem | Common loss | |---|---| | Regression | Squared error | | Binary classification | Logistic loss | | Margin classification | Hinge loss | | Multiclass classification | Cross-entropy | | Ranking | Pairwise ranking loss | | Embedding learning | Contrastive loss | The choice of loss changes the optimization problem. ## 120.6 Training Training means choosing model parameters to minimize loss. For a linear model, training solves $$ \min_w L(w). $$ For squared loss, $$ \min_w \|Xw-y\|^2. $$ This is ordinary least squares. If \(X^TX\) is invertible, the solution is $$ \hat{w}=(X^TX)^{-1}X^Ty. $$ In larger or more complex models, training is usually done by iterative optimization, such as gradient descent. ## 120.7 Gradient Descent Gradient descent updates parameters by moving opposite the gradient: $$ w_{k+1}=w_k-\eta \nabla L(w_k). $$ Here \(\eta>0\) is the learning rate. For squared loss, $$ L(w)=\frac{1}{m}\|Xw-y\|^2, $$ the gradient is $$ \nabla L(w)=\frac{2}{m}X^T(Xw-y). $$ Thus each update uses matrix-vector products with \(X\) and \(X^T\). This is one reason large-scale machine learning depends heavily on efficient linear algebra kernels. ## 120.8 Regularization Regularization adds a penalty to the training objective. A common example is ridge regularization: $$ \min_w \|Xw-y\|^2+\lambda\|w\|^2. $$ Here \(\lambda>0\) controls the penalty strength. The solution satisfies $$ (X^TX+\lambda I)w=X^Ty. $$ Regularization discourages overly large parameter vectors and improves stability when features are correlated or data are limited. CS229 notes describe \(\ell_2\) regularization as encouraging small parameter norm and, in gradient descent form, as weight decay. ## 120.9 Classification In binary classification, the target is usually $$ y\in\{-1,+1\} $$ or $$ y\in\{0,1\}. $$ A linear classifier computes a score $$ s=w^Tx+b. $$ The predicted class may be $$ \hat{y}=\operatorname{sign}(s). $$ Geometrically, the equation $$ w^Tx+b=0 $$ defines a hyperplane. This hyperplane separates feature space into two half-spaces. The vector \(w\) is normal to the separating hyperplane. Classification is therefore a geometric problem in vector space. ## 120.10 Logistic Regression Logistic regression converts a linear score into a probability. The score is $$ s=w^Tx+b. $$ The probability of class \(1\) is $$ p=\sigma(s)=\frac{1}{1+e^{-s}}. $$ The sigmoid function maps real numbers to values between \(0\) and \(1\). Training usually minimizes cross-entropy loss: $$ L(w) = -\sum_{i=1}^m \left[ y_i\log p_i+(1-y_i)\log(1-p_i) \right]. $$ Although the model is linear in its score, the probability is nonlinear in the parameters. The training objective is convex for ordinary logistic regression. ## 120.11 Support Vector Machines A support vector machine seeks a separating hyperplane with a large margin. For binary labels $$ y_i\in\{-1,+1\}, $$ a linear classifier uses $$ f(x)=w^Tx+b. $$ The margin condition is $$ y_i(w^Tx_i+b)\geq 1. $$ The hard-margin SVM solves $$ \min_{w,b}\frac{1}{2}\|w\|^2 $$ subject to the margin constraints. The support vectors are training points that lie on or inside the margin boundary. SVMs are commonly developed through optimization, kernels, and inner products, and the kernel trick replaces explicit high-dimensional feature maps by kernel evaluations. ## 120.12 Kernels A kernel is a function $$ K(x,z) $$ that behaves like an inner product in some feature space: $$ K(x,z)=\langle \phi(x),\phi(z)\rangle. $$ The kernel trick allows algorithms to use inner products in a high-dimensional feature space without explicitly constructing the feature vectors. Common kernels include: | Kernel | Formula | |---|---| | Linear | \(K(x,z)=x^Tz\) | | Polynomial | \(K(x,z)=(x^Tz+c)^p\) | | Gaussian RBF | \(K(x,z)=\exp(-\gamma\|x-z\|^2)\) | Kernel methods show that linear algebra can operate implicitly through Gram matrices. The Gram matrix has entries $$ G_{ij}=K(x_i,x_j). $$ ## 120.13 Embeddings An embedding maps an object into a vector space. For example, a word, document, image, user, or item may be mapped to $$ z\in\mathbb{R}^d. $$ The goal is that geometry in the embedding space reflects semantic or task-relevant structure. Similar objects should have nearby vectors. Dissimilar objects should have distant or differently oriented vectors. Common similarity measures include: | Measure | Formula | |---|---| | Dot product | \(x^Tz\) | | Euclidean distance | \(\|x-z\|\) | | Cosine similarity | \(\frac{x^Tz}{\|x\|\|z\|}\) | Embeddings turn complex objects into points in a learned vector space. ## 120.14 Neural Networks A neural network is a composition of linear maps and nonlinear activation functions. A single layer has the form $$ h=\sigma(Wx+b). $$ Here \(W\) is a weight matrix, \(b\) is a bias vector, and \(\sigma\) is applied componentwise. A multilayer network has the form $$ f(x) = W_L\sigma(W_{L-1}\sigma(\cdots\sigma(W_1x+b_1)))+b_L. $$ The matrices \(W_1,\ldots,W_L\) contain the learned parameters. Without nonlinear activation functions, the composition would collapse to one linear map. Nonlinearity is what allows neural networks to represent complex functions. Still, each layer is built from matrix multiplication. ## 120.15 Backpropagation Backpropagation computes gradients of a loss with respect to all parameters in a neural network. It applies the chain rule through the computational graph. For a layer $$ h=\sigma(Wx+b), $$ the gradient with respect to \(W\) has an outer-product structure: $$ \frac{\partial L}{\partial W} = \delta x^T, $$ where \(\delta\) is the backpropagated error vector for the layer. Thus training neural networks repeatedly uses matrix products, transposes, Jacobian-vector products, and outer products. MIT notes on matrix calculus for machine learning emphasize this matrix-based calculus viewpoint for differentiating vector and matrix expressions used in learning systems. ## 120.16 Dimensionality Reduction High-dimensional data are often compressed into lower-dimensional representations. A linear dimensionality reduction map has the form $$ z=W^Tx, $$ where $$ W\in\mathbb{R}^{d\times r}, \qquad r