斯坦福CS229（吴恩达授）学习笔记（1）

CS229-notes1-part1

• 说明
• 正文
• • Linear Regression
  • • LMS algorithm（迭代法、梯度下降法）
    • The normal equations（解析法）

说明

此笔记 是cs229-notes1讲义中的第一部分学习内容，与B站上的“02 监督学习应用.梯度下降”视频对应，主要是对讲义中一些推理的补充以及一些重点内容的记录，另外还会附加该部分相对应的习题解答和算法的C++实现。
B站相关视频：猛击此处
Stanford原视频及讲义等相关材料：猛击此处

正文

Linear Regression

LMS algorithm（迭代法、梯度下降法）

1.如果令x_{0}=1，则hypothesis可以表示为（样本点x是多维输入向量，x_i表示其中的第i个特征维度）

h(x)=\sum_{i=0}^n \theta_{i}x_{i}=\theta^{T}x \tag{1}

这里n是the number of input variables (not counting x_{0})。
2.对于a training set of more than one example的情况，cost函数（此时x^{(i)}是第i个样本点，即一个多维输入向量）

J(\theta)=\frac{1}{2}\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})^2 \tag{2}

所以

\begin{aligned} \frac{\partial}{\partial\theta_{j}}J(\theta) =&\frac{\partial}{\partial\theta_{j}}\frac{1}{2}\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})^2 \\ =&\frac{1}{2}\sum_{i=1}^m\frac{\partial}{\partial\theta_{j}}(h_{\theta}(x^{(i)})-y^{(i)})^2\\ =&\frac{1}{2}\sum_{i=1}^m·2·(h_{\theta}(x^{(i)})-y^{(i)})·\frac{\partial}{\partial\theta_{j}}h_{\theta}(x^{(i)})\\ =&\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})·\frac{\partial}{\partial\theta_{j}}·\theta^{T}x^{(i)}\\ =&\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}\tag{3} \end{aligned}

The normal equations（解析法）

1.关于矩阵迹（只有方阵才讲迹 ）的一些公式：
（1）迹的定义：trA=\sum_{i=1}^nA_{ii}；
（2）tra=a，当a为实数（real number）的时候；
（3）交换：trAB=trBA，注意A和B此处可以不是方阵，证明如下，
\begin{aligned} trAB=&\sum_{i=1}^n(AB)_{ii}\\ =&\sum_{i=1}^n\sum_{s=1}^ma_{is}b_{si}\\ =&\sum_{i=1}^n(a_{i1}b_{1i}+a_{i2}b_{2i}+a_{i3}b_{3i}+...+a_{im}b_{mi})\\ =&\sum_{s=1}^m\sum_{i=1}^nb_{si}a_{is}\\ =&\sum_{s=1}^m(BA)_{ss}\\ =&trBA \end{aligned}
推论1：trABC=trCAB=trBCA；
推论2：trABCD=trDABC=trCDAB=trBCDA；
（4）转置：trA=trA^T；
（5）分解：tr(A+B)=trA+trB；
（6）因子：traA=atrA。
2.关于矩阵迹求偏导的一些公式：
（1）\nabla_{A}trAB=B^{T}，证明如下，
\begin{aligned} \nabla_{A}trAB=&\nabla_{A}\sum_{i=1}^n(AB)_{ii}\\ =&\nabla_{A}\sum_{i=1}^n\sum_{s=1}^ma_{is}b_{si}\\ =&\left[ \begin{matrix} \frac{\partial \sum_{i=1}^n\sum_{s=1}^ma_{is}b_{si}}{\partial a_{11}} & \cdots & \frac{\partial \sum_{i=1}^n\sum_{s=1}^ma_{is}b_{si}}{\partial a_{1m}} \\ \vdots & \ddots & \vdots \\ \frac{\partial \sum_{i=1}^n\sum_{s=1}^ma_{is}b_{si}}{\partial a_{n1}} & \cdots & \frac{\partial \sum_{i=1}^n\sum_{s=1}^ma_{is}b_{si}}{\partial a_{nm}} \end{matrix} \right]\\ =&\left[ \begin{matrix} b_{11} & \cdots & b_{m1}\\ \vdots & \ddots & \vdots \\ b_{1n} & \cdots & b_{mn} \end{matrix} \right]\\ =&B^T \end{aligned}
推论：\nabla_{A}trA^{T}B=B（利用转置公式）
（2）\nabla_{A^{T}}f(A)=(\nabla_{A}f(A))^{T}，证明如下，
\begin{aligned} \nabla_{A^{T}}f(A)=&\left[ \begin{matrix} \frac{f}{\partial a_{11}} & \cdots & \frac{f}{\partial a_{m1}} \\ \vdots & \ddots & \vdots \\ \frac{f}{\partial a_{1n}} & \cdots & \frac{f}{\partial a_{mn}} \end{matrix} \right]\\ =&\left[ \begin{matrix} \frac{f}{\partial a_{11}} & \cdots & \frac{f}{\partial a_{1n}} \\ \vdots & \ddots & \vdots \\ \frac{f}{\partial a_{m1}} & \cdots & \frac{f}{\partial a_{mn}} \end{matrix} \right]^{T}\\ =&(\nabla_{A}f(A))^{T} \end{aligned}
（3）\nabla_{A}trABA^{T}C=CAB+C^{T}AB^{T}，证明如下，来源猛击此处

（4）\nabla_{A}|A|=|A|(A^{-1})^{T}，证明如下，
根据行列式展开的拉普拉斯法则，a_{ij}为A的元素，A_{ij}^{'}为a_{ij}对应的伴随行列式（代数余子式），则展开第i行时（展开方法猛击此处）
|A|=\sum_{j}a_{ij}A_{ij}^{'}
所以
\begin{aligned} \nabla_{A}|A|=&\nabla_{A}\sum_{j}a_{ij}A_{ij}^{'} \end{aligned}
因为A_{ij}^{'}与a_{ij}没有关系，所以\frac{\partial \sum_{j}a_{ij}A_{ij}^{'}}{\partial a_{ij}}=A_{ij}^{'}，故\nabla_{A}|A|=A^{'}，其中A^{'}=(A^{*})^{T}，A^{*}为A的伴随矩阵
而A^{-1}=A^{*}/|A|=(A^{'})^{T}/|A|，所以(A^{'})^{T}=|A|A^{-1}，即A^{'}=|A|(A^{-1})^{T}，即证。