OpenRaiser/Intern-Atlas huggingface dataset:
Monadic Decomposability of Regular Relations
Venue: arXiv cs.FL 2019
Year: 2019

Monadic decomposibility --- the ability to determine whether a formula in a given logical theory can be decomposed into a boolean combination of monadic formulas --- is a powerful tool for devising a decision procedure for a given logical theory. In this paper, we revisit a classical decision problem in automata theory: given a regular (a.k.a. synchronized rational) relation, determine whether it is recognizable, i.e., it has a monadic decomposition (that is, a representation as a boolean combination of cartesian products of regular languages). Regular relations are expressive formalisms which, using an appropriate string encoding, can capture relations definable in Presburger Arithmetic. In fact, their expressive power coincide with relations definable in a universal automatic structure; equivalently, those definable by finite set interpretations in WS1S (Weak Second Order Theory of One Successor). Determining whether a regular relation admits a recognizable relation was known to be decidable (and in exponential time for binary relations), but its precise complexity still hitherto remains open. Our main contribution is to fully settle the complexity of this decision problem by developing new techniques employing infinite Ramsey theory. The complexity for DFA (resp. NFA) representations of regular relations is shown to be NLOGSPACE-complete (resp. \PSPACE-complete).
Research Software Development & Management in Universities: Case Studies from Manchester's RSDS Group, Illinois' NCSA, and Notre Dame's CRC
Venue: arXiv cs.SE 2019
Year: 2019

Modern research in the sciences, engineering, humanities, and other fields depends on software, and specifically, research software. Much of this research software is developed in universities, by faculty, postdocs, students, and staff. In this paper, we focus on the role of university staff. We examine three different, independently-developed models under which these staff are organized and perform their work, and comparatively analyze these models and their consequences on the staff and on the software, considering how the different models support software engineering practices and processes. This information can be used by software engineering researchers to understand the practices of such organizations and by universities who want to set up similar organizations and to better produce and maintain research software.
Automating Predictive Modeling Process using Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

Building a good predictive model requires an array of activities such as data imputation, feature transformations, estimator selection, hyper-parameter search and ensemble construction. Given the large, complex and heterogenous space of options, off-the-shelf optimization methods are infeasible for realistic response times. In practice, much of the predictive modeling process is conducted by experienced data scientists, who selectively make use of available tools. Over time, they develop an understanding of the behavior of operators, and perform serial decision making under uncertainty, colloquially referred to as educated guesswork. With an unprecedented demand for application of supervised machine learning, there is a call for solutions that automatically search for a good combination of parameters across these tasks to minimize the modeling error. We introduce a novel system called APRL (Autonomous Predictive modeler via Reinforcement Learning), that uses past experience through reinforcement learning to optimize such sequential decision making from within a set of diverse actions under a time constraint on a previously unseen predictive learning problem. APRL actions are taken to optimize the performance of a final ensemble. This is in contrast to other systems, which maximize individual model accuracy first and create ensembles as a disconnected post-processing step. As a result, APRL is able to reduce up to 71\% of classification error on average over a wide variety of problems.
Stability of decision trees and logistic regression
Venue: arXiv cs.LG 2019
Year: 2019

Decision trees and logistic regression are one of the most popular and well-known machine learning algorithms, frequently used to solve a variety of real-world problems. Stability of learning algorithms is a powerful tool to analyze their performance and sensitivity and subsequently allow researchers to draw reliable conclusions. The stability of these two algorithms has remained obscure. To that end, in this paper, we derive two stability notions for decision trees and logistic regression: hypothesis and pointwise hypothesis stability. Additionally, we derive these notions for L2-regularized logistic regression and confirm existing findings that it is uniformly stable. We show that the stability of decision trees depends on the number of leaves in the tree, i.e., its depth, while for logistic regression, it depends on the smallest eigenvalue of the Hessian matrix of the cross-entropy loss. We show that logistic regression is not a stable learning algorithm. We construct the upper bounds on the generalization error of all three algorithms. Moreover, we present a novel stability measuring framework that allows one to measure the aforementioned notions of stability. The measures are equivalent to estimates of expected loss differences at an input example and then leverage bootstrap sampling to yield statistically reliable estimates. Finally, we apply this framework to the three algorithms analyzed in this paper to confirm our theoretical findings and, in addition, we discuss the possibilities of developing new training techniques to optimize the stability of logistic regression, and hence decrease its generalization error.
Predicting Algorithm Classes for Programming Word Problems
Venue: arXiv cs.CL 2019
Year: 2019

We introduce the task of algorithm class prediction for programming word problems. A programming word problem is a problem written in natural language, which can be solved using an algorithm or a program. We define classes of various programming word problems which correspond to the class of algorithms required to solve the problem. We present four new datasets for this task, two multiclass datasets with 550 and 1159 problems each and two multilabel datasets having 3737 and 3960 problems each. We pose the problem as a text classification problem and train neural network and non-neural network-based models on this task. Our best performing classifier gets an accuracy of 62.7 percent for the multiclass case on the five class classification dataset, Codeforces Multiclass-5 (CFMC5). We also do some human-level analysis and compare human performance with that of our text classification models. Our best classifier has an accuracy only 9 percent lower than that of a human on this task. To the best of our knowledge, these are the first reported results on such a task. We make our code and datasets publicly available.
Multiple Learning for Regression in big data
Venue: arXiv cs.LG 2019
Year: 2019

Regression problems that have closed-form solutions are well understood and can be easily implemented when the dataset is small enough to be all loaded into the RAM. Challenges arise when data is too big to be stored in RAM to compute the closed form solutions. Many techniques were proposed to overcome or alleviate the memory barrier problem but the solutions are often local optimal. In addition, most approaches require accessing the raw data again when updating the models. Parallel computing clusters are also expected if multiple models need to be computed simultaneously. We propose multiple learning approaches that utilize an array of sufficient statistics (SS) to address this big data challenge. This memory oblivious approach breaks the memory barrier when computing regressions with closed-form solutions, including but not limited to linear regression, weighted linear regression, linear regression with Box-Cox transformation (Box-Cox regression) and ridge regression models. The computation and update of the SS array can be handled at per row level or per mini-batch level. And updating a model is as easy as matrix addition and subtraction. Furthermore, multiple SS arrays for different models can be easily computed simultaneously to obtain multiple models at one pass through the dataset. We implemented our approaches on Spark and evaluated over the simulated datasets. Results showed our approaches can achieve closed-form solutions of multiple models at the cost of half training time of the traditional methods for a single model.
Recognition of Multiple Food Items in a Single Photo for Use in a Buffet-Style Restaurant
Venue: arXiv cs.CV 2019
Year: 2019

We investigate image recognition of multiple food items in a single photo, focusing on a buffet restaurant application, where menu changes at every meal, and only a few images per class are available. After detecting food areas, we perform hierarchical recognition. We evaluate our results, comparing to two baseline methods.
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
Venue: arXiv cs.DC 2019
Year: 2019

Given parameters $α\geq 1,β\geq 0$, a subgraph $G'=(V,H)$ of an $n$-vertex unweighted undirected graph $G=(V,E)$ is called an $(α,β)$-spanner if for every pair $u,v\in V$ of vertices, $d_{G'}(u,v)\leq αd_{G}(u,v)+β$. If $β=0$ the spanner is called a multiplicative $α$-spanner, and if $α= 1+ε$, for an arbitrarily small $ε>0$, the spanner is said to be a near-additive one. Graph spanners are a fundamental and extremely well-studied combinatorial construct, with a multitude of applications in distributed computing and in other areas. Near-additive spanners, introduced in [EP01], preserve large distances much more faithfully than multiplicative spanners. Also, recent lower bounds [AB15] ruled out the existence of arbitrarily sparse purely additive spanners (i.e., spanners with $α=1$), and therefore near-additive spanners provide the best approximation of distances that one can hope for. Numerous distributed algorithms for constructing sparse near-additive spanners exist. In particular, there are now known efficient randomized algorithms in the CONGEST model that construct such spanners [EN17], and also there are efficient deterministic algorithms in the LOCAL model [DGPV09]. The only known deterministic CONGEST-model algorithm for the problem [Elk01] requires superlinear time in $n$. We remedy the situation and devise an efficient deterministic CONGEST-model algorithm for constructing arbitrarily sparse near-additive spanners. The running time of our algorithm is low polynomial, i.e., roughly $O(β\cdot n^ρ)$, where $ρ> 0$ is an arbitrarily small positive constant that affects the additive term $β$. In general, the parameters of our algorithm and of the resulting spanner are at the same ballpark as the respective parameters of the state-of-the-art randomized algorithm for the problem due to [EN17].
Robust corner and tangent point detection for strokes with deep learning approach
Venue: arXiv cs.CG 2019
Year: 2019

A robust corner and tangent point detection (CTPD) tool is critical for sketch-based engineering modeling. This paper proposes a robust CTPD approach for hand-drawn strokes with deep learning approach. Its robustness for users, stroke shapes and biased datasets is improved due to multiscaled point contexts and a vote scheme. Firstly, all stroke points are classified into segments by two deep learning networks, based on scaled point contexts which mimic human's perception. Then, a vote scheme is adopted to analyze the merge conditions and operations for adjacent segments. If most points agree with a stroke's type, this type is accepted. Finally, new corners and tangent points are inserted at transition points. The algorithm's performance is experimented with 1500 strokes of 20 shapes. Results show that our algorithm can achieve 95.3% for all-or-nothing accuracy and 88.6% accuracy for biased datasets, compared to 84.6% and 71% of the state-of-the-art CTPD technique, which is heuristic and empirical-based.
Modular specification of monads through higher-order presentations
Venue: arXiv cs.LO 2019
Year: 2019

In their work on second-order equational logic, Fiore and Hur have studied presentations of simply typed languages by generating binding constructions and equations among them. To each pair consisting of a binding signature and a set of equations, they associate a category of `models', and they give a monadicity result which implies that this category has an initial object, which is the language presented by the pair. In the present work, we propose, for the untyped setting, a variant of their approach where monads and modules over them are the central notions. More precisely, we study, for monads over sets, presentations by generating (`higher-order') operations and equations among them. We consider a notion of 2-signature which allows to specify a monad with a family of binding operations subject to a family of equations, as is the case for the paradigmatic example of the lambda calculus, specified by its two standard constructions (application and abstraction) subject to $β$- and $η$-equalities. Such a 2-signature is hence a pair $(Σ,E)$ of a binding signature $Σ$ and a family $E$ of equations for $Σ$. This notion of 2-signature has been introduced earlier by Ahrens in a slightly different context. We associate, to each 2-signature $(Σ,E)$, a category of `models of $(Σ,E)$; and we say that a 2-signature is `effective' if this category has an initial object; the monad underlying this (essentially unique) object is the `monad specified by the 2-signature'. Not every 2-signature is effective; we identify a class of 2-signatures, which we call `algebraic', that are effective. Importantly, our 2-signatures together with their models enjoy `modularity': when we glue (algebraic) 2-signatures together, their initial models are glued accordingly. We provide a computer formalization for our main results.
Practical Prediction of Human Movements Across Device Types and Spatiotemporal Granularities
Venue: arXiv cs.NI 2019
Year: 2019

Understanding and predicting mobility are essential for the design and evaluation of future mobile edge caching and networking. Consequently, research on prediction of human mobility has drawn significant attention in the last decade. Employing information-theoretic concepts and machine learning methods, earlier research has shown evidence that human behavior can be highly predictable. Despite existing studies, more investigations are needed to capture intrinsic mobility characteristics constraining predictability, and to explore more dimensions (e.g. device types) and spatio-temporal granularities, especially with the change in human behavior and technology. We analyze extensive longitudinal datasets with fine spatial granularity (AP level) covering 16 months. The study reveals device type as an important factor affecting predictability. Ultra-portable devices such as smartphones have "on-the-go" mode of usage (and hence dubbed "Flutes"), whereas laptops are "sit-to-use" (dubbed "Cellos"). The goal of this study is to investigate practical prediction mechanisms to quantify predictability as an aspect of human mobility modeling, across time, space and device types. We apply our systematic analysis to wireless traces from a large university campus. We compare several algorithms using varying degrees of temporal and spatial granularity for the two modes of devices; Flutes vs. Cellos. Through our analysis, we quantify how the mobility of Flutes is less predictable than the mobility of Cellos. In addition, this pattern is consistent across various spatio-temporal granularities, and for different methods (Markov chains, neural networks/deep learning, entropy-based estimators). This work substantiates the importance of predictability as an essential aspect of human mobility, with direct application in predictive caching, user behavior modeling and mobility simulations.
A Fundamental Performance Limitation for Adversarial Classification
Venue: arXiv cs.LG 2019
Year: 2019

Despite the widespread use of machine learning algorithms to solve problems of technological, economic, and social relevance, provable guarantees on the performance of these data-driven algorithms are critically lacking, especially when the data originates from unreliable sources and is transmitted over unprotected and easily accessible channels. In this paper we take an important step to bridge this gap and formally show that, in a quest to optimize their accuracy, binary classification algorithms -- including those based on machine-learning techniques -- inevitably become more sensitive to adversarial manipulation of the data. Further, for a given class of algorithms with the same complexity (i.e., number of classification boundaries), the fundamental tradeoff curve between accuracy and sensitivity depends solely on the statistics of the data, and cannot be improved by tuning the algorithm.
An FPT Algorithm for Minimum Additive Spanner Problem
Venue: arXiv cs.DS 2019
Year: 2019

For a positive integer $t$ and a graph $G$, an additive $t$-spanner of $G$ is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus $t$. Minimum Additive $t$-Spanner Problem is to find an additive $t$-spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive $t$-spanners, Minimum Additive $t$-Spanner Problem is hard to handle, and hence only few results are known for it. In this paper, we study Minimum Additive $t$-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to $(α, β)$-spanners.
Stochastic Online Learning with Probabilistic Graph Feedback
Venue: arXiv cs.LG 2019
Year: 2019

We consider a problem of stochastic online learning with general probabilistic graph feedback, where each directed edge in the feedback graph has probability $p_{ij}$. Two cases are covered. (a) The one-step case, where after playing arm $i$ the learner observes a sample reward feedback of arm $j$ with independent probability $p_{ij}$. (b) The cascade case where after playing arm $i$ the learner observes feedback of all arms $j$ in a probabilistic cascade starting from $i$ -- for each $(i,j)$ with probability $p_{ij}$, if arm $i$ is played or observed, then a reward sample of arm $j$ would be observed with independent probability $p_{ij}$. Previous works mainly focus on deterministic graphs which corresponds to one-step case with $p_{ij} \in \{0,1\}$, an adversarial sequence of graphs with certain topology guarantees, or a specific type of random graphs. We analyze the asymptotic lower bounds and design algorithms in both cases. The regret upper bounds of the algorithms match the lower bounds with high probability.
Automatic microscopic cell counting by use of deeply-supervised density regression model
Venue: arXiv cs.CV 2019
Year: 2019

Accurately counting cells in microscopic images is important for medical diagnoses and biological studies, but manual cell counting is very tedious, time-consuming, and prone to subjective errors, and automatic counting can be less accurate than desired. To improve the accuracy of automatic cell counting, we propose here a novel method that employs deeply-supervised density regression. A fully convolutional neural network (FCNN) serves as the primary FCNN for density map regression. Innovatively, a set of auxiliary FCNNs are employed to provide additional supervision for learning the intermediate layers of the primary CNN to improve network performance. In addition, the primary CNN is designed as a concatenating framework to integrate multi-scale features through shortcut connections in the network, which improves the granularity of the features extracted from the intermediate CNN layers and further supports the final density map estimation.
Complement Objective Training
Venue: arXiv cs.LG 2019
Year: 2019

Learning with a primary objective, such as softmax cross entropy for classification and sequence generation, has been the norm for training deep neural networks for years. Although being a widely-adopted approach, using cross entropy as the primary objective exploits mostly the information from the ground-truth class for maximizing data likelihood, and largely ignores information from the complement (incorrect) classes. We argue that, in addition to the primary objective, training also using a complement objective that leverages information from the complement classes can be effective in improving model performance. This motivates us to study a new training paradigm that maximizes the likelihood of the groundtruth class while neutralizing the probabilities of the complement classes. We conduct extensive experiments on multiple tasks ranging from computer vision to natural language understanding. The experimental results confirm that, compared to the conventional training with just one primary objective, training also with the complement objective further improves the performance of the state-of-the-art models across all tasks. In addition to the accuracy improvement, we also show that models trained with both primary and complement objectives are more robust to single-step adversarial attacks.
Low-cost VR Collaborative System equipped with Haptic Feedback
Venue: arXiv cs.HC 2019
Year: 2019

In this paper, we present a low-cost virtual reality (VR) collaborative system equipped with a haptic feedback sensation system. This system is composed of a Kinect sensor for bodies and gestures detection, a microcontroller and vibrators to simulate outside interactions, and smartphone powered cardboard, all of this are put into a network implemented with Unity 3D game engine. CCS CONCEPTS $\bullet$ Interaction paradigms $\rightarrow$ Virtual reality; Collaborative interaction; $\bullet$ Hardware $\rightarrow$ Sensors and actuators; Wireless devices; KEYWORDS collaborative virtual reality, haptic feedback system.
A Reliabel and an efficient web testing system
Venue: arXiv cs.SE 2019
Year: 2019

To improve the reliability and efficiency of Web Software, the Testing Team should be creative and innovative. The experience and intuition of Tester also matters a lot and most often the destructive nature of Tester brings reliable software to the user. Actually, Testing is the responsibility of everybody who is involved in the Project.