OpenRaiser/Intern-Atlas huggingface dataset:
Finding Tutte paths in linear time
Venue: arXiv cs.DS 2019
Year: 2019

It is well-known that every planar graph has a Tutte path, i.e., a path $P$ such that any component of $G-P$ has at most three attachment points on $P$. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of $G-P$ have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to $P$. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.
Computing Nearby Non-trivial Smith Forms
Venue: arXiv cs.SC 2019
Year: 2019

We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal Form. We show that computing the Smith form of a matrix polynomial is amenable to numeric computation as an optimization problem. Furthermore, we describe an effective optimization technique to find a nearby matrix polynomial with a non-trivial Smith form. The results are then generalized to include the computation of a matrix polynomial having a maximum specified number of ones in the Smith Form (i.e., with a maximum specified McCoy rank). We discuss the geometry and existence of solutions and how our results can be used for an error analysis. We develop an optimization-based approach and demonstrate an iterative numerical method for computing a nearby matrix polynomial with the desired spectral properties. We also describe an implementation of our algorithms and demonstrate the robustness with examples in Maple.
Rotation Invariant Descriptors for Galaxy Morphological Classification
Venue: arXiv cs.CV 2019
Year: 2019

The detection of objects that are multi-oriented is a difficult pattern recognition problem. In this paper, we propose to evaluate the performance of different families of descriptors for the classification of galaxy morphologies. We investigate the performance of the Hu moments, Flusser moments, Zernike moments, Fourier-Mellin moments, and ring projection techniques based on 1D moment and the Fourier transform. We consider two main datasets for the performance evaluation. The first dataset is an artificial dataset based on representative templates from 11 types of galaxies, which are evaluated with different transformations (noise, smoothing), alone or combined. The evaluation is based on image retrieval performance to estimate the robustness of the rotation invariant descriptors with this type of images. The second dataset is composed of real images extracted from the Galaxy Zoo 2 project. The binary classification of elliptical and spiral galaxies is achieved with pre-processing steps including morphological filtering and a Laplacian pyramid. For the binary classification, we compare the different set of features with Support Vector Machines (SVM), Extreme Learning Machine, and different types of linear discriminant analysis techniques. The results support the conclusion that the proposed framework for the binary classification of elliptical and spiral galaxies provides an area under the ROC curve reaching 99.54%, proving the robustness of the approach for helping astronomers to study galaxies.
Efficient Super Resolution For Large-Scale Images Using Attentional GAN
Venue: arXiv cs.CV 2019
Year: 2019

Single Image Super Resolution (SISR) is a well-researched problem with broad commercial relevance. However, most of the SISR literature focuses on small-size images under 500px, whereas business needs can mandate the generation of very high resolution images. At Expedia Group, we were tasked with generating images of at least 2000px for display on the website, four times greater than the sizes typically reported in the literature. This requirement poses a challenge that state-of-the-art models, validated on small images, have not been proven to handle. In this paper, we investigate solutions to the problem of generating high-quality images for large-scale super resolution in a commercial setting. We find that training a generative adversarial network (GAN) with attention from scratch using a large-scale lodging image data set generates images with high PSNR and SSIM scores. We describe a novel attentional SISR model for large-scale images, A-SRGAN, that uses a Flexible Self Attention layer to enable processing of large-scale images. We also describe a distributed algorithm which speeds up training by around a factor of five.
A Multimodal LSTM for Predicting Listener Empathic Responses Over Time
Venue: arXiv cs.CL 2019
Year: 2019

People naturally understand the emotions of-and often also empathize with-those around them. In this paper, we predict the emotional valence of an empathic listener over time as they listen to a speaker narrating a life story. We use the dataset provided by the OMG-Empathy Prediction Challenge, a workshop held in conjunction with IEEE FG 2019. We present a multimodal LSTM model with feature-level fusion and local attention that predicts empathic responses from audio, text, and visual features. Our best-performing model, which used only the audio and text features, achieved a concordance correlation coefficient (CCC) of 0.29 and 0.32 on the Validation set for the Generalized and Personalized track respectively, and achieved a CCC of 0.14 and 0.14 on the held-out Test set. We discuss the difficulties faced and the lessons learnt tackling this challenge.
An Empirical Study of Example Forgetting during Deep Neural Network Learning
Venue: arXiv cs.LG 2019
Year: 2019

