Additivity
$$ L(n + v) = L(n) + L(v) $$
Homogeneity
$$ L(cv) = cL(v)$$
$$ c^1v_1 + c^2v_2 + ... + c^nv_n = 0, c^i \in R, some ; c^i \not = 0$$
라고 한다면, 벡터 $v_1, v_2, ... , v_3$ 는 $Linearly; Dependent$ 하다.$Linearly; Independent$ 하다.
행렬식과 Linearly Dependent 간의 관계 $$ c^1v_1 + c^2v_2 + c^3v_3 = 0$$
위와 같은 선형 시스템이 있다고 한다면 아래 행렬식으로 표현 가능하고
$$ \to \left(\begin{array}{cc}v1 & v2 & v3\end{array}\right) \left(\begin{array}{cc} c^1 \c^2 \c^3 \end{array}\right) = 0$$
$v_i$ 의 행렬을 M으로 표기할 수 있다.
$$ M := \left(\begin{array}{cc}v1 & v2 & v3\end{array}\right)$$
$$\to M \left(\begin{array}{cc}c^1 \ c^2 \ c^3\end{array}\right) = 0$$
위 식에서 행렬 M에 대해 역행렬이 존재할 경우, Linearly Dependent 하다.
$det(M) = {0}$ 인 경우, 역행렬이 존재하지 않는다. $\therefore det(M) = {0}$ 이면 $Linearly; Independent$ 하다 역행렬을 구할때 왜 행렬식이 0이 되면 안될까? 역행렬을 구하는 수식은 아래와 같다.
$$ A^{-1} = \frac{1}{det(A)}adj(A)$$
행렬식이 0이 되어서 $\frac{1}{0}$ 이 된다면 이를 를 정의할 수 없음.
$c^1v_1 + c^2v_2 + c^3v_3$ 를 $Linear; Combination$ 이라고 한다 $V$ 를 벡터 공간이라고 하고, $S$ 집합이 $Linearly; Independent$ 하고 $V = spanS$ 일 때, $S$ 집합을 V의 $basis$ (기저)라고 한다.
$basis$ 인 $S$ 가 유한 개의 원소를 가지고 있다면, $V$ 를 $finite-dimensional$ 이라고 하고, $S$ 원소의 개수를 $V$ 의 $dimension$ 이라고 한다.
$S$ 가 벡터 공간 $V$ 의 $basis$ 고, $T$ 가 $Linearly; Independent$ 벡터 집합이면, $T$ 의 벡터 개수($m$ )는 항상 $S$ 의 벡터 개수($n$ )보다 작거나 같다.
$$ m \leq n$$
유한 차원의 벡터 공간 $V$ 에 대해서, 무작위의 두 $basis$ 의 벡터 개수는 같다.
행렬식. 정방 행렬(Square Matrix)에 어떤 특정한 방법으로 하나의 수로 대응 시키는 함수.
2차원이면 평행사변형의 넓이, 고차원에서는 벡터 들의 내부의 부피.
$$ det(A) $$
$$ |A| $$
$$ A = \left(\begin{array}{cc} 2 & 1 \ 0 & 3 \end{array}\right)$$
$$ det(A) = 23 - 1 0 $$
$$ = 6 $$
$$ det(A) = \sum_{j=1}^n a_{ij}(-1)^{i + j}M_{ij}$$
$$ = \sum_{j=1}^n a_{ij}C_{ij}$$
$$ A = \left(\begin{array}{cc} 1 & 2 & 3 \ 3 & 2 & 1 \ 1 & 2 & 2 \end{array}\right) $$
i값은 행이나 열 중에서 하나로 고정 ( $i=1$ 로 고정 )
$$ det(A) = \sum_{j=1}^n a_{1j}(-1)^{1 + j}M_{1j}$$
$$ = a_{11}(-1)^{1+1}M_{11} + a_{12}(-1)^{1+2}M_{12} + a_{13}(-1)^{1+3}M_{13}$$
$$ = 2 - 10 + 12$$
$$ = 4$$
$I$ (Indentity Matrix)의 행렬식은 항상 1이다 $$ det(I_n) = 1 $$
$$ det(A) = det(A^t) $$
행렬 $A$ 에서 임의의 두 row|col을 바꾼 행렬 $B$ 의 행렬식은 $-det(A)$ 이다 $$ A = \left(\begin{array}{cc} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{array}\right) B = \left(\begin{array}{cc} 1 & 2 & 3 \ 7 & 8 & 9 \ 4 & 5 & 6 \end{array}\right)$$
2번째 행과 3번째 행을 바꿈.
$$ \to det(B) = -det(A)$$
행렬 $A$ 에서 임의의 한 row|col에 상수 $t$ 배를 한 행렬 $C$ 의 행렬식은 $t|A|$ 이다 $$ A = \left(\begin{array}{cc} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{array}\right) C = \left(\begin{array}{cc} 1 & 2 & 3 \ 8 & 10 & 12 \ 7 & 8 & 9 \end{array}\right)$$
2번째 행에 2를 곱함.
$$ \to det(C) = 2det(A)$$
$$|C| = t|A|$$
$$\to |ta_1, a_2, ... , a_n| = t|a_1, a_2, ..., a_n|$$
$$\to |tA| = |ta_1, ta_2, ..., ta_n| = t^n|A|$$
가산성(Additivity) 또는 선형성(Linearity) $$ |a_1 + a_1', a_2, ..., a_n| = |a_1, a_2, ..., a_n| + |a_1', a_2, ..., a_n|$$
교대성(Alternating Property) 행렬 $A$ 에서 임의의 두 row|col을 바꾼 행렬 $B$ 의 행렬식은 $-det(A)$ 이다.
$$ A = \left(\begin{array}{cc} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{array}\right) B = \left(\begin{array}{cc} 1 & 2 & 3 \ 7 & 8 & 9 \ 4 & 5 & 6 \end{array}\right)$$
2번째 행과 3번째 행을 바꿈.
$$ \to det(B) = -det(A)$$
$$ det(AB) = det(A)det(B) $$
모든 비대각선 원소가 0인 행렬.
$$ D = \begin{pmatrix} d_1 & 0 & 0 & ... & 0 \ 0 & d_2 & 0 & ... & 0 \ &&\dotsm \ 0 & 0 & 0 & ... & d_n \end{pmatrix}$$
원소의 역수를 취한 값이다.
$$ D = \begin{pmatrix} d_1 & 0 \ 0 & d_2 \end{pmatrix}$$
$$ D^{-1} = \begin{pmatrix} \frac{1}{d_1} & 0 \ 0 & \frac{1}{d_2} \end{pmatrix}$$
$$ det(D) = d_1 \cdot d_2 \dotsm d_n$$
고유값: $d_1 , d_2 , \dotsm, d_n$
$\begin{pmatrix}1\0\end{pmatrix}$ 과 같은 기저 벡터들이 고유벡터가 됨.
선형 변환에서의 해석이 직관적임. 각 축에 대해 스케일링 변화를 나타냄.
$$a_{ij} = a_{ji} \ square; matrix$$
$$ A^T = A $$
$$ \begin{bmatrix} 8 & 1 & 4 \ 1 & 3 & 7 \ 4 & 7 & 6 \end{bmatrix} = \begin{bmatrix} 8 & 1 & 4 \ 1 & 3 & 7 \ 4 & 7 & 6 \end{bmatrix}$$
고유값은 실수이다.
고유벡터들은 서로 직각을 이룬다.
$$ \forall z\not ={0}, z^TAz > 0 \to positive ; definite \ \forall z\not ={0}, z^TAz \geq 0 \to positive ; semidefinite$$
대칭행렬 $A$ 가 positive definite 하면, 이 행렬의 모든 Eigen Value는 항상 양수이다.\
$A^TA$ 와 $AA^T$ 는 항상 대칭행렬이므로, $A^TA$ 와 $AA^T$ 의 고유값들은 항상 양수이다.
$Ax=0$ 를 만족하는 모든 벡터 $x$ 의 집합.
$$ Null(A) = {x \in R^n | Ax = 0 }$$
예시 ( Q 행렬 A의 $null; space$ 는? ) $$ A = \left(\begin{array}{cc} 1 & 2\3 & 4\end{array}\right)$$
$$ Ax = 0 $$
$$ \to \left(\begin{array}{cc} 1 & 2\3 & 4\end{array}\right)\left(\begin{array}{cc} x_1\ x_2\end{array}\right) = \left(\begin{array}{cc} 0\ 0\end{array}\right)$$
$$\to Null(A) = {t \left[\begin{array}{cc} -2\ 1\end{array}\right] | t \in R }$$
$null; space$ 는 $\left[\begin{array}{cc} -2\1\end{array}\right]$ 의 방향으로 펼쳐진 1차원 선형 공간.
$null; space$ 의 차원
$$ A \in R^{n}$$
$$ rank(A) + nullity(A) = n$$
주어진 행렬이 갖는 선형 독립적인 행 또는 열의 최대 개수.
RREF( Reduced Row Echelon Form)으로 변환하여 0이 아닌 행의 개수를 센다.
$$ A = \left[\begin{array}{cc} 1 & 2 & 3\4 & 5 & 6\7 & 8 & 9 \end{array}\right]$$
가우스 소거법 적용
$$ A \sim \left[\begin{array}{cc} 1 & 2 & 3\0 & -3 & -6\ 0 & 0 & 0 \end{array}\right]$$
0 이 아닌 행 은 2개
$$ rank = 2 $$
$$ A \in R^{n}$$
$$ rank(A) + nullity(A) = n$$
가역적(invertible) - 역행렬이 존재한다.
특이 행렬(Singular Matrix) - 역행렬이 존재하지 않는 행렬. ( 행렬식 = 0 )
정방 행렬에서 랭크가 최대가 아니라면 역행렬이 존재 하지 않는다.
차원축소시 랭크와 작거나 같은 차원으로 축소 가능하다.
Eigen Vector & Eigen Value 임의의 선형 변환 연산(행렬)으로 벡터에 선형 변환을 했을때,
$$ A\vec{x} = \lambda \vec{x}$$
행렬 $A$ 에 대해서, 0이 아닌 솔루션 벡터 $\vec{x}$ 가 존재한다면, $\lambda$ 는 행렬 $A$ 의 고윳값이다.$\vec{x}$ 는 고유벡터이다.
Nontrivial solution을 가지기 위한 필요충분 조건 $$ (A - \lambda I)\vec{x} = 0 $$
$\vec{x} = 0$ 이면 trivial solution이다.$(A - \lambda I)$ 이 역행렬을 가지지 않아야만 nontrivial solution을 가진다.
$$det(A - \lambda I) = 0 $$
Eigen Vector/Value 구하기 예시 $$ A = \begin{pmatrix} 2 & 1 \ 1 & 2 \end{pmatrix}$$
Nontrivial solution을 가지기 위한 필요충분 조건 만족하기 위해서 $det(A - \lambda I) = 0$ 를 만족해야한다.
$$det(A - \lambda I) = 0 $$
$$\to det(\begin{bmatrix} 2 - \lambda& 1 \ 1 & 2 - \lambda \end{bmatrix}) = 0 $$
$$\to (2 - \lambda)^2 - 1 = 0$$
$$\to \lambda^2 - 4\lambda + 3 = 0 $$
$$\to \lambda_1 = 1, \lambda_2 = 3 $$
고유값 ($\lambda_1 = 1$ ) 인 케이스 $$ \begin{bmatrix} 2 & 1 \ 1 & 2 \end{bmatrix}\begin{bmatrix} x_1 \ x_2 \end{bmatrix} = 1 \begin{bmatrix} x_1 \ x_2 \end{bmatrix}$$
$$ 2x_1 + x_2 = x_1 \ x_1 + 2x_2 = x_2$$
$$\to \begin{bmatrix} x_1 \ x_2 \end{bmatrix} = \begin{bmatrix} 1 \ -1 \end{bmatrix}$$
고유값 ($\lambda_2 = 3$ ) 인 케이스 $$ \begin{bmatrix} 2 & 1 \ 1 & 2 \end{bmatrix}\begin{bmatrix} x_1 \ x_2 \end{bmatrix} = 3 \begin{bmatrix} x_1 \ x_2 \end{bmatrix}$$
$$ 2x_1 + x_2 = 3x_1 \ x_1 + 2x_2 = 3x_2$$
$$\to \begin{bmatrix} x_1 \ x_2 \end{bmatrix} = \begin{bmatrix} 1 \ 1 \end{bmatrix}$$
Eigen Value Decomposition (EVD)
고유값 분해는 $n \times n$ 정방 행렬을 고유벡터로 이루어진 행렬과 고유값으로 이루어진 행렬로 대각화 하는 방법.
행렬의 거듭제곱, SVD등에서 활용된다.
$$X = V \Lambda V^{-1} $$
정방행렬
대각화 가능한 행렬. ( 고유값이 열/행의 개수만큼 다른 값을 가짐. 열/행 개수만큼의 독립적인 고유벡터를 가진다.)
$$ X = V \Lambda V^{-1} = V \Lambda V^T$$
대칭행렬은 항상 고유값 분해가 가능.
고유값 분해시 직교행렬로 분해.
SVD에서 이러한 특징을 이용.
Singular Value Decomposition (SVD)
고유값 분해처럼 행렬을 대각화 하는 방법.
정방행렬이 아니여도 관계없이 $m \times n$ 에 대해 적용가능.
$$ A = U Σ V^t$$
$$ = \sigma_1 U_{col_1} V_{row_1}^t + \sigma_2 U_{col_2} V_{row_2}^t + ... + \sigma_r U_{col_r} V_{row_r}^t $$
$$ A = U Σ V^t \to AV = U Σ V^t V \to AV = UΣ $$
$$ \to AV_{col_i} = \sigma_iU_{col_i}$$
$A$ : $m \times n$ 행렬
$U$ : $m \times m$ 왼쪽 특이벡터. $A$ 의 열공간을 이루는 직교 벡터($orthogonal$ )들로 구성. $AA^t$ 의 고유벡터
$V^t$ : $n \times n$ 오른쪽 특이벡터. $A$ 의 행공간을 이루는 직교 벡터($orthogonal$ )들로 구성. $A^tA$ 의 고유벡터
$Σ$ : $m \times n$ 대각행렬, 대각선에 위치한 값들은 $A$ 의 특이값. 특이값들은 $A$ 의 크기를 나타내며, 중요한 차원들을 구별하는 역할을 함. 내림차순으로 정렬되어 있음.
$$ CC^t = C^tC = I $$
직교행렬인 $U$ , $V^t$ 는 크기는 변하지 않고 위치/방향만 바뀐다.
$A$ 의 선형 변환에서 "크기"나 "스케일링"에 해당하는 정보.
특이값이 0 이면 해당 차원은 선형 종속적이고 "정보를 담고 있지 않다"고 해석 가능.
특이 값이 크면 해당 차원은 데이터에서 중요한 역할을 한다고 해석 가능.
$A^tA$ , $AA^t$ 의 고유값 분해를 통해 V와 U를 찾는다.
특이값은 $A^tA$ 의 고유값의 제곱근
특이값은 내림차순으로 정렬되고, 그에 맞춰 U와 V도 정렬
$$ A = \begin{pmatrix} 1 & 2 \ 3 & 4 \ 5 & 6 \end{pmatrix}$$
$A^tA$
$$A^tA = \begin{pmatrix} 1 & 3 & 5 \ 2 & 4 & 6 \end{pmatrix} \begin{pmatrix} 1 & 2 \ 3 & 4 \ 5 & 6 \end{pmatrix} $$
$$ = \begin{pmatrix} 35 & 44 \ 44 & 56 \end{pmatrix} $$
$AA^t$
$$AA^t =\begin{pmatrix} 1 & 2 \ 3 & 4 \ 5 & 6 \end{pmatrix}\begin{pmatrix} 1 & 3 & 5 \ 2 & 4 & 6 \end{pmatrix} $$
$$ = \begin{pmatrix} 5 & 11 & 17 \ 11 & 25 & 39 \ 17 & 39 & 61 \end{pmatrix} $$
고유값 분해
$A^tA$ 의 고유값 0.514, 90.486
$AA^t$ 의 고유값 0.514, 90.486 ( 동일 하다. )
특이값 계산
특이값 $\sigma_i$ 는 $A^tA$ 또는 $AA^t$ 의 고유값의 제곱근.
$\sigma_1 = \sqrt{90.486} \approx 9.51$ $\sigma_2 = \sqrt{0.514} \approx 0.71$
$$ Σ = \begin{pmatrix} 9.51 & 0 \ 0 & 0.71 \ 0 & 0 \end{pmatrix}$$
실제 컴퓨터에서는 QR알고리즘이나 Jacobi 방법을 사용 $$ A^+ = V Σ^+ U^t$$
$Σ^+$ : Σ의 대각선 원소들을 모두 역수로 바꾼 행렬이다.
행렬의 역행렬이 존재하면 유사 역행렬과 역행렬은 동일하다.
$Channel$ 을 $960 \times 714$ 인 행렬이라고 한다면, 총 685, 440개의 공간이 필요하다.
$Channel$ 을 특이값 분해하면 아래와 같다.
$$ Channel = U_{960 \times 960} Σ_{960 \times 714} V^t_{714 \times 714} $$
Σ의 특이 값중 큰 값부터 25개만 선택.
$$ Channel_{reduced} = U_{960 \times 25} Σ_{25 \times 25} V^t_{25 \times 714}$$
축소되고 나서는 960 X 25 + 25(대각행렬에서 0은 저장할 필요가 없다.) + 25 X 714 = $41, 875$ 개만 저장하면 된다.
공분산 행렬은 데이터의 각 특성 간의 관계를 나타내는 중요한 행렬.
$$ Cov(X, Y) = \frac{1}{n - 1} \sum_{i=1}^n (X_i - \mu_X)(Y_i - \mu_Y)$$
$X_i$ , $Y_i$ 는 각각 $X$ , $Y$ 의 i번째 데이터 값.
$\mu_X$ , $\mu_Y$ 는 각 $X$ , $Y$ 의 평균.
$n$ 은 데이터의 개수
공분산 값이 양수면 같은 방향으로 변화하고, 음수면 반대 방향으로 변화.
0이라면 두 변수간에 선형 관계가 없다는 것을 의미한다.
$$ Σ = \begin{pmatrix} Cov(X, X) & Cov(X, Y) \ Cov(Y, X) & Cov(Y, Y) \end{pmatrix} $$
앞선 예제는 feature가 2개(X, Y)인 두개의 행렬로 가정하였다.
$$ \Sigma = \frac{1}{n}X^TX$$
열(col): Feature
행(row): Data
각 feature의 평균 값이 0이라고 하면 중심 축(pivot)을 찾는데 도움을 준다.
Principal Component Anlysis (PCA)
공분산 행렬에 특이값 분해를 적용한 차원 축소기법
(확인) 공분산 행렬은 고유 벡터로 정사영 했을때 분산이 최대이다
데이터 개수는 n개이고, feature는 d개인 행렬 X
$$ X \in \R^{n \times d}$$
임의의 벡터 $\vec{v}$ 로 정사영 한다고 했을때, 어떤 $\vec{v}$ 에서 데이터의 분산이 최대가 될까?
$$Var(X\vec{v}) = \frac{1}{n}\sum_{i = 1}^n (x_i\vec{v} - E(x_i\vec{v}))^2$$
앞서서 feature의 평균 값을 0으로 맞추어 놨었다고 한다면. 아래로 바꿀 수 있다.
$$= \frac{1}{n}\sum_{i = 1}^n (x_i\vec{v})^2$$
$$=\frac{1}{n}(X\vec{v})^T(X\vec{v})$$
$$=\frac{1}{n}\vec{v}^TX^TX\vec{v} = \frac{1}{n}\vec{v}^T(X^TX)\vec{v}$$
$$=\vec{v}^T\frac{(X^TX)}{n}\vec{v}$$
$$\therefore Var(X\vec{v}) =\vec{v}^T\Sigma\vec{v}$$
이제부터는 $\vec{v}^T\Sigma\vec{v}$ 를 최대로 만드는$\vec{v}$를 구하는 것이 목표이다.$\vec{v}$ 는 단위벡터이므로, 제약조건은 $|\vec{v}|^2 = 1$ 이다.
$$L = \vec{v}^T\Sigma\vec{v} - \lambda(|\vec{v}|^2 - 1)$$
$$\to \frac{\partial L}{\partial \vec{v}} = 2 \Sigma \vec{v} - 2 \lambda \vec{v} = 0$$
$$\therefore \Sigma \vec{v} = \lambda \vec{v}$$
위 식을 만족하는 $\vec{v}$ 는 공분산 행렬$\Sigma$의 고유 벡터이다.$\lambda$ 는 고유 값이자 분산 값이다.
통상 $n \times n$ 행렬에서는 고유벡터는 n개가 있다.
특이값 분해를 통해 구한다.
PCA는 공분산 행렬에 SVD를 하는 것이다.
데이터 표준화
공분산 행렬 계산
고유값과 고유벡터 계산
주성분 선택
선형 변환
