OpenRaiser/Intern-Atlas huggingface dataset:
Discriminative Transformation Learning for Fuzzy Sparse Subspace Clustering
Venue: arXiv cs.CV 2017
Year: 2017

This paper develops a novel iterative framework for subspace clustering in a learned discriminative feature domain. This framework consists of two modules of fuzzy sparse subspace clustering and discriminative transformation learning. In the first module, fuzzy latent labels containing discriminative information and latent representations capturing the subspace structure will be simultaneously evaluated in a feature domain. Then the linear transforming operator with respect to the feature domain will be successively updated in the second module with the advantages of more discrimination, subspace structure preservation and robustness to outliers. These two modules will be alternatively carried out and both theoretical analysis and empirical evaluations will demonstrate its effectiveness and superiorities. In particular, experimental results on three benchmark databases for subspace clustering clearly illustrate that the proposed framework can achieve significant improvements than other state-of-the-art approaches in terms of clustering accuracy.
Green Base Station Placement for Microwave Backhaul Links
Venue: arXiv cs.IT 2017
Year: 2017

Wireless mobile backhaul networks have been proposed as a substitute in cases in which wired alternatives are not available due to economical or geographical reasons. In this work, we study the location problem of base stations in a given region where mobile terminals are distributed according to a certain probability density function and the base stations communicate through microwave backhaul links. Using results of optimal transport theory, we provide the optimal asymptotic distribution of base stations in the considered setting by minimizing the total power over the whole network.
Differentially Private Identity and Closeness Testing of Discrete Distributions
Venue: arXiv cs.LG 2017
Year: 2017

We investigate the problems of identity and closeness testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing Differential Privacy to the individuals of the population. We describe an approach that yields sample-efficient differentially private testers for these problems. Our theoretical results show that there exist private identity and closeness testers that are nearly as sample-efficient as their non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors with sample size sublinear in the domain size of the underlying distributions.
On the State of the Art of Evaluation in Neural Language Models
Venue: arXiv cs.CL 2017
Year: 2017

Ongoing innovations in recurrent neural network architectures have provided a steady influx of apparently state-of-the-art results on language modelling benchmarks. However, these have been evaluated using differing code bases and limited computational resources, which represent uncontrolled sources of experimental variation. We reevaluate several popular architectures and regularisation methods with large-scale automatic black-box hyperparameter tuning and arrive at the somewhat surprising conclusion that standard LSTM architectures, when properly regularised, outperform more recent models. We establish a new state of the art on the Penn Treebank and Wikitext-2 corpora, as well as strong baselines on the Hutter Prize dataset.
On Optimizing Distributed Tucker Decomposition for Dense Tensors
Venue: arXiv cs.DC 2017
Year: 2017

The Tucker decomposition expresses a given tensor as the product of a small core tensor and a set of factor matrices. Apart from providing data compression, the construction is useful in performing analysis such as principal component analysis (PCA)and finds applications in diverse domains such as signal processing, computer vision and text analytics. Our objective is to develop an efficient distributed implementation for the case of dense tensors. The implementation is based on the HOOI (Higher Order Orthogonal Iterator) procedure, wherein the tensor-times-matrix product forms the core routine. Prior work have proposed heuristics for reducing the computational load and communication volume incurred by the routine. We study the two metrics in a formal and systematic manner, and design strategies that are optimal under the two fundamental metrics. Our experimental evaluation on a large benchmark of tensors shows that the optimal strategies provide significant reduction in load and volume compared to prior heuristics, and provide up to 7x speed-up in the overall running time.
The Compressed Overlap Index
Venue: arXiv cs.DS 2017
Year: 2017

For analysing text algorithms, for computing superstrings, or for testing random number generators, one needs to compute all overlaps between any pairs of words in a given set. The positions of overlaps of a word onto itself, or of two words, are needed to compute the absence probability of a word in a random text, or the numbers of common words shared by two random texts. In all these contexts, one needs to compute or to query overlaps between pairs of words in a given set. For this sake, we designed COvI, a compressed overlap index that supports multiple queries on overlaps: like computing the correlation of two words, or listing pairs of words whose longest overlap is maximal among all possible pairs. COvI stores overlaps in a hierarchical and non-redundant manner. We propose an implementation that can handle datasets of millions of words and still answer queries efficiently. Comparison with a baseline solution - called FullAC - relying on the Aho-Corasick automaton shows that COvI provides significant advantages. For similar construction times, COvI requires half the memory FullAC, and still solves complex queries much faster.
Learning Powers of Poisson Binomial Distributions
Venue: arXiv cs.DS 2017
Year: 2017

