import pandas as pd

service = pd.Series(['예금', '출금', '여신', '수신', '보험', '대출'])

employee = pd.Series(['영희', '철수', '기영', '길동', '장금', '희동'])

df = pd.DataFame({
    "service" : service,
    "employee" : employee
})

# 칼럼 가져오기
df[['service', 'employee']]
cols = ['service', 'employee']
df[cols]

# csv 저장
df.to_csv('bank.csv')
df.to_csv('bank.csv', index=False)
df.to_csv('bank.csv', index_col='컬럼명')
# csv 불러오기
df = pd.read_csv('bank.csv')

df 는 [[]], series는 []

list 자료형

하나의 카테고리 내부에 여러가지 자료를 저장할 때 사용하는 자료형

• 인덱스가 부여된다는 특징 (0부터 시작)
• 데이터 분석 관점에서 여러개의 정보를 하나의 변수공간에 순차적으로 담을 수 있다는 점이 매력적

list 자료형에 쓰이는 함수

추가

# 초기 리스트 정의 list = []
# 리스트에 요소 추가
list_.append('happiyoung')

정렬

정렬은 탐색을 편리하게 해준다는 점에서 꼭 필요한 함수이다.

• 오름차순 정렬을 한다면 n 번째 원소는 n-1까지보다는 적어도 무조건 크다는 의미를 내포
• 내림차순 정렬을 한다면 n번째 원소는 n-1까지보다는 적어도 무조건 작다는 의미를 내포

위의 두가지 정의를 이용해서 정렬 후에 편하게 원소에 접근가능

# 정렬
list_ = sorted(list_, [정렬할 조건 명시])

정렬 조건

