Lecture 2

• Generalization
• Speed of Convergence for Training and Learning quality

Performance Generalization

Neural network는 두 가지 중요한 점을 충족시켜야 한다.

1. training data를 통해서 학습하기 때문에, training data에 대해서는 정확하게 분류해야 한다.
2. learning process에 대해서 generalize하기 위해서 이전에 보지 못한 데이터(test data)에 대해서도 잘 분류해야 한다.

복잡한 결정 경계선(면)을 가지고 있다고 해서 이 것이 좋은 generalization performance를 가지고 있다고 하지 않는다.

실험 과정에서는 다음과 같이 진행된다.

1. data set을 Learning set(85%)과 test set(15%)으로 구분한다.
2. Learning set을 training set(70%)와 validation set(15%)로 구분을 한다.
3. training set으로 network을 훈련을 하고, training set과 validation set으로 성능을 평가한다.

만약 training error가 높다면 underfitting이 발생한 것이고, training error가 낮지만 validation error가 높으면 overfitting, 둘 다 낮은 수치가 나온다면 generalization이 잘 일어난 것을 의미한다.

위에서 했던 것에서 더 발전시켜서 3번을 서로 다른 구조로 진행한다.

4. 3번의 여러 구조에서 over and underfit이 아닌 best network을 고른다.
   • 다른 model인 것이 아니라 parameter tuning을 하는 것
5. 이를 learning set으로 다시 훈련을 한다.
6. test set으로 generalization을 테스트 한다.

• three subset을 바꿔가면서 N번 반복하는 것을 N-fold cross validation protocol이라고 한다.
• 하지만 각 parameter별로 best value가 다르다면...?

Parameter search

1. training set으로 다른 parameter들을 train하고, validation으로 평가한다.
2. 각 parameter에 대해서 error_val을 기록한다.
3. training set과 validation set을 reshuffle을 해서 1과 2를 반복한다.
4. 3번을 n times 반복한다.(n-fold CV)
5. n-fold로 부터 얻은 error_val 평균내고, 작은 평균 error_val을 가진 것들을 모아서 best parameter set을 만든다.

• Parameter searching 전략에는 다음 두 가지가 있다.
  • Grid Search
    • q개의 파라미터가 있고, 각 파라미터당 p개의 value가 생긴다면 이 경우에 대해서 모두 탐색하는 것을 의미한다.
    • mp^q개다.
  • Random Search
    • parameter value들을 random combination으로 진행한다.
    • grid search보다 좋은 점은 each parameter마다 unique한 value를 얻을 수 있기 때문에 좋다??

Generalization

generalization을 위해서 적절한 모델을 고르는 것도 중요하지만 다른 방법들에는 어떠한 것이 있을 까?

1. Enrich Training data

적은 데이터를 가지고 있으면, 모델은 쉽게 수렴할 수 있다.(small training error) 적은 데이터를 모델이 전부 외어버린다고 생각하면 된다. 하지만 절대적인 정보의 양이 부족하기 때문에 나쁜 generalization을 가진다.(large training error)

거대한 데이터라면 모델이 이를 학습하기 위해서 더 많은 노력을 해야 한다. (higher training error) 대신 정보의 양이 충분해졌기 때문에 더 좋은 generalization 성능을 가질 것이다.(lower test error)

즉, 질이 좋고 많은 양의 데이터를 사용해야 overfitting을 방지할 수 있다. 하지만, 이러한 데이터를 구하는 것은 많은 비용이 들고, 힘들다.

그래서 인공적으로 training data를 늘리는 방법을 사용하는데, 이를 Data augmentation이라고 부른다. (translation, rotation, stretching, shearing, lens distortions...)

2. Early stopping

훈련을 진행할 때, 언제 멈추는 것이 좋을까? 훈련을 계속해서 진행을 한다면 zero training error를 달성할 수 있을 것이다. 하지만 이는 train data에 overfitting 된 상태이기 때문에 test error는 매우 높을 것이다. 따라서 validation error를 기준으로 early stopping 할 포인트를 구한다.

3. Ensemble

여러 Network를 동시에 훈련을 시키고, 이들의 average를 사용하는 방법이다.

4. Regularization

network의 complexity를 줄이는 방법이다.

• L2(weight decay)

  

  • 각각의 벡터에 대해 항상 unique한 값을 반환

• L1

  

  • 특정 feature가 없어도 같은 값을 반환
  • feature selection이 가능하다.
  • Sparse model이 적합하다.
  • 미분 불가능한 점이 있기 때문에 gradient에 주의해야 한다.

