英文题目：A decision-theoretic generalization of on-line learning and an application to boosting

中文题目：在线学习的决策理论推广及其在Boosting中的应用

作者：Yoav Freund, Robert E. Schapire

发表期刊 或 会议：Journal of Computer and System Sciences

发表日期：September 20, 1995

AdaBoost可将弱学习算法的预测精度提升到任意高的水平！这项研究不仅为在线资源分配问题提供了一个更通用的框架，还为机器学习领域带来了新的思路。AdaBoost无需事先了解弱学习算法的性能，就能自适应地调整参数，最大程度地利用弱学习算法生成的假设，从而获得惊人的预测精度。

<研究背景与目的>

在 1990 年，Schapire 提出了最初的 Boosting 算法，展示了如何将多个弱学习器组合成一个强学习器。

1993 年，Drunker 和 Schapire 将 Boosting 算法应用于 OCR 问题，使用神经网络作为弱学习器。

1995 年，Freund 和 Schapire 在此论文中提出了 AdaBoost 算法，进一步发展了 Boosting 技术。

这篇论文研究了在线资源分配问题，并将其应用于提升弱学习算法的性能。在线资源分配问题旨在动态地将资源分配给一组选项，目标是在最坏情况下最小化累计损失，并与最佳选项的损失相比。传统的在线预测模型主要关注二元决策和结果空间（意味着模型只能预测两种可能的结果，例如“是”或“否”），而这篇论文将其扩展到更一般的决策理论框架（意味着模型可以处理更多种类的结果空间，包括多类别结果空间和连续结果空间），并将其应用于提升弱学习算法，使其能够处理更广泛的学习问题。

<创新点>

1. 将Littlestone和Warmuth的乘法权重更新规则应用于在线资源分配模型，并推导出更通用的边界。 这使得算法能够处理更广泛的学习问题，包括多结果预测、重复博弈和预测R^n中的点。
2. 提出了一种新的Boosting算法AdaBoost，该算法无需事先了解弱学习算法的性能。 AdaBoost能自适应地调整参数，以最大程度地利用弱学习算法生成的假设。
3. 将AdaBoost扩展到多类别预测问题，提出了AdaBoost.M1和AdaBoost.M2两种算法。 AdaBoost.M1要求弱假设的预测误差小于1/2，而AdaBoost.M2则使用更灵活的伪损失度量，允许弱学习器即使预测误差大于1/2也能做出贡献。
4. 将AdaBoost扩展到回归问题，提出了AdaBoost.R算法。 该算法将回归问题简化为二元分类问题，并利用AdaBoost来提升弱回归算法的性能。
   

<结论>

1. 在线资源分配算法Hedge(β)的性能可以接近最佳策略的性能，且误差率随时间减少。
2. AdaBoost能够将弱学习算法的性能提升到任意高的精度，其最终假设的误差以指数速度下降。
3. AdaBoost可以扩展到多类别预测和回归问题。
   

<实验内容>

论文中没有包含实验内容，但提到了Drucker, Schapire and Simard [7]的实验结果，表明新算法在实际应用中可能具有优势。

<对本领域的贡献>

1. 将在线预测模型推广到更一般的决策理论框架，并证明了乘法权重更新规则的广泛适用性。
2. 提出了一种新的自适应Boosting算法AdaBoost，该算法无需事先了解弱学习算法的性能，并在理论上证明了其有效性。
3. 为多类别预测和回归问题提供了新的Boosting算法。
   

<主要定理>

1. 定理2： 给出了Hedge(β)算法净损失的上界，证明其性能接近最佳策略。
2. 定理6： 给出了AdaBoost算法最终假设误差的上界，证明其误差以指数速度下降。
3. 定理10和定理11： 分别给出了AdaBoost.M1和AdaBoost.M2算法的误差上界，证明其可用于多类别预测问题。
4. 定理12： 给出了AdaBoost.R算法的均方误差上界，证明其可用于回归问题。
   

<存在的不足>

1. 论文中没有包含实验结果来验证新算法在实际应用中的性能。
2. 对于多类别预测问题，AdaBoost.M1和AdaBoost.M2的性能需要进一步的实证研究来比较。
3. 对于回归问题，需要进一步研究如何找到具有1/2损失的弱假设，以改进AdaBoost.R算法。
   

<未来的工作>

1. 将AdaBoost扩展到更复杂的学习问题，例如结构化预测和强化学习。
   

2.AdaBoost.M1算法

AdaBoost.M1 算法是一个用于解决多类别分类问题的 boosting 算法，它通过组合多个弱学习器来构建一个强学习器。 弱学习器指的是性能略好于随机猜测的分类器，而强学习器则可以达到很高的分类精度。

