OpenRaiser/Intern-Atlas huggingface dataset:
Blind Unwrapping of Modulo Reduced Gaussian Vectors: Recovering MSBs from LSBs
Venue: arXiv cs.IT 2021
Year: 2021

We consider the problem of recovering $n$ i.i.d samples from a zero mean multivariate Gaussian distribution with an unknown covariance matrix, from their modulo wrapped measurements, i.e., measurement where each coordinate is reduced modulo $Δ$, for some $Δ>0$. For this setup, which is motivated by quantization and analog-to-digital conversion, we develop a low-complexity iterative decoding algorithm. We show that if a benchmark informed decoder that knows the covariance matrix can recover each sample with small error probability, and $n$ is large enough, the performance of the proposed blind recovery algorithm closely follows that of the informed one. We complement the analysis with numeric results that show that the algorithm performs well even in non-asymptotic conditions.
Go-Explore: a New Approach for Hard-Exploration Problems
Venue: arXiv cs.LG 2021
Year: 2021

A grand challenge in reinforcement learning is intelligent exploration, especially when rewards are sparse or deceptive. Two Atari games serve as benchmarks for such hard-exploration domains: Montezuma's Revenge and Pitfall. On both games, current RL algorithms perform poorly, even those with intrinsic motivation, which is the dominant method to improve performance on hard-exploration domains. To address this shortfall, we introduce a new algorithm called Go-Explore. It exploits the following principles: (1) remember previously visited states, (2) first return to a promising state (without exploration), then explore from it, and (3) solve simulated environments through any available means (including by introducing determinism), then robustify via imitation learning. The combined effect of these principles is a dramatic performance improvement on hard-exploration problems. On Montezuma's Revenge, Go-Explore scores a mean of over 43k points, almost 4 times the previous state of the art. Go-Explore can also harness human-provided domain knowledge and, when augmented with it, scores a mean of over 650k points on Montezuma's Revenge. Its max performance of nearly 18 million surpasses the human world record, meeting even the strictest definition of "superhuman" performance. On Pitfall, Go-Explore with domain knowledge is the first algorithm to score above zero. Its mean score of almost 60k points exceeds expert human performance. Because Go-Explore produces high-performing demonstrations automatically and cheaply, it also outperforms imitation learning work where humans provide solution demonstrations. Go-Explore opens up many new research directions into improving it and weaving its insights into current RL algorithms. It may also enable progress on previously unsolvable hard-exploration problems in many domains, especially those that harness a simulator during training (e.g. robotics).
Ensembling methods for countrywide short term forecasting of gas demand
Venue: arXiv cs.LG 2021
Year: 2021

Gas demand is made of three components: Residential, Industrial, and Thermoelectric Gas Demand. Herein, the one-day-ahead prediction of each component is studied, using Italian data as a case study. Statistical properties and relationships with temperature are discussed, as a preliminary step for an effective feature selection. Nine "base forecasters" are implemented and compared: Ridge Regression, Gaussian Processes, Nearest Neighbours, Artificial Neural Networks, Torus Model, LASSO, Elastic Net, Random Forest, and Support Vector Regression (SVR). Based on them, four ensemble predictors are crafted: simple average, weighted average, subset average, and SVR aggregation. We found that ensemble predictors perform consistently better than base ones. Moreover, our models outperformed Transmission System Operator (TSO) predictions in a two-year out-of-sample validation. Such results suggest that combining predictors may lead to significant performance improvements in gas demand forecasting.
Exact Optimization via Sums of Nonnegative Circuits and Sums of AM/GM Exponentials
Venue: arXiv cs.SC 2021
Year: 2021

We provide two hybrid numeric-symbolic optimization algorithms, computing exact sums of nonnegative circuits (SONC) and sums of arithmetic-geometric-exponentials (SAGE) decompositions. Moreover, we provide a hybrid numeric-symbolic decision algorithm for polynomials lying in the interior of the SAGE cone. Each framework, inspired by previous contributions of Parrilo and Peyrl, is a rounding-projection procedure. For a polynomial lying in the interior of the SAGE cone, we prove that the decision algorithm terminates within a number of arithmetic operations, which is polynomial in the number of terms of the input, and linear in the distance to the boundary of the cone. We also provide experimental comparisons regarding the implementation of the two optimization algorithms.
Decentralized Multi-Agents by Imitation of a Centralized Controller
Venue: arXiv cs.MA 2021
Year: 2021

