Ordinal Regression Techniques Based On Evolutionary Algorithms

A natural order among different categories is frequently involved in many practical applications. For example, one-to-five stars are used to evaluate movies. The evalua-tion with three stars is higher than the evaluation with two stars, while four is lower than five. In contrast to nominal data, this kind of data are called ordinal data. The categories belong to ordinal data can be ranked, but the differences between categories are not exactly defined. For example, the three-star evaluation is typically considered to be better than two-star evaluation. However, it is hard to quantify the distance between them. Ordinal regression is a type of learning problem, which attempts to predict the ranks of ordinal data. It has been applied in a wide variety of practical applications, including sentiment analysis, information retrieval, recommendation system, credit rat-ing, medical research etc.As an important research topic in machine learning and data mining, ordinal regres-sion got more and more attention from researchers. The previous work mainly focused on the supervised ordinal regression problem. However, it is hard to tackle ordinal re-gression when lacking sufficient labeled data. In many practical applications, the labels are often difficult to obtain and costly to calibrate. Nevertheless, unlabeled data exist in abundance and are always easily available. Therefore, the semi-supervised ordinal regression, which considers the labeled data as well as the unlabeled data, has impor-tant research significance and practical value. With this motivation, this dissertation did some research and discussion about semi-supervised ordinal regression.In this dissertation, we propose a semi-supervised ordinal regression technique using weighted kernel Fisher discriminant analysis. This algorithm incorporates the unlabeled data with a weighting scheme, where the weights indicate the degrees of con-tributions to the class distribution by different training instances. By using both labeled and unlabeled data, the class distribution can be estimated more accurately, in order to obtain better projection and thresholds. The projection maps the original data to a one-dimensional space, which makes the adjacent classes to be separated, and the same class to be aggregated. In addition, the rank information can be preserved correctly. The thresholds are used to predict the ranks of new instances. A label propagation method is employed to calculate the weights in this algorithm. However, the estimated weights are not very accurate sometimes, because the label propagation method doesn’t take the order information into account. In order to estimate the data distribution more accurately and improve the performance, we propose an improved technique, called evolutionary semi-supervised ordinal regression. This algorithm tunes the weights of unlabeled data by evolutionary algorithm, and the optimization objective is to make the learner has good learning performance and generalization ability. Due to introducing the unlabeled data and order information at the same time, the optimization problem is non-convex and non-differentiable. Evolutionary algorithm is suitable for this problem, and we use differential evolution in this dissertation. In order to reduce the dimension of the optimization problem, we present a weight updating rule and individual repre-sentation method to evolve the weights indirectly. Through this method, the magnitude of problem dimension drops from the number of instances to the number of ranks. The experimental results on various datasets demonstrate the effectiveness of our two semi-supervised algorithms.