OpenRaiser/Intern-Atlas huggingface dataset:
Itemsets for Real-valued Datasets
Venue: arXiv cs.DS 2019
Year: 2019

Pattern mining is one of the most well-studied subfields in exploratory data analysis. While there is a significant amount of literature on how to discover and rank itemsets efficiently from binary data, there is surprisingly little research done in mining patterns from real-valued data. In this paper we propose a family of quality scores for real-valued itemsets. We approach the problem by considering casting the dataset into a binary data and computing the support from this data. This naive approach requires us to select thresholds. To remedy this, instead of selecting one set of thresholds, we treat thresholds as random variables and compute the average support. We show that we can compute this support efficiently, and we also introduce two normalisations, namely comparing the support against the independence assumption and, more generally, against the partition assumption. Our experimental evaluation demonstrates that we can discover statistically significant patterns efficiently.
Planar digraphs for automatic complexity
Venue: arXiv cs.FL 2019
Year: 2019

We show that the digraph of a nondeterministic finite automaton witnessing the automatic complexity of a word can always be taken to be planar. In the case of total transition functions studied by Shallit and Wang, planarity can fail. Let $s_q(n)$ be the number of binary words $x$ of length $n$ having nondeterministic automatic complexity $A_N(x)=q$. We show that $s_q$ is eventually constant for each $q$ and that the eventual constant value of $s_q$ is computable.
Joint User Selection, Power Allocation, and Precoding Design with Imperfect CSIT for Multi-Cell MU-MIMO Downlink Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, a new optimization framework is presented for the joint design of user selection, power allocation, and precoding in multi-cell multi-user multiple-input multiple-output (MU-MIMO) systems when imperfect channel state information at transmitter (CSIT) is available. By representing the joint optimization variables in a higher-dimensional space, the weighted sum-spectral efficiency maximization is formulated as the maximization of the product of Rayleigh quotients. Although this is still a non-convex problem, a computationally efficient algorithm, referred to as generalized power iteration precoding (GPIP), is proposed. The algorithm converges to a stationary point (local maximum) of the objective function and therefore it guarantees the first-order optimality of the solution. By adjusting the weights in the weighted sum-spectral efficiency, the GPIP yields a joint solution for user selection, power allocation, and downlink precoding. The GPIP is also extended to a multi-cell scenario, where cooperative base stations perform joint user selection and design their precoding vectors by sharing global yet imperfect CSIT within the cooperative BSs. System-level simulations show the gains of the proposed approach with respect to conventional user selection and linear downlink precoding.
Real-Time Freespace Segmentation on Autonomous Robots for Detection of Obstacles and Drop-Offs
Venue: arXiv cs.CV 2019
Year: 2019

Mobile robots navigating in indoor and outdoor environments must be able to identify and avoid unsafe terrain. Although a significant amount of work has been done on the detection of standing obstacles (solid obstructions), not much work has been done on the detection of negative obstacles (e.g. dropoffs, ledges, downward stairs). We propose a method of terrain safety segmentation using deep convolutional networks. Our custom semantic segmentation architecture uses a single camera as input and creates a freespace map distinguishing safe terrain and obstacles. We then show how this freespace map can be used for real-time navigation on an indoor robot. The results show that our system generalizes well, is suitable for real-time operation, and runs at around 55 fps on a small indoor robot powered by a low-power embedded GPU.
New Constellation Design and Bit Mapping for Dual Mode OFDM-IM
Venue: arXiv cs.IT 2019
Year: 2019

Dual mode orthogonal frequency division multiplexing with index modulation (DM-OFDM-IM) is recently proposed, which modulates all subcarriers to eliminate the limits of spectrum efficiency in OFDM with index modulation (OFDM-IM). In DM-OFDM-IM, the subcarriers within each subblock are divided into two groups, which are modulated by two distinguishable constellation alphabets drawn from the distinct two constellations. In this paper, a new constellation design for DM-OFDM-IM is proposed based on the pairwise error probability (PEP) analysis. In previous works, the design of the constellation pair is naive and induces much power. Also, a new bit mapping scheme for DM-OFDM-IM is proposed. The proposed bit mapping scheme can relieve the catastrophic effect of the index demodulation error incurring burst of errors, which is the endemic problem of the index demodulation systems. The simulation results show that the proposed constellation pair and the proposed bit mapping scheme substantially enhance the BER performance of the DM-OFDM-IM than the conventional DM-OFDM-IM.
Deep Autotuner: A Data-Driven Approach to Natural-Sounding Pitch Correction for Singing Voice in Karaoke Performances
Venue: arXiv cs.SD 2019
Year: 2019

We describe a machine-learning approach to pitch correcting a solo singing performance in a karaoke setting, where the solo voice and accompaniment are on separate tracks. The proposed approach addresses the situation where no musical score of the vocals nor the accompaniment exists: It predicts the amount of correction from the relationship between the spectral contents of the vocal and accompaniment tracks. Hence, the pitch shift in cents suggested by the model can be used to make the voice sound in tune with the accompaniment. This approach differs from commercially used automatic pitch correction systems, where notes in the vocal tracks are shifted to be centered around notes in a user-defined score or mapped to the closest pitch among the twelve equal-tempered scale degrees. We train the model using a dataset of 4,702 amateur karaoke performances selected for good intonation. We present a Convolutional Gated Recurrent Unit (CGRU) model to accomplish this task. This method can be extended into unsupervised pitch correction of a vocal performance, popularly referred to as autotuning.
Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
Venue: arXiv cs.LG 2019
Year: 2019

In experimental design, we are given a large collection of vectors, each with a hidden response value that we assume derives from an underlying linear model, and we wish to pick a small subset of the vectors such that querying the corresponding responses will lead to a good estimator of the model. A classical approach in statistics is to assume the responses are linear, plus zero-mean i.i.d. Gaussian noise, in which case the goal is to provide an unbiased estimator with smallest mean squared error (A-optimal design). A related approach, more common in computer science, is to assume the responses are arbitrary but fixed, in which case the goal is to estimate the least squares solution using few responses, as quickly as possible, for worst-case inputs. Despite many attempts, characterizing the relationship between these two approaches has proven elusive. We address this by proposing a framework for experimental design where the responses are produced by an arbitrary unknown distribution. We show that there is an efficient randomized experimental design procedure that achieves strong variance bounds for an unbiased estimator using few responses in this general model. Nearly tight bounds for the classical A-optimality criterion, as well as improved bounds for worst-case responses, emerge as special cases of this result. In the process, we develop a new algorithm for a joint sampling distribution called volume sampling, and we propose a new i.i.d. importance sampling method: inverse score sampling. A key novelty of our analysis is in developing new expected error bounds for worst-case regression by controlling the tail behavior of i.i.d. sampling via the jointness of volume sampling. Our result motivates a new minimax-optimality criterion for experimental design which can be viewed as an extension of both A-optimal design and sampling for worst-case regression.
BottleNet: A Deep Learning Architecture for Intelligent Mobile Cloud Computing Services
Venue: arXiv cs.DC 2019
Year: 2019

Recent studies have shown the latency and energy consumption of deep neural networks can be significantly improved by splitting the network between the mobile device and cloud. This paper introduces a new deep learning architecture, called BottleNet, for reducing the feature size needed to be sent to the cloud. Furthermore, we propose a training method for compensating for the potential accuracy loss due to the lossy compression of features before transmitting them to the cloud. BottleNet achieves on average 30x improvement in end-to-end latency and 40x improvement in mobile energy consumption compared to the cloud-only approach with negligible accuracy loss.
Deep-Emotion: Facial Expression Recognition Using Attentional Convolutional Network
Venue: arXiv cs.CV 2019
Year: 2019

Facial expression recognition has been an active research area over the past few decades, and it is still challenging due to the high intra-class variation. Traditional approaches for this problem rely on hand-crafted features such as SIFT, HOG and LBP, followed by a classifier trained on a database of images or videos. Most of these works perform reasonably well on datasets of images captured in a controlled condition, but fail to perform as good on more challenging datasets with more image variation and partial faces. In recent years, several works proposed an end-to-end framework for facial expression recognition, using deep learning models. Despite the better performance of these works, there still seems to be a great room for improvement. In this work, we propose a deep learning approach based on attentional convolutional network, which is able to focus on important parts of the face, and achieves significant improvement over previous models on multiple datasets, including FER-2013, CK+, FERG, and JAFFE. We also use a visualization technique which is able to find important face regions for detecting different emotions, based on the classifier's output. Through experimental results, we show that different emotions seems to be sensitive to different parts of the face.
Cooperative Driving at Unsignalized Intersections Using Tree Search
Venue: arXiv cs.MA 2019
Year: 2019

In this paper, we propose a new cooperative driving strategy for connected and automated vehicles (CAVs) at unsignalized intersections. Based on the tree representation of the solution space for the passing order, we combine Monte Carlo tree search (MCTS) and some heuristic rules to find a nearly global-optimal passing order (leaf node) within a very short planning time. Testing results show that this new strategy can keep a good tradeoff between performance and computation flexibility.
Estimation with Fast Landmark Selection in Robot Visual Navigation
Venue: arXiv cs.RO 2019
Year: 2019

