OpenRaiser/Intern-Atlas huggingface dataset:
Query-free Clothing Retrieval via Implicit Relevance Feedback
Venue: arXiv cs.CV 2017
Year: 2017

Image-based clothing retrieval is receiving increasing interest with the growth of online shopping. In practice, users may often have a desired piece of clothing in mind (e.g., either having seen it before on the street or requiring certain specific clothing attributes) but may be unable to supply an image as a query. We model this problem as a new type of image retrieval task in which the target image resides only in the user's mind (called "mental image retrieval" hereafter). Because of the absence of an explicit query image, we propose to solve this problem through relevance feedback. Specifically, a new Bayesian formulation is proposed that simultaneously models the retrieval target and its high-level representation in the mind of the user (called the "user metric" hereafter) as posterior distributions of pre-fetched shop images and heterogeneous features extracted from multiple clothing attributes, respectively. Requiring only clicks as user feedback, the proposed algorithm is able to account for the variability in human decision-making. Experiments with real users demonstrate the effectiveness of the proposed algorithm.
The Price of Information in Combinatorial Optimization
Venue: arXiv cs.DS 2017
Year: 2017

Consider a network design application where we wish to lay down a minimum-cost spanning tree in a given graph; however, we only have stochastic information about the edge costs. To learn the precise cost of any edge, we have to conduct a study that incurs a price. Our goal is to find a spanning tree while minimizing the disutility, which is the sum of the tree cost and the total price that we spend on the studies. In a different application, each edge gives a stochastic reward value. Our goal is to find a spanning tree while maximizing the utility, which is the tree reward minus the prices that we pay. Situations such as the above two often arise in practice where we wish to find a good solution to an optimization problem, but we start with only some partial knowledge about the parameters of the problem. The missing information can be found only after paying a probing price, which we call the price of information. What strategy should we adopt to optimize our expected utility/disutility? A classical example of the above setting is Weitzman's "Pandora's box" problem where we are given probability distributions on values of $n$ independent random variables. The goal is to choose a single variable with a large value, but we can find the actual outcomes only after paying a price. Our work is a generalization of this model to other combinatorial optimization problems such as matching, set cover, facility location, and prize-collecting Steiner tree. We give a technique that reduces such problems to their non-price counterparts, and use it to design exact/approximation algorithms to optimize our utility/disutility. Our techniques extend to situations where there are additional constraints on what parameters can be probed or when we can simultaneously probe a subset of the parameters.
Performance Analysis for Massive MIMO Downlink with Low Complexity Approximate Zero-Forcing Precoding
Venue: arXiv cs.IT 2017
Year: 2017

Zero-forcing (ZF) precoding plays an important role for massive MIMO downlink due to its near optimal performance. However, the high computation cost of the involved matrix inversion hinders its application. In this paper, we adopt the first order Neumann series (NS) for a low-complexity approximation. By introducing a relaxation parameter jointly with one selected user's interference to others into the precondition matrix, we propose the identity-plus-column NS (ICNS) method. By further exploiting the multi-user diversity gain via choosing the user with the largest interference to others, the ordered ICNS method is also proposed. Moreover, the sum-rate approximations of the proposed ICNS method and the competitive existing identity matrix based NS (INS) method are derived in closed-form, based on which the performance loss of ICNS due to inversion approximation compared with ideal ZF and its performance gain over INS are explicitly analyzed for three typical massive MIMO scenarios. Finally, simulations verify our analytical results and also show that the proposed two designs achieve better performance-complexity tradeoff than ideal ZF and existing low-complexity ZF precodings for practical large antenna number, correlated channels and not-so-small loading factor.
Learning with Latent Language
Venue: arXiv cs.CL 2017
Year: 2017

The named concepts and compositional operators present in natural language provide a rich source of information about the kinds of abstractions humans use to navigate the world. Can this linguistic background knowledge improve the generality and efficiency of learned classifiers and control policies? This paper aims to show that using the space of natural language strings as a parameter space is an effective way to capture natural task structure. In a pretraining phase, we learn a language interpretation model that transforms inputs (e.g. images) into outputs (e.g. labels) given natural language descriptions. To learn a new concept (e.g. a classifier), we search directly in the space of descriptions to minimize the interpreter's loss on training examples. Crucially, our models do not require language data to learn these concepts: language is used only in pretraining to impose structure on subsequent learning. Results on image classification, text editing, and reinforcement learning show that, in all settings, models with a linguistic parameterization outperform those without.
Learning One-hidden-layer Neural Networks with Landscape Design
Venue: arXiv cs.LG 2017
Year: 2017

