Skip to main content

Data Mining Lab. Blog

Search This Blog

Pages

Showing posts from April, 2020

Posts

BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart

Posted by Data Mining Lab. 날짜: 4/01/2020

Data Mining Lab.

Go to DMLAB Website

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

연구실에서 진행하고 있는

최신 연구를 소개합니다.

Archive

2024 4

2023 12
2022 12
2021 12
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) 는 주어진 텐서를 분석할 수 있는 가장 핵심적인 도구 중 하나입니

Unsupervised Multi-Source Domain Adaptation with No Observable Source Data

본 문서에서는 PLOS ONE 저널에 게재된 " Unsupervised Multi-Source Domain Adaptation with No Observable Source Data " 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title: Unsupervised Multi-Source Domain Adaptation with No Observable Source Data Authors: Hyunsik Jeon, Seongmin Lee, and U Kang Journal: PLOS ONE (2021) Unsupervised Multi-Source Domain Adaptation UMDA (Unsupervised Multi-source Domain Adaptation)는 라벨(label)이 있는 여러 소스 도메인(source domain)의 지식을 라벨이 없는 타겟 도메인(target domain)으로 적응(adaptation)하여 타겟 라벨을 정확히 예측하는 것을 목표로 합니다. 기존의 UMDA 기법들은 소스 도메인의 데이터를 모두 관측할 수 있다는 가정을 합니다. 그러나 실세계 예시에서 소스 도메인의 데이터를 관측하지 못하는 상황이 많이 있습니다. 예를 들어, 한 병원에서 질병을 예측하는 분류기를 학습할 때 다른 병원들의 충분한 데이터에서 학습한 정보를 적응하는 것을 목표로 할 수 있습니다. 하지만 환자들의 개인 정보는 개인 정보 보호의 이유로 직접 관측할 수 없기 때문에 기존 UMDA 기법들을 이용할 수 없습니다. 이처럼 기존의 UMDA 기법들은 개인 정보나 정보의 기밀성 등의 이유로 여러 실세계 상황에서 활용할 수 없습니다. 본 논문에서는 소스 데이터를 관측할 수 없는 상황에서 여러 소스 도메인의 정보를 타겟 도메인으로 적응하여 타겟 라벨을 정확히 예측하는 문제를 다룹니다. 기존의 UMDA 기법들은 모든 소스 데이터와 타겟 데이터를 관측할 수 있다는 점을 이용하여 잠재 공간(latent space) 상에서 모든 도

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 분해 방법을 포함한 기존 분해 방법들은 위 두 가지 특성 모두 고려하지 않았습니다. 본 논문의 목표는 결측치 예측을 위

Accurate Retraining-free Pruning for Pretrained Encoderbased Language Models

본 문서에서는 2024년 ICLR에서 발표될 " Accurate Retraining-free Pruning for Pretrained Encoder-based Language Models " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : Accurate Retraining-free Pruning for Pretrained Encoder-based Language Models Authors : Seungcheol Park, Hojun Choi, and U Kang Conference: International Conference on Learning Representations (ICLR) 2024 Retraining-free Pruning of Language Models 최근 트랜스포머(Transformer) 기반의 기학습 언어 모델(Pretrained Language Model, PLM)들은 사람에 가까운 언어를 구사하며, 단순히 대화를 할 수 있으을 뿐만 아니라 문제 풀이, 코드 작성 등에서도 뛰어난 성능을 보이고 있습니다. 하지만, 이러한 언어 모델의 발전은 언어 모델의 거대화를 바탕으로 이루어 졌습니다. 이로 인해 모델을 서비스하기 위한 유지 비용이 매우 값비싸지고, 환경 오염을 일으키며, 개인의 모바일 기기에 탑재하여 개인화된 서비스를 제공하기가 어려워졌다는 부작용들이 발생합니다. 이러한 부작용들을 없애는 방법 중 하나는 모델 내에서 불필요한 부분을 식별하여 잘라내는 가지치기 기법입니다. 하지만, 일반적인 가지치기 기법들은 모델 내의 불필요한 부분을 식별하고 정확도 손실을 최소화하며 잘라내기 위해 긴 재학습 과정을 필요로 하며, 이로 인해 거대한 언어 모델들에서는 사용이 불가능합니다. 그리하여 거대한 언어 모델들에도 사용 가능하도록 설계된 재학습이 없는 가지치기 기법들이 제안되었지만, 이들은 간소화 된 가지치기 과정으로 인해 성능을 보존하지 못한다는 단점이 있습니다. 그러므로, 기존 가지

Accurate Semi-Supervised Automatic Speech Recognition via Multi-hypotheses-based Curriculum Learning

