OpenRaiser/Intern-Atlas huggingface dataset:
LookAhead: Augmenting Crowdsourced Website Reputation Systems With Predictive Modeling
Venue: arXiv cs.CR 2015
Year: 2015

Unsafe websites consist of malicious as well as inappropriate sites, such as those hosting questionable or offensive content. Website reputation systems are intended to help ordinary users steer away from these unsafe sites. However, the process of assigning safety ratings for websites typically involves humans. Consequently it is time consuming, costly and not scalable. This has resulted in two major problems: (i) a significant proportion of the web space remains unrated and (ii) there is an unacceptable time lag before new websites are rated. In this paper, we show that by leveraging structural and content-based properties of websites, it is possible to reliably and efficiently predict their safety ratings, thereby mitigating both problems. We demonstrate the effectiveness of our approach using four datasets of up to 90,000 websites. We use ratings from Web of Trust (WOT), a popular crowdsourced web reputation system, as ground truth. We propose a novel ensemble classification technique that makes opportunistic use of available structural and content properties of webpages to predict their eventual ratings in two dimensions used by WOT: trustworthiness and child safety. Ours is the first classification system to predict such subjective ratings and the same approach works equally well in identifying malicious websites. Across all datasets, our classification performs well with average F$_1$-score in the 74--90\% range.
PQStream: A Data Stream Architecture for Electrical Power Quality
Venue: arXiv cs.DB 2015
Year: 2015

In this paper, a data stream architecture is presented for electrical power quality (PQ) which is called PQStream. PQStream is developed to process and manage time-evolving data coming from the country-wide mobile measurements of electrical PQ parameters of the Turkish Electricity Transmission System. It is a full-fledged system with a data measurement module which carries out processing of continuous PQ data, a stream database which stores the output of the measurement module, and finally a Graphical User Interface for retrospective analysis of the PQ data stored in the stream database. The presented model is deployed and is available to PQ experts, academicians and researchers of the area. As further studies, data mining methods such as classification and clustering algorithms will be applied in order to deduce useful PQ information from this database of PQ data.
Online Inference for Relation Extraction with a Reduced Feature Set
Venue: arXiv cs.CL 2015
Year: 2015

Access to web-scale corpora is gradually bringing robust automatic knowledge base creation and extension within reach. To exploit these large unannotated---and extremely difficult to annotate---corpora, unsupervised machine learning methods are required. Probabilistic models of text have recently found some success as such a tool, but scalability remains an obstacle in their application, with standard approaches relying on sampling schemes that are known to be difficult to scale. In this report, we therefore present an empirical assessment of the sublinear time sparse stochastic variational inference (SSVI) scheme applied to RelLDA. We demonstrate that online inference leads to relatively strong qualitative results but also identify some of its pathologies---and those of the model---which will need to be overcome if SSVI is to be used for large-scale relation extraction.
Reed-Muller Realization of X (mod P)
Venue: arXiv cs.CR 2015
Year: 2015

This article provides a novel technique of X (mod P) realization. It is based on the Reed-Muller polynomial expansion. The advantage of the approach concludes in the capability to realize X (mod P) for an arbitrary P. The approach is competitive with the known realizations on the speed processing. Advantages and results of comparison with the known approaches for X [9:1] and P=7 is demonstrated.
Approximate Message Passing with Unitary Transformation
Venue: arXiv cs.IT 2015
Year: 2015

Approximate message passing (AMP) and its variants, developed based on loopy belief propagation, are attractive for estimating a vector x from a noisy version of z = Ax, which arises in many applications. For a large A with i. i. d. elements, AMP can be characterized by the state evolution and exhibits fast convergence. However, it has been shown that, AMP mayeasily diverge for a generic A. In this work, we develop a new variant of AMP based on a unitary transformation of the original model (hence the variant is called UT-AMP), where the unitary matrix is available for any matrix A, e.g., the conjugate transpose of the left singular matrix of A, or a normalized DFT (discrete Fourier transform) matrix for any circulant A. We prove that, in the case of Gaussian priors, UT-AMP always converges for any matrix A. It is observed that UT-AMP is much more robust than the original AMP for difficult A and exhibits fast convergence. A special form of UT-AMP with a circulant A was used in our previous work [13] for turbo equalization. This work extends it to a generic A, and provides a theoretical investigation on the convergence.
Socializing Autonomous Units with the Reflexive Game Theory and Resonate-and-Fire neurons
Venue: arXiv cs.MA 2015
Year: 2015

