bluuebunny/crossref_metadata_2025 huggingface dataset:
Locality Preserving Matching
Authors: Ma Jiayi , Zhao Ji , Guo Hanqi , Jiang Junjun , Zhou Huabing , Gao Yuan
Published: July 2017

Seeking reliable correspondences between two feature sets is a fundamental and important task in computer vision. This paper attempts to remove mismatches from given putative image feature correspondences. To achieve the goal, an efficient approach, termed as locality preserving matching (LPM), is designed, the principle of which is to maintain the local neighborhood structures of those potential true matches. We formulate the problem into a mathematical model, and derive a closed-form solution with linearithmic time and linear space complexities. More specifically, our method can accomplish the mismatch removal from thousands of putative correspondences in only a few milliseconds. Experiments on various real image pairs for general feature matching, as well as for visual homing and image retrieval demonstrate the generality of our method for handling different types of image deformations, and it is more than two orders of magnitude faster than state-of-the-art methods in the same range of or better accuracy.
Combining Models from Multiple Sources for RGB-D Scene Recognition
Authors: Song Xinhang , Jiang Shuqiang , Herranz Luis
Published: July 2017

Depth can complement RGB with useful cues about object volumes and scene layout. However, RGB-D image datasets are still too small for directly training deep convolutional neural networks (CNNs), in contrast to the massive monomodal RGB datasets. Previous works in RGB-D recognition typically combine two separate networks for RGB and depth data, pretrained with a large RGB dataset and then fine tuned to the respective target RGB and depth datasets. These approaches have several limitations: 1) only use low-level filters learned from RGB data, thus not being able to exploit properly depth-specific patterns, and 2) RGB and depth features are only combined at high-levels but rarely at lower-levels. In this paper, we propose a framework that leverages both knowledge acquired from large RGB datasets together with depth-specific cues learned from the limited depth data, obtaining more effective multi-source and multi-modal representations. We propose a multi-modal combination method that selects discriminative combinations of layers from the different source models and target modalities, capturing both high-level properties of the task and intrinsic low-level properties of both modalities.
Adaptive Elicitation of Preferences under Uncertainty in Sequential Decision Making Problems
Authors: Benabbou Nawal , Perny Patrice
Published: July 2017

This paper aims to introduce an adaptive preference elicitation method for interactive decision support in sequential decision problems. The Decision Maker's preferences are assumed to be representable by an additive utility, initially unknown or imperfectly known. We first study the determination of possibly optimal policies when admissible utilities are imprecisely defined by some linear constraints derived from observed preferences. Then, we introduce a new approach interleaving elicitation of utilities and backward induction to incrementally determine an optimal or near-optimal policy. We propose an interactive algorithm with performance guarantees and describe numerical experiments demonstrating the practical efficiency of our approach.
COG-DICE: An Algorithm for Solving Continuous-Observation Dec-POMDPs
Authors: Clark-Turner Madison , Amato Christopher
Published: July 2017

The decentralized partially observable Markov decision process (Dec-POMDP) is a powerful model for representing multi-agent problems with decentralized behavior. Unfortunately, current Dec-POMDP solution methods cannot solve problems with continuous observations, which are common in many real-world domains. To that end, we present a framework for representing and generating Dec-POMDP policies that explicitly include continuous observations. We apply our algorithm to a novel tagging problem and an extended version of a common benchmark, where it generates policies that meet or exceed the values of equivalent discretized domains without the need for finding an adequate discretization.
Coarse-to-Fine Lifted MAP Inference in Computer Vision
Authors: Habeeb Haroun , Anand Ankit , Mausam  , Singla Parag
Published: July 2017

There is a vast body of theoretical research on lifted inference in probabilistic graphical models (PGMs). However, few demonstrations exist where lifting is applied in conjunction with top of the line applied algorithms. We pursue the applicability of lifted inference for computer vision (CV), with the insight that a globally optimal (MAP) labeling will likely have the same label for two symmetric pixels. The success of our approach lies in efficiently handling a distinct unary potential on every node (pixel), typical of CV applications. This allows us to lift the large class of algorithms that model a CV problem via PGM inference. We propose a generic template for coarse-to-fine (C2F) inference in CV, which progressively refines an initial coarsely lifted PGM for varying quality-time trade-offs. We demonstrate the performance of C2F inference by developing lifted versions of two near state-of-the-art CV algorithms for stereo vision and interactive image segmentation. We find that, against flat algorithms, the lifted versions have a much superior anytime performance, without any loss in final solution quality.
Variational Mixtures of Gaussian Processes for Classification
Authors: Luo Chen , Sun Shiliang
Published: July 2017

