Logistic Regression

Classification and Representation

Classification

对于二分类问题，我们使用线性函数，然后把大于0.5作为1，小于0.5视为0。但是实际上，分类使用线性函数的效果不是这么好。

粉红色线是我们给出的一些样本，粉红线画点对应的x轴左部是良性肿瘤，右边是恶行肿瘤。但是如果此时给了一个很远的恶性肿瘤样本点，我们画出的蓝线在区分恶良性肿瘤问题上的效果是这么好。

我们现在关注二分类问题，y值为0和1(0称为negative class，1称为positive class)，后面我们推广为多元分类问题。给出的 $x^{(i)}$x(i) 则相应的标签为 $y^{(i)}$y(i)。

Hypothesis Representation

我们可以忽略y是离散值的事实来处理分类问题，并使用我们的旧线性回归算法来尝试预测给定x。但是，线性回归处理 $h_{\theta}(x)$hθ​(x) 比1大或比0小。为了一直保持$h_{\theta}(x)$hθ​(x)在[0，1]之间，我们把 $\theta^T x$θTx 带入 g(z) 中。即：

g(z)称之为sigmoid函数或logistic函数，sigmoid函数图像如下：

此处所示的函数g（z）将任何实数映射到（0,1）区间，这使得将任意值函数转换为更适合分类的函数非常有用。

$h_{\theta}(x)$hθ​(x) 代表我们输出值为1的概率。比如：$h_{\theta}(x)=0.7$hθ​(x)=0.7 意味着我们输出1的可能性为0.7，输出0的可能性为0.3 。

Decision Boundary(决策边界)

记住sigmoid函数：
$\\z=0, e^{0}=1 \Rightarrow g(z)=1/2 \\ z \to \infty, e^{-\infty} \to 0 \Rightarrow g(z)=1 \\ z \to -\infty, e^{\infty}\to \infty \Rightarrow g(z)=0$z=0,e0=1⇒g(z)=1/2z→∞,e−∞→0⇒g(z)=1z→−∞,e∞→∞⇒g(z)=0
为了得到分类离散值0和1，我们可以转换我们假设函数的输出，如下
$h_\theta (x) = g ( \theta^T x ) \\ h_\theta(x) \geq 0.5 \rightarrow y = 1 \\ h_\theta(x) &lt; 0.5 \rightarrow y = 0$hθ​(x)=g(θTx)hθ​(x)≥0.5→y=1hθ​(x)<0.5→y=0
如果输入为 $\theta^T x$θTx ,这意味着：
$\theta^T x \geq 0 \Rightarrow y = 1 \\ \theta^T x &lt; 0 \Rightarrow y = 0$θTx≥0⇒y=1θTx<0⇒y=0
重点自己说3遍：decision boundary(决策边界)是分隔y = 0和y = 1的区域的线。它由我们的假设函数创建，准确的说是由 $\theta^T$θT 决定。decision boundary(决策边界)不是训练集的属性。训练集确定参数 $\theta$θ。

一个例子：

在这种情况下，我们的决策边界是图形上的直线垂直线，其中x_1。直线左边的所有都表示y = 1，而右边的所有都表示y = 0。

输入sigmoid函数 $g(z)$g(z) 不需要一定是线性，也可以是曲线如$z=\theta_0+\theta_1 x_1^2+ \theta_2 x_2^2$z=θ0​+θ1​x12​+θ2​x22​，也可以根据对应数据的任意形状。

Logistic Regression Model

Cost Function

Logistic函数使用线性回归相同的cost函数，即$h_\theta(x)$hθ​(x)用粉红色的式子代入，然后得到$J(\theta)$J(θ):

$J(\theta)$J(θ)是"non-convex"，会有多个局部最优。而”convex“有global最小值。

总结：我们不能使用与线性回归相同的cost函数，因为Logistic函数会导致输出波动，导致许多局部最优。换句话说，它不会是凸函数(convex)。

相反，我们的逻辑回归成本函数如下：

当y=1时，我们得到$J(\theta)$J(θ) vs $h_{\theta}(x)$hθ​(x)图像：

当y=0时，我们得到$J(\theta)$J(θ) vs $h_{\theta}(x)$hθ​(x)图像：


注意：以这种方式编写成本函数可以保证$J(\theta)$J(θ)对于逻辑回归是凸的。

Simplified Cost Function and Gradient Descent

Simplified Cost Function

