A unified framework for semi-supervised PU learning

Traditional supervised classifiers use only labeled data (features/label pairs) as the training set, while the unlabeled data is used as the testing set. In practice, it is often the case that the labeled data is hard to obtain and the unlabeled data contains the instances that belong to the predefined class but not the labeled data categories. This problem has been widely studied in recent years and the semi-supervised PU learning is an efficient solution to learn from positive and unlabeled examples. Among all the semi-supervised PU learning methods, it is hard to choose just one approach to fit all unlabeled data distribution. In this paper, a new framework is designed to integrate different semi-supervised PU learning algorithms in order to take advantage of existing methods. In essence, we propose an automatic KL-divergence learning method by utilizing the knowledge of unlabeled data distribution. Meanwhile, the experimental results show that (1) data distribution information is very helpful for the semi-supervised PU learning method; (2) the proposed framework can achieve higher precision when compared with the state-of-the-art method.     

Bidirectional Label Propagation over Graphs

Graph-Based label propagation algorithms are popular in the state-of-the-art semi-supervised learning research. The key idea underlying this algorithmic family is to enforce labeling consistency between any two examples with a positive similarity. However, negative similarities or dissimilarities are equivalently valuable in practice. To this end, we simultaneously leverage similarities and dissimilarities in our proposed semi-supervised learning algorithm which we term Bidirectional Label Propagation (BLP). Different from previous label propagation mechanisms that proceed along a single direction of graph edges, the BLP algorithm can propagate labels along not only positive but also negative edge directions. By using an initial neighborhood graph and class assignment constraints inherent among the labeled examples, a set of class-specific graphs are learned, which include both positive and negative edges and thus reveal discriminative cues. Over the learned graphs, a convex propagation criterion is carried out to ensure consistent labelings along the positive edges and inconsistent labelings along the negative edges. Experimental evidence discovered in synthetic and real-world datasets validates excellent performance of the proposed BLP algorithm.     

Learning model order from labeled and unlabeled data for partially supervised classification, with application to word sense disambiguation

Previous partially supervised classification methods can partition unlabeled data into positive examples and negative examples for a given class by learning from positive labeled examples and unlabeled examples, but they cannot further group the negative examples into meaningful clusters even if there are many different classes in the negative examples. Here we proposed an automatic method to obtain a natural partitioning of mixed data (labeled data + unlabeled data) by maximizing a stability criterion defined on classification results from an extended label propagation algorithm over all the possible values of model order (or the number of classes) in mixed data. Our experimental results on benchmark corpora for word sense disambiguation task indicate that this model order identification algorithm with the extended label propagation algorithm as the base classifier outperforms SVM, a one-class partially supervised classification algorithm, and the model order identification algorithm with semi-supervised k-means clustering as the base classifier when labeled data is incomplete.     

基于新型间谍技术的半监督自训练正例无标记学习

正例无标记（PU）学习中的间谍技术极易受噪声和离群点干扰，导致划分的可靠正例不纯，且在初始正例中随机选择间谍样本的机制极易造成划分可靠负例时效率低下，针对这些问题提出一种结合新型间谍技术和半监督自训练的PU学习框架。首先，该框架对初始有标记样本进行聚类并选取离聚类中心较近的样本来取代间谍样本，这些样本能有效地映射出无标记样本的分布结构，从而更好地辅助选取可靠负例；然后对间谍技术划分后的可靠正例进行自训练提纯，采用二次训练的方式取回被误分为正例样本的可靠负例。该框架有效地解决了传统间谍技术在PU学习中分类效率易受数据分布干扰以及随机间谍样本影响的问题。通过9个标准数据集上的仿真实验结果表明，所提框架的平均分类准确率和F-值均高于基本PU学习算法（Basic_PU）、基于间谍技术的PU学习算法（SPY）、基于朴素贝叶斯的自训练PU学习算法（NBST）和基于迭代剪枝的PU学习算法（Pruning）。     

Stream-based semi-supervised learning for recommender systems

To alleviate the problem of data sparsity inherent to recommender systems, we propose a semi-supervised framework for stream-based recommendations. Our framework uses abundant unlabelled information to improve the quality of recommendations. We extend a state-of-the-art matrix factorization algorithm by the ability to add new dimensions to the matrix at runtime and implement two approaches to semi-supervised learning: co-training and self-learning. We introduce a new evaluation protocol including statistical testing and parameter optimization. We then evaluate our framework on five real-world datasets in a stream setting. On all of the datasets our method achieves statistically significant improvements in the quality of recommendations.     