In this study the concept of reflexia is applied to modeling behavior of autonomous units. The relationship between reflexia, on the one hand, and mirror neuron system and perception of emotions, on the other hand, is introduced. The main method of using reflexia in a group of autonomous units is Reflexive Game Theory (RGT). To embody RGT in a group of autonomous agents a communication system is employed. This communication system uses frequency domain multiplexing by means of Izhikevich's resonate-and-fire neural models. The result of socialization of autonomous units by means of RGT and communication system is illustrated in several examples.
Desensitized Kalman Filtering with Analytical Gain
Venue: arXiv cs.IT 2015
Year: 2015

The possible methodologies to handle the uncertain parameter are reviewed. The core idea of the desensitized Kalman filter is introduced. A new cost function consisting of a posterior covariance trace and trace of a weighted norm of the state error sensitivities matrix is minimizing to obtain a well-known analytical gain matrix, which is different from the gain of the desensitized Kalman filter. The pre-estimated uncertain parameter covariance is set as a referential sensitivity-weighting matrix in the new framework, and the rationality and validity of the covariance are tested. Then, these results are extended to the linear continuous system.
Locally Encodable and Decodable Codes for Distributed Storage Systems
Venue: arXiv cs.IT 2015
Year: 2015

We consider the locality of encoding and decoding operations in distributed storage systems (DSS), and propose a new class of codes, called locally encodable and decodable codes (LEDC), that provides a higher degree of operational locality compared to currently known codes. For a given locality structure, we derive an upper bound on the global distance and demonstrate the existence of an optimal LEDC for sufficiently large field size. In addition, we also construct two families of optimal LEDC for fields with size linear in code length.
Stretching Multi-Ring Paxos
Venue: arXiv cs.DC 2015
Year: 2015

Internet-scale services rely on data partitioning and replication to provide scalable performance and high availability. Moreover, to reduce user-perceived response times and tolerate disasters (i.e., the failure of a whole datacenter), services are increasingly becoming geographically distributed. Data partitioning and replication, combined with local and geographical distribution, introduce daunting challenges, including the need to carefully order requests among replicas and partitions. One way to tackle this problem is to use group communication primitives that encapsulate order requirements. This paper presents a detailed performance evaluation of Multi-Ring Paxos, a scalable group communication primitive. We focus our analysis on "extreme conditions" with deployments including high-end 10 Gbps networks, a large number of combined rings (i.e., independent Paxos instances), a large number of replicas in a ring, and a global deployment. We also report on the performance of recovery under peak load and present two novel extensions to boost Multi-Ring Paxos's performance.
On the Girth of (3,L) Quasi-Cyclic LDPC Codes based on Complete Protographs
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of constructing $(3,L)$ quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.
Index reduction of differential algebraic equations by differential algebraic elimination
Venue: arXiv cs.SC 2015
Year: 2015

High index differential algebraic equations (DAEs) are ordinary differential equations (ODEs) with constraints and arise frequently from many mathematical models of physical phenomenons and engineering fields. In this paper, we generalize the idea of differential elimination with Dixon resultant to polynomially nonlinear DAEs. We propose a new algorithm for index reduction of DAEs and establish the notion of differential algebraic elimination, which can provide the differential algebraic resultant of the enlarged system of original equations. To make use of structure of DAEs, variable pencil technique is given to determine the termination of differentiation. Moreover, we also provide a heuristics method for removing the extraneous factors from differential algebraic resultant. The experimentation shows that the proposed algorithm outperforms existing ones for many examples taken from the literature.
A Modified KZ Reduction Algorithm
Venue: arXiv cs.IT 2015
Year: 2015

The Korkine-Zolotareff (KZ) reduction has been used in communications and cryptography. In this paper, we modify a very recent KZ reduction algorithm proposed by Zhang et al., resulting in a new algorithm, which can be much faster and more numerically reliable, especially when the basis matrix is ill conditioned.
Optimal Nudging: Solving Average-Reward Semi-Markov Decision Processes as a Minimal Sequence of Cumulative Tasks
Venue: arXiv cs.LG 2015
Year: 2015

This paper describes a novel method to solve average-reward semi-Markov decision processes, by reducing them to a minimal sequence of cumulative reward problems. The usual solution methods for this type of problems update the gain (optimal average reward) immediately after observing the result of taking an action. The alternative introduced, optimal nudging, relies instead on setting the gain to some fixed value, which transitorily makes the problem a cumulative-reward task, solving it by any standard reinforcement learning method, and only then updating the gain in a way that minimizes uncertainty in a minmax sense. The rule for optimal gain update is derived by exploiting the geometric features of the w-l space, a simple mapping of the space of policies. The total number of cumulative reward tasks that need to be solved is shown to be small. Some experiments are presented to explore the features of the algorithm and to compare its performance with other approaches.
Poisson Matrix Recovery and Completion
Venue: arXiv cs.LG 2015
Year: 2015

