OpenRaiser/Intern-Atlas huggingface dataset:
Collaborative Spatial Reuse in Wireless Networks via Selfish Multi-Armed Bandits
Venue: arXiv cs.NI 2018
Year: 2018

Next-generation wireless deployments are characterized by being dense and uncoordinated, which often leads to inefficient use of resources and poor performance. To solve this, we envision the utilization of completely decentralized mechanisms to enable Spatial Reuse (SR). In particular, we focus on dynamic channel selection and Transmission Power Control (TPC). We rely on Reinforcement Learning (RL), and more specifically on Multi-Armed Bandits (MABs), to allow networks to learn their best configuration. In this work, we study the exploration-exploitation trade-off by means of the $\varepsilon$-greedy, EXP3, UCB and Thompson sampling action-selection, and compare their performance. In addition, we study the implications of selecting actions simultaneously in an adversarial setting (i.e., concurrently), and compare it with a sequential approach. Our results show that optimal proportional fairness can be achieved, even when no information about neighboring networks is available to the learners and Wireless Networks (WNs) operate selfishly. However, there is high temporal variability in the throughput experienced by the individual networks, specially for $\varepsilon$-greedy and EXP3. These strategies, contrary to UCB and Thompson sampling, base their operation on the absolute experienced reward, rather than on its distribution. We identify the cause of this variability to be the adversarial setting of our setup in which the set of most played actions provide intermittent good/poor performance depending on the neighboring decisions. We also show that learning sequentially, even if using a selfish strategy, contributes to minimize this variability. The sequential approach is therefore shown to effectively deal with the challenges posed by the adversarial settings that are typically found in decentralized WNs.
Sentiment Protocol: A Decentralized Protocol Leveraging Crowd Sourced Wisdom
Venue: arXiv cs.CY 2018
Year: 2018

The wisdom of the crowd is a valuable asset in today's society. It is not only important in predicting elections but also plays an essential role in marketing and the financial industry. Having a trustworthy source of opinion can make forecasts more accurate and markets predictable. Until now, a fundamental problem of surveys is the lack of incentives for participants to provide accurate information. Classical solutions like small monetary rewards or the chance of winning a prize are often not very attractive for participants. More attractive solutions, such as prediction markets, face the issue of illegality and are often unavailable. In this work, we present a solution that unites the advantages from classical polling and prediction markets via a customizable incentivization framework. Apart from predicting events, this framework can also be used to govern decentralized autonomous organizations.
Multi-Task Learning by Deep Collaboration and Application in Facial Landmark Detection
Venue: arXiv cs.CV 2018
Year: 2018

Convolutional neural networks (CNNs) have become the most successful approach in many vision-related domains. However, they are limited to domains where data is abundant. Recent works have looked at multi-task learning (MTL) to mitigate data scarcity by leveraging domain-specific information from related tasks. In this paper, we present a novel soft-parameter sharing mechanism for CNNs in a MTL setting, which we refer to as Deep Collaboration. We propose taking into account the notion that task relevance depends on depth by using lateral transformation blocs with skip connections. This allows extracting task-specific features at various depth without sacrificing features relevant to all tasks. We show that CNNs connected with our Deep Collaboration obtain better accuracy on facial landmark detection with related tasks. We finally verify that our approach effectively allows knowledge sharing by showing depth-specific influence of tasks that we know are related.
Automata-Guided Hierarchical Reinforcement Learning for Skill Composition
Venue: arXiv cs.AI 2018
Year: 2018

Skills learned through (deep) reinforcement learning often generalizes poorly across domains and re-training is necessary when presented with a new task. We present a framework that combines techniques in \textit{formal methods} with \textit{reinforcement learning} (RL). The methods we provide allows for convenient specification of tasks with logical expressions, learns hierarchical policies (meta-controller and low-level controllers) with well-defined intrinsic rewards, and construct new skills from existing ones with little to no additional exploration. We evaluate the proposed methods in a simple grid world simulation as well as a more complicated kitchen environment in AI2Thor
Pomegranate: fast and flexible probabilistic modeling in python
Venue: arXiv cs.AI 2018
Year: 2018

