어찌보니 Leetcode 프리미엄이 1년치가 구독이 되어져버렸다.. (취소를 못한 나의잘못..)

여튼 그래서 이번에 공부를 좀 해보고자 한다.

Dynamic Programming(DP)에 대해서 공부한지가 너무 가물가물하니 예시 문제를 풀면서 Github에도 업로드도 하면서 복습하면 좋은 시간이 되어지지 않을까 싶다!

DP를 이해하기 앞서서 Recursion과 Greedy algorithm에 대해서 알아야하며 Big O와 hash tables에 대해서도 알아야 하며 잘 모를경우 Recursion먼저 배워야한다.

What is Dynamic Programming ?

DP가 무엇인가에 대해서 문게에 대해서 가능한 모든 방법을 탐색해서 해결하는 방식을 말하는데.. 이는 직관적으로 이해가 되지 않는다. 그래서 2가지의 특성을 가지면 이해할수 있는데 아래와 같다.

1. 여러번 재 반복해서 더 작은 문제로 풀수 있는 방법인가('overlapping subproblems')
2. 이러한 overlapping subproblems이 최적의 방법으로 풀수 있는가 ('optimal substructures')

대표적인 예시의 문제로 피보나치 수열의 문제가 있는데 이는 DP에 대해서 설명을 하여준다. 처음 시작은 0,1로 시작을 하고 다음에서는 이전에 정의되었던 0,1의 합으로 다음 수가 만들어지는 원리이다.

위의 그림처럼 $n^{th}$의 경우에서는 피보나치 수를 $F(n)$으로 정의를 하는데 방법을 subproblems로 나눌수 있다.즉 $F(n-1) + F(n-2)$로 나뉘어진다. 그리고 두 수식은 optimal substructure로 표현이 되어지는 $F(n) = F(n-1) + F(n-2)$로 더해진다. 이 subproblems은 overlapping이 되어진다.

위와 같은 방법은 greedy problems과 유사한데 optimal substructure를 가진다는 점이다. 하지만 overlapping(겹치지) 하지는 않다. 다른 방법중에 하나인 divide and conquer의 방법도 비슷하지만 overlapping하지 않는 점이 다르다고 볼 수 있다.

Top-down and Bottom-up

이러한 DP는 2가지의 방법으로 풀수 있으며 아래처럼 알려져있다.

1. bottom-up 은 tabulation
2. top-down은 memoization

Bottom-up(Tabulation)

이 방법의 경우에서는 가장 base case에서부터 시작되는 방법이다. 피보나치로 예시로 들었을 때 $F(0)=0, F(1)=1$를 사용하여 $F(3)$을 만들고 나중에 $F(n)$가지 만드는 과정을 말한다.

// Pseudocode example for bottom-up

F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

Top-down (Memoizaion)

이 방법의 경우는 recursion사용하고 효과적으로 memoization을 만들어진다. 예시로 $n^{th}$의 경우 $F(n)$의 피보나치 수를 가지며 이는 $F(n-1), F(n-2)$로 구성이 되어지는것을 찾을 수 있다. 이는 recusive 패턴을 찾아 $F(0) = F(1) = 1$이라는 것을 찾을 수 있다.
반복적인 패턴으로 인해서 $F(100)$같의 값을 찾기 위해서는 이전의 $F(99), ... F(0)$까지 값을 계산해야되는데 이는 비효율적이다. 결국 빠르게 찾기 찾기 위해서 memoize의 결과를 활용하고 이를 memoizion이라고 불린다.

**memoizion**는 결과의 값을 hashmap, array에 저장을 해 놓고 같은 값이 나오면 return을 하는 방법이다. 

코드는 아래와 같다.

// Pseudocode example for top-down

memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

둘중에 누가 좋나?

• bottom up의 경우에서는 runtime이 빠르다. 왜냐! recursive를 하지 않기 때문에
• top-down은 더 쉽게 코드 작성이 가능하며 recursion을 사용하지 않음.

When to Use DP

특히나 DP의 문제에서는 코테에서 문제를 푸는 방법을 찾는데 시간을 절반을 소요하기 때문에 앞서 말한 2가지의 특징이 중요합니다.

1. overlapping subproblems : 작은 문제를 여러번 사용이 가능해야됨
2. optimal substructure : 중첩되는 즉 overlapping의 문제를 최적의 방법으로 풀어야한다.
   이렇게 말하면 뭔가 느낌적으로 감이 안올것이기 때문에 좀더 쉽게 몇가지의 특징에 대해서 말해보겠습니다.

First characteristic

어떤 문제에 있어서 optimum value를 요구합니다.
예로들어서 가장 cost가 적게드는 maximum한 값, 몇가지의 방법이 있는가..등등
모든 방법들이 위의 예제같이 나타나진 않지만 공통된 특징을 가지고 있습니다.
첫번째의 방법은 설명한 방법을 무조건 DP로 풀진 않아도 됩니다. (Greedy algorithm 으로도 풀수 있음)

Second characteristic

DP의 다른 특징중에 하나는 미래의 decisions이 과거의 Decision에 영향을 가지는 특징을 가지고 있습니다.
마치 나비효과처럼 처음의 값이 나중에 값의 영향을 미치는것입니다.
이 특징은 greedy algorithm에서는 적용할수 없는 문제이기때문에 DP로만 풀수 있습니다.

0. 예시 문제 : Climbing Stairs

1. 예시 문제 : House Robber  (링크 : 풀이)

2. 예시 문제 : Longest Increasing Subsequence  (링크 : 풀이)

## Introduction

