bluuebunny/crossref_metadata_2025 huggingface dataset:
Distributed Constraint Optimization Under Stochastic Uncertainty
Authors: Léauté Thomas , Faltings Boi
Published: September 2022

In many real-life optimization problems involving multiple agents, the rewards are not necessarily known exactly in advance, but rather depend on sources of exogenous uncertainty. For instance, delivery companies might have to coordinate to choose who should serve which foreseen customer, under uncertainty in the locations of the customers. The framework of Distributed Constraint Optimization under Stochastic Uncertainty was proposed to model such problems; in this paper, we generalize this formalism by introducing the concept of evaluation functions that model various optimization criteria. We take the example of three such evaluation functions, expectation, consensus, and robustness, and we adapt and generalize two previous algorithms accordingly. Our experimental results on a class of Vehicle Routing Problems show that incomplete algorithms are not only cheaper than complete ones (in terms of simulated time, Non-Concurrent Constraint Checks, and information exchange), but they are also often able to find the optimal solution. We also show that exchanging more information about the dependencies of their respective cost functions on the sources of uncertainty can help the agents discover higher-quality solutions.
Limits of Preprocessing
Authors: Szeider Stefan
Published: September 2022

We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning. We show that, subject to a complexity theoretic assumption, none of the considered problems can be reduced by polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, such as induced width or backdoor size. Our results provide a firm theoretical boundary for the performance of polynomial-time preprocessing algorithms for the considered problems.
Succinct Set-Encoding for State-Space Search
Authors: Schmidt Tim , Zhou Rong
Published: September 2022

We introduce the level-ordered edge sequence (LOES), a suc- cinct encoding for state-sets based on prefix-trees. For use in state-space search, we give algorithms for member testing and element hashing with runtime dependent only on state- size, as well as space and memory efficient construction of and iteration over such sets. Finally we compare LOES to binary decision diagrams (BDDs) and explicitly packed set- representation over a range of IPC planning problems. Our results show LOES produces succinct set-encodings for a wider range of planning problems than both BDDs and ex- plicit state representation, increasing the number of problems that can be solved cost-optimally.
Planning in Domains with Cost Function Dependent Actions
Authors: Phillips Mike , Likhachev Maxim
Published: September 2022

In a number of graph search-based planning problems, the value of the cost function that is being minimized also affects the set of possible actions at some or all the states in the graph. For example, in path planning for a robot with a limited battery power, a common cost function is energy consumption, whereas the level of remaining energy affects the navigational capabilities of the robot. Similarly, in path planning for a robot navigating dynamic environments, a total traversal time is a common cost function whereas the timestep affects whether a particular transition is valid. In such planning problems, the cost function typically becomes one of the state variables thereby increasing the dimensionality of the planning problem, and consequently the size of the graph that represents the problem. In this paper, we show how to avoid this increase in the dimensionality for the planning problems whenever the availability of the actions is monotonically non-increasing with the increase in the cost function. We present three variants of A* search for dealing with such planning problems: a provably optimal version, a suboptimal version that scales to larger problems while maintaining a bound on suboptimality, and finally a version that relaxes our assumption on the relationship between the cost function and action space. Our experimental analysis on several domains shows that the presented algorithms achieve up to several orders of magnitude speed up over the alternative approaches to planning.
Cognitive Synergy between Procedural and Declarative Learning in the Control of Animated and Robotic Agents Using the OpenCogPrime AGI Architecture
Authors: Goertzel Ben , Pitt Joel , Wigmore Jared , Geisweiller Nil , Cai Zhenhua , Lian Ruiting , Huang Deheng , Yu Gino
Published: September 2022

The hypothesis is presented that "cognitive synergy" -- proactive and mutually-assistive feedback between different cognitive processes associated with different types of memory -- may serve as a foundation for advanced artificial general intelligence. A specific AI architecture founded on this idea, OpenCogPrime, is described, in the context of its application to control virtual agents and robots. The manifestations of cognitive synergy in OpenCogPrime's procedural and declarative learning algorithms are discussed in some detail.
Cross Media Entity Extraction and Linkage for Chemical Documents
Authors: Yan Su , Spangler Scott , Chen Ying
Published: September 2022

Text and images are two major sources of information in scientific literature. Information from these two media typically reinforce and complement each other, thus simplifying the process for human to extract and comprehend information. However, machines cannot create the links or have the semantic understanding between images and text. We propose to integrate text analysis and image processing techniques to bridge the gap between the two media, and discover knowledge from the combined information sources, which would be otherwise lost by traditional single-media based mining systems. The focus is on the chemical entity extraction task because images are well known to add value to the textual content in chemical literature. Annotation of US chemical patent documents demonstrates the effectiveness of our proposal.
Relational Blocking for Causal Discovery
Authors: Rattigan Matthew , Maier Marc , Jensen David
Published: September 2022

