OpenRaiser/Intern-Atlas huggingface dataset:
A Waterfilling Algorithm for Multiple Access Point Connectivity with Constrained Backhaul Network
Venue: arXiv cs.IT 2015
Year: 2015

The 4G/5G paradigm offers User Equipment (UE) simultaneous connectivity to a plurality of wireless Access Points (APs). We consider a UE communicating with its destination through multiple uplinks operating on orthogonal wireless channels with unequal bandwidth. The APs are connected via a tree-like backhaul network with destination at the root and non-ideal link capacities. We develop a power allocation scheme that achieves a near-optimal rate without explicit knowledge of the backhaul network topology at transmitter side. The proposed algorithm waterfills a dynamic subset of uplinks using a low-overhead backhaul load feedback.
Verification and Control of Partially Observable Probabilistic Real-Time Systems
Venue: arXiv cs.LO 2015
Year: 2015

We propose automated techniques for the verification and control of probabilistic real-time systems that are only partially observable. To formally model such systems, we define an extension of probabilistic timed automata in which local states are partially visible to an observer or controller. We give a probabilistic temporal logic that can express a range of quantitative properties of these models, relating to the probability of an event's occurrence or the expected value of a reward measure. We then propose techniques to either verify that such a property holds or to synthesise a controller for the model which makes it true. Our approach is based on an integer discretisation of the model's dense-time behaviour and a grid-based abstraction of the uncountable belief space induced by partial observability. The latter is necessarily approximate since the underlying problem is undecidable, however we show how both lower and upper bounds on numerical results can be generated. We illustrate the effectiveness of the approach by implementing it in the PRISM model checker and applying it to several case studies, from the domains of computer security and task scheduling.
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
Venue: arXiv cs.DS 2015
Year: 2015

A hypergraph is said to be $χ$-colorable if its vertices can be colored with $χ$ colors so that no hyperedge is monochromatic. $2$-colorability is a fundamental property (called Property B) of hypergraphs and is extensively studied in combinatorics. Algorithmically, however, given a $2$-colorable $k$-uniform hypergraph, it is NP-hard to find a $2$-coloring miscoloring fewer than a fraction $2^{-k+1}$ of hyperedges (which is achieved by a random $2$-coloring), and the best algorithms to color the hypergraph properly require $\approx n^{1-1/k}$ colors, approaching the trivial bound of $n$ as $k$ increases. In this work, we study the complexity of approximate hypergraph coloring, for both the maximization (finding a $2$-coloring with fewest miscolored edges) and minimization (finding a proper coloring using fewest number of colors) versions, when the input hypergraph is promised to have the following stronger properties than $2$-colorability: (A) Low-discrepancy: If the hypergraph has discrepancy $\ell \ll \sqrt{k}$, we give an algorithm to color the it with $\approx n^{O(\ell^2/k)}$ colors. However, for the maximization version, we prove NP-hardness of finding a $2$-coloring miscoloring a smaller than $2^{-O(k)}$ (resp. $k^{-O(k)}$) fraction of the hyperedges when $\ell = O(\log k)$ (resp. $\ell=2$). Assuming the UGC, we improve the latter hardness factor to $2^{-O(k)}$ for almost discrepancy-$1$ hypergraphs. (B) Rainbow colorability: If the hypergraph has a $(k-\ell)$-coloring such that each hyperedge is polychromatic with all these colors, we give a $2$-coloring algorithm that miscolors at most $k^{-Ω(k)}$ of the hyperedges when $\ell \ll \sqrt{k}$, and complement this with a matching UG hardness result showing that when $\ell =\sqrt{k}$, it is hard to even beat the $2^{-k+1}$ bound achieved by a random coloring.
DeepOrgan: Multi-level Deep Convolutional Networks for Automated Pancreas Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Automatic organ segmentation is an important yet challenging problem for medical image analysis. The pancreas is an abdominal organ with very high anatomical variability. This inhibits previous segmentation methods from achieving high accuracies, especially compared to other organs such as the liver, heart or kidneys. In this paper, we present a probabilistic bottom-up approach for pancreas segmentation in abdominal computed tomography (CT) scans, using multi-level deep convolutional networks (ConvNets). We propose and evaluate several variations of deep ConvNets in the context of hierarchical, coarse-to-fine classification on image patches and regions, i.e. superpixels. We first present a dense labeling of local image patches via $P{-}\mathrm{ConvNet}$ and nearest neighbor fusion. Then we describe a regional ConvNet ($R_1{-}\mathrm{ConvNet}$) that samples a set of bounding boxes around each image superpixel at different scales of contexts in a "zoom-out" fashion. Our ConvNets learn to assign class probabilities for each superpixel region of being pancreas. Last, we study a stacked $R_2{-}\mathrm{ConvNet}$ leveraging the joint space of CT intensities and the $P{-}\mathrm{ConvNet}$ dense probability maps. Both 3D Gaussian smoothing and 2D conditional random fields are exploited as structured predictions for post-processing. We evaluate on CT images of 82 patients in 4-fold cross-validation. We achieve a Dice Similarity Coefficient of 83.6$\pm$6.3% in training and 71.8$\pm$10.7% in testing.
Cross-layer estimation and control for Cognitive Radio: Exploiting Sparse Network Dynamics
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a cross-layer framework to jointly optimize spectrum sensing and scheduling in resource constrained agile wireless networks is presented. A network of secondary users (SUs) accesses portions of the spectrum left unused by a network of licensed primary users (PUs). A central controller (CC) schedules the traffic of the SUs, based on distributed compressed measurements collected by the SUs. Sensing and scheduling are jointly controlled to maximize the SU throughput, with constraints on PU throughput degradation and SU cost. The sparsity in the spectrum dynamics is exploited: leveraging a prior spectrum occupancy estimate, the CC needs to estimate only a residual uncertainty vector via sparse recovery techniques. The high complexity entailed by the POMDP formulation is reduced by a low-dimensional belief representation via minimization of the Kullback-Leibler divergence. It is proved that the optimization of sensing and scheduling can be decoupled. A partially myopic scheduling strategy is proposed for which structural properties can be proved showing that the myopic scheme allocates SU traffic to likely idle spectral bands. Simulation results show that this framework balances optimally the resources between spectrum sensing and data transmission. This framework defines sensing-scheduling schemes most informative for network control, yielding energy efficient resource utilization.
Towards an algebraic characterization of rational word functions
Venue: arXiv cs.FL 2015
Year: 2015

