OpenRaiser/Intern-Atlas huggingface dataset:
Improving the Izhikevich Model Based on Rat Basolateral Amygdala and Hippocampus Neurons, and Recognizing Their Possible Firing Patterns
Venue: arXiv cs.NE 2021
Year: 2021

Introduction- Identifying the potential firing patterns following different brain regions under normal and abnormal conditions increases our understanding of events at the level of neural interactions in the brain. The Izhikevich model is one of the simplest biologically plausible models, i.e. capable of capturing the most recognized firing patterns of neurons. This property makes the model efficient in simulating the large-scale networks of neurons. Improving the Izhikevich model for adapting to the neuronal activity of the rat brain with great accuracy would make the model effective for future neural network implementations. Methods- Data sampling from two brain regions, the HIP and BLA, was performed by the extracellular recordings of male rats, and spike sorting was conducted by Plexon offline sorter. Further analyses were performed through NeuroExplorer and MATLAB. To optimize the Izhikevich model parameters, a genetic algorithm was used. The process of comparison in each iteration leads to the survival of better populations until achieving the optimum solution. Results- In the present study, the possible firing patterns of the real single neurons of the HIP and BLA were identified. Additionally, an improved Izhikevich model was achieved. Accordingly, the real neuronal spiking pattern of these regions neurons and the corresponding cases of the Izhikevich neuron spiking pattern were adjusted with great accuracy. Conclusion- This study was conducted to elevate our knowledge of neural interactions in different structures of the brain and accelerate the quality of future large-scale neural network simulations, as well as reducing the modeling complexity. This aim was achievable by performing the improved Izhikevich model, and inserting only the plausible firing patterns, and eliminating unrealistic ones.
Collision Avoidance in Pedestrian-Rich Environments with Deep Reinforcement Learning
Venue: arXiv cs.RO 2021
Year: 2021

Collision avoidance algorithms are essential for safe and efficient robot operation among pedestrians. This work proposes using deep reinforcement (RL) learning as a framework to model the complex interactions and cooperation with nearby, decision-making agents, such as pedestrians and other robots. Existing RL-based works assume homogeneity of agent properties, use specific motion models over short timescales, or lack a principled method to handle a large, possibly varying number of agents. Therefore, this work develops an algorithm that learns collision avoidance among a variety of heterogeneous, non-communicating, dynamic agents without assuming they follow any particular behavior rules. It extends our previous work by introducing a strategy using Long Short-Term Memory (LSTM) that enables the algorithm to use observations of an arbitrary number of other agents, instead of a small, fixed number of neighbors. The proposed algorithm is shown to outperform a classical collision avoidance algorithm, another deep RL-based algorithm, and scales with the number of agents better (fewer collisions, shorter time to goal) than our previously published learning-based approach. Analysis of the LSTM provides insights into how observations of nearby agents affect the hidden state and quantifies the performance impact of various agent ordering heuristics. The learned policy generalizes to several applications beyond the training scenarios: formation control (arrangement into letters), demonstrations on a fleet of four multirotors and on a fully autonomous robotic vehicle capable of traveling at human walking speed among pedestrians.
String Matching with Wildcards in the Massively Parallel Computation Model
Venue: arXiv cs.DC 2021
Year: 2021

We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a pattern) as a substring of string T . Each wildcard character in the pattern matches a specific class of strings based on its type. String matching is one of the most fundamental problems in computer science, especially in the fields of bioinformatics and machine learning. Persistent effort has led to a variety of algorithms for the problem since 1960s. With rise of big data and the inevitable demand to solve problems on huge data sets, there have been many attempts to adapt classic algorithms into the MPC framework to obtain further efficiency. MPC is a recent framework for parallel computation of big data, which is designed to capture the MapReduce-like algorithms. In this paper, we study the string matching problem using a set of tools translated to MPC model. We consider three types of wildcards in string matching: - '?' wildcard: In this setting, the pattern is allowed to contain special '?' characters or don't cares that match any character of the text. String matching with don't cares could be solved by fast convolutions, and we give a constant round MPC algorithm for which by utilizing FFT in a constant number of MPC rounds. - '+' wildcard: '+' wildcard is a special character that allows for arbitrary repetitions of a character. When the pattern contains '+' wildcard characters, our algorithm runs in a constant number of MPC rounds by a reduction from subset matching problem. - '*' wildcard: '*' is a special character that matches with any substring of the text. When '*' is allowed in the pattern, we solve two special cases of the problem in logarithmic rounds.
RACH Optimization with Decision Tree Based Supervised Learning for Conditional Handover in 5G Beamformed Systems
Venue: arXiv cs.NI 2021
Year: 2021