Blocking is a technique commonly used in manual statistical analysis to account for confounding variables. However, blocking is not currently used in automated learning algorithms. These algorithms rely solely on statistical conditioning as an operator to identify conditional independence. In this work, we present relational blocking as a new operator that can be used for learning the structure of causal models. We describe how blocking is enabled by relational data sets, where blocks are determined by the links in the network. By blocking on entities rather than conditioning on variables, relational blocking can account for both measured and unobserved variables. We explain the mechanism of these methods using graphical models and the semantics of d-separation. Finally, we demonstrate the effectiveness of relational blocking for use in causal discovery by showing how blocking can be used in the causal analysis of two real-world social media systems.
Causal Theories of Actions Revisited
Authors: Lin Fangzhen , Soutchanski Mikhail
Published: September 2022

It has been argued that causal rules are necessary for representing both implicit side-effects of actions and action qualifications, and there have been a number different approaches for representing causal rules in the area of formal theoriesof actions. These different approaches in general agree on rules without cycles. However, they differ on causal rules with mutual cyclic dependencies, both in terms of how these rules are supposed to be represented and their semantics. In this paper we show that by adding one more minimization to Lin's circumscriptive causal theory in the situation calculus, we can have a uniform representation of causal rules including those with cyclic dependencies. We also demonstrate that sometimes causal rules can be compiled into logically equivalent successor state axioms even in the presence of cyclical dependencies between fluents.
An Algebraic Prolog for Reasoning about Possible Worlds
Authors: Kimmig Angelika , Van den Broeck Guy , De Raedt Luc
Published: September 2022

We introduce aProbLog, a generalization of the probabilistic logic programming language ProbLog. An aProbLog program consists of a set of definite clauses and a set of algebraic facts; each such fact is labeled with an element of a semiring. A wide variety of labels is possible, ranging from probability values to reals (representing costs or utilities), polynomials, Boolean functions or data structures. The semiring is then used to calculate labels of possible worlds and of queries. We formally define the semantics of aProbLog and study the aProbLog inference problem, which is concerned with computing the label of a query. Two conditions are introduced that allow one to simplify the inference problem, resulting in four different algorithms and settings. Representative basic problems for each of these four settings are: is there a possible world where a query is true (SAT), how many such possible worlds are there (#SAT), what is the probability of a query being true (PROB), and what is the most likely world where the query is true (MPE). We further illustrate these settings with a number of tasks requiring more complex semirings.
Two-Dimensional Description Logics for Context-Based Semantic Interoperability
Authors: Klarman Szymon , Gutiérrez-Basulto Víctor
Published: September 2022

Description Logics (DLs) provide a clear and broadly accepted paradigm for modeling and reasoning about terminological knowledge. However, it has been often noted, that although DLs are well-suited for representing a single, global viewpoint on an application domain, they offer no formal grounding for dealing with knowledge pertaining to multiple heterogeneous viewpoints — a scenario ever more often approached in practical applications, e.g. concerned with reasoning over distributed knowledge sources on the Semantic Web. In this paper, we study a natural extension of DLs, in the style of two-dimensional modal logics, which supports declarative modeling of viewpoints as contexts, in the sense of McCarthy, and their semantic interoperability. The formalism is based on two-dimensional semantics, where one dimension represents a usual object domain and the other a (possibly infinite) domain of viewpoints, addressed by additional modal operators and a metalanguage, on the syntactic level. We systematically introduce a number of expressive fragments of the proposed logic, study their computational complexity and connections to related formalisms.
A Closer Look at the Probabilistic Description Logic Prob-EL
Authors: Gutiérrez Basulto Víctor , Jung Jean Christoph , Lutz Carsten , Schröder Lutz
Published: September 2022

We study probabilistic variants of the description logic EL. For the case where probabilities apply only to concepts, we provide a careful analysis of the borderline between tractability and ExpTime-completeness. One outcome is that any probability value except zero and one leads to intractability in the presence of general TBoxes, while this is not the case for classical TBoxes. For the case where probabilities can also be applied to roles, we show PSpace-completeness. This result is (positively) surprising as the best previously known upper bound was 2-ExpTime and there were reasons to believe in completeness for this class.
Refinement of Strong Stackelberg Equilibria in Security Games
Authors: An Bo , Tambe Milind , Ordonez Fernando , Shieh Eric , Kiekintveld Christopher
Published: September 2022

Given the real-world deployments of attacker-defender Stackelberg security games, robustness to deviations from expected attacker behaviors has now emerged as a critically important issue. This paper provides four key contributions in this context. First, it identifies a fundamentally problematic aspect of current algorithms for security games. It shows that there are many situations where these algorithms face multiple equilibria, and they arbitrarily select one that may hand the defender a significant disadvantage, particularly if the attacker deviates from its equilibrium strategies due to unknown constraints. Second, for important subclasses of security games, it identifies situations where we will face such multiple equilibria. Third, to address these problematic situations, it presents two equilibrium refinement algorithms that can optimize the defender's utility if the attacker deviates from equilibrium strategies. Finally, it experimentally illustrates that the refinement approach achieved significant robustness in consideration of attackers' deviation due to unknown constraints.
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems
Authors: Macarthur Kathryn , Stranders Ruben , Ramchurn Sarvapali , Jennings Nicholas
Published: September 2022

We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.
Complexity of and Algorithms for Borda Manipulation
Authors: Davies Jessica , Katsirelos George , Narodytska Nina , Walsh Toby
Published: September 2022

We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this NP-hardness, we treat computing a manipulation as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin packing and multiprocessor scheduling, we propose two new approximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly outperform the previous best known approximation method. We are able to find optimal manipulations in almost all the randomly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coalition is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.
Strategic Information Disclosure to People with Multiple Alternatives
Authors: Azaria Amos , Rabinovich Zinovi , Kraus Sarit , Goldman Claudia
Published: September 2022

This paper studies how automated agents can persuade humans to behave in certain ways. The motivation behind such agent's behavior resides in the utility function that the agent's designer wants to maximize and which may be different from the user's utility function. Specifically, in the strategic settings studied, the agent provides correct yet partial information about a state of the world that is unknown to the user but relevant to his decision. Persuasion games were designed to study interactions between automated players where one player sends state information to the other to persuade it to behave in a certain way. We show that this game theory based model is not sufficient to model human-agent interactions, since people tend to deviate from the rational choice. We use machine learning to model such deviation in people from this game theory based model. The agent generates a probabilistic description of the world state that maximizes its benefit and presents it to the users. The proposed model was evaluated in an extensive empirical study involving road selection tasks that differ in length, costs and congestion. Results showed that people's behavior indeed deviated significantly from the behavior predicted by the game theory based model. Moreover, the agent developed in our model performed better than an agent that followed the behavior dictated by the game-theoretical models.
Branch and Price for Multi-Agent Plan Recognition
Authors: Banerjee Bikramjit , Kraemer Landon
Published: September 2022

The problem of identifying the (dynamic) team structures and team behaviors from the observed activities of multiple agents is called Multi-Agent Plan Recognition (MAPR). We extend a recent formalization of this problem to accommodate a compact, partially ordered, multi-agent plan language, as well as complex plan execution models — particularly plan abandonment and activity interleaving. We adopt a branch and price approach to solve MAPR in such a challenging setting, and fully instantiate the (generic) pricing problem for MAPR. We show experimentally that this approach outperforms a recently proposed hypothesis pruning algorithm in two domains: multi-agent blocks word, and intrusion detection. The key benefit of the branch and price approach is its ability to grow the necessary component (occurrence) space from which the hypotheses are constructed, rather than begin with a fully enumerated component space that has an intractable size, and search it with pruning. Our formulation of MAPR has the broad objective of bringing mature Operations Research methodologies to bear upon MAPR, envisaged to have a similar impact as mature SAT-solvers had on planning.
On Expressing Value Externalities in Position Auctions
Authors: Constantin Florin , Rao Malvika , Huang Chien-Chung , Parkes David
Published: September 2022

We introduce a bidding language for expressing negative value externalities in position auctions for online advertising. The unit-bidder constraints (UBC) language allows a bidder to condition a bid on its allocated slot and on the slots allocated to other bidders. We introduce a natural extension of the Generalized Second Price (GSP) auction, the expressive GSP (eGSP) auction, that induces truthful revelation of constraints for a rich subclass of unit-bidder types, namely downward-monotonic UBC. We establish the existence of envy-free Nash equilibrium in eGSP under a further restriction to a subclass of exclusion constraints, for which the standard GSP has no pure strategy Nash equilibrium. The equilibrium results are obtained by reduction to equilibrium analysis for reserve price GSP (Even-Dar et al. 2008). In considering the winner determination problem, which is NP-hard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.
A Nonparametric Bayesian Model of Multi-Level Category Learning
Authors: Canini Kevin , Griffiths Thomas
Published: September 2022

Categories are often organized into hierarchical taxonomies, that is, tree structures where each node represents a labeled category, and a node's parent and children are, respectively, the category's supertype and subtypes. A natural question is whether it is possible to reconstruct category taxonomies in cases where we are not given explicit information about how categories are related to each other, but only a sample of observations of the members of each category. In this paper, we introduce a nonparametric Bayesian model of multi-level category learning, an extension of the hierarchical Dirichlet process (HDP) that we call the tree-HDP. We demonstrate the ability of the tree-HDP to reconstruct simulated datasets of artificial taxonomies, and show that it produces similar performance to human learners on a taxonomy inference task.
Symmetric Graph Regularized Constraint Propagation
Authors: Fu Zhenyong , Lu Zhiwu , Ip Horace , Peng Yuxin , Lu Hongtao
Published: September 2022

This paper presents a novel symmetric graph regularization framework for pairwise constraint propagation. We first decompose the challenging problem of pairwise constraint propagation into a series of two-class label propagation subproblems and then deal with these subproblems by quadratic optimization with symmetric graph regularization. More importantly, we clearly show that pairwise constraint propagation is actually equivalent to solving a Lyapunov matrix equation, which is widely used in Control Theory as a standard continuous-time equation. Different from most previous constraint propagation methods that suffer from severe limitations, our method can directly be applied to multi-class problem and also can effectively exploit both must-link and cannot-link constraints. The propagated constraints are further used to adjust the similarity between data points so that they can be incorporated into subsequent clustering. The proposed method has been tested in clustering tasks on six real-life data sets and then shown to achieve significant improvements with respect to the state of the arts.
Large Scale Spectral Clustering with Landmark-Based Representation
Authors: Chen Xinlei , Cai Deng
Published: September 2022

Spectral clustering is one of the most popular clustering approaches. Despite its good performance, it is limited in its applicability to large-scale problems due to its high computational complexity. Recently, many approaches have been proposed to accelerate the spectral clustering. Unfortunately, these methods usually sacrifice quite a lot information of the original data, thus result in a degradation of performance. In this paper, we propose a novel approach, called Landmark-based Spectral Clustering (LSC), for large scale clustering problems. Specifically, we select $p\ (\ll n)$ representative data points as the landmarks and represent the original data points as the linear combinations of these landmarks. The spectral embedding of the data can then be efficiently computed with the landmark-based representation. The proposed algorithm scales linearly with the problem size. Extensive experiments show the effectiveness and efficiency of our approach comparing to the state-of-the-art methods.
Value Function Approximation in Reinforcement Learning Using the Fourier Basis
Authors: Konidaris George , Osentoski Sarah , Thomas Philip
Published: September 2022

We describe the Fourier basis, a linear value function approximation scheme based on the Fourier series. We empirically demonstrate that it performs well compared to radial basis functions and the polynomial basis, the two most popular fixed bases for linear value function approximation, and is competitive with learned proto-value functions.
Transfer Learning by Structural Analogy
Authors: Wang Huayan , Yang Qiang
Published: September 2022

Transfer learning allows knowledge to be extracted from auxiliary domains and be used to enhance learning in a target domain. For transfer learning to be successful, it is critical to find the similarity between auxiliary and target domains, even when such mappings are not obvious. In this paper, we present a novel algorithm for finding the structural similarity between two domains, to enable transfer learning at a structured knowledge level. In particular, we address the problem of how to learn a non-trivial structural similarity mapping between two different domains when they are completely different on the representation level. This problem is challenging because we cannot directly compare features across domains. Our algorithm extracts the structural features within each domain and then maps the features into the Reproducing Kernel Hilbert Space (RKHS), such that the "structural dependencies" of features across domains can be estimated by kernel matrices of the features within each domain. By treating the analogues from both domains as equivalent, we can transfer knowledge to achieve a better understanding of the domains and improved performance for learning. We validate our approach on synthetic and real-world datasets.
Basis Function Discovery Using Spectral Clustering and Bisimulation Metrics
Authors: Comanici Gheorghe , Precup Doina
Published: September 2022

We study the problem of automatically generating features for function approximation in reinforcement learning. We build on the work of Mahadevan and his colleagues, who pioneered the use of spectral clustering methods for basis function construction. Their methods work on top of a graph that captures state adjacency. Instead, we use bisimulation metrics in order to provide state distances for spectral clustering. The advantage of these metrics is that they incorporate reward information in a natural way, in addition to the state transition information. We provide theoretical bounds on the quality of the obtained approximation, which justify the importance of incorporating reward information. We also demonstrate empirically that the approximation quality improves when bisimulation metrics are used instead of the state adjacency graph in the basis function construction process.
Automatic Group Sparse Coding
Authors: Wang Fei , Lee Noah , Sun Jimeng , Hu Jianying , Ebadollahi Shahram
Published: September 2022

Sparse Coding (SC), which models the data vectors as sparse linear combinations over basis vectors (i.e., dictionary), has been widely applied in machine learning, signal processing and neuroscience. Recently, one specific SC technique, Group Sparse Coding (GSC), has been proposed to learn a common dictionary over multiple different groups of data, where the data groups are assumed to be pre-defined. In practice, this may not always be the case. In this paper, we propose Automatic Group Sparse Coding (AutoGSC), which can (1) discover the hidden data groups; (2) learn a common dictionary over different data groups; and (3) learn an individual dictionary for each data group. Finally, we conduct experiments on both synthetic and real world data sets to demonstrate the effectiveness of AutoGSC, and compare it with traditional sparse coding and Nonnegative Matrix Factorization (NMF) methods.
Across-Model Collective Ensemble Classification
Authors: Eldardiry Hoda , Neville Jennifer
Published: September 2022

Ensemble classification methods that independently construct component models (e.g., bagging) improve accuracy over single models by reducing the error due to variance. Some work has been done to extend ensemble techniques for classification in relational domains by taking relational data characteristics or multiple link types into account during model construction. However, since these approaches follow the conventional approach to ensemble learning, they improve performance by reducing the error due to variance in learning. We note however, that variance in inference can be an additional source of error in relational methods that use collective classification, since inferred values are propagated during inference. We propose a novel ensemble mechanism for collective classification that reduces  both learning and inference variance, by incorporating prediction averaging into the collective inference process itself. We show that our proposed method significantly outperforms a straightforward relational ensemble baseline on both synthetic and real-world datasets.
The Influence of Emotion Expression on Perceptions of Trustworthiness in Negotiation
Authors: Antos Dimitrios , De Melo Celso , Gratch Jonathan , Grosz Barbara
Published: September 2022

When interacting with computer agents, people make inferences about various characteristics of these agents, such as their reliability and trustworthiness. These perceptions are significant, as they influence people's behavior towards the agents, and may foster or inhibit repeated interactions between them. In this paper we investigate whether computer agents can use the expression of emotion to influence human perceptions of trustworthiness. In particular, we study human-computer interactions within the context of a negotiation game, in which players make alternating offers to decide on how to divide a set of resources. A series of negotiation games between a human and several agents is then followed by a "trust game." In this game people have to choose one among several agents to interact with, as well as how much of their resources they will trust to it. Our results indicate that, among those agents that displayed emotion, those whose expression was in accord with their actions (strategy) during the negotiation game were generally preferred as partners in the trust game over those whose emotion expressions and actions did not mesh. Moreover, we observed that when emotion does not carry useful new information, it fails to strongly influence human decision-making behavior in a negotiation setting.
Grammatical Error Detection for Corrective Feedback Provision in Oral Conversations
Authors: Lee Sungjin , Noh Hyungjong , Lee Kyusong , Lee Gary Geunbae
Published: September 2022

The demand for computer-assisted language learning systems that can provide corrective feedback on language learners’ speaking has increased. However, it is not a trivial task to detect grammatical errors in oral conversations because of the unavoidable errors of automatic speech recognition systems. To provide corrective feedback, a novel method to detect grammatical errors in speaking performance is proposed. The proposed method consists of two sub-models: the grammaticality-checking model and the error-type classification model. We automatically generate grammatical errors that learners are likely to commit and construct error patterns based on the articulated errors. When a particular speech pattern is recognized, the grammaticality-checking model performs a binary classification based on the similarity between the error patterns and the recognition result using the confidence score. The error-type classification model chooses the error type based on the most similar error pattern and the error frequency extracted from a learner corpus. The grammaticality checking method largely outperformed the two comparative models by 56.36% and 42.61% in F-score while keeping the false positive rate very low. The error-type classification model exhibited very high performance with a 99.6% accuracy rate. Because high precision and a low false positive rate are important criteria for the language-tutoring setting, the proposed method will be helpful for intelligent computer-assisted language learning systems.
First-Order Logic with Counting for General Game Playing
Authors: Kaiser Lukasz , Stafiniak Lukasz
Published: September 2022

General Game Players (GGPs) are programs which can play an arbitrary game given only its rules and the Game Description Language (GDL) is a variant of Datalog used in GGP competitions to specify the rules. GDL inherits from Datalog the use of Horn clauses as rules and recursion, but it too requires stratification and does not allow to use quantifiers. We present an alternative formalism for game description which is based on first-order logic (FO). States of the game are represented by relational structures, legal moves by structure rewriting rules guarded by FO formulas, and the goals of the players by formulas which extend FO with counting. The advantage of our formalism comes from more explicit state representationcand from the use of quantifiers in formulas. We show how to exploit existential quantification in players' goals to generate heuristics for evaluating positions in the game. The derived heuristics are good enough for a basic alpha-beta agent to win against state of the art GGP.
WikiSimple: Automatic Simplification of Wikipedia Articles
Authors: Woodsend Kristian , Lapata Mirella
Published: September 2022

Text simplification aims to rewrite text into simpler versions and thus make information accessible to a broader audience (e.g., non-native speakers, children, and individuals with language impairments). In this paper, we propose a model that simplifies documents automatically while selecting their most important content and rewriting them in a simpler style. We learn content selection rules from same-topic Wikipedia articles written in the main encyclopedia and its Simple English variant. We also use the revision histories of Simple Wikipedia articles to learn a quasi-synchronous grammar of simplification rewrite rules. Based on an integer linear programming formulation, we develop a joint model where preferences based on content and style are optimized simultaneously. Experiments on simplifying main Wikipedia articles show that our method significantly reduces the reading difficulty, while still capturing the important content.
Leveraging Wikipedia Characteristics for Search and Candidate Generation in Question Answering
Authors: Chu-Carroll Jennifer , Fan James
Published: September 2022

Most existing Question Answering (QA) systems adopt a type-and-generate approach to candidate generation that relies on a pre-defined domain ontology. This paper describes a type independent search and candidate generation paradigm for QA that leverages Wikipedia characteristics. This approach is particularly useful for adapting QA systems to domains where reliable answer type identification and type-based answer extraction are not available. We present a three-pronged search approach motivated by relations an answer-justifying title-oriented document may have with the question/answer pair. We further show how Wikipedia metadata such as anchor texts and redirects can be utilized to effectively extract candidate answers from search results without a type ontology. Our experimental results show that our strategies obtained high binary recall in both search and candidate generation on TREC questions, a domain that has mature answer type extraction technology, as well as on Jeopardy! questions, a domain without such technology. Our high-recall search and candidate generation approach has also led to high overall QA performance in Watson, our end-to-end system.
Semantic Relatedness Using Salient Semantic Analysis
Authors: Hassan Samer , Mihalcea Rada
Published: September 2022

This paper introduces a novel method for measuring semantic relatedness using semantic profiles constructed from salient encyclopedic features. The model is built on the notion that the meaning of a word can be characterized by the salient concepts found in its immediate context. In addition to being computationally efficient, the new model has superior performance and remarkable consistency when compared to both knowledge-based and corpus-based state-of-the-art semantic relatedness models.
Tree Sequence Kernel for Natural Language
Authors: Sun Jun , Zhang Min , Tan Chew Lim
Published: September 2022

We propose Tree Sequence Kernel (TSK), which implicitly exhausts the structure features of a sequence of subtrees embedded in the phrasal parse tree. By incorporating the capability of sequence kernel, TSK enriches tree kernel with tree sequence features so that it may provide additional useful patterns for machine learning applications. Two approaches of penalizing the substructures are proposed and both can be accomplished by efficient algorithms via dynamic programming. Evaluations are performed on two natural language tasks, i.e. Question Classification and Relation Extraction. Experimental results suggest that TSK outperforms tree kernel for both tasks, which also reveals that the structure features made up of multiple subtrees are effective and play a complementary role to the single tree structure.
Comparing Action-Query Strategies in Semi-Autonomous Agents
Authors: Cohn Robert , Durfee Edmund , Singh Satinder
Published: September 2022

We consider settings in which a semi-autonomous agent has uncertain knowledge about its environment, but can ask what action the human operator would prefer taking in the current or in a potential future state. Asking queries can improve behavior, but if queries come at a cost (e.g., due to limited operator attention), the value of each query should be maximized. We compare two strategies for selecting action queries: 1) based on myopically maximizing expected gain in long-term value, and 2) based on myopically minimizing uncertainty in the agent's policy representation. We show empirically that the first strategy tends to select more valuable queries, and that a hybrid method can outperform either method alone in settings with limited computation.
Learning Tasks and Skills Together From a Human Teacher
Authors: Akgun Baris , Subramanian Kaushik , Shim Jaeeun , Thomaz Andrea
Published: September 2022

