OpenRaiser/Intern-Atlas huggingface dataset:
Robust nonparametric nearest neighbor random process clustering
Venue: arXiv cs.LG 2017
Year: 2017

We consider the problem of clustering noisy finite-length observations of stationary ergodic random processes according to their generative models without prior knowledge of the model statistics and the number of generative models. Two algorithms, both using the $L^1$-distance between estimated power spectral densities (PSDs) as a measure of dissimilarity, are analyzed. The first one, termed nearest neighbor process clustering (NNPC), relies on partitioning the nearest neighbor graph of the observations via spectral clustering. The second algorithm, simply referred to as $k$-means (KM), consists of a single $k$-means iteration with farthest point initialization and was considered before in the literature, albeit with a different dissimilarity measure. We prove that both algorithms succeed with high probability in the presence of noise and missing entries, and even when the generative process PSDs overlap significantly, all provided that the observation length is sufficiently large. Our results quantify the tradeoff between the overlap of the generative process PSDs, the observation length, the fraction of missing entries, and the noise variance. Finally, we provide extensive numerical results for synthetic and real data and find that NNPC outperforms state-of-the-art algorithms in human motion sequence clustering.
Implementing and Evaluating Candidate-Based Invariant Generation
Venue: arXiv cs.SE 2017
Year: 2017

The discovery of inductive invariants lies at the heart of static program verification. Presently, many automatic solutions to inductive invariant generation are inflexible, only applicable to certain classes of programs, or unpredictable. An automatic technique that circumvents these deficiencies to some extent is candidate-based invariant generation. This paper describes our efforts to apply candidate-based invariant generation in GPUVerify, a static checker for programs that run on GPUs. We study a set of GPU programs that contain loops, drawn from a number of open source suites and vendor SDKs. We describe the methodology we used to incrementally improve the invariant generation capabilities of GPUVerify to handle these benchmarks, through candidate-based invariant generation, using cheap static analysis to speculate potential program invariants. We also describe a set of experiments that we used to examine the effectiveness of our rules for candidate generation, assessing rules based on their generality (the extent to which they generate candidate invariants), hit rate (the extent to which the generated candidates hold), worth (the extent to which provable candidates actually help in allowing verification to succeed), and influence (the extent to which the success of one generation rule depends on candidates generated by another rule). The candidates produced by GPUVerify help to verify 231 of the 253 programs. This increase in precision, however, makes GPUVerify sluggish: the more candidates that are generated, the more time is spent determining which are inductive invariants. To speed up this process, we have investigated four under-approximating program analyses that aim to reject false candidates quickly and a framework whereby these analyses can run in sequence or in parallel.
Throughput of Infrastructure-based Cooperative Vehicular Networks
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we provide detailed analysis of the achievable throughput of infrastructure-based vehicular network with a finite traffic density under a cooperative communication strategy, which explores combined use of vehicle-to-infrastructure (V2I) communications, vehicle-to-vehicle (V2V) communications, mobility of vehicles and cooperations among vehicles and infrastructure to facilitate the data transmission. A closed form expression of the achievable throughput is obtained, which reveals the relationship between the achievable throughput and its major performance-impacting parameters such as distance between adjacent infrastructure points, radio ranges of infrastructure and vehicles, transmission rates of V2I and V2V communications and vehicular density. Numerical and simulation results show that the proposed cooperative communication strategy significantly increases the throughput of vehicular networks, compared with its non-cooperative counterpart, even when the traffic density is low. Our results shed insight on the optimum deployment of vehicular network infrastructure and optimum design of cooperative communication strategies in vehicular networks to maximize the throughput.
On the existence of weak subgame perfect equilibria
Venue: arXiv cs.GT 2017
Year: 2017

We study multi-player turn-based games played on (potentially infinite) directed graphs. An outcome is assigned to every play of the game. Each player has a preference relation on the set of outcomes which allows him to compare plays. We focus on the recently introduced notion of weak subgame perfect equilibrium (weak SPE). This is a variant of the classical notion of SPE, where players who deviate can only use strategies deviating from their initial strategy in a finite number of histories. Having an SPE in a game implies having a weak SPE but the contrary is generally false. We propose general conditions on the structure of the game graph and on the preference relations of the players that guarantee the existence of a weak SPE, that additionally is finite-memory. From this general result, we derive two large classes of games for which there always exists a weak SPE: (i) the games with a finite-range outcome function, and (ii) the games with a finite underlying graph and a prefix-independent outcome function. For the second class, we identify conditions on the preference relations that guarantee memoryless strategies for the weak SPE.
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problem
Venue: arXiv cs.CC 2017
Year: 2017

