搜广推校招面经二十

信息论角度：交叉熵是衡量两个概率分布之间的差异，描述了真实分布和预测分布之间的信息量差异。最大似然估计角度：交叉熵可以视为负对数似然损失，是通过最大化样本标签的预测概率来训练模型的损失函数。这两种角度是交叉熵的推导方法，其中最大似然估计角度更直接与模型训练过程相关，而信息论角度则提供了更深入的理论背景。

Y1n

10549人浏览 · 2025-02-19 01:02:34

Y1n · 2025-02-19 01:02:34 发布

字节-抖音推荐

一、42. 接雨水（hot100_双指针_困难）

朴素的做法是对于数组height中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组height的长度为n，该做法需要对每个下标位置使用O(n)的时间向两边扫描并得到最大高度，因此总时间复杂度是 $O(n^2)$ 。
使用动态规划
创建两个长度为n的数组leftMax和rightMax。对于0≤i<n，leftMax[i]表示下标i及其左边的位置中，height的最大高度，rightMax[i]表示下标i及其右边的位置中，height的最大高度。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
            
        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans

二、交叉熵推导，从两种角度

交叉熵（Cross-Entropy）是机器学习中常用的损失函数，尤其在分类问题中广泛应用。推导交叉熵的过程可以从两个不同的角度来理解：信息论角度和最大似然估计角度。

2.1. 信息论角度

交叉熵的定义源自信息论，它衡量的是一个概率分布与真实分布之间的差异。假设有两个概率分布 $p $ 和 $q$ ，其中 $p$ 是真实分布， $q$ 是预测分布，交叉熵 $H (p, q)$ 定义为：

$\sum_{i} p(x_i) \log q(x_i)$

$p(x_i)$ 是真实标签的概率分布，表示第 $i$ 类样本的真实概率。
$q(x_i)$ 是模型的预测概率分布，表示模型预测第 $i$ 类的概率。

在分类任务中，通常假设目标类别是离散的，因此每个样本属于某个类别的概率是 1，其它类别的概率是 0。假设有 $C$ 类，目标是学习模型的预测分布 $q$ 来最小化真实分布 $p$ 和预测分布 $q$ 之间的交叉熵。
对于多分类问题中的每个样本 ( x )，交叉熵损失可以表示为：

$\sum_{i=1}^{C} p(y_i) \log q(y_i)$

其中：

$p(y_i)$ 是真实标签 $y_i$ 的概率。对单个样本来说，如果 $y = j$ ，则 $p(y_j) = 1$ 其余 $p(y_i = 0)$ 。
$q(y_i)$ 是模型对类别 $y_i$ 的预测概率。

2.2. 最大似然估计角度

最大似然估计（MLE）是一种统计学方法，用于估计概率分布参数。假设我们有一个由 ( N ) 个样本组成的训练集 ( {x_1, x_2, \dots, x_N} )，每个样本 ( x_i ) 的标签 ( y_i ) 属于 ( C ) 个类别中的一个。

假设我们用 ( q(y | x_i) ) 来表示模型对样本 ( x_i ) 预测的类别 ( y ) 的概率。目标是最大化所有样本的似然函数，即：
$L(\theta) = \prod_{i=1}^{N} q(y_i | x_i)$
我们可以通过最大化对数似然函数来简化计算：
$\log L(\theta) = \sum_{i=1}^{N} \log q(y_i | x_i)$

为了优化模型参数 $\theta$ ，我们通常最大化对数似然函数。但由于分类任务中的目标是最小化损失，我们会对其取负数，得到负对数似然（Negative Log Likelihood, NLL）损失。对于每个样本 $x_i$ ，其对应的负对数似然损失为：
$\text{NLL}(x_i) = - \log q(y_i | x_i)$
因此，总的损失函数为：
$\sum_{i=1}^{N} \log q(y_i | x_i)$
这就是交叉熵的形式，它实际上是通过最大化数据的似然函数来优化模型的预测。交叉熵损失函数最小化了真实标签和模型预测标签之间的差异。

2.3. 总结

信息论角度：交叉熵是衡量两个概率分布之间的差异，描述了真实分布和预测分布之间的信息量差异。
最大似然估计角度：交叉熵可以视为负对数似然损失，是通过最大化样本标签的预测概率来训练模型的损失函数。
这两种角度是交叉熵的推导方法，其中最大似然估计角度更直接与模型训练过程相关，而信息论角度则提供了更深入的理论背景。

三、bagging和boosting的区别

见【搜广推校招面经十、十一】

3.1. Bagging（Bootstrap Aggregating）

基本思想：通过对训练数据进行有放回的抽样，创建多个训练集。每个训练集用于训练一个独立的模型，然后将这些模型的预测结果进行平均（回归问题）或投票（分类问题）。
目标：减少方差，防止过拟合，尤其适用于高方差的模型（如决策树）。
方法：
- 通过自助采样法（Bootstrap）生成多个子数据集。
- 每个模型在独立的子数据集上训练，并且每个模型对测试数据做出独立预测。
- 最终的预测是通过对所有模型预测结果的平均（回归）或投票（分类）来得到。
示例算法：随机森林（Random Forest）是典型的 Bagging 方法。

3.2. Boosting

基本思想：通过将多个弱学习器（通常是浅决策树）顺序地训练成一个强学习器。每个新的模型都专注于纠正前一个模型的错误。
目标：减少偏差，增强模型的预测能力，尤其适用于偏差较大的模型。
方法：
- 模型是顺序训练的，后续的模型根据前一模型的错误进行调整。
- 每个模型的权重取决于其对训练集的贡献（正确预测样本的权重较低，错误预测样本的权重较高）。
- 最终预测是基于所有模型的加权预测结果。
示例算法：AdaBoost、Gradient Boosting（包括 XGBoost、LightGBM 等）。

3.3. 主要区别

特征	Bagging	Boosting
训练方式	并行训练多个模型，训练过程相互独立。	顺序训练，每个新模型依赖于前一个模型的表现。
主要目标	降低方差，防止过拟合，适用于高方差模型。	降低偏差，提高模型预测能力，适用于高偏差模型。
模型组合方式	通过平均或投票对模型结果进行结合。	通过加权平均或加权投票对模型结果进行结合。