METHOD AND APPARATUS FOR PROGRAMMATICALLY SYNTHESIZING MULTIPLE SOURCES OF DATA FOR PROVIDING A RECOMMENDATION

[0001] This application claims the benefit of U.S. Provisional Patent Application No. 62/098,127, filed on Dec. 30, 2014, the entire contents of which are incorporated herein by reference.

[0002] Embodiments of the present invention relate generally to social media technologies and, more particularly, relate to a method, apparatus, and computer program product for programmatically synthesizing multiple sources of data for providing a recommendation based on an end user's affinity for a given item, when direct evidence about that affinity may be absent.

[0003] An important class of machine-learning algorithms having very broad application is recommendation engines. Recommendation engines take as input the historical preferences of a class of users for a class of items, and estimate the same users' preferences for items in the same class, where a given user has not yet expressed a preference for a given item. Recommendation engines have proven especially useful on Internet sites that offer to consumers such a large set of items that it would be practically impossible for a given consumer to determine manually which of the items the consumer preferred. In such cases the recommendation engine can infer from the preferences of similar consumers, or from consumers preferences for similar items, which items the target consumer is likely to prefer, and the Internet site can draw the target consumer's attention to these items.

[0004] For example, in one embodiment a social-networking Web site can recommend to a target consumer socially relevant businesses, products, and services that the consumer is likely to purchase. When a user is provided with a recommendation for a destination, product, or service that they ultimately end up liking, the social network service acquires a loyal and enthusiastic user and the user is more engaged often interacting with the physical world based on the recommendations.

[0005] While current services may provide search functionality enabling search results to be provided in response to a search request, and even may provide functionality for providing advertisements tailored to an individual, the algorithms are unable to estimate an end user's affinity for a given item when direct and indirect evidence about that affinity is absent. In other words, where current services may use content based systems, users may be continually provided with recommendations that are the same or very close to the same as those they have already indicated that they like. And where current services attempt to use collaborative filtering systems, the systems are unable to adequately provide a recommendation when the service lacks sufficient data relevant to that end user's preferences. Similarly, current systems cannot provide recommendation of an item when the item is new and no known preferences for the item are available.

[0006] Example embodiments of the invention described herein include a method of solving such a problem, referred to herein as a cold-start problem for collaborative filtering (CF) recommendation engines. In some examples, the cold-start problem occurs when the CF engine is required to produce a recommendation for a given end user, and either lacks sufficient data describing that end user's preferences, or lacks sufficient data describing other, potentially similar, end users' preferences, to compute the recommendation. A cold-start problem similarly occurs when a new item, destination, location or the like is added.

[0007] In some embodiments herein, an apparatus, method, and computer program product may be provided for programmatically synthesizing multiple sources of data bearing on user preferences for providing a recommendation of an item in response to a recommendation request.