We introduce the problem of simultaneously learning all powers of a Poisson Binomial Distribution (PBD). A PBD of order $n$ is the distribution of a sum of $n$ mutually independent Bernoulli random variables $X_i$, where $\mathbb{E}[X_i] = p_i$. The $k$'th power of this distribution, for $k$ in a range $[m]$, is the distribution of $P_k = \sum_{i=1}^n X_i^{(k)}$, where each Bernoulli random variable $X_i^{(k)}$ has $\mathbb{E}[X_i^{(k)}] = (p_i)^k$. The learning algorithm can query any power $P_k$ several times and succeeds in learning all powers in the range, if with probability at least $1- δ$: given any $k \in [m]$, it returns a probability distribution $Q_k$ with total variation distance from $P_k$ at most $ε$. We provide almost matching lower and upper bounds on query complexity for this problem. We first show a lower bound on the query complexity on PBD powers instances with many distinct parameters $p_i$ which are separated, and we almost match this lower bound by examining the query complexity of simultaneously learning all the powers of a special class of PBD's resembling the PBD's of our lower bound. We study the fundamental setting of a Binomial distribution, and provide an optimal algorithm which uses $O(1/ε^2)$ samples. Diakonikolas, Kane and Stewart [COLT'16] showed a lower bound of $Ω(2^{1/ε})$ samples to learn the $p_i$'s within error $ε$. The question whether sampling from powers of PBDs can reduce this sampling complexity, has a negative answer since we show that the exponential number of samples is inevitable. Having sampling access to the powers of a PBD we then give a nearly optimal algorithm that learns its $p_i$'s. To prove our two last lower bounds we extend the classical minimax risk definition from statistics to estimating functions of sequences of distributions.
Fixpoint Semantics and Optimization of Recursive Datalog Programs with Aggregates
Venue: arXiv cs.DB 2017
Year: 2017

A very desirable Datalog extension investigated by many researchers in the last thirty years consists in allowing the use of the basic SQL aggregates min, max, count and sum in recursive rules. In this paper, we propose a simple comprehensive solution that extends the declarative least-fixpoint semantics of Horn Clauses, along with the optimization techniques used in the bottom-up implementation approach adopted by many Datalog systems. We start by identifying a large class of programs of great practical interest in which the use of min or max in recursive rules does not compromise the declarative fixpoint semantics of the programs using those rules. Then, we revisit the monotonic versions of count and sum aggregates proposed in (Mazuran et al. 2013b) and named, respectively, mcount and msum. Since mcount, and also msum on positive numbers, are monotonic in the lattice of set-containment, they preserve the fixpoint semantics of Horn Clauses. However, in many applications of practical interest, their use can lead to inefficiencies, that can be eliminated by combining them with max, whereby mcount and msum become the standard count and sum. Therefore, the semantics and optimization techniques of Datalog are extended to recursive programs with min, max, count and sum, making possible the advanced applications of superior performance and scalability demonstrated by BigDatalog (Shkapsky et al. 2016) and Datalog-MC (Yang et al. 2017). This paper is under consideration for acceptance in TPLP.
Exploiting Convolutional Representations for Multiscale Human Settlement Detection
Venue: arXiv cs.CV 2017
Year: 2017

We test this premise and explore representation spaces from a single deep convolutional network and their visualization to argue for a novel unified feature extraction framework. The objective is to utilize and re-purpose trained feature extractors without the need for network retraining on three remote sensing tasks i.e. superpixel mapping, pixel-level segmentation and semantic based image visualization. By leveraging the same convolutional feature extractors and viewing them as visual information extractors that encode different image representation spaces, we demonstrate a preliminary inductive transfer learning potential on multiscale experiments that incorporate edge-level details up to semantic-level information.
Energy-Efficient Data Transfer Algorithms for HTTP-Based Services
Venue: arXiv cs.NI 2017
Year: 2017

According to recent statistics, more than 1 zettabytes of data is moved over the Internet annually, which consumes several terawatt hours of electricity, and costs billions of US dollars to the world economy. HTTP protocol is used in the majority of these data transfers, accounting for 70% of the global Internet traffic. We claim that HTTP transfers, and the services based on HTTP, can become more energy efficient without any performance degradation by application-level tuning of certain protocol parameters. In this paper, we analyze several application-level parameters that affect the throughput and energy consumption in HTTP data transfers, such as the level of parallelism, concurrency, and pipelining. We introduce SLA-based algorithms which can decide the best combination of these parameters based on user-defined energy efficiency and performance criteria. Our experimental results show that up to 80% energy savings can be achieved at the client and server hosts during HTTP data transfers and the end-to-end data throughput can be increased at the same time.
AirCode: Unobtrusive Physical Tags for Digital Fabrication
Venue: arXiv cs.HC 2017
Year: 2017

