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]:
This paper proposes an interesting approach: identify features which are likely to correlate with a class predictor on a small set and learn to predict the presence of this binary features on a large unlabeled dataset. The paper is however not very clear and its experimental section is far from thorough. 

The paper is dense but misses important points. In particular,
  - what are the modeling assumptions of RDEs?
  - what types of data are likely to succeed?

It could be more fluent and better structured. In particular, the theorems follow each other without much transitions. The reader could be guided more telling what you are going to show and why, on results are going to be linked toward the final goal. I also feel that the results of supervised RDE on their own seems very good, better than SVM and logistic regression. It might be good to invest more work to propose RDEs in a supervised setting with extensive empirical comparison on reference dataset, before then extending them to semi-supervised learning. A paper with a single message is likely to be clearer. 

The quality of its experimental section could greatly be improved. The experiments are performed on a single dataset. Reporting results on standard text classification datasets like RCV1 and other types of data would greatly improve the paper. I feel this is necessary since your results indicate that SVM and logistic regression, which have been state-of-the-art text classification algorithms for many years seem significantly outperformed by the simple supervised RDE. If this is confirmed over benchmark dataset this could be a game changer. However, this single result in non-standard setting is likely to rise doubts. I would also appreciate an analysis of the different step of the algorithm: 
- is the reference feature selection step important (e.g. you could compare with other feature selection strategies like information gain) ?
- are the individual RDE good predictors of their reference features ? is that important or it does not matter for the final task?
- what is the impact of k on the generalization performance?

Also, the baseline algorithm SVM and logistic regression are not trained on the full dataset (this is easily feasible with an efficient SGD implementation like http://leon.bottou.org/projects/sgd). Moreover, I do not understand why no learning curve is reported for semi-supervised RDEs (only the point at 5K labeled samples is reported). Finally, you mention that the hyperparameters of the baselines have been tuned on the test set, which is usually discouraged as it could a very optimistic estimate of the generalization performance. It also raises the question of the methodology used for tuning of k, t and the regularization parameter 'ridge' for your technique. Could you detail your procedure and provide more detail on hyper-parameter sensitivity?