OpenRaiser/Intern-Atlas huggingface dataset:
QCSP monsters and the demise of the Chen Conjecture
Venue: arXiv cs.CC 2022
Year: 2022

We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language $Γ$, QCSP$(Γ)$, where $Γ$ is a finite language over $3$ elements which contains all constants. In particular, such problems are either in P, NP-complete, co-NP-complete or PSpace-complete. Our classification refutes the hitherto widely-believed Chen Conjecture. Additionally, we show that already on a 4-element domain there exists a constraint language $Γ$ such that QCSP$(Γ)$ is DP-complete (from Boolean Hierarchy), and on a 10-element domain there exists a constraint language giving the complexity class $Θ_{2}^{P}$. Meanwhile, we prove the Chen Conjecture for finite conservative languages $Γ$. If the polymorphism clone of $Γ$ has the polynomially generated powers (PGP) property then QCSP$(Γ)$ is in NP. Otherwise, the polymorphism clone of $Γ$ has the exponentially generated powers (EGP) property and QCSP$(Γ)$ is PSpace-complete.
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Venue: arXiv cs.DS 2022
Year: 2022

For a finite collection of graphs ${\cal F}$, the \textsc{${\cal F}$-TM-Deletion} problem has as input an $n$-vertex graph $G$ and an integer $k$ and asks whether there exists a set $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a topological minor. We prove that for every such ${\cal F}$, \textsc{${\cal F}$-TM-Deletion} is fixed parameter tractable on planar graphs. Our algorithm runs in a $2^{\mathcal{O}(k^2)}\cdot n^{2}$ time or, alternatively in $2^{\mathcal{O}(k)}\cdot n^{4}$ time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface.
Shapley Q-value: A Local Reward Approach to Solve Global Reward Games
Venue: arXiv cs.LG 2022
Year: 2022

Cooperative game is a critical research area in the multi-agent reinforcement learning (MARL). Global reward game is a subclass of cooperative games, where all agents aim to maximize the global reward. Credit assignment is an important problem studied in the global reward game. Most of previous works stood by the view of non-cooperative-game theoretical framework with the shared reward approach, i.e., each agent being assigned a shared global reward directly. This, however, may give each agent an inaccurate reward on its contribution to the group, which could cause inefficient learning. To deal with this problem, we i) introduce a cooperative-game theoretical framework called extended convex game (ECG) that is a superset of global reward game, and ii) propose a local reward approach called Shapley Q-value. Shapley Q-value is able to distribute the global reward, reflecting each agent's own contribution in contrast to the shared reward approach. Moreover, we derive an MARL algorithm called Shapley Q-value deep deterministic policy gradient (SQDDPG), using Shapley Q-value as the critic for each agent. We evaluate SQDDPG on Cooperative Navigation, Prey-and-Predator and Traffic Junction, compared with the state-of-the-art algorithms, e.g., MADDPG, COMA, Independent DDPG and Independent A2C. In the experiments, SQDDPG shows a significant improvement on the convergence rate. Finally, we plot Shapley Q-value and validate the property of fair credit assignment.
Choosing with unknown causal information: Action-outcome probabilities for decision making can be grounded in causal models
Venue: arXiv cs.AI 2022
Year: 2022

Decision-making under uncertainty and causal thinking are fundamental aspects of intelligent reasoning. Decision-making has been well studied when the available information is considered at the associative (probabilistic) level. The classical Theorems of von Neumann-Morgenstern and Savage provide a formal criterion for rational choice using associative information: maximize expected utility. There is an ongoing debate around the origin of probabilities involved in such calculation. In this work, we will show how the probabilities for decision-making can be grounded in causal models by considering decision problems in which the available actions and consequences are causally connected. In this setting, actions are regarded as an intervention over a causal model. Then, we extend a previous causal decision-making result, which relies on a known causal model, to the case in which the causal mechanism that controls some environment is unknown to a rational decision-maker. In this way, action-outcome probabilities can be grounded in causal models in known and unknown cases. Finally, as an application, we extend the well-known concept of Nash Equilibrium to the case in which the players of a strategic game consider causal information.
Model Agnostic Defence against Backdoor Attacks in Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