Metric facility location and $K$-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete $K$-means problem is tightly PLS-complete and hence has exponential worst-case running time.
An algorithm to assign musical prime commas to every prime number and construct a universal and compact free Just Intonation musical notation
Venue: arXiv cs.SD 2017
Year: 2017

Musical frequencies in Just Intonation are comprised of rational numbers. The structure of rational numbers is determined by prime factorisations. Just Intonation frequencies can be split into two components. The larger component uses only integer powers of the first two primes, 2 and 3. The smaller component decomposes into a series of microtonal adjustments, one for each prime number 5 and above present in the original frequency. The larger 3-limit component can be notated using scientific pitch notation modified to use Pythagorean tuning. The microtonal adjustments can be notated using rational commas which are built up from prime commas. This gives a notation system for the whole of free-JI, called Rational Comma Notation. RCN is compact since all microtonal adjustments can be represented by a single notational unit based on a rational number. RCN has different versions depending on the choice of algorithm to assign a prime comma to each prime number. Two existing algorithms SAG and KG2 are found in the literature. A novel algorithm DR is developed based on discussion of mathematical and musical criteria for algorithm design. Results for DR are presented for primes below 1400. Some observations are made about these results and their applications, including shorthand notation and pitch class lattices. Results for DR are compared with those for SAG and KG2. Translation is possible between any two free-JI notations and any two versions of RCN since they all represent the same underlying set of rational numbers.
Tag Prediction at Flickr: a View from the Darkroom
Venue: arXiv cs.CV 2017
Year: 2017

Automated photo tagging has established itself as one of the most compelling applications of deep learning. While deep convolutional neural networks have repeatedly demonstrated top performance on standard datasets for classification, there are a number of often overlooked but important considerations when deploying this technology in a real-world scenario. In this paper, we present our efforts in developing a large-scale photo tagging system for Flickr photo search. We discuss topics including how to 1) select the tags that matter most to our users; 2) develop lightweight, high-performance models for tag prediction; and 3) leverage the power of large amounts of noisy data for training. Our results demonstrate that, for real-world datasets, training exclusively with this noisy data yields performance on par with the standard paradigm of first pre-training on clean data and then fine-tuning. In addition, we observe that the models trained with user-generated data can yield better fine-tuning results when a small amount of clean data is available. As such, we advocate for the approach of harnessing user-generated data in large-scale systems.
Porous Structure Design in Tissue Engineering Using Anisotropic Radial Basis Function
Venue: arXiv cs.GR 2017
Year: 2017

Development of additive manufacturing in last decade greatly improves tissue engineering. During the manufacturing of porous scaffold, simplified but functionally equivalent models are getting focused for practically reasons. Scaffolds can be classified into regular porous scaffolds and irregular porous scaffolds. Several methodologies are developed to design these scaffolds. A novel method is proposed in this paper using anisotropic radial basis function (ARBF) interpolation. This is method uses geometric models such as volumetric meshes as input and proves to be flexible because geometric models are able to capture the characteristics of complex tissues easily. Moreover, this method is straightforward and easy to implement.
Bottom-Up Top-Down Cues for Weakly-Supervised Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

We consider the task of learning a classifier for semantic segmentation using weak supervision in the form of image labels which specify the object classes present in the image. Our method uses deep convolutional neural networks (CNNs) and adopts an Expectation-Maximization (EM) based approach. We focus on the following three aspects of EM: (i) initialization; (ii) latent posterior estimation (E-step) and (iii) the parameter update (M-step). We show that saliency and attention maps, our bottom-up and top-down cues respectively, of simple images provide very good cues to learn an initialization for the EM-based algorithm. Intuitively, we show that before trying to learn to segment complex images, it is much easier and highly effective to first learn to segment a set of simple images and then move towards the complex ones. Next, in order to update the parameters, we propose minimizing the combination of the standard softmax loss and the KL divergence between the true latent posterior and the likelihood given by the CNN. We argue that this combination is more robust to wrong predictions made by the expectation step of the EM method. We support this argument with empirical and visual results. Extensive experiments and discussions show that: (i) our method is very simple and intuitive; (ii) requires only image-level labels; and (iii) consistently outperforms other weakly-supervised state-of-the-art methods with a very high margin on the PASCAL VOC 2012 dataset.
Individual Differential Privacy: A Utility-Preserving Formulation of Differential Privacy Guarantees
Venue: arXiv cs.CR 2017
Year: 2017

