算法岗知识汇总【机器学习】

损失函数

常用损失函数

均方误差（MSE,L2）: $L=(y-\hat{y})^2$ （回归任务常用，隐含的预设是数据误差符合高斯分布）
绝对误差（MAE,L1）: $L=|y-\hat{y}|$
二值交叉熵（BCE）： $L=\frac{1}{N}\sum_i -[ y_i* log(p_i)+(1-y_i)*log(1-p_i)]$ ;
交叉熵（CE）： $L=\frac{1}{N}\sum_i\sum\limits_{c=1}^M -y_{ic}log(p_{ic})$ ;（倾向于任务数据接近多项式分布）
Cross Entropy的推导过程

KL(p,q) = H(p,q) - H(p)，因此优化交叉熵实际上是优化p和q分布之间的KL散度。
回归任务中MAE和MSE的理解和区别
MAE：
- 优点：
1. 直观易懂：MAE直接反映了平均预测误差，单位与原始数据一致，易于解释。
2. 对异常值不敏感：由于没有平方运算，MAE对异常值的影响较小，更加稳健。
3. 优化稳定：MAE损失函数的梯度平滑，使得优化算法收敛更加稳定
- 缺点:
1. 对大误差不敏感：MAE对较大的误差没有特别的惩罚，因此在某些需要更严格控制大误差的应用中可能不适用。
2. 不可微性：MAE在零点处不可微，这在一些优化算法中可能会引起问题，尽管通过技术手段可以缓解这一问题。

MSE:

优点：

对大误差敏感：MSE通过平方项放大了大误差的影响，适用于需要严格控制大误差的应用

数学性质好：MSE的二次损失函数具有良好的数学性质，便于推导和计算，特别是在最小二乘法中应用广泛

缺点：

异常值影响大：由于对大误差的敏感性，异常值会显著影响MSE，使得模型对异常值过度关注。

解释性差：MSE的单位是原始数据单位的平方，不直观，需要转化为RMSE来辅助解释。

交叉熵伪代码

def softmax(x):
	exps = np.exp(x - np.max(x)) # 防止上溢
    return exps / np.sum(exps)
	
def cross_entropy_error(p,y):
    delta=1e-7       #添加一个微小值可以防止负无限大(np.log(0))的发生。
	p = softmax(p)   # 通过 softmax 变为概率分布，并且sum(p) = 1
    return -np.sum(y*np.log(p+delta))

分类任务为什么常用交叉熵而不是MSE？
- 问题本质：交叉熵损失函数是为分类问题设计的，而均方误差是为回归问题设计的。分类问题的目标是预测一个离散的标签，而回归问题的目标是预测一个连续的值。交叉熵直接衡量的是预测概率分布与真实分布之间的差异。
- 梯度大小：交叉熵损失函数的梯度在预测错误时相对较大，这有助于模型在训练初期快速学习。而MSE的梯度随着预测值接近真实值而减小，这可能导致训练过程在后期变得缓慢。
- 优化问题：MSE在分类问题中是一个非凸优化，可能收敛到局部最优值；而交叉熵是凸优化，能够收敛到全局最优值。
- 归一化：交叉熵损失函数对类别进行了归一化处理，这意味着不同类别的预测误差对损失的贡献是相等的。而MSE可能会偏向于数值较大的类别。
如何选择损失函数？

需要出于对数据分布的假设，不同的loss隐式地对数据分布有要求。例如L2隐含的是数据误差符合高斯分布。

正则化

L0正则项
$||x||_0= \#(i),with\ i\neq 0.$ $∣∣ x ∣ ∣_{0} = # (i), w i t h i \neq = 0.$
- 使用L0正则项可以使尽可能多的参数为0。可以使模型稀疏化且易于解释，并且在某种意义上实现了「特征选择」。
- 但L0正则项存在缺点：（1）非连续（2）非凸（3）不可导。因此转而考虑L0范数最紧的凸放松：L1范数。
L1正则项(Lasso Regularizer)

$||x||_1=\sum|x_i|;$
考虑目标函数： $Obj(F)=L(F)+\lambda\cdot l_1\frac{||w||_1}{n}$

有对wi的偏导数： $\frac{\partial{Obj}}{\partial{w_i}}=\frac{\partial{L}}{\partial{w_i}}+\frac{\lambda l_1}{n}sgn(w_i)$

因此有参数更新过程:
$w_i'=w_i-\eta\frac{\partial{L}}{\partial{w_i}}-\eta\frac{\lambda l_1}{n}sgn(w_i)$
因为 $\eta\frac{\lambda l_1}{n}\gt 0$ ，所以多出的项 $\eta\frac{\lambda l_1}{n}sgn(w_i)$ 使得w_i趋近0，实现稀疏化。
为什么加入L1正则项有助于阐述稀疏解呢？

假设对于某个i来说，wi=0。然后在接下来的迭代中，wi被更新为 $w_i\larr 0-\eta\frac{\partial{Obj}}{\partial{w_i}}$ ，而其他参数保持不变。

