OpenRaiser/Intern-Atlas huggingface dataset:
Variability in data streams
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of tracking with small relative error an integer function $f(n)$ defined by a distributed update stream $f'(n)$. Existing streaming algorithms with worst-case guarantees for this problem assume $f(n)$ to be monotone; there are very large lower bounds on the space requirements for summarizing a distributed non-monotonic stream, often linear in the size $n$ of the stream. Input streams that give rise to large space requirements are highly variable, making relatively large jumps from one timestep to the next. However, streams often vary slowly in practice. What has heretofore been lacking is a framework for non-monotonic streams that admits algorithms whose worst-case performance is as good as existing algorithms for monotone streams and degrades gracefully for non-monotonic streams as those streams vary more quickly. In this paper we propose such a framework. We introduce a new stream parameter, the "variability" $v$, deriving its definition in a way that shows it to be a natural parameter to consider for non-monotonic streams. It is also a useful parameter. From a theoretical perspective, we can adapt existing algorithms for monotone streams to work for non-monotonic streams, with only minor modifications, in such a way that they reduce to the monotone case when the stream happens to be monotone, and in such a way that we can refine the worst-case communication bounds from $Θ(n)$ to $\tilde{O}(v)$. From a practical perspective, we demonstrate that $v$ can be small in practice by proving that $v$ is $O(\log f(n))$ for monotone streams and $o(n)$ for streams that are "nearly" monotone or that are generated by random walks. We expect $v$ to be $o(n)$ for many other interesting input classes as well.
Evaluation of Deep Convolutional Nets for Document Image Classification and Retrieval
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a new state-of-the-art for document image classification and retrieval, using features learned by deep convolutional neural networks (CNNs). In object and scene analysis, deep neural nets are capable of learning a hierarchical chain of abstraction from pixel inputs to concise and descriptive representations. The current work explores this capacity in the realm of document analysis, and confirms that this representation strategy is superior to a variety of popular hand-crafted alternatives. Experiments also show that (i) features extracted from CNNs are robust to compression, (ii) CNNs trained on non-document images transfer well to document analysis tasks, and (iii) enforcing region-specific feature-learning is unnecessary given sufficient training data. This work also makes available a new labelled subset of the IIT-CDIP collection, containing 400,000 document images across 16 categories, useful for training new CNNs for document analysis.
RF-Powered Cognitive Radio Networks: Technical Challenges and Limitations
Venue: arXiv cs.IT 2015
Year: 2015

The increasing demand for spectral and energy efficient communication networks has spurred a great interest in energy harvesting (EH) cognitive radio networks (CRNs). Such a revolutionary technology represents a paradigm shift in the development of wireless networks, as it can simultaneously enable the efficient use of the available spectrum and the exploitation of radio frequency (RF) energy in order to reduce the reliance on traditional energy sources. This is mainly triggered by the recent advancements in microelectronics that puts forward RF energy harvesting as a plausible technique in the near future. On the other hand, it is suggested that the operation of a network relying on harvested energy needs to be redesigned to allow the network to reliably function in the long term. To this end, the aim of this survey paper is to provide a comprehensive overview of the recent development and the challenges regarding the operation of CRNs powered by RF energy. In addition, the potential open issues that might be considered for the future research are also discussed in this paper.
CrowdSurf: Empowering Informed Choices in the Web
Venue: arXiv cs.CY 2015
Year: 2015

When surfing the Internet, individuals leak personal and corporate information to third parties whose (legitimate or not) businesses revolve around the value of collected data. The implications are serious, from a person unwillingly exposing private information to an unknown third party, to a company unable to manage the flow of its information to the outside world. The point is that individuals and companies are more and more kept out of the loop when it comes to control private data. With the goal of empowering informed choices in information leakage through the Internet, we propose CROWDSURF, a system for comprehensive and collaborative auditing of data that flows to Internet services. Similarly to open-source efforts, we enable users to contribute in building awareness and control over privacy and communication vulnerabilities. CROWDSURF provides the core infrastructure and algorithms to let individuals and enterprises regain control on the information exposed on the web. We advocate CROWDSURF as a data processing layer positioned right below HTTP in the host protocol stack. This enables the inspection of clear-text data even when HTTPS is deployed and the application of processing rules that are customizable to fit any need. Preliminary results obtained executing a prototype implementation on ISP traffic traces demonstrate the feasibility of CROWDSURF.
On the Performance comparison of RIP, OSPF, IS-IS and EIGRP routing protocols
Venue: arXiv cs.NI 2015
Year: 2015

Nowadays, routing protocols have become a crucial part of the modern communication networks. A routing protocol's responsibility lies in determining the way routers communicate with each other in order to forward any kind of packets, from a source to a destination, using the optimal path that would provide the most efficiency. There are many routing protocols out there today, some old and some new, but all are used for the same purpose. In general, to ideally select routes between any two nodes on a computer network and disseminate information. This paper takes into consideration four of such routing protocols (RIP, OSPF, IS-IS and EIGRP), expresses them and analyzes their way of operation. It also presents the results of a simulation, that took place for the sole purpose of studying the behavior of those four protocols, under the same circumstances, as well as the evaluation of the comparison with one another based on the results of the simulation.
Linear complexity SimRank computation based on the iterative diagonal estimation
Venue: arXiv cs.DS 2015
Year: 2015

This paper presents a deterministic linear time complexity IDE-SimRank method to approximately compute SimRank with proved error bound. SimRank is a well-known similarity measure between graph vertices which relies on graph topology only and is built on intuition that "two objects are similar if they are related to similar objects". The fixed point equation for direct SimRank computation is the discrete Lyapunov equation with specific diagonal matrix in the right hand side. The proposed method is based on estimation of this diagonal matrix with GMRES and use this estimation to compute singe-source and single pairs queries. These computations are executed with the part of series converging to the discrete Lyapunov equation solution.
Construction and implementation of asymptotic expansions for Jacobi--type orthogonal polynomials
Venue: arXiv cs.MS 2015
Year: 2015

We are interested in the asymptotic behavior of orthogonal polynomials of the generalized Jacobi type as their degree $n$ goes to $\infty$. These are defined on the interval $[-1,1]$ with weight function $w(x)=(1-x)^α(1+x)^βh(x)$, $α,β>-1$ and $h(x)$ a real, analytic and strictly positive function on $[-1,1]$. This information is available in the work of Kuijlaars, McLaughlin, Van Assche and Vanlessen, where the authors use the Riemann--Hilbert formulation and the Deift--Zhou non-linear steepest descent method. We show that computing higher-order terms can be simplified, leading to their efficient construction. The resulting asymptotic expansions in every region of the complex plane are implemented both symbolically and numerically, and the code is made publicly available. The main advantage of these expansions is that they lead to increasing accuracy for increasing degree of the polynomials, at a computational cost that is actually independent of the degree. In contrast, the typical use of the recurrence relation for orthogonal polynomials in computations leads to a cost that is at least linear in the degree. Furthermore, the expansions may be used to compute Gaussian quadrature rules in $\mathcal{O}(n)$ operations, rather than $\mathcal{O}(n^2)$ based on the recurrence relation.
Groebner basis in Boolean rings is not polynomial-space
Venue: arXiv cs.SC 2015
Year: 2015

We give an example where the number of elements of a Groebner basis in a Boolean ring is not polynomially bounded in terms of the bitsize and degrees of the input.
The Spy in the Sandbox -- Practical Cache Attacks in Javascript
Venue: arXiv cs.CR 2015
Year: 2015

We present the first micro-architectural side-channel attack which runs entirely in the browser. In contrast to other works in this genre, this attack does not require the attacker to install any software on the victim's machine -- to facilitate the attack, the victim needs only to browse to an untrusted webpage with attacker-controlled content. This makes the attack model highly scalable and extremely relevant and practical to today's web, especially since most desktop browsers currently accessing the Internet are vulnerable to this attack. Our attack, which is an extension of the last-level cache attacks of Yarom et al., allows a remote adversary recover information belonging to other processes, other users and even other virtual machines running on the same physical host as the victim web browser. We describe the fundamentals behind our attack, evaluate its performance using a high bandwidth covert channel and finally use it to construct a system-wide mouse/network activity logger. Defending against this attack is possible, but the required countermeasures can exact an impractical cost on other benign uses of the web browser and of the computer.
Representative Selection in Non Metric Datasets
Venue: arXiv cs.AI 2015
Year: 2015

This paper considers the problem of representative selection: choosing a subset of data points from a dataset that best represents its overall set of elements. This subset needs to inherently reflect the type of information contained in the entire set, while minimizing redundancy. For such purposes, clustering may seem like a natural approach. However, existing clustering methods are not ideally suited for representative selection, especially when dealing with non-metric data, where only a pairwise similarity measure exists. In this paper we propose $δ$-medoids, a novel approach that can be viewed as an extension to the $k$-medoids algorithm and is specifically suited for sample representative selection from non-metric data. We empirically validate $δ$-medoids in two domains, namely music analysis and motion analysis. We also show some theoretical bounds on the performance of $δ$-medoids and the hardness of representative selection in general.
Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
Venue: arXiv cs.DB 2015
Year: 2015

Differential privacy is a promising privacy-preserving paradigm for statistical query processing over sensitive data. It works by injecting random noise into each query result, such that it is provably hard for the adversary to infer the presence or absence of any individual record from the published noisy results. The main objective in differentially private query processing is to maximize the accuracy of the query results, while satisfying the privacy guarantees. Previous work, notably \cite{LHR+10}, has suggested that with an appropriate strategy, processing a batch of correlated queries as a whole achieves considerably higher accuracy than answering them individually. However, to our knowledge there is currently no practical solution to find such a strategy for an arbitrary query batch; existing methods either return strategies of poor quality (often worse than naive methods) or require prohibitively expensive computations for even moderately large domains. Motivated by this, we propose low-rank mechanism (LRM), the first practical differentially private technique for answering batch linear queries with high accuracy. LRM works for both exact (i.e., $ε$-) and approximate (i.e., ($ε$, $δ$)-) differential privacy definitions. We derive the utility guarantees of LRM, and provide guidance on how to set the privacy parameters given the user's utility expectation. Extensive experiments using real data demonstrate that our proposed method consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins.
Euclidean Distance Matrices: Essential Theory, Algorithms and Applications
Venue: arXiv cs.OH 2015
Year: 2015

Euclidean distance matrices (EDM) are matrices of squared distances between points. The definition is deceivingly simple: thanks to their many useful properties they have found applications in psychometrics, crystallography, machine learning, wireless sensor networks, acoustics, and more. Despite the usefulness of EDMs, they seem to be insufficiently known in the signal processing community. Our goal is to rectify this mishap in a concise tutorial. We review the fundamental properties of EDMs, such as rank or (non)definiteness. We show how various EDM properties can be used to design algorithms for completing and denoising distance data. Along the way, we demonstrate applications to microphone position calibration, ultrasound tomography, room reconstruction from echoes and phase retrieval. By spelling out the essential algorithms, we hope to fast-track the readers in applying EDMs to their own problems. Matlab code for all the described algorithms, and to generate the figures in the paper, is available online. Finally, we suggest directions for further research.
Relaxation-based revision operators in description logics
Venue: arXiv cs.AI 2015
Year: 2015

As ontologies and description logics (DLs) reach out to a broader audience, several reasoning services are developed in this context. Belief revision is one of them, of prime importance when knowledge is prone to change and inconsistency. In this paper we address both the generalization of the well-known AGM postulates, and the definition of concrete and well-founded revision operators in different DL families. We introduce a model-theoretic version of the AGM postulates with a general definition of inconsistency, hence enlarging their scope to a wide family of non-classical logics, in particular negation-free DL families. We propose a general framework for defining revision operators based on the notion of relaxation, introduced recently for defining dissimilarity measures between DL concepts. A revision operator in this framework amounts to relax the set of models of the old belief until it reaches the sets of models of the new piece of knowledge. We demonstrate that such a relaxation-based revision operator defines a faithful assignment and satisfies the generalized AGM postulates. Another important contribution concerns the definition of several concrete relaxation operators suited to the syntax of some DLs (ALC and its fragments EL and ELU).
Detecting Malware with Information Complexity
Venue: arXiv cs.CR 2015
Year: 2015

This work focuses on a specific front of the malware detection arms-race, namely the detection of persistent, disk-resident malware. We exploit normalised compression distance (NCD), an information theoretic measure, applied directly to binaries. Given a zoo of labelled malware and benign-ware, we ask whether a suspect program is more similar to our malware or to our benign-ware. Our approach classifies malware with 97.1% accuracy and a false positive rate of 3%. We achieve our results with off-the-shelf compressors and a standard machine learning classifier and without any specialised knowledge. An end-user need only collect a zoo of malware and benign-ware and then can immediately apply our techniques. We apply statistical rigour to our experiments and our selection of data. We demonstrate that accuracy can be optimised by combining NCD with the compressibility rates of the executables. We demonstrate that malware reported within a more narrow time frame of a few days is more homogenous than malware reported over a longer one of two years but that our method still classifies the latter with 95.2% accuracy and a 5% false positive rate. Due to the use of compression, the time and computation cost of our method is non-trivial. We show that simple approximation techniques can improve the time complexity of our approach by up to 63%. We compare our results to the results of applying the 59 anti-malware programs used on the VirusTotal web site to our malware. Our approach does better than any single one of them as well as the 59 used collectively.
Airborne Ultrasonic Tactile Display Brain-computer Interface -- A Small Robotic Arm Online Control Study
Venue: arXiv cs.HC 2015
Year: 2015

We report on an extended robot control application of a contact-less and airborne ultrasonic tactile display (AUTD) stimulus-based brain-computer interface (BCI) paradigm, which received last year The Annual BCI Research Award 2014. In the award winning human communication augmentation paradigm the six palm positions are used to evoke somatosensory brain responses, in order to define a novel contactless tactile BCI. An example application of a small robot management is also presented in which the users control a small robot online.
Data-Driven Robust Receding Horizon Fault Estimation
Venue: arXiv cs.SY 2015
Year: 2015

