Patent ID: 12231708

DETAILED DESCRIPTION

Reference will now be made to embodiments, examples of which are illustrated in the accompanying drawings. In the following description, numerous specific details are set forth in order to provide an understanding of the various described embodiments. However, it will be apparent to one of ordinary skill in the art that the various described embodiments may be practiced without these specific details. In other instances, well-known methods, procedures, components, circuits, and networks have not been described in detail so as not to unnecessarily obscure aspects of the embodiments.

It will also be understood that, although the terms first, second, etc. are, in some instances, used herein to describe various elements, these elements should not be limited by these terms. These terms are used only to distinguish one element from another. For example, a first electronic device could be termed a second electronic device, and, similarly, a second electronic device could be termed a first electronic device, without departing from the scope of the various described embodiments. The first electronic device and the second electronic device are both electronic devices, but they are not the same electronic device.

The terminology used in the description of the various embodiments described herein is for the purpose of describing particular embodiments only and is not intended to be limiting. As used in the description of the various described embodiments and the appended claims, the singular forms “a,” “an,” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term “and/or” as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. It will be further understood that the terms “includes,” “including,” “comprises,” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

As used herein, the term “if” is, optionally, construed to mean “when” or “upon” or “in response to determining” or “in response to detecting” or “in accordance with a determination that,” depending on the context. Similarly, the phrase “if it is determined” or “if [a stated condition or event] is detected” is, optionally, construed to mean “upon determining” or “in response to determining” or “upon detecting [the stated condition or event]” or “in response to detecting [the stated condition or event]” or “in accordance with a determination that [a stated condition or event] is detected,” depending on the context.

As used herein, the term “playlist” means a list of digital files to be played on an electronic device (e.g., an electronic device102). In some embodiments, the playlists described herein are generated automatically (e.g., algorithmically) by a computer system (e.g., the playlists comprise suggested media content). In some embodiments, the playlists described herein include so-called “radio stations” (e.g., streaming music “stations” based on particular songs, artists, genres, or topics). In some embodiments, the playlist described herein include personalized playlists (e.g., playlist based on preferences of the user to whom the playlist is being provided). An example of a personalized playlist is a “Daily Mix,” which recommends media items that a user is likely to enjoy. In some embodiments, the personalized playlists are based on a listening history of the user with a streaming media service (e.g., the streaming media service providing the playlist). One of skill in the art, having the benefit of this disclosure, will recognize numerous other types of playlists to which the embodiments described herein may apply.

FIG.1is a block diagram illustrating a media content delivery system100, in accordance with some embodiments. The media content delivery system100includes one or more electronic devices102(e.g., electronic device102-1to electronic device102-m, where m is an integer greater than one), one or more media content servers104, and/or one or more content distribution networks (CDNs)106. The one or more media content servers104are associated with (e.g., at least partially compose) a media providing service. The one or more CDNs106store and/or provide one or more content items (e.g., to electronic devices102). In some embodiments, the CDNs106are included in the media content servers104. One or more networks112communicably couple the components of the media content delivery system100. In some embodiments, the one or more networks112include public communication networks, private communication networks, or a combination of both public and private communication networks. For example, the one or more networks112can be any network (or combination of networks) such as the Internet, other wide area networks (WAN), local area networks (LAN), virtual private networks (VPN), metropolitan area networks (MAN), peer-to-peer networks, and/or ad-hoc connections.

In some embodiments, an electronic device102is associated with one or more users. In some embodiments, an electronic device102is a personal computer, mobile electronic device, wearable computing device, laptop computer, tablet computer, mobile phone, feature phone, smart phone, infotainment system, digital media player, a speaker, television (TV), digital versatile disk (DVD) player, and/or any other electronic device capable of presenting media content (e.g., controlling playback of media items, such as music tracks, podcasts, videos, etc.). Electronic devices102may connect to each other wirelessly and/or through a wired connection (e.g., directly through an interface, such as an HDMI interface). In some embodiments, an electronic device102is a headless client. In some embodiments, electronic devices102-1and102-mare the same type of device (e.g., electronic device102-1and electronic device102-mare both speakers). Alternatively, electronic device102-1and electronic device102-minclude two or more different types of devices.

In some embodiments, electronic devices102-1and102-msend and receive media-control information through network(s)112. For example, electronic devices102-1and102-msend media control requests (e.g., requests to play music, podcasts, movies, videos, or other media items, or playlists thereof) to media content server104through network(s)112. Additionally, electronic devices102-1and102-m, in some embodiments, also send indications of media content items to media content server104through network(s)112. In some embodiments, the media content items are uploaded to electronic devices102-1and102-mbefore the electronic devices forward the media content items to media content server104.

In some embodiments, electronic device102-1communicates directly with electronic device102-m(e.g., as illustrated by the dotted-line arrow), or any other electronic device102. As illustrated inFIG.1, electronic device102-1is able to communicate directly (e.g., through a wired connection and/or through a short-range wireless signal, such as those associated with personal-area-network (e.g., BLUETOOTH/BLE) communication technologies, radio-frequency-based near-field communication technologies, infrared communication technologies, etc.) with electronic device102-m. In some embodiments, electronic device102-1communicates with electronic device102-mthrough network(s)112. In some embodiments, electronic device102-1uses the direct connection with electronic device102-mto stream content (e.g., data for media items) for playback on the electronic device102-m.

In some embodiments, electronic device102-1and/or electronic device102-minclude a media application222(FIG.2) that allows a respective user of the respective electronic device to upload (e.g., to media content server104), browse, request (e.g., for playback at the electronic device102), and/or present media content (e.g., control playback of music tracks, podcasts, videos, etc.). In some embodiments, one or more media content items are stored locally by an electronic device102(e.g., in memory212of the electronic device102,FIG.2). In some embodiments, one or more media content items are received by an electronic device102in a data stream (e.g., from the CDN106and/or from the media content server104). The electronic device(s)102are capable of receiving media content (e.g., from the CDN106) and presenting the received media content. For example, electronic device102-1may be a component of a network-connected audio/video system (e.g., a home entertainment system, a radio/alarm clock with a digital display, or an infotainment system of a vehicle). In some embodiments, the CDN106sends media content to the electronic device(s)102.

