United States

We consider datasets consisting of arbitrarily structured entities (e.g., molecules,
 sequences, graphs, etc) whose similarity can be assessed with a reproducing ker-
 nel (or a family thereof). These entities are assumed to additionally have a
 set of named attributes (e.g.: number_of_atoms, stock_price, etc). These
 attributes can be used to classify the structured entities in discrete sets (e.g.,
 â€˜number_of_atoms &lt; 3&#39;, â€˜stock_price â‰¤ 100&#39;, etc) and can effectively serve
 as Boolean predicates. Our goal is to use this side-information to provide explain-
 able kernel-based clustering. To this end, we propose a method which is able
 to find among all possible entity subsets that can be described as a conjunction
 of the available predicates either a) the optimal cluster within the Reproducing
 Kernel Hilbert Space, or b) the most anomalous subset within the same space.
 Our method works employs combinatorial optimisation via an adaptation of the
 Maximum-Mean-Discrepancy measure that captures the above intuition. Finally,
 we propose a criterion to select the optimal one out of a family of kernels in a
 way that preserves the available side-information. We provide several real world
 datasets that demonstrate the usefulness of our proposed method.

AAAI 2022

Naming the Most Anomalous Cluster in Hilbert Space for Structures with Attribute Information

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. 

We consider datasets consisting of arbitrarily structured entities (e.g., molecules,
 sequences, graphs, etc) whose similarity can be assessed with a reproducing ker-
 nel (or a family thereof). These entities are assumed to additionally have a
 set of named attributes (e.g.: number_of_atoms, stock_price, etc). These
 attributes can be used to classify the structured entities in discrete sets (e.g.,
 â€˜number_of_atoms < 3', â€˜stock_price â‰¤ 100', etc) and can effectively serve
 as Boolean predicates. Our goal is to use this side-information to provide explain-
 able kernel-based clustering. To this end, we propose a method which is able
 to find among all possible entity subsets that can be described as a conjunction
 of the available predicates either a) the optimal cluster within the Reproducing
 Kernel Hilbert Space, or b) the most anomalous subset within the same space.
 Our method works employs combinatorial optimisation via an adaptation of the
 Maximum-Mean-Discrepancy measure that captures the above intuition. Finally,
 we propose a criterion to select the optimal one out of a family of kernels in a
 way that preserves the available side-information. We provide several real world
 datasets that demonstrate the usefulness of our proposed method.

technical paper

Ontology-based query answering with existential rules is well understood and implemented for positive queries, in particular conjunctive queries. For queries with negation, however, there is no agreed-upon semantics or standard implementation. This problem is unknown for simpler rule languages, such as Datalog, where it is intuitive and practical to evaluate negative queries over the least model. This fails for existential rules, which instead of a single least model have multiple universal models that may not lead to the same results for negative queries. We therefore propose universal core models as a basis for a meaningful (non-monotonic) semantics for queries with negation. Since cores are hard to compute, we identify syntactic conditions (on rules and queries) under which our core-based semantics can equivalently be obtained for other universal models, such as those produced by practical chase algorithms. Finally, we use our findings to propose a semantics for a broad class of existential rules with negation.

Answering Queries with Negation over Existential Rules

A recent report of Littmann published in the Communications of the ACM outlines the existence and the fatal impact of collusion rings in academic peer reviewing. We introduce and analyze the problem Cycle-Free Reviewing that aims at finding a review assignment without the following kind of collusion ring: A sequence of reviewers each reviewing a paper authored by the next reviewer in the sequence (with the last reviewer reviewing a paper of the first), thus creating a review cycle where each reviewer gives favorable reviews. As a result, all papers in that cycle have a high chance of acceptance independent of their respective scientific merit.

