OpenRaiser/Intern-Atlas huggingface dataset:
The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities
Venue: arXiv cs.NE 2019
Year: 2019

Biological evolution provides a creative fount of complex and subtle adaptations, often surprising the scientists who discover them. However, because evolution is an algorithmic process that transcends the substrate in which it occurs, evolution's creativity is not limited to nature. Indeed, many researchers in the field of digital evolution have observed their evolving algorithms and organisms subverting their intentions, exposing unrecognized bugs in their code, producing unexpected adaptations, or exhibiting outcomes uncannily convergent with ones in nature. Such stories routinely reveal creativity by evolution in these digital worlds, but they rarely fit into the standard scientific narrative. Instead they are often treated as mere obstacles to be overcome, rather than results that warrant study in their own right. The stories themselves are traded among researchers through oral tradition, but that mode of information transmission is inefficient and prone to error and outright loss. Moreover, the fact that these stories tend to be shared only among practitioners means that many natural scientists do not realize how interesting and lifelike digital organisms are and how natural their evolution can be. To our knowledge, no collection of such anecdotes has been published before. This paper is the crowd-sourced product of researchers in the fields of artificial life and evolutionary computation who have provided first-hand accounts of such cases. It thus serves as a written, fact-checked collection of scientifically important and even entertaining stories. In doing so we also present here substantial evidence that the existence and importance of evolutionary surprises extends beyond the natural world, and may indeed be a universal property of all complex evolving systems.
Detecting Adversarial Examples via Neural Fingerprinting
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural networks are vulnerable to adversarial examples, which dramatically alter model output using small input changes. We propose Neural Fingerprinting, a simple, yet effective method to detect adversarial examples by verifying whether model behavior is consistent with a set of secret fingerprints, inspired by the use of biometric and cryptographic signatures. The benefits of our method are that 1) it is fast, 2) it is prohibitively expensive for an attacker to reverse-engineer which fingerprints were used, and 3) it does not assume knowledge of the adversary. In this work, we pose a formal framework to analyze fingerprints under various threat models, and characterize Neural Fingerprinting for linear models. For complex neural networks, we empirically demonstrate that Neural Fingerprinting significantly improves on state-of-the-art detection mechanisms by detecting the strongest known adversarial attacks with 98-100% AUC-ROC scores on the MNIST, CIFAR-10 and MiniImagenet (20 classes) datasets. In particular, the detection accuracy of Neural Fingerprinting generalizes well to unseen test-data under various black- and whitebox threat models, and is robust over a wide range of hyperparameters and choices of fingerprints.
Linear-Time In-Place DFS and BFS on the Word RAM
Venue: arXiv cs.DS 2019
Year: 2019

We present an in-place depth first search (DFS) and an in-place breadth first search (BFS) that runs on a word RAM in linear time such that, if the adjacency arrays of the input graph are given in a sorted order, the input is restored after running the algorithm. To obtain our results we use properties of the representation used to store the given graph and show several linear-time in-place graph transformations from one representation into another.
A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
Venue: arXiv cs.DS 2019
Year: 2019

Despite rapid recent progress towards the development of quantum computers capable of providing computational advantages over classical computers, it seems likely that such computers will, initially at least, be required to run in a hybrid quantum-classical regime. This realisation has led to interest in hybrid quantum-classical algorithms allowing, for example, quantum computers to solve large problems despite having very limited numbers of qubits. Here we propose a hybrid paradigm for quantum annealers with the goal of mitigating a different limitation of such devices: the need to embed problem instances within the (often highly restricted) connectivity graph of the annealer. This embedding process can be costly to perform and may destroy any computational speedup. In order to solve many practical problems, it is moreover necessary to perform many, often related, such embeddings. We will show how, for such problems, a raw speedup that is negated by the embedding time can nonetheless be exploited to give a real speedup. As a proof-of-concept example we present an in-depth case study of a simple problem based on the maximum weight independent set problem. Although we do not observe a quantum speedup experimentally, the advantage of the hybrid approach is robustly verified, showing how a potential quantum speedup may be exploited and encouraging further efforts to apply the approach to problems of more practical interest.
Extended Affinity Propagation: Global Discovery and Local Insights
Venue: arXiv cs.LG 2019
Year: 2019