下面是算法的步骤详解：

1. 输入： 算法的输入包括 N 个带标签的训练样本、样本分布 D、弱学习算法 WeakLearn 以及迭代次数 T。 每个样本是一个二元组 (xᵢ, yᵢ)，其中 xᵢ 是一个实例，yᵢ 是它的标签。标签 yᵢ 来自于一个包含 k 个可能标签的集合 Y = {1, ..., k}。
   
2. 初始化： 算法将权重向量 w¹ 初始化为分布 D，这个权重向量为每个训练样本分配一个权重。初始时，可令所有样本的权重都相等。
   
3. 迭代： 算法进行 T 轮迭代，每轮迭代执行以下步骤：
   
   a. 计算样本分布： 根据当前的权重向量 wᵗ 计算样本分布 pᵗ，也就是将每个样本的权重除以所有样本权重之和。
   
   b. 调用弱学习器： 使用分布 pᵗ 调用弱学习算法 WeakLearn，得到一个弱假设 hₜ: X → Y。（学习出一个分类器 hₜ）
   
   c. 计算假设误差： 计算弱假设 hₜ 在当前样本分布 pᵗ 下的误差 εₜ，也就是 hₜ 分类错误的样本权重之和。如果 εₜ ≥ 1/2，说明这个弱假设的性能甚至不如随机猜测，此时设置 T = t - 1 并停止迭代。
   
   d. 计算更新参数： 根据误差 εₜ 计算更新参数 βₜ = εₜ / (1 - εₜ)。
   
   e. 更新权重向量： 使用更新参数 βₜ 更新样本权重向量 wᵗ⁺¹。更新规则是：如果弱假设 hₜ 在样本 xᵢ 上分类错误，则增加 xᵢ 的权重；否则，减少 xᵢ 的权重。具体来说，wᵗ⁺¹ᵢ = wᵗᵢ βₜ ^(1-[hₜ(xᵢ) ≠ yᵢ])，其中 [hₜ(xᵢ) ≠ yᵢ] 表示当 hₜ 在样本 xᵢ 上分类错误时为 1，否则为 0。
   
4. 输出： 迭代结束后，算法输出最终假设 hꜰ，该假设对新的样本 x 的预测结果是 arg maxᵧ∈Y Σₜ (log 1/βₜ) [hₜ(x) = y]，也就是所有弱假设的加权投票结果，其中每个弱假设的权重由更新参数 β 决定。
   

简而言之，AdaBoost.M1 算法通过迭代地训练弱学习器，并根据弱学习器的性能调整样本权重，最终得到一个强学习器。

AdaBoost.M1算法中的权重类型及用法

在AdaBoost.M1算法中，涉及的权重类型主要有以下几种：

1. 样本权重 \(w^t\):

• 类型：初始权重和更新权重
• 初始化： \(w^1_i = D(i)\) 对于每个样本 \(i\) 来说，其中 \(D(i)\) 表示样本的初始权重。
• 计算公式：在每次迭代结束后，权重 \(w^t\) 会根据弱学习器的错误率 \(\epsilon_t\) 进行更新：
  

  \(\displaystyle w^{t+1}_i = w^t_i \beta_t^{1 - [h_t(x_i) \neq y_i]}\)

  其中， \(\beta_t = \frac{\epsilon_t}{1 - \epsilon_t}\)
• 作用：初始化时表示每个样本的初始重要性，迭代过程中根据弱学习器的表现调整样本的权重，使得错误分类的样本在后续迭代中得到更大的关注。
  

2. 归一化权重 \(p^t\):

• 类型：归一化权重
• 计算公式：

• \(\displaystyle p^t_i = \frac{w^t_i}{\sum_{j=1}^N w^t_j}\)

• 作用：将当前迭代的权重 \(w^t\) 归一化为概率分布，以便提供给弱学习器 WeakLearn。
  

3. 错误率 \(\epsilon_t\):

• 类型：计算辅助权重
• 计算公式：

• \(\displaystyle \epsilon_t = \sum_{i=1}^N p^t_i [h_t(x_i) \neq y_i]\)

• 作用：衡量弱学习器在当前迭代中的错误率，指导下一步的权重更新。
  

通过以上几种权重的相互作用，AdaBoost.M1算法能够逐步提升整体分类器的性能，每次迭代中，样本的权重根据弱学习器的表现进行调整，使得难分类的样本得到更多的关注。

弱学习算法是如何使用分布 pᵗ 的？

弱学习算法使用分布 pᵗ 的方式取决于具体的算法实现。一般来说，有两种主要的方式：

1. 重新采样训练样本：

