OpenRaiser/Intern-Atlas huggingface dataset:
Deterministic Logics for UL
Venue: arXiv cs.FL 2014
Year: 2014

The class of Unambiguous Star-Free Regular Languages (UL) was defined by Schutzenberger as the class of languages defined by Unambiguous Polynomials. UL has been variously characterized (over finite words) by logics such as TL[X_a,Y_a], UITL, TL[F,P], FO2[<], the variety DA of monoids, as well as partially-ordered two-way DFA (po2DFA). We revisit this language class with emphasis on notion of unambiguity and develop on the concept of Deterministic Logics for UL. The formulas of deterministic logics uniquely parse a word in order to evaluate satisfaction. We show that several deterministic logics robustly characterize UL. Moreover, we derive constructive reductions from these logics to the po2DFA automata. These reductions also allow us to show NP-complete satisfaction complexity for the deterministic logics considered. Logics such as TL[F,P], FO2[<] are not deterministic and have been shown to characterize UL using algebraic methods. However there has been no known constructive reduction from these logics to po2DFA. We use deterministic logics to bridge this gap. The language-equivalent po2DFA for a given TL[F,P] formula is constructed and we analyze its size relative to the size of the TL[F,P] formula. This is an efficient reduction which gives an alternate proof to NP-complete satisfiability complexity of TL[F,P] formulas.
A hierarchically blocked Jacobi SVD algorithm for single and multiple graphics processing units
Venue: arXiv cs.NA 2014
Year: 2014

We present a hierarchically blocked one-sided Jacobi algorithm for the singular value decomposition (SVD), targeting both single and multiple graphics processing units (GPUs). The blocking structure reflects the levels of GPU's memory hierarchy. The algorithm may outperform MAGMA's dgesvd, while retaining high relative accuracy. To this end, we developed a family of parallel pivot strategies on GPU's shared address space, but applicable also to inter-GPU communication. Unlike common hybrid approaches, our algorithm in a single GPU setting needs a CPU for the controlling purposes only, while utilizing GPU's resources to the fullest extent permitted by the hardware. When required by the problem size, the algorithm, in principle, scales to an arbitrary number of GPU nodes. The scalability is demonstrated by more than twofold speedup for sufficiently large matrices on a Tesla S2050 system with four GPUs vs. a single Fermi card.
Predicting Defect Content and Quality Assurance Effectiveness by Combining Expert Judgment and Defect Data - A Case Study
Venue: arXiv cs.SE 2014
Year: 2014

Planning quality assurance (QA) activities in a systematic way and controlling their execution are challenging tasks for companies that develop software or software-intensive systems. Both require estimation capabilities regarding the effectiveness of the applied QA techniques and the defect content of the checked artifacts. Existing approaches for these purposes need extensive measurement data from historical projects. Due to the fact that many companies do not collect enough data for applying these approaches (especially for the early project lifecycle), they typically base their QA planning and controlling solely on expert opinion. This article presents a hybrid method that combines commonly available measurement data and context-specific expert knowledge. To evaluate the method's applicability and usefulness, we conducted a case study in the context of independent verification and validation activities for critical software in the space domain. A hybrid defect content and effectiveness model was developed for the software requirements analysis phase and evaluated with available legacy data. One major result is that the hybrid model provides improved estimation accuracy when compared to applicable models based solely on data. The mean magnitude of relative error (MMRE) determined by cross-validation is 29.6% compared to 76.5% obtained by the most accurate data-based model.
Exact Optimized-cost Repair in Multi-hop Distributed Storage Networks
Venue: arXiv cs.IT 2014
Year: 2014

The problem of exact repair of a failed node in multi-hop networked distributed storage systems is considered. Contrary to the most of the current studies which model the repair process by the direct links from surviving nodes to the new node, the repair is modeled by considering the multi-hop network structure, and taking into account that there might not exist direct links from all the surviving nodes to the new node. In the repair problem of these systems, surviving nodes may cooperate to transmit the repair traffic to the new node. In this setting, we define the total number of packets transmitted between nodes as repair-cost. A lower bound of the repaircost can thus be found by cut-set bound analysis. In this paper, we show that the lower bound of the repair-cost is achievable for the exact repair of MDS codes in tandem and grid networks, thus resulting in the minimum-cost exact MDS codes. Further, two suboptimal (achievable) bounds for the large scale grid networks are proposed.
Patents as Instruments for Exploring Innovation Dynamics: Geographic and Technological Perspectives on "Photovoltaic Cells"
Venue: arXiv cs.CY 2014
Year: 2014