We present AirCode, a technique that allows the user to tag physically fabricated objects with given information. An AirCode tag consists of a group of carefully designed air pockets placed beneath the object surface. These air pockets are easily produced during the fabrication process of the object, without any additional material or postprocessing. Meanwhile, the air pockets affect only the scattering light transport under the surface, and thus are hard to notice to our naked eyes. But, by using a computational imaging method, the tags become detectable. We present a tool that automates the design of air pockets for the user to encode information. AirCode system also allows the user to retrieve the information from captured images via a robust decoding algorithm. We demonstrate our tagging technique with applications for metadata embedding, robotic grasping, as well as conveying object affordances.
Heroes and Zeroes: Predicting the Impact of New Video Games on Twitch.tv
Venue: arXiv cs.SI 2017
Year: 2017

Video games and the playing thereof have been a fixture of American culture since their introduction in the arcades of the 1980s. However, it was not until the recent proliferation of broadband connections robust and fast enough to handle live video streaming that players of video games have transitioned from a content consumer role to a content producer role. Simultaneously, the rise of social media has revealed how interpersonal connections drive user engagement and interest. In this work, we discuss the recent proliferation of video game streaming, particularly on Twitch.tv, analyze trends and patterns in video game viewing, and develop predictive models for determining if a new game will have substantial impact on the streaming ecosystem.
Program Completionin the Input Language of GRINGO
Venue: arXiv cs.LO 2017
Year: 2017

We argue that turning a logic program into a set of completed definitions can be sometimes thought of as the "reverse engineering" process of generating a set of conditions that could serve as a specification for it. Accordingly, it may be useful to define completion for a large class of ASP programs and to automate the process of generating and simplifying completion formulas. Examining the output produced by this kind of software may help programmers to see more clearly what their program does, and to what degree its behavior conforms with their expectations. As a step toward this goal, we propose here a definition of program completion for a large class of programs in the input language of the ASP grounder GRINGO, and study its properties. This note is under consideration for publication in Theory and Practice of Logic Programming.
MIT SuperCloud Portal Workspace: Enabling HPC Web Application Deployment
Venue: arXiv cs.DC 2017
Year: 2017

The MIT SuperCloud Portal Workspace enables the secure exposure of web services running on high performance computing (HPC) systems. The portal allows users to run any web application as an HPC job and access it from their workstation while providing authentication, encryption, and access control at the system level to prevent unintended access. This capability permits users to seamlessly utilize existing and emerging tools that present their user interface as a website on an HPC system creating a portal workspace. Performance measurements indicate that the MIT SuperCloud Portal Workspace incurs marginal overhead when compared to a direct connection of the same service.
Improving the capacity of molecular communication using enzymatic reaction cycles
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the capacity of a diffusion-based molecular communication link assuming the receiver uses chemical reactions. The key contribution is we show that enzymatic reaction cycles, which is a class of chemical reactions commonly found in cells consisting of a forward and a backward enzymatic reaction, can improve the capacity of the communication link. The technical difficulty in analysing enzymatic reaction cycles is that their reaction rates are nonlinear. We deal with this by assuming that the amount of certain chemicals in the enzymatic reaction cycle is large. In order to simplify the problem further, we use singular perturbation to study a particular operating regime of the enzymatic reaction cycles. This allows us to derive a closed-form expression of the channel gain. This expression suggests that we can improve the channel gain by increasing the total amount of substrate in the enzymatic reaction cycle. By using numerical calculations, we show that the effect of the enzymatic reaction cycle is to increase the channel gain and to reduce the noise, which results in a better signalto- noise ratio and in turn a higher communication capacity. Furthermore, we show that we can increase the capacity by increasing the total amount of substrate in the enzymatic reaction cycle.
Real-Time Impulse Noise Removal from MR Images for Radiosurgery Applications
Venue: arXiv cs.AR 2017
Year: 2017

In the recent years image processing techniques are used as a tool to improve detection and diagnostic capabilities in the medical applications. Medical applications have been so much affected by these techniques which some of them are embedded in medical instruments such as MRI, CT and other medical devices. Among these techniques, medical image enhancement algorithms play an essential role in removal of the noise which can be produced by medical instruments and during image transfer. It has been proved that impulse noise is a major type of noise, which is produced during medical operations, such as MRI, CT, and angiography, by their image capturing devices. An embeddable hardware module which is able to denoise medical images before and during surgical operations could be very helpful. In this paper an accurate algorithm is proposed for real-time removal of impulse noise in medical images. All image blocks are divided into three categories of edge, smooth, and disordered areas. A different reconstruction method is applied to each category of blocks for the purpose of noise removal. The proposed method is tested on MR images. Simulation results show acceptable denoising accuracy for various levels of noise. Also an FPAG implementation of our denoising algorithm shows acceptable hardware resource utilization. Hence, the algorithm is suitable for embedding in medical hardware instruments such as radiosurgery devices.
Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
Venue: arXiv cs.DS 2017
Year: 2017

