A Maximum Margin Approach for Semisupervised Ordinal Regression Clustering

Ordinal Regression With Pinball Loss

Ordinal regression (OR) aims to solve multiclass classification problems with ordinal classes. Support vector OR (SVOR) is a typical OR algorithm and has been extensively used in OR problems. In this article, based on the characteristics of OR problems, we propose a novel pinball loss function and present an SVOR method with pinball loss (pin-SVOR). Pin-SVOR is fundamentally different from traditional SVOR with hinge loss. Traditional SVOR employs the hinge loss function, and the classifier is determined by only a few data points near the class boundary, called support vectors, which may lead to a noise sensitive and re-sampling unstable classifier. Distinctively, pin-SVOR employs the pinball loss function. It attaches an extra penalty to correctly classified data that lies inside the class, such that all the training data is involved in deciding the classifier. The data near the middle of each class has a small penalty, and that near the class boundary has a large penalty. Thus, the training data tend to lie near the middle of each class instead of on the class boundary, which leads to scatter minimization in the middle of each class and noise insensitivity. The experimental results show that pin-SVOR has better classification performance than state-of-the-art OR methods.

Maximum Margin Multi-Dimensional Classification

Multi-dimensional classification (MDC) assumes heterogeneous class spaces for each example, where class variables from different class spaces characterize semantics of the example along different dimensions. The heterogeneity of class spaces leads to incomparability of the modeling outputs from different class spaces, which is the major difficulty in designing MDC approaches. In this article, we make a first attempt toward adapting maximum margin techniques for MDC problem and a novel approach named M3MDC is proposed. Specifically, M3MDC maximizes the margins between each pair of class labels with respect to individual class variable while modeling relationship across class variables (as well as class labels within individual class variable) via covariance regularization. The resulting formulation admits convex objective function with nonlinear constraints, which can be solved via alternating optimization with quadratic programming (QP) or closed-form solution in either alternating step. Comparative studies on the most comprehensive real-world MDC datasets to date are conducted and it is shown that M3MDC achieves highly competitive performance against state-of-the-art MDC approaches.

A Unified Entropy-Based Distance Metric for Ordinal-and-Nominal-Attribute Data Clustering

Ordinal data are common in many data mining and machine learning tasks. Compared to nominal data, the possible values (also called categories interchangeably) of an ordinal attribute are naturally ordered. Nevertheless, since the data values are not quantitative, the distance between two categories of an ordinal attribute is generally not well defined, which surely has a serious impact on the result of the quantitative analysis if an inappropriate distance metric is utilized. From the practical perspective, ordinal-and-nominal-attribute categorical data, i.e., categorical data associated with a mixture of nominal and ordinal attributes, is common, but the distance metric for such data has yet to be well explored in the literature. In this paper, within the framework of clustering analysis, we therefore first propose an entropy-based distance metric for ordinal attributes, which exploits the underlying order information among categories of an ordinal attribute for the distance measurement. Then, we generalize this distance metric and propose a unified one accordingly, which is applicable to ordinal-and-nominal-attribute categorical data. Compared with the existing metrics proposed for categorical data, the proposed metric is simple to use and nonparametric. More importantly, it reasonably exploits the underlying order information of ordinal attributes and statistical information of nominal attributes for distance measurement. Extensive experiments show that the proposed metric outperforms the existing counterparts on both the real and benchmark data sets.

Incremental sparse Bayesian ordinal regression

Ordinal Regression (OR) aims to model the ordering information between different data categories, which is a crucial topic in multi-label learning. An important class of approaches to OR models the problem as a linear combination of basis functions that map features to a high-dimensional non-linear space. However, most of the basis function-based algorithms are time consuming. We propose an incremental sparse Bayesian approach to OR tasks and introduce an algorithm to sequentially learn the relevant basis functions in the ordinal scenario. Our method, called Incremental Sparse Bayesian Ordinal Regression (ISBOR), automatically optimizes the hyper-parameters via the type-II maximum likelihood method. By exploiting fast marginal likelihood optimization, ISBOR can avoid big matrix inverses, which is the main bottleneck in applying basis function-based algorithms to OR tasks on large-scale datasets. We show that ISBOR can make accurate predictions with parsimonious basis functions while offering automatic estimates of the prediction uncertainty. Extensive experiments on synthetic and real word datasets demonstrate the efficiency and effectiveness of ISBOR compared to other basis function-based OR approaches.

On Selecting Effective Patterns for Fast Support Vector Regression Training

It is time consuming to train support vector regression (SVR) for large-scale problems even with efficient quadratic programming solvers. This issue is particularly serious when tuning the model's parameters. One way to address the issue is to reduce the problem's scale by selecting a subset of the training set. This paper presents a fast pattern selection method by scanning the training data set to reduce a problem's scale. In particular, we find the k-nearest neighbors (kNNs) in a local region around each pattern's target value, and then determine to retain the pattern according to the distribution of its nearest neighbors. There is a high probability that the pattern locates outside the -tube. Since the kNNs of a pattern are found in a very small region, it is fast to scan the whole training data set. The proposed method deals with the year prediction Million Song Data set, which contains 463 715 patterns, within 10 s on a personal computer with an Intel Core i5-4690 CPU at 3.50 GHz and 8GB DRAM. An additional advantage of the proposed method is that it can predefine the size of the selected subset according to the training set. Comprehensive empirical evaluations demonstrate that the proposed method can significantly eliminate redundant patterns for SVR training with only a slight decrease in performance.

Semi-supervised learning for ordinal Kernel Discriminant Analysis

Ordinal classification considers those classification problems where the labels of the variable to predict follow a given order. Naturally, labelled data is scarce or difficult to obtain in this type of problems because, in many cases, ordinal labels are given by a user or expert (e.g. in recommendation systems). Firstly, this paper develops a new strategy for ordinal classification where both labelled and unlabelled data are used in the model construction step (a scheme which is referred to as semi-supervised learning). More specifically, the ordinal version of kernel discriminant learning is extended for this setting considering the neighbourhood information of unlabelled data, which is proposed to be computed in the feature space induced by the kernel function. Secondly, a new method for semi-supervised kernel learning is devised in the context of ordinal classification, which is combined with our developed classification strategy to optimise the kernel parameters. The experiments conducted compare 6 different approaches for semi-supervised learning in the context of ordinal classification in a battery of 30 datasets, showing (1) the good synergy of the ordinal version of discriminant analysis and the use of unlabelled data and (2) the advantage of computing distances in the feature space induced by the kernel function.