PAPER

Abstract

NLU는 tedtual entailment, QA, semantice similarity assessment, 문서 분류과 같은 다양한 task를 구성함. large unlabeled text corpora🔺/ 특정 task를 학습하기 위한 labeled data 🔻 ▶ discriminatively trained model이 적절하게 수행하는 것이 어려움

semi-supervised한 접근법을 소개 다양한 unlabeled text corpus에서 언어 모델의 generative pre-training과 각 task별 discriminative fine-tuning으로 큰 성과 ▶unlabeled data로 general하게 모델을 학습한 후, laebeled data로 원하는 task에 specific하게 모델을 fine-tuning

Introduction

대부분의 딥러닝 방법들이 수동적으로 labeled data를 구해야하는 상황에서 unlabeled data의 언어 정보를 활용할 수 있는 annotation 작업의 대안으로 가치있음. (시간과 비용이 많이 드는 작업이기 때문) 비지도 방식으로 좋은 표현 학습 > 지도 방식 ex. pre-trained word embedding 사용 → NLP task의 성능 향상

unlabeled text에서 word-level 이상의 정보를 활용하는 것이 어려운 이유 → uncertainties (불확실성) ⓛ transfer에 유용한 text를 표현을 학습하는 데 어떤 종류의 optimization objectives가 가장 효과적인지 명확하지 않음 ② 학습된 표현을 target task로 transfer하는 가장 효과적인 방법이 정해져있지 않음

비지도(unsuperivsed) pre-training + 지도(supervised) fine-tuning → NLU에 대한 semi-supervised 방식 탐구 ▶다양한 task에 사용하면서도 약간의 adaptation으로 transfer할 수 있는 universal representation 학습

두 단계의 훈련 절차 ⓛ unlabeled data에 대한 language modeling objective를 사용하여 신경망 모델의 초기 파라미터 학습 ② 해당하는 supervised objective를 사용해 target task에 맞게 파라미터 수정

모델 구조 → Transformer 사용 ▶ recurrent network와 같은 대안과 비교했을 때 텍스트의 장기 의존성을 다루기 위해 더 구조화된 메모리 제공 → 다양한 task에 robust한 전이 성능을 얻음 transfer를 할 때는 traversal-style approachs에서 사용된 task-specific한 input adaptation 사용 → 구조화된 text input을 single contiguous sequence of tokens로 처리함. → 모델의 구조를 최소한으로 변경하면서 효과적으로 fine tuning할 수 있음.

Related Work

Semi-supervised learning for NLP sequence labeling, text classification에 적용되며 관심을 받았는데, 초기 연구에서는 unlabeled data를 사용해서 word-level이나 phrase-level의 통계량을 계산하고 이를 supervised model의 feature로 사용하였음. 최근 연구에서는 unlabeled data에서 word-level semantics 이상의 phrase-level이나 sentence-level embedding을 시도함.

Unsupervised pre-training supervised learning objective 조절이 목표가 아닌 좋은 initialization point를 찾는 것이 목표 (semi-supervised learning의 special case) 이 논문과 비슷한 연구로 language modeling objective를 사용해서 사전 학습을 진행하고 target task에 fine-tuning하는 연구가 있었는데, 사전학습을 할 때 언어 정보를 얻기 위해 LSTM을 사용했고 이로인해 짧은 범위의 예측만 가능했음. → 본 논문에서는 transformer를 사용해 긴 범위의 데이터에서도 가능하도록 함.

Auxiliary training objectives auxiliary unsupervised training objectives를 추가하는 것은 semi-supervised learinng의 다른 형태임. 본 논문에서도 auxiliary objective를 사용하지만, unsupervised pre-training은 이미 target task와 관련된 여러 언어적 측면을 학습함.

Framework

① large corpus of text에서 high-capacity 언어 모델을 학습 ② fine-tuning → labeled data를 사용해서 모델을 discriminative task에 적용

Unsupervised pre-training

비지도 말뭉치 토큰 u={u_1, u_2, ... ,u_n}이 주어졌을 때, likelihood를 최대화하는 방향으로 stadard lanuage modeling objective 사용 :

k : context window의 크기 조건부 확률 P : 파라미터 Θ를 가진 신경망을 사용하여 모델링

→ stchastic gradient descent(확률적 경사 하강법)를 사용하여 훈련 ex) I like you → I와 like가 주어졌을 때, you를 예측

i-k ~ i-1번째의 token들로 i번째 token을 예측할 likelihood를 최대화하도록 모델의 파라미터 업데이트 unlabeled data에서도 학습이 가능하기 때문에 Unsupervised learning에 해당함.

Transformer의 변형인 multi-layer Transformer decoder를 언어 모델로 사용 ✅ multi-headed self-attention을 input context token에 적용 ✅ position-wise feedforward layer를 거쳐 target tokens에 대한 output distribution 생성

임베딩 후에 potision embedding matrix를 더하고, layer의 갯수만큼 decoder block을 통과한 후, position-wise layer를 거쳐 softmax로 확률값을 구함.

U = (u−k, . . . , u−1) : token context vetor n : 레이어의 수 $W_e$ : token embedding matrix, $W_p$ : position embedding matrix

$W_e$를 통해 token embedding하고, 그 결과값에 W_p을 통해 구한 position embedding 값을 더함 → n개의 transformer의 decoder block에 통과 → 최종 결과에 $W_e'$를 내적하고, softmax을 적용

Supervised fine-tuning

Unsupervised pre-training한 뒤에,사용된 파라미터들을 supervised target task에 맞게 fine-tuning

y : label x : input token

pre-training된 transformer의 최종 출력물인 $h_l^m$을 얻게 되고, label $y$를 예측하기 위해 $W_y$와 곱해 softmax함수 적용

log likelihood를 최대화 하는 식 :

input token을 넣었을 때 label값을 반환할 likelihood를 의미하고 likelihood를 최대화하도록 $W_y$를 업데이트함.

fine-tuning에 언어 모델링을 auxiliary objective로 포함 (a) supervised model의 일반화 성능 향상 (b) 수렴 가속화 → 학습에 도움 + 성능 향상

lambda : 가중치

L1은 pre-train에서의 식 즉, auxiliary objective 두 식을 함께 사용함으로써 모델의 generalization과 convergence에 도움이 됨.

Task-specific input transformatons

각 task에 적합하게 input data의 구조를 만들어주면 pre-train한 모델의 구조를 크게 바꾸지 않더라도 다양한 task에 fine-tuning 가능

pre-trained model이 contiguous sequences of text에 대해 학습되었기 때문에 orderded sentence pairs, triplets of document, QA와 같은 task에 적용하기 위해서는 일부 수정이 필요함. ▶traversal-style approach를 사용해서 구조화된 입력을 pre-trained model이 사용할 수 있는 순서화된 시퀀스로 변환

Textual entailment premise p와 hypothesis h 토큰 시퀀스를 결합함. 두 시퀀스 사이에 delimiter token ($)를 concat

Similarity 순서 X, 입력 시퀀스를 수정하여 가능한 두 문장 순서(delimiter 포함)를 모두 포함하여 독립적으로 처리, 두 시퀀스 표현 $h_l^m$을 요소별로 더한 후에 linear ouput layer에 입력함.

Question Answering and Commonsense Reasoning context documnet z, question q, possible answers ${a_k}$가 주어짐. delimiter token으로 [z; q; $; ak]를 더해줘서 document context와 question을 각각 가능한 answer와 concat함. 각 시퀀스들은 독립적으로 처리되고 softmax layer를 통해 정규화돼서 가능한 답변에 대한 분포를 생성함.

Experiments

setup

Model specifications

• masked self-attention heads를 가진 12개의 transformer decoder layer로 학습
• self-attention head (각 64개의 Q, K, V과 총 12개의 heads로 구성)
• position-wise feed-forward는 총 3072차원
• Adam optimizer 사용
• activation function : Gaussian Error Linear Unit (GELU)

Supervised fine-tuning

Natural Language inference

Question answering and commonsense reasoning

Semantic similarity and Classification

Analysis

Impact of number of layers transferred

unsupervised pre-trainnig에서 supervised target task로 이동하는 layer의 수가 변할 때 영향 ✅ transferring embedding들이 layer마다 최대 9%의 성능 향상 Figure2 : 왼쪽 그림 ✅ pre-trained model의 각 layer가 유용한 기능을 포함한다는 것을 나타냄. ✅ *Transfer하는 layer의 개수가 많을 수록 성능이 좋아짐. *

Zero-shot Behaviors transformer를 사용한 언어 모델 pre-training이 효과적인 이유 ▶ generative model이 언어 모델링의 capability를 향상시키기 위해 많은 task를 배울 수 있고, LSTM과 비교해 transformer의 구조화된 attentional memory가 transfer에 도움이 됨. ▶ supervised fine tuning없이 generative model 사용

heuristic solution의 generative pre-training의 효과 시각화 Figure2 : 오른쪽 그림 : 학습 횟수에 따라 성능이 안정적으로 꾸준히 증가 → generative pretraining이 다양한 task를 학습하는 것에 도움을 줌. ▶ pre-training을 더 많이 할수록 다양한 task에 성능 증가 LSTM은 zero-shot 성능에서 더 큰 분산을 보이는데, Transformer 아키텍쳐의 inductive bias(일반화가 잘 되었는지)가 transfer에 도움이 됨을 의미함.

Ablation studies

auxiliary objective의 효과 NLI와 QQP(Quora Question Pairs) 데이터셋에서 성능 향상에 도움을 줌 (크기가 작은 데이터셋에서는 X) Transformer 대신에 LSTM 모델을 사용한 결과 - MRPC 데이터셋을 제외하고는 transformer가 더 좋은 성능을 보임 pre-training을 했을 때가 성능이 더 좋음

Conclusion

generative pre-training과 discriminative fine-tuning을 통해 여러 task에 강력한 NLU를 달성하는 framework를 소개함. contiguous text의 long stretches로 다양한 corpus에서 pre-training함으로써 word knowledge와 long-range dependencies를 처리하는 능력을 얻어 QA, semantic similarity assessment, entailment determination, text classification과 같은 task에 맞게 성공적으로 전이되었고 12개의 데이터셋 중에서 9개에서 SOTA 달성함.

PAPER

Abstract

새로운 type의 deep contextualized word representation을 소개 (1) 단어 사용의 복잡한 특성들 (e.g. syntax and semantics)을 모두 만족시키는 표현 (2) 언어적 맥락에서 어떻게 다양하게 사용되는지 (i.e. to model polysemy) 💭 ‘눈’이라는 다의어는 일부 문장에서는 snow❄로, 다른 문장에서는 eye👀로 다르게 해석됨.

논문에서 제시한 word vector는 large text corpus에서 사전 훈련된 deep bidirectional language model (biLM)의 내부 상태의 학습된 함수 ▶ 기존 모델에 쉽게 추가 ▶ QA, textual entailment, 감성 분석을 포함한 6개의 NLP 문제에서 SOTA 달성

ELMo(Embeddings from Language Model)는 2018년에 제안된 새로운 word embedding 방법론

• 더 좋은 단어 표현을 위해 만들어짐
• 사전 훈련된 언어 모델(Pre-trained language model) 사용

Introduction

사전 훈련된 word representations는 많은 NLU model에서 중요한 요소지만, high quality representations 학습은 어려움. (1) 단어 사용의 복잡한 특성들 e.g. syntax and semantics (2) 언어적 맥락에서 어떻게 다양하게 사용되는지 i.e. to model polysemy 에 대해 모델링해야 함. 문맥에 따라서 다르게 word embedding → new type of deep contextualized word representation

기존의 각 토큰별로 embedding하는 전통적인 word type embedding과 다름 ▶ large text corpus에서 coupled language model (LM)로 훈련된 bidirectional LSTM에서 파생된 벡터 사용 ▶ Embeddings from Language Models → ELMo ▶ LSTM의 마지막 레이어만 사용 X → LSTM의 모든 내부 레이어 사용 (각 입력 단어 위에 쌓인 벡터들의 선형 조합) • higher-level LSTM : 문맥을 반영한 단어의 의미를 잘 표현 • lower-level LSTM : 단어의 문법적인 측면을 잘 표현

ELMo: Embeddings from Language Models

ELMo word representations ▶전체 입력 문장의 함수 ▶ character convolutions을 사용한 two-layer biLMs 위에 계산됨 → 대규모로 사전 학습된 biLM을 사용하여 semi-supervised learning 수행 + 기존의 neural NLP architecture에 쉽게 통합

Bidirectional language models

길이가 N인 token $(t_1,t_2, …,t_N)$이 있을 때, forward language model은 $(t_1, t_k,…,t_{k-1})$가 주어졌을 때, $t_k$ token이 나올 확률 계산

backward language model은 $(𝑡{𝑘+1},𝑡{𝑘+2}, …,𝑡_𝑁) $이 주어졌을 때 token 𝑡_𝑘가 나올 확률을 계산 → 다음 context가 주어졌을 때, 이전 token 예측

biLM = forward language model + backward language model forward & backward directions의 log likelihood를 최대화

완전히 독립적인 parameter를 사용하는 대신 directions 간에 일부 weights 공유

ELMo

두 LSTM의 layer representations의 결합 biLM의 L개의 layer는 각 token $t_k$당 $2L+1$개의 representation 계산

모델을 downstream에 적용하기 전에 먼저 모든 layers를 하나의 vector로 압축시켜야 함.

모든 biLM layers의 task specific weighting 계산

$s_{task}$ : softmax-normalized weights, scalar parameter $γ_{task}$ : 작업 모델이 전체 ELMo 벡터를 조절 scale

ELMo의 embedding 동작 방식

1. 단어마다 Forward LSTM의 hidden vector 및 token embedding vector와 Backward LSTM의 hidden vector 및 token embedding vector를 Concatenate
2. 이어 붙인 벡터에 각각 가중치 s0,s1,s2를 곱해줌.
3. 세 벡터를 더해준 벡터를 ELMo 임베딩 벡터로 사용함. • s0,s1,s2는 학습을 통해 갱신되는 parameter로 task에 따라 달라짐. • 단어의 문맥적인 의미가 중요한 태스크 - 상위 레이어에 곱해주는 s2 🔺 • 구조 관계가 중요한 태스크 - 하위 레이어에 곱해주는 s1 🔺

Using biLMs for supervised NLP tasks

supervised downstream task에 ELMo를 적용하는 구체적인 방법은 간단함. 1. biLM을 학습시켜 각 단어에 대한 layer representations를 저장 2. downstream이 pretrain된 모델의 선형결합 학습

biLM이 없는 supervised model의 가장 낮은 레이어 고려 ▶ token sequence $(𝑡1,𝑡_2, …,𝑡_𝑁)$가 주어지면, 사전 훈련된 word embedding과 선택적 character-based representations를 사용해 각 token position마다 context-independent token representation $x_k$를 만듦 ▶ bidirectional RNNs, CNNs 또는 feed forward networks를 사용해 context-sensitive representation $h_k$ 생성

ELMo를 supervised model에 추가 ▶ biLM의 가중치 고정 ▶ ELMo vector ELMo_task_k를 xk에 연결 ▶ [xk; ELMo_task_k]을 task RNN으로 전달

➕ moderate amount of dropout를 추가하는 것이 유용함 ➕ ELMo 가중치를 정규화하기 위해 손실에 λ||w||2_2를 추가하는 것도 유용함 → ELMo 가중치에 대한 inductive bias를 가해서 모든 biLM layers의 평균에 가깝게 유지 일반화 성능🔺

Pre-trained bidirectional language model architecture

L = 2 biLSTM을 사용, dimension = 512, LSTM 첫 번째와 두 번째 레이어 사이에 residual connection로 연결 (각 layer는 4096 units과 512 dimension projections) embedding은 2048 character n-gram convolutional filters에 두 개의 highway layer 사용, 512차원으로 projection시켜줌.

Evaluation

6개의 NLP task에 대해서 ELMo를 적용했을때 성능 향상이 있었고 일부 task에서는 SOTA성능을 얻음

Analysis

• 모두 다른 가중치를 적용했을때 가장 성능이 좋았음 • 선형 결합없이 최상단 은닉 벡터만 사용하는것이 임베딩 없이 사용할때보다 성능이 좋았음

• 입출력 단계에 모두 ELMo 임베딩을 적용하는 것이 가장 좋음 • 입, 출력 벡터 중 하나에만 적용하는 경우는 모두 적용한 경우보다는 떨어지지만, 아무것도 사용하지 않은 모델보다는 좋은 성능을 보임

Glove에서는 “play”에 관련된 단어들로 스포츠와 관련된 단어 등장 biLM에서는 “play“와 유사한 의미로 사용되는 문장이 관련된 단어 등장

기존모델은 486 epochs에 최고 성능을 도달, ELMo를 적용한 모델은 10 epochs에 최고 성능을 도달 모델에 ELMo를 추가했을 때 학습속도가 빠름 + 더 작은 훈련 세트를 더 효율적으로 훈련함

Conclusion

ELMo를 시작으로 대량의 말뭉치로부터 생성된 품질 좋은 임베딩 벡터를 만드는 모델이 많이 사용됨. ELMo는 이후에 등장하는 트랜스포머 기반의 BERT나 GPT보다 많이 사용되지는 않지만 좋은 품질의 임베딩 벡터를 바탕으로 적절한 Fine-tuning후에 여러 태스크에 적용하는 전이 학습(Transfer learning)의 시초격인 모델로서의 의의가 있다고 할 수 있음.

BERT와 같은 Transformer 기반의 모델들은 NLP에서 매우 성공적인 deep learning model이 되었음. 하지만, full attention mechanism을 수행으로 인한 sequence 길이에 따른 quadratic dependency가 주요 한계임. Big Bird는 sparse attention mechanism을 사용하여 quadratic dependency를 선형으로 줄일 수 있음. sparse attention으로 인해 비슷한 하드웨어를 사용하고도 8배의 길이의 sequence를 다룰 수 있게 됨. 이로 인해, QA나 summarization 같은 다양한 NLP task에 성능을 향상시켰음.

Introduction

Transformer는 self-attention mechanism으로 input sequence의 각 토큰을 병렬로 처리할 수 있고, RNN의 sequential dependency도 해결할 수 있었음. (모든 토큰에 대해 독립적으로 attention 가능) self-attention은 계산과 메모리 요구가 sequence 길이의 제곱에 비례하게 증가함. 대략 512 토큰 길이의 input sequence를 다룰 수 있는데 이는 QA나 document classification과 같이 큰 context에서 적용하기 어려움.

