OpenRaiser/Intern-Atlas huggingface dataset:
Bootstrapped Coordinate Search for Multidimensional Scaling
Venue: arXiv cs.LG 2019
Year: 2019

In this work, a unified framework for gradient-free Multidimensional Scaling (MDS) based on Coordinate Search (CS) is proposed. This family of algorithms is an instance of General Pattern Search (GPS) methods which avoid the explicit computation of derivatives but instead evaluate the objective function while searching on coordinate steps of the embedding space. The backbone element of CSMDS framework is the corresponding probability matrix that correspond to how likely is each corresponding coordinate to be evaluated. We propose a Bootstrapped instance of CSMDS (BS CSMDS) which enhances the probability of the direction that decreases the most the objective function while also reducing the corresponding probability of all the other coordinates. BS CSMDS manages to avoid unnecessary function evaluations and result to significant speedup over other CSMDS alternatives while also obtaining the same error rate. Experiments on both synthetic and real data reveal that BS CSMDS performs consistently better than other CSMDS alternatives under various experimental setups.
Discovering Nested Communities
Venue: arXiv cs.DS 2019
Year: 2019

Finding communities in graphs is one of the most well-studied problems in data mining and social-network analysis. In many real applications, the underlying graph does not have a clear community structure. In those cases, selecting a single community turns out to be a fairly ill-posed problem, as the optimization criterion has to make a difficult choice between selecting a tight but small community or a more inclusive but sparser community. In order to avoid the problem of selecting only a single community we propose discovering a sequence of nested communities. More formally, given a graph and a starting set, our goal is to discover a sequence of communities all containing the starting set, and each community forming a denser subgraph than the next. Discovering an optimal sequence of communities is a complex optimization problem, and hence we divide it into two subproblems: 1) discover the optimal sequence for a fixed order of graph vertices, a subproblem that we can solve efficiently, and 2) find a good order. We employ a simple heuristic for discovering an order and we provide empirical and theoretical evidence that our order is good.
SASSE: Scalable and Adaptable 6-DOF Pose Estimation
Venue: arXiv cs.CV 2019
Year: 2019

Visual localization has become a key enabling component of many place recognition and SLAM systems. Contemporary research has primarily focused on improving accuracy and precision-recall type metrics, with relatively little attention paid to a system's absolute storage scaling characteristics, its flexibility to adapt to available computational resources, and its longevity with respect to easily incorporating newly learned or hand-crafted image descriptors. Most significantly, improvement in one of these aspects typically comes at the cost of others: for example, a snapshot-based system that achieves sub-linear storage cost typically provides no metric pose estimation, or, a highly accurate pose estimation technique is often ossified in adapting to recent advances in appearance-invariant features. In this paper, we present a novel 6-DOF localization system that for the first time simultaneously achieves all the three characteristics: significantly sub-linear storage growth, agnosticism to image descriptors, and customizability to available storage and computational resources. The key features of our method are developed based on a novel adaptation of multiple-label learning, together with effective dimensional reduction and learning techniques that enable simple and efficient optimization. We evaluate our system on several large benchmarking datasets and provide detailed comparisons to state-of-the-art systems. The proposed method demonstrates competitive accuracy with existing pose estimation methods while achieving better sub-linear storage scaling, significantly reduced absolute storage requirements, and faster training and deployment speeds.
Joint Millimeter Wave and Microwave Wave Resource Allocation Design for Dual-Mode Base Stations
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider the design of joint resource blocks (RBs) and power allocation for dual-mode base stations operating over millimeter wave (mmW) band and microwave ($μ$W) band. The resource allocation design aims to minimize the system energy consumption while taking into account the channel state information, maximum delay, load, and different types of user applications (UAs). To facilitate the design, we first propose a group-based algorithm to assign UAs to multiple groups. Within each group, low-power UAs, which often appear in short distance and experience less obstacles, are inclined to be served over mmW band. The allocation problem over mmW band can be solved by a greedy algorithm. Over $μ$W band, we propose an estimation-optimal-descent algorithm. The rate of each UA at all RBs is estimated to initialize the allocation. Then, we keep altering RB's ownership until any altering makes power increases. Simulation results show that our proposed algorithm offers an excellent tradeoff between low energy consumption and fair transmission.
Minimum description length as an objective function for non-negative matrix factorization
Venue: arXiv cs.LG 2019
Year: 2019

Non-negative matrix factorization (NMF) is a dimensionality reduction technique which tends to produce a sparse representation of data. Commonly, the error between the actual and recreated matrices is used as an objective function, but this method may not produce the type of representation we desire as it allows for the complexity of the model to grow, constrained only by the size of the subspace and the non-negativity requirement. If additional constraints, such as sparsity, are imposed the question of parameter selection becomes critical. Instead of adding sparsity constraints in an ad-hoc manner we propose a novel objective function created by using the principle of minimum description length (MDL). Our formulation, MDL-NMF, automatically trades off between the complexity and accuracy of the model using a principled approach with little parameter selection or the need for domain expertise. We demonstrate our model works effectively on three heterogeneous data-sets and on a range of semi-synthetic data showing the broad applicability of our method.
A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
Venue: arXiv cs.LG 2019
Year: 2019

