{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 岭回归的求解\n",
    "\n",
    "岭回归就是 **基于 $L_2$ 约束的最小二乘法**，它的损失函数为：\n",
    "\n",
    "$$\n",
    "loss = \\sum_{i=1}^m (y_i - w^Tx_i)^2 + \\lambda \\| w \\|^2\n",
    "$$\n",
    "\n",
    "我们将损失函数表示成矩阵形式：\n",
    "\n",
    "$$\n",
    "loss = (y - w^TX)^2 + \\lambda w^2\n",
    "$$\n",
    "\n",
    "和最小二乘的正规方程解法一样，我们对 $w$ 求偏导：\n",
    "\n",
    "$$\n",
    "\\frac {\\partial}{\\partial w}loss = 2X^T(Xw-y)+2 \\lambda w\n",
    "$$\n",
    "\n",
    "令其等于 0，求得损失函数最小时 $w$ 的解析解：\n",
    "\n",
    "$$\n",
    "\\hat{w} = (X^TX + \\lambda I)^{-1}X^Ty\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一般 $L_2$ 约束的最小二乘求解\n",
    "\n",
    "在前面介绍岭回归的时候，我们不仅介绍了 $L_2$ 约束，还将其扩展到更一般的情况：\n",
    "\n",
    "$$\n",
    "\\mathop{\\min}_{\\theta}J(\\theta), \\theta^TG\\theta \\leqslant R\n",
    "$$\n",
    "\n",
    "它的损失函数可以表示成：\n",
    "\n",
    "$$\n",
    "loss = (y - w^TX)^2 + \\lambda w^TGw\n",
    "$$\n",
    "\n",
    "我们可以对其求偏导，得到 $w$ 的解析解：\n",
    "\n",
    "$$\n",
    "\\hat{w} = (X^TX + \\lambda G)^{-1}X^Ty\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LASSO 回归的求解\n",
    "\n",
    "LASSO 回归是 **基于 L_1 约束的最小二乘法**，它的损失函数为：\n",
    "\n",
    "$$\n",
    "loss = \\sum_{i=1}^m (y_i - w^Tx_i)^2 + \\lambda \\| w \\|\n",
    "$$\n",
    "\n",
    "这里的 $\\| w \\|$ 是对所有的 $w_i$ 绝对值进行求和，我们知道绝对值函数不能求导，所以不能像上面那样通过求偏导来求解。\n",
    "\n",
    "1. 解法一：通过二次函数在绝对值函数的上方进行控制\n",
    "\n",
    "$$\n",
    "|\\theta| \\leqslant \\frac{\\theta^2}{2c} + \\frac{c}{2}\n",
    "$$\n",
    "\n",
    "得到 $\\theta$ 的迭代更新公式：\n",
    "\n",
    "$$\n",
    "\\theta := (X^TX + \\lambda\\Theta^\\dagger)^{-1}X^Ty\n",
    "$$\n",
    "\n",
    "其中，$\\Theta = diag(|\\theta_1|, \\dots, |\\theta_b|)$，$\\Theta^\\dagger$ 表示 $\\Theta$ 的广义逆。\n",
    "\n",
    "具体的求解过程参见《图解机器学习》p45.\n",
    "\n",
    "2. 解法二：使用近端梯度下降（Proximal Gradient Descent，简称 PGD）\n",
    "\n",
    "L-Lipschitz 条件、二阶泰勒展开\n",
    "\n",
    "参见《机器学习》p253.\n",
    "\n",
    "3. 解法三：拟牛顿法\n",
    "\n",
    "BFGS、L-BFGS、Armijo 搜索准则、Sherman-Morrison 公式"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}