[SAS 프로그래밍] SAS/IML 로 SVD(singular value decomposition) 계산해보기

[#1]

 안녕하세요. 이번 시간에는 추천시스템에서 연산량을 줄이고 보다 효율적인 모델을 만들기 위해 자주 쓰이는 특이값분해(Singural value decomposition, SVD)에 대해 알아보겠습니다.

Introducing SVD

특이값 분해는 텍스트 마이닝, 추천시스템, 이미지 프로세싱, 분류모형 등의 데이터 과학에서 현대 알고리즘의 수학적 기초를 제공하고 있습니다. 수학적으로 발견된 것은 1800년대 이지만 잘 계산상의 문제로 잘 쓰이지 않다가 컴퓨터의 발명으로 계산 통계와 데이터 과학에서 없어서는 안되는 툴이 되었습니다.

SVD in linear algebra

선형대수학적으로 특이값 분해는 행렬의 인수분해라고 할 수 있습니다. 다시말해, 극좌표 분해를통해 positive semidefinite normal matrix(모든 고유값이 음수가 아닌 정규행렬)을 인수분해하는 고유값 분해의 일반화된 형태입니다. 정방행렬에 대해서만 적용가능한 고유값 분해를 응용하여 의미를 확장시킨 개념이라고 할 수 있습니다.

 M이라는 m x n행렬이 있을 때, M의 특이값 분해 형식은 U로 표현합니다. 이때

- U는 m x m 직교행렬(역행렬과 같은 전치행렬)입니다. M의 Left_sigular vectors 라고 합니다.

- 는 m x n 음수가 아닌 대각원소를 갖는 직사각 대각행렬입니다. 2 x n 직사각 대각행렬의 형태는 다음과 같습니다. 여기서 대각원소가 분해된 특이값을 나타내는 것입니다.

- 는 n x n 직교행렬입니다. M의 Right-singular vectors 라고 합니다.

SVD in geometric interpretation

 SVD는 기하학적인 선형방법으로도 표현할 수 있습니다. 위의 세가지 행렬이 세가지 선형변환을 나타내는 것입니다. 선형변환은 오른쪽부터 시작하기 때문에 오른쪽부터 해석해보면,

- 는 M행렬을 n차원공간에서 회전 또는 반사합니다.

- 는 앞서 회전, 반사된 M행렬을 스케일링하는 단계입니다. p차원의 공간을 n차원으로 바꿔주는 역할입니다.

- U는 m차원공간에서 마지막으로 회전 또는 반사합니다.

요약하자면 SVD는 회전 또는 반사 다음 크기를 조절하는 단계가 있고 다시 회전 또는 반사를 하는 세단계의 선형변환입니다.

Uses of SVD

SVD는 상당히 많은 쓰임이 있는데 그중 대표적인 몇가지를 소개하겠습니다.

1. Pseudoinverse

SVD를 통해 의사역행렬을 구할 수 있습니다. 행렬식에서 역행렬의 존재는 계산상의 편의를 돕기 때문에 상당히 유용하지만 일반적으로 정방행렬에서만 역행렬을 구할 수 있다는 단점이 있습니다. 이런 점을 해결하는 방법이 의사역행렬입니다. 다음은 행렬 M을 특이값분해하고 이를 통해 의사역행렬을 구하는 과정입니다.

M=UΣV*      =VU*

는 Σ의 0이 아닌 대각원소들을 역수로 취하고 나머지는 전치행렬 처럼 행과열이 바뀌게 됩니다.

1. Low_rank matrix approximation

SVD에서 행렬의 대각요소들은 좌상측부터 우하측으로 갈수록 크기가 작아집니다. 이러한 점을 이용하여 크기가 작은 대각원소들을 0으로 취급하여 필요에 따라 원하는 만큼 대각원소의 개수를 줄여 나가면서 원래 행렬의 특징은 살리되 연산량은 줄이고 노이즈는 없앨 수 있습니다. 이러한 기능은 실제로 이미지 처리에서 이미지의 특징을 찾아내거나 크기를 줄일 때 유용하게 사용됩니다. 0이 아닌 대각 원소의 개수가 많아질수록 이미지는 원본에 가깝고 화질은 좋으며, 개수가 줄어들수록 특징만 살아 있는 이미지에 가까워지고 화질은 나빠집니다.

1. Practical applications

SVD는 위에서 알아본 장점들을 활용하여 빅데이터의 주성분 분석이나 통신 분석, 신호처리, 패턴 인식 등에서 실제로 유용하게 사용되고 있습니다.

 SVD in IML/SAS

SAS에서는 IML언어의 서브루틴을 통해 SVD를 계산할 수 있습니다. SAS에서는 메모리 절약을 위해 ‘thin SVD’를 사용하고 있습니다. ‘thin SVD’란, 주어진 행렬 A의 크기가 nxp(n>p)이고 A=UΣV* 일때 단순SVD는 U=nxn, Σ=nxp, V*=pxp 이지만 ‘thin SVD’의 경우, U=nxp, Σ=pxp, V*=pxp 로 계산하여 특이값을 나타내는 대각원소의 수를 줄이고 연산량을 줄이는 방법입니다. 하지만, p가 n보다 큰 경우는 U와 V의 역할이 서로 바뀌어 같은 방식으로 진행합니다.

    SVD 를 계산하는 서브루틴 CALL SVD문의 기본형식은 다음과 같습니다.

   CALL SVD (u, d, v, a)

   괄호안에 들어간 알파벳 u, d, v, a는 설명을 위해 임의로 지정한 것으로 분석자가 원하는 다른 이름을 사용하여도 됩니다. 우선 SVD를 할 대상이 되는 행렬은 ‘a’자리에 지정해주면 됩니다.

‘u’로 만들어지는 행렬은 위에서 언급한 ‘U’와 같은 행렬입니다. 만약 ‘a’행렬이 nxp(n>p)크기의 행렬인 경우 ‘u’행렬은 nxp크기의 행렬이 됩니다.

‘d’로 만들어지는 행렬은 위에서 언급한 대각원소 행렬에서 대각원소만을 원소로 가지는 열벡터로 계산되어 나타납니다. 만약 ‘a’행렬이 nxp(n>p)크기의 행렬인 경우 ‘d’행렬은 px1크기의 행렬이 됩니다.

‘v’로 만들어지는 행렬은 위에서 언급한 ‘V’와 같은 행렬입니다. 만약 ‘a’행렬이 nxp(n>p)크기의 행렬인 경우 ‘v’행렬은 pxp크기의 행렬이 됩니다.

이해를 돕기 위해 4x3크기의 행렬을 만들어서 실습해보겠습니다.

임의의 4x3행렬 m을 만들어서 m을 SVD한 결과입니다. 위에서 설명한대로 ‘u’에 해당하는 행렬은 4x3(nxp)로, ‘d’에 해당하는 행렬은 3x1(px1)로, ‘v’에 해당하는 행렬은 3x3(pxp)로 만들어진 것을 확인하였습니다. ‘d’에 계산된 특이값들 역시 위에서 알아본대로 아래로 갈수록 작아지는 것 또한 확인하였습니다.

 마치며

이번시간에는 데이터처리에 유용하게 쓰이고 있는 SVD에 대해 간단히 알아보고 SAS의 IML을 통해 SVD를 계산하는 방법까지 알아보았습니다. SVD는 이미지 처리, 주성분 분석, 신호처리 등에서 많이 쓰이는 유용한 개념인 것 같습니다.

Reference

https://en.wikipedia.org/wiki/Singular-value_decomposition

https://blogs.sas.com/content/iml/2017/08/28/singular-value-decomposition-svd-sas.html

http://support.sas.com/documentation/cdl/en/imlug/66845/HTML/default/viewer.htm#imlug_langref_sect45...