📍 2가지의 아이디어를 바탕으로 연구를 진행함. ① 더 적은 inner-product를 사용하여 fully quadratic self-attention의 이점을 달성할 수 있을까? ② sparse attention mechanism으로 원래 네트워크의 expressivity와 flexibility를 보존할 수 있을까?

Big Bird는 3가지 main part로 이루어짐. ✅ sequence의 모든 부분에 attention하는 g개의 global token ✅ 모든 토큰이 w개의 local neighboring token에 attention함. ✅ 모든 토큰이 r개의 random token에 attention함. → 더 긴 sequence 길이(8배)에 높은 성능의 attention mechanism을 수행할 수 있음.

Related Work

두 가지의 방법으로 Transformer의 quadratic dependency를 해결하고자 했음.

• 길이 제한을 받아들이고(입력 문장의 길이 : 512 token) 발전시키기 (ex. sliding window) SpanBERT, ORQA, REALM, RAG
• 입력 문장의 길이를 늘리기 위해 full attention을 하지 않는 approach Reformer, BlockBERT, Longformer → Big Bird도 여기에 해당❗

BigBird Architecture

Bir Bird는 multi-head attention과 feed forward network로 이루어진 layer를 쌓아서 만든 Transformer 구조 기반임. ✔ self-attention layer에서 full-attention 이 아닌 generalised attention mechanism을 사용함.

generalised attention mechanism은 노드(vertex) 집합 $[n] = {1, ... , n}$이고, inner product의 집합인 attention mechanism을 수행하는 directed edge로 이루어진 directed graph D로 나타낼 수 있음.

input $d$ 차원으로 embedding된 input sequence $X =(x_1,x_2,...,x_n)∈R(n$x$d)$

$A ∈ [0, 1]$n×n이고 query i가 key j에 attention하는 경우 $A(i, j) = 1$이고 그렇지 않은 경우 $0$ 예를 들어, full self attention(모든 token이 다른 모든 token을 attention)을 하는 BERT같은 경우, matrix가 모두 1이 되며 quadratic complexity를 유발함. → self-attention의 fully connected graph의 관점을 통해 complexity를 줄이기 위해 기존의 graph theory를 사용할 수 있음.

📌 *graph sparsification problem *: self-attention의 quadratic complexity를 줄이기 위한 문제

📍 attention mechanism을 위한 sparse random graph에서 필요한 2가지

1. small average path length between nodes 간단한 random graph 구조인 Erdos-Rényi model를 보면, 각 edge는 고정된 확률로 독립적이게 선택됨. 두 노드간의 가장 짧은 길이는 logarithmic에 비례함. random graph는 complete graph의 spectral property를 근사하고, (인접 행렬의) 두 번째 고유값은 첫 번째 교유값과 멀어지게 됨. → 그래프 내에 mixing time for random walks가 빠르기 때문에 임의의 두 노드 사이를 빠르게 흐를 수 있음. 본 연구에서는 각 query가 r개의 random key를 attention하는 sparse attention을 제안함. A(i, ·) = 1로 random하게 선택된 r개의 키, Figure1-(a)

2. notion of locality locality of reference → 토큰에 대한 많은 정보는 주변 토큰으로부터 유도됨. 그래프 이론에 적용하면, clustering coefficient는 connectivity의 locality를 측정하는 지표이고 그래프가 많은 clique, 가까운 clique를 포함하면 clustering coefficient가 높아짐.

노드에 대한 sliding window로 시작 → 모든 연결의 랜덤한 부분집합(k%)은 랜덤한 연결로 교체, (100-k)% 연결은 유지 window size가 w인 self attention 중에 위치 i의 쿼리가 i-w/2에서 i+w/2까지의 key에 attention함. A(i, i-w/2 : i+w/2) = 1 (Figure1-(b))

✔ random block과 local window로 필요한 모든 context를 포착하는 것은 BERT의 성능보다 부족했음.

이론적 분석과 경험적 성능에 거쳐서 "global tokens"(토큰이 시퀀스에 있는 모든 토큰들에 attention)의 중요성을 활용함. Figure1-(c)

📍 global token은 2가지로 정의됨. - BigBird-ITC(Internal Transformer Construction) : 기존의 일부 토큰들을 전체 sequence에 attention하도록 "global"하게 만들어줌. A(i, :) = 1 및 A(:, i) = 1이 되도록 인덱스의 부분집합 G를 선택 (i ∈ G) - BigBird-ETC(Extended Transformer Construction) : CLS와 같은 추가 "global" token 포함. 모든 기존 토큰에 attention하는 g개의 global token 추가.

→ context를 추가할 추가적인 공간을 더할 수 있고 성능이 향상된 것을 볼 수 있음.

✔ 최종적으로 사용하는 attention mechanism = random attention + window attention + global attention Figure1-(d) random attention query가 r개의 random한 key에 attention window attention 각 query는 왼쪽, 오른쪽에 w/2개의 token에 attention global attention g개의 global token 포함 (global token은 기존 token이거나 추가된 token임.)

📌 Implementation details GPU 및 TPU와 같은 하드웨어 가속기는 연속된 바이트 블록을 한 번에 load하는 병합된 메모리 작업에서 효과적으로 작동함. → sliding window or random element queries로 인한 small sporadic look-ups는 효율적X → "blockifying"로 완화 query, key 벡터가 각각 12개씩 있는 경우, block size를 2로 설정하여 query matrix를 12/2 = 6개 block으로 나누고 key matrix도 12/2 = 6개 block으로 나눔. (query block과 key block의 수는 동일해야 함) 1. Random attention : 각 query block은 r개의 random key block에 attention함. Figure 3(a) r = 1이고 block size=2 → 크기 2의 각 query block이 크기 2의 random key block에 random attention함. 2. Window local attention : block을 만들면서 #query_block = #key_block이도록 함. → block window attention 정의하는데 도움을 줌. 각 query block j는 index j - (w - 1)/2에서 j + (w - 1)/2까지의 key block에 attention함. Figure 3(b) w=3, block size=2 → 각 query block j (크기 2의 query)이 key block j - 1, j, j + 1에 attention함. 3. Global attention : Global block과 모든 block들과의 attention 계산 (block 단위로 계산) Figure 3(c) g = 1, block size=2 / BIGBIRD-ITC의 경우 한 query block과 key block이 모든 block에 attention함.

Theoretical Results about Sparse Attention Mechanism

sparse attention이 2가지 측면에서 full-attention mechanism과 마찬가지로 강력함. ① sparse attention mechanism이 독립적인 encoder에서 사용될 때, seq2seq 함수의 Universal Approximator임. ② sparse encoder-decoder trasformer는 Turing Complete임.

Experiments : Natural Language Processing

MLM을 시작으로, 더 긴 연속적인 sequence를 활용하여 더 나은 contextual representation을 학습할 수 있는지 확인하고 QA와 document classification task에 적용함.

Encoder-Decoder Tasks

Big Bird의 encoder 부분에만 sparse attention mechanism 사용 / decoder에는 full attention 사용 → 실제 generative application에서 input에 비해 ouput sequence의 길이가 대체적으로 작기 때문

Conclusion

토큰의 수에 선형적인 sparse attention mechanism을 사용하는 BigBird를 제안함. seq2seq 함수의 universal approximator이고 Turing complete함. 이론적으로, global token을 추가해서 모델의 expressive power를 보존함. QA와 document classification와 같은 NLP task에서 SOTA 달성. 더 나아가 DNA에 대한 attention based contextual language model을 소개하고 promoter region prediction과 non-coding variants의 predicting effect와 같은 downstream task를 위해 미세조정함.

PAPER

Abstract

BART는 seq2seq 모델을 사전 훈련시키기 위한 denoising autoencoder(DAE)

(1) noising funcion으로 corrupt시키고 (2) original text로 복원 하도록 학습되어짐.

standard Transformer를 기반으로 한 neural machine translation 구조를 사용하여 단순함 + BERT(bidirectional encoder), GPT(left-to-right decoder)와 최근의 다양한 사전 훈련 기법들을 일반화하는데 사용할 수 있음

많은 noising approach에 대해 평가하는데, 원래 문장의 순서를 섞고 text span을 단일 마스트 토큰으로 대체하는 in-filling 기법을 사용해서 최고의 성능을 찾음.

BART는 텍스트 생성을 위해 fine-tuning할 때 특히 효과적이며 comprehension task에서도 잘 작동함.

Introduction

Self-supervised(자기 지도) method는 많은 NLP task에서 성공적이었음.

가장 성공적인 접근 방식은 MLM(Masked Language Models)의 변형으로, 랜덤한 단어의 일부가 masking 처리된 text를 재구성하도록 훈련된 denoising autoencoder임.

최근 masking된 토큰의 분포, masking된 토큰의 순서 예측, masking된 토큰을 대체할 수 있는 context를 개선함으로써 발전함. 그러나, 이러한 방법들은 span prediction, generation와 같은 end task에만 집중해서 applicability을 제한함.

BART는 Bidirectional and Auto-Regressive Transformer를 결합한 모델을 사전 훈련함. seq2seq 모델로 구축된 denoising autoencoder로 다양한 end task에 적용할 수 있음.

(1) noising funcion으로 corrupt시키고 (2) original text로 복원의 두 단계로 사전 훈련됨. BART는 standard Transformer 기반의 neural machine translation 구조를 사용하는데 간단함에도 불구하고 BERT, GPT 및 다양한 사전 훈련 기법을 일반화하는 데 사용되어질 수 있음.

BART의 주요한 장점은 noising flexibility → 원래 text에 임의의 변형을 적용할 수 있고, 길이를 변화시킬 수도 있음.

다양한 noising approach를 평가하였고 원래 문장의 순서를 랜덤하게 섞고 새로운 in-filling기법(text span을 mask token으로 대체)을 사용하는 것이 가장 좋은 성능을 보였음. 이 접근 방식은 BERT의 original word masking과 next sentence prediction을 일반화시킴으로써 모델이 전체 길이의 문장을 추론하고 input에 더 긴 변형을 수행하도록 함.

Model

BART는 corrupted document를 원래의 상태로 매핑해주는 denoising autoencoder임.

seq2seq 모델로 구현되었는데, corrupted text에 대한 bidirectional encoder와 left-to-right autoregressive decoder로 되어있음. 사전 훈련을 위해서 original document의 negative log likelihood을 최적화함.

Architecture

BART는 standard seq2seq Transformer 구조를 사용함. decoder에서는 GPT에서 사용하는 ReLU가 아니라 GeLU를 사용하는 것으로 바꾸고 파라미터 초기화는 N(0, 0.02)로 함.

BART base에서는 encoder와 decoder 각각 6개의 layer 사용 / BART large에서는 encoder와 decoder 각각 12개의 layer 사용

구조는 BERT에서 사용한 것과 비슷하지만, 차이점이 2가지 있음.

(1) decoder의 각 layer가 encoder의 최종 hidden layer와 cross-attention수행 (Transformer와 동일)

(2) BERT는 word prediction 전에 FFN을 추가로 사용하지만, BART는 사용하지 않음.

→ BERT보다 파라미터를 약 10% 더 가지게 됨. (decoder에서 cross-attention을 수행하는 layer 추가)

Pre-training BART

BART는 document를 corrupt하고 decoder의 output과 original document와의 cross entropy인 reconstruction loss를 최적화하는 식으로 훈련되어짐.

기존의 특정 noising scheme에 맞춰진 denoising autoencoder와 다른 것은 BART는 어떤 document corruption이라도 적용할 수 있다는 점임. 극단적인 경우에 source에 대한 모든 정보가 없는 상태더라도 BART는 원래 언어 모델과 동일하게 동작할 수 있음.

Token Masking

BERT와 마찬가지로 랜덤한 token들이 샘플링되어 [MASK]로 대체됨.

Token Deletion

랜덤한 token들이 input으로부터 제거됨. token masking과 다르게 모델이 missing input의 위치를 결정해야 함.

Text Infilling

여러 개의 text span이 샘플링되어 지고, span의 길이는 포아송 분포(λ = 3)를 따름. 각 span은 단일 [MASK] 토큰으로 대체됨. 0-length span도 [MASK] 토큰이 입력될 수 있음. Text Infilling은 SpanBERT에서 영향을 받았는데, SpanBERT는 서로 다른 분포에서 span length를 샘플링하고 각 span을 같은 길이의 [MASK] 토큰 시퀀스로 대체함. Text Infilling은 모델이 하나의 span에서 얼마나 많은 토큰이 없어졌는지 예측하는 방법을 학습시킴.

Sentence Permutation

document는 마침표를 기준으로 문장이 나눠지고 문장은 랜덤한 순서로 섞여짐.

Document Rotation

token이 랜덤하게 균일한 확률로 선택되고 document가 해당 토큰으로 시작되도록 회전되어짐. document의 시작 부분을 찾을 수 있게 훈련됨.

Fine-tuning BART

✅ Sequence Classification Tasks sequence classification task를 위해 encoder와 decoder에 같은 input이 들어가고 마지막 decoder의 마지막 hidden state는 새로운 multi-class linear classifier에 들어감. 이 접근 방법은 BERT에 CLS token과 관련되어 있는데, 여기서는 마지막에 추가적인 토큰을 더하여 decoder에 해당 토큰(마지막에 추가한 토큰)의 representation이 전체 input으로부터 decoder state에 attention 할 수 있도록 함.

✅ Token Classification Tasks token classification task를 위해 complete document를 encoder와 decoder에 입력으로 하고, 각 단어에 대한 representation으로 decoder의 가장 위의 hidden state를 사용함. 이 representation은 토큰을 분류하는데 사용됨.

✅ Sequence Generation Tasks BART는 autoregressive docoder이기 때문에 abstractive QA와 summarization 같은 sequence geration task에 대해 직접적으로 fine-tuning할 수 있음. 이러한 task에서 정보는 input에서 복사되어지지만, 조작(manipulated)되는데 denoising pre-training objective와 관련되어있음. encoder input은 input sequence이고 decoder는 ouput을 autogressive하게 생성함.

✅ Machine Translation BART를 사용하여 영어로 번역하는 machine translation decoer를 개선하는 것을 탐구함.

이전 연구에서는 pre-trained encoder를 통합해서 모델이 개선되었지만, decoder에 pre-trained language model을 사용하는데서는 제한된 효과만 얻음.

BART 전체 모델로 machine translation을 위한 single pretrained decoder로 사용할 수 있음을 보여주었고, bitext로 학습된 새로운 encoder parameter를 추가함.

BART의 encoder embedding layer를 새로 랜덤하게 초기화된 encoder로 변경함. 이 모델은 end-to-end로 학습되며 새로운 encoder를 학습시키는 것으로 외래어를 BART가 영어로 de-noise할 수 있는 input으로 매핑하도록 함. 새로운 encoder는 원래 BART 모델과 다른 별도의 vocabulary를 사용할 수 있음.

두 단계로 source encoder를 훈련하는데, 모두 BART 모델의 ouput으로부터 cross-entropy를 역전파함.

첫 번째 단계에서는 대부분의 BART parameter들을 고정하고 랜덤하게 초기화된 source encoder, BART positional embedding, BART encoder 첫 번째 layer의 self-attention input projection matrix만 업데이트함.

두 번째 단계에서는 모든 모델 parameter를 작은 수의 iteration으로 학습함.

Comparing Pre-training Objectives

BART는 이전 연구보다 pre-training 동안 더 넓은 범위의 noising 방식을 지원함.

Comparison Objectives

훈련 데이터, 훈련 자원, 모델 간의 구조적 차이, fine-tuning 절차의 차이로 인해 공정한 비교가 어려웠음.

최근 제안된 강력한 pre-training approach들을 discriminative와 generation task에 맞게 다시 구현함.

가능한 pre-training objective와 관계없는 차이들을 통제하고자 했지만, 성능 향상을 위해 학습률과 layer normalisation을 최소한으로 변경했음.

Language Model

GPT와 유사하게 left-to-right Transformer language model을 훈련함. 이 모델은 cross-attention을 수행하지 않은 BART decoder와 동일함.

Permuted Language Model

XLNet에 기반하여 1/6의 토큰을 샘플링하고 랜덤한 순서로 autoregressive하게 생성함. 다른 모델들과 동일하게 XLNet에서 수행한 relative positional embedding 또는 attention across segment를 구현하지 않았음.

Masked Language Model

BERT를 따라서 토큰의 15%를 [MASK] 처리하고 독립적으로 원래 토큰을 예측하도록 학습함.

Multitask Masked Language Model

UniLM에서와 같이 Masked Language 모델을 additional self-attention mask와 훈련함. Self-attentionmask는 1/6 left-to-right, 1/6 right-to-left, 1/3 unmasked, 1/3에서 처음 50% 토큰은 unmasked, 나머지는 left-to-right mask 중에 랜덤하게 선택

Masked Seq-to-Seq

MASS에서 영향 받아서 토큰의 50%을 포함한 span을 mask하고 masking된 토큰을 예측하기 위해 seq2seq 모델을 훈련함.

Permuted LM, Masked LM, Multitask Masked LM을 위해 two-stream attention을 이용하여 효율적으로 sequence output에 대한 likelihood를 계산함. (left-to-right 단어 예측을 위해 diagonal self-attention mask를 출력에 사용)

(1) task를 standard seq2seq 문제로 취급, source input은 encoder에 target은 decoder ouput으로

(2) decoder에 source를 target에 prefix로 더하고, sequence의 target 부분에만 loss를 계산

로 실험했는데 전자(1)가 BART 모델에 더 잘 작동했음.

Results

• pre-training method의 성능은 task마다 확연한 차이가 있음.
• Token masking은 중요함.
• Left-to-right pre-training은 generation 성능을 향상시킴.
• SQuAD에서 Bidirectional encoder는 중요함.
• pre-training objective 외에도 중요한 요소가 많음.
• Pure language model이 ELI5에서 최고 성능을 보임.
• BART는 꾸준히 좋은 성능을 달성함.

Large-scale Pre-training Experiments

최근 연구에서는 pre-training이 큰 배치 사이즈와 corpora로 스케일되어질 때, downstream 성능이 극적으로 개선된 것을 보여줌.

Conclusions

