OpenRaiser/Intern-Atlas huggingface dataset:
Ray-of-Arrival Passing for Indirect Beam Training in Cooperative Millimeter Wave MIMO Networks
Venue: arXiv cs.IT 2018
Year: 2018

This paper is concerned with the channel estimation problem in multi-cell Millimeter (mmWave) wireless systems. We develop a novel Ray-of-Arrival Passing for Indirect (RAPID) Beam Training framework, in which a network consisting of multiple BS are able to work cooperatively to estimate jointly the UE channels. To achieve this aim, we consider the spatial geometry of the mmWave environment and transform conventional angular domain beamforming concepts into the more euclidean, Ray-based domain. Leveraging this model, we then consider the conditional probabilities that pilot signals are received in each direction, given that the deployment of each BS is known to the network. Simulation results show that RAPID is able to improve the average estimation of the network and significantly increase the rate of poorer quality links. Furthermore, we also show that, when a coverage rate threshold is considered, RAPID is able to improve greatly the probability that multiple link options will be available to a user at any given time.
Efficient Calculation of Meta Distributions and the Performance of User Percentiles
Venue: arXiv cs.IT 2018
Year: 2018

Meta distributions (MDs) are refined performance metrics in wireless networks modeled using point processes. While there is no known method to directly calculate MDs, the moments of the underlying conditional distributions (given the point process) can often be expressed in exact analytical form. The problem of finding the MD given the moments has several solutions, but the standard approaches are inefficient and sensitive to the choices of a number of parameters. Here we propose and explore the use of a method based on binomial mixtures, which has several key advantages over other methods, since it is based on a simple linear transform of the moments.
Trees in Partial Higher Dimensional Automata
Venue: arXiv cs.LO 2018
Year: 2018

In this paper, we give a new definition of partial Higher Dimension Automata using lax functors. This definition is simpler and more natural from a categorical point of view, but also matches more clearly the intuition that pHDA are Higher Dimensional Automata with some missing faces. We then focus on trees. Originally, for example in transition systems, trees are defined as those systems that have a unique path property. To understand what kind of unique property is needed in pHDA, we start by looking at trees as colimits of paths. This definition tells us that trees are exactly the pHDA with the unique path property modulo a notion of homotopy, and without any shortcuts. This property allows us to prove two interesting characterisations of trees: trees are exactly those pHDA that are an unfolding of another pHDA; and trees are exactly the cofibrant objects, much as in the language of Quillen's model structure. In particular, this last characterisation gives the premisses of a new understanding of concurrency theory using homotopy theory.
Partial complementation of graphs
Venue: arXiv cs.CC 2018
Year: 2018

A partial complement of the graph $G$ is a graph obtained from $G$ by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph $G$ and graph class $\mathcal{G}$, is there a partial complement of $G$ which is in $\mathcal{G}$? We show that this problem can be solved in polynomial time for various choices of the graphs class $\mathcal{G}$, such as bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when $\mathcal{G}$ is the class of $r$-regular graphs.
Embedding with a Rigid Substructure
Venue: arXiv cs.NA 2018
Year: 2018

This paper presents a new distance geometry algorithm for calculating atomic coordinates from estimates of the interatomic distances, which maintains the positions of the atoms in a known rigid substructure. Given an $M \times 3$ matrix of coordinates for the rigid substructure $\mathbf X$, this problem consists of finding the $N \times 3$ matrix $\mathbf Y$ that yields of global minimum of the so-called STRAIN, i.e. \[ \min_{\mathbf Y} \left\| \begin{bmatrix} \mathbf{XX}^\top & \mathbf{XY}^\top \\ \mathbf{YX}^\top & \mathbf{YY}^\top \end{bmatrix} \,-\, \begin{bmatrix} \mathbf A & \mathbf B \\ \mathbf B^\top & \mathbf C \end{bmatrix} \right\|_{\mathsf F}^2 ~, \] where $\mathbf A = \mathbf{XX}^\top$ , and $\mathbf B, \mathbf C$ are matrices of inner products calculated from the estimated distances. The vanishing of the gradient of the STRAIN is shown to be equivalent to a system of only six nonlinear equations in six unknowns for the inertial tensor associated with the solution Y . The entire solution space is characterized in terms of the geometry of the intersection curves between the unit sphere and certain variable ellipsoids. Upon deriving tight bilateral bounds on the moments of inertia of any possible solution, we construct a search procedure that reliably locates the global minimum. The effectiveness of this method is demonstrated on realistic simulated and chemical test problems.
Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
Venue: arXiv cs.LO 2018
Year: 2018

