bluuebunny/crossref_metadata_2025 huggingface dataset:
Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation
Authors: Zhu Heng , Ling Qing
Published: July 2022

This paper aims at jointly addressing two seemly conflicting issues in federated learning: differential privacy (DP) and Byzantine-robustness, which are particularly challenging when the distributed data are non-i.i.d. (independent and identically distributed). The standard DP mechanisms add noise to the transmitted messages, and entangles with robust stochastic gradient aggregation to defend against Byzantine attacks. In this paper, we decouple the two issues via robust stochastic model aggregation, in the sense that our proposed DP mechanisms and the defense against Byzantine attacks have separated influence on the learning performance. Leveraging robust stochastic model aggregation, at each iteration, each worker calculates the difference between the local model and the global one, followed by sending the element-wise signs to the master node, which enables robustness to Byzantine attacks. Further, we design two DP mechanisms to perturb the uploaded signs for the purpose of privacy preservation, and prove that they are (epsilon,0)-DP by exploiting the properties of noise distributions. With the tools of Moreau envelop and proximal point projection, we establish the convergence of the proposed algorithm when the cost function is nonconvex. We analyze the trade-off between privacy preservation and learning performance, and show that the influence of our proposed DP mechanisms is decoupled with that of robust stochastic model aggregation. Numerical experiments demonstrate the effectiveness of the proposed algorithm.
The Complexity of Envy-Free Graph Cutting
Authors: Deligkas Argyrios , Eiben Eduard , Ganian Robert , Hamm Thekla , Ordyniak Sebastian
Published: July 2022

We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.
Multi-Tier Platform for Cognizing Massive Electroencephalogram
Authors: Chen Zheng , Zhu Lingwei , Yang Ziwei , Zhang Renyuan
Published: July 2022

An end-to-end platform assembling multiple tiers is built for precisely cognizing brain activities. Being fed massive electroencephalogram (EEG) data, the time-frequency spectrograms are conventionally projected into the episode-wise feature matrices (seen as tier-1). A spiking neural network (SNN) based tier is designed to distill the principle information in terms of spike-streams from the rare features, which maintains the temporal implication in the nature of EEGs. The proposed tier-3 transposes time- and space-domain of spike patterns from the SNN; and feeds the transposed pattern-matrices into an artificial neural network (ANN, Transformer specifically) known as tier-4, where a special spanning topology is proposed to match the two-dimensional input form. In this manner, cognition such as classification is conducted with high accuracy. For proof-of-concept, the sleep stage scoring problem is demonstrated by introducing multiple EEG datasets with the largest comprising 42,560 hours recorded from 5,793 subjects. From experiment results, our platform achieves the general cognition overall accuracy of 87% by leveraging sole EEG, which is 2% superior to the state-of-the-art. Moreover, our developed multi-tier methodology offers visible and graphical interpretations of the temporal characteristics of EEG by identifying the critical episodes, which is demanded in neurodynamics but hardly appears in conventional cognition scenarios.
Efficient and Accurate Conversion of Spiking Neural Network with Burst Spikes
Authors: Li Yang , Zeng Yi
Published: July 2022

Spiking neural network (SNN), as a brain-inspired energy-efficient neural network, has attracted the interest of researchers. While the training of spiking neural networks is still an open problem. One effective way is to map the weight of trained ANN to SNN to achieve high reasoning ability. However, the converted spiking neural network often suffers from performance degradation and a considerable time delay. To speed up the inference process and obtain higher accuracy, we theoretically analyze the errors in the conversion process from three perspectives: the differences between IF and ReLU, time dimension, and pooling operation. We propose a neuron model for releasing burst spikes, a cheap but highly efficient method to solve residual information. In addition, Lateral Inhibition Pooling (LIPooling) is proposed to solve the inaccuracy problem caused by MaxPooling in the conversion process. Experimental results on CIFAR and ImageNet demonstrate that our algorithm is efficient and accurate. For example, our method can ensure nearly lossless conversion of SNN and only use about 1/10 (less than 100) simulation time under 0.693x energy consumption of the typical method. Our code is available at https://github.com/Brain-Inspired-Cognitive-Engine/Conversion_Burst.
Semi-Supervised Imitation Learning of Team Policies from Suboptimal Demonstrations
Authors: Seo Sangwon , Unhelkar Vaibhav V.
Published: July 2022

