SAMME算法

SAMME（Stagewise Additive Modeling using a Multiclass Exponential loss function）是对Adaboost的一种扩展，用于处理多分类问题。Adaboost本身主要用于二分类问题，而SAMME通过调整弱分类器的权重计算和最终的分类组合方式，使得它可以应用于多类别任务。

SAMME算法由 Zhu 等人在 2009 年提出，它将 Adaboost 的二分类框架扩展到多分类的情境，目标是最小化多分类指数损失函数。

---

SAMME算法的核心思想

与 Adaboost 类似，SAMME也通过集成多个弱学习器（弱分类器）构建强学习器。SAMME 的主要特点在于：

1. 扩展到多分类问题：
   • 通过修改弱分类器的权重计算公式，使其适应多分类的场景。
2. 多分类的加权投票机制：
   • 每个弱分类器的输出被赋予一个权重，最终的强分类器通过这些弱分类器的加权投票决定最终类别。

SAMME使用的弱学习器可以是任何能够处理多分类问题的模型（如决策树）。

---

SAMME算法的步骤

假设我们有一个多分类数据集：
D={(x1,y1),(x2,y2),…,(xn,yn)},yi∈{1,2,…,K} \mathcal{D} = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}, \quad y_i \in \{1, 2, \dots, K\} D={(x1​,y1​),(x2​,y2​),…,(xn​,yn​)},yi​∈{1,2,…,K}
其中 $K$ 是类别的数量。

SAMME的训练过程如下：

1. 初始化样本权重：

与Adaboost相同，初始时每个样本的权重是相等的：
$$D_1(i)=\frac{1}{n},i=1,2,\dots ,n$$

2. 迭代训练弱分类器：

对于 $t=1,2,\dots ,T$（总共 $T$ 轮迭代）：

1. 训练弱分类器：

   • 在样本权重分布 $D_t$ 下，训练弱分类器 $h_t(x)$，输出类别预测 ht(x)∈{1,2,…,K}h_t(x) \in \{1, 2, \dots, K\}ht​(x)∈{1,2,…,K}。

2. 计算加权错误率：

   • 计算弱分类器的加权错误率 ${ϵ}_t$：
     $${ϵ}_t=\sum _{i=1}^n{D}_t(i)\cdot \mathbb{I}(h_t(x_i)\ne y_i)$$
     其中 $\mathbb{I}(\cdot )$ 是指示函数，若分类错误则为 1，否则为 0。

3. 计算弱分类器权重：

   • SAMME 中弱分类器的权重 ${\alpha }_t$ 的计算公式为：
     $${\alpha }_t=\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)+\ln (K-1)$$
     这一公式相比 Adaboost，多了 $\ln (K-1)$ 的修正项，它反映了多分类任务中类别数量 $K$ 对权重的影响。

4. 更新样本权重分布：

   • 样本权重更新公式为：
     $$D_{t+1}(i)=\frac{D_t(i)\cdot \exp \left(-{\alpha }_t\cdot \mathbb{I}(h_t(x_i)=y_i)\right)}{Z_t}$$
     其中 $Z_t$ 是归一化因子：
     $$Z_t=\sum _{i=1}^n{D}_t(i)\cdot \exp \left(-{\alpha }_t\cdot \mathbb{I}(h_t(x_i)=y_i)\right)$$
     • 若 $h_t(x_i)=y_i$（分类正确），则样本权重减少。
     • 若 $h_t(x_i)\ne y_i$（分类错误），则样本权重增加。

3. 构建强分类器：

最终的强分类器 $H(x)$ 是所有弱分类器的加权组合，定义为：
H(x)=arg⁡max⁡k∈{1,2,…,K}∑t=1Tαt⋅I(ht(x)=k) H(x) = \arg\max_{k \in \{1, 2, \dots, K\}} \sum_{t=1}^T \alpha_t \cdot \mathbb{I}(h_t(x) = k) H(x)=argk∈{1,2,…,K}max​t=1∑T​αt​⋅I(ht​(x)=k)
即，对于每个类别 $k$，计算所有弱分类器中支持 $k$ 类别的权重总和，选择权重总和最大的类别作为最终预测结果。