对于L1正则项来说，在这一轮迭代中增加了 $\Delta{\Omega}=\eta\frac{\lambda_1}{n}|\frac{\partial{Obj}}{\partial{w_i}}|$ ;对于损失函数来说，在这一轮迭代中下降了 $\Delta{L}=\eta|\frac{\partial{Obj}}{\partial{w_i}}| |\frac{\partial{L}}{\partial{w_i}}|$ 。而如果 $\Delta{L}\lt\Delta{\Omega}$ ，那么目标函数整体是变大了。

因此对于这种情况，优化器会拒绝更新wi，也就是拒绝将wi更新为非0值。由此得到相对稀疏的模型。
L2正则项(Ridge Regularizer)

$||x||_2=(\sum x_i^2)^{\frac{1}{2}}$
因此有目标函数： $Obj(F)=L(F)+\lambda\cdot l_2 \frac{||w||_2^2}{2n}$

对参数wi的偏导数，有： $\frac{\partial{Obj}}{\partial{w_i}}=\frac{\partial{L}}{\partial{w_i}}+\frac{\lambda l_2}{n}w_i$

有参数更新：
$w_i'=w_i-\eta\frac{\partial{L}}{\partial{w_i}}-\eta\frac{\lambda l_2}{n}w_i\\=(1-\eta\frac{\lambda l_2}{n})w_i-\eta\frac{\partial{L}}{\partial{w_i}}$
因此，引入L2正则项后，相当于衰减了参数的权重，使参数趋近于0.
L1正则项与L2正则项的区别
为什么使用 L1-正则项，会倾向于使得参数稀疏化；而使用 L2-正则项，会倾向于使得参数稠密地接近于零？

对于目标函数Obj(F)来说，实际上是要在正则项的等值线与损失函数的等值线中寻找一个交点，使得二者的和最小。
- 对于 L1-正则项来说，因为 L1-正则项的等值线是一组菱形，这些交点容易落在坐标轴上。因此，另一个参数的值在这个交点上就是零，从而实现了稀疏化。
- 对于 L2-正则项来说，因为 L2-正则项的等值线是一组圆形。所以，这些交点可能落在整个平面的任意位置。所以它不能实现「稀疏化」。但是，另一方面，由于 (w1,w2)落在圆上，所以它们的值会比较接近。这就是为什么 L2-正则项可以使得参数在零附近稠密而平滑。

评估指标

TP,FP,TN,FN

TP（True Positive）: 预测为正，实际为正
FP（False Positive）: 预测为正，实际为负
TN（True Negative）：预测为负，实际为负
FN（false negative）: 预测为负，实际为正
Accuracy,Precision,Recall,F-Score

Accuracy = (TP+TN)/N
Precision = TP/(TP+FP)
Recall = TP/(TP+FN)
F1-Score = (2* Precision * Recall)/(Precision+Recall)
上述指标用于评估二分类问题。
P-R曲线

P-R曲线：横轴是Recall，纵轴是Precision。
ROC曲线

ROC曲线：横轴是FPR=FP/(FP+TN),表示所有真实为负的样本中，被错误预测为正的比例；纵轴是TPR=TP/(TP+FN)，表示所有真实为正的样本中，被正确预测为正的比例。
如何画ROC曲线？

假设我们预测出（z,0.08）,(a,0.1),(b,0.2),(c,0.4),(d,0.5)，然后我们在预测结果中选择每一个样本的分值作为阈值，比如第一个数据（a,0.1）则分值大于等于0.1的都为正样本，小于0.1的为负样本，然后便根据这些样本算出一组FPR,与TPR值，得到ROC曲线上的一点，对所有测试用例做一遍操作，便可以绘制得到ROC曲线图。
AUC的定义
AUC(Area Under Curve)：
- 第一个定义：ROC曲线下的面积大小，AUC越大，说明分类器越可能把真正的正样本排在前面，分类性能越好。
- 第二个定义：正样本被预测成正样本(TP)的得分大于负样本被预测成正样本(FP)的得分的概率。

AUC的计算方法

ROC曲线方法：

import numpy as np
import matplotlib.pyplot as plt

roc_point = []
    for i in range(num):
        i = pred_prob[i]
        TP = 0  # 真阳样本数
        FP = 0  # 假阳样本数
        TP_rate = 0.  # 真阳率
        FP_rate = 0.  # 假阳率
        pos_num = 0   # 预测真样本数

        # 计数过程
        for ind, prob in enumerate(pred_prob):
            if prob>i:
                pos_num += 1
            if prob>i and labels[ind]>0.5:
                TP+=1
            elif prob>i and labels[ind]<0.5:
                FP+=1
        if pos_num!=0:
            TP_rate = TP / sum(labels)
            FP_rate = FP / (num-sum(labels))
        roc_point.append([FP_rate, TP_rate])  # 记录ROC中的点
    # 画出ROC曲线
    roc_point.sort(key=lambda x: x[0])
    plt.plot(np.array(roc_point)[1:, 0], np.array(roc_point)[1: ,1])
    plt.xlabel("FPR")
    plt.ylabel("TPR")
    plt.show()

    # 计算每个小长方形的面积，求和即为auc
    lastx = 0.
    for x,y in roc_point:
        auc1 += (x-lastx)*y  # 底乘高
        lastx = x

    print("方法一 auc:", auc1)

