机器学习相关作业/公式应用

kingwzun / 2024-10-13 / 原文

work4

证明函数是否是凸函数

题目：要求证明两个性质：

Logistic函数 $f(\mathbf{x}; \beta) = \frac{1}{1 + e^{-\beta^T \mathbf{x}}}$ 对参数 $\beta$ 是非凸的。
对数似然函数 $L(\beta) = -y_0 \beta^T \mathbf{x} + \ln(1 + e^{\beta^T \mathbf{x}})$ 对 $\beta$ 是凸的，其中 $y_0$ 是常数。

基本知识补充

问题一：$f(\mathbf{x}; \beta)$ 什么含义？
可以理解为函数$ f(\mathbf{x}; \beta)$ 有 $\mathbf{x}$ 和 $\beta$两个变量。
但是 $ f(\mathbf{x}; \beta)$ 通常表示一个参数化的函数，$\mathbf{x}$ 和 $\beta$ 的先后顺序在符号上有不同的含义，通常，会把参数 $\beta$ 写在后面，以强调 $\mathbf{x}$ 是输入特征，而 $\beta$ 是控制模型行为的参数。具体来说：

$\mathbf{x}$ 是输入变量（特征向量），例如在机器学习模型中代表数据样本的特征。
$\beta$ 是参数向量，表示模型的参数，需要通过训练来优化。

进一步说明，假设我们有一个线性回归模型：$f(\mathbf{x}; \beta) = \beta^T \mathbf{x}$ 和 $f(\beta; \mathbf{x}) = \beta^T \mathbf{x}$。从数学上来说，这两者给出的输出值是相同的，因为内积运算在交换变量时不受影响。但是

前者强调：在固定 $\beta$ 的情况下，$\mathbf{x}$ 的变化如何影响输出。
后者强调：在固定 $\mathbf{x}$ 的情况下，$\beta$ 的变化如何影响输出。

举例： Logistic 回归中的 $f(\mathbf{x}; \beta)$ 在逻辑回归中，$ f(\mathbf{x}; \beta)$ 通常定义为：$f(\mathbf{x}; \beta) = \sigma(\beta^T \mathbf{x})$
其中：

$\beta^T \mathbf{x}$ 是参数 $\beta$ 和特征向量 $\mathbf{x}$ 的内积，结果是一个标量。
$\sigma(z)$ 是 Sigmoid 函数，定义为：$\sigma(z) = \frac{1}{1 + e^{-z}}$

这个函数的输出是一个介于 0 和 1 之间的数值，表示输入特征 $\mathbf{x}$ 属于某一类的概率。

解释含义：

输入 $\mathbf{x}$：代表特征或数据样本，它可以是多维的向量。
参数 $\beta$：表示模型参数的集合，它们是训练过程中需要调整的，以使模型更好地拟合训练数据。
输出 $ f(\mathbf{x}; \beta)$：模型对输入 $\mathbf{x}$ 的输出结果，通常代表一种预测值或概率。

问题二：$\beta^T$是什么
$\beta^T$ 表示向量 $\beta$ 的转置。它是将一个列向量变成行向量，或者将行向量变成列向量的操作。

具体来说：

如果 $\beta$ 是一个列向量，例如：

\[\beta = \begin{pmatrix} \beta_1 \\ \beta_2 \\ \vdots \\ \beta_n \end{pmatrix} \]
那么 $\beta^T$ 就是一个行向量： $\beta^T = (\beta_1, \beta_2, \ldots, \beta_n)$
如果 $\beta$ 是一个行向量：$\beta = (\beta_1, \beta_2, \ldots, \beta_n)$
那么 $\beta^T$ 就是一个列向量：

\[\beta^T = \begin{pmatrix} \beta_1 \\ \beta_2 \\ \vdots \\ \beta_n \end{pmatrix} \]

问题三：什么是凸函数，如何证明？
凸函数（Convex Function）是定义在一个凸集上的实值函数，其满足以下性质：如果在该集合中任意两点之间画一条直线，该直线上的函数值不低于连接两点的函数值。直观地说，凸函数的图形总是“向上弯曲”的。

几何含义：在凸函数图形中，连接两点 $(\mathbf{x}_1, f(\mathbf{x}_1))$ 和 $(\mathbf{x}_2, f(\mathbf{x}_2))$ 的线段不会位于函数图形的下方。

使用二阶导数条件（Hessian 矩阵）可以证明是否为凸函数(下面证明都是使用该方法)，即满足以下所有条件即可证明是凸函数：

适用于两次可微的函数。
计算函数的 Hessian 矩阵 $\nabla^2 f(\mathbf{x})$。
证明 $\nabla^2 f(\mathbf{x})$ 是正半定矩阵，即对于任意非零向量 $\mathbf{z}$，都有：$\mathbf{z}^T \nabla^2 f(\mathbf{x}) \mathbf{z} \geq 0$