• Max norm constraints

  • weight vector에 upper bound를 설정하는 것이다. (미분값도 제한된다.)
  • learning_rate를 크게 잡더라도 explode 하지 않는다.

• Dropout

  • 위에서 소개한 정규화 방법들과 같이 사용할 수 있다. random 하게 hidden node와 input node를 제거하고(off하고) 이들은 weight를 업데이트 하지 않는다.
  • 이는 training 과정에서만 적용되고, prediction에서는 dropout을 사용하지 않는다.

Speed of Convergence

• batch training
• Momentum term
• weight initialization
• learning rate
• activation functions
• feature normalization and scaling
• batch normalization(BN)

일반적인 BP(backpropagation)은 saddle point나 local minimum에 약하다는 단점이 있다.

• momentum term
  • gradient update에 관성을 부여한다는 아이디어다.
  • 기존 BP는 다음 식에 따라서 업데이트 된다.

    • 

  • momemtum term은 이전 weight update 한 값을 일부 제해서 더해준다.

    • 

    • a가 0이라면 일반적인 backpropagation과 동일하다.
    • a가 1이라면 gradient descent는 완전히 무시되고, mometum에 의해서만 업데이트 된다.
    • 보통 0.9나 0.95를 많이 사용한다.
• weight Initialization
  • 초기에 weight를 어떻게 init하는지에 따라서 성능이 바뀐다. 적절한 값을 사용해야 한다.
  • Xavier Initialization을 사용한다.
• Learning rate
  • 적절한 learning rate를 골라야 한다.
    • 너무 작게 고르면 늦게 수렴할 수 있다.
    • 너무 크게 고르면 발산 할 수 있다.
  • Adagrad, RMSprop, ADAM, ...
• Activation function
  • simoid나 tanh같은 경우에는 미분값을 자주 곱할수록 작아지기 때문에 gradient vanishing 문제가 발생한다.
  • 따라서 ReLU를 사용한다.
    • 장점
      • simple하고, positive region에서는 stable하다.
      • 수렴속도도 따르다.
      • sparsifcaiton을 허용한다.
    • 단점
      • gradient가 0보다 작은 값이 많다면 Dying 할수도 있다.
        • Leaky ReLU, Parametric ReLU와 같은 걸로 해결 가능
• Feature Normalization
  • 각 feature들의 range가 다르기 때문에 normalization을 수행한다.
  • Max-min normalization
  • Z score normalization
  • PCA - large dataset에는 부적합
• Batch Normalization (BN)
  • 각 layer마다 input의 distribution이 달라지는 것을 막기 위함이다.
  • pre-activation, post-activation에 각각 normalizing을 수행한다.
  • 이는 mini-batch 단위로 수행히 가능하고, 각각 독립적으로 수행할 수 있다.
  • prediction을 위해서는 re-adjust해야 하고, r과 b도 알아야 한다.
  • 장점
    • high learning rate가 가능하다.
    • deep network에 사용 가능하다.
    • weight init에 민감하지 않다.
  • 단점
    • Batch number가 커야 한다.
    • dynamic network 구조나 recurrent network에 적합하지 않다.

Summary

• good convergence를 가장 우선적으로 생각해야 하지만 good generalization을 보장하진 않는다.
• convergence의 속도를 향상시키기 위해서 여러 방법들을 사용할 수 있다.

문제:

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력:

이 문제는 입력이 없다.

출력:

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이방법:

 조건이 맞는 a,b,c,d를 찾는 것은 쉬우나 시간을 줄이는 것이 이 문제의 핵심이다. a 같은 경우에는 6이 가장 같은 경우의 수 이기 때문에 6부터 시작하게 한다. 그리고 1보다 큰 자연수여야 하기 때문에 b는 2부터, b<c<d를 만족해야하기 때문에 c는 b부터, d는 c부터 시작하게 하도록 한다.

문제링크:

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

Aspect Based Sentiment Analysis with Gated Convolutional Networks

• Aspect Based Sentiment Analysis(ABSA)은 일반 Sentiment analysis보다 더 정교한 정보를 제공한다.
  • 텍스트의 주어진 aspect나 entities의 sentiment 특성을 예측하는데 도움을 주기 때문
• ABSA는 크게 두 가지로 나뉜다.
  • Aspect Category Sentiment Analysis (ACSA)
  • Aspect-term Sentiment analysis (ATSA)
