OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms and Complexity of Range Clustering
Venue: arXiv cs.DS 2018
Year: 2018

We introduce a novel criterion in clustering that seeks clusters with limited range of values associated with each cluster's elements. In clustering or classification the objective is to partition a set of objects into subsets, called clusters or classes, consisting of similar objects so that different clusters are as dissimilar as possible. We propose a number of objective functions that employ the range of the clusters as part of the objective function. Several of the proposed objectives mimic objectives based on sums of similarities. These objective functions are motivated by image segmentation problems, where the diameter, or range of values associated with objects in each cluster, should be small. It is demonstrated that range-based problems are in general easier, in terms of their complexity, than the analogous similarity-sum problems. Several of the problems we present could therefore be viable alternatives to existing clustering problems which are NP-hard, offering the advantage of efficient algorithms.
Topological Skeletonization and Tree-Summarization of Neurons Using Discrete Morse Theory
Venue: arXiv cs.CG 2018
Year: 2018

Neuroscientific data analysis has classically involved methods for statistical signal and image processing, drawing on linear algebra and stochastic process theory. However, digitized neuroanatomical data sets containing labelled neurons, either individually or in groups labelled by tracer injections, do not fully fit into this classical framework. The tree-like shapes of neurons cannot mathematically be adequately described as points in a vector space. There is therefore a need for new approaches. Methods from computational topology and geometry are naturally suited to the analysis of neuronal shapes. Here we introduce methods from Discrete Morse Theory to extract tree-skeletons of individual neurons from volumetric brain image data, or to summarize collections of neurons labelled by localized anterograde tracer injections. Since individual neurons are topologically trees, it is sensible to summarize the collection of neurons labelled by a localized anterograde tracer injection using a consensus tree-shape. The algorithmic procedure includes an initial pre-processing step to extract a density field from the raw volumetric image data, followed by initial skeleton extraction from the density field using a discrete version of a 1-(un)stable manifold of the density field. Heuristically, if the density field is regarded as a mountainous landscape, then the 1-(un)stable manifold follows the "mountain ridges" connecting the maxima of the density field. We then simplify this skeleton-graph into a tree using a shortest-path approach and methods derived from persistent homology. The advantage of this approach is that it uses global information about the density field and is therefore robust to local fluctuations and non-uniformly distributed input signals. To be able to handle large data sets, we use a divide-and-conquer approach. The resulting software DiMorSC is available on Github.
Collaborative Item Embedding Model for Implicit Feedback Data
Venue: arXiv cs.IR 2018
Year: 2018

Collaborative filtering is the most popular approach for recommender systems. One way to perform collaborative filtering is matrix factorization, which characterizes user preferences and item attributes using latent vectors. These latent vectors are good at capturing global features of users and items but are not strong in capturing local relationships between users or between items. In this work, we propose a method to extract the relationships between items and embed them into the latent vectors of the factorization model. This combines two worlds: matrix factorization for collaborative filtering and item embed- ding, a similar concept to word embedding in language processing. Our experiments on three real-world datasets show that our proposed method outperforms competing methods on top-n recommendation tasks.
Rogue Drone Detection: A Machine Learning Approach
Venue: arXiv cs.NI 2018
Year: 2018

The emerging, practical and observed issue of how to detect rogue drones that carry terrestrial user equipment (UEs) on mobile networks is addressed in this paper. This issue has drawn much attention since the rogue drones may generate excessive interference to mobile networks and may not be allowed by regulations in some regions. In this paper, we propose a novel machine learning approach to identify the rogue drones in mobile networks based on radio measurements. We apply two classification machine learning models, Logistic Regression, and Decision Tree, using features from radio measurements to identify the rogue drones. We find that for high altitudes the proposed machine learning solutions can yield high rogue drone detection rate while not mis-classifying regular ground based UEs as rogue drone UEs. The detection accuracy however degrades at low altitudes.
A 3D Parallel Algorithm for QR Decomposition
Venue: arXiv cs.DC 2018
Year: 2018

Interprocessor communication often dominates the runtime of large matrix computations. We present a parallel algorithm for computing QR decompositions whose bandwidth cost (communication volume) can be decreased at the cost of increasing its latency cost (number of messages). By varying a parameter to navigate the bandwidth/latency tradeoff, we can tune this algorithm for machines with different communication costs.
Exploiting Data and Human Knowledge for Predicting Wildlife Poaching
Venue: arXiv cs.CY 2018
Year: 2018

