OpenRaiser/Intern-Atlas huggingface dataset:
Improved Regularity Model-based EDA for Many-objective Optimization
Venue: arXiv cs.NE 2018
Year: 2018

The performance of multi-objective evolutionary algorithms deteriorates appreciably in solving many-objective optimization problems which encompass more than three objectives. One of the known rationales is the loss of selection pressure which leads to the selected parents not generating promising offspring towards Pareto-optimal front with diversity. Estimation of distribution algorithms sample new solutions with a probabilistic model built from the statistics extracting over the existing solutions so as to mitigate the adverse impact of genetic operators. In this paper, an improved regularity-based estimation of distribution algorithm is proposed to effectively tackle unconstrained many-objective optimization problems. In the proposed algorithm, \emph{diversity repairing mechanism} is utilized to mend the areas where need non-dominated solutions with a closer proximity to the Pareto-optimal front. Then \emph{favorable solutions} are generated by the model built from the regularity of the solutions surrounding a group of representatives. These two steps collectively enhance the selection pressure which gives rise to the superior convergence of the proposed algorithm. In addition, dimension reduction technique is employed in the decision space to speed up the estimation search of the proposed algorithm. Finally, by assigning the Pareto-optimal solutions to the uniformly distributed reference vectors, a set of solutions with excellent diversity and convergence is obtained. To measure the performance, NSGA-III, GrEA, MOEA/D, HypE, MBN-EDA, and RM-MEDA are selected to perform comparison experiments over DTLZ and DTLZ$^-$ test suites with $3$-, $5$-, $8$-, $10$-, and $15$-objective. Experimental results quantified by the selected performance metrics reveal that the proposed algorithm shows considerable competitiveness in addressing unconstrained many-objective optimization problems.
Stochastic Gradient Descent on Highly-Parallel Architectures
Venue: arXiv cs.DB 2018
Year: 2018

There is an increased interest in building data analytics frameworks with advanced algebraic capabilities both in industry and academia. Many of these frameworks, e.g., TensorFlow and BIDMach, implement their compute-intensive primitives in two flavors---as multi-thread routines for multi-core CPUs and as highly-parallel kernels executed on GPU. Stochastic gradient descent (SGD) is the most popular optimization method for model training implemented extensively on modern data analytics platforms. While the data-intensive properties of SGD are well-known, there is an intense debate on which of the many SGD variants is better in practice. In this paper, we perform a comprehensive study of parallel SGD for training generalized linear models. We consider the impact of three factors -- computing architecture (multi-core CPU or GPU), synchronous or asynchronous model updates, and data sparsity -- on three measures---hardware efficiency, statistical efficiency, and time to convergence. In the process, we design an optimized asynchronous SGD algorithm for GPU that leverages warp shuffling and cache coalescing for data and model access. We draw several interesting findings from our extensive experiments with logistic regression (LR) and support vector machines (SVM) on five real datasets. For synchronous SGD, GPU always outperforms parallel CPU---they both outperform a sequential CPU solution by more than 400X. For asynchronous SGD, parallel CPU is the safest choice while GPU with data replication is better in certain situations. The choice between synchronous GPU and asynchronous CPU depends on the task and the characteristics of the data. As a reference, our best implementation outperforms TensorFlow and BIDMach consistently. We hope that our insights provide a useful guide for applying parallel SGD to generalized linear models.
Kernel-smoothed proper orthogonal decomposition (KSPOD)-based emulation for prediction of spatiotemporally evolving flow dynamics
Venue: arXiv cs.CE 2018
Year: 2018

This interdisciplinary study, which combines machine learning, statistical methodologies, high-fidelity simulations, and flow physics, demonstrates a new process for building an efficient surrogate model for predicting spatiotemporally evolving flow dynamics. In our previous work, a common-grid proper-orthogonal-decomposition (CPOD) technique was developed to establish a physics-based surrogate (emulation) model for prediction of mean flowfields and design exploration over a wide parameter space. The CPOD technique is substantially improved upon here using a kernel-smoothed POD (KSPOD) technique, which leverages kriging-based weighted functions from the design matrix. The resultant emulation model is then trained using a dataset obtained through high-fidelity simulations. As an example, the flow evolution in a swirl injector is considered for a wide range of design parameters and operating conditions. The KSPOD-based emulation model performs well, and can faithfully capture the spatiotemporal flow dynamics. The model enables effective design surveys utilizing high-fidelity simulation data, achieving a turnaround time for evaluating new design points that is 42,000 times faster than the original simulation.
Effectiveness of Diffusing Information through a Social Network in Multiple Phases
Venue: arXiv cs.SI 2018
Year: 2018

We study the effectiveness of using multiple phases for maximizing the extent of information diffusion through a social network, and present insights while considering various aspects. In particular, we focus on the independent cascade model with the possibility of adaptively selecting seed nodes in multiple phases based on the observed diffusion in preceding phases, and conduct a detailed simulation study on real-world network datasets and various values of seeding budgets. We first present a negative result that more phases do not guarantee a better spread, however the adaptability advantage of more phases generally leads to a better spread in practice, as observed on real-world datasets. We study how diffusing in multiple phases affects the mean and standard deviation of the distribution representing the extent of diffusion. We then study how the number of phases impacts the effectiveness of multiphase diffusion, how the diffusion progresses phase-by-phase, and what is an optimal way to split the total seeding budget across phases. Our experiments suggest a significant gain when we move from single phase to two phases, and an appreciable gain when we further move to three phases, but the marginal gain thereafter is usually not very significant. Our main conclusion is that, given the number of phases, an optimal way to split the budget across phases is such that the number of nodes influenced in each phase is almost the same.
Asynchronous Stochastic Proximal Methods for Nonconvex Nonsmooth Optimization
Venue: arXiv cs.LG 2018
Year: 2018

We study stochastic algorithms for solving nonconvex optimization problems with a convex yet possibly nonsmooth regularizer, which find wide applications in many practical machine learning applications. However, compared to asynchronous parallel stochastic gradient descent (AsynSGD), an algorithm targeting smooth optimization, the understanding of the behavior of stochastic algorithms for nonsmooth regularized optimization problems is limited, especially when the objective function is nonconvex. To fill this theoretical gap, in this paper, we propose and analyze asynchronous parallel stochastic proximal gradient (Asyn-ProxSGD) methods for nonconvex problems. We establish an ergodic convergence rate of $O(1/\sqrt{K})$ for the proposed Asyn-ProxSGD, where $K$ is the number of updates made on the model, matching the convergence rate currently known for AsynSGD (for smooth problems). To our knowledge, this is the first work that provides convergence rates of asynchronous parallel ProxSGD algorithms for nonconvex problems. Furthermore, our results are also the first to show the convergence of any stochastic proximal methods without assuming an increasing batch size or the use of additional variance reduction techniques. We implement the proposed algorithms on Parameter Server and demonstrate its convergence behavior and near-linear speedup, as the number of workers increases, on two real-world datasets.
Time Series Learning using Monotonic Logical Properties
Venue: arXiv cs.LG 2018
Year: 2018

Cyber-physical systems of today are generating large volumes of time-series data. As manual inspection of such data is not tractable, the need for learning methods to help discover logical structure in the data has increased. We propose a logic-based framework that allows domain-specific knowledge to be embedded into formulas in a parametric logical specification over time-series data. The key idea is to then map a time series to a surface in the parameter space of the formula. Given this mapping, we identify the Hausdorff distance between boundaries as a natural distance metric between two time-series data under the lens of the parametric specification. This enables embedding non-trivial domain-specific knowledge into the distance metric and then using off-the-shelf machine learning tools to label the data. After labeling the data, we demonstrate how to extract a logical specification for each label. Finally, we showcase our technique on real world traffic data to learn classifiers/monitors for slow-downs and traffic jams.
Secure Serverless Computing Using Dynamic Information Flow Control
Venue: arXiv cs.PL 2018
Year: 2018

The rise of serverless computing provides an opportunity to rethink cloud security. We present an approach for securing serverless systems using a novel form of dynamic information flow control (IFC). We show that in serverless applications, the termination channel found in most existing IFC systems can be arbitrarily amplified via multiple concurrent requests, necessitating a stronger termination-sensitive non-interference guarantee, which we achieve using a combination of static labeling of serverless processes and dynamic faceted labeling of persistent data. We describe our implementation of this approach on top of JavaScript for AWS Lambda and OpenWhisk serverless platforms, and present three realistic case studies showing that it can enforce important IFC security properties with low overhead.
Deep Neural Network for Learning to Rank Query-Text Pairs
Venue: arXiv cs.IR 2018
Year: 2018

This paper considers the problem of document ranking in information retrieval systems by Learning to Rank. We propose ConvRankNet combining a Siamese Convolutional Neural Network encoder and the RankNet ranking model which could be trained in an end-to-end fashion. We prove a general result justifying the linear test-time complexity of pairwise Learning to Rank approach. Experiments on the OHSUMED dataset show that ConvRankNet outperforms systematically existing feature-based models.
Adaptive Streaming in Interactive Multiview Video Systems
Venue: arXiv cs.MM 2018
Year: 2018

