A novel Bayesian logistic discriminant model: An application to face recognition

The linear discriminant analysis (LDA) is a linear classifier which has proven to be powerful and competitive compared to the main state-of-the-art classifiers. However, the LDA algorithm assumes the sample vectors of each class are generated from underlying multivariate normal distributions of common covariance matrix with different means (i.e., homoscedastic data). This assumption has restricted the use of LDA considerably. Over the years, authors have defined several extensions to the basic formulation of LDA. One such method is the heteroscedastic LDA (HLDA) which is proposed to address the heteroscedasticity problem. Another method is the nonparametric DA (NDA) where the normality assumption is relaxed. In this paper, we propose a novel Bayesian logistic discriminant (BLD) model which can address both normality and heteroscedasticity problems. The normality assumption is relaxed by approximating the underlying distribution of each class with a mixture of Gaussians. Hence, the proposed BLD provides more flexibility and better classification performances than the LDA, HLDA and NDA. A subclass and multinomial versions of the BLD are proposed. The posterior distribution of the BLD model is elegantly approximated by a tractable Gaussian form using variational transformation and Jensen's inequality, allowing a straightforward computation of the weights. An extensive comparison of the BLD to the LDA, support vector machine (SVM), HLDA, NDA and subclass discriminant analysis (SDA), performed on artificial and real data sets, has shown the advantages and superiority of our proposed method. In particular, the experiments on face recognition have clearly shown a significant improvement of the proposed BLD over the LDA.     

Decompositional Rule Extraction from Support Vector Machines by Active Learning

Support vector machines (SVMs) are currently state-of-the-art for the classification task and, generally speaking, exhibit good predictive performance due to their ability to model nonlinearities. However, their strength is also their main weakness, as the generated nonlinear models are typically regarded as incomprehensible black-box models. In this paper, we propose a new active learning-based approach (ALBA) to extract comprehensible rules from opaque SVM models. Through rule extraction, some insight is provided into the logics of the SVM model. ALBA extracts rules from the trained SVM model by explicitly making use of key concepts of the SVM: the support vectors, and the observation that these are typically close to the decision boundary. Active learning implies the focus on apparent problem areas, which for rule induction techniques are the regions close to the SVM decision boundary where most of the noise is found. By generating extra data close to these support vectors that are provided with a class label by the trained SVM model, rule induction techniques are better able to discover suitable discrimination rules. This performance increase, both in terms of predictive accuracy as comprehensibility, is confirmed in our experiments where we apply ALBA on several publicly available data sets.     

Robust large margin discriminant tangent analysis for face recognition

Fisher’s Linear Discriminant Analysis (LDA) has been recognized as a powerful technique for face recognition. However, it could be stranded in the non-Gaussian case. Nonparametric discriminant analysis (NDA) is a typical algorithm that extends LDA from Gaussian case to non-Gaussian case. However, NDA suffers from outliers and unbalance problems, which cause a biased estimation of the extra-class scatter information. To address these two problems, we propose a robust large margin discriminant tangent analysis method. A tangent subspace-based algorithm is first proposed to learn a subspace from a set of intra-class and extra-class samples which are distributed in a balanced way on the local manifold patch near each sample point, so that samples from the same class are clustered as close as possible and samples from different classes will be separated far away from the tangent center. Then each subspace is aligned to a global coordinate by tangent alignment. Finally, an outlier detection technique is further proposed to learn a more accurate decision boundary. Extensive experiments on challenging face recognition data set demonstrate the effectiveness and efficiency of the proposed method for face recognition. Compared to other nonparametric methods, the proposed one is more robust to outliers.     

基于隐含狄列克雷分配分类特征扩展的微博广告过滤方法

传统的微博广告过滤方法忽略了微博广告文本的数据稀疏性、语义信息和广告背景领域特征等因素的影响。针对这些问题,提出一种基于隐含狄列克雷分配（LDA）分类特征扩展的广告过滤方法。首先,将微博分为正常微博和广告型微博,并分别构建LDA主题模型预测短文本对应的主题分布,将主题中的词作为特征扩展的基础;其次,在特征扩展时结合文本类别信息提取背景领域特征,以降低其对文本分类的影响;最后,将扩展后的特征向量作为分类器的输入,根据支持向量机（SVM）的分类结果过滤广告。实验结果表明,与现有的仅基于短文本分类的过滤方法相比,其准确率平均提升4个百分点。因此,该方法能有效扩展文本特征,并降低背景领域特征的影响,更适用于数据量较大的微博广告过滤。     

