OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized Complexity of Conflict-free Graph Coloring
Venue: arXiv cs.CC 2019
Year: 2019

Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring $c:V(G) \rightarrow \{1,2,\ldots,q\}$ such that for each vertex $v \in V(G)$ there is a vertex in $N(v)$ that is uniquely colored from the rest of the vertices in $N(v)$. When we replace $N(v)$ by the closed neighborhood $N[v]$, then we call such a coloring a q-closed neighborhood conflict-free coloring or simply q-CNCF-coloring. In this paper, we study the NP-hard decision questions of whether for a constant q an input graph has a q-ONCF-coloring or a q-CNCF-coloring. We will study these two problems in the parameterized setting. First of all, we study running time bounds on FPT-algorithms for these problems, when parameterized by treewidth. We improve the existing upper bounds, and also provide lower bounds on the running time under ETH and SETH. Secondly, we study the kernelization complexity of both problems, using vertex cover as the parameter. We show that both $(q \geq 2)$-ONCF-coloring and $(q \geq 3)$-CNCF-coloring cannot have polynomial kernels when parameterized by the size of a vertex cover unless $NP \in coNP/poly$. However, we obtain a polynomial kernel for 2-CNCF-coloring parameterized by vertex cover. We conclude with some combinatorial results. Denote $χ_{ON}(G)$ and $χ_{CN}(G)$ to be the minimum number of colors required to ONCF-color and CNCF-color G, respectively. Upper bounds on $χ_{CN}(G)$ with respect to structural parameters like minimum vertex cover size, minimum feedback vertex set size and treewidth are known. To the best of our knowledge only an upper bound on $χ_{ON}(G)$ with respect to minimum vertex cover size was known. We provide tight bounds for $χ_{ON}(G)$ with respect to minimum vertex cover size. Also, we provide the first upper bounds on $χ_{ON}(G)$ with respect to minimum feedback vertex set size and treewidth.
Interpretable multiclass classification by MDL-based rule lists
Venue: arXiv cs.LG 2019
Year: 2019

Interpretable classifiers have recently witnessed an increase in attention from the data mining community because they are inherently easier to understand and explain than their more complex counterparts. Examples of interpretable classification models include decision trees, rule sets, and rule lists. Learning such models often involves optimizing hyperparameters, which typically requires substantial amounts of data and may result in relatively large models. In this paper, we consider the problem of learning compact yet accurate probabilistic rule lists for multiclass classification. Specifically, we propose a novel formalization based on probabilistic rule lists and the minimum description length (MDL) principle. This results in virtually parameter-free model selection that naturally allows to trade-off model complexity with goodness of fit, by which overfitting and the need for hyperparameter tuning are effectively avoided. Finally, we introduce the Classy algorithm, which greedily finds rule lists according to the proposed criterion. We empirically demonstrate that Classy selects small probabilistic rule lists that outperform state-of-the-art classifiers when it comes to the combination of predictive performance and interpretability. We show that Classy is insensitive to its only parameter, i.e., the candidate set, and that compression on the training set correlates with classification performance, validating our MDL-based selection criterion.
Network Calculus-based Timing Analysis of AFDX networks incorporating multiple TSN/BLS traffic classes
Venue: arXiv cs.NI 2019
Year: 2019

We propose a formal timing analysis of an extension of the AFDX standard, incorporating the TSN/BLS shaper, to homogenize the avionics communication architecture, and enable the interconnection of different avionics domains with mixed-criticality levels, e.g., current AFDX traffic, Flight Control and In-Flight Entertainment. Existing Network Calculus models are limited to three classes, but applications with heterogeneous traffic require additional classes. Hence, we propose to generalize an existing Network Calculus model to do a worst-case timing analysis of an architecture with multiple BLS on multi-hop networks, to infer real-time bounds. Then, we conduct the performance analysis of such a proposal. First we evaluate the model on a simple 3-classes single-hop network to assess the sensitivity and tightness of the model, and compare it to existing models (CPA and Network Calculus). Secondly, we study a realistic AFDX configuration with six classes and two BLS. Finally, we compute a real use-case to add A350 flight control traffic to the AFDX. Results show the good properties of the generalized Network Calculus model compared to the CPA model and the efficiency of the extended AFDX to noticeably enhance the medium priority level delay bounds, while respecting the higher priority level constraints, in comparison with the current AFDX standard.
An ADMM Based Framework for AutoML Pipeline Configuration
Venue: arXiv cs.LG 2019
Year: 2019

We study the AutoML problem of automatically configuring machine learning pipelines by jointly selecting algorithms and their appropriate hyper-parameters for all steps in supervised learning pipelines. This black-box (gradient-free) optimization with mixed integer & continuous variables is a challenging problem. We propose a novel AutoML scheme by leveraging the alternating direction method of multipliers (ADMM). The proposed framework is able to (i) decompose the optimization problem into easier sub-problems that have a reduced number of variables and circumvent the challenge of mixed variable categories, and (ii) incorporate black-box constraints along-side the black-box optimization objective. We empirically evaluate the flexibility (in utilizing existing AutoML techniques), effectiveness (against open source AutoML toolkits),and unique capability (of executing AutoML with practically motivated black-box constraints) of our proposed scheme on a collection of binary classification data sets from UCI ML& OpenML repositories. We observe that on an average our framework provides significant gains in comparison to other AutoML frameworks (Auto-sklearn & TPOT), highlighting the practical advantages of this framework.
Detection of Single Grapevine Berries in Images Using Fully Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Yield estimation and forecasting are of special interest in the field of grapevine breeding and viticulture. The number of harvested berries per plant is strongly correlated with the resulting quality. Therefore, early yield forecasting can enable a focused thinning of berries to ensure a high quality end product. Traditionally yield estimation is done by extrapolating from a small sample size and by utilizing historic data. Moreover, it needs to be carried out by skilled experts with much experience in this field. Berry detection in images offers a cheap, fast and non-invasive alternative to the otherwise time-consuming and subjective on-site analysis by experts. We apply fully convolutional neural networks on images acquired with the Phenoliner, a field phenotyping platform. We count single berries in images to avoid the error-prone detection of grapevine clusters. Clusters are often overlapping and can vary a lot in the size which makes the reliable detection of them difficult. We address especially the detection of white grapes directly in the vineyard. The detection of single berries is formulated as a classification task with three classes, namely 'berry', 'edge' and 'background'. A connected component algorithm is applied to determine the number of berries in one image. We compare the automatically counted number of berries with the manually detected berries in 60 images showing Riesling plants in vertical shoot positioned trellis (VSP) and semi minimal pruned hedges (SMPH). We are able to detect berries correctly within the VSP system with an accuracy of 94.0 \% and for the SMPH system with 85.6 \%.
Attention Monitoring and Hazard Assessment with Bio-Sensing and Vision: Empirical Analysis Utilizing CNNs on the KITTI Dataset
Venue: arXiv cs.HC 2019
Year: 2019

Assessing the driver's attention and detecting various hazardous and non-hazardous events during a drive are critical for driver's safety. Attention monitoring in driving scenarios has mostly been carried out using vision (camera-based) modality by tracking the driver's gaze and facial expressions. It is only recently that bio-sensing modalities such as Electroencephalogram (EEG) are being explored. But, there is another open problem which has not been explored sufficiently yet in this paradigm. This is the detection of specific events, hazardous and non-hazardous, during driving that affects the driver's mental and physiological states. The other challenge in evaluating multi-modal sensory applications is the absence of very large scale EEG data because of the various limitations of using EEG in the real world. In this paper, we use both of the above sensor modalities and compare them against the two tasks of assessing the driver's attention and detecting hazardous vs. non-hazardous driving events. We collect user data on twelve subjects and show how in the absence of very large-scale datasets, we can still use pre-trained deep learning convolution networks to extract meaningful features from both of the above modalities. We used the publicly available KITTI dataset for evaluating our platform and to compare it with previous studies. Finally, we show that the results presented in this paper surpass the previous benchmark set up in the above driver awareness-related applications.
An Efficient Reachability-Based Framework for Provably Safe Autonomous Navigation in Unknown Environments
Venue: arXiv cs.RO 2019
Year: 2019

Real-world autonomous vehicles often operate in a priori unknown environments. Since most of these systems are safety-critical, it is important to ensure they operate safely in the face of environment uncertainty, such as unseen obstacles. Current safety analysis tools enable autonomous systems to reason about safety given full information about the state of the environment a priori. However, these tools do not scale well to scenarios where the environment is being sensed in real time, such as during navigation tasks. In this work, we propose a novel, real-time safety analysis method based on Hamilton-Jacobi reachability that provides strong safety guarantees despite environment uncertainty. Our safety method is planner-agnostic and provides guarantees for a variety of mapping sensors. We demonstrate our approach in simulation and in hardware to provide safety guarantees around a state-of-the-art vision-based, learning-based planner.
The relationship between Biological and Artificial Intelligence
Venue: arXiv cs.AI 2019
Year: 2019

Intelligence can be defined as a predominantly human ability to accomplish tasks that are generally hard for computers and animals. Artificial Intelligence [AI] is a field attempting to accomplish such tasks with computers. AI is becoming increasingly widespread, as are claims of its relationship with Biological Intelligence. Often these claims are made to imply higher chances of a given technology succeeding, working on the assumption that AI systems which mimic the mechanisms of Biological Intelligence should be more successful. In this article I will discuss the similarities and differences between AI and the extent of our knowledge about the mechanisms of intelligence in biology, especially within humans. I will also explore the validity of the assumption that biomimicry in AI systems aids their advancement, and I will argue that existing similarity to biological systems in the way Artificial Neural Networks [ANNs] tackle tasks is due to design decisions, rather than inherent similarity of underlying mechanisms. This article is aimed at people who understand the basics of AI (especially ANNs), and would like to be better able to evaluate the often wild claims about the value of biomimicry in AI.
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel computation (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph $G$ using about $κ(G)$ colors, where $κ(G)$ is the degeneracy of $G$: this parameter is closely related to the arboricity $α(G)$. As a function of $κ(G)$ alone, our results are close to best possible, since the optimal number of colors is $κ(G)+1$. On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses $κ(G)+1$ many colors, would require $Ω(n^2)$ storage in the one pass streaming model, and $Ω(n^2)$ many queries in the general graph query model, where $n$ is the number of vertices in the graph. These lower bounds hold even when the value of $κ(G)$ is known in advance; at the same time, our upper bounds do not require $κ(G)$ to be given in advance.
Social Network of Extreme Tweeters: A Case Study
Venue: arXiv cs.SI 2019
Year: 2019

The number of posts made by a single user account on a social media platform Twitter in any given time interval is usually quite low. However, there is a subset of users whose volume of posts is much higher than the median. In this paper, we investigate the content diversity and the social neighborhood of these extreme users and others. We define a metric called "interest narrowness", and identify that a subset of extreme users, termed anomalous users, write posts with very low topic diversity, including posts with no text content. Using a few interaction patterns we show that anomalous groups have the strongest within-group interactions, compared to their interaction with others. Further, they exhibit different information sharing behaviors with other anomalous users compared to non-anomalous extreme tweeters.
Reputation-Based Information Design for Inducing Prosocial Behavior
Venue: arXiv cs.SI 2019
Year: 2019

We study the idea of information design for inducing prosocial behavior in the context of electricity consumption. We consider a continuum of agents. Each agent has a different intrinsic motivation to reduce her power consumption. Each agent models the power consumption of the others via a distribution. Using this distribution, agents will anticipate their reputational benefit and choose a power consumption by trading off their own intrinsic motivation to do a prosocial action, the cost of this prosocial action and their reputation. Initially, the service provider can provide two types of quantized feedbacks of the power consumption. We study their advantages and disadvantages. For each feedback, we characterize the corresponding mean field equilibrium, using a fixed point equation. Besides computing the mean field equilibrium, we highlight the need for a systematic study of information design, by showing that revealing less information to the society can lead to more prosociality. In the last part of the paper, we introduce the notion of privacy and provide a new quantized feedback, more flexible than the previous ones, that respects agents' privacy concern but at the same time improves prosociality. The results of this study are also applicable to generic resource sharing problems.
Directing DNNs Attention for Facial Attribution Classification using Gradient-weighted Class Activation Mapping
Venue: arXiv cs.CV 2019
Year: 2019

Deep neural networks (DNNs) have a high accuracy on image classification tasks. However, DNNs trained by such dataset with co-occurrence bias may rely on wrong features while making decisions for classification. It will greatly affect the transferability of pre-trained DNNs. In this paper, we propose an interactive method to direct classifiers paying attentions to the regions that are manually specified by the users, in order to mitigate the influence of co-occurrence bias. We test on CelebA dataset, the pre-trained AlexNet is fine-tuned to focus on the specific facial attributes based on the results of Grad-CAM.
Variational Autoencoders for Sparse and Overdispersed Discrete Data
Venue: arXiv cs.LG 2019
Year: 2019

Many applications, such as text modelling, high-throughput sequencing, and recommender systems, require analysing sparse, high-dimensional, and overdispersed discrete (count-valued or binary) data. Although probabilistic matrix factorisation and linear/nonlinear latent factor models have enjoyed great success in modelling such data, many existing models may have inferior modelling performance due to the insufficient capability of modelling overdispersion in count-valued data and model misspecification in general. In this paper, we comprehensively study these issues and propose a variational autoencoder based framework that generates discrete data via negative-binomial distribution. We also examine the model's ability to capture properties, such as self- and cross-excitations in discrete data, which is critical for modelling overdispersion. We conduct extensive experiments on three important problems from discrete data analysis: text analysis, collaborative filtering, and multi-label learning. Compared with several state-of-the-art baselines, the proposed models achieve significantly better performance on the above problems.
LivDet in Action - Fingerprint Liveness Detection Competition 2019
Venue: arXiv cs.CV 2019
Year: 2019

The International Fingerprint liveness Detection Competition (LivDet) is an open and well-acknowledged meeting point of academies and private companies that deal with the problem of distinguishing images coming from reproductions of fingerprints made of artificial materials and images relative to real fingerprints. In this edition of LivDet we invited the competitors to propose integrated algorithms with matching systems. The goal was to investigate at which extent this integration impact on the whole performance. Twelve algorithms were submitted to the competition, eight of which worked on integrated systems.
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
Venue: arXiv cs.DS 2019
Year: 2019

We consider the $k$-Median problem on planar graphs: given an edge-weighted planar graph $G$, a set of clients $C \subseteq V(G)$, a set of facilities $F \subseteq V(G)$, and an integer parameter $k$, the task is to find a set of at most $k$ facilities whose opening minimizes the total connection cost of clients, where each client contributes to the cost with the distance to the closest open facility. We give two new approximation schemes for this problem: -- FPT Approximation Scheme: for any $ε>0$, in time $2^{O(kε^{-3}\log (kε^{-1}))}\cdot n^{O(1)}$ we can compute a solution that (1) has connection cost at most $(1+ε)$ times the optimum, with high probability. -- Efficient Bicriteria Approximation Scheme: for any $ε>0$, in time $2^{O(ε^{-5}\log (ε^{-1}))}\cdot n^{O(1)}$ we can compute a set of at most $(1+ε)k$ facilities (2) whose opening yields connection cost at most $(1+ε)$ times the optimum connection cost for opening at most $k$ facilities, with high probability. As a direct corollary of the second result we obtain an EPTAS for the Uniform Facility Location on planar graphs, with same running time. Our main technical tool is a new construction of a "coreset for facilities" for $k$-Median in planar graphs: we show that in polynomial time one can compute a subset of facilities $F_0\subseteq F$ of size $k\cdot (\log n/ε)^{O(ε^{-3})}$ with a guarantee that there is a $(1+ε)$-approximate solution contained in $F_0$.
Privacy of Agents' Costs in Peer-to-Peer Distributed Optimization
Venue: arXiv cs.SY 2019
Year: 2019

In this paper, we propose a protocol that preserves (statistical) privacy of agents' costs in peer-to-peer distributed optimization against a passive adversary that corrupts certain number of agents in the network. The proposed protocol guarantees privacy of the affine parts of the honest agents' costs (agents that are not corrupted by the adversary) if the corrupted agents do not form a vertex cut of the underlying communication topology. Therefore, if the (passive) adversary corrupts at most t arbitrary agents in the network then the proposed protocol can preserve the privacy of the affine parts of the remaining honest agents' costs if the communication topology has (t+1)-connectivity. The proposed privacy protocol is a composition of a privacy mechanism (we propose) with any (non-private) distributed optimization algorithm.
Performance Analysis of SSK-NOMA
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider the combination between two promising techniques: space-shift keying (SSK) and non-orthogonal multiple access (NOMA) for future radio access networks. We analyze the performance of SSK-NOMA networks and provide a comprehensive analytical framework of SSK-NOMA regarding bit error probability (BEP), ergodic capacity and outage probability. It is worth pointing out all analysis also stand for conventional SIMO-NOMA networks. We derive closed-form exact average BEP (ABEP) expressions when the number of users in a resource block is equal to i.e., $L=3$. Nevertheless, we analyze the ABEP of users when the number of users is more than i.e., $L\geq3$, and derive bit-error-rate (BER) union bound since the error propagation due to iterative successive interference canceler (SIC) makes the exact analysis intractable. Then, we analyze the achievable rate of users and derive exact ergodic capacity of the users so the ergodic sum rate of the system in closed-forms. Moreover, we provide the average outage probability of the users exactly in the closed-form. All derived expressions are validated via Monte Carlo simulations and it is proved that SSK-NOMA outperforms conventional NOMA networks in terms of all performance metrics (i.e., BER, sum rate, outage). Finally, the effect of the power allocation (PA) on the performance of SSK-NOMA networks is investigated and the optimum PA is discussed under BER and outage constraints.
Single Image Portrait Relighting
Venue: arXiv cs.GR 2019
Year: 2019

Lighting plays a central role in conveying the essence and depth of the subject in a portrait photograph. Professional photographers will carefully control the lighting in their studio to manipulate the appearance of their subject, while consumer photographers are usually constrained to the illumination of their environment. Though prior works have explored techniques for relighting an image, their utility is usually limited due to requirements of specialized hardware, multiple images of the subject under controlled or known illuminations, or accurate models of geometry and reflectance. To this end, we present a system for portrait relighting: a neural network that takes as input a single RGB image of a portrait taken with a standard cellphone camera in an unconstrained environment, and from that image produces a relit image of that subject as though it were illuminated according to any provided environment map. Our method is trained on a small database of 18 individuals captured under different directional light sources in a controlled light stage setup consisting of a densely sampled sphere of lights. Our proposed technique produces quantitatively superior results on our dataset's validation set compared to prior works, and produces convincing qualitative relighting results on a dataset of hundreds of real-world cellphone portraits. Because our technique can produce a 640 $\times$ 640 image in only 160 milliseconds, it may enable interactive user-facing photographic applications in the future.