1. reverse = True/False
2. key=lambda x: x[1] # 특정 요소 기준 정렬
3. sorted(data, key=lambda x: (x[0], x[1])) # x[0] 오름차순, 그다음 x 오름차순
4. sorted(data, key=lambda x: (x[0], -x[1])) # x[0] 오름차순, 그 안에서 x 내림차순
5. 길이 기준 정렬: sorted(words, key=lambda x: len(x))
6. 문자열 슬라이싱 활용: sorted(s, key=lambda x: (x.split()[1], x.split()

인덱스와 값을 모두 추출하고싶을때

enumerate() 함수를 사용하여, 반복문에 넣어서 인덱스와 함께 반환

list_ = ["happiyoung", "unhappy"]

for index, value in enumerate(list_):
# => 이렇게 인덱스와 값을 모두 사용하여 반복문내에서 지지고 볶고~
    print(index, value) # 0happiyoung \n 1unhappy

dict 자료형

key와 value 쌍을 가지고 있어서, key를 통해 바로 접근가능하기 때문에 검색이 빠르다는 장점을 가진다.

• 유형이 명확하게 정해진 검색을 하고자 한다면 딕셔너리 자료형이 필수

dict 자료형에 쓰이는 함수

생성

dict_ = {"name" : "happiyoung", "job" : "developer" }

출력, 변경

dict_["name"] # happiyoung
dict_["job"] # developer

dict_["job"] = "home-protector"
dict_["lover"] = ["mom", "dad", "sisters"]

키, 값

# key 확인
dict_.keys # dict_keys(["name", "job"])

# value 확인
dict_.values # dict_values (["happiyoung", "developer"])

# (key,value) 쌍으로 확인
dict_.items() # dict_items ([("name", "happiyoung"), ("job", "developer")]

zip

좌측, 우측 날을 맞춰서 1:1 매칭을 통해 이어 붙이는 zipper 처럼 두 리스트를 길게 쭉 열을 맞춰 나열한 다음 매칭해서 가져오는 함수

...
for key, value in zip(dict_.keys(), dict_.values()):

슬라이싱/인덱싱

문자열이나, 리스트 같이 여러 원소가 모여있는 집합에서 각각의 요소에 접근하고자 한다면 이 개념을 사용하면 된다.

• 슬라이싱을 통해 문자열의 일부분을 잘라온다.
• 인덱싱을 통해 특정 자리에 있는 값를 가져온다.

list_[0] # 0번째 요소를 가져오겠다.
list_[0:3] # 0부터 3-1 까지 요소를 가져오겠다.
list_[::2] # 전체 원소범위에서 1칸씩 건너서 가져오겠다.

내장함수

# 합계 (boolean 자료형도 sum 가능, True : 1, False : 0 )
sum(list_)
# 최댓값
max(list_)
# 최소값
min(list_)
# 항목의 개수
len(list_)
# 반올림
round(1.2323, 2)

문자열

text = "happiyoung is unhappy"
# 문자 변경
text = text.replace("unhappy", "happy")
# 문자열도 리스트처러 슬라이싱 가능
# 문자열 분리
text.split() # 띄어쓰기 단위 분리
text.split('h') # 문자단위 분리

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다. computer[i][i]는 항상 1입니다.

접근 방식

연결된 컴퓨터 묶음이 몇개인가를 묻는 문제

1. 아직 방문하지 않은 컴퓨터를 찾는다.
2. 방문하지 않은 컴퓨터에 방문하여, 그 컴퓨터와 연결된 애들을 전부 방문한다.
3. 더이상 연결된 곳이 없다면 네트워크 1개를 발견한 것
4. 다시 아직 방문하지 않은 컴퓨터를 찾는다. (반복 수행)

DFS 를 한번 돌릴 때마다 네트워크 1개를 찾는 것과 동일

준비물 챙기기

1. 연결 여부가 포함된 맵
   • 행과 열이 의미하는 바가 무엇인지 생각해보기
2. 방문한 컴퓨터인지 표시하는 컴퓨터 방문록
   • N개의 컴퓨터라면 N만큼 길이의 방문 배열 존재

     visited = [False] * n

     DFS 함수가 해야하는 일 정리

3. 현재 컴퓨터 방문처리
4. 현재 컴퓨터와 연결된 부분 (맵상에서 1인부분) 확인
5. 연결되어있는데, 아직 방문 안했다면 재귀로 방문
   • computers[now][next] == 1 이면 무슨 뜻일까? now번 컴퓨터와 next번 컴퓨터가 연결되어 있다는 의미

해결

def solution(n, computers):
    # computers 행렬에서 행과 열은 각각 컴퓨터의 총 개수와 동일
    # 방문한 컴퓨터를 또 방문하지 않도록 방문 체크 배열 생성
    visited = [False] * n
    # 방문 여부 확인후
    #   방문 x => 그 노드를 시작으로 dfs => 네트워크 + 1
    #   방문 o => pass
    networks = 0
    def dfs(now):
        # 방문 표시
        visited[now] = True
        # 하나의 컴퓨터 종류에 대해서 연결 여부 탐색
        for next in range(n):
            # 연결이 되어있고 (1이고) 방문하지 않은 경우 dfs 진행 (파고 들어가)
            if computers[now][next] == 1 and not visited[next]:
                dfs(next)
    # 다음 컴퓨터로 이동하는 로직 (컴퓨터 마다 하나씩 실행)
    for i in range(n):
        if not visited[i]:
            dfs(i)
            networks += 1
    return networks

탬플릿

1. 네트워크 개수
2. 섬의 개수
3. 연결요소개수
4. 무리 개수

for 모든 정점:
    아직 방문 안 했으면:
        탐색 한번
        count += 1

BFS로 푸는 문제의 특징

한 칸 이동할 때마다 비용이 전부 1칸으로 같다면,

BFS는 가까운 칸부터 한 층씩 탐색하므로 처음 도착한 경로가 곧 최단거리가 됩니다.

즉,

DFS: 갈 수 있는 데까지 막 가봄 → 최단거리 보장 X BFS: 거리 순서대로 탐색 → 최단거리 보장 O

BFS는 최단 거리를 보장하기에

BFS는 먼저 도착한 경로가 가장 짧다

기본 BFS 구조

from collections import deque

def solution(maps):
    answer = 0
    # 맵의 크기 측정
    n = len(maps)
    m = len(maps[0])
    # 맵의 좌표 값이용 (방문 노드 처리)
    visited = [[False] * m for _ in range(n)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    def bfs(x,y):
        q = deque()
        q.append((x,y))
        visited[x][y] = True
        while q :
            cx, cy = q.popleft()
            # 현재 위치 (cx, cy)에서 상하좌우
            for d in range(4):
                nx = cx + dx[d]
                ny = cy + dy[d]

                # 맵밖을 나가지 않도록 조절
                if 0<= nx < n and 0 <= ny < m:
                    # 방문 여부 파악 + 벽이 아닌 조건
                    if not visited[nx][ny] and maps[nx][ny] ==1:
                        # 방문 표시
                        visited[nx][ny] = True
                        # 이동할 다음 위치 큐에 저장
                        q.append((nx,ny))
    bfs(0,0)
    return answer

하지만 이 문제에서는 최단 거리의 길이를 반환해야하기 때문에, 위치 저장과 더불어 거리저장도 함께 이루어 져야한다.

최단거리 수까지 출력하는 BFS

노드의 인자로 (큐에 들어갈 요소) 거리정보 추가

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    def bfs(x,y):
        q = deque()
        q.append((x,y,1)) # 시작 칸도 포함 하므로 거리 1
        visited[x][y] = True
        while q :
            cx, cy, dist = q.popleft() # 거리 정보도 같이 추출
            # 도착했는지 여부 확인 (문제에서 n,m이 도착 지점이라고 제시)
            if cx == n - 1 and cy == m - 1:
                return dist

            for d in range(4):
                nx = cx + dx[d]
                ny = cy + dy[d]

                if 0<= nx < n and 0 <= ny < m:
                    if not visited[nx][ny] and maps[nx][ny] ==1:
                        visited[nx][ny] = True
                        # 한칸 이동 한 정보를 큐에 넣는데, 칸수 증가 +1
                        q.append((nx,ny, dist+1))
        return -1 # 이동이 안되면 -1 리턴
    return bfs(0,0)

• 노드를 거쳐가면서 추가적으로 필요한 정보가 있다면, 노드의 인자로 한개 더 만들면 된다.

• 함수의 return 문을 이용해 bfs 이후 최종 출력할 값을 지정한다.

1. 뻗어나가는 가지가 무엇인가 2. 각 노드에 해당하는 값은 무엇인가 3. 더이상 가지가 뻗어나가지 않는 종료조건은 무엇인가

DFS는 언제 쓰이는 가?

• 선택지가 계속 분기됨

• 끝까지 가봐야 정답인지 알 수 있음
• 가능한 모든 경우를 세야 함

기본 유형

dfs(index, total)

• index: 지금 몇 번째 노드를 처리중인지
• total: 지금까지 만든 트리

예시 (타겟 넘버)

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

** 이 문제를 DFS로 생각하는 법**

start = 0
├─ +1 → 1
│  ├─ +1 → 2
│  │  ├─ +1 → 3
│  │  └─ -1 → 1
│  └─ -1 → 0
│     ├─ +1 → 1
│     └─ -1 → -1
└─ -1 → -1
   ├─ +1 → 0
   │  ├─ +1 → 1
   │  └─ -1 → -1
   └─ -1 → -2
      ├─ +1 → -1
      └─ -1 → -3

“현재 몇 번째 숫자까지 처리했는가?” “지금까지 합이 얼마인가?”

dfs(index, total)

• index: 지금 몇 번째 숫자를 처리 중인지
• total: 지금까지 만든 합

그리고 다음 숫자에 대해 두 갈래

dfs(index + 1, total + numbers[index]) dfs(index + 1, total - numbers[index])

완성 코드

def solution(numbers, target):
    answer = 0

    def dfs(index, total):
        nonlocal answer

        # 모든 숫자를 다 사용한 경우
        if index == len(numbers):
            if total == target:
                answer += 1
            return

        # (가지치기) 현재 숫자를 더하는 경우 (재귀호출)
        dfs(index + 1, total + numbers[index])

        # (가지치기) 현재 숫자를 빼는 경우 (재귀호출)
        dfs(index + 1, total - numbers[index])

    dfs(0, 0) # 초기 노드
    return answer

정렬을 왜 할까?

• 오름차순/내림차순 정렬시에 가져오는 효과에 대해 집중
• 정렬을 진행한다면 도중에 멈출 수 있는 하나의 조건을 가져올 수 있음
• 정렬을 진행한다면 최대, 최소를 고려해 로직을 짜고, 특정 값 이후는 작으니까 절대 불가 또는 특정 값 이후는 크니까 절대 불가 이런 관점을 가져올 수 있음

문자열 슬라이싱

• 인덱스 조심하기 (0부터 시작하는지 1부터 시작하는지)

정렬 함수

• list.sort() : 리스트에 대해서 정렬 후 저장
• sorted : 정렬 후 리스트 반환 (원본 변경 x)

1. K번째수

def solution(array, commands):
    answer = []
    for cmd in commands:
        i, j, k = cmd #리스트 각 변수로 가져오는 방법
        target = sorted(array[i - 1:j]) # 리스트 슬라이싱 진행
        answer.append(target[k-1]) # k번째의 원소 리스트에 추가
    return answer

2. 가장 큰 수

def solution(numbers):
    answer = ''
    # 배열 내부 오름차순으로 정렬 (문자열 기준)
    #result = [str(x) for x in numbers]
    result = list(map(str, numbers))
    # 각 요소 별 첫번째 숫자가 가장 클수록 처음에 오도록 해야함
    #sorted_result = sorted(result, reverse = True)
    result.sort(key=lambda x:x * 3, reverse=True) # 요소의 길이가 1000 이하 이므로 3을 곱해서 길이를 맞춰준 다음에 sorting
    # 문자열로 바꾸어 리턴
    #answer = ''.join(sorted_result)
    return str(int(''.join(result))) # 000인 반례를 해결하지 못하기에 int로 다시 변환

3. H-Index

def solution(citations):
    # 내림차순 정렬을 해서 인용수가 가장 많은 것 부터 논문의 수 (index+1) 비교
    citations.sort(reverse=True)
    # 리스트를 돌면서 index 와 그에 해당하는 값을 동시에 가져오는 함수 enum
    # 인덱스랑 값 둘 다 필요할 때 사용
    for i,c in enumerate(citations): # c = 인용수, i+1 = 논문수
        if c < i + 1:
            return i
        # 어차피 h 값은 논문의 총개수가 최대값
    return len(citations)

주요 함수

# 리스트 컴프리헨션
[str(x) for x in arr]
# map
list(map(str, arr))
# enumerate
for i, x in enumerate(arr):
# 정렬 key
sort(key=...)

개수 세기 유형

1. 리스트로 하면 탐색 시간 소모가 크다. (list.remove() / for … in range(0, len(list)))
2. 딕셔너리를 활용해서 key 기준 계수하는 테이블 생성 하기 (d[name] = d.get(name, 0) + 1 )
3. 이후 value 값을 이용해서 수를 더하고 빼면서 로직 구현

존재 여부 유형

1. 리스트 관련 함수 적용
   1. 정렬, 제거, 나열, 필터링, 등

1. 완주하지 못한 선수

def solution(participant, completion):
    d = {}
    # 참가자 수 세기
    for name in participant:
        d[name] = d.get(name, 0) + 1 # key가 없다고 하더라도 에러없이 default r값으로 dict 생성
        # name:숫자

    # 완주자 수 빼기
    for name in completion:
        d[name] -= 1
        # 참가를 했다면 기본적으로 1, 완주하면 -1 되어 0이 됨
    # 남은 사람 찾기
    for name in d:
        if d[name] > 0: # 완주했다면 0이 되었을테니, 0이상인 값의 key returb
            return name

2. 폰켓몬

def solution(nums):
    # '종류:마리수' 느낌으로 dict 생성
    mon_nums = len(nums)
    d = {}
    # 해시테이블 생성
    for mon in nums:
        d[mon] = d.get(mon,0)+1 # 개체 유형별로 몇마리인지 정리
    # 전체 유형 수
    mon_type = len(set(nums))
    # 전체 유형수가 절반보다 많으면 절반이 유형의 최대값
    #                     적으면 그때의 유형의 개수가 최대값
    if mon_type < (mon_nums / 2):
        return mon_type
    else: 
        return mon_nums / 2

3. 전화번호 목록

def solution(phone_book):
    # 리스트를 정렬하면 접두어 바로 뒤에 해당되는 접두어를 가진 요소가 붙게됨 => 핵심!
    phone_book.sort()

    for i in range(len(phone_book) - 1):
        # 접두어로 시작하는지 확인하기 위한 메서드
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

4. 의상

def solution(clothes):
    closet = {}
    for _, category in clothes:
        # 어떤 옷인지는 이 문제에서 중요하지 않음 => 카운팅만 해주면 된다.
        closet[category] = closet.get(category, 0) + 1

    # 딕셔너리 key 값별로 value의 길이를 구하고 각각 +1 해주고, 최종 값에서 아무것도 안입는 경우 1을 빼주면 결과값
    answer = 1
    for k, v in closet.items(): # 딕셔너리 요소별로 키와 값 가져오기
        v = v + 1
        answer *= v

    answer -= 1

    return answer

• Optimal Policy 를 위한 과정
• 주어진 MDP를 이용해 Transition Probability와 reward function을 구함

  GOAL

1. 목적함수를 사용하여 리워드의 총합을 최대화하는 policy를 찾기
2. 최적의 state값 또는 action 값 함수 기반하여 optimal policy 찾기

즉, 최적의 state value와 state를 찾으면 최적의 policy를 찾을 수 있다.

그렇다면 어떻게 q*와 v*를 어떻게 구할 것인가?

그 방법은 다음 2가지

1. Policy Iteration (policy evaluation and policy improvement)
   • policy를 반복적으로 업그래이드 하겠다.
2. Value Iteration

이를 dynamic programming이라고 부른다.

Planning by Dynamic Programming

1. For prediction • Input: MDP S, A, p, r, ρ0, γ and policy π • Output: value function vπ

2. For control • Input: MDP S, A, p, r, ρ0, γ • Output: optimal value function v∗ and optimal policy π∗

   Planning by DP: Methods

   MDP에 관한 모든 정보를 알고 있고, 문제가 작을 때 활용 가능

3. Prediction : mdp와 policy가 주어졌을때, policy를 반복적으로 평가 (벨만 ex pectation 방정식 활용)

4. Control : mdp와 policy가 주어졌을때, policy반복적으로 평가 및 greedy policy (Bellman Expectation Equation) 와 value iteration (Bellman Optimal Equation)

Optimal Value Function vs. Optimal Policy

fixed-point iteration method의 필요성

fixed-point iteration method

fixed-point : 함수를 만족하는 해 fixed-point iteration : 해를 구하는 정의

어떻게 해를 구하는가? 초기값 x0에서 시작해서 반복적으로 찾아가겠다.

시간이 고정되어있다고 가정하면 순간의 state, action, reward는 랜덤변수 전체 Trajectory는 랜덤 프로세스

목표는 다음과 같다.

1. trajectory의 joint 확률을 규정 (여기서 쓰이는 과정이 markov 정리)
2. trajectory의 평균을 최대화를 하도록 어떤 액션을 취할지 결정

강화학습은 여기에서부터 시작된다.

1. Markov Process (state로 이루어진 프로세스) 여기에 reward 개념이 들어감
2. Markov Reward Process 여기에 action policy가 들어감
3. 최종 Markov Decision Process 완성

Markov Property

random process 특별히 마르코브 특징을 갖는다. 현재 직전까지의 history가 다음 상태에 영향을 미치지 않는다. (conditional independence)

마르코브는 state transition 확률만 알면 복잡한 joint 확률 대신에 마르코브 프로세스를 알 수 있게 된다.

예를 들면, 상태가 맑음, 흐림 두가지만 존재한다고 하자. transition matrix (오늘 날씨에만 의존한다고 가정)은 다음과 같다. 최초의 확률은 P(맑음) = 0.6, P(흐림) = 0.4

오늘 상태가 '맑음'이라고 가정하고 다음 상태를 구하면 다음과 같다. P(맑음,맑음,흐림 | 맑음) = P(맑음|맑음) * P(맑음|맑음) * P(흐림|맑음) = 0.8 * 0.8 * 0.2

• 0≤𝑃[𝐴𝐴]≤1
• 𝑃[Ω] = 1
• 𝑃[𝐴𝐴 ∪ 𝐵𝐵]=𝑃𝑃[𝐴𝐴] + 𝑃𝑃[𝐵𝐵]

  랜덤변수

  확률을 정의하기 위한 변수

  Discreate X

• Probability Mass Function (PMF)
• 반드시 확률은 0보다 클것
• 확률의 합은 반드시 1

  Continuous X

• Probability Density Function (PDF)
• 확률은 0보다 크거나 같을 것
• 랜덤변수 x가 A보다 크고 B보다 작을 확률은 적분으로 구할 수 있음

  Discrete Distriubution

  Bernoulli

  두개의 아웃풋을 내는 확률 실험 (0또는1, 동전 뒤집기)

Categorical

강화학습을 확률적으로 모델링하는데 가장 중요한 분포

주사위 던지기 할때, 1-6까지 경우의 수 가능했던 것을 생각해보면, 강화학습에서 현재 상황에서 어디로 갈지 하나를 고르는 문제와 동일

Continuous Distribution

Gaussian

강화학습시 policy를 결정하는데 중요한 역할을 하는 함수

• 평균, 분산의 분포

  Uniform

  min, max 값이 파라미터로 들어오는 함수

Multivariate Gaussian Distribution

covariance 값에 따라서 모양이 많이 달라진다.

• full
• diagonal
• spherical

In RL

예시

1. Frozen Lake example : 현재 상태가 어떠한지, 현재 상태에서 어떤 액션을 취할지 모른다 => 랜덤변수로 정의 -> state와 action은 이산 확률 변수
2. Cart Pole example : 현재 막대가 어느정도로 위치해있고, 각도는 어느정도로 틀어져 있는지 모른다. => state 랜덤 액션의 경우 오른쪽으로 갈지, 왼쪽으로 갈지 두개의 액션 존재 => action 이산 (2가지 -> 베르누이)
3. Pendulum example : 스테이트 : 벡터 연속변수 / 액션 : 스칼라 연속 변수
4. 많은 상태, 액션, 보상이 있으나 이 모든 확률을 모아서 (joint) 만드는 것

--

조건부 확률

Random Variable 사이 관계

두 확률변수 사이의 관계를 정의하자 : joint 분포

• joint : 두개가 동시에 발생했을때
• marginal : 하나만 일어났을때 확률값
• conditional : 한개의 랜덤변수가 주어졌을때, 다른 하나의 랜덤변수를 결정 가능 => policy 결정하는데 이용

현재 a 상태에 있다고 가정하면 앞으로 어떤 상태로 나아가야 하느냐를 결정하는 것 조건부 확률이자 policy 개념에 해당

independence & Conditional Independence

independence : 𝑋⊥Y

Y가 발생했다고 해서 X에 영향을 미치지 않는다. n개의 독립변수라면 각각의 합에 의해서 정의

conditional : 𝑋⊥Y | Z

이미 z 확률 변수가 알고있다고 가정했을때, x와 y가 어떻게 만들어지는가

in RL

Policy는 state와 action을 매핑한 함수 => 조건부 확률에 의해 결정 Markov Property : 과거의 상태와 독립적으로 작용하여 미래 결정 State Transition Probability : 다음 상태를 현재상태와 액션에 의해 결정

예시

1. Frozen-Lake -discrete policy : Categorical
2. Cart Pole -discrete policy : Categorical
3. Pendulum
   • continuous policy : Gaussian

강화학습의 goal : 끝날때마다 리워드의 합이 달라지고, 언제 끝날지도 모르기 때문에 전체적인 평균이 최대가 되게

조건확률과 베이즈

chain-rule

조건부 확률을 n개의 변수에 대한 것으로 확장 상태에서 다음 액션을 하고 다시 상태가 변하고 액션을 하고 ... 체인과 같이 연결

베이즈

이러한 베이즈와 체인룰을 사용해서 조인트에서 conditional, marginal 과의 관계를 정의 가능

conditional expectation

조건에 따라 두가지 유형으로 구분할 수 있다.

1. 임의의 값이 주어졌다는 조건 하에
   • 하나의 상수로 나온다
2. 임의의 랜덤변수가 주어졌다는 조건하에
   • 정해지지않아서 그것의 평균을 가져오나 여전히 랜덤변수

가령, 초등학교에 5학년의 키평균을 알고싶다고 가정한다면 값이 오로지 하나 (5학년이라고 특정) 1~6학년 어떤 학년인지 모르나, 그런 경우의 평균은 값이 6개의 값이 가능 후자에 대해서 평균을 다시한번 한다고 생각하면 평균의 평균이 되고, 다음과 같은 식으로 구성

Law of Total Expectation (law of iterated expectation, or Tower property) E[X] = E[E[X|Y]] 로 표현

다양한 용어 정리

확률 VS 통계

확률 : 현상을 정의하고 어떤 데이터를 예측하고, 생성하는 것

• 데이터가 없지만 확률 모델로부터 예측하거나, 생성할 수 있다는 것

• 데이터를 생성하고, 예측 가능

  통계 : DATA를 다루는 것

• 데이터로부터 확률을 추정하거나, 결론을 도출해내는 것

• 데이터에 숨겨진 다양한 특성 (분포)를 꺼낼 수 있음

분포가 갖는 파라미터가 존재한다면 분포로부터 데이터를 만들 수 있으며 (sampling)

sampling methode, generative model (생성형)

데이터가 존재한다면 데이터로부터 분포를 추정할 수 있음 (estimation)

maximum likelihood (ML) estimation method

*큰수의 법칙 : 데이터의 크기가 커질수록 분포에 가까워짐

Monte Carlo (MC) Estimation : 확률과 통계가 만나는 지점

샘플링을 통해서 복잡한 수학적인 값들을 근사화 하겠다.

• 문제 : 주어진 함수의 기댓값은 함수와 pdf의 곱을 적분 만일 주어진 함수가 아주 복잡해진다면 계산이 불가해진다. 그래서 나온 기법 MC

분포를 알면 데이터를 생성할 수 있다. -> 분포에서 N개의 데이터를 샘플링한후 -> 복잡한 주어진 함수에 대입하여 나온값들을 평균하면 실제 평균과 근사해진다. (N이 무한대로 갈때)

Random Process

랜덤변수는 값하나를 할당하는 것

예를 들어, 랜덤변수의 값이 정해지면 그와 매칭되는 하나의 랜덤 확률 P(X=0.4)가 결정되어야함

랜덤프로세스는 랜덤변수의 함수. 변수가 시간/공간에 따라 바뀌는 것 = stocastic process

이는 강화학습에서 상황, 액션, 리워드에 따라 만들어지는 trajectory가 시간에 따라 이어지는 것을 표현하는데 이용되는 개념이다. (이산적인 개념)

시간이 계속 변하나 이를 join해서 하나의 확률로 규정

joint 확률은 시간의 개념을 고려하지않고, 하나의 확률로 규정하는 것인데, 이 시간을 고려하지않는다는걸 지지하는 정리가 markov 이다.

과거의 개념을 잊는다?

이전에 어떻게 움직였든 관계없이 현재 상황에 따라서 액션을 결정하겠다는 것

Stationary Markov Process

시간에 무관하게 값들이 같다.

이 개념은 transiton probability, policy, reward 에 적용

• 모델은 함수다
• 모델의 모양은 parameter에 의해 결정된다.
• 이는 모델이 1차함수가 될 수도 있고, 2차식이 될 수도 있다는 의미
• loss/cost 함수 : 모델이 input과 output을 잘 설명하고 있는지 알려주는 척도
• optimization : 모델이 가진 파라미터를 최적의 파라미터로 만들기위한 목적
• 훈련이 얼마나 잘 되었는가 -> 테스트 과정
• 학습의 5단계 : data -> 모델 (함수, 파라미터) -> loss함수 정의 -> 최적화 -> 테스트
• 모델의 파라미터는 사용자가 정하는 것 (data를 보고 data의 특성이 가장 잘 드러나도록 정하는 것)
• 데이터가 들어오면 모델이 파라미터에 의해 값을 내고 이 값이 타겟을 얼마나 잘 설명하는지 loss함수로 값을 내고, 이 손실함수의 값을 가져와 파라미터를 업데이트하며 최적화(GD)를 진행한다. => target을 잘 설명하는 파라미터의 최적값을 찾아내는 것이 학습의 목표
• 최적의 파라미터를 찾아내면 그 파라미터를 이용해 새로운 data를 넣어서 아웃풋을 보고 테스트 진행
• 검증데이터와 테스트 데이터는 다른것 (검증은 train 데이터의 일부를 떼서, 검증에 활용) (data를 묶어서 처리하는 방식 : batch, 묶음, 다발)
• full-batch : 모든데이터를 한번에 입력해서 파라미터를 업데이트
• mini-batch : 데이터셋을 쪼개서 사용
• 데이터는 tensor로 표현 (스칼라 : 하나의 값(점) | 벡터 : 스칼라의 모음(선) | 메트릭스 : 행과 열로 표현(면) | 텐서 : 3차원 공간상에 depth도 포함)
• 이미지 : 픽셀로 구성 (픽셀은 0~255 크기)

           - 다중분류 - target이 k개의 정수인경우 (여러 정수중 하나로 예측하는 것) (학점 분배)

비지도학습

• target이 없는 학습 형태
• 비슷한 것끼리 모을수 있다. (input 만가지고 데이터의 특징을 발견해내는 일을 하는 학습 방법)

강화학습

• 학습의 구조가 전혀 다름
• agent(인공지능 프로그램) <-> environment (에이전트 외의 것 예를들어, 로봇/게임/ 강화학습 수행의 대상)
• 1. state (화면전체의 상태) 2. reward (보상) 3. action (행위) : action으로 인해 화면이 어떻게 바뀌고 보상이 어떻게 되는지 행동의 목적이 존재 (예를 들면 점수를 얻고자 하는것
• 미래의 보상을 최대화하는 인풋에 대하여 보상 진행
• 한번에 학습이 되는 것이 아니라 시간에 따라서 (goal : select actions to maximize total future reward)
• 피드백, delay, 순차적
• 어디에 쓰이냐 ? sequential decision making problems : 한번에 끝나는 것이 아니라 순차적으로 천천히 학습 / 시간마다 어떤 action을 할것이냐를 학습하는 것
• 순간에 어떤 결정을 할래? 이걸 결정하는 함수를 구하는 것이 강화학습의 목적 (future reward 극대화)

import gymnasium as gym

1. 다양한 실습 환경

* cartpole 환경

• continuous state / discret env / reward (넘어지지않으면 1점, cart의 위치가 벗어났을때, 막대의 각도가 넘어갈때 끝)

  * frozen lake

• 구멍에 빠지지않고, goal에 도달하기
• discrete state (16개의 공간) / discrete action (상하좌우이동) / slipperiness (환경을 stocastic하게 만들수있음)

  * pendulum

• 막대기를 돌려서 수직으로 세우는 것이 목표
• continuous state (세워진각도, 가속도 값 코사인값) / continuous action (회전력의 힘) / reward (세워지면 +1, 기운 각도가 세운것에멀어질수록 -)

  * nujoco : ant

• 8개의 관절에 힘을줘서 앞으로 잘 가도록 하게 만드는 것이 목표
• continuous state / continuous action

  2. 기본적인 코드

1. 환경을 준비하라 : 환경을 준비하고 초기 상태로 리셋 (make, reset)
2. policy에서 action을 선택해서(action_space.sample) environment로 보냄(step(action) : step 함수가 action을 받아서 결과를 output) => loop
3. 결과 출력 env.render 이후 env.close() : 환경 종료

   3. 개인적인 환경을 만들고 싶을때 사용할 class

• print(env.action_space)
• print(env.observation_space) (state)
• step() : action을 받아서 5개의 요소를 출력으로 뱉는다.
• fundamental space : box(=continuous) / discrete / multidiscrete / ..
• wrapper : gym을 만들고 wrapper로 감싸면 super class를 상속받아서 환경의 일부를 수정가능 (예를들어, 원래는 step 마다 0이었는데, step마다 -1이 되도록 변경 가능)

1. 강화학습의 개념 ( 아래 6개의 키워드 기억하기 )

• componants : agent, environment

• data : action, state, reward

• function : policy

  2. Componants

  agent, environment => interaction의 주체

• 주거니 받거니 하는 주체들

• 에이전트 : ai 프로그램 (연구 도메인의 ai 프로그램, 학습자, 결정알고리즘)

• 환경 : 에이전트가 상호작용하는 대상 => 에이전트가 환경에 진입하여 상호작용

  3. action, state, reward

• action의 주체 : 에이전트 (예, 자율주행차가 핸들을 꺽는 행위)

• action의 객체 : 환경 ( 핸들을 꺽는 행위를 환경이 받아들이고, 환경을 변화시킴) => 환경을 변화시키는 것 환경이 변화된다는것은 state가 바뀐다는 것이고, 그에 따른 reward를 에이전트에 보낸다. => 에이전트는 state와 reward를 받아와서 action을 만들고, 환경은 액션을 받아 state와 reward를 보낸다.

• state : 환경의 상황, 상태

• reward : 값이 딱 하나인 실수값 (action에 대한 좋은지 나쁜지에 대한 피드백)

  4. policy

• agent에 속해있는 함수

• state 기반 최적의 어떤 액션을 낼 것인가에 대한 전략

  5. trajectory (학습의 시퀀스)

• 시간에 따라서 멀티스탭

• 각 스탭마다 전략(policy/함수)가 존재. 이걸 위해 reward라는 개념이 존재

• 행동이 좋은지 나쁜지는 지금 당장은 모르나, 나중에 피드백이 발생

  6. state 의 정의가 반드시 필요

• state는 환경의 상황에 대한 모든 정보 포함

• 환경은 이전상태 + 현재 액션을 반영해 다음 상태를 결정 = 상태 전이 (state transition)

• 상태의 모든 정보가 에이전트에 제공되는 경우 : fully observable

• 모든걸 알 수 없고 부분적인 것만 알수 있는 경우 : partial observable

  7. reward

  하나의 스칼라값

• 액션에 대한 좋고 나쁨을 피드백하는 값

• 에이전트는 리워드가 굉장히 중요함 (왜? 지도학습은 목적이 확실, 강화학습은 학습하려는 함수 f를 만드는 기준이 리워드가 되기 때문)

• 리워드가 함수 f를 어떻게 만들어야 잘만든것인지 가이드를 해줌

• 이러한 피드백은 즉시가 아니라 한참뒤에 나올 수 도 있음 즉, 과거, 미래의 리워드를 고려해야한다는 의미

• 미래의 리워드가 어떻게 되어야 좋은 결과를 낼것인가 f를 정의 예를들어, 주식도 지금 당장 10만원보다 1년뒤에 총 1억을 버는것이 더 낫다. => 이과정에는 지금 당장은 오르거나 잃을 수도 있으나 전체적인건 1억을 벌고자함 리워드도 그때그때의 리워드를 생각할 것이 아니라 "누적"된 리워드를 생각

• 순간의 리워드 : 행동자체를 강화 또는 자제

• 장기적인 리워드

• dense : 행동을 할때마다 리워드가 나타나는 것

• sparse : 행동을 쭉하는데 마지막에, 듬성듬성 리워드가 나타나는 것 (바둑)

  8. 강화학습의 궁극적인 목적

• policy f를 아는것

• 기준 : 최종 최고 점수를 얻는 것이 목적, 리워드를 누적한 값

• 로봇의 경우, 최대의 보상 값을 얻기위해서는 넘어지지않고, 걸어가는것을 계속 유지할때 최대 (상황이 어떻게 변하던 간에)

9. exploitation

현재 액션을 하는데 기존의 경험을 활용해서 진행

10. exploration

그동안 간곳보다 최고의 액션이 있을 수도 있음 -> 한번 모험해보는 것 => 9와 10은 트레이드 오프 관계

11. 각 state별 함수를 얻어와, 최종 합이 최대값이 되도록 하는 목표를 이루기위해
12. 강화학습은 인간이 모르는 새로운 방법론을 도입할 수 있다.

    각 요소가 가질 수 있는 값

    1. action

    • action이 이산적인 값인지 연속적인 것인지에 따라 쓰이는 함수가 다르다.

      2. policy

    • policy state가 정해지면 행해지는 액션은 하나로 고정 :: deterministic == 확률이 1인 것 == 확률 분포 PMF
    • 확률실험에 의해서 state가 주어지는 것, 확률 분포가 필요한 이유 :: stochastic == 확률이 0.2, 0.8, 0.3 다양 == 확률분포 PDF => 그렇다면 확률이 결정되어야하는데 그 결정을 위해 확률 분포가 쓰인다. / 반드시 어딘가로 가는 것으로 정해진 것이 아니라 때로는 확률적으로 낮은 곳으로 가는 것도 가능 (새로운것을 탐험할 때 유리)

      3. environment

• 위로가기로 정해지면 반드시 위로 간다 :: deterministic
• 위로가기로 정해져도, 위로갈지 옆으로갈지 확률적으로 정해진다. :: stochastic

  4. etc

• trajectory : policy에 의해 벌어지는 것들
• episode : 하나의 trajectory가 끝나는 단위
• transition : state, action, reward. state (t+1) 의 쌍
• horizon - finite : episodic case
  • infinite : continuous case
• goal : trajectory마다 있는 reward의 총 합이 극대화가 되도록 하는 것

1) 정의

• 데이터를 망가뜨렸을때 모델의 성능 (에러율) 이 얼마나 나빠지는가

  2) 목표

• 모델이 실제 정답을 맞히기 위해 해당 피처에 얼마나 의존하고 있는지 확인하고자 함

Partial Dependence (부분 의존성)

1) 정의

• 다른 모든 조건 (피처)가 동일할 때, 오직 특정 피처 하나만 값이 변하면 모델의 예측값 (평균)이 어떻게 변하는가를 보여주는 기법

• 예를 들어, 집값을 예측하는 모델 (회귀)에서 방의 개수에 대한 부분 의존성을 본다면 방이 1개에서 5개로 늘어날때 집값 예측치가 평균적으로 어떻게 우상향하는지 선 그래프로 보여줌

  2) pd_variance (부분 의존성 분산)