A new method for positive and unlabeled learning with privileged information

Positive and unlabeled learning (PU learning) has been studied to address the situation in which only positive and unlabeled examples are available. Most of the previous work has been devoted to identifying negative examples from the unlabeled data, so that the supervised learning approaches can be applied to build a classifier. However, for the remaining unlabeled data, they either exclude them from the learning phase or force them to belong to a class, and this always limits the performance of PU learning. In addition, previous PU methods assume the training data and the testing data have the same features representations. However, we can always collect the features that the training data have while the test data do not have, these kinds of features are called privileged information. In this paper, we propose a new method, which is based on similarity approach for the problem of positive and unlabeled learning with privileged information (SPUPIL), which consists of two steps. The proposed SPUPIL method first conducts KNN method to generate the similarity weights and then the similarity weights and privileged information are incorporated to the learning model based on Ranking SVM to build a more accurate classifier. We also use the Lagrangian method to transform the original model into its dual problem, and solve it to obtain the classifier. Extensive experiments on the real data sets show that the performance of the SPUPIL is better than the state-of-the-art PU learning methods.

     

One-class remote sensing classification: one-class vs. binary classifiers

Many applications of remote sensing only require the classification of a single land type. This is known as the one-class classification problem and it can be performed using either binary classifiers, by treating all other classes as the negative class, or one-class classifiers which only consider the class of interest. The key difference between these two approaches is in their training data and the amount of effort needed to produce it. Binary classifiers require an exhaustively labelled training data set while one-class classifiers are trained using samples of just the class of interest. Given ample and complete training data, binary classifiers generally outperform one-class classifiers. However, what is not clear is which approach is more accurate when given the same amount of labelled training data. That is, for a fixed labelling effort, is it better to use a binary or one-class classifier. This is the question we consider in this article. We compare several binary classifiers, including backpropagation neural networks, support vector machines, and maximum likelihood classifiers, with two one-class classifiers, one-class SVM, and presence and background learning (PBL), on the problem of one-class classification in high-resolution remote sensing imagery. We show that, given a fixed labelling budget, PBL consistently outperforms the other methods. This advantage stems from the fact that PBL is a positive-unlabelled method in which large amounts of readily available unlabelled data is incorporated into the training phase, allowing the classifier to model the negative class more effectively.     

结合半监督与主动学习的时间序列PU问题分类

目前基于PU问题的时间序列分类常采用半监督学习对未标注数据集[U]中数据进行自动标注并构建分类器,但在这种方法中,边界数据样本类别的自动标注难以保证正确性,从而导致构建分类器的效果不佳。针对以上问题,提出一种采用主动学习对未标注数据集[U]中数据进行人工标注从而构建分类器的方法OAL（Only Active Learning）,基于投票委员会（QBC）对标注数据集构建多个分类器进行投票,以计算未标注数据样本的类别不一致性,并综合考虑数据样本的分布密度,计算数据样本的信息量,作为主动学习的数据选择策略。鉴于人工标注数据量有限,在上述OAL方法的基础上,将主动学习与半监督学习相结合,即在主动学习迭代过程中,将类别一致性高的部分数据样本自动标注,以增加训练数据中标注数据量,保证构建分类器的训练数据量。实验表明了该方法通过部分人工标注,相比半监督学习,能够为PU数据集构建更高准确率的分类器。     

Semi-supervised AUC optimization based on positive-unlabeled learning

Maximizing the area under the receiver operating characteristic curve (AUC) is a standard approach to imbalanced classification. So far, various supervised AUC optimization methods have been developed and they are also extended to semi-supervised scenarios to cope with small sample problems. However, existing semi-supervised AUC optimization methods rely on strong distributional assumptions, which are rarely satisfied in real-world problems. In this paper, we propose a novel semi-supervised AUC optimization method that does not require such restrictive assumptions. We first develop an AUC optimization method based only on positive and unlabeled data and then extend it to semi-supervised learning by combining it with a supervised AUC optimization method. We theoretically prove that, without the restrictive distributional assumptions, unlabeled data contribute to improving the generalization performance in PU and semi-supervised AUC optimization methods. Finally, we demonstrate the practical usefulness of the proposed methods through experiments.     

Wrapper positive Bayesian network classifiers