We present pomegranate, an open source machine learning package for probabilistic modeling in Python. Probabilistic modeling encompasses a wide range of methods that explicitly describe uncertainty using probability distributions. Three widely used probabilistic models implemented in pomegranate are general mixture models, hidden Markov models, and Bayesian networks. A primary focus of pomegranate is to abstract away the complexities of training models from their definition. This allows users to focus on specifying the correct model for their application instead of being limited by their understanding of the underlying algorithms. An aspect of this focus involves the collection of additive sufficient statistics from data sets as a strategy for training models. This approach trivially enables many useful learning strategies, such as out-of-core learning, minibatch learning, and semi-supervised learning, without requiring the user to consider how to partition data or modify the algorithms to handle these tasks themselves. pomegranate is written in Cython to speed up calculations and releases the global interpreter lock to allow for built-in multithreaded parallelism, making it competitive with---or outperform---other implementations of similar algorithms. This paper presents an overview of the design choices in pomegranate, and how they have enabled complex features to be supported by simple code.
Automatic calcium scoring in low-dose chest CT using deep neural networks with dilated convolutions
Venue: arXiv cs.CV 2018
Year: 2018

Heavy smokers undergoing screening with low-dose chest CT are affected by cardiovascular disease as much as by lung cancer. Low-dose chest CT scans acquired in screening enable quantification of atherosclerotic calcifications and thus enable identification of subjects at increased cardiovascular risk. This paper presents a method for automatic detection of coronary artery, thoracic aorta and cardiac valve calcifications in low-dose chest CT using two consecutive convolutional neural networks. The first network identifies and labels potential calcifications according to their anatomical location and the second network identifies true calcifications among the detected candidates. This method was trained and evaluated on a set of 1744 CT scans from the National Lung Screening Trial. To determine whether any reconstruction or only images reconstructed with soft tissue filters can be used for calcification detection, we evaluated the method on soft and medium/sharp filter reconstructions separately. On soft filter reconstructions, the method achieved F1 scores of 0.89, 0.89, 0.67, and 0.55 for coronary artery, thoracic aorta, aortic valve and mitral valve calcifications, respectively. On sharp filter reconstructions, the F1 scores were 0.84, 0.81, 0.64, and 0.66, respectively. Linearly weighted kappa coefficients for risk category assignment based on per subject coronary artery calcium were 0.91 and 0.90 for soft and sharp filter reconstructions, respectively. These results demonstrate that the presented method enables reliable automatic cardiovascular risk assessment in all low-dose chest CT scans acquired for lung cancer screening.
Detection for 5G-NOMA: An Online Adaptive Machine Learning Approach
Venue: arXiv cs.LG 2018
Year: 2018

Non-orthogonal multiple access (NOMA) has emerged as a promising radio access technique for enabling the performance enhancements promised by the fifth-generation (5G) networks in terms of connectivity, low latency, and high spectrum efficiency. In the NOMA uplink, successive interference cancellation (SIC) based detection with device clustering has been suggested. In the case of multiple receive antennas, SIC can be combined with the minimum mean-squared error (MMSE) beamforming. However, there exists a tradeoff between the NOMA cluster size and the incurred SIC error. Larger clusters lead to larger errors but they are desirable from the spectrum efficiency and connectivity point of view. We propose a novel online learning based detection for the NOMA uplink. In particular, we design an online adaptive filter in the sum space of linear and Gaussian reproducing kernel Hilbert spaces (RKHSs). Such a sum space design is robust against variations of a dynamic wireless network that can deteriorate the performance of a purely nonlinear adaptive filter. We demonstrate by simulations that the proposed method outperforms the MMSE-SIC based detection for large cluster sizes.
Don't Decay the Learning Rate, Increase the Batch Size
Venue: arXiv cs.LG 2018
Year: 2018

It is common practice to decay the learning rate. Here we show one can usually obtain the same learning curve on both training and test sets by instead increasing the batch size during training. This procedure is successful for stochastic gradient descent (SGD), SGD with momentum, Nesterov momentum, and Adam. It reaches equivalent test accuracies after the same number of training epochs, but with fewer parameter updates, leading to greater parallelism and shorter training times. We can further reduce the number of parameter updates by increasing the learning rate $ε$ and scaling the batch size $B \propto ε$. Finally, one can increase the momentum coefficient $m$ and scale $B \propto 1/(1-m)$, although this tends to slightly reduce the test accuracy. Crucially, our techniques allow us to repurpose existing training schedules for large batch training with no hyper-parameter tuning. We train ResNet-50 on ImageNet to $76.1\%$ validation accuracy in under 30 minutes.
User Scheduling for Millimeter Wave MIMO Communications with Low-Resolution ADCs
Venue: arXiv cs.IT 2018
Year: 2018