排序方法

其中\sum{rank}为正样本序号之和，M为正样本数，N为负样本数。（正样本这里有个特殊情况在于当正负样本概率相等时，可能排在前面也可能在后面，如果单纯将正样本排在前面或者后面计算，计算结果与前面的会有偏差。可以将两者样本序号取平均）

# 时间复杂度为O(nlogn)
    new_data = [[p, l] for p, l in zip(pred_prob, labels)]
    new_data.sort(key=lambda x:x[0])

    # 求正样本rank之和
    rank_sum = 0
    for ind, [prob,label] in enumerate(new_data):
        if label>0.5:
            rank_sum+=ind
    auc3 = (rank_sum - len(P_ind)*(1+len(P_ind))/2) / (len(P_ind)*len(F_ind))
    print("方法二 auc:", auc3)

解释AUC的定义，它解决了什么问题，优缺点是什么

当AUC=1时，分类器能够正确区分所有的正类点和负类点；当AUC=0.5时，分类器无法区分正类点和负类点，即相当于随机猜测。
AUC的优点包括：

AUC本身与模型预测score绝对值无关，只关注排序效果，衡量排序能力，适合排序类任务。

对正负样本均衡不敏感，在样本不均衡情况下也能够合理评估。

不需要手动设置阈值，是一种整体上的衡量方法。

然而，AUC也有一些缺点：

忽略了预测的概率值和模型的拟合程度。

反应信息较为笼统，无法反映召回率、精确率等实际业务关心指标。

没有给出模型误差的空间分布信息，只关心正负样本之间的排序，并不关心正负样本内部的排序，难以衡量样本对于实际程度的刻画能力。

多分类问题评价指标
- micro-F1
  取值范围：（0，1）
  权重倾向：每一个样本的权重都相同
  适用环境：多分类不平衡，若数据极度不平衡会影响结果。
  计算方式:
由micro-F1计算方式可以得知，

macro-F1
取值范围：（0,1）
权重倾向：每一类别的权重都相同；
适用环境：多分类问题，不受数据不平衡影响，容易受到高识别性（高recall，高precision）的类别影响。
计算方式：

weighted-F1
macro-F1的变种，将F1-score乘以该类的比例之后相加。

多元线性回归

import numpy as np
from tqdm import tqdm

class LinearRegression:

    def __init__(self,learning_rate=0.01,n_iters=5000):
        self.lr = learning_rate
        self.n_iters = n_iters
        self.w = None
        self.b = None

    def train(self,X,y):
        '''
        Train the model using the training data
        ------
        X: [n_samples,n_features]
        y: [n_samples]
        '''
        n_samples , n_features = X.shape

        self.w = np.zeros(n_features)
        self.b = 0

        for _ in tqdm(range(self.n_iters)):
            y_predicted = np.dot(X,self.w) + self.b
            loss = np.sum((y-y_predicted)**2) / n_samples

            ## 注意这里loss是负的，所以梯度要加上负号
            dw = -(2/n_samples) * np.dot(X.T,(y-y_predicted))
            db = -(2/n_samples) * np.sum(y-y_predicted)

            self.w = self.w - self.lr * dw
            self.b = self.b - self.lr * db
    
    def predict(self,X):
        return np.dot(X,self.w) + self.b

逻辑回归

逻辑回归是一种二分类算法，目的是预测二元输出变量（比如0和1）。

其使用一个参数化函数计算给定输入变量的输出概率。
$g(z)=\frac{1}{1+e^{-z}}$ ，z是输入变量的线性组合，可以表示为 $z=b+w_1x_1+w_2x_2+...+w_nx_n$
其训练的损失函数为最大化对数似然函数，这里即BCE。
$J(w) = -\frac{1}{n}\sum{y_i log\ g(z_i)+(1-y_i)log(1-g(z_i))}$
训练完成后，我们可以使用模型来预测新的样本的类别标签。预测类别标签的方法是，将新样本的特征向量代入 sigmoid 函数，计算输出概率，如果概率大于0.5，则预测为正例，否则预测为负例。

Python实现如下：

import numpy as np

def sigmoid(x):
    return 1./(1+np.exp(-x))