• 부분 의존성 그래프 (선)가 위아래로 얼마나 심하게 요동치는지를 측정한 값

• 피처 중요도의 지표로 사용

  • 분산이 크다 : 그래프의 기울기가 가파르거나 굴곡이 심함 (해당 피처의 값을 조금만 바꿔도 모델의 예측값이 휙휙 변함 = 영향을 많이 미치는 중요한 피처)
  • 분산이 작다 : 그래프가 평평한 수평선에 가까움. 이 피처의 값을 아무리 바꿔봐야 모델의 예측값은 미동도 하지 않음 = 모델 예측에 쓸모없는 피처

    3) 목표

• 모델이 정답을 맞히는지, 틀리는지 관심없음. 모델의 출력이 해당 피처의 변화에 얼마나 민감하게 반응하는지 확인

  4) 코드

  exp = explainer.explain(X=X_train,features=features,kind='both')

• kind='average' (부분 의존성, PDP): 1,000명의 사람이 있다면 그 1,000명의 반응을 뭉뚱그려서 평균을 낸 굵은 선 딱 1개만 보여줌 (반 평균 성적)

• kind='individual' (개별 조건부 기대치, ICE): 평균을 내지 않고, 1,000명 각각이 온도가 변할 때 대여를 어떻게 할지 얇은 선 1,000개를 모조리 그려줌 (학생 개개인의 성적표)