corrupted document를 원본으로 매핑하는 pre-training approach인 BERT를 소개함. BART는 discriminative task에서 RoBERTa와 비슷한 성능을 달성하면서 여러 텍스트 생성에서 SOTA를 달성함. 다음 연구에서는 pre-training을 위해 document를 corrupting하는 새로운 방식에 대해 탐구할 것이고 specific end task에 맞게 조정하는 것이 가능할 것임.

PAPER BERT의 T가 Transformer의 약자이기 때문에 Transformer 논문을 먼저 읽고 읽는게 좋을 것 같다. BERT는 Transformer의 Encoder 구조만을 활용한 모델이다!

Abstract

BERT: Bidirectional Encoder Representations from Transformers Transformer의 양방향 인코더 표현 최근 언어 표현 모델들과 달리, unlabeled text로부터 deep bidirectional representations pre-train이 가능 ➡ unlabeled data로 pre-training을 거친 후, 특정 downstream task에 fine-tuning

• task별로 구조를 크게 수정할 필요 없이, 출력 layer 하나를 추가하여 fine-tuning이 가능함. ➡ QA (질문 답변), Language inference (언어 추론)과 같은 task에서 SOTA 달성

이 논문에서 계속해서 deep bidirectional을 강조하는데, 기존의 bidirectional LSTM과 ELMo와 차별화되는 점이 있으니까 강조했겠거니,, 생각했다. ELMo에서는 forward와 backward LSTM의 출력을 단순히 concat(연결)해주는데, 이렇게 함으로써 양방향적인 문맥 정보를 고려한 임베딩을 얻을 수 있었다. 즉, ELMo는 여러 개의 양방향 LSTM 계층을 사용해서 양방향적인 문맥 정보를 고려한 임베딩을 생성하지만, 각각의 LSTM 계층은 단방향으로 동작한다. 그래서 deep bidirectional하지 않다고 표현한 것으로 이해했다 ^_^,,

Introduction

Language model에서 pre-training은 많은 자연어 처리 task에 효과적이라는 것임을 보여줌. NLI(natural language inference)와 paraphrasing과 같은 문장 수준의 task는 문장 간의 관계를 전체적으로 분석하여 예측 개체명 인식과 QA와 같은 토큰 수준의 task는 토큰 단위의 fine-grained ouput을 생성 fine-grained ouput : 하나의 ouput을 내기 위해 ouput 프로세스를 세분화하여 수행

📍Down stream task에 pre-trained language representation를 적용하는 2가지 방법

1. feature-based approach ex. ELMo

• pre-trained representation을 additinal feature로 활용해서 task-specific architecture 사용

2. fine-tuning approach ex. GPT

• 최소한의 task-specific parameter를 도입하고, 모든 사전 훈련된 parameter를 단순히 fine-tuning함으로써 down stream task 학습 ➡ 둘 다 pre-traning 과정에서 동일한 objective function을 공유, general language representation을 학습하기 위해 unidirectional language model 사용

기존의 방식들은 pre-trained representation을 제한함. (특히 fine-tuning approach) 가장 큰 한계는 언어 모델들이 unidirectional하다는 것 → 사전 훈련하는 동안 사용될 수 있는 architecture의 선택을 제한 ex. GPT는 'left-to-right' 구조 사용 → self-attention layer에서 모든 토큰이 이전 토큰에만 attend

BERT는 "MLM(Masked Language Model)"을 사용하여 단방향 제한을 완화시킴.

• MLM은 랜덤하게 input에서 일부 토큰들을 masking하는 것을 말함. - 해당 토큰이 구성하는 문장만을 기반으로 마스킹 된 토큰들의 원래 값을 정확하게 예측하는 것이 목표→ 단방향 언어 모델의 pre-training과는 달리, MLM은 양방향 맥락을 융합시켜서 deep bidirectional이 가능하도록 함. ➕ MLM에서 text-pair representations로 pretrain하면 Next sentence prediction task에도 적용 가능

Related Work

Unsupervised Feature-based Approaches

word embedding을 통한 접근은 sentence embedding 또는 paragraph embedding으로 세분화 되어짐.

sentence representation의 학습은
*① 다음 문장의 후보들에 순위를 매기기 ② 이전 문장이 주어졌을 때, 다음 문장의 단어를 left-to-right로 생성 ③ denoising auto-encoder * 등을 사용했었음.

ELMo와 이전 모델들은 기존의 전통적인 단어 임베딩 연구를 다른 차원에서 일반화하는 방법을 제시 left-to-right와 right-to-left 언어 모델을 통해 context-sensitive feature 추출 각 토큰의 문맥적 표현은 left-to-right 및 right-to-left 표현의 연결(concatenation)로 구성됨.

Unsupervised Fine-tuning Approaches

feature-based approach에서 처음 해야할 작업은 unlabeled text의 word embedding 파라미터들을 사전 학습시키는 것. 최근 contextual token representation을 생성하는 sentence or document encoder는 unlabeled text로 사전 학습시키고 supervised downstream task를 위해 fine-tuning함 ➡ 처음부터 학습시켜야 할 파라미터 수가 적다는 장점

Transfer Learning from Supervised Data

NLI와 machine translation과 같은 큰 데이터셋을 사용한 supervised task에서의 전이 학습도 효과적이었음. 전이학습의 중요성은 CV research 분야에서도 드러나는데, ImageNet으로 사전 훈련된 모델을 fine-tuning한 것도 효과적이었음.

BERT

📍 BERT의 framework는 2단계로 이루어져 있음.

*① pre-training * 다양한 pre-training task의 unlabeled data로 훈련됨.

② fine-tuning 사전 훈련된 파라미터들로 초기화되고 모든 파라미터들은 downstream task의 labeled data를 사용하여 fine-tuning 됨. 각 downstream task는 같은 사전 학습된 파라미터들을 가지고 초기화되더라도 별도의 fine-tuning된 모델을 가짐.

BERT는 다른 task를 수행할 때도 동일한 구조를 가진다는 특징이 있음. ➡ 사전 학습된 구조와 마지막 downstream 구조에서의 최소한의 차이만 존재

Model Architecture

모델 구조는 Transformer에 나와있는 구현에 기반한 multi-layer bidirectional Transformer encoder L : layer의 수 , H : hidden size , A : self-attention head의 수

BERT base L = 12, H = 768, A = 12로 총 110M개의(약 1억1천만) 파라미터 사용 BERT large L = 24, H = 1024, A = 16으로 총 340M개의(약 3억4천만) 파라미터 사용

BERT base는 OpenAI GPT와 비교를 위해 모델 크기를 동일하게 함. BERT Transformer는 bidirectional self-attention을 사용하지만, GPT Transformer는 모든 토큰이 이전의 context만 attention할 수 있는 self-attention을 사용한다는 점이 중요하게 다름. ➡ BERT는 bidirectional self-attention / GPT는 constrained self-attention

• GPT는 next token을 맞추는 기본적인 language model을 만들기 위해 transformer decoder만 사용

• BERT는 MLM과 NSP를 위해 self-attention을 수행하는 transformer encoder만 사용

Input/Output Representations

BERT로 다양한 down-stream task에 적용하기 위해서는 input representation에 단일 문장과 문장 쌍을 하나의 토큰 sequence로 명확하게 나타낼 수 있어야 함. 30,000개의 token vocabulary를 가지는 wordpiece embedding 사용

BERT는 3가지 embedding vector를 합쳐서 input으로 사용

[CLS] : special classification token으로 모든 sequence의 첫 번째 토큰 [SEP] : 문장 쌍이 입력될 때, 문장을 구분해주는 special token

[CLS] 토큰과 일치하는 최종 hidden state는 classification task를 위해 sequence를 표현을 종합함. 문장 쌍은 하나의 sequence로 함께 묶여지는데 special token인 [SEP]로 분리하고, 문장 A인지, B인지 나타내는 embedding인 Segment Embedding을 추가함.

최종적으로 Input은 Token Embedding + Segment Embedding + Position Embedding으로 이루어짐.

Token Embedding은 wordpiece embedding , Position Embedding은 Transformer와 동일

Pre-training BERT

Task #1 : Masked LM

standard conditional language model에서는 'left-to-right'나 'right-to-left'로 훈련되어져 왔는데, bidirectional conditioning은 예측하려는 단어를 간접적으로 참조할 수 있고, multi-layered 구조에서 해당 단어를 예측할 수 있기 때문

deep bidirectional representation을 훈련시키기 위해 input의 일부를 랜덤하게 mask하고 masked token을 예측함. ➡ masked LM (MLM)

mask token에 해당하는 마지막 hidden vector는 standard LM에서와 같이 vocabulary에 대한 출력 softmax로 전달됨. 마스크된 토큰에 해당하는 최종 은닉 벡터들은 출력 소프트맥스를 통해 어휘(vocabulary)에 대한 확률 분포를 생성하고, 확률 분포는 각 단어가 다음에 올 단어일 확률을 나타냄

각 sequence에서 랜덤하게 WordPiece token의 15%를 마스킹함. → masked word 예측

❗ bidirection으로 사전 학습할 수 있게 됐지만, fine-tuning 과정에는 [MASK] 토큰이 없기 때문에 mismatch되는 문제가 생김

이를 완화시키기 위해, [MASK] 토큰을 항상 masked시키지는 않음. 훈련 데이터를 생성할 때, 예측을 위해 랜덤으로 token position의 15%를 선택 (1) 80%는 [MASK] 토큰으로 교체 (2) 10%는 임의의 토큰으로 교체 (3) 10%는 변경되지 않은(기존의) 토큰 사용 이 방식으로 token($T_i$)이 cross entropy loss를 통해 원래 token을 예측함. ($T_i$는 (1)에서는 [MASK] 토큰, (2)에서는 무작위한 토큰, (3)에서는 원래 토큰)

(2)에서 임의의 토큰으로 교체해도 될까 싶지만, 15%의 10%면 1.5%이기 때문에 모델 성능에 영향을 미치지 않는다고 한다..!

Fine-tuning BERT

BERT의 fine-tuning은 Transformer의 self-attention mechanism을 사용하기 때문에 간단함. text pair를 포함한 application에서는 bidirectional cross attention을 적용하기 전에 독립적으로 text pair를 인코딩함. BERT는 self-attention mechanism을 사용해서 이 두 단계를 통합함. ➡ encoding하는 과정에 bidirectional cross attention이 포함 즉, BERT는 두 문장을 하나의 시퀀스로 합치고(self-attention을 통해 각 토큰 간의 상호 작용을 파악), 인코딩된 시퀀스를 통해 두 문장 간의 관계를 동시에 파악함.

각 task에 대해 단순히 task-specific한 입력과 출력을 BERT에 연결하고 모든 파라미터를 end-to-end로 fine-tuning

✅ (1) Sentence pairs in paraphrasing

• 두 개의 문장이 주어졌을 때, 이들이 의미적으로 유사하거나 동일한지 여부를 판단
• 텍스트 간의 의미적 유사성을 파악하고 문장 재구성에 활용

✅ (2) Hypothesis-Premise pairs in entailment

• 두 개의 문장이 가설(hypothesis)과 전제(premise)로 주어졌을 때, 가설과 전제가 맞는지에 대해 확인
• 두 문장 간의 추론 관계 파악

✅ (3) Question-Passage pairs in question answering

• 주어진 지문과 질문에 대해 답을 추출
• 지문에서 질문에 해당하는 정보를 찾아서 답을 추출함.

✅ (4) Degenerate text-∅ pair in text classification or sequence tagging

• 텍스트 분류, 품사 태깅 및 개체명 인식 등
• degenerate text-∅ pair : class 또는 label이 주어지지 않은 텍스트

ouput도 task마다 달라짐.

• 토큰 단위의 task인 sequence tagging이나 QA에서는 ouput layer에 token representation이 들어감.
• 분류를 위한 entailment나 감성 분석에서는 ouput layer에 [CLS] representation이 들어감.

Experiments & Ablation Studies

experiments와 ablation studies는 생략하도록 하겠습니다! 그래도 한 가지만 보도록 하겠습니다,, ㅎㅎ

Feature-based Approach with BERT를 보면 Concat Last Four Hidden의 Dev F1이 96.1로 Fine-tuning approach랑 별로 차이가 안 났습니다. 그런데도 fine-tuning이 더 많이 사용되는 이유가 뭘까 고민해보다 fine-tuning하는게 더 간단한데 성능도 더 좋아서 라고 생각했는데, 다른 이유가 있을까 해서 chat GPT에게 물어봤습니다 ㅎ

Feature-based approach는 모델과 특징을 별도로 설계하고 결합해야 하는 번거로움과 작업의 복잡성으로 인해 제약을 가지고 있습니다. 반면 Fine-tuning은 사전 훈련된 모델을 작업에 맞게 조정하기만 하면 되므로, 특징 엔지니어링과 작업 복잡성에 대한 부담이 줄어듭니다.

라고 하네요!

Conclusion

최근 언어 모델들을 이용한 전이 학습에 따른 실증적인 개선은 unsupervised pre-training이 많은 언어 이해 시스템에 필수적인 부분임을 보여줌. deep unidirectional architecture이 아닌 deep bidirectional architecture를 통해 일반화함으로써 동일한 pre-trained model이 다양한 NLP task를 성공적으로 처리할 수 있다는 것이 주요 기여한 점임.

ABSTRACT

더 정확하고, 다양하고 설명 가능한 추천을 위해서는 user-item interaction과 side information을 추가하는 것이 필요함. FM(factorization machine)과 같은 Traditional method는 각 interaction을 independent instance로 가정해서 supervised learning 문제로 취급했는데 때문에 collborative signal을 추출하는 것이 부족함. ➡ knowledge graph(KG)와 user-item graph를 사용하는 hyhbride 구조를 제안!

• 각 노드의 임베딩을 개선하기 위해 해당 노드의 이웃들의 임베딩을 재귀적으로 전파
• 주변 neighbors의 중요성을 구별하기 위해 attention mechanism 사용

INTRODUCTION

*CF(Collaborative Filtering) 방법 * ✔ side information (아이템 속성, 사용자 프로필 및 맥락 등)을 모델링할 수 없어 user와 item간의 상호 작용이 적은 상황에서 성능이 저하됨.

SL(Supervised Learning) 모델 user ID와 item ID를 함께 generic feature vector로 변환하여 score 예측

✔ 각 상호작용을 독립적인 data instance로 모델링하여 관계를 고려하지 않았음. ✔ Attribute-based Colloborative Signal이 잘 전달되지 않음.

기존 CF 모델들은 user $u_1$이 선호하는 item $i_1$에 focus하여 user $u_4, u_5$에 관심이 있었고, SL 모델은 entity $e_1$을 통해 비슷한 item $i_2$에 관심이 있었음. ❗ 동일한 entity $e_1$에 관심을 갖는 user $u_2, u_3$과 entity $e_1$과 다른 relation을 갖는 item $i_3, i_4$을 고려하지 못함.

✔ high-order information을 활용하는 것에 어려움

1) target user와 high-order relation을 가진 노드들은 order size가 급격히 증가해서 계산량 복잡 2) high-order relation은 예측에 미치는 영향이 동일하지 않아서 가중치 고려 문제 존재

📍 기존 CKG (Collaborative Knowledge Graph)의 문제점

Path-based methods high-order information에 대한 path를 추출하고 예측 모델에 입력 ➡ path selection algorithm or meta-path pattern 사용

two-stage method (path select ➡ training)의 문제점

• path selection이 final performance에 많은 영향을 줌
• 효과적인 meta-path를 정의하기 위해 도메인에 대한 지식 요구

Regularization-based methods 추천 모델을 학습을 regularize하기 위해 KG structure의 loss를 추가적으로 구현

KTUP 및 CFKG는 KG에 포함된 entity 및 relation information을 shared item embedding으로 변환하여 추천과 KG completion 두 가지 task를 동시에 학습시킴. ➡ user와 item 간의 상호 작용뿐만 아니라 KG의 구조적 정보를 함께 고려하여 추천

❗high-order relation을 직접 plugging하는 대신, implicit한 방식으로만 인코딩함. ➡ long-range connectivity를 포착할 수 없고 high-order modeling의 해석도 어려움.

KGAT는 high-order rlation modeling에서 발생하는 문제들을 해결하기 위해 recursive embedding propagation과 attention-based aggregation을 활용함.

TASK FORMULATION

User-Item Bipartite Graph

Knowledge Graph

Collaborative Knowledge Graph

High-Order Connectivity

METHODOLOGY

📍 Embedding Layer KG의 노드를 공간 상의 벡터로 표현하여 각 노드의 특징을 임베딩

📍 Attentive Embedding 임베딩을 업데이트하는 데에 사용되며, attention mechanism을 통해 노드의 특징을 더욱 정교하게 모델링

📍 Prediction Layer 최종 예측 결과 생성

Embedding Layer

Knowledge Completion의 접근 방식인 Translation model에 대해 간단히 학습하고 논문을 읽는 것을 추천한다.

본 논문의 모델은 TransR(entity 와 relation을 다른 차원에 표현)을 이용해 KG를 임베딩함.

$e_h$ : head의 embedding, $e_r$: relation의 embedding, $e_t$: tail의 embedding, $W_r$: relation r의 변환 행렬

TransR에서 $e_h+e_r≈e_t^r$의 translation principle을 따름 ➡ $g(h, r, t)$의 score가 낮을수록 triplet이 실제 있을 가능성🔺