Poaching continues to be a significant threat to the conservation of wildlife and the associated ecosystem. Estimating and predicting where the poachers have committed or would commit crimes is essential to more effective allocation of patrolling resources. The real-world data in this domain is often sparse, noisy and incomplete, consisting of a small number of positive data (poaching signs), a large number of negative data with label uncertainty, and an even larger number of unlabeled data. Fortunately, domain experts such as rangers can provide complementary information about poaching activity patterns. However, this kind of human knowledge has rarely been used in previous approaches. In this paper, we contribute new solutions to the predictive analysis of poaching patterns by exploiting both very limited data and human knowledge. We propose an approach to elicit quantitative information from domain experts through a questionnaire built upon a clustering-based division of the conservation area. In addition, we propose algorithms that exploit qualitative and quantitative information provided by the domain experts to augment the dataset and improve learning. In collaboration with World Wild Fund for Nature, we show that incorporating human knowledge leads to better predictions in a conservation area in Northeastern China where the charismatic species is Siberian Tiger. The results show the importance of exploiting human knowledge when learning from limited data.
An Automatic Patch-based Approach for HER-2 Scoring in Immunohistochemical Breast Cancer Images Using Color Features
Venue: arXiv cs.CV 2018
Year: 2018

Breast cancer (BC) is the most common cancer among women world-wide, approximately 20-25% of BCs are HER-2 positive. Analysis of HER-2 is fundamental to defining the appropriate therapy for patients with breast cancer. Inter-pathologist variability in the test results can affect diagnostic accuracy. The present study intends to propose an automatic scoring HER-2 algorithm. Based on color features, the technique is fully-automated and avoids segmentation, showing a concordance higher than 90% with a pathologist in the experiments realized.
O.D.E.S. : An Online Dynamic Examination System based on a CMS Wordpress plugin
Venue: arXiv cs.CY 2018
Year: 2018

This paper describes the online dynamic examination application plugin named O.D.E.S., developed according to the open source software philosophy, where the CMS Wordpress is used as programmers/coders are given the potential to develop applications from scratch with safety and ease. In ODES application there exists two types of users: admin/teacher and student. The admin/teacher can create/edit/delete/view questions, categories of questions and examination papers. The questions are divided in two types, multiple choice questions (including true/false) and long answer questions (essays). The teacher can create exams choosing the number of questions and the types of questions that exist in the pool of questions that are previously created. The selection is done randomly by the application and the teacher just determines the total number of both multiple choice or long answer questions as well as the importance (weight) of each one of them (including negative grades also). The student takes the random generated exam and receives his/hers grades. The grades of the multiple choice questions are done automatically, whereas for the long answer questions the teacher is responsible to put grades on. After the completion of the exam the teacher can view the student's final score via the control panel or a report.
Online interval scheduling to maximize total satisfaction
Venue: arXiv cs.DS 2018
Year: 2018

The interval scheduling problem is one variant of the scheduling problem. In this paper, we propose a novel variant of the interval scheduling problem, whose definition is as follows: given jobs are specified by their {\em release times}, {\em deadlines} and {\em profits}. An algorithm must start a job at its release time on one of $m$ identical machines, and continue processing until its deadline on the machine to complete the job. All the jobs must be completed and the algorithm can obtain the profit of a completed job as a user's satisfaction. It is possible to process more than one job at a time on one machine. The profit of a job is distributed uniformly between its release time and deadline, that is its interval, and the profit gained from a subinterval of a job decreases in reverse proportion to the number of jobs whose intervals intersect with the subinterval on the same machine. The objective of our variant is to maximize the total profit of completed jobs. This formulation is naturally motivated by best-effort requests and responses to them, which appear in many situations. In best-effort requests and responses, the total amount of available resources for users is always invariant and the resources are equally shared with every user. We study online algorithms for this problem. Specifically, we show that for the case where the profits of jobs are arbitrary, there does not exist an algorithm whose competitive ratio is bounded. Then, we consider the case in which the profit of each job is equal to its length, that is, the time interval between its release time and deadline. For this case, we prove that for $m = 2$ and $m \geq 3$, the competitive ratios of a greedy algorithm are at most $4/3$ and at most $3$, respectively. Also, for each $m \geq 2$, we show a lower bound on the competitive ratio of any deterministic algorithm.
On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model
Venue: arXiv cs.DS 2018
Year: 2018