举例：证明 $ f(x) = x^2 $ 是凸函数

前提： 函数 $ f(x) = x^2 $ 在 $\mathbb{R}$ 上可微且二次可微。
步骤 1：计算一阶导数和二阶导数
$f'(x) = 2x \quad \text{和} \quad f''(x) = 2$
步骤 2：检查二阶导数
$f''(x) = 2 > 0 \quad \forall x \in \mathbb{R}$由于二阶导数恒为正，Hessian 矩阵在此情况下是 $2$，是正半定的。因此，$ f(x) = x^2 $ 是凸函数。

问题四：Hessian 矩阵是什么？二阶导数就是Hessian 矩阵吗？
Hessian 矩阵的定义

Hessian 矩阵是一个多变量函数的二阶导数矩阵。具体来说，如果多变量函数( 即$\mathbf{x}$ 是一个 $ n $ 维向量) $ f(\mathbf{x}) $是一个可微两次的函数，其 Hessian 矩阵定义为：

\[\nabla^2 f(\mathbf{x}) = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{pmatrix} \]

其中：

$\frac{\partial^2 f}{\partial x_i^2}$ 是 $ f $ 对第 $ i $ 个变量的二阶偏导数。
$\frac{\partial^2 f}{\partial x_i \partial x_j}$ 是 $ f $ 对第 $ i $ 个变量和第 $ j $ 个变量的混合二阶偏导数。

二阶导数和 Hessian 矩阵的关系

单变量函数：对于单变量函数 $ f(x) $，Hessian 矩阵退化为一个 $ 1 \times 1 $ 的矩阵，也就是二阶导数 $ f''(x) $ 本身。它描述了函数的曲率。
- 例如，若 $ f(x) = x^2 $，则其二阶导数为 $ f''(x) = 2 $，对应的 Hessian 矩阵是 $ [2] $。
多变量函数：对于多变量函数 $ f(\mathbf{x}) $，Hessian 矩阵的维度为 $ n \times n $，它包含了所有变量之间的二阶变化率。
- 例如，若 $ f(x, y) = x^2 + y^2 $，则其 Hessian 矩阵为：
  \[\nabla^2 f(x, y) = \begin{pmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} \]

证明思路及其过程

证明思路

Logistic函数 $ f(\mathbf{x}; \beta)$ 对 $\beta$ 的非凸性：
Logistic函数 $ f(\mathbf{x}; \beta)$ 对参数 $\beta$ 不是凸的，是因为其二阶导数在某些情况下会出现负值。
通过计算 $ f(\mathbf{x}; \beta)$ 对 $\beta$ 的Hessian矩阵（即二阶导数矩阵），并证明它不是正半定的，从而证明其非凸性。
对数似然函数 $ L(\beta)$ 的凸性：
对数似然函数 $ L(\beta)$ 常用于Logistic回归中拟合参数 $\beta$。
证明凸性即证明 $ L(\beta)$ 对 $\beta$ 的二阶导数（即Hessian矩阵）是正半定的。

证明过程

证明 Logistic 函数 $f(\mathbf{x}; \beta) = \frac{1}{1 + e^{-\beta^T \mathbf{x}}}$ 对参数 $\beta$ 的非凸性

第一步：计算 Logistic 函数的一阶导数

Logistic函数可以重写为：

\[f(\mathbf{x}; \beta) = \frac{1}{1 + e^{-\beta^T \mathbf{x}}} \]

对参数 $\beta$ 求一阶导数：

\[\frac{\partial f(\mathbf{x}; \beta)}{\partial \beta} = \frac{e^{-\beta^T \mathbf{x}} \mathbf{x}}{\left(1 + e^{-\beta^T \mathbf{x}}\right)^2} \]

第二步：计算 Logistic 函数的二阶导数（Hessian矩阵）

接下来，对 $\frac{\partial f(\mathbf{x}; \beta)}{\partial \beta}$ 再对 $\beta$ 求导，得到Hessian矩阵：

\[\frac{\partial^2 f(\mathbf{x}; \beta)}{\partial \beta^2} = \frac{e^{-\beta^T \mathbf{x}} \mathbf{x} \mathbf{x}^T \left(1 - e^{-\beta^T \mathbf{x}}\right)}{\left(1 + e^{-\beta^T \mathbf{x}}\right)^3} \]

第三步：验证Hessian矩阵的正负定性

为了判断函数的凸性，我们需要验证Hessian矩阵的正负定性。可以观察到，当 $e^{-\beta^T \mathbf{x}}$ 较大时（即 $\beta^T \mathbf{x} $ 较小时），$1 - e^{-\beta^T \mathbf{x}}$ 为负，因此Hessian矩阵的部分项可能为负值。