Vector Addition Systems with States (VASS) provide a well-known and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract models of programs in resource bound analysis. In this paper we study the problem of obtaining asymptotic bounds on the termination time of a given VASS. In particular, we focus on the practically important case of obtaining polynomial bounds on termination time. Our main contributions are as follows: First, we present a polynomial-time algorithm for deciding whether a given VASS has a linear asymptotic complexity. We also show that if the complexity of a VASS is not linear, it is at least quadratic. Second, we classify VASS according to quantitative properties of their cycles. We show that certain singularities in these properties are the key reason for non-polynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form $Θ(n^k)$, for some integer $k\leq d$, where $d$ is the dimension of the VASS. We present a polynomial-time algorithm computing the optimal $k$. For general VASS, the same algorithm, which is based on a complete technique for the construction of ranking functions in VASS, produces a valid lower bound, i.e., a $k$ such that the termination complexity is $Ω(n^k)$. Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis.
Automatic Documentation of ICD Codes with Far-Field Speech Recognition
Venue: arXiv cs.SD 2018
Year: 2018

Documentation errors increase healthcare costs and cause unnecessary patient deaths. As the standard language for diagnoses and billing, ICD codes serve as the foundation for medical documentation worldwide. Despite the prevalence of electronic medical records, hospitals still witness high levels of ICD miscoding. In this paper, we propose to automatically document ICD codes with far-field speech recognition. Far-field speech occurs when the microphone is located several meters from the source, as is common with smart homes and security systems. Our method combines acoustic signal processing with recurrent neural networks to recognize and document ICD codes in real time. To evaluate our model, we collected a far-field speech dataset of ICD-10 codes and found our model to achieve 87% accuracy with a BLEU score of 85%. By sampling from an unsupervised medical language model, our method is able to outperform existing methods. Overall, this work shows the potential of automatic speech recognition to provide efficient, accurate, and cost-effective healthcare documentation.
Towards the Automation of Metamorphic Testing in Model Transformations
Venue: arXiv cs.SE 2018
Year: 2018

Model transformations are the cornerstone of Model-Driven Engineering, and provide the essential mechanisms for manipulating and transforming models. Checking whether the output of a model transformation is correct is a manual and error-prone task, this is referred to as the oracle problem in the software testing literature. The correctness of the model transformation program is crucial for the proper generation of its output, so it should be tested. Metamorphic testing is a testing technique to alleviate the oracle problem consisting on exploiting the relations between different inputs and outputs of the program under test, so-called metamorphic relations. In this paper we give an insight into our approach to generically define metamorphic relations for model transformations, which can be automatically instantiated given any specific model transformation.
Author-topic profiles for academic search
Venue: arXiv cs.IR 2018
Year: 2018

We implemented and evaluated a two-stage retrieval method for personalized academic search in which the initial search results are re-ranked using an author-topic profile. In academic search tasks, the user's own data can help optimizing the ranking of search results to match the searcher's specific individual needs. The author-topic profile consists of topic-specific terms, stored in a graph. We re-rank the top-1000 retrieved documents using ten features that represent the similarity between the document and the author-topic graph. We found that the re-ranking gives a small but significant improvement over the reproduced best method from the literature. Storing the profile as a graph has a number of advantages: it is flexible with respect to node and relation types; it is a visualization of knowledge that is interpretable by the user, and it offers the possibility to view relational characteristics of individual nodes.
Q-Map: Clinical Concept Mining from Clinical Documents
Venue: arXiv cs.IR 2018
Year: 2018

Over the past decade, there has been a steep rise in the data-driven analysis in major areas of medicine, such as clinical decision support system, survival analysis, patient similarity analysis, image analytics etc. Most of the data in the field are well-structured and available in numerical or categorical formats which can be used for experiments directly. But on the opposite end of the spectrum, there exists a wide expanse of data that is intractable for direct analysis owing to its unstructured nature which can be found in the form of discharge summaries, clinical notes, procedural notes which are in human written narrative format and neither have any relational model nor any standard grammatical structure. An important step in the utilization of these texts for such studies is to transform and process the data to retrieve structured information from the haystack of irrelevant data using information retrieval and data mining techniques. To address this problem, the authors present Q-Map in this paper, which is a simple yet robust system that can sift through massive datasets with unregulated formats to retrieve structured information aggressively and efficiently. It is backed by an effective mining technique which is based on a string matching algorithm that is indexed on curated knowledge sources, that is both fast and configurable. The authors also briefly examine its comparative performance with MetaMap, one of the most reputed tools for medical concepts retrieval and present the advantages the former displays over the latter.
Control strategies for off-line testing of timed systems
Venue: arXiv cs.FL 2018
Year: 2018