• 이전에는 LSTM과 attention을 사용해서 이 문제를 주로 해결했다.
  • 하지만 시간이 많이 필요하고 많이 복잡하다.
  • 따라서 위 문제를 해결할 수 있는 Gated Mechanism을 가지고 있는 CNN 모델을 제안한다.
• 장점 1 : Gated Tanh-ReLU는 주어진 aspect나 entity에 따라 sentiment feature를 선택적으로 출력한다.
• 장점 2 : 기존 모델들보다 더 간단하다.(attention을 가진 모델들에 비해)
• 장점 3 : LSTM 모델과 달리 시간에 종속적이지 않기 때문에 병렬적으로 훈련 가능
• SemEval 데이터셋으로 효과적임을 입증함

1. Introduction

Opinion mining 이나 Sentiment Analysis는 소비자와 생산자에게 가치있는 정보를 제공한다.

전체적인 Sentiment를 예측하는 것보다 review를 이해하는데 ABSA를 사용한다. 특히 text의 aspect categories와 target entities에 관심이 있다.

• Aspect Category Sentiment Analysis(ACSA)

  사전에 정해진 categories 중 하나에서 aspect를 예측

• Aspect-Term Sentiment Analysis(ATSA)

  text에서 나타나는 target entities 특성을 식별하는 것인데, 다중 단어 구 혹은 단일 단어일 수 있다.

"Average to good Thai food, but terrible delivery" 라는 문장이 있을 때, ATSA는 Thai food entity에 집중해서 특성을 찾아내고, ACSA는 문장에서 service라는 문장이 없어도 service의 관점에서 특성을 분석한다.

기존의 모델들은 LSTM이나 Attention을 사용했다. 하지만 이들은 더 높은 정확도를 얻기 위해서는 더 많은 분석이 필요하고 더 많은 훈련간을 요구한다. 따라서 gated mechanism을 가지고 있는 CNN을 제안한다.

ACSA task에선 embedding layer 다음에 두 개의 분리된 CNN layer가 있다. multiple filter를 가지고 있는 CNN은 각 receptive field의 많은 granularities에서 n-gram 특징을 효과적으로 추출할 수 있다.

제안하는 gating unit은 두 개의 nonlinear을 가지고 있고, 각각은 하나의 convolutional layer로 연결되어 있다.

aspect 정보가 주어지면 모델은 선택적으로 aspect-specific 정보를 추출한다.

"Average to good Thai food, but terrible delivery" 와 'food' aspect가 주어지면 gating unit은 자동으로 두번째 문장에 있는' delivery'의 부정적인 것을 무시하고 첫번째 문장만을 보고 긍정적으로 예측한다.

여러 단어로 구성된 aspect term인 ATSA에서는 target experssion을 위해서 다른 convolution layer를 모델에 추가한다.

2. Related Work

2.1 Neural Networks

pass

2.2 Aspect based Sentiment Analysis

pass

3. Gated Convolutional Network with Aspect Embedding

더 효율적이고 간단한 Gated Convolutional network with Aspect Embedding (GCAE)를 제안한다. 각 convolutional filter는 각 위치에서의 임베딩 벡터로부터의 다른 세분화에서 n-gram feature를 계산한다.

각 위치에서 convolutional layer에 있는 gating unit은 서로 독립적으로 있다. 그러므로 parallel computing에 더 적합하다.

게다가, 모델은 두 개의 효과적인 filtering mechanism을 가지고 있다.

1. gating unit
2. max pooling layer

이 둘은 모두 정확한 생성과 aspect-related sentiment feature를 선택하도록 한다.

CNN에 대한 설명

CNN model은 text classification에서 좋은 성능을 보이고 있다.

CNN은 embedding layer, 1차원의 convolutional layer와 max-pooling layer로 구성되어 있다.

embedding layer는 단어 w_i {i=1,...,V}들을 입력으로 받아서 그에 상응하는 embedding vector v_i를 반환한다. 이 때, V는 word vocabulary의 크기다. embedding layer는 주로 GloVe와 같은 pre-trained embedding으로 초기화되며, training stage에서 fine-tuned된다.

1차원 convolutional layer는 여러 개의 서로 다른 width를 가지고 있는 kernel을 가지고 있다. Each kernel corresponds a linguistic feature detector which extracts a specific pattern of n-gram at various granularities

전체 sentence를 filter로 slide하고 나면 새로운 feature c를 얻게 된다.

max-pooling layer를 통해 가장 큰 값을 선택한 후 최종적으로 softmax layer를 사용해 sentiment polarity를 예측한다.

