[Data Science] Lecture 8: Linear Algebra

naljin

11 min readJun 18, 2019

2019년 1학기 고려대학교 강재우 교수님 데이터 과학 정리

Linear Algebra

선형 대수란 matrix를 위한 수학으로 많은 머신러닝 알고리즘이 선형대수의 이해를 기반으로 한다.

What Can n x m Matrices Represent?

Data : row = object /column = feature
Geometric point set : row = point / column = dimension
Systems of Equation(연립방정식) : row = equation / column = 각 변수에 대한 계수
Graph / Network : M[i,j]는 vertex i와 j 사이 edge의 개수
Vector : any row, column or d*1 matrix

Angle between Vectors

다음과 같은 삼각형이 있을 때 cos(θ)의 식은 아래와 같다.

이때 단위 벡터에 대해 ‖A‖= ‖B‖=1이므로 A와 B의 사이각은 벡터의 내적(dot product)에 의해 정의될 수 있다. (cos(θ) = dot product)

한편 cos으로 mean zero variable의 상관관계를 나타낼 수 있다. (cos(θ) 값이 1이면 같은 방향, 0이면 90°, -1이면 반대방향)

cos(θ) = dot product 이므로 따라서 내적이 높으면 높은 연관성을 가진다고 할 수 있다.

cf) 내적(dot product. a.k.a. inner product)
내적은 더하기 빼기 같은 연산이다. 특이점은 벡터와 벡터의 연산인데 결과가 스칼라라는 것.

(u,v) = u⋅v = u1v1+….+unvn

이를 간단히 벡터의 element 끼리 곱한 후에 더한 것이라고 생각할 수 있지만, 벡터의 곱으로 생각할 수도 있다. 예를 들어 u,v가 아래와 같이 열벡터 형태라고 생각해보자.

u = (u1u2:un), v =(v1,v2:vn)

위와 같은 두 열벡터의 내적은 아래와 같이 표현 가능하다

u⋅v = uTv

즉 두 열 벡터의 내적을 구하려고 할 때, 둘 중하나의 벡터를 transpose 시켜 행벡터의 형태로 바꾼 후 나머지 벡터와 벡터 곱을 하는 것이다. 이 내적연산을 이용해 벡터의 norm을 구한다든가, 두 벡터 사이 거리를 측정할 수 있다. v 의 norm 은 벡터의 길이라고도 표현하고 norm 이 1인 vector는 unit vector 라고 한다.

‖v‖ = <v, v>

cf) 두 단위 벡터의 내적의 값은 그 사이각에 cos 취한 것 같은 값. 즉 unit vector에 대해, dot product = cos(θ)
cf) 단위 벡터(unit vector) : 방향은 주어진 벡터와 같고 크기가 1인 벡터

A Matrix and its Transpose

Matrix M의 transpose라는 것은 M의 행과 열을 바꾼 것으로 a x b 행렬을 b x a 행렬로 바꾼 것이다.

Addition and Transposition

스칼라 곱과 합의 mix

여기서 첫번째 사진을 A, 두번째 사진을 B라고 할때 B는 transposed A이다. 세번째 사진은 아래 식이 적용된 형태로 ɑ(알파) 값은 0.5 일 것이다.

cf) scalar : 방향 가지고 있지 않고 크기만 가진 물리량

Linear Combination

왼쪽은 ɑ값이 1일때, 오른쪽은 ɑ값이 0일때 사진이다.

Matrix Multiplication / Dot Products

A*B는 곱셈을 위해 반드시 inner dimensions를 공유한다. 곱해진 행렬의 각 element는 row/column vector의 dot product 이다.

dot product는 공분산 혹은 연관성 계산을 통해 두 벡터가 얼마나 “in sync”한지 나타낸다.

Properties of Matrix Multiplication

결합 법칙(associative) 성립 : (AB)C = A(BC)
교환 법칙(commutative) 성립 불가 : AB != BA
항등원의 곱셈 : IA = AI = A

Multiplying Feature Matrices

A가 n*d의 data 행렬이라고 가정할때 A와 At(transposed)의 곱에서

C = A⋅At 는 dot product의 n*n 행렬이다. points(docs)들의 “in sync-ness”를 나타낸다. 즉 Cij는 doci와 docj의 similarity를 나타낸다.
D = At⋅A 는 dot product의 d*d 행렬이다. features 들의 “in sync-ness”를 나타낸다. (similarity among terms)

이는 공분산 행렬(covariance matrices)로 해석 가능하다.

Interpreting Matrix Multiplication

0/1 인접 행렬을 곱하면 길이가 2인 path 개수를 구할 수 있다. 값이 1이면 node사이에 path 있는 것, 0이면 없는 것이다. 방향 그래프에서는 행렬이 비대칭 형태가, 그렇지 않다면 대칭 형태가 될 것이다.
permutation matrix 곱하면 행과 열을 재정렬할 수 있다.

Matrix Rank

만약 행렬에서 선형적(linear)인 관계에 있는 row 들이 존재한다면 좋지 않다. 서로가 dependent 하기 때문에 나머지에서 새로운 정보를 얻어낼 수 없을 것이다.

