OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions
Venue: arXiv cs.LG 2017
Year: 2017

A function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is a Sparse Additive Model (SPAM), if it is of the form $f(\mathbf{x}) = \sum_{l \in \mathcal{S}}ϕ_{l}(x_l)$ where $\mathcal{S} \subset [d]$, $|\mathcal{S}| \ll d$. Assuming $ϕ$'s, $\mathcal{S}$ to be unknown, there exists extensive work for estimating $f$ from its samples. In this work, we consider a generalized version of SPAMs, that also allows for the presence of a sparse number of second order interaction terms. For some $\mathcal{S}_1 \subset [d], \mathcal{S}_2 \subset {[d] \choose 2}$, with $|\mathcal{S}_1| \ll d, |\mathcal{S}_2| \ll d^2$, the function $f$ is now assumed to be of the form: $\sum_{p \in \mathcal{S}_1}ϕ_{p} (x_p) + \sum_{(l,l^{\prime}) \in \mathcal{S}_2}ϕ_{(l,l^{\prime})} (x_l,x_{l^{\prime}})$. Assuming we have the freedom to query $f$ anywhere in its domain, we derive efficient algorithms that provably recover $\mathcal{S}_1,\mathcal{S}_2$ with finite sample bounds. Our analysis covers the noiseless setting where exact samples of $f$ are obtained, and also extends to the noisy setting where the queries are corrupted with noise. For the noisy setting in particular, we consider two noise models namely: i.i.d Gaussian noise and arbitrary but bounded noise. Our main methods for identification of $\mathcal{S}_2$ essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing based schemes. Once $\mathcal{S}_1, \mathcal{S}_2$ are known, we show how the individual components $ϕ_p$, $ϕ_{(l,l^{\prime})}$ can be estimated via additional queries of $f$, with uniform error bounds. Lastly, we provide simulation results on synthetic data that validate our theoretical findings.
Near-Optimal Finite-Length Scaling for Polar Codes over Large Alphabets
Venue: arXiv cs.IT 2017
Year: 2017

For any prime power $q$, Mori and Tanaka introduced a family of $q$-ary polar codes based on $q$~by~$q$ Reed-Solomon polarization kernels. For transmission over a $q$-ary erasure channel, they also derived a closed-form recursion for the erasure probability of each effective channel. In this paper, we use that expression to analyze the finite-length scaling of these codes on the $q$-ary erasure channel with erasure probability $ε\in(0,1)$. Our primary result is that, for any $γ>0$ and $δ>0$, there is a $q_{0}$ such that, for all $q\geq q_{0}$, the fraction of effective channels with erasure rate at most $N^{-γ}$ is at least $1-ε-O(N^{-1/2+δ})$, where $N=q^{n}$ is the blocklength. Since this fraction cannot be larger than $1-ε-O(N^{-1/2})$, this establishes near-optimal finite-length scaling for this family of codes. Our approach can be seen as an extension of a similar analysis for binary polar codes by Hassani, Alishahi, and Urbanke. A similar analysis is also considered for $q$-ary polar codes with $m$ by $m$ polarizing matrices. This separates the effect of the alphabet size from the effect of the matrix size. If the polarizing matrix at each stage is drawn independently and uniformly from the set of invertible $m$ by $m$ matrices, then the linear operator associated with the Lyapunov function analysis can be written in closed form. To prove near-optimal scaling for polar codes with fixed $q$ as $m$ increases, however, two technical obstacles remain. Thus, we conclude by stating two concrete mathematical conjectures that, if proven, would imply near-optimal scaling for fixed~$q$.
Estimating Depth from Monocular Images as Classification Using Deep Fully Convolutional Residual Networks
Venue: arXiv cs.CV 2017
Year: 2017

