{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第二部分：分类问题（Classification）和逻辑回归（Logistic regression）\n",
    "\n",
    "在前面的回归问题中，我们尝试预测的变量$y$是连续变量，现在我们来讨论分类问题。分类问题与回归问题不同之处在于，$y$的取值是少量的离散值。现在，我们先介绍**二元分类（binary classification）**，也就是$y$只能取$0$或$1$。（在二元分类中介绍的很多方法也可以推广至多元情况。）比如，我们尝试实现一个垃圾邮件分类器，用$x^{(i)}$表示邮件的某些特征，通过分类算法预测得到：如果该邮件是垃圾邮件时$y=1$，反之$y=0$。我们也把$0$称为**negative class**，把$1$称为**positive class**，我们有时也使用$-,\\ +$作为标记。对于给定的$x^{(i)}$，$y^{(i)}$也称作训练样本的**label**。\n",
    "\n",
    "## 5. 逻辑回归\n",
    "\n",
    "对于分类问题，我们也可以无视$y$是取离散值的特征而继续使用线性回归，使用老办法通过$x$预测$y$的取值。然而，强行使用线性回归的方法处理分类问题通常会得到很糟糕的预测结果。况且，在我们已经明确知道$y\\in\\{0,\\ 1\\}$的情况下仍旧使用线性回归的$h_\\theta(x)\\in\\mathbb{R}$是不合逻辑的。\n",
    "\n",
    "所以，我们应该对原来的假设函数做出修改：\n",
    "\n",
    "$$h_\\theta(x)=g\\left(\\theta^Tx\\right)=\\frac{1}{1+e^{-\\theta^Tx}}$$\n",
    "\n",
    "这里的$g(z)=\\frac{1}{1+e^{-z}}$，也叫作**逻辑函数（logistic function）**或**S型函数（sigmoid function）**，图像如下图所示：\n",
    "\n",
    "<img src=\"./resource/chapter03_image02.png\" width=\"400\" alt=\"\" align=center />\n",
    "\n",
    "在$z\\to\\infty$时函数$g(z)$趋近于$1$，而$z\\to-\\infty$是函数$g(z)$趋近于$0$。而且不光是$g(z)$，包括上面的$h(x)$都在$(0, 1)$之间取值。有$\\theta^Tx=\\theta_0+\\displaystyle\\sum_{j=0}^n\\theta_jx_j$，这里我们依然令$x_0=1$。\n",
    "\n",
    "其它的在$(-\\infty,\\ \\infty)$上能够从$0$取到$1$的可导的连续函数也可以使用，但是因为一些原因（我们将在后面的关于GLM、生成学习法的课程中了解），选择上面的逻辑函数是一种“自然”的结果。再继续前，我们先来看一下逻辑函数求导的优良性质：\n",
    "\n",
    "$$\\begin{align}g'(z)&=\\frac{\\mathrm d}{\\mathrm dz}\\frac{1}{1+e^{-z}}\\\\&=\\frac{1}{\\left(1+e^{-z}\\right)^2}\\left(e^{-z}\\right)\\\\&=\\frac{1}{1+e^{-z}}\\cdot\\left(1-\\frac{1}{1+e^{-z}}\\right)\\\\&=g(z)(1-g(z))\\end{align}$$\n",
    "\n",
    "接下来，我们应该如何用$\\theta$拟合逻辑回归模型呢？在线性回归中我们知道了，从一些列假设下的最大似然估计可以推导出最小二乘回归的合理性，所以，我们也可以按照这个思路，给我们的分类模型赋予一些列概率假设，然后通过最大似然估计拟合参数。假设：\n",
    "\n",
    "$$\\begin{align}P(y=1\\mid x;\\theta)&=h_\\theta(x)\\\\P(y=0\\mid x;\\theta)&=1-h_\\theta(x)\\end{align}$$\n",
    "\n",
    "当然，我们也可以将这两个假设合入一个简洁的式子：\n",
    "\n",
    "$$p(y\\mid x;\\theta)=(h_\\theta(x))^y(1-h_\\theta(x))^{(1-y)}$$\n",
    "\n",
    "假设训练集中的$m$个训练样本是相互独立的，我们就可以这样写出参数的似然估计：\n",
    "\n",
    "$$\\begin{align}L(\\theta)&=p\\left(\\vec y\\mid X;\\theta\\right)\\\\&=\\prod_{i=1}^m p\\left(y^{(i)}\\mid x^{(i)};\\theta\\right)\\\\&=\\prod_{i=1}^m\\left(h_\\theta\\left(x^{(i)}\\right)\\right)^{y^{(i)}}\\left(1-h_\\theta\\left(x^{(i)}\\right)\\right)^{1-y^{(i)}}\\end{align}$$\n",
    "\n",
    "跟线性回归中的运算一样，我们取对数便于求导：\n",
    "\n",
    "$$\\begin{align}\\mathscr{l}(\\theta)&=\\log L(\\theta)\\\\&=\\sum_{i=1}^my^{(i)}\\log h_\\theta\\left(x^{(i)}\\right)+\\left(1-y^{(i)}\\right)\\log\\left(1-h_\\theta\\left(x^{(i)}\\right)\\right)\\end{align}$$\n",
    "\n",
    "我们依然沿用线性回归中的思路，通过求导发现最大化似然函数的极值点，这次我们使用梯度上升法。我们使用矢量记法，则有更新规则为$\\theta:=\\theta+\\alpha\\nabla_\\theta\\mathscr{l}(\\theta)$。（因为想要求函数的最大值，所以我们在更新规则里使用了加号。）我们现在假设训练集中只有一个训练样本$(x,\\ y)$，对其求导，希望能导出适用于随机梯度上升更新规则：\n",
    "\n",
    "$$\\begin{align}\\frac{\\partial}{\\partial\\theta_j}\\mathscr{l}(\\theta)&=\\left(y\\frac{1}{g\\left(\\theta^Tx\\right)}-(1-y)\\frac{1}{1-g\\left(\\theta^Tx\\right)}\\right)\\frac{\\partial}{\\partial\\theta_j}g\\left(\\theta^Tx\\right)\\\\&=\\left(y\\frac{1}{g\\left(\\theta^Tx\\right)}-(1-y)\\frac{1}{1-g\\left(\\theta^Tx\\right)}\\right)g\\left(\\theta^Tx\\right)\\left(1-g\\left(\\theta^Tx\\right)\\right)\\frac{\\partial}{\\partial\\theta_j}\\theta^Tx\\\\&=\\left(y\\left(1-g\\left(\\theta^Tx\\right)\\right)-(1-y)g\\left(\\theta^Tx\\right)\\right)x_j\\\\&=(y-h_\\theta(x))x_j\\end{align}$$\n",
    "\n",
    "在上面的求导中，从第一步到第二步我们使用了逻辑函数求导性质$g'(z)=g(z)(1-g(z))$。这样，我们也就得到了适用于随机梯度上升的更新规则：\n",
    "\n",
    "$$\\theta_j:=\\theta_j+\\alpha\\left(y^{(i)}-h_\\theta\\left(x^{(i)}\\right)\\right)x_j$$\n",
    "\n",
    "如果使用批量梯度上升则是：\n",
    "\n",
    "$$\\theta_j:=\\theta_j+\\alpha\\sum_{i=1}^m\\left(y^{(i)}-h_\\theta\\left(x^{(i)}\\right)\\right)x_j$$\n",
    "\n",
    "回顾上一讲的最小均方法法，我们会发现上面这条更新规则和以前的更新规则一模一样，我们在这里必须说明，$h_\\theta(x)$已经变为关于$\\theta^Tx^{(i)}$的非线性函数，所以这并不是同一个算法。尽管如此，对于不同的算法得到同样形式的更新规则，我们还是感到很惊讶。对于这个现象，我们会在后面关于GLM模型的课程中给出解释。\n",
    "\n",
    "## 6. 感知算法（perceptron learning algorithm）\n",
    "\n",
    "最后，我们来简要的介绍一下感知算法，我们以后在介绍学习理论是还会继续讨论这个算法。对于上面的逻辑回归，我们如何“强迫”算法只输出$0$或$1$？我们会自然的想到改变$g$的定义，使其变为一个阈函数：\n",
    "\n",
    "$$g(z)=\\begin{cases}1\\quad z\\geq 0\\\\0\\quad z\\lt 0\\end{cases}$$\n",
    "\n",
    "如果我们依然令$h_\\theta(x)=g\\left(\\theta^Tx\\right)$，并将$g$修改为上面的阈函数，然后使用$\\theta_j:=\\theta_j+\\alpha\\displaystyle\\sum_{i=1}^m\\left(y^{(i)}-h_\\theta\\left(x^{(i)}\\right)\\right)x_j$或$\\theta_j:=\\theta_j+\\alpha\\left(y^{(i)}-h_\\theta\\left(x^{(i)}\\right)\\right)x_j$作为学习规则，那么我们就实现了一个**感知算法（perceptron learning algorithm）**。\n",
    "\n",
    "在六十年代，这个感知算法被认为是一种粗略的描述脑中独立神经元工作方式的模型。该模型很简单，所以我们也将它作为日后讨论学习理论的起点。需要注意的是，尽管这个算法看起来并不特殊，但实际上，与其前面的逻辑回归、最小二乘线性回归比起来，这是一个非常不同的算法：比如，我们很难赋予它一个在概率上有意义的解释，也很难从最大似然估计推导出感知算法。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}