4.1. Скользящий контроль - MachineLearning (2015 Лекции (Майсурадзе))

08.04.2015Скользящий контрольСкользящий контрольМатериал из MachineLearning.(Перенаправлено с Кросс­валидация)Скользящий контроль или кросс­проверка или кросс­валидация (cross­validation, CV) — процедура эмпирического оценивания обобщающейспособности алгоритмов, обучаемых по прецедентам.Фиксируется некоторое множество разбиений исходной выборки на две подвыборки: обучающую и контрольную. Для каждого разбиения выполняетсянастройка алгоритма по обучающей подвыборке, затем оценивается его средняя ошибка на объектах контрольной подвыборки. Оценкой скользящегоконтроля называется средняя по всем разбиениям величина ошибки на контрольных подвыборках.Если выборка независима, то средняя ошибка скользящего контроля даёт несмещённую оценку вероятности ошибки. Это выгодно отличает её от среднейошибки на обучающей выборке, которая может оказаться смещённой (оптимистически заниженной) оценкой вероятности ошибки, что связано с явлениемпереобучения.Скользящий контроль является стандартной методикой тестирования и сравнения алгоритмов классификации, регрессии и прогнозирования.Содержание1 Определения и обозначения1.1 Процедура скользящего контроля1.2 Доверительное оценивание1.3 Стратификация2 Разновидности скользящего контроля2.1 Полный скользящий контроль (complete CV)2.2 Случайные разбиения2.3 Контроль на отложенных данных (hold­out CV)2.4 Контроль по отдельным объектам (leave­one­out CV)2.5 Контроль по q блокам (q­fold CV)2.6 Контроль по r×q блокам (r×q­fold CV)3 Скользящий контроль в задачах прогнозирования3.1 Контроль при нарастающей длине обучения3.2 Контроль при фиксированной длине обучения4 Недостатки скользящего контроля5 Применения скользящего контроля6 Примечания7 ЛитератураОпределения и обозначенияРассматривается задача обучения с учителем.Пусть  — множество описаний объектов, Задана конечная выборка прецедентов Задан алгоритм обучения — отображение . — множество допустимых ответов.., которое произвольной конечной выборке прецедентов  ставит в соответствие функцию (алгоритм) Качество алгоритма   оценивается по произвольной выборке прецедентов  с помощью функционала качества контроля не важно, как именно вычисляется этот функционал. Как правило, он аддитивен по объектам выборки:где  — неотрицательная функция потерь, возвращающая величину ошибки ответа алгоритма . Для процедуры скользящего при правильном ответе .Процедура скользящего контроляВыборка длины m,  разбивается   различными способами на две непересекающиеся подвыборки:  — контрольная подвыборка длины ,  — номер разбиения., где Для каждого разбиения n строится алгоритм  и вычисляется значение функционала качества значений   по всем разбиениям называется оценкой скользящего контроля: — обучающая подвыборка. Среднее арифметическоеРазличные варианты скользящего контроля отличаются видами функционала качества и способами разбиения выборки.Доверительное оцениваниеКроме среднего значения качества на контроле строят также доверительные интервалы.http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D1%80%D0%BE%D1%81%D1%81­%D0%B2%D0%B0%D0%BB%D0%B8%D0%B4%…1/408.04.2015Скользящий контрольНепараметрическая оценка доверительного интервала. Строится вариационный ряд значений , Утверждение 1. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью  не превосходит : значение случайной величины .Следствие 1. Значение случайной величины  не превосходит  с вероятностью В частности, для получения верхней оценки с надёжностью 95% достаточно взять  разбиений.Утверждение 2. Если разбиения осуществлялись случайно, независимо и равновероятно, то с вероятностью  не выходит за границы доверительного интервала Следствие 2. Значение случайной величины . значение случайной величины . не выходит за границы вариационного ряда В частности, для получения двусторонней оценки с надёжностью 95% достаточно взять  с вероятностью . разбиений.Параметрические оценки доверительного интервала основаны на априорном предположении о виде распределения случайной величины .Если априорные предположения не выполняются, доверительный интервал может оказаться сильно смещённым. В частности, если предположения онормальности распределения не выполнены, то нельзя пользоваться стандартным «правилом двух сигм» или «трёх сигм». Джон Лангфорд в своейдиссертации (2002) указывает на распространённую ошибку, когда правило двух сигм применяется к функционалу частоты ошибок, имеющему на самомделе биномиальное распределение. Однако биномиальным распределением в общем случае тоже пользоваться нельзя, поскольку в результате обучения послучайным подвыборкам  вероятность ошибки алгоритма  оказывается случайной величиной. Следовательно, случайная величина описывается не биномиальным распределеним, а (неизвестной) смесью биномиальных распределений. Аппроксимация смесибиномиальным распределением может приводить к ошибочному сужению доверительного интервала. Приведённые выше непараметрические оценкилишены этого недостатка.СтратификацияСтратификация выборки — это способ уменьшить разброс (дисперсию) оценок скользящего контроля, в результате чего получаются более узкиедоверительные интервалы и более точные (tight) верхние оценки.Стратификация заключается в том, чтобы заранее поделить выборку на части (страты), и при разбиении на обучение длины m и контроль длины kгарантировать, что каждая страта будет поделена между обучением и контролем в той же пропорции .Стратификация классов в задачах классификации означает, что каждый класс делится между обучением и контролем в пропорции .Стратификация по вещественному признаку. Объекты выборки сортируются согласно некоторому критерию, например, по возрастанию одного изпризнаков. Затем выборка разбивается на k последовательных страт одинаковой (с точностью до 1) длины. При формировании контрольных выборок изкаждой страты выбирается по одному объекту, либо с заданным порядковым номером внутри страты, либо случайным образом.Разновидности скользящего контроляВозможны различные варианты скользящего контроля, отличающиеся способами разбиения выборки.Полный скользящий контроль (complete CV)Оценка скользящего контроля строится по всем Частный случай при  разбиениям. В зависимости от   (длины обучающей выборки) различают: — контроль по отдельным объектам (leave­one­out CV);Было показано (Li,1987) , что контроль по отдельным объектом является асимптотически оптимальным при некоторых условиях[1], то есть: по вероятности,где:1. 2.  ­ класс сравниваемых моделей; ­ среднеквадратичная ошибка при выборе 3. ­ой модели;.Общий случай при . Здесь число разбиений  становится слишком большим даже при сравнительно малых значениях  , что затрудняетпрактическое применение данного метода. Для этого случая полный скользящий контроль используется либо в теоретических исследованиях(Воронцов,2004), либо в тех редких ситуациях, когда для него удаётся вывести эффективную вычислительную формулу. Например, такая формулаизвестна для метода k ближайших соседей [1], что позволяет эффективно выбирать параметр k. На практике чаще применяются другие разновидностискользящего контроля.Случайные разбиенияРазбиения  выбираются случайно, независимо и равновероятно из множества всех  разбиений. Именно для этого случая справедливыприведённые выше оценки доверительных интервалов. На практике эти оценки, как правило, без изменений переносится и на другие способы разбиениявыборки.http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D1%80%D0%BE%D1%81%D1%81­%D0%B2%D0%B0%D0%BB%D0%B8%D0%B4%…2/408.04.2015Скользящий контрольКонтроль на отложенных данных (hold­out CV)Оценка скользящего контроля строится по одному случайному разбиению, .Этот способ имеет существенные недостатки:1.  Приходится слишком много объектов оставлять в контрольной подвыборке. Уменьшение длины обучающей подвыборки приводит к смещённой(пессимистически завышенной) оценке вероятности ошибки.2.  Оценка существенно зависит от разбиения, тогда как желательно, чтобы она характеризовала только алгоритм обучения.3.  Оценка имеет высокую дисперсию, которая может быть уменьшена путём усреднения по разбиениям.Следует различать скользящий контроль по отложенным данным и контроль по тестовой выборке. Если во втором случае оценивается вероятность ошибкидля классификатора, построенного по обучающей подвыборке, то в первом случае ­ для классификатора, построенного по полной выборке (то есть доляошибок вычисляется не для того классификатора, который выдается в качестве результата решения задачи).Контроль по отдельным объектам (leave­one­out CV)Является частным случаем полного скользящего контроля при скользящего контроля., соотвественно, . Это, пожалуй, самый распространённый вариантПреимущества LOO в том, что каждый объект ровно один раз участвует в контроле, а длина обучающих подвыборок лишь на единицу меньше длиныполной выборки.Недостатком LOO является большая ресурсоёмкость, так как обучаться приходится   раз. Некоторые методы обучения позволяют достаточно быстроперенастраивать внутренние параметры алгоритма при замене одного обучающего объекта другим. В этих случаях вычисление LOO удаётся заметноускорить.Контроль по q блокам (q­fold CV)Выборка случайным образом разбивается на q непересекающихся блоков одинаковой (или почти одинаковой) длины :     Каждый блок по очереди становится контрольной подвыборкой, при этом обучение производится по остальным определяется как средняя ошибка на контрольной подвыборке: блокам. КритерийЭто компромисс между LOO, hold­out и случайными разбиениями. С одной стороны, обучение производится только q раз вместо L. С другой стороны,длина обучающих подвыборок, равная случайным образом на 10 или 20 блоков. с точностью до округления, не сильно отличается от длины полной выборки L. Обычно выборку разбиваютКонтроль по r×q блокам (r×q­fold CV)Контроль по q блокам (q­fold CV) повторяется r раз. Каждый раз выборка случайным образом разбивается на q непересекающихся блоков. Этот способнаследует все преимущества q­fold CV, при этом появляется дополнительная возможность увеличивать число разбиений.Данный вариант скользящего контроля, со стратификацией классов, является стандартной методикой тестирования и сравнения алгоритмов классификации.В частности, он применяется в системах WEKA и «Полигон алгоритмов».Скользящий контроль в задачах прогнозированияВ задачах прогнозирования, динамического обучения, обучения с подкреплением и активного обучения прецеденты изначально линейно упорядочены повремени их появления. В этом случае варианты скользящего контроля не так разнообразны.Контроль при нарастающей длине обученияОбучающая подвыборка образуется всеми прошлыми объектами , где . Контрольная подвыборка образуется всеми будущими объектами  — величина зедержки прогнозирования (обычно ). Момент «настоящего времени» n «скользит» повыборке данных:где  — минимальная длина обучающей выборки, требуемая для нормальной работы алгоритма обучения , .Поскольку длина обучения  увеличивается со временем, точность прогнозов может постепенно улучшаться. Этот побочный эффект являетсянежелательным, если скользящий контроль применяется для оценивания качества алгоритма обучения.Контроль при фиксированной длине обученияОтличается от предыдущего варианта только тем, что длина обучения m фиксируется, ограничивась последними m прецедентами ряда: . При этом полагают .Недостатки скользящего контроля1.  Задачу обучения приходится решать N раз, что сопряжено со значительными вычислительными затратами.http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D1%80%D0%BE%D1%81%D1%81­%D0%B2%D0%B0%D0%BB%D0%B8%D0%B4%…3/408.04.2015Скользящий контроль2.  Оценка скользящего контроля предполагает, что алгоритм обучения   уже задан. Она ничего не говорит о том, какими свойствами должны обладать«хорошие» алгоритмы обучения, и как их строить. Такого рода подсказки дают, например, теоретические оценки обобщающей способности.3.  Попытка использовать скользящий контроль для обучения, в роли оптимизируемого критерия, приводит к тому, что он утрачивает свойствонесмещённости, и снова возникает риск переобучения.4.  Скользящий контроль дает несмещенную точечную, но не интервальную оценку риска. В настоящее время не существует методов построения наоснове скользящего контроля точных доверительных интервалов для риска, то есть математического ожидания потерь (в частности, вероятностиошибочной классификации).Применения скользящего контроляНа практике скользящий контроль применяется для оптимизации некоторых критически важных параметров, как правило, определяющих структуру илисложность используемой модели алгоритма, и имеющих относительно небольшое число возможных значений.Примеры:Выбор модели алгоритмов из небольшого множества альтернативных вариантов.Оптимизация параметра регуляризации, в частности:параметра регуляризации в гребневой регрессии;параметра сокращения весов (weight decay) в нейронных сетях;параметра C в методе опорных векторов.Оптимизация ширины окна в методахпарзеновского окна;ближайшего соседа;ядерного сглаживания.Оптимизация числа нейронов в скрытом слое многослойной нейронной сети.Выбор информативного набора признаков.Редукция решающего дерева.Структурная минимизация риска.ПримечанияЛитература1.  Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов. — Математические вопросы кибернетики / Под ред. О. Б.Лупанов. — М.: Физматлит, 2004. — T. 13. — С. 5–36.2.  Эфрон Б. Нетрадиционные методы многомерного статистического анализа. — М: Финансы и статистика. — 1988.3.  Langford J. Quantitatively Tight Sample Complexity Bounds (http://citeseer.ist.psu.edu/langford02quantitatively.html) . — Carnegie Mellon Thesis. — 2002. —124 с.4.  Kohavi R. A Study of Cross­Validation and Bootstrap for Accuracy Estimation and Model Selection (http://citeseer.ist.psu.edu/kohavi95study.html) . — 14thInternational Joint Conference on Artificial Intelligence, Palais de Congres Montreal, Quebec, Canada. — 1995. — С. 1137­1145.5.  Mullin M., Sukthankar R. Complete Cross­Validation for Nearest Neighbor Classifiers (http://citeseer.ist.psu.edu/309025.html) . — Proceedings of InternationalConference on Machine Learning. — 2000. — С. 1137­1145.Это незавершённая статья. Вы поможете проекту, исправив и дополнив (http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B8%D0%B9_%D0%BA%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%её.Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B8%D0%B9_%D0%BA%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%Категории: Незавершённые статьи | Машинное обучениеПоследнее изменение этой страницы: 16:25, 15 февраля 2010.Содержимое доступно в соответствии с Creative Commons Attribution/Share­Alike.http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D1%80%D0%BE%D1%81%D1%81­%D0%B2%D0%B0%D0%BB%D0%B8%D0%B4%…4/4.