OpenRaiser/Intern-Atlas huggingface dataset:
Generalization and Regularization in DQN
Venue: arXiv cs.LG 2020
Year: 2020

Deep reinforcement learning algorithms have shown an impressive ability to learn complex control policies in high-dimensional tasks. However, despite the ever-increasing performance on popular benchmarks, policies learned by deep reinforcement learning algorithms can struggle to generalize when evaluated in remarkably similar environments. In this paper we propose a protocol to evaluate generalization in reinforcement learning through different modes of Atari 2600 games. With that protocol we assess the generalization capabilities of DQN, one of the most traditional deep reinforcement learning algorithms, and we provide evidence suggesting that DQN overspecializes to the training environment. We then comprehensively evaluate the impact of dropout and $\ell_2$ regularization, as well as the impact of reusing learned representations to improve the generalization capabilities of DQN. Despite regularization being largely underutilized in deep reinforcement learning, we show that it can, in fact, help DQN learn more general features. These features can be reused and fine-tuned on similar tasks, considerably improving DQN's sample efficiency.
On-line partitioning of width w posets into w^O(log log w) chains
Venue: arXiv cs.DS 2020
Year: 2020

An on-line chain partitioning algorithm receives the elements of a poset one at a time, and when an element is received, irrevocably assigns it to one of the chains. In this paper, we present an on-line algorithm that partitions posets of width $w$ into $w^{O(\log{\log{w}})}$ chains. This improves over previously best known algorithms using $w^{O(\log{w})}$ chains by Bosek and Krawczyk and by Bosek, Kierstead, Krawczyk, Matecki, and Smith. Our algorithm runs in $w^{O(\sqrt{w})}n$ time, where $w$ is the width and $n$ is the size of a presented poset.
Mean Field Control for Efficient Mixing of Energy Loads
Venue: arXiv cs.SY 2020
Year: 2020

We pose an engineering challenge of controlling an Ensemble of Energy Devices via coordinated, implementation-light and randomized on/off switching as a problem in Non-Equilibrium Statistical Mechanics. We show that Mean Field Control} with nonlinear feedback on the cumulative consumption, assumed available to the aggregator via direct physical measurements of the energy flow, allows the ensemble to recover from its use in the Demand Response regime, i.e. transition to a statistical steady state, significantly faster than in the case of the fixed feedback. Moreover when the nonlinearity is sufficiently strong, one observes the phenomenon of "super-relaxation" -- where the total instantaneous energy consumption of the ensemble transitions to the steady state much faster than the underlying probability distribution of the devices over their state space, while also leaving almost no devices outside of the comfort zone.
Variational Discriminator Bottleneck: Improving Imitation Learning, Inverse RL, and GANs by Constraining Information Flow
Venue: arXiv cs.LG 2020
Year: 2020

Adversarial learning methods have been proposed for a wide range of applications, but the training of adversarial models can be notoriously unstable. Effectively balancing the performance of the generator and discriminator is critical, since a discriminator that achieves very high accuracy will produce relatively uninformative gradients. In this work, we propose a simple and general technique to constrain information flow in the discriminator by means of an information bottleneck. By enforcing a constraint on the mutual information between the observations and the discriminator's internal representation, we can effectively modulate the discriminator's accuracy and maintain useful and informative gradients. We demonstrate that our proposed variational discriminator bottleneck (VDB) leads to significant improvements across three distinct application areas for adversarial learning algorithms. Our primary evaluation studies the applicability of the VDB to imitation learning of dynamic continuous control skills, such as running. We show that our method can learn such skills directly from \emph{raw} video demonstrations, substantially outperforming prior adversarial imitation learning methods. The VDB can also be combined with adversarial inverse reinforcement learning to learn parsimonious reward functions that can be transferred and re-optimized in new settings. Finally, we demonstrate that VDB can train GANs more effectively for image generation, improving upon a number of prior stabilization methods.
SVIn2: An Underwater SLAM System using Sonar, Visual, Inertial, and Depth Sensor
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents a novel tightly-coupled keyframe-based Simultaneous Localization and Mapping (SLAM) system with loop-closing and relocalization capabilities targeted for the underwater domain. Our previous work, SVIn, augmented the state-of-the-art visual-inertial state estimation package OKVIS to accommodate acoustic data from sonar in a non-linear optimization-based framework. This paper addresses drift and loss of localization -- one of the main problems affecting other packages in underwater domain -- by providing the following main contributions: a robust initialization method to refine scale using depth measurements, a fast preprocessing step to enhance the image quality, and a real-time loop-closing and relocalization method using bag of words. An additional contribution is the introduction of depth measurements from a pressure sensor to the tightly-coupled optimization formulation. Experimental results on datasets collected with a custom-made underwater sensor suite and an autonomous underwater vehicle from challenging underwater environments with poor visibility demonstrate performance never achieved before in terms of accuracy and robustness.
Performance Guarantees of Distributed Algorithms for QoS in Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2020
Year: 2020

Consider a wireless network where each communication link has a minimum bandwidth quality-of-service requirement. Certain pairs of wireless links interfere with each other due to being in the same vicinity, and this interference is modeled by a conflict graph. Given the conflict graph and link bandwidth requirements, the objective is to determine, using only localized information, whether the demands of all the links can be satisfied. At one extreme, each node knows the demands of only its neighbors; at the other extreme, there exists an optimal, centralized scheduler that has global information. The present work interpolates between these two extremes by quantifying the tradeoff between the degree of decentralization and the performance of the distributed algorithm. This open problem is resolved for the primary interference model, and the following general result is obtained: if each node knows the demands of all links in a ball of radius $d$ centered at the node, then there is a distributed algorithm whose performance is away from that of an optimal, centralized algorithm by a factor of at most $(2d+3)/(2d+2)$. The tradeoff between performance and complexity of the distributed algorithm is also analyzed. It is shown that for line networks under the protocol interference model, the row constraints are a factor of at most $3$ away from optimal. Both bounds are best possible.
Combining Bayesian Optimization and Lipschitz Optimization
Venue: arXiv cs.LG 2020
Year: 2020

Bayesian optimization and Lipschitz optimization have developed alternative techniques for optimizing black-box functions. They each exploit a different form of prior about the function. In this work, we explore strategies to combine these techniques for better global optimization. In particular, we propose ways to use the Lipschitz continuity assumption within traditional BO algorithms, which we call Lipschitz Bayesian optimization (LBO). This approach does not increase the asymptotic runtime and in some cases drastically improves the performance (while in the worst-case the performance is similar). Indeed, in a particular setting, we prove that using the Lipschitz information yields the same or a better bound on the regret compared to using Bayesian optimization on its own. Moreover, we propose a simple heuristics to estimate the Lipschitz constant, and prove that a growing estimate of the Lipschitz constant is in some sense ``harmless''. Our experiments on 15 datasets with 4 acquisition functions show that in the worst case LBO performs similar to the underlying BO method while in some cases it performs substantially better. Thompson sampling in particular typically saw drastic improvements (as the Lipschitz information corrected for its well-known ``over-exploration'' phenomenon) and its LBO variant often outperformed other acquisition functions.
Granularity of wagers in games and the possibility of savings
Venue: arXiv cs.GT 2020
Year: 2020

In a casino where arbitrarily small bets are admissible, any betting strategy M can be modified into a savings strategy that, not only is successful on each casino sequence where M is (thus accumulating unbounded wealth inside the casino) but also saves an unbounded capital, by permanently and gradually withdrawing it from the game. Teutsch showed that this is no longer the case when a fixed minimum wager is imposed by the casino, thus exemplifying a savings paradox where a player can win unbounded wealth inside the casino, but upon withdrawing a sufficiently large amount out of the game, he is forced into bankruptcy. We study the potential for saving under a shrinking minimum wager rule (granularity) and its dependence on the rate of decrease (inflation) as well as timid versus bold play.
A Machine Learning Approach to Persian Text Readability Assessment Using a Crowdsourced Dataset
Venue: arXiv cs.CL 2020
Year: 2020

An automated approach to text readability assessment is essential to a language and can be a powerful tool for improving the understandability of texts written and published in that language. However, the Persian language, which is spoken by over 110 million speakers, lacks such a system. Unlike other languages such as English, French, and Chinese, very limited research studies have been carried out to build an accurate and reliable text readability assessment system for the Persian language. In the present research, the first Persian dataset for text readability assessment was gathered and the first model for Persian text readability assessment using machine learning was introduced. The experiments showed that this model was accurate and could assess the readability of Persian texts with a high degree of confidence. The results of this study can be used in a number of applications such as medical and educational text readability evaluation and have the potential to be the cornerstone of future studies in Persian text readability assessment.
The CoNLL--SIGMORPHON 2018 Shared Task: Universal Morphological Reinflection
Venue: arXiv cs.CL 2020
Year: 2020

The CoNLL--SIGMORPHON 2018 shared task on supervised learning of morphological generation featured data sets from 103 typologically diverse languages. Apart from extending the number of languages involved in earlier supervised tasks of generating inflected forms, this year the shared task also featured a new second task which asked participants to inflect words in sentential context, similar to a cloze task. This second task featured seven languages. Task 1 received 27 submissions and task 2 received 6 submissions. Both tasks featured a low, medium, and high data condition. Nearly all submissions featured a neural component and built on highly-ranked systems from the earlier 2017 shared task. In the inflection task (task 1), 41 of the 52 languages present in last year's inflection task showed improvement by the best systems in the low-resource setting. The cloze task (task 2) proved to be difficult, and few submissions managed to consistently improve upon both a simple neural baseline system and a lemma-repeating baseline.
Autonomous Deep Learning: Continual Learning Approach for Dynamic Environments
Venue: arXiv cs.LG 2020
Year: 2020

The feasibility of deep neural networks (DNNs) to address data stream problems still requires intensive study because of the static and offline nature of conventional deep learning approaches. A deep continual learning algorithm, namely autonomous deep learning (ADL), is proposed in this paper. Unlike traditional deep learning methods, ADL features a flexible structure where its network structure can be constructed from scratch with the absence of an initial network structure via the self-constructing network structure. ADL specifically addresses catastrophic forgetting by having a different-depth structure which is capable of achieving a trade-off between plasticity and stability. Network significance (NS) formula is proposed to drive the hidden nodes growing and pruning mechanism. Drift detection scenario (DDS) is put forward to signal distributional changes in data streams which induce the creation of a new hidden layer. The maximum information compression index (MICI) method plays an important role as a complexity reduction module eliminating redundant layers. The efficacy of ADL is numerically validated under the prequential test-then-train procedure in lifelong environments using nine popular data stream problems. The numerical results demonstrate that ADL consistently outperforms recent continual learning methods while characterizing the automatic construction of network structures.
Adversarial Balancing for Causal Inference
Venue: arXiv cs.LG 2020
Year: 2020

Biases in observational data of treatments pose a major challenge to estimating expected treatment outcomes in different populations. An important technique that accounts for these biases is reweighting samples to minimize the discrepancy between treatment groups. We present a novel reweighting approach that uses bi-level optimization to alternately train a discriminator to minimize classification error, and a balancing weights generator that uses exponentiated gradient descent to maximize this error. This approach borrows principles from generative adversarial networks (GANs) to exploit the power of classifiers for measuring two-sample divergence. We provide theoretical results for conditions in which the estimation error is bounded by two factors: (i) the discrepancy measure induced by the discriminator; and (ii) the weights variability. Experimental results on several benchmarks comparing to previous state-of-the-art reweighting methods demonstrate the effectiveness of this approach in estimating causal effects.
Solving Linear Programs in the Current Matrix Multiplication Time
Venue: arXiv cs.DS 2020
Year: 2020

This paper shows how to solve linear programs of the form $\min_{Ax=b,x\geq0} c^\top x$ with $n$ variables in time $$O^*((n^ω+n^{2.5-α/2}+n^{2+1/6}) \log(n/δ))$$ where $ω$ is the exponent of matrix multiplication, $α$ is the dual exponent of matrix multiplication, and $δ$ is the relative accuracy. For the current value of $ω\sim2.37$ and $α\sim0.31$, our algorithm takes $O^*(n^ω \log(n/δ))$ time. When $ω= 2$, our algorithm takes $O^*(n^{2+1/6} \log(n/δ))$ time. Our algorithm utilizes several new concepts that we believe may be of independent interest: $\bullet$ We define a stochastic central path method. $\bullet$ We show how to maintain a projection matrix $\sqrt{W}A^{\top}(AWA^{\top})^{-1}A\sqrt{W}$ in sub-quadratic time under $\ell_{2}$ multiplicative changes in the diagonal matrix $W$.
Complexity of Computing the Anti-Ramsey Numbers for Paths
Venue: arXiv cs.CC 2020
Year: 2020

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd\" os, Simonovits and S\' os. For given graphs $G$ and $H$ the \emph{anti-Ramsey number} $\textrm{ar}(G,H)$ is defined to be the maximum number $k$ such that there exists an assignment of $k$ colors to the edges of $G$ in which every copy of $H$ in $G$ has at least two edges with the same color. There are works on the computational complexity of the problem when $H$ is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number $\textrm{ar}(G,P_k)$, where $P_k$ is a path of length $k$. First, we observe that when $k = Ω(n)$, the problem is hard; hence, the challenging part is the computational complexity of the problem when $k$ is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing $\textrm{ar}(G,P_k)$ for every integer $k>2$ is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We investigate further and show that approximating $\textrm{ar}(G,P_3)$ to a factor of $n^{-1/2 - ε}$ is hard already in $3$-partite graphs, unless P=NP. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant $k$. Given the hardness of approximation and parametrization of the problem, it is natural to study the problem on restricted graph families. We introduce the notion of color connected coloring and employing this structural property. We obtain a linear time algorithm to compute $\textrm{ar}(G,P_k)$, for every integer $k$, when the host graph, $G$, is a tree.
STAIRoute: Early Global Routing using Monotone Staircases for Congestion Reduction
Venue: arXiv cs.OH 2020
Year: 2020

With aggressively shrinking process nodes, physical design methods face severe challenges due to poor convergence and uncertainty in getting an optimal solution. An early detection of potential failures is thus mandated. This has encouraged to devise a feedback mechanism from a lower abstraction level of the design flow to the higher ones, such as placement driven synthesis, routability (timing) driven placement etc. Motivated by this, we propose an early global routing framework using pattern routing following the floorplanning stage. We assess feasibility of a floorplan topology of a given design by estimating routability, routed wirelength and vias count while addressing the global congestion scenario across the layout. Different capacity profiles for the routing regions, such as uniform or non-uniform different cases of metal pitch variation across the metals layers ensures adaptability to technology scaling. The proposed algorithm STAIRoute takes $O(n^2kt)$ time for a given design with $n$ blocks and $k$ nets having at most $t$ terminals. Experimental results on a set of floorplanning benchmark circuits show $100\%$ routing completion, with no over-congestion in the routing regions reported. The wirelength for the $t$-terminal ($t\geq$ 2) nets is comparable with the Steiner length computed by FLUTE. An estimation on the number of vias for different capacity profiles is also presented, along with congestion and runtime results.
The Second-Price Knapsack Problem: Near-Optimal Real Time Bidding in Internet Advertisement
Venue: arXiv cs.GT 2020
Year: 2020

In many online advertisement (ad) exchanges, ad slots are each sold via a separate second-price auction. This paper considers the bidder's problem of maximizing the value of ads they purchase in these auctions, subject to budget constraints. This 'second-price knapsack' problem presents challenges when devising a bidding strategy because of the uncertain resource consumption: bidders win if they bid the highest amount, but pay the second-highest bid, unknown a priori. This is in contrast to the traditional online knapsack problem, where posted prices are revealed when ads arrive, and for which there exists a rich literature of primal and dual algorithms. The main results of this paper establish general methods for adapting these primal and dual online knapsack selection algorithms to the second-price knapsack problem, where the prices are revealed only after bidding. In particular, a methodology is provided for converting deterministic and randomized knapsack selection algorithms into second-price knapsack bidding strategies, that purchase ads through an equivalent set of criteria and thereby achieve the same competitive guarantees. This shows a connection between the traditional knapsack selection algorithm and second-price auction bidding algorithms, that has not previously been leveraged. Empirical analysis on real ad exchange data verifies the usefulness of this method, and gives examples where it can outperform state-of-the-art techniques.
UniMorph 2.0: Universal Morphology
Venue: arXiv cs.CL 2020
Year: 2020

The Universal Morphology UniMorph project is a collaborative effort to improve how NLP handles complex morphology across the world's languages. The project releases annotated morphological data using a universal tagset, the UniMorph schema. Each inflected form is associated with a lemma, which typically carries its underlying lexical meaning, and a bundle of morphological features from our schema. Additional supporting data and tools are also released on a per-language basis when available. UniMorph is based at the Center for Language and Speech Processing (CLSP) at Johns Hopkins University in Baltimore, Maryland and is sponsored by the DARPA LORELEI program. This paper details advances made to the collection, annotation, and dissemination of project resources since the initial UniMorph release described at LREC 2016. lexical resources} }
A Faster-Than Relation for Semi-Markov Decision Processes
Venue: arXiv cs.FL 2020
Year: 2020

When modeling concurrent or cyber-physical systems, non-functional requirements such as time are important to consider. In order to improve the timing aspects of a model, it is necessary to have some notion of what it means for a process to be faster than another, which can guide the stepwise refinement of the model. To this end we study a faster-than relation for semi-Markov decision processes and compare it to standard notions for relating systems. We consider the compositional aspects of this relation, and show that the faster-than relation is not a precongruence with respect to parallel composition, hence giving rise to so-called parallel timing anomalies. We take the first steps toward understanding this problem by identifying decidable conditions sufficient to avoid parallel timing anomalies in the absence of non-determinism.
Efficient and Trustworthy Social Navigation Via Explicit and Implicit Robot-Human Communication
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present a planning framework that uses a combination of implicit (robot motion) and explicit (visual/audio/haptic feedback) communication during mobile robot navigation. First, we developed a model that approximates both continuous movements and discrete behavior modes in human navigation, considering the effects of implicit and explicit communication on human decision making. The model approximates the human as an optimal agent, with a reward function obtained through inverse reinforcement learning. Second, a planner uses this model to generate communicative actions that maximize the robot's transparency and efficiency. We implemented the planner on a mobile robot, using a wearable haptic device for explicit communication. In a user study of an indoor human-robot pair of orthogonal crossing situation, the robot was able to actively communicate its intent to users in order to avoid collisions and facilitate efficient trajectories. Results showed that the planner generated plans that were easier to understand, reduced users' effort, and increased users' trust of the robot, compared to simply performing collision avoidance. The key contribution of this work is the integration and analysis of explicit communication (together with implicit communication) for social navigation.