We present Bayesian Team Imitation Learner (BTIL), an imitation learning algorithm to model the behavior of teams performing sequential tasks in Markovian domains. In contrast to existing multi-agent imitation learning techniques, BTIL explicitly models and infers the time-varying mental states of team members, thereby enabling learning of decentralized team policies from demonstrations of suboptimal teamwork. Further, to allow for sample- and label-efficient policy learning from small datasets, BTIL employs a Bayesian perspective and is capable of learning from semi-supervised demonstrations. We demonstrate and benchmark the performance of BTIL on synthetic multi-agent tasks as well as a novel dataset of human-agent teamwork. Our experiments show that BTIL can successfully learn team policies from demonstrations despite the influence of team members' (time-varying and potentially misaligned) mental states on their behavior.
On Preferences and Priority Rules in Abstract Argumentation
Authors: Alfano Gianvincenzo , Greco Sergio , Parisi Francesco , Trubitsyna Irina
Published: July 2022

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism for argumentation in AI.

Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way.

In this paper we first investigate the complexity of the verification as well as credulous and skeptical acceptance problems in Preference-based AF (PAF) that extends AF with preferences over arguments.

Next, after introducing new semantics for AF where extensions are selected using cardinality (instead of set inclusion) criteria and investigating their complexity, we introduce a framework called AF with Priority rules (AFP) that extends AF with sequences of priority rules.

AFP generalizes AF with classical set-inclusion and cardinality based semantics, suggesting that argumentation semantics can be viewed as ways to express priorities among extensions.

Finally, we extend AFP by proposing AF with Priority rules and Preferences (AFP^2), where also preferences over arguments can be used to define priority rules, and study the complexity of the above-mentioned problems.
Verification and Monitoring for First-Order LTL with Persistence-Preserving Quantification over Finite and Infinite Traces
Authors: Calvanese Diego , De Giacomo Giuseppe , Montali Marco , Patrizi Fabio
Published: July 2022

We address the problem of model checking first-order dynamic systems where new objects can be injected in the active domain during execution. Notable examples are systems induced by a first-order action theory, e.g., expressed in the Situation Calculus. Recent results have shown that, under the state-boundedness assumption, such systems, in spite of having a first-order representation of the state, admit decidable model checking for full first-order mu-calculus. However, interestingly, model checking remains undecidable in the case of first-order LTL (LTL-FO). In this paper, we show that in LTL-FOp, which is the fragment of LTL-FO in which quantification is over objects that persist along traces, model checking state-bounded systems becomes decidable over finite and infinite traces. We then employ this result to show how to handle monitoring of LTL-FOp properties against a trace stemming from an unknown state-bounded dynamic system, simultaneously considering the finite trace up to the current point, and all its possibly infinite future continuations.
LTLf Synthesis as AND-OR Graph Search: Knowledge Compilation at Work
Authors: De Giacomo Giuseppe , Favorito Marco , Li Jianwen , Vardi Moshe Y. , Xiao Shengping , Zhu Shufang
Published: July 2022

Synthesis techniques for temporal logic specifications are typically based on exploiting symbolic techniques, as done in model checking. These symbolic techniques typically use backward fixpoint computation. Planning, which can be seen as a specific form of synthesis, is a witness of the success of forward search approaches. In this paper, we develop a forward-search approach to full-fledged Linear Temporal Logic on finite traces (LTLf) synthesis. We show how to compute the Deterministic Finite Automaton (DFA) of an LTLf formula on-the-fly, while performing an adversarial forward search towards the final states, by considering the DFA as a sort of AND-OR graph. Our approach is characterized by branching on suitable propositional formulas, instead of individual evaluations, hence radically reducing the branching factor of the search space. Specifically, we take advantage of techniques developed for knowledge compilation, such as Sentential Decision Diagrams (SDDs), to implement the approach efficiently.
Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies
Authors: Funk Maurice , Jung Jean Christoph , Lutz Carsten
Published: July 2022

We study ELI queries (ELIQs) in the presence of ontologies formulated in the description logic DL-Lite. For the dialect DL-LiteH, we show that ELIQs have a frontier (set of least general generalizations) that is of polynomial size and can be computed in polynomial time. In the dialect DL-LiteF, in contrast, frontiers may be infinite. We identify a natural syntactic restriction that enables the same positive results as for DL-LiteH. We use our results on frontiers to show that ELIQs are learnable in polynomial time in the presence of a DL-LiteH / restricted DL-LiteF ontology in Angluin's framework of exact learning with only membership queries.
In Data We Trust: The Logic of Trust-Based Beliefs
Authors: Jiang Junli , Naumov Pavel
Published: July 2022

The paper proposes a data-centred approach to reasoning about the interplay between trust and beliefs. At its core, is the modality "under the assumption that one dataset is trustworthy, another dataset informs a belief in a statement". The main technical result is a sound and complete logical system capturing the properties of this modality.
Search Space Expansion for Efficient Incremental Inductive Logic Programming from Streamed Data
Authors: Law Mark , Broda Krysia , Russo Alessandra
Published: July 2022

