Вопрос или проблема
Я пытаюсь решить следующую задачу, но застрял.
Итак, для адебуст $err_t = \frac{\sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) \neq t^{(i)})}{\sum_{i=1}^{N}w_i}$
и $\alpha_t = \frac{1}{2}ln(\frac{1-err_t}{err_t})$
Весы для следующей итерации равны $w_i’ = w_i exp(-\alpha_t t^{(i)} h_t(x^{(i)}))$ и это предполагает, что $t$ и $h_t$ принимают значение либо $-1$, либо $+1$.
Мне нужно показать, что ошибка по отношению к новым весам $w_i’$ равна $\frac{1}{2}$. То есть, $err_t’ = \frac{\sum_{i=1}^{N}w_i’ \Pi (h_t(x^{(i)}) \neq t^{(i)})}{\sum_{i=1}^{N}w_i’} = \frac{1}{2}$
То есть мы используем слабого учащегося итерации t и оцениваем его согласно новым весам, которые будут использоваться для обучения $t+1$-го слабого учащегося.
Я упростил это так, что $w_i’=w_i \sqrt{\frac{err_t}{1-err_t}}$, если $w_i$ был правильно классифицирован, и $w_i’=w_i \sqrt{\frac{1-err_t}{err_t}}$, если $w_i$ был классифицирован неправильно. Затем я попытался подставить это в уравнение для $err_t’=\frac{1}{2}$ и получил $\frac{err_t}{1-err_t} \frac{\sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) = t^{(i)})}{\sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) \neq t^{(i)})} = 1$, но в этот момент я как бы натолкнулся на тупик и теперь я задаюсь вопросом, как можно показать исходный вопрос.
Спасибо за любую помощь!
Вы почти у цели. Количество $err_t/(1-err_t)$ – это именно то, что вам нужно. Может быть легче увидеть, если вы подумаете о $$\sum_{i=1}^N w_i \Pi(h_t(x^{(i)})=t^{(i)})$$ как о $$\sum_{i:\ x^{(i)}\text{ правильно классифицирован}} w_i$$ (просто используя индикаторную функцию, чтобы сократить диапазон суммирования).
Для упрощения давайте определим некоторые переменные следующим образом:
$W_C := \sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) = t^{(i)})$
$W_I := \sum_{i=1}^{N}w_i \Pi (h_t(x^{(i)}) \neq t^{(i)})$
Таким образом, $err_t = W_I/(W_C+W_I)$
$a := \sqrt{\frac{err_t}{1-err_t}} = \sqrt{\frac{W_I}{W_C}}$
Теперь для новых весов у нас есть
$W’_C := \sum_{i=1}^{N}w’_i \Pi (h_t(x^{(i)}) = t^{(i)}) = aW_C$
$W’_I := \sum_{i=1}^{N}w’_i \Pi (h_t(x^{(i)}) \neq t^{(i)}) = (1/a)W_I$
Теперь, на финальном этапе:
$err’_t = \frac{W’_I}{W’_I + W’_C} = \frac{(1/a)W_I}{(1/a)W_I + aW_C} \overset{\times a}{=} \frac{W_I}{W_I + a^2W_C} = \frac{W_I}{W_I + \frac{W_I}{W_C}W_C}=\frac{1}{2}$
Ответ или решение
Обоснование того, что корректировка весов в Adaboost приводит к ошибке текущей итерации, равной 0.5
Adaboost (Adaptive Boosting) — это алгоритм, который использует ансамблевый подход для повышения точности классификации через итеративную коррекцию весов. В данной задаче нам нужно установить, что обновление весов после итерации приводит к ошибке в 0.5.
Формулы, используемые в алгоритме
-
Ошибка текущей итерации (
err_t) определяется как:[
errt = \frac{\sum{i=1}^{N}w_i \Pi(ht(x^{(i)}) \neq t^{(i)})}{\sum{i=1}^{N}w_i}
]где ( w_i ) — веса, ( h_t(x^{(i)}) ) — предсказание текущего слабого классификатора, а ( t^{(i)} ) — истинный класс.
-
Коэффициент Альфа (α) для текущего слабого классификатора задается как:
[
\alpha_t = \frac{1}{2} \ln\left(\frac{1-err_t}{err_t}\right)
] -
Обновление весов для следующей итерации определяется следующей формулой:
[
w_i’ = w_i \cdot \exp(-\alpha_t t^{(i)} h_t(x^{(i)}))
]
Обозначения для упрощения
Для упрощения записи мы введем следующие обозначения:
- ( WC := \sum{i=1}^{N}w_i \Pi(h_t(x^{(i)}) = t^{(i)}) ) — сумма весов правильно классифицированных объектов.
- ( WI := \sum{i=1}^{N}w_i \Pi(h_t(x^{(i)}) \neq t^{(i)}) ) — сумма весов неправильно классифицированных объектов.
Следовательно, ошибка может быть выражена как:
[
err_t = \frac{W_I}{W_C + W_I}
]
Соотношение весов в следующей итерации
Теперь обновления весов можно выразить в терминах ( W_C ) и ( W_I ):
-
Если объект классифицируется правильно, то:
[
w_i’ = w_i \sqrt{\frac{err_t}{1 – err_t}} \text{ (если правильно классифицирован)}
] -
Если объект классифицируется неправильно, то:
[
w_i’ = w_i \sqrt{\frac{1 – err_t}{err_t}} \text{ (если неправильно классифицирован)}
]
Теперь мы можем рассчитать новые веса:
-
Для правильно классифицированных объектов:
[
W’_C = a W_C \quad \text{где}\ a = \sqrt{\frac{err_t}{1 – err_t}} = \sqrt{\frac{W_I}{W_C}}
] -
Для неправильно классифицированных объектов:
[
W’_I = \frac{1}{a} W_I \quad \text{где}\ \frac{1}{a} = \sqrt{\frac{1 – err_t}{err_t}} = \sqrt{\frac{W_C}{W_I}}
]
Вычисление новой ошибки
Теперь можно выразить новую ошибку:
[
err’_t = \frac{W’_I}{W’_I + W’_C} = \frac{\frac{1}{a} W_I}{\frac{1}{a} W_I + a W_C}
]
Умножая числитель и знаменатель на ( a ):
[
err’_t = \frac{W_I}{W_I + a^2 W_C} = \frac{W_I}{W_I + \frac{W_I}{W_C} W_C} = \frac{1}{2}
]
Таким образом, мы получили соотношение, показывающее, что:
[
err’_t = \frac{1}{2}
]
Заключение
Таким образом, обновление весов в алгоритме Adaboost корректирует оценку ошибки на текущей итерации к значению 0.5. Это критически важно, так как позволяет системе акцентировать усилия на более сложных для классификации объектах в следующих итерациях. Такое поведение делает Adaboost мощным инструментом для построения надежных классификаторов, способных комбинировать результаты множеств слабых классификаторов в один сильный.
Этот процесс способствует не только повышению точности, но и стабилизации результатов, что в свою очередь позволяет эффективно справляться с задачами машинного обучения.