CS229: Machine Learning（草稿）

参考 CS229 Summer 2024，Autumn 2018 视频，Lecture Notes。参考 CMU 10-601 Spring 2023，Spring 2023 视频，Panopto，以及 Mathematical Foundations for ML，Mathematics for Machine Learning。

Linear regression

由 \(n\) 个训练样本组成的训练集，\((\boldsymbol{x}^{i}, y^{i})\) 表示第 \(i\) 个训练样本，\(\boldsymbol{x}^{i}\) 和 \(y^{i}\) 分别表示输入特征（向量）和目标变量。监督学习的目标是给定训练集，找到函数 \(h : \mathcal X \to \mathcal Y\) 使得 \(h(\boldsymbol{x})\) 能够预测 \(y\) 值，该函数被称为假设（hypothesis），其中 \(\mathcal X\) 和 \(\mathcal Y\) 表示输入空间和输出空间。如果目标变量是连续的，则该学习问题被称为回归（regression）问题。如果目标变量是离散的，则该学习问题被称为分类（classification）问题。

LMS algorithm

使用 \(x\) 的线性函数 \(h_{\theta}(\boldsymbol{x})\) 近似 \(y\)，其中 \(\theta_{i}\) 是参数（权重），\(d\) 是输入变量的数量（不包括 \(x_{0}\)）。\(J(\boldsymbol{\theta})\) 是根据最小二乘法得到的代价函数（cost function），其中系数 \(\frac{1}{2}\) 的目的是简化求导计算，\(n\) 是训练样本数量。

$$ x_{0} = 1,\ h_{\theta}(\boldsymbol{x}) = \sum_{i = 0}^{d}\theta_{i}x_{i} = \boldsymbol{\theta}^{T}\boldsymbol{x},\ J(\boldsymbol{\theta}) = \frac{1}{2}\sum_{i = 1}^{n}(h_{\theta}(\boldsymbol{x}^{i}) - y^{i})^{2} $$

由于梯度方向是函数变化率最大的方向，所以可以使用梯度下降（gradient descent）算法，从某个初始 \(\boldsymbol{\theta}\) 向量开始，不断沿梯度反方向移动直到收敛。每次对所有 \(\theta_{j}\) 执行一下操作，该方法被称为批量梯度下降，其中 \(\alpha\) 是学习率（learning rate）。由于 \(J\) 是凸函数，所以梯度下降总是收敛到全局最小值点（假设学习率不太大）。

$$ \theta_{j} := \theta_{j} - \alpha\frac{\partial}{\partial\theta_{j}}J(\boldsymbol{\theta}) := \theta_{j} + \alpha\sum_{i = 1}^{n}(y^{(i)} - h_{\theta}(\boldsymbol{x}^{(i)}))x_{j}^{(i)} \rightarrow \boldsymbol{\theta} := \boldsymbol{\theta} + \alpha\sum_{i = 1}^{n}(y^{(i)} - h_{\theta}(\boldsymbol{x}^{(i)}))\boldsymbol{x}^{(i)} $$

由于批量梯度下降每次迭代都需要遍历所有样本，时间复杂度为 \(O(n)\)，如果训练集很大则比较耗时。替代方案是使用随机梯度下降，每次迭代使用单个训练样本的梯度更新参数。该方法可能无法收敛到最小值点，而是在最小值点附近振荡，通过在算法运行过程中逐渐将学习率降低至零，能够确保参数收敛到最小值点。

$$ \boldsymbol{\theta} := \boldsymbol{\theta} + \alpha(y^{(i)} - h_{\theta}(\boldsymbol{x}^{(i)}))\boldsymbol{x}^{(i)} $$

The normal equations

函数 \(f : \mathbb R^{n \times d} \to \mathbb R\) 将 \(n \times d\) 矩阵映射到实数，则函数 \(f\) 对矩阵 \(A\) 的导数如下。假设有 \(n\) 个训练样本，每个训练样本有 \(d\) 个输入变量，则 \(m \times (d + 1)\) 设计矩阵 \(X\) 如下，列数为 \(d + 1\) 是因为有额外的 \(x_{0} = 1\)。经过以下推导得到正规方程 \(X^{T}X\boldsymbol{\theta} = X^{T}\boldsymbol{y}\)，通过该方程可以直接求解全局最小值点 \(\theta\)，如果 \(X^{T}X\) 可逆的话。

$$ \nabla_{A}f(A) = \left[\begin{matrix} \frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1d}} \\ \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial A_{n1}} & \cdots & \frac{\partial f}{\partial A_{nd}} \\ \end{matrix}\right],\ X = \left[\begin{matrix} (\boldsymbol{x}^{(1)})^{T} \\ (\boldsymbol{x}^{(2)})^{T} \\ \vdots \\ (\boldsymbol{x}^{(n)})^{T} \end{matrix}\right],\ \boldsymbol{y} = \left[\begin{matrix} y^{1} \\ y^{2} \\ \vdots \\ y^{n} \end{matrix}\right] $$

$$ J(\boldsymbol{\theta}) = \frac{1}{2}(X\boldsymbol{\theta} - \boldsymbol{y})^{T}(X\boldsymbol{\theta} - \boldsymbol{y}) \rightarrow \nabla_{\theta}J(\boldsymbol{\theta}) = X^{T}X\boldsymbol{\theta} - X^{T}\boldsymbol{y} = 0 \rightarrow X^{T}X\boldsymbol{\theta} = X^{T}\boldsymbol{y} $$

Probabilistic interpretatoin

Locally weighted linear regression (optional reading)

线性回归中所有训练样本的权值都是 \(1\)，拟合 \(\boldsymbol{\theta}\) 使 \(\sum_{i}(y^{(i)} - \boldsymbol{\theta^{T}\boldsymbol{x}^(i)})^{2}\) 最小化。局部加权线性回归关注输入特征 \(\boldsymbol{x}\) 附近局部的训练样本，拟合 \(\boldsymbol{\theta}\) 使 \(\sum_{i}w^{(i)}(y^{(i)} - \boldsymbol{\theta}^{T}\boldsymbol{x}^{(i)})^{2}\) 最小化，其中 \(w^{(i)}\) 是非负权重。可以使用以下公式计算权重，其中 \(\tau\) 是带宽（bandwidth）参数，用于控制训练样本的权重随 \(\boldsymbol{x}^{i}\) 到 \(\boldsymbol{x}\) 的距离增大而减小的速度。

$$ w^{(i)} = \exp\left(-\frac{(x^{(i)} - x)^{2}}{2\tau^{2}}\right) $$

局部加权线性回归是非参数算法，而之前的线性回归是参数算法。参数算法有固定且有限数量的参数 \(\boldsymbol{\theta}\)，使用训练集拟合参数之后，就不需要使用训练集进行预测。而非参数算法需要保留的用于假设 \(h\) 的训练样本数量随训练集大小的增长而线性增长。

Classification and logistic regression