Differential privacy is a popular privacy model within the research community because of the strong privacy guarantee it offers, namely that the presence or absence of any individual in a data set does not significantly influence the results of analyses on the data set. However, enforcing this strict guarantee in practice significantly distorts data and/or limits data uses, thus diminishing the analytical utility of the differentially private results. In an attempt to address this shortcoming, several relaxations of differential privacy have been proposed that trade off privacy guarantees for improved data utility. In this work, we argue that the standard formalization of differential privacy is stricter than required by the intuitive privacy guarantee it seeks. In particular, the standard formalization requires indistinguishability of results between any pair of neighbor data sets, while indistinguishability between the actual data set and its neighbor data sets should be enough. This limits the data controller's ability to adjust the level of protection to the actual data, hence resulting in significant accuracy loss. In this respect, we propose individual differential privacy, an alternative differential privacy notion that offers em the same privacy guarantees as standard differential privacy to individuals (even though not to groups of individuals). This new notion allows the data controller to adjust the distortion to the actual data set, which results in less distortion and more analytical accuracy. We propose several mechanisms to attain individual differential privacy and we compare the new notion against standard differential privacy in terms of the accuracy of the analytical results.
Improving the Performance of Neural Machine Translation Involving Morphologically Rich Languages
Venue: arXiv cs.CL 2017
Year: 2017

The advent of the attention mechanism in neural machine translation models has improved the performance of machine translation systems by enabling selective lookup into the source sentence. In this paper, the efficiencies of translation using bidirectional encoder attention decoder models were studied with respect to translation involving morphologically rich languages. The English - Tamil language pair was selected for this analysis. First, the use of Word2Vec embedding for both the English and Tamil words improved the translation results by 0.73 BLEU points over the baseline RNNSearch model with 4.84 BLEU score. The use of morphological segmentation before word vectorization to split the morphologically rich Tamil words into their respective morphemes before the translation, caused a reduction in the target vocabulary size by a factor of 8. Also, this model (RNNMorph) improved the performance of neural machine translation by 7.05 BLEU points over the RNNSearch model used over the same corpus. Since the BLEU evaluation of the RNNMorph model might be unreliable due to an increase in the number of matching tokens per sentence, the performances of the translations were also compared by means of human evaluation metrics of adequacy, fluency and relative ranking. Further, the use of morphological segmentation also improved the efficacy of the attention mechanism.
A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We present a data stream algorithm for estimating the size of the maximum matching of a low arboricity graph. Recall that a graph has arboricity $α$ if its edges can be partitioned into at most $α$ forests and that a planar graph has arboricity $α=3$. Estimating the size of the maximum matching in such graphs has been a focus of recent data stream research. A surprising result on this problem was recently proved by Cormode et al. They designed an ingenious algorithm that returned a $(22.5α+6)(1+ε)$ approximation using a single pass over the edges of the graph (ordered arbitrarily) and $O(ε^{-2}α\cdot \log n \cdot \log_{1+ε} n)$ space. In this note, we improve the approximation factor to $(α+2)(1+ε)$ via a tighter analysis and show that, with a modification of their algorithm, the space required can be reduced to $O(ε^{-2} \log n)$.
Query-adaptive Image Retrieval by Deep Weighted Hashing
Venue: arXiv cs.CV 2017
Year: 2017

Hashing methods have attracted much attention for large scale image retrieval. Some deep hashing methods have achieved promising results by taking advantage of the strong representation power of deep networks recently. However, existing deep hashing methods treat all hash bits equally. On one hand, a large number of images share the same distance to a query image due to the discrete Hamming distance, which raises a critical issue of image retrieval where fine-grained rankings are very important. On the other hand, different hash bits actually contribute to the image retrieval differently, and treating them equally greatly affects the retrieval accuracy of image. To address the above two problems, we propose the query-adaptive deep weighted hashing (QaDWH) approach, which can perform fine-grained ranking for different queries by weighted Hamming distance. First, a novel deep hashing network is proposed to learn the hash codes and corresponding class-wise weights jointly, so that the learned weights can reflect the importance of different hash bits for different image classes. Second, a query-adaptive image retrieval method is proposed, which rapidly generates hash bit weights for different query images by fusing its semantic probability and the learned class-wise weights. Fine-grained image retrieval is then performed by the weighted Hamming distance, which can provide more accurate ranking than the traditional Hamming distance. Experiments on four widely used datasets show that the proposed approach outperforms eight state-of-the-art hashing methods.
Distributed Publish/Subscribe Query Processing on the Spatio-Textual Data Stream
Venue: arXiv cs.DB 2017
Year: 2017

