OpenRaiser/Intern-Atlas huggingface dataset:
A Latent Variable Model Approach to PMI-based Word Embeddings
Venue: arXiv cs.LG 2019
Year: 2019

Semantic word embeddings represent the meaning of a word via a vector, and are created by diverse methods. Many use nonlinear operations on co-occurrence statistics, and have hand-tuned hyperparameters and reweighting methods. This paper proposes a new generative model, a dynamic version of the log-linear topic model of~\citet{mnih2007three}. The methodological novelty is to use the prior to compute closed form expressions for word statistics. This provides a theoretical justification for nonlinear models like PMI, word2vec, and GloVe, as well as some hyperparameter choices. It also helps explain why low-dimensional semantic embeddings contain linear algebraic structure that allows solution of word analogies, as shown by~\citet{mikolov2013efficient} and many subsequent papers. Experimental support is provided for the generative model assumptions, the most important of which is that latent word vectors are fairly uniformly dispersed in space.
Bayesian Incentive-Compatible Bandit Exploration
Venue: arXiv cs.GT 2019
Year: 2019

Individual decision-makers consume information revealed by the previous decision makers, and produce information that may help in future decisions. This phenomenon is common in a wide range of scenarios in the Internet economy, as well as in other domains such as medical decisions. Each decision-maker would individually prefer to "exploit": select an action with the highest expected reward given her current information. At the same time, each decision-maker would prefer previous decision-makers to "explore", producing information about the rewards of various actions. A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance the exploration and exploitation so as to maximize social welfare. We formulate this problem as a multi-armed bandit problem (and various generalizations thereof) under incentive-compatibility constraints induced by the agents' Bayesian priors. We design an incentive-compatible bandit algorithm for the social planner whose regret is asymptotically optimal among all bandit algorithms (incentive-compatible or not). Further, we provide a black-box reduction from an arbitrary multi-arm bandit algorithm to an incentive-compatible one, with only a constant multiplicative increase in regret. This reduction works for very general bandit setting that incorporate contexts and arbitrary auxiliary feedback.
Binary Embedding: Fundamental Limits and Fast Algorithm
Venue: arXiv cs.DS 2019
Year: 2019

Binary embedding is a nonlinear dimension reduction methodology where high dimensional data are embedded into the Hamming cube while preserving the structure of the original space. Specifically, for an arbitrary $N$ distinct points in $\mathbb{S}^{p-1}$, our goal is to encode each point using $m$-dimensional binary strings such that we can reconstruct their geodesic distance up to $δ$ uniform distortion. Existing binary embedding algorithms either lack theoretical guarantees or suffer from running time $O\big(mp\big)$. We make three contributions: (1) we establish a lower bound that shows any binary embedding oblivious to the set of points requires $m = Ω(\frac{1}{δ^2}\log{N})$ bits and a similar lower bound for non-oblivious embeddings into Hamming distance; (2) [DELETED, see comment]; (3) we also provide an analytic result about embedding a general set of points $K \subseteq \mathbb{S}^{p-1}$ with even infinite size. Our theoretical findings are supported through experiments on both synthetic and real data sets.
Communicating with Beeps
Venue: arXiv cs.DC 2019
Year: 2019

The \emph{beep model} is a very weak communications model in which devices in a network can communicate only via beeps and silence. As a result of its weak assumptions, it has broad applicability to many different implementations of communications networks. This comes at the cost of a restrictive environment for algorithm design. Despite being only recently introduced, the beep model has received considerable attention, in part due to its relationship with other communication models such as that of ad-hoc radio networks. However, there has been no definitive published result for several fundamental tasks in the model. We aim to rectify this with our paper. We present algorithms and lower bounds for a variety of fundamental global communications tasks in the model.
Dynamic Service Migration in Mobile Edge Computing Based on Markov Decision Process
Venue: arXiv cs.DC 2019
Year: 2019