Machine Learning (ML) has automated a multitude of our day-to-day decision making domains such as education, employment and driving automation. The continued success of ML largely depends on our ability to trust the model we are using. Recently, a new class of attacks called Backdoor Attacks have been developed. These attacks undermine the user's trust in ML models. In this work, we present NEO, a model agnostic framework to detect and mitigate such backdoor attacks in image classification ML models. For a given image classification model, our approach analyses the inputs it receives and determines if the model is backdoored. In addition to this feature, we also mitigate these attacks by determining the correct predictions of the poisoned images. An appealing feature of NEO is that it can, for the first time, isolate and reconstruct the backdoor trigger. NEO is also the first defence methodology, to the best of our knowledge that is completely blackbox. We have implemented NEO and evaluated it against three state of the art poisoned models. These models include highly critical applications such as traffic sign detection (USTS) and facial detection. In our evaluation, we show that NEO can detect $\approx$88% of the poisoned inputs on average and it is as fast as 4.4 ms per input image. We also reconstruct the poisoned input for the user to effectively test their systems.
Improved circuits for a biologically-inspired random pulse computer
Venue: arXiv cs.ET 2022
Year: 2022

We present improved circuits intended for building a universal computer based on Random Pulse Computing (RPC) paradigm, a biologically-inspired way of computation in which variable is represented by a frequency of a Random Pulse Train (RPT) rather than a logic state. The RPC we mention here is also known as "stochastic unipolar computation" in newer literature. Unlike in previous art, where randomness is obtained from electronics noise or a pseudorandom shift register while processing circuitry is deterministic, in our approach both variable generation and signal processing rely on the random flip-flop (RFF) whose randomness is derived from a fundamentally random quantum process. This offers advantage in better precision and faster calculation.
Towards Making the Most of BERT in Neural Machine Translation
Venue: arXiv cs.CL 2022
Year: 2022

GPT-2 and BERT demonstrate the effectiveness of using pre-trained language models (LMs) on various natural language processing tasks. However, LM fine-tuning often suffers from catastrophic forgetting when applied to resource-rich tasks. In this work, we introduce a concerted training framework (CTNMT) that is the key to integrate the pre-trained LMs to neural machine translation (NMT). Our proposed CTNMT consists of three techniques: a) asymptotic distillation to ensure that the NMT model can retain the previous pre-trained knowledge; b) a dynamic switching gate to avoid catastrophic forgetting of pre-trained knowledge; and c) a strategy to adjust the learning paces according to a scheduled policy. Our experiments in machine translation show CTNMT gains of up to 3 BLEU score on the WMT14 English-German language pair which even surpasses the previous state-of-the-art pre-training aided NMT by 1.4 BLEU score. While for the large WMT14 English-French task with 40 millions of sentence-pairs, our base model still significantly improves upon the state-of-the-art Transformer big model by more than 1 BLEU score. The code and model can be downloaded from https://github.com/bytedance/neurst/ tree/master/examples/ctnmt.
Sensor-Based Estimation of Dim Light Melatonin Onset (DLMO) Using Features of Two Time Scales
Venue: arXiv cs.LG 2022
Year: 2022

Circadian rhythms influence multiple essential biological activities including sleep, performance, and mood. The dim light melatonin onset (DLMO) is the gold standard for measuring human circadian phase (i.e., timing). The collection of DLMO is expensive and time-consuming since multiple saliva or blood samples are required overnight in special conditions, and the samples must then be assayed for melatonin. Recently, several computational approaches have been designed for estimating DLMO. These methods collect daily sampled data (e.g., sleep onset/offset times) or frequently sampled data (e.g., light exposure/skin temperature/physical activity collected every minute) to train learning models for estimating DLMO. One limitation of these studies is that they only leverage one time-scale data. We propose a two-step framework for estimating DLMO using data from both time scales. The first step summarizes data from before the current day, while the second step combines this summary with frequently sampled data of the current day. We evaluate three moving average models that input sleep timing data as the first step and use recurrent neural network models as the second step. The results using data from 207 undergraduates show that our two-step model with two time-scale features has statistically significantly lower root-mean-square errors than models that use either daily sampled data or frequently sampled data.
Indoor Depth Completion with Boundary Consistency and Self-Attention
Venue: arXiv cs.CV 2022
Year: 2022

Depth estimation features are helpful for 3D recognition. Commodity-grade depth cameras are able to capture depth and color image in real-time. However, glossy, transparent or distant surface cannot be scanned properly by the sensor. As a result, enhancement and restoration from sensing depth is an important task. Depth completion aims at filling the holes that sensors fail to detect, which is still a complex task for machine to learn. Traditional hand-tuned methods have reached their limits, while neural network based methods tend to copy and interpolate the output from surrounding depth values. This leads to blurred boundaries, and structures of the depth map are lost. Consequently, our main work is to design an end-to-end network improving completion depth maps while maintaining edge clarity. We utilize self-attention mechanism, previously used in image inpainting fields, to extract more useful information in each layer of convolution so that the complete depth map is enhanced. In addition, we propose boundary consistency concept to enhance the depth map quality and structure. Experimental results validate the effectiveness of our self-attention and boundary consistency schema, which outperforms previous state-of-the-art depth completion work on Matterport3D dataset. Our code is publicly available at https://github.com/tsunghan-wu/Depth-Completion.
A Novel Approach to the Partial Information Decomposition
Venue: arXiv cs.IT 2022
Year: 2022