[0008] A method may be provided for programmatically synthesizing multiple different sources of data bearing on user preferences for providing a recommendation of an item in response to a recommendation request, the method comprising receiving a recommendation request, the recommendation request comprising identification information indicative of a target user and a set of search terms, the set of search terms comprised of zero or more search terms, providing a search result, the search results generated by identifying whether the identification information is indicative of a new user, in an instance in which the identification information is indicative of a new user, querying a set of (new user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching, and in an instance in which the identification information is indicative of a known user, querying a set of (target user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching.

[0009] In some embodiments, the method may further comprise preceding reception of the recommendation request, accessing, for each of at least one known users and at least one item, all related expressed affinities, behavioral data, firmographic variables, and socio-demographic variables, and for at least one user-item pair, setting a user-item affinity to an expressed affinity in an instance in which the user provided an affinity for the item explicitly, calculating a computed affinity as a function of available behavioral data and setting the user-item affinity to the computed affinity in the absence of the user providing an affinity for the item explicitly and in an instance in which a number of instances of behavioral data meets a threshold, and in absence of an expressed affinity and a computed affinity, calculating an inferred affinity using one of a plurality of collaborative filtering algorithms and setting the user-item affinity to the inferred affinity.

[0010] In some embodiments, the method may further comprise calculating the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing an item-based collaborative filtering algorithm in an instance in which a number of user-item interactions meets a first predetermined threshold, calculating the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing a user-based collaborative filtering algorithm in an instance in which the number of user-item interactions fails to meet the first predetermined threshold, extending it to account for socio-demographic variables, calculating the inferred affinity for a user item pair, for user-item pairs in which the user is not modeled, utilizing a global average algorithm, and merging results into the set of (user, affinity) pairs, each item having a corresponding user-item pair, global averages having identification information indicative of a new user, known users having identification information indicative of a known user.

[0011] In some embodiments, the item is a destination, the calculating of the item-based collaborative filtering model comprising defining one or more user-destination affinities, wherein in an instance in which a user has given the destination a rating, normalizing the rating, and setting the normalized rating as the affinity, and wherein in an instance in which the user has not given the destination a rating, computing the affinity as a function of user site behaviors related to the destination, computing a similarity metric as a function of one or more firmographic or descriptive variables and known user-destination affinities, and generating a prediction for at least one unknown user-destination affinity as a function of the similarity metric.

[0012] In some embodiments, the item is an advertisement, the calculating of the item-based collaborative filtering model comprising computing one or more known user-advertisement click rates, a click rate computed for each user-advertisement pair for which the user has at least one impression the advertisement, computing a similarity metric as a function of known click rates and whether the advertising business is the same for two different advertisements, and generating predicted click rates for each user-advertisement pair in which the user has not had an impression of the advertisement as a function of the similarity metric.

[0013] In some embodiments, the item is a destination, the calculating of the user-based collaborative filtering model comprising computing user-destination affinities as a function of user site behaviors related to the destination, computing a similarity metric as a function of socio-demographic and user preference variables and known user-destination affinities, and generating a prediction for at least one unknown user-destination affinity using the similarity metric.

[0014] In some embodiments, the item is an advertisement, the calculating of the user-based collaborative filtering model comprising computing one or more known user-advertisement click rates, a click rate computed for each user-advertisement pair for which the user has at least one impression the advertisement, computing a similarity metric as a function of socio-demographic and user preference variables and known user-advertisement click rates, and generating a predicted user-advertisement click rate for each user-advertisement pair in which the user has not had an impression of the advertisement as a function of the similarity metric.

[0015] In some embodiments, the item is a destination, the computing of the global average model comprising calculating a mean of all known affinities for the item, scaling the mean based on the number of all known affinities, and setting the affinity for the item to the scaled mean.

[0016] In some embodiments, the item is an advertisement, the computing of the global average model comprising identifying a total number of clicks for the advertisement, identifying a total number of impression for the advertisement, and generating a user independent click rate for the advertisement using the total number of clicks and the total number of impressions, and setting the click rate for the advertisement to the user independent click rate.

[0017] In some embodiments, an apparatus may be provided for programmatically synthesizing multiple different sources of data bearing on user preferences for providing a recommendation of an item in response to a recommendation request, the apparatus comprising a processor including one or more processing devices configured to perform independently or in tandem to execute hard-coded functions or execute software instructions, a user interface, a communications module, and a memory comprising one or more volatile or non-volatile electronic storage devices storing computer-readable instructions configured to programmatically update budgeting data, target consumer profile data, and promotion component data, the computer-readable instructions being configured, when executed, to cause the processor to receive a recommendation request, the recommendation request comprising identification information indicative of a target user and a set of search terms, the set of search terms comprised of zero or more search terms, the target user, provide a search result, the search results generated by identifying whether the identification information is indicative of a new user, in an instance in which the identification information is indicative of a new user, querying a set of (new user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching, and in an instance in which the identification information is indicative of a known user, querying a set of (target user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching.

[0018] In some embodiments, the memory stores computer-readable instructions that, when executed, cause the processor to preceding reception of the recommendation request, access, for each of at least one known users and at least one item, all related expressed affinities, behavioral data, firmographic variables, and socio-demographic variables, for at least one user-item pair, set a user-item affinity to an expressed affinity in an instance in which the user provided an affinity for the item explicitly, calculate a computed affinity as a function of available behavioral data and set the user-item affinity to the computed affinity in the absence of the user providing an affinity for the item explicitly and in an instance in which a number of instances of behavioral data meets a threshold, and in absence of an expressed affinity and a computed affinity, calculate an inferred affinity using one of a plurality of collaborative filtering algorithms set the user-item affinity to the inferred affinity.

[0019] In some embodiments, the memory stores computer-readable instructions that, when executed, cause the processor to calculate the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing an item-based collaborative filtering algorithm in an instance in which a number of user-item interactions meets a first predetermined threshold, calculate the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing a user-based collaborative filtering algorithm in an instance in which the number of user-item interactions fails to meet the first predetermined threshold, extending it to account for socio-demographic variables, calculate the inferred affinity for a user item pair, for user-item pairs in which the user is not modeled, utilizing a global average algorithm, and merge results into the set of (user, affinity) pairs, each item having a corresponding user-item pair, global averages having identification information indicative of a new user, known users having identification information indicative of a known user.

[0020] In some embodiments, the item is a destination, and the memory stores computer-readable instructions that, when executed, cause the processor to, in the computing of the item-based collaborative filtering model define one or more user-destination affinities, wherein in an instance in which a user has given the destination a rating, normalizing the rating, and setting the normalized rating as the affinity, and wherein in an instance in which the user has not given the destination a rating, computing the affinity as a function of user site behaviors related to the destination, compute a similarity metric as a function of one or more firmographic or descriptive variables and known user-destination affinities, and generate a prediction for at least one unknown user-destination affinity as a function of the similarity metric.

[0021] In some embodiments, the item is an advertisement, and the memory stores computer-readable instructions that, when executed, cause the processor to, in the computing of the item-based collaborative filtering model compute one or more known user-advertisement click rates, a click rate computed for each user-advertisement pair for which the user has at least one impression the advertisement, compute a similarity metric as a function of known click rates and whether the advertising business is the same for two different advertisements, and generate predicted click rates for each user-advertisement pair in which the user has not had an impression of the advertisement as a function of the similarity metric.

[0022] In some embodiments, the item is a destination, and the memory stores computer-readable instructions that, when executed, cause the processor to, in the computing of the user-based collaborative filtering model compute user-destination affinities as a function of user site behaviors related to the destination, compute a similarity metric as a function of socio-demographic and user preference variables and known user-destination affinities, and generate a prediction for at least one unknown user-destination affinity using the similarity metric.

[0023] In some embodiments, the item is an advertisement, and the memory stores computer-readable instructions that, when executed, cause the processor to, in the computing of the user-based collaborative filtering model compute one or more known user-advertisement click rates, a click rate computed for each user-advertisement pair for which the user has at least one impression the advertisement, compute a similarity metric as a function of socio-demographic and user preference variables and known user-advertisement click rates, and generate a predicted user-advertisement click rate for each user-advertisement pair in which the user has not had an impression of the advertisement as a function of the similarity metric.

[0024] In some embodiments, the item is a destination, and the memory stores computer-readable instructions that, when executed, cause the processor to, in the computing of the global average collaborative filtering model calculate a mean of all known affinities for the item, scale the mean based on the number of all known affinities, and set the affinity for the item to the scaled mean.

[0025] In some embodiments, the item is an advertisement, and the memory stores computer-readable instructions that, when executed, cause the processor to, in the computing of the global average collaborative filtering model identify a total number of clicks for the advertisement, identify a total number of impression for the advertisement, and generate a user independent click rate for the advertisement using the total number of clicks and the total number of impressions, and set the click rate for the advertisement to the user independent click rate.

[0026] In some embodiments, a computer program product may be provided, the computer program product configured for programmatically synthesizing multiple different sources of data bearing on user preferences for providing a recommendation of an item in response to a recommendation request, the computer program product comprising at least one computer-readable storage medium having computer-executable program code instructions stored therein, the computer-executable program code instructions comprising program code instructions for receiving a recommendation request, the recommendation request comprising identification information indicative of a target user and a set of search terms, the set of search terms comprised of zero or more search terms, the target user, providing a search result, the search results generated by identifying whether the identification information is indicative of a new user, in an instance in which the identification information is indicative of a new user, querying a set of (new user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching, and in an instance in which the identification information is indicative of a known user, querying a set of (target user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching.

[0027] In some embodiments, the computer-executable program code instructions further comprise program code instructions for preceding reception of the recommendation request, accessing, for each of at least one known users and at least one item, all related expressed affinities, behavioral data, firmographic variables, and socio-demographic variables, for at least one user-item pair, setting a user-item affinity to an expressed affinity in an instance in which the user provided an affinity for the item explicitly, calculating a computed affinity as a function of available behavioral data and setting the user-item affinity to the computed affinity in the absence of the user providing an affinity for the item explicitly and in an instance in which a number of instances of behavioral data meets a threshold, and in absence of an expressed affinity and a computed affinity, calculating an inferred affinity using one of a plurality of collaborative filtering algorithms setting the user-item affinity to the inferred affinity.

[0028] In some embodiments, the computer-executable program code instructions further comprise program code instructions for calculating the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing an item-based collaborative filtering algorithm in an instance in which a number of user-item interactions meets a first predetermined threshold, calculating the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing a user-based collaborative filtering algorithm in an instance in which the number of user-item interactions fails to meet the first predetermined threshold, extending it to account for socio-demographic variables, calculating the inferred affinity for a user item pair, for user-item pairs in which the user is not modeled, utilizing a global average algorithm, and merging results into the set of (user, affinity) pairs, each item having a corresponding user-item pair, global averages having identification information indicative of a new user, known users having identification information indicative of a known user.

[0029] In some embodiments, the item is a destination, and wherein the computer-executable program code instructions further comprise program code instructions for, in the computing of the item-based collaborative filtering model defining one or more user-destination affinities, wherein in an instance in which a user has given the destination a rating, normalizing the rating, and setting the normalized rating as the affinity, and wherein in an instance in which the user has not given the destination a rating, computing the affinity as a function of user site behaviors related to the destination, computing a similarity metric as a function of one or more firmographic or descriptive variables and known user-destination affinities, and generating a prediction for at least one unknown user-destination affinity as a function of the similarity metric.

[0030] In some embodiments, the item is an advertisement, and wherein the computer-executable program code instructions further comprise program code instructions for, in the computing of the item-based collaborative filtering model computing one or more known user-advertisement click rates, a click rate computed for each user-advertisement pair for which the user has at least one impression the advertisement, computing a similarity metric as a function of known click rates and whether the advertising business is the same for two different advertisements, and generating predicted click rates for each user-advertisement pair in which the user has not had an impression of the advertisement as a function of the similarity metric.

[0031] In some embodiments, the item is a destination, and wherein the computer-executable program code instructions further comprise program code instructions for, in the computing of the user-based collaborative filtering model computing user-destination affinities as a function of user site behaviors related to the destination, computing a similarity metric as a function of socio-demographic and user preference variables and known user-destination affinities, and generating a prediction for at least one unknown user-destination affinity using the similarity metric.

[0032] In some embodiments, the item is an advertisement, and wherein the computer-executable program code instructions further comprise program code instructions for, in the computing of the user-based collaborative filtering model computing one or more known user-advertisement click rates, a click rate computed for each user-advertisement pair for which the user has at least one impression the advertisement, computing a similarity metric as a function of socio-demographic and user preference variables and known user-advertisement click rates, and generating a predicted user-advertisement click rate for each user-advertisement pair in which the user has not had an impression of the advertisement as a function of the similarity metric.

[0033] In some embodiments, the item is a destination and wherein the computer-executable program code instructions further comprise program code instructions for, in the computing of the global average collaborative filtering model calculating a mean of all known affinities for the item, scaling the mean based on the number of all known affinities, and setting the affinity for the item to the scaled mean.

[0034] In some embodiments, the item is an advertisement, and wherein the computer-executable program code instructions further comprise program code instructions for, in the computing of the global average collaborative filtering model identifying a total number of clicks for the advertisement, identifying a total number of impression for the advertisement, and generating a user independent click rate for the advertisement using the total number of clicks and the total number of impressions, and setting the click rate for the advertisement to the user independent click rate.

[0044] Example embodiments will now be described more fully hereinafter with reference to the accompanying drawings, in which some, but not all, embodiments are shown. Indeed, the embodiments may take many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will satisfy applicable legal requirements. Like reference numerals refer to like elements throughout. The terms “data,” “content,” “information,” and similar terms may be used interchangeably, according to some example embodiments, to refer to data capable of being transmitted, received, operated on, and/or stored. Moreover, the term “exemplary”, as may be used herein, is not provided to convey any qualitative assessment, but instead merely to convey an illustration of an example. Thus, use of any such terms should not be taken to limit the spirit and scope of embodiments of the present invention.

[0045] An apparatus, method, and computer program product described herein by way of a plurality of example embodiments is configured to solve a cold-start problem existing in collaborative filtering (CF) recommendation engines. In a preprocessing portion of an exemplary method described herein, the method may be configured to receive, access, or otherwise collect available expressed affinities, compute affinities from behavioral data where expressed affinities do not exist and sufficient behavioral data is available, compute the item-based CF model, extending it to account for content variables, compute the user-based CF model, extending it to account for socio-demographic variables, compute global averages, and merge the results into a single set of user, affinity, item) ordered triples.

[0046] The affinity in the ordered triple may be computed, in some examples, according to a process configured to elicit where possible an expressed affinity. Absent an expressed affinity, the process may be configured to gather behavioral evidence of a user's preference for an item; and compute affinity from the behavioral evidence. Subsequently, the process may be configured to use these expressed or computed (“empirical”) affinities as the basis for item-based CF to infer affinities for items lacking empirical affinities, where sufficient empirical affinities exist. Otherwise, the process may be configured to use available empirical affinities as the basis for user-based CF to infer affinities for items lacking empirical affinities, where sufficient empirical affinities do not exist. Otherwise, the process may be configured to use global averages over available empirical affinities.

[0047] At run time, when a recommendation request is received, the ordered triples may be used to induce an overall recommendation ranking for items matching the request's criteria, the criteria being, in some embodiments, text-search terms.

[0048] As such, example embodiments described herein provide a method for solving the cold-start problem for collaborative filtering (CF) recommendation engines, and is able to produce a recommendation for a given end user when lacking sufficient data describing that end user's preferences, or lacking sufficient data describing other end users' preferences. Furthermore, example embodiments described herein provide a method for enabling recommendation of an item when the item is new and no user preference for the item exists.

[0049] An affinity is an ordinal real number in an interval, e.g., [−1, 1], reflecting a user's degree of preference for, or aversion to, an item such as a destination, product, or service. As is described herein, affinity can be split into at least three types of affinities, namely expressed affinity, computed affinity, and/or inferred infinity. Expressed and computed affinities constitute empirical affinities, those derived directly from behavioral data relevant to estimating a user's preferences.

[0050] An expressed affinity is an affinity directly expressed by a user for an item. The expression may occur through a computer application's user interface (UI), for example the UI of an Internet social-networking service, whether rendered on a personal computer, tablet computer, mobile phone, etc. The web site may provide functionality enabling users to express affinities in a predefined range, e.g., [1, 10]. In some embodiments, the recommendation engine, discussed below, may be configured to receive an expressed affinity in the predefined range, and center and rescale these values into a fixed interval, e.g. [−1, 1.

[0051] A computed affinity is an affinity computed indirectly, based on a user's behavior or interaction with the social networking system, or in other embodiments, other web sites or mobile applications. The interactions may include favorites, follows, and activations (e.g., visits) through the UI. In some embodiments, for a given user and destination, variables I_fav and I_fol may be defined to be indicator (zero-one) variables indicating whether a user has, respectively, favorited and followed a destination. In some embodiments, variable A may take the form of a nonnegative-integer variable configured for counting how many activations the user has had at the destination in a time period (e.g., the most recent time period may be used). Further variables W_fav and W_fol, indicative of weights, may be included in determining a computed affinity in some examples. Each of these weights may be in a predefined range, e.g., [0, 1], as may be their sum. Finally, variable C_a may be a non-negative constant. Then the computed affinity may be calculated as:

W_fav*I_fav+W_fol*I_fol+(1−W_fav−W_fol)*(A/(C_a+A)

[0052] Thus, in an exemplary embodiment, any favoriting, following, or activation data may yield a computed affinity above the mean, that is, in the interval [0, 1]. In other words, in this exemplary embodiment, favoriting, following, or activation types of data indicate a degree of positive affinity.

[0053] Empirical affinity may be defined as the union of the sets of expressed and computed affinities. This will be further described below.

[0054] An inferred affinity is an affinity estimated by, for example, a recommendation module, using item or user-based collaborate filtering, for users in the data set. For new users not yet in the data set, global averages of empirical affinities may be utilized for calculating the inferred affinity.

[0055] In some embodiments, one of, for example, five methods may be provided for determining a user's affinity for an item: (1) expressed affinity; (2) computed affinity; (3) item-based CF; (4) user-based CF; and (5) global averages. The method may depend on what kind of evidence is available. In some embodiments, the above list may be in descending order of preference where more precise methods are preferred. Thus a recommendation module may be configured to first use expressed affinities where they exist; otherwise computed affinities where likes, follows, or activations exist; otherwise item-based CF where sufficient data exists; otherwise user-based CF; and otherwise global averages.

[0056] Content-based item attributes, as referred to herein, may be information indicative of one or more characteristics of items, that a recommendation engine may use to assess item similarity. For example, firmographic variables such as product type and price range characterize social destinations such as restaurants.

[0057] Sociodemographic user attributes, as referred to herein, may be information indicative of one or more characteristics of users, that a recommendation engine may use to assess user similarity. For example, variables such as age, gender, and personal income characterize social-network users.

[0058] While providers of recommendation engines exist in may diverse industries, each recommendation engine may face many of the same or similar problems. One such problem that each may face is that of a “cold start”. Specifically, recommendation engines may face three kinds of cold-start problems. First, an engine may have no affinity data for a new user (e.g., the user cold-start problem). Second, an engine may have no affinity data for a new item (e.g., the item cold-start problem). Third, an engine may have very little total affinity data (e.g., the system cold-start problem). In response, providers of such engines have spent a tremendous amount of time, money, manpower, and other resources in determining methods to solve the cold start problem by, for example, acquiring and utilizing affinity data.

[0059] General solutions to these problems usually involve hybrid engine architectures. To date, such architectures have mostly combined a single CF architecture with a single content-based architecture, where content-based attributes function as a surrogate for known affinities. Such approaches generally improve on single-architecture CF models, but fail to account for much of the available information, or to weigh different sources and kinds of information appropriately.

[0060] The present invention reaches beyond traditional hybrid models by combining five recommendation architectures—a behavioral model (empirical affinities, that is, expressed and computed affinities), two CF models (user and item based CF models using empirical affinities as their inputs), and two content-based models (user and item attributes). Moreover, the present invention combines CF and content-based models in a novel way that always uses content-based data to the degree that empirical affinity data do not overshadow the former.

[0061] In the context of social networking services, the result is a set of recommendation engines that produce item recommendations (such as destination and advertisement recommendations) based on all available information, including user attributes (sociodemographic variables), item attributes (such as firmographics for commercial destinations), and behavioral data (such as users' expressed affinities; text-search terms; likes, follows, and activations for destinations; and “click throughs” for previous advertisements produced by a given destination). By using all available information to recommend e.g., a social destination in the physical world, social networking system recommendation engines maximize the probability that each interaction between a user and a user interface in the virtual world will result in a positive social experience for the end user in the physical world. As such, programmatically providing functionality enabling provision of a recommendation of an item in response to a recommendation request by programmatically synthesizing multiple sources of data is a complex and difficult technological challenge to overcome for the provider of a recommendation engine.

[0062] In many cases, the inventors have determined that providers of recommendation engines, such as those related to social network services or medical industries, are constrained by technological obstacles unique to the electronic nature of the services provided, such as constraints on data storage, machine communication and processor resources. For example, a provider of a recommendation engine must continuously capture, maintain, and calculate information (e.g., expressed and computed affinities, (user, item, affinity) triples, etc.) that is up-to-date and accurate as well as provide, maintain, and add functionality that enables users to provide utilize the recommendation engine.

[0063] One specific problem unique to the electronic nature of the services provided is building and maintaining the technical infrastructure and user infrastructure. In an exemplary social networking context for example, the technical infrastructure being necessary to enable a robust social network and the user infrastructure being necessary for the mass of individual users necessary to provide a social network service. For example, a social network service must have many users, enough users to form social networks around various offerings, such as destinations, events, families, friends, and interests. To do this a social network service must provide the technical infrastructure such as individual profile pages, chat functionality, the ability to form and participate in groups, entourages, etc. Once the basics of social networks are met, the digital medium allows the mass of individuals to grow without geographic restriction. However, data must continuously be captured, stored, and verified. Each of the many functionalities must be maintained and updated as their use grows and new platforms are utilized.

[0064] Another specific problem unique to the electronic nature of the services provided herein arises in the provision and performance of the services on multiple devices. Users access social networks from laptops, tablets, cellular phones, and “phablets” these days.). Thus the social network service providers must be able to provide functionality, including the coding, maintaining, updating, and migrating of each functionality, on each device.

[0065] Finally, given the volume of electronic post data and the volume of related data, such as advertisement data, social networks often provide imperfect or irrelevant information to a user or are unable to provide specific information, notably when a user or the information, such as a product, service, or ad, is new. This problem is not found in the physical world as users are more able to filter content, such as by navigating a newspaper or selecting a news program. In social networks, no such filter is available.

[0066] In response to these problems and other problems, the inventors have identified methods and apparatuses for providing functionality for providing a recommendation of an item (e.g., destination, advertisement, event, etc.) in response to a recommendation request by programmatically synthesizing all available sources of data that is unlike current technologic functionality offered by social network services or elsewhere so as to encourage user consumption of the offered item, for example attendance at a destination, event, etc.). That is, embodiments of the present invention as described herein serve to offer improved services such as programmatically synthesizing each of a plurality of sources of data bearing on user preferences for selecting an item to recommend and providing a recommendation of the item. The concept of combining global averages, user-based CF, item-based CF, behavioral modeling, expressed preferences, and content-based (e.g. socio-demographic and firmographic) recommendations into a single hybrid recommender distinguishes the system and method described herein.

[0067] The programmatic synthesizing of multiple sources of data in the process of recommending an item enables example embodiments of the present invention to overcome the cold start problem encountered by known collaborative filtering engines. In one exemplary embodiment, asocial network service may programmatically synthesize each of a plurality of sources of data bearing on user preferences for programmatically and in real-time, providing recommendations for a given end user when lacking either sufficient data describing that end user's preferences or sufficient data describing other end users' preferences. In other words, the social network service may programmatically and in real time provide and/or display relevant material.

[0068] Methods, apparatuses, and computer program products of example embodiments of the present invention may be embodied by any of a variety of devices. For example, the method, apparatus, and computer program product of an example embodiment may be embodied by a networked device, such as a server or other network entity, configured to communicate with one or more devices, such as one or more client devices. Additionally or alternatively, the computing device may include fixed computing devices, such as a personal computer or a computer workstation. Still further, example embodiments may be embodied by any of a variety of mobile terminals, such as a portable digital assistant (PDA), mobile telephone, smartphone, laptop computer, tablet computer, or any combination of the aforementioned devices.

[0069] FIG. 1 is an example block diagram of example components of an example social media environment 100. In some example embodiments, the social media environment 100 comprises one or more users 102a-102n, one or more items (e.g., destinations (e.g., establishments, businesses), advertisements, entertainers, promoters, etc.) 104a-104n, and/or a recommendation module 106. The recommendation module 106 may take the form of, for example, a code module, a component, circuitry and/or the like. The components of the example social media environment 100 are configured to provide various logic (e.g., code, instructions, functions, routines and/or the like) and/or services related to the recommendation module 106 and its components.

[0070] FIG. 1 is an example block diagram of example components of an example social media environment 100. In some example embodiments, the social media environment 100 comprises one or more users 102a-102n, one or more items (e.g., destinations (e.g., establishments, businesses), advertisements, entertainers, promoters, etc.) 104a-104n, and/or a recommendation module 106. The recommendation module 106 may take the form of, for example, a code module, a component, circuitry and/or the like. The components of the example social media environment 100 are configured to provide various logic (e.g., code, instructions, functions, routines and/or the like) and/or services related to the recommendation module 106 and its components.

[0071] In some embodiments, the item-based collaborative filtering module 110 may be configured to be used when a number of user-to-item pairings meet a predetermined threshold. For example, in one use embodiment, recommendation module 106 may be configured to be a destination recommendation module, and the item-based collaborative filtering module 110 may be configured to be used in or called by the recommendation module, when a user (e.g., one of the one or more users 102a-102n) has known interactions with at least N Destinations (e.g., one or more items 104a-104n), N being a configurable parameter. Furthermore, in some embodiments, recommendation module 106 may be configured to be an advertisement recommendation module, and the item-based collaborative filtering module 110 may be configured to be used in or called by the advertisement recommendation module when a user (e.g., one of the one or more users 102a-102n) has recorded clicks on at least N different Advertisements, again N is a configurable parameter.

[0072] In some embodiments, the user-based collaborative filtering module 112 may be configured to be used when a number of user-to-item pairings fails to meet a predetermined threshold. For example, in one use embodiment, recommendation module 106 may be configured to be a destination recommendation module, the user-based collaborative filtering module 112 may be configured to be used in or called by the destination recommendation module when a user (e.g., one of the one or more users 102a-102n) has less than N empirical affinities, the user-based recommender may be used to predict unknown affinities, N is a configurable parameter. Furthermore, in some embodiments, recommendation module 106 may be configured to be an advertisement destination recommendation module, the item-based collaborative filtering module 110 may be configured to be used in or called by the advertisement recommendation module when a user (e.g., one of the one or more users 102a-102n) clicks on less than N advertisements, the user-based recommendation model may be used to predict unknown click rates, again N is a configurable parameter.

[0073] The prediction of unknown affinities as used herein comprises the ordering of items (e.g., destinations and advertisements), in descending order of predicted affinity. In other words, affinity, such as the affinity of a user for a destination or advertisement, is an ordinal concept; and, as such, may be used to rank items. In some embodiments, the magnitude has no absolute meaning. In particular, the magnitude is not a probability or a rate.

[0074] In some embodiments, the global average module 114 is configured to be used only in the case of new users (e.g., one or more of the one or more users 102a-102n) that have registered on the site since the last batch collaborative filtering run and therefore will not receive user-specific predictions until a next batch run of the algorithm. In some examples, the global average module 114 may be used in an instance in which new destinations, advertisements, events, experiences or the like are added.

[0075] In some embodiments, recommendation module 106 may be configured or otherwise embodied as a destination recommendation module, to provide or otherwise output destination recommendations. The destination recommendation module may be configured to generate user-specific rankings of destinations based on known and/or inferred preferences (“affinities”). As described above, known affinities may be computed as a function of known user interactions with a destination, for example, within the social network service or environment. In some embodiments, the social network service may provide functionality for rating a destination, setting a destination as a favorite, following a destination, accepting/executing a discount offered by a destination, activating at a destination, or the like, each of which may be configured to factor into any output destination recommendations.

[0076] In some embodiments, recommendation module 106, and in particular the destination recommendation model that may be stored, executed, or provided therein, may be comprised of one or more, but in some examples four independent recommendation models. In some embodiments, the behavioral model 108 may be used when expressed or computer affinities are available. The behavioral model 108 may be configured to combine the expressed and computed into a single class of empirical (behavioral) affinities. The output of the behavioral model 108 may be configured to serve as input(s) to the one or more of the CF and global-average models. In some embodiments, two models, the item-based CF model and the user-based CF model, may be configured for predicting preference of, calculating or otherwise determining unknown affinities for a given user, the choice of which may depend on the amount of known affinity data available for the user. The third model, the global average model, may be a degenerate case of user-based CF, where a “neighborhood” of users “similar” to the target user may be the entire user population, and where degree of similarity is not used to weigh the population's empirical affinities. This model may be configured to be used depending on how recently the user registered.

[0077] As will be described further in FIG. 2A, the recommendation module 106 may comprise an item-based collaborative filtering model 110. The item-based collaborative filtering model 110 may be used when a user has known interactions with at least N destinations, N being a configurable parameter. The recommendation module 106 may further be configured to comprise a user-based collaborative filtering model 112, which will be described in FIG. 3A. For a user with less than N empirical destination affinities, the user-based recommendation model 112 may be used to predict unknown affinities.

[0078] The item-based collaborative filtering model 110 may be utilized to addresses system user-specific “cold starts” in which new users do not have enough known ratings to generate meaningful recommendations using the item-based collaborative filtering model 110. In some embodiments, if the number of empirical affinities for a given destination is less than a predefined threshold, the recommendation model 106 may utilize a distance metric configured to shift weight from content evidence to affinity evidence, to the degree the quantity of affinity evidence overshadows the quantity of content evidence. The recommendation module 106 may further be configured to comprise a global average model, which will be described in FIG. 4A. The global average module 114 may be used in instances in which a new user (e.g., a user that has registered on the site since, for example, the last batch collaborative filtering run and as such will not receive user-specific predictions until the next batch run of the algorithm) is provided.

[0079] In some embodiments, recommendation module 106 may be configured as an advertisement recommendation module, and further be configured to provide or otherwise output advertisement (or ‘ad’) recommendations. The advertisement recommendation module may be configured to generate user-specific rankings of ads to be shown to users based on empirical affinities for the advertisements, such as the number of impressions until the first click or, in some embodiments, the ratio of clicks to impressions). In some embodiments, when the system requests a ranking of candidate ads for a given location on, for example, the site for a specified user, the advertisement recommendation module may return a sorting based on the overall ad ranking for that user.

[0080] In some embodiments, recommendation module 106, and in particular the advertisement recommendation model that may be stored, executed, or otherwise provided therein, may be comprised of one or more, but preferably four recommendation models. In some embodiments, the behavioral model may be used when expressed or computer click rates are available and the results may be used when available as the click rates (direct evidence). The output of the behavioral model may be configured to serve as input to the one or more of the CF and global-average models. In some embodiments, the item-based CF model and the user-based CF model, may be configured for, ranking unknown click rates, the model used to rank unknown click rates for a given user depending on the amount of known user click data that is available, and another used based on how recently the user registered. The third model, the global average model, may be a degenerate case of user-based CF, where a “neighborhood” of users “similar” to the target user may be the entire user population, and where degree of similarity is not used to weigh the population's empirical affinities. This model may be configured for use with a new user.

[0081] As will be described further with reference to FIG. 2B, the recommendation module 106 may comprise an item-based collaborative filtering model 110. In some embodiments, the item-based collaborative filtering model 110 may be configured for use when a user has recorded clicks on at least N different advertisements, (e.g., a known click rate can be determined), N being a configurable parameter. The recommendation module 106 may further be configured to comprise a user-based collaborative filtering model, which will be described in FIG. 3B. The user-based collaborative filtering model 112 may be configured for use with a user having recorded clicks on less than N advertisements, the user-based recommendation model configured to rank advertisements based on a predicted affinity. The item-based collaborative filtering model 110 may be utilized to addresses system user-specific “cold starts” in which new users do not have enough recorded impressions and clicks to generate meaningful recommendations using the item-based collaborative filtering model 110. The recommendation module 106 may further be configured to comprise a global average model, which will be described in FIG. 4C. The global average model may be configured for use with a new user (e.g., users that have registered on the site since the last batch collaborative filtering run and therefore may not receive user-specific predictions until the next batch run of the algorithm). Note that parameter N is a distinct parameter from the parameter described with reference to the destination recommendation model.

[0082] In view of the system described with reference to FIG. 1, FIGS. 2A and 2B show flowcharts illustrating example processes that may be performed by the item-based collaborative filtering module 110 in accordance with some example embodiments of the present invention. FIG. 2A is directed to destination recommendation model embodiment and FIG. 2B is directed to an advertisement recommendation model embodiment of the item-based collaborative filtering module 110.

[0083] FIGS. 3A and 3B show flowcharts illustrating example processes that may be performed by user-based collaborative filtering module 112 in accordance with some example embodiments of the present invention. FIG. 3A is directed to destination recommendation model embodiment and FIG. 3B is directed to an advertisement recommendation model embodiment.

[0084] FIGS. 4A and 4B show flowcharts illustrating example processes that may be performed by the global average module 114 in accordance with some example embodiments of the present invention. FIG. 4A is directed to destination recommendation embodiment and FIG. 4B is directed to an advertisement recommendation embodiment.

[0085] In some embodiments, the models may be partitioned. For example, in a social networking context, there may be a difference between how the advertisement and destination recommendation models use location information or data (e.g., a particular neighborhood or city). That is, in some exemplary embodiments, the destination recommendation module may be configured such that each location may be treated or otherwise utilized effectively as an independent model, each location having a separate, location-specific model. For example, each city may have its own model of user affinities for destinations in the city. The logic may be that a large majority of user-destination interactions are anticipated to occur between users and destinations in the same social city. In contrast, advertisements need not be geographically limited. Thus the advertisement recommendation model may not explicitly partition the model, although, in some embodiments, it may. In some embodiments, for example, the computational demands of the user-based recommendation model described in FIG. 4B may be configured for partitioning to be implemented when the site-wide number of users reaches a threshold.

[0086] In an item-based collaborative filtering model, a pairwise item (e.g., a destination) similarity may be quantified based on how similar users tend to rate the two items. A sorting of items (destinations, ads, etc.) in descending order of an inferred affinity may then be generated for user-destination pairs with no known interactions based on the user's known affinities for similar items. Hybrid item-based collaborative filtering may follow the same high-level logic but may include content-based variables such as firmographics and content tagging in calculating a similarity metric.

[0087] In some embodiments, the item-based recommendation module may require a certain density of known preferences for a user in order to be more effective than user-based recommendation or global averaging. Thus the item-based recommendation module may, in some embodiments, only be used when the user has known affinities for at least N destinations, where N is a configurable model parameter.

[0088] The item-based recommendation module may be configured to predict a preference order and/or generate a ranking of items in descending order of an inferred affinity, for all, or some portion of, user-destination pairs in a particular location (e.g., each user city) with an unknown preference where the user meets the minimum known affinity threshold. For each user, the predicted preference order and the known affinities may then be used to generate a user-specific preference ranking over all destinations.

[0089] FIG. 2A is a flowchart illustrating an example process that may be performed by the item-based collaborative filtering module 110 in accordance with some example embodiments (e.g., a destination recommendation embodiment) of the present invention. In some embodiments, the item-based collaborative filtering module may be configured as a hybrid item-based collaborative filtering model. The item-based collaborative filtering module may be comprised of one or more, but preferably three sub-models, which are described below. In some examples, the models may include a pair of a user (ST), which is a user of the social network, and a destination (DN).

[0090] The first of the three sub-models, the affinity model may define ST-DN affinities. The second of the three sub-models is the destination similarity model which may compute a similarity metric as a function of firmographic/descriptive variables and known ST-DN affinities. The third of the three sub-models is collaborative filtering model proper and uses the destination similarities to generate a ranking, in order of inferred affinity, of ST-DN affinities.

[0091] In some embodiments, the collaborative filtering model may be run as a batch job with the frequency of a batch update set as a parameter (e.g., 1-4 times daily in production). The similarity model may, in some embodiments, require affinities, and additionally in some embodiments, firmographic data, as an input, and the collaborative filtering model may, in some embodiments, require both affinities and similarities as inputs. Many of the affinities/similarities are likely to persist between batch runs and may not need to be recomputed. Affinities/similarities that do change can be updated between batch runs either through continuous updating (monitor for triggering events and immediately, or near immediate, recomputed) or in more frequent batch updates between the collaborative filtering batch runs. This may reduce the peak processing load during full batch updates but may increase average processing loads due to some affinity/similarity updates being overwritten by additional updates prior to the next batch run. This tradeoff may be evaluated in the implementation of the model.

[0092] 1. Affinity Model

[0093] The affinity model may be configured to assign affinities, (e.g., between −1 and 1) for ST-DN pairs in which there are known site interactions. Accordingly, as is shown in operation 205, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the processor 803, or the like, for defining each of one or more user-destination (ST-DN) affinities. In some embodiments, in an instance in which the ST has given the DN a rating, the rating may be used. In some embodiments, the given rating may be normalized, and the apparatus may then be configured for setting the normalized rating as the affinity. In contrast, in an instance in which the user has not given the destination a rating, the apparatus may be configured to compute an affinity as a function of ST site behaviors related to the DN, such as for example, follows, favorites, activations at destinations, acceptance of deals, etc. That is, in some embodiments, if the ST has, for example, reviewed a particular destination and given it an overall experience rating, the model may assign a normalized rating as the affinity. Otherwise, the model may be configured to process a range of logged ST-DN interactions into a computed affinity that attempts to infer how the ST would rate the DN based on other logged behaviors. ST-DN pairs with no recorded action may be assigned a null affinity to indicate that the preference order will need to be predicted by the collaborative filtering sub-model.

[0094] In some embodiments, many of the affinities are likely to remain static between consecutive batch runs. Thus the known affinities may be stored between batches and updated as needed. A (ST,DN) pair may be flagged for update when one of the following interactions occurs between that ST and DN: (1) ST adds/updates rating for DN; (2) ST has not rated the DN; and (3) one of (a) ST adds/removes DN as a favorite; or (b) ST follows/unfollows DN, or (c) ST activates at DN, (d) or ST accepts a deal from DN, or (e) ST activation at DN or acceptance of deal from DN “ages out” (e.g., becomes more than 15 months old).

[0095] In some embodiments, affinities for flagged (ST,DN) pairs may be updated continuously by triggering the affinity model when a pair is flagged, or, in some embodiments, the flagged (ST,DN) pairs may be updated in batches. If updated in batches, in some embodiments, the affinity batch updates must occur with at least as much frequency as the collaborative filtering sub-model batch updates.

[0096] For a given (ST,DN) pair, the affinity aff(ST, DN) may be computed as a function of the known interactions between the ST and DN. There are one or more, but preferably three possible cases:

[0097] 1) If the ST has not rated, followed, favorited, activated at, or accepted a deal offered by the DN then set aff(ST, DN)=null to indicate that this affinity is unknown and its ranking in a preference order of the items must be predicted by the collaborative filtering model.

[0098] 2) If the ST has given the DN an overall experience rating of, for example, 1-10 in a review then the affinity may be set to the normalized ST-DN rating. In some embodiments, if r(ST, DN) may be defined as the rating given by User ST to Destination DN and r_ST as the mean overall experience rating given by ST across all rated destinations. Then set

$\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)=\{\begin{array}{cc}\frac{r\left(\mathrm{ST},\mathrm{DN}\right)-{\stackrel{\_}{r}}_{\mathrm{ST}}}{10-{\stackrel{\_}{r}}_{\mathrm{ST}}}& \mathrm{if}r\left(\mathrm{ST},\mathrm{DN}\right)>{\stackrel{\_}{r}}_{\mathrm{ST}};\\ \frac{{\stackrel{\_}{r}}_{\mathrm{ST}}-r\left(\mathrm{ST},\mathrm{DN}\right)}{{\stackrel{\_}{r}}_{\mathrm{ST}}-1}& \mathrm{if}r\left(\mathrm{ST},\mathrm{DN}\right)<{\stackrel{\_}{r}}_{\mathrm{ST}};\\ 0& \mathrm{if}r\left(\mathrm{ST},\mathrm{DN}\right)={\stackrel{\_}{r}}_{\mathrm{ST}}.\end{array}$

[0099] Note, in some examples the last case may be explicitly defined to account for the cases where all known user ratings are 10 or all known user ratings are 1.

[0100] 3) Otherwise, compute the affinity as a function of the known ST-DN interactions. Define, in some examples, the following configurable parameters:

• • [0101] W_fav: weight for favorites
  • [0102] W_fol: weight for follows (likely that W_fol<W_fav)
  • [0103] W_a: weight for activations

[0104] where 0<W_fav,W_fol,W_a<1 and W_fav+W_fol+W_a=1.

[0105] In some embodiments, the following functions may also defined:

$x_{\mathrm{fav}}\left(\mathrm{ST},\mathrm{DN}\right)=\{\begin{array}{cc}1& \mathrm{if}\mathrm{DN}\mathrm{in}\mathrm{ST}\mathrm{favorites}\\ 0& \mathrm{otherwise}\end{array}x_{\mathrm{fol}}\left(\mathrm{ST},\mathrm{DN}\right)=\{\begin{array}{cc}1& \mathrm{if}\mathrm{ST}\mathrm{following}\mathrm{DN}\\ 0& \mathrm{otherwise}\end{array}x_a\left(\mathrm{ST},\mathrm{DN}\right)=\left(\begin{array}{c}\mathrm{count}\mathrm{of}\mathrm{ST}\mathrm{activations}\mathrm{at}\mathrm{DN}\mathrm{and}\\ \mathrm{acceptance}\mathrm{of}\mathrm{deals}\mathrm{from}\mathrm{DN}\\ \mathrm{over}\mathrm{preceding}15\mathrm{months}\end{array}\right)$

[0106] Then the ST-DN affinity may be computed as either of the following equations:

$\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)=W_{\mathrm{fav}}x_{\mathrm{fav}}\left(\mathrm{ST},\mathrm{DN}\right)+W_{\mathrm{fol}}x_{\mathrm{fol}}\left(\mathrm{ST},\mathrm{DN}\right)+W_a\frac{x_a\left(\mathrm{ST},\mathrm{DN}\right)}{C+x_a\left(\mathrm{ST},\mathrm{DN}\right)}$ $\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)=W_{\mathrm{fav}}x_{\mathrm{fav}}\left(\mathrm{ST},\mathrm{DN}\right)+W_{\mathrm{fol}}x_{\mathrm{fol}}\left(\mathrm{ST},\mathrm{DN}\right)+W_a\left(1-{}^{\frac{5x_a\left(\mathrm{ST},\mathrm{DN}\right)}{C}}\right)$

[0107] where C is a configurable constant with a default value, for example 1.5. Different affinity models may be used, and may involve other parameters. In general, the appropriate value for these configuration parameters is whatever value minimizes affinity error. This value can be determined experimentally by parameter estimation over past affinity data. Note that in this exemplary embodiment, the affinity will be in the interval [0,1].

[0108] 2. Destination Similarity Model

[0109] The Destination similarity model may be configured to compute pairwise similarities between Destinations. As is shown in operation 210, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the processor 803, or the like, for computing a similarity metric. In some embodiments, the similarity metric may be computed as a function of firmographic/descriptive variables and known ST-DN affinities. For example, for each of one or more pairs of destinations, a similarity metric may be computed. Where a user has not given a particular destination a rating, a rating may be inferred based on a rating that the user has given a similar destination.

[0110] Similarity may be computed as a modified cosine similarity between the extended firmographic and affinity vectors of the destinations. The model may be constructed in such a way that as the number of known affinities increases for a destination, the relative weight of affinity similarity naturally increases compared to firmographic similarity in the overall similarity computation.

[0111] In some embodiments, the item-based filtering model may require that similarities be computed for all DN pairs. In some embodiments, many similarities are likely to remain unchanged between consecutive batch runs of the filtering model. Therefore, the similarities may be stored between batch runs and be computed/recomputed only as required. A DN may be flagged as needing to have its similarities updated if any of the following occur: (1)—The DN is new to the system (i.e., does not have any defined or otherwise inferred similarities); (2)—The categories, tags, or neighborhoods in the DN profile have been updated; (3) One or more (ST,DN) affinities have been updated for this DN.

[0112] In some embodiments, when a DN is flagged, the similarities between that DN and all other DNs in the same user city may be recomputed. In some embodiments, similarities are symmetric, (e.g., sim(DN1,DN2)=sim(DN2,DN1)). Thus it is important that recomputed similarities be updated for both pair orderings if they are stored separately.

[0113] As in the case of affinities, flagged DNs may be updated continuously by triggering the similarity model immediately when a DN is flagged, or the flagged DNs can be updated in batches. The update frequency may be no more frequent than the affinity update frequency and no less frequent than the collaborative filtering batch frequency in some examples.

[0114] In some examples, the system may be configured to determine the similarity between two destinations. The similarity between two destinations DN1 and DN2 may be computed as a cosine-like similarity function over a set of pure cosine similarity sub-functions. The similarity may be a real number on the interval, for example, [−1,1] with a higher value indicating greater similarity.

[0115] For the firmographic dimensions, the sub-functions are of similar form:

${\mathrm{sim}}_{\mathrm{tags}}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)=\frac{{\mathrm{DN}}_1\mathrm{profile}\mathrm{tags}\bigcap {\mathrm{DN}}_2\mathrm{profile}\mathrm{tags}}{\sqrt{{\mathrm{DN}}_1\mathrm{profile}\mathrm{tags}*{\mathrm{DN}}_2\mathrm{profile}\mathrm{tags}}}$ ${\mathrm{sim}}_{\mathrm{cat}}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)=\frac{{\mathrm{DN}}_1\mathrm{factual}\mathrm{categories}\bigcap {\mathrm{DN}}_2\mathrm{factual}\mathrm{categories}}{\sqrt{{\mathrm{DN}}_1\mathrm{factual}\mathrm{categories}*{\mathrm{DN}}_2\mathrm{factual}\mathrm{categories}}}$ ${\mathrm{sim}}_{\mathrm{nbd}}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)=\frac{{\mathrm{DN}}_1\mathrm{neighborhood}\mathrm{tags}\bigcap {\mathrm{DN}}_2\mathrm{neighborhood}\mathrm{tags}}{\sqrt{{\mathrm{DN}}_1\mathrm{neighborhood}\mathrm{tags}*{\mathrm{DN}}_2\mathrm{neighborhood}\mathrm{tags}}}$ $\mathrm{sim}\left(a,b\right)=\frac{a\bigcap b}{a\bigcup b}$

