Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
  • G06Q30/00—Commerce
  • G06Q30/02—Marketing; Price estimation or determination; Fundraising
  • G06Q30/0241—Advertisements
  • G06Q30/0273—Determination of fees for advertising
  • G06Q30/0275—Auctions
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
  • G06N20/00—Machine learning
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
  • G06Q30/00—Commerce
  • G06Q30/02—Marketing; Price estimation or determination; Fundraising
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
  • G06Q30/00—Commerce
  • G06Q30/02—Marketing; Price estimation or determination; Fundraising
  • G06Q30/0241—Advertisements
  • G06Q30/0242—Determining effectiveness of advertisements
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
  • G06Q30/00—Commerce
  • G06Q30/02—Marketing; Price estimation or determination; Fundraising
  • G06Q30/0241—Advertisements
  • G06Q30/0251—Targeted advertisements
  • G06Q30/0254—Targeted advertisements based on statistics
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
  • G06Q30/00—Commerce
  • G06Q30/02—Marketing; Price estimation or determination; Fundraising
  • G06Q30/0241—Advertisements
  • G06Q30/0251—Targeted advertisements
  • G06Q30/0255—Targeted advertisements based on user history

Definitions

• the present invention relates to the application of machine learning models for predicting behaviour of online users.
• embodiments of the invention predict likelihood of user interaction with online content elements based upon aggregated behaviour of prior users in similar contexts.
• the invention may be applied in online advertising systems, for example to determine whether or not to bid for placement of an advertisement to be presented to a user, e.g. via a web page on within a mobile app.
• Online (e.g. web-based, mobile, or in-app) advertising differs from advertising in traditional media in its degree of personalised audience targeting.
• broadcast media advertising such as television advertising
• online advertising aims to reach individuals having a particular interest in the product, service, or information that is presented.
• Advertisers whose
• advertisements appear on these websites may pay the operator on the basis of viewing opportunities or impressions (commonly measured as 'cost per thousand impressions', a.k.a. CPM), on the basis of a cost per click (CPC), or according to some other measure of performance.
• the actual selection of an advertisement to be placed on a web page presented to an individual user may be based, at least in part, on a bidding process whereby an advertiser who is willing to pay a higher CP , CPC, or other cost measure, is more likely to have its advertisement presented to the user.
• the bidding process is facilitated by an 'ad exchange platform'.
• An ad exchange is a technology platform that implements a digital marketplace allowing advertisers and publishers of web sites and other online content to buy and sell advertising space, often through real-time auctions.
• Well-known ad exchange platforms include DoubleclickTM (owned by GoogleTM), AppNexusTM, MicrosoftTM Ad ExchangeTM, and OpenXTM.
• An ad exchange maintains a 'pool' of ad slots. Publishers contribute their ad slots, e.g. available advertising slots embedded within web pages served to users, into the pool. Buyers can then bid for the slots that they wish to purchase. Bidding decisions are often made in real time based on information such as the previous behaviour of the user an ad is being served to, time of day, device type, ad position, and so forth. In practice, these bidding decisions must themselves be made very rapidly, e.g. in at most a few tens of milliseconds, using technology platforms commonly known as demand side platforms (DSPs). Since there is a real cost to the advertiser in purchasing impressions through an ad exchange, the performance of technologies and algorithms deployed in a DSP for assessing the potential 'value' of a user in order to make a bid decision may have a significant business impact.
• DSPs demand side platforms
• an average click through rate (CTR) for web-based display ads is around 0.05%, i.e. five clicks per 10,000 impressions.
• every impression represents a cost (i.e. the price paid following a winning bid).
• CTR average click through rate
• a low CTR thus results in an inefficient use of technical resources (such as the processing resources of the DSP) and a higher cost to successful advertisers (since a smaller number of 'clicks' must cover the cost of all impressions).
• a low CTR is indicative of a lack of suitability or relevance of the displayed advertising to online users.
• One common approach to increasing CTR employs online tracking to infer user interests and to place advertising content that is relevant to those interests.
• browser cookies and other tracking technologies may be used to gather information regarding, for example, web sites visited by a user, topics viewed on social media sites, and/or online searches conducted by the user. Such information may be processed to identify advertising content that is inferred to be relevant to the user.
• predicting the likelihood that the user will interact with such content is more difficult.
• average CTR is low, and individual online users therefore rarely interact with advertising content, even when it has been effectively targeted based on user interests. There is, accordingly, very little direct data that can be used to predict the likelihood of users interacting with advertising content on the basis of individual user tracking.
• the present invention provides a computer-implemented method comprising:
• matched data set which comprises a plurality of records, each record of the matched data set including a set of raw feature values derived from a content placement event along with an interaction event tag indicating whether or not an interaction event occurred corresponding with the content placement event;
• an enriched estimation feature vector based upon a content item selected for placement within the online content placement slot, the information relating to the user, and the information relating to the online content placement slot;
• embodiments of the invention employ matching of aggregated content placement events with aggregated user interaction events to support prediction of online user interactions with content using a machine learning model.
• Content items may be, for example, online ads comprising one or more offers, and the user interaction events may comprise interactions such as clicks on specific offers within the ads. Accordingly, in such embodiments:
• the online content placement slot is an ad slot
• the information relating to the ad slot and information relating to the user to whom content within the ad slot will be displayed is received along with a bid request message transmitted from an ad exchange server;
• the content item comprises at least one offer for placement within the ad slot.
• the method may further comprise:
• embodiments of the invention provide for continuous updating of the stored records of content placement events and user interaction events, enabling the machine learning model to be updated with current information regarding user behaviour.
• the method may comprise repeatedly executing the steps of accessing the online data store, matching the retrieved content placement event records with the retrieved interaction event records, computing enriched training feature vectors, and training the machine learning model.
• the invention provides a computing apparatus which implements a demand side platform, the computing apparatus comprising:
• the memory device contains a body of program instructions including a machine learning model which is executable by the processor and configured to determine an estimate of likelihood of user interaction with a content item, the model having been trained using a set of enriched training feature vectors and corresponding interaction event tags derived from a matched data set generated from records relating to content placement events and records relating to user interaction events retrieved from an online data store wherein the placement and interaction events occur within a defined time period,
• the body of program instructions further including instructions which, when executed by the processor, cause the computing apparatus to implement a method comprising steps of:
• the machine learning model is a generalised linear model comprising a plurality of model coefficients, and in particular the machine learning model may be a logistic regression model.
• the plurality of model coefficients may be stored in a dictionary data structure in which each entry is defined by a key and a coefficient value, wherein each key comprises a hashed representation of a concatenation of a feature name and a corresponding feature value.
• the use of this type of data structure enables a prediction of the likelihood of a user interaction to be computed very rapidly, e.g. within 30 ms.
• the program instructions may thus cause the computing apparatus to implement the step of executing the machine learning model by:
• the online content placement slot is an ad slot
• the information relating to the ad slot and information relating to the user to whom content within the ad slot will be displayed is received along with a bid request message transmitted from an ad exchange server
• the content item comprises at least one offer for placement within the ad slot
• the body of program instructions may further include instructions which, when executed by the processor, cause the computing apparatus to implement the method comprising further steps of:
• the invention provides a computing apparatus which implements training of a machine learning model configured to estimate of likelihood of user interaction with content items, the computing apparatus comprising:
• the memory device contains a body of program instructions including instructions which, when executed by the processor, cause the computing apparatus to implement a method comprising steps of:
• each record of the matched data set including a set of raw feature values derived from a content placement event along with an interaction event tag indicating whether or not an interaction event occurred corresponding with the content placement event;
• the machine learning model is a logistic regression model comprising a plurality of model coefficients
• the program instructions cause the computing apparatus to implement the step of training the machine learning model using regularised logistic regression with 'follow-the-regularised-leader' (FTRL)-proximal learning.
• the body of program instructions may further include instructions which, when executed by the processor, cause the computing apparatus to implement the method comprising further steps, for each coefficient of the plurality of model coefficients, of:
• generating a key comprising a hashed representation of a feature name and a feature value corresponding with the coefficient
• the dictionary data structure comprises an efficient encoding of the machine learning model.
• the body of program instructions may include instructions which, when executed by the processor, cause the computing apparatus to repeatedly execute the steps of accessing the online data store, matching the retrieved content placement event records with the retrieved interaction event records, computing (406) enriched training feature vectors, and training the machine learning model, to update the machine learning model.
• the invention provides a computer program comprising program code instructions for executing the steps of the method according to the first aspect when said program is executed on a computer.
• the program code instructions may, for example, be stored on tangible machine- readable media.
• Figure 1 is a schematic diagram illustrating an exemplary networked system embodying the invention
• Figure 2 shows a timeline of communications between a user device, a web server, and ad exchange server, and a DSP embodying the invention
• Figure 3 is a block diagram illustrating schematically a number of code modules comprising an online user interaction prediction engine embodying the invention
• Figure 4 shows a flowchart of a method of online updating of a machine learning model embodying the invention
• Figure 5 shows a flowchart of a method of feature engineering and model hyperparameter optimisation according to an embodiment of the invention
• Figure 6 shows a flowchart of a method of operating a real-time bidding module according to an embodiment of the invention.
• Figures 7(a) and 7(b) show charts illustrating performance of a realtime bidding module embodying the invention.
• FIG. 1 is a block diagram illustrating an exemplary networked system 100 including a demand side platform (DSP) server 102, which is configured to implement a method of bidding for placement of advertising content in accordance with an embodiment of the invention.
• the DSP server 102 may comprise a computer system having a conventional architecture.
• the DSP server 102 as illustrated, comprises a processor 104.
• the processor 104 is operably associated with a non-volatile memory/storage device 106, e.g. via one or more data/address busses 108 as shown.
• the non-volatile storage 106 may be a hard disk drive, and/or may include a solid-state non-volatile memory, such as ROM, flash memory, solid-state drive (SSD), or the like.
• the processor 104 is also interfaced to volatile storage 110, such as RAM, which contains program instructions and transient data relating to the operation of the DSP server 102.
• the storage device 106 maintains known program and data content relevant to the normal operation of the DSP server 102.
• the storage device 106 may contain operating system programs and data, as well as other executable application software necessary for the intended functions of the authentication server 102.
• the storage device 106 also contains program instructions which, when executed by the processor 104, cause the DSP server 102 to perform operations relating to an embodiment of the present invention, such as are described in greater detail below, and with reference to Figures 2 and 6 in particular. In operation, instructions and data held on the storage device 106 are transferred to volatile memory 110 for execution on demand.
• the processor 104 is also operably associated with a communications interface 112 in a conventional manner.
• the communications interface 112 facilitates access to a wide-area data communications network, such as the Internet 116.
• the volatile storage 110 contains a corresponding body 114 of program instructions transferred from the storage device 106 and configured to perform processing and other operations embodying features of the present invention.
• the program instructions 114 comprise a specific technical contribution to the art in accordance with the invention, as further described below.
• DSP server 102 and other processing systems and devices described in this specification, terms such as 'processor', 'computer' , and so forth, unless otherwise required by the context, should be understood as referring to a range of possible implementations of devices, apparatus and systems comprising a combination of hardware and software.
• Physical processors may include general purpose CPUs, digital signal processors, graphics processing units (GPUs), and/or other hardware devices suitable for efficient execution of required programs and algorithms.
• Computing systems may include conventional personal computer architectures, or other general-purpose hardware platforms.
• Software may include open-source and/or commercially-available operating system software in combination with various application and service programs.
• computing or processing platforms may comprise custom hardware and/or software architectures.
• computing and processing systems may comprise cloud computing platforms, enabling physical hardware resources to be allocated dynamically in response to service demands. While all of these variations fall within the scope of the present invention, for ease of explanation and understanding the exemplary embodiments described herein are based upon single-processor general-purpose computing platforms, commonly available operating system platforms, and/or widely available consumer products, such as desktop PCs, notebook or laptop PCs, smartphones, tablet computers, and so forth.
• processing unit' is used in this specification (including the claims) to refer to any suitable combination of hardware and software configured to perform a particular defined task, such as accessing and processing offline or online data, executing training steps of a machine learning model, or executing prediction steps of a machine learning model.
• a processing unit may comprise an executable code module executing at a single location on a single processing device, or may comprise cooperating executable code modules executing in multiple locations and/or on multiple processing devices.
• classification and bid decision processing may be performed entirely by code executing on DSP server 102, while in other embodiments corresponding processing may be performed is a distributed manner over a plurality of DSP servers.
• Software components e.g. program instructions 114, embodying features of the invention may be developed using any suitable programming language, development environment, or combinations of languages and development environments, as will be familiar to persons skilled in the art of software engineering.
• suitable software may be developed using the C programming language, the Java programming language, the C++ programming language, the Go programming language, and/or a range of languages suitable for implementation of network or web-based services, such as JavaScript, HTML, PHP, ASP, JSP, Ruby, Python, Perl, and so forth. These examples are not intended to be limiting, and it will be appreciated that convenient languages or development systems may be employed, in accordance with system requirements.
• the system 100 further comprises additional DSP servers, e.g. 118, 120 that, in use, compete with DSP server 102 to bid for placement of advertising content within online ad slots offered via an ad exchange server 122.
• the ad exchange server 122 implements a digital marketplace allowing advertisers and publishers of web sites and other online content to buy and sell advertising space in the form of a real-time, online auction in which each DSP server 102, 118, 120 is an automated, high-speed, bidder.
• the ad exchange server 122 comprises a database 124 in which it maintains details of online content providers (web servers) and advertisers (DSPs) for the purpose of operating a digital advertising marketplace.
• DoubleclickTM owned by GoogleTM
• AppNexusTM owned by GoogleTM
• MicrosoftTM Ad ExchangeTM and OpenXTM
• OpenXTM OpenXTM
• the system 100 further includes user terminal devices, exemplified by terminal device 126.
• the terminal devices 126 may be, for example, desktop or portable PCs, smartphones, tablets, or other personal computing devices, and each comprise a processor 128 interfaced, e.g. via address/data bus 130, with volatile storage 132, non-volatile storage 134, and at least one data
• the processor 128 is also interfaced to one or more user input/output (I/O) interfaces 140.
• the volatile storage 132 contains program instructions and transient data relating to the operation of the terminal device 126.
• the terminal device storage 132, 134 may contain program and data content relevant to the normal operation of the device 126. This may include operating system programs and data (e.g. associated with a Windows, Android, iOS, MacOS, Linux, or other operating system), as well as other executable application software generally unrelated to the present invention.
• the storage 132 also includes program instructions 138 which, when executed by the processor 128 enable the terminal device to provide a user with access to online content. While many applications are known for providing such access, for simplicity in the present description it is assumed that the program instructions 138 implement a web browser having a graphical user interface (GUI) presented via the user I/O interface 140.
• GUI graphical user interface
• a corresponding web page display 144 is generated via the device Ul 140.
• the display 144 include website content 146, and one or more advertising slots, e.g. 148, 150.
• each advertising slot 148, 150 may comprise a plurality of specific Offers' on behalf of an advertiser. These offers are commonly arranged in a grid layout, e.g. as indicated by dashed rectangles 148a, 148b, 148c, 150a, 150b, 150c in Figure 1.
• a number of communications steps then take place in order to populate these slots, i.e. to provide online advertisers with ad impressions within the web page display 144. These communications steps will now be described with reference to the timeline 200 illustrated in Figure 2.
• the user terminal 126 via the executing web browser application 138 and responsive to user input, transmits 202 an HTTP request to the web server 142 which includes a URL of desired web content.
• the web server 142 responds by transmitting 204 content, e.g. a web page in HTML format, to the user device 126.
• content e.g. a web page in HTML format
• the complete population and rendering of web page display 144 may require multiple requests and responses, and may involve further transactions with the web server 142 and/or with other online servers, such as content distribution network (CDN) servers and other web servers providing embedded content.
• CDN content distribution network
• the web page transmitted by the web server 142 to the user device 126 typically includes a hypertext reference ('href) directing the browser 138 to retrieve content from the ad exchange server 122 in accordance with an application programming interface (API) defined and provided by the relevant operator of the server 122.
• the user device 126 transmits 208 an HTTP request to the ad exchange server 122.
• the request includes web site information and user information relating to the user of the terminal device 126.
• Available user information may include information that the web server 142 has gathered, and may include client-side information, such as device and browser identity and technical details, identifying information and contents of browser cookies, and the like.
• client-side information such as device and browser identity and technical details, identifying information and contents of browser cookies, and the like.
• the ad exchange server 122 receives the request, identifies relevant DSP servers 102, 118, 120 in its database 124, and transmits 210 bid request messages to each selected DSP server.
• One such bid request message including site and user information, is received at DSP server 102 embodying the present invention, which executes a process 212 in accordance with its specific programming 114 in order to predict a likelihood of user interaction with a selected ad including one or more offers, placed within one or more of the available slots 148, 150, and arrive at a bid decision.
• the DSP server 102 transmits 214 the bid to the ad exchange server 122.
• the ad exchange server 122 receives all bids transmitted from DSP servers, including server 102, and selects a winning bid. It then retrieves ad content corresponding with the winning bid from its database 124, and transmits 216 the ad content to the user device 126 for rendering within the corresponding ad slot, e.g. 148 or 150.
• This decision must be made with limited user information, and in view of the fact that a bad decision may have significant consequences for the advertiser. For example, if the DSP server wrongly determines that the user is a desirable target for a particular ad (i.e. computes a 'false positive'), it may place a relatively high winning bid and incur a real cost with little or no prospect of any return. Conversely, if the DSP server wrongly determines that the user is not a desirable target for the ad (i.e. computes a 'false negative'), it may place no bid, or a low losing bid, and cause the advertiser to miss an opportunity to obtain an impression with a real prospect of a return.
• FIG. 1 the system 100 further includes a machine learning server ('ML server') 152, which is configured to process raw data relating to placement of content (i.e. ads/offers) along with user interactions (i.e. user clicks on ads/offers), to generate training data sets for a machine learning model, and to train the machine learning model for deployment to the DSP server 102.
• 'ML server' machine learning server
• the processing, training and deployment steps are described in greater detail below, with reference to Figures 3 and 4, and may be carried out continuously, periodically and/or on-demand in order to maintain currency of the machine learning model.
• the ML server 152 may comprise a computer system having a conventional architecture, e.g. comprising a processor 154 that is operably associated with a non-volatile memory/storage device 156, via one or more data/address busses 158 as shown.
• the processor 154 is also interfaced to volatile storage 60 which contains program instructions and transient data relating to the operation of the ML server 152.
• the storage device 156 contains operating system programs and data, as well as other executable application software necessary for the intended functions of the ML server 152, and including program instructions which, when executed by the processor 154, cause the ML server 152 to perform operations relating to an embodiment of the present invention, such as are described in greater detail below with reference to Figures 3 and 4 in particular.
• instructions and data held on the storage device 156 are transferred to volatile memory 150 for execution on demand.
• the processor 154 is operably associated with a communications interface 162 in a conventional manner, providing access to the Internet 116.
• the volatile storage 160 contains a corresponding body 164 of program instructions transferred from the storage device 156 and configured to perform processing, training and deployment steps embodying the present invention.
• the program instructions 164 comprise a further specific technical contribution to the art in accordance with the invention.
• the system 100 further includes at least one database 166, which is configured to store raw historical data relating to placement of content (i.e.
• a log of data for a single day comprises on the order of 20 million lines (i.e.
• the database 166 is preferably implemented using technologies that are optimised for efficient storage, retrieval and update of very large volumes of data (sometimes referred to as 'big data') across multiple database servers and storage devices. While a number of suitable commercial and open source technologies exist for implementation of the database 166, an exemplary experimental embodiment has been implemented using Apache Hadoop framework, with data stored in Parquet format on HDFS (Hadoop Distributed File System), and using Impala to provide a high-speed, SQL-like query engine. This implementation has been tested and found to provide more than adequate performance for practical online deployment of embodiments of the invention.
• Apache Hadoop framework Apache Hadoop framework
• HDFS Hadoop Distributed File System
• the database 166 is accessible to both the DSP server 102 and the ML server 152.
• logical access is illustrated by corresponding arrows.
• physical access between the database 166 and the DSP and ML servers 102, 152 may be via the Internet 116, and/or via other dedicated communications links or networks, such as a local storage area network (SAN).
• the DSP server 102 is configured to update the database 166, in real time, with raw data relating to placement and interaction events.
• the ML server 152 is configured to retrieve the raw data from the database 166 and to carry out processing, training and deployment steps, based on the retrieved data, in accordance with an embodiment of the invention.
• FIG. 3 is a block diagram illustrating schematically a number of code modules that together comprise an online user interaction prediction engine 300 embodying the invention. Implementation of the user interaction prediction engine 300 is distributed across the ML server 152 and DSP server 02, as shown by the dashed boxes in Figure 3. Three code modules make up the ML server component of the engine 300, namely a matching module 302, a feature enrichment module 304 and a machine learning module 306. These three modules are all implemented within the program instructions 164 executing on the ML server 152. The functionality implemented within each of these modules will now be described in greater detail.
• the purpose of the matching module 302 is to match placement events (i.e. display of ads, and offers within ads, in ad slots 148, 150 of the display 144 of the user device 126) to subsequent interaction events (i.e. instances of a user clicking on an offer within an ad placed on the display 144 of the user device 126).
• Matching enables placement events to be tagged as 'clicked' or 'not clicked', so that they can be used by machine learning module 306 in training of a supervised machine learning model for prediction of user interaction events based upon placement event data. Additionally, matching enables placement event data to be combined with corresponding interaction event data to create a record for clicked ads containing all available information regarding placement and interaction.
• Matching presents a challenge because there is no explicit link between a placement event (ad impression) and a subsequent user interaction (ad click).
• a user interaction may occur at any time following placement, e.g. following a substantial delay. Since new placement and/or interaction events may occur at a very high rate (e.g.
• the rate of interaction events may be very low, e.g. it is generally reported that the click through rate (CTR) for web-based display advertising is on the order of 0.05%.
• CTR click through rate
• the general approach employed for matching in embodiments of the invention is to identify, in the database 166, placement events and subsequent interaction events within a predetermined time window that have a selected set of matching parameters.
• the time window should be of sufficient duration to capture a substantial majority of all interactions, and the number and choice of parameters should be sufficient to ensure unique matching in a substantial majority of cases. Perfect matching may be difficult to achieve, because it is impossible to know if or when an interaction will occur.
• a time window of longer duration will capture interactions that occur after longer delays, but will also increase the risk of erroneous matching where, for example, a user interacts with a subsequently-presented ad having similar parameters.
• the risk of erroneous matching can be reduced by using a larger selected set of parameters to distinguish between presented ads, at the expense of making the matching process more complex.
• the invention has been implemented in the context of a domain-specific DSP server operating on behalf of advertisers, using event data captured from a live system.
• a heuristic approach was taken to design of the matching module, with a number of experiments being conducted to determine a suitable time window, and a selected set of parameters.
• An 80 second time window was found to be effective in combination with matching the following event parameters:
• publisher identifier i.e. the ad exchange/distribution network through which the ad was placed
• user segment a combination of a user product segment, based upon a product such as flight, hotel or restaurant previously viewed by the user, and a user time segment, indicating how long it has been since the last activity of the user
• ad slot key (a stable identifier for the combination of publisher, ad slot and page).
• matching is performed using an Impala SQL query to select and join tables of records of placement and interaction events on the values of fields corresponding with the parameters listed above.
• placement records are LEFT JOINed to interaction records, such that the resulting table includes a row for each placement event.
• Each row comprises a set of values of raw features derived from the matched events, along with an indicator of whether or not an interaction event, i.e. ad/offer click, occurred.
• the table of matched data is input to the feature enrichment module 304.
• the function of the feature enrichment module 304 is to derive, from the values of raw features in the matched data table generated by the matching module 302, a corresponding set of enriched feature vectors for use by the machine learning module 306.
• a process for determining a suitable set of enriched features i.e. feature engineering
• definitions of enriched features for use by the feature enrichment module 304 are shown as being stored in a file 310 within data store 308, however this may be regarded as a schematic convenience.
• feature definitions may be stored in this way, may be compiled into a code module and linked to the feature enrichment module 304, or may be hard-coded into the feature enrichment module.
• each of these implementation options (and others that will be apparent to persons skilled in the art) potentially offers a different trade-off between flexibility, code complexity and execution speed.
• all of the enriched features are of categorical type (i.e. take on one of a number of discrete values), and are one-hot encoded.
• the resulting feature vectors are therefore generally relatively sparse, and comprise binary elements.
• each feature vector corresponds with an offer within an ad presented to a user, and is associated with a binary tag indicating whether or not the user interacted with (i.e. clicked on) the offer.
• the resulting table of feature vectors and tags is input to the machine learning module 306.
• the machine learning module 306 comprises program code executing on the ML server 152, and configured in the exemplary experimental embodiment to implement a generalised linear model. Specifically, the machine learning module 306 of the exemplary embodiment implements a regularised logistic regression algorithm, with 'follow-the-regularised-leader' (FTRL)-proximal learning.
• this machine learning algorithm is known to be effective in the case of highly unbalanced datasets (noting that only around 0.05% of samples in the table of feature vectors are tagged as 'clicked'). Further details of the algorithm, and its application to click-prediction, can be found in H. Brendan McMahan et al, 'Ad Click Prediction: a View from the Trenches',
• the algorithm has a number of hyperparameters that can be adjusted in order to optimise its learning accuracy on the training data for a specific problem.
• a process for determining a suitable set of values for the hyperparameters is described in detail below with reference to Figure 5.
• fixed values of the hyperparameters for use by the machine learning module 306 are shown as being stored in a file 3 2 within data store 308.
• alternative implementations are possible, such as hard-coding the parameters into the machine learning module 306.
• Execution of the machine learning module 306 on a particular dataset results in the generation of a model that can be executed by the DSP server 102, as will be described in greater detail below with reference to Figure 6.
• a logistic regression model is wholly characterised by a set of coefficients associated with elements of the input feature vector.
• a particularly efficient representation of the model is employed, to enable the DSP server 102 to compute a prediction of the likelihood of a user interaction very rapidly, i.e. well within the 30 ms target window 220 for generating a bid decision.
• the coefficients are stored in a dictionary data structure in which each entry is defined by a key and a value.
• the key is a hashed representation of a concatenation of the feature name (i.e. column label in the feature table) and a corresponding feature value (i.e. categorical values prior to one-hot coding).
• the associated value in the dictionary is simply the corresponding model coefficient.
• This type of data structure is known to provide extremely fast lookup, particularly for sparse feature sets.
• a limit on the number of hashed features may be imposed (a scheme sometimes referred to as the 'hashing trick').
• This scheme can be used to greatly speed lookup and computation, at the expense of possible collisions in dictionary key values.
• the statistical effect of these collisions can be neglected from the perspective of overall performance of the algorithm.
• the model data structure is serialised in a binary format (in the exemplary embodiment the Python 'pickle' format is used), and stored in a model file 314 in data store 308.
• the ML server 152 executes the modules 302, 304, 306 repeatedly, e.g. continuously, periodically, or on-demand. This is illustrated by the flowchart 400 shown in Figure 4.
• Raw data is retrieved from the database 166 at step 402.
• Exemplary embodiments use a predetermined period of recent data, which is considered to be representative of the behaviour of current online users of the system 100. For example, raw data from the most recent one-month period may be employed.
• the matching module 302 performs matching of placement and interaction events, as has been described. In practice, retrieval 402 and matching 404 steps may be combined as a single query, e.g. an Impala SQL query.
• the ML server 152 executes the feature enrichment module, which uses the enriched feature definitions 310 to compute enriched feature vectors corresponding with the matched data. These are transferred to the machine learning module 306 which trains the model using the tagged feature vectors and the predetermined hyperparameters defined in the configuration file 312. The resulting model coefficients are hashed, serialised and published 410 to the model file 314.
• the ML server then waits 412, before recommencing the process at step 402. Exit from the wait condition 412 may be triggered by a number of different events.
• the ML server may be configured to run the modules 302, 304, 306 periodically, e.g. once per day. Alternatively, or additionally, it may be configured to run the modules 302, 304, 306 on-demand, e.g. upon receipt of a signal from a controller (not shown) within the system 100.
• the ML server may run the modules 302, 304, 306 continuously, thereby updating the model fife 314 as frequently as possible based upon the time required for data matching, feature enrichment and model training.
• FIG. 5 there is shown a flowchart 500 of a process of feature engineering and model hyperparameter optimisation according to an embodiment of the invention.
• the process 500 is partially automated, and operated under human supervision.
• the development of suitable features with strong predictive capability, and the selection of appropriate ranges of model hyperparameters involves significant experience, judgment, creativity and ingenuity, and in most cases cannot efficiently be fully-automated.
• the process 500 requires a set of test data, which is retrieved at step 502, and which may be obtained in the same manner as described above in relation to the functionality of the matching module 302.
• data may be extracted from the database 166 for a selected test period using an Impala SQL query of the same form as that used by the matching module 302.
• a set of enriched features is defined and configured. In the exemplary embodiment, this step involves application of judgment, creativity and ingenuity of an experienced data scientist. In practice, a number of experiments have been performed, according to the process 500 and supported by further analysis of the test data set, in order to identify an effective set of enriched features. At step 506, values of the defined enriched features are computed from the raw test data set.
• a set of hyperparameter values is selected and a machine learning model is configured with the selected values.
• the resulting model is trained using the enriched test data. Typically, a portion of the test data is held back in the training step 510, which is then used in a cross-validation step 512 to assess the performance of the trained model on data that was not seen during the training step 510.
• Performance of the trained model is then assessed at decision step 514, to determine whether or not it is acceptable, for example by reaching some optimal or sufficient level of performance. The choice of criteria for assessing performance may be important to identifying an acceptable model.
• Gini which is related to the AUROC.
• AUROC Area Under the Receiver Operating Curve
• log loss which is desirably as high as possible
• log loss which is desirably as low as possible
• This approach was employed not only for different hyperparameters of the selected FTRL-Proximal model, but also for a number of alternative models, including decision trees (distributed random forest, gradient boosted trees), naive Bayes, and deep learning networks, which were consequently rejected as providing inferior performance on the analysed datasets.
• a further decision 516 is made as to whether the model hyperparameters.
• the resulting loop of configuring hyperparameters, training and testing the model is typically automated using an algorithm such as grid search, or similar.
• the role of the supervising data scientist in this case is to determine suitable ranges for the grid of hyperparameters.
• an outer loop implemented via decision 518, allows for the testing of alternative sets of enriched features. If available selections and values of model algorithms, hyperparameters and enriched features have been exhausted without identifying an acceptable model, then the process 500 may be regarded as having failed, and a reconsideration of strategy may be required. For the purposes of the exemplary embodiment, however, the process 500 led to a model with acceptable performance. At step 520, therefore, the identified enriched feature definitions and model hyperparameters are written to the data files 310, 312 in the data store 308. A summary of the enriched features developed via the process 500 is presented in Table 1.
• the online user interaction prediction engine 300 includes a real-time bidding module 316, which is implemented within the program instructions 114 executing on the DSP server 102.
• the real-time bidding module 316 employs the enriched feature definitions 310 and the trained model representation 314.
• the operation of the real-time bidding module 316 is represented by the flow chart 600 shown in Figure 6 in which, at step 602, site and user information is received, i.e. via transmission 210 from the ad exchange server 122. This information is used at step 604 to compute a corresponding enriched feature vector according to the definitions 310.
• the real-time bidding module accesses the model representation which, as has been described, comprises a set of coefficients stored in a highly efficient dictionary structure for rapid coefficient lookup.
• the model may be updated from time-to-time by the ML server 152.
• the model representation 314 may be stored in a shared storage medium 308, and be asynchronously readable by the DSP server 102.
• the DSP server may maintain a cached copy of the model representation 314 for rapid access, which is updated upon update of the stored file by the ML server 152.
• the output of the model is an estimate of likelihood of user interaction with an offer within a selected ad, based on the enriched feature vector.
• the output is a value representing a probability that the user will click on an offer within the selected ad. This value is used in a bid decision process at step 608.
• the process 608 may include determining whether or not to bid at all, and/or a determination of a particular price to bid for the available ad slot. For example, a threshold may be applied, such that if the value is below the threshold then no bid is made.
• a bid amount may be determined based upon the magnitude of the value, such that a higher price is bid if the model indicates a higher likelihood that the user will click on an offer within the selected ad.
• control is directed 610 to step 612 wherein the bid information is transmitted 214 back to the ad exchange server 22.
• control is directed 614 to step 616, in which the database 166 is updated with details of the placement event.
• Figure 7(a) is a chart 700 having click through rate (CTR) on the vertical axis 702, with the corresponding performance of ten bidding modules shown as a series of bars.
• the bars 704 represent the performance of nine conventional bidding modules, while the bar 706 represents the performance of the experimental bidder embodying the invention.
• CTR click through rate
• Figure 7(b) is a chart 708 having margin, defined as net profit divided by cost, on the vertical axis 710.
• the bars 712 represent the performance of the nine conventional bidding modules, all of which operated at a loss.
• the experimental bidder, represented by the bar 714 was able to operate at a profit.
• ts_day_of_week The day of the week (Sun-Sat) of the placement event.
• ts_hour_of_day The hour of the day (00-23) of the placement event.
• publisherj ' d Identifier of publisher i.e. operator of ad exchange server.
• advertiserjd Identifier of advertiser i.e. operator of ad exchange server.
• offer_key A unique offer identifier, created by combining advertiserjd
• ad_dst_top199 A destination associated with an offer. Limited to the top 199 destinations, which were found in feature engineering experiments to capture 92% of all clicks.
• nb_offers_per_ad Number of offers included with the ad slot nb_offers_per_ad Number of offers included with the ad slot.
• mq_dst Proximity/distance of destination of interest to the user and destination associated with an offer A categorical value indicating closeness of match on a set scale.
• user_pseg Identifier of a product segment previously viewed by user e.g.
• user_tseg Identifier of a time segment of the user's previous activity e.g.
• domain_name_top99 Domain name of site in which ad slot is displayed Limited to the top 99 domains, which were found in feature engineering experiments to capture 95% of all clicks.
• fmt_device An engineered feature comprising a combination of offer
• ad_slot_key_top499 A unique identifier for the combination of publisher, ad slot, and page. Limited, to the top 499 values, which were found in feature engineering experiments to capture 97% of all clicks. campjype Categorical identifier of campaign type associated with an offer (e.g. text + image, image, display banner with dynamic content, static display banner). Feature Name Feature Description
• user_country_top3 The country from which the user accessed a site. Limited to the top three countries, which were found in feature engineering experiments to capture over 99% of all traffic. Note, however, that the number and identity of top countries is specific to a publisher/ad exchange, which may be region and language specific.
• offer_pos A categorical value indicating the placement of an offer within an ad slot.
• browser Identifier of user browser e.g. Chrome, IE, Safari, etc.

Landscapes

• Business, Economics & Management (AREA)
• Engineering & Computer Science (AREA)
• Strategic Management (AREA)
• Accounting & Taxation (AREA)
• Development Economics (AREA)
• Finance (AREA)
• Theoretical Computer Science (AREA)
• Physics & Mathematics (AREA)
• General Physics & Mathematics (AREA)
• General Business, Economics & Management (AREA)
• Economics (AREA)
• Marketing (AREA)
• Game Theory and Decision Science (AREA)
• Entrepreneurship & Innovation (AREA)
• Software Systems (AREA)
• Evolutionary Computation (AREA)
• Computer Vision & Pattern Recognition (AREA)
• Data Mining & Analysis (AREA)
• Artificial Intelligence (AREA)
• Medical Informatics (AREA)
• Probability & Statistics with Applications (AREA)
• Computing Systems (AREA)
• General Engineering & Computer Science (AREA)
• Mathematical Physics (AREA)
• Information Transfer Between Computers (AREA)
• Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=63557443

Family Applications (1)

Country Status (3)

Families Citing this family (9)

Citations (2)

Family Cites Families (5)

• 2018
  • 2018-09-05 EP EP18769114.2A patent/EP3682402A1/de not_active Withdrawn
  • 2018-09-05 WO PCT/EP2018/073841 patent/WO2019052869A1/en not_active Ceased
  • 2018-09-05 CN CN201880056986.0A patent/CN111095330B/zh active Active

Patent Citations (2)

Non-Patent Citations (3)

Also Published As

Similar Documents

Legal Events