OpenRaiser/Intern-Atlas huggingface dataset:
Enabling Complex Wikipedia Queries - Technical Report
Venue: arXiv cs.IR 2015
Year: 2015

In this technical report we present a database schema used to store Wikipedia so it can be easily used in query-intensive applications. In addition to storing the information in a way that makes it highly accessible, our schema enables users to easily formulate complex queries using information such as the anchor-text of links and their location in the page, the titles and number of redirect pages for each page and the paragraph structure of entity pages. We have successfully used the schema in domains such as recommender systems, information retrieval and sentiment analysis. In order to assist other researchers, we now make the schema and its content available online.
Multi-Task Learning with Group-Specific Feature Space Sharing
Venue: arXiv cs.LG 2015
Year: 2015

When faced with learning a set of inter-related tasks from a limited amount of usable data, learning each task independently may lead to poor generalization performance. Multi-Task Learning (MTL) exploits the latent relations between tasks and overcomes data scarcity limitations by co-learning all these tasks simultaneously to offer improved performance. We propose a novel Multi-Task Multiple Kernel Learning framework based on Support Vector Machines for binary classification tasks. By considering pair-wise task affinity in terms of similarity between a pair's respective feature spaces, the new framework, compared to other similar MTL approaches, offers a high degree of flexibility in determining how similar feature spaces should be, as well as which pairs of tasks should share a common feature space in order to benefit overall performance. The associated optimization problem is solved via a block coordinate descent, which employs a consensus-form Alternating Direction Method of Multipliers algorithm to optimize the Multiple Kernel Learning weights and, hence, to determine task affinities. Empirical evaluation on seven data sets exhibits a statistically significant improvement of our framework's results compared to the ones of several other Clustered Multi-Task Learning methods.
Looking at Software Sustainability and Productivity Challenges from NSF
Venue: arXiv cs.CY 2015
Year: 2015

This paper is a contribution to the Computational Science & Engineering Software Sustainability and Productivity Challenges (CSESSP Challenges) Workshop (https://www.nitrd.gov/csessp/), sponsored by the Networking and Information Technology Research and Development (NITRD) Software Design and Productivity (SDP) Coordinating Group, held October 15th-16th 2015 in Washington DC, USA. It introduces the role of software at the National Science Foundation (NSF) and the NSF Software Infrastructure for Sustained Innovation (SI2) program, then describes challenges that the SI2 program has identified, including funding models, career paths, incentives, training, interdisciplinary work, portability, and dissemination, as well as lesson that have been learned.
On the Consistency and Confidence of Distributed Dynamic State Estimation in Wireless Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

The problem of distributed dynamic state estimation in wireless sensor networks is studied. Two important properties of local estimates, namely, the consistency and confidence, are emphasized. On one hand, the consistency, which means that the approximated error covariance is lower bounded by the true unknown one, has to be guaranteed so that the estimate is not over-confident. On the other hand, since the confidence indicates the accuracy of the estimate, the estimate should be as confident as possible. We first analyze two different information fusion strategies used in the case of information sources with, respectively, uncorrelated errors and unknown but correlated errors. Then a distributed hybrid information fusion algorithm is proposed, where each agent uses the information obtained not only by itself, but also from its neighbors through communication. The proposed algorithm not only guarantees the consistency of the estimates, but also utilizes the available information sources in a more efficient manner and hence improves the confidence. Besides, the proposed algorithm is fully distributed and guarantees convergence with the sufficient condition formulated. The comparisons with existing algorithms are shown.
An Algorithm for Comparing Similarity Between Two Trees
Venue: arXiv cs.CG 2015
Year: 2015

An important problem in geometric computing is defining and computing similarity between two geometric shapes, e.g. point sets, curves and surfaces, etc. Important geometric and topological information of many shapes can be captured by defining a tree structure on them (e.g. medial axis and contour trees). Hence, it is natural to study the problem of comparing similarity between trees. We study gapped edit distance between two ordered labeled trees, first proposed by Touzet \cite{Touzet2003}. Given two binary trees $T_{1}$ and $T_{2}$ with $m$ and $n$ nodes. We compute the general gap edit distance in $O(m^{3}n^{2} + m^{2}n^{3})$ time. The computation of this distance in the case of arbitrary trees has shown to be NP-hard \cite{Touzet2003}. We also give an algorithm for computing the complete subtree gap edit distance, which can be applied to comparing contour trees of terrains in $\mathbb{R}^{3}$.
Moment Matching Based Model Reduction for LPV State-Space Models
Venue: arXiv cs.SY 2015
Year: 2015

We present a novel algorithm for reducing the state dimension, i.e. order, of linear parameter varying (LPV) discrete-time state-space (SS) models with affine dependence on the scheduling variable. The input-output behavior of the reduced order model approximates that of the original model. In fact, for input and scheduling sequences of a certain length, the input-output behaviors of the reduced and original model coincide. The proposed method can also be interpreted as a reachability and observability reduction (minimization) procedure for LPV-SS representations with affine dependence.
Sum-rate Maximizing in Downlink Massive MIMO Systems with Circuit Power Consumption
Venue: arXiv cs.IT 2015
Year: 2015

The downlink of a single cell base station (BS) equipped with large-scale multiple-input multiple-output (MIMO) system is investigated in this paper. As the number of antennas at the base station becomes large, the power consumed at the RF chains cannot be anymore neglected. So, a circuit power consumption model is introduced in this work. It involves that the maximal sum-rate is not obtained when activating all the available RF chains. Hence, the aim of this work is to find the optimal number of activated RF chains that maximizes the sum-rate. Computing the optimal number of activated RF chains must be accompanied by an adequate antenna selection strategy. First, we derive analytically the optimal number of RF chains to be activated so that the average sum-rate is maximized under received equal power. Then, we propose an efficient greedy algorithm to select the sub-optimal set of RF chains to be activated with regards to the system sum-rate. It allows finding the balance between the power consumed at the RF chains and the transmitted power. The performance of the proposed algorithm is compared with the optimal performance given by brute force search (BFS) antenna selection. Simulations allow to compare the performance given by greedy, optimal and random antenna selection algorithms.
RFC 7800 - Money Over IP
Venue: arXiv cs.CR 2015
Year: 2015

This Request For Comment (RFC) is a proposal for a new protocol to use money over the Internet. Features like a distributed architecture, a published cryptographic algorithm, a minimal authority responsibility, the absence of fees will make this protocol a perfect tool for citizens in today's digital World. An implementation has validated the main principles and we entering now a testing phase (v0.1). Depending of the results, a released date for the 1.0 revision will to decided to allow anybody to send or to receive money to/from anyone, in any currency, with a regular and personal smart-phone. A distributed hash table (DHT) is used to store all transactions, public keys and certificates redundantly on several nodes. The all system may replace coins, banknotes and classical checks in the future. We also argue that the Bitcoin technology does not satisfy the requirements for a digital mean of payment. This proposal is expected to be reviewed and commented by the Internet Engineering Task Force.
Borobudur was Built Algorithmically
Venue: arXiv cs.CY 2015
Year: 2015

The self-similarity of Indonesian Borobudur Temple is observed through the dimensionality of stupa that is hypothetically closely related to whole architectural body. Fractal dimension is calculated by using the cube counting method and found that the dimension is 2.325, which is laid between the two-dimensional plane and three dimensional space. The applied fractal geometry and self-similarity of the building is emerged as the building process implement the metric rules, since there is no universal metric standard known in ancient traditional Javanese culture thus the architecture is not based on final master plan. The paper also proposes how the hypothetical algorithmic architecture might be applied computationally in order to see some experimental generations of similar building. The paper ends with some conjectures for further challenge and insights related to fractal geometry in Javanese traditional cultural heritages.
Computing in Additive Networks with Bounded-Information Codes
Venue: arXiv cs.DC 2015
Year: 2015

This paper studies the theory of the additive wireless network model, in which the received signal is abstracted as an addition of the transmitted signals. Our central observation is that the crucial challenge for computing in this model is not high contention, as assumed previously, but rather guaranteeing a bounded amount of \emph{information} in each neighborhood per round, a property that we show is achievable using a new random coding technique. Technically, we provide efficient algorithms for fundamental distributed tasks in additive networks, such as solving various symmetry breaking problems, approximating network parameters, and solving an \emph{asymmetry revealing} problem such as computing a maximal input. The key method used is a novel random coding technique that allows a node to successfully decode the received information, as long as it does not contain too many distinct values. We then design our algorithms to produce a limited amount of information in each neighborhood in order to leverage our enriched toolbox for computing in additive networks.
Mixture Selection, Mechanism Design, and Signaling
Venue: arXiv cs.GT 2015
Year: 2015

We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and an $n \times m$ matrix $A$ with bounded entries, maximize $g(Ax)$ over $x$ in the $m$-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a.k.a. signaling). We present an approximation algorithm for this problem when $g$ simultaneously satisfies two smoothness properties: Lipschitz continuity with respect to the $L^\infty$ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability errors in the inputs of $g$ can impact its output. When $g$ is both $O(1)$-Lipschitz continuous and $O(1)$-stable, we obtain an (additive) PTAS for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive FPTAS. We apply our algorithm to different game-theoretic applications from mechanism design and optimal signaling. We make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan; we resolve the problem of revenue-maximizing signaling in Bayesian second-price auctions posed by Emek et al. and Miltersen and Sheffet; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and Câmara.
Distributed Robust Bilinear State Estimation for Power Systems with Nonlinear Measurements
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a fully distributed robust state-estimation (D-RBSE) method that is applicable to multi-area power systems with nonlinear measurements. We extend the recently introduced bilinear formulation of state estimation problems to a robust model. A distributed bilinear state-estimation procedure is developed. In both linear stages, the state estimation problem in each area is solved locally, with minimal data exchange with its neighbors. The intermediate nonlinear transformation can be performed by all areas in parallel without any need of inter-regional communication. This algorithm does not require a central coordinator and can compress bad measurements by introducing a robust state estimation model. Numerical tests on IEEE 14-bus and 118-bus benchmark systems demonstrate the validity of the method.
Some New Research Trends in Wirelessly Powered Communications
Venue: arXiv cs.IT 2015
Year: 2015