We consider the problem of learning a one-hidden-layer neural network: we assume the input $x\in \mathbb{R}^d$ is from Gaussian distribution and the label $y = a^\top σ(Bx) + ξ$, where $a$ is a nonnegative vector in $\mathbb{R}^m$ with $m\le d$, $B\in \mathbb{R}^{m\times d}$ is a full-rank weight matrix, and $ξ$ is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously. Inspired by the formula, we design a non-convex objective function $G(\cdot)$ whose landscape is guaranteed to have the following properties: 1. All local minima of $G$ are also global minima. 2. All global minima of $G$ correspond to the ground truth parameters. 3. The value and gradient of $G$ can be estimated using samples. With these properties, stochastic gradient descent on $G$ provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity result and validate the results by simulations.
Random Subspace Two-dimensional LDA for Face Recognition
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, a novel technique named random subspace two-dimensional LDA (RS-2DLDA) is developed for face recognition. This approach offers a number of improvements over the random subspace two-dimensional PCA (RS2DPCA) framework introduced by Nguyen et al. [5]. Firstly, the eigenvectors from 2DLDA have more discriminative power than those from 2DPCA, resulting in higher accuracy for the RS-2DLDA method over RS-2DPCA. Various distance metrics are evaluated, and a weighting scheme is developed to further boost accuracy. A series of experiments on the MORPH-II and ORL datasets are conducted to demonstrate the effectiveness of this approach.
TCPSnitch: Dissecting the Usage of the Socket API
Venue: arXiv cs.NI 2017
Year: 2017

Networked applications interact with the TCP/IP stack through the socket API. Over the years, various extensions have been added to this popular API. In this paper, we propose and implement the TCPSnitch software that tracks the interactions between Linux and Android applications and the TCP/IP stack. We collect a dataset containing the interactions produced by more than 120 different applications. Our analysis reveals that applications use a variety of API calls. On Android, many applications use various socket options even if the Java API does not expose them directly. TCPSnitch and the associated dataset are publicly available.
A Universal Marginalizer for Amortized Inference in Generative Models
Venue: arXiv cs.LG 2017
Year: 2017

We consider the problem of inference in a causal generative model where the set of available observations differs between data instances. We show how combining samples drawn from the graphical model with an appropriate masking function makes it possible to train a single neural network to approximate all the corresponding conditional marginal distributions and thus amortize the cost of inference. We further demonstrate that the efficiency of importance sampling may be improved by basing proposals on the output of the neural network. We also outline how the same network can be used to generate samples from an approximate joint posterior via a chain decomposition of the graph.
Adaptive coordination of working-memory and reinforcement learning in non-human primates performing a trial-and-error problem solving task
Venue: arXiv cs.AI 2017
Year: 2017

Accumulating evidence suggest that human behavior in trial-and-error learning tasks based on decisions between discrete actions may involve a combination of reinforcement learning (RL) and working-memory (WM). While the understanding of brain activity at stake in this type of tasks often involve the comparison with non-human primate neurophysiological results, it is not clear whether monkeys use similar combined RL and WM processes to solve these tasks. Here we analyzed the behavior of five monkeys with computational models combining RL and WM. Our model-based analysis approach enables to not only fit trial-by-trial choices but also transient slowdowns in reaction times, indicative of WM use. We found that the behavior of the five monkeys was better explained in terms of a combination of RL and WM despite inter-individual differences. The same coordination dynamics we used in a previous study in humans best explained the behavior of some monkeys while the behavior of others showed the opposite pattern, revealing a possible different dynamics of WM process. We further analyzed different variants of the tested models to open a discussion on how the long pretraining in these tasks may have favored particular coordination dynamics between RL and WM. This points towards either inter-species differences or protocol differences which could be further tested in humans.
Doris: A tool for interactive exploration of historic corpora (Extended Version)
Venue: arXiv cs.HC 2017
Year: 2017

Insights into social phenomenon can be gleaned from trends and patterns in corpora of documents associated with that phenomenon. Recent years have witnessed the use of computational techniques, mostly based on keywords, to analyze large corpora for these purposes. In this paper, we extend these techniques to incorporate semantic features. We introduce Doris, an interactive exploration tool that combines semantic features with information retrieval techniques to enable exploration of document corpora corresponding to the social phenomenon. We discuss the semantic techniques and describe an implementation on a corpus of United States (US) presidential speeches. We illustrate, with examples, how the ability to combine syntactic and semantic features in a visualization helps researchers more easily gain insights into the underlying phenomenon.
Stochastic Routing and Scheduling Policies for Energy Harvesting Communication Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study the joint routing-scheduling problem in energy harvesting communication networks. Our policies, which are based on stochastic subgradient methods on the dual domain, act as an energy harvesting variant of the stochastic family of backpresure algorithms. Specifically, we propose two policies: (i) the Stochastic Backpressure with Energy Harvesting (SBP-EH), in which a node's routing-scheduling decisions are determined by the difference between the Lagrange multipliers associated to their queue stability constraints and their neighbors'; and (ii) the Stochastic Soft Backpressure with Energy Harvesting (SSBP-EH), an improved algorithm where the routing-scheduling decision is of a probabilistic nature. For both policies, we show that given sustainable data and energy arrival rates, the stability of the data queues over all network nodes is guaranteed. Numerical results corroborate the stability guarantees and illustrate the minimal gap in performance that our policies offer with respect to classical ones which work with an unlimited energy supply.
Scalable Approximation Algorithm for Network Immunization
Venue: arXiv cs.DM 2017
Year: 2017

The problem of identifying important players in a given network is of pivotal importance for viral marketing, public health management, network security and various other fields of social network analysis. In this work we find the most important vertices in a graph G = (V,E) to immunize so as the chances of an epidemic outbreak is minimized. This problem is directly relevant to minimizing the impact of a contagion spread (e.g. flu virus, computer virus and rumor) in a graph (e.g. social network, computer network) with a limited budget (e.g. the number of available vaccines, antivirus software, filters). It is well known that this problem is computationally intractable (it is NP-hard). In this work we reformulate the problem as a budgeted combinational optimization problem and use techniques from spectral graph theory to design an efficient greedy algorithm to find a subset of vertices to be immunized. We show that our algorithm takes less time compared to the state of the art algorithm. Thus our algorithm is scalable to networks of much larger sizes than best known solutions proposed earlier. We also give analytical bounds on the quality of our algorithm. Furthermore, we evaluate the efficacy of our algorithm on a number of real world networks and demonstrate that the empirical performance of algorithm supplements the theoretical bounds we present, both in terms of approximation guarantees and computational efficiency.
On the complexity of optimal homotopies
Venue: arXiv cs.CG 2017
Year: 2017

In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves $γ_1$ and $γ_2$ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between $γ_1$ and $γ_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Fréchet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.
BinPro: A Tool for Binary Source Code Provenance
Venue: arXiv cs.CR 2017
Year: 2017

Enforcing open source licenses such as the GNU General Public License (GPL), analyzing a binary for possible vulnerabilities, and code maintenance are all situations where it is useful to be able to determine the source code provenance of a binary. While previous work has either focused on computing binary-to-binary similarity or source-to-source similarity, BinPro is the first work we are aware of to tackle the problem of source-to-binary similarity. BinPro can match binaries with their source code even without knowing which compiler was used to produce the binary, or what optimization level was used with the compiler. To do this, BinPro utilizes machine learning to compute optimal code features for determining binary-to-source similarity and a static analysis pipeline to extract and compute similarity based on those features. Our experiments show that on average BinPro computes a similarity of 81% for matching binaries and source code of the same applications, and an average similarity of 25% for binaries and source code of similar but different applications. This shows that BinPro's similarity score is useful for determining if a binary was derived from a particular source code.
Does Phase Matter For Monaural Source Separation?
Venue: arXiv cs.SD 2017
Year: 2017

The "cocktail party" problem of fully separating multiple sources from a single channel audio waveform remains unsolved. Current biological understanding of neural encoding suggests that phase information is preserved and utilized at every stage of the auditory pathway. However, current computational approaches primarily discard phase information in order to mask amplitude spectrograms of sound. In this paper, we seek to address whether preserving phase information in spectral representations of sound provides better results in monaural separation of vocals from a musical track by using a neurally plausible sparse generative model. Our results demonstrate that preserving phase information reduces artifacts in the separated tracks, as quantified by the signal to artifact ratio (GSAR). Furthermore, our proposed method achieves state-of-the-art performance for source separation, as quantified by a mean signal to interference ratio (GSIR) of 19.46.
Dynamic Influence Networks for Rule-based Models
Venue: arXiv cs.GR 2017
Year: 2017

