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.

Date Published: 16 March 2015
PDF: 8 pages
Proc. SPIE 9399, Image Processing: Algorithms and Systems XIII, 939902 (16 March 2015); doi: 10.1117/12.2083994

Published in SPIE Proceedings Vol. 9399:
Image Processing: Algorithms and Systems XIII
Karen O. Egiazarian; Sos S. Agaian; Atanas P. Gotchev, Editor(s)