• 根据分布 pᵗ 对原始训练样本进行重新采样，生成一个新的训练集。新的训练集中，那些在 pᵗ 中权重较高的样本出现的次数更多，而权重较低的样本出现的次数更少。
• 使用新的训练集来训练弱学习算法，得到新的弱假设。
  

这种方法的优点是简单易懂，并且适用于大多数弱学习算法。缺点是重新采样可能会丢失一些信息，并且可能会导致训练集规模发生变化。

2. 直接修改算法的目标函数：

• 一些弱学习算法，例如基于梯度下降的算法，其目标函数通常包含一个损失函数项，用于衡量模型预测值与真实值之间的差异。
• 可以通过将损失函数乘以样本权重 pᵗᵢ 来修改目标函数，使得算法更加关注权重较高的样本。
• 使用修改后的目标函数来训练弱学习算法，得到新的弱假设。
  

这种方法的优点是能够更直接地利用样本权重信息，并且不会改变训练集规模。缺点是需要对弱学习算法进行修改，并且只适用于部分弱学习算法。

举例说明：

• 决策树算法： 当使用决策树作为弱学习算法时，可以使用重新采样方法。根据分布 pᵗ 对原始训练样本进行重新采样，然后使用新的训练集构建决策树。
• 支持向量机算法： 当使用支持向量机作为弱学习算法时，可以通过修改目标函数来使用样本权重。具体来说，可以将每个样本的损失乘以其对应的权重 pᵗᵢ，然后使用修改后的目标函数来训练支持向量机。
  

总结:

弱学习算法使用分布 pᵗ 的目的是，让算法更加关注权重较高的样本，从而在下一轮迭代中学习到更有效的弱假设。具体使用方式取决于具体的弱学习算法，可以采用重新采样方法或修改目标函数的方法。

\(\epsilon_t \)与 \(\omega_{t+1}\) 之间的关系

在 AdaBoost.M1 算法中，εₜ (epsilon_t) 代表第 t 轮弱学习器 hₜ 的分类误差，而 wᵗ⁺¹ (omega_{t+1}) 代表第 t+1 轮迭代的样本权重向量。 这两者之间存在着密切的联系， εₜ 直接影响 wᵗ⁺¹ 的更新。

具体来说，他们的关系体现在以下几个方面：

1. εₜ 决定 βₜ，进而影响 wᵗ⁺¹：
   
   • 更新参数 βₜ 由 βₜ = εₜ / (1 - εₜ) 计算得到，εₜ 越大， βₜ 也越大。
   • 样本权重更新公式为 wᵗ⁺¹ᵢ = wᵗᵢ βₜ ^(1-[hₜ(xᵢ) ≠ yᵢ]) 。 βₜ 越大，分类正确的样本权重降低越多，而分类错误的样本权重保持不变。
     
2. εₜ 越大，wᵗ⁺¹ 中难以分类样本的权重占比越高：
   
   • 当 εₜ 较大时，说明当前弱学习器 hₜ 性能较差，很多样本都被分类错误。
   • 此时 βₜ 也会较大，导致分类正确的样本权重被大幅降低，而分类错误的样本权重保持不变。
   • 最终结果是， wᵗ⁺¹ 中那些难以分类的样本的权重占比会显著提高，使得他们在下一轮迭代中得到更多关注。
     
3. εₜ 引导后续弱学习器关注难以分类的样本：
   
   • AdaBoost.M1 算法的核心思想是，每一轮迭代都重点关注那些被先前弱学习器分类错误的样本。
   • εₜ 反映了当前弱学习器的分类性能，通过 βₜ 影响样本权重 wᵗ⁺¹，进而引导后续弱学习器更加关注那些难以分类的样本。
     

总结:

εₜ 和 wᵗ⁺¹ 之间的关系是 AdaBoost.M1 算法的核心机制。 εₜ 越大，说明当前弱学习器性能越差，算法会通过增大 βₜ 来大幅降低分类正确样本的权重，从而使得 wᵗ⁺¹ 中难以分类样本的权重占比更高。 这就迫使后续弱学习器更加关注这些难以分类的样本，最终提高整个模型的分类精度。

对输出结果的解释

这个公式定义了 AdaBoost.M1 算法的最终假设 hꜰ(x)，它是一个整合了所有弱假设的强分类器。

具体解释如下：

• h_f(x): 代表最终假设 hꜰ 对新样本 x 的预测结果，也就是最终预测的标签。
• arg maxᵧ∈Y : 代表取使得后面表达式最大化的标签 y，也就是说，最终预测的标签是所有标签中，得分最高的那个标签。
• Σₜ (log 1/βₜ) [hₜ(x) = y]： 这是每个标签 y 的得分计算公式，它累加了所有弱假设对该标签的支持程度。
  
  • Σₜ： 代表对所有 T 个弱学习器进行求和。
  • log 1/βₜ： 代表第 t 个弱学习器 hₜ 的权重，该权重由更新参数 βₜ 决定。 βₜ 越小，说明弱学习器 hₜ 的误差越小，其权重就越大。
  • [hₜ(x) = y]： 这是一个指示函数，当弱学习器 hₜ 将样本 x 预测为标签 y 时为 1，否则为 0。
    

