Table of Contents

• 逻辑回归
  • [Logist 函数](#Logist 函数)
  • 目标函数
  • [最大似然求解Loss Function](#最大似然求解Loss Function)
  • 运用梯度下降得到参数更新递推公式
  • Logistic回归与梯度上升法
  • 逻辑回归解决多分类问题
    • 方法一：OvR
    • 方法二：OvO
    • 方法三：softmax
• 朴素贝叶斯
  • 条件概率
  • 极大似然估计
• SVM
  • 目标
  • 支持向量
  • 最优化问题
  • 对偶问题
  • 求支撑向量
  • 求分界线
  • 运用梯度下降方法求解SVM
• 决策树
  • 决策树针对缺失数据的处理办法
  • 信息熵
  • 决策树类型
    • ID3
    • C4.5
    • CART
• 感知机算法
  • 目标
  • 运用梯度下降进行求解
  • 具体做题步骤
• LDA
  • 主要思想
  • 模型建立
  • 二分类
  • 多分类

逻辑回归

标准逻辑回归是结果为0，1的二分类算法。目标是求$P(y_i=1\Vert x_i,w)$，若其大于$\frac{1}{2}$，则预测分类结果为1，否则为0。

Logist 函数

令$p(x_i)=P(y_i=1\Vert x_i,w)$，构建$p(x_i)$与$w^T{x}_i$之间的关系式。

首先提出以下猜想

$p(x_i)=w^T{x}_i？\log p(x_i)=w^T{x}_i$？

由于$0\le p(x)\le 1$, $w^T{x}_i$是无界的。于是我们说以上等式都是不成立的，因此又有了以下猜想

$\log \frac{p(x_i)}{1-p(x_i)}=w^T{x}_i$

可以证明$\text{odd}=\frac{p(x_i)}{1-p(x_i)}$的范围是[0,$\inf$]，则等式成立。我们称其为logist函数。

则可以化简得到

$$p(x_i)=\frac{1}{1+e^{-w^T{x}_i}}$$

可以类比Sigmoid函数发现，$p(x_i)$与Sigmoid函数一致。因此我们设$p(x_i)=g(w^T{x}_i)$。

目标函数

$$ma{x}_w\prod _{i=1}^{n}P(y_i|x_i,w)$$

其中

$$P(y_i|x_i,w)=P(y_i=1|x_i,w{)}^{y_i}P(y_i=0|x_i,w{)}^{1-y_i}$$

最大似然求解Loss Function

令

$$J=\prod _{i=1}^{n}P(y_i|x_i,w)$$

$$=\prod _{i=1}^{n}g(w^T{x}_i{)}^{y_i}(1-g(w^T{x}_i){)}^{1-y_i}$$

$$\log J=\sum _{i=1}^m{y}_i\ln (g(w^T{x}_i))+(1-y_i)\ln (1-g(w^T{x}_i))$$

$$\text{Loss}=-\log J$$

目标函数为

$$\underset{w}{\min }-\log J(w)$$

其中$g$ 为sigmoid函数

运用梯度下降得到参数更新递推公式

对Loss函数求导

$$\frac{\partial -\log J}{\partial w}=-\sum _{i=1}^n[y_i\frac{\frac{\partial g(w^T{x}_i)}{\partial w}}{g(w^T{x}_i)}+(1-y_i)\frac{\frac{-\partial g(w^T{x}_i)}{\partial w}}{1-g(w^T{x}_i)}]$$

由于令$z_i=w^T{x}_i$，则有

$$\frac{\partial g(w^T{x}_i)}{\partial w}=\frac{\partial g(z_i)}{\partial z_i}\frac{\partial z_i}{\partial w}$$

又因为

$$\frac{\partial g(z_i)}{\partial z_i}=g(z_i{)}^{\prime }=g(z_i)(1-g(z_i))$$

于是整合得

$$\frac{\partial -\log J}{\partial w}=\sum _{i=1}^n(g{z}_i)-y_i)x_i$$

根据梯度定义得到

$$w:=w-\alpha \sum _{i=1}^n(g{z}_i)-y_i)$$

Logistic回归与梯度上升法

逻辑回归解决多分类问题

方法一：OvR

• 思想：

n 种类型的样本进行分类时，分别取一种样本作为一类，将剩余的所有类型的样本看做另一类，这样就形成了 n 个二分类问题，使用逻辑回归算法对 n 个数据集训练出 n 个模型，将待预测的样本传入这 n 个模型中，所得概率最高的那个模型对应的样本类型即认为是该预测样本的类型；

• 时间复杂度：O(n)
• 示意图
  
  

方法二：OvO

• 思想

n 类样本中，每次挑出 2 种类型，两两结合，一共有$C_n^2$种二分类情况，使用$C_n^2$种模型预测样本类型，有$C_n^2$个预测结果，种类最多的那种样本类型，就认为是该样本最终的预测类型；

• 时间复杂度：$O(n^2)$
• 示意图
  
  

方法三：softmax

• 思想

由于发现OvR的所有概率相加通常会超过1，因此对OvR进行改进，对概率进行归一化

• 推导

令$z_i^j=(w^j{)}^T{x}_i$,其中$w^j$表示第$j$类的权重(是个列向量)，$、x_i$表示第$i$个样本(是个列向量)。

将$z_i^j$映射到$y_j(z_i)=e^{z_i^j}/\sum _{c=1}^C{e}^{z_i^c}$，其中C表示有C个类，$y_j(z_i)$表示第$j$类的softmax值，即样本$i$属于$j$类的概率

令$$gs(z_i)=[y_1(z_i),y_2(z_i),\dots ,y_C(z_i){]}^T$$
相当于用矩阵表示

$Ps(w^{T}x)=\frac{exp(w^{T}x)}{1^{T}exp(w^{T}x)},其中1是全为1的向量,w=[w^1,w^2,\dots ,w^C{]}^T$

用统计学知识解释，那么在多分类问题中，假设类别标签y∈{1, 2, …, C}有C个取值，那么给定一个样本x，softmax回归预测x属于类别i的后验概率为：

$$P(y=i|x;w_i)=\frac{exp(w_i^{T}x)}{{\sum }_{c=1}^{C}exp(w_c^{T}x)}.$$

• 示意图
  
• 目标函数

L=${\sum }_k{t}_k\cdot lnP(y=k)$，其中目标类的$t_k$为1，其余类的$t_k$为0

• 权重递推公式

由于对比普通逻辑回归，只是改变了映射函数

logistic的递推公式

$$w:=w+\alpha \sum _{i=1}^C(x_i(y_i-g(w^T{x}_i)))w:=w-\alpha X^T(g(w^{T}X)-y)$$

则softmax的递推公式

$$w:=w+\alpha \sum _{i=1}^C(x_i(y_i-Ps(w^T{x}_i)))w:=w-\alpha X^T(Ps(w^{T}X)-y)$$