Наименьшие абсолютные отклонения

Статистический критерий оптимальности

Наименьшие абсолютные отклонения ( LAD ), также известные как наименьшие абсолютные ошибки ( LAE ), наименьшие абсолютные остатки ( LAR ) или наименьшие абсолютные значения ( LAV ), являются статистическим критерием оптимальности и статистическим методом оптимизации , основанным на минимизации суммы абсолютных отклонений (также суммы абсолютных остатков или суммы абсолютных ошибок ) или нормы L 1 таких значений. Он аналогичен методу наименьших квадратов , за исключением того, что он основан на абсолютных значениях вместо квадратов значений . Он пытается найти функцию , которая близко приближает набор данных путем минимизации остатков между точками, сгенерированными функцией, и соответствующими точками данных. Оценка LAD также возникает как оценка максимального правдоподобия , если ошибки имеют распределение Лапласа . Она была введена в 1757 году Роджером Джозефом Босковичем . ^[1]

Формулировка

Предположим, что набор данных состоит из точек ( x _i , y _i ) с i = 1, 2, ..., n . Мы хотим найти функцию f такую, что ${\displaystyle f(x_{i})\approx y_{i}.}$

Для достижения этой цели мы предполагаем, что функция f имеет определенную форму, содержащую некоторые параметры, которые необходимо определить. Например, простейшей формой будет линейная: f ( x ) = bx + c , где b и c — параметры, значения которых неизвестны, но которые мы хотели бы оценить. Менее просто, предположим, что f ( x ) является квадратичной , что означает, что f ( x ) = ax ² + bx + c , где a , b и c еще неизвестны. (В более общем смысле, может быть не только один экспланатор x , но и несколько экспланаторов, все из которых появляются как аргументы функции f .)

Теперь ищем оценочные значения неизвестных параметров, которые минимизируют сумму абсолютных значений остатков:

${\displaystyle S=\sum _{i=1}^{n}|y_{i}-f(x_{i})|.}$

Решение

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

• Симплексные методы (например, алгоритм Барродейла-Робертса ^[2] )
  • Поскольку задача представляет собой линейную программу , можно применить любой из многочисленных методов линейного программирования (включая симплекс-метод и другие).
• Итеративно перевзвешенные наименьшие квадраты ^[3]
• Метод прямого спуска Весоловского ^[4]
• Метод максимального правдоподобия Ли-Арсе ^[5]
• Рекурсивный подход к уменьшению размерности ^[6]
• Проверить все комбинации линий точка-точка на минимальную сумму ошибок

Методы на основе симплекса являются «предпочтительным» способом решения проблемы наименьших абсолютных отклонений. ^[7] Метод симплекса — это метод решения проблемы линейного программирования. Самым популярным алгоритмом является модифицированный алгоритм симплекса Барродейла-Робертса. Алгоритмы для IRLS, метода Весоловски и метода Ли можно найти в Приложении A к ^[7] среди других методов. Проверка всех комбинаций линий, пересекающих любые две точки данных (x, y), является еще одним методом нахождения линии наименьших абсолютных отклонений. Поскольку известно, что по крайней мере одна линия наименьших абсолютных отклонений пересекает по крайней мере две точки данных, этот метод найдет линию, сравнивая SAE (наименьшую абсолютную ошибку по точкам данных) каждой линии и выбирая линию с наименьшей SAE. Кроме того, если несколько линий имеют одинаковую наименьшую SAE, то линии очерчивают область множественных решений. Несмотря на простоту, этот окончательный метод неэффективен для больших наборов данных.

Решение с использованием линейного программирования

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

${\displaystyle {\text{Minimize}}\sum _{i=1}^{n}|y_{i}-a_{0}-a_{1}x_{i1}-a_{2}x_{i2}-\cdots -a_{k}x_{ik}|}$

относительно выбора значений параметров , где y _i — значение i ^-го наблюдения зависимой переменной, а x _ij — значение i- ^го наблюдения j ^-й независимой переменной ( j = 1,..., k ). Перепишем эту задачу в терминах искусственных переменных u _i как ${\displaystyle a_{0},\ldots ,a_{k}}$

${\displaystyle {\text{Minimize}}\sum _{i=1}^{n}u_{i}}$

в отношении и ${\displaystyle a_{0},\ldots ,a_{k}}$ ${\displaystyle u_{1},\ldots ,u_{n}}$

при условии

