OpenRaiser/Intern-Atlas huggingface dataset:
Concept Extraction to Identify Adverse Drug Reactions in Medical Forums: A Comparison of Algorithms
Venue: arXiv cs.AI 2015
Year: 2015

Social media is becoming an increasingly important source of information to complement traditional pharmacovigilance methods. In order to identify signals of potential adverse drug reactions, it is necessary to first identify medical concepts in the social media text. Most of the existing studies use dictionary-based methods which are not evaluated independently from the overall signal detection task. We compare different approaches to automatically identify and normalise medical concepts in consumer reviews in medical forums. Specifically, we implement several dictionary-based methods popular in the relevant literature, as well as a method we suggest based on a state-of-the-art machine learning method for entity recognition. MetaMap, a popular biomedical concept extraction tool, is used as a baseline. Our evaluations were performed in a controlled setting on a common corpus which is a collection of medical forum posts annotated with concepts and linked to controlled vocabularies such as MedDRA and SNOMED CT. To our knowledge, our study is the first to systematically examine the effect of popular concept extraction methods in the area of signal detection for adverse reactions. We show that the choice of algorithm or controlled vocabulary has a significant impact on concept extraction, which will impact the overall signal detection process. We also show that our proposed machine learning approach significantly outperforms all the other methods in identification of both adverse reactions and drugs, even when trained with a relatively small set of annotated text.
WHOSE - A Tool for Whole-Session Analysis in IIR
Venue: arXiv cs.IR 2015
Year: 2015

One of the main challenges in Interactive Information Retrieval (IIR) evaluation is the development and application of re-usable tools that allow researchers to analyze search behavior of real users in different environments and different domains, but with comparable results. Furthermore, IIR recently focuses more on the analysis of whole sessions, which includes all user interactions that are carried out within a session but also across several sessions by the same user. Some frameworks have already been proposed for the evaluation of controlled experiments in IIR, but yet no framework is available for interactive evaluation of search behavior from real-world information retrieval (IR) systems with real users. In this paper we present a framework for whole-session evaluation that can also utilize these uncontrolled data sets. The logging component can easily be integrated into real-world IR systems for generating and analyzing new log data. Furthermore, due to a supplementary mapping it is also possible to analyze existing log data. For every IR system different actions and filters can be defined. This allows system operators and researchers to use the framework for the analysis of user search behavior in their IR systems and to compare it with others. Using a graphical user interface they have the possibility to interactively explore the data set from a broad overview down to individual sessions.
Efficient Interference Management Policies for Femtocell Networks
Venue: arXiv cs.IT 2015
Year: 2015

Managing interference in a network of macrocells underlaid with femtocells presents an important, yet challenging problem. A majority of spatial (frequency/time) reuse based approaches partition the users based on coloring the interference graph, which is shown to be suboptimal. Some spatial time reuse based approaches schedule the maximal independent sets (MISs) in a cyclic, (weighted) round-robin fashion, which is inefficient for delay-sensitive applications. Our proposed policies schedule the MISs in a non-cyclic fashion, which aim to optimize any given network performance criterion for delay-sensitive applications while fulfilling minimum throughput requirements of the users. Importantly, we do not take the interference graph as given as in existing works; we propose an optimal construction of the interference graph. We prove that under certain conditions, the proposed policy achieves the optimal network performance. For large networks, we propose a low-complexity algorithm for computing the proposed policy. We show that the policy computed achieves a constant competitive ratio (with respect to the optimal network performance), which is independent of the network size, under wide range of deployment scenarios. The policy can be implemented in a decentralized manner by the users. Compared to the existing policies, our proposed policies can achieve improvement of up to 130 % in large-scale deployments.
Information Technology in New Zealand: Review of Emerging Social Trends, Current Issues, and Policies
Venue: arXiv cs.CY 2015
Year: 2015

This paper discusses the general state of information technology in New Zealand society, current issues, and policies. It is a qualitative study that reviews recent scholarly articles, periodicals, and surveys in order to create an understanding of some of the information technology issues and trends in New Zealand. After reviewing previous research, it assesses the potential existence and nature of a 'digital divide' in New Zealand society whilst also evaluating possible strategic responses to the issue. New Zealand society has rapidly accepted emerging online trends as well as achieving an overall high level of Internet provision nationally. Through government policy and education, this small island nation has remained at the forefront of information technology and can be considered somewhat of an e-democracy. However, despite these positives, there is a risk of low-income communities being left behind as New Zealand society becomes increasingly dependent on IT in the workplace and in governmental administration.
Meta learning of bounds on the Bayes classifier error
Venue: arXiv cs.LG 2015
Year: 2015

