PDF《Introducing炉he?》

Introducing?the? g Separability Matrix?for? p y ECOC?coding COC cod g Miguel?Angel?Bautista,?Sergio?Escalera,?Xavier?Baró?&?Oriol?Pujol

1 Outline Outline ? Classification problems and the ECOC framework.

? Motivation. ? The Separability Matrix. ? An application of the Separability Matrix for coding ? An application of the Separability Matrix for coding ECOCs. ? The Conf sion Separabilit E tension Coding ? The Confusion\Separability Extension Coding. ? Experiments and Results. ? Conclusions and Future Work.

2 Introduction to the ECOC framework ? Classification tasks are a well known type of supervised learning problem. The goal is to classify and object among a ? The ECOC framework has proven to be a powerful tool to d l i h l i l l ifi i bl certain number of possible categories. deal with multi\class classification problems. ? This framework is composed of two different steps : di l bl f ? Coding : Decompose a given N\class problem into a set of n binary problems. D di Gi t t l d t i it t ? Decoding : Given a test sample s, determine its category.

3 Introduction to the ECOC framework ? At?the?coding?step?a?decomposition?of?the?N\class?problem? into?n binary?problems?is?build?and?represented?into?a?matrix. ? The columns of the matrix represent the binary problems ? The?columns?of?the?matrix?represent?the?binary?problems. ? The?rows?of?the?matrix?represent?the?codes?of?the?N?classes. + + + +

4 Introduction to the ECOC framework ? At the decoding step a new sample s is classified by comparing the binary responses to the rows of M by means comparing the binary responses to the rows of M by means of a decoding measure . ? Different types of decoding based on the distance used (i.e. yp g ( Hamming Decoding, Euclidean Decoding, etc.)

5 Motivation Motivation ? Standard predefined or random strategies may not be suitable for a given problem. ? Find an optimum coding matrix M for a given problem was proved to be an NP\Complete problem [1]. ? In [2] we show how reduced codes can perform has well d d d i i h f l b f as standard designs with far less number of dichotomizers. ? Those reduced codes can be extended in a problem ? Those reduced codes can be extended in a problem\ dependent way to benefit from error\correcting principles. principles.

6 [1]?On?the?learnability?and?design?of?Error?Correcting?Output?Codes,?K.Crammer?&?Y.?Singer? [2]?Compact?Evolutionary?Design?of?Error?Correcting?Output?Codes,?M.?Bautista,?S.?Escalera,?X.?Baró,?O.?Pujol,?J.?Vitrià?and?P.?Radeva The Separability Matrix ? The?Separability matrix?S contains?the?pairwise?distance? between the codewords in M between?the?codewords in?M. ? With?this?matrix?we?can?analyze?the correction?capability??????of? M?since, ? Standard?ECOC?designs?shown?constant?Separability matrices.

2 2

2 2

0 h5 h4 h3 h2 h1

7 2

2 2

0 2

0 2

2 0

2 2

0 2

2 0

2 2

2 2

2 2 An?application?of?the?Separability Matrix for coding ECOCs Matrix?for?coding?ECOCs ? In?[2]?we?show?how?reduced?codes?can?perform?has?well?as? standard?designs?with?far?less?number?of?dichotomizers. h3 h2 h1 h h1 h3 h2 ? Identify those classes that need an increment of distance in h3 h2 h1 h1 Identify?those?classes?that?need?an?increment?of?distance?in? order?to?benefit?from?error\correcting?principles. h3 h2

2 3

1 3

2 2

0 1

2 0

2 1

1 1

0 8

1 0

1 0

1 2

0 2

1 3

2 2

2 1

3 The Confusion\Separability Extension coding (CSE Coding) ? Use?the?Confusion?matrix?over?a?validation?subset?to?find?the? t f d l most?confused?classes. ? Use?the?Separability?matrix?to?find?the?classes?that?need?at? increment of distance in order to benefit from error\correcting increment?of?distance?in?order?to?benefit?from?error correcting? principles. ? Compute?and?Extension?Matrix?of?a?Binary?Compact?ECOC? matrix?which?is?focused?on?the?classes?that?show?both?high? confusion?and?low?separation. E t d th di t i til i l th f N ? Extend?the?coding?matrix?until?a?maximum?length?of?N dichotomies.