OpenRaiser/Intern-Atlas huggingface dataset:
Content Enhanced BERT-based Text-to-SQL Generation
Venue: arXiv cs.CL 2020
Year: 2020

We present a simple methods to leverage the table content for the BERT-based model to solve the text-to-SQL problem. Based on the observation that some of the table content match some words in question string and some of the table header also match some words in question string, we encode two addition feature vector for the deep model. Our methods also benefit the model inference in testing time as the tables are almost the same in training and testing time. We test our model on the WikiSQL dataset and outperform the BERT-based baseline by 3.7% in logic form and 3.7% in execution accuracy and achieve state-of-the-art.
On the complexity of acyclic modules in automata networks
Venue: arXiv cs.DM 2020
Year: 2020

Modules were introduced as an extension of Boolean automata networks. They have inputs which are used in the computation said modules perform, and can be used to wire modules with each other. In the present paper we extend this new formalism and study the specific case of acyclic modules. These modules prove to be well described in their limit behavior by functions called output functions. We provide other results that offer an upper bound on the number of attractors in an acyclic module when wired recursively into an automata network, alongside a diversity of complexity results around the difficulty of deciding the existence of cycles depending on the number of inputs and the size of said cycle.
Sharper bounds for uniformly stable algorithms
Venue: arXiv cs.LG 2020
Year: 2020

Deriving generalization bounds for stable algorithms is a classical question in learning theory taking its roots in the early works by Vapnik and Chervonenkis (1974) and Rogers and Wagner (1978). In a series of recent breakthrough papers by Feldman and Vondrak (2018, 2019), it was shown that the best known high probability upper bounds for uniformly stable learning algorithms due to Bousquet and Elisseef (2002) are sub-optimal in some natural regimes. To do so, they proved two generalization bounds that significantly outperform the simple generalization bound of Bousquet and Elisseef (2002). Feldman and Vondrak also asked if it is possible to provide sharper bounds and prove corresponding high probability lower bounds. This paper is devoted to these questions: firstly, inspired by the original arguments of Feldman and Vondrak (2019), we provide a short proof of the moment bound that implies the generalization bound stronger than both recent results (Feldman and Vondrak, 2018, 2019). Secondly, we prove general lower bounds, showing that our moment bound is sharp (up to a logarithmic factor) unless some additional properties of the corresponding random variables are used. Our main probabilistic result is a general concentration inequality for weakly correlated random variables, which may be of independent interest.
LibriVoxDeEn: A Corpus for German-to-English Speech Translation and German Speech Recognition
Venue: arXiv cs.CL 2020
Year: 2020

We present a corpus of sentence-aligned triples of German audio, German text, and English translation, based on German audiobooks. The speech translation data consist of 110 hours of audio material aligned to over 50k parallel sentences. An even larger dataset comprising 547 hours of German speech aligned to German text is available for speech recognition. The audio data is read speech and thus low in disfluencies. The quality of audio and sentence alignments has been checked by a manual evaluation, showing that speech alignment quality is in general very high. The sentence alignment quality is comparable to well-used parallel translation data and can be adjusted by cutoffs on the automatic alignment score. To our knowledge, this corpus is to date the largest resource for German speech recognition and for end-to-end German-to-English speech translation.
An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version)
Venue: arXiv cs.DB 2020
Year: 2020

Document database systems store self-describing semi-structured records, such as JSON, "as-is" without requiring the users to pre-define a schema. This provides users with the flexibility to change the structure of incoming records without worrying about taking the system offline or hindering the performance of currently running queries. However, the flexibility of such systems does not free. The large amount of redundancy in the records can introduce an unnecessary storage overhead and impact query performance. Our focus in this paper is to address the storage overhead issue by introducing a tuple compactor framework that infers and extracts the schema from self-describing semi-structured records during the data ingestion. As many prominent document stores, such as MongoDB and Couchbase, adopt Log Structured Merge (LSM) trees in their storage engines, our framework exploits LSM lifecycle events to piggyback the schema inference and extraction operations. We have implemented and empirically evaluated our approach to measure its impact on storage, data ingestion, and query performance in the context of Apache AsterixDB.
Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs
Venue: arXiv cs.LG 2020
Year: 2020

