OpenRaiser/Intern-Atlas huggingface dataset:
Compressed Sensing via Universal Denoising and Approximate Message Passing
Venue: arXiv cs.IT 2014
Year: 2014

We study compressed sensing (CS) signal reconstruction problems where an input signal is measured via matrix multiplication under additive white Gaussian noise. Our signals are assumed to be stationary and ergodic, but the input statistics are unknown; the goal is to provide reconstruction algorithms that are universal to the input statistics. We present a novel algorithm that combines: (i) the approximate message passing (AMP) CS reconstruction framework, which converts the matrix channel recovery problem into scalar channel denoising; (ii) a universal denoising scheme based on context quantization, which partitions the stationary ergodic signal denoising into independent and identically distributed (i.i.d.) subsequence denoising; and (iii) a density estimation approach that approximates the probability distribution of an i.i.d. sequence by fitting a Gaussian mixture (GM) model. In addition to the algorithmic framework, we provide three contributions: (i) numerical results showing that state evolution holds for non-separable Bayesian sliding-window denoisers; (ii) a universal denoiser that does not require the input signal to be bounded; and (iii) we modify the GM learning algorithm, and extend it to an i.i.d. denoiser. Our universal CS recovery algorithm compares favorably with existing reconstruction algorithms in terms of both reconstruction quality and runtime, despite not knowing the input statistics of the stationary ergodic signal.
Reachability in succinct one-counter games
Venue: arXiv cs.LO 2014
Year: 2014

We consider the reachability problem on transition systems corresponding to succinct one-counter machines, that is, machines where the counter is incremented or decremented by a value given in binary.
ImpNet: Programming Software-Defied Networks Using Imperative Techniques
Venue: arXiv cs.PL 2014
Year: 2014

Software and hardware components are basic parts of modern networks. However the software compo- nent is typical sealed and function-oriented. Therefore it is very difficult to modify these components. This badly affected networking innovations. Moreover, this resulted in network policies having complex interfaces that are not user-friendly and hence resulted in huge and complicated flow tables on physical switches of networks. This greatly degrades the network performance in many cases. Software-Defined Networks (SDNs) is a modern architecture of networks to overcome issues mentioned above. The idea of SDN is to add to the network a controller device that manages all the other devices on the network including physical switches of the network. One of the main tasks of the managing process is switch learning; achieved via programming physical switches of the network by adding or removing rules for packet-processing to/from switches, more specifically to/from their flow tables. A high-level imperative network programming language, called ImpNet, is presented in this paper. ImpNet enables writing efficient, yet simple, and powerful programs to run on the controller to control all other network devices including switches. ImpNet is compositional, simply-structured, expressive, and more importantly imperative. The syntax of ImpNet together two types of operational semantics to contracts of ImpNet are presented in the paper. The proposed semantics are of the static and dynamic types. Two modern application programmed using ImpNet are shown in the paper as well. The semantics of the applications are shown in the paper also.
Data-driven controller design for nonlinear systems: a two degrees of freedom architecture
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, the D2-IBC (Data-Driven Inversion Based Control) approach for nonlinear control is introduced and analyzed. The method does not require any a-priori knowledge of the system dynamics and relies on a two degrees of freedom scheme, with a nonlinear controller and a linear controller running in parallel. In particular, the former is devoted to stabilize the system around a trajectory of interest, whereas the latter is used to boost the closed-loop performance. The paper also presents a thorough stability and performance analysis of the closed-loop system.
Visualization of Large Volumetric Multi-Channel Microscopy Data Streams on Standard PCs
Venue: arXiv cs.GR 2014
Year: 2014

Background: Visualization of multi-channel microscopy data plays a vital role in biological research. With the ever-increasing resolution of modern microscopes the data set size of the scanned specimen grows steadily. On commodity hardware this size easily exceeds the available main memory and the even more limited GPU memory. Common volume rendering techniques require the entire data set to be present in the GPU memory. Existing out-of-core rendering approaches for large volume data sets either are limited to single-channel volumes, or require a computer cluster, or have long preprocessing times. Results: We introduce a ray-casting technique for rendering large volumetric multi-channel microscopy data streams on commodity hardware. The volumetric data is managed at different levels of detail by an octree structure. In contrast to previous octree-based techniques, the octree is built incrementally and therefore supports streamed microscopy data as well as data set sizes exceeding the available main memory. Furthermore, our approach allows the user to interact with the partially rendered data set at all stages of the octree construction. After a detailed description of our method, we present performance results for different multi-channel data sets with a size of up to 24 GB on a standard desktop PC. Conclusions: Our rendering technique allows biologists to visualize their scanned specimen on their standard desktop computers without high-end hardware requirements. Furthermore, the user can interact with the data set during the initial loading to explore the already loaded parts, change rendering parameters like color maps or adjust clipping planes. Thus, the time of biologists being idle is reduced. Also, streamed data can be visualized to detect and stop flawed scans early during the scan process.
Sequential Data Mining using Correlation Matrix Memory
Venue: arXiv cs.OH 2014
Year: 2014

