Skip to main content

Data Mining Lab. Blog

Search This Blog

Pages

Showing posts from June, 2020

Posts

Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference

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

Data Mining Lab.

Go to DMLAB Website

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

연구실에서 진행하고 있는

최신 연구를 소개합니다.

Archive

2021 9

2020 12
2019 1
- December 2019 1

Show more Show less

Popular Posts

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를 고정시켜 업데이트합니다. 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와

Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries

본 문서에서는 데이터 마이닝 분야 학회 중 하나인 KDD 2021에서 발표될 " Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries " 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title: Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries Authors: Jun-Gi Jang and U Kang Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( KDD ), 2021 Temporal Dense Tensor 실세계에 존재하는 많은 데이터가 시간 밀도 텐서 (temporal dense tensor)로 표현될 수 있습니다. 시간 밀도 텐서는 한 차원이 시간과 관련이 있으며, 대부분의 값들이 관측된 데이터입니다. 예를 들어, 여러 위치에 설치된 센서들에서 매 시간마다 측정값들을 얻을 수 있습니다. 해당 데이터는 3차원 시간 밀도 텐서로 표현할 수 있습니다. 이 외에도, 주식 데이터, 비디오 데이터, 교통량 데이터 등도 시간 밀도 텐서로 표현할 수 있습니다. 그림 1. 시간 밀도 텐서 예시. 센서 데이터, 주식 데이터, 비디오 데이터, 교통량 데이터 등 다양한 실세계 데이터가 시간 밀도 텐서로 표현할 수 있다. 이렇듯 실세계에 존재하는 많은 데이터가 시간 밀도 텐서로 표현될 수 있으며 여러 차원을 가지는 텐서 특성상 데이터의 크기는 매우 큽니다. 그러므로, 시간 밀도 텐서를 효율적이고 효과적으로 분석하는 방법을 개발하는 것은 매우 중요합니다. Tucker Decomposition 터커 분해 (Tucker decomposition) 는 주어진 텐서를 분석할 수 있는 가장 핵심적인 도구 중 하나입니

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)이 무척 어려워집니다.

Fast and Accurate Partial Fourier Transform for Time Series Data

본 문서에서는 KDD 2021 학회에서 발표된 " Fast and Accurate Partial Fourier Transform for Time Series Data " 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title : Fast and Accurate Partial Fourier Transform for Time Series Data Authors : Yong-chan Park, Jun-Gi Jang, and U Kang Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( KDD ), 2021 Fourier Transform 고속 푸리에 변환(Fast Fourier Transform, FFT)은 20세기 인류가 발명한 가장 중요한 알고리즘이라고 불릴 만큼 막대한 영향력과 광범위한 응용 분야를 가지고 있는 알고리즘입니다. 실제로 FFT는 MP3, JPEG, MPEG 등의 디지털 데이터를 탄생시킴으로써 오늘날과 같은 디지털 시대의 문을 열어준 알고리즘이라 할 수 있습니다. 인공지능의 시대로 접어들고 있는 21세기에 FFT의 중요성은 더욱 더 커지고 있다고 말할 수 있는데, 앞서 언급한 디지털 데이터의 처리를 비롯하여 데이터 이상 감지, 표현 학습, 합성 곱 신경망 등 수많은 인공지능 분야에 FFT가 널리 사용되고 있기 때문입니다. 구체적으로 푸리에 변환은 시간 또는 공간 영역의 데이터를 주파수 영역으로 변환하는 수학적 연산입니다. 푸리에 변환이 중요한 이유는, 대부분의 실제 세계 데이터가 주파수 영역 내에서 강한 에너지 응축(energy compaction) 현상을 보이기 때문입니다. 다시 말해, 주어진 데이터의 푸리에 계수는 극히 일부분에서만 유의미한 값을 가지며, 나머지 부분에서는 값이 매우 작다는 의미입니다 (그림 1 참조). 그런데, 기존의 FFT는 실제 세계 데이터가 갖는 이러한

Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance

본 문서에서는 IROS 2019에서 발표된 Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다. Title: Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance [ link ] Authors: Seungcheol Park, Shuyu Wang, Hunjung Lim, and U Kang Conference: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019 Segmentation of 3D LiDAR Point Clouds 3차원 라이다 센서 (3D LiDAR sensor)란 빛을 이용하여 주변 물체까지의 거리를 측정하여 센서 주변에 있는 물체들에 대한 위치 정보를 전달해주는 장치입니다. 라이다 센서는 실내에서 사용되는 안내 로봇부터 자율주행 차량까지 다양한 분야에서 사용되고 있습니다. 이때, 라이다 센서는 주로 주변에 물체가 있는지 없는지를 인식 (detection)하거나, 물체가 있다면 어떤 물체인지를 식별 (classification)하는 일을 주로 하게 됩니다. 특히 실내외에서 사람을 인식하는 보행자 식별 (pedestrian classification) 과정은 안전을 위해서도 중요하기 때문에 활발하게 연구되고 있는 분야입니다. 그림 1. 라이다 센서를 이용한 보행자 식별 과정의 예시 그림 1은 현관에 설치된 라이다 센서를 통해 보행자를 인식하는 예시를 보여주고 있습니다. 라이다 센서가 인식한 점 정보 (Input Data)를 전달받은 후 다음과 같은 네 단계를 통해 보행자 인식이

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 해당 논문의 목표는 임의

Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks

본 문서에서는 데이터 마이닝 분야의 ICDM 2017 학회에서 발표된 Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title: Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks Authors: Jaemin Yoo, Saehan Jo, and U Kang Conference: IEEE International Conference on Data Mining (ICDM) 2017 Node Classification 정점 분류(node classification)는 그래프 내의 각 정점(node)을 분류하는 문제입니다. 예를 들어 넷플릭스 같은 스트리밍 서비스에서 그림 1과 같이 사용자들이 컨텐츠를 소비한 내역을 그래프로 모델링한 다음 영화나 드라마를 분류하는 작업 등을 생각해볼 수 있습니다. 최근에 그래프 신경망에 대한 연구가 활발히 이루어지면서 함께 주목을 받고 있는 문제이기도 한데, 데이터간 관계가 그래프 형태로 주어져 있는 경우 정점 분류를 통해 학습 데이터가 부족한 반지도 학습(semi-supervised learning) 상황을 해결할 수 있기 때문입니다. 그림 1. 스트리밍 서비스에서 사용자와 컨텐츠간 관계를 나타내는 그래프. 만약 그래프의 각 정점이 고유한 피처 벡터를 가지고 있다면 그래프는 피처간 관계를 나타내는 보조적인 정보로서 사용됩니다. 이런 경우에는 각 정점의 피처 벡터와 그래프 구조를 동시에 고려하여 그 관계를 학습하는 것이 중요합니다. 반면, 본 논문에서는 피처 벡터가 주어지지 않고 그래프 구조 및 간선 정보가 정점 분류를 위한 유일한 정보라고 가정합니다. 따라서, 정점 피처를 인위적으로 생성해야 하는 그래프 신경망 모델을 바로 적용하기 어렵고, 그래프 구조를 최대한 활용하여

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)을 취하는 것이 최적인가를 학습을 통해 파악하는 분

Time-Aware Tensor Decomposition for Missing Entry Prediction

본 문에서는 Arxiv에 기재된 Time-Aware Tensor Decomposition for Missing Entry Prediction 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Time-Aware Tensor Decomposition for Missing Entry Prediction Authors: Dawon Ahn, Jun-Gi Jang, U Kang Arixv: https://arxiv.org/pdf/2012.08855.pdf CANDECOMP/PARAFAC (CP) Decomposition 그림 1. 3차원 시간 텐서의 CP 분해 다차원 배열을 의미하는 텐서는 시간에 따라 변화하는 다중적인 관계를 표현할 수 있습니다. 예를 들어, 센서에서 수집된 대기 오염 데이터는 오염 물질의 측정 값을 포함하는 3차원 시간 텐서(장소, 오염 물질, 시간)로 표현됩니다. 텐서 분해(Tensor Decomposition)는 텐서 데이터를 효과적으로 분석하는 방법으로, 클러스터링 및 이상 탐지를 포함한 다양한 응용 프로그램에서 광범위하게 활용되고 있습니다. CANDECOMP / PARAFAC (CP) 분해는 가장 대표적인 텐서 분해 모델 중 하나로, 그림 1과 같이 텐서를 각 차원의 벡터들의 외적의 합으로 나타낼 수 있습니다. 위와 같은 시간 텐서에는 대표적인 특성 2가지를 관측할 수 있습니다. 첫번째는 텐서의 시간 차원은 인접한 값들끼리는 서로 연관성이 있는 특징이 있습니다. 예를 들어, t번째 시간에서 관측된 오염 데이터는 t-1, t+1번째 시간에서 관측된 오염 데이터와 비슷한 값을 갖을 것입니다. 두번째로는 데이터를 수집하는 센서 및 기계 오류 및 고장으로 인해 텐서는 많은 결측치로 포함하고, 이는 시간 조각(Time Slice) 별로 다른 희소성(혹은 밀도)을 갖게 합니다. 그러나 표준적인 CP 분해 방법을 포함한 기존 분해 방법들은 위 두 가지 특성 모두 고려하지 않았습니다. 본 논문의 목표는 결측치 예측을 위