OpenRaiser/Intern-Atlas huggingface dataset:
Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learning
Venue: arXiv cs.AI 2020
Year: 2020

Morpion Solitaire is a popular single player game, performed with paper and pencil. Due to its large state space (on the order of the game of Go) traditional search algorithms, such as MCTS, have not been able to find good solutions. A later algorithm, Nested Rollout Policy Adaptation, was able to find a new record of 82 steps, albeit with large computational resources. After achieving this record, to the best of our knowledge, there has been no further progress reported, for about a decade. In this paper we take the recent impressive performance of deep self-learning reinforcement learning approaches from AlphaGo/AlphaZero as inspiration to design a searcher for Morpion Solitaire. A challenge of Morpion Solitaire is that the state space is sparse, there are few win/loss signals. Instead, we use an approach known as ranked reward to create a reinforcement learning self-play framework for Morpion Solitaire. This enables us to find medium-quality solutions with reasonable computational effort. Our record is a 67 steps solution, which is very close to the human best (68) without any other adaptation to the problem than using ranked reward. We list many further avenues for potential improvement.
RasterNet: Modeling Free-Flow Speed using LiDAR and Overhead Imagery
Venue: arXiv cs.CV 2020
Year: 2020

Roadway free-flow speed captures the typical vehicle speed in low traffic conditions. Modeling free-flow speed is an important problem in transportation engineering with applications to a variety of design, operation, planning, and policy decisions of highway systems. Unfortunately, collecting large-scale historical traffic speed data is expensive and time consuming. Traditional approaches for estimating free-flow speed use geometric properties of the underlying road segment, such as grade, curvature, lane width, lateral clearance and access point density, but for many roads such features are unavailable. We propose a fully automated approach, RasterNet, for estimating free-flow speed without the need for explicit geometric features. RasterNet is a neural network that fuses large-scale overhead imagery and aerial LiDAR point clouds using a geospatially consistent raster structure. To support training and evaluation, we introduce a novel dataset combining free-flow speeds of road segments, overhead imagery, and LiDAR point clouds across the state of Kentucky. Our method achieves state-of-the-art results on a benchmark dataset.
The Statistical Cost of Robust Kernel Hyperparameter Tuning
Venue: arXiv cs.LG 2020
Year: 2020

This paper studies the statistical complexity of kernel hyperparameter tuning in the setting of active regression under adversarial noise. We consider the problem of finding the best interpolant from a class of kernels with unknown hyperparameters, assuming only that the noise is square-integrable. We provide finite-sample guarantees for the problem, characterizing how increasing the complexity of the kernel class increases the complexity of learning kernel hyperparameters. For common kernel classes (e.g. squared-exponential kernels with unknown lengthscale), our results show that hyperparameter optimization increases sample complexity by just a logarithmic factor, in comparison to the setting where optimal parameters are known in advance. Our result is based on a subsampling guarantee for linear regression under multiple design matrices, combined with an ε-net argument for discretizing kernel parameterizations.
Generalized Adversarially Learned Inference
Venue: arXiv cs.LG 2020
Year: 2020

Allowing effective inference of latent vectors while training GANs can greatly increase their applicability in various downstream tasks. Recent approaches, such as ALI and BiGAN frameworks, develop methods of inference of latent variables in GANs by adversarially training an image generator along with an encoder to match two joint distributions of image and latent vector pairs. We generalize these approaches to incorporate multiple layers of feedback on reconstructions, self-supervision, and other forms of supervision based on prior or learned knowledge about the desired solutions. We achieve this by modifying the discriminator's objective to correctly identify more than two joint distributions of tuples of an arbitrary number of random variables consisting of images, latent vectors, and other variables generated through auxiliary tasks, such as reconstruction and inpainting or as outputs of suitable pre-trained models. We design a non-saturating maximization objective for the generator-encoder pair and prove that the resulting adversarial game corresponds to a global optimum that simultaneously matches all the distributions. Within our proposed framework, we introduce a novel set of techniques for providing self-supervised feedback to the model based on properties, such as patch-level correspondence and cycle consistency of reconstructions. Through comprehensive experiments, we demonstrate the efficacy, scalability, and flexibility of the proposed approach for a variety of tasks.
Hybrid Systems Differential Dynamic Programming for Whole-Body Motion Planning of Legged Robots
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents a Differential Dynamic Programming (DDP) framework for trajectory optimization (TO) of hybrid systems with state-based switching. The proposed Hybrid Systems DDP (HS-DDP) approach is considered for application to whole-body motion planning with legged robots. Specifically, HS-DDP incorporates three algorithmic advances: an impact-aware DDP step addressing the impact event in legged locomotion, an Augmented Lagrangian (AL) method dealing with the switching constraint, and a Switching Time Optimization (STO) algorithm that optimizes switching times by leveraging the structure of DDP. Further, a Relaxed Barrier (ReB) method is used to manage inequality constraints and is integrated into HS-DDP for locomotion planning. The performance of the developed algorithms is benchmarked on a simulation model of the MIT Mini Cheetah executing a bounding gait. We demonstrate the effectiveness of AL and ReB for handling switching constraints, friction constraints, and torque limits. By comparing to previous solutions, we show that the STO algorithm achieves 2.3 times more reduction of total switching times, demonstrating the efficiency of our method.
Expertise and Dynamics within Crowdsourced Musical Knowledge Curation: A Case Study of the Genius Platform
Venue: arXiv cs.SI 2020
Year: 2020

Many platforms collect crowdsourced information primarily from volunteers. As this type of knowledge curation has become widespread, contribution formats vary substantially and are driven by diverse processes across differing platforms. Thus, models for one platform are not necessarily applicable to others. Here, we study the temporal dynamics of Genius, a platform primarily designed for user-contributed annotations of song lyrics. A unique aspect of Genius is that the annotations are extremely local -- an annotated lyric may just be a few lines of a song -- but also highly related, e.g., by song, album, artist, or genre. We analyze several dynamical processes associated with lyric annotations and their edits, which differ substantially from models for other platforms. For example, expertise on song annotations follows a "U shape" where experts are both early and late contributors with non-experts contributing intermediately; we develop a user utility model that captures such behavior. We also find several contribution traits appearing early in a user's lifespan of contributions that distinguish (eventual) experts from non-experts. Combining our findings, we develop a model for early prediction of user expertise.
Solution Subset Selection for Final Decision Making in Evolutionary Multi-Objective Optimization
Venue: arXiv cs.NE 2020
Year: 2020

In general, a multi-objective optimization problem does not have a single optimal solution but a set of Pareto optimal solutions, which forms the Pareto front in the objective space. Various evolutionary algorithms have been proposed to approximate the Pareto front using a pre-specified number of solutions. Hundreds of solutions are obtained by their single run. The selection of a single final solution from the obtained solutions is assumed to be done by a human decision maker. However, in many cases, the decision maker does not want to examine hundreds of solutions. Thus, it is needed to select a small subset of the obtained solutions. In this paper, we discuss subset selection from a viewpoint of the final decision making. First we briefly explain existing subset selection studies. Next we formulate an expected loss function for subset selection. We also show that the formulated function is the same as the IGD plus indicator. Then we report experimental results where the proposed approach is compared with other indicator-based subset selection methods.
hSPICE: State-Aware Event Shedding in Complex Event Processing
Venue: arXiv cs.DC 2020
Year: 2020

In complex event processing (CEP), load shedding is performed to maintain a given latency bound during overload situations when there is a limitation on resources. However, shedding load implies degradation in the quality of results (QoR). Therefore, it is crucial to perform load shedding in a way that has the lowest impact on QoR. Researchers, in the CEP domain, propose to drop either events or partial matches (PMs) in overload cases. They assign utilities to events or PMs by considering either the importance of events or the importance of PMs but not both together. In this paper, we propose a load shedding approach for CEP systems that combines these approaches by assigning a utility to an event by considering both the event importance and the importance of PMs. We adopt a probabilistic model that uses the type and position of an event in a window and the state of a PM to assign a utility to an event corresponding to each PM. We, also, propose an approach to predict a utility threshold that is used to drop the required amount of events to maintain a given latency bound. By extensive evaluations on two real-world datasets and several representative queries, we show that, in the majority of cases, our load shedding approach outperforms state-of-the-art load shedding approaches, w.r.t. QoR.
Differentiable Neural Architecture Transformation for Reproducible Architecture Improvement
Venue: arXiv cs.LG 2020
Year: 2020

Recently, Neural Architecture Search (NAS) methods are introduced and show impressive performance on many benchmarks. Among those NAS studies, Neural Architecture Transformer (NAT) aims to improve the given neural architecture to have better performance while maintaining computational costs. However, NAT has limitations about a lack of reproducibility. In this paper, we propose differentiable neural architecture transformation that is reproducible and efficient. The proposed method shows stable performance on various architectures. Extensive reproducibility experiments on two datasets, i.e., CIFAR-10 and Tiny Imagenet, present that the proposed method definitely outperforms NAT and be applicable to other models and datasets.
Learn to cycle: Time-consistent feature discovery for action recognition
Venue: arXiv cs.CV 2020
Year: 2020

Generalizing over temporal variations is a prerequisite for effective action recognition in videos. Despite significant advances in deep neural networks, it remains a challenge to focus on short-term discriminative motions in relation to the overall performance of an action. We address this challenge by allowing some flexibility in discovering relevant spatio-temporal features. We introduce Squeeze and Recursion Temporal Gates (SRTG), an approach that favors inputs with similar activations with potential temporal variations. We implement this idea with a novel CNN block that uses an LSTM to encapsulate feature dynamics, in conjunction with a temporal gate that is responsible for evaluating the consistency of the discovered dynamics and the modeled features. We show consistent improvement when using SRTG blocks, with only a minimal increase in the number of GFLOPs. On Kinetics-700, we perform on par with current state-of-the-art models, and outperform these on HACS, Moments in Time, UCF-101 and HMDB-51.
Renewable Energy Assisted Function Splitting in Cloud Radio Access Networks
Venue: arXiv cs.NI 2020
Year: 2020

Cloud-Radio Access Network (C-RAN) is a promising network architecture to reduce energy consumption and the increasing number of base station deployment costs in mobile networks. However, the necessity of enormous fronthaul bandwidth between a remote radio head and a baseband unit (BBU) calls for novel solutions. One of the solutions introduces the edge-cloud layer in addition to the centralized cloud (CC) to keep resources closer to the radio units (RUs). Then, split the BBU functions between the center cloud (CC) and edge clouds (ECs) to reduce the fronthaul bandwidth requirement and to relax the stringent end-to-end delay requirements. This paper expands this architecture by combining it with renewable energy sources in CC and ECs. We explain this novel system and formulate a mixed-integer linear programming (MILP) problem, which aims to reduce the operational expenditure of this system. Due to the NP-Hard property of this problem, we solve the smaller instances by using a MILP Solver and provide the results in this paper. Moreover, we propose a faster online heuristic to find solutions for high user densities. The results show that make splitting decisions by considering renewable energy provides more cost-effective solutions to mobile network operators (MNOs). Lastly, we provide an economic feasibility study for renewable energy sources in a CRAN architecture, which will encourage the MNOs to use these sources in this architecture.
Existential Theory of the Reals Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games
Venue: arXiv cs.GT 2020
Year: 2020

We show that the problem of deciding whether in a multi-player perfect information recursive game (i.e. a stochastic game with terminal rewards) there exists a stationary Nash equilibrium ensuring each player a certain payoff is Existential Theory of the Reals complete. Our result holds for acyclic games, where a Nash equilibrium may be computed efficiently by backward induction, and even for deterministic acyclic games with non-negative terminal rewards. We further extend our results to the existence of Nash equilibria where a single player is surely winning. Combining our result with known gadget games without any stationary Nash equilibrium, we obtain that for cyclic games, just deciding existence of any stationary Nash equilibrium is Existential Theory of the Reals complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.
Probing Neural Dialog Models for Conversational Understanding
Venue: arXiv cs.CL 2020
Year: 2020

The predominant approach to open-domain dialog generation relies on end-to-end training of neural models on chat datasets. However, this approach provides little insight as to what these models learn (or do not learn) about engaging in dialog. In this study, we analyze the internal representations learned by neural open-domain dialog systems and evaluate the quality of these representations for learning basic conversational skills. Our results suggest that standard open-domain dialog systems struggle with answering questions, inferring contradiction, and determining the topic of conversation, among other tasks. We also find that the dyadic, turn-taking nature of dialog is not fully leveraged by these models. By exploring these limitations, we highlight the need for additional research into architectures and training methods that can better capture high-level information about dialog.
An Augmented Translation Technique for low Resource language pair: Sanskrit to Hindi translation
Venue: arXiv cs.CL 2020
Year: 2020

Neural Machine Translation (NMT) is an ongoing technique for Machine Translation (MT) using enormous artificial neural network. It has exhibited promising outcomes and has shown incredible potential in solving challenging machine translation exercises. One such exercise is the best approach to furnish great MT to language sets with a little preparing information. In this work, Zero Shot Translation (ZST) is inspected for a low resource language pair. By working on high resource language pairs for which benchmarks are available, namely Spanish to Portuguese, and training on data sets (Spanish-English and English-Portuguese) we prepare a state of proof for ZST system that gives appropriate results on the available data. Subsequently the same architecture is tested for Sanskrit to Hindi translation for which data is sparse, by training the model on English-Hindi and Sanskrit-English language pairs. In order to prepare and decipher with ZST system, we broaden the preparation and interpretation pipelines of NMT seq2seq model in tensorflow, incorporating ZST features. Dimensionality reduction of word embedding is performed to reduce the memory usage for data storage and to achieve a faster training and translation cycles. In this work existing helpful technology has been utilized in an imaginative manner to execute our NLP issue of Sanskrit to Hindi translation. A Sanskrit-Hindi parallel corpus of 300 is constructed for testing. The data required for the construction of parallel corpus has been taken from the telecasted news, published on Department of Public Information, state government of Madhya Pradesh, India website.
An Algorithm to find Superior Fitness on NK Landscapes under High Complexity: Muddling Through
Venue: arXiv cs.AI 2020
Year: 2020

Under high complexity - given by pervasive interdependence between constituent elements of a decision in an NK landscape - our algorithm obtains fitness superior to that reported in extant research. We distribute the decision elements comprising a decision into clusters. When a change in value of a decision element is considered, a forward move is made if the aggregate fitness of the cluster members residing alongside the decision element is higher. The decision configuration with the highest fitness in the path is selected. Increasing the number of clusters obtains even higher fitness. Further, implementing moves comprising of up to two changes in a cluster also obtains higher fitness. Our algorithm obtains superior outcomes by enabling more extensive search, allowing inspection of more distant configurations. We name this algorithm the muddling through algorithm, in memory of Charles Lindblom who spotted the efficacy of the process long before sophisticated computer simulations came into being.
Open-Domain Question Answering with Pre-Constructed Question Spaces
Venue: arXiv cs.CL 2020
Year: 2020

Open-domain question answering aims at solving the task of locating the answers to user-generated questions in massive collections of documents. There are two families of solutions available: retriever-readers, and knowledge-graph-based approaches. A retriever-reader usually first uses information retrieval methods like TF-IDF to locate some documents or paragraphs that are likely to be relevant to the question, and then feeds the retrieved text to a neural network reader to extract the answer. Alternatively, knowledge graphs can be constructed from the corpus and be queried against to answer user questions. We propose a novel algorithm with a reader-retriever structure that differs from both families. Our reader-retriever first uses an offline reader to read the corpus and generate collections of all answerable questions associated with their answers, and then uses an online retriever to respond to user queries by searching the pre-constructed question spaces for answers that are most likely to be asked in the given way. We further combine retriever-reader and reader-retriever results into one single answer by examining the consistency between the two components. We claim that our algorithm solves some bottlenecks in existing work, and demonstrate that it achieves superior accuracy on real-world datasets.
Application of Fuzzy Rule based System for Highway Research Board Classification of Soils
Venue: arXiv cs.AI 2020
Year: 2020

Fuzzy rule-based model is a powerful tool for imitating the human way of thinking and solving uncertainty-related problems as it allows for understandable and interpretable rule bases. The objective of this paper is to study the applicability of fuzzy rule-based modelling to quantify soil classification for engineering purposes by qualitatively considering soil index properties. The classification system of the Highway Research Board is considered to illustrate a fuzzy rule-based model. The soil's index properties are fuzzified using triangular functions, and the fuzzy membership values are calculated. Fuzzy arithmetical operators are then applied to the membership values obtained for classification. Fuzzy decision tree classification algorithm is used to derive fuzzy if-then rules to quantify qualitative soil classification. The proposed system is implemented in MATLAB. The results obtained are checked and the implementation of the proposed model is measured against the outcomes of the laboratory tests.
Modeling bike availability in a bike-sharing system using machine learning
Venue: arXiv cs.CY 2020
Year: 2020

This paper models the availability of bikes at San Francisco Bay Area Bike Share stations using machine learning algorithms. Random Forest (RF) and Least-Squares Boosting (LSBoost) were used as univariate regression algorithms, and Partial Least-Squares Regression (PLSR) was applied as a multivariate regression algorithm. The univariate models were used to model the number of available bikes at each station. PLSR was applied to reduce the number of required prediction models and reflect the spatial correlation between stations in the network. Results clearly show that univariate models have lower error predictions than the multivariate model. However, the multivariate model results are reasonable for networks with a relatively large number of spatially correlated stations. Results also show that station neighbors and the prediction horizon time are significant predictors. The most effective prediction horizon time that produced the least prediction error was 15 minutes.
Generating Master Faces for Use in Performing Wolf Attacks on Face Recognition Systems
Venue: arXiv cs.CV 2020
Year: 2020

Due to its convenience, biometric authentication, especial face authentication, has become increasingly mainstream and thus is now a prime target for attackers. Presentation attacks and face morphing are typical types of attack. Previous research has shown that finger-vein- and fingerprint-based authentication methods are susceptible to wolf attacks, in which a wolf sample matches many enrolled user templates. In this work, we demonstrated that wolf (generic) faces, which we call "master faces," can also compromise face recognition systems and that the master face concept can be generalized in some cases. Motivated by recent similar work in the fingerprint domain, we generated high-quality master faces by using the state-of-the-art face generator StyleGAN in a process called latent variable evolution. Experiments demonstrated that even attackers with limited resources using only pre-trained models available on the Internet can initiate master face attacks. The results, in addition to demonstrating performance from the attacker's point of view, can also be used to clarify and improve the performance of face recognition systems and harden face authentication systems.