Search

Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics., Comment: In the proceedings of AAAI-25

The evaporation of multi-component sessile droplets is key in many physicochemical applications such as inkjet printing, spray cooling, and micro-fabrication. Past fundamental research has primarily concentrated on single drops, though in applications they are rarely isolated. Here, we experimentally explore the effect of neighbouring drops on the evaporation process, employing direct imaging, confocal microscopy, and PTV. Remarkably, the centres of the drops move away from each other rather than towards each other, as we would expect due to the shielding effect at the side of the neighbouring drop and the resulting reduced evaporation on that side. We find that pinning-induced motion mediated by suspended particles in the droplets is the cause of this counter-intuitive behaviour. Finally, the azimuthal dependence of the radial velocity in the drop is compared to the evaporative flux and a perfect agreement is found.

Group equivariance has emerged as a valuable inductive bias in deep learning, enhancing generalization, data efficiency, and robustness. Classically, group equivariant methods require the groups of interest to be known beforehand, which may not be realistic for real-world data. Additionally, baking in fixed group equivariance may impose overly restrictive constraints on model architecture. This highlights the need for methods that can dynamically discover and apply symmetries as soft constraints. For neural network architectures, equivariance is commonly achieved through group transformations of a canonical weight tensor, resulting in weight sharing over a given group $G$. In this work, we propose to learn such a weight-sharing scheme by defining a collection of learnable doubly stochastic matrices that act as soft permutation matrices on canonical weight tensors, which can take regular group representations as a special case. This yields learnable kernel transformations that are jointly optimized with downstream tasks. We show that when the dataset exhibits strong symmetries, the permutation matrices will converge to regular group representations and our weight-sharing networks effectively become regular group convolutions. Additionally, the flexibility of the method enables it to effectively pick up on partial symmetries., Comment: 19 pages, 14 figures, 4 tables

A well-known, but often ignored issue in Yoneda-style definitions of cohomology objects via collections of $n$-step extensions (i.e., equivalence classes of exact sequences of a given length $n$ between two given objects, usually subject to further criteria, and equipped with some algebraic structure) is, whether such a collection of extensions forms a set. We explain that in the context of a semi-abelian variety of algebras, the answer to this question is, essentially, yes: for the collection of all $n$-step extensions between any two objects, a set of representing extensions can be chosen, so that the collection of extensions is "small" in the sense that a bijection to a set exists. We further consider some variations on this result, involving double extensions and crossed extensions (in the context of a semi-abelian variety), and Schreier extensions (in the category of monoids)., Comment: 15 pages

Modern software for propositional satisfiability problems gives a powerful automated reasoning toolkit, capable of outputting not only a satisfiable/unsatisfiable signal but also a justification of unsatisfiability in the form of resolution proof (or a more expressive proof), which is commonly used for verification purposes. Empirically, modern SAT solvers produce relatively short proofs, however, there are no inherent guarantees that these proofs cannot be significantly reduced. This paper proposes a novel branch-and-bound algorithm for finding the shortest resolution proofs; to this end, we introduce a layer list representation of proofs that groups clauses by their level of indirection. As we show, this representation breaks all permutational symmetries, thereby improving upon the state-of-the-art symmetry-breaking and informing the design of a novel workflow for proof minimization. In addition to that, we design pruning procedures that reason on proof length lower bound, clause subsumption, and dominance. Our experiments suggest that the proofs from state-of-the-art solvers could be shortened by 30-60% on the instances from SAT Competition 2002 and by 25-50% on small synthetic formulas. When treated as an algorithm for finding the shortest proof, our approach solves twice as many instances as the previous work based on SAT solving and reduces the time to optimality by orders of magnitude for the instances solved by both approaches., Comment: 42 pages, 16 figures, 8 tables, submitted to Journal of Artificial Intelligence Research

Large Language Models (LLMs) can assist in the prebunking of election misinformation. Using results from a preregistered two-wave experimental study of 4,293 U.S. registered voters conducted in August 2024, we show that LLM-assisted prebunking significantly reduced belief in specific election myths,with these effects persisting for at least one week. Confidence in election integrity was also increased post-treatment. Notably, the effect was consistent across partisan lines, even when controlling for demographic and attitudinal factors like conspiratorial thinking. LLM-assisted prebunking is a promising tool for rapidly responding to changing election misinformation narratives.

We compare the concepts of protomodular and weakly protomodular objects within the context of unital categories. Our analysis demonstrates that these two notions are generally distinct. To establish this, we introduce left pseudocancellative unital magmas and characterise weakly protomodular objects within the variety of algebras they constitute. Subsequently, we present an example of a weakly protomodular object that is not protomodular in this category.

