OpenRaiser/Intern-Atlas huggingface dataset:
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Venue: arXiv cs.DC 2017
Year: 2017

We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires $Ω(n^2/\log^2{n})$ rounds in the worst case in the CONGEST model, as well as any algorithm for $χ$-coloring a graph, where $χ$ is the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple $Ω(n)$ lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a complexity of $Θ(n/\log{n})$. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
A Long Short-Term Memory Recurrent Neural Network Framework for Network Traffic Matrix Prediction
Venue: arXiv cs.NI 2017
Year: 2017

Network Traffic Matrix (TM) prediction is defined as the problem of estimating future network traffic from the previous and achieved network traffic data. It is widely used in network planning, resource management and network security. Long Short-Term Memory (LSTM) is a specific recurrent neural network (RNN) architecture that is well-suited to learn from experience to classify, process and predict time series with time lags of unknown size. LSTMs have been shown to model temporal sequences and their long-range dependencies more accurately than conventional RNNs. In this paper, we propose a LSTM RNN framework for predicting short and long term Traffic Matrix (TM) in large networks. By validating our framework on real-world data from GEANT network, we show that our LSTM models converge quickly and give state of the art TM prediction performance for relatively small sized models.
A General Scheme Implicit Force Control for a Flexible-Link Manipulator
Venue: arXiv cs.RO 2017
Year: 2017

In this paper we propose an implicit force control scheme for a one-link flexible manipulator that interact with a compliant environment. The controller was based in the mathematical model of the manipulator, considering the dynamics of the beam flexible and the gravitational force. With this method, the controller parameters are obtained from the structural parameters of the beam (link) of the manipulator. This controller ensure the stability based in the Lyapunov Theory. The controller proposed has two closed loops: the inner loop is a tracking control with gravitational force and vibration frequencies compensation and the outer loop is a implicit force control. To evaluate the performance of the controller, we have considered to three different manipulators (the length, the diameter were modified) and three environments with compliance modified. The results obtained from simulations verify the asymptotic tracking and regulated in position and force respectively and the vibrations suppression of the beam in a finite time.
Comparison-Based Choices
Venue: arXiv cs.DS 2017
Year: 2017

A broad range of on-line behaviors are mediated by interfaces in which people make choices among sets of options. A rich and growing line of work in the behavioral sciences indicate that human choices follow not only from the utility of alternatives, but also from the choice set in which alternatives are presented. In this work we study comparison-based choice functions, a simple but surprisingly rich class of functions capable of exhibiting so-called choice-set effects. Motivated by the challenge of predicting complex choices, we study the query complexity of these functions in a variety of settings. We consider settings that allow for active queries or passive observation of a stream of queries, and give analyses both at the granularity of individuals or populations that might exhibit heterogeneous choice behavior. Our main result is that any comparison-based choice function in one dimension can be inferred as efficiently as a basic maximum or minimum choice function across many query contexts, suggesting that choice-set effects need not entail any fundamental algorithmic barriers to inference. We also introduce a class of choice functions we call distance-comparison-based functions, and briefly discuss the analysis of such functions. The framework we outline provides intriguing connections between human choice behavior and a range of questions in the theory of sorting.
Stochastic k-Server: How Should Uber Work?
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we study a stochastic variant of the celebrated k-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are serving an online sequence of t requests in a metric. In the stochastic setting we are given t independent distributions <P_1, P_2,..., P_t> in advance, and at every time step i a request is drawn from Pi. Designing the optimal online algorithm in such setting is NP-hard, therefore the emphasis of our work is on designing an approximately optimal online algorithm. We first show a structural characterization for a certain class of non-adaptive online algorithms. We prove that in general metrics, the best of such algorithms has a cost of no worse than three times that of the optimal online algorithm. Next, we present an integer program that finds the optimal algorithm of this class for any arbitrary metric. Finally, by rounding the solution of the linear relaxation of this program, we present an online algorithm for the stochastic k-server problem with the approximation factor of 3 in the line and circle metrics and O(log n) in a general metric of size n. Moreover, we define the Uber problem, in which each demand consists of two endpoints, a source and a destination. We show that given an a-approximation algorithm for the k-server problem, we can obtain an (a+2)-approximation algorithm for the Uber problem. Motivated by the fact that demands are usually highly correlated with the time we study the stochastic Uber problem. Furthermore, we extend our results to the correlated setting where the probability of a request arriving at a certain point depends not only on the time step but also on the previously arrived requests.
All-relevant feature selection using multidimensional filters with exhaustive search
Venue: arXiv cs.AI 2017
Year: 2017