Given a set of $n$ points $P$ in the plane, each colored with one of the $t$ given colors, a color-spanning set $S\subset P$ is a subset of $t$ points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum (among all color-spanning sets of $P$). Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest (among all color-spanning sets of $P$). Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed-parameter tractable (FPT) when $t$ is a parameter is still open. Motivated by this question, we consider the FPT tractability of some matching problems under this color-spanning model, where $t=2k$ is the parameter. The problems are summarized as follows: (1) MinSum Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that their total edge length is minimized; (2) MaxMin Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that the minimum edge length is maximized; (3) MinMax Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that the maximum edge length is minimized; and (4) $k$-Multicolored Independent Matching, namely, computing a matching of $2k$ vertices in a graph such that the vertices of the edges in the matching do not share common edges in the graph. We show that the first three problems are polynomially solvable (hence in FPT), while problem (4) is W[1]-hard.
Improved Predictive Models for Acute Kidney Injury with IDEAs: Intraoperative Data Embedded Analytics
Venue: arXiv cs.CY 2018
Year: 2018

Acute kidney injury (AKI) is a common and serious complication after a surgery which is associated with morbidity and mortality. The majority of existing perioperative AKI risk score prediction models are limited in their generalizability and do not fully utilize the physiological intraoperative time-series data. Thus, there is a need for intelligent, accurate, and robust systems, able to leverage information from large-scale data to predict patient's risk of developing postoperative AKI. A retrospective single-center cohort of 2,911 adult patients who underwent surgery at the University of Florida Health has been used for this study. We used machine learning and statistical analysis techniques to develop perioperative models to predict the risk of AKI (risk during the first 3 days, 7 days, and until the discharge day) before and after the surgery. In particular, we examined the improvement in risk prediction by incorporating three intraoperative physiologic time series data, i.e., mean arterial blood pressure, minimum alveolar concentration, and heart rate. For an individual patient, the preoperative model produces a probabilistic AKI risk score, which will be enriched by integrating intraoperative statistical features through a machine learning stacking approach inside a random forest classifier. We compared the performance of our model based on the area under the receiver operating characteristics curve (AUROC), accuracy and net reclassification improvement (NRI). The predictive performance of the proposed model is better than the preoperative data only model. For AKI-7day outcome: The AUC was 0.86 (accuracy was 0.78) in the proposed model, while the preoperative AUC was 0.84 (accuracy 0.76). Furthermore, with the integration of intraoperative features, we were able to classify patients who were misclassified in the preoperative model.
Wearable Audio and IMU Based Shot Detection in Racquet Sports
Venue: arXiv cs.LG 2018
Year: 2018

Wearables like smartwatches which are embedded with sensors and powerful processors, provide a strong platform for development of analytics solutions in sports domain. To analyze players' games, while motion sensor based shot detection has been extensively studied in sports like Tennis, Golf, Baseball; Table Tennis and Badminton are relatively less explored due to possible less intense hand motion during shots. In our paper, we propose a novel, computationally inexpensive and real-time system for shot detection in table tennis, based on fusion of Inertial Measurement Unit (IMU) and audio sensor data embedded in a wrist-worn wearable. The system builds upon our presented methodology for synchronizing IMU and audio sensor input in time using detected shots and achieves 95.6% accuracy. To our knowledge, it is the first fusion-based solution for sports analysis in wearables. Shot detectors for other racquet sports as well as further analytics to provide features like shot classification, rally analysis and recommendations, can easily be built over our proposed solution.
A CNN for homogneous Riemannian manifolds with applications to Neuroimaging
Venue: arXiv cs.CV 2018
Year: 2018

Convolutional neural networks are ubiquitous in Machine Learning applications for solving a variety of problems. They however can not be used in their native form when the domain of the data is commonly encountered manifolds such as the sphere, the special orthogonal group, the Grassmanian, the manifold of symmetric positive definite matrices and others. Most recently, generalization of CNNs to data domains such as the 2-sphere has been reported by some research groups, which is referred to as the spherical CNNs (SCNNs). The key property of SCNNs distinct from CNNs is that they exhibit the rotational equivariance property that allows for sharing learned weights within a layer. In this paper, we theoretically generalize the CNNs to Riemannian homogeneous manifolds, that include but are not limited to the aforementioned example manifolds. Our key contributions in this work are: (i) A theorem stating that linear group equivariance systems are fully characterized by correlation of functions on the domain manifold and vice-versa. This is fundamental to the characterization of all linear group equivariant systems and parallels the widely used result in linear system theory for vector spaces. (ii) As a corrolary, we prove the equivariance of the correlation operation to group actions admitted by the input domains which are Riemannian homogeneous manifolds. (iii) We present the first end-to-end deep network architecture for classification of diffusion magnetic resonance image (dMRI) scans acquired from a cohort of 44 Parkinson Disease patients and 50 control/normal subjects. (iv) A proof of concept experiment involving synthetic data generated on the manifold of symmetric positive definite matrices is presented to demonstrate the applicability of our network to other types of domains.
Multi-Modal Trajectory Prediction of Surrounding Vehicles with Maneuver based LSTMs
Venue: arXiv cs.CV 2018
Year: 2018

