OpenRaiser/Intern-Atlas huggingface dataset:
The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study
Venue: arXiv cs.LG 2017
Year: 2017

Which topics of machine learning are most commonly addressed in research? This question was initially answered in 2007 by doing a qualitative survey among distinguished researchers. In our study, we revisit this question from a quantitative perspective. Concretely, we collect 54K abstracts of papers published between 2007 and 2016 in leading machine learning journals and conferences. We then use machine learning in order to determine the top 10 topics in machine learning. We not only include models, but provide a holistic view across optimization, data, features, etc. This quantitative approach allows reducing the bias of surveys. It reveals new and up-to-date insights into what the 10 most prolific topics in machine learning research are. This allows researchers to identify popular topics as well as new and rising topics for their research.
Google Map Aided Visual Navigation for UAVs in GPS-denied Environment
Venue: arXiv cs.CV 2017
Year: 2017

We propose a framework for Google Map aided UAV navigation in GPS-denied environment. Geo-referenced navigation provides drift-free localization and does not require loop closures. The UAV position is initialized via correlation, which is simple and efficient. We then use optical flow to predict its position in subsequent frames. During pose tracking, we obtain inter-frame translation either by motion field or homography decomposition, and we use HOG features for registration on Google Map. We employ particle filter to conduct a coarse to fine search to localize the UAV. Offline test using aerial images collected by our quadrotor platform shows promising results as our approach eliminates the drift in dead-reckoning, and the small localization error indicates the superiority of our approach as a supplement to GPS.
Hardware Impairments Aware Transceiver Design for Full-Duplex Amplify-and-Forward MIMO Relaying
Venue: arXiv cs.IT 2017
Year: 2017

In this work we study the behavior of a full-duplex (FD) and amplify-and-forward (AF) relay with multiple antennas, where hardware impairments of the FD relay transceiver is taken into account. Due to the inter-dependency of the transmit relay power on each antenna and the residual self-interference in an FD-AF relay, we observe a distortion loop that degrades the system performance when the relay dynamic range is not high. In this regard, we analyze the relay function in presence of the hardware inaccuracies and an optimization problem is formulated to maximize the signal to distortion-plus-noise ratio (SDNR), under relay and source transmit power constraints. Due to the problem complexity, we propose a gradient-projection-based (GP) algorithm to obtain an optimal solution. Moreover, a nonalternating sub-optimal solution is proposed by assuming a rank-1 relay amplification matrix, and separating the design of the relay process into multiple stages (MuStR1). The proposed MuStR1 method is then enhanced by introducing an alternating update over the optimization variables, denoted as AltMuStR1 algorithm. It is observed that compared to GP, (Alt)MuStR1 algorithms significantly reduce the required computational complexity at the expense of a slight performance degradation. Finally, the proposed methods are evaluated under various system conditions, and compared with the methods available in the current literature. In particular, it is observed that as the hardware impairments increase, or for a system with a high transmit power, the impact of applying a distortion-aware design is significant.
I CAN HAS SUPERCOMPUTER? A Novel Approach to Teaching Parallel and Distributed Computing Concepts Using a Meme-Based Programming Language
Venue: arXiv cs.DC 2017
Year: 2017

A novel approach is presented to teach the parallel and distributed computing concepts of synchronization and remote memory access. The single program multiple data (SPMD) partitioned global address space (PGAS) model presented in this paper uses a procedural programming language appealing to undergraduate students. We propose that the amusing nature of the approach may engender creativity and interest using these concepts later in more sober environments. Specifically, we implement parallel extensions to LOLCODE within a source-to-source compiler sufficient for the development of parallel and distributed algorithms normally implemented using conventional high-performance computing languages and APIs.
A Variation Evolving Method for Optimal Control
Venue: arXiv cs.SY 2017
Year: 2017

A new method for the optimal solutions is proposed. Originating from the continuous-time dynamics stability theory in the control field, the optimal solution is anticipated to be obtained in an asymptotically evolving way. By introducing a virtual dimension, the variation time, a dynamic system that describes the variation motion is deduced from the Optimal Control Problem (OCP), and the optimal solution is its equilibrium point. Through this method, the intractable OCP is transformed to the Initial-value Problem (IVP) and it may be solved with mature Ordinary Differential Equation (ODE) numerical integration methods. Especially, the deduced dynamic system is globally stable, so any initial value will evolve to the extremal solution ultimately.
Shared urbanism: Big data on accommodation sharing in urban Australia
Venue: arXiv cs.CY 2017
Year: 2017

As affordability pressures and tight rental markets in global cities mount, online shared accommodation sites proliferate. Home sharing arrangements present dilemmas for planning that aims to improve health and safety standards, while supporting positives such as the usage of dormant stock and the relieving of rental pressures on middle/lower income earners. Currently, no formal data exists on this internationally growing trend. Here, we present a first quantitative glance on shared accommodation practices across all major urban centers of Australia enabled via collection and analysis of thousands of online listings. We examine, countrywide, the spatial and short time scale temporal characteristics of this market, along with preliminary analysis on rents, dwelling types and other characteristics. Findings have implications for housing policy makers and planning practitioners seeking to monitor and respond to housing policy and affordability pressures in formal and informal housing markets.
Preserving Distances in Very Faulty Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain {\em replacement paths} around the faulted set. In this paper we make substantial progress on fault tolerant preservers and additive spanners: (1) We present the first truly sub-quadratic size single-pair preservers in unweighted (possibly directed) graphs for \emph{any} fixed number $f$ of faults. Our result indeed generalizes to the single-source case, and can be used to build new fault-tolerant additive spanners (for all pairs). (2) The size of the above single-pair preservers is $O(n^{2-g(f)})$ for some positive function $g$, and grows to $O(n^2)$ for increasing $f$. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size $O(n^{2-ε})$ for $ε>0$, then the additive error has to be $Ω(\eps f)$. This surprisingly matches known upper bounds in the literature. (3) For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is $Θ(n^2)$ for $f\geq 2$ in both directed and undirected graphs, while for $f=1$ the size is $Θ(n)$ in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.
Planecell: Representing the 3D Space with Planes
Venue: arXiv cs.CV 2017
Year: 2017

Reconstruction based on the stereo camera has received considerable attention recently, but two particular challenges still remain. The first concerns the need to aggregate similar pixels in an effective approach, and the second is to maintain as much of the available information as possible while ensuring sufficient accuracy. To overcome these issues, we propose a new 3D representation method, namely, planecell, that extracts planarity from the depth-assisted image segmentation and then projects these depth planes into the 3D world. An energy function formulated from Conditional Random Field that generalizes the planar relationships is maximized to merge coplanar segments. We evaluate our method with a variety of reconstruction baselines on both KITTI and Middlebury datasets, and the results indicate the superiorities compared to other 3D space representation methods in accuracy, memory requirements and further applications.
Energy Harvesting Enabled MIMO Relaying through PS
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers a multiple-input multiple-output (MIMO) relay system with an energy harvesting relay node. All nodes are equipped with multiple antennas, and the relay node depends on the harvested energy from the received signal to support information forwarding. In particular, the relay node deploys power splitting based energy harvesting scheme. The capacity maximization problem subject to power constraints at both the source and relay nodes is considered for both fixed source covariance matrix and optimal source covariance matrix cases. Instead of using existing software solvers, iterative approaches using dual decomposition technique are developed based on the structures of the optimal relay precoding and source covariance matrices. Simulation results demonstrate the performance gain of the joint optimization against the fixed source covariance matrix case.
Static Contract Simplification
Venue: arXiv cs.PL 2017
Year: 2017

Contracts and contract monitoring are a powerful mechanism for specifying properties and guaranteeing them at run time. However, run time monitoring of contracts imposes a significant overhead. The execution time is impacted by the insertion of contract checks as well as by the introduction of proxy objects that perform delayed contract checks on demand. Static contract simplification attacks this issue using program transformation. It applies compile-time transformations to programs with contracts to reduce the overall run time while preserving the original behavior. Our key technique is to statically propagate contracts through the program and to evaluate and merge contracts where possible. The goal is to obtain residual contracts that are collectively cheaper to check at run time. We distinguish different levels of preservation of behavior, which impose different limitations on the admissible transformations: Strong blame preservation, where the transformation is a behavioral equivalence, and weak blame preservation, where the transformed program is equivalent up to the particular violation reported. Our transformations never increase the overall number of contract checks.
Efficient Benchmarking of Algorithm Configuration Procedures via Model-Based Surrogates
Venue: arXiv cs.AI 2017
Year: 2017