pairwise ranking loss를 통해 $g(h, r, t')$와 $g(h, r, t)$ 간의 상대적인 순서 고려

$g(h, r, t')$ : 실제 그래프상에 존재하지 않는 triplet $g(h, r, t)$ : 실제 그래프상에 존재하는 triplet

Attentive Embedding Propagation Layers

🔍 Information Propagation

• 특정 entity h를 중심으로 h와 연결된 triplet들의 모음
• $π(h,r,t)$ weight값이 $e_t$(tail의 embedding)와 결합되어 propagate

Ego-network : 특정 노드를 중심으로 주변에 직접적으로 연결된 모든 다른 노드의 집합 ✔ 해당 entity가 관여한 관계들을 보다 자세히 이해하고 분석하는 데 사용

🔍 Knowledge-aware Attention

각 weight는 위의 식을 통해 학습함.

비선형 활성화 함수인 tanh를 사용함으로써 attention score가 relation r's space에 있는 $e_h$와 $e_t$ 사이의 거리를 고려할 수 있게 함.

entity들 사이의 거리가 가까울수록 attention score가 높아짐 ➡ 해당 entity들 간의 관계가 더 중요하다고 판단

최종적으로 attention weight는 고정된 head 하나와 관련된 neighbor tail의 모든 weight를 softmax로 표현됨.

💡 final attention score는 collaborative signal을 포착하기 위해 어떤 이웃 노드에 더 많은 attention을 해야 하는지를 제안함.

🔍 Information Aggregation entity h $e_h$와 ego-network $e_{N_h}$을 모아서 새로운 entity h $e^{(1)}_h$을 생성하는 과정

$e^{(1)}h =f(e_h, e{N_h})$

GCN Aggregator

$e_h$와 $e_{N_h}$을 합치고 비선형 변환을 적용

GraphSage Aggregator

$e_h$와 $e_{N_h}$을 연결하고 비선형 변환을 적용

Bi-Interaction Aggregator

$e_h$와 $e_{N_h}$을 각각 합치고, element-wise product를 적용한 후 비선형 변환을 적용

➡ $e_h$와 $e_{N_h}$ 간의 feature interaction을 추가로 인코딩하고 이를 통해 전파되는 정보가 $e_h$와 $e_{N_h}$ 간의 유사도에 민감하게 반응하도록 함.

💡 userm item, knowledge entity representation을 연관시키기 위해 embedding propagation layer를 통해 explicit하게 first-order connectivity information을 활용

Model Prediction

사용자 노드 $u$에 대해 $L$ 레이어를 수행하면 {${e^{(1)}_u, ... e^{(L)}_u}$}의 다층 표현을 얻을 수 있음. (item도 유사)

layer-aggregation mechanism을 적용해서 표현들을 연결하여 단일 벡터로 표현함.

최종적으로 user와 item의 표현에 대해 내적을 수행하여 matching score 예측

EXPERIMENTS

ABSTRACT

기존 GCN(Graph Convolution Network)은 협업 필터링에서 SOTA를 달성하였으나 추천시스템에서 효과적인 이유를 설명하기 어려웠음. GCN은 원래 그래프 분류 태스크를 위해 설계되었던 모델이고 많은 neural entwork operation을 갖추고 있음.

💡 GCN의 가장 흔한 설계인 feature transformation과 nonlinear activation이 협업 필터링 성능에 별로 기여하지 않음을 발견❕ ➕ 훈련의 어려움🔺, 추천 성능🔻 ➡ GCN 모델을 단순화해서 추천에 적합하도록 만들자 (LightGCN)

user-item embeddings를 user-item interaction graph에서 선형적으로 전파하고(linearly propagating), 모든 레이어에서 학습된 임베딩의 가중합을 최종 임베딩으로 사용

INTRODUCTION

CF(Collaborative Filtering, 협업 필터링)의 가장 일반적인 패러다임은 user와 item을 나타내는 latent feature(즉, embedding)을 학습하고, embedding vector를 기반으로 예측을 수행하는 것. ❗ NGCF는 GCN의 구조를 차용했고 CF에서 SOTA를 달성했지만, 본 논문의 저자들은 CF구조에 적절하지 않다고 주장

GCN 모델은 노드 분류를 위해 제안되었기 때문에 각 노드(user or item)가 단순히 식별자인 one-hot ID로만 표현됨. 이러한 간단한 입력에 대해 여러 층의 비선형 특성 변환을 수행(복잡한 모듈 사용)하는 것은 모델 훈련의 어려움만 증가하고 긍정적인 영향을 없을 것이라고 생각 ➡ NGCF에 대한 ablation studies

• feature transformation과 nonlinear activation이 NGCF의 효과에 기여❌
• 오히려 연산을 제거함으로써 모델의 성능🔺

❶ 각 user(item)에 ID embedding을 연결 ❷ user-item interaction graph에 embedding을 전파 ❸ 다양한 propagation layer에서 학습된 embedding을 가중합으로 결합하여 예측을 위한 최종 임베딩을 얻음

✅ 논문에서 하고자 하는 일들

• GCN의 feature transformation과 nonlinear activation이 CF에 긍정적인 영향을 미치지 않음을 보이기
• LightGCN 제안 - 추천을 위해 GCN의 가장 필수적인 구성 요소만 포함하여 모델 단순화
• 동일한 환경에서 NGCF와 LightGCN을 비교하여 개선됨을 보이기
  

PRELIMINARIES

NGCF Brief

NGCF의 embedding rule

user(u) item(i)

• self-connection $(W_1e_u^{(k)},W_2e_i^{(k)})$을 통해 이전에 갖고 있었던 임베딩 정보 유지
• 각 레이어 연산 결과에 symmetric normalization $\frac{1}{\sqrt{|N_u||N_i|}}$을 적용하여 정규화
• feature transformation$(W_1,W_2)$과 nonlinear activation(σ)를 사용해 임베딩 값 업데이트

NGCF는 user-item interaction matrix를 투입했을 때 L개의 레이어를 통과하여 L+1개의 임베딩 user : $(e_u^0, e_u^1, ... ,e_u^L)$ | item : $(e_i^0, e_i^1, ... ,e_i^L)$를 얻을 수 있으며, L+1개의 임베딩을 연결하여 최종 user 임베딩과 item 임베딩을 얻을 수 있고 내적을 사용해서 prediction score 생성함.

Empirical Explorations on NGCF

NGCF-f : feature transformation matrices $W_1, W_2$ 제거 NGCF-n : non-linear activation function σ 제거 NGCF-fn : feature transformation matrices, non-linear activation function 둘다 제거

❶ feature transformation을 추가하는 것은 NGCF에 부정적인 영향을 미침. feature transformation을 제거함으로써 NGCF와 NGCF-n의 성능이 크게 향상됨. ❷ non-linear activation을 추가하는 것은 feature transformation이 포함된 경우 약간 영향을 미치지만, feature transformation을 비활성화할 때 부정적인 영향을 미침. ❸ 전반적으로, feature transformation과 non-linear activation는 NGCF에 부정적인 영향을 미침. 둘다 제거한 NGCF-fn이 NGCF에 비해 큰 개선을 보임. (recall 기준 9.57% 개선)

METHOD

LightGCN

GCN의 핵심 아이디어는 그래프 상의 노드를 표현하기 위해 이웃 노드의 정보를 결합하는 것. 이를 위해 GCN은 graph convolution을 반복하여 각 노드의 새로운 표현을 만듦.

대부분의 작업에서는 feature transformation 또는 nonlinear activation을 AGG 함수와 결합함. semantic input feature를 가지는 graph classification task에서는 잘 수행되지만, CF에서는 아닐 수 있음!

LGC(Light Graph Convolution)에서는 연결된 이웃만 aggregate하고 self-connection을 하지 않음. Layer Combination에서의 작업이 self-connection의 효과와 동일해서 제외함.

기존에 GCN에서 사용하는 정규화 방식인 symmetric normalization $\frac{1}{\sqrt{|N_u||N_i|}}$을 그대로 사용 ➡ embedding의 크기가 증가하는 것을 막을 수 있음.

위의 식을 이용해서 더 높은 레이어의 임베딩을 계산할 수 있으므로 유일하게 학습 가능한 파라미터는 0번째 레이어의 임베딩뿐..! K개의 레이어를 LGC한 후에 각 레이어에서 얻은 임베딩을 결합하여 최종 표현을 생성함.

$α_k$ ≥ 0은 최종 임베딩을 구성하는 k번째 레이어의 임베딩의 중요도 일반적으로 $α_k$를 균일하게 1/(K + 1)로 설정하는 것이 좋은 성능을 낸다는 것을 발견함. ➡ LightGCN을 복잡하게 만들지 않기 위해 특별한 설정없이 이대로 사용

📍 최종 표현을 얻기 위해 레이어 결합을 수행하는 이유

(1) 레이어의 수가 증가함에 따라 임베딩이 over-smoothed될 수 있기 때문 (2) 서로 다른 레이어의 임베딩은 서로 다른 의미를 포착하기 때문 (3) 가중합을 사용하여 서로 다른 레이어의 임베딩을 결합하면 self-connection을 가진 graph convolution의 효과를 가질 수 있음

💡 레이어 수가 증가함에 따라 임베딩이 over-smoothed 되는 이유 + 레이어 결합으로 이 문제를 해결할 수 있는 이유 GCN은 그래프에서 이웃 노드의 정보를 aggregate하여 각 노드의 표현을 갱신함. 이 과정을 여러 번 반복하면 각 노드의 표현이 점점 변화하는데 너무 많은 레이어를 거치면 노드의 표현이 "over-smoothed"될 수 있음. 즉, 각 노드의 표현이 너무 유사해져서 그래프 상의 구조나 특성을 더 이상 충분히 반영하지 못하게 됨. 이는 임베딩이 너무 많은 정보를 잃어버리고 더 이상 유의미한 패턴을 학습하지 못하게 될 수 있다는 것을 의미함. 여러 레이어에서 얻은 임베딩을 결합하면 각 레이어에서 포착한 서로 다른 의미와 특성을 종합적으로 반영할 수 있음!

모델 예측은 user와 item의 최종 표현의 내적으로 정의됨. 추천을 위한 ranking score로 사용

Matrix에 대해 논문에서 설명할 때 대부분 기본적인 설명을 해주는데 기억해야 할 몇 가지 중요한 부분이 있다❗

✅ user 개수가 M, item 개수가 N이지만, Matrix가 (MxN)이라는 것이 아니라 (M+N) x (M+N)이다! ✅ $A$ Matrix를 보면, 빠르게 이해할 수 있는데, 0이 두 군데에 존재한다. 즉, user-item interaction만 반영되고 user-user, item-item interaction은 반영되지 않는다. 그래서 0으로 나타나있는 것이다!

Model Analysis

📍 LightGCN은 self-connection을 사용 ❌

왜 LGC에서 self-connection을 제거해도 되는지 수식적으로 설명

SGCN (Simplifying Graph Convolutional Networks)의 수식을 보면 알 수 있듯, $I ∈ R^{(M+N)×(M+N)}$를 더해줘서 self-connection을 유지함.

LightGCN에서는 단순화를 위해 $(D + I)^{−\frac{1}{2}}$을 제거 ➡ 아래 식이 만들어짐

$α$를 조정하면 아래 식과 동일하다는 것을 알 수 있음 ➡ self-connection 수식을 굳이 넣지 않더라도 self-connection의 효과가 있음

📍 APPNP에서 입증된 over-smooting을 잘 다루는 LightGCN ** [APPNP**](https://arxiv.org/abs/1810.05997)는 initial embedding을 더해줌으로써 long range에서도 oversmoothing에 강한 모델임.

over-smoothing은 레이어의 수가 증가할 수록 최종 임베딩 값이 유사해져 더 이상 유용한 정보를 추출할 수 없게 되어 모델의 성능이 저하되는 문제를 말함.

➡ APPNP의 propagation layer 식

• k 번째 임베딩 $E^{(k)}$을 구하기 위해 초기 임베딩 $E^{(0)}$값을 더해 줌으로써 over-smoothing 문제를 해결
• $β$ ($E^{(0)}$의 반영 비율을 나타내는 확률변수)를 통해 초기 임베딩 값에 대한 영향력을 조정 가능

*📍 두 개의 레이어를 가진 LGC 분석 * user(item)와 연결된 다른 user(item)의 second-order layer 분석하여 인사이트를 얻고자 함.

user $v$가 target user $u$와 같은 item에 상호 작용했다면, 사용자 $v$의 $u$에 대한 영향은 $c_{v→u}$계수에 의해 측정 가능

• 두 user의 interaction history간 겹치는 item이 많으면 계수🔺
• 겹치는 item이 인기가 많으면 계수🔻 (연결이 적으면 계수🔺)
• user $v$의 action history가 적으면 계수🔻 (유저 $u$와 연결된 $v$가 적을수록)
  

Model Training

LightGCN의 학습 가능한 파라미터는 0번째 레이어의 임베딩에만 존재 손실함수 Bayesian Personalized Ranking (BPR) 사용

** BPR** 선호하는 아이템에 대한 예측값이 나머지보다 높도록 유도하는 pair-wise optimization 기법

i : user가 선호하는 item (구매한 item) j : user가 선호하지 않는 item (구매하지 않은 item)

• 모든 유저에 대해서 실제 구매한 아이템과 구매하지 않은 아이템의 차이를 계산
• 구매한 item에는 높은 가중치를 부여하고 구매하지 않은 item은 낮은 가중치를 부여해 loss를 계산하여(BPR 사용) 모델 최적화

EXPERIMENTS

기존 NGCF 모델과 성능 비교

평가 지표로 recall과 ndcg를 보았을 때 모든 데이터 셋과 레이어 수에서 LightGCN의 성능이 훨씬 우수함.

Loss를 보게 되면 LightGCN의 Loss가 더 낮은 것을 보아 NGCF 모델보다 학습을 더 잘함.

LightGCN-single에서 (주황색 막대) Layers의 수가 증가할수록 모델의 성능이 떨어지는 것을 보아, over-smoothing이 발생했다고 판단 ➡ 파란색 막대 - Layer combination의 효과로 over-smoothing 문제 해결

FIFO인 큐와 다르게 우선순위를 가지고 있어서, 우선순위가 높은 데이터부터 처리된다.

✅ 같은 우선순위를 가지면, 먼저 들어온 순으로 처리한다. ✅ 배열, 연결리스트, 힙(Heap) 모두 구현할 수 있지만 일반적으로는 시간복잡도가 적은 힙(Heap)을 사용함

💻 PriorityQueue 구현

from queue import PriorityQueue
q = PriorityQueue() 

# 원소 삽입
q.put(3)
q.put(4)
q.put(1)

# 원소 삭제 및 반환
q.get() # 1

힙 (Heap)

최댓값, 최솟값을 빠르게 연산하기 위한 완전 이진 트리

✅ 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 함

📌 최소 힙(Min Heap)

루트 노드가 가장 작은 값을 가지며, 항상 부모 노드는 자식 노드보다 작은 값을 가짐 (부모 노드 >= 자식 노드)

💻 최소 힙 구현

import heapq
hq = []

# 삽입 - heapq.heappush(heap, item)
heapq.heappush(hq, 4)
heapq.heappush(hq, 1)
heapq.heappush(hq, 3)
heapq.heappush(hq, 7)

print(hq) # [1, 3, 4, 7]

# 삭제 - heapq.heappop(heap)
heapq.heappop(hq) # 1

📍 최소 힙으로 삽입, 삭제 과정 알아보기 !

삽입

완전 이진 트리를 만족하는 노드에 1 삽입

부모 노드인 5보다 1이 더 작으므로 최소 힙의 조건에 만족하도록 노드 위치 변경

1이 부모 노드인 2보다 더 작으므로 위의 과정과 동일하게 노드 위치 변경

삭제

1을 삭제

루트 노드가 비어있기 때문에 마지막 노드인 5로 채움

자식 노드인 2와 4가 5보다 더 작기 때문에 위치를 바꿔야 함.

4보다 2가 더 작으므로 2와 노드 위치를 바꿔주고, 최소 힙의 조건에 만족하므로 삭제를 종료함.

✔ 삽입, 삭제의 시간복잡도 힙의 조건을 만족하도록 재배치하는 연산은 보통 힙의 높이(h)에 비례하여 시간이 소요되므로 데이터가 n개일때, $O(log n)$의 시간이 소요됨.

📌 최대 힙(Max Heap)

루트 노드가 가장 큰 값을 가지며, 항상 부모 노드는 자식 노드보다 큰 값을 가짐 (부모 노드 <= 자식 노드)

💻 최대 힙 구현

hq = [1, 3, 4, 7] # 위에서 구현한 기존 힙

max_heap = []
for item in hq:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)
-> [(-7,7), (-4,4), (-3,3), (-1,1)]

heapq.heappop(max_heap)[1] # 7

Reference

• https://c4u-rdav.tistory.com/34
• https://velog.io/@mein-figur/Python%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq
• https://velog.io/@hsshin0602/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90priority-%ED%9E%99%ED%81%90heap

다이나믹 프로그래밍

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법

💡 DP 사용 조건 ✅ 큰 문제를 작은 문제로 나눌 수 있다. ✅ 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. ➡ 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 !! ex) 피보나치 수열

Top-Down

큰 문제를 해결하기 위해 작은 문제 호출

메모이제이션 (Memoization) : 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

➡ 한 번 구한 정보를 리스트에 저장하여 구현

📍 메모이제이션을 활용한 피보나치 수열 코드 (재귀적)

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

Bottom-Up

📌 다이나믹 프로그래밍의 전형적인 형태

작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구하기

DP 테이블 : 결과 저장용 리스트

📍 bottom up 방식을 이용한 피보나치 수열 코드 (for문 사용)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수를 반복문으로 구현
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

DP 문제 푸는 방법

✅ 저장하기 변수에 따른 결과를 DP 테이블에 저장하고 저장된 값을 재사용 !

✅ 변수 간 관계식 만들기 점화식을 만드는 것 ! 가장 중요한 부분 ⭐

📝 문제 풀어보기

1로 만들기

✏ 문제 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 4가지다.

1. X가 5로 나누어떨어지면, 5로 나눈다.
2. X가 3으로 나누어떨어지면, 3으로 나눈다.
3. X가 2로 나누어떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

4가지 연산을 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력 조건 첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000) 출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

입력 예시

26

출력 예시

3

🔑 답안

num = int(input())

# DP 테이블 초기화
dp = [0] * 30001

# 다이나믹 프로그래밍 진행 (bottom-up)
for i in range(2, x+1):
    # 현재 수에서 1을 빼는 경우
    dp[i] = dp[i-1] + 1
    # 현재 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    # 현재 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    # 현재 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i//5] + 1)

print(dp[num])

📍 26 - 1 = 25 26이 주어지면 25에서 1을 빼는 연산을 하면 되고 여기서 25에 걸리는 연산 횟수보다 1이 더 추가된다. ➡️ dp[i] = dp[i-1] + 1