위 그림은 모델의 구조를 그린 그림이다. Gated Tanh-ReLU Units(GTRU)에서 두 개의 convolutional neurons와 aspect embedding와 연결된다.각 feature들은 다음과 같이 계산된다.

그 다음은 보통 CNN에서 하는 작용들에 대한 설명

4. Gating Mechanisms

GTRU는 pooling layer로 향하는 sentiment 정보들을 조절해준다. 이러한 gating mechanism은 LSTM에서 효과적임이 증명되었다. aspect based sentiment analysis에서 하나의 문장에서 서로 다른 sentiment를 가지고 있는 aspect가 나타나는 것은 흔한 일이다. ReLU로 인해 양수값은 제한이 없지만 음수는 제한이 생긴다. 그러므로 이를 주어진 aspect information과 aspect feature 사이의 유사도라고 할 수 있다. 만약 0이라면 sentiment feature들은 gate에서 block 되고, 그렇지 않다면 증폭될 것이다.

GTU와 GLU의 모델이 있지만 GTRU가 이 두개보다 좋음

5. GCAE on ATSA

ATSA는 주어진 문장에서 aspect term의 sentiment 특성을 예측하는 것이다. 따라서 GCAE에 aspect term에 수행하는 작은 convolution layer를 추가적으로 사용한다.

위 그림에서 ACSA 같은 경우에는 aspect가 하나의 단어로 구성되어 있지만 ATSA는 여러 단어로 구성되어 있기 때문에 작은 CNN을 통해서 정보를 공급받는다.

이 추가적인 CNN은 parallel computing을 사용하여 중요한 특징들을 뽑아낸다.

6. Experiments

6.1 Datasets and Experiment Preparation

본 연구에서는 restaurant와 laptop의 customer review로 구성되어 있는 SemEval workshop 공공 데이터 셋으로 실험을 진행한다. 몇몇 선행 연구에서는 4개의 sentiment label에서 "conflict"를 제거하여 진행을 했고, 따라서 workshop report와 비교를 할 수 없다. 그래서 그들의 것을 구현해서 만들어냈다.

문장에서 서로 다른 aspect와 target에 대해 서로 다른 sentiment label을 가지고 있는 문장이 일반 benchmark보다 더 많다. 그래서 더 정확하게 수행하기 위해서 서로 다른 sentiment나 aspect를 가지고 있는 문장으로 구성된 작지만 어려운 데이터셋을 만든다. 따라서 같은 한 문장이 데이터셋에 서로 다른 sentiment를 가진채로 포함되어 있을 수 있다. 즉, 문장이 4개의 aspect target을 가지고 있으면 한 문장이 4개로 복사되어 데이터셋에 포함되어 있다.

• SemEval 2014 Task 4 in ACSA

  • 5 aspect : food, price, service, ambience, misc
  • 4 sentiment polarities : positive, negative, neutral and conflict
  • 2014-2016 사이의 음식점 리뷰
  • 이를 Restaurant-Large라고 부름
  • 2014 데이터셋에서는 conflict를 neutral로 대체를 함
  • 2015-2016 데이터셋에서는 aspect terms과 aspect category를 가지고 있는 복수의 쌍이 있을 수 있음
  • p > 0 이면 긍정, p < 0 이면 부정, p = 0 이면 중립

• SemEval 2014 Task 4(restaurant, laptop)

  • 중복하게 만듦

• hard dataset은 모델이 한 문장에서 복수의 다른 sentiment polarities를 찾을 수 있는지 테스트 한다. 일반적인 문장들 같은 경우는 잘 분류할 것이다.

6.2 Compared Methods

pass

6.3 Results and Analysis

6.3.1 ACSA

test dataset과 hard test dataset에 대해서 정확도를 측정하였으며, 5번 실행해서 평균과 분산을 기록했다.

LSTM 기반 모델 ATAE-LSTM은 모든 neural-net 중에서 가장 낮은 성능을 보였다.

ABSA는 주어진 aspect와 유사하게 감성 정보를 추출해야 한다. 문장의 추출된 정보로부터 aspect information과 sentiment information을 분리하는게 중요하다. LSTM으로 생성된 context vector는 동시에 두 정보를 수행하고, attention score는 전체 context vector에 대해 수행한다.

GCAE는 ATAE-LSTM은 1.1~2.5%의 성능향상을 보인다.

우선, 본 모형은 GTRU를 가지고 있어서 주어진 aspect에 따라 sentiment information flow를 조절한다. Element-wise gating mechanism은 attention에서 alignment score를 사용하는 대신 미세한 세분화로 사용한다.

