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

2020 9

2019 1
- December 2019 1

Show more Show less

Popular Posts

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 RangeAuthors: Jun-Gi Jang, Dongjin Choi, Jinhong Jung, and U KangConference: 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해당 논문의 목표는 임의의 시간 범위에서 얻은 여러 시계열 데이터를…

Knowledge Extraction with No Observable Data

본 문서에서는 NeurIPS 2019에서 발표된 Knowledge Extraction with No Observable Data 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
Title: Knowledge Extraction with No Observable DataAuthors: Jaemin Yoo, Minyong Cho, Taebum Kim, and U KangConference 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로부터 가짜 데이터를 생성하여 이를 지식 증류에 활용하는 새로운 딥 러닝 구조를 제안합니다. 이때 모델의 지식을 증류하기 위해서는 먼저 지식을 추출해야 한다는 의미에서, 본 논문이 해결…

Accurate Relational Reasoning in Edge-labeled Graphs by Multi-labeled Random Walk with Restart

본 문서에서는 WWW Journal에 게재된 "Accurate Relational Reasoning in Edge-labeled Graphs by Multi-labeled Random Walk with Restart" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Accurate Relational Reasoning in Edge-labeled Graphs by Multi-labeled Random Walk with RestartAuthors: Jinhong Jung, Woojeong Jin, Ha-Myung Park, and U KangJournal: World Wide Web - Internet and Web Information Systems 2020Relation Inference Task관계 추론 (Relation Inference) 문제는 간선에 관계 라벨이 있는 그래프에서 연결되지 않은 두 정점이 주어졌을 때 두 정점 사이의 관계 라벨을 추론하는 문제입니다.
예를 들어서 그림 1과 같이 그래프에서 간선에 관계 라벨이 {childOf, spouseOf, grandchildOf} 중에 하나 있을 수 있을 때 두 정점 s와 t 사이의 라벨을 맞추는 문제 입니다.
관계 추론 문제를 푸는 방법은 전통적으로 크게 path feature model과 translation based model로 분류되어 다루어져왔습니다. path feature model은 두 정점 사이에 특정 길이의 path를 추출하여 이를 기반으로 학습을 하여 추론을 하는 방법론입니다. 그러나 그래프에서 path를 추출하는 작업은 길이가 조금만 길어져도 많은 계산량을 요구하기 때문에 전통적인 path feature model은 짧은 경로의 path만을 대상으로 학습을 하였고 이는 더 긴 path로 부터 얻을 수 있는 정보를 활용할 수 없게 되어 추론 성능에 제약이 있습니다. translation based model은 시작 정점의 임베딩에 관…

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 2020Tucker Decomposition 동영상 (가로, 세로, 시간), 기상 데이터 (오염물질, 위치, 시간) 등과 같이 다양한 데이터들이 밀도 높은 텐서 (Dense tensor)로 표현됩니다. 터커 분해 (Tucker Decomposition)은 텐서 데이터를 분석하는 가장 유명한 모델 중 하나이며 차원 축소, 클러스터링, 추천 시스템 등과 같이 다양한 응용들에서 활용하고 있습니다.
터커 분해는 그림 1의 예시와 같이 주어진 텐서를 각 차원의 저계수 요인행렬 (low-rank factor matrix)과 관계간의 강도를 표현하는 코어 텐서 (core tensor)로 분해합니다. 터커 분해는 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서간의 차이를 줄이는 방향으로 요인 행렬들과 코어 텐서를 학습합니다.
ALS (Alternating Least Square)는 터커 분해의 요인 행렬들과 코어 텐서를 학습할 때 사용하는 접근법 중 하나입니다. 해당 방법은 임의의 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하며, 요인 행렬들을 순서대로 업데이트합니다. 그림 1의 예에서는 행렬 B와 C를 고정시키고 A를 업데이트합니다. 그 다음, A와 C를 고정시키고 B를 업데이트하며, C도 마찬가지로 A와 B를 고정시켜 업데이트합니다. 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서 간의 차이가 수렴할 때까지 업데이트를 반복합니다.
Limitations of Exis…

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 PreferencesAuthors: Bonhun Koo, Hyunsik Jeon, and U KangConference on The 24th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2020, SingaporeNews Recommendation