In the past decade, several systems for learning Answer Set Programs (ASP) have been proposed, including the recent FastLAS system. Compared to other state-of-the-art approaches to learning ASP, FastLAS is more scalable, as rather than computing the hypothesis space in full, it computes a much smaller subset relative to a given set of examples that is nonetheless guaranteed to contain an optimal solution to the task (called an OPT-sufficient subset). On the other hand, like many other Inductive Logic Programming (ILP) systems, FastLAS is designed to be run on a fixed learning task meaning that if new examples are discovered after learning, the whole process must be run again.

In many real applications, data arrives in a stream. Rerunning an ILP system from scratch each time new examples arrive is inefficient. In this paper we address this problem by presenting IncrementalLAS, a system that uses a new technique, called hypothesis space expansion, to enable a FastLAS-like OPT-sufficient subset to be expanded each time new examples are discovered. We prove that this preserves FastLAS's guarantee of finding an optimal solution to the full task (including the new examples), while removing the need to repeat previous computations. Through our evaluation, we demonstrate that running IncrementalLAS on tasks updated with sequences of new examples is significantly faster than re-running FastLAS from scratch on each updated task.
Revision by Comparison for Ranking Functions
Authors: Sezgin Meliha , Kern-Isberner Gabriele
Published: July 2022

Revision by Comparison (RbC) is a non-prioritized belief revision mechanism on epistemic states that specifies constraints on the plausibility of an input sentence via a designated reference sentence, allowing for kind of relative belief revision. In this paper, we make the strategy underlying RbC more explicit and transfer the mechanism together with its intuitive strengths to a semi-quantitative framework based on ordinal conditional functions where a more elegant implementation of RbC is possible. We furthermore show that RbC can be realized as an iterated revision by so-called weak conditionals. Finally, we point out relations of RbC to credibility-limited belief revision, illustrating the versatility of RbC for advanced belief revision operations.
Considering Constraint Monotonicity and Foundedness in Answer Set Programming
Authors: Shen Yi-Dong , Eiter Thomas
Published: July 2022

Should the properties of constraint monotonicity and foundedness be mandatory requirements that every answer set and world view semantics must satisfy? This question is challenging and has incurred a debate in answer set programming (ASP). In this paper we address the question by introducing natural logic programs whose expected answer sets and world views violate these properties and thus may be viewed as counter-examples to these requirements. Specifically we use instances of the generalized strategic companies problem for ASP benchmark competitions as concrete examples to demonstrate that the requirements of constraint monotonicity and foundedness may exclude expected answer sets for some simple disjunctive programs and world views for some epistemic specifications. In conclusion these properties should not be mandatory conditions for an answer set and world view semantics in general.
Learning Label Initialization for Time-Dependent Harmonic Extension.
Authors: Azad Amitoz
Published: July 2022

Node classification on graphs can be formulated as the Dirichlet problem on graphs where the signal is given at the labeled nodes, and the harmonic extension is done on the unlabeled nodes. This paper considers a time-dependent version of the Dirichlet problem on graphs and shows how to improve its solution by learning the proper initialization vector on the unlabeled nodes. Further, we show that the improved solution is at par with state-of-the-art methods used for node classification. Finally, we conclude this paper by discussing the importance of parameter t, pros, and future directions.
Heterogeneous Ensemble Knowledge Transfer for Training Large Models in Federated Learning
Authors: Cho Yae Jee , Manoel Andre , Joshi Gauri , Sim Robert , Dimitriadis Dimitrios
Published: July 2022

Federated learning (FL) enables edge-devices to collaboratively learn a model without disclosing their private data to a central aggregating server. Most existing FL algorithms require models of identical architecture to be deployed across the clients and server, making it infeasible to train large models due to clients' limited system resources. In this work, we propose a novel ensemble knowledge transfer method named Fed-ET in which small models (different in architecture) are trained on clients, and used to train a larger model at the server. Unlike in conventional ensemble learning, in FL the ensemble can be trained on clients' highly heterogeneous data. Cognizant of this property, Fed-ET uses a weighted consensus distillation scheme with diversity regularization that efficiently extracts reliable consensus from the ensemble while improving generalization by exploiting the diversity within the ensemble. We show the generalization bound for the ensemble of weighted models trained on heterogeneous datasets that supports the intuition of Fed-ET. Our experiments on image and language tasks show that Fed-ET significantly outperforms other state-of-the-art FL algorithms with fewer communicated parameters, and is also robust against high data-heterogeneity.
Reinforcement Learning with Option Machines
Authors: den Hengst Floris , Francois-Lavet Vincent , Hoogendoorn Mark , van Harmelen Frank
Published: July 2022

