OpenRaiser/Intern-Atlas huggingface dataset:
Task-driven sampling of attributed networks
Venue: arXiv cs.SI 2017
Year: 2017

This paper introduces new techniques for sampling attributed networks to support standard Data Mining tasks. The problem is important for two reasons. First, it is commonplace to perform data mining tasks such as clustering and classification of network attributes (attributes of the nodes, including social media posts). Furthermore, the extraordinarily large size of real-world networks necessitates that we work with a smaller graph sample. Second, while random sampling will provide an unbiased estimate of content, random access is often unavailable for many networks. Hence, network samplers such as Snowball sampling, Forest Fire, Random Walk, Metropolis-Hastings Random Walk are widely used; however, these attribute-agnostic samplers were designed to capture salient properties of network structure, not node content. The latter is critical for clustering and classification tasks. There are three contributions of this paper. First, we introduce several attribute-aware samplers based on Information Theoretic principles. Second, we prove that these samplers have a bias towards capturing new content, and are equivalent to uniform sampling in the limit. Finally, our experimental results over large real-world datasets and synthetic benchmarks are insightful: attribute-aware samplers outperform both random sampling and baseline attribute-agnostic samplers by a wide margin in clustering and classification tasks.
Reply & Supply: Efficient crowdsourcing when workers do more than answer questions
Venue: arXiv cs.SI 2017
Year: 2017

Crowdsourcing works by distributing many small tasks to large numbers of workers, yet the true potential of crowdsourcing lies in workers doing more than performing simple tasks---they can apply their experience and creativity to provide new and unexpected information to the crowdsourcer. One such case is when workers not only answer a crowdsourcer's questions but also contribute new questions for subsequent crowd analysis, leading to a growing set of questions. This growth creates an inherent bias for early questions since a question introduced earlier by a worker can be answered by more subsequent workers than a question introduced later. Here we study how to perform efficient crowdsourcing with such growing question sets. By modeling question sets as networks of interrelated questions, we introduce algorithms to help curtail the growth bias by efficiently distributing workers between exploring new questions and addressing current questions. Experiments and simulations demonstrate that these algorithms can efficiently explore an unbounded set of questions without losing confidence in crowd answers.
The Complexity of Holant Problems over Boolean Domain with Non-negative Weights
Venue: arXiv cs.CC 2017
Year: 2017

Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice $\#$CSPs. Intuitively, some $\#$CSPs that are $\#$P-hard become tractable when restricting to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set $\mathcal{F}$ satisfies the condition, then $\mathcal{F}$ is of affine type or product type. Otherwise (a) $\mathrm{Holant}(\mathcal{F})$ is $\#$P-hard; or (b) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; or (c) $\mathcal{F}$ is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.
Topological Interference Management: Linear Cooperation is not useful for Wyner's Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we study the value of cooperative transmission in wireless networks if no channel state information is available at the transmitters (no CSIT). Our focus is on large locally connected networks, where each transmitter is connected to the receiver that has the same index as well as L succeeding receivers. The cases of L=1 and L=2 represent Wyner's asymmetric and symmetric network models, respectively. The considered rate criterion is the per user Degrees of Freedom (puDoF) as the number of transmitter-receiver pairs goes to infinity. For the case when L=1, it was shown in previous work that linear cooperation schemes do not increases the puDoF value, and that the optimal scheme relies on assigning each message to a single transmitter and using orthogonal access (TDMA). Here, we extend this conclusion to the case where L=2, by proving optimality of TDMA in this case as well. We conclude by discussing whether increasing the value of L can create a value for linear cooperation schemes from a DoF perspective.
STDP-based spiking deep convolutional neural networks for object recognition
Venue: arXiv cs.CV 2017
Year: 2017

