재귀 (온라인) 정규화 된 최소 제곱 알고리즘 온라인 (재귀) 알고리즘의 방향을 알려 줄

누구든지 Tikhonov 정규화 (정규 최소 제곱)에 대한 온라인 (재귀) 알고리즘의 방향을 알려 줄 수 있습니까?

오프라인 설정에서 n-fold cross validation을 사용하여 λ 를 찾은 원래 데이터 세트를 사용하여

β^=(XTX+λI)1XTY

를 계산 합니다. y = x ^ T \ hat \ beta를 사용하여 주어진 x에 대해 새로운 y 값을 예측할 수 있습니다 .

λ

y

x

y=xTβ^

온라인 설정에서 나는 지속적으로 새로운 데이터 포인트를 그립니다. 전체 데이터 세트 (원본 + 신규)에서 전체 재 계산을 수행하지 않고 새로운 추가 데이터 샘플을 그릴 때 \ hat \ beta를 어떻게 업데이트 할 수

β^

있습니까?



답변

β^n=(XXT+λI)1i=0n1xiyi

하자 , 다음

Mn1=(XXT+λI)1

β^n+1=Mn+11(i=0n1xiyi+xnyn)

Mn+1Mn=xnxnT

, 우리는 얻을 수 있습니다

β^n+1=β^n+Mn+11xn(ynxnTβ^n)

에 따르면 우드 베리 공식 , 우리가

Mn+11=Mn1Mn1xnxnTMn1(1+xnTMn1xn)

결과적으로

β^n+1=β^n+Mn11+xnTMn1xnxn(ynxnTβ^n)

Polyak 평균화
를 사용하여 을 범위가 근사값에 사용할 수 있음을 나타냅니다. 에 . 귀하의 경우 재귀에 가장 적합한 를 선택하려고 시도 할 수 있습니다 .M 1 n

ηn=nα

α0.51α

Mn11+xnTMn1xn

α

0.5

1

α


배치 그라디언트 알고리즘을 적용하면 작동한다고 생각합니다.

β^n+1=β^n+ηnni=0n1xi(yixiTβ^n)


답변

지금까지 아무도 다루지 않은 점은 일반적 으로 데이터 포인트가 추가 될 때 정규화 매개 변수 일정하게 유지하는 것이 의미가 없다는 것 입니다. 그 이유는 는 일반적으로 데이터 포인트 수에 따라 선형 적으로 증가하지만 정규화 용어 는 그렇지 않습니다. X β Y 2λ

λ

Xβy2

λβ2


답변

아마도 확률 적 그라디언트 디센트 와 같은 것이 여기에서 작동 할 수 있습니다. 계산 초기 데이터 세트에 위의 식을 이용하여, 즉 당신의 시작 예상됩니다. 각각의 새로운 데이터 포인트에 대해 한 단계의 경사 하강을 수행하여 모수 추정치를 업데이트 할 수 있습니다.

β^


답변

선형 회귀 분석에서 한 가지 가능성은 여기에 설명 된대로 의 QR 분해를 직접 업데이트하는 입니다. 새로운 각 데이터 포인트가 추가 된 후 를 다시 추정하지 않는 한 능선 회귀로 매우 유사한 것을 수행 할 수 있다고 생각합니다.λ

X

λ


답변

다음은 Woodbury 수식을 사용하는 것과 비교하여 대안이면서 덜 복잡한 방법입니다. 참고 와 같이 쓸 수있다 합계 . 우리는 온라인으로 물건을 계산하고 합계가 날아 가기를 원하지 않기 때문에 대체 수단 ( 및 )을 사용할 수 있습니다.

XTX

XTy

XTX/n

XTy/n

와 를 다음 과 같이 쓰면 :

X

y

X=(x1TxnT),y=(y1yn),

및 ( 번째 행 까지 계산)에 대한 온라인 업데이트를 다음과 같이 작성할 수 있습니다 .

XTX/n

XTy/n

t

At=(11t)At1+1txtxtT,

bt=(11t)bt1+1txtyt.

그러면 의 온라인 견적 이됩니다

β

β^t=(At+λI)1bt.

이것은 관측치를 추가 할 때 일정하게 유지되는 해석에도 도움이됩니다 .

λ

이 절차는 https://github.com/joshday/OnlineStats.jl 이 선형 / 릿지 회귀의 온라인 추정치를 계산 하는 방법 입니다.


답변