OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchically Organized Latent Modules for Exploratory Search in Morphogenetic Systems
Venue: arXiv cs.LG 2021
Year: 2021

Self-organization of complex morphological patterns from local interactions is a fascinating phenomenon in many natural and artificial systems. In the artificial world, typical examples of such morphogenetic systems are cellular automata. Yet, their mechanisms are often very hard to grasp and so far scientific discoveries of novel patterns have primarily been relying on manual tuning and ad hoc exploratory search. The problem of automated diversity-driven discovery in these systems was recently introduced [26, 62], highlighting that two key ingredients are autonomous exploration and unsupervised representation learning to describe "relevant" degrees of variations in the patterns. In this paper, we motivate the need for what we call Meta-diversity search, arguing that there is not a unique ground truth interesting diversity as it strongly depends on the final observer and its motives. Using a continuous game-of-life system for experiments, we provide empirical evidences that relying on monolithic architectures for the behavioral embedding design tends to bias the final discoveries (both for hand-defined and unsupervisedly-learned features) which are unlikely to be aligned with the interest of a final end-user. To address these issues, we introduce a novel dynamic and modular architecture that enables unsupervised learning of a hierarchy of diverse representations. Combined with intrinsically motivated goal exploration algorithms, we show that this system forms a discovery assistant that can efficiently adapt its diversity search towards preferences of a user using only a very small amount of user feedback.
Spot the conversation: speaker diarisation in the wild
Venue: arXiv cs.SD 2021
Year: 2021

The goal of this paper is speaker diarisation of videos collected 'in the wild'. We make three key contributions. First, we propose an automatic audio-visual diarisation method for YouTube videos. Our method consists of active speaker detection using audio-visual methods and speaker verification using self-enrolled speaker models. Second, we integrate our method into a semi-automatic dataset creation pipeline which significantly reduces the number of hours required to annotate videos with diarisation labels. Finally, we use this pipeline to create a large-scale diarisation dataset called VoxConverse, collected from 'in the wild' videos, which we will release publicly to the research community. Our dataset consists of overlapping speech, a large and diverse speaker pool, and challenging background conditions.
"Most of" leads to undecidability: Failure of adding frequencies to LTL
Venue: arXiv cs.LO 2021
Year: 2021

Linear Temporal Logic (LTL) interpreted on finite traces is a robust specification framework popular in formal verification. However, despite the high interest in the logic in recent years, the topic of their quantitative extensions is not yet fully explored. The main goal of this work is to study the effect of adding weak forms of percentage constraints (e.g. that most of the positions in the past satisfy a given condition, or that sigma is the most-frequent letter occurring in the past) to fragments of LTL. Such extensions could potentially be used for the verification of influence networks or statistical reasoning. Unfortunately, as we prove in the paper, it turns out that percentage extensions of even tiny fragments of LTL have undecidable satisfiability and model-checking problems. Our undecidability proofs not only sharpen most of the undecidability results on logics with arithmetics interpreted on words known from the literature, but also are fairly simple. We also show that the undecidability can be avoided by restricting the allowed usage of the negation, and briefly discuss how the undecidability results transfer to first-order logic on words.
Supervisory Controller Synthesis for Non-terminating Processes is an Obliging Game
Venue: arXiv cs.LO 2021
Year: 2021

We present a new algorithm to solve the supervisory control problem over non-terminating processes modeled as $ω$-regular automata. A solution to this problem was obtained by Thistle in 1995 which uses complex manipulations of automata. We show a new solution to the problem through a reduction to obliging games, which, in turn, can be reduced to $ω$-regular reactive synthesis. Therefore, our reduction results in a symbolic algorithm based on manipulating sets of states using tools from reactive synthesis.
The Effect of Class Imbalance on Precision-Recall Curves
Venue: arXiv cs.LG 2021
Year: 2021

In this note I study how the precision of a classifier depends on the ratio $r$ of positive to negative cases in the test set, as well as the classifier's true and false positive rates. This relationship allows prediction of how the precision-recall curve will change with $r$, which seems not to be well known. It also allows prediction of how $F_β$ and the Precision Gain and Recall Gain measures of Flach and Kull (2015) vary with $r$.
Text Data Augmentation: Towards better detection of spear-phishing emails
Venue: arXiv cs.CL 2021
Year: 2021