因此，这个公式的含义是：

对于新样本 x，最终假设 hꜰ 会遍历所有可能的标签 y，并计算每个标签 y 的得分。每个标签 y 的得分是所有将样本 x 预测为标签 y 的弱学习器的权重之和。最终预测的标签是得分最高的那个标签。

简单来说，AdaBoost.M1 算法的最终假设 hꜰ 是对所有弱假设的加权投票，每个弱假设的投票权重由其分类误差决定。 分类误差越小的弱假设拥有更大的投票权重，从而对最终预测结果的影响也越大。

3. AdaBoost.M2算法

AdaBoost.M2 算法是 AdaBoost 算法的另一个多类别分类扩展版本，它在弱学习器和 boosting 算法之间采用了更复杂的通信机制，为弱学习器提供了更大的灵活性。

算法解释：

1. 输入：
   
   • N 个带标签的样本 ((x₁, y₁), ..., (xₙ, yₙ))，其中标签 yᵢ ∈ Y = {1, ..., k}。
   • 样本分布 D。
   • 弱学习算法 WeakLearn。
   • 迭代次数 T。
     
2. 初始化： 为每个样本 xᵢ 和每个不等于真实标签 yᵢ 的标签 y，初始化一个权重 \(w_{i, y}^1=D(i) /(k-1)\)。这表示每个样本在初始时，对每个错误标签的权重都相等。
   
3. 迭代： 算法进行 T 轮迭代，每轮迭代执行以下步骤：
   
   a. 计算样本权重和标签权重函数：

• 计算每个样本的权重\(W_i^t=\sum_{y \neq y_i} w_{i, y}^t\) 。
• 计算标签权重函数 \(q_t(i, y)=\frac{w_{i, y}^t}{W_i^t}\)。 这表示在样本 xᵢ 上，区分真实标签 yᵢ 和错误标签 y 的重要性。
• 计算样本分布 \(D_t(i)=\frac{W_i^t}{\sum_{i=1}^N W_i^t}\)。
  
  b. 调用弱学习器： 使用分布 Dᵗ 和标签权重函数 qᵗ 调用 WeakLearn，得到一个弱假设 hₜ: X × Y → [0, 1]。
• 与 AdaBoost.M1 不同，这里的弱假设输出一个介于 0 到 1 之间的值，表示对每个标签的置信度。
  
  c. 计算伪损失： 计算弱假设 hₜ 的伪损失 εₜ = (1/2) Σᵢ Dᵗ(i) (1 - hₜ(xᵢ, yᵢ) + Σᵧ≠yᵢ qᵗ(i, y) hₜ(xᵢ, y))。
  
• 伪损失衡量了弱假设在区分真实标签和其他标签方面的能力。
  
  d. 计算更新参数： 根据伪损失 εₜ 计算更新参数 βₜ = εₜ / (1 - εₜ)。
  
  e. 更新权重向量： 使用更新参数 βₜ 更新样本权重向量 wᵗ⁺¹ᵢ,ᵧ = wᵗᵢ,ᵧ βₜ^(1/2)(1+hₜ(xᵢ,yᵢ)-hₜ(xᵢ,y))，y ≠ yᵢ。
• 更新规则与 AdaBoost.M1 类似，但考虑了弱假设对每个标签的置信度。
  

4. 输出： 迭代结束后，算法输出最终假设 hꜰ(x) = arg maxᵧ∈Y Σₜ (log 1/βₜ) hₜ(x, y)。
   
   • 最终假设也是对所有弱假设的加权投票，但投票权重考虑了弱假设对每个标签的置信度。
     

总结：

AdaBoost.M2 算法通过引入标签权重函数和伪损失，使得弱学习器能够更灵活地进行预测，即使在某些样本上无法准确预测真实标签，也能通过区分其他标签来提供有用信息，最终提高整个模型的分类精度。

AdaBoost.M2算法的权重类型其及用法

AdaBoost.M2算法中的权重类型及用法

在AdaBoost.M2算法中，涉及的权重类型主要有以下几种：