Reinforcement learning (RL) is a powerful framework for learning complex behaviors, but lacks adoption in many settings due to sample size requirements. We introduce a framework for increasing sample efficiency of RL algorithms. Our approach focuses on optimizing environment rewards with high-level instructions. These are modeled as a high-level controller over temporally extended actions known as options. These options can be looped, interleaved and partially ordered with a rich language for high-level instructions. Crucially, the instructions may be underspecified in the sense that following them does not guarantee high reward in the environment. We present an algorithm for control with these so-called option machines (OMs), discuss option selection for the partially ordered case and describe an algorithm for learning with OMs. We compare our approach in zero-shot, single- and multi-task settings in an environment with fully specified and underspecified instructions. We find that OMs perform significantly better than or comparable to the state-of-art in all environments and learning settings.
Residual Contrastive Learning for Image Reconstruction: Learning Transferable Representations from Noisy Images
Authors: Dong Nanqing , Maggioni Matteo , Yang Yongxin , Pérez-Pellitero Eduardo , Leonardis Ales , McDonagh Steven
Published: July 2022

This paper is concerned with contrastive learning (CL) for low-level image restoration and enhancement tasks. We propose a new label-efficient learning paradigm based on residuals, residual contrastive learning (RCL), and derive an unsupervised visual representation learning framework, suitable for low-level vision tasks with noisy inputs. While supervised image reconstruction aims to minimize residual terms directly, RCL alternatively builds a connection between residuals and CL by defining a novel instance discrimination pretext task, using residuals as the discriminative feature. Our formulation mitigates the severe task misalignment between instance discrimination pretext tasks and downstream image reconstruction tasks, present in existing CL frameworks. Experimentally, we find that RCL can learn robust and transferable representations that improve the performance of various downstream tasks, such as denoising and super resolution, in comparison with recent self-supervised methods designed specifically for noisy inputs. Additionally, our unsupervised pre-training can significantly reduce annotation costs whilst maintaining performance competitive with fully-supervised image reconstruction.
Multi-Vector Embedding on Networks with Taxonomies
Authors: Fan Yue , Ma Xiuli
Published: July 2022

A network can effectively depict close relationships among its nodes, with labels in a taxonomy describing the nodes' rich attributes. Network embedding aims at learning a representation vector for each node and label to preserve their proximity, while most existing methods suffer from serious underfitting when dealing with datasets with dense node-label links. For instance, a node could have dozens of labels describing its diverse properties, causing the single node vector overloaded and hard to fit all the labels. We propose HIerarchical Multi-vector Embedding (HIME), which solves the underfitting problem by adaptively learning multiple 'branch vectors' for each node to dynamically fit separate sets of labels in a hierarchy-aware embedding space. Moreover, a 'root vector' is learned for each node based on its branch vectors to better predict the sparse but valuable node-node links with the knowledge of its labels. Experiments reveal HIME’s comprehensive advantages over existing methods on tasks such as proximity search, link prediction and hierarchical classification.
Fixed-Budget Pure Exploration in Multinomial Logit Bandits
Authors: Fang Boli
Published: July 2022

In this paper we investigate pure exploration problem in Multinomial Logit bandit(MNL-bandit) under fixed budget settings, a problem motivated by real-time applications in online advertising and retailing. Given an MNL-bandit instance and a fixed exploration budget, our goal is to minimize the misidentification error of the optimal assortment. Towards such an end we propose an algorithm that achieve gap-dependent complexities, and complement our investigation with a discussion on recent studies and a minimax lower bound on misidentification probability. To the best of our knowledge, our paper is the first to address the recently proposed open problem of fixed-budget pure exploration problem for MNL-bandits.
DeepExtrema: A Deep Learning Approach for Forecasting Block Maxima in Time Series Data
Authors: Galib Asadullah Hill , McDonald Andrew , Wilson Tyler , Luo Lifeng , Tan Pang-Ning
Published: July 2022

Accurate forecasting of extreme values in time series is critical due to the significant impact of extreme events on human and natural systems. This paper presents DeepExtrema, a novel framework that combines a deep neural network (DNN) with generalized extreme value (GEV) distribution to forecast the block maximum value of a time series. Implementing such a network is a challenge as the framework must preserve the inter-dependent constraints among the GEV model parameters even when the DNN is initialized. We describe our approach to address this challenge and present an architecture that enables both conditional mean and quantile prediction of the block maxima. The extensive experiments performed on both real-world and synthetic data demonstrated the superiority of DeepExtrema compared to other baseline methods.
A Reinforcement Learning-Informed Pattern Mining Framework for Multivariate Time Series Classification
Authors: Gao Ge , Gao Qitong , Yang Xi , Pajic Miroslav , Chi Min
Published: July 2022

