Alex Fabrikant

Alex Fabrikant

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Preview abstract The widely studied task of Natural Language Inference (NLI) requires a system to recognize whether one piece of text is textually entailed by another, i.e. whether the entirety of its meaning can be inferred from the other. In current NLI corpora and models, the textual entailment relation is typically defined on the sentence- or paragraph- level. However, even a simple sentence often contains multiple propositions, i.e. distinct units of meaning conveyed by the sentence. These propositions can carry different truth values in the context of a given premise, and we argue for the need to identify such fine-grained textual entailment relations. To facilitate the study on proposition-level segmentation and entailment, we propose PropSegmEnt, a corpus of over 35K propositions annotated by trained expert annotators. Our dataset structure resembles the tasks of (1) segmenting sentences within a document to the set of propositions, and (2) classifying the entailment relation of each proposition with respect to a different yet topically-aligned document, i.e. documents describing the same event or entity. We establish strong baselines for the segmentation and entailment tasks. We demonstrate that our conceptual framework is potentially useful for understanding and explaining the compositionality of NLI labels. View details
    Preview abstract Transformer encoders contextualize token representations by attending to all other tokens at each layer, leading to quadratic increase in compute effort with the input length. In practice, however, the input text of many NLP tasks can be seen as a sequence of related segments (e.g., the sequence of sentences within a passage, or the hypothesis and premise in NLI). While attending across these segments is highly beneficial for many tasks, we hypothesize that this interaction can be delayed until later encoding stages. To this end, we introduce Layer-adjustable Interactions in Transformers (LAIT). Within LAIT, segmented inputs are first encoded independently, and then jointly. This partial two-tower architecture bridges the gap between a Dual Encoder's ability to pre-compute representations for segments and a fully self-attentive Transformer's capacity to model cross-segment attention. Also, LAIT can be introduced only when finetuning, effectively converting an existing pretrained Transformer into the hybrid of the two aforementioned architectures, and providing an intuitive control over the performance-efficiency tradeoff. Experimenting on a wide range of NLP tasks, we find LAIT to significantly improve efficiency while preserving accuracy. View details
    Preview abstract Natural Language Inference (NLI) has been extensively studied by the NLP community as a framework for estimating the semantic relation between sentence pairs. While early work identified certain biases in NLI models, recent advancements in modeling and datasets demonstrated promising performance. In this work, we further explore the direct zero-shot applicability of NLI models to real applications, beyond the sentence-pair setting they were trained on. First, we analyze the robustness of these models to longer and out-of-domain inputs. Then, we develop new aggregation methods to allow operating over full documents, reaching state-of-the-art performance on the ContractNLI dataset. Interestingly, we find NLI scores to provide strong retrieval signals, leading to more relevant evidence extractions compared to common similarity-based methods. Finally, we go further and investigate whole document clusters to identify both discrepancies and consensus among sources. In a test case, we find real inconsistencies between Wikipedia pages in different languages about the same topic. View details
    Early social distancing policies in Europe, changes in mobility & COVID-19 case trajectories: Insights from Spring 2020
    Liana R. Woskie
    Jonathan Hennessy
    Valeria Espinosa
    Thomas Tsai
    Swapnil Vispute
    Ciro Cattuto
    Laetitia Gauvin
    Michele Tizzoni
    Krishna Gadepalli
    Adam Boulanger
    Adam Pearce
    Chaitanya Kamath
    Arran Schlosberg
    Charlotte Stanton
    Shailesh Bavadekar
    Matthew Abueg
    Michael Hogue
    Andrew Oplinger
    Katherine Chou
    Ashish K. Jha
    Greg Wellenius
    Evgeniy Gabrilovich
    PLOS ONE(2021)
    Preview abstract Background: Social distancing have been widely used to mitigate community spread of SARS-CoV-2. We sought to quantify the impact of COVID-19 social distancing policies across 27 European counties in spring 2020 on population mobility and the subsequent trajectory of disease. Methods: We obtained data on national social distancing policies from the Oxford COVID-19 Government Response Tracker and aggregated and anonymized mobility data from Google. We used a pre-post comparison and two linear mixed-effects models to first assess the relationship between implementation of national policies and observed changes in mobility, and then to assess the relationship between changes in mobility and rates of COVID-19 infections in subsequent weeks. Results: Compared to a pre-COVID baseline, Spain saw the largest decrease in aggregate population mobility (~70%), as measured by the time spent away from residence, while Sweden saw the smallest decrease (~20%). The largest declines in mobility were associated with mandatory stay-at-home orders, followed by mandatory workplace closures, school closures, and non-mandatory workplace closures. While mandatory shelter-in-place orders were associated with 16.7% less mobility (95% CI: -23.7% to -9.7%), non-mandatory orders were only associated with an 8.4% decrease (95% CI: -14.9% to -1.8%). Large-gathering bans were associated with the smallest change in mobility compared with other policy types. Changes in mobility were in turn associated with changes in COVID-19 case growth. For example, a 10% decrease in time spent away from places of residence was associated with 11.8% (95% CI: 3.8%, 19.1%) fewer new COVID-19 cases. Discussion: This comprehensive evaluation across Europe suggests that mandatory stay-at-home orders and workplace closures had the largest impacts on population mobility and subsequent COVID-19 cases at the onset of the pandemic. With a better understanding of policies’ relative performance, countries can more effectively invest in, and target, early nonpharmacological interventions. View details
    Impacts of social distancing policies on mobility and COVID-19 case growth in the US
    Gregory Alexander Wellenius
    Swapnil Suresh Vispute
    Valeria Espinosa
    Thomas Tsai
    Jonathan Hennessy
    Krishna Kumar Gadepalli
    Adam Boulanger
    Adam Pearce
    Chaitanya Kamath
    Arran Schlosberg
    Catherine Bendebury
    Chinmoy Mandayam
    Charlotte Stanton
    Shailesh Bavadekar
    Christopher David Pluntke
    Damien Desfontaines
    Benjamin H. Jacobson
    Zan Armstrong
    Katherine Chou
    Andrew Nathaniel Oplinger
    Ashish K. Jha
    Evgeniy Gabrilovich
    Nature Communications(2021)
    Preview abstract Social distancing has emerged as the primary mitigation strategy to combat the COVID-19 pandemic in the United States. However, large-scale evaluation of the effectiveness of social distancing policies are lacking. We used aggregated mobility data to quantify the impact of social distancing policies on observed changes in mobility. Declarations of states of emergency resulted in approximately a 10% reduction in time spent outside places of residence and an increase in visits to grocery stores and pharmacies. Subsequent implementation of ≥1 social distancing policies resulted in an additional 25% reduction in mobility in the following week. The seven states that subsequently ordered residents to shelter in place on or before March 23, 2020 observed an additional 29% reduction in time spent outside the residence. Our findings suggest that state-wide mandates are highly effective in achieving the goals of social distancing to minimize the transmission of COVID-19. View details
    Google COVID-19 Search Trends Symptoms Dataset: Anonymization Process Description
    Akim Kumok
    Chaitanya Kamath
    Charlotte Stanton
    Damien Desfontaines
    Evgeniy Gabrilovich
    Gerardo Flores
    Gregory Alexander Wellenius
    Ilya Eckstein
    John S. Davis
    Katie Everett
    Krishna Kumar Gadepalli
    Rayman Huang
    Shailesh Bavadekar
    Thomas Ludwig Roessler
    Venky Ramachandran
    Yael Mayer
    Arxiv.org, N/A(2020)
    Preview abstract This report describes the aggregation and anonymization process applied to the initial version of COVID-19 Search Trends symptoms dataset, a publicly available dataset that shows aggregated, anonymized trends in Google searches for symptoms (and some related topics). The anonymization process is designed to protect the daily search activity of every user with \varepsilon-differential privacy for \varepsilon = 1.68. View details
    LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale
    Georg Osang
    James Cook
    Marco Gruteser
    Proceedings of IEEE Intelligent Transportation Systems Conference 2019(2019)
    Preview abstract We present LiveTraVeL (Live Transit Vehicle Labeling), a real-time system to label a stream of noisy observations of transit vehicle trajectories with the transit routes they are serving (e.g., northbound bus #5). In order to scale efficiently to large transit networks, our system first retrieves a small set of candidate routes from a geometrically indexed data structure, then applies a fine-grained scoring step to choose the best match. Given that real-time data remains unavailable for the majority of the world’s transit agencies, these inferences can help feed a real-time map of a transit system’s trips, infer transit trip delays in real time, or measure and correct noisy transit tracking data. This system can run on vehicle observations from a variety of sources that don’t attach route information to vehicle observations, such as public imagery streams or user-contributed transit vehicle sightings. We abstract away the specifics of the sensing system and demonstrate the effectiveness of our system on a “semisynthetic” dataset of all New York City buses, where we simulate sensed trajectories by starting with fully labeled vehicle trajectories reported via the GTFS-Realtime protocol, removing the transit route IDs, and perturbing locations with synthetic noise. Using just the geometric shapes of the trajectories, we demonstrate that our system converges on the correct route ID within a few minutes, even after a vehicle switches from serving one trip to the next. View details
    Preview abstract In many computational and economic models of multi-agent interaction, each participant repeatedly "best-responds" to the others' actions. Game theory research on the prominent "best-response dynamics" model typically relies on the premise that the interaction between agents is somehow synchronized. However, in many real-life settings, e.g., internet protocols and large-scale markets, the interaction between participants is asynchronous. We tackle the following important questions: (1) When are best-response dynamics guaranteed to converge to an equilibrium even under asynchrony? (2) What is the (computational and communication) complexity of verifying guaranteed convergence? We show that, in general, verifying guaranteed convergence is intractable. In fact, our main negative result establishes that this task is undecidable. We exhibit, in contrast, positive results for several environments of interest, including complete, computationally-tractable, characterizations of convergent systems. We discuss the algorithmic implications of our results, which extend beyond best-response dynamics to applications such as asynchronous Boolean circuits. View details
    Preview abstract We consider the algorithmic challenges behind a novel interface that simplifies consumer research of online reviews by surfacing relevant comparable review bundles: reviews for two or more of the items being researched, all generated in similar enough circumstances to provide for easy comparison. This can be reviews by the same reviewer, or by the same demographic category of reviewer, or reviews focusing on the same aspect of the items. But such an interface will work only if the review ecosystem often has comparable review bundles for common research tasks. Here, we develop and evaluate practical algorithms for suggesting additional review targets to reviewers to maximize comparable pair coverage, the fraction of co-researched pairs of items that have both been reviewed by the same reviewer (or more generally are comparable in one of several ways). We show the exact problem and many subcases to be intractable, and give a greedy online, linear-time 2-approximation for a very general setting, and an offline 1.583-approximation for a narrower setting. We evaluate the algorithms on the Google+ Local reviews dataset, yielding more than 10x gain in pair coverage from six months of simulated replacement of existing reviews by suggested reviews. Even allowing for 90% of reviewers ignoring the suggestions, the pair coverage grows more than 2x in the simulation. To explore other parts of the parameter space, we also evaluate the algorithms on synthetic models. View details
    Arrival and departure in Social Networks
    Shaomei Wu
    Atish Das Sarma
    Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013
    Preview
    On the structure of weakly acyclic games
    Aaron D Jaggard
    Michael Schapira
    Theory of Computing Systems, 53(2013), pp. 107-122
    Preview abstract The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapable oscillations. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a unique pure Nash equilibrium in every subgame implies the weak acyclicity of a game. In contrast, the possible existence of multiple pure Nash equilibria in every subgame is insufficient for weak acyclicity in general; here, we also systematically identify the special cases (in terms of the number of players and strategies) for which this is sufficient to guarantee weak acyclicity. View details
    Preview abstract Online social networks like Google+, Twitter, and Facebook allow users to build, organize, and manage their social connections for the purposes of information sharing and consumption. Nonetheless, most social network users still report that building and curating contact groups is a time-consuming burden. To help users overcome the burdens of contact discovery and grouping, Google+ recently launched a new feature known as "circle sharing". The feature makes it easy for users to share the benefits of their own contact curation by sharing entire "circles" (contact groups) with others. Recipients of a shared circle can adopt the circle as a whole, merge the circle into one of their own circles, or select specific members of the circle to add. In this paper, we investigate the impact that circle-sharing has had on the growth and structure of the Google+ social network. Using a cluster analysis, we identify two natural categories of shared circles, which represent two qualitatively different use cases: circles comprised primarily of celebrities (celebrity circles), and circles comprised of members of a community (community circles). We observe that exposure to circle-sharing accelerates the rate at which a user adds others to his or her circles. More specifically, we notice that circle-sharing has accelerated the "densification" rate of community circles, and also that it has disproportionately affected users with few connections, allowing them to find new contacts at a faster rate than would be expected based on accepted models of network growth. Finally, we identify features that can be used to predict which of a user’s circles (s)he is most likely to share, thus demonstrating that it is feasible to suggest to a user which circles to share with friends. View details
    BGP safety with spurious updates
    Martin Suchara
    Jennifer Rexford
    INFOCOM, IEEE(2011), pp. 2966-2974
    Preview abstract We explore BGP safety, the question of whether a BGP system converges to a stable routing, in light of several BGP implementation features that have not been fully included in the previous theoretical analyses. We show that Route Flap Damping, MRAI timers, and other intra-router features can cause a router to briefly send “spurious” announcements of less-preferred routes. We demonstrate that, even in simple configurations, this short-term spurious behavior may cause long-term divergence in global routing. We then present DPVP, a general model that unifies these sources of spurious announcements in order to examine their impact on BGP safety. In this new, more robust model of BGP behavior, we derive a necessary and sufficient condition for safety, which furthermore admits an efficient algorithm for checking BGP safety in most practical circumstances - two complementary results that have been elusive in the past decade's worth of classical studies of BGP convergence in more simple models. We also consider the implications of spurious updates for well-known results on dispute wheels and safety under filtering. View details
    There's something about MRAI: Timing diversity can exponentially worsen BGP convergence
    Umar Syed
    Jennifer Rexford
    Proceedings of the Thirtieth IEEE International Conference on Computer Communications (INFOCOM 2011)
    Preview abstract To better support interactive applications, individual network operators are decreasing the timers that affect BGP convergence, leading to greater diversity in the timer settings across the Internet. While decreasing timers is intended to improve routing convergence, we show that, ironically, the resulting timer heterogeneity can make routing convergence substantially worse. We examine the widely-used Min Route Advertisement Interval (MRAI) timer that rate-limits update messages to reduce router overhead. We show that, while routing systems with homogeneous MRAI timers have linear convergence time, diverse MRAIs can cause exponential increases in both the number of BGP messages and the convergence time (as measured in “activations”). We prove tight upper bounds on these metrics in terms of MRAI timer diversity in general dispute-wheel-free networks and economically sensible (Gao-Rexford) settings. We also demonstrate significant impacts on the data plane: blackholes sometimes last throughout the route-convergence process, and forwarding changes, at best, are only polynomially less frequent than routing changes. We show that these problems vanish in contiguous regions of the Internet with homogeneous MRAIs or with next-hop-based routing policies, suggesting practical strategies for mitigating the problem, especially when all routers are administered by one institution. View details
    The complexity of pure Nash equilibria
    Christos H. Papadimitriou
    Kunal Talwar
    STOC(2004), pp. 604-612