OpenRaiser/Intern-Atlas huggingface dataset:
Pool-Based Sequential Active Learning for Regression
Venue: arXiv cs.LG 2018
Year: 2018

Active learning is a machine learning approach for reducing the data labeling effort. Given a pool of unlabeled samples, it tries to select the most useful ones to label so that a model built from them can achieve the best possible performance. This paper focuses on pool-based sequential active learning for regression (ALR). We first propose three essential criteria that an ALR approach should consider in selecting the most useful unlabeled samples: informativeness, representativeness, and diversity, and compare four existing ALR approaches against them. We then propose a new ALR approach using passive sampling, which considers both the representativeness and the diversity in both the initialization and subsequent iterations. Remarkably, this approach can also be integrated with other existing ALR approaches in the literature to further improve the performance. Extensive experiments on 11 UCI, CMU StatLib, and UFL Media Core datasets from various domains verified the effectiveness of our proposed ALR approaches.
A Cognitive Approach to Real-time Rescheduling using SOAR-RL
Venue: arXiv cs.AI 2018
Year: 2018

Ensuring flexible and efficient manufacturing of customized products in an increasing dynamic and turbulent environment without sacrificing cost effectiveness, product quality and on-time delivery has become a key issue for most industrial enterprises. A promising approach to cope with this challenge is the integration of cognitive capabilities in systems and processes with the aim of expanding the knowledge base used to perform managerial and operational tasks. In this work, a novel approach to real-time rescheduling is proposed in order to achieve sustainable improvements in flexibility and adaptability of production systems through the integration of artificial cognitive capabilities, involving perception, reasoning/learning and planning skills. Moreover, an industrial example is discussed where the SOAR cognitive architecture capabilities are integrated in a software prototype, showing that the approach enables the rescheduling system to respond to events in an autonomic way, and to acquire experience through intensive simulation while performing repair tasks.
Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries
Venue: arXiv cs.DC 2018
Year: 2018

This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries on the tree, in addition to non-blocking algorithms for Insert, Delete and Find, using single-word Compare-and-Swap (CAS). The implementation is linearizable and tolerates any number of crash failures. Insert and Delete operations that operate on different parts of the tree run fully in parallel (without any interference with one another). We employ a lightweight helping mechanism, where each Insert, Delete and Find operation helps only update operations that affect the local neighbourhood of the leaf it arrives at. Similarly, a Scan helps only those updates taking place on nodes of the part of the tree it traverses, and therefore Scans operating on different parts of the tree do not interfere with one another. Our implementation works in a dynamic system where the number of processes may change over time. The implementation builds upon the non-blocking binary search tree implementation presented by Ellen et al. (in PODC 2010) by applying a simple mechanism to make the tree persistent.
Zero-Shot Dialog Generation with Cross-Domain Latent Actions
Venue: arXiv cs.CL 2018
Year: 2018

This paper introduces zero-shot dialog generation (ZSDG), as a step towards neural dialog systems that can instantly generalize to new situations with minimal data. ZSDG enables an end-to-end generative dialog system to generalize to a new domain for which only a domain description is provided and no training dialogs are available. Then a novel learning framework, Action Matching, is proposed. This algorithm can learn a cross-domain embedding space that models the semantics of dialog responses which, in turn, lets a neural dialog generation model generalize to new domains. We evaluate our methods on a new synthetic dialog dataset, and an existing human-human dialog dataset. Results show that our method has superior performance in learning dialog models that rapidly adapt their behavior to new domains and suggests promising future research.
An attention-based Bi-GRU-CapsNet model for hypernymy detection between compound entities
Venue: arXiv cs.CL 2018
Year: 2018

Named entities are usually composable and extensible. Typical examples are names of symptoms and diseases in medical areas. To distinguish these entities from general entities, we name them \textit{compound entities}. In this paper, we present an attention-based Bi-GRU-CapsNet model to detect hypernymy relationship between compound entities. Our model consists of several important components. To avoid the out-of-vocabulary problem, English words or Chinese characters in compound entities are fed into the bidirectional gated recurrent units. An attention mechanism is designed to focus on the differences between the two compound entities. Since there are some different cases in hypernymy relationship between compound entities, capsule network is finally employed to decide whether the hypernymy relationship exists or not. Experimental results demonstrate
Distributional stability and deterministic equilibrium selection under heterogeneous evolutionary dynamics
Venue: arXiv cs.GT 2018
Year: 2018

In the presence of persistent payoff heterogeneity, the evolution of the aggregate strategy hugely depends on the underlying strategy composition under many evolutionary dynamics, while the aggregate dynamic under the standard BRD reduces to a homogenized smooth BRD, where persistent payoff heterogeneity averages to homogeneous transitory payoff shocks. In this paper, we consider deterministic evolutionary dynamics in heterogeneous population and develop the stronger concept of local stability by imposing robustness to persistent payoff heterogeneity. It is known that nonaggregability holds generically if the switching rate in a given evolutionary dynamic correlates with the payoff gain from a switch. To parameterize the payoff sensitivity of an evolutionary dynamic, we propose to use tempered best response dynamics with bounded support of switching costs.
Low-pass Recurrent Neural Networks - A memory architecture for longer-term correlation discovery
Venue: arXiv cs.LG 2018
Year: 2018

Reinforcement learning (RL) agents performing complex tasks must be able to remember observations and actions across sizable time intervals. This is especially true during the initial learning stages, when exploratory behaviour can increase the delay between specific actions and their effects. Many new or popular approaches for learning these distant correlations employ backpropagation through time (BPTT), but this technique requires storing observation traces long enough to span the interval between cause and effect. Besides memory demands, learning dynamics like vanishing gradients and slow convergence due to infrequent weight updates can reduce BPTT's practicality; meanwhile, although online recurrent network learning is a developing topic, most approaches are not efficient enough to use as replacements. We propose a simple, effective memory strategy that can extend the window over which BPTT can learn without requiring longer traces. We explore this approach empirically on a few tasks and discuss its implications.
Word learning and the acquisition of syntactic--semantic overhypotheses
Venue: arXiv cs.CL 2018
Year: 2018

Children learning their first language face multiple problems of induction: how to learn the meanings of words, and how to build meaningful phrases from those words according to syntactic rules. We consider how children might solve these problems efficiently by solving them jointly, via a computational model that learns the syntax and semantics of multi-word utterances in a grounded reference game. We select a well-studied empirical case in which children are aware of patterns linking the syntactic and semantic properties of words --- that the properties picked out by base nouns tend to be related to shape, while prenominal adjectives tend to refer to other properties such as color. We show that children applying such inductive biases are accurately reflecting the statistics of child-directed speech, and that inducing similar biases in our computational model captures children's behavior in a classic adjective learning experiment. Our model incorporating such biases also demonstrates a clear data efficiency in learning, relative to a baseline model that learns without forming syntax-sensitive overhypotheses of word meaning. Thus solving a more complex joint inference problem may make the full problem of language acquisition easier, not harder.
AuthStore: Password-based Authentication and Encrypted Data Storage in Untrusted Environments
Venue: arXiv cs.CR 2018
Year: 2018

Passwords are widely used for client to server authentication as well as for encrypting data stored in untrusted environments, such as cloud storage. Both, authentication and encrypted cloud storage, are usually discussed in isolation. In this work, we propose AuthStore, a flexible authentication framework that allows users to securely reuse passwords for authentication as well as for encrypted cloud storage at a single or multiple service providers. Users can configure how secure passwords are protected using password stretching techniques. We present a compact password-authenticated key exchange protocol (CompactPAKE) that integrates the retrieval of password stretching parameters. A parameter attack is described and we show how existing solutions suffer from this attack. Furthermore, we introduce a password manager that supports CompactPAKE.
A Two-stage Approach to Estimate CFO and Channel with One-bit ADCs
Venue: arXiv cs.IT 2018
Year: 2018

In this letter, we propose a two-stage approach to estimate the carrier frequency offset (CFO) and channel with one-bit analog-to-digital converters (ADCs). Firstly, a simple metric which is only a function of the CFO is proposed, and the CFO is estimated via solving the one-dimensional optimization problem. Secondly, the generalized approximate message passing (GAMP) algorithm combined with expectation maximization (EM) method is utilized to estimate the channel. In order to provide a benchmark of our proposed algorithm in terms of the CFO estimation, the corresponding Cramér-Rao bound (CRB) is derived. Furthermore, numerical results demonstrate the effectiveness of the proposed approach when applied to the general Gaussian channel and mmWave channel.
Sparse Convolutional Beamforming for Ultrasound Imaging
Venue: arXiv cs.IT 2018
Year: 2018

The standard technique used by commercial medical ultrasound systems to form B-mode images is delay and sum (DAS) beamforming. However, DAS often results in limited image resolution and contrast, which are governed by the center frequency and the aperture size of the ultrasound transducer. A large number of elements leads to improved resolution but at the same time increases the data size and the system cost due to the receive electronics required for each element. Therefore, reducing the number of receiving channels while producing high quality images is of great importance. In this paper, we introduce a nonlinear beamformer called COnvolutional Beamforming Algorithm (COBA), which achieves significant improvement of lateral resolution and contrast. In addition, it can be implemented efficiently using the fast Fourier transform. Based on the COBA concept, we next present two sparse beamformers with closed form expressions for the sensor locations, which result in the same beam pattern as DAS and COBA while using far fewer array elements. Optimization of the number of elements shows that they require a minimal number of elements which is on the order of the square root of the number used by DAS. The performance of the proposed methods is tested and validated using simulated data, phantom scans and in vivo cardiac data. The results demonstrate that COBA outperforms DAS in terms of resolution and contrast and that the suggested beamformers offer a sizable element reduction while generating images with an equivalent or improved quality in comparison to DAS.
Using Elm to Introduce Algebraic Thinking to K-8 Students
Venue: arXiv cs.CY 2018
Year: 2018

In recent years, there has been increasing interest in developing a Computer Science curriculum for K-8 students. However, there have been significant barriers to creating and deploying a Computer Science curriculum in many areas, including teacher time and the prioritization of other 21st-century skills. At McMaster University, we have developed both general computer literacy activities and specific programming activities. Integration of these activities is made easy as they each support existing curricular goals. In this paper, we focus on programming in the functional language Elm and the graphics library GraphicSVG. Elm is in the ML (Meta Language) family, with a lean syntax and easy inclusion of Domain Specific Languages. This allows children to start experimenting with GraphicSVG as a language for describing shape, and pick up the core Elm language as they grow in sophistication. Teachers see children making connections between computer graphics and mathematics within the first hour. Graphics are defined declaratively, and support aggregation and transformation, i.e., Algebra. Variables are not needed initially, but are introduced as a time-saving feature, which is immediately accepted. Since variables are declarative, they match students' expectations. Advanced students are also exposed to State by making programs that react to user taps or clicks. The syntax required to do so closely follows the theoretical concepts, making it easy for them to grasp. For each of these concepts, we explain how they fit into the presentations we make to students, like the 5200 children taught in 2016. Finally, we describe ongoing work on a touch-based Elm editor for iPad, which features (1) type highlighting (as opposed to syntax highlighting), (2) preservation of correct syntax and typing across transformations, (3) context information (e.g. displaying parameter names for GraphicSVG functions), and (4) immediate feedback (e.g. restarting animations after every program change).
Teaching Erlang through the Internet: An Experience Report
Venue: arXiv cs.CY 2018
Year: 2018

Today functional programming languages are seen as a practical solution to the difficult problems of concurrent and distributed programming. Erlang is a functional language designed to build massively scalable and fault tolerant applications. This paper describes the authors' experiences delivering a massively online open course (MOOC) on the FutureLearn platform.
A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states
Venue: arXiv cs.DC 2018
Year: 2018

A population protocol can be viewed as a sequence of pairwise interactions of $n$ agents (nodes). During one interaction, two agents selected uniformly at random update their states by applying a specified deterministic transition function. In a long run, the whole system should stabilize at the correct output property. The main performance objectives in designing population protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem which uses $Θ(\log n)$ states (per agent) and stabilizes in $O(\log^{5/3} n)$ parallel time (i.e., $O(n\log^{5/3} n)$ interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that any exact-majority protocol which stabilizes in expected $O(n^{1-ε})$ parallel time, for any constant $ε> 0$, requires $Ω(\log n)$ states. They also showed an $O(\log^2 n)$-time protocol with $O(\log n)$ states, the currently fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on $O(\log n)$ phases and requires that all nodes are well synchronized within each phase, leading naturally to upper bounds of the order of at least $\log^2 n$ because of $Θ(\log n)$ synchronization time per phase. We show how this framework can be tightened with {\em weak synchronization} to break the $O(\log^2 n)$ upper bound of previous protocols.
Energy-Efficient Downlink Power Control in mmWave Cell-Free and User-Centric Massive MIMO
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers cell-free and user-centric approaches for coverage improvement in wireless cellular systems operating at millimeter wave frequencies, and proposes downlink power control algorithms aimed at maximizing the global energy efficiency. To tackle the non-convexity of the problems, an interaction between sequential and alternating optimization is considered. The use of hybrid analog/digital beamformers is also taken into account. The numerical results show the benefits obtained from the power control algorithm, as well as that the user-centric approach generally outperforms the cell-free one.
Effects of Word Embeddings on Neural Network-based Pitch Accent Detection
Venue: arXiv cs.CL 2018
Year: 2018

Pitch accent detection often makes use of both acoustic and lexical features based on the fact that pitch accents tend to correlate with certain words. In this paper, we extend a pitch accent detector that involves a convolutional neural network to include word embeddings, which are state-of-the-art vector representations of words. We examine the effect these features have on within-corpus and cross-corpus experiments on three English datasets. The results show that while word embeddings can improve the performance in corpus-dependent experiments, they also have the potential to make generalization to unseen data more challenging.
On the approximability of the stable marriage problem with one-sided ties
Venue: arXiv cs.DS 2018
Year: 2018

The classical stable marriage problem asks for a matching between a set of men and a set of women with no blocking pairs, which are pairs formed by a man and a woman who would both prefer switching from their current status to be paired up together. When both men and women have strict preferences over the opposite group, all stable matchings have the same cardinality, and the famous Gale-Shapley algorithm can be used to find one. Differently, if we allow ties in the preference lists, finding a stable matching of maximum cardinality is an NP-hard problem, already when the ties are one-sided, that is, they appear only in the preferences of one group. For this reason, many researchers have focused on developing approximation algorithm for this problem. In this paper, we give a refined analysis of an approximation algorithm given by Huang and Telikepalli (IPCO14) for the stable marriage problem with one-sided ties, which shows an improved 13/9 -approximation factor for the problem. Interestingly, our analysis is tight.
A Navigational Approach to Health
Venue: arXiv cs.CY 2018
Year: 2018

What if an app could guide you to better health, similar to how GPS navigation directs you to your desired destination? What if the app could use real-time information to redirect you around a disease, just as you're rerouted to avoid traffic? What if the app could provide step-by-step directions to get you to your optimal health state, whether you're a professional athlete or retires school teacher? We discuss how this navigational approach to healthcare could become a reality by combining technology with well-established cybernetics principles.
The Concept of the Deep Learning-Based System "Artificial Dispatcher" to Power System Control and Dispatch
Venue: arXiv cs.CY 2018
Year: 2018

Year by year control of normal and emergency conditions of up-to-date power systems becomes an increasingly complicated problem. With the increasing complexity the existing control system of power system conditions which includes operative actions of the dispatcher and work of special automatic devices proves to be insufficiently effective more and more frequently, which raises risks of dangerous and emergency conditions in power systems. The paper is aimed at compensating for the shortcomings of man (a cognitive barrier, exposure to stresses and so on) and automatic devices by combining their strong points, i.e. the dispatcher's intelligence and the speed of automatic devices by virtue of development of the intelligent system "Artificial dispatcher" on the basis of deep machine learning technology. For realization of the system "Artificial dispatcher" in addition to deep learning it is planned to attract the game theory approaches to formalize work of the up-to-date power system as a game problem. The "gain" for "Artificial dispatcher" will consist in bringing in a power system in the normal steady-state or post-emergency conditions by means of the required control actions.
An efficient structural attack on NIST submission DAGS
Venue: arXiv cs.CR 2018
Year: 2018

We present an efficient key recovery attack on code based encryption schemes using some quasi-dyadic alternant codes with extension degree 2. This attack permits to break the proposal DAGS recently submitted to NIST.
Nonlinear Dimensionality Reduction for Discriminative Analytics of Multiple Datasets
Venue: arXiv cs.LG 2018
Year: 2018

Principal component analysis (PCA) is widely used for feature extraction and dimensionality reduction, with documented merits in diverse tasks involving high-dimensional data. Standard PCA copes with one dataset at a time, but it is challenged when it comes to analyzing multiple datasets jointly. In certain data science settings however, one is often interested in extracting the most discriminative information from one dataset of particular interest (a.k.a. target data) relative to the other(s) (a.k.a. background data). To this end, this paper puts forth a novel approach, termed discriminative (d) PCA, for such discriminative analytics of multiple datasets. Under certain conditions, dPCA is proved to be least-squares optimal in recovering the component vector unique to the target data relative to background data. To account for nonlinear data correlations, (linear) dPCA models for one or multiple background datasets are generalized through kernel-based learning. Interestingly, all dPCA variants admit an analytical solution obtainable with a single (generalized) eigenvalue decomposition. Finally, corroborating dimensionality reduction tests using both synthetic and real datasets are provided to validate the effectiveness of the proposed methods.
Incremental Database Design using UML-B and Event-B
Venue: arXiv cs.DB 2018
Year: 2018

Correct operation of many critical systems is dependent on the data consistency and integrity properties of underlying databases. Therefore, a verifiable and rigorous database design process is highly desirable. This research aims to investigate and deliver a comprehensive and practical approach for modelling databases in formal methods through layered refinements. The methodology is being guided by a number of case studies, using abstraction and refinement in UML-B and verification with the Rodin tool. UML-B is a graphical representation of the Event-B formalism and the Rodin tool supports verification for Event-B and UML-B. Our method guides developers to model relational databases in UML-B through layered refinement and to specify the necessary constraints and operations on the database.