This paper proposes a method for sequential data mining using correlation matrix memory. Here, we use the concept of the Logical Match to mine the indices of the sequential pattern. We demonstrate the uniqueness of the method with both the artificial and the real datum taken from NCBI databank.
$LCSk$++: Practical similarity metric for long strings
Venue: arXiv cs.DS 2014
Year: 2014

In this paper we present $LCSk$++: a new metric for measuring the similarity of long strings, and provide an algorithm for its efficient computation. With ever increasing size of strings occuring in practice, e.g. large genomes of plants and animals, classic algorithms such as Longest Common Subsequence (LCS) fail due to demanding computational complexity. Recently, Benson et al. defined a similarity metric named $LCSk$. By relaxing the requirement that the $k$-length substrings should not overlap, we extend their definition into a new metric. An efficient algorithm is presented which computes $LCSk$++ with complexity of $O((|X|+|Y|)\log(|X|+|Y|))$ for strings $X$ and $Y$ under a realistic random model. The algorithm has been designed with implementation simplicity in mind. Additionally, we describe how it can be adjusted to compute $LCSk$ as well, which gives an improvement of the $O(|X|\dot|Y|)$ algorithm presented in the original $LCSk$ paper.
Designing and implementing the logical security framework for e-commerce based on service oriented architecture
Venue: arXiv cs.CR 2014
Year: 2014

Rapid evolution of information technology has contributed to the evolution of more sophisticated E- commerce system with the better transaction time and protection. The currently used E-commerce models lack in quality properties such as logical security because of their poor designing and to face the highly equipped and trained intruders. This editorial proposed a security framework for small and medium sized E-commerce, based on service oriented architecture and gives an analysis of the eminent security attacks which can be averted. The proposed security framework will be implemented and validated on an open source E-commerce, and the results achieved so far are also presented.
Coding Together at Scale: GitHub as a Collaborative Social Network
Venue: arXiv cs.SI 2014
Year: 2014

GitHub is the most popular repository for open source code. It has more than 3.5 million users, as the company declared in April 2013, and more than 10 million repositories, as of December 2013. It has a publicly accessible API and, since March 2012, it also publishes a stream of all the events occurring on public projects. Interactions among GitHub users are of a complex nature and take place in different forms. Developers create and fork repositories, push code, approve code pushed by others, bookmark their favorite projects and follow other developers to keep track of their activities. In this paper we present a characterization of GitHub, as both a social network and a collaborative platform. To the best of our knowledge, this is the first quantitative study about the interactions happening on GitHub. We analyze the logs from the service over 18 months (between March 11, 2012 and September 11, 2013), describing 183.54 million events and we obtain information about 2.19 million users and 5.68 million repositories, both growing linearly in time. We show that the distributions of the number of contributors per project, watchers per project and followers per user show a power-law-like shape. We analyze social ties and repository-mediated collaboration patterns, and we observe a remarkably low level of reciprocity of the social connections. We also measure the activity of each user in terms of authored events and we observe that very active users do not necessarily have a large number of followers. Finally, we provide a geographic characterization of the centers of activity and we investigate how distance influences collaboration.
Recent Symbolic Summation Methods to Solve Coupled Systems of Differential and Difference Equations
Venue: arXiv cs.SC 2014
Year: 2014

We outline a new algorithm to solve coupled systems of differential equations in one continuous variable $x$ (resp. coupled difference equations in one discrete variable $N$) depending on a small parameter $ε$: given such a system and given sufficiently many initial values, we can determine the first coefficients of the Laurent-series solutions in $ε$ if they are expressible in terms of indefinite nested sums and products. This systematic approach is based on symbolic summation algorithms in the context of difference rings/fields and uncoupling algorithms. The proposed method gives rise to new interesting applications in connection with integration by parts (IBP) methods. As an illustrative example, we will demonstrate how one can calculate the $ε$-expansion of a ladder graph with 6 massive fermion lines.
Classifying Fonts and Calligraphy Styles Using Complex Wavelet Transform
Venue: arXiv cs.CV 2014
Year: 2014

