More Like this

1. Higher-Kinded Data Types: Syntax and Semantics

   https://doi.org/10.1109/LICS.2019.8785657  

   Johann, Patricia; Polonsky, Andrew (January 2019, Logic in Computer Science)

   We present a grammar for a robust class of data types that includes algebraic data types (ADTs), (truly) nested types, generalized algebraic data types (GADTs), and their higher-kinded analogues. All of the data types our grammar defines, as well as their associated type constructors, are shown to have fully functorial initial algebra semantics in locally presentable categories. Since local presentability is a modest hypothesis, needed for such semantics for even the simplest ADTs, our semantic framework is actually quite conservative. Our results thus provide evidence that if a category supports fully functorial initial algebra semantics for standard ADTs, then it does so for advanced higher-kinded data types as well. To give our semantics we introduce a new type former called Lan that captures on the syntactic level the categorical notion of a left Kan extension. We show how left Kan extensions capture propagation of a data type’s syntactic generators across the entire universe of types, via a certain completion procedure, so that the type constructor associated with a data type becomes a bona fide functor with a canonical action on morphisms. A by-product of our semantics is a precise measure of the semantic complexity of data types, given by the least cardinal λ for which the functor underlying a data type is λ-accessible. The proof of our main result allows this cardinal to be read off from a data type definition without much effort. It also gives a sufficient condition for a data type to have semantic complexity ω, thus characterizing those data types whose data elements are effectively enumerable. 

   more » « less
2. A minimalist dataset for systematic generalization of perception, syntax, and semantics

   Li, Q.; Huang, S.; Hong, Y.; Zhu, Y.; Wu, Y. N.; Zhu, S. C. (May 2023, International Conference on Learning Representations (ICLR 2023))

   Inspired by humans’ exceptional ability to master arithmetic and generalize to new problems, we present a new dataset, Handwritten arithmetic with INTegers (HINT), to examine machines’ capability of learning generalizable concepts at three levels: perception, syntax, and semantics. In HINT, machines are tasked with learning how concepts are perceived from raw signals such as images (i.e., perception), how multiple concepts are structurally combined to form a valid expression (i.e., syntax), and how concepts are realized to afford various reasoning tasks (i.e., semantics), all in a weakly supervised manner. Focusing on systematic generalization, we carefully design a five-fold test set to evaluate both the interpolation and the extrapolation of learned concepts w.r.t. the three levels. Further, we design a few-shot learning split to determine whether or not models can rapidly learn new concepts and generalize them to more complex scenarios. To comprehend existing models’ limitations, we undertake extensive experiments with various sequence-to-sequence models, including RNNs, Transformers, and GPT-3 (with the chain of thought prompting). The results indicate that current models struggle to extrapolate to long-range syntactic dependency and semantics. Models exhibit a considerable gap toward human-level generalization when evaluated with new concepts in a few-shot setting. Moreover, we discover that it is infeasible to solve HINT by merely scaling up the dataset and the model size; this strategy contributes little to the extrapolation of syntax and semantics. Finally, in zero-shot GPT-3 experiments, the chain of thought prompting exhibits impressive results and significantly boosts the test accuracy. We believe the HINT dataset and the experimental findings are of great interest to the learning community on systematic generalization. 

   more » « less
3. To Check or Not to Check: Syntax, Semantics, and Context in the Language of Check-Worthy Claims

   https://doi.org/10.1007/978-3-030-28577-7_23  

   Zuo, Chaoyuan; Karakas, Ayla; Banerjee, Ritwik (August 2019, Lecture notes in computer science)

   As the spread of information has received a compelling boost due to pervasive use of social media, so has the spread of misinformation. The sheer volume of data has rendered the traditional methods of expert-driven manual fact-checking largely infeasible. As a result, computational linguistics and data-driven algorithms have been explored in recent years. Despite this progress, identifying and prioritizing what needs to be checked has received little attention. Given that expert-driven manual intervention is likely to remain an important component of fact-checking, especially in specific domains (e.g., politics, environmental science), this identification and prioritization is critical. A successful algorithmic ranking of “check-worthy” claims can help an expert-in-the-loop fact-checking system, thereby reducing the expert’s workload while still tackling the most salient bits of misinformation. In this work, we explore how linguistic syntax, semantics, and the contextual meaning of words play a role in determining the check-worthiness of claims. Our preliminary experiments used explicit stylometric features and simple word embeddings on the English language dataset in the Check-worthiness task of the CLEF-2018 Fact-Checking Lab, where our primary solution outperformed the other systems in terms of the mean average precision, R-precision, reciprocal rank, and precision at k for multiple values k. Here, we present an extension of this approach with more sophisticated word embeddings and report further improvements in this task. 

   more » « less
4. Automata for subregular syntax: Syntax with strings attached

   https://doi.org/10.7275/scil.3184  

   Graf, Thomas; Hanson, Kenneth (January 2025, Proceedings of the Society for Computation in Linguistics)

   Building on recent work in subregular syntax, we argue that syntactic constraints are best understood as operating not over trees, but rather strings that track structural relations such as dominance and c-command. Even constraints that seem intrinsically tied to trees (e.g. constraints on tree tiers) can be reduced to such strings. We define serial constraints as an abstraction that decomposes string constraints into a context function (which associates nodes with strings) and a requirement function (which enforces constraints on these strings). We provide a general procedure for implementing serial constraints as deterministic tree automata. The construction reveals that the many types of constraints found in subregular syntax are variants of the same computational template. Our findings open up a string-based perspective on syntactic constraints and provide a new, very general approach to the automata-theoretic study of subregular complexity. 

   more » « less
5. Monotonicity in Syntax

   https://doi.org/10.1007/978-3-662-62843-0_3  

   Graf, Thomas (January 2020, Lecture Notes in Computer Science)

   Deng, Dun; Liu, Fenrong; Liu, Mingming; Westerstahl, Dag (Ed.)

   Extending previous work on monotonicity in morphology and morphosyntax, I argue that some of the most important constraints in syntax can be analyzed in terms of monotonic functions that map specific kinds of syntactic representations to fixed, universal hierarchies. I cover the Ban Against Improper Movement, the Williams Cycle, the Ban Against Improper Case, and omnivorous number. The general method of analysis is remarkably similar across all phenomena, which suggests that monotonicity provides a unified perspective on a wide range of phenomena in syntax as well as morphology and morphosyntax. I also argue that syntax, thanks to extensive work in computational syntax, provides a unique opportunity to probe whether the prevalence of monotonicity principles in natural language is due to computational complexity considerations. Not only, then, is it possible to extend the purview of monotonicity from semantics to syntax, doing so might yield new insights into monotonicity that would not be obtainable otherwise. 

   more » « less