Multi-class learning using data driven ECOC with deep search and re-balancing

Multi-class learning is an important task in Data Science. One of the ways to achieve good performance on this task is to use Error Correcting Output Codes (ECOC), which is a powerful ensemble learning method that transforms a multi-class problem into a series of binary classifiers which it uses indirectly to learn the original multi-class problem. A crucial component of ECOC is the design of the coding matrix, which determines which binary problems should be combined to achieve multi-class classification. There are two general ways of designing the coding matrix. One is rooted in information theory while the other is data driven. In this work, we investigate the data-driven approach which was previously shown to bear greater promise and propose a better search through the coding-matrix space, keeping in mind the tradeoff between efficiency and effectiveness, as well as considerations about class-imbalance issues in the underlying binary problems. After consolidating our hy! potheses with a study on artificial domains, we propose the Unsupervised Deep Search Algorithm (UDS) coupled with re-sampling, to address both concerns. Our results on real world domains show that our method outperforms traditional multi-class learning methods.