[2주차 - Day3] 인공지능 수학 - 자료의 정리(1)

7. 벡터와 직교분해

---

벡터(Vector)

벡터 : 길이와 방향의 물리량
벡터의 내적(inner product 또는 dot product)

• 좌표계 없이 표현
  두 \(n\)-벡터의 길이와 두 벡터 간의 사이각 \(\theta\)을 통해 다음과 같이 정의된다.
  $$u \cdot v=|u||v|\cos\theta$$

 

• 좌표계를 도입하여 표현
  \(u = (u_1, u_2, \dots, u_{n}), v = (v_1, v_2, \dots, v_{n}) \)의 좌표값을 통해 다음과 같이 계산된다.
  $$u \cdot v = u_1v_1+u_2v_2+\dots+u_{n}v_{n}$$

 

 

벡터의 내적 - 두 벡터의 내적이 0이면 두 벡터는 직교(Orthogonal)이다.
$$u \cdot v = 0 \Leftrightarrow u \perp v$$
\(u \perp v\) 일 때, \(u\)방향으로의 전진은 \(v\)방향에서 전혀 측정되지 않는다. 그 반대도 마찬가지.

(고교 과정에서 배운 \(xy\)-좌표계나 \(xyz\)-좌표계는 직교좌표계)

 

 

투영(Projection)

투영 : 어떤 벡터의 주어진 방향에의 성분을 구하는 것
(\(u\)를 \(Ax = b\)에서의 \(b\)로 생각해도 무방)
두 벡터 \(u, a\)가 있을 때
벡터 \(u\)를 \(a\) 위에 투영한 벡터를 \(proj_{a}u)라 하고 다음과 같이 구한다.

벡터 \(u\)를 \(a\)위에 투영하고 남은 보완 벡터(Complement vector)는 \(u - proj_{a}u\)이다.
벡터 \(u\)에서 \(u\)를 \(a\)에 투영한 벡터를 빼면 \(u\)를 \(a\)에 투영한 벡터에서 \(u\)를 가리키는 벡터를 구할 수 있음.
투영한 벡터와 보완 벡터는 직교한다.

 

정리

 1.  투영(Projection) 벡터와 보완(Complement) 벡터는 직교한다.

 

 2.  투영(Projection) 벡터와 보완(Complement) 벡터를 합하면 원래 벡터를 구할 수 있다.그림(원래 벡터는 투영 벡터와 보완 벡터로 나눌 수 있고, 이 나눔은 직교성을 보장한다.)

 

투영과 보완의 개념을 이용하여 직교 분할이 가능하다.

 

 

직교행렬(Orthogonal Marix)

행렬 : 각 열벡터가 기저(basis)를 이루는 좌표계

 

각 행렬의 열벡터끼리 내적이 0이면 직교한다고 한다.

 

직교행렬을 이용한 선형 시스템

일반적인 행렬(직교행렬이 아닌 행렬)에서는 각 열벡터들이 서로 연관성을 가지고 있어서 해를 구하기가 어려움
(첫 번째 열벡터와 두 번째 열벡터를 각각 얼마큼 쓰냐에 대해서 연관성이 존재 → 첫 번째
열벡터를 많이 쓰면 두 번째 열벡터는 적어지고, 첫 번째 열벡터를 조금 쓰면 두 번째 열벡터는 많이 쓰게 됨)

• 직교행렬(Orthogonal Matrix)
  선형시스템 \(Ax = b\)에서 행렬 \(A\)가 직교행렬이면, \(x\)는 역행렬 \(A^-1\)의 계산 없이 다음과 같이 구할 수 있다.
  • \(x\)의 \(i\)-번째 요소는 투영(Projection)으로 계산할 수 있다.
    -> 벡터 \(b\)를 행렬 \(A\)의 각 열벡터 \(a_{i}\)에 투영한 \(proj_{ai}b\)로 부터 다음을 계산

 

 

• 정규직교행렬(Orthonormal Matrix) (= 회전행렬)
  선형시스템 \(Ax = b\)에서 행렬 \(A\)가 정규직교행렬이면, \(x\)는 역행렬 \(A^-1\)의 계산 없이 다음과 같이 구할 수 있다.
  • \(x\)의 \(i\)-번째 요소는 투영(Projection)으로 계산할 수 있다.
    -> 벡터 \(b\)를 행렬 \(A\)의 각 열벡터 \(a_{i}\)에 투영한 \(proj_{ai}b\)로 부터 다음을 계산
  • 정규직교행렬에서 모든 \(a_{i}\)(행렬 \(A\)의 열벡터)의 길이 \(|a|\) 는 1이기 때문에 내적만 수행하여도 된다

 

직교행렬의 장점

1. 역행렬 계산 없이 해를 구하는 것이 가능
2. \(x_{i}\)와 \(x_{j}\)의 계산은 독립적 -> \(x\)의 계산은 병렬처리가 가능

 

 