When samples have internal structure, we often see a mismatch between the objective optimized during training and the model's goal during inference. For example, in sequence-to-sequence modeling we are interested in high-quality translated sentences, but training typically uses maximum likelihood at the word level. The natural training-time loss would involve a combinatorial problem -- dynamic programming-based global sequence alignment -- but solutions to combinatorial problems are not differentiable with respect to their input parameters, so surrogate, differentiable losses are used instead. Here, we show how to perform gradient descent over combinatorial optimization algorithms that involve continuous parameters, for example edge weights, and can be efficiently expressed as linear programs. We demonstrate usefulness of gradient descent over combinatorial optimization in sequence-to-sequence modeling using differentiable encoder-decoder architecture with softmax or Gumbel-softmax, and in image classification in a weakly supervised setting where instead of the correct class for each photo, only groups of photos labeled with correct but unordered set of classes are available during training.
Federated Learning with Unbiased Gradient Aggregation and Controllable Meta Updating
Venue: arXiv cs.LG 2020
Year: 2020

Federated learning (FL) aims to train machine learning models in the decentralized system consisting of an enormous amount of smart edge devices. Federated averaging (FedAvg), the fundamental algorithm in FL settings, proposes on-device training and model aggregation to avoid the potential heavy communication costs and privacy concerns brought by transmitting raw data. However, through theoretical analysis we argue that 1) the multiple steps of local updating will result in gradient biases and 2) there is an inconsistency between the expected target distribution and the optimization objectives following the training paradigm in FedAvg. To tackle these problems, we first propose an unbiased gradient aggregation algorithm with the keep-trace gradient descent and the gradient evaluation strategy. Then we introduce an additional controllable meta updating procedure with a small set of data samples, indicating the expected target distribution, to provide a clear and consistent optimization objective. Both the two improvements are model- and task-agnostic and can be applied individually or together. Experimental results demonstrate that the proposed methods are faster in convergence and achieve higher accuracy with different network architectures in various FL settings.
Digital Democracy: Episode IV -- A New Hope, How a Corporation for Public Software Could Transform Digital Engagement for Government and Civil Society
Venue: arXiv cs.CY 2020
Year: 2020

Though successive generations of digital technology have become increasingly powerful in the past twenty years, digital democracy has yet to realize its potential for deliberative transformation. The undemocratic exploitation of massive social media systems continued this trend, but it only worsened an existing problem of modern democracies, which were already struggling to develop deliberative infrastructure independent of digital technologies. There have been many creative conceptions of civic tech, but implementation has lagged behind innovation. This essay argues for implementing one such vision of digital democracy through the establishment of a public corporation. Modeled on the Corporation for Public Broadcasting in the U.S., this entity would foster the creation of new digital technology by providing a stable source of funding to nonprofit technologists, interest groups, civic organizations, government, researchers, private companies, and the public. Funded entities would produce and maintain software infrastructure for public benefit. The concluding sections identify what circumstances might create and sustain such an entity.
OffWorld Gym: open-access physical robotics environment for real-world reinforcement learning benchmark and research
Venue: arXiv cs.LG 2020
Year: 2020

Success stories of applied machine learning can be traced back to the datasets and environments that were put forward as challenges for the community. The challenge that the community sets as a benchmark is usually the challenge that the community eventually solves. The ultimate challenge of reinforcement learning research is to train real agents to operate in the real environment, but until now there has not been a common real-world RL benchmark. In this work, we present a prototype real-world environment from OffWorld Gym -- a collection of real-world environments for reinforcement learning in robotics with free public remote access. Close integration into existing ecosystem allows the community to start using OffWorld Gym without any prior experience in robotics and takes away the burden of managing a physical robotics system, abstracting it under a familiar API. We introduce a navigation task, where a robot has to reach a visual beacon on an uneven terrain using only the camera input and provide baseline results in both the real environment and the simulated replica. To start training, visit https://gym.offworld.ai
Computer-supported Analysis of Positive Properties, Ultrafilters and Modal Collapse in Variants of Gödel's Ontological Argument
Venue: arXiv cs.LO 2020
Year: 2020

Three variants of Kurt Gödel's ontological argument, proposed by Dana Scott, C. Anthony Anderson and Melvin Fitting, are encoded and rigorously assessed on the computer. In contrast to Scott's version of Gödel's argument the two variants contributed by Anderson and Fitting avoid modal collapse. Although they appear quite different on a cursory reading they are in fact closely related. This has been revealed in the computer-supported formal analysis presented in this article. Key to our formal analysis is the utilization of suitably adapted notions of (modal) ultrafilters, and a careful distinction between extensions and intensions of positive properties.
Image recognition from raw labels collected without annotators
Venue: arXiv cs.LG 2020
Year: 2020

