OpenRaiser/Intern-Atlas huggingface dataset:
Boolean matrix factorization meets consecutive ones property
Venue: arXiv cs.DS 2019
Year: 2019

Boolean matrix factorization is a natural and a popular technique for summarizing binary matrices. In this paper, we study a problem of Boolean matrix factorization where we additionally require that the factor matrices have consecutive ones property (OBMF). A major application of this optimization problem comes from graph visualization: standard techniques for visualizing graphs are circular or linear layout, where nodes are ordered in circle or on a line. A common problem with visualizing graphs is clutter due to too many edges. The standard approach to deal with this is to bundle edges together and represent them as ribbon. We also show that we can use OBMF for edge bundling combined with circular or linear layout techniques. We demonstrate that not only this problem is NP-hard but we cannot have a polynomial-time algorithm that yields a multiplicative approximation guarantee (unless P = NP). On the positive side, we develop a greedy algorithm where at each step we look for the best 1-rank factorization. Since even obtaining 1-rank factorization is NP-hard, we propose an iterative algorithm where we fix one side and and find the other, reverse the roles, and repeat. We show that this step can be done in linear time using pq-trees. We also extend the problem to cyclic ones property and symmetric factorizations. Our experiments show that our algorithms find high-quality factorizations and scale well.
Inferring Streaming Video Quality from Encrypted Traffic: Practical Models and Deployment Experience
Venue: arXiv cs.NI 2019
Year: 2019

Inferring the quality of streaming video applications is important for Internet service providers, but the fact that most video streams are encrypted makes it difficult to do so. We develop models that infer quality metrics (\ie, startup delay and resolution) for encrypted streaming video services. Our paper builds on previous work, but extends it in several ways. First, the model works in deployment settings where the video sessions and segments must be identified from a mix of traffic and the time precision of the collected traffic statistics is more coarse (\eg, due to aggregation). Second, we develop a single composite model that works for a range of different services (i.e., Netflix, YouTube, Amazon, and Twitch), as opposed to just a single service. Third, unlike many previous models, the model performs predictions at finer granularity (\eg, the precise startup delay instead of just detecting short versus long delays) allowing to draw better conclusions on the ongoing streaming quality. Fourth, we demonstrate the model is practical through a 16-month deployment in 66 homes and provide new insights about the relationships between Internet "speed" and the quality of the corresponding video streams, for a variety of services; we find that higher speeds provide only minimal improvements to startup delay and resolution.
Resource Allocation for Multi-User Downlink URLLC-OFDMA Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study resource allocation for downlink orthogonal frequency division multiple access (OFDMA) systems with the objective to enable ultra-reliable low latency communication (URLLC). To meet the stringent delay requirements of URLLC, the impact of short packet communication is taken into account for resource allocation algorithm design. In particular, the resource allocation design is formulated as a weighted system sum throughput maximization problem with quality-of-service (QoS) constraints for the URLLC users. The formulated problem is non-convex, and hence, finding the global optimum solution entails a high computational complexity. Thus, an algorithm based on successive convex optimization is proposed to find a sub-optimal solution with polynomial time complexity. Simulation results confirm that the proposed algorithm facilities URLLC and significantly improves the system sum throughput compared to two benchmark schemes.
A Multilevel Approach for the Performance Analysis of Parallel Algorithms
Venue: arXiv cs.DC 2019
Year: 2019

