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 7

2019 1
- December 2019 1

Show more Show less

Popular Posts

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

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과 같습니다. 사용자와 상품간의 관계인 평점 뿐만 아니라 사용자간의 관계인 사회관계망 혹은 상품의 장르 정보가 함께 주어졌을 때 아직 발견되지 않은 평점을 정확하게 예측하는 것이 목표입니다…

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

본 문서에서는 SIGMOD 2017에서 발표된 "BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
Jinhong Jung et al., BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart, SIGMOD 2017Random Walk with RestartRandom Walk with Restart (RWR)는 그래프에서 두 정점 사이의 관계도 (relavance)를 측정하는 모델입니다. 하나의 정점을 기준으로 다른 모든 정점들과의 관계도를 구하면 기준 정점 (seed or query node)에 대한 개인화된 정점 랭킹을 구할 수 있고 이러한 랭킹은 그래프에서 추천 시스템, 이상 현상 탐지, 검색 등에 활용될 수 있습니다. 예를 들어서 아래 그림에서 기준 정점은 node 4가 되고 RWR의 결과는 오른쪽 표와 같이 node 4 대해 다른 정점들과의 점수를 계산합니다. 이와 같이 하나의 기준 정점에 대해 다른 모든 정점의 RWR 점수를 구하는 것을 single source RWR 문제라고도 합니다.

RWR은 랜덤 서퍼 (random surfer)를 이용하여 정점간의 관계도를 계산합니다. 랜덤 서퍼는 기준 정점에서 출발해서 매번 다음의 행동중 하나를 랜덤으로 선택하여 수행합니다. Random walk (랜덤 워크): 현재 정점의 이웃 정점중 하나를 랜덤으로 선택하여 이동합니다. 예를 들어서, 위 그림에서 현재 정점이 12번이라고 한다면 10번 또는 11번 중 하나를 랜덤으로 선택하여 이동합니다. Restart (재시작): 기준 정점으로 되돌아갑니다. 예를 들어서, 위 그림에서 기준 정점인 4번으로 돌아가는 것을 의미합니다. 이를 지속적으로 수행하다 보면 각 정점 별로 랜덤 서퍼가 방문하게 되는 확…

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): 확장성 테스트는 개발한 알고리즘이 얼마나 큰 데이터를 처리 할 수 있는지 실험적으로 확인하는 작업으로 생성되는 네트워크의 크기…

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…

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