들어가며

최근 업무를 보면서 학습 데이터가 지속적으로 증가하는 경우가 발생하다보니 Incremental Leanring에 대해서 공부를 하는 경우가 생겼다. 그렇다보니 자연스럽게 2D object detection이외에 다른 분야에도 있을까 생각하고 찾아보다 보니 해당논문을 찾게 되어졌다. 

이 논문의 경우 AAAI 2022년 Oral paper로 되어진 논문으로 3D 분야에서 처음으로 적용한 부분이다 보니 더욱 주목 받는 방법이 아닐까 생각이든다. 

아래의 그림처럼 Incremental Learning의 기조를 따라가다 보니 Novel Class에 대해서 객체를 찾게 되어지고 기본 Base Classes에서도 여전히 찾게 되어지는것을 볼 수 있다.

그렇다면 이 논문의 핵심 아이디어의 핵심은 새로운 Task에 적용한것 말고 어떤것이 있을까? 

저자는 새로운 아디이어로 Pesudo Labeling을 방식을 제안했다. 일반적인 방식이 있을수도 있지만 이전의 Task에서 만들어진 모델을 바탕으로 새로운 Novel에 기존의 Base의 class에 Pesudo labeling을 같이 넣어서 학습을 시키는것이다. 

그렇게 되면 Pesudo labeling의 중요성이 높아지는데 이를 해결하기 위해서 Techer Student Model을 들고왔고, Static & Dynamic 이라는 두개의 Teacher를 들고오면서 해당 문제를 해결했다고 한다. 

그러면 자세하게 이 논문이 어떤 방식으로 문제를 풀었는지 살펴보자. 

방법

Baseline Model

3D에 접근하기 위해서는 저자는 Point Clould Object Detection의 기본이 되어지는 모델일 VoteNet을 수정해서 개선이 되었다고 한다. 

VoteNet의 경우 아래의 그림과 같이 있는데 $X$라는 XYZ를 가지는 좌표값을 넣어 Featuer를 추가한 $S$라는 seeds를 뽑아낸다. 이 과정까지는 일반적인 방법이지만 Voting Module이라는 방식을 통해서 Point들을 대표할수 있는 지점을 뽑고 그 주위의 Point들을 구성해서 새롭게 만들어낸다. 이를 통해서 $V$라는 point들이 최정적으로 나오게 되어진다. 

이 point들을 바탕으로 Detection이 수행이 되어진다.

SDCOT 모델방식

Pesudo Label Generation 

이전에 말했던것처럼 이 논문의 경우 Peusdo label을 만드는것에 아디어를 더했다고 한다. 

Novel Class를 학습할때 Base Class로 학습 했던 모델을 Novel Class에 Peusdo labeling을 만들어서 적용했다고 한다. 

이 Peusdo labeling을 만드는건 생각보다 너무 쉬운데 Low-confidence box 부분을 지웠고 그리고 Classification 의 확률값과 바탕으로 낮은 Prob을 가진 Class도 Pesudo labeing이 넣지 않는 방식을 선택했다. 

그럼에도 불구하고 부정확한 결과가 나온다는데 이를 해결하기 위해서 아래의 새로운 방법을 사용한다. 

Static-Dynamic Co-Teaching

저자는 부정확한 결과를 개선하기 위해서 Static Teacher과 Dynamic Teacher를 2개를 만들어서 작업을 하는데 각각의 Teacher의 하는 역할은 다음과 같이 나뉘어진다. 

Static Teacher의 경우는 Base Class로 학습한후 Freeze되어진 모델이며 이 Teacher의 역할은 Peusdo labeling을 만들어 내는 역할을 하며 Distillation을 Student에 하는 역할로 보면되어진다. 

Dynmaic Teacher의 경우는 기존의 Student에 대해서 EMA가 진행이 되어짐과 동시게 Input에 대해서 Consistency를 유지하기 위한 역할을 수행한다. 

전체적인 흐름은 아래의 그림과 같이 되어진다. 

그러면 각각의 Loss는 아래와 같이 되어진다. 

Distillation Loss의 경우는 Student와 Static Teacher의 SoftMax이전의 Logit의 값의 차이를 최소화하는 작업을 말한다. 그럴경우 이전의 Knwoledge를 Distiliation하는 효과가 있다. 

Supervised Loss의 경우는 기존의 CE로 적용이 되어지면 Novel Class를 추가해서 BaseL Class와 함께 재 학습을 하는데 이때 Base Class의 경우는 Static Teacher에서 나온 Pesudo label로 적용이 되어서 학습이 되어진다. 

Consistency Loss의 경우에서는 SimCLR와 같은 Loss를 사용한다고 보면된다.

방법은 너무 단순하지만 효과적으로 나오며 기존에 접근하지 않았던 새로운 방법이라 확실히 성능적인 면은 효과가 있다. 

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

27

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

9

Solution

1. 이 문제의 경우에서는 완전탐색으로 풀어야 된다. 그렇다면 BFS/DFS둘중에 하나이다. 

2. 바이러스의 대한 정보를 저장해놓는것이 중요함.

3. 4방향으로 바이러스는 퍼짐

4. 백트레킹으로 시간단축을 해야됨 

5. 하지만 combination으로 변경해서 풀면 시간 내에 풀림 

import sys
import copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline
N,M = list(map(int,input().split()))

# 바이러스 위치 추출
maps = []
birus_list = []
y_x_list = []
for yidx in range(N): 
    row = list(map(int,input().split()))
    maps.append(row)
    for xidx, j in enumerate(row): 
        if j == 2 : 
            birus_list.append([yidx, xidx])
        if j == 0 : 
            y_x_list.append([yidx,xidx])

