Accurate Graph-Based PU Learning without Class Prior

Posted by 날짜:

본 문서에서는 데이터 마이닝 분야의 ICDM 2021 학회에서 발표될 Accurate Graph-Based PU Learning without Class Prior 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.

  • Title: Accurate Graph-Based PU Learning without Class Prior
  • Authors: Jaemin Yoo*, Junghun Kim*, Hoyoung Yoon*, Geonsoo Kim, Changwon Jang, and U Kang (*equal contribution)
  • Conference: IEEE International Conference on Data Mining (ICDM) 2021

Graph-Based PU Learning

PU 학습(positive-unlabeled learning, PU learning)은 양성(positive) 데이터와 미분류(unlabeled) 데이터가 주어졌을 때 이진 분류기(binary classifier)를 학습하는 문제입니다. 일반적인 지도 학습(supervised learning)에서는 학습에 사용할 수 있도록 양성 및 음성(negative) 클래스 라벨이 모두 주어져 있다고 가정합니다. 반면, PU 학습에서는 미분류 데이터가 양성 및 음성 데이터를 모두 포함하고 있고, 음성 데이터에 대한 라벨은 주어져 있지 않다고 가정합니다. 그림 1은 일반적인 지도 학습 문제와 PU 학습 문제의 차이점을 보여줍니다. PU 학습에서는 양성 데이터와 음성 데이터 사이의 경계를 분명하게 알기 어렵기 때문에 정확한 분류기를 학습하는 것이 어렵습니다.

그림 1. PU 학습의 예시.

PU 학습 문제는 실제 상황에서 흔히 나타납니다. 예를 들어 신용카드 거래 내역 중 사기 거래를 탐지하는 문제를 생각해볼 수 있습니다. 경찰에 의해 직접 검거된 사기의 경우에는 분명한 "사기" 라벨을 매길 수 있지만 나머지 모든 거래에 대해 "정상" 라벨을 붙이기는 어렵습니다. 나머지 거래 중에도 아직 탐지되지 않은 사기 거래가 포함되어 있기 때문입니다. 이 경우, 사기가 아닌 모든 거래 내역을 음성 데이터로 가정하는 것보다는 이를 미분류 데이터로 가정하고 PU 학습 문제를 푸는 것이 결과적으로 더 정확한 모델로 이어질 수 있습니다.

본 논문에서는 더욱 구체적인 상황을 가정하여 그래프 기반 PU 학습 문제를 다룹니다. 여기서는 예측의 대상이 되는 데이터들이 그래프(graph) 형태로 연결되어 있다고 가정하고, 그래프 내에서 인접한 데이터는 인접하지 않은 데이터에 비해 더 유사도가 높다고 가정합니다. 즉, 각 데이터의 피처 벡터와는 별개로 그래프 구조를 바탕으로 데이터의 특성을 이해할 수 있는 것입니다. 이러한 그래프를 활용하면 미분류 데이터를 일차적으로 분류할 수 있는데, 예를 들면 알려진 양성 데이터와 가까운 미분류 데이터를 "약양성" 데이터로, 알려진 양성 데이터와 먼 미분류 데이터를 "약음성" 데이터로 나누는 것이 한 가지 방법이 될 수 있습니다.

Class Prior

그래프 기반 PU 학습 문제를 다루는 기존의 모든 논문은 클래스 사전 확률(class prior)이 주어져 있다고 가정합니다. 이는 전체 미분류 데이터 중 실제 양성 데이터의 비율을 나타내는 값으로 미분류 데이터에 대한 핵심적인 정보로서 기능합니다. 예를 들어 미분류 데이터가 10,000개이고 클래스 사전 확률이 0.7이라면 전체 미분류 데이터 중 7,000개가 양성 데이터라는 뜻입니다. 이러한 정보를 미리 알고 있다면 그래프 구조를 활용해 양성 데이터에 가장 가까운 미분류 데이터 7,000개를 골라 약양성으로 표기하는 방식으로 최소한의 성능을 이끌어 낼 수 있습니다.

하지만, PU 학습 상황에서 클래스 사전 확률을 알기 위해서는 미분류 데이터에 대한 충분한 지식이 필요하기 때문에 실제로는 클래스 사전 확률이 주어지지 않은 경우가 많습니다. 위에서 예시로 든 신용카드 사기 거래 탐지 문제의 경우 클래스 사전 확률은 전체 미분류 거래 중 사기 거래가 차지하는 실제 비중을 의미하는데, 이를 미리 정확하게 아는 것은 어렵습니다. 기존 논문이 클래스 사전 확률을 가정한 것은 이런 가정이 실제 상황에서 타당해서라기보다는 이러한 가정 없이 주어진 데이터만으로 PU 학습 문제를 푸는 것이 무척 어렵기 때문입니다.

GRAB

본 논문에서는 그래프 기반 PU 학습 문제를 풀기 위한 새로운 방법인 GRAB(Graph-based Risk minimization with iterAtive Belief propagation)을 제시합니다. GRAB은 클래스 사전 확률이 주어지지 않은 상황에서도 그래프 구조를 기반으로 이를 추정할 수 있고, 그 결과 클래스 사전 확률을 입력으로 받는 기존 방법에 비해 더 좋은 성능을 보입니다. 구체적으로, GRAB은 주어진 그래프를 확률 그래프 모델로 가정한 다음 기댓값 최대화(expectation-maximization, EM) 알고리즘과 비슷한 방식을 통해 이진 분류기를 점진적으로 개선하고, 그 과정에서 사전 확률을 추정합니다.

