OpenRaiser/Intern-Atlas huggingface dataset:
Website-Targeted False Content Injection by Network Operators
Venue: arXiv cs.CR 2016
Year: 2016

It is known that some network operators inject false content into users' network traffic. Yet all previous works that investigate this practice focus on edge ISPs (Internet Service Providers), namely, those that provide Internet access to end users. Edge ISPs that inject false content affect their customers only. However, in this work we show that not only edge ISPs may inject false content, but also core network operators. These operators can potentially alter the traffic of \emph{all} Internet users who visit predetermined websites. We expose this practice by inspecting a large amount of traffic originating from several networks. Our study is based on the observation that the forged traffic is injected in an out-of-band manner: the network operators do not update the network packets in-path, but rather send the forged packets \emph{without} dropping the legitimate ones. This creates a race between the forged and the legitimate packets as they arrive to the end user. This race can be identified and analyzed. Our analysis shows that the main purpose of content injection is to increase the network operators' revenue by inserting advertisements to websites. Nonetheless, surprisingly, we have also observed numerous cases of injected malicious content. We publish representative samples of the injections to facilitate continued analysis of this practice by the security community.
δ-MAPS: From spatio-temporal data to a weighted and lagged network between functional domains
Venue: arXiv cs.OH 2016
Year: 2016

We propose δ-MAPS, a method that analyzes spatio-temporal data to first identify the distinct spatial components of the underlying system, referred to as "domains", and second to infer the connections between them. A domain is a spatially contiguous region of highly correlated temporal activity. The core of a domain is a point or subregion at which a metric of local homogeneity is maximum across the entire domain. We compute a domain as the maximum-sized set of spatially contiguous cells that include the detected core and satisfy a homogeneity constraint, expressed in terms of the average pairwise cross-correlation across all cells in the domain. Domains may be spatially overlapping. Different domains may have correlated activity, potentially at a lag, because of direct or indirect interactions. The proposed edge inference method examines the statistical significance of each lagged cross-correlation between two domains, infers a range of lag values for each edge, and assigns a weight to each edge based on the covariance of the two domains. We illustrate the application of δ-MAPS on data from two domains: climate science and neuroscience.
Reducing MIMO Detection Complexity via Hierarchical Modulation
Venue: arXiv cs.IT 2016
Year: 2016

This work considers multiple-input multiple-output (MIMO) communication systems using hierarchical modulation. A disadvantage of the maximum-likelihood (ML) MIMO detector is that computational complexity increases exponentially with the number of transmit antennas. To reduce complexity, we propose a hierarchical modulation scheme to be used in MIMO trans- mission where base and enhancement layers are incorporated. In the proposed receiver, the base layer is detected first with a minimum mean square error (MMSE) detector which is followed by ML detection of the enhancement layer. Our results indicate that the proposed low complexity scheme does not compromise performance when design parameters such as code rates and constellation ratio are chosen carefully.
Stuck in a What? Adventures in Weight Space
Venue: arXiv cs.LG 2016
Year: 2016

Deep learning researchers commonly suggest that converged models are stuck in local minima. More recently, some researchers observed that under reasonable assumptions, the vast majority of critical points are saddle points, not true minima. Both descriptions suggest that weights converge around a point in weight space, be it a local optima or merely a critical point. However, it's possible that neither interpretation is accurate. As neural networks are typically over-complete, it's easy to show the existence of vast continuous regions through weight space with equal loss. In this paper, we build on recent work empirically characterizing the error surfaces of neural networks. We analyze training paths through weight space, presenting evidence that apparent convergence of loss does not correspond to weights arriving at critical points, but instead to large movements through flat regions of weight space. While it's trivial to show that neural network error surfaces are globally non-convex, we show that error surfaces are also locally non-convex, even after breaking symmetry with a random initialization and also after partial training.
Investigating Drivers' Head and Glance Correspondence
Venue: arXiv cs.OH 2016
Year: 2016