Depth estimation from single monocular images is a key component of scene understanding and has benefited largely from deep convolutional neural networks (CNN) recently. In this article, we take advantage of the recent deep residual networks and propose a simple yet effective approach to this problem. We formulate depth estimation as a pixel-wise classification task. Specifically, we first discretize the continuous depth values into multiple bins and label the bins according to their depth range. Then we train fully convolutional deep residual networks to predict the depth label of each pixel. Performing discrete depth label classification instead of continuous depth value regression allows us to predict a confidence in the form of probability distribution. We further apply fully-connected conditional random fields (CRF) as a post processing step to enforce local smoothness interactions, which improves the results. We evaluate our approach on both indoor and outdoor datasets and achieve state-of-the-art performance.
Verification of interlocking systems using statistical model checking
Venue: arXiv cs.SE 2017
Year: 2017

In the railway domain, an interlocking is the system ensuring safe train traffic inside a station by controlling its active elements such as the signals or points. Modern interlockings are configured using particular data, called application data, reflecting the track layout and defining the actions that the interlocking can take. The safety of the train traffic relies thereby on application data correctness, errors inside them can cause safety issues such as derailments or collisions. Given the high level of safety required by such a system, its verification is a critical concern. In addition to the safety, an interlocking must also ensure that availability properties, stating that no train would be stopped forever in a station, are satisfied. Most of the research dealing with this verification relies on model checking. However, due to the state space explosion problem, this approach does not scale for large stations. More recently, a discrete event simulation approach limiting the verification to a set of likely scenarios, was proposed. The simulation enables the verification of larger stations, but with no proof that all the interesting scenarios are covered by the simulation. In this paper, we apply an intermediate statistical model checking approach, offering both the advantages of model checking and simulation. Even if exhaustiveness is not obtained, statistical model checking evaluates with a parametrizable confidence the reliability and the availability of the entire system.
The GPU-based Parallel Ant Colony System
Venue: arXiv cs.DC 2017
Year: 2017

The Ant Colony System (ACS) is, next to Ant Colony Optimization (ACO) and the MAX-MIN Ant System (MMAS), one of the most efficient metaheuristic algorithms inspired by the behavior of ants. In this article we present three novel parallel versions of the ACS for the graphics processing units (GPUs). To the best of our knowledge, this is the first such work on the ACS which shares many key elements of the ACO and the MMAS, but differences in the process of building solutions and updating the pheromone trails make obtaining an efficient parallel version for the GPUs a difficult task. The proposed parallel versions of the ACS differ mainly in their implementations of the pheromone memory. The first two use the standard pheromone matrix, and the third uses a novel selective pheromone memory. Computational experiments conducted on several Travelling Salesman Problem (TSP) instances of sizes ranging from 198 to 2392 cities showed that the parallel ACS on Nvidia Kepler GK104 GPU (1536 CUDA cores) is able to obtain a speedup up to 24.29x vs the sequential ACS running on a single core of Intel Xeon E5-2670 CPU. The parallel ACS with the selective pheromone memory achieved speedups up to 16.85x, but in most cases the obtained solutions were of significantly better quality than for the sequential ACS.
Measurement Bounds for Sparse Signal Reconstruction with Multiple Side Information
Venue: arXiv cs.IT 2017
Year: 2017

In the context of compressed sensing (CS), this paper considers the problem of reconstructing sparse signals with the aid of other given correlated sources as multiple side information. To address this problem, we theoretically study a generic \textcolor{black}{weighted $n$-$\ell_{1}$ minimization} framework and propose a reconstruction algorithm that leverages multiple side information signals (RAMSI). The proposed RAMSI algorithm computes adaptively optimal weights among the side information signals at every reconstruction iteration. In addition, we establish theoretical bounds on the number of measurements that are required to successfully reconstruct the sparse source by using \textcolor{black}{weighted $n$-$\ell_{1}$ minimization}. The analysis of the established bounds reveal that \textcolor{black}{weighted $n$-$\ell_{1}$ minimization} can achieve sharper bounds and significant performance improvements compared to classical CS. We evaluate experimentally the proposed RAMSI algorithm and the established bounds using synthetic sparse signals as well as correlated feature histograms, extracted from a multiview image database for object recognition. The obtained results show clearly that the proposed algorithm outperforms state-of-the-art algorithms---\textcolor{black}{including classical CS, $\ell_1\text{-}\ell_1$ minimization, Modified-CS, regularized Modified-CS, and weighted $\ell_1$ minimization}---in terms of both the theoretical bounds and the practical performance.
Sending a Message with Unknown Noise
Venue: arXiv cs.CR 2017
Year: 2017