We extend the theory of low-rank matrix recovery and completion to the case when Poisson observations for a linear combination or a subset of the entries of a matrix are available, which arises in various applications with count data. We consider the usual matrix recovery formulation through maximum likelihood with proper constraints on the matrix $M$ of size $d_1$-by-$d_2$, and establish theoretical upper and lower bounds on the recovery error. Our bounds for matrix completion are nearly optimal up to a factor on the order of $\mathcal{O}(\log(d_1 d_2))$. These bounds are obtained by combing techniques for compressed sensing for sparse vectors with Poisson noise and for analyzing low-rank matrices, as well as adapting the arguments used for one-bit matrix completion \cite{davenport20121} (although these two problems are different in nature) and the adaptation requires new techniques exploiting properties of the Poisson likelihood function and tackling the difficulties posed by the locally sub-Gaussian characteristic of the Poisson distribution. Our results highlight a few important distinctions of the Poisson case compared to the prior work including having to impose a minimum signal-to-noise requirement on each observed entry and a gap in the upper and lower bounds. We also develop a set of efficient iterative algorithms and demonstrate their good performance on synthetic examples and real data.
Inferring Program Transformations from Type Transformations for Partitioning of Ordered Sets
Venue: arXiv cs.PL 2015
Year: 2015

In this paper I introduce a mechanism to derive program transforma- tions from order-preserving transformations of vector types. The purpose of this work is to allow automatic generation of correct-by-construction instances of programs in a streaming data processing paradigm suitable for FPGA processing. We show that for it is possible to automatically derive instances for programs based on combinations of opaque element- processing functions combined using foldl and map, purely from the type transformations.
Effective Discriminative Feature Selection with Non-trivial Solutions
Venue: arXiv cs.LG 2015
Year: 2015

Feature selection and feature transformation, the two main ways to reduce dimensionality, are often presented separately. In this paper, a feature selection method is proposed by combining the popular transformation based dimensionality reduction method Linear Discriminant Analysis (LDA) and sparsity regularization. We impose row sparsity on the transformation matrix of LDA through ${\ell}_{2,1}$-norm regularization to achieve feature selection, and the resultant formulation optimizes for selecting the most discriminative features and removing the redundant ones simultaneously. The formulation is extended to the ${\ell}_{2,p}$-norm regularized case: which is more likely to offer better sparsity when $0<p<1$. Thus the formulation is a better approximation to the feature selection problem. An efficient algorithm is developed to solve the ${\ell}_{2,p}$-norm based optimization problem and it is proved that the algorithm converges when $0<p\le 2$. Systematical experiments are conducted to understand the work of the proposed method. Promising experimental results on various types of real-world data sets demonstrate the effectiveness of our algorithm.
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
Venue: arXiv cs.DS 2015
Year: 2015

We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of $k$ objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the $n^{O(k)}$ time brute force algorithm of selecting $k$ objects can be improved to $n^{O(\sqrt{k})}$ time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram of a hypothetical solution of $k$ objects, guess a balanced separator cycle of this Voronoi diagram to obtain a set that separates the solution in a balanced way, and then recurse on the resulting subproblems. We complement our study by giving evidence that packing problems have $n^{O(\sqrt{k})}$ time algorithms for a much more general class of objects than covering problems have.
Deep Convolutional Neural Networks Based on Semi-Discrete Frames
Venue: arXiv cs.LG 2015
Year: 2015

Deep convolutional neural networks have led to breakthrough results in practical feature extraction applications. The mathematical analysis of these networks was pioneered by Mallat, 2012. Specifically, Mallat considered so-called scattering networks based on identical semi-discrete wavelet frames in each network layer, and proved translation-invariance as well as deformation stability of the resulting feature extractor. The purpose of this paper is to develop Mallat's theory further by allowing for different and, most importantly, general semi-discrete frames (such as, e.g., Gabor frames, wavelets, curvelets, shearlets, ridgelets) in distinct network layers. This allows to extract wider classes of features than point singularities resolved by the wavelet transform. Our generalized feature extractor is proven to be translation-invariant, and we develop deformation stability results for a larger class of deformations than those considered by Mallat. For Mallat's wavelet-based feature extractor, we get rid of a number of technical conditions. The mathematical engine behind our results is continuous frame theory, which allows us to completely detach the invariance and deformation stability proofs from the particular algebraic structure of the underlying frames.
A robust and efficient video representation for action recognition
Venue: arXiv cs.CV 2015
Year: 2015

