4.3Итерационный алгоритм численного решения двойственной задачи

Обозначим через произвольное разбиение множества признаков:

, , , , .

Свяжем с произвольным разбиением задачу оптимизации

получающуюся из выбором соответствующего слагаемого в сумме . Очевидно, что есть задача квадратичного программирования.

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

Теорема 2. Пусть – некоторое разбиение множества признаков , –решение соответствующей задачи квадратичного программирования , и – разбиение множества признаков, определяемое этим решением . Для того, чтобы совокупность была решением двойственной задачи , необходимо и достаточно, чтобы разбиения и совпадали.

Доказательство. Начнем с необходимости. Пусть есть решение задачи , и

.

Тогда согласно выражению в фигурных скобках в имеем

Примем в качестве разбиение множества признаков , т.е. положим , и рассмотрим задачу . Очевидно, что в этом случае в задачах и выполняется равенство

,

т.е. эти задачи совпадают. Следовательно, наряду с , справедливо также утверждение

,

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

Перейдем к доказательству достаточности. Пусть – некоторое разбиение совокупности признаков , и – решение задачи квадратичного программирования для этого разбиения. Сформируем разбиение согласно

п предположим, что . Тогда согласно принятому предположению есть решение задачи

т.е. в силу это решение задачи . Достаточность доказана.

Теорема доказана полностью.

Теорема 2 подсказывает итерационный алгоритм численного решения двойственной задачи выпуклого программирования , сводящийся к многократному решению задачи квадратичного программирования .

Пусть – некоторое очередное приближение к искомой точке минимума задачи , – соответствующее разбиение множества признаков. Выберем в качестве решение задачи квадратичного программирования для , т.е.

.

Нетрудно убедиться, что

, если .

Алгоритм останавливается, когда .

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

.

Алгоритм обычно сходится за 20-30 итераций.

5Задача оценивания числовой зависимости

5.1Линейная модель числовой зависимости. Центрированная и нормированная обучающая совокупность

Продолжим рассмотрение идеальной ситуации, когда вектор действительных признаков , , погружает множество реальных объектов в конечномерное линейное пространство (раздел 1.5). Однако будем говорить о задаче восстановления числовой зависимости, когда множество значений скрытой характеристики объектов есть числовая ось , а модель зависимости ищется в линейном виде

.

Если задана обучающая совокупность , то задача оценивания линейной модели зависимости в условиях излишне большого множества числовых признаков объектов , , может быть сформулирована как задача построения модели гребневой регрессии, заключающаяся в совместной взвешенной минимизации остаточной суммы квадратов ошибок и так называемого гребневого регуляризующего штрафа , где – коэффициент баланса между этими взаимно противоречивыми требованиями. Однако очевидно, что гребневой штраф имеет смысл, только если обучающая совокупность центрирована и нормирована:

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

Если – исходная обучающая совокупность, то она может быть нормализована следующим образом:

.

Обратно, если по нормализованной обучающей совокупности найдена регрессионная модель , то ее следует пересчитать в исходные шкалы, в которых естественным образом измерены признаки нового объекта . Согласно , поэтому

В предположении, что обучающая совокупность центрирована и нормирована , задача гребневого обучения (Ridge Regression) примет следующий вид:

.

Критерий гребневой регрессии содержит два структурных параметра – гребневой штраф и подмножество признаков . Выбор первого из них не составляет серьезной проблемы, достаточно принять достаточно малое значение с единственной целью гарантировать строгую выпуклость критерия обучения в случае возможной линейной зависимости подвекторов признаков в . Однако что качается выбора подмножества , то это очень трудная задача.

Оценить «качество» конкретного подмножества признаков можно по методу скользящего контроля, который для квадратичного критерия допускает простую численную реализацию [⁷], основанную на известной матричной формуле (Sherman-Woodbury-Morrison formula) [⁸]. Однако перебрать все подмножеств все равно невозможно.