이진 탐색 트리

이진 탐색 트리는 아래 그림과 같은데, 다음과 같은 특징을 가진다.

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노브보다 오른쪽 자식 노드가 크다.
• 이진 탐색 트리에서 탐색시간이 O(LogN)을 보장하려면 트리가 균형잡혀야 한다.

트리의 순회

• 트리 구조에 포함된 대표적인 순회 방법은 다음과 같다.

1. 전위 순회 (pre-order traverse): 부모 노드를 먼저 방문한 후, 왼쪽 자식 > 오른쪽 자식 노드를 방문 하는 방법
2. 중위 순회 (in-order traverse): 왼쪽 자식 방문 이후 부모 노드 방문, 이후 오른쪽 노드를 방문 하는 방법
3. 후위 순회 (post-order traverse): 왼쪽 자식 방문 > 오른쪽 자식 방문 이후 > 부모 노드를 방문 하는 방법

순회 방법을 헷갈리지 않는 방법은 제목에 모든 KEY가 있다. 원칙: 항상 왼쪽 자식 > 오른쪽 자식의 방문순서는 고정이다 pre / in / post는 부모노드의 방문순서가 어디에 있을지 정해준다. (e.g., pre일 경우에는 부모 > 왼쪽 자식 > 오른쪽 자식)

class Node:

  def __init__(self, data, left_node, right_node):
    self.data = data
    self.left_node = left_node
    self.right_node = right_node


n = int(input())
tree = {}

for i in range(n):
  data, left_node, right_node = input().split()
  if left_node == 'None':
    left_node = None
  if right_node == 'None':
    right_node = None
  tree[data] = Node(data, left_node, right_node)


def pre_order(node):
  print(node.data, end=" ")
  if node.left_node != None:
    pre_order(tree[node.left_node])
  if node.right_node != None:
    pre_order(tree[node.right_node])


def in_order(node):
  if node.left_node != None:
    in_order(tree[node.left_node])
  print(node.data, end=" ")
  if node.right_node != None:
    in_order(tree[node.right_node])


def post_order(node):
  if node.left_node != None:
    post_order(tree[node.left_node])
  if node.right_node != None:
    post_order(tree[node.right_node])
  print(node.data, end=" ")


pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])
print()

!!Tree 상에서 이동하는 tree[node.left/rigt_node]를 헷갈려서 시간을 좀 허비했다.. 다음부터는 사소한 곳에서 헷갈리지 말도록 하자!

순차탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.
• 일반적으로 정렬되지 않는 데이터를 찾아야할 때 사용되며, 리스트 자료형에서 count() 메서드를 이용할 때에 내부에서는 순차 탐색이 수행되곤 한다.

input_data = input().split()
n = int(input_data[0])
target = str(input_data[1])

array = input().split()

def sequential_search(n, target, array):
  for i in range(n):
    if array[i] == target:
      return i + 1
  return None

print(sequential_search(n, target, array))

• 앞에서부터 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도를 가지고 있다.

이진탐색

• 데이터가 정렬되어 있다고 가정하고 사용하는 알고리즘
• 리스트의 시작, 끝, 중간을 안다고 할때, 찾으려는 데이터와 중간에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다.

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

def binary_search(array, target, start, end):
    if start > end:
     return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

result = binary_search(array, target, 0, n - 1)

if result == None:
  print("No 원소")
else:
  print(result + 1)

1. 리스트가 정렬되어 있다는 가정하여 target과 중간점을 비교하여 데이터를
2. (1) 중간점과 같으면 return (2) 중간점과 큰 데이터들과 비교를 지속할지 (3) 중간점보다 작은 데이터들과 비교를 지속할지를 결정한다.
3. 재귀함수를 통해 logN의 시간복잡도를 보장해준다.

python의 bisect library 활용해서 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
  # 정렬된 순서를 유지한 채 배열 a에 x를 삽입할 가장 오른쪽 idx 반환
  right_index = bisect_right(a, right_value)
  # 정렬된 순서를 유지한 채 배열 a에 x를 삽입할 가장 왼쪽 idx 반환
  left_index = bisect_left(a, left_value)
  return right_index - left_index

a = [1,2,3,3,3,3,4,4,8,9]
print(count_by_range(a,4,4))

parametric search

• 최적화 문제를 결정문제로 바꾸어 해결하는 기법
• 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

실전문제 1

• 입력조건: 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다.
• 둘째 줄에는 떡의 개별 높이가 주어진자. 떡 높이는 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 . 수있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

start = 0
end = max(array)

result = 0

while (start <= end):
  total = 0
  mid = (start + end) // 2
  for x in array:
    if x > mid:
      total += (x - mid)

  if total < target:
      # mid 기준으로 모든 합이 target보다 적으면 mid가 크다는 의미 > mid를 감소
    end = mid - 1
  else:
   # mid 기준으로 모든 합이 target보다 크거나 같다
   # 현재 mid가 가장 좋은 point가 될 수 있지만 증가 가능성 있음 > mid를 증가 
    result = mid
    start = mid + 1

print(result)

실전문제 2

• 입력조건: 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
• 출력조건: 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):  
  right_index = bisect_right(a, right_value)
  left_index = bisect_left(a, left_value)
  return right_index - left_index

n,x = list(map(int, input().split()))
array = list(map(int, input().split()))


count = count_by_range(array, x, x)

if count == 0:
  print(-1)
else:
  print(count)

이 문제의 KEY는 일반적인 선형탐색을 하면, 시간초과판정을 받기 때문에 O(LogN)으로 탐색으로 수행하는 이진탐색 알고리즘을 사용해야 한다라는 제한조건이 존재한다.

선택정렬

• 처리(=정렬)되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
  min_index = i
  for min_index in range(len(array)):
    if array[i] < array[min_index]: 
      array[min_index], array[i] = array[i], array[min_index]

print(array)

선택정렬의 시간복잡도

• 매번 정렬되지 않은 N번만큼의 가장 작은 수를 앞으로 보내야 한다.
• N, (N-1), (N-2), ... 2
• $$(N^2+N-2)/2$$

삽입정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬.
• 즉, 현재 인덱스 앞에 있는 모든 아이템들은 모두 정렬이 되어있다고 가정하고, 현재 인덱스의 아이템을 그 앞에 있는 아이템들과 비교해서 올바른 위치에 삽입하는 알고리즘이다.

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
  for j in range(i,0,-1): # i는 index를 하나씩 줄이면서 첫번째 원소까지
    if array[j] < array[j-1]:
      array[j] , array[j-1] = array[j-1], array[j]
    else: # 자기 자신보다 작은 원소를 만나면 멈춤 (i번째 이전까지는 모두 정렬이 되어있다고 가정하기 때문)
      break

print(array)

삽입정렬의 시간복잡도

• 반복문을 2번 돌아야함으로 $O(N^2)$의 시간복잡도이나
• 현재 리스트가 거의 정렬되어있을 경우 매우 빠르게 동작함.

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)으로 상정합니다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]


def quick_sort(array, start, end):
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  # pivot을 기준으로 left, right을 탐색할 예정인데 엇갈리는 순간 pivot을 기준으로
  # 정렬이 되어있다는 의미임으로 while문 탈출.
  while (left <= right):
    # 좌측의 데이터에 대해서, puvot보다 큰 데이터를 찾기 때문에
    # piovot보다 같거나 작으면 한칸씩 이동
    while left <= end and array[pivot] >= array[left]:
      left += 1
    # 우측의 데이터에 대해서, puvot보다 작은 데이터를 찾기 때문에
    # piovot보다 같거나 크면 한칸씩 이동
    while start < right and array[pivot] <= array[right]:
      right -= 1

    # pivot을 기준으로 left에 있는 데이터보다 right에 있는 데이터가 더 큰 상황
    # index 상으로도 left > right인 상황.
    # 이 말은 곧 pivot이 제대로 동작하고 있음을 의미하니, pivot을 right
    # (좌측의 최우단)에 배치시킨다.
    if left > right:
      array[pivot], array[right] = array[right], array[pivot]
    # pivot을 기준으로 left에 있는 데이터보다 right에 있는 데이터가 더 큰 상황
    # 그러나 index 상으로 left < right인 상황 따하서 둘의 데이터 순서를 바꾸어 준다.
    else:
      array[left], array[right] = array[right], array[left]

  quick_sort(array, start, right - 1)
  quick_sort(array, right + 1, end)


quick_sort(array, 0, len(array) - 1)
print(array)

개인적으로 이해하기 어려웠던 알고리즘이라 코드를 짜면서 들었던 생각들이다.

• 한번의 함수 호출 후에 pivot이 어느 위치에 있을지 모르겠지만, pivot 좌측에는 pivot보다 작은 값들이 pivot 우측에는 pivot보다 큰 값들이 위치해 있도록 하는 것이 목표인 알고리즘이다. (log 복잡도를 위해)
• 따라서 pivot이 맨 첫 데이터라고 할때, 왼쪽에 있는 데이터를 searching할때는 pivot보다 큰 데이터를, 오른쪽에 있는 데이터를 searching할때는 pivot보다 작은 데이터를 search하면 되며 한번 탐색한 index는 더이상 볼 필요가 없기 때문에 while문으로 탐색해도 무방하다. (대신 out-of-index 뜨지 않게 종료조건 잘 맞춰주기)
• (좌>우로 탐색해서) 찾은 pivot보다 큰 데이터의 index가 (우>좌로 탐색해서) 찾은 pivot보다 작은 데이터의 index보다 클 경우 pivot을 기준으로 정렬이 되어있다는 것을 의미한다. 따라서 (우>좌로 탐색해서) 찾은 pivot보다 작은 데이터와 pivot의 위치를 바꿔주면 pivot을 기준으로 좌측은 크기가 무조건 작고, 우측은 무조건 큰게 보장이 되기에 좌/우 영역에 한정해서 재귀호출을 걸어주면 된다.

내가 했던 고민들을 보다 더 직관적으로 파이썬으로 풀어서 반영해준 코드는 아래와 같다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8,7,7]

def quick_sort(array):
  print(array)
  if len(array) <= 1:
    return array

  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x<=pivot]
  right_side = [x for x in tail if x>pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

• if len(array) <=1인 이유는 left_side나 right_side에 빈 array가 넘어올 수도 있기 때문이다.

계수(count) 정렬

• 데이터의 크기 범위가 제한되어 정수 형태로 표현되어 있을때 사용가능한 정렬 알고리즘이다.
• 데이터 개수가 N, 데이터(양수) 중 최대값이 K일 때 최악의 경우애도 수행시간 $O(N+K)$을 보장한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 7, 7]
count = [0] * (max(array) - min(array) + 1)  # array의 max, min값을 알고 있다고 가정

for i in array: # N회 반복
  count[i] += 1

for idx, cnt in enumerate(count): # K회 반복
  for _ in range(cnt): # N회 반복
    print(idx, end=" ")

• 이 알고리즘은 array내 최소값과 최대값이 무엇인지 알고 있어야 사용할 수 있다. (차이+1 만큼의 count array를 선언)
• 또한 동일한 값을 가지는 데이터가 여러개 등장할 때 효율적으로 사용할 수가 있다.

문제 - 두 배열의 원소 교체

• 첫번째 줄에 n,k가 공백되어 입력된다. (0<=N<=100,000, 0<=K<=N)
• 두번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 100,000,000보다 작은 자연수이다.
• 세번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수입니다.
• 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

for i in range(k):
  if a[i] < b[i]:
    a[i], b[i] = b[i], a[i]

print(sum(a))

• 첫번째 배열은 오름차순, 두번째 배열은 내림차순으로 정렬한 후 1>K까지 원소를 탐색하면서 첫번째 배열의 원소가 두번째 배열의 원소보다 작으면 swapping하면 벼열 A의 합을 최대화할 수 있다.

Preliminary

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 탐색에서 많이 쓰이는 자료구조는 다음과 같다.

• Stack: LIFO (Last In First Out)의 형태로 데이터가 유통되는 자료구조 > python에서 list & append() & pop()로 구현할 수 있음
• Queue: FIFO (First In First Out)의 형태로 데이터가 유통되는 자료구조 > python에서 from collections import deque를 사용 & append() '오른쪽으로 들어와서' & popleft() '왼쪽으로 나감' 로 구현 가능

Recursive Function

재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()

위같은 함수를 호출하면 max recursion depth에 도달해서 오류메세지를 호출한다. 따라서 재귀함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 포함한 재귀 함수 예제

def recursive_function(i):
    # 100 번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀 함수를 호출을 종료합니다.')
recursive_function(1)

유클리드 호제법이 재귀함수를 활용하는 대표적인 예시이다.

• 두 자연수 A,B에 관하여 (A>B) A를 B로 나눈 나머지를 R이라고 합니다.
• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.

def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

print(gcd(192,162))

DFS (Depth First Search)

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 스택 자료구조 (혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드(직전에 방문한 노드에 아래 방향으로 간선이 뻗은 노드)가 하나라도 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

예제 01

아래와 같은 그래프가 있을 때, 시작 노드 1을 기준으로 번호가 낮은 인접 노드를 기준으로 DFS를 수행하시오.

gragh = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]  
]

visited = [False]*9

def dfs(gragh, i, visited):
  # 현재 노드를 방문처리
  visited[i] = True
  # 방문한 노드를 print
  print(i, end=' ')
  for v in gragh[i]:
    # 인접한 노드 중에서 방문하지 않았으면 재귀호출로 방문진행
    if not visited[v]:
      dfs(gragh, v, visited)

dfs(gragh, 1, visited)

위의 코드를 공부하면서 가장 중요하다고 느낀 2가지는 다음과 같다.

• 그래프구조를 표현할때, 인점노드를 기준으로 표현하며 그래프 상에서 첫번째 노드는 index=0을 기준으로 표현하는 것이다. (이렇게 하면 문제상황에서 표현하고자 하는 index와 동일하게 표현할 수 있게 된다.)
• 재귀호출을 할 때, 깊은 노드에서 이미 인접노드들을 다 방문하면 if not visted[v] == false임으로 자연스럽게 본인의 dfs(graph,i,visted)가 return 없이 마무리 되고 본인을 호출했던 dfs(graph,i,visted)으로 다시 돌아가게 된다.

BFS (Breadth First Search)

• BFS는 넓이 우선 탐색이라고도 부르며 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다.
• BFS는 큐 자료구조 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

from collections import deque

gragh = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8],
         [1, 7]]

visited = [False] * 9

def bfs(gragh, i, visited):
  # 탐색 시작 노드를 큐에 삽입하고 방문처리
  queue = deque([i])
  visited[i] = True
  # 방문한 노드를 print
  print(i, end=' ')
  while queue:
    # 큐에서 노드를 꺼냄 
    v = queue.popleft()
    for i in gragh[v]:
      # 인접노드가 방문하지 않은 노드면 전부다 방문처리
      if not visited[i]:
        queue.append(i)
        visited[i] = True
        print(i, end=' ')


bfs(gragh, 1, visited)

마찬가지로 BFS를 공부하면서 느꼈던 점은 2가지이다.

• 첫번째 노드에 대한 처리 : 첫번째 노드도 바로 큐에 삽입하고 '꺼낸 다음 인접한 이웃 노드의 방문여부를 탐색'한다. ''의 부분은 일반적인 노드들에 있어서 적용되는 함수인데 이게 예외적인 첫번째 노드에도 어떻게 잘 적용되도록 코드를 짜는게 관건으로 보인다.
• BFS는 해당 노드에 도착했을때 인접한 노드를 모두 방문처리하면서 search하는 알고리즘이다. (vs DFS는 해당 노드에 도착했을때 한 노드씩 타고 들어가면서 search하는 알고리즘이다.)

문제 01 - 음료수 얼려 먹기

• 첫번째 줄에 얼음 틀의 세로 길이 Nrhk 가로 길이 M이 주어진다. (1<=N,M<=1000)
• 두번째 줄부터 N+1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
• 한번에 만들 수 있는 아이스크림의 개수를 출력한다.

