Линейная регрессия

Линейная регрессия является одним из известнейших методов регрессии, достаточно хорошо работающим в ряде простых задач. И, несмотря на наличие более совершенных методов, линейная регрессия нашла свою нишу. К достоинствам линейной регрессии можно отнести простоту алгоритма и высокое быстродействие. Недостаток только один, и он очевиден - неприспособленность к решению существенно нелинейных задач.

Содержание

    Линейная регрессия в ALGLIB
    Особенности и улучшения алгоритма
    Manual entries

Линейная регрессия в ALGLIB

Работа с линейными моделями в ALGLIB осуществляется в два этапа:

Построение линейной модели при помощи одной из подпрограмм (выбор конкретной подпрограммы зависит от особенностей решаемой задачи). Результатом работы является структура LinearModel, хранящая построенную модель.
Работа с полученной моделью (обработка данных, копирование/сериализация модели и т.д.).

Особенности и улучшения алгоритма

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

во-первых, перед началом работы пакет ALGLIB осуществляет стандартизацию переменных (применяя обратное преобразование к результату). Это улучшает численные свойства задачи и решает некоторые проблемы, которые могут возникать, если переменные плохо отмасштабированы.
во-вторых, пакет ALGLIB вычисляет кросс-валидационную оценку ошибки обобщения при помощи быстрого алгоритма, использующего формулу Шермана-Моррисона для обновления сингулярного разложения матрицы задачи при устранении из обучающего множества одного элемента. Использование быстрого алгоритма leave-one-out кросс-валидации позволяет получить оценку ошибки обобщения за время O(N·M), при условии, что известно сингулярное разложение матрицы (здесь N – размер обучающего множества, M – число переменных). Для сравнения – трудоемкость решения задачи линейной регрессии составляет O(N*M2), а процедура leave-one-out кросс-валидации при реализации без учета особенностей задачи потребует времени порядка O(N2*M2).

Следует отметить две особенности быстрого вычисления кросс-валидационной оценки. Во-первых, "быстрая" формула применима только к невырожденным задачам – если задача вырождена, её размерность должна быть понижена при помощи метода главных компонент. При необходимости это делается автоматически, но примерно вдвое замедляет алгоритм. Во-вторых, существуют более утонченные типы вырожденности – с точки зрения решения системы линейных уравнений задача невырождена, но формула Шермана-Моррисона оказывается неприменима к части векторов обучающего множества (для некоторых с виду обычных векторов она приводит к делению на ноль). Теоретически в обучающем множестве может быть до M+1 таких "дефектных" элементов (из N имеющихся), хотя чаще всего нет ни одного. Эти «дефектные» векторы не учитываются при расчете кросс-валидационной оценки ошибки, что несколько искажает результат алгоритма, но не является багом (на случай, если кто-то решит проверить правильность работы быстрой кросс-валидации и случайно наткнется на один из таких векторов).