Multivariate time series (MTS) classification is a challenging and important task in various domains and real-world applications. Much of prior work on MTS can be roughly divided into neural network (NN)- and pattern-based methods. The former can lead to robust classification performance, but many of the generated patterns are challenging to interpret; while the latter often produce interpretable patterns that may not be helpful for the classification task. In this work, we propose a reinforcement learning (RL) informed PAttern Mining framework (RLPAM) to identify interpretable yet important patterns for MTS classification. Our framework has been validated by 30 benchmark datasets as well as real-world large-scale electronic health records (EHRs) for an extremely challenging task: sepsis shock early prediction. We show that RLPAM outperforms the state-of-the-art NN-based methods on 14 out of 30 datasets as well as on the EHRs. Finally, we show how RL informed patterns can be interpretable and can improve our understanding of septic shock progression.
Bootstrapping Informative Graph Augmentation via A Meta Learning Approach
Authors: Gao Hang , Li Jiangmeng , Qiang Wenwen , Si Lingyu , Sun Fuchun , Zheng Changwen
Published: July 2022

Recent works explore learning graph representations in a self-supervised manner. In graph contrastive learning, benchmark methods apply various graph augmentation approaches. However, most of the augmentation methods are non-learnable, which causes the issue of generating unbeneficial augmented graphs. Such augmentation may degenerate the representation ability of graph contrastive learning methods. Therefore, we motivate our method to generate augmented graph with a learnable graph augmenter, called MEta Graph Augmentation (MEGA). We then clarify that a "good" graph augmentation must have uniformity at the instance-level and informativeness at the feature-level. To this end, we propose a novel approach to learning a graph augmenter that can generate an augmentation with uniformity and informativeness. The objective of the graph augmenter is to promote our feature extraction network to learn a more discriminative feature representation, which motivates us to propose a meta-learning paradigm. Empirically, the experiments across multiple benchmark datasets demonstrate that MEGA outperforms the state-of-the-art methods in graph self-supervised learning tasks. Further experimental studies prove the effectiveness of different terms of MEGA. Our codes are available at https://github.com/hang53/MEGA.
Leveraging Class Abstraction for Commonsense Reinforcement Learning via Residual Policy Gradient Methods
Authors: Hopner Niklas , Tiddi Ilaria , van Hoof Herke
Published: July 2022

Enabling reinforcement learning (RL) agents to leverage a knowledge base while learning from experience promises to advance RL in knowledge intensive domains. However, it has proven difficult to leverage knowledge that is not manually tailored to the environment. We propose to use the subclass relationships present in open-source knowledge graphs to abstract away from specific objects. We develop a residual policy gradient method that is able to integrate knowledge across different abstraction levels in the class hierarchy. Our method results in improved sample efficiency and generalisation to unseen objects in commonsense games, but we also investigate failure modes, such as excessive noise in the extracted class knowledge or environments with little class structure.
Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem
Authors: Flammini Michele , Varricchio Giovanna
Published: July 2022

We investigate strategyproof mechanisms in the Group Activity Selection Problem with the additively separable property. Namely, agents have distinct preferences for each activity and individual weights for the other agents. We evaluate our mechanisms in terms of their approximation ratio with respect to the maximum utilitarian social welfare.

We first show that, for arbitrary non-negative preferences, no deterministic mechanism can achieve a bounded approximation ratio. Thus, we provide a randomized k-approximate mechanism, where k is the number of activities, and a corresponding 2-2/(k+1) lower bound. Furthermore, we propose a tight (2 - 1/k)-approximate randomized mechanism when activities are copyable.