This paper describes a method for identification of the informative variables in the information system with discrete decision variables. It is targeted specifically towards discovery of the variables that are non-informative when considered alone, but are informative when the synergistic interactions between multiple variables are considered. To this end, the mutual entropy of all possible k-tuples of variables with decision variable is computed. Then, for each variable the maximal information gain due to interactions with other variables is obtained. For non-informative variables this quantity conforms to the well known statistical distributions. This allows for discerning truly informative variables from non-informative ones. For demonstration of the approach, the method is applied to several synthetic datasets that involve complex multidimensional interactions between variables. It is capable of identifying most important informative variables, even in the case when the dimensionality of the analysis is smaller than the true dimensionality of the problem. What is more, the high sensitivity of the algorithm allows for detection of the influence of nuisance variables on the response variable.
Demystifying Relational Latent Representations
Venue: arXiv cs.AI 2017
Year: 2017

Latent features learned by deep learning approaches have proven to be a powerful tool for machine learning. They serve as a data abstraction that makes learning easier by capturing regularities in data explicitly. Their benefits motivated their adaptation to relational learning context. In our previous work, we introduce an approach that learns relational latent features by means of clustering instances and their relations. The major drawback of latent representations is that they are often black-box and difficult to interpret. This work addresses these issues and shows that (1) latent features created by clustering are interpretable and capture interesting properties of data; (2) they identify local regions of instances that match well with the label, which partially explains their benefit; and (3) although the number of latent features generated by this approach is large, often many of them are highly redundant and can be removed without hurting performance much.
Lagrangian Reachabililty
Venue: arXiv cs.SY 2017
Year: 2017

We introduce LRT, a new Lagrangian-based ReachTube computation algorithm that conservatively approximates the set of reachable states of a nonlinear dynamical system. LRT makes use of the Cauchy-Green stretching factor (SF), which is derived from an over-approximation of the gradient of the solution flows. The SF measures the discrepancy between two states propagated by the system solution from two initial states lying in a well-defined region, thereby allowing LRT to compute a reachtube with a ball-overestimate in a metric where the computed enclosure is as tight as possible. To evaluate its performance, we implemented a prototype of LRT in C++/Matlab, and ran it on a set of well-established benchmarks. Our results show that LRT compares very favorably with respect to the CAPD and Flow* tools.
Subregular Complexity and Deep Learning
Venue: arXiv cs.CL 2017
Year: 2017

This paper argues that the judicial use of formal language theory and grammatical inference are invaluable tools in understanding how deep neural networks can and cannot represent and learn long-term dependencies in temporal sequences. Learning experiments were conducted with two types of Recurrent Neural Networks (RNNs) on six formal languages drawn from the Strictly Local (SL) and Strictly Piecewise (SP) classes. The networks were Simple RNNs (s-RNNs) and Long Short-Term Memory RNNs (LSTMs) of varying sizes. The SL and SP classes are among the simplest in a mathematically well-understood hierarchy of subregular classes. They encode local and long-term dependencies, respectively. The grammatical inference algorithm Regular Positive and Negative Inference (RPNI) provided a baseline. According to earlier research, the LSTM architecture should be capable of learning long-term dependencies and should outperform s-RNNs. The results of these experiments challenge this narrative. First, the LSTMs' performance was generally worse in the SP experiments than in the SL ones. Second, the s-RNNs out-performed the LSTMs on the most complex SP experiment and performed comparably to them on the others.
Differentially Private Release of Public Transport Data: The Opal Use Case
Venue: arXiv cs.CR 2017
Year: 2017

This document describes the application of a differentially private algorithm to release public transport usage data from Transport for New South Wales (TfNSW), Australia. The data consists of two separate weeks of "tap-on/tap-off" data of individuals who used any of the four different modes of public transport from TfNSW: buses, light rail, train and ferries. These taps are recorded through the smart ticketing system, known as Opal, available in the state of New South Wales, Australia.
Polar-Coded Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2017
Year: 2017

Non-orthogonal multiple access (NOMA) is one of the key techniques to address the high spectral efficiency and massive connectivity requirements for the fifth generation (5G) wireless system. To efficiently realize NOMA, we propose a joint design framework combining the polar coding and the NOMA transmission, which deeply mines the generalized polarization effect among the users. In this polar coded NOMA (PC-NOMA) framework, the original NOMA channel is decomposed into multiple bit polarized channels by using a three-stage channel transform, that is, user$\to$signal$\to$bit partitions. Specifically, for the first-stage channel transform, we design two schemes, namely sequential user partition (SUP) and parallel user partition (PUP). For the SUP, a joint successive cancellation detecting and decoding scheme is developed, and a search algorithm is proposed to schedule the NOMA detecting order which improves the system performance by enhanced polarization among the user synthesized channels. The "worst-goes-first" idea is employed in the scheduling strategy, and its theoretic performance is analyzed by using the polarization principle. For the PUP, a corresponding parallel detecting scheme is exploited to reduce the latency. The block error ratio performances over the additive white Gaussian noise channel and the Rayleigh fading channel indicate that the proposed PC-NOMA obviously outperforms the state-of-the-art turbo coded NOMA scheme due to the advantages of joint design between the polar coding and NOMA.
AI, Native Supercomputing and The Revival of Moore's Law
Venue: arXiv cs.AI 2017
Year: 2017

Based on Alan Turing's proposition on AI and computing machinery, which shaped Computing as we know it today, the new AI computing machinery should comprise a universal computer and a universal learning machine. The later should understand linear algebra natively to overcome the slowdown of Moore's law. In such a universal learnig machine, a computing unit does not need to keep the legacy of a universal computing core. The data can be distributed to the computing units, and the results can be collected from them through Collective Streaming, reminiscent of Collective Communication in Supercomputing. It is not necessary to use a GPU-like deep memory hierarchy, nor a TPU-like fine-grain mesh.
PaMM: Pose-aware Multi-shot Matching for Improving Person Re-identification
Venue: arXiv cs.CV 2017
Year: 2017

Person re-identification is the problem of recognizing people across different images or videos with non-overlapping views. Although there has been much progress in person re-identification over the last decade, it remains a challenging task because appearances of people can seem extremely different across diverse camera viewpoints and person poses. In this paper, we propose a novel framework for person re-identification by analyzing camera viewpoints and person poses in a so-called Pose-aware Multi-shot Matching (PaMM), which robustly estimates people's poses and efficiently conducts multi-shot matching based on pose information. Experimental results using public person re-identification datasets show that the proposed methods outperform state-of-the-art methods and are promising for person re-identification from diverse viewpoints and pose variances.
Millimeter Wave Communications for Future Mobile Networks
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave (mmWave) communications have recently attracted large research interest, since the huge available bandwidth can potentially lead to rates of multiple Gbps (gigabit per second) per user. Though mmWave can be readily used in stationary scenarios such as indoor hotspots or backhaul, it is challenging to use mmWave in mobile networks, where the transmitting/receiving nodes may be moving, channels may have a complicated structure, and the coordination among multiple nodes is difficult. To fully exploit the high potential rates of mmWave in mobile networks, lots of technical problems must be addressed. This paper presents a comprehensive survey of mmWave communications for future mobile networks (5G and beyond). We first summarize the recent channel measurement campaigns and modeling results. Then, we discuss in detail recent progresses in multiple input multiple output (MIMO) transceiver design for mmWave communications. After that, we provide an overview of the solution for multiple access and backhauling, followed by analysis of coverage and connectivity. Finally, the progresses in the standardization and deployment of mmWave for mobile networks are discussed.
Unlabeled Data for Morphological Generation With Character-Based Sequence-to-Sequence Models
Venue: arXiv cs.CL 2017
Year: 2017

We present a semi-supervised way of training a character-based encoder-decoder recurrent neural network for morphological reinflection, the task of generating one inflected word form from another. This is achieved by using unlabeled tokens or random strings as training data for an autoencoding task, adapting a network for morphological reinflection, and performing multi-task training. We thus use limited labeled data more effectively, obtaining up to 9.9% improvement over state-of-the-art baselines for 8 different languages.
Estimating Sequence Similarity from Read Sets for Clustering Next-Generation Sequencing data
Venue: arXiv cs.DS 2017
Year: 2017

To cluster sequences given only their read-set representations, one may try to reconstruct each one from the corresponding read set, and then employ conventional (dis)similarity measures such as the edit distance on the assembled sequences. This approach is however problematic and we propose instead to estimate the similarities directly from the read sets. Our approach is based on an adaptation of the Monge-Elkan similarity known from the field of databases. It avoids the NP-hard problem of sequence assembly. For low coverage data it results in a better approximation of the true sequence similarities and consequently in better clustering, in comparison to the first-assemble-then-cluster approach.
Practical Processing of Mobile Sensor Data for Continual Deep Learning Predictions
Venue: arXiv cs.LG 2017
Year: 2017

