AI Fundamentals - C4 监督学习

机器学习基础：数据驱动学习(data-driven learning)

机器学习分类：

监督学习(supervised learning)：有标签数据，回归或者分类
无监督学习(un-supervised learning)：无标签数据，聚类或者降维
强化学习(reinforcement learning) ：序列数据决策，与从环境交互

监督学习

监督学习的三个要素是对象、方法和评估。

**对象-标注数据：**训练和测试数据：训练集，测试集。应用到未知数据集

方法-学习模型：
生成方法 (generative approach) -生成模型(generative model)
学习联合概率分布𝑃（𝑋, 𝑌）
方法：贝叶斯方法、隐马尔可夫链

判别方法 (discriminative approach)-判别模型(discriminative model)
学习判别函数𝒇(X)或者条件概率分布𝑷(Y|𝑿) 。
包括：回归模型、神经网络、支持向量机、Ada boosting

评估-损失函数

常用损失函数：
经验风险(empirical risk )：训练集中数据产生的损失，表征训练数据拟合程度。
ERM：经验风险最小化
$\min_{f \in \Phi}{\frac{1}{n}\sum_{i = 1}^{n}{Loss(y_i,f(x_i))}}$
期望风险(expected risk): 当测试集中存在无穷多数据时产生的损失，表征学习所得模型效果。
$\min_{f \in \Phi}{\int_{x \times y}{Loss(y,f(x))P(x,y) dxdy}}$
注意样本容量趋于无穷时，经验风险趋于期望风险。但现实中训练样本数有限，要对经验风险进行一定的约束。
过学习(over-fitting)：经验风险小，期望风险大
欠学习(under-fitting)：经验风险、期望风险均大
好的算法应该泛化能力强，经验风险、期望风险均小
结构风险(structural risk minimization)最小化：引入正则化项 (regulatizer) 或惩罚项 (penalty term )
$\min_{f \in \Phi}{(\frac{1}{n} \sum_{i = 1}^{n}{Loss(y_i,f(x_i))} + \lambda J(f))}$

回归分析

一元线性回归：𝒚 = 𝒂𝒙 + b

方法：最小二乘法。可对𝑳(𝒂, 𝒃)参数𝒂和𝒃分别求导，令其导数值为零，再求取参数𝒂和𝒃的取值。

𝑳（𝒂, 𝒃） = ∑^{n}_{𝒊=𝟏}（𝒚𝒊 -𝒂𝒙_𝒊 -𝒃 )^𝟐

a = \frac{\sum_{i = 1}^{n}{x_iy_i} - n\bar{x}\bar{y}}{\sum_{i = 1}^{n}x_i^2 - n\bar{x}^2},\quad b = \bar{y} - a\bar{x}

多元线性回归：𝒚 = 𝒂’·𝒙 + a0

f(x_i) = a_0 + \sum_{j = 1}^{D}{a_jx_{i,j}} = a_0 + \vec{a}^\tau\vec{x}_i

最小化目标：

J_m = \frac{1}{m} \sum_{i = 1}^{m}{((y_i) - f(\vec{x}_i))^2}

同样通过求导可令

\nabla{J(a)} = -2X(y - X^\tau\vec{a}) = 0

即有

XX^\tau\vec{a} = X\vec{y}

\vec{a} = (XX^\tau)^{-1}X\vec{y}

线性回归对离群点（outlier)敏感，离群点会导致模型建模不稳定，结果有偏。

逻辑斯蒂回归/对数几率回归

引入 sigmoid函数：

y = \frac{1}{1 + e^{-z}}

单调递增，值域为(0，1)。输出可作为概率值。
对输入𝑧取值范围没有限制。但当𝑧大于（小于）一定数值后，函数输出无限趋近于1（0）。y(0) = 0.5

用于二分类问题：
y = 1表示输入数据𝒙属于正例，y = 0表示输入数据𝒙属于负例。
y理解为输入数据𝒙为正例概率，1-y理解为输入数据x为负例的概率。
几率：p / (1-p) ，反应相对可能性。从而定义对数几率/logit函数

判断（属于正例）：输入数据𝒙，属于正例的概率大于其属于负例的概率。即𝑝(𝑦=1| 𝒙) > 0.5。这等价于 $\frac{p(𝑦=1| 𝒙)}{p(𝑦= 0| 𝒙)} > 1$ ,即log(……) = 𝒘’𝒙 + b > 0成立。是线性回归。