1. 样本权重 \(w_{i,j}^t\):
   
   • 类型：初始权重和更新权重
   • 初始化：对于每个样本 \(i\) 和类别 \(y \neq y_i\)，初始化权重为 \(w_{i,j}^t = \frac{D(i)}{k-1}\)，其中 \(k\) 是类别数，\(D(i)\) 是样本 \(i\) 的初始权重。
   • 计算公式：在每次迭代结束后，权重 \(w_{i,j}^t\) 会根据以下公式进行更新：
     

     \(\displaystyle w_{i,j}^{t+1} = w_{i,j}^t \beta_t^{\frac{1}{2}(1 + h_t(x_i, y_i) - h_t(x_i, y))}\)

     其中，\(\beta_t = \frac{\epsilon_t}{1 - \epsilon_t}\)。
   • 作用：初始化时表示每个样本的初始重要性，迭代过程中根据弱学习器的表现调整样本的权重，使得错误分类的样本在后续迭代中得到更大的关注。
     
2. 归一化权重 \(W_i^t\):
   
   • 类型：归一化权重
   • 计算公式：计算当前迭代的归一化权重 \(W_i^t\)：
     

     \(\displaystyle W_i^t = \sum_{y \neq y_i} w_{i,y}^t\)

   • 作用：将当前迭代的权重 \(w_{i,y}^t\) 归一化为概率分布，以便提供给弱学习器 WeakLearn。
     
3. 类别权重 \(q_t(i, y)\):
   
   • 类型：计算辅助权重
   • 计算公式：类别权重 \(q_t(i, y)\) 计算公式如下：
     

     \(\displaystyle q_t(i, y) = \frac{w_{i,y}^t}{W_i^t}\)

     其中 \(y \neq y_i\)。
   • 作用：用于计算 \(h_t\) 的伪损失 \(\epsilon_t\)，表示样本 \(i\) 被错误分类为类别 \(y\) 的权重。
     
4. 伪损失 \(\epsilon_t\):
   
   • 类型：计算辅助权重
   • 计算公式：伪损失 \(\epsilon_t\) 的计算公式如下：
     

     \(\displaystyle \epsilon_t = \frac{1}{2} \sum_{i=1}^N D_t(i) \left(1 - h_t(x_i, y_i) + \sum_{y \neq y_i} q_t(i, y) h_t(x_i, y)\right)\)

   • 作用：衡量弱学习器在当前迭代中的错误率，指导下一步的权重更新。
     
5. 分布 \(D_t(i)\):
   
   • 类型：分布权重
   • 计算公式：分布 \(D_t(i)\) 的计算公式如下：
     

     \(\displaystyle D_t(i) = \frac{W_i^t}{\sum_{i=1}^N W_i^t}\)

   • 作用：用于表示当前迭代中每个样本的分布权重，指导弱学习器的训练。
     

通过以上几种权重的相互作用，AdaBoost.M2算法能够逐步提升整体分类器的性能，每次迭代中，样本的权重根据弱学习器的表现进行调整，使得难分类的样本得到更多的关注。

损失函数的解释

损失函数：

\(\displaystyle \epsilon_t = \frac{1}{2} \sum_{i=1}^{N} D_t(i) \left( 1 - h_t(x_i, y_i) + \sum_{y \neq y_i} q_t(i, y) h_t(x_i, y) \right)\)

1. \(\displaystyle \epsilon_t\)

• 作用：表示第 \(t\) 轮弱分类器 \(h_t\) 的加权误差。
• 意义：这个值越小，表示当前弱分类器 \(h_t\) 在当前权重分布 \(D_t\) 下表现越好。
  

2. \(\displaystyle \frac{1}{2}\)

• 作用：缩放因子。
• 意义：将整个公式的值缩小到合理的范围，通常在0到1之间，方便后续计算和比较。
  

3. \(\displaystyle \sum_{i=1}^{N}\)

• 作用：对所有训练样本求和。
• 意义：累积每个样本的加权误差，得到整体的加权误差。
  

4. \(\displaystyle D_t(i)\)

• 作用：第 \(t\) 轮中第 \(i\) 个训练样本的权重。
• 意义：反映了当前轮次中每个样本的重要性。权重越大的样本对总误差的影响越大，算法会更关注这些样本。
  

5. \(\displaystyle 1 - h_t(x_i, y_i)\)

• 作用：如果弱分类器 \(h_t\) 对第 \(i\) 个样本分类正确，这一项为0；如果分类错误，这一项为1。
• 意义：衡量分类器在正确分类时的表现。如果分类正确，则不增加误差；如果分类错误，则增加误差。
  

6. \(\displaystyle \sum_{y \neq y_i} q_t(i, y) h_t(x_i, y)\)

• 作用：对所有非真实标签 \(y \neq y_i\) 的误差进行加权求和。
• 意义：衡量分类器在错误分类时的置信度。如果分类器认为错误标签 \(y\) 是正确的，并且置信度高，则这一项会增加总误差。\(q_t(i, y)\) 是标签 \(y\) 的权重，表示不同错误标签的重要性。
  