Partial observability and controllability are two well-known issues in test-case synthesis for interactive systems. We address the problem of partial control in the synthesis of test cases from timed-automata specifications. Building on the tioco timed testing framework, we extend a previous game interpretation of the test-synthesis problem from the untimed to the timed setting. This extension requires a deep reworking of the models, game interpretation and test-synthesis algorithms. We exhibit strategies of a game that tries to minimize both control losses and distance to the satisfaction of a test purpose, and prove they are winning under some fairness assumptions. This entails that when turning those strategies into test cases, we get properties such as soundness and exhaustiveness of the test synthesis method.
Privacy Preserving Machine Learning: Threats and Solutions
Venue: arXiv cs.CR 2018
Year: 2018

For privacy concerns to be addressed adequately in current machine learning systems, the knowledge gap between the machine learning and privacy communities must be bridged. This article aims to provide an introduction to the intersection of both fields with special emphasis on the techniques used to protect the data.
Violence originated from Facebook: A case study in Bangladesh
Venue: arXiv cs.CY 2018
Year: 2018

Facebook as in social network is a great innovation of modern times. Among all social networking sites, Facebook is the most popular social network all over the world. Bangladesh is no exception. People use Facebook for various reasons e.g. social networking and communication, online shopping and business, knowledge and experience sharing etc. However, some recent incidents in Bangladesh, originated from or based on Facebook activities, led to arson and violence. Social network i.e. Facebook was used in these incidents mostly as a tool to trigger hatred and violence. This case study discusses these technology related incidents and recommends possible future measurements to prevent such violence.
Proof-relevant Horn Clauses for Dependent Type Inference and Term Synthesis
Venue: arXiv cs.LO 2018
Year: 2018

First-order resolution has been used for type inference for many years, including in Hindley- Milner type inference, type-classes, and constrained data types. Dependent types are a new trend in functional languages. In this paper, we show that proof-relevant first-order resolution can play an important role in automating type inference and term synthesis for dependently typed languages. We propose a calculus that translates type inference and term synthesis problems in a dependently typed language to a logic program and a goal in the proof-relevant first-order Horn clause logic. The computed answer substitution and proof term then provide a solution to the given type inference and term synthesis problem. We prove the decidability and soundness of our method. The paper is under consideration for acceptance in TPLP.
Reflections on digital innovation
Venue: arXiv cs.CY 2018
Year: 2018

The paper by Henfridsson et al. opens up a new agenda for IS research on the content and process of digital innovation. The crucial element in their perspective is the role of recombination in innovation. They supplement an emphasis on design recombination with a symmetrical emphasis on use recombination. While supporting Henfridsson et al.s overall argument, I point out how central parts overlap with and are extended in disciplines outside IS research.
A Formal Transformation Method for Automated Fault Tree Generation from a UML Activity Model
Venue: arXiv cs.SE 2018
Year: 2018

Fault analysis and resolution of faults should be part of any end-to-end system development process. This paper is concerned with developing a formal transformation method that maps control flows modeled in UML Activities to semantically equivalent Fault Trees. The transformation method developed features the use of propositional calculus and probability theory. Fault Propagation Chains are introduced to facilitate the transformation method. An overarching metamodel comprised of transformations between models is developed and is applied to an understood Traffic Management System of Systems problem to demonstrate the approach. In this way, the relational structure of the system behavior model is reflected in the structure of the Fault Tree. The paper concludes with a discussion of limitations of the transformation method and proposes approaches to extend it to object flows, State Machines and functional allocations.
Performance Evaluation of an Algorithm-based Asynchronous Checkpoint-Restart Fault Tolerant Application Using Mixed MPI/GPI-2
Venue: arXiv cs.DC 2018
Year: 2018

One of the hardest challenges of the current Big Data landscape is the lack of ability to process huge volumes of information in an acceptable time. The goal of this work, is to ascertain if it is useful to use typical Big Data tools to solve High Performance Computing problems, by exploring and comparing a distributed computing framework implemented on a commodity cluster architecture: the experiment will depend on the computational time required using tools such as Apache Spark. This will be compared to "equivalent more traditional" approaches such as using a distributed memory model with MPI on a distributed file system such as HDFS (Hadoop Distributed File System) and native C libraries that create an interface to encapsulate this file system functionalities, and using the GPI-2 implementation for the GASPI protocol and it's in-memory checkpointing library to provide an application with Fault Tolerance features. To be more precise, we've chosen the K-means algorithm as experiment, that will be ran on variable size datasets, and then we will compare the computational run time and time resilience of both approaches.
On the iterative refinement of densely connected representation levels for semantic segmentation
Venue: arXiv cs.CV 2018
Year: 2018

