Skip to main content

Data Mining Lab. Blog

Search This Blog

Pages

Showing posts from June, 2020

Posts

Sampling Subgraphs with Guaranteed Treewidth

Posted by Data Mining Lab. 날짜: 6/09/2020

Data Mining Lab.

Go to DMLAB Website

본 블로그에서는 서울대학교
컴퓨터공학부 데이터마이닝

연구실에서 진행하고 있는

최신 연구를 소개합니다.

Archive

2021 3

2020 12
2019 1
- December 2019 1

Show more Show less

Popular Posts

Pea-KD: Parameter-efficient and accurate Knowledge Distillation on BERT

본 문서에서는 Pea-KD: Parameter-efficient and accurate Knowledge Distillation on BERT 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Pea-KD: Parameter-efficient and accurate Knowledge Distillation on BERT Authors: Ikhyun Cho and U Kang Arxiv: https://arxiv.org/abs/2009.14822 BERT 압축 (BERT Compression) 최근 들어 자연어 처리 분야에서 사전학습 (pretrain) 후 특정 데이터셋에 미세조정 (fine-tuning)하는 모델들이 굉장히 좋은 성능을 보이고 있으며 그 중에 가장 대표적인 모델이 BERT입니다. BERT 모델은 하나의 임베딩 층과 트랜스포머 (transformer)의 인코더 (encoder) 부분을 여러 층 쌓은 구조로 이루어져 있습니다. 그리고 각 인코더는 멀티 헤드 셀프 어텐션 (multi-head self-attention) 구조를 사용합니다. 간단히 말해서 각 인코더에 들어오는 인풋 벡터를 n 등분한 후 각각에 셀프 어텐션을 적용한 후 다시 합치는 (concatenate) 과정을 사용합니다. BERT의 가장 기본적인 모델로 BERT-base를 흔히 사용하며, 이는 12개의 인코더 층과 벡터의 dimension으로 768을 사용합니다. 하지만 이러한 BERT는 파라미터 수가 굉장히 많다는 단점이 있습니다. BERT-base의 파라미터 수는 대략 1.1억개로 상당히 많은 편이며 따라서 edge device에 적용하기가 어렵습니다. 따라서, BERT를 압축하는 여러 연구가 진행되고 있고 본 논문에서는 Knowledge Distillation과 Parameter Sharing 측면에서 BERT 압축을 기존보다 더 효율적으로 할 수 있는 방법을 제시합니다. 지식 증류 (Knowledge Distillation (KD)) 지

Attention-Based Autoregression for Accurate and Efficient Multivariate Time Series Forecasting

본 문서에서는 데이터 마이닝 분야의 SDM 2021 학회에서 발표될 예정인 Attention-Based Autoregression for Accurate and Efficient Multivariate Time Series Forecasting 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Attention-Based Autoregression for Accurate and Efficient Multivariate Time Series Forecasting Authors: Jaemin Yoo and U Kang Conference: SIAM International Conference on Data Mining (SDM) 2021 Multivariate Time Series Forecasting 시계열 예측(time series forecasting)은 기계 학습 및 데이터 마이닝 분야에서 활발히 연구되고 있는 문제로서, 많은 수의 실세계 데이터가 시계열 형태로 모델링되기 때문에 주가 예측, 날씨 예측, 전력 수요 예측 등 다양한 실세계 문제와 밀접히 연관되어 있습니다. 그중에서도 다변수(multivariate) 시계열 예측은 서로 연관되어 있는 여러 개의 시계열 변수를 동시에 예측하는 상황을 의미합니다. 위에서 언급한 시계열 예측 문제의 예시는 모두 다변수 예측에 해당됩니다. 즉, 예측 대상이 되는 주식 종목간 관계, 지역간 관계, 그리고 도시 구획별 관계를 모델링함으로써 시계열 예측 정확도를 크게 향상시킬 수 있습니다. 하지만, 각 변수에서 관측되는 패턴과 여러 변수간 관계를 동시에 고려하다 보니 다변수 시계열 예측을 위한 기존 모델은 지나치게 많은 파라미터를 갖는 경향을 보였습니다. 학습 데이터의 양이 충분하지 않고 과거 시점의 데이터에 과적합(overfitting)되기 쉬운 시계열 데이터의 특성상 파라미터 수가 많아질 경우 성능 재현과 하이퍼파라미터 튜닝(hyperparameter tuning)이 무척 어려워집니다.

SIDE: Representation Learning in Signed Directed Networks

