OpenRaiser/Intern-Atlas huggingface dataset:
Identification of Pleonastic It Using the Web
Venue: arXiv cs.CL 2014
Year: 2014

In a significant minority of cases, certain pronouns, especially the pronoun it, can be used without referring to any specific entity. This phenomenon of pleonastic pronoun usage poses serious problems for systems aiming at even a shallow understanding of natural language texts. In this paper, a novel approach is proposed to identify such uses of it: the extrapositional cases are identified using a series of queries against the web, and the cleft cases are identified using a simple set of syntactic rules. The system is evaluated with four sets of news articles containing 679 extrapositional cases as well as 78 cleft constructs. The identification results are comparable to those obtained by human efforts.
Low-Complexity Polynomial Channel Estimation in Large-Scale MIMO with Arbitrary Statistics
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers pilot-based channel estimation in large-scale multiple-input multiple-output (MIMO) communication systems, also known as massive MIMO, where there are hundreds of antennas at one side of the link. Motivated by the fact that computational complexity is one of the main challenges in such systems, a set of low-complexity Bayesian channel estimators, coined Polynomial ExpAnsion CHannel (PEACH) estimators, are introduced for arbitrary channel and interference statistics. While the conventional minimum mean square error (MMSE) estimator has cubic complexity in the dimension of the covariance matrices, due to an inversion operation, our proposed estimators significantly reduce this to square complexity by approximating the inverse by a L-degree matrix polynomial. The coefficients of the polynomial are optimized to minimize the mean square error (MSE) of the estimate. We show numerically that near-optimal MSEs are achieved with low polynomial degrees. We also derive the exact computational complexity of the proposed estimators, in terms of the floating-point operations (FLOPs), by which we prove that the proposed estimators outperform the conventional estimators in large-scale MIMO systems of practical dimensions while providing a reasonable MSEs. Moreover, we show that L needs not scale with the system dimensions to maintain a certain normalized MSE. By analyzing different interference scenarios, we observe that the relative MSE loss of using the low-complexity PEACH estimators is smaller in realistic scenarios with pilot contamination. On the other hand, PEACH estimators are not well suited for noise-limited scenarios with high pilot power; therefore, we also introduce the low-complexity diagonalized estimator that performs well in this regime. Finally, we ...
Extracting tag hierarchies
Venue: arXiv cs.IR 2014
Year: 2014

Tagging items with descriptive annotations or keywords is a very natural way to compress and highlight information about the properties of the given entity. Over the years several methods have been proposed for extracting a hierarchy between the tags for systems with a "flat", egalitarian organization of the tags, which is very common when the tags correspond to free words given by numerous independent people. Here we present a complete framework for automated tag hierarchy extraction based on tag occurrence statistics. Along with proposing new algorithms, we are also introducing different quality measures enabling the detailed comparison of competing approaches from different aspects. Furthermore, we set up a synthetic, computer generated benchmark providing a versatile tool for testing, with a couple of tunable parameters capable of generating a wide range of test beds. Beside the computer generated input we also use real data in our studies, including a biological example with a pre-defined hierarchy between the tags. The encouraging similarity between the pre-defined and reconstructed hierarchy, as well as the seemingly meaningful hierarchies obtained for other real systems indicate that tag hierarchy extraction is a very promising direction for further research with a great potential for practical applications.
The Impact of Social Segregation on Human Mobility in Developing and Urbanized Regions
Venue: arXiv cs.SI 2014
Year: 2014

This study leverages mobile phone data to analyze human mobility patterns in developing countries, especially in comparison to more industrialized countries. Developing regions, such as the Ivory Coast, are marked by a number of factors that may influence mobility, such as less infrastructural coverage and maturity, less economic resources and stability, and in some cases, more cultural and language-based diversity. By comparing mobile phone data collected from the Ivory Coast to similar data collected in Portugal, we are able to highlight both qualitative and quantitative differences in mobility patterns - such as differences in likelihood to travel, as well as in the time required to travel - that are relevant to consideration on policy, infrastructure, and economic development. Our study illustrates how cultural and linguistic diversity in developing regions (such as Ivory Coast) can present challenges to mobility models that perform well and were conceptualized in less culturally diverse regions. Finally, we address these challenges by proposing novel techniques to assess the strength of borders in a regional partitioning scheme and to quantify the impact of border strength on mobility model accuracy.
Trusty URIs: Verifiable, Immutable, and Permanent Digital Artifacts for Linked Data
Venue: arXiv cs.CR 2014
Year: 2014