[0116] Here, the vertical bars represent the set size function. Thus the sub-functions may be computed as the number of common tags/categories between DN1 and DN2 divided by the square root of the product of the number of tags in each destination's profile. If either DN does not have any profile tags, factual categories, or neighborhood tags then the denominator will be zero in the corresponding similarity component, and the component ratio will be undefined. In this case, the similarity may be set to zero. As one of ordinary skill would appreciate, other similarity functions may be used. Moreover, regarding design assumptions, note the importance of the form's upper/lower bounds ([−1 to 1] or [0 to 1]) and its algebraic properties (symmetry, monotonicity, intransitivity) because these properties may dictate how often the scores may be recalculated.

[0117] The profile tags and neighborhood tags may, in some embodiments, be used directly for the above sub-functions. The factual categories may be expanded. For example, the factual category (Social,Restaurant,Italian) may be expanded into one or more, but preferably three categories:

[0118] (Social),(Social,Restaurant),(Social,Restaurant,Italian)

[0119] For Destinations with multiple factual categories, any duplicates resulting from the expansion of the categories may be removed. For example, a restaurant with the two categories (Social,Restaurant,Italian) and (Social,Restaurant,Greek) would, after removing duplicates, have expanded categories:

[0120] (Social),(Social,Restaurant),(Social,Restaurant,Italian),(Social,Restaurant,Greek)

[0121] The expanded factual categories are the basis for computing sim_cat( ).

[0122] The final similarity measure may be a function of the firmographic similarities defined above and the known affinities across all users for each Destination. V_DN may be defined to be the vector of (ST,DN) affinities across all users ST in the city. If the affinity is null (i.e., unknown) then the corresponding element of the vector may be set to zero. The overall similarity function may then be defined to be:

$\mathrm{sim}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)=\frac{W_f\left(\begin{array}{c}{\mathrm{sim}}_{\mathrm{tags}}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)+{\mathrm{sim}}_{\mathrm{cat}}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)+\\ {\mathrm{sim}}_{\mathrm{nbd}}\left({\mathrm{DN}}_1,{\mathrm{DN}}_2\right)\end{array}\right)+V_{{\mathrm{DN}}_1}·V_{{\mathrm{DN}}_2}}{\sqrt{3W_f+{\Sigma }_{\mathrm{ST}}\left({\mathrm{aff}\left(\mathrm{ST},{\mathrm{DN}}_1\right)}^2\right)}*\sqrt{3W_f+{\Sigma }_{\mathrm{ST}}\left({\mathrm{aff}\left(\mathrm{ST},{\mathrm{DN}}_2\right)}^2\right)}}$

[0123] where V_DN1·V_DN2 may be the dot-product of the rating vectors:

$V_{{\mathrm{DN}}_1}·V_{{\mathrm{DN}}_2}=\sum _{\mathrm{ST}}\left(\mathrm{aff}\left(\mathrm{ST},{\mathrm{DN}}_1\right)*\mathrm{aff}\left(\mathrm{ST},{\mathrm{DN}}_2\right)\right)$

[0124] The above similarity function is similar to a cosine similarity but has been modified to account differently for firmographic and affinity-based components of the similarity. As the number of known affinities grows for DN1 and/or DN2, the length of the affinity vectors and thus the denominator of sim(DN₁, DN₂) will increase. The contribution of the firmographic variables to the numerator has a fixed maximum (each sub-function is between zero and one), and thus the influence of firmographic similarity will decrease as the length of the two vectors increases. This may naturally shift influence from firmographic similarity to affinity similarity as the number of known affinities for a destination increases. Technically, if the known affinities' values are all zero, or if they get smaller at a sufficiently high rate, the convergence this paragraph describes may not occur. It suffices mathematically to assume that a subsequence of known affinities in each vector have magnitude greater than some constant, so that once enough affinities are known, the vectors' lengths are greater than any given value.