The relationship between a driver's glance pattern and corresponding head rotation is highly complex due to its nonlinear dependence on the individual, task, and driving context. This study explores the ability of head pose to serve as an estimator for driver gaze by connecting head rotation data with manually coded gaze region data using both a statistical analysis approach and a predictive (i.e., machine learning) approach. For the latter, classification accuracy increased as visual angles between two glance locations increased. In other words, the greater the shift in gaze, the higher the accuracy of classification. This is an intuitive but important concept that we make explicit through our analysis. The highest accuracy achieved was 83% using the method of Hidden Markov Models (HMM) for the binary gaze classification problem of (1) the forward roadway versus (2) the center stack. Results suggest that although there are individual differences in head-glance correspondence while driving, classifier models based on head-rotation data may be robust to these differences and therefore can serve as reasonable estimators for glance location. The results suggest that driver head pose can be used as a surrogate for eye gaze in several key conditions including the identification of high-eccentricity glances. Inexpensive driver head pose tracking may be a key element in detection systems developed to mitigate driver distraction and inattention.
Capacity-Achieving Iterative LMMSE Detection for MIMO-NOMA Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a iterative Linear Minimum Mean Square Error (LMMSE) detection for the uplink Multiuser Multiple-Input and Multiple-Output (MU-MIMO) systems with Non-Orthogonal Multiple Access (NOMA). The iterative LMMSE detection greatly reduces the system computational complexity by departing the overall processing into many low-complexity distributed calculations. However, it is generally considered to be sub-optimal and achieves relatively poor performance. In this paper, we firstly present the matching conditions and area theorems for the iterative detection of the MIMO-NOMA systems. Based on the proposed matching conditions and area theorems, the achievable rate region of the iterative LMMSE detection is analysed. We prove that by properly design the iterative LMMSE detection, it can achieve (i) the optimal sum capacity of MU-MIMO systems, (ii) all the maximal extreme points in the capacity region of MU-MIMO system, and (iii) the whole capacity region of two-user MIMO systems.
Parametric Prediction from Parametric Agents
Venue: arXiv cs.GT 2016
Year: 2016

We consider a problem of prediction based on opinions elicited from heterogeneous rational agents with private information. Making an accurate prediction with a minimal cost requires a joint design of the incentive mechanism and the prediction algorithm. Such a problem lies at the nexus of statistical learning theory and game theory, and arises in many domains such as consumer surveys and mobile crowdsourcing. In order to elicit heterogeneous agents' private information and incentivize agents with different capabilities to act in the principal's best interest, we design an optimal joint incentive mechanism and prediction algorithm called COPE (COst and Prediction Elicitation), the analysis of which offers several valuable engineering insights. First, when the costs incurred by the agents are linear in the exerted effort, COPE corresponds to a "crowd contending" mechanism, where the principal only employs the agent with the highest capability. Second, when the costs are quadratic, COPE corresponds to a "crowd-sourcing" mechanism that employs multiple agents with different capabilities at the same time. Numerical simulations show that COPE improves the principal's profit and the network profit significantly (larger than 30% in our simulations), comparing to those mechanisms that assume all agents have equal capabilities.
A Bayesian Approach to the Data Description Problem
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we address the problem of data description using a Bayesian framework. The goal of data description is to draw a boundary around objects of a certain class of interest to discriminate that class from the rest of the feature space. Data description is also known as one-class learning and has a wide range of applications. The proposed approach uses a Bayesian framework to precisely compute the class boundary and therefore can utilize domain information in form of prior knowledge in the framework. It can also operate in the kernel space and therefore recognize arbitrary boundary shapes. Moreover, the proposed method can utilize unlabeled data in order to improve accuracy of discrimination. We evaluate our method using various real-world datasets and compare it with other state of the art approaches of data description. Experiments show promising results and improved performance over other data description and one-class learning algorithms.
Noisy population recovery in polynomial time
Venue: arXiv cs.CC 2016
Year: 2016

In the noisy population recovery problem of Dvir et al., the goal is to learn an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $μ\in [0,1]$, a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with probability $(1-μ)/2$. We assume an upper bound $k$ on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error $\varepsilon$. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We show that for $μ> 0$, the sample complexity (and hence the algorithmic complexity) is bounded by a polynomial in $k$, $n$ and $1/\varepsilon$ improving upon the previous best result of $\mathsf{poly}(k^{\log\log k},n,1/\varepsilon)$ due to Lovett and Zhang. Our proof combines ideas from Lovett and Zhang with a \emph{noise attenuated} version of Möbius inversion. In turn, the latter crucially uses the construction of \emph{robust local inverse} due to Moitra and Saks.
From quantum foundations via natural language meaning to a theory of everything
Venue: arXiv cs.CL 2016
Year: 2016

In this paper we argue for a paradigmatic shift from `reductionism' to `togetherness'. In particular, we show how interaction between systems in quantum theory naturally carries over to modelling how word meanings interact in natural language. Since meaning in natural language, depending on the subject domain, encompasses discussions within any scientific discipline, we obtain a template for theories such as social interaction, animal behaviour, and many others.
Spatial multi-LRU Caching for Wireless Networks with Coverage Overlaps
Venue: arXiv cs.PF 2016
Year: 2016