Recognizing fonts has become an important task in document analysis, due to the increasing number of available digital documents in different fonts and emphases. A generic font-recognition system independent of language, script and content is desirable for processing various types of documents. At the same time, categorizing calligraphy styles in handwritten manuscripts is important for palaeographic analysis, but has not been studied sufficiently in the literature. We address the font-recognition problem as analysis and categorization of textures. We extract features using complex wavelet transform and use support vector machines for classification. Extensive experimental evaluations on different datasets in four languages and comparisons with state-of-the-art studies show that our proposed method achieves higher recognition accuracy while being computationally simpler. Furthermore, on a new dataset generated from Ottoman manuscripts, we show that the proposed method can also be used for categorizing Ottoman calligraphy with high accuracy.
A multi-instance learning algorithm based on a stacked ensemble of lazy learners
Venue: arXiv cs.LG 2014
Year: 2014

This document describes a novel learning algorithm that classifies "bags" of instances rather than individual instances. A bag is labeled positive if it contains at least one positive instance (which may or may not be specifically identified), and negative otherwise. This class of problems is known as multi-instance learning problems, and is useful in situations where the class label at an instance level may be unavailable or imprecise or difficult to obtain, or in situations where the problem is naturally posed as one of classifying instance groups. The algorithm described here is an ensemble-based method, wherein the members of the ensemble are lazy learning classifiers learnt using the Citation Nearest Neighbour method. Diversity among the ensemble members is achieved by optimizing their parameters using a multi-objective optimization method, with the objectives being to maximize Class 1 accuracy and minimize false positive rate. The method has been found to be effective on the Musk1 benchmark dataset.
What you need to know about the state-of-the-art computational models of object-vision: A tour through the models
Venue: arXiv cs.CV 2014
Year: 2014

Models of object vision have been of great interest in computer vision and visual neuroscience. During the last decades, several models have been developed to extract visual features from images for object recognition tasks. Some of these were inspired by the hierarchical structure of primate visual system, and some others were engineered models. The models are varied in several aspects: models that are trained by supervision, models trained without supervision, and models (e.g. feature extractors) that are fully hard-wired and do not need training. Some of the models come with a deep hierarchical structure consisting of several layers, and some others are shallow and come with only one or two layers of processing. More recently, new models have been developed that are not hand-tuned but trained using millions of images, through which they learn how to extract informative task-related features. Here I will survey all these different models and provide the reader with an intuitive, as well as a more detailed, understanding of the underlying computations in each of the models.
Learning Valuation Distributions from Partial Observation
Venue: arXiv cs.GT 2014
Year: 2014

Auction theory traditionally assumes that bidders' valuation distributions are known to the auctioneer, such as in the celebrated, revenue-optimal Myerson auction. However, this theory does not describe how the auctioneer comes to possess this information. Recently, Cole and Roughgarden [2014] showed that an approximation based on a finite sample of independent draws from each bidder's distribution is sufficient to produce a near-optimal auction. In this work, we consider the problem of learning bidders' valuation distributions from much weaker forms of observations. Specifically, we consider a setting where there is a repeated, sealed-bid auction with $n$ bidders, but all we observe for each round is who won, but not how much they bid or paid. We can also participate (i.e., submit a bid) ourselves, and observe when we win. From this information, our goal is to (approximately) recover the inherently recoverable part of the underlying bid distributions. We also consider extensions where different subsets of bidders participate in each round, and where bidders' valuations have a common-value component added to their independent private values.
Understanding Co-evolution in Large Multi-relational Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Understanding dynamics of evolution in large social networks is an important problem. In this paper, we characterize evolution in large multi-relational social networks. The proliferation of online media such as Twitter, Facebook, Orkut and MMORPGs\footnote{Massively Multi-player Online Role Playing Games} have created social networking data at an unprecedented scale. Sony's Everquest 2 is one such example. We used game multi-relational networks to reveal the dynamics of evolution in a multi-relational setting by macroscopic study of the game network. Macroscopic analysis involves fragmenting the network into smaller portions for studying the dynamics within these sub-networks, referred to as `communities'. From an evolutionary perspective of multi-relational network analysis, we have made the following contributions. Specifically, we formulated and analyzed various metrics to capture evolutionary properties of networks. We find that co-evolution rates in trust based `communities' are approximately $60\%$ higher than the trade based `communities'. We also find that the trust and trade connections within the `communities' reduce as their size increases. Finally, we study the interrelation between the dynamics of trade and trust within `communities' and find interesting results about the precursor relationship between the trade and the trust dynamics within the `communities'.
Run-time extensibility and librarization of simulation software
Venue: arXiv cs.SE 2014
Year: 2014

Build-time configuration and environment assumptions are hampering progress and usability in scientific software. That which would be utterly unacceptable in non-scientific software somehow passes for the norm in scientific packages. The community needs reusable software packages that are easy use and flexible enough to accommodate next-generation simulation and analysis demands.
Approximate Range Emptiness in Constant Time and Optimal Space
Venue: arXiv cs.DS 2014
Year: 2014