---

QR 분해

주어진 행렬을 직교행렬로 만들 수 있으면 직교행렬의 장점을 이용할 수 있음

 

QR 분해  

 

주어진 행렬 \(A\)에서 정규직교행렬 \(Q\)와 그 나머지 \(R\)을 추출하는 행렬분해

• \(Q\) : 행렬 \(A\)에서 정규직교성을 추출한 정규직교행렬
• \(R\) : 행렬 \(A\)에서 정규직교성을 추출 후 남은 나머지들 (residual), (상삼각행렬 모양)

 

푸는 순서

 

 

 1.  \(Q\)(정규직교행렬)에서 내적을 이용하여 풀고

 

 2. \(R\)(상삼각행렬)에서 후방대치법을 이용하여 연산

-> LU 분해와 유사

 

 

 

QR 분해의 의미

QR 분해는 주어진 행렬에서 정규직교성을 추출하여 계산의 편의를 도모함

 

QR 분해의 활용

• 빠른 계산
  선형시스템 \(Ax = b\)의 해를 구할 때, 정규직교행렬 \(Q\)를 이용한 계산 부분은 병렬처리로 빠르게 계산 가능.
  (하지만 \(R\)을 이용한 계산 부분은 병렬처리가 불가)
• \(b\)가 자주 업데이트 되는 경우 # LU 분해와 동일
  선형시스템 \(Ax = b\)에서 행렬 \(A\)는 고정되어 있고, \(b\)가 자주 변하는 문제가 있다.
  이런 경우, 행렬 \(A\)를 미리 \(QR\)로 분해해두면 \(b\)가 업데이트될 때마다 선형시스템의 해 \(x\)를 실시간으로 구할 수 있다.

 

QR 분해 VS LU 분해

• \(LU\)분해의 경우, 선형시스템을 풀 때 병렬처리 불가능
• \(QR\)분해의 경우, \(Q\) 행렬이 꽉찬 구조를 가진 행렬이므로, 메모리 사용량이 많다

 

 

8. SVD, PCA

---

특이값 분해(SVD; Singular Value Decomposition)

\(LU\) 분해와 \(QR\) 분해는 \(m \times n\) 정방행렬(Square Matrix)에 대한 행렬분해인 반면,
특이값 분해는 일반적인 \(m \times n\)행렬에 관한 행렬 분해이다.
-> 특이값 분해는 직교분할, 확대축소, 차원변환 등과 관련이 있다.
특이값 분해는 주어진 아래의 형태를 가지는 세 행렬의 곱으로 나누는 행렬분해이다.

 

• \(U\) : \(m\)차원 회전행렬 (정규직교행렬)
• \(D\) : \(n\)차원 확대축소 (확대축소 크기에 따른 정렬 형태)
• \(V\) : \(n\)차원 회전행렬
  \(V -> D -> U \) 방식으로 구성됨

 

 

특이값 분해 예제

 

 

특이값 분해 의미

 

 

특이값 분해 활용

\(A\)의 특이값 분해 \(U\), \(D\), \(V\)는 각각 열벡터의 순서대로 행렬 \(A\)의 열벡터가 어떤 방향으로 강한 응집성을 보이고 있는지를 분석한 것

