OpenRaiser/Intern-Atlas huggingface dataset:
Network Morphism
Venue: arXiv cs.LG 2016
Year: 2016

We present in this paper a systematic study on how to morph a well-trained neural network to a new one so that its network function can be completely preserved. We define this as \emph{network morphism} in this research. After morphing a parent network, the child network is expected to inherit the knowledge from its parent network and also has the potential to continue growing into a more powerful one with much shortened training time. The first requirement for this network morphism is its ability to handle diverse morphing types of networks, including changes of depth, width, kernel size, and even subnet. To meet this requirement, we first introduce the network morphism equations, and then develop novel morphing algorithms for all these morphing types for both classic and convolutional neural networks. The second requirement for this network morphism is its ability to deal with non-linearity in a network. We propose a family of parametric-activation functions to facilitate the morphing of any continuous non-linear activation neurons. Experimental results on benchmark datasets and typical neural networks demonstrate the effectiveness of the proposed network morphism scheme.
Coverage gain and Device-to-Device user Density: Stochastic Geometry Modeling and Analysis
Venue: arXiv cs.IT 2016
Year: 2016

Device-to-device (D2D) communication has huge potential for capacity and coverage enhancements for next generation cellular networks. The number of potential nodes for D2D communication is an important parameter that directly impacts the system capacity. In this paper, we derive analytic expression for average coverage probability of cellular user and corresponding number of potential D2D users. In this context, mature framework of stochastic geometry and Poisson point process has been used. The retention probability has been incorporated in Laplace functional to capture reduced path-loss and shortest distance criterion based D2D pairing. The numerical results show a close match between analytic expression and simulation setup.
New Algorithms for Heavy Hitters in Data Streams
Venue: arXiv cs.DS 2016
Year: 2016

An old and fundamental problem in databases and data streams is that of finding the heavy hitters, also known as the top-$k$, most popular items, frequent items, elephants, or iceberg queries. There are several variants of this problem, which quantify what it means for an item to be frequent, including what are known as the $\ell_1$-heavy hitters and $\ell_2$-heavy hitters. There are a number of algorithmic solutions for these problems, starting with the work of Misra and Gries, as well as the CountMin and CountSketch data structures, among others. In this survey paper, accompanying an ICDT invited talk, we cover several recent results developed in this area, which improve upon the classical solutions to these problems. In particular, with coauthors we develop new algorithms for finding $\ell_1$-heavy hitters and $\ell_2$-heavy hitters, with significantly less memory required than what was known, and which are optimal in a number of parameter regimes.
An Argument-based Creative Assistant for Harmonic Blending
Venue: arXiv cs.SD 2016
Year: 2016

Conceptual blending is a powerful tool for computational creativity where, for example, the properties of two harmonic spaces may be combined in a consistent manner to produce a novel harmonic space. However, deciding about the importance of property features in the input spaces and evaluating the results of conceptual blending is a nontrivial task. In the specific case of musical harmony, defining the salient features of chord transitions and evaluating invented harmonic spaces requires deep musicological background knowledge. In this paper, we propose a creative tool that helps musicologists to evaluate and to enhance harmonic innovation. This tool allows a music expert to specify arguments over given transition properties. These arguments are then considered by the system when defining combinations of features in an idiom-blending process. A music expert can assess whether the new harmonic idiom makes musicological sense and re-adjust the arguments (selection of features) to explore alternative blends that can potentially produce better harmonic spaces. We conclude with a discussion of future work that would further automate the harmonisation process.
Identifying and Improving Dataset References in Social Sciences Full Texts
Venue: arXiv cs.DL 2016
Year: 2016

Scientific full text papers are usually stored in separate places than their underlying research datasets. Authors typically make references to datasets by mentioning them for example by using their titles and the year of publication. However, in most cases explicit links that would provide readers with direct access to referenced datasets are missing. Manually detecting references to datasets in papers is time consuming and requires an expert in the domain of the paper. In order to make explicit all links to datasets in papers that have been published already, we suggest and evaluate a semi-automatic approach for finding references to datasets in social sciences papers. Our approach does not need a corpus of papers (no cold start problem) and it performs well on a small test corpus (gold standard). Our approach achieved an F-measure of 0.84 for identifying references in full texts and an F-measure of 0.83 for finding correct matches of detected references in the da|ra dataset registry.
Generalised rely-guarantee concurrency: An algebraic foundation
Venue: arXiv cs.LO 2016
Year: 2016

