A network embedding consists of a vector representation for each node in the network. Its usefulness has been shown in many real-world application domains, such as social networks and web networks. Directed networks with text associated with each node, such as software package dependency networks, are commonplace. However, to the best of our knowledge, their embeddings have hitherto not been specifically studied. In this paper, we propose PCTADW-1 and PCTADW-2, two algorithms based on neural networks that learn embeddings of directed networks with text associated with each node. We create two new node-labeled such networks: The package dependency networks in two popular GNU/Linux distributions, Debian and Fedora. We experimentally demonstrate that the embeddings produced by our algorithms resulted in node classification with better quality than those of various baselines on these two networks. We observe that there exist systematic presence of analogies (similar to those in word embeddings) in the network embeddings of software package dependency networks. To the best of our knowledge, this is the first time that such systematic presence of analogies is observed in network and document embeddings. We further demonstrate that these network embeddings can be novelly used for better understanding software attributes, such as the development process and user interface of software, etc.

The CoNLL-2003 corpus for Englishlanguage named entity recognition (NER) is one of the most influential corpora for NER model research.A large number of publications, including many landmark works, have used this corpus as a source of ground truth for NER tasks.In this paper, we examine this corpus and identify over 1300 incorrect labels (out of 35089 in the corpus).In particular, the number of incorrect labels in the test fold is comparable to the number of errors that state-of-the-art models make when running inference over this corpus.We describe the process by which we identified these incorrect labels, using novel variants of techniques from semi-supervised learning.We also summarize the types of errors that we found, and we revisit several recent results in NER in light of the corrected data.Finally, we show experimentally that our corrections to the corpus have a positive impact on three state-ofthe-art models.

The weighted constraint satisfaction problem (WCSP) is a powerful mathematical framework for combinatorial optimization. The branch and bound search paradigm is very successful in solving the WCSP but critically depends on the ordering in which variables are instantiated. In this paper, we introduce a new framework for dynamic variable ordering for solving the WCSP. This framework is inspired by regression decision tree learning. Variables are ordered dynamically based on samples of random assignments of values to variables as well as their corresponding total weights. Within this framework, we propose four variable ordering heuristics (sdr, inv-sdr, rr and inv-rr). We compare them with many other state-of-the-art dynamic variable ordering heuristics, and show that sdr and rr outperform them on many real-world and random benchmark instances.

A recent trend observed in traditionally challenging fields such as computer vision and natural language processing has been the significant performance gains shown by deep learning (DL). In many different research fields, DL models have been evolving rapidly and become ubiquitous. Despite researchers' excitement, unfortunately, most software developers are not DL experts and oftentimes have a difficult time following the booming DL research outputs. As a result, it usually takes a significant amount of time for the latest superior DL models to prevail in industry. This issue is further exacerbated by the common use of sundry incompatible DL programming frameworks, such as Tensorflow, PyTorch, Theano, etc. To address this issue, we propose a system, called Model Asset Exchange (MAX), that avails developers of easy access to state-of-the-art DL models. Regardless of the underlying DL programming frameworks, it provides an open source Python library (called the MAX framework) that wraps DL models and unifies programming interfaces with our standardized RESTful APIs. These RESTful APIs enable developers to exploit the wrapped DL models for inference tasks without the need to fully understand different DL programming frameworks. Using MAX, we have wrapped and open-sourced more than 30 state-of-the-art DL models from various research fields, including computer vision, natural language processing and signal processing, etc. In the end, we selectively demonstrate two web applications that are built on top of MAX, as well as the process of adding a DL model to MAX.

Physical keyboards have been peripheral input devices to electronic computers since early 1970s and become ubiquitous during the past few decades, especially in professional areas such as software programming, professional game playing, and document processing. In these real-world applications, key bindings, a fundamental vehicle for human to interact with software systems using physical keyboards, play a critical role in users' productivity. However, as essential applications of artificial intelligence research, research on intelligent user interfaces and recommender systems barely relates to key bindings on physical keyboards. In this paper, we develop a recommender system (referred to as EKBRS) for intelligently recommending key bindings with demonstration in Emacs, which we use as a base user interface. This is a brand new direction of intelligent user interface research and also a novel application of recommender systems. To the best of our knowledge, this is the world's first intelligent user interface that heavily exploits key bindings of physical keyboards and the world's first recommender system for recommending key bindings. We empirically show the effectiveness of our recommender system and briefly discuss the applicability of this recommender system to other software systems.

Local consistency algorithms, like arc consistency (AC) algorithms, are polynomial-time algorithms that prune the search space of constraint satisfaction problems (CSPs). In this paper, we present connections between message passing algorithms and AC for semiring-based CSPs (SCSPs) and valued CSPs (VCSPs), two well-established frameworks that generalize CSPs. Message passing algorithms are well known distributed search algorithms for solving many combinatorial problems in artificial intelligence, probabilistic reasoning, and information theory. However, the relationship between message passing algorithms and SCSPs or VCSPs still remains understudied. Towards this end, we propose the best-O message passing (BOMP) algorithm for SCSPs and VCSPs. We prove that, unlike other standard message passing algorithms which are in general not guaranteed to converge, the BOMP algorithm guarantees convergence for SCSPs and specific subclasses of VCSPs. We also theoretically study the relationship between the BOMP algorithm and AC on SCSPs, and empirically study the quality of the solutions produced by the BOMP algorithm for VCSPs.

Filtering denotes any method whereby an agent updates its belief state—its knowledge of the state of the world—from a sequence of actions and observations. Popular filtering techniques like Kalman and particle filters maintain compact representations of the belief state at all times. However, these techniques cannot be applied to situations where the world is described using constraints instead of stochastic models. In such cases, the belief state is a logical formula describing all possible world states. In this paper, we first review a logical filtering algorithm for connected row convex (CRC) constraints. CRC constraints are representationally very powerful; and the filtering algorithm for CRC constraints is a logical equivalent of the Kalman filter. We later study the CRC filtering algorithm in distributed settings where nodes of a network are interested in different subsets of variables from a larger system. We deduce its reducibility to the problem of distributed path consistency (PC) and prove the compactness of the belief state representations maintained at each node at all times.

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

In this paper, we develop the message passing based linear-time and linear-space MVC algorithm (MVC-MPL) for solving the minimum vertex cover (MVC) problem. MVC-MPL is based on heuristics derived from a theoretical analysis of message passing algorithms in the context of belief propagation. We show that MVC-MPL produces smaller vertex covers than other linear-time and linear-space algorithms.

In this paper, we study the Complex Routing Problem (CRP), where several homogeneous robots need to visit given task locations to accomplish complex tasks in a cooperative setting. Each task location hosts a task. The complexity level of a task is defined as the number of robots that need to be simultaneously present at its location to accomplish it. The robots need to be routed so that all tasks get accomplished with minimal makespan. We present a new centralized algorithm, called SAGL, for solving the CRP heuristically. SAGL is inspired by the application of linear programming duality to the Steiner Forest Problem. It makes less restrictive assumptions than the state-of-the-art distributed Approach with Reaction Functions and scales better in both the complexity levels of tasks and the number of complex tasks (whose complexity levels are greater than one), although it results in somewhat larger makespans.