We introduce the Dynamic Influence Network (DIN), a novel visual analytics technique for representing and analyzing rule-based models of protein-protein interaction networks. Rule-based modeling has proved instrumental in developing biological models that are concise, comprehensible, easily extensible, and that mitigate the combinatorial complexity of multi-state and multi-component biological molecules. Our technique visualizes the dynamics of these rules as they evolve over time. Using the data produced by KaSim, an open source stochastic simulator of rule-based models written in the Kappa language, DINs provide a node-link diagram that represents the influence that each rule has on the other rules. That is, rather than representing individual biological components or types, we instead represent the rules about them (as nodes) and the current influence of these rules (as links). Using our interactive DIN-Viz software tool, researchers are able to query this dynamic network to find meaningful patterns about biological processes, and to identify salient aspects of complex rule-based models. To evaluate the effectiveness of our approach, we investigate a simulation of a circadian clock model that illustrates the oscillatory behavior of the KaiC protein phosphorylation cycle.
PS-DBSCAN: An Efficient Parallel DBSCAN Algorithm Based on Platform Of AI (PAI)
Venue: arXiv cs.DB 2017
Year: 2017

We present PS-DBSCAN, a communication efficient parallel DBSCAN algorithm that combines the disjoint-set data structure and Parameter Server framework in Platform of AI (PAI). Since data points within the same cluster may be distributed over different workers which result in several disjoint-sets, merging them incurs large communication costs. In our algorithm, we employ a fast global union approach to union the disjoint-sets to alleviate the communication burden. Experiments over the datasets of different scales demonstrate that PS-DBSCAN outperforms the PDSDBSCAN with 2-10 times speedup on communication efficiency. We have released our PS-DBSCAN in an algorithm platform called Platform of AI (PAI - https://pai.base.shuju.aliyun.com/) in Alibaba Cloud. We have also demonstrated how to use the method in PAI.
Optimal Pricing-Based Edge Computing Resource Management in Mobile Blockchain
Venue: arXiv cs.GT 2017
Year: 2017

As the core issue of blockchain, the mining requires solving a proof-of-work puzzle, which is resource expensive to implement in mobile devices due to high computing power needed. Thus, the development of blockchain in mobile applications is restricted. In this paper, we consider the edge computing as the network enabler for mobile blockchain. In particular, we study optimal pricing-based edge computing resource management to support mobile blockchain applications where the mining process can be offloaded to an Edge computing Service Provider (ESP). We adopt a two-stage Stackelberg game to jointly maximize the profit of the ESP and the individual utilities of different miners. In Stage I, the ESP sets the price of edge computing services. In Stage II, the miners decide on the service demand to purchase based on the observed prices. We apply the backward induction to analyze the sub-game perfect equilibrium in each stage for uniform and discriminatory pricing schemes. Further, the existence and uniqueness of Stackelberg game are validated for both pricing schemes. At last, the performance evaluation shows that the ESP intends to set the maximum possible value as the optimal price for profit maximization under uniform pricing. In addition, the discriminatory pricing helps the ESP encourage higher total service demand from miners and achieve greater profit correspondingly.
On the Capacity of SWIPT Systems with a Nonlinear Energy Harvesting Circuit
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study information-theoretic limits for simultaneous wireless information and power transfer (SWIPT) systems employing a practical nonlinear radio frequency (RF) energy harvesting (EH) receiver. In particular, we consider a three-node system with one transmitter that broadcasts a common signal to separated information decoding (ID) and EH receivers. Owing to the nonlinearity of the EH receiver circuit, the efficiency of wireless power transfer depends significantly on the waveform of the transmitted signal. In this paper, we aim to answer the following fundamental question: What is the optimal input distribution of the transmit waveform that maximizes the rate of the ID receiver for a given required harvested power at the EH receiver? In particular, we study the capacity of a SWIPT system impaired by additive white Gaussian noise (AWGN) under average-power (AP) and peak-power (PP) constraints at the transmitter and an EH constraint at the EH receiver. Using Hermite polynomial bases, we prove that the optimal capacity-achieving input distribution that maximizes the rate-energy region is unique and discrete with a finite number of mass points. Furthermore, we show that the optimal input distribution for the same problem without PP constraint is discrete whenever the EH constraint is active and continuous zero-mean Gaussian, otherwise. Our numerical results show that the rate-energy region is enlarged for a larger PP constraint and that the rate loss of the considered SWIPT system compared to the AWGN channel without EH receiver is reduced by increasing the AP budget.