We then turn our attention to instances where preferences can only be unitary, that is 0 or 1. In this case, we provide a k-approximate deterministic mechanism, which we show to be the best possible one within the class of strategyproof and anonymous mechanisms. We also provide a general lower bound of Ω({\sqrt{k}) when anonymity is no longer a constraint. Finally, we focus on unitary preferences and weights, and prove that, while any mechanism returning the optimum is not strategyproof, there exists a 2-approximate deterministic mechanism.
Set Interdependence Transformer: Set-to-Sequence Neural Networks for Permutation Learning and Structure Prediction
Authors: Jurewicz Mateusz , Derczynski Leon
Published: July 2022

The task of learning to map an input set onto a permuted sequence of its elements is challenging for neural networks. Set-to-sequence problems occur in natural language processing, computer vision and structure prediction, where interactions between elements of large sets define the optimal output. Models must exhibit relational reasoning, handle varying cardinalities and manage combinatorial complexity. Previous attention-based methods require n layers of their set transformations to explicitly represent n-th order relations. Our aim is to enhance their ability to efficiently model higher-order interactions through an additional interdependence component. We propose a novel neural set encoding method called the Set Interdependence Transformer, capable of relating the set's permutation invariant representation to its elements within sets of any cardinality. We combine it with a permutation learning module into a complete, 3-part set-to-sequence model and demonstrate its state-of-the-art performance on a number of tasks. These range from combinatorial optimization problems, through permutation learning challenges on both synthetic and established NLP datasets for sentence ordering, to a novel domain of product catalog structure prediction. Additionally, the network's ability to generalize to unseen sequence lengths is investigated and a comparative empirical analysis of the existing methods' ability to learn higher-order interactions is provided.
Learning from Students: Online Contrastive Distillation Network for General Continual Learning
Authors: Li Jin , Ji Zhong , Wang Gang , Wang Qiang , Gao Feng
Published: July 2022

The goal of General Continual Learning (GCL) is to preserve learned knowledge and learn new knowledge with constant memory from an infinite data stream where task boundaries are blurry. Distilling the model's response of reserved samples between the old and the new models is an effective way to achieve promise performance on GCL. However, it accumulates the inherent old model's response bias and is not robust to model changes. To this end, we propose an Online Contrastive Distillation Network (OCD-Net) to tackle these problems, which explores the merit of the student model in each time step to guide the training process of the student model. Concretely, the teacher model is devised to help the student model to consolidate the learned knowledge, which is trained online via integrating the model weights of the student model to accumulate the new knowledge. Moreover, our OCD-Net incorporates both relation and adaptive response to help the student model alleviate the catastrophic forgetting, which is also beneficial for the teacher model preserves the learned knowledge. Extensive experiments on six benchmark datasets demonstrate that our proposed OCD-Net significantly outperforms state-of-the-art approaches in 3.26%~8.71% with various buffer sizes. Our code is available at https://github.com/lijincm/OCD-Net.
Can Buyers Reveal for a Better Deal?
Authors: Halpern Daniel , Kehne Gregory , Tucker-Foltz Jamie
Published: July 2022

We study market interactions in which buyers are allowed to credibly reveal partial information about their types to the seller. Previous recent work has studied the special case of one buyer and one good, showing that such communication can simultaneously improve social welfare and ex ante buyer utility. However, with multiple buyers, we find that the buyer-optimal signalling schemes from the one-buyer case are actually harmful to buyer welfare. Moreover, we prove several impossibility results showing that, with either multiple i.i.d. buyers or multiple i.i.d. goods, maximizing buyer utility can be at odds with social efficiency, which is surprising in contrast with the one-buyer, one-good case. Finally, we investigate the computational tractability of implementing desirable equilibrium outcomes. We find that, even with one buyer and one good, optimizing buyer utility is generally NP-hard but tractable in a practical restricted setting.
JueWu-MC: Playing Minecraft with Sample-efficient Hierarchical Reinforcement Learning
Authors: Lin Zichuan , Li Junyou , Shi Jianing , Ye Deheng , Fu Qiang , Yang Wei
Published: July 2022

Learning rational behaviors in open-world games like Minecraft remains to be challenging for Reinforcement Learning (RL) research due to the compound challenge of partial observability, high-dimensional visual perception and delayed reward. To address this, we propose JueWu-MC, a sample-efficient hierarchical RL approach equipped with representation learning and imitation learning to deal with perception and exploration. Specifically, our approach includes two levels of hierarchy, where the high-level controller learns a policy to control over options and the low-level workers learn to solve each sub-task. To boost the learning of sub-tasks, we propose a combination of techniques including 1) action-aware representation learning which captures underlying relations between action and representation, 2) discriminator-based self-imitation learning for efficient exploration, and 3) ensemble behavior cloning with consistency filtering for policy robustness. Extensive experiments show that JueWu-MC significantly improves sample efficiency and outperforms a set of baselines by a large margin. Notably, we won the championship of the NeurIPS MineRL 2021 research competition and achieved the highest performance score ever.
SELC: Self-Ensemble Label Correction Improves Learning with Noisy Labels
Authors: Lu Yangdi , He Wenbo
Published: July 2022

Deep neural networks are prone to overfitting noisy labels, resulting in poor generalization performance. To overcome this problem, we present a simple and effective method self-ensemble label correction (SELC) to progressively correct noisy labels and refine the model. We look deeper into the memorization behavior in training with noisy labels and observe that the network outputs are reliable in the early stage. To retain this reliable knowledge, SELC uses ensemble predictions formed by an exponential moving average of network outputs to update the original noisy labels. We show that training with SELC refines the model by gradually reducing supervision from noisy labels and increasing supervision from ensemble predictions. Despite its simplicity, compared with many state-of-the-art methods, SELC obtains more promising and stable results in the presence of class-conditional, instance-dependent, and real-world label noise. The code is available at https://github.com/MacLLL/SELC.
Locally Normalized Soft Contrastive Clustering for Compact Clusters
Authors: Ma Xin , Kim Won Hwa
Published: July 2022

