Method, Apparatus and Computer Program Product for Similarity Determination in Multimedia Content
In an example embodiment, a method, apparatus and computer program product are provided. The method includes determining an upper bound on a probability of error associated with a mapping of a data into binary codes. The mapping is performed based on a plurality of hash functions. The method further includes selecting a set of hash functions from among the plurality of hash functions associated with a minimization of the upper bound on the probability of error.
1 . A method comprising:
determining an upper bound on a probability of error associated with a mapping of a data into binary codes, the mapping being performed based on a plurality of hash functions; and
selecting a set of hash functions from among the plurality of hash functions associated with a minimization of the upper bound on the probability of error.
2 . The method as claimed in claim 1 , wherein the data comprises a multi-dimensional data and capable of being classified into a class of a plurality of classes.
3 . The method as claimed in claim 1 , further comprising recursively partitioning a space associated with the data into a plurality of subsets based on the plurality of hash functions, the plurality of subsets being associated with a corresponding binary code and a corresponding hash function.
4 . The method as claimed in claim 2 , wherein the upper bound being determined based on a Jensen Shanon Divergence (JSD) measure between probability distributions associated with the plurality of classes for the plurality of hash functions.
5 . The method as claimed in claim 4 , wherein the JSD measure being related with the probability of error based on following equation:
P
(
e
)
≤
1
2
(
H
(
π
)
-
J
S
D
π
(
p
1
…
,
p
M
)
)
where, H(π) represents an entropy of priori probabilities associated with the plurality of classes.
6 . The method as claimed in claim 5 , wherein selection of the set of hash functions based on the JSD measure being configured to minimize the probability of error associated with the mapping.
7 . The method as claimed in claim 4 , further comprising:
applying a set of randomly generated candidate linear projections to the data to generate a candidate binary matrix, the randomly generated candidate linear projections comprises the plurality of hash functions;
rearranging the data to partition the candidate binary matrix based on the plurality of classes for generating a set of candidate vectors;
determining a set of binary vectors associated with the data, each binary vector of the set of binary vectors being associated with a corresponding class and a corresponding binary code;
determining, for a set of binary codes comprising the corresponding binary code associated with the each binary vector, a set of probability distributions associated with the plurality of classes based on the set of candidate vectors and the set of binary vectors;
computing the JSD measure for the plurality of hash functions based on the set of probability distributions associated with the plurality of classes; and
determining the set of hash functions from among the plurality of hash functions configured to maximize the JSD measure.
8 . The method as claimed in claim 7 , further comprising updating the candidate binary matrix by appending a binary matrix associated with a binary code learning mechanism to the candidate binary matrix.
9 . An apparatus comprising:
at least one processor; and
at least one memory comprising computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:
determine an upper bound on a probability of error associated with a mapping of a data into binary codes, the mapping being performed based on a plurality of hash functions; and
select a set of hash functions from among the plurality of hash functions associated with a minimization of the upper bound on the probability of error.
10 . The apparatus as claimed in claim 9 , wherein the data comprises a multi-dimensional data and capable of being classified into a class of a plurality of classes.
11 . The apparatus as claimed in claim 9 , wherein the apparatus is further caused, at least in part to:
recursively partition a space associated with the data into a plurality of subsets based on the plurality of hash functions, the plurality of subsets being associated with a corresponding binary code and a corresponding hash function.
12 . The apparatus as claimed in claim 10 , wherein the apparatus is further caused, at least in part to determine the upper bound based on a Jensen Shanon Divergence (JSD) measure between probability distributions associated with the plurality of classes for the plurality of hash functions.
13 . The apparatus as claimed in claim 12 , wherein the JSD measure being related with the probability of error based on following equation:
P
(
e
)
≤
1
2
(
H
(
π
)
-
J
S
D
π
(
p
1
…
,
p
M
)
)
H(π) represents an entropy of priori probabilities associated with the plurality of classes.
14 . The apparatus as claimed in claim 13 , wherein the apparatus is further caused, at least in part to perform selection of the set of hash functions based on the JSD measure for minimizing the probability of error associated with the mapping.
15 . The apparatus as claimed in claim 12 , wherein the apparatus is further caused, at least in part to:
apply a set of randomly generated candidate linear projections to the data to generate a candidate binary matrix, the randomly generated candidate linear projections comprises the plurality of hash functions;
rearrange the data to partition the candidate binary matrix based on the plurality of classes for generating a set of candidate vectors;
determine a set of binary vectors associated with the data, each binary vector of the set of binary vectors being associated with a corresponding class and a corresponding binary code;
determine, for a set of binary codes comprising the corresponding binary code associated with the each binary vector, a set of probability distributions associated with the plurality of classes based on the set of candidate vectors and the set of binary vectors;
compute the JSD measure for the plurality of hash functions based on the set of probability distributions associated with the plurality of classes; and
determine the set of hash functions from among the plurality of hash functions configured to maximize the JSD measure.
16 . The apparatus as claimed in claim 15 , wherein the apparatus is further caused, at least in part to update the candidate binary matrix by appending a binary matrix associated with a binary code learning mechanism to the candidate binary matrix.
17 . A computer program product comprising at least one computer-readable storage medium, the computer-readable storage medium comprising a set of instructions, which, when executed by one or more processors, cause an apparatus to at least perform:
determine an upper bound on a probability of error associated with a mapping of a data into binary codes, the mapping being performed based on a plurality of hash functions; and
select a set of hash functions from among the plurality of hash functions associated with a minimization of the upper bound on the probability of error.
18 . The computer program product as claimed in claim 17 , wherein the data comprises a multi-dimensional data and capable of being classified into a class of a plurality of classes.
19 . The computer program product as claimed in claim 17 , wherein the apparatus is further caused, at least in part to:
recursively partition a space associated with the data into a plurality of subsets based on the plurality of hash functions, the plurality of subsets being associated with a corresponding binary code and a corresponding hash function.
20 . The computer program product as claimed in claim 18 , wherein the apparatus is further caused, at least in part to determine the upper bound based on a Jensen Shanon Divergence (JSD) measure between probability distributions associated with the plurality of classes for the plurality of hash functions.
21 . The computer program product as claimed in claim 20 , wherein the JSD measure being related with the probability of error based on following equation:
P
(
e
)
≤
1
2
(
H
(
π
)
-
J
S
D
π
(
p
1
…
,
p
M
)
)
H(π) represents the entropy of priori probabilities associated with the plurality of classes.
22 . The computer program product as claimed in claim 20 , wherein the apparatus is further caused, at least in part to:
apply a set of randomly generated candidate linear projections to the data to generate a candidate binary matrix, the randomly generated candidate linear projections comprises the plurality of hash functions;
rearrange the data to partition the candidate binary matrix based on the plurality of classes for generating a set of candidate vectors;
determine a set of binary vectors associated with the data, each binary vector of the set of binary vectors being associated with a corresponding class and a corresponding binary code;
determine, for a set of binary codes comprising the corresponding binary code associated with the each binary vector, a set of probability distributions associated with the plurality of classes based on the set of candidate vectors and the set of binary vectors;
compute the JSD measure for the plurality of hash functions based on the set of probability distributions associated with the plurality of classes; and
determine the set of hash functions from among the plurality of hash functions configured to maximize the JSD measure.