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

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

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

Предположим, что набор данных состоит из точек ( x _i , y _i ) с i = 1, 2, ..., n . Мы хотим найти функцию f такую, что $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 .)

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

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

Решение

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

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

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

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

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

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

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

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

относительно

a_{0},\ldots ,a_{k}

и

u_{1},\ldots ,u_{n}

при условии

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

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.

Эти ограничения заставляют каждого $u_{i}$ равняться $|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), который путем возведения остатков в квадрат придает больший вес большим остаткам, то есть выбросам, в которых прогнозируемые значения далеки от фактических наблюдений. Это может быть полезно в исследованиях, в которых выбросам не нужно придавать больший вес, чем другим наблюдениям. Если важно придать больший вес выбросам, лучшим выбором будет метод наименьших квадратов.

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

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

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

минимизировать

S(\mathbf {\beta } ,b)=\sum _{i}|\mathbf {x} '_{i}\mathbf {\beta } +b-y_{i}|

при условии, например,

\mathbf {x} '_{1}\mathbf {\beta } +b-y_{1}\leq k

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

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

См. также

Ссылки

^ «Регрессия наименьшего абсолютного отклонения». Краткая энциклопедия статистики . Спрингер. 2008. С. 299–302 . дои : 10.1007/978-0-387-32833-1_225 . ISBN 9780387328331 .
^ Барродейл, И.; Робертс, ФДК (1973). «Улучшенный алгоритм дискретной линейной аппроксимации L ₁ ». SIAM Journal по численному анализу . 10 (5): 839–848. Бибкод : 1973SJNA...10..839B . дои : 10.1137/0710069 . hdl : 1828/11491 . JSTOR 2156318 .
^ Шлоссмахер, Э.Дж. (декабрь 1973 г.). «Итеративный метод подбора кривой абсолютных отклонений». Журнал Американской статистической ассоциации . 68 (344): 857–859. дои : 10.2307/2284512 . JSTOR 2284512 .
^ Весоловский, ГО (1981). «Новый алгоритм спуска для задачи регрессии наименьшего абсолютного значения». Коммуникации в статистике – моделирование и вычисления . Б10 (5): 479–491. дои : 10.1080/03610918108812224 .
^ Ли, Инбо; Арсе, Гонсало Р. (2004). «Подход максимального правдоподобия к регрессии наименьшего абсолютного отклонения» . Журнал EURASIP по прикладной обработке сигналов . 2004 (12): 1762–1769. Бибкод : 2004EJASP2004...61L . дои : 10.1155/S1110865704401139 .
^ Кржич, Ана Сович; Сершич, Дамир (2018). «Минимизация L1 с использованием рекурсивного уменьшения размерности». Обработка сигналов . 151 : 119–129. дои : 10.1016/j.sigpro.2018.05.002 .
^ Jump up to: Перейти обратно: ^а ^б Уильям А. Пфейл, Статистические учебные пособия , диссертация на степень бакалавра наук, Вустерский политехнический институт , 2006 г.
^ Бранхам, Р.Л.-младший, «Альтернативы методу наименьших квадратов», Astronomical Journal 87, июнь 1982 г., 928–937. [1] в Системе астрофизических данных (ADS) САО/НАСА.
^ Набор апплетов, демонстрирующих эти различия, можно найти на следующем сайте: http://www.math.wpi.edu/Course_Materials/SAS/lablets/7.3/73_choices.html.
^ Обсуждение LAD и OLS см. в этих научных статьях и отчетах: http://www.econ.uiuc.edu/~roger/research/rq/QRJEP.pdf и https://www.leeds.ac.uk. /educol/documents/00003759.htm
^ Ши, Мингрен; Марк А., Лукас (март 2002 г.). « Алгоритм оценки L ₁ с вырождением и линейными ограничениями» . Вычислительная статистика и анализ данных . 39 (1): 35–55. дои : 10.1016/S0167-9473(01)00049-4 .
^ Ван, Ли; Гордон, Майкл Д.; Чжу, Цзи (декабрь 2006 г.). «Регуляризованная регрессия наименьших абсолютных отклонений и эффективный алгоритм настройки параметров». Материалы шестой международной конференции по интеллектуальному анализу данных . стр. 690–700. дои : 10.1109/ICDM.2006.134 .

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

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

[1] «Регрессия наименьшего абсолютного отклонения». Краткая энциклопедия статистики . Спрингер. 2008. С. 299–302 . дои : 10.1007/978-0-387-32833-1_225 . ISBN 9780387328331 .

[2] Барродейл, И.; Робертс, ФДК (1973). «Улучшенный алгоритм дискретной линейной аппроксимации L ₁ ». SIAM Journal по численному анализу . 10 (5): 839–848. Бибкод : 1973SJNA...10..839B . дои : 10.1137/0710069 . hdl : 1828/11491 . JSTOR 2156318 .

[3] Шлоссмахер, Э.Дж. (декабрь 1973 г.). «Итеративный метод подбора кривой абсолютных отклонений». Журнал Американской статистической ассоциации . 68 (344): 857–859. дои : 10.2307/2284512 . JSTOR 2284512 .

[4] Весоловский, ГО (1981). «Новый алгоритм спуска для задачи регрессии наименьшего абсолютного значения». Коммуникации в статистике – моделирование и вычисления . Б10 (5): 479–491. дои : 10.1080/03610918108812224 .

[5] Ли, Инбо; Арсе, Гонсало Р. (2004). «Подход максимального правдоподобия к регрессии наименьшего абсолютного отклонения» . Журнал EURASIP по прикладной обработке сигналов . 2004 (12): 1762–1769. Бибкод : 2004EJASP2004...61L . дои : 10.1155/S1110865704401139 .

[6] Кржич, Ана Сович; Сершич, Дамир (2018). «Минимизация L1 с использованием рекурсивного уменьшения размерности». Обработка сигналов . 151 : 119–129. дои : 10.1016/j.sigpro.2018.05.002 .

[Pfeil-7] Jump up to: Перейти обратно: ^а ^б Уильям А. Пфейл, Статистические учебные пособия , диссертация на степень бакалавра наук, Вустерский политехнический институт , 2006 г.

[8] Бранхам, Р.Л.-младший, «Альтернативы методу наименьших квадратов», Astronomical Journal 87, июнь 1982 г., 928–937. [1] в Системе астрофизических данных (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 г.). « Алгоритм оценки L ₁ с вырождением и линейными ограничениями» . Вычислительная статистика и анализ данных . 39 (1): 35–55. дои : 10.1016/S0167-9473(01)00049-4 .

[12] Ван, Ли; Гордон, Майкл Д.; Чжу, Цзи (декабрь 2006 г.). «Регуляризованная регрессия наименьших абсолютных отклонений и эффективный алгоритм настройки параметров». Материалы шестой международной конференции по интеллектуальному анализу данных . стр. 690–700. дои : 10.1109/ICDM.2006.134 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]