Machine Learning Week03

Posted on Edited on In Views: Symbols count in article: 3.3k Reading time ≈ 3 mins.

Machine Learning

Week 03 Classification and Representation | Overfitting

1. Classification and Representation 分类和表征

  1. Logistic Regression算法应用于Classification

    • binary classification problem 二元分类问题

      • 函数值是离散的discrete

    • Hypothesis Representation 假设陈述

      • 因为需要\(y∈\{0,1\}\)，所以要使得\(0\le h_\theta(x)\le1\)，令\[h_\theta(x)=g(\theta^Tx),\ z=\theta^Tx,\ g(x)=\frac {1}{1+e^{-z}}\]

      • \(h_\theta(x)\)表示输出为1的概率: \[ h_\theta(x)=P(y=1|x;\theta)=1-P(y=0|x;\theta) \]

  2. Decision Boundary 决策边界：分类的边界 \[ h_\theta(x)=g(\theta_0+\theta_1x_1+\theta_2x_2) \]

    • 非线性(non-linear)决策边界

      多项式是决策边界的属性，不是训练集的属性，训练集决定参数θ的值

2. Logistic Regression Model 逻辑回归模型

  1. Cost Function

    • convex 凸函数，可以收敛到全局最小

    • 不能使用linear regression的Cost function，因为这会使得logistic function的成本函数变成波浪形，形成许多局部最优，就无法形成凸函数

    • 因此替换成本函数为： \[ J(\theta)=\frac {1}{m}\sum \limits_{i=1}^mCost(h_\theta(x^{(i)}),y^{(i)}) \\ Cost(h_\theta(x),y)= \begin{cases}-log(h_\theta(x)) & \quad if\ y=1 \\ -log(1-h_\theta(x)) & \quad if\ y=0 \end{cases} \]

      The cost function in this way guarantees that J(θ) is convex for logistic regression.

    • 这里的Cost function等价于： \[ Cost(h_\theta(x),y)=-ylog(h_\theta(x))-(1-y)log(1-h_\theta(x)) \]

    • 带入到代价函数 J(θ) 中

    • 使用==最大似然估计法==可以得出这个代价函数，最大似然估计可以有效地为不同模型找到参数数据。

    • 凸性是这个函数优秀地属性之一

    • 接下来：为了拟合θ，就要最小化 J(θ)

  2. Gradient Descent 梯度下降法 \[ \theta_j:=\theta_j-\alpha\frac {\partial} {\partial \theta_j}J(\theta)=\theta_j-\alpha\frac {1}{m}\sum \limits_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\quad(for\ j=0...n) \]

    • 选择学习速率：绘制 J(θ) 关于迭代次数的函数，使得每一次迭代函数值都在下降

    • 可以使用向量化实现算法 \[ \begin{array}{lc} h=g(\theta^TX)\\ J(\theta)=\frac{1}{m}\cdot(-y^Tlog(h)-(1-y)^Tlog(1-h))\\ \text{注：这里X是$（n+1）\times1$维列向量} \end{array} \] 最终得到： \[ \theta:=\theta-\frac{\alpha}{m}X(g(\theta^TX)-\vec{y}) \]

  • 特征值缩放也同样适用该模型

关于代价函数的最大似然估计法相关数学推导参见这里

==统计学是机器学习的数学基础==

  1. Optimization algorithm 优化算法

    • 例如：

      • Conjugate gradient 共轭梯度法

      • BFGS变尺度法

      • L-BFGS限制变尺度法

        优点：无需手动选择α（线性搜索法每一步都在改变α）；比梯度下降法收敛更快

        缺点：算法更复杂、难理解

    • octave中的优化算法表达：

      1
      2
      3
      4
      function [jVal, gradient] = costFunction(theta)
        jVal = [...code to compute J(theta)...];
        gradient = [...code to compute derivative of J(theta)...];
      end
      1
      2
      3
      options = optimset('GradObj', 'on', 'MaxIter', 100);
      initialTheta = zeros(2,1);
         [optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);

3. Multiclass Classification 多类别分类问题

  1. one-vs-all 一对多分类算法

    划分为多个二分类问题，求多个h(x)。应用于预测集时，将x分类到h最大的那个集里。

    \(h^{(i)}_\theta(x)=P(y=i|x;\theta),\quad prediction=\max\limits_{i}(h^{(i)}_\theta(x))\)

4. Overfitting 过拟合

  1. underfitting —— 高bias偏差（Bias反映的是模型在样本上的输出与真实值之间的误差，即模型本身的精准度，即算法本身的拟合能力）

    Overfitting —— 高variance方差（variance反映的是模型每一次输出结果与模型输出期望之间的误差，即模型的稳定性。反应预测的波动情况。）

    关于方差与偏差的意义参见这里

    1. 解决过拟合：
    • 减少特征的数量
      • 手动选择保留的特征
      • 模型选择算法model selection algorithm，可以自动决定要保留的变量和要剔除的变量
      • 缺点：剔除了一部分信息
    • regularization 正则化
      • 保留所有变量，减少变量θ的magnitude
      • 在有很多变量时很有用
    1. 正则化
    • 在代价函数加一个正则化项，使得参数θ尽可能小，排除bias偏差项

    \[ \min\limits_\theta\frac{1}{2m}\sum \limits_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\lambda\sum\limits_{j=1}^n\theta_j^2 \]

    • λ是正则化参数regularization parameter

    • 应用于梯度下降法：（注：\(\theta_0\)一定不要正则化！） \[ \theta_j:=\theta_j-\alpha\frac {\partial} {\partial \theta_j}J(\theta)=\theta_j-\alpha[\frac {1}{m}\sum \limits_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda}{m}\theta_j]\quad(for\ j=1...n) \]

    • 应用于正规方程normal equation： \[ \theta=(X^TX+\lambda\cdot L)^{-1}X^Ty\\ where \quad L=\begin{bmatrix}0\\\ &1\\\ &\ &1\\\ &\ &\ &\ddots\\\ &\ &\ &\ &1\\\end{bmatrix} \]

      • Non-invertibility 不可逆性 suppose \(m\le n\), 特征多于例子时，\(\theta=(X^TX)^{-1}X^Ty\) 中，\(X^TX\)是不可逆的（或奇异的），即为退化矩阵（degenerate） 但是加入λL 后，解决了上述问题，公式（9）括号内的矩阵是可逆的（前提是λ>0）
Related Posts