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

Материал из 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)

• ...В этом случае фактическая емкость используемого в среднем подкласса будет меньше формальной емкости класса решающих функций ... эффект не имеет места в частности для методов полного перебора.
  По поводу этой мысли согласен с Константином - даже при полном переборе не обязательно в результате обучения будут получаться все алгоритмы из семейства, так что мысль, кажется, неверная. Видимо произошло смешение - множества алгоритмов из которого метод поиска производит выбор(это может быть все семейство алгоритмов) и множества алгоритмов, которые могут получаться в результате обучения на всех возможных конечных обучающих выборках - именно по последнему множеству в оценке делается union bound. Kochede 17:34, 8 мая 2009 (MSD)
  • Для методов полного перебора емкость используемого подкласса по определению равна емкости класса решающих функций, поскольку емкость - это не общее число классификаторов, а число классификаторов, различимых (а это значит, что и достижимых при различных назначениях классов выборочным точкам) на "наиболее информативной" выборке заданного объема. Nvm 17:27, 11 мая 2009 (MSD)
    • ..различимых (а это значит, что и достижимых при различных назначениях классов выборочным точкам
      Вроде бы не значит. Метод обучения не обязательно выбирает алгоритм с минимальной эмпирической ошибкой из всех перебранных им алгоритмов. Cовместно с эмпирической ошибкой алгоритма могут оцениваться простота алгоритма, его лучшее соответствие априорным знаниям о целевой зависимости и прочее и прочее. Такой метод обучения даже при полном переборе будет выдавать в результате обучения по всевозможным разметкам обучающей выборки не все возможные алгоритмы, а только их небольшое подмножество. Kochede 17:36, 13 мая 2009 (MSD)
      Это, конечно, так. Говоря об методе полного перебора, я имел в виду метод, минимизирующий эмпирический риск по фиксированному множеству классификаторов, полагая, что в контексте данного обсуждения такое умолчание будет понятно. Nvm 09:07, 17 мая 2009 (MSD)
• Однако, кажется, действительно есть резон в том, чтобы разделять расслоение и локализацию.
  • Расслоение алгоритмов семейства по вероятности ошибки - никак не зависит от метода поиска, это свойство семейства относительно решаемой задачи. Даже без метода поиска семейство так или иначе расслоено по вероятности ошибки, т.е. имеет профиль разнообразия.
  • Локализация же - это следствие трех причин 1) расслоенности семейства 2) того, что метод поиска обычно минимизирует эмпирический риск 3) концентрированности биномиального(или гипергеометрического) распределения. В результате этих трех причин метод обучения чаще выбирает алгоритмы с малой вероятностью ошибки и редко выбирает(или вообще не выбирает) алгоритмы с большой(>0.5) вероятностью ошибки. То есть - в результате обучения получается не все семейство, а часть - то есть и union bound в оценке можно делать только по части семейства - это и есть локализация.
    • В результате обучения получается не семейство, а ровно один классификатор. Эффект локализации имеет место, когда метод обучения не всегда находит лучшее выборочное решающее правило. ..Либо под локализацией можно понимать отличие вапниковской энтропии от емкости. Nvm 17:27, 11 мая 2009 (MSD)
      • Эффект локализации имеет место, когда метод обучения не всегда находит лучшее выборочное решающее правило.
        Метод обучения действительно не всегда выбирает алгоритм с наименьшим числом ошибок на обучающей выборке. Наверное выше я неудачно выразился 'метод поиска обычно минимизирует эмпирический риск'. Имелось ввиду, что метод обучения среди прочего обычно стремится уменьшать эмпирический риск. Kochede 17:36, 13 мая 2009 (MSD)
  • Пренебрежение эффектом расслоения это фактор№4 из исходной статьи - свертка профиля разнообразия в коэффициент разнообразия. Есть оценки, которые полностью пренебрегают эффектом локализации, но учитывают эффект расслоения, то есть не сворачивают профиль разнообразия. К примеру - Shell bound Лэнгфорда или Occam razor bound с равномерным априорным распределением на алгоритмах.
    Kochede 17:26, 8 мая 2009 (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)
