GenAI4ELab/papercli-papers huggingface dataset:
Learning to Select Prototypical Parts for Interpretable Sequential Data Modeling
Authors: Yifei Zhang; Neng Gao; Cunqing Ma
Venue: AAAI 2023 (main)

Abstract: Prototype-based interpretability methods provide intuitive explanations of model prediction by comparing samples to a reference set of memorized exemplars or typical representatives in terms of similarity. In the field of sequential data modeling, similarity calculations of prototypes are usually based on encoded representation vectors. However, due to highly recursive functions, there is usually a non-negligible disparity between the prototype-based explanations and the original input. In this work, we propose a Self-Explaining Selective Model (SESM) that uses a linear combination of prototypical concepts to explain its own predictions. The model employs the idea of case-based reasoning by selecting sub-sequences of the input that mostly activate different concepts as prototypical parts, which users can compare to sub-sequences selected from different example inputs to understand model decisions. For better interpretability, we design multiple constraints including diversity, stability, and locality as training objectives. Extensive experiments in different domains demonstrate that our method exhibits promising interpretability and competitive accuracy.
RETRACTED: McOmet: Multimodal Fusion Transformer for Physical Audiovisual Commonsense Reasoning
Authors: Daoming Zong; Shiliang Sun
Venue: AAAI 2023 (main)

Abstract: Referred to by:Retraction Note to: McOmet: Multimodal Fusion Transformer for Physical Audiovisual Commonsense Reasoning.This article, which was published in Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2023), has been retracted by agreement between the authors and the journal.
Approximating Full Conformal Prediction at Scale via Influence Functions
Authors: Javier Abad Martinez; Umang Bhatt; Adrian Weller; Giovanni Cherubin
Venue: AAAI 2023 (main)

Abstract: Conformal prediction (CP) is a wrapper around traditional machine learning models, giving coverage guarantees under the sole assumption of exchangeability; in classification problems, a CP guarantees that the error rate is at most a chosen significance level, irrespective of whether the underlying model is misspecified. However, the prohibitive computational costs of full CP led researchers to design scalable alternatives, which alas do not attain the same guarantees or statistical power of full CP. In this paper, we use influence functions to efficiently approximate full CP. We prove that our method is a consistent approximation of full CP, and empirically show that the approximation error becomes smaller as the training set increases; e.g., for 1,000 training points the two methods output p-values that are <0.001 apart: a negligible error for any practical application. Our methods enable scaling full CP to large real-world datasets. We compare our full CP approximation (ACP) to mainstream CP alternatives, and observe that our method is computationally competitive whilst enjoying the statistical predictive power of full CP.
Efficient Distributed Inference of Deep Neural Networks via Restructuring and Pruning
Authors: Afshin Abdi; Saeed Rashidi; Faramarz Fekri; Tushar Krishna
Venue: AAAI 2023 (main)

Abstract: In this paper, we consider the parallel implementation of an already-trained deep model on multiple processing nodes (a.k.a. workers). Specifically, we investigate as to how a deep model should be divided into several parallel sub-models, each of which is executed efficiently by a worker. Since latency due to synchronization and data transfer among workers negatively impacts the performance of the parallel implementation, it is desirable to have minimum interdependency among parallel sub-models. To achieve this goal, we propose to rearrange the neurons in the neural network, partition them (without changing the general topology of the neural network), and modify the weights such that the interdependency among sub-models is minimized under the computations and communications constraints of the workers while minimizing its impact on the performance of the model. We propose RePurpose, a layer-wise model restructuring and pruning technique that guarantees the performance of the overall parallelized model. To efficiently apply RePurpose, we propose an approach based on L0 optimization and the Munkres assignment algorithm. We show that, compared to the existing methods, RePurpose significantly improves the efficiency of the distributed inference via parallel implementation, both in terms of communication and computational complexity.
Symbolic Metamodels for Interpreting Black-Boxes Using Primitive Functions
Authors: Mahed Abroshan; Saumitra Mishra; Mohammad Mahdi Khalili
Venue: AAAI 2023 (main)

