Constructing a table of music similarity vectors from a music similarity graph

• US 7,777,125 B2
• Filed: 11/19/2004
• Issued: 08/17/2010
• Est. Priority Date: 11/19/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Herley, Cormac, Renshaw, Erin, Chickering, Max, Platt, John
• Primary Examiner(s): Benson; Walter
• Assistant Examiner(s): Chan; Kawing
• Application Number:
  US10/993,109
• Publication Number:
  US 20060107823A1
• Time in Patent Office: 2,097 Days
• Field of Search: 846/09, 846/16, 846/49, 846/54, 707/104.1, 707/10, 707/101, 348/722
• US Class Current: 84/616
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/635 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/639 using playlists
• CPC Class Codes: G06F 16/68 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G10H 2240/091 Info, i.e. juxtaposition of unrelated auxiliary information or commercial messages with or between music files metadata G10H2240/075
• CPC Class Codes: G10H 2240/135 Library retrieval index, i.e. using an indexing scheme to efficiently retrieve a music piece
• CPC Class Codes: G10H 2240/155 Library update, i.e. making or modifying a musical database using musical parameters as indices data structures involving musical parameters G10H2240/005
• CPC Class Codes: G10H 2250/005 Algorithms for electrophonic musical instruments or musical processing, e.g. for automatic composition or resource allocation mathematical functions therefor G10H2250/131; details of musical waveform synthesis G10H2250/541
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A “Music Mapper” automatically constructs a set coordinate vectors for use in inferring similarity between various pieces of music. In particular, given a music similarity graph expressed as links between various artists, albums, songs, etc., the Music Mapper applies a recursive embedding process to embed each of the graphs music entries into a multi-dimensional space. This recursive embedding process also embeds new music items added to the music similarity graph without reembedding existing entries so long a convergent embedding solution is achieved. Given this embedding, coordinate vectors are then computed for each of the embedded musical items. The similarity between any two musical items is then determined as either a function of the distance between the two corresponding vectors. In various embodiments, this similarity is then used in constructing music playlists given one or more random or user selected seed songs or in a statistical music clustering process.

Claims

1. A system for generating a set of coordinate vectors from a sparse graph of media object similarities, comprising using a computing device for:

receiving a sparse graph of media object similarities;

computing a set of coordinate vectors from the media object similarities of each media object comprising a subset of media objects represented by the sparse graph;

updating the set of coordinate vectors by computing coordinate vectors for each remaining media object represented by the sparse graph which was not included in the subset of media objects; and

storing the set of coordinate vectors to a computer readable storage media.

2. The system of claim 1 wherein receiving the sparse graph of media object similarities comprises automatically constructing the sparse graph from a plurality of sparse graph data sources.

3. The system of claim 2 wherein automatically constructing the sparse graph of media object similarities comprises automatically combining two or more sparse graphs from the plurality of sparse graph data sources.

4. The system of claim 2 wherein the plurality of sparse graph data sources includes a set of collaborative filtering data for describing similarity relationships between a plurality of the media objects.

5. The system of claim 2 wherein the plurality of sparse graph data sources includes an ordered list of media object adjacency data derived from one or more authored media streams.

6. The system of claim 5 wherein the media object adjacency data is derived by monitoring a broadcast of the authored media streams, identifying the media objects in the authored media streams, and recording the adjacency data for each identified object in the authored media streams.

7. The system of claim 2 wherein one of the plurality of sparse graph data sources is generated from a set of metadata for characterizing each of the media objects.

8. The system of claim 1 wherein the sparse graph of media object similarities is an editorial sparse graph of media object similarities.

9. The system of claim 1 wherein computing the set of coordinate vectors from each media object comprising the subset of media objects comprises initially embedding each media object in the subset into a multidimensional space.

10. The system of claim 9 wherein updating the set of coordinate vectors by computing coordinate vectors for each remaining media object comprises:

holding the coordinate vectors of the initially embedded media objects fixed in the multidimensional space; and

for each remaining media object, recursively assigning a coordinate vector to each remaining media object, wherein the assigned coordinate vector is an average of the fixed coordinate vectors of media objects linked to that remaining media object and of the assigned coordinate vectors of each remaining media object linked to that remaining media object in the sparse graph.

11. The system of claim 10 wherein the average of the fixed coordinate vectors is a weighted average.

12. The system of claim 10 wherein recursively assigning the coordinate vector to each remaining media object continues until a convergent coordinate vector embedding solution is achieved for at least a majority of the remaining media objects.

13. The system of claim 10 wherein recursively assigning the coordinate vector to each remaining media object continues for a predetermined number of iterations.

14. The system of claim 9 wherein initially embedding each media object into a multidimensional space comprises performing a multidimensional scaling-based processing of the sparse graph of media object similarities.

15. The system of claim 14 wherein the multidimensional scaling-based processing is a Landmark MDS process.

16. The system of claim 14 wherein the multidimensional scaling-based processing is a Fast Sparse Embedding process.

17. The system of claim 1 wherein the media objects include any of music artists, music albums, and music tracks.

18. The system of claim 1 further comprising weighting one or more links of the sparse graph of media object similarities.

19. The system of claim 18 further comprising performing a simplex optimization for automatically optimizing the weighted links for maximally matching a predetermined data set.

20. The system of claim 1 further comprising weighting one or more global classes of links of the sparse graph of media object similarities.

21. The system of claim 20 further wherein the global classes of links of the sparse graph of media object similarities include one or more of music artists, music albums, and music tracks.