We consider a multi-agent reinforcement learning problem where each agent seeks to maximize a shared reward while interacting with other agents, and they may or may not be able to communicate. Typically the agents do not have access to other agent policies and thus each agent is situated in a non-stationary and partially-observable environment. In order to obtain multi-agents that act in a decentralized manner, we introduce a novel algorithm under the popular framework of centralized training, but decentralized execution. This training framework first obtains solutions to a multi-agent problem with a single centralized joint-space learner, which is then used to guide imitation learning for independent decentralized multi-agents. This framework has the flexibility to use any reinforcement learning algorithm to obtain the expert as well as any imitation learning algorithm to obtain the decentralized agents. This is in contrast to other multi-agent learning algorithms that, for example, can require more specific structures. We present some theoretical bounds for our method, and we show that one can obtain decentralized solutions to a multi-agent problem through imitation learning.
A coalgebraic take on regular and $ω$-regular behaviours
Venue: arXiv cs.LO 2021
Year: 2021

We present a general coalgebraic setting in which we define finite and infinite behaviour with Büchi acceptance condition for systems whose type is a monad. The first part of the paper is devoted to presenting a construction of a monad suitable for modelling (in)finite behaviour. The second part of the paper focuses on presenting the concepts of a (coalgebraic) automaton and its ($ω$-) behaviour. We end the paper with coalgebraic Kleene-type theorems for ($ω$-) regular input. The framework is instantiated on non-deterministic (Büchi) automata, tree automata and probabilistic automata.
Mitigating Traffic Remapping Attacks in Autonomous Multi-hop Wireless Networks
Venue: arXiv cs.NI 2021
Year: 2021

Multi-hop wireless networks with autonomous nodes are susceptible to selfish traffic remapping attacks (TRAs). Nodes launching TRAs leverage the underlying channel access function to receive unduly high quality of service (QoS) for packet flows traversing source-to-destination routes. TRAs are easy to execute, impossible to prevent, difficult to detect, and harmful to the QoS of honest nodes. Recognizing the need for providing QoS security, we use a novel network-oriented QoS metric to propose a self-enforcing game-theoretic mitigation approach. By switching between TRA and honest behavior, selfish nodes engage in a noncooperative multistage game in pursuit of high QoS. We analyze feasible node strategies and design a distributed signaling mechanism called DISTRESS, under which, given certain conditions, the game produces a desirable outcome: after an upper-bounded play time, honesty tends to become a selfish node's best-reply behavior, while yielding acceptable QoS to most or all nodes. We verify these findings by Monte Carlo and ns-3 simulations of static and mobile nodes.
Robust Multi-instance Learning with Stable Instances
Venue: arXiv cs.LG 2021
Year: 2021

Multi-instance learning (MIL) deals with tasks where data is represented by a set of bags and each bag is described by a set of instances. Unlike standard supervised learning, only the bag labels are observed whereas the label for each instance is not available to the learner. Previous MIL studies typically follow the i.i.d. assumption, that the training and test samples are independently drawn from the same distribution. However, such assumption is often violated in real-world applications. Efforts have been made towards addressing distribution changes by importance weighting the training data with the density ratio between the training and test samples. Unfortunately, models often need to be trained without seeing the test distributions. In this paper we propose possibly the first framework for addressing distribution change in MIL without requiring access to the unlabeled test data. Our framework builds upon identifying a novel connection between MIL and the potential outcome framework in causal effect estimation. Experimental results on synthetic distribution change datasets, real-world datasets with synthetic distribution biases and real distributional biased image classification datasets validate the effectiveness of our approach.
An application of parallel cut elimination in multiplicative linear logic to the Taylor expansion of proof nets
Venue: arXiv cs.LO 2021
Year: 2021

We examine some combinatorial properties of parallel cut elimination in multiplicative linear logic (MLL) proof nets. We show that, provided we impose a constraint on some paths, we can bound the size of all the nets satisfying this constraint and reducing to a fixed resultant net. This result gives a sufficient condition for an infinite weighted sum of nets to reduce into another sum of nets, while keeping coefficients finite. We moreover show that our constraints are stable under reduction. Our approach is motivated by the quantitative semantics of linear logic: many models have been proposed, whose structure reflect the Taylor expansion of multiplicative exponential linear logic (MELL) proof nets into infinite sums of differential nets. In order to simulate one cut elimination step in MELL, it is necessary to reduce an arbitrary number of cuts in the differential nets of its Taylor expansion. It turns out our results apply to differential nets, because their cut elimination is essentially multiplicative. We moreover show that the set of differential nets that occur in the Taylor expansion of an MELL net automatically satisfies our constraints. Interestingly, our nets are untyped: we only rely on the sequentiality of linear logic nets and the dynamics of cut elimination. The paths on which we impose bounds are the switching paths involved in the Danos--Regnier criterion for sequentiality. In order to accommodate multiplicative units and weakenings, our nets come equipped with jumps: each weakening node is connected to some other node. Our constraint can then be summed up as a bound on both the length of switching paths, and the number of weakenings that jump to a common node.
On the Complexity of Anonymous Communication Through Public Networks
Venue: arXiv cs.CR 2021
Year: 2021