Image classification problems are typically addressed by first collecting examples with candidate labels, second cleaning the candidate labels manually, and third training a deep neural network on the clean examples. The manual labeling step is often the most expensive one as it requires workers to label millions of images. In this paper we propose to work without any explicitly labeled data by i) directly training the deep neural network on the noisy candidate labels, and ii) early stopping the training to avoid overfitting. With this procedure we exploit an intriguing property of standard overparameterized convolutional neural networks trained with (stochastic) gradient descent: Clean labels are fitted faster than noisy ones. We consider two classification problems, a subset of ImageNet and CIFAR-10. For both, we construct large candidate datasets without any explicit human annotations, that only contain 10%-50% correctly labeled examples per class. We show that training on the candidate examples and regularizing through early stopping gives higher test performance for both problems than when training on the original, clean data. This is possible because the candidate datasets contain a huge number of clean examples, and, as we show in this paper, the noise generated through the label collection process is not nearly as adversarial for learning as the noise generated by randomly flipping labels.
Self-supervised classification of dynamic obstacles using the temporal information provided by videos
Venue: arXiv cs.CV 2020
Year: 2020

Nowadays, autonomous driving systems can detect, segment, and classify the surrounding obstacles using a monocular camera. However, state-of-the-art methods solving these tasks generally perform a fully supervised learning process and require a large amount of training labeled data. On another note, some self-supervised learning approaches can deal with detection and segmentation of dynamic obstacles using the temporal information available in video sequences. In this work, we propose to classify the detected obstacles depending on their motion pattern. We present a novel self-supervised framework consisting of learning offline clusters from temporal patch sequences and considering these clusters as labeled sets to train a real-time image classifier. The presented model outperforms state-of-the-art unsupervised image classification methods on large-scale diverse driving video dataset BDD100K.
Cryptomining Makes Noise: a Machine Learning Approach for Cryptojacking Detection
Venue: arXiv cs.CR 2020
Year: 2020

A new cybersecurity attack,where an adversary illicitly runs crypto-mining software over the devices of unaware users, is emerging in both the literature and in the wild . This attack, known as cryptojacking, has proved to be very effective given the simplicity of running a crypto-client into a target device. Several countermeasures have recently been proposed, with different features and performance, but all characterized by a host-based architecture. This kind of solutions, designed to protect the individual user, are not suitable for efficiently protecting a corporate network, especially against insiders. In this paper, we propose a network-based approach to detect and identify crypto-clients activities by solely relying on the network traffic, even when encrypted. First, we provide a detailed analysis of the real network traces generated by three major cryptocurrencies, Bitcoin, Monero, and Bytecoin, considering both the normal traffic and the one shaped by a VPN. Then, we propose Crypto-Aegis, a Machine Learning (ML) based framework built over the results of our investigation, aimed at detecting cryptocurrencies related activities, e.g., pool mining, solo mining, and active full nodes. Our solution achieves a striking 0.96 of F1-score and 0.99 of AUC for the ROC, while enjoying a few other properties, such as device and infrastructure independence. Given the extent and novelty of the addressed threat we believe that our approach, supported by its excellent results, pave the way for further research in this area.
Text Matters but Speech Influences: A Computational Analysis of Syntactic Ambiguity Resolution
Venue: arXiv cs.CL 2020
Year: 2020

Analyzing how human beings resolve syntactic ambiguity has long been an issue of interest in the field of linguistics. It is, at the same time, one of the most challenging issues for spoken language understanding (SLU) systems as well. As syntactic ambiguity is intertwined with issues regarding prosody and semantics, the computational approach toward speech intention identification is expected to benefit from the observations of the human language processing mechanism. In this regard, we address the task with attentive recurrent neural networks that exploit acoustic and textual features simultaneously and reveal how the modalities interact with each other to derive sentence meaning. Utilizing a speech corpus recorded on Korean scripts of syntactically ambiguous utterances, we revealed that co-attention frameworks, namely multi-hop attention and cross-attention, show significantly superior performance in disambiguating speech intention. With further analysis, we demonstrate that the computational models reflect the internal relationship between auditory and linguistic processes.
A Tableau Construction for Finite Linear-Time Temporal Logic
Venue: arXiv cs.LO 2020
Year: 2020