본 문서에서는 WWW 2018에서 발표된 "SIDE: Representation Learning in Signed Directed Networks" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: SIDE: Representation Learning in Signed Directed Networks Authors: Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang Link: https://datalab.snu.ac.kr/~ukang/papers/sideWWW2018.pdf Representation Learning in Signed Directed Networks. 부호화 되어있고, 방향성이 있는 그래프에 있는 노드들에 대해서 어떻게 하면 각 노드의 표현 (representation)을 정확하게 학습할 수 있을까요? Representation learning은 주어진 그래프 내에 있는 각각의 노드들에 대해서 각 노드를 표현하는 벡터를 학습하는 것을 의미하며, 그림 1에서와 같이 각 노드별로 고유의 벡터를 가지게 되는 것을 알 수 있습니다. 이때의 노드별로 학습되는 벡터들을 표현 (representation)이라고 하며, 학습된 노드들의 표현은 노드 식별 (node classification), 연결 예측 (link prediction), 그리고 군집화 (clustering) 등 다양한 그래프 문제를 푸는데 사용되기 때문에 각 노드별로 정확한 표현을 학습하는 것은 매우 중요합니다. 그림 1. Representation learning 예시 이때, 각 노드별로 학습된 표현은 그래프의 구조적인 정보를 잘 담고 있어야 하는데 그래프에서 방향성이 추가되고, 각 간선 (edge)에 부호가 주어진다면 그래프의 구조적인 정보가 더욱 복잡해져서 이러한 정보들을 정확하게 담기가 더욱 어려워지게 됩니다. 본 문서에서는 이러한 방향성이 있고, 부호화된 그래프에서도 정확하게 표

Knowledge Extraction with No Observable Data

본 문서에서는 NeurIPS 2019에서 발표된 Knowledge Extraction with No Observable Data 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Knowledge Extraction with No Observable Data Authors: Jaemin Yoo, Minyong Cho, Taebum Kim, and U Kang Conference on Neural Information Processing Systems (NeurIPS) 2019 Knowledge Extraction 지식 증류(knowledge distillation)는 한 모델의 학습된 지식을 다른 모델에 전달하는 방법입니다. 예를 들면 모델 A와 B가 주어져 있는데 A는 파라미터의 수도 많고 학습 능력이 뛰어난 반면 B는 그렇지 않다고 합시다. 그러면 주어진 데이터로부터 모델 B를 직접 훈련하는 것보다 모델 A를 훈련한 다음에 A가 학습한 지식을 모델 B에 이용하는 것이 더 좋은 성능을 이끌어낼 수 있습니다. 지식 증류 알고리즘의 구체적인 동작 방식을 요약하자면 다음과 같습니다 ( 참고 ). 훈련된 모델 A가 주어져 있다고 가정합니다. 데이터(피처)를 모델 A에 입력으로 주어 예측값을 저장합니다. 저장한 예측값을 정답으로 하여 모델 B를 학습합니다. 그러나 훈련된 모델 A는 주어져 있으나 데이터가 없는 상황이라면 지식 증류 방법을 활용해 A의 지식을 다른 모델로 전달할 수 없습니다. 모델 A에 입력할 데이터가 없기 때문에 예측값을 얻을 수도 없기 때문입니다. 입력 형식이 같은 임의의 데이터를 생성할 수는 있지만, 그런 데이터는 실제 데이터와 전혀 다른 분포를 갖게 될 가능성이 높아 모델 B의 성능을 오히려 저하시킬 수도 있습니다. 이러한 상황에서, 본 논문은 모델 A로부터 가짜 데이터를 생성하여 이를 지식 증류에 활용하는 새로운 딥 러닝 구조를 제안합니다. 이때 모델의 지식을 증류하기 위해서는 먼

AUBER: Automated BERT Regularization

본 문서에서는 AUBER: Automated BERT Regularization 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: AUBER: Automated BERT Regularization Authors: Hyun Dong Lee, Seongmin Lee, U Kang Arxiv: https://arxiv.org/abs/2009.14409.pdf BERT 정규화 (BERT Regularization) BERT는 2018년 제안된 모델로 많은 자연어 처리 문제에서 좋은 성능을 내고 있습니다. BERT의 학습은 수많은 데이터로 사전학습(pretrain) 후, 풀고자 하는 특정 문제에 맞추어 미세조정(fine-tuning)함으로써 이루어집니다. BERT 모델은 트랜스포머(transformer)의 인코더(encoder)가 여러 층 쌓인 구조로 이루어져 있습니다. 그리고 각 인코더는 멀티 헤드 셀프 어텐션(multi-head self-attention) 구조를 갖습니다. 간단히 말해 어텐션 헤드(attention head)라는 블록 여러 개가 나란히 놓인 구조입니다. 가장 기본적인 모델인 BERT-base의경우, 12개의 어텐션 헤드로 구성된 인코더가 12층으로 쌓인 형태를 갖습니다. 즉, 어텐션 헤드가 12x12 형태로 배치되어 있습니다. 하지만 이러한 BERT는 파라미터가 굉장히 많은 큰 모델입니다. 이로 인해 과적합(overfitting)이 발생해 성능이 낮아지곤 합니다. 특히, 10,000개 이하의 훈련 데이터를 갖는 문제에 대해서는 과적합으로 인해 학습이 전혀 되지 않는 경우도 보고된 바 있습니다. 이는 BERT의 정규화의 필요성을 보여줍니다. 본 논문에서는 프루닝(pruning)을 통해 파라미터 수를 줄임으로써 문제를 해결하고자 합니다. 강화학습과 DQN (Reinforcement Learning and DQN) 강화학습은 현재 상태(state)에서 어떤 행동(action)을 취하는 것이 최적인가를 학습을 통해 파악하는 분