Onion routing is the most widely used approach to anonymous communication online. The idea is that Alice wraps her message to Bob in layers of encryption to form an "onion," and routes it through a series of intermediaries. Each intermediary's job is to decrypt ("peel") the onion it receives to obtain instructions for where to send it next, and what to send. The intuition is that, by the time it gets to Bob, the onion will have mixed with so many other onions, that its origin will be hard to trace even for an adversary that observes the entire network and controls a fraction of the participants, possibly including Bob. In spite of its widespread use in practice, until now no onion routing protocol was known that simultaneously achieved, in the presence of an active adversary that observes all network traffic and controls a constant fraction of the participants, (a) fault-tolerance, where even if a few of the onions are dropped, the protocol still delivers the rest; (b) reasonable communication and computational complexity as a function of the security parameter and the number of participants; and (c) anonymity. In this paper, we give the first onion routing protocol that meets these goals: our protocol (a) tolerates a polylogarithmic (in the security parameter) number of dropped onions and still delivers the rest; (b) requires a polylogarithmic number of rounds and a polylogarithmic number of onions sent per participant per round; and (c) achieves anonymity. We also show that to achieve anonymity in a fault-tolerant fashion via onion routing, this number of onions and rounds is necessary. Of independent interest, our analysis introduces two new security properties of onion routing -- mixing and equalizing -- and we show that together they imply anonymity.
Non-Suicidal Self-Injury Online Posts: Implications for Mental Health Professionals
Venue: arXiv cs.CY 2021
Year: 2021

While non-suicidal self-injury (NSSI) is not a new phenomenon, there is still a limited yet little is still known about understanding of the behavior, the intent behind the behavior and what the individuals themselves say about their behavior. This study collected pro-NSSI public blog posts from Reddit on pro-NSSI and analyzed the content linguistically using LIWC software, in order to examine the use of NSSI specific words, linguistic properties and the psychological linguistic properties. were examined. The results inform current counseling practices by dispelling myths and providing insight into the inner world of people who engage in use NSSII to cope. The most frequently appearing category of For NSSI specific words categories, in the Reddit blogs was the reasons in which one engagesfor engaging in NSSI was the most frequently used in the Reddit blogs. The linguistic properties found in the analysis reflected the predicted results; authors of pro-NSSI posts used demonstrated expected results of first-person singular pronouns extensively, which indicatesing high levels of mental health distress and isolation. The psychological linguistic properties that could be observed of in these public Reddit posts were dominantly in a negative emotional tone which demonstrates youth and impulsivity. The linguistic properties found when these posts were analyzed supports the work of earlier studies that dispelled common myths about NSSI that were circulating in the mental health community. These findings suggest that the language of people who engage in NSSI supports research findings in dispelling common myths about NSSI.
Towards a Robust Deep Neural Network in Texts: A Survey
Venue: arXiv cs.CL 2021
Year: 2021