본 문서에서는 2024년 PAKDD에서 발표될 " Accurate Semi-Supervised Automatic Speech Recognition via Multi-hypotheses-based Curriculum Learning " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : Accurate Semi-Supervised Automatic Speech Recognition via Multi-hypotheses-based Curriculum Learning Authors : Junghun Kim*, Ka Hyun Park*, and U Kang (*equal contribution) Conference: The Pacific-Asia Conference on Knowledge Discovery and Data Mining ( PAKDD ) 2024 Hypothesis in Automatic Speech Recognition 온라인 상에 매 순간 새로운 데이터가 업로드되어 사용할 수 있는 음성 데이터가 끊임없이 생성되고 있으며, 이에 따라 음성을 텍스트로 바꿔주는 자동 음성 인식 (Automatic Speech Recognition, ASR) 기술이 온라인 상의 방대한 음성 및 동영상 데이터를 활용하기 위한 방안으로 각광받고 있습니다. 가용 음성 데이터에 대해 사람이 직접 레이블을 생성하는 것은 비용이 많이 들고, 데이터가 추가되는 속도를 따라 잡을 수 없다는 한계가 존재합니다. 이러한 이유로 이미 레이블이 되어있는 음성 데이터를 활용해 새로운 음성 데이터에 대한 자동적인 텍스트 변환이 이루어질 수 있도록 하는 반지도학습 기반 음성 인식 기술에 대한 연구가 활발하게 진행되고 있습니다. 기존 반지도학습 기반 음성 인식 기술은 레이블이 있는, 적은 양의 음성 데이터를 이용해 초기 ASR 모델을 학습시킨 후 레이블이 없는 음성 데이터에 대한 레이블을 만들어내는 방식을 사용해왔습니다. ASR 모델은

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로부터 가짜 데이터를 생성하여 이를 지식 증류에 활용하는 새로운 딥 러닝 구조를 제안합니다. 이때 모델의 지식을 증류하기 위해서는 먼

BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks

본 문서에서는 EDBT 2020에서 발표될 " BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks Authors : Jinhong Jung , Ha-Myung Park , and U Kang Conference : International Conference on Extending Database Technology (EDBT) 2020 Signed Network and Network Generation 부호화된 네트워크 (signed network)란 정점 간의 신뢰 관계를 + (양, 신뢰) 또는 - (음, 불신뢰)의 부호가 붙은 간선으로 표현하는 네트워크를 말하며, Epinions와 같은 온라인 소셜 서비스는 각 사용자에게 다른 사용자에 대한 신뢰를 표현할 수 있게 하여 자연스럽게 부호화된 네트워크를 형성합니다 ( 참고 ). 이와 같이 부호화된 네트워크는 정점 간의 신뢰 관계를 기반으로 링크 예측, 정점 랭킹, 정점 분류, 이상현상 탐지 등의 다양한 그래프 응용에 활용되고 있습니다. 그림 1. 부호화된 네트워크의 예시. 그러나 부호화된 네트워크는 광범위하게 활용되고 있음에 비해, 어떻게 해야 실제 부호화된 네트워크와 비슷한 성향을 가지며 새로운 형태의 다른 부호화된 네트워크를 생성할 수 있는지에 대한 연구는 많이 진행되지 않았습니다. 네트워크 생성 (network generation) 문제는 실세계 그래프 형성의 이해에 대한 중요한 문제로, 네트워크 생성 문제는 다음과 같은 방안으로 많이 활용되고 있습니다. 확장성 테스트 (scalability evaluation) : 확장성 테스트는 개발한 알고리즘이 얼마나 큰 데이터를 처

Personalized Ranking in Signed Networks using Signed Random Walk with Restart

본 문서에서는 데이터 마이닝 분야의 ICDM 2016 학회에서 발표된 Personalized Ranking in Signed Networks using Signed Random Walk with Restart 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title : Personalized Ranking in Signed Networks using Signed Random Walk with Restart Authors : Jinhong Jung et al. Conference : IEEE International Conference on Data Mining (ICDM) 2016 Personalized Ranking in Signed Network 부호화된 네트워크(signed network)는 노드(node) 간의 신뢰 관계를 + (positive, 신뢰) 또는 - (negative, 불신뢰)의 부호가 붙은 간선(edge)로 표현하는 네트워크를 말하며, 이 네트워크가 가장 많이 사용되는 분야로는 각 유저들간의 관계가 신뢰/불신뢰로 이루어진 소셜 네트워크가 있습니다. 부호화된 네트워크에서는 어떠한 유저와 다른 유저들간의 신뢰 정도 혹은 불신뢰 정도의 순위(rank)를 매겨 유저간의 신뢰도를 표현할 수 있는데, 이는 간선 부호 예측(link sign prediction), 연결 예측(link prediction), 집단 탐지(community detection) 등의 문제를 푸는 데에 사용될 수 있습니다. 본 논문에서는 각 노드별로 다른 노드들과의 신뢰 정도 혹은 불신뢰 정도의 순위를 매기는 방법인 개인화된 신뢰도 랭킹(personalized trust ranking) 방법을 통해 간선 부호 예측 문제를 풉니다. 그림 1. 부호화된 네트워크 예시 Signed Random Walk with Restart (SRWR) 개인화된 신뢰도 랭킹을 계산하는 방법에는 여러 방법이 있는데, 본 논문에서는 랜덤 워크(random walk)를 기반으로 한 방법을

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)) 지