Материал из MachineLearning.
На данной странице предлагается обсуждать лекции Владимира Колчинского. Одной из целью обсуждения является получение результатов, связывающих комбинаторную теорию переобучения и классическую Computational learning theory.
Данная страница не ставит целью дать краткое изложения лекций Владимира Колчинского. Перед чтением лекций рекомендуется прослушать видео-запись выступления Владимира Колчинского Bounding Excess Risk in Machine Learning (в трёх частях, суммарная длительность - порядка трёх часов).
Открытые замечания
- Стандартная оценка для excess risk выбрасывает отрицательную величину
)
, где 
--- результат минимизации эмпирического риска, 
--- минимизация true риска. Данная величина, некотором смысле, соответствует комбинаторной вероятности переобучения. Потому что данное выражение похоже на усредненное по наблюдаемой выборке значение разности между эмпирически-лучшим и реально-лучшим алгоритмом. Если задуматься, как мерять эту величину, то лучший вариант – это кросс-валидация полного скользящего контроля. Если научиться получать нижние оценки CCV в комбинаторной постановке, то возможно таким образом удалось бы уточнить оценки Кольчинского. Важно, что оценки должны быть нижними, а не верхними --- действительно, стандартная оценка выбрасывает отрицательное слагаемой, а хотелось бы не выбрасывать полностью, а только его кусочек (нижнюю оценку).
- Попытка разобраться с конфликтом в трактовке шума на
. В комбинаторной теории индикатор ошибки )
предполагается фиксированным. Таким образом неявно предполагается наличие единственного правильного ответа 
на объект 
(по крайней мере --- фиксируется некая группа правильных ответов без дальнейших обсуждений распределения вероятностей на элементах этой группы). В общепринятой постановке SLT принята другая интерпретация этого момента. ПРедполагается распределение 
на декартовом произведении 
. Таким образом при фиксированном объекте 
допускаются разные ответы в соответствии с распределением . В литературе этот вопрос фигурирует под графой 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." Толстихин не утверждает что правильно ТАК или ЭДАК. Но точно стоит подумать в этом направлении.
Литература
См. также
