Модифицированная ортогонализация Грама-Шмидта
Материал из MachineLearning.
Строка 122: | Строка 122: | ||
6: <tex> \ \ r_{jj}</tex> := <tex>||g_j||</tex>; | 6: <tex> \ \ r_{jj}</tex> := <tex>||g_j||</tex>; | ||
+ | |||
+ | ---- | ||
Строка 211: | Строка 213: | ||
10: <tex>\ \ \ \ \ </tex>прекратить добавление столбцов; выход; | 10: <tex>\ \ \ \ \ </tex>прекратить добавление столбцов; выход; | ||
- | 11: для <tex>i</tex> := <tex>j + 1, . . . , n</tex> | + | 11: <tex>\ \ </tex>для <tex>i</tex> := <tex>j + 1, . . . , n</tex> |
12: <tex>\ \ \ \ r_{ji}</tex> := <tex>\tilde{g}^T_jg_i</tex>; (компоненты вектор-столбца <tex>r_i</tex>); | 12: <tex>\ \ \ \ r_{ji}</tex> := <tex>\tilde{g}^T_jg_i</tex>; (компоненты вектор-столбца <tex>r_i</tex>); | ||
Строка 223: | Строка 225: | ||
16: конец цикла по <tex>j</tex>. | 16: конец цикла по <tex>j</tex>. | ||
+ | ---- | ||
+ | Наконец, можно использовать совокупность критериев, выбирая тот столбец, добавление которого выгодно с нескольких точек зрения. | ||
+ | В Алгоритме 1.2 применяются первые два критерия. | ||
+ | Алгоритм состоит из основного цикла по <tex>j</tex>, в котором поочерёдно добавляются столбцы. На шаге 3 принимается решение, какой из оставшихся столбцов <tex>f_m</tex> добавить, затем он меняется местами со столбцом <tex>f_j</tex> . Шаги 5–8 обновляют текущие | ||
+ | значения функционала <tex>Q_j</tex> , обратной матрицы <tex>T_j</tex> и коэффициентов <tex>\alpha_j</tex>. На шаге 9 проверяется условие останова: если достаточная точность аппроксимации уже достигнута, то добавлять оставшиеся столбцы не имеет смысла. Таким образом, Алгоритм 1.2 осуществляет отбор информативных признаков (features selection). Шаги 11–15 реализуют вложенный цикл, в котором все последующие столбцы ортогонализуются относительно только что добавленного столбца. Заодно обновляются значения квадратов норм столбцов <tex>Z_j = ||g_j||^2</tex> и скалярных произведений <tex>D_j = y^Tg_j</tex> , необходимые для эффективного выбора признака <tex>f_m</tex> на шаге 3 в следующей итерации. | ||
+ | == Литература == | ||
+ | *''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]] | ||
- | + | {{Задание|DValov|Константин Воронцов|7 января 2010}} | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | {{Задание|DValov|Константин Воронцов| | + |
Версия 18:00, 5 января 2010
Модифицированная ортогонализация Грама-Шмидта - известный алгоритм ортогонализации, который строит ортогональные векторы
, линейная оболочка которых совпадает с линейной оболочкой
.
Введение
Рассмотрим ортогональное разложение , где
- верхняя треугольная матрица размера
×
,
- ортогональная
×
- матрица,
. Для любой матрицы
существует бесконечно много разложений указанного вида. Имея одно из них, легко выразить псевдообратную матрицу
через
и
:
.
Для вычисления псевдообратной достаточно построить какое-нибудь ортогональное разложение матрицы
, обратить верхнюю треугольную матрицу
и умножить её на
. Этот метод во многом удобнее явного обращения матрицы.
Метод ортогонализации Грама-Шмидта
Для построения разложения воспользуемся процессом ортогонализации Грама-Шмидта. Запишем матрицы
и
по столбцам:
;
.
Волной здесь и далее обозначается операция нормирования вектора:
.
Процесс ортогонализации Грама-Шмидта строит ортогональные векторы , линейная оболочка которых совпадает с линейной оболочкой
:
;
;
· · ·
.
Легко проверить, что для всех из
,
, векторы
и
ортогональны.
Вспомогательные утверждения
Лемма 1.1. На -м шаге процесса,
, матрица
представима в виде ортогонального разложения
, где
- ортонормированная матрица;
- верхняя треугольная матрица,
По окончании процесса ортогонализации получаем ортогональное разложение .
С вычислительной точки зрения процесс Грама-Шмидта удобен тем, что на каждом шаге матрицы и
получаются путём дописывания справа по одному столбцу к матрицам
и
соответственно. При этом предыдущие столбцы не изменяются (если не считать изменением дописывание нулей снизу к матрице
- при разумной программной реализации эти нули всё равно не хранятся).
В следующей лемме утверждается, что обратная матрица также является верхней треугольной и формируется путём дописывания столбцов справа.
Лемма 1.2. Пусть матрицы невырождены и в блочной записи имеют вид
;
,
,
где - скаляр,
- вектор-столбец размера
. Тогда матрицы
могут быть вычислены по рекуррентной формуле
;
,
,
где - скаляр,
- вектор-столбец размера
.
Замечание 1.1. Обеспечить невырожденность матрицы в процессе ортогонализации очень просто. Допустим, матрица
невырождена. Поскольку
- верхняя треугольная, вырожденность может возникнуть только в том случае, если
. Такое возможно только при
, а это означает, что вектор
линейно зависит от векторов
. Если в ходе процесса
оказывается равным нулю, то коэффициент
обнуляется и
-й признак далее не учитывается, как будто его вообще не существовало. Если
не равен, но близок к нулю, может возникнуть проблема неустойчивости решения, поскольку на
приходится делить. На практике признак
исключают, например, по такому условию:
, где
имеет порядок
.
Назовём вектор текущим вектором коэффициентов на
-м шаге.
Этот вектор имеет размерность
. По окончании процесса
.
Лемма 1.3. Пусть выполняются условия предыдущей леммы. Тогда на -м шаге
процесса вектор
может быть вычислен по рекуррентной формуле
,
,
.
Назовём величину текущим значением функционала
на
-м шаге. Оно равно кратчайшему расстоянию от
до линейной оболочки столбцов
. По окончании процесса
. Следующая лемма показывает, что текущее значение
от шага к шагу только уменьшается.
Лемма 1.4. Значения могут быть вычислены в ходе ортогонализации по рекуррентной формуле
;
.
Лемма 1.5. Текущий вектор невязок на
-м шаге процесса ортогонализации вычисляется по рекуррентной формуле
;
.
Алгоритм 1.1. Ортогонализация Грама-Шмидта
1: инициализация: :=
:=
;
2: для :=
3: для
:=
4: :=
; (вычисление
-й компоненты вектор-столбца
);
5: :=
; (ортогонализация
относительно
);
6: :=
;
Модифицированная ортогонализация Грама-Шмидта
Если вместо :=
вычислять
:=
, то формально результат не изменится, поскольку
.
Данная модификация повышает численную устойчивость алгоритма. Это объясняется тем, что вектор обладает минимальной нормой среди всех векторов вида
, где
- произвольные коэффициенты. Поэтому при скалярном умножении на
ошибки накапливаются существенно медленнее.
Прежде чем переходить к следующей модификации, запишем основную часть
алгоритма ортогонализации, вычисляющую и
.
Изменим порядок ортогонализации столбцов. До сих пор мы ортогонализовали столбец относительно предыдущих столбцов
. Но можно сделать и подругому - ортогонализовать все последующие столбцы
относительно
:
:=
.
Тогда в начале -го шага все столбцы
по построению будут ортогональны всем столбцам
. При этом подматрицы
и вектор
останутся такими же, как и до модификации.
Описанная модификация обладает важным преимуществом. Теперь на каждом шаге можно выбрать столбец , добавление которого наиболее выгодно. Чтобы не менять обозначений, будем полагать, что перед добавлением столбцы
и
переставляются местами (при реализации придётся сохранять соответствие между старой и новой нумерацией признаков, но мы не будем останавливаться на столь мелких технических деталях).
Возможны альтернативные критерии выбора добавляемого столбца:
1) столбец с максимальной нормой , что соответствует выбору столбца
, максимально некоррелированного с
; применение этого критерия решает проблему вырожденности
(см. Замечание 1.1); здесь существенно, чтобы матрица
была заранее стандартизована;
2) столбец, наиболее коррелированный с вектором ответов: ; его добавление ведёт к скорейшему убыванию функционала
;
3) столбец, добавление которого ведёт к наименьшему увеличению нормы век-
тора коэффициентов , что соответствует применению регуляризации;
4) столбец, после добавления которого значение функционала качества на независимой контрольной выборке
окажется минимальным, что соответствует применению скользящего контроля (hold-out CV).
Алгоритм 1.2. Решение линейной задачи наименьших квадратов путём ортогонализации Грама-Шмидта с последовательным добавлением признаков
Вход:
- матрица информации;
- вектор ответов;
- параметр критерия останова.
Выход:
- вектор коэффициентов линейной комбинации;
- минимальное значение функционала.
1: инициализация:
:=
:=
:=
:=
:=
2: для :=
3: выбор
по критериям
и
4: перестановка местами столбцов:
5: :=
; нормировка:
:=
6: вычисление текущего значения функционала:
:=
; (эффективное вычисление
:=
);
:=
7: обращение верхней треугольной матрицы
:
(вектор-столбец
длины
);
8: вычисление текущего вектора коэффициентов:
9: если
то
10: прекратить добавление столбцов; выход;
11: для
:=
12: :=
; (компоненты вектор-столбца
);
13: :=
; (ортогонализация
относительно
);
14: :=
; (теперь
);
15: :=
; (теперь
);
16: конец цикла по .
Наконец, можно использовать совокупность критериев, выбирая тот столбец, добавление которого выгодно с нескольких точек зрения.
В Алгоритме 1.2 применяются первые два критерия.
Алгоритм состоит из основного цикла по , в котором поочерёдно добавляются столбцы. На шаге 3 принимается решение, какой из оставшихся столбцов
добавить, затем он меняется местами со столбцом
. Шаги 5–8 обновляют текущие
значения функционала
, обратной матрицы
и коэффициентов
. На шаге 9 проверяется условие останова: если достаточная точность аппроксимации уже достигнута, то добавлять оставшиеся столбцы не имеет смысла. Таким образом, Алгоритм 1.2 осуществляет отбор информативных признаков (features selection). Шаги 11–15 реализуют вложенный цикл, в котором все последующие столбцы ортогонализуются относительно только что добавленного столбца. Заодно обновляются значения квадратов норм столбцов
и скалярных произведений
, необходимые для эффективного выбора признака
на шаге 3 в следующей итерации.
Литература
- К.В. Воронцов, Машинное обучение (курс лекций)
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |