Существуют ли алгоритмы для вычисления «работающих» параметров линейной или логистической регрессии?

32

В документе «Точное вычисление текущей дисперсии» по адресу http://www.johndcook.com/standard_deviation.html показано, как вычислить среднее значение, дисперсию и стандартные отклонения.

Существуют ли алгоритмы, в которых параметры модели линейной или логистической регрессии можно аналогичным образом «динамически» обновлять при предоставлении каждой новой записи обучения?

1

С огромным обучающим набором или непрерывным входным потоком данных вы можете использовать итерационные алгоритмы, такие как Stochastic Gradient Descent, и захватывать ввод небольшими партиями по мере продвижения. Это то, что вы спрашивали?

andreister

1

Алгоритм поиска RLS и его варианты. en.wikipedia.org/wiki/Recursive_least_squares_filter

Memming

20

Линейные коэффициенты регрессии : и . $y = ax + b$ $a = cov(x,y)/var(x)$ $b = mean(y) - a \cdot mean(x)$

Так что все, что вам действительно нужно, это инкрементный метод для вычисления . Из этого значения и дисперсии и среднего значения и можно вычислить параметры и . Как вы увидите в приведенном ниже псевдокоде, инкрементальное вычисление очень похоже на инкрементальное вычисление . Это не должно быть сюрпризом, потому что . $cov(x,y)$ $x$ $y$ $x$ $a$ $b$ $cov(x,y)$ $var(x)$ $var(x) = cov(x,x)$

Вот псевдокод, который вы, вероятно, ищете:

init(): meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0

update(x,y):
n += 1
dx = x - meanX
dy = y - meanY
varX += (((n-1)/n)*dx*dx - varX)/n
covXY += (((n-1)/n)*dx*dy - covXY)/n
meanX += dx/n
meanY += dy/n

getA(): return covXY/varX
getB(): return meanY - getA()*meanX

Я нашел этот вопрос во время поиска эквивалентного алгоритма, постепенно многовариантную регрессию как так что $R = (X'X)^{-1}X'Y$ $XR = Y+\epsilon$

chmike
источник

4

Спасибо Вам за Ваш вклад! Часть вопроса о линейной регрессии на самом деле является дубликатом stats.stackexchange.com/questions/6920/… , ответы на который показывают, как обновить модель множественной линейной регрессии. Нынешняя тема может стоять, потому что часть вопроса о логистической регрессии не представляет интереса. На самом деле, даже логистическая часть была продублирована на stats.stackexchange.com/questions/59174/… .

whuber

1

Я подумал, что этот ответ будет полезен, учитывая справочный текст, приведенный в вопросе. Спасибо за ссылку. Однако это не то, что я ищу. Мой случай использования, по-видимому, особенный.

chmike

3

Я считаю, что это может быть полезно и уникально в предложении рабочего кода.

whuber

Могу я спросить вас, почему вы позволяете dx * dy times (n-1) / n?

FavorMylikes

Можете ли вы улучшить код для расчета p-значения?

Натан,

12

Для ваших двух конкретных примеров:

Линейная регрессия В статье Александра Стреля и Майкла Литтмана «Линейная регрессия в режиме онлайн и ее применение к обучению на основе моделей» описывается алгоритм «Линейная регрессия KWIK» (см. Алгоритм 1), который обеспечивает приближение к решению линейной регрессии с использованием инкрементных обновлений. , Обратите внимание, что это не регуляризовано (т. Е. Это не регрессия Риджа). Я почти уверен, что метод Strehl & Littman не может распространяться на этот параметр.

Логистическая регрессия

Эта тема проливает свет на этот вопрос. Цитирование:

Даже без ограничения регуляризации логистическая регрессия является нелинейной задачей оптимизации. Уже это не имеет аналитического решения, которое обычно является предпосылкой для получения решения для обновления. С ограничением регуляризации это становится ограниченной задачей оптимизации. Это вводит совершенно новый набор неаналитических осложнений в дополнение к тем, которые уже были в безусловной проблеме.

Однако существуют и другие онлайн (или инкрементные) методы регрессии, которые вы, возможно, захотите посмотреть, например, Локально-взвешенная регрессия проекции (LWPR).

TDC
источник

Что касается логистической регрессии, я думаю, что вы излишне пессимистичны. Логистическая регрессия эквивалентна вычислению вероятностей апостериорных классов для задачи двух классов с распределением по Гауссу каждого класса с различными средствами и общей ковариацией. MLE для ковариации - это просто взвешенная сумма ковариаций для каждого класса, поэтому достаточные статистические данные - это просто число, сумма и сумма квадратов для каждого класса. Очевидно, что легко создать точное обновление, используя достаточную статистику.

Роберт Додье

3

@RobertDodier Вы описали линейный дискриминантный анализ, а не логистическую регрессию. Последний абзац вводного раздела здесь разъясняет отношения.

Ахфосс

@ahfoss Даже если данные для каждого класса обычно не распространяются, все равно можно построить модель, эквивалентную логистической регрессии через ковариации для каждого класса.

Роберт Додье

1

@RobertDodier Что такое эквивалентная модель? Вы, кажется, намекаете, что есть очевидное решение по существу сложной проблемы. Ваше решение или более блестящее, чем вы думаете, или гораздо меньше.

Ахфосс

11

Как общий принцип:

0) вы ведете достаточную статистику и текущие оценки ML

