webb-c.log

환경설정 기록

Sat, 27 May 2023 10:51:26 GMT

anaconda 재설치

버전 문제랑 기본 파일 깨짐 등등 여러가지 문제로 죽어가길래 그냥 한번 갈아엎고자 conda를 재설치 했다. 설치할 때 환경변수 추가하는걸 까먹어서 실행이 인식 못하던 문제가 하나 있었다.

윈도우에서는

시스템 환경변수 편집 > 고급 > 환경변수에서 a. 만약 본인이 현재 User에 대해서만 설정했다면 User 탭에서, b. 전체 User에 대해서 conda를 설치했다면 System 탭에서
"Path" 변수를 더블클릭하고 다음 3개의 폴더를 추가해주면 된다. a. anaconda b. anaconda/Library c. anaconda/Scripts

추가를 완료한 뒤 다음 명령어를 통해 제대로 설치 되었는지 확인해보자.

conda --version

cuda version 확인

사용하는 GPU에 따라서 tensorflow-gpu의 권장 버전이 다르다는 이야기가 있기 때문에 cuda version을 확인했다.

cuda는 NVDIA에서 개발한 병렬 컴퓨팅 및 프로그래밍 모델로, NVIDA에서 제작한 GPU가 효율적인 병렬처리 연산을 할 수 있도록 지원하기 위한 소프트웨어이다.

CUDA version 확인하기

nvcc --version

-> 내가 사용하는 컴퓨터의 version은 11.3 인 것을 확인했다. 여기서 문제 :

그 외 알아두면 유용한 CUDA 명령어

GPU상태, 메모리 사용 등을 표기

nvidia-smi

자 이제 가상환경(들)을 만들어보자

가상환경 설정

만들기

conda create -n {가상환경이름}

추가적인 다양한 옵션을 쓸 수 있다. 유용해 보이는 옵션만 몇개 적어본다.

python 버전 지정 python=버전

활성화 및 비활성화

conda activate {이름}

패키지 관리

pip이랑 conda를 사용할 수 있다. pip을 쓰면 서로 다른 버전때문에 발생하는 호환성 문제를 해결하지 않지만 대부분의 라이브러리를 지원하며, conda는 라이브러리를 설치할 때 호환성을 고려하여 설치해준다. (*pip은 권한 문제가 발생할 수 있는데, 이때는 가장 뒤에 --user를 붙여주자.)

설치

특정 버전을 설치하고 싶다면,

pip : =={버전}
conda : ={버전}
```
pip install {라이브러리이름}
```

```bash
conda install {라이브러리이름}

업그레이드

pip install --upgrade {라이브러리이름}

conda upgrade {라이브러리이름}

삭제

pip uninstall {라이브러리이름}

conda remove {라이브러리이름}

기타 명령어 들 (conda, pip)

현재 환경에 설치된 라이브러리 출력

conda list

가상환경 리스트

conda info --envs

가상환경 삭제

conda remove -n {가상환경이름} --all

실전도입

총 3개의 가상환경을 만들어야한다. 하나는 tensorflow를 사용하며, 다른 하나는 torch를 사용하고 마지막을 torch와 image처리와 관련된 다양한 응용을 사용하는 환경이다. tensorflow-gpu를 잘... 사용하고자한다.

GPU 못 찾음

~~버전문제가 아니었다. 그냥 지금 torch든지 tensorflow든지 그냥 GPU를 못 잡고 있다.~~ 인줄 알았는데 tensorflow는 버전 문제가 맞았다. ㅋㅋㅋ CUDA 11.2까지 GPU를 지원하는 2.10버전을 사용하는데 내 컴퓨터에 깔려있는 CUDA는 11.3이고... 이거 한번 돌리고 다시는 안 쓸 tensorflow 사용하기 위해서 CUDA 재설치하는건 너무 낭비라고 생각하기 때문에 걍 pytorch만 잘 해보려고 한다.

해결하려는 과정을 써보려한다.

cuDNN 활성화 여부 확인

if torch.backends.cudnn.enabled:
 print("활성화")

CUDA version에 맞는 pytorch 설치하기 https://download.pytorch.org/whl/cu113/torch_stable.html

나는 11.3이므로 cu113을 써두었다. 자신에게 맞는 버전으로 url를 바꾸면 된다. 해당 CUDA버전과 호환이 잘 되는 pytorch 버전을 찾아볼 수 있다.

하지만 문제가 읎음 -> ??

새로운 문제... nvcc-v로 확인한 CUDA버전이랑 nvidia-smi로 확인한 버전이 다르다.

=> 큰 문제 아니고 그냥 nvcc-v를 참고하라함...? 뭘까

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그냥 바보짓함...

당연히 나는 선배가 cuDNN설치 했을 줄 알았고 위에 코드도 True로 나오길래 음. 있구만 했었는데.. 아니었다. 위에 코드는 뭐지...? 써서는 안되는 코드인가 어이없음. 혹시나 해서 include, lib 라이브러리 가봤는데 cudnn 관련 파일들이 없었다... 그래서 다운 받고 추가해줬다.

미래에 도움 될 수 있으니까 설정 관련 정보 추가한다.

cuDNN 다운 받는 곳

https://developer.nvidia.com/rdp/cudnn-archive

-> 압축 파일을 받아서 생긴 lib, include, bin 폴더 안에 있는 파일들을 NVIDIA GPU ~~ > CUDA > v11.3에다가 옮겨준다.

CUDA 환경변수 설정하는 방법

사용자 환경변수의 Path에다가 아래 3개의 폴더를 추가해준다.

시스템 환경변수에는 CUDA 설치시 기본적으로 CUDA_PATH와 CUDA_PATH_V11_3이 만들어진다.

~~*근데 왜 아직도 안됨? *~~

💙 CUDA 사용을 위한 pytorch 설치 방법

CUDA 버전에 맞는 pytorch와 toolkit 설치하기

위 사이트에서 내가 사용하는 os, CUDA버전에 맞게 pytorch를 설치하는 방법이 나와있다. 나는 바보였고... cudatoolkit 도 함께 설치해줘야하는 걸 모르고 있었다.

KoBERT

koBERT를 사용하는 프로젝트가 하나 있는데 개발한 사람이 window를 고려안한건지 뭔지 잘 모르겠지만 mxnet이랑 trnasformer간에 numpy 버전 충돌이 있어서 계속 설치가 안되는 문제가 있었다.

https://github.com/SKTBrain/KoBERT/issues/84

위 issue를 참고하여 그냥 직접 설치명령어를 실행하니까 오류메시지가 나기는하는데 그래도 설치가 되긴한다.

[강화학습] Model Free Control

Mon, 30 Jan 2023 07:06:09 GMT

본 포스팅은 David Silver 교수님의 강화학습 강의와 그 강의를 정리한 팡요랩 강의를 바탕으로 정리한 것입니다.

환경을 알지 못하는 상황에서 던져진 Agent를 이용하여 어떻게 최적의 policy를 찾을 것인가?

1. Model-free control

1.1 model-free control의 문제점

⚠️ model-free환경에서 control문제를 해결할때는 MDP를 모르기 때문에 발생하는 여러 문제점이 존재한다. (=$\mathcal P^a_{ss'}, \mathcal R^a_s$를 알지못한다)

policy iteration의 원리
- 기본적으로 control문제를 풀기 위해서는 policy evaluation과 policy improvement를 반복해서 수행하면서 점차 개선된 policty를 찾아나가는 과정을 필요로한다.
- 이때, policy evaluation과 improvement 각 단계에서는 어떤 method를 적용하여도 된다.
  
  e.g. (model-based에서는) iterative, greedy

![](https://velog.velcdn.com/images/webb-c/post/a9ebfb85-1b29-42f5-95a5-9e4b3ff061a0/image.png)

MDP를 모를 때 발생하는 문제점
1. Iterative policy evaluation을 적용할 수 없다.
  
  Iterative policy evaluation은 Bellman Expectation Equation을 기반으로 value를 계산해나가는 과정이다.
  
  그런데 Bellman Expectation Equation에는 MDP를 알아야만 알 수 있는 요소$^*$들이 존재하기 때문에 MDP를 알 수 없는 model-free환경에서는 이 식을 그대로 적용할 수 없다.
  - state $s$에서 action $a$를 했을 때 받는 reward는 실제로 Agent가 경험해봐야만 알 수 있다.
  - state $s$에서 action $a$을 했을 때 어떤 state $s'$에 도달하게 되는지는 실제로 Agent가 경험해봐야만 알 수 있으며, 경험을 하더라도 구체적인 확률 분포를 정의하지는 못한다.
    
    $$ v_\pi(s) =\sum_{a\in\mathcal A} \pi(a|s) \left( \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_\pi(s')\right) $$
2. $V$를 기반으로는 Greedy policy를 만들 수 없다.
  
  greedy policy는 state-value function을 기반으로 가장 value가 높은 next-state에 도달하게 하는 action을 선택하는 방법으로 만들어진다.
  
  그런데 model-free환경에서는 어떤 action $a$을 수행했을 때 어떤 state $s'$에 도달하게 되는지는 실제로 Agent가 경험해봐야만 알 수 있으며, 경험을 하더라도 구체적인 확률 분포를 정의하지는 못한다.
  
  따라서 어떤 action을 했을 때 최종적으로 더 높은 value를 갖는 state에 도달할 확률이 더 높은 action을 선택하는 greedy policy를 정의할 수 없다.
*Example of Greedy Action Selection
- problem : 2개의 문이 존재하고 각각의 문을 선택할 때마다 reward를 받게 되며, 문을 선택한 뒤에는 그 방으로 들어간다. (model-free)
  - action : 왼쪽 문을 연다, 오른쪽 문을 연다
  - state : left, right
  - episode
    1. 왼쪽 문을 열고 reward 0을 받은 뒤 왼쪽 방에 들어갔다. → $V(\text{left}) = 0$
    2. 오른쪽 문을 열고 reward 1을 받은 뒤 오른쪽 방에 들어갔다. → $V(\text{right}) = 1$
    3. 더 value가 높은 state인 right에 도달하기 위해 오른쪽 문을 열고 reward 3을 받은 뒤 오른쪽 방에 들어갔다. → $V(\text{right}) = (1+3)/2 =2$
    4. 더 value가 높은 state인 right에 도달하기 위해 오른쪽 문을 열고 reward 2을 받은 뒤 오른쪽 방에 들어갔다. → $V(\text{right}) = (1+3+2)/3 =2$
      
      $\vdots$

 - $Q$.  오른쪽 문을 여는 행동을 선택하는 것이 과연 최적의 행동이라고 확신할 수 있는가?
   $A$. 왼쪽 문을 여는 행동을 딱 한번 수행하는 것으로는 완전히 파악할 수가 없다. (e.g. 왼쪽 문을 다시 열었더니 reward $+100$이 주어질수도 있음)

1.2 model-free에서 Policy improvement

MDP를 모를 때 발생하는 문제점의 해결방안

policy evaluation 단계 즉 prediction 문제는 model-free prediction문제를 해결하는 방법론인 MC, TD를 적용하여 평가할 수 있다.

policy improvement 단계

더 나은 action을 평가하는 기준으로 state-value $v(s)$ 대신에 action-value $q(s,a)$를 이용한다.

exploration을 고려하기 위하여 $\epsilon$-greedy 방법을 이용한다.

Greedy policy improvement
- MDP를 알아야, $V(s)$에 대하여 greedy policy improvement를 할 수 있다.
  
  $=$model-free일 때는 할 수 없다!
  
  $$ \pi'(s) = \argmax_{a\in \mathcal A}\left( \mathcal R^a_s + \gamma \sum_{s'\in \mathcal S}\mathcal P^a_{ss'}V(s')\right) $$
- model-free일 때는 $Q(s,a)$에 대하여 greedy하게 action을 선택하는 방법으로서 greedy policy improvement를 수행할 수 있다.

    $$
    \pi'(s) = \argmax_{a\in \mathcal A} Q(s,a)
    $$

$\epsilon$-greedy Exploration
- Exploration이 고려되어야하는 이유
  
  model-based와 달리 model-free환경에서는 실제로 Agent가 action을 선택하고 state사이를 이동하면서 환경에 대한 정보를 배우게 된다. 그런데 학습의 초기 단계에서부터 greedy action만을 선택한다면 Agent가 다양한 state를 방문하지 못하고 이미 방문한 state만 계속 방문하게 될 수 있다.
- 각 action이 non-zero probability를 가질 때, ($n(\mathcal A) = m$)
  - $1-\epsilon$의 probability만큼 greedy action을 선택한다. → policy가 계속 emprovement함을 보장한다.
  - $\epsilon$의 probability만큼 random action을 선택한다. → agent가 모든 state를 방문할 수 있음을 보장한다.
    
    $$ \pi(a|s) = \begin{cases} \epsilon /m +1 - \epsilon & \text{if }a^* = \argmax_{a\in \mathcal A} Q(s,a)\ \epsilon /m & \text{otherwise}\end{cases} $$
- (Theorem) $\epsilon$-greedy policy improvement
  
  For any $\epsilon$-greedy policy $\pi$, the $\epsilon$-greedy policy $\pi'$ with respect to $q_\pi$ is an improvement
  
  $$ v_{\pi'} (s) \ge v_\pi(s) $$

  1. state $s$에서의 action은 $\pi'$을 따라 선택하고 이후에는 $\pi$를 따라 시행했을 때의 action-value $q_\pi(s, \pi'(s))$를 bellman equation으로 표현한 것 
  2. $\pi'(a|s)$를 epsilon-greedy형태로 표현한 것 

        가능한 모든 action에 대하여 greedy action에 대해서는 $\epsilon/m+(1-\epsilon)$을 곱해주고 그렇지 않은 경우 그냥 $\epsilon/m$만을 곱해주었다. *(probability $\times$ value)

    3. geedy action에 대한 value는 다른 어떤 action-value보다도 큰 값이기 때문에 다른 action들에 대한 weighted-sum보다도 큰 값을 가진다.

        **weight는 4번째 식으로 정리하기 위해 곱해준 임의의 값*

    4. 해당 수식은 $v_\pi(s)$로 표현된다. (action-value간의 관계)

      → 1-step에 대해서 더 좋음을 보이면 결국 policy improvement theorem에 의해 $v_{\pi'}(s) \ge v_\pi(s)$임을 보일 수 있다. 


    $$
    q_\pi(s, \pi'(s)) = \sum_{a\in \mathcal A}\pi'(a|s) q_\pi(s,a)
    $$
    $$
    =\frac{\epsilon}{m}\sum_{a\in \mathcal A}q_\pi(s,a) + (1-\epsilon)\max_{a\in \mathcal A}q_\pi(s,a)
    $$
    $$
    \ge \frac{\epsilon}{m}\sum_{a\in \mathcal A}q_\pi(s,a) + (1-\epsilon)\sum_{a\in \mathcal A}\frac{\pi(a|s) - \epsilon/m}{1-\epsilon}q_\pi(s,a)
    $$
    $$
    =\sum_{a\in \mathcal A}\pi(a|s) q_\pi(s,a) = v_\pi(s)
    $$

1.3 on-policy와 off-policy

On-policy Learning
- Learn on the job
- 학습시키려는 policy와 실제 environment에서 Agent가 경험을 쌓을 때 따르는 policy가 동일한 경우
Off-policy Learning
- Look over someone’s shoulder
- 학습시키려는 policy와 실제 environment에서 Agent가 경험을 쌓을 때 따르는 policy가 다른경우

2. On-Policy Monte-Carlo Control

2.1 Monte-Carlo Control

for Every episode :

Policy evaluation : Monte-Carlo policy evaluation, $Q \approx q_\pi$
Policy improvement : $\epsilon$-greedy policy improvement

*효율적인 갱신방법 : policy evaluation을 수행할 때, $q_\pi$에 수렴할 때까지 진행하지 않고 early-stop한다.

→ Agnet가 경험한 하나의 episode에 대한 정보를 가지고 바로 더 나은 pocliy로 갱신

2.2 GLIE property

Definition of Greedy in the Limit with Infinite Exploration : GLIE
Greedy in the Limit with Infinite Exploration under the following conditions :
- All state-action pairs are explored infinitely many times,
  
  $$ \lim_{k \rightarrow \infin} N_k(s,a) = \infin $$
- The policy converges on a greedy policy,
  
  $\epsilon$-greedy를 이용한다면 optimal Q-value를 가지고 있더라도 $\epsilon$이라는 확률만큼은 최적이 아닌 랜덤한 action을 수행하기 때문에, 결국 최적의 policy를 찾기 위해서는 최종적으로 greedy policy에 수렴해야한다.
  
  $$ \lim_{k \rightarrow \infin} \pi_k(a|s) = \bold 1(a=\argmax_{a' \in \mathcal A} Q_k(s,a')) $$
⇒ GLIE와 $\epsilon$-greedy : 예를 들어, $\epsilon$이 점차 $0$으로 수렴한다면($=\epsilon_k = 1/k$) GLIE의 조건을 만족시킬 수 있다.

GLIE Monte-Carol Control

$\pi$를 따라 수행한 $k$번째 episode에서, ${S_1, A_1, R_2, \cdots, S_T} \sim \pi$

For each state $S_t$ and action $A_t$ in the episode, (in Evaluation) *$N(S_t, A_t)$ : 수행 횟수

N(S_t, A_t) \leftarrow N(S_t, A_t) + 1

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} (G_t - Q(S_t, A_t)

Improve policy based on new action-value function (in Emplovement)

$$
```
\epsilon \leftarrow \frac{1}{k}
```
$$

$$
```
\pi \leftarrow \epsilon\text{-greedy}(Q)
```
$$

(Theorem) GLIE Monte-Carol Control의 수렴성

GLIE Monte-Carlo control converges to the optimal action-value function,

$$ Q(s,a) → q_*(s,a) $$

2.3 MC vs. TD Control

TD의 장점
- MC에 비하여 Lower variance
- Online Update
- Incomplete sequence에도 적용가능하다.
TD를 MC대신에 control loop에 적용하자!
- apply TD to $Q(S,A)$
- $\epsilon$-greedy policy improvement
- Update every time-step

3. On-Policy Temporal-Difference Learning

3.1 SARSA

SARSA: state $S$에서 action $A$를 수행하여 reward $R$을 받고 next state $S'$에 도달한 뒤, 다시 action $A'$를 수행하는 과정
SARSA를 이용한 Action-Value function Update
- TD Target : $R + \gamma Q(S', A')$
- TD error : $\delta = R+\gamma Q(S', A') - Q(S,A)$
$$ Q(S,A) \leftarrow Q(S,A) + \alpha (R+\gamma Q(S', A') - Q(S,A)) $$
for Every time-step :
- Policy evaluation : SARSA, $Q \approx q_\pi$
- Policy improvement : $\epsilon$-greedy policy improvement

3.2 SARSA Algorithm

SARSA 알고리즘 설명
1. 초기에는 랜덤한 값들로 Q-table을 초기화한다.
2. $Q$에 대한 $\epsilon$-greedy방법을 이용하여 state $S$에서의 action $A$를 고른다.
3. action $A$를 Agent가 시행하고, 그 결과로 받게되는 reward $R$과 도달한 next-state $S'$에 대한 정보를 받는다.
4. $Q$에 대한 $\epsilon$-greedy방법을 이용하여 이동한 state $S'$에서의 action $A'$를 선택한다.
5. next state-action pair에 대한 Q-value를 이용하여 current Q-value를 TD방법으로 업데이트한다.
  
  $$ Q(S,A) \leftarrow Q(S,A) + \alpha (R+\gamma Q(S', A') - Q(S,A)) $$
6. current state, action에 $S'$, $A'$를 대입한다.
  
  $\vdots$

3.3 Convergence of SARSA

(Theorem) SARSA의 수렴성
SARSA converges to the optimal action-value function $Q(s,a) → q_(s,a)$, *under the following conditions :
- GLIE sequence of policies $\pi_t(a|s)$
- Robbins-Monro sequence of step-sizes $\alpha_t$
  
  : step size는 충분히 커야하지만, 수렴할 정도로 작아야한다.
  
  $$ \sum^\infin_{t=1} \alpha_t = \infin,\ \ \ \sum^\infin_{t=1} \alpha_t^2 < \infin $$

3.4 n-step SARSA(𝝺)

n-step SARSA($\lambda$)
- $n=1,2,\cdots, \infin$일 때의 Q-return
  
  $n$만큼의 실제 reward와, $t+n$번째 step에서의 추정 value function의 합으로 표현한다.
  - $n=1$ : $q_t^{(1)} = R_{t+1} + \gamma Q(S_{t+1})$ [SARSA]
  - $n=2$ : $q_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma ^2Q(S_{t+2})$
```
$\vdots$
```
  - $n=\infin$ : $q_t^{(\infin)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-1}R_T$ [MC]
- n-step Q-return의 define
  
  $$
```
q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n Q(S_{t+n})
```
  $$
  - n-step SARSA learning
    - n-step TD target : $q^{(n)}_t$
    - n-step TD error : $\delta_t = q^{(n)}_t - Q(S_t, A_t)$ ; target과 이전 예측 값의 차이
      
      $$ Q(S_t, A_t) \leftarrow Q(S_t, A_t)+\alpha(q_t^{(n)} - Q(S_t, A_t)) $$
Forward View SARSA($\lambda$)
- $q^\lambda$-return : SARSA부터 MC까지 진행했을 때의 모든 return의 평균
  - 각 n-step return $q_t^{(n)}$에 대하여 $(1-\lambda)\lambda^{(n-1)}$ weight를 적용하여 계산한다.
  - $n$이 커질수록 $\lambda$가 계속해서 곱해지게 되므로 더 작은 가중치를 가지게 된다.
    
    $$ q_t^\lambda = (1-\lambda)\sum^\infin_{n=1}\lambda^{n-1} q_t^{(n)} $$
- Forward-view SARSA($\lambda$) Update
  
  $$ Q(S_t, A_t) \leftarrow Q(S_t, A_t)+\alpha(q_t^{\lambda} - Q(S_t, A_t)) $$

Backward View SARSA($\lambda$)
- 아이디어
  - TD($\lambda$)에서 사용한 것처럼 SARSA도 eligibility traces를 적용할 수 있다.
  - 단, SARSA는 Q-function에 대해 TD를 적용하므로 각각의 state-action pair에 대해 대응되는 하나의 eligibility trace를 가진다.
- eligibility trace
  - init : $E_0(s, a) = 0$
  - time-step $t$에서 어떤 state $s$에서 어떤 action $a$를 수행하면, $1$을 더해주고 방문하지 않았을 때는 $t-1$에서의 값에다가 $\gamma\in (0,1)$를 곱해줘서 값을 감소시킨다.
    
    $$ E_t(s,a) = \gamma\lambda E_{t-1}(s,a)+\bold 1(S_t=s, A_t = a) $$
- Backward-view SARSA($\lambda$) Update
  
  $$ \delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) $$

$$
Q(s, a) \leftarrow Q(s)+\alpha \delta_tE_t(s, a)
$$

SARSA($\lambda$)의 효율성 (Gridworld Example)
- one-step SARSA에서는 reward를 받는 순간, 그 state에만 갱신이 된다.
- 그러나 SARSA($\lambda$) *$\lambda \approx 1$는 reward를 받는 순간, 그 state까지 오기까지 거쳤던 모든 state, action에 대해 약간이나마 그 reward가 전파된다!

3.5 SARSA(𝝺) Algorithm

SARSA($\lambda$) 알고리즘 설명
1. 초기에는 랜덤한 값들로 Q-table을 초기화한다.
2. $Q$에 대한 $\epsilon$-greedy방법을 이용하여 state $S$에서의 action $A$를 고른다.
3. action $A$를 Agent가 시행하고, 그 결과로 받게되는 reward $R$과 도달한 next-state $S'$에 대한 정보를 받는다.
4. $Q$에 대한 $\epsilon$-greedy방법을 이용하여 이동한 state $S'$에서의 action $A'$를 선택한다.
5. next state-action pair에 대한 Q-value를 이용하여 current Q-value와의 차이; TD error를 계산한다.
  
  $$ \delta \leftarrow R+\gamma Q(S', A') - Q(S,A) $$
6. current state-action pair에 대한 eligibility; 방문횟수를 1 더해준다.
  
  $$ E(S,A) = E(S,A)+ 1 $$
7. 모든 $s, a$에 대하여 eligibility를 고려한 만큼의 TD-error값을 더하여 Q-value를 갱신하고, 다른 실제로 방문되지 않은 state-action pair에 대해 eligibility를 감소시키는 과정을 반복한다.
  
  (=Q-table 전체를 업데이트 한다.)
  
  $$ Q(s,a) \leftarrow Q(s,a) + \alpha \delta E(s,a) $$
  
  $$ E(s,a) \leftarrow \gamma \lambda E(s,a) $$
8. current state, action에 $S'$, $A'$를 대입한다.
  
  $\vdots$

4. Off-Policy Learning

4.1 off-policy learning

off-policy란?

target policy $\pi$를 따랐을 때의 value를 계산하거나, policy를 개선하고 싶을 때 target과 다른 behavior policy $\mu$를 따랐을 때의 경험적 정보를 활용하는 방법
- target policy $\pi(a|s)$ : compute $v_\pi(s)$ or $q_\pi(s,a)$
- behavior policy $\mu(a|s)$ : ${S_1, A_1, R_2, \cdots, S_T} \sim \mu$
  
  → 실제로 action을 sampling 할 때 사용하는 policy

off-policy의 장점
- 사람이나 다른 agent가 수행한 결과를 보고 나의 target policy를 emprovement 할 수 있다.
- emprovement policy에 대해 다시 iterative를 수행할 때, 이미 과거에 했던 경험을 재사용할 수 있다.
  
  (=behavior policy는 update되지 않았으므로)
- behavior policy가 exploration하는 경험을 바탕으로 optimal policy를 학습할 수 있다.
  
  *trade-off에서 탈출!
- 하나의 behavior policy의 경험을 바탕으로 여러개의 policy들을 학습시킬 수 있다.

4.2 Importance Sampling for off-policy

Importance Sampling
- notation
  - $X$ : 확률분포 $P$를 따라 sampling되는 확률변수
  - $Q$ : $P$와는 다른 어떤 확률분포
  - $f(\cdot)$ : input에 대한 어떤 function
- proof
  1. $P$를 따라 samping된 $X$에 대한 $f(X)$의 Expectation은 expectation의 definition에 의해 probability $\times$ value의 합으로 표현될 수 있다.
  2. 위 수식을 $Q$에 대한 probability로 나타내기 위하여 $Q(X)$를 분자 분모에 동일하게 곱해준다.
  3. 위 수식은 이제 $(\text{probability} = Q(X)) \times (\text{value} = (P(X)/Q(X)) \cdot f(X))$의 형태로 해석할 수 있고, 이는 $Q$를 따라 samping된 $X$에 대한 $(P(X)/Q(X)) \cdot f(X)$의 expectation으로 나타낼 수 있다!

> 💡  두 **확률분포의 비율**만 곱해주면 어떤 확률 분포를 기반으로 구한 값에 대한 기댓값을 다른 확률 분포를 기반으로 구했을 때에 대한 기댓값으로 표현할 수 있다!


$$
\mathbb E_{X \sim P}[f(X)] = \sum P(X)f(X)
$$

$$
=\sum Q(X) \frac{P(X)}{Q(X)}f(X)
$$

$$
=\mathbb E_{X\sim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]
$$

Importance Sampling for Off-policy MC
- $G_t$를 얻을 때까지 수행한 각각이 action이 선택될 확률의 비을 계속 곱해준다.
- return
  
  $$
```
G_t^{\pi/\mu}= \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)} \frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})} \cdots \frac{\pi(A_T|S_T)}{\mu(A_T|S_T)} G_t
```
  $$
- Update
  
  $$
```
V(S_t) \leftarrow V(S_t) + \alpha\left(G_t^{\pi/\mu} - V(S_t)\right)
```
  $$
- 그러나 MC는 전체 episode가 끝난 다음에 $G_t$를 받아 계산하기 때문에, 끝날때까지 수행한 action의 수가 커지면 커질수록 $G_t$의 앞에 곱해지는 ratio가 너무 많아지기 때문에 실제로 이 방법을 사용해서 계산할 수는 없다. (ratio들의 곱에 대한 variance가 너무 큼)
  
  → 그렇다면 1-step해서도 수행가능한 TD는?

Importance Sampling for Off-policy TD

TD의 경우에는 앞에 곱해지는 term이 훨씬 적기 때문에 Importance sampling을 이용하여 off-policy method로 학습할 수 있다.

$$ V(S_t) \leftarrow V(S_t) + \alpha\left(\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}(R_{t+1} + \gamma V(S_{t+1})) - V(S_t)\right) $$

4.3 Q-Learning

Q-Learning의 특징
- No importance sampling required !
- Agent가 실행할 실제 next-action은 behaviour policy를 따라 선택된다. $A_{t+1} \sim \mu(\cdot |S_t)$

그러나 Q-function을 update할 때는 target policy를 따라 선택된 action $A'$에 대하여 계산한다! $A' \sim \pi(\cdot |S_t)$

 >  TD는 reward + **추측값**과의 차이를 이용하여 현재값을 update하는데, 추측값에서는 behavior policy를 따르지 않아도 상관없기 때문이다.

- *update (by Bellman Equation!)*

    $$
    Q(S_t, A_t)\leftarrow Q(S_t, A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, A') - Q(S_t, A_t))
    $$

off-policy control with Q-Learning
- (both) policy improvement
- 아이디어* : behavior policy와 target policy 둘다 점차 emprovement가 되지만, behavior policy는 여전히 exploration을 고려할 수 있도록 policy를 설정하고 싶다.
  - target policy : greedy
    
    $$
```
\pi(S_{t+1}) = \argmax_{a'}Q(S_{t+1}, a')
```
    $$
  - behavior policy : $\epsilon$-greedy
- Q-Learning target
  
  target policy를 이용하여 선택된 action A’를 greedy policy에 대한 수식으로 바꾸어 표현할 수 있다.
  
  $$ R_{t+1} + \gamma Q(S_{t+1}, A') $$ $$ =R_{t+1} + \gamma Q(S_{t+1}, \argmax_{a'}Q(S_{t+1}. a')) $$ $$ =R_{t+1}+\max_{a'}\gamma Q(S_{t+1}, a') $$
- Q-Learning Update
  
  $$ Q(S, A)\leftarrow Q(S, A) + \alpha\left( R + \gamma \max_{a'} Q(S', a') - Q(S, A)\right) $$
(Theorem) Q-learning Control의 수렴성

Q-learning control converges to the optimal action-value function,

$$ Q(s,a) → q_*(s,a) $$

4.4 Q-Learning Algorithm

Q-Learning 알고리즘 설명
1. 초기에는 랜덤한 값들로 Q-table을 초기화한다.
2. $Q$에 대한 $\epsilon$-greedy방법을 이용하여 state $S$에서의 action $A$를 고른다.
3. action $A$를 Agent가 시행하고, 그 결과로 받게되는 reward $R$과 도달한 next-state $S'$에 대한 정보를 받는다.
4. $Q$에 대한 greedy방법을 ***이용하여 state $S'$에서의 action $A'$를 *선택한다.
5. Q-Learning Update를 수행한다.
  
  $$ Q(S, A)\leftarrow Q(S, A) + \alpha\left( R + \gamma \max_{a} Q(S', a) - Q(S, A)\right) $$
6. current state, action에 $S'$만 대입한다.
  
  $\vdots$

Summary

Relationship Between DP and TD

(where $x\overset{\alpha}{\leftarrow} y \equiv x \leftarrow x + \alpha(y-x)$

Reference

[강화학습] Model Free Prediction

Mon, 30 Jan 2023 02:59:38 GMT

본 포스팅은 David Silver 교수님의 강화학습 강의와 그 강의를 정리한 팡요랩 강의를 바탕으로 정리한 것입니다.

환경을 알지 못하는 상황에서 던져진 Agent를 이용하여 어떻게 value function을 추정할 것인가?

1. Model-Free Prediction

1.1 Model-Free?

Environment의 MDP에 대한 정보를 알지 못하는 상황
MDP를 모른다?
- 내가 어떤 action을 했을 때 받는 reward $R_{t}$를 사전에 알지 못한다. → 직접 경험해봐야 알 수 있다.
- 내가 어떤 action을 했을 때 어떤 next-state로 transition할지를 결정하는 transition probability $\mathcal P^a_{ss'}$를 알지 못한다.
  - 직접 경험해봐야 어떤 next-state에 도달했는지를 알 수 있다.
  - 많이 경험하더라도 어떤 정확한 “확률 분포”를 알 수 없다.

1.2 Model-Free일 때 문제의 종류

prediction 문제 : MDP를 모를 때, value function을 구하는 과정
control 문제 : MDP를 모를 때, 최적의 optimal policy를 찾는 과정 → (next chapter)

2. Monte-Carlo Learning

2.1 Monte-Carlo Policy Evaluation

Mote-Carlo method?
- 실제로 구하기 어려운 값을 계산할 때, Agent의 “경험”을 기반으로 구해진 실제 값들을 이용하여 추정하는 방법
- (in prediction)
  
  prediction 문제에는 Agent가 따르는 “policy”가 정의되어있기 때문에 실제로 agent가 해당 policy를 따라서 environment를 경험하도록 한다. 이를 하나의 episode라고 한다.
  
  episode를 수행하면서 얻은 각각의 실제 return 값을 저장하고 평균을 구하면, value를 계산할 수 있다.
- → value function의 definition이 return의 expectation이기 때문!*
$$
```
  \text{value} = \text{mean Return}
