Пошаговая регрессия и SVD

[katamaran]

Добрый день.
Задача:
Есть переопределенная СЛАУ (порядка 1000 уравнений и 20 неизвестных).
Количество неизвестных явно больше чем необходимо для решения задачи с нужной точностью (это известно из постановки задачи).
Тем самым необходимо придумать алгоритм отбрасывания "лишних" неизвестных.
В частности существует т.н. пошаговая регрессия, однако этот подход может приводить к локальным минимумам. В прекрасной книге "Численное решение задач метода наименьших квадратов"
Лоусон Ч., Хенсон Р. говорится, что "Эту трудность можно обойти, выполняя линейный переход к новым переменным, чьи индивидуальные воздействия на вектор невязки взаимно независимы" и предлагается использовать SVD разложение матрицы коэффициентов уравнения и т.д. Подробностей не нашел(

Может кто сталкивался с подобным подходом/алгоритмом посоветуйте книжку или ресурс.
Спасибо.

[svv]

Вы можете ещё более определённо подтвердить, что простой метод $A^{\top} A x=A^{\top} b$ Вам не подходит?
(так как есть подозрение, что подходит)

[katamaran]

Объяснение 1. Физическое. Переопределенная СЛАУ, в моем случае, это измеренный энергетический спектр некоторой смеси хим. элементов (b), который представляется в виде суперпозиции энергетических спектров отдельных химических элементов (A). Всего элементов может быть порядка 20, но в каждой конкретной смеси порядка 5-10. Если использовать при решении задачи полный набор, то результат получается плохой: пропадают нужные элементы и появляются не нужные.
Объяснение 2. Математическое. Число обусловленности матрицы А большое, задача неустойчивая. Разброс по значениям сингулярных чисел очень большой, несколько порядков.

[мат-ламер]

katamaran в сообщении #536020 писал(а):

"Эту трудность можно обойти, выполняя линейный переход к новым переменным,

Если линейный переход к новым переменным Вас устроит, то посмотрите в сторону метода главных компонент. Смотрите в Википедии соответствующую статью.

[Евгений Машеров]

Посмотрите в сторону ридж-регрессии.

[katamaran]

На сколько я понимаю, метод главных компонент позволяет построить некоторый новый набор т.е. перейти от А к А', меньшего размера.
Но А' не состоит из столбцов А, т.е. теряет физический смысл. (Поправьте если я не правильно трактую)
Меня в общем в первую очередь интересуют именно x, как решение СЛАУ Ax=b, потому что x при А , это совершенно конкретная физическая величина.
Т.е здесь решается задача оценки параметров, а не аппроксимации данных.

Ридж регрессия по сути это регуляризация, т.е. решение будет строиться исходя из полной матрицы А,
мне кажется , что сначала необходимо как-нибудь "урезать" А, вот в этом и вопрос.

Большое спасибо.

[Евгений Машеров]

0. Вот и появился человек, которому бы пригодилась моя диссертация (технических наук).
Машеров, Евгений Леонидович Методы оценивания зависимостей, использующие сингулярное разложение. Смещенные и несмещенные оценки : автореферат дис. ... кандидата технических наук : 05.13.16 / Ин-т проблем управления Москва, 1991
(к сожалению, бумажный экземпляр у меня "убежал", а электронный сохранился в устаревшем формате ChiWriter, современные же конверторы из этого формата правильно формулы не интерпретируют; надо бы в Ленинке копию заказать).
1. Проблема в использовании главных компонент (или сингулярного разложения обычным образом, что, собственно, и есть ГК) состоит в том, что отбрасываются компоненты, соответствующие минимальным собственным числам. А вот в выражение для регрессионных коэффициентов сингулярные числа входят в обратном виде. Т.е. отбрасываем основную часть выражения для коэффициентов. Что, разумеется, резко сокращает их дисперсию и столь же резко порождает их смещение.
Когда имеет место "истинная мультиколлинеарность", то есть линейная зависимость между регрессорами (точная в пределах погрешности вычислений), то, разумеется, это (отбрасывание сингулярных чисел, по порядку величины близких к ошибке округления) к ухудшению не приводит. Увы, в реальных задачах типична неполная мультиколлинеарность, то есть линейной зависимости нет, а коррелированность велика (в данном случае - два спектра компонент могут быть различны, но сходны).
2. Ридж-регрессия (и все вообще регуляризационные подходы) не обнуляют, а "придавливают" соответствующие компоненты, беря их с меньшими весами. Однако появляется субъективный выбор ридж-параметра.
3. Подход, который я развивал - состоял в том, что можно выбрать оптимальные веса (нечто в духе оптимальной фильтрации Винера). И хотя знание оптимальных весов эквивалентно знанию самих коэффициентов (а если они уже известны - зачем суетиться?), но подстановка в выражение для оптимальных весов оценок даёт хороший эффект.

[katamaran]

Спасибо за развернутый ответ. В ленинке постараюсь заказать, а пока можно посмотреть на Вашу диссертацию в электронном виде (попробую ChiWriter прочитать, если не трудно выслать на [e-mail]).
Еще одно соображение: в принципе я могу перебрать все комбинации своих компонент, и найти подходящие, но перебор очень уж большой. Выбрасывать по одному, не очень понятно как, дело в том , что компонента с наименьшим вкладом (с наибольшей ошибкой) на i-том шаге может быть важнее на j-том, т.е. зависит от комбинации компонент.
Вот я и ищу метод правильного "выкидывания" компонент.

[Евгений Машеров]

Вообще, при 20 регрессорах полный перебор это всего лишь 1048575 вариантов (не считая "нулевого"). Обращение матрицы 20х20 это порядка $10^5$ операций или менее, так что даже "в лоб" это порядка $10^{11}$ операций. На даже не очень крутой машине - несколько часов. Может, ночь. Более того, описан (например, Себер, "Линейный регрессионный анализ" - есть, скажем, тут: http://www.twirpx.com/file/95399/ ) подход, в котором при переходе от модели к модели (в смысле набора регрессоров) вводятся-выводятся они по одному, со сложностью O(n) вместо кубической, и перечисление всех моделей проводится обходом бинарного дерева. Там такого рода полный перебор (который возможность "застревания в локальном оптимуме" исключает в принципе) считается возможным для числа регрессоров до 20 (книга отражает уровень 1970-х, так что сейчас, пожалуй, и 30 допустимо, если не более), для числа регрессоров до 40 рекомендуется пошаговая регрессия методом включения-исключения (собственно, тот же метод, что и в "полном переборе по дереву"; появляется риск остановиться на локальном оптимуме, например, при нескольких сильно коррелированных регрессорах первым может быть выбран менее влияющий, но улучшение от замены более связанным менее регрессора недостаточно, чтобы такая замена была бы произведена), а в задачах с числом регрессоров вплоть до 100 предлагается использовать случайный поиск (сейчас, вероятно, надо рассмотреть и генетические алгоритмы).

[katamaran]

При переборе регрессоров для каждой комбинации ищется решение СЛАУ - это очень долго, специфика мой задачи в том что она повторяется порядка 1000 раз, т.е. у меня тысяча смесей которые надо определить, время которое меня устроит порядка нескольких минут. Решение без выбора , обычным МНК, порядка нескольких десятков секунд. Если делать прямой перебор то соответственно общее время будет порядка 100 дней(