OpenRaiser/Intern-Atlas huggingface dataset:
Reachability in two-parametric timed automata with one parameter is EXPSPACE-complete
Venue: arXiv cs.FL 2020
Year: 2020

Parametric timed automata (PTA) are an extension of timed automata in which clocks can be compared against parameters. The reachability problem asks for the existence of an assignment of the parameters to the non-negative integers such that reachability holds in the underlying timed automaton. The reachability problem for PTA is long known to be undecidable, already over three parametric clocks. A few years ago, Bundala and Ouaknine proved that for PTA over two parametric clocks and one parameter the reachability problem is decidable and also showed a lower bound for the complexity class PSPACE^NEXP. Our main result is that the reachability problem for two-parametric timed automata with one parameter is EXPSPACE-complete. Our contribution is two-fold. For the EXPSPACE lower bound we make use of deep results from complexity theory, namely a serializability characterization of EXPSPACE (based on Barrington's Theorem) and a logspace translation of numbers in chinese remainder representation to binary representation. For the EXPSPACE upper bound, we give a careful exponential time reduction from PTA over two parametric clocks and one parameter to a slight subclass of parametric one-counter automata (POCA) over one parameter based on a minor adjustment of a construction due to Bundala and Ouaknine. We provide a series of techniques to partition a fictitious run of a POCA into several carefully chosen subruns that allow us to prove that it is sufficient to consider a parameter value of exponential magnitude only. This allows us to show a doubly-exponential upper bound on the value of the only parameter of a PTA over two parametric clocks and one parameter. We hope that extensions of our techniques lead to finally establishing decidability of the long-standing open problem of reachability in parametric timed automata with two parametric clocks (and arbitrarily many parameters).
Reducing Inference Latency with Concurrent Architectures for Image Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Satisfying the high computation demand of modern deep learning architectures is challenging for achieving low inference latency. The current approaches in decreasing latency only increase parallelism within a layer. This is because architectures typically capture a single-chain dependency pattern that prevents efficient distribution with a higher concurrency (i.e., simultaneous execution of one inference among devices). Such single-chain dependencies are so widespread that even implicitly biases recent neural architecture search (NAS) studies. In this visionary paper, we draw attention to an entirely new space of NAS that relaxes the single-chain dependency to provide higher concurrency and distribution opportunities. To quantitatively compare these architectures, we propose a score that encapsulates crucial metrics such as communication, concurrency, and load balancing. Additionally, we propose a new generator and transformation block that consistently deliver superior architectures compared to current state-of-the-art methods. Finally, our preliminary results show that these new architectures reduce the inference latency and deserve more attention.
The Teacher-Student Chatroom Corpus
Venue: arXiv cs.CL 2020
Year: 2020

The Teacher-Student Chatroom Corpus (TSCC) is a collection of written conversations captured during one-to-one lessons between teachers and learners of English. The lessons took place in an online chatroom and therefore involve more interactive, immediate and informal language than might be found in asynchronous exchanges such as email correspondence. The fact that the lessons were one-to-one means that the teacher was able to focus exclusively on the linguistic abilities and errors of the student, and to offer personalised exercises, scaffolding and correction. The TSCC contains more than one hundred lessons between two teachers and eight students, amounting to 13.5K conversational turns and 133K words: it is freely available for research use. We describe the corpus design, data collection procedure and annotations added to the text. We perform some preliminary descriptive analyses of the data and consider possible uses of the TSCC.
Streaming Attention-Based Models with Augmented Memory for End-to-End Speech Recognition
Venue: arXiv cs.CL 2020
Year: 2020

Attention-based models have been gaining popularity recently for their strong performance demonstrated in fields such as machine translation and automatic speech recognition. One major challenge of attention-based models is the need of access to the full sequence and the quadratically growing computational cost concerning the sequence length. These characteristics pose challenges, especially for low-latency scenarios, where the system is often required to be streaming. In this paper, we build a compact and streaming speech recognition system on top of the end-to-end neural transducer architecture with attention-based modules augmented with convolution. The proposed system equips the end-to-end models with the streaming capability and reduces the large footprint from the streaming attention-based model using augmented memory. On the LibriSpeech dataset, our proposed system achieves word error rates 2.7% on test-clean and 5.8% on test-other, to our best knowledge the lowest among streaming approaches reported so far.
PLAS: Latent Action Space for Offline Reinforcement Learning
Venue: arXiv cs.RO 2020
Year: 2020

The goal of offline reinforcement learning is to learn a policy from a fixed dataset, without further interactions with the environment. This setting will be an increasingly more important paradigm for real-world applications of reinforcement learning such as robotics, in which data collection is slow and potentially dangerous. Existing off-policy algorithms have limited performance on static datasets due to extrapolation errors from out-of-distribution actions. This leads to the challenge of constraining the policy to select actions within the support of the dataset during training. We propose to simply learn the Policy in the Latent Action Space (PLAS) such that this requirement is naturally satisfied. We evaluate our method on continuous control benchmarks in simulation and a deformable object manipulation task with a physical robot. We demonstrate that our method provides competitive performance consistently across various continuous control tasks and different types of datasets, outperforming existing offline reinforcement learning methods with explicit constraints. Videos and code are available at https://sites.google.com/view/latent-policy.
HackerScope: The Dynamics of a Massive Hacker Online Ecosystem
Venue: arXiv cs.CR 2020
Year: 2020

Authors of malicious software are not hiding as much as one would assume: they have a visible online footprint. Apart from online forums, this footprint appears in software development platforms, where authors create publicly-accessible malware repositories to share and collaborate. With the exception of a few recent efforts, the existence and the dynamics of this community has received surprisingly limited attention. The goal of our work is to analyze this ecosystem of hackers in order to: (a) understand their collaborative patterns, and (b) identify and profile its most influential authors. We develop HackerScope, a systematic approach for analyzing the dynamics of this hacker ecosystem. Leveraging our targeted data collection, we conduct an extensive study of 7389 authors of malware repositories on GitHub, which we combine with their activity on four security forums. From a modeling point of view, we study the ecosystem using three network representations: (a) the author-author network, (b) the author-repository network, and (c) cross-platform egonets. Our analysis leads to the following key observations: (a) the ecosystem is growing at an accelerating rate as the number of new malware authors per year triples every 2 years, (b) it is highly collaborative, more so than the rest of GitHub authors, and (c) it includes influential and professional hackers. We find 30 authors maintain an online "brand" across GitHub and our security forums. Our study is a significant step towards using public online information for understanding the malicious hacker community.
Graph-Based Neural Network Models with Multiple Self-Supervised Auxiliary Tasks
Venue: arXiv cs.LG 2020
Year: 2020

Self-supervised learning is currently gaining a lot of attention, as it allows neural networks to learn robust representations from large quantities of unlabeled data. Additionally, multi-task learning can further improve representation learning by training networks simultaneously on related tasks, leading to significant performance improvements. In this paper, we propose three novel self-supervised auxiliary tasks to train graph-based neural network models in a multi-task fashion. Since Graph Convolutional Networks are among the most promising approaches for capturing relationships among structured data points, we use them as a building block to achieve competitive results on standard semi-supervised graph classification tasks.
Towards transformation-resilient provenance detection of digital media
Venue: arXiv cs.LG 2020
Year: 2020

Advancements in deep generative models have made it possible to synthesize images, videos and audio signals that are difficult to distinguish from natural signals, creating opportunities for potential abuse of these capabilities. This motivates the problem of tracking the provenance of signals, i.e., being able to determine the original source of a signal. Watermarking the signal at the time of signal creation is a potential solution, but current techniques are brittle and watermark detection mechanisms can easily be bypassed by applying post-processing transformations (cropping images, shifting pitch in the audio etc.). In this paper, we introduce ReSWAT (Resilient Signal Watermarking via Adversarial Training), a framework for learning transformation-resilient watermark detectors that are able to detect a watermark even after a signal has been through several post-processing transformations. Our detection method can be applied to domains with continuous data representations such as images, videos or sound signals. Experiments on watermarking image and audio signals show that our method can reliably detect the provenance of a signal, even if it has been through several post-processing transformations, and improve upon related work in this setting. Furthermore, we show that for specific kinds of transformations (perturbations bounded in the L2 norm), we can even get formal guarantees on the ability of our model to detect the watermark. We provide qualitative examples of watermarked image and audio samples in https://drive.google.com/open?id=1-yZ0WIGNu2Iez7UpXBjtjVgZu3jJjFga.
Analyzing 'Near Me' Services: Potential for Exposure Bias in Location-based Retrieval
Venue: arXiv cs.IR 2020
Year: 2020

The proliferation of smartphones has led to the increased popularity of location-based search and recommendation systems. Online platforms like Google and Yelp allow location-based search in the form of nearby feature to query for hotels or restaurants in the vicinity. Moreover, hotel booking platforms like Booking[dot]com, Expedia, or Trivago allow travelers searching for accommodations using either their desired location as a search query or near a particular landmark. Since the popularity of different locations in a city varies, certain locations may get more queries than other locations. Thus, the exposure received by different establishments at these locations may be very different from their intrinsic quality as captured in their ratings. Today, many small businesses (shops, hotels, or restaurants) rely on such online platforms for attracting customers. Thus, receiving less exposure than that is expected can be unfavorable for businesses. It could have a negative impact on their revenue and potentially lead to economic starvation or even shutdown. By gathering and analyzing data from three popular platforms, we observe that many top-rated hotels and restaurants get less exposure vis-a-vis their quality, which could be detrimental for them. Following a meritocratic notion, we define and quantify such exposure disparity due to location-based searches on these platforms. We attribute this exposure disparity mainly to two kinds of biases -- Popularity Bias and Position Bias. Our experimental evaluation on multiple datasets reveals that although the platforms are doing well in delivering distance-based results, exposure disparity exists for individual businesses and needs to be reduced for business sustainability.
Synthesis of SQL Queries from South African Local Language Narrations
Venue: arXiv cs.CY 2020
Year: 2020

English remains the language of choice for database courses and widely used for instruction in nearly all South African universities, and also in many countries. Novice programmers of native origins are mostly taught Structured Query Language (SQL) through English as the medium of instruction. Consequently, this creates a myriad of problems in understanding the syntax of SQL as most native learners are not too proficient in English. This could affect a learner's ability in comprehending SQL syntaxes. To resolve this problem, this work proposes a tool called local language narrations (Local-Nar-SQL) to SQL that uses a type of Finite Machine, such as a Jumping Finite Automaton to translate local language narratives into SQL queries. Further, the generated query extracts information from a sample database and presents output to the learner. This paper is an extension of work originally presented in a previous study in this field. A survey involving 145 participants concluded that the majority found Local-Nar-SQL to be helpful in understanding SQL queries from local languages. If the proposed tool is used as a learning aid, native learners will find it easier to work with SQL, which will eliminate many of the barriers faced with English proficiencies in programming pedagogies.
Few-shot Object Grounding and Mapping for Natural Language Robot Instruction Following
Venue: arXiv cs.RO 2020
Year: 2020

We study the problem of learning a robot policy to follow natural language instructions that can be easily extended to reason about new objects. We introduce a few-shot language-conditioned object grounding method trained from augmented reality data that uses exemplars to identify objects and align them to their mentions in instructions. We present a learned map representation that encodes object locations and their instructed use, and construct it from our few-shot grounding output. We integrate this mapping approach into an instruction-following policy, thereby allowing it to reason about previously unseen objects at test-time by simply adding exemplars. We evaluate on the task of learning to map raw observations and instructions to continuous control of a physical quadcopter. Our approach significantly outperforms the prior state of the art in the presence of new objects, even when the prior approach observes all objects during training.
Cost-Sensitive Machine Learning Classification for Mass Tuberculosis Verbal Screening
Venue: arXiv cs.LG 2020
Year: 2020

Score-based algorithms for tuberculosis (TB) verbal screening perform poorly, causing misclassification that leads to missed cases and unnecessary costly laboratory tests for false positives. We compared score-based classification defined by clinicians to machine learning classification such as SVM-RBF, logistic regression, and XGBoost. We restricted our analyses to data from adults, the population most affected by TB, and investigated the difference between untuned and unweighted classifiers to the cost-sensitive ones. Predictions were compared with the corresponding GeneXpert MTB/Rif results. After adjusting the weight of the positive class to 40 for XGBoost, we achieved 96.64% sensitivity and 35.06% specificity. As such, the sensitivity of our identifier increased by 1.26% while specificity increased by 13.19% in absolute value compared to the traditional score-based method defined by our clinicians. Our approach further demonstrated that only 2000 data points were sufficient to enable the model to converge. The results indicate that even with limited data we can actually devise a better method to identify TB suspects from verbal screening.
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
Venue: arXiv cs.GT 2020
Year: 2020

We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(\frac{3}{4}-\frac{1}{240}+\varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $\exp(Ω(\varepsilon^2 \cdot m))$ communication, whereas a non-truthful algorithm by Dobzinski and Schapira [SODA 2006] and Feige [2009] is already known to achieve a $\frac{3}{4}$-approximation in $poly(m)$ communication. We obtain our separation by proving that any {simultaneous} protocol ({not} necessarily truthful) which guarantees a $(\frac{3}{4}-\frac{1}{240}+\varepsilon)$-approximation requires communication $\exp(Ω(\varepsilon^2 \cdot m))$. The taxation complexity framework of Dobzinski [FOCS 2016] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).
Model-Driven Synthesis for Programming Tutors
Venue: arXiv cs.HC 2020
Year: 2020

When giving automated feedback to a student working on a beginner's exercise, many programming tutors run into a completeness problem. On the one hand, we want a student to experiment freely. On the other hand, we want a student to write her program in such a way that we can provide constructive feedback. We propose to investigate how we can overcome this problem by using program synthesis, which we use to generate correct solutions that closely match a student program, and give feedback based on the results.
2CP: Decentralized Protocols to Transparently Evaluate Contributivity in Blockchain Federated Learning Environments
Venue: arXiv cs.LG 2020
Year: 2020

Federated Learning harnesses data from multiple sources to build a single model. While the initial model might belong solely to the actor bringing it to the network for training, determining the ownership of the trained model resulting from Federated Learning remains an open question. In this paper we explore how Blockchains (in particular Ethereum) can be used to determine the evolving ownership of a model trained with Federated Learning. Firstly, we use the step-by-step evaluation metric to assess the relative contributivities of participants in a Federated Learning process. Next, we introduce 2CP, a framework comprising two novel protocols for Blockchained Federated Learning, which both reward contributors with shares in the final model based on their relative contributivity. The Crowdsource Protocol allows an actor to bring a model forward for training, and use their own data to evaluate the contributions made to it. Potential trainers are guaranteed a fair share of the resulting model, even in a trustless setting. The Consortium Protocol gives trainers the same guarantee even when no party owns the initial model and no evaluator is available. We conduct experiments with the MNIST dataset that reveal sound contributivity scores resulting from both Protocols by rewarding larger datasets with greater shares in the model. Our experiments also showed the necessity to pair 2CP with a robust model aggregation mechanism to discard low quality inputs coming from model poisoning attacks.
Domain Adaptation Gaze Estimation by Embedding with Prediction Consistency
Venue: arXiv cs.CV 2020
Year: 2020

Gaze is the essential manifestation of human attention. In recent years, a series of work has achieved high accuracy in gaze estimation. However, the inter-personal difference limits the reduction of the subject-independent gaze estimation error. This paper proposes an unsupervised method for domain adaptation gaze estimation to eliminate the impact of inter-personal diversity. In domain adaption, we design an embedding representation with prediction consistency to ensure that the linear relationship between gaze directions in different domains remains consistent on gaze space and embedding space. Specifically, we employ source gaze to form a locally linear representation in the gaze space for each target domain prediction. Then the same linear combinations are applied in the embedding space to generate hypothesis embedding for the target domain sample, remaining prediction consistency. The deviation between the target and source domain is reduced by approximating the predicted and hypothesis embedding for the target domain sample. Guided by the proposed strategy, we design Domain Adaptation Gaze Estimation Network(DAGEN), which learns embedding with prediction consistency and achieves state-of-the-art results on both the MPIIGaze and the EYEDIAP datasets.
Learning Frame Similarity using Siamese networks for Audio-to-Score Alignment
Venue: arXiv cs.SD 2020
Year: 2020

Audio-to-score alignment aims at generating an accurate mapping between a performance audio and the score of a given piece. Standard alignment methods are based on Dynamic Time Warping (DTW) and employ handcrafted features, which cannot be adapted to different acoustic conditions. We propose a method to overcome this limitation using learned frame similarity for audio-to-score alignment. We focus on offline audio-to-score alignment of piano music. Experiments on music data from different acoustic conditions demonstrate that our method achieves higher alignment accuracy than a standard DTW-based method that uses handcrafted features, and generates robust alignments whilst being adaptable to different domains at the same time.
Placement in Integrated Circuits using Cyclic Reinforcement Learning and Simulated Annealing
Venue: arXiv cs.AI 2020
Year: 2020

Physical design and production of Integrated Circuits (IC) is becoming increasingly more challenging as the sophistication in IC technology is steadily increasing. Placement has been one of the most critical steps in IC physical design. Through decades of research, partition-based, analytical-based and annealing-based placers have been enriching the placement solution toolbox. However, open challenges including long run time and lack of ability to generalize continue to restrict wider applications of existing placement tools. We devise a learning-based placement tool based on cyclic application of Reinforcement Learning (RL) and Simulated Annealing (SA) by leveraging the advancement of RL. Results show that the RL module is able to provide a better initialization for SA and thus leads to a better final placement design. Compared to other recent learning-based placers, our method is majorly different with its combination of RL and SA. It leverages the RL model's ability to quickly get a good rough solution after training and the heuristic's ability to realize greedy improvements in the solution.
Safety Synthesis Sans Specification
Venue: arXiv cs.FL 2020
Year: 2020

We define the problem of learning a transducer ${S}$ from a target language $U$ containing possibly conflicting transducers, using membership queries and conjecture queries. The requirement is that the language of ${S}$ be a subset of $U$. We argue that this is a natural question in many situations in hardware and software verification. We devise a learning algorithm for this problem and show that its time and query complexity is polynomial with respect to the rank of the target language, its incompatibility measure, and the maximal length of a given counterexample. We report on experiments conducted with a prototype implementation.