Recent deep clustering algorithms take advantage of self-supervised learning and self-training techniques to map the original data into a latent space, where the data embedding and clustering assignment can be jointly optimized. However, as many recent datasets are enormous and noisy, getting a clear boundary between different clusters is challenging with existing methods that mainly focus on contracting similar samples together and overlooking samples near boundary of clusters in the latent space. In this regard, we propose an end-to-end deep clustering algorithm, i.e., Locally Normalized Soft Contrastive Clustering (LNSCC). It takes advantage of similarities among each sample's local neighborhood and globally disconnected samples to leverage positiveness and negativeness of sample pairs in a contrastive way to separate different clusters. Experimental results on various datasets illustrate that our proposed approach achieves outstanding clustering performance over most of the state-of-the-art clustering methods for both image and non-image data even without convolution.
Tessellation-Filtering ReLU Neural Networks
Authors: Moser Bernhard A. , Lewandowski Michal , Kargaran Somayeh , Zellinger Werner , Biggio Battista , Koutschan Christoph
Published: July 2022

We identify tessellation-filtering ReLU neural networks that, when composed with another ReLU network, keep its non-redundant tessellation unchanged or reduce it.The additional network complexity modifies the shape of the decision surface without increasing the number of linear regions. We provide a mathematical understanding of the related additional expressiveness by means of a novel measure of shape complexity by counting deviations from convexity which results in a Boolean algebraic characterization of this special class. A local representation theorem gives rise to novel approaches for pruning and decision surface analysis.
Certified Robustness via Randomized Smoothing over Multiplicative Parameters of Input Transformations
Authors: Muravev Nikita , Petiushko Aleksandr
Published: July 2022

Currently the most popular method of providing robustness certificates is randomized smoothing where an input is smoothed via some probability distribution. We propose a novel approach to randomized smoothing over multiplicative parameters. Using this method we construct certifiably robust classifiers with respect to a gamma correction perturbation and compare the result with classifiers obtained via other smoothing distributions (Gaussian, Laplace, uniform). The experiments show that asymmetrical Rayleigh distribution allows to obtain better certificates for some values of perturbation parameters. To the best of our knowledge it is the first work concerning certified robustness against the multiplicative gamma correction transformation and the first to study effects of asymmetrical distributions in randomized smoothing.
Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes
Authors: Ronca Alessandro , Paludo Licks Gabriel , De Giacomo Giuseppe
Published: July 2022

Our work aims at developing reinforcement learning algorithms that do not rely on the Markov assumption. We consider the class of Non-Markov Decision Processes where histories can be abstracted into a finite set of states while preserving the dynamics. We call it a Markov abstraction since it induces a Markov Decision Process over a set of states that encode the non-Markov dynamics. This phenomenon underlies the recently introduced Regular Decision Processes (as well as POMDPs where only a finite number of belief states is reachable). In all such kinds of decision process, an agent that uses a Markov abstraction can rely on the Markov property to achieve optimal behaviour. We show that Markov abstractions can be learned during reinforcement learning. Our approach combines automata learning and classic reinforcement learning. For these two tasks, standard algorithms can be employed. We show that our approach has PAC guarantees when the employed algorithms have PAC guarantees, and we also provide an experimental evaluation.
Federated Multi-Task Attention for Cross-Individual Human Activity Recognition
Authors: Shen Qiang , Feng Haotian , Song Rui , Teso Stefano , Giunchiglia Fausto , Xu Hao
Published: July 2022

Federated Learning (FL) is an emerging privacy-aware machine learning technique that applies successfully to the collaborative learning of global models for Human Activity Recognition (HAR). As of now, the applications of FL for HAR assume that the data associated with diverse individuals follow the same distribution. However, this assumption is impractical in real-world scenarios where the same activity is frequently performed differently by different individuals. To tackle this issue, we propose FedMAT, a Federated Multi-task ATtention framework for HAR, which extracts and fuses shared as well as individual-specific multi-modal sensor data features. Specifically, we treat the HAR problem associated with each individual as a different task and train a federated multi-task model, composed of a shared feature representation network in a central server plus multiple individual-specific networks with attention modules stored in decentralized nodes. In this architecture, the attention module operates as a mask that allows to learn individual-specific features from the global model, whilst simultaneously allowing for features to be shared among different individuals. We conduct extensive experiments based on publicly available HAR datasets, which are collected in both controlled environments and real-world scenarios. Numeric results verify that our proposed FedMAT significantly outperforms baselines not only in generalizing to existing individuals but also in adapting to new individuals.
RecipeRec: A Heterogeneous Graph Learning Model for Recipe Recommendation
Authors: Tian Yijun , Zhang Chuxu , Guo Zhichun , Huang Chao , Metoyer Ronald , Chawla Nitesh V.
Published: July 2022