我们之前定义的分段函数cost function可以用一个式子表达：
$\mathrm{Cost}(h_\theta(x),y) = - y \; \log(h_\theta(x)) - (1 - y) \log(1 - h_\theta(x))$Cost(hθ​(x),y)=−ylog(hθ​(x))−(1−y)log(1−hθ​(x))
因此，我们的得到了$J(\theta)$J(θ)：
$J({\theta } )= -\frac{1}{m}\sum_{i=1}^{m}[(y^{(i)}log(h_\theta(x^{(i)})) +(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$J(θ)=−m1​i=1∑m​[(y(i)log(hθ​(x(i)))+(1−y(i))log(1−hθ​(x(i)))]
向量化为：
$h = g(X\theta)\\ J(\theta) = \frac{1}{m} \cdot \left(-y^{T}\log(h)-(1-y)^{T}\log(1-h)\right)$h=g(Xθ)J(θ)=m1​⋅(−yTlog(h)−(1−y)Tlog(1−h))

Gradient Descent

梯度下降的一般形式是:
$Repeat \;\lbrace \\ \qquad \qquad \qquad \qquad \theta_j := \theta_j - \alpha \dfrac{\partial}{\partial \theta_j}J(\theta) \\\\\rbrace$Repeat{θj​:=θj​−α∂θj​∂​J(θ)}
我们可以使用微积分来计算导数部分(不知道如何求导？???? ):
$Repeat \; \lbrace \\ \; \theta_j := \theta_j - \frac{\alpha}{m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)} \\ \rbrace$Repeat{θj​:=θj​−mα​i=1∑m​(hθ​(x(i))−y(i))xj(i)​}
值得注意的时，此算法与我们在线性回归中使用的算法相同。我们仍然需要同时更新theta中的所有值。

矢量化实现是：$\theta := \theta - \frac{\alpha }{m} X^T(g(X\theta) - \vec{y})$θ:=θ−mα​XT(g(Xθ)−y​)

Advanced Optimization

红线方框内是我们要计算的内容，下面是一些高级优化算法，右边是高级优化算法的优缺点。

给定的$\theta$θ，我们要计算：
$J(\theta) \\ \dfrac{\partial}{\partial \theta_j}J(\theta)$J(θ)∂θj​∂​J(θ)

1. 我们可以写一个返回这两个值的costFunction函数：

function [jVal, gradient] = costFunction(theta)
  jVal = [...code to compute J(theta)...];
  gradient = [...code to compute derivative of J(theta)...];
end

2. 然后我们可以使用octave的“fminunc（）”优化算法以及“optimset（）”函数，optimset（）该函数创建一个包含我们要发送到“fminunc（）”的选项的对象。我们输入到函数“fminunc（）”是我们之前定义的成本函数，我们的 $\theta$θ 值的初始向量，以及我们事先创建的“options”对象。

options = optimset('GradObj', 'on', 'MaxIter', 100);
initialTheta = zeros(2,1);
   [optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);

3. 例子
   
   修正：options()最后一个参数’100’应该改为100，因为最后一个参数是Integer而不是string.

   说明：

   • options()：

     -‘GradObj’, -‘on’：设置梯度目标参数为on打开状态

     -‘MaxIter’, -100：设置最大跌打次数100

   • @：指向定义costFunction函数的指针。

   • 结果：

   • 

     optTheta：求得 $\theta$θ 。

     functionVal：cost函数值，接近0.

     exitFlag：是否收敛，已经收敛了。

   • 最后注意：我们写作 $\theta$θ 是下标是从0开始的向量。而在Octave中， $\theta$θ 从下标1开始。
     

Multiclass Classification

Multiclass Classification: One-vs-all

当我们有两种以上的类型时，我们需要拓展我们的数据分类，我们将y = {0,1}延伸为y = {0,1…n}。由于y = {0,1 … n}，我们将问题分为n + 1（+1，因为索引从0开始）二进制分类问题。在每一个中，我们预测’y’是我们其中一个类的成员的概率。
$y \in \lbrace0, 1 ... n\rbrace \\ h_\theta^{(0)}(x) = P(y = 0 | x ; \theta) \\ h_\theta^{(1)}(x) = P(y = 1 | x ; \theta) \\ \cdots \\ h_\theta^{(n)}(x) = P(y = n | x ; \theta) \\ \mathrm {prediction} = \max_i( h_\theta ^{(i)}(x) )$y∈{0,1...n}hθ(0)​(x)=P(y=0∣x;θ)hθ(1)​(x)=P(y=1∣x;θ)⋯hθ(n)​(x)=P(y=n∣x;θ)prediction=imax​(hθ(i)​(x))
我们可以单独拿出一类来看，把这一类是为正样本，其余的所有类视为负样本，这就把多元分类变为了二分逻辑回归问题。最后返回最高值的假设函数值作为我们的预测。

总结：

• 为每一类训练一个逻辑回归分类器 $h_{\theta}(x)$hθ​(x) 预测 y=i 时候的概率。
• 预测一个新的x 时，选择 $max(h_{\theta}(x))$max(hθ​(x)) 的那一个类。

---

Regularization(正则化)

Solving the Problem of Overfitting(过拟合)

The Problem of Overfitting

最左边的直线其实没有很好地拟合数据，我们称之为”underfit“(欠拟合)或”high bias“（高偏差）。当我们增加一个特征 $x^2$x2 ,我们获得了稍微更好的数据拟合（参见中图）。但是我们增加到很多的特征之后，我们看到最右图即使拟合曲线完美地通过数据，我们也不会觉得这是一个非常好的预测。最右图是一个过拟合(overfit或者称为”high variance“)例子。

欠拟合或高偏差是指我们的假设函数 h 的形式很难映射到数据的趋势。它通常是由假设函数过于简单或特征太少引起的。另一方面，过度拟合或高变异是由适合可用数据的假设函数引起的，但不能很好地推广以预测新数据。它通常是由复杂的函数引起的，它会产生许多与数据无关的不必要的曲线和角度。

该术语适用于线性和逻辑回归。解决过度拟合问题有两个主要选择：

1. 减少特征的数量：
   • 手动选择要保留的特征；
   • 使用模型选择算法（在课程后面学习）。
2. 正则化（Regularization）
   • 保留所有特征，但减少参数 $\theta_{j}$θj​ 的大小；
   • 当我们有许多稍微有用的特征时，正则化很有效。

Cost Function

如果我们的假设函数产生了过拟合，我们想要降低假设函数种某些项的权重，可以采取提高这些项的成本方式。看一个例子：
$\theta_0 + \theta_1 x+\theta_2 x^2+\theta_3 x^3 +\theta_4 x^4$θ0​+θ1​x+θ2​x2+θ3​x3+θ4​x4
假设我们想让以上函数更加二次，我们就要消除 $\theta_3 x^3 +\theta_4 x^4$θ3​x3+θ4​x4 的影响。在没有真正消除这些特征或改变我们的假设形式的情况下，我们可以修改我们的成本函数（cost function）：
$min \theta \quad \frac{1}{2m}\sum_{i=1}^{m }(h_{\theta}(x^{(i)})-y^{(i)})^2 + 1000\cdot \theta_3^2+ 1000\cdot \theta_4^2$minθ2m1​i=1∑m​(hθ​(x(i))−y(i))2+1000⋅θ32​+1000⋅θ42​
我们添加了1000来凸显 $\theta_3， \theta_4$θ3​，θ4​ 的成本。为了使成本函数接近于0，我们必须使 $\theta_3 ，\theta_4$θ3​，θ4​接近于0，这样会在假设函数中消除 $\theta_3 x^3 +\theta_4 x^4$θ3​x3+θ4​x4 的影响。结果看起来，我们假设函数曲线更接近于二次曲线。

但在实际问题种，我们不知道哪些 $\theta$θ 项需要消除影响。此时，我们可以将所有 $\theta$θ 项正则化（不包括 $\theta_0$θ0​）。
$min \theta \quad \frac{1}{2m}\sum_{i=1}^{m }(h_{\theta}(x^{(i)})-y^{(i)})^2 + \lambda \sum_{j=1}^{n}\theta_j^2$minθ2m1​i=1∑m​(hθ​(x(i))−y(i))2+λj=1∑n​θj2​
$\lambda$λ 称为regularization parameter，它决定了我们的θ参数的成本增加了多少。

• $\lambda$λ 过大，它会使 $\theta$θ 项接近为0，最后$h_{\theta} (x) = \theta_0$hθ​(x)=θ0​，可能会使功能过度平滑并导致不合适。
• $\lambda$λ 过小，还是过拟合。

Regularized Linear Regression

Gradient Descent

我们将修改梯度下降函数从其余 $\theta$θ 项中分离出 $\theta_0$θ0​ ,因为我们不想惩罚 $\theta_0$θ0​ 。
$\\ \text{Repeat}\ \lbrace \\ \\ \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \\ \\ \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] \ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\\ \\ \rbrace$Repeat {    θ0​:=θ0​−α m1​ i=1∑m​(hθ​(x(i))−y(i))x0(i)​    θj​:=θj​−α [(m1​ i=1∑m​(hθ​(x(i))−y(i))xj(i)​)+mλ​θj​]          j∈{1,2...n}}
$\frac{\lambda}{m} \theta_j$mλ​θj​这项执行正则化，通过一些操作，我们的更新规则也可以表示为：
$\theta_j := \theta_j(1- \alpha\frac{\lambda}{m}) - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}$θj​:=θj​(1−αmλ​)−α m1​ i=1∑m​(hθ​(x(i))−y(i))xj(i)​
$(1- \alpha\frac{\lambda}{m})$(1−αmλ​) 必定一直小于1，也就是 $\theta_j(1- \alpha\frac{\lambda}{m})$θj​(1−αmλ​) 每次都比原来 $\theta_j$θj​ 小，个人理解为更好地惩罚 $\theta_j$θj​ 。值得注意是，第二项 $\alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}$α m1​ ∑i=1m​(hθ​(x(i))−y(i))xj(i)​ 和原来相比没有发生改变。

