提升算法 - 分类器产生正确的标签

Question

我是一名计算机科学专业的学生；我正在自学算法课程

在课程中，我看到了这个问题：

Suppose we have a set X = {x1, . . . , xn} of elements, each with a label L(i) ∈ {0, 1} (think of x(i) as a picture, and the label indicates whether it is a cat or not). We also have a set of classifiers H, and an algorithm A that given any distribution D on X, outputs h ∈ H such that

Pr(i∼D)[h(x(i)) = L(i)] ≥ 0.51

Show an algorithm that produces a set of T = O(log n) classifiers h (1), . . . , h(T) ∈ H, such that the majority vote among these T classifiers yields the correct label for all 1 ≤ i ≤ n.

photo of the question

据我了解，这是一个与boosting相关的问题。但是我不清楚如何显示这个问题的算法。

我找到了一个算法，但不知道是否适合问题：

Algorithm 1 Boost(D, A)
Let T ← 4 log n/ E^2 for E < 0.01.
Initialize a copy of polynomial weights to run over w^t ∈ ∆n.
for t = 1 to T do
  Let h^t = A(D, w^t)
  Let L^t ∈ [0, 1]^m be such that L^t_i = 1[h^t(xi) = yi].
  Pass L^t to the PW algorithm.
end for
Let pˆ =1/T(SIGMA^T_t=1 e_h^t )
Return fpˆ(x).

link to algorithm, page 16

老实说，我不明白如何解决这个问题。

Answer 1

我们可以将其视为 two-player zero-sum 游戏。 Carol（“分类器” 播放器）选择一个分类器，Dave（“数据”播放器）选择一个标记的元素。如果分类器在这一点上是正确的，则卡罗尔获胜元素，如果不正确，Dave 将获胜。

算法 A 意味着卡罗尔至少可以赢得这场比赛的 51% 时间。我们可以使用运行 ε = 0.005 (0.5%) 的算法 ComputeEQ 来找到一个 Carol 的策略，她从 O(log n) 中随机选择分类器并至少有 50.5% 的时间获胜，无论 Dave 战略。这意味着多数票对所有 n 都是正确的元素。

（这真的是https://cs.stackexchange.com的一道题。）

提升算法 - 分类器产生正确的标签

boosting algorithm - classifiers yields the correct label

algorithm

boosting