Higher frequencies that are introduced in 5G networks cause rapid signal degradation and challenge user mobility. In recent studies, a conditional handover procedure has been adopted for 5G networks to enhance user mobility robustness. In this paper, mobility performance of the conditional handover is analysed for 5G mm-Wave systems with beamforming. In addition, a resource efficient random access procedure is proposed that increases the chance of contention-free random access during handover, which reduces signaling and interruption time. Moreover, simple, yet, effective decision tree based supervised learning method is proposed to minimize the handover failures that are caused by beam preparation phase of random access procedure. Results reveal the trade-off between contention free random access and handover failures. It is also shown that the optimum operation point of random access is achievable with proposed learning algorithm for conditional handover.
Image-Based Place Recognition on Bucolic Environment Across Seasons From Semantic Edge Description
Venue: arXiv cs.CV 2021
Year: 2021

Most of the research effort on image-based place recognition is designed for urban environments. In bucolic environments such as natural scenes with low texture and little semantic content, the main challenge is to handle the variations in visual appearance across time such as illumination, weather, vegetation state or viewpoints. The nature of the variations is different and this leads to a different approach to describing a bucolic scene. We introduce a global image descriptor computed from its semantic and topological information. It is built from the wavelet transforms of the image semantic edges. Matching two images is then equivalent to matching their semantic edge descriptors. We show that this method reaches state-of-the-art image retrieval performance on two multi-season environment-monitoring datasets: the CMU-Seasons and the Symphony Lake dataset. It also generalises to urban scenes on which it is on par with the current baselines NetVLAD and DELF.
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of quickly computing point-to-point shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have large index size, slow query running times or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives.The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 38 times smaller indexes than competing approaches.
GENDIS: GENetic DIscovery of Shapelets
Venue: arXiv cs.NE 2021
Year: 2021

In the time series classification domain, shapelets are small time series that are discriminative for a certain class. It has been shown that classifiers are able to achieve state-of-the-art results on a plethora of datasets by taking as input distances from the input time series to different discriminative shapelets. Additionally, these shapelets can easily be visualized and thus possess an interpretable characteristic, making them very appealing in critical domains, such as the health care domain, where longitudinal data is ubiquitous. In this study, a new paradigm for shapelet discovery is proposed, which is based upon evolutionary computation. The advantages of the proposed approach are that (i) it is gradient-free, which could allow to escape from local optima more easily and to find suited candidates more easily and supports non-differentiable objectives, (ii) no brute-force search is required, which drastically reduces the computational complexity by several orders of magnitude, (iii) the total amount of shapelets and length of each of these shapelets are evolved jointly with the shapelets themselves, alleviating the need to specify this beforehand, (iv) entire sets are evaluated at once as opposed to single shapelets, which results in smaller final sets with less similar shapelets that result in similar predictive performances, and (v) discovered shapelets do not need to be a subsequence of the input time series. We present the results of experiments which validate the enumerated advantages.
A Game-theoretical Approach to Analyze Film Release Time
Venue: arXiv cs.GT 2021
Year: 2021

Film release dates play an important part in box office revenues because of the facts of obvious seasonality demand in the film industry and severe competition among films shown at the same time. In this paper, we study how film studios choose release time for movies they produce to maximize their box offices. We first formalize this problem as an attraction competition game where players (film studios) consider both potential profits and competitors' choices when deciding the release time. Then we prove that there always exists a pure Nash equilibrium and give the sufficient condition of the uniqueness of the Nash equilibrium. Our model can be generalized to an extensive game and we compute the subgame-perfect equilibrium for homogeneous players. For the case that one film studio could have multiple movies to release, we prove that finding a player's best response is NP-hard and it does not guarantee the existence of a pure Nash equilibrium. Experiments are provided to support the soundness of our model. In the final state, most of film studios, accounting for 84 percent of the market, would not change their release time. The behaviors of film studios imply they are following some strategies to reach a Nash equilibrium.
Automatic Testing With Reusable Adversarial Agents
Venue: arXiv cs.LG 2021
Year: 2021

