Это 19-й день моего участия в августовском испытании обновлений.Подробности о событии:Испытание августовского обновления
Эффективное количество гипотез
Давайте вспомним, откуда это м. Обратите внимание, что уравнение M -те встречает плохое образец в качестве события, то вероятность возникновения плохого образца является совместная вероятность всех уравнений, возникающих плохой образец. Если каждое уравнение сталкивается с плохой образец, который не зависит друг от друга, вероятность возникновения плохого образца является сумма вероятностей каждого уравнения, встречающегося с плохой образец, поэтому их совместная вероятность должна быть меньше или равна сумме вероятности каждого события, происходящего по отдельности и.
Но на самом деле плохие события не являются полностью независимыми. Представьте себе два очень похожих уравнения.Они сталкиваются с плохими образцами, и они являются событиями, и, поскольку эти два уравнения очень близки, они часто возникают, когда они происходят.Можно сказать, что совпадение и очень велико (перекрытие).
Затем мы подумаем, можем ли мы рассматривать эти уравнения с похожими результатами как класс, например, некоторые уравнения, результаты предсказания которых всегда одинаковы или очень близки.
Предположим, что наш алгоритм состоит в том, чтобы выбрать уравнение прямой линии на плоскости как , существует бесконечно много уравнений, но мы можем сгруппировать эти уравнения в две категории. Один должен судить как круг, а другой — как вилку.
Что делать, если у нас есть сумма 2 точек данных? При этом бесконечное количество прямых можно разделить на 4 категории. Прогнозирование суммы этих 4 типов линий дает в общей сложности 4 разных результата.
Что, если у нас есть 3 точки данных, сумма?
В существует не более 8 типов прямых линий, которые действуют на вышеупомянутые 8 типов результатов.
Что, если бы у нас в руках было 4 точки данных~. В предыдущем примере мы в основном объединили условия каждой точки данных путем перестановки и комбинации. А вот для более чем 4 баллов это не так просто.
Из этих 16 комбинаций две являются результатами, которые «уравнение прямой линии» не может дать. Следовательно, если это все прямые линии в 2-мерном пространстве на поверхности, кажется, что они выбраны из бесчисленных уравнений прямых, но поскольку результаты, порождаемые большинством уравнений прямых, совершенно одинаковы, категории прямых линии с разными результатами соответствуют приведенным выше примерам соответственно Классу 2, Классу 4, Классу 8 и Классу 14 (Эффективное количество линий). Строки, принадлежащие одному и тому же классу, будут встречать или не встречать плохие выборки одновременно.Поскольку предыдущая граница объединения основана на предположении о независимости, вероятность встречи с плохими выборками явно преувеличена. Итак, мы должны переписать неравенство в виде:
Сколько различных результатов можно получить, воздействуя на него? (дихотомии)
Выберите из него любое уравнение, пусть пара выполнит бинарную классификацию и выведет результирующий вектор, например, предсказывает и выводит 4 балла.Такой выходной вектор мы называем дихотомией. Нетрудно заключить, что уравнению прямой соответствует дихотомия в , а дихотомии соответствует хотя бы одно уравнение прямой. Мы рассматриваем все уравнения прямых, соответствующие дихотомии, как один тип, тогда эффективное число прямых равно равно количеству различных дихотомий в разных . Очевидно, что количество дихотомий меньше или равно количеству перестановок и комбинаций всех точек данных.Например, перестановка и комбинация, соответствующие изображению с большим крестом на приведенном выше рисунке, не могут быть дихотомией, потому что они не могут быть порождена любым уравнением прямой линии. (Конечно, если вы не рассматриваете уравнение прямой линии, то перестановка и комбинация могут стать дихотомией)
Итак, что мы искали
= сколько разных типов прямых можно найти на плоскости
= Действует в зависимости от того, сколько различных дихотомий может быть получено.
Поскольку не все перестановки и комбинации могут стать дихотомиями, количество различных дихотомий не должно превышать количество перестановок и комбинаций, В приведенном выше примере, если три точки лежат на одной прямой, количество дихотомий будет меньше, поэтому:
= действует на "самый«Сколько различных дихотомий можно произвести
Функция роста
Тогда, действуя на "самый«Сколько различных дихотомий можно сгенерировать? Это число связано с объемом данных. Его можно выразить математически как:
Приведенная выше формула также называется функцией роста. В детерминированном случае функция роста является функцией, связанной с N. Ниже приведены функции роста нескольких распространенных наборов гипотез.
- Positive Rays
Входное пространство является одномерным действительным числовым пространством. Прогнозы выше порога a +1, в противном случае -1. Например: Когда N=4, Положительные Лучи воздействуют на ~, что в сумме может привести к 5 различным дихотомиям. Как показано ниже:
Об этом нетрудно подумать, 4 точки, 5 возможных точек отсечения и максимум 5 дихотомий. Итак, функция роста Positive Rays: - Positive Intervals
Аналогичен предыдущему, за исключением того, что Положительные интервалы имеют два порога, а предсказание между двумя порогами равно +1, а остальные предсказания равны -1. Например: Когда N=4, Положительные интервалы воздействуют на ~, что может дать всего 11 дихотомий. Как показано ниже:
Также нетрудно подумать о 4 точках и 5 возможных точках касания, чтобы выбрать две в качестве порога, плюс одна, созданная совпадением двух порогов, поэтому функция роста положительных интервалов: - Convex Sets
Выберите любые k точек, и все точки внутри выпуклого многоугольника, окруженного этими k точками, прогнозируются +1, в противном случае прогнозируется -1. Ранее мы говорили, что описанная функция роста имеет вид «самый«Количество дихотомий, которые могут быть сгенерированы, поэтому, если наши N входных данных помещены в круг, любая перестановка и комбинация этих N точек может стать дихотомией. Следовательно, функция роста выпуклых множеств:
Сломанный дробовик (Shatter & Break)
Применительно к N входным данным количество сгенерированных дихотомий равно количеству перестановок и комбинаций N точек, мы говорим, что N входных данных отбрасываются при разрушении. Или можно сказать, что сгенерированные дихотомии объединяют перестановки N точек вдребезги.
Значение этого осколка кажется трудным для понимания.Это ответ Учителя Лин в области обсуждения:
«Обсуждение точки останова хорошо, но обратите внимание, что первоначальное значение слова «разбить» — «сломать», что здесь означает «генерируются все (фрагментированные) возможные случаи N точек». Так что ситуация "разбитая". "
Я понимаю это с точки зрения игры и разрушения:
«Это дробовик. На каждом уровне (уровень N) у него могут быть маленькие пули (каждая маленькая пуля соответствует дихотомии), и вы сталкиваетесь с врагом. Вы должны выстрелить осколком, чтобы убить всех людей. Для этого дробовика , первый и второй уровни в порядке, третий уровень 6 маленьких пуль разбивается, не может уронить 8 человек, поэтому он ломается».
Для заданной функции роста от начальной точки N постепенно увеличивается, а когда она увеличивается до k, возникает ситуация, то мы говорим, что k является точкой излома функции роста, При любом входе нет пути дальнейшего разбить их.
В соответствии с функцией роста нетрудно сделать вывод, что точка излома функции роста положительных лучей равна 2, точка излома функции роста положительных интервалов равна 3, а выпуклые наборы могут разбиться, чтобы сбросить N точек независимо от размера N, поэтому его функция роста не имеет точки разрыва. Точка останова двумерных персептронов равна 4, потому что при N = 3 он может разрушаться и генерировать дихотомии, а при N = 4 он не может разрушаться и может генерировать максимум 14 () типов дихотомий, поэтому функция роста двумерных персептронов Точка останова 4.
Что взять с собой в функцию роста города (ограничение точки останова)
Некоторые функции роста легко найти, такие как Положительные лучи, Положительные интервалы и Выпуклые множества, упомянутые выше; некоторые не так просто, например, двумерные персептроны, мы не можем напрямую увидеть, какова их функция роста, поэтому мы не будем? Не совсем, по крайней мере, у нас все еще есть точка останова, можем ли мы использовать эту точку останова, чтобы что-то сделать? Если нет способа получить функцию роста, также хорошо получить верхнюю границу функции роста.
Сначала возьмем пример. Когда мы вообще не знаем, что это такое, а знаем только точку излома k, он действует на "самое большее«Сколько таких дихотомий можно составить. Обратите внимание, что здесь я использовал две»самый", так как мы не можем точно знать функцию роста, количество дихотомий, которые мы выводим с этой точкой излома, все еще является завышенной оценкой, эта завышенная оценка на самом деле является фактическим количеством дихотомий, создаваемых любой точкой излома k верхней границы .
Например, предположим, что мы не знаем некоторую функцию роста, но знаем ее точку излома k=2, тогда при воздействии на N=3 "самое большее«Сколько дихотомий можно составить?
Из k=2 мы можем знать, что любые 2 точки данных не могут быть разрушены. Помните концепцию разрушения? Это означает, что дихотомии, которые я генерирую, не могут содержать все перестановки и комбинации любых двух точек данных. Начнем с 1 дихотомии.
1 dichotomy
2 dichotomies
3 dichotomies
Посмотрите на эти два столбца, эти 3 дихотомии уже содержат 3 из 4 перестановок этих двух точек. Добавьте еще один, и вы будете разбиты.
4 dichotomies
Посмотрите на две колонки справа, и был разбит. Но я уже говорил, что k=2, то есть любые 2 точки не могут быть разрушены, поэтому невозможно сгенерировать эти 4 дихотомии. Тогда давайте попробуем другую дихотомию.
4 dichotomies
Просто измените дихотомию. 2 столбца справа содержат только 3 из 4 типов перестановок и комбинаций, поэтому эти две точки не разбиваются. Продолжайте проверять, что любые две точки (,), (,) не разбиты.Кажется, что эти 4 дихотомии в порядке.
Случай 5 дихотомий здесь больше не рисуется.Легко видеть, что независимо от того, какая дихотомия добавлена, две точки будут разрушены. Так вот "самое большее«Может быть только 4 дихотомии. Следовательно, верхняя граница равна 4. Мы используем для обозначения верхней границы числа дихотомий, которые могут быть порождены любым действием с точкой излома k, действующей на любой размер N («самое большее"). Тогда только что сделанный вывод может быть выражен как, потому что любые 2 точки данных не могут быть разрушены, поэтому в то время, самое большее, существует.
Чудесная часть скоро появится.Хотя часто мы не можем получить функцию роста напрямую, если мы знаем, какова ее точка излома, у нас, похоже, есть способ вычислить ее верхнюю границу. Итак, у нас появилась новая цель — не учиться напрямую, а учиться.
Мы уже знаем это ранее. Нетрудно узнать:
- При , нет возможности разбить на 1 балл (2 перестановки и комбинации), поэтому он всегда равен 1.
- При , он должен иметь возможность разрушить точку, поэтому тип порождаемых им дихотомий равен количеству всех перестановок и комбинаций этой точки.
- , удалите одну из перестановок, а остальные можно использовать как дихотомии, отсюда и количество дихотомий, которые он производит».самое большее"Возможно.
Таким образом, мы можем получить следующую таблицу:
Как заполнить оставшуюся часть таблицы? Это связано с?
В это время аспирант, помогавший учителю подбросить монетку в лаборатории некой лаборатории, собирается играть, он перебрал все возможные дихотомии и обнаружил, что результаты его исследования следующие:
Сортируем этот результат:
Вы нашли секрет?Оранжевые части появляются парами, и только фиолетовые части появляются по отдельности:
- Если вы удалите его, просто посмотрите на эти 3 точки:
Части могут стать дихотомиями этих 3 точек, потому что любые 3 точки не могут быть разбиты на части, поэтому существуют: - Посмотрим на оставшуюся часть:
Обратите внимание, что это часть, которая существовала парами ранее, и эта часть не может разрушить любые 2 точки, потому что, если дихотомии части могут разрушить любые 2 точки, каждая линия сопоставляется с двумя случаями, так что сгенерированные дихотомии могут быть Shatter потерял 3 очка, что противоречит брейк-пойнту 3. Таким образом, осколки не могут сбросить никакие 2 очка. Итак, есть:
Комбинируя два предыдущих неравенства, мы можем получить:
Это завершит предыдущую форму:
Доказывается методом математической индукции:
Неравенство всегда устанавливается в это время, поэтому обсуждается только случай. При выполняется неравенство, а если выполняются все неравенства, то нужно доказать выполнение неравенств. Согласно предыдущим выводам, существуют: