OpenRaiser/Intern-Atlas huggingface dataset:
Simple and Fast Algorithms for Interactive Machine Learning with Random Counter-examples
Venue: arXiv cs.LG 2019
Year: 2019

This work describes simple and efficient algorithms for interactively learning non-binary concepts in the learning from random counter-examples (LRC) model. Here, learning takes place from random counter-examples that the learner receives in response to their proper equivalence queries. In this context, the learning time is defined as the number of counter-examples needed by the learner to identify the target concept. Such learning is particularly suited for online ranking, classification, clustering, etc., where machine learning models must be used before they are fully trained. We provide two simple LRC algorithms, deterministic and randomized, for exactly learning non-binary target concepts for any concept class $H$. We show that both of these algorithms have an $\mathcal{O}(\log{}|H|)$ asymptotically optimal average learning time. This solves an open problem on the existence of an efficient LRC randomized algorithm while simplifying and generalizing previous results. We also show that the expected learning time of any arbitrary LRC algorithm can be upper bounded by $\mathcal{O}(\frac{1}ε\log{\frac{|H|}δ})$, where $ε$ and $δ$ are the allowed learning error and failure probability respectively. This shows that LRC interactive learning is at least as efficient as non-interactive Probably Approximately Correct (PAC) learning. Our simulations show that in practice, these algorithms outperform their theoretical bounds.
Consistency and validity of interdisciplinarity measures
Venue: arXiv cs.DL 2019
Year: 2019

Measuring interdisciplinarity is a pertinent but challenging issue in quantitative studies of science. There seems to be a consensus in the literature that the concept of interdisciplinarity is multifaceted and ambiguous. Unsurprisingly, various different measures of interdisciplinarity have been proposed. However, few studies have thoroughly examined the validity and relations between these measures. In this study, we present a systematic review of these interdisciplinarity measures and explore their inherent relations. We examine these measures in relation to the Web of Science journal subject categories. Our results corroborate recent claims that the current measurements of interdisciplinarity in science studies are both confusing and unsatisfying. We find surprisingly deviant results when comparing measures that supposedly should capture similar features or dimensions of the concept of interdisciplinarity. We therefore argue that the current measurements of interdisciplinarity should be interpreted with much caution in science and evaluation studies, or in relation to science policies. We also question the validity of current measures and argue that we do not need more of the same, but rather something very different in order to be able to measure the multidimensional and complex construct of interdisciplinarity.
Fault Tolerant Adaptive Parallel and Distributed Simulation through Functional Replication
Venue: arXiv cs.DC 2019
Year: 2019

This paper presents FT-GAIA, a software-based fault-tolerant parallel and distributed simulation middleware. FT-GAIA has being designed to reliably handle Parallel And Distributed Simulation (PADS) models, which are needed to properly simulate and analyze complex systems arising in any kind of scientific or engineering field. PADS takes advantage of multiple execution units run in multicore processors, cluster of workstations or HPC systems. However, large computing systems, such as HPC systems that include hundreds of thousands of computing nodes, have to handle frequent failures of some components. To cope with this issue, FT-GAIA transparently replicates simulation entities and distributes them on multiple execution nodes. This allows the simulation to tolerate crash-failures of computing nodes. Moreover, FT-GAIA offers some protection against Byzantine failures, since interaction messages among the simulated entities are replicated as well, so that the receiving entity can identify and discard corrupted messages. Results from an analytical model and from an experimental evaluation show that FT-GAIA provides a high degree of fault tolerance, at the cost of a moderate increase in the computational load of the execution units.
Orbital Stabilization of Nonlinear Systems via the Immersion and Invariance Technique
Venue: arXiv cs.SY 2019
Year: 2019

Immersion and Invariance is a technique for the design of stabilizing and adaptive controllers and state observers for nonlinear systems. In all these applications the problem considered is the stabilization of equilibrium points. Motivated by some modern applications we show that the technique can also be used to solve the problem of orbital stabilization, where the final objective is to generate periodic solutions that are attractive. The feasibility of our result is illustrated with some classical mechanical engineering and electronics examples.
A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
Venue: arXiv cs.LG 2019
Year: 2019