In the information retrieval framework, there are problems where the goal is to recover objects of a particular class from big sets of unlabelled objects. In some of these problems, only examples from the class we want to recover are available. For such problems, the machine learning community has developed algorithms that are able to learn binary classifiers in the absence of negative examples. Among them, we can find the positive Bayesian network classifiers, algorithms that induce Bayesian network classifiers from positive and unlabelled examples. The main drawback of these algorithms is that they require some previous knowledge about the a priori probability distribution of the class. In this paper, we propose a wrapper approach to tackle the learning when no such information is available, setting this probability at the optimal value in terms of the recovery of positive examples. The evaluation of classifiers in positive unlabelled learning problems is a non-trivial question. We have also worked on this problem, and we have proposed a new guiding metric to be used in the search for the optimal a priori probability of the positive class that we have called the pseudo F. We have empirically tested the proposed metric and the wrapper classifiers on both synthetic and real-life datasets. The results obtained in this empirical comparison show that the wrapper Bayesian network classifiers provide competitive results, particularly when the actual a priori probability of the positive class is high.     

一种基于EM和分类损失的半监督主动DBN学习算法

对于建立动态贝叶斯网络(DBN)分类模型时,带有类标注样本数据集获得困难的问题,提出一种基于EM和分类损失的半监督主动DBN学习算法.半监督学习中的EM算法可以有效利用未标注样本数据来学习DBN分类模型,但是由于迭代过程中易于加入错误的样本分类信息而影响模型的准确性.基于分类损失的主动学习借鉴到EM学习中,可以自主选择有用的未标注样本来请求用户标注,当把这些样本加入训练集后能够最大程度减少模型对未标注样本分类的不确定性.实验表明,该算法能够显著提高DBN学习器的效率和性能,并快速收敛于预定的分类精度.     

A general graph-based semi-supervised learning with novel class discovery

In this paper, we propose a general graph-based semi-supervised learning algorithm. The core idea of our algorithm is to not only achieve the goal of semi-supervised learning, but also to discover the latent novel class in the data, which may be unlabeled by the user. Based on the normalized weights evaluated on data graph, our algorithm is able to output the probabilities of data points belonging to the labeled classes or the novel class. We also give the theoretical interpretations for the algorithm from three viewpoints on graph, i.e., regularization framework, label propagation, and Markov random walks. Experiments on toy examples and several benchmark datasets illustrate the effectiveness of our algorithm.     

Building text classifiers using positive,unlabeled and ‘outdated’ examples

Learning from positive and unlabeled examples (PU learning) is a partially supervised classification that is frequently used in Web and text retrieval system. The merit of PU learning is that it can get good performance with less manual work. Motivated by transfer learning, this paper presents a novel method that transfers the ‘outdated data’ into the process of PU learning. We first propose a way to measure the strength of the features and select the strong features and the weak features according to the strength of the features. Then, we extract the reliable negative examples and the candidate negative examples using the strong and the weak features (Transfer‐1DNF). Finally, we construct a classifier called weighted voting iterative support vector machine (SVM) that is made up of several subclassifiers by applying SVM iteratively, and each subclassifier is assigned a weight in each iteration. We conduct the experiments on two datasets: 20 Newsgroups and Reuters‐21578, and compare our method with three baseline algorithms: positive example‐based learning, weighted voting classifier and SVM. The results show that our proposed method Transfer‐1DNF can extract more reliable negative examples with lower error rates, and our classifier outperforms the baseline algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

基于KL距离的非平衡数据半监督学习算法

在实际应用中,由于各种原因时常无法直接获得已标识反例,导致传统分类方法暂时失灵,因此,基于正例和未标识集的半监督学习顿时成了理论界研究的热点.研究者们提出了不同的解决方法,然而,这些方法都不能有效处理非平衡的分类问题,尤其当隐匿反例非常少或训练集中的实例分布不均匀时.因此,提出了一种基于KL距离的半监督分类算法——LiKL:依次挖掘出未标识集中的最可靠正例和反例,接着使用训练好的增强型分类器来分类.与其他方法相比,不仅提高了分类的查准率和查全率,而且具有鲁棒性.     

Learning classification rules from data

