Reference Distance Estimator
Authors: Yanpeng Li
ICLR 2014

Abstract: A theoretical study is presented for a simple linear classifier called reference distance estimator (RDE), which assigns the weight of each feature j as P(r|j)-P(r), where r is a reference feature relevant to the target class y. The analysis shows that if r performs better than random guess in predicting y and is conditionally independent with each feature j, the RDE will have the same classification performance as that from P(y|j)-P(y), a classifier trained with the gold standard y. Since the estimation of P(r|j)-P(r) does not require labeled data, under the assumption above, RDE trained with a large number of unlabeled examples would be close to that trained with infinite labeled examples. For the case the assumption does not hold, we theoretically analyze the factors that influence the closeness of the RDE to the perfect one under the assumption, and present an algorithm to select reference features and combine multiple RDEs from different reference features using both labeled and unlabeled data. The experimental results on 10 text classification tasks show that the semi-supervised learning method improves supervised methods using 5,000 labeled examples and 13 million unlabeled ones, and in many tasks, its performance is even close to a classifier trained with 13 million labeled examples. In addition, the bounds in the theorems provide good estimation of the classification performance and can be useful for new algorithm design.


Peer review:
[Review]:
To Anonymous 7977: 

-  '..just selects features are (on average) as correlated to other features as possible...'

1) You could have missed the I(r) in the formula, an important measure of the discriminating ability of reference feature, which is also obtained from the theory. 

2) When you look at the Step 2 of Section 2.2, you will know it is not a feature selection method, because each RDE (Formula 1) incorporates new information (beyond labeled data) from unlabeled data via P(r|j) and P(r). In other words, this method learns new features from the co-occurrence of existing features in huge unlabeled data. 

3) For example, we have the following Boolean features: f1, f2, f3, f4, f5...  In the instance xi, the features f1, f2, and f3 appear. We select f4 and f5 as reference features. According to the first two steps of Section 2.2, the new representation for xi has two features. The feature values are RDE(xi, f4) and RDE(xi, f5), which are not the simple weighted combination of the old features in labeled data. For example, if f3, a highly indicative feature, does not appear in labeled data but in unlabeled data, it cannot be utilized in supervised learning method but can be learnt from RDE (xi, f4) if f4 is a good reference feature. Also it will be the similar case if f2 is an extremely low-frequency in labeled data. It provides a powerful strategy to overcome the data sparseness problem in machine learning, and also makes it feasible to design high-order features from the combination of existing features, e.g., n-gram features (Figure 1b).   


-	'There is little motivation on using a reference feature --- which is not available in practice'

Can you prove that it is not available in practice? Actually, the assumptions in Theorem 1 are much weaker than those in Naive Bayes and Co-training. Also, most machine learning method aims to find a prediction label as close as the gold standard label. RDE aims to find a good reference feature which is not necessarily the gold standard. In this sense, it should be more practical. 


-	“Moreover, how Theorem 3's condition is generally true?” 

It is a much weaker assumption than that in Theorem 1, and found generally true in the text classification experiments. Due to the page limitation, I am not able to give a detailed analysis in this paper. Theoretical study needs to make assumptions at first even if there could be a gap with the practice such as the IID assumption and conditional independence assumption. At least they can inspire people to move towards the correct direction. 

 Looking forward to your response.