OpenRaiser/Intern-Atlas huggingface dataset:
Rate-Splitting Multiple Access with Finite Blocklength for Short-Packet and Low-Latency Downlink Communications
Venue: arXiv cs.IT 2022
Year: 2022

Rate-Splitting Multiple Access (RSMA) is an emerging flexible and powerful multiple access for downlink multiantenna networks. In this paper, we introduce the concept of RSMA into short-packet downlink communications. We design optimal linear precoders that maximize the sum rate with Finite Blocklength (FBL) constraints. The relations between the sum rate and blocklength of RSMA are investigated for a wide range of network loads and user deployments. Numerical results demonstrate that RSMA can achieve the same transmission rate as Non-Orthogonal Multiple Access (NOMA) and Space Division Multiple Access (SDMA) with shorter blocklengths (and therefore lower latency), especially in overloaded multi-antenna networks. Hence, we conclude that RSMA is a promising multiple access for low-latency communications.
A Graphical Calculus for Lagrangian Relations
Venue: arXiv cs.LO 2022
Year: 2022

Symplectic vector spaces are the phase spaces of linear mechanical systems. The symplectic form describes, for example, the relation between position and momentum as well as current and voltage. The category of linear Lagrangian relations between symplectic vector spaces is a symmetric monoidal subcategory of relations which gives a semantics for the evolution -- and more generally linear constraints on the evolution -- of various physical systems. We give a new presentation of the category of Lagrangian relations over an arbitrary field as a `doubled' category of linear relations. More precisely, we show that it arises as a variation of Selinger's CPM construction applied to linear relations, where the covariant orthogonal complement functor plays the role of conjugation. Furthermore, for linear relations over prime fields, this corresponds exactly to the CPM construction for a suitable choice of dagger. We can furthermore extend this construction by a single affine shift operator to obtain a category of affine Lagrangian relations. Using this new presentation, we prove the equivalence of the prop of affine Lagrangian relations with the prop of qudit stabilizer theory in odd prime dimensions. We hence obtain a unified graphical language for several disparate process theories, including electrical circuits, Spekkens' toy theory, and odd-prime-dimensional stabilizer quantum circuits.
3D-CNN for Facial Micro- and Macro-expression Spotting on Long Video Sequences using Temporal Oriented Reference Frame
Venue: arXiv cs.CV 2022
Year: 2022

Facial expression spotting is the preliminary step for micro- and macro-expression analysis. The task of reliably spotting such expressions in video sequences is currently unsolved. The current best systems depend upon optical flow methods to extract regional motion features, before categorisation of that motion into a specific class of facial movement. Optical flow is susceptible to drift error, which introduces a serious problem for motions with long-term dependencies, such as high frame-rate macro-expression. We propose a purely deep learning solution which, rather than tracking frame differential motion, compares via a convolutional model, each frame with two temporally local reference frames. Reference frames are sampled according to calculated micro- and macro-expression duration. As baseline for MEGC2021 using leave-one-subject-out evaluation method, we show that our solution achieves F1-score of 0.105 in a high frame-rate (200 fps) SAMM long videos dataset (SAMM-LV) and is competitive in a low frame-rate (30 fps) (CAS(ME)2) dataset. On unseen MEGC2022 challenge dataset, the baseline results are 0.1176 on SAMM Challenge dataset, 0.1739 on CAS(ME)3 and overall performance of 0.1531 on both dataset.
On Minimizing the Number of Running Buffers for Tabletop Rearrangement
Venue: arXiv cs.RO 2022
Year: 2022

For tabletop rearrangement problems with overhand grasps, storage space outside the tabletop workspace, or buffers, can temporarily hold objects which greatly facilitates the resolution of a given rearrangement task. This brings forth the natural question of how many running buffers are required so that certain classes of tabletop rearrangement problems are feasible. In this work, we examine the problem for both the labeled (where each object has a specific goal pose) and the unlabeled (where goal poses of objects are interchangeable) settings. On the structural side, we observe that finding the minimum number of running buffers (MRB) can be carried out on a dependency graph abstracted from a problem instance, and show that computing MRB on dependency graphs is NP-hard. We then prove that under both labeled and unlabeled settings, even for uniform cylindrical objects, the number of required running buffers may grow unbounded as the number of objects to be rearranged increases; we further show that the bound for the unlabeled case is tight. On the algorithmic side, we develop highly effective algorithms for finding MRB for both labeled and unlabeled tabletop rearrangement problems, scalable to over a hundred objects under very high object density. Employing these algorithms, empirical evaluations show that random labeled and unlabeled instances, which more closely mimics real-world setups, have much smaller MRBs.
Equilibria in Schelling Games: Computational Hardness and Robustness
Venue: arXiv cs.GT 2022
Year: 2022

In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI '20] and Elkind et al. [IJCAI '19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.
Efficient PAC Reinforcement Learning in Regular Decision Processes
Venue: arXiv cs.AI 2022
Year: 2022

Recently regular decision processes have been proposed as a well-behaved form of non-Markov decision process. Regular decision processes are characterised by a transition function and a reward function that depend on the whole history, though regularly (as in regular languages). In practice both the transition and the reward functions can be seen as finite transducers. We study reinforcement learning in regular decision processes. Our main contribution is to show that a near-optimal policy can be PAC-learned in polynomial time in a set of parameters that describe the underlying decision process. We argue that the identified set of parameters is minimal and it reasonably captures the difficulty of a regular decision process.
VICEROY: GDPR-/CCPA-compliant Enforcement of Verifiable Accountless Consumer Requests
Venue: arXiv cs.CR 2022
Year: 2022

Recent data protection regulations (such as GDPR and CCPA) grant consumers various rights, including the right to access, modify or delete any personal information collected about them (and retained) by a service provider. To exercise these rights, one must submit a verifiable consumer request proving that the collected data indeed pertains to them. This action is straightforward for consumers with active accounts with a service provider at the time of data collection, since they can use standard (e.g., password-based) means of authentication to validate their requests. However, a major conundrum arises from the need to support consumers without accounts to exercise their rights. To this end, some service providers began requiring such accountless consumers to reveal and prove their identities (e.g., using government-issued documents, utility bills, or credit card numbers) as part of issuing a verifiable consumer request. While understandable as a short-term cure, this approach is cumbersome and expensive for service providers as well as privacy-invasive for consumers. Consequently, there is a strong need to provide better means of authenticating requests from accountless consumers. To achieve this, we propose VICEROY, a privacy-preserving and scalable framework for producing proofs of data ownership, which form a basis for verifiable consumer requests. Building upon existing web techniques and features, VICEROY allows accountless consumers to interact with service providers, and later prove that they are the same person in a privacy-preserving manner, while requiring minimal changes for both parties. We design and implement VICEROY with emphasis on security/privacy, deployability and usability. We also thoroughly assess its practicality via extensive experiments.
ExSinGAN: Learning an Explainable Generative Model from a Single Image
Venue: arXiv cs.CV 2022
Year: 2022

Generating images from a single sample, as a newly developing branch of image synthesis, has attracted extensive attention. In this paper, we formulate this problem as sampling from the conditional distribution of a single image, and propose a hierarchical framework that simplifies the learning of the intricate conditional distributions through the successive learning of the distributions about structure, semantics and texture, making the process of learning and generation comprehensible. On this basis, we design ExSinGAN composed of three cascaded GANs for learning an explainable generative model from a given image, where the cascaded GANs model the distributions about structure, semantics and texture successively. ExSinGAN is learned not only from the internal patches of the given image as the previous works did, but also from the external prior obtained by the GAN inversion technique. Benefiting from the appropriate combination of internal and external information, ExSinGAN has a more powerful capability of generation and competitive generalization ability for the image manipulation tasks compared with prior works.
SLGPT: Using Transfer Learning to Directly Generate Simulink Model Files and Find Bugs in the Simulink Toolchain
Venue: arXiv cs.SE 2022
Year: 2022

Finding bugs in a commercial cyber-physical system (CPS) development tool such as Simulink is hard as its codebase contains millions of lines of code and complete formal language specifications are not available. While deep learning techniques promise to learn such language specifications from sample models, deep learning needs a large number of training data to work well. SLGPT addresses this problem by using transfer learning to leverage the powerful Generative Pre-trained Transformer 2 (GPT-2) model, which has been pre-trained on a large set of training data. SLGPT adapts GPT-2 to Simulink with both randomly generated models and models mined from open-source repositories. SLGPT produced Simulink models that are both more similar to open-source models than its closest competitor, DeepFuzzSL, and found a super-set of the Simulink development toolchain bugs found by DeepFuzzSL.
In Congestion Games, Taxes Achieve Optimal Approximation
Venue: arXiv cs.GT 2022
Year: 2022

In this work, we consider the problem of minimising the social cost in atomic congestion games. For this problem, we provide tight computational lower bounds along with taxation mechanisms yielding polynomial time algorithms with optimal approximation. Perhaps surprisingly, our results show that indirect interventions, in the form of efficiently computed taxation mechanisms, yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the agents' actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: Judiciously chosen taxes achieve optimal approximation. Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP-hard to approximate within a given factor depending solely on the admissible resource costs. Second, we design a tractable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is worst-case optimal. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation.
APPL: Adaptive Planner Parameter Learning
Venue: arXiv cs.RO 2022
Year: 2022

While current autonomous navigation systems allow robots to successfully drive themselves from one point to another in specific environments, they typically require extensive manual parameter re-tuning by human robotics experts in order to function in new environments. Furthermore, even for just one complex environment, a single set of fine-tuned parameters may not work well in different regions of that environment. These problems prohibit reliable mobile robot deployment by non-expert users. As a remedy, we propose Adaptive Planner Parameter Learning (APPL), a machine learning framework that can leverage non-expert human interaction via several modalities -- including teleoperated demonstrations, corrective interventions, and evaluative feedback -- and also unsupervised reinforcement learning to learn a parameter policy that can dynamically adjust the parameters of classical navigation systems in response to changes in the environment. APPL inherits safety and explainability from classical navigation systems while also enjoying the benefits of machine learning, i.e., the ability to adapt and improve from experience. We present a suite of individual APPL methods and also a unifying cycle-of-learning scheme that combines all the proposed methods in a framework that can improve navigation performance through continual, iterative human interaction and simulation training.
Efficient Stochastic Optimal Control through Approximate Bayesian Input Inference
Venue: arXiv cs.LG 2022
Year: 2022

Optimal control under uncertainty is a prevailing challenge for many reasons. One of the critical difficulties lies in producing tractable solutions for the underlying stochastic optimization problem. We show how advanced approximate inference techniques can be used to handle the statistical approximations principled and practically by framing the control problem as a problem of input estimation. Analyzing the Gaussian setting, we present an inference-based solver that is effective in stochastic and deterministic settings and was found to be superior to popular baselines on nonlinear simulated tasks. We draw connections that relate this inference formulation to previous approaches for stochastic optimal control and outline several advantages that this inference view brings due to its statistical nature.
Conscious AI
Venue: arXiv cs.AI 2022
Year: 2022

Recent advances in artificial intelligence (AI) have achieved human-scale speed and accuracy for classification tasks. In turn, these capabilities have made AI a viable replacement for many human activities that at their core involve classification, such as basic mechanical and analytical tasks in low-level service jobs. Current systems do not need to be conscious to recognize patterns and classify them. However, for AI to progress to more complicated tasks requiring intuition and empathy, it must develop capabilities such as metathinking, creativity, and empathy akin to human self-awareness or consciousness. We contend that such a paradigm shift is possible only through a fundamental shift in the state of artificial intelligence toward consciousness, a shift similar to what took place for humans through the process of natural selection and evolution. As such, this paper aims to theoretically explore the requirements for the emergence of consciousness in AI. It also provides a principled understanding of how conscious AI can be detected and how it might be manifested in contrast to the dominant paradigm that seeks to ultimately create machines that are linguistically indistinguishable from humans.
TRIM: A Design Space Exploration Model for Deep Neural Networks Inference and Training Accelerators
Venue: arXiv cs.DC 2022
Year: 2022

There is increasing demand for specialized hardware for training deep neural networks, both in edge/IoT environments and in high-performance computing systems. The design space of such hardware is very large due to the wide range of processing architectures, deep neural network configurations, and dataflow options. This makes developing deep neural network processors quite complex, especially for training. We present TRIM, an infrastructure to help hardware architects explore the design space of deep neural network accelerators for both inference and training in the early design stages. The model evaluates at the whole network level, considering both inter-layer and intra-layer activities. Given applications, essential hardware specifications, and a design goal, TRIM can quickly explore different hardware design options, select the optimal dataflow and guide new hardware architecture design. We validated TRIM with FPGA-based implementation of deep neural network accelerators and ASIC-based architectures. We also show how to use TRIM to explore the design space through several case studies. TRIM is a powerful tool to help architects evaluate different hardware choices to develop efficient inference and training architecture design.
Simulating 3-symbol Turing machines with SIMD||DNA
Venue: arXiv cs.ET 2022
Year: 2022

SIMD||DNA is a model of DNA strand displacement allowing parallel in-memory computation on DNA storage. We show how to simulate an arbitrary 3-symbol space-bounded Turing machine with a SIMD||DNA program, giving a more direct and efficient route to general-purpose information manipulation on DNA storage than the Rule 110 simulation of [Wang, Chalk, Soloveichik, DNA 2019]. We also develop software that can simulate SIMD||DNA programs and produce SVG figures.
Graph Neural Networks for Decentralized Multi-Robot Submodular Action Selection
Venue: arXiv cs.RO 2022
Year: 2022

The problem of decentralized multi-robot target tracking asks for jointly selecting actions, e.g., motion primitives, for the robots to maximize target tracking performance with local communications. One major challenge for practical implementations is to make target tracking approaches scalable for large-scale problem instances. In this work, we propose a general-purpose learning architecture toward collaborative target tracking at scale, with decentralized communications. Particularly, our learning architecture leverages a graph neural network (GNN) to capture local interactions of the robots and learns decentralized decision-making for the robots. We train the learning model by imitating an expert solution and implement the resulting model for decentralized action selection involving local observations and communications only. We demonstrate the performance of our GNN-based learning approach in a scenario of active target tracking with large networks of robots. The simulation results show our approach nearly matches the tracking performance of the expert algorithm, and yet runs several orders faster with up to 100 robots. Moreover, it slightly outperforms a decentralized greedy algorithm but runs faster (especially with more than 20 robots). The results also exhibit our approach's generalization capability in previously unseen scenarios, e.g., larger environments and larger networks of robots.
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Venue: arXiv cs.LG 2022
Year: 2022

Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps and complementing results from the literature, we present several results on the parameterized complexity of training two-layer ReLU networks with respect to various loss functions. After a brief discussion of other parameters, we focus on analyzing the influence of the dimension $d$ of the training data on the computational complexity. We provide running time lower bounds in terms of W[1]-hardness for parameter $d$ and prove that known brute-force strategies are essentially optimal (assuming the Exponential Time Hypothesis). In comparison with previous work, our results hold for a broad(er) range of loss functions, including $\ell^p$-loss for all $p\in[0,\infty]$. In particular, we extend a known polynomial-time algorithm for constant $d$ and convex loss functions to a more general class of loss functions, matching our running time lower bounds also in these cases.
Latent Gaussian Model Boosting
Venue: arXiv cs.LG 2022
Year: 2022

Latent Gaussian models and boosting are widely used techniques in statistics and machine learning. Tree-boosting shows excellent prediction accuracy on many data sets, but potential drawbacks are that it assumes conditional independence of samples, produces discontinuous predictions for, e.g., spatial data, and it can have difficulty with high-cardinality categorical variables. Latent Gaussian models, such as Gaussian process and grouped random effects models, are flexible prior models which explicitly model dependence among samples and which allow for efficient learning of predictor functions and for making probabilistic predictions. However, existing latent Gaussian models usually assume either a zero or a linear prior mean function which can be an unrealistic assumption. This article introduces a novel approach that combines boosting and latent Gaussian models to remedy the above-mentioned drawbacks and to leverage the advantages of both techniques. We obtain increased prediction accuracy compared to existing approaches in both simulated and real-world data experiments.
Objective-aware Traffic Simulation via Inverse Reinforcement Learning
Venue: arXiv cs.AI 2022
Year: 2022

Traffic simulators act as an essential component in the operating and planning of transportation systems. Conventional traffic simulators usually employ a calibrated physical car-following model to describe vehicles' behaviors and their interactions with traffic environment. However, there is no universal physical model that can accurately predict the pattern of vehicle's behaviors in different situations. A fixed physical model tends to be less effective in a complicated environment given the non-stationary nature of traffic dynamics. In this paper, we formulate traffic simulation as an inverse reinforcement learning problem, and propose a parameter sharing adversarial inverse reinforcement learning model for dynamics-robust simulation learning. Our proposed model is able to imitate a vehicle's trajectories in the real world while simultaneously recovering the reward function that reveals the vehicle's true objective which is invariant to different dynamics. Extensive experiments on synthetic and real-world datasets show the superior performance of our approach compared to state-of-the-art methods and its robustness to variant dynamics of traffic.