```
$$
- 하나의 episode가 완전히 끝나야 return을 알 수 있기 때문에 모든 episode가 반드시 종료된다는 조건을 만족할 때만 적용할 수 있다는 단점을 가진다.
Policy Evaluation의 목적 : agent가 policy $\pi$를 따라 경험한 episode를 이용하여 $v_\pi$를 찾는 것
Monte-Carlo 방법의 적용
- return : total discounted reward
  
  $$ G_t = R_{t+1}+\gamma R_{t+2} + \cdots + \gamma^{T-1}R_T $$
- value function : expected return
  
  $$ v_\pi(s) = \mathbb E_\pi[G_t|S_t=s] $$

2.2 MC Update

가정 : Agent가 모든 state $s\in \mathcal S$를 방문해야한다.

why? $N(s) → \infin$에 근접해야하기 때문
First-visit MC Update : Agent가 해당 state에 처음 방문 했을 때만, 방문횟수를 증가시키고 return을 더한다.

To evaluate state $s$,
1. Increment counter
  
  $N(s) ← N(s) +1$
2. Increment total return
  
  $S(s) ← S(s) + G_t$
3. Mean return
  
  $$ V(s) = \frac{S(s)}{N(s)} $$
  
  ⇒ 큰 수의 법칙; law of large number에 따라 $N(s) → \infin$에 가까워질수록 $V(s) → v_\pi(s)$에 수렴한다.
Every-visit MC Update: Agent가 해당 state에 방문 할 때마다, 방문횟수를 증가시키고 return을 더한다.

To evaluate state $s$,
- for every time-step $t$ in each episode
  1. Increment counter
    
    $N(s) ← N(s) +1$
  2. Increment total return
    
    $S(s) ← S(s) + G_t$
- Mean return
  
  $$ V(s) = \frac{S(s)}{N(s)} $$
  
  ⇒ 큰 수의 법칙; law of large number에 따라 $N(s) → \infin$에 가까워질수록 $V(s) → v_\pi(s)$에 수렴한다.

2.3 Incremental Mean을 이용한 MC Update

*한번에 평균을 구하여 업데이트를 하는 것이 아니라 하나의 에피소드가 끝날때마다 조금씩 평균을 업데이트 하는 방법

Incremental Mean
- 점진적으로 평균을 구하는 방법
- mean $\mu_1, \mu_2$는 sequence $x_1, x_2, \cdots$가 구해짐에 따라 다음과 같이 점진적으로 증가시키면서 update할 수 있다.
  $$ \mu_k = \frac{1}{k}\sum^k_{j=1}x_j $$ $$ =\frac{1}{k}\left(x_k + \sum^{k-1}{j=1} x_j \right) $$ $$=\frac{1}{k}(x_k+(k-1)\mu{k-1}) $$ $$ =\mu_{k-1}+\frac{1}{k}(x_k - \mu_{k-1}) $$
MC Update
- Incremental Mean을 이용하면 $V(s)$를 episode하나가 끝난 뒤에 incrementally update할 수 있다.
- for each state $S_t$ with return $G_t$
  
  $$ N(S_t) \leftarrow N(S_t) +1 $$
  
  $$ V(S_t) \leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t - V(S_t)) $$

  → 실제값 $G_t$와 학습중인 value $V(S_t)$의 차이; error만큼 조금씩 업데이트 한다.


- $N(S_t)$를 사용하지 않는 경우
    - $1/N(S_t)$가 아닌, 어떤 고정된 상수 $\alpha$를 곱해서 업데이트 하는 방법
    - $1/N(S_t)$는 자주 방문할 수록 점점 작아지기 때문에 기존 방법은 최신 episode보다 과거의 episode에 대해 더 중요하게 가정했다면, 이 방법에서는 **과거의 episode를 forget하는 효과**를 보일 수 있다.
    - non-stationary problem문제\*에서는 이렇게 update하는 방법이 더 효과적일 수 있다.
    _*non-stationary problem_ : MDP가 일정하지 않고 조금씩 변화하는 문제

$$ V(S_t) \leftarrow V(S_t)+\alpha(G_t - V(S_t)) $$

3. Temporal-Difference Learning

3.1 Temporal-Difference Policy Evaluation

Temporal-Difference method의 아이디어
- Agent의 “경험”을 기반으로 추정하는 방법
- TD는 incomplete episode에서도 업데이트 할 수 있다.
- TD updates a guess towards a guess
  
  💡 1-step을 더 진행하면 1-step만큼의 실제정보(=reward)가 반영되기 때문에 더 정확한 value를 가지고 있을 것이다 !

Policy Evaluation의 목적 : agent가 policy $\pi$를 따라 경험한 episode를 이용하여 $v_\pi$를 찾는 것
Temporal-Difference 방법의 적용
- MC policy evaluation : value를 실제 return $G_t$과의 차이를 이용해 update
  
  $$ V(S_t) \leftarrow V(S_t)+\alpha(G_t - V(S_t)) $$

- **TD learning algotithm** : value를 **1-step을 더 진행**했을 때, **추정된** return $R_{t+1}+\gamma V(S_{t+1})$과의 **차이**을 이용하여 update
    - TD target : $R_{t+1} + \gamma V(S_{t+1})$
    - TD error : $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ ; target과 실제 값의 차이

    $$
    V(S_t) \leftarrow V(S_t)+\alpha(\red{R_{t+1} + \gamma V(S_{t+1})} - V(S_t))
    $$

3.2 n-step TD

TD를 적용할 때는 1-step만 진행하고 바로 update를 진행할 수도 있지만, 여러번의 step을 진행하고 나서 그 때의 값을 이용하여 update하는 방법을 사용할 수도 있다.

→ 이때 terminal state까지의 step을 경험한뒤에 update하는 방법은 MC와 동일하다!

n-step Return
- $n=1,2,\cdots, \infin$일 때의 return
  
  $n$만큼의 실제 reward와, $t+n$번째 step에서의 추정 value function의 합으로 표현한다.
  - $n=1$ : $G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})$ [TD]
  - $n=2$ : $G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma ^2V(S_{t+2})$ $\vdots$
    - $n=\infin$ : $G_t^{(\infin)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-1}R_T$ [MC]

n-step return의 define $$

G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n})

n-step TD learning
- n-step TD target : $G^{(n)}_t$
- n-step TD error : $\delta_t = G^{(n)}_t - V(S_t)$ ; target과 실제 값의 차이
  
  $$ V(S_t) \leftarrow V(S_t)+\alpha(G_t^{(n)} - V(S_t)) $$

🍎 TD(0)과 MC사이에는 둘의 효과를 극대화할 수 있는 가장 적절한 sweet-spot이 존재한다.

3.3 Forward View of TD(𝝺)*

Averaging n-Step Returns
- 여러가지의 n-step을 따라 수행해서 구한 return이 있을 때, 각각의 return을 평균한 값을 사용하여 학습해도 된다! (combine)
- e.g. 2-step and 4-step return의 average
  
  $$ \frac{1}{2}G^{(2)} + \frac{1}{2}G^{(4)} $$
- $\lambda$-return : TD(0)부터 MC까지 진행했을 때의 모든 return의 평균 $G^\lambda_t$
  - 각 n-step return $G_t^{(n)}$에 대하여 $(1-\lambda)\lambda^{(n-1)}$ weight를 적용하여 계산한다.
    - $n$이 커질수록 $\lambda$가 계속해서 곱해지게 되므로 더 작은 가중치를 가지게 된다.
    $$ G_t^\lambda = (1-\lambda)\sum^\infin_{n=1}\lambda^{n-1} G_t^{(n)} $$

- *TD($\lambda$) weighting function*

![](https://velog.velcdn.com/images/webb-c/post/8908ed44-5894-439d-a274-9910670ba63d/image.png)

Forward-view TD($\lambda$)
- 작은 step만이 아닌, 미래를 보고 update한다.
- MC에서 사용하는 return도 사용하기 때문에 episode가 끝나야 계산할 수 있다.

$$
V(S_t) \leftarrow V(S_t)+\alpha(G_t^{\lambda} - V(S_t))
$$

3.4 Backward View of TD(𝝺)*

Eligibility trace $E_t(s)$

어떤 사건이 일어났을 때, 그 사건에 대한 책임이 가장 큰 요소를 더 많이 update하는 방법
- $Q$. 누가 책임이 가장 큰지는 어떻게 판단하는가?
- 아이디어 : heuristic을 이용하자!
  - Frequency heuristic : 가장 자주 일어난 state의 책임이 크다.
  - Recency heuristic : 가장 최근에 일어난 state의 책임이 크다.
- Eligibility trace
  - init : $E_0(s) = 0$
  - time-step $t$에서 어떤 state s에 방문하면, $1$을 더해주고 방문하지 않았을 때는 $t-1$에서의 값에다가 $\gamma\in (0,1)$를 곱해줘서 값을 감소시킨다.
    
    $$
```
E_t(s) = \gamma\lambda E_{t-1}(s)+\bold 1(S_t=s) 
```
    $$
  - 시간에 따른 eligibility trace의 변화

TD-error

$$ \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) $$
Backward-view TD($\lambda$)
- TD(0)와 TD($\lambda$)의 장점을 모두 가진다.
  - online(매 step)마다 update할 수 있다.
  - episode가 끝나지 않는 환경에서도 사용할 수 있다.
- $t$일때의 TD-error에 대해 그 상황에서의 eligibility trace값을 곱한만큼 update한다. → 수학적으로 TD($\lambda$)와 동일함

$$
V(s) \leftarrow V(s)+\alpha \delta_tE_t(s)
$$

3.5 Forward and Baackward Equivalance*

TD($\lambda$) and TD(0)
- $\lambda=0$일 때, 오직 current state만이 update된다.
  - eligibility trace
  - $E_t(s) = \bold 1(S_t=s)$
- TD(0) update
  
  $$
```
V(S_t) \leftarrow V(S_t)+\alpha \delta_t
```
  $$
TD($\lambda$) and TD(1) and MC
- $\lambda=1$일 때, episode의 끝까지 고려하게된다.
- Theorem
  
  The sum of offline updates is identical for forward-view and backward-view TD($\lambda$)
  
  $$ \sum^T_{t=1} \alpha\delta_tE_t(s) = \sum^T_{t=1} \alpha \left(G_t^\lambda - V(S_t)\right) \bold 1 (S_t=s) $$
- eligibility trace
  
  $$ E_t(s) = \gamma\lambda E_{t-1}(s)+\bold 1(S_t=s) $$
  
  $$ =\begin{cases} 0 & \text{if }t
- update : online
  
  $$ \sum^{T-1}{t=1} \alpha\delta_tE_t(s) = \alpha\sum^{T-1}{t=k}\lambda^{t-k}\delta_t =\alpha \left(G_t - V(S_k)\right) $$
- total error
  
  $$ \delta_k + \gamma\delta_{k+1}+ \gamma^2\delta_{k+2} + \cdots+ \gamma^{T-1-k}\delta_{T-1} $$
- MC error의 표현
  
  $\delta_k + \gamma\delta_{k+1}+ \gamma^2\delta_{k+2} + \cdots+ \gamma^{T-1-k}\delta_{T-1}$
  
  $=R_{t+1} + \gamma V(S_{t+1})-V(S_t)$
  
  $+ \gamma R_{t+2} + \gamma^2 V(S_{t+2}) - \gamma V(S_{t+1})$
  
  $+ \gamma^2 R_{t+3} + \gamma^3 V(S_{t+3}) - \gamma^2 V(S_{t+2})$
  
  $\ \ \ \vdots$
  
  $+ \gamma^{T-1-t} R_{T} + \gamma^{T-t} V(S_{T}) - \gamma^{T-1-t} V(S_{T-1})$
  
  $=R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-1-t} R_T - V(S_t)$
  
  $=G_t - V(S_t)$

Forward and Backwards TD($\lambda$)
- For general $\lambda$, TD errors also telescope to $\lambda$-error, $G_t^\lambda - V(S_t)$
  
  $G_t^\lambda - V(S_t)$
  
  $= -V(S_t) + (1-\lambda)\lambda^0 (R_{t+1} + \gamma V(S_{t+1}))$

 $+ \ (1-\lambda)\lambda^1 (R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2}))$

 $+ \ (1-\lambda)\lambda^2 (R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3}  + \gamma^3 V(S_{t+3}))$

 $+\ \cdots$

 $= -V(S_t) + (\gamma\lambda)^0 (R_{t+1} + \gamma V(S_{t+1})-\gamma\lambda V(S_{t+1}))$

 $+\ (\gamma\lambda)^1 (R_{t+2} + \gamma V(S_{t+2})-\gamma\lambda V(S_{t+2}))$

 $+\ (\gamma\lambda)^2 (R_{t+3} + \gamma V(S_{t+3})-\gamma\lambda V(S_{t+3}))$

 $+\ \cdots$

 $= (\gamma\lambda)^0 (R_{t+1} + \gamma V(S_{t+1}) - V(S_t))$

 $+\ (\gamma\lambda)^1 (R_{t+2} + \gamma V(S_{t+2})-V(S_{t+1}))$

 $+\ (\gamma\lambda)^2 (R_{t+3} + \gamma V(S_{t+3})-V(S_{t+2}))$

 $+\ \cdots$

 $$
    =\delta_t + \gamma\lambda\delta_{t+1} + (\gamma\lambda)^2\delta_{t+2} + \cdots
 $$

TD 총정리*

4. MC vs. TD

4.1 Non Episodic MDP

TD는 final outcome이 산출되기 전에 학습할 수 있다.
- TD는 각각의 모든 step에서 online으로 학습이 가능하다.
- MC는 반드시 episode의 끝에 도달할 때까지 기다리고 return을 알게되면 그때 학습한다.
TD는 final outcome 없이도 학습할 수 있다.
- TD는 non-teriminatinh 환경에서도 적용할 수 있다.
- MC는 오직 episodic(=terminating)한 환경에서만 적용할 수 있다.

4.2 Bias / Variance trade-off

bias와 variance
- bias
  - return $G_t$는 $v_\pi(S_t)$에 대한 unbiased estimate이다.
    
    즉, value function의 정의에 따라 $G_t$를 계속 sampling하면 결국 $v_\pi(S_t)$에 수렴할 것이다.
    - true TD target $R_{t+1}+\gamma v_\pi(S_{t+1})$은 $v_\pi(S_t)$에 대한 unbiased estimate이지만, 우리는 $v_\pi$의 실제 값을 알지 못한 상태에서 계산하기 때문에 TD target은 $R_{t+1} + \gamma V(S_{t+1})$은 biased estimate이다.
    추정값을 이용하여 갱신하기 때문에 발생하는 biase가 존재하고 따라서 수없이 많이 반복하더라도 TD target이 실제 $v_\pi(S_t)$에 정확히 수렴하리라는 보장은 가질 수 없다.
- variance
  - TD target은 반드시 return보다 더 작은 variance를 가진다.
  - why?
    Return은 수많은 랜덤한 action, transition, reward를 이용하여 계산되지만 TD target은 딱 한번의 랜덤한 action, transition, reward에 의해 계산되기 때문이다.
    → 1-step에서 발생할 수 있는 랜덤성은 episode가 끝날 때까지 발생할 수 있는 랜덤성보다 훨씬 작다.
  - variance가 클수록 그 확률분포에서 어떤 것을 sampling 했을 때 뽑힌 sample들에대한 편차가 클 수 있다. → 정확성이 떨어진다.

MC는 high variance, zero bias
- (function approximation$^{[1]}$에서도) 수렴성이 좋다.
- initial value에 그다지 민감하지 않다.
- 이해하고 사용하기 간단하다.
TD는 low variance, some bias
- MC보다 대부분 더 효율적이다.
- TD(0)은 $v_\pi(s)$로 수렴하긴 하지만, function approzimation에서는 수렴함이 보장되지 않는다.
- MC에 비하여 더 initial value에 민감하다.

4.3 Batch MC and TD

MC와 TD의 수렴성
- $\infin$번 experience할 수 있다면 $V(s) → v_\pi(s)$로 반드시 수렴한다는 것은 알고 있다.
- 그런데 만약 k개의 제한된 episode만을 가지고 있을 때, MC와 TD는 수렴하는가?
  
  $s^1_1, a^1_1, r^1_2, \cdots, s^1_{T_1}$
  
  $\vdots$
  
  $s^k_1, a^k_1, r^k_2, \cdots, s^k_{T_k}$
AB Example
- problem
  - state : A, B
  - 아래의 8개의 episode에 대한 정보만을 알고 있을 때 $V(A), V(B)$의 값은?
- MC와 TD에서의 value
  - MC : $V(A)= 0$ 전체 episode에서 A에 도달한 경우는 1번인데 그때의 return이 0이므로
  - TD : $V(A) = 0.75$ $V(A)$는 reward $0+V(B)$, 즉 V(B)의 value를 이용하여 갱신되기 때문이다.

certainty Equivalence
- MC : minimum MSE
  
  $$ \sum^K_{k=1}\sum^{T_k}_{t=1} (G_t^k - V(s^k_t))^2 $$
- TD(0) : max likelihood Markov model
  
  $$ \hat{\mathcal P}^a_{s, s'} = \frac{1}{N(s,a)}\sum^K_{k=1} \sum^{T_k}{t=1} \bold 1(s^k_t, a^k_t, s^k{t+1} = s, a, s') $$
  
  $$ \hat{\mathcal R}^a_{s} = \frac{1}{N(s,a)}\sum^K_{k=1} \sum^{T_k}_{t=1} \bold 1(s^k_t, a^k_t = s, a)r^k_t $$
  
  → 한정된 개수의 episode를 이용할 때는 MC와 TD를 사용하여 계산했을 때 value에 차이가 발생한다.

*따라서,*  

- TD는 Markov property를 사용하여 value를 추측한다. → Markov 환경에서 더 효율적이다.
- MC는 Markov property를 사용하지 않고 value를 추측한다. → non-Markov 환경에서 더 효율적이다.

4.4 More difference

Backup 방법의 차이
- Monte-Carlo Backup : DFS
  
  $$ V(S_t) \leftarrow V(S_t) + \alpha(G_t- V(S_t)) $$

- Temporal-Difference Backup : (1-step) <**Bootstraping**>

    $$
    V(S_t) \leftarrow V(S_t) + \alpha(R_{t+1}+\gamma V(S_{t+1})- V(S_t))
    $$

    ![](https://velog.velcdn.com/images/webb-c/post/f46dc542-6d7e-4812-8480-52751c64012c/image.png)


- Dynamic Programming Backup : BFS

    $$
    V(S_t) \leftarrow V(S_t) + \alpha(R_{t+1}+\gamma V(S_{t+1})- V(S_t))
    $$

    ![](https://velog.velcdn.com/images/webb-c/post/1e0867ac-6b3f-4e6d-82b5-473c2a0a1b7c/image.png)

Bootstrapping & Sampling
- Bootstrapping : update involves an estimate
  - DP : bootstraps
  - MC : does not bootstraps
  - TD : bootstraps
- Sampling : update samples an expectation ****
  - DP : does not sample (sampling을 하지않고 가능한 모든 action에 대한 값을 이용한다.
  - MC : samples
  - TD : samples

(bootstrapping & sampling 관점에서) RL method의 총정리*

4.5 with Example

Random Walk Example

problem : policy를 평가
- state : A, B, C, D, E
- teminal state : ▪️
- policy : left / right 랜덤하게 움직인다.

MC vs. TD (with. $\alpha$ 값에 따른 변화)

→ error는 실제 value function과의 RMS로 표현

Reference

[강화학습] Planning by Dynamic Programming

Sat, 28 Jan 2023 14:56:33 GMT

본 포스팅은 David Silver 교수님의 강화학습 강의와 그 강의를 정리한 팡요랩 강의를 바탕으로 정리한 것입니다.

Planning이란?

→ Environment; MDP를 알고 있을 때 더 나은 policy를 찾아나가는 과정

1. Dynamic Programming

1.1 Dynamic Programming 이란?

⚙ Dynamic Programming

Dynamic : sequential or temporal component to the problem
Programming : optimising a “program”

하나의 큰 문제를 바로 해결하기 힘들 때, 여러개의 작은 부분 문제들로로 문제를 나누고 부분 문제들의 해를 모두 구한 뒤에 그 해를 이용해서 더 큰 크기의 부분 문제를 해결하는 과정을 거쳐 문제를 해결하는 하나의 방법론

1.2 Dynamic Programming의 요구조건

Optimal substructure : 하나의 큰 문제에 대한 solution은 여러개의 작은 부분문제들의 solution으로 분할 할 수 있어야 한다.
Overlapping subproblems : 어떤 부분문제의 해는 상위의 부분문제를 해결하기 위하여 여러번 사용될 수 있다. 따라서 보통 부분문제의 해들을 저장해두고 가져와서 이용한다.
⇒ Markov decision processes satisfy both properties!*
- Bellman equation은 재귀적으로 표현된다.
- value function이 계산한 value는 저장해두었다가 Policy를 평가/갱신하기 위해 사용된다.

1.3 Planning by DP

DP를 이용하여 planning을 수행할 때는, MDP에 대한 모든 정보$^{[1]}$를 알고있다고 가정한다. [1] MDP의 정보
1. state transition probability
2. reward
강화학습 문제의 종류에 따른 표현
- prediction
  MDP와 policy가 주어졌을 때, 그 policy$^{[2]}$를 따라 Agent가 수행했을 때의 value function을 계산하는 문제
  - input : MDP $<\mathcal S, \mathcal A, \mathcal P, \mathcal R, \gamma>,\ \pi$ (=or $<\mathcal S, \mathcal P^\pi, \mathcal R^\pi, \gamma>$)
    - output : value function $v_\pi$
  [2] 이때 주어지는 Policy는 optimal policy여야하는 조건같은건 가지고 있지 않는다.
- control
  MDP가 주어졌을 때, optimal value function, policy를 찾는 문제
  - input : MDP $<\mathcal S, \mathcal A, \mathcal P, \mathcal R, \gamma>$
  - output : optimal value function $v_$, optimal policy $\pi_$

2. Policy Evaluation

Policy가 고정되어있을 때, value-function을 게산하는 과정

2.1 Iterative Policy Evaluation

문제 정의
- problem : 주어진 어떤 policy $\pi$를 평가하는 것, 즉 policy를 따랐을 때의 value function $v_\pi(s)$를 찾는 것을 목적으로 한다. [prediction]
- solution : Bellman expectation equation을 이용하여 iterative한 방법을 적용한다.
  
  $v_{1;\ init} → v_2 → \cdots → v_\pi$
synchronous backup
1. each iteration k+1
  1. for all states $s \in \mathcal S$
    1. update $v_{k+1}(s)$ from $v_k (s')$
      
      → 전 단계 $k$에서의 value f를 이용하여 현재 단계 $k+1$에서의 value를 갱신한다.
      
      (where $s'$는 $s$에서 갈 수 있는 가능한 모든 state)
  → 이 과정을 반복하면 $v_\pi(s)$에 수렴하게 된다.

Bellman Expectation Equation
- $k+1$ 단계에서는 $k$단계에서보다 더 정확한 value 값을 가지게 하고 싶어한다.
- evaluate하는 state $s$에서 갈 수 있는 가능한 모든 state $s'$에서의 value를 사용하여 갱신해준다.
- next state의 value일수록 지금까지 policy를 따라 진행하면서 실제로 얻은 정확한 reward $r$의 값이 더 많이 존재하기 때문에 점점더 정확한 value를 가지게 된다.
- 따라서 가장 초기 init 상태일 때의 value function의 값은 모두 정확하지 않더라도 정확한 값인 “reward”가 고려되기 때문에 최종적으로 $v_\pi(s)$에 수렴할 수 있게 된다.

$$ v_{k+1}(s) = \sum_{a\in \mathcal A} \pi(a|s) \left( \mathcal R^a_s + \gamma \sum_{s'\in \mathcal S} \mathcal P^a_{ss'}v_k(s')\right) $$

$$ \bold v _{k+1} = \mathcal R^{\pi} + \gamma \mathcal P^\pi \bold v _k $$

2.2 Example with Gridword

*Gridworld for prediction
- MDP
  - 1~14는 nonterminal state이고, 왼쪽 위 또는 오른쪽 아래에 하나의 terminal state를 가진다.
  - $\gamma = 1$ (미래지향적)
  - terminal state에 도달하기 전까지 항상 $-1$의 reward를 받는다.

random policy

$\pi(n|\cdot)=\pi(s|\cdot)=\pi(w|\cdot)=\pi(e|\cdot)=0.25$

Iterative Policy Evaluation
- ex) $k=0$ 일 때 6번 state의 갱신과정
  
  $$ v_{1}(6) = \sum_{a\in \mathcal {n, s, w, e}} 0.25 \times \left( -1 + 1\times \sum_{s'\in \mathcal {2, 5, 7, 10}} \mathcal 1\times 0\right) = -1 $$

![](https://velog.velcdn.com/images/webb-c/post/cbef3f51-3e3c-455e-9d97-909eaea67219/image.png)

> 🤖 (이 예시에서는) 멍청한 policy를 기반으로 value function의 값을 계산하였는데, 계산된 value function에 대하여 value가 $\max$가 되게하는 action만 항상 **그리디하게** 선택하는 policy를 따랐더니 optimal policy가 되었다!

→ 더 나은 policy를 찾을 수 있다. **[policy 개선의 아이디어]**

3. Policy Iteration

Iterative한 방법을 사용하여 policy기반으로 최적의 policy를 찾는 과정

3.1 Policy 개선의 원리

Evaluate the policy (=policy evaluation)

$$ v_\pi(s) = \mathbb [R_{t+1} + \gamma R_{t+2} + \cdots | S_t = s] $$
Improve the policy

$$ \pi' = \text{greedy} (v_\pi) $$

⇒ Evaluate와 Improve를 반복해서 수행하면 점점 policy가 optimal policy $\pi*$에 수렴하게 된다!

3.2 Policy Iteration

Policy 개선 과정

초기 policy $\pi$를 평가 [evaluation]

계산된 value function에 대하여 greedy하게 선택하는 새로운 policy $\pi'$로 policy를 개선 [improvement]

개선된 policy $\pi'$를 다시 평가 [evaluation]

$\cdots$

3.3 proof of policy Improvement

$\text{Q}_1$. greedily하게 행동하는 새로운 policy는 항상 이전의 policy보다 개선되는가?
- 어떤 deterministic$^{[1]}$한 policy, $a = \pi(s)$가 있다고 하자.
  
  [1] 어떤 state에서 어떤 action을 할 지 명확하게 정의된 policy → 확률 분포가 아님
- greedily하게 행동하는 새로운 policy를 정의함으로서 우리는 policy를 improve시킬 수 있다
  
  $$ \pi'(s) = \arg\max_{a\in \mathcal A} q_{\pi} (s,a) $$
- one-step에 대한 policy improve 증명
  
  *notation
  
  $q_\pi(s, \pi(s))$ : $\pi$를 따라서 1-step을 수행하고 그 이후로도 계속 \pi를 따랐을 때의 action-value
  
  $q_\pi(s, \pi'(s))$ : $\pi'$를 따라서 1-step을 수행하고 그 이후에는 \pi를 따랐을 때의 action-value
  - $s$에서의 state-value는 $s$에서 policy에 의해 결정된 action $a = \pi(s)$을 수행했을 때의 action-value와 동일하다. (action-value function의 정의상 자명함)
  - policy가 결정한 action을 했을 때의 value는 value가 최대가 되도록하는 action을 했을 때의 value보다는 절대로 크지는 않을 것이다.
  - 그런데 greedily policy의 정의에 따라 이 값은 greedily policy에 의해 결정된 action $a= \pi'(s)$을 수행했을 때의 action-value와 동일하다.
    
    $$ q_{\pi} (s, \pi'(s)) = \max_{a\in\mathcal A} q_{\pi} (s,a) \ge q_{\pi} (s, \pi(s)) = v_\pi(s) $$
    
    ⇒ one-step이라도 $\pi'$를 따라 진행했을 때의 action-value가 기존 policy를 따랐을 때의 value보다 항상 같거나 크다.
- value function에 대한 증명
  - one-step일 때 증명한 것에 따라서 $v_\pi(s) ≤ q_\pi(s, \pi'(s))$이다. $-\ (1)$
  - Q-function의 정의에 의하여 아래와 같이 expectation 공식으로서 나타낼 수 있다.
    
    $$ v_\pi(s) \le q_\pi(s, \pi'(s)) = \mathbb E_{\pi'}[R_{t+1} + \gamma v_{\pi} (S_{t+1}) | S_t = s] $$
  - one-step일 때 증명한 내용 (1)을 다시 적용하면 아래와 같이 표현할 수 있다.
    
    $$ \le \mathbb E_{\pi'} [R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1}))|S_t=s] $$
  - Q-function에 대해 한번의 step을 더 진행하여 bellman equation처럼 재귀적으로 아래와 같이 표현할 수 있다.
    
    $$ \le \mathbb E_{\pi'} [R_{t+1} + \gamma R_{t+2}+\gamma^2 q_\pi(S_{t+2}, \pi'(S_{t+2}))|S_t=s] $$
  - 재귀적인 과정을 반복하면 결국 value-function에 정의에 의하여 $v_\pi'(s)$로 표현된다.
    
    $$
    
    \le \mathbb E_{\pi'} [R_{t+1} + \gamma R_{t+2}+\cdots |S_t=s] = v_{\pi'}(s) $$
    
    ⇒ 따라서 모든 state에서 $\pi'$를 따랐을 때의 value가 $\pi$를 따랐을 때의 value보다 높기 때문에 policy는 항상 improvement 된다는 것을 보일 수 있다.

$\text{Q}_2$. 개선된 policy는 최종적으로 optimal에 수렴하는가?
- 아래 등식이 성립하는 상황이라면 어떤 policy에 수렴했다고 말할 수 있다.
  
  $$ q_{\pi} (s, \pi'(s)) = \max_{a\in\mathcal A} q_{\pi} (s,a) = q_{\pi} (s, \pi(s)) = v_\pi(s) $$
- bellman optimality equation을 적용할 수 있는 상황이다.
  - $v_\pi(s) = v_*(s)$ for all $s \in \mathcal S$
  - 따라서 $\pi$는 optimal policy이다.
    
    $$ v_\pi(s) = \max_{a\in \mathcal A} q_\pi(s, a) $$

3.4 Modified Policy Iteration

💬 Q. policy iteration을 수행할 때, evaluation단계에서 $v_\pi$가 수렴할 때까지 반드시 진행해야하는가?

*여러가지 아이디어

$\infin$보다 조금 더 일찍 종료할 수는 없을까?
$k=3$과 같이 iteration횟수를 정해두고 수행하면 안될까?

A. $v_\pi$가 수렴할 때까지 진행하지 않아도 된다!

극단적인 경우, 단 한번만 policy evaluation을 진행하고 바로 policy improvement 단계로 넘어가도된다.

정확히 수렴하지는 않았지만 달라진 policy에 대한 value가 업데이트 되었기 때문!

4. Value Iteration

policy가 존재하지 않을 때 Iterative한 방법을 사용하여 value 기반으로 최적의 value function을 찾는 과정

4.1 Principle of Optimality : Theorem

optimal policy의 component
- 첫번째로 optimal action $A_*$를 수행한다.
- 이후 그 다음 state $S'$에서 다시 optimal policy를 따라 진행한다.
Principle of Optimality : Theorem
A policy $\pi(a|s)$ achieves the optimal value from state $s$, $v_\pi(s) = v_(s)$, *if and only if
- For any state $s'$ reachable from s
- $\pi$ achieves the optimal value from state $s'$, $v_\pi(s') = v_*(s')$

4.2 Deterministic Value Iteration

value iteration; DP의 도입
- $v_(s')$를 구하는 문제는 여러개의 *subproblem**들로 표현할 수 있다.
- subproblem
  
  one-step lookahead를 통하여 $v_*(s)$를 구할 수 있다. [Bellman Optimality Equation]
  
  $$ v_(s) \leftarrow \max_{a\in\mathcal A} \left(\mathcal R^a_s + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{ss'} v_(s')\right) $$

### 4.3 Example with Gridword

문제 : 최단거리를 찾는 문제
- reward는 항상 -1

4.4 Value Iteration

문제 정의
- problem : optimal policy $\pi$를 찾는 것을 목적으로 한다.
- solution : Bellman optimality equation을 이용하여 iterative한 방법을 적용한다.
  
  $v_{1;\ init} → v_2 → \cdots → v_*$
- synchronous backup
  1. each iteration k+1
    1. for all states $s \in \mathcal S$
      1. update $v_{k+1}(s)$ from $v_k (s')$
      → 전 단계 $k$에서의 value f를 이용하여 현재 단계 $k+1$에서의 value를 갱신한다.
      
      (where $s'$는 $s$에서 갈 수 있는 가능한 모든 state)
    → 이 과정을 반복하면 $v_\pi(s)$에 수렴하게 된다.
- policy가 주어지지 않는다.

Bellman optimality Equation

$$
v_{k+1}(s) = \max_{a\in \mathcal A} \left( \mathcal R^a_s + \gamma \sum_{s'\in \mathcal S} \mathcal P^a_{ss'}v_k(s')\right)
$$

$$
\bold v_{k+1} = \max_{a\in\mathcal A} \mathcal R^{\pi} + \gamma \mathcal P^\pi \bold v_k
$$

model을 알 때, prediction과 control문제의 해결방법

문제	사용하는 벨만 방정식	알고리즘
Prediction	Bellman Expectation Equation	Iterative
Policy Evaluation
Control	Bellman Expectation Equation +
Greedy Policy Improvement	Policy Iteration
Control	Bellman Optimality Equation	Value Iteration

5. Extensions to DP*

기본적인 DP 방법을 적용하여 RL문제를 해결하는 것은 computation적으로 비효율이 너무 크기 때문에 여러가지 테크닉을 이용한다.

5.1 Asynchronous DP

In-Place DP
- 기존 방법 (synchronous) : $k$번째의 value function에 대한 정보와 $k+1$번째의 value function에 대한 정보를 따로 저장해야하기 때문에 2배의 저장공간을 필요로 한다.
  
  $$ v_{\text {new}}(s) \leftarrow \max_{a\in \mathcal A} \left( \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S} \mathcal P^a_{ss'} v_{\text{old}}(s')\right)\\ \ v_{\text{old}} \leftarrow v_{\text{new}} $$
- In-Place : 갱신된 값과 갱신되지 않은 값을 저장하기 위한 공간을 따로 할당하지 않고 바로 덮어씌워서 업데이트 한다.
  - 다른 state에 대해 value를 계산할 때는 이제 바로 직전에 갱신된 값을 사용하게된다.
  - 이렇게 구현하더라도 문제를 풀 수 있다는 것은 증명되어있다.
    
    $$ v(s) \leftarrow \max_{a\in \mathcal A} \left( \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S} \mathcal P^a_{ss'} v(s')\right) $$
Prioritised Sweeping
- state에 우선순위(priority)를 두어, value를 업데이트할 때 중요한 state를 먼저 갱신한다.
- 중요한 state?
  → Bellman error가 큰 state

$$
\left| \max_{a\in \mathcal A} \left( \mathcal R^a_s + \gamma \sum _{s' \in \mathcal S}\mathcal P^a_{ss'}v(s') \right) - v(s)\right|
$$

Real-Time DP
- state의 공간은 매우큰데 실제로 agent가 유의미하게 자주 방문하는 state는 그리 많지 않을 때,
- Agent가 실제로 방문한 state를 먼저 업데이트한다.

$$ v(S_t) \leftarrow \max_{a\in \mathcal A} \left( \mathcal R^a_{S_t} + \gamma \sum_{s'\in\mathcal S} \mathcal P^a_{S_ts'} v(s')\right) $$

5.2 Full-width & sample backups

Full-width backup
- DP의 방법론
- $s$에서 갈 수 있는 모든 $s'$를 이용하여 업데이트한다. → 이럴 필요가 있는가?

Sample backup

- large MDP에서는 Full-width backup으로 구현하기 매우 어렵다.

    (state수가 늘어날 수록 계산량이 exponential하게 변화함)

- Advantage
   - state가 많아지더라도 고정된 sample의 수만 확인하기 때문에 cost가 일정하다.
   - Model-free인 문제에서도 수행할 수 있다.
   - break the curse of dimensionality

![](https://velog.velcdn.com/images/webb-c/post/3a06d87a-38ca-4703-a913-60f41eaf99a1/image.png)

5.3 Approximate DP

$$ \tilde v_k(s) = \max_{a\in \mathcal A} \left( \mathcal R^a_s + \gamma \sum_{s' \in \mathcal S} \mathcal P^a_{ss'} \hat v (s' \bold w_k)\right) $$

Reference

[강화학습] Markov Decision Process

Tue, 24 Jan 2023 17:04:06 GMT

본 포스팅은 David Silver 교수님의 강화학습 강의와 그 강의를 정리한 팡요랩 강의를 바탕으로 정리한 것입니다.

문제를 해결하기 위해서는 먼저 문제를 잘 정의하는 것에서부터 시작하여야한다.

대부분의 강화학습 문제는 Environment를 MDP로 formal하게 표현할 수 있다.(fully observable) 그렇다면 MDP는 무엇이며, MDP를 풀기 위해서는 어떻게 해야하는가?

1. Markov Processes : MP

1.1 Markov Property

✂️ “The future is independent of the past given the present”

Definition of Markov Property
A state $S_t$ is Markov if and only if $$ \mathbb P[S_{t+1}|S_t] = \mathbb P [S_{t+1} | S_1. \cdots, S_t] $$
- 시작 state $S_1$에서부터 현재 state $S_{t+1}$까지 도달할 확률이 바로 이전 state $S_{t}$에서 현재 state $S_{t+1}$까지 도달할 확률과 같은 state를 Markov state라고 한다.
- 이전 state만 알 수 있다면, 이전까지의 모든 history는 잊어버려도 된다.
- 강화학습의 문제는 기본적으로 MDP로 표현하기 때문에 Markov Property를 따른다고 가정한다.
State Transition Matrix
- Basic Markov Process에서는 action 없이, 매번의 time-step마다 state를 확률에 기반하여 옮겨다니게 된다.
- Markov state $s$에서 $s'$로 transition할 probability은 다음과 같이 정의된다.
  
  $$ \mathcal P_{ss'} = \mathbb P[S_{t+1}=s' | S_t = s] $$
- 가능한 모든 state $s$와 $s'$ pair를 원소로 갖는 matrix로 표현할 수 있다. (matrix의 각각의 row의 합은 1)
  
  $$ \mathcal P = \begin{bmatrix} \mathcal P_{11} & \cdots & \mathcal P_{1n} \ \vdots & & \vdots \ \mathcal P_{n1} & \cdots & \mathcal P _{nn}\end{bmatrix} $$

1.2 Definition of Markov Processes

Definition of Markov Processes
A Markov Process is a tuple $< \mathcal S, \mathcal P >$
- $\mathcal S$ is a (finite) set of states
- $\mathcal P$ is a state transition probability matrix, $$ \mathcal P {ss'} = \mathbb P [S{t+1}=s'|S_t = s] $$
  - Markov process는 memoryless random process이다.
    - memoryless는 내가 지금까지 어떤 경로를 따라 도달했는지 상관없이 state s에 도달한 순간, $s'$를 결정할 수 있다.
    - random process는 동일한 state에서 시작하더라도 어떤 state를 거치는지에 따라 여러가지 episode를 샘플링을 할 수 있다는 뜻이다.
      → 즉, random한 state들의 sequence $S_1, S_2, \cdots$ 는 Markov property를 따른다!

1.3 Example of Markov Processes

위와 같은 model에서 $S_1=C1$에서 시작하는 Sample episode는 다음과 같은 것들이 있을 수 있다.
- C1 → C2 → C3 → Pass → Sleep
- C1 → FB → FB → C1 → C2 → Sleep
- C1 → C2 → C3 → Pub → C2 → C3 → Pass → Sleep
- C1 → FB → FB → C1 → C2 → C3 → Pub → C1 → FB → FB → FB → C1 → C2 → C3 → Pub → C2 → Sleep
Model의 Edge에 표기된 probability를 바탕으로 다음과 같은 Transition Matrix를 정의할 수 있다.

2. Markov Reward Processes : MRP

2.1 Definition of Markov Reward Processes

Definition of Markov Reward Processes
A Markov Reward Process is a tuple $< \mathcal S, \mathcal P , \color{red} \mathcal R, \mathcal \gamma \color{b}>$
- $\mathcal S$ is a finite set of states
- $\mathcal P$ is a state transition probability matrix, $\mathcal P_{ss'} = \mathbb P [S_{t+1}=s'|S_t = s]$
- $\mathcal R$ is a reward function, $\mathcal R_s = \mathbb E[R_{t+1} | S_t = s]$
- $\gamma$ is a discount factor, $\gamma \in [0, 1]$
Reward
- state의 변화에 따른 reward를 “environment”가 Agent에게 알려준다.
- MRP에서는 현재 state $S_t=s$에 도달하면 Reward $R_{t+1}$을 제공한다.
- Agent는 immediate reward 뿐만 아니라, 이후로 얻게되는 미래의 reward까지 고려한다. (with discount)

2.2 Value function

Definition of Return

The return $G_t$ is the total discounted reward from time-step $t$

$$ G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum^\infin_{k=0} \gamma^k R_{t+k+1} $$
- discount $\gamma \in [0,1]$
  - $k+1$ time-step이후의 reward는 $\gamma^k R$의 reward로 표현된다.
  - immediate reward가 delayed reward보다 더 큰 영향을 줄 수 있게 한다.
    - $\gamma$ 값에 따른 효과
  - $0$에 가까울수록 “myopic” evaluation (근시안적)
  - $1$에 가까울수록 “far-sighted” evaluation (미래지향적)
    - why discount?

    *discount가 없을 때 발생할 수 있는 문제점*

    - **infinite**한 time-step을 가질 때, 매 time step마다 0.1의 reward를 받는 episode와 1의 reward를 받는 episode를 구분할 수 없다. ($\infin$ 크기비교 불가)
    - Agent가 시작할 떄 1을 받은 경우와 종료할 때 1을 받은 경우 둘 중에 어떤 episode가 더 나은지를 판단할 수 없다.

Definition of Value Function

The state value function $v(s)$ of an MRP is the expected return starting from state $s$

$$ v(s) = \mathbb E[G_t|S_t=s] $$
- 현재 state $s$에서 Return에 대한 기댓값으로 value function을 정의할 수 있다.

2.3 Bellman Equation for MRPs

Bellman Equation
- value function은 다음의 2가지 part로 분리할 수 있다.
  - immediate reward $R_{t+1}$

  - **discounted** **value** *of* *successor* *state*  $\gamma v(S_{t+1})$

유도과정
1. $v(s) = \mathbb E [G_t | S_t = s]$
2. $= \mathbb E [R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots | S_t=s]$
3. $= \mathbb E [R_{t+1}+\gamma (R_{t+2} + \gamma R_{t+3} + \cdots) | S_t=s]$
4. $= \mathbb E [R_{t+1}+\gamma G_{t+1} | S_t=s]$
5. $= \mathbb E [R_{t+1}+\gamma v(S_{t+1}) | S_t=s]$

Bellman Equation의 직관적인 이해
- Bellman Equation
  
  $$ v(s) = \mathbb E [R_{t+1} + \gamma v(S_{t+1})|S_t = s] $$
  
  현재 state $s$가 transition할 수 있는 다음 state $s'$들의 후보는 여러가지가 있을 수 있다. 여러가지 후보 중에서 “확률”에 따라 next state를 결정하게 된다. 따라서 가능한 여러가지 episode들에 대한 기댓값으로서 리턴을 계산하며, 이 때 같은 value-function을 사용하여 재귀 형태로 표현할 수 있게된다.

- *Expectation을 제거한 형태*
  - MRP에서 1-step Reward는 현재의 state $s$에 따라 고정된 상수이기 때문에 그대로 빠져나온다.
   - $v(s')$는 next state s’가 무엇인지에 따라 달라지는 값이기 때문에 Expectation을 적용한다.  
   *Definition of Expectation : probability $\times$ value 


$$
v(s) = \mathcal R_s + \gamma\sum_{s'\in \mathcal S} \mathcal P_{ss'}v(s')
$$

for Matrix Form

$$ v = \mathcal R + \gamma \mathcal Pv $$

$v$ is a column vector with one entry per state

$$ \begin{bmatrix} v(1) \ \vdots \ v(n) \end{bmatrix} = \begin{bmatrix} \mathcal R_1 \ \vdots \ \mathcal R_n \end{bmatrix} + \gamma \begin{bmatrix} \mathcal P_{11} & \cdots & \mathcal P_{1n} \ \vdots & & \vdots \ \mathcal P_{n1} & \cdots & \mathcal P_{nn} \end{bmatrix} \begin{bmatrix} v(1) \ \vdots \ v(n) \end{bmatrix} $$
- solving Bellman Equation
  
  $$ v = \mathcal R + \gamma \mathcal Pv $$
  
  $$ (I-\gamma\mathcal P) v = \mathcal R $$
  
  $$ v = (I - \gamma \mathcal P)^{-1} \mathcal R $$
  
  ⇒ Bellman Equation을 linear equation으로 표현하여 directly solve할 수 있다!
- 단점
  - 단, computational complexity가 $O(n^3)$이다.
  - state가 커질수록 계산량이 매우 커지기 때문에 direct solution은 small MRPs에만 적용한다.
- 대부분의 경우 MRPs는 iterative method를 이용하여 해결한다.
  - Dynamic Programming
  - Monte-Carlo evaluation
  - Temporal-Difference learning
  여기서 소개된 iterative method는 MDP를 solve하기 위해서 사용되는 방법이기도 하다. MRP와 달리 MDP는 directly solve를 위한 방법이 존재하지 않기 때문에, iterative method를 채택한다.

2.4 Example of MRPs

Sample returns for Student MRP

starting from $S_1 = C1$ with $\gamma = 0.5$ 일 때, 각각의 sample episode들에 대한 Return은 다음과 같이 계산될 수 있다.

$$ G_1 = R_2 + \gamma R_3 + \cdots + \gamma^{T-2}R_T $$

discount value에 따른 state value의 변화

Bellman Equation

Q. 빨간색 state의 value가 $4.3$이라고 알려져 있을 떄, Bellman Equation을 만족하는가?

3. Markov Decision Processes : MDP

3.1 Definition of Markov Decision Processes

MP, MRP에서는 state의 변화가 오로지 Environment의 transition probability $\mathcal P$에 의해 결정되었다.

그러나 MDP에서는 state의 변화가 Agent의 Action $\mathcal A$에 의해 결정되게 된다! (다만, 여전히 환경의 불안정함은 존재)

Definition of Markov Reward Processes
A Markov Reward Process is a tuple $< \mathcal S, \color{red} \mathcal A, \color{b}\mathcal P , \mathcal R, \mathcal \gamma>$
- $\mathcal S$ is a finite set of states
- $\mathcal A$ is a finite set of actions
- $\mathcal P$ is a state transition probability matrix, $\mathcal P^{a}{ss'} = \mathbb P [S{t+1}=s'|S_t = s, A_t = \color {red} a \color{b} ]$
  
  → state $s$에서 action $a$를 취할 때, state $s'$에 도달할 확률 (환경의 불안정함)
- $\mathcal R$ is a reward function, $\mathcal R^a_s = \mathbb E[R_{t+1} | S_t = s, A_t = \color{red} a \color{b} ]$
- $\gamma$ is a discount factor, $\gamma \in [0, 1]$
state transition probability
- Agent가 어떠한 Action을 취했을 때, Agent가 인식하는 state가 deterministic하게 결정되지 않고 “확률”적으로 정해지게 된다.
  - 또한 해당 state에서 그 Action을 할 확률도 정해진다.
  - Example) 무인이동체가 우회전이라는 action을 결정했지만, 그 순간 빨간불로 신호가 바뀌어 우회전을 하지 못하고 정지하는 경우

3.2 Policy & Value function

Definition of Policy

A policy $\pi$ is a distribution over actions given states,

$$ \pi(a|s) = \mathbb P[A_t=a|S_t=s] $$
- state $s$에서 action $a$를 수행할 확률 분포
- Agent는 policy를 따라서 어떤 action을 선택할지를 결정하게 된다.
- MDP의 policy는 agent가 지금까지 겪어온 history가 아닌, 오직 current state에 의해서만 의존한다.$^{[1]}$
- Policies are stationary (time-independent)
  $A_t ∼ \pi (\cdot|S_t),\ \ \forall t>0$

(번외) policy와 MDP를 이용하여 MRP로 표현하기

MDP에서 Agent의 policy가 고정이라면 Agent가 없는 Markov Process로 표현할 수 있다.

Given an MDP $\mathcal M = < \mathcal S, \mathcal A, \mathcal P, \mathcal R, \gamma>$ and a policy $\pi$
- State sequence $S_1, S_2, \cdots$ → Markov process $<\mathcal S, \mathcal P^\pi>$ 로 표현할 수 있다.
  - State and Reward sequence $S_1, R_2, S_2, \cdots$ → Markov reward process $<\mathcal S, \mathcal P^\pi, \mathcal R^\pi, \gamma>$ 로 표현할 수 있다.
    *where : policy가 고정되어있다면, 어떤 action 선택하고-transition probability에 따라 최종적으로 어떤 state가 next state가 되는지를 확률로서 계산할 수 있다.
- transition probability : $s'$으로 갈 확률은 각 action의 확률 $\times$ action $a$를 했을 때 $s'$로 갈 확률의 합(기댓값)
- reward : $s$의 return은 각 action의 확률 $\times$ action $a$를 했을 때 $s$의 reward의 합(기댓값)
  
  $$ \mathcal P^\pi_{s,s'} = \sum_{a\in\mathcal A} \pi(a|s) \mathcal P^a_{ss'} $$
  
  $$ \mathcal R^\pi_{s} = \sum_{a\in\mathcal A} \pi(a|s) \mathcal R^a_{s} $$
Value Function
- 어떤 “policy” 를 따라 episode를 진행하는지에 따라 value가 달라질 수 있기 때문에, Agent가 어떻게 행동하는지를 나타내는 policy $\pi$를 함께 기술해야한다.
- Definition of state-value function
  
  The state value function $v_\pi(s)$ of an MDP is the expected return starting from state $s$, and then following policy $\pi$
  
  $$ v_\pi(s) = \mathbb E_\pi[G_t|S_t=s] $$
- Definition of action-value function
  
  The action value function $q_\pi(s, a)$ is the expected return starting from state $s$, taking action $a$, and then following policy $\pi$
  
  $$ q_\pi(s,a) = \mathbb E_\pi[G_t|S_t=s, A_t = a] $$
  - 현재 state $s$에서 선택하는 action $a$는 policy를 따라 선택한 것이 아닐수도 있다! 단, 이후 episode를 진행할 때는 policy $\pi$를 따라 진행하게 된다.
  - action-value function이 정의된다면, Agent가 어떤 action을 선택할 지 결정할 때 Action value function의 값을 보고 선택하기만 하면된다.
    ⇒ 즉, 문제를 간단하게 표현할 수 있다. (state value function을 사용하면 다른 state들의 value function을 알아야하며, 그때 어떤 action을 했을 때 $s'$로 가게될 확률도 알고 있어야한다.)
  - Q-learning이나 DQN같은 곳에서 사용하는 Q가 바로 action-value function을 의미한다.

3.3 Bellman Expectation Equation

MRP에서 value function을 2가지 part(immediate reward, discounted value)로 분리했던 과정을 동일하게 적용하면 MDP에서도 초기 Bellman Equation을 쉽게 얻을 수 있다.

Bellman Expectation Equation (초기)
- Bellman Expectation Equation for $v_\pi$
  
  $s$에서의 state-value는 $\pi$를 따라 1-step 수행하여 받은 reward와 next-state $S_{t+1}$에서의 value의 합의 기댓값과 동일하다.
$$
```
  v_\pi(s) = \mathbb E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t=s] \\ \ \\