Normal Equation

现在让我们使用非迭代正规方程的替代方法来逼近正则化。要添加正则化，除了我们在括号内添加另一个术语之外，该等式与我们的原来的相同：
$\theta = \left( X^TX + \lambda \cdot L \right)^{-1} X^Ty \\\ \text{where}\ \ L = \begin{bmatrix} 0 &amp; &amp; &amp; &amp; \\ &amp; 1 &amp; &amp; &amp; \\ &amp; &amp; 1 &amp; &amp; \\&amp; &amp; &amp; \ddots &amp; \\ &amp; &amp; &amp; &amp; 1 \\\end{bmatrix}$θ=(XTX+λ⋅L)−1XTy where  L=⎣⎢⎢⎢⎢⎡​0​1​1​⋱​1​⎦⎥⎥⎥⎥⎤​
L矩阵的维度为：(n+1)×(n+1). 直觉上，这是单位矩阵（虽然我们不包括 $x_0$x0​ ），乘以单个实数λ。

X 矩阵维度：m x (n+1) ；y 是 m x 1维向量。m表示样本个数，n表示是特征的个数。如果 m < n，矩阵X一定是不可逆（non-invertible）矩阵；如果m=n，矩阵X有可能是不可逆矩阵。

记住：如果 m < n，矩阵$X^TX$XTX不可逆（non-invertible）。然而，我们添加 $\lambda \cdot L$λ⋅L , $X^TX + \lambda \cdot L$XTX+λ⋅L 就是可逆矩阵。也就是使用正则化把一些不可逆矩阵变为可逆矩阵。