• kind='both' (PDP + ICE): 위의 두 가지를 한 번에 다 계산. 배경에는 1,000개의 얇은 선(개별 반응)을 쫙 깔아두고, 그 위에 굵고 진한 선(전체 평균)을 얹어서 함께 보여줄 준비를 마친 것

both가 주는 인사이트 : 피처에 따라 극단적으로 다르게 반응하는 그룹이 있는지 살펴볼수있음 (피처간 상호작용가능)

(feature_names.index('temp'), feature_names.index('windspeed')),
(feature_names.index('mnth'), feature_names.index('weather')),
(feature_names.index('season'), feature_names.index('temp'))
]
 # compute explanations
exp = explainer.explain(X=X_train,
features=feature_interaction,
kind='average',
grid_resolution=25)

• 두 피처를 짝지어서 넣어서 두개의 피처가 서로 어떻게 상호작용하며 예측값에 영향을 미치는지 분석

from alibi.explainers import plot_pd_variance
plot_pd_variance(exp=exp_importance)

• 범용성, 확장성 우수
• C언어로 작성되어 시스템간의 이식과정을 단순화
• 다양한 기능
• 다중사용자, 다중작업, 대화형
• 파일과 입출력장치를 동일 취급 (장치의존성 제거)
• 유지보수 용이, 계층적파일시스템 (트리구조)