We present ELEM2, a machine learning system that induces classification rules from a set of data based on a heuristic search over a hypothesis space. ELEM2 is distinguished from other rule induction systems in three aspects. First, it uses a new heuristtic function to guide the heuristic search. The function reflects the degree of relevance of an attribute-value pair to a target concept and leads to selection of the most relevant pairs for formulating rules. Second, ELEM2 handles inconsistent training examples by defining an unlearnable region of a concept based on the probability distribution of that concept in the training data. The unlearnable region is used as a stopping criterion for the concept learning process, which resolves conflicts without removing inconsistent examples. Third, ELEM2 employs a new rule quality measure in its post-pruning process to prevent rules from overfitting the data. The rule quality formula measures the extent to which a rule can discriminate between the positive and negative examples of a class. We describe features of ELEM2, its rule induction algorithm and its classification procedure. We report experimental results that compare ELEM2 with C4.5 and CN2 on a number of datasets.     

Spatial-spectral locality preserving projection for hyperspectral image classification with limited training samples

Locality preserving projection (LPP) is a popular unsupervised feature extraction (FE) method. In this paper, the spatial-spectral LPP (SSLPP) method is proposed, which uses both the spectral and spatial information of hyperspectral image (HSI) for FE. The proposed method consists of two parts. In the first part, unlabelled samples are selected in a spatially homogeneous neighbourhood from filtered HSI. In the second part, the transformation matrix is calculated by an LPP-based method and by using the spectral and spatial information of the selected unlabelled samples. Experimental results on Indian Pines (IP), Kennedy Space Center (KSC), and Pavia University (PU) datasets show that the performance of SSLPP is superior to spectral unsupervised, supervised, and semi-supervised FE methods in small and large sample size situations. Moreover, the proposed method outperforms other spatial-spectral semi-supervised FE methods for PU dataset, which has high spatial resolution. For IP and KSC datasets, spectral regularized local discriminant embedding (SSRLDE) has the best performance by using spectral and spatial information of labelled and unlabelled samples, and SSLPP is ranked just behind it. Experiments show that SSLPP is an efficient unsupervised FE method, which does not use training samples as preparation of them is so difficult, costly, and sometimes impractical. SSLPP results are much better than LPP. Also, it decreases the storage and calculation costs using less number of unlabelled samples.     

Learning from positive and unlabeled data: a survey

Learning from positive and unlabeled data or PU learning is the setting where a learner only has access to positive examples and unlabeled data. The assumption is that the unlabeled data can contain both positive and negative examples. This setting has attracted increasing interest within the machine learning literature as this type of data naturally arises in applications such as medical diagnosis and knowledge base completion. This article provides a survey of the current state of the art in PU learning. It proposes seven key research questions that commonly arise in this field and provides a broad overview of how the field has tried to address them.

     

Semi-supervised learning based on nearest neighbor rule and cut edges

In this paper, we propose a novel semi-supervised learning approach based on nearest neighbor rule and cut edges. In the first step of our approach, a relative neighborhood graph based on all training samples is constructed for each unlabeled sample, and the unlabeled samples whose edges are all connected to training samples from the same class are labeled. These newly labeled samples are then added into the training samples. In the second step, standard self-training algorithm using nearest neighbor rule is applied for classification until a predetermined stopping criterion is met. In the third step, a statistical test is applied for label modification, and in the last step, the remaining unlabeled samples are classified using standard nearest neighbor rule. The main advantages of the proposed method are: (1) it reduces the error reinforcement by using relative neighborhood graph for classification in the initial stages of semi-supervised learning; (2) it introduces a label modification mechanism for better classification performance. Experimental results show the effectiveness of the proposed approach.     

Semi-supervised adaptive feature analysis and its application for multimedia understanding

Multimedia understanding for high dimensional data is still a challenging work, due to redundant features, noises and insufficient label information it contains. Graph-based semi-supervised feature learning is an effective approach to address this problem. Nevertheless, Existing graph-based semi-supervised methods usually depend on the pre-constructed Laplacian matrix but rarely modify it in the subsequent classification tasks. In this paper, an adaptive local manifold learning based semi-supervised feature selection is proposed. Compared to the state-of-the-art, the proposed algorithm has two advantages: 1) Adaptive local manifold learning and feature selection are integrated jointly into a single framework, where both the labeled and unlabeled data are utilized. Besides, the correlations between different components are also considered. 2) A group sparsity constraint, i.e. l _2?,?1-norm, is imposed to select the most relevant features. We also apply the proposed algorithm to serval kinds of multimedia understanding applications. Experimental results demonstrate the effectiveness of the proposed algorithm.