OpenRaiser/Intern-Atlas huggingface dataset:
Practical Data Compression for Modern Memory Hierarchies
Venue: arXiv cs.AR 2016
Year: 2016

In this thesis, we describe a new, practical approach to integrating hardware-based data compression within the memory hierarchy, including on-chip caches, main memory, and both on-chip and off-chip interconnects. This new approach is fast, simple, and effective in saving storage space. A key insight in our approach is that access time (including decompression latency) is critical in modern memory hierarchies. By combining inexpensive hardware support with modest OS support, our holistic approach to compression achieves substantial improvements in performance and energy efficiency across the memory hierarchy. Using this new approach, we make several major contributions in this thesis. First, we propose a new compression algorithm, Base-Delta-Immediate Compression (BDI), that achieves high compression ratio with very low compression/decompression latency. BDI exploits the existing low dynamic range of values present in many cache lines to compress them to smaller sizes using Base+Delta encoding. Second, we observe that the compressed size of a cache block can be indicative of its reuse. We use this observation to develop a new cache insertion policy for compressed caches, the Size-based Insertion Policy (SIP), which uses the size of a compressed block as one of the metrics to predict its potential future reuse. Third, we propose a new main memory compression framework, Linearly Compressed Pages (LCP), that significantly reduces the complexity and power cost of supporting main memory compression. We demonstrate that any compression algorithm can be adapted to fit the requirements of LCP, and that LCP can be efficiently integrated with the existing cache compression designs, avoiding extra compression/decompression.
Quantitative recovery conditions for tree-based compressed sensing
Venue: arXiv cs.IT 2016
Year: 2016

As shown in [Blumensath and Davies 2009, Baraniuk et al. 2010], signals whose wavelet coefficients exhibit a rooted tree structure can be recovered using specially-adapted compressed sensing algorithms from just n=O(k) measurements, where k is the sparsity of the signal. Motivated by these results, we introduce a simplified proportional-dimensional asymptotic framework which enables the quantitative evaluation of recovery guarantees for tree-based compressed sensing. In the context of Gaussian matrices, we apply this framework to existing worst-case analysis of the Iterative Tree Projection (ITP) algorithm which makes use of the tree-based Restricted Isometry Property (RIP). Within the same framework, we then obtain quantitative results based on a new method of analysis, recently introduced in [Cartis and Thompson, 2015], which considers the fixed points of the algorithm. By exploiting the realistic average-case assumption that the measurements are statistically independent of the signal, we obtain significant quantitative improvements when compared to the tree-based RIP analysis. Our results have a refreshingly simple interpretation, explicitly determining a bound on the number of measurements that are required as a multiple of the sparsity. For example we prove that exact recovery of binary tree-based signals from noiseless Gaussian measurements is asymptotically guaranteed for ITP with constant stepsize provided n>50k. All our results extend to the more realistic case in which measurements are corrupted by noise.
The Social Dynamics of Language Change in Online Networks
Venue: arXiv cs.CL 2016
Year: 2016

Language change is a complex social phenomenon, revealing pathways of communication and sociocultural influence. But, while language change has long been a topic of study in sociolinguistics, traditional linguistic research methods rely on circumstantial evidence, estimating the direction of change from differences between older and younger speakers. In this paper, we use a data set of several million Twitter users to track language changes in progress. First, we show that language change can be viewed as a form of social influence: we observe complex contagion for phonetic spellings and "netspeak" abbreviations (e.g., lol), but not for older dialect markers from spoken language. Next, we test whether specific types of social network connections are more influential than others, using a parametric Hawkes process model. We find that tie strength plays an important role: densely embedded social ties are significantly better conduits of linguistic influence. Geographic locality appears to play a more limited role: we find relatively little evidence to support the hypothesis that individuals are more influenced by geographically local social ties, even in their usage of geographical dialect markers.
UberNet: Training a `Universal' Convolutional Neural Network for Low-, Mid-, and High-Level Vision using Diverse Datasets and Limited Memory
Venue: arXiv cs.CV 2016
Year: 2016

In this work we introduce a convolutional neural network (CNN) that jointly handles low-, mid-, and high-level vision tasks in a unified architecture that is trained end-to-end. Such a universal network can act like a `swiss knife' for vision tasks; we call this architecture an UberNet to indicate its overarching nature. We address two main technical challenges that emerge when broadening up the range of tasks handled by a single CNN: (i) training a deep architecture while relying on diverse training sets and (ii) training many (potentially unlimited) tasks with a limited memory budget. Properly addressing these two problems allows us to train accurate predictors for a host of tasks, without compromising accuracy. Through these advances we train in an end-to-end manner a CNN that simultaneously addresses (a) boundary detection (b) normal estimation (c) saliency estimation (d) semantic segmentation (e) human part segmentation (f) semantic boundary detection, (g) region proposal generation and object detection. We obtain competitive performance while jointly addressing all of these tasks in 0.7 seconds per frame on a single GPU. A demonstration of this system can be found at http://cvn.ecp.fr/ubernet/.
Routing-Verification-as-a-Service (RVaaS): Trustworthy Routing Despite Insecure Providers
Venue: arXiv cs.NI 2016
Year: 2016

