프로그래머스 인공지능 데브코스 3기 수업내용 정리 #5(인공지능 수학 - 선형대수)

Jupyter Notebook 시작하기

• 개발을 하는 과정에서 코드를 작성하게 되고 코드를 작성하는 툴 IDE를 사용하게 된다. Terminal, Eclipse, Visual studio등을 사용할때는 코드 외에는 주석 처리를 하게 된다. 하지만 주석이 너무 길어지면 코드의 흐름을 따라기가 어려워진다.
  인공지능은 수식이 필요하기 때문에 맥락을 덧붙여주어야 한다.
  Jupyter Notebook은 코드의 작성과 공유를 위한 개발도구이다.

• Jupyter Notebook의 명령어
  ESC로 명령모드 Enter로 입력모드를 전환
  Y로 Code Cell, M으로 Markdown Cell
  명령모드에서 A로 위에 Cell추가, B로 아래 Cell추가
  명령모드에서 dd로 핸재 Cell 삭제
  ctrl + Enter, shift + Enter로 Cell을 실행

• Makrdown : 일반 텍스트로 서식이 있는 문서를 작성하는 방법

# str : header
*str* or _str _ : italic
**str** or __str__ : bold
~str~ : strikethrough
* str or - str : unordered list
1. str : ordered list

Numpy로 숫자 다루기

1. Numpy 시작하기

   python의 list는 연산이 느리기 때문에 연산에 적합한 라이브러리인 numpy를 사용한다.

import numpy as np
#numpy의 연산 속도를 비교해보자.
#List의 경우 302us 1000 loops each
L = range(1000)
%timeit [i**2 for i in L]

#numpy.array의 경우 895ns 1000000 loops each
N = np.arange(1000)
%timeit N ** 2

2. numpy의 Container, array

#행렬식으로 표현이 가능하다.
arr_2d = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
#array([[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]])
arr_2d.shape
#(3,3)

선형시스템(Lenear System)

선형시스템 복습

1. 일차 방정식

• 일차방정식 3x = 6 -> x = 2
• 연립일차방정식 3x + y = 2, x - 2y = 3 -> x = 1, y = -1
• 좀더 복잡한 연립 일차 방정식
  3x + y + z = 4
  x - 2y - z = 1
  x + y + z = 2
• Gauss소거법은 식들의 항을 소거해서 더이상 소거를 하지 않아도 되는 일차방정식으로 만드는 방법이다. 하지만 식과 미지수가 늘어나면 소거법으로 해결 하기가 쉽지 않다.

2. 선형대수의 목표

• 어떤 연립일차방정식, 즉 어떤 선형시스템linear system 문제라도 정형적인 방법으로 표현하고 해결하는 방법을 배우는 것이다.

• 선형방정식 linear equation
  3x + y + z = 4
  x - 2y - z = 1
  x + y + z = 2
  이 방정식들을 각각 선형방정식이라고 한다. 선형방정식에서 linear는 선의 형태라는 뜻이다. 평면과 같은 왜곡되지 않은 공간에서 올곧게 그려지는 식을 의미한다.

• 미지수 Unknowns
  x, y, z를 각각 미지수 unknown or variable이라고 한다.
  그리고 위와 같이 3개의 linear equations와 3개의 uknowns로 구성된 연립일차방정식을 3 x 3 linear system이라고 한다.

• 선형방정식의 예시

2 x 3 linear system

3x + y + z = 4
x - 2y - z = 1

1 x 2 lenear system

2x + y = 3

3 x 2 linear sytem

2x + y = 2
x -2y = 3
2x -4y = 6

미지수의 승수가 1승으로만 구성되어 있다면 그 방정식은 직선이나 평평한 형태로 그려진다.

• 비선형방정식

sinx + y = 2
삼각함수의 형태는 곡선이 생기므로 반드시 비선형방정식이 된다.

3x + y^3 = 2
y미지수가 3승이므로 곡선과 관련하는 비선형방정식이 된다.

xy + z = 3
위와 같은 방정식은 미지수끼리 곱해져 있기 때문에 2승이 존재한다고 생각해야 한다.

선형시스템의 대수적 표현

1. 선형시스템을 Ax = b로 표현하기
   선형시스템의 unknows를 모아 column vector x로 표현한다.
   선형 시스템의 선형방정식에 대해 다음을 수행한다.

• 계수를 모아 A의 row vector로 표현한다.
• 상수를 모아 b에 표현한다.

2. 예시

3x + y = 2
x - 2y = 3
2x - 4y = 6를 Ax = b꼴로 표현하면

 A     x  =  b
[3  1] [x]   [2]
[1 -2] [y] = [3]
[2 -4]       [6]

