OpenRaiser/Intern-Atlas huggingface dataset:
Minfer: Inferring Motif Statistics From Sampled Edges
Venue: arXiv cs.SI 2015
Year: 2015

Characterizing motif (i.e., locally connected subgraph patterns) statistics is important for understanding complex networks such as online social networks and communication networks. Previous work made the strong assumption that the graph topology of interest is known, and that the dataset either fits into main memory or stored on disks such that it is not expensive to obtain all neighbors of any given node. In practice, researchers have to deal with the situation where the graph topology is unknown, either because the graph is dynamic, or because it is expensive to collect and store all topological and meta information on disk. Hence, what is available to researchers is only a snapshot of the graph generated by sampling edges from the graph at random, which we called a "RESampled graph". Clearly, a RESampled graph's motif statistics may be quite different from the underlying original graph. To solve this challenge, we propose a framework and implement a system called Minfer, which can take the given RESampled graph and accurately infer the underlying graph's motif statistics. We also use Fisher information to bound the error of our estimates. Experiments using large scale datasets show that our method to be accurate.
On the Multiple Threshold Decoding of LDPC codes over GF(q)
Venue: arXiv cs.IT 2015
Year: 2015

We consider the decoding of LDPC codes over GF(q) with the low-complexity majority algorithm from [1]. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time the transition to multiple thresholds does not affect the order of complexity.
On Reducing Linearizability to State Reachability
Venue: arXiv cs.LO 2015
Year: 2015

Efficient implementations of atomic objects such as concurrent stacks and queues are especially susceptible to programming errors, and necessitate automatic verification. Unfortunately their correctness criteria - linearizability with respect to given ADT specifications - are hard to verify. Even on classes of implementations where the usual temporal safety properties like control-state reachability are decidable, linearizability is undecidable. In this work we demonstrate that verifying linearizability for certain fixed ADT specifications is reducible to control-state reachability, despite being harder for arbitrary ADTs. We effectuate this reduction for several of the most popular atomic objects. This reduction yields the first decidability results for verification without bounding the number of concurrent threads. Furthermore, it enables the application of existing safety-verification tools to linearizability verification.
Web-scale Surface and Syntactic n-gram Features for Dependency Parsing
Venue: arXiv cs.CL 2015
Year: 2015

We develop novel first- and second-order features for dependency parsing based on the Google Syntactic Ngrams corpus, a collection of subtree counts of parsed sentences from scanned books. We also extend previous work on surface $n$-gram features from Web1T to the Google Books corpus and from first-order to second-order, comparing and analysing performance over newswire and web treebanks. Surface and syntactic $n$-grams both produce substantial and complementary gains in parsing accuracy across domains. Our best system combines the two feature sets, achieving up to 0.8% absolute UAS improvements on newswire and 1.4% on web text.
Recharging Probably Keeps Batteries Alive
Venue: arXiv cs.SY 2015
Year: 2015

The kinetic battery model is a popular model of the dynamic behavior of a conventional battery, useful to predict or optimize the time until battery depletion. The model however lacks certain obvious aspects of batteries in-the-wild, especially with respect to (i) the effects of random influences and (ii) the behavior when charging up to capacity bounds. This paper considers the kinetic battery model with bounded capacity in the context of piecewise constant yet random charging and discharging. The resulting model enables the time-dependent evaluation of the risk of battery depletion. This is exemplified in a power dependability study of a nano satellite mission.
High-Speed Query Processing over High-Speed Networks
Venue: arXiv cs.DB 2015
Year: 2015

Modern database clusters entail two levels of networks: connecting CPUs and NUMA regions inside a single server in the small and multiple servers in the large. The huge performance gap between these two types of networks used to slow down distributed query processing to such an extent that a cluster of machines actually performed worse than a single many-core server. The increased main-memory capacity of the cluster remained the sole benefit of such a scale-out. The economic viability of high-speed interconnects such as InfiniBand has narrowed this performance gap considerably. However, InfiniBand's higher network bandwidth alone does not improve query performance as expected when the distributed query engine is left unchanged. The scalability of distributed query processing is impaired by TCP overheads, switch contention due to uncoordinated communication, and load imbalances resulting from the inflexibility of the classic exchange operator model. This paper presents the blueprint for a distributed query engine that addresses these problems by considering both levels of networks holistically. It consists of two parts: First, hybrid parallelism that distinguishes local and distributed parallelism for better scalability in both the number of cores as well as servers. Second, a novel communication multiplexer tailored for analytical database workloads using remote direct memory access (RDMA) and low-latency network scheduling for high-speed communication with almost no CPU overhead. An extensive evaluation within the HyPer database system using the TPC-H benchmark shows that our holistic approach indeed enables high-speed query processing over high-speed networks.
Automata and Graph Compression
Venue: arXiv cs.IT 2015
Year: 2015

