작성자 리뷰

Abstract

Time2Vec

1. Peroidicity : 주기적, 비 주기적인 패턴을 모두 표현할 수 있어야 합니다.
2. Time Rescaling : 시간의 단위를 변환 할 수 있어야 합니다.
3. Simplicity : 다양한 모델에서 사용할 수 있도록 간단해야 합니다.

Time2Vec

• t2v(τ) : time τ 에서의 벡터 t2v(τ)[ i ] : t2v(τ) 의 i 번째 element
• k : t2v의 dimension
• F : periodic activation function (논문에서는 sin 함수)

Properties

• Peroidicity
  sin함수를 통해 주기를 표현 할 수 있습니다.
  
• Time Rescaling
  w_i * τ = w_i * 60 * (τ/60) 으로 표현할 수 있습니다. 예를 들어 초 단위의 τ 를 분 단위의 τ/60로 변환 한다면 주기도 같은 만큼 변환됩니다.
  
• Simplicity
  간단한 sin함수의 벡터 형태로 시간을 표현할 수 있습니다.
  

Questions

Q1. Is Time2Vec a good representation for time?

• LSTM + T : LSTM에 Time 정보를 concat 하여 사용한 기존 모델

Q2. Can Time2Vec be used in other architectures and improve their performance?

Q3. What do the sine functions learn?

• 개인적으로 위 실험이 왜 Q3에 대한 답이 될 수 있는지 명확히 이해하지 못했습니다.

Q4. Can we obtain similar results using non-periodic activation functions instead of periodic ones?

Q5. Is there value in learning the sine frequencies or can they be fixed

Reference

• https://arxiv.org/pdf/1907.05321.pdf
• https://towardsdatascience.com/time2vec-for-time-series-features-encoding-a03a4f3f937e

hash(char[] key) c++ 코드

• c++ 코드로 보는 - 문자열 비교(strcmp), 문자열 카피(strcpy)

#include <stdio.h>

#define MAX_KEY 1000
#define MAX_TABLE 2000

int strcmp(const char *str1, const char *str2) {
        
        while (*str1) {

                if (*str1 != *str2) break;

                ++str1;
                ++str2;
        }

        return *(const unsigned char*)str1 - *(const unsigned char*)str2;
}


void strcpy(char *dest, const char *source){
        
        while (*source) {
                *dest = *source;

                ++dest;
                ++source;
        }
}



struct Node {
        int idx;
};

struct Hash
{
        //hash를 만들고자 하는 key
        char key[MAX_KEY + 1];
        //key에 할당 되는 data
        Node* data;
};

Hash htb[MAX_TABLE];

//djb2 algorithm 
unsigned long hash(const char *str)
{
        // hash값을 잘 분산 시키기 위해 실험적으로 증명된 상수 값
        unsigned long hash = 5381;
        
        int c;

        //문자열이 한 개씩 들어올 때 마다
        //아래와 같은 연산을 한 후 MAX_TABLE 값으로 modular연산을 한다
        while (c = *str++)
        {
                hash = (((hash << 5) + hash) + c) % MAX_TABLE; /* hash * 33 + c */
        }

        return hash % MAX_TABLE;
}

//주어진 key와 data를 테이블에 삽입하는 함수
int add(const char *key, Node *data)
{
        //key값을 hash값으로 변환
        unsigned long h = hash(key);

        //해당하는 hash값이 이미 사용되었다면(충돌이 일어난 경우)
        while (htb[h].key[0] != 0)
        {
                //같은 key값이라면 0을 return한다. 즉 같은 key가 존재하므로 add 하지 않는다
                if (strcmp(htb[h].key, key) == 0)
                {
                        return 0;
                }

                //open addressing 기법
                //같은 hash값이지만 다른 key라면 다음 hash값을 확인한다
                h = (h + 1) % MAX_TABLE;
        }

        //비어있는 해당 hash값에 key와 data를 저장한다 
        strcpy(htb[h].key, key);
        htb[h].data = data;
        return 1;
}