This paper introduces a state-of-the-art video representation and applies it to efficient action recognition and detection. We first propose to improve the popular dense trajectory features by explicit camera motion estimation. More specifically, we extract feature point matches between frames using SURF descriptors and dense optical flow. The matches are used to estimate a homography with RANSAC. To improve the robustness of homography estimation, a human detector is employed to remove outlier matches from the human body as human motion is not constrained by the camera. Trajectories consistent with the homography are considered as due to camera motion, and thus removed. We also use the homography to cancel out camera motion from the optical flow. This results in significant improvement on motion-based HOF and MBH descriptors. We further explore the recent Fisher vector as an alternative feature encoding approach to the standard bag-of-words histogram, and consider different ways to include spatial layout information in these encodings. We present a large and varied set of evaluations, considering (i) classification of short basic actions on six datasets, (ii) localization of such actions in feature-length movies, and (iii) large-scale recognition of complex events. We find that our improved trajectory features significantly outperform previous dense trajectories, and that Fisher vectors are superior to bag-of-words encodings for video recognition tasks. In all three tasks, we show substantial improvements over the state-of-the-art results.
A New Covert Channel over Cellular Voice Channel in Smartphones
Venue: arXiv cs.CR 2015
Year: 2015

Investigating network covert channels in smartphones has become increasingly important as smartphones have recently replaced the role of traditional computers. Smartphones are subject to traditional computer network covert channel techniques. Smartphones also introduce new sets of covert channel techniques as they add more capabilities and multiple network connections. This work presents a new network covert channel in smartphones. The research studies the ability to leak information from the smartphones applications by reaching the cellular voice stream, and it examines the ability to employ the cellular voice channel to be a potential medium of information leakage through carrying modulated speech-like data covertly. To validate the theory, an Android software audio modem has been developed and it was able to leak data successfully through the cellular voice channel stream by carrying modulated data with a throughput of 13 bps with 0.018% BER. Moreover, Android security policies are investigated and broken in order to implement a user-mode rootkit that opens the voice channels by stealthily answering an incoming voice call. Multiple scenarios are conducted to verify the effectiveness of the proposed covert channel. This study identifies a new potential smartphone covert channel, and discusses some security vulnerabilities in Android OS that allow the use of this channel demonstrating the need to set countermeasures against this kind of breach.
Distinguishing Cause from Effect Based on Exogeneity
Venue: arXiv cs.AI 2015
Year: 2015

Recent developments in structural equation modeling have produced several methods that can usually distinguish cause from effect in the two-variable case. For that purpose, however, one has to impose substantial structural constraints or smoothness assumptions on the functional causal models. In this paper, we consider the problem of determining the causal direction from a related but different point of view, and propose a new framework for causal direction determination. We show that it is possible to perform causal inference based on the condition that the cause is "exogenous" for the parameters involved in the generating process from the cause to the effect. In this way, we avoid the structural constraints required by the SEM-based approaches. In particular, we exploit nonparametric methods to estimate marginal and conditional distributions, and propose a bootstrap-based approach to test for the exogeneity condition; the testing results indicate the causal direction between two variables. The proposed method is validated on both synthetic and real data.
On Two-Pair Two-Way Relay Channel with an Intermittently Available Relay
Venue: arXiv cs.IT 2015
Year: 2015

When multiple users share the same resource for physical layer cooperation such as relay terminals in their vicinities, this shared resource may not be always available for every user, and it is critical for transmitting terminals to know whether other users have access to that common resource in order to better utilize it. Failing to learn this critical piece of information may cause severe issues in the design of such cooperative systems. In this paper, we address this problem by investigating a two-pair two-way relay channel with an intermittently available relay. In the model, each pair of users need to exchange their messages within their own pair via the shared relay. The shared relay, however, is only intermittently available for the users to access. The accessing activities of different pairs of users are governed by independent Bernoulli random processes. Our main contribution is the characterization of the capacity region to within a bounded gap in a symmetric setting, for both delayed and instantaneous state information at transmitters. An interesting observation is that the bottleneck for information flow is the quality of state information (delayed or instantaneous) available at the relay, not those at the end users. To the best of our knowledge, our work is the first result regarding how the shared intermittent relay should cooperate with multiple pairs of users in such a two-way cooperative network.