📍 25 / 5 = 5 25는 5로 나누면 5가 되니까 5보다 연산 횟수가 1이 추가된다. ➡️ dp[i] = min(dp[i], dp[i//5] + 1)

📍 5 / 5 = 1 5는 5로 나누면 1이 되는데 dp[5 // 5] + 1 = dp[1] + 1이고 dp[1]은 0이 들어가 있으니까 1이 된다.

이렇게 같은 연산을 여러 번하는 과정이 있으니 매번 다시 계산하는 것이 아니라 DP 테이블에 저장해놓은 값을 활용하면 된다는 것을 이해하면 된다!

Reference

• 이것이 코딩 테스트다 with 파이썬
• https://doing7.tistory.com/75
• https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming
• https://velog.io/@hoonww/DP%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EB%B0%8F-%ED%99%9C%EC%9A%A9

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

✅ 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용

✅ 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음

💡순차 탐색 코드 구현

def sequential_search(n, target, array) :
    # 각 원소를 하나씩 확인
    for i in range(n) :
        # 현재의 원소가 찾고자 하는 원소와 동일할 경우
        if array[i] == target :
            # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)
            return i + 1       

input_data = input().split()
n = int(input_data[0]      # 원소의 개수
target = input_data[1]     # 찾고자 하는 문자열

array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

✔ 순차 탐색의 시간복잡도 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 특징이 있다. 따라서 데이터 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 $O(N)$

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

✅ 데이터가 무작위일 때는 사용❌

✅ 이미 정렬되어 있다면 매우 빠르게 데이터 찾을 수 있음

✅ 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

　　찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 찾기!

📌 Example 정렬되어 있는 데이터에서 4 찾기!

📍 시작점 : 0 / 끝점 : 9 / 중간점 : 4　($\frac{(0 + 9)}2$, 소수점 이하 제거)

중간점의 데이터는 8이므로 찾으려는 수 4보다 크다 ➡ 끝점을 옮겨서 범위를 줄여야겠다! ➡ 8 이후의 값은 8보다 크므로 8보다 한 칸 앞으로 끝점을 옮긴다. ➡ end = mid - 1

📍 시작점 : 0 / 끝점 : 3 / 중간점 : 1　($\frac{(0 + 3)}2$, 소수점 이하 제거)

중간점의 데이터는 2이므로 찾으려는 수 4보다 작다 ➡ 시작점을 옮겨서 범위를 줄여야겠다! ➡ 2 이하의 값은 2보다 작으므로 2보다 한 칸 뒤로 시작점을 옮긴다. ➡ start = mid + 1

📍 시작점 : 2 / 끝점 : 3 / 중간점 : 2　($\frac{(2 + 3)}2$, 소수점 이하 제거)

중간점의 데이터와 찾으려는 값이 같으므로 탐색을 종료한다!

💡이진 탐색 코드 구현

　　✏ 재귀 함수 사용

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    # 찾은 경우 중간점 안덱스 반환
    if array[mid] == target:
        return mid

    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)

    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

　　✏ 반복문 사용

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid

        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1

        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

✔ 이진 탐색의 시간복잡도

한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어듦 ➡ $O(logN)$ 이진 탐색은 한 단계를 고칠 때마다 확인하는 원소가 평균적으로 절반으로 줄어든다.

💡 백준 [1920] 수 찾기

이진 탐색 사용

n = int(input())
n_list = list(map(int, input().split()))
n_list.sort()

m = int(input())
m_list = list(map(int, input().split()))


def binary_search(target, data):
    start = 0
    end = n-1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return 1
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0

for tg in m_list:
    if binary_search(tg, n_list):
        print(1)
    else:
        print(0)

별 다른 풀이없이 이진탐색 코드 그대로 사용해주면 되는데, 이진탐색을 사용할 때 꼭 sort()를 해야한다는 것만 기억하면 될 것 같다.

• 찾는 값과 data[mid]가 같은 경우라면 값을 찾은 것!
• data[mid] < target 이라면 내가 찾는 값이 더 크니까 범위를 mid 뒤로 바꿔주기 위해 start = mid + 1로 설정
• data[mid] > target 이라면 내가 찾는 값이 더 작으니까 end 범위를 mid 앞으로 바꿔줘야 한다! end = mid - 1로 설정
  

이진 탐색 사용 ❌ (in 사용)

n = int(input())
n_list = set(map(int, input().split()))

m = int(input())
m_list = list(map(int, input().split()))

for num in m_list:
    if num in n_list:
        print(1)
    else:
        print(0)

n_list를 list로 한다면 시간 초과가 발생한다. list(map(int, input().split()) set(map(int, input().split())으로 하면 시간 초과없이 정답으로 처리된다!

데이터를 표현하고 관리하고 처리하기 위한 구조

• 삽입(Push) : 데이터를 삽입
• 삭제(Pop) : 데이터를 삭제

• overflow : 자료구조가 수용할 수 있는 데이터의 크기를 이미 채운 상태에서 삽입 연산을 수행할 때 발생
• underflow : 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생

스택

• 후입선출 (LIFO : Last In First Out) 구조
• 별도의 라이브러리 필요 ❌
• append()와 pop() 사용

큐

• 선입선출 (FIFO : First In First Out) 구조
• *deque 자료구조 사용 * from collections import deque queue = deque()
  • deque는 스택과 큐의 장점을 모두 합친 것인데 데이터 삽입, 삭제의 속도가 list 자료형에 비해 효율적이고 queue 라이브러리보다 간단함

탐색 알고리즘

DFS

Depth-First Search / 깊이 우선 탐색

• 한 방향으로 갈 수 있을 때까지 탐색하다가 더 이상 갈 수 없게 되면, 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색
• 되돌아가기 위해 스택 (Stack) 필요
  

💡 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end ='')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# graph 표현 (2차원 리스트 활용)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9

# DFS 함수 호출
dfs(graph, 1, visited)

>> 1 2 7 6 8 3 4 5

• 실제로는 스택을 쓰지 않아도 된다 !
• 데이터의 개수가 N개인 경우 O(N)의 시간 소요

BFS

Breadth-First search / 너비 우선 탐색

• 시작 노드로부터 가까운 노드를 먼저 탐색하고 멀리 떨어져 있는 노드는 나중에 탐색하는 순회 방법
• 큐(Queue)를 사용해서 구현

💡 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

  from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드 방문 처리
    visited[v] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = ' ')
        # 해당 원소와 연결되어 있고 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# graph 표현
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

>> 1 2 3 8 7 4 5 6

• deque 라이브러리 사용
• O(N) 시간 소요
• 일반적인 수행 시간은 DFS보다 좋은 편

*📌 최종 정리 *

Reference

• 이것이 코딩 테스트다 with 파이썬
• https://hong-devbox.tistory.com/4
• https://yoongrammer.tistory.com/46

• 기존의 sequence transduction 모델들은 encoder와 decoder를 포함한 RNN, CNN을 기반으로 함.

• 좋은 성능을 보인 모델들은 attention mechanism을 통해 encoder와 decoder를 연결했음.

➡ attention mechanism만을 사용한 Transformer을 제안 (RNN or CNN을 사용하지 않음)

① machine translation (기계 번역) task에서 성능이 좋음

② 학습할 때, 더 많은 병렬화 / 더 적은 시간 소요

③ 일반화 성능이 좋음 ➡ constituency parsing (구문 분석)에서도 결과가 좋았음

Introduction

RNN, LSTM, gate RNN은 language modeling, machine translation과 같은 sequence modeling과 transduction problem에서 SOTA를 달성함. Recurrent model은 일반적으로 input과 output suqence의 symbol position에 따라 계산함. 계산 단계의 위치에 따라 이전 hidden state $h_{t-1}$과 position t가 input인 hidden state $h_t$가 생성됨.

➡ t를 계산하려면 순차적으로 t 이전의 output들이 다 계산되어야 최종 output을 생성할 수 있음.

➡ 이러한 순차적인 특성으로 인해 병렬화를 막고, sequence가 길어질수록 더 취약해짐.

최근에는 factorization tricks와 conditional computation으로 계산 효율성을 개선하고자 하였지만 근본적인 제약이 여전히 남아있음.

Attention mechanism은 input 또는 ouput sequence의 거리에 관계없이 dependencies(의존성)을 모델링하여 sequence modeling에 중요한 부분이 되었지만, recurrent network와 결합하여 사용해서 효율적인 병렬화를 이룰 수 없음.

➡ recurrence를 제거하고 input과 output 사이의 global dependencies를 학습하기 위한 attention mechanism만을 사용한 모델 transformer를 제안

Background

sequential 연산을 줄이기 위해 여러 노력을 했지만, 모두 CNN을 기반으로 함. 입력과 출력 위치에 대해 병렬로 hidden representation을 계산함. Extended Neural GPU, ByteNet, ConvS2S와 같은 모델들은 입력과 출력 위치 사이의 관련성을 학습하는 과정에서 먼 거리의 위치 간의 의존성을 학습하기 어려워지는 단점이 있음.

Self-attention은 sequence의 representation을 계산하기 위해 single sequence의 다른 위치들을 연관시키는 attention mechanism. End-to-end memory networks는 sequence-aligned recurrence 대신 recurrent attention mechanism을 기반으로함.

➡ Transformer는 self attention만을 사용해서 input과 output의 representation을 계산

Model Architecture

대부분의 sequence transduction model들은 encoder-decoder의 구조를 가짐. 입력 $(x_1, ..., x_n)$은 인코더에 의해 $z=(z_1, ... , z_n)$으로 표현됨. 인코더로 표현된 z를 활용하여, 한 번에 한 Element 씩 Output Sequence $(y_1, ..., y_m)$이 생성됨.

• auto-regrssive : 생성된 Symbol은 다음 생성 과정에서 추가 입력으로 사용됨.

Transformer는 encoder와 decoder 모두에서 스택으로 쌓인 self-attention 레이어와 point-wise fully connected layer를 사용하는 아키텍처를 따름.

✅ Encoder

• N = 6의 동일한 layer stack으로 구성- 각 layer에는 2개의 sub-layer → multi-head self attention / fully connected feed-forward network

• 각 Sub-Layer는 Residual Connection 및 Layer Nomalization 적용

즉, sub-layer의 output은 LayerNorm(x + Sublayer(x))이고, Sublayer(x)는 sub-layer 자체의 function (multi-head attention or FFN)

• Residual Connection 적용을 용이하게 하기 위해, Sub-layer, Embedding, Output Dimension을 512로 통일

Residual Connection 적용을 위해선, Input과 연결된 Output의 Dimenstion이 동일해야 함

✅ Decoder

• N = 6의 동일한 layer stack으로 구성

• 각 layer는 3개의 sub-layer → Masked Multi-head self attention / Multi-head self attention / fully connected feed-forward network

1) Masked Multi-head self attention

☑ masking

이후의 positions에 attending하는 것을 막기 위해 decoder stack에 있는 self-attention sub-layer를 수정함.

알려진 output에만 의존 → 현재 위치 i 이후에 있는 정보는 i에 영향 X

Output Embedding은 One Position씩 Offset

2) encoder의 output에 대해 Multi-head self attention

3) Position-wise Fully Connected Feed-Forward Network

• 각 Sub-Layer는 Residual Connection 및 Layer Nomalization 적용

✅ Attention Attention function은 query와 key-value 집합 쌍을 query, keys, values, output이 모두 벡터인 output에 매핑함. output은 values의 weighted sum에 의해 계산되고, 각 weight는 key에 해당하는 query의 compatibility function에 의해 계산됨.

✅ Scaled Dot-Product Attention Input은 $d_k$차원의 query, key와 $d_v$차원의 value로 구성됨. key와 query의 dot product를 계산하고 루트 $d_k$로 나눠서 softmax function을 적용한 후, value의 weight를 계산함.

주로 사용하는 attention function은 additive attention과 dot-product(multiplicative) attention이 있음.

1) Dot-product attention - scaling factor인 $\frac{1}{\sqrt{d_k}}$를 제외하면 동일

2) Additive attention - single hidden layer가 있는 FFN을 사용하여 compatibility function을 계산

➡ 두 방법은 이론적으로 복잡성이 비슷하지만, dot-product attetion은 matrix를 통해 최적화된 연산을 구현할 수 있기 때문에 더 빠르고 공간 효율적임.

💡 Multi-Head Attention

$d_{model}$ 차원의 query, key, value를 사용하여 single attention을 수행하는 대신, 각각 $d_k$, $d_k$, $d_v$ 차원에 대해 학습된 서로 다른 linear projection을 사용하여 query, key, value를 h번 linear projection하는 것이 더 좋을 것이라는 것을 알게 됨. 이러한 query, key, value의 각 projection version에서 attention funtction을 병렬로 수행하여 $d_v$차원 output을 생성하고, 이를 concat하여 다시 $d_{model}$ 차원의 output을 생성함.

Multi-head attention을 통해 모델은 다른 position의 서로 다른 representation subspaces의 정보에 공동으로 attend할 수 있음.

h = 8개의 병렬 attention layer 혹은 head를 사용하고 $d_k$ = $d_v$ = $d_{model}/h = 64$를 사용함. 각 head의 축소된 차원으로 인해 전체 계산 비용은 전체 차원을 갖는 single-head attention 비용과 비슷함.

Applications of Attention in our Model

1) encoder-decoder attention layer

query는 이전 decoder layer에서, key와 value는 encoder의 output에서 얻음. → decoder의 모든 위치가 input sequence의 모든 위치에 배치될 수 있음.

2) Encoder self-attention layer

key, value, query는모두 같은 위치에서 나오고, 이 위치는 encoder의 이전 layer의 output임.

encoder의 각 위치에서 이전 layer에 모든 위치에 관여할 수 있음.

3) Decoder self-attention layer

decoder에서 각 위치는 해당 position까지 포함해서 모든 위치에 관여할 수 있음. auto-regressive property를 보존하기 위해 decoder에서 leftward information flow를 막아야 함. scaled dot-product attention 안에서 올바르지 않은 연결에 해당하는 모든 softmax의 input의 모든 value를 masking(-)해서 구현함.

➡ 이전 위치에서 생성한 정보만을 사용하여 단어를 생성 / 미래 시점의 단어를 볼 수 없음

Position-wise Feed-Forward Networks

encoder와 decoder의 각 layer에는 fully connected feed-forward network가 있음. ReLU activation이 있는 두 개의 선형 변환으로 구성됨. 선형 변환은 여러 위치에서 동일하게 이루어지지만, layer마다 다른 파라미터를 사용함.

Embeddings and Softmax

다른 sequence trasduction model과 비슷하게, 학습된 embedding을 사용해서 input token과 output token을 $d_{model}$차원의 벡터로 변환함. 일반적으로 학습된 linear transformation과 softmax 함수를 사용해서 decoder output을 다음 token의 예측확률로 변환함.

Positional Encoding

Transformer에는 recurrence와 convolution을 사용하지 않음. sequence의 위치 정보가 없기 때문에 상대적이든 절대적이든 position에 대한 정보를 추가해야 함.

➡ encoder와 decoder stack 아래 input embedding에 "positional encodings"를 추가함.

Positional encoding은 embedding과 동일한 차원을 가지기 때문에 이 둘을 합할 수 있음.

( 단어의 의미를 담은 임베딩과 단어의 위치 정보를 담은 위치 인코딩을 결합 → 모델이 입력 시퀀스의 단어들을 상대적인 위치 정보를 유지하며 처리할 수 있음.)

pos는 토큰의 위치, i는 차원을 나타냄 PE(pos+k)는 PE(pos)의 선형 함수로 표현될 수 있기 때문에 모델이 상대적인 위치를 쉽게 학습할 수 있을 것이라고 생각해서 위의 함수를 사용함.

더 긴 sequence에서도 추론 가능하기 때문에 sinusoidal version 선택.

Why Self-Attention

• self-attention layer와 recurrent, convolutional layer와 비교

방법은 symbol representations(x1, ..., xn)의 one variable-length sequence를 같은 길이 (z1, ..., zn)으로 mapping

Self attention을 사용한 이유

① layer별 총 계산복잡도

② 요구되는 최소한의 sequential 연산의 수로 측정된 병렬 연산량

③ 네트워크에서 장거리 의존성(long-range dependencies) 사이의 path 길이 (신호가 전달되는 경로의 길이)

많은 시퀀스 변환 task에서 장거리 의존성(long-range dependencies)을 학습하는 것이 주요 과제임.

경로의 길이는 입력 시퀀스와 출력 시퀀스 사이의 모든 위치들 간에 신호가 전달되는 데에 영향을 미치고, 경로의 길이가 짧을수록 장거리 의존성을 학습하는 것이 더 쉬움.** → maximum path length를 비교함.**

Training

💡Training Data and Batching

• 약 450만 개의 문장 쌍으로 구성된 표준 WMT 2014 영어-독일어 datatset에 대해 학습함.

• byte-pair encoding을 통해 인코딩, 약 37,000 토큰의 공유 sourcetarget vocabulary를 가짐.

• 각 훈련 배치에는 약 25000개의 소스 token과 25000개의 대상 token을 포함하는 문장 쌍 세트가 포함됨.

💡Optimizer

• $β_1$ = 0.9, $β_2$ = 0.98, ϵ = $10^{-9}$인 Adam optimizer 사용함.

• 다음 식에 따라 학습을 진행하면서 learning rate를 변화시킴.

** 💡Regularization**

• Resicual Drop

encoder와 decoder에 여러 개의 sub-layer의 출력에 dropout 적용한 뒤, 원래의 sub-layer의 입력과 합쳐서 정규화 수행

인코더와 디코더의 모든 stack에 대해 embedding과 positional encoding의 합에 dropout 적용

• Label Smoothing

perplexity는 해치지만 BLEU score가 높아지는 결과를 보임.

Results

💡Machine Translation

💡Model Variation

💡English Constituency Parsing

Conclusion

recurrent layer를 대체하여 attention 기반의 sequence transduction model을 제안함. 주로 인코더-디코더 아키텍처에서 사용되는 RNN 레이어들을 multi-heade self-attention으로 대체함. Translation task의 경우, Transformer는 recurrent, convolutional layer기반의 아키텍쳐들보다 훨씬 빠르게 훈련할 수 있음. WMT 2014 English-to-German과 WMT 2014 English-to-French translation tasks에서 SOTA 달성. 텍스트, 이미지, 오디오, 비디오와 같이 상대적으로 큰 input과 output을 요구하는 task들을 효율적으로 처리하기 위해 확장할 수 있을 것임.

Abstract

large data set으로부터 단어들의 연속적인 벡터 표현을 계산하기 위해 두 가지 새로운 모델 구조를 제안함.

representation의 quality는 단어 유사도 측정되어지고 결과는 이전에 가장 성능이 좋았던 다른 타입의 신경망 기반으로 한 기술과 비교되어짐.

➡ 더 낮은 연산 비용을 사용해서 정확도에서 큰 성능 향상을 관찰 + 16억 단어 데이터셋에서 high quality word vectors를 학습하는 데 하루가 안 걸림.