In formal language theory, several different models characterize regular languages, such as finite automata, congruences of finite index, or monadic second-order logic (MSO). Moreover, several fragments of MSO have effective characterizations based on algebraic properties. When we consider transducers instead of automata, such characterizations are much more challenging, because many of the properties of regular languages do not generalize to regular word functions. In this paper we consider word functions that are definable by one-way transducers (rational functions). We show that the canonical bimachine of Reutenauer and Schützenberger preserves certain algebraic properties of rational functions, similar to the case of word languages. In particular, we give an effective characterization of functions that can be defined by an aperiodic one-way transducer.
Distributional Sentence Entailment Using Density Matrices
Venue: arXiv cs.CL 2015
Year: 2015

Categorical compositional distributional model of Coecke et al. (2010) suggests a way to combine grammatical composition of the formal, type logical models with the corpus based, empirical word representations of distributional semantics. This paper contributes to the project by expanding the model to also capture entailment relations. This is achieved by extending the representations of words from points in meaning space to density operators, which are probability distributions on the subspaces of the space. A symmetric measure of similarity and an asymmetric measure of entailment is defined, where lexical entailment is measured using von Neumann entropy, the quantum variant of Kullback-Leibler divergence. Lexical entailment, combined with the composition map on word representations, provides a method to obtain entailment relations on the level of sentences. Truth theoretic and corpus-based examples are provided.
Quantifying Cultural Histories via Person Networks in Wikipedia
Venue: arXiv cs.SI 2015
Year: 2015

At least since Priestley's 1765 Chart of Biography, large numbers of individual person records have been used to illustrate aggregate patterns of cultural history. Wikidata, the structured database sister of Wikipedia, currently contains about 2.7 million explicit person records, across all language versions of the encyclopedia. These individuals, notable according to Wikipedia editing criteria, are connected via millions of hyperlinks between their respective Wikipedia articles. This situation provides us with the chance to go beyond the illustration of an idiosyncratic subset of individuals, as in the case of Priestly. In this work we summarize the overlap of nationalities and occupations, based on their co-occurrence in Wikidata individuals. We construct networks of co-occurring nationalities and occupations, provide insights into their respective community structure, and apply the results to select and color chronologically structured subsets of a large network of individuals, connected by Wikipedia hyperlinks. While the imagined communities of nationality are much more discrete in terms of co-occurrence than occupations, our quantifications reveal the existing overlap of nationality as much less clear-cut than in case of occupational domains. Our work contributes to a growing body of research using biographies of notable persons to analyze cultural processes.
A Probe into Causes of Non-citation Based on Survey Data
Venue: arXiv cs.DL 2015
Year: 2015