The rely-guarantee technique allows one to reason compositionally about concurrent programs. To handle interference the technique makes use of rely and guarantee conditions, both of which are binary relations on states. A rely condition is an assumption that the environment performs only atomic steps satisfying the rely relation and a guarantee is a commitment that every atomic step the program makes satisfies the guarantee relation. In order to investigate rely-guarantee reasoning more generally, in this paper we allow interference to be represented by a process rather than a relation and hence derive more general rely-guarantee laws. The paper makes use of a weak conjunction operator between processes, which generalises a guarantee relation to a guarantee process, and introduces a rely quotient operator, which generalises a rely relation to a process. The paper focuses on the algebraic properties of the general rely-guarantee theory. The Jones-style rely-guarantee theory can be interpreted as a model of the general algebraic theory and hence the general laws presented here hold for that theory.
Low-Complexity Iterative Sinusoidal Parameter Estimation
Venue: arXiv cs.SD 2016
Year: 2016

Sinusoidal parameter estimation is a computationally-intensive task, which can pose problems for real-time implementations. In this paper, we propose a low-complexity iterative method for estimating sinusoidal parameters that is based on the linearisation of the model around an initial frequency estimate. We show that for N sinusoids in a frame of length L, the proposed method has a complexity of O(LN), which is significantly less than the matching pursuits method. Furthermore, the proposed method is shown to be more accurate than the matching pursuits and time frequency reassignment methods in our experiments.
Proximal groupoid patterns In digital images
Venue: arXiv cs.CV 2016
Year: 2016

The focus of this article is on the detection and classification of patterns based on groupoids. The approach hinges on descriptive proximity of points in a set based on the neighborliness property. This approach lends support to image analysis and understanding and in studying nearness of image segments. A practical application of the approach is in terms of the analysis of natural images for pattern identification and classification.
Improved Noise Weighting in CELP Coding of Speech - Applying the Vorbis Psychoacoustic Model To Speex
Venue: arXiv cs.SD 2016
Year: 2016

One key aspect of the CELP algorithm is that it shapes the coding noise using a simple, yet effective, weighting filter. In this paper, we improve the noise shaping of CELP using a more modern psychoacoustic model. This has the significant advantage of improving the quality of an existing codec without the need to change the bit-stream. More specifically, we improve the Speex CELP codec by using the psychoacoustic model used in the Vorbis audio codec. The results show a significant increase in quality, especially at high bit-rates, where the improvement is equivalent to a 20% reduction in bit-rate. The technique itself is not specific to Speex and could be applied to other CELP codecs.
Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of personalized advertisement recommendation (PAR), which consist of a user visiting a system (website) and the system displaying one of $K$ ads to the user. The system uses an internal ad recommendation policy to map the user's profile (context) to one of the ads. The user either clicks or ignores the ad and correspondingly, the system updates its recommendation policy. PAR problem is usually tackled by scalable \emph{contextual bandit} algorithms, where the policies are generally based on classifiers. A practical problem in PAR is extreme click sparsity, due to very few users actually clicking on ads. We systematically study the drawback of using contextual bandit algorithms based on classifier-based policies, in face of extreme click sparsity. We then suggest an alternate policy, based on rankers, learnt by optimizing the Area Under the Curve (AUC) ranking loss, which can significantly alleviate the problem of click sparsity. We conduct extensive experiments on public datasets, as well as three industry proprietary datasets, to illustrate the improvement in click-through-rate (CTR) obtained by using the ranker-based policy over classifier-based policies.
Confidence-Constrained Maximum Entropy Framework for Learning from Multi-Instance Data
Venue: arXiv cs.LG 2016
Year: 2016

Multi-instance data, in which each object (bag) contains a collection of instances, are widespread in machine learning, computer vision, bioinformatics, signal processing, and social sciences. We present a maximum entropy (ME) framework for learning from multi-instance data. In this approach each bag is represented as a distribution using the principle of ME. We introduce the concept of confidence-constrained ME (CME) to simultaneously learn the structure of distribution space and infer each distribution. The shared structure underlying each density is used to learn from instances inside each bag. The proposed CME is free of tuning parameters. We devise a fast optimization algorithm capable of handling large scale multi-instance data. In the experimental section, we evaluate the performance of the proposed approach in terms of exact rank recovery in the space of distributions and compare it with the regularized ME approach. Moreover, we compare the performance of CME with Multi-Instance Learning (MIL) state-of-the-art algorithms and show a comparable performance in terms of accuracy with reduced computational complexity.
Optimal Geographic Caching in Finite Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Cache-enabled device-to-device (D2D) networks turn memory of the devices at the network edge, such as smart phones and tablets, into bandwidth by enabling asynchronous content sharing directly between proximate devices. Limited storage capacity of the mobile devices necessitates the determination of optimal set of contents to be cached on each device. In order to study the problem of optimal cache placement, we model the locations of devices in a finite region (e.g., coffee shop, sports bar, library) as a uniform binomial point process (BPP). For this setup, we first develop a generic framework to analyze the coverage probability of the target receiver (target-Rx) when the requested content is available at the $k^{th}$ closest device to it. Using this coverage probability result, we evaluate optimal caching probability of the popular content to maximize the total hit probability. Our analysis concretely demonstrates that optimal caching probability strongly depends on the number of simultaneously active devices in the network.
Stochastic Collection and Replenishment (SCAR) Optimisation for Persistent Autonomy
Venue: arXiv cs.RO 2016
Year: 2016

