OpenRaiser/Intern-Atlas huggingface dataset:
Non-erasing Chomsky-Sch{ü}tzenberger theorem with grammar-independent alphabet
Venue: arXiv cs.FL 2018
Year: 2018

The famous theorem by Chomsky and Schützenberger (CST) says that every context-free language $L$ over an alphabet $Σ$ is representable as $h(D \cap R)$, where $D$ is a Dyck language over a set $Ω$ of brackets, $R$ is a local language and $h$ is an alphabetic homomorphism that erases unboundedly many symbols. Berstel found that the number of erasures can be linearly limited if the grammar is in Greibach normal form; Berstel and Boasson (and later, independently, Okhotin) proved a non-erasing variant of CST for grammars in Double Greibach Normal Form. In all these CST statements, however, the size of the Dyck alphabet $Ω$ depends on the grammar size for $L$. In the Stanley variant of the CST, $|Ω|$ only depends on $|Σ|$ and not on the grammar, but the homomorphism erases many more symbols than in the other versions of CST; also, the regular language $R$ is strictly locally testable but not local. We prove a new version of CST which combines both features of being non-erasing and of using a grammar-independent alphabet. In our construction, $|Ω|$ is polynomial in $|Σ|$, namely $O(|Σ|^{46})$, and the regular language $R$ is strictly locally testable. Using a recent generalization of Medvedev's homomorphic characterization of regular languages, we prove that the degree in the polynomial dependence of $|Ω|$ on $|Σ|$ may be reduced to just 2 in the case of linear grammars in Double Greibach Normal Form.
CloudLaunch: Discover and Deploy Cloud Applications
Venue: arXiv cs.DC 2018
Year: 2018

Cloud computing is a common platform for delivering software to end users. However, the process of making complex-to-deploy applications available across different cloud providers requires isolated and uncoordinated application-specific solutions, often locking-in developers to a particular cloud provider. Here, we present the CloudLaunch application as a uniform platform for discovering and deploying applications for different cloud providers. CloudLaunch allows arbitrary applications to be added to a catalog with each application having its own customizable user interface and control over the launch process, while preserving cloud-agnosticism so that authors can easily make their applications available on multiple clouds with minimal effort. It then provides a uniform interface for launching available applications by end users across different cloud providers. Architecture details are presented along with examples of different deployable applications that highlight architectural features.
Towards an Unequivocal Representation of Actions
Venue: arXiv cs.CV 2018
Year: 2018

This work introduces verb-only representations for actions and interactions; the problem of describing similar motions (e.g. 'open door', 'open cupboard'), and distinguish differing ones (e.g. 'open door' vs 'open bottle') using verb-only labels. Current approaches for action recognition neglect legitimate semantic ambiguities and class overlaps between verbs (Fig. 1), relying on the objects to disambiguate interactions. We deviate from single-verb labels and introduce a mapping between observations and multiple verb labels - in order to create an Unequivocal Representation of Actions. The new representation benefits from increased vocabulary and a soft assignment to an enriched space of verb labels. We learn these representations as multi-output regression, using a two-stream fusion CNN. The proposed approach outperforms conventional single-verb labels (also known as majority voting) on three egocentric datasets for both recognition and retrieval.
A Proposal for Outlier and Noise Detection in Public Officials' Affidavits
Venue: arXiv cs.CY 2018
Year: 2018

Outlier and noise detection processes are highly useful in the quality assessment of any kind of database. Such processes may have novel civic and public applications in the detection of anomalies in public data. The purpose of this work is to explore the possibilities of experimentation with, validation and application of hybrid outlier and noise detection procedures in public officials' affidavit systems currently available in Argentina.
Boosting up Scene Text Detectors with Guided CNN
Venue: arXiv cs.CV 2018
Year: 2018

Deep CNNs have achieved great success in text detection. Most of existing methods attempt to improve accuracy with sophisticated network design, while paying less attention on speed. In this paper, we propose a general framework for text detection called Guided CNN to achieve the two goals simultaneously. The proposed model consists of one guidance subnetwork, where a guidance mask is learned from the input image itself, and one primary text detector, where every convolution and non-linear operation are conducted only in the guidance mask. On the one hand, the guidance subnetwork filters out non-text regions coarsely, greatly reduces the computation complexity. On the other hand, the primary text detector focuses on distinguishing between text and hard non-text regions and regressing text bounding boxes, achieves a better detection accuracy. A training strategy, called background-aware block-wise random synthesis, is proposed to further boost up the performance. We demonstrate that the proposed Guided CNN is not only effective but also efficient with two state-of-the-art methods, CTPN and EAST, as backbones. On the challenging benchmark ICDAR 2013, it speeds up CTPN by 2.9 times on average, while improving the F-measure by 1.5%. On ICDAR 2015, it speeds up EAST by 2.0 times while improving the F-measure by 1.0%.
Extracting structured dynamical systems using sparse optimization with very few samples
Venue: arXiv cs.IT 2018
Year: 2018

Learning governing equations allows for deeper understanding of the structure and dynamics of data. We present a random sampling method for learning structured dynamical systems from under-sampled and possibly noisy state-space measurements. The learning problem takes the form of a sparse least-squares fitting over a large set of candidate functions. Based on a Bernstein-like inequality for partly dependent random variables, we provide theoretical guarantees on the recovery rate of the sparse coefficients and the identification of the candidate functions for the corresponding problem. Computational results are demonstrated on datasets generated by the Lorenz 96 equation, the viscous Burgers' equation, and the two-component reaction-diffusion equations (which is challenging due to parameter sensitives in the model). This formulation has several advantages including ease of use, theoretical guarantees of success, and computational efficiency with respect to ambient dimension and number of candidate functions.
ProCal: A Low-Cost and Programmable Calibration Tool for IoT Devices
Venue: arXiv cs.PF 2018
Year: 2018

Calibration is an important step towards building reliable IoT systems. For example, accurate sensor reading requires ADC calibration, and power monitoring chips must be calibrated before being used for measuring the energy consumption of IoT devices. In this paper, we present ProCal, a low-cost, accurate, and scalable power calibration tool. ProCal is a programmable platform which provides dynamic voltage and current output for calibration. The basic idea is to use a digital potentiometer connected to a parallel resistor network controlled through digital switches. The resistance and output frequency of ProCal is controlled by a software communicating with the board through the SPI interface. Our design provides a simple synchronization mechanism which prevents the need for accurate time synchronization. We present mathematical modeling and validation of the tool by incorporating the concept of Fibonacci sequence. Our extensive experimental studies show that this tool can significantly improve measurement accuracy. For example, for ATMega2560, the ADC error reduces from 0.2% to 0.01%. ProCal not only costs less than 2\% of the current commercial solutions, it is also highly accurate by being able to provide extensive range of current and voltage values.
Human-Machine Collaborative Optimization via Apprenticeship Scheduling
Venue: arXiv cs.AI 2018
Year: 2018

Coordinating agents to complete a set of tasks with intercoupled temporal and resource constraints is computationally challenging, yet human domain experts can solve these difficult scheduling problems using paradigms learned through years of apprenticeship. A process for manually codifying this domain knowledge within a computational framework is necessary to scale beyond the ``single-expert, single-trainee" apprenticeship model. However, human domain experts often have difficulty describing their decision-making processes, causing the codification of this knowledge to become laborious. We propose a new approach for capturing domain-expert heuristics through a pairwise ranking formulation. Our approach is model-free and does not require enumerating or iterating through a large state space. We empirically demonstrate that this approach accurately learns multifaceted heuristics on a synthetic data set incorporating job-shop scheduling and vehicle routing problems, as well as on two real-world data sets consisting of demonstrations of experts solving a weapon-to-target assignment problem and a hospital resource allocation problem. We also demonstrate that policies learned from human scheduling demonstration via apprenticeship learning can substantially improve the efficiency of a branch-and-bound search for an optimal schedule. We employ this human-machine collaborative optimization technique on a variant of the weapon-to-target assignment problem. We demonstrate that this technique generates solutions substantially superior to those produced by human domain experts at a rate up to 9.5 times faster than an optimization approach and can be applied to optimally solve problems twice as complex as those solved by a human demonstrator.
Argument Harvesting Using Chatbots
Venue: arXiv cs.AI 2018
Year: 2018

Much research in computational argumentation assumes that arguments and counterarguments can be obtained in some way. Yet, to improve and apply models of argument, we need methods for acquiring them. Current approaches include argument mining from text, hand coding of arguments by researchers, or generating arguments from knowledge bases. In this paper, we propose a new approach, which we call argument harvesting, that uses a chatbot to enter into a dialogue with a participant to get arguments and counterarguments from him or her. Because it is automated, the chatbot can be used repeatedly in many dialogues, and thereby it can generate a large corpus. We describe the architecture of the chatbot, provide methods for managing a corpus of arguments and counterarguments, and an evaluation of our approach in a case study concerning attitudes of women to participation in sport.
IPchain: Securing IP Prefix Allocation and Delegation with Blockchain
Venue: arXiv cs.NI 2018
Year: 2018

We present IPchain, a blockchain to store the allocations and delegations of IP addresses, with the aim of easing the deployment of secure interdomain routing systems. Interdomain routing security is of vital importance to the Internet since it prevents unwanted traffic redirections. IPchain makes use of blockchains' properties to provide flexible trust models and simplified management when compared to existing systems. In this paper we argue that Proof of Stake is a suitable consensus algorithm for IPchain due to the unique incentive structure of this use-case. We have implemented and evaluated IPchain's performance and scalability storing around 150k IP prefixes in a 1GB chain.
Pocket Game Jams: a Constructionist Approach at Schools
Venue: arXiv cs.CY 2018
Year: 2018

The constructionist approach is more interested in constructing personal experience than about acquiring information. It states that learning is most effective when building knowledge through active engagement. Experiential and discovery learning by challenges inspire creativity, and projects allow independent thinking and new ways of learning information. This paper describes how the "No One Left Behind" (NOLB) project plans to integrate this approach into school curricula using two concepts. The first one is to enable students to create their own games with Pocket Code by using its easy-to-learn visual programming language. The second concept is to foster collaboration and teamwork through hands-on sessions by conducting Game Jams using Pocket Code, so called Pocket Game Jams. We present insights into such a Pocket Game Jam and give an outlook on how we will use this concept.
Cell-free Massive MIMO Networks: Optimal Power Control against Active Eavesdropping
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies the security aspect of a recently introduced network ("cell-free massive MIMO") under a pilot spoofing attack. Firstly, a simple method to recognize the presence of this type of an active eavesdropping attack to a particular user is shown. In order to deal with this attack, we consider the problem of maximizing the achievable data rate of the attacked user or its achievable secrecy rate. The corresponding problems of minimizing the consumption power subject to security constraints are also considered in parallel. Path-following algorithms are developed to solve the posed optimization problems under different power allocation to access points (APs). Under equip-power allocation to APs, these optimization problems admit closed-form solutions. Numerical results show their efficiencies.
Research Curation on Knowledge Management
Venue: arXiv cs.DL 2018
Year: 2018