N, M = map(int, input().split())
graph = []
for _ in range(N):
  graph.append(list(map(int, input())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

count = 0


def dfs(x, y):

  if 0 > x or N <= x or 0 > y or M <= y:
    return False

  if graph[x][y] == 0:
    graph[x][y] = 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      '''
      재귀 호출된 함수가 반환하는 
      True/False에 너무 집착하지 말자
      '''
      dfs(nx, ny)
    return True
  else:
    return False


for i in range(N):
  for j in range(M):
    if dfs(i, j) == True:
      count += 1

print(count)

이 문제의 접근법은 다음과 같다.

전체 노드를 방문하는 것은 기본적인 전제이다. 특정 노드의 인접 노드가 아직 방문하지 않았다면 DFS로 연결된 모든 방문 지점을 방문하고 (도착하면 > 방문표시 > 재귀함수 호출) count를 추가하는 것이다.

• 이 문제나 위의 재귀함수 문제를 풀면서 느꼈던 것중에 제일 헷갈렸던 부분은 (1) 처음으로 호출했던 함수의 반환값이랑 (2) 그 이후에 재귀적으로 호출하는 함수의 반환값이랑 다르게 처리 로직을 두고 생각해도 된다는 점이다.

• 위의 문제의 경우 첫번째 호출하는 함수는 True/False를 반환하고 이것 받아서 for문에 있는 어떤 처리를 하지만 재귀적으로 호출하는 함수는 굳이 반환된 True/False를 가지고 무엇을 하지 않는다 (호출되고 그래프 안에 숫자 표기만 바꿔줄뿐). 내가 재귀적으로 호출한 함수들도 이 반환된 True/False로 무엇을 해야하도록 함수를 짜야한다는 강박때문에 시간이 좀 오래걸린 문제이다.

문제 02 - 미로 탈출

• 첫째 줄에 두 정수 N, M (4<=N ,M <=200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 불어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

from collections import deque

N, M = map(int, input().split())
graph = []
for _ in range(N):
  graph.append(list(map(int, input())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

[나의 풀이]

def bfs(x, y):
  count = 0
  queue = deque()
  queue.append((x,y))
  graph[x][y] = 0
  while queue:
    x, y = queue.popleft()
    count +=1
    for i in range(0, 4, 2):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
        graph[nx][ny] = graph[nx][ny] - 1
        queue.append((nx,ny))

  assert x == (N-1) and y == (M-1)

  return count

[공식 풀이]

def bfs(x, y):
  queue = deque()
  queue.append((x, y))
  while queue:
    x, y = queue.popleft()
    for i in range(0, 4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= N or ny < 0 or ny >= M:
        continue
      if graph[nx][ny] == 0:
        continue
      if graph[nx][ny] == 1:
          # 인접 노드에 대한 값을 queue에 넣기 전에 값을 업데이트
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))

  print(graph)
  return graph[N - 1][M - 1]


print(bfs(0, 0))

• 위의 문제의 정석적인 접근법은 다음과 같다.

  (노든 간선간의 가중치가 같다는 가정 하에) BFS를 활용하여 시작 시점에서부터 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.

  특정한 노드(이전 노드에 의해서 인접해 있기 때문에 밤문하게 된 노드)를 방문하면 그 이전 노드의 거리에 1(문제 상황마다 다름)을 더한 값을 큐에 넣는다.

• 이전 DFS 문제도 그렇고 가능한 모든 경로를 모두 탐색하고 ((1,1) > (1,2)로 가서 다시 (1,1)을 큐에 넣는 상황도 발생함), 그 중 최적의 값을 찾는다는 가정을 하지 않았다. 하지만 문제 풀이를 보면 그렇게 풀도록 설계가 되어있다. (앞으로 이렇게 푸는 사고가 필요할 듯 하다.)

그리디 & 구현

구현

• 머릿속에 잇는 알고리즘을 소스코드로 바꾸는 과정이다.
• 이 강의에서는 아래 2가지 개념과 구현을 하나의 강의에서 동시에 설명하고 있다.

완전탐색

• 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션

• 문제에서 제시한 알고르짐을 한 계단씩 차례대로 직접 수행해야하는 문제 유형

상하좌우 문제

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진자. (1<=<=100)
• 둘째 줄에 여행가A가 이동할 계호기서 내용이 주어진다. (1<=이동회수<=100)
• 첫번째 출바공간이 (1,1) 좌측하단이 (N,N) 공간 밖의 공간으로 이동은 무시한다는 가정하에 여행가A가 출발공간에서 이동을 시작해서 도착할 지점의 좌표 (X,Y)를 공백으로 구분해서 출력하세요.

n = int(input())
directions = list(input().split(" "))

x, y = 1, 1

dx = [0,0,-1,1]
dy = [1,-1,0,0]
move_types = ['R','L','U','D']

for direction in directions:
  for i in range(len(move_types)):
    if direction == move_types[i]:
      nx = x + dx[i]
      ny = y + dy[i]
  if nx < 1 or ny < 1 or nx > n or ny > n:
    continue
  x, y = nx, ny

print(x, y)

이문제의 핵심사항을 정리해보면 다음과 같다.

• 시뮬레이션 문제로 이동가가 이동할 수 있는 방향을 방향벡터로 설정해주기. (시뮬레이션의 큰 그림을 간단히 표현할 수 잇는 것을 구현시키는 방법을 빠르게 찾는게 point로 보여짐)
• 문제의 조건에 따라 좌표 공간을 벗어나는 경우 'continue'를 사용해서 loop문 통과시켜주기.

  시뮬레이션 문제의 전반적인 큰 그림을 배우기 가장 좋은 문제라고 생각이 든다.

시각 문제

• 정수 N이 입력되면 00시 00분부터 00초부터 N시 59분 59초까지 모든 시각 중에서 3이 하나라도 포함하는 모든 겨웅의 수를 구하는 프로그램을 작성하시오.

내가 처음에 찬 코드이다.

n = int(input())

count = 0

only_second_3 = 15 * 60
only_minutes_3 = 45 * 15

for i in range(0, n + 1):
  if i % 3 != 0 or i == 0:
    count += (only_second_3 + only_minutes_3)
  else:
    count += 3600

print(count)

• 분을 기준으로 2가지로 나누어서 문제를 푼다.

  • 분에 숫자 3이 없는 경우, 초에 반드시 3이 있어야함
  • 분에 숫자 3이 있는 경우.

• 이후, 다시 시를 숫자 3이 있는 경우와 없는 경우로 나누어서 푼다.

하지만 이는 완전탐색으로 문제를 푸는게 아니었다.

n = int(input())

count = 0

for h in range(0, 1 + n):
  for j in range(0, 60):
    for k in range(0, 60):
      if '3' in str(h) + str(j) + str(k):
        count += 1

print(count)

• 완전탐색으로 문제를 푸는 방법은 1-h시간동안 모든 j,k를 탐색하도록 string 시각을 선언한 후 이 때 3이 있는지 검색하는 식으로 코드가 작성되었다. (일종의 테크닉인듯...)

왕실의 나이트

• 8x8 체스판에서 행은 1..8, 열은 a..h로 표현된다.
• 첫째 입력에 현재 나이트가 위치한 곳의 좌표가 입력된다. (eg., a1)
• 나이트는 수직/수평 이동 2칸 이후 수평/수직 이동 1칸만이 가능하다.
• 첫째 줄에 나이트가 이동할 수 있는 모든 경우의 수를 구하시오.

x = input()
row = int(x[1])
column = int(ord(x[0])) - int(ord('a')) + 1

count = 0

directions = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2),(1, 2)]

for dx, dy in directions:
  nx = row + dx
  ny = column + dy
  if nx > 0 and nx <= 8 and ny > 0 and ny <= 8:
    count += 1

print(count)

이 문제가 개인적으로 가장 헷갈리는 요인들이 많았는데 정리해보면 다음과 같다.

• 행,열이 다른 문자열로 표현되어있는데 아스키 코드를 활용해서 int형으로 바꿔주면 보다 수월한 문제풀이가 가능하다는 것을 늦게 떠올렸다. (+ ord(a)-ord(a)0임으로 행과 맞춰주기 위해서는 +1도 생각하기)
• 입력은 열/행 순으로 주어졌는데, 다른 문제들의 경우 방향벡터에서 step이 (행,열)로 되어있는 경우가 많아서 위에서 선언한 걸 그대로 사용했을 경우 오답이 산출될 수도 있다.
• 역시 다른 시뮬레이션&완선탐색과 마찬가지록 가능한 모든 이동경로를 방향벡터로 선언한다는 아이디어를 빠르게 생각해내는게 관건으로 보인다.

그리디 알고리즘

그리디 알고리즘은 현재 time-step에서 가장 좋은 선택지를 선택해 문제를 해결하는 알고리즘이다. 현재 time-step에서 가장 좋은 선택지를 선택하기 때문에 현재 time-step의 선택이 미래에 어떤 영향을 미칠지에 대해서는 고려하지 않는다.

그리디 알고리즘의 정당성

• 그리디 알고리즘을 이용해 해법이 구해졌을 때 그 해법이 왜 최적의 해법으로 귀결되는가 검토하는 과정이 필요하다.

예제 1

어떠한 수 N이 1이 될때까지 다음의 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.

   N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.

정답코드

n, k = map(int, input().split())
count = 0

while True:
  target = (n // k) * k
  count += (n - target)
  n = target
  if n < k:
    break
  count += 1
  n //= k

count += (n - 1)
print(count)

이 코드의 장점은 2가지가 있다. (하나는 개인적인 생각)

• 한번 실행될때마다 빼기 연산과 나누기 연산을 한번에 실행시키기 때문에 시간복잡도가 log복잡도로 줄어든다.
• 위와 마찬가지로 빼기 연산을 한번의 연산에 처리했기 때문에 마지막에 count+= (n-1)로 통일성 있게 N=1을 만들어줄 수 있다. (통일성 있게 모든 하위 연산을 큰 하나의 연산 안에서 처리하도록 logic을 짜는 연산을 하는게 중요한 작업으로 보임)

예제 2

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나식 모든 숫자를 확인하며 숫자 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 구하시오.

정답코드

data = input()

result = int(data[0])

for i in range(1, len(data)):
  num = int(data[i])
  if num <= 1 or result <= 1:
    result += num
  else:
    result *= num

print(result)

이 코드에서 내가 간과한 부분은 다음과 같다.

• 그리디 알고리즘의 핵심은 현재 상황에서 가장 좋은 선택지를 고르는 것이다. 따라서, num이 1이하인 수이면 항상 result에 *=를 하는게 최적의 선택이도록 알고리즘을 설계해야 한다.

예제 3

한 마을에 모험가가 N명이 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포도를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. (조건1) 공포도가 X인 모험가는 반드시 X명이상으로 구성한 모험가 그룹에 참여해야하며 (조건2) 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

N = input()
scare_list = list(map(int, input().split()))
scare_list.sort()
result = 0
count = 0

for i in scare_list:
  count += 1
  if count >= i:
    result += 1
    count = 0

print(result)

이 문제를 접하면서 간과했던 점은 다음과 같다.

• 그룹수를 최대화하려면 공포도가 낮은 모험가부터 그룹을 지어서 보내야 최대한 많은 그룹을 만들 수 있다. > 공포도가 낮은 순으로 그룹을 만드는게 가장 최적의 선택이다.
• 그룹인원수를 count하면 그 count 이상이 되는 공포도 X가 포함되는 모험가를 그 그룹에 포함시켜서 모험에 보낼 수 있도록 코드를 작성해야 한다.

Adapter계열 논문이라고 봐도 무방하나,들은 adapter 계열들은 $y=f(x)$ 에서 $f$자체를 건드는 method이지만 Prompt tuning은 task마다 prompt를 update하기 때문에 $x$를 update하는 method이라고 소개한다.

1. Introduction

PLM을 활용해 dowmnstream을 해결하는 방법은 크게 2가지가 있다.

• Fine-Tuning: model parameter 전체를 downstream에 맞게 update 시키는 것 > 본 논문에서는 Model Tuning이라고 명명
• Prompting: model parameter freeze한 후 task desecription과 demonstration으로 task를 푸는 것 (few-shot learning) > 본 논문에서는 Prompt Design이라고 명명

Prompting이 가지고 있는 장점이 명확하지만 가지고 있는 단점 또한 명확하다.

1. task description에 error prone하다.
2. demonstration들 수에 의해서 prompt의 효용성이 달려있다. (=zero shot이 여전히 좋지는 않음)

따라서 여전히 특정 task에 대한 성능은 Prompting이 (굉장히 큰 모델사이즈(175B GPT3)를 가지고 있음에도) Fine-tuning을 따라잡지 못하고 있다.

하지만 Prompt라는 것 자체가 text임으로 discrete하기 때문에 backpropagation으로 optimization할 수 있는 대상도 아니다.

이를 해결하기 위해 'Prefix-Tuning: Optimizing Continuous Prompts for Generation'라는 논문이 'prefix를 adapter 형식을 차용해 parameterized 했다면 본 논문은 보다 범용적인 'Prompt'를 parameterized했다고 보면 될 것 같다.

2. Prompt Tuning

Prompt Tuning 방법론은 굉장히 간단한다.

모델 parameter $\theta$는 freeze하고 prompt parameter $\theta_p$ 만을 모델에 추가한 후 update하는 것이다.

• Input ${x_1, x_2, ...x_n}$ : $X_e\in \mathbb{R^{n\times e}}$
• Prompt : $P_e\in \mathbb{R^{p\times e}}$

모델은 $[P_e;X_e]\in \mathbb{R^{(p+n)\times e}}$를 입력으로 받게 되고 $Pr_{\theta,\theta_p}(Y|[P_e;X_e])$를 maximize하게 training되면서 $\theta_p$만을 update하는 형식이 된다.

논문에서 언급된 부분은 이게 끝이다. (결국 코드를 까봐야 한다,,)

Transformer구조에서 $\theta_p$에 해당되는 부분이 굉장히 많은데 결론적으로 말하면 Prompt Tuning이 업데이트 하는 부분은 word embedding layer이다.

정리를 하면 PLM은 freeze한채로 특정 task에 대응되는 prompt word embedding layer를 각 task마다 fine tuning해서 쓰자!가 Prompt tuning의 주요 contribution이다. (실제로 T5-XXL를 정교하게 prompt tuning 하면 성능이 좋음)

Downstream task마다 Prompt Embedding을 Fine-tuning해야되는 것을 알았으니 이제 결정할 것은 Prompt Design이다.

1. Prompt Embedding Intialization

• Random Initilziation
• PLM most common voab embedding에서 sampling하기
• downstream task의 class label의 string에 대응되는 embedding 가져오기 (prompt의 길이가 길 경우 2번째 방법에서 나머지 길이 채우기)

2. Prompt의 길이

• P가 parameter 사이즈랑 직결됨으로 작게하면서도 성능이 좋게하는걸 목표로 했다고 함 (개인적으로는 LM에게 task specific한 정보를 줄 정도의 길이는 되어야하지 않을까라고는 생각합니다. 실제로 실험결과를 봐도 20token정도면 model size에 상관 없이 어느정도 안정적인 결과를 가져오는 것을 볼 수 있습니다)

Huggingface PEFT 구현

@dataclass
class PromptTuningConfig(PromptLearningConfig):
    """
    This is the configuration class to store the configuration of a [`~peft.PromptEmbedding`].
    Args:
        prompt_tuning_init (Union[[`PromptTuningInit`], `str`]): The initialization of the prompt embedding.
        prompt_tuning_init_text ( Optional[`str`]): The text to initialize the prompt embedding.
            Only used if `prompt_tuning_init` is `TEXT`
        tokenizer_name_or_path ( Optional[`str`]): The name or path of the tokenizer.
            Only used if `prompt_tuning_init` is `TEXT`
    """

    prompt_tuning_init: Union[PromptTuningInit, str] = field(
        default=PromptTuningInit.RANDOM,
        metadata={"help": "How to initialize the prompt tuning parameters"},
    )
    prompt_tuning_init_text: Optional[str] = field(
        default=None,
        metadata={
            "help": "The text to use for prompt tuning initialization. Only used if prompt_tuning_init is `TEXT`"
        },
    )
    tokenizer_name_or_path: Optional[str] = field(
        default=None,
        metadata={
            "help": "The tokenizer to use for prompt tuning initialization. Only used if prompt_tuning_init is `TEXT`"
        },
    )

    def __post_init__(self):
        self.peft_type = PeftType.

huggingface에서는 prompt_tuning_init이 Prompt Embedding Intialization하는 방법이고

• prompt_tuning_init.RANDOM : random initialization
• prompt_tuning_init.TEXT: task instruction으로 구성된 PLM의 token vocab embedding으로 initialize하는 방법이다. (e.g., Predict if sentiment of this review is positive, negative or neutral"가 task instruction이면 tokenzier가 tokenize한 후 PLM embedding layer를 copy떠서 prompt encoder로 활용함)

downstream task의 class string representation 별로 embedding copy 떠오는 건 아쉽게도 huggingface도 구현이 쉽지 않았나 보다.

class PromptEmbedding(torch.nn.Module):
    """
    The model to encode virtual tokens into prompt embeddings.
    Args:
        config ([`PromptTuningConfig`]): The configuration of the prompt embedding.
        word_embeddings (`torch.nn.Module`): The word embeddings of the base transformer model.
    **Attributes**:
        **embedding** (`torch.nn.Embedding`) -- The embedding layer of the prompt embedding.
    Example::
        >>> from peft import PromptEmbedding, PromptTuningConfig >>> config = PromptTuningConfig(
                peft_type="PROMPT_TUNING", task_type="SEQ_2_SEQ_LM", num_virtual_tokens=20, token_dim=768,
                num_transformer_submodules=1, num_attention_heads=12, num_layers=12, prompt_tuning_init="TEXT",
                prompt_tuning_init_text="Predict if sentiment of this review is positive, negative or neutral",
                tokenizer_name_or_path="t5-base",
            )
        >>> # t5_model.shared is the word embeddings of the base model >>> prompt_embedding = PromptEmbedding(config,
        t5_model.shared)
    Input Shape: (batch_size, total_virtual_tokens)
    Output Shape: (batch_size, total_virtual_tokens, token_dim)
    """

    def __init__(self, config, word_embeddings):
        super().__init__()

        total_virtual_tokens = config.num_virtual_tokens * config.num_transformer_submodules
        self.embedding = torch.nn.Embedding(total_virtual_tokens, config.token_dim)
        if config.prompt_tuning_init == PromptTuningInit.TEXT:
            from transformers import AutoTokenizer

            tokenizer = AutoTokenizer.from_pretrained(config.tokenizer_name_or_path)
            init_text = config.prompt_tuning_init_text
            init_token_ids = tokenizer(init_text)["input_ids"]
            # Trim or iterate until num_text_tokens matches total_virtual_tokens
            num_text_tokens = len(init_token_ids)
            if num_text_tokens > total_virtual_tokens:
                init_token_ids = init_token_ids[:total_virtual_tokens]
            elif num_text_tokens < total_virtual_tokens:
                num_reps = math.ceil(total_virtual_tokens / num_text_tokens)
                init_token_ids = init_token_ids * num_reps
            init_token_ids = init_token_ids[:total_virtual_tokens]

            word_embedding_weights = word_embeddings(torch.LongTensor(init_token_ids)).detach().clone()
            word_embedding_weights = word_embedding_weights.to(torch.float32)
            self.embedding.weight = torch.nn.Parameter(word_embedding_weights)

    def forward(self, indices):
        # Just get embeddings
        prompt_embeddings = self.embedding(indices)
        return prompt_embeddings

• num_virtual_tokens: 위에서 설명한 Prompt의 길이라고 보면 되겠다. prompt_tuning_init.RANDOM할 경우에는 이 길이만큼 embedding을 생성해주고, prompt_tuning_init.TEXT할 경우에는 task description만큼 그 길이만큼 truncation하거나 반복생성해서 입력으로 넣어준다.

PEFT main model code를 까보면 Model forwarding을 할때는 임의의 prompt token index를 arrange함수를 만들어줘서 (e.g.,[0,,,20]) 위에코드로 생성한 prompt embedding을 매번 forwarding 시켜준다고 보면 된다.

3. Unlearning Span Corruption

T5의 Pre-training MLM

• Input: Thank you 〈X〉 me to your party 〈Y〉 week
• Output: 〈X〉 for inviting 〈Y〉 last 〈Z〉

T5를 full fine-tuning하면 pre-train에서 본 sentinel의 영향으로부터 자유로울 수 있지만 prompt tuning은 제한적이기 때문에 3가지 unlearning span corruption 기법을 제안했다.

• Span corruption: unlearning하지 않고 prompt tuning
• Span corruption + Sentinel : Sentinel 붙혀서 prompt tuning
• LM Adaption: prefix주고 natural text continuation 생성하는 식으로 100K step LM화 allevation 시킴

4. Experimental Results

Main Results

(model tuning = fine tuning (각 down stream task 마다 독립적으로 모델 fine tuning) / model tuning (multi-task) (1개 모델을 여러개 task에 대해서 multi-task fine-tuning) / Prompt Design = GPT3 / Prompt Tuning = 30,000 steps, learning rate =0.3 & batch size=32)

• T5-XXLarge까지 키우면 Prompt-Tuning만으로 Full fine-tuning 이길 수 있다.

Ablation Study

• Prompt Length
  • XXL size는 1token prompt만 사용해도 충분하다
  • 일반적으로 20token prompt embedding이면 성능을 뽑아낼 수 있다.
• Prompt Initializtion
  • XXL size 쓰지 않을꺼면 random initialize는 쓰지 말자
• Pre-training method
  • XXL size 쓰지 않을꺼면 LM 100까지는 Lm adaptation을 해줘야 한다.
  • 100k step까지는 해줘야 small size모델에서 T5가 prompt tuning에서 안정적으로 성능을 뽑아낼 수 있다.

Resilinece to Domain shift

Prompt Embedding만 Tuning하는 것의 가장 큰 장점은 PLM weight 자체는 freeze 되어 있기 때문에 $p_{\theta}$가 변형되지 않아 domain shift에 robust하다는 것이다.

이를 증명하기 위해 저자들은 QA와 Paraphrase detection task에서 Prompt Tuning이 Fine tuning보다 domian shift에 강건하다는 것을 보였다.

(SQuAD로 Tuning후에 out of domain MRQA dataset으로 evaluate)

• DROP <> wiki처럼 domain sharing 비율이 크지 않은 경우를 제외하면 prompt tuning이 domain shift에서 강건함

• paraphrase task에서도 비슷한 경향성을 보임

fine-tuning을 하긴 해야되는데 했을 때 발생하는 model weight distribution shift risk를 prompt에 전이시키는 것으로 보인다.

Introduction

저자들은 GPT-3와 같은 LLM의 zero shot 성능이 좋지 않은 이유를 demonstration이 없는 환경에서 모델이 pretraining data와 유사하지 않은 prompt를 해석해야 했기 때문이라고 지적한다.

FLAN은 모델에게 올바른 'instruct'을 지속적으로 해석하도록 학습한다면 저자들은 unseen task 상황에서도 zero shot performance가 향상될 수 있음을 보여준다.

'intstruct tuning'은 'instruction' 형식으로 LM을 fine-tuning하는 것이다. 위의 그림에서 보는 것처럼 해당 method의 가장 큰 장점은 pre-training fine-tuning과 prompting의 이점을 동시에 누릴 수 있다는 점이다.

Google은 137B LaMDA에 'instruct tuning'을 했는데 결론적으로 175B GPT3에 비해서 zero shot 성능은 당연하고 일부 few shot에서도 좋은 성능을 보였다.

2. FLAN: INSTRUCTION TUNING IMPROVES ZERO-SHOT LEARNING

'instruct tuning'의 motivation'은 간단하다. 자연어 형식으로 LM을 supervised training한다면 unseen task에 대해서도 instruct 형식으로만 준다면 충분히 풀 수 있다는 것이다. (일종의 자연어 task protocol을 모델에게 심어주려는 행위)

• 저자들은 62개의 text datasets을 12개의 task cluster로 분류했다.

• dataset마다 다양성을 위해 10개의 templates을 적용해서 자연어 instruction을 만들었다.

• Evaluation의 경우 굉장히 보수적으로 진행했다고 주장한다. 저자들의 말을 빌리면, 위의 dataset cluster 예시에서 read. comp. with commonsense cluster에 대해서 evaluation할 때 read. comp.과 commonsense reasoning instruct tuning에서 제외했다고 한다.

• instruction 형식으로 모든 task를 해결할 경우 classification에서 문제가 생길 수 있다. ("yes" / "no" 경우 학습과정에서 LM이 정확히 저 두 토큰의 logit만 높힌다는 보장이 없다) 이를 해결하기 위해 GPT3에서는 "yes" / "no" 중 확률이 높은 대답을 예측값으로 활용했는데 보다 더 instruct의 활용을 극대화하기 위해 FLAN은 접미사+토큰 활용한 아래의 방법을 활용해 자연어 대답을 생성해 분류문제를 해결한다.

• Pretraning Model은 LaMDA를 활용했다.

• Training detail: dataset마다 크기를 맞춰주기 휘해 training size를 30k로 맞춰주었다. (input and target sequence lengths used in finetuning are 1024 and 256, respectively.)

3. Results

이전에 언급했던것처럼 evaluation은 held-out cluser들로 이루어졌다.

Baseline은 GPT-3 175B, GLaM 64B/64E, LaMDA-PT (LaMDA의 pre-training 버전으로 GPT3의 prompt 활용했다고 함)을 사용했다.

결과적으로 GPT-3 175B보다 zero-shot은 20/25개 few-shot은 10/25개 우위를 GLaM 64B보다 zero-shot은 13/19개 one-shot은 11/19개 우위에 있는 결과를 거두었다고 한다.

특히 instruction이 효과가 있었던 데이터셋은 'NLI, QA, translation, struct-to-text'었고 'commonsense reasoning and coreference resolution tasks that are formatted as finishing an incomplete sentence or paragraph'처럼 이미 language modeling로 형식화되어있는 task에서는 큰 효과가 없었다고 한다.

FLAN은 7개의 task (commonsense reasoning and coreference resolution tasks) 중 3개에서만 LaMDA-PT의 성능을 넘었다고 한다. 저자들은 그 이유가 pre-raining과 fine-tuning 목적함수가 redunant하게 overlap되는 부분이 많은게 성능에 도움이 되지 않는다고 주장한다.

4. ABLATION STUDIES & FURTHER ANALYSIS

4.1. NUMBER OF INSTRUCTION TUNING CLUSTERS

상호 베타적인 cluster로 instruct tuning 할수록 UNSEEN TASK에 대해서 ZERO SHOT 성능이 향상된다.

4.2 SCALING LAWS

이전과 동일하게 NLI, closed-book QA, and commonsense reasoning을 held out set으로 두고 scaling law에 대한 실험을 돌린 결과는 아래와 같다.

모델 사이즈가 8B이상 커져야 instruction tuning이 유효해지는데, 저자들은 이를 두고 ~40 task 이상의 instructions을 학습하기에 그 충분한 capacity가 필요하지 않았나라고 주장한다.

4.3 ROLE OF INSTRUCTIONS

저자들은 모델이 multi-task 학습능력이 아닌 instruct 해석능력 때문에 성능이 좋아진 것을 보여주기 위해 instruction을 제외한 실험도 보여주었다.

실험세팅은 2가지이다.

(1) no template setup (e.g., for translation the input would be “The dog runs.” and the output would be “Le chien court.”) (2) dataset name setup (e.g., for translation to French, the input would be “[Translation: WMT’14 to French] The dog runs.”).

4.4 INSTRUCTIONS WITH FEW-SHOT EXEMPLARS

16개의 demonstration을 붙혀 few-shot setting에서의 실험을 돌렸는데 struct to text, translation, and closed-book QA처럼 large complex output space를 가진 task에서 성능이 향상되었고 few shot이 전반적으로 (당연히) std를 줄여주었다고 한다.

Google은 instruct learning을 통해 LM의 범용적인 활용도를 극대화하고 싶어하는 것 같다.

적은 sample안에 있는 context를 파악해 문제를 해결하는 in-context learning은 LLM이 보이는 강력한 능력 중 하나이다.

Incontext learning은 기존에 X,Y pair로 된 dataset을 finetuning하는 방식과는 다른 방식으로 inference를 진행한다. 우선, X,Y를 ‘template’을 통해 자연어의 형태로 모델에 입력될 수 있도록 변경해 준다. 다음, inference 하기 위한 X(i.e., new query) (figure에서의 good meal!)를 위한 몇가지 예시들을 모델 앞에 붙혀주는데 이를 demonstration들이라고 한다. LLM은 demonstration들을 활용해 new query에 대한 inference를 진행하며, 이러한 학습 방법은 gradient descent를 통해 model parameter를 update할 필요가 없다.

저자들은 ICL은 크게 3가지 장점을 갖는다고 주장하다.

1. 자연어로 작성된 demonstration이 인간과 LLM이 소통할 수 있는interface 역할을 한다.
2. 유추를 통해 새로운 정보를 해석/추론하는 인간의 능력을 모방한다. (딥러닝을 포함한 대부분의 성공적인 기술은 생물을 모방)
3. Training-free learning framework이다. (이건 관점에 따라 다른 것 같다)

ICL이 갖는 장점은 분명하고 GPT3에서 좋은 성능을 보여주는 것은 분명했지만

• Pretraining 단계에서 adaption을 통해 개선의 여지가 더 많이 남아 있고

  On the Relation between Sensitivity and Accuracy in In-context Learning

  Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?

• Prompt Template, In-context example selection, example order에 민감가며 (분산이 큼)

• ICL이 동작하는 것이 직관적으로는 이해가 가능하나 아직까지 명확하게 근거를 밝혀내지는 못하고 있다.

  Why Can GPT Learn In-Context? Language Models Secretly Perform Gradient Descent as Meta-Optimizers

  Transformers learn in-context by gradient descent

2. Overview

ICL 능력은 크게 2가지에 의해 영향을 받는다.

1. LLM이 ICL 능력 자체를 학습하는 training (pretraining)
2. 특정 task에서 어떤 demonstrastion을 활용해 inference를 할 것인가?

3. Definition and Formulation

저자들은 GPT3의 저자들을 따라 ICL을 다음과 같이 정의한다.

'In-context learning is a paradigm that allows language models to learn tasks given only a few examples in the form of demonstration.’

수식으로 정의하면 위와 같은데, 저자들은 기존의 (fine-tuning과 같은 방법으로) inference하고자 하는 candidate likelihood $p(y_{j}|x)$는 demonstation(=C)와 X, y_{j}가 같이 (1)과 같은 scoring function으로 표현될 수 있다고 주장하며, 이때 scoring funciton f는 query $x$와 demonstration이 주어졌을때 current answer $y_{j}$의 정답 가능성(how possible)을 측정하는 함수로 뒤에 더 자세하게 다룰 예정이라고 한다.

ICL과 다른 유사한 개념들 간의 차이점은 다음과 같다.

(1) Prompt Learning : Prompt learning은 desired output를 위해 어떻게 prompt를 설계할 것인가에 초점을 맞추고 있다. ICL의 demonstration 설계가 prompt tuning의 일부로 볼 수 있다.

(2) Few-shot learning : Few-shot은 제한된 sample들로 parameter update를 하지만 ICL은 그렇지 update하지 않는다.

4. Model Warmup

LLM의 ICL성능을 높히고 pretraining과 ICL inference 사이의 discrepancy를 줄이기 위해 미세한 continual training을 하는 것(parameter update & adding module)을 본 survey에서 ‘model warmup’이라고 정의한다. warmup은 ‘특정 task를 위해’ model parameter를 하는 것이 아니기 때문에 fine-tuning과는 구별된다.

##### 4.1. Supervised In-context Training

크게 2가지 방법이 있음

→ MetaICL (w/ demenstration)

pretraining 목적함수가 ICL에 최적화 된 것이 아니기 때문에 task에 맞는 demonstration example들을 구축해 ICL에 최적화된 continual training을 하는 것

→ Instruction tuning

‘task instructions’을 통해 continual training하는 것 (ex. LaMDA-PT and FLAN)

(각 task마다 demonstration을 설계해야하는 MetaICL과 달리 task explanation만 잘 설계해주면 됨)

##### 4.2. Self-supervised In-context Training

→ original raw text를 input-output pair를 가진 4가지 형태의 objectives로 변경해 continual learning을 진행 (Improving In-Context Few-Shot Learning via Self-Supervised Training)

##### Supervised In-context Training & Self-supervised In-context Training 둘다 데이터 양이 일정 수준 넘어가면 성능향상이 정체된다고 한다.

5. Prompt Designing

demonstration = prompt를 어떻게 설계하고, 구성 및 배열은 어떻게 할 것인가?

##### 5.1. Demonstration Organization

→ 어떻게 demonstration을 selection할 것인가에 대해서는 크게 unsupervised와 supervised가 있다. unsupervised에는 pre-defined metric(L2, Cosine) 기반해서 유사한 example을 가져오는 방법론이나 LLM을 직접 활용해 demonstration을 생성하는 방법이 있다 Kim et al. (2022a). Supervised 방법론으로는 처음에 BM25 같은 unsupervised retriever로 유사한 candidate들을 가져 온 후 scoring LM을 통해 candidate에 대해서 positive, negative labeling을 하게 한 후 supervised retriever을 학습하는 방식을 제안한 논문이 있다. (+ 강화학습을 사용했다는 논문도..)

→ demonstration order에 따라 model의 ICL performance가 민감하게 반응하는데, Liu et al. (2022)는 query에 유사한 example들이 query와 가까운 내림차순 방식을 활용한다. 그들은 ‘entropy metric’이 ICL performance와 양의 상관관계가 있음을 보이며 ‘entropy metric’을 best ordering을 선택하는데 사용함

##### 5.2. Demonstration Formatting

• 복잡한 추론능력을 요구하는 task일수록 (math, commonsense reasoning), chain-of-thought와 같은 x와 y사이의 intermediate 단계를 추가하는 것이 필요하다.

• 좋은 demonstration을 설계하는 것만큼 정확하게 task를 설명하는 Instruction을 설계하는 것은 Inference 성능을 향상시키는데 도움이 된다. 하지만 demonstration과 달리 instruction은 training data에서 얻을 수 없기 때문에, LLM을 활용한 방식 (p(instruction|demonstration) & automatic instruction generation and selection & bootstrap off its own generations)이 많이 연구되고 있다.

• arithmetic reasoning과 symbolic reasoning을 해결하기 위해 도입된 CoT에 따라 Input-Output Pair를 여러 stage로 나누어 추론하는게 가능해짐에 따라 각 reasoning step에 따라 다른 prompt를 주어서 ICL을 하는 연구들도 진행되고 있다고 한다.

6. Scoring Function

• LM prediction을 specific answer의 likelihood로 변환하는 작업

• Direct : highgest probability selected as the final answer → 제한적인 template design (answer가 항상 left)

• PPL : ppl of whole input sequence $s_{j}={C,s(x,y_{j},I)}$ (C: demonstration, x: query, y: label) → extra computation

• Channel : p(query|demonstration,label)

7. Analysis

• ICL 성능에 영향을 미치는 요인들에는 무엇이 있는가?

• Pretraining Corpus domain source가 size보다 성능에 중요한 영향을 미친다. 규모의 법칙 (pretraining step & model size)

• Inference demonstration samples (input-label pairing format, label space, input distribution, input-label mapping) demonstration sample order demonstration-query similarity

• How ICL Works? Distribution of Training Data, Learning Mechanism, Functional Modules (e.g., Transformer내 특정 head)를 분석해 왜 ICL이 동작하는지 연구하는 논문들이 그동안 발표되었다. 하지만 위의 연구들은 simple task와 small model에 국한되어있다는 한계가 있다고 한다. 또한, 저자들은 Meta Optimization 관점에서 ICL을 보는 것이 합리적이라고 이야기 하고 있음. (ICL의 key는 LM이 demonstration을 얼마나 잘 활용하는가에 있으니깐)**

8. Evaluation and Resources

• Traditional Tasks : 전통적인 fine-tuning setting에 ICL을 적용하려면 각 task마다 n개 (32 samples)를 sampling하는 few shot setting을 구축해야 한다. GPT-3의 경우 범용성은 좋으나 세부 task별로 대부분 fine-tuning SOTA를 이기지는 못함

• New Challenging Tasks

LLM의 다양한 역량을 측정하기 위해 BIG-Bench, Big-Bench의 어려운 버전인 Big-Bench Hard가 구축되었다. 또한 모델 사이즈가 커질 수록 성능이 떨어지는 task도 찾고 있는 중이라고 한다. 최근에는 ICL의 reasoning 능력을 특정하기 위한 데이터셋 (MGSM, LLMAS)도 구축되고 있다.

여전히 ICL 성능을 정확히 측정하기 위한 metric이 무엇인지에 대한 합의가 이루어지는 않은듯하다.

9. Application

demonstration이 명시적으로 추론에 대한 근거를 제시하기 때문에 ICL은 복잡한 추론과 복잡한 문제를 generalization하는 영역에서 좋은 성능을 보인다고 알려져 있다. 저자들이 제시하는 ICL의 application 방향은 크게 2가지이다.

• Model Editing

scale and a mixture of all types of demonstration examples strengthen the knowledge editing success rate of ICL. (demonstration을 활용해 LLM 안에 있는 knowledge를 수정할 수 있다)

• Data Annotation

GPT-3 사용해서 50%-96% 비용 절감이 있었다는 논문이 존재..

10. Challenges and Future Directions

• New Pretraining Strategies (bridge the gap between pretraining objectives and ICL)

• Distill the ICL Ability to Smaller Models

• 범용 LM과 마찬가지로 Dialog Model들도 Scaling Law가 적용된다는 선행 연구에 따라 구글에서도 application 단위에서 적용가능한 LLM 기반의 대화 모델을 제시했음 (논문에서 2B > 137B까지 size 늘리면서 실험적으로 보임)

• LaMDA는 대화모델이지만, 범용성을 지향했기 때문에 사실상 dialog 형식으로 multi-task를 처리하는 모델이다.

2. Related Works

• 선행연구처럼 model size를 scaling up할 수록 quality (sensibleness, specificity, and interestingness), safety, groundedness 지표는 상승했었다. 하지만 LaMDA는 fine-tuning하면 그 성능이 훨씬 더 향상될 수 있다는 것을 보여준다. (FLAN에서도 이러한 경향성이 계속해서 보여지는데 Google은 Fine-Tuning으로 (L)LM이 가지는 한계들을 극복해내려고 하고 있음)

quality (sensibleness, specificity, and interestingness), safety, groundedness는 대화모델의 성능을 측정하기 위해 존재했거나 본 논문에서 제안한 지표임

• 선행연구에 따라 LaMDA를 dialog-only data, crowdworker-annotated data (discriminating responses), external knowledge에 fine-tuning을 진행했다.

• perplexity, F1, Hits@1/N, USR, BLEU/ROUGE은 human과 correlation이 낮아서 LaMDA는 human evaluation으로만 평가했다.

• Multi-dimensional한 metric의 장점인 debuggability(결국 labeling을 통한 fine-tuning을 하기 위해)을 위해 위에서 보이는 것처럼 여러 metric으로 모델을 평가했다. ('MEENA'와 달리 'Interestingness'를 추가적인 metric으로 사용했음을 contribution으로 제시)

• 선행연구에 따라 separate layer를 훈련해 unsafe detect하도록 fine-tuning

• Attributable to Identified Sources (AIS) framework에 따라 2 step으로 crowdworker로부터 groundedness를 평가했다. (1) dialog turn에 있는 정보를 명확히 식별하고 이해했는가 (2) 거기 있는 정보들이 authoritative external source로부터 검증이 가능한가?

3. LaMDA pre-training

• Pre-training data composition: 50% dialogs data from public forums; 12.5% C4 data; 12.5% code documents from sites related to programming like Q&A sites, tutorials, etc; 12.5% Wikipedia (English); 6.25% English web documents; and 6.25% Non-English web documents.

저자들은 public web document에도 모델을 훈련시켜 LaMDA가 일반적인 LM의 능력도 가질 수 있도록 하였다. (코드도 포함하고, non-English document도 포함한 것을 보면 대화의 형식을 갖는 범용 LM을 구축하려고 한것 같음)

• Model Structure는 decoder only Transformer로 137B 모델의 스펙은 64 layers, dmodel = 8192, dff = 65536, h = 128, dk = dv = 128, relative attention, 32k (Meena에 비해서 상대적으로 작은 vocab size)이다.

• Decoding Strategy는 Meena의 Sample-and-rank straegy를 따른다. (using top-k (k=40) sampling (no temperature))

  Sample-and Rank는 temperature T로 둔 plain random sampling를 바탕으로 N개의 독립된 candidate responses를 생성한 후 높은 확률값을 가진 답변을 채택하는 decoding straetegy (beam 사용 X, temperature로 spike 조정)

4. Metric

저자들은 위의 기법으로 pre-training한 모델을 가지고 worker들과 대화를 한 다음 해당 대화를 평하기 위한 metric들을 해당 section에서 자세하게 다룬다.

4.1 Foundation metrics: Quality, Safety and Groundedness

Sensibleness, Specificity, Interestingness (모두 binary로 labeling)

• Sensible: measures whether a model’s responses make sense in context and do not contradict anything that was said earlier.

• Specificity: used to measure whether a response is specific to a given context.

• Interestingness: label a response as interesting if they judge that it is likely to “catch someone’s attention” or “arouse their curiosity”, or if it is unexpected, witty, or insightful.

Sensible를 X로 labeling하면 Specificity과 Interestingness 모두 labeling하지 않음. Specificity X로 labeling하면 Interestingness labeling하지 않음.

• Safety: Google's aI Principles에 따라 Labeling

• Groundedness: claims about the external world that can be supported by authoritative external sources (e.g., 'Rafael Nadal is the winner of Roland Garros 2020.')

• Informativenss: responses that carry information about the external world that can be supported by known sources as a share of all responses (e.g., 'That’s a great idea.')

4.2 Role-specific metrics: Helpfulness and Role consistency

application-specific한 role(e.g., teaching information about the animal)을 평가하기 위해 Helpfulness와 Role Consisteny라는 Metric을 제시하였다.

뒤에서 저자들이 few-shot prompt의 형태로 LaMDA가 특정 Role을 수행할 수 있는지에 대한 실험을 하는데 (dialog도 할 수 있고, 새로운 주제에 대해서도 어느정도 말하는 in-context learning 능력이 학습되었는지를 test) 해당 task를 평가하기 위해 지표를 제시한 것이다.

• Helpfulness: 특정 role이 부여되었을 때 그 role에 대응되는 correct한 information을 주는가?
• Role Consistency: The model’s responses are marked role consistent if they look like something an agent performing the target role would say. (multi-turn에 걸쳐서 Persona의 일관성 X을 유지한게 아니라, 해당 turn에서 특정 역할을 잘 수행했는지를 평가하는 metric이다. ex. 음악을 추천해주는 선생이면, (t-1), (t) turn 각각에서 그 역할을 잘 수행했는가?)

5. LaMDA fine-tuning and evaluation data

Quality (Sensibleness, Specificity, Interestingness), Safety, Groundedness 모두 pre-trained된 LaMDA와 crowdworker와 대화를 직접한 다음에 human evaluation/labeling을 해서 데이터셋을 직접 구축하였다.

6. LaMDA fine-tuning

LaMDA의 fine-tuning step은 크게 2가지로 나누어져 있다.

6.1 Discriminative and generative fine-tuning for Quality (SSI) and Safety

• context가 주어지면 LaMDA가 Response를 생성한다.

'<context> <sentinel> <response>' (loss는 response에만 흐름)

• “What’s up? RESPONSE not much.”

• 위에서 구축한 Metric과 Fine-tuning dataset을 기반으로 LaMDA가 생성한 답변이 적절한 지를 평가한다.

'<context> <sentinel> <response> <attribute-name> <rating>' (loss는 attribute name에만 흐름)

• “What’s up? RESPONSE not much. SENSIBLE 1” • “What’s up? RESPONSE not much. INTERESTING 0” • “What’s up? RESPONSE not much. UNSAFE 0”

이렇게 fine-tune된 LaMDA로 candidate response를 생성한 후 safety threhold 넘지 못하는 답변들은 필터링하였다. Ranking시에는 Sensible에 높은 가중치를 부여하고 높은 확률값 (i.e., 3 * P(sensible) + P(specific) + P(interesting))을 가진 답변이 next response로 선정되었다.

6.2 Fine-tuning to learn to call an external information retrieval system

External Knowledge를 활용하기 위해 (IR, calculator, translator가 가능한) Toolset이라는 것을 활용하였다.

Toolset은 string input을 받으면 list of strings을 output으로 return하는 system이다. (e.g., IR의 경우 input으로 “How old is Rafael Nadal?”을 받으면 [“Rafael Nadal / Age / 35”/]를 return 한다.)

Fine-tuning 순서는

(1) base model이 multiturn dialog context를 받아서 Toolset에 보낼 response를 학습하는 과정이다. (e.g., context + base > “How old is Rafael Nadal?”이라는 답변을 생성하면 TS, Rafael Nadal’s age이라는 query를 생성해 Toolset에서 snippet을 가져오는 과정이다. TS는 query에 접근하고 User는 response가 User에게 답변이라는 것을 의미한다.)

(2) Toolset에서 query에 대한 knowledge를 꺼내오면, research model이 이를 기반으로 user에게 보다 근거 있는 대답을 하는 과정이다. 또는 research model이 또 다른 query를 만들어 지속적으로 search를 할 수도 있다. (e.g., context + base + query + snippet > “User, He is 35 years old right now”. & context + base + query + snippet > “TS, Rafael Nadal’s favorite song”)

model이 생성한 output 값에 따라 'TS'를 생성할지 말지를 결정하지만 inference 시에는 loop에 maximum 제한 수를 두었다고 한다.

7. Results on foundation metrics

• Fine-tuning은 Scaling Law의 이익을 극대화시킬 수 있다.
• Fine-tuning은 Safety 측면에서 Scaling Law가 해결할 수 없는 부분을 해결할 수 있다.
• Groundedness의 경우 fine-tuning시 모델이 가중치에 모든 지식을 담을 필요가 없기 때문에 load가 줄어들어 (당연히) scale up함에 따라 성능이 향상되었다.
• Safety, Groundedness, Informativeness는 Human에 비해서 여전히 개선의 여지가 많이 남아 있다.

8. Domain grounding

LaMDA에게 role prompt를 주었을 때 그 역할을 충분히 수행할 수 있는지에 대한 실험을 했다.

위에 Table에서 보는 것처럼 2개의 Role을 수행할 수 있는지에 대한 실험을 했다. 아래 Figure에서 이탈릭체가 prompt라고 보면 된다.

실험결과는 아래 Table과 같다. Role Consistency(Prompt 해석능력 = in-context learning)은 LaMDA와 PT 사이에 큰 차이를 보이지 않는다. (in-context learnining은 pre-training 과정에서 학습한다.) 반면 Helpfulness는 큰 차이를 보인다. 저자들은 PT 자체가 Quality, Safety, Groundedness가 떨어져서 Helpfulness에서 큰 차이가 벌어졌다고 주장하고 있다.

LM의 output에 대한 'uncertainty'를 정확히 측정할 수 없다면 (application 상황에서) 우리는 해당 output에 대한 일관성에 의구심을 가질 수 밖에 없다.

하지만 자연어 생성 task는 '비정형 데이터'를 생성하고 평가하는 문제이기 때문에 (논문에서는 free-form NLG라고 명명함) 'uncertainty'를 명확히 측정하는 것은 굉장히 제한적이다.

그리고 우리가 언어라는 것을 바라볼 때는 기본적으로 '의미(semantic)'과 '형태(lexical)'을 동시에 고려하지만, 현재의 LM들의 token-likelihood 기반의 학습 방법들은 lexical confidence만을 강화하는 방법들로 학습이 되어왔다. 그렇지만, 정작 application 단으로 넘어가면 LM이 생성된 문장들의 의미가 중요해진다. (저자들이 아래에 가져온 예시들을 살펴보자)

LM이'France’s capital is Paris'을 생성할지 아니면 'Paris is France’s capital'을 생성할지 'uncertainty'해도 실제 두 문장이 의미하는 바가 같기 때문에 같은 대답이라고 해야한다. 하지만 현재의 LM들은 token 단위로 학습되기 때문에 (같은 의미를 같는) 위의 2개의 대답에 대한 불확실성을 굉장히 높게 평가한다. (의미론적으로 보면 분포상 한점에 높은 밀도 안에 모여 있어야하는 대답들임에도 불구하고)

이러한 semantic equivalence을 설명하기 위해 저자들은 semantic likelihood를 측정하는 기법을 제시한다. 저자들이 제시하는 알고리즘은 간단하다. 한 문장으로 다른 문장의 의미를 추론할 수 있다면 두 문장은 같은 의미를 같다고 가정할 수 있고, 이 가정을 바탕으로 여러 군집들은 만든다. 만들어진 군집들은 확률의 개념을 도입해 엔트로피를 측정해 LM의 ouput의 semantic uncertainty를 측정하는데 활용된다.

2. Background on Uncertainty Estimation

예측의 불확실성은 output distribution의 예측가능한 entropy로 측정할 수 있으며, 데이터 point x에 대한 y의 조건부 entropy는 다음과 같이 정의될 수 있다.

일반적으로 Entropy는 누락된 데이터 분포에 내제된 노이즈로부터 파생된 'aleatoric uncertainty'와 모델이 데이터를 충분히 학습하지 못해 파라미터에 내제된 'epistemic uncertainty'로 구분된다. LM이 생성하는 output은 'epistemic uncertainty'로 구분지을 있기에 본논문에서는 'epistemic uncertainty'에 집중한다.

'epistemic uncertainty'은 일반적으로 'mutual information'으로 측정되는데, NLP 분야에서는 이를 위해서는 여러 LM들의 output들을 ensemble해 위의 수식을 적분해야하기 때문에 비효율적이라는 문제가 있다고 한다.

또한 introduction에서 지적한바와 같이 product of the conditional probabilities of new tokens given past tokens로 output sequence의 likelihood를 구하는 것은 output의 semantic을 제대로 구하는데 한계가 존재한다.

3. CHALLENGES IN UNCERTAINTY ESTIMATION FOR NLG

NLP가 다른 분야와 달리 불확실성을 측정하기 어려운 이유는 output들이 완전히 상호 베타적이지 않기 때문이다. 위의 예시를 가지고 오면 'France’s capital is Paris'와 'Paris is France’s capital'는 lexical & syntax 측면에서 완전히 다른 output이지만 semantic 측면에서 완전히 동일한 output이기에 완전히 상호 베타적으로 분류할 수 없다.

따라서 본 논문에서는 'semantic equivalence', 의미적으로 동일한 output을 estimation 해내는 방법론을 제시한다.

$N$개의 token들로 이루어진 각각의 sequence가 하나의 의미를 가지고 있다고 할 때, sequence equivalence relation을 정의하기 위해 저자들은 $E(\cdot,\cdot)$라는 placeholder를 정의한다. 이 placeholder는 reflexive(for all x, x=x), symmetric (for all real numbers x and y ,if x=y, then y=x), transitive (for all real numbers x,y, and z, if x=y and y=z, then x=z)하다. Sequence equivalence relation은 semantic equivalence class를 정의하기 위해 활용되며 하나의 semantic equivalence class는 1개의 의미만을 가질 수 있다.

일반적으로 LM의 conditional output은 $p(s|x)$로 정의하지만, semantic equivalence class에 대한 확률을 정의하기 위해 논문에서는 LM이 equivalence class로 생성한 output distribution에 대해서 전부 다 더해 아래와 같은 수식을 제안한다.

4. SEMANTIC UNCERTAINTY

저자들이 제시하는 meaning space에서 uncertainty를 측정하는 방법은 크게 3가지 단계로 나누어진다.

Step 01. Generating s set of answers from the model

1개의 LM에 대해서 $M$개의 sequence ${{s^1,s^2,...,s^M}}$들을 생성하였다. (데이터셋은 Q&A 데이터셋을 활용했는데, 하나의 question에 대해서 한 모델이 multinomial sampling & multinomial beam sampling을 통해 $M$개의 answer pair를 만들었다고 보면 된다)

선행연구와는 달리 ensemble models들을 쓰지 않아 independent foundation models training cost가 없다는 장점을 지속적으로 어필하고 있음

Step 02. Clustering by semantic equivalence

위의 section 03에서 정의한 equivalence relation $E(\cdot,\cdot)$와 MNLI dataset으로 finetuning한 Deberta-large model을 활용해 생성한 $M$개의 sequence ${{s^1,s^2,...,s^M}}$들을 clustering한다.

방법은 아래 알고리즘에 나와있는데로 서로 다른 sequence들을 context들과 함께 concat해 bidirectional한 방향으로 2번 inference해서 모두 entailment가 나오면 하나의 cluster로 분류하고 아니면 다른 cluster로 분류하는 식이다.

Step 03. Computing the semantic entropy

Step 02에서 sequence별로 cluster가 구해졌다면 동일한 cluster에 속한 generated sequence들 별로 likelihood들을 더한 후 semantic entropy를 계산하였다.

저자들은 모든 가능한 meaning class $c$를 활용하지 않고 Monte Carlo integration을 활용해 몇개만을 sampling해서 활용했다고 한다.

저자들이 아래 첨부한 Table을 보면 LM이 유사한 대답을 하는 상황에서 Semantic Likelihood는 vanilla Likelihood에 비해 LM의 대답이 상대적으로 덜 uncertainty하다는 것을 잡아내고 있음.

5. Empirical Evaluation

MODEL: OPT (2.7B, 6.7B, 13B and 30B parameters) DATASET: CoQA & TriviaQA *$ROUGE-L(S,S')>0.3 9)$ (Appendix에서 Robustness 검증함) * (reference 문장이랑 모델이 생성한 문장이랑 rouge-lcs가 0.3이상이면 postive라고 분류했다고 보는듯) *METRIC: AUROC *

(논문에 앞에까지 계속 Semantic Entropy로 Estimation한다고 이야기하다가 갑자기 AUROC 계산 한다는 이야기가 나와서.. 이부분은 여전히 이해가 가지를 않습니다...)

• Fig. 1a) we show that semantic entropy has a significantly higher AUROC than entropy in sequence-probability- space with and without length-normalisation, as well as the lexical similarity baseline. At the same time, it performs dramatically better than p(True).
• Fig. 1b) that our method out- performs more for larger model sizes and continues to steadily improve as the model size increases.

또한 incorrect하게 답할수록 더 많은 semantically distinct한 cluster를 하는 것도 보였습니다. (LM이 생성하는 대답이 uncertainty하다 > (한질문에 대해서) semantically하게 퍼져있는 대답을 생성한다)

본 벨로그의 내용 및 이미지는 다음의 강의를 참고해서 작성이 되었으며, 틀린 내용이 있을 수도 있으니 너그럽게 봐주시면 감사하겠습니다:)

• 널널한 개발자 TV님의 운영체제 강의 가상 메모리 개요
• 널널한 개발자 TV님의 운영체제 강의 가상 메모리 페이징 기법의 구현
• 널널한 개발자 TV님의 운영체제 강의 가상 메모리 접근 권한
• 한빛 아카데미 '쉽게 배우는 운영체제'

가상메모리 개요

가상 메모리 시스템의 모든 프로세스는 물리 메모리와 별개로 자신이 메모리의 어느 위치에 있는지 상관없이 0번지부터 시작하는 연속된 메모리 공간을 가진다. 그리고 각 프로세스가 가진 가상 메모리 공간 (Virtual Memory Space)의 크기는 컴퓨터 시스템이 가진 물리 메모리의 최대 크기로 한정된다. 32bit 체계의 경우 최대로 표현할 수 있는 주소가 약 4GB이기 때문에 각 프로세스가 할당할 수 있는 가상 메모리의 최대 크기 역시 약 4GB이다.

그렇다면 32bit 시스템에서 10개의 프로세스가 있다면 최소 40GB의 물리적 메모리가 필요하다는 이야기 인데, 실제로 40GB가 다 필요한 경우가 많지는 않다. 하지만 운영체제의 메모리 관리자는 RAM과 스왑영역을 활용해 실제 프로세스가 동작하기 위한 물리적 메모리 공간을 확보해놓는다.

이전에 프로세스마다 가상 메모리 공간이 할당된다고 했는데, 이 말은 프로세스마다 0번지, 1번지라는 메모리 주소가 할당된다는 의미이다. 하지만 이 말이 각각 프로세스 1번과 프로세스 2번의 가상 메모리 주소 0번지가 참조하는 주소가 둘다 실제 물리 메모리 주소의 0번지의 주소가 아니라는 뜻이다. (프로세스마다 메모리 공간이 가상화/추상화 되어있다는 의미) 따라서 가상 메모리 시스템에서 메모리 관리자는 RAM과 스왑 영역을 합쳐서 실제 메모리의 물리 주소로 변환하는 작업을 수행해주어야 하는데 이러한 작업을 동적 주소 변환 (Dynamic Addresss Translation) 이라고 하며, 매핑 테이블을 통해 각 프로세스의 가상 메모리 공간이 물리 메모리의 세그먼트/페이지로 매핑이 된다.

이렇게 메모리를 가상화 되어서 관리했을때 가장 큰 장점은 관리적 용이성이 매우 좋아진다는 것이다. 예를 들어, 프로세스가 죽었을때 매핑 테이블을 참조해서 메모리를 회수하면 보다 다른 프로세스가 해당 메모리를 활용할 수 있게 되고 보다 자원을 효율적으로 사용할 수 있게 된다.

페이징 기법

가상 메모리 공간 역시 물리적 메모리 공간과 마찬가지로 고정 분할 방식인 페이징 기법과 가변 분할 방식인 세그멘테이션 기법으로 구분지어서 관리된다. 두 관리 기법이 갖는 단점을 보완하기 위해 가상 메모리 시스템 역시 세그멘테이션-페이징 혼용 기법을 사용해 관리된다. 강의에서 페이징 기법을 위주로 다루었음으로 포스팅에서도 페이징 기법 중심으로 정리하였다.

위의 그림에서처럼 가상 메모리 공간을 고정된 크기로 나누어서 관리했을때 각각의 고정된 크기를 '페이지' 라고 하며, 각 페이지에 상응되는 물리적 메모리 공간의 고정된 공간을 '프레임' 이라고 부른다고 한다. 일반적으로 관리의 편리성을 위해 페이지와 프레임의 크기는 똑같이 맞춰준다고 하며 강의에 따르면 위도우의 경우 4KB로 페이지를 분할해 관리한다고 한다. 그림에서 invalid라고 표시되어 있는 부분은 해당 페이지가 스왑 영역에 있다는 의미라고 책에서는 서술되어 있다. (강의에서는 실제 물리적 메모리 공간에 메핑된 곳이 없는 경우 invalid가 나오고 오류 메세지가 뜬다고 설명하고 있다.)

페이징 기법에서의 주소 변환 작업을 살펴보면 다음과 같다.

위의 그림처럼 한 페이지/프레임의 크기를 10B로 나누었고, 각 페이지/프레임이 10개의 주소를 가진다고 하자. 프로세스가 30번지의 내용을 읽으려고 할 때의 주소 변환 과정은 아래와 같다.

1. 가상 주소 30번지가 어느 페이지에 있는지 찾는다. 30번지는 페이지 3의 0번째 위치에 있다.
2. 페이지 테이블의 페이지 3으로 가서 해당 페이지가 프레임 1에 있다는 것을 알아챈다.
3. 최종적으로 물리 메로리 프레임 1의 0번째 위치에 접근한다. 이 주소가 가상 메모리 30번지의 물리 주소이다.

이러한 주소 변환 과정을 정형화해보면, 페이징 기법에서는 가상 주소를 VA=<P,A>로 표현하는데, 여기서 VA는 가상 주소, P는 페이지, D는 페이지의 처음 위치에서 해당 주소까지의 거리를 의미하며 offset이라고 정의되기도 한다. 위의 그림을 보면 가상 메모리의 페이지 VA=<P,A>가 물리 메모리의 프레임 PA=<F,D>로 메핑이 되는데, 페이지와 프레임의 크기를 똑같이 나누었을 경우 특정 주소까지의 거리가 변하지 않기 때문에 D는 변하지 않는 것을 확인할 수 있다.

메모리 접근 권한

메모리 접근 권한은 메모리의 특정 번지에 지정된 데이터를 사용할 수 있는 권한으로 읽기(read), 쓰기(write), 실행(execute) 권한이 있다. 일반적인 데이터에는 읽기 및 쓰기 권한이 적용되고, 상수나 읽기 전용 파일에는 읽기 권한이 적용된다.

위의 그림은 프로세스의 영역별 메모리 접근 권한을 나타낸 것이다. 프로세스는 몸체에 해당하는 코드 영역, 프로세스가 사용하는 데이터를 저장하는 데이터 영역, 프로세스를 실행하는데 필요하는 스택 영역과 프로세스 제어 영역으로 구성된다.

• 코드 영역: 자기 자신을 수정하는 프로그램은 없기 때문에 읽기 및 실행 권한을 가진다.
• 데이터 영역: 데이터는 크게 읽거나 쓸 수 있는 데이터와 읽기만 가능한 데이터로 나눌 수 있다. 일반적인 변수는 읽거나 쓸 수 있으므로 읽기 및 쓰기 권한을 가지고 상수로 선언한 변수는 읽기 권한만 가진다.

메모리 접근 권한 검사는 가상 주소에서 물리주소로 변환이 일어날 때마다 시행된다. 위의 그림처럼 매핑 테이블에서 각 프레임번호마다 권한 비트가 있어서 해당 프레임이 읽기가 가능한 영역인지 읽기/실행이 모두 가능한 영역인지를 메핑과정에서 검사하게 된다. 이렇듯 변환과정에서 유용한 접근인지 확인하기는 하지만 사용자가 직접 권한을 바꿀 수 있다고 한다. 이와 관련해서 강의에서 Data Execution Prevention 이라는 개념을 추가로 설명해주는데, 이는 데이터가 담기는 영역에서 코드가 실행되는 것을 운영체제가 선제적으로 막는 개념이다. 동적할당된 메모리 영역에 특정 기계어가 실행되버리면 보안문제 같은 이슈가 발생하기 때문이다.

위의 그림에서 프레임마다 권한비트를 추가하면 페이지 테이블의 크기가 커지는 자원을 낭비하는 문제가 발생해 이를 해결하기 위해 세그멘테이션 테이블을 추가해 테이블의 크기를 줄이는 기법이 도입되었다고 한다.

본 벨로그의 내용 및 이미지는 다음의 강의를 참고해서 작성이 되었으며, 틀린 내용이 있을 수도 있으니 너그럽게 봐주시면 감사하겠습니다:)

• 널널한 개발자 TV님의 운영체제 강의 메모리 관리 개요
• 널널한 개발자 TV님의 운영체제 강의 절대주소와 상대주소
• 널널한 개발자 TV님의 운영체제 강의 메모리 오버레이와 스왑
• 널널한 개발자 TV님의 운영체제 강의 (물리)메모리 분할 방식
• 한빛 아카데미 '쉽게 배우는 운영체제'

32 bit 와 64 bit의 차이

비트(bit)는 한번에 다룰 수 있는 데이터의 최대 크기를 의미한다. 32bit CPU가 있다고 하면 당연하게도 이 CPU내부의 레지스터, 각종 버스의 크기의 대역폭도 32 bit이다. 이 32bit CPU의 경우 메모리 주소를 지정하는 레지스터인 MAR의 크기가 32bit이므로 표현할 수 있는 메모리 주소의 범위가 02^32-1 총 2^32이며 이를 16진수로 나타내면 00000000FFFFFFFF이며 총크기는 4GB이다. 따라서 32bit CPU 컴퓨터는 메모리를 최대 4GB까지 사용할 수 있다. 64bit CPU까지 확장하여서 비교해해보면 다음과 같다.

메모리 관리의 복잡성

컴퓨터는 메모리 공간을 관리할때 (위의 그림에서의 정사각형 한칸) 1byte 단위로 관리한다. CPU는 메모리에 있는 내용을 가져오거나 작업 결과를 메모리에 저장하기 위해 메모리 주소 레지스터(MAR)를 사용한다.

메모리 관리의 이중성

메모리 관리의 이중성이란 프로세스 입장에서는 메모리를 독차지하려 하고, 메모리 관리자 입장에서는 되도록 관리를 효율적으로 하고 싶어하는 것을 말한다. 메모리 관리 시스템은 이러한 메모리 관리의 이중성을 완만하게 해결학 위해 노력한다.

계층적 메모리 구조를 만든 이유 : 충분히 크지 않은 메모리에서 여러 작업을 동시에 실행해야 하는데, 작업 속도 역시 CPU에 필적해야 작업 효율이 떨어지지 않게 되므로 메모리를 계층적 구조로 만들어 작업 속도를 올리고 가격을 낮추어 계층적 메모리 구조로 만들었다.

메모리 관리자의 역할

메모리는 메모리 관리자에 의해 관뢰되며 크게 가져오기 (fetch), 배치 (replacment), 재배치 (replacement)의 작업을 한다.

• 가져오기 (fetch): 프로세스와 데이터를 메모리로 가져오는 작업이다. 가져와야하는 데이터의 용량이 메모리의 크기를 넘어가는 경우에는 필요할때마다 수시로 가져오기도 한다. 필요하다고 예상되는 데이터를 미리 가져오는 방법도 있다.
• 배치 (replacement): 가져온 프로세스를 메모리의 어떤 위치에 올려놓을지 결정하는 정책이다. 메모리를 같은 크기로 자르는 것을 페이징(paging) 이라고 하며, 프로세스를 크기에 맞게 자르는 것을 세그멘테이션(segmentation) 이라고 한다. 둘다 한정된 메모리를 효율적으로 사용하기 위해 고안된 정책이다.
• 재배치 (replacement): 새로운 프로세스르 가져와야 하는데 메모리가 꽉 찼다면 메모리에 있는 프로세스를 하드디스크로 옮겨놓아야 새로운 프로세스를 메모르에 가져올 수 있다. 이때 어떤 프로세스를 내보낼지 결정하는 알고리즘을 교체 알고리즘이라고 한다.

절대주소와 상대주소

기본적으로 사용자 프로세스는 운영체제 영역을 피하여 메모리에 적재된다. 따라서 보다 실제 물리적인 프로세스의 위치가 주소가 아닌 상대적인 주소로 프로세스를 관리하기 시작하기 위해 상대주소라는 개념이 도입되었다. 위의 그림 7-12에서 360번지가 0번지로, 400번지가 40번지로 바뀌는데, 360번지와 400번지는 절대 주소 (MAR이 사용하는 주소로 실제 컴퓨터에 꽃힌 램 메모리의 주소)이고 0번지와 40번지는 상대 주소이다. 상대 주소는 논리 주소라고도 불리며, 가상 메모리와 관련이 있다고 한다.

메모리 오버레이

프로그램의 크기가 실제 메모리보다 클 때, 프로그램을 몇 개의 모듈로 나누고 필요할 때마다 모듈을 메모리에 가져와 사용하는 것을 메모리 오버레이라고 한다. 위의 그림 예시에서 처럼 아래 한글을 실행하면 모든 모듈들을 전부 램에다 올리고 실행하는 것이 아니라 맞춤법 검사나 그림판과 같은 모듈들을 필요할때마다 램에다 올려놓고 실행하는 방식이 메모리 오버레이 기법이다.

스왑

메모리 오버레이를 위해 프로세스를 모듈로 나누어서 메모리에 가져와서 실행을 했다. 그렇다면 나누어진 각 모듈들은 어디서 가져와서 실행할까? 바로 2차 메모리 공간인 SSD이다. 하지만 이 모듈들은 언제 다시 메모리록 가져올 지 모르기 때문에 메모리 관리자에 의해 스왑 영역이라는 공간에 특별 보관된다. 그리고 스왑 영역에서 메모리로 데이터를 가져오는 작업을 스왑 인, 메모리에서 스왑 영역으로 데이터를 내보내는 작업을 스왑 아웃이라고 한다. 스왑 인 & 아웃은 페이지 인 & 아웃 이라고 불리기도 한다.

메모리 분할 방식

메모리에 여러 개의 프로세스를 배치하는 방법은 크게 가변 분할 방식과 고정 분할 방식으로 나뉜다.

• 가변 분할 방식: 프로세스의 크기에 맞게 메모리를 분할하는 방식이다. 메모리 관리 측면에서 복잡하다는 단점이 있다. 예를 들어 위의 그림의 오른쪽 그림 처럼 18KB의 프로세스와 17KB의 프로세스가 종료된 후 25KB의 프로세스가 들어오면 적당한 공간이 없어서 배정하지 못하게 되는 문제가 생긴다. 이러한 문제를 외부 단편화 문제라고 하며, 이를 해결하기 위해서는 실행중인 프로세스들을 다른 메모리 공간으로 복사하고, 빈 공간들을 모으는 조각모음을 수행해야하기 때문에 자원이 소모된다는 한계가 존재한다.
• 고정 분할 방식: 프로세스의 크기에 상관없이 메모리를 같은 크기로 나누고, 큰 프로세스가 메모리에 올라오면 여러 조각으로 나누어 배치하는 방식이다. 관리적인 측면에서 가변 분할 방식보다는 유리하다는 장점이 있으나 위의 그림처럼 20KB로 메모리 공간을 나눈다고 했을 때, 18KB와 같은 프로세스가 올라오면 2KB와 같은 공간이 남는 내부 단편화 문제가 발생한다는 한계가 존재한다.

따라서 현대 운영체제는 기본적으로 고정 분할 방식을 사용하면서 일부분은 가변 분할 방식을 혼합한다고 한다.

본 벨로그의 내용 및 이미지는 다음의 강의를 참고해서 작성이 되었으며, 틀린 내용이 있을 수도 있으니 너그럽게 봐주시면 감사하겠습니다:)