Huge amount of data with both space and text information, e.g., geo-tagged tweets, is flooding on the Internet. Such spatio-textual data stream contains valuable information for millions of users with various interests on different keywords and locations. Publish/subscribe systems enable efficient and effective information distribution by allowing users to register continuous queries with both spatial and textual constraints. However, the explosive growth of data scale and user base has posed challenges to the existing centralized publish/subscribe systems for spatio-textual data streams. In this paper, we propose our distributed publish/subscribe system, called PS2Stream, which digests a massive spatio-textual data stream and directs the stream to target users with registered interests. Compared with existing systems, PS2Stream achieves a better workload distribution in terms of both minimizing the total amount of workload and balancing the load of workers. To achieve this, we propose a new workload distribution algorithm considering both space and text properties of the data. Additionally, PS2Stream supports dynamic load adjustments to adapt to the change of the workload, which makes PS2Stream adaptive. Extensive empirical evaluation, on commercial cloud computing platform with real data, validates the superiority of our system design and advantages of our techniques on system performance improvement.
Fixpoint Approximation of Strategic Abilities under Imperfect Information
Venue: arXiv cs.MA 2017
Year: 2017

Model checking of strategic ability under imperfect information is known to be hard. The complexity results range from NP-completeness to undecidability, depending on the precise setup of the problem. No less importantly, fixpoint equivalences do not generally hold for imperfect information strategies, which seriously hampers incremental synthesis of winning strategies. In this paper, we propose translations of ATLir formulae that provide lower and upper bounds for their truth values, and are cheaper to verify than the original specifications. That is, if the expression is verified as true then the corresponding formula of ATLir should also hold in the given model. We begin by showing where the straightforward approach does not work. Then, we propose how it can be modified to obtain guaranteed lower bounds. To this end, we alter the next-step operator in such a way that traversing one's indistinguishability relation is seen as atomic activity. Most interestingly, the lower approximation is provided by a fixpoint expression that uses a nonstandard variant of the next-step ability operator. We show the correctness of the translations, establish their computational complexity, and validate the approach by experiments with a scalable scenario of Bridge play.
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
Venue: arXiv cs.DS 2017
Year: 2017

We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with $n$ items using $O^*(2^{0.86n})$ time and polynomial space, where the $O^*(\cdot)$ notation suppresses factors polynomial in the input size. Both algorithms assume random read-only access to random bits. Modulo this mild assumption, this resolves a long-standing open problem in exact algorithms for NP-hard problems. These results can be extended to solve Binary Linear Programming on $n$ variables with few constraints in a similar running time. We also show that for any constant $k\geq 2$, random instances of $k$-Sum can be solved using $O(n^{k-0.5}polylog(n))$ time and $O(\log n)$ space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length $n$ with integers bounded by a polynomial in $n$ share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using $O(\log n)$ space significantly faster than the trivial $O(n^2)$ time algorithm if no value occurs too often in the same list.
Learning Representations by Stochastic Meta-Gradient Descent in Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Representations are fundamental to artificial intelligence. The performance of a learning system depends on the type of representation used for representing the data. Typically, these representations are hand-engineered using domain knowledge. More recently, the trend is to learn these representations through stochastic gradient descent in multi-layer neural networks, which is called backprop. Learning the representations directly from the incoming data stream reduces the human labour involved in designing a learning system. More importantly, this allows in scaling of a learning system for difficult tasks. In this paper, we introduce a new incremental learning algorithm called crossprop, which learns incoming weights of hidden units based on the meta-gradient descent approach, that was previously introduced by Sutton (1992) and Schraudolph (1999) for learning step-sizes. The final update equation introduces an additional memory parameter for each of these weights and generalizes the backprop update equation. From our experiments, we show that crossprop learns and reuses its feature representation while tackling new and unseen tasks whereas backprop relearns a new feature representation.