The notions of knowledge and its management have been at the core of the information systems (IS) field almost since its inception. Knowledge has been viewed in several ways in the prior literature, including as a state of mind, an object, a process, access to information, and a capability. A commonly-used definition characterizes knowledge as a justified belief that increases an entity's capacity for effective action (Alavi and Leidner 2001, p. 109). Relatedly, knowledge management (KM) has been defined as a systemic process to acquire, organize, and communicate individual knowledge so that others may make use of it (Beck et al. 2014). Knowledge-management systems (KMSs) support these processes for creating, exchanging, and storing knowledge (Beck et al. 2014), and have been viewed as being either repository- based or network-based (Kankanhalli et al. 2005). In an attempt to provide a useful resource for scholars interested in KM, we take stock of the pertinent research published in MISQ. More specifically, the goal of this curation is to serve as a living document that will offer a starting point for future KM research. This curation highlights the 44 articles with a primary focus on KM (Table 1). The articles address theoretical and conceptual issues, provide methodological guidance, and use a wide range of quantitative and qualitative research methods. To define the scope of this curation, we excluded: (1) articles in which KM is used as part of another construct; (2) some early articles that were practice- oriented with limited scholarly orientation; and (3) articles that focus on knowledge (such as the knowledge requirements of IS professionals) but not on KM.
DFINITY Technology Overview Series, Consensus System
Venue: arXiv cs.DC 2018
Year: 2018

The DFINITY blockchain computer provides a secure, performant and flexible consensus mechanism. At its core, DFINITY contains a decentralized randomness beacon which acts as a verifiable random function (VRF) that produces a stream of outputs over time. The novel technique behind the beacon relies on the existence of a unique-deterministic, non-interactive, DKG-friendly threshold signatures scheme. The only known examples of such a scheme are pairing-based and derived from BLS. The DFINITY blockchain is layered on top of the DFINITY beacon and uses the beacon as its source of randomness for leader selection and leader ranking. A "weight" is attributed to a chain based on the ranks of the leaders who propose the blocks in the chain, and that weight is used to select between competing chains. The DFINITY blockchain is layered on top of the DFINITY beacon and uses the beacon as its source of randomness for leader selection and leader ranking blockchain is further hardened by a notarization process which dramatically improves the time to finality and eliminates the nothing-at-stake and selfish mining attacks. DFINITY consensus algorithm is made to scale through continuous quorum selections driven by the random beacon. In practice, DFINITY achieves block times of a few seconds and transaction finality after only two confirmations. The system gracefully handles temporary losses of network synchrony including network splits, while it is provably secure under synchrony.
Examining a hate speech corpus for hate speech detection and popularity prediction
Venue: arXiv cs.CL 2018
Year: 2018

As research on hate speech becomes more and more relevant every day, most of it is still focused on hate speech detection. By attempting to replicate a hate speech detection experiment performed on an existing Twitter corpus annotated for hate speech, we highlight some issues that arise from doing research in the field of hate speech, which is essentially still in its infancy. We take a critical look at the training corpus in order to understand its biases, while also using it to venture beyond hate speech detection and investigate whether it can be used to shed light on other facets of research, such as popularity of hate tweets.
Towards Autonomous Reinforcement Learning: Automatic Setting of Hyper-parameters using Bayesian Optimization
Venue: arXiv cs.AI 2018
Year: 2018

With the increase of machine learning usage by industries and scientific communities in a variety of tasks such as text mining, image recognition and self-driving cars, automatic setting of hyper-parameter in learning algorithms is a key factor for achieving satisfactory performance regardless of user expertise in the inner workings of the techniques and methodologies. In particular, for a reinforcement learning algorithm, the efficiency of an agent learning a control policy in an uncertain environment is heavily dependent on the hyper-parameters used to balance exploration with exploitation. In this work, an autonomous learning framework that integrates Bayesian optimization with Gaussian process regression to optimize the hyper-parameters of a reinforcement learning algorithm, is proposed. Also, a bandits-based approach to achieve a balance between computational costs and decreasing uncertainty about the Q-values, is presented. A gridworld example is used to highlight how hyper-parameter configurations of a learning algorithm (SARSA) are iteratively improved based on two performance functions.
Lock-Free Search Data Structures: Throughput Modelling with Poisson Processes
Venue: arXiv cs.DS 2018
Year: 2018