Meta learning uses information from base learners (e.g. classifiers or estimators) as well as information about the learning problem to improve upon the performance of a single base learner. For example, the Bayes error rate of a given feature space, if known, can be used to aid in choosing a classifier, as well as in feature selection and model selection for the base classifiers and the meta classifier. Recent work in the field of f-divergence functional estimation has led to the development of simple and rapidly converging estimators that can be used to estimate various bounds on the Bayes error. We estimate multiple bounds on the Bayes error using an estimator that applies meta learning to slowly converging plug-in estimators to obtain the parametric convergence rate. We compare the estimated bounds empirically on simulated data and then estimate the tighter bounds on features extracted from an image patch analysis of sunspot continuum and magnetogram images.
Systems-theoretic Safety Assessment of Robotic Telesurgical Systems
Venue: arXiv cs.RO 2015
Year: 2015

Robotic telesurgical systems are one of the most complex medical cyber-physical systems on the market, and have been used in over 1.75 million procedures during the last decade. Despite significant improvements in design of robotic surgical systems through the years, there have been ongoing occurrences of safety incidents during procedures that negatively impact patients. This paper presents an approach for systems-theoretic safety assessment of robotic telesurgical systems using software-implemented fault-injection. We used a systemstheoretic hazard analysis technique (STPA) to identify the potential safety hazard scenarios and their contributing causes in RAVEN II robot, an open-source robotic surgical platform. We integrated the robot control software with a softwareimplemented fault-injection engine which measures the resilience of the system to the identified safety hazard scenarios by automatically inserting faults into different parts of the robot control software. Representative hazard scenarios from real robotic surgery incidents reported to the U.S. Food and Drug Administration (FDA) MAUDE database were used to demonstrate the feasibility of the proposed approach for safety-based design of robotic telesurgical systems.
Correlational Neural Networks
Venue: arXiv cs.CL 2015
Year: 2015

Common Representation Learning (CRL), wherein different descriptions (or views) of the data are embedded in a common subspace, is receiving a lot of attention recently. Two popular paradigms here are Canonical Correlation Analysis (CCA) based approaches and Autoencoder (AE) based approaches. CCA based approaches learn a joint representation by maximizing correlation of the views when projected to the common subspace. AE based methods learn a common representation by minimizing the error of reconstructing the two views. Each of these approaches has its own advantages and disadvantages. For example, while CCA based approaches outperform AE based approaches for the task of transfer learning, they are not as scalable as the latter. In this work we propose an AE based approach called Correlational Neural Network (CorrNet), that explicitly maximizes correlation among the views when projected to the common subspace. Through a series of experiments, we demonstrate that the proposed CorrNet is better than the above mentioned approaches with respect to its ability to learn correlated common representations. Further, we employ CorrNet for several cross language tasks and show that the representations learned using CorrNet perform better than the ones learned using other state of the art approaches.
Mid-level Elements for Object Detection
Venue: arXiv cs.CV 2015
Year: 2015

Building on the success of recent discriminative mid-level elements, we propose a surprisingly simple approach for object detection which performs comparable to the current state-of-the-art approaches on PASCAL VOC comp-3 detection challenge (no external data). Through extensive experiments and ablation analysis, we show how our approach effectively improves upon the HOG-based pipelines by adding an intermediate mid-level representation for the task of object detection. This representation is easily interpretable and allows us to visualize what our object detector "sees". We also discuss the insights our approach shares with CNN-based methods, such as sharing representation between categories helps.
Adaptive Computation of the Swap-Insert Correction Distance
Venue: arXiv cs.DS 2015
Year: 2015

The Swap-Insert Correction distance from a string $S$ of length $n$ to another string $L$ of length $m\geq n$ on the alphabet $[1..d]$ is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting $S$ into $L$. Contrarily to other correction distances, computing it is NP-Hard in the size $d$ of the alphabet. We describe an algorithm computing this distance in time within $O(d^2 nm g^{d-1})$, where there are $n_α$ occurrences of $α$ in $S$, $m_α$ occurrences of $α$ in $L$, and where $g=\max_{α\in[1..d]} \min\{n_α,m_α-n_α\}$ measures the difficulty of the instance. The difficulty $g$ is bounded by above by various terms, such as the length of the shortest string $S$, and by the maximum number of occurrences of a single character in $S$. Those results illustrate how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.
The Unknown Input Observer and its Advantages with Examples
Venue: arXiv cs.SY 2015
Year: 2015

This brief memo reviews the theory of Unknown Input Observers (UIO) for state estimation in systems subject to disturbance inputs that are not known a priori. One main advantage of the UIO is that the observer structure naturally decouples the plant inputs from the state estimation process. This advantage is highlighted in three example dynamic systems commonly found in control theory. It is shown that the estimation error for all three systems asymptotically approaches zero by application of the UIO under the influence of dynamic disturbances.
Notes on Cloud computing principles
Venue: arXiv cs.DC 2015
Year: 2015