Many time series, particularly health data streams, can be best understood as a sequence of phenomenon or events, which we call motifs. A time series motif is a short trace segment which may implicitly capture an underlying phenomenon within the time series. Specifically, we focus on glucose traces collected from continuous glucose monitors (CGMs), which inherently contain motifs representing underlying human behaviors such as eating and exercise. The ability to identify and quantify causal relationships amongst motifs can provide a mechanism to better understand and represent these patterns, useful for improving deep learning and generative models and for advanced technology development (e.g., personalized coaching and artificial insulin delivery systems). However, no previous work has developed causal discovery methods for time series motifs. Therefore, in this paper we develop MotifDisco (motif disco-very of causality), a novel causal discovery framework to learn causal relations amongst motifs from time series traces. We formalize a notion of Motif Causality (MC), inspired from Granger Causality and Transfer Entropy, and develop a Graph Neural Network-based framework that learns causality between motifs by solving an unsupervised link prediction problem. We also integrate MC with three model use cases of forecasting, anomaly detection and clustering, to showcase the use of MC as a building block for other downstream tasks. Finally, we evaluate our framework and find that Motif Causality provides a significant performance improvement in all use cases.

Decision trees are traditionally trained using greedy heuristics that locally optimize an impurity or information metric. Recently there has been a surge of interest in optimal decision tree (ODT) methods that globally optimize accuracy directly. We identify two relatively unexplored aspects of ODTs: the objective function used in training trees and tuning techniques. Additionally, the value of optimal methods is not well understood yet, as the literature provides conflicting results, with some demonstrating superior out-of-sample performance of ODTs over greedy approaches, while others show the exact opposite. In this paper, we address these three questions: what objective to optimize in ODTs; how to tune ODTs; and how do optimal and greedy methods compare? Our experimental evaluation examines 13 objective functions, including four novel objectives resulting from our analysis, seven tuning methods, and six claims from the literature on optimal and greedy methods on 165 real and synthetic data sets. Through our analysis, both conceptually and experimentally, we discover new non-concave objectives, highlight the importance of proper tuning, support and refute several claims from the literature, and provide clear recommendations for researchers and practitioners on the usage of greedy and optimal methods, and code for future comparisons.

People often strive for deep engagement in activities which is usually associated with feelings of flow: a state of full task absorption accompanied by a sense of control and fulfillment. The intrinsic factors driving such engagement and facilitating subjective feelings of flow remain unclear. Building on computational theories of intrinsic motivation, this study examines how learning progress predicts engagement and directs cognitive control. Results showed that task engagement, indicated by feelings of flow and distractibility, is a function of learning progress. Electroencephalography data further revealed that learning progress is associated with enhanced proactive preparation (e.g., reduced pre-stimulus contingent negativity variance and parietal alpha desynchronization) and improved feedback processing (e.g., increased P3b amplitude and parietal alpha desynchronization). The impact of learning progress on cognitive control is observed at the task-block and goal-episode levels, but not at the trial level. This suggests that learning progress shapes cognitive control over extended periods as progress accumulates. These findings highlight the critical role of learning progress in sustaining engagement and cognitive control in goal-directed behavior.

Robots are becoming more capable and can autonomously perform tasks such as navigating between locations. However, human oversight remains crucial. This study compared two touchless methods for directing mobile robots: voice control and gesture control, to investigate the efficiency of the methods and the preference of users. We tested these methods in two conditions: one in which participants remained stationary and one in which they walked freely alongside the robot. We hypothesized that walking alongside the robot would result in higher intuitiveness ratings and improved task performance, based on the idea that walking promotes spatial alignment and reduces the effort required for mental rotation. In a 2x2 within-subject design, 218 participants guided the quadruped robot Spot along a circuitous route with multiple 90-degree turns using rotate left, rotate right, and walk forward commands. After each trial, participants rated the intuitiveness of the command mapping, while post-experiment interviews were used to gather the participants' preferences. Results showed that voice control combined with walking with Spot was the most favored and intuitive, whereas gesture control while standing caused confusion for left/right commands. Nevertheless, 29% of participants preferred gesture control, citing increased task engagement and visual congruence as reasons. An odometry-based analysis revealed that participants often followed behind Spot, particularly in the gesture control condition, when they were allowed to walk. In conclusion, voice control with walking produced the best outcomes. Improving physical ergonomics and adjusting gesture types could make gesture control more effective.

Conformal prediction offers a practical framework for distribution-free uncertainty quantification, providing finite-sample coverage guarantees under relatively mild assumptions on data exchangeability. However, these assumptions cease to hold for time series due to their temporally correlated nature. In this work, we present a novel use of conformal prediction for time series forecasting that incorporates time series decomposition. This approach allows us to model different temporal components individually. By applying specific conformal algorithms to each component and then merging the obtained prediction intervals, we customize our methods to account for the different exchangeability regimes underlying each component. Our decomposition-based approach is thoroughly discussed and empirically evaluated on synthetic and real-world data. We find that the method provides promising results on well-structured time series, but can be limited by factors such as the decomposition step for more complex data., Comment: Accepted at COPA 2024; 34 pages, 14 figures, 8 tables (incl. appendix)