Multiview applications endow final users with the possibility to freely navigate within 3D scenes with minimum-delay. A real feeling of scene navigation is enabled by transmitting multiple high-quality camera views, which can be used to synthesize additional virtual views to offer a smooth navigation. However, when network resources are limited, not all camera views can be sent at high quality. It is therefore important, yet challenging, to find the right tradeoff between coding artifacts (reducing the quality of camera views) and virtual synthesis artifacts (reducing the number of camera views sent to users). To this aim, we propose an optimal transmission strategy for interactive multiview HTTP adaptive streaming (HAS). We propose a problem formulation to select the optimal set of camera views that the client requests for downloading, such that the navigation quality experienced by the user is optimized while the bandwidth constraints are satisfied. We show that our optimization problem is NP-hard, and we therefore develop an optimal solution based on the dynamic programming algorithm with polynomial time complexity. To further simplify the deployment, we present a suboptimal greedy algorithm with effective performance and lower complexity. The proposed controller is evaluated in theoretical and realistic settings characterized by realistic network statistics estimation, buffer management and server-side representation optimization. Simulation results show significant improvement in terms of navigation quality compared with alternative baseline multiview adaptation logic solutions.
Building Instance Classification Using Street View Images
Venue: arXiv cs.CV 2018
Year: 2018

Land-use classification based on spaceborne or aerial remote sensing images has been extensively studied over the past decades. Such classification is usually a patch-wise or pixel-wise labeling over the whole image. But for many applications, such as urban population density mapping or urban utility planning, a classification map based on individual buildings is much more informative. However, such semantic classification still poses some fundamental challenges, for example, how to retrieve fine boundaries of individual buildings. In this paper, we proposed a general framework for classifying the functionality of individual buildings. The proposed method is based on Convolutional Neural Networks (CNNs) which classify facade structures from street view images, such as Google StreetView, in addition to remote sensing images which usually only show roof structures. Geographic information was utilized to mask out individual buildings, and to associate the corresponding street view images. We created a benchmark dataset which was used for training and evaluating CNNs. In addition, the method was applied to generate building classification maps on both region and city scales of several cities in Canada and the US. Keywords: CNN, Building instance classification, Street view images, OpenStreetMap
Retrodirective Large Antenna Energy Beamforming in Backscatter Multi-User Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this letter, we study a new technique for energy beamforming (EB) in multi-user networks, which combines large antenna retrodirectivity at the transmitter side with signal backscattering at the energy receivers. The proposed technique has low complexity and achieves EB without any active operation at the receivers or complicated signal processing techniques at the transmitter. Since the average harvested energy depends on the backscattering coefficients, we investigate different reflection policies for various design objectives. The proposed policies are analyzed from a system level standpoint by taking into account spatial randomness.
Free LSD: Prior-Free Visual Landing Site Detection for Autonomous Planes
Venue: arXiv cs.RO 2018
Year: 2018

Full autonomy for fixed-wing unmanned aerial vehicles (UAVs) requires the capability to autonomously detect potential landing sites in unknown and unstructured terrain, allowing for self-governed mission completion or handling of emergency situations. In this work, we propose a perception system addressing this challenge by detecting landing sites based on their texture and geometric shape without using any prior knowledge about the environment. The proposed method considers hazards within the landing region such as terrain roughness and slope, surrounding obstacles that obscure the landing approach path, and the local wind field that is estimated by the on-board EKF. The latter enables applicability of the proposed method on small-scale autonomous planes without landing gear. A safe approach path is computed based on the UAV dynamics, expected state estimation and actuator uncertainty, and the on-board computed elevation map. The proposed framework has been successfully tested on photo-realistic synthetic datasets and in challenging real-world environments.
Perceptual Quality Assessment of Immersive Images Considering Peripheral Vision Impact
Venue: arXiv cs.MM 2018
Year: 2018

Conventional images/videos are often rendered within the central vision area of the human visual system (HVS) with uniform quality. Recent virtual reality (VR) device with head mounted display (HMD) extends the field of view (FoV) significantly to include both central and peripheral vision areas. It exhibits the unequal image quality sensation among these areas because of the non-uniform distribution of photoreceptors on our retina. We propose to study the sensation impact on the image subjective quality with respect to the eccentric angle $θ$ across different vision areas. Often times, image quality is controlled by the quantization stepsize $q$ and spatial resolution $s$, separately and jointly. Therefore, the sensation impact can be understood by exploring the $q$ and/or $s$ in terms of the $θ$, resulting in self-adaptive analytical models that have shown quite impressive accuracy through independent cross validations. These models can further be applied to give different quality weights at different regions, so as to significantly reduce the transmission data size but without subjective quality loss. As demonstrated in a gigapixel imaging system, we have shown that the image rendering can be speed up about 10$\times$ with the model guided unequal quality scales, in comparison to the the legacy scheme with uniform quality scales everywhere.
User Satisfaction-Driven Bandwidth Allocation for Image Transmission in a Crowded Environment
Venue: arXiv cs.MM 2018
Year: 2018

