CS229学习笔记（3）

CS229_3-正规方程

正规方程

上一小节中，我们使用批量梯度下降算法，通过不断迭代以求得最佳参数 $\theta$ 的值。本小节将介绍另一种方法——正规方程（The Normal Euqations）来计算出最佳参数 $\theta$ 的值。

在介绍正规方程法之前，我们先看看一些基本概念。

Matrix Derivatives

对于一个 $m * n$ 的矩阵到实数的函数映射 $f: R^{m * n} \mapsto R$ ，其关于 $A$ 的导数为：

$\nabla_A f(A) = \left[ \begin{matrix} \frac{\partial f}{\partial A_{11}} & \dots & \frac{\partial f}{\partial A_{1n}} \\ \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial A_{m1}} & \dots & \frac{\partial f}{\partial A_{mn}} \end{matrix} \right]$

其中 $A$ 为 $m * n$ 的矩阵。

便于理解，我们不妨假设矩阵 $A$ 为：

$A = \left[ \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right]$

函数映射 $f: R^{2 * 2} \mapsto R$ 为：

$f(A) = \frac{3}{2}A_{11} + 5A_{12}^2 + A_{21}A_{22}$

根据上述公式，我们可得：

$\nabla_A f(A) = \left[ \begin{matrix} \frac{3}{2} & 10A_{12} \\ A_{22} & A_{21} \end{matrix} \right]$

对于 $n * n$ 矩阵A，我们将矩阵A对角线上元素的和定义为矩阵A的迹：

$trA = \sum\limits_{i=1}^n A_{ii}$

其中若矩阵A为 $1 * 1$ ，即为一实数，则其迹为本身， $trA = A$ 。

一些常用性质如下：

$trAB = trBA \\ trABC = trCAB = trBCA \\ trA = trA^T \\ tr(A+B) = tr(A) + tr(B) \\ traA = atrA \\$

结合矩阵导数的概念有如下性质：

$\begin{align} \nabla_A trAB = B^T \tag{1} \\ \nabla_{A^T} f(A) = (\nabla_A f(A))^T \tag{2} \\ \nabla_A trABA^TC = CAB + C^TAB^T \tag{3} \\ \nabla_A |A| = |A|(A^{-1})^T \tag{4} \end{align}$

其中等式（1）要求 $AB$ 为方阵；等式（3）要求 $ABA^TC$ 为方阵；等式（4）要求矩阵A为非奇异矩阵，即可逆； $|A|$ 表示矩阵A的行列式。

Least Squares Revisited

好了，现在让我们开始介绍正规方程法，以找到最佳参数 $\theta$ 的值最小化代价函数 $J(\theta)$ 。

在给定训练集中，我们可构建一个维度为 $m * n$ 的矩阵 $X$ ，其中 $m$ 为样本个数， $n$ 为每个样本的特征变量个数。

$X = \left[ \begin{matrix} - \, (x^{(1)})^T \, - \\ - \, (x^{(2)})^T \, - \\ \vdots \\ - \, (x^{(m)})^T \, - \end{matrix} \right]$

同样，向量 $Y$ 为：

$Y = \left[ \begin{matrix} (y^{(1)})^T \\ (y^{(2)})^T \\ \vdots \\ (y^{(m)})^T \end{matrix} \right]$

根据 $h_\theta(x^{(i)}) = (x^{(i)})^T\theta$ ，我们可得：

$\begin{aligned} X\theta - Y &= \begin{bmatrix} (x^{(1)})^T\theta \\ (x^{(2)})^T\theta \\ \vdots \\ (x^{(m)})^T\theta \end{bmatrix} - \begin{bmatrix} (y^{(1)})^T \\ (y^{(2)})^T \\ \vdots \\ (y^{(m)})^T \end{bmatrix} \\ &= \left[ \begin{matrix} h_\theta(x^{(1)}) - y^{(1)} \\ h_\theta(x^{(2)}) - y^{(2)} \\ \vdots \\ h_\theta(x^{(m)}) - y^{(m)} \end{matrix} \right] \end{aligned}$

又因为对于向量 $z$ ，有 $z^Tz = \sum_{i}z_i^2$ 。故我们可得：

$J(\theta) = \frac{1}{2}(X\theta - Y)^T(X\theta - Y) = \frac{1}{2}\sum_{i=1}^m(h_\theta(x_{(i)}) - y^{(i)})^2$

所以，我们对代价函数 $J(\theta)$ 求偏导，可得：

$\begin{align} \nabla_\theta J(\theta) &= \frac{1}{2}\nabla_\theta (\theta^TX^T - Y^T)(X\theta - Y) \tag{1} \\ &= \frac{1}{2}\nabla_\theta (\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY) \tag{2} \\ &= \frac{1}{2}\nabla_\theta tr(\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY) \tag{3} \\ &= \frac{1}{2}\nabla_\theta (tr\theta^TX^TX\theta - 2trY^TX\theta) \tag{4} \\ &= \frac{1}{2}(X^TX\theta + X^TX\theta - 2X^TY) \tag{5} \\ &= X^TX\theta - X^TY \tag{6} \end{align}$

其中等式（1）类似于完全平方展开得到等式（2）；等式（2）应用 $trA = A$ 得到等式（3）；等式（3）应用 $Y^TY$ 为实数，且实数的转置为其本身，从而得到等式（4）；等式（4）应用 $trAB = trBA$ ， $\nabla_AAB=B^T$ 和 $\nabla_A trABA^TC = CAB + C^TAB^T$ 得到等式（5）。

最后，我们令该偏导为 $0$ 可得：

$X^TX\theta = X^TY \Rightarrow \theta = (X^TX)^{-1}X^TY$

从而，我们求出了参数 $\theta$ 的值。

最后编辑于：2019.04.22 13:45:35

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 199,064评论 5赞 466
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 83,606评论 2赞 376
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 146,011评论 0赞 328
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 53,550评论 1赞 269
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 62,465评论 5赞 359
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 47,919评论 1赞 275
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,428评论 3赞 390
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,075评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,208评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,185评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,191评论 1赞 328
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,914评论 3赞 316
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,482评论 3赞 302
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,585评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,825评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,194评论 2赞 344
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,703评论 2赞 339

CS229学习笔记（3）

CS229_3-正规方程

正规方程

Matrix Derivatives

Least Squares Revisited

推荐阅读更多精彩内容