Alice and Bob are connected via a two-way channel, and Alice wants to send a message of $L$ bits to Bob. An adversary flips an arbitrary but finite number of bits, $T$, on the channel. This adversary knows our algorithm and Alice's message, but does not know any private random bits generated by Alice or Bob, nor the bits sent over the channel, except when these bits can be predicted by knowledge of Alice's message or our algorithm. We want Bob to receive Alice's message and for both players to terminate, with error probability at most $δ> 0$, where $δ$ is a parameter known to both Alice and Bob. Unfortunately, the value $T$ is unknown in advance to either Alice or Bob, and the value $L$ is unknown in advance to Bob. We describe an algorithm to solve the above problem while sending an expected $L + O \left( T + \min \left(T+1,\frac{L}{\log L} \right) \log \left( \frac{L}δ \right) \right)$ bits. A special case is when $δ= O(1/L^c)$, for some constant $c$. Then when $T = o(L/\log L)$, the expected number of bits sent is $L + o(L)$, and when $T = Ω(L)$, the expected number of bits sent is $L + O\left( T \right)$, which is asymptotically optimal.
Regression with n$\to$1 by Expert Knowledge Elicitation
Venue: arXiv cs.LG 2017
Year: 2017

We consider regression under the "extremely small $n$ large $p$" condition, where the number of samples $n$ is so small compared to the dimensionality $p$ that predictors cannot be estimated without prior knowledge. This setup occurs in personalized medicine, for instance, when predicting treatment outcomes for an individual patient based on noisy high-dimensional genomics data. A remaining source of information is expert knowledge, which has received relatively little attention in recent years. We formulate the inference problem of asking expert feedback on features on a budget, propose an elicitation strategy for a simple "small $n$" setting, and derive conditions under which the elicitation strategy is optimal. Experiments on simulated experts, both on synthetic and genomics data, demonstrate that the proposed strategy can drastically improve prediction accuracy.
Deep convolutional networks on the pitch spiral for musical instrument recognition
Venue: arXiv cs.SD 2017
Year: 2017

Musical performance combines a wide range of pitches, nuances, and expressive techniques. Audio-based classification of musical instruments thus requires to build signal representations that are invariant to such transformations. This article investigates the construction of learned convolutional architectures for instrument recognition, given a limited amount of annotated training data. In this context, we benchmark three different weight sharing strategies for deep convolutional networks in the time-frequency domain: temporal kernels; time-frequency kernels; and a linear combination of time-frequency kernels which are one octave apart, akin to a Shepard pitch spiral. We provide an acoustical interpretation of these strategies within the source-filter framework of quasi-harmonic sounds with a fixed spectral envelope, which are archetypal of musical notes. The best classification accuracy is obtained by hybridizing all three convolutional layers into a single deep learning architecture.
Mobile Cloud Computing with a UAV-Mounted Cloudlet: Optimal Bit Allocation for Communication and Computation
Venue: arXiv cs.NI 2017
Year: 2017

Mobile cloud computing relieves the tension between compute-intensive mobile applications and battery-constrained mobile devices by enabling the offloading of computing tasks from mobiles to a remote processors. This paper considers a mobile cloud computing scenario in which the "cloudlet" processor that provides offloading opportunities to mobile devices is mounted on unmanned aerial vehicles (UAVs) to enhance coverage. Focusing on a slotted communication system with frequency division multiplexing between mobile and UAV, the joint optimization of the number of input bits transmitted in the uplink by the mobile to the UAV, the number of input bits processed by the cloudlet at the UAV, and the number of output bits returned by the cloudlet to the mobile in the downlink in each slot is carried out by means of dual decomposition under maximum latency constraints with the aim of minimizing the mobile energy consumption. Numerical results reveal the critical importance of an optimized bit allocation in order to enable significant energy savings as compared to local mobile execution for stringent latency constraints.
Stochastic Patching Process
Venue: arXiv cs.AI 2017
Year: 2017