Deep neural networks (DNNs) have achieved remarkable success in various tasks (e.g., image classification, speech recognition, and natural language processing (NLP)). However, researchers have demonstrated that DNN-based models are vulnerable to adversarial examples, which cause erroneous predictions by adding imperceptible perturbations into legitimate inputs. Recently, studies have revealed adversarial examples in the text domain, which could effectively evade various DNN-based text analyzers and further bring the threats of the proliferation of disinformation. In this paper, we give a comprehensive survey on the existing studies of adversarial techniques for generating adversarial texts written by both English and Chinese characters and the corresponding defense methods. More importantly, we hope that our work could inspire future studies to develop more robust DNN-based text analyzers against known and unknown adversarial techniques. We classify the existing adversarial techniques for crafting adversarial texts based on the perturbation units, helping to better understand the generation of adversarial texts and build robust models for defense. In presenting the taxonomy of adversarial attacks and defenses in the text domain, we introduce the adversarial techniques from the perspective of different NLP tasks. Finally, we discuss the existing challenges of adversarial attacks and defenses in texts and present the future research directions in this emerging and challenging field.
S-TRIGGER: Continual State Representation Learning via Self-Triggered Generative Replay
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of building a state representation model for control, in a continual learning setting. As the environment changes, the aim is to efficiently compress the sensory state's information without losing past knowledge, and then use Reinforcement Learning on the resulting features for efficient policy learning. To this end, we propose S-TRIGGER, a general method for Continual State Representation Learning applicable to Variational Auto-Encoders and its many variants. The method is based on Generative Replay, i.e. the use of generated samples to maintain past knowledge. It comes along with a statistically sound method for environment change detection, which self-triggers the Generative Replay. Our experiments on VAEs show that S-TRIGGER learns state representations that allows fast and high-performing Reinforcement Learning, while avoiding catastrophic forgetting. The resulting system is capable of autonomously learning new information without using past data and with a bounded system size. Code for our experiments is attached in Appendix.
Population protocols with unreliable communication
Venue: arXiv cs.DC 2021
Year: 2021

Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication opportunities occur nondeterministically, allowing the agents involved to change their states based on each other's states. In the present paper we study unreliable models based on population protocols and their variations from the point of view of expressive power. We model the effects of message loss. We show that for a general definition of unreliable protocols with constant-storage agents such protocols can only compute predicates computable by immediate observation population protocols (sometimes also called one-way protocols). Immediate observation population protocols are inherently tolerant of unreliable communication and keep their expressive power under a wide range of fairness conditions. We also prove that a large class of message-based models that are generally more expressive than immediate observation becomes strictly less expressive than immediate observation in the unreliable case.
A multimodal movie review corpus for fine-grained opinion mining
Venue: arXiv cs.MM 2021
Year: 2021

In this paper, we introduce a set of opinion annotations for the POM movie review dataset, composed of 1000 videos. The annotation campaign is motivated by the development of a hierarchical opinion prediction framework allowing one to predict the different components of the opinions (e.g. polarity and aspect) and to identify the corresponding textual spans. The resulting annotations have been gathered at two granularity levels: a coarse one (opinionated span) and a finer one (span of opinion components). We introduce specific categories in order to make the annotation of opinions easier for movie reviews. For example, some categories allow the discovery of user recommendation and preference in movie reviews. We provide a quantitative analysis of the annotations and report the inter-annotator agreement under the different levels of granularity. We provide thus the first set of ground-truth annotations which can be used for the task of fine-grained multimodal opinion prediction. We provide an analysis of the data gathered through an inter-annotator study and show that a linear structured predictor learns meaningful features even for the prediction of scarce labels. Both the annotations and the baseline system are made publicly available. https://github.com/eusip/POM/
Tensor-variate Mixture of Experts for Proportional Myographic Control of a Robotic Hand
Venue: arXiv cs.RO 2021
Year: 2021

When data are organized in matrices or arrays of higher dimensions (tensors), classical regression methods first transform these data into vectors, therefore ignoring the underlying structure of the data and increasing the dimensionality of the problem. This flattening operation typically leads to overfitting when only few training data is available. In this paper, we present a mixture-of-experts model that exploits tensorial representations for regression of tensor-valued data. The proposed formulation takes into account the underlying structure of the data and remains efficient when few training data are available. Evaluation on artificially generated data, as well as offline and real-time experiments recognizing hand movements from tactile myography prove the effectiveness of the proposed approach.
An Improved Approximation Algorithm for Maximin Shares
Venue: arXiv cs.GT 2021
Year: 2021

Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a fair manner. We study the case where m indivisible items need to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist, a series of work provided approximation algorithms for a 2/3-MMS allocation in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, Ghodsi et al. [EC'2018] showed the existence of a 3/4-MMS allocation and a PTAS to find a (3/4-ε)-MMS allocation for an ε> 0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 3/4-MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial-time algorithm to find a 3/4-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (3/4 + 1/(12n))-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 3/4 was the best factor known for n> 4.
Design and Development of Underwater Vehicle: ANAHITA
Venue: arXiv cs.RO 2021
Year: 2021

Anahita is an autonomous underwater vehicle which is currently being developed by interdisciplinary team of students at Indian Institute of Technology(IIT) Kanpur with aim to provide a platform for research in AUV to undergraduate students. This is the second vehicle which is being designed by AUV-IITK team to participate in 6th NIOT-SAVe competition organized by the National Institute of Ocean Technology, Chennai. The Vehicle has been completely redesigned with the major improvements in modularity and ease of access of all the components, keeping the design very compact and efficient. New advancements in the vehicle include, power distribution system and monitoring system. The sensors include the inertial measurement units (IMU), hydrophone array, a depth sensor, and two RGB cameras. The current vehicle features hot swappable battery pods giving a huge advantage over the previous vehicle, for longer runtime.