OpenRaiser/Intern-Atlas huggingface dataset:
Tracing Equilibrium in Dynamic Markets via Distributed Adaptation
Venue: arXiv cs.GT 2018
Year: 2018

Competitive equilibrium is a central concept in economics with numerous applications beyond markets, such as scheduling, fair allocation of goods, or bandwidth distribution in networks. Computation of competitive equilibria has received a significant amount of interest in algorithmic game theory, mainly for the prominent case of Fisher markets. Natural and decentralized processes like tatonnement and proportional response dynamics (PRD) converge quickly towards equilibrium in large classes of Fisher markets. Almost all of the literature assumes that the market is a static environment and that the parameters of agents and goods do not change over time. In contrast, many large real-world markets are subject to frequent and dynamic changes. In this paper, we provide the first provable performance guarantees of discrete-time tatonnement and PRD in markets that are subject to perturbation over time. We analyze the prominent class of Fisher markets with CES utilities and quantify the impact of changes in supplies of goods, budgets of agents, and utility functions of agents on the convergence of tatonnement to market equilibrium. Since the equilibrium becomes a dynamic object and will rarely be reached, our analysis provides bounds expressing the distance to equilibrium that will be maintained via tatonnement and PRD updates. Our results indicate that in many cases, tatonnement and PRD follow the equilibrium rather closely and quickly recover conditions of approximate market clearing. Our approach can be generalized to analyzing a general class of Lyapunov dynamical systems with changing system parameters, which might be of independent interest.
Angiodysplasia Detection and Localization Using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Accurate detection and localization for angiodysplasia lesions is an important problem in early stage diagnostics of gastrointestinal bleeding and anemia. Gold-standard for angiodysplasia detection and localization is performed using wireless capsule endoscopy. This pill-like device is able to produce thousand of high enough resolution images during one passage through gastrointestinal tract. In this paper we present our winning solution for MICCAI 2017 Endoscopic Vision SubChallenge: Angiodysplasia Detection and Localization its further improvements over the state-of-the-art results using several novel deep neural network architectures. It address the binary segmentation problem, where every pixel in an image is labeled as an angiodysplasia lesions or background. Then, we analyze connected component of each predicted mask. Based on the analysis we developed a classifier that predict angiodysplasia lesions (binary variable) and a detector for their localization (center of a component). In this setting, our approach outperforms other methods in every task subcategory for angiodysplasia detection and localization thereby providing state-of-the-art results for these problems. The source code for our solution is made publicly available at https://github.com/ternaus/angiodysplasia-segmentatio
A General Per-Flow Service Curve for GPS
Venue: arXiv cs.NI 2018
Year: 2018

Generalized Processor Sharing (GPS), which provides the theoretical underpinnings for fair packet scheduling algorithms, has been studied extensively. However, a tight formulation of the available service of a flow only exists for traffic that is regulated by affine arrival envelopes and constant-rate links. In this paper, we show that the universal service curve by Parekh and Gallager can be extended to concave arrival envelopes and links with time-variable capacity. We also dispense with the previously existing assumption of a stable system.
Efficient Large-Scale Domain Classification with Personalized Attention
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we explore the task of mapping spoken language utterances to one of thousands of natural language understanding domains in intelligent personal digital assistants (IPDAs). This scenario is observed for many mainstream IPDAs in industry that allow third parties to develop thousands of new domains to augment built-in ones to rapidly increase domain coverage and overall IPDA capabilities. We propose a scalable neural model architecture with a shared encoder, a novel attention mechanism that incorporates personalization information and domain-specific classifiers that solves the problem efficiently. Our architecture is designed to efficiently accommodate new domains that appear in-between full model retraining cycles with a rapid bootstrapping mechanism two orders of magnitude faster than retraining. We account for practical constraints in real-time production systems, and design to minimize memory footprint and runtime latency. We demonstrate that incorporating personalization results in significantly more accurate domain classification in the setting with thousands of overlapping domains.
Cellular Connectivity for UAVs: Network Modeling, Performance Analysis and Design Guidelines
Venue: arXiv cs.NI 2018
Year: 2018