[0125] In some embodiments, non-negative weight W_f may be a configurable parameter that may adjust the rate at which the affinity similarity dominates firmographic similarity. Higher values of W_f may put greater weight on the firmographic similarity components, which means that a higher number of known affinities is required to reach a similar balance between firmographic and affinity-based similarity as for a lower value of W_f. Note that W_f is the length of an affinity dot product necessary before firmographics data stops dominating the function. For example, in the event that there is no user rating history, firmographic similarity dominates by default. If a user gives the maximum rating to DN1 and DN2, this is the same contribution as perfect firmographic similarity if W_f=1. The amount of weight given to perfect firmographic similarity is W_f=X, and as such it is weighted the same as if X users all gave DN1 and DN2 the maximum rating

[0126] As noted above, for a flagged DN the similarity to each other DN must be updated. Each pairwise similarity may be computed independently. Whether similarity updates are performed continuously or in batches, computation for these pairwise similarities can be distributed (e.g., on a Hadoop infrastructure or the like).

[0127] 3. Item-Based Filtering Model

[0128] As is shown in operation 215, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the processor 803, or the like, for sorting items in descending order of inferred affinity In some embodiments, the output of the collaborative filtering sub-model may be a list of a predicted preference order for every (ST,DN) pair within one or more user cities.

[0129] The item-based filtering model may be configured to run as a batch job with for example, a frequency of 1-4 runs daily. The model may apply a simple k-nearest neighbor model to the Destination similarities and known (ST,DN) affinities to predict the preference order of all (ST,DN) affinities. Much of the preference order is likely to remain constant between consecutive batch runs; however efficiently identifying those in the preference order that will remain constant is non-trivial. Thus each batch may update all unknown affinities.

[0130] In some embodiments, configurable parameter k≧N (default value 50) may be defined to be the neighborhood size. For each (ST,DN) pair in each user city with unknown affinity, the set n_ST (DN) may be defined to be the k Destinations DN′ in the same city with highest similarity to DN for which aff(ST, DN′) is known. If fewer than k such affinities are known then n_ST(DN) may be the set of all destinations DN′ for which aff(ST, DN′) is known. The unknown (ST,DN) affinity may then be computed as:

$\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)=\frac{{\Sigma }_{{\mathrm{DN}}^{\prime }\in n_{\mathrm{ST}}\left(\mathrm{DN}\right)}\left({\mathrm{sim}\left(\mathrm{DN},{\mathrm{DN}}^{\prime }\right)}^m*\mathrm{aff}\left(\mathrm{ST},{\mathrm{DN}}^{\prime }\right)\right)}{{\Sigma }_{{\mathrm{DN}}^{\prime }\in n_{\mathrm{ST}}\left(\mathrm{DN}\right)}\left({\mathrm{sim}\left(\mathrm{DN},{\mathrm{DN}}^{\prime }\right)}^m\right)}.$

[0131] Known affinities for Destinations most similar to DN are given the greatest weight in the prediction. Configurable parameter m changes the relative weighting—higher values of m lead to a greater difference in relative weighting for the same difference in similarity.

[0132] In some embodiments, this computationally expensive batch job may be parallelized by distributing the unknown (ST,DN) affinities across machines for independent computation.

[0133] The output of the collaborative filtering sub-model may be a list indicative of a preference order for every (ST,DN) pair within each user city. However, this is likely too much data to be useful in translating into real-time recommendations. Thus the output may also be post-processed to generate a fixed-length ranked list for each ST of the destinations for which ST has the highest inferred affinities.

[0134] In some embodiments, the hybrid item-based collaborative filtering model may be configured to compute unknown ad click rates for a given user based on known click rates for similar ads. In a pure hybrid collaborative filtering implementation, the pairwise item (advertisement) similarity may be computed based on the similarity of known click rates between two ads across all users. The hybrid model described herein augments this similarity with an indicator, such as an indicator of whether the ads have been placed by the same advertiser. That is, ads from the same advertiser may be given a higher similarity than those from different advertisers. The relative importance of click rate similarity versus common advertiser may be adjusted through a configurable parameter.

[0135] The item-based recommendation module may require a certain density or threshold of recorded clicks for a user in order to be effective. Thus the item-based recommendation module may be, in some embodiments, only used when the user has known positive click rates for at least N advertisements, where N is a configurable model parameter.

[0136] In some embodiments, advertisements may have, or otherwise be associated with, a start and end date and may be considered active between those two dates. The item-based recommendation module may generate predicted click rates for active advertisements for each user that has not been shown the ad. In some embodiments, unknown click rates for inactive ads do not need to be predicted; however, known click rates inactive ads can be used to predict click rates for active ads. For each user, the predicted and known click rates may be used to generate a user-specific ranking of active ads.

[0137] FIG. 2B is a flowchart illustrating an example process that may be performed by the item-based collaborative filtering module 110 in accordance with some example embodiments (e.g., an advertisement recommendation embodiment) of the present invention. In some embodiments, the output of the item-based collaborative filtering sub-model may be a list of known or predicted click rates for every user-advertisement (ST, AID) pair where AID is active.

[0138] The item-based recommendation module may be configured to generate predicted click rates for all active advertisements for each user (ST) with recorded clicks on at least N ads (active or inactive). An advertisement may be considered active if the current date is between the ad's start and end date, inclusive. Click rates may be normalized based on ad location, such that a common ranking may be used for each location on the site.

[0139] The item-based collaborative filtering module may be configured to utilize, for each site advertisement, the following data, Advertisement ID (AID); Start/end dates: used to determine whether ad is active or inactive; Location ID (LID): site location that this particular ad. A single ad may be associated with multiple location IDs (e.g., if multiple locations of the same size exist on the site then a single ad may be eligible for multiple locations); Advertising Business ID (BID): this allows the model to link multiple ads from the same advertiser either across a campaign offering ads on multiple locations in the site or across historical campaigns (or both); History of ad impressions for each User ST of each (AID, LID) pair. An impression occurs when ad AID has been displayed in location LID while User ST is on the user site; and History of clicks for each User ST of each (AID, LID) pair.

[0140] In some embodiments, the item-based recommendation module may be composed of three sub-models: (1) click rate model; (2) advertisement similarity model; and (3) collaborative filtering model proper. The click rate model may be configured to compute known click rates for each ST. A click rate may be computed for each advertisement for which the ST has at least one impression. The click rates may be normalized across advertisement location based on overall location click rates, which may allow for a single click rate for advertisements that may appear in multiple locations and a single ranking of advertisements for the ST independent of location. The Advertisement similarity model may be configured to compute a similarity metric as a function of known click rates and whether the advertising business is the same for two different advertisements. The collaborative filtering model may be configured to use the advertisement similarities to generate predicted click rates for each ST-Advertisement pair in which the ST has not had an impression of the Advertisement.

[0141] The collaborative filtering model may be run as a batch job with the frequency of the batch update set as a parameter (e.g., 1-4 times daily in production). The outputs from the models may flow ‘downward’, such that the similarity model uses the computed click rates, and the collaborative filtering model uses the click rates and similarities. Inactive Advertisements may not be recording new impressions or clicks. Thus click rates may only need to be updated between batch runs for active Advertisements, and similarities only need to be computed for Advertisement pairs in which at least one Advertisement is active.

[0142] In some embodiments, click rates are only recomputed for user and advertisement pairs in which there has been an impression since the last batch update. Click rates may be updated more frequently between batch updates in order to reduce processing time of the batch updates in some examples. In some embodiments, similarities may also be computed more frequently between collaborative filtering batches. However, new impressions for at least one user may be likely to be recorded with high frequency for any active advertisement, and thus there may be little benefit to such an approach. It will likely be more efficient to run all three models sequentially with each batch.

[0143] In some embodiments, some advertisements may specifically target users by socio-demographic, geographic, or other variables with the explicit direction that the advertisement not be shown to users outside of the defined target group. In some embodiments, the model may be configured to read in, or otherwise receive, those constraints and compute predicted click rates only for those Advertisements for which a given ST is eligible. Additionally or alternatively, some embodiments may include associating advertisements with keywords, for example, received during a search, pacing impressions, for example, evenly, during an advertisement's lifetime, factoring known destination affinity/similarity into estimated advertisement affinity/similarity.

[0144] 1. Click Rates

[0145] In some embodiments, the click rate for a given advertisement may be the key metric that is being estimated. Click rate may typically be computed as simply the ratio of clicks to impressions for a given AID. The Advertisement recommendation module may instead use a normalized click rate that is scaled based on the overall click rate for a given ad location. This may allow impressions and clicks on a single ad across multiple locations to be aggregated into a single click rate, and it allows comparison of click rates across ads regardless of location.

[0146] Accordingly, as is shown in operation 255, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the processor 803, or the like, for computing known click rates for each ST, a click rate may be computed for each advertisement for which the ST has at least one impression. Click rate may, in some embodiments, be computed as the ratio of clicks to impressions for a given AID.

[0147] In some embodiments, a portion of click rates may not change between consecutive batch runs. Thus known click rates can be stored between batches and updated only as required. Click rates for inactive ads (Advertisements for which the current date falls outside of the start and end dates) may not need to be updated. For active ads, a ST-AID pair may be flagged for update if either of the following events occurs: (1) An impression of AID is recorded for ST; (2) ST clicks on AID. Click rates may be updated before each collaborative filtering batch run. In some embodiments, the module may be configured to update click rates at a higher frequency between batch runs.

[0148] In some embodiments, configurable parameter n_min may be defined as the minimum number of impressions that must be recorded for a given (ST,AID) pair in order for the click rate to be computed (rather than inferred). For a user, advertisement, location triple (ST,AID,LID), the following impression and click variables may be defined:

I_ST,AID,LID=count of impressions for ST of AID at LID

C_ST,AID,LID=count of clicks by ST of AID at LID

[0149] The overall click rate for a Location LID may be then computed as:

${\mathrm{rate}}_{\mathrm{loc}}\left(\mathrm{LID}\right)=\frac{{\Sigma }_{\mathrm{ST},\mathrm{AID}}C_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}{{\Sigma }_{\mathrm{ST},\mathrm{AID}}I_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}.$

[0150] The absolute and normalized click rates for a given ad AID by user ST at location LID are, respectively:

$\mathrm{rate}\left(\mathrm{ST},\mathrm{AID},\mathrm{LID}\right)=\frac{C_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}{I_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}$ $\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},\mathrm{AID},\mathrm{LID}\right)=\frac{\mathrm{rate}\left(\mathrm{ST},\mathrm{AID},\mathrm{LID}\right)}{{\mathrm{rate}}_{\mathrm{loc}}\left(\mathrm{LID}\right)}.$

[0151] If there have been no impressions for a given (ST,AID,LID) triple then both values may be set to 0. The normalized click rate may scale the absolute click rate by the overall location click rate to enable comparisons to be made across different locations.

[0152] If a ST has recorded zero clicks on ad AID and has had fewer than n_min impressions of AID then the normalized click rate for that (ST,AID) is set to null to indicate that it needs to be predicted by the collaborative filtering model. Otherwise, the normalized rate may be set equal to a weighted sum of the adjusted click rates across locations with the number of impressions as the weighting factor:

$\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},\mathrm{AID}\right)=\frac{{\Sigma }_{\mathrm{LID}}\left(I_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}*\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},\mathrm{AID},\mathrm{LID}\right)\right)}{{\Sigma }_{\mathrm{LID}}I_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}.$

[0153] 2. Advertisement Similarity Model

[0154] As is shown in operation 260, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the processor 803, or the like, for computing a similarity metric between one or more advertisement pairs as a function of known click rates and a component that increases similarity when the advertising business matches between two advertisements. In other words, the component is a function of whether the advertising business is the same for two different advertisements. In some embodiments, a similarity metric may be required for all pairs of advertisements in which at least one advertisement is active.

[0155] The Advertisement similarity model may be a modified cosine similarity metric across the normalized (ST,AID) click rates that include a component that increases similarity when the advertising business matches between two advertisements. The weight placed on this parameter is configurable in some examples.

[0156] Similarities may be required for all pairs of advertisements in which at least one advertisement is active (ad start date≦current date≦ad end date). Similarities may be updated for each (AID1,AID2) pair in which an impression or click has been recorded for either ad. The rate of impressions is likely to be high enough that all active advertisements receive impressions between batch runs. Therefore, it is likely that similarities may need to be recomputed for every ad pair with an active ad prior to every batch run. However, in some embodiments, the number of active advertisements is likely to be low enough (i.e., below a predefined threshold) that this does not present a significant computing challenge.

[0157] In some embodiments, configurable parameter W_BID may be defined as the weight in interval [0,1] assigned to a business ID or destination in computing similarities. This may imply a (1−W_BID) weight on click rate similarity.

[0158] For each advertisement AID, rating vector R_AID may be defined as the vector of adjusted click rates rate(ST,AID) for each ST with null values set to zero. In some embodiments, vector dot-product may also be defined.

$R_{{\mathrm{AID}}_1}·R_{{\mathrm{AID}}_2}=\sum _{\mathrm{ST}}\left(\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},{\mathrm{AID}}_1\right)*\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},{\mathrm{AID}}_2\right)\right)$

[0159] Vector magnitude may also be defined:

$R_{\mathrm{AID}}=\sqrt{\sum _{\mathrm{ST}}\left({\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},\mathrm{AID}\right)}^2\right)}.$

[0160] Indicator function x_BID (AID₁, AID₂) may be equal to 1 if AID1 and AID2 have the same advertising business and zero otherwise. Then the similarity of AID1 and AID2 may be defined as:

$\mathrm{sim}\left({\mathrm{AID}}_1,{\mathrm{AID}}_2\right)=W_{\mathrm{BID}}x_{\mathrm{BID}}\left({\mathrm{AID}}_1,{\mathrm{AID}}_2\right)+\left(1-W_{\mathrm{BID}}\right)\frac{R_{{\mathrm{AID}}_1}·R_{{\mathrm{AID}}_2}}{R_{{\mathrm{AID}}_1}R_{{\mathrm{AID}}_2}}.$

[0161] In some embodiments, similarities may need only be recomputed for (AID1, AID2) pairs in which at least one of the advertisements has new normalized click rates for at least one user since the last batch update. It may not be necessary to compute similarities for (AID1, AID2) pairs for which both ads are no longer active (i.e., current date is outside of the ad start date and end date, inclusive).

[0162] Similarities may be computed independently for each pair. Thus the computation may be distributed.

[0163] Similarities may be symmetric, e.g., sim(AID₁, AID₂)=sim(AID₂, AID₁). There may therefore be no need to compute the similarities for both (AID1, AID2) and (AID2,AID1) as long as both similarities are updated when one is computed.

[0164] 3. Item-Based Filtering Model

[0165] As is shown in operation 265, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the processor 803, or the like, for sorting items in descending order of inferred affinity. That is, an inferred click rate may be determined for each ST-Advertisement pair in which the ST has not had an impression of the advertisement using the advertisement similarities. The output may be a list of all ST-Advertisement pairs in descending order of affinity, some empirical, some inferred.

[0166] The item-based filtering model may be configured to run as a batch job, with a frequency of, for example, 1-4 runs daily. The model may apply a simple k-nearest neighbor model (with configurable parameter k) to the advertisement similarities and known (ST, AID) click rates to predict all unknown (ST, AID) click rates. Because similarities are likely to change between each batch run, all unknown click rates for active advertisements may need to be recomputed during each batch.

[0167] In some embodiments, for each (ST, AID) pair with an unknown click rate and where AID is active, the set n_ST (AID) may be defined to be the k Advertisements AID′ (active or inactive) with highest similarity to AID for which rate(ST, AID′) is known. Then the unknown (ST,AID) click rate may be computed as:

$\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},\mathrm{AID}\right)=\frac{{\Sigma }_{{\mathrm{AID}}^{\prime }\in n_{\mathrm{ST}}\left(\mathrm{AID}\right)}\left({\mathrm{sim}\left(\mathrm{AID},{\mathrm{AID}}^{\prime }\right)}^m*\mathrm{aff}\left(\mathrm{ST},{\mathrm{AID}}^{\prime }\right)\right)}{{\Sigma }_{{\mathrm{AID}}^{\prime }\in n_{\mathrm{ST}}\left(\mathrm{AID}\right)}\left({\mathrm{sim}\left(\mathrm{AID},{\mathrm{AID}}^{\prime }\right)}^m\right)}.$

[0168] Known click rates for advertisements most similar to AID may be given the greatest weight in the prediction. Configurable parameter m changes the relative weighting—higher values of m lead to a greater difference in relative weighting for the same difference in similarity.

[0169] Click rates may need only be predicted for active Advertisements. The batch job may be parallelized by distributing the unknown (ST, AID) affinities across machines for independent computation. The output of the collaborative filtering sub-model may be a list of known or predicted click rates for every (ST, AID) pair where AID is active.

[0170] In some embodiments, as described above, the item-based collaborative filtering model may require a sufficient amount of affinity data for a given user in order to predict their unknown preferences. However, for a newly registered user or a user with limited recorded activity, the item-based collaborative filtering model may not perform well, such as it may perform below a defined performance threshold. As such, the user-based collaborative filtering model may be utilized.

[0171] When a user has fewer than N known affinities, the user's unknown affinities may be predicted using a hybrid user-based collaborative filtering model. User-based collaborative filtering may transpose item-based filtering. That is, instead of predicting affinity based on a user's known affinities for similar destinations, user-based filtering predicts affinity based on known affinities of similar users for the same destination. Hybrid user-based collaborative filtering may use both socio-demographic variables and known affinities to compute similarity.

[0172] The user-based recommendation module may be configured to generate the same outputs as the item-based model: predicted preferences for user-destination pairs in each user city with unknown preference. In some embodiments, the predictions may be generated only for those pairs where the user does not have enough known affinities to qualify for the item-based recommender. For each user, the predicted and known preferences may be used to generate a user-specific preference ranking over all destinations.

