[ICML 2018] GAIN: Missing Data Imputation using Generative Adversarial Nets

Paper url : https://arxiv.org/abs/1806.02920

Author and affiliation

Figure 01: paper snapshot

Background

Three assumptions of missing values

우리는 머신러닝을 활용한 분석 및 예측을 진행하면서 다양한 데이터를 접하게 된다. 그 중 결측치가 존재하는 데이터를 분석하는 일은 흔한 일일 것이다. 결측치는 다음과 같이 3가지 유형으로 분류할 수 있다 [1].

1. MCAR (Missing Completely at Random) : 완전 무작위 결측

2. MNAR (Missing Not at Random) : 결측치가 특정 의미를 내포하며 그 의미가 결측된 변수를 지칭

3. MAR (Missing at Random) : 결측치가 특정 의미를 내포하며 그 의미가 데이터 내 다른 변수를 지칭

예를 들어 특정 회사에서 코로나 감염 여부를 예측하기 위해 체온 측정, 일주일 내 회식 참석 여부를 조사하였다고 가정하자. 독립변수는 체온, 회식 참석 여부이며 종속변수는 코로나 감염 여부이다. 이 때 체온 변수에 결측이 발생하였다면 위 3가지 가정은 각각 다음에 해당한다.

각 부서의 데이터를 종합하여 저장하는 와중, 담당자가 실수로 특정 날짜의 데이터를 누락하였다면 이 경우 MCAR에 해당한다. MCAR 가정은 결측치가 어떠한 의미를 지니지 않고 완전 무작위로 결측이 발생한 경우이기 때문이며 고전적인 경우의 예를 들면 데이터 sheet에 커피를 쏟아 임의로 값이 지워진 경우가 해당한다.

반면 코로나에 걸리거나, 감기에 걸려 고열이 발생한 회사원들이 의도적으로 체온 측정을 기피하였다고 가정하자. 이 경우 체온 변수에 결측이 발생한 샘플은 체온 측정 당시 고열이였을 것이라고 추정할 수 있다. 이 경우 결측치가 특정 의미를 내포하며(체온 변수의 결측 = 고열) 그 의미가 결측이 발생한 변수(체온)을 지칭하기에 MNAR 가정에 해당한다.

마지막으로 체온 측정을 할 당시에 회식에 참석한 부서가 존재하여 체온 측정을 실시하지 못해 결측이 발생한 경우라면 MAR 가정에 해당한다. 이 경우 결측치가 특정 의미를 내포하며(체온 변수의 결측 = 회식 참석) 그 의미가 데이터 내 다른 변수(회식 참석 여부)를 지칭하기 때문이다.

이와 같이 결측치 가정을 분류한 이유는 바로 결측치의 가정에 따라 우리가 대처해야할 방법이 달라지기 때문이다. 예를 들어 결측치에 아무런 의미가 없는 MCAR 가정에 의해 결측치가 존재한다면, 이 경우 데이터를 삭제해도 분석이나 예측에 어떠한 영향을 미치지 않는다(데이터가 충분하다는 가정 하에). 반면 결측치에 특정 의미가 존재하는 MNAR, MAR 가정의 경우 데이터를 삭제한다면 왜곡된 결과를 얻을 수 있다.

따라서 데이터의 도메인 지식에 기반하여 결측치가 어떤 특성을 확인하는지는 매우 중요하며, 만약 도메인 지식이 없다고 한다면 결측이 발생한 sample들과 그렇지 않은 sample들의 target variable의 분포 확인을 통해 결측치가 target variable에 어떤 영향을 끼치는지 확인하는 과정이 필요하다.

Single imputation & Multiple imputation

결측치를 다루는 방법에는 삭제(deletion)와 대치(imputation)이 존재한다. 대부분의 경우 결측치를 보완한다의 의미는 대치(=결측치를 임의의 값으로 대체함)를 뜻하기에 삭제는 핵심적인 내용만 다루도록 하겠다.

삭제란 결측치를 포함하는 학습 데이터를 모두 제거하는 것을 뜻한다. 결측치가 특정 의미를 내포하지 않는 MCAR에 해당하거나 그 비율이 많지 않을 때 사용할 수 있다. 일반적으로 결측 비율이 10%가 넘어가면 삭제는 좋은 선택이 아니다 [2]. 비교적 간단하며 computational cost에 이점이 있으나, 결측 발생 원인이 MNAR, MAR 가정에 해당한다면 원래 분포를 왜곡할 수 있다는 단점이 존재한다.

