System and method for selecting a training sample from a sample test based on data sample proximity
Described are a system and method for selecting a training sample from a sample set. The method comprises determining proximities between all data samples in a set of the data samples, forming edges between the data samples as a function of the proximities, computing weights for the edges as a function of the proximities, selecting a plurality of the data samples as a function of the weights to form a subset of the data samples, and storing the subset of the data samples.
1. A method, comprising:
determining proximities between all data samples in a set of the data samples;
forming edges between the data samples as a function of the proximities;
computing weights for the edges as a function of the proximities;
selecting a plurality of the data samples as a function of the weights to form a subset of the data samples by solving an optimization problem,
max
Z
=
(
z
1
,
…
,
z
k
)
tr
(
X
(
Z
T
Z
+
λ
1
X
T
LX
+
λ
2
I
)
-
1
X
T
)
for a maximum where X is a matrix whose columns contain feature vectors for all of the data samples, Z is a matrix whose columns contain feature vectors for the subset of data samples, tr( ) denotes a matrix trace operation, I is an identity matrix, λ 1 is a first parameter, λ 2 is a second parameter, and L is a matrix defined as L=D−S, where S is a weight matrix including the weights and D is a diagonal matrix whose i-th entry at a diagonal is an i-th row sum of S; and
storing the subset of the data samples.
2. The method according to claim 1 , further comprising:
generating a feature vector for each of the data samples in the set of data samples; and
determining the proximities as a function of the feature vector for each of the data samples.
3. The method according to claim 1 , wherein the determining includes:
constructing an adjacency graph of all of the data samples.
4. The method according to claim 3 , wherein the constructing includes:
computing a proximity between a first data sample and one or more second data samples using an ε neighborhood methodology.
5. The method according to claim 4 , wherein the computing includes:
forming an edge between the first data sample and a selected one of the one or more second data samples when ∥x i −x j ∥ 2 <ε, wherein ε is a Euclidean norm in R n , x i is a first feature vector for the first data sample and x j is a second feature for the selected one of the one or more data samples.
6. The method according to claim 3 , wherein the constructing includes:
computing a proximity between a first data sample and one or more second data samples using a k-nearest-neighbor methodology.
7. The method according to claim 6 , wherein the constructing includes:
forming an edge between the first data sample and a selected one of the one or more second data samples when the first data sample is among k nearest neighbors of the selected one of the one or more second data samples.
8. The method according to claim 1 , wherein the computing weights includes:
setting a weight of an edge between a first data sample and a second data sample equal to e −(∥xi−xj∥^2)/t , wherein x i is a first feature vector for the first data sample, x j is a second feature for the second data sample and t is a parameter selected from a set of real numbers R.
9. The method according to claim 1 , wherein the computing weights includes:
setting a weight of an edge between a first data sample and a second data sample equal to one.
10. The method according to claim 1 , wherein the first parameter is about 0.001 and the second parameter is about 0.00001.
11. The method according to claim 1 , further comprising:
upon determining the maximum, identifying the subset of data samples associated with the matrix Z.
12. The method according to claim 1 , further comprising:
assigning one or more labels to each of the data samples in the subset.
13. The method according to claim 12 , further comprising:
solving a loss function for a classification model using the one or more labels to obtain a weight vector.
14. The method according to claim 13 , wherein the weight vector includes a weight for each feature identified in the set of data samples.
15. The method according to claim 13 , further comprising:
computing a new label for a new data sample as a function of the weight vector and features associated with the new data sample.
16. The method according to claim 13 , wherein the classification model is a regression function.
17. The method according to claim 13 , wherein the loss function is
E
(
w
)
=
∑
i
=
1
k
(
f
(
z
i
)
-
y
i
)
2
+
λ
2
∑
i
,
j
=
1
m
(
f
(
x
i
)
-
f
(
x
j
)
)
2
S
ij
where:
k is a number of the data samples in the subset;
z i (i=l . . . k) is an i-th data sample of the subset;
y i (i=l . . . k) is a label of z i ;
x i (i=l . . . m) is an i-th data sample (feature vector);
x j (j=l . . . m) is a j-th data sample (feature vector);
ƒ is a regression function;
λ is a regularization parameter; and
S ij is a weight matrix for an edge between data samples i,j.
18. The method according to claim 1 , wherein the data samples are one of webpages, query pairs, biometric data, face images, weather data, stock data and environmental data.