7. \(\displaystyle q_t(i, y)\)

• 作用：标签权重分布，针对第 \(i\) 个样本对所有非真实标签 \(y \neq y_i\) 的权重。
• 意义：强调在区分真实标签和不同错误标签时的难度。如果某个错误标签容易被混淆，该标签的权重会更高，从而在计算误差时更突出其影响。
  

8. \(\displaystyle h_t(x_i, y)\)

• 作用：弱分类器 \(h_t\) 对样本 \(x_i\) 预测标签 \(y\) 的输出。
• 意义：如果分类器认为标签 \(y\) 是正确的，输出较高；否则输出较低。这一项在计算错误标签的置信度时起作用。
  

通过以上每一项的解释，我们可以看到公式整体上是如何综合考虑分类器在正确分类和错误分类时的表现，通过样本权重 \(D_t(i)\) 和标签权重 \(q_t(i, y)\) 动态调整分类器的关注点，从而在每一轮迭代中逐步优化分类器的整体性能。

输出函数的解释

在AdaBoost.M2算法中，最终输出的分类器是通过综合所有弱分类器的输出得到的。具体形式如下：

\(\displaystyle h_f(x) = \arg \max_{y \in Y} \sum_{t=1}^T \left( \log \frac{1}{\beta_t} \right) h_t(x, y)\)

1. \(h_f(x)\):

这是最终的组合分类器，用于对输入 \(x\) 进行分类。

2. \(\arg \max_{y \in Y}\):

表示在所有类别 \(y \in Y\) 中找到使得后面表达式最大的类别。也就是说，最终的分类结果是使得后面加权和最大的类别。

3. \(\sum_{t=1}^T\):

表示对所有 \(T\) 个弱分类器的加权和。

4. \(\left( \log \frac{1}{\beta_t} \right)\):

这是对每个弱分类器的权重，\(\beta_t = \frac{\epsilon_t}{1 - \epsilon_t}\)，其中 \(\epsilon_t\) 是第 \(t\) 个弱分类器的伪损失。通过取对数并取倒数，增加了弱分类器在最终分类器中的权重。

5. \(h_t(x, y)\):

这是第 \(t\) 个弱分类器在输入 \(x\) 上对类别 \(y\) 的预测，\(h_t : X \times Y \rightarrow [0,1]\)。表示输入 \(x\) 被分类为 \(y\) 的概率。

总结：

最终的输出分类器 \(h_f(x)\) 通过加权求和所有弱分类器 \(h_t\) 对输入 \(x\) 的预测结果，并选择使加权和最大的类别作为最终的分类结果。权重 \(\left( \log \frac{1}{\beta_t} \right)\) 反映了每个弱分类器的准确性，准确性越高的弱分类器在最终结果中占的比重越大。通过这种方式，AdaBoost.M2 能够有效地提升分类性能。

权重更新式的解释

这个权重更新公式在Adaboost.M2算法中用于更新每一轮迭代后的样本权重：

\(\displaystyle w_{i,y}^{t+1} = w_{i,y}^t \beta_t^{(1/2)(1 + h_t(x_i, y_i) - h_t(x_i, y))} \)

公式中每一项的作用：

1. \( w_{i,y}^{t+1} \)：

作用：表示第 (t+1) 轮中样本\(x_i\) 的标签 y 的权重。

意义：这是我们更新后的权重，用于下一轮迭代。

2. \(w_{i,y}^t\)：

作用：表示第 (t) 轮中样本\(x_i\)的标签 y的权重。

意义：这是当前轮次的权重，新的权重是基于当前权重进行调整的基础。

3. \(\beta_t\)：

作用：表示用于调整权重的系数，通常基于当前轮次弱分类器的误差\(\epsilon_t\)计算得出。

意义：它决定了权重调整的幅度。通常，\(\beta_t\)的值是 \(\beta_t = \frac{\epsilon_t}{1 - \epsilon_t}\)。分类器表现越好（误差越小），\(\beta_t\)越小，反之，分类器表现越差，\(\beta_t\)越大。

4. \((1/2)(1 + h_t(x_i, y_i) - h_t(x_i, y)) \)：

作用：调整权重的因子，根据分类器在真实标签和错误标签上的输出进行调整。

• \(h_t(x_i, y_i)\)是弱分类器对样本\(x_i\)的真实标签\(y_i\)的输出可能性。
  
  • \(h_t(x_i, y)\)是弱分类器对样本 \(x_i\)的标签 y的输出可能性。

意义：