State-of-the-art semantic segmentation approaches increase the receptive field of their models by using either a downsampling path composed of poolings/strided convolutions or successive dilated convolutions. However, it is not clear which operation leads to best results. In this paper, we systematically study the differences introduced by distinct receptive field enlargement methods and their impact on the performance of a novel architecture, called Fully Convolutional DenseResNet (FC-DRN). FC-DRN has a densely connected backbone composed of residual networks. Following standard image segmentation architectures, receptive field enlargement operations that change the representation level are interleaved among residual networks. This allows the model to exploit the benefits of both residual and dense connectivity patterns, namely: gradient flow, iterative refinement of representations, multi-scale feature combination and deep supervision. In order to highlight the potential of our model, we test it on the challenging CamVid urban scene understanding benchmark and make the following observations: 1) downsampling operations outperform dilations when the model is trained from scratch, 2) dilations are useful during the finetuning step of the model, 3) coarser representations require less refinement steps, and 4) ResNets (by model construction) are good regularizers, since they can reduce the model capacity when needed. Finally, we compare our architecture to alternative methods and report state-of-the-art result on the Camvid dataset, with at least twice fewer parameters.
Universality in Freezing Cellular Automata
Venue: arXiv cs.CC 2018
Year: 2018

Cellular Automata have been used since their introduction as a discrete tool of modelization. In many of the physical processes one may modelize thus (such as bootstrap percolation, forest fire or epidemic propagation models, life without death, etc), each local change is irreversible. The class of freezing Cellular Automata (FCA) captures this feature. In a freezing cellular automaton the states are ordered and the cells can only decrease their state according to this "freezing-order". We investigate the dynamics of such systems through the questions of simulation and universality in this class: is there a Freezing Cellular Automaton (FCA) that is able to simulate any Freezing Cellular Automata, i.e. an intrinsically universal FCA? We show that the answer to that question is sensitive to both the number of changes cells are allowed to make, and geometric features of the space. In dimension 1, there is no universal FCA. In dimension 2, if either the number of changes is at least 2, or the neighborhood is Moore, then there are universal FCA. On the other hand, there is no universal FCA with one change and Von Neumann neighborhood. We also show that monotonicity of the local rule with respect to the freezing-order (a common feature of bootstrap percolation) is also an obstacle to universality.
A General Framework for Relational Parametricity
Venue: arXiv cs.LO 2018
Year: 2018

Reynolds' original theory of relational parametricity was intended to capture the idea that polymorphically typed System F programs preserve all relations between inputs. But as Reynolds himself later showed, his theory can only be formalized in a meta-theory with an impredicative universe, such as the Calculus of Inductive Constructions. Abstracting from Reynolds' ideas, Dunphy and Reddy developed their well-known framework for parametricity that uses parametric limits in reflexive graph categories and aims to subsume a variety of parametric models. As we observe, however, their theory is not sufficiently general to subsume the very model that inspired parametricity, namely Reynolds' original model, expressed inside type theory. To correct this, we develop an abstract framework for relational parametricity that generalizes the notion of a reflexive graph categories and delivers Reynolds' model as a direct instance in a natural way. This framework is uniform with respect to a choice of meta-theory, which allows us to obtain the well-known PER model of Longo and Moggi as a direct instance in a natural way as well. In addition, we offer two novel relationally parametric models of System F: i) a categorical version of Reynolds' model, where types are functorial on isomorphisms and all polymorphic functions respect the functorial action, and ii) a proof-relevant categorical version of Reynolds' model (after Orsanigo), where, additionally, witnesses of relatedness are themselves suitably related. We show that, unlike previously existing frameworks for parametricity, ours recognizes both of these new models in a natural way. Our framework is thus descriptive, in that it accounts for well-known models, as well as prescriptive, in that it identifies abstract properties that good models of relational parametricity should satisfy and suggests new constructions of such models.
New Methods of Studying Valley Fitness Landscapes
Venue: arXiv cs.NE 2018
Year: 2018

The word "valley" is a popular term used in intuitively describing fitness landscapes. What is a valley on a fitness landscape? How to identify the direction and location of a valley if it exists? However, such questions are seldom rigorously studied in evolutionary optimization especially when the search space is a high dimensional continuous space. This paper presents two methods of studying valleys on a fitness landscape. The first method is based on the topological homeomorphism. It establishes a rigorous definition of a valley. A valley is regarded as a one-dimensional manifold. The second method takes a different viewpoint from statistics. It provides an algorithm of identifying the valley direction and location using principle component analysis.