由于Hessian矩阵不是正半定的，说明Logistic函数对参数 $\beta$ 是 非凸的。

证明对数似然函数 $L(\beta) = -y_0 \beta^T \mathbf{x} + \ln(1 + e^{\beta^T \mathbf{x}})$ 对参数 $\beta$ 的凸性

第一步：计算对数似然函数$L(\beta)$的一阶导数

\[\frac{\partial L(\beta)}{\partial \beta} = -y_0 \mathbf{x} + \frac{e^{\beta^T \mathbf{x}}}{1 + e^{\beta^T \mathbf{x}}} \mathbf{x} \]

第二步：计算对数似然函数的二阶导数（Hessian矩阵）
对一阶导数再求导，得到Hessian矩阵：

\[\frac{\partial^2 L(\beta)}{\partial \beta^2} = \frac{e^{\beta^T \mathbf{x}}}{(1 + e^{\beta^T \mathbf{x}})^2} \mathbf{x} \mathbf{x}^T \]

第三步：验证Hessian矩阵的正定性

Hessian矩阵的结构中，$\frac{e^{\beta^T \mathbf{x}}}{(1 + e^{\beta^T \mathbf{x}})^2}$ 始终为非负数，且 $\mathbf{x} \mathbf{x}^T$ 是正半定矩阵。
因此，Hessian矩阵是 正半定的，这表明对数似然函数 $ L(\beta) $ 对参数 $\beta$ 是凸的。

解惑

为什么二阶导数会出现$x^T$

关键在于理解 Hessian 矩阵的计算原理及向量外积的来源。

背景知识：

梯度 $\nabla l(\beta)$：对多维参数 $\beta$ 求导数，结果是一个向量。它代表的是损失函数相对于每个参数的变化率。

Hessian 矩阵 $\nabla^2 l(\beta)$：对梯度 $\nabla l(\beta)$ 再求一次导数，结果是一个矩阵。Hessian 矩阵捕捉的是损失函数相对于参数的二阶变化，即二阶偏导数。

以损失函数对数似然函数：$ l(\beta) = \sum_{i=1}^m \left(-y_i \beta^T x_i + \ln\left(1 + e^{\beta^T x_i}\right)\right)$ 为例

计算一阶导数 $\nabla l(\beta)$：
对于第 $ i $ 项，$\nabla l(\beta)$ 的推导过程如下：

对 $-y_i \beta^T x_i$ 求导：

$ \nabla (-y_i \beta^T x_i) = -y_i x_i $
对 $\ln\left(1 + e^{\beta^T x_i}\right)$ 求导：
- 设 $\sigma(\beta^T x_i) = \frac{e^{\beta^T x_i}}{1 + e^{\beta^T x_i}}$，即 Sigmoid 函数。
- $\nabla \left(\ln(1 + e^{\beta^T x_i})\right)$ 的导数为：$\frac{e^{\beta^T x_i}}{1 + e^{\beta^T x_i}} x_i = \sigma(\beta^T x_i) x_i$
综合一阶导数：

$ \nabla l(\beta) = \sum_{i=1}^m \left(\sigma(\beta^T x_i) x_i - y_i x_i\right) $
或者写作：
$ \nabla l(\beta) = \sum_{i=1}^m \left(\left(\sigma(\beta^T x_i) - y_i\right) x_i\right) $

计算二阶导数 $\nabla^2 l(\beta)$（Hessian 矩阵）：
计算 Hessian 矩阵，即对梯度向量 $\nabla l(\beta)$ 对 $\beta$ 再求导数：

$ \nabla^2 l(\beta) = \sum_{i=1}^m \nabla \left(\sigma(\beta^T x_i) x_i - y_i x_i\right) $

注意到，$-y_i x_i$ 是一个关于 $\beta$ 的线性项，它的导数为零，所以我们只需要对 $\sigma(\beta^T x_i) x_i$ 进行求导。

对 $\sigma(\beta^T x_i) x_i$ 求导：
这里是关键步骤：$\sigma(\beta^T x_i)$ 是一个标量，而 $ x_i $ 是一个向量。

为什么$\sigma(\beta^T x_i)$ 是一个标量，而 $ x_i $ 是一个向量？
因为

$\beta$ 是一个向量，假设它的维度是 $n$，表示模型的参数：$\beta = (\beta_1, \beta_2, \ldots, \beta_n)^T$

$\boldsymbol{x}_i$ 是一个向量，维度同样是 $n$，表示第 $i$ 个样本的特征：$\boldsymbol{x}_i = (x_{i1}, x_{i2}, \ldots, x_{in})^T$

内积 $\beta^T \boldsymbol{x}_i$ 是一个标量，即：$\beta^T \boldsymbol{x}_i = \beta_1 x_{i1} + \beta_2 x_{i2} + \ldots + \beta_n x_{in}$