Computer networks today typically do not provide any mechanisms to the users to learn, in a reliable manner, which paths have (and have not) been taken by their packets. Rather, it seems inevitable that as soon as a packet leaves the network card, the user is forced to trust the network provider to forward the packets as expected or agreed upon. This can be undesirable, especially in the light of today's trend toward more programmable networks: after a successful cyber attack on the network management system or Software-Defined Network (SDN) control plane, an adversary in principle has complete control over the network. This paper presents a low-cost and efficient solution to detect misbehaviors and ensure trustworthy routing over untrusted or insecure providers, in particular providers whose management system or control plane has been compromised (e.g., using a cyber attack). We propose Routing-Verification-as-a-Service (RVaaS): RVaaS offers clients a flexible interface to query information relevant to their traffic, while respecting the autonomy of the network provider. RVaaS leverages key features of OpenFlow-based SDNs to combine (passive and active) configuration monitoring, logical data plane verification and actual in-band tests, in a novel manner.
Reduced-Rank Channel Estimation for Large-Scale MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

We present two reduced-rank channel estimators for large-scale multiple-input, multiple-output (MIMO) systems and analyze their mean square error (MSE) performance. Taking advantage of the channel's transform domain sparseness, the estimators yield outstanding performance and may offer additional mean angle-of-arrival (AoA) information. It is shown that, for the estimators to be effective, one has to select a proper predetermined unitary basis (transform) and be able to determine the dominant channel rank and the associated subspace. Further MSE analysis reveals the relations among the array size, channel rank, signal-to-noise ratio (SNR), and the estimators' performance. It provides rationales for the proposed rank determination and mean AoA estimation algorithms as well. An angle alignment operation included in one of our channel models is proved to be effective in further reducing the required rank, shifting the dominant basis vectors' range (channel spectrum) and improving the estimator's performance when a suitable basis is used. We also draw insightful analogies among MIMO channel modeling, transform coding, parallel spatial search, and receive beamforming. Computer experiment results are provided to examine the numerical effects of various estimator parameters and the advantages of the proposed channel estimators and rank determination method.
ITect: Scalable Information Theoretic Similarity for Malware Detection
Venue: arXiv cs.CR 2016
Year: 2016

Malware creators have been getting their way for too long now. String-based similarity measures can leverage ground truth in a scalable way and can operate at a level of abstraction that is difficult to combat from the code level. We introduce ITect, a scalable approach to malware similarity detection based on information theory. ITect targets file entropy patterns in different ways to achieve 100% precision with 90% accuracy but it could target 100% recall instead. It outperforms VirusTotal for precision and accuracy on combined Kaggle and VirusShare malware.
Comparison of several short-term traffic speed forecasting models
Venue: arXiv cs.CV 2016
Year: 2016

The widespread adoption of smartphones in recent years has made it possible for us to collect large amounts of traffic data. Special software installed on the phones of drivers allow us to gather GPS trajectories of their vehicles on the road network. In this paper, we simulate the trajectories of multiple agents on a road network and use various models to forecast the short-term traffic speed of various links. Our results show that traditional techniques like multiple regression and artificial neural networks work well but simpler adaptive models that do not require prior training also perform comparatively well.
A Flexible Recommendation System for Cable TV
Venue: arXiv cs.IR 2016
Year: 2016

Recommendation systems are being explored by Cable TV operators to improve user satisfaction with services, such as Live TV and Video on Demand (VOD) services. More recently, Catch-up TV has been introduced, allowing users to watch recent broadcast content whenever they want to. These services give users a large set of options from which they can choose from, creating an information overflow problem. Thus, recommendation systems arise as essential tools to solve this problem by helping users in their selection, which increases not only user satisfaction but also user engagement and content consumption. In this paper we present a learning to rank approach that uses contextual information and implicit feedback to improve recommendation systems for a Cable TV operator that provides Live and Catch-up TV services. We compare our approach with existing state-of-the-art algorithms and show that our approach is superior in accuracy, while maintaining high scores of diversity and serendipity.
A Large-Scale Characterization of User Behaviour in Cable TV
Venue: arXiv cs.IR 2016
Year: 2016