//key가 주어졌을 때, hash table내에 있는 data를 비어있는 주소값에 넣어 리턴하는 함수
int find(const char *key, Node *data)
{
        //key값을 hash값으로 바꾼다
        unsigned long h = hash(key);

        //테이블이 모두 차있을 경우를 대비하는 index
        int cnt = MAX_TABLE;

        //충돌이 일어나지 않거나, 모든 테이블을 검사할 때까지 탐색
        while (htb[h].key[0] != 0 && cnt--)
        {

                //찾고자 하는 key를 찾았으면 해당 데이터를 비어있는 주소값에 넣어 리턴
                if (strcmp(htb[h].key, key) == 0)
                {
                        data = htb[h].data;
                        return 1;
                }

                //open addressing
                h = (h + 1) % MAX_TABLE;
        }
        return 0;
}


int main() {

        char str1[] = "abcjoijdsafjioc";
        char str2[] = "dkjvoiadjsf";

        // output : 122
        printf("%d\n", hash(str1));
        
        // output : 1172
        printf("%d\n", hash(str2));

}

문자열 비교(strcmp), 문자열 카피(strcpy) c++ 코드

#include <stdio.h>

//str1과 str2를 비교
int strcmp(const char *str1, const char *str2) {
        
        //첫번째 str의 마지막까지 확인
        while (*str1) {

                if (*str1 != *str2) break;

                ++str1;
                ++str2;
        }

        //0보다 크면 str1 > str2
        //0보다 작으면 str1 < str2
        //0이면 str1 == str2
        return *(const unsigned char*)str1 - *(const unsigned char*)str2;
}


//source를 dest에 복사
void strcpy(char *dest, char *source){
        
        //source가 있을 때 까지 dest에 복사
        while (*source) {
                *dest = *source;

                ++dest;
                ++source;
        }
}

int main() {
        char str1[] = "abcde";
        char str2[] = "zewdf";

        // output : -25 => str1 < str2
        printf("%d\n", strcmp(str1, str2));
        // output : 25 => str1 > str2
        printf("%d\n", strcmp(str2, str1));

        strcpy(str1, str2);

        // output : 0 => str1 == str2
        printf("%d\n", strcmp(str2, str1));

}

Merge Sort c++ 코드

#include <stdio.h>

#define MAX_N 10

int arr[MAX_N] = { 9,6,5,8,4,2,3,1,7,0 };
int sorted_arr[MAX_N];

void merge(int left, int mid, int right) {
        int i, j, k;
        // i : left 에서 mid 까지 arr에서 움직이는 index
        // j : mid+1 에서 right 까지 arr에서 움직이는 index
        // k : sorted_arr에서 left부터 right까지 움직이는 index

        i = left;
        j = mid + 1;
        k = left;

        //arr의 왼쪽 절반, 오른쪽 절반을 비교하며 sorted_arr에 채워 넣는다
        while (i <= mid && j <= right) {
                //arr[i] < arr[j] 이면 오름차순   arr[i] > arr[j] 이면 내림차순
                if (arr[i] < arr[j]) 
                        sorted_arr[k++] = arr[i++];
                else
                        sorted_arr[k++] = arr[j++];
        }

        //남아있는 arr의 값을 모두 sorted_arr에 넣는다
        while (i <= mid) {
                sorted_arr[k++] = arr[i++];
        }
        while (j <= right){
                sorted_arr[k++] = arr[j++];
        }
        //sorted_arr의 값을 arr에 복사해준다
        for (int l = left; l <= right; l++) {
                arr[l] = sorted_arr[l];
        }
        int a = 0;
}

void merge_sort(int left, int right) {
        int mid;

        //left가 right보다 작으면 분할
        if (left < right) {
                mid = (left + right) / 2;

                merge_sort(left, mid);
                merge_sort(mid + 1, right);

                merge(left, mid, right);
        }
}




int main() {

        //input : arr = { 9,6,5,8,4,2,3,1,7,0 }
        for (int i = 0; i < MAX_N; i++) printf("%d ", arr[i]);
        printf("\n");
        
        merge_sort(0, MAX_N - 1);
        
        //ouput : arr = { 0,1,2,3,4,5,6,7,8,9 }
        for (int i = 0 ; i < MAX_N ; i++) printf("%d ", arr[i]);
        printf("\n");

}

작성자 리뷰

ABSTRACT

in-domain inputs 이란 주어진 데이터를 뜻합니다. 논문에서는 주어진 데이터 내에서 성능을 높이는 의미를 표현하기 위해 사용되었습니다.
위 그림은 고양이와 강아지를 분류하는 분류기의 예시입니다. 이미지의 input은 pixel의 모든 조합을 space로 가지고 있습니다. ϕ_standard는 고양이와 강아지를 비롯하여 알지 못하는(e.g. 흑백의 노이즈 이미지) 이미지까지 모두 분류를 합니다. 반면 ϕ_activations는 주어진 데이터에만 관심을 가지고 분류합니다.

Quantization

Quantization is the process of constraining an input from a continuous or otherwise large set of values (such as the real numbers) to a discrete set (such as the integers). -wiki-
Quantization은 continuous한 값을 discrete한 set에 맵핑 시키는 과정입니다. 논문에서는 연속적인 값(weight)를 이산적인 집합(codebook)으로 맵핑 한다는 의미로 사용하고 있습니다.

Our Approach

지금부터 어떻게 weight를 quantize 하는 지 살펴보겠습니다. 논문에서는 이해를 돕기 위해 Product Quantization, FC layer에서의 quantization, CNN 에서의 quantization 순으로 설명합니다.

Product Quantization

출처 - https://www.jeremyjordan.me/scaling-nearest-neighbors-search-with-approximate-methods/

Quantization은 차원이 높아질수록 많은 양의 데이터와 많은 양의 centroid를 필요로 합니다.
Product Quantization은 이 문제를 해결하기 위해 vector를 slice하여 낮아진 차원의 subvector들을 quantize 하고 이를 다시 concat하여 사용하는 방법입니다.
위 예시를 보면 8차원의 vector를 2차원의 subvector 4개로 slice합니다. 이 후 각 subvector를 quantize하고 다시 concat 하여 원래 차원의 vector로 복원합니다.
Product Quantization은 적은 수의 데이터와 centroid로도 할 수 있습니다. 만약 vector를 subvector k개로 slice하고 subvector에 centroid가 m개 만큼 있다면, k^m 개 만큼의 vector quantization을 할 수 있습니다.

Quantization of a Fully-Connected layer

FC layer에서의 Quantization입니다. 왼쪽 그림에서 FC layer에 들어가는 input 노드의 개수를 C_in이라 하고, output 노드의 개수를 C_out이라 합니다.
layer의 weight는 두 번째 그림과 같이 C_in * C_out행렬로 표현 할 수 있습니다. 이 때 행렬의 열은 output 하나에 해당하는 weight vector입니다. 이 vector를 Product Quantization 합니다.
만약 d가 2차원이라면, 최종적으로 오른쪽 그림과 같이 표현 됩니다. 그림에서 검은색 점이 subvector들이고 빨간색 x가 centroid 즉 codebook이 됩니다.
이 때 codebook을 구하는 방법은 다음의 두 단계를 반복적으로 진행합니다. 기본적으로 k-means와 같습니다.

• E-step (cluster assignment)
  subvector들을 centroid에 할당하는 단계입니다.

• M-step (codeword update)
  centroid를 업데이트 하는 단계입니다.

다음으로 centroid를 찾기 위한 vector간의 거리(유사도)를 어떻게 정의 하는지 살펴보겠습니다.

• W : 기존 네트워크의 weight vector     W_hat : quantization으로 재구성 된 weight vector
• y : 기존 네트워크의 output                     y_hat : quantization으로 재구성 된 ouput
• x : 네트워크의 input
• w_j : W의 subvector
• q(w_j): quantize된 subvector (할당 된 centroid)

다음 두 수식이 있습니다. 수식을 보기 앞서 논문에서는 weight 자체를 복원하기 보다 output을 잘 나타낼 수 있는 weight를 복원한다고 하였습니다. weight의 차이가 아닌 output의 차이를 거리로 이용합니다. 왼쪽 수식이 weight 자체를 복원하는 식, 오른쪽 수식이 output을 잘 나타낼 수 있는 식입니다.
논문에서는 오른쪽 수식으로 vector간의 거리(유사도)를 결정합니다. 이 때 수식에 input(x) 값이 들어가기 때문에 in-domain에 최적화 된 quantization이 되는게 아닐까 싶습니다.

Convolutional layer

CNN도 FC layer와 동일합니다. 하지만 weight의 차원이 다르기 때문에 reshape이 필요합니다.
가장 왼쪽 그림은 CNN filter를 나타낸 것입니다. input channel이 C_in, output channel이 C_out인 layer의 filter입니다. 논문에서는 quantization을 위해 3차원의 filter를 1차원의 weight vector로 표현하고 subvector로 나누길 원합니다.
filter를 reshape할 때 subvector가 의미를 내포하길 원합니다. 따라서 논문에서는 subvector를 위 그림에서 색으로 칠해진 것과 같이 나누었습니다. 이렇게 나누면 각 input channel의 activation map을 convolve하는 공간적인 의미를 내포하도록 subvector를 표현할 수 있습니다.
subvector의 차원은 kernal size * kernal size가 됩니다.
3차원의 weight를 reshape한 후에 FC-layer에서 한 것과 동일하게 codebook을 찾습니다.

Network Quantization

지금까지 하나의 Layer에 대해서 어떻게 Quantization을 진행하는지 살펴봤습니다. 이를 바탕으로 다층의 Layer가 있는 네트워크를 Quantization 하는 방법입니다.

Learning the codebook

다 층의 Layer 중 하나를 예시로 생각해보면, 이전 Layer의 activation이 현재 Layer의 input이 됩니다. 이전 Layer의 activation을 구하는 방법은 2가지가 있습니다.

• 실제 weight를 통해서 구해진 activation
• quantization 이후에 다시 재구성 한 weight를 통해 구해진 activation

논문에서는 실험적으로 재구성한 weight를 사용 하는 것이 더욱 classification errors를 줄일 수 있다고 합니다.
결국 전체 네트워크의 Quantization은 input layer부터 Quantization을 진행합니다. 즉 재구성된 weight를 통해 나온 activation 값으로 다음 Quantization을 진행하는 sequential한 구조입니다.

Finetuning the codebook

Quantization을 진행한 후 codebook을 finetuning 해줍니다. codebook으로 재구성 된 weight로 만들어진 output(현 Layer를 거쳐 나온 activation)과 기존 네트워크의 output은 유사 해야합니다. 이를 위해 distillation 방법을 차용해 fintuning을 합니다.

• y_s : student network output (Quantization 된 네트워크)
• y_t : teacher network output (기존 네트워크)
• b_p : codeword c 에 속하는 subvector (codeword c로 quantize 되는 subvector)

Global Fintuning

마지막으로, 각 layer에서의 codebook이 완성되고 나면 전체 네트워크에 대해서 fintuning을 다시 진행하게 됩니다. finetuning과정은 위와 동일합니다. 하지만 이 때는 BatchNorm layer도 함께 업데이트 시켜주게 됩니다.

Reference

• https://arxiv.org/pdf/1907.05686.pdf
• https://github.com/facebookresearch/kill-the-bits