We present a practical approach for processing mobile sensor time series data for continual deep learning predictions. The approach comprises data cleaning, normalization, capping, time-based compression, and finally classification with a recurrent neural network. We demonstrate the effectiveness of the approach in a case study with 279 participants. On the basis of sparse sensor events, the network continually predicts whether the participants would attend to a notification within 10 minutes. Compared to a random baseline, the classifier achieves a 40% performance increase (AUC of 0.702) on a withheld test set. This approach allows to forgo resource-intensive, domain-specific, error-prone feature engineering, which may drastically increase the applicability of machine learning to mobile phone sensor data.
Shape Classification using Spectral Graph Wavelets
Venue: arXiv cs.GR 2017
Year: 2017

Spectral shape descriptors have been used extensively in a broad spectrum of geometry processing applications ranging from shape retrieval and segmentation to classification. In this pa- per, we propose a spectral graph wavelet approach for 3D shape classification using the bag-of-features paradigm. In an effort to capture both the local and global geometry of a 3D shape, we present a three-step feature description framework. First, local descriptors are extracted via the spectral graph wavelet transform having the Mexican hat wavelet as a generating ker- nel. Second, mid-level features are obtained by embedding lo- cal descriptors into the visual vocabulary space using the soft- assignment coding step of the bag-of-features model. Third, a global descriptor is constructed by aggregating mid-level fea- tures weighted by a geodesic exponential kernel, resulting in a matrix representation that describes the frequency of appearance of nearby codewords in the vocabulary. Experimental results on two standard 3D shape benchmarks demonstrate the effective- ness of the proposed classification approach in comparison with state-of-the-art methods.
CardiacNET: Segmentation of Left Atrium and Proximal Pulmonary Veins from MRI Using Multi-View CNN
Venue: arXiv cs.CV 2017
Year: 2017

Anatomical and biophysical modeling of left atrium (LA) and proximal pulmonary veins (PPVs) is important for clinical management of several cardiac diseases. Magnetic resonance imaging (MRI) allows qualitative assessment of LA and PPVs through visualization. However, there is a strong need for an advanced image segmentation method to be applied to cardiac MRI for quantitative analysis of LA and PPVs. In this study, we address this unmet clinical need by exploring a new deep learning-based segmentation strategy for quantification of LA and PPVs with high accuracy and heightened efficiency. Our approach is based on a multi-view convolutional neural network (CNN) with an adaptive fusion strategy and a new loss function that allows fast and more accurate convergence of the backpropagation based optimization. After training our network from scratch by using more than 60K 2D MRI images (slices), we have evaluated our segmentation strategy to the STACOM 2013 cardiac segmentation challenge benchmark. Qualitative and quantitative evaluations, obtained from the segmentation challenge, indicate that the proposed method achieved the state-of-the-art sensitivity (90%), specificity (99%), precision (94%), and efficiency levels (10 seconds in GPU, and 7.5 minutes in CPU).
Political Footprints: Political Discourse Analysis using Pre-Trained Word Vectors
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we discuss how machine learning could be used to produce a systematic and more objective political discourse analysis. Political footprints are vector space models (VSMs) applied to political discourse. Each of their vectors represents a word, and is produced by training the English lexicon on large text corpora. This paper presents a simple implementation of political footprints, some heuristics on how to use them, and their application to four cases: the U.N. Kyoto Protocol and Paris Agreement, and two U.S. presidential elections. The reader will be offered a number of reasons to believe that political footprints produce meaningful results, along with some suggestions on how to improve their implementation.
Optimizing and Visualizing Deep Learning for Benign/Malignant Classification in Breast Tumors
Venue: arXiv cs.CV 2017
Year: 2017

Breast cancer has the highest incidence and second highest mortality rate for women in the US. Our study aims to utilize deep learning for benign/malignant classification of mammogram tumors using a subset of cases from the Digital Database of Screening Mammography (DDSM). Though it was a small dataset from the view of Deep Learning (about 1000 patients), we show that currently state of the art architectures of deep learning can find a robust signal, even when trained from scratch. Using convolutional neural networks (CNNs), we are able to achieve an accuracy of 85% and an ROC AUC of 0.91, while leading hand-crafted feature based methods are only able to achieve an accuracy of 71%. We investigate an amalgamation of architectures to show that our best result is reached with an ensemble of the lightweight GoogLe Nets tasked with interpreting both the coronal caudal view and the mediolateral oblique view, simply averaging the probability scores of both views to make the final prediction. In addition, we have created a novel method to visualize what features the neural network detects for the benign/malignant classification, and have correlated those features with well known radiological features, such as spiculation. Our algorithm significantly improves existing classification methods for mammography lesions and identifies features that correlate with established clinical markers.