矩阵求导与实例


图片名称

机器学习的算法中很多都牵涉到了矩阵求导,本文将对矩阵求导做简要阐述。
一方面举一些简单的例子,另一方面推导了SVM,linear regressionlogistic regression等。

缘由

机器学习的很多算法表示中都采用了矩阵的形式,对算法的描述分析中就涉及到了对向量、对矩阵的求导。
比如SVM、linear regression的推导等。

布局

矩阵求导有两种布局:

  • 分子布局(numerator layout)
  • 分母布局(denominator layout)

下面用向量$\mathrm{\mathbf{y}}$对标量$x$求导简单说明这两种布局的区别。
我们假定所有的向量都是列向量。
$$\mathbf{y}=\begin{bmatrix}y_{1}\
y_{2}\
\vdots\
y_{m}
\end{bmatrix}$$

在分子布局下:
$$\frac{\partial\mathbf{y}}{\partial x}=\begin{bmatrix}\frac{\partial y_{1}}{\partial x}\
\frac{\partial y_{2}}{\partial x}\
\vdots\
\frac{\partial y_{m}}{\partial x}
\end{bmatrix}$$

在分母布局下:
$$\frac{\partial\mathbf{y}}{\partial x}=\begin{bmatrix}\frac{\partial y_{1}}{\partial x} & \frac{\partial y_{2}}{\partial x} & \cdots & \frac{\partial y_{m}}{\partial x}\end{bmatrix} %]]>$$

在下面的推导中,都将采用分母布局,也就是向量(列)对标量求导的结果都是行向量。(采用这种布局的主要原因是向量对向量的求导就是一个矩阵了)

求导的类别

求导大致分为5类:

  1. 向量对标量
  2. 标量对向量
  3. 向量对向量
  4. 矩阵对向量
  5. 向量对矩阵

矩阵求导的大致规则如下:
对标量求导结果都要转置,而标量对向量或者矩阵求导的话位置不变。
简单来说,上变下不变。

向量对标量求导:
$$\frac{\partial\mathbf{y}}{\partial x}=\begin{bmatrix}\frac{\partial y_{1}}{\partial x} & \frac{\partial y_{2}}{\partial x} & \cdots & \frac{\partial y_{m}}{\partial x}\end{bmatrix} %]]>$$

标量对向量求导:
$$\frac{\partial y}{\partial\mathbf{x}}=\begin{bmatrix}\frac{\partial y}{\partial x_{1}}\
\frac{\partial y}{\partial x_{2}}\
\vdots\
\frac{\partial y}{\partial x_{m}}
\end{bmatrix}$$

向量对向量求导:
$$\mathbf{x}=\begin{bmatrix}x_{1}\
x_{2}\
\vdots\
x_{n}
\end{bmatrix}$$
$$\mathbf{y}=\begin{bmatrix}y_{1}\
y_{2}\
\vdots\
y_{m}
\end{bmatrix}$$
$$\frac{\partial\mathbf{y}}{\partial\mathbf{x}}=\begin{bmatrix}\frac{\partial y_{1}}{\partial x_{1}} & \frac{\partial y_{2}}{\partial x_{1}} & \cdots & \frac{\partial y_{m}}{\partial x_{1}}\\
\frac{\partial y_{1}}{\partial x_{2}} & \frac{\partial y_{2}}{\partial x_{2}} & \cdots & \frac{\partial y_{m}}{\partial x_{2}}\\
\vdots & \vdots & \ddots & \vdots\\
\frac{\partial y_{1}}{\partial x_{n}} & \frac{\partial y_{2}}{\partial x_{n}} & \cdots & \frac{\partial y_{m}}{\partial x_{n}}
\end{bmatrix} %]]>$$

矩阵对标量求导:
$$\frac{\partial\mathbf{y}}{\partial x}=\begin{bmatrix}\frac{\partial y_{11}}{\partial x} & \frac{\partial y_{21}}{\partial x} & \cdots & \frac{\partial y_{m1}}{\partial x}\\
\frac{\partial y_{12}}{\partial x} & \frac{\partial y_{22}}{\partial x} & \cdots & \frac{\partial y_{m2}}{\partial x}\\
\vdots & \vdots & \ddots & \vdots\\
\frac{\partial y_{1n}}{\partial x} & \frac{\partial y_{2n}}{\partial x} & \cdots & \frac{\partial y_{mn}}{\partial x}
\end{bmatrix}$$