Abstract: One approach for interpreting black-box machine learning models is to find a global approximation of the model using simple interpretable functions, which is called a metamodel (a model of the model). Approximating the black-box with
a metamodel can be used to 1) estimate instance-wise feature importance; 2) understand the functional form of the model; 3) analyze feature interactions. In this work, we propose a new method for finding interpretable metamodels. Our approach utilizes Kolmogorov superposition theorem, which expresses multivariate functions as a composition of univariate functions (our primitive parameterized
functions). This composition can be represented in the form of a tree. Inspired by symbolic regression, we use a modified form of genetic programming to search over different tree configurations. Gradient descent (GD) is used to optimize the parameters of a given configuration. Our method is a novel memetic algorithm that uses GD  not only for training numerical constants but also for the training
of building blocks. Using several experiments, we show that our method outperforms recent metamodeling approaches suggested for interpreting black-boxes.
Utilizing Prior Solutions for Reward Shaping and Composition in Entropy-Regularized Reinforcement Learning
Authors: Jacob Adamczyk; Argenis Arriojas; Stas Tiomkin; Rahul V. Kulkarni
Venue: AAAI 2023 (main)

Abstract: In reinforcement learning (RL), the ability to utilize prior knowledge from previously solved tasks can allow agents to quickly solve new problems. In some cases, these new problems may be approximately solved by composing the solutions of previously solved primitive tasks (task composition). Otherwise, prior knowledge can be used to adjust the reward function for a new problem, in a way that leaves the optimal policy unchanged but enables quicker learning (reward shaping). In this work, we develop a general framework for reward shaping and task composition in entropy-regularized RL. To do so, we derive an exact relation connecting the optimal soft value functions for two entropy-regularized RL problems with different reward functions and dynamics. We show how the derived relation leads to a general result for reward shaping in entropy-regularized RL. We then generalize this approach to derive an exact relation connecting optimal value functions for the composition of multiple tasks in entropy-regularized RL. We validate these theoretical contributions with experiments showing that reward shaping and task composition lead to faster learning in various settings.
Clustering What Matters: Optimal Approximation for Clustering with Outliers
Authors: Akanksha Agrawal; Tanmay Inamdar; Saket Saurabh; Jie Xue
Venue: AAAI 2023 (main)

Abstract: Clustering with outliers is one of the most fundamental problems in Computer Science.  Given a set X of n points and two numbers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) * poly(n) for some function f), that almost matches the approximation ratio for its outlier-free counterpart.

As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.
Contrastive Classification and Representation Learning with Probabilistic Interpretation
Authors: Rahaf Aljundi; Yash Patel; Milan Sulc; Nikolay Chumerin; Daniel Olmeda Reino
Venue: AAAI 2023 (main)

Abstract: Cross entropy loss has served as the main objective function for classification-based tasks. Widely deployed for learning neural network classifiers, it shows both effectiveness and a probabilistic interpretation.  Recently, after the success of self supervised contrastive representation learning methods, supervised contrastive methods have been proposed to learn representations and have shown superior and more robust performance, compared to solely training with cross entropy loss. However, cross entropy loss is still needed to train the final classification layer. In this work, we investigate the possibility of learning both the representation and the classifier using one objective function that combines the robustness of contrastive learning and the probabilistic interpretation of  cross entropy loss. First,  we revisit a previously proposed contrastive-based objective function that approximates cross entropy loss and present a simple extension to learn  the classifier jointly. Second, we propose a new version of the supervised contrastive training that learns jointly the parameters of the classifier and the backbone of the network. We empirically show that these proposed objective functions demonstrate state-of-the-art performance and show a significant improvement over the standard cross entropy loss with more training stability and robustness in various challenging settings.
Simulating Network Paths with Recurrent Buffering Units
Authors: Divyam Anshumaan; Sriram Balasubramanian; Shubham Tiwari; Nagarajan Natarajan; Sundararajan Sellamanickam; Venkat N. Padmanabhan
Venue: AAAI 2023 (main)

Abstract: Simulating physical network paths (e.g., Internet) is a cornerstone research problem in the emerging sub-field of AI-for-networking. We seek a model that generates end-to-end packet delay values in response to the time-varying load offered by a sender, which is typically a function of the previously output delays. The problem setting is unique, and renders the state-of-the-art text and time-series generative models inapplicable or ineffective. We formulate an ML problem at the intersection of dynamical systems, sequential decision making, and time-series modeling. We propose a novel grey-box approach to network simulation that embeds the semantics of physical network path in a new RNN-style model called Recurrent Buffering Unit, providing the interpretability of standard network simulator tools, the power of neural models, the efficiency of SGD-based techniques for learning, and yielding promising results on synthetic and real-world network traces.
Fully Dynamic Online Selection through Online Contention Resolution Schemes
Authors: Vashist Avadhanula; Andrea Celli; Riccardo Colini-Baldeschi; Stefano Leonardi; Matteo Russo
Venue: AAAI 2023 (main)