The growing use of aerial user equipments (UEs) in various applications requires ubiquitous and reliable connectivity for safe control and data exchange between these devices and ground stations. Key questions that need to be addressed when planning the deployment of aerial UEs are whether the cellular network is a suitable candidate for enabling such connectivity, and how the inclusion of aerial UEs might impact the overall network efficiency. This paper provides an in-depth analysis of user and network level performance of a cellular network that serves both unmanned aerial vehicles (UAVs) and ground users in the downlink. Our results show that the favorable propagation conditions that UAVs enjoy due to their height often backfire on them, as the increased co-channel interference received from neighboring ground BSs is not compensated by the improved signal strength. When compared with a ground user in an urban area, our analysis shows that a UAV flying at 100 meters can experience a throughput decrease of a factor 10 and a coverage drop from 76% to 30%. Motivated by these findings, we develop UAV and network based solutions to enable an adequate integration of UAVs into cellular networks. In particular, we show that an optimal tilting of the UAV antenna can increase their coverage and throughput from 23% to 89% and from 3.5 b/s/Hz to 5.8 b/s/Hz, respectively, outperforming ground UEs. Furthermore, our findings reveal that depending on UAV altitude, the aerial user performance can scale with respect to the network density better than that of a ground user. Finally, our results show that network densification and the use of micro cells limit UAV performance. While UAV usage has the potential to increase area spectral efficiency (ASE) of cellular networks with moderate number of cells, they might hamper the development of future ultra dense networks.
Characterizing the Impact of SNR Heterogeneity on Time-of-Arrival based Localization Outage Probability
Venue: arXiv cs.NI 2018
Year: 2018

In localization, an outage occurs if the positioning error exceeds a pre-defined threshold, $ε_{\rm th}$. For time-of-arrival based localization, a key factor affecting the positioning error is the relative positions of the anchors, with respect to the target location. Specifically, the positioning error is a function of (a) the distance-dependent signal-to-noise ratios (SNRs) of the anchor-target links, and (b) the pairwise angles subtended by the anchors at the target location. From a design perspective, characterizing the distribution of the positioning error over an ensemble of target and anchor locations is essential for providing probabilistic performance guarantees against outage. To solve this difficult problem, previous works have assumed all links to have the same SNR (i.e., SNR homogeneity), which neglects the impact of distance variation among the anchors on the positioning error. In this paper, we model SNR heterogeneity among anchors using a distance-dependent pathloss model and derive an accurate approximation for the error complementary cumulative distribution function (ccdf). By highlighting the accuracy of our results, relative to previous ones that ignore SNR heterogeneity, we concretely demonstrate that SNR heterogeneity has a considerable impact on the error distribution.
Maximizing Profit with Convex Costs in the Random-order Model
Venue: arXiv cs.DS 2018
Year: 2018

Suppose a set of requests arrives online: each request gives some value $v_i$ if accepted, but requires using some amount of each of $d$ resources. Our cost is a convex function of the vector of total utilization of these $d$ resources. Which requests should be accept to maximize our profit, i.e., the sum of values of the accepted demands, minus the convex cost? We consider this problem in the random-order a.k.a. secretary model, and show an $O(d)$-competitive algorithm for the case where the convex cost function is also supermodular. If the set of accepted demands must also be independent in a given matroid, we give an $O(d^3 α)$-competitive algorithm for the supermodular case, and an improved $O(d^2α)$ if the convex cost function is also separable. Here $α$ is the competitive ratio of the best algorithm for the submodular secretary problem. These extend and improve previous results known for this problem. Our techniques are simple but use powerful ideas from convex duality, which give clean interpretations of existing work, and allow us to give the extensions and improvements.
Advancing Tabu and Restart in Local Search for Maximum Weight Cliques
Venue: arXiv cs.AI 2018
Year: 2018