参数w,b优化
D表示观测（训练）数据，𝜃 = {𝒘, 𝑏}表示模型参数。假设观测所得每一个样本数据是独立同分布(independent and identically distributed, i.i.d）
取对数有

最大似然估计MLE目的是计算似然函数的最大值，而分类过程是需要损失函数最小化。因此在上式前加一个负号作为损失函数(交叉熵)
求θ偏导，注意ℎθ’ (𝑥) = ℎθ(𝑥)(1-ℎθ(𝑥))
则梯度下降公式

MLE和MAP

决策树

通过树形结构来进行分类。可以看作是一系列以叶子节点为输出的决策规则（Decision Rules）.
每个非叶子节点：对分类目标在某个属性上的判断，每个分支代表基于该属性做出的一个判断.
每个叶子节点: 一种分类结果

信息熵

𝐾个信息组成了集合样本𝐷，记第𝑘个信息发生的概率为𝑝k.则信息熵
表征了𝑫的纯度。ED越小，纯度越高，𝑫包含的信息越确定。

好的决策树：划分属性的顺序选择重要。性能好的决策树随着划分不断进行，决策树分支结点样本集的“纯度”会越来越高，即其所包含样本尽可能属于相同类别。

构建决策树

计算选择不同属性作为划分的指标。
选择最佳指标（最小）对原样本集进行划分。
重复以上操作直到划分后的不同子样本集都只存在同类样本。

指标的选择

信息增益：原来熵减新熵
信息增益率：纳入划分本身带来的信息info
Gini：从样本中选取样本同类的概率，更快。

线性区别分析LDA /FDA

对于一组具有标签信息的高维数据样本，LDA利用类别信息将其线性投影到一个低维空间上，使得低维空间中同一类别样本尽可能靠近，不同类别样本尽可能彼此远离。

二分类

最小化𝑠1+𝑠2：投影后归属于同一类别的样本数据在投影后的空间中尽可能靠近。
最大化|𝑚1 -𝑚2|^2 : 投影后归属于两个类别的数据样本中心尽量远。
综上即最大化：

提取特征有类间散度矩阵(between-class scatter matrix)Sb：

和类内散度矩阵(within-class scatter matrix)Sw:

由于𝐽 (𝒘) 的分子和分母都是关于𝒘的二项式，最后解只与𝒘的方向有关，与𝒘的长度无关.
令分母𝒘’ Sw w = 1，然后用拉格朗日乘子法来求解这个问题。

对𝒘求偏导并使其求导结果为零，结果有λ和w分别是特征根、特征向量。

令实数λ_{w} = (m2-m1)’ w,则有
把λ_{w}和λ放在w侧，取新的w约去（大小不影响)有：

多分类

优化目标：

步骤

计算数据样本集中每个类别样本的均值
计算类内散度矩阵𝑺𝒘和类间散度矩阵𝑺𝒃
根据𝑺𝒘^{-1}𝑺𝒃𝑾 = λ𝑾 求解𝑺𝒘^{-1}Sb特征向量 𝒘𝟏, 𝒘𝟐,… , 𝒘𝒓 ，构成矩阵𝑾
通过矩阵𝑾将每个样本映射到低维空间，实现特征降维。

LDA和PCA

Ada Boosting 自适应提升

对于一个复杂的分类任务，可以将其分解为若干子任务，然后将若干子任务完成方法综合，最终完成该复杂任务。
组合弱分类器(weak classifiers) 形成一个强分类器(strong classifier)。

计算学习理论

可计算：图灵可停机
霍夫丁不等式(Hoeffding’s inequality)

概率近似正确（PAC）

研究范围：假设正确/训练数据规模/假设空间复杂度/假设空间选择
概念：学习任务、实例集和概念集（对应）、假设空间、实例分布和数据集。
强可学习模型和弱可学习模型
强可学习和弱可学习是等价的。

Ada Boosting 的核心问题

如何在每个弱分类器学习过程中改变训练数据的权重：提高在上一轮中分类错误样本的权重。
如何将一系列弱分类器组合成强分类器：加权多数表决方法提高分类误差小的弱分类器的权重，减少分类误差大的弱分类器的权重。

算法描述

数据样本权重（均等）初始化
分别训练第𝒎个弱分类器 - 序列化学习机制
- 使用具有分布权重𝑫𝒎的训练数据来学习得到第𝒎个基分类器（弱分类器）𝑮𝒎
- 计算𝑮𝒎 （𝒙）在训练数据集上的加权分类误差
- 根据误差计算分类器权重
- 更新样本分布权重
  𝒁𝒎是归一化因子。
在开始训练第𝒎+𝟏个弱分类器𝑮𝒎+𝟏 之前对训练数据集中数据权重进行调整.
以线性加权形式来组合弱分类器𝒇(x)

注意 𝜶𝒎累加之和并不等于1。