Обсуждение:Комбинаторная теория переобучения (виртуальный семинар)

Материал из MachineLearning.

Комментарий по степени завышенности

Можно привести задачи, где первая причина дает значения от 1 до бесконечности (значение 1 — для алгоритмов полного перебора классификаторов, бесконечность — например, для метода k>1 ближайших соседей), вторая - от 2-х, т.е есть конструктивные примеры, где суммарно они дают всего 2 (и даже меньше). Исследованный пример, где получен такой результат, правда, является практически мало значимым — это классификация в дискретном пространстве, когда в каждой точке пространства решение принимается изолированно (на основе тех прецедентов, что попали в эту точку). Однако вероятно можно найти и более актуальные примеры с малой степенью завышенности.— Nvm 07:48, 24 сентября 2008 (MSD)

• ...значение 1 для алгоритмов полного перебора классификаторов — по-моему это ошибочное суждение. Из-за него я и перенёс данный комментарий сюда, в обсуждение. «Полнота перебора» никак не связана с расслоением. Даже если делается полный перебор, некоторые алгоритмы могут всё же никогда не выбираться в результате обучения по выборке. В эксперименте с цепочками выбор лучшего алгоритма из цепочки делался как раз полным перебором. Значение 1 будет наблюдаться у семейств (почти) без расслоения, то есть когда все алгоритмы обладают (почти) одинаковым качеством относительно данной задачи. Однако эта ситуация представляется довольно искусственной. Это либо семейство алгоритмов, «сильно заточенное» под данную конкретную задачу (хорошая «физическая» модель целевой зависимости), либо «случайное гадание» с уровнем ошибок 50%. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)
• Бесконечность ёмкости kNN — не очень удачный пример; ясное дело, что выяснять причины завышенности Вапниковской оценки здесь бесполезно. К тому же, есть другие оценки для kNN, например, основанные на стабильности метода обучения. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)

Сформулированная в статье первая причина завышенности включает два разных эффекта. Первый - это расслоение: поскольку классификаторы имеют разную вероятность ошибки, то и уклонение нужно "отсчитывать" для каждого от своей вероятности, а не от одной величины, как у В-Ч. Второй эффект имеет место для методов обучения, осуществляющих направленный поиск, который не гарантирует нахождение лучшего классификатора в классе. В этом случае фактическая емкость используемого в среднем подкласса будет меньше формальной емкости класса решающих функций. Пример с kNN приведен как иллюстрация того, как метод обучения не использует максимальную емкость класса. Второй эффект не имеет места в частности для методов полного перебора. Первый отсутствует, если вероятность ошибки для лучшего классификатора в классе близка к 0,5 - это возможно, если класс выбран неудачно (даже если классификация возможна). - Nvm 12:05, 25 сентября 2008 (MSD)

Учёт эффекта расслоения улучшает оценки только в области малых рисков

Заметим, что в случае «нулевой гипотезы» (когда распределения обоих классов совпадают, как и их априорные вероятности, и вероятность ошибки для любого классификатора равна 0.5) эффект расслоения не имеет места. Поскольку оценки должны быть справедливы для любых распределений, можно ожидать за счет учета расслоения улучшения оценок в области малых, но не больших рисков. Это подтверждается исследованием модельной дискретной задачи, где вычисленная точно погрешность оценок В-Ч была тем больше, чем меньше риск. — Nvm 08:27, 24 сентября 2008 (MSD)