moves = [[-1,0],[1,0],[0,-1],[0,1]] # moving
answer = 0 
def move_avaiable(y,x,tmp_maps): 
    return 0<=y<N and 0<=x<M and tmp_maps[y][x] == 0

def cal_area(tmp_maps): 
    return sum([row.count(0) for row in tmp_maps])

def bfs(): 
    global answer
    q = deque(birus_list)
    tmp_maps = copy.deepcopy(maps)

    while q: 
        y, x = q.popleft()
        for dy, dx in moves: 
            ny, nx = dy + y, dx + x
            if move_avaiable(ny, nx, tmp_maps): #이동가능하면 퍼진다.
                tmp_maps[ny][nx] = 2 # 새롭게
                q.append([ny,nx])
    count = cal_area(tmp_maps)
    answer = max(answer, count)
    return 
# map의 기준으로 벽생성
# def make_wall(cnt): 
#     if cnt == 3: 
#         bfs()
#         return 
#     for j in range(N): 
#         for i in range(M): 
#             if maps[j][i] == 0 : 
#                 maps[j][i] = 1
#                 make_wall(cnt+1)
#                 maps[j][i] = 0 # backtrking

def make_wall(cnt): 
    for c in combinations(y_x_list,3): 
        for cy, cx in c:  maps[cy][cx] = 1
        bfs()
        for cy, cx in c:  maps[cy][cx] = 0

make_wall(0)
print(answer)

https://www.acmicpc.net/problem/14500

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

19

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

20

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

7

https://www.acmicpc.net/problem/3190

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

9

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

21

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

13

문제방법

1. 문제대로 차근차근이 읽으면서 경우의 수를 생각해서 예외처리해주면됨 

2. 큐의 형태로 생각하면서 문제를 풀자.

from collections import deque
import sys
inputs = sys.stdin.readline
N = int(inputs())
maps = [[0]*N for _ in range(N)]

K = int(inputs())
apple_index = [list(map(int,inputs().split())) for _ in range(K)]
for y,x in apple_index:
    maps[y-1][x-1] = -1 # 사과 있음 

D = int(inputs())
directions = {}
for i in range(D):
    x, c = input().split()
    directions[int(x)] = c

move = [[0,1],[1,0],[0,-1],[-1,0]] #오하왼상 
## 몇초안에 끝나는지.. 계속 길이가 길어지고 있음 & 큐로 푸는것임.. 구현문제도 맞는듯.. 

def rotate_direction(curr_dir, move_idx): 
    if curr_dir == 'L': 
        move_idx -= 1
    elif curr_dir == 'D': 
        move_idx += 1
    return move_idx%4

# 너무 어렵게 생각하지말자.뱀의 길이가 이전의 길이에 따라오면 되는 것이 핵심 아이디어도 
y, x, curr_dir = 0,0,0
start_time = 0 

q = deque()
q.append((y,x))
while True : 
    start_time += 1 
    dy, dx = move[curr_dir] # 초기 방향설정
    ny, nx = y + dy, x + dx # 다음길이로 이동
    if ny < 0 or ny >= N or nx < 0 or nx >= N or (ny,nx) in q:  # 벽에 부딧치거나 꼬리에 부딧치면 게임 끝
        break
    # 사과를 먹지 못한다면 꼬리가 따라다님
    if maps[ny][nx] != -1:
        ty,tx = q.popleft()
        maps[ty][tx]=0
    
    # 지나갈때마다 경로를 체크
    y, x = ny, nx
    maps[ny][nx] = 1
    q.append((ny, nx))
	
    # 시간에 해당하는 방향전환 정보가 있을 경우
    if start_time in directions.keys():
        curr_dir = rotate_direction(directions[start_time], curr_dir)
print(start_time)

https://www.acmicpc.net/problem/14499

  2
4 1 3
  5
  6

4 2 0 0 8
0 2
3 4
5 6
7 8
4 4 4 1 3 3 3 2

0
0
3
0
0
8
6
3

3 3 1 1 9
1 2 3
4 0 5
6 7 8
1 3 2 2 4 4 1 1 3

0
0
0
3
0
1
0
6
0

문제풀이 

1. 구현문제이기때문에 3차원에서 주사위가 굴러갈때 변경되는 값을 저장해놓으면 쉽다.

2. 그외에 시작점이나 변수선언에 유의해서 작성하자 

import sys
inputs = sys.stdin.readline
N,M,y,x,K = list(map(int, inputs().split()))
maps = [list(map(int, inputs().split())) for i in range(N)]
direction = list(map(int, inputs().split()))

dice = [0,0,0,0,0,0]
move = [[0,1],[0,-1],[-1,0],[1,0]] #동서북남
sy,sx = y,x

def flip(dice, direct): 
    a,b,c,d,e,f = dice
    if direct == 1: #동    
        dice = d,b,a,f,e,c
    elif direct == 2: #서 
        dice = c,b,f,a,e,d
    elif direct == 3 : #북 
        dice = e,a,c,d,f,b
    elif direct == 4: #남
        dice = b,f,c,d,a,e
    return list(dice)

#주사위 문제로써 구현문제라고 볼 수 있다.
answer = []
for direct in direction: 
    dy,dx = move[direct-1]
    ny, nx = sy+dy, sx+dx
    if 0<=ny<N and 0<=nx<M: #범위안에서만 동작한다. 주사위가 돌아갔으며 위치도 위치도 이동함
        sy, sx = ny, nx
        
        dice = flip(dice, direct)
        
        if maps[ny][nx] == 0 : # 바닥면이 0이면 주사위의 값이 복사가 되어진다. 
            maps[ny][nx] = dice[-1]

        else: # 아닐경우 바닥면에 주사위의 밑으로 복사가 되어짐
            dice[-1] = maps[ny][nx] 
            maps[ny][nx] = 0 # 바닥은 0으로 변경됨 
        print(dice[0])