Previous studies have shown that spike-timing-dependent plasticity (STDP) can be used in spiking neural networks (SNN) to extract visual features of low or intermediate complexity in an unsupervised manner. These studies, however, used relatively shallow architectures, and only one layer was trainable. Another line of research has demonstrated - using rate-based neural networks trained with back-propagation - that having many layers increases the recognition robustness, an approach known as deep learning. We thus designed a deep SNN, comprising several convolutional (trainable with STDP) and pooling layers. We used a temporal coding scheme where the most strongly activated neurons fire first, and less activated neurons fire later or not at all. The network was exposed to natural images. Thanks to STDP, neurons progressively learned features corresponding to prototypical patterns that were both salient and frequent. Only a few tens of examples per category were required and no label was needed. After learning, the complexity of the extracted features increased along the hierarchy, from edge detectors in the first layer to object prototypes in the last layer. Coding was very sparse, with only a few thousands spikes per image, and in some cases the object category could be reasonably well inferred from the activity of a single higher-order neuron. More generally, the activity of a few hundreds of such neurons contained robust category information, as demonstrated using a classifier on Caltech 101, ETH-80, and MNIST databases. We also demonstrate the superiority of STDP over other unsupervised techniques such as random crops (HMAX) or auto-encoders. Taken together, our results suggest that the combination of STDP with latency coding may be a key to understanding the way that the primate visual system learns, its remarkable processing speed and its low energy consumption.
Learning a Static Analyzer from Data
Venue: arXiv cs.PL 2017
Year: 2017

To be practically useful, modern static analyzers must precisely model the effect of both, statements in the programming language as well as frameworks used by the program under analysis. While important, manually addressing these challenges is difficult for at least two reasons: (i) the effects on the overall analysis can be non-trivial, and (ii) as the size and complexity of modern libraries increase, so is the number of cases the analysis must handle. In this paper we present a new, automated approach for creating static analyzers: instead of manually providing the various inference rules of the analyzer, the key idea is to learn these rules from a dataset of programs. Our method consists of two ingredients: (i) a synthesis algorithm capable of learning a candidate analyzer from a given dataset, and (ii) a counter-example guided learning procedure which generates new programs beyond those in the initial dataset, critical for discovering corner cases and ensuring the learned analysis generalizes to unseen programs. We implemented and instantiated our approach to the task of learning JavaScript static analysis rules for a subset of points-to analysis and for allocation sites analysis. These are challenging yet important problems that have received significant research attention. We show that our approach is effective: our system automatically discovered practical and useful inference rules for many cases that are tricky to manually identify and are missed by state-of-the-art, manually tuned analyzers.
Bayesian Optimisation with Prior Reuse for Motion Planning in Robot Soccer
Venue: arXiv cs.RO 2017
Year: 2017

We integrate learning and motion planning for soccer playing differential drive robots using Bayesian optimisation. Trajectories generated using end-slope cubic Bezier splines are first optimised globally through Bayesian optimisation for a set of candidate points with obstacles. The optimised trajectories along with robot and obstacle positions and velocities are stored in a database. The closest planning situation is identified from the database using k-Nearest Neighbour approach. It is further optimised online through reuse of prior information from previously optimised trajectory. Our approach reduces computation time of trajectory optimisation considerably. Velocity profiling generates velocities consistent with robot kinodynamoic constraints, and avoids collision and slipping. Extensive testing is done on developed simulator, as well as on physical differential drive robots. Our method shows marked improvements in mitigating tracking error, and reducing traversal and computational time over competing techniques under the constraints of performing tasks in real time.
Memory-augmented Attention Modelling for Videos
Venue: arXiv cs.CV 2017
Year: 2017

We present a method to improve video description generation by modeling higher-order interactions between video frames and described concepts. By storing past visual attention in the video associated to previously generated words, the system is able to decide what to look at and describe in light of what it has already looked at and described. This enables not only more effective local attention, but tractable consideration of the video sequence while generating each word. Evaluation on the challenging and popular MSVD and Charades datasets demonstrates that the proposed architecture outperforms previous video description approaches without requiring external temporal video features.
Learning from Untrusted Data
Venue: arXiv cs.LG 2017
Year: 2017

The vast majority of theoretical results in machine learning and statistics assume that the available training data is a reasonably reliable reflection of the phenomena to be learned or estimated. Similarly, the majority of machine learning and statistical techniques used in practice are brittle to the presence of large amounts of biased or malicious data. In this work we consider two frameworks in which to study estimation, learning, and optimization in the presence of significant fractions of arbitrary data. The first framework, list-decodable learning, asks whether it is possible to return a list of answers, with the guarantee that at least one of them is accurate. For example, given a dataset of $n$ points for which an unknown subset of $αn$ points are drawn from a distribution of interest, and no assumptions are made about the remaining $(1-α)n$ points, is it possible to return a list of $\operatorname{poly}(1/α)$ answers, one of which is correct? The second framework, which we term the semi-verified learning model, considers the extent to which a small dataset of trusted data (drawn from the distribution in question) can be leveraged to enable the accurate extraction of information from a much larger but untrusted dataset (of which only an $α$-fraction is drawn from the distribution). We show strong positive results in both settings, and provide an algorithm for robust learning in a very general stochastic optimization setting. This general result has immediate implications for robust estimation in a number of settings, including for robustly estimating the mean of distributions with bounded second moments, robustly learning mixtures of such distributions, and robustly finding planted partitions in random graphs in which significant portions of the graph have been perturbed by an adversary.
Chaos-based Wireless Communication Resisting Multipath Effects
Venue: arXiv cs.IT 2017
Year: 2017