• 널널한 개발자 TV님의 운영체제 강의 프로세스간 통신 개요
• 널널한 개발자 TV님의 운영체제 강의 공유 자원과 임계 구역
• 널널한 개발자 TV님의 운영체제 강의 임계구역 해결방법 결론은 하나 'Queue'!
• 널널한 개발자 TV님의 운영체제 강의 대충 넘어가는 교착상태(Dead lock)
• 한빛 아카데미 '쉽게 배우는 운영체제'

프로세스 간 통신의 개념

OS는 프로세스가 독립적인 공간에서 작동되도록 하는 것을 보장하며 외부로 부터의 접근을 차단한다. 하지만 한 프로세스가 다른 프로세스와 데이터를 주고 받으면서 통신해야할 때도 있는데 프로세스 간 통신의 종류는 크게 3가지로 구분지을 수 있다.

1. 프로세스 내부 데이터 통신 : 하나의 프로세스 내에 2개 이상의 스레드가 존재하는 경우의 통신. 프로세스 내부의 스레드는 '전역 변수나 파일' 을 이용하여 데이터를 주고 받는다.
2. 프로세스 간 데이터 통신 : 같은 컴퓨터에 있는 여러 프로세스끼리 통신하는 경우로, 공용 파일 또는 운영체제가 제공하는 '파이프' 를 사용하여 통신한다.
3. 네트워크를 이용한 데이터 통신 : 여러 컴퓨터가 네트워크로 연결되어 있을 때도 통신이 가능한데, 이 경우 프로세스는 소켓을 이용하여 데이터를 주고받는다. 이처럼 '소켓' 을 이용하는 프로세스 간 통신을 네트워킹이라고 한다.