${\displaystyle u_{i}\geq y_{i}-a_{0}-a_{1}x_{i1}-a_{2}x_{i2}-\cdots -a_{k}x_{ik}\,\ \,\ \,\ \,\ \,\ {\text{for }}i=1,\ldots ,n}$

${\displaystyle u_{i}\geq -[y_{i}-a_{0}-a_{1}x_{i1}-a_{2}x_{i2}-\cdots -a_{k}x_{ik}]\,\ \,\ {\text{ for }}i=1,\ldots ,n.}$

Эти ограничения приводят к тому, что при минимизации все они становятся равными , поэтому целевая функция эквивалентна исходной целевой функции. Поскольку эта версия постановки задачи не содержит оператора абсолютного значения, она находится в формате, который может быть решен с помощью любого пакета линейного программирования. ${\displaystyle u_{i}}$ ${\displaystyle |y_{i}-a_{0}-a_{1}x_{i1}-a_{2}x_{i2}-\cdots -a_{k}x_{ik}|}$

Характеристики

Существуют и другие уникальные свойства линии наименьших абсолютных отклонений. В случае набора данных ( x , y ) линия наименьших абсолютных отклонений всегда будет проходить по крайней мере через две точки данных, если только не существует множественных решений. Если существует множественные решения, то область допустимых решений наименьших абсолютных отклонений будет ограничена по крайней мере двумя линиями, каждая из которых проходит по крайней мере через две точки данных. В более общем смысле, если есть k регрессоров (включая константу), то по крайней мере одна оптимальная регрессионная поверхность пройдет через k точек данных. ^{[8] : стр.936}

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

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

Рисунок A: Набор точек данных с симметрией отражения и решениями с несколькими наименьшими абсолютными отклонениями. «Область решения» показана зеленым цветом. Вертикальные синие линии представляют абсолютные ошибки от розовой линии до каждой точки данных. Розовая линия — одно из бесконечного множества решений в зеленой области.

Чтобы понять, почему в случае, показанном на рисунке A, существует несколько решений, рассмотрим розовую линию в зеленой области. Ее сумма абсолютных ошибок составляет некоторое значение S. Если бы мы немного наклонили линию вверх, сохраняя ее в пределах зеленой области, сумма ошибок все еще была бы S. Она не изменилась бы, поскольку расстояние от каждой точки до линии увеличивается с одной стороны линии, в то время как расстояние до каждой точки с противоположной стороны линии уменьшается на точно такую ​​же величину. Таким образом, сумма абсолютных ошибок остается прежней. Кроме того, поскольку можно наклонять линию на бесконечно малые приращения, это также показывает, что если есть более одного решения, то решений бесконечно много.

Преимущества и недостатки

Ниже приведена таблица, в которой некоторые свойства метода наименьших абсолютных отклонений сравниваются со свойствами метода наименьших квадратов (для невырожденных задач). ^{[9] [10]}

*При условии, что количество точек данных больше или равно количеству признаков.

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

Вариации, расширения, специализации

Если в сумме абсолютных значений остатков обобщить функцию абсолютного значения до наклонной функции абсолютного значения, которая на левой полупрямой имеет наклон , а на правой полупрямой имеет наклон , где , то получим квантильную регрессию . Случай дает стандартную регрессию по наименьшим абсолютным отклонениям и также известен как медианная регрессия . ${\displaystyle \tau -1}$ ${\displaystyle \tau }$ ${\displaystyle 0<\tau <1}$ ${\displaystyle \tau =1/2}$

Проблема наименьшего абсолютного отклонения может быть расширена для включения множественных объяснений, ограничений и регуляризации , например, линейная модель с линейными ограничениями: ^[11]