In additive white gaussian noise (AWGN) channel, chaos has been proved to be the optimal coherent communication waveform in the sense of using very simple matched filter to maximize the signal-to-noise ratio (SNR). Recently, Lyapunov exponent spectrum of the chaotic signals after being transmitted through a wireless channel has been shown to be unaltered, paving the way for wireless communication using chaos. In wireless communication systems, inter-symbol interference (ISI) caused by multipath propagation is one of the main obstacles to achieve high bit transmission rate and low bit error rate (BER). How to resist multipath effect is a fundamental problem in a chaos-based wireless communication system (CWCS). In this paper, implementation of a CWCS is presented. It is built to transmit chaotic signals generated by a hybrid dynamical system and then to filter the received signals by using the corresponding matched filter to decrease the noise effect and to detect the binary information. We find that the multipath effect can be effectively resisted by regrouping the return map of the received signal and by setting the corresponding threshold based on the available information. We show that the optimal threshold is a function of the channel parameters and of the transmitted information symbols. Practically, the channel parameters are time-variant, and the future information symbols are unavailable. In this case, a suboptimal threshold (SOT) is proposed, and the BER using the SOT is derived analytically. Simulation results show that the CWCS achieves a remarkable competitive performance even under inaccurate channel parameters.
Price Doubling and Item Halving: Robust Revenue Guarantees for Item Pricing
Venue: arXiv cs.GT 2017
Year: 2017

We study approximation algorithms for revenue maximization based on static item pricing, where a seller chooses prices for various goods in the market, and then the buyers purchase utility-maximizing bundles at these given prices. We formulate two somewhat general techniques for designing good pricing algorithms for this setting: Price Doubling and Item Halving. Using these techniques, we unify many of the existing results in the item pricing literature under a common framework, as well as provide several new item pricing algorithms for approximating both revenue and social welfare. More specifically, for a variety of settings with item pricing, we show that it is possible to deterministically obtain a log-approximation for revenue and a constant-approximation for social welfare simultaneously: thus one need not sacrifice revenue if the goal is to still have decent welfare guarantees. %In addition, we provide a new black-box reduction from revenue to welfare based on item pricing, which immediately gives us new revenue-approximation algorithms (e.g., for gross substitutes valuations). The main technical contribution of this paper is a $O((\log m + \log k)^2)$-approximation algorithm for revenue maximization based on the Item Halving technique, for settings where buyers have XoS valuations, where $m$ is the number of goods and $k$ is the average supply. Surprisingly, ours is the first known item pricing algorithm with polylogarithmic approximations for such general classes of valuations, and partially resolves an important open question from the algorithmic pricing literature about the existence of item pricing algorithms with logarithmic factors for general valuations. We also use the Item Halving framework to form envy-free item pricing mechanisms for the popular setting of multi-unit markets, providing a log-approximation to revenue in this case.
Network-wide Configuration Synthesis
Venue: arXiv cs.NI 2017
Year: 2017

Computer networks are hard to manage. Given a set of high-level requirements (e.g., reachability, security), operators have to manually figure out the individual configuration of potentially hundreds of devices running complex distributed protocols so that they, collectively, compute a compatible forwarding state. Not surprisingly, operators often make mistakes which lead to downtimes. To address this problem, we present a novel synthesis approach that automatically computes correct network configurations that comply with the operator's requirements. We capture the behavior of existing routers along with the distributed protocols they run in stratified Datalog. Our key insight is to reduce the problem of finding correct input configurations to the task of synthesizing inputs for a stratified Datalog program. To solve this synthesis task, we introduce a new algorithm that synthesizes inputs for stratified Datalog programs. This algorithm is applicable beyond the domain of networks. We leverage our synthesis algorithm to construct the first network-wide configuration synthesis system, called SyNET, that support multiple interacting routing protocols (OSPF and BGP) and static routes. We show that our system is practical and can infer correct input configurations, in a reasonable amount time, for networks of realistic size (> 50 routers) that forward packets for multiple traffic classes.
PixelSNE: Visualizing Fast with Just Enough Precision via Pixel-Aligned Stochastic Neighbor Embedding
Venue: arXiv cs.LG 2017
Year: 2017