본 논문의 목적은 온라인 뉴스 미디어의 사용자를 대상으로 개별 뉴스를 추천할 수 있는 기법을 제안하는 것 입니다. 뉴스 기사의 아래와 같은 특징 때문에 뉴스 추천 시스템은 일반적인 추천 시스템에 비하여 기계 학습을 이용한 추천 모델을 활용 하였을 때 좋은 성능을 기대하기 어렵습니다. 수 십만개의 새로운 뉴스 기사가 매일 출간됩니다.추천 시간에 따라서 사용자가 흥미를 보이는 뉴스가 빠르게 변합니다. 다시 말해, 수많은 새로운 뉴스 기사가 매일 생성 되며 이를 추천 대상으로 삼아야 하기 때문에 뉴스 추천 시스템에서는 학습 단계에서 활용되는 뉴스 기사들과 실제로 사용자에게 추천해야할 뉴스 기사는 다른 경우가 많습니다. 또한 추천 시간이 변화하면 사용자가 실제로 선택할 뉴스의 내용이 변화할 수 있는데, 예를 들면 월드컵 시즌에는 사용자들이 전반적으로 그들의 개별 취향과는 상관없이 축구 관련 뉴스에 흥미를 보이기도 합니다.
본 논문은 이러한 상황을 극복하고자 '일시적 전체 취향'(Global Temporal Preference)을 활용합니다. 또한, Attention network를 응용하여 '사용자의 개별 취향'…

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

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 KangConference: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019Segmentation of 3D LiDAR Point Clouds 3차원 라이다 센서 (3D LiDAR sensor)란 빛을 이용하여 주변 물체까지의 거리를 측정하여 센서 주변에 있는 물체들에 대한 위치 정보를 전달해주는 장치입니다. 라이다 센서는 실내에서 사용되는 안내 로봇부터 자율주행 차량까지 다양한 분야에서 사용되고 있습니다. 이때, 라이다 센서는 주로 주변에 물체가 있는지 없는지를 인식 (detection)하거나, 물체가 있다면 어떤 물체인지를 식별 (classification)하는 일을 주로 하게 됩니다. 특히 실내외에서 사람을 인식하는 보행자 식별 (pedestrian classification) 과정은 안전을 위해서도 중요하기 때문에 활발하게 연구되고 있는 분야입니다.

그림 1은 현관에 설치된 라이다 센서를 통해 보행자를 인식하는 예시를 보여주고 있습니다. 라이다 센서가 인식한 점 정보 (Input Data)를 전달받은 후 다음과 같은 네 단계를 통해 보행자 인식이 이루어 집니다. 관심 영역 필터링 (ROI filtering): 우리가 관심을 가지는 영역 (range of interetst, R…

Data Context Adaptation for Accurate Recommendation with Additional Information

본 문서에서는 IEEE BigData 2019 에서 발표된 "Data Context Adaptation for Accurate Recommendation with Additional Information" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.

Title: Data Context Adaptation for Accurate Recommendation with Additional InformationAuthors: Hyunsik Jeon, Bonhun Koo, and U KangConference: IEEE BigData 2019 Data Context-aware Recommendation 추천 시스템은 모든 IT 서비스 회사들에게 필수적인 기능입니다. 추천 시스템은 고객들에게 개인화된 추천을 제공함으로써 수많은 상품들 중 필요한 상품을 쉽게 찾을 수 있게 하고 회사의 매출 향상으로 이어지게 됩니다. 추천 시스템은 사용자와 가장 가까운 상품들을 예측하고 사용자들에게 추천하는 방식으로 동작합니다.

초창기의 추천 시스템은 사용자와 상품간의 관계 정보 (평점)만을 이용하여 문제를 해결하였습니다. 그러나 최근에는 추가적인 정보 (사용자들의 관계망, 상품의 카테고리 정보 등)를 쉽게 이용할 수 있기 때문에 이러한 정보들을 같이 사용하여 더 정확하게 추천하는 연구들이 많이 진행되고 있습니다. 이처럼 추가적인 정보들을 같이 사용하여 추천하는 문제를 Data Context-aware Recommendation이라고 합니다. 본 논문에서는 Data Context-aware Recommendation 문제에서 정확한 추천 성능을 제공하는 새로운 알고리즘을 제안합니다.
Data Context-aware Recommendation 문제를 도식화하면 그림 1과 같습니다. 사용자와 상품간의 관계인 평점 뿐만 아니라 사용자간의 관계인 사회관계망 혹은 상품의 장르 정보가 함께 주어졌을 때 아직 발견되지 않은 평점을 정확하게 예측하는 것이 목표입니다…