This paper presents a data-driven receding horizon fault estimation method for additive actuator and sensor faults in unknown linear time-invariant systems, with enhanced robustness to stochastic identification errors. State-of-the-art methods construct fault estimators with identified state-space models or Markov parameters, but they do not compensate for identification errors. Motivated by this limitation, we first propose a receding horizon fault estimator parameterized by predictor Markov parameters. This estimator provides (asymptotically) unbiased fault estimates as long as the subsystem from faults to outputs has no unstable transmission zeros. When the identified Markov parameters are used to construct the above fault estimator, zero-mean stochastic identification errors appear as model uncertainty multiplied with unknown fault signals and online system inputs/outputs (I/O). Based on this fault estimation error analysis, we formulate a mixed-norm problem for the offline robust design that regards online I/O data as unknown. An alternative online mixed-norm problem is also proposed that can further reduce estimation errors when the online I/O data have large amplitudes, at the cost of increased computational burden. Based on a geometrical interpretation of the two proposed mixed-norm problems, systematic methods to tune the user-defined parameters therein are given to achieve desired performance trade-offs. Simulation examples illustrate the benefits of our proposed methods compared to recent literature.
Second-order Quantile Methods for Experts and Combinatorial Games
Venue: arXiv cs.LG 2015
Year: 2015

We aim to design strategies for sequential decision making that adjust to the difficulty of the learning problem. We study this question both in the setting of prediction with expert advice, and for more general combinatorial decision tasks. We are not satisfied with just guaranteeing minimax regret rates, but we want our algorithms to perform significantly better on easy data. Two popular ways to formalize such adaptivity are second-order regret bounds and quantile bounds. The underlying notions of 'easy data', which may be paraphrased as "the learning problem has small variance" and "multiple decisions are useful", are synergetic. But even though there are sophisticated algorithms that exploit one of the two, no existing algorithm is able to adapt to both. In this paper we outline a new method for obtaining such adaptive algorithms, based on a potential function that aggregates a range of learning rates (which are essential tuning parameters). By choosing the right prior we construct efficient algorithms and show that they reap both benefits by proving the first bounds that are both second-order and incorporate quantiles.
Decentralized Abstractions for Feedback Interconnected Multi-Agent Systems
Venue: arXiv cs.SY 2015
Year: 2015

The purpose of this report is to define abstractions for multi-agent systems under coupled constraints. In the proposed decentralized framework, we specify a finite or countable transition system for each agent which only takes into account the discrete positions of its neighbors. The dynamics of the considered systems consist of two components. An appropriate feedback law which guarantees that certain performance requirements (eg. connectivity) are preserved and induces the coupled constraints and additional free inputs which we exploit in order to accomplish high level tasks. In this work we provide sufficient conditions on the space and time discretization of the system which ensure that we can extract a well posed and hence meaningful finite transition system.
Probabilistic Zero-shot Classification with Semantic Rankings
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we propose a non-metric ranking-based representation of semantic similarity that allows natural aggregation of semantic information from multiple heterogeneous sources. We apply the ranking-based representation to zero-shot learning problems, and present deterministic and probabilistic zero-shot classifiers which can be built from pre-trained classifiers without retraining. We demonstrate their the advantages on two large real-world image datasets. In particular, we show that aggregating different sources of semantic information, including crowd-sourcing, leads to more accurate classification.
DistancePPG: Robust non-contact vital signs monitoring using a camera
Venue: arXiv cs.CV 2015
Year: 2015

Vital signs such as pulse rate and breathing rate are currently measured using contact probes. But, non-contact methods for measuring vital signs are desirable both in hospital settings (e.g. in NICU) and for ubiquitous in-situ health tracking (e.g. on mobile phone and computers with webcams). Recently, camera-based non-contact vital sign monitoring have been shown to be feasible. However, camera-based vital sign monitoring is challenging for people with darker skin tone, under low lighting conditions, and/or during movement of an individual in front of the camera. In this paper, we propose distancePPG, a new camera-based vital sign estimation algorithm which addresses these challenges. DistancePPG proposes a new method of combining skin-color change signals from different tracked regions of the face using a weighted average, where the weights depend on the blood perfusion and incident light intensity in the region, to improve the signal-to-noise ratio (SNR) of camera-based estimate. One of our key contributions is a new automatic method for determining the weights based only on the video recording of the subject. The gains in SNR of camera-based PPG estimated using distancePPG translate into reduction of the error in vital sign estimation, and thus expand the scope of camera-based vital sign monitoring to potentially challenging scenarios. Further, a dataset will be released, comprising of synchronized video recordings of face and pulse oximeter based ground truth recordings from the earlobe for people with different skin tones, under different lighting conditions and for various motion scenarios.