To make digital resources on the web verifiable, immutable, and permanent, we propose a technique to include cryptographic hash values in URIs. We call them trusty URIs and we show how they can be used for approaches like nanopublications to make not only specific resources but their entire reference trees verifiable. Digital artifacts can be identified not only on the byte level but on more abstract levels such as RDF graphs, which means that resources keep their hash values even when presented in a different format. Our approach sticks to the core principles of the web, namely openness and decentralized architecture, is fully compatible with existing standards and protocols, and can therefore be used right away. Evaluation of our reference implementations shows that these desired properties are indeed accomplished by our approach, and that it remains practical even for very large files.
Improving Smartphone Battery Life Utilizing Device-to-device Cooperative Relays Underlaying LTE Networks
Venue: arXiv cs.NI 2014
Year: 2014

The utility of smartphones has been limited to a great extent by their short battery life. In this work, we propose a new approach to prolonging smartphone battery life. We introduce the notions of "valueless" and "valued battery", as being the available battery when the user does or does not have access to a power source, respectively. We propose a cooperative system where users with high battery level help carry the traffic of users with low battery level. Our scheme helps increase the amount of valued battery in the network, thus it reduces the chance of users running out of battery early. Our system can be realized in the form of a proximity service (ProSe) which utilizes a device-to-device (D2D) communication architecture underlaying LTE. We show through simulations that our system reduces the probability of cellular users running out of battery before their target usage time (probability of outage). Our simulator source code is made available to the public.
A Simple and Scalable Static Analysis for Bound Analysis and Amortized Complexity Analysis
Venue: arXiv cs.PL 2014
Year: 2014

We present the first scalable bound analysis that achieves amortized complexity analysis. In contrast to earlier work, our bound analysis is not based on general purpose reasoners such as abstract interpreters, software model checkers or computer algebra tools. Rather, we derive bounds directly from abstract program models, which we obtain from programs by comparatively simple invariant generation and symbolic execution techniques. As a result, we obtain an analysis that is more predictable and more scalable than earlier approaches. Our experiments demonstrate that our analysis is fast and at the same time able to compute bounds for challenging loops in a large real-world benchmark. Technically, our approach is based on lossy vector addition systems (VASS). Our bound analysis first computes a lexicographic ranking function that proves the termination of a VASS, and then derives a bound from this ranking function. Our methodology achieves amortized analysis based on a new insight how lexicographic ranking functions can be used for bound analysis.
Algorithms and Limits for Compact Plan Representations
Venue: arXiv cs.AI 2014
Year: 2014

Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.
Interactions between Knowledge and Time in a First-Order Logic for Multi-Agent Systems: Completeness Results
Venue: arXiv cs.MA 2014
Year: 2014

We investigate a class of first-order temporal-epistemic logics for reasoning about multi-agent systems. We encode typical properties of systems including perfect recall, synchronicity, no learning, and having a unique initial state in terms of variants of quantified interpreted systems, a first-order extension of interpreted systems. We identify several monodic fragments of first-order temporal-epistemic logic and show their completeness with respect to their corresponding classes of quantified interpreted systems.
The Logical Difference for the Lightweight Description Logic EL
Venue: arXiv cs.LO 2014
Year: 2014

We study a logic-based approach to versioning of ontologies. Under this view, ontologies provide answers to queries about some vocabulary of interest. The difference between two versions of an ontology is given by the set of queries that receive different answers. We investigate this approach for terminologies given in the description logic EL extended with role inclusions and domain and range restrictions for three distinct types of queries: subsumption, instance, and conjunctive queries. In all three cases, we present polynomial-time algorithms that decide whether two terminologies give the same answers to queries over a given vocabulary and compute a succinct representation of the difference if it is non- empty. We present an implementation, CEX2, of the developed algorithms for subsumption and instance queries and apply it to distinct versions of Snomed CT and the NCI ontology.
Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
Venue: arXiv cs.CC 2014
Year: 2014