We study the problem of optimizing a function under a \emph{budgeted number of evaluations}. We only assume that the function is \emph{locally} smooth around one of its global optima. The difficulty of optimization is measured in terms of 1) the amount of \emph{noise} $b$ of the function evaluation and 2) the local smoothness, $d$, of the function. A smaller $d$ results in smaller optimization error. We come with a new, simple, and parameter-free approach. First, for all values of $b$ and $d$, this approach recovers at least the state-of-the-art regret guarantees. Second, our approach additionally obtains these results while being \textit{agnostic} to the values of both $b$ and $d$. This leads to the first algorithm that naturally adapts to an \textit{unknown} range of noise $b$ and leads to significant improvements in a moderate and low-noise regime. Third, our approach also obtains a remarkable improvement over the state-of-the-art SOO algorithm when the noise is very low which includes the case of optimization under deterministic feedback ($b=0$). There, under our minimal local smoothness assumption, this improvement is of exponential magnitude and holds for a class of functions that covers the vast majority of functions that practitioners optimize ($d=0$). We show that our algorithmic improvement is borne out in experiments as we empirically show faster convergence on common benchmarks.
Super-Resolution Blind Channel-and-Signal Estimation for Massive MIMO with One-Dimensional Antenna Array
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study blind channel-and-signal estimation by exploiting the burst-sparse structure of angular-domain propagation channels in massive MIMO systems. The state-of-the-art approach utilizes the structured channel sparsity by sampling the angular-domain channel representation with a uniform angle-sampling grid, a.k.a. virtual channel representation. However, this approach is only applicable to uniform linear arrays and may cause a substantial performance loss due to the mismatch between the virtual representation and the true angle information. To tackle these challenges, we propose a sparse channel representation with a super-resolution sampling grid and a hidden Markovian support. Based on this, we develop a novel approximate inference based blind estimation algorithm to estimate the channel and the user signals simultaneously, with emphasis on the adoption of the expectation-maximization method to learn the angle information. Furthermore, we demonstrate the low-complexity implementation of our algorithm, making use of factor graph and message passing principles to compute the marginal posteriors. Numerical results show that our proposed method significantly reduces the estimation error compared to the state-of-the-art approach under various settings, which verifies the efficiency and robustness of our method.
AlphaSeq: Sequence Discovery with Deep Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

Sequences play an important role in many applications and systems. Discovering sequences with desired properties has long been an interesting intellectual pursuit. This paper puts forth a new paradigm, AlphaSeq, to discover desired sequences algorithmically using deep reinforcement learning (DRL) techniques. AlphaSeq treats the sequence discovery problem as an episodic symbol-filling game, in which a player fills symbols in the vacant positions of a sequence set sequentially during an episode of the game. Each episode ends with a completely-filled sequence set, upon which a reward is given based on the desirability of the sequence set. AlphaSeq models the game as a Markov Decision Process (MDP), and adapts the DRL framework of AlphaGo to solve the MDP. Sequences discovered improve progressively as AlphaSeq, starting as a novice, learns to become an expert game player through many episodes of game playing. Compared with traditional sequence construction by mathematical tools, AlphaSeq is particularly suitable for problems with complex objectives intractable to mathematical analysis. We demonstrate the searching capabilities of AlphaSeq in two applications: 1) AlphaSeq successfully rediscovers a set of ideal complementary codes that can zero-force all potential interferences in multi-carrier CDMA systems. 2) AlphaSeq discovers new sequences that triple the signal-to-interference ratio -- benchmarked against the well-known Legendre sequence -- of a mismatched filter estimator in pulse compression radar systems.
CEM-RL: Combining evolutionary and gradient-based methods for policy search
Venue: arXiv cs.LG 2019
Year: 2019

Deep neuroevolution and deep reinforcement learning (deep RL) algorithms are two popular approaches to policy search. The former is widely applicable and rather stable, but suffers from low sample efficiency. By contrast, the latter is more sample efficient, but the most sample efficient variants are also rather unstable and highly sensitive to hyper-parameter setting. So far, these families of methods have mostly been compared as competing tools. However, an emerging approach consists in combining them so as to get the best of both worlds. Two previously existing combinations use either an ad hoc evolutionary algorithm or a goal exploration process together with the Deep Deterministic Policy Gradient (DDPG) algorithm, a sample efficient off-policy deep RL algorithm. In this paper, we propose a different combination scheme using the simple cross-entropy method (CEM) and Twin Delayed Deep Deterministic policy gradient (td3), another off-policy deep RL algorithm which improves over ddpg. We evaluate the resulting method, cem-rl, on a set of benchmarks classically used in deep RL. We show that cem-rl benefits from several advantages over its competitors and offers a satisfactory trade-off between performance and sample efficiency.
The Parikh Property for Weighted Context-Free Grammars
Venue: arXiv cs.FL 2019
Year: 2019

Parikh's Theorem states that every context-free grammar (CFG) is equivalent to some regular CFG when the ordering of symbols in the words is ignored. The same is not true for the so-called weighted CFGs, which additionally assign a weight to each grammar rule. If the result holds for a given weighted CFG $G$, we say that $G$ satisfies the Parikh property. We prove constructively that the Parikh property holds for every weighted nonexpansive CFG. We also give a decision procedure for the property when the weights are over the rationals.
Mixing patterns and individual differences in networks
Venue: arXiv cs.SI 2019
Year: 2019

