An official website of the United States government
We present a new approach for independently computing compact sketches that can be used to approximate the inner product between pairs of high-dimensional vectors. Based on the Weighted MinHash algorithm, our approach admits strong accuracy guarantees that improve on the guarantees of popular linear sketching approaches for inner product estimation, such as CountSketch and Johnson-Lindenstrauss projection. Specifically, while our method exactly matches linear sketching for dense vectors, it yields significantly lower error for sparse vectors with limited overlap between non-zero entries. Such vectors arise in many applications involving sparse data, as well as in increasingly popular dataset search applications, where inner products are used to estimate data covariance, conditional means, and other quantities involving columns in unjoined tables. We complement our theoretical results by showing that our approach empirically outperforms existing linear sketches and unweighted hashing-based sketches for sparse vectors.
more »
« less
Point configurations, phylogenetic trees, and dissimilarity vectors
In 2004, Pachter and Speyer introduced the higher dissimilarity maps for phylogenetic trees and asked two important questions about their relation to the tropical Grassmannian. Multiple authors, using independent methods, answered affirmatively the first of these questions, showing that dissimilarity vectors lie on the tropical Grassmannian, but the second question, whether the set of dissimilarity vectors forms a tropical subvariety, remained opened. We resolve this question by showing that the tropical balancing condition fails. However, by replacing the definition of the dissimilarity map with a weighted variant, we show that weighted dissimilarity vectors form a tropical subvariety of the tropical Grassmannian in exactly the way that Pachter and Speyer envisioned. Moreover, we provide a geometric interpretation in terms of configurations of points on rational normal curves and construct a finite tropical basis that yields an explicit characterization of weighted dissimilarity vectors.
more »
« less
- Award ID(s):
- 1952473
- PAR ID:
- 10217498
- Publisher / Repository:
- Proceedings of the National Academy of Sciences
- Date Published:
- Journal Name:
- Proceedings of the National Academy of Sciences
- Volume:
- 118
- Issue:
- 12
- ISSN:
- 0027-8424
- Page Range / eLocation ID:
- Article No. e2021244118
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We define and study the totally nonnegative part of the Chow quotient of the Grassmannian, or more simply thenonnegative configuration space. This space has a natural stratification bypositive Chow cells, and we show that nonnegative configuration space is homeomorphic to a polytope as a stratified space. We establish bijections between positive Chow cells and the following sets: (a) regular subdivisions of the hypersimplex into positroid polytopes, (b) the set of cones in the positive tropical Grassmannian, and (c) the set of cones in the positive Dressian. Our work is motivated by connections to super Yang–Mills scattering amplitudes, which will be discussed in a sequel.more » « less
-
Abstract The positive Grassmannian $$Gr^{\geq 0}_{k,n}$$ is a cell complex consisting of all points in the real Grassmannian whose Plücker coordinates are non-negative. In this paper we consider the image of the positive Grassmannian and its positroid cells under two different maps: the moment map$$\mu $$ onto the hypersimplex [ 31] and the amplituhedron map$$\tilde{Z}$$ onto the amplituhedron [ 6]. For either map, we define a positroid dissection to be a collection of images of positroid cells that are disjoint and cover a dense subset of the image. Positroid dissections of the hypersimplex are of interest because they include many matroid subdivisions; meanwhile, positroid dissections of the amplituhedron can be used to calculate the amplituhedron’s ‘volume’, which in turn computes scattering amplitudes in $$\mathcal{N}=4$$ super Yang-Mills. We define a map we call T-duality from cells of $$Gr^{\geq 0}_{k+1,n}$$ to cells of $$Gr^{\geq 0}_{k,n}$$ and conjecture that it induces a bijection from positroid dissections of the hypersimplex $$\Delta _{k+1,n}$$ to positroid dissections of the amplituhedron $$\mathcal{A}_{n,k,2}$$; we prove this conjecture for the (infinite) class of BCFW dissections. We note that T-duality is particularly striking because the hypersimplex is an $(n-1)$-dimensional polytope while the amplituhedron $$\mathcal{A}_{n,k,2}$$ is a $2k$-dimensional non-polytopal subset of the Grassmannian $$Gr_{k,k+2}$$. Moreover, we prove that the positive tropical Grassmannian is the secondary fan for the regular positroid subdivisions of the hypersimplex, and prove that a matroid polytope is a positroid polytope if and only if all 2D faces are positroid polytopes. Finally, toward the goal of generalizing T-duality for higher $$m$$, we define the momentum amplituhedron for any even $$m$$.more » « less
-
Inquisitive questions — open-ended, curiosity-driven questions people ask as they read — are an integral part of discourse processing and comprehension. Recent work in NLP has taken advantage of question generation capabilities of LLMs to enhance a wide range of applications. But the space of inquisitive questions is vast: many questions can be evoked from a given context. So which of those should be prioritized to find answers? Linguistic theories have not yet provided an answer. This paper presents QSALIENCE, a salience predictor of inquisitive questions. QSALIENCE is instruction-tuned over a dataset of linguist-annotated salience scores of 1,766 (context, question) pairs. A question scores high on salience if answering it would greatly enhance the understanding of the text. The authors show that highly salient questions are empirically more likely to be answered in the same article, bridging potential questions with Questions Under Discussion. They further validate their findings by showing that answering salient questions is an indicator of summarization quality in news.more » « less
-
Abstract Curiosity can be a powerful motivator to learn and retain new information. Evidence shows that high states of curiosity elicited by a specific source (i.e., a trivia question) can promote memory for incidental stimuli (non-target) presented close in time. The spreading effect of curiosity states on memory for other information has potential for educational applications. Specifically, it could provide techniques to improve learning for information that did not spark a sense of curiosity on its own. Here, we investigated how high states of curiosity induced through trivia questions affect memory performance for unrelated scholastic facts (e.g., scientific, English, or historical facts) presented in close temporal proximity to the trivia question. Across three task versions, participants viewed trivia questions closely followed in time by a scholastic fact unrelated to the trivia question, either just prior to or immediately following the answer to the trivia question. Participants then completed a surprise multiple-choice memory test (akin to a pop quiz) for the scholastic material. In all three task versions, memory performance was poorer for scholastic facts presented after trivia questions that had elicited high versus low levels of curiosity. These results contradict previous findings showing curiosity-enhanced memory for incidentally presented visual stimuli and suggest that target information that generates a high-curiosity state interferes with encoding complex and unrelated scholastic facts presented close in time.more » « less