class LogisticRegression:
    def __init__(self, learning_rate=0.003, iterations=100):
        self.learning_rate = learning_rate # 学习率
        self.iterations = iterations # 迭代次数
        self.weights = None
        self.bias = None
        

    def fit(self, X, y):
        # X [N,d] , y [N]
        # 初始化参数
        self.weights = np.random.randn(X.shape[1])
        self.bias = 0
        
        # 梯度下降
        for i in range(self.iterations):
            # 计算sigmoid函数的预测值, y_hat = w * x + b
            y_hat = sigmoid(np.dot(X, self.weights) + self.bias)

            # 计算损失函数
            loss = -np.mean(y*np.log(y_hat)+(1-y)*np.log(1-y_hat))
            # 计算梯度
            dw = -np.dot(X.T,(y_hat-y)) / X.shape[0]
            db = -np.mean(y_hat-y)

            # 更新参数
            self.weights -= self.learning_rate * dw
            self.bias -= self.learning_rate * db

            # 打印损失函数值
            if i % 10 == 0:
                print(f"Loss after iteration {i}: {loss}")
    # 预测
    def predict(self, X):
        y_hat = sigmoid(np.dot(X, self.weights) + self.bias)
        y_hat[y_hat >= 0.5] = 1
        y_hat[y_hat < 0.5] = 0
        return y_hat
    
    # 精度
    def score(self, y_pred, y):
        accuracy = (y_pred == y).sum() / len(y)
        return accuracy

决策树

决策树模型

决策树根据样本属性对样本进行分类，其学习算法流程图如下：

由上可以看出，关键在于每次对最优划分属性的选取。根据对划分属性选取的规则不同，有不同的决策树算法。
ID3决策树（信息增益）

假设离散属性a有V个可能的取值，若使用a来对样本集D进行划分，所获得的信息增益定义如下：
$Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的”纯度提升”越大.因此，我们可用信息增益来进行决策树的划分属性选择。
C4.5决策树（增益率）

信息增益准则对可取值数目较多的属性有所偏好。为减少这种偏好可能带来的不利影响，可使用增益率作为最优划分属性准则。增益率定义为：
$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\\ 其中,IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log\frac{|D^v|}{|D|}$
IV(a)称为属性a的固有值，属性a的可能取值数目越多（即V越大），则IV(a)的值通常会越大。
CART分类决策树（基尼系数）

CART在分类和回归任务都可用。数据集D的纯度可用基尼值来度量：
$Gini(D)=1-\sum_{k=1}^{|y|}p_k^2$
直观来说， Gini(D) 反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率.因此， Gini(D) 越小，则数据集D的纯度越高.

属性a的基尼指数定义为：
$Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$
在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
CART回归决策树（MSE）

上面的c为每一个部分的均值。CART在每一次迭代的过程中利用贪心方法将结点二分，并且特征在下一次迭代中可以重复使用，每个节点的值是当前节点真实值的均值。
剪枝处理
降低决策树过拟合的风险。有预剪枝和后剪枝两种。
- 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;
- 后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.
如何判断决策树泛化性能是否提升呢?可以使用验证集进行性能评估。
连续值与缺失值处理

见西瓜书。

集成学习

集成学习的概念

集成学习通过构建并结合多个学习器来完成学习任务。
只包含同种类型的个体学习器是同质的，每一个称为基学习器；否则叫做异质的。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。

集成学习方法可分为两大类：

个体学习器间存在强依赖关系、必须串行生成的序列化方法。如Boosting。

个体学习器间不存在强依赖关系、可同时生成的并行化方法。如Bagging和随机森林。

偏差与方差的分解
- 偏差：偏差是指由有所采样得到的大小为m的训练数据集，训练出的所有模型的输出的平均值和真实模型输出之间的偏差。描述模型输出结果的期望与样本真实结果的差距。分类器表达能力有限导致的系统性错误，表现在训练误差不收敛。
- 方差：是指有所有采样得到的大小为m的训练数据集，训练出的所有模型的输出的方差。描述模型对于给定值的输出稳定性。分类器对样本分布过于敏感，到指在训练样本较少的时候，出现过拟合。

Boosting

Boosting族算法的工作机制

先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器;如此重复进行，直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权结合.
Adaboost的算法流程

Boosting 算法要求基学习器能对特定的数据分布进行学习，这可通过”重赋权法” (re-weighting) 实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重.对无法接受带权样本的基学习算法，则可通过”重采样法” (re-sampling) 来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练.

从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

Bagging与随机森林

欲得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立;虽然”独立”在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异.给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，我们获得的基学习器可望具有比较大的差异。同时还希望个体学习器不能太差：如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器.为解决这个问题，我们可考虑使用相互有交叠的采样子集。

Bagging的原理

基于自助采样法：给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。

照这样，我们可采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。

结合的策略有很多，通常对分类任务采用简单投票法，对回归任务采用简单平均法。

从偏差-方差分解的角度看， Bagging 主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
Bagging的优点
1. 标准AdaBoost只适用于二分类任务；Bagging能不经修改地用于多分类、回归等。
2. :由于每个基学习器只使用了初始训练集中约 63.2% 的样本，剩下约 36.8% 的样本可用作验证集来对泛化性能进行”包外估计” (out-of-bag estimate)。
随机森林的原理
RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。
- 传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性;
- 在RF中，对基决策树的每个节点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性划分。若k=d，则基决策树的构建与传统决策树相同；若k=1，则完全基于随机划分。
Bagging方法的结合策略
- 平均法：对数值型输出，常用简单平均法和加权平均法。
- 投票法：对分类任务来说，最常用投票法，有绝对多数投票法、相对多数投票法和加权投票法。其中，如果基于类标记，则称为硬投票；如果基于类概率，称为软投票。
- Stacking：通过另一个学习器来进行结合，用于结合的学习器称为次级学习器。Stacking 先从初始数据集训练出初级学习器，然后”生成”一个新数据集用于训练次级学习器.在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。
在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大;因此,一般是通过使用交叉验证或留一法这样的方式用训练初级学习器未使用的样本来产生次级学习器的训练样本。

