Ternary Bradley-Terry Model-Based Decoding for Multi-Class Classification and Its Extensions

Abstract

A multi-class classifier based on the Bradley-Terry model predicts the multi-class label of an input by combining the outputs from multiple binary classifiers, where the combination should be a priori designed as a code word matrix. The code word matrix was originally designed to consist of +1 and −1 codes, and was later extended into deal with ternary code +1,0,−1, that is, allowing 0 codes. This extension has seemed to work effectively but, in fact, contains a problem: a binary classifier forcibly categorizes examples with 0 codes into either +1 or −1, but this forcible decision makes the prediction of the multi-class label obscure. In this article, we propose a Boosting algorithm that deals with three categories by allowing a ‘don’t care’ category corresponding to 0 codes, and present a modified decoding method called a ‘ternary’ Bradley-Terry model. In addition, we propose a couple of fast decoding schemes that reduce the heavy computation by the existing Bradley-Terry model-based decoding.