In mobile edge computing, local edge servers can host cloud-based services, which reduces network overhead and latency but requires service migrations as users move to new locations. It is challenging to make migration decisions optimally because of the uncertainty in such a dynamic cloud environment. In this paper, we formulate the service migration problem as a Markov Decision Process (MDP). Our formulation captures general cost models and provides a mathematical framework to design optimal service migration policies. In order to overcome the complexity associated with computing the optimal policy, we approximate the underlying state space by the distance between the user and service locations. We show that the resulting MDP is exact for uniform one-dimensional user mobility while it provides a close approximation for uniform two-dimensional mobility with a constant additive error. We also propose a new algorithm and a numerical technique for computing the optimal solution which is significantly faster than traditional methods based on standard value or policy iteration. We illustrate the application of our solution in practical scenarios where many theoretical assumptions are relaxed. Our evaluations based on real-world mobility traces of San Francisco taxis show superior performance of the proposed solution compared to baseline solutions.
Non-Metric Space Library Manual
Venue: arXiv cs.MS 2019
Year: 2019

This document covers a library for fast similarity (k-NN)search. It describes only search methods and distances (spaces). Details about building, installing, Python bindings can be found online:https://github.com/searchivarius/nmslib/tree/v1.8/. Even though the library contains a variety of exact metric-space access methods, our main focus is on more generic and approximate search methods, in particular, on methods for non-metric spaces. NMSLIB is possibly the first library with a principled support for non-metric space searching.
Software Agents with Concerns of their Own
Venue: arXiv cs.AI 2019
Year: 2019

We claim that it is possible to have artificial software agents for which their actions and the world they inhabit have first-person or intrinsic meanings. The first-person or intrinsic meaning of an entity to a system is defined as its relation with the system's goals and capabilities, given the properties of the environment in which it operates. Therefore, for a system to develop first-person meanings, it must see itself as a goal-directed actor, facing limitations and opportunities dictated by its own capabilities, and by the properties of the environment. The first part of the paper discusses this claim in the context of arguments against and proposals addressing the development of computer programs with first-person meanings. A set of definitions is also presented, most importantly the concepts of cold and phenomenal first-person meanings. The second part of the paper presents preliminary proposals and achievements, resulting of actual software implementations, within a research approach that aims to develop software agents that intrinsically understand their actions and what happens to them. As a result, an agent with no a priori notion of its goals and capabilities, and of the properties of its environment acquires all these notions by observing itself in action. The cold first-person meanings of the agent's actions and of what happens to it are defined using these acquired notions. Although not solving the full problem of first-person meanings, the proposed approach and preliminary results allow us some confidence to address the problems yet to be considered, in particular the phenomenal aspect of first-person meanings.
Estimating the Degree Centrality Ranking of a Node
Venue: arXiv cs.SI 2019
Year: 2019

Complex networks have gained more attention from the last few years. The size of real-world complex networks, such as online social networks, WWW network, collaboration networks, is increasing exponentially with time. It is not feasible to collect the complete data and store and process it. In the present work, we propose a method to estimate the degree centrality rank of a node without having the complete structure of the graph. The proposed algorithm uses the degree of a node and power-law exponent of the degree distribution to calculate the ranking. Simulation results on the Barabasi-Albert networks show that the average error in the estimated ranking is approximately $5\%$ of the total number of nodes.
A Geometric Structure Associated with the Convex Polygon
Venue: arXiv cs.CG 2019
Year: 2019

