Paper: An Empirical Evaluation of Generic Convolutional and Recurrent Networks for sequence Modeling

Author: Shaojie Bai, J. Zico Kolter, Vladlen Koltun

Motivation & Problem Setup

• 현재까지 거의 대부분의 딥러닝 사용자들에게 sequence modeling = rnn처럼 여겨져왔다.

• 그러나, 최근 연구 결과는 cnn으로 audio, machine translation 같은 sequence modeling task에서 rnn을 앞설 수 있다고 말한다. sequence modling의 특정 분야에 국한되어 cnn의 성공적인 성능이 나오는 것인지 혹은 sequence modeling에서 rnn의 독점을 다시 고려해 볼 만한 이슈인지 자세히 알아볼 필요가 있다.

• 이 논문에서는 이를 알아보기 위해 rnn이 우세하게 사용되고 있는 다양한 sequence modeling benchmark에서 cnn과의 체계적인 비교 실험을 진행한다.

• Sequence modeling에서 활용될 수 있는 cnn의 대표 모델 TCN을 제안했음. TCN은 불과 몇 년 전 나왔으며 의도적으로 심플함을 유지함과 동시에 여러 task에서 성공적이었던 cnn 구조를 결합했다.

• 논문에서의 결과는 TCN 아키텍쳐가 다양한 task에서 기존 lstm 같은 recurrent based model을 앞섰고, 또한 longer effective memory(장기 기억 능력)을 입증했다. rnn design에 초점을 맞춘 다양한 benchmark를 포함하고 있는 결과이기 때문에 이는 매우 주목할 만한 성과라고 볼 수 있다.

• 나아가 여러 가지 결과를 잘 해석하기 위해 recurrent network의 기억력 저하 문제에 대해서 더 분석했다. 기존에 rnn에서 이론적으로 입증된 장기 기억 능력에도 불구하고 TCN은 이를 넘는 longer effective memory를 보였다.

• 일반적으로 sequence modeling == rnn에 대한 통념은 다시 생각해 볼 필요가 있다. sequence modeling에서 발휘되는 cnn의 성능을 무시하지 말자.

Method

Overall Architecture of TCN

• TCN은 Causal convolution으로 구성된 아키텍쳐이다. 이는 미래에서부터 과거로의 정보 유출이 없다는 것을 뜻한다. TCN은 기본적으로 1d-dilated causal convolutional network를 사용하는 wavenet에 기반하지만 layer 간의 skip connection을 없애거나 gate activations 등을 없애면서 훨씬 가벼워진 모형이다.

• TCN은 input으로 다양한 길이의 sequence를 받고 이를 동일한 길이의 output sequence로 맵핑시킨다. (RNN과 같은 방식)

Sequence Modeling

• Input sequence: $x_0,...,x_T$를 받아 각 시간에 대응하는 output: $y_0,...,y_T$를 예측하고자 함. 이 때, $y_t$를 예측할 때는 t시점 포함 이전의 input ($x_0,...x_t$)만을 활용한다.

• $f : X^{T+1}\rightarrow Y^{T+1}$의 함수로 sequence modeling network를 표현할 수 있겠다. 이는 $y_t$가 오직 t보다 과거 시점의 input $x_0,...,x_T$에만 의존한다는 causal constraint에 기반한다.

• 예측 값과 실제 값 사이의 오차 $L(y_0,...,y_T, f(x_0,...,x_T))$를 최소화하는 function $f$를 찾는 것이 최종 목표.

Causal Convolution

TCN은 두 가지의 원리에 기반하는데, 우선 network가 input과 동일한 길이의 output을 내놓는다는 것이고 다른 하나는 미래에서 과거로의 정보 유출이 없다는 것이다(causal). 즉 convolution 연산시에 time step t의 output을 내기 위해서는 time t와 그 이전 시점의 원소들과만 convolved 된다는 것이다.

• 첫 번째 특성을 만족시키기 위해서 TCN은 output hidden layer가 input layer와 동일한 길이를 갖는 1D fully-convolutional network(FCN)을 사용한다. 이전 layer와 동일한 길이를 유지하기 위해서는 (kernel size - 1) 만큼의 zero padding이 추가된다. dilation이 추가된다면 zero padding은 (kernel_size-1)*dilation factor

