linear algebra

Linear Independence, Span, and Subspace

Linearly Independent(선형 독립)

  • 기하학적으로 살펴보게 되면, 선형시스템을 이루는 벡터들에 스칼라배한 오직 하나의 평행사변형만을 통해 상수벡터 $ b $ 를 만족시키는 경우에는 Unique Solution을 갖게 되는 것이고, 상수벡터를 여러개의 평행사변형으로 표현할 수 있다면 무수히 많은 Solution을 갖는다.

유일한 해를 갖는 조건

  • 위에서 언급한 linearly Independent란 아래 그림과 같이 기존의 $ a $ 벡터와 $ b $ 벡터로 이루어진 행렬에서 추가적으로 $ c $ 벡터를 열벡터로 받아 만들어진 행렬의 Span 변화를 생각해보면, 기존의 $ a $ 와 $ b $ 열벡터들간의 조합으로 만들어질 수 있는 Span에서 $ c $ 가 추가 되었음에도 불구하고 변화가 없게 된다. 이러한 경우 linearly dependent하다고 볼 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a = np.array([0, 1])
b = np.array([1, 0])
c = np.array([1, 1])
plt.figure(figsize=(12, 8))
plt.annotate('', xy=a, xytext=(0, 0), arrowprops=black)
plt.annotate('', xy=b, xytext=(0, 0), arrowprops=black)
plt.annotate('', xy=c, xytext=(0, 0), arrowprops=black)
plt.text(0, 1.2, "$a$")
plt.text(1.2, 0, "$b$")
plt.text(1.15, 1.15, "$c$")
plt.xticks(np.arange(-2, 4))
plt.yticks(np.arange(-1, 4))
plt.xlim(-2.4, 3.4)
plt.ylim(-0.8, 3.4)
plt.show()

Span의 변화

  • 위의 방법처럼 벡터를 하나씩 늘려 나갈 때 마다 기존의 Span에 포함되어있는지를 확인해보면서 linearly dependent한지를 찾는 것도 하나의 방법이다. 만일 기존의 벡터들의 Span에 포함되어있지 않다면 linearly independent가 될 것이다.

벡터들이 Linearly Independent한지 확인하는 법 - 01

  • 행렬의 $ V_{1}, V_{2}, \ldots, V_{n} $개의 열벡터에 대해 homogeneous linear system인 을 만족하는 $ C_{1}, C_{2}, \ldots, C_{n} $ 을 찾을 때, 오직 $ C_{1} = C_{2} = \cdots = C_{n} = 0 $ 인 경우 해당 행렬의 열벡터들이 linearly independent 하다고 말한다. 왜냐하면 열벡터들 중 0이아닌 다른 상수로 스칼라배를 하여 영벡터를 만들어 냈다는 의미는 서로 스칼라배로 만들어질 수 있는 관계라는 의미이기 때문이다.
  • 아래의 $ C_{1} $, $ C_{2} $, $ C_{3} $ 가 모두 $ 0 $ 값을 갖아야 영벡터를 만들 수 있으므로 아래 열벡터들은 서로 linearly Independent 하다고 할 수 있다.
  • 아래 행렬도 동일하게 열벡터들간의 선형조합으로 영벡터를 만족시키기 위해선 스칼라들이 모두 다 0이어야 하기 때문에 linearly Independent하다.

벡터들이 Linearly Independent한지 확인하는 법 - 02

  • 또 다른 방법으로 마지막으로 추가된 열벡터의 선형조합을 제외하곤 나머지를 우변으로 넘겨 해당 조합들로 마지막 열벡터를 만들 수 있다면 마지막 열벡터는 기존의 열벡터들의 선형조합에 대한 Span에 포함되있는 것이므로 이 또한 linearly dependent 가 될 것이다.

벡터들이 Linearly Independent한지 확인하는 법 - 03

  • 위에서 한 번 언급한 것과 같이 linearly dependent한 경우에는 Span의 변화가 없다. 즉, 열벡터가 하나 추가 되어도 Span이 증가하지 않는다.

Linearly Dependent한 상황에서의 Span의 변화

  • linear dependence한 집합은 여러개의 가능한 선형조합을 만들 수 있다는 것이다. 여러 가능한 조합들이 있으므로 solution도 무수히 많다.

Linear dependent와 solution의 관계 - 01

Linear dependent와 solution의 관계 - 02

  • linear independent한 경우에는 해당 상수벡터(b)를 만들 수 있는 조합이 unique하기 때문에 solution도 unique하다.

Linear independent와 solution의 관계

Subspace and Span

  • Subspace는 이전에 말했던 것과 같이 총 4가지로 말할 수 있는데 근본적인 개념을 여기서 다시 한번 짚고 넘어갈 것이다. n차원상의 선형결합에 닫혀있는 부분집합으로서 정의된다. 즉, 벡터들의 선형결합에 닫혀있기 때문에 span에 포함되어진다고 말할 수도 있다.

Span과 Subspace의 관계

  • Basis vector의 의미는 아래 2가지를 만족하는 벡터를 의미한다.
    • 주어진 subspace를 완전히 Span해야한다.
    • linearly independent해야한다.
  • 즉, linearly independent vectors to fully span the vector space라고 할 수 있다.
  • number of minimum vectors to span the vector subspace = maximum number of linearly independent vectors