This letter provides a review of fundamental distributed systems and economic Cloud computing principles. These principles are frequently deployed in their respective fields, but their inter-dependencies are often neglected. Given that Cloud Computing first and foremost is a new business model, a new model to sell computational resources, the understanding of these concepts is facilitated by treating them in unison. Here, we review some of the most important concepts and how they relate to each other.
Geo-Temporal Distribution of Tag Terms for Event-Related Image Retrieval
Venue: arXiv cs.IR 2015
Year: 2015

Media sharing applications, such as Flickr and Panoramio, contain a large amount of pictures related to real life events. For this reason, the development of effective methods to retrieve these pictures is important, but still a challenging task. Recognizing this importance, and to improve the retrieval effectiveness of tag-based event retrieval systems, we propose a new method to extract a set of geographical tag features from raw geo-spatial profiles of user tags. The main idea is to use these features to select the best expansion terms in a machine learning-based query expansion approach. Specifically, we apply rigorous statistical exploratory analysis of spatial point patterns to extract the geo-spatial features. We use the features both to summarize the spatial characteristics of the spatial distribution of a single term, and to determine the similarity between the spatial profiles of two terms -- i.e., term-to-term spatial similarity. To further improve our approach, we investigate the effect of combining our geo-spatial features with temporal features on choosing the expansion terms. To evaluate our method, we perform several experiments, including well-known feature analyses. Such analyses show how much our proposed geo-spatial features contribute to improve the overall retrieval performance. The results from our experiments demonstrate the effectiveness and viability of our method.
An Optimal Linear Coding for Index Coding Problem
Venue: arXiv cs.IT 2015
Year: 2015

An optimal linear coding solution for index coding problem is established. Instead of network coding approach by focus on graph theoric and algebraic methods a linear coding program for solving both unicast and groupcast index coding problem is presented. The coding is proved to be the optimal solution from the linear perspective and can be easily utilize for any number of messages. The importance of this work is lying mostly on the usage of the presented coding in the groupcast index coding problem.
Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems
Venue: arXiv cs.LG 2015
Year: 2015

We present a machine learning algorithm for building classifiers that are comprised of a small number of disjunctions of conjunctions (or's of and's). An example of a classifier of this form is as follows: If X satisfies (x1 = 'blue' AND x3 = 'middle') OR (x1 = 'blue' AND x2 = '<15') OR (x1 = 'yellow'), then we predict that Y=1, ELSE predict Y=0. An attribute-value pair is called a literal and a conjunction of literals is called a pattern. Models of this form have the advantage of being interpretable to human experts, since they produce a set of conditions that concisely describe a specific class. We present two probabilistic models for forming a pattern set, one with a Beta-Binomial prior, and the other with Poisson priors. In both cases, there are prior parameters that the user can set to encourage the model to have a desired size and shape, to conform with a domain-specific definition of interpretability. We provide two scalable MAP inference approaches: a pattern level search, which involves association rule mining, and a literal level search. We show stronger priors reduce computation. We apply the Bayesian Or's of And's (BOA) model to predict user behavior with respect to in-vehicle context-aware personalized recommender systems.
Comparative Stability of Cloned and Non-cloned Code: A Replication Study
Venue: arXiv cs.SE 2015
Year: 2015

Code cloning is an important software engineering aspect. It is a common software reuse principle that consists of duplicating source code within a program or across different systems owned or maintained by the same entity. There are several contradictory claims concerning the impact of cloning on software stability and maintenance effort. Some papers state that cloning is desired since it speeds up the development process and helps stakeholders meet the tight schedule and deliver on time. Other papers argue that code clone leads to code bloat and causes increase software maintenance costs due to copied defects and dead code. In this paper, we are replicating a previous study done on cloning by the original author. We are repeating his work using the same methods and metrics but with different subjects and experimenters. The paper we are addressing evaluates the impact of code cloning on code stability using three different stability-measuring methods. Our team will apply the same stability measurement techniques on a different software system developed in C programming language to determine generalizability, assure that the results are reliable, validate their outcomes, and to inspire new search by combining previous findings from related studies.
Hydras: Directed Hypergraphs and Horn Formulas
Venue: arXiv cs.DM 2015
Year: 2015