vectors가 syntactic and semantic word similarities를 측정하기 위한 테스트셋에서 SOTA 달성

Introduction

현재(2013년 기준) 많은 NLP system과 techiniques에서 단어를 atomic unit으로 취급함. ➡ 단어 간 유사성의 개념 X / vocabulary에서 index로 표현됨.

📌 word embedding

one-hot encoding 표현하고자 하는 단어를 1, 나머지 단어를 0으로 채운 (1, 단어 개수) 크기의 벡터

✅ 한계점 ▶ 단어 간의 상관관계 및 유사도 판단 X $(W^귤)^TW^배 = (W^귤)^TW^감 = 0$

▶ sparse한 representation vector (실제로 의미있는 표현이 희소함 - 희소 표현 문제)

distributed representation 신경망을 기반으로 단어를 여러 차원에 분산하여(distributed) 표현하는 방법

• 단어 벡터간 유사도 및 Syntactic regularities 계산 가능
• '비슷한 위치에서 등장하는 단어들은 비슷한 의미를 가진다'는 가정
• word2vec (https://word2vec.kr/search/)

이러한 방식의 장점

① simplicity

② robustness

③ 대량의 데이터에서 훈련된 simple model이 적은 데이터로 학습된complex system보다 좋은 성능

예를 들어, 통계적 언어 모델링에 사용되는 N-gram 모델

📌 N-gram n개의 연속적인 단어 나열

example> An adorable little boy is spreading smiles unigrams : an, adorable , little , boy , is , spreading , smiles bigrams : an adorable , adorable little , little boy , boy is, is spreading , spreading smiles trigrams : an adorable little, adorable little boy, little boy is, boy is spreading, is spreading smiles 4-grams : an adorable little boy, adorable little boy is, little boy is spreading, boy is spreading smiles

✅ 그러나 simple technique은 많은 task에 한계가 있음.

예를 들어, automatic speech recognition 관련 도메인 데이터의 양이 제한적임. 성능은 보통 high quality transcribed speech data의 크기에 영향을 받는데, machine translation에서 많은 언어에 대한 corpora는 몇 십억 단어 이하임.

➡ basic technique의 simple scaling up에 의미있는 진전 X, more advanced technique에 집중해야 함.

최근 몇 년간 machine elarning technique의 발전으로 더 많은 데이터셋을 더 복잡한 모델에 학습시키는 것이 가능해졌고 이는 일반적으로 단순한 모델에 비해 좋은 성능을 보임.

단어의 분포 표현을 사용하는 것이 가장 성공적인 컨셉임. (ex. 언어 모델 기반 신경망은 N-gram model을 능가함.)

Goals of the Paper

✅ 연구의 주요 목표

: 수십억 단어의 큰 데이터셋과 수백만 단어의 vocabulary에서 high-quality word vector를 학습하는데 사용한 기술 소개

(이전 연구에서는 이렇게 큰 데이터셋으로 훈련한 사례❌, 단어 벡터의 차원도 50-100이었음.)

비슷한 단어들이 서로 가까이 위치하도록 기대 ➕ 단어 간에 다양한 유사성 정도를 고려함

이러한 다양한 유사성 정도는 inflectional language의 context에서 이전에도 관찰됨.

example> 명사는 multiple word endings를 가질 수 있고, original vector space의 subspace에서 비슷한 단어를 찾을 때 similar endings를 찾을 수 있음.

단어 표현의 유사성은 simple syntactic regularities을 뛰어넘음. 단어 벡터에 수행하는 word offset technique을 사용해서 vector(”King”) - vector(”Man”) + vector(”Woman”) = vector("Queen") 와 같은 연산 수행

단어 간의 선형 규칙을 유지하는 새로운 모델 아키텍쳐를 개발하여 벡터 연산의 정확도를 극대화하고자 함.

syntactic & semantic regularities를 측정하기 위한 new comprehensive test set 설계하고, 많은 regularities이 높은 정확도로 학습될 수 있음.

훈련 데이터의 양과 단어 벡터의 차원이 학습 시간과 정확도에 어떤 영향을 미치는지 논의하고자 함.

Privious Work

① NNLM(neural network language model)을 추정하기 위한 모델 아키텍쳐

➡ linear projection layer와 non-linear hidden layer로 구성된 feedforward neural network 구성

➡ 단어 벡터 표현과 통계적 언어 모델을 학습하고자 함.

② single hidden layer로 구성된 neural network를 사용하여 단어 벡터 학습 → 단어 벡터를 사용하여 NNLM을 학습

➡ 전체 NNLM 구축 필요 X

Model Architecture

단어의 연속적 표현을 추정하기 위해 Latent Semantic Analysis (LSA)와 Latent Dirichlet Allocation (LDA) 같은 여러 모델이 제안됨.

본 논문에서는 neural networks에 의해 학습된 단어의 distributed representations에 집중하고자 함.

: 이전 연구에서 LSA에 비해 단어 간의 선형 규칙을 보존하는 데 더 나은 성능을 보였음.

모델을 완전히 훈련하기 위해 액세스해야 하는 파라미터의 수를 모델의 computational complexity로 정의함.

→ 정확도 최대화, 계산 복잡도 최소화

훈련 복잡도 O = E × T × Q (E : epoch(3-50), T : training set 내의 단어 수(최대 1B), Q : 각 모델 아키텍쳐에 따라 달라짐)

stochastic gradient descent와 backpropagation를 사용하여 모델 훈련

Feedforward Neural Net Language Model (NNLM)

probabilistic feedforward neural network language model

✅ input, projection, hidden, output layers로 구성됨.

✅ input layer : N 이전 단어는 1-of-V coding을 사용해서 인코딩 (V : vocabulary의 size)

✅ input layer는 shared projection matrix를 사용하여 차원수 NxD인 projection layer P로 투영됨.

각 training example당 computational complexity : Q = N × D + N × D × H + H × V (dominating term : HxV)

N x D: input data의 size와 관련된 항 N x D x H : 입력 데이터의 표현 크기와 은닉 레이어 크기를 곱한 값 모델의 파라미터 크기와 관련, 학습 및 예측 과정에서 계산이 많이 필요함 H x V (domination term) : output layer의 size와 관련된 항 출력 레이어의 크기가 모델의 복잡성에 큰 영향→ dominating term computational complexit을 피하기 위한 해결책

✔ 소프트맥스의 hierarchical versions 사용

✔ 훈련 중에 정규화되지 않는 모델(non-normalized models)을 사용하여 정규화된 모델을 피하는 것

➡ vocabulary의 binary tree representations 사용하면 평가해야 하는 output unit 수를 log2(V)정도로 줄일 수 있음.

➡ 대부분의 complexity는 N x D x H 항에서 발생

Recurrent Neural Net Language Model (RNNLM)

언어 모델에 기반한 RNN은 feedforward NNLM의 한계를 극복하기 위해 제안됨.

✔ context length를 지정해줘야 함 → RNN은 context length 자동 처리

✔ 이론적으로 RNN은 shallow neural networks 보다 더 복잡한 패턴을 효율적으로 표현할 수 있음.

✔ RNN은 projection layer 존재 X / input, hidden, output layer만 존재

💡 time-delayed connections을 이용해 hidden layer를 자신에게 연결하는 recurrent matrix

➡ 이전 time step에서의 hidden layer state와 현재 input을 기반으로 업데이트된 hidden layer로 과거 정보를 나타냄 (과거의 정보가 현재에 영향)

➡ short term memory를 형성하도록 함.

각 training example당 computational complexity: Q = H × H + H × V

(단어 표현 D는 hidden layer 차원 H와 동일 → hierarchical softmax를 사용하면 H x V는 H × log2(V)로 줄일 수 있음.)

Parallel Training of Neural Networks

큰 데이터셋을 학습하기 위해 large-scale distributed framework인 DistBelief 위에 여러 모델 구현 (feedforward NNLM + α)

➡ 같은 모델의 multiple replicas를 병렬로 수행

➡ 각 replica는 gradient를 업데이트를 모든 파라미터를 관리하는 centralized server를 통해 동기화함.

New Log-linear Models

단어의 distributed representations를 학습하는 2가지 새로운 모델 아키텍쳐 제안 (computational complexity 최소화 시도)

Continuous Bag-of-Words Model

feedforward NNLM과 유사 - non-linear hidden layer 제거 / 모든 단어에 대해 공유된 projection layer 사용

➡ 모든 단어들은 동일한 위치에 투영 (분산 표현 평균화 / 단어의 순서 영향 ❌)

💡 CBOW (context의 continuous distributed representation 사용)

input> 현재 단어를 중심으로 각각 4개의 future words와 4개의 history words

training criterion> 현재 단어를 올바르게 분류

→ 단어 임베딩(단어의 분산 표현)을 학습하기 위해 log-linear classifier 구축

training complexity> N x D + D x log2(V)

input과 projection layer 사이의 가중치 행렬은 NNLM에서의 방식과 동일하게 모든 단어 위치에 공유됨.

CBOW : 주변 단어들을 통해 현재 단어 예측

Continuous Skip-gram Model

context를 기반으로 현재 단어를 예측X → 같은 문장에서 다른 단어에 기반하여 분류

각각의 현재 단어를 입력으로 사용하여 continuous projection layer와 log-linear classifier를 갖는 모델을 만들고, 현재 단어의 앞뒤로 일정 범위 내의 단어 예측

✅ 범위 증가 → resulting word vectors의 quality 🔺 , computational complexity 🔺

현재 단어와 더 멀리있는 단어는 가까이 있는 단어보다 관련성 🔻 (가까이 있으면 관련성 🔺 , 멀리 있으면 관련성 🔻)

→ 멀리 있는 단어들은 training examples에서 더 적게 샘플링하여 멀리 있는 단어에 가중치를 적게 줌

training complexity of this architecture: Q = C x (D + D x log2(V)) (C: 단어간의 최대거리)

Skip-Gram : 현재 단어를 통해 주변 단어 예측

Results

Conclusion

CBOW와 skip-gram이라는 새로운 word embedding 학습 방법 제안

많은 계산량을 요구하는 기존의 신경망 모델 구조를 사용하지 않고, 간단한 구조를 사용해서 높은 성능을 보임

높은 성능의 word vector가 NLP task에서 매우 중요한 요소가 될 것임

📌 JOIN이란?

• 두 개 이상의 테이블간의 데이터를 결합하여 데이터를 검색하는 방법
• 검색하고 싶은 컬럼이 다른 테이블에 있을 경우 주로 사용
• 여러 테이블을 마치 하나의 테이블인 것처럼 활용하여 효율적으로 조회할 수 있음

INNER JOIN

• 기본 JOIN (아무런 명시 없이 JOIN을 쓰면 INNER JOIN이 적용됨)
• 두 테이블 간의 일치하는 행만을 반환
• 두 테이블을 JOIN할 때, 두 테이블에 지정한 열의 데이터가 모두 있어야 함 (ON절)

SELECT * FROM TableA A
INNER JOIN TableB B ON A.key = B.key 

OUTER JOIN

• 두 테이블을 JOIN할 때, 1개의 테이블에만 데이터가 있어도 결과가 나옴
  

OUTER JOIN의 종류

✅ LEFT OUTER JOIN ✅ RIGHT OUTER JOIN ✅ FULL OUTER JOIN

LEFT OUTER JOIN

왼쪽 테이블의 모든 값이 출력되는 JOIN

LEFT Table을 기준으로 가져오는데 RIGHT Table에 없으면 null

LEFT Table만(교집합 제외)을 가져오고 싶은 경우라면, LEFT OUTER JOIN을 한 후에 RIGHT TABLE에 NULL인 값들만 가져오면 됨 (WHERE문 추가)

  SELECT * FROM TableA A
  LEFT JOIN TableB B ON A.key = B.key 
  WHERE B.key IS NULL

RIGHT OUTER JOIN

오른쪽 테이블의 모든 값이 출력되는 JOIN

RIGHT Table을 기준으로 가져오는데 LEFT Table에 없으면 null

RIGHT Table만(교집합 제외)을 가져오고 싶은 경우라면, RIGHT OUTER JOIN을 한 후에 LEFT TABLE에 NULL인 값들만 가져오면 됨 (WHERE문 추가)

  SELECT * FROM TableA A
  RIGHT JOIN TableB B ON A.key = B.key 
  WHERE A.key IS NULL

FULL OUTER JOIN

왼쪽 또는 오른쪽 테이블의 모든 값이 출력되는 JOIN

  SELECT * FROM TableA A
  FULL OUTER JOIN TableB B ON A.key = B.key

CROSS JOIN

• 한쪽 테이블의 모든 행과 다른 쪽 테이블의 모든 행을 JOIN
• CROSS JOIN 결과의 전체 행 개수는 두 테이블의 각 행의 개수를 곱한 수가 됨

  SELECT * FROM TableA
  CROSS JOIN TableB

💡 on절 존재 X → 모든 행에 대해서 match하기 때문에 💡 Where 절이 포함되면 INNER JOIN으로 작동함

SELF JOIN

• 자기 자신과 조인하므로 1개의 테이블을 사용

• 테이블의 행을 같은 테이블 안에 있는 다른 행과 JOIN

• 계층적인 구조를 테이블화 할 경우

  SELECT A.col, B.col from TableA as A
  JOIN TableA as B on A.col = B.col

  

  📍 staff_id와 manager_id와의 관계를 연결할 수 있게 해줌

프로그래머스 SQL 고득점 kit

✏ JOIN > 오랜 기간 보호한 동물 (1)

https://school.programmers.co.kr/learn/courses/30/lessons/59044

ANIMAL_INS 동물 보호소에 들어온 동물의 정보를 담은 테이블 ANIMAL_OUTS 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블

** 조건 ** ✔ 입양을 못 간 동물 조회 ✔ 가장 오래 보호소에 있었던 동물 3마리 ✔ 보호 시작일 순으로 조회

이 문제에서 가장 관건인 것은 입양을 못 간 동물을 조회하는 것이다. 그냥 평소 JOIN 문제를 풀던대로 무작정 JOIN문을 작성하면 입양을 간 동물들만 조회되게 된다. (ANIMAL_INS과 ANIMAL_OUTS를 INNER JOIN하게 되면, 입양 보낸 동물의 정보가 나오기 때문) 따라서, ANIMAL_INS를 기준으로 LEFT JOIN하여 ANIMAL_OUTS에는 NULL값인 데이터들을 조회해야 한다.

  SELECT I.NAME, I.DATETIME FROM ANIMAL_INS AS I
  LEFT JOIN ANIMAL_OUTS AS O ON O.ANIMAL_ID = I.ANIMAL_ID
  WHERE O.DATETIME IS NULL
  ORDER BY DATETIME 
  LIMIT 3

REFERENCE

• https://sql-joins.leopard.in.ua/
• https://hongong.hanbit.co.kr/sql-%EA%B8%B0%EB%B3%B8-%EB%AC%B8%EB%B2%95-joininner-outer-cross-self-join/
• https://www.devart.com/dbforge/sql/sqlcomplete/sql-cross-join.html
• https://doh-an.tistory.com/30
• https://www.sqlservertutorial.net/sql-server-basics/sql-server-self-join/

linearity assumption은 가정일 뿐, 언제나 선형 모형을 따를 수는 없습니다. 따라서 이번 챕터에서는 항을 추가하거나, transformation을 함으로써 비선형성을 따르는 모형들을 살펴보고자 합니다.

Polynomial Regression

종속변수와 독립변수가 선형을 따르지 않을 경우 단순 선형회귀 모형을 적용하게 되면, 적합하지 않을 수 있습니다. 다항 회귀는 비선형 곡선을 생성할 수 있게 해주어 한계점을 극복할 수 있습니다.

Step Functions

X의 범위에 따라 구간별로 다른 상수를 fitting하는 것을 Piecewise polynomial이라고 합니다. 이때 구간별로 나누는 point들을 knots 또는 cut off point라고 부릅니다. constant가 바뀌는 곳에서 cut off를 찾으면 되고, cut off를 통해 더 적은 차수를 사용할 수 있게 되어 더 간단한 식으로 fitting 할 수 있습니다. 밑에 식에 적용하면 $c_1, c_2, ... , c_k$가 cutpoints가 됩니다.

🔼 선형 모델에 fitting 시킨 식

Regression Splines

Piecewise Polynomials

X의 전체 범위에 high-degree의 다항식을 fitting시키는 대신, piecewise polynomial는 X의 범위를 range에 따라 나누어 고차항의 식을 저차원으로 fitting 시킵니다.

Regression Splines

Piecewise polynomial의 경우 knot에서 continuous하지 않습니다. Regression Spline은 knot에서 연속이라는 조건을 추가하여 다항식을 fitting하는 것입니다.

🔼 파란색 선은 underline, 초록색 선은 model fitting의 결과, dot은 observation

첫 번째에서 두 번째 그림으로 갈 때는 continuity assumption을 적용한 것입니다. 따라서 Discontionous 했던 그래프가 Continuous하게 바뀌게 되었죠. 그런데 미분불가능한 peak point가 있어 미분한 그래프가 discontinous하게 됩니다. 세 번째 그림으로 넘어가 미분한 curve가 연속이 되도록 합니다. 이 미분하는 과정을 반복하게 됩니다.

세 번째 그래프에서 Cubic Spline은 Age가 커질수록 CI가 넓은 것을 확인할 수 있습니다. 더 좁은 CI를 위해 Natural cubic spline을 적용한 것이 빨간색 선입니다.

The Spline Basis Representation

K개의 knot를 가진 cubic spline에서 우리는 intercept 와 $3+k$ predictors로 least squares regression을 해야 합니다. $X,X^2,X^3,h(X,ξ1),...,h(X,ξ_K)$의 form을 사용하게 되는데 $h(x,ξ) = (x −ξ)^3+$ 과 같습니다. (total of K + 4 regression coefficients.)

natural spline은 가장 작은 knot보다 작은 region과 가장 큰 knot보다 큰 region은 cubic이 아니라 linear하게 적합하는 제약 조건을 추가한 모형을 말합니다.

Smoothing Splines

smoothing spline은 주어진 input의 unique한 모든 값을 knots로 사용합니다. 따라서 Smoothing spline을 구현하는 것은 모든 unique한 X값을 knots로 사용하는 Natural Cublic Spline을 구현한 것과 같습니다.

$RSS = \sum_{i}(y_i - g(x_i))^2$ 일 때 우리는 RSS를 작게 만들기를 바랍니다.

$\lambda$가 0이면 OLS fitting과 같게 되고, $\lambda$가 커질수록 g는 더 smooth해집니다. 여기서 $\lambda$를 조절함에 따라 bias, variance trade-off가 나타나게 됩니다.

Local regression

local regression은 전체 데이터를 사용하지 않고 local한 data를 사용하는 동시에 그 local 안에서도 다른 weight를 적용하는 방법론입니다.

그래프를 통해 자세히 설명하자면, 각 point마다 다른 weight를 가지게 되는데 이때 target point와 가깝다면 weight값이 올라가고, 멀어지면 weight값이 내려가게 됩니다. 선택되지 않은 점들은 weight가 0이 되는 것입니다.

다음과 같이 다양한 weight function이 있지만, weight ftn에 따라 크게 달라지지는 않습니다.

local regression의 장점은 모든 data에 fit한 function을 요구하지 않는다는 것고 단점은 다른 method들에 비해 data point가 많아야 한다는 것입니다. 이는 특히 dimension이 커질수록 많이 필요하게 됩니다.

같은 data point인데도 불구하고 dimension에 따라 달라지는 것을 볼 수 있는데, 1D에서는 촘촘하지만 dimension이 커질수록 같은 데이터 개수라도 sparse해지는 것을 확인할 수 있습니다 그래서 dimension이 커질수록 데이터의 개수가 많이 필요하게 됩니다.

Generalized Additive Models

GAMs는 standard linear model을 각 variable의 비선형 함수들을 통해 확장한 것을 말합니다. normal dstn을 따르지 않을 때, link ftn을 사용하는 것입니다.

GLM의 대표적인 예시인 Logistic regression의 경우 link function은 다음과 같은 형태를 가집니다.

smoothing의 첫 번째 그래프를 보면 age와 edu가 고정되어있을 때의 그래프를 볼 수 있습니다.

세 번째 그래프를 보면 CI(Confidence Interval)이 extreme한 것을 볼 수 있는데, 이는 250 초과하는 급여를 받은 데이터가 존재하지 않고 0만 존재했기 때문이라고 합니다. 위의 식을 보면, 250이 넘으면 1 그게 아니라면 (else) 0으로 coding 했기 때문에 이렇게 나타났다는 것을 알 수 있습니다.

그래서 $<HS$ 라는 카테고리를 제거한 그래프입니다.

최근 LM들은 긴 contexts를 input으로 받을 수 있기는 하지만, 그것을 얼마나 잘 활용하는지에 대해서는 잘 알고 있지 않다.

우리의 input text 내에 관련된 정보가 있는 2가지 task에 대해 성능을 분석함.

• multidocument question answering
• key-value retrieval
  

관련 정보가 input context의 시작 또는 끝에 있는 것이 성능 🔺

중간에 있는 정보에 접근해야 할 경우 성능🔻

긴 context를 다루는 모델에서도 입력 context가 길어질수록 성능 🔻

💡 논문에서 하고자 하는 일

• LM이 input context를 어떻게 활용하는 지에 대한 더 나은 이해 제공
• long context model을 평가하기 위한 새로운 평가 프로토콜 제공

Introduction

LM은 일반적으로 Transformer로 구현 (입력 시퀀스의 길이에 따라 self-attention complexity가 제곱으로 증가 → 긴 시퀀스 처리 불가능)

하드웨어 개선 및 알고리즘 발전 → larger context windows 가능 & downstream task를 어떻게 할지에 대한 문제가 남아있음

experiment

💡multidocument question answering

모델이 제공된 문서를 기반으로 추론하고 관련 정보를 찾아 주어진 질문에 답하는 task

input context size와 관련된 정보의 위치를 변경하며 모델 성능 평가

• input context에 더 많은 문서를 추가하여 input context length 증가시킴
• 관련된 정보의 위치를 context의 처음, 중간, 끝으로 변경해가면서 배치

위치 정보를 변화시켰을 때의 성능 그래프

관련 정보가 context의 처음과 끝에 있을 때 성능이 올라가고, input context의 중간에 있는 정보에 접근해야 할 경우, 성능이 크게 저하됨. (문서 없이 예측하는 것보다 성능이 낮아짐)

• extended-context model이라고 해서 input context를 더 잘 활용하는 것은 아님.

(context가 길어질 수록 성능이 점차 낮아짐)

🤔 Given that language models struggle to retrieve and use relevant information in the multi-document question answering task, to what extent can language models even retrieve from their input contexts❓

✔️ input context에서 retrieve matching token을 최소한의 basic ability로 testbed 설계함. ✔️ JSON-formatted key-value pairs을 받고 특정 키의 연결된 값을 반환

❓ 왜 context 중간에 관련 정보가 있으면 정보에 접근하는 데 어려움이 생길까?

1️⃣ 모델 구조의 역할 (decoder-only vs encoder-decoder)

encoder-decoder 모델이 training time sequence length 내에서 평가될 때 input context 내에 관련 정보의 위치 변화에 대해서는 robust함. 그러나 training 때 본 길이보다 긴 시퀀스가 주어지면 평가될 때 U자형 곡선을 보임. 2️⃣ query-aware contextualization

query-aware contextualization(쿼리를 문서나 key-value 쌍의 앞이나 뒤에 위치하게 함)은 모델이 e synthetic key-value task를 완벽하게 수행하지만, multi-document QA에 미미함. 3️⃣ instruction fine-tuning

instruction fine-tuning 없이도 input context와 관련된 정보의 위치의 다양함은 U자 곡선을 보임.

✔️ 추론 ↔ 정보 추가 (trade off 관계)

✔️ 정보의 양이 일정한 수준에 도달하면 결과가 더 이상 크게 변화하지 않음

Language Models

대부분의 LM은 Transformer의 구조로 구현되어있음.

• input contexts가 self-attention으로 인코딩 되어있어 시간과 메모리 복잡도가 input의 길이의 제곱적으로 증가함.
• 긴 시퀀스에 적용하기에 한계가 있음.
• 작은 context window를 사용 → 최대 길이를 설정에도 한계

Increasing language model maximum context length.

→ 최근 하드웨어와 알고리즘의 발전으로 maximum context length가 급격히 증가함.

Multi-Document Question Answering

• multi-document QA
• input context의 길이와 관련 정보의 위치를 변경해가면서 성능을 측정함.

Experimental Setup

commercial search & questoin answering app (예: Bing Chat)을 기반으로 한 retrieval-augmented generation setup과 유사함.

model inputs

1️⃣ a question to answer

2️⃣ k documents

k개의 documents가 있고, 1개의 document에만 Question에 대한 정보가 있음.

(K-1)개의 documents에는 Q에 대한 정보 X → “distractor” document

NaturalQuestions 벤치마크에서 데이터 사용 (NaturalQuestions-Open에서 query를 가져와 사용)

1) 정답이 담긴 document 수집