GRAB은 반복 과정(iterative process)을 통해 그래프 합성곱 신경망(graph convolutional network, GCN) 분류기를 학습하는 알고리즘이라 할 수 있습니다. 각 반복 단계(iteration)는 두 개의 연산으로 구성됩니다. 첫 번째는 주변화(marginalization) 연산으로, 이 단계에서는 현재 가지고 있는 GCN 모델을 바탕으로 각 미분류 데이터가 양성(혹은 음성)일 확률을 계산합니다. 이는 주어진 그래프를 마코프 망(Markov network)으로 가정한 뒤 GCN의 예측값을 기반으로 하여 신뢰 전파(belief propagation) 알고리즘을 동작시킴으로써 수행되며, GCN이 만드는 각 데이터별 예측 결과를 확률 모델 측면에서 그래프 전체로 전파시키는 역할을 합니다.

두 번째는 업데이트(update) 단계로, 여기서는 위에서 계산한 각 변수별 주변 확률(marginal probability)을 통해 새로운 목적 함수를 생성하고, 이 목적 함수를 바탕으로 새로운 GCN 분류기를 학습합니다. 다만, 각 미분류 데이터가 분명하게 양성 혹은 음성으로 취급되는 것이 아니라 양성과 음성 모두 될 수 있는 확률 변수로 취급되기 때문에 분류기 학습에 더 풍부한 근거를 제공한다는 특징이 있습니다. 반복 과정을 통해서 GCN 분류기의 성능이 점진적으로 향상됨에 따라 목적 함수가 주어진 데이터 및 그래프 구조의 특성을 더 잘 반영하게 되고, 그 결과 GCN 분류기의 성능을 다시 개선하는 선순환을 이루게 됩니다.

Experiments

본 논문은 실험을 통해 GRAB과 그래프 기반 PU 학습을 위한 기존 방법을 비교합니다. 그림 2를 보면 GRAB이 대부분의 경우에서 가장 뛰어난 성능을 보입니다. 다만, 이 결과는 클래스 사전 확률을 사용하지 않는 GRAB과는 달리 모든 경쟁 상대가 정확한 클래스 사전 확률을 알고 있다고 가정한 것으로, GRAB에게 무척 불리한 실험 설정입니다. 그럼에도 불구하고 GRAB은 가장 좋은 성능을 보여주고, 클래스 사전 확률이 GRAB 뿐 아니라 모든 경쟁 상대에게도 알려져 있지 않다고 가정하면 이 차이는 훨씬 더 커집니다 (논문에 자세한 결과가 나타나 있습니다).

그림 2. GRAB과 기존 방법의 정확도 비교.

그림 3는 GRAB의 반복 학습 과정에서 위에서부터 순서대로 (a) 목적 함수, (b) 테스트 정확도, 그리고 (c) 추정된 클래스 사전 확률이 어떻게 변하는지 보여줍니다. 맨 윗줄과 두 번째 줄을 보면 GRAB의 학습 과정에서 일관성 있게 목적 함수가 감소하고, 정확도가 향상되는 것을 알 수 있습니다. 마지막 줄을 보면 GRAB이 클래스 사전 확률에 대한 정보를 전혀 사용하지 않으면서도 학습을 통해 이를 비교적 정확하게 근사한다는 것을 알 수 있습니다. 이는 미분류 데이터라고 하더라도 실제 클래스에 대한 정보가 그래프 구조 및 각 데이터의 피처 벡터에 충분히 내재되어 있다는 것, GRAB이 이를 효과적으로 추출하여 학습에 활용한다는 것을 보여줍니다.

그림 3. GRAB의 훈련 과정에서 목적 함수 및 클래스 사전 확률의 변화.

Conclusion

본 문서에서는 ICDM 2021에서 발표될 예정인 Accurate Graph-Based PU Learning without Class Prior 논문을 소개하였습니다. 해당 논문은 그래프 형태의 데이터에서 PU 학습 문제를 수행하는 새로운 방법인 GRAB을 제시하였고, 이는 기존 방법과 달리 클래스 사전 확률을 모르는 상태에서도 동작한다는 점에서 뚜렷한 장점을 갖습니다. 실제 그래프 데이터에 대한 실험 결과 GRAB은 반복을 통한 학습 과정에서 클래스 사전 확률을 비교적 정확하게 추정하였고 기존 방법에 비해 더 높은 분류 정확도를 보였습니다.

PU 학습 문제는 실생활에서 빈번하게 관찰됩니다. 앞에서 예시로 든 사기 탐지 문제를 포함하여 소셜 네트워크에서의 봇(bot) 탐지, 쇼핑 사이트에서의 리뷰 조작 탐지 등 이진 분류 문제에서 클래스간 불균형이 존재하고 음성 라벨에 대한 확신을 가질 수 없는 상황이라면 대부분 PU 학습 문제로 볼 수 있습니다. 이러한 상황에서 단순한 이진 분류 학습을 수행하는 것은 데이터 특성을 무시하고 미분류 데이터에 포함된 양성 데이터를 고려하지 못하는 결과를 낳습니다. 사물간 상호작용은 대부분의 경우 그래프로 나타나고, 이러한 그래프는 피처와 더불어 클래스 특성을 이해하는 데 큰 도움을 주기 때문에, 그래프 기반 PU 학습은 실세계 이진 분류 문제를 새로운 방식으로 모델링하고 더 정확한 결과를 만드는 데 사용될 수 있습니다. 자세한 내용은 논문에서 확인하실 수 있습니다.