두번째로, GCAE는 single context vector를 생성하지 않고, aspect sentiment 특징을 생성한다. hard dataset에서 CNN과 성능 비교를 함으로써, GCAE의 convolution layer가 sentiment의 multiple entities를 세분화하는 것을 보인다.

CNN과 GCN은 ABSA로 디자인되어 있지 않지만 ATAE-LSTM보다 좋음

SVM은 사용할 수 있는 feature의 가용성에 의존. 충분한 양의 sentiment lexicons가 없다면, SVM은 성능이 좋지 못함. 따라서 neural networks에서 leveraging sentiment lexicon을 하는 것은 추후 연구.

hard test 데이터셋은 서로 다른 aspect에 따른 sentiment를 가진 중복의 문장들로 구성되어 있다. CNN과 GCN은 기대했던 것보다 성능이 좋지 못했고, GCAE는 더 높은 성능을 기록했다.

6.3.2 ATSA

ATSA에서는 GCAE의 확장된 버전을 적용한다. 문장에 marked된 aspect term은 multiple 단어로 구성되어 있다. GCAE를 제외하고 다른 모델들은 LSTM 기반이다.

물론 제일 좋은 성능을 가지고 있음

6.4 Training Time

ATSA task에서 가장 빠른 수렴을 보임

6.5 Gating Mechanisms

Gating Mechanisms들의 성능 비교 GTU vs GLU vs GTRU

7. Visualization

pass

8. Conclusions and Future Work

How to leverage large-scale sentiment lexicons in neural networks would be our future work.

문제:

유진이가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.

이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.

예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다

랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다. 그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 송유진의 새로운 점수가 주어진다. 이때, 송유진의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그램을 작성하시오. 만약 점수가 랭킹 리스트에 올라갈 수 없을 정도로 낮다면 -1을 출력한다.

만약, 랭킹 리스트가 꽉 차있을 때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다. (예제 2)

입력:

첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보다 작거나 같은 자연수 또는 0이다. 둘째 줄에는 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다. 둘째 줄은 N이 0보다 큰 경우에만 주어진다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 기존에 있던 중복된 숫자가 있을 수 있는데, 이를 새로 들어오는 숫자와 구분을 할 수 있어야 하는 문제다. 이를 구분하기 위해서 기존에 있던 숫자들에게 인덱스를 부여했으며, 새로 들어오는 숫자는 가장 큰 인덱스를 가지도록 하게 한다. 이렇게 하면 새로 들어오는 숫자가 기존에 있던 점수와 동일한 것이 있으면 그 뒤에 배치되게 된다.

 새로 정렬을 마친 뒤에 앞에서부터 P개 자르고, (새로 들어온 숫자, 인덱스)가 그 배열에 있다면 등수를 찾아 출력을 하고, 그렇지 않다면 -1을 출력하게 한다.

 또한 N이 0일 경우도 존재하게 되는데, 이 때는 두번째 줄을 입력받지 않아야 한다. 따라서 따로 예외처리를 해주어 빈 리스트를 정의하게 하도록 한다.

문제링크:

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

Lecture1

• Multiple Layer Perceptron(MLP)
• Loss Function
  • Mean Square Error
• Backpropagation Algorithms
  • Stochastic Gradient Descent(SGD)
  • Batch Gradient Descent(BGD)
  • Mini-batch GD

Multiple Layer Perceptron

하나의 Neuron은 이전 Neuron들의 값과 weight 간의 곱의 합들을 구한 뒤 activation function인 f를 통과해서 y를 만들어 낸다.

layer들은 이러한 Neuron들을 여러 개 가지고 있는 것을 의미하고, 이러한 layer가 여러 개 존재한다면 이를 Multiple Layer Perceptron(MLP)라고 부른다.

Input layer는 x_i 만큼의 입력값이 존재하고, Hidden Layer가 앞서 말한 연산을 수행한다. Output Layer는 하나의 값을 계산하기 때문에 하나의 Neuron이 존재한다.

Activation function

각 hidden node에 적용되는 activation function은 다음과 같은 것들이 있고, 이들의 대한 설명은 다음에 기회가 있으면 하도록 한다.

• Sigmoid Function
• 
• Hyperbolic Tangent
• 
• Rectifier Linear(ReLU)
• 

Usage

MLP는 Classification, Regression 등에서 사용될 수 있다.

Loss Function For MLPs

Loss Function은 참값과 예측값과의 차이를 의미하기 때문에 MLP에서 Supervised Learning 학습 방법에서 나타난다.

그림으로 프로세스를 보면 다음과 같이 설명할 수 있다.

