Bekker, Jessa, and Jesse Davis. "Learning from positive and unlabeled data: A survey." Machine Learning 109.4 (2020): 719-760.

작성중인 포스트입니다.

PU learning methods

Two-step techniques

Method	Step 1	Step 2	Step 3
S-EM Liu et al. (2002)	Spy	EM NB	$\Delta E$
Roc-SVM Li and Liu (2003)	Rocchio	Iterative SVM	FNR > 5%
Roc-Clu-SVM Li and Liu (2003)	Rocchio	Iterative SVM	FNR > 5%
PEBL Yu et al. (2002); Yu et al. (2004)	1-DNF	Iterative SVM	Last
A-EM Li and Liu (2005)	Augmented Negatives	EM NB	$\Delta F$
LGN Li et al. (2007)	Single Negative	BN	/
PE_PUC Yu and Li (2007)	PE	(EM) NB	Unspecified
WVC/PSOC Peng et al. (2007)	1-DNF	Iterative SVM	Vote
CR-SVM Li et al. (2010)	Rocchio	SVM	/
MCLS Chaudhari and Shevade (2012)	k-means	Iterative LS-SVM	Last
C-CRNE Liu and Peng (2014)	C-CRNE	TFIPNDF	/
Pulce Ienco and Pensa (2016)	DILCA	DILCA-KNN	/
PGPU HE et al. (2018)	PGPU	Biased SVM	/

• Assumption: separability and smoothness
  - P는 labeled example과 유사하고, N은 labeled example과 많이 다를 것

위 가정을 바탕으로 다음과 같은 방식으로 PU learning을 진행함

1. Identify reliable negative examples. Optionally, additional positive examples can also be generated.
2. Use (semi-)Supervised learning techniques with the positively labeled exampes, reliable negatives, and, optionally, the remaining unlabeled examples.
3. (When applicable) Select the best classifier generated in step 2.

Step 1: Identifying Reliable Negatives (and Positives)

positive example과 negative example을 잘 구분하는 distance를 새롭게 정의하는 연구가 많음. (특히 text classification problem에서). 이 중 내 맘대로 몇개를 소개함

PGPU

probabilistic gap assumption을 이용하여, probabilistic gap이 observed P보다 크거나 같으면 P로 판단, 작으면 N으로 판단하여 labeling

k-means

k-means clustering을 통해 positive examples과 가장 멀리 있는 cluster를 negative samples로 판단함

GPU

labeled set of positives를 이용하여 generative model을 만들고(=positive distribution을 학습하고), generative model이 만들어낸 example 중 probability가 낮은 example을 reliable negative로 판단함

Step 2: (Semi-)Superivsed Learning

Support vector machine (SVM), Naive Bayes (NB), Expectation Maximization on top of Naive Bayes (EM NB) 등 기법을 통해서 classifier를 학습함

Iterative SVM

매 iteration 마다 reliable negative를 추가해가면서 학습해가는 방법

Biased learning

• Biased learning은 unlabeled example을 class label noise가 있는 negative example로 취급하는 방법.
• Assumption: SCAR (Selected completely at random)
• misclassified postive example에 penalty를 주거나 hparams를 튜닝하는 식으로 noise를 고려함

Classification

SVM based

• biased SVM: a standard SVM method that penalizes misclassified positive and negative examples differently (Liu et al. 2003)
• biased SVM + extra penalty on misclassified unlabeled exampels (Ke et al. 2012)
• Weighted unlabeled samples SVM (WUS-SVM) (Liu et al. 2005)

The noisiness of the negative data makes the learning harder

• bagging techniques or least-square SVMs (LS-SVM) (Suykens and Vandewalle 1995)
• Bagging SVM: positive examples and the subset of the negative examples are trained (Mordelet and Vert 2014)
• Robust Ensemble SVM (RESVM): bagging SVM + resampling the positive examples and using a bootstrap approach (Claesen et al. 2015d)
• Biased least squares SVM (BLSSVM): biased version of LS-SVM (Ke et al. 2017)
• MD-BLSSVM: using the Mahalanobis distance instead of the Euclidean distance (Ke et al. 2018)

  Note: bagging SVM, RESVM은 지금 시도하고 있는 연구에 차용할만한 아이디어가 될 듯. must read

RankSVM based

Minimizing a regularized margin-based pairwise loss

• Biased Twin SVMs (Xu et al. 2014)
• nonparallel SVM (NPSVM) (Zhang et al. 2014)
• Laplacian Unit-Hyperplane classifier (LUHC) (Shao et al. 2015)

Weighted logistic regression

• larger weights on correctly classified positive examples (Lee and Lu 2003)

Clustering

• Topic-Sensitive pLSA (probabilistic latent semantic analysis) (Zhou et al. 2010)

Matrix completion

• Binary matrix completion can also be seen as a PU learning problem: the ones in the matrix are the known positives and the zeros are unlabeled (Hsieh et al. 2015)
  • Assumption: complete binary matrix를 generate하는 probability matrix가 존재함

Non-deterministic setting

The complete binary matrix was generated by sampling from the probability matrix.

• Shifted Matrix Completion (ShiftMC): Minimizing an unbiased estimator for the mean square error loss.

Deterministic setting

The complete binary matrix was generated by thresholding the probability matrix. The observed matrix is generated by uniform samping from the complete binary matrix.

• Biased Matrix Completion (BiasMC): penalizing misclassified positives more than misclassified negatives.
• BiasMC for graphs (Natarajan et al. 2015): additional information that neighbors are likely similar

Incorporation of the class prior

Postprocessing

Preprocessing

Method modification

Relational approaches

Other methods

Comparison of PU learning methods