We are interested in developing Learning from Demonstration (LfD) systems that are tailored to be used by everyday people. We highlight and tackle the issues of skill learning, task learning and interaction in the context of LfD As part of the AAAI 2011 LfD Challenge, we will demonstrate some of our most recent Socially Guided-Machine Learning work, in which the PR2 robot learns both low-level skills and high-level tasks through an ongoing social dialog with a human partner
Generating Diverse Plans Using Quantitative and Qualitative Plan Distance Metrics
Authors: Coman Alexandra , Munoz-Avila Hector
Published: September 2022

Diversity-aware planning consists of generating multiple plans which, while solving the same problem, are dissimilar from one another. Quantitative plan diversity is domain-independent and does not require extensive knowledge-engineering effort, but can fail to reflect plan differences that are relevant to users. Qualitative plan diversity is based on domain-specific characteristics, thus being of greater practical value, but may require substantial knowledge engineering. We demonstrate a domain-independent diverse plan generation method that is based on customizable plan distance metrics and amenable to both quantitative and qualitative diversity. Qualitative plan diversity is obtained with minimal knowledge-engineering effort, using distance metrics which incorporate domain-specific content.
A POMDP Model of Eye-Hand Coordination
Authors: Erez Tom , Tramper Julian , Smart William , Gielen Stan
Published: September 2022