• Поскольку оценки должны быть справедливы для любых распределений, можно ожидать за счет учета расслоения улучшения оценок в области малых, но не больших рисков
  Виктор, можно об этом более развернуто? С тезисом не спорю, просто не понял, если честно, как получилась гипотеза, что за счет учета расслоения оценки будут улучшаться в области малых эмпирических частот. Kochede 17:55, 8 мая 2009 (MSD)
  Гипотеза (достаточно очевидная, и практически доказанная) в том, что расслоение вообще улучшает оценки риска. При этом легко показать, что улучшения не может быть в области больших эмпирических частот. По своему определению, расслоение не имеет места при нулевой гипотезе. Если оценка дает верхнюю границу риска меньше 0,5, то она является статистическим критерием, отвергающим нулевую гипотезу. Однако любой разумный (в плане мощности) критерий, основанный на эмпирическом риске, не может отвергнуть нулевую гипотезу при большом эмпирическом риске (поскольку именно при нулевой гипотезе большие эмпирические частоты наиболее правдоподобны). Nvm 17:54, 11 мая 2009 (MSD)

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

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

• В целом согласен, но хочется уточнить. Представляют ценность «условные» оценки вида «ЕСЛИ задача обладает свойством X, ТО оценка будет такая-то, а если не обладает, то ничего сказать нельзя». Такого сорта оценки должны существовать для разных «интересных» свойств X, чтобы всегда можно было «вынуть из загашника» ту оценку, которая лучше подходит для данной задачи. Совершенно не обязательно, чтобы свойства X формулировались как предположения о распределениях. Например свойство X = «целевая зависимость является монотонной функцией таких-то признаков» совершенно незачем формулировать в вероятностных терминах — это просто неудобно. — К.В.Воронцов 20:57, 27 сентября 2008 (MSD)

• Монотонность целевой зависимости - это по сути ограничение на признаковое пространство (сужение области допустимых комбинаций значений), т.е. просто признаковое пространство особой "формы". Вероятности тут, конечно, ни при чем. Если это априорная гипотеза. Если же это свойство устанавливается апостериорно на основе анализа данных, то для его проверки можно конструировать статистические критерии - не обязательный, но разумный подход.— Nvm 18:31, 30 сентября 2008 (MSD)

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

• Проверка качества оценок по наихудшему случаю практически бесполезна. Оценки должны быть не сильно завышены (tight) в практически полезных ситуациях — вот это правильный критерий. Именно это и есть камень преткновения, за tightness оценок все и борятся.
• Уточню, в каком именно смысле «оценки НЕ должны быть справедливы для любых распределений». Среди всех распределений есть ОЧЕНЬ плохие, и оценки для них тоже ОЧЕНЬ плохие, но, к счастью, «Бог изощрён, но не злонамерен», и эти плохие распределения на практике не встречаются; так зачем принимать их в расчёт? На практике априорные гипотезы о свойствах задачи появляются на стадии предварительного анализа данных; вот тут и выясняется, что классы в некоторых метриках удовлетворяют гипотезе компактности, что «на глаз вроде есть» какие-то закономерности, что признаки имеют разную информативность, и т.д. Априорная уверенность может также следовать из того, что хороший эксперт данный тип задач всё-таки неплохо решает; значит, рассчитывать на худшие классификаторы с вероятностью ошибки 1/2 нет никакого смысла.— К.В.Воронцов 20:57, 27 сентября 2008 (MSD)

• Во многих случаях худшим распределением является "нулевая гипотеза", относительно которой договорились (выше), что априорно ее не всегда можно отвергнуть. Но более интересный факт в том, что даже самые "плохие" распределения вовсе не обязательно практически значимо влияют на оценки (замечено при построении эмпирических оценок риска). Масштабного исследования не проводил, но в навскидку исследованных практически интересных случаях (деревья решений при разумной сложности) "плохие" распределения сказывались только в области больших эмпирических рисков (что не важно), а в области малых - все определяли "хорошие" распределения. Здесь эффект в том, что оценка риска одновременно является статистическим критерием, отвергающим "плохие" распределения (и нет смысла исключать их априорно).— Nvm 18:31, 30 сентября 2008 (MSD)

• В общем случае хотелось бы измерять прямо в процессе обучения какие-то статистики, характеризующие степень соответствия задачи (выборки) и метода обучения. Это позволило бы управлять качеством алгоритма прямо в процессе обучения. С помощью таких статистических запросов (statistical queries) мы постепенно узнаём о задаче всё больше и больше, и на этом этапе уже нет никакого смысла считать, что мы имеем дело с «любым распределением»; есть смысл выжимать максимум пользы из той информации о распределении, которая накапливается по ходу обучения. А вся тяжесть задачи концентрируется в том, чтобы научиться поточнее оценивать, насколько ошибычными могут быть наши решения, принимаемые в ходе обучения по результату каждого конкретного статистического запроса — К.В.Воронцов 20:57, 27 сентября 2008 (MSD)

