ИСТИНА

We propose a novel supervised distance metric extraction technique. Given several original metrics and a finite set of labeled objects, the problem is to produce a new metric which better agrees with the labels of the training objects. The problem may be seen as the best single metric extraction from a metric-based description. Feature-based object descriptions are not used even implicitly. Unlike many metric approaches, we treat intraclass and interclass distances differently. The metric extraction problem is reduced to a linear programming problem that makes it possible to use effective optimization techniques. It is proved that an admissible solution always exists, so there is no need to introduce any soft-constraint extension and the number of variables remains small. Thus, the computational complexity depends mainly on the original metric calculation. The method is empirically tested on biometric data where all the original and derived metrics are calculated in real time.