[0173] FIG. 3A is a flowchart illustrating an example process that may be performed by the user-based collaborative filtering module 112 in accordance with some example embodiments (e.g., a destination recommendation embodiment) of the present invention. In some embodiments, the output of the collaborative filtering sub-model may be a list of a known or predicted (ST, DN) affinity for each of one or more (ST, DN) pairs. In some embodiments, the output may a fixed-length ranked list for each ST of the destinations for which ST has the highest known or predicted affinities.

[0174] The user-based recommendation module may be configured to generate affinities for every pair of user and destination in each user city where the number of known affinities for the user is less than N. The model may be a hybrid user-based collaborative filtering model. This model may be composed of 3 sub-models: (1) an affinity model; (2) user similarity model; and (3) a collaborative filtering model proper.

[0175] The affinity model may be configured to compute ST-DN affinities as a function of ST site behaviors related to the DN: follows, favorites, activations at Destinations, acceptance of deals, etc. The user similarity model may be configured to compute a similarity metric as a function of socio-demographic and ST preference variables and known ST-DN affinities. The collaborative filtering model proper may be configured to use the user similarities to generate predictions for unknown ST-DN affinities.

[0176] In some embodiments, the model flow may be the same as for the item-based recommender. The key difference between the models is that the user-based recommender uses user similarity instead of destination similarity. As in the case of the item-based recommendation module, the user-based recommendation module may be updated in batches, for example, at approximately 1-4 times per day. The affinity and similarity components may be updated more frequently between batches to reduce the peak loads during batch processing.

[0177] 1. Affinity Model

[0178] The affinity model for the user-based recommendation module may be configured the same as or similar to the affinity model for the item-based recommendation module. The two affinity models, in some embodiments, may in fact be run as a single model, and the computed affinities may not need to be segregated until they are input into the appropriate similarity and filtering sub-models. Accordingly, as is shown in operation 305, an apparatus, such as computing system 500, may include means, such as the user-based collaborative filtering module 112, the processor 803, or the like, for computing ST-DN affinities as a function of ST site behaviors related to the DN.

[0179] 2. User Similarity Model

[0180] The user similarity model may be configured to generate pairwise similarities between users. As is shown in operation 310, an apparatus, such as computing system 500, may include means, such as the user-based collaborative filtering module 112, the processor 803, or the like, for computing a similarity metric between two users as a function of socio-demographic and ST preference variables and known ST-DN affinities.

[0181] In some embodiments, the similarity metric may then be computed as a modified cosine similarity between the extended socio-demographic and affinity vectors of the users. The model may be constructed in such a way that as the number of known affinities may increase for a user, the relative weight of affinity similarity naturally increases compared to socio-demographic similarity in the overall similarity computation.

[0182] The user-based filtering model may require that similarities be computed for all (ST1, ST2) pairs in which at least one of ST1 or ST2 does not meet the threshold requirement for the item-based recommendation module. The processing flow for the user similarity model is similar to that of the destination similarity model described above. As is the case for the destination model, many ST similarities are likely to remain unchanged between consecutive batch runs of the filtering model. Therefore, the similarities may be stored between batch runs and be computed/recomputed only as required. A ST may be flagged as needing to have its similarities updated if any of the following occur: (1) The ST is new to the system (i.e., does not have any similarities); (2) The relevant ST profile information has been updated either by the user or the system; (3) One or more (ST, DN) affinities have been updated for this ST.

[0183] When a ST is flagged, the similarities between that ST and all other STs in the same user city may be recomputed. In some embodiments, similarities may be symmetric, meaning that sim(ST₁, ST₂)=sim(ST₂, ST₁). Thus it may be important that recomputed similarities be updated for both pair orderings if they are stored separately, although the computation may only be performed a single time.

[0184] As in the destination similarity model, flagged STs may be updated continuously by triggering the similarity model immediately when a ST is flagged, or the flagged STs may be updated in batches. The update frequency may be no more frequent than the affinity update frequency and no less frequent than the collaborative filtering batch frequency.

[0185] The logic below describes the algorithm for computing similarity for a single pair of STs.

[0186] The similarity between two Users ST1 and ST2 may be computed as a cosine-like similarity function over a set of pure cosine similarity sub-functions. The similarity may be a real number on an interval, for example [−1,1], with a higher value indicating greater similarity.

[0187] The model may be configured to first compute a socio-demographic similarity between ST1 and ST2. The input socio-demographic dimensions are: (1) Demographics; (2) Age (normalized onto [−1,1] interval; unknown age set to median); (3) Gender (1=M, −1=F, 0=unknown); (4) Interests; Drink of choice; Sports interests (e.g., up to 5); Favorite music (e.g., up to 5); Favorite food (e.g., up to 5); Favorite travel destination (e.g., up to 5); Hobbies/interests (e.g., up to 5); Personal Style (e.g., up to 5); Favorite Destinations. Additionally or alternatively, the model may be configured to utilize social media data. That is, in a social media environment, social media data may provide another important source of user-similarity information. Specifically, any reciprocal measure of user-user interaction may be considered to suggest, for example, a certain mutual influence between the actions of ST1 and ST2 and such information may be encoded in the user-similarity. In some embodiments, a new sub-function may be utilized in the form of a weighted sum over many cosine similarity sub-functions. Each of these sub-functions may be configured to measure similarity in terms of a different user-user relationship (i.e. a different kind of possible social media interaction (e.g., are ST1 and ST2 “friends” on social media, what is the set similarity between ST1 and ST2 “friends” on social media, do ST1 and ST2 “chat” with each other more often than a certain threshold rate of chats per time, or the like).

[0188] The interest dimensions may be concatenated into a single list for each ST. The socio-demographic similarity between ST1 and ST2 may then be computed as:

${\mathrm{sim}}_{\mathrm{sd}}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)=\frac{W_aa_{{\mathrm{ST}}_1}a_{{\mathrm{ST}}_2}+W_gg_{{\mathrm{ST}}_1}g_{{\mathrm{ST}}_2}+{\mathrm{ST}}_1\mathrm{interests}\bigcap {\mathrm{ST}}_2\mathrm{interests}}{\sqrt{W_a+W_g+{\mathrm{ST}}_1\mathrm{interests}}*\sqrt{W_a+W_g+{\mathrm{ST}}_2\mathrm{interests}}}$

[0189] where a_ST1 and a_ST2 are the age (normalized) and gender, respectively, of User ST. W_a, and W_g may be configurable weights controlling the relative contribution of the age and gender dimensions, respectively, to the overall user similarity.

[0190] Similar to the destination model, the final user similarity measure may be a function of the socio-demographic similarities defined above and the known affinities of each user. V_ST may be defined to be the vector of (ST,DN) affinities across all destinations DN in the city. If the affinity is null (i.e., unknown) then the corresponding element of the vector may be set to zero. Then the user similarity between ST1 and ST2 may be defined as:

$\mathrm{sim}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)=\frac{W_{\mathrm{sd}}{\mathrm{sim}}_{\mathrm{sd}}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)+V_{{\mathrm{ST}}_1}·V_{{\mathrm{ST}}_2}}{\sqrt{W_{\mathrm{sd}}+{\Sigma }_{\mathrm{DN}}\left({\mathrm{aff}\left({\mathrm{ST}}_1,\mathrm{DN}\right)}^2\right)}*\sqrt{W_{\mathrm{sd}}+{\Sigma }_{\mathrm{DN}}\left({\mathrm{aff}\left({\mathrm{ST}}_2,\mathrm{DN}\right)}^2\right)}}.$

[0191] As was the case for the destination similarity model, the user similarity model may adjust weight toward the affinity component of the similarity as more affinities become known for either ST1 or ST2. Non-negative weight W_sd may be a configurable parameter that may adjust the rate at which the affinity similarity gains influence over the socio-demographic similarity. Higher values of W_sd put greater weight on the socio-demographic similarity components, which may mean that a higher number of known affinities is required to reach a similar balance between socio-demographic and affinity-based similarity as for a lower value of W_sd.

[0192] As is the case for the destination similarity model, for a flagged ST the similarity to each other ST may be updated. Each pairwise similarity may be computed independently. Whether similarity updates are performed continuously or in batches, computation for these pairwise similarities can be distributed (e.g., on a Hadoop infrastructure).

[0193] 3. User-Based Filtering Model

[0194] As is shown in operation 315, an apparatus, such as computing system 500, may include means, such as the user-based collaborative filtering module 112, the processor 803, or the like, for sorting items in descending order of inferred affinity. In some embodiments, the apparatus is configured to output a list of a predicted preference order of all unknown (ST, DN) affinities for users without enough known affinities to meet the item-base model threshold.

[0195] In some embodiments, the user-based filtering model may be configured to run as a batch job. The frequency may be the same as for the item-based model. The user-based model may be a transposition of the item-based model. The user-based model may apply a simple k-nearest neighbor model to the user similarities and known (ST, DN) affinities to predict all unknown (ST, DN) affinities for users without enough known affinities to meet the item-base model threshold. Many predicted affinities are likely to remain constant between consecutive batch runs; however, efficiently identifying the predicted affinities that will remain constant is non-trivial. Thus each batch may update all unknown affinities in some examples.

[0196] In some embodiments, configurable parameter k (default value 50) may be defined to be the neighborhood size. For each (ST, DN) pair in each user city with unknown affinity, the set n_DN(ST) may be defined to be the k Users ST′ in the same city with highest similarity to ST for which aff(ST′, DN) is known. If fewer than k such affinities are known then n_DN(ST) may be the set of all Users ST′ for which off (ST′, DN) is known. In some embodiments, a configurable variable k_min≦k (default value 20) may also be defined. If no known exist for DN then, in some embodiments, aff(ST, DN)=0. If |n_DN(ST)|≧k_min then the unknown (ST,DN) affinity may be computed as:

$\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)=\frac{{\Sigma }_{{\mathrm{ST}}^{\prime }\in n_{\mathrm{DN}}\left(\mathrm{ST}\right)}\left({\mathrm{sim}\left(\mathrm{ST},{\mathrm{ST}}^{\prime }\right)}^m*\mathrm{aff}\left({\mathrm{ST}}^{\prime },\mathrm{DN}\right)\right)}{{\Sigma }_{{\mathrm{ST}}^{\prime }\in n_{\mathrm{DN}}\left(\mathrm{ST}\right)}\left({\mathrm{sim}\left(\mathrm{ST},{\mathrm{ST}}^{\prime }\right)}^m\right)}.$

[0197] If instead 0<|n_DN(ST)|<k_min then the unknown affinity may be computed as:

$\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)=\frac{{\Sigma }_{{\mathrm{ST}}^{\prime }\in n_{\mathrm{DN}}\left(\mathrm{ST}\right)}\left({\mathrm{sim}\left(\mathrm{ST},{\mathrm{ST}}^{\prime }\right)}^m*\mathrm{aff}\left({\mathrm{ST}}^{\prime },\mathrm{DN}\right)\right)}{{\Sigma }_{{\mathrm{ST}}^{\prime }\in n_{\mathrm{DN}}\left(\mathrm{ST}\right)}\left({\mathrm{sim}\left(\mathrm{ST},{\mathrm{ST}}^{\prime }\right)}^m\right)}*\frac{{\log }_b\left(1+n_{\mathrm{DN}}\left(\mathrm{ST}\right)\right)}{{\log }_b\left(1+k_{\min }\right)}.$

[0198] In some embodiments, the second term may scale the inferred rating based on the number of known affinities—a small number of known affinities means relatively less confidence in the validity of the mean affinity, and thus the mean affinity is scaled toward zero. In some embodiments, b is a configurable parameter. As the number of known affinities approach k_min, this ratio approaches 1, and the impact of the scaling factor may decrease.

[0199] Known affinities for users most similar to ST may be given the greatest weight in the prediction. In some embodiments, configurable parameter m may change the relative weighting—higher values of m lead to a greater difference in relative weighting for the same difference in similarity.

[0200] The common parameters for user- and item-based models (k and m) may in fact have different values and may be initialized in the implementation as distinct parameters. This computationally expensive batch job may be parallelized by distributing the unknown (ST, DN) affinities across machines for independent computation.

[0201] The output of the collaborative filtering sub-model may be a list of known or predicted (ST, DN) affinity for every (ST, DN) pair within each user city. However, this may be, in some embodiments, too much data to be useful in translating into real-time recommendations. Thus the output may be post-processed to generate a fixed-length ranked list for each ST of the Destinations for which ST has the highest known or predicted affinities.

[0202] In some embodiments, the item-based collaborative filtering model may require a sufficient number of known (ST, AID) click rates for a given user in order to predict click rates for that user on other advertisements. For a newly registered user or a user with limited recorded activity, the model may not perform above a model performance level. This is known, and has been described herein, as the user cold start problem.

[0203] When a user has recorded clicks on fewer than N advertisements, the user's unknown click rates may be predicted using a hybrid user-based collaborative filtering model. User-based collaborative filtering transposes item-based filtering. That is, instead of predicting click rates based on a user's known click rates on similar advertisements, user-based filtering predicts click rates based on observed click rates of similar users for the same advertisement. Hybrid user-based collaborative filtering may use both socio-demographic variables and known click rates to compute similarity.

[0204] The user-based collaborative filtering model is complementary to the item-based model. Both generate predicted click rates for (ST, AID) pairs with no known impressions, but they do so for two different sets of users.

[0205] Some advertisements may specifically target STs by socio-demographic, geographic, or other variables with the explicit direction that the advertisement not be shown to STs outside of the defined target group. In some embodiments, those constraints may be received and predicted click rates may be computed only for those advertisements for which a given ST is eligible.

[0206] FIG. 3B is flowchart illustrating an example process that may be performed by the user-based collaborative filtering module 112 in accordance with some example embodiments (e.g., an advertisement recommendation embodiment) of the present invention. The output, in some embodiments, is predicted click rates for each (ST, AID) pair in which the ST has not had an impression of the advertisement.

[0207] The user-based collaborative filtering module may be configured to predict click rates for every (ST, AID) pair in which ad AID is active, ST has not yet had an impression of AID, and the total number of advertisements that ST has clicked on is less than N. The user-based collaborative filtering module may be configured as a hybrid user-based collaborative filtering model, and may be comprised of sub-models: (1) a click rate model; (2) a user similarity model; and (3) a collaborative filtering model proper.

[0208] The click rate model may be configured to compute known click rates for each ST. This model may be the same as the click rate model for the item-based recommender. The user similarity model may be configured to compute a similarity metric as a function of socio-demographic and ST preference variables and known (ST, AID) click rates. The collaborative filtering model proper may be configured to use the user similarities to generate predicted click rates for each (ST, AID) pair in which the ST has not had an impression of the advertisement.

[0209] In some embodiments, the required input data for the user-based collaborative filtering module may include some portion of or, in some embodiments, all inputs for the item-based model except the advertising business. In addition, ST socio-demographic and preference variables may be required. These variables are specified in the user similarity model description.

[0210] The model flow may be the same as for the item-based recommendation module. The key difference between the two models is that the user-based collaborative filtering module uses user similarity instead of advertiser similarity. As in the case of the item-based collaborative filtering module, the user-based model may be updated in batches, at a frequency of, for example, approximately 1-4 times per day. The click rate and user similarity component models may be updated more frequently between batches to reduce the peak loads during batch processing.

[0211] A difference between the item-based and user-based modules is that, whereas the advertisements similarity model in the item-based collaborative filtering module may compute similarities for a relative small number of active advertisements, the number of user pairs that must be evaluated in the user-based user similarity model may be significant. Possible example implementation strategies that would mitigate this challenge are discussed in the user similarity model description.

[0212] 1. Click Rate Model

[0213] The click rate model for the user-based recommender may be the same as or similar to the click rate model for the item-based recommendation module. In some embodiments, the two models may in fact be run as a single model, and the computed click rates may not need to be segregated until they are input into the appropriate similarity and filtering sub-models. Accordingly, as is shown in operation 355, an apparatus, such as computing system 500, may include means, such as the user-based collaborative filtering module 112, the processor 803, or the like, for computing known click rates for each ST, a click rate may be computed for each advertisement for which the ST has at least one impression.

[0214] 2. User Similarity Model

[0215] The User similarity model may be configured to generate pairwise similarities between users. As is shown in operation 360, an apparatus, such as computing system 500, may include means, such as the user-based collaborative filtering module 112, the processor 803, or the like, for computing a similarity metric as a function of socio-demographic and ST preference variables and known (ST,AID) click rates. For example, in some embodiments, the apparatus may be configured to apply a simple k-nearest neighbor model to the user similarities and known (ST,AID) click rates to predict all unknown (ST,AID) click rates for users that do not meet the click threshold for the item-based recommendation model. In some embodiments, the apparatus may be configured for, as the number of known click rates increases for a user, increasing the relative weight of click rate similarity compared to socio-demographic similarity in the overall similarity computation.

[0216] In some embodiments, similarity may be computed as a modified cosine similarity between the extended socio-demographic and click rate vectors of the users. The model may be constructed in such a way that as the number of known click rates increases for a user, the relative weight of click rate similarity naturally increases compared to socio-demographic similarity in the overall similarity computation.

[0217] The model is very similar to the user similarity model for the destination recommendation module. The primary difference is in the use of click rates in place of ST-Destination affinities.

[0218] In some embodiments, the user-based filtering model may require that similarities be computed for all (ST1,ST2) pairs in which at least one of ST1 or ST2 does not meet the threshold requirement for the item-based recommender. Many ST similarities are likely to remain unchanged between consecutive batch runs of the filtering model. Therefore, the similarities may be stored between batch runs and be computed/recomputed only as required. A ST may be flagged as needing to have its similarities updated if any of the following occur: (1) The ST is new to the system (i.e., does not have any similarities); (2) The relevant ST profile information has been updated either by the user or the system; or (3) The ST has recorded at least one new impression or click for any advertisement.