минимизировать ${\displaystyle S(\mathbf {\beta } ,b)=\sum _{i}|\mathbf {x} '_{i}\mathbf {\beta } +b-y_{i}|}$

при условии, например, ${\displaystyle \mathbf {x} '_{1}\mathbf {\beta } +b-y_{1}\leq k}$

где — вектор-столбец коэффициентов, подлежащих оценке, b — отсекаемый отрезок, подлежащий оценке, x _i — вектор-столбец i- ^х наблюдений по различным объясняющим переменным, y _i — i ^-е наблюдение по зависимой переменной, а k — известная константа. ${\displaystyle \mathbf {\beta } }$

Регуляризация с помощью LASSO (оператор наименьшего абсолютного сжатия и выбора) также может быть объединена с LAD. ^[12]

Смотрите также

• Геометрическая медиана
• Квантильная регрессия
• Регрессионный анализ
• Модель линейной регрессии
• Абсолютное отклонение
• Среднее абсолютное отклонение
• Среднее абсолютное отклонение
• Обычный метод наименьших квадратов
• Надежная регрессия

Ссылки

1. "Регрессия наименьшего абсолютного отклонения". Краткая энциклопедия статистики . Springer. 2008. стр. 299–302. doi :10.1007/978-0-387-32833-1_225. ISBN 9780387328331.
2. Barrodale, I.; Roberts, FDK (1973). «Улучшенный алгоритм для дискретной линейной аппроксимации L _{1 ».} SIAM Journal on Numerical Analysis . 10 (5): 839–848. Bibcode : 1973SJNA...10..839B. doi : 10.1137/0710069. hdl : 1828/11491 . JSTOR  2156318.
3. Schlossmacher, EJ (декабрь 1973 г.). «Итеративный метод подгонки кривой абсолютных отклонений». Журнал Американской статистической ассоциации . 68 (344): 857–859. doi :10.2307/2284512. JSTOR  2284512.
4. Весоловски, ГО (1981). «Новый алгоритм спуска для задачи регрессии наименьшего абсолютного значения». Communications in Statistics – Simulation and Computation . B10 (5): 479–491. doi :10.1080/03610918108812224.
5. Ли, Иньбо; Арсе, Гонсало Р. (2004). «Подход максимального правдоподобия к регрессии наименьшего абсолютного отклонения». Журнал EURASIP по прикладной обработке сигналов . 2004 (12): 1762–1769. Bibcode : 2004EJASP2004...61L. doi : 10.1155/S1110865704401139 .
6. Кржич, Ана Сович; Сершич, Дамир (2018). «Минимизация L1 с использованием рекурсивного уменьшения размерности». Обработка сигналов . 151 : 119–129. doi :10.1016/j.sigpro.2018.05.002.
7. Уильям А. Пфейл, Статистические учебные пособия , диссертация бакалавра наук, Вустерский политехнический институт , 2006 г.
8. Бранхам, Р. Л., младший, «Альтернативы наименьшим квадратам», Astronomical Journal 87, июнь 1982 г., стр. 928–937. [1] в SAO/NASA Astrophysics Data System (ADS)
9. Набор апплетов, демонстрирующих эти различия, можно найти на следующем сайте: http://www.math.wpi.edu/Course_Materials/SAS/lablets/7.3/73_choices.html
10. Для обсуждения LAD и OLS см. эти научные статьи и отчеты: http://www.econ.uiuc.edu/~roger/research/rq/QRJEP.pdf и https://www.leeds.ac.uk/educol/documents/00003759.htm
11. Ши, Мингрен; Марк А., Лукас (март 2002 г.). «Алгоритм оценки L1 с вырожденностью и линейными ограничениями». Computational Statistics & Data Analysis . 39 (1): 35–55. doi :10.1016/S0167-9473(01)00049-4.
12. Ван, Ли; Гордон, Майкл Д.; Чжу, Цзи (декабрь 2006 г.). «Регуляризованная регрессия наименьших абсолютных отклонений и эффективный алгоритм настройки параметров». Труды Шестой международной конференции по интеллектуальному анализу данных . стр. 690–700. doi :10.1109/ICDM.2006.134.

Дальнейшее чтение

• Питер Блумфилд ; Уильям Штайгер (1980). «Подгонка кривой наименьших абсолютных отклонений». Журнал SIAM по научным вычислениям . 1 (2): 290–301. doi :10.1137/0901019.
• Субхаш К. Нарула и Джон Ф. Веллингтон (1982). «Минимальная сумма абсолютных ошибок регрессии: обзор современного состояния». Международный статистический обзор . 50 (3): 317–326. doi :10.2307/1402501. JSTOR  1402501.
• Роберт Ф. Филлипс (июль 2002 г.). «Оценка наименьших абсолютных отклонений с помощью алгоритма EM». Статистика и вычисления . 12 (3): 281–285. doi :10.1023/A:1020759012226.
• Энно Симсен и Кеннет А. Боллен (2007). «Оценка наименьшего абсолютного отклонения в моделировании структурных уравнений». Социологические методы и исследования . 36 (2): 227–265. doi :10.1177/0049124107301946.