OpenRaiser/Intern-Atlas huggingface dataset:
Splaying Preorders and Postorders
Venue: arXiv cs.DS 2019
Year: 2019

Let $T$ be a binary search tree. We prove two results about the behavior of the Splay algorithm (Sleator and Tarjan 1985). Our first result is that inserting keys into an empty binary search tree via splaying in the order of either $T$'s preorder or $T$'s postorder takes linear time. Our proof uses the fact that preorders and postorders are pattern-avoiding: i.e. they contain no subsequences that are order-isomorphic to $(2,3,1)$ and $(3,1,2)$, respectively. Pattern-avoidance implies certain constraints on the manner in which items are inserted. We exploit this structure with a simple potential function that counts inserted nodes lying on access paths to uninserted nodes. Our methods can likely be extended to permutations that avoid more general patterns. Second, if $T'$ is any other binary search tree with the same keys as $T$ and $T$ is weight-balanced (Nievergelt and Reingold 1973), then splaying $T$'s preorder sequence or $T$'s postorder sequence starting from $T'$ takes linear time. To prove this, we demonstrate that preorders and postorders of balanced search trees do not contain many large "jumps" in symmetric order, and exploit this fact by using the dynamic finger theorem (Cole et al. 2000). Both of our results provide further evidence in favor of the elusive "dynamic optimality conjecture."
GLOSS: Generative Latent Optimization of Sentence Representations
Venue: arXiv cs.CL 2019
Year: 2019

We propose a method to learn unsupervised sentence representations in a non-compositional manner based on Generative Latent Optimization. Our approach does not impose any assumptions on how words are to be combined into a sentence representation. We discuss a simple Bag of Words model as well as a variant that models word positions. Both are trained to reconstruct the sentence based on a latent code and our model can be used to generate text. Experiments show large improvements over the related Paragraph Vectors. Compared to uSIF, we achieve a relative improvement of 5% when trained on the same data and our method performs competitively to Sent2vec while trained on 30 times less data.
Multi-hop Federated Private Data Augmentation with Sample Compression
Venue: arXiv cs.LG 2019
Year: 2019

On-device machine learning (ML) has brought about the accessibility to a tremendous amount of data from the users while keeping their local data private instead of storing it in a central entity. However, for privacy guarantee, it is inevitable at each device to compensate for the quality of data or learning performance, especially when it has a non-IID training dataset. In this paper, we propose a data augmentation framework using a generative model: multi-hop federated augmentation with sample compression (MultFAug). A multi-hop protocol speeds up the end-to-end over-the-air transmission of seed samples by enhancing the transport capacity. The relaying devices guarantee stronger privacy preservation as well since the origin of each seed sample is hidden in those participants. For further privatization on the individual sample level, the devices compress their data samples. The devices sparsify their data samples prior to transmissions to reduce the sample size, which impacts the communication payload. This preprocessing also strengthens the privacy of each sample, which corresponds to the input perturbation for preserving sample privacy. The numerical evaluations show that the proposed framework significantly improves privacy guarantee, transmission delay, and local training performance with adjustment to the number of hops and compression rate.
Tracking sex: The implications of widespread sexual data leakage and tracking on porn websites
Venue: arXiv cs.CY 2019
Year: 2019

This paper explores tracking and privacy risks on pornography websites. Our analysis of 22,484 pornography websites indicated that 93% leak user data to a third party. Tracking on these sites is highly concentrated by a handful of major companies, which we identify. We successfully extracted privacy policies for 3,856 sites, 17% of the total. The policies were written such that one might need a two-year college education to understand them. Our content analysis of the sample's domains indicated 44.97% of them expose or suggest a specific gender/sexual identity or interest likely to be linked to the user. We identify three core implications of the quantitative results: 1) the unique/elevated risks of porn data leakage versus other types of data, 2) the particular risks/impact for vulnerable populations, and 3) the complications of providing consent for porn site users and the need for affirmative consent in these online sexual interactions.
A Relational Static Semantics for Call Graph Construction
Venue: arXiv cs.PL 2019
Year: 2019

The problem of resolving virtual method and interface calls in object-oriented languages has been a long standing challenge to the program analysis community. The complexities are due to various reasons, such as increased levels of class inheritance and polymorphism in large programs. In this paper, we propose a new approach called type flow analysis that represent propagation of type information between program variables by a group of relations without the help of a heap abstraction. We prove that regarding the precision on reachability of class information to a variable, our method produces results equivalent to that one can derive from a points-to analysis. Moreover, in practice, our method consumes lower time and space usage, as supported by the experimental results.
Characterizing Developer Use of Automatically Generated Patches
Venue: arXiv cs.SE 2019
Year: 2019

