OpenRaiser/Intern-Atlas huggingface dataset:
Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks
Venue: arXiv cs.SI 2014
Year: 2014

Kernel spectral clustering corresponds to a weighted kernel principal component analysis problem in a constrained optimization framework. The primal formulation leads to an eigen-decomposition of a centered Laplacian matrix at the dual level. The dual formulation allows to build a model on a representative subgraph of the large scale network in the training phase and the model parameters are estimated in the validation stage. The KSC model has a powerful out-of-sample extension property which allows cluster affiliation for the unseen nodes of the big data network. In this paper we exploit the structure of the projections in the eigenspace during the validation stage to automatically determine a set of increasing distance thresholds. We use these distance thresholds in the test phase to obtain multiple levels of hierarchy for the large scale network. The hierarchical structure in the network is determined in a bottom-up fashion. We empirically showcase that real-world networks have multilevel hierarchical organization which cannot be detected efficiently by several state-of-the-art large scale hierarchical community detection techniques like the Louvain, OSLOM and Infomap methods. We show a major advantage our proposed approach i.e. the ability to locate good quality clusters at both the coarser and finer levels of hierarchy using internal cluster quality metrics on 7 real-life networks.
Bus Travel Time Predictions Using Additive Models
Venue: arXiv cs.LG 2014
Year: 2014

Many factors can affect the predictability of public bus services such as traffic, weather and local events. Other aspects, such as day of week or hour of day, may influence bus travel times as well, either directly or in conjunction with other variables. However, the exact nature of such relationships between travel times and predictor variables is, in most situations, not known. In this paper we develop a framework that allows for flexible modeling of bus travel times through the use of Additive Models. In particular, we model travel times as a sum of linear as well as nonlinear terms that are modeled as smooth functions of predictor variables. The proposed class of models provides a principled statistical framework that is highly flexible in terms of model building. The experimental results demonstrate uniformly superior performance of our best model as compared to previous prediction methods when applied to a very large GPS data set obtained from buses operating in the city of Rio de Janeiro.
Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions
Venue: arXiv cs.LG 2014
Year: 2014

We consider the least-squares regression problem and provide a detailed asymptotic analysis of the performance of averaged constant-step-size stochastic gradient descent (a.k.a. least-mean-squares). In the strongly-convex case, we provide an asymptotic expansion up to explicit exponentially decaying terms. Our analysis leads to new insights into stochastic approximation algorithms: (a) it gives a tighter bound on the allowed step-size; (b) the generalization error may be divided into a variance term which is decaying as O(1/n), independently of the step-size $γ$, and a bias term that decays as O(1/$γ$ 2 n 2); (c) when allowing non-uniform sampling, the choice of a good sampling density depends on whether the variance or bias terms dominate. In particular, when the variance term dominates, optimal sampling densities do not lead to much gain, while when the bias term dominates, we can choose larger step-sizes that leads to significant improvements.
Guaranteed sensor coverage with the weighted-$D^2$ sampling
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we focus on the mobile sensor coverage problem formulated as a continuous locational optimization problem. Cortès et al. first proposed a distributed version of the Lloyd descent algorithm with guaranteed convergence to a local optima. Since then researchers have studied a number of variations of the coverage problem. The quality of the final solution with the Lloyd descent depends on the initial sensor configuration. Inspired by the recent results on a related $k$-means problem, in this paper we propose the weighted-$D^2$ sampling to choose the initial sensor configuration and show that it yields $O(\log k)$-competitive sensor coverage before even applying the Lloyd descent. Through extensive numerical simulations, we show that the initial coverage with the weighted-$D^2$ sampling is significantly lower than that with the uniform random initial sensor configuration. We also show that the average distance traveled by the sensors to reach the final configuration through the Lloyd descent is also significantly lower than that with the uniform random configuration. This also implies considerable savings in the energy spent by the sensors during motion and faster convergence.
Lifted Probabilistic Inference for Asymmetric Graphical Models
Venue: arXiv cs.AI 2014
Year: 2014