---

SAMME算法的关键点

1. 权重修正项 $\ln (K-1)$：

   • Adaboost假设二分类问题，因此无需考虑类别数量的影响。
   • SAMME引入了 $\ln (K-1)$ 的修正项，使得权重计算能够更好地适应多分类任务。

2. 加权投票：

   • SAMME将所有弱分类器的预测结果进行加权投票，结合每个弱分类器的权重 ${\alpha }_t$ 来决定最终分类结果。

3. 指数损失函数：

   • SAMME的优化目标是最小化多分类指数损失函数：
     $$\mathcal{L}=\sum _{i=1}^n\exp \left(-\sum _{t=1}^T{\alpha }_t\cdot \mathbb{I}(h_t(x_i)=y_i)\right)$$

---

SAMME和Adaboost的对比

特性	Adaboost	SAMME
任务类型	二分类	多分类
弱分类器权重公式	${\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$	${\alpha }_t=\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)+\ln (K-1)$
强分类器组合方式	加权投票	加权投票
权重修正项	无	$\ln (K-1)$

---

SAMME的优缺点

优点：

1. 扩展性强：
   • SAMME能够适应多分类任务，而不需要将其转化为多个二分类任务（如One-vs-One或One-vs-Rest）。
2. 自适应性强：
   • 与Adaboost类似，SAMME会自适应地调整样本权重，关注难分类的样本。
3. 弱分类器灵活：
   • SAMME对弱分类器没有特殊要求，可以结合各种能够处理多分类问题的模型。

缺点：

1. 计算复杂度高：
   • 多分类任务下，训练多个弱分类器和调整样本权重的计算开销较大。
2. 对噪声敏感：
   • 与Adaboost类似，SAMME对噪声样本较为敏感，容易过度关注异常值。
3. 依赖弱分类器性能：
   • 弱分类器的性能需要优于随机猜测，否则算法无法正常工作。

---

SAMME的变体：SAMME.R

SAMME.R 是对 SAMME 的改进，能够进一步提升多分类性能：

1. 连续概率输出：
   • SAMME.R 要求弱分类器输出类别的预测概率 $P(y=k|x)$，而不仅是一个单一的类别预测结果。
2. 权重计算公式：
   • 弱分类器的权重由类别的预测概率直接计算，目标是进一步逼近真实概率分布。

SAMME.R 的表现通常优于 SAMME，尤其在弱分类器能够输出概率的情况下。

示例

假设我们有一个三分类问题，数据集如下：

样本	特征 $x$	标签 $y$
1	1	A
2	2	A
3	3	B
4	4	B
5	5	C
6	6	C

我们将使用 SAMME 算法，通过迭代地训练弱分类器（在本例中，我们选择简单的决策桩作为弱分类器）来构建一个强分类器。假设我们进行 2 轮迭代。

SAMME算法步骤

1. 初始化样本权重

   初始时，每个样本的权重相等：
   $$w_i^{(1)}=\frac{1}{6}\approx 0.1667\text{for }i=1,2,\dots ,6$$

2. 迭代训练弱分类器（假设迭代次数为2）

第1轮迭代

a. 选择最佳弱分类器

我们选择一个简单的决策桩，根据特征 $x$ 的阈值进行分类。假设我们选择阈值 $\theta =3.5$，分类规则如下：

$$h_1(x)=\{\begin{array}{ll}A& \text{如果 }x\le 3.5\\ B& \text{如果 }3.5<x\le 5.5\\ C& \text{如果 }x>5.5\end{array}$$

b. 计算加权误差

SAMME 的加权误差定义为：

$${ϵ}_t=\frac{{\sum }_{i=1}^N{w}_i^{(t)}\cdot \mathbb{I}(h_t(x_i)\ne y_i)}{{\sum }_{i=1}^N{w}_i^{(t)}}$$

对于第1轮，计算每个样本的分类结果与真实标签的对比：

样本	$x$	$y$	$h_1(x)$	错误?	$w_i^{(1)}\cdot \mathbb{I}$
1	1	A	A	否	0
2	2	A	A	否	0
3	3	B	A	是	0.1667
4	4	B	B	否	0
5	5	C	B	是	0.1667
6	6	C	C	否	0

加权误差：
$${ϵ}_1=0.1667+0.1667=0.3334$$

c. 计算分类器权重 ${\alpha }_1$

SAMME 中分类器权重的计算公式为：

$${\alpha }_t=\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)+\ln (K-1)$$

