Осуществимость алгоритма машинного обучения (краеугольный камень машинного обучения)

Модель изучается на обучающих выборках для оценки неизвестных данных (представление можно рассматривать как удерживание горстки шариков из корзины и оценку соотношения разных цветов во всей корзине через соотношение разных цветов в шариках). , что является типичным небольшим взглядом на большое , мы должны изучить, как машинное обучение гарантирует, что этот «заглянуть» осуществим. Выполнимость машинного обучения, то есть есть надежда доказать частоту ошибок E для h в выборке._inможет и частота ошибок E по неизвестным данным_outБлиже, значит следующий шаг - опускание Е_in, чтобы получить соответствующее малое E_out, а затем получить h, который ближе к f как g, чтобы добиться хорошего эффекта машинного обучения.

Шаг за шагом (все берут бинарную задачу в качестве примера):

• Hoeffding

Математически доказано неравенство Хёффдинга, что доказывает одно: при достаточно большом размере выборки пропорция в выборке очень близка к общей реальной пропорции, то есть так называемая вероятно приблизительно правильная (ПАК)

Для данной гипотезы Хёффдинг можно использовать в качестве основы для суждения о том, является ли h хорошим, то есть, если частота ошибок h в выборке мала, максимальная вероятность может гарантировать, что она имеет небольшую частоту ошибок в выборке. все реальные данные.

• Multi-binhoeffding

Для наборов гипотез, содержащих много h, нельзя просто использовать вывод Хёффинга. Если маловероятное событие повторяется много раз, вероятность его возникновения будет очень велика (если 150 человек подбрасывают монету 5 раз, вероятность того, что хотя бы один человек пять раз выпадет решкой, составляет 99,15 %, и речь идет только об одном человеке). Эта вероятность равна 1/32), что делает возможной следующую ситуацию: по выборке D в H выбирается h с наименьшей частотой ошибок, но фактически h имеет большую частоту ошибок в целом, т. е. , образец D для H - образец BAD

Для заданного произвольного D вероятность того, что это ПЛОХАЯ выборка некоторого h, равна P, и можно вывести, что P пропорциональна количеству выборочных данных N и обратно пропорциональна количеству M h в H (используя Hoeffingh и объединение), то есть говорят, что когда M меньше, а N больше, мы можем выбрать тот, у которого наименьшая частота ошибок в H, в качестве желаемого g.

(A)

На данный момент доказано, что [при условии, что M конечно и N достаточно велико] для любого h в H, E_in≈ Е_out

Ссылаться на:Нет. OSCHINA.net/найти Билла/ было бы…

• VC bound

[В случае M->∞] Как преобразовать M в конечный и медленно растущий многочлен, чтобы сделать правую часть неравенства как можно меньше, является проблемой, обсуждаемой ниже. использованный в процессе деформации в предыдущем доказательстве. Из формулы видно, что верхняя граница после вывода очень нечеткая, и верхняя граница будет получена только при отсутствии пересечения М событий, т. е. до тех пор, пока «есть ах, для h, D — ПЛОХАЯ выборка», то мы определяем, что это ПЛОХАЯ выборка (аналогично значению вето с одним голосом), то есть верхнее определение высокое

Dichotomy: Учитывая выборку D, в зависимости от того, является ли точка выборки ○ или × (представляющая E_in1 или 0) для их классификации, если результат классификации линейно разделим (для разделения ситуации можно использовать определенное h), то такая ситуация называется дихотомией (дихотомия/деление, что эквивалентно делению всех h на H по разным результатам линейной классификации группируются, или дихотомия содержит все h), которые могут разделить эту ситуацию; все деления на D образуют множество дихотомии

Growthfunction: Для определенного значения N можно взять много выборок размера N и соответственно много наборов дихотомий Максимальный размер этих наборов определяется как функция роста Функция роста: m(N)

Пока что ситуация с M->∞, кажется, немного улучшилась, мы надеемся заменить M на m(N), а из (A) формулы (B) формулы

(B)

Привязка ВК:На самом деле, невозможно напрямую заменить M на m(N), а (B) нельзя использовать. Внесите небольшие изменения, чтобы правильно вывести формулу (B'), т. е. связать VC.

(Б')

Ограничивающая функция:Функция верхнего предела функции роста, обозначаемая как B(N,k)

Получена верхняя граница (N) верхней границы (граничной функции) верхней границы (функции роста)^k-1)

В этот момент (B') можно продолжить вывод, и граница VC может быть переписана как

… (C)

До сих пор было доказано, что без учета M [при условии, что k существует и N достаточно велико] для любого h в H, E_in≈ Е_out

▲VC dimension

Shatter: m(N) не более 2^N, м(Н)=2^NПри вызове H "расколоть" (разбить) эти N точек (до определенного D)

Точка останова:Пусть для H m(N)≠2^NУстановленное минимальное значение N, обозначаемое как k (для определенного D)

Используйте игру о борьбе с монстрами и прохождении уровней, чтобы понять вышеприведенные понятия: m(N) — дробовик, H — игрок, на каждом уровне (уровень N) у игрока m(N) пуль, обращенных в сторону 2.^NМонстр должен быть застрелен и разбит вдребезги всех монстров, чтобы пройти уровень; когда N постепенно увеличивается с 1, m(N) впервые на N-м уровне меньше 2^N, игрок не может сбросить всех монстров, игра сломана, этот N-й уровень является точкой останова

VCdimension:Для H выполняется условие m(N)≠2^NНаибольшее значение N, обозначаемое как d_VC(для всех D размера N)

① VCdimension = k-1

② N≤d_VCПри , хотя бы один D разрушен, N≥d_VC, никакое D не может быть разрушено

Значение (не легко понять)

(1) Для D-персептрона размерность его параметра гипотезы равна d+1 (пороговое значение равно размерности 0, возьмем w₀=1, весовой векторw(w₀,w₁,w₂,w₃, ..., w_d)), это похоже на то, что набор гипотез имеет d+1 ручек, представляющих его степени свободы, а для D-PLA d_VC=d+1 (процесс доказательства можно рассмотреть внимательно), то есть d_VCАссоциируется с Эффективными «бинарными» степенями свободы множества гипотез; можно также сказать, что d_VCОтражая мощь H, d_VCЧем больше значение, тем мощнее набор гипотез, то есть он может разбить больше точек и более точно разделить данные.

Чтобы быть более общим, d_VCс предполагаемыми параметрамиwКоличество свободных переменных примерно равно...

(2) Замените k-1 в (C) на d_VC, можно вывести, что

Ω(N, H, δ) называется штрафом за сложность модели, ценой, которую должен заплатить набор гипотез, как показано на рисунке ниже (d_VCДело не в том, что чем больше, тем лучше, чем мощнее, тем выше цена ошибки)

(3) Еще один смысловой уровень — сложность выборки.

Подсчитано, что требуемый размер выборки обычно составляет N≈10d._VC