matrix의 rank 라는 것은 선형적으로 independent 한 row들의 개수와 관련있다. 따라서 n*n 매트릭스의 rank는 n 이 되는 것이 좋다. (full rank)

위의 식에서 전자의 경우 서로가 independent 하기 때문에 rank 는 2가 된다. 하지만 후자의 경우, 다른 식일지라도 linearly dependent 하기 때문에 다른 특징을 찾아낼 수 없고 rank 는 1이 된다.

Algebraic Proof : 2 = 1

네번째 줄 다섯번째 줄로 넘어갈때 (a-b)로 나누고 있는데, a=b이므로 devide by zero의 문제가 발생한다.

Lessons from the Proof

대수적 증명은 보통 왜 그것이 동작하는가에 대한 직관을 주지 못한다
증명하는 것이 만드는 것보다 쉽다
그럴지라도 division by 0 과 같은 특별한 케이스를 주의해야 한다
선형대수에서는 singular matrix (특이 행렬) 이러한 케이스들이다

Dividing Matrices

inverse operation(역연산)은 x를 항등원으로 만드는 것이다. 예를 들어 덧셈의 항등원은 0이므로 x의 inverse operation은 -x 이고 곱셈의 inverse operation은 나누기이다.

A⋅A-1 = A-1⋅A = I

위의 식이 성립할때 A-1을 A의 곱셈의 역원(multiplicative inverse)이라고 하며 여기서 I는 단위 행렬이다.

모든 matrix가 곱셈의 역원이 있는 것은 아니며 이렇게 곱셈의 역원이 없는 matrix를 singular matrix 라고 한다.

cf )단위 행렬(identity matrix)은 주대각선의 원소가 모두 1이며 나머지 원소는 모두 0인 정사각 행렬

Matrix Inversion

만약 matrix 곱셈의 역원이 있다면, 가우스 소거법(Gaussian elimination)을 이용한 선형계(linear system)를 풂으로써 구할 수 있다.

Inverse of Lincoln

LL-1에서의 대각선은 non-zero value.

이러한 과정에서 생기는 noise들은 다수의 floating point operation 에 의해 누적된 small numerical error 이다. 이러한 에러를 줄이기 위해 라이브러리에서 제공하는 함수는 고도로 최적화 되어 있다.

Increasing Lincoln Memorial’s Rank

만약 링컨 기념관을 나타내는 row들 사이의 관계가 선형 독립이 아니라 full rank 가 성립이 되지 않는다고 가정하자. 이럴때 적은 양의 random noise를 추가하면 심각한 이미지 왜곡을 하지 않고도 rank를 높일 수 있다.

Matrix Inversion and Linear Systems

Ax=b

위의 식에 A의 역원을 곱하면 아래와 같은 식을 도출할 수 있다.

(A-1⋅A)x = (A-1)b or x = (A-1)b

따라서 일차 방정식을 푼다는 것은 역행렬을 구하는 것과 같다.

Principal Component Analysis

주성분(principal component)을 분석한다는 것은 고차원을 저차원으로 줄이는 작업, 즉 차원 축소가 필요하다.

고차원을 2 차원으로 줄이려면 제일 중요한 축 2개를 잡으면 된다.

original data에서 maximum variance 를 찾을 수 있는 축
그 축과 90°를 이루되, 처음 축에서 잡힐 것들을 제거했을때 maximum variance 를 찾을 수 있는 축

기술적으로 이 축들은 공분산 행렬(At⋅A/ A⋅At)의 eigen vector(고유 벡터)이다. first/second eigen vector of Mt⋅M

cf) 고유 벡터 (eigen vector): 행렬 A를 선형 변환으로 봤을때, 선형 변환 A에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터

Singular Value Decomposition (SVD)

특이값 분해. matrix factorization method.

V*- compressed number 로 나타나 있지만 ML에선 모두 real number 이기 때문에 T로 표현해도 무방.

matrix M에 original data가 있다. 이때 중요한 n 개의 feature만 골라서 데이터를 표현하고자 한다면, 해당 feature를 표현하는 축(axis) n개를 골라서 원래 데이터와 곱한다. 해당 축 상에 origianl data 가 표현 될 것이고 이것을 projection이라고 한다.

현재 축 2개를 고르는 2D space projection을 하고자 할때, M⋅V2(nx2)를 하면 되고 그 결과는 m*2 matrix로 나타날 것이다. 이는 각 data point 들이 2D로 표현된 것이다.

한편 M는 U⋅Σ⋅Vt로 나눠 표현할 수 있는데, 이때 U는 M⋅Mt, Vt는 Mt⋅M의 형태이다. U의 각 열은 left singular vector 또는 eigen vector of M⋅Mt로, Vt의 각 열은 right singular vector 또는 eigen vector of Mt⋅M로 표현 가능하다. Σ에 표현된 0이 아닌 각 값은 singular value(특이치)이다.

M⋅V2 는 U⋅Σ⋅Vt⋅V2 와 동일하므로 Vt⋅V2를 먼저 계산하면 단일 행렬(identity matrix)과 비슷한 n*2 matrix가 나온다.