Linear classifier design under heteroscedasticity in Linear Discriminant Analysis

Under normality and homoscedasticity assumptions, Linear Discriminant Analysis (LDA) is known to be optimal in terms of minimising the Bayes error for binary classification. In the heteroscedastic case, LDA is not guaranteed to minimise this error. Assuming heteroscedasticity, we derive a linear classifier, the Gaussian Linear Discriminant (GLD), that directly minimises the Bayes error for binary classification. In addition, we also propose a local neighbourhood search (LNS) algorithm to obtain a more robust classifier if the data is known to have a non-normal distribution. We evaluate the proposed classifiers on two artificial and ten real-world datasets that cut across a wide range of application areas including handwriting recognition, medical diagnosis and remote sensing, and then compare our algorithm against existing LDA approaches and other linear classifiers. The GLD is shown to outperform the original LDA procedure in terms of the classification accuracy under heteroscedasticity. While it compares favourably with other existing heteroscedastic LDA approaches, the GLD requires as much as 60 times lower training time on some datasets. Our comparison with the support vector machine (SVM) also shows that, the GLD, together with the LNS, requires as much as 150 times lower training time to achieve an equivalent classification accuracy on some of the datasets. Thus, our algorithms can provide a cheap and reliable option for classification in a lot of expert systems.     

基于边界向量的支持向量机增量算法

提出了一种新的基于边界向量的增量式支持向量机学习算法。该算法根据支持向量的几何分布特点,采用边界向量预选取方法,从增量样本中选取最有可能成为支持向量的样本形成边界向量集,在其上进行支持向量训练。通过对初始样本是否满足新增样本KKT条件的判断,解决非支持向量向支持向量的转化问题,有效地处理历史数据。针对UCI标准数据集上的仿真实验表明,基于边界向量的增量算法可以有效地减少训练样本数,积累历史信息,具有更高的分类速度和更好的推广能力。     

Linear dimensionality reduction via a heteroscedastic extension of LDA: the Chernoff criterion

We propose an eigenvector-based heteroscedastic linear dimension reduction (LDR) technique for multiclass data. The technique is based on a heteroscedastic two-class technique which utilizes the so-called Chernoff criterion, and successfully extends the well-known linear discriminant analysis (LDA). The latter, which is based on the Fisher criterion, is incapable of dealing with heteroscedastic data in a proper way. For the two-class case, the between-class scatter is generalized so to capture differences in (co)variances. It is shown that the classical notion of between-class scatter can be associated with Euclidean distances between class means. From this viewpoint, the between-class scatter is generalized by employing the Chernoff distance measure, leading to our proposed heteroscedastic measure. Finally, using the results from the two-class case, a multiclass extension of the Chernoff criterion is proposed. This criterion combines separation information present in the class mean as well as the class covariance matrices. Extensive experiments and a comparison with similar dimension reduction techniques are presented.     

Generalized discriminant analysis using a kernel approach

We present a new method that we call generalized discriminant analysis (GDA) to deal with nonlinear discriminant analysis using kernel function operator. The underlying theory is close to the support vector machines (SVM) insofar as the GDA method provides a mapping of the input vectors into high-dimensional feature space. In the transformed space, linear properties make it easy to extend and generalize the classical linear discriminant analysis (LDA) to nonlinear discriminant analysis. The formulation is expressed as an eigenvalue problem resolution. Using a different kernel, one can cover a wide class of nonlinearities. For both simulated data and alternate kernels, we give classification results, as well as the shape of the decision function. The results are confirmed using real data to perform seed classification.     

样例约简支持向量机

支持向量机(support vector machine,SVM)仅利用靠近分类边界的支持向量构造最优分类超平面,但求解SVM需要整个训练集,当训练集的规模较大时,求解SVM需要占用大量的内存空间,寻优速度非常慢。针对这一问题,提出了一种称为样例约简的寻找候选支持向量的方法。在该方法中,支持向量大多靠近分类边界,可利用相容粗糙集技术选出边界域中的样例,作为候选支持向量,然后将选出的样例作为训练集来求解SVM。实验结果证实了该方法的有效性,特别是对大型数据库,该方法能有效减少存储空间和执行时间。     

一种基于支持向量机的视频对象分割新方法