Robots have a finite supply of resources such as fuel, battery charge, and storage space. The aim of the Stochastic Collection and Replenishment (SCAR) scenario is to use dedicated agents to refuel, recharge, or otherwise replenish robots in the field to facilitate persistent autonomy. This paper explores the optimisation of the SCAR scenario with a single replenishment agent, using several different objective functions. The problem is framed as a combinatorial optimisation problem, and A* is used to find the optimal schedule. Through a computational study, a ratio objective function is shown to have superior performance compared with a total weighted tardiness objective function, with a greater performance advantage present when using shorter schedule lengths. The importance of incorporating uncertainty in the objective function used in the optimisation process is also highlighted, in particular for scenarios in which the replenishment agent is under- or fully-utilised.
Graph Theoretic Investigations on Inefficiencies in Network Models
Venue: arXiv cs.DM 2016
Year: 2016

We consider network models where information items flow %are sent from a source to a sink node. We start with a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption. We characterize graph topologies ensuring that every saturating flow under every energy-to-node assignment is maximum and provide a polynomial-time algorithm for checking this property. We then consider the standard flow networks with capacity on edges, where again efficiency is related to maximality of saturating flows, and a traffic model for selfish routing, where efficiency is related to latency at a Wardrop equilibrium. Finally, we show that all these forms of inefficiency yield different classes of graphs (apart from the acyclic case, where the last two forms generate the same class). Interestingly, in all cases inefficient graphs can be made efficient by removing edges; this resembles a well-known phenomenon, called Braess's paradox.
A Desired PAR-Achieving Precoder Design for Multi-User MIMO OFDM based on Concentration of Measure
Venue: arXiv cs.IT 2016
Year: 2016

For multi-user multiple-input and multiple-output (MIMO) wireless communications in orthogonal frequency di- vision multiplexing systems, we propose a MIMO precoding scheme providing a desired peak-to-average power ratio (PAR) at the minimum cost that is defined as received SNR degradation. By taking advantage of the concentration of measure, we formulate a convex problem with constraint on the desired PAR. Consequently, the proposed scheme almost exactly achieves the desired PAR on average, and asymptotically attains the desired PAR at the 0.001 point of its complementary cumulative distribution function, as the number of subcarriers increases.
How to make RSA and some other encryptions probabilistic
Venue: arXiv cs.CR 2016
Year: 2016

A new scheme of probabilistic subgroup-related encryption is introduced. Some applications of this scheme based on the RSA, Diffie-Hellman and ElGamal encryption algorithms are described. Security assumptions and main advantages of this scheme are discussed. We outline that this scheme is potentially semantically secure under reasonable cryptographic assumptions.
Modeling Information Diffusion in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

One major feature of social networks (e.g., massive online social networks) is the dissemination of information, such as news, rumors and opinions. Information can be propagated via natural connections in written, oral or electronic forms. The physics of information diffusion has been changed with the mainstream adoption of the Internet and Web. Until a few years ago, the major barrier for someone who wanted a piece of information to spread through a community was the cost of the technical infrastructure required to reach a large number of people. Today, with widespread access to the Internet, this bottleneck has largely been removed. Information diffusion has been one of the focuses in social network research area, due to its importance in social interactions and everyday life. More recently, during the last twenty to thirty years, there has been interest and attention not just in observing information and innovation flow, but also in influencing and creating them. Modeling information diffusion in networks enables us to reason about its spread.
Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection
Venue: arXiv cs.LG 2016
Year: 2016

We describe a learning-based approach to hand-eye coordination for robotic grasping from monocular images. To learn hand-eye coordination for grasping, we trained a large convolutional neural network to predict the probability that task-space motion of the gripper will result in successful grasps, using only monocular camera images and independently of camera calibration or the current robot pose. This requires the network to observe the spatial relationship between the gripper and objects in the scene, thus learning hand-eye coordination. We then use this network to servo the gripper in real time to achieve successful grasps. To train our network, we collected over 800,000 grasp attempts over the course of two months, using between 6 and 14 robotic manipulators at any given time, with differences in camera placement and hardware. Our experimental evaluation demonstrates that our method achieves effective real-time control, can successfully grasp novel objects, and corrects mistakes by continuous servoing.
Drift Robust Non-rigid Optical Flow Enhancement for Long Sequences
Venue: arXiv cs.CV 2016
Year: 2016

It is hard to densely track a nonrigid object in long term, which is a fundamental research issue in the computer vision community. This task often relies on estimating pairwise correspondences between images over time where the error is accumulated and leads to a drift issue. In this paper, we introduce a novel optimization framework with an Anchor Patch constraint. It is supposed to significantly reduce overall errors given long sequences containing non-rigidly deformable objects. Our framework can be applied to any dense tracking algorithm, e.g. optical flow. We demonstrate the success of our approach by showing significant error reduction on 6 popular optical flow algorithms applied to a range of real-world nonrigid benchmarks. We also provide quantitative analysis of our approach given synthetic occlusions and image noise.
Towards Automated Android App Collusion Detection
Venue: arXiv cs.SE 2016
Year: 2016

Android OS supports multiple communication methods between apps. This opens the possibility to carry out threats in a collaborative fashion, c.f. the Soundcomber example from 2011. In this paper we provide a concise definition of collusion and report on a number of automated detection approaches, developed in co-operation with Intel Security.
Terminal Embeddings
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we study {\em terminal embeddings}, in which one is given a finite metric $(X,d_X)$ (or a graph $G=(V,E)$) and a subset $K \subseteq X$ of its points are designated as {\em terminals}. The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve $\approx|K|\cdot |X|$ pairs, the distortion depends only on $|K|$, rather than on $|X|$. We also strengthen this notion, and consider embeddings that approximately preserve the distances between {\em all} pairs, but provide improved distortion for pairs containing a terminal. Surprisingly, we show that such embeddings exist in many settings, and have optimal distortion bounds both with respect to $X \times X$ and with respect to $K \times X$. Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [ALN08] devised an $\tilde{O}(\sqrt{\log r})$-approximation algorithm for sparsest-cut instances with $r$ demands. Building on their framework, we provide an $\tilde{O}(\sqrt{\log |K|})$-approximation for sparsest-cut instances in which each demand is incident on one of the vertices of $K$ (aka, terminals). Since $|K| \le r$, our bound generalizes that of [ALN08].
Constant Approximation for Capacitated $k$-Median with $(1 + ε)$-Capacity Violation
Venue: arXiv cs.DS 2016
Year: 2016

We study the Capacitated k-Median problem for which existing constant-factor approximation algorithms are all pseudo-approximations that violate either the capacities or the upper bound k on the number of open facilities. Using the natural LP relaxation for the problem, one can only hope to get the violation factor down to 2. Li [SODA'16] introduced a novel LP to go beyond the limit of 2 and gave a constant-factor approximation algorithm that opens $(1 + ε)k$ facilities. We use the configuration LP of Li [SODA'16] to give a constant-factor approximation for the Capacitated k-Median problem in a seemingly harder configuration: we violate only the capacities by $1 + ε$. This result settles the problem as far as pseudo-approximation algorithms are concerned.
Enhanced Robot Audition Based on Microphone Array Source Separation with Post-Filter
Venue: arXiv cs.RO 2016
Year: 2016

We propose a system that gives a mobile robot the ability to separate simultaneous sound sources. A microphone array is used along with a real-time dedicated implementation of Geometric Source Separation and a post-filter that gives us a further reduction of interferences from other sources. We present results and comparisons for separation of multiple non-stationary speech sources combined with noise sources. The main advantage of our approach for mobile robots resides in the fact that both the frequency-domain Geometric Source Separation algorithm and the post-filter are able to adapt rapidly to new sources and non-stationarity. Separation results are presented for three simultaneous interfering speakers in the presence of noise. A reduction of log spectral distortion (LSD) and increase of signal-to-noise ratio (SNR) of approximately 10 dB and 14 dB are observed.
Interactive Browsing and Navigation in Relational Databases
Venue: arXiv cs.DB 2016
Year: 2016

Although researchers have devoted considerable attention to helping database users formulate queries, many users still find it challenging to specify queries that involve joining tables. To help users construct join queries for exploring relational databases, we propose ETable, a novel presentation data model that provides users with a presentation-level interactive view. This view compactly presents one-to-many and many-to-many relationships within a single enriched table by allowing a cell to contain a set of entity references. Users can directly interact with this enriched table to incrementally construct complex queries and navigate databases on a conceptual entity-relationship level. In a user study, participants performed a range of database querying tasks faster with ETable than with a commercial graphical query builder. Subjective feedback about ETable was also positive. All participants found that ETable was easier to learn and helpful for exploring databases.