Empirical analysis results about the possible causes leading to non-citation may help increase the potential of researchers' work to be cited and editorial staffs of journals to identify contributions with potential high quality. In this study, we conduct a survey on the possible causes leading to citation or non-citation based on a questionnaire. We then perform a statistical analysis to identify the major causes leading to non-citation in combination with the analysis on the data collected through the survey. Most respondents to our questionnaire identified eight major causes that facilitate easy citation of one's papers, such as research hotspots and novel topics of content, longer intervals after publication, research topics similar to my work, high quality of content, reasonable self-citation, highlighted title, prestigious authors, academic tastes and interests similar to mine.They also pointed out that the vast difference between their current and former research directions as the primary reason for their previously uncited papers. They feel that text that includes notes, comments, and letters to editors are rarely cited, and the same is true for too short or too lengthy papers. In comparison, it is easier for reviews, articles, or papers of intermediate length to be cited.
Automatic vehicle tracking and recognition from aerial image sequences
Venue: arXiv cs.CV 2015
Year: 2015

This paper addresses the problem of automated vehicle tracking and recognition from aerial image sequences. Motivated by its successes in the existing literature focus on the use of linear appearance subspaces to describe multi-view object appearance and highlight the challenges involved in their application as a part of a practical system. A working solution which includes steps for data extraction and normalization is described. In experiments on real-world data the proposed methodology achieved promising results with a high correct recognition rate and few, meaningful errors (type II errors whereby genuinely similar targets are sometimes being confused with one another). Directions for future research and possible improvements of the proposed method are discussed.
A Survey on Distributed Visualization Techniques over Clusters of Personal Computers
Venue: arXiv cs.GR 2015
Year: 2015

In the last years, Distributed Visualization over Personal Computer (PC) clusters has become important for research and industrial communities. They have made large-scale visualizations practical and more accessible. In this work we survey Distributed Visualization techniques aiming at compiling last decade's literature on the use of PC clusters as suitable alternatives to high-end workstations. We review the topic by defining basic concepts, enumerating system requirements and implementation challenges, and presenting up-to-date methodologies. Our work fulfills the needs of newcomers and seasoned professionals as an introductory compilation at the same time that it can help experienced personnel by organizing ideas.
R-CNN minus R
Venue: arXiv cs.CV 2015
Year: 2015

Deep convolutional neural networks (CNNs) have had a major impact in most areas of image understanding, including object category detection. In object detection, methods such as R-CNN have obtained excellent results by integrating CNNs with region proposal generation algorithms such as selective search. In this paper, we investigate the role of proposal generation in CNN-based detectors in order to determine whether it is a necessary modelling component, carrying essential geometric information not contained in the CNN, or whether it is merely a way of accelerating detection. We do so by designing and evaluating a detector that uses a trivial region generation scheme, constant for each image. Combined with SPP, this results in an excellent and fast detector that does not require to process an image with algorithms other than the CNN itself. We also streamline and simplify the training of CNN-based detectors by integrating several learning steps in a single algorithm, as well as by proposing a number of improvements that accelerate detection.
On the Shift Value Set of Cyclic Shifted Sequences for PAPR Reduction in OFDM Systems
Venue: arXiv cs.IT 2015
Year: 2015

Orthogonal frequency division multiplexing (OFDM) signals have high peak-to-average power ratio (PAPR), which causes distortion when OFDM signal passes through a nonlinear high power amplifier (HPA). A partial transmit sequence (PTS) scheme is one of the typical PAPR reduction methods. A cyclic shifted sequences (CSS) scheme is evolved from the PTS scheme to improve the PAPR reduction performance, where OFDM signal subsequences are cyclically shifted and combined to generate alternative OFDM signal sequences. The shift value (SV) sets in the CSS scheme should be carefully selected because those are closely related to the PAPR reduction performance of the CSS scheme. In this letter, we propose some criteria to select the good SV sets and verify its validness through simulations.
User-Centric IT Security - How to Design Usable Security Mechanisms
Venue: arXiv cs.CR 2015
Year: 2015

Nowadays, advanced security mechanisms exist to protect data, systems, and networks. Most of these mechanisms are effective, and security experts can handle them to achieve a sufficient level of security for any given system. However, most of these systems have not been designed with focus on good usability for the average end user. Today, the average end user often struggles with understanding and using security mechanisms. Other security mechanisms are simply annoying for end users. As the overall security of any system is only as strong as the weakest link in this system, bad usability of IT security mechanisms may result in operating errors, resulting in insecure systems. Buying decisions of end users may be affected by the usability of security mechanisms. Hence software providers may decide to better have no security mechanism then one with a bad usability. Usability of IT security mechanisms is one of the most underestimated properties of applications and systems. Even IT security itself is often only an afterthought. Hence, usability of security mechanisms is often the afterthought of an afterthought. Software developers are missing guidelines on how to build security mechanisms with good usability for end users. This paper presents some guidelines that should help software developers to improve end user usability of security-related mechanisms, and analyzes common applications based on these guidelines.
Incremental RANSAC for Online Relocation in Large Dynamic Environments
Venue: arXiv cs.RO 2015
Year: 2015