We introduce a new graph parameter, the hydra number, arising from the minimization problem for Horn formulas in propositional logic. The hydra number of a graph $G=(V,E)$ is the minimal number of hyperarcs of the form $u,v\rightarrow w$ required in a directed hypergraph $H=(V,F)$, such that for every pair $(u, v)$, the set of vertices reachable in $H$ from $\{u, v\}$ is the entire vertex set $V$ if $(u, v) \in E$, and it is $\{u, v\}$ otherwise. Here reachability is defined by forward chaining, a standard marking algorithm. Various bounds are given for the hydra number. We show that the hydra number of a graph can be upper bounded by the number of edges plus the path cover number of the line graph of a spanning subgraph, which is a sharp bound in several cases. On the other hand, we construct single-headed graphs for which that bound is off by a constant factor. Furthermore, we characterize trees with low hydra number, and give a lower bound for the hydra number of trees based on the number of vertices that are leaves in the tree obtained from $T$ by deleting its leaves. This bound is sharp for some families of trees. We give bounds for the hydra number of complete binary trees and also discuss a related minimization problem.
Spatial CSMA: A Distributed Scheduling Algorithm for the SIR Model with Time-varying Channels
Venue: arXiv cs.NI 2015
Year: 2015

Recent work has shown that adaptive CSMA algorithms can achieve throughput optimality. However, these adaptive CSMA algorithms assume a rather simplistic model for the wireless medium. Specifically, the interference is typically modelled by a conflict graph, and the channels are assumed to be static. In this work, we propose a distributed and adaptive CSMA algorithm under a more realistic signal-to-interference ratio (SIR) based interference model, with time-varying channels. We prove that our algorithm is throughput optimal under this generalized model. Further, we augment our proposed algorithm by using a parallel update technique. Numerical results show that our algorithm outperforms the conflict graph based algorithms, in terms of supportable throughput and the rate of convergence to steady-state.
Weighted graph algorithms with Python
Venue: arXiv cs.DS 2015
Year: 2015

Python implementation of selected weighted graph algorithms is presented. The minimal graph interface is defined together with several classes implementing this interface. Graph nodes can be any hashable Python objects. Directed edges are instances of the Edge class. Graphs are instances of the Graph class. It is based on the adjacency-list representation, but with fast lookup of nodes and neighbors (dict-of-dict structure). Other implementations of this class are also possible. In this work, many algorithms are implemented using a unified approach. There are separate classes and modules devoted to different algorithms. Three algorithms for finding a minimum spanning tree are implemented: the Boruvka's algorithm, the Prim's algorithm (three implementations), and the Kruskal's algorithm. Three algorithms for solving the single-source shortest path problem are implemented: the dag shortest path algorithm, the Bellman-Ford algorithm, and the Dijkstra's algorithm (two implementations). Two algorithms for solving all-pairs shortest path problem are implemented: the Floyd-Warshall algorithm and the Johnson's algorithm. All algorithms were tested by means of the unittest module, the Python unit testing framework. Additional computer experiments were done in order to compare real and theoretical computational complexity. The source code is available from the public GitHub repository.
A Solution Merging Heuristic for the Steiner Problem in Graphs Using Tree Decompositions
Venue: arXiv cs.DS 2015
Year: 2015

Fixed parameter tractable algorithms for bounded treewidth are known to exist for a wide class of graph optimization problems. While most research in this area has been focused on exact algorithms, it is hard to find decompositions of treewidth sufficiently small to make these al- gorithms fast enough for practical use. Consequently, tree decomposition based algorithms have limited applicability to large scale optimization. However, by first reducing the input graph so that a small width tree decomposition can be found, we can harness the power of tree decomposi- tion based techniques in a heuristic algorithm, usable on graphs of much larger treewidth than would be tractable to solve exactly. We propose a solution merging heuristic to the Steiner Tree Problem that applies this idea. Standard local search heuristics provide a natural way to generate subgraphs with lower treewidth than the original instance, and subse- quently we extract an improved solution by solving the instance induced by this subgraph. As such the fixed parameter tractable algorithm be- comes an efficient tool for our solution merging heuristic. For a large class of sparse benchmark instances the algorithm is able to find small width tree decompositions on the union of generated solutions. Subsequently it can often improve on the generated solutions fast.
Language Emptiness of Continuous-Time Parametric Timed Automata
Venue: arXiv cs.FL 2015
Year: 2015

Parametric timed automata extend the standard timed automata with the possibility to use parameters in the clock guards. In general, if the parameters are real-valued, the problem of language emptiness of such automata is undecidable even for various restricted subclasses. We thus focus on the case where parameters are assumed to be integer-valued, while the time still remains continuous. On the one hand, we show that the problem remains undecidable for parametric timed automata with three clocks and one parameter. On the other hand, for the case with arbitrary many clocks where only one of these clocks is compared with (an arbitrary number of) parameters, we show that the parametric language emptiness is decidable. The undecidability result tightens the bounds of a previous result which assumed six parameters, while the decidability result extends the existing approaches that deal with discrete-time semantics only. To the best of our knowledge, this is the first positive result in the case of continuous-time and unbounded integer parameters, except for the rather simple case of single-clock automata.