```
$$

- **state와 action의 관계** - (1)  
  - state의 value는 그 state에서 가능한 모든 action($a\in \mathcal A$)에 대한 action-value의 기댓값과 동일하다.
  - action의 선택은 오로지 policy에 의존하기 때문에 확률분포에 따라 episode별로 선택된 action이 달라지고 따라서 reward가 변화하여 정확한 값을 모르기 때문에 기댓값 형태로 표현해야한다.
  - state-value function의 definition이 policy에 의해 선택된 action에 대한 가능한 모든 episode의 리턴의 기댓값이기 때문에 Q-function으로 표현할 수 있다.  

  → $G_t$에 대한 기댓값의 다른 표현

$$ v_\pi(s) =\sum_{a\in\mathcal A} \pi(a|s) q_\pi(s,a) $$

Bellman Expectation Equation for $q_\pi$

$s$에서 action $a$를 선택하여 받은 action-value는 $a$를 선택해 1-step 수행하여 받은 reward와 next-state $S_{t+1}$에서의 action-value의 합의 기댓값과 동일하다.

$$ q_\pi(s,a) = \mathbb E_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})|S_t=s, A_t = a]\\ \ $$
- action과 state의 관계 - (2)
  - action의 value는 action을 수행함으로써 전달받는 1-step reward $\mathcal R^a_s$과 가능한 모든 next-state($s'\in \mathcal S$)에 대한 state-value의 (감쇄)기댓값의 합과 동일하다.
  - 특정 action $a$를 수행하면 그 때 받게되는 reward의 값을 확실하게 알 수 있기 때문에 immediate rewrd를 이용하여 표현한다.
  - Bellman Expectation Equation에서 Expectation $\mathbb E$를 제거한 형태

    $$
    q_\pi(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_\pi(s')
    $$

Bellman Expectation Equation [재귀]

MRP에서의 Bellman Equation과 달리, MDP에서는 action의 존재로 인하여 가장 초기의 Bellman Equation을 바로 재귀적으로 표현하기 힘들다. 따라서 action-value와 state-value간의 관계를 이용하여 재귀적 표현으로 Bellman Expectation Equation을 표현한다.

→ 그대로 관계식을 대입한다!
- Bellman Expectation Equation for $v_\pi$

    $$
    v_\pi(s) =\sum_{a\in\mathcal A} \pi(a|s) \left( \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_\pi(s')\right)
    $$

- Bellman Expectation Equation for $q_\pi$

    ![](https://velog.velcdn.com/images/webb-c/post/51c24b9a-b976-44e4-b7a3-173affa676fb/image.png)


    $$
    q_\pi(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'} \sum_{a'\in\mathcal A}\pi(a'|s') q_\pi(s',a')
    $$

for Matrix Form
*MDP에서 Agent의 policy가 고정이라면 Agent가 없는 MRP로 표현할 수 있기 때문에, 그대로 matrix form을 적용해서 direct solution을 얻을 수 있다.

$$ v_\pi = \mathcal R^\pi + \gamma \mathcal P^\pi v_\pi $$

with direct solution

$$ v_\pi = (I - \gamma \mathcal P^\pi)^{-1} \mathcal R^\pi $$

3.4 Example of MDPs

MDP의 예시 : Action에 대하여 reward가 제공된다

MDP에서 state-value function의 계산

Bellman Expectation Equation

Q. 빨간색 state의 value가 $7.4$라고 알려져 있을 떄, Bellman Expectation Equation을 만족하는가?

4. Optimal Solution

4.1 Optimal Value Function

Definition of Optimal Value Function

가능한 모든 policy에 대하여 계산했을 때, 그 중에서 가장 maximum 값을 갖는 value function
- Definition of optimal state-value function
  
  The optimal state value function $v_(s)$ is the *maximum** value function over all policies
  
  $$ v_*(s) = \max_\pi v_\pi(s) $$
- Definition of optimal action-value function
  
  The optimal action value function $q_(s, a)$ is the *maximum** action-value function over all policies
  
  $$ q_*(s,a) = \max_\pi q_\pi(s,a) $$
Optimal Value Function
- optimal value function은 MDP에서 가능한 최고의 성능을 나타낸다.
- 해당 MDP의 optimal value function을 찾았다면, 그 MDP는 “solved”되었다고 한다.
- 일반 value function과 달리 bellman optimality eqation은 matrix form으로 표현되지 않기 때문에 directly solve가 불가능하다.
Example

optimal policy를 따랐을 때, state-value function과 action-value function

4.2 Optimal Policy

policy간의 partial ordering

모든 state에 대하여 $v_\pi(s)$가 $v_\pi'(s)$보다 같거나 크다면, $\pi$가 $\pi'$보다 더 나은 policy 라고 말할 수 있다.

$$ \pi \ge \pi' \text{ if } v_\pi(s) \ge v_{\pi'}(s), \forall s\\ \ $$
Theorem of policy

For any Markov Decision Process
- 다른 모든 policy보다 더 같거나 좋은 $\pi_* \ge \pi, \forall \pi$ optimal policy $\pi_*$가 존재한다.
- optimal policy를 따르는 value function은 optimal value function과 동일하다
  - 모든 optimal policy는 그 optimal policy를 따르는 optimal value function을 가진다. $v_{\pi_}(s) = v_(s)$
  - 모든 optimal policy는 그 optimal policy를 따르는 optimal action-value function을 가진다.
    
    $q_{\pi_}(s,a) = q_(s,a)$

Optimal Policy를 찾는 방법
- optimal action-value function에 대하여 max가 되게하는 action만을 계속해서 취하는 policy
- 즉, optimal action-value function $q_(s,a)$을 알고있다면 그 즉시 *deterministic optimal policy를 구할 수 있다. ⇒ MDP를 solve!
  
  deterministic
  - 원래 policy는 각각의 action을 수행할 확률로 정의되기 때문에 stochastic하다.
  - 그러나 optimal action-value function을 사용하여 구한 optimal policy는 하나의 action만을 하도록 결정된 deterministic한 policy이다.
  $$ \pi_(a|s) = \begin{cases} 1 & \text{if } a= \argmax_{a\in \mathcal A}q_(s,a)\ 0 & \text{ otherwise}\end{cases} $$
Example : Optimal Policy

4.3 Bellman Optimality Equation

기본적으로 Bellman Expectation Equation과 동일한 구조를 이룬다. 다만, optimal policy를 알지 못하여 모든 수식을 Expectation으로부터 표현하기 시작했던 것과 달리 여기서는 optimal policy $*$를 알고있기 때문에 이를 이용하여 equation을 표현한다.

Optimal state-value function과 Optimal action-value function의 관계
- state과 action의 관계 - (1)
  - state $s$의 optimal value는 그 state에서 optimal action-value가 최대가 되게하는 action $a$을 취했을 때의 optimal action value와 동일하다.
  - action-value를 maximize하는 action을 선택하는것이 optimal하기 때문에 자명하다.

    $$
    v_*(s) =\max_aq_*(s,a)
    $$

- action과 state의 관계 - (2)
    - (state $s$에서) action $a$의 optimal value는 action을 수행함으로써 전달받는 1-step reward  $\mathcal R^a_s$과 가능한 모든 next-state($s'\in \mathcal S$)에 대한 **optimal** state-value의 (감쇄)기댓값의 합과 동일하다.
    - action을 하더라도 그 다음 state가 무엇으로 결정되는지는 환경의 불안정성(=state probability)를 따르기 때문에 기댓값의 형태로 표현한다.

    ![](https://velog.velcdn.com/images/webb-c/post/14c756cf-8cba-4568-a886-195ae5705296/image.png)


    $$
    q_*(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_*(s')
    $$

Bellman Optimality Equation [재귀]
- Bellman Optimality Equation for $v_\pi$

    $$
    v_*(s) =\max_a \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_*(s')
    $$

- Bellman Optimality Equation $q_\pi$

    ![](https://velog.velcdn.com/images/webb-c/post/c380cf0d-865a-4830-a5db-f7a9520c3767/image.png)


    $$
    q_*(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'} \max_{a'} q_*(s',a')
    $$

Example

Q. 빨간색 state의 value가 $6$이라고 알려져 있을 떄, Bellman Optimality Equation을 만족하는가?

Bellman Optimaliy Equation을 푸는 방법
- Bellman Optimally Equation은 non-linear equation이다. ($\max$ 때문)
  
  ⇒ 따라서 closed form solution을 가지지 았는다. (in general)
- Many iterative solution methods
  - Value Iteration (DP)
  - Policy Iteration (DP)
  - Q-learning
  - SARSA

Reference

파워포인트에서 LaTex 문법 사용하여 수식넣기 : IguanaTex

Tue, 17 Jan 2023 17:19:31 GMT

최근 랩미팅 발표용 파워포인트를 제작할 때마다 느껴지는 불편함이 존재했다.

현재 나는 다년간의 경험으로 수식을 입력할 때 LaTex 문법이 매우 익숙해진 상태이다. ppt를 제작할 때 레이텍으로 Notion에 정리해둔 수식을 그대로 끌어와서 ppt에 삽입하고 싶은데 MSpowerpoint는 레이텍을 지원하지 않아서 파워포인트 자체적으로 지원하는 수식 입력 기능을 사용해야한다.

파워포인트에서 한번이라도 수식을 입력해본적이 있다면 이게 얼마나 귀찮은 일인지 알고 있으리라 생각한다. (^, _ 사용 불가, 기호 단축키 없음...)

그래서 최근에 계속 수식을 삽입할 때마다 귀찮음을 느끼고 있어서 새벽에 생각난 김에 해결방법을 한번 찾아보았다.

IguanaTex

IguanaTex라는 MS powerpoint용 add-in을 사용하면, LaTex문법으로 작성된 수식을 그대로 이용하여 파워포인트 안에 삽입할 수 있다!

🔗 IguanaTex 홈페이지

위 홈페이지에 접속하면 IguanaTex에 대한 설명과 간단한 사용방법, 그리고 github 주소를 얻을 수 있다.

깃허브에서 자신이 맞는 운영체제(Window/MacOS/Linux)를 선택하여 README에서 안내하는 방식을 따라 설치하면 된다.

나는 MacOS를 사용하고 homebrew를 이용하기 때문에 별도로 다른 파일을 다운로드 없이 터미널에서 명령어 입력을 통해 자동 다운로드 방식으로 설치했다.

brew tap tsung-ju/iguanatexmac
brew install --cask --no-quarantine iguanatexmac latexit-metadata

제대로 설치가 완료되었다면, 파워포인트의 상단 탭에 자동으로 IguanaTex가 추가된것을 확인할 수 있을 것이다.

사용방법

새로운 수식 삽입하기

New Latex display
default틀 안에, LaTex문법으로 작성된 equation을 삽입한다.
Generate를 누르면 파워포인트에 삽입할 수식 "이미지"를 생성하고 자동으로 현재 ppt 슬라이드에 수식이 추가된다.

사용예시

기존 LaTex 수식
파워포인트에 삽입된 수식

이미 삽입한 수식 수정하기

수정하고자하는 수식 이미지를 선택한다.
Edit LaTex display
수식을 수정한 뒤 ReGenerate를 눌러 변경된 수식을 다시 삽입한다.

매우 편리하게 사용할 수 있으며, 작성된 수식을 캡쳐하여 첨부하면 화질이 깨지지만 실제로 수식을 입력하자니 귀찮았던 두가지 문제를 모두 해결해주는 유용한 기능이라고 생각한다.

또는 레이텍 문법에 많이 익숙하다면, LaTex을 이용하여 프레젠테이션 파일을 PDF 형식으로 제작할 수 있는 Beamer latex을 이용하여도 된다.

나는 Beamer Latex까지 사용하기에는 너무 시간이 오래 걸릴 것 같아서 이구아나로 만족하고 있다!

[강화학습] Deep Reinforcement Learning

Thu, 05 Jan 2023 08:26:27 GMT

1. Deep Reinforcement Learning

1.1 Needs for DRL

기본적인 강화학습 방법들은 Agent가 반복해서 시뮬레이션하면서 Agent가 겪는 경험들을 이용하여 action을 선택할 때 참조하는 일종의 look-up table을 갱신하는 방법이었다. 즉, 경험;heuristic을 통해 데이터베이스를 쌓아가면서 나에게 유리한 action과 그렇지 않은 action을 구분해나가는 방법이다.

*look-up table : 특정한 state에 연관된 action과 reward를 기록한 table

그러나 더이상 모든 state와 그때의 가능한 모든 action을 표기할 수 없을정도로 큰 state space, action space를 갖는 환경이라면, look-up table의 형식으로 표현하는것이 불가능하다.

Deep Reinforcement Learning은 신경망을 이용하여 학습하면서, 주어진 state에서 중요한 feature만을 뽑아내어 state를 자동으로 분석한다. 신경망 모델에서 사용되는 parameter는 가능한 모든 state의 조합을 저장하는데 필요한 항목의 개수보다 훨씬 적다!

예를 들어, Atari 2600 게임을 플레이하는 강화학습 agent를 학습하는데 사용했던 구글 딥마인드의 DQN의 파라미터의 개수는 $1792$개 뿐이지만 실제로 비디오 게임 화면($84\times 84$ gray scale image)의 고유한 표현상태는 $256^{28228}$개 였다.

DRL의 발전과 함께 강화학습도 많은 발전을 이루었으며, 실제 세계의 대부분의 문제는 매우 복잡한 state-action space를 가지기 때문에 실제 세계의 문제에 적용하기 위해서는 대부분 DRL을 사용한다.

1.2 Category of (Deep)RL

강화학습 알고리즘을 구분하는 기준은 크게 2가지로 나뉜다.

모델이 존재하는가?
- Model-Free RL
  - 모델이 존재하지 않는 RL
  - 실제 문제에서는 Environment를 정확히 묘사할 수 있는 모델을 구하는것이 매우 어렵다.
- Model-Based RL
  - 모델이 존재하는 RL
  - Environment를 정확히 표현할 수 있는 모델이 존재한다면, env와 실제로 상호작용하지 않고도 모델을 이용하여 Planning을 할 수 있다.
    
    → 즉, 실제로 Action을 하기전에 미리 simulate해보고 최적의 action을 선택할 수 있다.
  - 모델이 주어진 경우와, 모델을 스스로 학습하는 2가지 범주로 분류할 수 있다.
  - 대표적인 model-based RL이 바로 AlphaZero이다.
Value function / Policy 중에서 무엇을 최적화하는가?

Value function을 학습한다면, 각각의 state에서 최적의 value를 갖는 Action만을 선택하면 Optimal Policy를 구할 수 있다. 반면에 Policy를 학습한다면, value function은 Policy를 얻기 위하여 중간 계산과정일 뿐이기 때문에 Optimal Policy를 구할 수 있다.
- Policy-based method (Policy Optimization)
- Value-based method (Q-Learning)
  
  (완벽하게 2가지 범주로 구분되는 것은 아니고, 2가지를 모두 함께 학습하는 Actor-Critic 등의 방법들도 존재한다.)

2. DQN

2.1 Q-Learning

Q-Learning은 간단하게 설명하자면, 각각의 state에서 선택한 action에 따른 reward값을 이용하여 Q(=value function)값을 계속해서 갱신해나가는 과정이다. (using Bellman Optimal Equation)

💡 현재의 추측 value 값을, 바로 그 다음 time-step에서의 추측 value값을 이용하여 갱신하자

Q-Learning의 분류

Temporal-Difference; TD

episode가 끝날 때까지 기다리지 않고, 그 다음 time-step에서 즉각적으로 얻은 return과 그때의 value를 이용하여 갱신을 수행한다. (↔ episode가 끝날 때 까지 기다리는 방법이 MC)
Model-Free RL
Value based method

(보통 $\epsilon$-greedy와 같은 policy를 사용하여 action을 선택한다.)
off-policy

*off-policy와 on-policy?

off-policy는 실제로 environment와 상호작용하면서 경험을 쌓는 Agent와 실제로 내가 갱신하고자하는 Agent가 다른 경우를 뜻한다.

on-policy : target policy = behavior policy
off-policy : target policy ≠ behavior policy

예를 들어, 실제로 게임을 하면서 경험을 쌓아 티어가 올라가는 경우는 off-policy를 사용하는 것이고 게임을 계속 플레이하는 사람의 뒤에서 그 사람이 플레이 하는 것을 보고 학습하는 경우는 on-policy를 사용하는 것이다.

off-policy를 사용하는데에는 다음과 같은 이유가 존재한다.

사람이나 다른 RL method를 이용하여 학습된 Agent를 이용할 수 있다.
behavior policy를 따르는 agent가 수행한 결과를 보고, 좋지 못한 결과를 만드는 action의 경우에는 수정할 수 있다.

ex) 바둑에서 잘못된 곳에 둬서 승률이 급격하게 떨어지는 것을 확인했다면, target policy를 수정할 수 있다.

2.2 Q-update : in Formal

아이디어 : Bellman Optimal Equation for $q_{*}$

벨만 최적 방정식에 따라, $R_{t+1} + \gamma\max_a q_(S_{t+1}, a)$의 기댓값이 $q_(S_t, A_t)$이다. 즉, 여러번의 반복을 통해 바로 그 다음 time-step에서의 값을 모을 수록 점점 value function의 값을 업데이트 할 수 있을 것이다.

$$ q_*(S_t, A_t) = \mathbb E_{S_{t+1}}[R_{t+1} + \gamma\max_{a}q(S_{t+1}, a)] $$

Notation
- $Q$ : value-function → state와 그때 수행한 action이 주어지면 value를 평가하여 반환하는 함수
  - $S_t$ : time-step $t$에서 state
  - $A_t$ : time-step $t$에서 수행한 ation
각 term의 의미
- $\alpha$ : 갱신할 때, 새로운 값을 기존의 value-function값에 비하여 어느정도로 고려할 것인가?
- $R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a )$ : TD target
  
  $\epsilon$-greedy 등의 policy를 이용하여 transition한 뒤, 다음 time-step에서 value를 최대로 하는 action을 선택했을 때의 value와 return의 합
  
  즉, Q-learning은 off-policy를 이용하기 때문에 transition은 behavior policy를 따라서 수행하고 이동한 미래의 state에서 value를 계산할 때는 target policy를 이용한다.
  
  ⇒ Target과 기존 값 $Q(S_t, A_t)$의 차이를 이용하여 Q-update를 수행한다.

$$ Q(S_t, A_t) \leftarrow Q(S_t,A_t) + \alpha(R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a )- Q(S_t, A_t))) $$

위와 같은 Q-update과정을 반복해서 수행하여 최종적으로 얻은 Optimal action value function은 다음의 수식으로 표현할 수 있다.

$$ Q_(S_t, A_t) = \mathbb E_{S_{t+1}} [R_{t+1} + \gamma \max_{a} Q_(S_{t+1}, a)] $$

2.3 DQN

DQN은 Q-Learning에서 value function을 Table형태가 아닌 “신경망”으로 표현하기 때문에, $Q$는 신경망의 parameter $\theta$에 영향을 받게 된다. 따라서 DQN에서는 value function term을 $Q_\theta$로 표현한다.

DQN으로 표현한 Q-Learning의 수식

Loss function

실제 정답을 $R_t + \gamma \max_{a_{t+1}}Q_{\theta}(s_{t+1}, a_{t+1})$ 라고 보고, 현재 value function값과의 차이의 제곱으로 loss를 표현한다.

$$ L(\theta) = \mathbb E[(R_{t+1} + \gamma \max_{a}Q_{\theta}(S_{t+1}, a) - Q_{\theta}(S_t, A_t))^2] $$
parameter update

$$ \theta' = \theta + \alpha\left(R_{t+1} + \gamma \max_{a}Q_{\theta}(S_{t+1}, a) - Q_{\theta}(S_t, A_t)\right)\nabla_\theta Q_\theta(S_t, A_t) $$

DQN의 성능향상을 위한 방법

Replay Buffer
- 이미 한번 겪었던 경험을 재사용함으로서 이전에 있었던 실수를 줄이고 더 나은 방향으로 학습하게하기 위하여 도입한 개념
- 여러개의 경험들을 저장해두었다가 샘플링하여 학습하면서, 여러번 재사용될 수 있다.
- 샘플링 되어 뽑히는 경험들은 실제 episode의 연속된 state와 달리 state간의 상관성이 떨어지기 때문에 더 효율적으로 학습할 수 있다.
target Network
- 학습 대상이 되는 Q-net과 정답을 계산할 때 사용되는 network 2가지를 사용하여 각 network에 사용되는 parmeter를 달리하는 방법
- 정답을 계산할 때 사용하는 네트워크가 자주 갱신되는 것은 학습의 안정성을 떨어트리기 때문에, 매우 긴 일정 주기마다 한번씩 정답 네트워크의 parameter를 갱신해준다.

2.4 Playing Atari with Deep Reinforcement Learning

“Playing Atari with Deep Reinforcement Learning” 은 처음으로 Neural Net과 Reinforcement Learning을 결합하여 유의미한 성과를 보인 논문이다.

Atari 2600 Games

Agent가 플레이하는 게임 : Atari 2600 games

⇒ 각각의 게임에 대해 학습한다면 여러 게임을 플레이할 수 있는 강화학습의 “알고리즘” 개발
게임 화면 : $210 \times 160$ (pixel) RGB video (60 Hz)

DQN Network 구조

게임 화면 “이미지”를 입력받기 때문에 CNN을 사용한다.

DQN Algorithm

notation
- reward $r$ : game score
- $s_1 = {x_1}$ : 한 episode의 sequence를 초기화
  
  → observation과 action의 sequence
- $x$ : observation → 게임 화면
- $\phi$ : image preprocessing

반복문
- for episode : 각각의 episode별로 반복하며 $M$번 수행
- for t : episode의 sequence time-step별로 반복

Reward 비교

다른 방법을 이용하여 학습한 모델들과 비교했을 때 훨씬 띄어난 성능을 보였으며, 몇몇 게임의 경우에는 심지어 사람이 play한 것보다도 좋은 성능을 보이는 것을 확인할 수 있다.

3. Policy Gradient Method

3.1 Concept of Policy Gradient

Action을 선택하기 위한 Policy를 참조할 때, Value function없이도 action을 선택할 수 있는 파라미터 기반의 policy를 학습하는 방법이다.

$\theta \in \mathbb R^d$로 표현되는 policy parameter vector를 이용하여 policy를 정의하고, parameter에 대한 value를 나타내는 $J(\theta)$의 gradient를 이용하여 policy의 parameter를 학습할 것이다.

policy를 나타내는 신경망의 구조
- input : state
- output : 그 state에 대한 각각의 action의 확률

Needs for Policy Gradient method

value based Agent는 Optimal value function $Q_$를 구하면, action을 선택할 때는 항상 value가 최대가 되게 하는 action만을 *deterministic**하게 선택한다.

그러나 policy는 $\pi(s,a) = \mathbb P[a|s]$ 처럼 “확률”로서 정의되기 때문에 policy based Agent는 다음 action이 non-deterministic한 유연한 선택을 할 수 있게 해준다.

Example

예를 들어, 가위바위보 게임에서 처음으로 낼 action을 고른다고 가정하자.

value based Agent에서 Optimal value function의 값이 $Q_(s_0, 보) = 0.1, Q_(s_0, 주먹) = 0.8, Q_(s_0, 가위) = 0.5$ 이라면 Agent는 $\max_a Q_(s_0, a)$을 따라 항상 “보”만을 선택하게 된다.

그러나 policy based Agent가 갖는 policy가 각각의 action에 대해 $1/3$이라면, 각각의 action을 선택할 확률이 $1/3$이 되어 $s_0$이 주어질 때마다 다른 action을 선택할 수 있다.

3.2 Policy Optimization : in formal

Policy Optimization을 위한 아이디어

loss의 정의
Policy Neural Net을 학습시키기 위해서는 Loss를 정의해야한다. Loss는 실제 정답과 현재 출력의 차이로서 정의할 수 있는데 policy net의 정답은 바로 Optimal Policy가 되지만, 이는 현재 우리가 모르는 상태이기 때문에 optimal policy를 정답으로 사용할수는 없다.
따라서 policy optimization을 수행할 때는, 현재 policy $\pi_\theta$가 얼마나 좋은지를 평가하는 평가함수 $J(\theta)$를 정의하여 평가함수의 값을 최대화하는 방향으로 Gradient Ascent를 통해 갱신한다.

평가함수의 정의
- Q. 그렇다면 좋은 정책은 무엇일까?
- A. Return의 합이 가장 큰 정책!
  
  각각의 episode에 따라 최종적으로 받는 Return의 합은 달라질 수 있기 때문에, 기댓값을 이용하여 표현하면 다음과 같이 평가함수를 정의할 수 있다.
  
  $$ J(\theta) = \mathbb E_{\pi_\theta} \left[ \sum_t R_t\right] $$
  
  Return의 합은 state-value function과 동일! (최종합이므로 start state에 대한 value function)
  
  $$ J(\theta) = \mathbb E_{\pi_\theta} \left[ \sum_t R_t\right] = v_{\pi_{\theta}} (s_0) $$
  
  시작 state가 고정이 아니고 시작 state 또한 매번 다른 상태에서 시작한다면, start state에 대한 확률분포를 정의하여 이에 따른 확률$\times$ 값; 기댓값 공식으로 표현한다.
  
  $$ J(\theta) = \sum_{s\in S}d(s) \times v_{\pi_\theta}(s) $$
Gradient ascent

최대화가 목적이기 때문에 gradient와 같은 방향으로 update한다.

$$ \theta' \leftarrow \theta + \alpha \nabla_\theta J(\theta) $$

Policy Optimization : 1-step

1-step MDP로 문제를 간소화하고 생각하자. start state $s_0$에서 policy를 따라 하나의 action을 선택한 뒤 바로 Return을 받고 episode가 종료된다.

가능한 모든 action에 대한 return의 기댓값; action을 선택할 확률 $\times$보상으로 value function을 재정의할 수 있다.

$$ J(\theta) = \sum_{s\in S}d(s) \sum_{a\in A}\pi_\theta(s, a)\times R_{s, a} $$

Gradient 도입

$$ \nabla_\theta J(\theta) =\nabla_\theta \sum_{s\in S}d(s) \sum_{a\in A}\pi_\theta(s, a)\times R_{s, a} $$

우리의 문제는 Model-free이며 무한히 많은 state가 존재하기 때문에 위의 term으로는 계산할 수 없다. 샘플기반 방법론을 도입한다면 아래와 같이 수식을 변경하여 계산할 수 있다.

$d(s)$는 $\theta$와 관계없음

$$ \nabla_\theta J(\theta) =\sum_{s\in S}d(s) \sum_{a\in A} \nabla_\theta \pi_\theta(s, a)\times R_{s, a} $$
분모 분자가 같은 값을 곱함 (=1이니까 수식자체에 변화는 없다)

$$ \nabla_\theta J(\theta) =\sum_{s\in S}d(s) \sum_{a\in A} \frac{\pi_\theta(s, a)} {\pi_\theta(s, a)}\nabla_\theta \pi_\theta(s, a)\times R_{s, a} $$

$$ \nabla_\theta J(\theta) =\sum_{s\in S}d(s) \sum_{a\in A} \pi_\theta(s, a)\frac{\nabla_\theta \pi_\theta(s, a)} {\pi_\theta(s, a)}\times R_{s, a} $$
$\ln x$의 미분을 이용하여 변경
1. $\frac{d }{dx} \ln x= \frac{1}{x}$
2. (양변 $\times dx$) ⇒ $d \ln x = \frac{dx}{x}$
  
  $$ \nabla_\theta J(\theta) =\sum_{s\in S}d(s) \sum_{a\in A} \pi_\theta(s, a)\nabla_\theta \log\pi_\theta(s, a)\times R_{s, a} $$
기댓값으로 표현

$$ \nabla_\theta J(\theta) =\mathbb E_{\pi_\theta} [\nabla_\theta \log \pi_\theta(s,a) \times R_{s,a}] $$

⇒ 기댓값으로 표현되었기 때문에, $\pi_\theta(s,a)$를 따라 움직이는 Agent가 실제로 Environment와 상호작용하면서 기댓값을 계산하기 위해 사용할 샘플값을 여러개 모아 평균을 내어 gradient를 계산할 수 있다.

1-step이 아닌 일반적인 MDP에서는 return을 바로 받는 것이 아니라 리턴의 기댓값 q로 표현된다.

$$ \nabla_\theta J(\theta) =\mathbb E_{\pi_\theta} [\nabla_\theta \log \pi_\theta(s,a) \times Q_{\pi_\theta}(s,a)] $$

3.3 REINFORCE

최초의 policy gradient method로 몬테카를로 기법을 이용한다. → episode 단위로 학습

action-value function의 정의에 따라 $Q_{\pi}(s,a) = \mathbb E_{\pi_\theta}[G_t|s_t=s,a_t=a]$로 표현될 수 있기 때문에 기댓값의 term 안에 $Q$를 $G_t$로 표현하여 넣어준다.

$$ \nabla_\theta J(\theta) =\mathbb E_{\pi_\theta} [\nabla_\theta \log \pi_\theta(s,a) \times G_t] $$

Algorithm

3.4 PPO

PPO는 Gradient를 이용하여 학습하기 때문에 발생하는 REINFORCE 알고리즘의 단점을 해결하기 위해 고안된 알고리즘이다.

Needs for PPO
- REINFORCE의 단점 : episode 단위로 학습하기 때문에 한번에 결과가 반영되어서 각각의 step에 대한 중요도가 잘 표현되지 않는다. ⇒ MC의 단점을 그대로 가짐
- 작은 step이 아닌 가능한 큰 step만큼 갱신을 하면서도 어느정도는 기존의 policy를 유지하고 싶다.
  
  ⇒ Gradient가 너무 커서도, 너무 작아서도 안되게 조절하고 싶다!!

Formal Optimization

policy gradients : loss의 미분값

$$ \nabla_\theta J(\theta) =\mathbb E_{\pi_\theta} [\nabla_\theta \log \pi_\theta(s,a) \times \hat A_{\pi_\theta}(s,a)] $$
obejective function
- gradient를 취하기 전 표현
  
  $$ J^{PG}(\theta) = \mathbb E_{\pi_\theta}[\log \pi_\theta(s,a)\times \hat A_{\pi_\theta} (s,a)] $$
- probability ratio를 이용한 표현
  
  $$ J_{\theta_\text{old}} (\theta) = \mathbb E_{\pi_\theta} \left[ \frac{\pi_\theta(s, a)}{\pi_{\theta_{old}}(s,a)} \hat A_{\theta_{old}}(s,a)\right] $$

probability ratio

old policy와 new policy 간의 probability ratio를 다음과 같이 정의할 수 있다.

$$ r(θ)=\frac{\pi_θ(a|s)}{π{θ{old}}(a|s)} $$

$θ_{old}$와 $θ$ 간의 차이에 대한 제한이 없다면, $J$를 maximize하기 위해 parameter $\theta$를 update할 때 극도로 커질 수도 있고 극도록 작아질 수도 있게 된다. 즉, 안정성이 매우 떨어지게된다.

PPO에서는 $r(θ)$가 1 이내의 작은 interval $[1−ϵ,1+ϵ]$ 사이의 값을 계속 가지도록 constraint를 추가함으로서 안정성을 유지할 수 있게 하였다. 원래의 값과, clip으로 다듬어진 probability ratio를 이용한 값 중에서 더 작은 값을 택한다.

⇒ 이로 인하여 더 많은 reward를 받기 위해 policy를 과하게 update하는 경우를 예방할 수 있다.

$$ J^{\text{CLIP}} (\theta) = \mathbb E [\min (r(\theta) \hat{A}{\theta{old}}(s,a),\ \text{clip}(r(\theta), 1-\epsilon , 1+\epsilon) \hat A_{\theta_{old}}(s,a))] $$

Actor-critic Network
policy(actor)와 value-function(critic)간에 parameter를 공유하는 network 구조에 PPO를 적용할 때는 value function에 대한 error값과 entropy에 대한 term을 추가하여 exploration을 더 고려해준다.

$$ J^{\text{CLIP}'}(\theta) = \mathbb E[J^{\text{CLIP}}(\theta) - c_1 (V_\theta(s) - V_{\text{target}})^2 + c_2 H(s, \pi_\theta(\cdot))] $$

(사실 policy optimization은 헷갈리는부분이 아직 있어서 추후에 따로 더 공부할 생각이다)

Reference

OpenAI
[RL] Policy Gradient Algorithm
바닥부터 배우는 강화학습, 노승은
심층 강화학습 인 액션

[강화학습] Introduction to Reinforcement Learning

Tue, 27 Dec 2022 02:36:33 GMT

본 포스팅은 David Silver 교수님의 강화학습 강의와 그 강의를 정리한 깃북, 팡요랩 강의를 바탕으로 정리한 것입니다.

1. What is Reinforcement Learning

1.1 Definition of RL (in WikiPedia)

강화 학습(Reinforcement learning)은 기계학습이 다루는 문제 중에서 다음과 같이 기술 되는 것을 다룬다. 어떤 환경을 탐색하는 에이전트가 현재의 상태를 인식하여 어떤 행동을 취한다. 그러면 그 에이전트는 환경으로부터 포상을 얻게 된다. 포상은 양수와 음수 둘 다 가능하다. 강화 학습의 알고리즘은 그 에이전트가 앞으로 누적될 포상을 최대화하는 일련의 행동으로 정의되는 정책을 찾는 방법이다.

학습 : 환경과의 상호작용을 통한 습득과정
기계학습 : 학습 과정을 “computational”한 방법으로 접근하는 것

기계학습의 범주

강화학습 : 올바른 action이 무엇인지 알지 못하지만, 환경과의 상호작용을 통하여 점차 학습해 나가는 기계학습의 한 학습 방법
Example*) 사람이 처음 자전거를 탈 때

1.2 Problem of RL

강화학습은 해결하고자하는 문제가 강화학습 문제; Problem인지를 기준으로 정의된다.
-> 대부분의 기계학습 방법들은 “어떻게 학습하는가”를 기준으로 정의된다. (학습하는 방식)

강화학습 문제의 예
- Fly stunt manoeuvres in a helicopter
- Defeat the world champion at Backgammon (→ AlpaGo)
- Manage an investment portfolio : 이윤을 maximize
- Control a power station
- Make a humanoid robot walk
- Play many different Atari games better than humans
강화학습의 특징
- no supervisor, only a reward signal
  - supervisor가 존재한다면 기계가 아무리 학습을 잘 하더라도 supervisor를 넘어설 수 없다.
    - 스스로 optimal 한 해를 찾아간다. ↔ supervisor는 아무리 잘 하더라도 suboptimal일 가능성이 높다…!
    - Example) 바둑에서 이기는 것을 목적이라고 할 때, supervised learning은 어떻게 돌을 둬야 좋은지 직접 일일이 훈수하는 것이라면, RL은 게임에서 이기는게 좋은 reward를 줄 뿐 어떻게 해야 게임에서 이길지를 알려주지 않는다.
- Agent’s actions affect the subsequent data it receives
  - 수행한 행동에 따라서 그 다음에 주어지는 데이터가 달라진다.
    ↔ 일반적인 기계학습 모델은 train set이 정해져있다. (ex. image classification…)
- Delayed Reward
  - 강화학습은 “시간에 따른 순서”가 있는 문제를 해결하기에 지금 수행한 행동에 대한 반응이 뒤늦게 전달될 수도 있다. (즉각적으로 전달되지 않는다.)
    
    → sequential, non i.i.d data
  - 지연된 그 시간동안 수행한 여러가지 다른 행동들중에서 어떤 것이 좋은 행동이었는지를 판단하기 어렵게 만드는 주요한 문제가 된다.
- Trial and Error
  - Predict이 아니라, 실제로 Trial; 수행해보면서 모델을 조정해나간다.
  - good action을 수행하면 enviroment로부터 good reward가 전달된다.
  - 어떻게 상을 더 많이 받을 것인지를 알아내는게 강화학습의 주요 쟁점 중 하나이다.

1.2 History of RL

Trial and Error
- 동물 행동에 대한 심리학 연구에서 출발했다.
- 심리학에서 “강화”
  동물이나 인간이 행동에 대한 결과에 따라, 다음의 행동을 변화시키고 발전시킨다는 이론(스키너 상자실험)

Delayed Reward
- optimal control : 어떤 비용함수의 비용을 최소화하도록 controler를 디자인하는것
- Bellman equation : optimal control 문제의 해결방법 [Dynamic Programming]
- MDP : Bellman이 고안한 순차 결정 문제에 대한 수학적 모델

이 2가지의 기초적인 토대로부터 강화학습이 탄생하였으며, 이후 Temporal difference Learning, Q-Learning으로 발전하다가 최근 Deep RL으로 발전하게 되었다.

*Deep Reinforcement Learning

처음에 강화학습을 배우기 시작할 때는 Grid world같이 작은 환경에서 예시 문제를 풀어볼 것이다.
그러나 실제로 게임을 학습하거나 해결하고싶은 복잡한 문제를 풀 때는 데이터의 숫자가 너무 많기 때문에 고전적인 RL을 이용해서는 제대로 학습이 되지 않는다.
따라서 데이터의 숫자를 다 일일이 Table로 저장해서 행동하는 것이 아니라 함수의 형태로 만들어서 정확하지는 않더라도 효율적으로 학습을 할 수 있게 하는 방법을 사용한다. [Approximation]

1.3 Example of RL

Playing atari with deep reinforcement learning
- 강화학습 + 딥러닝을 이용하여 Atari라는 고전게임을 학습
- Breakout 게임의 학습과정
  - 랜덤하게 Agent가 움직이다가 우연히 공을 쳐서 게임의 점수가 올라가는 것을 확인한다면, “이 행동이 나에게 보상을 주는구나!”를 학습하게되어 보상을 받은 행동을 계속 수행하게된다.
  - 이때 Agent는 단순히 즉각적인 점수만을 높이려는 것이 아니라 하나의 episode 동안 받는 점수를 최대화시키려고 한다.
    
    ⇒ 따라서 Agent는 최대한 높은 점수를 얻게 해주는 일련의 연속된 행동; 정책(Policy)을 찾아나선다.
  - 어떤 행동이 좋은 행동이고, 어떤 행동들의 조합이 좋은 정책이 되는지는 Trail and Error로 여러번 시도하보면서 학습된다.

- *논문에서 주목할 점*
    - input data로 raw pixel를 받아온 점 → CNN과의 연결
    - 같은 agent로 여러 개의 게임에 적용되어서 학습이 된다는 점
    - Deep neural network를 function approximator로 사용
    - Experience Replay
    - Target networks

2. The RL Problem

2.1 Reward

Definition of Reward

All goals can be described by the maximisation of expected cumulative reward
- with Reward Hypothesis
  
  모든 목적이 누적된 reward를 최대화하는 것으로 표현할 수 있다는 가정
- scalar feedback signal $R_t$ (with $t$ is time step)
- Indicates how well agent is doing at $t$
  
  🛠 Agent’s job is to maximise cumulative;누적 reward

Example
- Fly stunt manoeuvres in a helicopter
  - +ve reward for following desired trajectory
  - −ve reward for crashing
- Defeat the world champion at Backgammon
  - +/−ve reward for winning/losing a game
- Manage an investment portfolio
  - +ve reward for each $ in bank
- Control a power station
  - +ve reward for producing power
  - −ve reward for exceeding safety thresholds
- Make a humanoid robot walk
  - +ve reward for forward motion
  - −ve reward for falling over
- Play many different Atari games better than humans
  - +/−ve reward for increasing/decreasing score
Sequential Decision Making
- Goal : select Actions to maximise total future reward
- Problem 특징
  - Action에 대한 결과는 long term이후에 나타날 수도 있다.
  - Reward가 Delay될 수 있다.
- 가끔은 즉각적인 Reward는 포기하는 대신 long-term reward를 더 maximise하기 위한 Action을 수행할 수도 있다.
  
  → 늘 greedy 하게 local oprima만 선택하지는 않는다.
- Example
  - A financial investment (may take months to mature)
  - Refuelling a helicopter (might prevent a crash in several hours)
  - Blocking opponent moves (might help winning chances many moves from now)

2.2 Agent and Environment

At each step $t$,

The Agent’s aspect
- env로부터 Observation $O_t$를 받는다. 이때 Observation은 Agent의 action으로 인하여 변화된 환경을 나타낸다.
- env로부터 scalar reward $R_t$를 받는다.
  
  ⬇
- Action $A_t$를 수행한다.
The Environment’s aspect
- agent로부터 Action $A_t$를 받는다.
  
  ⬇
- observation $O_{t+1}$를 준다.
- scalar reward $R_{t+1}$를 준다.
  
  → $t$는 environment의 step에 따라 증가한다.

2.3 State

History
- $H_t$는 그 시간 $t$까지 있었던 모든 각각의 timestep마다 Agent가 수행한 action과 그때의 observation, reward를 순차적으로 기록한 것
- history가 결정하는 것
  - Agent는 Action을 결정한다.
  - Environment는 observation과 reward를 결정한다.
  $$ H_t = O_1,R_1,A_1, \cdots, A_{t-1},O_t,R_t $$
State
- State is the information used to determine what happens Next
- history에 대한 함수; History가 가지고 있는 정보들을 가공하여 State를 만든다.
  
  $$ S_t = f(H_t) $$
관점에 따른 State
- Environment State $S^e_t$
  - env가 Next observation과 reward를 계산하기 위해 사용한 모든 information (숫자들)
    
    Example) Atari game에서 Agent가 select한 Action에 따라 표기되는 다음 화면(=observation)을 계산하기 위해 참고하는 정보들
    *→ 공의 위치, 현재 박스의 개수 및 구조…
  - env의 state는 agent에게는 보이지 않는다. (보이더라도 너무 복잡한 정보라 활용x)
    
    Example) 우리가 게임을 플레이할 때는 컴퓨터 내부적으로 어떻게 계산되는지는 알 필요가 없다 !
- Agent State $S^a_t$
  - Agent가 Next Action을 select하기 위해 참고하는 정보들 (내가 정하는 것)
  - 실제로 통용되는 State와 동일하다.
    
    $$ S^a_t = f(H_t) $$
Information state : Markov state
- Definition
  
  A state $S_t$ is Markov *if and only if*
  
  $$ \mathbb P[S_{t+1}|S_t] = \mathbb P[S_{t+1}|S_1, \cdots, S_t] $$
- The future is independent of the past given the present
  - 과거와 미래는 독립적이다!
  - 미래를 결정할 때, 예전의 state들은 필요없이 바로 이전의 state만을 참고하여 결정한다.
    
    $$ H_{1:t} \rightarrow S_t \rightarrow H_{t+1:\infin} $$
- 즉, 이런식으로 state를 Markov하게 표현할 수 있다면, 문제를 훨씬 더 간단하게 표현할 수 있다!
- Example : Rat

    1. 최근 3가지의 signal을 state로 정의한다면, → *감전*
    2. 전체 history에서 각 signal이 등장한 횟수를 state로 정의한다면, → *치즈*

    ⇒ 즉, 어떻게 History에 대한 function을 정의하여 State를 표현하는지에 따라서 같은 데이터라 하더라도 다르게 예측할 수 있다.

Observe에 따른 State
- Fully Observability
  - Markov decision process : MDP
  - env의 state를 agent가 볼 수 있는 상황
  - Agent state = environment state = Information state
    
    $$ O_t = S^a_t = S^e_t $$
- Partially Observability
  - partially observable Markov decision process : POMDP
  - Agent state ≠ environment state
    ⇒ 따라서 Agent는 반드시 자신의 State를 표현하기 위한 방법을 구축해야한다.

    - Agent의 State 표현법 예시들…
        - Complete history : $S^a_t = H_t$
        - Beliefs of environment state : $S^a_t = (\mathbb P[S^e_t = s^1],\cdots, \mathbb P[S^e_t = s^n])$
        - Recurrent Neural network : $S^a_t = \sigma(S^a_{t-1}W_s + O_t W_o)$
    - *Example*
        - 로봇이 길을 걸을 때 카메라는, 로봇의 정확한 위치정보를 제공하지 않는다.
        - 포커를 할 때, 상대방이 가지고 있는 패와 내가 뽑게될 패에 대한 정보를 모르더라도 Action을 결정해야한다.

3. The RL Agent

대표적인 RL Agent의 구성요소

Policy : Agent’s behaviour function
Value Function : how good is each state and/or action
Model : Agent’s representation of the environment

→ Agent는 3가지의 구성요소를 모두 가지고 있을수도 있고, 하나만 가지고 있을수도 있다!

3.1 Policy

$$ \pi $$

A policy is the Agent’s behaviour
- Agent의 행동을 규정한다.
- state를 입력으로 전달하면, action을 반환한다. → state와 action을 mapping
Policy의 종류
- deterministic policy : state에 대하여 하나의 action을 정확하게 결정해서 반환한다.
  
  $$ a=\pi(s) $$
- stochastic policy : state에 대하여 여러가지 action이 가능한데, 이때 각각의 action에 대한 확률을 반환한다.
  
  $$ \pi(a|s) = \mathbb P[A_t=a|S_t=s] $$

3.2 Value Function

$$ v_\pi $$

Value function is a prediction of future reward
- 현재의 state가 얼마나 좋은지를 “평가”한다.
- 현재로부터 미래까지 받을 수있는 모든 Reward들의 합산의 기댓값으로 표현할 수 있다.
Formal 표현
- $s$ : 현재 state를 의미
- $v$ : value fuction을 의미
  
  → 이때 아래첨자 $\pi$는 Agent가 어떤 policy $\pi$를 따라서 진행한다는 것을 나타낸다.
- $\mathbb E$ : 여러가지 가능한 모든 episode가 존재하기 때문에, 기댓값을 이용하여 나타낸다.
- $\gamma$ : 미래의 Reward에 대한 가중치를 줄여서 나타내기 위한 상수값

$$ v_\pi(s) = \mathbb E_{\pi}[R_{t+1}+\gamma R_{t+2} + \gamma^2R_{t+3} + \cdots | S_t = s] $$

3.3 Model

Model predicts what the environment will do next
- Environment가 어떻게 변화할지를 예측하는 요소
- Environment의 역할(=state의 변화, reward 전달)을 Agent가 Model을 이용하여 예측해서 표현
Model의 종류
- $\mathcal P$ predicts the next state = state의 transition을 예측
- $\mathcal R$ predicts the next (immediate) reward
  
  $$ \mathcal P^a_{ss'} = \mathbb P[S_{t+1} = s' | S_t = s, A_t =a] $$
  
  $$ \mathcal R^a_{s} = \mathbb E[R_{t+1} | S_t = s, A_t =a] $$

3.4 Category of RL Agent

Policy와 Value에 따른 분류
- Value Based
  - No Policy
  - Value Function
- Policy Based
  - Policy
  - No Value Function
- Actor Critic
  - Policy
  - Value Function
Model에 따른 분류
- Model Free
  - Policy and/or Value Function
  - No Model
- Model Based
  - Policy and/or Value Function
  - Model

4. Problems within RL

4.1 Learning & Planning

[1]

강화학습 문제의 종류

(Reinforcement) Learning
- Environment는 initially unknown이다.
- Agent는 environment와 상호작용한다.
- Agent는 자신의 policy를 향상시키려고한다.
- Example with Atari
  실제로 게임의 동작과정이나 규칙을 모르는 상태에서, 실제로 Agent가 게임을 플레이하는 과정을 통하여 env와 상호작용하면서 policy가 향상되는 방향으로 학습해나간다.

Planning *(a.k.a) delibertation, reasoning, introspection, pondering, thought, search
- Environment의 Model은 known이다. (즉, Reward와 Transition을 알고있다.)
- Agent는 model을 이용하여 computation한다.
  → 실제로 environment와 상호작용하지 않고도 simulation할 수 있다.
- Agent는 자신의 policy를 향상시키려고한다.
- Example with Atari
  게임의 규칙을 알고 있어서 어떤 query emulator가 존재한다. emulator에 query를 전달하면, 그 Action에 대한 state의 transition, reward등에 대한 질문에 대답할 수 있다.

4.2 Exploitation & Exploration

Exploration finds more information about the environment
env로부터 정보를 얻는 과정
Exploitation exploits known information to maximise reward
지금까지 얻은 정보를 바탕으로 reward를 maximise할 수 있는 선택을 수행하는 과정 ⇒ It is usually important to explore as well as exploit
Example
- Restaurant Selection
  - Exploitation Go to your favourite restaurant
  - Exploration Try a new restaurant
- Online Banner Advertisements
  - Exploitation Show the most successful advert
  - Exploration Show a different advert
- Oil Drilling
  - Exploitation Drill at the best known location
  - Exploration Drill at a new location
- Game Playing
  - Exploitation Play the move you believe is best
  - Exploration Play an experimental move

4.3 Prediction & Control

Prediction
- evaluate the future, Given a policy
- policy가 주어졌을 때, 미래를 평가하는 문제
  
  ⇒ value function을 잘 학습시키는 것이 문제의 목적이다.
Control
- optimise the future, Find the best policy
- 미래를 최적화하는 문제
  
  ⇒ best policy를 찾는 것이 문제의 목적이다.
Gridworld Example
- Prediction : uniform random policy로 agent가 움직일 때, 각 칸의 value는 얼마가 될 것인가?
- (a)가 주어진 reward일 때, (b)가 prediction 문제를 푼 결과이다.

- Control : 최적$^{[1]}$ policy는 무엇이고, 최적 policy를 따르는 value function을 이용한 value는 얼마가 될 것인가?
- *(a)가 주어진 reward일 때, (b)와 (c)가 control 문제를 푼 결과이다.*

    ![](https://velog.velcdn.com/images/webb-c/post/6ff9286d-e237-49d3-a983-579766e6d134/image.png)

Reference

[선형대수학] Change of Basis

Sun, 28 Aug 2022 05:05:21 GMT

Image Compression idea

Basis의 특징

Basis는 하나의 동일한 subspace에 대하여 여러개 존재할 수 있다.

이때, subspace안의 벡터를 표현할 때 어떤 basis를 사용하여 표현하는지에 따라서 필요한 정보의 양이 달라질 수 있다. [이미지 압축의 아이디어]
Basis들은 subspace안의 모든 벡터들을 linear combination으로 표현할 수 있다.

→ 이런 basis의 특징들을 이용하여 어떤 벡터나 값을 아주 단순하게 표현하게 하는 basis를 찾을 수 있고, 현재의 복잡한 basis 대신에 단순한 basis를 이용하여 subspace를 표현하는 것이 바로 Change of Basis이다.

Example

$\mathbb R^4$상에 존재하는 벡터 $\bold v$의 간단한 표현

standard basis 표현

$$ \bold v = \begin{bmatrix} 2 \ -2 \ 2 \ -2 \end{bmatrix} = 2 \begin{bmatrix} 1 \ 0 \ 0 \ 0 \end{bmatrix} -2 \begin{bmatrix} 0 \ 1 \ 0 \ 0 \end{bmatrix} + 2 \begin{bmatrix} 0 \ 0 \ 1 \ 0 \end{bmatrix} - 2 \begin{bmatrix} 0 \ 0 \ 0 \ 1 \end{bmatrix} $$

→ 이렇게 표현하면 컴퓨터는 각 standard vector에 곱해지는 상수값 2, -2, 2, -2 (4개)와 사용하는 basis의 벡터와 그 순사를 모두 저장해야한다.

동일한 공간을 나타내는 다른 basis를 사용한 표현
- basis
  
  $\left{ \begin{bmatrix} 1 \ 1 \ 1 \ 1 \end{bmatrix},\begin{bmatrix} 1\ -1 \ -1 \ 1 \end{bmatrix},\begin{bmatrix} 1 \ 1 \ -1 \ -1 \end{bmatrix},\begin{bmatrix} 1 \ -1 \ 1 \ -1 \end{bmatrix} \right}$
- 표현
  
  $$ \bold v = 0\begin{bmatrix} 1 \ 1 \ 1 \ 1 \end{bmatrix}+0 \begin{bmatrix} 1\ -1 \ -1 \ 1 \end{bmatrix}+0 \begin{bmatrix} 1 \ 1 \ -1 \ -1 \end{bmatrix}+2\begin{bmatrix} 1 \ -1 \ 1 \ -1 \end{bmatrix} $$
  
  → 이렇게 표현하면 사용하는 벡터가 1개 뿐이므로, 사용되는 벡터와 거기에 곱해지는 상수값 2만 저장하면 된다.
  
  ⇒ standard basis를 이용하여 표현 했던 것보다 훨씬 간단하게(=저장용량을 적게 사용하도록) 표현할 수 있다!

Image Compression Idea

$1024\times 1024$ pixel의 gray image($255$)를 나타내는 벡터 $\bold x ∈ \mathbb R^{1024^2}$. 이때 벡터 $\bold x$의 각각의 픽셀 $x_i$는 $0 -255$ 사이의 값(=$1$byte로 표현가능)을 가진다.

각각의 픽셀 값을 모두 저장하려면 $1024^2$개의 픽셀 값을 저장하기 위한 공간이 필요하다.

→ $1024^2$ byte 필요
Image Compression
- 각각의 픽셀이 모두 검은색인 어떤 imgae를 저장한다고 가정해보자.
- 아무런 처리과정을 거치지 않고 저장한다면 $1024^2$개 픽셀값에 모두 $255$(=black)값이 저장되어 $1024^2$ byte를 이미지 표현에 사용하게된다.
  
  $$ 255\begin{bmatrix} 1 \ 0 \ \vdots \ 0 \end{bmatrix}+255 \begin{bmatrix} 0\ 1 \ \vdots \ 0\end{bmatrix}+\cdots +255\begin{bmatrix} 0 \ 0 \ \vdots \ 1 \end{bmatrix} $$
- 만약, 앞에서 보인 예시처럼 standard basis를 이용하여 이미지를 표현하지 않고 다른 basis를 사용하면 어떻게 될까?
- 벡터$[1,1,...,1]^T$를 가지는 어떤 basis를 사용하여 이미지를 표현하면 다음과 같이 나타낼 수 있다.
  
  $$ 255\begin{bmatrix} 1 \ 1 \ \vdots \ 1 \end{bmatrix}+0 \begin{bmatrix} 1\ -1 \ \vdots \ -1\end{bmatrix}+\cdots +0\begin{bmatrix} -1 \ -1 \ \vdots \ -1 \end{bmatrix} $$
- 0 이 곱해지는 의미없는 벡터는 무시하고, 의미있는 상수값 255가 곱해지는 벡터만을 컴퓨터가 저장하면 훨씬 작은 저장공간을 사용하면서 같은 이미지를 저장할 수 있게 된다.

→ standard basis의 결합으로 이미지를 표현하지 말고 다른 basis로 표현하면 저장공간을 아낄 수 있다.

*JPEG?

표준 이미지 형식 JPEG는 이미지를 각각의 $8\times 8$ block으로 나눈다.

(이미지 전체를 계산하기에는 계산양이 너무 많기 때문에 고안한 방식)

Discrete Wavelet Transform; DWT

Discrete Wavelet Transform

아래의 Othogonal basis는 실제로 JPEG2000에서 사용하는 basis이다.
영벡터가 아닌 직교벡터 8개는 서로 독립이므로 아래의 벡터들은 $\mathbb R^8$의 basis이다.

$$ \begin{bmatrix} 1 \1 \1\1\1\1\1\1 \end{bmatrix},\begin{bmatrix} 1 \1 \1\1\-1\-1\-1\-1 \end{bmatrix},\begin{bmatrix} 1 \1 \-1\-1\0\0\0\0 \end{bmatrix},\begin{bmatrix} 0 \0 \0\0\1\1\-1\-1 \end{bmatrix},\begin{bmatrix} 1 \-1 \0\0\0\0\0\0 \end{bmatrix},\begin{bmatrix} 0 \0 \1\-1\0\0\0\0 \end{bmatrix},\begin{bmatrix} 0 \0 \0\0\1\-1\0\0 \end{bmatrix},\begin{bmatrix} 0 \0 \0\0\0\0\1\-1 \end{bmatrix} $$

💡 이처럼, orthogonal basis를 basis로 고르는 것이 가장 좋은 방법이다. (why?)

Interpretation of Harar Wavelet Basis

$\mathbb R^4$으로 생각해보기 - Harar Matrix 이해하기

$\mathbb R^4$의 Othogonal basis는 다음과 같다.

$$ \begin{bmatrix} 1 \ 1\ 1\ 1 \end{bmatrix} , \begin{bmatrix} 1 \ 1\ -1\ -1 \end{bmatrix} ,\begin{bmatrix} 1 \ -1\ 0\ 0 \end{bmatrix} ,\begin{bmatrix} 0 \ 0\ 1\ -1 \end{bmatrix} $$
다음 vector $\bold x$를 Othogonal basis로 표현 해보자.

$$ \bold x =\begin{bmatrix} 100 \ 100\ 101\ 101 \end{bmatrix} $$

$$ =\begin{bmatrix} 100 \ 100\ 101\ 101 \end{bmatrix} = 100.5 \times \begin{bmatrix} 1 \ 1 \ 1\ 1 \end{bmatrix} + (-0.5) \times \begin{bmatrix} 1 \ 1 \ -1\ -1 \end{bmatrix} + 0 \times \begin{bmatrix} 1 \ -1 \ 0\ 0 \end{bmatrix} + 0 \times \begin{bmatrix} 0 \ 0 \ 1\ -1 \end{bmatrix} $$
- 첫번째 basis 벡터에는 벡터 $\bold x$ 요소들의 평균값을 곱한다.
  
  $$ \frac{\sum_{i=1}^4 x_i}{4} = \frac{(x_1 + x_2 + x_3 + x_4) - 0}{4} $$
- 두번째 basis 벡터는 $\bold x$를 반으로 나눴을 때($x_1, x_2$ / $x_3, x_4$)위 요소의 합과 아래요소 합의 차이의 평균을 곱한다.
  
  (이때 나누는 기준은 vector의 값이 1 → -1로 변하는 위치이다)
  
  $$ \frac{(x_1 + x_2) - (x_3 + x_4)}{4} $$
- 세번째 basis 벡터는 첫번째 요소와 두번째 요소 차이의 평균을 곱한다.
  
  $$ \frac{x_1 - x_2}{2} $$
- 네번째 basis 벡터는 세번째 요소와 네번째 요소 차이의 평균을 곱한다.
  
  $$ \frac{x_3 - x_4}{2} $$

→ basis 벡터에서 0이 아닌 요소만을 고려했을 때, 값이 **음수**인 부분과 **양수**인 부분 각각의 합의 차이의 **평균값**이 각 basis 벡터에 곱해지는 상수 값이 된다.

$$
\frac{\text{양수인 요소들의 합 - 음수인 요소들의 합}}{\text{0이아닌 요소의 개수}}
$$

벡터 $\bold x$를 압축시킬 수 있는 벡터 $\bold c$ 구하기
- 벡터 $\bold c$는 $\bold x$를 압축시키기 위해 basis에 곱해지는 상수값들의 집합
- $W$는 $\bold w_i$를 column vector로 갖는 basis를 의미한다.
  
  $$ \bold x= c_1\bold w_1 + ... + c_4 \bold w_4 = [\bold w_1 \cdots \bold w_4] \begin{bmatrix} c_1 \ \vdots \ c_4 \end{bmatrix} = W\bold c $$
- 따라서 위 수식을 다르게 표현하면 다음과 같이 벡터 $\bold c$를 나타낼 수 있다.
  
  ($W$는 서로 independence한 column vector로 이루어져 있기에, 역행렬을 갖는다.)
  
  $$ \bold c = W^{-1}\bold x $$
- $\bold c$의 의미
  
  $\bold x$를 $W$basis를 이용한 좌표계상의 좌표로 표현한 것이 바로 $\bold c$이다.
  
  이렇게 표현한 $\bold c$에서는 데이터를 저장할 때 사용되는 용량을 줄이기 위해서 정보량이 가장 위쪽으로 쏠리도록 구성하는 것이 일반적이다. (0은 저장하지 않기 때문)

loseless압축과 lossy압축

loseless

손실없는 압축이라는 의미
- 0을 제외한 $\bold c$의 값들을 그대로 저장한다.
- 압축된 이미지를 클릭하는 순간 압축파일 $\bold c$ 왼쪽에 basis $W$를 곱해지면서 원본이미지를 그대로 복원할 수 있다.
  
  $$ W\bold c = WW^{-1}\bold x = \bold x $$
lossy
- 0을 제외한 $\bold c$의 값 중에서 특히 0과 가까운 값은 근사하여 0으로 취급하여 저장한다.
  
  → 0으로 근사된 값은 저장하지 않음
- 이렇게 압축을 했다가 복원하면 미세한 색의 차이가 1가지 색으로 뭉뚱그러지기때문에 약간의 손실이 발생한다.

Conditions for Good Basis

좋은 basis 선택의 조건

빠른 계산이 가능해야한다.

→ DWT에서는 역행렬을 $W^{-1} = W^T$로 표현할 수 있기 때문에 빠른 계산이 가능하다.
압축시 메모리 공간을 적게 차지하게 하는 basis를 선택해야한다.

응용

이미지는 기본적으로 2-D matrix형태이므로, 행렬에 대해서 압축을 하기 위해서는 Haar matrix가 필요하다.

Haar Wavelet Transform

최초의 DWT 변환 (변환방법의 한 종류임)

Kronecker Product

$m\times n$ 행렬 $A$와 $p\times q$ 행렬 $B$에 대하여 $A$의 각각의 요소에 모두 행렬 $B$를 곱하는 연산자.
연산결과는 $mp\times nq$ 행렬이 된다.
$A\otimes B$

$$ A \otimes B = \begin{bmatrix} a_{11}B & a_{12}B & \cdots & a_{1n} \a_{21}B & a_{22}B & \cdots & a_{2n}\ \vdots & \vdots & \ddots & \vdots \ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{bmatrix} $$
$A$와 $B$가 둘다 벡터라면, 이 연산은 외적과 동일하다.

Haar Matrix

$n=2^t (t=0,1,2,...)$인 $n\times n$행렬 $H_n$은 다음과 같이 정의된다.

($I_m$은 $m\times m$ identity matrix를 의미한다.)

$$ H_n = \begin{cases} \left[ H_m \otimes \begin{bmatrix} 1 \ 1 \end{bmatrix} \ \ I_m \otimes \begin{bmatrix} 1 \ -1 \end{bmatrix} \right] & \text{if } n=2m\ \left[ 1 \right ] & \text{if }n=1 \end{cases} $$

→ 이렇게 정의된 Haar Matrix에서 각각의 column vector를 column vector의 크기로 나누어 정규화:normalize 해서 사용한다.

Example of Haar Matrix

$$ H_2 = \begin{bmatrix}1 & 1 \ 1 & -1 \end{bmatrix} $$

$$ H_4 = \begin{bmatrix}1 & 1 & 1 & 0\ 1 & 1 & -1 & 0 \ 1 & -1 & 0 & 1 \ 1 & -1 & 0 & -1 \end{bmatrix} $$

$$ H_8 = \begin{bmatrix}1 & 1 & 1 & 0 & 1 & 0 & 0 & 0\ 1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 \ 1 & 1 &-1 & 0 & 0 & 1 & 0 & 0\ 1 & 1 &-1 & 0 & 0 & -1 & 0 & 0 \ 1 & -1 &0 & 1 & 0 & 0 & 1 & 0 \ 1 & -1 &0 & 1 & 0 & 0 & -1 & 0 \ 1 & -1 &0 & -1 & 0 & 0 & 0 & 1 \ 1 & -1 &0 & -1 & 0 & 0 & 0 & -1 \end{bmatrix} $$

Haar Wavelet Transforms : 2-D DWT

$n\times n$ matrix $A$가 $n \times n$ pixel의 gray image를 나타낸다. ($n = 2^t$)
$H_n$이 정규화된 Harr Matrix라고 하자.
- 정규화된 Harr Matrix는 Orthogonomal matrix이다.
- $\bold h_i$ 는 $H_n$의 $i$번째 column vector
$H_n^TH_n = I_n$ 임을 Orthogonal 행렬의 성질으로부터 알아낼 수 있고 이를 활용하여 나타낼 수 있다.

→ Orthogonal matrix는 역행렬이 전치행렬과 동일하다.
이미지 파일을 압축하기 위해서는 original image matrix $A$의 왼쪽에는 $H_n^T$를 오른쪽에는 $H_n$을 곱해줘서 압축한다.

$$ B = {H_n}^T A H_n = \begin{bmatrix} \bold {h_1}^TA\bold h_1 & \bold {h_1}^TA\bold h_2 & \cdots & \bold {h_1}^TA\bold h_n \ \bold {h_2}^TA\bold h_1 & \bold {h_2}^TA\bold h_2 & \cdots & \bold {h_2}^TA\bold h_n \ \vdots & \vdots & \ddots & \vdots \ \bold {h_n}^TA\bold h_1 & \bold {h_n}^TA\bold h_2 & \cdots & \bold {h_n}^TA\bold h_n\end{bmatrix} $$

Haar Wavelet Transforms의 특징

정보량이 Left-Top으로 모인다. (아래쪽에는 0)
- 전체 pixel의 평균값을 나타내는 성분 $\bold {h_1}^TA\bold h_1$이 $B_{11}$에 위치한다.
- 또한 $B_{nn}$으로 갈수록 적은 픽셀간의 차이만 나타내기 때문에 0에 가까운 값을 가지게 된다.
이 특징을 이용해서 압축 matrix $B$에서 데이터가 많이 모여있는 부분만 저장하고 다시 압축을 풀면, 차이는 있겠지만 여전히 $A$와 비슷한 이미지를 띈다.

$$ \hat A = H_n \hat B {H_n}^T $$

Orthonomal matrix

Orthogonal + nomalize

Orthonomal matrix

$n\times n$ matirx $Q = [\bold q_1,\ \bold q_2, \cdots , \ \bold q_n]$ 에서 각 column 벡터가 다음 성질을 만족하면 Orthonomal matrix이다.

$$ \bold{q_i}^T\bold{q_j} = \begin{cases} 1 & (i=j) \ 0 & (i \neq j)\end{cases} $$

$i=j$ 일 때, $1$ → 각 열벡터들의 자기자신의 내적이 $1$이므로 이는 column vector가 길이가 1인 nomal vector라는 것을 의미한다.
$i≠j$ 일 때, $0$ → 각 열벡터들간의 내적이 $0$이므로 서로 직교(Orthogonal)관계라는 것을 의미한다.

💡 따라서 행렬 $Q$는 각 열벡터의 길이가 1이고 서로 직교인 열벡터들로 이루어져 있다.

Orthogonomal 행렬의 역행렬이 전치행렬과 같은 이유

Orthogonomal matrix $Q$에 대하여,

$Q^TQ$를 계산하면 Orthogonomal 행렬의 정의에 의해 항등행렬이 결과로 나타나게 된다.

$$ \bold{q_i}^T\bold{q_j} = \begin{cases} 1 & (i=j) \ 0 & (i \neq j)\end{cases} $$

$$ Q^TQ = \begin{bmatrix} \bold{q_1}^T \ \vdots \ \bold{q_n}^T\end{bmatrix} \begin{bmatrix} \bold{q_1} & \cdots & \bold{q_n}\end{bmatrix}\\ \ = \begin{bmatrix} \bold {q_1}^TA\bold q_1 & \bold {q_1}^T\bold q_2 & \cdots & \bold {q_1}^T\bold q_n \ \bold {q_2}^T\bold q_1 & \bold {q_2}^T\bold q_2 & \cdots & \bold {q_2}^TA\bold q_n \ \vdots & \vdots & \ddots & \vdots \ \bold {q_n}^T\bold q_1 & \bold {q_n}^T\bold q_2 & \cdots & \bold {q_n}^T\bold q_n\end{bmatrix} $$

$$ Q^TQ = I $$

→ 따라서 $Q^{-1} = Q^T$ 이다.

[선형대수학] Orthogonality

Sun, 28 Aug 2022 02:22:57 GMT

Orthogonality

Definition of Orthogonal Vectors

Two vectors $\bold{v}$ and $\bold{w}$ are said to be orthogonal if their inner product is zero. ($\bold v^T \bold w = 0$)

→ 두 벡터의 내적이 0일 때, 두 벡터는 직교한다.

orthogonal의 의미 : $\cosθ$가 0이다.

두 벡터가 이루는 각 $\theta$ 에 대해 $\cos \theta$를 계산하는 수식은 다음과 같은데, 이때 두 벡터의 내적이 $0$이기 때문에 $\cos \theta = 0$ 이 된다.

$\cos \theta = 0$이 되게하는 $\theta$는 $\pi \over 2$ [직교]

$$ \cos \theta = \frac{\bold v \cdot \bold w}{||\bold v|| \ ||\bold w||} = 0 $$
Example of Orthogonal Vectors

$$ \begin{bmatrix} 1 \ 2 \end{bmatrix} \text{ and }\begin{bmatrix} -2 \ 1 \end{bmatrix} $$

Orthogonal 관계인 Vector and Subspace

어떤 subspace $S$에 들어있는 모든 벡터와 벡터 $\bold v$가 수직일 때, Subspace $S$와 벡터 $\bold v$가 orthogonal하다.

$$ \bold v⊥S \ \text{if }\ \bold v^T \bold w = 0\ (∀ \bold w∈S) $$

Definition of Orthogonal Subspaces

Orthogonal 관계인 Vector and Subspace의 표현을 확장시켜서 정의할 수 있다.

Two subspaces $S_1$ and $S_2$ are said to be orthogonal, if $\bold v$ and $\bold w$ are orthogonal for all $\bold v \in S_1$, $\bold w \in S_2$

→ $S_1$에 포함된 모든 벡터와 $S_2$에 포함된 모든 벡터가 수직(orthogonal)일 때 $S_1$과 $S_2$는 직교한다.

$$ S_1 ⊥ S_2\ \text{if} \ \bold v^T \bold w =0\ (\forall \bold v \in S_1, \forall \bold w \in S_2) $$

Example of Orthogonal Vectors

$$ S_1 = \left{ c \begin{bmatrix} 1 \ 2 \end{bmatrix}, \ \forall c \in \mathbb R \right} \text{ and }S_2 = \left{ c \begin{bmatrix} -2 \ 1\end{bmatrix}, \ \forall c \in \mathbb R \right} $$

Dimension과 orthogonal의 관계

Dimension과 orthogonal의 관계

Subspace $S_1$ and $S_2$ of $\mathbb R^n$ cannot be orthogonal when $\dim(S_1) + \dim(S_2) > n$

→ $\mathbb R^n$의 subspace $S_1$과 $S_2$에서 $\dim(S_1) + \dim(S_2) > n$ 을 만족하면, $S_1$과 $S_2$는 직교관계를 가질 수 없다.

Dimension의 의미 3차원 공간 ($\mathbb R^3$)의 subspace인 평면($\dim = 2$) $S_1$과 $S_2$를 가정하자. Orthogonal의 정의에 의해, 두 subspace가 orthogonal하기 위해서는 해당 subspace안에 속하는 어떤 벡터에 대해서도 직교해야하는데, 이를 만족하지 못한다. → 따라서 두 subspace는 orthogonal하지 않는다.
이때 위에서 정의한 관계식에 각 값을 대입하면 다음과 같이 두 subspace의 dimension의 합이 기존 space의 차원보다 크다.

$$ \dim(S_1) + \dim(S_2) = 4 > 3 $$

Otrhogonality of Four Fundamental Supspace

Orthogonality of $C(A^T)$ and $N(A)$

$$ C(A^T)\ ⊥\ N(A) $$

$A$의 row space와 nullspace는 서로 직교관계이다.
증명 * $A$가 $m\times n$ 행렬일 때, 두 부분공간은 $\mathbb R^n$의 subspace이다.
1. $C(A^T)$에 포함되는 벡터 $\bold v$와 $N(A)$에 포함되는 벡터 $\bold w$가 있다
  
  $$ \bold v \in C(A^T),\ \bold w \in N(A) $$
2. $\bold v=A^T \bold y를$ 만족하는 벡터 $\bold y$를 가정하자.
3. 벡터 $\bold v$의 위치에 위에서 정의한 표현을 대입하면 다음과 같이 나타난다.
  - $\bold v \in C(A^T)$이므로, $A^T \bold y$ 로 표현할 수 있다.
  - $\bold w \in N(A)$이므로, $A\bold w = 0$ 이다.
    
    $$ \bold v^T \bold w = (A^T \bold y)^T \bold w = \bold y^TA \bold w =\bold y^T \cdot \bold 0 = 0 $$
    
    → 따라서 $\bold v^T \bold w = 0$ 이므로, 두 subspace에 속하는 모든 임의의 벡터들끼리 서로 직교관계임을 보일 수 있다.
NullSpace의 의미
- $N(A)$는 원래 행렬 $A$의 row에 직교하는 모든 벡터들을 모아둔 subspace이다.
- $A\bold x = 0$에서 각각의 row vector $\bold a^T$에 곱해지는 $\bold x$의 결과가 $0$이므로 다음과 같이 해석할 수 있다.
  
  $$ \bold a^T \bold x = 0 $$
- 의미자체가 이렇다보니 $A$의 row들의 linear combination한 space인 $C(A^T)$와도 orthogonal하게 된다.

Orthogonality of $C(A)$ and $N(A^T)$

$$ C(A^T)\ ⊥\ N(A) $$

$A$의 column space와 left nullspace는 서로 직교관계이다.
row space와 nullspace간의 orthogonality 증명 과정을 $A^T$기준으로 진행하면 쉽게 증명할 수 있다.

Orthogonal Complement : 직교여집합

Definition of Orthogonal Complement

The orthogonal complement of a subspace $S$, contains every vector that is perpendicular to $S$.

→ 직교 여집합은 어떤 Subspace $S$와 직교하는 모든 벡터들의 집합이다.

직교 여집합의 표현

$$ S^⊥ $$

Orthogonal Complement of Four Fundamental Supspace

Four Fundamental Supspace은 단순 직교관계가 아닌 직교 여집합 관계를 만족한다.

Orthogonal Complement of Nullspace and Row space

$m\times n$ 행렬 $A$에 대하여

$C(A^T)$ and $N(A)$ are orthogonal complements of each other in $\mathbb R ^n$

$$ N(A) = C(A^T)^⊥ $$

$N(A)$의 정의에 의하여 성립한다.
- $N(A)$는 모든 row 벡터와 직교한 벡터들의 집합이다.
- 따라서 row 벡터에 대한 직교 여집한관계가 성립한다.
두 부분공간은 서로 직교하며, 현재 차원에서 자신의 차원을 뺀만큼의 차원을 상대방이 가지기 때문에 직교 여집합 관계를 만족할 수 밖에 없다.
- $n- \dim(C(A^T)) = \dim(N(A))$
- $n- \dim(N(A)) = \dim(C(A^T))$
  
  $$ \dim(C(A^T))+\dim(N(A)) = n $$

Orthogonal Complement of Column space and Left Nullspace

$m\times n$ 행렬 $A$에 대하여

$C(A)$ and $N(A^T)$ are orthogonal complements of each other in $\mathbb R ^m$

$$ C(A^T) = N(A)^⊥ $$

증명 [귀류법]
1. $N(A)$에 직교하지만, $C(A^T)$에 포함되지 않는 어떤 벡터 $\bold v$를 가정하자.
  
  $$ \bold v ⊥ N(A),\ \ \bold v \notin C(A^T) $$
2. 이 벡터 $\bold v$를 $A$의 행에 추가하여 행렬 $B$를 얻을 수 있다.
  
  $$ B = \begin{bmatrix} A \ \bold v^T\end{bmatrix} $$
3. 이때 새로 정의된 행렬 $B$의 nullspace는 기존 행렬 $A$의 nullspace와 동일하다.
  
  → nullspace는 변하지 않는다.
  1. $A\bold x = 0$ 일 때 $\bold x \in N(A)$이다 .
  2. 이때 행렬 $B$에 대해서 $B \bold x = 0$이 성립한다면, $\bold x \in N(A) \sub N(B)$를 만족한다.
    - $A\bold x = 0$ (자명)
    - $\bold v ⊥ N(A)$이므로 $\bold v^T\bold x = 0$
      
      $$ B\bold x = \begin{bmatrix} A\bold x \ \bold v ^T \bold x \end{bmatrix} = \begin{bmatrix} 0 \ 0 \end{bmatrix} = 0 $$
      
      → 따라서 $N(A) \sub N(B)$ - (1)
  3. 행렬 $B$를 정의할 때, 기존 행렬 $A$에 새로운 행을 추가시켜서(차원증가) 조건이 추가되었기에 $N(B) \sub N(A)$ - (2)
  4. 1번과 2번 조건을 모두 만족하는 것은 두 subspace가 동일한 경우이다.
    
    $$ N(A) = N(B) $$
4. $B$행렬은 $A$에 비해서 새로운 행이 하나 더 추기되었기 때문에 랭크의 갯수가 1개 더 많다.
  
  $$ r(B) = r(A) +1 $$
5. 랭크와 차원의 관계를 이용하여 다음과 같은 계산과정을 거칠 수 있다.
  - $N(A) = N(B)$이기 때문에 다음을 만족
    
    $$ \dim(N(B)) + \dim(C(B^T)) = n $$
    
    $$ \dim(N(A)) + \dim(C(B^T)) = n $$
  - 차원을 Rank로 표현
    
    $$ n-r(A) + r(B) = n $$
    
    $$ n - r(A) + r(A) + 1 = n $$
    
    $$ n - \cancel{(r(A))} + \cancel{(r(A))} + 1 = n $$
    
    → $n+1 = n$ [모순]
6. 따라서 처음 가정이 틀렸음을 보일 수 있다.

Orthogonality and Independence

$n$ Independent Vectors in $\mathbb R^n$

Any $n$ independent vectors in $\mathbb R^n$ must span $\mathbb R^n$. So they are a basis.

→ $\mathbb R^n$ 안에서 $n$개의 독립적인 벡터(=basis)는 $\mathbb R^n$ 을 span한다.

Any $n$ vectors in $\mathbb R^n$ that span $\mathbb R^n$ must be independent. So they are a basis.

→ ↔ $\mathbb R^n$ 을 span하는 $n$개의 벡터(=basis)는 서로 독립이다.

$n$ Independent Vectors in $\mathbb R^n$ (Matrix)

If the $n$ columns of $A$ are independent, they span $\mathbb R^n$. So $A\bold x = b$ is always solvable.
- 만약 $A$의 $n$개의 열이 독립이라면, $\mathbb R^n$을 span한다.
- 따라서 $A\bold x=b$의 해는 항상 존재한다.
  
  → $A$의 열의 linear combination으로 공간 안의 어떤 벡터도 표현가능하다.
If the $n$ columns of $A$ span $\mathbb R^n$, they are independent. So $A\bold x = b$ has a unique solution.
- 만약 $A$의 $n$개의 열이 $\mathbb R^n$을 span하면 서로 독립이다.
- 따라서 $A\bold x=b$의 해는 항상 존재한다.

Orthogonality and Independence

Orthogonal한 subspaces들의 basis

벡터 $\bold v_1, \bold v_2, \cdots, \bold v_r$이 subspace $S∈\mathbb R^n$의 basis이고 $\bold v_{r+1}, \bold v_{r+2} , \cdots , \bold v_n$이 subspace $T∈\mathbb R^n$의 basis일 때,

→ $S$와 $T$가 직교관계이면 벡터 $\bold v_1, \bold v_2, ..., \bold v_n$은 $\mathbb R^n$의 basis이다.
Q) 벡터들이 직교관계이면 해당 벡터들은 독립인가?
- 벡터 중에 영벡터가 들어있다면 직교관계는 만족한다.
- 하지만 영벡터가 존재하면 독립관계는 성립하지 않는다.
  
  → 따라서 항상 직교라고 독립조건을 만족하는 것은 아니다.

Combining Bases from $C(A^T)$ and $N(A)$

Combining bases from $C(A^T)$ and $N(A)$ to form a basis of $\mathbb R^n$

위 정리에 의해 $C(A^T)$ 와 $N(A)$ subspace를 모은 것이 $\mathbb R^n$의 basis임을 알 수 있다.
- $\dim(C(A^T)) + \dim(N(A)) = n$
  - $\dim(C(A^T)) = r$
  - $\dim(N(A)) = n-r$
- $C(A^T)⊥N(A)$
  
  → 위 정리의 두가지 조건을 모두 만족하기 때문
$\mathbb R^n$에 속하는 어떤 벡터 $\bold x$를 서로 직교관계인 두 벡터로 나눌 수 있다.

$$ \bold x = \bold x_r + \bold x_n $$
- $C(A^T) = { \bold v_1, \bold v_2, \cdots , \bold v_r}$ → $\bold x_r$
- $N(A) = {\bold v_{r+1}, \bold v_{r+2}, \cdots, \bold v_n}$ → $\bold x_n$
- ⇒ 특히 row space에 속하는 벡터와 nullspace에 속하는 벡터로 표현할 수 있다.*

[C++] 상속 : 응용

Tue, 23 Aug 2022 01:36:39 GMT

1.객체 포인터의 참조관계

01-객체 포인터 변수란?

객체의 주소값을 저장하는 포인터 변수

포인터는 어떤 변수의 주소값을 저장하는 변수이다.
따라서 클래스를 기반으로 생성된 객체의 주소값 저장을 위해-객체를 가리키기 위하여 해당 클래스의 타입으로 포인터 변수를 선언할 수 있다.
객체 포인터 변수의 선언 및 참조

    Person* ptr;          //Person class의 객체를 가리키기 위한 ptr 포인터변수
    ptr = new Person();   //포인터 변수의 객체 참조

02-객체 포인터 변수의 특성

C++에서 객체 포인터 변수는 가리키는 객체 뿐만 아니라, 그 클래스를 직접/간접 상속하는 자식 클래스의 객체도 가리킬 수 있다.

//Person을 직접 상속하는 Student
class Student : public Person {
    ...
};

//Person을 간접 상속하는 High_Student
class High_Student : public Student {
        ...
};

int main(){
    Person* ptr;          //Person class의 객체를 가리키는 ptr 포인터변수
    ptr = new Student(); 
        ptr = new High_Student();  
}

Q.이런 특성을 갖게 되는 이유는 무엇일까?

그 해답은 상속의 의미로부터 찾을 수 있다.

상속의 관계는 IS-A(~는 ~이다.)의 관계로 표현되는데, 따라서 Person을 상속받는 Student에서 상속의 관계는 “Student는 Person이다.”로 표현되는데, 이는 클래스와 해당 클래스로 만들어진 객체간의 관계와 유사하다.

클래스-객체 관계 : Vaughan(객체)은 Person(클래스)이다.
부모클래스-자식클래스 관계 : Student(자식)은 Person(클래스)이다.
→ 두 관계의 의미가 유사하다.

이러한 상속의 관계때문에 Person의 포인터 변수는 Student객체를 Person 객체의 일종으로 간주하게 된다.

2. 가상함수 : Virtual Function

01-C++ 컴파일러의 포인터 객체 참조 연산의 특성

객체포인터의 특성을 이용하면 우리는 쉽게 하나의 포인터를 이용해 부모/자식 객체에 편하게 접근할 수 있지만, 한가지 단점이 존재한다.
C++ 컴파일러는 포인터 연산의 가능 유무를 판단할 때 포인터의 자료형을 기준으로 판단하며, 실제 포인터 변수가 가리키는 객체의 자료형은 고려하지 않는다.

따라서 실제로 객체 포인터가 가리키는 객체의 자료형이 Student 클래스라도, 객체 포인터의 자료형이 Person 클래스라면 자식 클래스인 Student만 가지는 멤버에는 접근할 수 없다 !

02-객체 포인터 변수를 이용해 참조할 때 발생할 수 있는 오류 (예시)

Person 클래스 타입으로 정의한 객체 포인터 변수를 사용하여 자식 클래스인 Student의 객체를 사용한다.
이때, 가리키는 객체는 Studnet 타입이라도 포인터 변수가 정의된 자료형은 Person 클래스이기 때문에, 포인터 변수를 이용하여 객체를 참조할 때 마치 Person 클래스의 객체를 참조하는 것처럼 동작한다.
- Student만이 가지는 멤버 변수/함수에 접근할 수 없다.
- Student에서 재정의했던 Person의 함수를 호출하지 않고, Person에서 정의했던 기존 함수를 사용

#include
using namespace std;

class Person {
        private:
                char name[10];
        public:
                Person(char* name) {
                        strcpy(this->name, name);
                }
                void ShowInfo() const {
                        cout<<"name: "<GetNumber();   //컴파일 오류
    ptr->ShowInfo();      //오버라이딩 이전의, Person 클래스에 정의된 기존 함수를 사용함 
    return 0;
}

03-가상 함수의 의미 및 사용

virtual 키워드를 이용하여 가상함수로 선언된 함수는 포인터 변수를 이용하여 함수를 호출할 때 포인터 변수의 자료형을 기반으로 결정하지 않고 실제로 가리키는 객체를 참조하여 호출대상을 결정한다.

가상함수 또한 함수의 body를 가질 수 있다.
가상함수를 오버라이딩 하는 함수(=자식클래스에서 재정의한 함수)또한 (별도로 virtual 선언을 추가하지 않더라도,) 가상함수로 정의된다.
가상함수의 사용 예시

    #include 
    using namespace std;

    class First {
        public:
            virtual void MyFunc() { cout<<"FirstFunc"<MyFunc();
        sptr->MyFunc();
        fptr->MyFunc();

        delete tptr;
        return 0;
    }

04-순수 가상함수(pure virtual function)와 추상클래스(abstract class)

추상클래스

실제로 객체생성은 하지 않고, 상속만을 위해 정의된 클래스
- 객체 생성을 목적으로 정의되지 않는 클래스
- 이렇게 아무런 기능을 하지 않는 추상클래스를 실수로 생성했을 때, 문법적으로는 아무런 오류가 발생하지 않기 때문에 생성도지 않도록 막아두는 것이 좋다.
- → 이를 위해 순수 가상함수가 사용된다.*
순수 가상함수

함수의 몸체가 정의되지 않은 함수
- 순수 가상함수는 =0 으로 표현한다.
```
  // 추상 클래스
  class Employee {
          private:
                  char name[100];
          public:
                  Employ(char* name) {
                          strcpy(this->name, name);
                  }
                  void ShowYourname() const {
                          cout<<"name: "<
```





05-다형성(Polymorphism)

C++에서 가상함수의 호출단계에서 보이는 특성을 가리켜, ‘다형성'이라고 한다.
모습은 같은데(=명령문은 동일한데) 형태는(=결과는) 다르다.  
→ 동일한 포인터 변수라도, 참조하는 객체의 자료형에따라 그 결과가 달라진다.*




06-멤버함수와 가상함수의 동작원리

멤버변수와 멤버변수

어떤 클래스의 객체가 생성되면 멤버변수는 실제로 그 객체 안에 존재한다.
그러나 멤버함수는 메모리의 한 공간에 별도로 위치하고, 해당 클래스로 생성된 모든 객체가 그 멤버함수를 서로 공유하는 형태를 취한다.  


가상함수의 동작원리

1개이상의 가상함수를 포함하는 클래스에 대해서는 컴파일러가 가상함수 테이블을 만든다.

가상함수 테이블은 실제 호출되야할 함수의 위치정보(=주소)를 담고 있는 테이블이다.

이때 오버라이딩 된 가상함수의 주소정보는 자식클래스의 테이블에 포함되지 않는다.
  → 따라서 오버라이딩 된 가상함수를 호출하면 자동적으로 가장 마지막에 오버라이딩 한 자식 클래스의 멤버함수가 호출되는 것이다. 

가상함수 테이블의 예시
AAA를 상속받은 자식클래스 BBB의 V-table



key
value



void BBB::Func1()
0x1024


void AAA::Func2()
0x2048


void BBB::Func3()
0x4096









07-가상함수 테이블이 참조되는 방식

가상함수 테이블은 멤버함수 호출에 쓰이는 일종의 데이터이기 때문에, 객체가 생성되지 않더라도 일단 메모리 공간에 할당된다.
각 클래스의 객체에는 해당 클래스의 가상함수 테이블의 주소값이 저장된다.
참조 과정
객체를 통해 어떤 가상함수가 호출되었다.
가상함수가 어디에 위치한지 파악하기 위해 가상함수 테이블이 저장된 주소를 이용해 참조된다.
참조된 가상함수 테이블에서 저장된 가상함수의 주소로 향해 가상함수를 수행한다.






+ 객체 포인터 변수와 가상함수의 활용 (예제)
프로그램 설명 및 상속관계
어떤 회사의 전체 직원에게 제공하는 급여를 계산하고 관리하고자한다.

직원 종류
정규직 : 정해진 월급을 받는다.
임시직(알바) : 일한시간 * 시간당급여 로 계산된 급여를 받는다.
영업직 : 정해진 월급 + 판매실적*상여금비율 로 계산된 급여를 받는다.


클래스의 상속관계
→ 이때 Employee는 실제로 객체생성되지 않고 상속을 위해 정의된 추상클래스이다.


예제 코드
#include 
#include 
using namespace std;

class Employee {
    private:
        char name[100];
    public:
        Employee(char* name){
            strcpy(this->name, name);
        }
        void ShowYourName() const {
            cout<<"name: "<ShowSalaryInfo();
        }
        void ShowTotalSalary() const {
            int sum=0;
            for(int i=0 ; iGetPay();
            cout<<"salary sum: "<AddWorkTime(5);
    handler.AddEmployee(alba);

    //영업직 등록
    SalesWorker* seller = new SalesWorker("Hong", 1000, 0.1);
    seller->AddSalesResult(7000);
    handler.AddEmployee(seller);

    //이번 달 지불할 급여 정보
    handler.ShowAllSalaryInfo();

    //이번 달 지불할 급여 총합
    handler.ShowTotalSalary();

    return 0;
}

함수 오버라이딩과 함수 오버로딩

함수 오버라이딩 : 부모 클래스와 동일한 이름의 함수를 자식 클래스에서 재정의 하는 것  

함수 오버로딩 : 부모 클래스와 동일한 이름의 함수를 자식 클래스에 재정의할 때, 매개변수의 자료형 및 개수가 다른 경우로, 이때는 함수 호출시 전달된 인자에 따라 호출되는 함수가 결정된다.
  → 이는 상속의 관계에서도 구성할 수 있다.





3.가상 소멸자와 참조자의 참조 가능성
01-가상 소멸자(Virtual Destructor)
가상함수 말고도 virtual 키워드를 붙여줘야하는 대상, 소멸자

가상 소멸자의 필요성

부모클래스의 타입으로 선언된 포인터가 자식클래스의 객체를 가리킬 때, 객체 포인터를 이용하여 객체의 소멸을 명시하면 부모클래스의 소멸자만 호출되게된다.

이런 경우에는 메모리의 누수(leak)가 발생한다.

따라서 객체 소멸과정에서는 객체 포인터의 자료형과 관계없이, 실제로 포인터가 가리키는 객체의 자료형에 맞게 모든 소멸자가 호출되게 해주어야한다.
  → virtual 키워드의 필요성



가상 소멸자의 특징

부모클래스의 소멸자가 virtual로 선언되면, 이를 상속하는 자식클래스의 소멸자들은 (별도로 virtual 선언을 추가하지 않더라도,) 모두 자동으로 가상 소멸자로 선언된다.
객체가 소멸되면서 가상 소멸자가 호출되면, 객체 포인터의 자료형과 관계없이 상속의 계층구조상 가장 아래에 있는 자식클래스의 소멸자가 대힌 호출된다.  
→ 차례대로 부모클래스의 소멸자까지 순차적으로 호출됨*


가상 소멸자의 사용
  class First {
          . . .
          public:
                  virtual ~First() { . . . . }      // 가상 소멸자
  }

  //자식클래스
  class Second : public First {
          . . . 
          public:
                  virtual ~Second() { . . . . }
                  // ~Second() {} 로 정의해도(키워드없이) 자동으로 가상 소멸자로 정의된다. 
  }


02-참조자의 참조 가능성

C++에서 어떤 클래스의 참조자는 그 클래스를 직접/간접적으로 상속하는 모든 객체를 참조할 수 있다.


객체 포인터를 다룰때 설명한 특성은 참조자에도 적용된다.

또한, 객체 포인터 특성과 가상함수 등의 개념도 참조자에 그대로 적용된다.

참조자의 사용 예시

First 클래스 또는 이를 직/간접적으로 상속하는 클래스의 객체가 인자의 대상이 되는 함수

인자로 전달되는 객체의 실제 자료형과는 관계없이, 참조자가 First 클래스 타입이므로 함수 내에서는 First 클래스 내에서 정의된 멤버에 대해서만 접근할 수 있다.
void GoodFunction(const First &ref) {}







4.다중상속 : Multiple Inheritance
01-다중상속의 의미와 문제점

다중상속은 둘 이상의 클래스를 동시에 상속하는 것을 말한다.


일반적으로 다중상속은 많은 문제를 동반하기 때문에, 가급적 사용하지 않는 것이 좋다.
실제로 다중상속만으로 해결가능한 문제는 존재하지 않으니…




02-다중상속의 기본방법
기본적으로 상속방법은 기존과 동일하다.

다중상속시에는 상속의 대상이 되는 부모클래스를 ,를 이용하여 명시할 수 있다.
또한 상속의 대상이되는 각 부모클래스를 어떤 접근제한 형태로 상속할 지 또한 별도로 지정이 가능하다.

#includ 
using namespace std;

class BaseOne {
        public:
                void SimpleFuncOne() { cout<<"BaseOne"<




03-다중상속의 모호성 (Ambiguous)

다중상속의 대상이 되는 두 부모 클래스에 동일한 이름의 멤버가 존재하는 경우 문제가 발생할 수 있다.
  → 어떤 부모 클래스의 멤버에 접근하라는 것인지 알 수 없기 때문에 멤버의 이름만으로 접근이 불가능하다.

다중상속의 모호성을 해결하기 위해서는 부모클래스이름::멤버 의 형태로 접근해야한다.


#includ 
using namespace std;

class BaseOne {
        public:
                void SimpleFunc() { cout<<"BaseOne"<




04-가상 상속

간접상속으로 인한 다중상속의 모호성

Base 클래스를 상속하는 2개의 자식클래스를 가정해보자.

MiddleOne
MiddleTwo


만약 Derived 클래스가 MiddleOne, MiddleTwo 클래스를 모두 상속받게 된다면 Derived 클래스는 Base 클래스에 2번 간접 상속하게된다.

이렇듯 하나의 객체 안에 2개의 Base클래스 멤버가 존재하기 때문에, 어떤 Base클래스의 멤버를 호출할지에 대한 구분이 필요하다. [다중상속의 모호성]

MiddleOne::Func() : MiddleOne클래스가 상속한 Base클래스의 Func() 함수 호출

MiddleTwo::Func() : MiddleTwo클래스가 상속한 Base클래스의 Func() 함수 호출
→ 그러나 이경우, Base클래스의 멤버가 1개씩만 존재하는 것이 타당하기 때문에 해결책이 필요하다.





만약 가상으로 Base 클래스를 상속하는 두 클래스를 다중상속하게 되면, Base클래스의 멤버가 1개씩만 존재하게 할 수 있다.. 


→ 가상 상속을 하면 Base클래스의 생성자가 1번만 호출된다.



본문은 ⟪열혈 C++ 프로그래밍, 윤성우⟫ 도서에 기반하여 정리한 내용입니다.

key	value
void BBB::Func1()	0x1024
void AAA::Func2()	0x2048
void BBB::Func3()	0x4096



[선형대수학] Four Fundamental Subspace (feat.dimension)
Tue, 16 Aug 2022 08:34:48 GMT
Four Fundamental Subspace
$m\times n$ matrix $A$에 대하여,
Column space of A

모든 $n$차원 벡터 $\bold x$에 대해 $A\bold x$ 들의 집합 공간. (=행렬 $A$의 column의 linear combination)


$\bold x$ 의 차원 : $m\times n$ matrix $A$의 오른쪽에 곱해지므로 $n$차원 벡터  

$A \bold x$는 $m\times \not n \cdot \not n \times 1 = m \times 1$ 이므로 $m$차원의 subspace


$$
C(A) = {A \bold x|\ ∀ \bold x ∈ \mathbb R^ n}\text{ , a subspace of } \mathbb R^m
$$



Row space of A
=Column space of $A^T$

모든 $m$차원 벡터 $\bold x$에 대해 $A^T\bold x$ 들의 집합 공간. (=행렬 $A^T$의 column, 즉 $A$의 row의 linear combination)


$\bold x$ 의 차원 : $n\times m$ matrix $A^T$의 오른쪽에 곱해지므로 $m$차원 벡터  

$A^T \bold x$는 $n\times \not m \cdot \not m \times 1 = n \times 1$ 이므로 $n$차원의 subspace


$$
C(A^T) = {A^T \bold x|\ ∀ \bold x ∈ \mathbb R^m}\text{ , a subspace of } \mathbb R^n
$$



Nullspace of A

$A$에 곱한 결과가 0이 되도록하는 $n$차원 벡터 $\bold x$들의 집합 공간.


벡터 $\bold x$는 $m\times n$ matrix $A$의 오른쪽에 곱해지므로 $n$차원의 subspace

$$
N(A) = {\bold x|\ A \bold x = \bold 0}\text{ , a subspace of } \mathbb R^n
$$



Left nullspace of A
=Null space of $A^T$

$A^T$에 곱한 결과가 0이 되도록하는 $m$차원 벡터 $\bold x$들의 집합 공간.


Left?

행렬 $A$의 왼쪽에 곱한 결과가 $0$이 되는 벡터 $\bold y$를 가정한다.
  $$
  \bold y A =\bold 0
  $$

기존의 방정식 형태에 양변을 전치하여, $\bold y^T = \bold x$로 생각하여 left nullspace를 표현할 수 있다.
  $$
  (\bold y A)^T = \bold 0 \rightarrow A^T\bold y ^T = \bold 0
  $$



벡터 $\bold x$는 $n\times m$ matrix $A^T$의 오른쪽에 곱해지므로 $m$차원의 subspace
(↔  벡터 $\bold y$는 $m\times n$ matrix $A$의 왼쪽에 곱해지므로 $m$차원의 subspace)


$$
N(A^T) = {\bold x|\ A^T \bold x = \bold 0}\text{ , a subspace of } \mathbb R^m
$$



Demension of Four Fundamential Subspace
Dimension of C(A)
$C(A)$의 basis는 $A$의 pivot column의 갯수와 같다.
→ pivot column의 수는 pivot의 수와 동일하고, pivot의 개수를 나타내는 것은 rank이다.
→ 따라서 차원은 $r(A)$이다. 
$$
\dim(C(A)) = r(A)
$$



Dimension of C(A^T)
$C(A^T)$의 basis는 $A^T$의 pivot column의 갯수와 같다.
→ pivot column의 수는 pivot의 수와 동일하고, pivot의 개수를 나타내는 것은 rank이다.
→ $r(A^T) = r(A)$이므로 차원은 $r(A)$이다. 
$$
\dim(C(A^T)) = r(A)
$$



Dimension of N(A)
$A\bold x = \bold 0$의 special solution은 

서로 선형독립관계이다.
$N(A)$를 span한다.

→ special solution이 $N(A)$의 basis이며, basis안의 벡터의 개수(=차원)는 special solution의 개수와 동일하다. 
→ special solution의 개수는 free column의 수와 동일하므로 전체 column에서 pivot column의 수를 빼준다.
→ 따라서 차원은 $n- r(A)$이다.
$$
\dim(N(A)) = n-r(A)
$$



Dimension of N(A^T)
앞서 영공간의 차원을 구하는 과정을 똑같이 적용한다. (이때 $r(A) == r(A^T)$이므로 아래와 같이 표현가능)
$$
\dim(N(A^T)) = m - r(A^T)\\ \ =m-r(A)
$$



For Fundamential Subspace의 dimension 연산
4개의 subspace와 그 dimension에 대하여 아래 공식이 항상 성립한다.  ($A$는 $m\times n$ 행렬)

$\mathbb R^n$에서
  $$
  \dim(C(A^T)) + \dim(N(A)) = n
  $$



$\mathbb R^m$에서

$$
\dim(C(A)) + \dim(N(A^T)) = m
$$
→ 각 dimension이 어떤 값을 갖는지 생각해보면 쉽게 증명할 수 있다. 



+ Elimination 전후 row space 💫

행렬 $A$에 elimination을 진행한 결과로 나타나는 행렬을 $U$라고 할 때, $A$와 $U$는 동일한 row space를 갖는다.


elimination 과정은 기존 행렬의 row space안에서 일어나는 과정이다.  

→ 기존 행들의 linear combination이 바로 Gauss elimination를 의미한다.* 

linear combination은 해당 공간안에서만 일어나는 닫힌 연산이기 때문에, 기존의 row space로 표현할 수 없는 새로운 벡터가 Elimination이후에 나타날 수 없다.

단, column space는 변화한다.





[선형대수학] Basis and Dimension of Subspace
Mon, 15 Aug 2022 12:54:32 GMT
Span
Definition of Span

벡터들의 모든 linear combination을 모아둔 space가 다른 space와 정확히 같을 때, 해당 벡터들의 집합이 해당 space를 span한다고 한다.


주의점 : 정확히 동일한 경우에만 span이라고 한다. 포함관계($⊂,⊃$)면 span하지 않는다.

$\bold v_1$과 $\bold v_2$의 span : $\bold v_1$과 $\bold v_2$의 모든 linear combination을 모아둔 space
  $$
  \left{ c_1 \bold v_1 + c_2 \bold v_2,\ \ \forall c_1,c_2 \in \mathbb R \right}
  $$

ex) 행렬의 column들은 column space*를 span한다.
→ column space는 column의 모든 linear combination을 모아둔 subspace
  $$
  \text{if}\ \ A=[\bold a_1\ \bold a_2\ \cdots\ \bold a_n]\\ \C(A) = \left{ c_1 \bold a_1 + c_2 \bold a_2+\cdots+c_n \bold a_n,\ \ \forall c_i \in \mathbb R \right}
  $$





special solution과 NullSpace의 관계 : span

$A\bold x = \bold 0$의 special solution들은 Null space $N(A)$를 span한다.


Null space인 $N(A)$의 정의 자체가 special solution들의 모든 linear combination을 모아둔 공간이기 때문이다.

$A$가 $m\times n$ 행렬일 때 $r(A) = r$개라고 가정하면, $n-r$개의 special solution을 가진다.
  $$
  N(A) = {c_1\bold s_1 + ... + c_{n-r}\bold s_{n-r},\ ∀c_1, ..., c_{n-r} ∈ \mathbb R}
  $$





span과 independent

어떤 vector들이 어떤 space를 span한다고 해서, 해당 벡터들이 반드시 선형독립인것은 아니다.
span하는 벡터들은 서로 독립이어야한다는 조건은 존재하지 않는다.
종속관계인 벡터들도 서로 모여 space를 만들고, span할 수 있다.


어떤 space를 span하는 벡터들이 특별히 linear independent 관계일 때, 이를 Basis라고 부른다.




Basis
Definition of Basis

어떤 space를 span하는데 필요한 벡터의 최소모음
→ 이 벡터들은 서로 lineary independent 하다.


basis의 표현은 무수히 많을 수 있다. (ex: $[1, 2], [2, 4], [0.5, 1]...$ 같은 계수비)

어떤 basis로 그 basis가 span하는 공간안의 어떤 벡터를 표현할 때, 단 1가지 방법의 선형결합으로 표현할 수 있다. [only one linear combination]

basis는 space를 span하기 때문에, 해당 space안의 어떤 벡터라도 basis들의 linear combination으로 표현할 수 있다.





Basis of C(A)

Comlun space와 linear independence  

$C(A)$는 $A$의 모든 column들의 linear combination이다.
따라서 $A$의 column은 $C(A)$  공간을 span한다.
하지만 $A$의 column들 사이에는 독립관계가 보장되지 않기 때문에 basis는 아니다.


Basis of $C(A)$ 찾는 방법

행렬 $A$를 elimination하여 pivot column을 찾는다.

elimination하면 column space는 바뀔 수 있지만, row space는 변하지 않는다.
elimination했을 때, pivot column들은 반드시 독립이 될 수 밖에 없다.


pivot column과 동일한 위치(=열)에 존재하는 기존 $A$의 column들이 $C(A)$의 basis이다.
 → pivot column만 basis인 것은 아니지만, pivot column은 무조건 basis이다.







Finding a Basis (C(A) case의 확장)
벡터 $\bold v_1, \bold v_2, ... \bold v_n$이 어떤 space $S$를 span할 때,

각 벡터를 column을 갖는 행렬 $A$를 생각한다. $A = [\bold v_1\ \bold v_2\ \cdots \ \bold v_n]$

행렬 $A$를 elimination하여 pivot column을 찾는다.

pivot column과 동일한 위치에 존재하는 elimination하기 전 기존 행렬 $A$의 column벡터들이 $S$의 basis이다.


각 벡터를 열로 갖는 행렬을 가정한 뒤에는, $C(A)$의 Basis를 찾는 과정과 동일하다.



예시
*space $S$
$$
S=\left{c_1 \begin{bmatrix} 1 \ 2 \ 3 \end{bmatrix} + c_2\begin{bmatrix} 1 \ 1 \ 1 \end{bmatrix} + c_3 \begin{bmatrix} 4 \ 6 \ 8 \end{bmatrix},\ \ \forall c_1,c_2,c_3 \in \mathbb R\right}
$$

행렬 $A$ 가정
 $$
 A = \begin{bmatrix} 1 & 1 & 4 \ 2 & 1 & 6 \ 3 & 1 & 8 \end{bmatrix}
 $$  

elimination해서 pivot column 구하기
 $$
 \begin{bmatrix} 1 & 1 & 4 \ 2 & 1 & 6 \ 3 & 1 & 8 \end{bmatrix} \rightarrow^{G.E}\begin{bmatrix} 1 & 1 & 4 \ 0 & -1 & -2 \ 0 & -2 & 0 \end{bmatrix} \rightarrow^{G.E}\begin{bmatrix} \color{blue}1 & \color{blue}1 & 4 \ \color{blue}0 & \color{blue}-1 & -2 \ \color{blue}0& \color{blue}0 & 0\end{bmatrix} 
 $$

basis 구하기
 $$
 \begin{bmatrix} \color{blue}1 & \color{blue}1 & 4 \ \color{blue}2 & \color{blue}1 & 6 \ \color{blue}3 & \color{blue}1 & 8 \end{bmatrix}\ \ \rightarrow\ \ \ \begin{bmatrix} 1 \ 2  \ 3  \end{bmatrix},\ \begin{bmatrix} 1 \ 1  \ 1\end{bmatrix}
 $$





invertible matrix와 basis

$n\times n$ invertible matrix의 column들은 $\mathbb R^n$의 basis이다.

why?

역행렬을 가지기 위한 조건에 따라 $A$는 $n$개의 pivot을 갖는다. $r(A) = n$
$A$의 column들은 모두 linear independece이다.
따라서 $n$차원 $n$개의 column vector는  $\mathbb R^n$을 span하며, 서로 linear independece하기 때문에 basis이다.




basis와 basis를 구성하는 벡터간의 관계

어떤 Space에 대하여 basis는 무수히 많이 존재하는데, 이 basis들은 모두 같은 수의 벡터를 가진다.

증명

어떤 하나의 space에 대하여 $m$개의 벡터를 가지는 basis $V$와 $n$개의 벡터를 가지는 서로 다른 basis $W$가 있을때 $n > m$이라고 가정하자. (서로 다른 수의 벡터를 갖는 basis들이 존재한다고 가정: 귀류법)

basis $W$를 구성하는 벡터들은 space안에 포함된 벡터이기 때문에, 다른 basis인 $V$의 선형결합으로 각 벡터들를 표현할 수 있을 것이다. 
 $$
 \bold w_i = a_{1i}\bold v_1 + a_{2i}\bold v_2 + \cdots + a_{mi}\bold v_m 
 $$

이를 행렬곱으로 나타내면, 아래와 같다.
 $$
  W= [\bold w_1\ \bold w_2\ \cdots\ \bold w_n] = [\bold v_1\ \bold v_2\ \cdots\ \bold v_m] \begin{bmatrix} a_{11}& \cdots &a_{1n} \ \vdots &\ddots &\vdots \ a_{m1}& \cdots &a_{mn} \end{bmatrix} = VA
 $$
 a. 이때 행렬  $A$에서 가정에 따라 $n>m$이므로 full column rank 조건을 만족하지 않는다.  
   → $A\bold x = \bold 0$에서 $0$이 아닌 solution이 존재한다. 
 b. 따라서 양변에 0이 아닌 solution $\bold x$를 곱한다. 
$$
 W\bold x = VA\bold x 
$$
이때 $A\bold x = \bold 0$이 되는 $0$이 아닌 solution $\bold x$를 곱했기 때문에, 우변은 $0$이 된다. 
 $$
 W\bold x = \bold 0
 $$

[모순] 이때 basis $W$는 독립관계이기 때문에 위 수식을 만족하는 solution $\bold x$는 반드시 0이 되어야한다. 즉, $0$이 아닌 solution $\bold x$에 대하여 $W\bold x = \bold 0$이 될 수 없다. 
 → 증명 도중 모순이 발생했기 때문에 가정이 틀렸다.
 + $m>n$인 경우에 대해서도 진행하면 모순이 발생함 ($V=WA$). 따라서 $n=m$이다.





Standard basis

어떤 공간을 표현하는 표준 기저.


열 벡터를 구성하는 요소중에 하나만 1인 벡터들로 구성된 basis를 칭한다.

ex) 3차원 공간 $\mathbb R^3$의 Standard basis
  $$
  \bold e_x = \begin{bmatrix} 1 \ 0 \ 0\end{bmatrix},\ \bold e_y = \begin{bmatrix} 0 \ 1 \ 0\end{bmatrix},\ \bold e_z = \begin{bmatrix} 0 \ 0 \ 1\end{bmatrix}
  $$





Dimension
Definition of Dimension

어떤 space의 차원은 basis의 벡터의 개수를 의미한다.
$=$ pivot column의 개수
$=$ pivot의 개수
$=$ rank의 개수

Dimension of Subspace
$m\times n$ 행렬 $A$에 대하여, 

column space : $A$의 column space의 dimention은 $A$의 rank의 개수와 같다.
  $$
  \dim(C(A)) = r(A)
  $$

Null space : $A$의 nullspace의 dimention은 $A$의 special solution의 개수와 같다.
  $$
  \dim(N(A)) = n - r(A)
  $$
  $N(A)$는 special solution들의 linear combination으로 서로 독립이니까 basis의 조건을 만족함
  $=$ $A$의 special solution의 개수
  $=$ free column/variable의 개수





영벡터의 dimension 💫

영벡터는 기하학적으로 어떤 1개의 dot을 의미함

영벡터는 모든 linear combination에 대하여 갇혀있기에 subspace가 맞다.
ex)  $c \cdot \bold 0 = \bold 0$  

basis는 empty vector이다. $\dim=0$
  $$
  \text{span} (\empty) = \left{ \bold 0 \right }
  $$
  증명

empty vector이 basis임을 보인다.
 a. linear combination의 결과가 $0$이면 $\bold x$는 영벡터만 가능하다. (=span 조건)
가정) 어떤 영벡터가 아닌 $\bold x$에 대해 다음이 성립한다고 하자. [귀류법]

$$
 x_1\bold v_1 + \cdots + x_n \bold v_n = 0
$$
 b. 서로 독립이다.
→ empty vector는 가지고 있는 벡터가 없기 때문에, 식이 성립할 수가 없기 때문에 두 조건 모두 만족한다고 할 수 있다.
따라서 empty vector가 span하는 space는 가장 작은 space이다.

그런데 empty vector는 모든 space에 포함관계이다. 
 (모든집합은 부분집합으로 공집합을 가짐)

따라서 가장 작은 space는 ${ \bold 0 }$이다.







[선형대수학] Linear Independence (feat. Rank)
Mon, 15 Aug 2022 11:21:03 GMT
Definition of linearly Independent

아래 linear combination를 만족하는 유일한 해가 $x_i=0, \forall i$ 일 때, $\bold v_1... \bold v_n$ 벡터들은 서로 linearly Independent(일차/선형 독립) 이다.

$$
x_1\bold v_1 + x_2 \bold v_2 + · · · + x_n \bold v_n = \bold  0 \ \ \text{only when}\ \ x_i=0, \forall i
$$

Definition의 의미
  $\bold v_1... \bold v_n$ 열벡터를 갖는 행렬 $A$에 대해, $A \bold x= \bold 0$의 유일한 해가 $\bold x = \bold 0$ 일 때 행렬 $A$의 열벡터는 서로 선형독립이다. 
  → Rank의 개념을 적용하면 선형독립과 Rank의 관계를 유추할 수 있다! [Full column Rank]


$$
A\bold x =[\bold v_1\ \bold v_2 \ \cdots \ \bold v_n ] \begin{bmatrix} x_1\ x_2\ \vdots \ x_n\end{bmatrix} = \bold 0\ \ \text{only when}\ \ \bold x= \bold 0
$$




독립이 아니라면? (=종속이라면?)

만약 종속관계라면 linear combination에서 $0$이 아닌 다른해를 가진다.

종속관계이면 해당 관계에 속하는 벡터를 다른 벡터의 linear combination으로 표현할 수 있다.
→ $x_i ≠ 0$ 이라면, 다음과 같은 linear combination으로 $\bold v_i$를 표현할 수 있다.
 $$
  \bold v_i = - \frac{1}{x_i} (x_1\bold v_1 + x_2 \bold v_2 + \cdots + x_n \bold x _n )
 $$







Linear Independece에서 Rank의 의미

the rank of a matrix is also defined as the maximum number of linearly independent columns in the matrix.
행렬의 Rank는 행렬에서 독립적으로 뽑아낼 수 있는 column의 최대개수이다.


Rank와 Independence의 관계

만약 행렬이 full column rank이면, 모든 column들이 서로 독립적인 관계이다.  

full column rank : Rank의 개수가 column의 갯수와 동일 

$m \times n$ 행렬 $A$가 full column rank일 때, $n$개의 pivot variable/column을 가진다.

(pivot variable/column으로 표현되는) free variable/column을 가지지 않는다. [종속적인 관계]

Null Space는 영벡터만을 갖는다.
  $$
  N(A) = { \bold 0 }
  $$

$A\bold x = \bold b$ 는 해를 아예 가지지 않거나 1개의 해만을 가진다.



pivot을 가지는 column(=pivot column)들은 서로 독립관계이며, pivot을 갖지 않는 column(=free column)은 다른 pivot column들의 linear combination으로 나타낼 수 있다.



Row / Column rank와 Independence의 관계

Row rank는 선형독립한 행의 최대개수와 같다.
Column rank는 선형독립한 열의 최대개수와 같다.
⇒ row rank와 column rank는 사실상 같은 의미이다.
$$
r(A) = r(A^T)
$$






Checking Linear Independence

Rank의 갯수는 독립인 column의 수와 동일하다는 점을 이용하여 확인한다.

$m$차원 벡터 $n$개가 모여있을 때, (= $m \times n$ 행렬 $A$을 의미)

$n > m$이면 (벡터가 존재하는 차원보다 더 많은 벡터가 있을 때) 종속이다.
  ex) 2차원 좌표에 2개 이상의 벡터가 존재하면, 그 벡터들의 선형결합으로 다른 모든 2차원상의 벡터를 표현할 수 있게 된다.

$n ≤ m$인 경우

각각의 벡터를 열벡터로 갖는 행렬 $A$를 생각한다. $A = [\bold v_1\ \bold v_2\ \cdots\  \bold v_n]$

$A$에 Gauss Elimination을 적용하여 $r(A)$를 구한다. 

만약 $r(A) =  n$ (full column rank) 이면 독립이다. 
 ↔  $r(A)







[C++] 상속 : 기초
Mon, 15 Aug 2022 08:47:36 GMT
1.상속:Ingeritance의 이해
00-객체지향에서 중요시 하는 원리

요구사항의 변경에 쉽게 대응할 수 있는 프로그램의 유연성
다른 기능을 쉽게 추가할 수 있는 프로그램의 확장성




01-상속이 필요한 이유
과거에 상속을 바라보았던 관점

기존에 정의해 놓은 클래스의 재활용을 목적으로 만들어진 문법적 요소가 상속이다.

→ 그러나 상속은 재활용을 목적으로만 존재하는 문법적 요소가 아니며, 다양한 이점들이 존재한다.
어떤 회사가 직원의 급여를 관리하기 위해 어떤 프로그램을 만들었다. 회사 초기에는 ‘정규직'으로 직원의 종류가 1가지였지만, 점점 회사가 커지면서 직원의 역할이 세분화됨에 따라 직원의 고용형태가 달라졌다고하자. 이미 설계해둔 프로그램을 이용하여 현재의 조건에 맞는 기능을 할 수 있게 변경할 수는 없을까?
→ 상속을 적용하면 가능하다!



02-상속의 방법

자식클래스가 부모클래스를 상속하게 되면, 자식클래스는 부모클래스가 지니고 있는 모든 멤버를 물려받는다.


자식클래스를 정의할 때, 자식클래스의 이름 뒤에 : 접근제한자 부모클래스이름 을 붙여 상속할 수 있다.

소스코드
  /*부모클래스 Person*/
  class Person {
          private:
                  int age;
                  char name[50];
          public:
                  Person(int myage, char* myname) : age(myage) {
                          strcpy(name, myname);
                  }
                  void ShowInfo() const {
                          cout<<"Age: "<

  /*자식클래스 Student*/
  class Student : public Person {
          private:
                  char major[50];
          public:
                  Student(int myage, char* myname, char* mymajor) : Person(myage, myname) {
                          strcpy(major, mymajor);
                  }
                  void ShowInfo_std() const {
                          ShowInfo();
                          cout<<"Major: "<


상속받은 클래스의 객체가 가지는 멤버

자식클래스를 정의한 코드만 보면 major라는 멤버 변수와 ShowInfo_std()라는 멤버메소드만 가지고 있는 것 같지만, 실제로는 자기자신의 멤버 + 부모의 멤버(age, name, ShowInfo())를 모두 멤버로 가지고 있다.
따라서 자식클래스안에서 부모클래스의 멤버함수를 호출할 수 있었던 것이다.






03-자식클래스의 생성자 정의

자식클래스의 멤버 초기화

자식클래스의 생성자에서는 부모클래스의 멤버변수까지 모두 초기화 해야할 의무가 있다.

클래스의 멤버를 초기화 할 때는 멤버의 초기화를 목적으로 정의되었던 해당 클래스의 생성자를 호출하여 초기화하는 것이 정석이다.
  ⇒ 따라서 자식클래스의 생성자는 자신이 상속한 부모클래스의 멤버를 초기화하기 위해 부모클래스의 생성자를 자기자신의 생성자에서 호출한다.



생성자 구성

자식클래스의 생성자에서는 부모클래스의 멤버를 초기화하기위한 인자의 전달까지 요구한다.

이니셜라이저가 의미하는 바는 부모클래스의 생성자의 호출이다.
  Student(int myage, char* myname, char* mymajor) //부모멤버 초기화를 위한 인자요구
          : Person(myage, myname) //부모생성자의 호출
          {
                  strcpy(major, mymajor);  //자기자신의 멤버의 초기화
          }







04-자식클래스의 객체 생성 및 소멸
자식클래스의 객체 생성

자식 클래스 객체 생성과정

클래스를 생성하기 위해 메모리 공간이 할당된다. 

이후 객체 생성 명령문에 의해 인자가 전달되면서 생성자가 호출된다.

먼저 부모 클래스의 생성자 호출을 위해 이니셜 라이저를 찾고,   
a. 부모클래스의 생성자가 명시되어있으면 명시된 부모클래스의 생성자를 호출한다.  
b. 명시되어있지 않다면 void 생성자를 호출한다.


  *void 생성자 → 전달받는 인자가 없는 생성자. (default 생성자 or 전달받는 인자없이 초기화하는 생성자)

부모 클래스의 생성자 호출이 완료되어 부모 클래스의 멤버변수가 먼저 초기화된다.
부모 클래스의 생성자 호출을 위해 실행되지 않았던 자식 클래스의 생성자 실행이 마저 진행되면서 자식 클래스의 멤버변수도 초기화된다. 




자식 클래스 객체 생성 특징
자식 클래스의 객체 생성 과정에서 부모 클래스의 생성자는 무조건 호출된다.    



- 자식 클래스의 생성자에서 만약 부모 클래스의 생성자 호출을 명시하지 않았다면, 부모 클래스의 default 생성자가 호출된다.  

***부모 클래스의 생성자 정의에 따른 결과***

  - 부모 클래스에서 어떤 생성자도 정의하지 않았을 때  

  defalt 생성자가 사용된다. 따라서 생성만 했을 뿐 초기화를 위한 어떤 작업도 해주지 않았기 때문에 부모 클래스의 멤버변수에는 쓰레기 값이 들어있다.

  - 부모 클래스에 void생성자가 아닌 다른 생성자(=인자를 전달받는)를 정의했을 때
      - 자식 클래스의 default 생성자를 사용할 수 없다.
      - 반드시 자식 클래스 뒤에 정의해 둔 부모 클래스의 생성자를 명시해야한다. (명시하지 않으면 에러 발생)



자식클래스의 객체 소멸

자식 클래스의 객체 생성과정에서 생성자가 2번 호출된 것처럼, 자식 클래스의 객체가 소멸할 때는 소멸자가 2번 호출된다.

자식 클래스 객체 소멸 특징

자식 클래스의 객체가 소멸될 때는, 다음 순서를 따른다. (생성자 호출순서와 역순)

자식 클래스의 소멸자 실행

부모 클래스의 소멸자 실행
 ⇒ 스택에 생성된 객체의 소멸순서는 생성순서와 반대이다.



따라서 상속과 연관된 클래스에서는 생성자에서 동적할당한 메모리는 소멸자에서 해제하도록 정의해야한다.




+ 용어정리



Person
Student



상위클래스
하위클래스


기초(base)클래스
유도(derived)클래스


슈퍼(super)클래스
서브(sub)클래스


부모클래스
자식클래스





2.상속의 세 가지 형태
01-protected 선언의 접근 범위

private < protected < public


private와 protected는 모두 해당 클래스의 외부에서는 접근이 불가능하지만 내부에서는 접근이 가능하다.

그러나 상속에서는 이 2가지 키워드의 차이점을 한눈에 알 수 있다!

private : 자식클래스는 부모클래스의 외부이기 때문에 private로 선언된 부모 클래스의 멤버에 접근할 수 없다.
  → 상속과정에서는 어떤 접근제한범위로 선언된 멤버든 모두 상속된다.(private 멤버도 상속됨) 그러나 접근제한의 기준은 객체가 아니라 클래스이기 때문에, 부모 클래스의 외부인 자식 클래스에서는 private 멤버에 직접접근은 할 수 없다.

protected : 그러나 private와 다르게 protected로 선언된 부모 클래스의 멤버는 부모 클래스의 뫼부인 자식 클래스 안에서 접근할 수 있다!

자식클래스에게만 제한적으로 접근을 허용한다.




소스코드
  /*부모 클래스*/
  class Base {
          private:
                  int num1;
          protected:
                  int num2;
          public:
                  int num3;
  };
  /*자식 클래스*/
  class Derived : public Base {
          public:
                  void Show(){
                          cout<<"private number"<






02-3가지 형태의 상속

자식 클래스에서 상속을 명시하는데 있어서 3가지의 접근제한자를 모두 사용할 수 있다. [상속의 형태를 명시]
class 자식클래스 :접근제한자부모클래스 {};




03-protected 상속

protected보다 접근의 범위가 넓은 멤버(=public)는 protected로 변경시켜서 상속한다.

→ 따라서 protected 상속을 하게 되면, 기존에 클래스 밖에서 접근이 가능하던 멤버도 밖에서 접근할 수 없도록 보호된다. 

private 멤버 → 직접 접근 불가능한 멤버
protected 멤버 → protected 멤버
public 멤버 → public 멤버




04-private 상속

private보다 접근의 범위가 넓은 멤버(=public, protected)는 private로 변경시켜서 상속한다.

→ 따라서 private 상속을 한 클래스를 다시 한번 더 상속하게되면 모든 멤버(변수,함수)가 private이기 때문에, 자식클래스에서는 부모클래스의 모든 멤버에 직접접근할 수 없게된다. (사실상 의미없는 상속)

private 멤버 → 직접 접근 불가능한 멤버
protected 멤버 → private 멤버
public 멤버 → private 멤버




05-public 상속

public보다 접근의 범위가 넓은 멤버(=없음)는 public으로 변경시켜서 상속한다.
⇒ private를 제외한 나머지 멤버는 모두 그냥 그대로 상속한다. 


private 멤버 → 직접 접근 불가능한 멤버
protected 멤버 → protected 멤버
public 멤버 → public 멤버

*실제로는 public 이외의 상속은 다중상속과 같이 특별한 케이스가 아니라면 사용하지 않는다.



3.상속을 위한 조건
01-상속을 위한 기본조건 : IS-A 관계

상속관계가 성립하기 위해서는 자식 클래스와 부모클래스 간에 IS-A 관계가 성립해야한다.
자식클래스 is a 부모클래스


스마트폰은 일종의 전화기이다.
  → smart phone is a phone.

노트북은 일종의 컴퓨터이다.
  → notebook is a computer





02-HAS-A 관계 (소유의 관계)

자식클래스는 부모 클래스가 가지는 모든 멤버를 소유하기 때문에 소유의 관계도 상속으로 표현할 수 있다.
자식클래스 has a 부모클래스

(단, 소유의 관계는 상속이 아니라 가지고 있는 객체를 생성해서 사용하는 등의 방법을 사용하여 표현할 수 있다. )

경찰이 총을 가지고 있다.
  → police has a gun



상속관계로 표현하기 힘든 소유 관계

총을 가지고 있지 않은 경찰의 표현

총 만이 아니라 다른 도구도 소유하고 있는 경찰의 표현
  → 상속은 묶인 두 클래스는 강한 연관성을 띠기 때문에, 다양한 조건을 가질 수 있는 소유관계는 다른 복합 관계로 대신하는 것이 일반적이다.







본문은 ⟪열혈 C++ 프로그래밍, 윤성우⟫ 도서에 기반하여 정리한 내용입니다.



[선형대수학] Rank
Fri, 12 Aug 2022 13:43:25 GMT
Rank of a Matrix
Definition of Rank

The rank of a matrix $r(A)$ is the number of pivots


행렬의 rank는 pivot의 개수를 의미한다.    

rank의 의미
$m\times n$ 행렬 $A$가 $r$개의 rank를 가질 때,

$A\bold x = \bold 0$은 $m$개의 linear equation을 가진다.
$m$개의 linear equation중에서 $m-r$개의 equation은 다른 equaion으로부터 유도될 수 있다. [종속]
따라서 실제로는 rank의 개수인 $r$개의 equation이 존재하는 것이나 다름없다.
⇒ rank는 행렬의 진짜 크기를 나타낸다.



Rank의 응용
전체 행렬을 저장하는 것보다, 행렬의 정보(Rank, pivot)만을 저장한 뒤에 복원하는 방식으로 저장용량을 줄알 수 있다. 



Full Rank
Full Rank의 의미

$m\times n$ 행렬 $A$의 rank의 갯수 $r(A)$는 행렬의 행($m$)이나 열($n$)의 갯수를 넘어설 수 없다.
→ 각각의 column은 최대 1개의 pivot을 가지기 때문이다.

$$
r(A) ≤ min{m,n}
$$
Full Column Rank

$m\times n$ 행렬 $A$의 rank의 갯수 $r(A)$가 column의 갯수($n$)와 같을 때, $A$는 Full Column Rank를 가진다.
→ 각 column이 모두 pivot으로 가득 차있다는 의미

$$
r(A) = n
$$

Full Column Rank $m\times n$ 행렬 $A$의 특징. 

$n$개의 pivot column을 가진다. ↔ free column/variable을 가지지 않는다.

free variable로 다른 pivot vatiable을 표현하기 때문에 free variable이 없으면 표현자체를 할 수 없기에 Null Space는 영벡터만을 가진다.
  $$
  N(A) = { \bold0}
  $$

$A\bold x = \bold b$는 해를 아예 가지지 않거나 1개의 해만을 가진다.  




   >  💡 아이디어) $A\bold x = \bold b$의 complete solution은 $A\bold x= \bold 0$의 special solution과 $A\bold x = \bold b$의 particular solution의 합이다.


    1. Full Column Rank 행렬의 NullSpace는 영벡터만을 가지기 때문에 special solution이 존재하지 않는다.  

    2. 따라서 complete Solution이 $A\bold x= \bold b$의 particular solution과 동일하다. 
    3. *해를 가지는 경우*
        - particular solution가 존재하면 1개의 complete solution을 가짐
        - particular solution가 존재하면 0개의 complete solution을 가짐

$A\bold x = \bold b$에서
$\bold b$가 $A$의 column Space($C(A)$)에 존재하면 complete solution을 가진다.
$\bold b$가 $A$의 column Space($C(A)$)에 존재하지 않으면 complete solution을 가지지 않는다.


정사각형 or 아래로 긴 직사각형 형태의 행렬




Full Row Rank

$m\times n$ 행렬 $A$의 rank의 갯수 $r(A)$가 row의 갯수($m$)와 같을 때, $A$는 Full Row Rank를 가진다.
→ 각 row가 모두 pivot으로 가득 차있다는 의미

$$
r(A) = m
$$

Full Row Rank $m\times n$ 행렬 $A$의 특징

$A$의 Column Space는 $\mathbb R^m$과 같다.
  $$
  C(A) = \mathbb R^m 
  $$

$A\bold x = \bold b$ 는 항상 해를 가진다.
→ full row rank 행렬의 각 행은 모두 pivot을 가지기 때문에 solution이 항상 존재한다.
↔ 어떤 벡터 $\bold b$가 오더라도 $A\bold x = \bold b$가 항상 해를 가지면 $\bold b$는 $C(A)$에 포함관계이다. 

$n-m$개(=free variable의 개수)의 special solution을 가진다.



정사각형 or 옆으로 긴 직사각형 형태의 행렬





Rank와 Ax = b의 관계
Rank와 special solution의 관계
$m\times n$ 행렬 $A$를 가정하자.

pivot column의 수 : $r(A)$
free column의 수 : $n - r(A)$
→ $A\bold x = \bold 0$은 $n-r(A)$개의 special solution을 가진다는 것을 알 수 있다.

Rank의 개수에 따른 solution의 개수

$r(A) < n$ 이면 해가 무수히 많다.

$r(A) = n$이면 special solution을 가지지 않는다. ($n-n=0$)
  → full column rank

$r(A) = m$이면 solution은 무조건 존재한다.
  → full row rank

$r(A) < m$이면 solution이 존재하지 않을 수도 있다.





관계정리 (표)




[C++] 클래스 키워드
Wed, 10 Aug 2022 02:29:10 GMT
1. const 키워드
01-const 객체
const 키워드를 이용하여 변수를 상수화 하듯, 객체도 상수화 할 수 있다.

const 객체의 의미
const 선언과 함께 만들어진 객체를 대상으로는 const 멤버 함수만 호출할 수 있다.
객체의 데이터 변경을 허용하지 않기 때문이다.
→ 객체 데이터값을 변경시킬 능력이 있는 함수(≠const 함수)는 아예 호출할 수 없도록 한다.




const 객체 선언예시
  #include 
  using namespace std;

  class Simple{
          private:
                  int num;
          public:
                  Simple(int n) : num(n) {}
                  void ShowData() const {
                          cout<<"num: "<



02-함수 오버로딩에서 const

기본적으로 함수를 오버로딩 하려면 함수 호출시 확인하는 매개변수의 개수나 그 자료형이 달라야 한다.

함수 오버로딩에서는, 함수가 정의될 때 const 키워드의 유무로도 함수를 구분한다.
아래 두 함수는 서로 다른 함수이다!

void SimpleFunc() { . . . }
void SimpleFunc() **const** { . . . }






2.friend 선언

친구 !

01-클래스의 friend 선언

friend 선언의 의미

어떤 A클래스가 B클래스를 대상으로 friend선언을 하면, B클래스는 A클래스의 private 멤버에 직접 접근이 가능하다.
→ private 멤버의 접근을 허용하는 선언  

단, A클래스도 B클래스의 private멤버에 직접 접근하기위해서는 B클래스가 A클래스를 대상으로 friend선언을 해야한다.
→ friend선언은 일방적인 선언이다.






friend 선언방법

friend 선언은 클래스를 생성할 때, friend선언을 하고자하는 클래스를 클래스 안의 멤버로 선언하면 된다.

friend선언은 클래스 내의 private, public 영역 어디에 존재하든지 상관없다.

friend선언 예시코드
  #include 
  using namespace std;

  class B;     //클래스 원형
  class A {
          private: 
                  int num;
                  friend class B; //A클래스가 B클래스를 대상으로 friend선언을 함.
          public:
                  A(int num) : num(num) {}
  }




02-friend 선언이 존재하는 이유

friend선언은 객체지향의 기본 원리 중 하나인 ‘정보은닉'을 무너뜨리는 문법이다.
따라서 클래스를 사용할 때 freind선언을 가급적 사용하지 말자.
friend선언은 주로 연산자 오버로딩에 사용된다.

03-함수의 friend 선언

전역함수, 클래스의 멤버함수를 대상으로 friend선언이 가능하다.
클래스 안에서 friend선언된 함수는 자신이 선언된 클래스의 private영역에 접근할 수 있다.




3. static 키워드
01-C언어에서 static

전역변수에 선언된 static : 선언된 파일 내에서만 참조를 허용한다.
함수 내에 선언된 static : 딱 한번만 초기화되고, 일반적인 지역변수와 달리 함수를 빠져나가도 소멸되지 않는다.

02-static 멤버변수: 클래스변수

c++에서는 각각의 클래스별로 전역변수를 사용하고자하는 상황이 발생할 수 있다. 그러나 그냥 전역변수를 사용하면 그 변수에 대해 제한을 시켜줄 장치가 존재하지 않기 때문에, static멤버를 사용하여 그 역할을 대신한다.


static 멤버변수는 그 클래스의 객체를 몇개를 생성하건 아니면 아예 생성하지 않건, 메모리 공간에 딱 하나만 할당되어 공유되는 변수이다.

static 멤버변수는 객체안에 존재하지 않으며, 객체에게는 단지 해당 멤버변수에 접근할 수 있는 권한만을 주었을 뿐이다.

따라서 생성자를 이용해 초기화 하면 안된다. (static 멤버변수는 객체 생성과 상관없이 이미 메모리 할당이 이루어진 변수이기 떄문이다)

static 멤버변수의 초기화
  /* 자료형 클래스이름::클래스변수이름 = 초기화값 */
  int SoSimple::simObjCnt = 0;



생성 및 소멸의 시점 또한 전역변수와 동일하다.

static 멤버변수 사용예시

객체가 생성될 때마다 몇번째로 생성된 객체인지를 알려주는 프로그램

객체 생성될 때마다 해당객체의 클래스변수값을 증가시켜 그 클래스의 객체끼리 공유하는 변수로서 기능을 구현해냈다.
#include 
using namespace std;

class SoSimple {
      private:
              static in simObjCnt;
      public:
              SoSimple(){
                      simObjCnt++;
                      cout<





03-static 멤버변수의 접근방법

객체이름을 이용한 접근 (.)
 ex) obj1.simObjCnt

클래스 자체를 이용한 접근 (::) → 단 이런 접근은 public static 멤버인 경우에만 가능하다. 
 ex) SimClass::simObjCnt


04-static 멤버함수
static 멤버함수 또한 static 멤버변수와 동일한 특징을 가진다.

선언된 클래스의 모든 객체가 공유
public으로 선언되었으면, 클래스의 이름을 통해 접근할 수 있다.
객체의 멤버로 존재하지 않는다.
객체의 멤버가 아니기 때문에, static 멤버함수에서는 객체의 일반적인 멤버변수에 접근할 수 없다. (아직 만들어지기 전이니까)
따라서 static 멤버함수 안에서는 static 멤버변수와 static멤버함수만 호출할 수 있다.



05-const static
const static으로 선언되는 멤버변수는 상수라는 의미의 const키워드가 추가되었기 때문에, 따로 초기화해주지 않고 선언과 동시에 초기화가 가능하다.

일반적인 static변수의 초기화
int SoSimple::simObjCnt = 0;

const static 변수(상수)의 초기화
const static int SIMOBJCNT = 0;





4.값의 변경에 대한 키워드
01-const와 explicit

const : 값과 주소를 변경할 수 없도록 한다.
explicit : 자동 형변환이 일어나지 않도록 한다.

02-mutable*

거의 사용하지 않아야한다.
const 함수 내에서 값의 변경을 예외적으로 허용한다.




[선형대수학] Solvability of Ax = b
Wed, 10 Aug 2022 01:31:43 GMT
$A \bold x=\bold b$
$A\bold x= \bold b$의 의미
$m\times n$ 행렬 $A$에 대해서 $A\bold x$는 아래와 같이 표현할 수 있다.
$$
A\bold x = \begin{bmatrix}\bold{a_1}\ \ \bold{a_2}\ \ \cdots \ \ \bold{a_n}\end{bmatrix} \begin{bmatrix} x_1 \ x_2 \ \vdots \ x_n \end{bmatrix} = x_1\bold{a_1} + x_2\bold{a_2} + \cdots + x_n\bold{a_n}
$$

$n$개의 열벡터($\bold{a_i}$)로 이루어진 행렬 $A$와 $n$개의 미지수로 이루어진 벡터 $\bold x$의 곱
각 열벡터($\bold{a_i}$)와  벡터 $\bold x$의 요소들($x_i$)의 선형결합 → $\bold b$
=  $A$의 column들의 liner combination이다.


따라서 $A\bold x=\bold b$ 방정식은 벡터 $\bold b$가 $A$의 Column space 안에 들어있다면 해를 가진다. (if and only if)

$$
\bold x \text{ is exist, }\ \text{if and only if }\bold b ∈ C(A)
$$



Some Terminology : 용어
elimination이 진행된 행렬 $A$에 대해, $A\bold x = 0$ 에서 

Pivot column: 행렬 $A$에서 pivot을 가지는 column
Free column: 행렬 $A$에서 pivot을 가지지 않는 column
Pivot variable: 벡터 $\bold x$에서 행렬 $A$의 pivot column에 곱해지는 변수 (요소)
Free variable: 벡터 $\bold x$에서 행렬 $A$의 free column에 곱해지는 변수 (요소)

예시 : 아래 행렬에서 pivot/free column과 pivot/free variable은?
$$
\begin{bmatrix} 
1 & 2 & 1 & 0 \
0 & 1 & 4 & -1 \
0 & 0 & 0 & 0
\end{bmatrix} 
\begin{bmatrix} 
x_1 \
x_2 \
x_3 \
x_4
\end{bmatrix} = \begin{bmatrix} 
0 \
0 \
0\
\end{bmatrix}
$$

pivot column : $[1\ \ 0 \ \ 0]^T$, $[2\ \ 1 \ \ 0]^T$
  (pivot : $1, 1$)

free column : $[1\ \ 4 \ \ 0]^T$, $[0\ \ -1 \ \ 0]^T$

pivot variable : $x_1, x_2$

free variable : $x_3, x_4$





NullSpace 구하기 : special solution
method 1

각각의 pivot variable을 free variable를 이용해서 표현하고 벡터 $\bold x$에 대입한다.


$A\bold x = \bold 0$ 꼴로 행렬을 표현한다.

$A$에 대하여 Gauss Elimination을 진행한다.

이후 $\bold x$의 pivot variable을 free variable로 표현한다.
 → fv의 선형결합으로 표현된 pc를 각각의 표현으로 분리한다. 

그렇게 free variable로 표현된 변수들을 벡터 $\bold x$에 대입한다.

벡터 $\bold x$를 각각의 free variable과 벡터*의 linear combination 으로 표현한다. ⇒ solution to $A\bold x= \bold 0$, $N(A)$
 이때, 각각의 벡터를 special solution이라고 부른다.







표현 예시

variable에 대해 다음 두 방정식이 주어졌다. (fv : $x_2, x_4, x_5$ 일 때)

$x_1 = -2x_2 + 2x_5$
$x_3 = -x_4-2x_5$


식을 활용하여 벡터 $\bold x$에 대입한다.
 $$
 \bold x = 
 \begin{bmatrix}
 x_1\x_2\x_3\x_4\x_5
 \end{bmatrix}
 \begin{bmatrix}
 -2x_2 + 2x_5\x_2\-x_4-2x_5\x_4\x_5
 \end{bmatrix}
 $$

각각의 free variable에 대한 선형결합으로 표현한다. 
 $$
 \bold x = 
 x_2 \begin{bmatrix}
 -2\1\0\0\0
 \end{bmatrix}+x_4 \begin{bmatrix}
 0\0\-1\1\0
 \end{bmatrix}+x_5 \begin{bmatrix}
 2\0\-2\0\1
 \end{bmatrix},\ \ \ x_2,x_4,x_5\in \mathbb R
 $$




method 2

free variable중 하나의 변수에는 1을 대입하고 나머지에는 0을 대입하는 과정을 반복한다.


$A\bold x = \bold 0$ 꼴로 행렬을 표현한다.  

$A$에 대하여 Gauss Elimination을 진행한다.  

여러개의 free variable중 하나를 1로 하고 다른 free variale들은 0을 대입하여 표현한다.

3번 과정을 거쳐 이제 pivot variable의 값만 알아내면 되는 벡터 $\bold x$에 대해 $A\bold x = \bold 0$ 을 풀어 벡터: special solution를 구한다.

각각의 모든 free variable에 해당 과정을 반복해서(1인 variable을 변경해줌) 적용하여 모든 special solution들을 구한다.

이렇게 구한 special colution들의 linear combination ⇒ solution to $A\bold x= \bold 0$, $N(A)$








표현 예시
fv : $x_2, x_4, x_5$ 일 때

variable에 대해 다음 두 방정식이 주어졌다. (fv : $x_2, x_4, x_5$ 일 때)

$x_1 = -2x_2 + 2x_5$
$x_3 = -x_4-2x_5$


각 case별 Special solution

$x_2 = 1, x_4 = 0, x_5 = 0$
  $$
  \bold x = 
  \begin{bmatrix}
  -2x_2 + 2x_5\1\-x_4-2x_5\0\0
  \end{bmatrix}
  \begin{bmatrix}
  -2 \1\0\0\0
  \end{bmatrix}
  $$

$x_2 = 0, x_4 = 1, x_5 = 0$
  $$
  \bold x = 
  \begin{bmatrix}
  -2x_2 + 2x_5\0\-x_4-2x_5\1\0
  \end{bmatrix}
  \begin{bmatrix}
  0 \0\-1\1\0
  \end{bmatrix}
  $$

$x_2 = 0, x_4 = 0, x_5 = 1$
  $$
  \bold x = 
  \begin{bmatrix}
  -2x_2 + 2x_5\0\-x_4-2x_5\0\1
  \end{bmatrix}
  \begin{bmatrix}
  2 \0\-2\0\1
  \end{bmatrix}
  $$



Special solution들의 linear combination
 $$
 \bold x = 
 x_2 \begin{bmatrix}
 -2\1\0\0\0
 \end{bmatrix}+x_4 \begin{bmatrix}
 0\0\-1\1\0
 \end{bmatrix}+x_5 \begin{bmatrix}
 2\0\-2\0\1
 \end{bmatrix},\ \ \ x_2,x_4,x_5\in \mathbb R
 $$







special solution?

NullSpace를 이루는 vector
special solution은 free variable(=free column)의 개수와 동일하다.
free variable의 개수 = 전체 column의 갯수 - pivot의 개수 ($n-r$)




Complete Solution
Theorem
벡터 $\bold w$가 $A\bold x= \bold b$의 임의의 solution이라고 가정하자. Then,

$A\bold x= \bold b$ 의 solution이 $\bold y$이면 $\bold y = \bold w+\bold z$ 이다. ($\bold z \in N(A)$)
pf)

$\text{if }\ A\bold y = \bold b$ 이라면,
 $$
 A\bold y -  A\bold w = \bold b - \bold b =0\\ \A(\bold y - \bold w) = 0
 $$

따라서 벡터 $\bold y - \bold w$는 NullSpace에 속하는 vector이다.
 $$
 \bold y - \bold w \in N(A)
 $$

벡터 $\bold z$를 NullSpace에 속하는 또다른 vector라고 하면, linear combination 성질에 의해
 $$
 \bold y-\bold w = \bold z\ \ (\bold z \in N(A))\\ \ \bold y = \bold w + \bold z
 $$



↔  $\bold y = \bold w+\bold z$ ($\bold z \in N(A)$) 이면 $\bold y$는 $A\bold x= \bold b$의 solution이다.
pf)

$\text{if }\ \bold y = \bold w+\bold z$ 이라면,
 $$
 A\bold y =  A(\bold w + \bold z)= A\bold w + A\bold z
 $$

이때, 처음 Theorem의 가정에 따라 $A\bold w = \bold b$이고 $\bold z$는 NullSpace에 속하는 벡터이므로 $A\bold z = \bold 0$
 $$
 \bold b + \bold 0 = \bold b
 $$

따라서 $\bold y$는 $A\bold x= \bold b$의 solution이다.
 $$
 A\bold y = \bold b
 $$





$\bold y = \bold w + \bold z$ 를 이용하여 모든 solution을 표현할 수 있다.
→ 즉, NullSpace를 구하여 그 벡터 ($\bold z \in N(A)$)에 임의의 solution $\bold w$를 더하면 complete solution을 표현할 수 있다. 




기하학적 의미

임의의 solution과 NullSpace의 vector(special solution)을 더한 vector의 종점은 여전히 $A\bold x = \bold b$ 안에 들어있다.
따라서 NullSpace의 어떤 solution과 임의의 solution의 합으로 $A\bold x = \bold b$의 모든 solution을 표현할 수 있다.





과정

$A\bold x = \bold b$의 아무 solution을 찾는다. $(=x_p)$

임의의 어떤 solution이던간에 관계없음
따라서 가장 쉽게 solution을 찾을 수 있도록 fv를 0으로 가정하고 $A\bold x = \bold b$를 풀어서 particular solution을 구한다.


$A\bold x = \bold 0$의 solution을 찾는다. → Null Space를 찾는다. $(N(A) = x_n)$

$x_p + x_n$이 $A\bold x = \bold b$의 complete solution이 된다.
 (NullSpace의 모든 vector에 대해 진행하여 새로운 벡터 공간을 정의함)



완전해(complete solution)은 특수해들의 선형조합이다.


특수헤?
$A\bold x = \bold 0$ 의 해 (=Special solution) : NullSpace의 벡터
$A\bold x = \bold b$의 임의의 solution (=particular solution)






[선형대수학] Subspace
Tue, 09 Aug 2022 14:40:44 GMT
Subspace
Definition Vector Space

벡터들을 모아둔 집합이 다음 공리들을 만족할 때 이를 벡터공간: vector space이라고 부른다.


$V$에 속하는 모든 벡터에 대해 교환법칙이 만족
  $$
  \bold u + \bold v = \bold v + \bold u\ \  ∀\bold u, \bold v ∈ V
  $$

$V$에 속하는 모든 벡터에 대해 결합법칙이 만족
  $$
  (\bold u + \bold v) + \bold w = \bold u + (\bold v + \bold w)\ \ ∀\bold u, \bold v, \bold w ∈ V
  $$

$V$에 속하는 모든 벡터에 대해 0벡터가 존재
→ There exists a vector $\bold 0 ∈ V$ , called the zero vector. such that
 $$
 \bold v + \bold 0 = \bold v\ \ ∀\bold v ∈ V
 $$

$V$에 속하는 모든 벡터에 대하여 그 벡터의 음의 벡터와의 합은 0벡터를 만족
→ For every $\bold v ∈ V$ , there exists a vector $−\bold v ∈ V$ such that 
 $$
 \bold v + (−\bold v) = 0\ \ \forall \bold v\in V
 $$

$V$에 속하는 모든 벡터에 대해 분배법칙이 만족 ($c$는 상수)
  $$
  c(\bold u + \bold v) = c\bold u + c\bold v\ \ ∀\bold u, \bold v ∈ V
  $$

$V$에 속하는 모든 벡터에 대해 다음을 만족
  $$
  1 · \bold v = \bold v\ \ \forall \bold v \in V
  $$

$V$에 속하는 모든 벡터의 상수곱에 대해 결합법칙이 만족
  $$
  (c_1c_2)\bold v = c_1(c_2\bold v)\ \ \forall \bold v \in V
  $$

$V$에 속하는 모든 벡터의 상수연산에 대해 분배법칙이 만족
  $$
  (c_1 + c_2)\bold v = c_1\bold v + c_2\bold v\ \ \forall \bold v \in V
  $$





Definition of Subspace

vector space $V$의 부분공간(집합*) $S$가 다음 2개의 조건을 만족할 때, $S$를 Subspace라고 한다.

$S$에 속하는 벡터 $\bold v, \bold w$ 에 대해 다음을 만족 ($c$는 상수)

더하기 연산에 대해 “닫혀있다.”*
 $$
 \bold v + \bold w ∈ S
 $$

scailing 연산에 대해 “닫혀있다.”
 $$
 c \bold v ∈ S
 $$


→ 즉, subspace $S$는 linear combination*에 대하여 닫혀있다.(closed under)

닫혀있다? (closed under)
$S$에 속하는 벡터에 연산을 진행하더라도, 연산을 진행한 결과 벡터가 여전히 부분공간 $S$안에 존재한다. 


liner combination : 선형결합
  $$
  \forall \bold{v, w}\in S\ \rightarrow \ \ c\bold v+ d \bold w \in S\ \ (\forall c, d\in \mathbb R)
  $$



subspace와 subset의 차이점
subset : 단순히 전체집합의 일정 원소를 갖는 부분집합
subspace : subset이 어떤 특정 조건을 만족해야함






Subspace인지 아닌지 확인하는 방법

정의를 이용해서 공간 $S$에 속하는 임의의 벡터 $\bold v$와 $\bold w$를 정한뒤, liner combination의 결과가 여전히 $S$ 안에 존재하는 것을 보인다.

이때, 어떤 벡터공간의 subspace인지를 정하는 것은 벡터의 차원이 결정한다.  

ex)* 2차원 벡터이면 2차원 벡터공간($\mathbb R^2$)의 subspace
  $$
  \begin{bmatrix} 1 \ 1 \end{bmatrix} \rightarrow \mathbb R^2
  $$

예시



다음 집합이 어떤 벡터공간의 Subspace인지를 확인하여라.
  $$
 \left\{ c  \begin{bmatrix} 1 \\1    \end{bmatrix},\ \forall c\in\mathbb R \right\}
 $$
  → 위 집합은 $[1,\ 1]^T$ 벡터의 모든 scalar multiplication(=scailing)들의 집합을 의미한다.
 a. 어떤 벡터 $\forall \bold{v, w}\in S$를 정의
  $$
     \forall \bold v, \bold w \in S,\ \ \forall a,b\in\mathbb R\\\ \\\bold v=a\begin{bmatrix} 1 \\1    \end{bmatrix},\bold w=\ b\begin{bmatrix} 1 \\1    \end{bmatrix}
   $$
  b. liner combination의 결과가 여전히 $S$ 안에 존재함을 보임
  $$
     c\bold v + d \bold w =ca\begin{bmatrix} 1 \\1    \end{bmatrix} + d b\begin{bmatrix} 1 \\1    \end{bmatrix}\\\ \\ = (ca+db)\begin{bmatrix} 1 \\1    \end{bmatrix} \in S
   $$


  따라서 $S$는 $\mathbb R^2$의 subspace이다.  

다음 집합이 어떤 벡터공간의 Subspace인지를 확인하여라.
$$
 \left\{ c  \begin{bmatrix} 1 \\1    \end{bmatrix} +  d  \begin{bmatrix} 2 \\3    \end{bmatrix},\ \forall c,d\in\mathbb R \right\}
$$

→ 위 집합은 $[1,\ 1]^T$ 벡터와 $[2,\ 3]^T$벡터의 모든 linear combination들의 집합을 의미한다.
 a. 어떤 벡터 $\forall \bold{v, w}\in S$를 정의
   $$
     \forall \bold v, \bold w \in S,\ \ \forall a_1,a_2,b_1,b_2\in\mathbb R\\\ \\\bold v=a_1\begin{bmatrix} 1 \\1    \end{bmatrix}+a_2\begin{bmatrix} 2 \\3    \end{bmatrix},\bold w=\ b_1\begin{bmatrix} 1 \\1    \end{bmatrix}+ b_2\begin{bmatrix} 2 \\3   \end{bmatrix}
     $$
   b. liner combination의 결과가 여전히 $S$ 안에 존재함을 보임
   $$
     c\bold v + d \bold w =ca_1\begin{bmatrix} 1 \\1    \end{bmatrix}+ca_2\begin{bmatrix} 2 \\3    \end{bmatrix}+d b_1\begin{bmatrix} 1 \\1    \end{bmatrix}+ db_2\begin{bmatrix} 2 \\3   \end{bmatrix}\\\ \\ = (ca_1+db_1)\begin{bmatrix} 1 \\1    \end{bmatrix}+(ca_2+db_2)\begin{bmatrix} 2 \\3 \end{bmatrix} \in S
     $$

따라서 $S$는 $\mathbb R^2$의 subspace이다.




Properties of Subspace

subspace에는 0벡터가 반드시 포함되어야한다.
 $$
 0 ∈ S
 $$

원점을 지나는 직선은 subspace이다.
 (원점을 지난다는 것은 0벡터를 가진다는 의미이기 때문이다.)

$\mathbb R^n$은 자기자신의 subspace이다..
 (부분집합 개념이랑 동일함)

$\mathbb R^3$ 공간에서 가능한 subspace는 ${0}$,  $0$을 지나는 직선, $0$을 지나는 평면이다.





Space of Matrix
행렬에 대해 정의되는 4개의 space
Column Space $$C(A)$$

행렬 $A$에 있는 모든 column에 대한 liner combination의 집합

$$
C(A) = {A \bold x : ∀ \bold x}
$$
 x벡터의 각 요소가 A의 column에 곱해지는 상수값(scailing)으로 생각

column space의 표현 예시
  $$
  \bold x = \begin{bmatrix} x_1 \ x_2 \end{bmatrix},\ \ A=\begin{bmatrix} 1 & 0 \ 0 & 1\end{bmatrix}= \begin{bmatrix} \bold{a_1}\ \ \bold{a_2}\end{bmatrix}
  $$
  $$
  A\bold x= x_1\bold{a_1} + x_2\bold {a_2}\\ \ =\left{   \begin{bmatrix} x_1 \x_2    \end{bmatrix} ,\ \forall \bold x \right} = \mathbb R^2
  $$
  → 2차원 벡터공간
  $$
  \bold x = \begin{bmatrix} x_1 \ x_2  \ x_3\end{bmatrix},\ B=\begin{bmatrix} 1 & 2 & 3 \ 1 & 2 & 3\end{bmatrix}= \begin{bmatrix} \bold{b_1}\ \ \bold{b_2}\ \ \bold{b_3}\end{bmatrix}
  $$
  $$
  B\bold x= x_1\bold{b_1} + x_2\bold {b_2}+x_3\bold {b_3}\\ \ =\left{   (x_1+2x_2+3x_3)\begin{bmatrix}1 \1    \end{bmatrix} ,\ \forall \bold x \right} \in \mathbb R^2
  $$
  → 2차원 공간에서 원점을 지나는 한 직선

subspace?

$A$가 $m\times n$ 행렬일 때, $A\bold x$는 $m\times1$인 $m$차원 벡터를 의미한다.

벡터  $\bold x$가 $A$의 오른쪽에 곱해지기 위해서 $\bold x$는 $n$차원 벡터여야만 한다.
  $$
  C(A)=\left{ A\bold x,\ \ \forall \bold x \in \mathbb R^n \right} \sube \mathbb R^m
  $$

따라서 $C(A)$는 $\mathbb R^m$의 subspace이다.




Row Space $C(A^T)$

행렬 $A$에 있는 모든 행에 대한 liner combination 을 모아둔 공간
 ↔ $A$의 transpose matrix의 Column space

 x벡터의 각 요소가 A의 row에 곱해지는 상수값(scailing)으로 생각
$$
R(A) =C(A^{T}) = {A^Tx : ∀ x}
$$
Null Space $$N(A)$$ 💫

$A\bold x = 0$을 만족하는 모든 solution vector $\bold x$들을 모아둔 공간

$$
N(A) = {\bold x : \ A\bold x=0}
$$
x벡터의 각 요소가 A의 column에 곱해지는 상수값(scailing)으로 생각

$A$의 역행렬과 Null Space의 관계
  $$
  \exist\ A^{-1} \rightarrow\ N(A) = \left{ \bold 0 \right }
  $$
  → invertible matrix $A$의 Null space는 0벡터 뿐이다.
  Pf)
  $$
  A\bold x = 0
  $$
  양변에 $A$의 역행렬을 곱한다. 
  $$
  A^{-1}A\bold x = 0
  $$
  역행렬에 정의에 따라 역행렬과 기존행렬의 곱은 항등행렬로 사라지므로,
  $$
  \bold {x}=0
  $$

subspace?

$A$가 $m\times n$ 행렬일 때, $A\bold x$는 $m\times1$인 $m$차원 벡터를 의미한다.

벡터  $\bold x$가 $A$의 오른쪽에 곱해지기 위해서 $\bold x$는 $n$차원 벡터여야만 한다.
  $$
  N(A)=\left{ \bold x,\ \ A\bold x =0 \right} \sube \mathbb R^n
  $$

따라서 $\bold x$를 원소로 갖는 집합 $N(A)$는 $\mathbb R^n$의 subspace이다.




+여기에 $A$의 transpose matrix에 대한 NullSpace $N(A^T)$까지 포함하여 4개의 space를 갖는다.



[선형대수학] Inverse Matrix & Gauss-Jordan Elimination
Thu, 04 Aug 2022 06:03:46 GMT
Inverse Matrix
Definition of Inverse Matrix

행렬의 앞/뒤 어디에 곱하든 그 결과가 항등행렬 $I$가 되는 행렬

용어

invertible, non-singular : 역행렬이 존재하는 행렬
singular : 역행렬이 존재하지 않는 행렬

Properties of Inverse Matrix

Inverse Matrix는 유일하다. (1개이다)
 증명
a. 만약 행렬 $A$가 역행렬 $B$와 $C$를 가진다고 가정하자.
$$
AB = BA = I,\ \ AC=CA=I
$$
b. $CA=I$의 양변에 $B$를 곱하면,
$$
CAB = B 
$$
c. 이때, a에서 한 가정때문에 $AB=I$이다.
$$
C = B 
$$
d. 역행렬 $B$와 $C$는 동일한 행렬일 수 밖에 없다. 따라서 Inverse Matrix는 유일하다.

$n\times n$ 행렬 $A$가 invertible하면 $A$는 $n$개의 pivot을 가진다.
↔️  $n\times n$ 행렬 $A$가 $n$개의 pivot을 가지면 $A$는 invertible matrix이다.
증명
a. $n\times n$ 행렬 $A$가 $n$개의 pivot을 가지면, Gauss Elimination을 이용하여 $A$를 row echelon form matrix으로 나타낼 수 있다.
 *ex)* $2\times2$ 행렬을 G.E하여 pivot $1, -4$ 2개를 가지는 row echelon form으로 변환했다.
$$
\begin{bmatrix}
1 & 2 \
3 & 2
\end{bmatrix} \rightarrow^{G.E} \begin{bmatrix}
\color{blue}1 & 2 \
0 & \color{blue}-4
\end{bmatrix}
$$
b. 따라서 $Ax=b$는 무조건 해을 가지므로 해를 구하기 위해서 수식을 변형시키면 다음과 같다.
$$
x = A^{-1}b
$$
c. 따라서 행렬 $A$는 invertible matrix이다.  



$L$: Low transform matrix(or $U$: Upper transform matrix)이 invertible matrix라면, 대각성분에 0이 존재하지 않는다.
↔  대각성분에 0이 없다면 $L$or$U$ 행렬은 invertible matrix이다.   
: pivot이 n개 존재하기 위해서는 0인 성분을 가져서는 안된다. (2번 성질과 동일한 의미)

Digonal Matrix: 대각행렬 $A$의 대각성분 중에서 0이 1개라도 존재한다면, $A$는 singular matrix이다.
↔️  singular matrix인 Digonal Matirx $A$의 대각성분에는 적어도 0이 1개 이상존재한다.  
: $0$인 원소를 대각성분에 가진다면 pivot은 0이 될 수 없기 때문에 $n\times n$ 행렬이 $n$개의 pivot을 가지지 않게 된다. (2번 성질과 동일한 의미)

$A$가 역행렬을 가지면 선형방정식 $Ax = b$는  $x = A^{-1}b$인 유일한 해를 가진다. (2번 성질과 동일한 의미)

선형방정식 $Ax = 0$에서 $x$가 영벡터가 아니라면, $A$는 singular matrix이다.


증명
  a. 일반적인 선형방정식을 풀 때처럼(3번)* 양변에 $A$의 inverse matrix를 곱한다.
$$
x=A^{-1}0
$$
  b. $0$이 곱해졌기 떄문에 우변의 결과는 $0$이고, 따라서 좌변은 다음과 같다. 
  $$
  x=0
  $$
  c.  따라서 $A$가 역행렬을 가지면(a) $Ax = 0$의 유일한 해는 $x=0$ (영벡터) 이다.
   ↔️   $x≠0$이면, $A$는 역행렬을 가지지 않는다.

(드모르간의 정리) $n\times n$ 행렬 $A$, $B$가 invertible matrix이면 다음의 식이 만족한다.
 $$
 (AB)^{-1} = B^{-1}A^{-1}
 $$
 증명
 a. 우변에 $AB$를 곱하여 정리한다.
   $$
   AB(B^{-1}A^{-1})=AIA^{-1} = I
   $$
 b. 정리한 결과가 항등행렬이므로, inverse matrix의 definition에 따라 성질이 참임을 보일 수 있다.  

$2\times 2$ 행렬이 invertible이기 위한 조건 (필요충분)

조건 : 행렬식*이 $0$이 아니다.
  $$
  \text{if and only if}\ \ ad-bc \neq 0
  $$

역행렬을 구하는 방법
$$
  \begin{bmatrix} a & b \ c & d \end{bmatrix}^{-1} = \frac{1}{ad-bc}\begin{bmatrix} d & -b \ -c & a \end{bmatrix}$$




- *증명*  
  a. $a=0$ 이면, Gauss Elimination 과정에서 1행과 2행을 바꾸면서 $c$와 $b$가 pivot이 된다. pivot과 invertible의 관계에 의해 invertible 이려면 $c≠0, b≠0$  
$$
  \begin{bmatrix} 0 & b \ c & d \end{bmatrix} \rightarrow^{G.E} \begin{bmatrix}  \color{blue}c & d \  0 & \color{blue}b\end{bmatrix}$$
  $$
 \text{if}\ a=0,\ \ c\neq0 \text{ and } b\neq 0$$
   b. $a\neq0$ 이면, Gauss Elimination의 결과에 따라  $a$와 $d-{cb\over a}$가 pivot이 된다. pivot과 invertible의 관계에 의해 invertible이려면 $d-{cb\over a}\neq0 \rightarrow ad-cb \neq0$
   $$
    \begin{bmatrix} a & b \ c & d \end{bmatrix} \rightarrow^{G.E} \begin{bmatrix}  \color{blue}a & b\  0 & \color{blue}{d-\frac{cb}{a}}\end{bmatrix}$$
  $$
      \text{if}\ a\neq0,\ \ ad-cb \neq0
  $$



Gauss-Jordan Elimination
Gauss Elimination의 한계

Inverse matrix의 성질에 따라, $n\times n$ 행렬이 $n$개의 pivot을 가지면 Invertible하다는 것을 알 수 있다.

따라서 Gauss Elimination을 이용하여 행렬을 row echelon form으로 변환하고 pivot의 수를 세서 Invertible한지 아닌지를 알아낼 수 있다. 그러나 inverse matrix를 구하기 위해서 Gauss Elimination을 진행하기에는 계산량이 너무 과하다. $O(n^2)$
Gauss-Jordan elimination
Gauss-Jordan elimination은 일반적인 Gauss elimination과 크게 다르지 않지만, 행렬의 inverse matrix를 더 쉽게 구할 수 있도록 해준다.

행렬과 inverse matrix를 곱한 결과인 항등행렬 $I$의 각 열을 만드는 inverse matrix의 각 열 벡터를 계산하는 아이디어.

과정 (in $3\times 3$ matrix)
$$
AA^{-1} = I
$$

inverse matrix를 모르는 상태이므로 임의의 요소로 행렬을 만든다.

inverse matrix의 각 열을 하나의 열 벡터로 취급하여 표현한다. 
 $$
 A^{-1} = \begin{bmatrix} x_1 & y_1 & z_1 \ x_2 & y_2 & z_2\ x_3 & y_3 & z_3 \end{bmatrix} = \begin{bmatrix} \bold{x} & \bold{y} & \bold{z} \end{bmatrix}
 $$

이렇게 표현한 행렬을 이용하면, $AA^{-1}$을 다음과 같은 수식으로 표현할 수 있다.
 $$
 AA^{-1} = \begin{bmatrix} A\bold{x} & A\bold{y} & A\bold{z} \end{bmatrix}=I
 $$

항등행렬의 각 열을 $\bold{e_1, e_2, e_3}$으로 두면, 다래와 같은 3개의 방정식을 만들어낼 수 있다.
 $$
 I = \begin{bmatrix} 1 & 0 & 0 \ 0& 1 & 0\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} \bold{e_1} & \bold{e_2} & \bold{e_3} \end{bmatrix}
 $$
 $$
  A\bold{x} = \bold{e_1}\
  A\bold{y} = \bold{e_2}\
  A\bold{z} = \bold{e_3}\
 $$

이는 연립방정식의 형태와 크게 다르지 않기에, 3개의 방정식을 한번에 표현하여 Gauss Elimintation을 진행하여 Digonal Matrix를 만든다. 
 *일반적인 Gauss Elimination과 다른점은 위로도 행 소거연산이 가능하다.
 $$
 \left[\begin{array}{c|ccc}A & \bold{e_1} & \bold{e_2} & \bold{e_3} \end{array}\right]
 $$

elimination이 끝나면 $A$가 항등행렬로 표현될 수 있게 pivot이 1이 되도록 행마다 상수곱을 해준다.
 → 즉, Elimination을 끝낸 $A$행렬이 항등행렬이 된다. 

$A\bold{x} = \bold{e_1}$가 $I\bold{x} = A^{-1}$의 첫번째 열이 된다.
 → 즉, Elimination을 끝낸 $\begin{bmatrix} \bold{e_1} & \bold{e_2} & \bold{e_3} \end{bmatrix}$ 행렬이 Inverse matrix가 된다.
 $$
 [A|I] \rightarrow^{G-J} [I|A^{-1}]
 $$


G-J 과정을 거쳐 $A$를 항등행렬로 표현하는 과정은, 역행렬 $A^{-1}$을 곱한 결과와 동일하기 때문에 $A$와 함께 표현된 항등행렬$I$에 $A^{-1}$이 곱해졌다고 생각하면 $A^{-1}$을 얻을 수 있다. 
Gauss-Jordan elimination Example.
$$
A=\begin{bmatrix}2 & -1 & 0 \ -1 & 2 & -1 \ 0 & -1 & 2 \end{bmatrix}
$$

augmentend matrix form
 $$
 \left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \ -1 & 2 & -1 & 0 & 1 & 0 \ 0 & -1 & 2  & 0 & 0 & 1 \end{array}\right] 
 $$

Gauss-Jordan Elimination
 $$
 \rightarrow^{G.E}\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \ 0 & \frac{3}{2} & -1 & \frac{1}{2} & 1 & 0 \ 0 & -1 & 2  & 0 & 0 & 1 \end{array}\right]\ \rightarrow^{G.E}\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \ 0 & \frac{3}{2} & -1 & \frac{1}{2} & 1 & 0 \ 0 & 0 & \frac{4}{3}  & \frac{1}{3} & \frac{2}{3} & 1 \end{array}\right]
 $$
 G.E *upward
 $$
 \rightarrow^{G.E\ up}\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \ 0 & \frac{3}{2} & 0 & \frac{3}{4} & \frac{3}{2} & \frac{3}{4} \ 0 & 0 & \frac{4}{3}  & \frac{1}{3} & \frac{2}{3} & 1 \end{array}\right]\ \rightarrow^{G.E\ up}\left[\begin{array}{ccc|ccc}2 & 0 & 0 & \frac{2}{3} & 1 & \frac{1}{2} \ 0 & \frac{3}{2} & 0 & \frac{3}{4} & \frac{3}{2} & \frac{3}{4} \ 0 & 0 & \frac{4}{3}  & \frac{1}{3} & \frac{2}{3} & 1 \end{array}\right]
 $$

Scaliling
 $$
 \left[\begin{array}{ccc|ccc}1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4} \ 0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2} \ 0 & 0 & 1  & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \end{array}\right]
 $$


역행렬을 갖지 않는 행렬에 Gauss-Jordan elimination을 적용하면 breakdown이 일어나서 해가 존재하지 않는다.
→ 역행렬이 존재하지 않음을 알 수 있다.

Person	Student
상위클래스	하위클래스
기초(base)클래스	유도(derived)클래스
슈퍼(super)클래스	서브(sub)클래스
부모클래스	자식클래스