基于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.     

直推式遥感图像场景零样本分类算法

针对遥感图像场景零样本分类算法中的空间类结构不一致以及域偏移问题,提出基于Sammon嵌入和谱聚类方法结合的直推式遥感图像场景零样本分类算法。首先,基于Sammon嵌入算法修正语义特征空间类原型表示,使其与视觉特征空间类原型结构对齐;其次,借助结构迁移方法得到视觉特征空间测试类原型表示;最后,针对域偏移问题,采用谱聚类方法修正视觉特征空间测试类原型,以适应测试类样本分布特点,提高场景零样本分类准确度。在两个遥感场景集（UCM和AID）上分别获得52.89%和55.93%的最高总体分类准确度,均显著优于对比方法。实验结果表明,通过显著降低视觉特征空间和语义特征空间的场景类别结构不一致性,同时减轻了域偏移问题,可实现语义特征空间类结构知识到视觉特征空间的有效迁移,大幅提升遥感场景零样本分类的准确度。     

基于增量学习的直推式支持向量机算法

针对直推式支持向量机在进行大数据量分类时出现精度低、学习速度慢和回溯式学习多的问题,提出了一种基于增量学习的直推式支持向量机分类算法,将增量学习引入直推式支持向量机,使其在训练过程中仅保留有用样本而抛弃无用样本,从而减少学习时间,提高分类速度。实验结果表明,该算法具有较快的分类速度和较高的分类精度。     

A general framework for scalable transductive transfer learning

Transductive transfer learning is one special type of transfer learning problem, in which abundant labeled examples are available in the source domain and only unlabeled examples are available in the target domain. It easily finds applications in spam filtering, microblogging mining, and so on. In this paper, we propose a general framework to solve the problem by mapping the input features in both the source domain and the target domain into a shared latent space and simultaneously minimizing the feature reconstruction loss and prediction loss. We develop one specific example of the framework, namely latent large-margin transductive transfer learning algorithm, and analyze its theoretic bound of classification loss via Rademacher complexity. We also provide a unified view of several popular transfer learning algorithms under our framework. Experiment results on one synthetic dataset and three application datasets demonstrate the advantages of the proposed algorithm over the other state-of-the-art ones.     

Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces

We examine methods for constructing regression ensembles based on a linear program (LP). The ensemble regression function consists of linear combinations of base hypotheses generated by some boosting-type base learning algorithm. Unlike the classification case, for regression the set of possible hypotheses producible by the base learning algorithm may be infinite. We explicitly tackle the issue of how to define and solve ensemble regression when the hypothesis space is infinite. Our approach is based on a semi-infinite linear program that has an infinite number of constraints and a finite number of variables. We show that the regression problem is well posed for infinite hypothesis spaces in both the primal and dual spaces. Most importantly, we prove there exists an optimal solution to the infinite hypothesis space problem consisting of a finite number of hypothesis. We propose two algorithms for solving the infinite and finite hypothesis problems. One uses a column generation simplex-type algorithm and the other adopts an exponential barrier approach. Furthermore, we give sufficient conditions for the base learning algorithm and the hypothesis set to be used for infinite regression ensembles. Computational results show that these methods are extremely promising.     

基于半监督多示例学习的对象图像检索

针对基于对象的图像检索问题,提出一种新的半监督多示例学习(MIL)算法.该算法将图像当作包,分割区域的视觉特征当作包中的示例,按"点密度"最大原则,提取"视觉语义"构造投影空间;然后利用定义的非线性函数将包映射成投影空间中的一个点,以获得图像的"投影特征",并采用粗糙集(RS)方法对其进行属性约简;最后利用直推式支持向量机(TSVM)进行半监督的学习,得到分类器.实验结果表明,该方法有效且性能优于其他方法.     

基于TCM的多分类算法研究

基于算法随机性理论提出的直推式置信机器能够给出预测的可靠性,但其多用于解决两类识别问题。扩展了置信机器,利用了正反类的思想,在识别时比较多个[P]值来确定测试样本的分类,使其很容易一次性应用于多分类识别问题。为对扩展后的模型性能进行评估,将其应用于经典的模式识别-人脸识别。实验结果表明,扩展后的置信机器具有良好的分类性能,当每类训练集样本增加到6个时,识别率已高于96%。     

基于张量表示的直推式多模态视频语义概念检测

提出了一种基于高阶张量表示的视频语义分析与理解框架.在此框架中,视频镜头首先被表示成由视频中所包含的文本、视觉和听觉等多模态数据构成的三阶张量;其次,基于此三阶张量表达及视频的时序关联共生特性设计了一种子空间嵌入降维方法,称为张量镜头;由于直推式学习从已知样本出发能对特定的未知样本进行学习和识别.最后在这个框架中提出了一种基于张量镜头的直推式支持张量机算法,它不仅保持了张量镜头所在的流形空间的本征结构,而且能够将训练集合外数据直接映射到流形子空间,同时充分利用未标记样本改善分类器的学习性能.实验结果表明,该方法能够有效地进行视频镜头的语义概念检测.     

基于间接域适应特征生成的直推式零样本学习方法

近年来，零样本学习备受机器学习和计算机视觉领域的关注.传统的归纳式零样本学习方法通过建立语义与视觉之间的映射关系，实现类别之间的知识迁移.这类方法存在着可见类和未见类之间的映射域漂移（projection domain shift）问题，直推式零样本学习方法通过在训练阶段引入无标定的未见类数据进行域适应，能够有效地缓解上述问题并提升零样本学习精度.然而，通过实验分析发现，这种直接在视觉空间同时进行语义映射建立和域适应的直推式零样本学习方法容易陷入“相互制衡”问题，从而无法充分发挥语义映射和域适应的最佳性能.针对上述问题，提出了一种基于间接域适应特征生成（feature generation with indirect domain adaptation，FG-IDA）的直推式零样本学习方法.该方法通过串行化语义映射和域适应优化过程，使得直推式零样本学习的这两大核心步骤能够在不同特征空间分别进行最佳优化，从而激发其潜能提升零样本识别精度.在4个标准数据集（CUB，AWA1，AWA2，SUN）上对FG-IDA模型进行了评估，实验结果表明，FG-IDA模型不仅展示出了相对其他直推学习方法的优越性，同时还在AWA1，AWA2和CUB数据集上取得了当前最优结果（the state-of-the-art performance）.此外还进行了详尽的消融实验，通过与直接域适应方法进行对比分析，验证了直推式零样本学习中的“相互制衡”问题以及间接域适应思想的先进性.     

Learning context-free grammars using tabular representations

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.     

基于支持向量机的渐进直推式分类学习算法

支持向量机(support vector machine)是近年来在统计学习理论的基础上发展起来的一种新的模式识别方法,在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势.直推式学习(transductive inference)试图根据已知样本对特定的未知样本建立一套进行识别的方法和准则.较之传统的归纳式学习方法而言,直推式学习往往更具普遍性和实际意义.提出了一种基于支持向量机的渐进直推式分类学习算法,在少量有标签样本和大量无标签样本所构成的混合样本训练集上取得了良好的学习效果.