[0219] In some embodiments, when a ST is flagged, the similarities between that ST and all other STs may be recomputed (see implementation note below for discussion). Similarities may be symmetric, meaning that sim(ST₁, ST₂)=sim(ST₂,ST₁) so that recomputed similarities may be updated for both pair orderings if they are stored separately.

[0220] In some embodiments, similarities for flagged STs are updated in more frequent batches than the frequency of the user-based collaborative filtering sub-model in order to, for example, gain efficiency The update frequency may be no more frequent than the click rate update frequency and no less frequent than the collaborative filtering batch frequency in some example, however other frequencies may be envisioned in other examples.

[0221] The logic below describes an example algorithm for computing similarity for a single pair of STs.

[0222] The similarity between two users ST1 and ST2 may be computed as a cosine-like similarity function over a set of pure cosine similarity sub-functions. The similarity may be a real number on an interval, for example, the interval [−1,1], with a higher value indicating greater similarity.

[0223] In some embodiments, the model first may be configured to compute a socio-demographic similarity between ST1 and ST2. The input socio-demographic dimensions are: Demographics; Age (normalized onto [−1,1] interval; unknown age set to median); Gender (1=M, −1=F, 0=unknown); Interests; Drink of choice; Sports interests (up to 5); Favorite music (up to 5); Favorite food (up to 5); Favorite travel destination (up to 5); Hobbies/interests (up to 5); Personal Style (up to 5); and Favorite Destinations;

[0224] The interest dimensions may concatenate into a single list for each ST. The socio-demographic similarity between ST1 and ST2 may then computed as:

${\mathrm{sim}}_{\mathrm{sd}}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)=\frac{W_aa_{{\mathrm{ST}}_1}a_{{\mathrm{ST}}_2}+W_gg_{{\mathrm{ST}}_1}{g_{\mathrm{ST}}}_2+{\mathrm{ST}}_1\mathrm{interests}\bigcap {\mathrm{ST}}_2\mathrm{interests}}{\sqrt{W_a+W_g+{\mathrm{ST}}_1\mathrm{interests}}*\sqrt{W_a+W_g+{\mathrm{ST}}_2\mathrm{interests}}}$

[0225] where a_ST1 and a_ST2 are the age (normalized) and gender, respectively, of ST. W_a, and W_g may be configurable weights controlling the relative contribution of the age and gender dimensions, respectively, to the overall user similarity.

[0226] The final user similarity measure may be a function of the socio-demographic similarities defined above and the known click rates of each user. VST may be defined to be the vector of (ST,AID) click rates across all Advertisements AID. If the click rate for a given (ST,AID) pair is null (i.e., unknown) then the corresponding element of the vector may be set to zero. Then the User similarity between ST1 and ST2 may be defined as:

$\mathrm{sim}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)=\frac{W_{\mathrm{sd}}{\mathrm{sim}}_{\mathrm{sd}}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)+V_{{\mathrm{ST}}_1}·V_{{\mathrm{ST}}_2}}{\sqrt{W_{\mathrm{sd}}+{\Sigma }_{\mathrm{AID}}\left({\stackrel{\_}{\mathrm{rate}}\left({\mathrm{ST}}_1,\mathrm{AID}\right)}^2\right)}*\sqrt{W_{\mathrm{sd}}+{\Sigma }_{\mathrm{AID}}\left({\stackrel{\_}{\mathrm{rate}}\left({\mathrm{ST}}_2,\mathrm{AID}\right)}^2\right)}}.$

[0227] The User similarity model may naturally adjust weight toward the click rate component of the similarity as more click rates become known for either ST1 or ST2. Non-negative weight W_sd may a configurable parameter that may adjust the rate at which the click rate similarity gains influence over the socio-demographic similarity. Higher values of W_sd may put greater weight on the socio-demographic similarity components, which means that a higher number of known click rates may be required to reach a similar balance between socio-demographic and click-based similarity as for a lower value of W_sd.

[0228] In some embodiments, for a flagged ST, the similarity to each other ST may be updated. Each pairwise similarity may be computed independently. Whether similarity updates are performed continuously or in batches, computation for these pairwise similarities can be distributed (e.g., on a Hadoop infrastructure).

[0229] In some embodiments, the similarities may be updated between collaborative filtering batch runs in order to reduce peak processing loads. In some embodiments, some (ST1,ST2) similarities may be overwritten in that case if one of the STs is again flagged before the next full-model batch update, and thus the tradeoff may be analyzed to determine whether more frequent updates may be performed to, for example, improve computational performance.

[0230] In some embodiments, because a plurality of advertising campaigns are likely to be national or regional, ST similarities may ideally be computed for all (ST1,ST2) pairs, regardless of user city, in which at least one ST does not meet the threshold for the item-based recommendation module. The large number of users across the system may make this impractical. One potential solution to this issue is to partition the user-based recommendation module by social city. The accuracy of the model may decrease marginally relative to the reduction in computational requirements. Alternative partitioning rules may be set that cluster dynamically based on number of active users, for example, newly launched cities may be combined with one or more geographically and/or demographically similar cities until the number of users in the new city reaches a specified threshold.

[0231] 3. User-Based Filtering Model

[0232] As is shown in operation 365, an apparatus, such as computing system 500, may include means, such as the user-based collaborative filtering module 112, the processor 803, or the like, for sorting items in descending order of inferred affinity. In some embodiments, the output of the collaborative filtering sub-model may be a list of a predicted preference order for each (ST,AID) pair in which the ST has not had an impression of the advertisement using the user similarities.

[0233] In some embodiments, the user-based filtering model may be configured to run as a batch job. The frequency may be the same as for the item-based model. The user-based model may be a transposition of the item-based model. The user-based model may apply a simple k-nearest neighbor model to the user similarities and known (ST,AID) click rates to predict all unknown (ST,AID) click rates for users that do not meet the click threshold for the item-based recommender. Many predicted click rates are likely to remain constant between consecutive batch runs; however efficiently identifying the predicted click rates that may remain constant is non-trivial. Thus each batch may update all unknown click rates.

[0234] In some embodiments, configurable parameter k (default value 50) may be defined as the neighborhood size. For each (ST,AID) pair with unknown click rate, the set n_AID(ST) may be defined to be the k Users ST′ in with highest similarity to ST for which rate(ST′, AID) is known. If the number of known click rates for AID is less than k then n_AID(ST) will be the set of all users ST′ for which rate(ST′,AID) is known. If no known click rates exist for AID then the predicted (ST,AID) click rate may be set to zero.

[0235] Otherwise, the click rate may be predicted as:

$\stackrel{\_}{\mathrm{rate}}\left(\mathrm{ST},\mathrm{AID}\right)=\frac{{\Sigma }_{{\mathrm{ST}}^{\prime }\in n_{\mathrm{AID}}\left(\mathrm{ST}\right)}\left({\mathrm{sim}\left(\mathrm{ST},{\mathrm{ST}}^{\prime }\right)}^m*\stackrel{\_}{\mathrm{rate}}\left({\mathrm{ST}}^{\prime },\mathrm{AID}\right)\right)}{{\Sigma }_{{\mathrm{ST}}^{\prime }\in n_{\mathrm{AID}}\left(\mathrm{ST}\right)}\left({\mathrm{sim}\left(\mathrm{ST},{\mathrm{ST}}^{\prime }\right)}^m\right)}.$

[0236] Known click rates for users most similar to ST may be given the greatest weight in the prediction. In some embodiments, configurable parameter m may change the relative weighting such that, for example, higher values of m lead to a greater difference in relative weighting for the same difference in similarity.

[0237] The common parameters for user- and item-based models (k and m) may have different values and may be initialized in the implementation as distinct parameters. Additionally, these parameters are distinct from the similar parameters in the destination recommendation module.

[0238] Batch job may be parallelized by distributing the unknown (ST,AID) click rates across machines for independent computation.

[0239] In some embodiments, when a new user registers for the system, predicted affinities may be generated for that user in the next run of the collaborative filtering algorithms. The model, however, may still need to be able to recommend destinations for these users until user-specific recommendations become available. In this case, the model may use global average affinities across all users, adjusted for number of known affinities, as a stand in until a next collaborative filtering model run.

[0240] FIG. 4A is a flowchart illustrating an example process that may be performed by the global average module 114 in accordance with some example embodiments (e.g., a destination recommendation embodiment) of the present invention.

[0241] As is shown in operation 405, an apparatus, such as computing system 500, may include means, such as the global average module 114, the processor 803, or the like, for computing ST-DN affinities as a function of ST site behaviors related to the DN. As is shown in operation 410, an apparatus, such as computing system 500, may include means, such as the global average module 114, the processor 803, or the like, for, identifying, for each DN, the set of all users in the current city with known (ST,DN) affinity. As is shown in operation 415, an apparatus, such as computing system 500, may include means, such as the global average module 114, the processor 803, or the like, for sorting items in descending order of inferred affinity. In some embodiments, the output of the sub-model may be a list of a user independent predicted preference order for DN affinities based on the mean of all known affinities for each DN. In some embodiments, the predictions may be scaled based on the number of known affinities.

[0242] In some embodiments, global affinities may be computed in a manner similar to the user-based filtering model described above. For Destination DN, N_DN may be defined as the set of all users ST in the current city with known (ST, DN) affinity. If no such ST exist (i.e., there are no known affinities for DN) then the global affinity prediction aff(DN) may be set to zero. If |N_DN|<k_min, where k_min is the same parameter as defined above, then:

$\mathrm{aff}\left(\mathrm{DN}\right)=\frac{{\Sigma }_{\mathrm{ST}\in N_{\mathrm{DN}}}\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)}{N_{\mathrm{DN}}}*\frac{{\log }_b\left(1+N_{\mathrm{DN}}\left(\mathrm{ST}\right)\right)}{{\log }_b\left(1+k_{\min }\right)}.$

[0243] The first term may be the mean of all known affinities for DN. Note that because the known affinities include a normalized rating component, the known affinities may be either positive or negative. The second term scales the mean rating based on the number of known affinities, a small number of known affinities means relatively less confidence in the validity of the mean affinity, and thus the mean affinity is scaled toward zero.

[0244] If instead |N_DN|≧k_min then set:

$\mathrm{aff}\left(\mathrm{DN}\right)=\frac{{\Sigma }_{\mathrm{ST}\in N_{\mathrm{DN}}}\mathrm{aff}\left(\mathrm{ST},\mathrm{DN}\right)}{N_{\mathrm{DN}}}.$

[0245] results in an arithmetic mean over all known affinities for DN.

[0246] Note that the global average (GA) model may be configured to assign each destination a constant rating, based on an assumption that all users have the same preferences. While this assumption is dubious, it's the most that can be said until we know more about the destinations or the users. To determine “how much” observed affinities are enough to switch away from using GA, statistics may be utilized. A goal of the system may be to always make recommendations for a user (or destination) using the model that is expected to have the least error. GA performs the best under the most uncertainty, so the GA prediction is our null hypothesis, and the CF models are alternate hypotheses. The error comes from comparing the three model's predictions for each observed affinity. This gives three errors, and the model with the smallest expected error is the model chosen/selected at the time the recommendations are built/determined for a user. If the error for a DN is lowest with GA, then GA should be used for that DN—otherwise, where item-based CF has a lower error, item-based CF should be used. If the error for an ST is lowest with GA, then the GA should be used for that ST—otherwise, where user-based CF has a lower error, user-based CF may be used. The errors may not be known until after-the-fact, and as such, the system may not be configured in terms of error directly. Instead, statistical analysis of past affinities may be computed to determine other values which indicate at or near what point the error of GA exceeds the error of CF—these values are mentioned above (N, k, m, etc.) and the system may then perform best when these values are determined using statistical methods.

[0247] Note that this affinity computation may be independent of ST. Thus the predicted affinity may need only be computed once for each DN and used for any new user that was not included in the previous collaborative filtering model runs.

[0248] This model may be much less computationally intensive than the collaborative filtering models described above and may therefore be run with higher frequency update cycles than for the collaborative filtering models in some examples. However, given that global affinities are likely to change slowly over time, the system may be configured to run once per day, although other frequencies may be envisioned in some examples.

[0249] In the initial implementation, the system cold start model may also be applied when a new city is introduced. In some embodiments, however, new cities may be able to leverage information from existing user cities to improve recommendations immediately, e.g., via knowledge-based models trained on existing cities.

[0250] Similar to above, in some embodiments, when a new user registers for the system, no predicted click rates may be generated for that user until the next run of the collaborative filtering algorithms. The model, however, may still need to be able to recommend advertisements for these users until user-specific recommendations become available. In this case, the model may use global normalized click rates across all users.

[0251] FIG. 4B is a flowchart illustrating an example process that may be performed by the global average module 114 in accordance with some example embodiments (e.g., an advertisement recommendation embodiment) of the present invention.

[0252] Accordingly, as is shown in operation 455, an apparatus, such as computing system 500, may include means, such as the global average module 114, the processor 803, or the like, for computing known click rates for each ST, a click rate may be computed for each advertisement for which the ST has at least one impression. As is shown in operation 460, an apparatus, such as computing system 500, may include means, such as the global average module 114, the processor 803, or the like, for, for each advertisement, identifying the set of all users with known click rate. As is shown in operation 465, an apparatus, such as computing system 500, may include means, such as the global average module 114, the processor 803, or the like, for for sorting items in descending order of inferred affinity. In some embodiments, the output of the sub-model may be a list of a user independent predicted preference order for each advertisement.

[0253] In some embodiments, the global click rates may be computed similarly to the user-specific click rates described above. In some embodiments, the total clicks and impressions for ad AID at location LID may be defined as, respectively:

$C_{\mathrm{AID},\mathrm{LID}}=\sum _{\mathrm{ST}}^{}C_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}$ $I_{\mathrm{AID},\mathrm{LID}}=\sum _{\mathrm{ST}}I_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}$

[0254] The location click rate is defined as above:

${\mathrm{rate}}_{\mathrm{loc}}\left(\mathrm{LID}\right)=\frac{{\Sigma }_{\mathrm{ST},\mathrm{AID}}C_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}{{\Sigma }_{\mathrm{ST},\mathrm{AID}}I_{\mathrm{ST},\mathrm{AID},\mathrm{LID}}}=\frac{{\Sigma }_{\mathrm{AID}}C_{\mathrm{AID},\mathrm{LID}}}{{\Sigma }_{\mathrm{AID}}I_{\mathrm{AID},\mathrm{LID}}}.$

[0255] The absolute and normalized click rates for a given ad AID at location LID may be computed across all users instead of individually for each user. They are, respectively:

$\mathrm{rate}\left(\mathrm{AID},\mathrm{LID}\right)=\frac{C_{\mathrm{AID},\mathrm{LID}}}{I_{\mathrm{AID},\mathrm{LID}}}$ $\stackrel{\_}{\mathrm{rate}}\left(\mathrm{AID},\mathrm{LID}\right)=\frac{\mathrm{rate}\left(\mathrm{AID},\mathrm{LID}\right)}{{\mathrm{rate}}_{\mathrm{loc}}\left(\mathrm{LID}\right)}.$

[0256] The overall normalized click rate for AID is:

$\stackrel{\_}{\mathrm{rate}}\left(\mathrm{AID}\right)=\frac{{\Sigma }_{\mathrm{LID}}\left(I_{\mathrm{AID},\mathrm{LID}}*\stackrel{\_}{\mathrm{rate}}\left(\mathrm{AID},\mathrm{LID}\right)\right)}{{\Sigma }_{\mathrm{ST},\mathrm{LID}}I_{\mathrm{AID},\mathrm{LID}}}.$

[0257] In some embodiments, the predicted click rates rate (AID) are independent of ST. Thus the predicted click rate may need only be computed once for each AID during the overall recommender batch run and used to respond to system queries for which the user is unknown to the recommendation module.

[0258] This model is may be less computationally intensive than the collaborative filtering models described above and may therefore be run with higher frequency update cycles than for the collaborative filtering models. In some embodiments, given that global click rates are likely to change slowly over time, the system may be configured to run the updates less frequently, for example, once per day.

[0259] In some embodiments, the recommendation module (e.g., the destination recommendation model and the advertisement recommendation module) may be configured to generate recommendations in response to a user's keyword search. In some embodiments, two lists of results may be generated by sorting on different metrics: (1) The basic match score may be computed as a function of the known/predicted user-destination affinity and the level of keyword match; and (2) The boosted match score may also include a “boost” component computed from a destination status. Destinations may be sorted separately by the boosted score in order to determine which promotional/sponsored recommendations will be displayed.

[0260] In some embodiments, the level of keyword match may be measured as the ratio of keywords matched for a given destination. For example, a search for keywords “bar,” “country,” and “dancing” will have a match value of ⅔ with a destination with keywords “bar” and “dancing” but not “country.” In one exemplary embodiment, formally, let K_DN be the keywords associated with destination DN. For a search over keyword set K,

$\mathrm{match}\left(\mathrm{DN},K\right)=\frac{K\bigcap K_{\mathrm{DN}}}{K}.$

[0261] “Match” is a relevance function (i.e. the more relevant Items are to keywords, the higher “match” becomes.) In one exemplary embodiment, the example function shown above may be most appropriate for a use case where keywords are only chosen from a pre-defined list of options.

[0262] In other embodiments, users may freely enter arbitrary keywords. In this sort of use case, scoring (and the “match” logic) may be implemented through a specialized document store (e.g., Solr, Lucene, Elasticsearch.). The Items may be stored into these systems as documents, and these systems may then handle indexing in a way that efficiently allows whatever custom “match” is used for controlling relevance.

[0263] In some embodiments, use of a pre-defined list may be thought of as less risky than allowing unrestricted keyword entry. To mitigate risk factors in a scalable manner, the specialized document store discussed above may be implemented. That is, the operations necessary at query time may place stronger indexing demands on the system, and conventional relational database indexes may be less optimal.