内积的结果是一个实数（标量），因为它是将向量 $\beta$ 和 $\boldsymbol{x}_i$ 对应元素相乘并求和得到的。

点击查看后续更详细解释

2. Sigmoid 函数 $\sigma(z)$：

Sigmoid 函数的定义为：

\[\sigma(z) = \frac{1}{1 + e^{-z}} \]
其中，$z$ 是一个标量输入，$\sigma(z)$ 的输出也是一个标量，取值范围在 $ (0, 1) $ 之间。
在这个问题中，$z = \beta^T \boldsymbol{x}_i$，所以：

\[\sigma(\beta^T \boldsymbol{x}_i) = \frac{1}{1 + e^{-\beta^T \boldsymbol{x}_i}} \]
这是一个标量，因为它是对内积结果（标量）进行非线性变换。

3. 向量 $\boldsymbol{x}_i$ 的性质：

$\boldsymbol{x}_i$ 是一个向量，维度为 $n$，表示第 $i$ 个样本的特征向量。它在 Sigmoid 函数之外起作用，在计算梯度时需要考虑它的分量。

4. 结合梯度和 Hessian 矩阵：

当我们计算 梯度 $\nabla l(\beta)$ 时，会对每个 $\beta_j$（$\beta$ 的第 $j$ 个分量）求导。因为 $\sigma(\beta^T \boldsymbol{x}_i)$ 是标量，所以对它求导时，向量 $\boldsymbol{x}_i$ 会参与进来，表示为：

\[\nabla_{\beta} \sigma(\beta^T \boldsymbol{x}_i) = \sigma(\beta^T \boldsymbol{x}_i) (1 - \sigma(\beta^T \boldsymbol{x}_i)) \boldsymbol{x}_i \]
当进一步计算 Hessian 矩阵 $\nabla^2 l(\beta)$ 时，由于梯度项中有 $\boldsymbol{x}_i$，因此会产生向量的外积 $\boldsymbol{x}_i \boldsymbol{x}_i^T$，这个外积结果是一个 $n \times n$ 的矩阵。

总结：

$\sigma(\beta^T \boldsymbol{x}_i)$ 是一个标量，因为它是对内积 $\beta^T \boldsymbol{x}_i$ 的结果（一个数值）进行 Sigmoid 变换。
$\boldsymbol{x}_i$ 是一个向量，因为它表示样本的特征向量（有多个维度）。
在计算梯度和 Hessian 时，由于 $\boldsymbol{x}_i$ 参与到对 $\beta$ 的导数中，会导致出现 $\boldsymbol{x}_i \boldsymbol{x}_i^T$ 这样的外积形式。

我们应用乘积法则来对这个项求导：

$ \nabla \left(\sigma(\beta^T x_i) x_i\right) = \nabla \sigma(\beta^T x_i) \otimes x_i + \sigma(\beta^T x_i) \nabla (x_i) $

计算 $\nabla \sigma(\beta^T x_i) \otimes x_i$：
- $\sigma(\beta^T x_i)$ 对 $\beta$ 的导数为：
  
  $ \nabla \sigma(\beta^T x_i) = \sigma(\beta^T x_i) (1 - \sigma(\beta^T x_i)) x_i $
  
  这里使用了 Sigmoid 函数的导数性质。
- 将其代入，我们得到：
  
  $ \nabla \sigma(\beta^T x_i) \otimes x_i = \sigma(\beta^T x_i) (1 - \sigma(\beta^T x_i)) x_i x_i^T $
  - $\otimes$ 表示外积运算，$ x_i x_i^T $ 是外积的结果。
  - 由于 $\nabla \sigma(\beta^T x_i)$ 是一个 $ n $-维向量，外积的结果 $ x_i x_i^T $ 是一个 $ n \times n $ 的矩阵。
计算 $\sigma(\beta^T x_i) \nabla (x_i)$：
- 这里 $ x_i $ 是相对于 $\beta$ 的常数向量，因此它的导数为零。这个部分对 Hessian 没有贡献。
综合二阶导数：

最终得到 Hessian 矩阵：

$ \nabla^2 l(\beta) = \sum_{i=1}^m \sigma(\beta^T x_i) (1 - \sigma(\beta^T x_i)) x_i x_i^T $

为什么会出现 $ x_i x_i^T $：

在对梯度求二阶导数时，由于 Sigmoid 函数的导数是一个标量，但我们同时需要对向量 $ x_i $ 的分量进行导数运算，这就产生了向量之间的外积 $ x_i x_i^T $。
外积 $ x_i x_i^T $ 的出现 是因为当我们在多维空间中对标量函数进行二次导数时，需要考虑所有分量之间的相互关系。

总结：