Autonomous systems such as self-driving cars and general-purpose robots are safety-critical systems that operate in highly uncertain and dynamic environments. We propose an interactive multi-agent framework where the system-under-design is modeled as an ego agent and its environment is modeled by a number of adversarial (ado) agents. For example, a self-driving car is an ego agent whose behavior is influenced by ado agents such as pedestrians, bicyclists, traffic lights, road geometry etc. Given a logical specification of the correct behavior of the ego agent, and a set of constraints that encode reasonable adversarial behavior, our framework reduces the adversarial testing problem to the problem of synthesizing controllers for (constrained) ado agents that cause the ego agent to violate its specifications. Specifically, we explore the use of tabular and deep reinforcement learning approaches for synthesizing adversarial agents. We show that ado agents trained in this fashion are better than traditional falsification or testing techniques because they can generalize to ego agents and environments that differ from the original ego agent. We demonstrate the efficacy of our technique on two real-world case studies from the domain of self-driving cars.
Interactive Gibson Benchmark (iGibson 0.5): A Benchmark for Interactive Navigation in Cluttered Environments
Venue: arXiv cs.RO 2021
Year: 2021

We present Interactive Gibson Benchmark, the first comprehensive benchmark for training and evaluating Interactive Navigation: robot navigation strategies where physical interaction with objects is allowed and even encouraged to accomplish a task. For example, the robot can move objects if needed in order to clear a path leading to the goal location. Our benchmark comprises two novel elements: 1) a new experimental setup, the Interactive Gibson Environment (iGibson 0.5), which simulates high fidelity visuals of indoor scenes, and high fidelity physical dynamics of the robot and common objects found in these scenes; 2) a set of Interactive Navigation metrics which allows one to study the interplay between navigation and physical interaction. We present and evaluate multiple learning-based baselines in Interactive Gibson, and provide insights into regimes of navigation with different trade-offs between navigation path efficiency and disturbance of surrounding objects. We make our benchmark publicly available(https://sites.google.com/view/interactivegibsonenv) and encourage researchers from all disciplines in robotics (e.g. planning, learning, control) to propose, evaluate, and compare their Interactive Navigation solutions in Interactive Gibson.
A Formal Proof of PAC Learnability for Decision Stumps
Venue: arXiv cs.LG 2021
Year: 2021

We present a formal proof in Lean of probably approximately correct (PAC) learnability of the concept class of decision stumps. This classic result in machine learning theory derives a bound on error probabilities for a simple type of classifier. Though such a proof appears simple on paper, analytic and measure-theoretic subtleties arise when carrying it out fully formally. Our proof is structured so as to separate reasoning about deterministic properties of a learning function from proofs of measurability and analysis of probabilities.
Progressive Compressed Records: Taking a Byte out of Deep Learning Data
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning accelerators efficiently train over vast and growing amounts of data, placing a newfound burden on commodity networks and storage devices. A common approach to conserve bandwidth involves resizing or compressing data prior to training. We introduce Progressive Compressed Records (PCRs), a data format that uses compression to reduce the overhead of fetching and transporting data, effectively reducing the training time required to achieve a target accuracy. PCRs deviate from previous storage formats by combining progressive compression with an efficient storage layout to view a single dataset at multiple fidelities---all without adding to the total dataset size. We implement PCRs and evaluate them on a range of datasets, training tasks, and hardware architectures. Our work shows that: (i) the amount of compression a dataset can tolerate exceeds 50% of the original encoding for many DL training tasks; (ii) it is possible to automatically and efficiently select appropriate compression levels for a given task; and (iii) PCRs enable tasks to readily access compressed data at runtime---utilizing as little as half the training bandwidth and thus potentially doubling training speed.
Design and Challenges of Cloze-Style Reading Comprehension Tasks on Multiparty Dialogue
Venue: arXiv cs.CL 2021
Year: 2021

This paper analyzes challenges in cloze-style reading comprehension on multiparty dialogue and suggests two new tasks for more comprehensive predictions of personal entities in daily conversations. We first demonstrate that there are substantial limitations to the evaluation methods of previous work, namely that randomized assignment of samples to training and test data substantially decreases the complexity of cloze-style reading comprehension. According to our analysis, replacing the random data split with a chronological data split reduces test accuracy on previous single-variable passage completion task from 72\% to 34\%, that leaves much more room to improve. Our proposed tasks extend the previous single-variable passage completion task by replacing more character mentions with variables. Several deep learning models are developed to validate these three tasks. A thorough error analysis is provided to understand the challenges and guide the future direction of this research.
A Stealthy Hardware Trojan Exploiting the Architectural Vulnerability of Deep Learning Architectures: Input Interception Attack (IIA)
Venue: arXiv cs.CR 2021
Year: 2021

Deep learning architectures (DLA) have shown impressive performance in computer vision, natural language processing and so on. Many DLA make use of cloud computing to achieve classification due to the high computation and memory requirements. Privacy and latency concerns resulting from cloud computing has inspired the deployment of DLA on embedded hardware accelerators. To achieve short time-to-market and have access to global experts, state-of-the-art techniques of DLA deployment on hardware accelerators are outsourced to untrusted third parties. This outsourcing raises security concerns as hardware Trojans can be inserted into the hardware design of the mapped DLA of the hardware accelerator. We argue that existing hardware Trojan attacks highlighted in literature have no qualitative means how definite they are of the triggering of the Trojan. Also, most inserted Trojans show a obvious spike in the number of hardware resources utilized on the accelerator at the time of triggering the Trojan or when the payload is active. In this paper, we introduce a hardware Trojan attack called Input Interception Attack (IIA). In this attack, we make use of the statistical properties of layer-by-layer output to ensure that asides from being stealthy. Our IIA is able to trigger with some measure of definiteness. Moreover, this IIA attack is tested on DLA used to classify MNIST and Cifar-10 data sets. The attacked design utilizes approximately up to 2% more LUTs respectively compared to the un-compromised designs. Finally, this paper discusses potential defensive mechanisms that could be used to combat such hardware Trojans based attack in hardware accelerators for DLA.
Controlling a random population
Venue: arXiv cs.FL 2021
Year: 2021

Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is decidable and EXPTIME-complete in the adversarial setting, and posed as an open problem the stochastic setting, where the agent is represented by a Markov decision process. In this paper, we show that the stochastic control problem is decidable. Our solution makes significant uses of well quasi orders, of the max-flow min-cut theorem, and of the theory of regular cost functions. We introduce an intermediate problem of independence interest called the sequential flow problem and study its complexity.
Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
Venue: arXiv cs.DS 2021
Year: 2021

We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm can be made reversible and able to sample from a specified measure on partitions. Both of these properties are critical to some important applications and computational Bayesian statistics in general. Our proposal chain modifies the recently developed method called Recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the state space from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities. We demonstrate this method by sampling redistricting plans and find promising convergence results on several key observables of interest.
Increasing Robustness to Spurious Correlations using Forgettable Examples
Venue: arXiv cs.CL 2021
Year: 2021

Neural NLP models tend to rely on spurious correlations between labels and input features to perform their tasks. Minority examples, i.e., examples that contradict the spurious correlations present in the majority of data points, have been shown to increase the out-of-distribution generalization of pre-trained language models. In this paper, we first propose using example forgetting to find minority examples without prior knowledge of the spurious correlations present in the dataset. Forgettable examples are instances either learned and then forgotten during training or never learned. We empirically show how these examples are related to minorities in our training sets. Then, we introduce a new approach to robustify models by fine-tuning our models twice, first on the full training data and second on the minorities only. We obtain substantial improvements in out-of-distribution generalization when applying our approach to the MNLI, QQP, and FEVER datasets.
Multi-objectivization Inspired Metaheuristics for the Sum-of-the-Parts Combinatorial Optimization Problems
Venue: arXiv cs.NE 2021
Year: 2021

Multi-objectivization is a term used to describe strategies developed for optimizing single-objective problems by multi-objective algorithms. This paper focuses on multi-objectivizing the sum-of-the-parts combinatorial optimization problems, which include the traveling salesman problem, the unconstrained binary quadratic programming and other well-known combinatorial optimization problem. For a sum-of-the-parts combinatorial optimization problem, we propose to decompose its original objective into two sub-objectives with controllable correlation. Based on the decomposition method, two new multi-objectivization inspired single-objective optimization techniques called non-dominance search and non-dominance exploitation are developed, respectively. Non-dominance search is combined with two metaheuristics, namely iterated local search and iterated tabu search, while non-dominance exploitation is embedded within the iterated Lin-Kernighan metaheuristic. The resultant metaheuristics are called ILS+NDS, ITS+NDS and ILK+NDE, respectively. Empirical studies on some TSP and UBQP instances show that with appropriate correlation between the sub-objectives, there are more chances to escape from local optima when new starting solution is selected from the non-dominated solutions defined by the decomposed sub-objectives. Experimental results also show that ILS+NDS, ITS+NDS and ILK+NDE all significantly outperform their counterparts on most of the test instances.