3. m x n 선형시스템의 Ax = b표현을 정리하면 다음과 같다.

• 식은 행이고, 행은 식이다.(linear equation <-> row)
• m은 lenear equation의 개수이다.
• n은 unknown의 개수이다.
• A는 m x n 행렬이다.
• X는 n벡터이다.
• b는 m벡터이다.

선형 시스템 실습

행렬과 벡터의 코딩 및 연산

1. Ax = b의 해를 찾기

import numpy as np
A = np.array([[3,1,1], [1,-2,-1],[1,1,1]])
b = np.array([4,1,2])
A_inv = np.linalg.inv(A)
x = A_inv @ b

2. 결과 검증

bb = A @ x
if np.linalg.norm(b - bb) < 1e-3:
	print('OK')
else:
	print('something wrong')

가우스 소거법

선형 시스템의 해

1. 가장 간단한 형태의 선형 시스템은 ax = b(단, a와 b는 스칼라)이다.
   x = b * a^-1이지만 아래와 같은 경우의 수가 존재한다.

• 해가 하나인 경우(unique solution) : 3x = 6
• 해가 없는 경우(no solution) : 0x = 6
• 해가 여러개인 경우(infinitely many solutions) : 0x = 0

2.a = 0이면 특이하다.

• ax = b의 해가 곧장 나오지 않는다.
  a의 역수(inverse)가 존재하지 않는 경우, a가 특이(singular)하다고 한다.

• 해가 있으면 선형시스템이 consistent하다고 한다.(해가 있거나 여러개이다.)

• 해가 없으면 선형시스템이 inconsistent하다고 한다.(해가 없다.)

  3.예시

• 해가 하나인 경우
  x + 3y = 2
  -2x +y = 3

• 해가 없는 경우(평행하는 두 직선)(A의 역행렬이 존재하지 않음)
  x + 3y = 2
  2x + 6y = 5

• 해가 여러개인 경우(동일한 두 직선)(A의 역행렬이 존재하지 않음)
  x + 3y = 2
  2x + 6y = 4

  가우스 소거법 Gauss elimination

  Gauss elimination은 임의의 m x n 선형 시스템의 해를 구하는 가장 대표적인 방법이다. Gauss elimination은 다음의 두 단계로 수행된다.

• Forward elimination(전방소거법) : 주어진 선형 시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형한다.
  back-substitution(후방 대입법) : 아래에서부터 위로 미지수를 실제값으로 대체한다.

1. 전방 소거법
   주어진 선형 시스템은 전방소거법을 통해서 변형이 된다. 이때 선형시스템은 아래로 갈수록 더 단순한 형태의 선형방정식을 가지게 된다.
   x + 2y + z = 1(E1)
   x + 2y + 3z = 3(E2)
   2x + 3y -z = -3(E3)
   전방 소거법의 알고리즘을 따져보자. 1열의 1행은 남아도 되기에 그 밑 열의 숫자들은 소거한다. 2열의 2행은 남아도 되기에 그 밑 열의 숫자들은 소거한다. 마찬가지로 n열의 n행은 남아도 된다. 기준을 정리하는 식으로 알고리즘을 순서대로 정리해보면

• 1열을 정리하면 다음과 같다. E2 = E2 - E1, E3 = E3 -2E1
  2열을 정리하기위해 2열 2행을 보면 숫자가 사라졌다. 그래서 E2와 E3를 교환한다.
  또한 기준의 항은 1이 좋기 때문에 E2 = E2 * -1을 한다.
  3열의 3행은 1항이 되도록 2로 나누어 준다.
  결과물은 다음과 같다.

x + 2y +z = 1
y + 3z = 5
z = 1

2. 후방 대입법
   위의 예시에서 볼수 있듯이 전방 소거법으로 정리가 된 선형 방정식은 후방 대입법으로 손쉽게 그 해를 구할 수 있게 된다.

3. 소거법에 쓰이는 Elementry Row Operations

• Replacement : j번째 행을 기준행인 i번째 향을 m배 곱한뒤 빼서 업데이트한다.
  Interchange : j번째 행과 i번째 행의 위치를 서로 바꾼다.
  Scaling : j번째 행을 s배 스케일링 한다.

• Gauss elimination에서 forward elimination의 가치는 다음과 같다.

1. 주어진 선형 시스템을 가장 풀기 쉬운 꼴로 변형해 준다.
   상삼각 형태 upper triangle
2. 주어진 선형 시스템의 rank를 알려준다.
   주어진 선형 방정식들이 실제로 의미가 있는 식인지를 알 수 있다.
3. 선형시스템이 해가 있는지(consistent) 아니면 해가 없는지(inconsistent) 알려준다.