22. The system of claim 21 further comprising performing a simplex optimization for automatically optimizing one or more of the weighted global classes of links for maximally matching one or more predefined data sets.

23. The system of claim 1 wherein user preferences are used to assign a weight to one or more media objects represented by the sparse graph of media object similarities for adjusting one or more of the similarities.

24. The system of claim 23 wherein a weight for decreasing a similarity to other media objects is assigned a media objects having a negative user preference.

25. The system of claim 23 wherein a weight for increasing a similarity to other media objects is assigned a media objects having a positive user preference.

26. A non-transitory computer-readable medium having computer executable instructions for generating coordinate vectors from a sparse graph of music object similarities, comprising:

computing a set of coordinate vectors from music object similarities associated with each music object for each of a set of initial music objects represented by a sparse graph by embedding each initial music object into a multidimensional space as a function of the music object similarities associated with each music object;

updating the sparse graph by adding one or more subsequent music objects to the sparse graph; and

updating the set of coordinate vectors by computing coordinate vectors for each subsequent music object by holding the coordinate vectors of the initial music objects fixed in the multidimensional space, and iteratively computing a coordinate vector for each subsequent music object as a function of similar initial and subsequent music objects until a convergent embedding solution is achieved.

27. The computer-readable medium of claim 26 wherein nodes of the sparse graph represent the music objects and edges of the sparse graph represent a similarity between various nodes in the sparse graph.

28. The computer-readable medium of claim 27 further comprising weighting one or more of the edges of the sparse graph.

29. The computer-readable medium of claim 28 further comprising performing a simplex optimization for automatically optimizing the weighted edges of the sparse graph links relative to a predetermined data set.

30. The computer-readable medium of claim 26 wherein one or more nodes of the sparse graph are weighted to reflect user preferences as to the corresponding music objects.

31. The computer-readable medium of claim 26 wherein the music objects include any one or more of music artists, music albums, and music tracks.

32. The computer-readable medium of claim 26 wherein the sparse graph is generated from a plurality of sparse graph data sources.

33. The computer-readable medium of claim 32 wherein the plurality of sparse graph data sources includes at least one of:

a set of collaborative filtering data for describing similarity relationships between a plurality of the media objects;

an ordered list of media object adjacency data derived from one or more authored media streams;

a sparse graph generated from a set of metadata for characterizing a plurality of the media objects; and

an editorial sparse graph of media object similarities.

34. The computer-readable medium of claim 26 wherein updating the set of coordinate vectors by recursively computing coordinate vectors for each subsequent music object continues for a predetermined number of iterations.

35. The computer-readable medium of claim 26 wherein embedding each initial music object into the multidimensional space comprises performing a multidimensional scaling-based processing of the initial music objects represented by the sparse graph.

36. The computer-readable medium of claim 35 wherein the multidimensional scaling-based processing is a Landmark MDS process.

37. The computer-readable medium of claim 35 wherein the multidimensional scaling-based processing is a Fast Sparse Embedding process.

38. The computer-readable medium of claim 26 wherein assigning the coordinate vector to each subsequent music comprises, for each subsequent music object, iteratively computing an average of the fixed coordinate vectors of music objects linked to that subsequent music object and any coordinate vectors assigned to other subsequent music objects linked to that subsequent music object, and assigning the computed average coordinate vector to that music object until the convergent embedding solution is achieved.

39. The computer-readable medium of claim 38 wherein the iteratively computed average is a weighted average.

40. A computer-implemented process for constructing a table of music similarity vectors from a sparse graph of music similarities, comprising:

constructing a sparse graph of music similarities representing interrelationships between a plurality of music objects;

embedding each music object represented by the sparse graph of music similarities into a multidimensional space by applying multidimensional scaling to the sparse graph, thereby generating an initial set of music similarity vectors from the media object similarities corresponding to each music object; and

updating the sparse graph of music similarities by adding one or more subsequent music objects to the sparse graph of music similarities;

updating the initial set of music similarity vectors by iteratively generating new music similarity vectors for each subsequent music object while keeping each original music similarity vector in the initial set of music similarity vectors fixed; and

storing the updated set of music similarity vectors to a non-transitory computer readable storage media.

41. The computer-implemented process of claim 40 wherein nodes of the sparse graph represent the music objects and edges of the sparse graph represent a similarity between various nodes in the sparse graph.

42. The computer-implemented process of claim 41 the plurality of sparse graph data sources includes at least one of:

a set of collaborative filtering data for describing similarity relationships between a plurality of the media objects;

an ordered list of media object adjacency data derived from one or more authored media streams;

a sparse graph generated from a set of metadata for characterizing a plurality of the media objects; and

an editorial sparse graph of media object similarities.

43. The computer-implemented process of claim 41 further comprising weighting one or more of the edges of the sparse graph.

44. The computer-implemented process of claim 43 further comprising performing a simplex optimization for automatically optimizing the weights of the edges of the sparse graph links relative to a predetermined data set.

45. The computer-implemented process of claim 41 further comprising weighting one or more of the nodes of the sparse graph to reflect user preferences as to the corresponding music objects.

46. The computer-implemented process of claim 40 wherein constructing the sparse graph of music similarities comprises combining one or more of a plurality of sparse graph data sources.

47. The computer-implemented process of claim 40 wherein the multidimensional scaling is a Landmark MDS process.

48. The computer-implemented process of claim 40 wherein the multidimensional scaling is a Fast Sparse Embedding process.