OpenRaiser/Intern-Atlas huggingface dataset:
Transfer Learning Based on AdaBoost for Feature Selection from Multiple ConvNet Layer Features
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional Networks (ConvNets) are powerful models that learn hierarchies of visual features, which could also be used to obtain image representations for transfer learning. The basic pipeline for transfer learning is to first train a ConvNet on a large dataset (source task) and then use feed-forward units activation of the trained ConvNet as image representation for smaller datasets (target task). Our key contribution is to demonstrate superior performance of multiple ConvNet layer features over single ConvNet layer features. Combining multiple ConvNet layer features will result in more complex feature space with some features being repetitive. This requires some form of feature selection. We use AdaBoost with single stumps to implicitly select only distinct features that are useful towards classification from concatenated ConvNet features. Experimental results show that using multiple ConvNet layer activation features instead of single ConvNet layer features consistently will produce superior performance. Improvements becomes significant as we increase the distance between source task and the target task.
Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
Venue: arXiv cs.LO 2016
Year: 2016

Blondin et al. showed at LICS 2015 that two-dimensional vector addition systems with states have reachability witnesses of length exponential in the number of states and polynomial in the norm of vectors. The resulting guess-and-verify algorithm is optimal (PSPACE), but only if the input vectors are given in binary. We answer positively the main question left open by their work, namely establish that reachability witnesses of pseudo-polynomial length always exist. Hence, when the input vectors are given in unary, the improved guess-and-verify algorithm requires only logarithmic space.
A SHM method for detecting damage with incomplete observations based on VARX modelling and Granger causality
Venue: arXiv cs.SY 2016
Year: 2016

A SHM method is proposed that minimises the required number of sensors for detecting damage. The damage detection method consists of two steps. In an initial characterization step, substructuring approach is applied to the healthy structure in order to isolate the substructures of interest and later, each substructure is identified by a Vector Auto Regressive with eXogenous inputs (VARX) model measuring all DOFs. Then, pairwise conditional Granger causality analysis is carried out with data measured from substructural DOFs to evaluate the information loss when measurements from all DOFs are not available. This analysis allows selecting those accelerometers that can be suppressed minimising the information loss. In the evaluation phase, vibration data from the reduced set of sensors is compared to the estimated data obtained from the healthy substructure's VARX model, and as a result a damage indicator is computed. The proposed detection method is validated by finite element simulations in a lattice structure model.
Multi-object Classification via Crowdsourcing with a Reject Option
Venue: arXiv cs.LG 2016
Year: 2016

Consider designing an effective crowdsourcing system for an $M$-ary classification task. Crowd workers complete simple binary microtasks whose results are aggregated to give the final result. We consider the novel scenario where workers have a reject option so they may skip microtasks when they are unable or choose not to respond. For example, in mismatched speech transcription, workers who do not know the language may not be able to respond to microtasks focused on phonological dimensions outside their categorical perception. We present an aggregation approach using a weighted majority voting rule, where each worker's response is assigned an optimized weight to maximize the crowd's classification performance. We evaluate system performance in both exact and asymptotic forms. Further, we consider the setting where there may be a set of greedy workers that complete microtasks even when they are unable to perform it reliably. We consider an oblivious and an expurgation strategy to deal with greedy workers, developing an algorithm to adaptively switch between the two based on the estimated fraction of greedy workers in the anonymous crowd. Simulation results show improved performance compared with conventional majority voting.
A Gain Function for Architectural Decision-Making in Scientific Computing
Venue: arXiv cs.DC 2016
Year: 2016

Scientific Computing typically requires large computational needs which have been addressed with High Performance Distributed Computing. It is essential to efficiently deploy a number of complex scientific applications, which have different characteristics, and so require distinct computational resources too. However, in many research laboratories, this high performance architecture is not dedicated. So, the architecture must be shared to execute a set of scientific applications, with so many different execution times and relative importance to research. Also, the high performance architectures have different characteristics and costs. When a new infrastructure has to be acquired to meet the needs of this scenario, the decision-making is hard and complex. In this work, we present a Gain Function as a model of an utility function, with which it is possible a decision-making with confidence. With the function is possible to evaluate the best architectural option taking into account aspects of applications and architectures, including the executions time, cost of architecture, the relative importance of each application and also the relative importance of performance and cost on the final evaluation. This paper presents the Gain Function, examples, and a real case showing their applicabilities.
NEXT: In-Network Nonconvex Optimization
Venue: arXiv cs.DC 2016
Year: 2016

