OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Planning for Dynamic Resource Allocation in Smart and Connected Communities
Venue: arXiv cs.MA 2021
Year: 2021

Resource allocation under uncertainty is a classical problem in city-scale cyber-physical systems. Consider emergency response as an example; urban planners and first responders optimize the location of ambulances to minimize expected response times to incidents such as road accidents. Typically, such problems deal with sequential decision-making under uncertainty and can be modeled as Markov (or semi-Markov) decision processes. The goal of the decision-maker is to learn a mapping from states to actions that can maximize expected rewards. While online, offline, and decentralized approaches have been proposed to tackle such problems, scalability remains a challenge for real-world use-cases. We present a general approach to hierarchical planning that leverages structure in city-level CPS problems for resource allocation. We use emergency response as a case study and show how a large resource allocation problem can be split into smaller problems. We then use Monte-Carlo planning for solving the smaller problems and managing the interaction between them. Finally, we use data from Nashville, Tennessee, a major metropolitan area in the United States, to validate our approach. Our experiments show that the proposed approach outperforms state-of-the-art approaches used in the field of emergency response.
Dependent Type Systems as Macros
Venue: arXiv cs.PL 2021
Year: 2021

We present Turnstile+, a high-level, macros-based metaDSL for building dependently typed languages. With it, programmers may rapidly prototype and iterate on the design of new dependently typed features and extensions. Or they may create entirely new DSLs whose dependent type "power" is tailored to a specific domain. Our framework's support of language-oriented programming also makes it suitable for experimenting with systems of interacting components, e.g., a proof assistant and its companion DSLs. This paper explains the implementation details of Turnstile+, as well as how it may be used to create a wide-variety of dependently typed languages, from a lightweight one with indexed types, to a full spectrum proof assistant, complete with a tactic system and extensions for features like sized types and SMT interaction.
Towards safe human-to-robot handovers of unknown containers
Venue: arXiv cs.RO 2021
Year: 2021

Safe human-to-robot handovers of unknown objects require accurate estimation of hand poses and object properties, such as shape, trajectory, and weight. Accurately estimating these properties requires the use of scanned 3D object models or expensive equipment, such as motion capture systems and markers, or both. However, testing handover algorithms with robots may be dangerous for the human and, when the object is an open container with liquids, for the robot. In this paper, we propose a real-to-simulation framework to develop safe human-to-robot handovers with estimations of the physical properties of unknown cups or drinking glasses and estimations of the human hands from videos of a human manipulating the container. We complete the handover in simulation, and we estimate a region that is not occluded by the hand of the human holding the container. We also quantify the safeness of the human and object in simulation. We validate the framework using public recordings of containers manipulated before a handover and show the safeness of the handover when using noisy estimates from a range of perceptual algorithms.
Physical Layer Security for NOMA-Enabled Multi-Access Edge Computing Wireless Networks
Venue: arXiv cs.IT 2021
Year: 2021

Multi-access edge computing (MEC) has been regarded as a promising technique for enhancing computation capabilities for wireless networks. In this paper, we study physical layer security in an MEC system where multiple users offload partial of their computation tasks to a base station simultaneously based on non-orthogonal multiple access (NOMA), in the presence of a malicious eavesdropper. Secrecy outage probability is adopted to measure the security performance of the computation offloading against eavesdropping attacks. We aim to minimize the sum energy consumption of all the users, subject to constraints in terms of the secrecy offloading rate, the secrecy outage probability, and the decoding order of NOMA. Although the original optimization problem is non-convex and challenging to solve, we put forward an efficient algorithm based on sequential convex approximation and penalty dual decomposition. Numerical results are eventually provided to validate the convergence of the proposed algorithm and its superior energy efficiency with secrecy requirements.
Average-Case Communication Complexity of Statistical Problems
Venue: arXiv cs.CC 2021
Year: 2021

We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. Communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and $\mathbb{F}_2$-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.
Short-term probabilistic photovoltaic power forecast based on deep convolutional long short-term memory network and kernel density estimation
Venue: arXiv cs.LG 2021
Year: 2021