프로세스 간 통신 방식은 데이터를 주거나 (send) 받는 (receive) 행위로 크게 나누어질 수 있다. 하지만, 통신하려는 프로세스는 어떻게 찾을지, 데이터의 크기는 얼마로 할지, 데이터의 도착 여부는 어떻게 확인할지 (동기화)등 많은 문제를 정의해야 원활한 통신이 가능해진다.

동기화(synchronization) 수신하는 프로세스에 데이터가 도착했음을 알려주는 기능이다. 동기화 기능이 없으면 데이터를 받는 프로세스는 바쁜 대기를 사용하여 데이터가 도착했는지 여부를 직접 확인해야 한다.

전역 변수, 파일, 파이프, 소켓을 이용한 프로세스 간 통신은 다음과 같이 구분지을 수 있다.

• 전역 변수를 이용한 통신

int GV

int main()
{ int pid;

  pid=fork();
 ...

전역 변수를 이용한 통신은 공동으로 관리하는 메모리를 사용하여 데이터를 주고받는다. 데이터를 보내는 쪽에서 전역변수나 파일에 값을 쓰고, 데이터를 받는 쪽에서는 전역 변수의 값을 읽는다. 위의 코드를 보면 main() 이전에 정의된 전역 변수 GV는 부모 프로세스와 자식 프로세스가 공유하는 메모리 영역으로, GV에 데이터를 쓰거나 읽는 방법으로 두 프로세스가 통신한다.

전역 변수를 2개 만들면 프로세스는 양방향으로 데이터를 보낼 수 있게 된다. (A 변수는 > 방향 & B 변수는 < 방향)

• 파일을 이용한 통신

2차 메모리인 파일을 이용해 데이터를 주고받는 통신이다.

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int main()
{ int fd;
  char buf[5];

  fd = open("com.txt", O_RDWR);

  write(fd, "Test", 5);

  read(fd, buf, 5);

  close(fd);

  exit(0);
}

위의 코드는 open 함수를 이용하여 어떤 파일에 접근할 수 있는 권한인 file descriptor를 변수fd에 할당함으로써 2차 저장장치인 파일 시스템과 통신한다. 프로세스가 입출력 관리 프로세스에 쓰기를 요구하면 데이터가 저장되고, 읽기를 요구하면 입출력 관리 프로세스로부터 데이터를 가져온다. 쓰기 연산은 하드디스크에 데이터를 전송하는 명령, 읽기 연산은 데이터를 가져오는 명령이라고 볼 수 있다.

• 파이프를 이용한 통신

OS가 제공하는 동기화 통신 방식으로, 파일 입출력과 같이 open() 함수로 기술자를 얻고 작업을 한후 close() 함수로 마무리한다. 데이터를 보내는 프로세스가 쓰기 연산을 완료하면 받는 프로세스의 대기 상태가 자동으로 풀리기 때문에 동기화 문제로부터 자유롭다는 장점이 있다.

• 소켓을 이용한 통신

여러 컴퓨터에 있는 프로세스 간 통신을 네트워킹이라고 하는데, 이때 이용하는 것이 소켓이다. 소켓은 프로세스 동기화를 지원하기 때문에 데이터를 받는 프로세스가 바쁜 대기를 하지 않아도 되며, 양방향 통신을 위해 전역변수나 파이프처럼 2개의 객체가 필요하지 않다.

공유자원

공유자원은 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일, 등을 말한다. 공유 자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.

2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 '경쟁 조건 (race condition)'이라고 한다. 경쟁 조건이 발생하면, 공유 자원 접근 순서에 따라 실행 결과가 달라 질 수 있다.

임계구역

공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 임계구역이라고 한다.

위와 같이 서로 독립적인 producer()와 consumer()가 sum이라는 전역변수에 동시에 접근하는 코드가 있다고 할 때, sum을 읽어오고 덮어쓰는 부분이 임계구역이다.

sum=3 인 상황에서 (1) sum = sum + 1 과 (2) sum = sum - 1 이 미세한 시간 차이로 인해 온전히 실행되지 않아 원자성을 보장 받지 않을 경우 sum = 2 or 4인 결과가 도출될 수 있다. 따라서 이러한 문제를 해결하기 위해서는 프로세스들이 임계구역에서 동시에 작업을 하지 못하도록 해야 한다.

임계구역 해결 방법

임계구역 문제를 해결하기 위해서는 다음의 3가지 조건을 만족해야 한다.

1. 상호 배제 : 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.
2. 한정 대기 : 특정 프로세스는 무한 대기 상태에 빠질 수 없다.
3. 진행의 융통성 : 한 프로세스의 작업이 다른 프로세스의 작업을 방해하면 안된다.

임계구역을 해결하는 방법은 기본적으로 임계구역을 최소화하는 것이다. 하지만 강의에 따르면 임계구역을 최소화하는 것은 상황 by 상황에 따라 다른 접근법을 사용해야 된다고 한다.

하지만 나는 OS 잘 모르기 때문에 .. ㅎㅎ

임계구역 문제를 해결하는 단순한 방법인 lock이 있는데 이 방법과 이 방법이 갖는 한계를 하나씩 써내려가면서 나의 이해도를 재고해보도록 하겠다.

1. 1개의 공유 변수를 통해 잠금을 구현하는 방법

위의 코드 동작 원리는 간단하다. 프로세스 P1는 lock==true이면 임계구역에 진입하지 못한다 (다른 프로세스가 임계구역을 점유하고 있으면). 만약 lock==false이면 프로세스 P1은 임계구역에 대한 lock을 걸고 작업을 처리한다. 해당 방식은 상호 배제의 원칙을 완전히 만족시켜주는 것처럼 보이지만, 실제로는 그렇지 않다. 만약 lock==false인 상황에서 프로세스 P1인 상태에서 while(lock==true);까지만 실행되고 context switching이 일어나 프로세스 P2가 실행 될 경우 P1, P2가 모두 임계구역에 들어갈 수 있기 때문이다. 또한 while(lock==true);는 작업을 할 필요가 없을 때도 계속 무한 루프를 돌면서 시스템 자원을 낭비한다는 단점이 존재한다.

2. 2개의 공유 변수를 통해 잠금을 구현하는 방법

상호 배제의 원칙을 만족시키기 위해 2개의 공유변수를 도입하는 방식이 있다. 위의 그림처럼 2개의 공유 변수를 도입하면 같은 맥락에서의 상호 배제의 원칙을 만족시킬 수 있다. 하지만, lock1==true;나 lock2==true;가 실행된 이후 context switching이 일어날 경우 P1과 P2 모두 양쪽 lock을 걸어 놓았기 때문에 임계구역으로 진입할 수 없는 무한정 대기 상태인 deadlock 상태에 빠지게 된다는 한계가 존재한다.

3. 정수형 공유 변수를 통해 잠금을 구현하는 방법

상호 배제 및 한정 대기의 원칙을 모두 만족시키는 lock 방법은 공유변수를 정수형 변수로 선언하는 것이다. 하지만 이 방법의 문제는 한 프로세스가 연달아 임계구역에 진입할 수 없다는 한계가 존재한다 (P1 > P2). 즉 한 프로세스의 진행이 다른 프로세스로 인해 방해 받는 현상이 발생하며, 이를 '경직된 동기화'리고 한다.

4. 하드웨어적인 해결방법

하드웨어적인 해결방법은 그림에서 보이는 것처럼 while(lock=true);문과 lock=true;문을 하드워에적으로 동시에 실행해 그 사이에 context switching이 발생하는 것을 방지하는 것이다. 하지만 이 역시 시스템 자원을 낭비한다는 문제를 근본적으로 해결하지는 못한다 (while문 사용).

5. 세마포어

세마포어는 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠때까지 기다리다가 이후에 작업을 마치면 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 이때 대기하는 프로세스는 '큐' 에서 자기 순서를 기다리고 있기 때문에 직접 임계구역이 잠겼는지 점검하면서 바쁜대기를 할 필요가 없다.

위의 코드에 나오는 용어들을 정리해보면

• Semaphore(n): 전역 변수를 n으로 초기화한다. RS에는 현재 사용 가능한 자원의 수가 저장된다. 프린터가 2개라면 n=2이다.
• P(): 잠금을 수행하는 코드로, RS가 0보다 크면 1만큼 감소시키고 임계구역에 진입한다. 만약 RS가 0보다 작으면 0보다 커질 때까지 기다린다.
• V(): 잠금 해제와 동기화를 같이 수행하는 코드로, RS 값을 1 증가시키고 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake_up 신호를 보낸다.

세마포어가 안정적으로 작동되도록 하기 위해서는 P()와 V()의 원자성을 보장해 상호 배제 조건을 만족할 수 있도록 해주어야 한다.

6. 모니터

세마포어 알고리즘이 안정적으로 작동하기 위해서는 매 임계구역마다 P()와 V()를 정확하게 지정해주어야 한다. 따라서 공유 자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P()와 V()를 사용할 필요 없이 자동으로 처리한 게 바로 '모니터'이다. 모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다.

책에서는 모니터를 시스템 호출과 같은 개념으로 설명하는데, 사용자 입장에서는 임계구역에서 작업할 수 있는 인터페이스만 제공받는 것이다. 따라서 P()나 V()를 사용하지 않고도 프로세스는 모니터 큐에 들어가서 자기 순서를 기다리다가 자기 순서가 되면 모니터에서 처리가 된 후 동기화 신호를 통해 끝났음을 모니터 큐에 알려준다.

monitor shared_balance {

 private:

  int balance=10;
  boolean busy=false;
  condition mon;

 public:
  increase(int amount){
  if(busy==true) mon.wait(); /* waiting in queue */
  busy=true;
  balance=balance+amount;
  mon.signal(); /* wake up next waiting process */

}

교착 상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태라고 한다. 컴퓨터 시스템에서 교착 상태는 시스템 자원 (다른 프로세스와 공유할 수 없는 자원(P1는 프린터를 할당받고 스피커를 기다림. P2는 스피터를 할당받고 프린터를 기다림)을 사용할 때), 공유 변수 (위의 예시에서 서로 다른 프로세스 P1 & P2가 lock1 & lock2를 걸고 무한 루프에 걸릴때), 응용 프로그램 (데이터베이스에서 일관성, 원자성을 위해서 lock을 사용할 때)등을 사용할 때 발생할 수 있다.

교착 상태를 보다 잘 설명해주는 용어는 자원 할당 그래프이다. 위 그림에서 원은 프로세스, 사각형은 자원이다. 실선은 프로세스가 자원을 할당받은 상태를 의미하며, 점선은 프로세스가 자원을 기다리는 것을 의미한다. 위처럼 각 프로세스가 할당받은 자원이 다른 프로세스 입장에서 할당 받기 위해 기다리는 자원이라면 교착 상태가 발생한다.

교착 상태가 발생하기 위해서는 다음의 4가지 조건을 모두 만족시켜야 한다.

• 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 베타적인 자원이어야 한다.
• 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
• 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
• 원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이우어야 한다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠진다.

본 벨로그의 내용 및 이미지는 다음의 강의를 참고해서 작성이 되었으며, 틀린 내용이 있을 수도 있으니 너그럽게 봐주시면 감사하겠습니다:)

• 널널한 개발자 TV님의 운영체제 강의 Chapter04 CPU 스케줄링 개요
• 한빛 아카데미 '쉽게 배우는 운영체제'

CPU 스케줄링

스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다.

스케줄링의 단계

스케줄링은 크게 CPU에게 얼만큼의 작업의 양(capacity)을 배정하고 배정된 작업의 순서(order)를 어떻게 할것인지로 구분지어 설명할 수 있다.

• 고수준 스케줄링 : 시스템 내의 전체 '작업 수'를 조절하는 행위이다. (작업이란 일반적으로 여러 개의 프로세스들의 집합이라고 보면 된다. jobs = {proc1, proc2, ... }) 작업 요청이 오면 승인 여부를 결정하는 일이며, 작업의 양을 조절한다고 보면 된다.
• 중간수준 스케줄링 : 고수준과 저수준 사이의 스케줄링으로, 고수준 스케줄링에 의해 어떤 프로세스가 활성화 되었다고 해도 시스템 상에 과부하가 걸릴 수 있기 때문에 도중에 일부 프로세스를 중지 상태로 옮겨서 다른 프로세스가 원활히 처리되게 하는 일이라고 보면 된다.
• 저수준 스케줄링 : 준비 상태 있는 프로세스 중 어떤 프로세스를 골라 실행하고, 어떤 프로세스를 대기 상태로 보낼지를 결정하는 일로, 순서를 결정하는 일이라고 보면 된다.

Preemptive vs Non-preemptive

스케줄링은 크게 선점형 스케줄링과 비선점형 스케릴링으로 나누어질 수 있다.

• 선점형 스케줄링 (preemptive scheduling) : '어떤 프로세스가 CPU를 받아 실핼 중이더라도' 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
• 비선점형 스케줄링 (Non-preemptive scheduling) : 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식.

선점형 스케줄링은 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다. 인터럽트 처리가 대표적인 선점형 스케줄링 방식이다.

선점형 스케줄링 방식에도 비선점형 프로세스가 존재할 수 있다. (백업) 하지만 비선점형 프로세스가 선점형 프로세스에 크게 영향을 주지 못하도록 해야하기 때문에 중요도를 낮게 설정해야 한다.

프로세스 우선순위

아까 프로세스의 중요도에 대해서 설명했는데, 이는 사실상 프로세스의 '우선순위'와 같은 말이다. CPU 스케줄러는 우선순위가 높은 프로세스부터 처리한다.

프로세스의 우선순위는 일반적으로 (1) 매우 높음 (2) 약간 높음 (3) 보통 (4) 약간 낮음 (5) 매우 낮음과 같이 구분된다. GUI와 같이 사용자와 직접적으로 상호작용하는 프로세스의 우선순위는 상대적으로 매우 높은편이며, 압축해제와 같은 프로세스는 상대적으로 낮은 우선순위를 가지고 있다.

프로세스는 생성된 후 생성, 준비, 실행, 대기 상태를 거쳐서 완료되며, 실질적인 작업은 실행와 대기를 번갈아가면서 처리된다. 이때 CPU를 할당 받아 작업을 처리하는 작업을 CPU 버스트, 입출력 작업을 입출력 버스트라고 한다.

• CPU 집중 프로세스 : CPU 버스트가 많은 프로세스.
• 입출력 집중 프로세스 ; 입출력 버스트가 많은 프로세스. (ex. 데이터 복사)

CPU 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때는 입출력 프로세스를 먼저 처리하는게 효율적이다. 입출력 집중 프로레스가 CPU > 대기 (=긴 시간동안 I/O처리) 할 때 CPU 집중 프로세스가 실행되면 되기 때문

프로세스는 사용자와의 상호작용 정도에 따라도 구분되어진다.

• 전면 프로세스 : GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스. 현재 입력과 출력을 사용하는 프로세스
• 후면 프로세스 : 사용자와 상호작용이 없는 프로세스 (ex. 압축 프로그램)

본 벨로그의 내용 및 이미지는 다음의 강의를 참고해서 작성이 되었으며, 틀린 내용이 있을 수도 있으니 너그럽게 봐주시면 감사하겠습니다:)