In some embodiments, the CDN106stores and provides media content (e.g., media content requested by the media application222of electronic device102) to electronic device102via the network(s)112. Content (also referred to herein as “media items,” “media content items,” and “content items”) is received, stored, and/or served by the CDN106. In some embodiments, content includes audio (e.g., music, spoken word, podcasts, audiobooks, etc.), video (e.g., short-form videos, music videos, television shows, movies, clips, previews, etc.), text (e.g., articles, blog posts, emails, etc.), image data (e.g., image files, photographs, drawings, renderings, etc.), games (e.g., 2- or 3-dimensional graphics-based computer games, etc.), or any combination of content types (e.g., web pages that include any combination of the foregoing types of content or other content not explicitly listed). In some embodiments, content includes one or more audio media items (also referred to herein as “audio items,” “tracks,” and/or “audio tracks”).

In some embodiments, media content server104receives media requests (e.g., commands) from electronic devices102. In some embodiments, media content server104includes a voice API, a connect API, and/or key service (e.g., key database336,FIG.3). In some embodiments, media content server104validates (e.g., using key service) electronic devices102by exchanging one or more keys (e.g., tokens) with electronic device(s)102.

In some embodiments, media content server104and/or CDN106stores one or more playlists (e.g., information indicating a set of media content items). For example, a playlist is a set of media content items defined by a user, defined by an editor associated with a media providing service, defined by an algorithmic model, or defined through any other means (or combination of means). The description of the media content server104as a “server” is intended as a functional description of the devices, systems, processor cores, and/or other components that provide the functionality attributed to the media content server104. It will be understood that the media content server104may be a single server computer, or may be multiple server computers. Moreover, the media content server104may be coupled to CDN106and/or other servers and/or server systems, or other devices, such as other client devices, databases, content delivery networks (e.g., peer-to-peer networks), network caches, and the like. In some embodiments, the media content server104is implemented by multiple computing devices working together to perform the actions of a server system (e.g., cloud computing).

FIG.2is a block diagram illustrating an electronic device102(e.g., electronic device102-1and/or electronic device102-m,FIG.1), in accordance with some embodiments. The electronic device102includes one or more central processing units (CPU(s), i.e., processors or cores)202, one or more network (or other communications) interfaces210, memory212, and one or more communication buses214for interconnecting these components. The communication buses214optionally include circuitry (sometimes called a chipset) that interconnects and controls communications between system components.

In some embodiments, the electronic device102includes a user interface204, including output device(s)206and/or input device(s)208. In some embodiments, the input devices208include a keyboard, mouse, or track pad. Alternatively, or in addition, in some embodiments, the user interface204includes a display device that includes a touch-sensitive surface, in which case the display device is a touch-sensitive display. In electronic devices that have a touch-sensitive display, a physical keyboard is optional (e.g., a soft keyboard may be displayed when keyboard entry is needed). In some embodiments, the output devices (e.g., output device(s)206) include a speaker252(e.g., speakerphone device) and/or an audio jack250(or other physical output connection port) for connecting to speakers, earphones, headphones, or other external listening devices. Furthermore, some electronic devices102use a microphone and voice recognition device to supplement or replace the keyboard. Optionally, the electronic device102includes an audio input device (e.g., a microphone) to capture audio (e.g., speech from a user).

Optionally, the electronic device102includes a location-detection device240, such as a global navigation satellite system (GNSS) (e.g., GPS (global positioning system), GLONASS, Galileo, BeiDou) or other geo-location receiver, and/or location-detection software for determining the location of the electronic device102(e.g., module for finding a position of the electronic device102using trilateration of measured signal strengths for nearby devices).

In some embodiments, the one or more network interfaces210include wireless and/or wired interfaces for receiving data from and/or transmitting data to other electronic devices102, a media content server104, a CDN106, and/or other devices or systems. In some embodiments, data communications are carried out using any of a variety of custom or standard wireless protocols (e.g., NFC, RFID, IEEE 802.15.4, Wi-Fi, ZigBee, 6LoWPAN, Thread, Z-Wave, Bluetooth, ISA100.11a, WirelessHART, MiWi, etc.). Furthermore, in some embodiments, data communications are carried out using any of a variety of custom or standard wired protocols (e.g., USB, Firewire, Ethernet, etc.). For example, the one or more network interfaces210include a wireless interface260for enabling wireless data communications with other electronic devices102, media presentations systems108, and/or or other wireless (e.g., Bluetooth-compatible) devices (e.g., for streaming audio data to the media presentations system108of an automobile). Furthermore, in some embodiments, the wireless interface260(or a different communications interface of the one or more network interfaces210) enables data communications with other WLAN-compatible devices (e.g., a media presentations system108) and/or the media content server104(via the one or more network(s)112,FIG.1).

In some embodiments, electronic device102includes one or more sensors including, but not limited to, accelerometers, gyroscopes, compasses, magnetometer, light sensors, near field communication transceivers, barometers, humidity sensors, temperature sensors, proximity sensors, range finders, and/or other sensors/devices for sensing and measuring various environmental conditions.

