OpenRaiser/Intern-Atlas huggingface dataset:
Simple Surveys: Response Retrieval Inspired by Recommendation Systems
Venue: arXiv cs.SI 2018
Year: 2018

In the last decade, the use of simple rating and comparison surveys has proliferated on social and digital media platforms to fuel recommendations. These simple surveys and their extrapolation with machine learning algorithms shed light on user preferences over large and growing pools of items, such as movies, songs and ads. Social scientists have a long history of measuring perceptions, preferences and opinions, often over smaller, discrete item sets with exhaustive rating or ranking surveys. This paper introduces simple surveys for social science application. We ran experiments to compare the predictive accuracy of both individual and aggregate comparative assessments using four types of simple surveys: pairwise comparisons and ratings on 2, 5 and continuous point scales in three distinct contexts: perceived Safety of Google Streetview Images, Likeability of Artwork, and Hilarity of Animal GIFs. Across contexts, we find that continuous scale ratings best predict individual assessments but consume the most time and cognitive effort. Binary choice surveys are quick and perform best to predict aggregate assessments, useful for collective decision tasks, but poorly predict personalized preferences, for which they are currently used by Netflix to recommend movies. Pairwise comparisons, by contrast, perform well to predict personal assessments, but poorly predict aggregate assessments despite being widely used to crowdsource ideas and collective preferences. We demonstrate how findings from these surveys can be visualized in a low-dimensional space that reveals distinct respondent interpretations of questions asked in each context. We conclude by reflecting on differences between sparse, incomplete simple surveys and their traditional survey counterparts in terms of efficiency, information elicited and settings in which knowing less about more may be critical for social science.
Measuring the Robustness of Graph Properties
Venue: arXiv cs.SI 2018
Year: 2018

In this paper, we propose a perturbation framework to measure the robustness of graph properties. Although there are already perturbation methods proposed to tackle this problem, they are limited by the fact that the strength of the perturbation cannot be well controlled. We firstly provide a perturbation framework on graphs by introducing weights on the nodes, of which the magnitude of perturbation can be easily controlled through the variance of the weights. Meanwhile, the topology of the graphs are also preserved to avoid uncontrollable strength in the perturbation. We then extend the measure of robustness in the robust statistics literature to the graph properties.
Base Station Distance Adaptive LEACH
Venue: arXiv cs.DC 2018
Year: 2018

For some applications, we need to deploy a network of sensors in working field to sense the environment and send collected data to a base station for processing; these sensors depend on non-rechargeable batteries, so the routing protocols for such network of sensors need to be efficient. LEACH is one of these protocols which is a hierarchical routing protocol and helps in saving energy in wireless sensor networks. Enhanced LEACH depends on a mathematical model to calculate the estimated average energy in each round. consequently, utilizing the node remaining energy to ensure rotating cluster head role over all the nodes. It also depends on a mathematical model to calculate base station distance from work field whereas LEACH does not take into its account any consideration for remaining energy of node. In this paper, we enhance LEACH (work efficiency in homogeneous networks) to adapt with base-station distance, thus more energy saving for certain distances from base-station. The obtained simulation results show that enhanced LEACH saves energy better than LEACH and increase network stability and reliability when base-station is inside working field and consume the same energy as LEACH when base-station is outside work field.
Evolutionary framework for two-stage stochastic resource allocation problems
Venue: arXiv cs.NE 2018
Year: 2018

Resource allocation problems are a family of problems in which resources must be selected to satisfy given demands. This paper focuses on the two-stage stochastic generalization of resource allocation problems where future demands are expressed in a finite number of possible scenarios. The goal is to select cost effective resources to be acquired in the present time (first stage), and to implement a complete solution for each scenario (second stage), while minimizing the total expected cost of the choices in both stages. We propose an evolutionary framework for solving general two-stage stochastic resource allocation problems. In each iteration of our framework, a local search algorithm selects resources to be acquired in the first stage. A genetic metaheuristic then completes the solutions for each scenario and relevant information is passed onto the next iteration, thereby supporting the acquisition of promising resources in the following first stage. Experimentation on numerous instances of the two-stage stochastic Steiner tree problem suggests that our evolutionary framework is powerful enough to address large instances of a wide variety of two-stage stochastic resource allocation problems.
Design of statistical quality control procedures using genetic algorithms
Venue: arXiv cs.NE 2018
Year: 2018

In general, we can not use algebraic or enumerative methods to optimize a quality control (QC) procedure so as to detect the critical random and systematic analytical errors with stated probabilities, while the probability for false rejection is minimum. Genetic algorithms (GAs) offer an alternative, as they do not require knowledge of the objective function to be optimized and search through large parameter spaces quickly. To explore the application of GAs in statistical QC, we have developed an interactive GAs based computer program that designs a novel near optimal QC procedure, given an analytical process. The program uses the deterministic crowding algorithm. An illustrative application of the program suggests that it has the potential to design QC procedures that are significantly better than 45 alternative ones that are used in the clinical laboratories.
Nearly optimal exploration-exploitation decision thresholds
Venue: arXiv cs.AI 2018
Year: 2018

While in general trading off exploration and exploitation in reinforcement learning is hard, under some formulations relatively simple solutions exist. In this paper, we first derive upper bounds for the utility of selecting different actions in the multi-armed bandit setting. Unlike the common statistical upper confidence bounds, these explicitly link the planning horizon, uncertainty and the need for exploration explicit. The resulting algorithm can be seen as a generalisation of the classical Thompson sampling algorithm. We experimentally test these algorithms, as well as $ε$-greedy and the value of perfect information heuristics. Finally, we also introduce the idea of bagging for reinforcement learning. By employing a version of online bootstrapping, we can efficiently sample from an approximate posterior distribution.
Dependence Structure Estimation via Copula
Venue: arXiv cs.LG 2019
Year: 2019

Dependence strucuture estimation is one of the important problems in machine learning domain and has many applications in different scientific areas. In this paper, a theoretical framework for such estimation based on copula and copula entropy -- the probabilistic theory of representation and measurement of statistical dependence, is proposed. Graphical models are considered as a special case of the copula framework. A method of the framework for estimating maximum spanning copula is proposed. Due to copula, the method is irrelevant to the properties of individual variables, insensitive to outlier and able to deal with non-Gaussianity. Experiments on both simulated data and real dataset demonstrated the effectiveness of the proposed method.
Recognizability of Individual Creative Style Within and Across Domains: Preliminary Studies
Venue: arXiv cs.AI 2019
Year: 2019

It is hypothesized that creativity arises from the self-mending capacity of an internal model of the world, or worldview. The uniquely honed worldview of a creative individual results in a distinctive style that is recognizable within and across domains. It is further hypothesized that creativity is domaingeneral in the sense that there exist multiple avenues by which the distinctiveness of one's worldview can be expressed. These hypotheses were tested using art students and creative writing students. Art students guessed significantly above chance both which painting was done by which of five famous artists, and which artwork was done by which of their peers. Similarly, creative writing students guessed significantly above chance both which passage was written by which of five famous writers, and which passage was written by which of their peers. These findings support the hypothesis that creative style is recognizable. Moreover, creative writing students guessed significantly above chance which of their peers produced particular works of art, supporting the hypothesis that creative style is recognizable not just within but across domains.
Infinite-Horizon Policy-Gradient Estimation
Venue: arXiv cs.AI 2019
Year: 2019

Gradient-based approaches to direct policy search in reinforcement learning have received much recent attention as a means to solve problems of partial observability and to avoid some of the problems associated with policy degradation in value-function methods. In this paper we introduce GPOMDP, a simulation-based algorithm for generating a {\em biased} estimate of the gradient of the {\em average reward} in Partially Observable Markov Decision Processes (POMDPs) controlled by parameterized stochastic policies. A similar algorithm was proposed by Kimura, Yamamura, and Kobayashi (1995). The algorithm's chief advantages are that it requires storage of only twice the number of policy parameters, uses one free parameter $β\in [0,1)$ (which has a natural interpretation in terms of bias-variance trade-off), and requires no knowledge of the underlying state. We prove convergence of GPOMDP, and show how the correct choice of the parameter $β$ is related to the {\em mixing time} of the controlled POMDP. We briefly describe extensions of GPOMDP to controlled Markov chains, continuous state, observation and control spaces, multiple-agents, higher-order derivatives, and a version for training stochastic policies with internal states. In a companion paper (Baxter, Bartlett, & Weaver, 2001) we show how the gradient estimates generated by GPOMDP can be used in both a traditional stochastic gradient algorithm and a conjugate-gradient procedure to find local optima of the average reward
Block-Relaxation Methods for 3D Constant-Coefficient Stencils on GPUs and Multicore CPUs
Venue: arXiv cs.DC 2019
Year: 2019

Block iterative methods are extremely important as smoothers for multigrid methods, as preconditioners for Krylov methods, and as solvers for diagonally dominant linear systems. Developing robust and efficient algorithms suitable for current and evolving GPU and multicore CPU systems is a significant challenge. We address this issue in the case of constant-coefficient stencils arising in the solution of elliptic partial differential equations on structured 3D uniform and adaptively refined grids. Robust, highly parallel implementations of block Jacobi and chaotic block Gauss-Seidel algorithms with exact inversion of the blocks are developed using different parallelization techniques. Experimental results for NVIDIA Fermi GPUs and AMD multicore systems are presented.
General Truthfulness Characterizations Via Convex Analysis
Venue: arXiv cs.GT 2019
Year: 2019

We present a model of truthful elicitation which generalizes and extends mechanisms, scoring rules, and a number of related settings that do not qualify as one or the other. Our main result is a characterization theorem, yielding characterizations for all of these settings, including a new characterization of scoring rules for non-convex sets of distributions. We generalize this model to eliciting some property of the agent's private information, and provide the first general characterization for this setting. We combine this characterization with duality to give a simple construction to convert between scoring rules and randomized mechanisms. We also show how this characterization gives a new proof of a mechanism design result due to Saks and Yu.
Logarithmic Space and Permutations
Venue: arXiv cs.LO 2019
Year: 2019

In a recent work, Girard proposed a new and innovative approach to computational complexity based on the proofs-as-programs correspondence. In a previous paper, the authors showed how Girard proposal succeeds in obtaining a new characterization of co-NL languages as a set of operators acting on a Hilbert Space. In this paper, we extend this work by showing that it is also possible to define a set of operators characterizing the class L of logarithmic space languages.
Adaptive experiment design for LTI systems
Venue: arXiv cs.SY 2019
Year: 2019

Optimal experiment design for parameter estimation is a research topic that has been in the interest of various studies. A key problem in optimal input design is that the optimal input depends on some unknown system parameters that are to be identified. Adaptive design is one of the fundamental routes to handle this problem. Although there exist a rich collection of results on adaptive experiment design, there are few results that address these issues for dynamic systems. This paper proposes an adaptive input design method for general single-input single-output linear-time-invariant systems.
Bandits and Experts in Metric Spaces
Venue: arXiv cs.DS 2019
Year: 2019

In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a solution for the multi-armed bandit problem in this setting. That is, for every metric space we define an isometry invariant which bounds from below the performance of Lipschitz MAB algorithms for this metric space, and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. We also address the full-feedback ("best expert") version of the problem, where after every round the payoffs from all arms are revealed.
Kernel-Based Adaptive Online Reconstruction of Coverage Maps With Side Information
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we address the problem of reconstructing coverage maps from path-loss measurements in cellular networks. We propose and evaluate two kernel-based adaptive online algorithms as an alternative to typical offline methods. The proposed algorithms are application-tailored extensions of powerful iterative methods such as the adaptive projected subgradient method and a state-of-the-art adaptive multikernel method. Assuming that the moving trajectories of users are available, it is shown how side information can be incorporated in the algorithms to improve their convergence performance and the quality of the estimation. The complexity is significantly reduced by imposing sparsity-awareness in the sense that the algorithms exploit the compressibility of the measurement data to reduce the amount of data which is saved and processed. Finally, we present extensive simulations based on realistic data to show that our algorithms provide fast, robust estimates of coverage maps in real-world scenarios. Envisioned applications include path-loss prediction along trajectories of mobile users as a building block for anticipatory buffering or traffic offloading.
Tight Bounds on $\ell_1$ Approximation and Learning of Self-Bounding Functions
Venue: arXiv cs.LG 2019
Year: 2019

We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube ${0,1}^n$. Informally, a function $f:{0,1}^n \rightarrow \mathbb{R}$ is self-bounding if for every $x \in {0,1}^n$, $f(x)$ upper bounds the sum of all the $n$ marginal decreases in the value of the function at $x$. Self-bounding functions include such well-known classes of functions as submodular and fractionally-subadditive (XOS) functions. They were introduced by Boucheron et al. (2000) in the context of concentration of measure inequalities. Our main result is a nearly tight $\ell_1$-approximation of self-bounding functions by low-degree juntas. Specifically, all self-bounding functions can be $ε$-approximated in $\ell_1$ by a polynomial of degree $\tilde{O}(1/ε)$ over $2^{\tilde{O}(1/ε)}$ variables. We show that both the degree and junta-size are optimal up to logarithmic terms. Previous techniques considered stronger $\ell_2$ approximation and proved nearly tight bounds of $Θ(1/ε^{2})$ on the degree and $2^{Θ(1/ε^2)}$ on the number of variables. Our bounds rely on the analysis of noise stability of self-bounding functions together with a stronger connection between noise stability and $\ell_1$ approximation by low-degree polynomials. This technique can also be used to get tighter bounds on $\ell_1$ approximation by low-degree polynomials and faster learning algorithm for halfspaces. These results lead to improved and in several cases almost tight bounds for PAC and agnostic learning of self-bounding functions relative to the uniform distribution. In particular, assuming hardness of learning juntas, we show that PAC and agnostic learning of self-bounding functions have complexity of $n^{\tildeΘ(1/ε)}$.
A note on the relation between XOR and Selective XOR Lemmas
Venue: arXiv cs.CC 2019
Year: 2019

Given an unpredictable Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$, the standard Yao's XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in [k]}f(x_i)$ given $x_1, ..., x_k \in \{0, 1\}^n$, whereas the Selective XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in S}f(x_i)$ given $x_1, ..., x_k \in \{0, 1\}^n$ and $S \subseteq \{1, ..., k\}$. We give a reduction from the Selective XOR lemma to the standard XOR lemma. Our reduction gives better quantitative bounds for certain choice of parameters and does not require the assumption of being able to sample $(x, f(x))$ pairs.
Extending the Applicability Condition in the Formal System $λδ$
Venue: arXiv cs.LO 2019
Year: 2019

The formal system $λδ$ is a typed lambda calculus derived from $Λ_\infty$, aiming to support the foundations of Mathematics that require an underlying theory of expressions (for example the Minimal Type Theory). The system is developed in the context of the Hypertextual Electronic Library of Mathematics as a machine-checked digital specification, that is not the formal counterpart of previous informal material. The first version of the calculus appeared in 2006 and proved unsatisfactory for some reasons. In this article we present a revised version of the system and we prove three relevant desired properties: the confluence of reduction, the strong normalization of an extended form of reduction, known as the "big tree" theorem, and the preservation of validity by reduction. To our knowledge, we are presenting here the first fully machine-checked proof of the "big tree" theorem for a calculus that includes $Λ_\infty$.
User Session Identification Based on Strong Regularities in Inter-activity Time
Venue: arXiv cs.HC 2019
Year: 2019

Session identification is a common strategy used to develop metrics for web analytics and behavioral analyses of user-facing systems. Past work has argued that session identification strategies based on an inactivity threshold is inherently arbitrary or advocated that thresholds be set at about 30 minutes. In this work, we demonstrate a strong regularity in the temporal rhythms of user initiated events across several different domains of online activity (incl. video gaming, search, page views and volunteer contributions). We describe a methodology for identifying clusters of user activity and argue that regularity with which these activity clusters appear implies a good rule-of-thumb inactivity threshold of about 1 hour. We conclude with implications that these temporal rhythms may have for system design based on our observations and theories of goal-directed human activity.
Software Safety Demonstration and Idemnification
Venue: arXiv cs.LO 2019
Year: 2019

Computers may control safety-critical operations in machines having embedded software. This memoir proposes a regimen to verify such algorithms at prescribed levels of statistical confidence. The United States Department of Defense standard for system safety engineering (MIL-STD-882E) defines development procedures for safety-critical systems. However, a problem exists: the Standard fails to distinguish quantitative product assurance technique from categorical process assurance method for software development. Resulting is conflict in the technical definition of the term risk. The primary goal here is to show that a quantitative risk-based product assurance method exists and is consistent with hardware practice. Discussion appears in two major parts: theory, which shows the relationship between automata and software; and application, which covers demonstration and indemnification. Demonstration is a technique for generating random tests; indemnification converts pass/fail test results to compound Poisson parameters (severity and intensity). Together, demonstration and indemnification yield statistical confidence that safety-critical code meets design intent. Statistical confidence is the keystone of quantitative product assurance. A secondary goal is resolving the conflict over the term risk. The first meaning is an accident model known in mathematics as the compound Poisson stochastic process, and so is called statistical risk. Various of its versions underlie the theories of safety and reliability. The second is called developmental risk. It considers software autonomy, which considers time until manual recovery of control. Once these meanings are separated, MIL-STD-882 can properly support either formal quantitative safety assurance or empirical process robustness, which differ in impact.
On First-Order Model-Based Reasoning
Venue: arXiv cs.AI 2019
Year: 2019

Reasoning semantically in first-order logic is notoriously a challenge. This paper surveys a selection of semantically-guided or model-based methods that aim at meeting aspects of this challenge. For first-order logic we touch upon resolution-based methods, tableaux-based methods, DPLL-inspired methods, and we give a preview of a new method called SGGS, for Semantically-Guided Goal-Sensitive reasoning. For first-order theories we highlight hierarchical and locality-based methods, concluding with the recent Model-Constructing satisfiability calculus.