In Regression

MLP의 output layer에서 Linear function을 사용한다. loss function은 각 output error의 square들의 합으로 구성된다. 이를 Mean Square Error(MSE)라고 부르고, 식으로 표현하면 다음과 같다.

In Classification

MLP의 output layer에서 Softmax function을 사용한다. softmax는 Hard max function과는 다르게 exp()함수를 사용하는데, 그 이유는 더 큰 logit을 가지고 있는 값에 더 큰 값을 부여하기 위함이다. Loss function은 Average Cross-Entropy (ACE) loss를 사용한다.

t_i는 true label, f(s)_i는 softmax output을 의미한다.

Backpropagation

Gradient Descent는 weight를 기울기 반대 방향으로 업데이트 하면서 Optimal weight를 찾아가는 과정이다. 이 때 기울기 반대 방향으로 업데이트 할 때, learning rate를 적절한 값으로 설정해야 한다. 만약 너무 learning rate가 작다면 local minimum에 빠질 수 있고, 훈련속도가 너무 느릴 수 있다. 하지만 크다면 shooting이 발생할 수 있어 발산할 수도 있다.

역전파 하는 과정을 그림과 함께 보면 다음과 같이 표현할 수 있다.

위 그림과 같은 간단한 Two-Hidden layers MLP가 존재한다고 하자. 이 때, x는 input, y는 output을 의미하며 f 함수는 sigmoid라고 가정하자.

Forward

우선 x로부터 y를 얻기 위해 forwarding 과정을 거친다. x는 빨간 선을 따라서 y를 얻을 수 있다.

예측값 y를 얻으면 실제값 z와 비교해서 Error를 얻을 수 있다.

Backpropagation

이제 Error 오차를 얻었으니 각 노드에서 온 값들이 얼마나 영향을 주었는지 거꾸로 탐색하며 Error의 정도를 측정한다.

Forward되는 과정에서 w를 통하여 y로 도달했기 때문에 Error 또한 weight만큼의 영향을 주었다고 생각할 수 있다. 이 때, w_i,j는 i에서 j로 향하는 weight를 의미한다. 위 그림과 같은 과정을 input x 까지 계속해서 반복한다.

Weights Updating

Backpropagation 과정을 거쳤으면 각 weight별로 얼만큼의 에러를 발생했는지 확인했기 때문에 다음 예측을 정확히 하기 위해서 weight를 변경해야 한다. 이전 단계에서 구했던 Error를 편미분 하여서 weight를 update하도록 한다.

BP Training

1. Stochastic GD (SGD)
   • 각 single instance에 대해서 local error를 계산하고(like SE or CE) gradient를 계산한다.
   • solution에 도달하기까지 많은 시간이 걸린다.
   • 하지만 빠르다
2. Batch GD (BGD)
   • 전체 데이터를 가지고 global error를 계산한다.(like MSE or ACE) global error gradient를 계산해서 한번에 업데이트 한다.
   • 많은 계산량을 요구한다.(그래서 느리다.)
   • 소규모 훈련 데이터에 사용가능하다.
3. Mini-batch GD
   • 1번과 2번의 장점을 합친 것이다.
   • B=1이면 SGD가 되고, B=Q가 되면 BGD가 된다.

문제:

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력:

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력:

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

풀이방법:

 자두가 움직일 수 있는 횟수는 W로 초는 T로 고정되어 있기 때문에 열은 W이고, 행은 T인 DP 테이블을 만들어서 이 문제를 해결하도록 한다.

 계속해서 움직이지 않는 경우는 1에서만 점수가 오르기 때문에 1일때만 이전 행의 0열 값을 가져와 1을 더하도록 한다. 1번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 짝수일 때 카운트가 오르게 되고, 2번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 홀수일 때 카운트가 오르게 된다. (1번나무에서 초기에 위치하기 때문)

문제링크:

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

Abstract

93개의 다른언어를 위한 joint multilingual sentence representations를 배운다.

우리의 시스템은 모든 언어가 공유하는 BRE single BiLSTM encoder를 사용하고, 보조적인 역할을 하는 decoder가 있다. 공개되어 있는 parallel corpora로 학습한다.

이것은 영어로만 되어 있는 데이터를 가지고 resulting embedding의 top의 classifier를 배울 수 있고, 이 것을 수정없이 93개 언어로 전이 가능하다.

우리의 실험은 XNLI, ML-Doc, BUCC로 진행했고, 직접 만든 112개의 언어로 유사도를 측정했다.

1. Introduction

