[Dimensionality Reduction] 3

특이치 분해(SVD)

• 행렬 R은 세 개의 행렬로 분해될 수 있습니다: • U, S, V: 고유

• U, V: 열 또는 정규 분포 • UTU = I, VTV = I (I : 아이덴티티 매트릭스) • 열은 직교 단위 벡터입니다.

• S: 대각선

• 항목(단수 값)은 양수이며, 감소하는 순서로 정렬됩니다 ( ≥ ≥ ⋯ ≥ 0).

입력 데이터 행렬: m x n 행렬 왼쪽 단수 행렬: m x m 행렬 대각행렬 : m x n 행렬, 여기서 대각 원소는 특이값(개념의 강도) 오른쪽 단수 행렬: n x n 행렬

SVD의 특성

• 항상 행렬 A를 A = USV로 분해할 수 있습니다 • �, �, �: 유니크

• U, V: 열 또는 정규 분포 • ��� = �, ��� = �(I: ID 행렬) • 열은 직교 단위 벡터입니다.

• � : 대각선

• 항목(단수 값)은 양수입니다.

• 감소하는 순서로 정렬합니다(�! ≥ �" ≥ ⋯ ≥ 0).

SVD 계산 방법

• � = �∑�를 얻는 방법, • ��2 = �∑�2 �∑�2 2 = �∑�2�∑2�2 • �#� = �

• ∑# = ∑

• ��2 = �∑7�2 ( (��2)� = �∑7) • 이것은 고유 분해의 형태입니다 : �� = λ • �는 고유 벡터의 행렬입니다 • λ는 고유값의 대각선 행렬입니다 • �는 ��의 고유벡터#입니다 • ∑는 대각선 행렬입니다

• ��# 고유값 제곱근의 대각선 값

SVD 계산 방법

• � = �∑�를 얻는 방법, • �2� = �∑�2 2�∑�2 = �∑2�2�∑�2 • �#� = �

• ∑# = ∑

• �2� = �∑7�2

• 이것은 고유 분해의 형태입니다 : �� = λ • �는 고유 벡터의 행렬입니다 • λ는 고유값의 대각선 행렬입니다 • �는 �#�의 고유 벡터입니다 • ∑는 대각선 행렬입니다

• �의 제곱근 대각선 값#� 고유값

SVD와 PCA의 관계

• SVD와 PCA가 동시에 발생합니다 • SVD

• � = �∑�#

• �는 �#�의 고유 벡터 행렬입니다 • ∑에 �# �(또는 ��#)의 루트-squared 고유값이 있습니다 • PCA

• 평균 중심 행렬 A의 공분산 행렬은 �#�입니다.

• i번째 주성분

= i번째 고유값에 해당하는 고유벡터 • SVD의 � = 주성분 분석(PCA) SVD를 이용한 치수축소

• 점 위치를 설명하기 위해 두 개의 좌표(x, y)를 사용하는 대신 한 개의 좌표(z)만 사용합니다.

• 점의 위치는 벡터 v1을 따라 위치합니다.

• v1을 선택하는 방법 재구성 오류 최소화 첫 번째 오른쪽 단수 벡터

SVD를 이용한 치수축소

• 목표: 재구성 오류의 합계 최소화: • 여기서 xij는 "이전"이고 zij는 "새로운" 좌표입니다.

• SVD는 다음에 투영할 수 있는 "최상의" 축을 제공합니다: • "최상" = 재구성 오류 최소화 SVD 해석

• 인수분해 행렬을 어떻게 해석합니까?

• U: 사용자 대 개념 유사도 매트릭스 • V: 항목 대 개념 유사도 행렬 • S: 대각선 요소: 각 개념의 "강도"

• U: "사용자 대 개념" 매트릭스 • V: "항목 대 개념" 매트릭스

SVD 해석

US: 투영 축의 점들의 좌표

차원을 줄이는 방법

• Q: 차원 축소는 정확히 어떻게 이루어집니까?

• A: 가장 작은 특이값을 0으로 설정합니다.

재구성 오류를 최소화합니다.

SVD로 질의하는 방법?

• Q: '사랑'에 관한 문서는 어떻게 찾나요?

• A: 쿼리를 '개념 공간'에 매핑합니다. 어떻게 해야 합니까?

V는 "개념 간" 유사성 행렬입니다 • 관찰

• ('Romeo', 'Juliet')와 관련된 문서는 d와 q가 공통적으로 0의 등급을 가지고 있지만, 쿼리 q가 ('Love')와 유사합니다.

Number of Dimension(차원 수) 선택 • Q: 몇 개의 σ을 보관해야 합니까?

• A: 주먹구구식: '에너지' 80~90% 유지 = ∑i

SVD의 복잡성

• SVD를 계산하려면:

• �(�� 2) 또는 �(� 2 �)(whichever은 더 적음) • 그러나:

• 우리가 단수 값만 원하면 일이 줄어듭니다 • 또는 첫 번째 k개의 단수 벡터를 원하는 경우 • 또는 행렬이 희박한 경우

• 다음과 같은 선형 대수 패키지로 구현됩니다 • 린팩, 매트랩, 스플러스, 수학...

SVD의 단점

• 프로스

• 프로베니우스 노름의 관점에서 최적의 낮은 순위 근사치 • 콘스

• 해석 가능성 문제: 단일 벡터는 모든 입력 열 또는 행의 선형 조합을 지정합니다

희소성 부족: 특이 벡터는 밀도가 높습니다!

SVD: 최하위 근사치

• 정리: � = � � �� 및 � = � � ��로 하자 • � = 대각선 � × � 행렬 = � > (� = 1 … �) 기타 � > = 0 • 그런 다음 �는 �에 대한 최상의 순위(�)=� 근사치입니다.

• "최고"란 무엇을 의미합니까:

• �은 min에 대한 해결책입니다 s

� − �

여기서 순위(�) = �.