• 널널한 개발자 TV님의 운영체제 강의 Process와 Thread의 차이
• 널널한 개발자 TV님의 운영체제 강의 Chapter03
• 10분 테코톡 코다의 Process vs Thread
• 한빛 아카데미 '쉽게 배우는 운영체제'

Process? Thread?

기본적으로 프로세스와 스레드는 cpu core에서 실행되는 하나의 처리 단위이다. 일반적으로 OS는 프로세스를 하나의 작업(=관리) 단위로 보고, 하나의 프로세스 안에는 개별화된 코드의 흐름이 있을 수 있는데, 그 개별화된 하나의 코드의 흐름을 스레드라고 정의한다. 이때 하나의 프로세스 안에 여러 개의 코드의 흐름이 있는 경우에 멀티스레딩이라고 한다.

Process란?

그렇다면 프로세스란 무엇인가?

우리가 짜놓은 코드는 프로그램의 형태로 2차메모리인 HDD나 SDD에 저장이 된다. 이 프로그램을 실행하면, OS는 프로세스가 실행되기 위한 제한된 연산장치의 공간을 각 프로세스에 할당하는데 이를 Virtual Memory (가상 메모리)라고 한다. 위의 그림에서 보이는 것처럼 프로세스는 이러한 가상 메모리 공간을 실행 명령을 포함하는 코드들이 포함된 Code영역 Static 변수 혹은 Global 변수가 포함된 Data 영역, 동적 메모리 영역인 Heap 영역, Stack 영역이 차지하며, 해당 프로세스가 어느 정도까지 처리되었는지 확인하기 위해 필요한 Process Control Block (PID, PC, Register, ...) 역시 가상 메모리 공간 위에 올라간다.