NaturalQuestions 주석에서 답변이 포함된 위키피디아 단락을 사용

2) distractor documents 수집

Contriever 검색 시스템을 사용하여 질문과 관련성이 높은 위키피디아 paragraph 중에서 NaturalQuestions 답변 중 Question에 대한 Answer이 포함되지 않은 것을 k-1개 검색

💡 input context length 조절 → distractive document의 수를 증가 시키거나 감소시킴 관련된 정보의 위치를 조절 → document의 순서를 조절

✔️ accuracy를 primary evaluation metric으로 사용

✔️ 단순히 답을 copy하는 것을 방지하기 위해 처음 생성된 newline을 제거함.

✔️ 생성은 new line character 없이 end-of-sequence 토큰을 사용해서 종료함.

✔️ 관련된 paragraph가 input context의 처음에 위치하거나 random하게 놓였을 때 성능이 어떤 지에 대한 연구가 있는데, 본 논문은 위치를 미세하게 조정한다는 측면에서 다름.

Models

open models.

MPT-30BInstruct와 LongChat-13B (16K)에 대한 실험 내용

• MPT-30BInstruct은 최대 8192토큰의 문맥 길이를 가지며, 초기에는 2,048 token seq로 1조 개의 토큰에 대한 사전 훈련
• LongChat-13B (16K)는 LLaMA-13B를 기반으로 하며, 문맥 창을 16,384 토큰까지 확장하기 위해 rotary positional embedding을 사용했고, 이후 16,384 token seq로 미세 조정

closed models.

• GPT-3.5-Turbo: 최대 4,000 토큰의 문맥 길이를 처리할 수 있는 모델
• GPT-3.5-Turbo (16K): 최대 16,000 토큰의 문맥 길이를 다룰 수 있는 확장된 버전
• Claude-1.3: 최대 8,000 토큰의 문맥 길이를 가지는 모델
• Claude-1.3 (100K): 최대 100,000 토큰의 확장된 문맥 길이를 가지는 버전

Results and Discussion

closed-book 설정: 모델은 입력 문맥에 어떤 문서도 주어지지 않으며, 매개 변수 기반 메모리를 활용하여 올바른 답변을 생성

oracle 설정: 언어 모델에게 답변이 포함된 단일 문서가 주어지며, 이를 사용하여 질문에 답해야 함

💡Model performance is highest when relevant information occurs at the beginning or end of its input context

input context의 처음과 끝 부분에 나타나는 정보를 식별하고 활용하는 데 성능이 좋음

중간 부분에 있는 정보를 사용하려고 할 수록 성능 저하

⇒ downstream task를 수행할 때 전체 context window를 효과적으로 추론 X

⇒ input context의 처음이나 끝에 있는 정보를 사용하는 것이 더 쉬움.

💡Model performance substantially decreases as input contexts grow longer

⇒ input context의 길이가 길어질 수록 성능🔻

💡Extended-context models are not necessarily better at using input context

model과 extende-context model 모두 input context를 처리할 수 있는 경우 성능이 거의 동일함.

⇒ 더 긴 maximum context window를 가진 모델이 context를 더 잘 활용하는 것 X

How Well Can Language Models Retrieve From Input Contexts?

synthetic key-value retrieval task에 대한 연구

Experimental Setup

input

(i) k 개의 키-값 쌍을 가진 문자열로 직렬화된 JSON 객체 (각 키와 값은 고유한 무작위 생성 UUID)

(ii) 언급된 JSON 객체 내에서 특정 키

goal

speicified key와 연결된 value 반환

✔️ 각 JSON 객체는 하나의 관련 키-값 쌍을 포함, k - 1개의 관련 없는 "distractior" 키-값 쌍을 포함

✔️ accuracy 사용

✔️ synthetic key-value retrieval task는 input context에서 일치하는 토큰을 검색하는 것을 testbed로 함.

💡 input context length 조절 → distractor key-value pairs의 수를 증가 시키거나 감소시킴 관련된 정보의 위치를 조절 → 검색할 key의 위치를 조절

Results and Discussion

• synthetic key-value retrieval task는 input context 내에서 정확히 일치되는 것을 확인하는 것만 필요하지만, 모든 모델이 높은 성능을 달성한 것은 X

  (특히 140개 이상의 키-값 쌍에서 키를 검색할 때 어려움이 있었음)

• 키-값 검색 작업에서 완벽한 성능을 보이는 모델은 제외하고 multi document QA에서와 유사한 경향을 보임. → U자 곡선 (key-value pairs가 input context의 중간에 있을 때 성능이 가장 낮음)

Why Do Language Models Struggle To Use Their Entire Input Context?

긴 input context에서 관련 정보가 중간에 위치해있을 때 언어 모델의 성능이 저하됨.

이러한 원인을 더 잘 이해하기 위해 다음의 것들을 실행함.

Effect of Model Architecture

decoder only vs encoder-decoder

사용된 모델:

• Flan-T5-XXL: 512 토큰의 시퀀스로 훈련 (인코더 및 디코더 포함)
• Flan-UL2: 초기에는 512 토큰의 시퀀스로 훈련 / 추가적으로 100,000 단계 동안 1024 토큰의 시퀀스로 사전 훈련 / 그 후 2048 토큰의 인코더 시퀀스와 512 토큰의 디코더 시퀀스로 instruction-tuning

✔️ relative positional embedding 사용

⇒ 2048 토큰까지는 input context내에 관련 정보의 위치를 바꿔도 robust함 (2048 토큰보다 시퀀스가 길어지면 middle에서 다시 성능 저하)

⇒ encoder-decoder 모델은 양방향 인코더로 인해(prior token뿐 아니라 그 후에 있는 token도 참조할 수 있기 때문에) context window를 더 잘 활용할 수 있을 것

Effect of Query-Aware Contextualization

질문이나 키를(즉, 답변할 질문이나 검색할 키) 처리하는 데 있어서 데이터 (즉, 문서나 키-값 쌍) 다음에 질문이 오도록 설정

⇒ decoder 모델은 query token에 attend 할 수 없음 → prior token에만 attend 할 수 있기 때문에

(질문에 대한 프롬프트는 끝에 나옴)

⇒ encoder-decoder 모델이 위치가 변경되어도 더 robust함. (양방향 인코더를 사용하므로)

Effect of Instruction-Tuning

• instruction은 주로 input context의 시작 부분에 위치함 → instruction-tuned LM은 input context의 시작 부분에 더 많은 가중치를 둠.
• MPT-30B와 MPT-30B-Instruct 모두 U자형의 성능 곡선을 나타내는데, 관련 정보가 입력 문맥의 맨 처음이나 맨 끝에 발생할 때 성능이 가장 높음
• instruction이 없는 모델은 최근 토큰들에 편향되어있음. (long-range information에 좋지 않음)
• instruction-formatted data로 프롬프트될 때 언어 모델은 longer-range information 사용 가능

Is More Context Is Always Better? A Case Study With Open-Domain QA

✔️ trade-off

input context length를 증가 → LM에 더 많은 정보 제공 & 모델이 추론해야 하는 content의 양 🔺

❓ LM이 16,000개의 토큰을 처리할 수 있으면 실제로 16,000개의 토큰을 제공하는 것이 좋은가?

downstream task마다 다름 & 추가된 context의 가치와 긴 input context를 효과적으로 활용할 수 있는 지에 대한 모델의 능력에 따라 다름.

실험

• standard retriever-reader setup을 사용
• retriever recall과 reader accuracy를 평가

reader 모델의 성능이 retriever 모델의 성능 보다 더 빨리 포화됨 → readers가 추가된 context를 효과적으로 사용X

⇒ 모델들이 input context의 시작 또는 끝에서 정보를 검색하고 사용하는 데 더 능숙함

⇒ "effective reranking of retrieved documents"와 "ranked list truncation”이 context를 활용하기 위한 더 나은 방향

❓ "Effective Reranking of Retrieved Documents"

: 검색된 문서들을 다시 정렬하여 관련 정보를 input context의 시작 부분에 더 가깝게 위치시키는 것

ex) 관련 정보가 있는 문서를 먼저 나열하거나 가중치를 조절하여 중요한 정보에 더 집중

❓ "Ranked List Truncation"

: 검색된 문서들의 리스트를 필요에 따라 줄이는 것

ex) 모델이 다루기에 너무 많은 문서가 있는 경우, 중요한 정보만을 포함하는 작은 리스트로 줄일 수 있음

Related Work

Long-context language models

How do language models use context?

The serial-position effect

Conclusion

Intro

Session : 사용자가 웹 사이트, 모바일 앱 등을 통해 상호작용하는 일련의 과정

Ex) 쇼핑몰에 들어가서 상품을 검색하고 클릭하고 상세정보를 읽고 구매를 하는 모든 과정

• 해당 페이지를 벗어나거나 로그아웃 등의 행위를 하게 되면 session이 종료됨

• 여러 명의 정보가 동시에 입력되는 것이 아니라, 각 사용자마다 독립적으로 생성됨

➡ 해당 사용자의 개인화된 추천을 제공해줄 수 있음

Session based recommendation : 추천 시스템에서 사용자의 행동 데이터를 이용해, 해당 사용자가 현재 상황에서 무엇을 찾고 있는지를 파악하고 이에 맞는 아이템을 추천하는 방식

• session을 하나의 추천 단위로 하여 사용자가 선호할 만한 아이템을 추천해줌

  
  

GNN모델이 나오게 된 이유

이전 RNN 계열 모델에서는 유저의 선호도를 반영하는 user representation이 따로 존재 X ➡ RNN의 hidden vector를 user representation으로 가정하고 다음 아이템 예측

• 여기서 user representation은 유저의 특성벡터
• RNN은 이러한 user representation이 별도로 존재하지 않고, 이전의 모든 정보들을 hidden vector에 저장하기 때문에 hidden vector를 user representation이라고 가정하고 다음 아이템을 예측

각 세션이 user - specific하지 않음 ➡ 유저에 대한 특성 반영 X

• 한 유저만의 정보가 아닌 다른 유저들의 공통된 정보일 수 있음
• 유저의 모든 정보가 포함된 것이 아니라 일부분의 정보만 포함된 것일 수 있음

Session 내의 다른 여러 아이템들 간의 복잡한 transition 무시

• 예를 들어, 사용자가 책 ➡ 노트북 ➡ 의자 순으로 상품을 클릭했으면, 다음 아이템을 예측할 때는 의자만을 고려하여 아이템을 추천해줌

➡ 이러한 기존 모델들의 한계점을 보완하고자 나온 모델

GNN (Graph Neural Networks)

input : graph

𝐺 = (𝑉, 𝐸)로 정의 (𝑉 : node, 𝐸 : edge) - node는 각 아이템을, edge는 아이템들간의 관계를 의미함

output : session vector

session vector는 session에 대한 특성벡터

예를 들어, 쇼핑몰에서 상품을 추천할 때 상품의 가격, 카테고리, 브랜드, 색상 등을 수치화하여 표현한 것을 말함

SR-GNN 구조

모든 아이템들의 집합 $V = {v_1, v_2, ... , v_m}$ 세션 $s = [v_{s,1}, v_{s,2}, ... , v_{s,n}]$

$V = v_{x, n+1}$

• 이 모델의 task는 위의 식과 같이 session에 n까지의 아이템이 있을 때, n+1번째 아이템을 예측하는 것

• 모델의 아웃풋은 세션 s에서 가능한 모든 아이템들에 대한 확률값, y hat벡터 안의 모든 아이템들이 추천될 아이템의 후보

➡ Node : ** $v_{s,t}$ 시퀀스의 각 아이템 ➡ Edge :** $(v_{s,i-1}, v_{s,t})$ 시퀀스에 나타난 연속 두 아이템

Learning Item Embedding on Session Graphs

노드 벡터의 학습 과정