We consider the "partial information decomposition" (PID) problem, which aims to decompose the information that a set of source random variables provide about a target random variable into separate redundant, synergistic, union, and unique components. In the first part of this paper, we propose a general framework for constructing a multivariate PID. Our framework is defined in terms of a formal analogy with intersection and union from set theory, along with an ordering relation which specifies when one information source is more informative than another. Our definitions are algebraically and axiomatically motivated, and can be generalized to domains beyond Shannon information theory (such as algorithmic information theory and quantum information theory). In the second part of this paper, we use our general framework to define a PID in terms of the well-known Blackwell order, which has a fundamental operational interpretation. We demonstrate our approach on numerous examples and show that it overcomes many drawbacks associated with previous proposals.
An incompressibility theorem for automatic complexity
Venue: arXiv cs.FL 2022
Year: 2022

Shallit and Wang showed that the automatic complexity $A(x)$ satisfies $A(x)\ge n/13$ for almost all $x\in{\{\mathtt{0},\mathtt{1}\}}^n$. They also stated that Holger Petersen had informed them that the constant 13 can be reduced to 7. Here we show that it can be reduced to $2+ε$ for any $ε>0$. The result also applies to nondeterministic automatic complexity $A_N(x)$. In that setting the result is tight inasmuch as $A_N(x)\le n/2+1$ for all $x$.
NarrativeTime: Dense Temporal Annotation on a Timeline
Venue: arXiv cs.CL 2022
Year: 2022

For the past decade, temporal annotation has been sparse: only a small portion of event pairs in a text was annotated. We present NarrativeTime, the first timeline-based annotation framework that achieves full coverage of all possible TLinks. To compare with the previous SOTA in dense temporal annotation, we perform full re-annotation of TimeBankDense corpus, which shows comparable agreement with a significant increase in density. We contribute TimeBankNT corpus (with each text fully annotated by two expert annotators), extensive annotation guidelines, open-source tools for annotation and conversion to TimeML format, baseline results, as well as quantitative and qualitative analysis of inter-annotator agreement.
Pacer: Comprehensive Network Side-Channel Mitigation in the Cloud
Venue: arXiv cs.CR 2022
Year: 2022

Network side channels (NSCs) leak secrets through packet timing and packet sizes. They are of particular concern in public IaaS Clouds, where any tenant may be able to colocate and indirectly observe a victim's traffic shape. We present Pacer, the first system that eliminates NSC leaks in public IaaS Clouds end-to-end. It builds on the principled technique of shaping guest traffic outside the guest to make the traffic shape independent of secrets by design. However, Pacer also addresses important concerns that have not been considered in prior work -- it prevents internal side-channel leaks from affecting reshaped traffic, and it respects network flow control, congestion control and loss recovery signals. Pacer is implemented as a paravirtualizing extension to the host hypervisor, requiring modest changes to the hypervisor and the guest kernel, and only optional, minimal changes to applications. We present Pacer's key abstraction of a cloaked tunnel, describe its design and implementation, prove the security of important design aspects through a formal model, and show through an experimental evaluation that Pacer imposes moderate overheads on bandwidth, client latency, and server throughput, while thwarting attacks based on state-of-the-art CNN classifiers.
Simplified decision making in the belief space using belief sparsification
Venue: arXiv cs.AI 2022
Year: 2022

In this work, we introduce a new and efficient solution approach for the problem of decision making under uncertainty, which can be formulated as decision making in a belief space, over a possibly high-dimensional state space. Typically, to solve a decision problem, one should identify the optimal action from a set of candidates, according to some objective. We claim that one can often generate and solve an analogous yet simplified decision problem, which can be solved more efficiently. A wise simplification method can lead to the same action selection, or one for which the maximal loss in optimality can be guaranteed. Furthermore, such simplification is separated from the state inference and does not compromise its accuracy, as the selected action would finally be applied on the original state. First, we present the concept for general decision problems and provide a theoretical framework for a coherent formulation of the approach. We then practically apply these ideas to decision problems in the belief space, which can be simplified by considering a sparse approximation of their initial belief. The scalable belief sparsification algorithm we provide is able to yield solutions which are guaranteed to be consistent with the original problem. We demonstrate the benefits of the approach in the solution of a realistic active-SLAM problem and manage to significantly reduce computation time, with no loss in the quality of solution. This work is both fundamental and practical, and holds numerous possible extensions.
Defining the scope of AI regulations
Venue: arXiv cs.CY 2022
Year: 2022