Lifted probabilistic inference algorithms have been successfully applied to a large number of symmetric graphical models. Unfortunately, the majority of real-world graphical models is asymmetric. This is even the case for relational representations when evidence is given. Therefore, more recent work in the community moved to making the models symmetric and then applying existing lifted inference algorithms. However, this approach has two shortcomings. First, all existing over-symmetric approximations require a relational representation such as Markov logic networks. Second, the induced symmetries often change the distribution significantly, making the computed probabilities highly biased. We present a framework for probabilistic sampling-based inference that only uses the induced approximate symmetries to propose steps in a Metropolis-Hastings style Markov chain. The framework, therefore, leads to improved probability estimates while remaining unbiased. Experiments demonstrate that the approach outperforms existing MCMC algorithms.
The Interpreter In An Undergraduate Compilers Course
Venue: arXiv cs.CY 2014
Year: 2014

An undergraduate compilers course poses significant challenges to students, in both the conceptual richness of the major components and in the programming effort necessary to implement them. In this paper, I argue that a related architecture, the interpreter, serves as an effective conceptual framework in which to teach some of the later stages of the compiler pipeline. This framework can serve both to unify some of the major concepts that are taught in a typical undergraduate course and to structure the implementation of a semester-long compiler project.
Robotic Behavior Prediction Using Hidden Markov Models
Venue: arXiv cs.RO 2014
Year: 2014

There are many situations in which it would be beneficial for a robot to have predictive abilities similar to those of rational humans. Some of these situations include collaborative robots, robots in adversarial situations, and for dynamic obstacle avoidance. This paper presents an approach to modeling behaviors of dynamic agents in order to empower robots with the ability to predict the agent's actions and identify the behavior the agent is executing in real time. The method of behavior modeling implemented uses hidden Markov models (HMMs) to model the unobservable states of the dynamic agents. The background and theory of the behavior modeling is presented. Experimental results of realistic simulations of a robot predicting the behaviors and actions of a dynamic agent in a static environment are presented.
Countermeasures Against High-Order Fault-Injection Attacks on CRT-RSA
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we study the existing CRT-RSA countermeasures against fault-injection at-tacks. In an attempt to classify them we get to achieve deep understanding of how they work. We show that the many countermeasures that we study (and their variations) actually share a number of common features, but optimize them in different ways. We also show that there is no conceptual distinction between test-based and infective countermeasures and how either one can be transformed into the other. Furthermore, we show that faults on the code (skipping instructions) can be captured by considering only faults on the data. These intermediate results allow us to improve the state of the art in several ways: (a) we fix an existing and that was known to be broken countermeasure (namely the one from Shamir); (b) we drastically optimize an existing countermeasure (namely the one from Vigilant) which we reduce to 3 tests instead of 9 in its original version, and prove that it resists not only one fault but also an arbitrary number of randomizing faults; (c) we also show how to upgrade countermeasures to resist any given number of faults: given a correct first-order countermeasure, we present a way to design a prov-able high-order countermeasure (for a well-defined and reasonable fault model). Finally, we pave the way for a generic approach against fault attacks for any modular arithmetic computations, and thus for the automatic insertion of countermeasures.
Quipper: Concrete Resource Estimation in Quantum Algorithms
Venue: arXiv cs.PL 2014
Year: 2014

Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.
Hashing on Nonlinear Manifolds
Venue: arXiv cs.CV 2014
Year: 2014

Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes preserving the Euclidean similarity in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original high-dimensional data. The complexities of these models, and the problems with out-of-sample data, have previously rendered them unsuitable for application to large-scale embedding, however. In this work, how to learn compact binary embeddings on their intrinsic manifolds is considered. In order to address the above-mentioned difficulties, an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method is proposed. The proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. It is particularly shown that hashing on the basis of t-SNE outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths. The proposed hashing framework is shown to be easily improved, for example, by minimizing the quantization error with learned orthogonal rotations. In addition, a supervised inductive manifold hashing framework is developed by incorporating the label information, which is shown to greatly advance the semantic retrieval performance.
Dropshipping - a revolutionary form movement of goods in the global economic crisis
Venue: arXiv cs.CY 2014
Year: 2014

The paper analyzes the socio-economic impacts of dropshipping - a new form of organization of sales, is rapidly gaining the Russian market. Dropshipping opens up tremendous prospects not only for ordinary people, but also for the Russian manufacturers, which if used properly can dropshipping opportunities with minimal direct access to the world market.
Synthesizing Modular Invariants for Synchronous Code
Venue: arXiv cs.LO 2014
Year: 2014