梯度提升树(GBDT)

GBDT的概念

GBDT(Gradient Boosting Decision Tree)，是一种以CART回归树为基学习器的Boosting模型（所以优化的是偏差），其中每一步的拟合目标是目标函数的负梯度。

GBDT是加性模型，其最后回归结果是多个基模型结果之和。

在GBDT中，残差的概念是目标函数的负梯度（当目标函数是MSE时，就是目标值和预测值的差值）。
GBDT的算法流程
我们用M表示决策树的数量， $f_m(x_i)$ 表示第m论训练之后的决策树， $f(x_i)$ 表示最终输出的GBDT模型。
1. 初始化
首先创建第一棵回归树 $f_1(x)$ ，它是直接拟合目标值的结果，是单个节点的树，即： $f_1(x)=argmin_c\sum_{i=1}^N L(y_i,c)$ ，其中c为当前节点值。（当目标函数为MSE时，c就是所有节点的均值）
1. 迭代
对于第2到第m棵回归树，我们要对训练集中每个样本计算出训练目标，也就是前面结果的残差：
$r_{mi}=-[\frac{\partial{L(y_i,f_{m-1}(x_i))}}{\partial{f_{m-1}(x_i)}}]$ $r_{mi} = - [\frac{\partial L ( y _{i} , f _{m - 1} ( x _{i} ))}{\partial f _{m - 1} ( x _{i} )}]$
对于当前第m棵子树而言，我们需要遍历它的可行的切分点以及阈值，找到最优预测值c，使其尽可能逼近残差，公式为：
$c_{mj}=argmin_c\sum_{x_i\in R_{mj}} L(y_i,f_{m-1}(x_i)+c)$ $c_{mj} = a r g mi n_{c} \sum_{x_{i} \in R_{mj}} L (y_{i}, f_{m - 1} (x_{i}) + c)$
这里的 $R_{mj}$ 指第m棵子树所有的划分方法中叶子节点预测值的集合，也就是第m棵回归树可能达到的预测值。

由此不断迭代得到下一棵子树的训练目标。
1. 最终我们得到回归树
$F(x)=\sum_{m=1}^M f_m(x)=\sum_{m=1}^M\sum_{j=1}^J c_{mj} I(x\in R_{mj})$ $F (x) = \sum_{m = 1}^{M} f_{m} (x) = \sum_{m = 1}^{M} \sum_{j = 1}^{J} c_{mj} I (x \in R_{mj})$
GBDT训练过程中的Shrinkage

是一种优化避免GBDT陷入过拟合的正则化方法，这个方法的本质是减小每一次迭代对于残差的收敛程度。具体的表现措施就是给我们的每一棵回归树的结果乘上一个类似于学习率的参数，通过增大回归树的个数来弥补。
$f_m(x)=f_{m-1}(x)+\gamma \sum_{j=1}^J c_{mj}I(x\in R_{mj})$
GBDT的优缺点
- 优点：（1）灵活处理各种类型的数据（连续、离散）（2）易于特征组合、特征选择（3）相对少调参，预测精度高（4）可解释性强
- 缺点：（1）串行生成，并行难（2）数据维度高，计算复杂度高。

XGBoost

XGBoost的概念
- XGBoost的目标函数：
  模型的预测精度由模型的偏差和方差共同决定，损失函数代表了模型的偏差，想要方差小则需要在目标函数中添加正则项，用于防止过拟合。
$Obj=\sum_{i=1}^n L(y_i,\hat{y}_i)+ \sum_{i=1}^t\Omega(f_i)$ $O bj = \sum_{i = 1}^{n} L (y_{i}, \overset{y}{^}_{i}) + \sum_{i = 1}^{t} Ω (f_{i})$
由于XGBoost是boosting算法，遵从前向分布加法，因此第t步的目标函数可以写为：
$Obj^{(t)}=\sum_{i=1}^n L(y_i,\hat{y}_i^{(t)})+ \sum_{i=1}^t\Omega(f_i)\\ =\sum_{i=1}^n L(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\sum_{i=1}^t\Omega(f_i)\\ =\sum_{i=1}^n [L(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega(f_t)] + constant$ $O b j^{(t)} = \sum_{i = 1}^{n} L (y_{i}, \overset{y}{^}_{i}^{(t)}) + \sum_{i = 1}^{t} Ω (f_{i}) = \sum_{i = 1}^{n} L (y_{i}, \overset{y}{^}_{i}^{(t - 1)} + f_{t} (x_{i})) + \sum_{i = 1}^{t} Ω (f_{i}) = \sum_{i = 1}^{n} [L (y_{i}, \overset{y}{^}_{i}^{(t - 1)} + f_{t} (x_{i})) + Ω (f_{t})] + co n s t an t$
计算时，对损失函数L进行二阶泰勒展开：
$L(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))=L(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)$ $L (y_{i}, \overset{y}{^}_{i}^{(t - 1)} + f_{t} (x_{i})) = L (y_{i}, \overset{y}{^}_{i}^{(t - 1)}) + g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})$
其中，gi为损失函数一阶导，hi为二阶导。注意这里的求导是对 $\hat{y}_i^{(t-1)}$ 求导。