쉘 (shell)

• 프로그래밍 계층에 존재, 사용자가 입력하는 명령어를 이해, 실행하는 역할 수행
• 명령어 해석기
• 주기억장치에 상주하지않고, 보조기억장치에 교체가능 (커널과의 차이점)

커널 (kernel)

• 쉘을 포함한 응용프로그램에게 서비스 제공
• 컴퓨터 부팅시 디스크로부터 주기억장치로 적재된 후 시스템이 꺼질때까지 항상 주기억장치에 상주
• 대부분은 C, 일부는 어셈블리어

디스크 블록의 구조

• 부트 블록 : 디스크의 첫번째 논리적인 블록
  • 유닉스가 첫번째로 활성화되는데 사용되는 약간의 실행코드 포함
• 슈퍼블록 : 전체의 파일 시스템에 관한 정보를 가짐
  • 전체 블록의 수, 블록의 크기, 사용중인 블록의 수 등 파일 시스템의 정보를 가짐
• i-node 블록 : 디스크상의 파일에 대응하는 모든 inode 리스트로 된 고정된 크기의 블록
• 데이터 블록 : 실제 파일 블록을 저장하도록 사용, 디렉터리와 사용자 파일들 포함

파일 3가지 종류

1) 일반 파일 (regular file)

• 데이터 파일 : 일반적으로 보게되는 파일로써 문자를 담고 있는 텍스트 파일로써 이진 데이터를 담고 있는 파일
• 실행파일 : 실행될 수 있는 이진형식의 실행파일 (쉘스크립트같은 텍스트 형식의 파일)
• 숨김 파일 : 개인의 환경설정 파일이나, 시스템의 설정파일 ( . 으로 시작)
• 링크파일 : ms 윈도우의 바로가기 아이콘