We consider the visual feature selection to improve the estimation quality required for the accurate navigation of a robot. We build upon a key property that asserts: contributions of trackable features (landmarks) appear linearly in the information matrix of the corresponding estimation problem. We utilize standard models for motion and vision system using a camera to formulate the feature selection problem over moving finite time horizons. A scalable randomized sampling algorithm is proposed to select more informative features (and ignore the rest) to achieve a superior position estimation quality. We provide probabilistic performance guarantees for our method. The time-complexity of our feature selection algorithm is linear in the number of candidate features, which is practically plausible and outperforms existing greedy methods that scale quadratically with the number of candidates features. Our numerical simulations confirm that not only the execution time of our proposed method is comparably less than that of the greedy method, but also the resulting estimation quality is very close to the greedy method.
A Novel JT-CoMP Scheme in 5G Fractal Small Cell Networks
Venue: arXiv cs.NI 2019
Year: 2019

To satisfy the requirement of the fifth generation (5G) mobile communications that offers an ultra high data rate of 100Mbps to 1Gbps anytime and anywhere, the coordinated multipoint (CoMP) technique is proposed to mitigate inter-cell interference to improve the coverage of high data rate services, cell-edge throughput, and system capacity. However, the joint transmission (JT) CoMP technique is difficult to be applied in practice due to the critical time synchronization for multiple coordination links and the bottleneck of backhaul capacity and radio resource at each small cell base stations (SBSs). Moreover, since the coordination SBSs in the conditional scheme are entirely separate from each other, different time of arrivals at the user cause the severe time synchronization problem. The anisotropic propagation environment in the urban scenario makes the implementation condition even worse. To tackle these issues, we propose a novel JT-CoMP scheme with the anisotropic path loss model to minimize the network backhaul traffic subject to the constraints on the radio resource and the differences in time of arrivals. Simulation results demonstrate that the proposed distance-resource-limited CoMP scheme can obtain the maximum achievable rate with the minimum network backhaul traffic, compared with existing schemes.
Compatible and Diverse Fashion Image Inpainting
Venue: arXiv cs.CV 2019
Year: 2019

Visual compatibility is critical for fashion analysis, yet is missing in existing fashion image synthesis systems. In this paper, we propose to explicitly model visual compatibility through fashion image inpainting. To this end, we present Fashion Inpainting Networks (FiNet), a two-stage image-to-image generation framework that is able to perform compatible and diverse inpainting. Disentangling the generation of shape and appearance to ensure photorealistic results, our framework consists of a shape generation network and an appearance generation network. More importantly, for each generation network, we introduce two encoders interacting with one another to learn latent code in a shared compatibility space. The latent representations are jointly optimized with the corresponding generation network to condition the synthesis process, encouraging a diverse set of generated results that are visually compatible with existing fashion garments. In addition, our framework is readily extended to clothing reconstruction and fashion transfer, with impressive results. Extensive experiments with comparisons with state-of-the-art approaches on fashion synthesis task quantitatively and qualitatively demonstrate the effectiveness of our method.
Exploring Temporal Dependencies in Multimodal Referring Expressions with Mixed Reality
Venue: arXiv cs.HC 2019
Year: 2019

In collaborative tasks, people rely both on verbal and non-verbal cues simultaneously to communicate with each other. For human-robot interaction to run smoothly and naturally, a robot should be equipped with the ability to robustly disambiguate referring expressions. In this work, we propose a model that can disambiguate multimodal fetching requests using modalities such as head movements, hand gestures, and speech. We analysed the acquired data from mixed reality experiments and formulated a hypothesis that modelling temporal dependencies of events in these three modalities increases the model's predictive power. We evaluated our model on a Bayesian framework to interpret referring expressions with and without exploiting a temporal prior.
On the Enactability of Agent Interaction Protocols: Toward a Unified Approach
Venue: arXiv cs.MA 2019
Year: 2019

Interactions between agents are usually designed from a global viewpoint. However, the implementation of a multi-agent interaction is distributed. This difference can introduce issues. For instance, it is possible to specify protocols from a global viewpoint that cannot be implemented as a collection of individual agents. This leads naturally to the question of whether a given (global) protocol is enactable. We consider this question in a powerful setting (trace expression), considering a range of message ordering interpretations (what does it mean to say that an interaction step occurs before another), and a range of possible constraints on the semantics of message delivery, corresponding to different properties of underlying communication middleware.
Stabilization Time in Weighted Minority Processes
Venue: arXiv cs.DM 2019
Year: 2019

A minority process in a weighted graph is a dynamically changing coloring. Each node repeatedly changes its color in order to minimize the sum of weighted conflicts with its neighbors. We study the number of steps until such a process stabilizes. Our main contribution is an exponential lower bound on stabilization time. We first present a construction showing this bound in the adversarial sequential model, and then we show how to extend the construction to establish the same bound in the benevolent sequential model, as well as in any reasonable concurrent model. Furthermore, we show that the stabilization time of our construction remains exponential even for very strict switching conditions, namely, if a node only changes color when almost all (i.e., any specific fraction) of its neighbors have the same color. Our lower bound works in a wide range of settings, both for node-weighted and edge-weighted graphs, or if we restrict minority processes to the class of sparse graphs.
Robustness Certificates Against Adversarial Examples for ReLU Networks
Venue: arXiv cs.LG 2019
Year: 2019

While neural networks have achieved high performance in different learning tasks, their accuracy drops significantly in the presence of small adversarial perturbations to inputs. Defenses based on regularization and adversarial training are often followed by new attacks to defeat them. In this paper, we propose attack-agnostic robustness certificates for a multi-label classification problem using a deep ReLU network. Although computing the exact distance of a given input sample to the classification decision boundary requires solving a non-convex optimization, we characterize two lower bounds for such distances, namely the simplex certificate and the decision boundary certificate. These robustness certificates leverage the piece-wise linear structure of ReLU networks and use the fact that in a polyhedron around a given sample, the prediction function is linear. In particular, the proposed simplex certificate has a closed-form, is differentiable and is an order of magnitude faster to compute than the existing methods even for deep networks. In addition to theoretical bounds, we provide numerical results for our certificates over MNIST and compare them with some existing upper bounds.
PIPPS: Flexible Model-Based Policy Search Robust to the Curse of Chaos
Venue: arXiv cs.LG 2019
Year: 2019

Previously, the exploding gradient problem has been explained to be central in deep learning and model-based reinforcement learning, because it causes numerical issues and instability in optimization. Our experiments in model-based reinforcement learning imply that the problem is not just a numerical issue, but it may be caused by a fundamental chaos-like nature of long chains of nonlinear computations. Not only do the magnitudes of the gradients become large, the direction of the gradients becomes essentially random. We show that reparameterization gradients suffer from the problem, while likelihood ratio gradients are robust. Using our insights, we develop a model-based policy search framework, Probabilistic Inference for Particle-Based Policy Search (PIPPS), which is easily extensible, and allows for almost arbitrary models and policies, while simultaneously matching the performance of previous data-efficient learning algorithms. Finally, we invent the total propagation algorithm, which efficiently computes a union over all pathwise derivative depths during a single backwards pass, automatically giving greater weight to estimators with lower variance, sometimes improving over reparameterization gradients by $10^6$ times.
Semidefinite programming bounds for error-correcting codes
Venue: arXiv cs.IT 2019
Year: 2019

This chapter is written for the forthcoming book "A Concise Encyclopedia of Coding Theory" (CRC press), edited by W. Cary Huffman, Jon-Lark Kim, and Patrick Solé. This book will collect short but foundational articles, emphasizing definitions, examples, exhaustive references, and basic facts on the model of the Handbook of Finite Fields. The target audience of the Encyclopedia is upper level undergraduates and graduate students.
A Framework for Allocating Server Time to Spot and On-demand Services in Cloud Computing
Venue: arXiv cs.PF 2019
Year: 2019

Cloud computing delivers value to users by facilitating their access to computing capacity in periods when their need arises. An approach is to provide both on-demand and spot services on shared servers. The former allows users to access servers on demand at a fixed price and users occupy different periods of servers. The latter allows users to bid for the remaining unoccupied periods via dynamic pricing; however, without appropriate design, such periods may be arbitrarily small since on-demand users arrive randomly. This is also the current service model adopted by Amazon Elastic Cloud Compute. In this paper, we provide the first integral framework for sharing the time of servers between on-demand and spot services while optimally pricing spot instances. It guarantees that on-demand users can get served quickly while spot users can stably utilize servers for a properly long period once accepted, which is a key feature to make both on-demand and spot services accessible. Simulation results show that, by complementing the on-demand market with a spot market, a cloud provider can improve revenue by up to 464.7%. The framework is designed under assumptions which are met in real environments. It is a new tool that cloud operators can use to quantify the advantage of a hybrid spot and on-demand service, eventually making the case for operating such service model in their own infrastructures.
Robust Hidden Topology Identification in Distribution Systems
Venue: arXiv cs.SY 2019
Year: 2019

With more distributed energy resources (DERs) connected to distribution grids, better monitoring and control are needed, where identifying the topology accurately is the prerequisite. However, due to frequent re-configurations, operators usually cannot know a complete structure in distribution grids. Luckily, the growing data from smart sensors, restricted by Ohm law, provides the possibility of topology inference. In this paper, we show how line parameters of Ohm equation can be estimated for topology identification even when there are hidden nodes. Specifically, the introduced learning method recursively conducts hidden-node detection and impedance calculation. However, the assumptions on uncorrelated data, availability of phasor measurements, and a balanced system, are not met in practices, causing large errors. To resolve these problems, we employ Cholesky whitening first with a proof for measurement decorrelations. For increasing robustness further, we show how to handle practical scenarios when only measurement magnitudes are available or when the grid is three-phase unbalanced. Numerical performance is verified on multi-size distribution grids with both simulation and real-world data.