Я анализирую некоторые данные, в которых я хотел бы выполнить обычную линейную регрессию, однако это невозможно, поскольку я имею дело с настройкой в режиме онлайн с непрерывным потоком входных данных (который быстро станет слишком большим для памяти), и мне необходимо обновить оценки параметров, пока они потребляются. т.е. я не могу просто загрузить все это в память и выполнить линейную регрессию для всего набора данных.
Я предполагаю простую модель линейной многомерной регрессии, т.е.
Каков наилучший алгоритм для создания постоянно обновляемой оценки параметров линейной регрессии и ?б
Идеально:
- Мне бы хотелось, чтобы алгоритм с наибольшим пространством и временем на обновление, где - размерность независимой переменной ( ), а - размерность зависимой переменной ( ).N x M y
- Я хотел бы иметь возможность указать какой-либо параметр, чтобы определить, насколько параметры обновляются каждым новым образцом, например, 0,000001 будет означать, что следующий образец даст одну миллионную часть оценки параметра. Это дало бы некоторый экспоненциальный спад влияния образцов в далеком прошлом.
Ответы:
Майндональд описывает последовательный метод, основанный на вращениях Гивенса . (Вращение Гивенса - это ортогональное преобразование двух векторов, которое обнуляет данную запись в одном из векторов.) На предыдущем шаге вы разложили матрицу проекта в треугольную матрицу через ортогональное преобразование так что . (Получить результаты регрессии быстро и просто из треугольной матрицы.) Присоединив новую строку ниже , вы эффективно расширяете ненулевой строкой тоже скажиT Q Q X = ( T , 0 ) ′ v X ( T , 0 ) ′ t T T t T QX T Q QX=(T,0)′ v X (T,0)′ t , Задача состоит в том, чтобы обнулить эту строку, сохраняя записи в позиции диагонали . Последовательность вращений Гивенса делает это: вращение с первой строкой обнуляет первый элемент ; затем вращение со второй строкой обнуляет второй элемент и так далее. Эффект заключается в предварительном умножении серией вращений, что не меняет ее ортогональности.T T t T Q
Когда матрица проектирования имеет столбцы (что имеет место при регрессии на переменных плюс константа), необходимое количество вращений не превышает и каждый поворот меняет два вектора. Память, необходимая для составляет . Таким образом, этот алгоритм имеет вычислительную стоимость как во времени, так и в пространстве.p p + 1 p + 1 T O ( ( p + 1 ) 2 ) O ( ( p + 1 ) 2 )p+1 p p+1 p+1 T O((p+1)2) O((p+1)2)
Подобный подход позволяет определить влияние регрессии на удаление строки. Майндональд дает формулы; как и Белсли, Кух и Уэльс . Таким образом, если вы ищете движущееся окно для регрессии, вы можете сохранить данные для окна в круговом буфере, примыкая к новому элементу данных и отбрасывая старый при каждом обновлении. Это удваивает время обновления и требует дополнительной памяти для окна шириной . Похоже, что будет аналогом параметра влияния.k 1 / kO(k(p+1)) k 1/k
Для экспоненциального затухания, я думаю (умозрительно), что вы могли бы адаптировать этот подход к взвешенным наименьшим квадратам, придавая каждому новому значению вес, больший 1. Не должно быть необходимости поддерживать буфер предыдущих значений или удалять любые старые данные.
Рекомендации
JH Maindonald, Статистические вычисления. J. Wiley & Sons, 1984. Глава 4.
Д. А. Белсли, Е. Кух, Р. Уэлш. Регрессионная диагностика: идентификация влиятельных данных и источников коллинеарности. J. Wiley & Sons, 1980.
источник
Я думаю, что преобразование вашей модели линейной регрессии в модель пространства состояний даст вам то, что вам нужно. Если вы используете R, вы можете использовать пакет dlm и взглянуть на книгу-компаньон Petris et al.
источник
Вы всегда можете просто выполнить градиентный спуск по сумме квадратов стоят WRT параметров вашей модели . Просто возьмите его градиент, но не используйте решение для закрытой формы, а только для направления поиска.E W
Пусть является стоимость i - й обучающей выборки , учитывая параметры . Ваше обновление для параметра j'th тогдаE(i;W) W
где - это скорость шага, которую вы должны выбрать с помощью перекрестной проверки или надлежащей меры.α
Это очень эффективно и способ обучения нейронных сетей. Вы можете обрабатывать даже много сэмплов параллельно (скажем, 100 или около того) эффективно.
Конечно, могут быть применены более сложные алгоритмы оптимизации (импульс, сопряженный градиент, ...).
источник
Удивлен, никто больше не коснулся этого до сих пор. Линейная регрессия имеет квадратичную целевую функцию. Таким образом, ньютоновский шаг Рафсона из любой отправной точки ведет вас прямо к оптиме. Теперь предположим, что вы уже выполнили линейную регрессию. Целевая функция:
Теперь вы получили некоторые прошлые данные, выполнили линейную регрессию и работаете с вашими параметрами ( ). Градиент в этой точке равен нулю по определению. Гессиан, как указано выше. Новая точка данных ( ) прибывает. Вы просто рассчитываете градиент для новой точки через:β xnew,ynew
Добавьте это к старому гессиану, указанному выше. Затем просто сделайте шаг Ньютона Рафсона.
И вы сделали.
источник
Стандартный метод наименьших квадратов дает коэффициенты регрессии
где X - это матрица из M значений для каждой из N точек данных, и имеет размер NXM. Y - матрица выходов NX1. конечно матрица коэффициентов MX1. (Если вы хотите перехват, просто сделайте один набор х равным всегда 1.)β
Предположительно, чтобы сделать это онлайн, вам просто нужно отслеживать и , то есть одну матрицу MXM и одну матрицу MX1. Каждый раз, когда вы получаете новую точку данных, вы обновляете эти элементы , а затем снова вычисляете , что стоит вам инверсии матрицы MXM и умножения матрицы MXM и матрицы MX1.XTX XTY M2+M β
Например, если M = 1, то один коэффициент
поэтому каждый раз, когда вы получаете новую точку данных, вы обновляете обе суммы, вычисляете коэффициент и получаете обновленный коэффициент.
Если вы хотите геометрически ослабить более ранние оценки, я полагаю, что вы могли бы взвешивать и на каждый раз перед добавлением нового члена, где - это небольшое число.X T Y ( 1 - λ ) λXTX XTY (1−λ) λ
источник
Проблему легче решить, если немного переписать вещи:
Y = y
X = [x, 1]
тогда
Y = A * X
Одноразовое решение найдено путем расчета
V = X '* X
а также
C = X '* Y
обратите внимание, что V должен иметь размер N-by-N, а C - размер N-by-M. Параметры, которые вы ищете, затем определяются как:
A = inv (V) * C
Поскольку и V, и C рассчитываются путем суммирования по вашим данным, вы можете рассчитать A для каждой новой выборки. Однако это имеет временную сложность O (N ^ 3).
Поскольку V является квадратным и полуопределенным положительным, LU-разложение существует, что делает инвертирование V численно более устойчивым. Существуют алгоритмы для обновления ранга 1 для обратной матрицы. Найдите их, и вы получите эффективную реализацию, которую вы ищете.
Алгоритмы обновления ранга 1 можно найти в «Матричных вычислениях» Голуба и Ван Лоан. Это сложный материал, но он имеет исчерпывающий обзор таких алгоритмов.
Примечание: метод выше дает оценку наименьших квадратов на каждом шаге. Вы можете легко добавлять веса к обновлениям X и Y. Когда значения X и Y становятся слишком большими, они могут масштабироваться одним скаляром, не влияя на результат.
источник