D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

본 문서에서는 ICDE 2020에서 발표된 " D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Jun-Gi Jang et al., D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors , ICDE 2020 Tucker Decomposition 동영상 (가로, 세로, 시간), 기상 데이터 (오염물질, 위치, 시간) 등과 같이 다양한 데이터들이 밀도 높은 텐서 (Dense tensor)로 표현됩니다. 터커 분해 (Tucker Decomposition) 은 텐서 데이터를 분석하는 가장 유명한 모델 중 하나이며 차원 축소, 클러스터링, 추천 시스템 등과 같이 다양한 응용들에서 활용하고 있습니다. 그림 1. 3차원 텐서에 대한 터커 분해 예시 터커 분해는 그림 1의 예시와 같이 주어진 텐서를 각 차원의 저계수 요인행렬 (low-rank factor matrix)과 관계간의 강도를 표현하는 코어 텐서 (core tensor)로 분해합니다. 터커 분해는 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서간의 차이를 줄이는 방향으로 요인 행렬들과 코어 텐서를 학습합니다. ALS (Alternating Least Square) 는 터커 분해의 요인 행렬들과 코어 텐서를 학습할 때 사용하는 접근법 중 하나입니다. 해당 방법은 임의의 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하며, 요인 행렬들을 순서대로 업데이트합니다. 그림 1의 예에서는 행렬 B와 C를 고정시키고 A를 업데이트합니다. 그 다음, A와 C를 고정시키고 B를 업데이트하며, C도 마찬가지로 A와 B를 고정시켜 업데이트합니다. 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와

Accurate News Recommendation Coalescing Personal and Global Temporal Preferences

본 문서에서는 PAKDD 2020에서 발표될 " Accurate News Recommendation Coalescing Personal and Global Temporal Preferences " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Accurate News Recommendation Coalescing Personal and Global Temporal Preferences Authors: Bonhun Koo , Hyunsik Jeon , and U Kang Conference on The 24th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2020, Singapore News Recommendation 본 논문의 목적은 온라인 뉴스 미디어의 사용자를 대상으로 개별 뉴스를 추천할 수 있는 기법을 제안하는 것 입니다. 뉴스 기사의 아래와 같은 특징 때문에 뉴스 추천 시스템은 일반적인 추천 시스템에 비하여 기계 학습을 이용한 추천 모델을 활용 하였을 때 좋은 성능을 기대하기 어렵습니다. 수 십만개의 새로운 뉴스 기사가 매일 출간됩니다. 추천 시간에 따라서 사용자가 흥미를 보이는 뉴스가 빠르게 변합니다. 다시 말해, 수많은 새로운 뉴스 기사가 매일 생성 되며 이를 추천 대상으로 삼아야 하기 때문에 뉴스 추천 시스템에서는 학습 단계에서 활용되는 뉴스 기사들과 실제로 사용자에게 추천해야할 뉴스 기사는 다른 경우가 많습니다. 또한 추천 시간이 변화하면 사용자가 실제로 선택할 뉴스의 내용이 변화할 수 있는데, 예를 들면 월드컵 시즌에는 사용자들이 전반적으로 그들의 개별 취향과는 상관없이 축구 관련 뉴스에 흥미를 보이기도 합니다. 본 논문은 이러한 상황을 극복하고자 '일시적 전체 취향'(Global Temporal Preference)을 활용합니다. 또한, Attentio

Belief Propagation Network for Hard Inductive Semi-supervised Learning

