OpenRaiser/Intern-Atlas huggingface dataset:
On Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau
Venue: arXiv cs.NE 2020
Year: 2020

We consider the expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions with a plateau of second-best fitness in a Hamming ball of radius r around a unique global optimum. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for some modes of non-elitist EA based on unbiased mutation and the bitwise mutation in particular. On the other hand, we show that the EA with fitness proportionate selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.
On Verifying Designs With Incomplete Specification
Venue: arXiv cs.LO 2020
Year: 2020

Incompleteness of a specification $\mathit{Spec}$ creates two problems. First, an implementation $\mathit{Impl}$ of $\mathit{Spec}$ may have some $\mathit{unwanted}$ properties that $\mathit{Spec}$ does not forbid. Second, $\mathit{Impl}$ may break some $\mathit{desired}$ properties that are not in $\mathit{Spec}$. In either case, $\mathit{Spec}$ fails to expose bugs of $\mathit{Impl}$. In an earlier paper, we addressed the first problem above by a technique called Partial Quantifier Elimination (PQE). In contrast to complete QE, in PQE, one takes out of the scope of quantifiers only a small piece of the formula. We used PQE to generate properties of $\mathit{Impl}$ i.e. those $\mathit{consistent}$ with $\mathit{Impl}$. Generation of an unwanted property means that $\mathit{Impl}$ is buggy. In this paper, we address the second problem above by using PQE to generate false properties i.e those that are $\mathit{inconsistent}$ with $\mathit{Impl}$. Such properties are meant to imitate the missing properties of $\mathit{Spec}$ that are not satisfied by $\mathit{Impl}$ (if any). A false property is generated by modifying a piece of a quantified formula describing 'the truth table' of $\mathit{Impl}$ and taking this piece out of the scope of quantifiers. By modifying different pieces of this formula one can generate a "structurally complete" set of false properties. By generating tests detecting false properties of $\mathit{Impl}$ one produces a high quality test set. We apply our approach to verification of combinational and sequential circuits.
Utilizing Mask R-CNN for Waterline Detection in Canoe Sprint Video Analysis
Venue: arXiv cs.CV 2020
Year: 2020

Determining a waterline in images recorded in canoe sprint training is an important component for the kinematic parameter analysis to assess an athlete's performance. Here, we propose an approach for the automated waterline detection. First, we utilized a pre-trained Mask R-CNN by means of transfer learning for canoe segmentation. Second, we developed a multi-stage approach to estimate a waterline from the outline of the segments. It consists of two linear regression stages and the systematic selection of canoe parts. We then introduced a parameterization of the waterline as a basis for further evaluations. Next, we conducted a study among several experts to estimate the ground truth waterlines. This not only included an average waterline drawn from the individual experts annotations but, more importantly, a measure for the uncertainty between individual results. Finally, we assessed our method with respect to the question whether the predicted waterlines are in accordance with the experts annotations. Our method demonstrated a high performance and provides opportunities for new applications in the field of automated video analysis in canoe sprint.
Sampling and Inference of Networked Dynamics using Log-Koopman Nonlinear Graph Fourier Transform
Venue: arXiv cs.IT 2020
Year: 2020

Networked nonlinear dynamics underpin the complex functionality of many engineering, social, biological, and ecological systems. Monitoring the networked dynamics via the minimum subset of nodes is essential for a variety of scientific and operational purposes. When there is a lack of a explicit model and networked signal space, traditional evolution analysis and non-convex methods are insufficient. An important data-driven state-of-the-art method use the Koopman operator to generate a linear evolution model for a vector-valued observable of original state-space. As a result, one can derive a sampling strategy via the linear evolution property of observable. However, current polynomial Koopman operators result in a large sampling space due to: (i) the large size of polynomial based observables ($O(N^2)$, $N$ number of nodes in network), and (ii) not factoring in the nonlinear dependency between observables. In this work, to achieve linear scaling ($O(N)$) and a small set of sampling nodes, we propose to combine a novel Log-Koopman operator and nonlinear Graph Fourier Transform (NL-GFT) scheme. First, the Log-Koopman operator is able to reduce the size of observables by transforming multiplicative poly-observable to logarithm summation. Second, a nonlinear GFT concept and sampling theory are provided to exploit the nonlinear dependence of observables for Koopman linearized evolution analysis. Combined, the sampling and reconstruction algorithms are designed and demonstrated on two established application areas. The results demonstrate that the proposed Log-Koopman NL-GFT scheme can (i) linearize unknown nonlinear dynamics using $O(N)$ observables, and (ii) achieve lower number of sampling nodes, compared with the state-of-the art polynomial Koopman linear evolution analysis.
Global Sensitivity Methods for Design of Experiments in Lithium-ion Battery Context
Venue: arXiv cs.CE 2020
Year: 2020

