Предсказывающие неравенства в задаче эмпирической минимизации риска (виртуальный семинар)

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

Версия от 09:57, 13 марта 2013; Reshetov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Определения
2 Примеры
3 Постановка задачи
4 Открытые замечания
5 Литература
6 См. также

На данной странице предлагается обсуждать лекции Владимира Колчинского. Одной из целью обсуждения является получение результатов, связывающих комбинаторную теорию переобучения и классическую Computational learning theory.

Данная страница не ставит целью дать краткое изложения лекций Владимира Колчинского. Перед чтением лекций рекомендуется прослушать видео-запись выступления Владимира Колчинского Bounding Excess Risk in Machine Learning (в трёх частях, суммарная длительность - порядка трёх часов).

Определения

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

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

Примеры

Предположим, что обучающая выборка задана в виде соверше́нной дизъюнкти́вной норма́льной фо́рмы (СДНФ), содержащей все логически взаимоисключающие примеры:

x₁	x₂	f(x₁, x₂)
0	0	0
0	1	1
1	0	1
1	1	1

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

Чтобы в выборке имела место избыточность, необходимо и достаточно включить в неё один или более факторов, которые логически не будут влиять на результат классификации:

Например, включим в нашу выборку избыточный фактор x₀:

x₁	x₂	f(x₀, x₁, x₂)
0	0	0
0	1	1
1	0	1
1	1	1
0	0	0
0	1	1
1	0	1
1	1	1

Чтобы в выборке имелись в наличии логические неопределенности, необходимо и достаточно исключить из неё один или несколько примеров, так чтобы в ней содержались не все логически взаимоисключающие примеры для зависимых переменных (факторов):

x₁	x₂	f(x₁, x₂)
0	0	0
1	0	1
1	1	1

Согласно вышеприведенной выборки классификатор не может однозначно интерпретировать принадлежность объекта при x₁ = 0 и x₂ = 1 к классам 0 и 1.

Чтобы в выборке имелись в наличии логические противоречия, необходимо и достаточно включить из неё один или несколько примеров, так чтобы в ней содержались логически взаимоисключающие выходные значения классификатора примеры:

x₁	x₂	f(x₁, x₂)
0	0	0
0	1	0
0	1	1
1	0	1
1	1	1

Постановка задачи

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

Отсюда можно сделать вывод, что минимальная сложность задачи 2ⁿ, где: n - количество факторов, нормированных к диапазону от 0 до 1 включительно.

Открытые замечания

Стандартная оценка для excess risk выбрасывает отрицательную величину $P_n(\hat f - \bar f)$ , где $\hat f$ --- результат минимизации эмпирического риска, $\bar f$ --- минимизация true риска. Данная величина, некотором смысле, соответствует комбинаторной вероятности переобучения. Потому что данное выражение похоже на усредненное по наблюдаемой выборке значение разности между эмпирически-лучшим и реально-лучшим алгоритмом. Если задуматься, как мерять эту величину, то лучший вариант – это кросс-валидация полного скользящего контроля. Если научиться получать нижние оценки CCV в комбинаторной постановке, то возможно таким образом удалось бы уточнить оценки Кольчинского. Важно, что оценки должны быть нижними, а не верхними --- действительно, стандартная оценка выбрасывает отрицательное слагаемой, а хотелось бы не выбрасывать полностью, а только его кусочек (нижнюю оценку).

Попытка разобраться с конфликтом в трактовке шума на $Y$ . В комбинаторной теории индикатор ошибки $I(x_i)$ предполагается фиксированным. Таким образом неявно предполагается наличие единственного правильного ответа $y_i$ на объект $x_i$ (по крайней мере --- фиксируется некое множество правильных ответов без дальнейших обсуждений распределения вероятностей на элементах этой группы). В общепринятой постановке SLT принята другая интерпретация этого момента. Предполагается распределение $P$ на декартовом произведении $X\times Y$ . Таким образом при фиксированном объекте $X$ допускаются разные ответы $Y$ в соответствии с условным распределением $P(Y | X)$ . В комбинаторной теории это условное распределение имеет тривиальный вид: либо $P(Y | X)=1$ , либо $P(Y | X)=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." Толстихин не утверждает что правильно ТАК или ЭДАК. Но точно стоит подумать в этом направлении.Возможный подходы к решению: в случае бинарной классификации нам надо, чтобы условное распределение $P(Y|X)$ размазалось по обоим меткам классов $Y = \{ -1, +1\}$ . Таким образом для каждого объекта $x_i$ генеральной выборки $\mathbb{X}$ возникает параметр $p_i=P(Y=+1|x_i)$ . Тут начинаются проблемы. Фактически, индикатор ошибки $I(a,x_i)$ алгоритма $a$ на объекте $x_i$ становится случайной величиной. Она имеет распределение Бернулли с параметром $p_i$ (либо $1-p_i$ ). Возникает вопрос, как записывать функционал $Q_{\varepsilon}$ . Один из вариантов, предложенный Сашей Фреем, --- для каждого объекта $x_i$ генеральной выборки добавлять в нее его копию $x_i'$ . Индикаторы ошибок алгоритмов рассматриваемого семейства на этом фиктивном объекте $x_i'$ определить тождеством $I(a,x_i')\equiv 1 - I(a, x_i)$ . Тогда, кажется, функционал $Q_{\varepsilon}$ можно определить, введя веса на объектах новой пополненной генеральной выборки, используя параметры $p_i$ .

Комбинаторный подход от классического SLT отличается лишь тем, что вместо iid выборки длиной n из распределения P мы выбираем равномерно без возвращения из конечного множество объектов. В этом смысле в рамках комбинаторной теории можно было бы пойти путем, описанным в лекциях В.И. Колчинского. Но для этого нужен результат концентрации, позволяющий учитывать аналог $L_2(P)$ диаметра в комбинаторном случае --- расстояние Хэминга. Именно уменьшение к нулю диаметра дельта-минимального множества дает возможность получать хорошие оценки. Вдобавок этот подход --- начинающийся с супремума и затем итерационно уточняющий подмножества класса функций, по которому берется супремум, --- позволит распрощаться с бинарными потерями и использовать более общий класс потерь $F$ .