Text data augmentation, i.e., the creation of new textual data from an existing text, is challenging. Indeed, augmentation transformations should take into account language complexity while being relevant to the target Natural Language Processing (NLP) task (e.g., Machine Translation, Text Classification). Initially motivated by an application of Business Email Compromise (BEC) detection, we propose a corpus and task agnostic augmentation framework used as a service to augment English texts within our company. Our proposal combines different methods, utilizing BERT language model, multi-step back-translation and heuristics. We show that our augmentation framework improves performances on several text classification tasks using publicly available models and corpora as well as on a BEC detection task. We also provide a comprehensive argumentation about the limitations of our augmentation framework.
Accuracy-Efficiency Trade-Offs and Accountability in Distributed ML Systems
Venue: arXiv cs.CY 2021
Year: 2021

Trade-offs between accuracy and efficiency pervade law, public health, and other non-computing domains, which have developed policies to guide how to balance the two in conditions of uncertainty. While computer science also commonly studies accuracy-efficiency trade-offs, their policy implications remain poorly examined. Drawing on risk assessment practices in the US, we argue that, since examining these trade-offs has been useful for guiding governance in other domains, we need to similarly reckon with these trade-offs in governing computer systems. We focus our analysis on distributed machine learning systems. Understanding the policy implications in this area is particularly urgent because such systems, which include autonomous vehicles, tend to be high-stakes and safety-critical. We 1) describe how the trade-off takes shape for these systems, 2) highlight gaps between existing US risk assessment standards and what these systems require to be properly assessed, and 3) make specific calls to action to facilitate accountability when hypothetical risks concerning the accuracy-efficiency trade-off become realized as accidents in the real world. We close by discussing how such accountability mechanisms encourage more just, transparent governance aligned with public values.
On Molecular Flow Velocity Meters
Venue: arXiv cs.IT 2021
Year: 2021

Flow velocity is an important characteristic of the fluidic mediums. In this paper, we introduce a molecular based flow velocity meter consisting of a molecule releasing node and a receiver that counts these molecules. We consider both flow velocity detection and estimation problems, which are employed in different applications. For the flow velocity detection, we obtain the maximum a posteriori (MAP) decision rule. To analyze the performance of the proposed flow velocity detector, we obtain the error probability, its Gaussian approximation and Chernoff information (CI) upper bound, and investigate the optimum and sub-optimum sampling times accordingly. We show that, for binary hypothesis, the sub-optimum sampling times using CI upper bound are the same. Further, the sub-optimum sampling times are close to the optimum sampling times. For the flow velocity estimation, we obtain the MAP and minimum mean square error (MMSE) estimators. We consider the mean square error (MSE) to investigate the error performance of the flow velocity estimators and obtain the Bayesian Cramer-Rao (BCR) and expected Cramer-Rao (ECR) lower bounds. Further, we obtain the optimum sampling times for each estimator. It is seen that the optimum sampling times for each estimator are nearly the same. The proposed flow velocity meter can be used to design a new modulation technique in molecular communication (MC), where information is encoded in the flow velocity of the medium instead of the concentration, type, or release time of the molecules. The setup and performance analysis of the proposed flow velocity detector and estimator for molecular communication system need further investigation.
Selective Dyna-style Planning Under Limited Model Capacity
Venue: arXiv cs.LG 2021
Year: 2021

In model-based reinforcement learning, planning with an imperfect model of the environment has the potential to harm learning progress. But even when a model is imperfect, it may still contain information that is useful for planning. In this paper, we investigate the idea of using an imperfect model selectively. The agent should plan in parts of the state space where the model would be helpful but refrain from using the model where it would be harmful. An effective selective planning mechanism requires estimating predictive uncertainty, which arises out of aleatoric uncertainty, parameter uncertainty, and model inadequacy, among other sources. Prior work has focused on parameter uncertainty for selective planning. In this work, we emphasize the importance of model inadequacy. We show that heteroscedastic regression can signal predictive uncertainty arising from model inadequacy that is complementary to that which is detected by methods designed for parameter uncertainty, indicating that considering both parameter uncertainty and model inadequacy may be a more promising direction for effective selective planning than either in isolation.
Refined Analysis of the Asymptotic Complexity of the Number Field Sieve
Venue: arXiv cs.CR 2021
Year: 2021