• 두 번째의 causal한 특성을 만족시키기 위해서 TCN은 t시점에서의 convolution 연산이 이전 layer의 t시점과 그 이전의 시점들로만 구성되어 있는 Causal convolution 연산을 사용한다.

TCN = 1D FCN + Causal Convolutions

FCN + Causal Convolutions로만 이루어진 basic design은 긴 길이를 갖는 sequence에서 long effective history를 얻기 위해 매우 깊은 network를 사용하거나 큰 filter size를 사용해야 한다는 단점이 존재한다. 따라서 Dilated convolutions를 사용하게 됨.

Dilated Convolutions

• Receptive Field란 filter가 한 번에 보는 영역. Dilated convolutions는 Receptive Field를 크게 만들면서 연산량의 증가를 가져오지 않는 효과적인 방법.

• Simple한 causal convolution에서는 layer의 깊게 쌓아도 큰 receptive field를 만드는 것에 한계가 있다. 이는 먼 과거에 영향을 받는 sequence 데이터를 다루는 것을 어렵게 만든다. 반면, dilated convolution에서는 layer가 깊어짐에 따라서 receptive field가 지수적으로 증가할 수 있게 만들어준다.

• 1-D sequence input $x \in R^n$, filter $f :\{0,...,k-1\}$에서의
  dilated convolution operation
  $F(s)=(x*_df)(s)=\Sigma_{i=0}^{k-1}f(i)\cdot x_{s-d\cdot i}$
  $s$: sequence, $d$: dilation factor, $k$: filter size

1D Dilated Causal Convolutions example

kernel size=3, sequence length=10, dilation factor=2에서의 TCN 연산 예시. (Dilated causal convolution)

• TCN의 receptive field를 늘리는 방법이 두 가지 있다. 우선 첫 번째로 filter size k를 늘리고, dilation factor d를 증가시킴으로써 receptive field를 늘릴 수 있다. 예를 들어 충분히 큰 filter size k와 dilation factor d를 설정하였다면, 하나의 layer만으로도 (k-1)*d의 receptive field를 확보하게 되는 것. 두 번째로는 network의 깊이를 깊게 쌓는 것인데 보통 dilation factor d를 layer의 깊이에 맞춰 지수적($2^i,$ i: depth of network)으로 증가하는 형식을 많이 사용한다.

• receptive field를 늘리는 것은 아주 오래전의 과거에 영향을 받는 sequence data의 특성을 잘 반영하게 해주고 예측 성능을 높일 수 있는 방법이다. - large effective history

Residual Connections

• $o=Activation(x+F(x))$

• Residual connection은 이미 깊은 network에서의 degradation 문제를 해결하며 좋은 성능을 보여왔음.

• TCN에서는 특히 receptive field의 확보를 위해 network의 깊이, filter size, dilation factor에 의존하고 있으므로 모델 사이즈가 커지는 것은 불가피하다. 따라서 깊은 layer의 network에서 학습 안정화는 중요한 포인트이다.

• TCN Residual Block에서는 input과 output이 다른 channel 개수를 갖고 있을 수 있다. 따라서 추가적으로 1*1 convolution을 적용함으로써 output과 더해지는 input의 channel size를 맞출 수 있다.

Discussion

Advantages

• Parallelism: RNN 계열의 모델들과 다르게 병렬화 가능

• Flexible receptive field size: TCN에서는 dilated conv layer를 깊게 쌓거나, 큰 dilation factor를 사용하거나, filter size의 크기를 늘리는 방식으로 receptive field의 사이즈를 조절하는 것이 가능하다. 이는 자유롭게 모델의 메모리 사이즈 조절 및 도메인 별 설정을 유연하게 가져갈 수 있다.

• Stable gradients: TCN에서는 sequence의 temporal한 방향과는 다르게 backpropagation이 이루어진다. 따라서 rnn계열의 모델에서 흔히 발생하는 gradient vanishing이나 gradient exploding현상을 피할 수 있다.