We provide a multilevel approach for analysing performances of parallel algorithms. The main outcome of such approach is that the algorithm is described by using a set of operators which are related to each other according to the problem decomposition. Decomposition level determines the granularity of the algorithm. A set of block matrices (decomposition and execution) highlights fundamental characteristics of the algorithm, such as inherent parallelism and sources of overheads.
Age of Information With Prioritized Streams: When to Buffer Preempted Packets?
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider N information streams sharing a common service facility. The streams are supposed to have different priorities based on their sensitivity. A higher priority stream will always preempt the service of a lower priority packet. By leveraging the notion of Stochastic Hybrid Systems (SHS), we investigate the Age of Information (AoI) in the case where each stream has its own waiting room; when preempted by a higher priority stream, the packet is stored in the waiting room for future resume. Interestingly, it will be shown that a "no waiting room" scenario, and consequently discarding preempted packets, is better in terms of average AoI in some cases. The exact cases where this happen are discussed and numerical results that corroborate the theoretical findings and highlight this trade-off are provided.
Lower Bounds for Linear Decision Lists
Venue: arXiv cs.CC 2019
Year: 2019

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This completely answers an open question of Tur{á}n and Vatan [FoCM'97]. We also show that the spectral classes $PL_1, PL_\infty$, and the polynomial threshold function classes $\widehat{PT}_1, PT_1$, are incomparable to linear decision lists.
Denoising of structured random processes
Venue: arXiv cs.IT 2019
Year: 2019

Denoising stationary process $(X_i)_{i \in Z}$ corrupted by additive white Gaussian noise is a classic and fundamental problem in information theory and statistical signal processing. Despite considerable progress in designing efficient denoising algorithms, for general analog sources, theoretically-founded computationally-efficient methods are yet to be found. For instance in denoising $X^n$ corrupted by noise $Z^n$ as $Y^n=X^n+Z^n$, given the full distribution of $X^n$, a minimum mean square error (MMSE) denoiser needs to compute $E[X^n|Y^n]$. However, for general sources, computing $E[X^n|Y^n]$ is computationally very challenging, if not infeasible. In this paper, starting by a Bayesian setup, where the source distribution is fully known, a novel denoising method, namely, quantized maximum a posteriori (Q-MAP) denoiser, is proposed and its asymptotic performance in the high signal to noise ratio regime is analyzed. Both for memoryless sources, and for structured first-order Markov sources, it is shown that, asymptotically, as $σ$ converges to zero, ${1\over σ^2}E[(X_i-\hat{X}^{\rm Q-MAP}_i)^2]$ achieved by Q-MAP denoiser converges to the information dimension of the source. For the studied memoryless sources, this limit is known to be optimal. A key advantage of the Q-MAP denoiser is that, unlike an MMSE denoiser, it highlights the key properties of the source distribution that are to be used in its denoising. This property dramatically reduces the computational complexity of approximating the solution of the Q-MAP denoiser. Additionally, it naturally leads to a learning-based denoiser. Using ImageNet database for training, initial simulation results exploring the performance of such a learning-based denoiser in image denoising are presented.
Machine Learning Techniques for Brand-Influencer Matchmaking on the Instagram Social Network
Venue: arXiv cs.SI 2019
Year: 2019

The social media revolution has changed the way that brands interact with consumers. Instead of spending their advertising budget on interstate billboards, more and more companies are choosing to partner with so-called Internet "influencers" --- individuals who have gained a loyal following on online platforms for the high quality of the content they post. Unfortunately, it's not always easy for small brands to find the right influencer: someone who aligns with their corporate image and has not yet grown in popularity to the point of unaffordability. In this paper we sought to develop a system for brand-influencer matchmaking, harnessing the power and flexibility of modern machine learning techniques. The result is an algorithm that can predict the most fruitful brand-influencer partnerships based on the similarity of the content they post.
Degrees of Freedom Region of the $(M,N_1,N_2)$ MIMO Broadcast Channel with Partial CSIT: An Application of Sum-set Inequalities Based on Aligned Image Sets
Venue: arXiv cs.IT 2019
Year: 2019

The degrees of freedom (DoF) region is characterized for the $2$-user multiple input multiple output (MIMO) broadcast channel (BC), where the transmitter is equipped with $M$ antennas, the two receivers are equipped with $N_1$ and $N_2$ antennas, and the levels of channel state information at the transmitter (CSIT) for the two users are parameterized by $β_1, β_2$, respectively. The achievability of the DoF region was established by Hao, Rassouli and Clerckx, but no proof of optimality was heretofore available. The proof of optimality is provided in this work with the aid of sum-set inequalities based on the aligned image sets (AIS) approach.
FARSA: Fully Automated Roadway Safety Assessment
Venue: arXiv cs.CV 2019
Year: 2019

This paper addresses the task of road safety assessment. An emerging approach for conducting such assessments in the United States is through the US Road Assessment Program (usRAP), which rates roads from highest risk (1 star) to lowest (5 stars). Obtaining these ratings requires manual, fine-grained labeling of roadway features in street-level panoramas, a slow and costly process. We propose to automate this process using a deep convolutional neural network that directly estimates the star rating from a street-level panorama, requiring milliseconds per image at test time. Our network also estimates many other road-level attributes, including curvature, roadside hazards, and the type of median. To support this, we incorporate task-specific attention layers so the network can focus on the panorama regions that are most useful for a particular task. We evaluated our approach on a large dataset of real-world images from two US states. We found that incorporating additional tasks, and using a semi-supervised training approach, significantly reduced overfitting problems, allowed us to optimize more layers of the network, and resulted in higher accuracy.
TuckerMPI: A Parallel C++/MPI Software Package for Large-scale Data Compression via the Tucker Tensor Decomposition
Venue: arXiv cs.MS 2019
Year: 2019

Our goal is compression of massive-scale grid-structured data, such as the multi-terabyte output of a high-fidelity computational simulation. For such data sets, we have developed a new software package called TuckerMPI, a parallel C++/MPI software package for compressing distributed data. The approach is based on treating the data as a tensor, i.e., a multidimensional array, and computing its truncated Tucker decomposition, a higher-order analogue to the truncated singular value decomposition of a matrix. The result is a low-rank approximation of the original tensor-structured data. Compression efficiency is achieved by detecting latent global structure within the data, which we contrast to most compression methods that are focused on local structure. In this work, we describe TuckerMPI, our implementation of the truncated Tucker decomposition, including details of the data distribution and in-memory layouts, the parallel and serial implementations of the key kernels, and analysis of the storage, communication, and computational costs. We test the software on 4.5 terabyte and 6.7 terabyte data sets distributed across 100s of nodes (1000s of MPI processes), achieving compression rates between 100-200,000$\times$ which equates to 99-99.999% compression (depending on the desired accuracy) in substantially less time than it would take to even read the same dataset from a parallel filesystem. Moreover, we show that our method also allows for reconstruction of partial or down-sampled data on a single node, without a parallel computer so long as the reconstructed portion is small enough to fit on a single machine, e.g., in the instance of reconstructing/visualizing a single down-sampled time step or computing summary statistics.
Accelerated Experimental Design for Pairwise Comparisons
Venue: arXiv cs.DS 2019
Year: 2019

Pairwise comparison labels are more informative and less variable than class labels, but generating them poses a challenge: their number grows quadratically in the dataset size. We study a natural experimental design objective, namely, D-optimality, that can be used to identify which $K$ pairwise comparisons to generate. This objective is known to perform well in practice, and is submodular, making the selection approximable via the greedy algorithm. A naïve greedy implementation has $O(N^2d^2K)$ complexity, where $N$ is the dataset size, $d$ is the feature space dimension, and $K$ is the number of generated comparisons. We show that, by exploiting the inherent geometry of the dataset--namely, that it consists of pairwise comparisons--the greedy algorithm's complexity can be reduced to $O(N^2(K+d)+N(dK+d^2) +d^2K).$ We apply the same acceleration also to the so-called lazy greedy algorithm. When combined, the above improvements lead to an execution time of less than 1 hour for a dataset with $10^8$ comparisons; the naïve greedy algorithm on the same dataset would require more than 10 days to terminate.
The ANTAREX Domain Specific Language for High Performance Computing
Venue: arXiv cs.DC 2019
Year: 2019

The ANTAREX project relies on a Domain Specific Language (DSL) based on Aspect Oriented Programming (AOP) concepts to allow applications to enforce extra functional properties such as energy-efficiency and performance and to optimize Quality of Service (QoS) in an adaptive way. The DSL approach allows the definition of energy-efficiency, performance, and adaptivity strategies as well as their enforcement at runtime through application autotuning and resource and power management. In this paper, we present an overview of the key outcome of the project, the ANTAREX DSL, and some of its capabilities through a number of examples, including how the DSL is applied in the context of the project use cases.
TactileGCN: A Graph Convolutional Network for Predicting Grasp Stability with Tactile Sensors
Venue: arXiv cs.LG 2019
Year: 2019

Tactile sensors provide useful contact data during the interaction with an object which can be used to accurately learn to determine the stability of a grasp. Most of the works in the literature represented tactile readings as plain feature vectors or matrix-like tactile images, using them to train machine learning models. In this work, we explore an alternative way of exploiting tactile information to predict grasp stability by leveraging graph-like representations of tactile data, which preserve the actual spatial arrangement of the sensor's taxels and their locality. In experimentation, we trained a Graph Neural Network to binary classify grasps as stable or slippery ones. To train such network and prove its predictive capabilities for the problem at hand, we captured a novel dataset of approximately 5000 three-fingered grasps across 41 objects for training and 1000 grasps with 10 unknown objects for testing. Our experiments prove that this novel approach can be effectively used to predict grasp stability.
On the Achievable Rate and Capacity for a Sample-based Practical Photon-counting Receiver
Venue: arXiv cs.IT 2019
Year: 2019

We investigate the achievable rate and capacity of a non-perfect photon-counting receiver. For the case of long symbol duration, the achievable rate under on-off keying modulation is investigated based on Kullback-Leibler (KL) divergence and Chernoff $α$-divergence. We prove the tightness of the derived bounds for large peak power with zero background radiation with exponential convergence rate, and for low peak power of order two convergence rate. For large peak power with fixed background radiation and low background radiation with fixed peak power, the proposed bound gap is a small positive value for low background radiation and large peak power, respectively. Moreover, we propose an approximation on the achievable rate in the low background radiation and long symbol duration regime, which is more accurate compared with the derived upper and lower bounds in the medium signal to noise ratio (SNR) regime. For the symbol duration that can be sufficiently small, the capacity and the optimal duty cycle are is investigated. We show that the capacity approaches that of continuous Poisson capacity as $T_s=τ\to0$. The asymptotic capacity is analyzed for low and large peak power. Compared with the continuous Poisson capacity, the capacity of a non-perfect receiver is almost lossless and loss with attenuation for low peak power given zero background radiation and nonzero background radiation, respectively. For large peak power, the capacity with a non-perfect receiver converges, while that of continuous Poisson capacity channel linearly increases. The above theoretical results are extensively validated by numerical results.
Red blood cell image generation for data augmentation using Conditional Generative Adversarial Networks
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we describe how to apply image-to-image translation techniques to medical blood smear data to generate new data samples and meaningfully increase small datasets. Specifically, given the segmentation mask of the microscopy image, we are able to generate photorealistic images of blood cells which are further used alongside real data during the network training for segmentation and object detection tasks. This image data generation approach is based on conditional generative adversarial networks which have proven capabilities to high-quality image synthesis. In addition to synthesizing blood images, we synthesize segmentation mask as well which leads to a diverse variety of generated samples. The effectiveness of the technique is thoroughly analyzed and quantified through a number of experiments on a manually collected and annotated dataset of blood smear taken under a microscope.
Computing Optimal Coarse Correlated Equilibria in Sequential Games
Venue: arXiv cs.GT 2019
Year: 2019

We investigate the computation of equilibria in extensive-form games where ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by the hardness results on the computation of normal-form correlated equilibria, we introduce the notion of normal-form coarse correlated equilibrium, extending the definition of coarse correlated equilibrium to sequential games. We show that, in two-player games without chance moves, an optimal (e.g., social welfare maximizing) normal-form coarse correlated equilibrium can be computed in polynomial time, and that in general multi-player games (including two-player games with Chance), the problem is NP-hard. For the former case, we provide a polynomial-time algorithm based on the ellipsoid method and also propose a more practical one, which can be efficiently applied to problems of considerable size. Then, we discuss how our algorithm can be extended to games with Chance and games with more than two players.
Rwandacoin: Prospects and challenges of developing a cryptocurrency for transactions in Rwanda
Venue: arXiv cs.CY 2019
Year: 2019

The use of cryptocurrencies such as Bitcoin and Ethereum in performing online transactions has been on the rise in the world. Africa as a continent is not left out in the adoption of blockchain and cryptocurrencies. This paper explores the prospects and challenges of developing a cryptocurrency in Rwanda which we denote Rwandacoin. In addition, the paper discusses the potentials of Rwandacoin easing intercountry trading in East Africa.
NeuNetS: An Automated Synthesis Engine for Neural Network Design
Venue: arXiv cs.LG 2019
Year: 2019

Application of neural networks to a vast variety of practical applications is transforming the way AI is applied in practice. Pre-trained neural network models available through APIs or capability to custom train pre-built neural network architectures with customer data has made the consumption of AI by developers much simpler and resulted in broad adoption of these complex AI models. While prebuilt network models exist for certain scenarios, to try and meet the constraints that are unique to each application, AI teams need to think about developing custom neural network architectures that can meet the tradeoff between accuracy and memory footprint to achieve the tight constraints of their unique use-cases. However, only a small proportion of data science teams have the skills and experience needed to create a neural network from scratch, and the demand far exceeds the supply. In this paper, we present NeuNetS : An automated Neural Network Synthesis engine for custom neural network design that is available as part of IBM's AI OpenScale's product. NeuNetS is available for both Text and Image domains and can build neural networks for specific tasks in a fraction of the time it takes today with human effort, and with accuracy similar to that of human-designed AI models.
Analysis of a site's integrity by 3D models and Integrated database, case study : the pic-du-midi high-mountain observatory (France)
Venue: arXiv cs.CY 2019
Year: 2019

The concept of "integrity", as currently used in the analysis of World Heritage sites or cultural landscapes mainly consists of 1) the composition of a given site, regarding its origins and its current state of conservation; 2) the visual and functional relationships between its components (attributes). One of the major questions is "what defines the origin period?". The integrity analysis has to clearly understand and evaluate which tangible components exist, in order to correctly identify their origin period, estimate how much of the original structure and function remain. An additional difficulty rises in case of scientific and/or technical heritage assessment: the very historical necessity of updating and implementing technical/scientific innovations. These follow advances in science and/or technique(s), and lead to frequent successive changes, impacting the site's structure. Hence, for living sites, one cannot see the origin of the project as the only reference state, as it could be for classical heritage; it is instead requisite to enlighten a chronological series of major reference states. The Pic-du-Midi Observatory (France) is a remarkable example as high-mountain scientific station (2860 m). Its various and successive scientific uses led to a series of reshaping and structural evolutions over around 150 years, till nowadays. We have there a series of reference states very conform to an active scientific station and observatory. The project aims to combine historical data and measurements on the current site's state, to build a succession of 3D models for a series of 5 or 6 'reference state' of the observatory within associated database, and to document the integrity analysis more accurately than usual. The final uses of the digital achievement will also serve for the management of the site and for further development of