Gaussian Processes (GPs) are powerful tools for machine learning which have been applied to both classification and regression. The mixture models of GPs were later proposed to further improve GPs for data modeling. However, these models are formulated for regression problems. In this work, we propose a new Mixture of Gaussian Processes for Classification (MGPC). Instead of the Gaussian likelihood for regression, MGPC employs the logistic function as likelihood to obtain the class probabilities, which is suitable for classification problems. The posterior distribution of latent variables is approximated through variational inference. The hyperparameters are optimized through the variational EM method and a greedy algorithm. Experiments are performed on multiple real-world datasets which show improvements over five widely used methods on predictive performance. The results also indicate that for classification MGPC is significantly better than the regression model with mixtures of GPs, different from the existing consensus that their single model counterparts are comparable.
Weighted Model Integration with Orthogonal Transformations
Authors: Merrell David , Albarghouthi Aws , D'Antoni Loris
Published: July 2017

Weighted model counting and integration (WMC/WMI) are natural problems to which we can reduce many probabilistic inference tasks, e.g., in Bayesian networks, Markov networks, and probabilistic programs. Typically, we are given a first-order formula, where each satisfying assignment is associated with a weight---e.g., a probability of occurrence---and our goal is to compute the total weight of the formula. In this paper, we target exact inference techniques for WMI that leverage the power of satisfiability modulo theories (SMT) solvers to decompose a first-order formula in linear real arithmetic into a set of hyperrectangular regions whose weight is easy to compute. We demonstrate the challenges of hyperrectangular decomposition and present a novel technique that utilizes orthogonal transformations to transform formulas in order to enable efficient inference. Our evaluation demonstrates our technique's ability to improve the time required to achieve exact probability bounds.
Agent Design Consistency Checking via Planning
Authors: Yadav Nitin , Thangarajah John , Sardina Sebastian
Published: July 2017

In this work we present a novel approach to check the consistency of agent designs (prior to any implementation) with respect to the requirements specifications via automated planning. This checking is essentially a search problem which makes planning technology an appropriate solution. We focus our work on BDI agent systems and the Prometheus design methodology in order to directly compare our approach to previous work. Our experiments in more than 16K random instances prove that the approach is more effective than previous ones proposed: it achieves higher coverage, lower run-time, and importantly, can handle loops in the agent detailed design and unbounded subgoal reasoning.
When Will Negotiation Agents Be Able to Represent Us? The Challenges and Opportunities for Autonomous Negotiators
Authors: Baarslag Tim , Kaisers Michael , Gerding Enrico H. , Jonker Catholijn M. , Gratch Jonathan
Published: July 2017

Computers that negotiate on our behalf hold great promise for the future and will even become indispensable in emerging application domains such as the smart grid and the Internet of Things. Much research has thus been expended to create agents that are able to negotiate in an abundance of circumstances. However, up until now, truly autonomous negotiators have rarely been deployed in real-world applications. This paper sizes up current negotiating agents and explores a number of technological, societal and ethical challenges that autonomous negotiation systems have brought about. The questions we address are: in what sense are these systems autonomous, what has been holding back their further proliferation, and is their spread something we should encourage? We relate the automated negotiation research agenda to dimensions of autonomy and distill three major themes that we believe will propel autonomous negotiation forward: accurate representation, long-term perspective, and user trust. We argue these orthogonal research directions need to be aligned and advanced in unison to sustain tangible progress in the field.
Reinforcement Learning with a Corrupted Reward Channel
Authors: Everitt Tom , Krakovna Victoria , Orseau Laurent , Legg Shane
Published: July 2017

No real-world reward function is perfect. Sensory errors and software bugs may result in agents getting higher (or lower) rewards than they should. For example, a reinforcement learning agent may prefer states where a sensory error gives it the maximum reward, but where the true reward is actually small. We formalise this problem as a generalised Markov Decision Problem called Corrupt Reward MDP. Traditional RL methods fare poorly in CRMDPs, even under strong simplifying assumptions and when trying to compensate for the possibly corrupt rewards. Two ways around the problem are investigated. First, by giving the agent richer data, such as in inverse reinforcement learning and semi-supervised reinforcement learning, reward corruption stemming from systematic sensory errors may sometimes be completely managed. Second, by using randomisation to blunt the agent's optimisation, reward corruption can be partially managed under some assumptions.
A Goal Reasoning Agent for Controlling UAVs in Beyond-Visual-Range Air Combat
Authors: Floyd Michael W. , Karneeb Justin , Moore Philip , Aha David W.
Published: July 2017