대치(이하 imputation)는 단순 대치(single imputation)와 다중 대치(multiple imputation)으로 구분할 수 있다. Single imputation과 multiple imputation을 구분하는 기준은 결측치의 후보군 개수이다. 만약 결측치를 대체할 수 있는 후보군이 단일 값이라면 single imputation, 여러개가 존재한다면 multiple imputation이라고 부른다. 다음 그림을 통해 쉽게 이해할 수 있다.

Figure 02: single imputation & multiple imputation

일반적으로 single imputation의 경우 multiple imputation에 비해 표준 오차 과소의 문제를 지닌다고 말한다. 이는 불확실한 결측치를 단일값으로 대체하는 방법의 특성상, 추정값에 대한 과도한 신뢰도를 지닌다는 의미이다. 이에 반해 multiple imputation의 경우 결측치에 대한 후보군을 여러개 생성하기 때문에 보다 신뢰성 있는 추론이 가능하며 결측치의 신뢰 구간 또한 추정할 수 있다는 장점이 존재한다. 본 논문의 방법인 GAIN은 multiple imputation에 해당한다.

Related works

Single/multiple imputation의 대표적인 알고리즘들을 살펴보자. 먼저 single imputation에서는 대표적으로MissForest 알고리즘 [3]을 들 수 있다.

Single imputation - MissForest

MissForest는 이름에서 유추할 수 있듯, random forest 알고리즘의 예측값으로 결측치를 채워넣는 방법을 말한다. 총 4 단계를 거쳐 imputation이 진행되는데 세부 단계를 살펴보면 다음과 같다.

• Step1) 임의 대체

결측치를 임의로 대체하는 단계이다. 단순 평균, 최빈값과 같이 통계량을 사용하거나 간단한 다른 대치 방법을 사용한다.

Figure 03: 임의 대체의 예

• Step 2) Random Forest 활용 변수별 결측치 예측

결측치 비율이 가장 낮은 변수부터 random forest를 사용하여 예측을 진행한다. 이 때 학습 데이터는 결측이 발생하지 않은 sample이며 이를 토대로 결측치 예측을 진행한다. Figure 03을 통해 우리는 $x_{1}, x_{2}$가 결측치 비율이 가장 낮은 변수임을 알 수 있다. 따라서 결측치는 예측은 column 순서대로 진행하며 Figure 04와 같다.

Figure 04: 변수별 결측치 예측의 예

• Step 3) 위 과정과 같이 결측치가 보완된 데이터를 바탕으로 동일한 과정 진행

결측이 채워진 데이터(step 2 이후)를 사용하여 변수별 결측치 예측을 다시 진행한다. Step 3에서의 random forest 예측값은 step 2와는 다른 값이 될 것이다. 학습에 사용된 데이터 중 결측치의 값이 변경되었기 때문이다(step 1 - 평균, step 2 - 평균을 바탕으로한 random forest 예측값). 그림으로 표기하면 Figure 05와 같으며 결측치의 값이 step 2와는 다른 것을 확인할 수 있다.

Figure 05: Step 2 반복

• Step 4) 종료 조건을 만족할 때까지 step 3 반복

Step 3의 과정은 종료 조건을 만족할 때까지 반복된다. 여기서 종료 조건이라 함은 1. 사용자가 지정한 반복 횟수 도달과 2. 결측 대체 값의 변화량이 일정 기준점 이하로 수렴할 때를 말한다. Figure 06은 후자의 종료 조건을 만족할 때까지 반복하는 경우이다.

Figure 06: 종료조건을 만족한 imputed data

종료조건을 만족하여 대치가 완료된 데이터(imputed data)가 MissForest의 최종 결과이다. 각 결측치에 대해서 대체 후보군이 1개씩 존재하기 때문에 single imputation에 해당한다.

Multiple imputation - multiple imputation using denoising autoencoders (MIDA) [4]

Multiple imputation 방법으로는 대표적으로 multiple imputation by chained equations (MICE) [5], Amelia [6] 등이 존재한다. 이들은 Python, R을 이용하면 쉽게 사용할 수 있어 접근성이 높다. 해당 방법들은 타 블로그에 자세한 설명이 되어있으니 설명은 생략하였다.

Multiple imputation 방법 중 하나로 소개할 MIDA는 MICE, Amelia와는 달리 deep learning 기반 imputation method이다. 본 review 논문인 GAIN 또한 deep learning 기반의 방법이기에 성능을 직접적으로 비교하고있다. MIDA는 이름에서 알 수 있듯 denoising autoencoders (DAE)를 활용한 multiple imputation 방법이다. 먼저 DAE를 살펴보자.