The minimisation problem of a sum of unary and pairwise functions of discrete variables is a general NP-hard problem with wide applications such as computing MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or solving binary Valued Constraint Satisfaction Problems (VCSPs). We study the computational complexity of classes of discrete optimisation problems given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, the only non- trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property. Our results, apart from giving complete classifications in the studied cases, provide guidance in the search for hybrid tractable classes; that is, classes of problems that are not captured by restrictions on the functions (such as submodularity) or the structure of the problem graph (such as bounded treewidth). Furthermore, we introduce a class of problems with convex cardinality functions on cross-free sets of assignments. We prove that while imposing only one of the two conditions renders the problem NP-hard, the conjunction of the two gives rise to a novel tractable class satisfying the cross-free convexity property, which generalises the joint-winner property to problems of unbounded arity.
SAP Speaks PDDL: Exploiting a Software-Engineering Model for Planning in Business Process Management
Venue: arXiv cs.AI 2014
Year: 2014

Planning is concerned with the automated solution of action sequencing problems described in declarative languages giving the action preconditions and effects. One important application area for such technology is the creation of new processes in Business Process Management (BPM), which is essential in an ever more dynamic business environment. A major obstacle for the application of Planning in this area lies in the modeling. Obtaining a suitable model to plan with -- ideally a description in PDDL, the most commonly used planning language -- is often prohibitively complicated and/or costly. Our core observation in this work is that this problem can be ameliorated by leveraging synergies with model-based software development. Our application at SAP, one of the leading vendors of enterprise software, demonstrates that even one-to-one model re-use is possible. The model in question is called Status and Action Management (SAM). It describes the behavior of Business Objects (BO), i.e., large-scale data structures, at a level of abstraction corresponding to the language of business experts. SAM covers more than 400 kinds of BOs, each of which is described in terms of a set of status variables and how their values are required for, and affected by, processing steps (actions) that are atomic from a business perspective. SAM was developed by SAP as part of a major model-based software engineering effort. We show herein that one can use this same model for planning, thus obtaining a BPM planning application that incurs no modeling overhead at all. We compile SAM into a variant of PDDL, and adapt an off-the-shelf planner to solve this kind of problem. Thanks to the resulting technology, business experts may create new processes simply by specifying the desired behavior in terms of status variable value changes: effectively, by describing the process in their own language.
Plan-based Policies for Efficient Multiple Battery Load Management
Venue: arXiv cs.AI 2014
Year: 2014

Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem under uncertainty. We describe the approach we have adopted to modelling and solving this problem, seen as a Markov Decision Problem, building effective policies for battery switching in the face of stochastic load profiles. Our solution exploits and adapts several existing techniques: planning for deterministic mixed discrete-continuous problems and Monte Carlo sampling for policy learning. The paper describes the development of planning techniques to allow solution of the non-linear continuous dynamic models capturing the battery behaviours. This approach depends on carefully handled discretisation of the temporal dimension. The construction of policies is performed using a classification approach and this idea offers opportunities for wider exploitation in other problems. The approach and its generality are described in the paper. Application of the approach leads to construction of policies that, in simulation, significantly outperform those that are currently in use and the best published solutions to the battery management problem. We achieve solutions that achieve more than 99% efficiency in simulation compared with the theoretical limit and do so with far fewer battery switches than existing policies. Behaviour of physical batteries does not exactly match the simulated models for many reasons, so to confirm that our theoretical results can lead to real measured improvements in performance we also conduct and report experiments using a physical test system. These results demonstrate that we can obtain 5%-15% improvement in lifetimes in the case of a two battery system.
Gaussian-binary Restricted Boltzmann Machines on Modeling Natural Image Statistics
Venue: arXiv cs.NE 2014
Year: 2014

