机器算法验证 - 您如何从数学上证明，在以正负标记的正方形排列的训练集中，boosting 不可能有零误差？ - 吾爱随笔录

机器算法验证机器学习数理统计

2022-03-13 17:25:49

我有以下数据：

在此处输入图像描述

假设我们希望仅使用一组水平和垂直决策树桩来完美分离这些点。也许使用 Boosting 或 Adaboost，但重点是任何具有坐标加权树桩的集合。

直观地“显而易见”的是，不能仅使用树桩来分离这个特定的数据集。但是，我无法用严格的数学证明来说服自己。如何严格证明这样的主张？

我想知道，在树桩集合开始无法完美分离数据之前，我们是否还需要对点数进行概括。这是什么时候发生的，它的证据是什么？

1个回答

在这个数据集上，树桩可以做四件重要的事情：

所以你最终学习的函数可以是其中每个是。

\hat{y} (x) = \sum_{i = 1}^{n} f_{i} (x),

$\hat y(x) = \sum_{i=1}^n f_i(x),$

f

$f$

s_{j}

$s_j$

现在，请注意，该总和中的每个副本都会抵消的副本，因为它们是相反的，对于和也是如此。所以实际上是一个整数组合。 $s_1$ $s_2$ $s_3$ $s_4$ $\hat y$ $\hat y(x) = a\,s_1(x) + b\,s_3(x)$

但是当您从上到下移动时，该表达式的前半部分不会改变，而后半部分总是以相同的量变化（）。所以我们知道的输出要么总是随着数据点从上到下移动而增加（如果），或者总是减少（如果）。 $b$ $\hat y$ $b < 0$ $b > 0$

因此，没有任何可能的增强树桩总和可以完美地分类数据集，QED。

（编辑：我使证明更容易理解。前一个是正确的，但没有提供太多的直觉，我想出了一种方法来做直观的事情，而不需要太多的案例分析。）

其它你可能感兴趣的问题