Subspace의 Basis vector

  • basis vector가 먼저 정해지면, 해당 vector space내에 존재하는 특정 벡터를 계산하는 방식은 unique하다. 허나, 임의의 vector space에 대한 Basis vector들은 unique하지 않다. 즉, 어떤 vector space를 fully span하더라도 그 linearly independent한 vector의 집합인 Basis vector들은 unique하지 않는다는 것이다. 말로는 잘 이해하기 어렵다면 아래 예를 통해 이해해보자.
  • 아래 2가지 조합들 모두 Basis이다. vector space에서 Basis vector는 unique하지 않음을 확인할 수 있다. 허나 Basis vector들이 정해지면 특정한 vector를 linear combination해서 만들어낼 수 있는 $ C_{1}, C_{2} $ 와 같은 계수의 조합은 unique하다.

Basis vector의 비유일성

  • 위에서 본 조합처럼 Basis vector들이 unique하지 않기 때문에 linear combination을 찾는 방법은 여러가지일 것이다. 이를 위해 Basis vector들 간에 서로 수직인 조건을 만족하면 계수를 더 쉽게 찾을 수 있는데 이는 추후에 다시 다루어 볼 것이다.

  • 잠깐 맛보기로 설명해 보자면, $ \text{Basis vector들의 내적} = 0 $ 즉, Basis vector들끼리 서로 수직이라는 의미인 Basis independent라는 개념을 $ Ax = b $ 라는 방정식을 푸는데 적용시킬 수 있다. 여기서 A행렬의 크기는 $ m > n $인 $ m \times n $ 으로 가정할 것이다. 그렇다면 위의 방정식을 만족하는 solution은 존재하지 않는다는 것을 이미 배웠기 때문에 알 수 있다.

  • 해가 없으므로 $ || Ax-b || $ 가 최소가 되도록 $x$ 라는 적절한 근사 해를 구하자는 것이 Least square 문제이다. 행렬 A를 column vector 들의 선형조합으로 생각해보면 $ Ax $ 는 $ x $ 가 무엇이든 column space 내에 존재할 것이다. 허나 상수 벡터 $ b $ 는 column space 내에 존재하지 않기 때문에 column space의 부분집합인 $ Ax $ 와 상수 벡터 $ b $ 간의 거리를 최소화한 solution이 우리가 찾는 최적의 solution이 될 것이다. 거리를 최소화한 것은 결국 상수 벡터 $ b $ 에서 수선의 발을 $ Ax $ 내려 연결한 벡터의 길이가 될 것이므로 최종적으로 $ \underset{x}{\arg\min} || Ax-b || $ 를 찾아야 한다.

basis vector들과 최소제곱법을 통한 선형시스템 해 구하기의 연관성

  • 특정한 subspace $ H $ 가 주어졌을때 basis vector들은 여러개가 존재하지만, 그럼에도 해당 subspace H에 대한 basis vector들의 수는 unique하다. 그 개수를 subspace $ H $의 차원수라고 한다. 앞의 그림에서 평면은 2차원이었는데 이는 해당 subspace에 대한 어떠한 basis vector를 뽑던 2가지의 벡터로 구성된다는 의미를 갖는다.

Subspace의 차원

  • 먼저 행렬 A의 column 벡터들의 선형조합으로 만들 수 있는 Span을 Column Space라고 한다.

Column Space의 정의

  • 행렬의 linearly independent한 column vector의 개수가 곧 해당 subsapce의 차원의 수가 되며, rank이다.

행렬의 선형 독립 벡터들

  • 아래와 같이 rank들을 계산할 수 있으며, Machine learning에서 최소한 linear model(선형회귀, SVM 등...)에서는 Rank가 작다는 의미는 그만큼 linearly dependent한 column들이 많다는 얘기로 dependency한 feature들이 많으므로 데이터의 size가 커보이더라도 모형의 학습에 있어서는 쓸모없는 feature들이 많다는 이야기이므로 되도록 linearly independent한 feature들만을 사용하도록 해야한다. 이런 의미에서 선형회귀에서의 다중 공선성을 검사하는 것은 동일한 문제를 보완하는 것이라고 필자는 생각한다.

행렬의 rank

예시 1)

  • 아래의 두 벡터를 combination하더라도 벡터의 3차원은 항상 0이므로 결국에는 x,y 평면(2차원)을 나타내는 것이다. 또한 두 벡터가 서로 linearly independent한 column 벡터들이므로 Rank는 2이다.

예시 2)

  • 아래 동일한 matrix를 한번은 linearly independent한 column vector들의 개수를 통해 Dim Column Space를 찾고 다른 한번은 가우스 소거법을 통해서 찾는 방법을 풀이해 놓았다. Dimension은 2개로 마지막 가우스 소거법을 통해 푼 방법을 살펴보면 free variable의 위치의 vector들은 Independent한 pivot variable 위치의 벡터들의 조합으로 만들 수 있으므로 Column space를 구성할 때 없어도 상관없기 때문에 2개의 차원수를 갖는다.
Share