• 如果\(y = y_i\)，则 \(h_t(x_i, y_i) - h_t(x_i, y_i) = 0\)，所以调整因子为\((1/2)(1 + 0) = 1/2\)，表示权重缩小一半。
  
  • 如果\(y \neq y_i\)，则\(h_t(x_i, y_i) - h_t(x_i, y)\) 反映了分类器区分真实标签和错误标签的能力：
  • 若\(h_t(x_i, y_i)\)较大而 \(h_t(x_i, y)\)较小，则\(1 + h_t(x_i, y_i) - h_t(x_i, y)\) 接近2，调整因子较大，权重变化显著。
  • 反之，若分类器在错误标签上的输出较大，则调整因子较小，权重变化较小。
    

总体解释：

该公式描述了如何在每一轮迭代中根据弱分类器的输出和当前样本权重来更新样本的标签权重。具体来说，它通过缩放因子 (beta_t) 来调整权重，同时考虑了分类器在真实标签和错误标签上的输出可能性，确保分类器在下一轮中更关注那些当前分类错误的样本，从而逐步提高整体分类性能。

总结

AdaBoost.M2算法可适用于多分类问题，它并不直接输出所属的类别的标签，而是输出一个在[0, 1]范围之内的数值，以此来表示此样本为某一类别的可能性，此数值越大，则属于该类别的可能性越大。这个可能性数值是每个weakLearner的输出，在将所有的weakLearner的输出综合起来时，并不是简单的综合，而是使用了输出函数。在输出函数中使用了一个权重\(\beta_t = \frac{\epsilon_t}{1 - \epsilon_t}\)，其中\(\epsilon_t\)为损失函数，也就是说，\(\epsilon_t\)越大，\(\beta_t \)也就越大。在计算\(\epsilon_t\)时，用到了类别权重\(q_t(i,y)\)和样本权重\(D_t(i)\)，这两个权重又会用到样本与类别的联合权重\(w^t_{i,y}\)，\(w^t_{i,y}\)又会在每一次迭代时进行更新。

4. AdaBoost.R 算法

AdaBoost.R 算法是 AdaBoost 算法的一种扩展，用于解决回归问题，其标签空间为 \(Y = [0,1]\)。 该算法的核心思想是将回归问题转化为二元分类问题，并利用 AdaBoost 算法来提升弱回归算法的性能。

算法解释：

输入：

\(N\) 个带标签的样本 \(((x_1, y_1), ..., (x_N, y_N))\)，其中标签 \(y_i \in Y = [0, 1]\)。

样本分布 \(D\)。

弱学习算法 WeakLearn。

迭代次数 \(T\)。

初始化： 为每个样本 \(x_i\) 和每个标签值 \(y \in Y\)，初始化权重为：

\(\displaystyle w_{i,y}^1 = \frac{D(i)|y-y_i|}{Z} \)

其中 \(Z\) 是一个归一化常数，用于确保权重之和为 1：

\(\displaystyle Z = \sum_{i=1}^N D(i) \int_0^1 |y - y_i| dy. \)

迭代： 算法进行 \(T\) 轮迭代，每轮迭代执行以下步骤：

a. 计算密度函数: 根据当前权重 \(w^t\) 计算密度函数 \(p^t\)：

\(\displaystyle p^t = \frac{w^t}{\sum_{i=1}^N \int_0^1 w_{i,y}^t dy} \)

b. 调用弱学习器: 使用密度函数 \(p^t\) 调用 WeakLearn，得到一个弱假设 \(h_t: X \to Y\)。

c. 计算损失: 计算弱假设 \(h_t\) 的损失 \(\epsilon_t\)：

\(\displaystyle \epsilon_t = \sum_{i=1}^N \left| \int_{y_i}^{h_t(x_i)} p_{i,y}^t dy \right| \)

如果 \(\epsilon_t > 1/2\)，则设置 \(T = t-1\) 并停止迭代。

d. 计算更新参数: 根据损失 \(\epsilon_t\) 计算更新参数 \(\beta_t = \epsilon_t / (1 - \epsilon_t)\)。

e. 更新权重向量: 使用更新参数 \(\beta_t\) 更新权重向量：

输出： 迭代结束后，算法输出最终假设：

解释：

AdaBoost.R 算法将每个样本和每个可能的标签值组合成一个新的样本，并通过权重函数将回归问题转化为二元分类问题。 算法迭代地训练弱学习器，并根据弱学习器的性能调整样本权重，使得难以预测的样本得到更多关注。最终假设是所有弱假设的加权中位数，其中权重由每个弱假设的损失决定。

y 是连续的，那么\(w_{i, y}\)会有无穷多个？

在 AdaBoost.R 中，因为 \(y\) 是连续的，所以 \(w_{i, y}\) 确实会有无穷多个。