To safely and efficiently navigate through complex traffic scenarios, autonomous vehicles need to have the ability to predict the future motion of surrounding vehicles. Multiple interacting agents, the multi-modal nature of driver behavior, and the inherent uncertainty involved in the task make motion prediction of surrounding vehicles a challenging problem. In this paper, we present an LSTM model for interaction aware motion prediction of surrounding vehicles on freeways. Our model assigns confidence values to maneuvers being performed by vehicles and outputs a multi-modal distribution over future motion based on them. We compare our approach with the prior art for vehicle motion prediction on the publicly available NGSIM US-101 and I-80 datasets. Our results show an improvement in terms of RMS values of prediction error. We also present an ablative analysis of the components of our proposed model and analyze the predictions made by the model in complex traffic scenarios.
Two Sides of the Same Coin: Software Developers' Perceptions of Task Switching and Task Interruption
Venue: arXiv cs.SE 2018
Year: 2018

In the constantly evolving world of software development, switching back and forth between tasks has become the norm. While task switching often allows developers to perform tasks effectively and may increase creativity via the flexible pathway, there are also consequences to frequent task-switching. For high-momentum tasks like software development, "flow", the highly productive state of concentration, is paramount. Each switch distracts the developers' flow, requiring them to switch mental state and an additional immersion period to get back into the flow. However, the wasted time due to time fragmentation caused by task switching is largely invisible and unnoticed by developers and managers. We conducted a survey with 141 software developers to investigate their perceptions of differences between task switching and task interruption and to explore whether they perceive task switchings as disruptive as interruptions. We found that practitioners perceive considerable similarities between the disruptiveness of task switching (either planned or unplanned) and random interruptions. The high level of cognitive cost and low performance are the main consequences of task switching articulated by our respondents. Our findings broaden the understanding of flow change among software practitioners in terms of the characteristics and categories of disruptive switches as well as the consequences of interruptions caused by daily stand-up meetings.
Domain Analysis & Description - The Implicit and Explicit Semantics Problem
Venue: arXiv cs.PL 2018
Year: 2018

A domain analysis & description calculus is introduced. It is shown to alleviate the issue of implicit semantics. The claim is made that domain descriptions, whether informal, or as also here, formal, amount to an explicit semantics for what is otherwise implicit if not described.
Securing Open Source Clouds Using Models
Venue: arXiv cs.SE 2018
Year: 2018

The widespread adoption of cloud computing has resulted in the proliferation of open source cloud computing frameworks that give more control to enterprises over their data and networks. Though the benefits of open source software are widely recognized, there is a growing concern over their security assurance. Often open source software is a subject of frequent updates. The updates might introduce or remove a variety of features and hence violate security properties of the previous releases. Obviously, a manual inspection of security would be prohibitively slow and inefficient. In this work, we propose an automated approach that can help developers to assure the security of open source cloud framework even in the presence of frequent releases. Our methodology consists of creating a (stateful) wrapper that emulates the usage scenarios with explicit representation of security and functional requirements as contracts. We use a model-driven approach to model REST APIs of KeyStone, an identity service in OpenStack. OpenStack is an open source cloud computing framework providing IaaS. Our models define structural and behavioral properties of Keystone together with its security requirements. We detail the implementation of these models in Django Web Framework and also show how to use the behavioral interfaces to implement a service monitor for the cloud services. This mechanism facilitates verification and validation of functional behavior and security requirement in an automated manner.
Stabilizing a system with an unbounded random gain using only a finite number of bits
Venue: arXiv cs.SY 2018
Year: 2018

We study the stabilization of an unpredictable linear control system where the controller must act based on a rate-limited observation of the state. More precisely, we consider the system $X_{n+1} = A_n X_n + W_n - U_n$, where the $A_n$'s are drawn independently at random at each time $n$ from a known distribution with unbounded support, and where the controller receives at most $R$ bits about the system state at each time from an encoder. We provide a time-varying achievable strategy to stabilize the system in a second-moment sense with fixed, finite $R$. While our previous result provided a strategy to stabilize this system using a variable-rate code, this work provides an achievable strategy using a fixed-rate code. The strategy we employ to achieve this is time-varying and takes different actions depending on the value of the state. It proceeds in two modes: a normal mode (or zoom-in), where the realization of $A_n$ is typical, and an emergency mode (or zoom-out), where the realization of $A_n$ is exceptionally large.