본 문서에서는 IJCAI 2019에서 발표된 Belief Propagation Network for Hard Inductive Semi-supervised Learning 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Belief Propagation Network for Hard Inductive Semi-supervised Learning Authors: Jaemin Yoo, Hyunsik Jeon, U Kang Conference: The 28th International Joint Conference on Artificial Intelligence (IJCAI 2019) Graph-Based Semi-Supervised Learning 많은 기계학습 문제는 지도 학습(supervised learning) 상황을 대상으로 합니다. 즉, 라벨(label)이 주어진 훈련 데이터가 충분히 주어져 있다고 가정합니다. 반면, 반지도 학습(semi-supervised learning) 문제는 훈련 데이터의 양은 충분하되 일부 샘플에 대해서만 라벨이 주어져 있다고 가정합니다. 예를 들면 피처 벡터의 개수는 1,000개이지만 라벨의 개수는 10개밖에 안 되는 상황이 그렇습니다. 이럴 때 10개의 데이터 쌍만 사용해서 모델을 제대로 훈련하기는 어렵기 때문에, 라벨이 주어진 10개의 데이터와 라벨이 없는 990개의 데이터 사이의 관계를 찾아 전체 데이터를 훈련에 사용하는 것이 중요합니다. 반지도 학습 문제는 각 샘플을 정점(node)으로 하는 그래프(graph)가 주어져 있다면 훨씬 수월해집니다. 이 그래프를 통해 샘플 사이의 관계를 쉽게 파악할 수 있기 때문입니다. 예를 들어 페이스북의 친구 관계 그래프가 주어져 있다면 사람들 사이의 유사도를 비교적 쉽게 파악할 수 있고, 이를 이용해 각 사용자의 속성을 분류하는 반지도 학습 문제를 해결할 수 있습니다. 이렇게 그래프 데이터가 주어진 상황에서 반지도 학습을 푸는 상황을 그래프 기반 반

Sampling Subgraphs with Guaranteed Treewidth

본 문서에서는 WSDM 2020에서 발표된 Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다. Title: Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference Authors: Jaemin Yoo, U Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon ACM International Conference on Web Search and Data Mining (WSDM) 2020 Graph Sampling 그래프 샘플링(graph sampling)은 어떤 그래프가 주어졌을 때 해당 그래프의 특성을 보존하는 작은 서브그래프(subgraph)를 생성하는 문제입니다. 본 연구에서는 그래프 샘플링 중에서도 정점 집합을 유지하면서 간선 집합의 일부만을 선택하는 간선 샘플링(edge sampling) 문제를 다룹니다. 예를 들어 사용자간 관계를 설명하는 소셜 네트워크가 주어져 있다고 할 때, 간선 샘플링은 각 사용자의 정보는 유지한 채 사용자간 관계 정보만을 제거하여 서브그래프를 생성합니다. 간선 샘플링이 잘 이루어지면 그림 1 과 같은 결과를 생성하게 됩니다. 그림에 나타난 그래프는 여러 개의 블로그와 블로그간 하이퍼링크를 나타내는 웹 그래프로, 각 정점의 색은 블로그의 정치 성향을 나타냅니다. 이때, 그림 왼쪽의 그래프는 동일한 성향의 블로그끼리 간선을 생성하는 동종 친화성(homophily) 특성을 보이는데, 이 특성이 그림 오른쪽의 서브그래프에서도 잘 보존되는 것을 확인할 수 있습니다. 이렇게 생성된 서브그래프는 실제 그래프의 특성을 보다 효율적으로 파악하기 위해 사용될 수 있습니다. 그림 1.

Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range

본 문서에서는 CIKM 2018에서 발표된 " Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Zoom-SVD: Fast and Memory Efficient Method for Extracting Key Patterns in an Arbitrary Time Range Authors: Jun-Gi Jang, Dongjin Choi, Jinhong Jung, and U Kang Conference: 27th ACM International Conference on Information and Knowledge Management (CIKM 2018) Singular Value Decomposition 센서 데이터, 기상 데이터 등과 같이 여러 시계열 데이터 (multiple time series data)는 행이 시간 축, 열이 속성 (예를 들어, 센서 타입) 축인 행렬들로 표현 될 수 있습니다. Singular Value Decomposition (SVD)는 행렬로 표현된 실세계 데이터를 분석하는 가장 유명한 도구 중 하나입니다. SVD는 차원 축소, 클러스터링, 주성분 분석 등 데이터 마이닝 응용에서 많이 활용되고 있습니다. 아래 그림은 SVD 방식에 대한 예제를 나타냅니다. 그림 1. Singular Value Decomposition (SVD) - 출처[ link ] SVD는 주어진 행렬 A 를 세 개의 행렬들 U , 𝝨, V 로 분해합니다. 행렬 U 와 V 는 직교행렬이며, 𝝨는 대각행렬이고, 대각의 값은 내림차순으로 정렬되어 있습니다. 실세계 데이터는 중복이 많으며, 저차원 구조를 가지고 있으므로 작은 행렬들로 입력 데이터 행렬 A 를 표현할 수 있습니다. Problem Definition 해당 논문의 목표는 임의