We present a theoretical framework for the compression of automata, which are widely used in speech processing and other natural language processing tasks. The framework extends to graph compression. Similar to stationary ergodic processes, we formulate a probabilistic process of graph and automata generation that captures real world phenomena and provide a universal compression scheme LZA for this probabilistic model. Further, we show that LZA significantly outperforms other compression techniques such as gzip and the UNIX compress command for several synthetic and real data sets.
Rational fuzzy attribute logic
Venue: arXiv cs.LO 2015
Year: 2015

We present a logic for reasoning with if-then formulas which involve constants for rational truth degrees from the unit interval. We introduce graded semantic and syntactic entailment of formulas. We prove the logic is complete in Pavelka style and depending on the choice of structure of truth degrees, the logic is a decidable fragment of the Rational Pavelka logic (RPL) or the Rational Product Logic (RΠL). We also present a characterization of the entailment based on least models and study related closure structures.
Improved Approximation Algorithms for k-Submodular Function Maximization
Venue: arXiv cs.DS 2015
Year: 2015

This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $\max\{1/3, 1/(1+a)\}$-approximation by Ward and Živný~(SODA'14), where $a=\max\{1, \sqrt{(k-1)/4}\}$. We also show that for monotone $k$-submodular functions there is a polynomial-time $k/(2k-1)$-approximation algorithm while for any $\varepsilon>0$ a $((k+1)/2k+\varepsilon)$-approximation algorithm for maximizing monotone $k$-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.
Learning Depth from Single Monocular Images Using Deep Convolutional Neural Fields
Venue: arXiv cs.CV 2015
Year: 2015

In this article, we tackle the problem of depth estimation from single monocular images. Compared with depth estimation using multiple images such as stereo depth perception, depth from monocular images is much more challenging. Prior work typically focuses on exploiting geometric priors or additional sources of information, most using hand-crafted features. Recently, there is mounting evidence that features from deep convolutional neural networks (CNN) set new records for various vision applications. On the other hand, considering the continuous characteristic of the depth values, depth estimations can be naturally formulated as a continuous conditional random field (CRF) learning problem. Therefore, here we present a deep convolutional neural field model for estimating depths from single monocular images, aiming to jointly explore the capacity of deep CNN and continuous CRF. In particular, we propose a deep structured learning scheme which learns the unary and pairwise potentials of continuous CRF in a unified deep CNN framework. We then further propose an equally effective model based on fully convolutional networks and a novel superpixel pooling method, which is $\sim 10$ times faster, to speedup the patch-wise convolutions in the deep model. With this more efficient model, we are able to design deeper networks to pursue better performance. Experiments on both indoor and outdoor scene datasets demonstrate that the proposed method outperforms state-of-the-art depth estimation approaches.
Automatic Optimization of Hardware Accelerators for Image Processing
Venue: arXiv cs.PL 2015
Year: 2015

In the domain of image processing, often real-time constraints are required. In particular, in safety-critical applications, such as X-ray computed tomography in medical imaging or advanced driver assistance systems in the automotive domain, timing is of utmost importance. A common approach to maintain real-time capabilities of compute-intensive applications is to offload those computations to dedicated accelerator hardware, such as Field Programmable Gate Arrays (FPGAs). Programming such architectures is a challenging task, with respect to the typical FPGA-specific design criteria: Achievable overall algorithm latency and resource usage of FPGA primitives (BRAM, FF, LUT, and DSP). High-Level Synthesis (HLS) dramatically simplifies this task by enabling the description of algorithms in well-known higher languages (C/C++) and its automatic synthesis that can be accomplished by HLS tools. However, algorithm developers still need expert knowledge about the target architecture, in order to achieve satisfying results. Therefore, in previous work, we have shown that elevating the description of image algorithms to an even higher abstraction level, by using a Domain-Specific Language (DSL), can significantly cut down the complexity for designing such algorithms for FPGAs. To give the developer even more control over the common trade-off, latency vs. resource usage, we will present an automatic optimization process where these criteria are analyzed and fed back to the DSL compiler, in order to generate code that is closer to the desired design specifications. Finally, we generate code for stereo block matching algorithms and compare it with handwritten implementations to quantify the quality of our results.
Generation and Validation of Custom Multiplication IP Blocks from the Web
Venue: arXiv cs.AR 2015
Year: 2015

Every CPU carries one or more arithmetical and logical units. One popular operation that is performed by these units is multiplication. Automatic generation of custom VHDL models for performing this operation, allows the designer to achieve a time efficient design space exploration. Although these units are heavily utilized in modern digital circuits and DSP, there is no tool, accessible from the web, to generate the HDL description of such designs for arbitrary and different input bitwidths. In this paper, we present our web accessible tool to construct completely custom optimized multiplication units together with random generated test vectors for their verification. Our novel tool is one of the firsts web based EDA tools to automate the design of such units and simultaneously provide custom testbenches to verify their correctness. Our synthesized circuits on Xilinx Virtex 6 FPGA, operate up to 589 Mhz.
A hypothesize-and-verify framework for Text Recognition using Deep Recurrent Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Deep LSTM is an ideal candidate for text recognition. However text recognition involves some initial image processing steps like segmentation of lines and words which can induce error to the recognition system. Without segmentation, learning very long range context is difficult and becomes computationally intractable. Therefore, alternative soft decisions are needed at the pre-processing level. This paper proposes a hybrid text recognizer using a deep recurrent neural network with multiple layers of abstraction and long range context along with a language model to verify the performance of the deep neural network. In this paper we construct a multi-hypotheses tree architecture with candidate segments of line sequences from different segmentation algorithms at its different branches. The deep neural network is trained on perfectly segmented data and tests each of the candidate segments, generating unicode sequences. In the verification step, these unicode sequences are validated using a sub-string match with the language model and best first search is used to find the best possible combination of alternative hypothesis from the tree structure. Thus the verification framework using language models eliminates wrong segmentation outputs and filters recognition errors.
Sampling Sparse Signals on the Sphere: Algorithms and Applications
Venue: arXiv cs.IT 2015
Year: 2015

We propose a sampling scheme that can perfectly reconstruct a collection of spikes on the sphere from samples of their lowpass-filtered observations. Central to our algorithm is a generalization of the annihilating filter method, a tool widely used in array signal processing and finite-rate-of-innovation (FRI) sampling. The proposed algorithm can reconstruct $K$ spikes from $(K+\sqrt{K})^2$ spatial samples. This sampling requirement improves over previously known FRI sampling schemes on the sphere by a factor of four for large $K$. We showcase the versatility of the proposed algorithm by applying it to three different problems: 1) sampling diffusion processes induced by localized sources on the sphere, 2) shot noise removal, and 3) sound source localization (SSL) by a spherical microphone array. In particular, we show how SSL can be reformulated as a spherical sparse sampling problem.
Incentive Mechanisms for Participatory Sensing: Survey and Research Challenges
Venue: arXiv cs.GT 2015
Year: 2015

