OpenRaiser/Intern-Atlas huggingface dataset:
An Empirical Analysis of Approximation Algorithms for the Euclidean Traveling Salesman Problem
Venue: arXiv cs.AI 2017
Year: 2017

With applications to many disciplines, the traveling salesman problem (TSP) is a classical computer science optimization problem with applications to industrial engineering, theoretical computer science, bioinformatics, and several other disciplines. In recent years, there have been a plethora of novel approaches for approximate solutions ranging from simplistic greedy to cooperative distributed algorithms derived from artificial intelligence. In this paper, we perform an evaluation and analysis of cornerstone algorithms for the Euclidean TSP. We evaluate greedy, 2-opt, and genetic algorithms. We use several datasets as input for the algorithms including a small dataset, a mediumsized dataset representing cities in the United States, and a synthetic dataset consisting of 200 cities to test algorithm scalability. We discover that the greedy and 2-opt algorithms efficiently calculate solutions for smaller datasets. Genetic algorithm has the best performance for optimality for medium to large datasets, but generally have longer runtime. Our implementations is public available.
Wireless Powered Communications with Finite Battery and Finite Blocklength
Venue: arXiv cs.IT 2017
Year: 2017

We analyze a wireless communication system with finite block length and finite battery energy, under quasi-static Nakagami-m fading. Wireless energy transfer is carried out in the downlink while information transfer occurs in the uplink. Transmission strategies for scenarios with/without energy accumulation between transmission rounds are characterized in terms of error probability and energy consumption. A power control protocol for the energy accumulation scenario is proposed and results show the enormous impact on improving the system performance, in terms of error probability and energy consumption. The numerical results corroborate the existence and uniqueness of an optimum target error probability, while showing that a relatively small battery could be a limiting factor for some setups, specially when using the energy accumulation strategy.
Mobility Management as a Service for 5G Networks
Venue: arXiv cs.NI 2017
Year: 2017

Mobility Management (MM) techniques have conventionally been centralized in nature, wherein a single network entity has been responsible for handling the mobility related tasks of the mobile nodes attached to the network. However, an exponential growth in network traffic and the number of users has ushered in the concept of providing Mobility Management as a Service (MMaaS) to the wireless nodes attached to the 5G networks. Allowing for on-demand mobility management solutions will not only provide the network with the flexibility that it needs to accommodate the many different use cases that are to be served by future networks, but it will also provide the network with the scalability that is needed alongside the flexibility to serve future networks. And hence, in this paper, a detailed study of MMaaS has been provided, highlighting its benefits and challenges for 5G networks. Additionally, the very important property of granularity of service which is deeply intertwined with the scalability and flexibility requirements of the future wireless networks, and a consequence of MMaaS, has also been discussed in detail.
SLAM based Quasi Dense Reconstruction For Minimally Invasive Surgery Scenes
Venue: arXiv cs.CV 2017
Year: 2017

Recovering surgical scene structure in laparoscope surgery is crucial step for surgical guidance and augmented reality applications. In this paper, a quasi dense reconstruction algorithm of surgical scene is proposed. This is based on a state-of-the-art SLAM system, and is exploiting the initial exploration phase that is typically performed by the surgeon at the beginning of the surgery. We show how to convert the sparse SLAM map to a quasi dense scene reconstruction, using pairs of keyframe images and correlation-based featureless patch matching. We have validated the approach with a live porcine experiment using Computed Tomography as ground truth, yielding a Root Mean Squared Error of 4.9mm.
Neural Decomposition of Time-Series Data for Effective Generalization
Venue: arXiv cs.NE 2017
Year: 2017

We present a neural network technique for the analysis and extrapolation of time-series data called Neural Decomposition (ND). Units with a sinusoidal activation function are used to perform a Fourier-like decomposition of training samples into a sum of sinusoids, augmented by units with nonperiodic activation functions to capture linear trends and other nonperiodic components. We show how careful weight initialization can be combined with regularization to form a simple model that generalizes well. Our method generalizes effectively on the Mackey-Glass series, a dataset of unemployment rates as reported by the U.S. Department of Labor Statistics, a time-series of monthly international airline passengers, the monthly ozone concentration in downtown Los Angeles, and an unevenly sampled time-series of oxygen isotope measurements from a cave in north India. We find that ND outperforms popular time-series forecasting techniques including LSTM, echo state networks, ARIMA, SARIMA, SVR with a radial basis function, and Gashler and Ashmore's model.
Investigation of Using VAE for i-Vector Speaker Verification
Venue: arXiv cs.SD 2017
Year: 2017