We study nonconvex distributed optimization in multi-agent networks with time-varying (nonsymmetric) connectivity. We introduce the first algorithmic framework for the distributed minimization of the sum of a smooth (possibly nonconvex and nonseparable) function - the agents' sum-utility - plus a convex (possibly nonsmooth and nonseparable) regularizer. The latter is usually employed to enforce some structure in the solution, typically sparsity. The proposed method hinges on successive convex approximation techniques while leveraging dynamic consensus as a mechanism to distribute the computation among the agents: each agent first solves (possibly inexactly) a local convex approximation of the nonconvex original problem, and then performs local averaging operations. Asymptotic convergence to (stationary) solutions of the nonconvex problem is established. Our algorithmic framework is then customized to a variety of convex and nonconvex problems in several fields, including signal processing, communications, networking, and machine learning. Numerical results show that the new method compares favorably to existing distributed algorithms on both convex and nonconvex problems.
Ensemble Toolkit: Scalable and Flexible Execution of Ensembles of Tasks
Venue: arXiv cs.DC 2016
Year: 2016

There are many science applications that require scalable task-level parallelism and support for flexible execution and coupling of ensembles of simulations. Most high-performance system software and middleware, however, are designed to support the execution and optimization of single tasks. Motivated by the missing capabilities of these computing systems and the increasing importance of task-level parallelism, we introduce the Ensemble toolkit which has the following application development features: (i) abstractions that enable the expression of ensembles as primary entities, and (ii) support for ensemble-based execution patterns that capture the majority of application scenarios. Ensemble toolkit uses a scalable pilot-based runtime system that decouples workload execution and resource management details from the expression of the application, and enables the efficient and dynamic execution of ensembles on heterogeneous computing resources. We investigate three execution patterns and characterize the scalability and overhead of Ensemble toolkit for these patterns. We investigate scaling properties for up to O(1000) concurrent ensembles and O(1000) cores and find linear weak and strong scaling behaviour.
Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations
Venue: arXiv cs.SC 2016
Year: 2016

We give a Las Vegas algorithm which computes the shifted Popov form of an $m \times m$ nonsingular polynomial matrix of degree $d$ in expected $\widetilde{\mathcal{O}}(m^ωd)$ field operations, where $ω$ is the exponent of matrix multiplication and $\widetilde{\mathcal{O}}(\cdot)$ indicates that logarithmic factors are omitted. This is the first algorithm in $\widetilde{\mathcal{O}}(m^ωd)$ for shifted row reduction with arbitrary shifts. Using partial linearization, we reduce the problem to the case $d \le \lceil σ/m \rceil$ where $σ$ is the generic determinant bound, with $σ/ m$ bounded from above by both the average row degree and the average column degree of the matrix. The cost above becomes $\widetilde{\mathcal{O}}(m^ω\lceil σ/m \rceil)$, improving upon the cost of the fastest previously known algorithm for row reduction, which is deterministic. Our algorithm first builds a system of modular equations whose solution set is the row space of the input matrix, and then finds the basis in shifted Popov form of this set. We give a deterministic algorithm for this second step supporting arbitrary moduli in $\widetilde{\mathcal{O}}(m^{ω-1} σ)$ field operations, where $m$ is the number of unknowns and $σ$ is the sum of the degrees of the moduli. This extends previous results with the same cost bound in the specific cases of order basis computation and M-Padé approximation, in which the moduli are products of known linear factors.
Algorithm-Induced Prior for Image Restoration
Venue: arXiv cs.CV 2016
Year: 2016

This paper studies a type of image priors that are constructed implicitly through the alternating direction method of multiplier (ADMM) algorithm, called the algorithm-induced prior. Different from classical image priors which are defined before running the reconstruction algorithm, algorithm-induced priors are defined by the denoising procedure used to replace one of the two modules in the ADMM algorithm. Since such prior is not explicitly defined, analyzing the performance has been difficult in the past. Focusing on the class of symmetric smoothing filters, this paper presents an explicit expression of the prior induced by the ADMM algorithm. The new prior is reminiscent to the conventional graph Laplacian but with stronger reconstruction performance. It can also be shown that the overall reconstruction has an efficient closed-form implementation if the associated symmetric smoothing filter is low rank. The results are validated with experiments on image inpainting.
A Unified Framework for Information Consumption Based on Markov Chains
Venue: arXiv cs.SI 2016
Year: 2016

This paper establishes a Markov chain model as a unified framework for understanding information consumption processes in complex networks, with clear implications to the Internet and big-data technologies. In particular, the proposed model is the first one to address the formation mechanism of the "trichotomy" in observed probability density functions from empirical data of various social and technical networks. Both simulation and experimental results demonstrate a good match of the proposed model with real datasets, showing its superiority over the classical power-law models.
A Novel Human Computer Interaction Platform based College Mathematical Education Methodology
Venue: arXiv cs.HC 2016
Year: 2016

This article proposes the analysis on novel human computer interaction (HCI) platform based college mathematical education methodology. Above for the application of virtual reality technology in teaching the problems in the study, only through the organization focus on the professional and technical personnel, and constantly improve researchers in development process of professional knowledge, close to the actual needs of the teaching can we achieve the satisfactory result. To obtain better education output, we combine the Kinect to form the HCI based teaching environment. We firstly review the latest HCI technique and principles of college math courses, then we introduce basic components of the Kinect including the gesture segmentation, systematic implementation and the primary characteristics of the platform. As the further step, we implement the system with the re-write of script code to build up the personalized HCI assisted education scenario. The verification and simulation proves the feasibility of our method.
The Grail theorem prover: Type theory for syntax and semantics
Venue: arXiv cs.CL 2016
Year: 2016

As the name suggests, type-logical grammars are a grammar formalism based on logic and type theory. From the prespective of grammar design, type-logical grammars develop the syntactic and semantic aspects of linguistic phenomena hand-in-hand, letting the desired semantics of an expression inform the syntactic type and vice versa. Prototypical examples of the successful application of type-logical grammars to the syntax-semantics interface include coordination, quantifier scope and extraction.This chapter describes the Grail theorem prover, a series of tools for designing and testing grammars in various modern type-logical grammars which functions as a tool . All tools described in this chapter are freely available.
Practical Non-Linear Energy Harvesting Model and Resource Allocation in SWIPT Systems
Venue: arXiv cs.IT 2016
Year: 2016

Simultaneous wireless information and power transfer (SWIPT) is a promising solution for enabling long-life, and self-sustainable wireless networks. In this thesis, we propose a practical non-linear energy harvesting (EH) model and design a resource allocation algorithm for SWIPT systems. In particular, the algorithm design is formulated as a non-convex optimization problem for the maximization of the total harvested power at the EH receivers subject to quality of service (QoS) constraints for the information decoding (ID) receivers. To circumvent the non-convexity of the problem, we transform the corresponding non-convex sum-of-ratios objective function into an equivalent objective function in parametric subtractive form. Furthermore, we design a computationally efficient iterative resource allocation algorithm to obtain the globally optimal solution. Numerical results illustrate significant performance gain in terms of average total harvested power for the proposed non-linear EH receiver model, when compared to the traditional linear model.\
A sufficient condition for tail asymptotics of SIR distribution in downlink cellular networks
Venue: arXiv cs.IT 2016
Year: 2016

We consider the spatial stochastic model of single-tier downlink cellular networks, where the wireless base stations are deployed according to a general stationary point process on the Euclidean plane with general i.i.d. propagation effects. Recently, Ganti & Haenggi (2016) consider the same general cellular network model and, as one of many significant results, derive the tail asymptotics of the signal-to-interference ratio (SIR) distribution. However, they do not mention any conditions under which the result holds. In this paper, we compensate their result for the lack of the condition and expose a sufficient condition for the asymptotic result to be valid. We further illustrate some examples satisfying such a sufficient condition and indicate the corresponding asymptotic results for the example models. We give also a simple counterexample violating the sufficient condition.
Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices
Venue: arXiv cs.IT 2016
Year: 2016

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of noisy tests. While matching achievability and converse bounds are known in several cases of interest for i.i.d.~measurement matrices, less is known regarding converse bounds for arbitrary measurement matrices. We address this by presenting two converse bounds for arbitrary matrices and general noise models. First, we provide a strong converse bound ($\mathbb{P}[\mathrm{error}] \to 1$) that matches existing achievability bounds in several cases of interest. Second, we provide a weak converse bound ($\mathbb{P}[\mathrm{error}] \not\to 0$) that matches existing achievability bounds in greater generality.
5G Waveforms for Overlay D2D Communications: Effects of Time-Frequency Misalignment
Venue: arXiv cs.IT 2016
Year: 2016

