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

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

Версия 21:36, 24 сентября 2008

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

Можно привести задачи, где первая причина дает значения от 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)

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

Заметим, что в случае «нулевой гипотезы» (когда распределения обоих классов совпадают, как и их априорные вероятности, и вероятность ошибки для любого классификатора равна 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)