搜广推校招面经六十三

字节广告算法

一、学过Kmeans么？写一下损失函数，每个簇的中心点怎么选择，推导一下Kmeans的参数

不亏是字节，上来就是暴击。

• K-Means 通过最小化平方误差来寻找簇中心，使用欧几里得距离作为度量标准。
• 簇中心可以随机初始化，也可以通过Kmeans++的初始化方法，减少陷入局部最优解问题。并且通过计算簇内样本均值来更新。

1.1. K-Means 损失函数

K-Means 的目标是最小化簇内样本到簇中心的平方距离总和，损失函数（目标函数）定义如下：
$$J=\sum _{i=1}^k\sum _{x_j\in C_i}\Vert x_j-{\mu }_i{\Vert }^2$$

其中：

• $k$ 是簇的个数
• $C_i$ 代表第 $i$ 个簇
• $x_j$ 是属于第 $i$ 个簇的样本点
• ${\mu }_i$ 是簇 $C_i$ 的中心（均值）
• $\Vert x_j-{\mu }_i{\Vert }^2$ 代表欧几里得距离的平方

1.2. 簇中心的选择

1. 随机初始化：随机选取 $k$ 个数据点作为初始簇中心 ${\mu }_1,{\mu }_2,...,{\mu }_k$。
2. 迭代更新：

   • 分配样本：根据当前簇中心，将每个样本 $x_j$ 归入最近的簇 $C_i$，即：
     C i = { x j ∣ arg ⁡ min ⁡ i ∥ x j − μ i ∥ 2 } C_i = \{ x_j \mid \arg\min_{i} \| x_j - \mu_i \|^2 \} Ci​={xj​∣argimin​∥xj​−μi​∥2}

   • 更新簇中心：计算每个簇的新中心，取簇内所有样本点的均值：

$${\mu }_i=\frac{1}{|C_i|}\sum _{x_j\in C_i}{x}_j$$

• 重复上述步骤，直到簇中心收敛或满足终止条件。

1.3. 参数推导

1.3.1 目标函数对簇中心 ${\mu }_i$ 求导

目标函数为：
$$J=\sum _{i=1}^k\sum _{x_j\in C_i}\Vert x_j-{\mu }_i{\Vert }^2$$

对簇中心 ${\mu }_i$ 求偏导：
$$\frac{\partial J}{\partial {\mu }_i}=\sum _{x_j\in C_i}2({\mu }_i-x_j)$$

令偏导数为 0：
$$\sum _{x_j\in C_i}2({\mu }_i-x_j)=0$$

整理得：
$${\mu }_i=\frac{1}{|C_i|}\sum _{x_j\in C_i}{x}_j$$
这表明，每个簇的中心是该簇中所有数据点的均值。

1.3.2 迭代收敛性

K-Means 在每次迭代中都会降低目标函数值 $J$，因此收敛性是保证的。但由于其是基于随机初始化的，可能会收敛到局部最优解，因此可采用 K-Means++ 进行优化，即：

1. 选取一个数据点作为第一个簇中心。
2. 依概率 $p$ 选择新的簇中心：
   $$p(x)=\frac{D(x{)}^2}{\sum D(x{)}^2}$$
   其中 $D(x)$ 是数据点到最近簇中心的距离。
   K-Means++ 能有效减少初始中心的不稳定性，提高收敛效果。

1.4. 代码实现

见【搜广推校招面经二十三】

二、写一下逻辑回归的表达式，参数怎么推导

2.1. 逻辑回归的基本表达式

逻辑回归（Logistic Regression）用于二分类问题，其基本形式如下：
$$P(Y=1|X)=\sigma (W^{T}X+b)$$
其中：

• $X$ 是输入特征向量，
• $W$ 是权重向量，
• $b$ 是偏置项，
• $\sigma (z)$ 是 sigmoid 函数，定义如下：

$$\sigma (z)=\frac{1}{1+e^{-z}}$$
由于 $\sigma (z)$ 的值范围在 (0,1) 之间，因此逻辑回归输出的是一个概率值，通常设定阈值（如 0.5）进行分类。

2.2. 似然函数与对数似然函数