The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted $o(1)$ and called $ξ(N)$ throughout this paper, which tends to zero as the entry $N$ grows. The aim of this paper is to find optimal asymptotic choices of the parameters of NFS as $N$ grows, in order to minimize its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint. We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. One of the main outcomes of this analysis is that $ξ(N)$ has a very slow rate of convergence: We prove that it is equivalent to $4{\log}{\log}{\log}\,N/(3{\log}{\log}\,N)$. Moreover, $ξ(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $ξ$ and numerical experiments indicate that this series starts converging only for $N>\exp(\exp(25))$, far beyond the practical range of NFS. This raises doubts on the relevance of NFS running time estimates that are based on setting $ξ=0$ in the asymptotic formula.
EpiMob: Interactive Visual Analytics of Citywide Human Mobility Restrictions for Epidemic Control
Venue: arXiv cs.HC 2021
Year: 2021

The outbreak of coronavirus disease (COVID-19) has swept across more than 180 countries and territories since late January 2020. As a worldwide emergency response, governments have implemented various measures and policies, such as self-quarantine, travel restrictions, work from home, and regional lockdown, to control the spread of the epidemic. These countermeasures seek to restrict human mobility because COVID-19 is a highly contagious disease that is spread by human-to-human transmission. Medical experts and policymakers have expressed the urgency to effectively evaluate the outcome of human restriction policies with the aid of big data and information technology. Thus, based on big human mobility data and city POI data, an interactive visual analytics system called Epidemic Mobility (EpiMob) was designed in this study. The system interactively simulates the changes in human mobility and infection status in response to the implementation of a certain restriction policy or a combination of policies (e.g., regional lockdown, telecommuting, screening). Users can conveniently designate the spatial and temporal ranges for different mobility restriction policies. Then, the results reflecting the infection situation under different policies are dynamically displayed and can be flexibly compared and analyzed in depth. Multiple case studies consisting of interviews with domain experts were conducted in the largest metropolitan area of Japan (i.e., Greater Tokyo Area) to demonstrate that the system can provide insight into the effects of different human mobility restriction policies for epidemic control, through measurements and comparisons.
A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks
Venue: arXiv cs.AI 2021
Year: 2021

Dynamic Bayesian networks have been well explored in the literature as discrete-time models: however, their continuous-time extensions have seen comparatively little attention. In this paper, we propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence. Furthermore, we analyze and discuss the computational complexity of the best and worst cases for the proposed algorithm. Finally, we validate its performance using synthetic data, and we discuss its strengths and limitations comparing it with the score-based structure learning algorithm from Nodelman et al. (2003). We find the latter to be more accurate in learning networks with binary variables, while our constraint-based approach is more accurate with variables assuming more than two values. Numerical experiments confirm that score-based and constraint-based algorithms are comparable in terms of computation time.
CMPCC: Corridor-based Model Predictive Contouring Control for Aggressive Drone Flight
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we propose an efficient, receding horizon, local adaptive low-level planner as the middle layer between our original planner and controller. Our method is named as corridor-based model predictive contouring control (CMPCC) since it builds upon on MPCC and utilizes the flight corridor as hard safety constraints. It optimizes the flight aggressiveness and tracking accuracy simultaneously, thus improving our system's robustness by overcoming unmeasured disturbances. Our method features its online flight speed optimization, strict safety and feasibility, and real-time performance, and will be released as a low-level plugin for a large variety of quadrotor systems.
Computing a maximum clique in geometric superclasses of disk graphs
Venue: arXiv cs.CG 2021
Year: 2021

In the 90's Clark, Colbourn and Johnson wrote a seminal paper where they proved that maximum clique can be solved in polynomial time in unit disk graphs. Since then, the complexity of maximum clique in intersection graphs of d-dimensional (unit) balls has been investigated. For ball graphs, the problem is NP-hard, as shown by Bonamy et al. (FOCS '18). They also gave an efficient polynomial time approximation scheme (EPTAS) for disk graphs. However, the complexity of maximum clique in this setting remains unknown. In this paper, we show the existence of a polynomial time algorithm for a geometric superclass of unit disk graphs. Moreover, we give partial results toward obtaining an EPTAS for intersection graphs of convex pseudo-disks.
Adaptive Cascade Submodular Maximization
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we propose and study the cascade submodular maximization problem under the adaptive setting. The input of our problem is a set of items, each item is in a particular state (i.e., the marginal contribution of an item) which is drawn from a known probability distribution. However, we can not know its actual state before selecting it. As compared with existing studies on stochastic submodular maximization, one unique setting of our problem is that each item is associated with a continuation probability which represents the probability that one is allowed to continue to select the next item after selecting the current one. Intuitively, this term captures the externality of selecting one item to all its subsequent items in terms of the opportunity of being selected. Therefore, the actual set of items that can be selected by a policy depends on the specific ordering it adopts to select items, this makes our problem fundamentally different from classical submodular set optimization problems. Our objective is to identify the best sequence of selecting items so as to maximize the expected utility of the selected items. We propose a class of stochastic utility functions, \emph{adaptive cascade submodular functions}, and show that the objective functions in many practical application domains satisfy adaptive cascade submodularity. Then we develop a $0.12$ approximation algorithm to the adaptive cascade submodular maximization problem.
Deep learning of thermodynamics-aware reduced-order models from data
Venue: arXiv cs.CE 2021
Year: 2021