Nowadays, Cable TV operators provide their users multiple ways to watch TV content, such as Live TV and Video on Demand (VOD) services. In the last years, Catch-up TV has been introduced, allowing users to watch recent broadcast content whenever they want to. Understanding how the users interact with such services is important to develop solutions that may increase user satisfaction , user engagement and user consumption. In this paper, we characterize, for the first time, how users interact with a large European Cable TV operator that provides Live TV, Catch-up TV and VOD services. We analyzed many characteristics, such as the service usage, user engagement, program type, program genres and time periods. This characterization will help us to have a deeper understanding on how users interact with these different services, that may be used to enhance the recommendation systems of Cable TV providers.
Quantifying Radiographic Knee Osteoarthritis Severity using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a new approach to automatically quantify the severity of knee osteoarthritis (OA) from radiographs using deep convolutional neural networks (CNN). Clinically, knee OA severity is assessed using Kellgren \& Lawrence (KL) grades, a five point scale. Previous work on automatically predicting KL grades from radiograph images were based on training shallow classifiers using a variety of hand engineered features. We demonstrate that classification accuracy can be significantly improved using deep convolutional neural network models pre-trained on ImageNet and fine-tuned on knee OA images. Furthermore, we argue that it is more appropriate to assess the accuracy of automatic knee OA severity predictions using a continuous distance-based evaluation metric like mean squared error than it is to use classification accuracy. This leads to the formulation of the prediction of KL grades as a regression problem and further improves accuracy. Results on a dataset of X-ray images and KL grades from the Osteoarthritis Initiative (OAI) show a sizable improvement over the current state-of-the-art.
Fashion DNA: Merging Content and Sales Data for Recommendation and Article Mapping
Venue: arXiv cs.IR 2016
Year: 2016

We present a method to determine Fashion DNA, coordinate vectors locating fashion items in an abstract space. Our approach is based on a deep neural network architecture that ingests curated article information such as tags and images, and is trained to predict sales for a large set of frequent customers. In the process, a dual space of customer style preferences naturally arises. Interpretation of the metric of these spaces is straightforward: The product of Fashion DNA and customer style vectors yields the forecast purchase likelihood for the customer-item pair, while the angle between Fashion DNA vectors is a measure of item similarity. Importantly, our models are able to generate unbiased purchase probabilities for fashion items based solely on article information, even in absence of sales data, thus circumventing the "cold-start problem" of collaborative recommendation approaches. Likewise, it generalizes easily and reliably to customers outside the training set. We experiment with Fashion DNA models based on visual and/or tag item data, evaluate their recommendation power, and discuss the resulting article similarities.
Bottom-up Instance Segmentation using Deep Higher-Order CRFs
Venue: arXiv cs.CV 2016
Year: 2016

Traditional Scene Understanding problems such as Object Detection and Semantic Segmentation have made breakthroughs in recent years due to the adoption of deep learning. However, the former task is not able to localise objects at a pixel level, and the latter task has no notion of different instances of objects of the same class. We focus on the task of Instance Segmentation which recognises and localises objects down to a pixel level. Our model is based on a deep neural network trained for semantic segmentation. This network incorporates a Conditional Random Field with end-to-end trainable higher order potentials based on object detector outputs. This allows us to reason about instances from an initial, category-level semantic segmentation. Our simple method effectively leverages the great progress recently made in semantic segmentation and object detection. The accurate instance-level segmentations that our network produces is reflected by the considerable improvements obtained over previous work.
A Stackelberg Game for Incentive Proactive Caching Mechanisms in Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, an incentive proactive cache mechanism in cache-enabled small cell networks (SCNs) is proposed, in order to motivate the content providers (CPs) to participate in the caching procedure. A network composed of a single mobile network operator (MNO) and multiple CPs is considered. The MNO aims to define the price it charges the CPs to maximize its revenue while the CPs compete to determine the number of files they cache at the MNO's small base stations (SBSs) to improve the quality of service (QoS) of their users. This problem is formulated as a Stackelberg game where a single MNO is considered as the leader and the multiple CPs willing to cache files are the followers. The followers game is modeled as a non-cooperative game and both the existence and uniqueness of a Nash equilibrium (NE) are proved. The closed-form expression of the NE which corresponds to the amount of storage each CP requests from the MNO is derived. An optimization problem is formulated at the MNO side to determine the optimal price that the MNO should charge the CPs. Simulation results show that at the equilibrium, the MNO and CPs can all achieve a utility that is up to 50% higher than the cases in which the prices and storage quantities are requested arbitrarily.
Cutting down energy usage in wireless sensor networks using Duty Cycle technique and multi-hop routing
Venue: arXiv cs.NI 2016
Year: 2016