In this paper, we explore different techniques to synthesize modular invariants for synchronous code encoded as Horn clauses. Modular invariants are a set of formulas that characterizes the validity of predicates. They are very useful for different aspects of analysis, synthesis, testing and program transformation. We describe two techniques to generate modular invariants for code written in the synchronous dataflow language Lustre. The first technique directly encodes the synchronous code in a modular fashion. While in the second technique, we synthesize modular invariants starting from a monolithic invariant. Both techniques, take advantage of analysis techniques based on property-directed reachability. We also describe a technique to minimize the synthesized invariants.
The Entropy of Attention and Popularity in YouTube Videos
Venue: arXiv cs.SI 2014
Year: 2014

The vast majority of YouTube videos never become popular, languishing in obscurity with few views, no likes, and no comments. We use information theoretical measures based on entropy to examine how time series distributions of common measures of popularity in videos from YouTube's "Trending videos" and "Most recent" video feeds relate to the theoretical concept of attention. While most of the videos in the "Most recent" feed are never popular, some 20% of them have distributions of attention metrics and measures of entropy that are similar to distributions for "Trending videos". We analyze how the 20% of "Most recent" videos that become somewhat popular differ from the 80% that do not, then compare these popular "Most recent" videos to different subsets of "Trending videos" to try to characterize and compare the attention each receives.
Colorisation et texturation temps réel d'environnements urbains par système mobile avec scanner laser et caméra fish-eye
Venue: arXiv cs.RO 2014
Year: 2014

We present here a real time mobile mapping system mounted on a vehicle. The terrestrial acquisition system is based on a geolocation system and two sensors, namely, a laser scanner and a camera with a fish-eye lens. We produce 3D colored points cloud and textured models of the environment. Once the system has been calibrated, the data acquisition and processing are done "on the way". This article mainly presents our methods of colorization of point cloud, triangulation and texture mapping.
From Human-Computer Interaction to Human-Robot Social Interaction
Venue: arXiv cs.RO 2014
Year: 2014

Human-Robot Social Interaction became one of active research fields in which researchers from different areas propose solutions and directives leading robots to improve their interactions with humans. In this paper we propose to introduce works in both human robot interaction and human computer interaction and to make a bridge between them, i.e. to integrate emotions and capabilities concepts of the robot in human computer model to become adequate for human robot interaction and discuss challenges related to the proposed model. Finally an illustration through real case of this model will be presented.
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
Venue: arXiv cs.DS 2014
Year: 2014

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G = (V,E)$, with $|V| = n$ and $|E| =m$, in $o(\sqrt{m}\,)$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+\eps)$ approximation in $O(\min(\sqrt{n}/ε, m^{1/3}/\eps^2))$ {\em amortized} time per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld from STOC' 2010.
Space Exploration via Proximity Search
Venue: arXiv cs.CG 2014
Year: 2014

We investigate what computational tasks can be performed on a point set in $\Re^d$, if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following: (A) One can compute an approximate bi-criteria $k$-center clustering of the point set, and more generally compute a greedy permutation of the point set. (B) One can decide if a query point is (approximately) inside the convex-hull of the point set. We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set.
Qubit Data Structures for Analyzing Computing Systems
Venue: arXiv cs.OH 2014
Year: 2014

Qubit models and methods for improving the performance of software and hardware for analyzing digital devices through increasing the dimension of the data structures and memory are proposed. The basic concepts, terminology and definitions necessary for the implementation of quantum computing when analyzing virtual computers are introduced. The investigation results concerning design and modeling computer systems in a cyberspace based on the use of two-component structure <memory - transactions> are presented.
Memory Bounded Deep Convolutional Networks
Venue: arXiv cs.CV 2014
Year: 2014

In this work, we investigate the use of sparsity-inducing regularizers during training of Convolution Neural Networks (CNNs). These regularizers encourage that fewer connections in the convolution and fully connected layers take non-zero values and in effect result in sparse connectivity between hidden units in the deep network. This in turn reduces the memory and runtime cost involved in deploying the learned CNNs. We show that training with such regularization can still be performed using stochastic gradient descent implying that it can be used easily in existing codebases. Experimental evaluation of our approach on MNIST, CIFAR, and ImageNet datasets shows that our regularizers can result in dramatic reductions in memory requirements. For instance, when applied on AlexNet, our method can reduce the memory consumption by a factor of four with minimal loss in accuracy.
On the String Kernel Pre-Image Problem with Applications in Drug Discovery
Venue: arXiv cs.LG 2014
Year: 2014

