📂행렬대수

특이값분해를 이용한 티호노프 정칙화 계산량 절감 트릭

정리

리지 회귀의 최적해: $$ L \left( \beta \right) = \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{2}^{2} $$ $\lambda$ 가 상수로 주어져 있을 때, 리지 회귀의 목적 함수 $L$ 을 위와 같이 나타내자. 리지 회귀의 최적해 $\hat{\beta} = \argmin_{\beta} L \left( \beta \right)$ 는 다음과 같다. $$ \hat{\beta} = \left( X^{\top} X + \lambda I \right)^{-1} X^{\top} Y $$ 여기서 $A^{\top}$ 는 $A$ 의 전치행렬, $I$ 는 항등행렬, $A^{-1}$ 는 $A$ 의 역행렬이다.

행렬 $A \in \mathbb{R}^{m \times n}$ 와 벡터 $\mathbf{b} \in \mathbb{R}^{m}$ 가 주어졌을 때 $A \mathbf{x} = \mathbf{b}$ 를 최소제곱해를 찾을 때 $\lambda \ge 0$ 에 대한 티호노프 정칙화^{Tikhonov regularization}를 적용하면 다음의 최적화 문제를 풀게 된다. $$ \argmin_{\mathbf{x}} \left\| A \mathbf{x} - \mathbf{b} \right\|^2 + \lambda \left\| \mathbf{x} \right\|^2 $$ 보통 이 문제에 대한 해는 클로즈드 폼인 $\mathbf{x} = \left( A^{\top} A + \lambda I \right)^{-1} A^{\top} \mathbf{b}$ 로 알려져 있으나, $A$ 의 특이값 분해 $A = U \Sigma V^{\top}$ 를 이용하면 행렬분해를 한 번만 해서 $\lambda$ 를 바꿔가며 계산할 수 있는 다음의 공식으로도 나타낼 수 있다. $$ \mathbf{x}(\lambda) = V \left( \Sigma^{2} + \lambda I \right)^{-1} \Sigma U^{\top} \mathbf{b} $$

설명

여러가지 행렬분해를 통한 최소제곱법 구현에 대해 속도를 비교해보고 안정성을 비교해보면 다음과 같이 아주 명확한 트레이드 오프가 보인다.

방법	속도	안정성
LU	빠름	불안정
QR	보통	안정적
SVD	느림	매우 안정적

실제로 QR과 SVD 자체의 계산량만 보면 SVD가 느리지만, 가령 행렬이 매우 크고 리지 회귀를 위해 $\lambda$ 를 바꿔가며 계산을 반복하고 최적의 값을 찾는 경우에는 SVD를 통한 트릭을 통해 계산량을 줄일 수 있다. 제시된 공식에서 $\left( \Sigma^{2} + \lambda I \right)$ 는 대각행렬이므로 역행렬을 구하는 것은 매우 쉽고, $V$ 와 $U^{\top} \mathbf{b}$ 는 한 번만 계산하면 모든 $\lambda$ 에 대해 재사용 가능하다.

이러한 트릭은 단순히 계산량만 절감할 뿐만 아니라 SVD에 의한 안정성까지 확보할 수 있으므로, 막대한 크기와 악조건의 위험성이 높아지는 데이터에 가까워질수록 유용한 방법이 될 수 있다.

물론 위에서 언급한 문제가 없을 경우, 어지간하면 QR 분해를 이길 수 없거나 이길 필요가 없다. 가령 1초가 걸리던 태스크가 0.5초로 줄어든다고 해서 굳이 SVD 기반 리지 회귀를 구현하는 것은 너무 과한 것이고, 검증되지 않은 코드를 직접 짜는 시점에서 구현의 완성도도 의심을 산다. SVD를 적용할 상황인지 아닌지를 합리적으로 판단하고, 구현에 성공하더라도 실제 성능 향상이 있었는지에 대한 검증이 꼭 필요하다.

증명

$A = U \Sigma V^{\top}$ 를 $A$ 의 특이값 분해 (SVD)라고 하자. 여기서 $U$ 와 $V$ 는 직교행렬이고, $\Sigma$ 는 특이값을 담고 있는 대각행렬이다. $V$ 가 직교행렬이므로 $\mathbf{y} = V^{\top} \mathbf{x}$ 로 치환하면 다음을 얻는다. $$ \lambda \left\| \mathbf{x} \right\|^2 = \lambda \left\| V \mathbf{y} \right\|^2 = \lambda \mathbf{y}^{\top} V^{\top} V \mathbf{y} = \mathbf{y}^{\top} \lambda I \mathbf{y} $$ 그리고 $$ \begin{align*} \left\| A \mathbf{x} - \mathbf{b} \right\|^2 =& \left\| U \Sigma V^{\top} V \mathbf{y} - \mathbf{b} \right\|^2 \\ =& \left\| U \Sigma \mathbf{y} - \mathbf{b} \right\|^2 \\ =& \left( U \Sigma \mathbf{y} - \mathbf{b} \right)^{\top} \left( U \Sigma \mathbf{y} - \mathbf{b} \right) \\ =& \mathbf{y}^{\top} \Sigma^{\top} U^{\top} U \Sigma \mathbf{y} - 2 \mathbf{y}^{\top} \Sigma U^{\top} \mathbf{b} + \left\| \mathbf{b} \right\|^{2} \\ =& \mathbf{y}^{\top} \Sigma^{2} \mathbf{y} - 2 \mathbf{y}^{\top} \Sigma U^{\top} \mathbf{b} + \left\| \mathbf{b} \right\|^{2} \end{align*} $$ 이므로, $\mathbf{y}$ 에 대한 목적 함수와 그 그래디언트는 다음과 같이 나타낼 수 있다. $$ \begin{align*} J \left( \mathbf{y} \right) =& \mathbf{y}^{\top} \left( \Sigma^{2} + \lambda I \right) \mathbf{y} - 2 \mathbf{y}^{\top} \Sigma U^{\top} \mathbf{b} + \left\| \mathbf{b} \right\|^{2} \\ \partial J \left( \mathbf{y} \right) / \partial \mathbf{y} =& 2 \left( \Sigma^{2} + \lambda I \right) \mathbf{y} - 2 \Sigma U^{\top} \mathbf{b} . \end{align*} $$ 마지막으로, 주어진 $\lambda$ 에 대한 최적해 $\mathbf{x}(\lambda)$ 는 다음과 같다. $$ \mathbf{x}(\lambda) = V \left( \Sigma^{2} + \lambda I \right)^{-1} \Sigma U^{\top} \mathbf{b} $$

■

코드

다음은 필자가 연구에 실제로 사용하는 SVD 기반 티호노프 정칙화다.

using LinearAlgebra

function tikhonov_λ(A, b)
    U, s, V = svd(A)
    Uᵀb = U'b
    return λ -> V * (Diagonal(s ./ (s.^2 .+ λ)) * Uᵀb)
end

필자의 경우 Uᵀb = U'b를 빼먹고 익명함수에 그대로 넣었다가 매번 $\lambda$ 를 바꾸면서 $U^{\top} \mathbf{b}$ 를 계산하는 바람에 계산량이 기본 구현(QR 분해)에 밀리는 실수를 한 적이 있다. 수식만 믿지 말고 실제 벤치마크를 꼭 해보자.