The optimization of algorithm (hyper-)parameters is crucial for achieving peak performance across a wide range of domains, ranging from deep neural networks to solvers for hard combinatorial problems. The resulting algorithm configuration (AC) problem has attracted much attention from the machine learning community. However, the proper evaluation of new AC procedures is hindered by two key hurdles. First, AC benchmarks are hard to set up. Second and even more significantly, they are computationally expensive: a single run of an AC procedure involves many costly runs of the target algorithm whose performance is to be optimized in a given AC benchmark scenario. One common workaround is to optimize cheap-to-evaluate artificial benchmark functions (e.g., Branin) instead of actual algorithms; however, these have different properties than realistic AC problems. Here, we propose an alternative benchmarking approach that is similarly cheap to evaluate but much closer to the original AC problem: replacing expensive benchmarks by surrogate benchmarks constructed from AC benchmarks. These surrogate benchmarks approximate the response surface corresponding to true target algorithm performance using a regression model, and the original and surrogate benchmark share the same (hyper-)parameter space. In our experiments, we construct and evaluate surrogate benchmarks for hyperparameter optimization as well as for AC problems that involve performance optimization of solvers for hard combinatorial problems, drawing training data from the runs of existing AC procedures. We show that our surrogate benchmarks capture overall important characteristics of the AC scenarios, such as high- and low-performing regions, from which they were derived, while being much easier to use and orders of magnitude cheaper to evaluate.
Finding Even Cycles Faster via Capped k-Walks
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we consider the problem of finding a cycle of length $2k$ (a $C_{2k}$) in an undirected graph $G$ with $n$ nodes and $m$ edges for constant $k\ge2$. A classic result by Bondy and Simonovits [J.Comb.Th.'74] implies that if $m \ge100k n^{1+1/k}$, then $G$ contains a $C_{2k}$, further implying that one needs to consider only graphs with $m = O(n^{1+1/k})$. Previously the best known algorithms were an $O(n^2)$ algorithm due to Yuster and Zwick [J.Disc.Math'97] as well as a $O(m^{2-(1+\lceil k/2\rceil^{-1})/(k+1)})$ algorithm by Alon et al. [Algorithmica'97]. We present an algorithm that uses $O(m^{2k/(k+1)})$ time and finds a $C_{2k}$ if one exists. This bound is $O(n^2)$ exactly when $m=Θ(n^{1+1/k})$. For $4$-cycles our new bound coincides with Alon et al., while for every $k>2$ our bound yields a polynomial improvement in $m$. Yuster and Zwick noted that it is "plausible to conjecture that $O(n^2)$ is the best possible bound in terms of $n$". We show "conditional optimality": if this hypothesis holds then our $O(m^{2k/(k+1)})$ algorithm is tight as well. Furthermore, a folklore reduction implies that no combinatorial algorithm can determine if a graph contains a $6$-cycle in time $O(m^{3/2-ε})$ for any $ε>0$ under the widely believed combinatorial BMM conjecture. Coupled with our main result, this gives tight bounds for finding $6$-cycles combinatorially and also separates the complexity of finding $4$- and $6$-cycles giving evidence that the exponent of $m$ in the running time should indeed increase with $k$. The key ingredient in our algorithm is a new notion of capped $k$-walks, which are walks of length $k$ that visit only nodes according to a fixed ordering. Our main technical contribution is an involved analysis proving several properties of such walks which may be of independent interest.
Multimodal Network Alignment
Venue: arXiv cs.SI 2017
Year: 2017

A multimodal network encodes relationships between the same set of nodes in multiple settings, and network alignment is a powerful tool for transferring information and insight between a pair of networks. We propose a method for multimodal network alignment that computes a matrix which indicates the alignment, but produces the result as a low-rank factorization directly. We then propose new methods to compute approximate maximum weight matchings of low-rank matrices to produce an alignment. We evaluate our approach by applying it on synthetic networks and use it to de-anonymize a multimodal transportation network.
Real-Time Dispersion Code Multiple Access (DCMA) for High-Speed Wireless Communications
Venue: arXiv cs.IT 2017
Year: 2017

We model, demonstrate and characterize Dispersion Code Multiple Access (DCMA) and hence show the applicability of this purely analog and real-time multiple access scheme to high-speed wireless communications. We first mathematically describe DCMA and show the appropriateness of Chebyshev dispersion coding in this technology. We next provide an experimental proof-of-concept in a 2 X 2 DCMA system. Finally,we statistically characterize DCMA in terms of bandwidth, dispersive group delay swing, system dimension and signal-to-noise ratio.
Report on Two-Step Knowledge-Aided Iterative ESPRIT Algorithm
Venue: arXiv cs.NA 2017
Year: 2017

In this work, we propose a subspace-based algorithm for direction-of-arrival (DOA) estimation, referred to as two-step knowledge-aided iterative estimation of signal parameters via rotational invariance techniques (ESPRIT) method (Two-Step KAI-ESPRIT), which achieves more accurate estimates than those of prior art. The proposed Two-Step KAI-ESPRIT improves the estimation of the covariance matrix of the input data by incorporating prior knowledge of signals and by exploiting knowledge of the structure of the covariance matrix and its perturbation terms. Simulation results illustrate the improvement achieved by the proposed method.
Modeling, Analysis, and Optimization of Coded Caching in Small-Cell Networks
Venue: arXiv cs.IT 2017
Year: 2017

Coded caching is able to exploit accumulated cache size and hence superior to uncoded caching by distributing different fractions of a file in different nodes. This work investigates coded caching in a large-scale small-cell network (SCN) where the locations of small base stations (SBSs) are modeled by stochastic geometry. We first propose a content delivery framework, where multiple SBSs that cache different coded packets of a desired file transmit concurrently upon a user request and the user decodes the signals using successive interference cancellation (SIC). We characterize the performance of coded caching by two performance metrics, average fractional offloaded traffic (AFOT) and average ergodic rate (AER), for which a closed-form expression and a tractable expression are derived, respectively, in the high signal-to-noise ratio region. We then formulate the coded cache placement problem for AFOT maximization as a multiple-choice knapsack problem (MCKP). By utilizing the analytical properties of AFOT, a greedy but optimal algorithm is proposed. We also consider the coded cache placement problem for AER maximization. By converting this problem into a standard MCKP, a heuristic algorithm is proposed. Analytical and numerical results reveal several design and performance insights of coded caching in conjunction with SIC receiver in interference-limited SCNs.
Bootstrapping Labelled Dataset Construction for Cow Tracking and Behavior Analysis
Venue: arXiv cs.CV 2017
Year: 2017

This paper introduces a new approach to the long-term tracking of an object in a challenging environment. The object is a cow and the environment is an enclosure in a cowshed. Some of the key challenges in this domain are a cluttered background, low contrast and high similarity between moving objects which greatly reduces the efficiency of most existing approaches, including those based on background subtraction. Our approach is split into object localization, instance segmentation, learning and tracking stages. Our solution is compared to a range of semi-supervised object tracking algorithms and we show that the performance is strong and well suited to subsequent analysis. We present our solution as a first step towards broader tracking and behavior monitoring for cows in precision agriculture with the ultimate objective of early detection of lameness.
Strategyproof Pareto-Stable Mechanisms for Two-Sided Matching with Indifferences
Venue: arXiv cs.GT 2017
Year: 2017

We study variants of the stable marriage and college admissions models in which the agents are allowed to express weak preferences over the set of agents on the other side of the market and the option of remaining unmatched. For the problems that we address, previous authors have presented polynomial-time algorithms for computing a "Pareto-stable" matching. In the case of college admissions, these algorithms require the preferences of the colleges over groups of students to satisfy a technical condition related to responsiveness. We design new polynomial-time Pareto-stable algorithms for stable marriage and college admissions that correspond to strategyproof mechanisms. For stable marriage, it is known that no Pareto-stable mechanism is strategyproof for all of the agents; our algorithm provides a mechanism that is strategyproof for the agents on one side of the market. For college admissions, it is known that no Pareto-stable mechanism can be strategyproof for the colleges; our algorithm provides a mechanism that is strategyproof for the students.
QoS-Aware Multi-Armed Bandits
Venue: arXiv cs.LG 2017
Year: 2017

Motivated by runtime verification of QoS requirements in self-adaptive and self-organizing systems that are able to reconfigure their structure and behavior in response to runtime data, we propose a QoS-aware variant of Thompson sampling for multi-armed bandits. It is applicable in settings where QoS satisfaction of an arm has to be ensured with high confidence efficiently, rather than finding the optimal arm while minimizing regret. Preliminary experimental results encourage further research in the field of QoS-aware decision making.
Concurrent Segmentation and Localization for Tracking of Surgical Instruments
Venue: arXiv cs.CV 2017
Year: 2017

Real-time instrument tracking is a crucial requirement for various computer-assisted interventions. In order to overcome problems such as specular reflections and motion blur, we propose a novel method that takes advantage of the interdependency between localization and segmentation of the surgical tool. In particular, we reformulate the 2D instrument pose estimation as heatmap regression and thereby enable a concurrent, robust and near real-time regression of both tasks via deep learning. As demonstrated by our experimental results, this modeling leads to a significantly improved performance than directly regressing the tool position and allows our method to outperform the state of the art on a Retinal Microsurgery benchmark and the MICCAI EndoVis Challenge 2015.
BEGAN: Boundary Equilibrium Generative Adversarial Networks
Venue: arXiv cs.LG 2017
Year: 2017

We propose a new equilibrium enforcing method paired with a loss derived from the Wasserstein distance for training auto-encoder based Generative Adversarial Networks. This method balances the generator and discriminator during training. Additionally, it provides a new approximate convergence measure, fast and stable training and high visual quality. We also derive a way of controlling the trade-off between image diversity and visual quality. We focus on the image generation task, setting a new milestone in visual quality, even at higher resolutions. This is achieved while using a relatively simple model architecture and a standard training procedure.