Evaluation plays a crucial role in the development of ranking algorithms on search and recommender systems.It enables online platforms to create user-friendly features that drive commercial success in a steady and effective manner.The online environment is particularly conducive to applying causal inference techniques, such as randomized controlled experiments (known as A/B test), which are often more challenging to implement in fields like medicine and public policy.However, businesses face unique challenges when it comes to effective A/B test.Specifically, achieving sufficient statistical power for conversion-based metrics can be time-consuming, especially for significant purchases like booking accommodations.While offline evaluations are quicker and more cost-effective, they often lack accuracy and are inadequate for selecting candidates for A/B test.To address these challenges, we developed interleaving and counterfactual evaluation methods to facilitate rapid online assessments for identifying the most promising candidates for A/B tests.Our approach not only increased the sensitivity of experiments by a factor of up to 100 (depending on the approach and metrics) compared to traditional A/B testing but also streamlined the experimental process.The practical insights gained from usage in production can also benefit organizations with similar interests.

Improving statistical power is a common challenge for online experimentation platforms so that more hypotheses can be tested and lower effect sizes can be detected. To increase the power without increasing the sample size, it is necessary to consider the variance of experimental outcome metrics. Variance reduction was previously applied to online experimentation based on the idea of using pre-experiment covariate data to account for noise in the final metrics. Since this method relies on correlations between pre-experiment covariates and experiment outcomes, its effectiveness can be limited when testing features for specific product surfaces. We were also motivated by the challenge of attributing sparse, delayed binary outcomes to individual user-product interactions. We present two novel methods for variance reduction that rely exclusively on in-experiment data. The first method is a framework for a model-based leading indicator metric which continually estimates progress toward a delayed binary outcome. The second method is a counterfactual treatment exposure index that quantifies the amount that a user is impacted by the treatment. We applied these methods to past experiments and found that both can achieve variance reduction of 50% or more compared to the delayed outcome metric. The substantial reduction in variance afforded by the two methods presented in this paper has enabled Airbnb's experimentation platform to become more agile and innovative.

Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically: 1. We show that solving for the ML estimate over the single deletion channel (which can be cast as a discrete optimization problem) is equivalent to solving its relaxation, a continuous optimization problem; 2. We exactly compute the symbolwise posterior distributions (under some assumptions on the priors) for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels.

We consider the problem of reconstructing a sequence from fixed number of deleted versions of itself (also called traces). The problem is motivated from recent developments in de novo DNA sequencing technologies. The main contribution of this work is to provide a polynomial time algorithm for symbolwise MAP decoding with multiple traces. The algorithm leverages a dynamic program on the edit graph. We also develop a heuristic with reduced time complexity using similar ideas and provide preliminary numerical evaluations.

The problem of reconstructing a sequence when observed through multiple looks over deletion channels occurs in “de novo” DNA sequencing. The DNA could be sequenced multiple times, yielding several “looks” of it, but each time the sequencer could be noisy with (independent) deletion impairments. The main goal of this paper is to develop reconstruction algorithms for a sequence observed through the lens of a fixed number of deletion channels. We use the probabilistic model of the deletion channels to develop both symbol-wise and sequence maximum likelihood decoding criteria, and algorithms motivated by them. Numerical evaluations demonstrate improvement in terms of edit distance error, over earlier algorithms.