본 문서에서는 2022년 KAIS 저널에 발표된 "Graph-based PU Learning for Binary and Multiclass Classification without Class Pior" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Graph-based PU Learning for Binary and Multiclass Classification without Class Prior
- Authors: Jaemin Yoo*, Junghun Kim*, Hoyoung Yoon*, Geonsoo kim, Chanwon Jang, and U Kang (*equal contribution)
- Journal: Knowledge and Information Systems (KAIS) 2022
Graph-Based MPU Learning without Class Prior
MPU 학습(multi-positive-unlabeled learning, MPU learning)은 여러 클래스의 양성(positive) 데이터와 미분류(unlabeled) 데이터가 주어졌을 때, 데이터를 각 양성 클래스 및 음성(negative) 클래스로 분류하는 분류기(classifier)를 학습하는 문제입니다. 일반적인 PU 학습(positive-unlabeled learning, PU learning)은 양성 데이터와 음성 데이터를 분류하는 이진 분류(binary classification)를 수행하는데, MPU 학습은 이에 더해 각 양성 데이터 각각의 양성 클래스로 분류하는 다항 분류(multiclass classification)를 수행하기 때문에, MPU 학습이 일반적으로 PU 학습보다 어렵습니다.
그림 1. PU 학습, MPU 학습의 예시.
MPU 학습 문제는 실생활에서 어렵지 않게 찾아볼 수 있습니다. 예를 들어 MMORPG(massively multiplayer online role-playing game) 속 부정 사용자를 탐색하고, 각 부정 사용자의 위반한 규정을 분류하는 문제를 생각해볼 수 있습니다. 게임 회사에 의해 직접 색출된 부정 사용자는 분명한 "부정" 라벨(label)을 매길 수 있지만, 나머지 사용자에 대해서는 아직 색출되지 않은 부정 사용자가 있을 수 있기 때문에 "정상" 라벨을 붙이기 어렵습니다. 이에 더해 각 부정 사용자가 어떠한 규정을 위반하여 색출되었는지도 분류할 수 있다면, 부정 사용자 분석 측면에서 효율적입니다. 이러한 상황에서는 색출된 부정 사용자를 제외한 나머지 사용자를 미분류 사용자로 가정하고, 색출된 부정 사용자에 대해서는 어떤 규정을 위반하였는지를 분류하는 MPU 학습을 통해 문제를 푸는 것이 효과적입니다.
본 논문은 그래프 기반 PU 학습 문제를 다룬 ICDM 2021 논문(블로그)을 확장한 논문으로, PU 학습 문제를 MPU 학습 문제로 확장한 그래프 기반 MPU 학습을 다룹니다. 이 학습 문제에서는 앞에서 설명한 MPU 학습 상황을 기반으로, 분류 대상 데이터들이 서로 그래프 형태로 연결되어 있고, 그래프 내 인접한 데이터는 인접하지 않은 데이터에 비해 관련도가 높다고 가정합니다. 예를 들어,
위의 MMOPRG 예시에서 각 사용자들은 다른 사용자들과 친구, 파티 플레이(party play) 등으로 관계를 맺는데, 이러한 관계가 사용자들 사이의 간선(edge)으로 연결된 MMORPG 그래프 데이터에서의 MPU 학습을 생각해 볼 수 있습니다. 그래프 구조는 분류기를 학습할 때 각 데이터의 피쳐 벡터(feature vector)와 더불어 미분류 데이터의 분류에 사용될 수 있습니다.
클래스 사전 확률(class prior)은 전체 데이터 중 실제 양성 데이터의 비율입니다. MPU 학습에서는 음성 클래스 데이터 라벨에 대한 정보가 주어지지 않기 때문에, 클래스 사전 확률은 미분류 데이터를 분류할 때 핵심적인 정보입니다. 이 때문에 기존의 MPU 학습 논문들은 클래스에 대한 사전 확률이 알려져있다고 가정하였습니다. 하지만, 클래스 사전 확률을 알기 위해서는 미분류 데이터에 대한 충분한 정보가 사전에 필요하기 때문에, 실세계 문제에서는 사전 확률이 알려져 있지 않은 경우가 많습니다.
Proposed Method
본 논문에서는 클래스 사전 확률이 주어지지 않은 상황에서 그래프 기반 MPU 학습 문제를 정확하게 풀기 위한 새로운 방법인 GRAB(Graph-based Risk minimization with iterAtive Belief propagation)을 제시합니다. GRAB은 그래프 구조를 기반으로 각 클래스의 사전 확률을 추정하고, 이를 통해 분류기를 학습하여 기존 방법보다 더 정확하게 분류 대상들을 분류합니다. 새롭게 제안된 GRAB과 기존 ICDM 2021에 제출된 논문의 가장 핵심적인 차이점은, 목적 함수를 설계할 때 각 미분류 데이터가 여러 양성 클래스 및 음성 클래스 모두가 될 수 있는 확률 변수로 취급하는 것 입니다. 다시 말해, 미분류 데이터의 라벨을 단순하게 음성 혹은 여러 양성 클래스 중 하나로 정하지 않고, 각 클래스에 속할 확률을 수도(pseudo) 라벨로 사용합니다. GRAB의 전체적인 구조는 그림 2에 정리되어 있습니다.
그림 2. GRAB의 개요. GRAB은 주변화(marginalization) 단계와 업데이트(update) 단계를 반복하여 수행하며 정확한 분류기를 점진적으로 학습함.
GRAB 은 두가지 연산의 반복 과정(iterative process)을 통해 GCN(graph convolutional network) 분류기를 학습합니다. 반복 과정의 첫 번째 연산은 주변화(marginalizatoin) 연산입니다. 이 단계에서는 현재 학습된 GCN 분류기의 예측값을 기반으로 신뢰 전파(belief propagation) 알고리즘을 동작하여 각 미분류 데이터의 각 클래스에 대한 주변 확률(marginal probability)을 계산합니다.
두 번째 연산 과정은 업데이트(update) 단계입니다. 이 단계에서는 주변화 과정에서 계산한 각 주변 확률을 통해 새로운 목적 함수를 설정하고, 이 목적 함수를 최소화하면서 새로운 GCN 분류기를 학습합니다. 목적 함수는 각 미분류 데이터를 확률 변수로 취급하여 미분류 데이터의 라벨을 단순하게 음성 혹은 하나의 양성 클래스로 정하지 않고, 각 클래스에 속할 확률값들을 수도 라벨로 사용하여 분류기 학습에 더 풍부한 정보를 제공합니다.
업데이트 연산 과정에서 목적 함수를 설계하고, 최소화하면서 현재 학습된 GCN 분류기보다 더 높은 성능을 보이는 GCN 분류기를 학습하면, 주변화 연산에서는 이를 통해 더욱 정교화된 주변 확률을 구할 수 있습니다. 정교화된 주변 확률을 활용하면 데이터를 더 잘 반영한 목적 함수를 설계할 수 있는데, GRAB은 이 목적 함수를 업데이트 연산에서 다시 최소화하면서 GCN 분류기의 정확도를 높입니다. 이러한 순환 구조를 반복하면서 GRAB은 MPU 학습에서 높은 정확도를 보이는 GCN 분류기를 학습합니다.
Experiments
본 논문은 실험을 통해 GRAB과, 그래프 기반 MPU 학습을 위한 기존 방법들을 비교합니다. 그림 3은 그래프 기반 MPU 학습에서 GRAB 과 기존 방법들의 정점(node) 분류 정확도를 비교합니다. 여기서 주목할만한 점은 GRAB을 제외한 기존 기법들에서는 클래스 사전 확률이 알려져 있다고 가정했다는 점입니다. 그럼에도 불구하고, GRAB 은 모든 데이터에서 높은 차이로 가장 정확한 성능을 보여줍니다.
그림 3. MPU 학습에서 GRAB과 기존 방법들의 정확도 비교.
GRAB은 반복 과정을 통해 각 클래스의 사전 확률을 예측할 수 있습니다. 그림 4는 반복 과정의 진행에 따른 로스(loss), F1 스코어, 그리고 각 클래스 별 사전 확률의 예측값을 보여줍니다. 반복 과정이 진행됨에 따라 로스는 줄어들고, F1 스코어는 높아집니다. 이 때 주목할만한 점은 GRAB이 예측한 양성 클래스 별 사전 확률이 실제 사전 확률과 점진적으로 비슷해진다는 점입니다. 이는 사전 확률이 알려지지 않은 MPU 학습 상황에서도 GRAB은 각 양성 클래스로부터 중요한 피쳐를 추출할 수 있다는 것을 보여줍니다.
그림 4. 반복 과정이 진행됨에 따른 로스, F1 점수, 클래스 별 사전 확률의 예측값.
Conclusion
본 문서에서는 KAIS 2022에 발표된 Graph-based PU Learning for Binary and Multiclass Classification without Class Prior 논문을 소개하였습니다. 이 논문은 실세계 데이터의 클래스 사전 확률을 미리 정확히 알고 있는 것이 어렵다는 점에 착안하여, 클래스 사전 확률을 모르는 상황에서도 그래프 기반 MPU 학습 문제를 정확하게 풀 수 있는 방법인 GRAB을 제안하였습니다. 실제 그래프 데이터에서 실험을 진행한 결과 GRAB은 반복을 통한 학습 과정에서 기존 기법들에 비해 더 높은 정점 분류 정확도를 보였습니다.
그래프 기반 MPU 학습 문제는 실세계에서 쉽게 접할 수 있습니다. 예를 들어, 앞에서 소개한 MMORPG 속 부정 사용자 탐지 문제 외에도 소셜 네트워크에서 봇(bot)과 스팸(spam) 광고 유저를 동시에 탐지하는 등, 각 분류 대상끼리의 상호 작용이 존재하고 음성 라벨에 대한 불확실성이 있는 모든 상황에서 그래프 기반 MPU 학습 기법들이 활용될 수 있습니다. 분류 대상 간 상호 작용은 보통 그래프로 나타내어지고, 이러한 그래프는 각 클래스의 성질을 이해하는 데 큰 도움을 주기 때문에, 그래프 기반 MPU 학습은 실세계 분류 문제를 더욱 정확하고 효과적으로 풀 수 있는 방법이 될 수 있습니다. 자세한 내용은 논문에서 확인하실 수 있습니다.