The dynamics of innovation are nonlinear and complex: geographical, technological, and economic selection environments can be expected to interact. Can patents provide an analytical lens to this process in terms of different attributes such as inventor addresses, classification codes, backward and forward citations, etc.? Two recently developed patent maps with interactive overlay techniques--Google Maps and maps based on citation relations among International Patent Classifications (IPC)--are elaborated into dynamic versions that allow for online animations and comparisons by using split screens. Various forms of animation are explored. The recently developed Cooperative Patent Classifications (CPC) of the U.S. Patent and Trade Office (USPTO) and the European Patent Office (EPO) provide new options for a precise delineation of samples in both USPTO data and the Worldwide Patent Statistics Database (PatStat) of EPO. Among the "technologies for the mitigation of climate change" (class Y02), we zoom in on nine material technologies for photovoltaic cells; and focus on one of them (CuInSe2) as a lead case. The longitudinal development of Rao-Stirling diversity in the IPC-based maps provides a heuristics for studying technological generations during the period under study (1975-2012). The sequencing of generations prevails in USPTO data more than in PatStat data because PatStat aggregates patent information from countries in different stages of technological development, whereas one can expect USPTO patents to be competitive at the technological edge.
GPS-ABC: Gaussian Process Surrogate Approximate Bayesian Computation
Venue: arXiv cs.LG 2014
Year: 2014

Scientists often express their understanding of the world through a computationally demanding simulation program. Analyzing the posterior distribution of the parameters given observations (the inverse problem) can be extremely challenging. The Approximate Bayesian Computation (ABC) framework is the standard statistical tool to handle these likelihood free problems, but they require a very large number of simulations. In this work we develop two new ABC sampling algorithms that significantly reduce the number of simulations necessary for posterior inference. Both algorithms use confidence estimates for the accept probability in the Metropolis Hastings step to adaptively choose the number of necessary simulations. Our GPS-ABC algorithm stores the information obtained from every simulation in a Gaussian process which acts as a surrogate function for the simulated statistics. Experiments on a challenging realistic biological problem illustrate the potential of these algorithms.
Information Entropy Dynamics and Maximum Entropy Production Principle
Venue: arXiv cs.IT 2014
Year: 2014

The asymptotic convergence of probability density function (pdf) and convergence of differential entropy are examined for the non-stationary processes that follow the maximum entropy principle (MaxEnt) and maximum entropy production principle (MEPP). Asymptotic convergence of pdf provides new justification of MEPP while convergence of differential entropy is important in asymptotic analysis of communication systems. A set of equations describing the dynamics of pdf under mass conservation and energy conservation constraints is derived. It is shown that for pdfs with compact carrier the limit pdf is unique and can be obtained from Jaynes's MaxEnt principle.
Resilience in Numerical Methods: A Position on Fault Models and Methodologies
Venue: arXiv cs.MS 2014
Year: 2014

Future extreme-scale computer systems may expose silent data corruption (SDC) to applications, in order to save energy or increase performance. However, resilience research struggles to come up with useful abstract programming models for reasoning about SDC. Existing work randomly flips bits in running applications, but this only shows average-case behavior for a low-level, artificial hardware model. Algorithm developers need to understand worst-case behavior with the higher-level data types they actually use, in order to make their algorithms more resilient. Also, we know so little about how SDC may manifest in future hardware, that it seems premature to draw conclusions about the average case. We argue instead that numerical algorithms can benefit from a numerical unreliability fault model, where faults manifest as unbounded perturbations to floating-point data. Algorithms can use inexpensive "sanity" checks that bound or exclude error in the results of computations. Given a selective reliability programming model that requires reliability only when and where needed, such checks can make algorithms reliable despite unbounded faults. Sanity checks, and in general a healthy skepticism about the correctness of subroutines, are wise even if hardware is perfectly reliable.
Interference Alignment (IA) and Coordinated Multi-Point (CoMP) overheads and RF impairments: testbed results
Venue: arXiv cs.IT 2014
Year: 2014