We propose a new clustering algorithm, Extended Affinity Propagation, based on pairwise similarities. Extended Affinity Propagation is developed by modifying Affinity Propagation such that the desirable features of Affinity Propagation, e.g., exemplars, reasonable computational complexity and no need to specify number of clusters, are preserved while the shortcomings, e.g., the lack of global structure discovery, that limit the applicability of Affinity Propagation are overcome. Extended Affinity Propagation succeeds not only in achieving this goal but can also provide various additional insights into the internal structure of the individual clusters, e.g., refined confidence values, relative cluster densities and local cluster strength in different regions of a cluster, which are valuable for an analyst. We briefly discuss how these insights can help in easily tuning the hyperparameters. We also illustrate these desirable features and the performance of Extended Affinity Propagation on various synthetic and real world datasets.
Robustness to incorrect priors in partially observed stochastic control
Venue: arXiv cs.SY 2019
Year: 2019

We study the continuity properties of optimal solutions to stochastic control problems with respect to initial probability measures and applications of these to the robustness of optimal control policies applied to systems with incomplete or incorrect priors. It is shown that for single and multi-stage optimal cost problems, continuity and robustness cannot be established under weak convergence or Wasserstein convergence in general, but that the optimal cost is continuous in the priors under the convergence in total variation under mild conditions. By imposing further assumptions on the measurement models, robustness and continuity also hold under weak convergence of priors. We thus obtain robustness results and bounds on the mismatch error that occurs due to the application of a control policy which is designed for an incorrectly estimated prior in terms of a distance measure between the true prior and the incorrect one. Positive and negative practical implications of these results in empirical learning for stochastic control will be presented, where almost surely weak convergence of i.i.d. empirical measures occurs but stronger notions of convergence, such as total variation convergence, in general, do not.
Bad Smells in Software Analytics Papers
Venue: arXiv cs.SE 2019
Year: 2019

CONTEXT: There has been a rapid growth in the use of data analytics to underpin evidence-based software engineering. However the combination of complex techniques, diverse reporting standards and poorly understood underlying phenomena are causing some concern as to the reliability of studies. OBJECTIVE: Our goal is to provide guidance for producers and consumers of software analytics studies (computational experiments and correlation studies). METHOD: We propose using "bad smells", i.e., surface indications of deeper problems and popular in the agile software community and consider how they may be manifest in software analytics studies. RESULTS: We list 12 "bad smells" in software analytics papers (and show their impact by examples). CONCLUSIONS: We believe the metaphor of bad smell is a useful device. Therefore we encourage more debate on what contributes to the validty of software analytics studies (so we expect our list will mature over time).
Smartphone picture organization: A hierarchical approach
Venue: arXiv cs.CV 2019
Year: 2019

We live in a society where the large majority of the population has a camera-equipped smartphone. In addition, hard drives and cloud storage are getting cheaper and cheaper, leading to a tremendous growth in stored personal photos. Unlike photo collections captured by a digital camera, which typically are pre-processed by the user who organizes them into event-related folders, smartphone pictures are automatically stored in the cloud. As a consequence, photo collections captured by a smartphone are highly unstructured and because smartphones are ubiquitous, they present a larger variability compared to pictures captured by a digital camera. To solve the need of organizing large smartphone photo collections automatically, we propose here a new methodology for hierarchical photo organization into topics and topic-related categories. Our approach successfully estimates latent topics in the pictures by applying probabilistic Latent Semantic Analysis, and automatically assigns a name to each topic by relying on a lexical database. Topic-related categories are then estimated by using a set of topic-specific Convolutional Neuronal Networks. To validate our approach, we ensemble and make public a large dataset of more than 8,000 smartphone pictures from 10 persons. Experimental results demonstrate better user satisfaction with respect to state of the art solutions in terms of organization.
Linear logic in normed cones: probabilistic coherence spaces and beyond
Venue: arXiv cs.LO 2019
Year: 2019

Ehrhard, Pagani and Tasson proposed a model of probabilistic functional programming in a category of normed positive cones and stable measurable cone maps, which can be seen as a coordinate-free generalization of probabilistic coherence spaces. However, unlike the case of probabilistic coherence spaces, it remained unclear if the model could be refined to a model of classical linear logic. In this work we consider a somewhat similar category which gives indeed a coordinate-free model of full propositional linear logic with nondegenerate interpretation of additives and sound interpretation of exponentials. Objects are dual pairs of normed cones satisfying certain specific completeness properties, such as existence of norm-bounded monotone weak limits, and morphisms are bounded (adjointable) positive maps. Norms allow us a distinct interpretation of dual additive connectives as product and coproduct. Exponential connectives are modelled using real analytic functions and distributions that have representations as power series with positive coefficients. Unlike the familiar case of probabilistic coherence spaces, there is no reference or need for a preferred basis; in this sense the model is invariant. Probabilistic coherence spaces form a full subcategory, whose objects, seen as posets, are lattices. Thus we get a model fitting in the tradition of interpreting linear logic in a linear algebraic setting, which arguably is free from the drawbacks of its predecessors. Relations with constructions of Ehrhard, Pagani and Tasson's work are left for future research.
Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
Venue: arXiv cs.FL 2019
Year: 2019

We consider decision problems for relations over finite and infinite words defined by finite automata. We prove that the equivalence problem for binary deterministic rational relations over infinite words is undecidable in contrast to the case of finite words, where the problem is decidable. Furthermore, we show that it is decidable in doubly exponential time for an automatic relation over infinite words whether it is a recognizable relation. We also revisit this problem in the context of finite words and improve the complexity of the decision procedure to single exponential time. The procedure is based on a polynomial time regularity test for deterministic visibly pushdown automata, which is a result of independent interest.
Multimodal Sentiment Analysis: Addressing Key Issues and Setting up the Baselines
Venue: arXiv cs.CL 2019
Year: 2019

We compile baselines, along with dataset split, for multimodal sentiment analysis. In this paper, we explore three different deep-learning based architectures for multimodal sentiment classification, each improving upon the previous. Further, we evaluate these architectures with multiple datasets with fixed train/test partition. We also discuss some major issues, frequently ignored in multimodal sentiment analysis research, e.g., role of speaker-exclusive models, importance of different modalities, and generalizability. This framework illustrates the different facets of analysis to be considered while performing multimodal sentiment analysis and, hence, serves as a new benchmark for future research in this emerging field.
A modification of the CSP algorithm for infinite languages
Venue: arXiv cs.CC 2019
Year: 2019

Constraint Satisfaction Problem on finite sets is known to be NP-complete in general but certain restrictions on the constraint language can ensure tractability. It was proved that if a constraint language has a weak near unanimity polymorphism then the corresponding constraint satisfaction problem is tractable, otherwise it is NP-complete. In the paper we present a modification of the algorithm that works in polynomial time even for infinite constraint languages.
Dynamic Filtering with Large Sampling Field for ConvNets
Venue: arXiv cs.CV 2019
Year: 2019

We propose a dynamic filtering strategy with large sampling field for ConvNets (LS-DFN), where the position-specific kernels learn from not only the identical position but also multiple sampled neighbor regions. During sampling, residual learning is introduced to ease training and an attention mechanism is applied to fuse features from different samples. Such multiple samples enlarge the kernels' receptive fields significantly without requiring more parameters. While LS-DFN inherits the advantages of DFN, namely avoiding feature map blurring by position-wise kernels while keeping translation invariance, it also efficiently alleviates the overfitting issue caused by much more parameters than normal CNNs. Our model is efficient and can be trained end-to-end via standard back-propagation. We demonstrate the merits of our LS-DFN on both sparse and dense prediction tasks involving object detection, semantic segmentation, and flow estimation. Our results show LS-DFN enjoys stronger recognition abilities in object detection and semantic segmentation tasks on VOC benchmark and sharper responses in flow estimation on FlyingChairs dataset compared to strong baselines.
Video Object Segmentation with Language Referring Expressions
Venue: arXiv cs.CV 2019
Year: 2019

Most state-of-the-art semi-supervised video object segmentation methods rely on a pixel-accurate mask of a target object provided for the first frame of a video. However, obtaining a detailed segmentation mask is expensive and time-consuming. In this work we explore an alternative way of identifying a target object, namely by employing language referring expressions. Besides being a more practical and natural way of pointing out a target object, using language specifications can help to avoid drift as well as make the system more robust to complex dynamics and appearance variations. Leveraging recent advances of language grounding models designed for images, we propose an approach to extend them to video data, ensuring temporally coherent predictions. To evaluate our method we augment the popular video object segmentation benchmarks, DAVIS'16 and DAVIS'17 with language descriptions of target objects. We show that our language-supervised approach performs on par with the methods which have access to a pixel-level mask of the target object on DAVIS'16 and is competitive to methods using scribbles on the challenging DAVIS'17 dataset.
A Review of Situation Awareness Assessment Approaches in Aviation Environments
Venue: arXiv cs.HC 2019
Year: 2019

Situation awareness (SA) is an important constituent in human information processing and essential in pilots' decision-making processes. Acquiring and maintaining appropriate levels of SA is critical in aviation environments as it affects all decisions and actions taking place in flights and air traffic control. This paper provides an overview of recent measurement models and approaches to establishing and enhancing SA in aviation environments. Many aspects of SA are examined including the classification of SA techniques into six categories, and different theoretical SA models from individual, to shared or team, and to distributed or system levels. Quantitative and qualitative perspectives pertaining to SA methods and issues of SA for unmanned vehicles are also addressed. Furthermore, future research directions regarding SA assessment approaches are raised to deal with shortcomings of the existing state-of-the-art methods in the literature.
Distributed Mechanism Design for Multicast Transmission
Venue: arXiv cs.GT 2019
Year: 2019

In the standard Mechanism Design framework (Hurwicz-Reiter), there is a central authority that gathers agents' messages and subsequently determines the allocation and tax for each agent. We consider a scenario where, due to communication overhead and other constraints, such broadcasting of messages to a central authority cannot take place. Instead, only local message exchange is allowed between agents. As a result, each agent should be able to determine her own allocation and tax based on the messages in the local neighborhood, as defined by a given message graph describing the communication constraints. This scenario gives rise to a novel research direction that we call "Distributed Mechanism Design". In this paper, we propose such a distributed mechanism for the problem of rate allocation in a multicast transmission network. The proposed mechanism fully implements the optimal allocation in Nash equilibria and its message space dimension is linear with respect to the number of agents in the network.
Pando: Personal Volunteer Computing in Browsers
Venue: arXiv cs.DC 2019
Year: 2019

The large penetration and continued growth in ownership of personal electronic devices represents a freely available and largely untapped source of computing power. To leverage those, we present Pando, a new volunteer computing tool based on a declarative concurrent programming model and implemented using JavaScript, WebRTC, and WebSockets. This tool enables a dynamically varying number of failure-prone personal devices contributed by volunteers to parallelize the application of a function on a stream of values, by using the devices' browsers. We show that Pando can provide throughput improvements compared to a single personal device, on a variety of compute-bound applications including animation rendering and image processing. We also show the flexibility of our approach by deploying Pando on personal devices connected over a local network, on Grid5000, a French-wide computing grid in a virtual private network, and seven PlanetLab nodes distributed in a wide area network over Europe.
Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we are interested in bounding the number of instructions taken to process transactions. The main result is a multiversion transactional system that supports constant delay (extra instructions beyond running in isolation) for all read-only transactions, delay equal to the number of processes for writing transactions that are not concurrent with other writers, and lock-freedom for concurrent writers. The system supports precise garbage collection in that versions are identified for collection as soon as the last transaction releases them. As far as we know these are first results that bound delays for multiple readers and even a single writer. The approach is particularly useful in situations where read-transactions dominate write transactions, or where write transactions come in as streams or batches and can be processed by a single writer (possibly in parallel). The approach is based on using functional data structures to support multiple versions, and an efficient solution to the Version Maintenance (VM) problem for acquiring, updating and releasing versions. Our solution to the VM problem is precise, safe and wait-free (PSWF). We experimentally validate our approach by applying it to balanced tree data structures for maintaining ordered maps. We test the transactional system using multiple algorithms for the VM problem, including our PSWF VM algorithm, and implementations with weaker guarantees based on epochs, hazard pointers, and read-copy-update. To evaluate the functional data structure for concurrency and multi-versioning, we implement batched updates for functional tree structures and compare the performance with state-of-the-art concurrent data structures for balanced trees. The experiments indicate our approach works well in practice over a broad set of criteria.
A Curry-Howard Approach to Church's Synthesis
Venue: arXiv cs.LO 2019
Year: 2019

Church's synthesis problem asks whether there exists a finite-state stream transducer satisfying a given input-output specification. For specifications written in Monadic Second-Order Logic (MSO) over infinite words, Church's synthesis can theoretically be solved algorithmically using automata and games. We revisit Church's synthesis via the Curry-Howard correspondence by introducing SMSO, an intuitionistic variant of MSO over infinite words, which is shown to be sound and complete w.r.t. synthesis thanks to an automata-based realizability model.