为了实现基于内容的多媒体交互功能,视频对象的提取具有相当重要的作用.支持向量机是最新的学习机,在许多领域得到了成功的应用.提出使用自适应分级的支持向量机分类器解决对象分割跟踪问题,能够克服传统的基于运动的跟踪算法的固有缺陷.通过帧差图像的边缘图和当前帧边缘图进行匹配运算,自动获得用于训练支持向量机的初始视频对象.描述像素属性的特征向量由离散余弦变换系数计算的局部特征和用邻接区域的熵组成的临域特征共同组成.使用分级的支持向量机二叉树来决策前景和背景.实验结果证实了该方法的有效性和鲁棒性.     

KSVM错分及拒分区域的分类信息增益权重分类器

为解决KSVM分类器错分及拒分区域问题,提出了一种新的结合分类信息增益权重的改进KSVM分类器(classifica-tion information gain weight KNN&&SVM,CIGWKSVM)。采用熵期望值度量训练样本的复杂程度、特征集针对分类的不确定性以计算特征集的分类信息增益值,并融合特征分布信息定义训练集样本各条件属性在分类过程中的CIGW权重。在此基础上,设计围绕加CIGW权的欧式距离测度进行聚类处理,并优化选择错分、拒分区K近邻代表点的CIGWKSVM分类器。从理论上比较分析了CIGWKSVM分类器的性能,仿真实验结果表明,CIGWKSVM分类器在保证效率的情况下,分类精度得到了极大的提高。     

Subclass discriminant analysis

Over the years, many discriminant analysis (DA) algorithms have been proposed for the study of high-dimensional data in a large variety of problems. Each of these algorithms is tuned to a specific type of data distribution (that which best models the problem at hand). Unfortunately, in most problems the form of each class pdf is a priori unknown, and the selection of the DA algorithm that best fits our data is done over trial-and-error. Ideally, one would like to have a single formulation which can be used for most distribution types. This can be achieved by approximating the underlying distribution of each class with a mixture of Gaussians. In this approach, the major problem to be addressed is that of determining the optimal number of Gaussians per class, i.e., the number of subclasses. In this paper, two criteria able to find the most convenient division of each class into a set of subclasses are derived. Extensive experimental results are shown using five databases. Comparisons are given against linear discriminant analysis (LDA), direct LDA (DLDA), heteroscedastic LDA (HLDA), nonparametric DA (NDA), and kernel-based LDA (K-LDA). We show that our method is always the best or comparable to the best.     

Enhanced default risk models with SVM+

Default risk models have lately raised a great interest due to the recent world economic crisis. In spite of many advanced techniques that have extensively been proposed, no comprehensive method incorporating a holistic perspective has hitherto been considered. Thus, the existing models for bankruptcy prediction lack the whole coverage of contextual knowledge which may prevent the decision makers such as investors and financial analysts to take the right decisions. Recently, SVM+ provides a formal way to incorporate additional information (not only training data) onto the learning models improving generalization. In financial settings examples of such non-financial (though relevant) information are marketing reports, competitors landscape, economic environment, customers screening, industry trends, etc. By exploiting additional information able to improve classical inductive learning we propose a prediction model where data is naturally separated into several structured groups clustered by the size and annual turnover of the firms. Experimental results in the setting of a heterogeneous data set of French companies demonstrated that the proposed default risk model showed better predictability performance than the baseline SVM and multi-task learning with SVM.     

Variable predictive models—A new multivariate classification approach for pattern recognition applications

Many pattern recognition algorithms applied in literature exhibit data specific performances and are also computationally intense and complex. The data classification problem poses further challenges when different classes cannot be distinguished just based on decision boundaries or conditional discriminating rules. As an alternate to existing methods, inter-relations among the feature vectors can be exploited for distinguishing samples into specific classes. Based on this idea, variable predictive model based class discrimination (VPMCD) method is proposed as a new and alternative classification approach. Analysis is carried out using seven well studied data sets and the performance of VPMCD is benchmarked against well established linear and non-linear classifiers like LDA, kNN, Bayesian networks, CART, ANN and SVM. It is demonstrated that VPMCD is an efficient supervised learning algorithm showing consistent and good performance over these data sets. The new VPMCD method has the potential to be effectively and successfully extended to many pattern recognition applications of recent interest.     

SVM-based feature extraction for face recognition