Stochastic partition models tailor a product space into a number of rectangular regions such that the data within each region exhibit certain types of homogeneity. Due to constraints of partition strategy, existing models may cause unnecessary dissections in sparse regions when fitting data in dense regions. To alleviate this limitation, we propose a parsimonious partition model, named Stochastic Patching Process (SPP), to deal with multi-dimensional arrays. SPP adopts an "enclosing" strategy to attach rectangular patches to dense regions. SPP is self-consistent such that it can be extended to infinite arrays. We apply SPP to relational modeling and the experimental results validate its merit compared to the state-of-the-arts.
Bit complexity for multi-homogeneous polynomial system solving Application to polynomial minimization
Venue: arXiv cs.SC 2017
Year: 2017

Multi-homogeneous polynomial systems arise in many applications. We provide bit complexity estimates for solving them which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system under some genericity assumptions. The assumptions essentially imply that the Jacobian matrix of the system under study has maximal rank at the solution set and that this solution set if finite. The algorithm is probabilistic and a probability analysis is provided. Next, we apply these results to the problem of optimizing a linear map on the real trace of an algebraic set. Under some genericity assumptions, we provide bit complexity estimates for solving this polynomial minimization problem.
A Consistent Regularization Approach for Structured Prediction
Venue: arXiv cs.LG 2017
Year: 2017

We propose and analyze a regularization approach for structured prediction problems. We characterize a large class of loss functions that allows to naturally embed structured outputs in a linear space. We exploit this fact to design learning algorithms using a surrogate loss approach and regularization techniques. We prove universal consistency and finite sample bounds characterizing the generalization properties of the proposed methods. Experimental results are provided to demonstrate the practical usefulness of the proposed approach.
GROUPS-NET: Group Meetings Aware Routing in Multi-Hop D2D Networks
Venue: arXiv cs.NI 2017
Year: 2017

In the next generation cellular networks, device-to-device (D2D) communication is already considered a fundamental feature. A problem of multi-hop D2D networks is on how to define forwarding algorithms that achieve, at the same time, high delivery ratio and low network overhead. In this paper we aim to understand group meetings' properties by looking at their structure and regularity with the final goal of applying such knowledge in the design of a forwarding algorithm for D2D multi-hop networks. We introduce a forwarding protocol, namely GROUPS-NET, which is aware of social group meetings and their evolution over time. Our algorithm is parameter-calibration free and does not require any knowledge about the social network structure of the system. In particular, different from the state of the art algorithms, GROUPS-NET does not need communities detection, which is a complex and expensive task. We validate our algorithm using different publicly available data-sources. In real large scale scenarios, our algorithm achieves approximately the same delivery ratio of the state-of-art solution with up to 40% less network overhead.
Cross-validation estimate of the number of clusters in a network
Venue: arXiv cs.SI 2017
Year: 2017

Network science investigates methodologies that summarise relational data to obtain better interpretability. Identifying modular structures is a fundamental task, and assessment of the coarse-grain level is its crucial step. Here, we propose principled, scalable, and widely applicable assessment criteria to determine the number of clusters in modular networks based on the leave-one-out cross-validation estimate of the edge prediction error.
Temporal Clustering in Dynamic Networks with Tensor Decomposition
Venue: arXiv cs.SI 2017
Year: 2017

Dynamic networks are increasingly being usedd to model real world datasets. A challenging task in their analysis is to detect and characterize clusters. It is useful for analyzing real-world data such as detecting evolving communities in networks. We propose a temporal clustering framework based on a set of network generative models to address this problem. We use PARAFAC decomposition to learn network models from datasets.We then use $K$-means for clustering, the Silhouette criterion to determine the number of clusters, and a similarity score to order the clusters and retain the significant ones. In order to address the time-dependent aspect of these clusters, we propose a segmentation algorithm to detect their formations, dissolutions and lifetimes. Synthetic networks with ground truth and real-world datasets are used to test our method against state-of-the-art, and the results show that our method has better performance in clustering and lifetime detection than previous methods.
Adiabatic Persistent Contrastive Divergence Learning
Venue: arXiv cs.LG 2017
Year: 2017

