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

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

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

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

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

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

${\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}|}$

по выбору значений параметров ${\displaystyle a_{0},\ldots ,a_{k}}$, где у_я стоимость я^th наблюдение за зависимой переменной и Икс_ij стоимость я^th наблюдение за j^th независимая переменная (j = 1,...,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}|}$ после минимизации, поэтому целевая функция эквивалентна исходной целевой функции. Поскольку эта версия постановки задачи не содержит оператора абсолютного значения, ее формат может быть решен с помощью любого пакета линейного программирования.

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

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

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

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

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

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

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

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

Регрессия методом наименьших квадратов	Регрессия наименьших абсолютных отклонений
Не очень прочный	Надежный
Стабильное решение	Неустойчивое решение
Одно решение *	Возможно несколько решений

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

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

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

Задача наименьшего абсолютного отклонения может быть расширена за счет включения нескольких объяснений, ограничений и регуляризация, например, линейная модель с линейными ограничениями:^[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}$

где ${\displaystyle \mathbf {\beta } }$ вектор-столбец коэффициентов для оценки, б это перехват, который нужно оценить, Икс_я вектор-столбец я^th замечания по поводу различных объяснений, у_я это я^th наблюдение за зависимой переменной, и k известная константа.

Регуляризация с ЛАССО также может сочетаться с LAD.^[12]

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

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

Рекомендации

1. «Регрессия наименьшего абсолютного отклонения». Краткая энциклопедия статистики. Springer. 2008. С.299 –302. Дои:10.1007/978-0-387-32833-1_225. ISBN  9780387328331.
2. И. Барродейл и Ф. Д. К. Робертс (1973). "Улучшенный алгоритм для дискретных L₁ линейное приближение ». Журнал SIAM по численному анализу. 10 (5): 839–848. Bibcode:1973SJNA ... 10..839B. Дои:10.1137/0710069. HDL:1828/11491. JSTOR  2156318.
3. Э. Дж. Шлосмахер (декабрь 1973 г.). «Итерационный метод подбора кривой абсолютных отклонений». Журнал Американской статистической ассоциации. 68 (344): 857–859. Дои:10.2307/2284512. JSTOR  2284512.
4. Весоловский Г.О. (1981). «Новый алгоритм спуска для задачи регрессии наименьшего абсолютного значения». Коммуникации в статистике - моделирование и вычисления. B10 (5): 479–491. Дои:10.1080/03610918108812224.
5. Иньбо Ли и Гонсало Р. Арсе (2004). «Подход максимального правдоподобия к регрессии с наименьшим абсолютным отклонением». Журнал EURASIP по прикладной обработке сигналов. 2004 (12): 1762–1769. Bibcode:2004EJASP2004 ... 61L. Дои:10.1155 / S1110865704401139.^{[постоянная мертвая ссылка ]}
6. Ана Сович Кшич и Дамир Серсич (2018). «Минимизация L1 с использованием рекурсивного уменьшения размерности». Обработка сигналов. 151: 119–129. Дои:10.1016 / j.sigpro.2018.05.002.
7. Уильям А. Пфейл,Статистические учебные пособия, Дипломная работа бакалавра наук, Вустерский политехнический институт, 2006
8. Бранхам, Р. Л., мл., "Альтернативы наименьших квадратов", Астрономический журнал 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 г.). "An L₁ алгоритм оценивания с вырожденностью и линейными ограничениями ». Вычислительная статистика и анализ данных. 39 (1): 35–55. Дои:10.1016 / S0167-9473 (01) 00049-4.
12. Ли Ван, Майкл Д. Гордон и Цзи Чжу (декабрь 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.