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

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

오프라인 설정에서 n-fold cross validation을 사용하여 를 찾은 원래 데이터 세트를 사용하여 $\hat{β} = (X^{T} X + λ I)^{- 1} X^{T} Y$

\hat{β} = (X^{T} X + λ I)^{- 1} X^{T} Y

$\hat\beta=(X^TX+λI)^{−1}X^TY$ 를 계산 합니다. 사용하여 주어진 대해 새로운 값을 예측할 수 있습니다 . $λ$

λ

$λ$ $y$

y

$y$ $x$

x

$x$ $y = x^{T} \hat{β}$

y = x^{T} \hat{β}

$y=x^T\hat\beta$

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

\hat{β}

$\hat\beta$ 있습니까?

답변

${\hat{β}}_{n} = (X X^{T} + λ I)^{- 1} \sum_{i = 0}^{n - 1} x_{i} y_{i}$

{\hat{β}}_{n} = (X X^{T} + λ I)^{- 1} \sum_{i = 0}^{n - 1} x_{i} y_{i}

$\hat\beta_n=(XX^T+λI)^{−1} \sum\limits_{i=0}^{n-1} x_iy_i$

하자 , 다음 $M_{n}^{- 1} = (X X^{T} + λ I)^{- 1}$

M_{n}^{- 1} = (X X^{T} + λ I)^{- 1}

$M_n^{-1} = (XX^T+λI)^{−1}$

${\hat{β}}_{n + 1} = M_{n + 1}^{- 1} (\sum_{i = 0}^{n - 1} x_{i} y_{i} + x_{n} y_{n})$

{\hat{β}}_{n + 1} = M_{n + 1}^{- 1} (\sum_{i = 0}^{n - 1} x_{i} y_{i} + x_{n} y_{n})

$\hat\beta_{n+1}=M_{n+1}^{−1} (\sum\limits_{i=0}^{n-1} x_iy_i + x_ny_n)$ 및

$M_{n + 1} - M_{n} = x_{n} x_{n}^{T}$

M_{n + 1} - M_{n} = x_{n} x_{n}^{T}

$M_{n+1} - M_n = x_nx_n^T$ , 우리는 얻을 수 있습니다

${\hat{β}}_{n + 1} = {\hat{β}}_{n} + M_{n + 1}^{- 1} x_{n} (y_{n} - x_{n}^{T} {\hat{β}}_{n})$

{\hat{β}}_{n + 1} = {\hat{β}}_{n} + M_{n + 1}^{- 1} x_{n} (y_{n} - x_{n}^{T} {\hat{β}}_{n})

$\hat\beta_{n+1}=\hat\beta_{n}+M_{n+1}^{−1} x_n(y_n - x_n^T\hat\beta_{n})$

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

$M_{n + 1}^{- 1} = M_{n}^{- 1} - \frac{M_{n}^{- 1} x_{n} x_{n}^{T} M_{n}^{- 1}}{(1 + x_{n}^{T} M_{n}^{- 1} x_{n})}$

M_{n + 1}^{- 1} = M_{n}^{- 1} - \frac{M_{n}^{- 1} x_{n} x_{n}^{T} M_{n}^{- 1}}{(1 + x_{n}^{T} M_{n}^{- 1} x_{n})}

$M_{n+1}^{-1} = M_{n}^{-1} - \frac{M_{n}^{-1}x_nx_n^TM_{n}^{-1}}{(1+x_n^TM_n^{-1}x_n)}$

결과적으로

${\hat{β}}_{n + 1} = {\hat{β}}_{n} + \frac{M_{n}^{- 1}}{1 + x_{n}^{T} M_{n}^{- 1} x_{n}} x_{n} (y_{n} - x_{n}^{T} {\hat{β}}_{n})$

{\hat{β}}_{n + 1} = {\hat{β}}_{n} + \frac{M_{n}^{- 1}}{1 + x_{n}^{T} M_{n}^{- 1} x_{n}} x_{n} (y_{n} - x_{n}^{T} {\hat{β}}_{n})

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} x_n(y_n - x_n^T\hat\beta_{n})$

Polyak 평균화 는
를 사용하여 을 범위가 근사값에 사용할 수 있음을 나타냅니다. 에 . 귀하의 경우 재귀에 가장 적합한 를 선택하려고 시도 할 수 있습니다 . $η_{n} = n^{- α}$

η_{n} = n^{- α}

$\eta_n = n^{-\alpha}$ $\frac{M_{n}^{- 1}}{1 + x_{n}^{T} M_{n}^{- 1} x_{n}}$

\frac{M_{n}^{- 1}}{1 + x_{n}^{T} M_{n}^{- 1} x_{n}}

$\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ $α$

α

$\alpha$ $0.5$

0.5

$0.5$ $1$

1

$1$ $α$

α

$\alpha$

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

${\hat{β}}_{n + 1} = {\hat{β}}_{n} + \frac{η_{n}}{n} \sum_{i = 0}^{n - 1} x_{i} (y_{i} - x_{i}^{T} {\hat{β}}_{n})$

{\hat{β}}_{n + 1} = {\hat{β}}_{n} + \frac{η_{n}}{n} \sum_{i = 0}^{n - 1} x_{i} (y_{i} - x_{i}^{T} {\hat{β}}_{n})

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{\eta_n}{n} \sum\limits_{i=0}^{n-1}x_i(y_i - x_i^T\hat\beta_{n})$

답변

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

λ

$\lambda$ $‖ X β - y ‖^{2}$

‖ X β - y ‖^{2}

$\| X \beta -y \|^{2}$ $‖ λ β ‖^{2}$

‖ λ β ‖^{2}

$\| \lambda\beta \|^{2}$

답변

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

\hat{β}

$\hat{\beta}$

답변

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

X

$X$ $λ$

λ

$\lambda$

답변

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

X^{T} X

$X^TX$ $X^{T} y$

X^{T} y

$X^Ty$ $X^{T} X / n$

X^{T} X / n

$X^TX/n$ $X^{T} y / n$

X^{T} y / n

$X^Ty/n$

와 를 다음 과 같이 쓰면 : $X$

X

$X$ $y$

y

$y$

X = (\begin{matrix} x_{1}^{T} \\ ⋮ \\ x_{n}^{T} \end{matrix}), y = (\begin{matrix} y_{1} \\ ⋮ \\ y_{n} \end{matrix}),

$X = \begin{pmatrix} x_1^T \\ \vdots \\ x_n^T \end{pmatrix}, \quad y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix},$

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

X^{T} X / n

$X^TX/n$ $X^{T} y / n$

X^{T} y / n

$X^Ty/n$ $t$

t

$t$

A_{t} = (1 - \frac{1}{t}) A_{t - 1} + \frac{1}{t} x_{t} x_{t}^{T},

$A_t = \left(1 - \frac{1}{t}\right) A_{t-1} + \frac{1}{t}x_t x_t^T,$

b_{t} = (1 - \frac{1}{t}) b_{t - 1} + \frac{1}{t} x_{t} y_{t} .

$b_t = \left(1 - \frac{1}{t}\right) b_{t-1} + \frac{1}{t}x_t y_t.$

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

β

$\beta$

{\hat{β}}_{t} = (A_{t} + λ I)^{- 1} b_{t} .

$\hat\beta_t = (A_t + \lambda I)^{-1}b_t.$

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

λ

$\lambda$

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

How IT

언제든지 물어보세요.

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

답변

답변

답변

답변

답변

답변