Неотрицательный метод наименьших квадратов

Регрессивный анализ
Часть серии по

Модели
Линейная регрессия Простая регрессия Полиномиальная регрессия Общая линейная модель
Обобщенная линейная модель Дискретный выбор Биномиальная регрессия Бинарная регрессия Логистическая регрессия Полиномиальный логит Смешанный логит Пробит Полиномиальный пробит Заказал логит Заказал пробит Пуассон
Многоуровневая модель Фиксированные эффекты Случайные эффекты Линейная модель смешанных эффектов Нелинейная модель смешанных эффектов
Нелинейная регрессия Непараметрический Полупараметрический Крепкий Квантиль Изотонический Основные компоненты Наименьший угол Местный Сегментированный
Ошибки в переменных
Оценка
Наименьших квадратов Линейный Нелинейный
Обычный Взвешенный Обобщенный
Частичное Общий Неотрицательный Регрессия хребта Регулярный
Наименьшие абсолютные отклонения Итеративно переназначенный Байесовский Байесовская многомерная
Фон
Проверка регрессии Средний и прогнозируемый ответ Ошибки и остатки Доброта подгонки Студентизированный остаток Теорема Гаусса – Маркова
Математический портал
v т е

В математической оптимизации задача неотрицательных наименьших квадратов ( NNLS ) представляет собой тип задачи наименьших квадратов с ограничениями, в которой коэффициенты не могут становиться отрицательными. То есть, учитывая матрицу $A$ и вектор (столбец) переменных отклика $y$ , цель состоит в том, чтобы найти ^[1]

{\ displaystyle \ operatorname {arg \, min} \ limits _ {\ mathbf {x}} \ | \ mathbf {Ax} - \ mathbf {y} \ | _ {2}}

при условии

x \geq 0

.

Здесь $x \geq 0$ означает, что каждая компонента вектора $x$ должна быть неотрицательной, а $‖ \cdot ‖ 2$ обозначает евклидову норму .

Неотрицательные задачи наименьших квадратов возникают как подзадачи в матричной декомпозиции , например, в алгоритмах для PARAFAC ^[2] и неотрицательной матричной / тензорной факторизации . ^[3]^[4] Последнее можно рассматривать как обобщение NNLS. ^[1]

Другое обобщение NNLS - метод наименьших квадратов с ограниченными переменными (BVLS) с одновременными верхними и нижними границами $α i \leq x i \leq β i$ . ^[5]^{: 291}^[6]

Версия квадратичного программирования [ править ]

Задача NNLS эквивалентна задаче квадратичного программирования.

{\ displaystyle \ operatorname {arg \, min} \ limits _ {\ mathbf {x \ geq 0}} \ left ({\ frac {1} {2}} \ mathbf {x} ^ {\ mathsf {T}} \ mathbf {Q} \ mathbf {x} + \ mathbf {c} ^ {\ mathsf {T}} \ mathbf {x} \ right),}

где $Q$ = $A T A$ и $c$ = $- A T y$ . Эта проблема является выпуклой , а $Q$ является неотрицательно и ограничение неотрицательности образует выпуклое допустимое множество. ^[7]

Алгоритмы [ править ]

Первым широко используемым алгоритмом для решения этой проблемы является метод активного множества, опубликованный Лоусоном и Хэнсоном в их книге 1974 г. « Решение задач наименьших квадратов» . ^[5]^{: 291} В псевдокоде этот алгоритм выглядит следующим образом: ^[1]^[2]

Входы:
- вещественная матрица $A$ размерности $m \times n$ ,
- действительный вектор $y$ размерности $m$ ,
- действительное значение $ε$ , допуск по критерию остановки.
Инициализировать:
- Установите $P = \emptyset$ .
- Установите $R = {1, ..., n$ }.
- Установите $x$ равным нулевому вектору размерности $n$ .
- Установите $w = A T (y - A x)$ .
- Обозначим через $w R$ субвектор с индексами из R
Основной цикл: пока R ≠ ∅ и max ( w ^R )> ε :
- Пусть $j$ в $R$ будет индексом $max (w R)$ в $w$ .
- Добавить $J$ в $P$ .
- Удалить $J$ из $R$ .
- Пусть $P$ будет ограничено переменных , включенных в $P$ .
- Пусть $s$ вектор той же длины, что и $x$ . Давайте $сек P$ обозначим через суб-вектор с индексами от Р , и пусть $s R$ обозначают суб-вектор с индексами от R .
- Положим $s P = ((A P) T A P) -1 (A P) T y$
- Установить $s R$ на ноль
- Пока min ( s ^P ) ≤ 0 :
  - Пусть $α = min х я / х я - с я для i в P, где s i \leq 0$ .
  - Установите $x$ равным $x + α (s - x)$ .
  - Переместим в $R$ все индексы $j$ в $P$ такие, что $x j \leq 0$ .
  - Положим $s P = ((A P) T A P) -1 (A P) T y$
  - Установите $s R$ на ноль.
- Установите $x$ в $s$ .
- Набор $ш$ к $А Т (у - х)$ .
Выход: x

Этот алгоритм требует конечного числа шагов для достижения решения и плавно улучшает его возможное решение по мере продвижения (так что он может находить хорошие приближенные решения при отсечении разумного числа итераций), но на практике он очень медленный, в основном из-за вычисление псевдообратной $((A P) T A P) -1$ . ^[1] Варианты этого алгоритма доступны в MATLAB как процедура lsqnonneg ^[1] и в SciPy как optimize.nnls . ^[8]