Regularized Logistic Regression

下图显示了由粉色线显示的正则化函数如何比蓝线表示的非正则化函数更不容易过拟合：

逻辑回归的Cost Function

回想一下，我们的逻辑回归成本函数是：
$J(\theta) = -\frac{1}{m}\sum_{i=1}^{m}[(y^{(i)}log(h_\theta(x^{(i)})) +(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$J(θ)=−m1​i=1∑m​[(y(i)log(hθ​(x(i)))+(1−y(i))log(1−hθ​(x(i)))]
我们可以通过在末尾添加一个术语来实现正则化：
$J(\theta) = -\frac{1}{m}\sum_{i=1}^{m}[(y^{(i)}log(h_\theta(x^{(i)})) +(1-y^{(i)})log(1-h_\theta(x^{(i)}))] + \frac{\lambda}{2m}\sum_{i=1}^{n}\theta_j^2$J(θ)=−m1​i=1∑m​[(y(i)log(hθ​(x(i)))+(1−y(i))log(1−hθ​(x(i)))]+2mλ​i=1∑n​θj2​

逻辑回归的梯度下降

$\theta$θ向量下标是从0到n（$\theta_0$θ0​ 到 $\theta_n$θn​），实际上由n+1个值， $\sum_{i=1}^{n}\theta_j^2$∑i=1n​θj2​ 意味着明确排除 $\theta_0$θ0​ 。因此，在计算方程时，我们应该不断更新以下两个方程式：

逻辑回归的高级优化算法