problem1.ipynb 6.15 KB
Newer Older
20200203098 committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 凸优化\n",
    "本次作业主要用来练习逻辑回归相关的优化问题。通过完成作业,你讲会学到: 1. 逻辑回归的梯度下降法推导  2. 如何判断逻辑回归目标函数为凸函数。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设我们有训练数据$D=\\{(\\mathbf{x}_1,y_1),...,(\\mathbf{x}_n,y_n)\\}$, 其中$(\\mathbf{x}_i,y_i)$为每一个样本,而且$\\mathbf{x}_i$是样本的特征并且$\\mathbf{x}_i\\in \\mathcal{R}^D$, $y_i$代表样本数据的标签(label), 取值为$0$或者$1$. 在逻辑回归中,模型的参数为$(\\mathbf{w},b)$。对于向量,我们一般用粗体来表达。 为了后续推导的方便,可以把b融入到参数w中。 这是参数$w$就变成 $w=(w_0, w_1, .., w_D)$,也就是前面多出了一个项$w_0$, 可以看作是b,这时候每一个$x_i$也需要稍作改变可以写成 $x_i = [1, x_i]$,前面加了一个1。稍做思考应该能看出为什么可以这么写。\n",
    "\n",
    "请回答以下问题。请用Markdown自带的Latex来编写。\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  (a) ```编写逻辑回归的目标函数```\n",
    "请写出目标函数(objective function), 也就是我们需要\"最小化\"的目标(也称之为损失函数或者loss function),不需要考虑正则。 把目标函数表示成最小化的形态,另外把$\\prod_{}^{}$转换成$\\log \\sum_{}^{}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$L(w)=$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  (b) ```求解对w的一阶导数```\n",
    "为了做梯度下降法,我们需要对参数$w$求导,请把$L(w)$对$w$的梯度计算一下:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\partial L(w)}{\\partial w}=$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  (c) ```求解对w的二阶导数```\n",
    "在上面结果的基础上对$w$求解二阶导数,也就是再求一次导数。 这个过程需要回忆一下线性代数的部分 ^^。 参考: matrix cookbook: https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf, 还有 Hessian Matrix。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\partial^2 L(w)}{\\partial^2 w}=$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### (d) ```证明逻辑回归目标函数是凸函数```\n",
    "试着证明逻辑回归函数是凸函数。假设一个函数是凸函数,我们则可以得出局部最优解即为全局最优解,所以假设我们通过随机梯度下降法等手段找到最优解时我们就可以确认这个解就是全局最优解。证明凸函数的方法有很多种,在这里我们介绍一种方法,就是基于二次求导大于等于0。比如给定一个函数$f(x)=x^2-3x+3$,做两次\n",
    "求导之后即可以得出$f''(x)=2 > 0$,所以这个函数就是凸函数。类似的,这种理论也应用于多元变量中的函数上。在多元函数上,只要证明二阶导数是posititive semidefinite即可以。 问题(c)的结果是一个矩阵。 为了证明这个矩阵(假设为H)为Positive Semidefinite,需要证明对于任意一个非零向量$v\\in \\mathcal{R}$, 需要得出$v^{T}Hv >=0$\n",
    "请写出详细的推导过程:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "// TODO 请写下推导过程\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$L(w)=\\sum_{i}^{m}{y_{i}^{}log\\tilde{y}}+(1-y_{i})log(1-\\tilde{y}),\\tilde{y}=\\frac{1}{1-e_{}^{-(wx+b)}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\partial L}{\\partial w}=\\sum_{i}^{n}{(A_{i}^{}-y_{i}^{})*x_{i}^{}},A=\\frac{1}{1-e^{-(wx+b)}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">用向量表示即 $\\frac{\\partial L}{\\partial w}=X*(A-Y)^{T}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\partial^{2}L}{\\partial^{2}w}=\\sum_{i}^{n}\\frac{x_{ij}x_{ik}e^{-(wX_{i}+b)}}{A^{2}}=\\sum_{i}^{n}x_{ij}x_{ik}A_{i}(1-A_{i})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$H=\\left(\n",
    "  \\begin{array}{ccc}\n",
    "    x_{11}& ……&…… & x_{1n} \\\\\n",
    "    ……  &&&…… \\\\\n",
    "    ……  &  &&……   \\\\\n",
    "x_{n1} &……&…… &x_{nn}\n",
    "  \\end{array}\n",
    "\\right)*\\left(\n",
    "  \\begin{array}{ccc}\n",
    "    A_{1}(1-A_{1})& …… & …… & 0 \\\\\n",
    "    0 &A_{2}(1-A_{2})&&  \\\\\n",
    "    ……  &  &……&  \\\\\n",
    "0 &……&…… &A_{2}(1-A_{2})\\\\\n",
    "  \\end{array}\n",
    "\\right)*\\left(\n",
    "  \\begin{array}{ccc}\n",
    "    x_{11}& ……&…… & x_{n1} \\\\\n",
    "    ……  &&&…… \\\\\n",
    "    ……  &&&……   \\\\\n",
    "x_{1n} &……&…… &x_{nn}\n",
    "  \\end{array}\n",
    "\\right)=X^{T}*V*X$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">由于V中对角线上的值>0,因此矩阵H>=0,故逻辑回归函数的损失函数为凸函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}