Selecting items from a candidate pool to maximize the total return is a classical problem, which is faced by people frequently in real life and also engineers in information technology industry, e.g., digital advertising, e-commerce, web search, etc. For example, web UI designers always try to find the best web design among many candidates to display to users, Google needs to select personalized engaging ads to display to users based on their historical online behaviors. Each of these industries has hundreds of billions of dollars market, which means that even a small performance improvement of item selection efficiency can drive hundreds of millions of dollars growth in the real world.

In these applications, the true value of each item is unknown and can only be estimated from observed historical data. There is a large volume of significant research about building prediction models which are trained on historical data to estimate the item values. Given data volume and computation resource restrictions, engineers choose different models, e.g., deep neutral network, gradient boosting tree, or logistic regression to solve the problems. We will not dive into this area too much in this dissertation. Instead, our focus is how to maximize the total return given these predictions, especially taking into account the prediction uncertainties for the value optimization.

In the large-scale real applications, the candidate pool can be extraordinary large. It is infeasible to pick some items from the pool to get interactive feedback for exploration. Actually, not only is exploration infeasible, but even estimating the value of each item through a complex estimation mode is almost impossible due to the need of real-time response. For example, Apple needs to estimate users’ favorite apps and recommends them to users when they visit Apple store. Google needs to select ads to display to users given a users’ search queries. There are millions of candidates needing to be estimated from prediction models. It is very challenging to support such a large scale of model prediction under the low-latency constraint. Besides that, to have a good prediction accuracy, the models used in industry are getting more and more complex, e.g hidden neurons and layers of deep neural network increases rapidly in real applications, which also increases latency significantly. All of these make it infeasible to evaluate all candidates through one single complex model in large scale application. To solve this problem, engineers usually leverage the cascading waterfall filtering method to filter items sequentially, which means instead of using one complex model to estimate the values of all candidates, multiple stages are adopted to filter out candidates sequentially. For example, a simple model is used in the first stage to estimate candidates’ values for choosing a small subset from all candidates. These selected items are then passed to another stage to be estimated by a more complex model. Intuitively, this cascading waterfall filtering method provides a good trade-off between infrastructure cost and prediction accuracy, which can save computational resources use substantially, and simultaneously select most promising items accurately. However, there is no systematic study about how to efficiently choose the number of waterfalls and how many filtered items in each waterfall. Engineers tune the settings of this system heuristically through personal experience or online experiments, which is very inefficient, especially when the system is dynamic and changes rapidly. In this dissertation, we propose a theoretical framework for the cascading waterfall filtering problem and develop a mathematical algorithm to obtain the optimal solutions. Our method achieves a dramatic improvement in an important real-world application, which adopts cascading water filtering system to select a few items from tens of millions of candidates.

There are also some cases in which the candidate pool is relatively small. For instance, the number of web UI candidates is usually less than one hundred. Then, we are able to explore during item selection process. A typical exploration case is online experimentation, which is widely used to test and select items in real applications. In this situation, we can get interactive feedback to evaluate items. Considering online experiments for example, we usually randomly segments users into several groups, show them different candidates, and then compare the overall performance of each candidate to find the item with the largest value. Among all designs, A/B testing, which usually segments users into two statasitically equivalent groups to measure the difference between two versions of a single variable, is the most popular. For instance, in order to compare the impact of an ad versus another, we need to see the impact of exposing a user to viewing the first ad, and not the second, and then compare with the converse situation. However, a user cannot both see the first ad and not see it. Consequently, we need to create two “statistically equivalent populations” and expose users randomly to one or the other. This method is straightforward. However, the defect of this method is also obvious: to measure both versions, this method cannot expose all users to the best version, which leads to potential value loss. Some multi-armed bandit algorithms, e.g., Randomized Probability Matching (RPM), Upper Confidence Bounds (UCB), whose objective is maximizing the total return in experiment, have been proposed for improvement. However, these methods do not take into account the statistical confidence levels of the final result from the experiment and the corresponding impact on the subsequent item selection in the post-experimental stage. To solve this problem, we develop algorithms to achieve a good trade-off between reducing statistical uncertainty and maximizing cumulative reward, which aims at maximizing the total expected reward of item selection over a total duration, which includes both the current experimental stage and the post-experimental stage. The proposed algorithms demonstrate consistent and statistically significant improvements across different settings, outperforming both A/B testing and multi-armed bandit algorithms significantly.

Online experiment is widely used in online advertising, web development to compare effects, e.g. click through rate, conversion rate, of different versions. Among all the designs, A/B testing is the most popular one. It randomly segments users into two groups with equal probability and shows them different versions. This method is easy to implement. However the shortcoming is also obvious: to measure both versions it cannot expose all users to the best version, which leads to potential loss of rewards, e.g. clicks and conversions. Though this loss is inevitable in experiment, it can be reduced somehow. Reducing the loss is essentially equivalent to maximizing cumulative reward, which is also the goal of typical multi-armed bandit problem. Thus, multi-armed bandit algorithms are proposed to reduce potential loss in experiment. Compared with A/B testing, multi-armed bandit algorithms produce more cumulative reward during experiment. However, they suffer from high statistical uncertainty: e.g. they need more users than A/B testing to reach particular statistical significance level.