We present a theoretical analysis of Gaussian-binary restricted Boltzmann machines (GRBMs) from the perspective of density models. The key aspect of this analysis is to show that GRBMs can be formulated as a constrained mixture of Gaussians, which gives a much better insight into the model's capabilities and limitations. We show that GRBMs are capable of learning meaningful features both in a two-dimensional blind source separation task and in modeling natural images. Further, we show that reported difficulties in training GRBMs are due to the failure of the training algorithm rather than the model itself. Based on our analysis we are able to propose several training recipes, which allowed successful and fast training in our experiments. Finally, we discuss the relationship of GRBMs to several modifications that have been proposed to improve the model.
The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound
Venue: arXiv cs.DC 2014
Year: 2014

Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core thread-parallel adaptations of a state-of-the-art branch and bound algorithm for the maximum clique problem, and provide a novel explanation as to why they are successful. We show that load balance is sometimes a problem, but that the interaction of parallel search order and the most likely location of solutions within the search space is often the dominating consideration. We use this explanation to propose a new low-overhead, scalable work splitting mechanism. Our approach uses explicit early diversity to avoid strong commitment to the weakest heuristic advice, and late resplitting for balance. More generally, we argue that for branch and bound, parallel algorithm design should not be performed independently of the underlying sequential algorithm.
How are excellent (highly cited) papers defined in bibliometrics? A quantitative analysis of the literature
Venue: arXiv cs.DL 2014
Year: 2014

As the subject of research excellence has received increasing attention (in science policy) over the last few decades, increasing numbers of bibliometric studies have been published dealing with excellent papers. However, many different methods have been used in these studies to identify excellent papers. The present quantitative analysis of the literature has been carried out in order to acquire an overview of these methods and an indication of an "average" or "most frequent" bibliometric practice. The search in the Web of Science yielded 321 papers dealing with "highly cited", "most cited", "top cited" and "most frequently cited". Of the 321 papers, 16 could not be used in this study. In around 80% of the papers analyzed in this study, a quantitative definition has been provided with which to identify excellent papers. With definitions which relate to an absolute number, either a certain number of top cited papers (58%) or papers with a minimum number of citations are selected (17%). Around 23% worked with percentile rank classes. Over these papers, there is an arithmetic average of the top 7.6% (arithmetic average) or of the top 3% (median). The top 1% is used most frequently in the papers, followed by the top 10%. With the thresholds presented in this study, in future, it will be possible to identify excellent papers based on an "average" or "most frequent" practice among bibliometricians.
Collaboration in the open-source arena: The WebKit case
Venue: arXiv cs.CY 2014
Year: 2014

In an era of software crisis, the move of firms towards distributed software development teams is being challenged by emerging collaboration issues. On this matter, the open-source phenomenon may shed some light, as successful cases on distributed collaboration in the open-source community have been recurrently reported. In this paper, we explore the collaboration networks in the WebKit open-source project, by mining WebKit's source-code version-control-system data with Social Network Analysis (SNA). Our approach allows us to observe how key events in the mobile-device industry have affected the WebKit collaboration network over time. With our findings, we show the explanation power from network visualizations capturing the collaborative dynamics of a high-networked software project over time; and highlight the power of the open-source fork concept as a nexus enabling both features of competition and collaboration. We also reveal the WebKit project as a valuable research site manifesting the novel notion of open-coopetition, where rival firms collaborate with competitors in the open-source community.
A Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials
Venue: arXiv cs.NA 2014
Year: 2014

Let $p\in\mathbb{Z}[x]$ be an arbitrary polynomial of degree $n$ with $k$ non-zero integer coefficients of absolute value less than $2^τ$. In this paper, we answer the open question whether the real roots of $p$ can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of $p$. More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of $p$ with $O(k^3\cdot\log(nτ)\cdot \log n)$ many exact arithmetic operations over the rational numbers. When using approximate but certified arithmetic, the bit complexity of our algorithm is bounded by $\tilde{O}(k^4\cdot nτ)$, where $\tilde{O}(\cdot)$ means that we ignore logarithmic. Hence, for sufficiently sparse polynomials (i.e. $k=O(\log^c (nτ))$ for a positive constant $c$), the bit complexity is $\tilde{O}(nτ)$. We also prove that the latter bound is optimal up to logarithmic factors.
Constant Compositions in the Sphere Packing Bound for Classical-Quantum Channels
Venue: arXiv cs.IT 2014
Year: 2014

The sphere packing bound, in the form given by Shannon, Gallager and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is then applied to auxiliary channels to deduce a bound which can be interpreted as an extension of the Elias bound.