deep learning이 NLP에 놀라운 인상을 주었지만 여전히 데이터가 부족하고 제한된 실용성을 가지고 있다.

이러한 이슈를 해결하기 위한 첫 번째 방법은 unlabeled data에 대해 언어 표현을 배우는 것이었고, 이를 task-specific downstream에 적용하는 것이였다. 이 방법은 word embedding으로 유명하지만 최근에는 sentence-level의 표현을 원한다.

그럼에도 불구하고 각 모델들은 서로 다른 언어로 학습되어지기 때문에 서로 다른 언어에는 적용할 수 없어서 적은 자원의 언어로 충분한 성능을 내기에는 한계가 있었다.

그래서 이번에는 input과 NLP task에서 general 할 sentence의 vector representation인 전체 언어를 아우르는 sentence embedding을 다루려고 한다.

이러한 표현형에 동기는 여러 가지가 있다.

1. 제한된 자원을 가진 언어로 많은 언어를 처리할 수 있다는 희망
2. 한 언어에서 다른 언어로 zero-shot 하려는 욕망
3. code-switching을 할 수 있다는 가능성

이전에 있던 multilingual NLP 연구에서는 제한된 몇개 언어에 대해서만 수행을 하거나, 특정 task에 대해서만 수행했다. 이번 논문에서는 93개 언어에 대해서 시도를 했으며, 이는 아마도 우리가 처음일 것 이다.

2. Related Work

생략

3. Proposed method

single BiLSTM을 보조적인 역할을 하는 decoder와 함께 사용한다.

3.1 Architecture

Schwenk가 제안한 구조를 바탕으로 구성되었다.

보이는 것과 같이 sentence embedding은 encoder의 output에 max-pooling을 통해서 얻는다.

이러한 sentence embedding은 선형변환을 통해 decoder LSTM을 초기화하는데에 사용하고, 매 step마다 그 input embedding과 결합된다. sentence embedding에 의해 발견되는 input sequence과 관련된 모든 정보를 원하기 때문에 encoder와 decoder 사이에는 다른 연결은 없다.

우리는 포함된 모든 언어가 공유하는 single encoder와 decoder를 사용한다. 이를 위해서 우리는 50k의 연산을 가지고 있고 모든 훈련 corpora의 결합을 배우기 위해 joint byte-pair encoding (BPE)를 만든다.

encoder는 input language가 무엇인지 signal을 가지고 있지 않고, 이것은 독립적인 representation을 배우도록 할 수 있다. 대조적으로 decoder는 생성해야할 언어를 특정하는 ID embedding을 가지며 이는 input과 sentence embedding이 매 step 합쳐진 것이다.

거의 100개 언어를 위해 충분한 공간이 있어야 한다. 이 논문에서 BiLSTM은 512 차원을 가지는 5개의 layer를 가진다. resulting sentence representation은 1024차원이다. (양방향으로 결합되었기 때문?)

decoder는 항상 2048차원을 가진다.

input embedding 크기는 320으로 고정되어 있고, language ID embedding은 32차원을 가진다.

3.2 Training strategy

이전 연구에서 각 input sentence는 모든 다른 언어로 번역되었다. 하지만 이 접근은 언어의 수가 많아질수록 큰 두가지 단점을 가지고 있다. 첫번째는 이 방법은 N개의 평행한 corpus를 가지고 있어야 하는데 모든 언어를 얻기 힘들다. 두번째는 지수승으로 시간이 증가하기 때문이다.

우리의 사전 실험에서 우리는 두 개의 target 언어만을 사용해서 얻는 비슷한 결과를 관찰했다.

그와 동시에 각 언어 조합을 분리 alignment를 고려함으로써 N개의 parallel corpora에 대한 요구를 완화했다.

훈련 파라미터 설명

3.3 Training data and pre-processing

3.2에서 설명했던 것처럼 훈련 과정에서 두 target 언어가 놓여진 bitext를 요구한다. 따라서 이 논문에서는 영어와 스페인어를 골랐다. 대부분의 데이터가 이러한 언어와 정렬되어 있다.

93개의 언어를 다 수집했다. 기계번역 tool을 사용해서 pre-processing을 했다.

4. Experimental evaluation

multilingual sentence embedding을 평가하는 표준 방법이 존재하지는 않다. 그래서 가장 괜찮다고 생각되는 XNLI(4.1)과 cross-lingual document classification(4.2), Bitext mining(4.3)그리고 저자가 직접 만든 평가방법(4.4)로 이 모델을 평가하고자 한다.

4.1 XNLI : cross-lingual NLI

