约定：共m个样本，\(x^{(i)}_j\)表示第i个样本中第j个特征，将各样本\(x^{(i)}\)横卧堆积形成X，即横向索引为各样本，纵向索引为各特征，维度为m*(d+1)。y和w均为向量，w维度为d+1。
则代价函数\(J(w) = \dfrac{1}{2m}\sum_{i=1}^m(h(x^{(i)}) - y^{(i)})^2 = \dfrac{1}{2m}\sum_{i=1}^m(w^T x^{(i)} - y^{(i)})^2\)
则w各分量的梯度为\(\dfrac{\partial J}{\partial w_j} = \dfrac{1}{m} \sum_{i=1}^m (w^T x^{(i)} - y^{(i)}) x^{(i)}_j\)
整理成矢量表达为\(\dfrac{\partial J}{\partial w} = \dfrac{1}{m} X^T (Xw - y)\)
方法1：梯度下降法(Ng视频方法)\(w \leftarrow w - \alpha \dfrac{\partial J}{\partial w}\)
方法2：正规方程法(Normal Equation，林轩田视频方法)：\(w = (X^T X)^{-1} X^T y\)
注意到，伪逆矩阵中有逆矩阵的计算，逆矩阵是否一定存在？一般情况下，只要满足样本数量N远大于样本特征维度d+1，就能保证矩阵的逆是存在的，称之为非奇异矩阵。但是如果是奇异矩阵，不可逆怎么办呢？其实，大部分的计算逆矩阵的软件程序，都可以处理这个问题，也会计算出一个逆矩阵。所以，一般伪逆矩阵是可解的。
梯度下降法和正规方程法优缺点。
正规方程法泛化误差：\(E_{out}≈E_{out}+ \dfrac{2(d+1)}{N}\)
linear regressin这种方法可以用在binary classification上，虽然上界变宽松了，但是仍然能得到不错的学习方法。
一个心脏病预测的问题：根据患者的年龄、血压、体重等信息，来预测患者是否会有心脏病。很明显这是一个二分类问题，其输出y只有{-1,1}两种情况。二元分类，一般情况下，理想的目标函数f(x)>0.5，则判断为正类1；若f(x)<0.5，则判断为负类-1。
但是，如果我们想知道的不是患者有没有心脏病，而是到底患者有多大的几率是心脏病。这表示，我们更关心的是目标函数的值(分布在0,1之间)，表示是正类的概率(正类表示是心脏病)。这跟我们原来讨论的二分类问题不太一样，我们把这个问题称为软性二分类问题(‘soft‘ binary classification)。这个值越接近1，表示正类的可能性越大；越接近0，表示负类的可能性越大。注意：PLA中样本标签为{+1, -1}，此处标签用{0, 1}。
对于软性二分类问题，理想的数据是分布在[0,1]之间的具体值，但是实际中的数据只可能是0或者1，我们可以把实际中的数据看成是理想数据加上了噪声的影响(???)。故目标函数f: P(1|x)，即正样本发生的概率值。将加权平均经过sigmoid函数转到(0,1)区间。
Logistic Regression采用极大似然估计求未知参数。
使似然函数最大的假设函数h即可选为g，即\(g = \mathop{argmax}\limits_h Likelihold(h)\)
又知：记目标函数f: P(1|x)为p，则
该函数可统一为一个等式：$$P(y|x) = py(1-p){1-y}, \quad y=0,1$$
故可得（注：为看得清楚，最后一行上标省略）：$$\begin{equation}\begin{aligned}
g &= \mathop{argmax}\limits_h Likelihold(h)\
&= \mathop{argmax}\limits_h \sum\limits_{i=1}^m ln(P(y^{(i)} | x^{(i)})) \
&= \mathop{argmax}\limits_h \sum\limits_{i=1}^m [ylnp+(1-y)ln(1-p)] \
&= \mathop{argmin}\limits_h -\sum\limits_{i=1}^m [ylnp+(1-y)ln(1-p)]
\end{aligned}\end{equation}$$
即为Ng视频中代价函数(也称为cross-entropy error交叉熵误差)：
代价函数采用梯度下降法求解，过程略。
20190920注：林课中假设负样本为\(y=-1\)，故\(h(x_n)\)和\(1-h(x_n)\)均可以写成\(h(y_n x_n)\)的形式，即可推出\(err(w,x_n,y_n)=ln(1+e^{-y_n w^T x_n})\)，也称为cross-entropy error，推导详情可参考笔记。
三种线性模型：
注意：该课程中linear classification与logistic regression不同，前者特指结果只有两种{+1,-1}，后者特指结果为概率值(0,1)。(想法：后者之所以叫regression，拟合的是概率的regression，分类功能是下一步的副产品。)
三种线性模型均使用了线性得分函数\(s=w^Tx\)，均可用于解决linear classification的问题，优缺点如下。通常，我们使用linear regression来获得初始化的\(w_0\)，再用logistic regression模型进行最优化解。
针对多元分类问题，有三种解决方案：
(1).采用一对多、linear classification的方式；
(2).采用一对多、logistic regression的方式(称为One-Versus-All(OVA) Decomposition)；
(3).采用一对一、Binary Classification的方式(称为One-Versus-One(OVO) Decomposition)；
注意：
上一节主要了解了三种线性模型可以用于解决binary classification和multiclass classification问题，这一节介绍：利用非线性变换解决非线性分类问题；非线性变换带来的问题；如何安全地使用非线性变换。
线性模型的优点就是，它的VC Dimension比较小，保证了\(E_{in}\approx E_{out}\)。但是缺点也很明显，对某些非线性问题，可能会造成\(E_{in}\)很大，虽然\(E_{in}\approx E_{out}\)，但是也造成\(E_{out}\)很大，分类效果不佳。
一种解决方式是，将低维的特征映射到高维空间中，从而将低维空间中非线性问题转化高维空间中的线性问题。比如多项式回归，将各项变量作为一个维度。基于这种非线性思想，我们之前讨论的PLA、Regression问题都可以有非线性的形式进行求解。我们把\(x_n\rightarrow z_n\)这个过程称之为特征转换（Feature Transform）。
注意：
整个过程就是通过映射关系，换个空间去做线性分类，重点包括两个：特征转换；训练线性模型。之后预测时也进行变换至z域中判断。
进行特征变换之后，z域维度为\(d_z = C_{Q+d}^Q = C_{Q+d}^Q = O(Q^d)\) ，其中Q为多项式次数，d为x域维度。可以看出，随着Q和d的增大，z域维度急剧增加。(思考：是否因为引入了大量冗余信息？比如\(x\)、\(x^2\)本来是相关的，但在z域中纯粹作为两个独立维度。)
z域维度急剧增加带来了三个问题：
解决方案：如何选择合适的Q，来保证不会出现过拟合问题，使模型的泛化能力强呢？
台大林轩田老师《机器学习基石》课程笔记3：How can machines learn?
原文：https://www.cnblogs.com/inchbyinch/p/12549123.html