Метод наименьших модулей

[MestnyBomzh]

Как известно, для решения задачи регрессии обычно используют MSE метрику, то есть квадрат ошибки. При этом есть ещё одна метрика - MAE, модуль ошибки. Однако он неудобен тем, что он не дифференциируем в нуле. У меня вопрос: неужели это так критично, не дифференциируемость только лишь в одной точке? Тем более, что в этой точке ошибка равна нулю. Вообще, если я верно представляю, можно по градиенту двигаться и двигаться и в момент, когда мы попадем в точку, где не получится взять градиент => скажем, что мы нашли минимум. То есть нам и не нужен градиент в этой точке, как только мы не сможем найти градиент в точке - объявляем эту точку искомым минимумом. В чем проблема такого подхода?

[mihaild]

Недифференцируемость некритична - например, в нейронках активно используются функции типа $\operatorname{ReLU}(x) = x \cdot \mathbb{I}_{>0}(x)$ - через них модуль выражается.
И модуль вполне используется - например, при $l_1$ регуляризации, когда к функции ошибки добавляется $l_1$ норма весов. Такая регуляризация, в отличии от $l_2$, обычно приводит к разреженнным представлениям (большая часть коэффициентов близки к нулю).

На практике для большинства задач просто MSE интереснее, чем MAE - нам часто важнее, чтобы не было больших ошибок, чем чтобы маленькие были поменьше.

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

Это "поиски под фонарём". В том смысле, что под фонарём что-то да найдётся. Если целевая функция квадратична, то продифференцировав её для поиска минимума, придём к линейной системе уравнений. Которая решается. Решение единственно (ну, или бесконечно много дающих одинаковое значение невязки, мультиколлинеарность, но это лечится устранением лишнего из модели). И решить, в принципе, можно вручную (и решали больше века). А когда решили, опять же в силу того, что производные линейны, легко получаем оценки дисперсий коэффициентов и т.п. полезное.
Метод наименьших модулей приводит к задаче линейного программирования, методы решения которой это уже середина ХХ века, и вручную решать можно лишь в порядке воспитания воли. При этом решение не обязано быть однозначным даже при отсутствии избыточности переменных, зато возможна неустойчивость.

Вот пример неоднозначности, одинаковое значение ЦФ на любой прямой, проходящей в "зелёной области", а если внести малое возмущение в значение одного из наблюдений, может получить однозначный ответ, но "переключаемый" в зависимости от возмущения.
Линейной программирование не единственный метод, можно, например, использовать МНК, вводя веса так, чтобы взвешенные суммы квадратов были бы пропорциональны абсолютным значениям (чего добиваются итеративно). Это тоже усложнение алгоритма и не гарантирует единственности.

[mserg]

Если под модулем имеем "линейность", то MAE, в принципе, тоже приводит к линейному программированию.
Модуль заменяется с помощью двух переменных.
Например, если требуется
$|y| -> min$
то делаем замену
$y=x_1-x_2$
$|y|=x_1+x_2$
Т.е. получаем линейный целевую функцию и линейные ограничения.
Простые градиентные алгоритмы, наверное, имеют право на существование, однако в случае возникновения симметрий / вырожденности и т.п. видимо "сломаются".

[MestnyBomzh]

Судя по тому, что написали выше, проблем решить задачу с метрикой MAE не составляет труда. Тогда вопрос такой: так как MSE чувствительно к выбросам (мы же возводим ошибку в квадрат), то не лучше ли тогда использовать MAE? раз проблем при численном решении нет, то почему нет?

[ewert]

MestnyBomzh в сообщении #1253516 писал(а):

раз проблем при численном решении нет, то почему нет?

Они есть, и серьёзные. Трудоёмкость линейного программирования многократно превышает трудоёмкость МНК.

[MestnyBomzh]

Насколько я знаю - МНК решается с помощью градиентного спуска и его модификаций. Разве нельзя его же применить для решения MAE?

[ewert]

MestnyBomzh в сообщении #1253534 писал(а):

МНК решается с помощью градиентного спуска и его модификаций.

Во-первых, ни разу. Во всяком случае, если речь о классическом МНК, когда модель -- это некоторый обобщённый многочлен. Тогда всё сводится просто к системе линейных уравнений, которая прокручивается мгновенно.

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

[mserg]

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

Например, накидаем на линию $y=10$ - 1000 точек, а на линию $y=0$ - 1001 точку.

Аппроксимация константой $y=b$ приводит к оптимуму по MAE $y=0$ !
Аппроксимация прямой $y=kx+b$, возможно, приведет к тому же результату.

MAE наши 1000 выбросов "труба шатал", но не смог.

[Korvin]

Когда у меня смутная зависимость, я проверяю не только МНК (эксель это делает по ряду функций, в т.ч. полиномам степени до 6), но и по сумме модулей, и сумме квадратных корней из модулей, очень хорошо отсекает явные ошибки в измерениях. Хорошая зависимость проявляется во всех вариантах. Хотя да, если показатель степени брать очень малым, все преобразованные расстояния становятся единичными, а тогда какая разница, как проводить линию регрессии, сумма полюбому будет равна количеству точек. Решение неустойчиво.

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

MestnyBomzh в сообщении #1253534 писал(а):

Насколько я знаю - МНК решается с помощью градиентного спуска и его модификаций. Разве нельзя его же применить для решения MAE?

Для линейных задач - никогда (на всякий случай уточню, имеются в виду линейные по параметрам, то есть $y=a_0+a_1\sin t+a_2e^{t^2}+a+3\ln\frac {t^3}{1+t^2}$ линейна). Для них именно в силу квадратичности функции производные линейны, и решение сводится к однократному решению системы уравнений (симплекс-метод требует многократного повторения подобных шагов). То есть регрессию МНК руками посчитать возможно, МНМ - нет. И до определённого времени это было препятствие неодолимое. С доступностью компьютеров это стало вторичным возражением, на первое место вышли вопросы исследования решения (для МНК получить оценки дисперсий коэффициентов, доказать несмещённость и т.п. не просто, а очень просто, для МНМ нетривиально) и эффективности. Последняя, вообще говоря, будет разной для разных законов распределения ошибки. Для нормального МНК эффективен, скажем, для задачи определения параметра положения МНК оценка среднее арифметическое на 25% эффективнее МНМ-оценки - медианы. Если же предполагается отклонения от нормальности, эффективен может быть другой метод (и не обязательно МНМ, его триумф на двойном экспоненциальном).
В обычной практике статистики могут применять МНМ, как один из пакета робастных методов, для построения грубой модели, которая позволяет выявить "выбросы", затем их проанализировать (прежде всего нестатистическими методами, а исходя из содержательных соображений), а после их удаления использовать МНК.