This paper studies the \emph{$\varepsilon$-approximate range emptiness} problem, where the task is to represent a set $S$ of $n$ points from $\{0,\ldots,U-1\}$ and answer emptiness queries of the form "$[a ; b]\cap S \neq \emptyset$ ?" with a probability of \emph{false positives} allowed. This generalizes the functionality of \emph{Bloom filters} from single point queries to any interval length $L$. Setting the false positive rate to $\varepsilon/L$ and performing $L$ queries, Bloom filters yield a solution to this problem with space $O(n \lg(L/\varepsilon))$ bits, false positive probability bounded by $\varepsilon$ for intervals of length up to $L$, using query time $O(L \lg(L/\varepsilon))$. Our first contribution is to show that the space/error trade-off cannot be improved asymptotically: Any data structure for answering approximate range emptiness queries on intervals of length up to $L$ with false positive probability $\varepsilon$, must use space $Ω(n \lg(L/\varepsilon)) - O(n)$ bits. On the positive side we show that the query time can be improved greatly, to constant time, while matching our space lower bound up to a lower order additive term. This result is achieved through a succinct data structure for (non-approximate 1d) range emptiness/reporting queries, which may be of independent interest.
Increasing the Speed of Polar List Decoders
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we present a simplified successive cancellation list decoder that uses a Chase-like decoding process to achieve a six time improvement in speed compared to successive cancellation list decoding while maintaining the same error-correction performance advantage over standard successive-cancellation polar decoders. We discuss the algorithm and detail the data structures and methods used to obtain this speed-up. We also propose an adaptive decoding algorithm that significantly improves the throughput while retaining the error-correction performance. Simulation results over the additive white Gaussian noise channel are provided and show that the proposed system is up to 16 times faster than an LDPC decoder of the same frame size, code rate, and similar error-correction performance, making it more suitable for use as a software decoding solution.
FAME: Face Association through Model Evolution
Venue: arXiv cs.CV 2014
Year: 2014

We attack the problem of learning face models for public faces from weakly-labelled images collected from web through querying a name. The data is very noisy even after face detection, with several irrelevant faces corresponding to other people. We propose a novel method, Face Association through Model Evolution (FAME), that is able to prune the data in an iterative way, for the face models associated to a name to evolve. The idea is based on capturing discriminativeness and representativeness of each instance and eliminating the outliers. The final models are used to classify faces on novel datasets with possibly different characteristics. On benchmark datasets, our results are comparable to or better than state-of-the-art studies for the task of face identification.
A Proposed Infrastructure for Adding Online Interaction to Any Evolutionary Domain
Venue: arXiv cs.NE 2014
Year: 2014

To address the difficulty of creating online collaborative evolutionary systems, this paper presents a new prototype library called Worldwide Infrastructure for Neuroevolution (WIN) and its accompanying site WIN Online (http://winark.org/). The WIN library is a collection of software packages built on top of Node.js that reduce the complexity of creating fully persistent, online, and interactive (or automated) evolutionary platforms around any domain. WIN Online is the public interface for WIN, providing an online collection of domains built with the WIN library that lets novice and expert users browse and meaningfully contribute to ongoing experiments. The long term goal of WIN is to make it trivial to connect any platform to the world, providing both a stream of online users, and archives of data and discoveries for later extension by humans or computers.
Approximate well-supported Nash equilibria in symmetric bimatrix games
Venue: arXiv cs.GT 2014
Year: 2014

The $\varepsilon$-well-supported Nash equilibrium is a strong notion of approximation of a Nash equilibrium, where no player has an incentive greater than $\varepsilon$ to deviate from any of the pure strategies that she uses in her mixed strategy. The smallest constant $\varepsilon$ currently known for which there is a polynomial-time algorithm that computes an $\varepsilon$-well-supported Nash equilibrium in bimatrix games is slightly below $2/3$. In this paper we study this problem for symmetric bimatrix games and we provide a polynomial-time algorithm that gives a $(1/2+δ)$-well-supported Nash equilibrium, for an arbitrarily small positive constant $δ$.
The Need for a Versioned Data Analysis Software Environment
Venue: arXiv cs.SE 2014
Year: 2014

Scientific results in high-energy physics and in many other fields often rely on complex software stacks. In order to support reproducibility and scrutiny of the results, it is good practice to use open source software and to cite software packages and versions. With ever-growing complexity of scientific software on one side and with IT life-cycles of only a few years on the other side, however, it turns out that despite source code availability the setup and the validation of a minimal usable analysis environment can easily become prohibitively expensive. We argue that there is a substantial gap between merely having access to versioned source code and the ability to create a data analysis runtime environment. In order to preserve all the different variants of the data analysis runtime environment, we developed a snapshotting file system optimized for software distribution. We report on our experience in preserving the analysis environment for high-energy physics such as the software landscape used to discover the Higgs boson at the Large Hadron Collider.