New system for i-vector speaker recognition based on variational autoencoder (VAE) is investigated. VAE is a promising approach for developing accurate deep nonlinear generative models of complex data. Experiments show that VAE provides speaker embedding and can be effectively trained in an unsupervised manner. LLR estimate for VAE is developed. Experiments on NIST SRE 2010 data demonstrate its correctness. Additionally, we show that the performance of VAE-based system in the i-vectors space is close to that of the diagonal PLDA. Several interesting results are also observed in the experiments with $β$-VAE. In particular, we found that for $β\ll 1$, VAE can be trained to capture the features of complex input data distributions in an effective way, which is hard to obtain in the standard VAE ($β=1$).
Jointly Learning Sentence Embeddings and Syntax with Unsupervised Tree-LSTMs
Venue: arXiv cs.CL 2017
Year: 2017

We introduce a neural network that represents sentences by composing their words according to induced binary parse trees. We use Tree-LSTM as our composition function, applied along a tree structure found by a fully differentiable natural language chart parser. Our model simultaneously optimises both the composition function and the parser, thus eliminating the need for externally-provided parse trees which are normally required for Tree-LSTM. It can therefore be seen as a tree-based RNN that is unsupervised with respect to the parse trees. As it is fully differentiable, our model is easily trained with an off-the-shelf gradient descent method and backpropagation. We demonstrate that it achieves better performance compared to various supervised Tree-LSTM architectures on a textual entailment task and a reverse dictionary task.
Together We Know How to Achieve: An Epistemic Logic of Know-How
Venue: arXiv cs.AI 2017
Year: 2017

The existence of a coalition strategy to achieve a goal does not necessarily mean that the coalition has enough information to know how to follow the strategy. Neither does it mean that the coalition knows that such a strategy exists. The article studies an interplay between the distributed knowledge, coalition strategies, and coalition "know-how" strategies. The main technical result is a sound and complete trimodal logical system that describes the properties of this interplay.
Canonical Selection of Colimits
Venue: arXiv cs.LO 2017
Year: 2017

Colimits are a powerful tool for the combination of objects in a category. In the context of modeling and specification, they are used in the institution-independent semantics (1) of instantiations of parameterised specifications (e.g. in the specification language CASL), and (2) of combinations of networks of specifications (in the OMG standardised language DOL).
Parallel Space-Time Kernel Density Estimation
Venue: arXiv cs.DC 2017
Year: 2017

The exponential growth of available data has increased the need for interactive exploratory analysis. Dataset can no longer be understood through manual crawling and simple statistics. In Geographical Information Systems (GIS), the dataset is often composed of events localized in space and time; and visualizing such a dataset involves building a map of where the events occurred. We focus in this paper on events that are localized among three dimensions (latitude, longitude, and time), and on computing the first step of the visualization pipeline, space-time kernel density estimation (STKDE), which is most computationally expensive. Starting from a gold standard implementation, we show how algorithm design and engineering, parallel decomposition, and scheduling can be applied to bring near real-time computing to space-time kernel density estimation. We validate our techniques on real world datasets extracted from infectious disease, social media, and ornithology.
Unsupervised Feature Learning for Writer Identification and Writer Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

Deep Convolutional Neural Networks (CNN) have shown great success in supervised classification tasks such as character classification or dating. Deep learning methods typically need a lot of annotated training data, which is not available in many scenarios. In these cases, traditional methods are often better than or equivalent to deep learning methods. In this paper, we propose a simple, yet effective, way to learn CNN activation features in an unsupervised manner. Therefore, we train a deep residual network using surrogate classes. The surrogate classes are created by clustering the training dataset, where each cluster index represents one surrogate class. The activations from the penultimate CNN layer serve as features for subsequent classification tasks. We evaluate the feature representations on two publicly available datasets. The focus lies on the ICDAR17 competition dataset on historical document writer identification (Historical-WI). We show that the activation features trained without supervision are superior to descriptors of state-of-the-art writer identification methods. Additionally, we achieve comparable results in the case of handwriting classification using the ICFHR16 competition dataset on historical Latin script types (CLaMM16).
Centralized vs Decentralized Multi-Agent Guesswork
Venue: arXiv cs.IT 2017
Year: 2017

We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork.
Confidentiality-Preserving Publish/Subscribe: A Survey
Venue: arXiv cs.CR 2017
Year: 2017

Publish/subscribe (pub/sub) is an attractive communication paradigm for large-scale distributed applications running across multiple administrative domains. Pub/sub allows event-based information dissemination based on constraints on the nature of the data rather than on pre-established communication channels. It is a natural fit for deployment in untrusted environments such as public clouds linking applications across multiple sites. However, pub/sub in untrusted environments lead to major confidentiality concerns stemming from the content-centric nature of the communications. This survey classifies and analyzes different approaches to confidentiality preservation for pub/sub, from applications of trust and access control models to novel encryption techniques. It provides an overview of the current challenges posed by confidentiality concerns and points to future research directions in this promising field.
Duel and sweep algorithm for order-preserving pattern matching
Venue: arXiv cs.DS 2017
Year: 2017

