OpenRaiser/Intern-Atlas huggingface dataset:
From event labeled gene trees to species trees
Venue: arXiv cs.DM 2017
Year: 2017

Background: Tree reconciliation problems have long been studied in phylogenetics. A particular variant of the reconciliation problem for a gene tree T and a species tree S assumes that for each interior vertex x of T it is known whether x represents a speciation or a duplication. This problem appears in the context of analyzing orthology data. Results: We show that S is a species tree for T if and only if S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation vertex. A valid reconciliation map can then be found in polynomial time. Simulated data shows that the event-labeled gene trees convey a large amount of information on underlying species trees, even for a large percentage of losses. Conclusions: The knowledge of event labels in a gene tree strongly constrains the possible species tree and, for a given species tree, also the possible reconciliation maps. Nevertheless, many degrees of freedom remain in the space of feasible solutions. In order to disambiguate the alternative solutions additional external constraints as well as optimization criteria could be employed.
Robot Planning with Mathematical Models of Human State and Action
Venue: arXiv cs.RO 2017
Year: 2017

Robots interacting with the physical world plan with models of physics. We advocate that robots interacting with people need to plan with models of cognition. This writeup summarizes the insights we have gained in integrating computational cognitive models of people into robotics planning and control. It starts from a general game-theoretic formulation of interaction, and analyzes how different approximations result in different useful coordination behaviors for the robot during its interaction with people.
K-sets+: a Linear-time Clustering Algorithm for Data Points with a Sparse Similarity Measure
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we first propose a new iterative algorithm, called the K-sets+ algorithm for clustering data points in a semi-metric space, where the distance measure does not necessarily satisfy the triangular inequality. We show that the K-sets+ algorithm converges in a finite number of iterations and it retains the same performance guarantee as the K-sets algorithm for clustering data points in a metric space. We then extend the applicability of the K-sets+ algorithm from data points in a semi-metric space to data points that only have a symmetric similarity measure. Such an extension leads to great reduction of computational complexity. In particular, for an n * n similarity matrix with m nonzero elements in the matrix, the computational complexity of the K-sets+ algorithm is O((Kn + m)I), where I is the number of iterations. The memory complexity to achieve that computational complexity is O(Kn + m). As such, both the computational complexity and the memory complexity are linear in n when the n * n similarity matrix is sparse, i.e., m = O(n). We also conduct various experiments to show the effectiveness of the K-sets+ algorithm by using a synthetic dataset from the stochastic block model and a real network from the WonderNetwork website.
Improving Resilience of Autonomous Moving Platforms by Real Time Analysis of Their Cooperation
Venue: arXiv cs.SE 2017
Year: 2017

Environmental changes, failures, collisions or even terrorist attacks can cause serious malfunctions of the delivery systems. We have presented a novel approach improving resilience of Autonomous Moving Platforms AMPs. The approach is based on multi-level state diagrams describing environmental trigger specifications, movement actions and synchronization primitives. The upper level diagrams allowed us to model advanced interactions between autonomous AMPs and detect irregularities such as deadlocks live-locks etc. The techniques were presented to verify and analyze combined AMPs' behaviors using model checking technique. The described system, Dedan verifier, is still under development. In the near future, a graphical form of verified system representation is planned.
A Cascaded Convolutional Neural Network for X-ray Low-dose CT Image Denoising
Venue: arXiv cs.CV 2017
Year: 2017

Image denoising techniques are essential to reducing noise levels and enhancing diagnosis reliability in low-dose computed tomography (CT). Machine learning based denoising methods have shown great potential in removing the complex and spatial-variant noises in CT images. However, some residue artifacts would appear in the denoised image due to complexity of noises. A cascaded training network was proposed in this work, where the trained CNN was applied on the training dataset to initiate new trainings and remove artifacts induced by denoising. A cascades of convolutional neural networks (CNN) were built iteratively to achieve better performance with simple CNN structures. Experiments were carried out on 2016 Low-dose CT Grand Challenge datasets to evaluate the method's performance.
SEAGLE: Sparsity-Driven Image Reconstruction under Multiple Scattering
Venue: arXiv cs.CV 2017
Year: 2017

Multiple scattering of an electromagnetic wave as it passes through an object is a fundamental problem that limits the performance of current imaging systems. In this paper, we describe a new technique-called Series Expansion with Accelerated Gradient Descent on Lippmann-Schwinger Equation (SEAGLE)-for robust imaging under multiple scattering based on a combination of a new nonlinear forward model and a total variation (TV) regularizer. The proposed forward model can account for multiple scattering, which makes it advantageous in applications where linear models are inaccurate. Specifically, it corresponds to a series expansion of the scattered wave with an accelerated-gradient method. This expansion guarantees the convergence even for strongly scattering objects. One of our key insights is that it is possible to obtain an explicit formula for computing the gradient of our nonlinear forward model with respect to the unknown object, thus enabling fast image reconstruction with the state-of-the-art fast iterative shrinkage/thresholding algorithm (FISTA). The proposed method is validated on both simulated and experimentally measured data.
Learning to see people like people
Venue: arXiv cs.CV 2017
Year: 2017

