Ordinal regression based on data relationship

Ordinal regression is a supervised learning problem which aims to classify instances into ordinal categories. It is different from multi-class classification because there is an ordinal relationship between the categories. Moreover, it is different from metric regression because the target values to...

Full description

Saved in:
Bibliographic Details
Main Author: Liu, Yanzhu
Other Authors: Kong Wai-Kin Adams
Format: Theses and Dissertations
Language:English
Published: 2019
Subjects:
Online Access:https://hdl.handle.net/10356/105479
http://hdl.handle.net/10220/47844
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-105479
record_format dspace
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering
spellingShingle DRNTU::Engineering::Computer science and engineering
Liu, Yanzhu
Ordinal regression based on data relationship
description Ordinal regression is a supervised learning problem which aims to classify instances into ordinal categories. It is different from multi-class classification because there is an ordinal relationship between the categories. Moreover, it is different from metric regression because the target values to be predicted are discrete and the distances between different categories are not defined. Ordinal regression is an active research area because of numerous governmental, commercial and scientific applications, such as quality assessment, disease grading, credit rating, and risk stratification. The main challenge of ordinal regression is to model the ordinal information carried by the labels. Traditionally, there are two angles to tackle the ordinal regression problem: from metric regression perspective and classification perspective. However, most of existing works under both above categories are pointwise methods, in which the relationship between pairs or lists of data points is not explored sufficiently. Furthermore, learning models, especially deep neural network based models, on small datasets is challenging, but many real-world ordinal regression problems are in fact small data problems. The aim of this research is to propose ordinal regression algorithms by exploring data relationship and give consideration to suitability for small datasets and scalability for large datasets. This thesis proposes four approaches for ordinal regression problems based on data relationship. The first approach is a pairwise ordinal regression approach for small datasets. In the training phase, the labeled instances are paired up to train a binary classifier, and the relationship between two data points in each pair is represented by a pairwise kernel. In the testing phase, a decoder algorithm is developed to recover the ordinal information from the binary outputs. By pairing up the training points, the size of the training dataset is squared, which alleviates the lack of training points in small datasets. A proof is presented that if the pairwise kernel fulfills certain properties, the time complexity solving the QP problem can be reduced from O(n^4) to O(n^2) without any loss of accuracy, where n is the number of training points. Motivated by the study of the pairwise relationship, the second approach extends the data relationship representation from pairs to triplets based on deep neural networks. The intuition is to predict rank labels by answering the question: “Is the rank of an input greater than k −1 and smaller than k + 1?”. Therefore, the proposed approach transforms the ordinal regression problem to binary classification problems answering above question and uses triplets with instances from different categories to train deep neural networks such that high-level features describing their ordinal relationship can be extracted automatically. In the testing phase, triplets are formed by a testing instance and other instances with known ranks. A decoder is designed to estimate the rank of the testing instance based on the outputs of the network. Because of the data argumentation by permutation, deep learning can work for ordinal regression even on small datasets. The third proposed approach is a constrained deep neural network for ordinal regression, which aims to automatically extract high-level features for representing intraclass information and interclass ordinal relationship simultaneously. A constrained optimization formulation is proposed for the ordinal regression problem which minimizes the negative loglikelihood for multiple categories constrained by the order between instances. Mathematically, it is equivalent to an unconstrained formulation with a pairwise regularizer. An implementation based on a convolutional neural network framework is proposed to solve the problem such that high-level features can be extracted automatically, and the optimal solution can be learned through the traditional back-propagation method. The proposed pairwise constraints as a regularizer make the algorithm work even on small datasets, and a proposed efficient implementation makes it be scalable for large datasets. Furthermore, an ordinal network architecture is proposed for ordinal regression. The proposed approach embeds the ordinal relationship into the edges between nodes of the same layers in the neural network. Existing deep learning based ordinal regression approaches are implemented by traditional architectures for classification, in which no edges exist between nodes of the same layers. The proposed architecture performs as a latent function mapping the instances to a real line, and the target categories are the intervals on this line which are decided by multiple boundaries. Most significant benefit is that the ordinal network is able to predict the rank labels directly by the outputs of the network without explicit predictions of the multiple boundaries. This research breaks the limits of traditional ordinal regression approaches, and shows the effective and efficient performance of the proposed approaches comparing with the state-of-the-art ordinal regression approaches.
author2 Kong Wai-Kin Adams
author_facet Kong Wai-Kin Adams
Liu, Yanzhu
format Theses and Dissertations
author Liu, Yanzhu
author_sort Liu, Yanzhu
title Ordinal regression based on data relationship
title_short Ordinal regression based on data relationship
title_full Ordinal regression based on data relationship
title_fullStr Ordinal regression based on data relationship
title_full_unstemmed Ordinal regression based on data relationship
title_sort ordinal regression based on data relationship
publishDate 2019
url https://hdl.handle.net/10356/105479
http://hdl.handle.net/10220/47844
_version_ 1681057585092886528
spelling sg-ntu-dr.10356-1054792020-06-25T05:39:06Z Ordinal regression based on data relationship Liu, Yanzhu Kong Wai-Kin Adams School of Computer Science and Engineering DRNTU::Engineering::Computer science and engineering Ordinal regression is a supervised learning problem which aims to classify instances into ordinal categories. It is different from multi-class classification because there is an ordinal relationship between the categories. Moreover, it is different from metric regression because the target values to be predicted are discrete and the distances between different categories are not defined. Ordinal regression is an active research area because of numerous governmental, commercial and scientific applications, such as quality assessment, disease grading, credit rating, and risk stratification. The main challenge of ordinal regression is to model the ordinal information carried by the labels. Traditionally, there are two angles to tackle the ordinal regression problem: from metric regression perspective and classification perspective. However, most of existing works under both above categories are pointwise methods, in which the relationship between pairs or lists of data points is not explored sufficiently. Furthermore, learning models, especially deep neural network based models, on small datasets is challenging, but many real-world ordinal regression problems are in fact small data problems. The aim of this research is to propose ordinal regression algorithms by exploring data relationship and give consideration to suitability for small datasets and scalability for large datasets. This thesis proposes four approaches for ordinal regression problems based on data relationship. The first approach is a pairwise ordinal regression approach for small datasets. In the training phase, the labeled instances are paired up to train a binary classifier, and the relationship between two data points in each pair is represented by a pairwise kernel. In the testing phase, a decoder algorithm is developed to recover the ordinal information from the binary outputs. By pairing up the training points, the size of the training dataset is squared, which alleviates the lack of training points in small datasets. A proof is presented that if the pairwise kernel fulfills certain properties, the time complexity solving the QP problem can be reduced from O(n^4) to O(n^2) without any loss of accuracy, where n is the number of training points. Motivated by the study of the pairwise relationship, the second approach extends the data relationship representation from pairs to triplets based on deep neural networks. The intuition is to predict rank labels by answering the question: “Is the rank of an input greater than k −1 and smaller than k + 1?”. Therefore, the proposed approach transforms the ordinal regression problem to binary classification problems answering above question and uses triplets with instances from different categories to train deep neural networks such that high-level features describing their ordinal relationship can be extracted automatically. In the testing phase, triplets are formed by a testing instance and other instances with known ranks. A decoder is designed to estimate the rank of the testing instance based on the outputs of the network. Because of the data argumentation by permutation, deep learning can work for ordinal regression even on small datasets. The third proposed approach is a constrained deep neural network for ordinal regression, which aims to automatically extract high-level features for representing intraclass information and interclass ordinal relationship simultaneously. A constrained optimization formulation is proposed for the ordinal regression problem which minimizes the negative loglikelihood for multiple categories constrained by the order between instances. Mathematically, it is equivalent to an unconstrained formulation with a pairwise regularizer. An implementation based on a convolutional neural network framework is proposed to solve the problem such that high-level features can be extracted automatically, and the optimal solution can be learned through the traditional back-propagation method. The proposed pairwise constraints as a regularizer make the algorithm work even on small datasets, and a proposed efficient implementation makes it be scalable for large datasets. Furthermore, an ordinal network architecture is proposed for ordinal regression. The proposed approach embeds the ordinal relationship into the edges between nodes of the same layers in the neural network. Existing deep learning based ordinal regression approaches are implemented by traditional architectures for classification, in which no edges exist between nodes of the same layers. The proposed architecture performs as a latent function mapping the instances to a real line, and the target categories are the intervals on this line which are decided by multiple boundaries. Most significant benefit is that the ordinal network is able to predict the rank labels directly by the outputs of the network without explicit predictions of the multiple boundaries. This research breaks the limits of traditional ordinal regression approaches, and shows the effective and efficient performance of the proposed approaches comparing with the state-of-the-art ordinal regression approaches. Doctor of Philosophy 2019-03-19T01:44:23Z 2019-12-06T21:52:08Z 2019-03-19T01:44:23Z 2019-12-06T21:52:08Z 2019 Thesis Liu, Y. (2019). Ordinal regression based on data relationship. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/105479 http://hdl.handle.net/10220/47844 10.32657/10220/47844 en 143 p. application/pdf