Recipe recommendation systems play an essential role in helping people decide what to eat. Existing recipe recommendation systems typically focused on content-based or collaborative filtering approaches, ignoring the higher-order collaborative signal such as relational structure information among users, recipes and food items. In this paper, we formalize the problem of recipe recommendation with graphs to incorporate the collaborative signal into recipe recommendation through graph modeling. In particular, we first present URI-Graph, a new and large-scale user-recipe-ingredient graph. We then propose RecipeRec, a novel heterogeneous graph learning model for recipe recommendation. The proposed model can capture recipe content and collaborative signal through a heterogeneous graph neural network with hierarchical attention and an ingredient set transformer. We also introduce a graph contrastive augmentation strategy to extract informative graph knowledge in a self-supervised manner. Finally, we design a joint objective function of recommendation and contrastive learning to optimize the model. Extensive experiments demonstrate that RecipeRec outperforms state-of-the-art methods for recipe recommendation. Dataset and codes are available at https://github.com/meettyj/RecipeRec.
Stochastic Coherence Over Attention Trajectory For Continuous Learning In Video Streams
Authors: Tiezzi Matteo , Marullo Simone , Faggi Lapo , Meloni Enrico , Betti Alessandro , Melacci Stefano
Published: July 2022

Devising intelligent agents able to live in an environment and learn by observing the surroundings is a longstanding goal of Artificial Intelligence. From a bare Machine Learning perspective, challenges arise when the agent is prevented from leveraging large fully-annotated dataset, but rather the interactions with supervisory signals are sparsely distributed over space and time.

This paper proposes a novel neural-network-based approach to progressively and autonomously develop pixel-wise representations in a video stream. The proposed method is based on a human-like attention mechanism that allows the agent to learn by observing what is moving in the attended locations. Spatio-temporal stochastic coherence along the attention trajectory, paired with a contrastive term, leads to an unsupervised learning criterion that naturally copes with the considered setting. Differently from most existing works, the learned representations are used in open-set class-incremental classification of each frame pixel, relying on few supervisions. Our experiments leverage 3D virtual environments and they show that the proposed agents can learn to distinguish objects just by observing the video stream. Inheriting features from state-of-the art models is not as powerful as one might expect.
Initializing Then Refining: A Simple Graph Attribute Imputation Network
Authors: Tu Wenxuan , Zhou Sihang , Liu Xinwang , Liu Yue , Cai Zhiping , Zhu En , Zhang Changwang , Cheng Jieren
Published: July 2022

Representation learning on the attribute-missing graphs, whose connection information is complete while the attribute information of some nodes is missing, is an important yet challenging task. To impute the missing attributes, existing methods isolate the learning processes of attribute and structure information embeddings, and force both resultant representations to align with a common in-discriminative normal distribution, leading to inaccurate imputation. To tackle these issues, we propose a novel graph-oriented imputation framework called initializing then refining (ITR), where we first employ the structure information for initial imputation, and then leverage observed attribute and structure information to adaptively refine the imputed latent variables. Specifically, we first adopt the structure embeddings of attribute-missing samples as the embedding initialization, and then refine these initial values by aggregating the reliable and informative embeddings of attribute-observed samples according to the affinity structure. Specially, in our refining process, the affinity structure is adaptively updated through iterations by calculating the sample-wise correlations upon the recomposed embeddings. Extensive experiments on four benchmark datasets verify the superiority of ITR against state-of-the-art methods.
Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback
Authors: Wan Zongqi , Sun Xiaoming , Zhang Jialin
Published: July 2022

We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into d components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest d rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder nonoblivious setting. We show nonoblivious setting incurs Omega(T) pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys o(T) policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for K armed bandit and bandit convex optimization, our policy regret bound is in the order of T to the two third. We also prove a matching lower bound for K armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is nonoblivious. It answers the open problem proposed in [Wang, Wang, Huang 2021], showing that nonoblivious delay is enough to incur the regret in the order of T to the two third.
Stabilizing and Enhancing Link Prediction through Deepened Graph Auto-Encoders
Authors: wu Xinxing , Cheng Qiang
Published: July 2022

Graph neural networks have been widely used for a variety of learning tasks. Link prediction is a relatively under-studied graph learning task, with current state-of-the-art models based on one- or two-layer shallow graph auto-encoder (GAE) architectures. In this paper, we overcome the limitation of current methods for link prediction of non-Euclidean network data, which can only use shallow GAEs and variational GAEs. Our proposed methods innovatively incorporate standard auto-encoders (AEs) into the architectures of GAEs to capitalize on the intimate coupling of node and edge information in complex network data. Empirically, extensive experiments on various datasets demonstrate the competitive performance of our proposed approach. Theoretically, we prove that our deep extensions can inclusively express multiple polynomial filters with different orders. The codes of this paper are available at https://github.com/xinxingwu-uk/DGAE.