The tabu and restart are two fundamental strategies for local search. In this paper, we improve the local search algorithms for solving the Maximum Weight Clique (MWC) problem by introducing new tabu and restart strategies. Both the tabu and restart strategies proposed are based on the notion of a local search scenario, which involves not only a candidate solution but also the tabu status and unlocking relationship. Compared to the strategy of configuration checking, our tabu mechanism discourages forming a cycle of unlocking operations. Our new restart strategy is based on the re-occurrence of a local search scenario instead of that of a candidate solution. Experimental results show that the resulting MWC solver outperforms several state-of-the-art solvers on the DIMACS, BHOSLIB, and two benchmarks from practical applications.
High Performance Visual Tracking with Circular and Structural Operators
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, a novel circular and structural operator tracker (CSOT) is proposed for high performance visual tracking, it not only possesses the powerful discriminative capability of SOSVM but also efficiently inherits the superior computational efficiency of DCF. Based on the proposed circular and structural operators, a set of primal confidence score maps can be obtained by circular correlating feature maps with their corresponding structural correlation filters. Furthermore, an implicit interpolation is applied to convert the multi-resolution feature maps to the continuous domain and make all primal confidence score maps have the same spatial resolution. Then, we exploit an efficient ensemble post-processor based on relative entropy, which can coalesce primal confidence score maps and create an optimal confidence score map for more accurate localization. The target is localized on the peak of the optimal confidence score map. Besides, we introduce a collaborative optimization strategy to update circular and structural operators by iteratively training structural correlation filters, which significantly reduces computational complexity and improves robustness. Experimental results demonstrate that our approach achieves state-of-the-art performance in mean AUC scores of 71.5% and 69.4% on the OTB-2013 and OTB-2015 benchmarks respectively, and obtains a third-best expected average overlap (EAO) score of 29.8% on the VOT-2017 benchmark.
Multi-scale prediction for robust hand detection and classification
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we present a multi-scale Fully Convolutional Networks (MSP-RFCN) to robustly detect and classify human hands under various challenging conditions. In our approach, the input image is passed through the proposed network to generate score maps, based on multi-scale predictions. The network has been specifically designed to deal with small objects. It uses an architecture based on region proposals generated at multiple scales. Our method is evaluated on challenging hand datasets, namely the Vision for Intelligent Vehicles and Applications (VIVA) Challenge and the Oxford hand dataset. It is compared against recent hand detection algorithms. The experimental results demonstrate that our proposed method achieves state-of-the-art detection for hands of various sizes.
How Bad is the Freedom to Flood-It?
Venue: arXiv cs.DS 2018
Year: 2018

Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in Free-Flood-It the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for Fixed-Flood-It become intractable for Free-Flood-It. We also show that some tractable cases for Fixed-Flood-It are still tractable for Free-Flood-It but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for Fixed-Flood-It is always at most twice that of Free-Flood-It, and this is tight.
Generalized comparison trees for point-location problems
Venue: arXiv cs.CG 2018
Year: 2018

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$ can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from $H$; in particular, if all hyperplanes in $H$ are $k$-sparse then generalized comparisons are $2k$-sparse. The depth of the obtained linear decision tree is polynomial in $d$ and logarithmic in $|H|$, which is comparable to previous results in the literature that use general linear queries. This extends the study of comparison trees from a previous work by the authors [Kane {et al.}, FOCS 2017]. The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries. Our analysis combines a seminal result of Forster regarding sets in isotropic position [Forster, JCSS 2002], the margin-based inference dimension analysis for comparison queries from [Kane {et al.}, FOCS 2017], and compactness arguments.
Learn and Pick Right Nodes to Offload
Venue: arXiv cs.NI 2018
Year: 2018

Task offloading is a promising technology to exploit the benefits of fog computing. An effective task offloading strategy is needed to utilize the computational resources efficiently. In this paper, we endeavor to seek an online task offloading strategy to minimize the long-term latency. In particular, we formulate a stochastic programming problem, where the expectations of the system parameters change abruptly at unknown time instants. Meanwhile, we consider the fact that the queried nodes can only feed back the processing results after finishing the tasks. We then put forward an effective algorithm to solve this challenging stochastic programming under the non-stationary bandit model. We further prove that our proposed algorithm is asymptotically optimal in a non-stationary fog-enabled network. Numerical simulations are carried out to corroborate our designs.
Efficient Pose Tracking from Natural Features in Standard Web Browsers
Venue: arXiv cs.CV 2018
Year: 2018

Computer Vision-based natural feature tracking is at the core of modern Augmented Reality applications. Still, Web-based Augmented Reality typically relies on location-based sensing (using GPS and orientation sensors) or marker-based approaches to solve the pose estimation problem. We present an implementation and evaluation of an efficient natural feature tracking pipeline for standard Web browsers using HTML5 and WebAssembly. Our system can track image targets at real-time frame rates tablet PCs (up to 60 Hz) and smartphones (up to 25 Hz).
Decorrelated Batch Normalization
Venue: arXiv cs.CV 2018
Year: 2018

Batch Normalization (BN) is capable of accelerating the training of deep models by centering and scaling activations within mini-batches. In this work, we propose Decorrelated Batch Normalization (DBN), which not just centers and scales activations but whitens them. We explore multiple whitening techniques, and find that PCA whitening causes a problem we call stochastic axis swapping, which is detrimental to learning. We show that ZCA whitening does not suffer from this problem, permitting successful learning. DBN retains the desirable qualities of BN and further improves BN's optimization efficiency and generalization ability. We design comprehensive experiments to show that DBN can improve the performance of BN on multilayer perceptrons and convolutional neural networks. Furthermore, we consistently improve the accuracy of residual networks on CIFAR-10, CIFAR-100, and ImageNet.
Attention Based Natural Language Grounding by Navigating Virtual Environment
Venue: arXiv cs.CL 2018
Year: 2018