The primary goal of linear discriminant analysis (LDA) in face feature extraction is to find an effective subspace for identity discrimination. The introduction of kernel trick has extended the LDA to nonlinear decision hypersurface. However, there remained inherent limitations for the nonlinear LDA to deal with physical applications under complex environmental factors. These limitations include the use of a common covariance function among each class, and the limited dimensionality inherent to the definition of the between-class scatter. Since these problems are inherently caused by the definition of the Fisher's criterion itself, they may not be solvable under the conventional LDA framework. This paper proposes to adopt a margin-based between-class scatter and a regularization process to resolve the issue. Essentially, we redesign the between-class scatter matrix based on the SVM margins to facilitate an effective and reliable feature extraction. This is followed by a regularization of the within-class scatter matrix. Extensive empirical experiments are performed to compare the proposed method with several other variants of the LDA method using the FERET, AR, and CMU-PIE databases.     

A decision based one-against-one method for multi-class support vector machine

The support vector machine (SVM) has a high generalisation ability to solve binary classification problems, but its extension to multi-class problems is still an ongoing research issue. Among the existing multi-class SVM methods, the one-against-one method is one of the most suitable methods for practical use. This paper presents a new multi-class SVM method that can reduce the number of hyperplanes of the one-against-one method and thus it returns fewer support vectors. The proposed algorithm works as follows. While producing the boundary of a class, no more hyperplanes are constructed if the discriminating hyperplanes of neighbouring classes happen to separate the rest of the classes. We present a large number of experiments that show that the training time of the proposed method is the least among the existing multi-class SVM methods. The experimental results also show that the testing time of the proposed method is less than that of the one-against-one method because of the reduction of hyperplanes and support vectors. The proposed method can resolve unclassifiable regions and alleviate the over-fitting problem in a much better way than the one-against-one method by reducing the number of hyperplanes. We also present a direct acyclic graph SVM (DAGSVM) based testing methodology that improves the testing time of the DAGSVM method.     

基于三支决策的支持向量机增量学习方法

针对典型的支持向量机增量学习算法对有用信息的丢失和现有支持向量机增量学习算法单纯追求分类器精准性的客观性,将三支决策损失函数的主观性引入支持向量机增量学习算法中,提出了一种基于三支决策的支持向量机增量学习方法.首先采用特征距离与中心距离的比值来计算三支决策中的条件概率;然后把三支决策中的边界域作为边界向量加入到原支持向量和新增样本中一起训练;最后,通过仿真实验证明,该方法不仅充分利用有用信息提高了分类准确性,而且在一定程度上修正了现有支持向量机增量学习算法的客观性,并解决了三支决策中条件概率的计算问题.     

The reachability problem for branching vector addition systems requires doubly-exponential space

Branching vector addition systems are an extension of vector addition systems where new reachable vectors may be obtained by summing two reachable vectors and adding an integral vector from a fixed finite set. The reachability problem for them is shown hard for doubly-exponential space. For an alternative extension of vector addition systems, where reachable vectors may be combined by subtraction, most decision problems of interest are shown undecidable.     

基于证据理论和前景理论的犹豫-直觉模糊语言多准则决策方法

在犹豫模糊语言和直觉模糊语言的基础上,提出一种新的犹豫-直觉模糊语言集,并定义得分函数、精确函数和Hamming距离公式.针对准则值为犹豫-直觉模糊语言的不确定多准则决策问题,构建基于证据理论和前景理论的拓展型VIKOR方法.该决策方法利用证据理论处理自然状态发生的概率未知的不确定状况,应用前景理论刻画人在做决策时的有限理性行为,使决策结果更能反映实际情况.最后,通过算例表明了所提出方法的有效性和可行性.     

An information fusion framework for robust shape tracking

Existing methods for incorporating subspace model constraints in shape tracking use only partial information from the measurements and model distribution. We propose a unified framework for robust shape tracking, optimally fusing heteroscedastic uncertainties or noise from measurement, system dynamics, and a subspace model. The resulting nonorthogonal subspace projection and fusion are natural extensions of the traditional model constraint using orthogonal projection. We present two motion measurement algorithms and introduce alternative solutions for measurement uncertainty estimation. We build shape models offline from training data and exploit information from the ground truth initialization online through a strong model adaptation. Our framework is applied for tracking in echocardiograms where the motion estimation errors are heteroscedastic in nature, each heart has a distinct shape, and the relative motions of epicardial and endocardial borders reveal crucial diagnostic features. The proposed method significantly outperforms the existing shape-space-constrained tracking algorithm. Due to the complete treatment of heteroscedastic uncertainties, the strong model adaptation, and the coupled tracking of double-contours, robust performance is observed even on the most challenging cases.