Abstract: We study fully dynamic online selection problems in an adversarial/stochastic setting that includes Bayesian online selection, prophet inequalities, posted price mechanisms, and stochastic probing problems subject to combinatorial constraints.   In the classical ``incremental'' version of the problem, selected elements remain active until the end of the input sequence. On the other hand, in the fully dynamic version of the problem, elements stay active for a limited time interval, and then leave. This models, for example, the online matching of tasks to workers with task/worker-dependent working times, and sequential posted pricing of perishable goods. A successful approach to online selection problems in the adversarial setting is given by the notion of  Online Contention Resolution Scheme (OCRS), that uses  a priori information to formulate a linear relaxation of the underlying optimization problem, whose optimal fractional solution is rounded online for any adversarial order of the input sequence. Our main contribution is providing a general method for constructing an OCRS for fully dynamic online selection problems. Then, we show how to employ such OCRS to construct no-regret algorithms in a partial information model with semi-bandit feedback and adversarial inputs.
Tree Learning: Optimal Sample Complexity and Algorithms
Authors: Dmitrii Avdiukhin; Grigory Yaroslavtsev; Danny Vainstein; Orr Fischer; Sauman Das; Faraz Mirza
Venue: AAAI 2023 (main)

Abstract: We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.
Meta-Learning for Simple Regret Minimization
Authors: Javad Azizi; Branislav Kveton; Mohammad Ghavamzadeh; Sumeet Katariya
Venue: AAAI 2023 (main)

Abstract: We develop a meta-learning framework for simple regret minimization in bandits. In this framework, a learning agent interacts with a sequence of bandit tasks, which are sampled i.i.d. from an unknown prior distribution, and learns its meta-parameters to perform better on future tasks. We propose the first Bayesian and frequentist meta-learning algorithms for this setting. The Bayesian algorithm has access to a prior distribution over the meta-parameters and its meta simple regret over m bandit tasks with horizon n is mere O(m / √n). On the other hand, the meta simple regret of the frequentist algorithm is O(n√m + m/ √n). While its regret is worse, the frequentist algorithm is more general because it does not need a prior distribution over the meta-parameters. It can also be analyzed in more settings. We instantiate our algorithms for several classes of bandit problems. Our algorithms are general and we complement our theory by evaluating them empirically in several environments.
Generalizing Downsampling from Regular Data to Graphs
Authors: Davide Bacciu; Alessio Conte; Francesco Landolfi
Venue: AAAI 2023 (main)

Abstract: Downsampling produces coarsened, multi-resolution representations of data and it is used, for example, to produce lossy compression and visualization of large images, reduce computational costs, and boost deep neural representation learning. 
Unfortunately, due to their lack of a regular structure, there is still no consensus on how downsampling should apply to graphs and linked data. Indeed reductions in graph data are still needed for the goals described above, but reduction mechanisms do not have the same focus on preserving topological structures and properties, while allowing for resolution-tuning, as is the case in regular data downsampling.
In this paper, we take a step in this direction, introducing a unifying interpretation of downsampling in regular and graph data. In particular, we define a graph coarsening mechanism which is a graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. We leverage these concepts to define a graph pooling mechanism that we empirically assess in graph classification tasks, providing a greedy algorithm that allows efficient parallel implementation on GPUs, and showing that it compares favorably against pooling methods in literature.
PiCor: Multi-Task Deep Reinforcement Learning with Policy Correction
Authors: Fengshuo Bai; Hongming Zhang; Tianyang Tao; Zhiheng Wu; Yanna Wang; Bo Xu
Venue: AAAI 2023 (main)

Abstract: Multi-task deep reinforcement learning (DRL) ambitiously aims to train a general agent that masters multiple tasks simultaneously. However, varying learning speeds of different tasks compounding with negative gradients interference makes policy learning inefficient. In this work, we propose PiCor, an efficient multi-task DRL framework that splits learning into policy optimization and policy correction phases. The policy optimization phase improves the policy by any DRL algothrim on the sampled single task without considering other tasks. The policy correction phase first constructs an adaptive adjusted performance constraint set. Then the intermediate policy learned by the first phase is constrained to the set, which controls the negative interference and balances the learning speeds across tasks. Empirically, we demonstrate that PiCor outperforms previous methods and significantly improves sample efficiency on simulated robotic manipulation and continuous control tasks. We additionally show that adaptive weight adjusting can further improve data efficiency and performance.
Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm
Authors: Qinbo Bai; Amrit Singh Bedi; Vaneet Aggarwal
Venue: AAAI 2023 (main)