This paper presents a generative model of eye-hand coordination. We use numerical optimization to solve for the joint behavior of an eye and two hands, deriving a predicted motion pattern from first principles, without imposing heuristics. We model the planar scene as a POMDP with 17 continuous state dimensions. Belief-space optimization is facilitated by using a nominal-belief heuristic, whereby we assume (during planning) that the maximum likelihood observation is always obtained. Since a globally-optimal solution for such a high-dimensional domain is computationally intractable, we employ local optimization in the belief domain. By solving for a locally-optimal plan through belief space, we generate a motion pattern of mutual coordination between hands and eye: the eye's saccades disambiguate the scene in a task-relevant manner, and the hands' motions anticipate the eye's saccades. Finally, the model is validated through a behavioral experiment, in which human subjects perform the same eye-hand coordination task. We show how simulation is congruent with the experimental results.
Utilizing Partial Policies for Identifying Equivalence of Behavioral Models
Authors: Zeng Yifeng , Doshi Prashant , Pan Yinghui , Mao Hua , Chandrasekaran Muthukumaran , Luo Jian
Published: September 2022

We present a novel approach for identifying exact and approximate behavioral equivalence between models of agents. This is significant because both decision making and game play in multiagent settings must contend with behavioral models of other agents in order to predict their actions. One approach that reduces the complexity of the model space is to group models that are behaviorally equivalent. Identifying equivalence between models requires solving them and comparing entire policy trees. Because the trees grow exponentially with the horizon, our approach is to focus on partial policy trees for comparison and determining the distance between updated beliefs at the leaves of the trees. We propose a principled way to determine how much of the policy trees to consider, which trades off solution quality for efficiency. We investigate this approach in the context of the interactive dynamic influence diagram and evaluate its performance.
Abductive Markov Logic for Plan Recognition
Authors: Singla Parag , Mooney Raymond
Published: September 2022