We describe the Tactical Battle Manager (TBM), an intelligent agent that uses several integrated artificial intelligence techniques to control an autonomous unmanned aerial vehicle in simulated beyond-visual-range (BVR) air combat scenarios. The TBM incorporates goal reasoning, automated planning, opponent behavior recognition, state prediction, and discrepancy detection to operate in a real-time, dynamic, uncertain, and adversarial environment. We describe evidence from our empirical study that the TBM significantly outperforms an expert-scripted agent in BVR scenarios. We also report the results of an ablation study which indicates that all components of our agent architecture are needed to maximize mission performance.
Online Decision-Making for Scalable Autonomous Systems
Authors: Wray Kyle Hollins , Witwicki Stefan J. , Zilberstein Shlomo
Published: July 2017

We present a general formal model called MODIA that can tackle a central challenge for autonomous vehicles (AVs), namely the ability to interact with an unspecified, large number of world entities. In MODIA, a collection of possible decision-problems (DPs), known a priori, are instantiated online and executed as decision-components (DCs), unknown a priori. To combine their individual action recommendations of the DCs into a single action, we propose the lexicographic executor action function (LEAF) mechanism. We analyze the complexity of MODIA and establish LEAF’s relation to regret minimization. Finally, we implement MODIA and LEAF using collections of partially observable Markov decision process (POMDP) DPs, and use them for complex AV intersection decision-making. We evaluate the approach in six scenarios within an industry-standard vehicle simulator, and present its use on an AV prototype.
Rationalisation of Profiles of Abstract Argumentation Frameworks: Extended Abstract
Authors: Airiau Stephane , Bonzon Elise , Endriss Ulle , Maudet Nicolas , Rossit Julien
Published: July 2017

We review a recently introduced model in which each of a number of agents is endowed with an abstract argumentation framework reflecting her individual views regarding a given set of arguments. A question arising in this context is whether the diversity of views observed in such a situation is consistent with the assumption that every individual argumentation framework is induced by a combination of, first, some basic factual information and, second, the personal preferences of the agent concerned. We treat this question of rationalisability of a profile as an algorithmic problem and identify tractable and intractable cases. This is useful for understanding what types of profiles can reasonably be expected to occur in a multiagent system.
Predicting Human Similarity Judgments with Distributional Models: The Value of Word Associations
Authors: De Deyne Simon , Perfors Amy , Navarro Daniel J.
Published: July 2017

To represent the meaning of a word, most models use external language resources, such as text corpora, to derive the distributional properties of word usage. In this study, we propose that internal language models, that are more closely aligned to the mental representations of words, can be used to derive new theoretical questions regarding the structure of the mental lexicon. A comparison with internal models also puts into perspective a number of assumptions underlying recently proposed distributional text-based models could provide important insights into cognitive science, including linguistics and artificial intelligence. We focus on word-embedding models which have been proposed to learn aspects of word meaning in a manner similar to humans and contrast them with internal language models derived from a new extensive data set of word associations. An evaluation using relatedness judgments shows that internal language models consistently outperform current state-of-the art text-based external language models. This suggests alternative approaches to represent word meaning using properties that aren't encoded in text.
Enhancing Crowdworkers' Vigilance
Authors: Elmalech Avshalom , Sarne David , David Esther , Hajaj Chen
Published: July 2017

This paper presents methods for improving the attention span of workers in tasks that heavily rely on their attention to the occurrence of rare events. The underlying idea in our approach is to dynamically augment the task with some dummy (artificial) events at different times throughout the task, rewarding the worker upon identifying and reporting them. The proposed approach is an alternative to the traditional approach of exclusively relying on rewarding the worker for successfully identifying the event of interest itself. We propose three methods for timing the dummy events throughout the task. Two of these methods are static and determine the timing of the dummy events at random or uniformly throughout the task. The third method is dynamic and uses the identification (or misidentification) of dummy events as a signal for the worker's attention to the task, adjusting the rate of dummy events generation accordingly.
Lexicons on Demand: Neural Word Embeddings for Large-Scale Text Analysis
Authors: Fast Ethan , Chen Binbin , Bernstein Michael S.
Published: July 2017

Human language is colored by a broad range of topics, but existing text analysis tools only focus on a small number of them. We present Empath, a tool that can generate and validate new lexical categories on demand from a small set of seed terms (like "bleed" and "punch" to generate the category violence). Empath draws connotations between words and phrases by learning a neural embedding across billions of words on the web. Given a small set of seed words that characterize a category, Empath uses its neural embedding to discover new related terms, then validates the category with a crowd-powered filter. Empath also analyzes text across 200 built-in, pre-validated categories we have generated such as neglect, government, and social media. We show that Empath's data-driven, human validated categories are highly correlated (r=0.906) with similar categories in LIWC.
Which is the Fairest (Rent Division) of Them All? [Extended Abstract]
Authors: Gal Ya'akov (Kobi) , Mash Moshe , Procaccia Ariel D. , Zick Yair
Published: July 2017