\(U, D, V\)의 열벡터 순서대로 \(p\)개 취한다면, 강한 응집성을 가지는 \(p\)개의 방향으로 수선의 발을 내린 \(A\)의 근사치 \(A^`\)를 재구성할 수 있다.
(강한 응집성이란 것은 원래 행렬에 대해서 가장 높은 응집성을 가진 방향을 의미.
\(D\)행렬이 정렬되어 있다고 했는데, 큰 것부터 작은 것으로 정렬되어 있을 때 수치가 가장 큰 부분 -> 첫 열벡터)
응집성이 가장 강한 부분의 값이 높을수록 응집성이 강하다고 할 수 있다.

 

 

---

주성분분석(Principal Component Analysis; PCA)

다수의 n차원 데이터에 대해, 데이터의 중심으로부터 데이터의 응집력이 좋은 n개의 직교 방향을 분석하는 방법

주성분분석은 데이터의 공분산행렬(covariance matrix)에 대한 고유값 분해에 기반을 둔 직교분해이다.

 

공분산행렬(covariance matrix) : 중심으로부터 각각의 데이터가 어느 방향으로 뻗어 나가있는 지에 대한 외적행렬을 구하고, 외적행렬의 합을 도출

빨간색 벡터는 응집력이 높고, 파란색 벡터는 응집력이 낮음(서로 직교)

 

 

---

다음과 같은 데이터가 있을 때, 

 

공분산행렬과 이에 대한 주성분분석(PCA)는 다음과 같다.

\(W^T\)는 \(W\)의 Transpose(전치)
모든 데이터에 대해서 각각 외적을 하고 합을 구하면 \(\begin{bmatrix} 28 & 18 \\ 18 & 12 \end{bmatrix} \)가 나오게 되는데 데이터 수만큼 나누어서 평균을 구함

 

외적

\((2, 1)\) 데이터에 대한 외적은 \(\begin{bmatrix} 2 \\ 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \end{bmatrix} \) 외적을 하면 \( \begin{bmatrix} 4 & 2 \\ 2 & 1 \end{bmatrix} \)이 나오게 됨

• \(W\) -> 빨간색 벡터와 파란색 벡터를 그림
• \(D\) -> 빨간색 벡터는 6.3 만큼, 파란색 벡터는 0.55만큼 증폭

차원 축소를 한다면 빨간색 벡터만 남기고 파란색 벡터는 없애도 데이터를 표현 가능
어느정도 오차는 있지만, 받아들일 수 있는 적은 오차만 발생

 

 

 

 

9. 벡터공간과 최소제곱법

---

집합(set) : 임의의 원소(element)를 수집하여 만든 모임

"집합이 OO연산에 닫혀 있다" == 연산을 수행 후 결과가 원래 집합에도 포함되어 있다.

예시)

1. \({{x|x\in R(실수)}}\) → 덧셈 연산, 곱셈 연산에 닫혀 있다.
2. \({−1,0,1}\) → 덧셈 연산은 닫혀있지 않고, 곱셉 연산에는 닫혀 있다.

 

 

공간(Space)

공간(space)은 다음 두 연산에 닫혀 있는 집합이다.

• 덧셈연산에 닫혀 있다
  집합에서 임의의 두 원소 x, y를 뽑아 더해도 그 결과인 x + y는 집합의 원소이다.
• 스칼라 곱 연산에 닫혀 있다
  집합에서 임의의 한 원소 x를 뽑아 임의의 스칼라 s배 한 결과인 sx는 집합의 원소이다.

모든 n-벡터 집합 \(R^n\)은 n차원 벡터 공간(vector space)라 부를 수 있다.

 

 

 

열공간(Column Space)

행렬 \(A\)의 열벡터들에 대한 가능한 모든 선형조합의 결과를 모아 집합으로 구성한 것

\(Ax = b\) 에서
\(A\)의 열벡터를 조합해서 \(b\)를 만들 수 있으면 해가 존재한다.
-> 열공간에 존재하면 해가 존재한다.

 

 

---

최소제곱법(Least Squares Method)

최소제곱법의 의미

선형시스템 \(Ax = b\)에 대한 해가 없음에도 불구하고, 우리가 할 수 있는 최선이 무엇인가?
\(b\)가 \(A\)의 열공간에 없기 때문에 풀 수 없지만 제일 가까운 지점은 찾을 수 있다.

행렬 \(A\)가 정의하는 열공간에서 우리의 목표 \(b\)와 가장 가까운 지점은 \(b\)를 열공간에 투영(projection)한 지점일 것이다.
→ \(b\)를 \(A\)의 열공간 \(col(A)\)로 투영(projection)

즉, 달성가능한 최선의 목표 \(proj_{w}b\) 를 생각할 수 있다.

 

 

최소제곱법(Least Squares Method)

최소제곱법은 선형시스템 \(Ax = b\) 에 대한 해 x가 없음에도 불구하고할 수 있는 최선의 대안 \(\bar{x}\)를 내놓는 기법이다.

최소 제곱법은 원래의 선형시스템 \(Ax = b\)가 아닌 다음의 선형시스템을 해결한다.
$$ A\bar{x} = \bar{b} (단, \bar{b} = proj_{w}b) $$

이 방법은 원래 목표 \(b\) 와 달성 가능한 목표 \(\bar{b}\) 의 차이를 나타내는

벡터 \((b-\bar{b})\)의 제곱길이를 최소화시키는 의미를 가지기 때문에 최소제곱법(least square method)

 

 

최소제곱법의 해 구하기

주어진 선형시스템의 양변에 전치행렬 \(A^T\)를 곱하면 최소제곱법의 해를 구할 수 있다.

 

 

 

최소제곱법 응용: 선형회귀

선형회귀 문제는 다음과 같이 최소제곱법으로 풀 수 있다.

 

 1. 선형시스템 구성
직선이 각 정점을 모두 지나간다고 가정하고 선형시스템 \(Ax = b \) 구성
(단, 주어진 모든 정점을 지나가는 직선은 존재하지 않으므로 선형시스템의 해는 존재하지 않음.)

 

 2. 최소제곱법 적용
\(A^{T}A\bar{x}=A^{T}b\) 를 생각하고, \(\bar{x}=\begin{bmatrix}\bar{m}\\ \bar{b}\end{bmatrix}\) 를 구한다.