A wireless sensor network is composed of many sensor nodes that have been given out in a specific zone and each of them had an ability of collecting information from the environment and sending collected data to the sink. The most significant issues in wireless sensor networks despite the recent progress is the trouble of the severe limitations of energy resources. Since that in different applications of sensor nets we could throw a static or mobile sink then all aspects of such networks should be planned with an awareness of energy. One of the most significant topics related to these networks is routing. One of the most widely used and efficient methods of routing is a hierarchy (based on clustering) method. In The present study with the objective of cutting down energy consumption and persistence of network coverage we have offered a novel algorithm based on clustering algorithms and multi hop routing. To achieve this goal first we layer the network environment based on the size of the network. We will identify the optimal number of cluster heads and every cluster head based on the mechanism of topology control will start to accept members. Likewise we set the first layer as gate layer and subsequently identifying the gate nodes we would turn away half of the sensors and then stop using energy and the remaining nodes in this layer will join the gate nodes because they hold a critical part in bettering the functioning of the system. Cluster heads off following layers send the information to cluster heads in the above layer until sent data will be sent to gate nodes and finally will be sent to sink. We have tested the proposed algorithm in two situations 1) when the sink is off and 2) when a sink is on and simulation data shows that proposed algorithm has better performance in terms of the life span of a network than LEACH and E LEACH protocols.
Measuring Player's Behaviour Change over Time in Public Goods Game
Venue: arXiv cs.AI 2016
Year: 2016

An important issue in public goods game is whether player's behaviour changes over time, and if so, how significant it is. In this game players can be classified into different groups according to the level of their participation in the public good. This problem can be considered as a concept drift problem by asking the amount of change that happens to the clusters of players over a sequence of game rounds. In this study we present a method for measuring changes in clusters with the same items over discrete time points using external clustering validation indices and area under the curve. External clustering indices were originally used to measure the difference between suggested clusters in terms of clustering algorithms and ground truth labels for items provided by experts. Instead of different cluster label comparison, we use these indices to compare between clusters of any two consecutive time points or between the first time point and the remaining time points to measure the difference between clusters through time points. In theory, any external clustering indices can be used to measure changes for any traditional (non-temporal) clustering algorithm, due to the fact that any time point alone is not carrying any temporal information. For the public goods game, our results indicate that the players are changing over time but the change is smooth and relatively constant between any two time points.
Predicting the future relevance of research institutions - The winning solution of the KDD Cup 2016
Venue: arXiv cs.LG 2016
Year: 2016

The world's collective knowledge is evolving through research and new scientific discoveries. It is becoming increasingly difficult to objectively rank the impact research institutes have on global advancements. However, since the funding, governmental support, staff and students quality all mirror the projected quality of the institution, it becomes essential to measure the affiliation's rating in a transparent and widely accepted way. We propose and investigate several methods to rank affiliations based on the number of their accepted papers at future academic conferences. We carry out our investigation using publicly available datasets such as the Microsoft Academic Graph, a heterogeneous graph which contains various information about academic papers. We analyze several models, starting with a simple probabilities-based method and then gradually expand our training dataset, engineer many more features and use mixed models and gradient boosted decision trees models to improve our predictions.
Image and Video Mining through Online Learning
Venue: arXiv cs.CV 2016
Year: 2016

Within the field of image and video recognition, the traditional approach is a dataset split into fixed training and test partitions. However, the labelling of the training set is time-consuming, especially as datasets grow in size and complexity. Furthermore, this approach is not applicable to the home user, who wants to intuitively group their media without tirelessly labelling the content. Our interactive approach is able to iteratively cluster classes of images and video. Our approach is based around the concept of an image signature which, unlike a standard bag of words model, can express co-occurrence statistics as well as symbol frequency. We efficiently compute metric distances between signatures despite their inherent high dimensionality and provide discriminative feature selection, to allow common and distinctive elements to be identified from a small set of user labelled examples. These elements are then accentuated in the image signature to increase similarity between examples and pull correct classes together. By repeating this process in an online learning framework, the accuracy of similarity increases dramatically despite labelling only a few training examples. To demonstrate that the approach is agnostic to media type and features used, we evaluate on three image datasets (15 scene, Caltech101 and FG-NET), a mixed text and image dataset (ImageTag), a dataset used in active learning (Iris) and on three action recognition datasets (UCF11, KTH and Hollywood2). On the UCF11 video dataset, the accuracy is 86.7% despite using only 90 labelled examples from a dataset of over 1200 videos, instead of the standard 1122 training videos. The approach is both scalable and efficient, with a single iteration over the full UCF11 dataset of around 1200 videos taking approximately 1 minute on a standard desktop machine.