OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Dynamic Games in Belief Space
Venue: arXiv cs.RO 2021
Year: 2021

Information gathering while interacting with other agents under sensing and motion uncertainty is critical in domains such as driving, service robots, racing, or surveillance. The interests of agents may be at odds with others, resulting in a stochastic non-cooperative dynamic game. Agents must predict others' future actions without communication, incorporate their actions into these predictions, account for uncertainty and noise in information gathering, and consider what information their actions reveal. Our solution uses local iterative dynamic programming in Gaussian belief space to solve a game-theoretic continuous POMDP. Solving a quadratic game in the backward pass of a game-theoretic belief-space variant of iLQG achieves a runtime polynomial in the number of agents and linear in the planning horizon. Our algorithm yields linear feedback policies for our robot, and predicted feedback policies for other agents. We present three applications: active surveillance, guiding eyes for a blind agent, and autonomous racing. Agents with game-theoretic belief-space planning win 44% more races than without game theory and 34% more than without belief-space planning.
Meta-Learning for Few-Shot Time Series Classification
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks (DNNs) have achieved state-of-the-art results on time series classification (TSC) tasks. In this work, we focus on leveraging DNNs in the often-encountered practical scenario where access to labeled training data is difficult, and where DNNs would be prone to overfitting. We leverage recent advancements in gradient-based meta-learning, and propose an approach to train a residual neural network with convolutional layers as a meta-learning agent for few-shot TSC. The network is trained on a diverse set of few-shot tasks sampled from various domains (e.g. healthcare, activity recognition, etc.) such that it can solve a target task from another domain using only a small number of training samples from the target task. Most existing meta-learning approaches are limited in practice as they assume a fixed number of target classes across tasks. We overcome this limitation in order to train a common agent across domains with each domain having different number of target classes, we utilize a triplet-loss based learning procedure that does not require any constraints to be enforced on the number of classes for the few-shot TSC tasks. To the best of our knowledge, we are the first to use meta-learning based pre-training for TSC. Our approach sets a new benchmark for few-shot TSC, outperforming several strong baselines on few-shot tasks sampled from 41 datasets in UCR TSC Archive. We observe that pre-training under the meta-learning paradigm allows the network to quickly adapt to new unseen tasks with small number of labeled instances.
Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
Venue: arXiv cs.GT 2021
Year: 2021

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a $(ϕ-1)$-approximation of envy-freeness up to any good (EFX) and a $\frac{2}{ϕ+2}$-approximation of groupwise maximin share fairness (GMMS), where $ϕ$ is the golden ratio ($ϕ\approx 1.618$). The best known approximation factor for either one of these fairness notions prior to this work was $1/2$. Moreover, the returned allocation achieves envy-freeness up to one good (EF1) and a $2/3$-approximation of pairwise maximin share fairness (PMMS). While EFX is our primary focus, we also exhibit how to fine-tune our algorithm and improve the guarantees for GMMS or PMMS. Finally, we show that GMMS -- and thus PMMS and EFX -- allocations always exist when the number of goods does not exceed the number of agents by more than two.
k-Relevance Vectors: Considering Relevancy Beside Nearness
Venue: arXiv cs.LG 2021
Year: 2021

This study combines two different learning paradigms, k-nearest neighbor (k-NN) rule, as memory-based learning paradigm and relevance vector machines (RVM), as statistical learning paradigm. This combination is performed in kernel space and is called k-relevance vector (k-RV). The purpose is to improve the performance of k-NN rule. The proposed model significantly prunes irrelevant attributes. We also introduced a new parameter, responsible for early stopping of iterations in RVM. We show that the new parameter improves the classification accuracy of k-RV. Intensive experiments are conducted on several classification datasets from University of California Irvine (UCI) repository and two real datasets from computer vision domain. The performance of k-RV is highly competitive compared to a few state-of-the-arts in terms of classification accuracy.
Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
Venue: arXiv cs.LG 2021
Year: 2021

Improving the sample efficiency in reinforcement learning has been a long-standing research problem. In this work, we aim to reduce the sample complexity of existing policy gradient methods. We propose a novel policy gradient algorithm called SRVR-PG, which only requires $O(1/ε^{3/2})$ episodes to find an $ε$-approximate stationary point of the nonconcave performance function $J(\boldsymbolθ)$ (i.e., $\boldsymbolθ$ such that $\|\nabla J(\boldsymbolθ)\|_2^2\leqε$). This sample complexity improves the existing result $O(1/ε^{5/3})$ for stochastic variance reduced policy gradient algorithms by a factor of $O(1/ε^{1/6})$. In addition, we also propose a variant of SRVR-PG with parameter exploration, which explores the initial policy parameter from a prior probability distribution. We conduct numerical experiments on classic control problems in reinforcement learning to validate the performance of our proposed algorithms.
Voting with Random Classifiers (VORACE): Theoretical and Experimental Analysis
Venue: arXiv cs.LG 2021
Year: 2021

In many machine learning scenarios, looking for the best classifier that fits a particular dataset can be very costly in terms of time and resources. Moreover, it can require deep knowledge of the specific domain. We propose a new technique which does not require profound expertise in the domain and avoids the commonly used strategy of hyper-parameter tuning and model selection. Our method is an innovative ensemble technique that uses voting rules over a set of randomly-generated classifiers. Given a new input sample, we interpret the output of each classifier as a ranking over the set of possible classes. We then aggregate these output rankings using a voting rule, which treats them as preferences over the classes. We show that our approach obtains good results compared to the state-of-the-art, both providing a theoretical analysis and an empirical evaluation of the approach on several datasets.
Structured Discrete Shape Approximation: Theoretical Complexity and Practical Algorithm
Venue: arXiv cs.CG 2021
Year: 2021

We consider the problem of approximating a two-dimensional shape contour (or curve segment) using discrete assembly systems, which allow to build geometric structures based on limited sets of node and edge types subject to edge length and orientation restrictions. We show that already deciding feasibility of such approximation problems is NP-hard, and remains intractable even for very simple setups. We then devise an algorithmic framework that combines shape sampling with exact cardinality-minimization to obtain good approximations using few components. As a particular application and showcase example, we discuss approximating shape contours using the classical Zometool construction kit and provide promising computational results, demonstrating that our algorithm is capable of obtaining good shape representations within reasonable time, in spite of the problem's general intractability. We conclude the paper with an outlook on possible extensions of the developed methodology, in particular regarding 3D shape approximation tasks.
Redirection Controller Using Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

There is a growing demand for redirected walking (RDW) techniques and their application. To apply appropriate RDW methods and manipulation, the RDW controllers are predominantly used. There are three types of RDW controllers: direct scripted controller, generalized controller, and predictive controller. The scripted controller type pre-scripts the mapping between the real and virtual environments. The generalized controller type employs the RDW method and manipulation quantities according to a certain procedure depending on the user's position in relation to the real space. This approach has the potential to be reused in any environment; however, it is not fully optimized. The predictive controller type predicts the user's future path using the user's behavior and manages RDW techniques. This approach is highly anticipated to be very effective and versatile; however, it has not been sufficiently developed. This paper proposes a novel RDW controller using reinforcement learning (RL) with advanced plannability/versatility. Our simulation experiments indicate that the proposed method can reduce the number of reset manipulations, which is one of the indicators of the effectiveness of the RDW controller, compared to the generalized controller under real environments with many obstacles. Meanwhile, the experimental results also showed that the gain output by the proposed method oscillates. The results of a user study conducted showed that the proposed RDW controller can reduce the number of resets compared to the conventional generalized controller. Furthermore, no adverse effects such as cybersickness associated with the oscillation of the output gain were evinced. The simulation and user studies demonstrate that the proposed RDW controller with RL outperforms the existing generalized controllers and can be applied to users.
Multithreaded Filtering Preconditioner for Diffusion Equation on Structured Grid
Venue: arXiv cs.DC 2021
Year: 2021

A parallel and nested version of a frequency filtering preconditioner is proposed for linear systems corresponding to diffusion equation on a structured grid. The proposed preconditioner is found to be robust with respect to jumps in the diffusion coefficients. The storage requirement for the preconditioner is O(N),where N is number of rows of matrix, hence, a fairly large problem of size more than 42 million unknowns has been solved on a quad core machine with 64GB RAM. The parallelism is achieved using twisted factorization and SIMD operations. The preconditioner achieves a speedup of 3.3 times on a quad core processor clocked at 4.2 GHz, and compared to a well known algebraic multigrid method, it is significantly faster in both setup and solve times for diffusion equations with jumps.
Backpressure Flow Control
Venue: arXiv cs.NI 2021
Year: 2021

Effective congestion control for data center networks is becoming increasingly challenging with a growing amount of latency sensitive traffic, much fatter links, and extremely bursty traffic. Widely deployed algorithms, such as DCTCP and DCQCN, are still far from optimal in many plausible scenarios, particularly for tail latency. Many operators compensate by running their networks at low average utilization, dramatically increasing costs. In this paper, we argue that we have reached the practical limits of end-to-end congestion control. Instead, we propose, implement, and evaluate a new congestion control architecture called Backpressure Flow Control (BFC). BFC provides per-hop per-flow flow control, but with bounded state, constant-time switch operations, and careful use of buffers. We demonstrate BFC's feasibility by implementing it on Tofino2, a state-of-the-art P4-based programmable hardware switch. In simulation, we show that BFC achieves near optimal throughput and tail latency behavior even under challenging conditions such as high network load and incast cross traffic. Compared to existing end-to-end schemes, BFC achieves 2.3 - 60 X lower tail latency for short flows and 1.6 - 5 X better average completion time for long flows.
Matching Embeddings for Domain Adaptation
Venue: arXiv cs.LG 2021
Year: 2021

In this work we address the problem of transferring knowledge obtained from a vast annotated source domain to a low labeled target domain. We propose Adversarial Variational Domain Adaptation (AVDA), a semi-supervised domain adaptation method based on deep variational embedded representations. We use approximate inference and domain adversarial methods to map samples from source and target domains into an aligned class-dependent embedding defined as a Gaussian Mixture Model. AVDA works as a classifier and considers a generative model that helps this classification. We used digits dataset for experimentation. Our results show that on a semi-supervised few-shot scenario our model outperforms previous methods in most of the adaptation tasks, even using a fewer number of labeled samples per class on target domain.
Cut-and-Paste Dataset Generation for Balancing Domain Gaps in Object Instance Detection
Venue: arXiv cs.RO 2021
Year: 2021

Training an object instance detector where only a few training object images are available is a challenging task. One solution is a cut-and-paste method that generates a training dataset by cutting object areas out of training images and pasting them onto other background images. A detector trained on a dataset generated with a cut-and-paste method suffers from the conventional domain shift problem, which stems from a discrepancy between the source domain (generated training dataset) and the target domain (real test dataset). Though state-of-the-art domain adaptation methods are able to reduce this gap, it is limited because they do not consider the difference of domain gaps of foreground and background. In this study, we present that the conventional domain gap can be divided into two sub-domain gaps for foreground and background. Then, we show that the original cut-and-paste approach suffers from a new domain gap problem, an unbalanced domain gaps, because it has two separate source domains for foreground and background, unlike the conventional domain shift problem. Then, we introduce an advanced cut-and-paste method to balance the unbalanced domain gaps by diversifying the foreground with GAN (generative adversarial network)-generated seed images and simplifying the background using image processing techniques. Experimental results show that our method is effective for balancing domain gaps and improving the accuracy of object instance detection in a cluttered indoor environment using only a few seed images. Furthermore, we show that balancing domain gaps can improve the detection accuracy of state-of-the-art domain adaptation methods.
Adaptive Binary-Ternary Quantization
Venue: arXiv cs.LG 2021
Year: 2021

Neural network models are resource hungry. It is difficult to deploy such deep networks on devices with limited resources, like smart wearables, cellphones, drones, and autonomous vehicles. Low bit quantization such as binary and ternary quantization is a common approach to alleviate this resource requirements. Ternary quantization provides a more flexible model and outperforms binary quantization in terms of accuracy, however doubles the memory footprint and increases the computational cost. Contrary to these approaches, mixed quantized models allow a trade-off between accuracy and memory footprint. In such models, quantization depth is often chosen manually, or is tuned using a separate optimization routine. The latter requires training a quantized network multiple times. Here, we propose an adaptive combination of binary and ternary quantization, namely Smart Quantization (SQ), in which the quantization depth is modified directly via a regularization function, so that the model is trained only once. Our experimental results show that the proposed method adapts quantization depth successfully while keeping the model accuracy high on MNIST and CIFAR10 benchmarks.
Comment on "$Φ$ memristor: Real memristor found" by F. Z. Wang, L. Li, L. Shi, H. Wu, and L. O. Chua [J. Appl. Phys. 125, 054504 (2019)]
Venue: arXiv cs.ET 2021
Year: 2021

Wang et al. claim [J. Appl. Phys. 125, 054504 (2019)] that a current-carrying wire interacting with a magnetic core represents a memristor. Here, we demonstrate that this claim is false. We first show that such memristor "discovery" is based on incorrect physics, which does not even capture basic properties of magnetic core materials, such as their magnetic hysteresis. Moreover, the predictions of Wang et al.'s model contradict the experimental curves presented in their paper. Additionally, the theoretical pinched hysteresis loops presented by Wang et al. can not be reproduced if their model is used, and there are serious flaws in their "negative memristor" emulator design. Finally, a simple gedanken experiment shows that the proposed $Φ$-memristor would fail the memristor test we recently suggested in J. Phys. D: Appl. Phys. 52, 01LT01 (2019). The device "discovered" by Wang et al. is just an inductor with memory.
Beating humans in a penny-matching game by leveraging cognitive hierarchy theory and Bayesian learning
Venue: arXiv cs.AI 2021
Year: 2021

It is a long-standing goal of artificial intelligence (AI) to be superior to human beings in decision making. Games are suitable for testing AI capabilities of making good decisions in non-numerical tasks. In this paper, we develop a new AI algorithm to play the penny-matching game considered in Shannon's "mind-reading machine" (1953) against human players. In particular, we exploit cognitive hierarchy theory and Bayesian learning techniques to continually evolve a model for predicting human player decisions, and let the AI player make decisions according to the model predictions to pursue the best chance of winning. Experimental results show that our AI algorithm beats 27 out of 30 volunteer human players.
Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem
Venue: arXiv cs.IT 2021
Year: 2021

We establish fundamental limits on estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true locations of a target over a unit cube, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution to estimate the target location. Furthermore, applying the Berry--Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint. We specialize our second-order results to measurement-dependent versions of several channel models including the binary symmetric, the binary erasure and the binary Z- channels. The theory is extended to simultaneous searching for multiple targets. As a complement, we establish a second-order asymptotic achievability bound for adaptive querying and use this to bound the benefit of adaptive querying.
$r$-wise fractional $L$-intersecting family
Venue: arXiv cs.DM 2021
Year: 2021

Let $L = \{\frac{a_1}{b_1}, \ldots , \frac{a_s}{b_s}\}$, where for every $i \in [s]$, $\frac{a_i}{b_i} \in [0,1)$ is an irreducible fraction. Let $\mathcal{F} = \{A_1, \ldots , A_m\}$ be a family of subsets of $[n]$. We say $\mathcal{F}$ is a \emph{r-wise fractional $L$-intersecting family} if for every distinct $i_1,i_2, \ldots,i_r \in [m]$, there exists an $\frac{a}{b} \in L$ such that $|A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_r}| \in \{ \frac{a}{b}|A_{i_1}|, \frac{a}{b} |A_{i_2}|,\ldots, \frac{a}{b} |A_{i_r}| \}$. In this paper, we introduce and study the notion of r-wise fractional $L$-intersecting families. This is a generalization of notion of fractional $L$-intersecting families studied in [Niranjan et.al, Fractional $L$-intersecting families, The Electronic Journal of Combinatorics, 2019].
Identifying supportive student factors for mindset interventions: A two-model machine learning approach
Venue: arXiv cs.CY 2021
Year: 2021

Growth mindset interventions foster students' beliefs that their abilities can grow through effort and appropriate strategies. However, not every student benefits from such interventions - yet research identifying which student factors support growth mindset interventions is sparse. In this study, we utilized machine learning methods to predict growth mindset effectiveness in a nationwide experiment in the U.S. with over 10,000 students. These methods enable analysis of arbitrarily-complex interactions between combinations of student-level predictor variables and intervention outcome, defined as the improvement in grade point average (GPA) during the transition to high school. We utilized two separate machine learning models: one to control for complex relationships between 51 student-level predictors and GPA, and one to predict the change in GPA due to the intervention. We analyzed the trained models to discover which features influenced model predictions most, finding that prior academic achievement, blocked navigations (attempting to navigate through the intervention software too quickly), self-reported reasons for learning, and race/ethnicity were the most important predictors in the model for predicting intervention effectiveness. As in previous research, we found that the intervention was most effective for students with prior low academic achievement. Unique to this study, we found that blocked navigations predicted an intervention effect as low as 0.185 GPA points (on a 0-4 scale) less than the mean. This was a notable negative prediction given that the mean intervention effect in our sample was just 0.026 GPA points, though few students (4.4%) experienced a substantial number of blocked navigation events. We also found that some minoritized students were predicted to benefit less (or even not at all) from the intervention.
Learning Maximally Predictive Prototypes in Multiple Instance Learning
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we propose a simple model that provides permutation invariant maximally predictive prototype generator from a given dataset, which leads to interpretability of the solution and concrete insights to the nature and the solution of a problem. Our aim is to find out prototypes in the feature space to map the collection of instances (i.e. bags) to a distance feature space and simultaneously learn a linear classifier for multiple instance learning (MIL). Our experiments on classical MIL benchmark datasets demonstrate that proposed framework is an accurate and efficient classifier compared to the existing approaches.