We present an algorithm to learn the relevant latent variables of a large-scale discretized physical system and predict its time evolution using thermodynamically-consistent deep neural networks. Our method relies on sparse autoencoders, which reduce the dimensionality of the full order model to a set of sparse latent variables with no prior knowledge of the coded space dimensionality. Then, a second neural network is trained to learn the metriplectic structure of those reduced physical variables and predict its time evolution with a so-called structure-preserving neural network. This data-based integrator is guaranteed to conserve the total energy of the system and the entropy inequality, and can be applied to both conservative and dissipative systems. The integrated paths can then be decoded to the original full-dimensional manifold and be compared to the ground truth solution. This method is tested with two examples applied to fluid and solid mechanics.
Reversible data hiding in encrypted images based on pixel prediction and multi-MSB planes rearrangement
Venue: arXiv cs.MM 2021
Year: 2021

Great concern has arisen in the field of reversible data hiding in encrypted images (RDHEI) due to the development of cloud storage and privacy protection. RDHEI is an effective technology that can embed additional data after image encryption, extract additional data error-free and reconstruct original images losslessly. In this paper, a high-capacity and fully reversible RDHEI method is proposed, which is based on pixel prediction and multi-MSB (most significant bit) planes rearrangement. First, the median edge detector (MED) predictor is used to calculate the predicted value. Next, unlike previous methods, in our proposed method, signs of prediction errors (PEs) are represented by one bit plane and absolute values of PEs are represented by other bit planes. Then, we divide bit planes into uniform blocks and non-uniform blocks, and rearrange these blocks. Finally, according to different pixel prediction schemes, different numbers of additional data are embedded adaptively. The experimental results prove that our method has higher embedding capacity compared with state-of-the-art RDHEI methods.
Supervised machine learning techniques for data matching based on similarity metrics
Venue: arXiv cs.LG 2021
Year: 2021

Businesses, governmental bodies and NGO's have an ever-increasing amount of data at their disposal from which they try to extract valuable information. Often, this needs to be done not only accurately but also within a short time frame. Clean and consistent data is therefore crucial. Data matching is the field that tries to identify instances in data that refer to the same real-world entity. In this study, machine learning techniques are combined with string similarity functions to the field of data matching. A dataset of invoices from a variety of businesses and organizations was preprocessed with a grouping scheme to reduce pair dimensionality and a set of similarity functions was used to quantify similarity between invoice pairs. The resulting invoice pair dataset was then used to train and validate a neural network and a boosted decision tree. The performance was compared with a solution from FISCAL Technologies as a benchmark against currently available deduplication solutions. Both the neural network and boosted decision tree showed equal to better performance.
BS4NN: Binarized Spiking Neural Networks with Temporal Coding and Learning
Venue: arXiv cs.NE 2021
Year: 2021

We recently proposed the S4NN algorithm, essentially an adaptation of backpropagation to multilayer spiking neural networks that use simple non-leaky integrate-and-fire neurons and a form of temporal coding known as time-to-first-spike coding. With this coding scheme, neurons fire at most once per stimulus, but the firing order carries information. Here, we introduce BS4NN, a modification of S4NN in which the synaptic weights are constrained to be binary (+1 or -1), in order to decrease memory (ideally, one bit per synapse) and computation footprints. This was done using two sets of weights: firstly, real-valued weights, updated by gradient descent, and used in the backward pass of backpropagation, and secondly, their signs, used in the forward pass. Similar strategies have been used to train (non-spiking) binarized neural networks. The main difference is that BS4NN operates in the time domain: spikes are propagated sequentially, and different neurons may reach their threshold at different times, which increases computational power. We validated BS4NN on two popular benchmarks, MNIST and Fashion-MNIST, and obtained reasonable accuracies for this sort of network (97.0% and 87.3% respectively) with a negligible accuracy drop with respect to real-valued weights (0.4% and 0.7%, respectively). We also demonstrated that BS4NN outperforms a simple BNN with the same architectures on those two datasets (by 0.2% and 0.9% respectively), presumably because it leverages the temporal dimension. The source codes of the proposed BS4NN are publicly available at https://github.com/SRKH/BS4NN.
Decoder Ties Do Not Affect the Error Exponent of the Memoryless Binary Symmetric Channel
Venue: arXiv cs.IT 2021
Year: 2021

The generalized Poor-Verdu error lower bound established in [1] for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.