LEARNING FROM POSITIVE AND UNLABELED DATA WITH A SELECTION BIAS
We consider the problem of learning a binary classifier only from positive data and unlabeled data (PU learning). Recent methods of PU learning commonly assume that the labeled positive data are identically distributed as the unlabeled positive data. However, this assumption is unrealistic in many instances of PU learning because it fails to capture the existence of a selection bias in the labeling process. When the data has selection bias, it is difficult to learn the Bayes optimal classifier by conventional methods of PU learning. In this paper, we propose a method to partially identify the classifier. The proposed algorithm learns a scoring function that preserves the order induced by the class posterior under mild assumptions, which can be used as a classifier by setting an appropriate threshold. Through experiments, we show that the method outperforms previous methods for PU learning on various real-world datasets.
The paper proposes an approach to learning from positive and unlabelled data with a sample selection bias. Specifically, it is assumed that the observed positive instances are not necessarily drawn iid from the true positive distribution: rather, there is some bias as to which positive examples are selected. Under an assumption on the selection probability being proportional to the true probability, it is established that one may equally rank instances based on their probability of being labelled. Two algorithms are proposed for this task.
Learning under sample selection bias is an important and interesting problem. It is also arguably more realistic than the classic PU learning setting. The paper proposes a reasonable solution, which builds on some recent advances in the literature on PU learning.
My only critique is that the results are somewhat unsurprising in light of existing work on this topic (the idea of constructing unbiased risk estimators), and also on the topic of learning from label loans. Further, I believe some clarifications would better position the contributions of the paper, both in terms of strengths and limitations. More specifically:
- it seems the problem could be cast as a (interesting) special case of learning from instance dependent label noise. The assumption of the selection (i.e., label flip) probability preserving the ordering of the true class probability has a fair amount of precedent in these works; see, e.g.,
Bylander '97, Learning probabilistically consistent linear threshold functions
Du and Cai '15, Modelling class noise with symmetric and asymmetric distributions
Bootkrajang '16, A generalised label noise model for classification in the presence of annotation errors
It is in light of these works that I do not find Theorem 1 surprising. I note that the sample-selection bias setting could be seen as an interesting special case, but some discussion on the connection seems prudent.
- like in the above works, the proposed approach does not construct an unbiased estimator to the underlying risk. Instead, what is shown in e.g. Theorem 3 is that the Bayes-optimal solution to the risk is sensible. This is of course a minimal desiderata for any learning method, but unlike approaches for the classic PU learning setting, the lack of unbiasedness implies that minimizing over a restricted function class F may result in quite different solutions than if we had access to the true labels. Again, this isn't a limitation unique to this particular work, but I did feel the point could be made a little more explicit.
- also like the above work, there isn't a clear way of estimating P(y = 1). As this is crucial for the final risk estimate, it somewhat restricts the universality of the approach.
- with regards to the two algorithms proposed, both go about estimating the underlying "noisy" class probability (i.e., the probability of an instance being selected for labeling), just with different losses. While the logistic or "LSIF" loss are certainly valid choices, one could use any number of other similar loss (e.g., the exponential loss from class-probability estimation, or the "KLIEP" loss from density ratio estimation). Of course the specific choice of LSIF e.g. can be motivated since it has a closed-form solution, but the basic point is that the two approaches really boil down to changing the underlying loss function. This point could also be clarified.
Other comments:
- I believe the Elkan & Noto paper operates in the censoring rather than case-controlled setting.
- there are a few grammatical issues: e.g.., "Several recent researches", "is to find anomaly data"
- I don't follow how the case-controlled setting is "more general" than the censoring setting, as claimed in Sec 2; do you mean it is more practically realistic?
- it is correct to say in 2.1 that one cannot estimate p(y = 1 | x) from only PU data without assumptions. The next sentence states that a typical assumption that is thus made is SCR. However, this also does not guarantee that we can estimate the probability, since estimating p(y = 1) is also not possible without even further assumptions (see e.g. the mutually contaminated distribution work of Scott et al., 2013).
- in Defn 1, it would be clearer to explicate the dependence of all quantities on r.
- it is interesting that one achieves the BEP with the choice of threshold given by (2). But given that p(y = 1) is in general hard to estimate, it seems one could equally cast the problem of estimating p(y = 1) as the problem of choosing a good threshold? (This of course ignores the fact that we ostensibly need p(y = 1) when constructing the risk estimate.)
- restricting attention to scorers with output in [eps, 1 - eps] is a little strange. I assume this is in order to avoid solutions at +- infinity, which is a well-known problem with the logistic loss. It may be more natural to simply state that you operate with the extended real numbers.
- in the proof of Thm 3, I don't see the need to go through an infinite dimensional Lagrangian route. Since one is optimizing over all possible measurable functions, can one not (under suitable regularity conditions on the distribution & loss) simply compute the minimizer point wise for each x? This optimization would be a one-dimensional problem over predictions the domain [eps, 1 - eps]. The "inner risk" to be optimized (in the sense of Steinwart '06, "How to compare different loss functions and their risks") would I believe be a convex function, admitting exactly the minimizer claimed in the statement of the theorem.
- it is a bit confusing to move from F to \hat{F} as the function class.