We propose a geometric structure induced by any given convex polygon $P$, called $Nest(P)$, which is an arrangement of $Θ(n^2)$ line segments, each of which is parallel to an edge of $P$, where $n$ denotes the number of edges of $P$. We then deduce six nontrivial properties of $Nest(P)$ from the convexity of $P$ and the parallelism of the line segments in $Nest(P)$. Among others, we show that $Nest(P)$ is a subdivision of the exterior of $P$, and its inner boundary interleaves the boundary of $P$. They manifest that $Nest(P)$ has a surprisingly good interaction with the boundary of $P$. Furthermore, we study some computational problems on $Nest(P)$. In particular, we consider three kinds of location queries on $Nest(P)$ and answer each of them in (amortized) $O(\log^2n)$ time. Our algorithm for answering these queries avoids an explicit construction of $Nest(P)$, which would take $Ω(n^2)$ time. By applying the aforementioned six properties altogether, we find that the geometric optimization problem of finding the maximum area parallelogram(s) in $P$ can be reduced to answering $O(n)$ aforementioned location queries, and thus be solved in $O(n\log^2n)$ time. This application will be reported in a subsequent paper.
Communicating Correlated Sources over MAC and Interference Channels I : Separation-based schemes
Venue: arXiv cs.IT 2019
Year: 2019

We consider the two scenarios of communicating a pair $S_{1},S_{2}$ of correlated sources over multiple access (MAC) and interference channels (IC) respectively. We undertake a Shannon theoretic study and focus on achievability, i.e., characterizing sufficient conditions. In the absence of a Gaćs-Körner-Witsenhausen common part, the current known single-letter (S-L) coding schemes are constrained to the S-L long Markov Chain (LMC) $X_{1}-S_{1}-S_{2}-X_{2}$. Taking the lead of Dueck's example [Dueck, Mar 1981], we recognize that the latter constraint is debilitating, leading to sub-optimality of S-L coding schemes. The goal of our work is to design a coding scheme wherein (i) the choice of channel input at time $t$ is based on multiple source symbols, and is yet ii) amenable to performance characterization via S-L expressions. In this article, we present the first part of our findings. We propose a new separation-based coding scheme based on a fixed block-length (B-L) codes that enables choice of $X_{jt}$ - the symbol input on the channel by encoder $j$ at time $t$ - to be based on a generic number $l$ of source symbols $S_{j}^{l}$, thus permitting correlation of the input symbols $X_{1},X_{2}$ through a multi-letter LMC $X_{1}-S_{1}^{l}-S_{2}^{l}-X_{2}$. By carefully stitching together S-L coding techniques we devise a multi-letter coding scheme. We characterize an inner bound to its performance via a S-L expression and prove that the derived inner bound is strictly larger than the current known largest inner bounds for both the MAC and IC problems based on S-L coding schemes. In the second part of our work, we propose to enlarge the inner bound derived in this article by incorporating the technique of inducing source correlation onto channel inputs [Cover, El Gamal and Salehi, Nov 1980].
Supervisor Localization of Timed Discrete-Event Systems under Partial Observation and Communication Delay
Venue: arXiv cs.SY 2019
Year: 2019

We study supervisor localization for timed discrete-event systems under partial observation and communication delay in the Brandin-Wonham framework. First, we employ timed relative observability to synthesize a partial-observation monolithic supervisor; the control actions of this supervisor include not only disabling action of prohibitible events (as that of controllable events in the untimed case) but also "clock-preempting" action of forcible events. Accordingly we decompose the supervisor into a set of partial-observation local controllers one for each prohibitible event, as well as a set of partial-observation local preemptors one for each forcible event. We prove that these local controllers and preemptors collectively achieve the same controlled behavior as the partial-observation monolithic supervisor does. Moreover, we propose channel models for inter-agent event communication and impose bounded and unbounded delay as temporal specifications. In this formulation, there exist multiple distinct observable event sets; thus we employ timed relative coobservability to synthesize partial-observation decentralized supervisors, and then localize these supervisors into local controllers and preemptors. The above results are illustrated by a timed workcell example.
Extension Complexity of Formal Languages
Venue: arXiv cs.CC 2019
Year: 2019

In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary languages. This allows us to define the notion of extension complexity of formal languages. We prove several closure properties of languages admitting compact extended formulations. Furthermore, we give a sufficient machine characterization of compact languages. We demonstrate the utility of this machine characterization by obtaining upper bounds for polytopes for problems in nondeterministic logspace; lower bounds in streaming models; and upper bounds on extension complexities of several polytopes.
Semantic 3D Reconstruction with Continuous Regularization and Ray Potentials Using a Visibility Consistency Constraint
Venue: arXiv cs.CV 2019
Year: 2019

We propose an approach for dense semantic 3D reconstruction which uses a data term that is defined as potentials over viewing rays, combined with continuous surface area penalization. Our formulation is a convex relaxation which we augment with a crucial non-convex constraint that ensures exact handling of visibility. To tackle the non-convex minimization problem, we propose a majorize-minimize type strategy which converges to a critical point. We demonstrate the benefits of using the non-convex constraint experimentally. For the geometry-only case, we set a new state of the art on two datasets of the commonly used Middlebury multi-view stereo benchmark. Moreover, our general-purpose formulation directly reconstructs thin objects, which are usually treated with specialized algorithms. A qualitative evaluation on the dense semantic 3D reconstruction task shows that we improve significantly over previous methods.
Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints
Venue: arXiv cs.AI 2019
Year: 2019

The fixed parameter tractable (FPT) approach is a powerful tool in tackling computationally hard problems. In this paper, we link FPT results to classic artificial intelligence (AI) techniques to show how they complement each other. Specifically, we consider the workflow satisfiability problem (WSP) which asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment. It was shown by Cohen et al. (JAIR 2014) that WSP restricted to the class of user-independent constraints (UI), covering many practical cases, admits FPT algorithms, i.e. can be solved in time exponential only in the number of steps $k$ and polynomial in the number of users $n$. Since usually $k << n$ in WSP, such FPT algorithms are of great practical interest. We present a new interpretation of the FPT nature of the WSP with UI constraints giving a decomposition of the problem into two levels. Exploiting this two-level split, we develop a new FPT algorithm that is by many orders of magnitude faster than the previous state-of-the-art WSP algorithm and also has only polynomial-space complexity. We also introduce new pseudo-Boolean (PB) and Constraint Satisfaction (CSP) formulations of the WSP with UI constraints which efficiently exploit this new decomposition of the problem and raise the novel issue of how to use general-purpose solvers to tackle FPT problems in a fashion that meets FPT efficiency expectations. In our computational study, we investigate, for the first time, the phase transition (PT) properties of the WSP, under a model for generation of random instances. We show how PT studies can be extended, in a novel fashion, to support empirical evaluation of scaling of FPT algorithms.
$(2/2/3)$-SAT problem and its applications in dominating set problems
Venue: arXiv cs.DM 2019
Year: 2019

The satisfiability problem is known to be $\mathbf{NP}$-complete in general and for many restricted cases. One way to restrict instances of $k$-SAT is to limit the number of times a variable can be occurred. It was shown that for an instance of 4-SAT with the property that every variable appears in exactly 4 clauses (2 times negated and 2 times not negated), determining whether there is an assignment for variables such that every clause contains exactly two true variables and two false variables is $\mathbf{NP}$-complete. In this work, we show that deciding the satisfiability of 3-SAT with the property that every variable appears in exactly four clauses (two times negated and two times not negated), and each clause contains at least two distinct variables is $ \mathbf{NP} $-complete. We call this problem $(2/2/3)$-SAT. For an $r$-regular graph $G = (V,E)$ with $r\geq 3$, it was asked in [Discrete Appl. Math., 160(15):2142--2146, 2012] to determine whether for a given independent set $T $ there is an independent dominating set $D$ that dominates $T$ such that $ T \cap D =\varnothing $? As an application of $(2/2/3)$-SAT problem we show that for every $r\geq 3$, this problem is $ \mathbf{NP} $-complete. Among other results, we study the relationship between 1-perfect codes and the incidence coloring of graphs and as another application of our complexity results, we prove that for a given cubic graph $G$ deciding whether $G$ is 4-incidence colorable is $ \mathbf{NP} $-complete.
Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic
Venue: arXiv cs.LO 2019
Year: 2019

We show that on graphs with n vertices, the 2-dimensional Weisfeiler-Leman algorithm requires at most O(n^2/log(n)) iterations to reach stabilization. This in particular shows that the previously best, trivial upper bound of O(n^2) is asymptotically not tight. In the logic setting, this translates to the statement that if two graphs of size n can be distinguished by a formula in first-order logic with counting with 3 variables (i.e., in C3), then they can also be distinguished by a C3-formula that has quantifier depth at most O(n^2/log(n)). To prove the result we define a game between two players that enables us to decouple the causal dependencies between the processes happening simultaneously over several iterations of the algorithm. This allows us to treat large color classes and small color classes separately. As part of our proof we show that for graphs with bounded color class size, the number of iterations until stabilization is at most linear in the number of vertices. This also yields a corresponding statement in first-order logic with counting. Similar results can be obtained for the respective logic without counting quantifiers, i.e., for the logic L3.
Rational Bézier Curves Approximated by Bernstein-Jacobi Hybrid Polynomial Curves
Venue: arXiv cs.CG 2019
Year: 2019

In this paper, we propose a linear method for $C^{(r,s)}$ approximation of rational Bézier curve with arbitrary degree polynomial curve. Based on weighted least-squares, the problem be converted to an approximation between two polynomial curves. Then applying Bernstein-Jacobi hybrid polynomials, we obtain the resulting curve. In order to reduce error, degree reduction method for Bézier curve is used. A error bound between rational Bézier curve and Bézier curve is presented. Finally, some examples and figures were offered to demonstrate the efficiency, simplicity, and stability of our methods.
Formal Verification of Multi-Paxos for Distributed Consensus
Venue: arXiv cs.DC 2019
Year: 2019

Paxos is an important algorithm for a set of distributed processes to agree on a single value or a sequence of values, for which it is called Basic Paxos or Multi-Paxos, respectively. Consensus is critical when distributed services are replicated for fault-tolerance, because non-faulty replicas must agree on the state of the system or the sequence of operations that have been performed. Unfortunately, consensus algorithms including Multi-Paxos in particular are well-known to be difficult to understand, and their accurate specifications and correctness proofs remain challenging, despite extensive studies ever since Lamport introduced Paxos. This article describes formal specification and verification of Lamport's Multi-Paxos algorithm for distributed consensus. The specification is written in TLA+, Lamport's Temporal Logic of Actions. The proof is written and automatically checked using TLAPS, the TLA+ Proof System. The proof is for the safety property of the algorithm. Building on Lamport, Merz, and Doligez's specification and proof for Basic Paxos, we aim to facilitate the understanding of Multi-Paxos and its proof by minimizing the difference from those for Basic Paxos, and to demonstrate a general way of proving other variants of Paxos and other sophisticated distributed algorithms. We also discuss our general strategies and results for proving complex invariants using invariance lemmas and increments, for proving properties about sets and tuples to help the proof check succeed in significantly reduced time, and for overall proof improvement leading to considerably reduced proof size.
The Opacity of Backbones
Venue: arXiv cs.AI 2019
Year: 2019

This paper approaches, using structural complexity theory, the question of whether there is a chasm between knowing an object exists and getting one's hands on the object or its properties. In particular, we study the nontransparency of so-called backbones. A backbone of a boolean formula $F$ is a collection $S$ of its variables for which there is a unique partial assignment $a_S$ such that $F[a_S]$ is satisfiable [MZK+99,WGS03]. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values, $a_S$, of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone $S$ is intractable. Furthermore, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency. These results hold more generally, namely, in the settings where, respectively, one's assumption is that P $\neq$ NP $\cap$ coNP or that some problem in NP $\cap$ coNP is frequently hard.