In this work we investigate the network MIMO techniques of interference alignment (IA) and fully adaptive joint transmission coordinated multipoint (CoMP) in an indoor very small cell environment. Our focus is on the overheads in a system with quantized channel state feedback from the receiver to the transmitter (based on the 802.11ac standard) and on the impact of non-ideal hardware. The indoor office scenario should be the most favourable case in terms of the required feedback rates due to the large coherence bandwidth and coherence time of the channel. The evaluations are done using a real-world wireless testbed with three BSs and three MSs all having two antennas. The signal to noise ratio in the measurements is very high, 35-60dB, due to the short transmission range. Under such conditions radio hardware impairments becomes a major limitation on the performance. We quantify the impact of these impairments. For a 23ms update interval the overhead is 2.5% and IA and CoMP improves the sum throughput 27% and 47% in average (over the reference schemes e.g. TDMA MIMO), under stationary conditions. When two people are walking in the measurement area the throughput improvements drops to 16% and 45%, respectively.
Exploiting all phone media? A multidimensional network analysis of phone users' sociality
Venue: arXiv cs.SI 2014
Year: 2014

The growing awareness that human communications and social interactions are assuming a stratified structure, due to the availability of multiple techno-communication channels, including online social networks, mobile phone calls, short messages (SMS) and e-mails, has recently led to the study of multidimensional networks, as a step further the classical Social Network Analysis. A few papers have been dedicated to develop the theoretical framework to deal with such multiplex networks and to analyze some example of multidimensional social networks. In this context we perform the first study of the multiplex mobile social network, gathered from the records of both call and text message activities of millions of users of a large mobile phone operator over a period of 12 weeks. While social networks constructed from mobile phone datasets have drawn great attention in recent years, so far studies have dealt with text message and call data, separately, providing a very partial view of people sociality expressed on phone. Here we analyze how the call and the text message dimensions overlap showing how many information about links and nodes could be lost only accounting for a single layer and how users adopt different media channels to interact with their neighborhood.
From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance
Venue: arXiv cs.IT 2014
Year: 2014

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family ${\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}$, where $C_α \big |_{α= 1}$ is the original polar code, and $C_α \big |_{α= 0}$ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of $α$. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family ${\mathcal C}_{\rm inter}$ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
Dynamic Topology Adaptation and Distributed Estimation for Smart Grids
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents new dynamic topology adaptation strategies for distributed estimation in smart grids systems. We propose a dynamic exhaustive search--based topology adaptation algorithm and a dynamic sparsity--inspired topology adaptation algorithm, which can exploit the topology of smart grids with poor--quality links and obtain performance gains. We incorporate an optimized combining rule, named Hastings rule into our proposed dynamic topology adaptation algorithms. Compared with the existing works in the literature on distributed estimation, the proposed algorithms have a better convergence rate and significantly improve the system performance. The performance of the proposed algorithms is compared with that of existing algorithms in the IEEE 14--bus system.
Flexible Backhaul Design and Degrees of Freedom for Linear Interference Networks
Venue: arXiv cs.IT 2014
Year: 2014

The considered problem is that of maximizing the degrees of freedom (DoF) in cellular downlink, under a backhaul load constraint that limits the number of messages that can be delivered from a centralized controller to the base station transmitters. A linear interference channel model is considered, where each transmitter is connected to the receiver having the same index as well as one succeeding receiver. The backhaul load is defined as the sum of all the messages available at all the transmitters normalized by the number of users. When the backhaul load is constrained to an integer level B, the asymptotic per user DoF is shown to equal (4B-1)/(4B), and it is shown that the optimal assignment of messages to transmitters is asymmetric and satisfies a local cooperation constraint and that the optimal coding scheme relies only on zero-forcing transmit beamforming. Finally, an extension of the presented coding scheme is shown to apply for more general locally connected and two-dimensional networks.
Promises, Impositions, and other Directionals
Venue: arXiv cs.MA 2014
Year: 2014

Promises, impositions, proposals, predictions, and suggestions are categorized as voluntary co-operational methods. The class of voluntary co-operational methods is included in the class of so-called directionals. Directionals are mechanisms supporting the mutual coordination of autonomous agents. Notations are provided capable of expressing residual fragments of directionals. An extensive example, involving promises about the suitability of programs for tasks imposed on the promisee is presented. The example illustrates the dynamics of promises and more specifically the corresponding mechanism of trust updating and credibility updating. Trust levels and credibility levels then determine the way certain promises and impositions are handled. The ubiquity of promises and impositions is further demonstrated with two extensive examples involving human behaviour: an artificial example about an agent planning a purchase, and a realistic example describing technology mediated interaction concerning the solution of pay station failure related problems arising for an agent intending to leave the parking area.
Infinite Mixed Membership Matrix Factorization
Venue: arXiv cs.LG 2014
Year: 2014

