基于k均值聚类的直推式支持向量机学习算法

针对直推式支持向量机（TSVM）学习模型求解难度大的问题,提出了一种基于k均值聚类的直推式支持向量机学习算法——TSVMKMC。该算法利用k均值聚类算法,将无标签样本分为若干簇,对每一簇样本赋予相同的类别标签,将无标签样本和有标签样本合并进行直推式学习。由于TSVMKMC算法有效地降低了状态空间的规模,因此运行速度较传统算法有了很大的提高。实验结果表明,TSVMSC算法能够以较快的速度达到较高的分类准确率。     

Soft Constraint Harmonic Energy Minimization for Transductive Learning and its Two Interpretations

Using the labeled and unlabeled data to enhance the performance of classification is the core idea of transductive learning. It has recently attracted much interest of researchers on this topic. In this paper, we extend the harmonic energy minimization algorithm and propose a novel transductive learning algorithm on graph with soft label and soft constraint. Relaxing the label to real value makes the transductive problem easy to solve, while softening the hard constraint for the labeled data makes it tolerable to the noise in labeling. We discuss two cases for our algorithm and derive exactly the same form of solution. More importantly, such form of solution can be interpreted from the view of label propagation and a special random walks on graph, which make the algorithm intuitively reasonable. We also discuss several related issues of the proposed algorithm. Experiments on toy examples and real world classification problems demonstrate the effectiveness of our algorithm.     

一种基于转导的预测算法及其在软件性能测试中的应用

通过对转导推理理论的分析,设计了一种基于转导推理的预测算法。软件系统性能测试中的某些领域,如基于有限的历史测试数据,在某个特定条件下对系统响应时间的测试和分析,与转导推理具有相同的应用前提条件和应用目标,即利用小样本测试数据集,计算感兴趣处的结果。基于这一点,将所设计的算法应用在实际系统中的软件性能测试模块,并取得了一定的价值。     

Query by transduction

There has been recently a growing interest in the use of transductive inference for learning. We expand here the scope of transductive inference to active learning in a stream-based setting. Towards that end this paper proposes Query-by-Transduction (QBT) as a novel active learning algorithm. QBT queries the label of an example based on the p-values obtained using transduction. We show that QBT is closely related to Query-by-Committee (QBC) using relations between transduction, Bayesian statistical testing, Kullback-Leibler divergence, and Shannon information. The feasibility and utility of QBT is shown on both binary and multi-class classification tasks using SVM as the choice classifier. Our experimental results show that QBT compares favorably, in terms of mean generalization, against random sampling, committee-based active learning, margin-based active learning, and QBC in the stream-based setting.     

核聚类启发式转导SVM

传统转导支持向量机有效地利用了未标记样本,具有较高的分类准确率,但是计算复杂度较高。针对该不足,论文提出了一种基于核聚类的启发式转导支持向量机学习算法。首先将未标记样本利用核聚类算法进行划分,然后对划分后的每一簇样本标记为同一类别,最后根据传统的转导支持向量机算法进行新样本集合上的分类学习。所提方法通过对核聚类后同一簇未标记样本赋予同样的类别,极大地降低了传统转导支持向量机算法的计算复杂度。在MNIST手写阿拉伯数字识别数据集上的实验表明,所提算法较好地保持了传统转导支持向量机分类精度高的优势。     

Interactive 1-bit feedback segmentation using transductive inference

This paper presents an effective algorithm, interactive 1-bit feedback segmentation using transductive inference (FSTI), that interactively reasons out image segmentation. In each round of interaction, FSTI queries the user one superpixel for acquiring 1-bit user feedback to define the label of that superpixel. The labeled superpixels collected so far are used to refine the segmentation and generate the next query. The key insight is treating the interactive segmentation as a transductive inference problem, and then suppressing the unnecessary queries via an intrinsic-graph-structure derived from transductive inference. The experiments conducted on five publicly available datasets show that selecting query superpixels concerning the intrinsic-graph-structure is helpful to improve the segmentation accuracy. In addition, an efficient boundary refinement is presented to improve segmentation quality by revising the misaligned boundaries of superpixels. The proposed FSTI algorithm provides a superior solution to the interactive image segmentation problem is evident.     

Tensor-Based Transductive Learning for Multimodality Video Semantic Concept Detection

Interaction and integration of multimodality media types such as visual, audio, and textual data in video are the essence of video semantic analysis. Contextual information propagation is useful for both intra- and inter-shot correlations. However, the traditional concatenated vector representation of videos weakens the power of the propagation and compensation among the multiple modalities. In this paper, we introduce a higher-order tensor framework for video analysis. We represent image frame, audio, and text in video shots as data points by the 3rd-order tensor. Then we propose a novel dimension reduction algorithm which explicitly considers the manifold structure of the tensor space from contextual temporal associated cooccurring multimodal media data. Our algorithm inherently preserves the intrinsic structure of the sub- manifold where tensorshots are sampled and is also able to map out-of-sample data points directly. We propose a new transductive support tensor machines algorithm to train effective classifier using large amount of unlabeled data together with the labeled data. Experiment results on TREVID 2005 data set show that our method improves the performance of video semantic concept detection.     

A relational approach to probabilistic classification in a transductive setting

Transduction is an inference mechanism adopted from several classification algorithms capable of exploiting both labeled and unlabeled data and making the prediction for the given set of unlabeled data only. Several transductive learning methods have been proposed in the literature to learn transductive classifiers from examples represented as rows of a classical double-entry table (or relational table). In this work we consider the case of examples represented as a set of multiple tables of a relational database and we propose a new relational classification algorithm, named TRANSC, that works in a transductive setting and employs a probabilistic approach to classification. Knowledge on the data model, i.e., foreign keys, is used to guide the search process. The transductive learning strategy iterates on a k-NN based re-classification of labeled and unlabeled examples, in order to identify borderline examples, and uses the relational probabilistic classifier Mr-SBC to bootstrap the transductive algorithm. Experimental results confirm that TRANSC outperforms its inductive counterpart (Mr-SBC).     

Active Learning for Transductive Support Vector Machines with Applications to Text Classification

This paper presents a novel active learning approach for transductive support vector machines with applications to text classification. The concept of the centroid of the support vectors is proposed so that the selective sampling based on measuring the distance from the unlabeled samples to the centroid is feasible and simple to compute. With additional hypothesis, active learning offers better performance with comparison to regular inductive SVMs and transductive SVMs with random sampling,and it is even competitive to transductive SVMs on all available training data. Experimental results prove that our approach is efficient and easy to implement.     

A bi-fuzzy progressive transductive support vector machine(BFPTSVM) algorithm

Transductive support vector machine (TSVM) is a well-known algorithm that realizes transductive learning in the field of support vector classification. This paper constructs a bi-fuzzy progressive transductive support vector machine (BFPTSVM) algorithm by combining the proposed notation of bi-fuzzy memberships for the temporary labeled sample appeared in progressive learning process and the sample-pruning strategy, which decreases the computation complexity and store memory of algorithm. Simulation experiments show that the BFPTSVM algorithm derives better classification performance and converges rapidly with better stability compared to the other learning algorithms.