Language models (LMs), like other neural networks, often favor shortcut heuristics based on surface-level patterns. Although LMs behave like n-gram models early in training, they must eventually learn hierarchical syntactic representations to correctly apply grammatical rules out-of-distribution (OOD). In this work, we use case studies of English grammar to explore how complex, diverse training data drives models to generalize OOD. We construct a framework that unifies our understanding of random variation with training dynamics, rule selection with memorization, and data diversity with complexity. We show that these factors are nuanced, and that intermediate levels of diversity and complexity lead to inconsistent behavior across random seeds and to unstable training dynamics. Our findings emphasize the critical role of training data in shaping generalization patterns and illuminate how competing model strategies lead to inconsistent generalization outcomes across random seeds.

Natural language is structured hierarchically: words are grouped into phrases or constituents, which can be further grouped to form higher-level phrases up to the full sentence. How well do the neural network models trained on language data learn this phrase structure of human language has been a subject of great interest. A flurry of past work have shown that syntax trees can be recovered from recurrent neural network (RNN) and transformer-based models trained on large-scale language corpora (Tenney et al., 2019, Peters et al., 2018, Lin et al., 2019, Wu et al., 2020). While these studies provide useful evidence of the aforementioned phenomenon, they do not shed light on the architectural choices, training paradigms or dataset characteristics that lead models to learn the phrase structure of language. A useful tool to understand these model and dataset specific properties is through the test for hierarchical generalization, i.e., evaluating the capability of a model to generalize to novel syntactic forms, which were unseen during training. A classic problem to test for hierarchical generalization is question formation, where given a declarative sentence, e.g., My walrus does move the dogs that do wait., the task is to transform it into a question: Does my walrus move the dogs that do wait? The task is accomplished by moving one auxiliary verb to the front. The correct choice to move does in this example (rather than do), is predicted both by a hierarchical rule based on the phrase-structure syntax of the sentence, and by a linear rule that says to move the first auxiliary. Hence, as a test for hierarchical generalization, we can ask, for neural networks trained from scratch on data that is consistent with both hierarchical and linear rules (i.e.,

We consider a binary classification problem under group fairness constraints, which can be one of Demographic Parity (DP), Equalized Opportunity (EOp), or Equalized Odds (EO). We propose an explicit characterization of Bayes optimal classifier under the fairness constraints, which turns out to be a simple modification rule of the unconstrained classifier. Namely, we introduce a novel instancelevel measure of bias, which we call bias score, and the modification rule is a simple linear rule on top of the finite amount of bias scores. Based on this characterization, we develop a post-hoc approach that allows us to adapt to fairness constraints while maintaining high accuracy. In the case of DP and EOp constraints, the modification rule is thresholding a single bias score, while in the case of EO constraints we are required to fit a linear modification rule with 2 parameters. The method can also be applied for composite group-fairness criteria, such as ones involving several sensitive attributes. We achieve competitive or better performance compared to both in-processing and post-processing methods across three datasets: Adult, COMPAS, and CelebA. Unlike most post-processing methods, we do not require access to sensitive attributes during the inference time. Significant improvements have been made in classification tasks using machine learning (ML) algorithms. With ML algorithms being deployed in more and more decision-making applications, it is crucial to ensure fairness in their predictions. Although the debate on what is fairness and how to measure it is ongoing (Caton & Haas, 2023), oftentimes group fairness measures are utilized in practice due to the simplicity of their verification (Chouldechova, 2017; Hardt et al., 2016a), which conform to the intuition that predictions should not be biased toward a specific group of the population.

Linear regression is the task of modeling the relationship between a result variable and some explanatory variables by a linear rule. Linear regression is a standard tool of statistical analysis, with widespread applications spanning essentially all of the sciences. While the standard linear regression task seeks to model the majority of the data, we consider problems where a regression fit could exist for some subset or portion of the data, that does not necessarily model the majority of the data. We will consider cases in which the subset with a linear model is described by some simple condition; in other words, we desire to perform linear regression on this conditional distribution. Note that neither the condition nor the model is known in advance.

In this case, we would be interested used in biological and social sciences to predict events and to in identifying a segment of the population for which describe possible relationships between variables. When addressing a linear rule is highly predictive of the price of certain cars, the task of prediction, machine learning and statistics whereas this linear rule may not provide a good prediction commonly focus on capturing the vast majority of data, overall in the larger population. Let us imagine that for this occasionally ignoring a segment of the population as "outliers" data set, and for a target fraction of the population, we found or "noise," which could be helpful to better understand a simple rule that describes the subpopulation, along with the data. Previous work by Juba (2016) gave an algorithm its linear fit.

Linear regression, the fitting of linear relationships among variables in a data set, is a standard tool in data analysis. In particular, for the sake of interpretability and utility in further analysis, we desire to find highly sparse linear relationships, i.e., involving only a few variables. Of course, such simple linear relationships often will not hold across an entire population. But, more frequently there will exist conditions - perhaps a range of parameters or a segment of a larger population - under which such sparse models fit the data quite well. For example, Rosenfeld et al. [16] used data mining heuristics to identify small segments of a population in which a few additional risk factors were highly predictive of certain kinds of cancer, whereas these same risk factors were not significant in the overall population. Simple rules for special cases may also hint at the more complex general rules. More generally, we need to develop new techniques to reason about populations in which most members are atypical in some way, which are colloquially (and somewhat abusively) referred to as long-tailed distributions. We are seeking principled alternatives to ad-hoc approaches such as trying a variety of methods for clustering the data and hoping that the identified clusters can be modeled well.

We consider the scenario of ontology-based query answering. It is generally accepted that true scalability in this setting can only be achieved via query rewriting, which in turn allows for the exploitation of standard RDBMSs. In this work, we close two open fundamental questions related to query rewriting. We establish that linear existential rules are polynomially combined rewritable, while full linear rules are polynomially (purely) rewritable; in both cases, the target query language consists of first-order or non-recursive Datalog queries. An immediate consequence of our results is that DLR-Lite_R, the extension of DL-Lite_R with n-ary roles, is polynomially combined rewritable.