Inspired by the phenomenon of catastrophic forgetting, we investigate the learning dynamics of neural networks as they train on single classification tasks. Our goal is to understand whether a related phenomenon occurs when data does not undergo a clear distributional shift. We define a `forgetting event' to have occurred when an individual training example transitions from being classified correctly to incorrectly over the course of learning. Across several benchmark data sets, we find that: (i) certain examples are forgotten with high frequency, and some not at all; (ii) a data set's (un)forgettable examples generalize across neural architectures; and (iii) based on forgetting dynamics, a significant fraction of examples can be omitted from the training data set while still maintaining state-of-the-art generalization performance.
Dynamic Network Prediction
Venue: arXiv cs.SI 2019
Year: 2019

We present a statistical framework for generating predicted dynamic networks based on the observed evolution of social relationships in a population. The framework includes a novel and flexible procedure to sample dynamic networks given a probability distribution on evolving network properties; it permits the use of a broad class of approaches to model trends, seasonal variability, uncertainty, and changes in population composition. Current methods do not account for the variability in the observed historical networks when predicting the network structure; the proposed method provides a principled approach to incorporate uncertainty in prediction. This advance aids in the designing of network-based interventions, as development of such interventions often requires prediction of the network structure in the presence and absence of the intervention. Two simulation studies are conducted to demonstrate the usefulness of generating predicted networks when designing network-based interventions. The framework is also illustrated by investigating results of potential interventions on bill passage rates using a dynamic network that represents the sponsor/co-sponsor relationships among senators derived from bills introduced in the US Senate from 2003-2016.
On Privacy Notions in Anonymous Communication
Venue: arXiv cs.CR 2019
Year: 2019

Many anonymous communication networks (ACNs) with different privacy goals have been developed. However, there are no accepted formal definitions of privacy and ACNs often define their goals and adversary models ad hoc. However, for the understanding and comparison of different flavors of privacy, a common foundation is needed. In this paper, we introduce an analysis framework for ACNs that captures the notions and assumptions known from different analysis frameworks. Therefore, we formalize privacy goals as notions and identify their building blocks. For any pair of notions we prove whether one is strictly stronger, and, if so, which. Hence, we are able to present a complete hierarchy. Further, we show how to add practical assumptions, e.g. regarding the protocol model or user corruption as options to our notions. This way, we capture the notions and assumptions of, to the best of our knowledge, all existing analytical frameworks for ACNs and are able to revise inconsistencies between them. Thus, our new framework builds a common ground and allows for sharper analysis, since new combinations of assumptions are possible and the relations between the notions are known.
When to Preempt? Age of Information Minimization under Link Capacity Constraint
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider a scenario where a source continuously monitors an object and sends time-stamped status updates to a destination through a rate-limited link. We assume updates arrive randomly at the source according to a Bernoulli process. Due to the link capacity constraint, it takes multiple time slots for the source to complete the transmission of an update. Therefore, when a new update arrives at the source during the transmission of another update, the source needs to decide whether to skip the new arrival or to switch to it, in order to minimize the expected average age of information (AoI) at the destination. We start with the setting where all updates are of the same size, and prove that within a broadly defined class of online policies, the optimal policy should be a renewal policy, and has a sequential switching property. We then show that the optimal decision of the source in any time slot has threshold structures, and only depends on the age of the update being transmitted and the AoI at the destination. We then consider the setting where updates are of different sizes, and show that the optimal Markovian policy also has a multiple-threshold structure. For each of the settings, we explicitly identify the thresholds by formulating the problem as a Markov Decision Process (MDP), and solve it through value iteration. Special structural properties of the corresponding optimal policy are utilized to reduce the computational complexity of the value iteration algorithm.
Which criteria qualify power indices for applications? -- A comment to "The story of the poor Public Good index"
Venue: arXiv cs.GT 2019
Year: 2019

We discuss possible criteria that may qualify or disqualify power indices for applications. Instead of providing final answers we merely ask questions that are relevant from our point of view and summarize some material from the literature.
Evolutionary Neural Architecture Search for Image Restoration
Venue: arXiv cs.NE 2019
Year: 2019

Convolutional neural network (CNN) architectures have traditionally been explored by human experts in a manual search process that is time-consuming and ineffectively explores the massive space of potential solutions. Neural architecture search (NAS) methods automatically search the space of neural network hyperparameters in order to find optimal task-specific architectures. NAS methods have discovered CNN architectures that achieve state-of-the-art performance in image classification among other tasks, however the application of NAS to image-to-image regression problems such as image restoration is sparse. This paper proposes a NAS method that performs computationally efficient evolutionary search of a minimally constrained network architecture search space. The performance of architectures discovered by the proposed method is evaluated on a variety of image restoration tasks applied to the ImageNet64x64 dataset, and compared with human-engineered CNN architectures. The best neural architectures discovered using only 2 GPU-hours of evolutionary search exhibit comparable performance to the human-engineered baseline architecture.
Aggregate Power Flexibility in Unbalanced Distribution Systems
Venue: arXiv cs.SY 2019
Year: 2019

With a large-scale integration of distributed energy resources (DERs), distribution systems are expected to be capable of providing capacity support for the transmission grid. To effectively harness the collective flexibility from massive DER devices, this paper studies distribution-level power aggregation strategies for transmission-distribution interaction. In particular, this paper proposes a method to model and quantify the aggregate power flexibility, i.e., the net power injection achievable at the substation, in unbalanced distribution systems over time. Incorporating the network constraints and multi-phase unbalanced modeling, the proposed method obtains an effective approximate feasible region of the net power injection. For any aggregate power trajectory within this region, it is proved that there exists a feasible disaggregation solution. In addition, a distributed model predictive control (MPC) framework is developed for the practical implementation of the transmission-distribution interaction. At last, we demonstrate the performances of the proposed method via numerical tests on a real-world distribution feeder with 126 multi-phase nodes.
Action Quality Assessment Across Multiple Actions
Venue: arXiv cs.CV 2019
Year: 2019

Can learning to measure the quality of an action help in measuring the quality of other actions? If so, can consolidated samples from multiple actions help improve the performance of current approaches? In this paper, we carry out experiments to see if knowledge transfer is possible in the action quality assessment (AQA) setting. Experiments are carried out on our newly released AQA dataset (http://rtis.oit.unlv.edu/datasets.html) consisting of 1106 action samples from seven actions with quality scores as measured by expert human judges. Our experimental results show that there is utility in learning a single model across multiple actions.
Provable limitations of deep learning
Venue: arXiv cs.LG 2019
Year: 2019

As the success of deep learning reaches more grounds, one would like to also envision the potential limits of deep learning. This paper gives a first set of results proving that certain deep learning algorithms fail at learning certain efficiently learnable functions. The results put forward a notion of cross-predictability that characterizes when such failures take place. Parity functions provide an extreme example with a cross-predictability that decays exponentially, while a mere super-polynomial decay of the cross-predictability is shown to be sufficient to obtain failures. Examples in community detection and arithmetic learning are also discussed. Recall that it is known that the class of neural networks (NNs) with polynomial network size can express any function that can be implemented in polynomial time, and that their sample complexity scales polynomially with the network size. The challenge is with the optimization error (the ERM is NP-hard), and the success behind deep learning is to train deep NNs with descent algorithms. The failures shown in this paper apply to training poly-size NNs on function distributions of low cross-predictability with a descent algorithm that is either run with limited memory per sample or that is initialized and run with enough randomness. We further claim that such types of constraints are necessary to obtain failures, in that exact SGD with careful non-random initialization can be shown to learn parities. The cross-predictability in our results plays a similar role the statistical dimension in statistical query (SQ) algorithms, with distinctions explained in the paper. The proof techniques are based on exhibiting algorithmic constraints that imply a statistical indistinguishability between the algorithm's output on the test model v.s.\ a null model, using information measures to bound the total variation distance.
HoVer-Net: Simultaneous Segmentation and Classification of Nuclei in Multi-Tissue Histology Images
Venue: arXiv cs.CV 2019
Year: 2019

Nuclear segmentation and classification within Haematoxylin & Eosin stained histology images is a fundamental prerequisite in the digital pathology work-flow. The development of automated methods for nuclear segmentation and classification enables the quantitative analysis of tens of thousands of nuclei within a whole-slide pathology image, opening up possibilities of further analysis of large-scale nuclear morphometry. However, automated nuclear segmentation and classification is faced with a major challenge in that there are several different types of nuclei, some of them exhibiting large intra-class variability such as the tumour cells. Additionally, some of the nuclei are often clustered together. To address these challenges, we present a novel convolutional neural network for simultaneous nuclear segmentation and classification that leverages the instance-rich information encoded within the vertical and horizontal distances of nuclear pixels to their centres of mass. These distances are then utilised to separate clustered nuclei, resulting in an accurate segmentation, particularly in areas with overlapping instances. Then for each segmented instance, the network predicts the type of nucleus via a devoted up-sampling branch. We demonstrate state-of-the-art performance compared to other methods on multiple independent multi-tissue histology image datasets. As part of this work, we introduce a new dataset of Haematoxylin & Eosin stained colorectal adenocarcinoma image tiles, containing 24,319 exhaustively annotated nuclei with associated class labels.
Community structure: A comparative evaluation of community detection methods
Venue: arXiv cs.SI 2019
Year: 2019

Discovering community structure in complex networks is a mature field since a tremendous number of community detection methods have been introduced in the literature. Nevertheless, it is still very challenging for practioners to determine which method would be suitable to get insights into the structural information of the networks they study. Many recent efforts have been devoted to investigating various quality scores of the community structure, but the problem of distinguishing between different types of communities is still open. In this paper, we propose a comparative, extensive and empirical study to investigate what types of communities many state-of-the-art and well-known community detection methods are producing. Specifically, we provide comprehensive analyses on computation time, community size distribution, a comparative evaluation of methods according to their optimisation schemes as well as a comparison of their partioning strategy through validation metrics. We process our analyses on a very large corpus of hundreds of networks from five different network categories and propose ways to classify community detection methods, helping a potential user to navigate the complex landscape of community detection.
Learning to Generate Music with BachProp
Venue: arXiv cs.SD 2019
Year: 2019

As deep learning advances, algorithms of music composition increase in performance. However, most of the successful models are designed for specific musical structures. Here, we present BachProp, an algorithmic composer that can generate music scores in many styles given sufficient training data. To adapt BachProp to a broad range of musical styles, we propose a novel representation of music and train a deep network to predict the note transition probabilities of a given music corpus. In this paper, new music scores generated by BachProp are compared with the original corpora as well as with different network architectures and other related models. We show that BachProp captures important features of the original datasets better than other models and invite the reader to a qualitative comparison on a large collection of generated songs.
Research in Visible Light Communication Systems with OpenVLC1.3
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we present the design and implementation of our latest OpenVLC1.3 platform to perform research in Visible Light Communication Systems. We retain the advantages of the previous versions such as TCP/IP layers support, software programmability and low-cost front-end. We re-design the transceiver to support higher modulation rates and sensitivity. This allows us to reach a throughput of 400 kb/s (a factor of 4 with respect to the previous version) and increase the distance by a factor of 3.5. We further improve the software robustness of the system and reduce the form factor at similar hardware cost.
Recursively Feasible Stochastic Model Predictive Control using Indirect Feedback
Venue: arXiv cs.SY 2019
Year: 2019

We present a stochastic model predictive control (MPC) method for linear discrete-time systems subject to possibly unbounded and correlated additive stochastic disturbance sequences. Chance constraints are treated in analogy to robust MPC using the concept of probabilistic reachable sets for constraint tightening. We introduce an initialization of each MPC iteration which is always recursively feasibility and thereby allows that chance constraint satisfaction for the closed-loop system can readily be shown. Under an i.i.d. zero mean assumption on the additive disturbance, we furthermore provide an average asymptotic performance bound. Two examples illustrate the approach, highlighting feedback properties of the novel initialization scheme, as well as the inclusion of time-varying, correlated disturbances in a building control setting.
Instrument-Independent Dastgah Recognition of Iranian Classical Music Using AzarNet
Venue: arXiv cs.SD 2019
Year: 2019

In this paper, AzarNet, a deep neural network (DNN), is proposed to recognizing seven different Dastgahs of Iranian classical music in Maryam Iranian classical music (MICM) dataset. Over the last years, there has been remarkable interest in employing feature learning and DNNs which lead to decreasing the required engineering effort. DNNs have shown better performance in many classification tasks such as audio signal classification compares to shallow processing architectures. Despite image data, audio data need some preprocessing steps to extract spectra and temporal features. Some transformations like Short-Time Fourier Transform (STFT) have been used in the state of art researches to transform audio signals from time-domain to time-frequency domain to extract both temporal and spectra features. In this research, the STFT output results which are extracted features are given to AzarNet for learning and classification processes. It is worth noting that, the mentioned dataset contains music tracks composed with two instruments (violin and straw). The overall f1 score of AzarNet on test set, for average of all seven classes was 86.21% which is the best result ever reported in Dastgah classification according to our best knowledge.