A major portion of postings on social networking sites constitute high quality digital images and videos. These images and videos require a fairly large amount of bandwidth during transmission. Accordingly, high quality image and video postings become a challenge for the network service provider, especially in a crowded environment where bandwidth is in high demand. In this paper we present a user satisfaction driven bandwidth allocation scheme for image transmission in such environments. In an image, there are always objects that stand out more than others. The reason behind some set of objects being more important in a scene is based on a number of visual, as well as, cognitive factors. Being motivated by the fact that user satisfaction is more dependent on the quality of these salient objects in an image than non-salient ones, we propose a quantifiable metric for measuring user-satisfiability (based on image quality and delay of transmission). The bandwidth allocation technique proposed thereafter, ensures that this user-satisfiability is maximized. Unlike the existing approaches that utilize some fixed set of non-linear functions for framing the user-satisfiability index, our metric is modelled over customer survey data, where the unknown parameters are trained with machine learning methods.
Trace semantics via determinization for probabilistic transition systems
Venue: arXiv cs.LO 2018
Year: 2018

A coalgebraic definition of finite and infinite trace semantics for probabilistic transition systems has recently been given using a certain Kleisli category. In this paper this semantics is developed using a coalgebraic method which is an instance of general determinization. Once applied to discrete systems, this point of view allows the exploitation of the determinized structure by up-to techniques. Thereby it becomes possible to algorithmically check the equivalence of two finite probabilistic transition systems.
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an $n^{c}$-separator theorem for some $c<1$. We give a fully dynamic algorithm that maintains $(1+\varepsilon)$-approximations of the all-pairs effective resistances of an $n$-vertex graph $G$ undergoing edge insertions and deletions with $\tilde{O}(\sqrt{n}/\varepsilon^2)$ worst-case update time and $\tilde{O}(\sqrt{n}/\varepsilon^2)$ worst-case query time, if $G$ is guaranteed to be $\sqrt{n}$-separable (i.e., it is taken from a class satisfying a $\sqrt{n}$-separator theorem) and its separator can be computed in $\tilde{O}(n)$ time. Our algorithm is built upon a dynamic algorithm for maintaining \emph{approximate Schur complement} that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest. We complement our result by proving that for any two fixed vertices $s$ and $t$, no incremental or decremental algorithm can maintain the $s-t$ effective resistance for $\sqrt{n}$-separable graphs with worst-case update time $O(n^{1/2-δ})$ and query time $O(n^{1-δ})$ for any $δ>0$, unless the Online Matrix Vector Multiplication (OMv) conjecture is false. We further show that for \emph{general} graphs, no incremental or decremental algorithm can maintain the $s-t$ effective resistance problem with worst-case update time $O(n^{1-δ})$ and query-time $O(n^{2-δ})$ for any $δ>0$, unless the OMv conjecture is false.
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
Venue: arXiv cs.CC 2018
Year: 2018

We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over $\mathbb{R}$) of functions from some "simple" class ${\cal C}$. In particular, given ${\cal C}$ we are interested in finding low-complexity functions lacking sparse representations. When ${\cal C}$ is the set of PARITY functions or the set of conjunctions, this sort of problem has a well-understood answer, the problem becomes interesting when ${\cal C}$ is "overcomplete" and the set of functions is not linearly independent. We focus on the cases where ${\cal C}$ is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of low-degree polynomials over a finite field, all of which are well-studied in different contexts. We provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for "semi-explicit" Boolean functions. For example, we show there are functions in nondeterministic quasi-polynomial time that require super-polynomial size: $\bullet$ Depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds. $\bullet$ Depth-two neural networks with ReLU activation function. $\bullet$ $\mathbb{R}$-linear combinations of $O(1)$-degree $\mathbb{F}_p$-polynomials, for every prime $p$ (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in $E^{NP}$ requiring $2^{Ω(n)}$ linear combinations. $\bullet$ $\mathbb{R}$-linear combinations of $ACC \circ THR$ circuits of polynomial size (further generalizing the recent lower bounds of Murray and the author). (The above is a shortened abstract. For the full abstract, see the paper.)