Rating and recommendation systems have become a popular application area for applying a suite of machine learning techniques. Current approaches rely primarily on probabilistic interpretations and extensions of matrix factorization, which factorizes a user-item ratings matrix into latent user and item vectors. Most of these methods fail to model significant variations in item ratings from otherwise similar users, a phenomenon known as the "Napoleon Dynamite" effect. Recent efforts have addressed this problem by adding a contextual bias term to the rating, which captures the mood under which a user rates an item or the context in which an item is rated by a user. In this work, we extend this model in a nonparametric sense by learning the optimal number of moods or contexts from the data, and derive Gibbs sampling inference procedures for our model. We evaluate our approach on the MovieLens 1M dataset, and show significant improvements over the optimal parametric baseline, more than twice the improvements previously encountered for this task. We also extract and evaluate a DBLP dataset, wherein we predict the number of papers co-authored by two authors, and present improvements over the parametric baseline on this alternative domain as well.
Compositional Belief Update
Venue: arXiv cs.AI 2014
Year: 2014

In this paper we explore a class of belief update operators, in which the definition of the operator is compositional with respect to the sentence to be added. The goal is to provide an update operator that is intuitive, in that its definition is based on a recursive decomposition of the update sentences structure, and that may be reasonably implemented. In addressing update, we first provide a definition phrased in terms of the models of a knowledge base. While this operator satisfies a core group of the benchmark Katsuno-Mendelzon update postulates, not all of the postulates are satisfied. Other Katsuno-Mendelzon postulates can be obtained by suitably restricting the syntactic form of the sentence for update, as we show. In restricting the syntactic form of the sentence for update, we also obtain a hierarchy of update operators with Winsletts standard semantics as the most basic interesting approach captured. We subsequently give an algorithm which captures this approach; in the general case the algorithm is exponential, but with some not-unreasonable assumptions we obtain an algorithm that is linear in the size of the knowledge base. Hence the resulting approach has much better complexity characteristics than other operators in some situations. We also explore other compositional belief change operators: erasure is developed as a dual operator to update; we show that a forget operator is definable in terms of update; and we give a definition of the compositional revision operator. We obtain that compositional revision, under the most natural definition, yields the Satoh revision operator.
Learning Partially Observable Deterministic Action Models
Venue: arXiv cs.AI 2014
Year: 2014

We present exact algorithms for identifying deterministic-actions effects and preconditions in dynamic partially observable domains. They apply when one does not know the action model(the way actions affect the world) of a domain and must learn it from partial observations over time. Such scenarios are common in real world applications. They are challenging for AI tasks because traditional domain structures that underly tractability (e.g., conditional independence) fail there (e.g., world features become correlated). Our work departs from traditional assumptions about partial observations and action models. In particular, it focuses on problems in which actions are deterministic of simple logical structure and observation models have all features observed with some frequency. We yield tractable algorithms for the modified problem for such domains. Our algorithms take sequences of partial observations over time as input, and output deterministic action models that could have lead to those observations. The algorithms output all or one of those models (depending on our choice), and are exact in that no model is misclassified given the observations. Our algorithms take polynomial time in the number of time steps and state features for some traditional action classes examined in the AI-planning literature, e.g., STRIPS actions. In contrast, traditional approaches for HMMs and Reinforcement Learning are inexact and exponentially intractable for such domains. Our experiments verify the theoretical tractability guarantees, and show that we identify action models exactly. Several applications in planning, autonomous exploration, and adventure-game playing already use these results. They are also promising for probabilistic settings, partially observable reinforcement learning, and diagnosis.
Completeness and Performance Of The APO Algorithm
Venue: arXiv cs.AI 2014
Year: 2014

Asynchronous Partial Overlay (APO) is a search algorithm that uses cooperative mediation to solve Distributed Constraint Satisfaction Problems (DisCSPs). The algorithm partitions the search into different subproblems of the DisCSP. The original proof of completeness of the APO algorithm is based on the growth of the size of the subproblems. The present paper demonstrates that this expected growth of subproblems does not occur in some situations, leading to a termination problem of the algorithm. The problematic parts in the APO algorithm that interfere with its completeness are identified and necessary modifications to the algorithm that fix these problematic parts are given. The resulting version of the algorithm, Complete Asynchronous Partial Overlay (CompAPO), ensures its completeness. Formal proofs for the soundness and completeness of CompAPO are given. A detailed performance evaluation of CompAPO comparing it to other DisCSP algorithms is presented, along with an extensive experimental evaluation of the algorithm's unique behavior. Additionally, an optimization version of the algorithm, CompOptAPO, is presented, discussed, and evaluated.