We consider variational inequalities coming from monotone operators, a setting that includes convex minimization and convex-concave saddle-point problems. We assume an access to potentially noisy unbiased values of the monotone operators and assess convergence through a compatible gap function which corresponds to the standard optimality criteria in the aforementioned subcases. We present a universal algorithm for these inequalities based on the Mirror-Prox algorithm. Concretely, our algorithm simultaneously achieves the optimal rates for the smooth/non-smooth, and noisy/noiseless settings. This is done without any prior knowledge of these properties, and in the general set-up of arbitrary norms and compatible Bregman divergences. For convex minimization and convex-concave saddle-point problems, this leads to new adaptive algorithms. Our method relies on a novel yet simple adaptive choice of the step-size, which can be seen as the appropriate extension of AdaGrad to handle constrained problems.
eMBB-URLLC Resource Slicing: A Risk-Sensitive Approach
Venue: arXiv cs.NI 2019
Year: 2019

Ultra Reliable Low Latency Communication (URLLC) is a 5G New Radio (NR) application that requires strict reliability and latency. URLLC traffic is usually scheduled on top of the ongoing enhanced Mobile Broadband (eMBB) transmissions (i.e., puncturing the current eMBB transmission) and cannot be queued due to its hard latency requirements. In this letter, we propose a risk-sensitive based formulation to allocate resources to the incoming URLLC traffic while minimizing the risk of the eMBB transmission (i.e., protecting the eMBB users with low data rate) and ensuring URLLC reliability. Specifically, the Conditional Value at Risk (CVaR) is introduced as a risk measure for eMBB transmission. Moreover, the reliability constraint of URLLC is formulated as a chance constraint and relaxed based on Markov's inequality. We decompose the formulated problem into two subproblems in order to transform it into a convex form and then alternatively solve them until convergence. Simulation results show that the proposed approach allocates resources to the incoming URLLC traffic efficiently while satisfying the reliability of both eMBB and URLLC.
Stochastic Enumeration with Importance Sampling
Venue: arXiv cs.DS 2019
Year: 2019

Many hard problems in the computational sciences are equivalent to counting the leaves of a decision tree, or, more generally, summing a cost function over the nodes. These problems include calculating the permanent of a matrix, finding the volume of a convex polyhedron, and counting the number of linear extensions of a partially ordered set. Many approximation algorithms exist to estimate such sums. One of the most recent is Stochastic Enumeration (SE), introduced in 2013 by Rubinstein. In 2015, Vaisman and Kroese provided a rigorous analysis of the variance of SE, and showed that SE can be extended to a fully polynomial randomized approximation scheme for certain cost functions on random trees. We present an algorithm that incorporates an importance function into SE, and provide theoretical analysis of its efficacy. We also present the results of numerical experiments to measure the variance of an application of the algorithm to the problem of counting linear extensions of a poset, and show that introducing importance sampling results in a significant reduction of variance as compared to the original version of SE.
An Exploratory Study on Visual Exploration of Model Simulations by Multiple Types of Experts
Venue: arXiv cs.HC 2019
Year: 2019

Experts in different domains rely increasingly on simulation models of complex processes to reach insights, make decisions, and plan future projects. These models are often used to study possible trade-offs, as experts try to optimise multiple conflicting objectives in a single investigation. Understanding all the model intricacies, however, is challenging for a single domain expert. We propose a simple approach to support multiple experts when exploring complex model results. First, we reduce the model exploration space, then present the results on a shared interactive surface, in the form of a scatterplot matrix and linked views. To explore how multiple experts analyse trade-offs using this setup, we carried out an observational study focusing on the link between expertise and insight generation during the analysis process. Our results reveal the different exploration strategies and multi-storyline approaches that domain experts adopt during trade-off analysis, and inform our recommendations for collaborative model exploration systems.
AlphaStar: An Evolutionary Computation Perspective
Venue: arXiv cs.NE 2019
Year: 2019

In January 2019, DeepMind revealed AlphaStar to the world-the first artificial intelligence (AI) system to beat a professional player at the game of StarCraft II-representing a milestone in the progress of AI. AlphaStar draws on many areas of AI research, including deep learning, reinforcement learning, game theory, and evolutionary computation (EC). In this paper we analyze AlphaStar primarily through the lens of EC, presenting a new look at the system and relating it to many concepts in the field. We highlight some of its most interesting aspects-the use of Lamarckian evolution, competitive co-evolution, and quality diversity. In doing so, we hope to provide a bridge between the wider EC community and one of the most significant AI systems developed in recent times.
GNU Radio Implementation of MALIN: "Multi-Armed bandits Learning for Internet-of-things Networks"
Venue: arXiv cs.NI 2019
Year: 2019