What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.
Multi-Type Activity Recognition from a Robot's Viewpoint
Authors: Gori Ilaria , Aggarwal J. K. , Matthies Larry , Ryoo Michael. S.
Published: July 2017

The literature in computer vision is rich of works where different types of activities -- single actions, two persons interactions or ego-centric activities, to name a few -- have been analyzed. However, traditional methods treat such types of activities separately, while in real settings detecting and recognizing different types of activities simultaneously is necessary. We first design a new unified descriptor, called Relation History Image (RHI), which can be extracted from all the activity types we are interested in. We then formulate an optimization procedure to detect and recognize activities of different types. We assess our approach on a new dataset recorded from a robot-centric perspective as well as on publicly available datasets, and evaluate its quality compared to multiple baselines.
An End-to-End System for Accomplishing Tasks with Modular Robots: Perspectives for the AI community
Authors: Jing Gangyuan , Tosun Tarik , Yim Mark , Kress-Gazit Hadas
Published: July 2017

The advantage of modular robot systems lies in their flexibility, but this advantage can only be realized if there exists some reliable, effective way of generating configurations (shapes) and behaviors (controlling programs) appropriate for a given task. In this paper, we present an end-to-end system for addressing tasks with modular robots, and demonstrate that it is capable of accomplishing challenging multi-part tasks in hardware experiments. The system consists of four tightly integrated components: (1) A high-level mission planner, (2) A design library spanning a wide set of functionality, (3) A design and simulation tool for populating the library with new configurations and behaviors, and (4) Modular robot hardware. This paper condenses the material originally presented in Jing et al. 2016 into a shorter format suitable for a broad audience.
On Thompson Sampling and Asymptotic Optimality
Authors: Leike Jan , Lattimore Tor , Orseau Laurent , Hutter Marcus
Published: July 2017

We discuss some recent results on Thompson sampling for nonparametric reinforcement learning in countable classes of general stochastic environments. These environments can be non-Markovian, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that

(1) asymptotically its value converges in mean to the optimal value and

(2) given a recoverability assumption regret is sublinear.

We conclude with a discussion about optimality in reinforcement learning.
A SAT Approach to Branchwidth
Authors: Lodha Neha , Ordyniak Sebastian , Szeider Stefan
Published: July 2017

Branch decomposition is a prominent method for structurally decomposing a graph, hypergraph or CNF formula. The width of a branch decomposition provides a measure of how well the object is decomposed. For many applications it is crucial to compute a branch decomposition whose width is as small as possible. We propose a SAT approach to finding branch decompositions of small width. The core of our approach is an efficient SAT encoding which determines with a single SAT-call whether a given hypergraph admits a branch decomposition of certain width. For our encoding we develop a novel partition-based characterization of branch decompositions. The encoding size imposes a limit on the size of the given hypergraph. In order to break through this barrier and to scale the SAT approach to larger instances, we develop a new heuristic approach where the SAT encoding is used to locally improve a given candidate decomposition until a fixed-point is reached. This new method scales now to instances with several thousands of vertices and edges.
Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
Authors: Chen Jingwei , Holte Robert C. , Zilles Sandra , Sturtevant Nathan R.
Published: July 2017

