Alternating binary classifier and graph learning from partial labels

Cheng Yang, Gene Cheung, Vladimir Stankovic

Research output: Contribution to conferencePaper

1 Citation (Scopus)

Abstract

Semi-supervised binary classifier learning is a fundamental machine learning task where only partial binary labels are observed, and labels of the remaining data need to be interpolated. Leveraging on the advances of graph signal processing (GSP), recently binary classifier learning is posed as a signal restoration problem regularized using a graph smoothness prior, where the undirected graph consists of a set of vertices and a set of weighted edges connecting vertices with similar features. In this paper, we improve the performance of such a graph-based classifier by simultaneously optimizing the feature weights used in the construction of the similarity graph. Specifically, we start by interpolating missing labels by first formulating a boolean quadratic program with a graph signal smoothness objective, then relax it to a convex semi-definite program, solvable in polynomial time. Next, we optimize the feature weights used for construction of the similarity graph by reusing the smoothness objective but with a convex set constraint for the weight vector. The reposed convex but non-differentiable problem is solved via an iterative proximal gradient descent algorithm. The two steps are solved alternately until convergence. Experimental results show that our alternating classifier / graph learning algorithm outperforms existing graph-based methods and support vector machines with various kernels.

Conference

ConferenceAsia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018
Abbreviated titleAPSIPA ASC 2018
CountryUnited States
CityHonolulu
Period12/11/1815/11/18
Internet address

Fingerprint

Labels
Classifiers
Learning algorithms
Restoration
Support vector machines
Learning systems
Signal processing
Polynomials

Keywords

  • binary classifier learning
  • graph signal processing (GSP)
  • a graph-based classifier

Cite this

Yang, C., Cheung, G., & Stankovic, V. (2018). Alternating binary classifier and graph learning from partial labels. Paper presented at Asia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018, Honolulu, United States. https://doi.org/10.23919/APSIPA.2018.8659448
Yang, Cheng ; Cheung, Gene ; Stankovic, Vladimir. / Alternating binary classifier and graph learning from partial labels. Paper presented at Asia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018, Honolulu, United States.4 p.
@conference{c1ddc16c6da0416187b890178ae8b3cf,
title = "Alternating binary classifier and graph learning from partial labels",
abstract = "Semi-supervised binary classifier learning is a fundamental machine learning task where only partial binary labels are observed, and labels of the remaining data need to be interpolated. Leveraging on the advances of graph signal processing (GSP), recently binary classifier learning is posed as a signal restoration problem regularized using a graph smoothness prior, where the undirected graph consists of a set of vertices and a set of weighted edges connecting vertices with similar features. In this paper, we improve the performance of such a graph-based classifier by simultaneously optimizing the feature weights used in the construction of the similarity graph. Specifically, we start by interpolating missing labels by first formulating a boolean quadratic program with a graph signal smoothness objective, then relax it to a convex semi-definite program, solvable in polynomial time. Next, we optimize the feature weights used for construction of the similarity graph by reusing the smoothness objective but with a convex set constraint for the weight vector. The reposed convex but non-differentiable problem is solved via an iterative proximal gradient descent algorithm. The two steps are solved alternately until convergence. Experimental results show that our alternating classifier / graph learning algorithm outperforms existing graph-based methods and support vector machines with various kernels.",
keywords = "binary classifier learning, graph signal processing (GSP), a graph-based classifier",
author = "Cheng Yang and Gene Cheung and Vladimir Stankovic",
year = "2018",
month = "11",
day = "12",
doi = "10.23919/APSIPA.2018.8659448",
language = "English",
note = "Asia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018, APSIPA ASC 2018 ; Conference date: 12-11-2018 Through 15-11-2018",
url = "https://www.apsipa2018.org/default.asp",

}

Yang, C, Cheung, G & Stankovic, V 2018, 'Alternating binary classifier and graph learning from partial labels' Paper presented at Asia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018, Honolulu, United States, 12/11/18 - 15/11/18, . https://doi.org/10.23919/APSIPA.2018.8659448

Alternating binary classifier and graph learning from partial labels. / Yang, Cheng; Cheung, Gene; Stankovic, Vladimir.

2018. Paper presented at Asia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018, Honolulu, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Alternating binary classifier and graph learning from partial labels

AU - Yang, Cheng

AU - Cheung, Gene

AU - Stankovic, Vladimir

PY - 2018/11/12

Y1 - 2018/11/12

N2 - Semi-supervised binary classifier learning is a fundamental machine learning task where only partial binary labels are observed, and labels of the remaining data need to be interpolated. Leveraging on the advances of graph signal processing (GSP), recently binary classifier learning is posed as a signal restoration problem regularized using a graph smoothness prior, where the undirected graph consists of a set of vertices and a set of weighted edges connecting vertices with similar features. In this paper, we improve the performance of such a graph-based classifier by simultaneously optimizing the feature weights used in the construction of the similarity graph. Specifically, we start by interpolating missing labels by first formulating a boolean quadratic program with a graph signal smoothness objective, then relax it to a convex semi-definite program, solvable in polynomial time. Next, we optimize the feature weights used for construction of the similarity graph by reusing the smoothness objective but with a convex set constraint for the weight vector. The reposed convex but non-differentiable problem is solved via an iterative proximal gradient descent algorithm. The two steps are solved alternately until convergence. Experimental results show that our alternating classifier / graph learning algorithm outperforms existing graph-based methods and support vector machines with various kernels.

AB - Semi-supervised binary classifier learning is a fundamental machine learning task where only partial binary labels are observed, and labels of the remaining data need to be interpolated. Leveraging on the advances of graph signal processing (GSP), recently binary classifier learning is posed as a signal restoration problem regularized using a graph smoothness prior, where the undirected graph consists of a set of vertices and a set of weighted edges connecting vertices with similar features. In this paper, we improve the performance of such a graph-based classifier by simultaneously optimizing the feature weights used in the construction of the similarity graph. Specifically, we start by interpolating missing labels by first formulating a boolean quadratic program with a graph signal smoothness objective, then relax it to a convex semi-definite program, solvable in polynomial time. Next, we optimize the feature weights used for construction of the similarity graph by reusing the smoothness objective but with a convex set constraint for the weight vector. The reposed convex but non-differentiable problem is solved via an iterative proximal gradient descent algorithm. The two steps are solved alternately until convergence. Experimental results show that our alternating classifier / graph learning algorithm outperforms existing graph-based methods and support vector machines with various kernels.

KW - binary classifier learning

KW - graph signal processing (GSP)

KW - a graph-based classifier

U2 - 10.23919/APSIPA.2018.8659448

DO - 10.23919/APSIPA.2018.8659448

M3 - Paper

ER -

Yang C, Cheung G, Stankovic V. Alternating binary classifier and graph learning from partial labels. 2018. Paper presented at Asia-Pacific Signal and Information Processing Association Annual Summit and Conference 2018, Honolulu, United States. https://doi.org/10.23919/APSIPA.2018.8659448