서두에 하나의 프로세스 안에 여러개의 스레드가 존재할 수 있다고 했다. 이 말은 곧 하나의 프로세스 안에 있는 여러 개의 스레드의 공간은 OS가 그 프로세스에 할당된 가상 메모리로 그 공간이 한정된다는 뜻이다. 각 스레드들은 가상 메모리 내에서 공용 공간으로 사용할 수 있는 공간도 있지만, 각각의 스레드만이 사용할 수 있는 공간이 Thread Local Storage라는 공간도 존재한다.

다시 프로세스로 돌아와서, CPU는 한번에 하나의 작업만을 처리할 수 밖에 없기 때문에 여러 프로세스들을 동시에 (작은 단위로 나누어서 하나씩) 처리하기 위해서는 하나의 프로세스를 처리하다가 그 프로세스를 대기상태로 보내고, 다시 다른 프로세스를 처리하는 시분할 방식이 도입되었다.

Process의 상태

시분할 방식을 위해서는 각 프로세스는 여러 상태로 전이되면서 관리되는데, 프로세스가 가질 수 있는 상태를 구체적으로 명시해보면 다음과 같다.

1. 생성 : 프로세스가 메모리에 올라와 실행 준비를 한 상태로 PCB가 생성된다.
2. 준비 : 실행 대기 중인 프로세스가 자기 순서를 기다리는 상태이다. 프로새스 제어 블록은 ready queue에서 자기 순서를 기다리며 CPU 스케줄러에 의해 관리된다. 준비상태에서 자기 순번이 되면 dispatch(PID)를 통해 해당 프로세스가 실행이 된다.
3. 실행 : 프로세스가 CPU를 할당받아 실행되는 상태이다. 하나의 프로세스는 타임 슬라이스라는 주어진 시간동안만 CPU를 사용할 수 있는데, 이 시간이 지나면 timeout(PID)를 통해 해당 프로세스는 실행 상태에서 준비상태로 상태가 옮겨진다. 만약 실행 상태 동안 작업이 완료되면 exit(PID)가 실행되어 프로세스가 정상 종료된다. 만약 실행 상태에 있는 프로세스가 입출력을 요청하면 CPU는 입출력 관리자에게 입출력을 요청하고 해당 프로세스에 대해 block(PID)를 실행하면 해당 프로세스는 대기 상태로 옮겨진다.
4. 대기 : 실행 상태에 있는 프로세스가 입출력을 요청하면 입출력이 완료될때까지 기다리는 상태이다. 입출력이 완료되면 wakeup(PID)로 해당 프로세스는 다시 ready queue의 맨 뒤로 들어가 다시 준비 상태로 이동하게 된다.
5. 완료 상태 : 프로세스가 종료되는 상태로, 왼료 상태에서는 코드와 사용햇던 데이터를 메모리에서 삭제하고 프로세스 제어 블록을 폐기한다. 비정상적으로 종료되는 강제 중료를 만나면 디버깅하기 위해 강제 종료 직전의 메모리 상태를 저장장치로 옮기기 위해 덤프를 뜨기도 한다.