Abstract: We consider the problem of constrained Markov decision process (CMDP) in continuous state actions spaces where the goal is to maximize the expected cumulative reward subject to some constraints. We propose a novel Conservative Natural Policy Gradient Primal Dual Algorithm (CNPGPD) to achieve zero constraint violation while achieving state of the art convergence results for the objective value function. For general policy parametrization, we prove convergence of value function to global optimal upto an approximation error due to restricted policy class. We improve the sample complexity of existing constrained NPGPD algorithm. To the best of our knowledge, this is the first work to establish zero constraint violation with Natural policy gradient style algorithms for infinite horizon discounted CMDPs. We demonstrate the merits of proposed algorithm via experimental evaluations.
Optimal Sparse Recovery with Decision Stumps
Authors: Kiarash Banihashem; Mohammad Hajiaghayi; Max Springer
Venue: AAAI 2023 (main)

Abstract: Decision trees are widely used for their low computational cost, good
  predictive performance, and ability to assess the importance of features.
  Though often used in practice for feature selection, the theoretical
  guarantees of these methods are not well understood. We here obtain a tight
  finite sample bound for the feature selection problem in linear regression
  using single-depth decision trees. We examine the statistical properties of
  these "decision stumps" for the recovery of the s active features from p
  total features, where s << p. Our analysis provides tight sample performance guarantees on
  high-dimensional sparse systems which align with the finite sample bound of
  O(s log p) as obtained by Lasso, improving upon previous bounds for both
  the median and optimal splitting criteria. Our results extend to the
  non-linear regime as well as arbitrary sub-Gaussian distributions,
  demonstrating that tree based methods attain strong feature selection
  properties under a wide variety of settings and further shedding light on the
  success of these methods in practice. As a byproduct of our analysis, we show
  that we can provably guarantee recovery even when the number of active
  features s is unknown.
  We further validate our theoretical results and proof methodology
  using computational experiments.
Towards Efficient and Domain-Agnostic Evasion Attack with High-Dimensional Categorical Inputs
Authors: Hongyan Bao; Yufei Han; Yujun Zhou; Xin Gao; Xiangliang Zhang
Venue: AAAI 2023 (main)

Abstract: Our work targets at searching feasible adversarial perturbation to attack a classifier with  high-dimensional categorical inputs in a domain-agnostic setting.
This is intrinsically a NP-hard knapsack problem where the exploration space becomes explosively larger as the feature dimension increases. Without the help of domain knowledge, solving this problem via heuristic method, such as Branch-and-Bound, suffers from exponential complexity, yet can bring arbitrarily bad attack results. We address the challenge via the lens of multi-armed bandit based combinatorial search. Our proposed method, namely FEAT, treats modifying each categorical feature as pulling an arm in multi-armed bandit programming. Our objective is to achieve highly efficient and effective attack using an Orthogonal Matching Pursuit (OMP)-enhanced Upper Confidence Bound (UCB) exploration strategy. Our theoretical analysis bounding the regret gap of FEAT guarantees its practical attack performance. In empirical analysis, we compare FEAT with other state-of-the-art domain-agnostic attack methods over various real-world categorical data sets of different applications. Substantial experimental observations confirm the expected efficiency and attack effectiveness of FEAT applied in different application scenarios. Our work further hints the applicability of FEAT for assessing the adversarial vulnerability of classification systems with high-dimensional categorical inputs.
Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
Authors: Siddharth Barman; Arindam Khan; Arnab Maiti; Ayush Sawarni
Venue: AAAI 2023 (main)

Abstract: We extend the notion of regret with a welfarist perspective. Focussing on the classic multi-armed bandit (MAB) framework, the current work quantifies the performance of bandit algorithms by applying a fundamental welfare function, namely the Nash social welfare (NSW) function. This corresponds to equating algorithm's performance to the geometric mean of its expected rewards and leads us to the study of   Nash regret, defined as the difference between the - a priori unknown - optimal mean (among the arms) and the algorithm's performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. 

This work develops an algorithm that, given the horizon of play T, achieves a Nash regret of O ( sqrt{(k log T)/T} ), here k denotes the number of arms in the MAB instance. Since, for any algorithm, the Nash regret is at least as much as its average regret (the AM-GM inequality), the known lower bound on average regret holds for Nash regret as well. Therefore, our Nash regret guarantee is essentially tight. In addition, we develop an anytime algorithm with a Nash regret guarantee of O( sqrt{(k log T)/T} log T ).