[0264] Various risks for unrestricted keyword search may be classified as polysemy and synonymy—and each of these risk factors may be mitigated with different strategies, which can be applied in any combination. Multiple strategies are described below, but one or ordinary skill would appreciate that the list is non-exhaustive and other strategies may be implemented.

[0265] Polysemy may be described as a method or process for determining/identifying how to point a single keyword (e.g., “Italian”) to different Items based on the different meanings of the keyword.

[0266] For example, if a search is performed for “Italian food”, the original example match function gives equal relevance to three different items: one tagged “Italian cuisine”, another tagged “Italian movie”, and a third tagged “Mexican food.” While only the first item is what the user may be searching for and the other two are not relevant, the above-described embodiments do not distinguish that “Italian movie” isn't “Italian food”, which is an example of polysemy.

[0267] To solve this, metadata may be included with, for example, ambiguous keywords like “Italian”—a categorical label such as: Italian:restaurant, Italian:food, or the like. This metadata may give the information needed to solve for polysemy due to the term “Italian”, because in this embodiment, a match can count matches by categories, not just by tags.

[0268] In another exemplary embodiment, a way to handle the synonymy between “cuisine” and “food” may be added (which shouldn't be counted as different terms, even though they're unequal strings.)

[0269] Synonymy may be described as a method or process for determining/identifying how to guide keyword searches towards Items, even when the keywords (e.g., input by a user) do not exactly match the Item's tags. That is, a user should find a dance studio tagged “dancing” if the user searches for “dance”. The correlation/relationship may be determined by looking at the words themselves (without requiring the system knows what the words mean.) Other examples of synonymy may require a way to acknowledge relations between the meaning of words (“Italian cuisine” should be interchangeable with “Italian food” because “cuisine” is synonymous with “food” in this context.)

[0270] Stemming and fuzzy matching are relatively inexpensive options which may be used to handle matching between words which share common grammatical structure (e.g., “dances” and “dancing” have endings which suggest they can be stemmed equivalently to dance, so that all three terms become interchangeable to users when searching for tagged Items.

[0271] Synonym files may be utilized and may acknowledge relations of meaning that are not indicated by word structure (such as the relation between “cuisine” and “food”.) Items may be tagged initially, and the synonym files may provide a way for making these tags interchangeable with the actual keywords users eventually search; this simplifies the process of tagging Items and provides a basic way to handle complex synonymy. Additionally, unknown user keywords may be classified as related to known Item tags, by inferring a model of folksonomy based on user search history, known affinities, item similarity, and other models established elsewhere. The specifics of such a model exist outside the scope of this invention, though one or ordinary skill would appreciate that such a model may be used to generate a synonym file, which may then be treated as any other synonym file for the purposes of the present invention.

[0272] Context comparison (e.g., do “dance” and “dancing” have co-occurrence with any uncommon words, like “studio”, in some reference corpus?) and Semantic scoring functions (e.g., normalized compression distance) may also be utilized.

[0273] For the basic score, the relative importance of keyword match versus affinity may be governed by a weighting parameter W_keyε[0,1]. A higher value of the weighting parameter places more emphasis on the keyword match. For a search over keywords K by user ST, the basic match score list may be computed as follows:

• [0274] 1) Select Destinations DN with |K∩K_DN|>0.
• [0275] 2) Compute an overall score for each selected Destination DN as:

score(ST,DN,K)=W_key*match(DN,K)+(1−W_key)*aff(ST,DN).

• [0276] 3) Sort Destinations by score in descending order and return the first n list elements (maintaining order), where n is the number of recommendations requested.

[0277] a) If W_key=0 then order first by affinity and use keyword match as a tiebreaker.

[0278] b) If W_key=1 then order first by keyword match and use affinity as a tiebreaker.

[0279] The boosted score may also incorporate a boosting factor. The boosting factor may be computed as:

boost(DN)=W_b*status(DN)^p

[0280] where status(DN) is the status of Destination DN and p is a configurable parameter with 0<p≦1 (default value 0.5) and W_b>0 is a configurable weighting parameter.

[0281] In some embodiments, only destinations with status(DN)>S for configurable threshold S are eligible for inclusion on the list of promoted destinations. The boosted match score list may be computed as follows:

• [0282] 1) Select Destinations DN with |K∩K_DN|>0 and with status(DN)>S.
• [0283] 2) Compute a boosted score for each selected DN as:

score_boost(ST,DN,K)=score(ST,DN,K)+boost(DN).

• [0284] 3) Sort Destinations by score in descending order and return the first m elements (maintaining order), where m is the number of boosted recommendations requested.

[0285] a) If W_b=0 then order first by basic score and use boost as a tie-breaker.

[0286] In some embodiments, Advertisements compete for impressions, clicks, and other events (“advertisement opportunities”) which only occur every so often. Scarcity creates a market for these opportunities. This market can be implemented through auctioning the opportunities to the highest bidder, with relevance adjustments made based on keyword matching and/or affinity.

[0287] In some embodiments, generalized second-price bidding may be used to auction off the opportunities. Advertisers may create their advertisement, and define a start date and end date indicating how long they want to run the ad. The advertiser may also assign a budget indicating an amount of money (e.g., a maximum, a minimum, or the like) they are willing to pay during the ad's lifetime. The aggressiveness of the advertisement is controllable by the maximum bid indicating the highest price the advertiser is willing to pay to win whatever event is being auctioned (For example, this may the maximum price the system will ever charge the advertiser per click, impression, etc. for this particular advertisement.)

[0288] When it comes time for search results to field ad placement, the same kind of boost factor used for destinations can be defined for advertisements. The boost applied to advertisements should depend on the maximum bid, if nothing else:

boost(AD)=bid_max

[0289] To help facilitate more honest bidding, the boost function may include a scheduling factor:

boost(AD)=bid_max*scheduling(AD)

[0290] The purpose of scheduling function is to exhaust the budget at an even rate throughout the lifetime of the advertisement. This may be done by introducing feedback based on how much budget is getting spent, versus how much time remains:

$\mathrm{scheduling}\left(\mathrm{AD}\right)=\frac{{\mathrm{progress}}_{\mathrm{time}}\left(\mathrm{AD}\right)+L}{{\mathrm{progress}}_{\mathrm{budget}}\left(\mathrm{AD}\right)+L}$

[0291] In this example, L is a smoothing constant, which acts to avoid division by zero without changing the intended bounds of the scheduling function (which ranges between 0 and 1 in this example.) The value of L may be between 0 and 1. The value of L may be determined experimentally.

[0292] A scheduling function equal to, for example, 1 means the budget is being spent at an appropriate rate. A scheduling function below 1 may then be indicative that the advertisement is too aggressive (e.g., winning too many auctions in too short a time.). The boost function drops, and the advertisement then spends less of the budget towards winning unlikely keywords or users. A scheduling function above 1 may then be indicative that the advertisement is not winning enough auctions, because, for example, the advertisement has not been defined aggressively enough. The advertisement may target a less relevant audience if it is to exhaust its budget within the configured duration.

[0293] In the short term, the effects of boosting may vary up and down due to the random appearance of opportunities—but in the long-run, the maximum bid will still have a constant effect on the boost. Meaning that, in some embodiments, (all else equal) the best shot of winning is by increasing your maximum bid.

${\mathrm{progress}}_{\mathrm{budget}}\left(\mathrm{AD}\right)=\frac{\mathrm{total\_spent}\left(\mathrm{AD}\right)}{\mathrm{total\_budgeted}\left(\mathrm{AD}\right)}$