In millimeter wave (mmWave) systems, we investigate uplink user scheduling when a basestation employs low-resolution analog-to-digital converters (ADCs) with a large number of antennas. To reduce power consumption in the receiver, low-resolution ADCs can be a potential solution for mmWave systems in which many antennas are likely to be deployed to compensate for the large path loss. Due to quantization error, we show that the channel structure in the beamspace, in addition to the channel magnitude and beamspace orthogonality, plays a key role in maximizing the achievable rates of scheduled users. Consequently, we derive the optimal criteria with respect to the channel structure in the beamspace that maximizes the uplink sum rate for multi-user multiple input multiple output (MIMO) systems with a zero-forcing receiver. Leveraging the derived criteria, we propose an efficient scheduling algorithm for mmWave systems with low-resolution ADCs. Numerical results validate that the proposed algorithm outperforms conventional user scheduling methods in terms of the sum rate.
A Socially-Aware Incentive Mechanism for Mobile Crowdsensing Service Market
Venue: arXiv cs.GT 2018
Year: 2018

Mobile Crowdsensing has shown a great potential to address large-scale problems by allocating sensing tasks to pervasive Mobile Users (MUs). The MUs will participate in a Crowdsensing platform if they can receive satisfactory reward. In this paper, in order to effectively and efficiently recruit sufficient MUs, i.e., participants, we investigate an optimal reward mechanism of the monopoly Crowdsensing Service Provider (CSP). We model the rewarding and participating as a two-stage game, and analyze the MUs' participation level and the CSP's optimal reward mechanism using backward induction. At the same time, the reward is designed taking the underlying social network effects amid the mobile social network into account, for motivating the participants. Namely, one MU will obtain additional benefits from information contributed or shared by local neighbours in social networks. We derive the analytical expressions for the discriminatory reward as well as uniform reward with complete information, and approximations of reward incentive with incomplete information. Performance evaluation reveals that the network effects tremendously stimulate higher mobile participation level and greater revenue of the CSP. In addition, the discriminatory reward enables the CSP to extract greater surplus from this Crowdsensing service market.
Approximate Supermodularity Bounds for Experimental Design
Venue: arXiv cs.LG 2018
Year: 2018

This work provides performance guarantees for the greedy solution of experimental design problems. In particular, it focuses on A- and E-optimal designs, for which typical guarantees do not apply since the mean-square error and the maximum eigenvalue of the estimation error covariance matrix are not supermodular. To do so, it leverages the concept of approximate supermodularity to derive non-asymptotic worst-case suboptimality bounds for these greedy solutions. These bounds reveal that as the SNR of the experiments decreases, these cost functions behave increasingly as supermodular functions. As such, greedy A- and E-optimal designs approach (1-1/e)-optimality. These results reconcile the empirical success of greedy experimental design with the non-supermodularity of the A- and E-optimality criteria.
Approximating Partition Functions in Constant Time
Venue: arXiv cs.LG 2018
Year: 2018

We study approximations of the partition function of dense graphical models. Partition functions of graphical models play a fundamental role is statistical physics, in statistics and in machine learning. Two of the main methods for approximating the partition function are Markov Chain Monte Carlo and Variational Methods. An impressive body of work in mathematics, physics and theoretical computer science provides conditions under which Markov Chain Monte Carlo methods converge in polynomial time. These methods often lead to polynomial time approximation algorithms for the partition function in cases where the underlying model exhibits correlation decay. There are very few theoretical guarantees for the performance of variational methods. One exception is recent results by Risteski (2016) who considered dense graphical models and showed that using variational methods, it is possible to find an $O(εn)$ additive approximation to the log partition function in time $n^{O(1/ε^2)}$ even in a regime where correlation decay does not hold. We show that under essentially the same conditions, an $O(εn)$ additive approximation of the log partition function can be found in constant time, independent of $n$. In particular, our results cover dense Ising and Potts models as well as dense graphical models with $k$-wise interaction. They also apply for low threshold rank models.
Computational Complexity Aspects of Point Visibility Graphs
Venue: arXiv cs.DM 2018
Year: 2018