Embedding and visualizing large-scale high-dimensional data in a two-dimensional space is an important problem since such visualization can reveal deep insights out of complex data. Most of the existing embedding approaches, however, run on an excessively high precision, ignoring the fact that at the end, embedding outputs are converted into coarse-grained discrete pixel coordinates in a screen space. Motivated by such an observation and directly considering pixel coordinates in an embedding optimization process, we accelerate Barnes-Hut tree-based t-distributed stochastic neighbor embedding (BH-SNE), known as a state-of-the-art 2D embedding method, and propose a novel method called PixelSNE, a highly-efficient, screen resolution-driven 2D embedding method with a linear computational complexity in terms of the number of data items. Our experimental results show the significantly fast running time of PixelSNE by a large margin against BH-SNE, while maintaining the minimal degradation in the embedding quality. Finally, the source code of our method is publicly available at https://github.com/awesome-davian/PixelSNE
Sentence Ordering and Coherence Modeling using Recurrent Neural Networks
Venue: arXiv cs.CL 2017
Year: 2017

Modeling the structure of coherent texts is a key NLP problem. The task of coherently organizing a given set of sentences has been commonly used to build and evaluate models that understand such structure. We propose an end-to-end unsupervised deep learning approach based on the set-to-sequence framework to address this problem. Our model strongly outperforms prior methods in the order discrimination task and a novel task of ordering abstracts from scientific articles. Furthermore, our work shows that useful text representations can be obtained by learning to order sentences. Visualizing the learned sentence representations shows that the model captures high-level logical structure in paragraphs. Our representations perform comparably to state-of-the-art pre-training methods on sentence similarity and paraphrase detection tasks.
Variational Lossy Autoencoder
Venue: arXiv cs.LG 2017
Year: 2017

Representation learning seeks to expose certain aspects of observed data in a learned representation that's amenable to downstream tasks like classification. For instance, a good representation for 2D images might be one that describes only global structure and discards information about detailed texture. In this paper, we present a simple but principled method to learn such global representations by combining Variational Autoencoder (VAE) with neural autoregressive models such as RNN, MADE and PixelRNN/CNN. Our proposed VAE model allows us to have control over what the global latent code can learn and , by designing the architecture accordingly, we can force the global latent code to discard irrelevant information such as texture in 2D images, and hence the VAE only "autoencodes" data in a lossy fashion. In addition, by leveraging autoregressive models as both prior distribution $p(z)$ and decoding distribution $p(x|z)$, we can greatly improve generative modeling performance of VAEs, achieving new state-of-the-art results on MNIST, OMNIGLOT and Caltech-101 Silhouettes density estimation tasks.
Tight Lower Bounds for the Longest Common Extension Problem
Venue: arXiv cs.DS 2017
Year: 2017

The longest common extension problem is to preprocess a given string of length $n$ into a data structure that uses $S(n)$ bits on top of the input and answers in $T(n)$ time the queries $\mathit{LCE}(i,j)$ computing the length of the longest string that occurs at both positions $i$ and $j$ in the input. We prove that the trade-off $S(n)T(n) = Ω(n\log n)$ holds in the non-uniform cell-probe model provided that the input string is read-only, each letter occupies a separate memory cell, $S(n) = Ω(n)$, and the size of the input alphabet is at least $2^{8\lceil S(n) / n\rceil}$. It is known that this trade-off is tight.
Node Embedding via Word Embedding for Network Community Discovery
Venue: arXiv cs.SI 2017
Year: 2017

Neural node embeddings have recently emerged as a powerful representation for supervised learning tasks involving graph-structured data. We leverage this recent advance to develop a novel algorithm for unsupervised community discovery in graphs. Through extensive experimental studies on simulated and real-world data, we demonstrate that the proposed approach consistently improves over the current state-of-the-art. Specifically, our approach empirically attains the information-theoretic limits for community recovery under the benchmark Stochastic Block Models for graph generation and exhibits better stability and accuracy over both Spectral Clustering and Acyclic Belief Propagation in the community recovery limits.