С 1974 года было предложено много улучшенных алгоритмов. ^[1] Fast NNLS (FNNLS) - это оптимизированная версия алгоритма Лоусона-Хэнсона. ^[2] Другие алгоритмы включают варианты Ландвебер «s градиентный метода ^[9] и покоординатной оптимизации на основе квадратичной задачи программирования выше. ^[7]

См. Также [ править ]

М-матрица
Теорема Перрона – Фробениуса.

Ссылки [ править ]

^ a b c d e f Чен, Дунхуэй; Племмонс, Роберт Дж. (2009). Ограничения неотрицательности в численном анализе . Симпозиум по рождению численного анализа. CiteSeerX 10.1.1.157.9203 .
^ a b c Бро, Расмус; Де Йонг, Сиджмен (1997). «Быстрый алгоритм наименьших квадратов с ограничениями неотрицательности». Журнал хемометрики . 11 (5): 393. DOI : 10.1002 / (SICI) 1099-128X (199709/10) 11: 5 <393 :: AID-CEM483> 3.0.CO; 2-L .
^ Лин Чи-Jen (2007). «Спроектированные градиентные методы для неотрицательной матричной факторизации» (PDF) . Нейронные вычисления . 19 (10): 2756–2779. CiteSeerX 10.1.1.308.9135 . DOI : 10.1162 / neco.2007.19.10.2756 . PMID 17716011 .
^ Буцидис, Христос; Дриней, Петрос (2009). «Случайные проекции для неотрицательной задачи наименьших квадратов». Линейная алгебра и ее приложения . 431 (5–7): 760–771. arXiv : 0812.4547 . DOI : 10.1016 / j.laa.2009.03.026 .
^ a b Лоусон, Чарльз Л .; Хэнсон, Ричард Дж. (1995). Решение задач наименьших квадратов . СИАМ.
^ Старк, Филип Б .; Паркер, Роберт Л. (1995). «Метод наименьших квадратов с ограниченными переменными: алгоритм и приложения» (PDF) . Вычислительная статистика . 10 : 129.
^ a b Франк, Войтех; Главач, Вацлав; Навара, Мирко (2005). Последовательный координатно-мудрый алгоритм для задачи неотрицательных наименьших квадратов . Компьютерный анализ изображений и паттернов . Конспект лекций по информатике. 3691 . С. 407–414. DOI : 10.1007 / 11556121_50 . ISBN 978-3-540-28969-2.
^ "scipy.optimize.nnls" . Справочное руководство SciPy v0.13.0 . Проверено 25 января 2014 года .
^ Йоханссон, BR; Эльфвинг, Т .; Козлов, В .; Цензор Ю.А. Форссен, ЧП; Гранлунд, GS (2006). «Применение метода Ландвебера с наклонной проекцией к модели контролируемого обучения» . Математическое и компьютерное моделирование . 43 (7-8): 892. DOI : 10.1016 / j.mcm.2005.12.010 .

[chen-1] Чен, Дунхуэй; Племмонс, Роберт Дж. (2009). Ограничения неотрицательности в численном анализе . Симпозиум по рождению численного анализа. CiteSeerX 10.1.1.157.9203 .

[bro-2] Бро, Расмус; Де Йонг, Сиджмен (1997). «Быстрый алгоритм наименьших квадратов с ограничениями неотрицательности». Журнал хемометрики . 11 (5): 393. DOI : 10.1002 / (SICI) 1099-128X (199709/10) 11: 5 <393 :: AID-CEM483> 3.0.CO; 2-L .

[3] Лин Чи-Jen (2007). «Спроектированные градиентные методы для неотрицательной матричной факторизации» (PDF) . Нейронные вычисления . 19 (10): 2756–2779. CiteSeerX 10.1.1.308.9135 . DOI : 10.1162 / neco.2007.19.10.2756 . PMID 17716011 .

[4] Буцидис, Христос; Дриней, Петрос (2009). «Случайные проекции для неотрицательной задачи наименьших квадратов». Линейная алгебра и ее приложения . 431 (5–7): 760–771. arXiv : 0812.4547 . DOI : 10.1016 / j.laa.2009.03.026 .

[lawson-5] Лоусон, Чарльз Л .; Хэнсон, Ричард Дж. (1995). Решение задач наименьших квадратов . СИАМ.

[6] Старк, Филип Б .; Паркер, Роберт Л. (1995). «Метод наименьших квадратов с ограниченными переменными: алгоритм и приложения» (PDF) . Вычислительная статистика . 10 : 129.

[sca-7] Франк, Войтех; Главач, Вацлав; Навара, Мирко (2005). Последовательный координатно-мудрый алгоритм для задачи неотрицательных наименьших квадратов . Компьютерный анализ изображений и паттернов . Конспект лекций по информатике. 3691 . С. 407–414. DOI : 10.1007 / 11556121_50 . ISBN 978-3-540-28969-2.

[8] "scipy.optimize.nnls" . Справочное руководство SciPy v0.13.0 . Проверено 25 января 2014 года .

[9] Йоханссон, BR; Эльфвинг, Т .; Козлов, В .; Цензор Ю.А. Форссен, ЧП; Гранлунд, GS (2006). «Применение метода Ландвебера с наклонной проекцией к модели контролируемого обучения» . Математическое и компьютерное моделирование . 43 (7-8): 892. DOI : 10.1016 / j.mcm.2005.12.010 .