OpenRaiser/Intern-Atlas huggingface dataset:
Sorted Top-k in Rounds
Venue: arXiv cs.DS 2019
Year: 2019

We consider the sorted top-$k$ problem whose goal is to recover the top-$k$ items with the correct order out of $n$ items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to algorithms with a constant number of rounds $r$ and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noiseless, we characterize how the optimal sample complexity depends on the number of rounds (up to a polylogarithmic factor for general $r$ and up to a constant factor for $r=1$ or 2). In particular, the sample complexity is $Θ(n^2)$ for $r=1$, $Θ(n\sqrt{k} + n^{4/3})$ for $r=2$ and $\tildeΘ\left(n^{2/r} k^{(r-1)/r} + n\right)$ for $r \geq 3$. We extend our results of sorted top-$k$ to the noisy case where each comparison is correct with probability $2/3$. When $r=1$ or 2, we show that the sample complexity gets an extra $Θ(\log(k))$ factor when we transition from the noiseless case to the noisy case. We also prove new results for top-$k$ and sorting in the noisy case. We believe our techniques can be generally useful for understanding the trade-off between round complexities and sample complexities of rank aggregation problems.
Reinforcement Knowledge Graph Reasoning for Explainable Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

Recent advances in personalized recommendation have sparked great interest in the exploitation of rich structured information provided by knowledge graphs. Unlike most existing approaches that only focus on leveraging knowledge graphs for more accurate recommendation, we perform explicit reasoning with knowledge for decision making so that the recommendations are generated and supported by an interpretable causal inference procedure. To this end, we propose a method called Policy-Guided Path Reasoning (PGPR), which couples recommendation and interpretability by providing actual paths in a knowledge graph. Our contributions include four aspects. We first highlight the significance of incorporating knowledge graphs into recommendation to formally define and interpret the reasoning process. Second, we propose a reinforcement learning (RL) approach featuring an innovative soft reward strategy, user-conditional action pruning and a multi-hop scoring function. Third, we design a policy-guided graph search algorithm to efficiently and effectively sample reasoning paths for recommendation. Finally, we extensively evaluate our method on several large-scale real-world benchmark datasets, obtaining favorable results compared with state-of-the-art methods.
A Simple Text Mining Approach for Ranking Pairwise Associations in Biomedical Applications
Venue: arXiv cs.IR 2019
Year: 2019

We present a simple text mining method that is easy to implement, requires minimal data collection and preparation, and is easy to use for proposing ranked associations between a list of target terms and a key phrase. We call this method KinderMiner, and apply it to two biomedical applications. The first application is to identify relevant transcription factors for cell reprogramming, and the second is to identify potential drugs for investigation in drug repositioning. We compare the results from our algorithm to existing data and state-of-the-art algorithms, demonstrating compelling results for both application areas. While we apply the algorithm here for biomedical applications, we argue that the method is generalizable to any available corpus of sufficient size.
Artificial Intelligence Enabled Material Behavior Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Artificial Intelligence and Machine Learning algorithms have considerable potential to influence the prediction of material properties. Additive materials have a unique property prediction challenge in the form of surface roughness effects on fatigue behavior of structural components. Traditional approaches using finite element methods to calculate stress risers associated with additively built surfaces have been challenging due to the computational resources required, often taking over a day to calculate a single sample prediction. To address this performance challenge, Deep Learning has been employed to enable low cycle fatigue life prediction in additive materials in a matter of seconds.
Programming Technologies for the Development of Web-Based Platform for Digital Psychological Tools
Venue: arXiv cs.HC 2019
Year: 2019

The choice of the tools and programming technologies for information systems creation is relevant. For every projected system, it is necessary to define a number of criteria for development environment, used libraries and technologies. The paper describes the choice of technological solutions using the example of the developed web-based platform of the Russian Academy of Education. This platform is used to provide information support for the activities of psychologists in their research (including population and longitudinal researches). There are following system features: large scale and significant amount of developing time that needs implementation and ensuring the guaranteed computing reliability of a wide range of digital tools used in psychological research; ensuring functioning in different environments when conducting mass research in schools that have different characteristics of computing resources and communication channels; possibility of services scaling; security and privacy of data; use of technologies and programming tools that would ensure the compatibility and conversion of data with other tools of psychological research processing. Some criteria were introduced for the developed system. These criteria take into account the feature of the functioning and life cycle of the software. A specific example shows the selection of appropriate technological solutions.
Data Conversion in Area-Constrained Applications: the Wireless Network-on-Chip Case
Venue: arXiv cs.ET 2019
Year: 2019

Network-on-Chip (NoC) is currently the paradigm of choice to interconnect the different components of System-on-Chips (SoCs) or Chip Multiprocessors (CMPs). As the levels of integration continue to grow, however, current NoCs face significant scalability limitations and have prompted research in novel interconnect technologies. Among these, wireless intra-chip communications have been under intense scrutiny due to their low latency broadcast and architectural flexibility. Thus far, the practicality of the idea has been studied from the RF front-end and the network interface perspectives, whereas little to no attention has been placed on another essential component: the data converters. This article aims to fill this gap by providing a comprehensive analysis of the requirements of the scenario, as well as of the current performance and cost trends of Analog-to-Digital Converters (ADCs). Based on Murmann's data, we demonstrate that ADCs will not be a roadblock for the realization of wireless intra-chip communications although current designs do not meet their demands fully.
Loop Programming Practices that Simplify Quicksort Implementations
Venue: arXiv cs.DS 2019
Year: 2019

Quicksort algorithm with Hoare's partition scheme is traditionally implemented with nested loops. In this article, we present loop programming and refactoring techniques that lead to simplified implementation for Hoare's quicksort algorithm consisting of a single loop. We believe that the techniques are beneficial for general programming and may be used for the discovery of more novel algorithms.
Efficient Evaluation-Time Uncertainty Estimation by Improved Distillation
Venue: arXiv cs.LG 2019
Year: 2019

In this work we aim to obtain computationally-efficient uncertainty estimates with deep networks. For this, we propose a modified knowledge distillation procedure that achieves state-of-the-art uncertainty estimates both for in and out-of-distribution samples. Our contributions include a) demonstrating and adapting to distillation's regularization effect b) proposing a novel target teacher distribution c) a simple augmentation procedure to improve out-of-distribution uncertainty estimates d) shedding light on the distillation procedure through comprehensive set of experiments.
Interpretable Few-Shot Learning via Linear Distillation
Venue: arXiv cs.LG 2019
Year: 2019

It is important to develop mathematically tractable models than can interpret knowledge extracted from the data and provide reasonable predictions. In this paper, we present a Linear Distillation Learning, a simple remedy to improve the performance of linear neural networks. Our approach is based on using a linear function for each class in a dataset, which is trained to simulate the output of a teacher linear network for each class separately. We tested our model on MNIST and Omniglot datasets in the Few-Shot learning manner. It showed better results than other interpretable models such as classical Logistic Regression.
CoopSubNet: Cooperating Subnetwork for Data-Driven Regularization of Deep Networks under Limited Training Budgets
Venue: arXiv cs.CV 2019
Year: 2019

Deep networks are an integral part of the current machine learning paradigm. Their inherent ability to learn complex functional mappings between data and various target variables, while discovering hidden, task-driven features, makes them a powerful technology in a wide variety of applications. Nonetheless, the success of these networks typically relies on the availability of sufficient training data to optimize a large number of free parameters while avoiding overfitting, especially for networks with large capacity. In scenarios with limited training budgets, e.g., supervised tasks with limited labeled samples, several generic and/or task-specific regularization techniques, including data augmentation, have been applied to improve the generalization of deep networks.Typically such regularizations are introduced independently of that data or training scenario, and must therefore be tuned, tested, and modified to meet the needs of a particular network. In this paper, we propose a novel regularization framework that is driven by the population-level statistics of the feature space to be learned. The regularization is in the form of a \textbf{cooperating subnetwork}, which is an auto-encoder architecture attached to the feature space and trained in conjunction with the primary network. We introduce the architecture and training methodology and demonstrate the effectiveness of the proposed cooperative network-based regularization in a variety of tasks and architectures from the literature. Our code is freely available at \url{https://github.com/riddhishb/CoopSubNet
Cued@wmt19:ewc&lms
Venue: arXiv cs.CL 2019
Year: 2019

Two techniques provide the fabric of the Cambridge University Engineering Department's (CUED) entry to the WMT19 evaluation campaign: elastic weight consolidation (EWC) and different forms of language modelling (LMs). We report substantial gains by fine-tuning very strong baselines on former WMT test sets using a combination of checkpoint averaging and EWC. A sentence-level Transformer LM and a document-level LM based on a modified Transformer architecture yield further gains. As in previous years, we also extract $n$-gram probabilities from SMT lattices which can be seen as a source-conditioned $n$-gram LM.
Trading Location Data with Bounded Personalized Privacy Loss
Venue: arXiv cs.CR 2019
Year: 2019

As personal data have been the new oil of the digital era, there is a growing trend perceiving personal data as a commodity. Although some people are willing to trade their personal data for money, they might still expect limited privacy loss, and the maximum tolerable privacy loss varies with each individual. In this paper, we propose a framework that enables individuals to trade their personal data with bounded personalized privacy loss, which raises technical challenges in the aspects of budget allocation and arbitrage-freeness. To deal with those challenges,we propose two arbitrage-free trading mechanisms with different advantages.
A Comparison of Word-based and Context-based Representations for Classification Problems in Health Informatics
Venue: arXiv cs.CL 2019
Year: 2019

Distributed representations of text can be used as features when training a statistical classifier. These representations may be created as a composition of word vectors or as context-based sentence vectors. We compare the two kinds of representations (word versus context) for three classification problems: influenza infection classification, drug usage classification and personal health mention classification. For statistical classifiers trained for each of these problems, context-based representations based on ELMo, Universal Sentence Encoder, Neural-Net Language Model and FLAIR are better than Word2Vec, GloVe and the two adapted using the MESH ontology. There is an improvement of 2-4% in the accuracy when these context-based representations are used instead of word-based representations.
Transfer Learning in Biomedical Natural Language Processing: An Evaluation of BERT and ELMo on Ten Benchmarking Datasets
Venue: arXiv cs.CL 2019
Year: 2019

Inspired by the success of the General Language Understanding Evaluation benchmark, we introduce the Biomedical Language Understanding Evaluation (BLUE) benchmark to facilitate research in the development of pre-training language representations in the biomedicine domain. The benchmark consists of five tasks with ten datasets that cover both biomedical and clinical texts with different dataset sizes and difficulties. We also evaluate several baselines based on BERT and ELMo and find that the BERT model pre-trained on PubMed abstracts and MIMIC-III clinical notes achieves the best results. We make the datasets, pre-trained models, and codes publicly available at https://github.com/ncbi-nlp/BLUE_Benchmark.
New constructions of asymptotically optimal codebooks via character sums over a local ring
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we present explicit description on the additive characters, multiplicative characters and Gauss sums over a local ring. As an application, based on the additive characters and multiplicative characters satisfying certain conditions, two new constructions of complex codebooks over a local ring are introduced. With these two constructions, we obtain two families of codebooks achieving asymptotically optimal with respect to the Welch bound. It's worth mentioning that the codebooks constructed in this paper have new parameters.
Parametric Modelling Within Immersive Environments: Building a Bridge Between Existing Tools and Virtual Reality Headsets
Venue: arXiv cs.HC 2019
Year: 2019

Even though architectural modelling radically evolved over the course of its history, the current integration of Augmented Reality (AR) and Virtual Reality(VR) components in the corresponding design tasks is mostly limited to enhancing visualisation. Little to none of these tools attempt to tackle the challenge of modelling within immersive environments, that calls for new input modalities in order to move away from the traditional mouse and keyboard combination. In fact, relying on 2D devices for 3D manipulations does not seem to be effective as it does not offer the same degrees of freedom. We therefore present a solution that brings VR modelling capabilities to Grasshopper, a popular parametric design tool. Together with its associated proof-of-concept application, our extension offers a glimpse at new perspectives in that field. By taking advantage of them,one can edit geometries with real-time feedback on the generated models, without ever leaving the virtual environment. The distinctive characteristics of VR applications provide a range of benefits without obstructing design activities. The designer can indeed experience the architectural models at full scale from a realistic point-of-view and truly feels immersed right next to them.
Two modes of recognition: algebra, coalgebra, and languages
Venue: arXiv cs.LO 2019
Year: 2019

The aim of the paper is to build a connection between two approaches towards categorical language theory: the coalgebraic and algebraic language theory for monads. For a pair of monads modelling the branching and the linear type we defined regular maps that generalize regular languages known in classical non-deterministic automata theory. These maps are behaviours of certain automata (i.e. they possess a coalgebraic nature), yet they arise from Eilenberg-Moore algebras and their homomorphisms (by exploiting duality between the category of Eilenberg-Moore algebras and saturated coalgebras). Given some additional assumptions, we show that regular maps form a certain subcategory of the Kleisli category for the monad which is the composition of the branching and linear type. Moreover, we state a Kleene-like theorem characterising the regular morphisms category in terms of the smallest subcategory closed under certain operations. Additionally, whenever the branching type monad is taken to be the powerset monad, we show that regular maps are described as maps recognized by certain functors whose codomains are categories with all finite hom-sets. We instantiate our framework on classical non-deterministic automata, tree automata, fuzzy automata and weighted automata.
Temporally-Biased Sampling Schemes for Online Model Management
Venue: arXiv cs.DB 2019
Year: 2019

To maintain the accuracy of supervised learning models in the presence of evolving data streams, we provide temporally-biased sampling schemes that weight recent data most heavily, with inclusion probabilities for a given data item decaying over time according to a specified "decay function". We then periodically retrain the models on the current sample. This approach speeds up the training process relative to training on all of the data. Moreover, time-biasing lets the models adapt to recent changes in the data while---unlike in a sliding-window approach---still keeping some old data to ensure robustness in the face of temporary fluctuations and periodicities in the data values. In addition, the sampling-based approach allows existing analytic algorithms for static data to be applied to dynamic streaming data essentially without change. We provide and analyze both a simple sampling scheme (T-TBS) that probabilistically maintains a target sample size and a novel reservoir-based scheme (R-TBS) that is the first to provide both control over the decay rate and a guaranteed upper bound on the sample size. If the decay function is exponential, then control over the decay rate is complete, and R-TBS maximizes both expected sample size and sample-size stability. For general decay functions, the actual item inclusion probabilities can be made arbitrarily close to the nominal probabilities, and we provide a scheme that allows a trade-off between sample footprint and sample-size stability. The R-TBS and T-TBS schemes are of independent interest, extending the known set of unequal-probability sampling schemes. We discuss distributed implementation strategies; experiments in Spark illuminate the performance and scalability of the algorithms, and show that our approach can increase machine learning robustness in the face of evolving data.
RodSteward: A Design-to-Assembly System for Fabrication using 3D-Printed Joints and Precision-Cut Rods
Venue: arXiv cs.GR 2019
Year: 2019

We present RodSteward, a design-to-assembly system for creating furniture-scale structures composed of 3D printed joints and precision-cut rods. The RodSteward systems consists of: RSDesigner, a fabrication-aware design interface that visualizes accurate geometries during edits and identifies infeasible designs; physical fabrication of parts via novel fully automatic construction of solid 3D-printable joint geometries and automatically generated cutting plans for rods; and RSAssembler, a guided-assembly interface that prompts the user to place parts in order while showing a focus+context visualization of the assembly in progress. We demonstrate the effectiveness of our tools with a number of example constructions of varying complexity, style and parameter choices.
Querying a Matrix through Matrix-Vector Products
Venue: arXiv cs.CC 2019
Year: 2019

We consider algorithms with access to an unknown matrix $M\in\mathbb{F}^{n \times d}$ via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \mathbf{v}^q$, and observes $M\mathbf{v}^1,\ldots, M\mathbf{v}^q$. Here the $\mathbf{v}^i$ can be randomized as well as chosen adaptively as a function of $ M\mathbf{v}^1,\ldots,M\mathbf{v}^{i-1}$. Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number $q$ of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix $M$; to compute the AND/OR/Parity of each column or row of $M$, to decide whether there are identical columns or rows in $M$ or whether $M$ is symmetric, diagonal, or unitary; or to compute whether a graph defined by $M$ is connected or triangle-free. We also show separations for algorithms that are allowed to obtain matrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. Surprisingly, this fundamental model does not appear to have been studied on its own, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
Probing the Mystery of Cryptocurrency Theft: An Investigation into Methods for Taint Analysis
Venue: arXiv cs.CR 2019
Year: 2019

Since the creation of Bitcoin, transaction tracking is one of the prominent means for following the movement of Bitcoins involved in illegal activities. Although every Bitcoin transaction is recorded in the blockchain database, which is transparent for anyone to observe and analyse, Bitcoin's pseudonymity system and transaction obscuring techniques still allow criminals to disguise their transaction trail. While there have been a few attempts to develop tracking methods, there is no accepted evaluation method to measure their accuracy. Therefore, this paper investigates strategies for transaction tracking by introducing two new tainting methods, and proposes an address profiling approach with a metrics-based evaluation framework. We use our approach and framework to compare the accuracy of our new tainting methods with the previous tainting techniques, using data from two real Bitcoin theft transactions and several related control transactions.