This article introduces a novel family of decentralised caching policies, applicable to wireless networks with finite storage at the edge-nodes (stations). These policies are based on the Least-Recently-Used replacement principle, and are, here, referred to as spatial multi-LRU. Based on these, cache inventories are updated in a way that provides content diversity to users who are covered by, and thus have access to, more than one station. Two variations are proposed, namely the multi-LRU-One and -All, which differ in the number of replicas inserted in the involved caches. By introducing spatial approximations, we propose a Che-like method to predict the hit probability, which gives very accurate results under the Independent Reference Model (IRM). It is shown that the performance of multi-LRU increases the more the multi-coverage areas increase, and it approaches the performance of other proposed centralised policies, when multi-coverage is sufficient. For IRM traffic multi-LRU-One outperforms multi-LRU-All, whereas when the traffic exhibits temporal locality the -All variation can perform better.
Life, The Mind, and Everything
Venue: arXiv cs.GL 2016
Year: 2016

Incompleteness theorems of Godel, Turing, Chaitin, and Algorithmic Information Theory have profound epistemological implications. Incompleteness limits our ability to ever understand every observable phenomenon in the universe. Incompleteness limits the ability of evolutionary processes from finding optimal solutions. Incompleteness limits the detectability of machine consciousness. This is an effort to convey these thoughts and results in a somewhat entertaining manner.
Toward Game Level Generation from Gameplay Videos
Venue: arXiv cs.AI 2016
Year: 2016

Algorithms that generate computer game content require game design knowledge. We present an approach to automatically learn game design knowledge for level design from gameplay videos. We further demonstrate how the acquired design knowledge can be used to generate sections of game levels. Our approach involves parsing video of people playing a game to detect the appearance of patterns of sprites and utilizing machine learning to build a probabilistic model of sprite placement. We show how rich game design information can be automatically parsed from gameplay videos and represented as a set of generative probabilistic models. We use Super Mario Bros. as a proof of concept. We evaluate our approach on a measure of playability and stylistic similarity to the original levels as represented in the gameplay videos.
Top-N Recommendation with Novel Rank Approximation
Venue: arXiv cs.IR 2016
Year: 2016

The importance of accurate recommender systems has been widely recognized by academia and industry. However, the recommendation quality is still rather low. Recently, a linear sparse and low-rank representation of the user-item matrix has been applied to produce Top-N recommendations. This approach uses the nuclear norm as a convex relaxation for the rank function and has achieved better recommendation accuracy than the state-of-the-art methods. In the past several years, solving rank minimization problems by leveraging nonconvex relaxations has received increasing attention. Some empirical results demonstrate that it can provide a better approximation to original problems than convex relaxation. In this paper, we propose a novel rank approximation to enhance the performance of Top-N recommendation systems, where the approximation error is controllable. Experimental results on real data show that the proposed rank approximation improves the Top-$N$ recommendation accuracy substantially.
Probe Machine
Venue: arXiv cs.CC 2016
Year: 2016

A novel computing model, called \emph{Probe Machine}, is proposed in this paper. Different from Turing Machine, Probe Machine is a fully-parallel computing model in the sense that it can simultaneously process multiple pairs of data, rather than sequentially process every pair of linearly-adjacent data. In this paper, we establish the mathematical model of Probe Machine as a 9-tuple consisting of data library, probe library, data controller, probe controller, probe operation, computing platform, detector, true solution storage, and residue collector. We analyze the computation capability of the Probe Machine model, and in particular we show that Turing Machine is a special case of Probe Machine. We revisit two NP-complete problems---i.e., the Graph Coloring and Hamilton Cycle problems, and devise two algorithms on basis of the established Probe Machine model, which can enumerate all solutions to each of these problems by only one probe operation. Furthermore, we show that Probe Machine can be implemented by leveraging the nano-DNA probe technologies. The computational power of an electronic computer based on Turing Machine is known far more than that of the human brain. A question naturally arises: will a future computer based on Probe Machine outperform the human brain in more ways beyond the computational power?
Minimum Cost Homomorphisms with Constrained Costs
Venue: arXiv cs.CC 2016
Year: 2016

Minimum cost homomorphism problems can be viewed as a generalization of list homomorphism problems. They also extend two well-known graph colouring problems: the minimum colour sum problem and the optimum cost chromatic partition problem. In both of these problems, the cost function meets an additional constraint: the cost of using a specific colour is the same for every vertex of the input graph. We study minimum cost homomorphism problems with cost functions constrained to have this property. Clearly, when the standard minimum cost homomorphism problem is polynomial, then the problem with constrained costs is also polynomial. We expect that the same may hold for the cases when the standard minimum cost homomorphism problem is NP-complete. We prove that this is the case for trees $H$: we obtain a dichotomy of minimum constrained cost homomorphism problems which coincides with the dichotomy of standard minimum cost homomorphism problems. For general graphs $H$, we prove a partial dichotomy: the problem is polynomial if $H$ is a proper interval graph and NP-complete when $H$ is not chordal bipartite.
Influence of morphological parameters in 3D composite materials on their effective thermal properties and comparison with effective mechanical properties
Venue: arXiv cs.CE 2016
Year: 2016