其中第一项是一个常数，对优化不会产生影响。因此，去掉全部的常数项，得到目标函数为：
$Obj^{(t)}=\sum_{i=1}^n[g_i f_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)$ $O b j^{(t)} = \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + Ω (f_{t})$

正则化项

XGBoost对决策树的复杂度定义为：
$\Omega(f_t)=\gamma T+\frac{1}{2}\lambda \sum_{j=1}^Tw_j^2$
T为叶子节点的个数，后一项为叶子节点数值的L2范数。

将其代入XGBoost的目标函数，可得其目标函数：
$Obj^{(t)}=\sum_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T$
其中，Gj是通过前t-1步得到的叶子节点j所包含样本的一阶偏导数累加之和，Hj通过前t-1步得到的叶子节点j所包含样本的二阶偏导数累加之和，两者的值已知，可视为常数。

XGBoost采用的最优切分点划分算法
与CART一样采用贪心算法：

从树的深度为0开始：

对每个叶节点枚举所有的可用特征；

针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；

选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集；

回到第1步，递归执行直到满足特定条件为止；

XGBoost与GBDT的区别
1. GBDT将目标函数泰勒展开到一阶，而xgboost将目标函数泰勒展开到了二阶。
2. GBDT是给新的基模型寻找新的拟合标签（前面加法模型的负梯度），而xgboost是给新的基模型寻找新的目标函数（目标函数关于新的基模型的二阶泰勒展开）。
3. xgboost加入了和叶子权重的L2正则化项，因而有利于模型获得更低的方差。
4. xgboost增加了自动处理缺失值特征的策略。通过把带缺失值样本分别划分到左子树或者右子树，比较两种方案下目标函数的优劣，从而自动对有缺失值的样本进行划分，无需对缺失特征进行填充预处理。
5. XGBoost采用了Shrinkage 和Column Subsampling方法，这两种方法都能在一定程度上防止过拟合。(Column Subsampling就是在同层每个节点分裂之前，先随机选择特征子集来筛选，类似RF)。
6. 同级的节点可以并行化训练。
7. XGBoost支持多种基分类器，包括决策树、线性分类器。
XGBoost的优缺点
优点：
1. 使用了许多策略去防止过拟合，如：正则化项、Shrinkage、Column Subsampling等。
2. 目标函数使用了损失函数关于待求函数的二阶导数
3. 支持并行化同级层节点可并行化，具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行，加快训练速度。
4. 添加了对稀疏数据的处理
5. 采用了交叉验证以及early stop，防止建树过深
6. 支持设置样本权重，可以通过调整权重可以更加关注一些样本。

缺点：

xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；

xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.

LightGBM

LightGBM的主要改进点
- Histogram算法：直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数（其实又是分桶的思想，而这些桶称为bin，比如[0,0.1)→0, [0.1,0.3)→1），同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。（降低了内存消耗与计算代价）

带深度限制的Leaf-wise的叶子生长策略：
在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝；但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

LightGBM进行进一步的优化，采用的Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合

多层感知机(MLP)

Numpy实现MLP回归

import numpy as np
from tqdm import tqdm

class Layer:
    def __init__(self):
        pass
    
    def forward(self,input):
        pass
    
    def backward(self,output_gradient,lr):
        pass

class Linear(Layer):
    def __init__(self,input_size,output_size):
        self.input_size = input_size
        self.output_size = output_size
        self.w = np.random.randn(input_size,output_size) * np.sqrt(2.0/input_size)
        self.b = np.zeros((1,output_size))

    def forward(self,x):
        self.input = x
        return np.dot(x,self.w) + self.b
    
    def backward(self,output_gradient,lr):
        input_gradient = np.dot(output_gradient,self.w.T)
        weights_gradient = np.dot(self.input.T,output_gradient)
        self.w -= lr * weights_gradient
        self.b -= lr * np.sum(output_gradient,axis=0,keepdims=True)
        
        return input_gradient
    
class Activation(Layer):
    def __init__(self,activation,activation_prime):
        self.activation = activation
        self.activation_prime = activation_prime

    def forward(self,input):
        self.input = input
        return self.activation(input)
    
    def backward(self,output_gradient,lr):
        return np.multiply(output_gradient,self.activation_prime(self.input))
    
class ReLU(Activation):
    def __init__(self):
        def relu(x):
            return np.maximum(0,x)
        
        def relu_prime(x):
            return np.where(x>0,1,0)
        
        super().__init__(relu,relu_prime)

