Links between binary classification and the assignment problem in ordered hypothesis machines

Reid Porter; Beate G. Zimmer

doi:10.1117/12.2083994

16 March 2015 Links between binary classification and the assignment problem in ordered hypothesis machines

Reid Porter, Beate G. Zimmer

Proceedings Volume 9399, Image Processing: Algorithms and Systems XIII; 939902 (2015) https://doi.org/10.1117/12.2083994
Event: SPIE/IS&T Electronic Imaging, 2015, San Francisco, California, United States

Abstract

Ordered Hypothesis Machines (OHM) are large margin classifiers that belong to the class of Generalized Stack Filters which were originally developed for non-linear signal processing. In previous work we showed how OHM classifiers are equivalent to a variation of Nearest Neighbor classifiers, with the advantage that training involves minimizing a loss function which includes a regularization parameter that controls class complexity. In this paper we report a new connection between OHM training and the Linear Assignment problem, a combinatorial optimization problem that can be solved efficiently with (amongst others) the Hungarian algorithm. Specifically, for balanced classes, and particular choices of parameters, OHM training is the dual of the Assignment problem. The duality sheds new light on the OHM training problem, opens the door to new training methods and suggests several new directions for research.

Citation Download Citation

Reid Porter and Beate G. Zimmer "Links between binary classification and the assignment problem in ordered hypothesis machines", Proc. SPIE 9399, Image Processing: Algorithms and Systems XIII, 939902 (16 March 2015); https://doi.org/10.1117/12.2083994

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available