Context Switching

Context switching은 실행 상태에 있던 프로세스(P1)가 타임아웃이 되면 PCB1에 자신의 상태를 저장하고 준비 상태에 있던 프로세스 P2가 PCB2에 있는 자신의 상태를 가져와서 실행하는 CPU내에서 문맥이 변경되면서 연산이 실행되는 과정을 의미한다.

Process의 구조

프로세스의 구조는 위의 그림에서 보이는 것처럼 크게 4가지로 나누어진다.

• 코드 영역 : 실행 명령을 포함하는 코드가 포함되어 있는 영역 (일반적으로 읽기 전용으로 처리)
• 데이터 영역 : 크드가 실행되면서 사용하는 변수나 파일 등의 각종 데이터가 있는 영역 (읽기 쓰기 둘다 가능)
• 스택 영역 : 프로세스를 실행하기 위해 부수적으로 필요한 데이터
• 힙 영역 : 동적 메모리 영역

Process의 생성과 복사

프로그램이 시작되면 OS 프로그램을 실행하기 위해 프로세스를 생성한다. 다시 말해 OS는 프로세스를 위해 PCB 및 해당 프로세스를 실행하기 위한 공간인 Virtual Memory Space를 할당한다.

SSD로부터 매번 RAM까지 프로그램을 올리려면 시간이 많이 걸리기 때문에 이미 실행 중인 프로세스로부터 새로운 프로세스를 복사하는 방법도 있다. (이미 구글 크롬을 실행하고 있는데 새로운 창을 띄우거나 이미 워드프로그램을 실행 중인데 또 실행) 대표적인 방법으로는 fork()와 exec()이 있다고 한다.

• fork(): 프로세스를 복사할 때 새로운 VMS를 할당한다. 즉 복사된 프로세스는 새로운 PID, 코드, 데이터, 스택 영역을 확보하게 된다.
• exec(): 프로세스를 복사할 때 새로운 VMS를 할당하지 않고, 기존 프로세스가 할당 받았던 VMS 영역을 자식 프로세스가 덮어쓰는 방식이다. 이렇게 될 경우, PID, PPID, CPID는 그대로 유지되며, 코드 영역, 데이터 영역, 스택 영역만이 변경된다.

Thread

프로세스가 생성되면 CPU 스케줄러는 프로세스가 해야 할 일을 CPU에 전달하고 실제 작업은 CPU가 수행한다. 이때 CPU 스케줄러가 CPU에 전달하는 일 하나가 스레드이다.

Multi-tasking vs Multi-threading

그렇다면 스레드를 사용하는 이유는 무엇일까? 프로세스는 크게 프로세스가 실행되면서 바뀌지 않는 영역인 정적인 영역과 작업을 하면서 바뀌는 동적인 영역(레지스터, 힙, 스택)으로 구분된다. 이때 OS가 빠른 작업을 위해 fork()를 통해 프로세스를 여러 개 만들면 multi-tasking을 한다고 할 수 있다. 하지만 multi-tasking은 불필요한 정적 영역을 계속 메모리에 복사하기 때문에 비효율성을 초래한다. 따라서 하나의 VMS안에서 정적인 영역은 공유하고 스레드별로 독립적인 동적 영역을 가지면서 작업을 하는 multi-threading이라는 개념이 도입되었다. Multi-threading에서는 각 스레드 별로 동기화 이슈를 처리하는 것이 중요하다고 한다.

cf) Mutli-processing vs Mulit-threading 멀티프로세싱은 CPU를 여러 개 사용하여 여러 개의 스레드를 동시에 처리하는 작업 환경을 말한다. 하나의 컴퓨커에 여러 개의 CPU 혹은 하나의 CPU 내 여러 개의 코어에 스레드를 배정하여 동시에 작동하는 경우 멀티프로세싱이라고 한다. 반면 멀티스레딩은 '프로세스' 내 작업을 여러 개의 스레드로 분할함으로써 작업의 부담을 줄이는 프로세스 운영 기법이다.

멀티스레드의 장점으로는

• 응답성 향상 : 한 스레드가 I/O처리를 할 때 다른 스레드가 작업을 처리
• 자원 공유 & 효율성 향상 : 프로세스 내 자원을 공유함으로써 불필요한 자원 낭비 방지

멀티스레드의 단점으로는

• 한 스레드에 문제가 생기면 전체 프로세스에 영향을 미침 (인터넷 익스플로러)

Multi-thread Model

스레드는 프로세스와 마찬가지로 구현하는 주체에 따라서 '사용자 스레드'와 '커널 스레드'로 나누어 진다.

• 커널 스레드 : 커널이 직접 생성하고 관리하는 스레드
• 사용자 스래드 : 라이브러리에 의해 구현된 일반적인 스레드 (사용자 스레드가 커널 스레드를 사용하려면 시스템 호출로 커널 기능을 이용해야 함)

1 to N Model

하나의 커널 스레드가 여러개의 사용자 스레드와 mapping되는 모델. 사용자 스레드 간의 문맥 교환과 같은 부가 작업이 줄어들어 속도가 빠르다는 장점은 있지만, 하나의 커널 스레드가 여러 사용자 스레드와 연결되어 있기 때문에 커널 스레드가 대기 상태에 들어가면 모든 사용자 스레드가 같이 대기 상태로 들어가게 된다. 또한 멀티코어나 멀티프로세스의 이점을 충분히 이용할 수 없다는 단점도 존재한다.

1 to 1 Model

하나의 사용자 스레드가 하나의 커널 스레드와 mapping된 모델. 커널 스레드가 독립적으로 스케줄링되기 때문에 작업 효율성이 높으며, 사용자 스레드는 커널 스레드가 제공하는 보호 기능과 같은 기능을 사용할 수도 있다. 하지만 (여러 스레드 생성으로 인한) 높은 생성비용 및 문맥 교환할 때의 오버헤드 비용은 단점이다.

M to N Model

M개의 사용자 스레드가 N개의 커널 스레드로 (일반적으로 M>N) mapping되는 모델. 1 to N Model과 1 to 1 Model의 장단점을 모두 가지고 있다.

Buffer는 속도에 차이가 있는 두 장치 사이에서 그 차이를 완화하기 위해 도입된 기술이다. 데이터를 입출력할 때 한번에 하나씩 전송하는 것이 아니라 일정량의 데이터를 모아 한꺼번에 전송함으로써 속도 차이를 완화활 수 있는데, 이때 사용하는게 바로 버퍼이다.

Cache

CPU는 속도가 느린 SDD가 아닌 RAM에서 데이터를 받아 연산을 처리하는데, RAM조차도 CPU의 연산속도를 따라잡는데에는 한계가 있다. 따라서 이를 완화하기 위해 도입된 장치가 Cache이다.

위의 그림은 컴퓨터 저장장치의 계층 구조를 보여준다. 위로 갈수록 속도는 빠르지만 그만큼 비용도 비싼 저장장치이다. 캐시는 CPU의 임시 저장 장치인 레지스터 다음으로 빠른 속도를 가지고 있다. CPU 캐시는 크게 L1, L2, L3 캐시로 나누어 진다. 강의에 따르면 제조사마다 다르지만 L1,L2 캐시는 CPU 코어마다 붙어있고 L3 캐시는 모든 코어가 공유한다고 한다.

CPU는 L1 > L2 > L3 > RAM 순으로 메모리를 요청하게 된다. 이때 캐시에 원하는 데이터가 캐시에 있으면 캐시 히트, 없으면 캐시 미스라고 한다. 캐시에 있는 데이터는 메모리에 있는 데이터를 임시로 가져온 것이다. 따라서 캐시의 변경된 데이터를 메모리에 반영할 때 즉시 변경하는 경우를 즉시 쓰기라고 하고, 변경된 내용을 모아서 주기적으로 반영하면 지연 쓰기라고 한다.

본 벨로그의 내용 및 이미지는 다음의 강의를 참고해서 작성이 되었으며, 틀린 내용이 있을 수도 있으니 너그럽게 봐주시면 감사하겠습니다:)

• 널널한 개발자 TV님의 운영체제 강의 컴퓨터가 3층집인건 알고 있죠?
• 한빛 아카데미 '쉽게 배우는 운영체제'

운영체제

운영체제란 사용자에게는 편리한 인터페이스 환경을 제공하고 컴퓨터 시스템의 자원을 효율적으로 관리하는 소프트웨어이다. 다시 말하면 OS가 사용자 측에게는 process 관리를 제공하고 하드웨어 측에게는 자원 관리를 제공한다고 보면 된다.

운영체제의 구조

위의 그림처럼 컴퓨터는 크게 user mode, kernel mode, hardware mode로 나누어 진다. 사용자가 어떤 프로그램을 만들어서 process를 실행하면 해당 process가 실행되기 위해서는 cpu와 같은 하드웨어에 직접 접근하지 않는다. 'System call' 이라는 인터페이스를 통해 user mode에서 kernel 모드로 넘어가면서 device driver를 제어하기 시작한다. 즉 응용 프로그램이 하드웨어 자원에 접근하거나 OS가 제공하는 서비스를 이용하려할 때는 system call을 이용해야 하며, 이렇게 함으로써 컴퓨터 자원을 보호할 수 있게 된다. kernel mode와 hardware mode 사이의 인터페이스는 driver가 담당한다. 이때 device driver가 IRQ를 통해 인터럽트를 요청하면서 원하는 장치를 사용하면서 연산을 시작하고 본인의 작업(위의 프로세스)이 끝나면 return하게 된다.

인터페이스(interface) 는 서로 다른 두 개의 시스템, 장치 사이에서 정보나 신호를 주고받는 경우의 접점이나 경계면이다.

드라이버 는 운영 체제와 디바이스가 서로 통신할 수 있는 소프트웨어 구성 요소

API

Application Programming Interface란 응용 프로그램이 자신과 연관된 프로그램을 만들 수 있도록 제고하는 인터페이스이다. API는 시스템 호출보다 광범위한 개념이며, 운영체제의 API를 시스템 호출이라고 정의할 수 있다.

인터럽트

인터럽트란 CPU가 특정 기능을 수행하는 도중에 급하게 다른 일을 처리하고자 할 때 사용할 수 있는 기능이다. (출처: 나무위키) CPU는 입출력 관리자 라는 장치를 통해 메모리와 통신하는데, 인터럽트가 발생하는 과정은 다음과 같다.

1. CPU가 입출력 관리자에게 입출력 명령을 보낸다.
2. 입출력 관리자는 명령받은 데이터를 메모리에 가져다 놓거나 메모리에 있는 데이터를 저장장치로 옮긴다.
3. 데이터 전송이 완료되면 입출력 관리자는 CPU에 '인터럽트' 라는 완료 신호를 보낸다.
4. 인터럽트가 발생하면 CPU 내부의 레지스터(PCB, PC), 메인 메모리 내용 등을 저장한다.
5. 해당하는 인터럽트를 처리해주기 위한 인터럽트 서비스 루틴을 처리한다.
6. 인터럽트 처리 이후 저장되었던 이전 작업의 상태를 복구하고 이전 작업 수행을 재개한다.