• Low memory requirement for training: Sequence의 길이가 길 때, lstm이나 gru모델에서는 다수의 cell gate 속에 많은 정보들을 저장하게 된다. 하지만 TCN의 경우 같은 layer에서 weight filter들끼리 가중치를 공유하기 때문에 메모리 사용을 절약할 수 있다.

• Variable length inputs: RNN과 동일하게 모델이 다양한 길이의 input을 받을 수 있다. 이는 TCN이 sequence를 sliding하며 1D convolution을 적용하기 때문임.

Disadvantages

• Data storage during evaluation: RNN계열의 모델들은 t+1시점의 예측을 수행할 때, t시점의 input과 hidden, cell state만 유지하면 된다. t시점 이전의 sequence input들은 더이상 유의미하지 않기 때문에 처분함으로써 메모리 효율을 높일 수 있다. 하지만, TCN은 예측 수행시에도 전체 raw sequence가 연산에 활용되므로 메모리 사용이 요구된다.

• Potential parameter change for a transfer of domain: TCN의 receptive field의 크기는 k와 d의 값으로 결정된다. 만약 작은 k와 d값의 TCN으로 학습된 모델이 다른 도메인에 전이되어 학습(transfer learning)된다고 할 때, 충분한 receptive field를 반영하지 못해 성능이 좋지 않을 수도 있다. 즉, 얼마나 먼 시점의 과거로부터 영향을 받는 sequence 데이터인지에 따라서 모델의 가용 범위가 결정된다.

Experiment

Dataset

• The adding problem
  
  길이 n의 sequence 데이터인데 2개의 차원을 가짐. 첫 번째 dimension 벡터는 0~1사이의 값을 갖는 random value. 두 번째 dimension의 벡터에서는 두 개의 원소를 제외하고는 전부 0. 목적은 두 번째 차원의 벡터에서 1로 지정된 위치의 random value의 합을 구하는 것으로 설정.

• Sequential MNIST and P-MNIST
  
  Sequential MNIST는 RNN이 먼 과거의 정보를 기억하는 정도를 측정하기 위해서 많이 사용된 benchmark이다. MNIST는 flatten되어 784길이의 sequence가 되고 0부터 9까지의 숫자를 맞추는 classification문제가 된다. P-MNIST는 sequence가 랜덤하게 섞인 것으로 더 어려운 과제임.

• Copy memory
  
  Input sequence는 T+20의 길이를 갖는다. 첫 번째 10개의 값은 1~8사이의 값으로 랜덤하게 지정되고 마지막 11개의 값은 9로 채워지는데 첫 번째 9의 위치는 delimiter 역할을 하게됨. 그리고 나머지 모든 원소들은 0으로 채워진다. 우선 이 benchmark 실험에서는 input과 같은 길이의 output을 생성한다. 이 때, 모델은 delimiter 위치까지의 모든 원소를 0으로 만들고 delimiter 이후 10개의 값으로 input의 처음 10개 원소 (1~8사이의 랜덤 값)를 맞추어야 한다.

• JSB Chorales and Nottingham: polyphonic music dataset

• PennTreebank: text dataset

• Wikitext-103: text dataset

• LAMBADA: text dataset

• text8: text dataset

Experimental Setup

• RNN 모델의 홈구장같은 곳에서(주로 RNN이 실험되는 benchmark) TCN과 RNN의 성능을 비교 실험. 여러 도메인의 real data와 synthetic data를 포괄적으로 활용.

• TCN에서 network depth $n$, kernel size $k$를 달리하여 여러가지 버전으로 실험. exponential dilation $d=2^i$ ($i$: network depth)

• Grid search for training RNN, network 사이즈는 TCN과 거의 동일하게 설정.

• Gating mechanism, skip connection과 같은 정교한 아키텍쳐 작업은 RNN, TCN 모두 추가되지 않음. (vanilla model)

Result

• The adding problem
  
  problem size 200, 600에서 실험되었고 모든 모델은 대략 70K의 파라미터 사이즈를 갖는다. 결과를 보면 TCN의 수렴이 가장 빠르고 GRU도 TCN보다 수렴속도는 느리지만 괜찮은 성능이다. 반면, LSTM과 RNN은 problem size 600세팅에서 loss가 수렴하지 않는 모습.