This paper analyses a scenario where a Device-To-Device (D2D) pair coexists with an Orthogonal Frequency Division Multiplexing (OFDM) based incumbent network. D2D transmitter communicates in parts of spectrum left free by cellular users, while respecting a given spectral mask. The D2D pair is misaligned in time and frequency with the cellular users. Furthermore, the D2D pair utilizes alternative waveforms to OFDM proposed for 5G. In this study, we show that it is not worth synchronising the D2D pair in time with respect to the cellular users. Indeed, the interference injected into the incumbent network has small variations with respect to time misalignment. We provide interference tables that encompass both time and frequency misalignment. We use them to analyse the maximum rate achievable by the D2D pair when it uses different waveforms. Then, we present numerical results showing what waveform should be utilized by the D2D pair according to the time-frequency resources that are not used by the incumbent network. Our results show that the delay induced by linearly convolved waveforms make them hardly applicable to short time windows, but that they dominate OFDM for long transmissions, mainly in the case where cellular users are very sensitive to interference.
From $μ$-Calculus to Alternating Tree Automata using Parity Games
Venue: arXiv cs.LO 2016
Year: 2016

$μ$-Calculus and automata on infinite trees are complementary ways of describing infinite tree languages. The correspondence between $μ$-Calculus and alternating tree automaton is used to solve the satisfiability and model checking problems by compiling the modal $μ$-Calculus formula into an alternating tree automata. Thus advocating an automaton model specially tailored for working with modal $μ$-Calculus. The advantage of the automaton model is its ability to deal with arbitrary branching in a much simpler way as compare to the one proposed by Janin and Walukiewicz. Both problems (i.e., model checking and satisfiability) are solved by reduction to the corresponding problems of alternating tree automata, namely to the acceptance and the non-emptiness problems, respectively. These problems, in turn, are solved using parity games where semantics of alternating tree automata is translated to a winning strategy in an appropriate parity game.
Using Node Centrality and Optimal Control to Maximize Information Diffusion in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

We model information dissemination as a susceptible-infected epidemic process and formulate a problem to jointly optimize seeds for the epidemic and time varying resource allocation over the period of a fixed duration campaign running on a social network with a given adjacency matrix. Individuals in the network are grouped according to their centrality measure and each group is influenced by an external control function---implemented through advertisements---during the campaign duration. The aim is to maximize an objective function which is a linear combination of the reward due to the fraction of informed individuals at the deadline, and the aggregated cost of applying controls (advertising) over the campaign duration. We also study a problem variant with a fixed budget constraint. We set up the optimality system using Pontryagin's Maximum Principle from optimal control theory and solve it numerically using the forward-backward sweep technique. Our formulation allows us to compare the performance of various centrality measures (pagerank, degree, closeness and betweenness) in maximizing the spread of a message in the optimal control framework. We find that degree---a simple and local measure---performs well on the three social networks used to demonstrate results: scientific collaboration, Slashdot and Facebook. The optimal strategy targets central nodes when the resource is scarce, but non-central nodes are targeted when the resource is in abundance. Our framework is general and can be used in similar studies for other disease or information spread models---that can be modeled using a system of ordinary differential equations---for a network with a known adjacency matrix.
A-expansion for multiple "hedgehog" shapes
Venue: arXiv cs.CV 2016
Year: 2016

Overlapping colors and cluttered or weak edges are common segmentation problems requiring additional regularization. For example, star-convexity is popular for interactive single object segmentation due to simplicity and amenability to exact graph cut optimization. This paper proposes an approach to multiobject segmentation where objects could be restricted to separate "hedgehog" shapes. We show that a-expansion moves are submodular for our multi-shape constraints. Each "hedgehog" shape has its surface normals constrained by some vector field, e.g. gradients of a distance transform for user scribbles. Tight constraint give an extreme case of a shape prior enforcing skeleton consistency with the scribbles. Wider cones of allowed normals gives more relaxed hedgehog shapes. A single click and +/-90 degrees normal orientation constraints reduce our hedgehog prior to star-convexity. If all hedgehogs come from single clicks then our approach defines multi-star prior. Our general method has significantly more applications than standard one-star segmentation. For example, in medical data we can separate multiple non-star organs with similar appearances and weak or noisy edges.
Improved Achievability and Converse Bounds for Erdős-Rényi Graph Matching
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of perfectly recovering the vertex correspondence between two correlated Erdős-Rényi (ER) graphs. For a pair of correlated graphs on the same vertex set, the correspondence between the vertices can be obscured by randomly permuting the vertex labels of one of the graphs. In some cases, the structural information in the graphs allow this correspondence to be recovered. We investigate the information-theoretic threshold for exact recovery, i.e. the conditions under which the entire vertex correspondence can be correctly recovered given unbounded computational resources. Pedarsani and Grossglauser provided an achievability result of this type. Their result establishes the scaling dependence of the threshold on the number of vertices. We improve on their achievability bound. We also provide a converse bound, establishing conditions under which exact recovery is impossible. Together, these establish the scaling dependence of the threshold on the level of correlation between the two graphs. The converse and achievability bounds differ by a factor of two for sparse, significantly correlated graphs.