Plan recognition is a form of abductive reasoning that involves inferring plans that best explain sets of observed actions. Most existing approaches to plan recognition and other abductive tasks employ either purely logical methods that donot handle uncertainty, or purely probabilistic methods thatdo not handle structured representations. To overcome these limitations, this paper introduces an approach to abductive reasoning using a ﬁrst-order probabilistic logic, speciﬁcally Markov Logic Networks (MLNs). It introduces several novel techniques for making MLNs efﬁcient and effective for abduction. Experiments on three plan recognition datasets showthe beneﬁt of our approach over existing methods.
Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks
Authors: Malone Brandon , Yuan Changhe , Hansen Eric
Published: September 2022

We describe a memory-efficient implementation of a dynamic programming algorithm for learning the optimal structure of a Bayesian network from training data. The algorithm leverages the layered structure of the dynamic programming graphs representing the recursive decomposition of the problem to reduce the memory requirements of the algorithm from O(n2n) to O(C(n, n/2)), where C(n, n/2) is the binomial coefficient. Experimental results show that the approach runs up to an order of magnitude faster and scales to datasets with more variables than previous approaches.
Probabilistic Plan Graph Heuristic for Probabilistic Planning
Authors: E-Martín Yolanda , R-Moreno Maria , Smith David
Published: September 2022