更准确地说，\(w_{i, y}\) 是一个关于 \(y\) 的函数，它的值表示实例 \(i\) 在 \(y\) 处被弱学习器选中的概率，它被定义为：

\(\displaystyle w_{i, y}^1=\frac{D(i)\left|y-y_i\right|}{Z} \)

其中，\(D(i)\) 是实例 \(i\) 在训练集中的权重，\(Z\) 是一个归一化常数，使得所有 \(w_{i, y}\) 的积分等于 1。

由于 \(y\) 是连续的，所以 \(w_{i, y}\) 的值在 \(y\) 上是连续变化的，而不是离散的。 为了在实践中使用 AdaBoost.R，通常会将 \(y\) 进行离散化，例如将 \(y\) 划分成 \(k\) 个等间隔的子区间。 这样一来，\(w_{i, y}\) 就变成了 \(k\) 个离散的权重，每个权重表示实例 \(i\) 属于相应子区间的概率。

下面公式中的\(\mathbf{w}\)是什么

这个式子中 \(\mathbf{w}^t\) 的表示方法可能造成了一些困惑。实际上，在这个算法中，并没有一个直接叫做 \(\mathbf{w}^t\) 的向量。更确切地说，在每一轮 \(t\)，算法维护的是一个 权重函数 \(w^t_{i,y}\)，它定义在每个实例 \(i\) 和每个可能的标签值 \(y \in [0,1]\) 上。

因此，与其说 \(\mathbf{w}^t\) 是一个向量，不如说它代表了所有 \(w^t_{i,y}\) 的集合。

在您引用的步骤 1 中，算法计算的是一个 概率密度函数 \(\mathbf{p}^t\)，它也是定义在每个实例 \(i\) 和每个可能的标签值 \(y \in [0,1]\) 上。这个密度函数是通过对 \(w^t_{i,y}\) 进行归一化得到的，也就是除以所有 \(w^t_{i,y}\) 的积分：

\(\displaystyle \mathbf{p}^t=\frac{\mathbf{w}^t}{\sum_{i=1}^N \int_0^1 w_{i, y}^t d y} . \)

所以，这里的 \(\mathbf{w}^t\) 实际上代表了所有 \(w^t_{i,y}\) 的集合，而不是一个具体的向量。

如何解释输出函数

此函数是 AdaBoost.R 算法中最终的预测函数 \(h_f(x)\)，它用于回归问题，即预测一个连续的标签值。

让我们逐步解释这个函数的含义：

弱学习器预测: \(h_t(x)\) 代表第 \(t\) 个弱学习器在输入 \(x\) 上的预测值。

权重: \(\log(1/\beta_t)\) 代表第 \(t\) 个弱学习器的权重。注意到 \(\beta_t = \epsilon_t / (1 - \epsilon_t)\)，其中 \(\epsilon_t\) 是第 \(t\) 个弱学习器的误差。因此，弱学习器的误差越小，它的权重就越大。

累积权重: \(\sum_{t: h_t(x) \leq y} \log \left(1 / \beta_t\right)\) 代表所有预测值小于等于 \(y\) 的弱学习器的权重之和。

中位数: \(\frac{1}{2} \sum_t \log \left(1 / \beta_t\right)\) 代表所有弱学习器权重之和的一半。

最终预测: 这个输出函数的意思是，找到最小的 \(y\) 值，使得所有预测值小于等于 \(y\) 的弱学习器的权重之和至少为所有弱学习器权重之和的一半。换句话说，\(h_f(x)\) 是所有弱学习器预测值的一个加权中位数。

直观解释:

AdaBoost.R 的最终预测函数 \(h_f(x)\) 通过对所有弱学习器的预测值进行加权投票来得到最终的预测值。 每个弱学习器的投票权重由其准确性决定：误差越小的弱学习器权重越大。 \(h_f(x)\) 寻找一个预测值，使得权重更大的弱学习器 "支持" 这个预测值。

例子:

假设我们有三个弱学习器，它们的预测值分别是 \(h_1(x) = 0.2\), \(h_2(x) = 0.6\), \(h_3(x) = 0.8\)，对应的权重分别是 \(\log(1/\beta_1) = 1\), \(\log(1/\beta_2) = 2\), \(\log(1/\beta_3) = 3\)。 那么所有弱学习器权重之和的一半是 \((1 + 2 + 3)/2 = 3\)。 我们可以看到，当 \(y = 0.6\) 时，所有预测值小于等于 \(y\) 的弱学习器的权重之和为 \(1 + 2 = 3\)，正好等于所有弱学习器权重之和的一半。 因此，最终预测值 \(h_f(x) = 0.6\)。

论文链接：https://www.jianguoyun.com/p/Da9MdtYQhs2mCRiAn9IFIAA