Direct Memory Access

I/O가 필요할 때 CPU로부터 입출력 요청을 받은 입출력 관리자가 데이터를 메모리가 가져다 놓기 위해서는 메모리에 대한 접근 권한이 필요해 또 다시 CPU와 통신을 해야 한다. 하지만 DMA를 지원할 경우, 특정 하드웨어 하위 시스템이 CPU와 독립적으로 메인 시스템 메모리에 접근할 수 있게 도와준다. 주변장치의 데이터는 장치 컨트롤러에 의해 로컬 버퍼로 이동한다. 그러나 전송할 데이터가 많은 경우, 많은 양의 데이터의 이동으로 인한 부담이 커지는데 이러한 문제를 해결하기 위해 DMA를 이용한다. 장치 컨트롤러가 데이터의 한 블록을 이동시키는데 이 과정에서 DMA로 인해 CPU의 개입이 필요없게 된다. CPU에서는 데이터 이동이 완료되었다는 단 한 번의 인터럽트만 발생한다. 데이터가 전송되는 동안 CPU는 다른 작업을 수행할 수 있게 되어 효율성이 높아진다. (위키피디아 참조)

Introduction

Open-AI의 GPT3와 같은 모델들은 좋은 성능을 보이지만, 자연어 생성이라는 task 측면에서는 여전히 제한적인 성능을 보이고 있다.

그 이유는 LM의 목적함수가 training data의 true distribution과 model prediction이 완벽하게 일치하지 않으면 값이 커지는 cross entropy loss로 설계되어 있기 때문이다.

이에 따라 cross entropy를 최소화하도록 훈련된 LM들은 text degeneration problem에 노출되는데, token, phrase, sentence 단위의 중복 생성이 그 대표적인 현상이다. (대화나 요약 task에 fine-tuning한 후 실제 생성결과를 뜯어보면 이러한 현상을 빈번히 찾아볼 수 있다.)

본 눈문은 이러한 text degeneration problem을 해결하기 위한 방법론을 제시하기에 앞서 LM이 생성하는 단어를 3가지로 구분해 정리한다.

1. Positive token (Label Token)
2. Negative token (Incorrectly repeating Token, 이전 context에 존재했던 token)
3. Irrelevant token (All other Token)

기존의 cross entropy가 non-label로 취급하는 token을 negative token과 irrelevant token으로 구분해서 정의한다고 보면 된다. Negative token의 경우 사실상 생성하는 t번째 token이전의 m개의 token들인데, 이는 LM이 같은 단어, 구, 문장을 계속해서 생성하는 경향을 없애기 위해 이렇게 정의한 것 같다. Irrelevant token은 말그대로 target token과 관련 없는 token들이다.

Backgrounds

제안하는 Contrastive token learning은 Cross Entropy와 Unlikelihood Training에 기반을 두고 있는데, 각 방법론을 비교하는 그림은 아래와 같다.

Cross Entropy

위와 같은 cross entropy 식은 (1) > (3)으로 변형될 수 있는데, cross entropy가 label token과 다른 모든 non-label token를 효율적으로 contrast하면서 학습되도록 설계되었음을 의미한다.

Unlikelihood Training

cross entropy의 repetition 문제를 해결하기 위해 2020년에 unlikelihood training이라는 방법론이 개발되었다. 이 방법론은 위의 수식에서 보이는 것처럼 negative token들에 대한 likelihood를 낮추는 식으로 설계된 후 가중합 형식으로 기존 CE에 더해져서 활용되었다. (위의 식은 t번째 이전의 모든 token들을 negative token이라고 치부했는데, 이를 보정하기 위해 원논문에서 t번째 이전의 k개의 token들을 prefix 형태로 negative token들로 취급하는 sequence-level unlikelihood objective 방법론을 제안했다.)

Discussions

위의 CE와 UT는 Repetition 문제를 완전히 해결하기에는 한계가 있다.

CT는 negative token과 irrelevant token을 동일하게 penalize한다는 점에서 제한적이다. 이는 실제 generate 시에 repetition 문제를 해결하기 어렵게 만든다. (따라서 negative token를 irrelavant token보다 더 hard하게 penalize해야 한다.)

UT는 (1) 한 negative token을 penalize하는 정도가 다른 negative token에 의해 결정되기 때문에 (negative token을 penalize하는데 있어서) 제한적이며 (2) 식 자체가 irrlevant token의 likelihood를 의도치 않게 높히도록 설계 되었다는 한계를 지니고 있다. (gradient analysis 참조)

Method

Contrastive token learning & Negative Token Selction

CE와 UT의 장점만을 가져오기 위해 저자들은 contrastive learning 기법을 차용했는데, 구체적인 내용은 다음과 같다.

Unlikelihood learning과 달리 contrastive token learning은 매 time step마다 positive (i.e., label) token과 negative token과의 distance를 넓힐 수 있는 loss term을 추가하고 이를 CE와 더해 최종 loss식을 완성하였다. 저자들이 제안한 contrastive token learing 식은 irrelavant token에 영향을 주지 않기 때문에 기존 CE와 결합했을 시에 negative token들에만 더 강한 penalty를 줄 수 있다는 장점이 있다.

UT 저자들이 제안했던것처럼, 문장이 길어질수록 선행하는 모든 token을 negative token으로 활용하는 것은 noise를 증가시키기 때문에 앞의 M개의 token만을 매 time step의 negative token으로 설정하였다.

Gradient Analysis

저자들은 왜 contrastive token learning이 효과적으로 negative token의 likelihood를 낮출 수 있는지를 gradient analysis를 통해 분석하였다.

!! 분석하기에 앞서 헷갈리지 않게 기억할 것 !! Minimize하는 Loss Function에 대한 Logit의 Gradient가 음수 : 해당 Logit의 한 단위 증가는 Loss 값을 감소시킨다

Cross Entropy

CE의 경우 positive token은 loss를 개선 (감소), irrelevant & negative token은 Loss를 억압한다.

Unlikelihood Training

UE의 경우 negative token은 loss를 개선시키는 것이 다른 negative token ($x_{t}^{-'}\neq x_{t}^{-}$)의 영향에 달려있다.

또한 위에서 보이는 것처럼 irrelevant token들은 loss를 감소시키면 안되는데 감소시키는 방향으로 gradient가 설정되어 있다.

Contrastive Token Learning

하지만 보이는 것처럼 contrastive token learning은 positive token (loss 감소)과 negative token(loss 증가)이 둘다 적절한 방향으로의 gradient를 가지고 있음을 알 수 있다.

Experimental Setup

Baselines

(i) The vanilla cross-entropy (CE) objective (ii) decoding-based methods: banning 3-grams, top-k sampling, nucleus sampling, and contrastive search (SimCTG-CS); and (iii) learning-based methods: unlikelihood training, SimCTG, and noise-contrastive estimation

Model

GPT2-Small Fine-tuning

Dataset

Wikitext-103 (50K steps with 3K warm-up steps)

Evaluation Metrics

(i) ppl (ppl : 512 token | ppl-s : 50 tokens) (ii) generative repetition (the number of repeated n-grams divided by the total number of generated n-grams in each sequence) (iii) diversity (distinct 1-gram rates (dist-1) and unique 1-gram counts (uniq-1))

Evaluation Results

(논문에 decoding-based에 어떤 learning으로 fine-tuning 했는지 명확하게 나와있지 않아서 답답...)

• CT compared to learning-based approaches

다른 learning method와 비교했을 시에 repetition rate가 개선되었음을 알 수 있다. 특히 NCE와 비교했을 때 CT는 positive token과 negative token이 직접적으로 상호작용하도록 (=contrast) 목적함수가 설계되어 있는데, 이게 repetition rate와 diversity 개선에 도움이 되었다고 주장한다. (아래 식을 보면 NCE는 CT와 달리 positive token과 negative token이 loss내에서 직접적으로 상호작용 X & gradient에 영향을 주는 방향은 같음)

• CT compared to learning-based approaches

SimCTG-CS는 inference 단계에서 매 time step마다 previous token와의 거리를 (contrastive search) 고려해 새로운 token들을 생성하기 때문에 reptition rate가 개선되지만, 아래의 표에서 보이는 것처럼 coherence와 fluency 측면에서는 좋지 못한 성능을 보인다고 한다. (decoding 기법이 heuristic한 특성을 강화할수록 LM이 자연스러운 문장을 생성할 능력이 떨어진다.)

• Visualization analysis of the generation probability

각 방법론마다 inference시에 각 time step마다 positive, negative token에 얼만큼의 확률값을 부여하는 지를 시각화를 통해 비교하였다.

row & col은 time step을 의미하며, 색의 진하기는 확률을 의미한다. CE의 경우 주대각선 이외의 줄무늬도 많이 관측되는데 이는 reptition이 관측될 확률이 그만큼 높다는 것을 의미한다. 또한, 하단부로 갈수록 색이 진해지는 것을 확인할 수 있는데, 이는 생성의 후반부에 갈수록 앞쪽 context에 대한 의존성이 강화되면서 reptition bias가 심화되는 것을 관측할 수 있다. UL-TS는 time step이 조금만 길어져도 positive token에 대한 예측조차 불확실해진다는 것을 알 수 있다.

• Open-ended text generation은 prompt가 주어졌을때, 유창하고 일관성 있는 대답을 하는 것을 목적으로 한다.
• 하지만 likelihood가 가장 높은 sequence를 찾는 decoding은 짧고 반복적이며 유창하지 않은 문장을 생성하는 경향이 있으며, 크기가 작은 LM일수록 그 경향이 더 뚜렷하다.

• 이를 해결하기 위해 저자들은 위의 그림에서 보이는것처럼 크기가 큰 Expert LM의 Token 분포에서 크기가 작은 Amateur LM의 Token 분포를 빼주는 Contrastive Decoding을 제시해, 비교적 유창한 생서잉 가능한 Expert LM에서 Amateur LM의 경향성을 제거하는 방법론을 제시한다. (예시에서 Expert LM과 Amateur LM 모두 앞의 Honolulu와 Hawaii에 영햐을 받아 next token prediction에서 두 토큰에 높은 확률값을 부여했으나 contrastive decoding을 통해 상쇄되는 것을 확인할 수 있다)
• 제안하는 방법론은 (1) 추가적인 학습이 필요없는 방법론이며 (2) contrastive decoding하는 LM간의 크기 차이가 커질수록 그 효과가 극대화된다고 한다.

2. Problem Statement

• 문제상황은 우리가 아는 일반적인 LM setting인 n개의 token을 가진 input이 주어질 경우 m개의 token을 가진 문장을 생성하는 상황이다.

• baseline decoding strategy는 아래와 같다.

1. Nucleas Sampling : 상위 p% 누적분포에서 sampling
2. Top-K Sampling : 상위 K개의 token에서 sampling
3. Greedy : 매 time-step마다 max liklihood token select
4. Beam Search : Most probable sequence search의 대안으로 나온 greedy search

3 Contrastive Decoding

3.1 Intuition

• Reptition, Topic Drift, Self Contradiction과 같은 LM failure은 크기가 작은LM일 수록 더 높은 confidence level을 가지고 이를 생성하는 경향이 있다.
• 따라서 Expert LM에서 위와 같은 Amateur LM의 경향성을 제거하면 Decoding 성능을 향상시킬 수 있다.
• 하지만 위의 방법론이 적용되기 위해서는 Amateur LM의 생성 능력이 Expert LM의 생성 능력과 흐름은 비슷해야한다. 만약, Amateur LM이 아무말이나 생성하면 Expert LM에서 관련 경향성을 제거해도 성능 향상을 기대할 수 없다.
• 또한 Amateur LM이 항상 잘못된 Token을 생성하는 것이 아니기 때문에 이를 보정하는 수식도 필요하다.

3.2 Method

방법론은 매우 간단하다.

• 매 time step 마다 plausible token set $V_{head}$에 속해 있는 token들에 대해서 Expert LM과 Amateur LM의 log likelihood값의 차이를 구해주어 CD-Score라는 term으로 표기를 하고 beam search를 적용하였다.

• plausible token set $V_{head}$은 nucleas sampling과 유사하게 Expert LM내 확률값이 낮은 token의 영향력을 제거하기 위해 만들어준 집합이며, $\alpha$는 0.1로 설정하였다.

3.3 $V_{head}$ : Adpative Plausibility Constraint

저자들은 plausible token set $V_{head}$를 추가한 이유를 2개의 근거를 들어서 설명하고 있다.

1. False Positive 제거 : Expert LM에서 낮은 확률 값을 부여받은 token이 contrastive decoding에서 rewarding받을 가능성 제거 (ex. Expert LM에서 낮은 확률값 - bias로 인해 Amateur LM에서 더 낮은 값)

2. False Negative 제거 : Expert LM과 Amateur에서 모두 굉장히 높은 확률값은 그대로 활용하도록 (ex. uni + ##corn에서 ##corn에 대해서 Expert LM, Amateur LM ahen 0.99를 부여할 경우, ##corn만이 선택됨)

3.4 Choice of Amateur

제기하는 프레임워크의 핵심은 적절한 Amateur LM 선택을 통한 Expert LM내에서의 경향성 제거이며 저자들이 고려한 기준으 3가지이다.

• Scale : LM의 크기가 작을 수록 LM failure 확률이 높다. (GPT2끼리 비교한다면 GPT2-XL - GPT2-SMALL식으로 Expert와 Amateur 선정)
• Temepature : $\tau$를 활용해 Amateur LM의 Token dist 분포 조정
• Context Window : Contrastive Decoding 효과를 극대화하기 위해 Amatuer의 context-window (prompt size)를 Expert LM에 비해서 적게 두었다고 한다.

4. Interpretation

저자들은 아래의 2가지 관점을 기준으로 목적함수에 대한 해석을 제시한다.

4.1 Distinguishability

저자들은 본인들의 식이 PMI Score를 최대화하는 것이라고 합니다.

웨에 보이는 것처럼 PMI Score는 두 사건이 독립이면 0의 값을 가지지만, p(x) 대비 p(x|y)이 커지면 높아지게 되어 두 사건의 관련성이 높을수록 해당 점수는 높아진다.

저자들은 본인들의 목적함수를 아래와 같은 PMI 식으로 표현한다.

Expert LM에 의해 생성될 경우 $I=1$이라고 하면 위의 PMI식처럼 표현이 되며 Expert LM은 동일하면서 Amateur LM term의 값이 작아질수록 해당 값은 커지게 된다.

따라서 목적함수의 값을 극대화하는 것은 두 모델 사이의 결과값의 차이를 극대화하는 것과 동일하다.

4.2 Pragmatic Communication

Pragmatic Communication이란 사회적 상황에서 적절한 의사 소통을 사용하는 것으로 무엇을 말할지, 어떻게 말할지, 언제 말할지 아는 것이다. 즉 화자는 높은 퀄리티의 언어를 청자에게 정보력 있게 전달해야한다.

저자들은 본인들의 목적함수가

1. Expert Prob에 더 높은 가중치를 줌으로 유창하고 유의미한 정보를 전달하고
2. Amateur Prob에 더 낮은 가중치를 줌으로 정보성이 덜한 정보를 제거한다고 주장한다.

5. Experimental Setup

사용한 open-ended text geneneration 데이터셋은 다음과 같다.

• Wikinews
• Wikipedia
• Story Domains

각 데이터셋의 passage token 개수가 160개 이하이면 활용하지 않았고, 첫 32 words를 prompt token으로 뒤의 256 token들을 생성하도록 하였다.

Automatic Evaluation는 다음과 같다.

Human Evaluation은 Fluency와 Prompt랑 생성한 문장이랑의 통일성을 보는 Coherence를 가지고 측정하였다.

Baselines Decoding 방법론들은 아래와 같다.

• Nucleus Sampling
• Top-K Sampling
• Typical Decoding
• Greedy Decoding (EXPERT LM only)
• SimCTG

Contrastive Decoding을 위한 Expert - Amateur Pair는 다음과 같다.

• GPT-2 XL (1.5b) vs GPT-2 small (100m)
• OPT (6.7b) vs OPT (125m)
• OPT (13b) vs OPT (125m)

Experimental Results

실험결과 Diversity를 제외한 모든 지표에서 Contrastive Decoding이 좋은 성능 보였습니다. 특히 Model Scale이 커질수록 Nucleus Sampling과 Contrastive Decoding의 차이가 줄어든다고 한다.

Ablation Study

Ablation Study에 따르면 Expert와 Amateur 사이의 크기가 크면 클수록 contrastive decoding의 성능이 향상되며, tri-gram LM같이 Expert LM의 경향성을 따라가지 못하는 성능이 낮은 LM을 Amateur로 쓸 경우 contrastive decoding의 효용성을 활용할 수 없다고 한다.

또한 $\tau$에 대한 ablation test도 진행했는데, $\tau$가 0.5-1.5 사이에 있을 수록 Amateur LM이 spike한 distribution을 가지게 되면서 contrastive decoding의 성능을 극대화할 수 있다고 한다.