Let $F\colon \mathcal{C} \to \mathcal{E}$ be a functor from a category $\mathcal{C}$ to a homological (Borceux-Bourn) or semi-abelian (Janelidze-M\'arki-Tholen) category $\mathcal{E}$. We investigate conditions under which the homology of an object $X$ in $\mathcal{C}$ with coefficients in the functor $F$, defined via projective resolutions in $\mathcal{C}$, remains independent of the chosen resolution. Consequently, the left derived functors of $F$ can be constructed analogously to the classical abelian case. Our approach extends the concept of chain homotopy to a non-additive setting using the technique of imaginary morphisms. Specifically, we utilize the approximate subtractions of Bourn-Janelidze, originally introduced in the context of subtractive categories. This method is applicable when $\mathcal{C}$ is a pointed regular category with finite coproducts and enough projectives, provided the class of projectives is closed under protosplit subobjects, a new condition introduced in this article and naturally satisfied in the abelian context. We further assume that the functor $F$ meets certain exactness conditions: for instance, it may be protoadditive and preserve proper morphisms and binary coproducts - conditions that amount to additivity when $\mathcal{C}$ and $\mathcal{E}$ are abelian categories. Within this framework, we develop a basic theory of derived functors, compare it with the simplicial approach, and provide several examples., Comment: 45 pages; final version, accepted for publication

Low-loss deposited dielectrics are beneficial for the advancement of superconducting integrated circuits for astronomy. In the microwave band ($\mathrm{\sim}$1$\unicode{x2013}$10 GHz) the cryogenic and low-power dielectric loss is dominated by two-level systems. However, the origin of the loss in the millimeter-submillimeter band ($\mathrm{\sim}$0.1$\unicode{x2013}$1 THz) is not understood. We measured the loss of hydrogenated amorphous SiC (a-SiC:H) films in the 0.27$\unicode{x2013}$100 THz range using superconducting microstrip resonators and Fourier-transform spectroscopy. The agreement between the loss data and a Maxwell-Helmholtz-Drude dispersion model suggests that vibrational modes above 10 THz dominate the loss in the a-SiC:H above 200 GHz.

Polarization imaging can yield crucial information in multiple applications of remote sensing, such as characterization of clouds, aerosols, and the Aurora Borealis. Some applications require sub-percent polarimetric sensitivity and accuracy in determining the Stokes parameters, which can be a challenge to attain. In 2018, Sony released a low-cost CMOS-based imaging chip with integrated micro-polarizer array for general polarization measurements. We implement the calibration steps required for these Sony chips to reach sub-percent polarimetric accuracies. To analyze their performances, we have compared the characteristics of four different detector packages by three manufacturers housing either the monochromatic version or the RGB color variant. We present a comprehensive overview of the effects that these characteristics have on the polarimetric performance of the camera. They include dark noise, behavior over different gain settings, detector/pixel artifacts, and polarimetric effects determined by polarizer extinction ratios, polarizer orientations, and accuracy of polarimetric zero points due to differential pixel gains. In addition to calibrations using unpolarized light and fully linearly polarized light, we assess the polarimetric sensitivity within a tilting and rotating glass-plate set-up. We discuss the benefits of adding a rotating half-wave plate as an additional temporal modulator to generically mitigate some of the detector effects, and achieve better polarimetric sensitivity/accuracy albeit at the expense of lower temporal resolution. We conclude by presenting and discussing the polarimetric limits to which we were able to calibrate the detector effects for practical purposes. By reaching a compound absolute polarimetric uncertainty of less than a percent, these very compact, low-cost detectors are enabled for a multitude of scientific goals., Comment: Conference proceeding for SPIE Polarization: Measurement, Analysis, and Remote Sensing XVI, 31 pages, 21 figures

We provide a foundation for working with homological and homotopical methods in categorical algebra. This involves two mutually complementary components, namely (a) the strategic selection of suitable axiomatic frameworks, some well known and some new, and (b) the development of categorical tools for effective reasoning and computing within those frameworks. The selection of axiomatic frameworks begins `from the ground up' with z-exact categories. These are pointed categories in which every morphism has a kernel and cokernel. Then we progress all the way to abelian categories, en route meeting contexts such as Borceux--Bourn homological categories and Janelidze--M\'arki--Tholen semiabelian categories. We clarify the relationship between these axiomatic frameworks by direct comparison, but also by explaining how concrete examples fit into the selection. The outcome is a fine-grained set of criteria by which one can map varieties of algebras (in the sense of Universal Algebra) and topological models of algebraic theories into the various frameworks. The categorical tools for effective computation deal mostly with situations involving universal factorizations of morphisms, with exact sequences, and with the homology of chain complexes. Further, the categorical tools for computation include the `basic diagram lemmas' of homological algebra, that is the (Short) $5$-Lemma, the $(3\times 3)$-Lemma, the Snake Lemma, and applications thereof. We find that these tools are even available in some surprisingly weak categorical environments, such as the category of pointed sets. In discovering such features, we make systematic use of what we call the self-dual axis of a category., Comment: vii+343 pages; minor changes throughout the text; added material on exact and abelian categories. This is a living document, whose scope will be expanded: we welcome any comments and suggestions you may have

Renewable hydrogen storage in salt caverns requires fast injection and production rates to cope with the imbalance between energy production and consumption. Such operational conditions raise concerns about the mechanical stability of salt caverns. Choosing an appropriate constitutive model for salt mechanics is an important step in investigating this issue, and many constitutive models with several parameters have been presented in the literature. However, a robust calibration strategy to reliably determine which model and which parameter set represent the given rock, based on stress-strain data, remains an unsolved challenge. For the first time in the community, we present a multi-step strategy to determine a single parameter set based on many deformation datasets for salt rocks. Towards this end, we first develop a comprehensive constitutive model able to capture all relevant nonlinear deformation physics of transient, reverse, and steady-state creep. The determination of the single set of representative material parameters is achieved by framing the calibration process as an optimization problem, for which the global PSO algorithm is employed. Dynamic data integration is achieved by a multi-step calibration strategy for a situation where experiments are included one at a time, as they become available. Additionally, our calibration strategy is made flexible to account for mild heterogeneity between rock samples, resulting in a single set of parameters that is representative of the deformation datasets. As a rigorous mathematical analysis and the lack of relevant experimental datasets, we consider a wide range of synthetic experimental data, inspired by the existing sparse relevant data in the literature. The results of our performance analyses show that the proposed calibration strategy is robust and accuracy is improved as more experiments are included for calibration., Comment: 27 pages, 23 figures

Survival analysis studies and predicts the time of death, or other singular unrepeated events, based on historical data, while the true time of death for some instances is unknown. Survival trees enable the discovery of complex nonlinear relations in a compact human comprehensible model, by recursively splitting the population and predicting a distinct survival distribution in each leaf node. We use dynamic programming to provide the first survival tree method with optimality guarantees, enabling the assessment of the optimality gap of heuristics. We improve the scalability of our method through a special algorithm for computing trees up to depth two. The experiments show that our method's run time even outperforms some heuristics for realistic cases while obtaining similar out-of-sample performance with the state-of-the-art., Comment: Published at AAAI-24

In school districts where assignments are exclusively determined by a clearinghouse students can only appeal their assignment with a valid reason. An assignment is incontestable if it is appeal-proof. We study incontestability when students do not observe the other students' preferences and assignments. Incontestability is shown to be equivalent to individual rationality, non-wastefulness, and respect for top-priority sets (a weakening of justified envy). Stable mechanisms and those Pareto dominating them are incontestable, as well as the Top-Trading Cycle mechanism (but Boston is not). Under a mild consistency property, incontestable mechanisms are i-indinstiguishable (Li, 2017), and share similar incentive properties.

Generative artificial intelligence has the potential to both exacerbate and ameliorate existing socioeconomic inequalities. In this article, we provide a state-of-the-art interdisciplinary overview of the potential impacts of generative AI on (mis)information and three information-intensive domains: work, education, and healthcare. Our goal is to highlight how generative AI could worsen existing inequalities while illuminating how AI may help mitigate pervasive social problems. In the information domain, generative AI can democratize content creation and access, but may dramatically expand the production and proliferation of misinformation. In the workplace, it can boost productivity and create new jobs, but the benefits will likely be distributed unevenly. In education, it offers personalized learning, but may widen the digital divide. In healthcare, it might improve diagnostics and accessibility, but could deepen pre-existing inequalities. In each section we cover a specific topic, evaluate existing research, identify critical gaps, and recommend research directions, including explicit trade-offs that complicate the derivation of a priori hypotheses. We conclude with a section highlighting the role of policymaking to maximize generative AI's potential to reduce inequalities while mitigating its harmful effects. We discuss strengths and weaknesses of existing policy frameworks in the European Union, the United States, and the United Kingdom, observing that each fails to fully confront the socioeconomic challenges we have identified. We propose several concrete policies that could promote shared prosperity through the advancement of generative AI. This article emphasizes the need for interdisciplinary collaborations to understand and address the complex challenges of generative AI., Comment: PNAS Nexus, in press