标量对矩阵求导:
$$\frac{\partial y}{\partial\mathbf{X}}=\begin{bmatrix}\frac{\partial y}{\partial x_{11}} & \frac{\partial y}{\partial x_{12}} & \cdots & \frac{\partial y}{\partial x_{1q}}\\
\frac{\partial y}{\partial x_{21}} & \frac{\partial y}{\partial x_{22}} & \cdots & \frac{\partial y}{\partial x_{2q}}\\
\vdots & \vdots & \ddots & \vdots\\
\frac{\partial y}{\partial x_{p1}} & \frac{\partial y}{\partial x_{p2}} & \cdots & \frac{\partial y}{\partial x_{pq}}
\end{bmatrix} %]]>$$

从简单的例子说起

例子1:

$$\mathbb{y} = \mathbb{a}^\mathrm{T}\mathbb{x}$$

其中,$\mathbb{y} \in \mathbb{R}, \mathbb{a} \in \mathbb{R}^{n \times 1}, \mathbb{x} \in \mathbb{R}^{n \times 1}$。

属于标量对向量求导,所以有:
$$\frac{\partial y}{\partial x} = a$$

例子2:

$$\mathbb{y} = \mathrm{A}\mathrm{x}$$

其中,$\mathbb{y} \in \mathbb{R}^{m \times 1}, \mathrm{A} \in \mathbb{R}^{m \times n}, \mathbb{x} \in \mathbb{R}^{n \times 1}$。

属于向量对向量求导,所以有:
$$\frac{\partial y}{\partial x} = \mathrm{A}^\mathrm{T}$$

例子3:
$$\mathbb{y} = \mathrm{A}\mathrm{u}(x)$$

其中,$\mathbb{y} \in \mathbb{R}^{m \times 1}, \mathrm{A} \in \mathbb{R}^{m \times n}, \mathrm{u} \in \mathbb{R}^{n \times 1},\mathbb{x} \in \mathbb{R}^{p \times 1}$。

属于向量对向量的求导,所以有:
$$\frac{\partial y}{\partial x} = \frac{\partial u}{\partial x} \mathrm{A}^{\mathrm{T}}$$

例子4:

$$\mathbb{y} = \mathrm{a(x)}\mathrm{u}(x)$$

其中,$\mathbb{y} \in \mathbb{R}^{m \times 1}, \mathrm{a} \in \mathbb{R}, \mathrm{u} \in \mathbb{R}^{m \times 1},\mathbb{x} \in \mathbb{R}^{n \times 1}$。

属于向量对向量的求导,所以有:
$$\frac{\partial y}{\partial x} = \frac{\partial u}{\partial x} \mathrm{a}+\frac{\partial a}{\partial x} \mathrm{u}^{\mathrm{T}}$$

假如已知:
$$
\begin{split}
a(x)&=Bx\
u(x)&=Cx
\end{split}$$

其中,$\mathrm{B} \in \mathbb{R}^{1 \times n}, \mathrm{C} \in \mathbb{R}^{m \times n}$
那么,
$$\frac{\partial y}{\partial x} =\mathrm{C}^{\mathrm{T}}\mathrm{a}+\mathrm{B}^{\mathrm{T}}\mathrm{u}^{\mathrm{T}}$$

例子5:
$$\mathrm{f} = \mathbf{x}^{\mathrm{T}}\mathbf{Ay(x)}$$
那么,
$$\frac{\partial f}{\partial x} =Ay+\frac{\partial y}{\partial x} A^T x$$

其中,$\mathbf{x}\in\mathbb{R}^{m\times1},\mathbf{y}\in\mathbb{R}^{n\times1},\mathbf{A}\in\mathbb{R}^{m\times n},\mathbf{f}\in\mathbb{R}$。

上面的式子,当$\mathbb{y(x)}=x$时,也就是$m=n$时。
$$
\begin{split}
&\mathrm{f}& = \mathbf{x}^{\mathrm{T}}\mathrm{A}\mathbf{x}\
&\frac{\partial f}{\partial x} &= (A+A^T)x
\end{split}$$

例子6:

$$\mathbb{f} = \mathbf{a}^{\mbox{T}}\mathbf{xx}^{\mbox{T}}\mathbf{b} ,\mathbf{a,b,x}\in\mathbb{R}^{m\times1}$$


$$\frac{\partial f}{\partial x} = a(x^Tb) + b(a^Tx) = (ab^T+ba^T)x $$

实例

SVM的对偶形式转换

