United States

Certifying the output of tools solving complex problems so as to ensure
the correctness of the results they provide is of tremendous importance.
Despite being widespread for SAT-solvers, this level of exigence has
not yet percolated for tools solving more complex tasks, such as model
counting or knowledge compilation. In this paper, the focus is laid on a
general family of top-down Decision-DNNF compilers. We explain how those
compilers can be tweaked so as to output certifiable Decision-DNNF
circuits, which are mainly standard Decision-DNNF circuits decorated by
annotations serving as certificates. We describe a polynomial-time
checker for testing whether a given CNFÂ formula is equivalent or not to
a given certifiable Decision-DNNF circuit. Finally, leveraging a
modified version of the compiler d4 for generating certifiable
Decision-DNNF circuits and an implementation of the checker, we present
the results of an empirical evaluation that has been conducted for
assessing how large are in practice certifiable Decision-DNNF circuits,
and how much time is needed to compute and to check such circuits.

AAAI 2021

Certifying Top-Down Decision-DNNF Compilers

technical paper

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

Approximate matrix multiplication with limited space has received ever-increasing attention due to the emergence of large-scale applications. Recently, based on a popular matrix sketching algorithm---frequent directions, previous work has introduced co-occuring directions (COD) to reduce the approximation error for this problem. Although it enjoys the space complexity of O((m_x+m_y)l) for two input matrices Xâˆˆâ„^{m_x â•³ n} and Yâˆˆâ„^{m_y â•³ n} where l is the sketch size, its time complexity is O(n(m_x+m_y+l)l), which is still very high for large input matrices. In this paper, we propose to reduce the time complexity by exploiting the sparsity of the input matrices. The key idea is to employ an approximate singular value decomposition (SVD) method which can utilize the sparsity, to reduce the number of QR decompositions required by COD. In this way, we develop sparse co-occuring directions, which reduces the time complexity to Ã•((nnz(X)+nnz(Y))l+nl^2) in expectation while keeps the same space complexity as O((m_x+m_y)l), where nnz(X) denotes the number of non-zero entries in X and the Ã• notation hides constant factors as well as polylogarithmic factors. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD. Furthermore, we empirically verify the efficiency and effectiveness of our algorithm.

Approximate Multiplication of Sparse Matrices with Limited Space

In open domain table-to-text generation, we notice the unfaithful generation usually contains hallucinated entities which can not be aligned to any input table record. We thus try to evaluate the generation faithfulness with two entity-centric metrics: table record coverage and the ratio of hallucinated entities in text, both of which are shown to have strong agreement with human judgements. Then based on these metrics,  we quantitatively analyze the correlation between training data quality and generation fidelity which indicates the potential usage of entity information in faithful generation. Motivated by these findings, we propose two methods for faithful generation: 1) augmented training by incorporating the auxiliary entity information, including both an augmented plan-based model and an unsupervised model and 2) training instance selection based on faithfulness ranking. We show these approaches improve generation fidelity in both full dataset setting and few shot setting by both automatic and human evaluations.

Towards Faithfulness in Open Domain Table-to-Text Generation from an Entity-Centric View

We study the NP-hard problem of learning a decision tree (DT) of smallest depth or size from data. We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size or depth of the DT, maximum domain size of all features, and the maximum Hamming distance between any two examples.  Our main result shows that learning DTs of smallest depth or size is fixed-parameter tractable (FPT) parameterized by the combination of all three of these parameters. We contrast this FPT-result by various hardness results that underline the algorithmic significance of the considered parameters.

Parameterized Complexity of Small Decision Tree Learning

Depth estimation from Light Field (LF) images is a crucial basis for LF related applications. Since multiple views with abundant information are available, how to effectively fuse features of these views is a key point for accurate LF depth estimation. In this paper, we propose a novel attention-based multi-level fusion network. Combined with the four-branch structure, we design intra-branch fusion strategy and inter-branch fusion strategy to hierarchically fuse effective features from different views. By introducing the attention mechanism, features of views with less occlusions and richer textures are selected inside and between these branches to provide more effective information for depth estimation. The depth maps are finally estimated after further aggregation. Experimental results shows the proposed method achieves state-of-the-art performance in both quantitative and qualitative evaluation, which also ranks first in the commonly used HCI 4D Light Field Benchmark.

Attention-Based Multi-Level Fusion Network for Light Field Depth Estimation

Recurrent autoencoder is a popular model for time series anomaly detection, in which outliers or abnormal segments are identified by their high reconstruction errors. However, existing recurrent autoencoders can easily suffer from overfitting and error accumulation due to sequential decoding. In this paper, we propose a simple yet efficient recurrent network ensemble called Recurrent Autoencoder with Multiresolution Ensemble Decoding (RAMED). By using decoders with different decoding lengths and a new coarse-to-fine fusion mechanism, lower-resolution information can help long-range decoding for decoders with higher-resolution outputs. A multiresolution shape-forcing loss is further introduced to encourage decoders' outputs at multiple resolutions to match the input's global temporal shape. Finally, the output from the decoder with the highest resolution is used to obtain an anomaly score at each time step. Extensive empirical studies on real-world benchmark data sets demonstrate that the proposed RAMED model outperforms recent strong baselines on time series anomaly detection.