This work focuses on developing domain-independent heuristics for probabilistic planning problems characterized by full observability and non-deterministic effects of actions that are expressed by probability distributions. The approach is to first search for a high probability deterministic plan using a classical planner. A novel probabilistic plan graph heuristic is used to guide the search towards high probability plans. The resulting plans can be used in a system that handles unexpected outcomes by runtime replanning. The plans can also be incrementally augmented with contingency branches for the most critical action outcomes. This abstract will describe the steps that we have taken in completing the above work and the obtained results.
Solution Quality Improvements for Massively Multi-Agent Pathfinding
Authors: Wang Ko-Hsin , Botea Adi , Kilby Philip
Published: September 2022

MAPP has been previously shown as a state-of-the-art multi-agent path planning algorithm on criteria including scalability and success ratio (i.e., percentage of solved units) on realistic game maps. MAPP further provides a formal characterization of problems it can solve, and low-polynomial upper bounds on the resources required. However, until now, MAPP's solution quality had not been extensively analyzed. In this work we empirically analyze the quality of MAPP's solutions, using multiple quality criteria such as the total travel distance, the makespan and the sum of actions (including move and wait actions). We also introduce enhancements that improve MAPP's solution quality significantly. For example, the sum of actions is cut to half on average. The improved MAPP is competitive in terms of solution quality with FAR and WHCA*, two successful algorithms from the literature, and maintains its advantages on different performance criteria, such as scalability, success ratio, and ability to tell apriori if it will succeed in the instance at hand. As optimal algorithms have limited scalability, evaluating the quality of the solutions provided by suboptimal algorithms is another important topic. Using lower bounds of optimal values, we show that MAPP's solutions have a reasonable quality. For example, MAPP's total travel distance is on average 19% longer than a lower bound on the optimal value.
Large Scale Diagnosis Using Associations between System Outputs and Components
Authors: Guo Ting , Li Zhanshan , Guo Ruizhi , Zhu Xingquan
Published: September 2022

