In this paper we propose and test a novel approach, namely Supervised Asymmetric Metric Extraction (SAME), that learns from the supervised metric data and extracts the best single metric from a given set of metrics. It takes up large space to represent the metric-based descriptions, so the approach is specifically crafted to allow for a computationally effective solution. The proposed learning model is scaleindependent and hence rescaling of any metric does not affect the learning. Another advantage of metric extraction is the way of training set annotation which specifically suits verification problems. In this metric extraction approach, we separate intraclass and interclass distances, simplifying the metric extraction problem to linear programming problem which can use optimization techniques effectively. Here, the number of variables needed in the computation remains small and hence it eliminates the need of any soft constraint extension resulting in reduced computational time complexity. The experimental results on offline and online signature data demonstrate that the proposed approach yields better performance and time complexity compared to other metric extraction technique as computational complexity in the proposed approach depends mainly on the calculation of original distances.
Due to the rapid development in electronics, communication and hardware technology, there is a high demand for the design of automated intelligent systems in industrial works, medical imaging, defense, data analytics and biometrics. In machine learning theory and data mining applications, there are increasingly frequent situations when different ways to measure similarity are set on the same objects. Such situations are typical in information retrieval, computer vision, biology, social systems, finance, etc. In many of these domains, similarity engineering is an important way to incorporate expert knowledge and similarity learning is a way to produce a similarity function based on some constraints. The performance of such automated intelligent systems depends upon suitable choice of similarity/dissimilarity function over the input space. Hence there is a increasing need of an extraction mechanism which can learn a best metric for a given set of data from the given set of several metrics. In this context, in this work we have presented metric extraction technique wherein the actual distance learning is performed only on a finite set of supervised training data, whereas the best metric learnt can be applied to the whole population of objects.
The conventional machine learning approaches focus on feature extraction and feature learning, here we have adopted a novel approach of metric extraction from several metrics. The idea here is, even if the individual metrics fail to discriminate classes accurately, their combination will definitely improve the quality of the discrimination. Hence, there is a need for aggregating original multimetric information. In this context, in this work we recognize a notion of metric dimension reduction methods which produces a best metric for a given population from a set of original metrics applied on a small set of labelled samples from the population. The theoretical properties of the problem are provided along with experimental results to exhibit the performance of the proposed approach. The computational complexity will be low as it is mainly due to calculation of original distances.
In automated intelligent systems, specifically biometrics, there are mainly two types of classification problems. First, identification systems that recognizes the subject by its description. Second, verification systems that test whether the given description relates to the given subject. In this paper, we focus on the verification systems, namely biometric systems that verify a person by his/her signatures.
In certain applications like mobile banking, as we need to deal with an intensive stream of verification queries, the update of the system with new information must be simple. This is met by means of specific annotation and classification techniques.
In the state of art literature there are ample number of
distance metric learning approaches applied to machine
learning problems such as computer vision, biometrics,
information retrieval and data analytics [
From the literature we can notice, the conventional machine learning algorithms are based on feature learning and metric learning. The metric learning produces new metric from conventional feature-based object descriptions. Our paper focuses on metric extraction technique which is a kind of dimensionality reduction of metric-based descriptions. The approach does not focus on object features but only takes specific annotations for pairs of objects. The conventional machine learning approaches ensembles the different classifiers at feature level or decision level, thus combining several distances obtained by various metrics in order to have consensus decision, whereas distance extraction technique aggregates original multimetric information giving rise to the best metric. In addition, most of the conventional machine learning approaches use non-negative linear or convex combinations of multiple metrics making it computationally expensive, whereas our approach is computationally efficient as the derived metric is a linear combination of original metric with a scalar value.
We consider a multimetric object space with
pseudo-metrics. Let 1, 2, ..., be the original metrics
on this object space. Let be the new derived metric
which is linear combination of original metrics defined
as follows,
( , ) = 1 1( , ) + 2 2( , ) + ⋯ + ( , )
where 1, 2,..., are the weights. The derived
distance ( , ) can be calculated for any pair ( , )
from the whole population. The combination model is
rather popular in the literature [
It is guaranteed that is a pseudo-metric if the
weights are non-negative [
Let be the finite sample of size , and 1, 2,..., be the objects of the sample. There are two sets of unordered pairs from the sample of training objects: the first set is annotated as must-link pairs, the other as cannot-link pairs. In the conventional case when each training object is annotated with its class label, the mustlink set contains all the pairs of the same class training objects and the cannot-link set contains all the pairs of training objects from different classes.
But for verification problems we propose to use another approach to annotation. In case of signature verification systems, we expect that for each person there will be genuine signatures and skilled forgeries. Accordingly, must-link pairs will represent pairs of genuine signatures, whereas cannot-link pairs will represent pairs of genuine signatures and skilled forgeries. Notice that we do not include the pairs of skilled forgeries to the training at all.
This annotation model is more expressive than labelling individual objects. Moreover, when we will use the extracted (derived) metric for verification we will have several options to prototype selection. One of the crucial advantages is that we will be able to add new people to the verification system without prototyping any forgeries.
One of the important challenges for training an automated signature verification system is the presence of partial knowledge during training. In a realistic scenario, during training we only have access to genuine signatures for the users enrolled to the system. During operations, however, we want the system not only to be able to accept genuine signatures, but also to reject forgeries. This is a challenging task, since during training a classifier has no information to learn what exactly distinguishes a genuine signature and a forgery for the users enrolled in the system. The proposed approach directly addresses this problem as our approach just takes only must link pair between samples of genuine class. We do not need forgery class.
As mentioned above, recognition process must deal with people without known forgeries. For that reason, we utilize the property of scale-independence which we are going to discuss in the following section. Our learning method automatically rescales the derived metric, so we can calculate the distances to genuine prototypes only. Then the distance to the nearest genuine prototype may be used as a score for classification.
We need forgeries for metric extraction, but later we can add a new person to our verification system without any forgery samples.
Conventional performance metrics for verification problems are FAR (false acceptance rate) and FRR (false rejection rate). As our recognition model produces a score, we can use ROC-analysis and calculate EER (equal error rate) which is an informative integral performance metric for the problem in hand.
At recognition phase, all the original metrics to all the prototypes can be calculated in parallel, so the decision can be made quickly.
follows
Let be the set of must-link pairs, let be the set of cannot-link pairs. Here, the reflexive pairs ( , ) are not considered. Let 1, …,
be the actual labels (Genuine or Forgery), then we can set = {( , ) ∣ = = } and
= {( , ) ∣ = and = }, where and are intraclass and interclass pairs respectively. The metric extraction problem
here is to minimize the average intraclass derived distance provided all interclass derived distances are not less than 1 and the weights 1, 2,..., are non-negative. The problem is formalized as
( , ) → min ( , )∈ s.t. ( , ) ≥ 1, for ( , ) ∈ ≥ 0, for ∈ {1, … , } .
. =1
When we use the linear form of the derived metric and change the order of summation in the objective function, we get the conventional linear programming problem
( , ) → min ( , )∈ s.t.
∑=1 ( , ) ≥ 1, for ( , ) ∈ (1) ≥ 0, for ∈
{1, … , }
The formalization makes it possible to consider the
result as metric selection by positive weights. As the
scales are ignored in the approach, so the weight rank has
no semantics. The approach selects relevant metrics. To
get rid of redundant metrics, it is advised to use
unsupervised metric extraction in advance [
Definition 1. A pair of objects from D is conflicting, if for all the original metrics the distance between the objects is zero.
Theorem 1. In the linear programming problem, there is always an admissible solution, unless there are conflicting objects in the sample.
It follows from the theorem that we can do without slack variables customary for SVM. A soft-margin extension is not required at all. Consequently, the number of variables and the size of the optimization problem remains small which is crucial to maintain the computational complexity at low levels.
The important feature of the proposed learning model is its scale-independence. This means that any rescaling of any original metric does not affect the learning. This is unlike many conventional feature-based techniques where changing the scale or units of a feature - e.g. from meters to kilometers – may dramatically. Also, any derived change metric the
results will have a standard scaling for the threshold from the learning model. That is why distances produced by any derived metric may be used as coherent scores for classification. Hence, we do not need samples of forgeries for recognition.
Let us consider automatic online signature verification problem in Biometric domain which is used to prevent identity fraud by verifying the authenticity of signatures. The dataset consists of both genuine and forged signatures. Although, there are plethora of metrics for computer vision applications such as online signature verification, devising an efficient and accurate metric is still a challenging issue. Hence, we are motivated to develop a computationally efficient metric extraction approach that can find linear combinations of the original metrics such that the resulting classification error is reduced compared to that of the original metric.
For the offline signature verification problem, we used Centre of Excellence for Document Analysis and Recognition (CEDAR) dataset. The CEDAR at SUNY Bualo has built the offline signature dataset with 55 signers, a total of 2640 signature samples. 24 genuine signature samples were collected from each signer and later, to obtain the forgeries (skilled), 20 arbitrary chosen signers skilfully forged the signature in the dataset each with 24 samples. Hence for each signer, 24 genuine and 24 skilled forge samples, a total of 48 signature samples were collected. Each signature image was labelled, i.e. it was known which person it had been taken from and whether it is genuine or forged.
In our experiment, we have partitioned each signature
image into eight vertical partitions of equal width. The
morphological
pattern
spectrum-based
features
are
extracted from the signature partitions as explained in
our earlier paper [
For the online signature verification problem, we
used two datasets: SVC2004 [
We used 8 original distance functions. All of them are
known to have been state-of-the-art for the problem
when used individually.
15. DTW for (x; y) – DTWxy [
The Table 1 and Table 2 below show the equal error rates for each of the original metrics and for the learned metric for offline and online signature verification problems respectively.
The Table 1 shows EER for 8 individual original metrics and derived metrics for the offline dataset. EER is averaged over people. As one can expect, none of the original metrics can be good for classification separately, as each one contains only one eighth of information about the signature. At the same time, the combination of these metrics can result in a considerably good discriminative function.
The Table 2 shows EER for 8 individual original
metrics and derived metrics for both online datasets. EER
is averaged over people. MMC [
EMDvy SumMinxy
MMC SAME
The metric extraction phase could be done once for a set of people. Metric combination and verification are extremely quick - in fact, it is negligible in comparison with image or time series transfer and preprocessing.
In this paper we presented a novel metric extraction method which produces best metric for a given population from a linear combination of several original metrics applied on a finite set of supervised training samples. In this approach the intraclass and interclass distances are treated separately resulting in linear optimization problem with reduced computational time complexity. The experimental results on offline signature as well as online Signature verification demonstrated the significant reduction in the error rate compared to the individual metrics. In addition, it is also shown that the metric extraction procedure is computationally effective taking only seconds to calculate coefficients of the linear combination. Acknowledgments. This research is partially supported by Russian Foundation for Basic Research (projects 1601-00196 and 17-01-00917) and Lomonosov Moscow State University (project 5.1.16).