Зависимость точной и В-Ч оценок вероятности ошибочной классификации от эмпирического риска для дискретной модельной задачи приведена в работе PDF [500Кб]. Можно заметить, что погрешность (относительная) оценок В-Ч растет с уменьшением риска, что иллюстрирует эффект расслоения. — Nvm 14:41, 25 сентября 2008 (MSD)

Вероятностная постановка задач машинного обучения

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

• Согласен — К.В.Воронцов 20:57, 27 сентября 2008 (MSD)

Кроме "байесовской теории классификации" целиком в вероятностной парадигме построена и теория Вапника-Червоненкиса. Поэтому, на мой взгляд, говорить о распределениях в рамках данного семинара как раз оправдано. — Nvm 14:41, 25 сентября 2008 (MSD)

• Ха-ха! Основные содержательные результаты теории В-Ч легко воспроизводятся без вероятностной парадигмы, опираясь только на гипотезу независимости, без единого упоминания о плотностях распределения. Суть основных результатов В-Ч оказалась чисто комбинаторной. Причём в этих терминах теория В-Ч очищается от многих вспомогательных построений: «основной Леммы», равномерной сходимости, необходимых условий сходимости, да и просто необходимости выписывать какие-то интегралы. Всё это оказывается шелухой, и теория излагается на трёх страницах вместо 100. Явления расслоения и различности алгоритмов также представляется более удобным исследовать в рамках комбинаторной аксиоматики, т.к. задача сводится к исследованию свойств бинарной матрицы векторов ошибок «объекты—алгоритмы», а это чисто дискретный объект. — К.В.Воронцов 20:57, 27 сентября 2008 (MSD)

• Все же Вапник и Червоненкис рассматривали именно вероятностную постанову, и результаты получены в ней. Если, их технику вывода переносить на другие постановки задачи, то это будут формально уже другие результаты.

• Вот именно это меня и веселит больше всего. По словам Пойя, в любом доказательстве есть «скрытая движущая пружина», некий ключевой момент, «в который всё и происходит». Когда я проштудировал Вапника и нашёл-таки эту пружину, долго удивлялся, потому что вероятностная обёртка оказалась на порядок тяжелее собственно основного результата, причём без неё легко можно обойтись. Ценность и применимость результата при этом не страдают, зато изложение упрощается, баги становятся виднее, и можно всё померить в экспериментах. — К.В.Воронцов 20:18, 30 сентября 2008 (MSD)

• При этом в вероятностной постановке основная идея теории В-Ч излагается не на 100 и не 3-х, а на одной странице - это случай конечного множества классификаторов. Он позиционируется как предварительные рассуждения, но фактически там и изложена идея, и получена базовая формула. Интуитивно, вполне естественно ожидать, что если множество классификаторов бесконечно, но состоит из конечного числа классов эквивалентности, внутри которых различие элементов несущественно, то эта базовая оценка должна остаться справедливой. И оставшиеся 100 страниц лишь подтверждают это ожидание (правда, отчасти, поскольку при доказательстве "набегает" ухудшающий коэффициент) - но все эти построения могут в лучшем случае лишь приблизиться (возможно, совпасть) к оценкам по конечному множеству, но заведомо не превзойти их. Для исследования оценок на качественном уровне (и грубых рассуждений) можно вообще "забыть" про эти математические трудности и оперировать классами эквивалентности как конечным множеством классификаторов, не выходя таким образом за пределы первых страниц теории (и иметь дело не с гипергеометрическим распределением, а с биномиальным). Nvm 17:57, 30 сентября 2008 (MSD)

• Ага, именно это и делает Джон Лэнгфорд, доказывая то же самое, и даже в более общем виде, всего на трети страницы :) и называя этот результат скромно Occam's Razor bound. Можно работать с гипергеометрическим распределеним, а можно и с биномиальным. Это дело вкуса. Лично мне не нравится вводить понятие «вероятности ошибки», а потом измерять её как частоту. Естественнее работать только с величинами, вычислимыми непосредственно, раз уж речь идёт об анализе данных. — К.В.Воронцов 20:18, 30 сентября 2008 (MSD)

• Получается, что вероятностная интерпретация теории В-Ч не сложнее комбинаторной, и предпочтение здесь вопрос субъективный, а о вкусах не спорят. Только аргумент об "измерении" вероятности через частоту выглядит очень странно. Совершенно непонятно, что имелось в виду. Вероятность - это математическая формализация и количественная мера содержательного понятия степени неопределенности. Для ее оценивания используется весь наличный эмпирический материал, в том числе частоты определенных событий. Непонятно, где здесь не хватает непосредственности.— Nvm 23:56, 30 сентября 2008 (MSD)