其中 $K$ 是类别数，这里 $K=3$。

计算：
$${\alpha }_1=\ln \left(\frac{1-0.3334}{0.3334}\right)+\ln (2)=\ln (2)+\ln (2)=2\ln (2)\approx 1.3863$$

d. 更新样本权重

样本权重更新公式为：

$$w_i^{(t+1)}=w_i^{(t)}\cdot \exp \left({\alpha }_t\cdot \mathbb{I}(h_t(x_i)\ne y_i)\right)$$

具体计算：

样本	$y_i$	$h_1(x_i)$	错误?	$\mathbb{I}$	$w_i^{(1)}\cdot \exp ({\alpha }_1\cdot \mathbb{I})$
1	A	A	否	0	$0.1667\times e^0=0.1667$
2	A	A	否	0	$0.1667\times e^0=0.1667$
3	B	A	是	1	$0.1667\times e^{1.3863}\approx 0.1667\times 4=0.6668$
4	B	B	否	0	$0.1667\times e^0=0.1667$
5	C	B	是	1	$0.1667\times e^{1.3863}\approx 0.6668$
6	C	C	否	0	$0.1667\times e^0=0.1667$

归一化权重

计算总和 $Z_1$：
$$Z_1=0.1667+0.1667+0.6668+0.1667+0.6668+0.1667=2.3336$$

归一化后的权重 $w_i^{(2)}$：

$$w_i^{(2)}=\frac{w_i^{(2)}}{Z_1}$$

样本	$w_i^{(2)}$
1	$\frac{0.1667}{2.3336}\approx 0.0714$
2	$\frac{0.1667}{2.3336}\approx 0.0714$
3	$\frac{0.6668}{2.3336}\approx 0.2857$
4	$\frac{0.1667}{2.3336}\approx 0.0714$
5	$\frac{0.6668}{2.3336}\approx 0.2857$
6	$\frac{0.1667}{2.3336}\approx 0.0714$

第2轮迭代

a. 选择最佳弱分类器

基于更新后的权重，我们选择另一个决策桩。假设这次我们选择阈值 $\theta =4.5$，分类规则如下：