2) 디렉터리 파일 (directory file)

• 디렉터리 내에 들어 있는 파일 및 디렉터리에 대한 정보 포함
• 디렉터리는 계층적으로 구성되며, 디렉터리 파일은 쓰기 보호 속성을 가진 일반 파일로써 파일 시스템만이 이 파일에 기록 가능 (사용자 프로그램은 읽기만 허용)

3) 특수 파일 (special file)

• 프린터, 터미널, 디스크 같은 주변장치나 직렬포트등을 표현하는 파일

링크파일 (link file)

1) 하드링크 (hard link)

• 파일을 생성하면 기본적으로 생성

• 일반 파일 이름 + inode + 데이터블록이 존재하면 하드링크는 1

• 일반파일은 기존 파일에 하드링크를 걸면 링크수 증가

• 두개의 파일이름이 하나의 inode 같은 데이터 블록을 가리킴

  → 시스템은 한 파일 이름에 대한 디렉터리 엔트리를 삭제하고 데이터 블록은 그대로

  → rm 명령어 : 하드링크에 대한 링크개수만 하나 감소

  → 실제 데이터 블록이 삭제되는 때는 그 링크의 개수가 0이 되는 시점

2) 심볼릭 링크 (symbolic link)

• 특정 디렉터리 파일을 다른 디렉터리에서 실행하려면 그 파일에 대한 절대경로를 이용해 명시
• 그 파일을 사용할 디렉터리로 복사
• 파일의 불필요한 반복적 복사를 방지하여 파일 시스템을 유연하게 활용
• 여러 디렉터리에서 동일한 라이브러리를 요구할 경우, 같은 파일을 여러사람이 공통으로 관리하면서 사용할 경우, 비슷한 역할을 담당하는 여러가지 파일들중하나를 선택하는 경우

inode의 내용

• 파일의 유형 (일반, 디렉터리, 특수)
• 파일의 보호 권한
• 파일 소유권과 소유자 그룹 id / 사용자와 그룹의 표시
• 하드링크계수, 파일에 대한 링크 수
• 파일의 생성 시기, 최종 수정시간 및 최종 접근 시간
• 일반 파일/ 디렉터리 파일인 경우 블록위치, 물리적 디스크 주소
• 특수파일인 경우 주기억장치 및 보조기억장치 번호
• 심볼릭 링크인 경우 심볼릭 링크의 값
• 파일을 지정하고 있는 디렉터리 항의 수
• (주의) 파일명은 없다!!!!

unix 명령어

UNIX 디렉터리 보호

• 각 SUB 디렉터리와 관련한 파일의 보호는 각각 3비트 (rwx)로 구성된 파일소유자, 프로젝트그룹, 일반 사용자들 3부분 정의

  • 파일 소유자 : 파일을 생성한 사용자
  • 프로젝트 그룹 : 파일에 대한 유사한 접근을 필요로 하는 사용자들의 집합
  • 일반 사용자 : 시스템에 있는 모든 다른 사용자들

• 첫글자 - 는 일반파일 d는 디렉터리 파일

• 하드링크수, 파일 소유자 이름, 그룹의 이름, 바이트 단위로 파일의 크기, 최종 변경 날짜, 파일명

• chmod : 허가권을 변경하기 위한 명령어

  chmod 741 [파일명]

프로세스간 통신

1) 파이프 pipe

• 두개의 프로세스를 연결해주는 open file로서 파이프의 한쪽 끝에 쓰인 정보를 파이프의 다른쪽에서 읽을 수 있도록 한다.
• 유닉스에서 프로세스들은 메일박스와 비슷하게 파이프를 통해서 프로세스 간에 통신하는 기법을 제공
• shell 에게 앞의 명령의 출력이 후속되는 명령의 입력으로 넘겨주도록 조정하는 수직선 |

2) 소켓 socket

• 종단간의 통신으로 네트워크를 통해서 다른 컴퓨터에 존재하는 프로세스와의 통신 제공
• 클라이언트 프로세스는 통신 시작, 서버프로세스는 통신내용 수신

3) 시그널 signal

• 하드웨어 인터럽트와 유사한 예외조건을 다루기 위한 소프트웨어 메커니즘
• 프로세스에게 이벤트 발생을 실시간으로 알려주기위해 사용

동기 vs 비동기

• 동기(Synchronous) : 작업을 요청한 뒤 결과가 나올 때까지 기다렸다가 다음 작업을 수행하는 방식
• 비동기(Asynchronous) : 작업을 요청한 뒤 기다리지 않고 다음 작업을 수행하다가 결과가 준비되면 처리하는 방식

관련정보를 포함하는 실제적인 파일들의 집합체와 시스템내의 모든 파일에 관한 정보를 제공하는 디렉터리 구조로 구성

• 파일 : 서로 연관성이 있는 데이터 집합 (보조기억장치의 저장단위)
• 파일이 저장되어있는 데이터를 액세스하는 방식 제공
• 파일이 안전하게 사용되고 보호될 수 있도록 하는 수단 제공

디렉터리

파일이름들을 디렉터리 항목으로 변환하는 기호테이블로 볼 수 있음

• 파일의 위치, 크기, 형태 등에 대한 각 파일의 실제적인 속성

파일 디스크립터

파일을 관리하기위해 시스템이 필요로 하는 정보를 보관하고 있는 자료구조 테이블

• file control block
• FCB는 보조기억장치에 저장되어 있다가 파일이 개방될 때 주기억장치로 이동

2. 보조기억장치 공간 할당 방식

(1) 연속할당

• 배열 구조 : 디스크 내의 파일들이 물리적으로 연속된 공간에 저장되는 기법
  • 고정크기, 가변크기로 구분
• 직접접근 : 연속하는 논리적 블록들이 디스크내의 물리적으로 서로 인접하여 있다는 것
• 파일의 시작주소와 파일 길이만 유지하면 되므로 파일 디렉터리 단순
• 파일의 생성과 삭제가 반복되면서 가용공간이 조각나, 외부단편화 발생 (압축필요)

(2) 연결할당

• 동일 파일에 속해있는 섹터들이 연결리스트로 연결
• 블록이 디스크 전체에 분산되어 있어도 액세스 가능
• 블록이 어디에 있는지 포인터만 연결해주면 되서 외부 단편화 발생 X
• 압축불필요
• 연결리스트는 포인터를 기억하기 위한 기억공간 필요 (낭비존재)
• 순차접근 : 파일의 블록들이 디스크 전체에 분산되어있어 검색에는 긴시간 요구
• 불연속 할당기법 : 링크를 이용한 섹터단위의 할당과 블록단위의 할당으로 구분

(3) 색인할당