In this work, we focus on the problem of grounding language by training an agent to follow a set of natural language instructions and navigate to a target object in an environment. The agent receives visual information through raw pixels and a natural language instruction telling what task needs to be achieved and is trained in an end-to-end way. We develop an attention mechanism for multi-modal fusion of visual and textual modalities that allows the agent to learn to complete the task and achieve language grounding. Our experimental results show that our attention mechanism outperforms the existing multi-modal fusion mechanisms proposed for both 2D and 3D environments in order to solve the above-mentioned task in terms of both speed and success rate. We show that the learnt textual representations are semantically meaningful as they follow vector arithmetic in the embedding space. The effectiveness of our attention approach over the contemporary fusion mechanisms is also highlighted from the textual embeddings learnt by the different approaches. We also show that our model generalizes effectively to unseen scenarios and exhibit zero-shot generalization capabilities both in 2D and 3D environments. The code for our 2D environment as well as the models that we developed for both 2D and 3D are available at https://github.com/rl-lang-grounding/rl-lang-ground.
Black Open Access in Ukraine: Analysis of Downloading Sci-Hub Publications by Ukrainian Internet Users
Venue: arXiv cs.DL 2018
Year: 2018

Introduction. High subscription fees to scholarly research journals provoke researchers to use illegal channels of access to scientific information. Analysis of statistical data on downloads of scholarly research papers by Ukrainian Internet users from illegal web resource can help to define gaps in information provision at the institutional or the state level for each scientific field. Problem Statement. To conduct an analysis of behavior and geography of downloads of scholarly research publications from illegal web resource Sci-Hub by Ukrainian Internet users within the period from September 1, 2015 to February 29, 2016. Purpose. To assess the information needs of Ukrainian researchers who download scientific papers from Sci-Hub. Materials and Methods. The used file is available at public domain and contains complete data of downloads of scholarly research articles from Sci-Hub for the period from September 1, 2015 to February 29, 2016. Inquiries of users with Ukrainian IP-addresses have been selected. Using DOI of downloaded articles enables finding the publishers and journal brands with the help of CrossRef API, whereas using the All Science Journal Classification (ASJC) codes makes it possible to identify the subject. Results. The study has shown that the most documents downloaded related to natural sciences (primarily, chemistry, physics, and astronomy), with Elsevier publications being the most frequently inquired by Ukrainian users of Sci-Hub and Internet users from Kyiv downloading the papers most actively. Conclusion. The obtained data are important for understanding the information needs of Ukrainian researchers and can be used to formulate an optimal subscription policy for providing access to information resources at Ukrainian R&D institutions.
Person Identification from Partial Gait Cycle Using Fully Convolutional Neural Network
Venue: arXiv cs.CV 2018
Year: 2018

Gait as a biometric property for person identification plays a key role in video surveillance and security applications. In gait recognition, normally, gait feature such as Gait Energy Image (GEI) is extracted from one full gait cycle. However in many circumstances, such a full gait cycle might not be available due to occlusion. Thus, the GEI is not complete giving rise to a degrading in gait-based person identification rate. In this paper, we address this issue by proposing a novel method to identify individuals from gait feature when a few (or even single) frame(s) is available. To do so, we propose a deep learning-based approach to transform incomplete GEI to the corresponding complete GEI obtained from a full gait cycle. More precisely, this transformation is done gradually by training several auto encoders independently and then combining these as a uniform model. Experimental results on two public gait datasets, namely OULP and Casia-B demonstrate the validity of the proposed method in dealing with very incomplete gait cycles.
VectorDefense: Vectorization as a Defense to Adversarial Examples
Venue: arXiv cs.CV 2018
Year: 2018

Training deep neural networks on images represented as grids of pixels has brought to light an interesting phenomenon known as adversarial examples. Inspired by how humans reconstruct abstract concepts, we attempt to codify the input bitmap image into a set of compact, interpretable elements to avoid being fooled by the adversarial structures. We take the first step in this direction by experimenting with image vectorization as an input transformation step to map the adversarial examples back into the natural manifold of MNIST handwritten digits. We compare our method vs. state-of-the-art input transformations and further discuss the trade-offs between a hand-designed and a learned transformation defense.