NLI는 sentence representation를 평가하는데 가장 많이 사용되는 방법이다. 두 문장이 주어지고 이 두 문장간의 관계를 파악하는 문제다. XNLI는 영어를 다른 언어로 번역을 한 뒤에 NLI 과정을 거치는 평가방법이다. 이를 BERT와 비교해보았을 때, 영어 단일 NLI에 대해서는 성능이 좋지 못했지만 이를 다른 언어로 번역한 뒤에 성능을 평가했을 때에는 더 좋은 성능을 얻었다.

4.2 MLDoc : cross-lingual classification

4.3 BUCC : bitext mining

4.4 Tatoeba: similarity search

5. Ablation experiments

5.1 Encoder depth

encoder의 깊이가 길어질수록 성능이 더 좋아진다.

5.2 Multitask learning

생략

5.3 Number of training languages

얼마나 많은 언어를 수용할 수 있는지 알 수 있기 위해 93개 언어를 가지고 있는 모델과 18개 언어를 가지고 있는 부분 모델과 비교해보았을 때, 큰 차이가 없다.

6. Conclusions

• 이 논문에서 93개 언어에 대해 multilingual fixed-length sentence embeddings을 배우는 구조를 제안했다.
• multilingual sentence embedding을 평가하는 방법들에 대해서 좋은 성능을 보였고, 이 논문에서 만든 평가방법에서도 좋은 성능을 보였다.
• 다음 연구에서는 self-attention을 encoder 구조를 사용하는 것을 생각해보겠다.
• 혹은 monolingual data를 사용하거나 unsupervised MT와 같은 방법을 사용하는 전략도 찾아보겠다.

사견

• 약 93개의 언어를 하나의 embedding으로 만드는 것은 좋다.
• 하지만 16개의 GPU를 사용했다고 하는데, 이건 facebook이라서 할 수 있는 방법이지 않을까 생각이 든다.
  • 성능으로 찍어 누른 느낌

문제:

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력:

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력:

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)

풀이방법:

N명이 있을 때, 발생하는 경우의 수를 점화식으로 구하면 DP[N] = DP[N-1]+DP[N-2]와 같이 구할 수 있다.

그리고 VIP들 같은 경우에는 움직이지 못하기 때문에 주위 사람들과 자리 변경이 불가능하다. 따라서 양 옆을 분할한다라고 생각할 수 있다. 즉 문제에서 소개한 예시로 보면 9개의 자리가 있을 때, 4와 7에서 자리를 분할하고 있다. 이제 이 문제는 DP[3] * DP[2] * DP[2]와 같이 경우의 수를 구하면 된다.

문제링크:

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

문제:

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

풀이방법:

 처음에는 이 문제를 투포인터를 사용하는 방법으로 접근하였다. list의 합이 N과 같으면 길이를 비교하여 저장하도록 하였고, N보다 작으면 리스트의 길이를 늘려주고 N보다 크면 리스트의 길이를 줄여주도록 하였다.

 하지만 이 방법은 N의 크기에 따라 시간이 많이 증가할 수 있다는 단점을 가지고 있었고 결국 시간초과가 발생하게 되었다. 코드는 다음과 같다.

따라서 다른 방법을 생각해보았는데, 이 문제를 수학적으로 접근해보았다. 

우선 길이가 L인 연속된 수들의 합이 N이 되는 수열은 항상 존재한다고 가정한다. 그리고 그 수열의 첫 시작 수를 X라고 할 때, 다음과 같이 식을 표현할 수 있다.

N = X + (X+1) + (X+2) + (X+3) + ... + (X+L-1)

이를 정리하면 다음과 같이 표현할 수 있다.

N = LX + (1+2+3+...+L-1)

   = LX + (L-1)L/2

그럼 X는 다음과 같이 구할 수 있다.

X = N/L - (L-1)/2

따라서 L을 증가 시키면서, 음이 아닌 정수가 되는 X를 찾으면 된다. 그리고 만약 L이 100이 넘어간다면 -1을 문제 조건에 따라 출력하도록 한다.

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

문제:

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

입력:

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력:

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

풀이방법:

1. 우선순위 큐를 사용해서 연료 내에서 움직일 수 있는 주유소에서 주유하도록 한다.

2. 데이터를 전처리할 때, 거리는 작은 순으로 주어지지 않는다. 정렬이 필요하다

3. 마을에 도착하지 못하는 경우는 while에 있지만 더 이상 움직이지 못할 때를 의미한다. (candidates가 비어있는 경우)

문제링크:

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