The paper argues that the material scope of AI regulations should not rely on the term "artificial intelligence (AI)". The argument is developed by proposing a number of requirements for legal definitions, surveying existing AI definitions, and then discussing the extent to which they meet the proposed requirements. It is shown that existing definitions of AI do not meet the most important requirements for legal definitions. Next, the paper argues that a risk-based approach would be preferable. Rather than using the term AI, policy makers should focus on the specific risks they want to reduce. It is shown that the requirements for legal definitions can be better met by defining the main sources of relevant risks: certain technical approaches (e.g. reinforcement learning), applications (e.g. facial recognition), and capabilities (e.g. the ability to physically interact with the environment). Finally, the paper discusses the extent to which this approach can also be applied to more advanced AI systems.
A Flexible and Lightweight Group Authentication Scheme
Venue: arXiv cs.CR 2022
Year: 2022

Internet of Things (IoT) networks are becoming a part of our daily lives, as the number of IoT devices around us are surging. The authentication of millions of connected things and the distribution and management of secret keys between these devices pose challenging research problems. Current one-to-one authentication schemes do not take the resource limitations of IoT devices into consideration. Nor do they address the scalability problem of massive machine type communication (mMTC) networks. Group authentication schemes (GAS), on the other hand, have emerged as novel approaches for many-to-many authentication problems. They can be used to simultaneously authenticate numerous resource-constrained devices. However, existing GAS are not energy efficient, and they do not provide enough security for widespread use. In this paper, we propose a lightweight GAS that significantly reduces energy consumption on devices, providing almost 80% energy savings when compared to the state-of-the-art solutions. Our approach is also resistant to the replay and man-in-the-middle attacks. The proposed approach also includes a solution for key agreement and key distribution problems in mMTC environments. Moreover, this approach can be used in both centralized and decentralized group authentication scenarios. The proposed approach has the potential to address the fast authentication requirements of the envisioned agile 6G networks, supported through aerial networking nodes.
Rethinking the Micro-Foundation of Opinion Dynamics: Rich Consequences of the Weighted-Median Mechanism
Venue: arXiv cs.SI 2022
Year: 2022

To identify the main mechanisms underlying complex opinion formation processes in social systems, researchers have long been exploring simple mechanistic mathematical models. Most existing opinion dynamics models are built on a common micro-foundation, i.e., the weighted-averaging opinion update. However, we argue that this universally-adopted mechanism features a non-negligible unrealistic feature, which brings unnecessary difficulties in seeking a proper balance between model complexity and predictive power. In this paper, we propose the weighted-median mechanism as a new micro-foundation of opinion dynamics, which, with minimal assumptions, fundamentally resolves the inherent unrealistic feature of the weighted-averaging mechanism. Derived from the cognitive dissonance theory in psychology, the weighted-median mechanism is supported by online experiment data and broadens the applicability of opinion dynamics models to multiple-choice issues with ordered discrete options. Moreover, the weighted-median mechanism, despite being the simplest in form, captures various non-trivial real-world features of opinion evolution, while some widely-studied averaging-based models fail to.
Driving in Dense Traffic with Model-Free Reinforcement Learning
Venue: arXiv cs.RO 2022
Year: 2022

Traditional planning and control methods could fail to find a feasible trajectory for an autonomous vehicle to execute amongst dense traffic on roads. This is because the obstacle-free volume in spacetime is very small in these scenarios for the vehicle to drive through. However, that does not mean the task is infeasible since human drivers are known to be able to drive amongst dense traffic by leveraging the cooperativeness of other drivers to open a gap. The traditional methods fail to take into account the fact that the actions taken by an agent affect the behaviour of other vehicles on the road. In this work, we rely on the ability of deep reinforcement learning to implicitly model such interactions and learn a continuous control policy over the action space of an autonomous vehicle. The application we consider requires our agent to negotiate and open a gap in the road in order to successfully merge or change lanes. Our policy learns to repeatedly probe into the target road lane while trying to find a safe spot to move in to. We compare against two model-predictive control-based algorithms and show that our policy outperforms them in simulation.
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
Venue: arXiv cs.DS 2022
Year: 2022

Let $G=(V,E)$ be a multigraph with a set $T\subseteq V$ of terminals. A path in $G$ is called a $T$-path if its ends are distinct vertices in $T$ and no internal vertices belong to $T$. In 1978, Mader showed a characterization of the maximum number of edge-disjoint $T$-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint $T$-paths. The algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint $T$-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds (1965). When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint $T$-paths. From this certificate, one can obtain the Edmonds--Gallai type decomposition introduced by Sebő and Szegő (2004). The algorithm runs in $O(|E|^2)$ time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of $T$-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.