Given a text $T$ and a pattern $P$ over alphabet $Σ$, the classic exact matching problem searches for all occurrences of pattern $P$ in text $T$. Unlike exact matching problem, order-preserving pattern matching (OPPM) considers the relative order of elements, rather than their real values. In this paper, we propose an efficient algorithm for OPPM problem using the "duel-and-sweep" paradigm. Our algorithm runs in $O(n + m\log m)$ time in general and $O(n + m)$ time under an assumption that the characters in a string can be sorted in linear time with respect to the string size. We also perform experiments and show that our algorithm is faster that KMP-based algorithm. Last, we introduce the two-dimensional order preserved pattern matching and give a duel and sweep algorithm that runs in $O(n^2)$ time for duel stage and $O(n^2 m)$ time for sweeping time with $O(m^3)$ preprocessing time.
Classification regions of deep neural networks
Venue: arXiv cs.CV 2017
Year: 2017

The goal of this paper is to analyze the geometric properties of deep neural network classifiers in the input space. We specifically study the topology of classification regions created by deep networks, as well as their associated decision boundary. Through a systematic empirical investigation, we show that state-of-the-art deep nets learn connected classification regions, and that the decision boundary in the vicinity of datapoints is flat along most directions. We further draw an essential connection between two seemingly unrelated properties of deep networks: their sensitivity to additive perturbations in the inputs, and the curvature of their decision boundary. The directions where the decision boundary is curved in fact remarkably characterize the directions to which the classifier is the most vulnerable. We finally leverage a fundamental asymmetry in the curvature of the decision boundary of deep nets, and propose a method to discriminate between original images, and images perturbed with small adversarial examples. We show the effectiveness of this purely geometric approach for detecting small adversarial perturbations in images, and for recovering the labels of perturbed images.
Enhancement of SSD by concatenating feature maps for object detection
Venue: arXiv cs.CV 2017
Year: 2017

We propose an object detection method that improves the accuracy of the conventional SSD (Single Shot Multibox Detector), which is one of the top object detection algorithms in both aspects of accuracy and speed. The performance of a deep network is known to be improved as the number of feature maps increases. However, it is difficult to improve the performance by simply raising the number of feature maps. In this paper, we propose and analyze how to use feature maps effectively to improve the performance of the conventional SSD. The enhanced performance was obtained by changing the structure close to the classifier network, rather than growing layers close to the input data, e.g., by replacing VGGNet with ResNet. The proposed network is suitable for sharing the weights in the classifier networks, by which property, the training can be faster with better generalization power. For the Pascal VOC 2007 test set trained with VOC 2007 and VOC 2012 training sets, the proposed network with the input size of 300 x 300 achieved 78.5% mAP (mean average precision) at the speed of 35.0 FPS (frame per second), while the network with a 512 x 512 sized input achieved 80.8% mAP at 16.6 FPS using Nvidia Titan X GPU. The proposed network shows state-of-the-art mAP, which is better than those of the conventional SSD, YOLO, Faster-RCNN and RFCN. Also, it is faster than Faster-RCNN and RFCN.
Combinatorial Multi-Armed Bandits with Filtered Feedback
Venue: arXiv cs.LG 2017
Year: 2017

Motivated by problems in search and detection we present a solution to a Combinatorial Multi-Armed Bandit (CMAB) problem with both heavy-tailed reward distributions and a new class of feedback, filtered semibandit feedback. In a CMAB problem an agent pulls a combination of arms from a set $\{1,...,k\}$ in each round, generating random outcomes from probability distributions associated with these arms and receiving an overall reward. Under semibandit feedback it is assumed that the random outcomes generated are all observed. Filtered semibandit feedback allows the outcomes that are observed to be sampled from a second distribution conditioned on the initial random outcomes. This feedback mechanism is valuable as it allows CMAB methods to be applied to sequential search and detection problems where combinatorial actions are made, but the true rewards (number of objects of interest appearing in the round) are not observed, rather a filtered reward (the number of objects the searcher successfully finds, which must by definition be less than the number that appear). We present an upper confidence bound type algorithm, Robust-F-CUCB, and associated regret bound of order $\mathcal{O}(\ln(n))$ to balance exploration and exploitation in the face of both filtering of reward and heavy tailed reward distributions.
SMORE: A Cold Data Object Store for SMR Drives (Extended Version)
Venue: arXiv cs.OS 2017
Year: 2017