Model-based diagnosis (MBD) uses an abstraction of system to diagnose possible faulty functions of an underlying system. To improve the solution efficiency for multi-fault diagnosis problems, especially for large scale systems, this paper proposes a method to induce reasonable diagnosis solutions, under coarse diagnosis, by using the relationships between system outputs and components. Compared to existing diagnosis methods, the proposed framework only needs to consider associations between outputs and components by using an assumption-based truth maintenance system (ATMS) [de Kleer 1986] to obtain correlation components for every output node. As a result, our method significantly reduces the number of variables required for model diagnosis, which makes it suitable for large scale circuit systems.
High aspect in the English be going to construction: Syntactic evidence
Authors: Duncan Daniel
Published: September 2022

Research into the syntax of English be going to has typically focused on how going to relates to gonna, but work has tended to focus less on the location and structure of the construction within the clausal spine. This paper compares two competing hypotheses for this location: the high aspect account, in which going to/gonna is a modal with be in a high functional head above it, and the little v account, in which future be going to is quite similar to the progressive main verb in structure. I observe that these proposals make contrasting predictions regarding additional material in the inflectional domain: the high aspect account prohibits future be going to from being preceded by a modal or have, while the little v account makes no such restriction. The synchronic accounts likewise represent differing views on the diachronic grammaticalization process. I test these predictions in two online experiments: a task in which participants determine the grammaticality of sentences containing be gonna, and a task in which participants determine whether sentences containing be going to take a future or motion reading. Results show that be gonna is ungrammatical when preceded by modals/perfect, and be going to takes more of a motion reading in the same context. Both tasks strongly favor the high aspect account. This supports syntactic approaches to grammaticalization that take items to move into and up the clausal spine.
New locations of the rare species Cotoneaster uralensis (Rosaceae) in the Polar Urals
Authors:   Institute for Biological Problems of Cryolithozone Sibirian Branch of RAS, Nikolin Evgenii G.
Published: September 2022

The study reveals and identifies a new distribution point of a rare plant endemic to the Middle, Circumpolar and Polar Urals, – Cotoneaster uralensis. The plant is listed in the regional Red Books of the Russian Federation – namely the Red Books of YANAO and H-MAO. The location of this species installed in the upper river Krestovaya (tributary of the Langotyugan river), close to the centerline of the Polar Urals, on the Western border of the Yamalo-Nenets Autonomous district (YANAO) of the Russian Federation. The article contains coordinates of this point and a brief description of the area. The new discovery of the species eliminates the gap in the distribution of C. uralensis between its 2 northernmost points and 7 points to the south known currently.