class MLPRegressor:
    def __init__(self,layers):
        self.layers = layers
        self.loss = None
        self.loss_prime = None

    def _mse(self,y_true,y_pred):
        return np.mean(np.power(y_true-y_pred,2))
    
    def _mse_prime(self,y_true,y_pred):
        return 2*(y_pred-y_true)/len(y_true)
    
    def fit(self,X,y,epochs=5000,lr=0.01):

        for epoch in tqdm(range(epochs)):
            output = X
            for layer in self.layers:
                output = layer.forward(output)

            loss = self._mse(y,output)

            grad = self._mse_prime(y,output)
            for layer in reversed(self.layers):
                grad = layer.backward(grad,lr)
    
    def predict(self,X):
        output = X
        for layer in self.layers:
            output = layer.forward(output)
        return output

if __name__ == '__main__':
    mlp = MLPRegressor([
        Linear(10,64),
        ReLU(),
        Linear(64,32),
        ReLU(),
        Linear(32,1)
    ])
    
    gt_w = np.random.randn(10,1)
    gt_b = np.random.randn(1)

    X = np.random.randn(100,10)
    y = np.dot(X,gt_w) + gt_b

    mlp.fit(X,y)

    preds = mlp.predict(X)
    print((y-preds).squeeze())

Numpy实现MLP分类

SVM

支持向量机（supporr vector machine，SVM）是一种二类分类模型，该模型是定义在特征空间上的间隔最大的线性分类器。间隔最大使它有区别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的最小化问题。使用Hinge loss训练。

当训练数据线性可分时，通过硬间隔最大化（hard margin maximization）学习一个线性的分类器，即线性可分支持向量机，又成为硬间隔支持向量机；
当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization）也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；
当训练数据线性不可分时，通过核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

K-means

K-means算法逻辑
K-means算法是一个实用的无监督聚类算法，其聚类逻辑依托欧式距离，当两个目标的距离越近，相似度越大。对于给定的样本集，按照样本之间的距离大小，将样本集划分为 K 个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
主要步骤：
1. 选择初始化的 k 个样本作为初始聚类中心 D = D1 , D2 , D3 , …, Dk 。
2. 针对数据集中每个样本 xi ，计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中。
3. 针对每个类别 Dj ，重新计算它的聚类中心 Dj 。（即属于该类的所有样本的质心）。
4. 重复上面2和3两步的操作，直到达到设定的中止条件（迭代次数、最小误差变化等）。

手撕K-means

import numpy as np
 
# 生成随机数据
np.random.seed(0)
X = np.random.rand(100, 2)
 
# 定义K值和迭代次数
K = 3
max_iterations = 100
 
# 随机初始化簇中心点
centers = X[np.random.choice(X.shape[0], K, replace=False)]
 
# 迭代更新簇中心点
for _ in range(max_iterations):
    # 计算每个数据点到每个簇中心点的欧氏距离
    distances = np.linalg.norm(X[:, np.newaxis, :] - centers, axis=2)
    
    # 分配每个数据点到最近的簇
    labels = np.argmin(distances, axis=1)
    
    # 更新簇中心点为每个簇的平均值
    new_centers = np.array([X[labels == k].mean(axis=0) for k in range(K)])
    
    # 如果簇中心点不再改变，结束迭代
    if np.all(centers == new_centers):
        break
    
    centers = new_centers

KNN

KNN算法逻辑
KNN是一种非参数有监督分类算法。K近邻（K-NN）算法计算不同数据特征值之间的距离进行分类。存在一个样本数据集合，也称作训练数据集，并且数据集中每个数据都存在标签，即我们知道每一个数据与所属分类的映射关系。接着输入没有标签的新数据后，在训练数据集中找到与该新数据最邻近的K个数据，然后提取这K个数据中占多数的标签作为新数据的标签（少数服从多数逻辑）。（训练可以使用KD树加速）
主要步骤：
1. 计算新数据与各个训练数据之间的距离。
2. 选取距离最小的K个点。
3. 确定前K个点所在类别的出现频率
4. 返回前K个点中出现频率最高的类别作为新数据的预测分类。

手撕KNN

import numpy as np
class KNNClassifier:
    def __init__(self,k=3):
        self.k = k
        self.x_train = None
        self.y_train = None
        
    def fit(self,x_train,y_train):
        self.x_train = x_train
        self.y_train = y_train
        return self
    
    def predict(self,x_predict):
        y_predict = [self._predict(x) for x in x_predict]
        return np.array(y_predict)
    
    def _predict(self,x):
        distances = [np.sqrt(np.sum((x_train - x)**2)) for x_train in self.x_train]
        nearest = np.argsort(distances)[:self.k]
        top_k_y = [self.y_train[index] for index in nearest]
        votes = np.bincount(top_k_y)
        return votes.argmax()

PCA

对原始样本进行中心化处理，即零均值化.
求出样本的协方差矩阵。
求解协方差矩阵的特征值和特征向量。
将特征值由大到小排列，取出前 k 个特征值对应的特征向量。
将 n 维样本映射到 k 维，实现降维处理。

其他

常见数据集划分方法

