An official website of the United States government
In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks.
more »
« less
Do Transformer Networks Improve the Discovery of Inference Rules from Text?
With their Discovery of Inference Rules from Text (DIRT) algorithm, Lin and Pantel (2001) made a seminal contribution to the field of rule acquisition from text, by adapting the distributional hypothesis of Harris (1954) to patterns that model binary relations such as X treat Y, where patterns are implemented as syntactic dependency paths. DIRT’s relevance is renewed in today’s neural era given the recent focus on interpretability in the field of natural language processing. We propose a novel take on the DIRT algorithm, where we implement the distributional hypothesis using the contextualized embeddings provided by BERT, a transformer-network-based language model (Vaswani et al., 2017; Devlin et al., 2018). In particular, we change the similarity measure between pairs of slots (i.e., the set of words matched by a pattern) from the original formula that relies on lexical items to a formula computed using contextualized embeddings. We empirically demonstrate that this new similarity method yields a better implementation of the distributional hypothesis, and this, in turn, yields patterns that outperform the original algorithm in the question answering-based evaluation proposed by Lin and Pantel (2001).
more »
« less
- Award ID(s):
- 2006583
- PAR ID:
- 10333733
- Date Published:
- Journal Name:
- LREC proceedings
- ISSN:
- 2522-2686
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an ϵ-stationary point of any directionally differentiable Lipschitz objective using [Formula: see text] calls to a specialized subgradient oracle and a randomized line search. Seeking by contrast a deterministic method, we present a simple black-box version that achieves [Formula: see text] for any difference-of-convex objective and [Formula: see text] for the weakly convex case. Our complexity bound depends on a natural nonconvexity modulus that is related, intriguingly, to the negative part of directional second derivatives of the objective, understood in the distributional sense. Funding: This work was supported by the National Science Foundation [Grant DMS-2006990].more » « less
-
Text data has become extremely valuable due to the emergence of machine learning algorithms that learn from it. A lot of high-quality text data generated in the real world is private and therefore cannot be shared or used freely due to privacy concerns. Generating synthetic replicas of private text data with a formal privacy guarantee, i.e., differential privacy (DP), offers a promising and scalable solution. However, existing methods necessitate DP finetuning of large language models (LLMs) on private data to generate DP synthetic data. This approach is not viable for proprietary LLMs (e.g., GPT-3.5) and also demands considerable computational resources for open-source LLMs. Lin et al. (2024) recently introduced the Private Evolution (PE) algorithm to generate DP synthetic images with only API access to diffusion models. In this work, we propose an augmented PE algorithm, named AUGPE, that applies to the complex setting of text. We use API access to an LLM and generate DP synthetic text without any model training. We conduct comprehensive experiments on three benchmark datasets. Our results demonstrate that AUGPE produces DP synthetic text that yields competitive utility with the SOTA DP finetuning baselines. This underscores the feasibility of relying solely on API access of LLMs to produce high-quality DP synthetic texts, thereby facilitating more accessible routes to privacy-preserving LLM applications. Our code and data are available at https://github.com/AI-secure/aug-pe.more » « less
-
Computational models of verbal analogy and relational similarity judgments can employ different types of vector representations of word meanings (embeddings) generated by machine-learning algorithms. An important question is whether human-like relational processing depends on explicit representations of relations (i.e., representations separable from those of the concepts being related), or whether implicit relation representations suffice. Earlier machine-learning models produced static embeddings for individual words, identical across all contexts. However, more recent Large Language Models (LLMs), which use transformer architectures applied to much larger training corpora, are able to produce contextualized embeddings that have the potential to capture implicit knowledge of semantic relations. Here we compare multiple models based on different types of embeddings to human data concerning judgments of relational similarity and solutions of verbal analogy problems. For two datasets, a model that learns explicit representations of relations, Bayesian Analogy with Relational Transformations (BART), captured human performance more successfully than either a model using static embeddings (Word2vec) or models using contextualized embeddings created by LLMs (BERT, RoBERTa, and GPT-2). These findings support the proposal that human thinking depends on representations that separate relations from the concepts they relate.more » « less
-
We present a proof under a generalization of the Riemann Hypothesis that the class group algorithm of Hafner and McCurley runs in expected time \begin{document}$$ e^{\left(3/\sqrt{8}+o(1)\right)\sqrt{\log d\log\log d}} $$\end{document} where \begin{document}$ -d $$\end{document} is the discriminant of the input imaginary quadratic order. In the original paper, an expected run time of \begin{document}$$ e^{\left(\sqrt{2}+o(1)\right)\sqrt{\log d\log\log d}} $$\end{document}$ was proven, and better bounds were conjectured. To achieve a proven result, we rely on a mild modification of the original algorithm, and on recent results on the properties of the Cayley graph of the ideal class group.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