Solar energy is a clean and renewable energy. Photovoltaic (PV) power is an important way to utilize solar energy. Accurate PV power forecast is crucial to the large-scale application of PV power and the stability of electricity grid. This paper proposes a novel method for short-term photovoltaic power forecast using deep convolutional long short-term memory (ConvLSTM) network and kernel density estimation (KDE). In the proposed method, ConvLSTM is used to forecast the future photovoltaic power and KDE is used for estimating the joint probabilistic density function and giving the probabilistic confidence interval. Experiments in an actual photovoltaic power station verify the effectiveness of the proposed method. Comparison experiments with convolutional neural network (CNN) and long short-term memory network (LSTM)shows that ConvLSTM can combine the advantages of both CNN and LSTM and significantly outperform CNN and LSTM in terms of forecast accuracy. Through further comparison with other five conventional methods including multilayer perceptron (MLP), support vector regression (SVR), extreme learning machine (ELM), classification and regression tree (CART) and gradient boosting decision tree (GBDT), ConvLSTM can significantly improve the forecast accuracy by more than 20% for most of the five methods and the superiorities of ConvLSTM are further verified.
Approximate Core Allocations for Multiple Partners Matching Games
Venue: arXiv cs.GT 2021
Year: 2021

The matching game is a cooperative game where the value of every coalition is the maximum revenue of players in the coalition can make by forming pairwise disjoint partners. The multiple partners matching game generalizes the matching game by allowing each player to have more than one possibly repeated partner. In this paper, we study profit-sharing in multiple partners matching games. A central concept for profit-sharing is the core which consists of all possible ways of distributing the profit among individual players such that the grand coalition remains intact. The core of multiple partners matching games may be empty [Deng et al., Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res., 1999.]; even when the core is non-empty, the core membership problem is intractable in general [Biro et al., The stable fixtures problem with payments, Games Econ. Behav., 2018]. Thus we study approximate core allocations upon which a coalition may be paid less than the profit it makes by seceding from the grand coalition. We provide an LP-based mechanism guaranteeing that no coalition is paid less than $2/3$ times the profit it makes on its own. We also show that $2/3$ is the best possible factor relative to the underlying LP-relaxation. Our result generalizes the work of Vazirani [Vazirani, The general graph matching game: approximate core, arXiv, 2021] from matching games to multiple partners matching games.
First-Order logic and its Infinitary Quantifier Extensions over Countable Words
Venue: arXiv cs.LO 2021
Year: 2021

We contribute to the refined understanding of the language-logic-algebra interplay in the context of first-order properties of countable words. We establish decidable algebraic characterizations of one variable fragment of FO as well as boolean closure of existential fragment of FO via a strengthening of Simon's theorem about piecewise testable languages. We propose a new extension of FO which admits infinitary quantifiers to reason about the inherent infinitary properties of countable words. We provide a very natural and hierarchical block-product based characterization of the new extension. We also explicate its role in view of other natural and classical logical systems such as WMSO and FO[cut] - an extension of FO where quantification over Dedekind-cuts is allowed. We also rule out the possibility of a finite basis for a block-product based characterization of these logical systems. Finally, we report simple but novel algebraic characterizations of one variable fragments of the hierarchies of the new proposed extension of FO.
Using Computer Simulations to Investigate the Potential Performance of 'A to B' Routing Systems for People with Mobility Impairments
Venue: arXiv cs.HC 2021
Year: 2021

Navigating from 'A to B' remains a serious problem for many people with mobility impairments, due to the need to avoid accessibility barriers. Yet there is currently no effective routing tool that is regularly used by people with disabilities in order to effectively avoid accessibility barriers in the built environment. To explore what is required to produce an effective routing tool, we have conducted Monte-Carlo simulations, simulating over 460 million journeys. This work illustrates the need to focus on barrier minimization, instead of barrier avoidance, due to the limitations of what can be achieved by any accessibility documentation tool. We also make a substantial contribution to the concern of meaningful performance metrics for activity recognition, illustrating how simulations can operate as useful real-world performance metrics for information sources utilized by navigation systems.
CasEE: A Joint Learning Framework with Cascade Decoding for Overlapping Event Extraction
Venue: arXiv cs.CL 2021
Year: 2021

Event extraction (EE) is a crucial information extraction task that aims to extract event information in texts. Most existing methods assume that events appear in sentences without overlaps, which are not applicable to the complicated overlapping event extraction. This work systematically studies the realistic event overlapping problem, where a word may serve as triggers with several types or arguments with different roles. To tackle the above problem, we propose a novel joint learning framework with cascade decoding for overlapping event extraction, termed as CasEE. Particularly, CasEE sequentially performs type detection, trigger extraction and argument extraction, where the overlapped targets are extracted separately conditioned on the specific former prediction. All the subtasks are jointly learned in a framework to capture dependencies among the subtasks. The evaluation on a public event extraction benchmark FewFC demonstrates that CasEE achieves significant improvements on overlapping event extraction over previous competitive methods.
Learning in nonatomic games, Part I: Finite action spaces and population games
Venue: arXiv cs.GT 2021
Year: 2021

