LogisticRegression/逻辑回归（LogisticRegression）.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 线性模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- 基本形式\n",
    "- 误差函数\n",
    "- 使误差函数最小\n",
    "- 广义线性模型\n",
    "- 逻辑回归\n",
    "- 线性判别分析\n",
    "- 对分类学习\n",
    "- 类别不平衡的问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 基本形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$$ f(x_i) =wx_i + b , 使得f(x_i) = y_i$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 误差函数\n",
    "\n",
    "为了衡量预测值和真实值之间的误差大小，构造误差函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$$E(w,b) = \\sum_{i=1}^{m}(f(x_i) - y_i)^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 使误差函数值最小\n",
    "\n",
    "- 通过求导获得\n",
    "- 通过最小二乘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 求导得出w，b **\n",
    "\n",
    "$$w = \\frac{\\sum_{i=1}^{m}y_i(x_i-\\overline{x})}{\\sum_{i=1}^{m}x_i^2 - \\frac{1}{m}(\\sum_{i}^{m}x_i)^2}$$   \n",
    "$$b = \\frac{1}{m} \\sum_{i=1}^{m}(y_i - wx_i)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 最小二乘求得w **\n",
    "\n",
    "$$ \\hat{w}^* = (X^TX)^{-1}X^Ty$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 广义线性模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "线性模型简写为：\n",
    "\n",
    "$$y = w^Tx + b$$\n",
    "\n",
    "可否另模型预测值逼近y的衍生物呢？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "比如假如我们人为示例所对应的输出标记是在指数尺度上变化，那就可将输出标记的对数作为线性模型逼近的目标：\n",
    "\n",
    "$$lny = w^Tx + b $$\n",
    "\n",
    "这就是“对数线性回归”，就是试图让$e^{w^Tx + b}$逼近y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "更一般的，考虑单调可微函数$g(\\cdot)$，令：\n",
    "\n",
    "$$y = g_{-1}(w^Tx + b)$$\n",
    "\n",
    "这就是“广义相对模型”，$g(\\cdot)$函数成为“联系函数”，对数线性回归模型就是广义线性模型在$g(\\cdot) = ln(\\cdot)$时的特例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 逻辑回归（Logistic Regression）\n",
    "\n",
    "上面说的是使用线性模型进行回归学习，但是要做的是分类任务该如何做？这时候需要找一个单调可微的函数将分类任务的真实标记y与线性回归模型的预测值联系起来\n",
    "\n",
    "常规步骤为：\n",
    "- 寻找h函数（即hypothesis）；\n",
    "- 构造J函数（损失函数）；\n",
    "- 想办法使得J函数最小并求得回归参数（θ）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 构造预测函数h **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "函数形式为：\n",
    "\n",
    "$h_\\theta (x) = g(\\theta^T x) = \\frac{1}{1+e^{-\\theta^T x}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "函数$h_\\theta(x)$的值有特殊的含义，它表示结果取1的概率，因此对于输入x分类结果为类别1和类别0的概率分别为：\n",
    "\n",
    "$P(y = 1|x;\\theta) = h_\\theta(x) $   \n",
    "$P(y = 0|x;\\theta) = 1- h_\\theta(x) $ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**构造损失函数J **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "将上面二式综合起来\n",
    "\n",
    "$P(y|x;\\theta) = (h_\\theta(x))^y(1- h_\\theta(x))^{1-y} $   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "取似然函数为：\n",
    "\n",
    "$L(\\theta) = \\Pi_{i=1}^{m}P(y_i|x_i;\\theta) = \\Pi_{i=1}^{m}(h_\\theta(x_i))^{y_i}(1- h_\\theta(x_i))^{1-y_i}$\n",
    "\n",
    "对数似然函数为：\n",
    "\n",
    "$l(\\theta) = logL(\\theta) = \\sum_{i=1}^{m}(y_ih_\\theta(x_i)+(1-y_i)(1- h_\\theta(x_i)))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "最大似然估计就是求使$l(\\theta)$取最大值时的θ，其实这里可以使用梯度上升法求解，求得的θ就是要求的最佳参数。\n",
    "\n",
    "$J(\\theta) = -\\frac{1}{m}l(\\theta)$\n",
    "\n",
    "因为乘了一个负的系数-1/m，所以取$J(\\theta)$最小值时的θ为要求的最佳参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 梯度下降法求的最小值 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\theta$更新过程:\n",
    "\n",
    "$\\theta_j:=\\theta_j - \\alpha \\frac{1}{m}\\sum_{i=1}^{m}(h_\\theta (x_i) - y_i)x_i^j$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 线性模型实例 **\n",
    "\n",
    "[线性模型实例](逻辑回归（Logistic Regression）经典实例.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 线性判别分析（LDA）\n",
    "\n",
    "LDA思想：给定训练样例，设法将样例投影到一条直线上，使得同样样例的投影点尽可能的接近、益阳例的投影点尽可能的远离，在对新样本进行分类时，将其投影到同样的直线上，再根据投影点的位置来确定新的样本的类别"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "公式字母说明：\n",
    "\n",
    "- $y =w^Tx$:样本要投影的直线\n",
    "- $X_i$: 第i类样本的集合\n",
    "- $\\mu_i$: 第i类样本的均值向量\n",
    "- $\\sum_i$: 第i类样本的均方差矩阵\n",
    "- $w^T\\mu_0,w^T\\mu_1$: 两类样本的中心在直线上的投影\n",
    "- $w^T\\sum_0w,w^T\\sum_1w$: 两类样本的均方差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "为了达到目的我们要使$||w^T\\mu_0 - w^T\\mu_1||_2^2$尽可能的大，使$w^T\\sum_0w+w^T\\sum_1w$尽可能的小，于是得到最大化目标：\n",
    "\n",
    "$$J = \\frac{||w^T\\mu_0 - w^T\\mu_1||_2^2}{w^T\\sum_0w+w^T\\sum_1w}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "定义“类内散度矩阵”：\n",
    "\n",
    "$$S_w = \\sum_0 + \\sum_1 = \\sum_{x \\in x_0}(\\mu_0 - \\mu_1)(\\mu_0 - \\mu_1)^T + \\sum_{x \\in x_1}(\\mu_0 - \\mu_1)(\\mu_0 - \\mu_1)^T$$   \n",
    "\n",
    "“类间散度矩阵”\n",
    "$$S_b = (\\mu_0 - \\mu_1)(\\mu_0 - \\mu_1)^T$$\n",
    "\n",
    "于是：\n",
    "\n",
    "$$ J = \\frac{w^TS_bw}{w^TS_ww}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "确定$w$，令$w^TS_ww = 1$:\n",
    "\n",
    "$$ min_w -w^TS_bw$$  \n",
    "$$ s.t.  w^TS_ww = 1$$\n",
    "\n",
    "由拉格郎日子乘法，得：\n",
    "\n",
    "$$ S_bw = \\lambda S_ww$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$S_bw$的方向恒为$\\mu_0-\\mu_1$,令$S_bw = \\lambda(\\mu_0-\\mu_1)$，得到$w = S_w^{-1}(\\mu_0-\\mu_1)$\n",
    "\n",
    "实践中，对 $S_w$进行奇异值分解，即$S_w = U\\sum V^T$，$S_w^{-1} = V\\sum^{-1}U^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "将LDA推广到多分类任务中，假定N个类，定义“全局散度矩阵”：\n",
    "\n",
    "$$S_t = S_b + S_w = \\sum_{i=1}^{m}(x_i-\\mu)(x_i-\\mu)^T$$\n",
    "\n",
    "$\\mu$是所有样本的均值向量\n",
    "\n",
    "$$S_w = \\sum_{i=1}^{N}S_{w_i}$$\n",
    "\n",
    "其中：\n",
    "\n",
    "$$S_{w_i} = \\sum_{x \\in X_i}(x-\\mu_i)(x-\\mu_i)^T$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 多分类学习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- 一对一（OvO）\n",
    "- 一对多（OvR）\n",
    "- 多对多（MvM）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 类别不平衡的问题\n",
    "\n",
    "如果不同类别的样本树目差别过大，则对学习过程造成困扰，假设有998个反例，2个正例，那么学习算法就算是得到一个永远将样本预测为反例的学习器，其正确率也会在99.8%，这样的学习器是没有价值的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "解决方法\n",
    "\n",
    "- 欠采样： 去除一些样本多的类别样本数量，是正反样本数目接近，欠采样若随机丢弃样本，可能会丢失一些重要的信息;欠采样的代表算法EasyEnsemble则利用集成学习机制，将样本分为若干个集合供不同学习器使用，这样对每个学习器来看都是进行了欠采样，但是对于全局来看不会丢失重要信息。\n",
    "- 过采样： 增加样本少的类别样本数量，是正反样本数目接近，过采样不能简单对样本进行重复采样，否则会招致严重的过拟合;过采样算法的代表性算法SMOTE是通过对训练集里面的样本进行插值来产生额外的正例\n",
    "- 阀值移动"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 阀值移动 **\n",
    "\n",
    "- 我们再用$y = w^Tx + b$对新样本进行分类时，实际上是再用预测出的y值与与一个阀值进行比较\n",
    "- 例如通常在$y>0.5$时判别为正例，否则为范例\n",
    "- y实际上表达了正例的可能性，几率$\\frac{y}{1-y}$反映了正例可能性与反例可能性比值，阀值为0.5表明了分类器认为真实正、反例可能性相同，即分类器决策规则为：\n",
    "\n",
    "$$若\\frac{y}{1-y} > 1 ，则预测为正例$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "当训练集正、反例样本树目不同时，令$m^+$表示正例数目，$m^-$表示反例数目，则观测几率为$\\frac{m^+}{m^-}$.   \n",
    "\n",
    "由于我们通常假设训练集是真实样本的无偏采样，所以观测几率就表示了真实几率，于是只要分类器的预测几率高于观测几率就应判定为正例，即：\n",
    "\n",
    "$$若 \\frac{y}{1-y} > \\frac{m^+}{m^-}, 则预测为正例$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "但是，我们的分类器是基于$\\frac{y}{1-y} > 1$进行决策，因此需要对其预测值进行调整，使其在基于 $\\frac{y}{1-y} > 1$决策时，实际在执行$\\frac{y}{1-y} > \\frac{m^+}{m^-}$，只需令：\n",
    "\n",
    "$$\\frac{y^{'}}{1-y^{'}} = \\frac{y}{1-y} \\times \\frac{m^+}{m^-}$$"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}