DAE는 autoencoder의 파생 모델로 noise가 섞인 input data로부터 noise가 제거된 원래의 input을 복원하는 모델을 말한다. 만약 정형 데이터에 적용이 되었다면 Figure 07과 같은 형태를 보인다.

Figure 07: DAE on structured data

MIDA는 잠재 변수(latent vector)의 dimension이 input의 dimension보다 높은 overcomplete autoencoder 구조를 사용한다. Overcomplete autoencoder 구조는 input data가 제공하는 정보보다 더 많은 정보를 찾을 때 사용한다. MIDA의 목적이 결측치를 채우는 것이기에 input data를 high-dimension으로 mapping하여 결측치의 내재된 정보를 탐색 후 다시 압축하는 과정을 통해 대치하는 알고리즘인 것이다. MIDA의 구조는 Figure 08과 같고 encoder의 경우 hidden node의 개수는 layer 당 $\theta$ (default = 7)만큼 증가하며 decoder의 경우 반대로 layer 당 $\theta$만큼 감소한다.

Figure 08: MIDA architecture

MIDA의 동작에 대해서 알아보자. 먼저 MissForest와 유사하게 임의 대체 과정을 거치는데 수치형 변수의 경우 평균, 범주형 변수의 경우 최빈값을 사용하여 임시 대치를 진행한다. 이후 DAE를 활용한 대치를 진행하며 n개의 data에 대해서 DAE의 초기 가중치를 변경하여 다양한 결측 대체값을 도출한다.

앞에서 설명을 생략하였으나 multiple imputation의 핵심은 n개의 imputed data의 다양성이다. Multiple imputation의 본질이 다양한 결측 후보군을 제시하여 신뢰도를 높히고 추정 구간을 제시할 수 있기 때문이다. MIDA의 경우 DAE의 초기 가중치로써 이를 구현한다고 볼 수 있다. 초기 가중치 뿐 아니라 noise 또한 n개 데이터 마다 다른 값이 부여되지만 DAE는 이를 제거하도록 복원하기 때문에 다양성에 기여하지는 못한다. MIDA의 전체 과정을 도식화 하면 Figure 09와 같다.

Figure 09: MIDA workflow

MIDA의 경우 deep learning을 활용한 imputation 방법의 시초격 모델이라고 볼 수 있다. 논문의 경우 MICE와 비교하여 대부분의 데이터 및 상황(결측치의 가정)에서 좋은 성능을 보였다고 하나 논문에서 제시된 data 외에 실 적용 시에도 동일한 결과를 보일지 의문이다. 필자가 논문의 성능을 믿지 못하는 이유는 다음과 같다.

논문의 주장에 따르면 MICE의 경우 특정 변수에서 결측치가 임계치 이상으로 발생할 때 이를 대치하지 못하지만 MIDA는 결측치의 양에 상관없이 대치가 가능하다고 한다. 이에 의구심을 가져 R에서 직접 실험한 결과(Python은 MICE가 제대로 구현되어있지 않은듯 하다) MICE가 결측치를 대치하지 못하는 경우는 오직 특정 변수가 모두 결측치로 구성되어 있을 때 뿐이였다.

동일한 환경에서 MIDA는 결측치 대치가 가능할까? 논문에서 주장한 바와 달리 MIDA 또한 평균 및 최빈값으로 임의 대체하는 과정을 거치기에 NaN으로만 구성된 변수는 대치를 진행하지 못한다. 논문에서 구체적인 실험 setting 및 사용 소프트웨어를 밝히지 않아 동일한 상황에서 검증할 수는 없으나 이와 같은 이유로 인해 실험 결과에 대한 의문이 남아있다. 다만 구현은 쉬우니 프로젝트를 진행할 일이 있다면 MIDA를 적용 후 MICE, KNN imputation 등의 다른 기법이 더 우수하였다고 내용 채우기에는 좋다.

Proposed method

Generative adversarial imputation nets (GAIN)은 2018년 국제머신러닝학회(ICML)에 등재된 논문이다. 이름에서 알 수 있듯이 GANs의 구조를 변경하여 결측치를 보완하는 방법이다. 본 포스팅은 GANs에 대한 사전지식이 있는 독자들이 본다는 가정하에 작성하였다. GAIN의 구조는 Figure 10과 같다.

Figure 10: GAIN architecture