It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called “surely expanded” (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.
Self-Adjusting Memory: How to Deal with Diverse Drift Types
Authors: Losing Viktor , Hammer Barbara , Wersing Heiko
Published: July 2017

Data Mining in non-stationary data streams is particularly relevant in the context of the Internet of Things and Big Data. Its challenges arise from fundamentally different drift types violating assumptions of data independence or stationarity. Available methods often struggle with certain forms of drift or require unavailable a priori task knowledge. We propose the Self-Adjusting Memory (SAM) model for the k Nearest Neighbor (kNN) algorithm. SAM-kNN can deal with heterogeneous concept drift, i.e. different drift types and rates. Its basic idea are dedicated models for current and former concepts used according to the demands of the given situation. It can be robustly applied in practice without meta parameter optimization.

We conduct an extensive evaluation on various benchmarks, consisting of artificial streams with known drift characteristics and real-world datasets. Highly competitive results throughout all experiments underline the robustness of SAM-kNN as well as its capability to handle heterogeneous concept drift.
The Many Benefits of Annotator Rationales for Relevance Judgments
Authors: McDonnell Tyler , Kutlu Mucahid , Elsayed Tamer , Lease Matthew
Published: July 2017

When collecting subjective human ratings of items, it can be difficult to measure and enforce data quality due to task subjectivity and lack of insight into how judges arrive at each rating decision. To address this, we propose requiring judges to provide a specific type of rationale underlying each rating decision. We evaluate this approach in the domain of Information Retrieval, where human judges rate the relevance of Webpages. Cost-benefit analysis over 10,000 judgments collected on Mechanical Turk suggests a win-win: experienced crowd workers provide rationales with no increase in task completion time while providing further benefits, including more reliable judgments and greater transparency.
KSP: A Resolution-based Prover for Multimodal K, Abridged Report
Authors: Nalon Cláudia , Hustadt Ullrich , Dixon Clare
Published: July 2017

In this paper, we briefly describe an implementation of a hyper-resolution-based calculus for the propositional basic multimodal logic, Kn. The prover, KSP, is designed to support experimentation with different combinations of refinements for its basic calculus. The prover allows for both local and global reasoning. We present an experimental evaluation that compares KSP with a range of existing reasoners for Kn.
nanoCoP: Natural Non-clausal Theorem Proving
Authors: Otten Jens
Published: July 2017

Most efficient fully automated theorem provers implement proof search calculi that require the input formula to be in a clausal form, i.e. disjunctive or conjunctive normal form. The translation into clausal form introduces a significant overhead to the proof search and modifies the structure of the original formula. Translating a proof in clausal form back into a more readable non-clausal proof of the original formula is not straightforward. This paper presents a non-clausal automated theorem prover for classical first-order logic. It is based on a non-clausal connection calculus and implemented with a few lines of Prolog code. Working entirely on the original structure of the input formula yields not only a speed up of the proof search, but the resulting non-clausal proofs are also shorter.
Local Topic Discovery via Boosted Ensemble of Nonnegative Matrix Factorization
Authors: Suh Sangho , Choo Jaegul , Lee Joonseok , Reddy Chandan K.
Published: July 2017

Nonnegative matrix factorization (NMF) has been increasingly popular for topic modeling of large-scale documents. However, the resulting topics often represent only general, thus redundant information about the data rather than minor, but potentially meaningful information to users. To tackle this problem, we propose a novel ensemble model of nonnegative matrix factorization for discovering high-quality local topics. Our method leverages the idea of an ensemble model to successively perform NMF given a residual matrix obtained from previous stages and generates a sequence of topic sets. The novelty of our method lies in the fact that it utilizes the residual matrix inspired by a state-of-the-art gradient boosting model and applies a sophisticated local weighting scheme on the given matrix to enhance the locality of topics, which in turn delivers high-quality, focused topics of interest to users.
Value Iteration Networks
Authors: Tamar Aviv , Wu Yi , Thomas Garrett , Levine Sergey , Abbeel Pieter
Published: July 2017

We introduce the value iteration network (VIN): a fully differentiable neural network with a `planning module' embedded within. VINs can learn to plan, and are suitable for predicting outcomes that involve planning-based reasoning, such as policies for reinforcement learning. Key to our approach is a novel differentiable approximation of the value-iteration algorithm, which can be represented as a convolutional neural network, and trained end-to-end using standard backpropagation.We evaluate VIN based policies on discrete and continuous path-planning domains, and on a natural-language based search task. We show that by learning an explicit planning computation, VIN policies generalize better to new, unseen domains.This paper is a significantly abridged and IJCAI audience targeted version of the original NIPS 2016 paper with the same title, available here: https://arxiv.org/abs/1602.02867
Automatic Description Generation from Images: A Survey of Models, Datasets, and Evaluation Measures (Extended Abstract)
Authors: Bernardi Raffaella , Cakici Ruket , Elliott Desmond , Erdem Aykut , Erdem Erkut , Ikizler-Cinbis Nazli , Keller Frank , Muscat Adrian , Plank Barbara
Published: July 2017

Automatic image description generation is a challenging problem that has recently received a large amount of interest from the computer vision and natural language processing communities. In this survey, we classify the known approaches based on how they conceptualise this problem and provide a review of existing models, highlighting their advantages and disadvantages. Moreover, we give an overview of the benchmark image-text datasets and the evaluation measures that have been developed to assess the quality of machine-generated descriptions. Finally we explore future directions in the area of automatic image description.
The Ceteris Paribus Structure of Logics of Game Forms (Extended Abstract)
Authors: Grossi Davide , Lorini Emiliano , Schwarzentruber François
Published: July 2017

We present a simple Ceteris Paribus Logic (CP) and study its relationship with existing logics that deal with the representation of choice and power in games in normal form including atemporal STIT, Coalition Logic of Propositional Control (CL-PC) and Dynamic Logic of Propositional Assignments (DL-PA). Thanks to the polynomial reduction of the satisfiability problem for atemporal STIT in the satisfiability problem for CP, we obtain a complexity result for the latter problem.
Computer Models Solving Intelligence Test Problems: Progress and Implications (Extended Abstract)
Authors: Hernández-Orallo José , Martínez-Plumed Fernando , Schmid Ute , Siebers Michael , Dowe David
Published: July 2017

While some computational models of intelligence test problems were proposed throughout the second half of the XXth century, in the first years of the XXIst century we have seen an increasing number of computer systems being able to score well on particular intelligence test tasks. However, despitethis increasing trend there has been no general account of all these works in terms of how theyrelate to each other and what their real achievements are. In this paper, we provide some insighton these issues by giving a comprehensive account of about thirty computer models, from the 1960sto nowadays, and their relationships, focussing on the range of intelligence test tasks they address, thepurpose of the models, how general or specialised these models are, the AI techniques they use in eachcase, their comparison with human performance, and their evaluation of item difficulty.
New Canonical Representations by Augmenting OBDDs with Conjunctive Decomposition (Extended Abstract)
Authors: Lai Yong , Liu Dayou , Yin Minghao
Published: July 2017

We identify two families of canonical representations called ROBDD[/\i^]_C and ROBDD[/\T^,i]_T by augmenting ROBDD with two types of conjunctive decompositions. These representations cover the three existing languages ROBDD, ROBDD with as many implied literals as possible (ROBDD-L_&infin), and AND/OR BDD. We introduce a new time efficiency criterion called rapidity which reflects the idea that exponential operations may be preferable if the language can be exponentially more succinct. Then we demonstrate that the expressivity, succinctness and operation rapidity do not decrease from ROBDD[/\T^,i]_T to ROBDD[/\i^]_C, and then to ROBDD[/\i+1^]_C. We also demonstrate that ROBDD[/\i^]_C (i > 1) and ROBDD[/\T^,i]_T are not less tractable than ROBDD-L_&infin and ROBDD, respectively. Finally, we develop a compiler for ROBDD[/\&infin^]_C which significantly advances the compiling efficiency of canonical representations.
Automated Conjecturing I: Fajtlowicz's Dalmatian Heuristic Revisited (Extended Abstract)
Authors: Larson Craig E. , Van Cleemput Nico
Published: July 2017

This condensed summary highlights the results of a 2016 AIJ paper reporting on a successful general-purpose conjecturing program.
Approximate Value Iteration with Temporally Extended Actions (Extended Abstract)
Authors: Mann Timothy A. , Mannor Shie , Precup Doina
Published: July 2017

The options framework provides a concrete way to implement and reason about temporally extended actions. Existing literature has demonstrated the value of planning with options empirically, but there is a lack of theoretical analysis formalizing when planning with options is more efficient than planning with primitive actions. We provide a general analysis of the convergence rate of a popular Approximate Value Iteration (AVI) algorithm called Fitted Value Iteration (FVI) with options. Our analysis reveals that longer duration options and a pessimistic estimate of the value function both lead to faster convergence. Furthermore, options can improve convergence even when they are suboptimal and sparsely distributed throughout the state space. Next we consider generating useful options for planning based on a subset of landmark states. This suggests a new algorithm, Landmark-based AVI (LAVI), that represents the value function only at landmark states. We analyze OFVI and LAVI using the proposed landmark-based options and compare the two algorithms. Our theoretical and experimental results demonstrate that options can play an important role in AVI by decreasing approximation error and inducing fast convergence.
Generating Models of a Matched Formula With a Polynomial Delay (Extended Abstract)
Authors: Savický Petr , Kučera Petr
Published: July 2017

A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. Such a formula is always satisfiable. Matched formulas are used, for example, in the area of parameterized complexity. We prove that the problem of counting the number of the models (satisfying assignments) of a matched formula is #P-complete. On the other hand, we define a class of formulas generalizing the matched formulas and prove that for a formula in this class one can choose in polynomial time a variable suitable for splitting the tree for the search of the models of the formula. As a consequence, the models of a formula from this class, in particular of any matched formula, can be generated sequentially with a delay polynomial in the size of the input. On the other hand, we prove that this task cannot be performed efficiently for linearly satisfiable formulas, which is a generalization of matched formulas containing the class considered above.
On the Expressivity of Inconsistency Measures (Extended Abstract)
Authors: Thimm Matthias
Published: July 2017

We survey recent approaches to inconsistency measurement in propositional logic and provide a comparative analysis in terms of their expressivity. For that, we introduce four different expressivity characteristics that quantitatively assess the number of different knowledge bases that a measure can distinguish. Our approach aims at complementing ongoing discussions on rationality postulates for inconsistency measures by considering expressivity as a desirable property. We evaluate a large selection of measures on the proposed characteristics and conclude that a distance-based measure from [Grant and Hunter, 2013] has maximal expressivity along all considered characteristics.
A generic approach to planning in the presence of incomplete information: Theory and implementation (Extended Abstract)
Authors: To Son Thanh , Son Tran Cao , Pontelli Enrico
Published: July 2017

This paper proposes a generic approach to planning in the presence of incomplete information. The approach builds on an abstract notion of a belief state representation, along with an associated set of basic operations. These operations facilitate the development of a sound and complete transition function, for reasoning about effects of actions in the presence of incomplete information, and a set of abstract algorithms for planning. The paper demonstrates how the abstract definitions and algorithms can be instantiated in three concrete representations—minimal-DNF, minimal-CNF, and prime implicates—resulting in three highly competitive conformant planners: DNF, CNF, and PIP. The paper relates the notion of a representation to that of ordered binary decision diagrams, a well-known belief state representation employed by many conformant planners, and several target compilation languages that have been presented in the literature.The paper also includes an experimental evaluation of the planners DNF, CNF, and PIP and proposes a new set of conformant planning benchmarks that are challenging for state-of-the-art conformant planners.
Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function (Extended Abstract)
Authors: Wang Yiyuan , Cai Shaowei , Yin Minghao
Published: July 2017

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.
Game Theoretic Analysis of Security and Sustainability
Authors: An Bo
Published: July 2017

Computational game theory has become a powerful tool to address critical issues in security and sustainability. Casting the security resource allocation problem as a Stackelberg game, novel algorithms have been developed to provide randomized security resource allocations. These algorithms have led to deployed security-game based decision aids for many real-world security domains including infrastructure security and wildlife protection. We contribute to this community by addressing several major research challenges in complex security resource allocation, including dynamic payoffs, uncertainty, protection externality, games on networks, and strategic secrecy. We also analyze optimal security resource allocation in many potential application domains including cyber security. Furthermore, we apply game theory to reasoning optimal policy in deciding taxi pricing scheme and EV charging placement and pricing.
Committee Scoring Rules: A Call to Arms
Authors: Faliszewski Piotr
Published: July 2017

Committee scoring rules are a class of voting rules used to select sets of candidates based on the preferences of the voters. The goal of this paper is to present this class and to invite researchers to study its properties (computational and axiomatic alike).
Learning from Data Heterogeneity: Algorithms and Applications
Authors: He Jingrui
Published: July 2017

Nowadays, as an intrinsic property of big data, data heterogeneity can be seen in a variety of real-world applications, ranging from security to manufacturing, from healthcare to crowdsourcing. It refers to any inhomogeneity in the data, and can be present in a variety of forms, corresponding to different types of data heterogeneity, such as task/view/instance/oracle heterogeneity. As shown in previous work as well as our own work, learning from data heterogeneity not only helps people gain a better understanding of the large volume of data, but also provides a means to leverage such data for effective predictive modeling. In this paper, along with multiple real applications, we will briefly review state-of-the-art techniques for learning from data heterogeneity, and demonstrate their performance at addressing these real world problems.
A Framework for Long-Term Learning Systems
Authors: Benavides-Prado Diana
Published: July 2017

Increasing amounts of data have made the use of machine learning techniques much more widespread. A lot of research in machine learning has been dedicated to the design and application of effective and efficient algorithms to explain or predict facts. The development of intelligent machines that can learn over extended periods of time, and that improve their abilities as they execute more tasks, is still a pending contribution from computer science to the world. This weakness has been recognised for some decades, and an interest to solve it seems to be increasing, as demonstrated by recent leading work and broader discussions at main events in the field [Chen and Liu, 2015; Chen et al., 2016]. Our research is intended to help fill that gap.
Learning Multi-faceted Knowledge Graph Embeddings for Natural Language Processing
Authors: Chen Muhao , Zaniolo Carlo
Published: July 2017

Knowledge graphs have challenged the present embedding-based approaches for representing their multifacetedness. To address some of the issues, we have investigated some novel approaches that (i) captures multilingual transitions on different language-specific versions of knowledge, and (ii) encodes the commonly existing monolingual knowledge with important relational properties and hierarchies. In addition, we propose the use of our approaches in a wide spectrum of NLP tasks that have not been well explored by related works.
Understanding and Measuring Collective Intelligence Across Different Cognitive Systems: An Information-Theoretic Approach
Authors: Chmait Nader
Published: July 2017

We develop the idea of collective intelligence by analysing a range of factors hindering the effectiveness of interactive cognitive agents. We give insights into how to explore the potential of collectives across different cognitive systems (human, animal and machine) and research areas. The endeavour is to bridge the different research disciplines in which collective intelligence might occur and apply the studies of intelligence in AI to other fields, thereby cross-fertilising diverse areas of study ranging from business and management to social sciences and fundamental biology.
SAT-Based Approaches for the General High School Timetabling Problem
Authors: Demirović Emir
Published: July 2017

High School Timetabling (HSTT) is a well known and widespread problem. It consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. lectures) with respect to various constraints. In this paper, I summarize the work I have done towards exploring the relationship between propositional logic and HSTT. This includes various modeling techniques in the form of maxSAT and bitvectors, data structures for local search algorithms, and the combination of maxSAT and metaheuristic algorithms. In addition, I discuss possible directions for future work as a part of a long-term research goal to combine complete and metaheuristic algorithms.
Resilient Control and Safety for Multi-Agent Cyber-Physical Systems
Authors: Lukina Anna
Published: July 2017

I develop novel intelligent approximation algorithms for solving modern problems of CPSs, such as control and verification, by combining advanced statistical methods. it is important for the control algorithms underlying the class of multi-agent CPSs to be resilient to various kinds of attacks, and so it is for my algorithms. I have designed a very general adaptive receding-horizon synthesis approach to planning and control that can be applied to controllable stochastic dynamical systems. Apart from being fast and efficient, it provides statistical guarantees of convergence. The optimization technique based on the best features of Model Predictive Control and Particle Swarm Optimization proves to be robust in finding a winning strategy in the stochastic non-cooperative games against a malicious attacker. The technique can further benefit probabilistic model checkers and real-world CPSs.
Stochastic Constraint Programming with And-Or Branch-and-Bound
Authors: Babaki Behrouz , Guns Tias , de Raedt Luc
Published: July 2017

Complex multi-stage decision making problems often involve uncertainty, for example, regarding demand or processing times. Stochastic constraint programming was proposed as a way to formulate and solve such decision problems, involving arbitrary constraints over both decision and random variables. What stochastic constraint programming still lacks is support for the use of factorized probabilistic models that are popular in the graphical model community. We show how a state-of-the-art probabilistic inference engine can be integrated into standard constraint solvers. The resulting approach searches over the And-Or search tree directly, and we investigate tight bounds on the expected utility objective. This significantly improves search efficiency and outperforms scenario-based methods that ground out the possible worlds.
Scalable Constraint-based Virtual Data Center Allocation
Authors: Bayless Sam , Kodirov Nodir , Beschastnikh Ivan , Hoos Holger H. , Hu Alan J.
Published: July 2017

Constraint-based techniques can solve challenging problems arising from highly diverse applications. This paper considers the problem of virtual data center (VDC) allocation, an important, emerging challenge for modern data center operators. To solve this problem, we introduce NETSOLVER, which is based on the general-purpose constraint solver MONOSAT. NETSOLVER represents a major improvement over existing approaches: it is sound, complete, and scalable, providing support for end-to-end, multi-path bandwidth guarantees across all the layers of hosting infrastructure, from servers to top-of-rack switches to aggregation switches to access routers. NETSOLVER scales to realistic data center sizes and VDC topologies, typically requiring just seconds to allocate VDCs of 5–15 virtual machines to physical data centers with 1000+ servers, maintaining this efficiency even when the data center is nearly saturated. In many cases, NETSOLVER can allocate 150%−300% as many total VDCs to the same physical data center as previous methods. Essential to our solution efficiency is our formulation of VDC allocation using monotonic theories, illustrating the practical value of the recently proposed SAT modulo monotonic theories approach.
Relaxed Exists-Step Plans in Planning as SMT
Authors: Bofill Miquel , Espasa Joan , Villaret Mateu
Published: July 2017

Planning Modulo Theories (PMT), inspired by Satisfiability Modulo Theories (SMT), allows the integration of arbitrary first order theories, such as linear arithmetic, with propositional planning. Under this setting, planning as SAT is generalized to planning as SMT. In this paper we introduce a new encoding for planning as SMT, which adheres to the relaxed relaxed ∃-step (R 2 ∃-step) semantics for parallel plans. We show the benefits of relaxing the requirements on the set of actions eligible to be executed at the same time, even though many redundant actions can be introduced. We also show how, by a MaxSMT based post-processing step, redundant actions can be efficiently removed, and provide experimental results showing the benefits of this approach.