We examine the long-run behavior of a wide range of dynamics for learning in nonatomic games, in both discrete and continuous time. The class of dynamics under consideration includes fictitious play and its regularized variants, the best-reply dynamics (again, possibly regularized), as well as the dynamics of dual averaging / "follow the regularized leader" (which themselves include as special cases the replicator dynamics and Friedman's projection dynamics). Our analysis concerns both the actual trajectory of play and its time-average, and we cover potential and monotone games, as well as games with an evolutionarily stable state (global or otherwise). We focus exclusively on games with finite action spaces; nonatomic games with continuous action spaces are treated in detail in Part II of this paper.
Implicit Gender Bias in Computer Science -- A Qualitative Study
Venue: arXiv cs.CY 2021
Year: 2021

Gender diversity in the tech sector is - not yet? - sufficient to create a balanced ratio of men and women. For many women, access to computer science is hampered by socialization-related, social, cultural and structural obstacles. The so-called implicit gender bias has a great influence in this respect. The lack of contact in areas of computer science makes it difficult to develop or expand potential interests. Female role models as well as more transparency of the job description should help women to promote their - possible - interest in the job description. However, gender diversity can also be promoted and fostered through adapted measures by leaders.
Learning ODEs via Diffeomorphisms for Fast and Robust Integration
Venue: arXiv cs.LG 2021
Year: 2021

Advances in differentiable numerical integrators have enabled the use of gradient descent techniques to learn ordinary differential equations (ODEs). In the context of machine learning, differentiable solvers are central for Neural ODEs (NODEs), a class of deep learning models with continuous depth, rather than discrete layers. However, these integrators can be unsatisfactorily slow and inaccurate when learning systems of ODEs from long sequences, or when solutions of the system vary at widely different timescales in each dimension. In this paper we propose an alternative approach to learning ODEs from data: we represent the underlying ODE as a vector field that is related to another base vector field by a differentiable bijection, modelled by an invertible neural network. By restricting the base ODE to be amenable to integration, we can drastically speed up and improve the robustness of integration. We demonstrate the efficacy of our method in training and evaluating continuous neural networks models, as well as in learning benchmark ODE systems. We observe improvements of up to two orders of magnitude when integrating learned ODEs with GPUs computation.
Efficient Explanations for Knowledge Compilation Languages
Venue: arXiv cs.AI 2021
Year: 2021

Knowledge compilation (KC) languages find a growing number of practical uses, including in Constraint Programming (CP) and in Machine Learning (ML). In most applications, one natural question is how to explain the decisions made by models represented by a KC language. This paper shows that for many of the best known KC languages, well-known classes of explanations can be computed in polynomial time. These classes include deterministic decomposable negation normal form (d-DNNF), and so any KC language that is strictly less succinct than d-DNNF. Furthermore, the paper also investigates the conditions under which polynomial time computation of explanations can be extended to KC languages more succinct than d-DNNF.
Low-Dimensional State and Action Representation Learning with MDP Homomorphism Metrics
Venue: arXiv cs.LG 2021
Year: 2021

Deep Reinforcement Learning has shown its ability in solving complicated problems directly from high-dimensional observations. However, in end-to-end settings, Reinforcement Learning algorithms are not sample-efficient and requires long training times and quantities of data. In this work, we proposed a framework for sample-efficient Reinforcement Learning that take advantage of state and action representations to transform a high-dimensional problem into a low-dimensional one. Moreover, we seek to find the optimal policy mapping latent states to latent actions. Because now the policy is learned on abstract representations, we enforce, using auxiliary loss functions, the lifting of such policy to the original problem domain. Results show that the novel framework can efficiently learn low-dimensional and interpretable state and action representations and the optimal latent policy.
Towards Scheduling Federated Deep Learning using Meta-Gradients for Inter-Hospital Learning
Venue: arXiv cs.LG 2021
Year: 2021

Given the abundance and ease of access of personal data today, individual privacy has become of paramount importance, particularly in the healthcare domain. In this work, we aim to utilise patient data extracted from multiple hospital data centres to train a machine learning model without sacrificing patient privacy. We develop a scheduling algorithm in conjunction with a student-teacher algorithm that is deployed in a federated manner. This allows a central model to learn from batches of data at each federal node. The teacher acts between data centres to update the main task (student) algorithm using the data that is stored in the various data centres. We show that the scheduler, trained using meta-gradients, can effectively organise training and as a result train a machine learning model on a diverse dataset without needing explicit access to the patient data. We achieve state-of-the-art performance and show how our method overcomes some of the problems faced in the federated learning such as node poisoning. We further show how the scheduler can be used as a mechanism for transfer learning, allowing different teachers to work together in training a student for state-of-the-art performance.
Mirror Mirror on the Wall: Wireless Environment Reconfiguration Attacks Based on Fast Software-Controlled Surfaces
Venue: arXiv cs.CR 2021
Year: 2021

The intelligent reflecting surface (IRS) is a promising new paradigm in wireless communications for meeting the growing connectivity demands in next-generation mobile networks. IRS, also known as software-controlled metasurfaces, consist of an array of adjustable radio wave reflectors, enabling smart radio environments, e.g., for enhancing the signal-to-noise ratio (SNR) and spatial diversity of wireless channels. Research on IRS to date has been largely focused on constructive applications. In this work, we demonstrate for the first time that the IRS provides a practical low-cost toolkit for attackers to easily perform complex signal manipulation attacks on the physical layer in real time. We introduce the environment reconfiguration attack (ERA) as a novel class of jamming attacks in wireless radio networks. Here, an adversary leverages the IRS to rapidly vary the electromagnetic propagation environment to disturb legitimate receivers. The IRS gives the adversary a key advantage over traditional jamming: It no longer has to actively emit jamming signals, instead the IRS reflects existing legitimate signals. In addition, the adversary doesn't need any knowledge about the legitimate channel. We thoroughly investigate the ERA in wireless systems based on the widely employed orthogonal frequency division multiplexing (OFDM) modulation. We present insights into the attack through analytical analysis, simulations, as well as experiments. Our results show that the ERA allows to severely degrade the available data rates even with reasonably small IRS sizes. Finally, we implement an attacker setup and demonstrate a practical ERA to slow down an entire Wi-Fi network.
A Multilayer Network Model of the Coevolution of the Spread of a Disease and Competing Opinions
Venue: arXiv cs.SI 2021
Year: 2021

During the COVID-19 pandemic, conflicting opinions on physical distancing swept across social media, affecting both human behavior and the spread of COVID-19. Inspired by such phenomena, we construct a two-layer multiplex network for the coupled spread of a disease and conflicting opinions. We model each process as a contagion. On one layer, we consider the concurrent evolution of two opinions -- pro-physical-distancing and anti-physical-distancing -- that compete with each other and have mutual immunity to each other. The disease evolves on the other layer, and individuals are less likely (respectively, more likely) to become infected when they adopt the pro-physical-distancing (respectively, anti-physical-distancing) opinion. We develop approximations of mean-field type by generalizing monolayer pair approximations to multilayer networks; these approximations agree well with Monte Carlo simulations for a broad range of parameters and several network structures. Through numerical simulations, we illustrate the influence of opinion dynamics on the spread of the disease from complex interactions both between the two conflicting opinions and between the opinions and the disease. We find that lengthening the duration that individuals hold an opinion may help suppress disease transmission, and we demonstrate that increasing the cross-layer correlations or intra-layer correlations of node degrees may lead to fewer individuals becoming infected with the disease.
The Least Restriction for Offline Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Many practical applications of reinforcement learning (RL) constrain the agent to learn from a fixed offline dataset of logged interactions, which has already been gathered, without offering further possibility for data collection. However, commonly used off-policy RL algorithms, such as the Deep Q Network and the Deep Deterministic Policy Gradient, are incapable of learning without data correlated to the distribution under the current policy, making them ineffective for this offline setting. As the first step towards useful offline RL algorithms, we analysis the reason of instability in standard off-policy RL algorithms. It is due to the bootstrapping error. The key to avoiding this error, is ensuring that the agent's action space does not go out of the fixed offline dataset. Based on our consideration, a creative offline RL framework, the Least Restriction (LR), is proposed in this paper. The LR regards selecting an action as taking a sample from the probability distribution. It merely set a little limit for action selection, which not only avoid the action being out of the offline dataset but also remove all the unreasonable restrictions in earlier approaches (e.g. Batch-Constrained Deep Q-Learning). In the further, we will demonstrate that the LR, is able to learn robustly from different offline datasets, including random and suboptimal demonstrations, on a range of practical control tasks.
An Information-Theoretic Approach for Automatically Determining the Number of States when Aggregating Markov Chains
Venue: arXiv cs.IT 2021
Year: 2021

A fundamental problem when aggregating Markov chains is the specification of the number of state groups. Too few state groups may fail to sufficiently capture the pertinent dynamics of the original, high-order Markov chain. Too many state groups may lead to a non-parsimonious, reduced-order Markov chain whose complexity rivals that of the original. In this paper, we show that an augmented value-of-information-based approach to aggregating Markov chains facilitates the determination of the number of state groups. The optimal state-group count coincides with the case where the complexity of the reduced-order chain is balanced against the mutual dependence between the original- and reduced-order chain dynamics.