抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）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可能会偏向于数值较大的类别。

  • 如何选择损失函数？

    需要出于对数据分布的假设，不同的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曲线，ROC, AUC

    P-R曲线：横轴是Recall，纵轴是Precision。
    ROC曲线：横轴是FPR=FP/N，纵轴是TPR=TP/N。
    AUC(Area Under Curve)：ROC曲线下的面积大小，AUC越大，说明分类器越可能把真正的正样本排在前面，分类性能越好。

  • 解释AUC的定义，它解决了什么问题，优缺点是什么，工业界如何计算AUC？

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

    • 衡量排序能力，适合排序类任务。
    • 对正负样本均衡不敏感，在样本不均衡情况下也能够合理评估。
    • 不需要手动设置阈值，是一种整体上的衡量方法。

    然而，AUC也有一些缺点：

    • 忽略了预测的概率值和模型的拟合程度。
    • 反应信息较为笼统，无法反映召回率、精确率等实际业务关心指标。
    • 没有给出模型误差的空间分布信息，只关心正负样本之间的排序，并不关心正负样本内部的排序，难以衡量样本对于实际程度的刻画能力。

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
    def knn_code(loc, k=5, order=2 ):  # k order是超参
        # print(order)
        diff_loc = X - loc
        dis_loc = np.linalg.norm(diff_loc, ord=order, axis=1) # 没有axis得到一个数，矩阵的泛数。axis=0，得到两个数
        knn = y[dis_loc.argsort()[:k]]
        counts = np.bincount(knn)
        return np.argmax(counts)

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年9月24日

算法岗

八股文