Time Series Anomaly Detection with Multiresolution Ensemble Decoding

To efficiently solve high-dimensional problems with complicated constraints, projection-free online learning has received ever-increasing research interest. However, previous studies either focused on static regret that is not suitable for dynamic environments, or only established the dynamic regret bound under the smoothness of losses. In this paper, without the condition of the smoothness, we propose a novel projection-free online algorithm, and achieve an O(max{T^{2/3}V_T^{1/3},T^{1/2}}) dynamic regret bound for convex functions and an O(max{(TV_Tlog T)^{1/2},log T}) dynamic regret bound for strongly convex functions, where T is the time horizon and V_T denotes the variation of loss functions. Specifically, we first improve an existing projection-free algorithm called online conditional gradient (OCG) to enjoy small dynamic regret bounds with the prior knowledge of V_T. To work with unknowable V_T, we maintain multiple instances of the improved OCG that can handle different functional variations, and combine them with a meta-algorithm that can track the best one. Experimental results validate the efficiency and effectiveness of our algorithm.

Projection-Free Online Learning in Dynamic Environments

We introduce and study a novel majority based opinion diffusion model. Consider a graph G, which represents a social network. Assume that initially a subset of nodes, called seed nodes or early adopters, are colored either black or white, which correspond to positive or negative opinion regarding a consumer product or a technological innovation. Then, in each round an uncolored node, which is adjacent to at least one colored node, chooses the most frequent color among its neighbors.

Consider a marketing campaign which advertises a product of poor quality and its ultimate goal is that more than half of the population believe in the quality of the product at the end of the opinion diffusion process. We focus on three types of attackers which can select the seed nodes in a deterministic or random fashion and manipulate almost half of them to adopt a positive opinion toward the product (that is, to choose black color). We say that an attacker succeeds if a majority of nodes are black at the end of the process. Our main purpose is to characterize classes of graphs where an attacker cannot succeed. In particular, we prove that if the maximum degree of the underlying graph is not too large or if it has strong expansion properties, then it is fairly resilient to such attacks.

Furthermore, we prove tight bounds on the stabilization time of the process (that is, the number of rounds it needs to end) in both settings of choosing the seed nodes deterministically and randomly. We also provide several hardness results for some optimization problems regarding stabilization time and choice of seed nodes.

Majority Opinion Diffusion in Social Networks: An Adversarial Approach

Explainability is a key requirement for text classification in many application domains ranging from sentiment analysis to medical diagnosis or legal reviews. Existing methods often rely on "attention" mechanisms for explaining classification results by estimating the relative importance of input units. However, recent studies have shown that such mechanisms tend to mis-identify irrelevant input units in their explanation. In this work, we propose a hybrid human-AI approach that incorporates human rationales into attention-based text classification models to improve the explainability of classification results. Specifically, we ask workers to provide rationales for their annotation by selecting relevant pieces of text. We introduce MARTA, a Bayesian framework that jointly learns an attention-based model and the reliability of workers while injecting human rationales into model training. We derive a principled optimization algorithm based on variational inference with efficient updating rules for learning MARTA parameters. Extensive validation on real-world datasets shows that our framework significantly improves the state of the art both in terms of classification explainability and accuracy.

MARTA: Leveraging Human Rationales for Explainable Text Classification

The Test Laboratory Scheduling Problem (TLSP) and its subproblem TLSP-S are real-world industrial scheduling problems that are extensions of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, TLSP includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. For TLSP-S such a grouping is already part of the input.

In this work, we show how TLSP-S can be solved by Answer-set Programming extended with ideas from other constraint solving paradigms. We propose a novel and efficient encoding and apply an answer-set solver for constraint logic programs called clingcon. Additionally, we utilize our encoding in a Very Large Neighborhood Search framework and compare our methods with the state of the art approaches. Our approach provides new upper bounds and optimality proofs for several existing benchmark instances in the literature.

Constraint Logic Programming for Real-World Test Laboratory Scheduling

To efficiently solve online problems with complicated constraints, projection-free algorithms including online frank-wolfe (OFW) and its variants have received significant interest recently. However, in the general case, existing efficient projection-free algorithms only achieved the regret bound of O(T^{3/4}), which is worse than the regret of projection-based algorithms, where T is the number of decision rounds. In this paper, we study the special case of online learning over strongly convex sets, for which we first prove that OFW can enjoy a better regret bound of O(T^{2/3}) for general convex losses. The key idea is to refine the decaying step-size in the original OFW by a simple line search rule. Furthermore, for strongly convex losses, we propose a strongly convex variant of OFW by redefining the surrogate loss function in OFW. We show that it achieves a regret bound of O(T^{2/3}) over general convex sets and a better regret bound of O(T^{1/2}) over strongly convex sets.

Certifying Top-Down Decision-DNNF Compilers

Downloads

Next from AAAI 2021

Approximate Multiplication of Sparse Matrices with Limited Space

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Certifying Top-Down Decision-DNNF Compilers

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2021

Approximate Multiplication of Sparse Matrices with Limited Space

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads