抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

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

算法岗八股文

发布于：2024年9月24日

损失函数

  • 常用损失函数

    均方误差（MSE,L2）:L=(y−y^)2L=(y-\hat{y})^2 （回归任务常用，隐含的预设是数据误差符合高斯分布）
    绝对误差（MAE,L1）:L=∣y−y^∣L=|y-\hat{y}|
    二值交叉熵（BCE）：L=1N∑i−[yi∗log(pi)+(1−yi)∗log(1−pi)]L=\frac{1}{N}\sum_i -[ y_i* log(p_i)+(1-y_i)*log(1-p_i)];
    交叉熵（CE）：L=1N∑i∑c=1M−yiclog(pic)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:

  • 优点：
  1. 对大误差敏感：MSE通过平方项放大了大误差的影响，适用于需要严格控制大误差的应用
  2. 数学性质好：MSE的二次损失函数具有良好的数学性质，便于推导和计算，特别是在最小二乘法中应用广泛
  • 缺点：
  1. 异常值影响大：由于对大误差的敏感性，异常值会显著影响MSE，使得模型对异常值过度关注。
  2. 解释性差：MSE的单位是原始数据单位的平方，不直观，需要转化为RMSE来辅助解释。
  • L1和L2正则化的区别？它们都能防止过拟合吗？

    L1正则化：通过在损失函数中添加权重的L1范数（权重向量的绝对值之和）作为惩罚项。这种正则化倾向于产生稀疏权重矩阵，即将一些权重推向零，从而实现特征选择的效果。L1正则化有助于在众多特征中选择最重要的特征，减少模型的复杂度，并且提高模型的泛化能力。L1正则化的优化是非凸的，这可能导致局部最优解，但它的稀疏性使得模型更易于理解和解释。（更适合于特征选择）

L2正则化：L2正则化会使权重值变得较小，但不会直接导致权重稀疏，因此不具有特征选择的作用。L2正则化有助于控制模型的复杂度，防止过拟合，同时保持模型的平滑性。它对离群值更加稳健。L2正则化的优化是凸的，这意味着它总是能够找到全局最优解。（更适合保持模型参数的平滑性）

  • 交叉熵伪代码

    1
    2
    3
    4
    5
    6
    7
    8
    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隐含的是数据误差符合高斯分布。

评估指标

  • 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曲线方法：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    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为负样本数。（正样本这里有个特殊情况在于当正负样本概率相等时，可能排在前面也可能在后面，如果单纯将正样本排在前面或者后面计算，计算结果与前面的会有偏差。可以将两者样本序号取平均）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 时间复杂度为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乘以该类的比例之后相加。

Logistic Regression

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

其使用一个参数化函数计算给定输入变量的输出概率。

g(z)=11+e−zg(z)=\frac{1}{1+e^{-z}}，z是输入变量的线性组合，可以表示为z=b+w1x1+w2x2+...+wnxnz=b+w_1x_1+w_2x_2+...+w_nx_n

其训练的损失函数为最大化对数似然函数，这里即BCE。

J(w)=−1n∑yilog g(zi)+(1−yi)log(1−g(zi))J(w) = -\frac{1}{n}\sum{y_i log\ g(z_i)+(1-y_i)log(1-g(z_i))}

训练完成后，我们可以使用模型来预测新的样本的类别标签。预测类别标签的方法是，将新样本的特征向量代入 sigmoid 函数，计算输出概率，如果概率大于0.5，则预测为正例，否则预测为负例。

Python实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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)=Ep[−log(p(x))]=−∑i=1npilog(pi)H(p)=E_p[-log(p(x))]=-\sum_{i=1}^n p_i log(p_i);

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

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

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

互信息：变量间相互依赖性的量度。
公式:I(X,Y)=∑y∈Y∑x∈Xp(x,y)log(p(x,y)p(x)p(y))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. 数据增强

更新于：2024年10月17日

算法岗

八股文