SVM的原形式(primary form)是:
$$
\begin{split}
&\min_{w,b} \quad &\frac{1}{2} w^Tw\
&s.t. & y_n(w^Tx_n+b) \ge1
\end{split}$$

SVM的对偶形式(dual form)是:

$$\begin{split}
&\min_{w,b} \max_{\alpha\ge 0} & \frac{1}{2} w^Tw + \sum_{n=1}^N \alpha_n [1- y_n(w^Tx_n+b)] \
&\max_{\alpha\ge 0} \min_{w,b} &\frac{1}{2} w^Tw + \sum_{n=1}^N \alpha_n [1- y_n(w^Tx_n+b)]\end{split}$$

上升分别对$w,b$求导后,得到
$$\begin{split}
w &= \sum_{n=1}^N \alpha_n y_n x_n\
\sum_{n=1}^N \alpha_n y_n &= 0
\end{split}$$

代入原式中,有
$$\begin{split}\min_\alpha \frac{1}{2}\sum_{n=1}^N&\sum_{m=1}^N \alpha_n \alpha_m y_n y_m {x_m}^T x_n - \sum_{n=1}^N \alpha_n \
s.t. \quad \sum_{n=1}^N \alpha_n y_n &= 0 \
\alpha_n &\ge 0
\end{split}$$

这个对偶问题,可以用相应的quadprog包求解。其中,$\sum_{n=1}^N\sum_{m=1}^N \alpha_n \alpha_m y_n y_m {x_m}^T x_n$是矩阵$\mathbb{\alpha}^T \mathrm{Q}\mathbb{\alpha}$。$y_n y_m {x_m}^T x_n$是矩阵中m行n列的元素。这个元素再乘以$ \alpha_n \alpha_m $。
同时,这个也是$w^Tw$的内积。可以理解为把$w$拆开多项,每一项分别做内积然后相加,就像多次项展开公式一样。

Soft-SVM对偶形式转换

SVM的原形式(primary form)是:
$$
\begin{split}
&\min_{w,b,\varepsilon} \quad &\frac{1}{2} w^Tw + C \sum_{n=1}^N \varepsilon_n \
&s.t. & y_n(w^Tx_n+b) \ge1-\varepsilon_n \
& &\varepsilon_n \ge 0
\end{split}$$

对偶形式是:
$$\begin{split}\min_\alpha \frac{1}{2}\sum_{n=1}^N&\sum_{m=1}^N \alpha_n \alpha_m y_n y_m {x_m}^T x_n - \sum_{n=1}^N \alpha_n \\
s.t. \quad \sum_{n=1}^N \alpha_n y_n &= 0 \\
0 \le\alpha_n &\le C
\end{split}$$

线性回归

原问题是:
$${E}_{in} (w) = \frac{1}{N} \sum_{n=1}^N (w^T x -y)^2=\frac{1}{N} \Vert XW-Y\Vert ^2$$

当最佳值存在时:
$$\nabla E_{in}(w)=\frac{2}{N} X^T(XW-Y)$$

所以有:
$$\begin{split}
W &= (X^TX)^{-1} X^TY \\
W &=X^\dagger Y
\end{split}$$

logistic回归

首先,定义需要的函数:
$$\begin{split}
\theta(s) &= \frac{e^s}{1+e^s} = \frac{1}{1+e^{-s}} \\
h(x)&= \theta(w^Tx)
\end{split}$$
接着,根据最大似然,并且利用 $1-h(x) = h(-x)$的性质,最大化点出现的概率:
$$\begin{split}
&\max \prod \theta(y_n w^T x_n) \\
&\min \sum_{n=1}^N ln(1+exp(-y_nw^Tx_n))
\end{split}$$

上式对$w$的倒数为0,所以有:

$$\begin{split}
&\min \sum_{n=1}^N ln(1+exp(-y_nw^Tx_n)) \\
s.t. & \sum_{n=1}^N \theta(-y_n w^T x_n)(-y_nx_n) = 0
\end{split}$$

下面,可以利用GD或者SGD求解。

GD:
$$\begin{split}
\nabla E_{in} (w_t) &= \frac{1}{N} \sum_{n=1}^N \theta(-y_n w^T x_n)(-y_nx_n) \
w_{t+1}&= w_t - \eta \nabla E_{in} (w_t)
\end{split}$$

SGD:

$$w_{t+1}= w_t -\eta \theta(-y_n w^T x_n)(-y_nx_n)$$

参考资料

  1. 闲话矩阵求导