M.Sc Thesis

M.Sc StudentDesyatnikov Ilya
SubjectError Correcting Codes and Performance Bounds for Multi-
Category Classification
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Ron Meir


Pattern Recognition is a task we perform daily, when understanding the words spoken to us, distinguishing a face in a crowd and performing other actions, often unconsciously. More generally it is an act of taking raw data, and deciding to which category it belongs. Technological advances make it possible to automate some of these processes. For instance, speech recognition or automated fingerprint identification would find very useful applications.

We distinguish binary classification from multi-category classification. While the former was widely studied and effective algorithms were developed, the latter is an area under current research. This work focuses on multi-category classification and especially on the Error Correcting Output Codes (ECOC) method. The objective of the work is to derive effective techniques of choosing good coding matrices.

Theoretically, the best way to choose a coding matrix is to minimize the true loss, but this is very complex. A common technique is to explore an error bound, which behaves similarly to the true loss, but is easier to study. This paper presents an introduction and survey of previous known results, as well as new findings on the consistency of convex loss based procedures. We develop a new fully data-dependent bound for multi-category classification, followed by a simplification of the achieved bound. The bound is demonstrated in the particular case of norm based regularization. Two numerical simulations are performed. The first examines the ECOC scheme with different binary algorithms, coding matrices and metrics, while the second tests the effectiveness of the bound minimizing technique.