Humans make complex inferences on faces, ranging from objective properties (gender, ethnicity, expression, age, identity, etc) to subjective judgments (facial attractiveness, trustworthiness, sociability, friendliness, etc). While the objective aspects of face perception have been extensively studied, relatively fewer computational models have been developed for the social impressions of faces. Bridging this gap, we develop a method to predict human impressions of faces in 40 subjective social dimensions, using deep representations from state-of-the-art neural networks. We find that model performance grows as the human consensus on a face trait increases, and that model predictions outperform human groups in correlation with human averages. This illustrates the learnability of subjective social perception of faces, especially when there is high human consensus. Our system can be used to decide which photographs from a personal collection will make the best impression. The results are significant for the field of social robotics, demonstrating that robots can learn the subjective judgments defining the underlying fabric of human interaction.
Hardware-Software Codesign of Accurate, Multiplier-free Deep Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

While Deep Neural Networks (DNNs) push the state-of-the-art in many machine learning applications, they often require millions of expensive floating-point operations for each input classification. This computation overhead limits the applicability of DNNs to low-power, embedded platforms and incurs high cost in data centers. This motivates recent interests in designing low-power, low-latency DNNs based on fixed-point, ternary, or even binary data precision. While recent works in this area offer promising results, they often lead to large accuracy drops when compared to the floating-point networks. We propose a novel approach to map floating-point based DNNs to 8-bit dynamic fixed-point networks with integer power-of-two weights with no change in network architecture. Our dynamic fixed-point DNNs allow different radix points between layers. During inference, power-of-two weights allow multiplications to be replaced with arithmetic shifts, while the 8-bit fixed-point representation simplifies both the buffer and adder design. In addition, we propose a hardware accelerator design to achieve low-power, low-latency inference with insignificant degradation in accuracy. Using our custom accelerator design with the CIFAR-10 and ImageNet datasets, we show that our method achieves significant power and energy savings while increasing the classification accuracy.
Optimal fidelity multi-level Monte Carlo for quantification of uncertainty in simulations of cloud cavitation collapse
Venue: arXiv cs.CE 2017
Year: 2017

We quantify uncertainties in the location and magnitude of extreme pressure spots revealed from large scale multi-phase flow simulations of cloud cavitation collapse. We examine clouds containing 500 cavities and quantify uncertainties related to their initial spatial arrangement. The resulting 2000-dimensional space is sampled using a non-intrusive and computationally efficient Multi-Level Monte Carlo (MLMC) methodology. We introduce novel optimal control variate coefficients to enhance the variance reduction in MLMC. The proposed optimal fidelity MLMC leads to more than two orders of magnitude speedup when compared to standard Monte Carlo methods. We identify large uncertainties in the location and magnitude of the peak pressure pulse and present its statistical correlations and joint probability density functions with the geometrical characteristics of the cloud. Characteristic properties of spatial cloud structure are identified as potential causes of significant uncertainties in exerted collapse pressures.
Evaluating vector-space models of analogy
Venue: arXiv cs.CL 2017
Year: 2017

Vector-space representations provide geometric tools for reasoning about the similarity of a set of objects and their relationships. Recent machine learning methods for deriving vector-space embeddings of words (e.g., word2vec) have achieved considerable success in natural language processing. These vector spaces have also been shown to exhibit a surprising capacity to capture verbal analogies, with similar results for natural images, giving new life to a classic model of analogies as parallelograms that was first proposed by cognitive scientists. We evaluate the parallelogram model of analogy as applied to modern word embeddings, providing a detailed analysis of the extent to which this approach captures human relational similarity judgments in a large benchmark dataset. We find that that some semantic relationships are better captured than others. We then provide evidence for deeper limitations of the parallelogram model based on the intrinsic geometric constraints of vector spaces, paralleling classic results for first-order similarity.
Time Accuracy Analysis of Post-Mediation Packet-Switched Charging Data Records for Urban Mobility Applications
Venue: arXiv cs.SI 2017
Year: 2017

Telecommunication data is being used increasingly in urban mobility applications around the world. Despite its ubiquity and usefulness, technical difficulties arise when using Packet-Switched Charging Data Records (CDR), since its main purpose was not intended for this kind of applications. Due to its particular nature, a trade-off must be considered between accessibility and time accuracy when using this data. On the one hand, to obtain highly accurate timestamps, huge amounts of network-level CDR must be extracted and stored. This task is very difficult and expensive since highly critical network node applications can be compromised in the data extraction and storage. On the other hand, post-mediation CDR can be easily accessed since no network node application is involved in its analysis. The pay-off is in the lower accurate timestamps recorded, since several aggregations and filtering is performed in previous steps of the charging pipelines. In this work, a detailed description of the timestamp error problem using post-mediation CDR is presented, together with a methodology to analyze error time series collected in each network cell.
Beamforming Codebook Compensation for Beam Squint with Channel Capacity Constraint
Venue: arXiv cs.IT 2017
Year: 2017

Analog beamforming with phased arrays is a promising technique for 5G wireless communication in millimeter wave bands. A beam focuses on a small range of angles of arrival or departure and corresponds to a set of fixed phase shifts across frequency due to practical hardware constraints. In switched beamforming, a discrete codebook consisting of multiple beams is used to cover a larger angle range. However, for sufficiently large bandwidth, the gain provided by the phased array is frequency dependent even if the radiation pattern of the antenna elements is frequency independent, an effect called beam squint. This paper shows that the beam squint reduces channel capacity of a uniform linear array (ULA). The beamforming codebook is designed to compensate for the beam squint by imposing a channel capacity constraint. For example, our codebook design algorithm can improve the channel capacity by 17.8% for a ULA with 64 antennas operating at bandwidth of 2.5 GHz and carrier frequency of 73 GHz. Analysis and numerical examples suggest that a denser codebook is required to compensate for the beam squint compared to the case without beam squint. Furthermore, the effect of beam squint is shown to increase as bandwidth increases, and the beam squint limits the bandwidth given the number of antennas in the array.
Learning to Refine Object Contours with a Top-Down Fully Convolutional Encoder-Decoder Network
Venue: arXiv cs.CV 2017
Year: 2017

We develop a novel deep contour detection algorithm with a top-down fully convolutional encoder-decoder network. Our proposed method, named TD-CEDN, solves two important issues in this low-level vision problem: (1) learning multi-scale and multi-level features; and (2) applying an effective top-down refined approach in the networks. TD-CEDN performs the pixel-wise prediction by means of leveraging features at all layers of the net. Unlike skip connections and previous encoder-decoder methods, we first learn a coarse feature map after the encoder stage in a feedforward pass, and then refine this feature map in a top-down strategy during the decoder stage utilizing features at successively lower layers. Therefore, the deconvolutional process is conducted stepwise, which is guided by Deeply-Supervision Net providing the integrated direct supervision. The above proposed technologies lead to a more precise and clearer prediction. Our proposed algorithm achieved the state-of-the-art on the BSDS500 dataset (ODS F-score of 0.788), the PASCAL VOC2012 dataset (ODS F-score of 0.588), and and the NYU Depth dataset (ODS F-score of 0.735).
TraX: The visual Tracking eXchange Protocol and Library
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we address the problem of developing on-line visual tracking algorithms. We present a specialized communication protocol that serves as a bridge between a tracker implementation and utilizing application. It decouples development of algorithms and application, encouraging re-usability. The primary use case is algorithm evaluation where the protocol facilitates more complex evaluation scenarios that are used nowadays thus pushing forward the field of visual tracking. We present a reference implementation of the protocol that makes it easy to use in several popular programming languages and discuss where the protocol is already used and some usage scenarios that we envision for the future.
Multi-Channel Random Access with Replications
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers a class of multi-channel random access algorithms, where contending devices may send multiple copies (replicas) of their messages to the central base station. We first develop a hypothetical algorithm that delivers a lower estimate for the access delay performance within this class. Further, we propose a feasible access control algorithm achieving low access delay by sending multiple message replicas, which approaches the performance of the hypothetical algorithm. The resulting performance is readily approximated by a simple lower bound, which is derived for a large number of channels.
Hardware Automated Dataflow Deployment of CNNs
Venue: arXiv cs.OH 2017
Year: 2017

Deep Convolutional Neural Networks (CNNs) are the state of the art systems for image classification and scene understating. However, such techniques are computationally intensive and involve highly regular parallel computation. CNNs can thus benefit from a significant acceleration in execution time when running on fine grain programmable logic devices. As a consequence, several studies have proposed FPGA-based accelerators for CNNs. However, because of the huge amount of the required hardware resources, none of these studies directly was based on a direct mapping of the CNN computing elements onto the FPGA physical resources. In this work, we demonstrate the feasibility of this so-called direct hardware mapping approach and discuss several associated implementation issues. As a proof of concept, we introduce the haddoc2 open source tool, that is able to automatically transform a CNN description into a platform independent hardware description for FPGA implementation.
Distributed-Memory Breadth-First Search on Massive Graphs
Venue: arXiv cs.DC 2017
Year: 2017