We implement an IoT network the following way: one gateway, one or several intelligent (i.e., learning) objects, embedding the proposed solution, and a traffic generator that emulates radio interferences from many other objects. Intelligent objects communicate with the gateway with a wireless ALOHA-based protocol, which does not require any specific overhead for the learning. We model the network access as a discrete sequential decision making problem, and using the framework and algorithms from Multi-Armed Bandit (MAB) learning, we show that intelligent objects can improve their access to the network by using low complexity and decentralized algorithms, such as UCB1 and Thompson Sampling. This solution could be added in a straightforward and costless manner in LoRaWAN networks, just by adding this feature in some or all the devices, without any modification on the network side.
An RNN-based IMM Filter Surrogate
Venue: arXiv cs.CV 2019
Year: 2019

The problem of varying dynamics of tracked objects, such as pedestrians, is traditionally tackled with approaches like the Interacting Multiple Model (IMM) filter using a Bayesian formulation. By following the current trend towards using deep neural networks, in this paper an RNN-based IMM filter surrogate is presented. Similar to an IMM filter solution, the presented RNN-based model assigns a probability value to a performed dynamic and, based on them, puts out a multi-modal distribution over future pedestrian trajectories. The evaluation is done on synthetic data, reflecting prototypical pedestrian maneuvers.
How to "DODGE" Complex Software Analytics?
Venue: arXiv cs.SE 2019
Year: 2019

Machine learning techniques applied to software engineering tasks can be improved by hyperparameter optimization, i.e., automatic tools that find good settings for a learner's control parameters. We show that such hyperparameter optimization can be unnecessarily slow, particularly when the optimizers waste time exploring "redundant tunings"', i.e., pairs of tunings which lead to indistinguishable results. By ignoring redundant tunings, DODGE, a tuning tool, runs orders of magnitude faster, while also generating learners with more accurate predictions than seen in prior state-of-the-art approaches.
Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI
Venue: arXiv cs.AI 2019
Year: 2019

This is an integrative review that address the question, "What makes for a good explanation?" with reference to AI systems. Pertinent literatures are vast. Thus, this review is necessarily selective. That said, most of the key concepts and issues are expressed in this Report. The Report encapsulates the history of computer science efforts to create systems that explain and instruct (intelligent tutoring systems and expert systems). The Report expresses the explainability issues and challenges in modern AI, and presents capsule views of the leading psychological theories of explanation. Certain articles stand out by virtue of their particular relevance to XAI, and their methods, results, and key points are highlighted. It is recommended that AI/XAI researchers be encouraged to include in their research reports fuller details on their empirical or experimental methods, in the fashion of experimental psychology research reports: details on Participants, Instructions, Procedures, Tasks, Dependent Variables (operational definitions of the measures and metrics), Independent Variables (conditions), and Control Conditions.
A Composable Coreset for k-Center in Doubling Metrics
Venue: arXiv cs.DS 2019
Year: 2019

A set of points $P$ in a metric space and a constant integer $k$ are given. The $k$-center problem finds $k$ points as centers among $P$, such that the maximum distance of any point of $P$ to their closest centers $(r)$ is minimized. Doubling metrics are metric spaces in which for any $r$, a ball of radius $r$ can be covered using a constant number of balls of radius $r/2$. Fixed dimensional Euclidean spaces are doubling metrics. The lower bound on the approximation factor of $k$-center is $1.822$ in Euclidean spaces, however, $(1+ε)$-approximation algorithms with exponential dependency on $\frac{1}ε$ and $k$ exist. For a given set of sets $P_1,\ldots,P_L$, a composable coreset independently computes subsets $C_1\subset P_1, \ldots, C_L\subset P_L$, such that $\cup_{i=1}^L C_i$ contains an approximation of a measure of the set $\cup_{i=1}^L P_i$. We introduce a $(1+ε)$-approximation composable coreset for $k$-center, which in doubling metrics has size sublinear in $|P|$. This results in a $(2+ε)$-approximation algorithm for $k$-center in MapReduce with a constant number of rounds in doubling metrics for any $ε>0$ and sublinear communications, which is based on parametric pruning. We prove the exponential nature of the trade-off between the number of centers $(k)$ and the radius $(r)$, and give a composable coreset for a related problem called dual clustering. Also, we give a new version of the parametric pruning algorithm with $O(\frac{nk}ε)$ running time, $O(n)$ space and $2+ε$ approximation factor for metric $k$-center.
Optimal Divisible Load Scheduling for Resource-Sharing Network
Venue: arXiv cs.DC 2019
Year: 2019