This paper describes a method for converting formulas in finite propositional linear-time temporal logic (Finite LTL) into finite-state automata whose languages are the models of the given formula. Finite LTL differs from traditional LTL in that formulas are interpreted with respect to finite, rather than infinite, sequences of states; this fact means that traditional finite-state automata, rather than ω-automata such as those developed by Büchi and others, suffice for recognizing models of such formulas. The approach considered is based on well-known tableau-construction techniques developed for LTL, which we adapt here for the setting of Finite LTL. The resulting automata may be used as a basis for model checking, satisfiability testing, and model synthesis.
Science and Technology Advance through Surprise
Venue: arXiv cs.DL 2020
Year: 2020

Breakthrough discoveries and inventions involve unexpected combinations of contents including problems, methods, and natural entities, and also diverse contexts such as journals, subfields, and conferences. Drawing on data from tens of millions of research papers, patents, and researchers, we construct models that predict next year's content and context combinations with an AUC of 95% based on embeddings constructed from high-dimensional stochastic block models, where the improbability of new combinations itself predicts up to 50% of the likelihood that they will gain outsized citations and major awards. Most of these breakthroughs occur when problems in one field are unexpectedly solved by researchers from a distant other. These findings demonstrate the critical role of surprise in advance, and enable evaluation of scientific institutions ranging from education and peer review to awards in supporting it.
HIGhER : Improving instruction following with Hindsight Generation for Experience Replay
Venue: arXiv cs.LG 2020
Year: 2020

Language creates a compact representation of the world and allows the description of unlimited situations and objectives through compositionality. While these characterizations may foster instructing, conditioning or structuring interactive agent behavior, it remains an open-problem to correctly relate language understanding and reinforcement learning in even simple instruction following scenarios. This joint learning problem is alleviated through expert demonstrations, auxiliary losses, or neural inductive biases. In this paper, we propose an orthogonal approach called Hindsight Generation for Experience Replay (HIGhER) that extends the Hindsight Experience Replay (HER) approach to the language-conditioned policy setting. Whenever the agent does not fulfill its instruction, HIGhER learns to output a new directive that matches the agent trajectory, and it relabels the episode with a positive reward. To do so, HIGhER learns to map a state into an instruction by using past successful trajectories, which removes the need to have external expert interventions to relabel episodes as in vanilla HER. We show the efficiency of our approach in the BabyAI environment, and demonstrate how it complements other instruction following methods.
Maximum Lifetime Convergecast Tree in Wireless Sensor Networks
Venue: arXiv cs.NI 2020
Year: 2020

We study the problem of building a maximum lifetime data collection tree for periodic convergecast applications in wireless sensor networks. We experimentally observe that if two nodes transmit same number of data packets, the amount of energy consumption of the nodes is approximately the same even if the payload lengths of the transmitted packets are different. This is because the major energy consumption during a packet transmission arises from radio start-up and medium access control overhead. Our formulated lifetime maximization problem captures the energy expenditure due to message transmissions/ receptions in terms of the number of data packets transmitted/ received, in contrast to prior works, which consider the number of data units (amount of sensor data generated by a node) transmitted/ received. Variable transmission power levels of the radio and accounting for the sensor energy consumption are other factors that make our problem formulation different from those in prior work. We prove that this problem is NP-complete and propose an algorithm to solve it. The performance of the proposed algorithm is experimentally evaluated using Jain's fairness index as a metric by implementing it on an actual testbed consisting of 20 sensor nodes and compared with those of the widely used shortest path tree (SPT) and random data collection tree (RDCT) algorithms. The energy consumption of different nodes under the proposed algorithm are shown to be more balanced than under SPT and RDCT algorithms. Also, the performance of the proposed algorithm in large networks is studied through simulations and is compared with those of the state-of-the-art RaSMaLai algorithm, SPT, minimum spanning tree, and RDCT based data collection schemes. Our simulations show that the proposed algorithm provides a significantly higher network lifetime compared to all the other considered data collection approaches.
Folding Polyominoes with Holes into a Cube
Venue: arXiv cs.CG 2020
Year: 2020

When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special \emph{simple} holes guarantee foldability.
Knowledge of Uncertain Worlds: Programming with Logical Constraints
Venue: arXiv cs.LO 2020
Year: 2020

Programming with logic for sophisticated applications must deal with recursion and negation, which together have created significant challenges in logic, leading to many different, conflicting semantics of rules. This paper describes a unified language, DA logic, for design and analysis logic, based on the unifying founded semantics and constraint semantics, that support the power and ease of programming with different intended semantics. The key idea is to provide meta-constraints, supports the use of uncertain information in the form of either undefined values or possible combinations of values or both, and promote the use of knowledge units that can be instantiated by any new predicates, including predicates with additional arguments.