Shingled magnetic recording (SMR) increases the capacity of magnetic hard drives, but it requires that each zone of a disk be written sequentially and erased in bulk. This makes SMR a good fit for workloads dominated by large data objects with limited churn. To explore this possibility, we have developed SMORE, an object storage system designed to reliably and efficiently store large, seldom-changing data objects on an array of host-managed or host-aware SMR disks. SMORE uses a log-structured approach to accommodate the constraint that all writes to an SMR drive must be sequential within large shingled zones. It stripes data across zones on separate disks, using erasure coding to protect against drive failure. A separate garbage collection thread reclaims space by migrating live data out of the emptiest zones so that they can be trimmed and reused. An index stored on flash and backed up to the SMR drives maps object identifiers to on-disk locations. SMORE interleaves log records with object data within SMR zones to enable index recovery after a system crash (or failure of the flash device) without any additional logging mechanism. SMORE achieves full disk bandwidth when ingesting data---with a variety of object sizes---and when reading large objects. Read performance declines for smaller object sizes where inter- object seek time dominates. With a worst-case pattern of random deletions, SMORE has a write amplification (not counting RAID parity) of less than 2.0 at 80% occupancy. By taking an index snapshot every two hours, SMORE recovers from crashes in less than a minute. More frequent snapshots allow faster recovery.
Lock-step simulation is child's play
Venue: arXiv cs.PL 2017
Year: 2017

Implementing multi-player networked games by broadcasting the player's input and letting each client calculate the game state - a scheme known as lock-step simulation - is an established technique. However, ensuring that every client in this scheme obtains a consistent state is infamously hard and in general requires great discipline from the game programmer. The thesis of this report is that in the realm of functional programming - in particular with Haskell's purity and static pointers - this hard problem becomes almost trivially easy. We support this thesis by implementing lock-step simulation under very adverse conditions. We extended the educational programming environment CodeWorld, which is used to teach math and programming to middle school students, with the ability to create and run interactive, networked multi-user games. Despite providing a very abstract and high-level interface, and without requiring
Is It Reasonable to Substitute Discontinuous SMC by Continuous HOSMC?
Venue: arXiv cs.SY 2017
Year: 2017

Professor Utkin in his discussion paper proposed an example showing that the amplitude of chattering caused by the presence of parasitic dynamics in systems governed by First-Order Sliding-Mode Control (FOSMC) is lower than the obtained using Super-Twisting Algorithm (STA). This example served to motivate this research reconsidering the problem of comparison of chattering magnitude in systems governed by FOSMC that produces a discontinuous control signal and by STA that produces a continuous one, using Harmonic Balance (HB) methodology. With this aim the Averaged Power (AP) criteria for chattering measurements is revisited. The STA gains are redesigned to minimize amplitude or AP of oscillations predicted by HB. The comparison of the chattering produced by FOSMC and STA with redesigned gains is analyzed taking into account their amplitudes, frequencies and values of AP allowing to conclude that: (a) for any value of upperbound of disturbance and Actuator Time Constant (ATC) there exist a bounded disturbance for which the amplitude and AP of chattering produced by FOSMC is lower than the caused by STA; (b) if the upperbound of disturbance and upperbound of time-derivative disturbance are given, then for all sufficiently small values of ATC the amplitude of chattering and AP produced by STA will be smaller than the caused by FOSMC; (c) critical values of ATC are predicted by HB for which the parameters, amplitude of chattering and AP, produced by FOSMC and STA are the same. Also the frequency of self-exited oscillations caused by FOSMC is always grater than the produced by STA.
Direct Estimation of Regional Wall Thicknesses via Residual Recurrent Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

Accurate estimation of regional wall thicknesses (RWT) of left ventricular (LV) myocardium from cardiac MR sequences is of significant importance for identification and diagnosis of cardiac disease. Existing RWT estimation still relies on segmentation of LV myocardium, which requires strong prior information and user interaction. No work has been devoted into direct estimation of RWT from cardiac MR images due to the diverse shapes and structures for various subjects and cardiac diseases, as well as the complex regional deformation of LV myocardium during the systole and diastole phases of the cardiac cycle. In this paper, we present a newly proposed Residual Recurrent Neural Network (ResRNN) that fully leverages the spatial and temporal dynamics of LV myocardium to achieve accurate frame-wise RWT estimation. Our ResRNN comprises two paths: 1) a feed forward convolution neural network (CNN) for effective and robust CNN embedding learning of various cardiac images and preliminary estimation of RWT from each frame itself independently, and 2) a recurrent neural network (RNN) for further improving the estimation by modeling spatial and temporal dynamics of LV myocardium. For the RNN path, we design for cardiac sequences a Circle-RNN to eliminate the effect of null hidden input for the first time-step. Our ResRNN is capable of obtaining accurate estimation of cardiac RWT with Mean Absolute Error of 1.44mm (less than 1-pixel error) when validated on cardiac MR sequences of 145 subjects, evidencing its great potential in clinical cardiac function assessment.