Vehicle relocation is the problem in which a mobile robot has to estimate the self-position with respect to an a priori map of landmarks using the perception and the motion measurements without using any knowledge of the initial self-position. Recently, RANdom SAmple Consensus (RANSAC), a robust multi-hypothesis estimator, has been successfully applied to offline relocation in static environments. On the other hand, online relocation in dynamic environments is still a difficult problem, for available computation time is always limited, and for measurement include many outliers. To realize real time algorithm for such an online process, we have developed an incremental version of RANSAC algorithm by extending an efficient preemption RANSAC scheme. This novel scheme named incremental RANSAC is able to find inlier hypotheses of self-positions out of large number of outlier hypotheses contaminated by outlier measurements.
Natural Scene Recognition Based on Superpixels and Deep Boltzmann Machines
Venue: arXiv cs.CV 2015
Year: 2015

The Deep Boltzmann Machines (DBM) is a state-of-the-art unsupervised learning model, which has been successfully applied to handwritten digit recognition and, as well as object recognition. However, the DBM is limited in scene recognition due to the fact that natural scene images are usually very large. In this paper, an efficient scene recognition approach is proposed based on superpixels and the DBMs. First, a simple linear iterative clustering (SLIC) algorithm is employed to generate superpixels of input images, where each superpixel is regarded as an input of a learning model. Then, a two-layer DBM model is constructed by stacking two restricted Boltzmann machines (RBMs), and a greedy layer-wise algorithm is applied to train the DBM model. Finally, a softmax regression is utilized to categorize scene images. The proposed technique can effectively reduce the computational complexity and enhance the performance for large natural image recognition. The approach is verified and evaluated by extensive experiments, including the fifteen-scene categories dataset the UIUC eight-sports dataset, and the SIFT flow dataset, are used to evaluate the proposed method. The experimental results show that the proposed approach outperforms other state-of-the-art methods in terms of recognition rate.
Mutation Testing as a Safety Net for Test Code Refactoring
Venue: arXiv cs.SE 2015
Year: 2015

Refactoring is an activity that improves the internal structure of the code without altering its external behavior. When performed on the production code, the tests can be used to verify that the external behavior of the production code is preserved. However, when the refactoring is performed on test code, there is no safety net that assures that the external behavior of the test code is preserved. In this paper, we propose to adopt mutation testing as a means to verify if the behavior of the test code is preserved after refactoring. Moreover, we also show how this approach can be used to identify the part of the test code which is improperly refactored.
Sequential Extensions of Causal and Evidential Decision Theory
Venue: arXiv cs.AI 2015
Year: 2015

Moving beyond the dualistic view in AI where agent and environment are separated incurs new challenges for decision making, as calculation of expected utility is no longer straightforward. The non-dualistic decision theory literature is split between causal decision theory and evidential decision theory. We extend these decision algorithms to the sequential setting where the agent alternates between taking actions and observing their consequences. We find that evidential decision theory has two natural extensions while causal decision theory only has one.
Open-TEE - An Open Virtual Trusted Execution Environment
Venue: arXiv cs.CR 2015
Year: 2015

Hardware-based Trusted Execution Environments (TEEs) are widely deployed in mobile devices. Yet their use has been limited primarily to applications developed by the device vendors. Recent standardization of TEE interfaces by GlobalPlatform (GP) promises to partially address this problem by enabling GP-compliant trusted applications to run on TEEs from different vendors. Nevertheless ordinary developers wishing to develop trusted applications face significant challenges. Access to hardware TEE interfaces are difficult to obtain without support from vendors. Tools and software needed to develop and debug trusted applications may be expensive or non-existent. In this paper, we describe Open-TEE, a virtual, hardware-independent TEE implemented in software. Open-TEE conforms to GP specifications. It allows developers to develop and debug trusted applications with the same tools they use for developing software in general. Once a trusted application is fully debugged, it can be compiled for any actual hardware TEE. Through performance measurements and a user study we demonstrate that Open-TEE is efficient and easy to use. We have made Open- TEE freely available as open source.
Global Optimality in Tensor Factorization, Deep Learning, and Beyond
Venue: arXiv cs.NA 2015
Year: 2015

Techniques involving factorization are found in a wide range of applications and have enjoyed significant empirical success in many fields. However, common to a vast majority of these problems is the significant disadvantage that the associated optimization problems are typically non-convex due to a multilinear form or other convexity destroying transformation. Here we build on ideas from convex relaxations of matrix factorizations and present a very general framework which allows for the analysis of a wide range of non-convex factorization problems - including matrix factorization, tensor factorization, and deep neural network training formulations. We derive sufficient conditions to guarantee that a local minimum of the non-convex optimization problem is a global minimum and show that if the size of the factorized variables is large enough then from any initialization it is possible to find a global minimizer using a purely local descent algorithm. Our framework also provides a partial theoretical justification for the increasingly common use of Rectified Linear Units (ReLUs) in deep neural networks and offers guidance on deep network architectures and regularization strategies to facilitate efficient optimization.