(1) 노드 간의 관계가 반영되도록 정보 전파

• 행렬 $A_s$에 의해 주어진 제한 하에 서로 다른 노드 사이의 정보 전파를 위해 사용

(2), (3) 노드 간의 관계 정보 보존 정도

• 각각 update gates와 reset gates를 의미, 어떤 정보를 유지할 것인지 혹은 버릴 것인지를 결정함

(4) 이전 state, reset gate를 기반으로 후보 state 구성

(5) 마지막 state는 update gate 제한 하에 이전의 hidden state와 후보 state의 혼합으로 구성

• 종합적으로 t-1시점의 값들로부터 t시점의 노드 벡터 값을 구함

Ex)

Matrix로 나타낸 것을 보면 outgoing edges와 incoming edges로 구성되어 있어서 $v$ x $2v$의 크기를 갖는데

이때 $v_2$처럼 아이템들이 한 sequence에서 반복적으로 등장할 수 있기 때문에 각 edge를 정규화된 가중치로 할당함

Loss Function

cross - entropy

• 각 노드마다 다음에 올 아이템이 정답일 확률과 오답일 확률을 계산하는데 사용 따라서 각 노드의 출력값이 0 또는 1에 가까울수록 이 손실함수의 값은 작아지는 방식으로 모델을 학습함

더하여 세션 기반 추천 시스템에서 대부분의 세션은 짧은 길이를 가지고 있기 때문에, overfitting 문제가 발생할 가능성이 높아짐 ➡ 이를 방지하기 위해 적은 수의 훈련 데이터를 사용하는 것이 좋음

Evaluation Metrics

• Yoochoose 1/62, Yoochoose 1/4, Diginetica 데이터셋과 P@20, MRR@20로 나누어서 모델 성능을 비교한 결과

• POP은 전체 데이터에 대해 인기 아이템을 고르는 단순한 모델이어서 성능이 낮음

• 그러나 GRU4REC나 NARM은 RNN모델을 사용해서 유저의 과거 행동에 대한 전반적 관심사를 파악하려 했기 때문에 성능이 좋아졌음

• SR-GNN은 세션뿐 아니라 아이템들이 가지는 관계를 파악하면서 진행했기 때문에 성능이 가장 좋은 것을 확인할 수 있음

Best Subset Selection ✔ 가능한 모든 모델을 고려하여 가장 좋은 모델을 선택 $1$. $M_0$이 아무 predictor를 포함하지 않는 null model이라고 할 때, 이 모델은 각 observation의 sample mean을 predict함 $2$. $k = 1,2, ... ,p$ : $(a)$ $pCk$ model들을 정확히 $k$ predictors가 포함되도록 함 $(b)$ $pCk$ model 중 가장 좋은 모델을 고르고 $M_k$라 함. ➡ 가장 좋다는 것은 가장 작은 RSS를 가지고 있다는 것 or 가장 큰 $R^2$을 가지고 있다는 것 $3$. $M_0, ... , M_p$ 중 single best model을 하나 선택함. ➡ cross-validated prediction error, $C_p$, (AIC), BIC, adjusted $R^2$ 등을 사용

Forward Stepwise Selection ✔ 변수를 하나씩 추가해가면서 Model을 선택 $1$. $M_0$은 아무 predictor를 포함하지 않는 null model $2$. $k = 0, ... ,p-1$ : 2-1) 모든 $p-k$ model들은 predictor를 하나씩 증가시킴 2-2) $p-k$ 모델들 중 $M_{k+1}$를 가장 좋은 것으로 고름 ➡ 가장 좋다는 것은 가장 작은 RSS를 가지고 있다는 것 or 가장 큰 $R^2$을 가지고 있다는 것 $3$. $M_0, ... , M_p$ 중 single best model을 하나 선택함. ➡ cross-validated prediction error, $C_p$, (AIC), BIC, adjusted $R^2$ 등을 사용

Backward Stepwise Selection ✔ Full model로 시작하여 하나씩 변수를 제거하면서 최적의 Model을 선택 $1$. $M_p$는 모든 p개의 predictor를 포함하는 full model $2$. $k = p, p-1, ... , 1$ : 2-1) $M_k$는 하나의 predictor를 제외한 모든 predictor를 포함하고 있는 모델 ➡ total : $k-1$ 2-2) $k$ 모델들 중 $M_{k-1}$를 가장 좋은 것으로 고름 ➡ 가장 좋다는 것은 가장 작은 RSS를 가지고 있다는 것 or 가장 큰 $R^2$을 가지고 있다는 것 $3$. $M_0, ... , M_p$ 중 single best model을 하나 선택함. ➡ cross-validated prediction error, $C_p$, (AIC), BIC, adjusted $R^2$ 등을 사용

• Mallow's $C_p = \frac{1}{2}(RSS + 2p\hat{\sigma}^2)$ 　　　p = #parameters

• $AIC = −2 log L + 2p$

• $BIC =\frac{1}{2}(RSS + log(n)p\hat{\sigma}^2)$

• Adjusted $R^2 = 1 − \frac{RSS/(n − p − 1)}{TSS/(n − 1)}$ 　　　TSS = Total Sum of Squares

Shrinkage

Ridge regression

Ridge regression coefficients은 아래 식을 최소화하는 것이 목표임

➡ $\underset{\beta}{\arg\min}(RSS + \lambda\beta'\beta)$

$\lambda\beta'\beta$는 shrinkage penalty

• $\beta_j$가 0에 가까워질 수록 penalty term은 작아짐
• Ridge regression은 tuning parameter $\lambda$는 회귀 계수 추정에 두 항이 미치는 상대적인 영향을 조절하는 데 사용 (shrinkage 효과 조절)

➡ $\lambda$가 크면 RSS를 줄이는 것보다 $\beta'\beta$을 거의 0으로 줄여줘야 함 여기서 beta는 vector임

✔ $\lambda$가 0이라면 OLS와 동일 ➡ $\hat{\beta}^{ridge} = \hat{\beta}^{OLS}$ ✔ $\lambda$가 점점 커짐에 따라 shrinkage 효과🔺 / Ridge Regression 계수들이 0에 가까워짐

For special case of $X'X = I$ , $\hat{\beta}^r_\lambda = \frac{1}{1+\lambda}\hat{\beta}^{OLS}$

• ridge regression estimates는 predictor에 상수를 곱해주면 많이 변하기 때문에 (패널티 부분에 있는 계수 제곱의 합 때문) predictor들에 표준화를 거친 다음 ridge regression을 적용하는 것이 좋음

📈 *effect of $\lambda$ value *

• 왼쪽 그래프 오른쪽으로 갈수록 $\lambda$이 점점 커짐 오른쪽으로 갈수록 $\hat{\beta}^{ridge}$ 값 shrink (0에 가까워짐)

• 오른쪽 그래프 왼쪽으로 갈수록 $\lambda$이 점점 커짐

📍Bias-Variance tradeoff

동일한 내용 필기본 ⬇

동일한 내용 필기본 ⬇

✔ 증명 과정에서의 SVD는 링크를 참고

The Lasso regression

📍 Lasso는 closed term이 존재하지 않음 ➡ penalty form이 미분 불가하기 떄문

Ridge의 penalty term: $\beta_j^2$, Lasso의 penalty term: $|\beta_j|$ Lasso는 explit form을 만들 수 없지만, variable selection이 가능함 Ridge는 variable selection 불가능

📈Lasso 왼쪽 그래프, L1 form

• variable selection 가능
• 타원에 있는 점 $\hat{\beta}$에서 Least squares estimator (제약조건 없는 경우 error 최소)
• 타원이 y축과 만나는 점에서 제약조건을 만족하며 error가 최소가 되고 이때 $\beta_1 = 0$이 되어 variable selection이 가능해짐 제약조건 $|\beta_1| + |\beta_2| \leq t$

📈Ridge 오른쪽 그래프, L2 form

• variable selection 불가능
• 타원에 있는 점 $\hat{\beta}$에서 Least squares estimator (제약조건 없는 경우 error 최소)
• 타원이 원과 만나는 점에서 제약조건을 만족하며 error가 최소
• $\beta_1$, $\beta_2$ 둘다 0이 아니기 때문에 selection이 일어나지 않음 제약조건 $\beta_1^2 + \beta_2^2 \leq t$

Lasso는 closed form이 없지만, $X'X=I$인 special case에 한해 closed form을 구할 수 있음 X가 모두 orthogonal

위의 식을 보면 $2\displaystyle\sum_{i=1}^{p} \hat{\beta}^{OLS}\ \beta_j^2$에서만 부호가 결정이 됨 만약 $\hat{\beta}^{OLS} > 0$ 이라면, $\beta_j$가 +일 때 $2\displaystyle\sum_{i=1}^{p} \hat{\beta}^{OLS}\ \beta_j^2$이 -가 되고,
$\beta_j$가 -일 때 $2\displaystyle\sum_{i=1}^{p} \hat{\beta}^{OLS}\ \beta_j^2$이 +가 됨.

$\hat{\beta}^{OLS} > 0$인 경우 ⬇

$sgn()^+$는 $\geq0$이면 괄호 안에 식을 그대로 사용하고 $<0$이면 괄호 안에 식이 0이 됨 ➡ $\beta_j$가 작아지는 것이 goal이기 때문에 더 큰 값이 될 바에 0이 되는 것이 작은 값에 도달할 수 있어 sgn form을 사용함

$\hat{\beta}^{OLS} < 0$인 경우 ⬇

➡ 수평선이 되는 구간에서 $\beta_j = 0$이 돼서 variable selection 가능 ➡ 흐릿하게 생긴 선이 ${\beta}_j^{Ridge}$, 진한 선이 ${\beta}_j^{Lasso}$

✔ Lasso는 Ridge와 달리 표준화할 필요 X ✔ $\lambda$ 가 증가할 떄 bias 증가 ↔ variance 감소 trade off

Reference - Introduction to Statistical Learning

• statistical learning method를 사용할 때, 주어진 데이터 셋에서 test error가 작게 나오면 해당 방법을 사용하는 것이 타당하다고 할 수 있음.
• test error는 특정 test set이 있을 경우 쉽게 계산할 수 있지만, 대부분 그렇지 않음. ➡ available training data를 사용하여 quantity를 추정하기 위해 많은 기술이 사용됨.

📌 일부 훈련 데이터를 테스트에 사용하여 test error를 추정하는 방법에 대해 다룸.

The Validation Set Approach

• random하게 training set과 validation (or hold-out set)으로 나눔.
• training set으로 model fitting + fitted model로 validation set을 예측
• validation set error는 test error를 제공함 ➡ quatitive response - MSE ➡ qualitative response - misclassification rate

+ 모델 평가를 위해 일부 데이터를 사용하므로 결과가 data split에 따라 달라질 수 있음

training set의 일부를 모델을 평가하기 위한 validation set으로 split하여 사용

K-fold Cross-validation

• 데이터를 K개로 나눔 (각 부분의 크기는 같음)
• (K-1) parts는 training set로 사용 + 나머지 1개의 part는 validation set으로 사용
• K번 반복 ➡ K개의 결과의 평균 사용

$MSE_k =\displaystyle\sum_{i\in C_k}{(y_i-\widehat{y}_i^{(k)})^2}/n_k$ $\widehat{y}_i^{(k)}$ : k번째 fold를 제외하고 modeling한 모델에 $x_i$를 넣어서 얻은 값

📌 overlap 되는 부분이 없음 (Bootstrap은 overlap 존재)

✔ LOOCV (Leave-one out CV) $K=n$일 경우 각 반복에서 하나의 데이터 포인트만을 validation set로 사용하고 나머지 데이터를 training에 사용 📌 bias는 작지만, 시간이 굉장히 많이 소요됨 least squares linear or polynomial regression에서 LOOCV를 구현하는 데 cost를 많이 줄일 수 있고, single model fit의 cost와 동일해짐 💡 오른쪽 식을 보면 n times를 반복해서 얻은 값이 아닌 n 개의 데이터를 가지고 얻어진 값을 사용하여 1 time의 시간이 걸림을 알 수 있음.

$K=5$ or $10$이 bias-variance tradeoff에 있어 좋은 결과를 제공

The Bootstrap

• 실제 데이터에서는 원래 모집단에서 새로운 sample을 생성할 수 없음.
• bootstrap에서는 독립적인 데이터 세트를 반복적으로 얻는 대신, 원래 데이터 세트에서 observation을 복원추출(replacement)하여 중복을 허용하는 방식으로 함. ➡** "bootstrap data sets"**

📌 overlap되는 것이 특징

estimate test MSE

prob $i$th obs is "not" selected when you sample one data for constructing bootstrap sample b $= 1 - \frac{1}{n}$

➡ prob $i$th obs is "not" selected when you sample n times data for constructing bootstrap samble b $= 1 - (\frac{1}{n})^n$

➡ prob $i$th obs is selected when you construct bootstrap sample b $= 1 - (1 - \frac{1}{n})^n$

$$\lim_{n \to \infty} 1 - (1 - \frac{1}{n})^n \approx 1 - \frac{1}{e} = 0.632$$

reference - Introduction to Statistical Learning

model

• 일반적으로 parameter β를 추정하기 위한 학습데이터 집합 ($x_1$, $y_1$), ... ,($x_N$, $y_N$)를 가짐
• 선형 회귀 모델은 inputs이 $X_1$, ... ,$X_p$일 때 $E(X|Y)$의 함수를 추정하는 것

  Estimation

  

추정 방법은 RSS를 최소로 만드는 β를 구하는 것 ( $X$는 $N * (p+1)$ matrix, β = ($β_0$, ... , $β_p$$)^T$, $y$는 $N$ vector ) 📌 X가 p+1인 이유는 intercept까지 포함되기 때문 📌 p는 #feature, N은 #observation

❓만약 $X$가 선형 독립이 아니라서 $X$가 full rank가 아니라면 ➡ $X^TX$가 singular이 되고, least squares coefficients $\widehat{β}$가 명확하게 정의되지 않을 수 있음. ➡ 특이값 분해(Singular Value Decomposition, SVD) 등의 기술 사용

Inference

📌 $\widehat{β}_j$와 $\widehat{σ}^2$은 통계적으로 독립

To test $H_0$ : $β_j = 0$ $(j = 0, ... , p$)

$z_j = \frac{\widehat{β}j}{\widehat{σ}\sqrt{v{j+1}}}$ 사용 ($v_j$는 ($X^TX$$)^{-1}$의 $j$번쨰 diagonal element)

Under $H_0$, $v_j$ ~ $t_{N-p-1}$

$(1-\alpha)$ x 100% CI of $βj$ : $\widehat{β}_j\pm$$t{\alpha/2,N-p-1}se(\widehat{β}_j)$

To test $H_0$ : $β{p_0+1} = ... = β{p_1} = 0$

use $F = \frac{(RSS_0 - RSS_1) / (p_1 - p_0)}{RSS_1/(N-p_1-1)}$

$RSS_1$는 $p_1+1$개의 파라미터를 갖는 큰 모델의 RSS이고, $RSS_0$는 $p_0+1$개의 파라미터를 갖는 작은 모델의 RSS임. Under $H_0$, $F$ ~ $F_{p_1-p_0,N-p_1-1}$

✔ F distribution은 $x^2$ 2개의 ratio로 이루어짐 $x^2$ > 0 ➡ F distribution도 항상 > 0 ➡ $RSS_0 - RSS_1 > 0$

❓왜 항상 $RSS_0$이 $RSS_1$보다 클까

➡ $RSS_0$은 simple model, $RSS_1$은 complex model로 $RSS_1$에서 일부 parameter를 0으로 둔 것이 $RSS_0$이 됨. ➡ simple model의 RSS > complex model의 RSS

The Gauss-Markov Theorem

parameter β에 대한 least squares estimate(최소 제곱 추정치)는 모든 linear unbiased estimates 중에서 분산이 가장 작은 값임 biased estimator에 더 작은 MSE(Mean Squared Error)가 존재할 수 있음 ➡ 약간의 bias를 감수하고 variance의 큰 감소시키는 효과를 가질 수 있음 ➡ least squares coefficients의 일부를 줄이거나 0로 설정하여 biased estiamte로 만들 수 있음. (variable selection & ridge regression)

💡 쉽게 말하면, bias가 없는 estimator(unbiased estimator) 중에 variance가 가장 작은 것을 찾는 것이 Gauss-Markov Theorem인데, bias가 있는 것 중(biased estimator)에 variance가 굉장히 작아서 총 MSE가 bias가 없는 것보다 더 작은 식이 있을 수 있음

➡ 우리는 작은 MSE를 찾는 것이 목표이기 때문에, bias가 있지만 variance가 작아서 총 MSE 값을 더 작게 가질 수 있다면, biased estimator를 선택할 수 있음.

Comparison of Linear regression with KNN

KNN은 Regression과 Classification 두 가지로 쓰이는데, 이 부분에서는 Regression 측면에서만 보도록 하겠음

KNN regression

$N_0$ : $x_0$와 가까운 $K$개의 training observation

c.f. KNN Classifier

간단하게 예시를 들자면, $x_i$와 가까운 k개의 데이터를 찾는 것 $\frac{1}{K}$$\displaystyle\sum_{i\subset N_0}$$I(y_i = A)$ ➡ A형과 비교 ➡ A형인 observation 수 / k 와 같이 B형, O형, AB형 모두 구한 뒤, 가장 큰 확률이 나오는 class로 분류

왼쪽 그림이 K=1일 때이고, 오른쪽 그림이 K=9일 때 + 주황색 dots는 observations 왼쪽 그림은 wiggly하고 오른쪽 그림은 smooth한데, K가 작으면 값들의 분포가 크고 K가 크면 값들의 분포가 크지 않아서 smooth 해짐

📌 wiggly ➡ $var$🔺, $bias^2$🔻 📌 smooth ➡ $var$🔻, $bias^2$🔺

• true form이 linear할 경우

OLS는 K값의 변화에 따라 변화하지 않고, KNN은 K값의 변화에 따라 달라짐. ➡ 위 그래프에서는 OLS의 MSE가 더 낮으므로 OLS가 더 좋음.

• true form이 linear하지 않을 경우

➡ 위 그래프에서는 KNN의 MSE가 OLS의 MSE보다 더 낮으므로 KNN이 더 좋음.

• ** Curse of dimensionality in KNN**

➡ dimension이 증가할수록 KNN의 성능🔻

reference - Introduction to Statistical Learning