任何贪心算法——试图通过选择局部最佳的来最大化你的目标——可能会陷入局部最小值。

这些包括但不限于：

• 梯度下降优化类似于神经网络，它试图通过在最小化损失的方向上对权重进行小的更改来逐渐最小化损失函数。这还包括梯度提升等算法。您可以通过使用二阶导数 (Hessian) 或智能启发式来缓解此类问题。
• 一种前瞻算法，例如决策树，它在本地选择特征$x$ 和阈值 $t$ 谁的分裂 $x<t$最大化/最小化给定指标，如 gini 或熵（以及随后的随机森林）——如果决策树能够看到所有可能组合的最终影响，那么它可能会做出不同的选择，但这将是不可行的.
• 期望最大化（如 k-means 所使用的）也受到初始化的严重影响。

我的列表有点不精确。定义优化问题是否可能陷入局部最小值的是您试图最大化的函数。如果您使用梯度下降来解决 SVM 优化问题，那么您将始终收敛到全局最小值。比算法更重要的是优化问题的表面（在 SVM 中，目标是一个很好的二次曲面）。

另请注意，像随机森林这样的算法（当树的数量非常非常多时）变得几乎是确定性的，但它们仍然会陷入局部最小值。我指出这一点是因为有些人将陷入局部最小值的优化与随机算法混淆——他们认为他们可以通过多次运行算法来缓解局部最小值。但是该算法容易受到局部最小值的影响$\neq$该算法是随机的。例如，您永远不会通过多次运行决策树或随机森林来解决一个前瞻问题。对于像 k-means 这样的算法，运行几次确实是个好主意，因为大多数实现都是在幕后进行的。

对于基于树的算法，它取决于构建您使用的树的算法。如果你使用 CART，就像在 sklearn 中一样，CART 根据定义是一种贪心算法。出于这个原因，没有人期望在构建树时找到全局最优值。但是，局部最优也可以完成这项工作。这实际上适用于梯度提升和随机森林，因为它们是用树构建的。关于 SVM，有两种方法可以拟合 SVM：对偶问题和原始问题。两种方法都涉及求解二次优化问题，这些解决方案始终是全局最优的。