We observe that review assignments computed using a standard Linear Programming approach typically admit many short review cycles. On the negative side, we show that Cycle-Free Reviewing is NP-hard in various restricted cases (i.e., when every author is qualified to review all papers and one wants to prevent that authors review each other's or their own papers or when every author has only one paper and is only qualified to review few papers). On the positive side, among others, we show that, in some realistic settings, an assignment without any review cycles of small length always exists. This result also gives rise to an efficient heuristic for computing (weighted) cycle-free review assignments, which we show to be of excellent quality in practice.

Combating Collusion Rings is Hard but Possible

Answer set programming (ASP) is a popular declarative programming paradigm
  with a wide range of applications in artificial intelligence. Oftentimes,
  when modeling an AI problem with ASP, and in particular when we are interested
  beyond simple search for optimal solutions, an actual solution, differences
  between solutions, or number of solutions of the ASP program matter. For
  example, when a user aims to identify a specific answer set according to her
  needs, or requires the total number of diverging solutions to comprehend
  probabilistic applications such as reasoning in medical domains. Then, there
  are only certain problem specific and handcrafted encoding techniques
  available to navigate the solution space of ASP programs, which is oftentimes
  not enough. In this paper, we propose a formal and general framework for
  interactive navigation toward desired subsets of answer sets analogous to
  faceted browsing. Our approach enables the user to explore the solution space
  by consciously zooming in or out of sub-spaces of solutions at a certain
  configurable pace. We illustrate that weighted faceted navigation is
  computationally hard. Finally, we provide an implementation of our approach
  that demonstrates the feasibility of our framework for incomprehensible
  solution spaces.

Rushing and Strolling among Answer Sets - Navigation Made Easy

In an out-of-distribution (OOD) detection problem, samples of known classes (also called in-distribution classes) are used to train a special classifier. In testing, the classifier can (1) classify the test samples of known classes to their respective classes and also (2) detect samples that do not belong to any of the known classes (i.e., they belong to some unknown or OOD classes). This paper studies the problem of zero-shot out-of-distribution (OOD) detection, which still performs the same two tasks in testing but has no training except using the given known class names. This paper proposes a novel and yet simple method (called ZOC) to solve the problem. ZOC builds on top of the recent advances in zero-shot classification through multi-modal representation learning. It first extends the pre-trained language-vision model CLIP by training a text-based image description generator on top of CLIP. In testing, it uses the extended model to generate candidate unknown class names for each test sample and computes a confidence score based on both the known class names and candidate unknown class names for zero-shot OOD detection. Experimental results on 5 benchmark datasets for OOD detection demonstrate that ZOC outperforms the baselines by a large margin.

Zero-Shot Out-of-Distribution Detection Based on the Pre-Trained Model CLIP

In this paper, we propose a framework centering around a novel architecture called the Event Decomposition Recomposition Network (EDRNet) to tackle the Audio-Visual Event (AVE) localization problem in the supervised and weakly supervised settings. AVEs in the real world exhibit common unraveling patterns (termed as Event Progress Checkpoints(EPC)), which humans can perceive through the cooperation of their auditory and visual senses. Unlike earlier methods which attempt to recognize entire event sequences, the EDRNet models EPCs and inter-EPC relationships using stacked temporal convolutions. Based on the postulation that EPC representations are theoretically consistent for an event category, we introduce the State Machine Based Video Fusion, a novel augmentation technique that blends source videos using different EPC template sequences. Additionally, we design a new loss function called the Land-Shore-Sea loss to compactify continuous foreground and background representations. Lastly, to alleviate the issue of confusing events during weak supervision, we propose a prediction stabilization method called Bag to Instance Label Correction. Experiments on the AVE dataset show that our collective framework outperforms the state-of-the-art by a sizable margin.

Decompose the Sounds and Pixels, Recompose the Events

Current pre-training methods in computer vision focus on natural images in the daily-life context. However, abstract diagrams such as icons and symbols are common and important in the real world. We are inspired by Tangram, a game that requires replicating an abstract pattern from seven dissected shapes. By recording human experience in solving tangram puzzles, we present the Tangram dataset and show that a pre-trained neural model on the Tangram helps solve some mini visual tasks based on low-resolution vision. Extensive experiments demonstrate that our proposed method generates intelligent solutions for aesthetic tasks such as folding clothes and evaluating room layouts. The pre-trained feature extractor can facilitate the convergence of few-shot learning tasks on human handwriting and improve the accuracy in identifying icons by their contours. The Tangram dataset is available at https://github.com/yizhouzhao/Tangram.

Learning from the Tangram to Solve Mini Visual Tasks

An activation function is a crucial component of a neural network that introduces non-linearity in the network. The state-of-the-art performance of a neural network depends also on the perfect choice of an activation function. We propose two novel non-monotonic smooth trainable activation functions, called ErfAct and Pserf. Experiments suggest that the proposed functions improve the network performance significantly compared to the widely used activations like ReLU, Swish, and Mish. Replacing ReLU by ErfAct and Pserf, we have 5.68% and 5.42% improvement for top-1 accuracy on Shufflenet V2 (2.0x) network in CIFAR100 dataset, 2.11% and 1.96% improvement for top-1 accuracy on Shufflenet V2 (2.0x) network in CIFAR10 dataset, 1.0%, and 1.0% improvement on mean average precision (mAP) on SSD300 model in Pascal VOC dataset.

ErfAct and Pserf: Non-Monotonic Smooth Trainable Activation Functions

We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. The exact distances between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a committee of k alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a committee is her distance from the q-th closest alternative in the committee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of k and q: The distortion is unbounded when q <= k/3, asymptotically linear in the number of agents when k/3 < q <= k/2, and constant when q > k/2.

The Metric Distortion of Multiwinner Voting

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

On Improving Resource Allocations by Sharing

Transformer language models have made tremendous strides in natural language understanding tasks. However, the complexity of natural language makes it challenging to ascertain how accurately these models are tracking the world state underlying the text. Motivated by this issue, we consider the task of language modeling for the game of chess. Unlike natural language, chess notations describe a simple, constrained, and deterministic domain. Moreover, we observe that the appropriate choice of chess notation allows for directly probing the world state, without requiring any additional probing-related machinery. We find that: (a) With enough training data, transformer language models can learn to track pieces and predict legal moves with high accuracy when trained solely on move sequences. (b) For small training sets providing access to board state information during training can yield significant improvements. (c) The success of transformer language models is dependent on access to the entire game history i.e. â€œfull attentionâ€. Approximating this full attention results in a significant performance drop. We propose this testbed as a benchmark for future work on the development and analysis of transformer language models.

Downloads

Next from AAAI 2022

Answering Queries with Negation over Existential Rules

Similar lecture

TRF: Learning Kernels with Tuned Random Features

.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 2022

Answering Queries with Negation over Existential Rules

Similar lecture

TRF: Learning Kernels with Tuned Random Features

Downloads