• Sequential MNIST and P-MNIST
  
  TCN이 수렴 속도와 최종 accuracy에서 RNN 계열의 모델들을 압도적으로 앞섬.

• Copy memory
  
  해당 task에서 두각을 나타낸 RNN계열의 모델 EURNN을 추가적으로 넣어서 실험. T=500 실험에서는 두 모델이 거의 비슷한 수렴 속도를 보였지만, T=1000 실험에서 TCN이 조금 앞선다. (loss와 수렴비율 모두)

• Memory Size of TCN, RNN
  
  무한한 길이의 sequence에서 RNN과 TCN의 기억 보유 능력을 실험하기 위해서 다양한 T(sequence length)에서의 copy memory task 정확도를 측정했다. TCN과 RNN모두 parameter size 10K에서 실험했다. 위의 결과를 보면 T의 길이가 250이 될 때까지 TCN은 test 정확도 100%에 수렴한다. 이는 RNN 비교실험 모델보다 TCN이 더 긴 유효한 기억 능력을 갖고 있다는 것을 입증한다.

Implementation

Model

class Chomp1d(nn.Module):
    def __init__(self, chomp_size):
        super(Chomp1d, self).__init__()
        # chomp_size(padding size): (kernel_size-1) * dilation_size 
        self.chomp_size = chomp_size  

    def forward(self, x):
        # output: (N, C_in, L_in - chomp_size)
        return x[:, :, :-self.chomp_size].contiguous()


class TemporalBlock(nn.Module):
    def __init__(self, n_inputs, n_outputs, kernel_size, stride, dilation, padding, dropout=0.2):
        super(TemporalBlock, self).__init__()
        #--------------------- Dilated Causal Convolution --------------------- 
        '''
        input: (N, C_in, L_in) -> (N, C_out, L_in)
        output sequence의 길이는 변하지 않는다. 
        '''
        self.conv1 = weight_norm(nn.Conv1d(n_inputs, n_outputs, kernel_size,
                                           stride=stride, padding=padding, dilation=dilation))
        self.chomp1 = Chomp1d(padding)
        #----------------------------------------------------------------------
        self.relu1 = nn.ReLU()
        self.dropout1 = nn.Dropout(dropout)

        #--------------------- Dilated Causal Convolution --------------------- 
        '''
        input: (N, C_in, L_in) -> output: (N, C_out, L_in)
        output sequence의 길이는 변하지 않는다. 
        '''
        self.conv2 = weight_norm(nn.Conv1d(n_outputs, n_outputs, kernel_size,
                                           stride=stride, padding=padding, dilation=dilation))
        self.chomp2 = Chomp1d(padding)
        #----------------------------------------------------------------------
        self.relu2 = nn.ReLU()
        self.dropout2 = nn.Dropout(dropout)
        
        # Dilated Causal Conv -> WeightedNorm -> ReLU -> Dropout -> ... (논문의 Residual block 구조와 동일)
        self.net = nn.Sequential(self.conv1, self.chomp1, self.relu1, self.dropout1,
                                 self.conv2, self.chomp2, self.relu2, self.dropout2)
        
        # Residual Connections 
        '''  
        만약 Dilated Causal Conv를 적용하기 전의 input channel과 적용한 후의 
        output channel이 달라질 경우를 대비하여 추가적인 1*1 convolution을 추가해줌.

        input: (N, C_in, L_in) -> output: (N, C_out, L_in)
        output sequence의 길이는 변하지 않는다. (1*1 convolution)
        '''  
        self.downsample = nn.Conv1d(n_inputs, n_outputs, 1) if n_inputs != n_outputs else None
        self.relu = nn.ReLU()
        self.init_weights()

    def init_weights(self):
        self.conv1.weight.data.normal_(0, 0.01)
        self.conv2.weight.data.normal_(0, 0.01)
        if self.downsample is not None:
            self.downsample.weight.data.normal_(0, 0.01)

    def forward(self, x):
        out = self.net(x)
        res = x if self.downsample is None else self.downsample(x)
        return self.relu(out + res)


class TemporalConvNet(nn.Module):
    def __init__(self, num_inputs, num_channels, kernel_size=2, dropout=0.2):
        super(TemporalConvNet, self).__init__()
        layers = []
        num_levels = len(num_channels)
        for i in range(num_levels):
            # dilation factor는 layer의 깊이에 지수적으로 증가 (2^i, i: layer depth) 
            dilation_size = 2 ** i 
            in_channels = num_inputs if i == 0 else num_channels[i-1]
            out_channels = num_channels[i]
            # 설정된 layer의 깊이만큼 TemporalBlock 생성 
            layers += [TemporalBlock(in_channels, out_channels, kernel_size, stride=1, dilation=dilation_size,
                                     padding=(kernel_size-1) * dilation_size, dropout=dropout)]

        self.network = nn.Sequential(*layers)

    def forward(self, x):
        return self.network(x)


class TCN(nn.Module):
    def __init__(self, input_size, output_size, num_channels, kernel_size, dropout):
        super(TCN, self).__init__()
        self.tcn = TemporalConvNet(input_size, num_channels, kernel_size=kernel_size, dropout=dropout)
        self.linear = nn.Linear(num_channels[-1], output_size)

    def forward(self, inputs):
        """
        Inputs have to have dimension (N, C_in, L_in)
        Flatten된 MNIST의 경우에는 (batch_size, 1, 784)
        """
        y1 = self.tcn(inputs)  # input should have dimension (N, C, L)
        o = self.linear(y1[:, :, -1]) # sequence의 마지막 time step로 linear계산 -> 분류예측
        return F.log_softmax(o, dim=1)

Train / Test

def train(ep):
    global steps
    train_loss = 0
    model.train()

    loss_lst = []
    for batch_idx, (data, target) in enumerate(train_loader):
        if cuda: data, target = data.cuda(), target.cuda()
        data = data.view(-1, input_channels, seq_length)
        if permute:
            data = data[:, :, permute]
        optimizer.zero_grad()
        output = model(data)
        loss = F.nll_loss(output, target)
        loss.backward()
        if clip > 0:
            torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
        optimizer.step()
        train_loss += loss
        steps += seq_length
        loss_lst.append(train_loss.item()/log_interval)
        if batch_idx > 0 and batch_idx % log_interval == 0:
            print('Train Epoch: {} [{}/{} ({:.0f}%)]\tLoss: {:.6f}\tSteps: {}'.format(
                ep, batch_idx * batch_size, len(train_loader.dataset),
                100. * batch_idx / len(train_loader), train_loss.item()/log_interval, steps))
            train_loss = 0

    return np.mean(loss_lst)


def test():
    model.eval()
    test_loss = 0
    correct = 0
    with torch.no_grad():
        for data, target in test_loader:
            if cuda:
                data, target = data.cuda(), target.cuda()
            data = data.view(-1, input_channels, seq_length)
            if permute:
                data = data[:, :, permute]
            output = model(data)
            test_loss += F.nll_loss(output, target, size_average=False).item()
            pred = output.data.max(1, keepdim=True)[1]
            correct += pred.eq(target.data.view_as(pred)).cpu().sum()

        test_loss /= len(test_loader.dataset)
        print('\nTest set: Average loss: {:.4f}, Accuracy: {}/{} ({:.0f}%)\n'.format(
            test_loss, correct, len(test_loader.dataset),
            100. * correct / len(test_loader.dataset)))
        return test_loss

# 학습 진행 
train_hist = np.zeros(epochs)
test_hist = np.zeros(epochs)

for epoch in range(1, epochs+1):
    train_loss = train(epoch)
    test_loss = test()
    train_hist[epoch] = train_loss
    test_hist[epoch] = test_loss

    if epoch % 10 == 0:
        lr /= 10
        for param_group in optimizer.param_groups:
            param_group['lr'] = lr

Result - Sequence MNIST

10 epoch만 학습을 해도 MNIST 분류 테스트 정확도 99%에 도달한다.

Reference

Keras TCN

TCN Github

TCN 참고 자료

DSBA연구실 TCN 강의

Paper-An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling

1-D Convolution

1-D Convolution

1-D Convolution