GAIN은 생성자(generator)와 판별자(discriminator) 부분으로 나눌 수 있다. 생성자는 총 3가지 input을 받는데 각각은 data matrix ($\tilde{X}$), random matrix ($( \textbf{1}-M)\odot Z$), mask matrix ($M$)이며 대치가 완료된 imputed matrix를 output으로 삼는다.

Data matrix는 결측치는 0으로 임의 대치한 행렬을 뜻한다. 이는 생성자가 만들고자하는 목표 분포에 해당하며 정답 역할을 한다. Random matrix는 생성자가 가상의 데이터(결측치 대체 값)를 생성할 때 필요한 input에 해당한다. 일반적인 GANs에서의 white noise에 해당하며 noise는 feature마다 서로 다른 분포를 띈다. Mask matrix는 결측치는 0, 결측치가 아닌 값은 1로 할당한 matrix이다. 이는 생성자와 판별자 모두 사용되며 주된 목적은 판별자의 정답지 역할을 한다. 생성자에서의 역할은 feature noise $Z$와 pairwise product를 통해 차원을 일치시키는 역할을 한다. Feature noise의 경우 feature 개수 * sample 수 차원을 지니는데 이를 1-mask matrix와의 곱을 통해 결측치 부분에만 noise가 지닌 행렬을 만들어 주는 역할을 하는 것이다. Figure 11을 통해서 생성자의 input과 그의 역할을 확인할 수 있다.

Figure 11: 생성자의 inputs 및 그 역할

생성자는 앞에서 정의한 3가지 input을 받아 결측치를 보완한 행렬($\bar{X}$)을 출력한다. 단 생성자의 순수 output인 $\bar{X}$는 imputed matrix가 될 수 없는데, 그 이유는 생성자를 거치면서 신경망 연산에 의해 결측치가 아닌 기존값($\hat{x_{ij}}$)들 또한 변형이 오기 때문이다. 따라서 본래 결측치가 아니었던 값은 data matrix의 값을 가져오고, 결측치 자리만 생성값으로 대체한 행렬을 사용한다. Imputed matrix ($\hat{X}$)의 수식은 다음과 같다.

다음으로 판별자에 대해서 알아보자. 판별자의 input은 두 가지로, 생성자를 거친 imputed matrix와 mask matrix를 토대로 생성된 hint matrix ($H$)이다. Hint matrix는 판별자의 원활한 학습을 유도하기 위해 특정 eleme-nt에 대한 정답을 제공하며 epoch 마다 임의로 노출되는 값이 달라진다. Figure 12를 살펴보자.

Figure 12: 판별자의 inputs 및 그 역할

Hint matrix가 필요한 이유를 알기 위해서는 판별자의 역할에 대해서 알아야한다. 판별자는 생성자가 만들어낸 값(결측 대체 후보값)과 결측치가 아닌 실제값을 구분하는 역할을 한다. 일반적인 GANs에서의 판별자는 image 한 장에 대한 real, fake를 구분하는 것이기에 output layer는 1개(with sigmoid activation function), 혹은 2개(softmax activation function)의 hidden nodes를 사용한다.

이와 달리 GAIN은 정형 데이터의 모든 elements에 대한 classification을 진행하기에 sample의 개수(n) * feature의 개수(p)의 nodes를 가져야한다. Softmax activation을 사용하기에는 턱없이 많은 숫자이기에 multi label classification으로 접근하여 n*p개의 output nodes 각각에 sigmoid activate function을 사용하겠지만 일반적으로 정형데이터의 경우 n*p의 개수는 상당한 수준이라 학습에 어려움이 존재할 것이다.

Hint matrix를 살펴보면 실제값은 1, 결측치는 0, hint element는 0.5의 값을 갖고 있다. 판별자의 입장에서 이와 같은 정답의 일부가 들어온 것이기에 학습을 진행할 때는 0.5의 hint element에 대해서만 학습을 진행한다고 이해하면 된다. 즉 모든 element를 예측, 학습할 필요 없이 epoch마다 다르게 배정되는 일부 element에 대한 loss를 반영한다. 해당 그림에서 hint generator라는 별도의 network가 존재하는 것 처럼 보이지만 epoch 마다 element 자리를 변경하는 것이 hint generator를 의미한다.

Loss function of GAIN