Participatory sensing is a powerful paradigm which takes advantage of smartphones to collect and analyze data beyond the scale of what was previously possible. Given that participatory sensing systems rely completely on the users' willingness to submit up-to-date and accurate information, it is paramount to effectively incentivize users' active and reliable participation. In this paper, we survey existing literature on incentive mechanisms for participatory sensing systems. In particular, we present a taxonomy of existing incentive mechanisms for participatory sensing systems, which are subsequently discussed in depth by comparing and contrasting different approaches. Finally, we discuss an agenda of open research challenges in incentivizing users in participatory sensing.
GREAT Process Modeller user manual
Venue: arXiv cs.OH 2015
Year: 2015

This report contains instructions to install, uninstall and use GREAT Process Modeller, a tool that supports Communication Analysis, a communication-oriented business process modelling method. GREAT allows creating communicative event diagrams (i.e. business process models), specifying message structures (which describe the messages associated to each communicative event), and automatically generating a class diagram (representing the data model of an information system that would support such organisational communication). This report briefly describes the methodological background of the tool. This handbook explains the modelling techniques in detail: España, S., A. González, Ó. Pastor and M. Ruiz (2012). Communication Analysis modelling techniques. Technical report ProS-TR-2012-02, PROS Research Centre, Universitat Politècnica de València, Spain, arXiv:1205.0987.
Globally Optimal Crowdsourcing Quality Management
Venue: arXiv cs.OH 2015
Year: 2015

We study crowdsourcing quality management, that is, given worker responses to a set of tasks, our goal is to jointly estimate the true answers for the tasks, as well as the quality of the workers. Prior work on this problem relies primarily on applying Expectation-Maximization (EM) on the underlying maximum likelihood problem to estimate true answers as well as worker quality. Unfortunately, EM only provides a locally optimal solution rather than a globally optimal one. Other solutions to the problem (that do not leverage EM) fail to provide global optimality guarantees as well. In this paper, we focus on filtering, where tasks require the evaluation of a yes/no predicate, and rating, where tasks elicit integer scores from a finite domain. We design algorithms for finding the global optimal estimates of correct task answers and worker quality for the underlying maximum likelihood problem, and characterize the complexity of these algorithms. Our algorithms conceptually consider all mappings from tasks to true answers (typically a very large number), leveraging two key ideas to reduce, by several orders of magnitude, the number of mappings under consideration, while preserving optimality. We also demonstrate that these algorithms often find more accurate estimates than EM-based algorithms. This paper makes an important contribution towards understanding the inherent complexity of globally optimal crowdsourcing quality management.
Product Measure Approximation of Symmetric Graph Properties
Venue: arXiv cs.DM 2015
Year: 2015

