Derivation of probabilistic score for audio sequence alignment
View Patent ↗A match score provides a semantically-meaningful quantification of the aural similarity of two chromae from two corresponding audio sequences. The match score can be applied to the chroma pairs of two corresponding audio sequences, and is independent of the lengths of the sequences, thereby permitting comparisons of matches across subsequences of different length. Accordingly, a single cutoff match score to identify “good” audio subsequence matches can be determined and has both good precision and good recall metrics. A function for determining the match score is determined by establishing a function P M indicating probabilities that chroma correspondence scores indicate semantic correspondences, and a function P R indicating probabilities that chroma correspondence scores indicate random correspondences, repeatedly updating P M and the match function based on existing values of P M and the match function as applied to audio subsequences with known semantic correspondences.
1. A computer-implemented method for matching audio sequences, the method performed by a computer processor and comprising:
deriving, by the computer processor, a first probability density function P M outputting a probability that an initial correspondence score for a pair of chroma vectors of an audio sequence indicates a semantic correspondence between the chroma vectors;
deriving, by the computer processor, a second probability density function P R outputting a probability that the initial correspondence score for a pair of chroma vectors of an audio sequence indicates that the chroma vectors have a random correspondence, the deriving of P R comprising:
randomly selecting a set of pairs of audio sequences;
deriving initial correspondence scores for the set of pairs of audio sequences; and
fitting the initial correspondence scores to a probability distribution;
deriving, by the computer processorusing P M and P R , a match function indicating whether a given pair of chroma vectors of an audio sequence correspond semantically;
obtaining a first audio sequence;
comparing, by the computer processorusing the match function, the first audio sequence with a plurality of known audio sequences; and
based on the comparing, identifying, by the computer processor, a best-matching audio sequence for the first audio sequence from the known audio sequences.
2. The computer-implemented method of claim 1 , wherein the match function outputs, for an initial correspondence score for the given pair of chroma vectors, an indication of how much more likely it is that the given pair of chroma vectors correspond semantically than that the given pair of chroma vectors have a random correspondence.
3. The computer-implemented method of claim 1 , wherein deriving the match function comprises:
identifying a set S M of pairs of audio sequences from audio sequences that have been determined to have a semantic correspondence;
identifying a plurality of pairs of chroma vectors from S M , a first chroma vector of the pairs from a first audio sequence of a pair from S M , and a second chroma vector of the pairs from a second audio sequence of the pair from S M ; and
iteratively refining the match function by:
updating the match function based on the functions P M and P R ;
computing scores for the identified plurality of pairs of chroma vectors using the match function;
based on the scores, identifying best matching pairs of subsequences of chroma vectors; and
updating the function P M by mapping initial correspondence scores, for pairs of chroma vectors in the best matching pairs of subsequences, to a probability distribution function.
4. The computer-implemented method of claim 1 , wherein identifying the best matching pairs comprises using dynamic programming to identify sub-sequence pairs of consecutive chroma vectors in the audio sequences of S M having highest sums of scores of the match function for the chroma vector pairs within the sub-sequence pairs.
5. The computer-implemented method of claim 1 , wherein an output of 0 from the match function for a pair of chroma vectors indicates that it is no more likely that the chroma vectors have a semantic correspondence than that the chroma vectors have only a degree of correspondence that is typical of randomly-selected chromae.
6. The computer-implemented method of claim 1 , further comprising deriving the match function as a logarithm of a ratio of P M and P R .
7. The computer-implemented method of claim 1 , wherein the first audio sequence is verbal input received from a user, and the best-matching audio sequence is a song.
8. A non-transitory computer-readable storage medium for matching audio sequences, the computer-readable medium storing processor-executable instructions comprising:
instructions for deriving a first probability density function P M outputting a probability that an initial correspondence score for a pair of chroma vectors of an audio sequence indicates a semantic correspondence between the chroma vectors;
instructions for deriving a second probability density function P R outputting a probability that the initial correspondence score for a pair of chroma vectors of an audio sequence indicates that the chroma vectors have a random correspondence, the deriving of P R comprising:
randomly selecting a set of pairs of audio sequences;
deriving initial correspondence scores for the set of pairs of audio sequences; and
fitting the initial correspondence scores to a probability distribution;
instructions for deriving, using P M and P R , a match function indicating whether a given pair of chroma vectors of an audio sequence correspond semantically;
instructions for obtaining a first audio sequence;
instructions for comparing, using the match function, the first audio sequence with a plurality of known audio sequences; and
instructions for, based on the comparing, identifying a best-matching audio sequence for the first audio sequence from the known audio sequences.
9. The non-transitory computer-readable storage medium of claim 8 , wherein the match function outputs, for an initial correspondence score for the given pair of chroma vectors, an indication of how much more likely it is that the given pair of chroma vectors correspond semantically than that the given pair of chroma vectors have a random correspondence.
10. The non-transitory computer-readable storage medium of claim 8 , wherein deriving the match function comprises:
identifying a set S M of pairs of audio sequences from audio sequences that have been determined to have a semantic correspondence;
identifying a plurality of pairs of chroma vectors from S M , a first chroma vector of the pairs from a first audio sequence of a pair from S M , and a second chroma vector of the pairs from a second audio sequence of the pair from S M ; and
iteratively refining the match function by:
updating the match function based on the functions P M and P R ;
computing scores for the identified plurality of pairs of chroma vectors using the match function;
based on the scores, identifying best matching pairs of subsequences of chroma vectors; and
updating the function P M by mapping initial correspondence scores, for pairs of chroma vectors in the best matching pairs of subsequences, to a probability distribution function.
11. The non-transitory computer-readable storage medium of claim 10 , wherein identifying the best matching pairs comprises using dynamic programming to identify sub-sequence pairs of consecutive chroma vectors in the audio sequences of S M having highest sums of scores of the match function for the chroma vector pairs within the sub-sequence pairs.
12. The non-transitory computer-readable storage medium of claim 8 , wherein an output of 0 from the match function for a pair of chroma vectors indicates that it is no more likely that the chroma vectors have a semantic correspondence than that the chroma vectors have only a degree of correspondence that is typical of randomly-selected chromae.
13. The non-transitory computer-readable storage medium of claim 8 , the instructions further comprising instructions for deriving the match function as a logarithm of a ratio of P M and P R .
14. The non-transitory computer-readable storage medium of claim 8 , wherein the first audio sequence is verbal input received from a user, and the best-matching audio sequence is a song.
15. A computer system for matching audio sequences, the system comprising:
a computer processor; and
a non-transitory computer-readable storage medium storing instructions that when executed by the computer processor perform actions comprising:
deriving a first probability density function P M outputting a probability that an initial correspondence score for a pair of chroma vectors of an audio sequence indicates a semantic correspondence between the chroma vectors;
deriving a second probability density function P R outputting a probability that the initial correspondence score for a pair of chroma vectors of an audio sequence indicates that the chroma vectors have a random correspondence, the deriving of P R comprising;
randomly selecting a set of pairs of audio sequences;
deriving initial correspondence scores for the set of pairs of audio sequences; and
fitting the initial correspondence scores to a probability distribution;
deriving, using P M and P R , a match function indicating whether a given pair of chroma vectors of an audio sequence correspond semantically;
obtaining a first audio sequence;
comparing, using the match function, the first audio sequence with a plurality of known audio sequences; and
based on the comparing, identifying a best-matching audio sequence for the first audio sequence from the known audio sequences.
16. The computer system of claim 15 , wherein the match function outputs, for an initial correspondence score for the given pair of chroma vectors, an indication of how much more likely it is that the given pair of chroma vectors correspond semantically than that the given pair of chroma vectors have a random correspondence.
17. The computer system of claim 15 , wherein deriving the match function comprises:
identifying a set S M of pairs of audio sequences from audio sequences that have been determined to have a semantic correspondence;
identifying a plurality of pairs of chroma vectors from S M , a first chroma vector of the pairs from a first audio sequence of a pair from S M , and a second chroma vector of the pairs from a second audio sequence of the pair from S M ; and
iteratively refining the match function by:
updating the match function based on the functions P M and P R ;
computing scores for the identified plurality of pairs of chroma vectors using the match function;
based on the scores, identifying best matching pairs of subsequences of chroma vectors; and
updating the function P M by mapping initial correspondence scores, for pairs of chroma vectors in the best matching pairs of subsequences, to a probability distribution function.