We study mixing patterns in networks, meaning the propensity for nodes of different kinds to connect to one another. The phenomenon of assortative mixing, whereby nodes prefer to connect to others that are similar to themselves, has been widely studied, but here we go further and examine how and to what extent nodes that are otherwise similar can have different preferences. Many individuals in a friendship network, for instance, may prefer friends who are roughly the same age as themselves, but some may display a preference for older or younger friends. We introduce a network model that captures this behavior and a method for fitting it to empirical network data. We propose metrics to characterize the mean and variation of mixing patterns and show how to infer their values from the fitted model, either using maximum-likelihood estimates of model parameters or in a Bayesian framework that does not require fixing any parameters.
An Analysis of Approaches Taken in the ACM RecSys Challenge 2018 for Automatic Music Playlist Continuation
Venue: arXiv cs.IR 2019
Year: 2019

The ACM Recommender Systems Challenge 2018 focused on the task of automatic music playlist continuation, which is a form of the more general task of sequential recommendation. Given a playlist of arbitrary length with some additional meta-data, the task was to recommend up to 500 tracks that fit the target characteristics of the original playlist. For the RecSys Challenge, Spotify released a dataset of one million user-generated playlists. Participants could compete in two tracks, i.e., main and creative tracks. Participants in the main track were only allowed to use the provided training set, however, in the creative track, the use of external public sources was permitted. In total, 113 teams submitted 1,228 runs to the main track; 33 teams submitted 239 runs to the creative track. The highest performing team in the main track achieved an R-precision of 0.2241, an NDCG of 0.3946, and an average number of recommended songs clicks of 1.784. In the creative track, an R-precision of 0.2233, an NDCG of 0.3939, and a click rate of 1.785 was obtained by the best team. This article provides an overview of the challenge, including motivation, task definition, dataset description, and evaluation. We further report and analyze the results obtained by the top performing teams in each track and explore the approaches taken by the winners. We finally summarize our key findings, discuss generalizability of approaches and results to domains other than music, and list the open avenues and possible future directions in the area of automatic playlist continuation.
BRAVO -- Biased Locking for Reader-Writer Locks
Venue: arXiv cs.OS 2019
Year: 2019

Designers of modern reader-writer locks confront a difficult trade-off related to reader scalability. Locks that have a compact memory representation for active readers will typically suffer under high intensity read-dominated workloads when the "reader indicator"' state is updated frequently by a diverse set of threads, causing cache invalidation and coherence traffic. Other designs, such as cohort reader-writer locks, use distributed reader indicators, one per NUMA node. This improves reader-reader scalability, but also increases the size of each lock instance. We propose a simple transformation BRAVO, that augments any existing reader-writer lock, adding just two integer fields to the lock instance. Readers make their presence known to writers by hashing their thread's identity with the lock address, forming an index into a visible readers table. Readers attempt to install the lock address into that element in the table, making their existence known to potential writers. All locks and threads in an address space can share the visible readers table. Updates by readers tend to be diffused over the table, resulting in a NUMA-friendly design. Crucially, readers of the same lock tend to write to different locations in the array, reducing coherence traffic. Specifically, BRAVO allows a simple compact lock to be augmented so as to provide scalable concurrent reading but with only a modest increase in footprint.
Extreme Augmentation : Can deep learning based medical image segmentation be trained using a single manually delineated scan?
Venue: arXiv cs.CV 2019
Year: 2019

Yes, it can. Data augmentation is perhaps the oldest preprocessing step in computer vision literature. Almost every computer vision model trained on imaging data uses some form of augmentation. In this paper, we use the inter-vertebral disk segmentation task alongside a deep residual U-Net as the learning model, to explore the effectiveness of augmentation. In the extreme, we observed that a model trained on patches extracted from just one scan, with each patch augmented 50 times; achieved a Dice score of 0.73 in a validation set of 40 cases. Qualitative evaluation indicated a clinically usable segmentation algorithm, which appropriately segments regions of interest, alongside limited false positive specks. When the initial patches are extracted from nine scans the average Dice coefficient jumps to 0.86 and most of the false positives disappear. While this still falls short of state-of-the-art deep learning based segmentation of discs reported in literature, qualitative examination reveals that it does yield segmentation, which can be amended by expert clinicians with minimal effort to generate additional data for training improved deep models. Extreme augmentation of training data, should thus be construed as a strategy for training deep learning based algorithms, when very little manually annotated data is available to work with. Models trained with extreme augmentation can then be used to accelerate the generation of manually labelled data. Hence, we show that extreme augmentation can be a valuable tool in addressing scaling up small imaging data sets to address medical image segmentation tasks.
Inhibited Softmax for Uncertainty Estimation in Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

We present a new method for uncertainty estimation and out-of-distribution detection in neural networks with softmax output. We extend softmax layer with an additional constant input. The corresponding additional output is able to represent the uncertainty of the network. The proposed method requires neither additional parameters nor multiple forward passes nor input preprocessing nor out-of-distribution datasets. We show that our method performs comparably to more computationally expensive methods and outperforms baselines on our experiments from image recognition and sentiment analysis domains.
From Soft Classifiers to Hard Decisions: How fair can we be?
Venue: arXiv cs.LG 2019
Year: 2019

A popular methodology for building binary decision-making classifiers in the presence of imperfect information is to first construct a non-binary "scoring" classifier that is calibrated over all protected groups, and then to post-process this score to obtain a binary decision. We study the feasibility of achieving various fairness properties by post-processing calibrated scores, and then show that deferring post-processors allow for more fairness conditions to hold on the final decision. Specifically, we show: 1. There does not exist a general way to post-process a calibrated classifier to equalize protected groups' positive or negative predictive value (PPV or NPV). For certain "nice" calibrated classifiers, either PPV or NPV can be equalized when the post-processor uses different thresholds across protected groups, though there exist distributions of calibrated scores for which the two measures cannot be both equalized. When the post-processing consists of a single global threshold across all groups, natural fairness properties, such as equalizing PPV in a nontrivial way, do not hold even for "nice" classifiers. 2. When the post-processing is allowed to `defer' on some decisions (that is, to avoid making a decision by handing off some examples to a separate process), then for the non-deferred decisions, the resulting classifier can be made to equalize PPV, NPV, false positive rate (FPR) and false negative rate (FNR) across the protected groups. This suggests a way to partially evade the impossibility results of Chouldechova and Kleinberg et al., which preclude equalizing all of these measures simultaneously. We also present different deferring strategies and show how they affect the fairness properties of the overall system. We evaluate our post-processing techniques using the COMPAS data set from 2016.
Seq2Slate: Re-ranking and Slate Optimization with RNNs
Venue: arXiv cs.IR 2019
Year: 2019

Ranking is a central task in machine learning and information retrieval. In this task, it is especially important to present the user with a slate of items that is appealing as a whole. This in turn requires taking into account interactions between items, since intuitively, placing an item on the slate affects the decision of which other items should be placed alongside it. In this work, we propose a sequence-to-sequence model for ranking called seq2slate. At each step, the model predicts the next `best' item to place on the slate given the items already selected. The sequential nature of the model allows complex dependencies between the items to be captured directly in a flexible and scalable way. We show how to learn the model end-to-end from weak supervision in the form of easily obtained click-through data. We further demonstrate the usefulness of our approach in experiments on standard ranking benchmarks as well as in a real-world recommendation system.
Classical linear logic, cobordisms and categorical semantics of categorial grammars
Venue: arXiv cs.LO 2019
Year: 2019

We propose a categorial grammar based on classical multiplicative linear logic. This can be seen as an extension of abstract categorial grammars (ACG) and is at least as expressive. However, constituents of {\it linear logic grammars (LLG)} are not abstract $λ$-terms, but simply tuples of words with labeled endpoints, we call them {\it multiwords}. At least, this gives a concrete and intuitive representation of ACG. A key observation is that the class of multiwords has a fundamental algebraic structure. Namely, multiwords can be organized in a category, very similar to the category of topological cobordisms. This category is symmetric monoidal closed and compact closed and thus is a model of linear $λ$-calculus and classical linear logic. We think that this category is interesting on its own right. In particular, it might provide categorical representation for other formalisms. On the other hand, many models of language semantics are based on commutative logic or, more generally, on symmetric monoidal closed categories. But the category of {\it word cobordisms} is a category of language elements, which is itself symmetric monoidal closed and independent of any grammar. Thus, it might prove useful in understanding language semantics as well.
Distributed Reconfiguration of Maximal Independent Sets
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we investigate a distributed maximal independent set (MIS) reconfiguration problem, in which there are two maximal independent sets for which every node is given its membership status, and the nodes need to communicate with their neighbors in order to find a reconfiguration schedule that switches from the first MIS to the second. Such a schedule is a list of independent sets that is restricted by forbidding two neighbors to change their membership status at the same step. In addition, these independent sets should provide some covering guarantee. We show that obtaining an actual MIS (and even a 3-dominating set) in each intermediate step is impossible. However, we provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible, as we fully characterize. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in $O(\texttt{MIS}+\texttt{R32})$ rounds, where $\texttt{MIS}$ is the complexity of finding an MIS in a worst-case graph and $\texttt{R32}$ is the complexity of finding a $(3,2)$-ruling set. For bounded degree graphs, this is $O(\log^*n)$ rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.