To solve this problem, this paper aims at building a model to analyze two conflicting goals: reducing statistical uncertainty and maximizing cumulative reward. We develop an algorithm for online experiment to balance the trade-off between these two goals. Right now our analysis focuses on one kind of online experiment: batch updating binomial experiment. We first discuss several statistical uncertainty criterion and propose corresponding algorithms to optimize these criterion for experiment. Then we extend some multi-armed bandit algorithms to maximizing cumulative reward for batch updating problem. Besides that, we propose an new algorithm: sequential two stages (STS) to solve this problem. After that, an improved performance evaluation method, which integrates statistical uncertainty with cumulative reward, is put forwarded. Instead of simply combining two objective functions, this new measure, virtual future measure (VFM) establishes connection between statistical uncertainty and cumulative reward directly through virtual future reward. Compared with other method, our proposed algorithm STS is adaptable to optimize VFM.

The allocation of a given budget to online display advertising as a marketing channel has motivated the development of statistical methods to measure its effectiveness. Recent studies show that display advertising often triggers online users to search for more information on products. Eventually, many of these users convert at the advertiser’s website. A key challenge is to measure the effectiveness of display advertising when users are exposed to multiple unknown advertising channels.

We develop a time series approach based on Dynamic Linear Models (DLM), to estimate the impact of ad impressions on the daily number of commercial actions when no user tracking is possible. This method uses aggregate observational data post-campaign and does not require an experimental set-up. We incorporate persistence of campaign effects and account for outliers in the time series without pre-defined thresholds. We analyze user conversions for 2,885 campaigns and 1,251 products during six months for model selection.

The current industry practice measures the campaign causal effect on online conversions by running a randomized experiment focused on the ad exposures (using placebo ads). This method ignores other campaign components, including user targeting in marketplaces with competitor effects. We propose a novel randomized design to estimate campaign and ad attribution in marketplaces. We determine the effect on the targeted users using the Potential Outcomes Causal Model and Principal Stratification. We analyze the impact of 2 performance-based (CPA) and 1 Cost-Per-Impression (CPM) campaigns with 20M+ users for each campaign. We estimate a non-zero CPM campaign presence in the marketplace effect (currently ignored by industry). Evidence suggests that CPA campaigns incentivize targeting of users who buy regardless of the ad (always-buyers).

We propose a user targeting simulator that leverages data from campaign randomized experiments. Based on the response of 37 million visiting users (targeted and non-targeted) and their demographic user features, we simulate different user targeting policies. We provide evidence that the standard conversion optimization policy shows similar effectiveness to that of uniform targeting, and is significantly inferior to other causally optimized targeting policies. These results challenge the standard practice of targeting users with the highest conversion probability.

To guide the user targeting to optimize causally generated conversions, we analyze the campaign on the conversion probability of the users who click on the ad as a behavioral feature. We show that designing a randomized experiment to evaluate this effect is infeasible, and propose a method to estimate the local effect on the clicker conversions. Based on two large-scale randomized experiments, performed for 7.16 and 22.7 million users, a pessimistic analysis shows a minimum increase of the effect on the clicker conversion probability of 75% with respect to the non-clickers. This evidence contradicts a recent belief that clicks are not indicative of campaign success.

Statistical Topic Models has been widely studied in Text Mining as an effective approach to extract latent topics from unstructured text documents. We present a robust and computationally efficient Hierarchical Bayesian model for effective topic correlation modeling Generalized Dirichlet distribution (GD). GD-LDA is effective to avoid over-fitting as the number of topics is increased. We provide results using Empirical Likelihood (EL) in 4 public datasets. We show the application of topic models in two different domains: 1)Information Retrieval, and 2)Dynamic Prediction Models applied in health care.

In Information Retrieval, we propose to leverage statistical topic modeling techniques in relevance feedback to incorporate a better estimate of context by including corpus level information about the document. We show results using the OHSUMED dataset for three different variants and obtain higher performance, up to 12.5% in Mean Average Precision (MAP).

Patients often search for information on the web about treatments and diseases after they are discharged from the hospital. However, searching for medical information on the web poses challenges due to related terms and synonyms for the same disease and treatment. We present a method to retrieve healthcare related documents using the patient discharge document. We show that the proposed framework outperformed the winner of the retrieval CLEF eHealth 2013 Challenge by 68% in the MAP measure, and by 13% in NDCG.

We present a method to estimate dynamically the probability of mortality inside the Intensive Care Unit (ICU) by combining heterogeneous data. We propose a method based on Generalized Linear Dynamic Models that models the probability of mortality as a latent state that evolves over time. This framework allows us to combine different types of features (lab results, vital signs readings, doctor and nurse notes, etc.) into a single state. We update this state each time new patient data is observed. We test our proposed approach using 15,000 Electronic Medical Records (EMRs) obtained from the MIMIC II public data set.

We expand this dynamic mortality estimation model in two forms. We estimate the probability that a patient is readmitted after he is discharged from the ICU and transferred to a lower level care unit. We also present a method to predict the failure of physiological subsystems from patients admitted to the ICU using heterogeneous data dynamically. We model the probability of failure in each subsystem as a latent state. Then, we estimate the probability of patient mortality as a combination of the estimated failure propensity for all subsystems. We propose a method of imputing missing values using the non-ignorable nature of the patient data. Experimental results show that our method outperforms other approaches in the literature in terms of AUC, sensitivity, and specificity. In addition, we show that the combination of different features (numerical and text) increases the prediction performance of the proposed approach.