[0294] The amount of time remaining versus the total time budgeted to the advertisement may be another measure of progress. This may define the schedule (in the following example, it's presumed all advertisements want to exhaust their budgets evenly over the course of the ad):

${\mathrm{progress}}_{\mathrm{time}}\left(\mathrm{AD}\right)=\frac{\mathrm{now}\left(\right)-\mathrm{starts}\left(\mathrm{AD}\right)}{\mathrm{finishes}\left(\mathrm{AD}\right)-\mathrm{starts}\left(\mathrm{AD}\right)}$

[0295] In some embodiments, the system may request recommendations from the recommendation module in real time by supplying a user ST, a location ID LID, and a list of feasible advertisements (AID1, AID2, . . . ). The advertisement recommendation module may return the list of feasible advertisements in sorted order based on the known/predicted click rates.

[0296] Because the click rate of the advertisement may be normalized with respect to location, an overall ordering of active advertisements may be maintained for each user, and new requests may use this sorted list. For each user, the active ads may be sorted in descending order by known/predicted click rate with ties broken by sorting in ascending order by number of impressions with further ties broken randomly. (Note that randomly is not equivalent to arbitrarily—the tie breaker may be random so that one advertisement is not consistently favored over another by an arbitrary rule). When the system calls for a recommendation based on a list of the feasible advertisements, the recommendation module may use the overall stored ordering for the user to sort the list of feasible ads.

[0297] There may be business considerations for selecting advertisements that fall outside of the scope of the recommendation module. For example, new advertisements with no click data may not be ranked highly by the recommendation module until a predetermined threshold of clicks have been recorded. There may therefore be a need to favor new advertisements in order to, for example, satisfy contractual requirements and/or build up click rate data that can be used by the recommendation module.

[0298] In a social media setting, a user may be presented with a social status posting tool providing various optional social states such as “Looking to”, “Going”, “I'm Here”, “On the way”, “Hanging out”. These states are optionally selected to provide the user a way to broadcast their current social interests to those on an online network they are connected with. Additionally a user may be provided the ability to type text into a text box, add tags or hashtags for specific interests, neighborhoods, or locations (ex: Live Music, Craft Beer, Southside, #partytime, @Nightclub). For example a user may select “Looking to” then type in the text: Go out #uptown for some #livemusic and maybe head to @Nightclub. Alternatively, a user may not select a social state and may simple post: Who is down for an after work happy hour later today? In either event, the system may use the social state, and scan the text that is posted by a user, and also use the tags, locations, and hashtags entered to determine the current interest of the user then importantly weigh advertisements and recommendations that are displayed to match this determined interest until the user status changes. This method allows for real time recommendations and advertisements based a user's current state of mind and interest.

[0299] Data science proposition: A different boosting function may be associated for each different social state when ranking search results (depending which data features are relevant to that state). For example, “I'm here”, “on the way”, “going” may use a boosting function which emphasizes the geo-location of associated text; whereas “looking to” may use a boosting function which prioritizes the window of opportunity (start and end dates) on advertisements; whereas “hanging out” may influence result rankings based on the historical information of mentioned users.

[0300] Alternatively or additionally, the system may begin to weight advertisements and recommendations when the user selects a social state, but before they make the post. For example, once the user selects “Looking to”, the system recognizes the geographic area of the user via a profile city selection or GPS, and then presents advertisements based on the “looking to” selection, and behavioral knowledge of the user. This would then change once the user has posted, as the system then combines any text entered, along with any tags, as described above

[0301] The models above (i.e. the item-based similarity model, the user-based similarity model, and the global average model) each include a common example application, which assumes a hypothetical set of features. In some embodiments, if the features were different, the formulas associated with each may change.

[0302] One or more additional (i.e. other) hypothetical features may be added, for example, as long as the feature can be measured in the dimension of a User-User, Item-Item or User-Item Relation. Methods for modifying the above-disclosed embodiments, based on whichever hypothetical interactions might be added between Users and Items in the future are described herein. The hybrid User-based CF model can be tuned to achieve higher accuracy or coverage than a non-hybrid model on the same data; the same applies for the Item-based and GA models. By configuring each engine to different partitions of User space, the engine with the highest accuracy in the partition can be run for any User in that partition's region. The engine with the best performance in a region of User space may be configured to run for the Users in that region of User space. This helps efficiently covers more User space with better accuracy than running a single classifier to predict the same input data.

[0303] As features are added, new kinds of contents and interaction become possible. The formulas used to model affinity/similarity may then change to account for these new Relations. The dimension of this Relation is measured by a data type, which determines the appropriate change needed in the formulas.

[0304] In some embodiments, the system may be configured to normalize the new dimension's measure. That is, dimensions may need to be normalized before they are combined into an Affinity or Similarity.

[0305] A plurality of strategies for Normalizing Binary Measures exist, some of which are described below.

[0306] Binary Relation=>include as an indicator term . . .

• • [0307] (Binary User-User Relation)=> . . . in User Similarity in (as with gender.)
  • [0308] (Binary User-Item Relation)=>in Affinity (as with favorite destinations.)
  • [0309] (Binary Item-Item Relation)=>in Item Similarity (as with advertisement's Business ID.)

[0310] Relation between sets=>transform using set similarity . . .

• • [0311] New disjoint set=> . . . concatenate with existing sets (as with a new interest category.)
  • [0312] New dependent set=> . . . requires a new pattern (explained later in this document.)

[0313] A plurality of strategies for Normalizing Continuous Measures exist, some of which are described below.

[0314] Bounded above AND below (such as ratings)=>

• • [0315] Linear Interpolation (“change of scale”)
  • [0316] Logarithmic transform=>as with estimated affinity [doc #60, section 191]

[0317] Bounded above OR below (such as counts)=>transform below a threshold

• • [0318] Horizontal asymptotic transform=>if you want diminishing returns, as with activations.
    • [0319] Piecewise linear transform (“clamping”)=>if you don't want diminishing returns.
  • [0320] Unbounded=>transform into an upper and lower sub-function, bounded by the same value.

[0321] The system may then be configured to weight the normalized measure. When a new dimension is weighted against old dimensions, the system may be configured to fix the sum of weights before and after adding the new dimension. In other words, when a new dimension is added with a certain weight (relative to the existing dimensions), the system may be configured to: (1) Find the ratios between the original weights; (2) Reduce these weights proportionally; and (3) Continue until the deficit (from the old total) equals the desired weight of the new dimension.

[0322] Subsequent to weighting the normalized measure, it should be appreciated that the system may then utilize similar calculations as above, using modified formulas. The process for identifying which equation to modify is discussed below.

[0323] In some embodiments, the system may be configured to first combine behaviors with behaviors, separately combine content with content, and finally combine the total behavioral contribution to a total content-based contribution.

[0324] In one exemplary embodiment, if adding a new behavioral dimension, the equation for computed behavioral Affinity may be modified. The total weight of all dimensions would remain constant (e.g., 1).

[0325] In another exemplary embodiment, if adding a new content-based User dimension, the computed User Similarity may be modified (adjusting weights out of the original constant sum.)

[0326] In yet another exemplary embodiment, if adding a new content-based Item dimension, I'd modify the computed Item Similarity (adjusting weights out of the original constant sum.)

[0327] In some embodiments, while any of the above-identified equations may be modified, the above choices may be the most manageable. Note that the equations for Total Affinity and Total Similarity may be modified. However, the equations for Total Affinity and Total Similarity are not where new dimensions are intended to go. That is, while adding new dimensions (Relations) directly to this level of calculation is possible, it may not be the most sustainable approach (e.g., it makes it harder to measure achievement of the benefits claimed in particular embodiments of the present invention.)

[0328] Set similarity is used to compare how much two sets overlap, and is readily applied to features such as tags in a profile (or words in documents, etc.). In a list of possible items, which are either chosen or not chosen, set-similarity is a natural model for comparing records of such lists.

[0329] Some embodiments of the present invention include set similarity between user “interests” as part of the over-all User Similarity. Below is the socio-demographic component of User Similarity (taken from above).

${\mathrm{sim}}_{\mathrm{sd}}\left({\mathrm{ST}}_1,{\mathrm{ST}}_2\right)=\frac{W_aa_{{\mathrm{ST}}_1}a_{{\mathrm{ST}}_2}+W_gg_{{\mathrm{ST}}_1}g_{{\mathrm{ST}}_2}+{\mathrm{ST}}_1\mathrm{interests}\bigcap {\mathrm{ST}}_2\mathrm{interests}}{\sqrt{W_a+W_g+{\mathrm{ST}}_1\mathrm{interests}}*\sqrt{W_a+W_g+{\mathrm{ST}}_2\mathrm{interests}}}$

[0330] A part of the equation calculates the set-similarity. These terms work to ensure that users become more/less similar based on how much their interests overlap.

[0331] Adding new Dimensions—Disjoint Sets

[0332] The above equation, which is described above stating that “the interest dimensions may be concatenated into a single list for each ST.” Interests can be broken down into sports, drinks, and various other lists of tags (which don't overlap.) Because none of the categories have overlapping options, a new category (or categories) may be added without changing the original equation, new disjoint dimension are concatenated with the existing disjoint dimensions.

[0333] Adding new Dimensions—Dependent Sets

[0334] The system may, in some embodiments, be configured to account for users disliking things other people are interested in. That is, “being different” is certainly a source of human preference and accordingly, the system may seek to avoid recommending a user to a tailgate for the wrong sports team. To help ensure this does not happen, a new dimension may be added which was dependent with interests—not a new category, but a second set of options covering the same items.

[0335] “Dislikes” isn't a category of “interests”—they share the same categories, and the same items in those categories. And “dislikes” and “interests” aren't disjoint—if the system already knows a user dislikes X, then it can be immediately known (or assumed) that the user is not interested in X.

[0336] As such, the original pattern (one set similarity, between two large, concatenated lists) will not work and the approach is modified. The modification maintains existing similarity properties, while capturing the disjoint information properly—and as such, changes may be restricted. For example, the changes may be restricted by the following:

[0337] As interests overlap, User Similarity increases.

[0338] As dislikes overlap, User Similarity increases.

[0339] As one user's interests overlap the other's dislikes, User Similarity decreases.

[0340] These three overlaps contribute to Similarity at equal rates.

[0341] The Similarity Relation remains symmetric.

[0342] The weight of the non-set-like dimensions should remain unchanged.

[0343] The simplest solution to these requirements is as follows:

|ST₁ interests ∩ST₂ interests| becomes

(|ST₁ interests∩ST₂ interests|+|ST₁ dislikes∩ST₂ dislikes|−|ST₁ interests∩ST₂ dislikes|−|ST₁ dislikes∩ST₂ interests|)

|ST₁ interests| becomes½(|ST₁ interests|+|ST₁ dislikes|)

|ST₂ interests| becomes ½(|ST₂ interests|+|ST₂ dislikes|)

[0344] As one or ordinary skill would appreciate that while this example is for adding “dislikes”, it could be applied for just as well if there were a dependent set dimension added to the firmographics for destinations, or any dependent set-like dimensions that might be added to ads, deals or other Items.

[0345] Note that the above example uses very precise definitions for the terms User and Item. That is, a user is only a “User” if the user satisfies the requirements of a User as defined by this document's “Definitions” section. If referring to users in general (whether or not they are also Users), the term “user” is used.

[0346] Example 1: an individual user, requesting deals

[0347] Example 2: a group of users planning a night out, requesting recommended destinations.

[0348] User—anything that can request recommendations. (e.g., the individual user, the group.)

[0349] Item—anything that can be recommended to a User. (e.g., deals, destinations, etc.)

[0350] Relation—Relations (e.g. “friendship”) are assigned to watch different actions (e.g. “adding a friend”, “removing a friend”). Relations can watch for behavioral signals, or content-based signals, or both (a Relation can be formed by combining simpler Relations, whether by joining in-database, or using a sub-function in the processor, and so on.)

[0351] Type—a thing's Type is what restricts the thing's available interactions. Users and Items aren't the same Type because “being an Item” doesn't guarantee you can request recommendations, whereas “being a User” always guarantees you can request recommendations.

[0352] A thing can have many Types—a user might be modeled as both a User and an Item, if destinations were able to request recommended patrons.

[0353] A Type can be generalized out of other, more specific Types—a “group” of users and an “individual” user are both Types of User (because both can receive recommendations). Even so, two “groups” cannot be friends the way two “individuals” can—making “groups” and “individuals” different Types (both within the same broader Type, User.)

[0354] User-User Relation—a Relation that records signs of User similarity. (e.g. ‘friendship’)

[0355] User-Item Relation—a Relation that records signs of affinity. (e.g. ‘activating’)

[0356] Item-Item Relation—a Relation that records signs of Item similarity (e.g. ‘favorited by the same users?’)

[0357] As described above, the present invention is directed to a method of solving the cold-start problem for collaborative filtering (CF) recommendation engines. The cold-start problem occurs when the CF engine is required to produce a recommendation for a given end user, and either lacks sufficient data describing that end user's preferences, or lacks sufficient data describing other end users' preferences, to compute the recommendation. A cold-start problem similarly occurs when a new item is added.

[0358] As described earlier, in some embodiments, the item-based collaborative filtering model may require a sufficient amount of affinity data for a given user in order to predict their unknown preferences. As such, for a newly registered user or a user with limited recorded activity, the item-based collaborative filtering model may not perform well. This is known and has been described herein as the user cold start problem.

[0359] FIG. 5 is a flowchart illustrating an example method that may be performed by the recommendation module in order to overcome the cold start problem, in accordance with some example embodiments described herein.

[0360] As is shown in operation 505, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for receiving a recommendation request, the recommendation request comprising identification information indicative of a target user and a set of search terms, the set of search terms comprised of zero or more search terms.

[0361] As is shown in operation 510, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for identifying whether the identification information is indicative of a new user.

[0362] As is shown in operation 515, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for in an instance in which the identification information is indicative of a new user, querying a set of (new user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching.

[0363] As is shown in operation 520, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for in an instance in which the identification information is indicative of a known user, querying a set of (target user, affinity) pairs for items matching the search terms and sorting the matching items according to a combination of the affinities and a strength of text matching.

[0364] In some embodiments, preceding reception of the recommendation request, a preprocessing method may be performed. FIG. 6 is a flowchart illustrating an example method that may be performed by the recommendation module or the like, prior to receiving a recommendation request, in accordance with some example embodiments described herein

[0365] As is shown in operation 605, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for accessing, for each of at least one known users and at least one item, all related expressed affinities, behavioral data, firmographic variables, and socio-demographic variables.

[0366] As is shown in operation 610, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for setting a user-item affinity to an expressed affinity in an instance in which the user provided an affinity for the item explicitly.

[0367] As is shown in operation 615, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for calculating a computed affinity as a function of available behavioral data and setting the user-item affinity to the computed affinity in the absence of the user providing an affinity for the item explicitly and in an instance in which a number of instances of behavioral data meets a threshold.

[0368] As is shown in operation 620, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for in absence of an expressed affinity and a computed affinity, calculating an inferred affinity using one of a plurality of collaborative filtering algorithms. Determining which collaborative filtering algorithm to utilize in calculating the inferred affinity is described with reference to FIG. 7.

[0369] As is shown in operation 705, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for calculating the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing an item-based collaborative filtering algorithm in an instance in which a number of user-item interactions meets a first predetermined threshold. The item-based collaborative filtering algorithm is described above with reference to FIGS. 2A and 2B. That is, FIG. 2A describes the item-based collaborative filtering algorithm when the item is a destination and FIG. 2B described the item-based collaborative filtering algorithm when the item is an advertisement.

[0370] As is shown in operation 710, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for calculating the inferred affinity for a user item pair, for user-item pairs in which the user is modeled, utilizing a user-based collaborative filtering algorithm in an instance in which the number of user-item interactions fails to meet the first predetermined threshold, extending it to account for socio-demographic variables. The user-based collaborative filtering algorithm is described above with reference to FIGS. 3A and 3B. That is, FIG. 3A describes the user-based collaborative filtering algorithm when the item is a destination and FIG. 3B described the user-based collaborative filtering algorithm when the item is an advertisement.

[0371] As is shown in operation 715, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for calculating the inferred affinity for a user item pair, for user-item pairs in which the user is not modeled, utilizing a global average algorithm. The global average filtering algorithm is described above with reference to FIGS. 4A and 4B. That is, FIG. 4A describes the global average collaborative filtering algorithm when the item is a destination and FIG. 42B described the global average collaborative filtering algorithm when the item is an advertisement.

[0372] Returning now to FIG. 6, once the inferred affinity is calculated as described above, the user-item affinity is set to the inferred affinity. As is shown in operation 625, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for setting the user-item affinity to the inferred affinity.

[0373] As is shown in operation 630, an apparatus, such as computing system 500, may include means, such as the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114, the processor 803, or the like, for merging results into the set of (user, affinity) pairs, each item having a corresponding user-item pair, global averages having identification information indicative of a new user, known users having identification information indicative of a known user.

[0374] FIG. 8 is an example block diagram of an example computing device for practicing embodiments of an example recommendation module. In particular, FIG. 8 shows a computing system 800 that may be utilized to implement a social media environment 100 having a recommendation module 106 including, in some examples, behavioral model 108, item-based collaborative filtering module 110, a user-based collaborative filtering module 112 and/or a global average module 114 and/or a user interface 810. One or more general purpose or special purpose computing systems/devices may be used to implement the recommendation module 106 and/or the user interface 810. In addition, the computing system 800 may comprise one or more distinct computing systems/devices and may span distributed locations. In some example embodiments, the recommendation module 106 may be configured to operate remotely via the network 850, such that one or more client devices may access the recommendation module 106 via an application, webpage or the like. In other example embodiments, a pre-processing module or other module that requires heavy computational load may be configured to perform that computational load and thus may be on a remote device or server. For example, behavior model 108, the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114 may be accessed remotely. In other example embodiments, a user device may be configured to operate or otherwise access the recommendation module 106. Furthermore, each block shown may represent one or more such blocks as appropriate to a specific example embodiment. In some cases one or more of the blocks may be combined with other blocks. Also, the recommendation module 106 may be implemented in software, hardware, firmware, or in some combination to achieve the capabilities described herein.

[0375] In the example embodiment shown, computing system 800 comprises a computer memory (“memory”) 801, a display 802, one or more processors 803, input/output devices 804 (e.g., keyboard, mouse, CRT or LCD display, touch screen, gesture sensing device and/or the like), other computer-readable media 806, and communications interface 807. The processor 803 may, for example, be embodied as various means including one or more microprocessors with accompanying digital signal processor(s), one or more processor(s) without an accompanying digital signal processor, one or more coprocessors, one or more multi-core processors, one or more controllers, processing circuitry, one or more computers, various other processing elements including integrated circuits such as, for example, an application-specific integrated circuit (ASIC) or field-programmable gate array (FPGA), or some combination thereof. Accordingly, although illustrated in FIG. 8 as a single processor, in some embodiments the processor 803 comprises a plurality of processors. The plurality of processors may be in operative communication with each other and may be collectively configured to perform one or more functionalities of the recommendation module as described herein.

[0376] The recommendation module 106 is shown residing in memory 801. The memory 801 may comprise, for example, transitory and/or non-transitory memory, such as volatile memory, non-volatile memory, or some combination thereof. Although illustrated in FIG. 8 as a single memory, the memory 801 may comprise a plurality of memories. The plurality of memories may be embodied on a single computing device or may be distributed across a plurality of computing devices collectively configured to function as the recommendation module. In various example embodiments, the memory 801 may comprise, for example, a hard disk, random access memory, cache memory, flash memory, a compact disc read only memory (CD-ROM), digital versatile disc read only memory (DVD-ROM), an optical disc, circuitry configured to store information, or some combination thereof. In some examples, the recommendation module 106 may be stored remotely, such that it resides in a “cloud.”

[0377] In other embodiments, some portion of the contents, some or all of the components of the recommendation module 106 may be stored on and/or transmitted over the other computer-readable media 806. The components of the recommendation module 106 preferably execute on one or more processors 803 and are configured to enable operation of a recommendation module, as described herein.

[0378] Alternatively or additionally, other code or programs 840 (e.g., an administrative interface, one or more application programming interface, a Web server, and the like) and potentially other data repositories, such as other data sources 808, also reside in the memory 801, and preferably execute on one or more processors 803. Of note, one or more of the components in FIG. 8 may not be present in any specific implementation. For example, some embodiments may not provide other computer readable media 806 or a display 802.

[0379] The recommendation module 106 is further configured to provide functions such as those described with reference to FIGS. 2A, 2B, 3A, 3B, 4A, 4B, 5, 6, and 7. The recommendation module 106 may interact with the network 850, via the communications interface 807, with remote content 860, such as third-party content providers, and one or more client devices operated by users 102, and/or items 104. The network 850 may be any combination of media (e.g., twisted pair, coaxial, fiber optic, radio frequency), hardware (e.g., routers, switches, repeaters, transceivers), and protocols (e.g., TCP/IP, UDP, Ethernet, Wi-Fi, WiMAX, Bluetooth) that facilitate communication between remotely situated humans and/or devices. In some instances, the network 850 may take the form of the internet or may be embodied by a cellular network such as an LTE based network. In this regard, the communications interface 807 may be capable of operating with one or more air interface standards, communication protocols, modulation types, access types, and/or the like. Client devices include, but are not limited to, desktop computing systems, notebook computers, mobile phones, smart phones, personal digital assistants, tablets and/or the like. In some example embodiments, a client device may embody some or all of computing system 800.

[0380] In an example embodiment, components/modules of the recommendation module 106 are implemented using standard programming techniques. For example, the recommendation module 106 may be implemented as a “native” executable running on the processor 803, along with one or more static or dynamic libraries. In other embodiments, the recommendation module 106 may be implemented as instructions processed by a virtual machine that executes as one of the other programs 840. In general, a range of programming languages known in the art may be employed for implementing such example embodiments, including representative implementations of various programming language paradigms, including but not limited to, object-oriented (e.g., Java, C++, C#, Visual Basic.NET, Smalltalk, and the like), functional (e.g., ML, Lisp, Scheme, and the like), procedural (e.g., C, Pascal, Ada, Modula, and the like), scripting (e.g., Perl, Ruby, Python, JavaScript, VBScript, and the like), and declarative (e.g., SQL, Prolog, and the like).

[0381] The embodiments described above may also use synchronous or asynchronous client-server computing techniques. Also, the various components may be implemented using more monolithic programming techniques, for example, as an executable running on a single processor computer system, or alternatively decomposed using a variety of structuring techniques, including but not limited to, multiprogramming, multithreading, client-server, or peer-to-peer, running on one or more computer systems each having one or more processors. Some embodiments may execute concurrently and asynchronously, and communicate using message passing techniques. Equivalent synchronous embodiments are also supported. Also, other functions could be implemented and/or performed by each component/module, and in different orders, and by different components/modules, yet still achieve the described functions.

[0382] In addition, programming interfaces to the data stored as part of the recommendation module 106, such as by using one or more application programming interfaces can be made available by mechanisms such as through application programming interfaces (API) (e.g., C, C++, C#, and Java); libraries for accessing files, databases, or other data repositories; through scripting languages such as XML; or through Web servers, FTP servers, or other types of servers providing access to stored data. The data sources 808 may be implemented as one or more database systems, file systems, or any other technique for storing such information, or any combination of the above, including implementations using distributed computing techniques and may provide relevant data to the behavior model 108, the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114. Alternatively or additionally, the behavior model 108, the item-based collaborative filtering module 110, the user-based collaborative filtering module 112 and/or the global average module 114 may have access to local data stores but may also be configured to access data from one or more remote data sources.

[0383] Different configurations and locations of programs and data are contemplated for use with techniques described herein. A variety of distributed computing techniques are appropriate for implementing the components of the illustrated embodiments in a distributed manner including but not limited to TCP/IP sockets, RPC, RMI, HTTP, Web Services (XML-RPC, JAX-RPC, SOAP, and the like). Other variations are possible. Also, other functionality could be provided by each component/module, or existing functionality could be distributed amongst the components/modules in different ways, yet still achieve the functions described herein.

[0384] Furthermore, in some embodiments, some or all of the components of the recommendation module 106 may be implemented or provided in other manners, such as at least partially in firmware and/or hardware, including, but not limited to one or more ASICs, standard integrated circuits, controllers executing appropriate instructions, and including microcontrollers and/or embedded controllers, FPGAs, complex programmable logic devices (“CPLDs”), and the like. Some or all of the system components and/or data structures may also be stored as contents (e.g., as executable or other machine-readable software instructions or structured data) on a computer-readable medium so as to enable or configure the computer-readable medium and/or one or more associated computing systems or devices to execute or otherwise use or provide the contents to perform at least some of the described techniques. Some or all of the system components and data structures may also be stored as data signals (e.g., by being encoded as part of a carrier wave or included as part of an analog or digital propagated signal) on a variety of computer-readable transmission mediums, which are then transmitted, including across wireless-based and wired/cable-based mediums, and may take a variety of forms (e.g., as part of a single or multiplexed analog signal, or as multiple discrete digital packets or frames). Such computer program products may also take other forms in other embodiments. Accordingly, embodiments of this disclosure may be practiced with other computer system configurations.

[0385] FIGS. 2A, 2B, 3A, 3B, 4A, 4B, 5, 6, and 7 illustrate example flowcharts of the operations performed by an apparatus, such as computing system 800 of FIG. 8, in accordance with example embodiments of the present invention. It will be understood that each block of the flowcharts, and combinations of blocks in the flowcharts, may be implemented by various means, such as hardware, firmware, one or more processors, circuitry and/or other devices associated with execution of software including one or more computer program instructions. For example, one or more of the procedures described above may be embodied by computer program instructions. In this regard, the computer program instructions which embody the procedures described above may be stored by a memory 801 of an apparatus employing an embodiment of the present invention and executed by a processor 803 in the apparatus. As will be appreciated, any such computer program instructions may be loaded onto a computer or other programmable apparatus (e.g., hardware) to produce a machine, such that the resulting computer or other programmable apparatus provides for implementation of the functions specified in the flowcharts' block(s). These computer program instructions may also be stored in a non-transitory computer-readable storage memory that may direct a computer or other programmable apparatus to function in a particular manner, such that the instructions stored in the computer-readable storage memory produce an article of manufacture, the execution of which implements the function specified in the flowcharts' block(s). The computer program instructions may also be loaded onto a computer or other programmable apparatus to cause a series of operations to be performed on the computer or other programmable apparatus to produce a computer-implemented process such that the instructions which execute on the computer or other programmable apparatus provide operations for implementing the functions specified in the flowcharts' block(s). As such, the operations of FIGS. 2A, 2B, 3A, 3B, 4A, 4B, 5, 6, and 7, when executed, convert a computer or processing circuitry into a particular machine configured to perform an example embodiment of the present invention. Accordingly, the operations of FIGS. 2A, 2B, 3A, 3B, 4A, 4B, 5, 6, and 7 define an algorithm for configuring a computer or processor, to perform an example embodiment. In some cases, a general purpose computer may be provided with an instance of the processor which performs the algorithm of FIGS. 2A, 2B, 3A, 3B, 4A, 4B, 5, 6, and 7 to transform the general purpose computer into a particular machine configured to perform an example embodiment.

[0386] Accordingly, blocks of the flowcharts support combinations of means for performing the specified functions and combinations of operations for performing the specified functions. It will also be understood that one or more blocks of the flowcharts, and combinations of blocks in the flowcharts, can be implemented by special purpose hardware-based computer systems which perform the specified functions, or combinations of special purpose hardware and computer instructions.

[0387] In some example embodiments, certain ones of the operations herein may be modified or further amplified as described herein. Moreover, in some embodiments additional optional operations may also be included. It should be appreciated that each of the modifications, optional additions or amplifications described herein may be included with the operations herein either alone or in combination with any others among the features described herein.

[0388] Many modifications and other embodiments of the inventions set forth herein will come to mind to one skilled in the art to which these inventions pertain having the benefit of the teachings presented in the foregoing descriptions and the associated drawings. Therefore, it is to be understood that the inventions are not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Moreover, although the foregoing descriptions and the associated drawings describe example embodiments in the context of certain example combinations of elements and/or functions, it should be appreciated that different combinations of elements and/or functions may be provided by alternative embodiments without departing from the scope of the appended claims. In this regard, for example, different combinations of elements and/or functions than those explicitly described above are also contemplated as may be set forth in some of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.