This paper considers the modelling and the analysis of the performance of lock-free concurrent search data structures. Our analysis considers such lock-free data structures that are utilized through a sequence of operations which are generated with a memoryless and stationary access pattern. Our main contribution is a new way of analysing lock-free search data structures: our execution model matches with the behavior that we observe in practice and achieves good throughput predictions. Search data structures are formed of linked basic blocks, usually referred as nodes, that can be accessed by two kinds of events, characterized by their latencies; (i) CAS events originated as a result of modifications of the search data structures (ii) Read events originated during traversals. This type of data structures are usually designed to accommodate a large number of data nodes, which makes the occurrence of an event on a given node rare at any given time. The throughput is defined by the number of events per operation in conjunction with the factors that impact the latencies of these events. We frame these impacting factors under capacity and coherence cache misses. In this context, we model the events as Poisson processes that we can merge and split to estimate the latencies of the events based on the interleaving of events from different threads, and in turn estimate the throughput. We have validated our analysis on several fundamental lock-free search data structures such as linked lists, hash tables, skip lists and binary trees.
Curriculum Adversarial Training
Venue: arXiv cs.LG 2018
Year: 2018

Recently, deep learning has been applied to many security-sensitive applications, such as facial authentication. The existence of adversarial examples hinders such applications. The state-of-the-art result on defense shows that adversarial training can be applied to train a robust model on MNIST against adversarial examples; but it fails to achieve a high empirical worst-case accuracy on a more complex task, such as CIFAR-10 and SVHN. In our work, we propose curriculum adversarial training (CAT) to resolve this issue. The basic idea is to develop a curriculum of adversarial examples generated by attacks with a wide range of strengths. With two techniques to mitigate the forgetting and the generalization issues, we demonstrate that CAT can improve the prior art's empirical worst-case accuracy by a large margin of 25% on CIFAR-10 and 35% on SVHN. At the same, the model's performance on non-adversarial inputs is comparable to the state-of-the-art models.
Shattered Trust: When Replacement Smartphone Components Attack
Venue: arXiv cs.CR 2018
Year: 2018

Phone touchscreens, and other similar hardware components such as orientation sensors, wireless charging controllers, and NFC readers, are often produced by third-party manufacturers and not by the phone vendors themselves. Third-party driver source code to support these components is integrated into the vendor's source code. In contrast to 'pluggable' drivers, such as USB or network drivers, the component driver's source code implicitly assumes that the component hardware is authentic and trustworthy. As a result of this trust, very few integrity checks are performed on the communications between the component and the device's main processor. In this paper, we call this trust into question, considering the fact that touchscreens are often shattered and then replaced with aftermarket components of questionable origin. We analyze the operation of a commonly used touchscreen controller. We construct two standalone attacks, based on malicious touchscreen hardware, that function as building blocks toward a full attack: a series of touch injection attacks that allow the touchscreen to impersonate the user and exfiltrate data, and a buffer overflow attack that lets the attacker execute privileged operations. Combining the two building blocks, we present and evaluate a series of end-to-end attacks that can severely compromise a stock Android phone with standard firmware. Our results make the case for a hardware-based physical countermeasure.
Lighting the Way to a Smart World: Lattice-Based Cryptography for Internet of Things
Venue: arXiv cs.CR 2018
Year: 2018

The Ukraine power grid cyberattacks remind us that the smart Internet of Things (IoT) can help us control our light-bulbs, but if under attacks it might also take us into darkness. Nowadays, many literatures have tried to address the concerns on IoT security, but few of them take into consideration the sever threats to IoT coming from the advances of quantum computing. As a promising candidate for the future post-quantum cryptography standard, lattice-based cryptography enjoys the advantages of strong security guarantees and high efficiency, which make it extremely suitable for IoT applications. In this paper, we summarize the advantages of lattice-based cryptography and the state of art of their implementations for IoT devices.