• 모든 포인터들을 색인 블록으로 관리 (인덱스구조)
• 외부단편화 없이도 직접접근 가능 색인블록에 대한 낭비 존재
• 색인블록문제해결방법
  • 연결기법 : 여러개의 색인 블록들에 분산시키는 방법
  • 다중수준색인 : 첫번째 단계 색인 블록은 여러개의 두번째 단계 색인 블록들에 대한 포인터를 가짐
  • 결합기법 : 다중수준 색인을 확장한 기법

3. 디스크 스케줄링

디스크상의 여러곳에 분포되어있는 데이터를 이용하기 위해 디스크헤드가 움직이는 경로를 결정하는 기법 (탐색시간 최적화)

• 탐색시간 + 회전지연시간 + 전송시간

4. 탐색시간 스케줄링

(1) FCFS (First Come First Served)

요청큐에 먼저 도착한 요청이 우선 서비스

(2) SSTF (Shortest Seek Time First)

현재 헤드 위치에서 탐색거리가 가장 짧은 요청 트랙을 먼저 서비스

• 일괄처리시스템에는 유용, 대화형시스템에는 응답시간 편차로 인해 부적합
• 기아상태 발생 가능

(3) SCAN

SSTF 같이 동작하지만 헤드진행방향상의 가장 짧은 거리에 있는 요청을 먼저 서비스

• S자로 쓸고 내려오는 느낌
• SCAN은 처음부터 끝 트랙까지 요청이 없더라도 헤드가 이동
• 필요한 마지막 요청까지만 이동하는 것은 LOOK 스케줄링

(4) N-단계 SCAN

헤드가 한쪽 방향으로 이동해 나가면서 요청에 의해서 들어온 것만 서비스하다가 다시 반대쪽으로 가면서 이전에 도착했던 요청들을 서비스

• 일반 SCAN은 이동해가면서 들어오면 즉시 스케줄링

(5) C-SCAN

헤드는 항상 한쪽방향으로 헤드를 이동해가면서 요청 BUT 더이상 그 방향에 요청이 없을시에는 반대방향으로 헤드를 이동하는 것이 아니라, 다시 같은 방향으로 처음부터 처리를 진행

• 빗자루 쓸듯이 내려오는 느낌
• 가장 좋은 효과

• 주기억장치에 참조하려고 하는 페이지가 없을 경우 페이지 부재가 발생

  이때, 주기억장치 내에 어떤 페이지와 교체할 것인가를 결정하는 방법

• 페이지 부재가 발생하면 운영체제가 메모리에 들어올 페이지에 대한 공간을 만들어 주기위해 주기억장치에서 제거할 페이지를 선택하게 된다.

1) 최적 교체

• 현재 주기억장치에 있는 페이지들 중 현재 시점 이후로 가장 오랫동안 참조되지않을 페이지 교체
• 페이지 호출순서를 사전에 미리 파악해야하기때문에 비현실적

2) 선입선출

• 각 페이지가 주기억장치로 들어올 때마다 그 시간을 기억하고 있다가 페이지가 교체될 필요가 있을때 가장 먼저 주기억장치에 들어있는 페이지와 교체시키는 방법
• 원래는 페이지 프레임 (가용한 페이지 개수) 개수를 늘리면 부재율이 줄어드는데 fifo는 그러지 않음

3) 2차 기회 교체 (SCR, Second Chance Replacement)

• FIFO 방식의 단점인 가장 오랫동안 주기억장치에 있었던 자주쓰이던 페이지가 대체될 수도 있다는 것을 막기위한 방법 → 참조 비트를 두어 관리
• 페이지 사상표에 한개의 참조비트를 만들어, 처음에는 모든 참조비트를 0으로 그 후 프로세스가 수행되면서 참조한 각 페이지와 관계된 참조비트는 그값이 1로 변경

4) LRU (Least Recently Used)

• 최근에 가장 적게 쓰인 페이지 대체
• 최근의 상황이 가까운 미래에 대한 좋은 척도라는 locality에 의존

5) LFU (Least Frequently Used)

• 사용빈도가 가장 적은 페이지가 교체
• 가장 드물게 사용된 페이지가 가장 최근에 주기억장치에 옮겨진 페이지일 가능성이 있어, locality 위배

6) NUR (Not Used Recently)

• 근래에 쓰이지 않은 페이지는 가까운 미래에도 쓰이지 않을 가능성 많음
• 새로 호출하는 페이지와 대체
• 각 페이지당 필요한 두개의 하드웨어 비트를 둔다.
  • 참조비트 (0) : 페이지가 호출된 적이 없을때
  • 참조비트 (1) : 페이지가 호출된 적이 있을때
  • 변형비트(0) : 페이지 내용이 변형되지 않을때
  • 변형비트(1) : 페이지 내용이 변형되었을때
  • 참조비트보단 변형비트가 우선순위

7) Working Set

• 프로세스에게 필요한 만큼의 프레임을 재할당하는 방법
• 일정한 시간간격 사이에 하나의 프로세스가 참조하는 페이지들의 집합
• 최근에 참조하는 페이지들의 집합에 속하지 않는 페이지를 교체시키는 기법
  • 스레싱을 일어나지 않게 하여 cpu 이용률을 최대화 시킴

8) 페이지 부재 빈도 (PFF, Page Fault Frequency)

• workingset은 일정주기로 기억장치를 참조하고 나서 세트를 고치는 반면, PFF 방식은 페이지 부재율에 따라 주기억장치의 페이지 프레임 수를 조절
• 페이지 부재율을 적정수준으로 유지

2. 스래싱 (Thrashing)

너무 자주 페이지 교환이 일어나는 경우 프로그램 수행시간보다 페이지 교체에 많은 시간을 할애

• 다중프로그래밍 정도가 더 커지면 스래싱 현상이 자주 일어남 (cpu 이용률 감소)

해결책

• 다중프로그래밍 정도를 낮춘다.
• 프로세스들에게 충분히 큰 페이지 프레임을 할당
• 프로세스들이 가질 수 있는 페이지 프레임 수를 늘림
• 지역성이나 우선순위 교환 알고리즘 하용
• 지역 교환 알고리즘
  • 한프로세스가 스래싱을 유발하더라도 다른 프로세스로부터 프레임을 뺏어올수없고 자기가 할당된 프레임 내부에서 교환

3. 교체 지역성 (locality)

프로세스들은 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라, 어느 한 순간에는 특정 부분을 집중적으로 참조

• 캐시메모리, 연관기억장치, LRU, WorkingSet, PFF 등의 근거 이론

종류

1. 시간지역성
   • 최근에 접근한 데이터나 명령을 곧 다시 사용할 가능성이 높다는 것
   • Looping, Subroutine, Stack, Counting, 집계에 활용되는 변수
2. 공간지역성
   • 어떤 주소를 접근하면 그 주변 주소들도 함께 접근될 가능성이 높다는 것
   • 배열 순회, 순차적 코드실행, 프로그래머들이 관련된 변수를 근처에 선언

동작원리

• 가상기억공간과 실기억공간을 연결하는 주소 매핑 과정 필요

• 논리 어드레스 공간을 블록으로 나누어 놓고 실제 주기억 용량에 맞는 블록만을 로드

  이때, 어떤 블록을 가져올 것인지는 DAT (Address 변환 테이블) 사용

• 가상주소는 프로그래머가 쓴 보조기억장치의 번지 (실행중인 프로세스가 참조하는 주소)

• 실주소는 주기억장치에서 사용가능한 실제 주소

2. 가상기억장치의 구분

3. 가상기억장치의 구현 방법에 따른 분류

(1) 페이징 (Paging)

블록 사이즈가 고정(동일)한 방식으로 사용자가 작성한 프로그램은 하드웨어에 의해 페이지 단위로 분해

• 물리적 (실) 주소 공간은 가상기억장치의 페이지 크기와 같은 페이지 프레임으로 나누어 사용된다.
• 최초, 최적, 최악 적합등 배치 기법이 필요없음

장점

• 세그먼트 테이블과 달리 페이지 테이블은 블록의 크기를 나타낼 필요가 없다.

• 보조기억장치의 페이지 크기와 주기억장치의 페이지 프레임의 크기가 동일

  ⇒ 외부 단편화 발생 x

단점

• 내부단편화 발생할 수 있다.
• 세그먼트 기법에 비해 주소변환 테이블을 기억하기 위한 많은 장소 필요 (페이지 사상으로 비용이 증가하고 수행속도 감소)
• 페이지는 프로그램에 상응하는 논리적의미를 갖지 못함 (세그먼트에 비해 공유, 보호 지원x)

