OpenRaiser/Intern-Atlas huggingface dataset:
Integer Programming Approaches to Balanced Connected $k$-Partition
Venue: arXiv cs.DM 2019
Year: 2019

We address the problem of partitioning a vertex-weighted connected graph into $k$ connected subgraphs that have similar weights, for a fixed integer $k\geq 2$. This problem, known as the \emph{balanced connected $k$-partition problem} ($BCP_k$), is defined as follows. Given a connected graph $G$ with nonnegative weights on the vertices, find a partition $\{V_i\}_{i=1}^k$ of $V(G)$ such that each class $V_i$ induces a connected subgraph of $G$, and the weight of a class with the minimum weight is as large as possible. It is known that $BCP_k$ is $NP$-hard even on bipartite graphs and on interval graphs. It has been largely investigated under different approaches and perspectives. On the practical side, $BCP_k$ is used to model many applications arising in police patrolling, image processing, cluster analysis, operating systems and robotics. We propose three integer linear programming formulations for the balanced connected $k$-partition problem. The first one contains only binary variables and a potentially large number of constraints that are separable in polynomial time. Some polyhedral results on this formulation, when all vertices have unit weight, are also presented. The other formulations are based on flows and have a polynomial number of constraints and variables. Preliminary computational experiments have shown that the proposed formulations outperform the other formulations presented in the literature.
Recombination: A family of Markov chains for redistricting
Venue: arXiv cs.CY 2019
Year: 2019

Redistricting is the problem of partitioning a set of geographical units into a fixed number of districts, subject to a list of often-vague rules and priorities. In recent years, the use of randomized methods to sample from the vast space of districting plans has been gaining traction in courts of law for identifying partisan gerrymanders, and it is now emerging as a possible analytical tool for legislatures and independent commissions. In this paper, we set up redistricting as a graph partition problem and introduce a new family of Markov chains called Recombination (or ReCom) on the space of graph partitions. The main point of comparison will be the commonly used Flip walk, which randomly changes the assignment label of a single node at a time. We present evidence that ReCom mixes efficiently, especially in contrast to the slow-mixing Flip, and provide experiments that demonstrate its qualitative behavior. We demonstrate the advantages of ReCom on real-world data and explain both the challenges of the Markov chain approach and the analytical tools that it enables. We close with a short case study involving the Virginia House of Delegates.
Artificial Intelligence Strategies for National Security and Safety Standards
Venue: arXiv cs.CY 2019
Year: 2019

Recent advances in artificial intelligence (AI) have lead to an explosion of multimedia applications (e.g., computer vision (CV) and natural language processing (NLP)) for different domains such as commercial, industrial, and intelligence. In particular, the use of AI applications in a national security environment is often problematic because the opaque nature of the systems leads to an inability for a human to understand how the results came about. A reliance on 'black boxes' to generate predictions and inform decisions is potentially disastrous. This paper explores how the application of standards during each stage of the development of an AI system deployed and used in a national security environment would help enable trust. Specifically, we focus on the standards outlined in Intelligence Community Directive 203 (Analytic Standards) to subject machine outputs to the same rigorous standards as analysis performed by humans.
Machine Learning Based Network Vulnerability Analysis of Industrial Internet of Things
Venue: arXiv cs.CR 2019
Year: 2019

It is critical to secure the Industrial Internet of Things (IIoT) devices because of potentially devastating consequences in case of an attack. Machine learning and big data analytics are the two powerful leverages for analyzing and securing the Internet of Things (IoT) technology. By extension, these techniques can help improve the security of the IIoT systems as well. In this paper, we first present common IIoT protocols and their associated vulnerabilities. Then, we run a cyber-vulnerability assessment and discuss the utilization of machine learning in countering these susceptibilities. Following that, a literature review of the available intrusion detection solutions using machine learning models is presented. Finally, we discuss our case study, which includes details of a real-world testbed that we have built to conduct cyber-attacks and to design an intrusion detection system (IDS). We deploy backdoor, command injection, and Structured Query Language (SQL) injection attacks against the system and demonstrate how a machine learning based anomaly detection system can perform well in detecting these attacks. We have evaluated the performance through representative metrics to have a fair point of view on the effectiveness of the methods.
Visual-Inertial Localization for Skid-Steering Robots with Kinematic Constraints
Venue: arXiv cs.RO 2019
Year: 2019

While visual localization or SLAM has witnessed great progress in past decades, when deploying it on a mobile robot in practice, few works have explicitly considered the kinematic (or dynamic) constraints of the real robotic system when designing state estimators. To promote the practical deployment of current state-of-the-art visual-inertial localization algorithms, in this work we propose a low-cost kinematics-constrained localization system particularly for a skid-steering mobile robot. In particular, we derive in a principle way the robot's kinematic constraints based on the instantaneous centers of rotation (ICR) model and integrate them in a tightly-coupled manner into the sliding-window bundle adjustment (BA)-based visual-inertial estimator. Because the ICR model parameters are time-varying due to, for example, track-to-terrain interaction and terrain roughness, we estimate these kinematic parameters online along with the navigation state. To this end, we perform in-depth the observability analysis and identify motion conditions under which the state/parameter estimation is viable. The proposed kinematics-constrained visual-inertial localization system has been validated extensively in different terrain scenarios.
Triply Robust Off-Policy Evaluation
Venue: arXiv cs.LG 2019
Year: 2019

We propose a robust regression approach to off-policy evaluation (OPE) for contextual bandits. We frame OPE as a covariate-shift problem and leverage modern robust regression tools. Ours is a general approach that can be used to augment any existing OPE method that utilizes the direct method. When augmenting doubly robust methods, we call the resulting method Triply Robust. We prove upper bounds on the resulting bias and variance, as well as derive novel minimax bounds based on robust minimax analysis for covariate shift. Our robust regression method is compatible with deep learning, and is thus applicable to complex OPE settings that require powerful function approximators. Finally, we demonstrate superior empirical performance across the standard OPE benchmarks, especially in the case where the logging policy is unknown and must be estimated from data.
Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

We present an algorithm, HOMER, for exploration and reinforcement learning in rich observation environments that are summarizable by an unknown latent state space. The algorithm interleaves representation learning to identify a new notion of kinematic state abstraction with strategic exploration to reach new states using the learned abstraction. The algorithm provably explores the environment with sample complexity scaling polynomially in the number of latent states and the time horizon, and, crucially, with no dependence on the size of the observation space, which could be infinitely large. This exploration guarantee further enables sample-efficient global policy optimization for any reward function. On the computational side, we show that the algorithm can be implemented efficiently whenever certain supervised learning problems are tractable. Empirically, we evaluate HOMER on a challenging exploration problem, where we show that the algorithm is exponentially more sample efficient than standard reinforcement learning baselines.
Inverse design of fluid flow structure with Turing pattern
Venue: arXiv cs.CE 2019
Year: 2019

Microchannel reactors are critical in biological plus energy-related applications and require meticulous design of hundreds-to-thousands of fluid flow channels. Such systems commonly comprise intricate space-filling microstructures to control the fluid flow distribution for the reaction process. Traditional flow channel design schemes are intuition-based or utilize analytical rule-based optimization strategies that are oversimplified for large-scale domains of arbitrary geometry. Here, a gradient-based optimization method is proposed, where effective porous media and fluid velocity vector design information is exploited and linked to explicit microchannel parameterizations. Reaction-diffusion equations are then utilized to generate space-filling Turing pattern microchannel flow structures from the porous media field. With this computationally efficient and broadly applicable technique, precise control of fluid flow distribution is demonstrated across large numbers (on the order of hundreds) of microchannels.
Emotion and Theme Recognition in Music with Frequency-Aware RF-Regularized CNNs
Venue: arXiv cs.SD 2019
Year: 2019

We present CP-JKU submission to MediaEval 2019; a Receptive Field-(RF)-regularized and Frequency-Aware CNN approach for tagging music with emotion/mood labels. We perform an investigation regarding the impact of the RF of the CNNs on their performance on this dataset. We observe that ResNets with smaller receptive fields -- originally adapted for acoustic scene classification -- also perform well in the emotion tagging task. We improve the performance of such architectures using techniques such as Frequency Awareness and Shake-Shake regularization, which were used in previous work on general acoustic recognition tasks.
The Complexity of Synthesizing nop-Equipped Boolean Nets from g-Bounded Inputs (Technical Report)
Venue: arXiv cs.CC 2019
Year: 2019

Boolean Petri nets equipped with nop allow places and transitions to be independent by being related by nop. We characterize for any fixed natural number g the computational complexity of synthesizing nop-equipped Boolean Petri nets from labeled directed graphs whose states have at most g incoming and at most g outgoing arcs.
SpiralNet++: A Fast and Highly Efficient Mesh Convolution Operator
Venue: arXiv cs.CV 2019
Year: 2019

Intrinsic graph convolution operators with differentiable kernel functions play a crucial role in analyzing 3D shape meshes. In this paper, we present a fast and efficient intrinsic mesh convolution operator that does not rely on the intricate design of kernel function. We explicitly formulate the order of aggregating neighboring vertices, instead of learning weights between nodes, and then a fully connected layer follows to fuse local geometric structure information with vertex features. We provide extensive evidence showing that models based on this convolution operator are easier to train, and can efficiently learn invariant shape features. Specifically, we evaluate our method on three different types of tasks of dense shape correspondence, 3D facial expression classification, and 3D shape reconstruction, and show that it significantly outperforms state-of-the-art approaches while being significantly faster, without relying on shape descriptors. Our source code is available on GitHub.
Revenue Maximization of Airbnb Marketplace using Search Results
Venue: arXiv cs.LG 2019
Year: 2019

Correctly pricing products or services in an online marketplace presents a challenging problem and one of the critical factors for the success of the business. When users are looking to buy an item they typically search for it. Query relevance models are used at this stage to retrieve and rank the items on the search page from most relevant to least relevant. The presented items are naturally "competing" against each other for user purchases. We provide a practical two-stage model to price this set of retrieved items for which distributions of their values are learned. The initial output of the pricing strategy is a price vector for the top displayed items in one search event. We later aggregate these results over searches to provide the supplier with the optimal price for each item. We applied our solution to large-scale search data obtained from Airbnb Experiences marketplace. Offline evaluation results show that our strategy improves upon baseline pricing strategies on key metrics by at least +20% in terms of booking regret and +55% in terms of revenue potential.
Multi-Antenna Aided Secrecy Beamforming Optimization for Wirelessly Powered HetNets
Venue: arXiv cs.IT 2019
Year: 2019

The new paradigm of wirelessly powered two-tier heterogeneous networks (HetNets) is considered in this paper. Specifically, the femtocell base station (FBS) is powered by a power beacon (PB) and transmits confidential information to a legitimate femtocell user (FU) in the presence of a potential eavesdropper (EVE) and a macro base station (MBS). In this scenario, we investigate the secrecy beamforming design under three different levels of FBS-EVE channel state information (CSI), namely, the perfect, imperfect and completely unknown FBS-EVE CSI. Firstly, given the perfect global CSI at the FBS, the PB energy covariance matrix, the FBS information covariance matrix and the time splitting factor are jointly optimized aiming for perfect secrecy rate maximization. Upon assuming the imperfect FBS-EVE CSI, the worst-case and outage-constrained SRM problems corresponding to deterministic and statistical CSI errors are investigated, respectively. Furthermore, considering the more realistic case of unknown FBS-EVE CSI, the artificial noise (AN) aided secrecy beamforming design is studied. Our analysis reveals that for all the above cases both the optimal PB energy and FBS information secrecy beamformings are of rank-1. Moreover, for all considered cases of FBS-EVE CSI, the closed-form PB energy beamforming solutions are available when the cross-tier interference constraint is inactive. Numerical simulation results demonstrate the secrecy performance advantages of all proposed secrecy beamforming designs compared to the adopted baseline algorithms.
Explainable Ordinal Factorization Model: Deciphering the Effects of Attributes by Piece-wise Linear Approximation
Venue: arXiv cs.LG 2019
Year: 2019

Ordinal regression predicts the objects' labels that exhibit a natural ordering, which is important to many managerial problems such as credit scoring and clinical diagnosis. In these problems, the ability to explain how the attributes affect the prediction is critical to users. However, most, if not all, existing ordinal regression models simplify such explanation in the form of constant coefficients for the main and interaction effects of individual attributes. Such explanation cannot characterize the contributions of attributes at different value scales. To address this challenge, we propose a new explainable ordinal regression model, namely, the Explainable Ordinal Factorization Model (XOFM). XOFM uses the piece-wise linear functions to approximate the actual contributions of individual attributes and their interactions. Moreover, XOFM introduces a novel ordinal transformation process to assign each object the probabilities of belonging to multiple relevant classes, instead of fixing boundaries to differentiate classes. XOFM is based on the Factorization Machines to handle the potential sparsity problem as a result of discretizing the attribute scales. Comprehensive experiments with benchmark datasets and baseline models demonstrate that the proposed XOFM exhibits superior explainability and leads to state-of-the-art prediction accuracy.
Enabling Efficient Privacy-Assured Outlier Detection over Encrypted Incremental Datasets
Venue: arXiv cs.CR 2019
Year: 2019

Outlier detection is widely used in practice to track the anomaly on incremental datasets such as network traffic and system logs. However, these datasets often involve sensitive information, and sharing the data to third parties for anomaly detection raises privacy concerns. In this paper, we present a privacy-preserving outlier detection protocol (PPOD) for incremental datasets. The protocol decomposes the outlier detection algorithm into several phases and recognises the necessary cryptographic operations in each phase. It realises several cryptographic modules via efficient and interchangeable protocols to support the above cryptographic operations and composes them in the overall protocol to enable outlier detection over encrypted datasets. To support efficient updates, it integrates the sliding window model to periodically evict the expired data in order to maintain a constant update time. We build a prototype of PPOD and systematically evaluates the cryptographic modules and the overall protocols under various parameter settings. Our results show that PPOD can handle encrypted incremental datasets with a moderate computation and communication cost.
Performance of Two-Way Relaying over $α$-$μ$ Fading Channels in Hybrid RF/FSO Wireless Networks
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, the performance of two-way relaying in mixed RF/FSO communication system with a backup RF link is investigated. Uplink RF channels are used to send data of $K$ users to a two-way relay, $R$, whereas FSO link is mainly used to exchange data between a base station $S$ and $R$. We propose to have a backup RF link between the relay $R$ and the node $S$ to improve reliability under certain conditions. All uplink RF channels follow Rayleigh fading model while $α$-$μ$ is adopted to model both backup RF and FSO links. We approximate the widely used Gamma-Gamma fading model using the $α$-$μ$ distribution based on moments-based estimator technique assuming perfect alignment between transmitter and receiver antennas. This approximation shows good agreement under certain atmospheric turbulence conditions. Then, we derive exact closed-form expressions for the outage and average symbol error probabilities and derive approximations at high signal-to-noise ratio (SNR). We corroborate our analytical expressions with extensive Monte-Carlo simulations and demonstrate exact match. Furthermore, we analyze the effect of number of nodes, opportunistic scheduling among $K$ nodes, and $α$-$μ$ parameters on the overall performance of mixed RF/FSO and backup RF systems. Our numerical results illustrate an achievable coding gain when increasing $K$; however, performance degradation occurs as the relay applies selection that favors the domination of specific links in the system.
Attention on Abstract Visual Reasoning
Venue: arXiv cs.LG 2019
Year: 2019

Attention mechanisms have been boosting the performance of deep learning models on a wide range of applications, ranging from speech understanding to program induction. However, despite experiments from psychology which suggest that attention plays an essential role in visual reasoning, the full potential of attention mechanisms has so far not been explored to solve abstract cognitive tasks on image data. In this work, we propose a hybrid network architecture, grounded on self-attention and relational reasoning. We call this new model Attention Relation Network (ARNe). ARNe combines features from the recently introduced Transformer and the Wild Relation Network (WReN). We test ARNe on the Procedurally Generated Matrices (PGMs) datasets for abstract visual reasoning. ARNe excels the WReN model on this task by 11.28 ppt. Relational concepts between objects are efficiently learned demanding only 35% of the training samples to surpass reported accuracy of the base line model. Our proposed hybrid model, represents an alternative on learning abstract relations using self-attention and demonstrates that the Transformer network is also well suited for abstract visual reasoning.
Graph Spanners in the Message-Passing Model
Venue: arXiv cs.DS 2019
Year: 2019

Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative, or both, and many variants of this problem have been extensively studied. We study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites in an arbitrary, possibly worst-case partition, and the goal is for the sites to minimize the communication used to output a spanner. We assume the message-passing model of communication, for which there is a point-to-point link between all pairs of sites as well as a coordinator who is responsible for producing the output. We stress that the subset of edges that each site has is not related to the network topology, which is fixed to be point-to-point. While this model has been extensively studied for related problems such as graph connectivity, it has not been systematically studied for graph spanners. We present the first tradeoffs for total communication versus the quality of the spanners computed, for two or more sites, as well as for additive and multiplicative notions of distortion. We show separations in the communication complexity when edges are allowed to occur on multiple sites, versus when each edge occurs on at most one site. We obtain nearly tight bounds (up to polylog factors) for the communication of additive $2$-spanners in both the with and without duplication models, multiplicative $(2k-1)$-spanners in the with duplication model, and multiplicative $3$ and $5$-spanners in the without duplication model. Our lower bound for multiplicative $3$-spanners employs biregular bipartite graphs rather than the usual Erdős girth conjecture graphs and may be of wider interest.
Efficient ConvNet-based Object Detection for Unmanned Aerial Vehicles by Selective Tile Processing
Venue: arXiv cs.CV 2019
Year: 2019

Many applications utilizing Unmanned Aerial Vehicles (UAVs) require the use of computer vision algorithms to analyze the information captured from their on-board camera. Recent advances in deep learning have made it possible to use single-shot Convolutional Neural Network (CNN) detection algorithms that process the input image to detect various objects of interest. To keep the computational demands low these neural networks typically operate on small image sizes which, however, makes it difficult to detect small objects. This is further emphasized when considering UAVs equipped with cameras where due to the viewing range, objects tend to appear relatively small. This paper therefore, explores the trade-offs involved when maintaining the resolution of the objects of interest by extracting smaller patches (tiles) from the larger input image and processing them using a neural network. Specifically, we introduce an attention mechanism to focus on detecting objects only in some of the tiles and a memory mechanism to keep track of information for tiles that are not processed. Through the analysis of different methods and experiments we show that by carefully selecting which tiles to process we can considerably improve the detection accuracy while maintaining comparable performance to CNNs that resize and process a single image which makes the proposed approach suitable for UAV applications.