The pre-image problem has to be solved during inference by most structured output predictors. For string kernels, this problem corresponds to finding the string associated to a given input. An algorithm capable of solving or finding good approximations to this problem would have many applications in computational biology and other fields. This work uses a recent result on combinatorial optimization of linear predictors based on string kernels to develop, for the pre-image, a low complexity upper bound valid for many string kernels. This upper bound is used with success in a branch and bound searching algorithm. Applications and results in the discovery of druggable peptides are presented and discussed.
Krylov Subspace Methods in Dynamical Sampling
Venue: arXiv cs.IT 2014
Year: 2014

Let $B$ be an unknown linear evolution process on $\mathbb C^d\simeq l^2(\mathbb Z_d)$ driving an unknown initial state $x$ and producing the states $\{B^\ell x, \ell = 0,1,\ldots\}$ at different time levels. The problem under consideration in this paper is to find as much information as possible about $B$ and $x$ from the measurements $Y=\{x(i)$, $Bx(i)$, $\dots$, $B^{\ell_i}x(i): i \in Ω\subset \mathbb Z^d\}$. If $B$ is a "low-pass" convolution operator, we show that we can recover both $B$ and $x$, almost surely, as long as we double the amount of temporal samples needed in \cite{ADK13} to recover the signal propagated by a known operator $B$. For a general operator $B$, we can recover parts or even all of its spectrum from $Y$. As a special case of our method, we derive the centuries old Prony's method \cite{BDVMC08, P795, PP13} which recovers a vector with an $s$-sparse Fourier transform from $2s$ of its consecutive components.
Application of Smart Antenna Technologies in Simultaneous Wireless Information and Power Transfer
Venue: arXiv cs.IT 2014
Year: 2014

Simultaneous wireless information and power transfer (SWIPT) is a promising solution to increase the lifetime of wireless nodes and hence alleviate the energy bottleneck of energy constrained wireless networks. As an alternative to conventional energy harvesting techniques, SWIPT relies on the use of radio frequency signals, and is expected to bring some fundamental changes to the design of wireless communication networks. This article focuses on the application of advanced smart antenna technologies, including multiple-input multiple-output and relaying techniques, to SWIPT. These smart antenna technologies have the potential to significantly improve the energy efficiency and also the spectral efficiency of SWIPT. Different network topologies with single and multiple users are investigated, along with some promising solutions to achieve a favorable trade-off between system performance and complexity. A detailed discussion of future research challenges for the design of SWIPT systems is also provided.
J2 Radical in Automata Nearrings
Venue: arXiv cs.FL 2014
Year: 2014

Looking at the automata defined over a group alphabet as a nearring, we see that they are a highly complicated structure. As with ring theory, one method to deal with complexity is to look at semisimplicity modulo radical structures. We find some bounds on the Jacobson 2-radical and show that in certain groups, this radical can be explicitly found and the semisimple image determined.
Beyond the Euler characteristic: Approximating the genus of general graphs
Venue: arXiv cs.DS 2014
Year: 2014

Computing the Euler genus of a graph is a fundamental problem in graph theory and topology. It has been shown to be NP-hard by [Thomassen '89] and a linear-time fixed-parameter algorithm has been obtained by [Mohar '99]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of an $O(1)$-approximation is not ruled out, the currently best-known upper bound is a trivial $O(n/g)$-approximation that follows from bounds on the Euler characteristic. In this paper, we give the first non-trivial approximation algorithm for this problem. Specifically, we present a polynomial-time algorithm which given a graph $G$ of Euler genus $g$ outputs an embedding of $G$ into a surface of Euler genus $g^{O(1)}$. Combined with the above $O(n/g)$-approximation, our result also implies a $O(n^{1-α})$-approximation, for some universal constant $α>0$. Our approximation algorithm also has implications for the design of algorithms on graphs of small genus. Several of these algorithms require that an embedding of the graph into a surface of small genus is given as part of the input. Our result implies that many of these algorithms can be implemented even when the embedding of the input graph is unknown.