1) при получении новых данных обновите достаточную статистику и оценки

2) Если у вас нет достаточной статистики, вам нужно использовать все данные.

3) Как правило, у вас нет закрытых решений; используйте предыдущие MLE в качестве отправной точки, используйте некоторый удобный метод оптимизации, чтобы найти новый оптимум оттуда. Возможно, вам придется немного поэкспериментировать, чтобы найти, какие подходы лучше всего подходят для ваших конкретных типов проблем.

Если ваша проблема имеет особую структуру, вы, вероятно, можете ее использовать.

Пара потенциальных ссылок, которые могут иметь или не иметь какое-то значение:

McMahan, HB и M. Streeter (2012), «
Открытая проблема: лучшие границы для онлайн-логистической регрессии» ,
JMLR: материалы семинаров и конференций , том 23, 44.1–44.3

Пенни, У.Д. и С.Дж. Робертс (1999),
Динамическая логистическая регрессия ,
Труды IJCNN '99

Glen_b - Восстановить Монику
источник

Я согласен с идеей сохранения достаточных статистических данных (если они существуют для проблемы), но не делает ли наличие достаточных статистических данных ненужными другие материалы? Если у вас есть достаточная статистика, вы можете вычислить обновленные параметры точно так же, как если бы вы использовали весь набор данных. Нет необходимости принимать во внимание текущие параметры и не нужно экспериментировать с методами оптимизации.

Роберт Додье

2

Важно отметить, что наличие достаточной статистики не означает, что у вас есть решение уравнений.

Glen_b

8

В добавление к ответу tdc, нет известных методов для вычисления точных оценок коэффициентов в любой момент времени с постоянным временем на одну итерацию. Однако есть несколько альтернатив, которые являются разумными и интересными.

Первая модель, на которую стоит обратить внимание - это онлайн-обучение . В этой настройке мир сначала объявляет значение x, ваш алгоритм предсказывает значение для y, мир объявляет истинное значение y ', и ваш алгоритм терпит убытки l (y, y'). Для этого параметра известно, что простые алгоритмы (градиентный спуск и экспоненциальный градиент, среди прочих) достигают сублинейного сожаления. Это означает, что, как вы видите больше примеров, количество дополнительных ошибок, которые ваш алгоритм делает (по сравнению с наилучшим из возможных линейных предикторов), не увеличивается с количеством примеров. Это работает даже в состязательных настройках. Есть хорошая статья, объясняющая одну популярную стратегию, чтобы доказать эти границы сожаления. Лекционные записи Шая Шалева-Шварца также полезны.