Battery management systems may rely on mathematical models to provide higher performance than standard charging protocols. Electrochemical models allow us to capture the phenomena occurring inside a lithium-ion cell and therefore, could be the best model choice. However, to be of practical value, they require reliable model parameters. Uncertainty quantification and optimal experimental design concepts are essential tools for identifying systems and estimating parameters precisely. Approximation errors in uncertainty quantification result in sub-optimal experimental designs and consequently, less-informative data, and higher parameter unreliability. In this work, we propose a highly efficient design of experiment method based on global parameter sensitivities. This novel concept is applied to the single-particle model with electrolyte and thermal dynamics (SPMeT), a well-known electrochemical model for lithium-ion cells. The proposed method avoids the simplifying assumption of output-parameter linearization (i.e., local parameter sensitivities) used in conventional Fisher information matrix-based experimental design strategies. Thus, the optimized current input profile results in experimental data of higher information content and in turn, in more precise parameter estimates.
Scheduling with Communication Delays via LP Hierarchies and Clustering
Venue: arXiv cs.DS 2020
Year: 2020

We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting, denoted by $\mathsf{P} \mid \mathsf{prec}, c \mid C_{\mathsf{max}}$, if two dependent jobs are scheduled on different machines, then at least $c$ units of time must pass between their executions. Despite its relevance to many applications, this model remains one of the most poorly understood in scheduling theory. Even for a special case where an unlimited number of machines is available, the best known approximation ratio is $2/3 \cdot (c+1)$, whereas Graham's greedy list scheduling algorithm already gives a $(c+1)$-approximation in that setting. An outstanding open problem in the top-10 list by Schuurman and Woeginger and its recent update by Bansal asks whether there exists a constant-factor approximation algorithm. In this work we give a polynomial-time $O(\log c \cdot \log m)$-approximation algorithm for this problem, where $m$ is the number of machines and $c$ is the communication delay. Our approach is based on a Sherali-Adams lift of a linear programming relaxation and a randomized clustering of the semimetric space induced by this lift.
Heterogeneous Causal Learning for Effectiveness Optimization in User Marketing
Venue: arXiv cs.LG 2020
Year: 2020

User marketing is a key focus of consumer-based internet companies. Learning algorithms are effective to optimize marketing campaigns which increase user engagement, and facilitates cross-marketing to related products. By attracting users with rewards, marketing methods are effective to boost user activity in the desired products. Rewards incur significant cost that can be off-set by increase in future revenue. Most methodologies rely on churn predictions to prevent losing users to make marketing decisions, which cannot capture up-lift across counterfactual outcomes with business metrics. Other predictive models are capable of estimating heterogeneous treatment effects, but fail to capture the balance of cost versus benefit. We propose a treatment effect optimization methodology for user marketing. This algorithm learns from past experiments and utilizes novel optimization methods to optimize cost efficiency with respect to user selection. The method optimizes decisions using deep learning optimization models to treat and reward users, which is effective in producing cost-effective, impactful marketing campaigns. Our methodology demonstrates superior algorithmic flexibility with integration with deep learning methods and dealing with business constraints. The effectiveness of our model surpasses the quasi-oracle estimation (R-learner) model and causal forests. We also established evaluation metrics that reflect the cost-efficiency and real-world business value. Our proposed constrained and direct optimization algorithms outperform by 24.6% compared with the best performing method in prior art and baseline methods. The methodology is useful in many product scenarios such as optimal treatment allocation and it has been deployed in production world-wide.
Learning Continuous Treatment Policy and Bipartite Embeddings for Matching with Heterogeneous Causal Effects
Venue: arXiv cs.LG 2020
Year: 2020

Causal inference methods are widely applied in the fields of medicine, policy, and economics. Central to these applications is the estimation of treatment effects to make decisions. Current methods make binary yes-or-no decisions based on the treatment effect of a single outcome dimension. These methods are unable to capture continuous space treatment policies with a measure of intensity. They also lack the capacity to consider the complexity of treatment such as matching candidate treatments with the subject. We propose to formulate the effectiveness of treatment as a parametrizable model, expanding to a multitude of treatment intensities and complexities through the continuous policy treatment function, and the likelihood of matching. Our proposal to decompose treatment effect functions into effectiveness factors presents a framework to model a rich space of actions using causal inference. We utilize deep learning to optimize the desired holistic metric space instead of predicting single-dimensional treatment counterfactual. This approach employs a population-wide effectiveness measure and significantly improves the overall effectiveness of the model. The performance of our algorithms is. demonstrated with experiments. When using generic continuous space treatments and matching architecture, we observe a 41% improvement upon prior art with cost-effectiveness and 68% improvement upon a similar method in the average treatment effect. The algorithms capture subtle variations in treatment space, structures the efficient optimizations techniques, and opens up the arena for many applications.
On the Compressive Power of Boolean Threshold Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

An autoencoder is a layered neural network whose structure can be viewed as consisting of an encoder, which compresses an input vector of dimension $D$ to a vector of low dimension $d$, and a decoder which transforms the low-dimensional vector back to the original input vector (or one that is very similar). In this paper we explore the compressive power of autoencoders that are Boolean threshold networks by studying the numbers of nodes and layers that are required to ensure that the numbers of nodes and layers that are required to ensure that each vector in a given set of distinct input binary vectors is transformed back to its original. We show that for any set of $n$ distinct vectors there exists a seven-layer autoencoder with the smallest possible middle layer, (i.e., its size is logarithmic in $n$), but that there is a set of $n$ vectors for which there is no three-layer autoencoder with a middle layer of the same size. In addition we present a kind of trade-off: if a considerably larger middle layer is permissible then a five-layer autoencoder does exist. We also study encoding by itself. The results we obtain suggest that it is the decoding that constitutes the bottleneck of autoencoding. For example, there always is a three-layer Boolean threshold encoder that compresses $n$ vectors into a dimension that is reduced to twice the logarithm of $n$.
The 1st Agriculture-Vision Challenge: Methods and Results
Venue: arXiv cs.CV 2020
Year: 2020

The first Agriculture-Vision Challenge aims to encourage research in developing novel and effective algorithms for agricultural pattern recognition from aerial images, especially for the semantic segmentation task associated with our challenge dataset. Around 57 participating teams from various countries compete to achieve state-of-the-art in aerial agriculture semantic segmentation. The Agriculture-Vision Challenge Dataset was employed, which comprises of 21,061 aerial and multi-spectral farmland images. This paper provides a summary of notable methods and results in the challenge. Our submission server and leaderboard will continue to open for researchers that are interested in this challenge dataset and task; the link can be found here.
Betweenness of partial orders
Venue: arXiv cs.LO 2020
Year: 2020

We construct a monadic second-order sentence that characterizes the ternary relations that are the betweenness relations of finite or infinite partial orders. We prove that no first-order sentence can do that. We characterize the partial orders that can be reconstructed from their betweenness relations. We propose a polynomial time algorithm that tests if a finite relation is the be-tweenness of a partial order.
Chat activity is a better predictor than chat sentiment on software developers productivity
Venue: arXiv cs.SE 2020
Year: 2020

Recent works have proposed that software developers' positive emotion has a positive impact on software developers' productivity. In this paper we investigate two data sources: developers chat messages (from Slack and Hipchat) and source code commits of a single co-located Agile team over 200 working days. Our regression analysis shows that the number of chat messages is the best predictor and predicts productivity measured both in the number of commits and lines of code with $R^2$ of 0.33 and 0.27 respectively. We then add sentiment analysis variables until AIC of our model no longer improves and gets $R^2$ values of 0.37 (commits) and 0.30 (lines of code). Thus, analyzing chat sentiment improves productivity prediction over chat activity alone but the difference is not massive. This work supports the idea that emotional state and productivity are linked in software development. We find that three positive sentiment metrics, but surprisingly also one negative sentiment metric is associated with higher productivity.
Business Process Re-engineering in Supply Chains Examining the case of the expanding Halal industry
Venue: arXiv cs.OH 2020
Year: 2020

Due to several issues arising in the rapidly-expanding Halal industry, among them the production of non-genuine or contaminated products and meats, there is a need to develop effective solutions for ensuring authenticity and quality. This paper proposes the specification of a formalized supply chain framework for the production and monitoring of food and products. The latter enforces high-level quality of automated monitoring as well as shorter production cycles through enhanced coordination between the actors and organizations involved. Our proposal is guided by business process support to ensure quality and efficiency of product development and delivery. It moreover meets the requirements of industrial standards by adopting the Capability Maturity Model Integration highest process maturity level through establishing quantitative process-improvement objectives, proposing the integrated support of engineering processes, enforcing synchronization and coordination, drastic monitoring and exception handling. We then delve into some of the important technologies from the implementation point-of-view and align it with the formalized Halal framework. An Information Technology support instantiation is proposed leading to a use case scenario with technology identification.
Knowledge-Driven Distractor Generation for Cloze-style Multiple Choice Questions
Venue: arXiv cs.CL 2020
Year: 2020

In this paper, we propose a novel configurable framework to automatically generate distractive choices for open-domain cloze-style multiple-choice questions, which incorporates a general-purpose knowledge base to effectively create a small distractor candidate set, and a feature-rich learning-to-rank model to select distractors that are both plausible and reliable. Experimental results on datasets across four domains show that our framework yields distractors that are more plausible and reliable than previous methods. This dataset can also be used as a benchmark for distractor generation in the future.
Enumerating Maximal Induced Subgraphs
Venue: arXiv cs.DS 2020
Year: 2020

Given a graph $G$, the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of $G$ that belong to a certain hereditary graph class. While its optimization version, known as the minimum vertex deletion problem in literature, has been intensively studied, enumeration algorithms are known for a few simple graph classes, e.g., independent sets, cliques, and forests, until very recently [Conte and Uno, STOC 2019]. There is also a connected variation of this problem, where one is concerned with only those induced subgraphs that are connected. We introduce two new approaches, which enable us to develop algorithms that solve both variations for a number of important graph classes. A general technique that has been proved very powerful in enumeration algorithms is to build a solution map, i.e., a multiple digraph on all the solutions of the problem, and the key of this approach is to make the solution map strongly connected, so that a simple traversal of the solution map solves the problem. We introduce retaliation-free paths to certificate strong connectedness of the solution map we build. Generalizing the idea of Cohen, Kimelfeld, and Sagiv [JCSS 2008], we introduce the $t$-restricted version, $t$ being a positive integer, of the maximal (connected) induced subgraphs problem, and show that it is equivalent to the original problem in terms of solvability in incremental polynomial time. Moreover, we give reductions between the two variations, so that it suffices to solve one of the variations for each class we study. Our work also leads to direct and simpler proofs of several important known results.
Considering Likelihood in NLP Classification Explanations with Occlusion and Language Modeling
Venue: arXiv cs.CL 2020
Year: 2020

Recently, state-of-the-art NLP models gained an increasing syntactic and semantic understanding of language, and explanation methods are crucial to understand their decisions. Occlusion is a well established method that provides explanations on discrete language data, e.g. by removing a language unit from an input and measuring the impact on a model's decision. We argue that current occlusion-based methods often produce invalid or syntactically incorrect language data, neglecting the improved abilities of recent NLP models. Furthermore, gradient-based explanation methods disregard the discrete distribution of data in NLP. Thus, we propose OLM: a novel explanation method that combines occlusion and language models to sample valid and syntactically correct replacements with high likelihood, given the context of the original input. We lay out a theoretical foundation that alleviates these weaknesses of other explanation methods in NLP and provide results that underline the importance of considering data likelihood in occlusion-based explanation.
An RNN-Survival Model to Decide Email Send Times
Venue: arXiv cs.LG 2020
Year: 2020

Email communications are ubiquitous. Firms control send times of emails and thereby the instants at which emails reach recipients (it is assumed email is received instantaneously from the send time). However, they do not control the duration it takes for recipients to open emails, labeled as time-to-open. Importantly, among emails that are opened, most occur within a short window from their send times. We posit that emails are likely to be opened sooner when send times are convenient for recipients, while for other send times, emails can get ignored. Thus, to compute appropriate send times it is important to predict times-to-open accurately. We propose a recurrent neural network (RNN) in a survival model framework to predict times-to-open, for each recipient. Using that we compute appropriate send times. We experiment on a data set of emails sent to a million customers over five months. The sequence of emails received by a person from a sender is a result of interactions with past emails from the sender, and hence contain useful signal that inform our model. This sequential dependence affords our proposed RNN-Survival (RNN-S) approach to outperform survival analysis approaches in predicting times-to-open. We show that best times to send emails can be computed accurately from predicted times-to-open. This approach allows a firm to tune send times of emails, which is in its control, to favorably influence open rates and engagement.
torchgpipe: On-the-fly Pipeline Parallelism for Training Giant Models
Venue: arXiv cs.DC 2020
Year: 2020

We design and implement a ready-to-use library in PyTorch for performing micro-batch pipeline parallelism with checkpointing proposed by GPipe (Huang et al., 2019). In particular, we develop a set of design components to enable pipeline-parallel gradient computation in PyTorch's define-by-run and eager execution environment. We show that each component is necessary to fully benefit from pipeline parallelism in such environment, and demonstrate the efficiency of the library by applying it to various network architectures including AmoebaNet-D and U-Net. Our library is available at https://github.com/kakaobrain/torchgpipe .