给定一组训练数据 $\{(X_i,Y_i){\}}_{i=1}^n$，样本的联合概率为：
$$L(W,b)=\prod _{i=1}^{n}P(Y_i|X_i)=\prod _{i=1}^n\sigma (W^T{X}_i+b{)}^{Y_i}(1-\sigma (W^T{X}_i+b){)}^{(1-Y_i)}$$
取对数得到对数似然函数：
$$\ell (W,b)=\sum _{i=1}^n\left[Y_i\log \sigma (W^T{X}_i+b)+(1-Y_i)\log (1-\sigma (W^T{X}_i+b))\right]$$

2.3. 梯度计算（参数推导）

对 $W$ 求偏导：

利用链式法则，对数似然函数关于 $W$ 的梯度为：
$$\frac{\partial \ell }{\partial W}=\sum _{i=1}^n\left(Y_i-\sigma (W^T{X}_i+b)\right)X_i$$

对 $b$ 求偏导：

$$\frac{\partial \ell }{\partial b}=\sum _{i=1}^n\left(Y_i-\sigma (W^T{X}_i+b)\right)$$

2.4. 参数更新（梯度下降）

利用梯度下降（Gradient Descent）更新参数：
$$W\leftarrow W+\alpha \sum _{i=1}^n(Y_i-\sigma (W^T{X}_i+b))X_i$$

$$b\leftarrow b+\alpha \sum _{i=1}^n(Y_i-\sigma (W^T{X}_i+b))$$
其中：

• $\alpha$ 为学习率（learning rate）。

若使用 随机梯度下降（SGD），则每次仅用一个样本更新：
$$\begin{gathered} W\leftarrow W+\alpha (Y_i-\sigma (W^T{X}_i+b))X_i \\ b\leftarrow b+\alpha (Y_i-\sigma (W^T{X}_i+b)) \end{gathered}$$

2.5. 代码实现

见【搜广推校招面经二十三】

三、L1、L2正则化公式，分别适用于什么场景、从数学角度讲一下两者区别

3.1. L1正则化（Lasso Regression）

L1 正则化是对模型的损失函数加上参数的 L1 范数（即绝对值之和）的惩罚项：
$$J(\theta )=L(\theta )+\lambda \sum _{i=1}^n|{\theta }_i|$$

适用场景

• 特征选择：L1 正则化会让某些特征的权重变为 0，从而起到特征筛选的作用，适用于高维稀疏数据。
• 稀疏模型：如果希望得到一个稀疏解（sparse solution），如在文本分类或基因数据分析中，L1 正则化是不错的选择。

3.2. L2 正则化（Ridge Regression）

L2 正则化是在损失函数中添加参数的 L2 范数（即平方和）的惩罚项：
$$J(\theta )=L(\theta )+\lambda \sum _{i=1}^n{\theta }_i^2$$

适用场景

• 防止过拟合：L2 正则化不会使参数变为 0，而是会让所有参数趋向较小的值，从而降低模型的复杂度，减少过拟合的风险。
• 适用于相关性较高的特征：如果输入特征之间存在较高的相关性，L2 正则化比 L1 更稳定，因为它不会完全去掉某个特征，而是让所有特征的权重缩小。

3.3 数学区别

具体来看：

• L1 的梯度：
  $$\frac{\partial J}{\partial {\theta }_i}=\frac{\partial L}{\partial {\theta }_i}+\lambda \cdot sign({\theta }_i)$$
  由于 $\text{sign}({\theta }_i)$ 只有三种取值（-1, 0, 1），导致 L1 正则化的梯度在 0 处不连续，因此在优化过程中部分参数可能被直接置为 0。

• L2 的梯度：
  $$\frac{\partial J}{\partial {\theta }_i}=\frac{\partial L}{\partial {\theta }_i}+2\lambda {\theta }_i$$
  L2 正则化会使参数逐步缩小，但不会变为 0。

3.4. 总结

• L1 正则化 适用于 特征选择，会让部分参数变为 0，从而得到稀疏模型。
• L2 正则化 适用于 防止过拟合，不会让参数变 0，而是让它们趋于较小的值，提高模型的泛化能力。
• 在深度学习中，L2（权重衰减）更常用，而在稀疏特征数据中，L1 更合适。

四、39. 组合总和（力扣hot100_回溯）

• 思路：字节考的题还是很难得，从八股都看得出来。算法题也是直接来也给回溯。
• 代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            if i == len(candidates) or left < 0:
                return

            # 不选
            dfs(i + 1, left)

            # 选
            path.append(candidates[i])
            dfs(i, left - candidates[i])
            path.pop()  # 恢复现场

        dfs(0, target)
        return ans