Alex Fabrikant
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
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
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
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)
Evaluation of US State-Based Policy Interventions on Social Distancing Using Aggregated Mobility Data during the COVID-19 Pandemic
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)
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
Preview
Shaomei Wu
Atish Das Sarma
Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013
On the structure of weakly acyclic games
Aaron D Jaggard
Michael Schapira
Theory of Computing Systems, vol. 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
BGP safety with spurious updates
There's something about MRAI: Timing diversity can exponentially worsen BGP convergence
Jennifer Rexford
Proceedings of the Thirtieth IEEE International Conference on Computer Communications (INFOCOM 2011)
The complexity of pure Nash equilibria