$$h_2(x)=\{\begin{array}{ll}A& \text{如果 }x\le 2.5\\ B& \text{如果 }2.5<x\le 4.5\\ C& \text{如果 }x>4.5\end{array}$$

b. 计算加权误差

计算每个样本的分类结果与真实标签的对比：

样本	$x$	$y$	$h_2(x)$	错误?	$w_i^{(2)}\cdot \mathbb{I}$
1	1	A	A	否	0
2	2	A	A	否	0
3	3	B	B	否	0
4	4	B	B	否	0
5	5	C	C	否	0
6	6	C	C	否	0

加权误差：
$${ϵ}_2=0$$

注意：在实际应用中，若 (\epsilon_t = 0)，意味着当前分类器已经完美分类所有样本，此时 SAMME 会提前终止迭代，并将当前分类器作为最终强分类器。但为了完整演示，我们假设 ${ϵ}_2\ne 0$ 并重新选择一个弱分类器。

调整弱分类器选择

假设我们选择阈值 $\theta =3.5$ ，即与第1轮相同的分类器，这样：

$$h_2(x)=\{\begin{array}{ll}A& \text{如果 }x\le 3.5\\ B& \text{如果 }3.5<x\le 5.5\\ C& \text{如果 }x>5.5\end{array}$$

重新计算误差：

样本	$x$	$y$	$h_2(x)$	错误?	$w_i^{(2)}\cdot \mathbb{I}$
1	1	A	A	否	0
2	2	A	A	否	0
3	3	B	A	是	0.2857
4	4	B	B	否	0
5	5	C	B	是	0.2857
6	6	C	C	否	0

加权误差：
$${ϵ}_2=0.2857+0.2857=0.5714$$

由于 (\epsilon_2 > \frac{K - 1}{K} = \frac{2}{3} \approx 0.6667)，分类器的错误率在允许范围内（即 (\epsilon_t < 1 - \frac{1}{K})），所以继续计算。

c. 计算分类器权重 ${\alpha }_2$

$${\alpha }_t=\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)+\ln (K-1)$$

代入：
$${\alpha }_2=\ln \left(\frac{1-0.5714}{0.5714}\right)+\ln (2)=\ln \left(\frac{0.4286}{0.5714}\right)+\ln (2)\approx \ln (0.75)+0.6931\approx -0.2877+0.6931=0.4054$$

d. 更新样本权重

样本权重更新公式为：

$$w_i^{(t+1)}=w_i^{(t)}\cdot \exp \left({\alpha }_t\cdot \mathbb{I}(h_t(x_i)\ne y_i)\right)$$

具体计算：

样本	$y_i$	$h_2(x_i)$	错误?	$\mathbb{I}$	$w_i^{(2)}\times \exp ({\alpha }_2\cdot \mathbb{I})$
1	A	A	否	0	$0.0714\times e^0=0.0714$
2	A	A	否	0	$0.0714\times e^0=0.0714$
3	B	A	是	1	$0.2857\times e^{0.4054}\approx 0.2857\times 1.5=0.4286$
4	B	B	否	0	$0.0714\times e^0=0.0714$
5	C	B	是	1	$0.2857\times e^{0.4054}\approx 0.4286$
6	C	C	否	0	$0.0714\times e^0=0.0714$

归一化权重

计算总和 $Z_2$：
$$Z_2=0.0714+0.0714+0.4286+0.0714+0.4286+0.0714=1.1428$$

归一化后的权重 $w_i^{(3)}$：

$$w_i^{(3)}=\frac{w_i^{(3)}}{Z_2}$$

样本	$w_i^{(3)}$
1	$\frac{0.0714}{1.1428}\approx 0.0625$
2	$\frac{0.0714}{1.1428}\approx 0.0625$
3	$\frac{0.4286}{1.1428}\approx 0.3750$
4	$\frac{0.0714}{1.1428}\approx 0.0625$
5	$\frac{0.4286}{1.1428}\approx 0.3750$
6	$\frac{0.0714}{1.1428}\approx 0.0625$

强分类器构建

经过2轮迭代，我们得到了两个弱分类器 $h_1$ 和 $h_2$ 及其权重 ${\alpha }_1$ 和 ${\alpha }_2$。

最终强分类器公式：

H(x)=arg⁡max⁡c∈{A,B,C}(∑t=1Tαt⋅I(ht(x)=c)) H(x) = \arg\max_{c \in \{A, B, C\}} \left( \sum_{t=1}^T \alpha_t \cdot \mathbb{I}(h_t(x) = c) \right) H(x)=argc∈{A,B,C}max​(t=1∑T​αt​⋅I(ht​(x)=c))

具体来说，对于每个类别 $c$，计算所有弱分类器预测为 $c$ 时的 ${\alpha }_t$ 之和，选择总和最大的类别作为最终预测。

例如，对于一个新样本 $x$：

假设 $x=3$：

• $h_1(3)=A$
• $h_2(3)=A$

计算：

• 类别 A 的得分：${\alpha }_1+{\alpha }_2=1.3863+0.4054=1.7917$
• 类别 B 的得分：0
• 类别 C 的得分：0

最终预测：A

总结

通过上述步骤，我们手动推导了 SAMME 算法的过程，包括：

1. 初始化样本权重：所有样本初始权重相等。
2. 迭代训练弱分类器：
   • 选择最佳弱分类器（决策桩）。
   • 计算加权误差。
   • 计算分类器权重 ${\alpha }_t$。
   • 更新并归一化样本权重。
3. 构建最终强分类器：基于所有弱分类器的加权投票。

在实际应用中，SAMME 通常会进行更多轮迭代，并使用更复杂的弱分类器（如决策树）以提升分类性能。此外，SAMME.R 是 SAMME 的一个变种，使用了概率估计，能够进一步提升性能和稳定性。