The vision of seamlessly integrating information transfer (IT) and microwave based power transfer (PT) in the same system has led to the emergence of a new research area, called wirelessly power communications (WPC). Extensive research has been conducted on developing WPC theory and techniques, building on the extremely rich wireless communications litera- ture covering diversified topics such as transmissions, resource allocations, medium access control and network protocols and architectures. Despite these research efforts, transforming WPC from theory to practice still faces many unsolved prob- lems concerning issues such as mobile complexity, power transfer efficiency, and safety. Furthermore, the fundamental limits of WPC remain largely unknown. Recent attempts to address these open issues has resulted in the emergence of numerous new research trends in the WPC area. A few promising trends are introduced in this article. From the practical perspective, the use of backscatter antennas can support WPC for low-complexity passive devices, the design of spiky waveforms can improve the PT efficiency, and analog spatial decoupling is proposed for solving the PT-IT near-far problem in WPC. From the theoretic perspective, the fundamental limits of WPC can be quantified by leveraging recent results on super-directivity and the limit can be improved by the deployment of large-scale distributed antenna arrays. Specific research problems along these trends are discussed, whose solutions can lead to significant advancements in WPC.
Depth-Gated LSTM
Venue: arXiv cs.NE 2015
Year: 2015

In this short note, we present an extension of long short-term memory (LSTM) neural networks to using a depth gate to connect memory cells of adjacent layers. Doing so introduces a linear dependence between lower and upper layer recurrent units. Importantly, the linear dependence is gated through a gating function, which we call depth gate. This gate is a function of the lower layer memory cell, the input to and the past memory cell of this layer. We conducted experiments and verified that this new architecture of LSTMs was able to improve machine translation and language modeling performances.
Causal Decision Trees
Venue: arXiv cs.AI 2015
Year: 2015

Uncovering causal relationships in data is a major objective of data analytics. Causal relationships are normally discovered with designed experiments, e.g. randomised controlled trials, which, however are expensive or infeasible to be conducted in many cases. Causal relationships can also be found using some well designed observational studies, but they require domain experts' knowledge and the process is normally time consuming. Hence there is a need for scalable and automated methods for causal relationship exploration in data. Classification methods are fast and they could be practical substitutes for finding causal signals in data. However, classification methods are not designed for causal discovery and a classification method may find false causal signals and miss the true ones. In this paper, we develop a causal decision tree where nodes have causal interpretations. Our method follows a well established causal inference framework and makes use of a classic statistical test. The method is practical for finding causal signals in large data sets.
The Computational Power of Beeps
Venue: arXiv cs.DC 2015
Year: 2015

