The relation between (a fragment of) assumption-based argumentation (ABA) and logic programs (LPs) under stable model semantics is well-studied. However, for obtaining this relation, the ABA framework needs to be restricted to being flat, i.e., a fragment where the (defeasible) assumptions can never be entailed, only assumed to be true or false. Here, we remove this restriction and show a correspondence between non-flat ABA and LPs with negation as failure in their head. We then extend this result to so-called set-stable ABA semantics, originally defined for the fragment of non-flat ABA called bipolar ABA. We showcase how to define set-stable semantics for LPs with negation as failure in their head and show the correspondence to set-stable ABA semantics.
相關內容
The advancements of machine learning-based (ML) decision-making algorithms created various research and industrial opportunities. One of these areas is ML-based near-real-time network management applications (xApps) in Open-Radio Access Network (O-RAN). Normally, xApps are designed solely for the desired objectives, and fine-tuned for deployment. However, telecommunication companies can employ multiple xApps and deploy them in overlapping areas. Consider the different design objectives of xApps, the deployment might cause conflicts. To prevent such conflicts, we proposed the xApp distillation method that distills knowledge from multiple xApps, then uses this knowledge to train a single model that has retained the capabilities of Previous xApps. Performance evaluations show that compared conflict mitigation schemes can cause up to six times more network outages than xApp distillation in some cases.
We conduct a systematic study of the approximation properties of Transformer for sequence modeling with long, sparse and complicated memory. We investigate the mechanisms through which different components of Transformer, such as the dot-product self-attention, positional encoding and feed-forward layer, affect its expressive power, and we study their combined effects through establishing explicit approximation rates. Our study reveals the roles of critical parameters in the Transformer, such as the number of layers and the number of attention heads. These theoretical insights are validated experimentally and offer natural suggestions for alternative architectures.
The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter twin width. The foremost open problems in this area is to resolve the Pach-Tardos conjecture from 2005, which states that if a forbidden pattern $P\in\{0,1\}^{k\times l}$ is the bipartite incidence matrix of an acyclic graph (forest), then $\mathrm{Ex}(P,n) = O(n\log^{C_P} n)$, where $C_P$ is a constant depending only on $P$. This conjecture has been confirmed on many small patterns, specifically all $P$ with weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that $\mathrm{Ex}(S_0,n),\mathrm{Ex}(S_1,n) \geq n2^{\Omega(\sqrt{\log n})}$, where $S_0,S_1$ are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns $(P_t)$, specifically that for every $t\geq 2$, $\mathrm{Ex}(P_t,n)=\Theta(n(\log n/\log\log n)^t)$. This is the first proof of an asymptotically sharp bound that is $\omega(n\log n)$.
Recent work has explored the capability of large language models (LLMs) to identify and correct errors in LLM-generated responses. These refinement approaches frequently evaluate what sizes of models are able to do refinement for what problems, but less attention is paid to what effective feedback for refinement looks like. In this work, we propose looking at refinement with feedback as a composition of three distinct LLM competencies: (1) identification of bad generations; (2) fine-grained natural language feedback generation; (3) refining with fine-grained feedback. The first step can be implemented with a high-performing discriminative model and steps 2 and 3 can be implemented either via prompted or fine-tuned LLMs. A key property of this approach is that the step 2 critique model can give fine-grained feedback about errors, made possible by offloading the discrimination to a separate model in step 1. We show that models of different capabilities benefit from refining with this approach on the task of improving factual consistency of document grounded summaries. Overall, our proposed method consistently outperforms existing end-to-end refinement approaches and current trained models not fine-tuned for factuality critiquing.
Digital quantum simulation has broad applications in approximating unitary evolution of Hamiltonians. In practice, many simulation tasks for quantum systems focus on quantum states in the low-energy subspace instead of the entire Hilbert space. In this paper, we systematically investigate the complexity of digital quantum simulation based on product formulas in the low-energy subspace. We show that the simulation error depends on the effective low-energy norm of the Hamiltonian for a variety of digital quantum simulation algorithms and quantum systems, allowing improvements over the previous complexities for full unitary simulations even for imperfect state preparations {due to thermalization}. In particular, for simulating spin models in the low-energy subspace, we prove that randomized product formulas such as qDRIFT and random permutation require smaller Trotter numbers. Such improvement also persists in symmetry-protected digital quantum simulations. We prove a similar improvement in simulating the dynamics of power-law quantum interactions. We also provide a query lower bound for general digital quantum simulations in the low-energy subspace.
We present new fundamental results for the mean square error (MSE)-optimal conditional mean estimator (CME) in one-bit quantized systems for a Gaussian mixture model (GMM) distributed signal of interest, possibly corrupted by additive white Gaussian noise (AWGN). We first derive novel closed-form analytic expressions for the Bussgang estimator, the well-known linear minimum mean square error (MMSE) estimator in quantized systems. Afterward, closed-form analytic expressions for the CME in special cases are presented, revealing that the optimal estimator is linear in the one-bit quantized observation, opposite to higher resolution cases. Through a comparison to the recently studied Gaussian case, we establish a novel MSE inequality and show that that the signal of interest is correlated with the auxiliary quantization noise. We extend our analysis to multiple observation scenarios, examining the MSE-optimal transmit sequence and conducting an asymptotic analysis, yielding analytic expressions for the MSE and its limit. These contributions have broad impact for the analysis and design of various signal processing applications.
We study a nonconforming virtual element method (VEM) for advection-diffusion-reaction problems with continuous interior penalty (CIP) stabilization. The design of the method is based on a standard variational formulation of the problem (no skew-symmetrization), and boundary conditions are imposed with a Nitsche technique. We use the enhanced version of VEM, with a ``DoFi-DoFi'' stabilization in the diffusion and reaction terms. We prove stability of the proposed method and derive $h$-version error estimates.
Reduced order models (ROMs) have achieved a lot of success in reducing the computational cost of traditional numerical methods across many disciplines. For convection-dominated (e.g., turbulent) flows, however, standard ROMs generally yield inaccurate results, usually affected by spurious oscillations. Thus, ROMs are usually equipped with numerical stabilization or closure models to account for the effect of the discarded modes. The literature on ROM closures and stabilizations is large and growing fast. In this paper, we focus on one particular type of ROM closures and stabilizations that are inspired by Large Eddy Simulation (LES). These ROMs, which we call LES-ROMs, are extremely easy to implement, very efficient, and accurate. Carefully tuned LES-ROMs can accurately capture the average physical quantities of interest in challenging convection-dominated flows in many applications. LES-ROM are constructed by leveraging spatial filtering, i.e., the same principle used to build classical LES models. This ensures a modeling consistency between LES-ROMs and the approaches that generated the data used to train them. It also ``bridges'' two distinct research fields (LES and ROMs), disconnected until now. This paper is a review of LES-ROMs. It starts with a description of a versatile LES strategy called evolve-filter-relax (EFR) that has been successfully used as a full order method. We then show how the EFR strategy, and spatial filtering in general, can be leveraged to construct LES-ROMs. Several applications of LES-ROMs are presented. Finally, we draw conclusions and outline several research directions and open questions in the LES-ROM development. While we do not claim this review to be comprehensive, we certainly hope it serves as a brief and friendly introduction to this exciting research area, which has a lot of potential in practical numerical simulation of convection-dominated flows.
We introduce a multi-task setup of identifying and classifying entities, relations, and coreference clusters in scientific articles. We create SciERC, a dataset that includes annotations for all three tasks and develop a unified framework called Scientific Information Extractor (SciIE) for with shared span representations. The multi-task setup reduces cascading errors between tasks and leverages cross-sentence relations through coreference links. Experiments show that our multi-task model outperforms previous models in scientific information extraction without using any domain-specific features. We further show that the framework supports construction of a scientific knowledge graph, which we use to analyze information in scientific literature.
We introduce a generic framework that reduces the computational cost of object detection while retaining accuracy for scenarios where objects with varied sizes appear in high resolution images. Detection progresses in a coarse-to-fine manner, first on a down-sampled version of the image and then on a sequence of higher resolution regions identified as likely to improve the detection accuracy. Built upon reinforcement learning, our approach consists of a model (R-net) that uses coarse detection results to predict the potential accuracy gain for analyzing a region at a higher resolution and another model (Q-net) that sequentially selects regions to zoom in. Experiments on the Caltech Pedestrians dataset show that our approach reduces the number of processed pixels by over 50% without a drop in detection accuracy. The merits of our approach become more significant on a high resolution test set collected from YFCC100M dataset, where our approach maintains high detection performance while reducing the number of processed pixels by about 70% and the detection time by over 50%.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191