OpenRaiser/Intern-Atlas huggingface dataset:
Gender Genetic Algorithm in the Dynamic Optimization Problem
Venue: arXiv cs.NE 2020
Year: 2020

A general approach to optimizing fast processes using a gender genetic algorithm is described. Its difference from the more traditional genetic algorithm it contains division the artificial population into two sexes. Male subpopulations undergo large mutations and more strong selection compared to female individuals from another subset. This separation allows combining the rapid adaptability of the entire population to changes due to the variation of the male subpopulation with fixation of adaptability in the female part. The advantage of the effect of additional individual learning in the form of Boldwin effect in finding optimal solutions is observed in comparison with the usual gender genetic algorithm. As a promising application of the gender genetic algorithm with the Boldwin effect, the dynamics of extinguishing natural fires is pointed.
Learning to rank for uplift modeling
Venue: arXiv cs.LG 2020
Year: 2020

Uplift modeling has effectively been used in fields such as marketing and customer retention, to target those customers that are most likely to respond due to the campaign or treatment. Uplift models produce uplift scores which are then used to essentially create a ranking. We instead investigate to learn to rank directly by looking into the potential of learning-to-rank techniques in the context of uplift modeling. We propose a unified formalisation of different global uplift modeling measures in use today and explore how these can be integrated into the learning-to-rank framework. Additionally, we introduce a new metric for learning-to-rank that focusses on optimizing the area under the uplift curve called the promoted cumulative gain (PCG). We employ the learning-to-rank technique LambdaMART to optimize the ranking according to PCG and show improved results over standard learning-to-rank metrics and equal to improved results when compared with state-of-the-art uplift modeling. Finally, we show how learning-to-rank models can learn to optimize a certain targeting depth, however, these results do not generalize on the test set.
Intelligent Reflecting Surface Assisted Massive MIMO Communications
Venue: arXiv cs.IT 2020
Year: 2020

In a practical massive MIMO (multiple-input multiple-output) system, the number of antennas at a base station (BS) is constrained by the space and cost factors, which limits the throughput gain promised by theoretical analysis. This paper thus studies the feasibility of adopting the intelligent reflecting surface (IRS) to further improve the beamforming gain of the uplink communications in a massive MIMO system. Under such a novel system, the central question lies in whether the IRS is able to enhance the network throughput as expected, if the channel estimation overhead is taken into account. In this paper, we first show that the favorable propagation property for the conventional massive MIMO system without IRS, i.e., the channels of arbitrary two users are orthogonal, no longer holds for the IRS-assisted massive MIMO system, due to its special channel property that each IRS element reflects the signals from all the users to the BS via the same channel. As a result, the maximal-ratio combining (MRC) receive beamforming strategy leads to strong inter-user interference and thus even lower user rates than those of the massive MIMO system without IRS. To tackle this challenge, we propose a novel strategy for zero-forcing (ZF) beamforming design at the BS and reflection coefficients design at the IRS to efficiently null the inter-user interference. Under our proposed strategy, it is rigorously shown that even if the channel estimation overhead is considered, the IRS-assisted massive MIMO system can always achieve higher throughput compared to its counterpart without IRS, despite the fact that the favorable propagation property no longer holds.
Optimal Pricing of Internet of Things: A Machine Learning Approach
Venue: arXiv cs.NI 2020
Year: 2020

Internet of things (IoT) produces massive data from devices embedded with sensors. The IoT data allows creating profitable services using machine learning. However, previous research does not address the problem of optimal pricing and bundling of machine learning-based IoT services. In this paper, we define the data value and service quality from a machine learning perspective. We present an IoT market model which consists of data vendors selling data to service providers, and service providers offering IoT services to customers. Then, we introduce optimal pricing schemes for the standalone and bundled selling of IoT services. In standalone service sales, the service provider optimizes the size of bought data and service subscription fee to maximize its profit. For service bundles, the subscription fee and data sizes of the grouped IoT services are optimized to maximize the total profit of cooperative service providers. We show that bundling IoT services maximizes the profit of service providers compared to the standalone selling. For profit sharing of bundled services, we apply the concepts of core and Shapley solutions from cooperative game theory as efficient and fair allocations of payoffs among the cooperative service providers in the bundling coalition.
Revisiting Underapproximate Reachability for Multipushdown Systems
Venue: arXiv cs.FL 2020
Year: 2020

Boolean programs with multiple recursive threads can be captured as pushdown automata with multiple stacks. This model is Turing complete, and hence, one is often interested in analyzing a restricted class that still captures useful behaviors. In this paper, we propose a new class of bounded under approximations for multi-pushdown systems, which subsumes most existing classes. We develop an efficient algorithm for solving the under-approximate reachability problem, which is based on efficient fix-point computations. We implement it in our tool BHIM and illustrate its applicability by generating a set of relevant benchmarks and examining its performance. As an additional takeaway, BHIM solves the binary reachability problem in pushdown automata. To show the versatility of our approach, we then extend our algorithm to the timed setting and provide the first implementation that can handle timed multi-pushdown automata with closed guards.
A Breezing Proof of the KMW Bound
Venue: arXiv cs.DC 2020
Year: 2020

In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW) proved a hardness result for several fundamental graph problems in the LOCAL model: For any (randomized) algorithm, there are input graphs with $n$ nodes and maximum degree $Δ$ on which $Ω(\min\{\sqrt{\log n/\log \log n},\log Δ/\log \log Δ\})$ (expected) communication rounds are required to obtain polylogarithmic approximations to a minimum vertex cover, minimum dominating set, or maximum matching. Via reduction, this hardness extends to symmetry breaking tasks like finding maximal independent sets or maximal matchings. Today, more than $15$ years later, there is still no proof of this result that is easy on the reader. Setting out to change this, in this work, we provide a fully self-contained and $\mathit{simple}$ proof of the KMW lower bound. The key argument is algorithmic, and it relies on an invariant that can be readily verified from the generation rules of the lower bound graphs.
Scalable and Practical Natural Gradient for Large-Scale Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

Large-scale distributed training of deep neural networks results in models with worse generalization performance as a result of the increase in the effective mini-batch size. Previous approaches attempt to address this problem by varying the learning rate and batch size over epochs and layers, or ad hoc modifications of batch normalization. We propose Scalable and Practical Natural Gradient Descent (SP-NGD), a principled approach for training models that allows them to attain similar generalization performance to models trained with first-order optimization methods, but with accelerated convergence. Furthermore, SP-NGD scales to large mini-batch sizes with a negligible computational overhead as compared to first-order methods. We evaluated SP-NGD on a benchmark task where highly optimized first-order methods are available as references: training a ResNet-50 model for image classification on ImageNet. We demonstrate convergence to a top-1 validation accuracy of 75.4% in 5.5 minutes using a mini-batch size of 32,768 with 1,024 GPUs, as well as an accuracy of 74.9% with an extremely large mini-batch size of 131,072 in 873 steps of SP-NGD.
A Prompt Report on the Performance of Intel Optane DC Persistent Memory Module
Venue: arXiv cs.PF 2020
Year: 2020

In this prompt report, we present the basic performance evaluation of Intel Optane Data Center Persistent Memory Module (Optane DCPMM), which is the first commercially-available, byte-addressable non-volatile memory modules released in April 2019. Since at the moment of writing only a few reports on its performance were published, this letter is intended to complement other performance studies. Through experiments using our own measurement tools, we obtained that the latency of random read-only access was approximately 374 ns. That of random writeback-involving access was 391 ns. The bandwidths of read-only and writeback-involving access for interleaved memory modules were approximately 38 GB/s and 3 GB/s, respectively.
A comparison of different types of Niching Genetic Algorithms for variable selection in solar radiation estimation
Venue: arXiv cs.NE 2020
Year: 2020

Variable selection problems generally present more than a single solution and, sometimes, it is worth to find as many solutions as possible. The use of Evolutionary Algorithms applied to this kind of problem proves to be one of the best methods to find optimal solutions. Moreover, there are variants designed to find all or almost all local optima, known as Niching Genetic Algorithms (NGA). There are several different NGA methods developed in order to achieve this task. The present work compares the behavior of eight different niching techniques, applied to a climatic database of four weather stations distributed in Tucuman, Argentina. The goal is to find different sets of input variables that have been used as the input variable by the estimation method. Final results were evaluated based on low estimation error and low dispersion error, as well as a high number of different results and low computational time. A second experiment was carried out to study the capability of the method to identify critical variables. The best results were obtained with Deterministic Crowding. In contrast, Steady State Worst Among Most Similar and Probabilistic Crowding showed good results but longer processing times and less ability to determine the critical factors.
Constructions of quantum MDS codes
Venue: arXiv cs.IT 2020
Year: 2020

Let $\mathbb{F}_q$ be a finite field with $q=p^{e}$ elements, where $p$ is a prime number and $e \geq 1$ is an integer. In this paper, by means of generalized Reed-Solomon (GRS) codes, we construct two new classes of quantum maximum-distance-separable ( quantum MDS) codes with parameters $$[[q + 1, 2k-q-1, q-k+2]]_q$$ for $\lceil\frac{q+2}{2}\rceil \leq k\leq q+1$, and $$[[n,2k-n,n-k+1]]_q$$ for $n\leq q $ and $ \lceil\frac{n}{2}\rceil \leq k\leq n$. Our constructions improve and generalize some results of available in the literature. Moreover, we give an affirmative answer to the open problem proposed by Fang et al. in \cite{Fang1}.
menoci: Lightweight Extensible Web Portal enabling FAIR Data Management for Biomedical Research Projects
Venue: arXiv cs.DL 2020
Year: 2020

Background: Biomedical research projects deal with data management requirements from multiple sources like funding agencies' guidelines, publisher policies, discipline best practices, and their own users' needs. We describe functional and quality requirements based on many years of experience implementing data management for the CRC 1002 and CRC 1190. A fully equipped data management software should improve documentation of experiments and materials, enable data storage and sharing according to the FAIR Guiding Principles while maximizing usability, information security, as well as software sustainability and reusability. Results: We introduce the modular web portal software menoci for data collection, experiment documentation, data publication, sharing, and preservation in biomedical research projects. Menoci modules are based on the Drupal content management system which enables lightweight deployment and setup, and creates the possibility to combine research data management with a customisable project home page or collaboration platform. Conclusions: Management of research data and digital research artefacts is transforming from individual researcher or groups best practices towards project- or organisation-wide service infrastructures. To enable and support this structural transformation process, a vital ecosystem of open source software tools is needed. Menoci is a contribution to this ecosystem of research data management tools that is specifically designed to support biomedical research projects.
Generating a Generic Fluent API in Java
Venue: arXiv cs.PL 2020
Year: 2020

Context: The algorithms for generating a safe fluent API are actively studied these years. A safe fluent API is the fluent API that reports incorrect chaining of the API methods as a type error to the API users. Although such a safe property improves the productivity of its users, the construction of a safe fluent API is too complicated for the developers. The generation algorithms are studied to reduce the development cost of a safe fluent API. The study on the generation would benefit a number of programmers since a fluent API is a popular design in the real world. Inquiry: The generation of a generic fluent API has been left untackled. A generic fluent API refers to the fluent API that provides generic methods (methods that contain type parameters in their definitions). The Stream API in Java is an example of such a generic API. The recent research on the safe fluent API generation rather focuses on the grammar class that the algorithm can deal with for syntax checking. The key idea of the previous study is to use nested generics to represent a stack structure for the parser built on top of the type system. In that idea, the role of a type parameter was limited to internally representing a stack element of that parser on the type system. The library developers could not use type parameters to include a generic method in their API so that the semantic constraints for their API would be statically checked, for example, the type constraint on the items passed through a stream. Approach: We propose an algorithm to generate a generic fluent API. Our translation algorithm is modeled as the construction of deterministic finite automaton (DFA) with type parameter information. Each state of the DFA holds information about which type parameters are already bound in that state. This information is used to identify whether a method invocation in a chain newly binds a type to a type parameter, or refers to a previously bound type. The identification is required since a type parameter in a chain is bound at a particular method invocation, and that bound type is referred to in the following method invocations. Our algorithm constructs the DFA by analyzing the binding time of type parameters and their propagation among the states in a DFA that is naively constructed from the given grammar. Knowledge and Importance: Our algorithm helps library developers to develop a generic fluent API. The ability to generate a generic fluent API is essential to bring the safe fluent API generation to the real world since the use of type parameters is a common technique in the library API design. By our algorithm, the generation of a safe fluent API will be ready for practical use. Grounding: We implemented a generator named Protocool to demonstrate our algorithm. We also generated several libraries using Protocool to show the ability and the limitations of our algorithm.
Foundations of a live data exploration environment
Venue: arXiv cs.PL 2020
Year: 2020

Context: A growing amount of code is written to explore and analyze data, often by data analysts who do not have a traditional background in programming, for example by journalists. Inquiry: The way such data anlysts write code is different from the way software engineers do so. They use few abstractions, work interactively and rely heavily on external libraries. We aim to capture this way of working and build a programming environment that makes data exploration easier by providing instant live feedback. Approach: We combine theoretical and applied approach. We present the \emph{data exploration calculus}, a formal language that captures the structure of code written by data analysts. We then implement a data exploration environment that evaluates code instantly during editing and shows previews of the results. Knowledge: We formally describe an algorithm for providing instant previews for the data exploration calculus that allows the user to modify code in an unrestricted way in a text editor. Supporting interactive editing is tricky as any edit can change the structure of code and fully recomputing the output would be too expensive. Grounding: We prove that our algorithm is correct and that it reuses previous results when updating previews after a number of common code edit operations. We also illustrate the practicality of our approach with an empirical evaluation and a case study. Importance: As data analysis becomes an ever more important use of programming, research on programming languages and tools needs to consider new kinds of programming workflows appropriate for those domains and conceive new kinds of tools that can support them. The present paper is one step in this important direction.
Fast Fair Regression via Efficient Approximations of Mutual Information
Venue: arXiv cs.LG 2020
Year: 2020

Most work in algorithmic fairness to date has focused on discrete outcomes, such as deciding whether to grant someone a loan or not. In these classification settings, group fairness criteria such as independence, separation and sufficiency can be measured directly by comparing rates of outcomes between subpopulations. Many important problems however require the prediction of a real-valued outcome, such as a risk score or insurance premium. In such regression settings, measuring group fairness criteria is computationally challenging, as it requires estimating information-theoretic divergences between conditional probability density functions. This paper introduces fast approximations of the independence, separation and sufficiency group fairness criteria for regression models from their (conditional) mutual information definitions, and uses such approximations as regularisers to enforce fairness within a regularised risk minimisation framework. Experiments in real-world datasets indicate that in spite of its superior computational efficiency our algorithm still displays state-of-the-art accuracy/fairness tradeoffs.
Electricity Theft Detection with self-attention
Venue: arXiv cs.LG 2020
Year: 2020

In this work we propose a novel self-attention mechanism model to address electricity theft detection on an imbalanced realistic dataset that presents a daily electricity consumption provided by State Grid Corporation of China. Our key contribution is the introduction of a multi-head self-attention mechanism concatenated with dilated convolutions and unified by a convolution of kernel size $1$. Moreover, we introduce a binary input channel (Binary Mask) to identify the position of the missing values, allowing the network to learn how to deal with these values. Our model achieves an AUC of $0.926$ which is an improvement in more than $17\%$ with respect to previous baseline work. The code is available on GitHub at https://github.com/neuralmind-ai/electricity-theft-detection-with-self-attention.
Proportional Fairness through Dual Connectivity in Heterogeneous Networks
Venue: arXiv cs.NI 2020
Year: 2020

Proportional Fair (PF) is a scheduling technique to maintain a balance between maximizing throughput and ensuring fairness to users. Dual Connectivity (DC) technique was introduced by the 3rd Generation Partnership Project (3GPP) to improve the mobility robustness and system capacity in heterogeneous networks. In this paper, we demonstrate the utility of DC in improving proportional fairness in the system. We propose a low complexity centralized PF scheduling scheme for DC and show that it outperforms the standard PF scheduling scheme. Since the problem of dual association of users for maximizing proportional fairness in the system is NP-hard, we propose three heuristic user association schemes for DC. We demonstrate that DC, along with the proposed PF scheme, gives remarkable gains on PF utility over single connectivity and performs almost close to the optimal PF scheme in heterogeneous networks.
Deep RL Agent for a Real-Time Action Strategy Game
Venue: arXiv cs.AI 2020
Year: 2020

We introduce a reinforcement learning environment based on Heroic - Magic Duel, a 1 v 1 action strategy game. This domain is non-trivial for several reasons: it is a real-time game, the state space is large, the information given to the player before and at each step of a match is imperfect, and distribution of actions is dynamic. Our main contribution is a deep reinforcement learning agent playing the game at a competitive level that we trained using PPO and self-play with multiple competing agents, employing only a simple reward of $\pm 1$ depending on the outcome of a single match. Our best self-play agent, obtains around $65\%$ win rate against the existing AI and over $50\%$ win rate against a top human player.
A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension
Venue: arXiv cs.SC 2020
Year: 2020

Let $f_1,\ldots,f_m$ be elements in a quotient $R^n / N$ which has finite dimension as a $K$-vector space, where $R = K[X_1,\ldots,X_r]$ and $N$ is an $R$-submodule of $R^n$. We address the problem of computing a Gröbner basis of the module of syzygies of $(f_1,\ldots,f_m)$, that is, of vectors $(p_1,\ldots,p_m) \in R^m$ such that $p_1 f_1 + \cdots + p_m f_m = 0$. An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of $R^n / N$ as the kernel of a collection of linear functionals. Following this viewpoint, we design a divide-and-conquer algorithm, which can be interpreted as a generalization to several variables of Beckermann and Labahn's recursive approach for matrix Padé and rational interpolation problems. To highlight the interest of this method, we focus on the specific case of bivariate Padé approximation and show that it improves upon the best known complexity bounds.
A Note on Unbounded Polyhedra Derived from Convex Caps
Venue: arXiv cs.CG 2020
Year: 2020

The construction of an unbounded polyhedron from a "jagged'' convex cap is described, and several of its properties discussed, including its relation to Alexandrov's "limit angle."