Tiny object detection의 경우에서는 실제 real image에서 많이 발견이 되어진다. 이미 object detection의 경우에서는 눈에 띄는 성능이 있었으며 large-scale의 object에서는 눈에띄는 성능의 향상이 있었다.

하지만 tiny object의 경우 16x16 픽셀의 아주 작은 이미지로 진행이 되어지며 information이 부족하며 또한 disriminative(분별)한 featurer가 학습하는것이 어렵다.

그렇기에 대표적으로 object detection의 성능만 보더라도 $AP_s$ 의 경우에서도 선능이 다르것에 비해서 높지 않는점이 있다.

이를 해결하기 위한 방법으로는 discriminative feature를 향상시키기 위한 방법도 있으며 , 어떤 방법은 small image의 resolution을 향상을 시켜서 input image의 scale과 비슷한 영상으로 만들어서 문제를 해결하는 방법이 있다. 

이와 유사하게 GAN을 사용하여서도 super-resolution의 method를 적용하여서 small object의 resolution을 키우는 방법도 사용되어지기도 한다. Network의 관점으로는 Feature Pyramid network(FPN)의 방법을 사용하여 다양한 feature size를 사용해서 TOD performance를 적용하기도 한다.

이번 논문에서는 위의 문제중에서 discriminative feature의 관점에서 문제를 풀어보도록 한다. 일반적으로 object detection의 방법중에서 anchor-base의 방법을 사용하게 되어지면 pos/neg의 대한 bbox를 사용할수 있는데 이의 경우 Figure 1에서 보이는 것처럼 Tiny object에서 문제를 다음과 같이 발생시키며 또한 Figure 2에서도 다음과 같은 문제가 생긴다.

1. 큰 Variance로 인해서 IOU의 값의 차이가 크게 남.

2. 일반적인 BBox의 경우 IOU-Deviation가 일정하나 small object의 경우에서는 IOU-Deviation이 급격하게 되어지는 점이 있다.

3. 작은 bbox의 이동만으로도 pos가 neg로 변경되어지기도 함.

4. tiny object에서는 IOU가 민감함으로 좋은 metric이 아님

이 방법을 해결하기 위해서 Normalized Wasserstein Distance(NWD)을 제안하였고 이는 gaussian distributions의 유사도를 측정할수 있다. 

## Method

IOU의 method랑 유사한 방법을 사용하였고 Jaccard similarity coefficient에서 영감을 받았다고 한다. 

이 저자는 distribution을 base로 문제를 제시하였고 일반적ㅇ니 2D Gaussian distribtuon은 다음과 같다. 

이때 x는 coordination , \mu는 mean, \sum 공분산이며 이는 

일단 처음으로는 bodning box에서 가장 중앙점 cx,cy의 값과 box의 width, height를 구한다.

처음에는 이러한 값들을 가지고는 아래의 값들과 같이 ellipse의 equation으로 나타낼수 있다.

또한 이 bbox를 2d gaussian distribution의 형태로 modeling을 할 수 있다.

이전에는 Pytorch1.x를 계속해서 사용했다. 

그렇다 보니 변경점과 어떤것을 적용해야될지 고민이 많이 되었는데 .. 이번 기회에 pytorch2.0을 알아보고 공부도 해보고 싶어서 알아보고자 한다. 

https://pytorch.org/get-started/pytorch-2.0/

다행이도 코드는 그대로 v1.x는 그대로 지원이 가능하다고 한다. 

API와 imperative style, python integration은 그대로 되어진다. 

다만 pytorch의 내부적으로 complier level의 작동하는 방식을 변경되었음. 

원래라면 Python API를 사용헀는데 pytorch의 torch.compile를 사용함으로서 속도가 더욱 빨라졌다고 한다. 

이 torch.compile는 4개의 구성요소로 되어있고 아래와 같이 되어있다.

• TorchDynamo , AOTAutograd  , PrimTorch  ,TorchInductor 

그 결과 속도가 매우 빨라졌다고 하며 성능을 확실하게 비교를 보여주기 위해서 HuggingFace, TIMM, TorchBench에 있는 Model를 전부 평가를 해보았다고 한다. 

신기한건 이때 속도를 개선할때 사용한 학습 기법은 AMP와 기존 Float32랑 Weight average를 해서 0.75*AM P + 0.25*float32로 해서 측정을 했다고 한다. 

그 결과 43%정도 빨라졌다고 하니.. 절반정도면 엄청나게 빨라진게 아닐까 싶다. 

이러한 compiler은 3가지의 구성으로 나누어져있으며 Graph acquisition, Graph lowering, Graph compilation으로 되어있다. 

기존에서는 torch.jit.trace, torchscript, Fxtracing, Lazy tesnor를 사용하였지만 일부분은 빠르지만 flexible하지 않고 몇몇에서는 좋지 않다고 한다. 

그림에서 보는 바와 같이. graph acquistion으로 나는 과정이 오래결렸다고 하며 이를 통해서 결과가 좀더 빨라졌다고 한다. 

앞전에 정리하였던 핵심적인 방법중에서 torchDynamo의 기술은 graph acquisition의 방법으로 CPython으로 되어있다고 한다. 

기존에서는 Torchscript는 graph를 만드는데 많은 시간이 걸렸다고 하는데 .. torchDynamo로 인해서 빠르게 만들어지는게 가능했다고 한다. 

TorchInductor는 TorchDynamo에서 생성된 FX 그래프를 최적화된 C++/Triton 커널로 컴파일하는 새로운 컴파일러 백엔드라고 한다. 

AOTAutograd의 경우에서는 training의 속도를 가속화하는 방법이라고 한다. 

결론.. 

결국 속도의 개선과 앞으로의 범용성으로 인해서도 변경할 필요가 있겠구나라는 생각이든다.