다음으로 GAIN의 loss function에 대해서 알아보자. 생성자의 loss function은 두 가지로 구성이 되는데, 첫 번째 loss는 결측치가 아닌 기존값($\hat{x_{ij}}$)과 생성자를 거쳐 변형이 된 기존값($\bar{x_{ij}}$)의 mean squared error (MSE)이다. 앞에서 생성자의 3가지 input을 소개하며 data matrix의 역할을 생성자가 추구하는 목표 분포라고 설명하였는데 MSE term을 통해 확인할 수 있다. 이렇듯 결측치가 아닌 값만을 사용하여 결측치를 채우는 측면에서 추천 시스템(recommender system)에서 사용되는 matrix factorization (MF)과 유사하다. 실험에서 비교 대상으로 MF가 사용되는 이유지 않을까 싶다.

$$L_{G1}=MSE(\tilde{X},M\odot\bar{X})$$

생성자의 두 번째 loss이자 판별자의 loss는 각 element들의 real, fake에 대한 예측 확률과 mask matrix 사이의 cross entropy이다. 이 두 가지 loss가 적용된 그림은 Figure 13과 같다.

Figure 13: Loss function of GAIN

실제 GAIN 논문을 살펴보면 pseudo code를 비롯한 수식적 증명 등 자세한 내용을 확인할 수 있으니 관심이 있는 독자는 참고하면 좋을 듯 하다.

Results

실험 결과는 총 5가지 datasets을 사용하였으며 비교 알고리즘은 위에서 설명한 MICE, MIDA (Auto-encoder), MissForest, Matrix (matrix factorization), expectation maximization (EM)이다. Data imputation의 성능은 임의로 결측치를 생성한 다음 이를 얼마나 잘 복원하는지, root mean squared error (RMSE)를 측정하여 비교할 수 있다. 아래 표는 각 알고리즘을 n번 수행 후 평균$\pm$편차를 나타낸 표이다. 이를 통해 저자들이 GANs가 갖고 있는 고질적인 문제(예: 학습 및 수렴의 어려움, 재현성의 issue)에서 자유롭다는 점을 강조한 모습을 확인할 수 있다.

5가지 datasets에 대해서 GAIN이 가장 높은 성능임을 확인할 수 있다.

다음으로 데이터에 결측치 내포 비율에 따른 imputation 성능(a)과 sample 숫자에 따른 성능(b), feature dimension에 따른 성능(c)을 MissForest, MICE와 비교한 그래프는 하기와 같다.

결측치 비율에 따른 imputation 성능을 확인하면 모든 missing rate에서 GAIN의 성능이 우수함을 알 수 있다(y-axis: RMSE). Sample 숫자에 따른 성능을 확인할 시 확실히 deep learning method인 GAIN과 MIDA는 100개 미만의 samle일 때 성능이 MissForest와 비교하여 좋지 않다. 그러나 GAIN은 MIDA와 달리 그 이상의 sample 수를 보유하고 있으면 가장 좋음을 확인할 수 있다. 마지막으로 feature dimension에 따른 imputation 성능의 경우 모든 측면에서 GAIN이 우월하다.

다양한 실험 결과에서 GAIN의 우수성을 입증하였고 탑 티어 컨퍼런스 ICML에 실린만큼 수리적 증명 또한 탄탄한 논문이라고 생각한다. 다만 현업에서 사용 가능할 정도로 구현이 용이한지, 또한 구현된 모델이 논문에서 입증된 것 처럼 학습 및 수렴의 어려움, 재현성 issue를 극복할 만큼 안정된 결과를 도출할 수 있는지는 해봐야 알 것 같다. 이상으로 포스팅을 마무리 짓는다.

Reference

[1] Rubin, D. B. (1976). Inference and missing data. Biometrika, 63(3), 581-592.

[2] Hair, J. F., Black, W. C., Babin , B. J., Anderson, R. E., & Tatham, R. L. (2006). Multivariate data analysis (6 th ed.). pp. 49 73. Upper Saddle River, NJ: Pearson Educations, Inc.

[3] Stekhoven, D. J., & Bühlmann, P. (2012). MissForest—non-parametric missing value imputation for mixed-type data. Bioinformatics, 28(1), 112-118.

[4] Gondara, L., & Wang, K. (2018, June). Mida: Multiple imputaJㅇㅔ 자Uㄹtion using denoising autoencoders. In Pacific-Asia conference on knowledge discovery and data mining (pp. 260-272). Springer, Cham.

[5] van Buuren, S. (2014). MICE: Multiple Imputation by Chained Equations. R Package Version 2.21.

[6] Honaker, J., King, G., & Blackwell, M. (2011). Amelia II: A program for missing data. Journal of statistical software, 45(1), 1-47.

$\checkmark$ 논문의 concept 및 idea 위주로 정리하여 자세한 수식이나 내용에 오류가 있을 수 있습니다.