OpenRaiser/Intern-Atlas huggingface dataset:
A Distributionally Robust Optimization Method for Adversarial Multiple Kernel Learning
Venue: arXiv cs.LG 2021
Year: 2021

We propose a novel data-driven method to learn a mixture of multiple kernels with random features that is certifiabaly robust against adverserial inputs. Specifically, we consider a distributionally robust optimization of the kernel-target alignment with respect to the distribution of training samples over a distributional ball defined by the Kullback-Leibler (KL) divergence. The distributionally robust optimization problem can be recast as a min-max optimization whose objective function includes a log-sum term. We develop a mini-batch biased stochastic primal-dual proximal method to solve the min-max optimization. To debias the minibatch algorithm, we use the Gumbel perturbation technique to estimate the log-sum term. We establish theoretical guarantees for the performance of the proposed multiple kernel learning method. In particular, we prove the consistency, asymptotic normality, stochastic equicontinuity, and the minimax rate of the empirical estimators. In addition, based on the notion of Rademacher and Gaussian complexities, we establish distributionally robust generalization bounds that are tighter than previous known bounds. More specifically, we leverage matrix concentration inequalities to establish distributionally robust generalization bounds. We validate our kernel learning approach for classification with the kernel SVMs on synthetic dataset generated by sampling multvariate Gaussian distributions with differernt variance structures. We also apply our kernel learning approach to the MNIST data-set and evaluate its robustness to perturbation of input images under different adversarial models. More specifically, we examine the robustness of the proposed kernel model selection technique against FGSM, PGM, C\&W, and DDN adversarial perturbations, and compare its performance with alternative state-of-the-art multiple kernel learning paradigms.
Reconfiguration of Connected Graph Partitions
Venue: arXiv cs.DM 2021
Year: 2021

Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $k\geq 1$, a $k$-district map of $G$ is a partition of $V(G)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is NP-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial length is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that takes a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.
Semi-supervised GANs to Infer Travel Modes in GPS Trajectories
Venue: arXiv cs.LG 2021
Year: 2021

Semi-supervised Generative Adversarial Networks (GANs) are developed in the context of travel mode inference with uni-dimensional smartphone trajectory data. We use data from a large-scale smartphone travel survey in Montreal, Canada. We convert GPS trajectories into fixed-sized segments with five channels (variables). We develop different GANs architectures and compare their prediction results with Convolutional Neural Networks (CNNs). The best semi-supervised GANs model led to a prediction accuracy of 83.4%, while the best CNN model was able to achieve the prediction accuracy of 81.3%. The results compare favorably with previous studies, especially when taking the large-scale real-world nature of the dataset into account.
Meta Dynamic Pricing: Transfer Learning Across Experiments
Venue: arXiv cs.LG 2021
Year: 2021

We study the problem of learning shared structure \emph{across} a sequence of dynamic pricing experiments for related products. We consider a practical formulation where the unknown demand parameters for each product come from an unknown distribution (prior) that is shared across products. We then propose a meta dynamic pricing algorithm that learns this prior online while solving a sequence of Thompson sampling pricing experiments (each with horizon $T$) for $N$ different products. Our algorithm addresses two challenges: (i) balancing the need to learn the prior (\emph{meta-exploration}) with the need to leverage the estimated prior to achieve good performance (\emph{meta-exploitation}), and (ii) accounting for uncertainty in the estimated prior by appropriately "widening" the estimated prior as a function of its estimation error. We introduce a novel prior alignment technique to analyze the regret of Thompson sampling with a mis-specified prior, which may be of independent interest. Unlike prior-independent approaches, our algorithm's meta regret grows sublinearly in $N$, demonstrating that the price of an unknown prior in Thompson sampling can be negligible in experiment-rich environments (large $N$). Numerical experiments on synthetic and real auto loan data demonstrate that our algorithm significantly speeds up learning compared to prior-independent algorithms.
Representing Continuous Functions between Greatest Fixed Points of Indexed Containers
Venue: arXiv cs.LO 2021
Year: 2021

We describe a way to represent computable functions between coinductive types as particular transducers in type theory. This generalizes earlier work on functions between streams by P. Hancock to a much richer class of coinductive types. Those transducers can be defined in dependent type theory without any notion of equality but require inductive-recursive definitions. Most of the properties of these constructions only rely on a mild notion of equality (intensional equality) and can thus be formalized in the dependently typed language Agda.
Efficient Reinforcement Learning for StarCraft by Abstract Forward Models and Transfer Learning
Venue: arXiv cs.LG 2021
Year: 2021

Injecting human knowledge is an effective way to accelerate reinforcement learning (RL). However, these methods are underexplored. This paper presents our discovery that an abstract forward model (thought-game (TG)) combined with transfer learning (TL) is an effective way. We take StarCraft II as our study environment. With the help of a designed TG, the agent can learn a 99% win-rate on a 64x64 map against the Level-7 built-in AI, using only 1.08 hours in a single commercial machine. We also show that the TG method is not as restrictive as it was thought to be. It can work with roughly designed TGs, and can also be useful when the environment changes. Comparing with previous model-based RL, we show TG is more effective. We also present a TG hypothesis that gives the influence of different fidelity levels of TG. For real games that have unequal state and action spaces, we proposed a novel XfrNet of which usefulness is validated while achieving a 90% win-rate against the cheating Level-10 AI. We argue that the TG method might shed light on further studies of efficient RL with human knowledge.
A Simple Solution to the Level-Ancestor Problem
Venue: arXiv cs.DS 2021
Year: 2021

A Level Ancestory query LA($u$, $d$) asks for the the ancestor of the node $u$ at a depth $d$. We present a simple solution, which pre-processes the tree in $O(n)$ time with $O(n)$ extra space, and answers the queries in $O(\log\ {n})$ time. Though other optimal algorithms exist, this is a simple enough solution that could be taught and implemented easily.
Sign Patterns of Inverse Doubly-Nonnegative Matrices
Venue: arXiv cs.SY 2021
Year: 2021

The sign patterns of inverse doubly-nonnegative matrices are examined. A necessary and sufficient condition is developed for a sign matrix to correspond to an inverse doubly-nonnegative matrix. In addition, for a doubly-nonnegative matrix whose graph is a tree, the inverse is shown to have a unique sign pattern, which can be expressed in terms of a two-coloring of the graph.
Incentives in Ethereum's Hybrid Casper Protocol
Venue: arXiv cs.CR 2021
Year: 2021

We present an overview of hybrid Casper the Friendly Finality Gadget (FFG): a Proof-of-Stake checkpointing protocol overlaid onto Ethereum's Proof-of-Work blockchain. We describe its core functionalities and reward scheme, and explore its properties. Our findings indicate that Casper's implemented incentives mechanism ensures liveness, while providing safety guarantees that improve over standard Proof-of-Work protocols. Based on a minimal-impact implementation of the protocol as a smart contract on the blockchain, we discuss additional issues related to parametrisation, funding, throughput and network overhead and detect potential limitations.
Polynomial analogue of Gandhi's fixed point theorem
Venue: arXiv cs.CC 2021
Year: 2021

The problem to be solved in this paper is to construct a general method of proving whether a certain set is p-computable or not. The method is based on a polynomial analogue of the classical Gandhi's fixed point theorem. The classical Gandhi theorem uses the extension of the predicate with the help of the special operator $Γ^{Ω^*}_{Φ(x)}$ whose smallest fixed point is the $Σ$-set. The work uses a new type of operator - $Δ_0^p$-operator $Γ_{F_{P_1^{+}},...,F_{P_n^{+}}}^{\mathfrak{M}}$, which extends predicates so that the smallest fixed point remains a p-computable set. Moreover, if in the classical Gandhi's fixed point theorem the special $Σ$-formula $Φ(\overline {x})$ is used in the construction of the operator, then in the new operator, instead of a single formula, special generating families of formulas $F_ {P_1 ^ {+}},...,F_{P_n^{+}}$. This work opens up broad prospects for the application of the polynomial analogue of the Gandhi theorem in the construction of new types of terms and formulas, in the construction of new data types and programs of polynomial computational complexity in Turing complete languages.
Quantum Relational Hoare Logic with Expectations
Venue: arXiv cs.LO 2021
Year: 2021

We present a variant of the quantum relational Hoare logic from (Unruh, POPL 2019) that allows us to use "expectations" in pre- and postconditions. That is, when reasoning about pairs of programs, our logic allows us to quantitatively reason about how much certain pre-/postconditions are satisfied that refer to the relationship between the programs inputs/outputs.
Data-driven Prognostics with Predictive Uncertainty Estimation using Ensemble of Deep Ordinal Regression Models
Venue: arXiv cs.LG 2021
Year: 2021

Prognostics or Remaining Useful Life (RUL) Estimation from multi-sensor time series data is useful to enable condition-based maintenance and ensure high operational availability of equipment. We propose a novel deep learning based approach for Prognostics with Uncertainty Quantification that is useful in scenarios where: (i) access to labeled failure data is scarce due to rarity of failures (ii) future operational conditions are unobserved and (iii) inherent noise is present in the sensor readings. All three scenarios mentioned are unavoidable sources of uncertainty in the RUL estimation process often resulting in unreliable RUL estimates. To address (i), we formulate RUL estimation as an Ordinal Regression (OR) problem, and propose LSTM-OR: deep Long Short Term Memory (LSTM) network based approach to learn the OR function. We show that LSTM-OR naturally allows for incorporation of censored operational instances in training along with the failed instances, leading to more robust learning. To address (ii), we propose a simple yet effective approach to quantify predictive uncertainty in the RUL estimation models by training an ensemble of LSTM-OR models. Through empirical evaluation on C-MAPSS turbofan engine benchmark datasets, we demonstrate that LSTM-OR is significantly better than the commonly used deep metric regression based approaches for RUL estimation, especially when failed training instances are scarce. Further, our uncertainty quantification approach yields high quality predictive uncertainty estimates while also leading to improved RUL estimates compared to single best LSTM-OR models.
Small Data Challenges in Big Data Era: A Survey of Recent Progress on Unsupervised and Semi-Supervised Methods
Venue: arXiv cs.CV 2021
Year: 2021

Representation learning with small labeled data have emerged in many problems, since the success of deep neural networks often relies on the availability of a huge amount of labeled data that is expensive to collect. To address it, many efforts have been made on training sophisticated models with few labeled data in an unsupervised and semi-supervised fashion. In this paper, we will review the recent progresses on these two major categories of methods. A wide spectrum of models will be categorized in a big picture, where we will show how they interplay with each other to motivate explorations of new ideas. We will review the principles of learning the transformation equivariant, disentangled, self-supervised and semi-supervised representations, all of which underpin the foundation of recent progresses. Many implementations of unsupervised and semi-supervised generative models have been developed on the basis of these criteria, greatly expanding the territory of existing autoencoders, generative adversarial nets (GANs) and other deep networks by exploring the distribution of unlabeled data for more powerful representations. We will discuss emerging topics by revealing the intrinsic connections between unsupervised and semi-supervised learning, and propose in future directions to bridge the algorithmic and theoretical gap between transformation equivariance for unsupervised learning and supervised invariance for supervised learning, and unify unsupervised pretraining and supervised finetuning. We will also provide a broader outlook of future directions to unify transformation and instance equivariances for representation learning, connect unsupervised and semi-supervised augmentations, and explore the role of the self-supervised regularization for many learning problems.
Pebble Exchange Group of Graphs
Venue: arXiv cs.DM 2021
Year: 2021

A graph puzzle ${\rm Puz}(G)$ of a graph $G$ is defined as follows. A configuration of ${\rm Puz}(G)$ is a bijection from the set of vertices of a board graph to the set of vertices of a pebble graph, both graphs being isomorphic to some input graph $G$. A move of pebbles is defined as exchanging two pebbles which are adjacent on both a board graph and a pebble graph. For a pair of configurations $f$ and $g$, we say that $f$ is equivalent to $g$ if $f$ can be transformed into $g$ by a finite sequence of moves. Let ${\rm Aut}(G)$ be the automorphism group of $G$, and let ${\rm 1}_G$ be the unit element of ${\rm Aut}(G)$. The pebble exchange group of $G$, denoted by ${\rm Peb}(G)$, is defined as the set of all automorphisms $f$ of $G$ such that ${\rm 1}_G$ and $f$ are equivalent to each other. In this paper, some basic properties of ${\rm Peb}(G)$ are studied. Among other results, it is shown that for any connected graph $G$, all automorphisms of $G$ are contained in ${\rm Peb}(G^2)$, where $G^2$ is a square graph of $G$.
Performance Analysis of Active Large Intelligent Surfaces (LISs): Uplink Spectral Efficiency and Pilot Training
Venue: arXiv cs.IT 2021
Year: 2021

Large intelligent surfaces (LISs) constitute a new and promising wireless communication paradigm that relies on the integration of a massive number of antenna elements over the entire surfaces of man-made structures. The LIS concept provides many advantages, such as the capability to provide reliable and space-intensive communications by effectively establishing line-of-sight (LOS) channels. In this paper, the system spectral efficiency (SSE) of an uplink LIS system is asymptotically analyzed under a practical LIS environment with a well-defined uplink frame structure. In order to verify the impact on the SSE of pilot contamination, the SSE of a multi-LIS system is asymptotically studied and a theoretical bound on its performance is derived. Given this performance bound, an optimal pilot training length for multi-LIS systems subjected to pilot contamination is characterized and, subsequently, the performance-maximizing number of devices that the LIS system must service is derived. Simulation results show that the derived analyses are in close agreement with the exact mutual information in presence of a large number of antennas, and the achievable SSE is limited by the effect of pilot contamination and intra/inter-LIS interference through the LOS path, even if the LIS is equipped with an infinite number of antennas. Additionally, the SSE obtained with the proposed pilot training length and number of scheduled devices is shown to reach the one obtained via a brute-force search for the optimal solution.
Transfer Learning for Clinical Time Series Analysis using Deep Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks have shown promising results for various clinical prediction tasks. However, training deep networks such as those based on Recurrent Neural Networks (RNNs) requires large labeled data, significant hyper-parameter tuning effort and expertise, and high computational resources. In this work, we investigate as to what extent can transfer learning address these issues when using deep RNNs to model multivariate clinical time series. We consider two scenarios for transfer learning using RNNs: i) domain-adaptation, i.e., leveraging a deep RNN - namely, TimeNet - pre-trained for feature extraction on time series from diverse domains, and adapting it for feature extraction and subsequent target tasks in healthcare domain, ii) task-adaptation, i.e., pre-training a deep RNN - namely, HealthNet - on diverse tasks in healthcare domain, and adapting it to new target tasks in the same domain. We evaluate the above approaches on publicly available MIMIC-III benchmark dataset, and demonstrate that (a) computationally-efficient linear models trained using features extracted via pre-trained RNNs outperform or, in the worst case, perform as well as deep RNNs and statistical hand-crafted features based models trained specifically for target task; (b) models obtained by adapting pre-trained models for target tasks are significantly more robust to the size of labeled data compared to task-specific RNNs, while also being computationally efficient. We, therefore, conclude that pre-trained deep models like TimeNet and HealthNet allow leveraging the advantages of deep learning for clinical time series analysis tasks, while also minimize dependence on hand-crafted features, deal robustly with scarce labeled training data scenarios without overfitting, as well as reduce dependence on expertise and resources required to train deep networks from scratch.
Aiming Low Is Harder -- Induction for Lower Bounds in Probabilistic Program Verification
Venue: arXiv cs.LO 2021
Year: 2021

We present a new inductive rule for verifying lower bounds on expected values of random variables after execution of probabilistic loops as well as on their expected runtimes. Our rule is simple in the sense that loop body semantics need to be applied only finitely often in order to verify that the candidates are indeed lower bounds. In particular, it is not necessary to find the limit of a sequence as in many previous rules.
Air Taxi Skyport Location Problem for Airport Access
Venue: arXiv cs.AI 2021
Year: 2021

Witnessing the rapid progress and accelerated commercialization made in recent years for the introduction of air taxi services in near future across metropolitan cities, our research focuses on one of the most important consideration for such services, i.e., infrastructure planning (also known as skyports). We consider design of skyport locations for air taxis accessing airports, where we present the skyport location problem as a modified single-allocation p-hub median location problem integrating choice-constrained user mode choice behavior into the decision process. Our approach focuses on two alternative objectives i.e., maximizing air taxi ridership and maximizing air taxi revenue. The proposed models in the study incorporate trade-offs between trip length and trip cost based on mode choice behavior of travelers to determine optimal choices of skyports in an urban city. We examine the sensitivity of skyport locations based on two objectives, three air taxi pricing strategies, and varying transfer times at skyports. A case study of New York City is conducted considering a network of 149 taxi zones and 3 airports with over 20 million for-hire-vehicles trip data to the airports to discuss insights around the choice of skyport locations in the city, and demand allocation to different skyports under various parameter settings. Results suggest that a minimum of 9 skyports located between Manhattan, Queens and Brooklyn can adequately accommodate the airport access travel needs and are sufficiently stable against transfer time increases. Findings from this study can help air taxi providers strategize infrastructure design options and investment decisions based on skyport location choices.
Towards annotation-efficient segmentation via image-to-image translation
Venue: arXiv cs.CV 2021
Year: 2021

Often in medical imaging, it is prohibitively challenging to produce enough boundary annotations to train deep neural networks for accurate tumor segmentation. We propose the use of weak labels about whether an image presents tumor or whether it is absent to extend training over images that lack these annotations. Specifically, we propose a semi-supervised framework that employs unpaired image-to-image translation between two domains, presence vs. absence of cancer, as the unsupervised objective. We conjecture that translation helps segmentation -- both require the target to be separated from the background. We encode images into two codes: one that is common to both domains and one that is unique to the presence domain. Decoding from the common code yields healthy images; decoding with the addition of the unique code produces a residual change to this image that adds cancer. Translation proceeds from presence to absence and vice versa. In the first case, the tumor is re-added to the image and we successfully exploit the residual decoder to also perform segmentation. In the second case, unique codes are sampled, producing a distribution of possible tumors. To validate the method, we created challenging synthetic tasks and tumor segmentation datasets from public BRATS (brain, MRI) and LitS (liver, CT) datasets. We show a clear improvement (0.83 Dice on brain, 0.74 on liver) over baseline semi-supervised training with autoencoding (0.73, 0.66) and a mean teacher approach (0.75, 0.69), demonstrating the ability to generalize from smaller distributions of annotated samples.
Modal Logics for Nominal Transition Systems
Venue: arXiv cs.LO 2021
Year: 2021

We define a general notion of transition system where states and action labels can be from arbitrary nominal sets, actions may bind names, and state predicates from an arbitrary logic define properties of states. A Hennessy-Milner logic for these systems is introduced, and proved adequate and expressively complete for bisimulation equivalence. A main technical novelty is the use of finitely supported infinite conjunctions. We show how to treat different bisimulation variants such as early, late, open and weak in a systematic way, explore the folklore theorem that state predicates can be replaced by actions, and make substantial comparisons with related work. The main definitions and theorems have been formalised in Nominal Isabelle.