This chapter studies the problem of traversing large graphs using the breadth-first search order on distributed-memory supercomputers. We consider both the traditional level-synchronous top-down algorithm as well as the recently discovered direction optimizing algorithm. We analyze the performance and scalability trade-offs in using different local data structures such as CSR and DCSC, enabling in-node multithreading, and graph decompositions such as 1D and 2D decomposition.
Towards a Principled Integration of Multi-Camera Re-Identification and Tracking through Optimal Bayes Filters
Venue: arXiv cs.CV 2017
Year: 2017

With the rise of end-to-end learning through deep learning, person detectors and re-identification (ReID) models have recently become very strong. Multi-camera multi-target (MCMT) tracking has not fully gone through this transformation yet. We intend to take another step in this direction by presenting a theoretically principled way of integrating ReID with tracking formulated as an optimal Bayes filter. This conveniently side-steps the need for data-association and opens up a direct path from full images to the core of the tracker. While the results are still sub-par, we believe that this new, tight integration opens many interesting research opportunities and leads the way towards full end-to-end tracking from raw pixels.
Single Image Action Recognition by Predicting Space-Time Saliency
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel approach based on deep Convolutional Neural Networks (CNN) to recognize human actions in still images by predicting the future motion, and detecting the shape and location of the salient parts of the image. We make the following major contributions to this important area of research: (i) We use the predicted future motion in the static image (Walker et al., 2015) as a means of compensating for the missing temporal information, while using the saliency map to represent the the spatial information in the form of location and shape of what is predicted as significant. (ii) We cast action classification in static images as a domain adaptation problem by transfer learning. We first map the input static image to a new domain that we refer to as the Predicted Optical Flow-Saliency Map domain (POF-SM), and then fine-tune the layers of a deep CNN model trained on classifying the ImageNet dataset to perform action classification in the POF-SM domain. (iii) We tested our method on the popular Willow dataset. But unlike existing methods, we also tested on a more realistic and challenging dataset of over 2M still images that we collected and labeled by taking random frames from the UCF-101 video dataset. We call our dataset the UCF Still Image dataset or UCFSI-101 in short. Our results outperform the state of the art.
Feedback Techniques in Computer-Based Simulation Training: A Survey
Venue: arXiv cs.HC 2017
Year: 2017

Computer-based simulation training (CBST) is gaining popularity in a vast range of applications such as surgery, rehabilitation therapy, military applications, and driver/pilot training, as it offers a low-cost, easily-accessible and effective training environment. Typically, CBST systems comprise of two essential components: 1) a simulation environment that provides an immersive and interactive learning experience, and 2) a feedback intervention system that supports knowledge/skill acquisition and decision making. The simulation environment is created using technologies such as virtual or augmented reality, and this is an area which has gained much interest in recent years. The provision of automated feedback in CBST however, has not been investigated as much, and thus, is the focus of this paper. Feedback is an essential component in learning, and should be provided to the trainee during the training process in order to improve skills, to correct mistakes, and most importantly, to inspire reasoning and critical thinking. In CBST, feedback should be provided in a useful and timely manner, ideally in a way that mimics the advice of an experienced tutor. Here, we explore the provision of feedback in CBST from three perspectives: 1) types of feedback to be provided, 2) presentation modalities of feedback, and 3) methods for feedback extraction/learning. This review is aimed at providing insight into how feedback is extracted, organized, and delivered in current applications, to be used as a guide to the development of future feedback intervention systems in CBST applications.
Deep Learning Microscopy
Venue: arXiv cs.LG 2017
Year: 2017

We demonstrate that a deep neural network can significantly improve optical microscopy, enhancing its spatial resolution over a large field-of-view and depth-of-field. After its training, the only input to this network is an image acquired using a regular optical microscope, without any changes to its design. We blindly tested this deep learning approach using various tissue samples that are imaged with low-resolution and wide-field systems, where the network rapidly outputs an image with remarkably better resolution, matching the performance of higher numerical aperture lenses, also significantly surpassing their limited field-of-view and depth-of-field. These results are transformative for various fields that use microscopy tools, including e.g., life sciences, where optical microscopy is considered as one of the most widely used and deployed techniques. Beyond such applications, our presented approach is broadly applicable to other imaging modalities, also spanning different parts of the electromagnetic spectrum, and can be used to design computational imagers that get better and better as they continue to image specimen and establish new transformations among different modes of imaging.