Scheduling is an important task allowing parallel systems to perform efficiently and reliably. For modern computation systems, divisible load is a special type of data which can be divided into arbitrary sizes and independently processed in parallel. Such loads are commonly encountered in applications which are processing a great amount of similar data units. For a multi-task processor, the processor's speed may be time-varying due to the arrival and departure of other background jobs. This paper studies an optimal divisible loads scheduling problem on a single level tree network, whose processing speeds and channel speeds are time-varying. Two recursive algorithms are provided to solve this problem when the arrival and departure times of the background jobs are known a priori and an iterative algorithm is provided to solve the case where such times are not known. Numerical tests and evaluations are performed for these three algorithms under different numbers of background jobs and processors.
Parallel Contextual Bandits in Wireless Handover Optimization
Venue: arXiv cs.NI 2019
Year: 2019

As cellular networks become denser, a scalable and dynamic tuning of wireless base station parameters can only be achieved through automated optimization. Although the contextual bandit framework arises as a natural candidate for such a task, its extension to a parallel setting is not straightforward: one needs to carefully adapt existing methods to fully leverage the multi-agent structure of this problem. We propose two approaches: one derived from a deterministic UCB-like method and the other relying on Thompson sampling. Thanks to its bayesian nature, the latter is intuited to better preserve the exploration-exploitation balance in the bandit batch. This is verified on toy experiments, where Thompson sampling shows robustness to the variability of the contexts. Finally, we apply both methods on a real base station network dataset and evidence that Thompson sampling outperforms both manual tuning and contextual UCB.
Particle Swarm Optimization Approaches for Primary User Emulation Attack Detection and Localization in Cognitive Radio Networks
Venue: arXiv cs.NI 2019
Year: 2019

The primary user emulation attack (PUEA) is one of the common threats in cognitive radio networks (CRNs), in this problem, an attacker mimics the Primary User (PU) signal to deceive other secondary users (SUs) to make them leave the white spaces (free spaces) in the spectrum assigned by the PU. In this paper, the PUEA is detected and localized using the Time-Difference-Of-Arrival (TDOA) localization technique. Particle Swarm Optimization (PSO) algorithms are proposed to solve the cost function of TDOA measurements. The PSO variants are developed by changing the parameters of the standard PSO such as inertia weight and acceleration constants. These approaches are presented and compared with the standard PSO in terms of convergence speed and processing time. This paper presents the first study of designing a PSO algorithm suitable for the localization problem and will be considered as a good guidance for applying the optimization algorithms in wireless positioning techniques. Mean square error (MSE) and cumulative distribution function (CDF) are used as the evaluation metrics to measure the accuracy of the proposed algorithms. Simulation results show that the proposed PSO approaches provide higher accuracy and faster convergence than the standard PSO and the Taylor series estimation (TSE).
Path Loss Characterization for Intra-Vehicle Wearable Deployments at 60 GHz
Venue: arXiv cs.NI 2019
Year: 2019

In this work, we present the results of a wideband measurement campaign at 60 GHz conducted inside a Linkker electric city bus. Targeting prospective millimeter-wave (mmWave) public transportation wearable scenarios, we mimic a typical deployment of mobile high-end consumer devices in a dense environment. Specifically, our intra-vehicle deployment includes one receiver and multiple transmitters corresponding to a mmWave access point and passengers' wearable and hand-held devices. While the receiver is located in the front part of the bus, the transmitters repeat realistic locations of personal devices (i) at the seat level (e.g., a hand-held device) and (ii) at a height 70 cm above the seat (e.g., a wearable device: augmented reality glasses or a head-mounted display). Based on the measured received power, we construct a logarithmic model for the distance-dependent path loss. The parametrized models developed in the course of this study have the potential to become an attractive ground for the link budget estimation and interference footprint studies in crowded public transportation scenarios.
Modeling Terms by Graphs with Structure Constraints (Two Illustrations)
Venue: arXiv cs.LO 2019
Year: 2019

In the talk at the workshop my aim was to demonstrate the usefulness of graph techniques for tackling problems that have been studied predominantly as problems on the term level: increasing sharing in functional programs, and addressing questions about Milner's process semantics for regular expressions. For both situations an approach that is based on modeling terms by graphs with structure constraints has turned out to be fruitful. In this extended abstract I describe the underlying problems, give references, provide examples, indicate the chosen approaches, and compare the initial situations as well as the results that have been obtained, and some results that are being developed at present.
Semantics-Preserving DPO-Based Term Graph Rewriting
Venue: arXiv cs.LO 2019
Year: 2019

Term graph rewriting is important as "conceptual implementation" of the execution of functional programs, and of data-flow optimisations in compilers. One way to define term graph transformation rule application is via the well-established and intuitively accessible double-pushout (DPO) approach; we present a new result proving semantics preservation for such DPO-based term graph rewriting.