Memory212includes high-speed random-access memory, such as DRAM, SRAM, DDR RAM, or other random-access solid-state memory devices; and may include non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid-state storage devices. Memory212may optionally include one or more storage devices remotely located from the CPU(s)202. Memory212, or alternately, the non-volatile memory solid-state storage devices within memory212, includes a non-transitory computer-readable storage medium. In some embodiments, memory212or the non-transitory computer-readable storage medium of memory212stores the following programs, modules, and data structures, or a subset or superset thereof:an operating system216that includes procedures for handling various basic system services and for performing hardware-dependent tasks;network communication module(s)218for connecting the client device102to other computing devices (e.g., media presentation system(s)108, media content server104, and/or other client devices) via the one or more network interface(s)210(wired or wireless) connected to one or more network(s)112;a user interface module220that receives commands and/or inputs from a user via the user interface204(e.g., from the input devices208) and provides outputs for playback and/or display on the user interface204(e.g., the output devices206);media application222(e.g., an application for accessing a media providing service of a media content provider associated with media content server104) for uploading, browsing, receiving, processing, presenting, and/or requesting playback of media (e.g., media items). In some embodiments, media application222includes a media player, a streaming media application, and/or any other appropriate application or component of an application. In some embodiments, media application222also includes the following modules (or sets of instructions), or a subset or superset thereof:a media content selection module224for selecting one or more media content items and/or sending, to the media content server, an indication of the selected media content item(s). In some embodiments, a user may select a playlist that is periodically generated or updated (e.g., a “My Daily Hits” playlist that is generated or updated daily, when the user requests the playlist, or otherwise on a predefined schedule);a media content browsing module226for providing controls and/or user interfaces enabling a user to navigate, select for playback, and otherwise control or interact with media content, whether the media content is stored or played locally or remotely;a content items module228for storing media items for playback and/or for forwarding requests for media content items to the media content server;a web browser application235(e.g., Internet Explorer or Edge by Microsoft, Firefox by Mozilla, Safari by Apple, or Chrome by Google) for accessing, viewing, and interacting with web sites; andother applications236, such as applications for word processing, calendaring, mapping, weather, stocks, time keeping, virtual digital assistant, presenting, number crunching (spreadsheets), drawing, instant messaging, e-mail, telephony, video conferencing, photo management, video management, a digital music player, a digital video player, 2D gaming, 3D (e.g., virtual reality) gaming, electronic book reader, and/or workout support.

FIG.3is a block diagram illustrating a media content server104, in accordance with some embodiments. The media content server104typically includes one or more central processing units/cores (CPUs)302, one or more network interfaces304, memory306, and one or more communication buses308for interconnecting these components.

Memory306includes high-speed random access memory, such as DRAM, SRAM, DDR RAM, or other random access solid-state memory devices; and may include non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid-state storage devices. Memory306optionally includes one or more storage devices remotely located from one or more CPUs302. Memory306, or, alternatively, the non-volatile solid-state memory device(s) within memory306, includes a non-transitory computer-readable storage medium. In some embodiments, memory306, or the non-transitory computer-readable storage medium of memory306, stores the following programs, modules and data structures, or a subset or superset thereof:an operating system310that includes procedures for handling various basic system services and for performing hardware-dependent tasks;a network communication module312that is used for connecting the media content server104to other computing devices via one or more network interfaces304(wired or wireless) connected to one or more networks112;one or more server application modules314for performing various functions with respect to providing and managing a content service, the server application modules314including, but not limited to, one or more of:a media content module316for storing one or more media content items and/or sending (e.g., streaming), to the electronic device, one or more requested media content item(s), or one or more media content item(s) from a requested playlist;a media request processing module322for processing requests for media content and facilitating access to requested media items by client devices (e.g., the client device102) including, optionally, streaming media content to such devices and/or to one or more media presentation system(s)108;A playlist generation module324for selecting a sequence of media items (e.g., for performing method700, as described with reference toFIGS.7A-7C). In some embodiments, the playlist generation module324includes one or more of:An objectives module326for generating scores for each of a plurality of objectives and aggregating the respective scores; andA constraints module328for determining which media items meet a plurality of constraints for generating the sequence of media items. In some embodiments, the constraints define disqualification criteria for excluding media items from a respective slot in the sequence of media items. The constraints may include global constraints (e.g., constraints that do not depend on already-populated slots in the sequence of media items) as well as non-global constraints (e.g., constraints that depend on already-populated slots in the sequence of media items).one or more server data module(s)330for handling the storage of and/or access to media items and/or metadata relating to the media items; in some embodiments, the one or more server data module(s)330include:a media content database332for storing media items;a metadata database334for storing metadata relating to the media items; anda key database336for storing keys related to account information for user media accounts, such as user profiles, credentials (e.g., user identifiers, passwords, email addresses, etc.), and/or identifiers of any linked accounts.

In some embodiments, the media content server104includes web or Hypertext Transfer Protocol (HTTP) servers, File Transfer Protocol (FTP) servers, as well as web pages and applications implemented using Common Gateway Interface (CGI) script, PHP Hyper-text Preprocessor (PHP), Active Server Pages (ASP), Hyper Text Markup Language (HTML), Extensible Markup Language (XML), Java, JavaScript, Asynchronous JavaScript and XML (AJAX), XHP, Javelin, Wireless Universal Resource File (WURFL), and the like.

Each of the above identified modules stored in memory212and306corresponds to a set of instructions for performing a function described herein. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures, or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various embodiments. In some embodiments, memory212and306optionally store a subset or superset of the respective modules and data structures identified above. Furthermore, memory212and306optionally store additional modules and data structures not described above.

AlthoughFIG.3illustrates the media content server104in accordance with some embodiments,FIG.3is intended more as a functional description of the various features that may be present in one or more media content servers than as a structural schematic of the embodiments described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated. For example, some items shown separately inFIG.3could be implemented on single servers and single items could be implemented by one or more servers. In some embodiments, media content database332and/or metadata database334are stored on devices (e.g., CDN106) that are accessed by media content server104. The actual number of servers used to implement the media content server104, and how features are allocated among them, will vary from one implementation to another and, optionally, depends in part on the amount of data traffic that the server system handles during peak usage periods as well as during average usage periods.

FIG.4Ais a schematic diagram of a process for sequencing a playlist of media items, in accordance with some embodiments. Playlist generation module324(server system104,FIG.3) accesses a candidate pool402. In some embodiments, the candidate pool comprises media content items that are candidates for inclusion into the playlist (referred to hereafter as “candidates”). In some embodiments, the candidate pool comprises a repository of media content items (e.g., several thousand or million media content items). In some embodiments, the media content items comprise audio content items and/or video content items (which would also typically include audio). In some embodiments, the media content items in the candidate pool have already been pre-filtered from a larger set (e.g., repository) of media content items. For example, in some embodiments, the media content items in the candidate pool comprise media content items that have been selected for a specific user (for whom the playlist is being generated). In some embodiments, the media content items have been selected for the specific user based on the specific user's listening history and/or current context (e.g., time of day, location, etc.). In some embodiments, the playlist generation module324pulls (e.g., considers) all of the media items in candidate pool402to fill a slot in the playlist (e.g., according to the remainder of the process illustrated inFIG.4A). Alternatively, in some embodiments, the candidate pool includes many thousands or millions of items and the playlist generation module324pulls a predefined batch of candidate items (e.g., 100 items selected at random) to fill a slot in the playlist.

The playlist generation module324keeps track of a sequencer state404that indicates an order of media content items that have already been added to the playlist (e.g., already-populated slots in the sequence of media items). In some embodiments, the set of constraints are varied based on the media content items that have already been added to the playlist (e.g., the constraints are dynamically updated, for each respective slot). At the outset (e.g., when populating slot or index0), there are no media content items in the playlist (e.g., the sequencer state404is null). Thus, the only constraints to be applied to index0are global constraints (e.g., constraints that do not depend on already-populated slots in the sequence of media items).

The playlist generation module324calculates (e.g., for each candidate) objective scores406for each of a plurality of objectives. For example, the objectives may include listener-based objectives (e.g., such as maximizing the number of “likes,” maximizing the length of the listening session, minimizing the number of skips, etc.) as well as artist-based objectives (e.g., an objective to promote certain tracks or artists, an objective to provide the user with a greater diversity of music so as to attract the user to new music, etc.). In addition, some objectives may depend on the sequencer state (e.g., by penalizing placement of two songs by the same artist in close proximity to one another).

The playlist generation module324aggregates408the objective scores for each candidate. In some embodiments, objective scores are aggregated according to an aggregation function. In some embodiments, objective scores are aggregated using a weighted average (e.g., the aggregation function is a weighted average function). In some embodiments, the objective scores are aggregated using an ordered weighted average. In some embodiments, the objective scores are aggregated using a hierarchical ordered weighted average (e.g., as described with reference toFIGS.5A-5B, below). In any event, the output of the aggregation function is typically a single value representing an overall score for the candidate.

The playlist generation module324selects410a scored candidate using a selection strategy. For example, in some embodiments, the playlist generation module324selects the highest scored candidate (e.g., the candidate item with the highest aggregated score). In some embodiments, the playlist generation module324randomly selects a candidate from the candidates with scores above a predefined threshold (e.g., randomly selects one of the top 10 or 100 scored candidates).

The playlist generation module324checks if the selected candidate passes constraints412. In some embodiments, the selected candidate item is checked against a plurality of constraints. The plurality of constraints define disqualification criteria for excluding media items from the respective slot in the sequence of media items. In some embodiments, the plurality of constraints for the respective slot in the sequence of media items includes at least one constraint that is based on already-populated slots in the sequence of media items (e.g., the playlist generation module324checks that the selected candidate meets the constraints with respect to the sequencer state404). For the first item in the playlist (e.g., index0), such constraints are moot. In accordance with a determination that the selected candidate has passed the constraints, the selected candidate item is added to the playlist414and the sequencer state404is updated, and the process is repeated for the next slot in the sequence of media items (e.g., using the updated sequencer state). On the other hand, in accordance with a determination that the selected candidate does not pass constraints, a new scored candidate is selected using the selection strategy. The loop of checking if the selected candidate passes constraints412and selecting a scored candidate item repeats until a selected candidate item passes the constraints or there are no remaining scored candidate items. In the latter case, in some embodiments, the constraints are relaxed (according to a priority of the constraints) and the loop is repeated. The sequenced candidates (e.g., the playlist) are then provided to the user418.

Note thatFIG.4Aillustrates embodiments in which the candidate items are scored before checking to see which candidate items pass the constraints. In some embodiments, however, the playlist generation module324checks which candidates pass the constraints for a respective slot, then scores the candidates and selects a candidate based on a selection strategy.

FIG.4Billustrates a disqualification table420for constraints for sequencing a playlist of media items, in accordance with some embodiments. In some embodiments (e.g., in which the playlist generation module324determines which candidates pass which constraints before scoring the candidates), the disqualification table420includes all constraints (e.g., global constraints, as well as constraints that depend on the sequencer state404) and is produced at the beginning of the process for populating each respective slot in the playlist (e.g., the disqualification table420is generated or updated once for each slot, before populating the slot). In some embodiments (e.g., in which the playlist generation module324scores candidates before determining whether individual candidates pass the constraints for a respective slot), the disqualification table420includes only global constraints (e.g., the disqualification table420is generated once for populating the entire playlist). In either event, the disqualification table420makes the process of determining whether particular candidates meet the constraints more efficient, without needing to constantly recheck the candidates (e.g., when relaxing constraints).

The constraints (e.g., constraints C0, C1, C2, C3, and C4) are specified by a list of constraints422, which also specifies a priority of the constraints (e.g., based on an order in which the constraints are passed as arguments). In the example shown inFIG.4B, C0is the highest priority constraint (with a priority of 5), C1is the second highest priority constraint (with a priority of 4), C2is the third highest priority constraint (with a priority of 3), C3is the fourth highest priority constraint (with a priority of 2) and C4is the lowest priority constraint (with a priority of 1).