Существует расширение настройки онлайн-обучения, называемое настройкой бандита, где вашему алгоритму присваивается только число, представляющее, насколько оно ошибочно (и нет указателя на правильный ответ). Впечатляет, что многие результаты онлайн-обучения переносятся на эту настройку, за исключением того, что здесь вынуждают исследовать и эксплуатировать, что приводит к всевозможным интересным задачам.

Александр Пассос
источник

6

Другие ответы указывают на мир машинного обучения, и это, безусловно, одно место, где эта проблема была решена.

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

Обновление QR-факторизации и проблемы наименьших квадратов Хаммерлинга и Лукаса.

источник

5

{год}_{T} знак равно β_{T} \cdot {Икс}_{T} + ε_{T}, β_{T} знак равно β_{T - 1} + η_{T}

$y_t = \beta_t\cdot x_t + \varepsilon_t, \\ \beta_t = \beta_{t-1}+ \eta_t$

β_{T} знак равно β_{T - 1}

$\beta_t = \beta_{t-1}$

{год}_{T} знак равно L о г я T (β_{T} \cdot {Икс}_{T} + ε_{T}), β_{T} знак равно β_{T - 1} + η_{T}

$y_t = logit(\beta_t\cdot x_t + \varepsilon_t), \\ \beta_t = \beta_{t-1}+ \eta_t$

Kochede
источник

2

Это добавить к ответу @chmike.

Похоже, что этот метод аналогичен онлайн-алгоритму BP Welford для стандартного отклонения, который также вычисляет среднее значение. Джон Кук дает хорошее объяснение здесь . Тони Финч в 2009 году предлагает метод экспоненциального скользящего среднего и стандартного отклонения:

diff := x – mean 
incr := alpha * diff 
mean := mean + incr 
variance := (1 - alpha) * (variance + diff * incr)

Вглядываясь в ранее опубликованный ответ и расширяя его, чтобы включить экспоненциальное окно перемещения:

init(): 
    meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0,
    meanXY = 0, varY = 0, desiredAlpha=0.01 #additional variables for correlation

update(x,y):
    n += 1
    alpha=max(desiredAlpha,1/n) #to handle initial conditions

    dx = x - meanX
    dy = y - meanY
    dxy = (x*y) - meanXY #needed for cor

    varX += ((1-alpha)*dx*dx - varX)*alpha
    varY += ((1-alpha)*dy*dy - varY)*alpha #needed for corXY
    covXY += ((1-alpha)*dx*dy - covXY)*alpha

    #alternate method: varX = (1-alpha)*(varX+dx*dx*alpha)
    #alternate method: varY = (1-alpha)*(varY+dy*dy*alpha) #needed for corXY
    #alternate method: covXY = (1-alpha)*(covXY+dx*dy*alpha)

    meanX += dx * alpha
    meanY += dy * alpha
    meanXY += dxy  * alpha

getA(): return covXY/varX
getB(): return meanY - getA()*meanX
corXY(): return (meanXY - meanX * meanY) / ( sqrt(varX) * sqrt(varY) )

В вышеприведенном «коде» для параметра selectedAlpha может быть установлено значение 0, и в этом случае код будет работать без экспоненциального взвешивания. Может быть предложено установить значение требуемой Альфа 1 / требуемый размер окна, как предложено Modified_moving_average для размера движущегося окна.

Дополнительный вопрос: об альтернативных расчетах выше, какие комментарии лучше с точки зрения точности?

Ссылки:

chmike (2013) https://stats.stackexchange.com/a/79845/70282

Кук, Джон (й) вычисление работает точно дисперсии http://www.johndcook.com/blog/standard_deviation/

Финч, Тони. (2009) Инкрементальный расчет средневзвешенного значения и дисперсии. https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf

Wikipedia. (nd) онлайн-алгоритм Уэлфорда https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm

Крис
источник

Существуют ли алгоритмы для вычисления «работающих» параметров линейной или логистической регрессии?

Ответы: