OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Sorting with Persistent Comparison Errors
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of sorting $n$ elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two elements can be wrong with some fixed (small) probability $p$, and \emph{comparisons cannot be repeated}. Sorting perfectly in this model is impossible, and the objective is to minimize the \emph{dislocation} of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, \emph{maximum dislocation} and \emph{total dislocation} better than $Ω(\log n)$ and $Ω(n)$, respectively, regardless of its running time. In this paper, we present the first \emph{$O(n\log n)$-time} sorting algorithm that guarantees both \emph{$O(\log n)$ maximum dislocation} and \emph{$O(n)$ total dislocation} with high probability. Besides improving over the previous state-of-the art algorithms -- the best known algorithm had running time $\tilde{O}(n^{3/2})$ -- our result indicates that comparison errors do not make the problem computationally more difficult: a sequence with the best possible dislocation can be obtained in $O(n\log n)$ time and, even without comparison errors, $Ω(n\log n)$ time is necessary to guarantee such dislocation bounds. In order to achieve this optimal result, we solve two sub-problems, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having $O(\log n)$ maximum dislocation in such a way that the dislocation of the resulting sequence will still be $O(\log n)$. The other is how to simultaneously insert $m$ elements into an almost sorted sequence of $m$ different elements, such that the resulting sequence of $2m$ elements remains almost sorted.
One-Shot Learning using Mixture of Variational Autoencoders: a Generalization Learning approach
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning, even if it is very successful nowadays, traditionally needs very large amounts of labeled data to perform excellent on the classification task. In an attempt to solve this problem, the one-shot learning paradigm, which makes use of just one labeled sample per class and prior knowledge, becomes increasingly important. In this paper, we propose a new one-shot learning method, dubbed MoVAE (Mixture of Variational AutoEncoders), to perform classification. Complementary to prior studies, MoVAE represents a shift of paradigm in comparison with the usual one-shot learning methods, as it does not use any prior knowledge. Instead, it starts from zero knowledge and one labeled sample per class. Afterward, by using unlabeled data and the generalization learning concept (in a way, more as humans do), it is capable to gradually improve by itself its performance. Even more, if there are no unlabeled data available MoVAE can still perform well in one-shot learning classification. We demonstrate empirically the efficiency of our proposed approach on three datasets, i.e. the handwritten digits (MNIST), fashion products (Fashion-MNIST), and handwritten characters (Omniglot), showing that MoVAE outperforms state-of-the-art one-shot learning algorithms.
Toward Intelligent Autonomous Agents for Cyber Defense: Report of the 2017 Workshop by the North Atlantic Treaty Organization (NATO) Research Group IST-152-RTG
Venue: arXiv cs.CR 2018
Year: 2018

This report summarizes the discussions and findings of the Workshop on Intelligent Autonomous Agents for Cyber Defence and Resilience organized by the NATO research group IST-152-RTG. The workshop was held in Prague, Czech Republic, on 18-20 October 2017. There is a growing recognition that future cyber defense should involve extensive use of partially autonomous agents that actively patrol the friendly network, and detect and react to hostile activities rapidly (far faster than human reaction time), before the hostile malware is able to inflict major damage, evade friendly agents, or destroy friendly agents. This requires cyber-defense agents with a significant degree of intelligence, autonomy, self-learning, and adaptability. The report focuses on the following questions: In what computing and tactical environments would such an agent operate? What data would be available for the agent to observe or ingest? What actions would the agent be able to take? How would such an agent plan a complex course of actions? Would the agent learn from its experiences, and how? How would the agent collaborate with humans? How can we ensure that the agent will not take undesirable destructive actions? Is it possible to help envision such an agent with a simple example?
Achievable Information Rates for Nonlinear Fiber Communication via End-to-end Autoencoder Learning
Venue: arXiv cs.IT 2018
Year: 2018

Machine learning is used to compute achievable information rates (AIRs) for a simplified fiber channel. The approach jointly optimizes the input distribution (constellation shaping) and the auxiliary channel distribution to compute AIRs without explicit channel knowledge in an end-to-end fashion.
Handling Constraints in Combinatorial Interaction Testing in the presence of Multi Objective Particle Swarm and Multithreading
Venue: arXiv cs.SE 2018
Year: 2018

Context: Combinatorial testing strategies have lately received a lot of attention as a result of their diverse applications. In its simple form, a combinatorial strategy can reduce several input parameters (configurations) of a system into a small set based on their interaction (or combination). In practice, the input configurations of software systems are subjected to constraints, especially in case of highly configurable systems. To implement this feature within a strategy, many difficulties arise for construction. While there are many combinatorial interaction testing strategies nowadays, few of them support constraints. Objective: This paper presents a new strategy, to construct combinatorial interaction test suites in the presence of constraints. Method: The design and algorithms are provided in detail. To overcome the multi-judgment criteria for an optimal solution, the multi-objective particle swarm optimization and multithreading are used. The strategy and its associated algorithms are evaluated extensively using different benchmarks and comparisons. Results: Our results are promising as the evaluation results showed the efficiency and performance of each algorithm in the strategy. The benchmarking results also showed that the strategy can generate constrained test suites efficiently as compared to state-of-the-art strategies. Conclusion: The proposed strategy can form a new way for constructing of constrained combinatorial interaction test suites. The strategy can form a new and effective base for future implementations.
Lightweight Adaptive Mixture of Neural and N-gram Language Models
Venue: arXiv cs.CL 2018
Year: 2018

It is often the case that the best performing language model is an ensemble of a neural language model with n-grams. In this work, we propose a method to improve how these two models are combined. By using a small network which predicts the mixture weight between the two models, we adapt their relative importance at each time step. Because the gating network is small, it trains quickly on small amounts of held out data, and does not add overhead at scoring time. Our experiments carried out on the One Billion Word benchmark show a significant improvement over the state of the art ensemble without retraining of the basic modules.
Learning Semantic Textual Similarity from Conversations
Venue: arXiv cs.CL 2018
Year: 2018

We present a novel approach to learn representations for sentence-level semantic similarity using conversational data. Our method trains an unsupervised model to predict conversational input-response pairs. The resulting sentence embeddings perform well on the semantic textual similarity (STS) benchmark and SemEval 2017's Community Question Answering (CQA) question similarity subtask. Performance is further improved by introducing multitask training combining the conversational input-response prediction task and a natural language inference task. Extensive experiments show the proposed model achieves the best performance among all neural models on the STS benchmark and is competitive with the state-of-the-art feature engineered and mixed systems in both tasks.
Phrase-Based & Neural Unsupervised Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

Machine translation systems achieve near human-level performance on some languages, yet their effectiveness strongly relies on the availability of large amounts of parallel sentences, which hinders their applicability to the majority of language pairs. This work investigates how to learn to translate when having access to only large monolingual corpora in each language. We propose two model variants, a neural and a phrase-based model. Both versions leverage a careful initialization of the parameters, the denoising effect of language models and automatic generation of parallel data by iterative back-translation. These models are significantly better than methods from the literature, while being simpler and having fewer hyper-parameters. On the widely used WMT'14 English-French and WMT'16 German-English benchmarks, our models respectively obtain 28.1 and 25.2 BLEU points without using a single parallel sentence, outperforming the state of the art by more than 11 BLEU points. On low-resource languages like English-Urdu and English-Romanian, our methods achieve even better results than semi-supervised and supervised approaches leveraging the paucity of available bitexts. Our code for NMT and PBSMT is publicly available.
Assessing Combinatorial Design for Analyzing System Performance of a Computer Network
Venue: arXiv cs.NI 2018
Year: 2018

Generally, combinatorial design concerns with the arrangement of a finite set of elements into patterns (subsets, words, arrays) according to specified rules. The usefulness of this design method is that the number of input combination can be reduced dramatically but all of them are covered by the combinatorial set. This paper presents the application of this design method in communication networks. Communication engineers can use this novel method to generate test cases for producing a cost-effective set of experiments to recognize the factors that have the least and most impact on the system's performance. A well-known scenario is used for the purpose of the experiment and five factors with different values are chosen to qualify their effect on the network performance. The experimental set is generated using combinatorial design method and then it is been used to analyze the effect of each factor. The experiments showed the effectiveness of the method to be used for analyzing the effect of factors on the communication network.
Robust Probabilistic Analysis of Transmission Power Systems based on Equivalent Circuit Formulation
Venue: arXiv cs.SY 2018
Year: 2018

Recent advances in steady-state analysis of power systems have introduced the equivalent split-circuit approach and corresponding continuation methods that can reliably find the correct physical solution of large-scale power system problems. The improvement in robustness provided by these developments are the basis for improvements in other fields of power system research. Probabilistic Power Flow studies are one of the areas of impact. This paper will describe a Simple Random Sampling Monte Carlo approach for probabilistic contingency analyses of transmission line power systems. The results are compared with those from Monte Carlo simulations using a standard power flow tool. Lastly, probabilistic contingency studies on two publicly available power system cases are presented.
Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey
Venue: arXiv cs.AI 2018
Year: 2018

The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What safe replacement means depends on the intended application of the ontology. If, for example, it is used to query data, then the answers to any relevant ontology-mediated query should be the same over any relevant data set; if, in contrast, the ontology is used for conceptual reasoning, then the entailed subsumptions between concept expressions should coincide. This gives rise to different notions of ontology inseparability such as query inseparability and concept inseparability, which generalize corresponding notions of conservative extensions. We survey results on various notions of inseparability in the context of description logic ontologies, discussing their applications, useful model-theoretic characterizations, algorithms for determining whether two ontologies are inseparable (and, sometimes, for computing the difference between them if they are not), and the computational complexity of this problem.
Decidability of Timed Communicating Automata
Venue: arXiv cs.FL 2018
Year: 2018

We study the reachability problem for networks of timed communicating processes. Each process is a timed automaton communicating with other processes by exchanging messages over unbounded FIFO channels. Messages carry clocks which are checked at the time of transmission and reception with suitable timing constraints. Each automaton can only access its set of local clocks and message clocks of sent/received messages. Time is dense and all clocks evolve at the same rate. Our main contribution is a complete characterisation of decidable and undecidable communication topologies generalising and unifying previous work. From a technical point of view, we use quantifier elimination and a reduction to counter automata with registers.
Joint entity recognition and relation extraction as a multi-head selection problem
Venue: arXiv cs.CL 2018
Year: 2018

State-of-the-art models for joint entity recognition and relation extraction strongly rely on external natural language processing (NLP) tools such as POS (part-of-speech) taggers and dependency parsers. Thus, the performance of such joint models depends on the quality of the features obtained from these NLP tools. However, these features are not always accurate for various languages and contexts. In this paper, we propose a joint neural model which performs entity recognition and relation extraction simultaneously, without the need of any manually extracted features or the use of any external tool. Specifically, we model the entity recognition task using a CRF (Conditional Random Fields) layer and the relation extraction task as a multi-head selection problem (i.e., potentially identify multiple relations for each entity). We present an extensive experimental setup, to demonstrate the effectiveness of our method using datasets from various contexts (i.e., news, biomedical, real estate) and languages (i.e., English, Dutch). Our model outperforms the previous neural models that use automatically extracted features, while it performs within a reasonable margin of feature-based neural models, or even beats them.
Social Bots for Online Public Health Interventions
Venue: arXiv cs.SI 2018
Year: 2018

According to the Center for Disease Control and Prevention, in the United States hundreds of thousands initiate smoking each year, and millions live with smoking-related dis- eases. Many tobacco users discuss their habits and preferences on social media. This work conceptualizes a framework for targeted health interventions to inform tobacco users about the consequences of tobacco use. We designed a Twitter bot named Notobot (short for No-Tobacco Bot) that leverages machine learning to identify users posting pro-tobacco tweets and select individualized interventions to address their interest in tobacco use. We searched the Twitter feed for tobacco-related keywords and phrases, and trained a convolutional neural network using over 4,000 tweets dichotomously manually labeled as either pro- tobacco or not pro-tobacco. This model achieves a 90% recall rate on the training set and 74% on test data. Users posting pro- tobacco tweets are matched with former smokers with similar interests who posted anti-tobacco tweets. Algorithmic matching, based on the power of peer influence, allows for the systematic delivery of personalized interventions based on real anti-tobacco tweets from former smokers. Experimental evaluation suggests that our system would perform well if deployed. This research offers opportunities for public health researchers to increase health awareness at scale. Future work entails deploying the fully operational Notobot system in a controlled experiment within a public health campaign.
A Cell-Division Search Technique for Inversion with Application to Picture-Discovery and Magnetotellurics
Venue: arXiv cs.NE 2018
Year: 2018

Solving inverse problems in natural sciences often requires a search pro- cess to find explanatory models that match collected field data. Inverse problems are often under-determined meaning that there are many poten- tial explanatory models for the same data. In such cases using stochastic search, through providing multiple solutions, can help characterise which model features that are most persistent and therefore likely to be real. Unfortunately, in some fields, large parameter spaces can make stochas- tic search intractable. In this work we improve upon previous work by defining a compact and expressive representation and search process able to describe and discover two and three dimensional spatial models. The search process takes place in stages starting with greedy search, followed by alternating stages of evolutionary search and a novel model-splitting process inspired by cell-division. We apply this framework to two prob- lems - magnetotellurics and picture discovery. We show that our improved representation and search process is able to produce detailed models with low error residuals.
Variational Inference In Pachinko Allocation Machines
Venue: arXiv cs.CL 2018
Year: 2018

The Pachinko Allocation Machine (PAM) is a deep topic model that allows representing rich correlation structures among topics by a directed acyclic graph over topics. Because of the flexibility of the model, however, approximate inference is very difficult. Perhaps for this reason, only a small number of potential PAM architectures have been explored in the literature. In this paper we present an efficient and flexible amortized variational inference method for PAM, using a deep inference network to parameterize the approximate posterior distribution in a manner similar to the variational autoencoder. Our inference method produces more coherent topics than state-of-art inference methods for PAM while being an order of magnitude faster, which allows exploration of a wider range of PAM architectures than have previously been studied.
Finer Tight Bounds for Coloring on Clique-Width
Venue: arXiv cs.CC 2018
Year: 2018

We revisit the complexity of the classical $k$-Coloring problem parameterized by clique-width. This is a very well-studied problem that becomes highly intractable when the number of colors $k$ is large. However, much less is known on its complexity for small, concrete values of $k$. In this paper, we completely determine the complexity of $k$-Coloring parameterized by clique-width for any fixed $k$, under the SETH. Specifically, we show that for all $k\ge 3,ε>0$, $k$-Coloring cannot be solved in time $O^*((2^k-2-ε)^{cw})$, and give an algorithm running in time $O^*((2^k-2)^{cw})$. Thus, if the SETH is true, $2^k-2$ is the "correct" base of the exponent for every $k$. Along the way, we also consider the complexity of $k$-Coloring parameterized by the related parameter modular treewidth ($mtw$). In this case we show that the "correct" running time, under the SETH, is $O^*({k\choose \lfloor k/2\rfloor}^{mtw})$. If we base our results on a weaker assumption (the ETH), they imply that $k$-Coloring cannot be solved in time $n^{o(cw)}$, even on instances with $O(\log n)$ colors.
Capacity of Multiple One-Bit Transceivers in a Rayleigh Environment
Venue: arXiv cs.IT 2018
Year: 2018

We analyze the channel capacity of a system with a large number of one-bit transceivers in a classical Rayleigh environment with perfect channel information at the receiver. With $M$ transmitters and $N=αM$ receivers, we derive an expression of the capacity per transmitter $\mathcal{C}$, where $\mathcal{C}\leq\min(1,α)$, as a function of $α$ and signal-to-noise ratio (SNR) $ρ$, when $M\to\infty$. We show that our expression is a good approximation for small $M$, and provide simple approximations of $\mathcal{C}$ for various ranges of $α$ and SNR $ρ$. We conclude that at high SNR, $\mathcal{C}$ reaches its upper limit of one only if the ratio $α>1.24$. Expressions for determining when $\mathcal{C}$ "saturates" as a function of $α$ and $ρ$ are given.
Additive Number Theory via Approximation by Regular Languages
Venue: arXiv cs.FL 2018
Year: 2018

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 25 is the sum of at most three natural numbers whose base-2 representation has an equal number of 0's and 1's.
A 2/3-Approximation Algorithm for Vertex-weighted Matching in Bipartite Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We consider the maximum vertex-weighted matching problem (MVM), in which non-negative weights are assigned to the vertices of a graph, the weight of a matching is the sum of the weights of the matched vertices, and we are required to compute a matching of maximum weight. We describe an exact algorithm for MVM with $O(|V|\, |E|)$ time complexity, and then we design a $2/3$-approximation algorithm for MVM on bipartite graphs by restricting the length of augmenting paths to at most three. The latter algorithm has time complexity $O(|E| + |V| \log |V|)$. The approximation algorithm solves two MVM problems on bipartite graphs, each with weights only on one vertex part, and then finds a matching from these two matchings using the Mendelsohn-Dulmage Theorem. The approximation ratio of the algorithm is obtained by considering failed vertices, i.e., vertices that the approximation algorithm fails to match but the exact algorithm does. We show that at every step of the algorithm there are two distinct heavier vertices that we can charge each failed vertex to. We have implemented the $2/3$-approximation algorithm for MVM and compare it with four other algorithms: an exact MEM algorithm, the exact MVM algorithm, a $1/2$-approximation algorithm for MVM, and a scaling-based $(1-ε)$-approximation algorithm for MEM. We also show that MVM problems should not be first transformed to MEM problems and solved using exact algorithms for the latter, since this transformation can increase runtimes by several orders of magnitude.