Two examples of constraints are shown inFIG.4B. Constraint C2disqualifies candidate A from indices0through3(in other words, disqualifies candidate A from the first four positions in the playlist). Constraint C3disqualifies all candidates other than candidate E from index zero. Such a constraint may be appropriate, for example, when the playlist is a “radio station” for a particular song, and candidate E is the particular song (e.g., it is often desirable to start a particular song's “radio station” with that song).

Disqualification table420includes columns corresponding to individual candidates and rows corresponding to indices within the sequence of media items (e.g., slots in the playlist). Disqualification table420indicates the highest priority at which each candidate is disqualified. For example, candidate A is disqualified from index0by both constraint C2and constraint C3. But because constraint C2has a higher priority (e.g., a priority of 3 as opposed to a priority of 2), the disqualification table420includes a value of 3 for candidate A at index0. A value of 0 in disqualification table420indicates that the candidate is not disqualified by any of the constraints. As constraints are relaxed to a certain level of priority, the playlist generation module324references the disqualification table to determine which candidates pass the constraints at that level of priority.

In some embodiments, the disqualification table420is calculated for the candidates in the candidate pool402(FIG.4A). In some embodiments, the disqualification table420is calculated for each candidate in the candidate pool402(e.g., disqualification table420includes a column for each candidate in the candidate pool402).

FIGS.5A-5Billustrate a block diagram of a process of combining multiple objectives using hierarchical ordered weighted averaging, in accordance with some embodiments. In order to determine an overall score for a particular media content item (referred to below as a candidate, x), as a candidate to include in a playlist, its scores for various objectives are aggregated using an ordered weighted average. Ordered weighted average functions (OWA functions) are aggregation functions that associate weights with the value of each input (instead of associating weights with a particular input). In this way, OWA functions differ from weighted arithmetic means in that the weights for OWA functions are not apriori associated with the particular inputs, but are associated with particular inputs based on the relative magnitude of the inputs (e.g., a first weight is applied to the highest-valued input, a second weight is applied to the second highest-valued input, and so on). Thus, the importance of an input is determined by its value. For example, when selecting candidates using several satisfaction criterion (e.g., relevance, popularity, artist affinity), the largest input (the highest satisfaction criterion) is the most important, regardless of whichever specific one it is. The procedure involves three main steps: (i) specifying a quantifier, Q, (ii) generating a set of order weights associated with Q, and (iii) computing the overall evaluation for each candidate (e.g., where, in some embodiments, each candidate is a media content item that could be included in a playlist) by means of the OWA combination function. Given a weighting vector w, the OWA function is:

OWAw(x)=∑i=1nwi⁢x(i)=〈w,x↘〉,
where w is the weighting vector, x is the input vector, and xis the vector obtained from x by arranging its components in non-increasing order (e.g., from the greatest value of x to the least value of x). Note that calculation of the value of the OWA function can be done by using a sort( ) operation. If all weights are equal, OWA becomes an arithmetic mean.

OWA functions are symmetric aggregation functions that allocate weights according to the input value. Thus, OWA can emphasize the largest, the smallest or mid-range inputs (in other words, the weight applied to the highest value need not be the largest weight). Thus, in the OWA aggregation, the weights are not associated with a particular argument but with the ordered position of the arguments. The quantifier is used to generate an OWA weighting vector W of dimension n (e.g., where n is the number of inputs to be weighted). This weighting vector is then used in an OWA aggregation to determine the overall evaluation for each candidate. For each candidate, the argument of this OWA aggregation is the satisfaction of the candidate to each of the criteria (e.g., where the satisfaction of the candidate to each of the criteria is the score for each objective, as discussed elsewhere in this document).

In some embodiments, the quantifier is a Regular Increasing Monotone (RIM) quantifier, which implies that the solution improves as more criteria are satisfied:

wi=Q⁡(in)-Q⁡(i-1n).

The Regular Increasing Monotone (RIM) quantifier can provide information aggregation procedures guided by verbally expressed concepts (e.g., linguistic quantifiers, that are able to express the concept of fuzzy majority: “for all”, “there exists”, “identity”, “most”, “at least half”, “as many as possible”) and a dimension independent description of the desired aggregation. A fuzzy subset Q of the real line is called a Regular Increasing Monotone (RIM) quantifier if Q(0)=0, Q(1)=1 and Q(x)≥Q(y) if x>y.

Some parameterized RIM quantifier families Q(x, α) are discussed where parameter α determines the “or”-ness level of these quantifiers, which serves as the control parameter in the aggregation process. Although the class of proportional quantifiers known as the regular increasing monotone (RIM) quantifiers is described here, it will be understood that other types of quantifiers can also be used. To identify the quantifier some embodiments employ a method for defining a parameterized subset on the unit interval. For example,
Q(p)=pα(α>0)
where Q(p) is represented as a fuzzy set in interval [0, 1]. It can be applied for generating a whole family of the RIM quantifiers. By changing the parameter, α, one can generate different types of quantifiers and associated operators between the two extreme cases of the all and at least one quantifiers. For α=1, Q(p) is proportional to α and therefore it is referred to as the identity quantifier. As α tends to zero, the quantifier Q(p) approaches its extreme case of at least one, which corresponds to the MAX operator. As α tends to infinity, the quantifier Q(p) approaches its extreme case of all, which corresponds to the MIN operator. The OWA operator can be used in multiple levels, so as to form a hierarchical ordering across multiple objectives.

Depending on the value of α, OWA can give high weights to (i) sets of objectives that have many high objective scores (OWA_MANY), which works like an “AND” operator, or (ii) sets of objectives that have any high objective scores (OWA_ANY), which works like an “OR” operator, or anything in between (depending on the value of alpha). For example, for a low value of alpha (e.g., OWA_ANY), a high weight is given to the entire set of objectives if at least one of the objective scores is high. In another example, for a high value of alpha, the OWA calculation acts like an “AND” operator, where the set of objectives is assigned a high weight value only when many of the objective scores are high.

Hierarchical Ordered Weighted Average (HOWA) is an expansion of OWA. Objectives are grouped into different Objective Sets and the weight outputs from OWA calculations (either OWA_MANY, or OWA_ANY) are used as inputs to another OWA calculation. In some embodiments, the Objective Sets are treated as individual objectives. For example, OWA outputs are recursively used as new OWA inputs. The “hierarchical” part of HOWA is where the output of different OWA results are then used as the input to another OWA calculation. This could be many-leveled, althoughFIGS.5A-5Bshow two-leveled examples.

In this way, for a media content provider selecting content to include in a playlist, HOWA combines multiple objectives that support user satisfaction (e.g., track affinity, and artist affinity) in a way that is more complex than using simple averaging or weighted sums. For example, a user is satisfied with different media content for different reasons, including, familiarity with the content item, familiarity with the artist, how the media content fits with the other media content that is recently played (e.g., in the rest of the playlist), etc. Thus, it is important to score a user's satisfaction (e.g., affinity) with a media content item that accounts for this plurality of reasons (e.g., objectives).

InFIG.5A, a first ordered weighted average is applied to a first set of objectives, resulting in a score (e.g., equal to the calculated OWA) for set 1 objectives512. For example, each objective in the first set of objectives (e.g., objective502, objective504, objective506and objective508) has a value. The objectives are ordered by their value (e.g., from largest value to smallest value). For example, objective502(e.g., user-satisfaction objective) has a value of 0.8, objective504(e.g., noise objective) has a value of 0.3, objective506(e.g., track-affinity objective) has a value of 0.9, and objective508(e.g., artist-affinity objective) has a value of 0.8. Thus, the order, from greatest value to least value, is: objective506, objective502and objective508, and objective504, thus producing an ordered value vector [0.9, 0.8, 0.8, 0.3].

Next, weights are assigned to each objective, based on their order, such that the objective with the largest value also is assigned the first weight (e.g., the largest weight, although that need not be the case), and the objective with the second-to-largest value applies the second weight (e.g., the second-to-largest weight), and so on. For example, where the weight (w), for each position (alternative) i, is calculated using:

wi=Q⁡(in)-Q⁡(i-1n)
as explained above.

An OWA is then calculated for the first set of objectives (e.g., to produce a score for set 1 objectives512). For example, OWA_MANY (e.g., an “AND” operator) is applied to the first set of objectives (e.g., objective502, objective504, objective506and objective508). A score for set 1 objectives512is determined by computing the weighted sum of the OWA weights multiplied by the objective values for the objectives in the first set. Thus, the OWA is calculated by taking the weighted sum of the OWA weights [w1, w2, w3, w4] applied to the value vector [0.9, 0.8, 0.8, 0.3] (e.g., by multiplying each value by its corresponding weight, and then summing the weighted values). By applying an OWA_ANY calculation (e.g., with a high value for α), the resulting OWA (e.g., score) is, for example, 0.89 for the first set of objectives.

As illustrated by this example, each objective in the set is assigned a weight based on its value (e.g., relative to the values of the other objectives), instead of assigning a weight to a particular objective. For example, if the value of an objective is updated (e.g., changed), the order of objectives is also updated, and the weights assigned to each objective is updated accordingly.

The computed score of the first set of objectives (e.g., 0.89) then becomes the value for the first set of objectives when the first set of objectives is used in the second OWA calculation. For example, set 1 objectives512(e.g., with a value of 0.89) becomes an objective within objective set 2 (e.g., which also includes additional objectives510,514, and515).

A second ordered weighted average is applied to the second set of objectives to determine combined objectives516, wherein the second set of objectives includes the result set 1 objectives512and additional objectives (e.g., single objectives), including objective510, objective514, and objective515.

The second OWA is then applied to the second set of objectives (e.g., including set 1 objectives512, objective510, objective514, and objective515). For example, an OWA_ANY (“OR”) (e.g., with a low value for a) is calculated for the second set of objectives. To calculate the OWA for the second set of objectives, the objectives in set 2 are now ordered (e.g., from greatest to least), each objective is assigned a weight, and the OWA is calculated by multiplying the respective weight by the respective objective in the second set to output a value (e.g., OWA) of the second set of objectives. For example, set 1 objectives has a value of 0.89 (e.g., as calculated above), objective510has a value of 0.1, objective514has a value of 0.4, and objective515has a value of 0.2. Thus, the ordered value vector, from greatest value to least, comprises: set 1 objectives, objective514, objective515, and objective510, with values [0.89, 0.4, 0.2, 0.1] to be assigned weights [w5, w6, w7, w8]. Because this is an “OWA_ANY” calculation, and at least one objective has a high value, the overall score for combined objectives516is also high with a value of 0.82.

Taking the overall score for the combined objectives as 0.82 for this media content item (e.g., a first media content item), this score is then used by the media content provider in considering candidates for inclusion into a playlist. For example, if the first media content item has a score of 0.82, and a second media content item has a score of 0.6, the media content provider select the first media content item over the second media content item (for consideration with respect to the playlist) because it has the larger score.

FIG.5Billustrates another example of calculating a hierarchical ordered weighted average (HOWA). For example, a score is calculated for set 1 objectives536by calculating an ordered weighted average of objective520, objective522, objective524, and objective526. A score is calculated for set 2 objectives538by calculating an ordered weighted average of objective528, objective530, objective532, and objective534.

Next, at a second level within the hierarchy of ordered weighted averages, the scores for set 1 objectives536and set 2 objectives538are combined by calculating an OWA of set 1 objectives536and set 2 objectives538. In the second level of the hierarchy, another OWA is calculated by combining the ordered weighted average of set 1 objectives536and the ordered weighted average of set 2 objectives538(and any other objectives or ordered weighted average of other sets of objectives), to determine a score for combined objectives540(e.g., where the score for combined objectives540is the OWA that is calculated using the score of set 1 objectives536and the score of set 2 objectives538). Thus, the ordered weighted average is hierarchical because the system calculates an OWA based on the values for set 1 objectives536and set 2 objectives538, where each of those values were also determined by calculating the OWA for the set 1 objectives536and calculating the OWA for the set 2 objectives538.

It will be understood that for any of the OWA calculations described, OWA_MANY or OWA_ANY may be applied depending on the value chosen for the parameter α.

In some embodiments, the objectives include different types of objectives, such as engagement objectives (e.g., user clicks, complete listens, skips), satisfaction objectives (e.g., hearts and hands, percentage streamed), content characteristic objectives (e.g., relevance, user-track genre similarity, artist and genre affinity), and platform objectives (e.g., strategic value of content to platform or artist). These objectives comprise a mix of computed and predicted estimates, with the predicted estimates (e.g., engagement criterion) being the output of sophisticated large-capacity models trained specifically for these tasks.

In some embodiments, a hierarchical ordered weighted average is computed for each media content item in a plurality of media content items. The score that is calculated (e.g., combined objectives516or combined objectives540) for each media content item is then used to rank the media content items in the plurality of media content items. For example, the media content items with the highest scores are ranked highest.

In some embodiments, the media content items with the highest ranking(s) are selected and considered for inclusion into a playlist (e.g., by checking whether the individual candidates meet the constraints for a respective slot in the playlist). In some embodiments, the plurality of media content items are ordered, for playback, according to the combined objective score (e.g., from the largest score to the smallest score). In some embodiments, the combined objective score for each media content item in the plurality of media content items is calculated using a same hierarchical ordered weighted average structure (e.g., a first OWA calculated using OWA_ANY and a second OWA calculated using OWA_MANY).

FIG.6is a chart illustrating trade-offs between a plurality of objectives, in accordance with some embodiments. In some embodiments, the different objectives correspond to different parties. As illustrated inFIG.6, in some embodiments, respective objectives are conflicting (e.g., represented by a negative correlation), while other respective objectives are aligned (e.g., represented by a positive correlation, with the greatest alignment having a value of 1). In some embodiments, a system for providing automatically generated playlists balances objectives to maximize the overall satisfaction among the different parties. In some embodiments, the automatically generated playlist comprises a list of media content items. Thus, the system recommends a list of media content items that will provide the overall greatest satisfaction (e.g., by balancing the multiple objectives from multiple parties).

In some embodiments, the multiple parties comprise one or more of: a user, a media content provider, and an advertiser. Each of the multiple parties has one or more objectives. For example, as illustrated inFIG.6, each axis includes a plurality of user objectives (e.g., user engagement metrics) and a plurality of objectives for a non-user (e.g., a third party). For example, the non-user comprises a stakeholder. For example, the non-user objectives comprise “diversity (g)” (e.g., representing gender diversity (of artists) present in the recommended set) and “promotion” (e.g., promotion of a particular artist and/or type of media content), while “stream” (e.g., duration of streamed media content), “clicks” (e.g., selections of playlists), “songs played” (e.g., number of media content items played), and long stream are user objectives. It should be understood that the objectives illustrated inFIG.6are merely examples of possible objectives. For example, in some embodiments, other types of diversity objectives (such as an objective to represent artists with a smaller following, in addition to big-name artists). In some embodiments, a diversity objective can be applied to any attribute of the media content items (e.g., which may be specified as metadata for the media content item).

In some embodiments, user objectives are determined based on previous interactions between the user and the media content provider. For example, the media content provider tracks and/or stores (e.g., in a playback history) actions (e.g., selections) made by the user. In some embodiments, the user interaction information comprises a number of clicks (e.g., a number of times a media content item is selected), a number of streams, a number of content items played (e.g., a length of a playback session), or other user engagement metrics. In some embodiments, the media content provider stores a plurality of user engagement metrics. In some embodiments, the plurality of user engagement metrics are correlated (or uncorrelated).

For example,FIG.6illustrates that the user objectives tend to be positively correlated with each other, while the non-user objectives are negatively correlated with the user objectives, indicating that optimizing the selection model based on the user objectives alone does not satisfy the non-user objectives (and vice-versa). Thus, there is a trade-off between optimizing a model for user objectives or optimizing the model for non-user objectives.

FIGS.7A-7Care flow diagrams illustrating a method of sequencing a playlist of media items, in accordance with some embodiments. Method700may be performed (702) at a server system associated with a media providing service. The server system has one or more processors and memory storing one or more programs including instructions executable by the one or more processors. In some embodiments, the method700is performed by executing instructions stored in the memory (e.g., memory306,FIG.3) of the server system (e.g., media content server104). In some embodiments, the method700is performed by a combination of the server system (e.g., including media content server104and CDN106) and an electronic device (e.g., electronic device102,FIG.2). In some embodiments, the server system provides tracks (e.g., media items) for playback to the electronic device(s)102of the media content delivery system100.

The method includes receiving (704) a request to generate a playlist. The playlist includes a sequence of media items (e.g., once the generating operation708is complete, the playlist includes the sequence of media items). In some embodiments, the playlist is an automatically generated playlist (e.g., the playlist is generated without the user selecting individual media items). In some embodiments, the media items include audio media items (e.g., songs, spoken word), video media items (which typically include audio) or a combination of audio and video media items. In some embodiments, the request to generate a playlist is received in response to a user selecting the playlist in a media application (e.g., media application222,FIG.2). For example, in some embodiments, the playlist is generated in response to the user selecting a “My Daily Hits” playlist on their device. In some embodiments, the playlist is generated on a predetermined schedule (e.g., the “My Daily Hits” playlist is updated daily, at midnight). In some embodiments, the playlist is a personalized playlist for a particular user.

The method includes receiving (706) a plurality of constraints that define disqualification criteria for excluding media items from a respective slot in the sequence of media items (e.g., the server system receives, from a developer, list of constraints422,FIG.4B). Note that the list of constraints may be received before or after the request to generate the playlist, although it is typically received before. The plurality of constraints for the respective slot in the sequence of media items includes at least one constraint that is based on already-populated slots in the sequence of media items. In some embodiments, the at least one constraint is based at least in part on the state of the playlist that has been generated so far (e.g., the constraint is based on the sequencer state404,FIG.4A). That is to say, in some embodiments, the already-populated slots are fed back into the constraints, so that the next slot is filled with a media item that meets the constraints given the already-populated slots. Examples of such constraints include a constraint that two media items by the same artist should not be placed within a predefined number of slots of one another (e.g., within 5 slots of one another), or that the style of adjacent media items (e.g., tempo) should not differ by more than a predefined amount.

In some embodiments, the plurality of constraints includes at least one constraint that is independent of the already-populated slots in the sequence of media items (e.g., a global constraint). Examples of global constraints include those described with reference toFIG.4B.

The method includes generating (708) the playlist by sequentially populating each respective slot in the sequence of media items, including selecting, for the respective slot, a respective media item that meets the plurality of constraints for the respective slot in the sequence of media items. In some embodiments, the plurality of candidate media items consists of media items that meet the plurality of constraints for the respective slot in the sequence of media items. Stated another way, the server system populates the playlist by going slot-by-slot, starting with the first slot, and ensuring that each subsequent slot meets the constraints given the already-populated playlist (or at least meets the relaxed constraints, as described in more detail below). This process is also further described with reference toFIG.4A.

In some embodiments, generating the playlist by sequentially populating each respective slot in the sequence of media items further includes (710), for each respective slot in the sequence of media items: for each respective candidate media item of a plurality of candidate media items: generating a respective score for each of a plurality of objectives; and aggregating the respective scores for the plurality of objectives to produce an overall score for the respective candidate media item. The respective media item is selected for the respective slot based on the overall score for each candidate media item of the plurality of candidate media items (e.g., by selecting the media item with the highest aggregate score, or randomly selecting a media item from the ten media items with the highest scores).

In some embodiments, the plurality of objectives for the sequence of media items includes at least one objective having a corresponding score that is based on already-populated slots in the sequence of media items. In some embodiments, the score for the at least one objective is based at least in part on the state of the playlist that has been generated so far (e.g., sequencer state404,FIG.4A). For example, in some embodiments, the plurality of objectives includes an objective to provide a playlist with a high degree of gender diversity.

In some embodiments, the constraints are applied before scoring the candidate media items (e.g., the server system determines which candidates meet the constraints, then scores all of the candidates that meet the constraints and selects one of the candidates that meets the constraints using a selection strategy based on the scores).

In some embodiments, the constraints are applied after scoring the candidate media items. In some embodiments, the operation of selecting, for the respective slot, the respective media item that meets the plurality of constraints for the respective slot in the sequence of media items is performed after producing the overall score for each respective candidate media item of the plurality of candidate media items (e.g., all of the candidates are scored, then a particular candidate is selected based on the scores, and that particular candidate is tested against the criteria, as shown in the loop between reference numbers410and412inFIG.4A).

In some embodiments, the scores for the various objectives are aggregated using a weighted average. In some embodiments, the scores for the various objectives are aggregated using an ordered weighted average (e.g., a hierarchical ordered weighted average as described with reference toFIGS.5A-5B). To that end, in some embodiments, the plurality of objectives includes (712) a first set of objectives and a second set of objectives. Aggregating the respective scores for the plurality of objectives to produce an overall score for the respective candidate media item includes: applying a first ordered weighted average to the respective scores for the first set of objectives, to produce a first combined score for the first set of objectives; applying a second ordered weighted average to the respective scores for the second set of objectives, to produce a second combined score for the second set of objectives; and applying a third ordered weighted average to the combined score for the first set of objectives and the combined score for the second set of objectives.

In some embodiments, the plurality of objectives includes at least one artist-based objective (e.g., a promotion objective, wherein the objective produces higher objective-specific scores for artists that are being promoted).

In some embodiments, the plurality of objectives includes at least one listener objective. In some embodiments, the at least one listener objective is a predicted objective (e.g., an objective for which a value is calculated by predicting a user interaction, e.g., based on the user's listening history) Examples of such objectives include an objective that the user will maintain the listening session for a long time, or play a large number of tracks, or click to “like” the tracks).

In some embodiments, the plurality of constraints is (714) a subset, less than all, of a larger set of constraints for the respective slot in the sequence of media items. Each constraint of the larger set of constraints for the respective slot in the sequence of media items has a respective priority. Populating a respective slot in the sequence of media items includes: before selecting the respective media item that meets the plurality of constraints, determining that none of a plurality of candidate media items meets the larger set of constraints; relaxing, based on the respective priorities, the larger set of constraints to produce the plurality of constraints that is the subset, less than all, of the larger set of constraints (e.g., as described inFIG.4B); and selecting, for the respective slot, the respective media item that meets the plurality of constraints that is the subset, less than all, of the larger set of constraints.

In some embodiments, the larger set of constraints includes (716) multiple constraints that are independent of the already-populated slots in the sequence of media items. The method includes prior to generating the playlist by sequentially populating each respective slot in the sequence of media items, generating a table that includes information indicating the priority at which each of the plurality of candidate media items is disqualified from each respective slot in the sequence of media items (e.g., disqualification table420,FIG.4B). Relaxing, based on the respective priorities, the larger set of constraints to produce the plurality of constraints that is the subset, less than all, of the larger set of constraints includes referring to the table.

In some embodiments, the method includes, prior to receiving the request to generate the playlist, receiving an ordered list of the larger set of constraints. The constraints in the ordered list of the larger set of constraints are ordered according to priority. In some embodiments, the method includes populating a next respective slot in the sequence of media items, immediately following the respective slot, by applying the larger set of constraints. Stated another way, in some embodiments, the constraints are relaxed, as necessary, on a slot-by-slot basis. Once a slot is filled, the full set of constraints is used for the next slot (and again relaxed, as necessary), since constraints that are not met for one slot may be met for the next slot.

In some embodiments, the method includes: prior to generating the playlist by sequentially populating each respective slot in the sequence of media items, filtering an initial set of candidate media items using the at least one constraint that is independent of the already-populated slots in the sequence of media items to produce a filtered set of candidate items. Selecting, for each respective slot, a respective media item that meets the plurality of constraints for the respective slot in the sequence of media items includes selecting the respective media item from the filtered set of candidate items. In some embodiments, the filtering is based on the user's listening history (e.g., the full repository of candidate items is filtered down to 2000 tracks that are most similar to tracks that the user has listened to). In some embodiments, the filtering is based on genre or other metadata associated with the set of candidate items. For example, in response to a determination that a user tends to listen to folk music, the server system suggests a “Daily Folk” playlist, and thus the repository of candidate items is initially filtered such that media items with a folk genre are considered for the playlist. In some embodiments, the at least one constraint that is independent of the already-populated slots in the sequence of media items includes a constraint based on the user's listening session. For example, in some embodiments, the filtering includes removing media content items that the user has listened to within a predetermined amount of time (e.g., 60 minutes, 120 minutes, 180 minutes, or since the user opened the application and began streaming media).

The method includes providing (718) the playlist to a user of the media providing service. In some embodiments, providing the playlist to the user comprises providing URLs to the user's device (e.g., an electronic device102) from which the user's device can obtain the media items in the playlist. In some embodiments, providing the playlist to the user comprises providing information to the user's device with which to display the playlist (e.g., in media application222). In some embodiments, providing the playlist to the user comprises streaming the media items in the playlist to the user's device. In some embodiments, the user may select a presentation device distinct from the user's device (e.g., a speaker system) and providing the playlist to the user comprises streaming the media items in the playlist to the presentation device.

In some embodiments, the method includes while providing the playlist to the user of the media providing service: receiving (720) user feedback with respect to a particular media item in the playlist; and in response to receiving the user feedback with respect to the particular media item in the playlist, re-generating a remainder of the playlist by sequentially populating each remaining respective slot in the sequence of media items, including selecting, for the respective slot, a respective media item that meets the plurality of constraints for the respective slot in the sequence of media items. Stated another way, in some embodiments, the server system re-generates the remainder of the playlist in response to a user action with respect to the playlist (e.g., a skip, a “like”) as such user actions may change scores for the objectives used to populate the playlist.

The foregoing description, for purposes of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the embodiments to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles and their practical applications, to thereby enable others skilled in the art to best utilize the embodiments and various embodiments with various modifications as are suited to the particular use contemplated.