A labeling scheme for nearest common ancestors assigns a distinct binary string, called the label, to every node of a tree, so that given the labels of two nodes (and no further information about the topology of the tree) we can compute the label of their nearest common ancestor. The goal is to make the labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor. Comput. Syst. 37(3):441-456 2004] showed that $O(\log n)$-bit labels are enough. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this to only $2.772\log n$, and provided a lower bound of $1.008\log n$. We connect designing a labeling scheme for nearest common ancestors to the existence of a tree, called a minor-universal tree, that contains every tree on $n$ nodes as a topological minor. Even though it is not clear if a labeling scheme must be based on such a notion, we argue that the existing schemes can be reformulated as such, and it allows us to obtain clean and good bounds on the length of the labels. As the main upper bound, we show that $2.318\log n$-bit labels are enough. Surprisingly, the notion of a minor-universal tree for binary trees on $n$ nodes has been already used in a different context by Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3):416-435, 1999] introduced a closely related notion of a universal tree. On the lower bound side, we show that the size of any minor-universal tree for trees on $n$ nodes is $Ω(n^{2.174})$. This highlights a natural limitation for all approaches based on such trees. Our lower bound technique also implies that the size of any universal tree in the sense of Young et al. is $Ω(n^{2.185})$, thus dramatically improves their lower bound of $Ω(n\log n)$. We complement the existential results with a generic transformation that decreases the query time to constant in any scheme based on a minor-universal tree.
Modeling the Intra-class Variability for Liver Lesion Detection using a Multi-class Patch-based CNN
Venue: arXiv cs.CV 2017
Year: 2017

Automatic detection of liver lesions in CT images poses a great challenge for researchers. In this work we present a deep learning approach that models explicitly the variability within the non-lesion class, based on prior knowledge of the data, to support an automated lesion detection system. A multi-class convolutional neural network (CNN) is proposed to categorize input image patches into sub-categories of boundary and interior patches, the decisions of which are fused to reach a binary lesion vs non-lesion decision. For validation of our system, we use CT images of 132 livers and 498 lesions. Our approach shows highly improved detection results that outperform the state-of-the-art fully convolutional network. Automated computerized tools, as shown in this work, have the potential in the future to support the radiologists towards improved detection.
Working Locally Thinking Globally: Theoretical Guarantees for Convolutional Sparse Coding
Venue: arXiv cs.IT 2017
Year: 2017

The celebrated sparse representation model has led to remarkable results in various signal processing tasks in the last decade. However, despite its initial purpose of serving as a global prior for entire signals, it has been commonly used for modeling low dimensional patches due to the computational constraints it entails when deployed with learned dictionaries. A way around this problem has been recently proposed, adopting a convolutional sparse representation model. This approach assumes that the global dictionary is a concatenation of banded Circulant matrices. While several works have presented algorithmic solutions to the global pursuit problem under this new model, very few truly-effective guarantees are known for the success of such methods. In this work, we address the theoretical aspects of the convolutional sparse model providing the first meaningful answers to questions of uniqueness of solutions and success of pursuit algorithms, both greedy and convex relaxations, in ideal and noisy regimes. To this end, we generalize mathematical quantities, such as the $\ell_0$ norm, mutual coherence, Spark and RIP to their counterparts in the convolutional setting, intrinsically capturing local measures of the global model. On the algorithmic side, we demonstrate how to solve the global pursuit problem by using simple local processing, thus offering a first of its kind bridge between global modeling of signals and their patch-based local treatment.
Object-Extent Pooling for Weakly Supervised Single-Shot Localization
Venue: arXiv cs.CV 2017
Year: 2017

In the face of scarcity in detailed training annotations, the ability to perform object localization tasks in real-time with weak-supervision is very valuable. However, the computational cost of generating and evaluating region proposals is heavy. We adapt the concept of Class Activation Maps (CAM) into the very first weakly-supervised 'single-shot' detector that does not require the use of region proposals. To facilitate this, we propose a novel global pooling technique called Spatial Pyramid Averaged Max (SPAM) pooling for training this CAM-based network for object extent localisation with only weak image-level supervision. We show this global pooling layer possesses a near ideal flow of gradients for extent localization, that offers a good trade-off between the extremes of max and average pooling. Our approach only requires a single network pass and uses a fast-backprojection technique, completely omitting any region proposal steps. To the best of our knowledge, this is the first approach to do so. Due to this, we are able to perform inference in real-time at 35fps, which is an order of magnitude faster than all previous weakly supervised object localization frameworks.