In this paper, we study the quantity of computational resources (state machine states and/or probabilistic transition precision) needed to solve specific problems in a single hop network where nodes communicate using only beeps. We begin by focusing on randomized leader election. We prove a lower bound on the states required to solve this problem with a given error bound, probability precision, and (when relevant) network size lower bound. We then show the bound tight with a matching upper bound. Noting that our optimal upper bound is slow, we describe two faster algorithms that trade some state optimality to gain efficiency. We then turn our attention to more general classes of problems by proving that once you have enough states to solve leader election with a given error bound, you have (within constant factors) enough states to simulate correctly, with this same error bound, a logspace TM with a constant number of unary input tapes: allowing you to solve a large and expressive set of problems. These results identify a key simplicity threshold beyond which useful distributed computation is possible in the beeping model.
Discrete Route/Trajectory Decision Making Problems
Venue: arXiv cs.AI 2015
Year: 2015

The paper focuses on composite multistage decision making problems which are targeted to design a route/trajectory from an initial decision situation (origin) to goal (destination) decision situation(s). Automobile routing problem is considered as a basic physical metaphor. The problems are based on a discrete (combinatorial) operations/states design/solving space (e.g., digraph). The described types of discrete decision making problems can be considered as intelligent design of a route (trajectory, strategy) and can be used in many domains: (a) education (planning of student educational trajectory), (b) medicine (medical treatment), (c) economics (trajectory of start-up development). Several types of the route decision making problems are described: (i) basic route decision making, (ii) multi-goal route decision making, (iii) multi-route decision making, (iv) multi-route decision making with route/trajectory change(s), (v) composite multi-route decision making (solution is a composition of several routes/trajectories at several corresponding domains), and (vi) composite multi-route decision making with coordinated routes/trajectories. In addition, problems of modeling and building the design spaces are considered. Numerical examples illustrate the suggested approach. Three applications are considered: educational trajectory (orienteering problem), plan of start-up company (modular three-stage design), and plan of medical treatment (planning over digraph with two-component vertices).
Visual Affect Around the World: A Large-scale Multilingual Visual Sentiment Ontology
Venue: arXiv cs.MM 2015
Year: 2015

Every culture and language is unique. Our work expressly focuses on the uniqueness of culture and language in relation to human affect, specifically sentiment and emotion semantics, and how they manifest in social multimedia. We develop sets of sentiment- and emotion-polarized visual concepts by adapting semantic structures called adjective-noun pairs, originally introduced by Borth et al. (2013), but in a multilingual context. We propose a new language-dependent method for automatic discovery of these adjective-noun constructs. We show how this pipeline can be applied on a social multimedia platform for the creation of a large-scale multilingual visual sentiment concept ontology (MVSO). Unlike the flat structure in Borth et al. (2013), our unified ontology is organized hierarchically by multilingual clusters of visually detectable nouns and subclusters of emotionally biased versions of these nouns. In addition, we present an image-based prediction task to show how generalizable language-specific models are in a multilingual context. A new, publicly available dataset of >15.6K sentiment-biased visual concepts across 12 languages with language-specific detector banks, >7.36M images and their metadata is also released.
Pose-Guided Human Parsing with Deep Learned Features
Venue: arXiv cs.CV 2015
Year: 2015

Parsing human body into semantic regions is crucial to human-centric analysis. In this paper, we propose a segment-based parsing pipeline that explores human pose information, i.e. the joint location of a human model, which improves the part proposal, accelerates the inference and regularizes the parsing process at the same time. Specifically, we first generate part segment proposals with respect to human joints predicted by a deep model, then part- specific ranking models are trained for segment selection using both pose-based features and deep-learned part potential features. Finally, the best ensemble of the proposed part segments are inferred though an And-Or Graph. We evaluate our approach on the popular Penn-Fudan pedestrian parsing dataset, and demonstrate the effectiveness of using the pose information for each stage of the parsing pipeline. Finally, we show that our approach yields superior part segmentation accuracy comparing to the state-of-the-art methods.
The AutoProof Verifier: Usability by Non-Experts and on Standard Code
Venue: arXiv cs.SE 2015
Year: 2015

Formal verification tools are often developed by experts for experts; as a result, their usability by programmers with little formal methods experience may be severely limited. In this paper, we discuss this general phenomenon with reference to AutoProof: a tool that can verify the full functional correctness of object-oriented software. In particular, we present our experiences of using AutoProof in two contrasting contexts representative of non-expert usage. First, we discuss its usability by students in a graduate course on software verification, who were tasked with verifying implementations of various sorting algorithms. Second, we evaluate its usability in verifying code developed for programming assignments of an undergraduate course. The first scenario represents usability by serious non-experts; the second represents usability on "standard code", developed without full functional verification in mind. We report our experiences and lessons learnt, from which we derive some general suggestions for furthering the development of verification tools with respect to improving their usability.