留出法（hold-out）直接将数据集划分为两个互斥的集合，其中一个集合作为训练集，另一个作为测试集。在训练集上训练出模型后，用测试集来评估其测试误差，作为对泛化误差的估计。

k折交叉验证（k-fold cross validation）通过分层抽样的方法，将数据集划分为k个大小相似的互斥子集。选择k-1个子集合并作为训练集，用于模型的训练，而剩下的一个子集则作为测试集，用于评估模型的性能。这个过程重复k次，每次选择不同的子集作为测试集，从而获得k组不同的训练/测试集组合。这种方式可以对模型进行k次独立的训练和测试，最终得到一个更加稳健和可靠的性能评估结果

自助法（boostrapping）通过采用有放回抽样的方法，我们每次从原始数据集D中随机选择一个样本，并将其复制到新的数据集D’中。这个过程重复进行m次，从而创建了一个包含$m$个样本的训练集D’。根据概率论的公式，这种有放回抽样的方式意味着每个样本在m次抽样中都不被选中的概率是(1-1/m)^m。当m趋向于无穷大时，这个概率的极限值为36.8%。因此，可以预期大约有36.8%的原始样本不会出现在新数据集D’中，这些未出现在D’中的样本可以用来作为测试集，以评估模型的性能。

判别式模型和生成式模型的区别

判别式模型
目标：直接学习输入数据 X 和标签 Y 之间的决策边界，即条件概率 P ( Y | X ) 。
任务：对未见数据X ，根据 P ( Y | X ) 可以求得标签 Y ，即可以直接判别出来未见数据的标签，主要用于分类和回归任务，关注如何区分不同类别。
例子：逻辑回归、支持向量机（SVM）、神经网络、随机森林等。

生成式模型
目标：学习输入数据 X 和标签 Y 的联合概率分布 P ( X , Y ) ，并通过它推导出条件概率 P ( Y | X ) 。
任务：不仅用于分类，还可以生成新的数据样本、建模数据的分布。
例子：扩散模型、高斯混合模型（GMM）、隐马尔可夫模型（HMM）、朴素贝叶斯、生成对抗网络（GAN）等。

基础信息论：熵，交叉熵，KL散度，JS散度，互信息

熵：衡量了一个概率分布的随机性程度，或者说它包含的信息量的大小。
公式:
对于离散型随机变量： $H(p)=E_p[-log(p(x))]=-\sum_{i=1}^n p_i log(p_i)$ ;

交叉熵：定义于两个概率分布之上，反映了它们之间的差异程度
公式： $H(p,q)=E_p[- log(q(x))]=-\sum_{x}p(x) log(q(x))$ ;
交叉熵不具有对称性，H(p,q) != H(q,p);

KL散度：也叫相对熵，用于度量两个分布之间的差异。
公式： $D_{KL}(p|q)=E_p[log\frac{p(x)}{q(x)}]=\sum_{x}p(x) ln \frac{p(x)}{q(x)}$ ;
与交叉熵的关系： $D_{KL}(p|q)=H(p,q)-H(p)$ ;

JS散度：KL散度是不对称的，会因为不同的顺序造成不一样的训练结果。
公式： $JS(P|Q)=\frac{1}{2}KL(P|\frac{P+Q}{2})+\frac{1}{2}KL(Q|\frac{P+Q}{2})$ ;

互信息：变量间相互依赖性的量度。
公式: $I(X,Y)=\sum\limits_{y\in Y}\sum\limits_{x\in X}p(x,y)log(\frac{p(x,y)}{p(x)p(y)})$ ;

数据类别不平衡怎么办？
1. 数据增强。
2. 对少数类别数据做过采样，多数类别数据做欠采样。
3. 损失函数的权重均衡。（不同类别的loss权重不一样，最佳参数需要手动调节）
4. 采集更多少数类别的数据。
5. Focal loss
什么是过拟合？解决办法有哪些？
过拟合：模型在训练集上拟合的很好，但是模型连噪声数据的特征都学习了，丧失了对测试集的泛化能力。
解决过拟合的方法：
1. 重新清洗数据，数据不纯会导致过拟合，此类情况需要重新清洗数据或重新选择数据。
2. 增加训练样本数量。使用更多的训练数据是解决过拟合最有效的手段。我们可以通过一定的规则来扩充训练数据，比如在图像分类问题上，可以通过图像的平移、旋转、缩放、加噪声等方式扩充数据;也可以用GAN网络来合成大量的新训练数据。
3. 降低模型复杂程度。适当降低模型复杂度可以避免模型拟合过多的噪声数据。在神经网络中减少网络层数、神经元个数等。
4. 加入正则化方法，增大正则项系数。给模型的参数加上一定的正则约束，比如将权值的大小加入到损失函数中。
5. 采用dropout方法，dropout方法就是在训练的时候让神经元以一定的概率失活。
6. 提前截断（early stopping），减少迭代次数。
7. 集成学习方法。集成学习是把多个模型集成在一起，来降低单一模型的过拟合风险，如Bagging方法。
常用正则化手段
1. L范数
2. Dropout
3. BatchNorm
4. Early Stopping
5. 数据增强