We present a study that characterizes the way developers use automatically generated patches when fixing software defects. Our study tasked two groups of developers with repairing defects in C programs. Both groups were provided with the defective line of code. One was also provided with five automatically generated and validated patches, all of which modified the defective line of code, and one of which was correct. Contrary to our initial expectations, the group with access to the generated patches did not produce more correct patches and did not produce patches in less time. We characterize the main behaviors observed in experimental subjects: a focus on understanding the defect and the relationship of the patches to the original source code. Based on this characterization, we highlight various potentially productive directions for future developer-centric automatic patch generation systems.
Metamorphic Testing of a Deep Learning based Forecaster
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we present the Metamorphic Testing of an in-use deep learning based forecasting application. The application looks at the past data of system characteristics (e.g. `memory allocation') to predict outages in the future. We focus on two statistical / machine learning based components - a) detection of co-relation between system characteristics and b) estimating the future value of a system characteristic using an LSTM (a deep learning architecture). In total, 19 Metamorphic Relations have been developed and we provide proofs & algorithms where applicable. We evaluated our method through two settings. In the first, we executed the relations on the actual application and uncovered 8 issues not known before. Second, we generated hypothetical bugs, through Mutation Testing, on a reference implementation of the LSTM based forecaster and found that 65.9% of the bugs were caught through the relations.
On improving learning capability of ELM and an application to brain-computer interface
Venue: arXiv cs.LG 2019
Year: 2019

As a type of pseudoinverse learning, extreme learning machine (ELM) is able to achieve high performances in a rapid pace on benchmark datasets. However, when it is applied to real life large data, decline related to low-convergence of singular value decomposition (SVD) method occurs. Our study aims to resolve this issue via replacing SVD with theoretically and empirically much efficient 5 number of methods: lower upper triangularization, Hessenberg decomposition, Schur decomposition, modified Gram Schmidt algorithm and Householder reflection. Comparisons were made on electroencephalography based brain-computer interface classification problem to decide which method is the most useful. Results of subject-based classifications suggested that if priority was given to training pace, Hessenberg decomposition method, whereas if priority was given to performances Householder reflection method should be preferred.
On the Relationships Between Average Channel Capacity, Average Bit Error Rate, Outage probability and Outage Capacity over Additive White Gaussian Noise Channels
Venue: arXiv cs.IT 2019
Year: 2019

In the theory of wireless communications, average performance measures (APMs) are widely utilized to quantify the performance gains/impairments in various fading environments under various scenarios, and to comprehend how the factors arising from design/implementation affect system performance. To the best of our knowledge, it has not been yet discovered in the literature how these APMs relate to each other. In this article, having been inspired by the work of Verdu et al. [1], we propose that one APM can be calculated using the other APMs instead of using the end-to-end SNR distribution. Particularly, using the Lamperti's transformation (LT), we propose a tractable approach, which we call LT-based APM analysis, to identify a relationship between any two given APMs such that it is irrespective of SNR distribution. Thereby, we introduce some novel relationships among average channel capacity (ACC), average bit error rate (ABER) and outage probability/capacity (OP/OC) performances, and accordingly present how to obtain ACC from ABER performance and how to obtain OP/OC from ACC performance in fading environments. We demonstrate that the ACC of any communications system can be evaluated empirically without using end-to-end SNR distribution. We consider some numerical examples and simulations to validate our newly derived relationships.
The Bach Doodle: Approachable music composition with machine learning at scale
Venue: arXiv cs.SD 2019
Year: 2019

To make music composition more approachable, we designed the first AI-powered Google Doodle, the Bach Doodle, where users can create their own melody and have it harmonized by a machine learning model Coconet (Huang et al., 2017) in the style of Bach. For users to input melodies, we designed a simplified sheet-music based interface. To support an interactive experience at scale, we re-implemented Coconet in TensorFlow.js (Smilkov et al., 2019) to run in the browser and reduced its runtime from 40s to 2s by adopting dilated depth-wise separable convolutions and fusing operations. We also reduced the model download size to approximately 400KB through post-training weight quantization. We calibrated a speed test based on partial model evaluation time to determine if the harmonization request should be performed locally or sent to remote TPU servers. In three days, people spent 350 years worth of time playing with the Bach Doodle, and Coconet received more than 55 million queries. Users could choose to rate their compositions and contribute them to a public dataset, which we are releasing with this paper. We hope that the community finds this dataset useful for applications ranging from ethnomusicological studies, to music education, to improving machine learning models.
A portable potentiometric electronic tongue leveraging smartphone and cloud platforms
Venue: arXiv cs.ET 2019
Year: 2019

Electronic tongues based on potentiometry offer the prospect of rapid and continuous chemical fingerprinting for portable and remote systems. The present contribution presents a technology platform including a miniaturized electronic tongue based on electropolymerized ion-sensitive films, microcontroller-based data acquisition, a smartphone interface and cloud computing back-end for data storage and deployment of machine learning models. The sensor array records a series of differential voltages without use of a true reference electrode and the resulting time-series potentiometry data is used to train supervised machine learning algorithms. For trained systems, inferencing tasks such as the classification of liquids are realized within less than 1 minute including data acquisition at the edge and inference using the cloud-deployed machine learning model. Preliminary demonstration of the complete electronic tongue technology stack is reported for the classification of beverages and mineral water.
AugLabel: Exploiting Word Representations to Augment Labels for Face Attribute Classification
Venue: arXiv cs.CV 2019
Year: 2019

Augmenting data in image space (eg. flipping, cropping etc) and activation space (eg. dropout) are being widely used to regularise deep neural networks and have been successfully applied on several computer vision tasks. Unlike previous works, which are mostly focused on doing augmentation in the aforementioned domains, we propose to do augmentation in label space. In this paper, we present a novel method to generate fixed dimensional labels with continuous values for images by exploiting the word2vec representations of the existing categorical labels. We then append these representations with existing categorical labels and train the model. We validated our idea on two challenging face attribute classification data sets viz. CelebA and LFWA. Our extensive experiments show that the augmented labels improve the performance of the competitive deep learning baseline and reduce the need of annotated real data up to 50%, while attaining a performance similar to the state-of-the-art methods.
Logic Conditionals, Supervenience, and Selection Tasks
Venue: arXiv cs.AI 2019
Year: 2019

Principles of cognitive economy would require that concepts about objects, properties and relations should be introduced only if they simplify the conceptualisation of a domain. Unexpectedly, classic logic conditionals, specifying structures holding within elements of a formal conceptualisation, do not always satisfy this crucial principle. The paper argues that this requirement is captured by supervenience, hereby further identified as a property necessary for compression. The resulting theory suggests an alternative explanation of the empirical experiences observable in Wason's selection tasks, associating human performance with conditionals on the ability of dealing with compression, rather than with logic necessity.
Hands Off my Database: Ransomware Detection in Databases through Dynamic Analysis of Query Sequences
Venue: arXiv cs.CR 2019
Year: 2019

Ransomware is an emerging threat which imposed a \$ 5 billion loss in 2017 and is predicted to hit \$ 11.5 billion in 2019. While initially targeting PC (client) platforms, ransomware recently made the leap to server-side databases - starting in January 2017 with the MongoDB Apocalypse attack, followed by other attack waves targeting a wide range of DB types such as MongoDB, MySQL, ElasticSearch, Cassandra, Hadoop, and CouchDB. While previous research has developed countermeasures against client-side ransomware (e.g., CryptoDrop and ShieldFS), the problem of server-side ransomware has received zero attention so far. In our work, we aim to bridge this gap and present DIMAQS (Dynamic Identification of Malicious Query Sequences), a novel anti-ransomware solution for databases. DIMAQS performs runtime monitoring of incoming queries and pattern matching using Colored Petri Nets (CPNs) for attack detection. Our system design exhibits several novel techniques to enable efficient detection of malicious query sequences globally (i.e., without limiting detection to distinct user connections). Our proof-of-concept implementation targets MySQL servers. The evaluation shows high efficiency with no false positives and no false negatives and very moderate performance overhead of under 5%. We will publish our data sets and implementation allowing the community to reproduce our tests and compare to our results.
Towards Robust Direction Invariance in Character Animation
Venue: arXiv cs.GR 2019
Year: 2019

In character animation, direction invariance is a desirable property. That is, a pose facing north and the same pose facing south are considered the same; a character that can walk to the north is expected to be able to walk to the south in a similar style. To achieve such direction invariance, the current practice is to remove the facing direction's rotation around the vertical axis before further processing. Such a scheme, however, is not robust for rotational behaviors in the sagittal plane. In search of a smooth scheme to achieve direction invariance, we prove that in general a singularity free scheme does not exist. We further connect the problem with the hairy ball theorem, which is better-known to the graphics community. Due to the nonexistence of a singularity free scheme, a general solution does not exist and we propose a remedy by using a properly-chosen motion direction that can avoid singularities for specific motions at hand. We perform comparative studies using two deep-learning based methods, one builds kinematic motion representations and the other learns physics-based controls. The results show that with our robust direction invariant features, both methods can achieve better results in terms of learning speed and/or final quality. We hope this paper can not only boost performance for character animation methods, but also help related communities currently not fully aware of the direction invariance problem to achieve more robust results.
Study of Max-Link Relay Selection with Buffers for Multi-Way Cooperative Multi-Antenna Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we present a relay-selection strategy for multi-way cooperative multi-antenna systems that are aided by a central processor node, where a cluster formed by two users is selected to simultaneously transmit to each other with the help of relays. In particular, we present a novel multi-way relay selection strategy based on the selection of the best link, exploiting the use of buffers and physical-layer network coding, that is called Multi-Way Buffer-Aided Max-Link (MW-Max-Link). We compare the proposed MW-Max-Link to existing techniques in terms of bit error rate, pairwise error probability, sum rate and computational complexity. Simulations are then employed to evaluate the performance of the proposed and existing techniques.
A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
Venue: arXiv cs.LG 2019
Year: 2019

A wide range of fundamental machine learning tasks that are addressed by the maximum a posteriori estimation can be reduced to a general minimum conical hull problem. The best-known solution to tackle general minimum conical hull problems is the divide-and-conquer anchoring learning scheme (DCA), whose runtime complexity is polynomial in size. However, big data is pushing these polynomial algorithms to their performance limits. In this paper, we propose a sublinear classical algorithm to tackle general minimum conical hull problems when the input has stored in a sample-based low-overhead data structure. The algorithm's runtime complexity is polynomial in the rank and polylogarithmic in size. The proposed algorithm achieves the exponential speedup over DCA and, therefore, provides advantages for high dimensional problems.
A Self-Attentive model for Knowledge Tracing
Venue: arXiv cs.LG 2019
Year: 2019

Knowledge tracing is the task of modeling each student's mastery of knowledge concepts (KCs) as (s)he engages with a sequence of learning activities. Each student's knowledge is modeled by estimating the performance of the student on the learning activities. It is an important research area for providing a personalized learning platform to students. In recent years, methods based on Recurrent Neural Networks (RNN) such as Deep Knowledge Tracing (DKT) and Dynamic Key-Value Memory Network (DKVMN) outperformed all the traditional methods because of their ability to capture complex representation of human learning. However, these methods face the issue of not generalizing well while dealing with sparse data which is the case with real-world data as students interact with few KCs. In order to address this issue, we develop an approach that identifies the KCs from the student's past activities that are \textit{relevant} to the given KC and predicts his/her mastery based on the relatively few KCs that it picked. Since predictions are made based on relatively few past activities, it handles the data sparsity problem better than the methods based on RNN. For identifying the relevance between the KCs, we propose a self-attention based approach, Self Attentive Knowledge Tracing (SAKT). Extensive experimentation on a variety of real-world dataset shows that our model outperforms the state-of-the-art models for knowledge tracing, improving AUC by 4.43% on average.
Distributed data storage for modern astroparticle physics experiments
Venue: arXiv cs.DC 2019
Year: 2019

The German-Russian Astroparticle Data Life Cycle Initiative is an international project launched in 2018. The Initiative aims to develop technologies that provide a unified approach to data management, as well as to demonstrate their applicability on the example of two large astrophysical experiments - KASCADE and TAIGA. One of the key points of the project is the development of a distributed storage, which, on the one hand, will allow data of several experiments to be combined into a single repository with unified interface, and on the other hand, will provide data to all participants of experimental groups for multi-messenger analysis. Our approach to storage design is based on the single write-multiple read (SWMR) model for accessing raw or centrally processed data for further analysis. The main feature of the distributed storage is the ability to extract data either as a collection of files or as aggregated events from different sources. In the last case the storage provides users with a special service that aggregates data from different storages into a single sample. Thanks to this feature, multi-messenger methods used for more sophisticated data exploration can be applied. Users can use both Web-interface and Application Programming Interface (API) for accessing the storage. In this paper we describe the architecture of a distributed data storage for astroparticle physics and discuss the current status of our work.
Coprocessors: failures and successes
Venue: arXiv cs.AR 2019
Year: 2019

The appearance and disappearance of coprocessors by integration into the CPU, the success or failure of coprocessors are examined by summarizing their characteristics from the mainframes of the 1960s. The coprocessors most particularly reviewed are the IBM 360 and CDC-6600 I/O processors, the Intel 8087 math coprocessor, the Cell processor, the Intel Xeon Phi coprocessors, the GPUs, the FPGAs, and the coprocessors of manycores SW26010 and Pezy SC-2 used in high-ranked supercomputers in the TOP500 or Green500. The conditions for a coprocessor to be viable in the medium or long-term are defined.