Материал из MachineLearning.
На данной странице предлагается обсуждать лекции Владимира Колчинского. Одной из целью обсуждения является получение результатов, связывающих комбинаторную теорию переобучения и классическую Computational learning theory.
Данная страница не ставит целью дать краткое изложения лекций Владимира Колчинского. Перед чтением лекций рекомендуется прослушать видео-запись выступления Владимира Колчинского Bounding Excess Risk in Machine Learning (в трёх частях, суммарная длительность - порядка трёх часов).
Открытые замечания
- Стандартная оценка для excess risk выбрасывает отрицательную величину
)
, где 
--- результат минимизации эмпирического риска, 
--- минимизация true риска. Данная величина, некотором смысле, соответствует комбинаторной вероятности переобучения. Потому что данное выражение похоже на усредненное по наблюдаемой выборке значение разности между эмпирически-лучшим и реально-лучшим алгоритмом. Если задуматься, как мерять эту величину, то лучший вариант – это кросс-валидация полного скользящего контроля. Если научиться получать нижние оценки CCV в комбинаторной постановке, то возможно таким образом удалось бы уточнить оценки Кольчинского. Важно, что оценки должны быть нижними, а не верхними --- действительно, стандартная оценка выбрасывает отрицательное слагаемой, а хотелось бы не выбрасывать полностью, а только его кусочек (нижнюю оценку).
- Попытка разобраться с конфликтом в трактовке шума на
. В комбинаторной теории индикатор ошибки )
предполагается фиксированным. Таким образом неявно предполагается наличие единственного правильного ответа 
на объект 
(по крайней мере --- фиксируется некое множество правильных ответов без дальнейших обсуждений распределения вероятностей на элементах этой группы). В общепринятой постановке SLT принята другая интерпретация этого момента. Предполагается распределение 
на декартовом произведении 
. Таким образом при фиксированном объекте 
допускаются разные ответы в соответствии с условным распределением )
. В комбинаторной теории это условное распределение имеет тривиальный вид: либо =1)
, либо =0)
. В литературе этот вопрос фигурирует под графой noise condition --- шума на множестве ответов. Таким образом в комбинаторной теории принципиально возможно построение идеального классификатора, не ошибающегося ни на одном объекте, в то время как в SLT --- всегда есть вероятность ошибки (за счет шума). Вопрос шума подробно учитывается в работах Tsybakov --- там существует понятие "Tsybakov low noise condition", также в работах Pascal Massart. У Толстихина есть прочное ощущение, что это неявное "отсутствие шума" может вызвать (и уже вызывало) много вопросов со стороны западного community. Вот, в частности, цитата третьего рецензента с COLT 2011: "Furthermore, it seems that the results only apply to the deterministic labeling model. This is quite restrictive and is nowhere explicitly stated in the paper." Толстихин не утверждает что правильно ТАК или ЭДАК. Но точно стоит подумать в этом направлении.Возможный подходы к решению: в случае бинарной классификации нам надо, чтобы условное распределение )
размазалось по обоим меткам классов 
. Таким образом для каждого объекта генеральной выборки 
возникает параметр )
. Тут начинаются проблемы. Фактически, индикатор ошибки )
алгоритма 
на объекте становится случайной величиной. Она имеет распределение Бернулли с параметром 
(либо 
). Возникает вопрос, как записывать функционал 
. Один из вариантов, предложенный Сашей Фреем, --- для каждого объекта генеральной выборки добавлять в нее его копию 
. Индикаторы ошибок алгоритмов рассматриваемого семейства на этом фиктивном объекте определить тождеством \equiv 1 - I(a, x_i))
. Тогда, кажется, функционал можно определить, введя веса на объектах новой пополненной генеральной выборки, используя параметры .
- Комбинаторный подход от классического SLT отличается лишь тем, что вместо iid выборки длиной n из распределения P мы выбираем равномерно без возвращения из конечного множество объектов. В этом смысле в рамках комбинаторной теории можно было бы пойти путем, описанным в лекциях В.И. Колчинского. Но для этого нужен результат концентрации, позволяющий учитывать аналог
)
диаметра в комбинаторном случае --- расстояние Хэминга. Именно уменьшение к нулю диаметра дельта-минимального множества дает возможность получать хорошие оценки. Вдобавок этот подход --- начинающийся с супремума и затем итерационно уточняющий подмножества класса функций, по которому берется супремум, --- позволит распрощаться с бинарными потерями и использовать более общий класс потерь 
.
Литература
См. также