In this paper we study the effective thermal behaviour of 3D representative volume elements (RVEs) of two-phased composite materials constituted by a matrix with cylindrical and spherical inclusions distributed randomly, with periodic boundaries. Variations around the shape of inclusions have been taken into account, by corrugating shapes, excavating and/or by removing pieces of inclusions. The effective behaviour is computed with the help of homogenization process based on an accelerated FFT-scheme giving the thermal conductivity tensor. Several morphological parameters are also taken into account for instance the number and the volume fraction of each type of inclusions,... in order to analyse the behaviour of the composite for a large number of geometries. We compare the results obtained for RVEs with and without variations, and then with the mechanical results of such composite studied in our previous paper.
Channel Estimation for Millimeter Wave Multiuser MIMO Systems via PARAFAC Decomposition
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of uplink channel estimation for millimeter wave (mmWave) systems, where the base station (BS) and mobile stations (MSs) are equipped with large antenna arrays to provide sufficient beamforming gain for outdoor wireless communications. Hybrid analog and digital beamforming structures are employed by both the BS and the MS due to hardware constraints. We propose a layered pilot transmission scheme and a CANDECOMP/PARAFAC (CP) decomposition-based method for joint estimation of the channels from multiple users (i.e. MSs) to the BS. The proposed method exploits the sparse scattering nature of the mmWave channel and the intrinsic multi-dimensional structure of the multiway data collected from multiple modes. The uniqueness of the CP decomposition is studied and sufficient conditions for essential uniqueness are obtained. The conditions shed light on the design of the beamforming matrix, the combining matrix and the pilot sequences, and meanwhile provide general guidelines for choosing system parameters. Our analysis reveals that our proposed method can achieve a substantial training overhead reduction by employing the layered pilot transmission scheme. Simulation results show that the proposed method presents a clear advantage over a compressed sensing-based method in terms of both estimation accuracy and computational complexity.
PCA/LDA Approach for Text-Independent Speaker Recognition
Venue: arXiv cs.SD 2016
Year: 2016

Various algorithms for text-independent speaker recognition have been developed through the decades, aiming to improve both accuracy and efficiency. This paper presents a novel PCA/LDA-based approach that is faster than traditional statistical model-based methods and achieves competitive results. First, the performance based on only PCA and only LDA is measured; then a mixed model, taking advantages of both methods, is introduced. A subset of the TIMIT corpus composed of 200 male speakers, is used for enrollment, validation and testing. The best results achieve 100%; 96% and 95% classification rate at population level 50; 100 and 200, using 39-dimensional MFCC features with delta and double delta. These results are based on 12-second text-independent speech for training and 4-second data for test. These are comparable to the conventional MFCC-GMM methods, but require significantly less time to train and operate.
Bayesian Inference of Diffusion Networks with Unknown Infection Times
Venue: arXiv cs.SI 2016
Year: 2016

The analysis of diffusion processes in real-world propagation scenarios often involves estimating variables that are not directly observed. These hidden variables include parental relationships, the strengths of connections between nodes, and the moments of time that infection occurs. In this paper, we propose a framework in which all three sets of parameters are assumed to be hidden and we develop a Bayesian approach to infer them. After justifying the model assumptions, we evaluate the performance efficiency of our proposed approach through numerical simulations on synthetic datasets and real-world diffusion processes.
vDNN: Virtualized Deep Neural Networks for Scalable, Memory-Efficient Neural Network Design
Venue: arXiv cs.DC 2016
Year: 2016

The most widely used machine learning frameworks require users to carefully tune their memory usage so that the deep neural network (DNN) fits into the DRAM capacity of a GPU. This restriction hampers a researcher's flexibility to study different machine learning algorithms, forcing them to either use a less desirable network architecture or parallelize the processing across multiple GPUs. We propose a runtime memory manager that virtualizes the memory usage of DNNs such that both GPU and CPU memory can simultaneously be utilized for training larger DNNs. Our virtualized DNN (vDNN) reduces the average GPU memory usage of AlexNet by up to 89%, OverFeat by 91%, and GoogLeNet by 95%, a significant reduction in memory requirements of DNNs. Similar experiments on VGG-16, one of the deepest and memory hungry DNNs to date, demonstrate the memory-efficiency of our proposal. vDNN enables VGG-16 with batch size 256 (requiring 28 GB of memory) to be trained on a single NVIDIA Titan X GPU card containing 12 GB of memory, with 18% performance loss compared to a hypothetical, oracular GPU with enough memory to hold the entire DNN.