In the study of random structures we often face a trade-off between realism and tractability, the latter typically enabled by assuming some form of independence. In this work we initiate an effort to bridge this gap by developing tools that allow us to work with independence without assuming it. Let $\mathcal{G}_{n}$ be the set of all graphs on $n$ vertices and let $S$ be an arbitrary subset of $\mathcal{G}_{n}$, e.g., the set of graphs with $m$ edges. The study of random networks can be seen as the study of properties that are true for most elements of $S$, i.e., that are true with high probability for a uniformly random element of $S$. With this in mind, we pursue the following question: What are general sufficient conditions for the uniform measure on a set of graphs $S \subseteq \mathcal{G}_{n}$ to be approximable by a product measure?
Modelling Local Deep Convolutional Neural Network Features to Improve Fine-Grained Image Classification
Venue: arXiv cs.CV 2015
Year: 2015

We propose a local modelling approach using deep convolutional neural networks (CNNs) for fine-grained image classification. Recently, deep CNNs trained from large datasets have considerably improved the performance of object recognition. However, to date there has been limited work using these deep CNNs as local feature extractors. This partly stems from CNNs having internal representations which are high dimensional, thereby making such representations difficult to model using stochastic models. To overcome this issue, we propose to reduce the dimensionality of one of the internal fully connected layers, in conjunction with layer-restricted retraining to avoid retraining the entire network. The distribution of low-dimensional features obtained from the modified layer is then modelled using a Gaussian mixture model. Comparative experiments show that considerable performance improvements can be achieved on the challenging Fish and UEC FOOD-100 datasets.
DAWN: Delay-Aware Wi-Fi Offloading and Network Selection
Venue: arXiv cs.NI 2015
Year: 2015

To accommodate the explosive growth in mobile data traffic, both mobile cellular operators and mobile users are increasingly interested in offloading the traffic from cellular networks to Wi-Fi networks. However, previously proposed offloading schemes mainly focus on reducing the cellular data usage, without paying too much attention on the quality of service (QoS) requirements of the applications. In this paper, we study the Wi-Fi offloading problem with delay-tolerant applications under usage-based pricing. We aim to achieve a good tradeoff between the user's payment and its QoS characterized by the file transfer deadline. We first propose a general Delay-Aware Wi-Fi Offloading and Network Selection (DAWN) algorithm for a general single-user decision scenario. We then analytically establish the sufficient conditions, under which the optimal policy exhibits a threshold structure in terms of both the time and file size. As a result, we propose a monotone DAWN algorithm that approximately solves the general offloading problem, and has a much lower computational complexity comparing to the optimal algorithm. Simulation results show that both the general and monotone DAWN schemes achieve a high probability of completing file transfer under a stringent deadline, and require the lowest payment under a non-stringent deadline as compared with three heuristic schemes.
Expressiveness of the modal mu-calculus on monotone neighborhood structures
Venue: arXiv cs.LO 2015
Year: 2015

We characterize the expressive power of the modal mu-calculus on monotone neighborhood structures, in the style of the Janin-Walukiewicz theorem for the standard modal mu-calculus. For this purpose we consider a monadic second-order logic for monotone neighborhood structures. Our main result shows that the monotone modal mu-calculus corresponds exactly to the fragment of this second-order language that is invariant for neighborhood bisimulations.
Combinatorial approximation of maximum $k$-vertex cover in bipartite graphs within ratio~0.7
Venue: arXiv cs.DS 2015
Year: 2015

We propose a \textit{purely combinatorial algorithm} for \mkvc{} in bipartite graphs, achieving approximation ratio~0.7. The only combinatorial algorithms currently known until now for this problem are the natural greedy algorithm, that achieves ratio 0.632, and an easy~$2/3$-approximation algorithm presented in \cite{DBLP:journals/corr/BonnetEPS14}.
Non-stochastic Best Arm Identification and Hyperparameter Optimization
Venue: arXiv cs.LG 2015
Year: 2015

Motivated by the task of hyperparameter optimization, we introduce the non-stochastic best-arm identification problem. Within the multi-armed bandit literature, the cumulative regret objective enjoys algorithms and analyses for both the non-stochastic and stochastic settings while to the best of our knowledge, the best-arm identification framework has only been considered in the stochastic setting. We introduce the non-stochastic setting under this framework, identify a known algorithm that is well-suited for this setting, and analyze its behavior. Next, by leveraging the iterative nature of standard machine learning algorithms, we cast hyperparameter optimization as an instance of non-stochastic best-arm identification, and empirically evaluate our proposed algorithm on this task. Our empirical results show that, by allocating more resources to promising hyperparameter settings, we typically achieve comparable test accuracies an order of magnitude faster than baseline methods.