搜广推校招面经六十三
字节广告算法
一、学过Kmeans么？写一下损失函数，每个簇的中心点怎么选择，推导一下Kmeans的参数
不亏是字节，上来就是暴击。
- K-Means 通过最小化平方误差来寻找簇中心，使用欧几里得距离作为度量标准。
- 簇中心可以随机初始化，也可以通过Kmeans++的初始化方法，减少陷入局部最优解问题。并且通过计算簇内样本均值来更新。
1.1. K-Means 损失函数
K-Means 的目标是最小化簇内样本到簇中心的平方距离总和，损失函数（目标函数）定义如下：
J
=
∑
i
=
1
k
∑
x
j
∈
C
i
∥
x
j
−
μ
i
∥
2
J = sum_{i=1}^{k} sum_{x_j in C_i} | x_j - mu_i |^2
J=i=1∑kxj∈Ci∑∥xj−μi∥2
其中：
- k k k 是簇的个数
- C i C_i Ci 代表第 i i i 个簇
- x j x_j xj 是属于第 i i i 个簇的样本点
- μ i mu_i μi 是簇 C i C_i Ci 的中心（均值）
- ∥ x j − μ i ∥ 2 | x_j - mu_i |^2 ∥xj−μi∥2 代表欧几里得距离的平方
1.2. 簇中心的选择
- 随机初始化：随机选取 k k k 个数据点作为初始簇中心 μ 1 , μ 2 , . . . , μ k mu_1, mu_2, ..., mu_k μ1,μ2,...,μk。
- 迭代更新：
-
分配样本：根据当前簇中心，将每个样本 x j x_j xj 归入最近的簇 C i C_i Ci，即：
C i = { x j ∣ arg min i ∥ x j − μ i ∥ 2 } C_i = { x_j mid rgmin_{i} | x_j - mu_i |^2 } Ci={xj∣argimin∥xj−μi∥2} -
更新簇中心：计算每个簇的新中心，取簇内所有样本点的均值：
-
μ i = 1 ∣ C i ∣ ∑ x j ∈ C i x j mu_i = rac{1}{|C_i|} sum_{x_j in C_i} x_j μi=∣Ci∣1xj∈Ci∑xj
- 重复上述步骤，直到簇中心收敛或满足终止条件。
1.3. 参数推导
1.3.1 目标函数对簇中心 μ i mu_i μi 求导
目标函数为：
J
=
∑
i
=
1
k
∑
x
j
∈
C
i
∥
x
j
−
μ
i
∥
2
J = sum_{i=1}^{k} sum_{x_j in C_i} | x_j - mu_i |^2
J=i=1∑kxj∈Ci∑∥xj−μi∥2
对簇中心
μ
i
mu_i
μi 求偏导：
∂
J
∂
μ
i
=
∑
x
j
∈
C
i
2
(
μ
i
−
x
j
)
rac{partial J}{partial mu_i} = sum_{x_j in C_i} 2(mu_i - x_j)
∂μi∂J=xj∈Ci∑2(μi−xj)
令偏导数为 0：
∑
x
j
∈
C
i
2
(
μ
i
−
x
j
)
=
0
sum_{x_j in C_i} 2(mu_i - x_j) = 0
xj∈Ci∑2(μi−xj)=0
整理得：
μ
i
=
1
∣
C
i
∣
∑
x
j
∈
C
i
x
j
mu_i = rac{1}{|C_i|} sum_{x_j in C_i} x_j
μi=∣Ci∣1xj∈Ci∑xj
这表明，每个簇的中心是该簇中所有数据点的均值。
1.3.2 迭代收敛性
K-Means 在每次迭代中都会降低目标函数值 J J J，因此收敛性是保证的。但由于其是基于随机初始化的，可能会收敛到局部最优解，因此可采用 K-Means++ 进行优化，即：
- 选取一个数据点作为第一个簇中心。
- 依概率
p
p
p 选择新的簇中心：
p ( x ) = D ( x ) 2 ∑ D ( x ) 2 p(x) = rac{D(x)^2}{sum D(x)^2} p(x)=∑D(x)2D(x)2
其中 D ( x ) D(x) D(x) 是数据点到最近簇中心的距离。
K-Means++ 能有效减少初始中心的不稳定性，提高收敛效果。
1.4. 代码实现
见【搜广推校招面经二十三】
二、写一下逻辑回归的表达式，参数怎么推导
2.1. 逻辑回归的基本表达式
逻辑回归（Logistic Regression）用于二分类问题，其基本形式如下：
P
(
Y
=
1
∣
X
)
=
σ
(
W
T
X
+
b
)
P(Y=1 | X) = sigma(W^T X + b)
P(Y=1∣X)=σ(WTX+b)
其中：
- X X X 是输入特征向量，
- W W W 是权重向量，
- b b b 是偏置项，
- σ ( z ) sigma(z) σ(z) 是 sigmoid 函数，定义如下：
σ
(
z
)
=
1
1
+
e
−
z
sigma(z) = rac{1}{1 + e^{-z}}
σ(z)=1+e−z1
由于
σ
(
z
)
sigma(z)
σ(z) 的值范围在 (0,1) 之间，因此逻辑回归输出的是一个概率值，通常设定阈值（如 0.5）进行分类。
2.2. 似然函数与对数似然函数
给定一组训练数据
{
(
X
i
,
Y
i
)
}
i
=
1
n
{(X_i, Y_i)}_{i=1}^{n}
{(Xi,Yi)}i=1n，样本的联合概率为：
L
(
W
,
b
)
=
∏
i
=
1
n
P
(
Y
i
∣
X
i
)
=
∏
i
=
1
n
σ
(
W
T
X
i
+
b
)
Y
i
(
1
−
σ
(
W
T
X
i
+
b
)
)
(
1
−
Y
i
)
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)}
L(W,b)=i=1∏nP(Yi∣Xi)=i=1∏nσ(WTXi+b)Yi(1−σ(WTXi+b))(1−Yi)
取对数得到对数似然函数：
ℓ
(
W
,
b
)
=
∑
i
=
1
n
[
Y
i
log
σ
(
W
T
X
i
+
b
)
+
(
1
−
Y
i
)
log
(
1
−
σ
(
W
T
X
i
+
b
)
)
]
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))
ight]
ℓ(W,b)=i=1∑n[Yilogσ(WTXi+b)+(1−Yi)log(1−σ(WTXi+b))]
2.3. 梯度计算（参数推导）
对 W W W 求偏导：
利用链式法则，对数似然函数关于
W
W
W 的梯度为：
∂
ℓ
∂
W
=
∑
i
=
1
n
(
Y
i
−
σ
(
W
T
X
i
+
b
)
)
X
i
rac{partial ell}{partial W} = sum_{i=1}^{n} left( Y_i - sigma(W^T X_i + b)
ight) X_i
∂W∂ℓ=i=1∑n(Yi−σ(WTXi+b))Xi
对 b b b 求偏导：
∂ ℓ ∂ b = ∑ i = 1 n ( Y i − σ ( W T X i + b ) ) rac{partial ell}{partial b} = sum_{i=1}^{n} left( Y_i - sigma(W^T X_i + b) ight) ∂b∂ℓ=i=1∑n(Yi−σ(WTXi+b))
2.4. 参数更新（梯度下降）
利用梯度下降（Gradient Descent）更新参数：
W
←
W
+
α
∑
i
=
1
n
(
Y
i
−
σ
(
W
T
X
i
+
b
)
)
X
i
W leftarrow W + lpha sum_{i=1}^{n} (Y_i - sigma(W^T X_i + b)) X_i
W←W+αi=1∑n(Yi−σ(WTXi+b))Xi
b
←
b
+
α
∑
i
=
1
n
(
Y
i
−
σ
(
W
T
X
i
+
b
)
)
b leftarrow b + lpha sum_{i=1}^{n} (Y_i - sigma(W^T X_i + b))
b←b+αi=1∑n(Yi−σ(WTXi+b))
其中：
- α lpha α 为学习率（learning rate）。
若使用 随机梯度下降（SGD），则每次仅用一个样本更新：
W
←
W
+
α
(
Y
i
−
σ
(
W
T
X
i
+
b
)
)
X
i
b
←
b
+
α
(
Y
i
−
σ
(
W
T
X
i
+
b
)
)
W leftarrow W + lpha (Y_i - sigma(W^T X_i + b)) X_i b leftarrow b + lpha (Y_i - sigma(W^T X_i + b))
W←W+α(Yi−σ(WTXi+b))Xi b←b+α(Yi−σ(WTXi+b))
2.5. 代码实现
见【搜广推校招面经二十三】
三、L1、L2正则化公式，分别适用于什么场景、从数学角度讲一下两者区别
3.1. L1正则化（Lasso Regression）
L1 正则化是对模型的损失函数加上参数的 L1 范数（即绝对值之和）的惩罚项：
J
(
θ
)
=
L
(
θ
)
+
λ
∑
i
=
1
n
∣
θ
i
∣
J( heta) = L( heta) + lambda sum_{i=1}^{n} | heta_i|
J(θ)=L(θ)+λi=1∑n∣θi∣
适用场景
- 特征选择：L1 正则化会让某些特征的权重变为 0，从而起到特征筛选的作用，适用于高维稀疏数据。
- 稀疏模型：如果希望得到一个稀疏解（sparse solution），如在文本分类或基因数据分析中，L1 正则化是不错的选择。
3.2. L2 正则化（Ridge Regression）
L2 正则化是在损失函数中添加参数的 L2 范数（即平方和）的惩罚项：
J
(
θ
)
=
L
(
θ
)
+
λ
∑
i
=
1
n
θ
i
2
J( heta) = L( heta) + lambda sum_{i=1}^{n} heta_i^2
J(θ)=L(θ)+λi=1∑nθi2
适用场景
- 防止过拟合：L2 正则化不会使参数变为 0，而是会让所有参数趋向较小的值，从而降低模型的复杂度，减少过拟合的风险。
- 适用于相关性较高的特征：如果输入特征之间存在较高的相关性，L2 正则化比 L1 更稳定，因为它不会完全去掉某个特征，而是让所有特征的权重缩小。
3.3 数学区别
| 正则化类型 | 惩罚项 | 对参数的影响 | 计算梯度 |
|---|---|---|---|
| L1 正则化 | ∑ θ i sum heta_i ∑θi | 使部分权重变为 0，得到稀疏解 | 梯度不连续，更新时可能直接设为 0 |
| L2 正则化 | ∑ θ i 2 sum heta_i^2 ∑θi2 | 使权重变小，但不会完全变为 0 | 梯度连续，参数缩小但仍保留 |
具体来看：
-
L1 的梯度：
∂ J ∂ θ i = ∂ L ∂ θ i + λ ⋅ s i g n ( θ i ) rac{partial J}{partial heta_i} = rac{partial L}{partial heta_i} + lambda cdot sign( heta_i) ∂θi∂J=∂θi∂L+λ⋅sign(θi)
由于 sign ( θ i ) ext{sign}( heta_i) sign(θi) 只有三种取值（-1, 0, 1），导致 L1 正则化的梯度在 0 处不连续，因此在优化过程中部分参数可能被直接置为 0。 -
L2 的梯度：
∂ J ∂ θ i = ∂ L ∂ θ i + 2 λ θ i rac{partial J}{partial heta_i} = rac{partial L}{partial heta_i} + 2lambda heta_i ∂θi∂J=∂θi∂L+2λθ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