This paper studies the problem of parameter learning in probabilistic graphical models having latent variables, where the standard approach is the expectation maximization algorithm alternating expectation (E) and maximization (M) steps. However, both E and M steps are computationally intractable for high dimensional data, while the substitution of one step to a faster surrogate for combating against intractability can often cause failure in convergence. We propose a new learning algorithm which is computationally efficient and provably ensures convergence to a correct optimum. Its key idea is to run only a few cycles of Markov Chains (MC) in both E and M steps. Such an idea of running incomplete MC has been well studied only for M step in the literature, called Contrastive Divergence (CD) learning. While such known CD-based schemes find approximated gradients of the log-likelihood via the mean-field approach in E step, our proposed algorithm does exact ones via MC algorithms in both steps due to the multi-time-scale stochastic approximation theory. Despite its theoretical guarantee in convergence, the proposed scheme might suffer from the slow mixing of MC in E step. To tackle it, we also propose a hybrid approach applying both mean-field and MC approximation in E step, where the hybrid approach outperforms the bare mean-field CD scheme in our experiments on real-world datasets.
Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
Venue: arXiv cs.LG 2017
Year: 2017

The primal-dual distributed optimization methods have broad large-scale machine learning applications. Previous primal-dual distributed methods are not applicable when the dual formulation is not available, e.g. the sum-of-non-convex objectives. Moreover, these algorithms and theoretical analysis are based on the fundamental assumption that the computing speeds of multiple machines in a cluster are similar. However, the straggler problem is an unavoidable practical issue in the distributed system because of the existence of slow machines. Therefore, the total computational time of the distributed optimization methods is highly dependent on the slowest machine. In this paper, we address these two issues by proposing distributed asynchronous dual free stochastic dual coordinate ascent algorithm for distributed optimization. Our method does not need the dual formulation of the target problem in the optimization. We tackle the straggler problem through asynchronous communication and the negative effect of slow machines is significantly alleviated. We also analyze the convergence rate of our method and prove the linear convergence rate even if the individual functions in objective are non-convex. Experiments on both convex and non-convex loss functions are used to validate our statements.
VIME: Variational Information Maximizing Exploration
Venue: arXiv cs.LG 2017
Year: 2017

Scalable and effective exploration remains a key challenge in reinforcement learning (RL). While there are methods with optimality guarantees in the setting of discrete state and action spaces, these methods cannot be applied in high-dimensional deep RL scenarios. As such, most contemporary RL relies on simple heuristics such as epsilon-greedy exploration or adding Gaussian noise to the controls. This paper introduces Variational Information Maximizing Exploration (VIME), an exploration strategy based on maximization of information gain about the agent's belief of environment dynamics. We propose a practical implementation, using variational inference in Bayesian neural networks which efficiently handles continuous state and action spaces. VIME modifies the MDP reward function, and can be applied with several different underlying RL algorithms. We demonstrate that VIME achieves significantly better performance compared to heuristic exploration methods across a variety of continuous control tasks and algorithms, including tasks with very sparse rewards.
Generalized Multi-view Embedding for Visual Recognition and Cross-modal Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, the problem of multi-view embedding from different visual cues and modalities is considered. We propose a unified solution for subspace learning methods using the Rayleigh quotient, which is extensible for multiple views, supervised learning, and non-linear embeddings. Numerous methods including Canonical Correlation Analysis, Partial Least Sqaure regression and Linear Discriminant Analysis are studied using specific intrinsic and penalty graphs within the same framework. Non-linear extensions based on kernels and (deep) neural networks are derived, achieving better performance than the linear ones. Moreover, a novel Multi-view Modular Discriminant Analysis (MvMDA) is proposed by taking the view difference into consideration. We demonstrate the effectiveness of the proposed multi-view embedding methods on visual object recognition and cross-modal image retrieval, and obtain superior results in both applications compared to related methods.