A point visibility graph is a graph induced by a set of points in the plane where the vertices of the graph represent the points in the point set and two vertices are adjacent if and only if no other point from the point set lies on the line segment between the two corresponding points. The set of all point visibility graphs form a graph class which is examined from a computational complexity perspective in this paper. We show NP-hardness for several classic graph problems on point visibility graphs such as Feedback Vertex Set, Longest Induced Path, Bisection and $\mathcal{F}$-free Vertex Deletion (for certain sets $\mathcal{F}$). Furthermore, we consider the complexity of the Dominating Set problem on point visibility graphs of points on a grid.
On the complexity of hazard-free circuits
Venue: arXiv cs.CC 2018
Year: 2018

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result we establish the NP-completeness of several hazard detection problems.
$A^{4}NT$: Author Attribute Anonymity by Adversarial Training of Neural Machine Translation
Venue: arXiv cs.CR 2018
Year: 2018

Text-based analysis methods allow to reveal privacy relevant author attributes such as gender, age and identify of the text's author. Such methods can compromise the privacy of an anonymous author even when the author tries to remove privacy sensitive content. In this paper, we propose an automatic method, called Adversarial Author Attribute Anonymity Neural Translation ($A^4NT$), to combat such text-based adversaries. We combine sequence-to-sequence language models used in machine translation and generative adversarial networks to obfuscate author attributes. Unlike machine translation techniques which need paired data, our method can be trained on unpaired corpora of text containing different authors. Importantly, we propose and evaluate techniques to impose constraints on our $A^4NT$ to preserve the semantics of the input text. $A^4NT$ learns to make minimal changes to the input text to successfully fool author attribute classifiers, while aiming to maintain the meaning of the input. We show through experiments on two different datasets and three settings that our proposed method is effective in fooling the author attribute classifiers and thereby improving the anonymity of authors.
Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index
Venue: arXiv cs.DS 2018
Year: 2018

Finding approximate occurrences of a pattern in a text using a full-text index is a central problem in bioinformatics and has been extensively researched. Bidirectional indices have opened new possibilities in this regard allowing the search to start from anywhere within the pattern and extend in both directions. In particular, use of search schemes (partitioning the pattern and searching the pieces in certain orders with given bounds on errors) can yield significant speed-ups. However, finding optimal search schemes is a difficult combinatorial optimization problem. Here for the first time, we propose a mixed integer program (MIP) capable to solve this optimization problem for Hamming distance with given number of pieces. Our experiments show that the optimal search schemes found by our MIP significantly improve the performance of search in bidirectional FM-index upon previous ad-hoc solutions. For example, approximate matching of 101-bp Illumina reads (with two errors) becomes 35 times faster than standard backtracking. Moreover, despite being performed purely in the index, the running time of search using our optimal schemes (for up to two errors) is comparable to the best state-of-the-art aligners, which benefit from combining search in index with in-text verification using dynamic programming. As a result, we anticipate a full-fledged aligner that employs an intelligent combination of search in the bidirectional FM-index using our optimal search schemes and in-text verification using dynamic programming outperforms today's best aligners. The development of such an aligner, called FAMOUS (Fast Approximate string Matching using OptimUm search Schemes), is ongoing as our future work.
Sequential Multi-Class Labeling in Crowdsourcing
Venue: arXiv cs.HC 2018
Year: 2018

We consider a crowdsourcing platform where workers' responses to questions posed by a crowdsourcer are used to determine the hidden state of a multi-class labeling problem. As workers may be unreliable, we propose to perform sequential questioning in which the questions posed to the workers are designed based on previous questions and answers. We propose a Partially-Observable Markov Decision Process (POMDP) framework to determine the best questioning strategy, subject to the crowdsourcer's budget constraint. As this POMDP formulation is in general intractable, we develop a suboptimal approach based on a $q$-ary Ulam-Rényi game. We also propose a sampling heuristic, which can be used in tandem with standard POMDP solvers, using our Ulam-Rényi strategy. We demonstrate through simulations that our approaches outperform a non-sequential strategy based on error correction coding and which does not utilize workers' previous responses.
Reconstructing Gene Trees From Fitch's Xenology Relation
Venue: arXiv cs.DM 2018
Year: 2018

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: $y$ is xenologous to $x$ if $y$ has been horizontally transferred at least once since it diverged from the least common ancestor of $x$ and $y$. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations.