OpenRaiser/Intern-Atlas huggingface dataset:
How Many and What Types of SPARQL Queries can be Answered through Zero-Knowledge Link Traversal?
Venue: arXiv cs.DB 2018
Year: 2018

The current de-facto way to query the Web of Data is through the SPARQL protocol, where a client sends queries to a server through a SPARQL endpoint. Contrary to an HTTP server, providing and maintaining a robust and reliable endpoint requires a significant effort that not all publishers are willing or able to make. An alternative query evaluation method is through link traversal, where a query is answered by dereferencing online web resources (URIs) at real time. While several approaches for such a lookup-based query evaluation method have been proposed, there exists no analysis of the types (patterns) of queries that can be directly answered on the live Web, without accessing local or remote endpoints and without a-priori knowledge of available data sources. In this paper, we first provide a method for checking if a SPARQL query (to be evaluated on a SPARQL endpoint) can be answered through zero-knowledge link traversal (without accessing the endpoint), and analyse a large corpus of real SPARQL query logs for finding the frequency and distribution of answerable and non-answerable query patterns. Subsequently, we provide an algorithm for transforming answerable queries to SPARQL-LD queries that bypass the endpoints. We report experimental results about the efficiency of the transformed queries and discuss the benefits and the limitations of this query evaluation method.
The Use of Activity Trackers for Health Empowerment and Commitment: The Philippine Cycling Perspective
Venue: arXiv cs.HC 2018
Year: 2018

Activity tracking devices have found its way in the world of cycling. With its projected market demand and increasing popularity of cycling in the Philippines, cyclists are slowly adopting this technology in their daily cycling routines. Activity trackers demonstrate real-time data which allow cyclists to adjust physical efforts to achieve their personal goals. Six common features of activity trackers were formed as constructs to explore its influence on health empowerment in the context of cycling using Partial Least Squares Structural Equation Model. A total of 393 cyclists in the Philippines participated in the study. Some features demonstrated strong evidence of positive influence in achieving health empowerment and commitment. Implications for future design and development of this technology device are discussed.
Algorithms Inspired by Nature: A Survey
Venue: arXiv cs.NE 2018
Year: 2018

Nature is known to be the best optimizer. Natural processes most often than not reach an optimal equilibrium. Scientists have always strived to understand and model such processes.Thus, many algorithms exist today that are inspired by nature. Many of these algorithms and heuristics can be used to solve problems for which no polynomial time algorithms exist,such as Job Shop Scheduling and many other Combinatorial Optimization problems. We will discuss some of these algorithms and heuristics and how they help us solve complex problems of practical importance.
Forbidden Information
Venue: arXiv cs.CC 2018
Year: 2018

Goedel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Goedel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious and involves Kolmogorov complexity. (This is unrelated to, well studied before, complexity quantifications of the usual Goedel effects.) I consider extensions U of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any U either leaves an n-bit input (statement) unresolved or contains nearly all information about the n-bit prefix of any r.e. real r (which is n bits for some r). I argue that creating significant information about a SPECIFIC math sequence is impossible regardless of the methods used. Similar problems and answers apply to other unsolvability results for tasks allowing multiple solutions, e.g. non-recursive tilings.
Efficient Teamwork
Venue: arXiv cs.OH 2018
Year: 2018

Our goal is to solve both problems of adverse selection and moral hazard for multi-agent projects. In our model, each selected agent can work according to his private "capability tree". This means a process involving hidden actions, hidden chance events and hidden costs in a dynamic manner, and providing contractible consequences which are affecting each other's working process and the outcome of the project. We will construct a mechanism that induces truthful revelation of the agents' capability trees and chance events and to follow the instructions about their hidden decisions. This enables the planner to select the optimal subset of agents and obtain the efficient joint execution. We will construct another mechanism that is collusion-resistant but implements an only approximately efficient outcome. The latter mechanism is widely applicable, and the major application details will be elaborated.
P != NP Proof
Venue: arXiv cs.CC 2019
Year: 2019

This paper demonstrates that P \not= NP. The way was to generalize the traditional definitions of the classes P and NP, to construct an artificial problem (a generalization to SAT: The XG-SAT, much more difficult than the former) and then to demonstrate that it is in NP but not in P (where the classes P and NP are generalized and called too simply P and NP in this paper, and then it is explained why the traditional classes P and NP should be fixed and replaced by these generalized ones into Theory of Computer Science). The demonstration consists of: 1. Definition of Restricted Type X Program; 2. Definition of the General Extended Problem of Satisfiability of a Boolean Formula - XG-SAT; 3. Generalization to classes P and NP; 4. Demonstration that the XG-SAT is in NP; 5. Demonstration that the XG-SAT is not in P; 6. Demonstration that the Baker-Gill-Solovay Theorem does not refute the proof; 7. Demonstration that the Razborov-Rudich Theorem does not refute the proof; 8. Demonstration that the Aaronson-Wigderson Theorem does not refute the proof.
Computation of Spatial Skyline Points
Venue: arXiv cs.CG 2019
Year: 2019

We discuss a method of finding skyline or non-dominated sites in a set $P$ of $n$ point sites with respect to a set $S$ of $m$ points. A site $p \in P$ is non-dominated if and only if for each $q \in P \setminus \{p\}$, there exists at least one point $s \in S$ that is closer to $p$ than to $q$. We reduce this problem of determining non-dominated sites to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under a convex distance function. The weights of said Voronoi diagram are derived from the coordinates of the sites of $P$, while the convex distance function is derived from $S$. In the two-dimensional plane, this reduction gives an $O((n + m) \log (n + m))$-time algorithm to find the non-dominated points.
An Agent-based Simulation of the Effectiveness of Creative Leadership
Venue: arXiv cs.MA 2019
Year: 2019

This paper investigates the effectiveness of creative versus uncreative leadership using EVOC, an agent-based model of cultural evolution. Each iteration, each agent in the artificial society invents a new action, or imitates a neighbor's action. Only the leader's actions can be imitated by all other agents, referred to as followers. Two measures of creativity were used: (1) invention-to-imitation ratio, iLeader, which measures how often an agent invents, and (2) rate of conceptual change, cLeader, which measures how creative an invention is. High iLeader increased mean fitness of ideas, but only when creativity of followers was low. High iLeader was associated with greater diversity of ideas in the early stage of idea generation only. High cLeader increased mean fitness of ideas in the early stage of idea generation; in the later stage it decreased idea fitness. Reasons for these findings and tentative implications for creative leadership in human society are discussed.
Experiments with Infinite-Horizon, Policy-Gradient Estimation
Venue: arXiv cs.AI 2019
Year: 2019

In this paper, we present algorithms that perform gradient ascent of the average reward in a partially observable Markov decision process (POMDP). These algorithms are based on GPOMDP, an algorithm introduced in a companion paper (Baxter and Bartlett, this volume), which computes biased estimates of the performance gradient in POMDPs. The algorithm's chief advantages are that it uses only one free parameter beta, which has a natural interpretation in terms of bias-variance trade-off, it requires no knowledge of the underlying state, and it can be applied to infinite state, control and observation spaces. We show how the gradient estimates produced by GPOMDP can be used to perform gradient ascent, both with a traditional stochastic-gradient algorithm, and with an algorithm based on conjugate-gradients that utilizes gradient information to bracket maxima in line searches. Experimental results are presented illustrating both the theoretical results of (Baxter and Bartlett, this volume) on a toy problem, and practical aspects of the algorithms on a number of more realistic problems.
Deciding Word Problems of Semigroups using Finite State Automata
Venue: arXiv cs.FL 2019
Year: 2019

We explore a natural class of semigroups that have word problem decidable by finite state automata. Among the main results are invariance of this property under change of generators, invariance under basic algebraic constructions and algebraic properties of these semigroups.
Nearest Neighbor Value Interpolation
Venue: arXiv cs.GR 2019
Year: 2019

This paper presents the nearest neighbor value (NNV) algorithm for high resolution (H.R.) image interpolation. The difference between the proposed algorithm and conventional nearest neighbor algorithm is that the concept applied, to estimate the missing pixel value, is guided by the nearest value rather than the distance. In other words, the proposed concept selects one pixel, among four directly surrounding the empty location, whose value is almost equal to the value generated by the conventional bilinear interpolation algorithm. The proposed method demonstrated higher performances in terms of H.R. when compared to the conventional interpolation algorithms mentioned.
On binary quadratic symmetric bent and almost bent functions
Venue: arXiv cs.IT 2019
Year: 2019

We give a new simple construction for known binary quadratic symmetric bent and almost bent functions. In particular, for even number of variables, they are self-dual and anti-self-dual quadratic bent functions, respectively, which are not of the Maiorana-McFarland type, but affine equivalent to it.
Unsupervised model-free representation learning
Venue: arXiv cs.LG 2019
Year: 2019

Numerous control and learning problems face the situation where sequences of high-dimensional highly dependent data are available but no or little feedback is provided to the learner, which makes any inference rather challenging. To address this challenge, we formulate the following problem. Given a series of observations $X_0,\dots,X_n$ coming from a large (high-dimensional) space $\mathcal X$, find a representation function $f$ mapping $\mathcal X$ to a finite space $\mathcal Y$ such that the series $f(X_0),\dots,f(X_n)$ preserves as much information as possible about the original time-series dependence in $X_0,\dots,X_n$. We show that, for stationary time series, the function $f$ can be selected as the one maximizing a certain information criterion that we call time-series information. Some properties of this functions are investigated, including its uniqueness and consistency of its empirical estimates. Implications for the problem of optimal control are presented.
How Did Humans Become So Creative? A Computational Approach
Venue: arXiv cs.NE 2019
Year: 2019

This paper summarizes efforts to computationally model two transitions in the evolution of human creativity: its origins about two million years ago, and the 'big bang' of creativity about 50,000 years ago. Using a computational model of cultural evolution in which neural network based agents evolve ideas for actions through invention and imitation, we tested the hypothesis that human creativity began with onset of the capacity for recursive recall. We compared runs in which agents were limited to single-step actions to runs in which they used recursive recall to chain simple actions into complex ones. Chaining resulted in higher diversity, open-ended novelty, no ceiling on the mean fitness of actions, and greater ability to make use of learning. Using a computational model of portrait painting, we tested the hypothesis that the explosion of creativity in the Middle/Upper Paleolithic was due to onset of con-textual focus: the capacity to shift between associative and analytic thought. This resulted in faster convergence on portraits that resembled the sitter, employed painterly techniques, and were rated as preferable. We conclude that recursive recall and contextual focus provide a computationally plausible explanation of how humans evolved the means to transform this planet.
Should I Stay or Should I Go: Coordinating Biological Needs with Continuously-updated Assessments of the Environment
Venue: arXiv cs.NE 2019
Year: 2019

This paper presents Wanderer, a model of how autonomous adaptive systems coordinate internal biological needs with moment-by-moment assessments of the probabilities of events in the external world. The extent to which Wanderer moves about or explores its environment reflects the relative activations of two competing motivational sub-systems: one represents the need to acquire energy and it excites exploration, and the other represents the need to avoid predators and it inhibits exploration. The environment contains food, predators, and neutral stimuli. Wanderer responds to these events in a way that is adaptive in the short turn, and reassesses the probabilities of these events so that it can modify its long term behaviour appropriately. When food appears, Wanderer be-comes satiated and exploration temporarily decreases. When a predator appears, Wanderer both decreases exploration in the short term, and becomes more "cautious" about exploring in the future. Wanderer also forms associations between neutral features and salient ones (food and predators) when they are present at the same time, and uses these associations to guide its behaviour.
Dynamic Sliding Mode Control based on Fractional calculus subject to uncertain delay based chaotic pneumatic robot
Venue: arXiv cs.RO 2019
Year: 2019

This paper considers the chattering problem of sliding mode control while delay in robot manipulator caused chaos in such electromechanical systems. Fractional calculus as a powerful theorem to produce a novel sliding mode; which has a dynamic essence is used for chattering elimination. To realize the control of a class of chaotic systems in master-slave configuration this novel fractional dynamic sliding mode control scheme is presented and examined on delay based chaotic robot in joint and work space. Also the stability of the closed-loop system is guaranteed by Lyapunov stability theory. Beside these, delayed robot motions are sorted out for qualitative and quantification study. Finally, numerical simulation example illustrates the feasibility of proposed control method.
Linear Regression from Strategic Data Sources
Venue: arXiv cs.GT 2019
Year: 2019

Linear regression is a fundamental building block of statistical data analysis. It amounts to estimating the parameters of a linear model that maps input features to corresponding outputs. In the classical setting where the precision of each data point is fixed, the famous Aitken/Gauss-Markov theorem in statistics states that generalized least squares (GLS) is a so-called "Best Linear Unbiased Estimator" (BLUE). In modern data science, however, one often faces strategic data sources, namely, individuals who incur a cost for providing high-precision data. In this paper, we study a setting in which features are public but individuals choose the precision of the outputs they reveal to an analyst. We assume that the analyst performs linear regression on this dataset, and individuals benefit from the outcome of this estimation. We model this scenario as a game where individuals minimize a cost comprising two components: (a) an (agent-specific) disclosure cost for providing high-precision data; and (b) a (global) estimation cost representing the inaccuracy in the linear model estimate. In this game, the linear model estimate is a public good that benefits all individuals. We establish that this game has a unique non-trivial Nash equilibrium. We study the efficiency of this equilibrium and we prove tight bounds on the price of stability for a large class of disclosure and estimation costs. Finally, we study the estimator accuracy achieved at equilibrium. We show that, in general, Aitken's theorem does not hold under strategic data sources, though it does hold if individuals have identical disclosure costs (up to a multiplicative factor). When individuals have non-identical costs, we derive a bound on the improvement of the equilibrium estimation cost that can be achieved by deviating from GLS, under mild assumptions on the disclosure cost functions.
NILE: Fast Natural Language Processing for Electronic Health Records
Venue: arXiv cs.CL 2019
Year: 2019

Objective: Narrative text in Electronic health records (EHR) contain rich information for medical and data science studies. This paper introduces the design and performance of Narrative Information Linear Extraction (NILE), a natural language processing (NLP) package for EHR analysis that we share with the medical informatics community. Methods: NILE uses a modified prefix-tree search algorithm for named entity recognition, which can detect prefix and suffix sharing. The semantic analyses are implemented as rule-based finite state machines. Analyses include negation, location, modification, family history, and ignoring. Result: The processing speed of NILE is hundreds to thousands times faster than existing NLP software for medical text. The accuracy of presence analysis of NILE is on par with the best performing models on the 2010 i2b2/VA NLP challenge data. Conclusion: The speed, accuracy, and being able to operate via API make NILE a valuable addition to the NLP software for medical informatics and data science.
A Process Algebra for Games
Venue: arXiv cs.LO 2019
Year: 2019

Using formal tools in computer science to describe games is an interesting problem. We give games, exactly two person games, an axiomatic foundation based on the process algebra ACP (Algebra of Communicating Process). A fresh operator called opponent's alternative composition operator (OA) is introduced into ACP to describe game trees and game strategies, called GameACP. And its sound and complete axiomatic system is naturally established. To model the outcomes of games (the co-action of the player and the opponent), correspondingly in GameACP, the execution of GameACP processes, another operator called playing operator (PO) is extended into GameACP. We also establish a sound and complete axiomatic system for PO. To overcome the new occurred non-determinacy introduced by GameACP, we extend truly concurrent process algebra APTC for games called GameAPTC. Finally, we give the correctness theorem between the outcomes of games and the deductions of GameACP and GameAPTC processes.
Interaction Graphs: Exponentials
Venue: arXiv cs.LO 2019
Year: 2019

This paper is the fourth of a series exposing a systematic combinatorial approach to Girard's Geometry of Interaction (GoI) program. The GoI program aims at obtaining particular realisability models for linear logic that accounts for the dynamics of cut-elimination. This fourth paper tackles the complex issue of defining exponential connectives in this framework. For that purpose, we use the notion of \emph{graphings}, a generalisation of graphs which was defined in earlier work. We explain how to define a GoI for Elementary Linear Logic (ELL) with second-order quantification, a sub-system of linear logic that captures the class of elementary time computable functions.
On the Capacity Region of Broadcast Packet Erasure Relay Networks With Feedback
Venue: arXiv cs.IT 2019
Year: 2019

We derive a new outer bound on the capacity region of broadcast traffic in multiple input broadcast packet erasure channels with feedback, and extend this outer bound to packet erasure relay networks with feedback. We show the tightness of the outer bound for various classes of networks. An important engineering implication of this work is that for network coding schemes for parallel broadcast channels, the `xor' packets should be sent over correlated broadcast subchannels.
Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards
Venue: arXiv cs.LG 2019
Year: 2019

In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize his cumulative expected earnings over some given horizon of play T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation); the price paid due to this trade off is often referred to as the regret, and the main question is how small can this price be as a function of the horizon length T. This problem has been studied extensively when the reward distributions do not change over time; an assumption that supports a sharp characterization of the regret, yet is often violated in practical settings. In this paper, we focus on a MAB formulation which allows for a broad range of temporal uncertainties in the rewards, while still maintaining mathematical tractability. We fully characterize the (regret) complexity of this class of MAB problems by establishing a direct link between the extent of allowable reward "variation" and the minimal achievable regret. Our analysis draws some connections between two rather disparate strands of literature: the adversarial and the stochastic MAB frameworks.
Price of Anarchy with Heterogeneous Latency Functions
Venue: arXiv cs.GT 2019
Year: 2019

In this paper we consider the price of anarchy (PoA) in multi-commodity flows where the latency or delay function on an edge has a heterogeneous dependency on the flow commodities, i.e. when the delay on each link is dependent on the flow of individual commodities, rather than on the aggregate flow. An application of this study is the performance analysis of a network with differentiated traffic that may arise when traffic is prioritized according to some type classification. This study has implications in the debate on net-neutrality. We provide price of anarchy bounds for networks with $k$ (types of) commodities where each link is associated with heterogeneous polynomial delays, i.e. commodity $i$ on edge $e$ faces delay specified by $g_{i1}(e)f^θ_1(e) + g_{i2}(e)f^θ_2(e) + \ldots + g_{ik}(e)f^θ_k(e) + c_i(e), $ where $f_i(e)$ is the flow of the $i$th commodity through edge $e$, $θ\in {\cal N}$, $g_{i1}(e), g_{i2}(e), \ldots, g_{ik}(e)$ and $c_i(e)$ are nonnegative constants. We consider both atomic and non-atomic flows. For networks with decomposable delay functions where the delay induced by a particular commodity is the same, i.e. delays on edge $e$ are defined by $a_1(e)f_1^θ(e) + a_2(e)f_2^θ(e) + \ldots + c(e)$ where $\forall j , \forall e: g_{1j}(e) = g_{2j}(e) = \ldots = a_j(e)$, we show an improved bound on the price of anarchy. Further, we show bounds on the price of anarchy for uniform latency functions where each edge of the network has the same delay function.