(2) 세그멘테이션 (Segmentation)

블록사이즈가 가변적인 방식, 가변 사이즈 블록을 세그먼트라고 함

• 세그먼트는 프로그램에서 서브루틴과 같은 의미

• 세그먼트를 나누는 일은 프로그래머의 일

• 기억장치의 사용자 관점을 지원하는 기억장치 관리 기법으로 논리주소 공간은 세그먼트의 모임

  ⇒ 최초, 최적, 최악 적합 등 배치 기법이 필요

• 세그먼트 테이블의 각 항목은 세그먼트의 기준 (base) 과 세그먼트의 한계 (limit)을 가지고 있음

장점

• 내부단편화 발생 x
• 세그먼트 공유와 보호 측면에서 세그먼트 시스템은 페이지 시스템보다 수행방법이 쉽고 명확
• 페이징 시스템에 비해 세심한 액세스 제어 가능

단점

• 외부 단편화가 발생 가능

  ⇒ 세그먼트의 크기가 고정되지 않고 가변적

• 세그먼트의 크기가 가변적이라 세그먼트 영역이 다른 세그먼트영역을 침범하지 않기 위한 특별한 하드웨어 관리 필요

(3) 페이징/세그멘테이션 혼용 기법

• 세그먼트는 너무 가변적, 세그먼트의 크기가 너무 커질때를 해결
• 프로그램을 논리적인 세그먼트 단위로 분할, 분할된 각 세그먼트들을 다시 각각 페이지 단위로 분할
• 외부 단편화 제거, 내부단편화 발생, 사상표가 차지하는 공간의 오버헤드 증가
• 각각의 세그먼트들마다 하나씩의 페이지 테이블 유지관리 필요

4. 사상표 색인을 찾는 방법에 따른 분류

(1) 직접사상방법

• 페이지 사상표는 주기억장치에 존재

• 프로세스의 가상기억장치를 구성하는 모든 페이지에 대한 항목이 페이지 사상표에 존재

• 명령어 수행주기 외에 추가적인 주기억장치 수행주기 요구

  → 페이지 테이블을 위해서 한번, 그 메모리 자체를 위해서 한번, 총 2번의 기억장치 접근 필요

• 페이지 테이블의 각 엔트리에는 유효/무효 비트를 둠

  • 유효 비트라면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타냄
  • 무효 비트라면 그 페이지는 프로세스의 논리 주소공간에 속하지 않는다는 것

(2) 연관사상방법

• 빠른 주소 변환을 위해 고속의 연관기억장치를 이용하여 페이지 사상표 전체를 넣는 방법
• 비용 많이들고, 구현하기 힘듦
• 캐시에 비해 매우 비싸서 이용하기 힘듦

(3) 연관/직접 사상 방법

• 보다 적당한 비용으로 연관사상의 장점을 살릴 수 있는 절충 방안
• 연관사상표 : 국부성에 의거, 최근에 가장 많이 참조된 페이지
• 페이지 사상표 : 연관 사상표에서 제외된 나머지 페이지

TLB (Translation Lookaside Buffer)

프로세서 내부에 있는 장치로 가상주소를 물리주소로 변환하는 속도를 높이기 위해 사용되는 캐시의 일종

5. 블록사상

(1) 페이지 크기가 작을 경우

• 더 많은 페이지와 frame이 존재하게 되어 → 페이지 테이블도 함께 커진다.
• 페이지 테이블 증가로 테이블 단편화 발생
• 작은 크기의 페이지가 지역성이 향상되어 프로세스가 효과적인 working set을 확보하는데 도움
  • working set : 일정한 시간 간격사이에 프로세서가 참조하는 페이지들의 집합
  • 공간지역성 : 어떤 주소를 접근하면 그 주변 주소들도 함께 접근될 가능성이 높다는 것
  • 시간지역성 : 최근에 접근한 데이터나 명령을 곧 다시 사용할 가능성이 높다는 것

(2) 페이지 크기가 클 경우

• 디스크로부터 입출력 전송 횟수 감소 → 입출력시간 최소화하기에 효율적

  디스크에서 하나의 페이지를 메모리로 전송하는 시간은 커짐

• 페이지 부재율 감소

• 참조되는 정보와 무관한 정보가 주기억장치에 적재되어 기억장치 내부 단편화 증가

• 전반적인 흐름은 페이지 크기를 크게하는 경향 존재

• 주기억장치 : cpu가 명령이나 자료를 직접 인출 혹은 반환할 수 있는 기억장치
  • CPU가 보조기억장치에 있는 프로그램이나 데이터를 참조하기 위해서는 먼저 주기억장치로 옮겨와야한다.
• 가상기억장치 : 주기억장치의 확장된 공간 (디스크)
  • 사용자가 주기억장치의 용량에 제한받지않고 보조기억장치의 용량에 해당하는 커다란 기억장소를 갖고 있는 것처럼
• 단일 사용자 시스템 : 한사람이 모든 주기억장치를 점유하여 사용하는 방법
• 다중프로그래밍 시스템 : 다수의 프로그램 또는 프로세스라 불리는 단위들을 주기억장치 내에 유지하여, CPU를 공유해가며 처리

2. 다중사용자 기억장치 할당기법

고정(정적) 분할 기억장치

주기억장치 사용자 영역을 여러개의 고정된(일정한) 크기로 분할하여 관리하는 기법

• 내부/외부 단편화 발생 가능

1) 내부 단편화

하나의 분할 영역에 작업을 할당하고 남은 빈 공간 (사용하고 남은 공간)

2) 외부 단편화

기억장치가 너무 많은 수의 매우작은 공간들로 단편화, 공간 중 일부를 사용할 수 없는 빈 공간 (사용할 수 없는 공간)

가변 (동적) 분할 기억장치

주기억장치 사용자영역을 각 작업에게 가장 합리적인 분할의 크기를 결정하여 주기억장치를 할당하는 기법

• 각 작업에 필요한 만큼의 기억장치를 할당, 내부단편화 발생 X 외부단편화 발생 O

1) 단편화 해결방법

• 기억장치 통합 : 이웃되는 가용공간을 하나의 커다란 가용공간으로
• 기억장치 집약 : 기억장치의 모든 내용들을 한군데로 몰고, 자유공간을 몰아서 큰블럭으로
• 쓰레기 수집 : 여러개의 작은 단편화 공간 (가용공간)을 모아서 하나의 큰 가용공간을 만드는 것

3. 기억장치 관리 정책

(1) 반입 FETCH 정책

CPU에 의해 실행되거나 참조되기 위해서 주기억장치로 적재할 다음 프로그램이나 자료를 언제 가져올 것인가 결정하는 정책

• 요구반입 : 실행중인 프로그램에 의해 어떤 프로그램이나 자료가 참조될 때 옮김
• 예상반입 : 앞으로 요구될 가능성이 큰 자료 또는 프로그램을 예상

(2) 배치 (Placement) 정책

주기억장치에 적재되어야할 페이지나 세그먼트를 주기억장치 어느 곳에 적재할 것인가

• 페이징 시스템 : 주기억장치에 적재될 페이지가 주기억장치의 가용 페이지 프레임 어디에 적재되되어도 무관 (배치기법 불필요)
• 세그먼트 시스템 : 최초 적합, 최적 적합, 최악 적합 같은 배치 기법 필요

1) 최초 적합 (First Fit)

• 가용공간중 첫번째 분할 영역에 할당
• 빈공간을 찾기위해 전체 조사하지 않아도 되어 결정이 빠르다.

2) 최적 적합 (Best Fit)

• 가용공간 중 사용한 후 남은 공백이 가장 적은 분할 영역에 할당
• 가용공간이 정렬되어 있다면 반만 탐색해도 필요한 공간 찾기 가능

3) 최악 적합 (Worst Fit)

• 가용공간 중 가장 큰 분할 영역에 할당

(3) 교체 (Replacement) 정책

새로들어온 프로그램이 들어갈 장소를 마련하기 위해서 어떤 프로그램이나 자료를 주기억 장치로부터 제거할 것인가

• 최적화 정책
• FIFO
• SCR (Second Chance Replacement)
• LRU (Least Recently Used)
• NUR (Not Used Recently)
• LFU (Least Frequence Used)
• Working Set
• PFF (Page Fault Frequency)