• ...можно ожидать за счет учета расслоения улучшения оценок в области малых рисков. Да, конечно. Практически интересны как раз случаи малых вероятностей ошибочной классификации, ведь именно этого мы и добиваемся! Алгоритм с 45% ошибок вряд ли будет представлять интерес, особенно если вполне реально построить алгоритм с 5% ошибок. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)
• Если вероятность ошибки для любого классификатора равна 0.5, то эффект расслоения не имеет места. Да, конечно. Однако это надуманная ситуация; искусственный контрпример, не имеющий отношения ни практике, ни к теории классификации. На практике мы пытаемся уйти от таких семейств алгоритмов, причём уйти от них чрезвычайно просто — достаточно взять любую хоть немного разумную эвристику, отличную от «случайного гадания». Зачем вообще такие ситуации брать в расчёт? На практике эффект расслоения возникает всегда, когда в семействе алгоритмов находятся алгоритмы как хорошие, так и плохие относительно заданной выборки. По-моему нельзя привести пример практической задачи и «разумного» семейства, когда дело обстояло бы не так. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)
• ...оценки должны быть справедливы для любых распределений. Это спорное утверждение, из-за которого я перенёс данный комментарий в сюда, в обсуждение. Какие именно оценки имелись в виду? Почему так строго — «должны»? Может, это относится только к старым оценкам вапниковского типа? Сейчас представляют интерес только data-dependent bounds; всем уже стало очевидно, что только учёт всей доступной информации (о свойствах выборки, целевой зависимости, семейства алгоритмов и метода обучения) позволяет получить численно точные оценки. Иначе, как в теории ВЧ — исследуем абстрактный «наихудший случай», который в жизни не встречается. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)
• Слова «распределения классов» на странице данного семинара считаю вообще неуместными, т.к. здесь вероятностная (байесовская) парадигма не вводится. Легко привести пример, когда абсолютное большинство известных стат.тестов скажут, что классы имеют одинаковое распределение, тем не менее, они хорошо разделимы, и некоторые (логические) методы обучения вполне способны обнаружить целевую зависимость; особенно, если внести некоторую априорную информацию о задаче в виде требования «искать периодические структуры». Этот пример — шахматная доска: чёрные клетки — один класс, белые клетки — второй, и выборка (допустим, из равномерных распределений) не так велика, скажем, по 50 объектов каждого класса. Если использовать «разумные» семейства, то эффект расслоения, конечно же, и здесь будет иметь место. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)
• По поводу байесовской теории классификации (раз уж к слову пришлось). Утверждение «Байесовский классификатор оптимален» вводит в заблуждение неискушённых людей. На практике приходится восстанавливать плотность по выбоке, а это можно сделать только приближённо, и только приняв какие-то гипотезы о виде плотностей. Именно при восстановлении плотностей возникает переобучение, кроме того, модель плотности обязательно будет иметь хоть какое-то смещение. В результате классификатор перестаёт быть оптимальным. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)
• Это подтверждается исследованием модельной дискретной задачи. — Если есть ссылка на статью, то её надо дать. Можно создать отдельный семинар об этих исследованиях, поскольку их проблематика отлична от исследования расслоения и различности. Кстати, тексты статей вполне можно загружаь в эту вики как файлы. — К.В.Воронцов 01:34, 25 сентября 2008 (MSD)

Проверка нулевой гипотезы и вероятностная постановка

Почему оценки должны быть справедливы для любых распределений. Вполне можно допустить, что иногда бывает априорно известно, что существует классификатор с небольшим числом ошибок и известно, какого он вида (семейства). Но все же гораздо чаще такой априорной уверенности нет, и именно на основе анализа выборки нужно установить, можно ли вообще классифицировать объекты с приемлемой точностью, и если можно, то как.

"Справедливы для любых распределений" означает, в частности (и главным образом), следующее. Пусть есть какая-то оценка вероятности ошибки. В конечном счете это некоторая функция выборки (например, отклонение от эмпирического риска). Возьмем равномерное распределение в признаковом пространстве, одинаковое для обоих классов (нулевая гипотеза) и сгенерируем из него большое число выборок. Для большинства выборок исследуемая оценка вероятности ошибки должна быть около 0,5. Иначе это ошибочная оценка.

Вероятностная парадигма (постановка) в задаче классификации далеко не то же, что "байесовская теория классификации". Вторая - даже не частный случай первой, а подход к решению задач в рамках первой. На мой взгляд, вместо "байесовская теория классификации" точнее говорить "подход к решению задач классификации, основанный на явной аппроксимации распределений" (будет меньше заблуждений у неискушенных людей).

Кроме "байесовской теории классификации" целиком в вероятностной парадигме построена и теория Вапника-Червоненкиса. Поэтому, на мой взгляд, говорить о распределениях в рамках данного семинара как раз оправдано.